(57)【要約】本発明は、複数の変数ノードおよび複数のチェック・ノードを有する二部グラフによる表現ができる誤り訂正符号の復号のためのメッセージ・パッシング型の逐次反復式復号方法に関する。当該方法の複数の復号反復工程の各反復工程について：変数ノードまたはコントロール・ノードが、これらのノードの近傍（Vn(d)、Vm(d)）において利用可能な復号情報のそれぞれの信頼度に応じて分類され、信頼度の高いノードが信頼度の低いノードより前に分類され；こうして分類された各ノードが、前記分類によって定義された順序で、少なくとも一つのメッセージ（αmn、βmn）を隣接ノードに渡す。本発明はまた、前記復号方法を実装するためのコンピュータ・プログラムにも関する。
2009545220.tif 000002
【特許請求の範囲】
【請求項１】
複数の変数ノードおよび複数のチェック・ノードを有する二部グラフにおいて表示できる誤り訂正符号の復号のためのメッセージ・パッシングによる逐次反復式方法であって、複数の復号反復工程の各反復工程について：
・変数ノードまたはチェック・ノードが、これらのノードの近傍（Vn(d)、Vm(d)）において利用可能な復号情報の対応する信頼度に応じて分類され（７２０）、信頼度の高いノードが信頼度の低いノードより前に分類され；
・こうして分類された各ノードが（７２５）、前記分類によって定義された順序で、少なくとも一つのメッセージ（αmn、βmn）を隣接ノードに渡す、
方法。
【請求項２】
請求項１記載の復号方法であって、分類されるべき各ノードについて、前記分類は、二部グラフにおいてこのノードから所定の距離（d）以内にあるノードに存在する、またはそのようなノードによって送信もしくは受信された情報の信頼性の指標
【数５１】
2009545220.tif 000053
の計算と、こうして得られた指標の値のソートとを含む、復号方法。
【請求項３】
請求項２記載の復号方法であって、前記複数の反復工程の各反復工程について、分類されたノードは、前記分類によって定義された順序で逐次的に処理され、分類された各ノードについて（８２５）、それに隣接するノードに宛てられたメッセージが計算され（８２５）、前記各隣接ノードについて、該隣接ノードに隣接するノードへのメッセージが計算される（８３０）、復号方法。
【請求項４】
請求項１記載の復号方法であって、分類されるべき各ノードについて、前記分類は、二部グラフにおいてこのノードから所定の距離（d）以内に位置するノードに存在する、またはそのようなノードによって送信もしくは受信された情報の信頼性の指標
【数５２】
2009545220.tif 000054
の計算を含み、ノードは、前記指標の値の諸区間においてグループ化される、復号方法。
【請求項５】
前記信頼性指標が整数値を使い、前記各整数値について、信頼性指標がこの値に等しくなるノードのインデックスが、それに関連付けられたメモリ・ゾーンに記憶される、請求項４記載の復号方法。
【請求項６】
請求項４または５記載の復号方法であって、前記複数の反復工程の各反復工程について、ノード・グループは前記分類によって定義された順序で逐次的に処理され、各ノード・グループ（Gj）について、そのグループ内のノードに隣接するノードへのメッセージが計算され（９３５）、前記各隣接ノードについて、それ自身が該隣接ノードに隣接するノードへのメッセージも計算される、復号方法。
【請求項７】
請求項１ないし６のうちいずれか一項記載の復号方法であって、前記二部グラフにおける各変数ノードについて、前記複数の反復工程の各反復工程は、このノード中にすでに存在する事前情報（αn）および隣接チェック・ノードからこのノードによって受信されるメッセージ（βmn）の関数として事後情報
【数５３】
2009545220.tif 000055
を計算するステップ（７４０、８４０、９４０）をも有する、復号方法。
【請求項８】
前記の事後情報計算ステップに続いて、前記変数のハードな値
【数５４】
2009545220.tif 000056
についての決定ステップ（７５０、８５０、９５０）がある、請求項７記載の復号方法。
【請求項９】
請求項８記載の復号方法であって、次のステップ（７６０、８６０、９６０）が、前記のようにして得られた変数のハードな値が、グラフ中のすべてのチェック・ノードに関連付けられたパリティ・チェックを満たすかどうかを試験し、もし満たせば、前記ハードな値によって構成される語が復号された語として提供される、復号方法。
【請求項１０】
請求項１ないし９のうちいずれか一項記載の復号方法であって、前記分類は、所定数の復号反復工程（Iterf）の後に中断され、当該復号方法は次いでその復号反復工程を、前記変数ノードまたは前記チェック・ノードの前記分類なしに続ける、復号方法。
【請求項１１】
請求項７記載の復号方法であって、前記分類は、前記変数の事後の値と事前の値との間の差の絶対値の最小値が所定の閾値（Tf）より大きい場合、中断され、その際、当該復号方法は、その復号反復工程を、前記変数ノードまたは前記チェック・ノードの前記分類なしに続ける、復号方法。
【請求項１２】
前記誤り訂正符号がターボ符号である、請求項１ないし１１のうちいずれか一項記載の復号方法。
【請求項１３】
前記誤り訂正符号が、N個の変数ノードおよびM＝N−K個のチェック・ノードをもつ二部グラフによって表現されるLDPC符号(K,N)である、請求項１ないし１１のうちいずれか一項記載の復号方法。
【請求項１４】
請求項１３記載の復号方法であって、インデックスm∈{1,…,M}をもつチェック・ノードからインデックスn∈{1,…,N}をもつ変数ノードへのβmnメッセージが次のように計算され：
【数５５】
2009545220.tif 000057
ここで、αmn'はインデックスn'をもつ変数ノードからインデックスmをもつチェック・ノードへのメッセージを表し、H(m)はインデックスmをもつチェック・ノードに隣接するすべての変数ノードを表し、xが正であればsgn(x)＝1、そうでなければsgn(x)＝−1であり、
【数５６】
2009545220.tif 000058
である、復号方法。
【請求項１５】
請求項１３記載の復号方法であって、インデックスm∈{1,…,M}をもつチェック・ノードからインデックスn∈{1,…,N}をもつ変数ノードへのメッセージβmnは次のように計算され：
【数５７】
2009545220.tif 000059
ここで、αmn'はインデックスn'をもつ変数ノードからインデックスmをもつチェック・ノードへのメッセージを表し、H(m)はインデックスmをもつチェック・ノードに隣接するすべての変数ノードを表し、xが正であればsgn(x)＝1、そうでなければsgn(x)＝−1である、復号方法。
【請求項１６】
請求項５および１５に記載の復号方法であって、前記分類はチェック・ノードに適用され、前記所定の距離は2に等しく、インデックスmをもつチェック・ノードの信頼性指標が次のように計算され：
【数５８】
2009545220.tif 000060
ここで、H(m)はインデックスmをもつチェック・ノードに隣接する変数ノードの集合を表し、H(n)はインデックスnをもつ変数ノードに隣接するチェック・ノードの集合を表し、Card(.)はある集合のカージナル数を表し、cm＝＋1であればc＝0、cm＝−1であればc＝δmax＋1であり、ここでδmaxは二分グラフ中のチェック・ノードの最大次数であり、cm＝＋1／cm＝−1は、インデックスmをもつチェック・ノードについてパリティ・チェックがそれぞれ満たされている／満たされていないことを意味する、復号方法。
【請求項１７】
コンピュータによって実行されたときに、請求項１ないし１６のうちいずれか一項記載の復号方法のステップを実装するよう適応されたソフトウェア手段を有するコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、遠隔通信またはデータ記録の分野における誤り訂正符号の復号に関する。より詳細には、本発明は、LDPC（Low  Density  Parity  Check［低密度パリティ・チェック］）符号またはターボ符号（turbocodes）のような二部グラフ（bipartite  graph）において表示できる誤り訂正符号の復号のためのメッセージ・パッシング（message  passing）による逐次反復方法に関する。
【背景技術】
【０００２】
二部グラフによって表示できる誤り訂正符号は幅広い多様な符号をカバーしており、具体的には、非特許文献１の論文において最初に記載され、最近興味深い属性が再発見されたLDPC符号や画期的な論文である非特許文献２によって導入されたターボ符号がある。
【０００３】
二部グラフは、あらゆるノードが二つの別個の部分集合をなし、単一の部分集合内のどの二つのノードもグラフのエッジによって接続されていない非有向グラフである。
【０００４】
いくつかの誤り訂正符号が二部グラフとして表示できる。グラフは、符号語を形成するシンボルに関連付けられたノードからなる第一の部分集合と、符号制約条件、典型的にはパリティ・チェックに関連付けられたノードからなる第二の部分集合とに分割される。制約条件のグループに関連付けられた二部グラフはタナー・グラフ（Tanner  graph）とも呼ばれる。
【０００５】
符号語中のシンボルは通例、ガロア体の元F2＝{0,1}、つまりビットであるが、より一般には、任意の標数2をもつ体
【０００６】
【数１】
2009545220.tif 000003
の、よって2p進アルファベットの元であってもよい。以下では、一般性を失うことなく、p＝1の場合、つまり二進符号に限定する。
【０００７】
二部グラフによる追加的な表現符号は、逐次反復的なメッセージ・パッシング（MP）またはBP（Belief  Propagation［信頼伝搬］）復号を使って復号できる。この復号方法についての一般的な記述は非特許文献３によって与えられている。MP型逐次反復式復号は実際には、復号の分野でよく知られたアルゴリズム、すなわちターボ符号に使われる「前方−後方（forward-backward）」アルゴリズムおよびLDPC符号のためのギャラガー・アルゴリズムの一般化である。
【０００８】
簡単のため、以下には、LDPC符号の枠組みにおけるメッセージ・パッシングによる逐次反復復号の原理の記載が含まれる。線形符号(K,N)を考える。ここで、Kはいくつかの情報ビットを表す符号の大きさ（dimension）であり、Nは前記いくつかの符号化されたビットを表す符号の長さである。M＝N−Kはパリティ・ビットの数、すなわちパリティ制約条件の数に等しい。
【０００９】
図１は、線形符号(K,N)のタナー・グラフを示している。グラフの左側は、符号中のビットに対応する、「変数（variable）」型ノードまたは単に「変数」とも呼ばれるノードを示し、右側は、「チェック（check）」型ノードまたはより単純に「チェック」とも呼ばれるパリティ・チェックに対応するノードを示している。このグラフの結合行列は、大きさM×Nをもつ前記符号のパリティ行列に対応する。よって、この二部グラフは、N個の「変数」型ノードおよびM個の「チェック」型ノードを有し、変数ノードnがチェック・ノードmに接続されるのはhmn＝1である場合でありかつその場合に限られる。たとえば、図１におけるグラフは符号(10,5)に対応し、次のパリティ行列
【００１０】
【数２】
2009545220.tif 000004
をもつ。
【００１１】
一般に、線形符号は二進値の要素をもつ生成行列Gによって定義され、符号語x＝(x1,x2,…,xN)は、情報ビットa＝(a1,a2,…,aK)をもつ語から
x＝aG            (2)
によって得られることを想起されたい。すべての符号語はパリティ・チェックを満たすので、関係
H・GT＝0            (3)
が得られる。ここで、GTは行列Gの転置を表す。
【００１２】
符号語xは通信チャネル上で伝送されたり、データ担体に記録されたりする。xのノイズ入りバージョン、すなわちy＝(y1,y2,…,yN)が受信に際して、あるいは担体を読むときに回復される。復号動作は、観察値yから出発してxを、したがってaを見出すことである。
【００１３】
逐次反復的メッセージ・パッシング復号の原理を記述する前に、以下の記号法について取り決めておく。
【００１４】
H(n)は、二部グラフ中の変数nに関係したすべての試験、つまりノードnに隣接するすべてのノードを表す。
【００１５】
H(m)は、二部グラフ中のチェックmに接続された変数の集合、つまりノードmに隣接するすべてのノードを表す。
【００１６】
αnは二部グラフ中の変数nに関する事前（a  priori）情報、つまり符号語中のn番目のビットに関する事前情報を表す。この情報が、受信される信号および伝送チャネルの特性を取り入れるものである。これはデコーダへの入力をなし、通例、ソフトな値の形で、すなわち確率を用いて復調器によって与えられる：
αn＝(pn0,pn1)            (4)
ここで、pna＝Pr(xn＝a|yn),      a∈{0,1}
あるいはより便利には、対数尤度比（LLR:  logarithmic  likelihood  ratio）の形
【００１７】
【数３】
2009545220.tif 000005
で与えられる。こうして、中央化された（centred）ガウス型ホワイトノイズおよびBPSK変調については、復調器は単に
αn＝（2/σ2）yn            (6)
を計算する。ここで、σ2はノイズ分散である。
【００１８】
αmnは、変数nによってチェックm∈H(n)に伝送されるメッセージを表す。ターボ符号を参照すると、αmnは外来情報（extrinsic  information）とも呼ばれる。
【００１９】
βnmは対称的にチェックmによって変数n∈H(m)に伝送されるメッセージを表す。これも外来情報と形容される。
【００２０】
＾付きのαnは、変数nに関係した事後（a  posteriori）情報を表す。これは、事前情報αnと、復号の間に隣接するチェックから変数nが受信したメッセージβnmとの両方を取り入れている。
【００２１】
￣付きのαnは、ソフト値である＾付きのαnに対応するハードな値、つまりビットxnについてなされた決定である。
【００２２】
図２は、メッセージ・パッシングによる逐次反復復号の原理を示している。
【００２３】
ステップ２１０では、メッセージαmnは、変数nおよびチェックm∈H(n)の対のそれぞれについて初期化される。メッセージαmnは、通例、前記の事前情報によって初期化される。すなわち、αmn＝αn、∀m∈H(n)。逐次反復カウンタ（iteration  counter）Iterも0に初期化される。
【００２４】
この初期化ステップには以下のステップを含む逐次反復ループが続く。
【００２５】
２２０では、チェックが初期化される。より正確には、各チェックmについて、チェックmから対応する変数n∈H(m)へのメッセージβmnが計算される。すなわち、
βmn＝FC（｛αmn'｜n'∈H(m)−{n}｝）          (7)
ここで、FCはチェック処理関数である。任意の与えられたノードの対m、n∈H(m)について、メッセージβmnは、チェックm自身が変数n'∈H(m)−{n}から受信したメッセージの関数として計算される。結果として、変数ノードから自分自身に回送される外来情報はないことがわかる。チェック処理ステップは水平ステップとも呼ばれる。
【００２６】
２３０では、変数は対称的に処理される。より正確には、各変数nについて、対応するチェックm∈H(n)に向けられたメッセージαmnが計算される。すなわち、
αmn＝FV（｛βm'n｜m'∈H(n)−{m}｝）          (7')
ここで、変数処理関数はFVと記されている。与えられたノードの対n、m∈H(n)について、メッセージαmnは、変数n自身がチェックm'∈H(n)−{m}から受信したメッセージの関数として計算される。よって、上記のように、ノードから自分自身に回送される外来情報はない。変数処理ステップは垂直ステップとも呼ばれる。
【００２７】
２４０では、事後情報（＾付きのαn）が、事前情報αnと、変数nによってその隣接チェック・ノードm∈H(n)から受信されたメッセージβmnとから推定される。記号的には
【００２８】
【数４】
2009545220.tif 000006
と表される。ここで、事後推定関数がFAPと表されている。
【００２９】
２５０では、ソフトな値（＾付きのαn）からハードな値（￣付きのαn）に対する決定がなされる。すなわち、
【００３０】
【数５】
2009545220.tif 000007
ここで、決定関数がFDで表されている。典型的には、BPSK変調について、ソフト値の符号について決定がされる。すなわち、
【００３１】
【数６】
2009545220.tif 000008
以下では便宜上、ビットの値はその変調された値と同定される。通常、ビット「0」が値「＋1」によって表現され、ビット「1」が値「−1」によって表現される。
【００３２】
２６０では、ベクトル
【００３３】
【数７】
2009545220.tif 000009
が符号語かどうかが検査される。つまり、前記ベクトルがパリティ・チェックを満たすかどうかが検査される。もし満たせば、ステップ２６５でループは終了され、復号された語は
【００３４】
【数８】
2009545220.tif 000010
となる。もし満たさなければ、反復数がステップ２６７でインクリメントされ、ステップ２７０における比較が、行われた反復数Iterが閾値Iter_maxに達したかどうかを判定する。もし達していなければ、逐次反復式復号はステップ２２０にループで戻って継続される。デフォルトでは、復号動作が失敗したと結論され、ループはステップ２７５で終了される。
【００３５】
逐次反復ループ中のステップの順序は、図２に示された順序とは異なるものであってもよい。特に、変数およびチェックの処理順は逆にでき、メッセージβmnをβmn＝0、∀n∈{1,…,N}および∀m∈H(n)と初期化することによって開始することが可能である。
【００３６】
図２に示される逐次反復符号の原理によれば、すべてのチェックがまず処理され、続いてすべての変数が処理されてもよいし、あるいは上述したように、すべての変数がまず処理されて、続いてすべてのチェックが処理されてもよい。これは、「並列スケジューリング（parallel  scheduling）」または「洪水スケジューリング（flooding  scheduling）」と称される。文献では他の型のスケジューリングも提案されており、それらは二つの範疇に分類されうる。
【００３７】
−シリアル型スケジューリング。「シリアル・スケジューリング（serial  scheduling）」、「シャッフルドBP（shuffled-BP）」、「水平シャッフルド（horizontal  shuffled）」または「垂直シャッフルド（vertical  shuffled）」スケジューリングを含みうる範疇である。シリアル型スケジューリングは、チェックおよび変数に等しく適用可能である。チェックへの適用については、復号は以下の戦略を使う：
・まず、単一のチェックmが変数n∈H(m)に送られるべきメッセージβmnを計算することによって処理される；
・チェックm'∈H(n)−{m}に送られるべき各変数n∈H(m)からのメッセージαm'nが更新され、送信される。これらの変数に関係した事後情報（＾付きのαn）も更新される；
・それ以上チェックがなくなるまで、次のチェックが処理され、上記２つのステップが反復される。
【００３８】
同様に、チェックごとの処理の代わりに、変数ごとの処理を採用することができる。想定される場合に依存して、用語「水平シャッフルド」または「垂直シャッフルド」スケジューリングが使用される。
【００３９】
上述した二つのスケジューリング型は、「混合（mixed）」または「グループ・シャッフルド（group  shuffled）」スケジューリングの形で混成されることもできる。混合スケジューリングに対応するデコード戦略の記述は、非特許文献４の論文に与えられている。戦略は、ノードのグループによる分割に基づき、処理はグループ内では並列、あるグループから次のグループへは直列である。より正確には、チェック・グループの分布について：
・チェック{m1,m2,…,mg}からなる第一のグループGは、i＝1,…,gについて変数n∈H(mi)に送られるべきメッセージβmi  nを計算することによって処理される；
・i＝1,…,gについて対応するチェックm'∈H(n)−{mi}に送られるべき各変数n∈H(mi)についてのメッセージαm'nが更新され、送信される。これらの変数についての事後情報（＾付きのαn）も更新される；
・それ以上チェック・グループがなくなるまで、次のチェック・グループが処理され、上記２つのステップが反復される。
【００４０】
同様に、処理は、チェックのグループごとの分割ではなく、変数のグループごとの分割に基づくこともできる。
【００４１】
図３、図４および図５は、それぞれ並列スケジューリング、シリアル・スケジューリングおよび混合スケジューリングについてのメッセージ・パッシング機構を図的に示している。変数が処理される前にチェックが処理されると想定されている。図３は、チェックの処理における第一のステップ（ａ）および変数の処理における第一のステップ（ｂ）を示している。図４および図５は、チェックの処理における第一（ａ）および第二（ｃ）のステップならびに変数の処理における第一のステップ（ｂ）および第二のステップ（ｄ）を示している。図５では、すべてのチェック・ノードは、逐次的に処理されるG1およびG2で表される二つのグループに分割されている。
【００４２】
なお、シリアル・スケジューリングおよび並列スケジューリングは混合スケジューリングの特殊な場合のように考えることもできる。前者は諸グループが単一元に縮小された場合に対応し、後者は一つのグループがすべてのチェック・ノード（および変数ノード）を含む場合に対応する。
【００４３】
LDPC符号について、二つの主要な逐次反復メッセージ・パッシング復号アルゴリズムが知られている。すなわち、「log-BP〔対数BP〕」とも呼ばれるSPA（Sum  Product  Algorithm［和積アルゴリズム］）および「based  BP〔基礎付きBP〕」とも呼ばれる「Min-Sum〔最小和〕」アルゴリズムである。これら二つのアルゴリズムの詳細な記述は、非特許文献５の論文によって与えられている。
【００４４】
SPAとMin-Sumアルゴリズムの唯一の相違は、チェック処理ステップにおいてであり、これについては後述する。他のステップは同一である。すなわち：
変数処理ステップ２３０は次のようにメッセージαmnを計算することからなる：
【００４５】
【数９】
2009545220.tif 000011
ここで、B*mnは、コントロールm'∈H(n)−{m}から変数nによって受信されたすべてのメッセージβm'nを表し、Cmnは、これらのチェックのそれぞれについて検証されたパリティ・チェックに対応するイベントを表す。yn値どうしが独立であるとすると、αmnはLLRの形で
【００４６】
【数１０】
2009545220.tif 000012
のように表せることが示される。
【００４７】
事後情報を推定するステップ２４０は
【００４８】
【数１１】
2009545220.tif 000013
を計算することからなる。ここで、BnはすべてのH(n)チェックから変数nによって受信されるメッセージを表し、Cnは、これらのチェックのそれぞれについて検証されたパリティ・チェックに対応するイベントを表す。上と同じ想定に基づき、＾付きのαnがLLRの形で
【００４９】
【数１２】
2009545220.tif 000014
のように表せることが示せる。
式(11)および(13)により、
【００５０】
【数１３】
2009545220.tif 000015
であることが見出される。その結果、変数処理ステップ２３０は、事後情報の推定後の、反復工程の終わりに置かれてもよい。表式(14)は、あるノード（m）が外来情報（この場合βmn）を自分自身に返さないことを翻訳したものである。
【００５１】
ハード値決定ステップ２５０は単に：
【００５２】
【数１４】
2009545220.tif 000016
によって行われる。ここで、xが正であればsgn(x)＝1、そうでなければsgn(x)＝−1である。
【００５３】
ステップ２６０におけるハード値に対するパリティ・チェックの検証は、パリティ・チェックの計算：
【００５４】
【数１５】
2009545220.tif 000017
を使う。すべてのパリティ・チェックが満たされるのは：
【００５５】
【数１６】
2009545220.tif 000018
の場合であって、かつこの場合のみである。
【００５６】
SPAアルゴリズムについては、チェック処理ステップ２２０は次を計算することからなる。
【００５７】
【数１７】
2009545220.tif 000019
ここで、cm＝1は、あるパリティ条件がチェックmについて満足されることを意味し、A*mnは、変数n'∈H(m)−{n}からチェックmによって受信されたすべてのメッセージαmn'を表す。βmnは
【００５８】
【数１８】
2009545220.tif 000020
によって表せることが示される。ここで、
【００５９】
【数１９】
2009545220.tif 000021
である。
【００６０】
Min-Sumアルゴリズムによるチェックの処理は、表式(19)の単純化に対応する。関数Φ(x)の速い減衰およびΦ(x)がその逆に等しい、すなわちΦ(Φ(x))＝xという事実のため、次のような近似：
【００６１】
【数２０】
2009545220.tif 000022
をすることが正当化できる。
【００６２】
このMin-Sum復号アルゴリズムは、加算、比較および符号変化を実行するだけなので、SPA復号アルゴリズムより著しく単純である。さらに、Min-Sumアルゴリズムの性能はノイズ分散σ2の推定とは独立である。
【００６３】
SPA復号アルゴリズムの性能のほうがMin-Sumアルゴリズムの性能より上ではあるが、SPA復号アルゴリズムの性能は、ノイズ・パワーの推定が悪いとひどく劣化することがありうる。
【先行技術文献】
【非特許文献】
【００６４】
【非特許文献１】R・ギャラガー（Gallager）、「低密度パリティ・チェック符号（Low  density  parity  check  codes）」、IEEE  Trans.  Inform.  Theory、vol.  IT-8、第21-28頁、1962年
【非特許文献２】C・ベルー（Berrou）ら、「最適に近い誤り訂正符号化および復号：ターボ符号（Near  optimum  error  correcting  coding  and  decoding:  turbo-codes）」、IEEE  Trans.  Inform.  Theory、vol.  44、No.10、第1261-1271頁、1996年
【非特許文献３】N・ウィベリ（Wiberg）、「一般グラフに対する符号および復号（Codes  and  decoding  on  general  graphs）」、学位論文、1996年
【非特許文献４】J・チャン（Zhang）ら、「シャッフルド逐次反復復号（Shuffled  iterative  decoding）」、IEEE  Trans.  on  Comm.、Vol.53、No.2、2005年2月、第209-213頁
【非特許文献５】W・E・ライアン（Ryan）、「LDPC符号入門（An  introduction  to  LDPC  codes）」、『記録システムのための符号化および信号処理のCRCハンドブック（CRC  Handbook  for  coding  and  signal  processing  for  recording  systems）』所収、リンクwww.csee.wvu.edu/wcrl/ldpc.htm
【発明の概要】
【発明が解決しようとする課題】
【００６５】
本発明の一般的な目的は、二部グラフによって表現できる誤り訂正符号を復号するための逐次反復式メッセージ・パッシング型復号アルゴリズムであって、現状技術で知られている同じ型のアルゴリズムよりも誤り率（error  rate）および収束率（convergence  rate）の意味で性能がよいものを提案することである。
【００６６】
本発明の第一の目的は、LDPC符号を復号するための逐次反復式メッセージ・パッシング型復号アルゴリズムであって、SPAアルゴリズムより著しく低い複雑さをもち、その一方で所与の信号対雑音比に対してSPAアルゴリズムに匹敵するまたさらにはよりよい誤り率性能をもち、またノイズ・パワーの推定を必要としないものを提案することである。
【００６７】
本発明のもう一つの個別目的は、LDPC符号を復号するためのメッセージ・パッシング型復号アルゴリズムであって、SPAまたはMin-Sumアルゴリズムより高い収束率をもつものを提案することである。
【課題を解決するための手段】
【００６８】
本発明は、複数の変数ノードおよび複数のチェック・ノードを有する二部グラフにおいて表示できる誤り訂正符号の復号のためのメッセージ・パッシングによる逐次反復的方法であって、複数の復号反復工程の各反復工程について：
・変数ノードまたはチェック・ノードが、これらのノードの近傍において利用可能な復号情報の対応する信頼度（degree  of  reliability）に応じて分類され、信頼度の高いノードが信頼度の低いノードより前に分類され；
・こうして分類された各ノードが、前記分類によって定義された順序で、少なくとも一つのメッセージを隣接ノードに渡す（pass）、
方法によって定義される。
【００６９】
第一の実施形態によれば、分類されるべき各ノードについて、前記分類は、二部グラフにおいてこのノードから所定の距離以内にあるノードに存在する、またはそのようなノードによって送信もしくは受信された情報の信頼性の指標（measurement）の計算と、こうして得られた指標の値のソート（sorting）を含む。
【００７０】
前記複数の反復工程の各反復工程について、分類されたノードは次いで、前記分類によって定義された順序で逐次的に処理される。分類された各ノードについて、それに隣接するノードに宛てられたメッセージが計算され、前記各隣接ノードについて、該隣接ノードに隣接するノードへのメッセージが計算される。
【００７１】
第二の実施形態によれば、分類されるべき各ノードについて、前記分類は、二部グラフにおいてこのノードから所定の距離以内に位置するノードに存在する、またはそのようなノードによって送信もしくは受信された情報の信頼性の指標の計算を含む。ノードは、前記指標の値の諸区間においてグループ化される。
【００７２】
信頼性指標が整数値を使う場合、前記各整数値について、信頼性指標がこの値に等しくなるノードのインデックスが、それに関連付けられたメモリ・ゾーンに記憶される。
【００７３】
前記複数の反復工程の各反復工程について、ノード・グループは前記分類によって定義された順序で逐次的に処理され、各ノード・グループについて、そのグループ内のノードに隣接するノードへのメッセージが計算され、前記各隣接ノードについて、それ自身が該隣接ノードに隣接するノードへのメッセージが計算される。
【００７４】
ある変形によれば、前記二部グラフにおける各変数ノードについて、前記複数の反復工程の各反復工程は、このノード中にすでに存在する事前情報および隣接チェック・ノードからこのノードによって受信されるメッセージの関数として事後情報を計算するステップをも有する。
【００７５】
この事後情報計算ステップに続いて、前記変数のハードな値についての決定ステップがあってもよい。
【００７６】
次のステップは、こうして得られた変数のハードな値が、グラフ中のすべてのチェック・ノードに関連付けられたパリティ・チェックを満たすかどうかを試験することである。もし満たせば、前記ハードな値によって構成される語が復号された語として与えられる。
【００７７】
有利には、前記分類は、所定数の復号反復工程の後に中断され、本復号方法は次いでその復号反復工程を、前記変数ノードまたは前記チェック・ノードの前記分類なしに続ける。
【００７８】
前記分類は、前記変数の事後の値と事前の値との間の差の絶対値の最小値が所定の閾値より大きい場合、中断される。その際、本復号方法は、その復号反復工程を、前記変数ノードまたは前記チェック・ノードの前記分類なしに続ける。
【００７９】
第一の応用では、前記誤り訂正符号はターボ符号である。
【００８０】
第二の応用では、前記誤り訂正符号は、N個の変数ノードおよびM＝N−K個のチェック・ノードをもつ二部グラフによって表されるLDPC符号(K,N)である。
【００８１】
後者の場合、インデックスm∈{1,…,M}をもつチェック・ノードからインデックスn∈{1,…,N}をもつ変数ノードへのβmnメッセージは次のように計算できる：
【００８２】
【数２１】
2009545220.tif 000023
ここで、αmn'はインデックスn'をもつ変数ノードからインデックスmをもつチェック・ノードへのメッセージを表し、H(m)はインデックスmをもつチェック・ノードに隣接するすべての変数ノードを表し、xが正であればsgn(x)＝1、そうでなければsgn(x)＝−1であり、
【００８３】
【数２２】
2009545220.tif 000024
である。
【００８４】
あるいはまた、インデックスm∈{1,…,M}をもつチェック・ノードからインデックスn∈{1,…,N}をもつ変数ノードへのβmnメッセージは次のように計算できる：
【００８５】
【数２３】
2009545220.tif 000025
ここで、αmn'はインデックスn'をもつ変数ノードからインデックスmをもつチェック・ノードへのメッセージを表し、H(m)はインデックスmをもつチェック・ノードに隣接するすべての変数ノードを表し、xが正であればsgn(x)＝1、そうでなければsgn(x)＝−1である。
【００８６】
ある例示的な実施形態によれば、前記分類はチェック・ノードに適用され、前記所定の距離は2に等しい。インデックスmをもつチェック・ノードの信頼性指標は次いで次のように計算される：
【００８７】
【数２４】
2009545220.tif 000026
ここで、H(m)はインデックスmをもつチェック・ノードに隣接する変数ノードの集合を表し、H(n)はインデックスnをもつ変数ノードに隣接するチェック・ノードの集合を表し、Card(.)はある集合のカージナル数（cardinal）を表す。cm＝＋1であればc＝0、cm＝−1であればc＝δmax＋1であり、ここでδmaxは二分グラフ中のチェック・ノードの最大次数（degree）である。cm＝＋1／cm＝−1は、インデックスmをもつチェック・ノードについてパリティ・チェックがそれぞれ満たされている／満たされていないことを意味する。
【００８８】
最後に、本発明は、コンピュータによって実行されたときに上記で定義された復号方法の諸ステップを実装するよう適応されたソフトウェア手段を有するコンピュータ・プログラムに関係する。
【図面の簡単な説明】
【００８９】
【図１】(K,N)符号についてのタナー・グラフの例を示す図である。
【図２】現状技術に基づいて知られている逐次反復式メッセージ・パッシング復号の原理を図的に示す図である。
【図３】並列型スケジューリングに基づくメッセージ・パッシングによる逐次反復式復号の最初のいくつかの反復工程を示す図である。
【図４】シリアル型スケジューリングに基づくメッセージ・パッシングによる逐次反復式復号の最初のいくつかの反復工程を示す図である。
【図５】混合型スケジューリングに基づくメッセージ・パッシングによる逐次反復式復号の最初のいくつかの反復工程を示す図である。
【図６Ａ】あるノードの1次の近傍を示す図である。
【図６Ｂ】あるノードの2次の近傍を示す図である。
【図７】本発明に基づく、メッセージ・パッシングによる逐次反復式復号の原理を示す図である。
【図８】本発明の第一の実施形態に基づく、メッセージ・パッシングによる復号のための逐次反復式方法を示す図である。
【図９】本発明の第二の実施形態に基づく、メッセージ・パッシングによる復号のための逐次反復式方法を示す図である。
【図１０】LDPC符号を復号するための、本発明に基づく復号方法の例示的な適用を示す図である。
【図１１】特定のLDPC符号について、本発明に基づく復号方法によって得られる誤り率を、現状技術に基づく他の諸方法との比較で示す図である。
【発明を実施するための形態】
【００９０】
いま一度、N個の変数およびM個のチェックをもつ二部グラフによって表現できる誤り訂正符号を考える。
【００９１】
グラフ上の二つのノードν、μをつなぐ、グラフを通る最短経路の長さは距離と呼ばれ、その長さはエッジ数で表されてD(ν,μ)と記される。二部グラフの定義を考えると、同じ型の二つのノードの間の距離は偶数であり、異なる型の二つのノードの間の距離は奇数であることが演繹される。
【００９２】
グラフΓの任意のノードνのd次（order  d）の近傍は、νからd以下の距離に位置するノードの集合Vν(d)として定義される。すなわち：
Vν(d)＝｛μ∈Γ｜D(μ,ν)≦d｝        (21)
よって、あるノードの0次の近傍はそのノード自身からなり、1次の近傍は0次の近傍とこのノードに隣接する全ノードとの組み合わせであり、2次の近傍は1次の近傍と1次の近傍中のノードに隣接する全ノードとの組み合わせである、などとなる。n個の変数およびm個のチェックからなる二部グラフについては、これらのノードの0次から2次の近傍は：
【００９３】
【数２５】
2009545220.tif 000027
によって与えられる。
【００９４】
単集合{n}（または{m}）がVn(2)（またはVm(2)）の表式に現れていないことに気づかれるであろう。これは、該単集合は、隣接関係の対称性から、組み合わせの第二項にすでに含まれているからである。
【００９５】
一般に、二部グラフのノードνの近傍は、再帰関係
【００９６】
【数２６】
2009545220.tif 000028
によって得ることができる。
【００９７】
図６Ａおよび図６Ｂは、近傍の概念を説明するために、図１のグラフ上のチェック・ノードmの1次および2次の近傍を示している。前記近傍に属するノードはグレーで示されている。
【００９８】
本記載の残りの部分では、Γのノードνのd次の信頼性指標（order  d  reliability  measurement）という用語が、近傍Vν(d)中の利用可能な復号情報、換言すれば前記近傍に属するノードに存在するまたはそのようなノードによって送信もしくは受信される情報に依存し、復号動作の局所的な信頼度を示す変数fd(ν)を指すために使われることになる。信頼度が高まるとともにfd(ν)が増加するときその指標を「正」と形容し、そうでない場合に「負」と形容することにする。
【００９９】
チェック・ノードmにおいて利用可能な復号情報は、第一に、パリティ・チェックが検証されているかどうかを示す値cmと、第二に、隣接変数ノードn∈H(m)に送信されるβmnメッセージとを含む。値cmおよびメッセージβmnが復号についての信頼性情報を担う。
【０１００】
変数ノードnにおいて利用可能な情報は、事前情報（αn）、事後情報（＾付きのαn）、隣接チェック・ノードm∈H(n)に送られるべき外来情報メッセージ（αmn）およびハードな値（￣付きのαn）を含む。
【０１０１】
上記の情報は、ハードな値を除いて、復号についての信頼性情報を担持している。
【０１０２】
一般に、LLRの形で表されたソフトな値
【０１０３】
【数２７】
2009545220.tif 000029
を考えると、その絶対値が大きいほど復号は信頼できることになる。
【０１０４】
以下は、0次ないし2次について信頼性指標の若干の例示的な、限定するものではない例を含む。
【０１０５】
・0次の信頼性指標：
この場合、近傍はノード自身に還元される。変数ノードnの0次の信頼性を測定するために、次の関数を選ぶことができる：
【０１０６】
【数２８】
2009545220.tif 000030
これは、ハードな値
【０１０７】
【数２９】
2009545220.tif 000031
についての信頼の度合い（degree  of  confidence）を示す。
【０１０８】
チェック・ノードmについては、単に次の関数を選ぶことができる：
【０１０９】
【数３０】
2009545220.tif 000032
パリティ・チェックが満たされていたとすると（cm＝1）、満たされていなかった場合よりも復号が信頼できることは理解できる。
【０１１０】
・1次の信頼性指標：
ここでもまた、変数ノードとチェック・ノードについて処理が異なる。変数ノードについては、次の関数
【０１１１】
【数３１】
2009545220.tif 000033
の一つが1次の信頼性指標として選べる。
【０１１２】
表式(27)は、パリティ・チェックが検証されている、変数ノードnに接続されたチェック・ノードmの数を表す。
【０１１３】
表式(28)は、符号の不規則性（換言すれば、複数の変数ノードが異なる次数（degree）をもつ可能性）取り入れ、検証されたおよび検証されていないパリティ・チェックのサマリーを生成する。
【０１１４】
表式(27')および(28')は、正の指標(27)および(28)に対応する負の指標である。
【０１１５】
(29)に表されている信頼性指標は、隣接チェック・ノードから受信される信頼性情報の縮小（reduction）に基づいているので、保守的なものである。
【０１１６】
チェック・ノードmについては、1次の信頼性指標について次の関数
【０１１７】
【数３２】
2009545220.tif 000034
の一つを選ぶことができる。
【０１１８】
表式(30)は、チェックmが接続されている変数の信頼性（事後情報）の最小値を示す。
【０１１９】
表式(31)は同様の基準を表しているが、外来情報に適用される。表式(29)と対応していることに気づかれるであろう。
【０１２０】
表式(32)は二つの情報項目のデカルト積を表し、結果としてそれらを統合して取り入れている。第一のものはパリティ・チェックの検証についてであり、第二のものは(30)と同様に事後情報についてである。
【０１２１】
・2次の信頼性指標：
変数ノードnについては次の関数
【０１２２】
【数３３】
2009545220.tif 000035
を選ぶことができる。
【０１２３】
表式(33)は負の復号信頼性指標を表す。これは、変数nに関係したチェックの数であって、パリティ条件が満たされておらず、変数nがこれらのチェックに隣接するすべての変数の間で最も信頼できないものであるようなものを示す。実は、測定値(33)は、指標(27')と(30)の合成と考えることができる。
【０１２４】
チェック・ノードmについては次の関数のうちの一つを選ぶことができる。
【０１２５】
【数３４】
2009545220.tif 000036
ここで、cm＝＋1であればc＝0、cm＝−1であればc＝δmax＋1であり、ここでδmaxはチェック・ノードの最大の次数（degree）、すなわち
【０１２６】
【数３５】
2009545220.tif 000037
である。
【０１２７】
表式(34)は、mのm自身を除いた次数2の近傍中において、満たされていないパリティ・チェックの数を与え、復号信頼性の負の指標を表している。表式(34)の二番目の等号は、当該近傍に長さ4のサイクルがない場合にのみ満たされることを注意しておく。実際上、タナー・グラフが可能な最長のサイクルをもつような符号が使われるので、この等号は通例検証される。
【０１２８】
表式(35)はmに隣接する、m自身を除いた、少なくとも一つの満たされていないチェックに接続されている変数の数を示し、結果として、復号信頼性の負の指標を表している。和の記号の中にある項は0または1に等しいので、この測定値の値は0からδmaxの間である。
【０１２９】
表式(35)は、ノードmについてパリティ・チェックが検証されているかどうかに依存した区別をしない。この情報を取り入れるために、チェックmの検証に依存する値をもつバイアスcが表式(36)に導入された。上述したバイアス値（c＝0、δmax＋1）について、信頼性指標は検証されたチェックについては0からδmaxの間の値に等しく、検証されたチェックについてはδmax＋1から2δmax＋1までの値に等しい。これは、上で定義した意味において負の信頼性指標であることを注意しておく。すなわち、チルダ付きf2(m)の値が小さいほどチェックmの値は信頼できる。よって、(35)の値に関わりなく、検証されたチェックの信頼度は、検証されていないチェックの信頼度よりも常に大きい。
【０１３０】
上で定義された関数のいくつか、特に関数(34)ないし(36)は整数値であることを注意しておく。したがって、これらの関数はマイクロプロセッサ実装に特に好適である。
【０１３１】
重要なことに、上で定義された関数のいくつか、特に関数(34)ないし(36)は、ハードな値cmしか使っていない。
【０１３２】
【数３６】
2009545220.tif 000038
であるから、ノイズ・パワー（σ2）の値はこれらの関数の計算に現れていないことが見て取れる。
【０１３３】
本発明の基本的な概念は、グラフのノードをその信頼性に応じて分類し、最も信頼できるノードまたはノードのグループから始めて、シリアルまたは混合型スキームを使ったメッセージ・パッシングによって復号を行うということである。これは復号性能を、収束率およびビット誤り率（BER:  bit  error  rate）の両方の面で著しく改善する。
【０１３４】
最も信頼できるノードによって伝送されるメッセージが、隣接ノードを復号するのに最も効率的に寄与できることは理解されるであろう。よって、ある反復工程から次の反復工程へ、そしてノードからノードへの信頼性の高速の伝搬があり、これに相関して諸反復工程が進行するにつれて外来情報の絶対値の著しい増加がある。
【０１３５】
図７は、本発明に基づく復号の原理を図的に示している。のちに詳述する初期化段階７１０ののち、反復工程ループが始まる。グラフのチェック・ノードまたは変数ノードが７２０において信頼度に依存して分類される。ここでは、チェック・ノードが分類されると想定する。変数ノードの分類は対称的な諸ステップにつながる。
【０１３６】
ステップ７３０ではシリアル処理または混合処理が行われる。シリアル型処理について、チェック・ノードが逐次的に処理され、各チェック・ノードに隣接する変数ノードも、最も信頼できるチェック・ノードから始まって信頼度が低下していく順序で、逐次的に処理される。混合型の処理については、チェック・ノードは信頼性グループに分類されている。第一のグループは最も信頼できるノードからなり、第二のグループはそれよりは信頼できないノードからなる、などである。変数ノードおよび第一のグループ中のチェック・ノードに対して並列処理がなされ、次いで次のグループの変数ノードおよびチェック・ノードに対して並列処理がなされ、それ以上グループがなくなるまで続けられる。ステップ７４０、７５０、７６０、７６５、７６７、７７０、７７５はそれぞれ図２のステップ２４０、２５０、２６０、２６５、２６７、２７０、２７５と同一であり、よってこれ以上詳細に述べることはしない。
【０１３７】
図８は、シリアル・スケジューリングを使った本発明のある実施形態のさらなる詳細を示している。
【０１３８】
ステップ８１０でメッセージαmnおよびβmnが初期化される。たとえば、変数nおよびチェックm∈H(n)の対のそれぞれについて、αmnはαmn＝αnと初期化される。同様に、チェックmおよび変数n∈H(m)の対のそれぞれについて、βmnはβmn＝0と初期化される。
【０１３９】
次いでステップ８２０で、前記チェックは、信頼性指標
【０１４０】
【数３７】
2009545220.tif 000039
を使って信頼度の降順にソートされる。還元すれば、正の指標については、チェックは
【０１４１】
【数３８】
2009545220.tif 000040
となるようソートされ、負の指標については逆順にソートされる。デカルト積指標（たとえば(32)参照）については、その指標が正か負かに依存して辞書順関係または逆辞書順関係が使われる。また、チェック・ノードのカウンタをj＝0と初期化する。
【０１４２】
次いで８２５で現在のチェックm＝mjが選択され、８３０で変数n∈H(m)が処理される。換言すれば、αmn＝FV（｛βm'n｜m’∈H(n)−{m}｝）が計算される。
【０１４３】
次いでステップ８３５は現在チェック処理mを行う。換言すれば、n∈H(m)についてβmn＝FC（｛αmn'｜n’∈H(m)−{n}｝）が計算される。
【０１４４】
ある変形実施形態によれば、ステップ８３０と９３５は逆にされる。
【０１４５】
ステップ８３７でチェック・ノード・カウンタがインクリメントされ、ステップ８３９で全部処理されたかどうかを見出す試験がなされる。もしまだである場合には、処理はループでステップ８２５に戻り、それ以外の場合には、処理は、それぞれ事後情報の計算、ハード値の決定およびパリティ・チェックの検証を表すステップ８４０ないし８６０に続く。ステップ８４０、８５０、８６０、８６５、８６７、８７０、８７５はそれぞれ図２のステップ２４０、２５０、２６０、２６５、２６７、２７０、２７５と同一である。
【０１４６】
ある代替的な実施形態によれば、チェックではなく変数がソートされる。その場合、内側のループ８２５ないし８３９は変数一つずつに適用されていき、前と同じようにして、現在の変数が、それに隣接するチェックの処理の前または後に、処理されうる。
【０１４７】
図９は、混合スケジューリングを使った本発明のある実施形態を示している。
【０１４８】
ステップ９１０では、図８のステップ８１０でのように、メッセージαmnおよびβmnが初期化される。
【０１４９】
ステップ９２０では、すべてのチェック・ノードまたは変数ノードが、それぞれ異なる信頼性クラスに対応するグループに分割される。たとえば、信頼性クラス（reliability  class）は信頼性指標の値のある区間によって定義される。この実施形態は、指標が整数値を使うときに特に有利である。その場合、ある整数値に、あるいは複数の連続する整数値にある範囲を割り当て、ノードのインデックスを対応するクラスの関数としてテーブルに記憶することができる。以後、異なる信頼性クラスをφ0,φ1,…,φωと記すことにする。ここで、φ0は信頼度が最も高いクラス、φωは信頼度が最も低いクラスである。G0,G1,…,Gωは対応するノード・グループである。以下では前記の分割はチェック・ノードに対してなされたと想定する。
【０１５０】
また、信頼性クラスのカウンタをj＝0に初期化する。
【０１５１】
ステップ９２５では、現在の信頼性クラスφjに対応するノードのグループ、つまりGjを選択する。
【０１５２】
ステップ９３０では、変数n∈H(m)、∀m∈Gjが並列に処理される。換言すれば、メッセージαmn＝FV（｛βm'n｜m'∈H(n)−{m}｝）、∀m∈Gj、∀n∈H(m)が計算される。
【０１５３】
ステップ９３５では、チェックm∈Gjが並列に処理される。換言すれば、メッセージβmn＝FC（｛αmn'｜n'∈H(m)−{n}｝）、∀m∈Gj、∀n∈H(m)が計算される。
【０１５４】
ある変形実施形態によれば、ステップ９３０と９３５は逆にされる。
【０１５５】
ステップ９３７ではクラス・カウンタがインクリメントされ、ステップ９３９で全部処理されたかどうかを判定するべく試験される。もしまだである場合には、処理はループでステップ９２５に戻り、それ以外の場合には、処理は、それぞれ事後情報の計算、ハード値の決定およびパリティ・チェックの検証を表すステップ９４０ないし９６０に続く。ステップ９４０、９５０、９６０、９６５、９６７、９７０、９７５はそれぞれ図２のステップ２４０、２５０、２６０、２６５、２６７、２７０、２７５と同一である。
【０１５６】
図１０は、整数値をもつ信頼性指標に基づく、混合スケジューリングによるLDPC符号の復号への、本発明の個別的な適用を示している。この場合、(36)で定義されたチェック・ノードに対する負の指標を選んだ。
【０１５７】
ステップ１０１０では、ソフトな事後の値（＾付きのαn）が対応する観察
【０１５８】
【数３９】
2009545220.tif 000041
によって初期化され、βmnメッセージは0によって初期化される。
【０１５９】
また、反復カウンタも0に初期化する。
【０１６０】
ステップ１０１５では、ハードな値についての決定がなされる。すなわち、
【０１６１】
【数４０】
2009545220.tif 000042
とする。
【０１６２】
ステップ１０２０は
【０１６３】
【数４１】
2009545220.tif 000043
の値を計算する。ここで、cmはパリティ・チェック
【０１６４】
【数４２】
2009545220.tif 000044
である。
【０１６５】
ステップ１０２３は、χ＝Mかどうかを、つまりすべてのパリティ・チェックが検証されているかどうかを試験する。もしそうであれば、ステップ１０２５で、符号語を提供することによって復号アルゴリズムは終了される。もしそうでなければ、処理は、指標(36)を使ってチェック・ノードの信頼性指標を計算することによってステップ１０２７に続く。この指標は0,1,…,2δmax＋1のうちの整数値に等しいことを想起されたい。ここで、δmaxはチェック・ノードの最大の次数である。この場合、信頼性クラスを整数値、つまりφ0,φ1,…,φωによって割り当てる。ここで、ω＝2δmax＋1であり、φjは指標の値に対応し、j∈{0,1,…,2δmax＋1}である。
【０１６６】
ステップ１０２９では、現在の信頼性クラスφjに対応するノードのグループ、つまりGjが選ばれる。
【０１６７】
ステップ１０３０では、変数n∈H(m)、∀m∈Gjの処理が並列になされる。換言すれば、メッセージ
【０１６８】
【数４３】
2009545220.tif 000045
が計算される。
【０１６９】
ステップ１０３５ではチェックm∈Gjが並列に処理される。換言すれば、変数n∈H(m)、∀m∈Gjに送られるべきメッセージ、具体的には、SPA処理については
【０１７０】
【数４４】
2009545220.tif 000046
簡略化されたMin-Sum型処理については
【０１７１】
【数４５】
2009545220.tif 000047
が計算される。図にはこの後者の場合が示されている。次いでステップ１０４０で事後情報が
【０１７２】
【数４６】
2009545220.tif 000048
を使って計算される。
【０１７３】
和の中で使われているチェックm∈H(n)の一部はグループGjの一部を形成しない可能性があり、よって、これらのチェックを起源とするメッセージβmnはステップ１０３５で計算され直さなかったことを注意しておく。さらに、変数nはいくつかのチェックm∈H(n)に隣接するので、事後情報の前記計算は、H(n)のチェックが処理されるにつれ複数回なされることになる。ステップ１０４０における和が複数回計算されるのを防ぎ、変更されなかった一部のメッセージβmnが毎回再計算されるのを防ぐため、ステップ１０３５および１０４０は有利には次の演算を含む単一のステップによって置き換えられる。
【０１７４】
∀m∈Gj、∀n∈H(m)
・古いメッセージを引く：
【０１７５】
【数４７】
2009545220.tif 000049
・新しいメッセージを計算する：
【０１７６】
【数４８】
2009545220.tif 000050
・前記新しいメッセージを足すことによって事後情報を更新する：
【０１７７】
【数４９】
2009545220.tif 000051
このようにして、チェックm∈H(n)によって変数nに送られた新しいメッセージが計算される際に事後情報が更新される。これは、事後情報の計算のために実行される演算の数を著しく減らすことができる。
【０１７８】
次のステップ１０４３は信頼性クラス・カウンタをインクリメントし、次いでステップ１０４５ですべてのクラスが処理されたかどうかを試験する。もしまだである場合には、ステップ１０２９が繰り返されて次の信頼性クラスが処理される。もしそうである場合には、ステップ１０５０で反復カウンタがインクリメントされる。ステップ１０５３は、停止基準が満たされているかどうか、換言すれば最大反復回数に達しているかどうかを試験する。もしそうであれば、ステップ１０５５でループは終了され、復号は失敗したと結論される。もしそうでなければ、処理は新しい反復工程のためにステップ１０１５にループで戻る。
【０１７９】
図１０において、ハードな値についての決定ステップおよびパリティ・チェックの検証のためのステップが、信頼性計算およびノード処理のステップに先行していることが見て取れる。これは、ここで使われる信頼性指標（表式(36)）がハード決定cmを必要とし、結果としてハード決定が前もって計算されることを要求するという事実のためである。
【０１８０】
図１０に示されるアルゴリズムは、現状技術に基づくSPAまたはMin-Sumアルゴリズムよりやや複雑なだけである。他方、近傍信頼性によるスケジューリングは、同じ信号対雑音比（SNR）についてより低いビット誤り率（BER）に達するための収束を加速する。あるいはまた、同じ設定された値の誤り率について、本発明に基づく復号方法は、より低い符号化利得をもつ符号を使うことができる。
【０１８１】
図１１は、従来技術のMin-SumおよびSPAアルゴリズムのビット誤り率（BER）の面での性能を、広い範囲の信号対雑音比について、Min-Sum-FVと記される近傍信頼性によるスケジューリングを使ったMin-Sumアルゴリズムと比較している。使用された符号は不規則なLDPC符号[1008,2016]および[4032,8064]であり、したがって1/2の効率をもつ。反復数は、上記三つのアルゴリズムについて200に等しい。
【０１８２】
本発明に基づくMin-Sum-FVアルゴリズムが、複雑さは著しく低くなったにもかかわらず、従来技術のSPAアルゴリズムより優れていることが観察される。
【０１８３】
図７ないし図１０に示された本発明に基づく復号方法では、近傍信頼性によるスケジューリングが復号期間を通じて使用されることが想定されている。ある変形によれば、このスケジューリングは初期の反復工程の間にのみ、観察値からノイズを取り除くために適用され、次いで通常の処理に移行することができる。移行基準は、反復回数Iterfであってもよいし、あるいは有利には外来情報の絶対値とある基準閾値との比較に基づいていてもよい。たとえば、逐次反復式復号において、最小信頼性閾値をTfで表すものとして、
【０１８４】
【数５０】
2009545220.tif 000052
となるやいなや、Min-Sumまたは通常のSPA処理に復帰することができる。この変形は、復号された値が十分信頼できるようになり、収束が確実となるとすぐ、ノードのソートまたは分類を防止する。
【０１８５】
本発明は、二部グラフによって表現できる誤り訂正符号、特にLDPC符号またはターボ符号の復号に適用可能である。本発明は、データ記録または遠隔通信の分野において、特に、すでにLDPC符号を使っている遠隔通信システム、たとえばIEEE  802.3a（10ギガビット毎秒イーサネット（登録商標））、DVB-S2（衛星ビデオ放送）、IEEE  802.16（WiMAX）といった規格に準拠する遠隔通信システムのために、あるいはこれらの符号を使うことができる遠隔通信システム、たとえばIEEE  802.11(WLAN)およびIEEE  802.20（移動体ブロードバンド無線アクセス）といった規格を満たすシステムのために使用できる。
【図１】
2009545220.tif 000061
【図２】
2009545220.tif 000062
【図３（ａ）】
2009545220.tif 000063
【図３（ｂ）】
2009545220.tif 000064
【図４（ａ）】
2009545220.tif 000065
【図４（ｂ）】
2009545220.tif 000066
【図４（ｃ）】
2009545220.tif 000067
【図４（ｄ）】
2009545220.tif 000068
【図５（ａ）】
2009545220.tif 000069
【図５（ｂ）】
2009545220.tif 000070
【図５（ｃ）】
2009545220.tif 000071
【図５（ｄ）】
2009545220.tif 000072
【図６Ａ】
2009545220.tif 000073
【図６Ｂ】
2009545220.tif 000074
【図７】
2009545220.tif 000075
【図８】
2009545220.tif 000076
【図９】
2009545220.tif 000077
【図１０】
2009545220.tif 000078
【図１１】
2009545220.tif 000079
【国際調査報告】
2009545220.tif 000080
2009545220.tif 000081
2009545220.tif 000082
2009545220.tif 000083
2009545220.tif 000084
2009545220.tif 000085