(57)【特許請求の範囲】
【請求項１】
有限サイズのデータブロックに対して誤り訂正符号を評価する方法であって、
パリティ検査行列を用いて誤り訂正符号を定義するステップと、
前記パリティ検査行列を、前記データブロックの変数ビットを表わす変数ノードと、前記データブロックのパリティビットを表わすチェックノードとを含む２部グラフとして表わすステップと、
所定のしきい値に達するまで、前記２部グラフ中の単一ノードを反復的に繰り込むステップと
を含み、
前記繰り込むステップは、
目標ノードとして、特定の変数ノードを選択するステップと、
前記目標ノードと、前記２部グラフ中の他のあらゆるノードとの距離を測定するステップと、
葉変数ノードが少なくとも１つある場合に、前記目標ノードからもっとも遠い特定の葉変数ノードを特定のノードとして繰り込むステップと、そうでなければ、
葉チェックノードが少なくとも１つある場合に、前記目標ノードからもっとも遠い特定の葉チェックノードを特定のノードとして繰り込むステップと、そうでなければ、
前記目標ノードからもっとも遠く、かつもっとも少ない直結チェックノードを有する非葉変数ノードを特定のノードとして繰り込むステップと
をさらに含むことを特徴とする方法。
【請求項２】
請求項１に記載の方法において、
前記所定のしきい値は、前記繰り込むステップにおいて前記特定のノードの繰り込み処理を施した後における前記目標ノードと、前記２部グラフ中の他のあらゆるノードとの距離の許容値として設定されることを特徴とする方法。
【請求項３】
請求項１に記載の方法において、
前記２部グラフは、ループがないことを特徴とする方法。
【請求項４】
請求項１に記載の方法において、
前記２部グラフは、少なくとも１つのループを含むことを特徴とする方法。
【請求項５】
請求項１に記載の方法において、
伝送通信路が２元消失通信路である方法であって、
前記２部グラフを、変数ノードからチェックノードへのメッセージの確率を表わす数値ｐｉａで、またチェックノードから変数ノードへのメッセージの確率を表わす数値ｑａｉで修飾するステップをさらに含み、
前記非葉変数ノードを繰り込むステップは、
前記非葉変数ノードに連結されたすべてのチェックノードａを列挙するステップと、
前記チェックノードａに結び付けられた他のすべての変数ノードｊを列挙するステップと、
前記数値ｑａｊを変換するステップと
をさらに含むことを特徴とする方法。
【請求項６】
請求項５に記載の方法において、
前記数値ｑａｊを変換するステップは、
前記目標ノードから所定の距離まで、すべてのチェックノードと変数ノードを列挙するステップと、
論理的推論を構築して、前記チェックノードａから前記変数ノードｊへの特定のメッセージが消失となる消失の組合せを決定するステップと、
前記論理的推論を、前記数値ｑａｊ用の変換に変えるステップと
をさらに含むことを特徴とする方法。
【請求項７】
請求項６に記載の方法において、
正確な決定により前記所定のしきい値に達すると、前記繰り込むステップを終了することを特徴とする方法。
【請求項８】
請求項７に記載の方法において、
前記残りの２部グラフは、前記正確な決定において、Ｎ個のノードを含む方法であって、
数値ｑａｉとｐｉａを有する前記修飾グラフを、前記２部グラフのノードｉごとに消失確率ｘｉを有する消失グラフに変換するステップと、
２Ｎ個の可能なメッセージすべてを生成するステップと、
消失されるあらゆるノードの数の範囲をｉ、消失されないあらゆるノードの数の範囲をｊとしたときに、確率ｐ＝ПｘｉП（１−ｘｊ）を有する前記２Ｎ個のメッセージのそれぞれを、ＢＰ（belief propagation）復号器を用いて復号するステップと
をさらに含むことを特徴とする方法。
【請求項９】
請求項５に記載の方法において、
すべての前記数値ｑａｉはゼロに初期設定され、またすべての前記数値ｐｉａは、前記伝送通信路の消失率に初期設定されることを特徴とする方法。
【請求項１０】
請求項５に記載の方法において、
列が変数ビットを表わし、行がパリティビットを表わし、また、伝送されない隠れ変数ビットを表わす上部横線が列の上に付されている一般化パリティ検査行列を用いて、前記誤り訂正符号を定義するステップと、
前記２部グラフ中の隠れノードにより、前記隠れ変数ビットを表わすステップと
をさらに含むことを特徴とする方法。
【請求項１１】
請求項１０に記載の方法において、
前記伝送通信路は、２元消失通信路であり、また前記誤り訂正符号は、一般化パリティ検査行列によって定義される方法であって、
隠れノードｉ用の前記数値ｐｉａを１に初期設定するステップをさらに含むことを特徴とする方法。
【請求項１２】
請求項１に記載の方法において、
前記伝送通信路は加法白色ガウス雑音通信路である方法であって、
前記２部グラフ中のノード間のメッセージを、ガウス分布を用いて表わすステップをさらに含むことを特徴とする方法。
【請求項１３】
請求項１に記載の方法において、
誤り訂正符号を評価する一組の基準を選択するステップと、
複数の誤り訂正符号を生成するステップと、
前記一組の基準により、前記複数の誤り訂正符号を調べて、最適な誤り訂正符号を探すステップと
をさらに含むことを特徴とする方法。
【請求項１４】
請求項１に記載の方法において、
複数のノードでの誤り訂正符号ごとに、誤り率を評価するステップと、
前記評価された誤り率により、前記最適な誤り訂正符号を生成するステップと
をさらに含むことを特徴とする方法。
【請求項１５】
請求項１に記載の方法において、
前記繰り込まれた２部グラフに対して誤り率を評価するステップをさらに含むことを特徴とする方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般に、データ記憶とデータ伝送用の誤り訂正符号の分野に関し、より詳しくは、中間的長さのデータブロックに対して、誤り訂正符号を評価および最適化することに関する。
【０００２】
【従来の技術】
データ記憶とデータ通信の分野の基本的な問題は、所与のブロック長と伝送速度のデータに最適または準最適な誤り訂正符号（ＥＣＣ）を生成し、これらの誤り訂正符号を実際的に復号することもできる点である。この問題は、今や、短いブロック長（例えば、長さＮ＜１００ビットのブロック）でも、また非常に長いブロック長（例えば、Ｎ＞１０６ビット）でも、ほぼ解決されている。しかしながら、多くの用途、例えば無線通信で用いられる誤り訂正符号は、一般に、中間的な範囲（およそＮ＝２０００ビット）のブロック長を有する。これらのブロック長に最適な符号を生成することが、今なお問題となっている。
【０００３】
多くが最適または準最適であることがわかっている短いブロック長では、多数の誤り訂正符号が知られている。このブロック長が充分短い限り、これらのＥＣＣは、最尤復号器を用いて、実際的に、かつ最適に復号できる。
【０００４】
非常に長いブロック長に最適な符号を見つけ出す問題は、一般化パリティ検査行列で定義されたパリティ検査符号によって、本質的に解決されてきた。これらのタイプの符号は、「低密度のパリティ検査符号」（MIT Press１９６３年発行のResearch Monograph Series第２１巻）の中で、R.G.Gallager氏により初めて述べられたが、最近まで、正しく評価されなかった。もっと最近では、疎な一般化パリティ検査行列で定義された改良符号、例えば、ターボ符号、イレギュラー低密度パリティ検査（ＬＤＰＣ）符号、Ｋａｎｔｅｒ−Ｓａａｄ符号、反復・累積符号、イレギュラー反復・累積符号が述べられた。
【０００５】
これらの改良された符号は、特に注目すべき３つの利点を持っている。第１に、これらの符号は、ＢＰ（belief propagation）反復復号法を用いて、効率的に復号できる。第２に、これらの符号の性能は、理論上、無限ブロック長の限界において、密度変化法を用いて解析できることが多い。第３に、密度変化法を用いれば、これらの符号が準最適な符号であることを実証できる。無限ブロック長の限界において、これらの符号のＢＰ復号法は、あるしきいレベルよりも低い雑音レベルを有するすべてのデータブロックを復号する。また、そのしきいレベルは、シャノン限界から遠くないことが多い。
【０００６】
改良符号を生成する好ましい従来技術の方法は、密度変化を用いて、無限ブロック長の限界に符号を最適化し、縮小バージョンであっても準最適な符号が得られると期待することであった。この方法の問題点は、Ｎ＜１０４では、少なくとも、このブロック長が、無限ブロック長の限界から、なお著しく遠いことである。特に、無限ブロック長の計算により予測されたしきいレベルよりもずっと低い雑音レベルで、多くの復号失敗が認められる。さらに、密度変化法から得られた符号を縮小する方法が、必ずしもあるとも限らない。
【０００７】
例えば、Ｎ→∞限界において所与の速度の、もっともよく知られたイレギュラーＬＤＰＣ符号は、何百、あるいは、何千ものパリティ検査に関与すべき変数ノードを持つことが多く、このことから、総体的なパリティ検査数が１００以下であるときには、まったく意味がない。
【０００８】
（二元消失通信路（ＢＥＣ）用の密度変化法）
この密度変化法は、二元消失通信路では単純である。二元消失通信路は、３つの出力シンボル、すなわち、０、１、消失（疑問符「？」で表現できる）を有する２元入力通信路である。この方法は、本発明による方法に対して重要なバックグラウンドであるから、さらに細かく違いを識別する。
【０００９】
（パリティ検査符号）
線形ブロック２進誤り訂正符号は、パリティ検査行列の点から定義できる。パリティ検査行列Ａでは、列は、送信変数ビットを表わし、また行は、変数ビット間の線形の拘束または検査を定める。さらに具体的には、行列Ａは、一組の有効なベクトルまたは符号語ｚを定義し、ｚの各成分が０か１のいずれかであり、また次式が成り立つようにしている。
【００１０】
ＡＺ＝０                                                  （１）
【００１１】
式中、すべての乗算と加算は、モジュロ２である。
【００１２】
このパリティ検査行列がＮ個の列とＮ−ｋ個の行を有する場合には、このパリティ検査は、ブロック長Ｎと伝送速度ｋ／Ｎの誤り訂正符号を定める。ただし、これらの行の一部が線形従属である場合にはこの限りではなく、このような場合、これらのパリティ検査の一部は冗長であり、またその符号は、実際には、さらに速い伝送速度を持つ。
【００１３】
図１に示されるように、パリティ検査行列ごとに、対応するタナーグラフがある。Ｒ．Ｍ．タナー氏の「低複雑度符号への再帰的方法」（１９８１年発行のIEEE Trans.Info.Theory，ＩＴ−２７、５３３〜５４７ページ）を参照のこと。タナーグラフ１００は、円で表わされる変数ノードｉと、四角で表わされるチェックノードａという２つのタイプのノードを有する２部グラフである。タナーグラフでは、各変数ノードは、変数ノードｉの検査に関与するチェックノードに連結される。例えば、次式のパリティ検査行列
【００１４】
【数１】
0004046543.tif 000002
【００１５】
は、図１に示される２部タナーグラフで表わされる。
【００１６】
実施の用途では、これらのグラフは、一般に、任意の数の異なるやり方で連結された何千ものノード（多数のループを有する）を含むものであることが理解されよう。このようなグラフを解析して、最適な構成を決定することは困難である。
【００１７】
パリティ検査行列で定義された誤り訂正符号は線形符号である。これは、各符号語が、他の符号語の線形組合せであることを意味している。検査行列では、それぞれ長さＮである２ｋ個の可能な符号語がある。上述の例では、これらの符号語は、００００００、００１０１１、０１０１１０、０１１１０１、１００１１０、１０１１０１、１１００１１、１１１０００である。線形の性質のために、これらの符号語はどれも、代表的なものである。それゆえ、符号を解析するために、通常は、すべて零の符号語が送られるものと仮定される。
【００１８】
（ＢＥＣでのＢＰ（belief propagation）復号法）
入力ビットは、確率ｘを有する消失として２元消失通信路を通り、確率１−ｘで正確に受け取られる。ＢＥＣは、ビットを０から１に（あるいは、その逆に）、絶対に切り換えないことに留意することが重要である。すべて零の符号語が送られる場合には、受け取られる語は、完全に、ゼロと消失から成っていなければならない。
【００１９】
受信機は、ＢＰ復号器を使用して、離散的メッセージをタナーグラフのノード間に通すことで、これらの入力ビットを復号する。メッセージｍｉａは、各変数ノードｉから、各変数ノードｉに連結された各チェックノードａへ送られる。このメッセージは、変数ノードｉの状態を表わす。一般に、このメッセージは、３つの状態の１つ、すなわち１、０、または？であることができるが、すべて零の符号語がいつでも送られるために、ｍｉａが値１を持つ可能性は無視できる。
【００２０】
同様に、各チェックノードａから、各チェックノードに連結されたすべての変数ノードｉへ送られるメッセージｍａｉがある。これらのメッセージは、変数ノードが、どのような状態にあるべきかについての、チェックノードａから変数ノードｉへの指示語と解される。このメッセージは、このチェックノードに連結された他の変数ノードの状態に基づいている。これらのｃｈｅｃｋ−ｔｏ−ｂｉｔメッセージは、原則として、０、１、または？の値を取ることができるが、やはり、すべて零の符号語が送られるときには、０と？の２つのメッセージしか妥当でない。
【００２１】
ＢＥＣ用のＢＰ復号プロセスにおいて、変数ノードｉからチェックノードａへのメッセージｍｉａは、そのようなメッセージがＢＥＣでは常に正しいために、非消失受信メッセージに等しいか、あるいは、入ってくるメッセージがすべて消失であるときには、消失に等しい。この検査に関与する別のノードから入ってくるどんなメッセージも消失であるときには、チェックノードａから変数ノードｉへのメッセージｍａｉは、消失であり、そうでなければ、メッセージｍａｉは、この検査に関与する他のノードから入ってくるすべてのメッセージの２進和の値を取る。
【００２２】
ＢＰ復号は、反復復号である。これらのメッセージを初期設定して、この通信路では消失されないすべての変数ノードが、対応する受信ビットに等しいメッセージを送り出し、また他のすべてのメッセージが、当初、消失であるようにする。ＢＰメッセージ・プロセスの反復は、終局的には定常メッセージに収束する。なぜなら、ＢＰ復号の収束は、特に単純なＢＥＣでは保証されるが、それ以外の通信路では保証されないからである。入ってくる非消失メッセージがない場合を除き、任意の消失された変数ノードの最終復号値は、まさに、そのノードに入ってくる任意の非消失メッセージの値である。このような場合、ＢＰ復号プロセスは終了し、特定の変数ノードを復号しそこなう。
【００２３】
（密度変化）
ここでは、多数のブロックにわたるＢＰ復号に対する平均失敗確率を考察する。このメッセージｍｉａが消失である確率を表わす実数ｐｉａは、各メッセージｍｉａと関連付けられる。同様に、メッセージｍａｉが消失である確率を表わす実数ｑａｉは、各メッセージｍａｉと関連付けられる。密度変化法では、確率ｐｉａとｑａｉは、誤り訂正符号を表わすタナーグラフがループを持たない限り、正確なやり方で決定される。
【００２４】
ｐｉａの式は、以下である。
【００２５】
【数２】
0004046543.tif 000003
【００２６】
式中、ｂ∈Ｎ（ｉ）＼ａは、チェックノードａを除き、隣接変数ノードｉに直結されたすべてのチェックノードを表わす。この式は、メッセージｍｉａが消失であるためには、変数ノードｉを送信時に消失しなければならず、また他の検査から入ってくるメッセージもすべて、消失であるという事実から、導き出すことができる。もちろん、入ってくるメッセージが相関関係にある場合には、この式は、正確ではない。しかしながら、ループを持たないタナーグラフでは、入ってくるメッセージはそれぞれ、他のすべてのメッセージとは無関係である。
【００２７】
同様に、以下の式
【００２８】
【数３】
0004046543.tif 000004
【００２９】
は、入ってくるメッセージがすべて、ゼロか１のいずれかの状態にあるときに、メッセージｑａｉも、０または１の状態でしかあり得ないという事実から、導き出すことができる。
【００３０】
密度変化の式（３）と（４）は、反復により解くことができる。この反復がｑａｉメッセージから始まる限り、適切な初期設定は、変数ノードからチェックノードへのあらゆるメッセージに対してｐｉａ＝ｘであり、またチェックノードから変数ノードへのあらゆるメッセージに対してｑａｉ＝０である。ＢＥＣの密度変化式は、最終的に収束する。これは、ループを持たないグラフにおいて定義された符号に対して保証できる。変数ノードｉにて復号しそこなう確率であるｂｉを、次式から決定することができる。
【００３１】
【数４】
0004046543.tif 000005
【００３２】
（小符号の正確な解）
上述の通り、密度変化式（３），（４），（５）は、この符号が、ループ無しのタナーグラフ表現を持つときに、正確である。
【００３３】
次式のパリティ検査行列で定義され、かつ、図２に示される対応するタナーグラフで表現された誤り訂正符号を考えてみる。
【００３４】
【数５】
0004046543.tif 000006
【００３５】
この符号は、００００、００１１、１１０１、１１１０という４つの符号語を有する。００００のメッセージが送られる場合には、００００、０００？、００？０、００？？、０？００などの１６個の可能な受信メッセージがある。ｎｅ個の消失を有するメッセージを受け取る確率は、ｘｎｅ（１−ｘ）４−ｎｅである。メッセージは、ＢＰ復号器により、部分的にまたは完全に復号されることもある。例えば、受信メッセージ？００？は、００００に完全に復号されるが、ただし、メッセージ０？？？は、部分的にのみ００？？に復号される。なぜなら、送信符号語が、実際に００００または００１１であったかどうか判定するのに充分な情報がないからである。
【００３６】
所与のビットが復号後に消失にとどまる正確な確率を、確率によって重みを付けられた１６個の可能な受信メッセージにわたって合計することで、決定することは容易である。例えば、第１のビットは、次のメッセージの１つ（すなわち、？？？０、？？０？、または、？？？？）を受け取ったときに、消失としてのみ復号される。したがって、第１のビットが復号されない正確な確率は、２ｘ３（１−ｘ）＋ｘ４＝２ｘ３−ｘ４である。
【００３７】
的を最後のビットに絞る場合には、このメッセージは、次のメッセージの１つ（すなわち、００？？、０？？？、？０？？、？？０？、または、？？？？）を送る場合を除き、復号される。それゆえ、第４のビットが復号されない総体的な確率は、ｘ２（１−ｘ）２＋３ｘ３（１−ｘ）＋ｘ４＝ｘ２＋ｘ３−ｘ４である。密度変化法では、ｐ１１、ｐ２１、ｐ２２、ｐ３２、ｐ４２、ｑ１１、ｑ１２、ｑ２２、ｑ２３、ｑ２４、ｂ１、ｂ２、ｂ３、ｂ４の変数の値は、次式で決定される。
【００３８】
ｐ１１＝ｘ                                                （７）
ｐ２１＝ｘｑ２２                                          （８）
ｐ２２＝ｘｑ１２                                          （９）
ｐ３２＝ｘ                                                （１０）
ｐ４２＝ｘｑ１１＝ｐ２１                                  （１１）
ｑ１２＝ｐ１１                                            （１２）
ｑ２２＝１−（１−ｐ３２）（１−ｐ４２）                  （１３）
ｑ２３＝１−（１−ｐ２２）（１−ｐ４２）                    （１４）
ｑ２４＝１−（１−ｐ２２）（１−ｐ４２）                    （１５）
および、
ｂ１＝ｘｑ１１                                              （１６）
ｂ２＝ｘｑ１２ｑ２２                                        （１７）
ｂ３＝ｘｑ２３                                              （１８）
ｂ４＝ｘｐ２４                                              （１９）
【００３９】
上記の式を解けば、次式が得られる。
【００４０】
ｐ１１＝ｘ                                                  （２０）
ｐ２１＝２ｘ２−ｘ３                                        （２１）
ｐ２２＝ｘ２                                                （２２）
ｐ３２＝ｘ                                                  （２３）
ｐ４２＝ｘ                                                  （２４）
ｐ１１＝２ｘ２−ｘ３                                        （２５）
および、
ｑ１２＝ｘ                                                  （２６）
ｑ２２＝２ｘ−ｘ２                                          （２７）
ｑ２３＝ｘ＋ｘ２−ｘ３                                      （２８）
ｑ２４＝ｘ＋ｘ２−ｘ３                                      （２９）
および、
ｂ１＝２ｘ３−ｘ４                                          （３０）
ｂ２＝２ｘ３−ｘ４                                          （３１）
ｂ３＝ｘ２＋ｘ３−ｘ４                                      （３２）
ｂ４＝ｘ２＋ｘ３−ｘ４                                      （３３）
【００４１】
ｂ１とｂ４の結果を調べれば、密度変化の解が、この符号用の直接のアプローチと正確に一致することが示される。
【００４２】
（長いブロック長の限界）
タナーグラフのすべての局所近傍が同一である場合には、密度変化式を簡約することができる。例えば、各変数ノードｉが、ｄｖ個のパリティ検査に連結され、また各チェックノードａがｄｃ個の変数ノードに連結される場合には、すべてのｐｉａは、同一値ｐに等しく、すべてのｑａｉは、同一値ｑに等しく、すべてのｂｉは、同一値ｂに等しい。したがって、
【００４３】
【数６】
0004046543.tif 000007
および、
【数７】
0004046543.tif 000008
【００４４】
これらの式は、Ｎ→∞限界において有効である（ｄｖ，ｄｃ）のレギュラーＧａｌｌａｇｅｒ符号用の密度変化式である。レギュラーＧａｌｌａｇｅｒ符号は、各行が、正確にｄｃ個の１を含み、また各列が、正確にｄｖ個の１を含むという制限を特徴とする疎なランダム・パリティ検査行列である。
【００４５】
これらの式が、無限ブロック長の限界において有効であるという直観的な理由は、Ｎ→∞のときに、レギュラーＧａｌｌａｇｅｒ符号のタナーグラフの代表的ループのサイズが無限大となり、したがって、ノードに入ってくるすべてのメッセージが別々となり、またレギュラーＧａｌｌａｇｅｒ符号は、ループなしのグラフ上で定義された符号として挙動する。ｄｖとｄｃの特定の値に対して、式（３４）と（３５）を解くと、ｘｃという臨界消失限度値よりも下で、ｐ＝ｑ＝ｂ＝０である解が得られる。これは、復号が完全であるということを意味している。ｘｃよりも上では、ｂは、非零の解を持ち、この解は、復号失敗に相当する。値ｘｃは、数値的に容易に決定できる。例えば、ｄｖ＝３およびｄｃ＝５の場合には、ｘｃ≒０．５１７５７である。
【００４６】
これらの密度変化計算は、イレギュラーＧａｌｌａｇｅｒ符号、あるいは、近傍が異なる有限数の異なるノード・クラスを有するイレギュラー反復・累積符号のような他の符号に一般化できる。このような一般化では、一般に、それぞれのノード・クラスを離れるメッセージに対して１つの方程式がある連立方程式を導き出すことができる。これらの連立方程式を解くことにより、やはり、臨界しきい値ｘｃを求めることができ、このしきい値よりも下では、復号が完全である。したがって、このような符号は、最大雑音しきい値ｘｃを有する符号を見つけることで、Ｎ→∞限界において最適化できる。
【００４７】
【発明が解決しようとする課題】
あいにく、密度変化法は、有限ブロック長の符号では、誤りがある。どんな有限符号に対しても方程式（３）と（４）を解くことが可能であると考え、しかも、ループの存在を無視することが、それほど重大な誤りではないと期待する場合もある。しかしながら、これは、レギュラーＧａｌｌａｇｅｒ符号を考慮すればわかるように、うまくいかない。有限ブロック長のレギュラーＧａｌｌａｇｅｒ符号用の方程式（３）、（４）、（５）は、無限ブロック長の限界において求めることになる解とちょうど同じ解を持ち、したがって、いかなる有限サイズの影響も予測しないであろう。しかしながら、有限ブロック長のレギュラーＧａｌｌａｇｅｒ符号の実際の性能は、このような単純な方法で予測されるものよりもかなり悪いことが知られている。
【００４８】
それゆえ、従来技術の方法の問題を伴わない有限長の誤り訂正符号を正しく評価する方法が必要である。
【００４９】
【課題を解決するための手段】
本発明は、２元消失通信路、または加法白色ガウス雑音通信路において、有限サイズのデータブロックに対して誤り訂正符号を評価する方法を提供する。誤り訂正符号は、列が変数ビットを表わし、行がパリティビットを表わす一般化パリティ検査行列によって定義される。この行列の表記法では、この通信路を通じては送られない「隠れ」変数ビットは、この一般化パリティ検査行列の対応する列の上に、横線で表わされる。この一般化パリティ検査行列は、２部グラフとして表わされる。２部グラフ中のノードの数が、所定のしきい値よりも小さくなるまで、この２部グラフ中の単一ノードを、反復的に繰り込む。
【００５０】
反復的な繰り込みの間、目標ノードとして、特定の変数ノードを選択し、その目標ノードと、２部グラフ中の他のあらゆるノードとの距離を測定する。次に、「葉」変数ノードが少なくとも１つある場合には、目標ノードからもっとも遠い葉変数ノードを繰り込む。そうでなければ、目標ノードからもっとも遠い葉チェックノードを繰り込み、また、そうでなければ、目標ノードからもっとも遠く、かつもっとも少ない直結チェックノードを有する変数ノードを繰り込む。葉ノードは、このグラフ中の他の１つのノードだけに連結される。
【００５１】
このグラフ中のノードの数が、所定のしきい値よりも少ないときには、目標ノードに対する復号失敗率が、正確に決定される。
【００５２】
本発明は、雑音の関数としての復号失敗の点から最高の性能を有する、指定したデータブロックサイズと伝送速度の誤り訂正符号を探すことで、誤り訂正符号を最適化する方法を提供する。最適な符号の探索を導くために、送信変数ビットに対する復号失敗率を利用する。
【００５３】
【発明の実施の形態】
（繰り込み群法）
本発明は、「実空間」の繰り込み群変換を用いることで、誤り訂正符号を評価する。本発明の繰り込み群（ＲＧ）法は、「相転移と臨界現象」（１９７６年版第６巻、監修者Ｃ．Ｄｏｍｂ氏およびＭ．Ｓ．Ｇｒｅｅｎ氏、ＡｃａｄｅｍｉｃＰｒｅｓｓ，Ｌｏｎｄｏｎ）の中で、Ｔ．Ｎｉｅｍｅｉｊｅｒ氏とＪ．Ｍ．Ｊ．ｖａｎ Ｌｅｅｕｗｅｎ氏により述べられた磁気スピン系の解析のための技法から修正変更されたものである。繰り込み群は、データの記憶および伝送に用いられる誤り訂正符号に、かつて応用されたことはなかった。
【００５４】
大きいが、ただし、有限の誤り訂正符号の性能を評価するために、本発明では、大きい符号を、同一の、またはほぼ同一の性能（すなわち、復号失敗率）を有するわずかに小さい符号に反復的に代える。特に、本発明では、その反復法の各段階にて、タナーグラフと、一組の確率変数ｐｉａおよびｑａｉを、タナーグラフのノードにより送られたメッセージと関連付けておく。本発明を記述する目的で、タナーグラフと、ｐおよびｑの変数との組合せを、「修飾タナーグラフ」と呼ぶ。
【００５５】
本発明のＲＧ法の基本は、ＲＧ変換であり、このＲＧ変換を使って、本発明では、この修飾タナーグラフ中の単一ノードを反復的に排除し（すなわち、「繰り込み」）、また、ｐおよびｑのメッセージの残りの値を調整して、少ない方の誤り訂正符号の復号失敗率を、その代えられた符号にできる限り近づけるようにしている。
【００５６】
したがって、繰り込み段階ごとに、本発明の符号を表わす修飾タナーグラフが、１ノードだけ収縮し、このような処理は、このグラフが、最終的に、誤り訂正符号の性能を効率的なやり方で決定できるくらい小さくなるまで、続けられる。これと対照的に、従来技術の密度変化法は、ノード数、あるいは、ノードを互いに連結する方法を絶対に変更しない。言い換えれば、それらのグラフは静的であるが、一方、本発明のグラフは、繰り込みの間、動的に変化する。本発明のグラフが充分小さいとき、例えば、残りのノードの数が、所定のしきい値よりも少ないときには、その失敗率は、容易に決定できる。一実施形態において、本発明では、このグラフを、単一ノードまで縮小する。
【００５７】
図９は、本発明による一般的な方法９００のステップを示している。復号失敗率ｂｉを決定する本発明の修飾タナーグラフ中の選択「目標」変数ノードｉごとに、このグラフからの単一ノード（目標ノード以外）を、所定のしきい値９５０に達するまで、繰り返して繰り込む。このしきい値は、所望のノード数、あるいは、残りのノードに対する所望の失敗率として表わすことができる。ノードは、以下のように、繰り込まれる。
【００５８】
他のあらゆるノードと、「目標」ノードｉとの間の「距離」を測定する（９１０）。２つのノード間の距離は、一方のノードから他方のノードに移動するのに通るノードの最小数（すなわち、介在するノードの数）である。
【００５９】
「葉」変数ノードがあれば、「目標」ノードからもっとも遠い葉変数ノードを繰り込む（９２０）。あるノードは、それが、グラフ中の他の１つのノードにしか連結されないときには、葉ノードである。距離の結合は、ランダムに断たれることがある。
【００６０】
そうでなく、「葉」変数ノードがなければ、「目標」ノードからもっとも遠い「葉」チェックノードを繰り込む（９３０）。この場合も、結合が、ランダムに断たれることがある。
【００６１】
そうでなく、「葉」チェックノードがなければ、「目標」ノードからもっとも遠い変数ノードの中から、最小数のチェックノードに直結された１つの変数ノードを繰り込む（９４０）。この場合も、結合が、ランダムに断たれることがある。
【００６２】
これらの繰り込みステップは、このグラフを、所望のノード数まで縮小するまで、反復的に繰り返される。これらのステップの詳細は、以下でさらに詳しく説明される。
【００６３】
上記のステップは、所望数の目標ノードに適用できる。例えば、グラフ中のあらゆるノードの平均失敗率を決定できる。実施の用途では、この繰り込みは、同じノードの群を表わす目標ノードに適用される。この場合、このノード群が、誤り訂正能力に関して、「強い」のか「弱い」のかを判定できる。この場合、この情報を使用すれば、誤り訂正符号の総体的な性能を向上させることができる。例えば、弱い群のノードは、さらに多くのパリティ検査に連結できる。したがって、本発明は、構造化されたやり方で誤り訂正符号を向上させる手段を提供する。
【００６４】
（ループを有さない修飾タナーグラフ用のＲＧ変換）
はじめに、ループのないタナーグラフを考慮に入れて、このような誤り訂正符号に対して、正確な失敗率を得るのに充分なＲＧ変換を決定する。次に、ＲＧ変換を拡大して、ループを有するタナーグラフに対して、優れた近似結果を得る。
【００６５】
本発明では、常に、その修飾タナーグラフを初期設定して、すべてのｂｌ＝ｘ、ｐｉａ＝ｘ、すべてのｑａｉ＝０が成り立つようにする。本発明は、指定した目標変数ノードｉでの復号失敗率ｂｉに関与している。本発明の方法９００は、目標変数ノードｉ自体以外のノードを、上述のように、一度に１つ、繰り返して繰り込むことで、ｂｉを得る。
【００６６】
第１の可能性は、目標ノードｉに連結されたもっとも遠い「葉」変数ノードを繰り込むことである。この葉ノードが「消える」と、ｐｉａとｑａｉも捨てられることが明らかである。本発明では、目標ノードｉから他の変数ノードｊに至るすべてのｑａｊ変数も繰り込む。このような繰り込みに関する本発明の式は、次式で示される。
【００６７】
ｑａｊ←１−（１−ｑａｊ）（１−ｐｉａ）                      （３７）
【００６８】
式中、左向きの矢印は、ｑａｊの旧値を新値に代えることを示している。ｑａｊの繰り込みごとに、その値が増すことに注目されたい。
【００６９】
単一の変数ノードにしか連結されない「葉」チェックノードａを繰り込むときに、目標ノードｉが結び付けられている他のチェックノードｂに至るすべてのｐｉｂ変数の値を調整する。この繰り込み群変換は、次式である示される。
【００７０】
ｐｉｂ←ｐｉｂｑａｉ                                        （３８）
【００７１】
ｐｉｂの繰り込みごとに、その値が減ることに注目されたい。また一方では、次式のように、ｂｉも繰り込まなければならない。
【００７２】
ｂｉ←ｂｉｑａｉ                                            （３９）
【００７３】
ステップ９４０の繰り込みは、ループの多いグラフについて、以下でさらに詳しく述べる。
【００７４】
「目標」ノードｉだけが残っているときには、平均失敗率のＲＧ予測として、ノードｂｉの現時点の値を使用する。上述の通り、これらのステップは、任意の数の目標ノードに対して、繰り返すことができる。
【００７５】
（例）
本発明によるＲＧ法をよりよく説明するために、以下の単純な例を与える。次式のパリティ検査行列により定義された誤り訂正符号を想起されたい。
【００７６】
【数８】
0004046543.tif 000009
【００７７】
第２の変数ノードｂ２での復号失敗率を決定したい。ｐ＝ｐ２１＝ｐ２２＝ｐ３２＝ｐ４２＝ｘ、ｑ１１＝ｑ１２＝ｑ２２＝ｑ２３＝ｑ２４＝０、およびｂ２＝０を初期設定する。
【００７８】
図３（ａ）に示されるように、本発明では、この符号のために、タナーグラフを修飾した。変数ノード２以外の変数ノードのすべては葉ノードであり、したがって、それらの変数ノードのどれでも繰り込むことができる。本発明の一般的な方法９００により、ノード２からもっとも遠いノードを繰り込んで、結合をランダムに断つ。変数ノード４を選択する場合には、ｐ４２とｑ２４を捨てて、式（３７）を用いて、新値ｑ２２＝ｘとｑ２３＝ｘを得る。
【００７９】
縮小サイズの新たなタナーグラフが、図３（ｂ）に示されている。次に、変数ノード３を繰り込む。ノードｐ３２とｑ２３を捨てて、ノードｑ２２を、値１−（１−ｘ）２＝２ｘ−ｘ２に繰り込む。さらに小さい修飾タナーグラフが図３（ｃ）に示されている。次に、変数ノード１を繰り込む。ノードｐ１１とｑ１１を捨てて、さらに小さい繰り込まれた値ｑ１２＝ｘを得る。このタナーグラフは、図３（ｄ）に示されている。次に、チェックノード２を繰り込む。ノードｐ２２とｑ２２を捨てて、図３（ｅ）のタナーグラフに関して図示されるようにｐ２１＝ｂ２＝２ｘ２−ｘ３を得ることができる。最後に、チェックノード１を繰り込む。これは、単一の変数ノード、すなわち、元の目標ノード２だけを残し、ｂ２は、上述のように、その正確な失敗率ｂ２＝２ｘ３−ｘ４に繰り込まれる。
【００８０】
この例により、ループを持たないグラフ上で定義された符号語に対して、ＲＧ法がなぜ正確であるのか明らかになる。ＲＧ変換は、本質的に、従来技術の密度変化式を再構成するものであり、このような誤り訂正符号に対して、密度変化が正確であることはわかっている。本発明のＲＧ法の利点は、ループを「有する」２部グラフで表わされる誤り訂正符号に対して、ＲＧ法が、さらに優れた近似を与えることである。優れた誤り訂正符号は、中位のサイズでも、常にループを持つことがよくわかっている。その主な理由として、ループは、実質的に符号のサイズを大きくすることなく、冗長さを提供するからである。
【００８１】
（ループを有するグラフ用のＲＧ法）
ループを有するグラフで表わされる誤り訂正符号では、終局的には、「葉」ノードではないノードを繰り込まなければならない（９４０）。本発明では、非葉チェックノードを絶対に繰り込む必要がないことに留意されたい。これを行うために、はじめに、目標ノードｉに連結されたすべてのチェックノードａ、ｂなどを収集し、ｑａｉ、ｑｂｉ、ｐｉａ、ｐｉｂなどを捨てる。ノードｉに結び付けられた任意の所与のチェックノード（例えば、チェックノードａ）では、ノードａに結び付けられた他のすべての変数ノードｊも収集して、ｑａｊの値を繰り込む。
【００８２】
ｑａｊ変数の繰り込みも、様々な精度で行うことができる。もっとも単純な方法は、直接、式（３７）を利用する。この方法の問題は、ｐｉａの値が、常に過大評価であることである。ｐｉａは、繰り込みごとに「減る」ことを想起されたい。ｉ番目のノードを繰り込んだ後で、そのノードが葉ノードになるから、ｐｉａは、まだ完全には繰り込まれておらず、したがって、過大評価される。
【００８３】
直接、ｐｉａを使用する代わりに、ｐｉａに連結されたあらゆるチェックノードを繰り込んだ後で、ｐｉａが取る値を使用することもできる。すなわち、式（３７）中のｐｉａを、次式で与えられた実効値ｐｉａｅｆｆに代えることもできる。
【００８４】
【数９】
0004046543.tif 000010
【００８５】
その一方、ｑｂｉの値は過小評価であることがわかっている。なぜなら、ｑｂｉの値も、まだ完全には繰り込まれておらず、したがって、ｐｉａｅｆｆも過小評価であるからである。さらに別のレベルに進むことで、このような誤りを訂正しようとすることもできる。ｐｉａｅｆｆを評価する前に、はじめに、ｐｉａｅｆｆに流れ込むｑｂｉを再評価する。したがって、式（３７）中のｐｉａを、次式で与えられた実効値ｐｉａｅｆｆに代える。
【００８６】
【数１０】
0004046543.tif 000011
【００８７】
式中、ｑｂｉｅｆｆは、さらに次式で与えられる。
【００８８】
【数１１】
0004046543.tif 000012
【００８９】
これらのすべての式をまとめて、最終的に、次式のＲＧ変換を得る。
【００９０】
【数１２】
0004046543.tif 000013
【００９１】
式（４４）のＲＧ変換は、さらに詳しく説明するに値する。
【００９２】
図４において、変数ノードｉが、ａ、ｂ、ｃの３つのチェックノードに結び付けられ、かつ、チェックノードａが変数ノードｊに結び付けられたタナーグラフが示されている。チェックノードｂおよびｃは、ｋ、ｌ、ｍ、ｎと標記された変数ノードに連結される。変数ノードｉを通る情報を考慮に入れて、チェックノードａが変数ノードｊに消失メッセージを送る確率ｑａｊを知りたい。
【００９３】
本発明では、チェックノードａが変数ノードｊに消失メッセージを送る、以前のある累積確率ｑａｊをすでに得ている。なぜなら、以前に、他のノードを、すでに繰り込まれたチェックノードａに結び付けているからである。
【００９４】
消失メッセージの新たな確率は、以下の論理的推論から決定できる。
「ｍａｊは、それがすでに消失であった場合、あるいは、ｍｉａが消失であり、かつ、
（ｍｂｉまたはｍｋｂまたはｍｌｂが消失であり）、かつ、（ｍｃｉまたはｍｍｃまたはｍｎｃが消失である）場合に、消失である。」
【００９５】
このような論理的推論を、確率用の式に変換することは簡単である。論理的推論において、２つのメッセージに対して「ｍ１およびｍ２」を得れば、これらの項を、対応する確率用の（ｐ１ｐ２）に変換するが、一方、「ｍ１またはｍ２」は、（１−（１−ｐ１）（１−ｐ２））に変換される。図４用の本発明の論理的推論全体を、確率用の式に変換すれば、式（４４）のＲＧ変換の一例を復元することができる。
【００９６】
本発明では、常に、ｑａｊ用のＲＧ変換を、繰り込んでいる変数ノードｉを中心とする局所近傍の論理に一致させる。実際、式（４４）に与えられたＲＧ変換は、ノードｉの局所近傍がツリー型であれば、適切であり、また、この局所近傍にループがあれば、調整されるべきである。
【００９７】
例えば、図５のグラフは、変数ノードｋをｂとｃの２つのチェックノードに結び付け、さらに、これら２つのノードをそれぞれ、繰り込まれる変数ノードｉに結び付けた場合を示している。チェックノードｂまたはｃを繰り込む前に、変数ノードｋが消失を送出する確率ｐｋｂとｐｋｃは、ｐｋｂとｐｋｃのすべての繰り込みが、相前後して起こるために、同一でなければならないことに留意されたい。
【００９８】
したがって、チェックノードａが、消失メッセージを変数ノードｊに送るかどうかについての論理的推論は、以下の通りである。
「ｍａｊは、それがすでに消失であった場合、あるいは、（（ｍｉａが消失であり）、
かつ、
（（ｍｋｂが消失であり）、あるいは、（ｍｂｉおよびｍｃｉが消失である）））場合に、消失である。」
【００９９】
繰り込みプロセスのこの段階では、ｍｋｂが消失である場合に、ｍｋｃも消失でなければならない。本発明の論理的推論をＲＧ変換に変えると、次式を得る。
【０１００】
ｑａｊ←１−(１−ｑａｊ)(１−ｐｉｊ(１−(１−ｐｋｂ)(１−ｑｂｉｑｃｉ)))（４５）
【０１０１】
正しく処理されたノードを中心とする近傍のサイズを大きくすれば、非葉変数ノードｉを繰り込む段階を、さらに正確にすることができる。もちろん、この近傍のサイズを大きくすると、さらに優れた計算法を用いて、精度を上げることに対処しなければならない。
【０１０２】
図１０は、葉ノードではない変数ノードを繰り込む方法（すなわち、図９のステップ９４０）を要約している。
【０１０３】
ステップ１０１０は、繰り込まれる変数ノードに連結されたａ、ｂなどのすべてのチェックノードを列挙して、これらのチェックノードと変数ノードとの間のすべての確率変数ｐｉａ、ｐｉｂ、ｑａｉ、ｑｂｉなどを捨てる。
【０１０４】
隣接するチェックノードの１つａに結び付けられた変数ノードｊごとに、以下のサブステップにより、ｑａｊの値を繰り込む。
【０１０５】
ステップ１０２０は、局所近傍において、繰り込まれる変数ノードｉから所定の距離までの、あらゆるチェックノードと変数ノードを見つける。これらの距離は、上述のように測定される。
【０１０６】
論理的推論を利用して、消失メッセージのどのような組合せにより、チェックノードａから変数ノードｊへのメッセージも消失となるのか決定する１０３０。
【０１０７】
上述の通り、この論理的推論を、ｑａｊ用のＲＧ変換に変える１０４０。
【０１０８】
（ＲＧ変換の正確な完了）
上述の通り、本発明のＲＧ法は、「目標」ノードｉのみを残すまで、常にノードを繰り込み、次に、復号失敗率ｂｉを決定することができる。その一方、本発明では、正確な決定を行うのに充分な数のノードを繰り込むこともできる。
【０１０９】
この正確な決定を説明する目的で、代りに、Ｎ個のノードのタナーグラフと、このグラフのノードｉごとの関連消失確率ｘｉを用いて、誤り訂正符号を表わす。この「消失グラフ」は、上述の修飾タナーグラフ３０１〜３０５とは異なる。この復号失敗率は、消失グラフに対して正確に決定できるが、ただし、その正確な計算は、消失確率グラフ中のノードの数が少ない場合にのみ、実施可能である。消失確率グラフに対して、復号失敗率を正確に決定する方法を述べ、次に、本発明による修飾グラフを、同等な消失グラフに変換する方法を述べる。
【０１１０】
所与のノードｉの復号失敗率を正確に決定するために、すべて零のメッセージから全消失のメッセージに及ぶ２Ｎ個の可能な受信メッセージすべてを生成し、ＢＰ復号器を用いて、メッセージをそれぞれ復号する。
【０１１１】
各メッセージは、次式の確率を持つ。
【０１１２】
ｐ＝ПｘｉП（１−ｘｊ）                                    （４６）
【０１１３】
式中、第１の積は、消失されるあらゆるノードにわたり、また第２の積は、消失されないあらゆるノードにわたる。ノードｉが消失に復号する確率のすべての可能な受信メッセージにわたって加重平均を取ることで、ｂｉを決定する。この正確な計算の複雑性がＯ（２Ｎ）であるために、本発明では、小さいＮに限定したが、それでも、充分なノードを繰り込んだ後で、正確な計算に切り替えれば、ある精度を得ることができる。
【０１１４】
正確な最終計算における１つの微妙な違いは、本発明において、タナーグラフと、変数ノードｉごとの関連消失確率ｘｉを用いて、誤り訂正符号を表わすことである。これと対照的に、一般のＲＧ法は、ただ修飾タナーグラフだけを使用する。幸いにも、修飾タナーグラフを消失グラフに変換することが可能である。ＲＧ法の各段階において、チェックノードａから出るあらゆる確率ｑａｉは等しく（すなわち、ｑａｉ＝ｑａ）、また変数ノードｉから出るあらゆる確率ｐｉａは等しい（すなわち、ｐｉａ＝ｐｉ）ことに留意されたい。
【０１１５】
ｐｋａ＝ｑａの確率を持つ新たな変数ノードｋを、消失グラフ中のノードａに追加することで、すべてのｑａ確率をゼロに等しく設定できる。修飾タナーグラフが残るときには、ｑ確率がすべてゼロになるようにし、また、各変数ノードから出るｐｉａ確率がすべて、ｐｉに等しくなるようにしている。本発明では、ｐｉを、これらの変数ノードの消失確率と解する。
【０１１６】
図６は、修飾タナーグラフ６０１を、消失確率を持つ等価消失タナーグラフ６０２に拡張する一例を示している。
【０１１７】
（一般化パリティ検査行列への拡大）
一般化パリティ検査行列は、ターボ符号、Ｋａｎｔｅｒ−Ｓａａｄ符号、反復・累積符号などの最新の誤り訂正符号の多くを定義している。一般化パリティ検査行列では、「隠れ」ノードを表わすために、パリティ検査行列に、付加的な列を追加している。隠れノードは、他のノードには渡されない状態変数を持っている。すなわち、隠れノードの状態は「隠される」。これらの隠れ状態変数について望ましい表記法は、対応する列上の水平線である。例えば、第１の変数ノードが隠れノードである符号を示すために、次のように書き表す。
【０１１８】
【数１３】
0004046543.tif 000014
【０１１９】
変数ノードが、本発明のグラフィカルモデルにおいて、隠れノードであることを示すために、塗りつぶし円ではなくて、白抜き円を用いている。このようなグラフは、タナーグラフを一般化したものであって、「Ｗｉｂｅｒｇグラフ」と呼ばれる。Ｎ．Ｗｉｂｅｒｇ氏の「一般的なグラフでの符号と復号」（１９９６年リンチェピング大学博士論文）、および、Ｎ．Ｗｉｂｅｒｇ氏らの「一般的なグラフでの符号と反復復号」（１９９５年発行のＥｕｒｏ．Ｔｒａｎｓ．Ｔｅｌｅｃｏｍｍ第６巻、５１３〜５２５ページ）を参照のこと。
【０１２０】
図７は、この一般化パリティ検査行列または式（４７）によって定義された誤り訂正符号を表わすＷｉｂｅｒｇグラフを示している。
【０１２１】
本発明のＲＧ法９００を一般化して、Ｗｉｂｅｒｇグラフを処理するために、通常の送信変数ノードに対して行うのと同様に、消失率ｘではなくて、隠れノードから出る確率ｐｉａを１に初期設定する。これは、隠れノードが常に消失される一方で、通常の変数ノードが、ｘの確率で消失されるという事実を反映している。
【０１２２】
（数値シミュレーションとの比較）
ここで、本発明のＲＧ法のいくつかの実験予測を述べる。Ｎ＝３６およびｋ＝３６と一致するパリティ検査行列により、（３，５）レギュラーＧａｌｌａｇｅｒ誤り訂正符号を定義する。すなわち、このパリティ検査行列内の３６行の各行は、１である５つのエントリを有し、その残りはゼロである。また６０列の各列は、ゼロである３つのエントリを有する。隠れノードはない。どの２つのパリティ検査も、２つ以上の変数ノードを共有しない。これは、ノードのすべての局所近傍がツリー型であることを意味している。それゆえ、非葉変数ノードを繰り込むときはいつでも、ＲＧ変換（４４）を利用する。７つのノードが残されるまでノードを繰り込み、次に、このような決定を正確に終了する。
【０１２３】
ｘ＝０とｘ＝１との間において、０．０５の間隔で消失率ｘを考慮に入れる。ＲＧ近似を利用するときに、すべてのノードｉにわたって復号失敗率ｂｉを平均して、総体的なビット誤り率を得る。本願発明者らの実験は、それぞれの消失率での１０００回の試行を含むが、標準ＢＰ復号法により復号する。
【０１２４】
図８は、本願発明者による実験結果を示している。図８では、ｘ軸は消失率であり、またｙ軸はビット誤り率である。曲線８０１は、従来技術の密度変化予測であり、曲線８０２は、ＲＧ理論的予測であり、白抜き円８０３は、本願発明者による実験結果である。図８は、密度変化予測が、しきい値型の挙動を持ち、短いブロック長または中位のブロック長に対しては完全に誤っているが、しかるに、本発明によるＲＧ法は誤っていないことを明確に示している。
【０１２５】
（ガウス雑音通信路への拡張）
本発明のＲＧ法を拡張して、ＲＧ法を加法的白色ガウス雑音（ＡＷＧＮ）通信路にも使用できるようにする。これは、「ガウス近似を用いた、低密度パリティ検査符号のＳｕｍ−Ｐｒｏｄｕｃｔ復号の解析」（ＩＥＥＥ Ｔｒａｎｓ．Ｉｎｆｏ．Ｔｈｅｏｒｙ、２００１年発行、第４７巻、第２号、６５７〜６７０ページ）の中でＣｈｕｎｇ氏らにより述べられたような、ＡＷＧＮ通信路用の密度変化に、ガウス近似を適応させることで行う。はじめに、この近似を説明する。
【０１２６】
ＡＷＧＮ通信路では、０と１の２つの可能な入力しかないが、出力は、一組の実数である。ｘが入力である場合には、出力は、ｙ＝（−１）ｘ＋ｚである。式中、ｚは、零平均と分散σ２を有するガウス確率変数である。この符号中の受信ビットｉごとに、対数尤度比ｍｉ０＝ｌｎ（ｐ（ｙｉ｜ｘｌ＝０）／ｐ（ｙｉ｜ｘｌ＝１））は、この送信ビットｉがゼロであった相対対数尤度比を決定する（ただし、受信実数をｙｉとする）。
【０１２７】
この誤り訂正符号は、上述のように、一般化パリティ検査行列によって定義される。すべて零の符号語が送られ、その復号プロセスは、ｓｕｍ−ｐｒｏｄｕｃｔのＢＰプロセスである。このような復号プロセスにおいて、実数値のメッセージは、互いの関数として、反復的に解かれる。使用されるタイプの実数値のメッセージは、変数ノードｉからチェックノードａへのｍｉａ、および、チェックノードａから変数ノードｉへのｍａｉである。
【０１２８】
メッセージｍｉａは、変数ノードｉが、ゼロか１のいずれかであるその確率を、チェックノードａに知らせるときに用いる対数尤度比である。例えば、ｍｉａ→∞は、ノードｉが確かにゼロであることを意味するが、一方、ｍｉａ＝１は、変数ノードｉが、ｌｎ（ｐ（ｘｌ＝０）／ｐ（ｘｌ＝１））＝１であることをチェックノードａに信号で知らせていることを意味している。メッセージｍａｉは、変数ノードｉの状態についての、チェックノードａから変数ノードｉへの情報と解される対数尤度比である。
【０１２９】
ｓｕｍ−ｐｒｏｄｕｃｔ復号では、これらのメッセージは、以下の更新ルールにより、反復的に解かれる。
【０１３０】
【数１４】
0004046543.tif 000015
【０１３１】
ノードｉが隠れノードである場合には、ｍｉ０は省略されて、次式となる：
【０１３２】
【数１５】
0004046543.tif 000016
【０１３３】
ＡＷＧＮ通信路用の密度変化法では、確率分布が、あらゆる可能な受信ブロックにわたっての平均値であるようなメッセージに対して、確率分布ｐ（ｍｉａ）とｐ（ｍａｉ）を考慮に入れる。すべてのｘに対してｆ（ｘ）＝ｆ（−ｘ）ｅｘである場合には、分布ｆ（ｘ）は、一致したと呼ばれる。この一致条件は、ｓｕｍ−ｐｒｏｄｕｃｔ復号のもとでのあらゆるメッセージに対して、メッセージ確率分布用に保存される。
【０１３４】
確率分布ｐ（ｍｉａ）とｐ（ｍａｉ）が、ガウス分布として近似される場合には、この一致条件は、これらの分布の平均μが、分散σ２×σ２＝２μに関係することを意味する。このことは、これらのメッセージ確率分布が、単一のパラメータ、すなわち、それらの平均で特徴づけられることを意味する。
【０１３５】
したがって、これらのメッセージ確率分布がガウス分布であるという近似を行うことで、ＡＷＧＮ通信路用の密度変化式を、変数ノードｉからチェックノードａへのメッセージの確率分布の平均ｕｉａ、および、チェックノードａから変数ノードｉへのメッセージの確率分布の平均ｖａｉに対して、首尾一貫した式に縮小することができる。これらの式は、次式である。
【０１３６】
【数１６】
0004046543.tif 000017
【０１３７】
式中、ｕ０はｍｉ０の平均値であって、隠れノードに対しては省かれて、次式となる。
【０１３８】
【数１７】
0004046543.tif 000018
【０１３９】
式中、φ（ｘ）は、次式によって定義された関数である。
【０１４０】
【数１８】
0004046543.tif 000019
【０１４１】
（ＡＷＧＮ通信路用のＲＧ変換）
ガウス近似のもとでのＡＷＧＮ通信路用の密度変化式（５０）および（５１）は、ＢＥＣ通信路用の密度変化式（４）および（３）の類似物である。ＡＷＧＮ通信路用の本発明のＲＧ処理法は、ＢＥＣ通信路用のものとほぼ同一である。主な違いは、ＲＧ変換を変更することである。
【０１４２】
ちょうど前例と同じように、ツリー型のグラフ用の密度変化式を正確に再現する一組のＲＧ変換を構築する。本願発明者は、ｕａｉとｖｉａの変数を、連結ノードのそれぞれの対の間に保つことで、その符号用の修飾Ｔａｎｎｅｒ／Ｗｉｂｅｒｇグラフを生成する。ｕａｉ変数は、無限大に初期設定されるが、一方、ｖｉａ変数は、ｕ０に初期設定される。ただし、ｉ番目のノードが隠れノードである場合にはこの限りではなく、この場合、ｖｉａは、ゼロに初期設定される。本発明ではまた、ｖｉａ変数のように初期設定される変数ｈＩ（ｂｉに類似している）をＢＥＣにも導入する。
【０１４３】
変数ノードｉに連結された葉チェックノードａを繰り込む場合には、ｉに結び付けられた他のチェックノードｂを見出して、以下のＲＧ変換を適用する。
【０１４４】
ｖｉｂ←ｖｉｂ＋ｕａｉ                                      （５３）
【０１４５】
および、
ｈｉ←ｈｉ＋ｕａｉ                                          （５４）
【０１４６】
チェックノードａに連結された葉変数ノードｉを繰り込む場合には、チェックノードａに結び付けられた他の変数ノードｊを見出して、以下のＲＧ変換を適用する。
【０１４７】
ｕａｊ←φ−１(１−(１−φ(ｕａｊ))(１−φ(ｖｉａ)))        （５５）
【０１４８】
ｖｉｂを繰り込むごとに、ｖｉｂの大きさが増す一方で、ｕａｊを繰り込むごとに、ｕａｊの大きさが減ることに留意されたい。
【０１４９】
ａ、ｂなどのチェックノードに連結された非葉変数ノードｉを繰り込むときには、ｕａｊのような変数を繰り込む。ここで、ｊは、チェックノードａに連結された他の変数ノードである。ちょうどＢＥＣの場合のように、ノードｉを中心とするノードの局所近傍を考慮に入れる。例えば、ｉに連結されたチェックノード、および、これらのチェックノードに連結された他の変数ノードの近傍がツリー型である場合には、以下のＲＧ変換を利用する。
【０１５０】
【数１９】
0004046543.tif 000020
【０１５１】
式中、
【数２０】
0004046543.tif 000021
【０１５２】
ＲＧ法は、ビット誤り率の決定まで、ＢＥＣの場合のように進行する。ＡＷＧＮ通信路では、ＲＧ法を中止した後で、「目標」ノードまでずっと繰り込むことは、常態では不便である。なぜなら、グラフ中にほんの数個のノードしかなくても正確な計算を行うことは容易でないからである。
【０１５３】
目標ノードｉを除いたすべてのノードを繰り込んでしまうと、ｈｉの最終繰り込み値が残される。このガウス近似から、ゼロとして復号されているノードｉ用の確率分布が、平均ｈｉと分散２ｈｉを有するガウス分布であることがわかる。復号失敗は、この確率分布のうち、ゼロよりも小さい部分に一致する。したがって、ノードｉでのビット誤り率（ｂｅｒｉ）に対する本発明の予測は、次式である。
【０１５４】
【数２１】
0004046543.tif 000022
【０１５５】
（誤り訂正符号の生成）
もっとも良く知られている実施可能な誤り訂正符号を生成する指針として、密度変化法が用いられてきたことを考慮に入れると、本発明のＲＧ法を用いて、さらに良い符号を生成することができる。本発明によるＲＧ法を用いれば、任意の一般化パリティ検査行列により定義された符号を入力して、ノードごとのビット誤り率の予測を、出力として得ることができる。
【０１５６】
可能な改良符号の空間を誘導探索するために、目的関数に、この出力を利用できる。例えば、ＡＷＧＮ通信路用に、できる限り小さい信号対雑音比（ＳＮ比）にて、１０−４よりも小さいビット誤り率を達成するＮ＝１００のブロック長、伝送速度１／２の符号（隠れ状態はない）を見出そうとすることができる。これは、本発明のＲＧ法を利用して、また任意の公知の探索技法（例えば、グリーディ下降、模擬アニーリング法、発生論的処理法など）を利用して有効なパリティ検査行列の空間を探索して、正確なブロック長と伝送速度の符号を反復的に評価することで行う。
【０１５７】
本発明では、長所のある正確な測度、すなわち、無限ブロック長の限界におけるしきい値ではなく、ビット誤り率自体に、直接に的を絞っているために、本発明による探索は、従来技術の密度変化処理を用いて得られた結果に改良を加える。本発明では、ノードごとに、ビット誤り率に関する情報を持っているために、このような探索を導くことができる。例えば、付加的なパリティ検査ノードを追加することで、高いビット誤り率を有する弱い変数ノードを「強くする」ことがもっともなこともある。あるいは、これらの弱いノードを、隠れノードに変え、したがって、その伝送速度を高めることで、低いビット誤り率を有する強いノードを「弱める」こともある。
【０１５８】
その一方、あらゆるノードのビット誤り率を決定することで、探索が減速する。少なくとも長いブロック長では、これらのノードの局所近傍の点から定義された少数の異なるノード・クラスだけしかない符号に制限することは、それだけの価値がある場合もある。もっともよく知られている符号の大部分は、このタイプのものである。本発明では、変数ノードごとにビット誤り率を決定するのではなく、それぞれのクラスの変数ノードの代表的なただ１つのノードだけに、ビット誤り率を決定することができる。
【０１５９】
例えば、レギュラーＧａｌｌａｇｅｒ符号では、各ノードは、同一の局所近傍を有し、したがって、その近傍のすべてのノードを代表するものとして、どんなノードでも選択できる。この方法で為された誤りは、同一クラスの異なるノードのビット誤り率を比較することで評価される。実際の有限サイズのレギュラーＧａｌｌａｇｅｒ符号では、ＲＧ法が、これらのノードのそれぞれに対して非常に類似した予測を与えることがわかり、したがって、これらのノードのすべてを代表するものとして単一の変数ノードだけを考慮に入れることで為される誤りは、極めて小さい。
【０１６０】
本発明は、好ましい実施形態の例示として述べられてきたが、他の様々な改造や変更は、本発明の意図および範囲内で行うことができるものとする。それゆえ、併記の特許請求の範囲の目的は、本発明の真の意図および範囲に入るものとして、このような変形や変更をすべて含むものである。
【図面の簡単な説明】
【図１】  ループを含む誤り訂正符号を表わす従来技術の２部グラフである。
【図２】  単純な従来技術の誤り訂正符号を表わす従来技術の２部グラフである。
【図３ａ】  本発明により繰り込まれた２部グラフである。
【図３ｂ】  本発明により繰り込まれた２部グラフである。
【図３ｃ】  本発明により繰り込まれた２部グラフである。
【図３ｄ】  本発明により繰り込まれた２部グラフである。
【図３ｅ】  本発明により繰り込まれた２部グラフである。
【図４】  本発明により繰り込まれる２部グラフである。
【図５】  繰り込まれる、ループを有する２部グラフである。
【図６】  繰り込まれる２部グラフの拡張を示す図である。
【図７】  繰り込まれる一般化パリティ検査行列を表わす、ループを有する２部グラフである。
【図８】  誤り訂正符号を評価する方法を比較したグラフである。
【図９】  本発明による繰り込み群法の流れ図である。
【図１０】  ループ付きのグラフに対する、本発明による方法の流れ図である。
【図１】
0004046543.tif 000023
【図２】
0004046543.tif 000024
【図３ａ】
0004046543.tif 000025
【図３ｂ】
0004046543.tif 000026
【図３ｃ】
0004046543.tif 000027
【図３ｄ】
0004046543.tif 000028
【図３ｅ】
0004046543.tif 000029
【図４】
0004046543.tif 000030
【図５】
0004046543.tif 000031
【図６】
0004046543.tif 000032
【図７】
0004046543.tif 000033
【図８】
0004046543.tif 000034
【図９】
0004046543.tif 000035
【図１０】
0004046543.tif 000036