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