(57)【要約】【課題】より少ない計算量で高速に、かつ小さい回路規模で信頼性の高い復号を行うことが可能な復号方法および復号装置、並びにプログラムを提供する。【解決手段】受信語の信頼度の大きさに従いソートし、その順番に対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を行って信頼度を更新し、その更新された値に対して、再び上記動作を繰り返す復号装置３０であって、受信語の信頼度（ＬＬＲ）の信頼性伝播（ＢＰ）を行う信頼性伝播部３５を有し、信頼性伝播部３５は、更新する列のインデックスと、この列に対応するパリティ検査行列の要行と、全列のＬＬＲのみを用いて信頼性伝播を行う。【選択図】図５
2008167379.tif 000002
【特許請求の範囲】
【請求項１】
受信語の信頼度の大きさに従いソートし、その順番に対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を行って信頼度を更新し、その更新された値に対して、再び上記動作を繰り返す復号方法であって、
受信語の信頼度（ＬＬＲ）の信頼性伝播（ＢＰ）を行うＢＰステップを有し、
前記ＢＰステップにおいては、
更新する列のインデックスと、当該列に対応するパリティ検査行列の要行と、全列のＬＬＲのみを用いて信頼性伝播を行う
復号方法。
【請求項２】
前記ＢＰステップは、
入力ＬＬＲとパリティ検査行によりチェックノード演算を行い、更新メッセージを生成する第１ステップと、
更新する列のインデックスにより選択された更新する列のＬＬＲと前記第１ステップで生成された更新メッセージにより更新列のＬＬＲを更新する第２ステップと、を含む
請求項１記載の復号方法。
【請求項３】
前記第２ステップにおいては、
対角化対象列のみそのＬＬＲの更新を行う
請求項２記載の復号方法。
【請求項４】
前記第２ステップにおいては、
非対角化対象列についてそのＬＬＲをそのまま更新値とする
請求項３記載の復号方法。
【請求項５】
前記第２ステップにおいては、
選択された更新する列のＬＬＲと更新メッセージとを足し合わせてＬＬＲを更新する
請求項２記載の復号方法。
【請求項６】
前記ＢＰステップにおいて、
信頼性伝播の繰り返しは１回である
請求項１から５のいずれか一に記載の復号方法。
【請求項７】
受信語の信頼度の大きさに従いソートし、その順番に対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を行って信頼度を更新し、その更新された値に対して、再び上記動作を繰り返す復号装置であって、
受信語の信頼度（ＬＬＲ）の信頼性伝播（ＢＰ）を行う信頼性伝播部を有し、
前記信頼性伝播部は、
更新する列のインデックスと、当該列に対応するパリティ検査行列の要行と、全列のＬＬＲのみを用いて信頼性伝播を行う
復号装置。
【請求項８】
前記信頼性伝播部は、
入力ＬＬＲとパリティ検査行によりチェックノード演算を行い、更新メッセージを生成する演算部と、
更新する列のインデックスにより選択された更新する列のＬＬＲと前記第１ステップで生成された更新メッセージにより更新列のＬＬＲを更新する更新部と、を含む
請求項７記載の復号装置。
【請求項９】
前記更新部は、
対角化対象列のみそのＬＬＲの更新を行う
請求項８記載の復号装置。
【請求項１０】
前記更新部は、
非対角化対象列についてそのＬＬＲをそのまま更新値として出力する
請求項９記載の復号装置。
【請求項１１】
前記更新部は、
選択された更新する列のＬＬＲと更新メッセージとを足し合わせてＬＬＲを更新する
請求項８記載の復号装置。
【請求項１２】
前記信頼性伝播部において、
信頼性伝播の繰り返しは１回である
請求項７から１１のいずれか一に記載の復号装置。
【請求項１３】
受信語の信頼度の大きさに従いソートし、その順番に対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を行って信頼度を更新し、その更新された値に対して、再び上記動作を繰り返す復号処理において、
受信語の信頼度（ＬＬＲ）の信頼性伝播（ＢＰ）を行うＢＰステップで、
更新する列のインデックスと、当該列に対応するパリティ検査行列の要行と、全列のＬＬＲのみを用いて信頼性伝播（ＢＰ）を行う処理を
コンピュータに実行させるプログラム。
【請求項１４】
前記ＢＰステップにおいて、
入力ＬＬＲとパリティ検査行によりチェックノード演算を行い、更新メッセージを生成する第１の処理と、
更新する列のインデックスにより選択された更新する列のＬＬＲと前記第１の処理で生成された更新メッセージにより更新列のＬＬＲを更新する第２の処理と、を含む処理をコンピュータに実行させる
請求項１３記載のプログラム
【請求項１５】
前記第２の処理においては、
対角化対象列のみそのＬＬＲの更新を行う
請求項１４記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、たとえば代数的手法を用いた誤り訂正符号技術を実現するための回路およびプログラム記憶媒体に関して適用される復号方法および復号装置、並びにプログラムに関するものである。
【背景技術】
【０００２】
代数幾何符号、たとえばリードソロモン（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ）符号やその部分体部分符号としてのＢＣＨ符号には、その代数的性質を利用した、性能・計算コスト共に良い復号法が知られている。
【０００３】
たとえば、符号長ｎ、情報長ｋ、定義体ＧＦ（ｑ）（ｑ＝ｐｍ，ｐ：素数）、最小距離ｄ＝ｎ−ｋのＲｅｅｄ−Ｓｏｌｏｍｏｎ符号をＲＳ（ｎ，ｋ）とすると、硬判定受信語をハミング（Ｈａｍｍｉｎｇ）距離が最小の符号語に復号する最小距離復号（通常復号）はｔ＜ｄ／２を満たすｔ個の誤りシンボルの訂正を保証するものとして良く知られている。
【０００４】
また、グルスワミ−スーダン（Ｇｕｒｕｓｗａｍｉ−Ｓｕｄａｎ）によるリスト復号（以下Ｇ−Ｓリスト復号）は、ｔ＜√ｎｋを満たすｔ個の誤りシンボルの訂正を保証している（非特許文献１参照）。
【０００５】
Ｇｕｒｕｓｗａｍｉ−Ｓｕｄａｎのリスト復号の拡張版として軟判定受信語を用いたコータ−バルディ（Ｋｏｅｔｔｅｒ−Ｖａｒｄｙ）によるリスト復号（以下Ｋ−Ｖリスト復号）は、Ｇｕｒｕｓｗａｍｉ−Ｓｕｄａｎ同様に（１）受信情報から各シンボルの信頼性を算出、（２）信頼性から２変数多項式補間条件の抽出、（３）２変数多項式の補間、（４）補間多項式の因数分解を行い復号語リスト作成、の４つの手順により構成され、硬判定復号時に比べてより高い性能を持つことが知られている（非特許文献２参照）。
【０００６】
また、リエンコード（Ｒｅ−ｅｎｃｏｄｅ）により、その計算コストも現実的な範囲まで削減できることが知られている（非特許文献３参照）。
【０００７】
一方、線形符号としては、信頼性伝播（ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を用いた繰り返し復号により限界性能に近い高性能を得られる低密度パリティ検査符号（Ｌｏｗ  ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ−ｃｈｅｃｋ  ｃｏｄｅ，ＬＤＰＣ符号）が昨今注目されている（非特許文献４参照）。
【０００８】
ＬＤＰＣ符号に用いられる信頼性伝播（ＢＰ）は、一般に低密度なパリティ検査行列を持つ線形符号にしか有効でないことが理論的に知られており、また、Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号やＢＣＨ符号のパリティ検査行列を低密度化することはＮＰ−ｈａｒｄであることが知られている（非特許文献５参照）。
【０００９】
よって、Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号やＢＣＨ符号に信頼性伝播（ＢＰ）を適用することは困難であるとされてきた。
【００１０】
しかし、２００４年、受信語の信頼性に応じて対角化を行ったパリティ検査行列を用いてＲｅｅｄ−Ｓｏｌｏｍｏｎ符号やＢＣＨ符号、その他低密度でないパリティ検査行列を持つ線形符号への信頼性伝播（ＢＰ）の適用が効果的であることがナラヤナン(Ｎａｒａｙａｎａｎ)等によって紹介された（非特許文献６参照）。
【００１１】
この手法は、適応的信頼性伝播（ＡＢＰ：Ａｄａｐｔｉｖｅ  Ｂｅｌｉｅｆ  Ｐｒｏｐａｇａｔｉｏｎ）復号と呼ばれる。以下、このＡＢＰ復号法について説明する。
【００１２】
たとえば、符号長ｎ＝６、情報長ｋ＝３、符号化率ｒ＝１／２の符号で、以下の３×６行列Ｈをパリティ検査行列として持つような線形符号Ｃを考える。
【００１３】
【数１】
2008167379.tif 000003
【００１４】
符号空間Ｃは、次のように表される。
【００１５】
【数２】
2008167379.tif 000004
【００１６】
ある符号語があるチャネル、たとえばＢＰＳＫ変調＋ＡＷＧＮチャネル（Ａｄｄｉｔｉｖｅ  Ｗｈｉｔｅ  Ｇａｕｓｓｉａｎ  Ｎｏｉｓｅチャネル）を通った後、次のような受信語ｒとして受信機が受け取ったとする。
【００１７】
【数３】
2008167379.tif 000005
【００１８】
このとき、受信値の各絶対値の大きさは受信語の信頼性の高さを表す。つまり、信頼性の低い順に番号をつけると以下のようになる。
【００１９】
【数４】
2008167379.tif 000006
【００２０】
次に、信頼性の低いシンボルに対応する列より順にパリティ検査行列Ｈの対角化を行う。この例においては、信頼性の低いシンボルに対応する列は順に第３列、第５列、第１列、第４または第６列、第２列となるので、その優先順位に従ってＨの対角化を行う。
【００２１】
【数５】
2008167379.tif 000007
【００２２】
【数６】
2008167379.tif 000008
【００２３】
【数７】
2008167379.tif 000009
【００２４】
対角化を試みた列がそれ以前に対角化した列と線形従属であった場合は、その列はそのまま残し、次の順位の列で対角化を試みる。
このようにして行列Ｈのランク分対角化が行われた結果得られる新たなパリティ検査行列Ｈｎｅｗを用いて、信頼性伝播（ＢＰ）による信頼性の更新を行う。
【００２５】
図１はパリティ検査行列Ｈｎｅｗに対応するタナーグラフである。
信頼性伝播（ＢＰ）はタナーグラフのエッジに沿ってメッセージを行き来させることによって実現される。
行列の各列に対応するノードを可変（ｖａｒｉａｂｌｅ：バリアブル）ノード１、各行に対応するノードを検査（ｃｈｅｃｋ：チェック）ノード２と呼ぶ。
【００２６】
ｉ番目のバリアブルノードからｊ番目のチェックノードへのメッセージをＱi,j、ｊ番目のチェックノードからｉ番目のバリアブルノードへのメッセージをＲｉ,j、さらにｉ番目のバリアブルノードに連接するチェックノードのインデックス集合をＪ（ｉ）、ｊ番目のチェックノードに連接するバリアブルノードのインデックス集合をＩ（ｊ）とした場合、それぞれの更新式は以下のようになる。
【００２７】
【数８】
2008167379.tif 000010
【００２８】
ここで、θはバーティカルステップダンピングファクタ（ｖｅｒｔｉｃａｌ  ｓｔｅｐ  ｄａｍｐｉｎｇ  ｆａｃｔｏｒ）と呼ばれる係数を示し、０＜θ≦１なる条件を満足する。Ｑi,jの初期値はｒjが設定され、外部情報（ｅｘｔｒｉｎｓｉｃ  ｉｎｆｏｒｍａｔｉｏｎ）Λｉｘ更新は次式により行われる。
【００２９】
【数９】
2008167379.tif 000011
【００３０】
さらに、各符号ビットのＬＬＲΛｉｑの更新は、次式により行われる。
【００３１】
【数１０】
2008167379.tif 000012
【００３２】
ここで、α１は適応的信頼性伝播ダンピングファクタ（ａｄａｐｔｉｖｅ  ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ  ｄａｍｐｉｎｇ  ｆａｃｔｏｒ）と呼ばれる係数を示し、０＜α１≦１なる条件を満足する。
この信頼性伝播（ＢＰ）によるＬＬＲの更新は事前に用意された繰り返し停止条件を満たすまで、たとえば最大繰り返し数ＩｔＨに達成するまで繰り返される。
また、ＬＬＲを更新する列は、全ての列を対象とせずとも一部の列、たとえば対角化の対象となった列についてのみ行ってもよい。
【００３３】
信頼性伝播（ＢＰ）によって更新されたＬＬＲの信頼性を用いて、つまり、ＬＬＲの絶対値の大きさを信頼性として、信頼性の低いシンボルに対応する列順に対角化を行うことにより、新たな信頼性伝播（ＢＰ）による繰り返し復号を行うことができる。
これを内側繰り返し復号と呼ぶ。このＬＬＲの更新は事前に用意された内側繰り返し復号停止条件ＳＣ１を満たすまで繰り返される。
【００３４】
さらに、パリティ検査行列の列の対角化優先順位の初期値として、受信値の信頼性順以外の順位を複数用意する。複数の順位を用いて、シリアルもしくはパラレルに繰り返し内側繰り返し復号を行う。
これを外側繰り返し復号と呼ぶ。このＬＬＲ更新は事前に用意された外側繰り返し復号停止条件ＳＣ２を満たすまで繰り返される。
【００３５】
以上のＡＢＰ（ａｄａｐｔｉｖｅ  ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ）手順により繰り返し更新されたＬＬＲを入カとして、復号器により復号を行う。
今、対象となる線形符号がＲｅｅｄ−Ｓｏｌｏｍｏｎ符号であった場合、繰り返し復号停止条件ＳＣ１、ＳＣ２として、たとえば以下のものが考えられる。
【００３６】
（Ａ）  Ｈ・ｄ  ＝＝  ０または繰り返し数ｔ≧Ｎ、
（Ｂ）  限界距離復号成功または繰り返し数ｔ≧Ｎ、
（Ｃ）  Ｋｏｅｔｔｅｒ−Ｖａｒｄｙ軟判定リスト復号成功または繰り返し数ｔ≧Ｎ。
【００３７】
ここで、ｄ＝（ｄ１，ｄ２，・・・，ｄ６）はΛｉの硬判定結果、ｄｉ＝｛Λｉｑ＞０なら１，Λｉｑ≦０なら０｝であり、Ｎは事前に決めた最大繰り返し回数である。
また、復号方法として、たとえば以下のものが考えられる。
【００３８】
（ａ）  硬判定復号
（ｂ）  限界距離復号
（ｃ）  Ｋｏｅｔｔｅｒ−Ｖａｒｄｙ軟判定リスト復号
【００３９】
図２は、ＡＢＰ復号法を用いた繰り返し復号のフローチャートである。
【００４０】
受信語の信頼性順の探索を行い（ＳＴ１）、順序変換を行う（ＳＴ２）。
変換した順序に応じてパリティ検査行列の対角化を行い（ＳＴ３）、このパリティ検査行列を用いて信頼性伝播（ＢＰ）を行う（ＳＴ４）。
次に、ＬＬＲを計算し（ＳＴ５）、計算したＬＬＲの信頼性順を探索し（ＳＴ６）、復号を行い、復号語をリストへ追加する（ＳＴ７）。
そして、繰り返し復号停止条件Ｎ１，Ｎ２を満足するまで以上の処理を繰り返す（ＳＴ８、ＳＴ９）。
そして、復号語を１つ選択する（ＳＴ１０）。
【００４１】
【非特許文献１】Ｖ．Ｇｕｒｕｓｗａｍｉ，Ｍ．Ｓｕｄａｎ，Ｉｍｐｒｏｖｅ  ｄｅｃｏｄｉｎｇ  ｏｆ  Ｒｅｅｄ−Ｓｏｌｏｍｏｎ  ａｎｄ  Ａｌｇｅｂｒａｉｃ−Ｇｅｏｍｅｔｒｙ  ｃｏｄｅｓ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ｖｏｌ．４５，ｐｐ．１７５７−１７６７，１９９９
【非特許文献２】Ｒ．Ｋｏｅｔｔｅｒ，Ａ．Ｖａｒｄｙ，Ａｌｇｅｂｒａｉｃ  ｓｏｆｔ−ｄｅｃｉｓｉｏｎ  ｄｅｃｏｄｉｎｇ  ｏｆ  Ｒｅｅｄ−Ｓｏｌｏｍｏｎ  ｃｏｄｅｓ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，２００１
【非特許文献３】Ｒ．Ｋｏｅｔｔｅｒ，Ｊ．Ｍａ，Ａ．Ｖａｒｄｙ，Ａ，Ａｈｍｅｄ，Ｅｆｆｃｉｅｎｔ  Ｉｎｔｅｒｐｏｌａｔｉｏｎ  ａｎｄ  Ｆａｃｔｏｒｉｚａｔｉｏｎ  ｉｎ  Ａｌｇｅｂｒａｉｃ  Ｓｏｆｔ−Ｄｅｃｉｓｉｏｎ  Ｄｅｃｏｄｉｎｇ  ｏｆ  Ｒｅｅｄ−Ｓｏｌｏｍｏｎ  ｃｏｄｅｓ，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＩＳＩＴ２００３
【非特許文献４】Ｄ．ＭａｃＫａｙ，Ｇｏｏｄ  Ｅｒｒｏｒ−Ｃｏｒｒｅｃｔｉｎｇ  Ｃｏｄｅｓ  Ｂａｓｅｄ  ｏｎ  Ｖｅｒｙ  Ｓｐａｒｓｅ  Ｍａｔｒｉｃｅｓ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，１９９９
【非特許文献５】Ｂｅｒｌｅｋａｍｐ，Ｒ．ＭｃＥｌｉｅｃｅ，Ｈ．ｖａｎ  Ｔｉｌｂｏｒｇ，Ｏｎ  ｔｈｅ  ｉｎｈｅｒｅｎｔ  ｉｎｔｒａｃｔａｂｉｌｉｔｙ  ｏｆ  ｃｅｒｔａｉｎ  ｃｏｄｉｎｇ  ｐｒｏｂｌｅｍｓ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ｖｏｌ．２４，ｐｐ．３８４−３８６，Ｍａｙ，１９７８）。
【非特許文献６】Ｊｉｎｇ  Ｊｉａｎｇ，Ｋ．Ｒ．Ｎａｒａｙａｎ，Ｓｏｆｔ  Ｄｅｃｉｓｉｏｎ  Ｄｅｃｏｄｉｎｇ  ｏｆ  ＲＳ  Ｃｏｄｅｓ  Ｕｓｉｎｇ  Ａｄａｐｔｉｖｅ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ  Ｍａｔｒｉｃｅｓ，Ｐｒｏｃｅｅｄｉｎｇ  ｏｆ  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ  ２００４
【発明の開示】
【発明が解決しようとする課題】
【００４２】
ところで、上述技術では、信頼性伝播（ＢＰ）の最大繰り返し数ＩｔＨは、特に回数が定められていない。また、繰り返し数が増えるにつれて計算量は増大する。
また、ＬＬＲ更新を符号語全てのノードに対して行うとかなり演算量がかかり、特に対角化対象列以外のノードは、部分行列が非常に密であるため、その演算量は非常に大きくなる。
特に、信頼性伝播（ＢＰ）装置においては、チェックノード演算とバリアブルノード演算を両方行わなければならず、両者のためパリティ検査行とパリティ検査行列の列の両方必要になり、前段の対角化回路から両方とも読み出すのは一般的なメモリの構成上でも困難である。
【００４３】
また、メッセージ（ｍｅｓｓａｇｅ）メモリは、パリティ検査行列の１の数のワード数が必要になるが、パリティ検査行列は随時変化するため、定まったメモリワード数を設定しにくいし、ワード数を十分大きくとろうとするとメモリがさらに増大する。
また、そもそも、バリアブルノード演算装置とメッセージメモリ自体の回路規模も大きい。
【００４４】
本発明は、より少ない計算量で高速に、かつ小さい回路規模で信頼性の高い復号を行うことが可能な復号方法および復号装置、並びにプログラムを提供することにある。
【課題を解決するための手段】
【００４５】
本発明の第１の観点は、受信語の信頼度の大きさに従いソートし、その順番に対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を行って信頼度を更新し、その更新された値に対して、再び上記動作を繰り返す復号方法であって、受信語の信頼度（ＬＬＲ）の信頼性伝播（ＢＰ）を行うＢＰステップを有し、前記ＢＰステップにおいては、更新する列のインデックスと、当該列に対応するパリティ検査行列の要行と、全列のＬＬＲのみを用いて信頼性伝播を行う。
【００４６】
好適には、前記ＢＰステップは、入力ＬＬＲとパリティ検査行によりチェックノード演算を行い、更新メッセージを生成する第１ステップと、更新する列のインデックスにより選択された更新する列のＬＬＲと前記第１ステップで生成された更新メッセージにより更新列のＬＬＲを更新する第２ステップと、を含む。
【００４７】
好適には、前記第２ステップにおいては、対角化対象列のみそのＬＬＲの更新を行う。
【００４８】
本発明の第２の観点は、受信語の信頼度の大きさに従いソートし、その順番に対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を行って信頼度を更新し、その更新された値に対して、再び上記動作を繰り返す復号装置であって、受信語の信頼度（ＬＬＲ）の信頼性伝播（ＢＰ）を行う信頼性伝播部を有し、前記信頼性伝播部は、更新する列のインデックスと、当該列に対応するパリティ検査行列の要行と、全列のＬＬＲのみを用いて信頼性伝播を行う。
【００４９】
好適には、前記信頼性伝播部は、入力ＬＬＲとパリティ検査行によりチェックノード演算を行い、更新メッセージを生成する演算部と、更新する列のインデックスにより選択された更新する列のＬＬＲと前記第１ステップで生成された更新メッセージにより更新列のＬＬＲを更新する更新部と、を含む。
【００５０】
好適には、前記更新部は、対角化対象列のみそのＬＬＲの更新を行う。
【００５１】
本発明の第３の観点は、受信語の信頼度の大きさに従いソートし、その順番に対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を行って信頼度を更新し、その更新された値に対して、再び上記動作を繰り返す復号処理において、受信語の信頼度（ＬＬＲ）の信頼性伝播（ＢＰ）を行うＢＰステップで、更新する列のインデックスと、当該列に対応するパリティ検査行列の要行と、全列のＬＬＲのみを用いて信頼性伝播（ＢＰ）を行う処理をコンピュータに実行させるプログラムである。
【００５２】
本発明によれば、そもそも信頼度の高いノードは、誤っていない可能性が高く、信頼度の低いノードは誤っている可能性が高い。また、対角化対象列と非対称列が入れ替わるのは、信頼度が近い両者間で起こりうり、かなり信頼度の高いノードについては対角化対象列にはまずなりにくい。以上から、対角化対象列以外のノードについては、ＬＬＲ更新は行わない。
また、信頼性伝播（ＢＰ）では、タナーグラフ上で２ｎのサイクルが存在する場合、ｎ回以上の信頼性伝播の繰り返しを行うとメッセージどうしの独立性が損なわれ性能劣化を生じる可能性がある。実際、パリティ検査行列も非常に密でｎ＝２のサイクルを多数持つ。このことから、本発明においては、信頼性伝播（ＢＰ）の繰り返し数を一回に限定されるように構成されている。
【発明の効果】
【００５３】
本発明によれば、より少ない計算量で高速に、かつ小さい回路規模で信頼性の高い復号を行うことができる利点がある。
【発明を実施するための最良の形態】
【００５４】
以下、本発明の実施形態を図面に関連付けて説明する。
【００５５】
本発明の実施形態に係る復号装置は、代数的手法を用いた誤り訂正符号技術を実現するための回路、たとえば適応的信頼性伝播（Ａｄａｐｔｉｖｅ  Ｂｅｌｉｅｆ  Ｐｒｏｐａｇａｔｉｏｎ：ＡＢＰ）復号器として応用できる。
ＡＢＰ復号は、リードソロモン（Ｒｅａｄ−Ｓｏｌｏｍｏｎ：ＲＳ）符号やＢＣＨ符号、その他低密度でないパリティ検査行列を持つ線形符号に対する復号法であり、ある伝送路から符号語を受信すると、その受信語をより信頼できる値に更新する。
【００５６】
以下、ＡＢＰ復号における復号装置の通信システム上の位置づけについて説明した後、本実施形態に係るソート装置の具体的な構成および機能について説明する。
【００５７】
図３は、デジタル信号受信機、たとえばデジタルテレビなどの誤り訂正システムにＡＢＰ復号器を用いた通信システムの構成例を示す図である。
【００５８】
本通信システム１０は、図３に示すように、ＲＳ符号化器１１、インタリーバ１２、畳み込み符号器１３、畳み込み符号の軟出力復号器１４、デインタリーバ１５、ＡＢＰ繰り返し復号器１６、およびチャネル１７を有する。
【００５９】
本通信システム１０では、ＲＳ符号化、畳み込み符号化された送信語に対して、畳み込み符号の軟出力復号をした後にＡＢＰ復号を行っている。
ここで言う畳み込み符号の軟出力復号とは、たとえばＢＣＪＲアルゴリズムやＳＯＶＡによる復号のことである。
ＡＢＰ復号器１６においては、ＡＢＰによる信頼性の更新後、硬判定後限界距離復号、リスト復号、もしくは、軟値をそのまま入力として軟判定リスト復号を行う。
【００６０】
図４は、ＭＡＰ復号が後段についたＡＢＰ復号器の構成例を示す図である。
この復号器２０は、図４に示すように、ＡＢＰ復号部２１、限界距離（ＢＤ）復号部２２、受信信頼度（ＬＬＲ）保持部２３、およびＭＡＰ復号部２４を有している。
【００６１】
復号器２０においては、ＡＢＰ復号部２１による信頼性（ＬＬＲ）の更新後、硬判定してＢＤ復号部２２において、限界距離復号を行い、この結果をリストに集め、最終的にＭＡＰ復号部２４において最大事後確率復号（Ｍａｘｉｍｕｍ  ａ  ｐｏｓｔｅｒｉｏｒｉ  Ｐｒｏｂａｂｉｌｉｙ：ＭＡＰ）復号を行う。
【００６２】
図５は、ＡＢＰ復号器の復号装置の構成例を示す図である。
【００６３】
図５のＡＢＰ復号器３０は、図３のＡＢＰ復号器１６や図４のＡＢＰ復号部２１に適用可能であり、ソート入力選択部３１、ソート部３２、パリティ検査行列の対角化部３３、信頼度（ＬＬＲ）保持部３４、および信頼性伝播（ＢＰ）部３５を有している。
【００６４】
ＡＢＰ復号器３０においては、入力として、受信ＬＬＲＳ３２が入力される。
列インデックスＳ３１は、入力された受信ＬＬＲの符号語の始まりからカウンタで０、１、２、３、、とカウントアップされた値を生成し利用する。
ソート入力選択部３１で、初回は、列インデックスＳ３１と受信ＬＬＲＳ３２を選択し、繰り返し二回目以降は信頼性伝播（ＢＰ）後、更新ＬＬＲＳ４０とその列インデックスＳ３９を選択する。
【００６５】
図５に示すように、受信語が入力されたら、まず、ソート部３２において、その信頼度（ＬＬＲ）の大きさに応じて列インデックスのソートを行う。
次に、信頼度の低いシンボルに対応する列より順に、対角化部３３でパリティ検査行列の対角化を行う。
最後に、対角化されたパリティ検査行Ｓ３７を用いて、信頼性伝播（ＢＰ）を行うことにより、値が更新される。
更新された値に対して、再びソート、対角化、信頼性伝播（ＢＰ）を行う。繰り返し数が予め決められており、その繰り返し数だけこれを繰り返す。
【００６６】
この復号器３０の信頼性伝播（ＢＰ）部３５において、本発明の実施形態に係る復号方法を適用することが可能である。
【００６７】
図６、図７、および図８は、本発明の実施形態に係る適応的信頼性伝播（ＡＢＰ：ａｄａｐｔｉｖｅ  ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ）を用いた繰り返し復号のタナーグラフ上のメッセージの流れを表す図である。
【００６８】
本実施形態においては、信頼性伝播（ＢＰ）の繰り返し数を一回に抑え、さらに信頼度を対角化対象列のみ更新する。
図６で、まずバリアブルノード（ｖａｒｉａｂｌｅ  ｎｏｄｅ）ノード４１からチェックノード（ｃｈｅｃｋ  ｎｏｄｅ）４２へのメッセージの初期値を決定する。初期値は、受信語ｒiが設定される。つまり、次式で与えられる。
【００６９】
【数１１】
2008167379.tif 000013
【００７０】
次に、図７でチェックノード４２からバリアブルノード４１へのメッセージが次のように計算される。
【００７１】
【数１２】
2008167379.tif 000014
【００７２】
最後に、図８において、繰り返し数が一回なので、バリアブルノード４１におけるバリアブルノード演算は行われず、各ビットのＬＬＲが更新される。対角化対象列である第１列、第３列、第５列については、値が更新され、以下に示す更新値として出力する。
【００７３】
【数１３】
2008167379.tif 000015
【００７４】
対角化対象列でない第２列、第４列、第６列については、受信語ｒiをそのまま更新値として出力する。
【００７５】
以上より、演算量が減り、特にバリアブルノード演算も行う必要がない。
【００７６】
図９は、既存手法および本実施形態に係る手法におけるシミュレーションを用いた復号性能比較のグラフを示す図である。
【００７７】
図９は、ＲＳ（２０４，１８８）を想定した場合のフレームエラーレート（Ｆｒａｍｅ  Ｅｒｒｏｒ  Ｒａｔｅ）を示す図であって、Ａで示す曲線が既存手法の復号性能を示し、Ｂで示す曲線が本実施形態に手法における復号性能を示している。
なお、図３のような畳み込み符号と連接したシミュレーションモデルにおいて、図９のように、本発明による性能劣化はほとんど存在しないことが、シミュレーションにより示されている。
【００７８】
図１０は、本発明の実施形態に係るＡＢＰ復号器の信頼性伝播（ＢＰ）部の構成例を示す図である。また、図１１は、本発明の実施形態に係る復号方法を適用していない場合のＡＢＰ復号器の信頼性伝播（ＢＰ）部の構成例を示す図である。
【００７９】
図１０の信頼性伝播（ＢＰ）部３５は、更新列ＬＬＲ選択部３５１、チェックノード（ｃｈｅｃｋ  ｎｏｄｅ）演算部３５２、およびＬＬＲ更新部３５３を有している。
たとえば、ＲＳ（２０４，１８８）を想定した場合、全１６３２列のＬＬＲＳ４２が入力されると、更新列ＬＬＲ選択部３５１と更新する列のインデックスＳ４１により、更新したい列のＬＬＲＳ８７が選択される。
また、入力ＬＬＲＳ４４とパリティ検査行Ｓ４３を利用して、チェックノード演算部３５２でチェックノード演算が行われる。
ここで、更新したいバリアブルノード（ｖａｒｉａｂｌｅ  ｎｏｄｅ）は常に対角化対象列であるため、このバリアブルノードにつながっているチェックノードは必ず一つしか存在しない。つまり、一回の行入力とＬＬＲ入力で、その更新したいバリアブルノードに到来する全てのメッセージが演算されることになる。
よって、チェックノード演算で更新されたメッセージＳ４５と更新列ＬＬＲ選択部３５１で選択されたＬＬＲＳ４４をＬＬＲ更新部３５３で足し合わせれば、つまり、次の演算を行うことにより、更新列Ｓ４１のＬＬＲは更新される
【００８０】
【数１４】
2008167379.tif 000016
【００８１】
また、図１１の信頼性伝播（ＢＰ）部３５Ａは、更新列ＬＬＲ選択部３５１Ａ、チェックノード（ｃｈｅｃｋ  ｎｏｄｅ）演算部３５２Ａ、ＬＬＲ更新部３５３Ａ、バリアブルノード（ｖａｒｉａｂｌｅ  ｎｏｄｅ）演算入力選択部３５４、バリアブルノード演算部３５５、ｖ２ｃメッセージメモリ３５６、およびｃ２ｖメッセージメモリ３５７を有している。
【００８２】
更新列ＬＬＲ選択部３５１Ａは、更新する列インデックスＳ８１のＬＬＲを符号長分のＬＬＲを持つ入力Ｓ５２から選択する。
バリアブルノード演算入力選択部３５４は、信頼性伝播（ＢＰ）の繰り返し一回目は、入力ＬＬＲＳ５２を選択し、繰り返し二回目以降は、チェックノード演算後のメッセージＳ８５を選択する。
ｖ２ｃメッセージメモリ３５６は、バリアブルノードからチェックノードへのメッセージメモリとして機能し、ｃ２ｖメッセージメモリ３５７は、チェックノードからバリアブルノードへのメッセージメモリとして機能する。
【００８３】
図１１の信頼性伝播（ＢＰ）部３５Ａにおいて、まず、バリアブルノード演算部３５５では、チェックノード演算後のメッセージを利用して、バリアブルノード演算を行い、更新したメッセージＳ５５を出力する。
ただし、上記のとおり、繰り返し一回目は、この更新メッセージＳ５５は入力ＬＬＲＳ５２に設定される。バリアブルノード演算完了後、ｖ２ｃメッセージメモリ３５６からバリアブルノードからチェックノードへのメッセージを出力し、チェックノード演算部３５２Ａでチェックノード演算を行う。
その後、更新メッセージがｃ２ｖメッセージメモリ３５７に保持される。ｃ２ｖメッセージメモリ３５７からメッセージＳ５９がバリアブルノード演算部３５５に送られる。
以降、これを繰り返す。繰り返し数だけこれを繰り返した後、ＬＬＲ更新部３５３Ａで、更新したいＬＬＲＳ５７とメッセージＳ５９を利用してＬＬＲを更新し、出力する。
【００８４】
このように、図１１の信頼性伝播（ＢＰ）部３５Ａにおいては、チェックノード演算とバリアブルノード演算を両方行わなければならず、両者のためパリティ検査行とパリティ検査行列の列の両方必要になる。また、メッセージメモリは、パリティ検査行列の１の数のワード数が必要になる。
【００８５】
これに対して、本発明の実施形態に係る図１０の信頼性伝播（ＢＰ）部３５においては、バリアブルノード演算部やメッセージメモリは必要ない。したがって、回路規模の増大を防止することができる。
また、パリティ検査行のみ必要で列は必要ないため、図５に示すように、対角化部３３は、パリティ検査行Ｓ３７のみ信頼性伝播（ＢＰ）部３５に出力すればよく、一般的なメモリの構成上この実現は難しくない。また、これにより、計算量が削減され動作周波数の低減も可能である。
【００８６】
以上説明したように、本実施形態によれば、信頼性伝播（ＢＰ）の繰り返し数を一回に抑えることができ、また、信頼度を対角化対象列にのみ更新することにより、計算量を削減することができる。
特に、装置においては、信頼性伝播（ＢＰ）の繰り返し数が一回であるため、バリアブルノード演算を行う必要がなく、その結果、バリアブルノード演算装置を省け、回路規模を縮小できる。
また、バリアブルノード演算に必要なパリティ検査行列の列を対角化部から読み出す必要もなくなる。さらに、信頼度を対角化対象列にのみ更新すると、ＬＬＲを更新するバリアブルノードとつながっているチェックノードの数が１である。そのため、チェックノード演算更新メッセージと更新したい列のＬＬＲを直接ＬＬＲ更新部に入力すればＬＬＲ更新は完了することから、チェックノード演算部後段のメッセージメモリを設ける必要もなくなる。
【００８７】
なお、以上詳細に説明した方法は、上記手順に応じたプログラムとして形成し、ＣＰＵ等のコンピュータで実行するように構成することも可能である。
また、このようなプログラムは、半導体メモリ、磁気ディスク、光ディスク、フロッピー（登録商標）ディスク等の記録媒体、この記録媒体をセットしたコンピュータによりアクセスし上記プログラムを実行するように構成可能である。
【図面の簡単な説明】
【００８８】
【図１】パリティ検査行列Ｈｎｅｗに対応するタナーグラフである。
【図２】ＡＢＰ復号法を用いた繰り返し復号のフローチャートである。
【図３】デジタル信号受信機、たとえばデジタルテレビなどの誤り訂正システムにＡＢＰ復号器を用いた通信システムの構成例を示す図である。
【図４】ＭＡＰ復号が後段についたＡＢＰ復号器の構成例を示す図である。
【図５】ＡＢＰ復号器の復号装置の構成例を示す図である。
【図６】本発明の実施形態に係る適応的信頼性伝播（ＡＢＰ：ａｄａｐｔｉｖｅ  ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ）を用いた繰り返し復号のタナーグラフ上のメッセージの第１の流れを表す図である。
【図７】本発明の実施形態に係る適応的信頼性伝播（ＡＢＰ：ａｄａｐｔｉｖｅ  ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ）を用いた繰り返し復号のタナーグラフ上のメッセージの第２の流れを表す図である。
【図８】本発明の実施形態に係る適応的信頼性伝播（ＡＢＰ：ａｄａｐｔｉｖｅ  ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ）を用いた繰り返し復号のタナーグラフ上のメッセージの第３の流れを表す図である。
【図９】既存手法および本実施形態に係る手法におけるシミュレーションを用いた復号性能比較のグラフを示す図である。
【図１０】本発明の実施形態に係るＡＢＰ復号器の信頼性伝播（ＢＰ）部の構成例を示す図である。
【図１１】図１１は、本発明の実施形態に係る復号方法を適用していない場合のＡＢＰ復号器の信頼性伝播（ＢＰ）部の構成例を示す図である。
【符号の説明】
【００８９】
１０・・・通信システム、１１・・・ＲＳ符号化器、１２・・・インタリーバ、１３・・・畳み込み符号器、１４・・・畳み込み符号の軟出力復号器、１５・・・デインタリーバ、１６・・・ＡＢＰ繰り返し復号器、１７・・・チャネル、２０・・・復号器、２１・・・ＡＢＰ復号部、２２・・・限界距離（ＢＤ）復号部、２３・・・受信信頼度（ＬＬＲ）保持部、２４・・・ＭＡＰ復号部、３０・・・ＡＢＰ復号器、３１・・・ソート入力選択部、３２，３２Ａ・・・ソート部、３３・・・パリティ検査行列の対角化部、３４・・・信頼度（ＬＬＲ）保持部、３５・・・信頼性伝播（ＢＰ）部、３５１・・・更新列ＬＬＲ選択部、３５２・・・チェックノード（ｃｈｅｃｋ  ｎｏｄｅ）演算部、３５３・・・ＬＬＲ更新部、４１・・・バリアブルノード、４２・・・チェックノード。
【図１】
2008167379.tif 000017
【図２】
2008167379.tif 000018
【図３】
2008167379.tif 000019
【図４】
2008167379.tif 000020
【図５】
2008167379.tif 000021
【図６】
2008167379.tif 000022
【図７】
2008167379.tif 000023
【図８】
2008167379.tif 000024
【図９】
2008167379.tif 000025
【図１０】
2008167379.tif 000026
【図１１】
2008167379.tif 000027