(57)【特許請求の範囲】
【請求項１】
デコーダによるｐｏｌａｒ符号の復号の範囲において信念伝播を実行する方法であって、前記ｐｏｌａｒ符号は、Ｎビットのサイズを有するとともに、Ｎ／２個の並行カーネルのＬ個の部分分極ステージの構造に基づいており、Ｎ及びＬは、Ｎ＝２Ｌとなるような正の整数であり、ｉは、前記Ｎ／２個の並行カーネルの中のカーネルＫｉ，ｊの前記部分分極ステージを識別するインデックスであり、ｊは、前記インデックスｉによって識別される前記部分分極ステージにおける前記Ｎ／２個の並行カーネルの中の前記カーネルＫｉ，ｊの位置を表すインデックスであり、各部分分極ステージにおける前記Ｎ／２個の並行カーネルは、シャッフラー（Φｉ）によって、各隣接部分分極ステージにおける近傍のＮ／２個の並行カーネルから分離されており、
前記デコーダは、
前記カーネルＫｉ，ｊごとの性能改善指標Ｍの値Ｍ（ｉ，ｊ）を計算することであって、前記性能改善指標Ｍは、検討対象のカーネルＫｉ，ｊの入力信念が一致していない振幅を表しており、及び／又は、前記性能改善指標Ｍは、前記検討対象のカーネルＫｉ，ｊの出力信念が前記検討対象のカーネルＫｉ，ｊの近傍カーネルへの瞬時情報レートをもたらす振幅を表している下で、前記性能改善指標Ｍの前記値Ｍ（ｉ，ｊ）を計算することと、
前記カーネルを、前記性能改善指標Ｍの前記値Ｍ（ｉ，ｊ）の降順にリスト内でソートすることと、
を実行することを特徴とし、
前記デコーダは、以下のように、すなわち、
正の整数であるＷにおいて、前記リスト内のＷ個の上位カーネルについて出力信念を更新することと、
更新された出力信念を、前記Ｗ個の上位カーネルの近傍カーネルの入力信念として伝播することと、
前記Ｗ個の上位カーネルの近傍カーネルごとの出力信念を、それらの入力信念の更新に後続して更新することと、
前記Ｗ個の上位カーネルの近傍カーネルごとの前記性能改善指標Ｍの前記値Ｍ（ｉ，ｊ）を再計算することと、
前記Ｗ個の上位カーネルについて前記性能改善指標Ｍをヌル値に設定することと、
前記性能改善指標Ｍの前記値Ｍ（ｉ，ｊ）の降順で、前記リスト内で前記カーネルを並べ替えることと、
を行うように信念伝播反復プロセスを実行することと、
前記デコーダは、停止条件が満たされるまで前記信念伝播反復プロセスを繰り返すこととを更に特徴とする、方法。
【請求項２】
カーネルＫｉ，ｊごとの前記性能改善指標Ｍの前記値Ｍ（ｉ，ｊ）は、前記カーネルＫｉ，ｊの入力信念に関連付けられた情報レートの総和と、前記カーネルＫｉ，ｊの直前の更新の前の前記カーネルＫｉ，ｊの各入力信念に関連付けられた前記情報レートの総和との間の差に依存する、請求項１に記載の方法。
【請求項３】
カーネルＫｉ，ｊごとの前記性能改善指標Ｍの前記値Ｍ（ｉ，ｊ）＝Ｍ（１）（ｉ，ｊ）は、以下のように規定され、
【数１】
0006887534.tif 000116
ここで、
【数２】
0006887534.tif 000117
であり、Ｌｉ，２ｊ−１：２ｊ（ｉｎ）は、前記部分分極ステージｉ−１から到来する入力信念であり、Ｌｉ，２ｊ−１：２ｊ（ｏｕｔ）は、前記部分分極ステージｉ＋１から到来する入力信念であり、ｍｉ，ｊ（１）は、前記カーネルＫｉ，ｊの各有効な更新後にｍｉ，ｊ（１）ｏｌｄになり、前記有効な更新中、前記性能改善指標Ｍの前記値Ｍ（ｉ，ｊ）＝Ｍ（１）（ｉ，ｊ）の後の更新において用いられるように、前記入力信念Ｌｉ，２ｊ−１：２ｊ（ｉｎ）及び前記入力信念Ｌｉ，２ｊ−１：２ｊ（ｏｕｔ）から前記出力信念
【数３】
0006887534.tif 000118
及び前記出力信念
【数４】
0006887534.tif 000119
が計算され、前記カーネルＫｉ，ｊについての前記性能改善指標Ｍの前記値Ｍ（１）（ｉ，ｊ）の最初の計算においてｍｉ，ｊ（１）ｏｌｄ＝０である、請求項２に記載の方法。
【請求項４】
カーネルＫｉ，ｊごとの前記性能改善指標Ｍの前記値Ｍ（ｉ，ｊ）は、前記カーネルＫｉ，ｊの入力事後信念に関連付けられた情報レートの総和と、前記カーネルＫｉ，ｊの直前の更新の前の前記カーネルＫｉ，ｊの入力事後信念に関連付けられた前記情報レートの総和との間の総和レート差に依存し、事後信念は、事前信念及び外部信念の総和である、請求項１に記載の方法。
【請求項５】
カーネルＫｉ，ｊごとの前記性能改善指標Ｍの前記値Ｍ（ｉ，ｊ）＝Ｍ（２）（ｉ，ｊ）は、以下のように規定され、
【数５】
0006887534.tif 000120
ここで、
【数６】
0006887534.tif 000121
であり、Ｌｉ，２ｊ−１：２ｊ（ｉｎ）は、前記部分分極ステージｉ−１から到来する入力信念であり、Ｌｉ，２ｊ−１：２ｊ（ｏｕｔ）は、前記部分分極ステージｉ＋１から到来する入力信念であり、
【数７】
0006887534.tif 000122
は、前記部分分極ステージｉ−１に向かう出力信念である
【数８】
0006887534.tif 000123
の直前のそれぞれの値を表しており、
【数９】
0006887534.tif 000124
は、前記部分分極ステージｉ＋１に向かう出力信念である
【数１０】
0006887534.tif 000125
の直前のそれぞれの値を表している、請求項４に記載の方法。
【請求項６】
カーネルＫｉ，ｊごとの前記性能改善指標Ｍの前記値Ｍ（ｉ，ｊ）は、前記カーネルＫｉ，ｊの最後の更新中の前記カーネルＫｉ，ｊによって出力される情報の増加に依存する、請求項１に記載の方法。
【請求項７】
カーネルＫｉ，ｊごとの前記性能改善指標Ｍの前記値Ｍ（ｉ，ｊ）＝Ｍ（３）（ｉ，ｊ）は、以下のように規定され、
【数１１】
0006887534.tif 000126
ここで、
【数１２】
0006887534.tif 000127
は、前記部分分極ステージｉ−１に向かう出力信念であり、
【数１３】
0006887534.tif 000128
は、前記部分分極ステージｉ＋１に向かう出力信念である、請求項６に記載の方法。
【請求項８】
カーネルＫｉ，ｊごとの前記性能改善指標Ｍの前記値Ｍ（ｉ，ｊ）は、前記カーネルＫｉ，ｊの最後の更新中の前記カーネルＫｉ，ｊによって出力される情報の増加に更に依存する、請求項２に記載の方法。
【請求項９】
カーネルＫｉ，ｊごとの前記性能改善指標Ｍの前記値Ｍ（ｉ，ｊ）＝Ｍ（１）（ｉ，ｊ）＋Ｍ（３）（ｉ，ｊ）は、以下のように規定され、
【数１４】
0006887534.tif 000129
ここで、
【数１５】
0006887534.tif 000130
及び、
【数１６】
0006887534.tif 000131
であり、Ｌｉ，２ｊ−１：２ｊ（ｉｎ）は、前記部分分極ステージｉ−１から到来する入力信念であり、Ｌｉ，２ｊ−１：２ｊ（ｏｕｔ）は、前記部分分極ステージｉ＋１から到来する入力信念であり、
【数１７】
0006887534.tif 000132
は、前記部分分極ステージｉ−１に向かう出力信念であり、
【数１８】
0006887534.tif 000133
は、前記部分分極ステージｉ＋１に向かう出力信念であり、ｍｉ，ｊ（１）は、前記カーネルＫｉ，ｊの各有効な更新後にｍｉ，ｊ（１）ｏｌｄになり、前記有効な更新中、前記性能改善指標Ｍの前記値Ｍ（ｉ，ｊ）＝Ｍ（１）（ｉ，ｊ）の後の更新において用いられるように、前記入力信念Ｌｉ，２ｊ−１：２ｊ（ｉｎ）及び前記入力信念Ｌｉ，２ｊ−１：２ｊ（ｏｕｔ）から前記出力信念
【数１９】
0006887534.tif 000134
及び前記出力信念
【数２０】
0006887534.tif 000135
が計算され、前記カーネルＫｉ，ｊについての前記性能改善指標Ｍの前記値Ｍ（１）（ｉ，ｊ）の最初の計算においてｍｉ，ｊ（１）ｏｌｄ＝０である、請求項８に記載の方法。
【請求項１０】
カーネルＫｉ，ｊごとの前記性能改善指標Ｍの前記値Ｍ（ｉ，ｊ）＝Ｍ（１）（ｉ，ｊ）．Ｍ（３）（ｉ，ｊ）は、以下のように規定され、
【数２１】
0006887534.tif 000136
ここで、
【数２２】
0006887534.tif 000137
及び、
【数２３】
0006887534.tif 000138
であり、Ｌｉ，２ｊ−１：２ｊ（ｉｎ）は、前記部分分極ステージｉ−１から到来する入力信念であり、Ｌｉ，２ｊ−１：２ｊ（ｏｕｔ）は、前記部分分極ステージｉ＋１から到来する入力信念であり、
【数２４】
0006887534.tif 000139
は、前記部分分極ステージｉ−１に向かう出力信念であり、
【数２５】
0006887534.tif 000140
は、前記部分分極ステージｉ＋１に向かう出力信念であり、ｍｉ，ｊ（１）は、前記カーネルＫｉ，ｊの各有効な更新後にｍｉ，ｊ（１）ｏｌｄになり、前記有効な更新中、前記性能改善指標Ｍの前記値Ｍ（ｉ，ｊ）＝Ｍ（１）（ｉ，ｊ）の後の更新において用いられるように、前記入力信念Ｌｉ，２ｊ−１：２ｊ（ｉｎ）及び前記入力信念Ｌｉ，２ｊ−１：２ｊ（ｏｕｔ）から前記出力信念
【数２６】
0006887534.tif 000141
及び前記出力信念
【数２７】
0006887534.tif 000142
が計算され、前記カーネルＫｉ，ｊについての前記性能改善指標Ｍの前記値Ｍ（１）（ｉ，ｊ）の最初の計算においてｍｉ，ｊ（１）ｏｌｄ＝０である、請求項８に記載の方法。
【請求項１１】
以下の条件、すなわち、
前記信念伝播反復プロセスが開始された後、所定の持続時間の期間が終わったとき、
前記信念伝播反復プロセスにおいて、所定の回数の反復が実行されたとき、
前記リスト内の最上位にある前記カーネルの前記性能改善指標Ｍの前記値Ｍ（ｉ，ｊ）が所定の閾値未満であるとき、
のうちの１つが充足されると、前記停止条件は満たされる、請求項１〜１０のいずれか１項に記載の方法。
【請求項１２】
プログラムコード命令がプログラマブルデバイスによって実行されると、請求項１〜１１のいずれか１項に記載の方法を実施する、前記プログラマブルデバイスにロードすることができる前記プログラムコード命令を含むコンピュータプログラム製品。
【請求項１３】
プログラムコード命令がプログラマブルデバイスによって実行されると、請求項１〜１１のいずれか１項に記載の方法を実施する、前記プログラマブルデバイスにロードすることができる前記プログラムコード命令を含むコンピュータプログラムを記憶する非一時的情報記憶媒体。
【請求項１４】
ｐｏｌａｒ符号の復号の範囲において信念伝播を実行するように構成されたｐｏｌａｒ符号デコーダであって、前記ｐｏｌａｒ符号は、Ｎビットのサイズを有するとともに、Ｎ／２個の並行カーネルのＬ個の部分分極ステージの構造に基づいており、Ｎ及びＬは、Ｎ＝２Ｌとなるような正の整数であり、ｉは、前記Ｎ／２個の並行カーネルの中のカーネルＫｉ，ｊの前記部分分極ステージを識別するインデックスであり、ｊは、前記インデックスｉによって識別される前記部分分極ステージにおける前記Ｎ／２個の並行カーネルの中の前記カーネルＫｉ，ｊの位置を表すインデックスであり、各部分分極ステージにおける前記Ｎ／２個の並行カーネルは、シャッフラー（Φｉ）によって、各隣接部分分極ステージにおける近傍のＮ／２個の並行カーネルから分離されており、
前記ｐｏｌａｒ符号デコーダは、
前記構造のカーネルＫｉ，ｊごとの性能改善指標Ｍの値Ｍ（ｉ，ｊ）を計算する手段であって、前記性能改善指標Ｍは、検討対象のカーネルＫｉ，ｊの入力信念が一致していない振幅を表しており、及び／又は、前記性能改善指標Ｍは、前記検討対象のカーネルＫｉ，ｊの出力信念が前記検討対象のカーネルＫｉ，ｊの近傍カーネルへの瞬時情報レートをもたらす振幅を表している、手段と、
前記カーネルを、前記性能改善指標Ｍの前記値Ｍ（ｉ，ｊ）の降順にリスト内でソートする手段と、
を備えることを特徴とし、
前記ｐｏｌａｒ符号デコーダは、
正の整数であるＷにおいて、前記リスト内のＷ個の上位カーネルについて出力信念を更新することと、更新された出力信念を、前記Ｗ個の上位カーネルの近傍カーネルの入力信念として伝播することとを行う手段と、
前記Ｗ個の上位カーネルの近傍カーネルごとの出力信念を、それらの入力信念の更新に後続して更新することと、前記Ｗ個の上位カーネルの近傍カーネルごとの前記性能改善指標Ｍの前記値Ｍ（ｉ，ｊ）を再計算することとを行う手段と、
前記Ｗ個の上位カーネルについて前記性能改善指標Ｍをヌル値に設定する手段と、
前記性能改善指標Ｍの前記値Ｍ（ｉ，ｊ）の降順で、前記リスト内で前記カーネルを並べ替える手段と、
を含む信念伝播反復プロセスを実行する手段を備えることと、
前記ｐｏｌａｒ符号デコーダは、停止条件が満たされるまで前記信念伝播反復プロセスを繰り返すように更に構成されることとを更に特徴とする、ｐｏｌａｒ符号デコーダ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、信念伝播中にｐｏｌａｒ符号構造のカーネルが処理される順序を規定することに関し、したがって、そのように規定された順序でカーネルを処理することによって信念伝播を実行することに関する。
【背景技術】
【０００２】
ｐｏｌａｒ符号は、代数的構成に依拠するのではなく、情報理論的な考慮から構築された線形ブロック誤り訂正符号である。ｐｏｌａｒ符号は、カーネルの多分岐の再帰から構築された構造に基づいており、これにより、物理的チャネルが仮想アウターチャネルに変換される。再帰の数量が多くなると、仮想チャネルは、高信頼度又は低信頼度のうちのいずれかを有する傾向がある。換言すれば、仮想チャネルは、分極化する（polarize）。その場合、情報ビットとも称される有用なデータビットは、最も信頼度の高い仮想チャネルに割り当てられ、凍結ビット（frozen bits）は、残りの仮想チャネルに割り当てられる。
【０００３】
ｐｏｌａｒ符号の符号化及び復号複雑度は、Ｎ．ｌｏｇ（Ｎ）のオーダーにあり、ここで、Ｎは、検討対象のｐｏｌａｒ符号のサイズである。しかしながら、ｐｏｌａｒ符号の性能は、Ｎが小さい場合、例えばＮ＝５１２の場合、ターボ符号又はＬＤＰＣ（低密度パリティチェック）符号等の他のコーディング技術と比較すると、かなり不良である。その上、ｐｏｌａｒ符号が用いられることを意図される所与のＢＤＭＣ（バイナリ離散入力無記憶チャネル）について当該ｐｏｌａｒ符号が最適化される。
【０００４】
以下において、図１に概略的に表されるように、エンコーダ１１０及びデコーダ１２０からなるシステムを検討する。エンコーダ１１０は、サイズＮ＝２Ｌのｐｏｌａｒ符号に従って符号語を生成し、ここで、Ｌは、ｐｏｌａｒ符号の構造の大域的深度である。換言すれば、Ｎ及びＬは、正の整数であり、Ｎは、より詳細には、「２」のべき乗である。生成された符号語は、ＢＤＭＣ１３０を介してデコーダ１２０への転送の対象となる。そのような転送は、有線送信とすることもできるし、無線送信とすることもできるし、エンコーダ１１０が非一時的情報記憶媒体上にデータを記憶するとともに、デコーダ１２０がその非一時的情報記憶媒体からデータを索出する場合の非一時的情報記憶媒体上の中間記憶とすることもできる。
【０００５】
ベクトルｘの第ｊ’のエントリをｘｊ’とし、ベクトルｘから抽出されるエントリｘｊ’、ｘｊ’＋１、．．．、ｘｋからなるサイズ（ｋ−ｊ’＋１）のベクトルをｘｊ’：ｋとする。さらに、ベクトルｘから抽出されるエントリ
【数１】
0006887534.tif 000002
からなるベクトルをｘｊ’：ｍ：ｋとし、ここで、
【数２】
0006887534.tif 000003
は、ｕの床関数を表す。
【０００６】
このようにして、本明細書において、レートＲ＜１のｐｏｌａｒ符号ベースエンコーダが検討され、このｐｏｌａｒ符号ベースエンコーダは、情報ビットと凍結ビットとからなるサイズＮのベクトルｂを、サイズＮの符号語ｘに変換する。ベクトルｂのＮ個のエントリのうちにＮ．Ｒ個の情報ビットが存在することに留意しなければならない。その場合、ベクトルｂのＮ個のエントリのうちにＮ．（１−Ｒ）個の凍結ビットが存在し、ベクトルｂ内の当該凍結ビットの位置及び値は、設計により既知であることに更に留意しなければならない。大半の場合、ビットは、値「０」に設定され、これらのビットのベクトルｂ内の位置は、ベクトルｂ内の第ｉの位置におけるビットが凍結ビットを保持する場合Ｆ（ｊ’）＝１であるとともに、ベクトルｂ内の第ｉの位置におけるビットが情報ビットを保持する場合Ｆ（ｊ’）＝０であるようなベクトルＦによって表される。
【０００７】
したがって、図２Ａに示すように、ｐｏｌａｒ符号を適用するために、Ｎ．Ｒ個の情報ビットからなるベクトルｂ’が、マルチプレクサＭＵＸ２１０によって、ベクトルＦによって規定される凍結ビット位置に従ってＮ．（１−Ｒ）個の数量の凍結ビットを挿入することによって、長さＮのベクトルｂに変換される。その後、ベクトルｂは、ベクトルｂを長さＮの符号語ｘに符号化するように、サイズＮの分極器（分極ブロックとも称される）ＰＯＬ−Ｎ２２０によって処理され、これにより、Ｒに等しいコーディングレートがもたらされる。分極器ＰＯＬ−Ｎ２２０は、エンコーダ１１０の符号化部分を表している。ｐｏｌａｒ符号の構造に従って凍結ビットのそれぞれの位置を適切に選択することは、良好な復号性能を達成するのに重要である。
【０００８】
ｐｏｌａｒ符号の主要な側面は、ベクトルｂから符号語ｘへの変換は、検討対象のＢＤＭＣの実効符号レートＲ及び実効特性がどのようなものであれ静的であるということにあり、これは、ｐｏｌａｒ符号の構造は、一定を保つことを意味する。したがって、レート適合化及び性能最適化は、ベクトルｂ内の凍結ビットの位置を適切に選ぶことによって実行される。
【０００９】
図２Ｂに概略的に表されるモジュール式アーキテクチャに示すように、サイズＮの分極器ＰＯＬ−Ｎ２２０は、サイズＮのＬ−１個のシャッフラーΦ１、．．．、ΦＬ−１（したがって、第Ｌ番目は、そのようなシャッフラーを含まないことに留意されたい）によって分離されるＮ／２個の並行カーネルのＬ個のグループにおいて配置されるＬ．Ｎ／２個のバイナリカーネルから構築される（図３に示すものとして、サイズ「２」の分極器）。各シャッフラーは、１対１マッピングを用いて、異なる順序で入力ベクトルのエントリを分配する。定義により、バイナリカーネルＫｉ，ｊは、ｐｏｌａｒ符号の構造の第ｉの深度位置（部分分極ステージ）における第ｊの列位置に位置するカーネルである。同様に、シャッフラーΦｉは、ｐｏｌａｒ符号の構造の第ｉの深度位置（部分分極ステージ）に配置される。
【００１０】
並行カーネルＫｉ，１、．．．、Ｋｉ，Ｎ／２の入力は、ベクトル
【数３】
0006887534.tif 000004
である。並行カーネルＫｉ，１、．．．、Ｋｉ，Ｎ／２の出力は、ベクトル
【数４】
0006887534.tif 000005
である。深度位置ｉ＋１における並行カーネルＫｉ＋１，１、．．．、Ｋｉ＋１，Ｎ／２の入力と、深度位置ｉにおける並行カーネルＫｉ，１、．．．、Ｋｉ，Ｎ／２の出力との関係は、以下のとおりである。
【数５】
0006887534.tif 000006
及び
【数６】
0006887534.tif 000007
ここで、φｉは、第ｉの深度位置におけるシャッフラーΦｉによって実行されるシャッフリング演算であり、φｉ−１は、第ｉの深度位置におけるこのシャッフラーΦｉに関連した逆シャッフリング演算である。例えば、シャッフリング演算φｉは、以下のように定義される。
【数７】
0006887534.tif 000008
【００１１】
代替的に、シャッフリング演算φｉは、以下のように定義される。
【数８】
0006887534.tif 000009
【００１２】
シャッフラー入力同士の間の他の代替的な組み合わせをシャッフリング演算によって実行することができ、例えば、第ｉの深度位置におけるシャッフラーΦｉによって実行されるシャッフリング演算は、第（ｉ―１）の深度位置におけるシャッフラーΦｉ−１によって実行されるシャッフリング演算、及び／又は、第（ｉ＋１）の深度位置におけるシャッフラーΦｉ＋１によって実行されるシャッフリング演算と異なるものとすることができる。
【００１３】
したがって、ベクトルｂは、ｘ１，ｊ（ｉｎ）（∀０＜ｊ’≦Ｎ）の連結としてそのように入力され、符号語ｘは、ｘＬ，ｊ（ｏｕｔ）（∀０＜ｊ’≦Ｎ）の連結としてそのように出力されることに留意することができる。
【００１４】
注釈として、ｐｏｌａｒ符号の構造において（１つのシャッフラーを介して）相互接続されるカーネルは、互いに対する近傍として指定される。したがって、各バイナリカーネルは、２つの入力及び２つの出力を有するので、最大で４つの近傍を有する。一般に、或るバイナリカーネルの全ての入力及び出力は、異なる近傍に接続され、それにより、１＜ｉ＜ＬについてカーネルＫｉ，１：Ｎ当たり厳密に４つの近傍がもたらされることが考慮される。
【００１５】
図３は、バイナリカーネルとも呼ばれる、サイズ「２」の分極器３００を概略的に表している。カーネルＫｉ，ｊを検討する場合、２つのビットｘｉ，２ｊ−１（ｉｎ）及びｘｉ，２ｊ（ｉｎ）が、サイズ「２」の分極器３００に入力される。２つのビットｘｉ，２ｊ−１（ｏｕｔ）及びｘｉ，２ｊ（ｏｕｔ）が、サイズ「２」の分極器３００から出力される。サイズ「２」の分極器３００は、ｘｉ，２ｊ−１（ｏｕｔ）及びｘｉ，２ｊ（ｏｕｔ）が、以下のように規定されるように分極演算を実行する。
【数９】
0006887534.tif 000010
ここで、
【数１０】
0006887534.tif 000011
は、ＸＯＲ関数を表している。
【００１６】
結果的に、出力された符号語ｘの各エントリｘｊ’（∀０＜ｊ’≦Ｎ）は、遷移確率Ｐ（ｙｊ’｜ｘｊ’）によって規定されたＢＤＭＣ上に送信される。例えば、ＢＰＳＫ（バイナリ位相シフトキーイング）入力を有するＡＷＧＮ（加法的白色ガウス雑音）チャネルを検討する場合、遷移確率Ｐ（ｙｊ’｜ｘｊ’）は、
【数１１】
0006887534.tif 000012
によって規定され、ここで、ρｊ’は、上記ＡＷＧＮチャネルの信号対雑音比である。
【００１７】
さらに、対数尤度比（ＬＬＲ）Ｌｊ’（ｘ）は、ｙｊ’を観測する場合にｘｊ’＝１又はｘｊ’＝０である確率を特徴付ける、
【数１２】
0006887534.tif 000013
として規定することができる。Ｌｊ’（ｘ）の正の値は、ｘｊ’＝０を得る確率の方が高いことに関連付けられている。同等に、ベクトルｂに関連付けられた事前対数尤度比（ＬＬＲ）Ｌｊ’（ｂ）は、
【数１３】
0006887534.tif 000014
として規定することができ、この式は、ベクトルビットｂｊ’が凍結ビットである場合、関連付けられたビットがヌルであることが確実に知られているので、ＬＬＲは、無限（又は十分に高い）値に初期化される一方、ベクトルｂ’から到来する情報ビットの場合、既知である事前情報がないので（すなわち、情報ビットが「１」に等しいのか又は「０」に等しいのかは未知であるので）、ＬＬＲの０初期化がもたらされることに関係する。
【００１８】
図４Ａに概略的に表されるモジュール式アーキテクチャに示すように、デコーダ１２０によって得られた観測値ｙからベクトルｂの推定値
【数１４】
0006887534.tif 000015
を索出することが可能であるように、当該デコーダ１２０は、ＬＬＲ計算モジュール４２１、信念伝播デコーダ４２２及び判断器４２３を含み、これらはともに、デコーダ１２０の復号部分４２０を形成する。デコーダ１２０は、エンコーダ１１０によって用いられる凍結ビットの位置の知識から、ベクトルｂの推定値
【数１５】
0006887534.tif 000016
をベクトルｂ’の推定値
【数１６】
0006887534.tif 000017
に変換するデマルチプレクサ４１０を更に含む。ＬＬＲ計算モジュール４２１は、ＬＬＲ形式における観測値、すなわちベクトルＬ（ｘ）を出力し、この出力値は、その後、ｐｏｌａｒ符号の入力における事前確率のベクトルであり、凍結ビットの値及び位置の事前知識により初期化される、同様にＬＬＲ形式におけるＬ（ｂ）とともに信念伝播デコーダ４２２によって用いられて、同様にＬＬＲ形式における推定値
【数１７】
0006887534.tif 000018
を出力する。このように、推定値
【数１８】
0006887534.tif 000019
は、デコーダ１２０の入力Ｌ（ｂ）及びＬ（ｘ）の観点におけるベクトルｂのビットの微調整された推定値であり、これらの推定値は、その後、判断器４２３によって用いられて、ベクトルｂの推定値
【数１９】
0006887534.tif 000020
を求める。信念伝播デコーダ４２２は、ＭＩＭＯ（多入力多出力）送信の文脈におけるチャネル推定の微調整及び／又はＱＡＭ（直交振幅変調）シンボル復調の微調整等のために、デコーダ１２０の他の確率論的検出ブロックを用いて反復するために、デコーダの入力Ｌ（ｂ）及びＬ（ｘ）の観点における観測値Ｌ（ｘ）の微調整された推定値である推定値
【数２０】
0006887534.tif 000021
を更に出力することができる。
【００１９】
デコーダ１２０の挙動は、図４Ｂにおけるアルゴリズムによって概略的に示されている。
【００２０】
ステップＳ４５１において、デコーダ１２０は、まずベクトルＬ（ｂ）をヌルベクトルとして初期化し、その後、デコーダ１２０は、このベクトルＬ（ｂ）を、以下のように、エンコーダ１１０によって用いられる凍結ビットの位置の知識に従って変更する。
【数２１】
0006887534.tif 000022
ここで、＋∞は、第ｊ’のビットのＬＬＲ  Ｌｊ’（ｂ）は、確率「１」を有するこのビットについての値として「０」を与える。凍結ビットが「０」の代わりに「１」の値を用いて初期化されると、ＬＬＲの値は、「−∞」となるべきであることに留意しなければならない。「＋∞」は、任意の分極器の入力において存在することができるＬＬＲ値の範囲外であるように十分に高い値によって数値的に表される。これは、ベクトルｂ内の凍結ビットの位置に対応する任意のインデックス値について、当該インデックス値におけるベクトルＬ（ｂ）の値は、無限又はこのベクトルを代表するデフォルト値に設定され、それ以外は「０」に設定されることを意味する。
【００２１】
後続するステップＳ４５２において、デコーダ１２０は、内部変数Ｌｉ，１：Ｎ（ｉｎ）及びＬｉ，１：Ｎ（ｏｕｔ）（∀０＜ｉ≦Ｌ）を、ヌル値に初期化する。これらの内部変数Ｌｉ，１：Ｎ（ｉｎ）及びＬｉ，１：Ｎ（ｏｕｔ）は、信念伝播の再帰に沿って伝播するように意図されている。
【００２２】
後続するステップＳ４５３において、デコーダ１２０は、ｐｏｌａｒ符号の既知の構造と、ＬＬＲ形式における観測値Ｌｊ’（ｘ）と、ＬＬＲ形式における凍結ビット情報Ｌｊ’（ｂ）とに従って、内部変数Ｌｉ，１：Ｎ（ｉｎ）及びＬｉ，１：Ｎ（ｏｕｔ）を用いて信念伝播を計算する。換言すれば、デコーダ１２０は、ベクトルＬ（ｂ）をＬ１，１：Ｎ（ｉｎ）として、及びベクトルＬ（ｘ）をＬＬ，１：Ｎ（ｏｕｔ）として内部に入力することによって、図４Ｄに概略的に示すアルゴリズムを用いる。信念伝播の出力は、ベクトル
【数２２】
0006887534.tif 000023
及び
【数２３】
0006887534.tif 000024
であり、ここで、ベクトル
【数２４】
0006887534.tif 000025
は、その後、ベクトルｂの推定値
【数２５】
0006887534.tif 000026
を求めるのに判断器４２３によって用いられる。
【００２３】
後続するステップＳ４５４において、デコーダ１２０は、信念伝播デコーダ４２２によって出力された推定値
【数２６】
0006887534.tif 000027
に従ってベクトルｂの推定値
【数２７】
0006887534.tif 000028
の各ビットについて判断を行う。この判断は、以下のように行われる。
【数２８】
0006887534.tif 000029
【００２４】
通常、
【数２９】
0006887534.tif 000030
（∀０＜ｊ’≦Ｎ）は、「０」に等しいべきではない。しかしながら、そのような状況が生じた場合、デコーダ１２０は、対応するビット
【数３０】
0006887534.tif 000031
を、「０」又は「１」のいずれかに任意に設定する。
【００２５】
したがって、デコーダ１２０は、ベクトルｂ内の凍結ビットの位置を知得しているので、デコーダは、そこから情報ビットを抽出してベクトルｂ’の推定値
【数３１】
0006887534.tif 000032
を形成することが可能であり、これにより、ｐｏｌａｒ符号手法を用いた、エンコーダ１１０からデコーダ１２０への当該情報ビットの転送が終了する。
【００２６】
ステップＳ４５３において明らかであるように、信念伝播デコーダ４２２の挙動は、図４Ｃに概略的に示すファクターグラフを適用することによって、図４Ｄにおけるアルゴリズムによって概略的に示されている。図４Ｃを検討するとき、図３の表記と混同しないようにすべきである。実際、ベクトルｂから符号語ｘへのｐｏｌａｒ符号変換を実行するためにｐｏｌａｒ符号の構造において用いられる各カーネルは、入力ｘｉ，２ｊ−１（ｉｎ）及びＸｉ，２ｊ（ｉｎ）、並びに、出力ｘｉ，２ｊ−１（ｏｕｔ）及びｘｉ，２ｊ（ｏｕｔ）を有する。情報の伝播は、１方向において生じる（図３に表されるカーネルを検討する場合には左から右）しかしながら、信念伝播を検討する場合、各カーネルは、４つの入力Ｌｉ，２ｊ−１：２ｊ（ｉｎ）及びＬｉ，２ｊ−１：２ｊ（ｏｕｔ）、並びに、４つの出力
【数３２】
0006887534.tif 000033
及び
【数３３】
0006887534.tif 000034
を有する。
【００２７】
信念伝播は、分極器ＰＯＬ−Ｎ２２０の各カーネル内で、左から右に、及び右からの左に確率（信念）を伝播する。図４Ｃに概略的に表されているカーネルＫｉ，ｊを参照して、カーネルの左側からの入力信念（ＬＬＲの形式における）Ｌ１，２ｊ−１：２ｊ（ｉｎ）及びカーネルの右側からの入力信念Ｌ１，２ｊ−１：２ｊ（ｏｕｔ）、並びに、カーネルの左側からの出力信念（ＬＬＲの形式における）
【数３４】
0006887534.tif 000035
及びカーネルの右側からの出力信念
【数３５】
0006887534.tif 000036
を検討する。それゆえ、入力信念を出力信念にリンクする更新関数Ｂ１（ｉｎ）、Ｂ２（ｉｎ）、Ｂ１（ｏｕｔ）及びＢ２（ｏｕｔ）が、以下のように規定される。
【数３６】
0006887534.tif 000037
【００２８】
ステップＳ４７１において、信念伝播デコーダ４２２は、以下の演算を実行することによって、全ての値
【数３７】
0006887534.tif 000038
及び
【数３８】
0006887534.tif 000039
（∀０＜ｉ≦Ｌ，∀０＜ｊ≦Ｎ／２）を計算する（又は、他の観点から、信念伝播デコーダ４２２は、全ての値
【数３９】
0006887534.tif 000040
及び
【数４０】
0006887534.tif 000041
（∀０＜ｉ≦Ｌ，∀０＜ｊ’≦Ｎ）を計算する）。
【数４１】
0006887534.tif 000042
【００２９】
後続するステップＳ４７２において、信念伝播デコーダ４２２は、データＬｉ−１，１：Ｎ（ｏｕｔ）を更新することを可能にするように、データ
【数４２】
0006887534.tif 000043
に対してシャッフリング逆演算φｉ−１−１（∀１＜ｉ≦Ｌ）を適用する。データＬｉ−１，１：Ｎ（ｏｕｔ）は、ここで、事前計算され、ステップＳ４７４において後に効果的に更新されることに留意することができる。
【００３０】
後続するステップＳ４７３において、信念伝播デコーダ４２２は、データＬｉ＋１，１：Ｎ（ｉｎ）を更新することを可能にするように、データ
【数４３】
0006887534.tif 000044
に対してシャッフリング演算φｉ（∀１＜ｉ＜Ｌ）を適用する。データＬｉ＋１，１：Ｎ（ｉｎ）は、ここで、事前計算され、ステップＳ４７４において後に効果的に更新されることに留意することができる。
【００３１】
ステップＳ４７２及びＳ４７３は、逆順に行うこともできるし、並行して実行することもできることに更に留意することができる。
【００３２】
ステップＳ４７２及びＳ４７３において信念伝播が実行されたことに続いて、後続するステップＳ４７４において、信念伝播デコーダ４２２は、信念
【数４４】
0006887534.tif 000045
及び
【数４５】
0006887534.tif 000046
を更新して返す。
【００３３】
ｐｏｌａｒ符号手法の主な強みは、その漸近的最適性にある。漸近状態の結果、情報ビットを転送するための完全チャネル（「１」に等しい相互情報量、すなわち「０」に等しい誤りレート）、及び凍結ビットを転送するためのヌルチャネル（「０」に等しい相互情報量、すなわち「１」に等しい誤りレート）が得られる。上記の導入部の説明から、有限長において、チャネル分極は完全等価チャネル及びヌル等価チャネルに完全には収束せず、それにより、情報ビットについて非ヌルの誤りレート及び非ユニタリの相互情報量を有する不完全の等価グローバルチャネルがもたらされることを見て取ることができる。さらに、したがって、凍結ビットは、非ヌルの相互情報量を有するチャネル上で転送され、これには、容量が分極器ＰＯＬ−Ｎ２２０によって保存されるので、情報レートにおける損失が伴う。
【００３４】
その上、ｐｏｌａｒ符号手法は、デコーダ１２０において信念伝播のために膨大な計算動作を必要とする。ＣＰＵ（中央処理装置）又はＧＰＵ（グラフィック処理装置）ベースのアーキテクチャは、これらの膨大な計算動作を実行するのに良好に適応されているが、利用可能な処理リソース数の観点から、これらの動作を制約された時間枠（又は制約された処理ステップ数）内で実行する際、困難に直面する可能性がある。そのような状況下では、制約された時間枠の終了に達すると（又は制約された処理ステップ数に達すると）（これは、一般に、停止条件を満たすと称される）信念伝播を停止し、そのままの状態で復号判断を行うことが通常である。
【００３５】
したがって、復号判断を行うことに至る停止条件が満たされるときのデコーダにおける信念伝播の性能を改善する解決策を提供することが望まれている。ｐｏｌａｒ符号の低複雑度の利益を保つことを可能にする解決策を提供することが更に望ましい。単純かつ費用効果的な解決策を提供することが更に望ましい。
【発明の概要】
【００３６】
そのために、本発明は、デコーダによるｐｏｌａｒ符号の復号の範囲において信念伝播を実行する方法であって、ｐｏｌａｒ符号は、Ｎビットのサイズを有するとともに、Ｎ／２個の並行カーネルＫｉ，ｊのＬ個の部分分極ステージの構造に基づいており、Ｎ及びＬは、Ｎ＝２Ｌとなるような正の整数であり、ｉは、カーネルＫｉ，ｊの部分分極ステージを識別するインデックスであり、ｊは、インデックスｉによって識別される部分分極ステージにおけるＮ／２個の並行カーネルの中の上記カーネルＫｉ，ｊの位置を表すインデックスであり、各部分分極ステージにおけるＮ／２個の並行カーネルは、シャッフラーによって、各隣接部分分極ステージにおける近傍のＮ／２個の並行カーネルから分離される、方法に関する。この方法は、デコーダが、構造のカーネルＫｉ，ｊごとの性能改善指標Ｍの値Ｍ（ｉ，ｊ）を計算することであって、性能改善指標Ｍは、検討対象のカーネルＫｉ，ｊの入力信念が一致していない振幅を表しており、及び／又は、性能改善指標Ｍは、検討対象のカーネルＫｉ，ｊの出力信念がこの検討対象のカーネルＫｉ，ｊの近傍カーネルへの瞬時情報レートをもたらす振幅を表している、計算することと、カーネルを、性能改善指標Ｍの値Ｍ（ｉ，ｊ）の降順にリストＬ内でソートすることとを実行するようになっている。この方法は、さらに、デコーダが、以下のように、すなわち、正の整数であるＷにおいて、リストＬのＷ個の上位カーネルについて出力信念を更新することと、上記出力信念を、上記Ｗ個の上位カーネルの近傍カーネルの入力信念として伝播することと、上記Ｗ個の上位カーネルの近傍カーネルごとの出力信念を、それらの入力信念の更新に後続して更新することと、上記近傍カーネルごとの性能改善指標値Ｍ（ｉ，ｊ）を再計算することと、上記Ｗ個の上位カーネルについて性能改善指標Ｍをヌル値に設定することと、性能改善指標Ｍの値Ｍ（ｉ，ｊ）の降順で、リストＬ内でカーネルを並べ替えることとを行うように信念伝播反復プロセスを実行するようになっている。さらに、この方法は、デコーダが、停止条件が満たされるまで信念伝播反復プロセスを繰り返すようになっている。
【００３７】
それゆえ、上記で規定された性能改善指標Ｍに起因して、復号プロセスに最も関連した情報をもたらすカーネルを識別することによって、復号プロセスにおける信念伝播の性能は、停止条件が満たされると改善される。
【００３８】
特定の一実施形態によれば、カーネルＫｉ，ｊごとの性能改善指標Ｍの値Ｍ（ｉ，ｊ）は、当該カーネルＫｉ，ｊの入力信念に関連付けられた情報レートの総和と、当該カーネルＫｉ，ｊの直前の更新の前の当該カーネルＫｉ，ｊの各入力信念に関連付けられた情報レートの総和との間の差に依存する。
【００３９】
それゆえ、第１の手法として、各検討対象のカーネルＫｉ，ｊの入力信念が一致していない振幅が用いられて、カーネルがソートされ、それゆえ、復号プロセス性能が改善される。
【００４０】
特定の一実施形態によれば、カーネルＫｉ，ｊごとの性能改善指標Ｍの値Ｍ（ｉ，ｊ）＝Ｍ（１）（ｉ，ｊ）は、以下のように規定され、
【数４６】
0006887534.tif 000047
ここで、
【数４７】
0006887534.tif 000048
であり、Ｌｉ，２ｊ−１：２ｊ（ｉｎ）は、部分分極ステージｉ−１から到来する入力信念であり、Ｌｉ，２ｊ−１：２ｊ（ｏｕｔ）は、部分分極ステージｉ＋１から到来する入力信念であり、ｍｉ，ｊ（１）は、カーネルＫｉ，ｊの各有効な更新後にｍｉ，ｊ（１）ｏｌｄになり、有効な更新中、性能改善指標値Ｍ（ｉ，ｊ）＝Ｍ（１）（ｉ，ｊ）の後の更新において用いられるように、入力信念Ｌｉ，２ｊ−１：２ｊ（ｉｎ）及びＬｉ，２ｊ−１：２ｊ（ｏｕｔ）から出力信念
【数４８】
0006887534.tif 000049
及び
【数４９】
0006887534.tif 000050
が計算され、カーネルＫｉ，ｊについての性能改善指標値Ｍ（１）（ｉ，ｊ）の最初の計算においてｍｉ，ｊ（１）ｏｌｄ＝０である。
【００４１】
それゆえ、第１の手法において、各検討対象のカーネルＫｉ，ｊの入力信念が一致していない振幅が容易に得られる。
【００４２】
特定の一実施形態によれば、カーネルＫｉ，ｊごとの性能改善指標Ｍの値Ｍ（ｉ，ｊ）は、当該カーネルＫｉ，ｊの入力事後信念（ex-post beliefs）に関連付けられた情報レートの総和と、当該カーネルＫｉ，ｊの直前の更新の前の当該カーネルＫｉ，ｊの入力事後信念に関連付けられた情報レートの総和との間の総和レート差に依存し、事後信念は、事前信念及び外部信念（extrinsic beliefs）の総和である。
【００４３】
それゆえ、第２の手法として、各検討対象のカーネルＫｉ，ｊの入力信念が一致していない振幅が用いられて、カーネルがソートされ、それゆえ、復号プロセス性能が改善される。
【００４４】
特定の一実施形態によれば、カーネルＫｉ，ｊごとの性能改善指標Ｍの値Ｍ（ｉ，ｊ）＝Ｍ（２）（ｉ，ｊ）は、以下のように規定され、
【数５０】
0006887534.tif 000051
ここで、
【数５１】
0006887534.tif 000052
であり、Ｌｉ，２ｊ−１：２ｊ（ｉｎ）は、部分分極ステージｉ−１から到来する入力信念であり、Ｌｉ，２ｊ−１：２ｊ（ｏｕｔ）は、部分分極ステージｉ＋１から到来する入力信念であり、
【数５２】
0006887534.tif 000053
は、部分分極ステージｉ−１に向かう出力信念である
【数５３】
0006887534.tif 000054
の直前のそれぞれの値を表しており、
【数５４】
0006887534.tif 000055
は、部分分極ステージｉ＋１に向かう出力信念である
【数５５】
0006887534.tif 000056
の直前のそれぞれの値を表している。
【００４５】
それゆえ、第２の手法において、各検討対象のカーネルＫｉ，ｊの入力信念が一致していない振幅が容易に得られる。
【００４６】
特定の一実施形態によれば、カーネルＫｉ，ｊごとの性能改善指標Ｍの値Ｍ（ｉ，ｊ）は、上記カーネルＫｉ，ｊの最後の更新中のカーネルＫｉ，ｊによって出力される情報の増加に依存する。
【００４７】
それゆえ、各検討対象のカーネルＫｉ，ｊの出力信念がこの検討対象のカーネルＫｉ，ｊの近傍カーネルへの瞬時情報レートをもたらす振幅が用いられて、カーネルがソートされ、それゆえ、復号プロセス性能が改善される。
【００４８】
特定の一実施形態によれば、カーネルＫｉ，ｊごとの性能改善指標Ｍの値Ｍ（ｉ，ｊ）＝Ｍ（３）（ｉ，ｊ）は、以下のように規定され、
【数５６】
0006887534.tif 000057
ここで、
【数５７】
0006887534.tif 000058
は、部分分極ステージｉ−１に向かう出力信念であり、
【数５８】
0006887534.tif 000059
は、部分分極ステージｉ＋１に向かう出力信念である。
【００４９】
それゆえ、各検討対象のカーネルＫｉ，ｊの出力信念がこの検討対象のカーネルＫｉ，ｊの近傍カーネルへの瞬時情報レートをもたらす振幅が容易に得られる。
【００５０】
特定の一実施形態によれば、カーネルＫｉ，ｊごとの性能改善指標Ｍの値Ｍ（ｉ，ｊ）＝Ｍ（１）（ｉ，ｊ）＋Ｍ（３）（ｉ，ｊ）は、以下のように規定され、
【数５９】
0006887534.tif 000060
ここで、
【数６０】
0006887534.tif 000061
及び、
【数６１】
0006887534.tif 000062
であり、Ｌｉ，２ｊ−１：２ｊ（ｉｎ）は、部分分極ステージｉ−１から到来する入力信念であり、Ｌｉ，２ｊ−１：２ｊ（ｏｕｔ）は、部分分極ステージｉ＋１から到来する入力信念であり、
【数６２】
0006887534.tif 000063
は、部分分極ステージｉ−１に向かう出力信念であり、
【数６３】
0006887534.tif 000064
は、部分分極ステージｉ＋１に向かう出力信念であり、ｍｉ，ｊ（１）は、カーネルＫｉ，ｊの各有効な更新後にｍｉ，ｊ（１）ｏｌｄになり、有効な更新中、性能改善指標値Ｍ（ｉ，ｊ）＝Ｍ（１）（ｉ，ｊ）の後の更新において用いられるように、入力信念Ｌｉ，２ｊ−１：２ｊ（ｉｎ）及びＬｉ，２ｊ−１：２ｊ（ｏｕｔ）から出力信念
【数６４】
0006887534.tif 000065
及び
【数６５】
0006887534.tif 000066
が計算され、カーネルＫｉ，ｊについての性能改善指標値Ｍ（１）（ｉ，ｊ）の最初の計算においてｍｉ，ｊ（１）ｏｌｄ＝０である。
【００５１】
特定の一実施形態によれば、カーネルＫｉ，ｊごとの性能改善指標Ｍの値Ｍ（ｉ，ｊ）＝Ｍ（１）（ｉ，ｊ）．Ｍ（３）（ｉ，ｊ）は、以下のように規定され、
【数６６】
0006887534.tif 000067
ここで、
【数６７】
0006887534.tif 000068
及び、
【数６８】
0006887534.tif 000069
であり、Ｌｉ，２ｊ−１：２ｊ（ｉｎ）は、部分分極ステージｉ−１から到来する入力信念であり、Ｌｉ，２ｊ−１：２ｊ（ｏｕｔ）は、部分分極ステージｉ＋１から到来する入力信念であり、
【数６９】
0006887534.tif 000070
は、部分分極ステージｉ−１に向かう出力信念であり、
【数７０】
0006887534.tif 000071
は、部分分極ステージｉ＋１に向かう出力信念であり、ｍｉ，ｊ（１）は、カーネルＫｉ，ｊの各有効な更新後にｍｉ，ｊ（１）ｏｌｄになり、有効な更新中、性能改善指標値Ｍ（ｉ，ｊ）＝Ｍ（１）（ｉ，ｊ）の後の更新において用いられるように、入力信念Ｌｉ，２ｊ−１：２ｊ（ｉｎ）及びＬｉ，２ｊ−１：２ｊ（ｏｕｔ）から出力信念
【数７１】
0006887534.tif 000072
及び
【数７２】
0006887534.tif 000073
が計算され、カーネルＫｉ，ｊについての性能改善指標値Ｍ（１）（ｉ，ｊ）の最初の計算においてｍｉ，ｊ（１）ｏｌｄ＝０である。
【００５２】
特定の一実施形態によれば、以下の条件、すなわち、信念伝播反復プロセスが開始された後、所定の持続時間の期間が終わったとき、信念伝播反復プロセスにおいて、所定の回数の反復が実行されたとき、リストＬ内の最上位にあるカーネルの性能改善指標Ｍの値Ｍ（ｉ，ｊ）が所定の閾値未満であるとき、のうちの１つが充足されると、停止条件は満たされる。
【００５３】
それゆえ、復号プロセスを効率的に実行するために、処理リソースが容易に管理される。
【００５４】
本発明は、ｐｏｌａｒ符号の復号の範囲において信念伝播を実行するように構成されるｐｏｌａｒ符号デコーダであって、ｐｏｌａｒ符号は、Ｎビットのサイズを有するとともに、Ｎ／２個の並行カーネルＫｉ，ｊのＬ個の部分分極ステージの構造に基づいており、Ｎ及びＬは、Ｎ＝２Ｌとなるような正の整数であり、ｉは、カーネルＫｉ，ｊの部分分極ステージを識別するインデックスであり、ｊは、インデックスｉによって識別される部分分極ステージにおけるＮ／２個の並行カーネルの中の上記カーネルＫｉ，ｊの位置を表すインデックスであり、各部分分極ステージにおけるＮ／２個の並行カーネルは、シャッフラーによって、各隣接部分分極ステージにおける近傍のＮ／２個の並行カーネルから分離される、ｐｏｌａｒ符号デコーダにも関する。このデコーダは、構造のカーネルＫｉ，ｊごとの性能改善指標Ｍの値Ｍ（ｉ，ｊ）を計算する手段であって、性能改善指標Ｍは、検討対象のカーネルＫｉ，ｊの入力信念が一致していない振幅を表しており、及び／又は、性能改善指標Ｍは、検討対象のカーネルＫｉ，ｊの出力信念がこの検討対象のカーネルＫｉ，ｊの近傍カーネルへの瞬時情報レートをもたらす振幅を表している、手段と、カーネルを、性能改善指標Ｍの値Ｍ（ｉ，ｊ）の降順にリストＬ内でソートする手段とを備える。このデコーダは、正の整数であるＷにおいて、リストＬのＷ個の上位カーネルについて出力信念を更新すると、この出力信念を、上記Ｗ個の上位カーネルの近傍カーネルの入力信念として伝播することとを行う手段と、上記Ｗ個の上位カーネルの近傍カーネルごとの出力信念を、それらの入力信念の更新に後続して更新することと、上記近傍カーネルごとの性能改善指標値Ｍ（ｉ，ｊ）を再計算することとを行う手段と、上記Ｗ個の上位カーネルについて性能改善指標Ｍをヌル値に設定する手段と、性能改善指標Ｍの値Ｍ（ｉ，ｊ）の降順で、リストＬ内でカーネルを並べ替える手段とを含む信念伝播反復プロセスを実行する手段を更に備える。さらに、このデコーダは、停止条件が満たされるまで信念伝播反復プロセスを繰り返すように更に構成される。
【００５５】
また、本発明は、少なくとも１つの実施形態では、通信ネットワークからダウンロードし、及び／又は、コンピュータによって読み出すことができる非一時的情報記憶媒体上に記憶し、プロセッサ又は処理電子回路部によって実行することができるコンピュータプログラムにも関する。このコンピュータプログラムは、プロセッサ又は処理電子回路部によって実行されると、その種々の実施形態のうちのいずれか１つにおいて前述の方法を実施する命令を含む。
【００５６】
また、本発明は、コンピュータによって非一時的情報記憶媒体から読み出されてプロセッサ又は処理電子回路部によって実行されると、その種々の実施形態のうちのいずれか１つにおいて前述の方法を実施する、プロセッサによって実行することができる命令のセットを含むコンピュータプログラムを記憶する非一時的情報記憶媒体にも関する。
【図面の簡単な説明】
【００５７】
【図１】ｐｏｌａｒ符号エンコーダ及び対応するｐｏｌａｒ符号デコーダを備えるシステムを概略的に表す図である。
【図２Ａ】従来技術によるエンコーダの符号化部分を概略的に表す図である。
【図２Ｂ】従来技術による符号化部分の部分分極ステージを概略的に表す図である。
【図３】従来技術による符号化部分において用いられるバイナリカーネル構造を概略的に表す図である。
【図４Ａ】従来技術による復号部分のモジュール式アーキテクチャを概略的に表す図である。
【図４Ｂ】従来技術による復号アルゴリズムを概略的に表す図である。
【図４Ｃ】図３に概略的に示すカーネル構造に適用されるファクターグラフを概略的に表す図である。
【図４Ｄ】従来技術による信念伝播アルゴリズムを概略的に表す図である。
【図５】本発明による信念伝播アルゴリズムを概略的に表す図である。
【図６】本発明による信念伝播アルゴリズムを実装するハードウェアアーキテクチャの一例示の実施形態を概略的に表す図である。
【図７】本発明による信念伝播アルゴリズムの特定の一実施形態を概略的に表す図である。
【発明を実施するための形態】
【００５８】
本発明の範囲において、ｐｏｌａｒ符号の符号化及びＢＤＭＣを介した送信は、図１、図２Ａ、図２Ｂ、図２Ｃ及び図３に関して、本明細書において上記で提供された説明に従って実行される。ｐｏｌａｒ符号の復号は、図４Ａ、図４Ｂ及び図４Ｃに関して、本明細書において上記で提供された説明に従って実行される。一方、信念伝播は、図５、図６及び図７に関して、本明細書において以下で詳述されるように実行される。
【００５９】
一般に、ＢＤＭＣの相互情報量Ｉ（ｘ’；ｙ’）（ただし、入力ｘ’、出力ｙ’（すなわち、観測値）、及びチャネル遷移確率を特徴付ける確率関数Ｐ（ｙ’｜ｘ’））は、以下のように規定される。
【数７３】
0006887534.tif 000074
ここで、ＥＬ，［］は、対数尤度比（ＬＬＲ：Log Likelihood Ratio）と呼ばれる確率変数Ｌ’にわたる数学的期待値を表しており、Ｌ’は、以下のように規定される。
【数７４】
0006887534.tif 000075
ここで、Ｐ（ｙ’｜ｘ’）及びＰ（ｙ’｜１−ｘ’）の双方は、入力ビット及び出力チャネル観測値に依存する。
【００６０】
瞬時情報レートを、１−ｌｏｇ２（１＋ｅ−Ｌ’）、すなわち、相互情報量Ｉ（ｘ’；ｙ’）を提供する瞬時情報レートの数学的期待値と定義する。
【００６１】
カーネルＫｉ，ｊを検討する。（図３において表されるように）適切なサイズのカーネルに対する各出力は、送信チャネルに向かってｉ＋１からＬまでの深度位置に位置する他のカーネルの入力及び出力の組み合わせの全ての効果を包含するＢＤＭＣに関連付けられている。実際、各カーネルによって実行される演算は、バイナリ演算であり、これにより、チャネルのＢＤＭＣ性質は変更されない。
【００６２】
ビットｘｉ，２ｊ−１（ｏｕｔ）とチャネル観測値ベクトルｙｉ，２ｊ−１：２ｊとの間の相互情報量をＩ（ｘｉ，２ｊ−１（ｏｕｔ）；ｙｉ，２ｊ−１：２ｊ）とする。同様に、ビットｘｉ，２ｊ（ｏｕｔ）とチャネル観測値ベクトルｙｉ，２ｊ−１：２ｊとの間の相互情報量をＩ（ｘｉ，２ｊ（ｏｕｔ）；ｙｉ，２ｊ−１：２ｊ）とする。同様に、ビットｘｉ，２ｊ−１（ｉｎ）とチャネル観測値ベクトルｙｉ，２ｊ−１：２ｊとの間の相互情報量をＩ（ｘｉ，２ｊ−１（ｉｎ）；ｙｉ，２ｊ−１：２ｊ）とする。同様に、ビットｘｉ，２ｊ（ｉｎ）と、ビットｘｉ，２ｊ−１（ｉｎ）を、誤りを伴わずに知得した上でのチャネル観測値ベクトルｙｉ，２ｊ−１：２ｊとの間の相互情報量をＩ（ｘｉ，２ｊ（ｉｎ）；ｙｉ，２ｊ−１：２ｊ｜ｘｉ，２ｊ−１（ｉｎ））とする。分極化演算の結果として、及び、チャネルのＢＤＭＣ性質に起因して、以下の関係が存在する。
【数７５】
0006887534.tif 000076
これは、ｘｉ，２ｊ（ｉｎ）の復号を試みる前にｘｉ，２ｊ−１（ｉｎ）が正しく複合されているという仮定の下での、検討対象のカーネルの容量保存特性である。
【００６３】
【数７６】
0006887534.tif 000077
である場合、ステップＳ４７１に関して記載された各カーネルの計算規則から、以下の関係を表すことができることは留意に値する。
【数７７】
0006887534.tif 000078
この式には、保存特性が、瞬時的にも達成される（すなわち、情報レートにおいて数学的期待値が存在することなく達成される）ことが伴う。この特性は、Ｌｉ，２ｊ−１（ｏｕｔ）及びＬｉ，２ｊ（ｏｕｔ）から
【数７８】
0006887534.tif 000079
及び
【数７９】
0006887534.tif 000080
を更新した後カーネルがこの特性に達した場合、信念Ｌｉ，２ｊ−１（ｏｕｔ）及びＬｉ，２ｊ（ｏｕｔ）は、完全に一致していることを教示し、これには、反復処理の観点からカーネルが安定していることが伴う。カーネル演算は、（左から右、又は、右から左に）対称であるので、
【数８０】
0006887534.tif 000081
及び
【数８１】
0006887534.tif 000082
の、Ｌｉ，２ｊ−１（ｉｎ）及びＬｉ，２ｊ（ｉｎ）との比較と同じ観測が当てはまる。
【００６４】
結果として、特定の一実施形態では、カーネルの安定性のメトリックをそれゆえ導出することができ、入力信念が一致しておらず、かつ、既に安定している他のカーネルよりも高い、近傍カーネルへの更新を提供するカーネルに高優先度を与えることができる。
【００６５】
その上、特定の一実施形態では、近傍カーネルにより関連度が高くロバストな情報をフィードする、高瞬時情報レートを有する信念を操作するカーネルに高優先度を与えることができる。
【００６６】
対応するメトリックを以下で記載するように規定することによって、復号性能に最も有益な向上を提供し、したがって、与えられた性能目標のための復号プロセスの複雑度を低減させるカーネルを処理することに高優先度が与えられる。
【００６７】
図５は、本発明による信念伝播アルゴリズムを概略的に表している。
【００６８】
ステップＳ５０１において、デコーダ１２０は、カーネルＫｉ，ｊ（対（ｉ，ｊ）、∀ｉ，ｊによって識別される）ごとの性能改善指標Ｍの値Ｍ（ｉ，ｊ）を計算し、ここで、ｉは、０＜ｉ≦Ｌとなるようなインデックスであり、ｊは、０＜ｊ≦Ｎ／２となるようなインデックスである。換言すれば、インデックスｉは、ｐｏｌａｒ符号の構造における対（ｉ，ｊ）によって識別される、検討対象のカーネルＫｉ，ｊの深度位置（部分分極ステージ）を表しており、ｊは、インデックスｉによって識別される構造深度位置（部分分極ステージ）におけるＮ／２個の並行カーネルの中の当該検討対象のカーネルの位置を表している。
【００６９】
以下で詳述される実施形態によって表されるように、性能改善指標Ｍは、検討対象のカーネルＫｉ，ｊの入力信念が一致していない振幅を表しており（すなわち、性能改善指標Ｍの値Ｍ（ｉ，ｊ）がより高くなるほど、入力信念間の差が大きくなる）、及び／又は、性能改善指標Ｍは、検討対象のカーネルＫｉ，ｊの出力信念が当該検討対象のカーネルＫｉ，ｊの近傍カーネルへの瞬時情報レートをもたらす振幅を表している（すなわち、性能改善指標Ｍの値Ｍ（ｉ，ｊ）が高くなるほど、瞬時情報レートが大きくなる）。
【００７０】
第１の実施形態によれば、カーネルＫｉ，ｊ（それゆえ、対（ｉ，ｊ）によって識別される）ごとの性能改善指標値Ｍ（ｉ，ｊ）は、当該カーネルＫｉ，ｊの入力信念に関連付けられた情報レートの総和と、当該カーネルＫｉ，ｊの直前の更新の前の当該カーネルＫｉ，ｊの各入力信念に関連付けられた情報レートの総和との間の差に依存する。
【００７１】
第１の実施形態の特定の一例では、性能改善指標値Ｍ（ｉ，ｊ）＝Ｍ（１）（ｉ，ｊ）は、第１の実施形態において以下のように規定される。
【数８２】
0006887534.tif 000083
ここで、
【数８３】
0006887534.tif 000084
であり、ｍｉ，ｊ（１）は、カーネルＫｉ，ｊの各有効な更新後にｍｉ，ｊ（１）ｏｌｄになり、有効な更新中、性能改善指標値Ｍ（ｉ，ｊ）＝Ｍ（１）（ｉ，ｊ）の後の更新において用いられるように、入力信念Ｌｉ，２ｊ−１：２ｊ（ｉｎ）及びＬｉ，２ｊ−１：２ｊ（ｏｕｔ）から出力信念
【数８４】
0006887534.tif 000085
及び
【数８５】
0006887534.tif 000086
が計算され、カーネルＫｉ，ｊについての性能改善指標値Ｍ（１）（ｉ，ｊ）の最初の計算においてｍｉ，ｊ（１）ｏｌｄ＝０である。
【００７２】
カーネルＫｉ，ｊの少なくとも１つの入力が、このカーネルに接続された近傍カーネルの更新の後に更新されている場合、Ｋｉ，ｊと識別されたカーネルも更新されるべきである。時として、カーネルＫｉ，ｊの更新は、ｐｏｌａｒ符号の全体性能に対して有意の変化を有さず、これには、カーネルＫｉ，ｊの更新の優先度は、自身の入力のうちの１つに大幅な変化を被る別のカーネルの更新の優先度よりも低いことが伴う。それゆえ、性能改善メトリック値Ｍ（ｉ，ｊ）＝Ｍ（１）（ｉ，ｊ）は、複数のカーネルの更新の間の優先度を定量的に管理することを可能にする。
【００７３】
第２の実施形態によれば、カーネルＫｉ，ｊ（それゆえ、対（ｉ，ｊ）によって識別される）ごとの性能改善指標値Ｍ（ｉ，ｊ）は、当該カーネルＫｉ，ｊの入力事後信念に関連付けられた情報レートの総和と、当該カーネルＫｉ，ｊの直前の更新の前の当該カーネルＫｉ，ｊの入力事後信念に関連付けられた情報レートの総和との間の総和レート差に依存する。事後信念は、事前信念及び外部信念の総和であり、事前信念及び外部信念は、例えば、２ｊ−１によって識別される入力の場合（これは、カーネルＫｉ，ｊの第１の入力であり、２ｊによって識別される入力は、カーネルＫｉ，ｊの第２の入力である）、
【数８６】
0006887534.tif 000087
によって特徴付けられ、ここで、Ｌｉ，２ｊ−１（ｉｎ）は、この場合対応する外部信念を表しており、
【数８７】
0006887534.tif 000088
は、この場合対応する事前信念を表している。
【００７４】
第２の実施形態の特定の一例では、性能改善指標値Ｍ（ｉ，ｊ）＝Ｍ（２）（ｉ，ｊ）は、第２の実施形態において以下のように規定される。
【数８８】
0006887534.tif 000089
ここで、
【数８９】
0006887534.tif 000090
であり、
【数９０】
0006887534.tif 000091
は、
【数９１】
0006887534.tif 000092
の直前の値を表しており、
【数９２】
0006887534.tif 000093
は、
【数９３】
0006887534.tif 000094
の直前の値を表しており、
【数９４】
0006887534.tif 000095
は、
【数９５】
0006887534.tif 000096
の直前の値を表しており、
【数９６】
0006887534.tif 000097
は、
【数９７】
0006887534.tif 000098
の直前の値を表している。
【００７５】
この第２の実施形態は、第１の実施形態に近いが、各カーネルＫｉ，ｊ、∀ｉ，ｊの各入力／出力の計算に提供される又はこの計算から得られる最後のＬＬＲ値のメモリを保持する。例えば、Ｌｉ，２ｊ−１（ｉｎ）及び
【数９８】
0006887534.tif 000099
を総和することによって、（第１の実施形態におけるように）唯一考慮されるＬｉ，２ｊ−１（ｉｎ）によって提供される外部信念の代わりに事後信念に関連した情報が得られる。第２の実施形態を実施するために、デコーダ１２０は、各カーネルＫｉ，ｊ、∀ｉ，ｊの各入力／出力の各計算において、一方において
【数９９】
0006887534.tif 000100
、及び他方において
【数１００】
0006887534.tif 000101
をメモリに記憶する必要がある。記憶された信念は、このカーネルＫｉ，ｊの後続の処理の場合、それぞれ、一方において
【数１０１】
0006887534.tif 000102
、及び他方において
【数１０２】
0006887534.tif 000103
になる。
【００７６】
第３の実施形態によれば、カーネルＫｉ，ｊ（それゆえ、対（ｉ，ｊ）によって識別される）ごとの性能改善指標Ｍ（ｉ，ｊ）は、このカーネルＫｉ，ｊの最後の更新中のカーネルＫｉ，ｊによって出力される情報の増加に依存する。
【００７７】
第３の実施形態の特定の一例では、性能改善指標Ｍ（ｉ，ｊ）＝Ｍ（３）（ｉ，ｊ）は、第３の実施形態において以下のように規定される。
【数１０３】
0006887534.tif 000104
【００７８】
第４の実施形態によれば、対（ｉ，ｊ）によって識別されるカーネルごとの性能改善指標Ｍ（ｉ，ｊ）は、Ｍ（ｉ，ｊ）＝Ｍ（１）（ｉ，ｊ）＋Ｍ（３）（ｉ，ｊ）となるようになっている。
【００７９】
第５の実施形態によれば、対（ｉ，ｊ）によって識別されるカーネルごとの性能改善指標Ｍ（ｉ，ｊ）は、Ｍ（ｉ，ｊ）＝Ｍ（１）（ｉ，ｊ）．Ｍ（３）（ｉ，ｊ）となるようになっている。
【００８０】
ステップＳ５０２において、デコーダ１２０は、カーネルを、性能改善指標Ｍの降順にリストＬ内でソートする。
【００８１】
その後、以下で詳述されるように、停止条件が満たされるまで繰り返される信念伝播反復プロセスを開始する。
【００８２】
ステップＳ５０３において、デコーダ１２０は、リストＬ内のＷ個の上位カーネルについてＬＬＲを更新する。ここで、Ｗは、０＜Ｗ＜Ｌ．Ｎ／２となるような正の整数である。すなわち、Ｗ個のカーネルが最高の性能改善指標Ｍを有するような正の整数である。好ましい一実施形態では、Ｗ＝１である。
【００８３】
ステップＳ５０４において、デコーダ１２０は、リストＬ内の上記Ｗ個の上位カーネルの近傍カーネルごとにＬＬＲを更新する。
【００８４】
ステップＳ５０５において、デコーダ１２０は、リストＬ内のＷ個の上位カーネルが処理されているので、これらのカーネルについて性能改善指標Ｍをヌル値に設定し、それらの近傍カーネルの性能改善指標Ｍを再計算する。
【００８５】
ステップＳ５０６において、デコーダ１２０は、ステップＳ５０５において性能改善指標Ｍに対して行われた変更に従って、なおも性能改善指標Ｍの降順で、リストＬ内でカーネルを並べ替える。
【００８６】
ステップＳ５０７において、デコーダ１２０は、停止条件が満たされているか否かをチェックする。
【００８７】
第１の実施形態によれば、図５のアルゴリズムが開始された後、所定の持続時間の期間が終わったときに停止条件が満たされる。
【００８８】
第２の実施形態によれば、図５のアルゴリズムが開始された後、所定の回数の反復（すなわち、図５のアルゴリズムが開始された後、ステップＳ５０３が実行された回数）が実行されたときに停止条件が満たされる。
【００８９】
第３の実施形態によれば、リストＬ内の最上位にあるカーネルの性能改善指標Ｍが所定の閾値α未満であるときに停止条件が満たされる。閾値αを規定することは、復号性能と復号複雑度（すなわち、時間及び／又は用いられる処理リソース）との間のトレードオフを微調整することが可能になる。
【００９０】
停止条件が満たされると、信念伝播プロセスが終了し、ステップＳ５０８が実行される。停止条件が満たされない場合、ステップＳ５０６において並べ替えられたリストＬを用いてステップＳ５０３が繰り返される（信念伝播反復プロセスの新たな反復）。
【００９１】
ステップＳ５０８において、デコーダ１２０は、図５のアルゴリズムの処理ステップの実行によって達成される信念伝播の観点から復号判断を行う。
【００９２】
図６は、本発明による信念伝播アルゴリズムを実装するハードウェアアーキテクチャの一例示の実施形態を概略的に表している。図示のアーキテクチャによれば、デコーダ１２０は、通信バス６１０によって相互接続される以下の構成要素、すなわち、プロセッサ、マイクロプロセッサ、ＣＰＵ６００又はＧＰＵ；ＲＡＭ（ランダムアクセスメモリ）６０１；ＲＯＭ（リードオンリメモリ）６０２；ＳＤ（セキュアデジタル）カードリーダー６０３、又はＨＤＤ（ハードディスクドライブ）等の非一時的記憶媒体上に記憶された情報を読み出すように適応された他の任意のデバイス；及び、エンコーダ１００によって実行される送信中にｐｏｌａｒ符号が用いられるＢＤＭＣを有する通信インターフェース６０４を備える。
【００９３】
ＣＰＵ６００は、ＲＯＭ６０２から、又は、ＨＤＤ若しくはＳＤカード等の外部メモリからＲＡＭ６０１にロードされた命令を実行することが可能である。デコーダ１２０に電源が投入された後、ＣＰＵ６００は、ＲＡＭ６０１から命令を読み出すとともに、１つのコンピュータプログラムを形成するこれらの命令を実行することが可能である。
【００９４】
デコーダ１２０によって実行されるステップは、ＰＣ（パーソナルコンピュータ）、ＤＳＰ（デジタル信号プロセッサ）又はＧＰＵ（グラフィック処理装置）等のプログラマブルコンピューティング機械による命令又はプログラムのセットの実行によってソフトウェアにおいて実施することができる。実際、近頃では、ＧＰＵは、非画像計算に用いられることが多くなっている。なぜならば、ＧＰＵは、従来の画像関連処理よりも他の大量計算並列問題によく適しているからである。有利には、ＣＰＵ６００又はＧＰＵは、メモリ間転送がスケジューリングされたときに通常発生する処理リソースの無効時間中に、ｐｏｌａｒ符号の復号、とりわけ、信念伝播を含む復号を実行することができる。
【００９５】
図７は、本発明による信念伝播アルゴリズムの特定の一実施形態を概略的に表している。
【００９６】
ステップＳ７０１において、デコーダ１２０は、自身の信念伝播デコーダ４２２によって、０＜ｉ≦Ｌ及び０＜ｊ’≦Ｎ（インデックスｊは、その最大値がＮ／２であるためにここでは用いることができないので、インデックスｊ’がここでは用いられる）となるような出力信念
【数１０４】
0006887534.tif 000105
及び
【数１０５】
0006887534.tif 000106
、∀ｉ，ｊ’を得るように、入力信念Ｌｉ，ｊ（ｉｎ）及びＬｉ，ｊ（ｏｕｔ）についての信念伝播を達成するための呼び出しを開始する。
【００９７】
ステップＳ７０２において、デコーダ１２０は、
【数１０６】
0006887534.tif 000107
及び
【数１０７】
0006887534.tif 000108
をヌル値、∀ｉ，ｊ’に設定する。
【００９８】
ステップＳ７０３において、デコーダ１２０は、図５に関して既に記載されたように、０＜ｉ≦Ｌ及び０＜ｊ≦Ｎ／２となるようなカーネルＫｉ，ｊ（それゆえ、対（ｉ，ｊ）によって識別される）、∀ｉ，ｊごとの性能改善指標Ｍを計算する。
【００９９】
ステップＳ７０４において、デコーダ１２０は、カーネルを、性能改善指標Ｍの降順にリストＬ内でソートする。
【０１００】
ステップＳ７０５において、デコーダ１２０は、リストＬ内のＷ個の上位カーネルを抽出する。
【０１０１】
ステップＳ７０６において、デコーダ１２０は、Ｗ個の抽出されたカーネルの中から、カーネルＫｉ，ｊごとに、以下のように出力信念を計算する。
【数１０８】
0006887534.tif 000109
【０１０２】
ステップＳ７０７において、デコーダ１２０は、ステップＳ７０５においてリストＬから抽出されたカーネルごとに性能改善指標Ｍをリセットする。その後、性能改善指標Ｍは、これらのカーネルについてヌルになる。
【０１０３】
ステップＳ７０８において、デコーダ１２０は、ステップＳ７０５においてリストＬから抽出されたＷ個のカーネルの近傍カーネルについてＬＬＲを以下のように更新する。
ｉ＜Ｌの場合、
【数１０９】
0006887534.tif 000110
が、Ｌｉ＋１，ｊ’’（ｉｎ）として伝播し、ここで、ｊ’’は、この記述において、深度位置ｉ（部分分極ステージ）におけるシャッフラーΦｉ（この伝播方向では、シャッフリング演算φｉを指す）を介してカーネルＫｉ，ｊの出力２ｊ−１に接続される、深度位置ｉ＋１（部分分極ステージ）における近傍カーネルの位置を表しており、
ｉ＜Ｌの場合、
【数１１０】
0006887534.tif 000111
が、Ｌｉ＋１，ｊ’’（ｉｎ）として伝播し、ここで、ｊ’’は、この記述において、深度位置ｉ（部分分極ステージ）におけるシャッフラーΦｉ（この伝播方向では、シャッフリング演算φｉを指す）を介してカーネルＫｉ，ｊの出力２ｊに接続される、深度位置ｉ＋１（部分分極ステージ）における近傍カーネルの位置を表しており、
ｉ＞１の場合、
【数１１１】
0006887534.tif 000112
が、Ｌｉ−１，ｊ’’（ｏｕｔ）として伝播し、ここで、ｊ’’は、この記述において、深度位置ｉ−１（部分分極ステージ）におけるシャッフラーΦｉ−１（この伝播方向では、逆シャッフリング演算φｉ−１−１を指す）を介してカーネルＫｉ，ｊの出力２ｊ−１に接続される、深度位置ｉ−１（部分分極ステージ）における近傍カーネルの位置を表しており、
ｉ＞１の場合、
【数１１２】
0006887534.tif 000113
が、Ｌｉ−１，ｊ’’（ｏｕｔ）として伝播し、ここで、ｊ’’は、この記述において、深度位置ｉ−１（部分分極ステージ）におけるシャッフラーΦｉ−１（この伝播方向では、逆シャッフリング演算φｉ−１−１を指す）を介してカーネルＫｉ，ｊの出力２ｊに接続される、深度位置ｉ−１（部分分極ステージ）における近傍カーネルの位置を表している。
【０１０４】
ステップＳ７０９において、デコーダ１２０は、ステップＳ７０８において実行されたＬＬＲ更新に従って、ステップＳ７０５においてリストＬから抽出されたＷ個のカーネルの近傍カーネルごとに性能改善指標Ｍを更新する。
【０１０５】
ステップＳ７１０において、デコーダ１２０は、ステップＳ７０７及びＳ７０９において性能改善指標Ｍに対して行われた変更に従って、なおも性能改善指標Ｍの降順で、リストＬ内でカーネルを並べ替える。
【０１０６】
ステップＳ７１１において、デコーダ１２０は、図５に関して既に記載されたように、停止条件が満たされているか否かをチェックする。停止条件が満たされると、ステップＳ７１２が実行される。停止条件が満たされない場合、ステップＳ７１０において並べ替えられたリストＬを用いてステップＳ７０５が繰り返される。
【０１０７】
ステップＳ７１２において、信念伝播は、そのままの状態で復号判断を行うことを可能にするために、出力信念
【数１１３】
0006887534.tif 000114
及び
【数１１４】
0006887534.tif 000115
∀ｉ，ｊ’を返すことによって終了する。
【図１】
0006887534.tif 000143
【図２Ａ】
0006887534.tif 000144
【図２Ｂ】
0006887534.tif 000145
【図３】
0006887534.tif 000146
【図４Ａ】
0006887534.tif 000147
【図４Ｂ】
0006887534.tif 000148
【図４Ｃ】
0006887534.tif 000149
【図４Ｄ】
0006887534.tif 000150
【図５】
0006887534.tif 000151
【図６】
0006887534.tif 000152
【図７】
0006887534.tif 000153