(57)【要約】【課題】動作周波数を実現可能な周波数に抑えることが可能で、より少ない計算量で高速に、かつ小さい回路規模で信頼性の高い復号を行うことが可能な復号方法および復号装置、並びにプログラムを提供する。【解決手段】受信語の信頼度の大きさに従いソートし、その順番に対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を行って信頼度を更新し、その更新された値に対して、再び上記動作を繰り返す復号装置３０であって、受信値の信頼度（ＬＬＲ）の小さいシンボルに対応する列順に対角化されたパリティ検査行列を用いて信頼性伝播を行い、更新された信頼度に基づきこの動作を繰り返す内側繰り返し復号処理の際に、内側繰り返し二回目以降において、一部の列に限定してパリティ検査行列の対角化を行う処理部３２，３３を有する。【選択図】図６
2008167377.tif 000002
【特許請求の範囲】
【請求項１】
受信語の信頼度の大きさに従いソートし、その順番に対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を行って信頼度を更新し、その更新された値に対して、再び上記動作を繰り返す復号方法であって、
受信値の信頼度（ＬＬＲ）の小さいシンボルに対応する列順に対角化されたパリティ検査行列を用いて信頼性伝播を行い、更新された信頼度に基づきこの動作を繰り返す内側繰り返し復号処理ステップを有し、
前記内側繰り返し復号処理ステップにおいて、
内側繰り返し二回目以降において、一部の列に限定してパリティ検査行列の対角化を行う
復号方法。
【請求項２】
内側繰り返し二回目以降において、新しく対角化対象から外れた列に対応する要行は過去の要行リストから外し、前回の対角化後の行列を用いて、新たに対角化対象となった列インデックスについてのみ対角化を行う
請求項１記載の復号方法。
【請求項３】
内側繰り返し二回目以降において、対角化の対象となる列インデックスと対角化の対象とはならない列インデックスの入れ替えを限られた数列同士に限定して行う
請求項２記載の復号方法。
【請求項４】
内側繰り返し二回目以降において、前繰り返しの際に対角化対象となった列インデックスの信頼度が更新されて、新たにソートする際、その更新された信頼度の大きい数列と、前繰り返しの際の対角化対象から外れた列インデックスのうち信頼度が小さい数列を比較し、その内信頼度の小さい数列を対角化対象に加え、信頼度の大きい数列を対角化対象から外す
請求項３記載の復号方法。
【請求項５】
内側繰り返し二回目以降において、前繰り返しの際に対角化対象となった列インデックスのうち更新された信頼度が大きい数列を強制的に対角化対象から外し、前繰り返しの際の対角化対象から外れた列インデックスのうち信頼度の小さい数列を強制的に新しい対角化対象列とする
請求項３記載の復号方法。
【請求項６】
受信語の信頼度の大きさに従いソートし、その順番に対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を行って信頼度を更新し、その更新された値に対して、再び上記動作を繰り返す復号装置であって、
受信値の信頼度（ＬＬＲ）の小さいシンボルに対応する列順に対角化されたパリティ検査行列を用いて信頼性伝播を行い、更新された信頼度に基づきこの動作を繰り返す内側繰り返し復号処理の際に、内側繰り返し二回目以降において、一部の列に限定してパリティ検査行列の対角化を行う処理部を有する
復号装置。
【請求項７】
前記処理部は、
内側繰り返し二回目以降において、新しく対角化対象から外れた列に対応する要行は過去の要行リストから外し、前回の対角化後の行列を用いて、新たに対角化対象となった列インデックスについてのみ対角化を行う
請求項６記載の復号装置。
【請求項８】
前記処理部は、
内側繰り返し二回目以降において、対角化の対象となる列インデックスと対角化の対象とはならない列インデックスの入れ替えを限られた数列同士に限定して行う
請求項７記載の復号装置。
【請求項９】
前記処理部は、
内側繰り返し二回目以降において、前繰り返しの際に対角化対象となった列インデックスの信頼度が更新されて、新たにソートする際、その更新された信頼度の大きい数列と、前繰り返しの際の対角化対象から外れた列インデックスのうち信頼度が小さい数列を比較し、その内信頼度の小さい数列を対角化対象に加え、信頼度の大きい数列を対角化対象から外す
請求項８記載の復号装置。
【請求項１０】
前記処理部は、
内側繰り返し二回目以降において、前繰り返しの際に対角化対象となった列インデックスのうち更新された信頼度が大きい数列を強制的に対角化対象から外し、前繰り返しの際の対角化対象から外れた列インデックスのうち信頼度の小さい数列を強制的に新しい対角化対象列とする
請求項８記載の復号装置。
【請求項１１】
受信語の信頼度の大きさに従いソートし、その順番に対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を行って信頼度を更新し、その更新された値に対して、再び上記動作を繰り返す復号処理において、
受信値の信頼度（ＬＬＲ）の小さいシンボルに対応する列順に対角化されたパリティ検査行列を用いて信頼性伝播を行い、更新された信頼度に基づきこの動作を繰り返す内側繰り返し復号処理ステップで、
内側繰り返し二回目以降において、一部の列に限定してパリティ検査行列の対角化を行う処理を
コンピュータに実行させるプログラム。
【請求項１２】
内側繰り返し二回目以降において、新しく対角化対象から外れた列に対応する要行は過去の要行リストから外し、前回の対角化後の行列を用いて、新たに対角化対象となった列インデックスについてのみ対角化を行う処理をコンピュータに実行させる
請求項１１記載のプログラム。
【請求項１３】
内側繰り返し二回目以降において、対角化の対象となる列インデックスと対角化の対象とはならない列インデックスの入れ替えを限られた数列同士に限定して行う処理をコンピュータに実行させる
請求項１２記載のプログラム。
【請求項１４】
内側繰り返し二回目以降において、前繰り返しの際に対角化対象となった列インデックスの信頼度が更新されて、新たにソートする際、その更新された信頼度の大きい数列と、前繰り返しの際の対角化対象から外れた列インデックスのうち信頼度が小さい数列を比較し、その内信頼度の小さい数列を対角化対象に加え、信頼度の大きい数列を対角化対象から外す処理をコンピュータに実行させる
請求項１３記載のプログラム。
【請求項１５】
内側繰り返し二回目以降において、前繰り返しの際に対角化対象となった列インデックスのうち更新された信頼度が大きい数列を強制的に対角化対象から外し、前繰り返しの際の対角化対象から外れた列インデックスのうち信頼度の小さい数列を強制的に新しい対角化対象列とする処理をコンピュータに実行させる
請求項１３記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、たとえば代数的手法を用いた誤り訂正符号技術を実現するための回路およびプログラム記憶媒体に関して適用される復号方法および復号装置、並びにプログラムに関するものである。
【背景技術】
【０００２】
代数幾何符号、たとえばリードソロモン（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ）符号やその部分体部分符号としてのＢＣＨ符号には、その代数的性質を利用した、性能・計算コスト共に良い復号法が知られている。
【０００３】
たとえば、符号長ｎ、情報長ｋ、定義体ＧＦ（ｑ）（ｑ＝ｐｍ，ｐ：素数）、最小距離ｄ＝ｎ−ｋのＲｅｅｄ−Ｓｏｌｏｍｏｎ符号をＲＳ（ｎ，ｋ）とすると、硬判定受信語をハミング（Ｈａｍｍｉｎｇ）距離が最小の符号語に復号する最小距離復号（通常復号）はｔ＜ｄ／２を満たすｔ個の誤りシンボルの訂正を保証するものとして良く知られている。
【０００４】
また、グルスワミ−スーダン（Ｇｕｒｕｓｗａｍｉ−Ｓｕｄａｎ）によるリスト復号（以下Ｇ−Ｓリスト復号）は、ｔ＜√ｎｋを満たすｔ個の誤りシンボルの訂正を保証している（非特許文献１参照）。
【０００５】
Ｇｕｒｕｓｗａｍｉ−Ｓｕｄａｎのリスト復号の拡張版として軟判定受信語を用いたコータ−バルディ（Ｋｏｅｔｔｅｒ−Ｖａｒｄｙ）によるリスト復号（以下Ｋ−Ｖリスト復号）は、Ｇｕｒｕｓｗａｍｉ−Ｓｕｄａｎ同様に（１）受信情報から各シンボルの信頼性を算出、（２）信頼性から２変数多項式補間条件の抽出、（３）２変数多項式の補間、（４）補間多項式の因数分解を行い復号語リスト作成、の４つの手順により構成され、硬判定復号時に比べてより高い性能を持つことが知られている（非特許文献２参照）。
【０００６】
また、リエンコード（Ｒｅ−ｅｎｃｏｄｅ）により、その計算コストも現実的な範囲まで削減できることが知られている（非特許文献３参照）。
【０００７】
一方、線形符号としては、信頼性伝播（ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を用いた繰り返し復号により限界性能に近い高性能を得られる低密度パリティ検査符号（Ｌｏｗ  ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ−ｃｈｅｃｋ  ｃｏｄｅ，ＬＤＰＣ符号）が昨今注目されている（非特許文献４参照）。
【０００８】
ＬＤＰＣ符号に用いられる信頼性伝播（ＢＰ）は、一般に低密度なパリティ検査行列を持つ線形符号にしか有効でないことが理論的に知られており、また、Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号やＢＣＨ符号のパリティ検査行列を低密度化することはＮＰ−ｈａｒｄであることが知られている（非特許文献５参照）。
【０００９】
よって、Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号やＢＣＨ符号に信頼性伝播（ＢＰ）を適用することは困難であるとされてきた。
【００１０】
しかし、２００４年、受信語の信頼性に応じて対角化を行ったパリティ検査行列を用いてＲｅｅｄ−Ｓｏｌｏｍｏｎ符号やＢＣＨ符号、その他低密度でないパリティ検査行列を持つ線形符号への信頼性伝播（ＢＰ）の適用が効果的であることがナラヤナン(Ｎａｒａｙａｎａｎ)等によって紹介された（非特許文献６参照）。
【００１１】
この手法は、適応的信頼性伝播（ＡＢＰ：Ａｄａｐｔｉｖｅ  Ｂｅｌｉｅｆ  Ｐｒｏｐａｇａｔｉｏｎ）復号と呼ばれる。以下、このＡＢＰ復号法について説明する。
【００１２】
たとえば、符号長ｎ＝６、情報長ｋ＝３、符号化率ｒ＝１／２の符号で、以下の３×６行列Ｈをパリティ検査行列として持つような線形符号Ｃを考える。
【００１３】
【数１】
2008167377.tif 000003
【００１４】
符号空間Ｃは、次のように表される。
【００１５】
【数２】
2008167377.tif 000004
【００１６】
ある符号語があるチャネル、たとえばＢＰＳＫ変調＋ＡＷＧＮチャネル（Ａｄｄｉｔｉｖｅ  Ｗｈｉｔｅ  Ｇａｕｓｓｉａｎ  Ｎｏｉｓｅチャネル）を通った後、次のような受信語ｒとして受信機が受け取ったとする。
【００１７】
【数３】
2008167377.tif 000005
【００１８】
このとき、受信値の各絶対値の大きさは受信語の信頼性の高さを表す。つまり、信頼性の低い順に番号をつけると以下のようになる。
【００１９】
【数４】
2008167377.tif 000006
【００２０】
次に、信頼性の低いシンボルに対応する列より順にパリティ検査行列Ｈの対角化を行う。この例においては、信頼性の低いシンボルに対応する列は順に第３列、第５列、第１列、第４または第６列、第２列となるので、その優先順位に従ってＨの対角化を行う。
【００２１】
【数５】
2008167377.tif 000007
【００２２】
【数６】
2008167377.tif 000008
【００２３】
【数７】
2008167377.tif 000009
【００２４】
対角化を試みた列がそれ以前に対角化した列と線形従属であった場合は、その列はそのまま残し、次の順位の列で対角化を試みる。
このようにして行列Ｈのランク分対角化が行われた結果得られる新たなパリティ検査行列Ｈｎｅｗを用いて、信頼性伝播（ＢＰ）による信頼性の更新を行う。
【００２５】
図１はパリティ検査行列Ｈｎｅｗに対応するタナーグラフである。
信頼性伝播（ＢＰ）はタナーグラフのエッジに沿ってメッセージを行き来させることによって実現される。
行列の各列に対応するノードを可変（ｖａｒｉａｂｌｅ：バリアブル）ノード１、各行に対応するノードを検査（ｃｈｅｃｋ：チェック）ノード２と呼ぶ。
【００２６】
ｉ番目のバリアブルノードからｊ番目のチェックノードへのメッセージをＱi,j、ｊ番目のチェックノードからｉ番目のバリアブルノードへのメッセージをＲｉ,j、さらにｉ番目のバリアブルノードに連接するチェックノードのインデックス集合をＪ（ｉ）、ｊ番目のチェックノードに連接するバリアブルノードのインデックス集合をＩ（ｊ）とした場合、それぞれの更新式は以下のようになる。
【００２７】
【数８】
2008167377.tif 000010
【００２８】
ここで、θはバーティカルステップダンピングファクタ（ｖｅｒｔｉｃａｌ  ｓｔｅｐ  ｄａｍｐｉｎｇ  ｆａｃｔｏｒ）と呼ばれる係数を示し、０＜θ≦１なる条件を満足する。Ｑi,jの初期値はｒjが設定され、外部情報（ｅｘｔｒｉｎｓｉｃ  ｉｎｆｏｒｍａｔｉｏｎ）Λｉｘ更新は次式により行われる。
【００２９】
【数９】
2008167377.tif 000011
【００３０】
さらに、各符号ビットのＬＬＲΛｉｑの更新は、次式により行われる。
【００３１】
【数１０】
2008167377.tif 000012
【００３２】
ここで、α１は適応的信頼性伝播ダンピングファクタ（ａｄａｐｔｉｖｅ  ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ  ｄａｍｐｉｎｇ  ｆａｃｔｏｒ）と呼ばれる係数を示し、０＜α１≦１なる条件を満足する。
この信頼性伝播（ＢＰ）によるＬＬＲの更新は事前に用意された繰り返し停止条件を満たすまで、たとえば最大繰り返し数ＩｔＨに達成するまで繰り返される。
また、ＬＬＲを更新する列は、全ての列を対象とせずとも一部の列、たとえば対角化の対象となった列についてのみ行ってもよい。
【００３３】
信頼性伝播（ＢＰ）によって更新されたＬＬＲの信頼性を用いて、つまり、ＬＬＲの絶対値の大きさを信頼性として、信頼性の低いシンボルに対応する列順に対角化を行うことにより、新たな信頼性伝播（ＢＰ）による繰り返し復号を行うことができる。
これを内側繰り返し復号と呼ぶ。このＬＬＲの更新は事前に用意された内側繰り返し復号停止条件ＳＣ１を満たすまで繰り返される。
【００３４】
さらに、パリティ検査行列の列の対角化優先順位の初期値として、受信値の信頼性順以外の順位を複数用意する。複数の順位を用いて、シリアルもしくはパラレルに繰り返し内側繰り返し復号を行う。
これを外側繰り返し復号と呼ぶ。このＬＬＲ更新は事前に用意された外側繰り返し復号停止条件ＳＣ２を満たすまで繰り返される。
【００３５】
以上のＡＢＰ（ａｄａｐｔｉｖｅ  ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ）手順により繰り返し更新されたＬＬＲを入カとして、復号器により復号を行う。
今、対象となる線形符号がＲｅｅｄ−Ｓｏｌｏｍｏｎ符号であった場合、繰り返し復号停止条件ＳＣ１、ＳＣ２として、たとえば以下のものが考えられる。
【００３６】
（Ａ）  Ｈ・ｄ  ＝＝  ０または繰り返し数ｔ≧Ｎ、
（Ｂ）  限界距離復号成功または繰り返し数ｔ≧Ｎ、
（Ｃ）  Ｋｏｅｔｔｅｒ−Ｖａｒｄｙ軟判定リスト復号成功または繰り返し数ｔ≧Ｎ。
【００３７】
ここで、ｄ＝（ｄ１，ｄ２，・・・，ｄ６）はΛｉの硬判定結果、ｄｉ＝｛Λｉｑ＞０なら１，Λｉｑ≦０なら０｝であり、Ｎは事前に決めた最大繰り返し回数である。
また、復号方法として、たとえば以下のものが考えられる。
【００３８】
（ａ）  硬判定復号
（ｂ）  限界距離復号
（ｃ）  Ｋｏｅｔｔｅｒ−Ｖａｒｄｙ軟判定リスト復号
【００３９】
図２は、ＡＢＰ復号法を用いた繰り返し復号のフローチャートである。
【００４０】
受信語の信頼性順の探索を行い（ＳＴ１）、順序変換を行う（ＳＴ２）。
変換した順序に応じてパリティ検査行列の対角化を行い（ＳＴ３）、このパリティ検査行列を用いて信頼性伝播（ＢＰ）を行う（ＳＴ４）。
次に、ＬＬＲを計算し（ＳＴ５）、計算したＬＬＲの信頼性順を探索し（ＳＴ６）、復号を行い、復号語をリストへ追加する（ＳＴ７）。
そして、繰り返し復号停止条件Ｎ１，Ｎ２を満足するまで以上の処理を繰り返す（ＳＴ８、ＳＴ９）。
そして、復号語を１つ選択する（ＳＴ１０）。
【００４１】
【非特許文献１】Ｖ．Ｇｕｒｕｓｗａｍｉ，Ｍ．Ｓｕｄａｎ，Ｉｍｐｒｏｖｅ  ｄｅｃｏｄｉｎｇ  ｏｆ  Ｒｅｅｄ−Ｓｏｌｏｍｏｎ  ａｎｄ  Ａｌｇｅｂｒａｉｃ−Ｇｅｏｍｅｔｒｙ  ｃｏｄｅｓ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ｖｏｌ．４５，ｐｐ．１７５７−１７６７，１９９９
【非特許文献２】Ｒ．Ｋｏｅｔｔｅｒ，Ａ．Ｖａｒｄｙ，Ａｌｇｅｂｒａｉｃ  ｓｏｆｔ−ｄｅｃｉｓｉｏｎ  ｄｅｃｏｄｉｎｇ  ｏｆ  Ｒｅｅｄ−Ｓｏｌｏｍｏｎ  ｃｏｄｅｓ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，２００１
【非特許文献３】Ｒ．Ｋｏｅｔｔｅｒ，Ｊ．Ｍａ，Ａ．Ｖａｒｄｙ，Ａ，Ａｈｍｅｄ，Ｅｆｆｃｉｅｎｔ  Ｉｎｔｅｒｐｏｌａｔｉｏｎ  ａｎｄ  Ｆａｃｔｏｒｉｚａｔｉｏｎ  ｉｎ  Ａｌｇｅｂｒａｉｃ  Ｓｏｆｔ−Ｄｅｃｉｓｉｏｎ  Ｄｅｃｏｄｉｎｇ  ｏｆ  Ｒｅｅｄ−Ｓｏｌｏｍｏｎ  ｃｏｄｅｓ，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＩＳＩＴ２００３
【非特許文献４】Ｄ．ＭａｃＫａｙ，Ｇｏｏｄ  Ｅｒｒｏｒ−Ｃｏｒｒｅｃｔｉｎｇ  Ｃｏｄｅｓ  Ｂａｓｅｄ  ｏｎ  Ｖｅｒｙ  Ｓｐａｒｓｅ  Ｍａｔｒｉｃｅｓ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，１９９９
【非特許文献５】Ｂｅｒｌｅｋａｍｐ，Ｒ．ＭｃＥｌｉｅｃｅ，Ｈ．ｖａｎ  Ｔｉｌｂｏｒｇ，Ｏｎ  ｔｈｅ  ｉｎｈｅｒｅｎｔ  ｉｎｔｒａｃｔａｂｉｌｉｔｙ  ｏｆ  ｃｅｒｔａｉｎ  ｃｏｄｉｎｇ  ｐｒｏｂｌｅｍｓ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ｖｏｌ．２４，ｐｐ．３８４−３８６，Ｍａｙ，１９７８）。
【非特許文献６】Ｊｉｎｇ  Ｊｉａｎｇ，Ｋ．Ｒ．Ｎａｒａｙａｎ，Ｓｏｆｔ  Ｄｅｃｉｓｉｏｎ  Ｄｅｃｏｄｉｎｇ  ｏｆ  ＲＳ  Ｃｏｄｅｓ  Ｕｓｉｎｇ  Ａｄａｐｔｉｖｅ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ  Ｍａｔｒｉｃｅｓ，Ｐｒｏｃｅｅｄｉｎｇ  ｏｆ  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ  ２００４
【発明の開示】
【発明が解決しようとする課題】
【００４２】
ところで、上述の技術では、受信ＬＬＲの大きさ順に列インデックスをソートする作業、および信頼性伝播（ＢＰ）によって更新されたＬＬＲを用いて再び列インデックスをソートしなおす作業を行うソート装置が必要となる。
しかし、このソート装置をどうやって実現するかについては特に提案されていない。
【００４３】
また、ソートを行った後に、後段の対角化装置が望むタイミングで列インデックスを出力する必要や、更新されたＬＬＲをソートする際に、一部の列のみＬＬＲが更新され、更新されたインデックスのみ入力される場合は、更新前のソートされたインデックス順の中にＬＬＲが更新されたインデックスを反映していく必要があるなど、様々な制約条件がある。
【００４４】
さらに、インデックスをソートする場合、ＬＬＲが同じインデックスについてはその入力順は特に気にする必要がないといったＡＢＰ復号特有の特徴がある。
さらにまた、ソートの方法には、選択整列法、挿入整列法、シェルソートなど様々な方法がある。
以上から、上記制約条件やＡＢＰ復号特有の特徴に適したソート装置とその方法を決めることは簡単ではない。
【００４５】
また、実際には、ＲＳ（204，188）といったＨよりも符号長の大きいＲＳ符号を対象としたシステムが多く、これについて、既存の技術を用いて現実的な動作周波数で実現することは不可能である。
【００４６】
図３は、ＡＢＰ復号装置の繰り返し毎のフローの一列を示す図である。
【００４７】
受信語が到来したらそれを信頼度の大きさに従いソートし、信頼度の小さい１２８列についてパリティ検査行列Ｈの対角化を行い、対角化後のパリティ検査行列をＨ１とする。
このＨ１を利用して信頼性伝播（ＢＰ）を行う。この場合、対角化対象となった１２８列のみ信頼度を更新する。繰り返し二回目以降も同様に、更新信頼度をソートし直し、信頼度の小さい１２８列についてパリティ検査行列Ｈを対角化し、信頼性伝播（ＢＰ）を行うことを繰り返す。
【００４８】
以上のようなＡＢＰ復号装置を実現したい場合、以下のように所要動作周波数を想定できる。
たとえば、ＲＳ（240，188）を想定し、内側繰り返し復号を装置で実現することを想定した場合、内側繰り返し数を１０回、ＬＬＲの更新を対角化対象となった列１２８列にのみ限定し、信頼性伝播（ＢＰ）の繰り返し数を１回にする条件において、ＡＢＰ復号するための必要なクロックサイクル数は、次のようになる。
【００４９】
【数１１】
2008167377.tif 000013
【００５０】
ここで、Ｔ１は繰り返し一回目に必要とするクロックサイクル数、Ｔ２は繰り返し二回目以降に必要とするクロックサイクル数を示している。
Ｔ１は、次式で示すようなクロックサイクル数が必要となる。
【００５１】
【数１２】
2008167377.tif 000014
【００５２】
ここで、Ｔsort1は、ソートに必要とするクロックサイクル数を示し、逆写像ソートを利用した場合、最低でも入力ビット数１６３２クロックサイクルが必要となる。また、Ｔdiagは、対角化に必要とするクロックサイクル数を示し、一回の行読出しで要探索と掃き出しを一度に行い、かつ並列に複数列、たとえばここでは４列の基本変形を行う対角化装置を利用した場合、今回R列パラレルに基本変形すると、最低でも１２８×１２８／４＝４０９６クロックサイクル数必要とする。また、Ｔbpは、信頼性伝播（ＢＰ）に必要とするクロックサイクル数を示し、対角化対象となった１２８列のみＬＬＲ更新を行うので、最低１２８クロックサイクル数必要となる。
【００５３】
以上より、Ｔ１は次のようになる
【００５４】
【数１３】
2008167377.tif 000015
【００５５】
また、内側繰り返し二回目以降のＴ２は次のようになる。
【００５６】
【数１４】
2008167377.tif 000016
【００５７】
ここで、Ｔsort2は、内側繰り返し二回目以降のソートに必要とするクロックサイクル数を示し、ＬＬＲが更新される列インデックスが１２８列とすると、Ｔsort2＝１２８と考えうる。
しかし、繰り返し二回目以降は、前繰り返しの信頼性伝播（ＢＰ）により、毎クロックサイクル１列ずつ更新された信頼度をソート装置に入力すれば、信頼性伝播（ＢＰ）とソートはほぼ同時に行うことが可能なためＴsort2＝０とすることができる。つまり、Ｔ２は次のようになる。
【００５８】
【数１５】
2008167377.tif 000017
【００５９】
以上より、Ｔは次式で与えられる。
【００６０】
【数１６】
2008167377.tif 000018
【００６１】
ここで、６４[Mbps]のデータをＡＢＰ復号する場合を考えると、動作周波数は次式で与えられる。
【００６２】
【数１７】
2008167377.tif 000019
【００６３】
このように、１．７２[GHｚ]の動作周波数が必要となり、既存の技術では現実的ではない。
【００６４】
本発明は、動作周波数を実現可能な周波数に抑えることが可能で、より少ない計算量で高速に、かつ小さい回路規模で信頼性の高い復号を行うことが可能な復号方法および復号装置、並びにプログラムを提供することにある。
【課題を解決するための手段】
【００６５】
本発明の第１の観点は、受信語の信頼度の大きさに従いソートし、その順番に対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を行って信頼度を更新し、その更新された値に対して、再び上記動作を繰り返す復号方法であって、受信値の信頼度（ＬＬＲ）の小さいシンボルに対応する列順に対角化されたパリティ検査行列を用いて信頼性伝播を行い、更新された信頼度に基づきこの動作を繰り返す内側繰り返し復号処理ステップを有し、前記内側繰り返し復号処理ステップにおいて、内側繰り返し二回目以降において、一部の列に限定してパリティ検査行列の対角化を行う。
【００６６】
本発明の第２の観点は、受信語の信頼度の大きさに従いソートし、その順番に対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を行って信頼度を更新し、その更新された値に対して、再び上記動作を繰り返す復号装置であって、受信値の信頼度（ＬＬＲ）の小さいシンボルに対応する列順に対角化されたパリティ検査行列を用いて信頼性伝播を行い、更新された信頼度に基づきこの動作を繰り返す内側繰り返し復号処理の際に、内側繰り返し二回目以降において、一部の列に限定してパリティ検査行列の対角化を行う処理部を有する。
【００６７】
好適には、前記処理部は、内側繰り返し二回目以降において、新しく対角化対象から外れた列に対応する要行は過去の要行リストから外し、前回の対角化後の行列を用いて、新たに対角化対象となった列インデックスについてのみ対角化を行う。
【００６８】
好適には、前記処理部は、内側繰り返し二回目以降において、対角化の対象となる列インデックスと対角化の対象とはならない列インデックスの入れ替えを限られた数列同士に限定して行う。
【００６９】
好適には、前記処理部は、内側繰り返し二回目以降において、前繰り返しの際に対角化対象となった列インデックスの信頼度が更新されて、新たにソートする際、その更新された信頼度の大きい数列と、前繰り返しの際の対角化対象から外れた列インデックスのうち信頼度が小さい数列を比較し、その内信頼度の小さい数列を対角化対象に加え、信頼度の大きい数列を対角化対象から外す。
【００７０】
好適には、前記処理部は、内側繰り返し二回目以降において、前繰り返しの際に対角化対象となった列インデックスのうち更新された信頼度が大きい数列を強制的に対角化対象から外し、前繰り返しの際の対角化対象から外れた列インデックスのうち信頼度の小さい数列を強制的に新しい対角化対象列とする。
【００７１】
本発明の第３の観点は、受信語の信頼度の大きさに従いソートし、その順番に対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を行って信頼度を更新し、その更新された値に対して、再び上記動作を繰り返す復号処理において、受信値の信頼度（ＬＬＲ）の小さいシンボルに対応する列順に対角化されたパリティ検査行列を用いて信頼性伝播を行い、更新された信頼度に基づきこの動作を繰り返す内側繰り返し復号処理ステップで、内側繰り返し二回目以降において、一部の列に限定してパリティ検査行列の対角化を行う処理をコンピュータに実行させるプログラムである。
【００７２】
本発明によれば、内側繰り返し二回目以降の対角化対象となる列と対角化対象とならない列の集合の分割方法を、前繰り返しの両集合の一部の入れ替えに限定し、そのときに入れ替えられ新しく対角化対象となった列についてのみ前対角化で更新されたパリティ検査行列を対象として対角化を行う。
【発明の効果】
【００７３】
本発明によれば、動作周波数を実現可能な周波数に抑えることが可能で、より少ない計算量で高速に、かつ小さい回路規模で信頼性の高い復号を行うことができる利点がある。
【発明を実施するための最良の形態】
【００７４】
以下、本発明の実施形態を図面に関連付けて説明する。
【００７５】
本発明の実施形態に係る復号装置は、代数的手法を用いた誤り訂正符号技術を実現するための回路、たとえば適応的信頼性伝播（Ａｄａｐｔｉｖｅ  Ｂｅｌｉｅｆ  Ｐｒｏｐａｇａｔｉｏｎ：ＡＢＰ）復号器に応用できる。
ＡＢＰ復号は、リードソロモン（Ｒｅａｄ−Ｓｏｌｏｍｏｎ：ＲＳ）符号やＢＣＨ符号、その他低密度でないパリティ検査行列を持つ線形符号に対する復号法であり、ある伝送路から符号語を受信すると、その受信語をより信頼できる値に更新する。
【００７６】
以下、ＡＢＰ復号における復号装置の通信システム上の位置づけについて説明した後、本実施形態に係る復号装置の具体的な構成および機能について説明する。
【００７７】
図４は、デジタル信号受信機、たとえばデジタルテレビなどの誤り訂正システムにＡＢＰ復号器を用いた通信システムの構成例を示す図である。
【００７８】
本通信システム１０は、図４に示すように、ＲＳ符号化器１１、インタリーバ１２、畳み込み符号器１３、畳み込み符号の軟出力復号器１４、デインタリーバ１５、ＲＳ符号の既知情報付きＡＢＰ繰り返し復号器１６、およびチャネル１７を有する。
【００７９】
本通信システム１０では、ＲＳ符号化、畳み込み符号化された送信語に対して、畳み込み符号の軟出力復号をした後にＡＢＰ復号を行っている。
ここで言う畳み込み符号の軟出力復号とは、たとえばＢＣＪＲアルゴリズムやＳＯＶＡによる復号のことである。
ＡＢＰ復号器１６においては、ＡＢＰによる信頼性の更新後、硬判定後限界距離復号、リスト復号、もしくは、軟値をそのまま入力として軟判定リスト復号を行う。
【００８０】
図５は、ＭＡＰ復号が後段についたＡＢＰ復号器の構成例を示す図である。
この復号器２０は、図５に示すように、ＡＢＰ復号部２１、限界距離（ＢＤ）復号部２２、受信信頼度（ＬＬＲ）保持部２３、およびＭＡＰ復号部２４を有している。
【００８１】
復号器２０においては、ＡＢＰ復号部２１による信頼性（ＬＬＲ）の更新後、硬判定してＢＤ復号部２２において、限界距離復号を行い、この結果をリストに集め、最終的にＭＡＰ復号部２４において最大事後確率復号（Ｍａｘｉｍｕｍ  ａ  ｐｏｓｔｅｒｉｏｒｉ  Ｐｒｏｂａｂｉｌｉｔｙ：ＭＡＰ）復号を行う。
【００８２】
図６は、ＡＢＰ復号器の復号装置の構成例を示す図である。
【００８３】
図５のＡＢＰ復号器３０は、図４のＡＢＰ復号器１６や図５のＡＢＰ復号部２１に適用可能であり、ソート入力選択部３１、ソート部３２、パリティ検査行列の対角化部３３、信頼度（ＬＬＲ）保持部３４、および信頼性伝播（ＢＰ）部３５を有している。
なお、ソート部３２および対角化部３３により、本実施形態に係る処理部が構成される。
【００８４】
ＡＢＰ復号器３０においては、入力として、受信ＬＬＲＳ３２が入力される。
列インデックスＳ３１は、入力された受信ＬＬＲの符号語の始まりからカウンタで０、１、２、３、、とカウントアップされた値を生成し利用する。
ソート入力選択部３１で、初回は、列インデックスＳ３１と受信ＬＬＲＳ３２を選択し、繰り返し二回目以降は信頼性伝播（ＢＰ）後、更新ＬＬＲＳ４０とその列インデックスＳ３９を選択する。
【００８５】
図５に示すように、受信語が入力されたら、まず、ソート部３２において、その信頼度（ＬＬＲ）の大きさに応じて列インデックスのソートを行う。
次に、信頼度の低いシンボルに対応する列より順に、対角化部３３でパリティ検査行列の対角化を行う。
最後に、対角化されたパリティ検査行列を用いて、信頼性伝播（ＢＰ）を行うことにより、値が更新される。
更新された値に対して、再びソート、対角化、信頼性伝播（ＢＰ）を行う。繰り返し数が予め決められており、その繰り返し数だけこれを繰り返す。
【００８６】
この復号器３０の処理部を構成するソート部３２において、本発明の実施形態に係るデータソート装置を適用することが可能である。
【００８７】
＜第１実施形態＞
図７は、本発明の第１の実施形態に係るＡＢＰ復号器のデータソート装置の構成例を示す図である。
【００８８】
本第１の実施形態に係るデータソート装置３２Ａは、図７に示すように、アドレスがデータの大きさに対応し、インデックスメモリ３２１、バッファとしてのバケツメモリ３２２に加えて、第１書込み読出しアドレス選択部３２３、第２書込み読出しアドレス選択部３２４、書込みデータ選択部３２５、および出力インデックス選択部３２６を有している。
【００８９】
インデックスメモリ３２１は、アドレス入力ＡＤに第２書込み読出しアドレス選択部３２４による第２書込み読出しアドレスＳ４６を受け、入力ＩＤＡＴＡにバケツメモリ３２２によるバケツ先頭インデックスＳ４５を受けて、あるインデックスをアドレスとして指定すると、データが同じ大きさである別のインデックスを保持し、出力ＯＤＡＴＡから読出しインデックスＳ１７を出力インデックス選択部３２８および書込みデータ選択部３２５に出力する。
【００９０】
バケツメモリ３２２は、アドレス入力ＡＤに第１書込み読出しアドレス選択部３２３による第１書込み読出しアドレスＳ４４を受け、入力ＩＤＡＴＡに書き込みデータ選択部３２５による書込みインデックスＳ４９を受けて各アドレスにそのデータの代表となるインデックスを持ち、出力ＯＤＡＴＡからバケツ先頭インデックスＳ４５をインデックスメモリ３２１および出力インデックス選択部３２６に出力する。
【００９１】
第１書込み読出しアドレス選択部３２３は、図示しない制御系の制御の下、入力データＳ４１と読出しデータＳ４２のいずれかを選択し、第１書込み読出しアドレスＳ４４としてバケツメモリ３２２のアドレス入力ＡＤに出力する。
【００９２】
第２書込み読出しアドレス選択部３２４は、図示しない制御系の制御の下、入力インデックスＳ４３と出力インデックス選択部３２６から出力される出力インデックスＳ４８のいずれかを選択し、第２書込み読出しアドレスＳ４６としてインデックスメモリ３２１のアドレス入力ＡＤに出力する。
【００９３】
書込みデータ選択部３２５は、図示しない制御系の制御の下、入力インデックスＳ４３とインデックスメモリ３２１による読出しインデックスＳ４７のいずれかを選択し、書込みインデックスＳ４９としてバケツメモリ３２２の入力ＩＤＡＴＡに出力する。
書込みデータ選択部３２５は、入力時に入力インデックスＳ４３を、出力時にインデックスメモリ３２１の読出しインデックスＳ４７を選択するように制御される。
【００９４】
出力インデックス選択部３２６は、図示しない制御系の制御の下、バケツメモリ３２２から出力されるバケツ先頭インデックスＳ４５とインデックスメモリ３２１から出力される読出しインデックスＳ４７のいずれかを選択し、出力インデックＳ４８として次段の対角部３３および第２書込み読出しアドレス選択部３２４に出力する。
【００９５】
以下、第１の実施形態に係るデータソート装置３２Ａの動作例を図７〜図１７に関連付けて説明する。
ここでは、ソート部３２において、符号長ｎ＝６、情報長ｋ＝３、符号化率ｒ＝1/2の符号で、３×６-行列Ｈをパリティ検査行列として持つような線形符号Ｃを復号する場合を考える。この場合、ソート部３２では、入力をソートした後、対角化対象列３列のインデックスを出力する。
【００９６】
図７において、入力データＳ１１にはＬＬＲが、入力インデックスＳ４３には列インデックスが入力される。読出しデータＳ４２はソート装置内部で生成するパラメータである。
入力データＳ４１と入力インデックスＳ４３が入力完了すると、データの大きさ順に並びなおされた列インデックスが出力列インデックスとして読み出される。入力データＳ４１は、ＬＬＲの絶対値どうしを比較するので、入力後絶対値に直されるものとする。
データＳ４１、インデックスＳ４３が入力された時は、これらをインデックスメモリ３２１、バケツメモリ３２２に書き込む作業を行う。
まず、バケツメモリ３２２の初期値として存在しないインデックスを保持しておく。この場合は、列インデックスが０〜５まで存在するとして、存在しないインデックスは６としておく。入力が開始されると、入力データＳ４１を読出しアドレスＳ４４としてバケツメモリ３２２から読み出したインデックスＳ４５を、入力インデックスＳ４３をアドレスＳ４６としてインデックスメモリ３２１に書き込む。
また、入力データＳ４１をアドレスＳ４４として入力インデックスＳ４３をバケツメモリ３２２に書込む。入力として、データＳ４１＝{2，0，1，2，1，2}、インデックスＳ４３＝{0，1，2，3，4，5}が入力されるとすると、入力完了後、データソート装置３２Ａは、図８に示すようになる。
【００９７】
出力時は、図９〜図１３に示すように、列インデックスを読出す。バケツメモリ３２２の書き換えも行われる。対角化対象となる３列を読出した時点で、出力は終了する。
まず、図９に示すように、データ０のインデックスの読出しを開始する。バケツメモリ３２２から１を読出し、これを出力する。出力データが存在しないインデックス６ではないので、データ０のインデックスの読出しを続ける。
次に、図１０に示すように、まず、出力インデックスＳ４８である１をアドレスとして、インデックスメモリ３２１から６を読み出す。さらに、読出した６をバケツメモリ３２２２のアドレス０に書き込む。これにより、既に出力されたインデックスについては、インデックス順の系列から外れることになる。また、出力インデックスＳ４８に存在しないインデックス６が読み出されたので、次からデータ１のインデックスを読み出す。
次に、図１１に示すように、読出しデータ１を指定する。出力インデックスＳ４８に４が読み出される。
次に、図１２に示すように、出力インデックスＳ４８に２が読み出される。また、バケツメモリ３２２のアドレス１に読出したインデックスＳ４７として２が書き込まれる。
既に３列読み出されたのでこの時点で出力は完了するが、最後に図１３に示すように、バケツメモリ３２２のアドレス１に読出しインデックスＳ４７として６を書き込んでおく。これによりメモリ内部のインデックス順の情報の更新も完了する。
以上の操作により、対角化部３３に出力されたインデックスＳ４８＝{1，4，2}のデータ情報は既にメモリ内のインデックス系列のリストから外れたことになる。
【００９８】
次に、出力されたインデックスＳ４８＝{1，4，2}のＬＬＲが信頼性伝播（ＢＰ）で更新されて再びこのソート装置に入力された場合を考える。
二回目の繰り返し入力の時点で、メモリに格納されている列インデックスは、図１３と同様に図１４に示すようになる。二回目の繰り返しの入力は、データＳ４１＝{1，0，2}、インデックスＳ４３＝{1，4，2}と入力された場合を考える。
【００９９】
図１５に示すように、入力インデックスＳ４３として１が、更新された入力データＳ４１でありそれが入力されると、通常の書き込み動作と同様に、バケツメモリ３２２に１を書込み、バケツメモリ３２２から読出したインデックスＳ４５である６をインデックスメモリ３２１に入力インデックスＳ４３をアドレスとして書き込む。
【０１００】
そして、図１６、さらには図１７に示すように、列インデックス４、２についても同様に行う。入力はこれで完了である。これを、通常の読出し動作と同様に列インデックスを読み出すと、データ０のインデックス＝{４}、データ１のインデックス１＝{１}、データ０のインデックス＝{2，5，3，0}というように正しくソートされて読み出される。
繰り返しを重ねても、常にインデックスを出力するたびに上記の通りバケツメモリ１１２を更新すれば、ＬＬＲが更新された一部のインデックスのみ入力される場合に適応できる。
【０１０１】
以上でデータのソートは実現される。
次に、さらに実用に即したＡＢＰ復号を実現するための動作周波数を実現可能な構成について考察する。
【０１０２】
図１８は、実用に即した動作周波数で動作可能なＡＢＰ復号器の動作フローを示す図である。
【０１０３】
本例においては、内側繰り返し二回目以降の対角化対象となる列と対角化対象とならない列の集合の分割方法を、前繰り返しの両集合の一部の入れ替えに限定し、その時に入れ替えられ新しく対角化対象となった列についてのみ前対角化で更新されたパリティ検査行列を対象として対角化を行う。
【０１０４】
この場合は、図１８では、繰り返し一回目の復号が行われた後、二回目のソート時、信頼度が更新された１２８列のうち、信頼度の最も大きい４列のみ、対角化対象から外し、残り１５０４列のうち信頼度の小さい４列を新しく対角化対象１２８列の集合に加える。
この新しい対角化対象４列について、前繰り返しで対角化された後のパリティ検査行列に対して対角化を行う。
このとき、今回新しく対角化対象から外れた列に対応する要行は、既要行リストからは外す。そして、そのパリティ検査行列を用いて信頼性伝播（ＢＰ）を行う。以降の繰り返しではこれを繰り返す。
【０１０５】
以上をもとに、具体的に動作周波数を想定してみる。
ＲＳ（204，188）を想定し、内側繰り返し復号を装置で実現することを想定した場合、内側繰り返し数を１０回、ＬＬＲの更新を対角化対象となった列１２８列にのみ限定し信頼性伝播（ＢＰ）を１回にする条件において、ＡＢＰ復号するための必要なクロックサイクル数は、次のようになる。
【０１０６】
【数１８】
2008167377.tif 000020
【０１０７】
ここで、Ｔ１は繰り返し一回目に必要とするクロックサイクル数、Ｔ２は繰り返し二回目以降に必要とするクロックサイクル数を示している。
Ｔ１は、次式で示すようなクロックサイクル数が必要となる。
【０１０８】
【数１９】
2008167377.tif 000021
【０１０９】
また、Ｔ２は次のようになる
【０１１０】
【数２０】
2008167377.tif 000022
【０１１１】
ここで、Ｔsort2は、内側繰り返し二回目以降のソートに必要とするクロックサイクル数を示し、Ｔdiag2は、対角化に必要とするクロックサイクル数を示し、Ｔbpは、信頼性伝播（ＢＰ）に必要とするクロックサイクル数を示している。
【０１１２】
まず、Ｔsort2について考える。
繰り返し二回目以降は、ＬＬＲが更新される列インデックスが１２８列である。まず、これをソートする。次にこの１２８列のうちＬＬＲの大きい数列と、前繰り返しの際に対角化対象から外れた中でＬＬＲが小さい数列、ここでは共に４列とし、この４列同士の入れ替えを行う。
この入れ替えは計８列のうちＬＬＲの小さい４列を選び直してもよいし、強制的に入れ替え、つまり前繰り返しの際に対角化対象から外れた中でＬＬＲが小さい４列を新たな対角化対象に加えてもよい。
今回は強制的に入れ替えるとし、Ｔsort2＝０とする。また、後段のパリティ検査行列の対角化においては、前繰り返しで対角化されたパリティ検査行列を利用し、今回新たに対角化対象列になった４列に対してのみ基本変形を行う。このとき、今回新たに対角化対象列から外れた４列については、それに対応する要行は、過去要行になった行リストからは外し、今回新たに対角化対象列になった４列に対応する要行になることができる。
【０１１３】
以上より本装置では、４列並列に対角化を行っているので、Ｔdiag2＝１２８となる。また、信頼性伝播（ＢＰ）、繰り返し一回目と同様に行う。つまり、Ｔ２は次のようになる。
【０１１４】
【数２１】
2008167377.tif 000023
【０１１５】
以上より、Ｔは次式で与えられる。
【０１１６】
【数２２】
2008167377.tif 000024
【０１１７】
ここで、６４[Ｍｂｐｓ]のデータをＡＢＰ復号する場合を考えると、動作周波数は次のようになる。
【０１１８】
【数２３】
2008167377.tif 000025
【０１１９】
このように、３２０[ＭＨｚ]の動作周波数が必要となり、かなり現実的な動作周波数となる。
なお、ＡＢＰ復号器を二つならべて一符号語毎に入力を入れ替えてＡＢＰ復号器に挿入すれば、さらに３２０／２＝１６０[ＭＨｚ]まで動作周波数を抑えることができる。さらに、ソートのみ二つ並べれば、符号語が入力されてから初めの１６３２クロックサイクルのうちに、前入力符号語のＡＢＰ復号が完了していればよいので、次のように、動作周波数を１２８[ＭＨｚ]まで抑えることができる。
【０１２０】
【数２４】
2008167377.tif 000026
【０１２１】
以下に、図１８の動作フローを実現するような処理部を構成するソート装置（図６のソート部）および対角化装置（図６の対角化部）を第２の実施形態として説明する。
【０１２２】
＜第２実施形態＞
図１９は、本発明の第２の実施形態に係るＡＢＰ復号器のデータソート装置の構成例を示す図である。
【０１２３】
本第２の実施形態に係るデータソート装置３２Ｂは、アドレスがデータの大きさに対応し、インデックスメモリ３２１、バッファとしてのバケツメモリ３２２に加えて、第１書込み読出しアドレス選択部３２３、第２書込み読出しアドレス選択部３２４、書込みデータ選択部３２５、および出力インデックス選択部３２６を有する図７のデータソート装置をソートコア部３２Ａとして有し、さらにソードコア部３２Ａに加えて、４列メモリ３２７、ソートコア入力選択部３２８、および対角化４列メモリ３２９を有している。
【０１２４】
メモリ３２７は、本繰り返しで新しく対角化対象から外れた４列を保持する。
【０１２５】
ソートコア部入力選択部３２８は、繰り返し一回目は、入力ＬＬＲＳ５１（図６のＳ３１）と、列インデックスＳ５２（図６のＳ３２）を選択し、繰り返し二回目以降は、今回新しく対角化対象から外れた４列のＬＬＲＳ５３と列インデックスＳ５４を選択する。
【０１２６】
対角化４列メモリ３２９は、次に後段の対角化部３３に送り出す４列のインデックスを前もって保持しておく。
【０１２７】
次に、第２の実施形態に係るデータソート装置の処理を、図２０〜図２７に関連付けて説明する。
【０１２８】
まず、図２０に示すように、繰り返し復号一回目は、入力ＬＬＲＳ５１と列インデックスＳ５２が１６３２個入力される。これをソートコア部３２Ａでソートする。
その後、後段の対角化部３３で１２８列の対角化を行う必要があるので、対角化対象列を４列毎に図２１、図２２、図２３に示すように出力する。
また、次の繰り返しのために、図２４に示すように、１２９列〜１３２列も対角化４列メモリ８０４に前もって保持しておく。
【０１２９】
繰り返し二回目は、図６において、信頼性伝播（ＢＰ）部３５から、ＬＬＲが更新された列１２８列のインデックスとそのＬＬＲがソート部３２に入力される。
図２５に示すように、ソート部３２に１列〜１２８列のインデックスが入力され、この中から今回新しく対角化対象から外れる４列を選ぶ。つまり、１列から順に入力されそのＬＬＲを比較し、ＬＬＲの絶対値が最も大きい４つを常にメモリ３２７に保持する。
１２８列の入力が完了すれば、図２６に示すように、今回新しく対角化対象から外れた４列メモリからＬＬＲＳ５３とその列インデックスＳ５４をソートコア部３２Ａへ出力する。これにより、ＬＬＲの順に、今回対角化対象から外れた１５０４列がＬＬＲ順に並べ直され、ソートコア部３２Ａに保持される。
【０１３０】
また、今回対角化を行う４列を対角化４列メモリ３２９から出力インデックスＳ５８に読み出す。
この際、後段の対角化部３３におけるパリティ検査行列の対角化においては、前繰り返しで対角化されたパリティ検査行列を利用し、今回新たに対角化対象列になった４列に対してのみ基本変形を行う。このとき、今回新たに対角化対象列から外れた４列については、それに対応する要行は、過去要行になった行リストからは外し、今回新たに対角化対象列になった４列に対応する要行になることができる。
【０１３１】
この今回新たに対角化対象列から外れた４列に対応する要行は、列インデックスと一緒に束ねられ、今回新しく対角化対象から外れた４列メモリ３２７に一緒に記憶され、出力列インデックスＳ５８を出力する際にこの今回新しく外れる要行を後段の対角化部３３に出力してもよい。
また、さらに、１２８列のうち何番目のデータが対角化回路から外れたのかについても、上書き位置として後段の対角化回路に出力してもよい。
また、図２７示すように、次の繰り返しの時のために、１２３列〜１３２列を対角化４列メモリ３２９に前もって出力し保持させておく。
【０１３２】
ここで、新しく対角化対象となった列についてのみ対角化するフロー例を、行列を使って説明する。
今回は簡単のため、以下の４×６-行列Ｈを、繰り返し一回目において第１、２、３、４列について対角化を行った後、繰り返し二回目において第５、６列について対角化する例を考える。
このとき、新しく対角化対象から外れる二列を第２、３列とすると、対応する要行は第３、４行なので、新しく第３、４行は要になることができる。
【０１３３】
【数２５】
2008167377.tif 000027
【０１３４】
行列Ｈを第１、２、３、４列について対角化すると、以下のＨnewのようになる。
【０１３５】
【数２６】
2008167377.tif 000028
【０１３６】
二回目で第３、４列が新しく対角化対象から外れ、第５、６列が新しく対角化対象となる。この時、第２、３列の元要行である第３、４は新しく要行になることができる。
まず、第５列について次のように基本変形する。
【０１３７】
【数２７】
2008167377.tif 000029
【０１３８】
次に、第６列について次のように基本変形する。
【０１３９】
【数２８】
2008167377.tif 000030
【０１４０】
以上で、新たに第５、６列についての対角化が完了する。
【０１４１】
ＡＢＰ復号器３０における対角化部３３は、行列の対角化を行った後に、後段の信頼性伝播（ＢＰ）部３５における信頼性伝播用に対角化対象列とそれに対応する要行を出力することを繰り返す。
以下、本第２の実施形態に係る対角化部の具体的な構成例および動作について、図２８〜図４０に関連付けて説明する。
図２８〜図４０は、繰り返し二回目以降の具体的な対角化部の構成および動作を示している。
図２８〜図３６は、パリティ検査行列の対角化フェーズを、図３７〜図４０は、信頼性伝播（ＢＰ）のための対角化対象列とそれに対応する要行を出力するフェーズである。
【０１４２】
この対角化部３３Ａは、図２８に示すように、行のインデックスを記憶する行インデックスメモリ３３１、行列を記憶する行列メモリ３３２、第１要探索、掃き出し回路３３３、第１行保持部３３４、第１要フラグ保持部３３５、第２要探索、掃き出し回路３３６、第２行保持部３３７、第２要フラグ保持部３２８、および要列・行インデックスメモリ３３９を有している。
【０１４３】
対角化部３３Ａ内部の要探索、掃き出し回路に送るパリティ検査行の読出し順番は、過去要になっていない行を先に読み出す必要がある。つまり、繰り返し二回目以降の対角化においては、新しく要になれる行を先に読み出すことになる。また、本対角化部３３Ａは、一度の行読出しで複数の列の対角化を行う。
【０１４４】
本対角化部３３Ａは、図２８に示すように、行インデックスメモリ３３１、行列メモリ３３２、要探索、掃き出し回路が存在する。
要列・行インデックスメモリ３３９には、対角化対象列とそれに対応する要行インデックスが保持されている。
行列Ｈを第１、２、３、４列について対角化し終わった後に、図２８に示すように、行列メモリ３３２には対角化された行列、行インデックスメモリ３３１には、行インデックスが保持される。
行インデックスメモリ３３１の読出し行インデックス保持部３３１１のインデックスの並びは、要探索、掃き出し回路で要になった行のインデックスをアドレスの後ろに書き込み、そうでない行のインデックスは先頭アドレスから順にインデックスを書き込んだ結果、図のようになっている。
さらに、要列・行インデックスメモリ３３９には、対角化対象列とそれに対応する要行インデックスが保持される。
【０１４５】
次に、次の繰り返し二回目で新しく要になれる行インデックスＳ６０と新しい対角化列インデックスＳ７２が入力される場合を考える。今回は、上記例と同様、第２、３列が対角化対象から外れ、つまり対応する第３、４行が新しく要になることができ、第５、６列が新しく対角化対象になる場合を考える。
つまり、入力として、新しく要行になれる行インデックスＳ６０＝｛３，４｝、新しい対角化対象列インデックスＳ７２＝｛５，６｝、上書き位置Ｓ７３＝｛２，３｝と入力される。上書き位置は、要列・行インデックスメモリ３３９のどのアドレスに新しい対角化対象列とそれに対応する要行を書き込めばよいかを表す。
【０１４６】
図２９に示すように、まず、上書き位置Ｓ７３として２が入力される。これにより、要列・行インデックスメモリ３３９のアドレス２番目の要列は、新しい対角化対象列インデックス５が入力され５と上書きされる。
また、第１要探索、掃き出し回路３３３に対角化対象列５が設定される。新しく要になれる行インデックスＳ６０である３が入力されると、これが行列メモリ３３２に読み込まれ、パリティ検査行列第３行Ｓ６３が出力される。
このパリティ検査行Ｓ６３は、まず第１要探索、掃き出し回路３３３へ送られ、対象列が非零なら要とし、その行を内部に保持し、要が見つかった後は入力される行に対して掃き出しを行う。
【０１４７】
図３０に示すように、上書き位置Ｓ７３として４が入力される。これにより、要列・行インデックスメモリ３３９のアドレス４番目の要列は、新しい対角化対象列インデックス６が入力され６と上書きされる。
また、第２要探索、掃き出し回路３３６に対角化対象列６が設定される。新しく要になれる行インデックスＳ６０である４が入力されると、これが行列メモリ３３２に読み込まれ、パリティ検査行列第４行Ｓ６３が出力される。
このパリティ検査行Ｓ６３は、まず第１要探索、掃き出し回路３３３へ送られ、対象列が非零なら要とし、その行を内部に保持、要が見つかった後は入力される行に対して掃き出しを行う。第２要探索、掃き出し回路３３６においても、同様の動作が行われる。
【０１４８】
図３１〜図３６に示す処理においても同様の要探索、掃き出し動作が行われる。
それに加えて、図３１に示すように、要列・行インデックスメモリ３３９には、今回第５列の要行として書込み行インデックス３と要フラグ１が到来するので、要列・行インデックスメモリ３３９には、要列５に対して要行３が書き込まれる。
図３２に示すように、要列・行インデックスメモリ３３９には、今回第６列の要行として書込み行インデックス４と要フラグ１が到来するので、要列・行インデックスメモリ３３９には、要列６に対して要行４が書き込まれる。
以降、図３３、図３４、図３５、図３６のように、同様に要探索、掃き出しが行われ、これが完了する。
【０１４９】
要探索、掃き出しが完了すると、それ以降、後段の信頼性伝播（ＢＰ）用に対角化対象列インデックスと、それに対応する要行が出力される。
【０１５０】
図３７〜図４０の処理においては、順に要列・行インデックスメモリ３３９から対角化対象列とそれに対応する要行が順に読み出される。
たとえば、図３７に示すように、要列・行インデックスメモリ３３９の先頭アドレスから、列インデックスＳ７４である１と、行インデックスＳ７４である２が読み出され、出力としては、列インデックスＳ７６と、行インデックスＳ７４により読み出された行Ｓ７５が出力される。
【０１５１】
以上の対角化と信頼性伝播（ＢＰ）を繰り返すことによって、ＡＢＰ復号器における対角化部は成り立つ。
【０１５２】
図４１は、シミュレーションモデルを示す図である。
このシミュレーションモデル４０は、図４１に示すように、ＲＳ符号化器４１、ＢＰＳ変調器４２、ＡＷＧＮチャネル４３、ＢＰＳＫ復調器４４、およびＡＢＰ復号器４５を有する。
図４２は、シミュレーション結果を示す図である。
図４２は、ＲＳ（２０４，１８８）を想定した場合のフレームエラーレート（Ｆｒａｍｅ  Ｅｒｒｏｒ  Ｒａｔｅ）を示す図であって、Ａで示す曲線が既存手法の復号性能を示し、Ｂで示す曲線が本実施形態に手法における復号性能を示している。
【０１５３】
以上の内側繰り返し二回目以降は４列のみ対角化対象列集合と非対象列集合の入れ替えを行い、４列のみ対角化し直すＡＢＰ復号を用いても、既存技術と比較して、図４１に示すようなシミュレーションモデルにおいて、図４２に示すように性能劣化はほとんど発生しないことがシミュレーションにより確認されている。
【０１５４】
なお、以上詳細に説明した方法は、上記手順に応じたプログラムとして形成し、ＣＰＵ等のコンピュータで実行するように構成することも可能である。
また、このようなプログラムは、半導体メモリ、磁気ディスク、光ディスク、フロッピー（登録商標）ディスク等の記録媒体、この記録媒体をセットしたコンピュータによりアクセスし上記プログラムを実行するように構成可能である。
【図面の簡単な説明】
【０１５５】
【図１】パリティ検査行列Ｈｎｅｗに対応するタナーグラフである。
【図２】ＡＢＰ復号法を用いた繰り返し復号のフローチャートである。
【図３】ＡＢＰ復号装置の繰り返し毎のフローの一列を示す図である。
【図４】デジタル信号受信機、たとえばデジタルテレビなどの誤り訂正システムにＡＢＰ復号器を用いた通信システムの構成例を示す図である。
【図５】ＭＡＰ復号が後段についたＡＢＰ復号器の構成例を示す図である。
【図６】ＡＢＰ復号器の復号装置の構成例を示す図である。
【図７】本発明の第１の実施形態に係るＡＢＰ復号器のデータソート装置の構成例を示す図であり、処理を説明するための第１図である。
【図８】第１の実施形態に係るソート装置の処理を説明するための第２図である。
【図９】第１の実施形態に係るソート装置の処理を説明するための第３図である。
【図１０】第１の実施形態に係るソート装置の処理を説明するための第４図である。
【図１１】第１の実施形態に係るソート装置の処理を説明するための第５図である。
【図１２】第１の実施形態に係るソート装置の処理を説明するための第６図である。
【図１３】第１の実施形態に係るソート装置の処理を説明するための第７図である。
【図１４】第１の実施形態に係るソート装置の処理を説明するための第８図である。
【図１５】第１の実施形態に係るソート装置の処理を説明するための第９図である。
【図１６】第１の実施形態に係るソート装置の処理を説明するための第１０図である。
【図１７】第１の実施形態に係るソート装置の処理を説明するための第１１図である。
【図１８】実用に即した動作周波数で動作可能なＡＢＰ復号器の動作フローを示す図である。
【図１９】本発明の第２の実施形態に係るＡＢＰ復号器のデータソート装置の構成例を示す図であり、処理を説明するための第１図である。
【図２０】第２の実施形態に係るソート装置の処理を説明するための第２図である。
【図２１】第２の実施形態に係るソート装置の処理を説明するための第３図である。
【図２２】第２の実施形態に係るソート装置の処理を説明するための第４図である。
【図２３】第２の実施形態に係るソート装置の処理を説明するための第５図である。
【図２４】第２の実施形態に係るソート装置の処理を説明するための第６図である。
【図２５】第２の実施形態に係るソート装置の処理を説明するための第７図である。
【図２６】第２の実施形態に係るソート装置の処理を説明するための第８図である。
【図２７】第２の実施形態に係るソート装置の処理を説明するための第９図である。
【図２８】本発明の第２の実施形態に係る対角化部の構成例を示す図であり、処理を説明するための第１図である。
【図２９】第２の実施形態に係る対角化部の処理を説明するための第２図である。
【図３０】第２の実施形態に係る対角化部の処理を説明するための第３図である。
【図３１】第２の実施形態に係る対角化部の処理を説明するための第４図である。
【図３２】第２の実施形態に係る対角化部の処理を説明するための第５図である。
【図３３】第２の実施形態に係る対角化部の処理を説明するための第６図である。
【図３４】第２の実施形態に係る対角化部の処理を説明するための第７図である。
【図３５】第２の実施形態に係る対角化部の処理を説明するための第８図である。
【図３６】第２の実施形態に係る対角化部の処理を説明するための第９図である。
【図３７】第２の実施形態に係る対角化部の処理を説明するための第１０図である。
【図３８】第２の実施形態に係る対角化部の処理を説明するための第１１図である。
【図３９】第２の実施形態に係る対角化部の処理を説明するための第１２図である。
【図４０】第２の実施形態に係る対角化部の処理を説明するための第１３図である。
【図４１】シミュレーションモデルを示す図である。
【図４２】シミュレーション結果を示す図である。
【符号の説明】
【０１５６】
１０・・・通信システム、１１・・・ＲＳ符号化器、１２・・・インタリーバ、１３・・・畳み込み符号器、１４・・・畳み込み符号の軟出力復号器、１５・・・デインタリーバ、１６・・・ＡＢＰ繰り返し復号器、１７・・・チャネル、２０・・・復号器、２１・・・ＡＢＰ復号部、２２・・・限界距離（ＢＤ）復号部、２３・・・受信信頼度（ＬＬＲ）保持部、２４・・・ＭＡＰ復号部、３０・・・ＡＢＰ復号器、３１・・・ソート入力選択部、３２・・・ソート部、３２Ａ，３２Ｂ・・・データソート装置、３３，３３Ａ・・・パリティ検査行列の対角化部、３４・・・信頼度（ＬＬＲ）保持部、３５・・・信頼性伝播（ＢＰ）部、３２１・・・インデックスメモリ、３２２・・・バケツメモリ、３２３・・・第１書込み読出しアドレス選択部、３２４・・・第２書込み読出しアドレス選択部、３２５・・・書込みデータ選択部、３２６・・・出力インデックス選択部、３２７・・・４列メモリ、３２８・・・ソートコア部入力選択部、３２９・・・対角化４列メモリ、３３１・・・行インデックスメモリ、３３２・・・行列メモリ、３３３・・・第１要探索、掃き出し回路、３３４・・・第１行保持部、３３５・・・第１要フラグ保持部、３３６・・・第２要探索、掃き出し回路、３３５・・・第２行保持部、３３８・・・第２要フラグ保持部、３２９・・・要列・行インデックスメモリ。
【図１】
2008167377.tif 000031
【図２】
2008167377.tif 000032
【図３】
2008167377.tif 000033
【図４】
2008167377.tif 000034
【図５】
2008167377.tif 000035
【図６】
2008167377.tif 000036
【図７】
2008167377.tif 000037
【図８】
2008167377.tif 000038
【図９】
2008167377.tif 000039
【図１０】
2008167377.tif 000040
【図１１】
2008167377.tif 000041
【図１２】
2008167377.tif 000042
【図１３】
2008167377.tif 000043
【図１４】
2008167377.tif 000044
【図１５】
2008167377.tif 000045
【図１６】
2008167377.tif 000046
【図１７】
2008167377.tif 000047
【図１８】
2008167377.tif 000048
【図１９】
2008167377.tif 000049
【図２０】
2008167377.tif 000050
【図２１】
2008167377.tif 000051
【図２２】
2008167377.tif 000052
【図２３】
2008167377.tif 000053
【図２４】
2008167377.tif 000054
【図２５】
2008167377.tif 000055
【図２６】
2008167377.tif 000056
【図２７】
2008167377.tif 000057
【図２８】
2008167377.tif 000058
【図２９】
2008167377.tif 000059
【図３０】
2008167377.tif 000060
【図３１】
2008167377.tif 000061
【図３２】
2008167377.tif 000062
【図３３】
2008167377.tif 000063
【図３４】
2008167377.tif 000064
【図３５】
2008167377.tif 000065
【図３６】
2008167377.tif 000066
【図３７】
2008167377.tif 000067
【図３８】
2008167377.tif 000068
【図３９】
2008167377.tif 000069
【図４０】
2008167377.tif 000070
【図４１】
2008167377.tif 000071
【図４２】
2008167377.tif 000072