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