(57)【特許請求の範囲】
【請求項１】
無線通信システムにおける低密度パリティチェック符号(ＬＤＰＣ)デコーダであって、
複数の変数ノードと前記複数の変数ノードの各々に対応する一つ以上のチェックノードとの間の各エッジを通じて伝送されるメッセージを格納するエッジメモリと、
前記各エッジに接続されたチェックノードに対応する振幅値と符号(sign)値を有するチェックノード値を格納するノードメモリと、
前記ノードメモリ及び前記エッジメモリのうち少なくとも一つに格納された情報を用いて前記複数の変数ノードのうち予め設定された一つの変数ノードに接続されるエッジのチェックノード出力(Ｃ２Ｖ)メッセージ及び新たなチェックノード値を生成し、前記生成されたチェックノード値を前記ノードメモリに貯蔵し、前記生成されたチェックノード出力メッセージを前記エッジメモリに格納し、前記格納されたチェックノード出力メッセージを用いて前記予め設定された一つの変数ノードのエッジに接続された変数ノード出力メッセージ(Ｖ２Ｃ)を生成し、各変数ノード別前記変数ノード出力メッセージの生成を反復する復号化動作を遂行するノード処理器と、を含み、
前記ノード処理器は、前記ノードメモリに格納されたチェックノード値の符号値に従って前記復号化動作を終了することを特徴とするＬＤＰＣデコーダ。
【請求項２】
前記振幅がｑｃであり、前記符号がｐｃである場合に、前記振幅と符号は下記の数式のように初期化されることを特徴とする請求項１に記載のＬＤＰＣデコーダ。
【数１】
0004402699.tif 000011
ここで、ｖ，ｃは変数ノード及びチェックノードを各々示し、Ｖ(ｃ)はｃ番目のチェックノードに近接した変数ノードのインデックス集合を示し、Ｃ(ｖ)はｖ番目の変数ノードに近接したチェックノードのインデックス集合を示し、ｓｇｎ(ｘ)はｘ値が０より小さい場合に−１(ｓｇｎ(ｘ)＝−１、ｘ＜０)、ｘ値が０以上である場合に＋１(ｓｇｎ(ｘ)＝＋１、ｘ≧０)を示し、
【数２】
0004402699.tif 000012
はｖ番目の変数ノードからｃ番目のチェックノードに伝送されるメッセージを示す。
【請求項３】
前記ノードメモリと前記エッジメモリにそれぞれ格納されるチェックノード値とチェックノード出力メッセージは、ノード基盤の直列スケジューリング方式によってアップデートされることを特徴とする請求項１記載のＬＤＰＣデコーダ。
【請求項４】
前記符号値は、前記チェックノード値が０以上であるか否かを示し、すべてのチェックノード値の符号値が、該当チェックノード値が０以上であることを示す場合に前記復号化動作を終了することを特徴とする請求項１記載のＬＤＰＣデコーダ。
【請求項５】
前記ノードメモリに格納されるチェックノード値は、前記変数ノード出力メッセージ及び入力ＬＬＲ(Log-Likelihood Ratio)の値と異なるビット精密度(bit  precision)を有することを特徴とする請求項１記載のＬＤＰＣデコーダ。
【請求項６】
前記ノードメモリと前記エッジメモリのうち少なくとも一つはメモリバンク(memory  bank)で構成されることを特徴とする請求項１記載のＬＤＰＣデコーダ。
【請求項７】
前記メモリバンクの個数が最大変数のノード次数であることを特徴とする請求項６記載のＬＤＰＣデコーダ。
【請求項８】
前記ノードメモリに格納されたチェックノード値と前記エッジメモリに格納されたチェックノード出力メッセージのうち少なくとも一つは、パイプライン構造によってサイクルごとに予め設定された変数ノードの個数だけアップデートされることを特徴とする請求項１記載のＬＤＰＣデコーダ。
【請求項９】
前記ＬＤＰＣデコーダは、
置換動作を通じて前記ノードメモリと前記ノード処理器の出力をスイッチングするスイッチと、
前記ノードメモリからの出力をパリティチェックするパリティチェック検証器と、
前記ノード処理器を制御するための制御信号を提供する制御部と、
をさらに含むことを特徴とする請求項１に記載のＬＤＰＣデコーダ。
【請求項１０】
前記スイッチは、
前記ノード処理器からの出力メッセージをスイッチングして前記ノードメモリに伝達する第１のスイッチと、
前記ノードメモリからの出力をスイッチングして前記ノード処理器に伝達する第２のスイッチと、
を含むことを特徴とする請求項９に記載のＬＤＰＣデコーダ。
【請求項１１】
前記スイッチは、前記ノードメモリと前記ノード処理器との間に位置することを特徴とする請求項９に記載のＬＤＰＣデコーダ。
【請求項１２】
前記パリティチェック検証器は、前記チェックノード値の符号を確認して前記ノードメモリからの出力をチェックすることを特徴とする請求項９に記載のＬＤＰＣデコーダ。
【請求項１３】
前記制御信号は、前記複数の変数ノード各々の順序を指定する指定信号及び前記ＬＤＰＣデコーダの終結信号のうちの少なくとも一つを含むことを特徴とする請求項９記載のＬＤＰＣデコーダ。
【請求項１４】
前記指定信号は、
前記複数の変数ノード各々の次数によってアップデート順序を決定する信号及び前記エッジの接続形態により前記複数の変数ノード各々のアップデート順序を決定する信号のうちいずれか一つを含むことを特徴とする請求項１３記載のＬＤＰＣデコーダ。
【請求項１５】
通信システムにおける低密度パリティチェック符号(ＬＤＰＣ)復号方法であって、
複数の変数ノードのうち、アップデートする変数ノード及び前記変数ノードを一つ以上のチェックノードに接続するエッジのチェックノード値を設定し、前記設定された変数ノードに対応する変数ノードメッセージと前記チェックノード値を格納する段階と、
前記格納されたチェックノード値を用いて前記一つ以上のチェックノードのメッセージを生成する段階と、
前記生成された一つ以上のチェックノードのメッセージを用いて前記変数ノードのメッセージ及び前記チェックノード値をアップデートし、前記アップデートされた変数ノードのメッセージ及び前記チェックノード値を格納する段階と、
前記アップデートして格納された変数ノードのメッセージ及びエッジの値を使用して次にアップデートして格納する変数ノードのメッセージ及び前記次にアップデートして格納する変数ノードとエッジによって接続される少なくとも一つのチェックノードのメッセージを生成し、
前記格納されたチェックノード値の符号(sign)値に基づいて前記変数ノードメッセージ及び前記チェックノード値のアップデートによる復号化動作を終了する段階と、を有し、
前記チェックノード値は、前記各エッジに接続されたチェックノードに対応する振幅値と前記符号値を含むことを特徴とするＬＤＰＣ復号方法。
【請求項１６】
前記アップデートする段階は、
変数ノード基盤の直列スケジューリング方式を使用して前記変数ノードのメッセージと前記チェックノード値をアップデートして格納する段階であることを特徴とする請求項１５記載のＬＤＰＣ復号方法。
【請求項１７】
前記格納されたチェックノード値は、前記格納された変数ノードメッセージ及び入力ＬＬＲ(Log-Likelihood Ratio)の値と異なるビット精密度を有することを特徴とする請求項１５記載のＬＤＰＣ復号方法。
【請求項１８】
前記アップデートされた変数ノードのメッセージを格納するメモリ及び前記アップデートされたチェックノード値を格納するメモリのうち少なくとも一つは、メモリバンクで構成されることを特徴とする請求項１７記載のＬＤＰＣ復号方法。
【請求項１９】
前記メモリバンクの個数が前記アップデートする変数ノードの最大次数であることを特徴とする請求項１８記載のＬＤＰＣ復号方法。
【請求項２０】
前記格納された変数ノードのメッセージ及び前記格納されたチェックノード値のうち少なくとも一つは、サイクルごとに予め設定された変数ノードの個数だけアップデートされることを特徴とする請求項１５記載のＬＤＰＣ復号方法。
【請求項２１】
前記復号化動作を終了する段階は、
すべてのチェックノード値の符号値が０以上であることを示す場合に、復号化動作を終了する段階を有し、前記符号値は前記チェックノード値が０以上であるか否かを示すことを特徴とする請求項１５記載のＬＤＰＣ復号方法。
【請求項２２】
前記複数の変数ノード及び複数のチェックノード値のアップデート順序を制御する制御信号を生成する段階
をさらに有することを特徴とする請求項１５記載のＬＤＰＣ復号方法。
【請求項２３】
前記制御信号は、前記複数の変数ノードのアップデート順序を指定する指定信号及びデコーダの終結信号のうちの少なくとも一つを含むことを特徴とする請求項２２記載のＬＤＰＣ復号方法。
【請求項２４】
前記指定信号は、前記複数の変数ノードの次数により前記複数の変数ノードのアップデート順序を決定する信号及び前記エッジの接続形態により前記複数の変数ノードのアップデート順序を決定する信号のうちのいずれか一つを含むことを特徴とする請求項２３記載のＬＤＰＣ復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は低密度パリティチェック(Low-Density Parity Check：以下、“ＬＤＰＣ”とする)デコーダに関するもので、特にノードメモリ構造に基づいた効率的なＬＤＰＣデコーダ及び復号方法に関するものである。
【背景技術】
【０００２】
Ｇａｌｌａｇｅｒによって最初に提案されたＬＤＰＣ符号は、ＭａｃＫａｙらによって再発見されて積和(sum-product)アルゴリズムに基づいた確率伝搬復号(belief propagation decoding)によって、Ｓｈａｎｎｏｎの容量限界に近接する優れた性能を示す符号として注目されている。
以後、Ｒｉｃｈａｒｄｓｏｎらは、ＬＤＰＣ符号を構成するファクターグラフ(factor graph)上で復号過程中に生成、アップデートされるメッセージの確率分布(probability distribution)によって変化することを追跡する密度拡散(density evolution)技法を提案した。また、これを用いて、サイクルフリー(cycle free）のファクターグラフ上で無限大の反復を仮定したとき、誤り確率を‘０’に収束可能にするチャンネルパラメーター(例えば、しきい値(threshold))を最大化できるファクターグラフの変数とチェックノードの次数分布(degree distribution)を提案した。そして、このような場合がサイクルが存在する有限な長さのＬＤＰＣ符号に対しても適用可能であることを理論的に提示した。このような密度拡散技法を用いて不規則ＬＤＰＣ符号の理論的なチャンネル容量がＳｈａｎｎｏｎ限界に僅か０.００４５ｄＢまで近接できることを示した。
【０００３】
一方、ＬＤＰＣ符号は、コード自体の特性上パケットサイズ(packet size)が大きいほど性能が増加するため、これによって符号/復号過程が複雑になりうる。最近、Ｆｌａｒｉｏｎ社は、パケットサイズが大きい場合にも低いハードウェア複雑度で実現できるマルチエッジタイプベクトル(multi-edge type vector)ＬＤＰＣ符号を提案したところである。上記のベクトルＬＤＰＣ、例えばブロックＬＤＰＣ(ＢＬＤＰＣ)は、小さなサイズの基本マトリックスＨ、例えばチェックマトリックス(check matrix)にもベクトル化した構造を用いて並列実現を通じて効率的なエンコーダ/デコーダの実現が可能な符号である。ＢＬＤＰＣの並列ファクターによる並列実現は、他のコード、例えばターボコード(Turbo code)、畳み込みコード(Convolutional code)などに比べて高い処理率(throughput）を有するデコーダの実現が可能にするため、データ率(data rate）が飛躍的に増加する次世代移動通信システムで、上記のような基本コードを代替することが可能な代案として議論されている。
【０００４】
このようなＬＤＰＣ符号は、一般的な線形ブロックコードの特殊な場合であり、パリティチェックマトリックス(parity check matrix）に定義される。
図１は、一般的なＬＤＰＣ符号のタナーグラフとパリティチェックマトリックスを示す。同図に、２個の情報ビットＫと３個のパリティビットの場合において、タナーグラフ(Tanner graph)とパリティチェックマトリックスＨを示す。
図１を参照すると、グラフ上で変数ノード(Variable node)は、符号語(codeword）の各ビットを示し、チェックノード(Check node)は一つのチェック方程式(equation）を示す。したがって、変数ノードの数は、符号語の長さ(length)、すなわちマトリックスＨの列サイズ(column size)を示し、チェックノードの数はパリティビット(parity bit）の数、すなわちマトリックスＨの行サイズ(row size)を示す。したがって、図１には符号率２/５のＬＤＰＣ符号を一例として示す。このようなタナーグラフ上で、各ノードを接続するエッジ(edge）はマトリックスＨにおける‘１’を示す。
【０００５】
図２は、一般的なメッセージパッシングによるデコーダの動作を説明するために示す。
図２を参照すると、一般的なＬＤＰＣ符号のデコーダは、二分グラフ(bipartite graph)上でメッセージパッシング(message-passing）の概念で説明可能であるが、このデコーダは、図２のように変数ノードとチェックノードとの間のメッセージ、すなわち外部情報(extrinsic information)を相互に交換しつつ反復(iterative)演算方式で動作する。
図２に示すように、
【０００６】
【数１】
0004402699.tif 000002
【０００７】
はｊ番目の変数ノードからｉ番目のチェックノードに伝達されるメッセージを示すもので、変数ノード処理器(variable node processor）の動作によって生成される。また、
【０００８】
【数２】
0004402699.tif 000003
【０００９】
は、ｉ番目のチェックノードからｊ番目の変数ノードに伝達されるメッセージを示し、チェックノード処理器(check node processor）の動作によって生成される。
一般的に知られている積和アルゴリズムの場合に、各メッセージの生成は、下記の＜数式（１）＞及び＜数式（２）＞のように表わされる。
【００１０】
【数３】
0004402699.tif 000004
【００１１】
【数４】
0004402699.tif 000005
【００１２】
上記の＜数式（１）＞は変数ノード処理器のメッセージ生成のための数式を、＜数式（２）＞はチェックノード処理器のメッセージ生成のための数式を、それぞれ示す。
＜数式（１）＞に示すように、yjはｊ番目の変数ノード、すなわちｊ番目の受信ビットに該当するＬＬＲ(Log-Likelihood Ratio)を、Ｃ(ｊ）はｊ番目の変数ノードに接続されたチェックノードのインデックス集合を、Ｖ(ｉ）はｉ番目のチェックノードに接続された変数ノードのインデックス集合を、それぞれ示す。
＜数式（２）＞に示すように、ｐはメッセージｍの符号(sign)、例えば‘＋１’又は‘-１’を、ｑはメッセージｍの振幅をそれぞれ示し、ｘ>＝０である場合にＦ(ｘ)＝-log(tanh(ｘ/２))、ｘ<０である場合にＦ(ｘ)＝＋log(tanh(-ｘ/２))を示す。
以上に説明したように、メッセージパッシングアルゴリズムで動作する一般的なＬＤＰＣデコーダは、上記の反復演算過程を経て情報ビットを復号する。
【００１３】
次に、ブロックＬＤＰＣは基本のマトリックスＨの拡張によって得られ、これについては下記の図３を参照して説明する。
図３は、一般的なブロックＬＤＰＣのグラフ形態及びチェックマトリックスを示す。
まず、図３は、上記した図１で使用されたマトリックスＨを並列要素Ｚだけ拡張して示すもので、一例としてＺ＝２である場合を示す。Ｚ＝２である場合に、符号語(codeword）の長さが２倍に拡張された。このような場合に、マトリックスＨは、既存の基本マトリックスＨで各要素をＺ×Ｚマトリックスで示すことができる。
まず、図３の左側に示すように、図１に示したマトリックスＨを単純拡張した場合に、単位マトリックス(identity matrix)は‘１’に位置される。しかしながら、このような場合にグラフで各階層(layer)間に情報の交換がないので、符号語長さが長くなるだけの符号化利得(coding gain）が得られない。したがって、図３の右側に示すように、エッジ置換(edge permutation)を通じて階層間にエッジの接続を任意に行う。これは、基本マトリックスＨで‘１’に該当する位置に単位マトリックスの代わりに置換マトリックス(permutation matrix)を使用することと同様である。以上のように、ブロックＬＤＰＣにおけるデコーダは、Ｚ単位で並列処理されることによって、処理率の向上と共に、制御オーバーヘッド(control overhead)の減少が可能になる。
【００１４】
一方、上記したようなデコーダは、ノードメッセージを交換するとき、各エッジのＶ２Ｃメッセージ、すなわち変数ノードの出力メッセージ(outgoing message)とＣ２Ｖメッセージ、すなわちチェックノードの出力メッセージを生成する。
一般的なメッセージパッシングデコーダは、エッジメッセージのアップデート順序に関係なく動作できる。ここで、スケジューリング方式は、エッジメッセージのアップデート順序を決定することで、デコーダの反復による収束速度に影響を及ぼす。
【００１５】
広く使用されているスケジューリング方式としては、フラッディングスケジューリング(flooding scheduling）と直列スケジューリング(serial scheduling)方式などがある。フラッディングスケジューリング方式は、すべてのＶ２Ｃメッセージをアップデートした後にすべてのＣ２Ｖメッセージをアップデートする方式である。そして、直列スケジューリング方式は、ノード基盤の動作を遂行する方式である。
なお、この直列スケジューリング方式は、変数ノード基盤(variable node based)方式とチェックノード基盤(check node based)方式に分けられる。
チェックノード基盤の直列スケジューリング方式は、一つのチェックノードに接続された出力メッセージＣ２Ｖをアップデートするために必要な入力メッセージ(incoming message)Ｖ２Ｃをまずアップデートする。一つのチェックノードに接続された出力メッセージがすべてアップデートされると、次のチェックノードに移動させた後にアップデートし、このような動作を繰り返して遂行する。同様に、変数ノード基盤の直列スケジューリング方式も上記のように動作が遂行されることができる。
【００１６】
図４は、従来の技術によるデコーダの構成を示す。
図４は、一つのベクトルノード処理器(Vector Node Processor：以下、“ＶＮＰＶＮＰ”とする)とベクトルエッジメッセージメモリ(Vector Edge Message Memory：以下、“ＶＭＭ”とする)で実現された従来のデコーダの実現例を示す。
ＶＮＰは、少なくとも一つのノード処理器ユニットを含んでおり、各ノード処理器ユニットはＺ回の演算を遂行する。また、ＶＮＰは、制御信号により変数ノード又はチェックノードの演算を遂行することができる。デコーダは、一つのＶＭＭをもってＶ２ＣとＣ２Ｖメッセージをすべて格納しなければならない。したがって、このような構造では、上記したようなフラッディングスケジューリング方式だけが適用されることができる。
例えば、ＶＮＰが変数ノード処理器として動作を始めるときに、ＶＭＭにはＣ２Ｖメッセージが格納されている。したがって、ＶＮＰが１番目の変数ノードに対する出力メッセージＶ２Ｃをアップデートするために、ＶＭＭに格納されているＣ２Ｖメッセージを読み出して出力メッセージを計算した後、読み取り動作を遂行したメモリアドレスにＶ２Ｃメッセージを格納する。
上記のように、すべての変数ノードに対する演算を遂行すると、ＶＭＭは、すべてＶ２Ｃメッセージにアップデートされる。その後、ＶＮＰは、制御信号の動作によってチェックノード処理器の動作を遂行する。すなわち、各エッジ当り一つのメモリでＶ２ＣとＣ２Ｖメッセージをすべて格納及び処理するためにはフラッディングスケジューリング技法だけが可能である。
【００１７】
また、ＶＮＰとＶＭＭとの間に存在するスイッチング装置(switching device）は、一例として図３に示したような各階層間のエッジ置換を遂行する。
この場合に、従来のデコーダの構造では、一個のＶＮＰで順次的な演算を遂行するので、メモリが小さく、ハードウェアが簡単な反面、デコーダの処理率が遅いという問題点が伴う。これについては、後述する図６Ａ及び図６Ｂを参照して具体的に説明するため、ここではその詳細な説明を省略する。
【００１８】
図５は、従来技術によるデコーダの構成を他の例として示す。特に、図５では、２個のＶＮＰを使用するデコーダの場合を例に挙げて説明する。
図５に示すように、それぞれのＶＮＰは、変数ノード又はチェックノード処理器の役割だけを遂行し、２個の処理器が同時に動作することによって復号処理率(decoding throughput）を向上可能にする。上記と同様に、ＶＮＰとＶＭＭとの間に存在するスイッチング装置は、一例として図３に示したような各階層間のエッジ置換を遂行する。しかしながら、図５のような構造を有するデコーダは、Ｃ２ＶとＶ２Ｃメッセージを格納するためのメモリが各々必要となる。したがって、メモリが、上記した図４に示した構造に比べて２倍増加、すなわちハードウェア個数の増加が２倍になって物理的体積が大きくなるという問題点がある。
したがって、複雑度を低下させつつ速い処理率を達成できるデコーダの設計及びその実現方法が要求される。
【非特許文献１】R. G. Gallger著、“Low-density parity-check code”、IRE Transaction on Information Theory、（米国）、IEEE、1962年1月、p. 21-28
【発明の開示】
【発明が解決しようとする課題】
【００１９】
したがって、上述した従来技術の問題点を解決するために案出された本発明の目的は、デコーダの複雑度を低下させ、かつ速い処理率を達成することができるデコーダ及びその実現方法を提供することにある。
本発明の他の目的は、メッセージメモリを別に使用することより、メモリの使用量を減少し、ベクトルノード処理器を利用しつつ速い処理率を達成することができるノードメモリ基盤のＬＤＰＣデコーダ及び復号方法を提供することにある。
【課題を解決するための手段】
【００２０】
上記のような目的を達成するために、本発明は、無線通信システムにおける低密度パリティチェック符号(ＬＤＰＣ)デコーダであって、変数ノードとチェックノードとの間のエッジを通じて伝送されるメッセージを格納するエッジメモリと、チェックノード値を格納するノードメモリと、前記ノードメモリ及び前記エッジメモリのうち少なくとも一つに格納された情報を用いてノード処理動作を遂行し、前記ノード処理動作を遂行して生成されたチェックノード値を前記ノードメモリに貯蔵し、前記ノード処理動作を遂行して生成されたメッセージを前記エッジメモリに格納するノード処理器と、置換動作を通じてノードメモリと前記ノード処理器の出力をスイッチングするスイッチと、前記ノードメモリからの出力をパリティチェックするパリティチェック検証器と、前記ノード処理器を制御するための制御信号を提供する制御部とを含むことを特徴とする。
【００２１】
また、本発明は、通信システムにおける低密度パリティチェック符号(ＬＤＰＣ)デコーダであって、チェックノード値を格納するノードメモリと、ノード処理動作を遂行し、前記ノード処理動作により前記ノードメモリに格納されるノード値を生成するノード処理器と、前記ノードメモリと前記ノード処理器との間に位置し、置換動作を通じてノードメモリと前記ノード処理器の出力をスイッチングするスイッチとを含むことを特徴とする。
【００２２】
さらに、本発明は、通信システムにおける低密度パリティチェック符号(ＬＤＰＣ)復号方法であって、変数ノードとチェックノード及びエッジを初期化する段階と、前記ノード及びエッジメッセージのうち、少なくとも一つを以前にアップデートされたエッジ及びノードのメッセージ値にアップデートする段階と、前記アップデートされたエッジメッセージ又はアップデートされたノードメッセージを格納する段階とを有することを特徴とする。
【発明の効果】
【００２３】
本発明の実施形態によるＬＤＰＣデコーダ及びその復号方法は、既存のフラッディングスケジューリング方式に比べてデコーダの反復による収束速度を大幅に増加させ、今後の次世代移動通信システムにおける必須事項となる高いデータ率の伝送が可能である効果がある。また、本発明の実施形態によるＬＤＰＣデコーダ及び復号方法は、メモリの使用量を減少しながらも復号化処理率を向上させることができる効果もある。
【発明を実施するための最良の形態】
【００２４】
以下、本発明の望ましい実施形態を添付の図面を参照して詳細に説明する。
下記に、本発明に関連した公知の機能又は構成に関する具体的な説明が本発明の要旨を不明にすると判断された場合に、その詳細な説明を省略する。
【００２５】
本発明は、変数ノード基盤の直列スケジューリング方式でメッセージパッシング復号化(message passing decoding）を遂行するデコーダ(decoder）の実現方式及び装置に関するものである。特に、本発明の実施形態では、一つのメッセージメモリＶ２Ｃを使用し、別途のＣ２Ｖエッジメッセージメモリを使用しない方式であって、Ｃ２Ｖメッセージメモリと差別化されるチェックノードメモリを使用する。
本発明の実施形態によるチェックノードメモリは、一つのチェックノード(check node)ごとに所定の代表値を格納しており、メモリ要素(memory element)の数はチェックノードの数と同一である。
したがって、本発明の実施形態では、上記の図５に示したように、Ｖ２ＣとＣ２Ｖエッジメッセージメモリを別途に使用することよりも、メモリの使用量を減少することができる。また、本発明の実施形態によると、変数ノード処理器でＶ２Ｃメッセージをアップデートするために関連したＣ２Ｖメッセージを注文型(on-demand)に生成する。これによって、上記の図４に示した場合と異なり、一つのベクトルノード処理器(Vector Node Processor：以下、“ＶＮＰ”とする)だけでも速い処理率(throughput）を実現することができる。
以上のように、提案する本発明の実施形態は、変数ノード基盤の直列スケジューリング方式でメッセージパッシング符号化を遂行するデコーダの実現方法及び装置に関するもので、本発明の実施形態によるデコーダの望ましい動作実施形態を添付の図面を参照して説明する。
【００２６】
本発明の説明に先立ち、従来から提案されたデコーダの動作について下記の図６Ａ及び図６Ｂを通じて説明する。
図６Ａ及び図６Ｂは、一般的なデコーダで使用されるフラッディングスケジューリング方式を示す。
図６Ａ及び図６Ｂを参照すると、従来のフラッディングスケジューリング方式は、変数ノード処理器(Ｖ２Ｃメッセージの生成)とチェックノード処理器(Ｃ２Ｖメッセージの生成)が順次に動作する。すなわち、デコーダは、まず図６Ａに示すように、すべてのエッジのＶ２Ｃメッセージをすべてアップデートした後に、図６Ｂに示すようにすべてのＣ２Ｖメッセージをアップデートする。
このような構造では、変数ノードとチェックノードの値をやりとりするとき、他のノードの値を使用しない。例えば、Ｖ２Ｃメッセージを生成する場合にＣ２Ｖメッセージを用いるが、この場合に用いられるＣ２Ｖメッセージは、以前の反復過程でのチェックノード処理器によってアップデートされたものである。すなわち、従来技術では、Ｖ２Ｃメッセージをアップデートする過程で、まずアップデートされたＶ２Ｃメッセージを用いてＣ２Ｖメッセージをアップデートすることができなかった。
【００２７】
図７Ａ〜図７Ｆは、本発明によるデコーダで使用するノードメモリ基盤の直列スケジューリング方式を示す。
図７Ａ〜図７Ｆを参照すると、本発明によるＬＤＰＣ復号方法は、アップデートされたメッセージを用いてこれに関連したメッセージをまずアップデートすることによって、デコーダの性能、すなわち収束速度を向上させることができる。すなわち、１番目の変数ノードのＶ２Ｃメッセージをアップデートするときに、ＬＤＰＣ復号方法は、図７Ａに示すように、第１の変数ノードに接続されたエッジ(例えば、エッジａ，ｂ）のＣ２Ｖメッセージを予め獲得しなければならない。
次に、図７Ｂに示すように、ＬＤＰＣ復号方法は、１番目の変数ノードにかかるＣ２Ｖメッセージを獲得すると、変数ノードに接続されたエッジ、すなわちエッジａ、ｂ(点線部分)のＣ２Ｖメッセージをアップデートするために第１及び第２のチェックノード処理器の動作によってメッセージを生成する。
以後、図７Ｃに示すように、ＬＤＰＣ復号方法は、上記の生成されたエッジａ，ｂのＣ２Ｖメッセージを獲得し、エッジａ，ｂに接続されたノードからのＣ２Ｖメッセージを通じてＶ２Ｃメッセージを生成する。次に、図７Ｄに示すように、２番目の変数ノードに接続されたエッジ(例えば、エッジｄ，ｅ，ｆ）のＶ２Ｃメッセージを生成するために、これらのＣ２Ｖメッセージを獲得する。Ｃ２Ｖメッセージを獲得する動作は図７Ａの動作と類似し、２番目の変数ノードに接続されたエッジ(例えば、エッジｄ，ｅ，ｆ）のＣ２Ｖメッセージを予め獲得する。
図７Ｅに、参照符号２番目の変数に接続されたエッジｄ，ｅ，ｆのＣ２Ｖメッセージをアップデートするために関連したチェックノード処理器の動作を示す。ここで、１番目の変数ノードからアップデートされたＶ２Ｃメッセージがエッジｄ、ｅのＣ２Ｖメッセージを生成するために用いられる。
それによって、図７Ｆに示すように、ＬＤＰＣ復号方法は、エッジｄ，ｅ，ｆにかかるＣ２Ｖメッセージをすべて獲得し、アップデートされたＣ２Ｖメッセージを通じてエッジｄ，ｅ，ｆのＶ２Ｃメッセージが生成される。
【００２８】
本発明では、図７Ａ〜図７Ｆに示すような方式ですべての変数ノードに関連したＶ２Ｃメッセージをすべてアップデートすれば自動的にＣ２Ｖメッセージもアップデートされる。本発明のＬＤＰＣ復号方法は、Ｃ２Ｖメッセージが変数ノードのＶ２Ｃメッセージの生成に基づいて注文型(on-demand）で生成される。すなわち、メッセージパッシング過程でそれ以前にアップデートされたＶ２ＣメッセージがＣ２Ｖメッセージを上記のように注文型で生成するために用いられるため、メッセージの収束速度が速くなる。このような手順を示すと、下記の＜数式（３）＞及び＜数式（４）＞のようである。
【００２９】
【数５】
0004402699.tif 000006
【００３０】
【数６】
0004402699.tif 000007
【００３１】
上記の＜数式（３）＞及び＜数式（４）＞は、ＬＤＰＣ復号方法において、初期化段階(Initialize stage)及び反復段階(Iteration stage)を各々示す。
＜数式（３）＞及び＜数式（４）＞に示すように、ｖ、ｃは、各々変数ノード及びチェックノードを示し、ｑcはノードメモリ値ｍcの振幅(magnitude of node memory value）を、ｐcはノードメモリ値ｍcの符号(sign of node memory value)を、Ｖ(ｃ）はｃ番目のチェックノードに近接した変数ノードのインデックス集合(index set）を、Ｃ(ｖ）はｖ番目の変数ノードに近接したチェックノードのインデックス集合を、ｓｇｎ(ｘ）はｘ値が０より小さい場合に-１(ｓｇｎ(ｘ)＝-１，ｘ＜０)、ｘ値が０以上である場合に＋１(ｓｇｎ(ｘ)＝＋１，ｘ≧０）を、それぞれ示す。
まず、＜数式（３）＞に示すように、初期化段階でｍvcは入力ＬＬＲであるｙvに初期化する。ここで、
【００３２】
【数７】
0004402699.tif 000008
【００３３】
はｖ番目の変数ノードからｃ番目のチェックノードに伝達されるメッセージを示す。そして、ｖとｃは下添え字である。ｑcとｐcは、各々ｍvcの初期化以後に、上記の＜数式（３）＞のように初期化する。
次に、＜数式（４）＞に示すように、反復段階でＬは変数ノードｖの入力メッセージをすべて合わせる過程を示し、ノードｖの入力メッセージは入力ＬＬＲであるｙvとＣ２Ｖメッセージからなる。
次に、
【００３４】
【数８】
0004402699.tif 000009
【００３５】
は、ｃ番目のチェックノードからｖ番目の変数ノードに伝送されるＣ２Ｖメッセージを示す。
【００３６】
以下、上記した＜式（数３）＞及び＜数式（４）＞を参照して、本発明のノードアップデート方法について説明する。
すなわち、本発明のスケジューリング方式は、既存のフラッディングスケジューリング方式とは差別される直列スケジューリング方式として、ｍvcを毎度アップデートする方式である。すなわち、本発明の実施形態では、一例として、変数ノードを基準としてチェックノードをアップデートする方式、すなわち直列スケジューリング方式を通じて、前記各変数ノードに接続されたチェックノードをすべてアップデートする方式に関して説明する。
まず、ｍvcを更新するためにＬから入力エッジの値を除去する。それにより、該当するエッジの振幅(magnitude)値と符号値を除去する部分が必要で、これは下記の＜数式（５）＞のように表わされる。
【００３７】
【数９】
0004402699.tif 000010
【００３８】
次に、上記のようにｍvcをアップデートした後には、更に該当するエッジが接続されたチェックノードメモリ値の振幅値と符号値を反映する。ここで、本発明によるノードアップデート方法はＶ２Ｃメッセージを別に格納するが、Ｃ２Ｖメッセージは別に格納せず、各チェックノードに該当する代表値(ｑc，ｐc)のみを格納する。
上記したように、本発明の実施形態によるノード処理器は、任意の変数ノードに対して出力メッセージ、すなわちＶ２Ｃメッセージを生成及び格納するためにＣ２Ｖメッセージをチェックノードメモリ値(ｐc，ｑc)からの要求により計算して使用する。これは、一種の統合されたノード処理(unified  node  processing)方式で、一つのノード処理過程でＣ２ＶとＶ２Ｃメッセージが同時に生成及びアップデートされる効果を有する。
【００３９】
図８は、本発明の実施形態によるデコーダの構成を示す図である。まず、図８に示す本発明の実施形態によるＬＤＰＣデコーダでは、並列要素Ｚ＝４である場合の例を示す。また、ＬＤＰＣデコーダは、チャンネルを介して入力される信号をＫビット精密度(precision)を有するＬＬＲとして受信し、Ｖ２Ｃエッジメモリの値もＫビット精密度を有すると仮定する。
図８を参照すると、本発明の実施形態によるＬＤＰＣデコーダは、ベクトルノード処理器８０１と、ベクトルノード処理器８０１に入力信号を提供する入力ＬＬＲ８０３と、ベクトルノード処理器８０１の出力の中でＶ２Ｃメッセージを格納するＶ２Ｃエッジメモリ８０５と、ノードメモリ値の振幅であるｐc(１ビット)又はノードメモリ値の符号であるｑc(Ｋ'-１ビット)が格納されるチェックノードメモリ８０７と、ベクトルノード処理器８０１を制御するための制御信号を提供する制御部８０９と、チェックノードメモリ８０７からの出力をパリティチェックするパリティチェック検証器(parity check verifier)８１１と、ベクトルノード処理器８０１から出力されるメッセージをスイッチングしてチェックノードメモリ８０７に伝送する第１のスイッチ８１３と、チェックノードメモリ８０７からの出力をスイッチングしてベクトルノード処理器８０１に伝達する第２のスイッチ８１５を含む。
【００４０】
本発明の実施形態によるベクトルノード処理器８０１は、上記した図７Ａ〜図７Ｆに示すノード処理手順を遂行する。チェックノードメモリ８０７とＶ２Ｃエッジメモリ８０５は、変数ノードとチェックノードがやりとりする値を効率的に利用するためにメッセージを格納する。したがって、本発明の実施形態によるＬＤＰＣデコーダは、チェックノードメモリ８０７とＶ２Ｃエッジメモリ８０５から各々チェックノードメモリ値と、Ｖ２Ｃメッセージ値を読み取った後に、ベクトルノード処理器８０１を通じてＶ２Ｃメッセージとチェックノード値(ｐc，ｑc）を新たに生成してから、各々Ｖ２Ｃエッジメモリ８０５とチェックノードメモリ８０７に格納する。
通常に、ブロックＬＤＰＣの場合は上記したメモリ読み取り/書き込みとメッセージの生成がＺ個の単位で一度に処理されることができる。ノードメモリの一例として、チェックノードメモリ８０７の値は、Ｖ２Ｃメッセージ又はＬＬＲ８０３からの入力ＬＬＲ値と異なるビット精密度(bit precision)Ｋ'を有することができる。
【００４１】
従来のＬＤＰＣデコーダは、反復過程で復号化停止(decoding stop)のために、各反復過程ごとに現在まで復号化された臨時符号語(temporary codeword)を用いてシンドローム(syndrom）をチェックし、或いは最大反復(maximum iteration）過程まで復号化する。しかしながら、本発明の実施形態によるデコーダではチェックノードメモリ８０７にチェックノードメモリ値の符号と振幅であるｐc(１ビット)、ｑc(Ｋ'-１ビット)が格納され、反復段階ごとにすべてのｐc値が＋１であると、すべてのチェック方程式が満たされるため、復号化動作を終結(termination)させることができる。
従来のデコーダでは、別途のパリティチェック検証器８１１を必要とすることに比べて、本発明によるＬＤＰＣデコーダではノードメモリ値の符号値を確認することだけでこの機能を遂行できるため、ハードウェアの実現が簡単になる。したがって、図８に示すような本発明の実施形態では、パリティチェック検証器８１１のハードウェアを簡単に実現することができる。
【００４２】
次に、Ｖ２Ｃエッジメモリ８０５は、Ｌ×Ｚ個のＫビット値を格納する装置で、ここで‘Ｌ’はタナーグラフでエッジの総数を示す。このとき、ベクトルノード処理器８０１では、Ｚ個の変数ノードが並列処理され、Ｖ２Ｃエッジメモリ８０５から関連エッジメッセージ値に対する読み取り/書き込み動作を遂行するときに、一つのセット(各セットはＺ個のエッジメッセージ値を含む)ずつ順次に処理し、或いは複数セットの値を同時に処理することができる。
複数セットの値に対して同時に読み取り/書き込みを遂行する場合に対する効率的な構造は、一つの変数ノードに接続されたエッジの数(ｄｖ、変数ノード次数(variable node degree))だけに処理するものである。このとき、Ｖ２Ｃメッセージ又はチェックノード値を格納するための構造は、ｄｖ個だけのメモリバンク(memory bank）からなる。
一方、不規則(irregular)ＬＤＰＣの場合には、最大変数ノード次数だけのメモリバンクからなる。このような場合に、一つの変数ノードに接続されたエッジメッセージと関連したチェックノード値が一つのサイクル(cycle)に読み取り又は書き込みが可能になるので、パイプライン(pipeline)構造を用いてサイクルごとに１セットの変数ノードに対する処理段階が可能である。これを通じて複数のデコーダの処理率を大幅向上させることができる。
【００４３】
制御部８０９は、ベクトルノード処理器８０１で処理するノードの順序を指定し、或いは反復によるデコーダの終結(termination)を決定する。本発明の実施形態によるＬＤＰＣデコーダは変数ノード基盤の直列スケジューリング方式を使用するため、デコーダで制御部８０９を通じて処理する変数ノードの順序を指定することができる。
例えば、情報ビットに該当するノードをまずアップデートし、その後、パリティビットに該当するノードをアップデートする。或いは、上記と反対又は不規則ＬＤＰＣ符号の場合に、ノード次数によりアップデート順序を決定することができることはもちろんである。なお、エッジの接続形態により、ノードのアップデート順序を決定することもできることはもちろんである。
【００４４】
次に、図８では、ブロックＬＤＰＣの置換(permutation)のための少なくとも一つのスイッチ、すなわち第１及び第２のスイッチ８１３，８１５がベクトルノード処理器８０１とチェックノードメモリ８０７との間に位置する。すなわち、上記の図４及び図５に示したような装置は、ベクトルノード処理器とエッジメモリとの間にスイッチング装置が位置することによって、本発明による装置とその構造的に異なる装置であることは、当業者にとっては自明なことであろう。
【００４５】
図８では、デコーダの出力としてＬＡＰＰ(Log-APriori Probability)８１７を生成するが、これは各変数ノードに接続されたエッジの入力メッセージをすべて合わせたものである。この値の符号は、復号後に出力ビットを示し、振幅(magnitude）は復号信頼度を示す値として、他の受信モジュール、例えばイコライザ(equalizer)、ＭＩＭＯ検出器(Multi-Input Multi-Output  detector)などに使用されうる。
【００４６】
図９は、本発明によるノード処理器の内部構成を示す。特に、図９では、本発明の実施形態によりメモリバンク構造を使用するノード処理器の構成を示す。ここで、各変数ノードに接続されたエッジの数ｄｖは６であると仮定する。
図９を参照すると、本発明の実施形態によるノード処理器は、Ｖ２Ｃエッジメモリバンク９１０とチェックノードメモリバンク９３０から現在処理している変数ノードに接続されたエッジに該当するエッジメッセージと、このエッジに接続されたチェックノードの値を読み取って上述した動作を遂行する。
新たに計算されたＶ２Ｃエッジメッセージとチェックノード値は、更に各変数ノードに接続されたエッジの数、すなわち上記に仮定したところによれば６個が一度に格納される。また、復号化処理率を向上するためのパイプライン構造では、コア(core)動作中にタイミングを合わせるためのラッチ(latch)が挿入されるため、メモリバンクに読み取り/書き込み動作が同時に遂行される。
したがって、デュアルポートメモリ(dual-port memory)を使用して読み取り/書き込みが同時に遂行されるため、メモリ接続の衝突が発生しないようにノードの処理手順を調節する。一方、図９で、関数Ｆの実現は、ルックアップテーブル(look-up table)又は色々な近似(approximation)アルゴリズム、例えば中間和(min-sum)、線形近似(linear approximation)などを用いて可能である。
【００４７】
以上、本発明の詳細な説明においては具体的な実施形態に関して説明したが、特許請求の範囲を外れない限り、形式や細部についての様々な変更が可能であることは、当該技術分野における通常の知識を持つ者には明らかである。したがって、本発明の範囲は、前述の実施形態に限定されるものではなく、特許請求の範囲の記載及びこれと均等なものに基づいて定められるべきである。
【図面の簡単な説明】
【００４８】
【図１】一般的なＬＤＰＣ符号の方向(tenor)グラフとパリティチェックマトリックスを示す図である。
【図２】一般的なメッセージパッシングによるデコーダの動作を説明するために示す図である。
【図３】一般的なブロックＬＤＰＣのグラフ形態及びチェックマトリックスを示す図である。
【図４】従来技術によるデコーダの構成を示す図である。
【図５】従来技術によるデコーダの他の構成を示す図である。
【図６Ａ】従来技術によるデコーダで使用されるフラッディングスケジューリング方式を示す図である。
【図６Ｂ】従来技術によるデコーダで使用されるフラッディングスケジューリング方式を示す図である。
【図７Ａ】本発明によるデコーダで使用されるノードメモリ基盤の直列スケジューリング方式を示す図である。
【図７Ｂ】本発明によるデコーダで使用されるノードメモリ基盤の直列スケジューリング方式を示す図である。
【図７Ｃ】本発明によるデコーダで使用されるノードメモリ基盤の直列スケジューリング方式を示す図である。
【図７Ｄ】本発明によるデコーダで使用されるノードメモリ基盤の直列スケジューリング方式を示す図である。
【図７Ｅ】本発明によるデコーダで使用されるノードメモリ基盤の直列スケジューリング方式を示す図である。
【図７Ｆ】本発明によるデコーダで使用されるノードメモリ基盤の直列スケジューリング方式を示す図である。
【図８】本発明によるデコーダ構成を示す図である。
【図９】本発明によるノード処理の内部構成を示す図である。
【符号の説明】
【００４９】
８０１  ベクトルノード処理器
８０３  ＬＬＲ
８０５  Ｖ２Ｃエッジメモリ（Ｌ×Ｚ×Ｋ）
８０７  チェックノードメモリ(Ｚ×Ｋ’)
８０９  制御部
８１１  パリティチェック検証器
８１７  ＬＡＰＰ
９１０  Ｖ２Ｃエッジメモリバンク
９３０  チェックノードメモリバンク
【図１】
0004402699.tif 000013
【図２】
0004402699.tif 000014
【図３】
0004402699.tif 000015
【図４】
0004402699.tif 000016
【図５】
0004402699.tif 000017
【図６Ａ】
0004402699.tif 000018
【図６Ｂ】
0004402699.tif 000019
【図７Ａ】
0004402699.tif 000020
【図７Ｂ】
0004402699.tif 000021
【図７Ｃ】
0004402699.tif 000022
【図７Ｄ】
0004402699.tif 000023
【図７Ｅ】
0004402699.tif 000024
【図７Ｆ】
0004402699.tif 000025
【図８】
0004402699.tif 000026
【図９】
0004402699.tif 000027