(57)【要約】【課題】より少ない計算量で同等の復号性能を得られ、計算所要時間、回路規模の削減を図ることが可能な復号方法および復号装置を提供する。【解決手段】線形符号の軟判定繰り返し復号の出力に対して、硬判定後限界距離復号、リスト復号、もしくは軟値をそのまま入力とした軟判定リスト復号を適用して復号語候補のリストを取得するリスト取得部１１０（１０２，１０４）と、受信語を硬判定する硬判定部１０３と、リスト取得部１１０で取得した復号語候補リストと硬判定部１０３で硬判定して得られた受信語との距離比較を行い、距離比較結果を用いて、復号語候補リストから１つの復号語を選択する最大事後確率復号（ｍａｘｉｍｕｍ  ａ  ｐｏｓｔｅｒｉｏｒｉ  ｐｒｏｂａｂｉｌｉｔｙ復号、ＭＡＰ復号）を行う復号部１０４とを有する。【選択図】図２
2008148056.tif 000002
【特許請求の範囲】
【請求項１】
線形符号の軟判定繰り返し復号の出力に対して、硬判定後限界距離復号、リスト復号、もしくは軟値をそのまま入力とした軟判定リスト復号を適用して復号語候補のリストを取得する第１ステップと、
受信語を硬判定する第２ステップと、
前記第１ステップで取得した復号語候補リストと前記第２ステップで硬判定して得られた受信語との距離比較を行う第３ステップと、
前記第３ステップの距離比較結果を用いて、復号語候補リストから１つの復号語を選択する最大事後確率復号（ｍａｘｉｍｕｍ  ａ  ｐｏｓｔｅｒｉｏｒｉ  ｐｒｏｂａｂｉｌｉｔｙ復号、ＭＡＰ復号）を行う第４ステップと
を有する復号方法。
【請求項２】
前記硬判定による受信語取得を１ビット（ｂｉｔ）量子化によって行う
請求項１記載の復号方法。
【請求項３】
１ｂｉｔ量子化で得られた受信語を一旦メモリに保存する
請求項２記載の復号方法。
【請求項４】
前記第４ステップにおいて復号語候補リストから１つの復号語を選択するＭＡＰ復号の際に前記メモリから読み出した受信語を距離比較対象として用いる
請求項３記載の復号方法。
【請求項５】
線形符号として有限体Ｆq（ｑ＝ｐｍ，ｐ；素数）上の代数幾何符号を用いる
請求項１記載の復号方法。
【請求項６】
前記第４ステップにおいて、ＭＡＰ復号で復号語候補リストと受信語との距離比較を行う際に、受信語からのハミング距離が最短となる復号語候補を復号語として選択する
請求項５記載の復号方法。
【請求項７】
適応的信頼性伝播（ＡＢＰ：Ａｄａｔｉｖｅ  Ｂｅｌｉｅｆ  Ｐｒｏｐａｇａｔｉｏｎ）を用いた繰り返し復号の各繰り返しで得られた信頼性を入力として、復号語候補のリストを取得する際に限界距離復号を適用する
請求項１記載の復号方法。
【請求項８】
線形符号の軟判定繰り返し復号の出力に対して、硬判定後限界距離復号、リスト復号、もしくは軟値をそのまま入力とした軟判定リスト復号を適用して復号語候補のリストを取得するリスト取得部と、
受信語を硬判定する硬判定部と、
前記リスト取得部で取得した復号語候補リストと前記硬判定部で硬判定して得られた受信語との距離比較を行い、当該距離比較結果を用いて、復号語候補リストから１つの復号語を選択する最大事後確率復号（ｍａｘｉｍｕｍ  ａ  ｐｏｓｔｅｒｉｏｒｉ  ｐｒｏｂａｂｉｌｉｔｙ復号、ＭＡＰ復号）を行う復号部と
を有する復号装置。
【請求項９】
前記硬判定部は、硬判定による受信語取得を１ビット（ｂｉｔ）量子化によって行う
請求項８記載の復号装置。
【請求項１０】
１ｂｉｔ量子化で得られた受信語を一旦保存するメモリを有する
請求項９記載の復号装置。
【請求項１１】
前記復号部は、
復号語候補リストから１つの復号語を選択するＭＡＰ復号の際に前記メモリから読み出した受信語を距離比較対象として用いる
請求項１０記載の復号装置。
【請求項１２】
線形符号として有限体Ｆq（ｑ＝ｐｍ，ｐ；素数）上の代数幾何符号を用いる
請求項８記載の復号装置。
【請求項１３】
前記復号部は、ＭＡＰ復号で復号語候補リストと受信語との距離比較を行う際に、受信語からのハミング距離が最短となる復号語候補を復号語として選択する
請求項１２記載の復号装置。
【請求項１４】
前記リスト取得部は、
適応的信頼性伝播（ＡＢＰ：Ａｄａｔｉｖｅ  Ｂｅｌｉｅｆ  Ｐｒｏｐａｇａｔｉｏｎ）を用いた繰り返し復号の各繰り返しで得られた信頼性を入力として、復号語候補のリストを取得する際に限界距離復号を適用する
請求項８記載の復号装置。
【請求項１５】
通信路を通って受信された受信語を受けて、適応的信頼性伝播（ＡＢＰ：Ａｄａｔｉｖｅ  Ｂｅｌｉｅｆ  Ｐｒｏｐａｇａｔｉｏｎ）を用いた繰り返し復号の各繰り返しにより更新されていく受信語を複数出力するＡＢＰ繰り返し復号部と、
供給された受信語を硬判定し、受信語を１ｂｉｔ量子化して出力する硬判定部と、
前記硬判定された受信語を保存するメモリと、
前記ＡＢＰ繰り返し復号部から供給されたデータに対し限界距離復号を行い、結果得られる復号語候補リストを出力する限界距離復号部と、
前記限界距離復号部から供給される復号語およびメモリから読み出した１ｂｉｔ量子化された受信語を受けて、受信語からの距離が最も近い復号語候補を復号語として出力する最大事後確率復号（ｍａｘｉｍｕｍ  ａ  ｐｏｓｔｅｒｉｏｒｉ  ｐｒｏｂａｂｉｌｉｔｙ復号、ＭＡＰ復号）部と
を有する復号装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、たとえば代数的手法を用いた誤り訂正符号技術を実現するための回路およびプログラム記憶媒体に関して適用される復号方法および復号装置に関するものである。
【背景技術】
【０００２】
代数幾何符号、たとえばリードソロモン（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ）符号やその部分体部分符号としてのＢＣＨ符号には、その代数的性質を利用した、性能・計算コスト共に良い復号法が知られている。
【０００３】
たとえば、符号長ｎ、情報長ｋ、定義体ＧＦ（ｑ）（ｑ＝ｐｍ，ｐ：素数）、最小距離ｄ＝ｎ−ｋのＲｅｅｄ−Ｓｏｌｏｍｏｎ符号をＲＳ（ｎ，ｋ）とすると、硬判定受信語をハミング（Ｈａｍｍｉｎｇ）距離が最小の符号語に復号する最小距離復号（通常復号）はｔ＜ｄ／２を満たすｔ個の誤りシンボルの訂正を保証するものとして良く知られている。
【０００４】
また、グルスワミ−スーダン（Ｇｕｒｕｓｗａｍｉ−Ｓｕｄａｎ）によるリスト復号（以下Ｇ−Ｓリスト復号）は、ｔ＜√ｎｋを満たすｔ個の誤りシンボルの訂正を保証している（非特許文献１参照）。
【０００５】
Ｇｕｒｕｓｗａｍｉ−Ｓｕｄａｎのリスト復号の拡張版として軟判定受信語を用いたケッター−バーディ（Ｋｏｅｔｔｅｒ−Ｖａｒｄｙ）によるリスト復号（以下Ｋ−Ｖリスト復号）は、Ｇｕｒｕｓｗａｍｉ−Ｓｕｄａｎ同様に（１）受信情報から各シンボルの信頼性を算出、（２）信頼性から２変数多項式補間条件の抽出、（３）２変数多項式の補間、（４）補間多項式の因数分解を行い復号語りスト作成、の４つの手順により構成され、硬判定復号時に比べてより高い性能を持つことが知られている（非特許文献２参照）。
【０００６】
また、リエンコード（Ｒｅ−ｅｎｃｏｄｅ）により、その計算コストも現実的な範囲まで削減できることが知られている（非特許文献３参照）。
【０００７】
一方、線形符号としては、信頼性伝播（ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を用いた繰り返し復号により限界性能に近い高性能を得られる低密度パリティ検査符号（Ｌｏｗ  ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ−ｃｈｅｃｋ  ｃｏｄｅ，ＬＤＰＣ符号）が昨今注目されている（非特許文献４参照）。
【０００８】
ＬＤＰＣ符号に用いられる信頼性伝播（ＢＰ）は、一般に低密度なパリティ検査行列を持つ線形符号にしか有効でないことが理論的に知られており、また、Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号やＢＣＨ符号のパリティ検査行列を低密度化することはＮＰ−ｈａｒｄであることが知られている（非特許文献５参照）。
【０００９】
よって、Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号やＢＣＨ符号に信頼性伝播（ＢＰ）を適用することは困難であるとされてきた。
【００１０】
しかし、２００４年、受信語の信頼性に応じて対角化を行ったパリティ検査行列を用いてＲｅｅｄ−Ｓｏｌｏｍｏｎ符号やＢＣＨ符号、その他低密度でないパリティ検査行列を持つ線形符号への信頼性伝播（ＢＰ）の適用が効果的であることがナラヤナン(Ｎａｒａｙａｎａｎ)等によって紹介された（非特許文献６参照）。
【００１１】
この手法は、適応的信頼性伝播（ＡＢＰ：Ａｄａｐｔｉｖｅ  Ｂｅｌｉｅｆ  Ｐｒｏｐａｇａｔｉｏｎ）復号と呼ばれる。
【００１２】
図１は、提案されているＡＢＰによる復号のフローチャートである。
【００１３】
受信後の信頼性順の探索を行い（ＳＴ１）、順序変換を行う（ＳＴ２）。
変換した順序に応じてパリティ検査行列の対角化を行い（ＳＴ３）、このパリティ検査行列を用いて信頼性伝播（ＢＰ）を行う（ＳＴ４）。
次に、ＬＬＲを計算し（ＳＴ５）、計算したＬＬＲの信頼性順を探索し（ＳＴ６）、復号を行う（ＳＴ７）。
そして、繰り返し復号停止条件ＳＣ１，ＳＣ２を満足するまで以上の処理を繰り返す（ＳＴ８、ＳＴ９）。
【００１４】
また、ＡＢＰによって更新された信頼性を用いて繰り返し復号を行う際に、途中得られた復号語候補のリストを保持し、最後に受信語から最小距離にあるものを復号語として、復号語候補リストから選択することによって、ＡＢＰ復号よりデコーダエラー生起確率が抑えられ、高い復号性能が得られるということが知られている。
【００１５】
【非特許文献１】Ｖ．Ｇｕｒｕｓｗａｍｉ，Ｍ．Ｓｕｄａｎ，Ｉｍｐｒｏｖｅ  ｄｅｃｏｄｉｎｇ  ｏｆ  Ｒｅｅｄ−Ｓｏｌｏｍｏｎ  ａｎｄ  Ａｌｇｅｂｒａｉｃ−Ｇｅｏｍｅｔｒｙ  ｃｏｄｅｓ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ｖｏｌ．４５，ｐｐ．１７５７−１７６７，１９９９
【非特許文献２】Ｒ．Ｋｏｅｔｔｅｒ，Ａ．Ｖａｒｄｙ，Ａｌｇｅｂｒａｉｃ  ｓｏｆｔ−ｄｅｃｉｓｉｏｎ  ｄｅｃｏｄｉｎｇ  ｏｆ  Ｒｅｅｄ−Ｓｏｌｏｍｏｎ  ｃｏｄｅｓ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，２００１
【非特許文献３】Ｒ．Ｋｏｅｔｔｅｒ，Ｊ．Ｍａ，Ａ．Ｖａｒｄｙ，Ａ，Ａｈｍｅｄ，Ｅｆｆｃｉｅｎｔ  Ｉｎｔｅｒｐｏｌａｔｉｏｎ  ａｎｄ  Ｆａｃｔｏｒｉｚａｔｉｏｎ  ｉｎ  Ａｌｇｅｂｒａｉｃ  Ｓｏｆｔ−Ｄｅｃｉｓｉｏｎ  Ｄｅｃｏｄｉｎｇ  ｏｆＲｅｅｄ−Ｓｏｌｏｍｏｎ  ｃｏｄｅｓ，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＩＳＩＴ２００３
【非特許文献４】Ｄ．ＭａｃＫａｙ，Ｇｏｏｄ  Ｅｒｒｏｒ−Ｃｏｒｒｅｃｔｉｎｇ  Ｃｏｄｅｓ  Ｂａｓｅｄ  ｏｎ  Ｖｅｒｙ  Ｓｐａｒｓｅ  Ｍａｔｒｉｃｅｓ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，１９９９
【非特許文献５】Ｂｅｒｌｅｋａｍｐ，Ｒ．ＭｃＥｌｉｅｃｅ，Ｈ．ｖａｎ  Ｔｉｌｂｏｒｇ，Ｏｎ  ｔｈｅ  ｉｎｈｅｒｅｎｔ  ｉｎｔｒａｃｔａｂｉｌｉｔｙ  ｏｆ  ｃｅｒｔａｉｎ  ｃｏｄｉｎｇ  ｐｒｏｂｌｅｍｓ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ｖｏｌ．２４，ｐｐ．３８４−３８６，Ｍａｙ，１９７８）。
【非特許文献６】Ｊｉｎｇ  Ｊｉａｎｇ，Ｋ．Ｒ．Ｎａｒａｙａｎ，Ｓｏｆｔ  Ｄｅｃｉｓｉｏｎ  Ｄｅｃｏｄｉｎｇ  ｏｆ  ＲＳ  Ｃｏｄｅｓ  Ｕｓｉｎｇ  Ａｄａｐｔｉｖｅ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ  Ｍａｔｒｉｃｅｓ，Ｐｒｏｃｅｅｄｉｎｇ  ｏｆ  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ  ２００４
【発明の開示】
【発明が解決しようとする課題】
【００１６】
軟判定した受信語をそのまま用いて、最大事後確率復号（ｍａｘｉｍｕｍ  ａ  ｐｏｓｔｅｒｉｏｒｉ  ｐｒｏｂａｂｉｌｉｔｙ復号、ＭＡＰ復号）により復号語を選択する手法で復号を行うと、ダブル（ｄｏｕｂｌｅ）の精度を持つ軟値受信語を一旦保存し、さらに復号語候補リストに対してユークリッド距離を求めることになる。
このため、一般的な回路装置では軟値受信値の保存のために要素毎でたとえば６ビット（ｂｉｔ）分のメモリが必要とされ、回路規模が大きくなってしまっていた。
【００１７】
さらに、ＭＡＰ復号においてこのダブル（ｄｏｕｂｌｅ）の精度を持つ軟値受信値とＡＢＰ繰り返し復号器から出力された復号語候補とのユークリッド距離の算出が必要となり、この計算には乗算回路が必要である上、計算量も多くなり、計算所要時間、回路規模共に大きくなってしまう。
【００１８】
本発明は、より少ない計算量で同等の復号性能を得られ、計算所要時間、回路規模の削減を図ることが可能な復号方法および復号装置を提供することにある。
【課題を解決するための手段】
【００１９】
本発明の第１の観点の復号方法は、線形符号の軟判定繰り返し復号の出力に対して、硬判定後限界距離復号、リスト復号、もしくは軟値をそのまま入力とした軟判定リスト復号を適用して復号語候補のリストを取得する第１ステップと、受信語を硬判定する第２ステップと、前記第１ステップで取得した復号語候補リストと前記第２ステップで硬判定して得られた受信語との距離比較を行う第３ステップと、前記第３ステップの距離比較結果を用いて、復号語候補リストから１つの復号語を選択する最大事後確率復号（ｍａｘｉｍｕｍ  ａ  ｐｏｓｔｅｒｉｏｒｉ  ｐｒｏｂａｂｉｌｉｔｙ復号、ＭＡＰ復号）を行う第４ステップと、を有する。
【００２０】
本発明の第２の観点の復号装置は、線形符号の軟判定繰り返し復号の出力に対して、硬判定後限界距離復号、リスト復号、もしくは軟値をそのまま入力とした軟判定リスト復号を適用して復号語候補のリストを取得するリスト取得部と、受信語を硬判定する硬判定部と、前記リスト取得部で取得した復号語候補リストと前記硬判定部で硬判定して得られた受信語との距離比較を行い、当該距離比較結果を用いて、復号語候補リストから１つの復号語を選択する最大事後確率復号（ｍａｘｉｍｕｍ  ａ  ｐｏｓｔｅｒｉｏｒｉ  ｐｒｏｂａｂｉｌｉｔｙ復号、ＭＡＰ復号）を行う復号部と、を有する。
【００２１】
本発明の第３の観点は、通信路を通って受信された受信語を受けて、適応的信頼性伝播（ＡＢＰ：Ａｄａｔｉｖｅ  Ｂｅｌｉｅｆ  Ｐｒｏｐａｇａｔｉｏｎ）を用いた繰り返し復号の各繰り返しにより更新されていく受信語を複数出力するＡＢＰ繰り返し復号部と、供給された受信語を硬判定し、受信語を１ｂｉｔ量子化して出力する硬判定部と、前記硬判定された受信語を保存するメモリと、前記ＡＢＰ繰り返し復号部から供給されたデータに対し限界距離復号を行い、結果得られる復号語候補リストを出力する限界距離復号部と、前記限界距離復号部から供給される復号語およびメモリから読み出した１ｂｉｔ量子化された受信語を受けて、受信語からの距離が最も近い復号語候補を復号語として出力する最大事後確率復号（ｍａｘｉｍｕｍ  ａ  ｐｏｓｔｅｒｉｏｒｉ  ｐｒｏｂａｂｉｌｉｔｙ復号、ＭＡＰ復号）部と、を有する。
【００２２】
本発明によれば、一般に幾何代数符号の一つであるリードソロモン符号の各符号間の距離が十分に大きいため、一つの受信語が複数の復号語候補に近接する可能性は低いという性質を持つことを利用し、限界距離復号の結果得られた復号語候補リストから最大事後確率復号（ｍａｘｉｍｕｍ  ａ  ｐｏｓｔｅｒｉｏｒｉ  ｐｒｏｂａｂｉｌｉｔｙ復号、ＭＡＰ復号）を用いて１つの復号語を選択する時に、硬判定して得られた受信語を用いる。
【発明の効果】
【００２３】
本発明によれば、より少ない計算コストで同等の復号性能を得られるため、計算所要時間、回路規模などが小さくなる。
【発明を実施するための最良の形態】
【００２４】
以下、本発明の実施形態を図面に関連付けて説明する。
【００２５】
図２は、本発明の実施形態に係る復号方法を採用した復号装置の構成例を示すブロック図である。
【００２６】
本実施形態に係る復号装置１００は、データソート部を有する線形符号の軟判定復号方式における最大事後確率復号法（ＭＡＰ復号法）を採用している。
後述する復号語候補リスト作成の段階において、限界距離復号を用いた場合の構成を有し、性能劣化が実用上無視できる程度小さい復号を、より少ない計算量、時間および回路規模で実現可能としている。
【００２７】
本実施形態に係る復号装置１００は、図２に示すように、軟判定部１０１、ＡＢＰ繰り返し復号部１０２、硬判定部１０３、硬判定後限界距離復号部１０４、およびＭＡＰ復号部１０５を有する。
なお、本実施形態においては、ＡＢＰ繰り返し復号部１０２および硬判定後限界距離復号部１０４によりリスト取得部１１０が構成される。
【００２８】
軟判定部１０１は、供給された受信語（ＬＬＲ）を軟判定して軟判定値Ｓ１０１をＭＡＰ復号部１０５に出力する。
【００２９】
ＡＢＰ繰り返し復号部１０２は、供給された受信語ＬＬＲを、ＡＢＰ（適応的信頼性伝播）を用いた手法で復号する装置であり、受信語ＬＬＲを入力として受け付け、その受信語ＬＬＲを更新したＬＬＲを硬判定後限界距離復号部１０４に出力する。
【００３０】
硬判定部１０３は、供給された受信値（ＬＬＲ）を硬判定して硬判定値Ｓ１０３をＭＡＰ復号部１０５に出力する。
【００３１】
硬判定後限界距離復号部１０４は、供給されたＬＬＲを限界距離復号して復号語候補リスト１０６をＭＡＰ復号部１０５に出力する。
【００３２】
ＭＡＰ復号部１０５は、供給された復号語候補リストおよび受信値の硬判定値を用いてＭＡＰ復号して、最適な復号語を１つ選択して外部に出力する。
【００３３】
以上のような構成を有する復号装置１００における復号処理の流れを図３のフローチャートを参照して説明する。
なお、ここでは具体的な例を適宜適用して説明する。つまり、有限体としてＦ２３、線形符号ｃとして符号長７、情報長３のＲｅｅｄ−Ｓｏｌｏｍｏｎ符号、ＲＳ（７，３）を考える。
【００３４】
Ｆ２３の原始根をα、原始多項式をα３十α＋１＝０、符号の生成多項式を、ｇ(ｘ）：＝（ｘ＋１）（ｘ＋α）（ｘ＋α２）（ｘ＋α３）とするとＣのパリティ検査行列Ｈは以下の形で与えられる。
【００３５】
【数１】
2008148056.tif 000003
【００３６】
これは、４×７-行列となっている。
ところで、Ｆ２３はＦ２の３次拡大体であることより行列をすべて４次元に展開することが可能である。
実際、上記のパリティ検査行列を３次元展開すると、次に示すような、Ｆ２上１２×２１行列Ｈexpを得ることができる。
【００３７】
【数２】
2008148056.tif 000004
【００３８】
対応する符号語も同様にＦ２上２１ビットに展開される。今、展開された符号語を次のような符号語とする。
【００３９】
【数３】
2008148056.tif 000005
【００４０】
この符号語をＡＷＧＮチャネル（Ａｄｄｉｔｉｖｅ  Ｗｈｉｔｅ  Ｇａｕｓｓｉａｎ  Ｎｏｉｓｅチャネル）上ＢＰＳＫ変調で送信した結果、たとえば、以下のＬＬＲｙを得たとする。
【００４１】
【数４】
2008148056.tif 000006
【００４２】
このようなＬＬＲがＡＢＰ繰り返し復号部１０２に供給されると復号語候補リストの復号が開始される。
ＡＢＰ繰り返し復号部１０２が、受信ＬＬＲｙに対して信頼性順の探索を行い（ＳＴ１０１）、各受信シンボルに信頼性の低い順に順序をつけると（ＳＴ１０２）、以下のようになる。
【００４３】
【数５】
2008148056.tif 000007
【００４４】
つまり、対角化する列のインデックスの順は以下の通りとなる。
【００４５】
【数６】
2008148056.tif 000008
【００４６】
パリティ検査行列Ｈexpについて、対応した列から順に対角化を行うと（ＳＴ１０３）、以下の行列Ｈnewが得られる。
【００４７】
【数７】
2008148056.tif 000009
【００４８】
このパリティ検査行列を用いて信頼性伝播（ＢＰ）を、たとえばＩｔ＝１回行う（ＳＴ１０４）。すると結果として更新されたＬＬＲが得られる（ＳＴ１０５，ＳＴ１０６）。
【００４９】
【数８】
2008148056.tif 000010
【００５０】
得られた新たなＬＬＲを後段の硬判定後限界距離復号部１０４への入力とし、復号を行う。得られた復号語候補を復号語リストへ加える（ＳＴ１０７）。
【００５１】
一方、更新されたＬＬＲの信頼性の大きさを用いて、再びパリティ検査行列の対角化をＡＢＰ繰り返し復号部１０２で行う。
対角化された行列を用いて信頼性伝播（ＢＰ）を行いＬＬＲの更新を行う。更新されたＬＬＲを後段の硬判定後限界距離復号部１０４への入力とし、復号を行う。得られた復号語候補を復号語リストへ加える。
このようにして、あらかじめ決めておいた繰り返し回数Ｎ１回（ＳＴ１０８）、ＡＢＰおよび後段の復号を行い、第１回目の外側繰り返し復号による復号語候補リストを得る。
【００５２】
次に、パリティ検査行列の対角化優先順位の初期値として前回と異なるものを用意する。つまり、第１回目の外側繰り返し復号の優先順位初期値は受信値のＬＬＲの信頼性の低い順であったが、それに変更を加える。
たとえば、受信値のＬＬＲの信頼性が低いビットに対応する列のインデックスは次の順である。
【００５３】
【数９】
2008148056.tif 000011
【００５４】
第１回目はこの順に対角化を試みたが、このインデックスの順序に対し、２１/Ｎ２＝２１/３＝７列分の入れ換えを行う（ＳＴ１０９）。
【００５５】
【数１０】
2008148056.tif 000012
【００５６】
この順序に則ってパリティ検査行列の対角化を行い、信頼性伝播（ＢＰ）を行う。更新されたＬＬＲを後段の硬判定後限界距離復号部１０４に入力し、復号リストを得る。
また、更新されたＬＬＲについて、その信頼性の低いビットに対応する列から順にパリティ検査行列の対角化を行う。
【００５７】
このようにして、第１回目の外側繰り返し復号とは順序の初期値が異なる第２の外側繰り返し復号を行う。あらかじめ決めておいた繰り返し回数Ｎ１回、信頼性伝播（ＢＰ）および後段の限界距離復号を硬判定後限界距離復号部１０４で行い、復号語候補リストを得る。
【００５８】
第３回目の順序の初期値としては、次のように、別の７ビット入れ換えを行い、同様な繰り返し復号を経て復号語リストを得る。
【００５９】
【数１１】
2008148056.tif 000013
【００６０】
以上の手順により、Ｎ２＝３回の外側繰り返し復号によって復号語リストが得られる。得られた復号語リストと最初に受信したＬＬＲより、ＭＡＰ復号部１０５におけるＭＡＰ復号によって最適と思われる復号語を一つ選択し（ＳＴ１１０）、それを復号語として出力する。
【００６１】
既存の方法では、このＭＡＰ復号において受信した軟値のＬＬＲと各復号語候補とのユークリッド距離を計算し、最もユークリッド距離の短いものを復号語としていた。
これに対して、本実施形態に係る手法では、受信したＬＬＲを硬判定して得られる受信語から各復号語候補までのハミング距離を計算し、最もハミング距離の短い復号語候補を復号語とする。
【００６２】
たとえば、この例では最初に受信したＬＬＲが次のように与えられている。
【００６３】
【数１２】
2008148056.tif 000014
【００６４】
このようにＬＬＲが与えられているので、既存の手法ではこの軟値の受信値と復号語候補のうち１つを次のようにする。
【００６５】
【数１３】
2008148056.tif 000015
【００６６】
これを次のようにＢＰＳＫ変調する。
【００６７】
【数１４】
2008148056.tif 000016
【００６８】
そして、これらの間のユークリッド距離を、次にように計算する。
【００６９】
【数１５】
2008148056.tif 000017
【００７０】
受信語と復号語候補のユークリッド距離は、復号語をＢＰＳＫ変調したものの各要素ｃｉと受信値の各要素ｙｉの差分の２乗和である。この場合
・ｙｉは定数、
・ｃｉ２＝１、
が常に成り立つので、（ｙｉ−ｃｉ）２＝ｙｉ２ｃｉ２−２ｙｉｃｉの和の異なる復号語候補間での大小関係は、−２ｙｉｃｉの和の異なる復号語候補間での大小関係と一致する。
したがって、この例で実際にユークリッド距離を比較するときには、代わりに次のように計算し、大小関係を求める。
【００７１】
【数１６】
2008148056.tif 000018
【００７２】
このとき、軟値の受信値の保持のために回路規模が大きくなり、さらに、ユークリッド距離の計算のために多ビットの乗算計算が必要であるため、多くの計算量を要する。
【００７３】
一方、本実施形態に係る手法では、１ｂｉｔ量子化により受信語の各ビットを硬判定し、正の受信ビットを１へ、負の受信ビットを０へ置き換える。このとき受信語は次のように与えられ、各要素は１ｂｉｔずつで表される。
【００７４】
【数１７】
2008148056.tif 000019
【００７５】
この硬判定された受信語と、ＬＬＲの繰り返し更新および後段の限界距離復号で得られた復号語リスト内の各復号語とのハミング距離は、たとえば復号語候補のうち一つが次のように与えられるとする。
【００７６】
【数１８】
2008148056.tif 000020
【００７７】
このとき、次のように、ｙおよびｃの各要素毎の排他的論理和(ＥＸＯＲ)の合計を計算するだけで求まる。
【００７８】
【数１９】
2008148056.tif 000021
【００７９】
このように、本実施形態の手法によれば、各要素ごとの演算は１ｂｉｔ同士の排他的論理和を求めているだけなので、既存の手法より少ない計算量で計算できる上、回路規模も削減される。
また、一般にリードソロモン符号の各符号語間の距離は大きいことが保障されており、１つの受信語が多数の復号語候補に近接する可能性は低い。このため、硬判定で得られた受信語と各復号語候補とのハミング距離（おおよそのユークリッド距離）が分かれば一意に復号語を求めることが可能であると考えられる。
【００８０】
図４は、既存手法および本実施形態に係る手法におけるシミュレーションを用いた復号性能比較のグラフを示す図である。
【００８１】
図４は、ＲＳ（７，３）に対して
１．各復号語候補と軟値受信値の間のユークリッド距離を元にＭＡＰ復号（最大事後確率復号）した場合（Ａ線）、
２．各復号語候補と硬判定した受信値の間のハミング距離を元に最大事後確率復号した場合（Ｂ線）、
のそれぞれのフレームエラーレート（Ｆｒａｍｅ  Ｅｒｒｏｒ  Ｒａｔｅ，○印）およびビットエラーレート（Ｂｉｔ  Ｅｒｒｏｒ  Ｒａｔｅ，×印）のグラフである。
【００８２】
図４から硬判定の有無に関わらず、性能の変化が無視できる程小さいことが確認できる。
【００８３】
なお、以上においては復号装置がリードソロモン符号を復号するように説明したが、これに限らずたとえばＢＣＨ符号を復号してもよいし、それ以外の符号化方式に対して復号を行うようにしても良い。
また、ＡＢＰ繰り返し復号で得られたＬＬＲから復号語候補リストを複合するときに硬判定後限界距離復号でなくとも、Ｋ−Ｖリスト復号、もしくは軟値をそのまま入力とした軟判定リスト復号等を適用しても良い。
【００８４】
図５は、回路実装されたＡＢＰ繰り返し復号器に対して、本発明の実施形態に係る復号方法を適用した具体例を示す図である。
【００８５】
この復号装置２００は、ＡＢＰ繰り返し復号部２０１、硬判定部２０２、限界距離復号部２０３、硬判定された受信値を保存するメモリ２０４、およびＭＡＰ復号部２０５を備えている。
【００８６】
ＡＢＰ繰り返し復号部２０１は、図示しない通信路を通って受信された受信語Ｄ２０１をＡＢＰを用いた手法で復号する装置であり、受信語Ｄ２０１を入力として受け付け、繰り返し復号により更新されていくＬＬＲＤ２０２を複数出力する。
【００８７】
また、硬判定部２０２は、供給された受信語Ｄ２０１に硬判定する装置であり、受信語Ｄ２０１を入力として受け付け、受信語を１ｂｉｔ量子化したデータＤ２０３をメモリ１０４に出力する。
【００８８】
限界距離復号部２０３は、ＡＢＰ繰り返し復号部２０１から供給されたＬＬＲＤ２０２を入力として受け付け、入力を硬判定したものに対し限界距離復号を行い、結果得られる復号語候補リストＤ２０４を出力する。
【００８９】
メモリ２０４は、硬判定部２０２から供給される１ｂｉｔ量子化された受信語Ｄ２０３を入力として受け付け、復号語候補リストが出力されるまでこれを保存し、復号語候補リストとのＭＡＰ復号の際にＭＡＰ復号部２０５にこの１ｂｉｔ量子化された受信語Ｄ２０５を出力する。
【００９０】
ＭＡＰ復号部２０５は、限界距離復号部２０３から供給される復号語Ｄ２０４およびメモリ２０４から供給される１ｂｉｔ量子化された受信語Ｄ２０５を入力として受け付け、受信語からのハミング距離が最も近い復号語候補を復号語Ｄ２０６として出力する。
【００９１】
次に、図５の構成の動作を図６に関連付けて説明する。
【００９２】
図示しない通信路を通って受信された受信語Ｄ２０１が、ＡＢＰ繰り返し復号部２０１および硬判定部２０２に入力される。
ＡＢＰ繰り返し復号部２０１においては、入力した受信語Ｄ２０１に対してをＡＢＰを用いた手法で復号し、このとき繰り返し復号により更新されていくＬＬＲＤ２０２が複数、硬判定後限界距離復号部２０３に出力される（ＳＴ２０１）。
【００９３】
硬判定部２０２においては、供給された受信語Ｄ２０１に硬判定が行われ（ＳＴ２０２）、入力して受け付けた受信語Ｄ２０１を１ｂｉｔ量子化したデータＤ２０３がメモリ２０４に出力される。
【００９４】
限界距離復号部２０３においては、ＡＢＰ繰り返し復号部２０１から供給されたＬＬＲＤ２０２が入力され、入力を硬判定したものに対し限界距離復号が行われる。その結果得られる復号語候補リストＤ２０４がＭＡＰ復号部２０５に出力される（ＳＴ２０３）。
【００９５】
また、メモリ２０４においては、硬判定部２０２から供給される１ｂｉｔ量子化された受信語Ｄ２０３が、限界距離復号部２０３から復号語候補リストが出力されるまで保存される。
そして、復号語候補リストとのＭＡＰ復号の際にＭＡＰ復号部２０５からの要求に応じてこの１ｂｉｔ量子化された受信語Ｄ２０５がＭＡＰ復号部２０５に出力される（ＳＴ２０４）。
【００９６】
そして、ＭＡＰ復号部２０５においては、限界距離復号部２０３から供給される復号語Ｄ２０４およびメモリ２０４から供給される１ｂｉｔ量子化された受信語Ｄ２０５が入力される。ＭＡＰ復号部２０５では、入力した受信語からのハミング距離が最も近い復号語候補が復号語Ｄ２０６として出力される（ＳＴ２０５）。
【００９７】
以上のように、本実施形態では、１ｂｉｔ量子化により硬判定した受信値を保存するため、要素毎に１ｂｉｔ分のメモリを用意するだけでよく、メモリを減らすことができ、回路規模も削減できる。
【００９８】
さらに、復号語候補リストから最適な復号語を選択するために、硬判定された受信値と各復号語候補とのハミング距離を求める際にも、各要素毎に１ｂｉｔ同士の排他的論理和を計算するだけでよいため、少ない計算コストおよび単純な演算回路での回路実装が可能であり、計算所要時間および回路規模の削減が実現される。
【００９９】
なお、以上においては復号装置がリードソロモン符号を復号するように説明したが、これに限らずたとえばＢＣＨ符号を復号してもよいし、それ以外の符号化方式に対して復号を行うようにしても良い。また、ＡＢＰ繰り返し復号で得られたＬＬＲから復号語候補リストを復号する時に硬判定後限界距離復号でなくとも、Ｋ−Ｖリスト復号、もしくは軟値をそのまま入力とした軟判定リスト復号等を適用しても良い。
【０１００】
以上説明したように、本実施形態によれば、既存のＡＢＰを用いた繰り返し復号法と比較して、計算コスト・回路規模を削減した上で同等の復号性能を得ることができる。
また、１ｂｉｔ量子化により硬判定した受信値を保存するため、要素毎に１ｂｉｔ分のメモリを用意するだけでよく、既存の方法よりメモリを減らすことができ、回路規模も削減できる。
さらに、復号語候補リストから最適な復号語を選択するために、硬判定された受信値と各復号語候補とのハミング距離を求める際にも、各要素毎に１ｂｉｔ同士の排他的論理和を計算するだけでよいため、少ない計算コストおよび単純な演算回路での回路実装が可能であり、計算所要時間および回路規模の削減が実現される。
【０１０１】
なお、以上詳細に説明した復号方法は、上記手順に応じたプログラムとして形成し、ＣＰＵ等のコンピュータで実行するように構成することも可能である。
また、このようなプログラムは、半導体メモリ、磁気ディスク、光ディスク、フロッピー（登録商標）ディスク等の記録媒体、この記録媒体をセットしたコンピュータによりアクセスし上記プログラムを実行するように構成可能である。
【図面の簡単な説明】
【０１０２】
【図１】提案されているＡＢＰによる復号のフローチャートである。
【図２】本発明の実施形態に係る復号方法を採用した復号装置の構成例を示すブロック図である。
【図３】本実施形態に係る復号装置における復号処理を説明するためのフローチャートである。
【図４】既存手法および本実施形態に係る手法におけるシミュレーションを用いた復号性能比較のグラフを示す図である。
【図５】回路実装されたＡＢＰ繰り返し復号器に対して、本発明の実施形態に係る復号方法を適用した具体例を示す図である。
【図６】図５の復号装置の動作を説明するための図である。
【符号の説明】
【０１０３】
１００・・・復号装置、１０１・・・軟判定部、１０２・・・ＡＢＰ繰り返し復号部、１０３・・・硬判定部、１０４・・・硬判定後限界距離復号部、１０５・・・ＭＡＰ復号部、１１０・・・リスト取得部、２００・・・復号装置、２０１・・・ＡＢＰ繰り返し復号部、２０２・・・硬判定部、２０３・・・限界距離復号部、２０４・・・メモリ、２０５・・・ＭＡＰ復号部。
【図１】
2008148056.tif 000022
【図２】
2008148056.tif 000023
【図３】
2008148056.tif 000024
【図４】
2008148056.tif 000025
【図５】
2008148056.tif 000026
【図６】
2008148056.tif 000027