(57)【要約】【課題】  リスト復号に適していない符号語をリスト復号できるようにする。【解決手段】  リスト復号に適していない符号化方式１で符号化されたデータをリスト復号する場合、リスト復号の１手順である補間処理において、補間点の変更の処理が実行される。その変更は、例えばリードソロモン符号の生成多項式に基づいて補間点を変更する。そして、その変更された補間点を用いて復号された復号語を、リードソロモン符号の生成多項式に基づいて変換し、その変換された復号語から、復号語としての候補のリストが作成される。本発明は、リスト復号を行う復号装置に適用することができる。【選択図】図７
2006042088.tif 000002
【特許請求の範囲】
【請求項１】
有限体Ｆq上で任意に与えられる［ｑ−１，ｋ］リードソロモン符号が施された符号語を入力する入力手段と、
所定の符号位置に基づいて求められる補間点と、その補間点における重複度を用いて、前記入力手段により入力された前記符号語から復号語の候補のリストを作成するリスト作成手段と
を備え、
前記リスト作成手段は、前記リードソロモン符号の生成多項式に基づいて前記補間点を変更し、その変更された前記補間点を用いると共に、取得される復号語を前記生成多項式に基づいて前記復号語の候補を変更し、その変更された前記復号語の候補のリストを作成する
ことを特徴とする復号装置。
【請求項２】
前記リスト作成手段は、前記有限体Ｆqの原始元をα、前記リードソロモン符号の生成多項式を
【数１】
2006042088.tif 000074
とし、前記所定の符号位置に基づいて求められる補間点を
【数２】
2006042088.tif 000075
とした場合、前記補間点を
【数３】
2006042088.tif 000076
と変更し、その変更された補間点を用いて取得される前記復号語（ｄ0，ｄ1，・・・，ｄq-2）を、（ｄ0，α1-bｄ1，・・・，α(q-2)(1-b)ｄq-2）と変更する
ことを特徴とする請求項１に記載の復号装置。
【請求項３】
前記リードソロモン符号が、前記有限体Ｆqの部分体上で部分符号として与えられるＢＣＨ符号である場合、前記リスト作成手段は、前記補間点を変更する前の時点で、前記部分体上のＢＣＨ符号の生成多項式に基づいて前記有限体Ｆq上の前記リードソロモン符号の生成多項式を求め、その生成多項式に基づいて前記補間点の変更および前記復号語の変更を行う
ことを特徴とする請求項１に記載の復号装置。
【請求項４】
前記リスト作成手段は、作成した前記リスト内の前記復号語の候補のうち、全成分が前記部分体に含まれる候補を選択し、その選択された復号語から構成されるリストをさらに作成する
ことを特徴とする請求項３に記載の復号装置。
【請求項５】
有限体Ｆq上で任意に与えられる［ｑ−１，ｋ］リードソロモン符号が施された符号語の入力を制御する入力制御ステップと、
所定の符号位置に基づいて求められる補間点と、その補間点における重複度を用いて、前記入力制御ステップの処理で入力が制御された前記符号語から復号語の候補のリストを作成するリスト作成ステップと
を含み、
前記リスト作成ステップは、前記リードソロモン符号の生成多項式に基づいて前記補間点を変更し、その変更された前記補間点を用いると共に、取得される復号語を前記生成多項式に基づいて前記復号語の候補を変更し、その変更された前記復号語の候補のリストを作成する
ことを特徴とする復号方法。
【請求項６】
有限体Ｆq上で任意に与えられる［ｑ−１，ｋ］リードソロモン符号が施された符号語の入力を制御する入力制御ステップと、
所定の符号位置に基づいて求められる補間点と、その補間点における重複度を用いて、前記入力制御ステップの処理で入力が制御された前記符号語から復号語の候補のリストを作成するリスト作成ステップと
を含む処理をコンピュータに実行させ、
前記リスト作成ステップは、前記リードソロモン符号の生成多項式に基づいて前記補間点を変更し、その変更された前記補間点を用いると共に、取得される復号語を前記生成多項式に基づいて前記復号語の候補を変更し、その変更された前記復号語の候補のリストを作成する
ことを特徴とするプログラム。
【請求項７】
有限体Ｆq上の任意に与えられる［ｑ−１，ｋ］リードソロモン符号の双対符号が施された符号語を入力する入力手段と、
所定の符号位置に基づいて求められる補間点と、その補間点における重複度を用いて、前記入力手段により入力された前記符号語から復号語の候補のリストを作成するリスト作成手段と
を備え、
前記リスト作成手段は、前記リードソロモン符号化の生成多項式に基づいて前記補間点を変更し、その変更された前記補間点を用いると共に、取得される復号語を前記生成多項式に基づいて前記復号語の候補を変更し、その変更された前記復号語の候補のリストを作成する
ことを特徴とする復号装置。
【請求項８】
前記リスト作成手段は、前記有限体Ｆqの原始元をα、前記リードソロモン符号の生成多項式を
【数４】
2006042088.tif 000077
とし、前記所定の符号位置に基づいて求められる補間点を
【数５】
2006042088.tif 000078
とした場合、前記補間点を
【数６】
2006042088.tif 000079
と変更し、その変更された補間点を用いて取得される前記復号語（ｄ0，ｄ1，・・・，ｄq-2）を、（ｄ0，αbｄ1，・・・，αb(q-2)ｄq-2）と変更する
ことを特徴とする請求項７に記載の復号装置。
【請求項９】
前記リードソロモン符号が、前記有限体Ｆqの部分体上で部分符号として与えられるＢＣＨ符号である場合、前記リスト作成手段は、前記補間点を変更する前の時点で、前記部分体上のＢＣＨ符号の生成多項式に基づいて前記有限体Ｆq上の前記リードソロモン符号の生成多項式を求め、その生成多項式に基づいて前記補間点の変更および前記復号語の変更を行う
ことを特徴とする請求項７に記載の復号装置。
【請求項１０】
前記リスト作成手段は、作成した前記リスト内の前記復号語の候補のうち、全成分が前記部分体に含まれる候補を選択し、その選択された復号語から構成されるリストをさらに作成する
ことを特徴とする請求項９に記載の復号装置。
【請求項１１】
有限体Ｆq上の任意に与えられる［ｑ−１，ｋ］リードソロモン符号の双対符号が施された符号語の入力を制御する入力制御ステップと、
所定の符号位置に基づいて求められる補間点と、その補間点における重複度を用いて、前記入力制御ステップの処理で入力が制御された前記符号語から復号語の候補のリストを作成するリスト作成ステップと
を含み、
前記リスト作成ステップは、前記リードソロモン符号化の生成多項式に基づいて前記補間点を変更し、その変更された前記補間点を用いると共に、取得される復号語を前記生成多項式に基づいて前記復号語の候補を変更し、その変更された前記復号語の候補のリストを作成する
ことを特徴とする復号方法。
【請求項１２】
有限体Ｆq上の任意に与えられる［ｑ−１，ｋ］リードソロモン符号の双対符号が施された符号語の入力を制御する入力制御ステップと、
所定の符号位置に基づいて求められる補間点と、その補間点における重複度を用いて、前記入力制御ステップの処理で入力が制御された前記符号語から復号語の候補のリストを作成するリスト作成ステップと
を含む処理をコンピュータに実行させ、
前記リスト作成ステップは、前記リードソロモン符号化の生成多項式に基づいて前記補間点を変更し、その変更された前記補間点を用いると共に、取得される復号語を前記生成多項式に基づいて前記復号語の候補を変更し、その変更された前記復号語の候補のリストを作成する
ことを特徴とするプログラム。
【請求項１３】
有限体上で与えられる任意の［ｑ−１，ｋ］リードソロモン符号化を行う符号化装置において、
情報ビットを係数にもつLaurent多項式の、所定の符号位置における値を符号語の各要素とする符号化を行う
ことを特徴とする符号化装置。
【請求項１４】
有限体上で与えられる任意の［ｑ−１，ｋ］リードソロモン符号化を行う符号化装置の符号化方法において、
情報ビットを係数にもつLaurent多項式の、所定の符号位置における値を符号語の各要素とする符号化を行う
ことを特徴とする符号化方法。
【請求項１５】
有限体上で与えられる任意の［ｑ−１，ｋ］リードソロモン符号化を行う符号化装置の符号化を制御するコンピュータのプログラムであって、
情報ビットを係数にもつLaurent多項式の、所定の符号位置における値を符号語の各要素とする符号化を行う
ことを特徴とするプログラム。
【請求項１６】
有限体上で与えられる任意の［ｑ−１，ｋ］リードソロモン符号化を行う符号化装置において、
情報ビットを係数にもつ多項式の、所定の符号位置における値を符号語の各要素とする符号化を行う
ことを特徴とする符号化装置。
【請求項１７】
有限体上で与えられる任意の［ｑ−１，ｋ］リードソロモン符号化を行う符号化装置の符号化方法において、
情報ビットを係数にもつ多項式の、所定の符号位置における値を符号語の各要素とする符号化を行う
ことを特徴とする符号化方法。
【請求項１８】
有限体上で与えられる任意の［ｑ−１，ｋ］リードソロモン符号化を行う符号化装置の符号化を制御するコンピュータのプログラムであって、
情報ビットを係数にもつ多項式の、所定の符号位置における値を符号語の各要素とする符号化を行う
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、復号装置および方法、符号化装置および方法、並びにプログラムに関し、特に、エラー訂正をより精度良く行えるようにする復号装置および方法、符号化装置および方法、並びにプログラムに関する。
【背景技術】
【０００２】
データが供給される際、そのデータを効率良く供給するために、符号化などの処理が実行される。データは、所定の信号にのせられて送信されることにより相手側に供給される、所定の記録媒体に記録された状態で相手側に供給されるなどの形態が考えられる。また、データの供給を受ける側は、供給を受けたデータを正確に再生するために、供給されたデータの符号化方式にあった復号方式でデータを再生する。
【０００３】
データの授受が行われる際、符号化や復号といった処理が行われるが、データが供給される際、伝送路上でデータが送信されるときや、記録媒体からデータが読み出されるときにノイズがのってしまうなどの原因により、復号結果にエラーが発生する可能性がある。よって、復号時に、エラーをいかにして訂正するかが問題となる。エラーを訂正し、精度良くデータを再生するための符号化方式や復号方式が提案されている。
【０００４】
符号化や復号の方式として、リードソロモン（Reed-Solomon）符号がある。リードソロモン符号の符号化法は、大きく分けて２つの符号化法がある。その２つの符号化方式を、それぞれ符号化方式１、符号化方式２として、簡便に以下に説明を加える。
【０００５】
［符号化方式１について］
符号化方式１は、巡回符号とし、生成多項式
【数１】
2006042088.tif 000003
を与え、情報ビットを係数にもつ多項式
【数２】
2006042088.tif 000004
に対して、
Ｃ（ｘ）＝ｆ（ｘ）ｇ（ｘ）
と定義される有限体Ｆの係数が高々ｎの多項式
【数３】
2006042088.tif 000005
の係数の組を
（Ｃ0，Ｃ1，Ｃ2，Ｃ3，・・・，Ｃn―1）：符号語
として符号化する方法である。
【０００６】
［符号化方法２について］
符号化方式２は、有限体の異なる元からなる集合として定義される符号位置
１，α，α2，α3，・・・，αq-2
を与え、情報ビットを係数にもつ多項式
【数４】
2006042088.tif 000006
を用いて
（ｆ（１），ｆ（α），ｆ（α2），・・・，ｆ（αn-1））：符号語
として符号化する方法である。
【０００７】
このような代数幾何符号であるリードソロモン符号や、その部分体部分符号としてのＢＣＨ（Bose-Chaudhuri-Hocquenghem）符号には、その代数的な性質を利用し、性能や計算コストの両面で良い結果が得られる復号法が提案されている。
【０００８】
［復号法について］
例えば、符号長ｎ、情報長ｋ、有限体Ｆｑ（ｑ＝ｐm、ｐは素数）、最小距離ｄ＝ｎ−ｋのリードソロモン符号をＲＳ（ｎ，ｋ）としたとき、硬判定受信語をハミング（Hamming）距離が最小の符号語に復号する限界距離復号（以下、適宜、通常復号と記述する）は、ｄ／２以下の最大の整数を満たすｔ個の誤りシンボルの訂正が保証されている。
【０００９】
ここで、受信語ｙと符号語ｃのハミング距離ｄH（ｙ，ｃ）は、
ｄH（ｙ，ｃ）＝０（ｙi＝ｃiのとき）
＝ｉ（ｙi≠ｃiのとき）
のことである。
【００１０】
データを復号する方法としてリスト復号と称される復号方式もある。上記した通常復号は、送信されてきたデータが何であるかを、一意に推定するが、リスト復号においては、複数の推定結果を示すような復号が行われる。リスト復号は、復号結果の出し方（例えば、幾つの結果を提示するか）や、その結果の使い方（例えば、提示された結果のうちどの結果を復号結果として採用するか）などにより、通常の復号より（１つの復号結果を提示し、その結果を復号結果として採用するような場合より）、信頼度を向上できる場合がある。そこで、リスト復号を行うことで、より精度良くデータを再生する復号方式が提案されている。
【００１１】
例えば、Guruswami-Sudanによるリスト復号（例えば、非特許文献１参照）や、Guruswami-Sudanによるリスト復号を拡張したKoetter-Vardyによるリスト復号（例えば、非特許文献２参照）が提案されている。また、これらのリスト復号の方式を適用した場合においても、Re-encode（再エンコード）により、計算コストなどを実用可能な範囲まで削減できるということも提案されている。（例えば、非特許文献３参照）
【非特許文献１】V.Guruswami, M.Sudan， Improved decoding of Reed-Solomon and Algebraic-Geometry codes，IEEE Transactions on Information Theory， VOL.45， pp1787-1767，1999.
【非特許文献２】R.Koetter, A.Vardy, Algebraic soft-decision decoding of Reed-Solomon codes, IEEE Transactions on Information Theory，2001.
【非特許文献３】R.Koetter, J.Ma, A.Vardy, A.Ahmed, Efficient Interpolation and Factorization in Algebraic Aoft-Decision Decoding of Reed-Solomon codes, Proceedings of ISIT2003.
【発明の開示】
【発明が解決しようとする課題】
【００１２】
リスト復号は、上述したように通常復号よりも精度良くエラーを訂正できる（結果として精度良くデータを再生できる）復号方式として提案されている。そこで復号方式として、リスト復号を適用するようにした場合、リスト復号に適した符号化が行われる必要がある。
【００１３】
しかしながら、リスト復号による復号方式は、符号化方式として上述した符号化方式２が適用されたときに適用できる方式として定義されている。すなわち、符号化方式２のように定義された符号に対して、リスト復号が提案されている。
【００１４】
よって、リスト復号を適用するには、符号化方式２で符号化する必要があり、符号化方式１で符号化された符号語に対してはリスト復号方式を適用することができないといった課題があった。
【００１５】
また、デジタル放送などでは、データは、短縮符号などと称され２０４バイト（２０４シンボル）で伝送が行われているが、非特許文献１や非特許文献２で提案されているリスト復号方式では、２５５バイト（２５５シンボル）でデータを扱うことが前提とされている。そのため、２０４バイトのデータを、非特許文献１や非特許文献２で提案されているリスト復号方式をそのまま適用して復号した場合、正確に復号できないといった課題があった。
【００１６】
換言すれば、非特許文献１や非特許文献２に記載されているリスト復号は、受信されたシンボルより得られる信頼度を用いて復号を行う方式であるため、受信されていないシンボルをもつ短縮符号（例えば、上述したように２０４シンボルの符号）の復号には対応してないといった課題があった。そのため、より精度良く復号を行うためにリスト復号を、現行のデジタル放送などの方式に対して適用しようとしても適用できないといった課題があった。
【００１７】
本発明はこのような状況に鑑みてなされたものであり、リスト復号を適用できるようにすることを目的とする。
【課題を解決するための手段】
【００１８】
本発明の復号装置は、有限体Ｆq上で任意に与えられる［ｑ−１，ｋ］リードソロモン符号が施された符号語を入力する入力手段と、所定の符号位置に基づいて求められる補間点と、その補間点における重複度を用いて、入力手段により入力された符号語から復号語の候補のリストを作成するリスト作成手段とを備え、リスト作成手段は、リードソロモン符号の生成多項式に基づいて補間点を変更し、その変更された補間点を用いると共に、取得される復号語を生成多項式に基づいて復号語の候補を変更し、その変更された復号語の候補のリストを作成することを特徴とする。
【００１９】
リスト作成手段は、有限体Ｆqの原始元をα、リードソロモン符号の生成多項式と、所定の符号位置に基づいて求められる補間点を用いて、その補間点を変更し、その変更された補間点を用いて取得される復号語（ｄ0，ｄ1，・・・，ｄq-2）を、（ｄ0，α1-bｄ1，・・・，α(q-2)(1-b)ｄq-2）と変更することを特徴とする。
【００２０】
リードソロモン符号が、有限体Ｆqの部分体上で部分符号として与えられるＢＣＨ符号である場合、リスト作成手段は、補間点を変更する前の時点で、部分体上のＢＣＨ符号の生成多項式に基づいて有限体Ｆq上のリードソロモン符号の生成多項式を求め、その生成多項式に基づいて補間点の変更および復号語の変更を行うようにすることができる。
【００２１】
リスト作成手段は、作成したリスト内の復号語の候補のうち、全成分が部分体に含まれる候補を選択し、その選択された復号語から構成されるリストをさらに作成するようにすることができる。
【００２２】
本発明の復号方法は、有限体Ｆq上で任意に与えられる［ｑ−１，ｋ］リードソロモン符号が施された符号語の入力を制御する入力制御ステップと、所定の符号位置に基づいて求められる補間点と、その補間点における重複度を用いて、入力制御ステップの処理で入力が制御された符号語から復号語の候補のリストを作成するリスト作成ステップとを含み、リスト作成ステップは、リードソロモン符号の生成多項式に基づいて補間点を変更し、その変更された補間点を用いると共に、取得される復号語を生成多項式に基づいて復号語の候補を変更し、その変更された復号語の候補のリストを作成することを特徴とする。
【００２３】
本発明のプログラムは、有限体Ｆq上で任意に与えられる［ｑ−１，ｋ］リードソロモン符号が施された符号語の入力を制御する入力制御ステップと、所定の符号位置に基づいて求められる補間点と、その補間点における重複度を用いて、入力制御ステップの処理で入力が制御された符号語から復号語の候補のリストを作成するリスト作成ステップとを含む処理をコンピュータに実行させ、リスト作成ステップは、リードソロモン符号の生成多項式に基づいて補間点を変更し、その変更された補間点を用いると共に、取得される復号語を生成多項式に基づいて復号語の候補を変更し、その変更された復号語の候補のリストを作成することを特徴とする。
【００２４】
本発明の復号装置は、有限体Ｆq上の任意に与えられる［ｑ−１，ｋ］リードソロモン符号の双対符号が施された符号語を入力する入力手段と、所定の符号位置に基づいて求められる補間点と、その補間点における重複度を用いて、入力手段により入力された符号語から復号語の候補のリストを作成するリスト作成手段とを備え、リスト作成手段は、リードソロモン符号化の生成多項式に基づいて補間点を変更し、その変更された補間点を用いると共に、取得される復号語を生成多項式に基づいて復号語の候補を変更し、その変更された復号語の候補のリストを作成することを特徴とする。
【００２５】
リスト作成手段は、有限体Ｆqの原始元をα、リードソロモン符号の生成多項式と、所定の符号位置に基づいて求められる補間点とを用い、その補間点を変更し、その変更された補間点を用いて取得される復号語（ｄ0，ｄ1，・・・，ｄq-2）を、（ｄ0，αbｄ1，・・・，αb(q-2)ｄq-2）と変更するようにすることができる。
【００２６】
本発明の復号装置は、リードソロモン符号が、有限体Ｆqの部分体上で部分符号として与えられるＢＣＨ符号である場合、リスト作成手段は、補間点を変更する前の時点で、部分体上のＢＣＨ符号の生成多項式に基づいて有限体Ｆq上のリードソロモン符号の生成多項式を求め、その生成多項式に基づいて補間点の変更および復号語の変更を行うことを特徴とする。
【００２７】
リスト作成手段は、作成したリスト内の復号語の候補のうち、全成分が部分体に含まれる候補を選択し、その選択された復号語から構成されるリストをさらに作成するようにすることができる。
【００２８】
本発明の復号方法は、有限体Ｆq上の任意に与えられる［ｑ−１，ｋ］リードソロモン符号の双対符号が施された符号語の入力を制御する入力制御ステップと、所定の符号位置に基づいて求められる補間点と、その補間点における重複度を用いて、入力制御ステップの処理で入力が制御された符号語から復号語の候補のリストを作成するリスト作成ステップとを含み、リスト作成ステップは、リードソロモン符号化の生成多項式に基づいて補間点を変更し、その変更された補間点を用いると共に、取得される復号語を生成多項式に基づいて復号語の候補を変更し、その変更された復号語の候補のリストを作成することを特徴とする。
【００２９】
本発明のプログラムは、有限体Ｆq上の任意に与えられる［ｑ−１，ｋ］リードソロモン符号の双対符号が施された符号語の入力を制御する入力制御ステップと、所定の符号位置に基づいて求められる補間点と、その補間点における重複度を用いて、入力制御ステップの処理で入力が制御された符号語から復号語の候補のリストを作成するリスト作成ステップとを含む処理をコンピュータに実行させ、リスト作成ステップは、リードソロモン符号化の生成多項式に基づいて補間点を変更し、その変更された補間点を用いると共に、取得される復号語を生成多項式に基づいて復号語の候補を変更し、その変更された復号語の候補のリストを作成することを特徴とする。
【００３０】
本発明の復号化装置は、有限体上で与えられる任意の［ｑ−１，ｋ］リードソロモン符号化を行う符号化装置において、情報ビットを係数にもつLaurent多項式の、所定の符号位置における値を符号語の各要素とする符号化を行うことを特徴とする。
【００３１】
本発明の符号化方法は、有限体上で与えられる任意の［ｑ−１，ｋ］リードソロモン符号化を行う符号化装置の符号化方法において、情報ビットを係数にもつLaurent多項式の、所定の符号位置における値を符号語の各要素とする符号化を行うことを特徴とする。
【００３２】
本発明のプログラムは、有限体上で与えられる任意の［ｑ−１，ｋ］リードソロモン符号化を行う符号化装置の符号化を制御するコンピュータのプログラムであって、情報ビットを係数にもつLaurent多項式の、所定の符号位置における値を符号語の各要素とする符号化を行うことを特徴とする。
【００３３】
本発明の符号化装置は、有限体上で与えられる任意の［ｑ−１，ｋ］リードソロモン符号化を行う符号化装置において、情報ビットを係数にもつ多項式の、所定の符号位置における値を符号語の各要素とする符号化を行うことを特徴とする。
【００３４】
本発明の符号化方法は、有限体上で与えられる任意の［ｑ−１，ｋ］リードソロモン符号化を行う符号化装置の符号化方法において、情報ビットを係数にもつ多項式の、所定の符号位置における値を符号語の各要素とする符号化を行うことを特徴とする。
【００３５】
本発明の符号化方式は、有限体上で与えられる任意の［ｑ−１，ｋ］リードソロモン符号化を行う符号化装置の符号化を制御するコンピュータのプログラムであって、情報ビットを係数にもつ多項式の、所定の符号位置における値を符号語の各要素とする符号化を行うことを特徴とする。
【００３６】
本発明の復号装置および方法、並びにプログラムにおいては、復号するデータをリスト復号に適したデータに変換するために、補間点が変更され、その変更された補間点が用いられ復号語の候補が生成され、さらに、その候補が生成多項式に基づいて変更される。
【００３７】
本発明の符号化装置および方法、並びにプログラムにおいては、リスト復号に適した符号化を行うために、情報ビットを係数に持つ多項式の所定の符号位置における値が符号語の各要素となる符号化が行なわれる。
【発明の効果】
【００３８】
本発明によれば、リスト復号を適用するための符号化を行うことが可能となる。
【００３９】
また、本発明によれば、リスト復号として、Guruswami-Sudanによるリスト復号やKoetter-Vardyによるリスト復号を適用することが可能となる。よって、より精度良くエラー訂正を行うことが可能となり、より正確なデータに復号することが可能となる。
【発明を実施するための最良の形態】
【００４０】
以下に本発明の最良の形態を説明するが、開示される発明と実施の形態との対応関係を例示すると、次のようになる。明細書中には記載されているが、発明に対応するものとして、ここには記載されていない実施の形態があったとしても、そのことは、その実施の形態が、その発明に対応するものではないことを意味するものではない。逆に、実施の形態が発明に対応するものとしてここに記載されていたとしても、そのことは、その実施の形態が、その発明以外の発明には対応しないものであることを意味するものでもない。
【００４１】
さらに、この記載は、明細書に記載されている発明の全てを意味するものではない。換言すれば、この記載は、明細書に記載されている発明であって、この出願では請求されていない発明の存在、すなわち、将来、分割出願されたり、補正により出現し、追加されたりする発明の存在を否定するものではない。
【００４２】
本発明の復号装置は、有限体Ｆq上で任意に与えられる［ｑ−１，ｋ］リードソロモン符号が施された符号語を入力する入力手段（例えば、図６の入力部１０１）と、所定の符号位置に基づいて求められる補間点と、その補間点における重複度を用いて、入力手段により入力された符号語から復号語の候補のリストを作成するリスト作成手段（例えば、図６のリスト作成部１０７）とを備え、リスト作成手段は、リードソロモン符号の生成多項式に基づいて補間点を変更し、その変更された補間点を用いると共に、取得される復号語を生成多項式に基づいて復号語の候補を変更し、その変更された復号語の候補のリストを作成することを特徴とする。
【００４３】
本発明の復号装置は、有限体Ｆq上の任意に与えられる［ｑ−１，ｋ］リードソロモン符号の双対符号が施された符号語を入力する入力手段（例えば、図６の入力部１０１）と、所定の符号位置に基づいて求められる補間点と、その補間点における重複度を用いて、入力手段により入力された符号語から復号語の候補のリストを作成するリスト作成手段（例えば、図６のリスト作成部１０７）とを備え、リスト作成手段は、リードソロモン符号化の生成多項式に基づいて補間点を変更し、その変更された補間点を用いると共に、取得される復号語を生成多項式に基づいて復号語の候補を変更し、その変更された復号語の候補のリストを作成することを特徴とする。
【００４４】
以下に、本発明の実施の形態について図面を参照して説明する。
【００４５】
［システム構成］
図１は、本発明が適用されるシステムの一実施の形態の構成を示す図である。図１に示したシステムにおいては、符号化器１において、所定の符号化方式に基づいて符号化されたデータが、例えば、テレビジョン放送として復号器２に供給される。テレビジョン放送としてデータが送信される場合、その形態は、地上波放送、衛星放送、ケーブルテレビジョン放送などであり、以下に説明する本発明は、これらの形態のいずれにも適用することが可能である。
【００４６】
また、符号化器１により符号化されたデータは、所定の記録媒体３に記録され、記録媒体３に記録された状態で、復号器２に供給される。記録媒体３は、例えば、フレキシブルディスクなどの磁気ディスク、CD-ROM（Compact Disc-Read Only Memory）やDVD（Digital Versatile Disc）などの光ディスク、MD（Mini-Disc）（登録商標）などの光磁気ディスク、メモリースティック（登録商標）などの半導体メモリなどである。
【００４７】
［具体的なシステム構成１］
図２は、具体的なシステム構成を示す図である。図２に示したシステムは、例えば、デジタルテレビジョン放送などのデジタル信号を送受信するシステムである。符号化器１は、ＲＳ（Reed-Solomon：リードソロモン）符号化部２１、インタリーブ（Interleave）部２２、および、畳み込み符号化部２３から構成されている。符号化器１からのデータは、所定のチャネル３１を介して復号器２に供給される構成とされている。復号器２は、畳み込み復号部４１、デインタリーブ（DeInterleve）部４２、および、リスト復号部４３から構成されている。
【００４８】
符号化器１のＲＳ符号化部２１は、リードソロモン符号化方式に基づき、入力されたデータを符号化し、インタリーブ部２２に供給する。インタリーブ部２２は、供給されたデータに対し、そのデータの一連の連続性を保ちながら、構成要素を互いに入れ換えて配置するといった処理を施す。このような処理が行われることにより、バーストエラーに対する耐久性を高めることが可能となる。
【００４９】
インタリーブ部２２による処理が施されたデータは、畳み込み符号化部２３に供給される。畳み込み符号化部２３は、供給されたデータに対して畳み込み符号化を行い、チャネル３１を介して、そのデータを復号器２に供給する。
【００５０】
復号器２は、基本的に、符号化器１において行われた符号化の逆の処理を実行する。復号器２の畳み込み復号部４１は、供給されたデータに対し、畳み込み符号化部２３に対応する復号を行い、デインタリーブ部４２に出力する。デインタリーブ部４２は、インタリーブ部２２により入れ換えて配置されたデータを、入れ換えられる前の状態に戻す処理を実行する。
【００５１】
デインタリーブ部４２により配置が元に戻されたデータは、リスト復号部４３に供給される。リスト復号部４３は、リスト復号を行う。このリスト復号部４３において行われるリスト復号については後述する。
【００５２】
［具体的なシステム構成２］
図３は、他のシステム構成を示す図である。図３に示したシステムは、例えば、デジタルテレビジョン放送などのデジタル信号を送受信するシステムである。図３に示したシステムのうち、符号化器１に関する構成は、図２に示した符号化器１と同様の構成なので、その説明は省略する。
【００５３】
符号化器１で符号化されたデータは、所定のチャネル３１を介して復号器２に供給される。図３に示した復号器２は畳み込み復号部５１、デインタリーブ部５２、リスト復号部５３、およびインタリーブ部５４から構成されている。図３に示した復号器２では、リスト復号が繰り返し行われる構成とされている。
【００５４】
畳み込み復号部５１には、チャネル３１を介して符号化器１から供給されたデータと、インタリーブ部５４から出力されたデータが供給される。畳み込み復号部５１は、供給されたデータを用いた畳み込み復号を行い、その結果をデインタリーブ部５２に供給する。デインタリーブ部５２は、図２に示したデインタリーブ部４２と同様の処理を実行する。すなわち、供給されたデータを、インタリーブされる前の配置のデータに配置し直す処理が実行される。
【００５５】
デインタリーブ部５２からの出力は、リスト復号部５３に供給される。リスト復号部５３は、基本的に、図２のリスト復号部４３と同様の処理により、供給されたデータをリスト復号する。復号されたデータは、復号結果として、図示されていない後段の処理部に供給されると共に、インタリーブ部５４にも供給される。インタリーブ部５４は、供給されたデータの配置を入れ換える。すなわち、基本的に、符号化部１のインタリーブ部２２と同様の処理を実行する。
【００５６】
畳み込み復号部５１には、一旦復号された後、再度インタリーブの処理が施されたデータと、符号化器１においてインタリーブの処理が施されたデータが供給されることになる。
【００５７】
このように、デインタリーブとインタリーブの処理が繰り返し行われることにより復号が行われる場合、図２に示したような１回だけデインタリーブの処理が行われて復号される場合と比較して、より精度良くエラー訂正を行うことができ、より精度良く復号できるようになる。
【００５８】
図２または図３に示した復号器２においては、リスト復号部４３やリスト復号部５３によりリスト復号が行われるとして説明した。従来のシステムでは、リスト復号の代わりにＲＳ復号が行われていた。換言すれば、従来のシステムでは、ＲＳ符号化部２１によりＲＳ符号化が行われ、畳み込み符号化部２３により畳み込み符号化が行われたデータ（送信語）に対して、畳み込み符号の復号、軟判定後のＲＳ通常復号が行われていた（通常復号が行われていた）。
【００５９】
このような従来のシステムに対し、本実施の形態においては、リスト復号が行われる。本実施の形態においても送信語としては、従来のシステムと同様、ＲＳ符号化が行われ、畳み込み符号化が行われたデータである。しかしながら、本実施の形態において、その送信語を受信する復号側では、畳み込み符号の軟出力復号をした後に、既知のシンボルの重複度が十分大きく設定されることによりリスト復号が行われる構成とされる。
【００６０】
ここで、畳み込み符号の軟出力復号とは、例えば、ＢＣＪＲ（Bahl, Cocke, Jelinek and Raviv）アルゴリズムやＳＯＶＡ（Soft-Output Viterbi Algorithm）による復号である。リスト復号部４３（図２）やリスト復号部５３（図３）が、軟判定復号を行う場合、畳み込み符号の軟出力は、そのままリスト復号部４３，５３に供給される構成とすることが可能である。
【００６１】
［具体的なシステム構成３］
図４は、他のシステム構成を示す図である。図４に示したシステムは、例えば、記録媒体３としてＤＶＤ（Digital Versatile Disc）が用いられ、その記録媒体３にデータが記録され、その記録媒体３に記録されたデータが再生される際のシステムである。
【００６２】
図４に示したシステムの符号化器１は、ｎ次元ＲＳ積符号化を行う。ｎ次元ＲＳ積符号化を行うために符号化器１は、１次元目乃至ｎ次元目までのＲＳ符号化をそれぞれ行うＲＳ符号化部６１−１乃至６１−ｎ個のＲＳ符号化部を備える構成とされている。復号器２は、ｎ次元ＲＳ積符号化されたデータを復号するために、１次元目乃至ｎ次元目までのリスト復号をそれぞれ行うリスト復号部７１―１乃至７１−ｎを備える構成とされている。
【００６３】
符号化器１は、入力されたデータをまず、ＲＳ符号化部６１−１において、１次元目のＲＳ符号化を行う。ＲＳ符号化部６１−１からの出力は、ＲＳ符号化部６１−２に供給され、２次元目のＲＳ符号化が行われる。このように、順次ｎ次元目までＲＳ符号化が繰り返される。このようにｎ次元目までの積符号化が行われたデータは、記録媒体３に記録され、復号器２に供給される。
【００６４】
復号器２は、記録媒体３から読み出されたデータをまず、リスト復号部７１−ｎにおいて、ｎ次元目のリスト復号を行う。このリスト復号部７１―ｎにおいて行われるｎ次元目のリスト復号は、ＲＳ符号化部６１−ｎで行われるｎ次元目の符号化に対応した復号処理である。
【００６５】
リスト復号部７１−ｎからの出力されたデータは、リスト復号部７１−（ｎ−１）（図４においては不図示）に供給され、同じくリスト復号が施される。このように、順次１次元目までリスト復号が繰り返される。
【００６６】
このように複数回（図４に示した例ではｎ回）の符号化、リスト復号が行われることにより、より強力なエラー訂正能力を有する符号化、リスト復号を行うことが可能となる。
【００６７】
なお、リスト復号部７１−１乃至７１−ｎは、基本的に同様のリスト復号（この復号に関する説明は後述する）を行うため、リスト復号部７１−１乃至７１−ｎを個々に区別する必要がない場合、単に、リスト復号部７１と記述する。
【００６８】
従来のシステムにおいては、ｎ次元のＲＳ積符号化されたデータに対して、軟判定後、ｎ次元のＲＳ通常復号が行われていた。これに対し本実施の形態においては、ｎ次元のＲＳ積符号化されたデータに対して、既知シンボルの重複度を十分大きく設定することによりリスト復号を各次元に対して行う構成とする。
【００６９】
［具体的なシステム構成４］
図５は、他のシステム構成を示す図である。図５に示したシステムは、図４に示したシステムと同様に、例えば、記録媒体３としてＤＶＤが用いられ、その記録媒体３にデータが記録され、その記録媒体３に記録されたデータが再生される際のシステムである。
【００７０】
図５に示したシステムのうち、符号化器１の構成は、図４に示した符号化器１の構成と同様であり、ＲＳ積符号化を行う構成とされている。ＲＳ積符号化されたデータは、記録媒体３に記録され、復号器２に供給される。復号器２は、まず、リスト復号部８１−ｎにおいて、供給されたデータをリスト復号する。ｎ次元目のリスト復号がリスト復号部８１−ｎにおいて行われると、その後、順次、１次元目のリスト復号まで、繰り返しリスト復号が行われる。
【００７１】
リスト復号部８１−１において、１次元目のリスト復号が行われると、その復号結果は、リスト復号部８２−ｎに供給される。リスト復号部８２−ｎにおいて、再度、ｎ次元目のリスト復号が行われる。その後、順次、１次元目のリスト復号まで、繰り返しリスト復号が、リスト復号部８２−（ｎ−１）乃至８２−１により行われる。
【００７２】
さらに、その後、同様なｎ次元のリスト復号が繰り返し行われる。そして、ｍ段目のリスト復号部ｍ−ｎ乃至ｍ−１のそれぞれにおいて、リスト復号が行われると、その結果は、図示されていない後段の処理に供給される。
【００７３】
このように、図５に示した復号器２においては、ｎ次元目乃至１次元目までのリスト復号が、ｍ段繰り返し行われる。このように、複数回繰り返しリスト復号が行われることにより、より精度良くエラー訂正を行うことが可能となる。
【００７４】
なお、リスト復号部８１−１乃至８１−ｎ、リスト復号部８２−１乃至８２−ｎ、リスト復号部ｍ−１乃至ｍ−ｎは、基本的に同様のリスト復号を行うため、これらのリスト復号部を個々に区別する必要がない場合、単に、リスト復号部８１と記述する。
【００７５】
従来のシステムにおいては、ｎ次元のＲＳ積符号化されたデータに対して、軟判定後、ｎ次元のＲＳ通常復号が行われていた。これに対し本実施の形態においては、ｎ次元のＲＳ積符号化されたデータに対して、既知シンボルの重複度を十分大きく設定することにより、複数のリスト復号部８１によりリスト復号が各次元に対して繰り返し行われる構成とする。
【００７６】
以下に、図２乃至図５に示したリスト復号部４３，５３，７１，８１において実行されるリスト復号について説明する。リスト復号部４３，５３，７１，８１は、基本的に同様の処理を実行するので、以下の説明においては、リスト復号部４３を例に挙げて説明する。
【００７７】
ここで、リスト復号部４３において行われるリスト復号について説明する前に、一般的なリスト復号について説明を加える。リードソロモン（ＲＳ）符号化法については、上述したように、符号化方式１と符号化方式２がある。リスト復号法は、符号化方式２に対して行われるように提案されている。本実施の形態においては、符号化方式１に対してもリスト復号が行えるように、補間点の変更などの処理（後述）が実行されるようにする。
【００７８】
［リスト復号に適用される符号化方式について］
ここで、符号化方式１と符号化方式２について、再度説明を加える。ＲＳ符号の符号化法として、生成多項式を用いた巡回符号としての符号化方式（生成多項式符号化などと称されることがあるが、ここでは、符号化方式１と称する）がある。この符号化方式１における符号化の手順を示す。
【００７９】
［符号化方式１（生成多項式符号化）について］
有限体Ｆqの原始根をα、
生成多項式を
【数５】
2006042088.tif 000007
情報語をｆ＝（ｆ0，ｆ1，ｆ2，・・・，ｆk-1）、
対応する情報多項式をｆ（ｘ）＝ｆ0＋ｆ1ｘ＋ｆ2ｘ2＋・・・＋ｆk-1ｘk-1
としたとき、
符号化方式１（生成多項式符号化）による符号語ｃ＝（ｃ0，ｃ1，ｃ2，・・・，ｃn-1）に対応する符号多項式は、
ｃ（ｘ）＝ｃ0＋ｃ1ｘ＋ｃ2ｘ2＋・・・＋ｃn-1ｘn-1
＝ｇ（ｘ）ｆ（ｘ）    ｍｏｄ（ｘq―1−１）
となる。
【００８０】
さらに、同じ符号空間への符号化として、組織的符号化がある。
ｃ（ｘ）＝ｃ0＋ｃ1ｘ＋ｃ2ｘ2＋・・・＋ｃn-1ｘn-1
＝ｆ（ｘ）ｘn―k＋ｐ（ｘ）    ｍｏｄ（ｘq―1−１）
ここで ｐ（ｘ） は、 ｆ（ｘ）ｘn-k を ｇ（ｘ） で除算したときの余りである。
【００８１】
特に組織的符号化を行った場合、
符号語ｃ＝（ｃ0，ｃ1，ｃ2，・・・，ｃn-1）
＝（ｐ0，ｐ1，・・・ｐn-k-1，ｆ0，ｆ1，ｆ2，・・・，ｆK-1）
となっている。この際、ｐ＝（ｐ0，ｐ1，・・・ｐn-k-1）はパリティと称される。また、ｎ＝ｑ−１のとき、ＲＳ符号は、原始的であると言われる。
【００８２】
［符号化方式２（符号位置符号化）について］
次に符号化方式２について説明を加える。符号化方式２は、符号化位置符号化などと称されることがある。
【００８３】
情報語をｆ＝（ｆ0，ｆ1，ｆ2，・・・，ｆk-1）、
対応する情報多項式を
ｆ（ｘ）＝ｆ0＋ｆ1ｘ＋ｆ2ｘ2＋・・・＋ｆk-1ｘk-1
符号位置を｛α0，α1，α2，・・・，αn-1｝（αi∈Ｆq）
としたとき、
符号位置符号化（符号化方式２）による符号語ｃは、
ｃ＝（ｃ0，ｃ1，ｃ2，・・・，ｃn-1）
＝（ｆ（α0），ｆ（α1），ｆ（α2），・・・，ｆ（αn-1））
となる。
【００８４】
特にｎ＝ｑ−１、かつ、符号位置を｛α0，α1，α2，・・・，αn-1｝と取ると、巡回符号となることが知られている。
【００８５】
このような符号化方式２により符号化されたデータに対してリスト復号を行うことは一般的に提案されている。しかしながら、符号化方式１により符号化されたデータに対してリスト復号を行うことは提案されていない。
【００８６】
そこで本実施の形態においては、符号化方式１により符号化されたデータに対してもリスト復号を適用できるようにするための処理が、復号器２側（復号部４３）で行われるようにする。その処理の詳細な説明は後述するが、簡便にその処理について、ここで説明を加えておく。
【００８７】
上述したように、生成多項式符号化方式と符号位置符号化方式という２つの符号化方式がある。
【００８８】
生成多項式符号化方式と符号位置符号化方式という２定義によるリードソロモン符号の族は異なるが、生成多項式符号化方式で符号化（符号化方式１により符号化）された任意のリードソロモン符号は、正則写像により符号位置｛α0，α1，α2，・・・，αn-1｝の符号位置符号化方式で符号化（符号化方式２により符号化）されたリードソロモンに写される。このことを利用し、生成多項式符号化されたデータを、符号位置符号化されたデータと同等に扱い、リスト復号を実行するようにする。
【００８９】
また、生成多項式符号化を行い、かつ、原始的でなかった場合、ｑ−１−ｎシンボルに０を充当した短縮符号を用いることにより、符号化効率を挙げることなく、送信や復号を行えるようにする。このような手法は、例えば、衛星放送の規格、例えば、ＤＶＢ−Ｓ（Digital Video Broadcasting-Satellite）、ＩＳＤＢ―Ｓ（Integrated Services Digital Broadcasting-Satellite）などに適用することができる。
【００９０】
［提案されているリスト復号について］
まず、一般的に提案されているリスト復号について説明する。リスト復号の手順としては、大きくわけて、信頼度計算の処理、重複度計算の処理、補間の処理、因子決定の処理、リスト作成の処理がある。
【００９１】
信頼度計算は、受信されたシンボルから得られる信頼度を用いて行われる。そして、その信頼度を用いた信頼度計算の結果が用いられ、重複度計算が行われる。重複度計算の処理は、まず、
符号位置｛α0，α1，α2，・・・，αq-2｝に対して、
補間点
【数６】
2006042088.tif 000008
および、
各補間点に対して重複度
【数７】
2006042088.tif 000009
が与えられる。但し、Ｍは自然数であり、ｉpは、１≦ｉ1，ｉ2，・・・ｉM≦ｑ−２を満たす数である。
【００９２】
補間の処理は、与えられた全ての補間点を、与えられた重複度で通るような（１、ｋ−１）重み次数が最小になるような２変数多項式を決定することにより行われる。
【００９３】
因子決定の処理は、補間の処理により決定された２変数多項式から、
【数８】
2006042088.tif 000010
という形の因子を全て求めることにより行われる。
【００９４】
リスト作成の処理は、因子決定の処理で求められた全ての因子ｙに対して、
（ｈ（１），ｈ（α），ｈ（α2），・・・，ｈ（αn-1））
という復号語を求め、その復号語のリストを作成する。
【００９５】
このようなリスト復号における補間点、その個数、重複度などの決定方法の一提案として、例えば、文献１乃至３に記載されている方法がある。
文献１  M.Sudan: Decoding of Reed-Solomon codes beyond the error correction bound, Journal of Complexity, vol 13, no.1, pp.180-193,1997.
文献２  V.Guruswami and M.Sudan: Improved decoding of Reed-Solomon and Algeebraic-Geometry codes, IEEE Transactions on Information Theory, vol 45, pp.1757-1767,1999.
文献３  R.Kotter and V.Vardy: Algebraic soft-decision decoding of Reed-Solomon codes, IEEE Transactions on Information Theory, August 31 2001.
【００９６】
また、補間処理や因子決定の処理などに係わるアルゴリズムの一提案として、例えば、文献４，５に記載されているアルゴリズムがある。
文献４  R.M.Roth and G.Ruckenstein: Efficient decoding of Reed-Solomon codes beyond half the minimum distance, IEEE Transactions on Information Theory,vol 46, pp.246-257,2000.
文献５  R.R.Nielsen: Decoding AG-codes beyond half the minimum distance, thesis,Technical University of Denmark, 1998.
【００９７】
［Ｇ−Ｓリスト復号について］
上述したように、リスト復号に関して複数の提案がなされているが、それらの提案のうち、文献２に記載されているV.Guruswami and M.Sudanにより提案されたリスト復号（以下、適宜、Ｇ−Ｓリスト復号と記述する）について説明を加える。このＧ−Ｓリスト復号は、最大で
【数９】
2006042088.tif 000011
個のエラーシンボルの訂正を保証する復号方式である。
【００９８】
符号位置｛α0，α1，α2，・・・，αn-1｝、
符号語ｃ＝（ｃ0，ｃ1，ｃ2，・・・，ｃn-1）、
符号語ｃに対応する硬判定受信語ｙ＝（ｙ0，ｙ1，ｙ2，・・・，ｙn-1）
とする。また、整数ｍ，ｒ，ｌを、それぞれ以下のように設定する。
【数１０】
2006042088.tif 000012
【００９９】
また、有限体Ｆqの係数２変数多項式Ｑ（Ｘ、Ｙ）＝Σａi,jＸiＹjに対して、以下のような定義を与える。
（１，ｋ−１）deg（Ｑ）＝ｍａｘ｛ｉ＋（ｋ―１）ｊ｜ａi,j≠０｝
Ｑα,β（Ｘ，Ｙ）＝Ｑ（Ｘ＋α，Ｙ＋β）
（ｑα,β）i,j＝｛Ｑα,β（Ｘ、Ｙ）のＸiＹjの係数｝
【０１００】
このようなとき、以下の３条件を設定する。
条件１
【数１１】
2006042088.tif 000013
（ｆｏｒ  ０≦∀ｉ≦ｎ、∀ｊ1，∀ｊ2≧０s.t.、ｊ1＋ｊ2＜ｒ）
条件２
【数１２】
2006042088.tif 000014
条件３
（１，ｋ−１）deg（Ｑ）≦ｌ
【０１０１】
Ｑ（Ｘ、Ｙ）が、上記した条件１乃至３を満たす場合、受信語ｙからハミング（Hamming）距離ｍ以下の符号語リストは、Ｑ（Ｘ、Ｙ）のＹ−ｆ（Ｘ）型因子（ｆは、ｋ−１次以下）より求められる。また、このようなＱ（Ｘ、Ｙ）は、上記のように設定した整数ｍ，ｒ，ｌに対して必ず存在すること確認されている。
【０１０２】
Ｑ（Ｘ，Ｙ）が、
Ｑ（Ｘ，Ｙ）＝（Ｙ―ｆ0（Ｘ））（Ｙ―ｆ1（Ｘ））
・・・（Ｙ―ｆs-1（Ｘ））（その他の型を持つ因子）
と因数分解された場合、
ｆ0（Ｘ）＝ｆ0,0＋ｆ0,1Ｘ＋ｆ0,2Ｘ2＋・・・＋ｆ0,k-1Ｘk-1
ｆ1（Ｘ）＝ｆ1,0＋ｆ1,1Ｘ＋ｆ1,2Ｘ2＋・・・＋ｆ1,k-1Ｘk-1
ｆ2（Ｘ）＝ｆ2,0＋ｆ2,1Ｘ＋ｆ2,2Ｘ2＋・・・＋ｆ2,k-1Ｘk-1
・・・・・・・・・・・・・・・・
ｆs-1（Ｘ）＝ｆs-1,0＋ｆs-1,1Ｘ＋ｆs-1,2Ｘ2＋・・・＋ｆs-1,k-1Ｘk-1
に対応して、
（ｆ0,0，ｆ0,1，ｆ0,2，・・・，ｆ0,k-1）
（ｆ1,0，ｆ1,1，ｆ1,2，・・・，ｆ1,k-1）
（ｆ2,0，ｆ2,1，ｆ2,2，・・・，ｆ2,k-1）
・・・・・・・・・・・
（ｆs-1,0，ｆs-1,1，ｆs-1,2，・・・，ｆs-1,k-1）
が復号語の候補とされる。
【０１０３】
このような復号語の候補とされたデータが復号結果としてリストにされる。このリスト内のデータに、受信語ｙからハミング距離が（ｎ−１−ｍ）以下の符号語に対応する情報語が必ず含まれることが、このＧ−Ｓリスト復号では保証されている。
【０１０４】
上述したＧ−Ｓリスト復号についてまとめると、Ｇ−Ｓ復号は、大きくわけて以下の４ステップの処理で実現されることがわかる。
【０１０５】
ステップ１  整数ｍ，ｒ，ｌを算出（符号化パラメータが定まれば一定）
ステップ２  条件１乃至３を満たす２変数多項式Ｑ（Ｘ、Ｙ）を補間により算出
ステップ３  ステップ１において求められたＱ（Ｘ、Ｙ）のＹ―ｆ（Ｘ）型因子を全て              求める
ステップ４  復号語候補リストを作成する
【０１０６】
［Ｋ−Ｖリスト復号について］
次に、文献３に記載されているR.Kotter and V.Vardyにより提案されたリスト復号（以下、適宜、Ｋ−Ｖリスト復号と記述する）について説明を加える。このＫ−Ｖリスト復号は、上述したＧ−Ｓリスト復号を拡張版としてとらえることができる。そして、Ｋ−Ｖリスト復号は、軟判定受信語を用いたリスト復号であり、硬判定復号時に比べてより高い性能を有するとされている。
【０１０７】
符号位置｛α0，α1，α2，・・・，αn-1｝、
符号語ｃ＝（ｃ0，ｃ1，ｃ2，・・・，ｃn-1）、
符号語ｃに対応する軟判定受信語ｙ＝（ｙ0，ｙ1，ｙ2，・・・，ｙn-1）
とする。
【０１０８】
受信語ｙに対応して、各列が符号位置、各行が有限体の元に対応するような正整数を要素としてもつ、以下のようなｑ×ｎの行列を考える。
【数１３】
2006042088.tif 000015
【０１０９】
この行列により補間の重複度条件が決定されるので、重複度行列と記述する。
【０１１０】
また、重複度行列ＭのコストＣ（Ｍ）を以下のように定義する。
Ｃ（Ｍ）＝（１／２）Σｍi,j（ｍi,j＋１）
さらに、以下の定義を加える。
【数１４】
2006042088.tif 000016
【０１１１】
このような定義が加えられているとき、符号語ｃの重複度行列Ｍに関するスコアＳM（ｃ）は、以下のようになる。
【数１５】
2006042088.tif 000017
【０１１２】
このようなとき、以下の３条件を設定する。
条件１
【数１６】
2006042088.tif 000018
（ｆｏｒ  ０≦∀ｉ≦ｎ、∀ｇ∈Ｆq，∀ｊ1，ｊ2≧０s.t.、ｊ1＋ｊ2＜ｍg,i）
条件２
【数１７】
2006042088.tif 000019
条件３
条件１と条件２を満たす２変数多項式中（１，ｋ−１）deg（Ｑ）は最小
【０１１３】
重複度行列Ｍに対してＦq係数２変数多項式Ｑ（Ｘ，Ｙ）が、上記した条件１乃至３を満たす場合、Ｍに関する符号語ｃのスコアＳM（ｃ）が、Δ1,k―1（Ｃ（Ｍ））より大きい符号語ｃに対応する符号語リストは、Ｑ（Ｘ、Ｙ）のＹ−ｆ（Ｘ）型因子（ｆは、ｋ−１次以下）より求められる。
【０１１４】
Ｑ（Ｘ，Ｙ）が、
Ｑ（Ｘ，Ｙ）＝（Ｙ―ｆ0（Ｘ））（Ｙ―ｆ1（Ｘ））
・・・（Ｙ―ｆs-1（Ｘ））（その他の型を持つ因子）
と因数分解された場合、
ｆ0（Ｘ）＝ｆ0,0＋ｆ0,1Ｘ＋ｆ0,2Ｘ2＋・・・＋ｆ0,k-1Ｘk-1
ｆ1（Ｘ）＝ｆ1,0＋ｆ1,1Ｘ＋ｆ1,2Ｘ2＋・・・＋ｆ1,k-1Ｘk-1
ｆ2（Ｘ）＝ｆ2,0＋ｆ2,1Ｘ＋ｆ2,2Ｘ2＋・・・＋ｆ2,k-1Ｘk-1
・・・・・・・・・・・・・・・・
ｆs-1（Ｘ）＝ｆs-1,0＋ｆs-1,1Ｘ＋ｆs-1,2Ｘ2＋・・・＋ｆs-1,k-1Ｘk-1
に対応して、
（ｆ0,0，ｆ0,1，ｆ0,2，・・・，ｆ0,k-1）
（ｆ1,0，ｆ1,1，ｆ1,2，・・・，ｆ1,k-1）
（ｆ2,0，ｆ2,1，ｆ2,2，・・・，ｆ2,k-1）
・・・・・・・・・・・
（ｆs-1,0，ｆs-1,1，ｆs-1,2，・・・，ｆs-1,k-1）
が復号語の候補とされる。
【０１１５】
このような符号語の候補とされたデータがリストにされる。重複度行列Ｍに関する符号語ｃのスコアＳM（ｃ）が、
ＳM（ｃ）＞Δ1,k―1（Ｃ（Ｍ））
という条件Ａを満たす符号語に対応する情報語は、作成されたリスト内のデータに必ず含まれることが、このＫ−Ｖリスト復号では保証されている。
【０１１６】
送信された符号語ｃが上述した手法に基づいて正しく復号される十分条件は、条件Ａである。
【０１１７】
［重複度行列について］
このような事実に基づき、受信語ｙの情報から正しい送信語がより高い確率で復号されるように、重複度行列を構成する方法が提案されている。その提案のうち、R.Kotter and V.Vardyは、以下のようなことを提案している。
【０１１８】
受信語ｙより、各シンボルに対して信頼度を要素としてもつｑ×ｎ信頼度行列Пを決定する。
【数１８】
2006042088.tif 000020
【０１１９】
信頼度行列Пから以下のようにП→Ｍアルゴリズムによって、コストの上限Ｃ*以下の重複度行列Ｍ＝（ｍi,j）が以下に示すような手順で決定される。
【０１２０】
まず信頼度行列Пとコストの上限Ｃ*が入力される。
【０１２１】
ステップ１
【数１９】
2006042088.tif 000021
が計算される。
【０１２２】
ステップ２
【数２０】
2006042088.tif 000022
が計算される。
【０１２３】
ステップ３
【数２１】
2006042088.tif 000023
が計算される。
【０１２４】
ステップ４
【数２２】
2006042088.tif 000024
が計算される。
【０１２５】
ステップＳ５
【数２３】
2006042088.tif 000025
が計算される。
【０１２６】
ステップＳ６
Ｃ（ｓ＋１）＜Ｃ*が満たされる場合、ステップ１に戻り、それ以降の計算が繰り返し行われる。
Ｃ（ｓ＋１）≧Ｃ*が満たされる場合、計算は終了される。すなわち、重複度行列が求められた状態とされる。
【０１２７】
このような計算が行われることにより、出力として
Ｍ＝Ｍ*（ｓ）
が出力される。
【０１２８】
このようにして求められた重複度行列Ｍを用いることにより上述したＫ−Ｖ復号が行われるようにしても良い。このようにして求められる重複度行列Ｍを用いてＫ−Ｖ復号が行われるときの手順についてまとめると、以下のようになる。
【０１２９】
ステップ１  コストの上限Ｃ*を設定
ステップ２  受信語より信頼度行例Пを算出
ステップ３  П→Ｍアルゴリズムにより重複度行列Ｍを算出
ステップ４  重複度行列Ｍにより与えられる条件を元に補間多項式Ｑ（Ｘ，Ｙ）を算出
ステップ５  Ｑ（Ｘ，Ｙ）のＹ―ｆ（Ｘ）型因子を全て求める
ステップ６  復号語候補リストを作成する
【０１３０】
Ｇ−Ｓリスト復号やＫ−Ｖリスト復号は、上述したように復号を行うが、その復号の対象となるのは、受信語である。そして、その受信された受信語より得られる信頼度が用いられて復号が行われる。Ｇ−Ｓリスト復号やＫ−Ｖリスト復号は、受信語が２５６シンボルであることを想定したものとされている。
【０１３１】
よって、短縮符号などの受信語が２５６シンボルに満たないデータは、Ｇ−Ｓリスト復号やＫ−Ｖリスト復号では、正確に復号できない可能性がある。本実施の形態においては、後述するような処理を実行することにより、短縮符号などの受信語であっても、リスト復号を行えるようにする。
【０１３２】
以上のことを考慮し、本実施の形態におけるリスト復号部４３で行われる復号について以下に説明を加える。
【０１３３】
［リスト復号を行うリスト復号部の構成］
図６は、リスト復号部４３の構成例を示す図である。リスト復号部４３は、符号化されたデータを入力する入力部１０１、入力部１０１に入力されたデータが短縮符号であるか否かなどの判断を行う判断部１０２を備える。判断部１０２の判断結果は、信頼度計算部１０３、重複度計算部１０４、補間処理部１０５、および、リスト作成部１０７にそれぞれ供給される。
【０１３４】
なお、図６では、判断部１０２の判断結果は、信頼度計算部１０３と重複度計算部１０４に供給されるとして図示したが、フローチャートを参照して後述するように、信頼度計算部１０３と重複度計算部１０４の両方でなく、どちらか一方のみに供給される構成としても良い。
【０１３５】
信頼度計算部１０３には、入力部１０１に入力されたデータも供給される。信頼度計算部１０３は、入力されたデータ（受信語）から得られる信頼度を計算すると共に、必要に応じ、所定の部分に対して信頼度を設定する。そして、その結果は、重複度計算部１０４に供給される。重複度計算部１０４は、与えられた信頼度を用いて重複度を計算すると共に、必要に応じ、所定の部分に対して重複度を設定する。そして、その結果は、補間処理部１０５に供給される。
【０１３６】
補間処理部１０５は、多項式を求めるなどの処理を実行することにより補間処理を行い、その結果を因数分解処理部１０６に供給する。因数分解処理部１０６は、所定の条件を満たすものを対象として因数分解を行う。そして、その結果は、リスト作成部１０７に供給され、リスト作成部１０７により復号語の候補のリストが作成される。この作成されたリストから、１つの復号語が選択され、出力部１０８を介して、図示していない後段の処理に供給される。
【０１３７】
［リスト復号部の処理１について］
図７は、図６に示したリスト復号部４３において実行される処理について説明するためのフローチャートである。リスト復号部４３において実行される処理は、［リスト復号について］、［Ｇ−Ｓリスト復号について］、［Ｋ−Ｖリスト復号について］、および、［重複度行列について］の各部分で説明した処理を基本とする。このような理由から、既に説明した事項については、以下の説明においては、適宜省略して説明する。
【０１３８】
ステップＳ１１において、判断部１０２は、入力部１０１に入力されたデータ（受信語）が短縮符号であるか否かを判断する。入力部１０１に入力されるデータは、復号器２が図２に示したような構成の場合、デインタリーブ部４２から出力されたデータである。判断部１０２は、入力されたデータが短縮符号であるか否かの判断を、そのシンボル数を判断することにより行う。短縮符号の場合、例えば、０乃至２０３までの２０４個のシンボルなど、２５５個のシンボル以下のシンボル数である。よって、入力されたシンボル数が、２５５シンボル数以下であるか否かを判断することにより、受信語は短縮符号であるか否かの判断を実行することが可能である。
【０１３９】
ステップＳ１１において、受信語は短縮符号であると判断された場合、ステップＳ１２に処理は進められる。判断部１０２は、受信語が短縮符号であると判断した場合、そのことを、信頼度計算部１０３に知らせる（そのことを示すデータを信頼度計算部１０３に出力する）。信頼度計算部１０３は、判断部１０２から、そのような知らせを受けた場合、入力部１０１から供給される受信語の各シンボルから取得される信頼度に対して、後段の処理を実行する上で不足しているシンボルの信頼度を補うような処理を行う。
【０１４０】
すなわち、例えば、受信語が２０４個のシンボルから構成されていた場合、５１（＝２５５−２０４）個のシンボルの信頼度は、受信語から得られないので、その５１シンボル分の信頼度が設定される。さらに換言すれば、短縮化され送信されなかったことが既知のシンボルに対して、復号する側で、信頼度を設定するという処理が実行される。
【０１４１】
信頼度は、対象とされるシンボルが、所定の値である確率を示す値であり、受信されないシンボルは、０である確率が１であるので（符号器１側で、該当する部分のシンボルは０であると設定されることにより、短縮符号の送信は実現されているため）、受信されない５１個のシンボルに対応する信頼度は、１に設定される。
【０１４２】
このような信頼度の設定が行われることにより、短縮符号のように、所定の復号方式を適用して復号を実行するには、シンボル数が少ないデータに対しても、不足しているシンボル数分だけ信頼度を充当することにより、所定の復号方式（ここでは、リスト復号）の対象に変更することが可能となる。
【０１４３】
このように、信頼度が充当されたデータが用いられ、信頼度計算が行われる。そして、信頼度計算部１０３において信頼度が計算されると、その結果は、重複度計算部１０４に供給される。重複度計算部１０４は、供給されたデータを用いて重複度を計算する。
【０１４４】
［信頼度の充当に関する具体例］
ステップＳ１２乃至Ｓ１３までの処理について、具体的な例を挙げて再度説明を加える。まず、供給される短縮化されている受信語について説明する。［リスト復号に適用される符号化方式について］の部分で詳細は説明したので、ここでは簡潔に、具体的な数値を挙げて再度説明する。
【０１４５】
有限体として、元の個数が２8個（＝２５６個）の有限体Ｆを考える。また、線形符号ｃとして符号長が２０４、情報長が１８８の（２０４，１８８）ＲＳ符号を考える。このときの生成多項式を、
【数２４】
2006042088.tif 000026
情報語をｆ＝（ｆ0，ｆ1，ｆ2，・・・，ｆ187）、
対応する情報多項式をｆ（ｘ）＝ｆ0＋ｆ1ｘ＋ｆ2ｘ2＋・・・＋ｆ187ｘ187
とする。
【０１４６】
このようなとき、組織的符号化による符号語ｃ＝（ｃ0，ｃ1，ｃ2，・・・，ｃ203）に対応する符号多項式は、
ｃ（ｘ）＝ｃ0＋ｃ1ｘ＋ｃ2ｘ2＋・・・＋ｃ203ｘ203
＝ｑ（ｘ）ｆ（ｘ）    ｍｏｄ（ｘ255−１）
＝ｆ（ｘ）ｘ16＋ｐ（ｘ）    ｍｏｄ（ｘ255−１）
ここで ｑ（ｘ），ｐ（ｘ） は、それぞれ ｆ（ｘ）ｘ16 を ｇ（ｘ） で除算したとき商と余りである。
【０１４７】
これは原始的な符号ＲＳ（２５５，２３９）のリードソロモン符号の５１シンボルに０を充当した情報語や符号語、例えば、
ｆp＝（ｆ0，ｆ1，ｆ2，・・・，ｆ187，ｆ188，ｆ189，・・・，ｆ238）
＝（ｆ0，ｆ1，ｆ2，・・・，ｆ187，０，０，０，・・・，０）
ｃp＝（ｃ0，ｃ1，・・，ｃ15，ｃ16，ｃ17，・・，ｃ203，ｃ204，・・ｃ254）
＝（ｐ0，ｐ1，・・，ｐ15，ｆ0，ｆ1，・・・，ｆ187，０，０，・・・，０）
と見なすことができる。
【０１４８】
このように０を充当した場合、シフトレジスタで構成した符号化器（例えば、図２のＲＳ符号化部２１）のレジスタ初期値を０に設定することで、実質的な情報語ｆ＝（ｆ0，ｆ1，ｆ2，・・・，ｆ187）を符号化器に入力し、符号語ｃ＝（ｃ0，ｃ1，・・・，ｃ203）を取得し、それら２０４シンボル分を送信することにより短縮符号の送信は実現されている。
【０１４９】
このようにして送信されてきた２０４シンボルのデータを受信した復号器２は、上述したような、ステップＳ１１乃至Ｓ１４の処理を実行する。すなわち、まず、短縮された符号語ｃ＝（ｃ0，ｃ1，・・・，ｃ203）に対応する受信語ｙ＝（ｙ0，ｙ1，ｙ2，・・・，ｙ203）が受信（入力）される。
【０１５０】
この受信された受信語に対しては、信頼度計算部１０３（図６）において、以下のような信頼度行列が計算される。すなわち、受信語の各シンボルに対してｑ×ｎ信頼度行列、
【数２５】
2006042088.tif 000027
が計算（この信頼度行列を信頼度行列Ａとする）される。
【０１５１】
上記した信頼度行列Ａにおいて、例えば、Ｐｒ（０｜ｙ0）との表記は、“ｙ0”が生起するという条件のもとで、“０”が生起する条件付き確率（ｙ0が０である確率）を表し、受信語の対応するシンボルから得られる具体的な確率値が割り当てられることを意味する。
【０１５２】
この信頼度行列Ａの部分に関しては、受信語が存在しているため、信頼度を計算することが可能である。よって、受信された受信語に対する信頼度計算部１０３の処理としては、入力されたシンボルに対して信頼度行列Ａを計算するといった処理が行われる。このように、受信語が存在する部分に対しては、その受信された受信語から信頼度を計算するという処理が実行されるが、受信されていないシンボルで、かつ、リスト復号を適用するには必要となるシンボルに対しては、受信語から信頼度を計算することができない（受信語から信頼度を計算する必要性がなく、信頼度を計算することは行われていない）ので、信頼度計算部１０３が信頼度を設定する。
【０１５３】
すなわちこの場合、信頼度計算部１０３は、短縮化されて０が充当されたものに該当する受信語ｙ＝（ｙ204，ｙ205，ｙ207，・・・，ｙ254）に対応する部分に、以下のような信頼度を設定する（この設定された信頼度から構成される信頼度行列を信頼度行列Ｂとする）。
【数２６】
2006042088.tif 000028
【０１５４】
上記した信頼度行列Ｂにおいて、例えば、Ｐｒ（０｜ｙ204）＝１との表記は、“ｙ204”が“０”である確率が“１”であることを意味している。上述したように、符号器１側では、２０４シンボルの短縮符号の符号語を送信する際、２０４シンボル以外のシンボルは、０が充当されているとして設定されているので、２０４シンボル以外のシンボルである“ｙ204”は、“０”であることが間違いないので、“ｙ204”が“０”である確率は“１”と設定される。
【０１５５】
換言すれば、“ｙ204”が“０”以外の値になることはないので、“ｙ204”が生起するという条件のもとで、“０”以外が生起する確率は、全て“０”と設定される。例えば、Ｐｒ（１｜ｙ204）は、０と設定される。受信語として含まれていなかったシンボル、例えば、“ｙ205”なども“ｙ204”と同様に０に設定される。
【０１５６】
このように、受信されていないシンボルの信頼度（確率）を設定することにより、リスト復号の対象となる２５５シンボルの受信語を受信したと場合と同様に後段の処理を実行することが可能となる。すなわち、原始的なＲＳ符号ＲＳ1（２５５，２３９）の符号に対応する受信語ｙ＝（ｙ0，ｙ1，ｙ2，・・・，ｙ254）で、上記した信頼度行列Ｂを導き出せるデータを含んだ状態で受信したと仮定し、リスト復号（Ｇ−Ｓリスト復号やＫ−Ｖリスト復号など）の処理を実行することが可能となる。
【０１５７】
図８を参照するに、符号位置が（α0，α1，α2，・・・・，αn―1）は、符号器１側から送信されてくる符号語であるため、受信器２側では、どのような値を有するデータであるかはわからないシンボル（unknown symbol）である。符号位置が（αn，αn+1，αn+2，・・・・，αN―1）は、短縮符号の場合、符号器１側からは送信されてこない符号語であり、受信器２側で信頼度などを設定するデータであるため、受信側２側では、既知のシンボル（known symbol）である。
【０１５８】
ここで、ｎを２０４、Ｎを２５６とすると、上記した例に該当する。すなわち、符号位置が（α0，α1，α2，・・・・，α203）はunknown symbolであり、符号位置が（α204，α205，α206，・・・・，α255）はknown symbolである。
【０１５９】
このように、復号側で受信されないシンボルに対して既知の値が設定されることにより、その設定されたシンボルも含めて重複度などの処理が実行される。すなわち、図８に示したように、各符号位置のシンボルを通る２変数多項式Ｑ（Ｘ，Ｙ）が求められることにより、重複度が算出される。
【０１６０】
図７のフローチャートの説明に戻り、ステップＳ１２の処理は、上記した信頼度行列Ｂを生成する処理であり、ステップＳ１３の処理は、上記した信頼度行列Ａを生成すると共に、信頼度行列Ｂを信頼度行列Ａに加える（設定する）処理である。そして、信頼度行列Ａと信頼度行列Ｂから構成される信頼度行列が用いられて、ステップＳ１４における重複度計算が行われる。
【０１６１】
ステップＳ１４において行われる重複度計算は、例えば、［重複度行列について］の部分で説明したような処理が実行されることにより行われる。そして、重複度計算が行われるとその結果が用いられ、補間処理など、ステップＳ１７以降の処理が実行される。
【０１６２】
ステップＳ１７以降の処理について説明する前に、ステップＳ１１において、受信語は短縮符号ではないと判断された場合について説明する。受信された受信語が短縮符号ではないと判断された場合、ステップＳ１５に処理が進められる。このような場合、受信語は、２５５シンボルで構成されているので、そのまま、その受信語を用いて信頼度計算を行うことができる。
【０１６３】
換言すれば、ステップＳ１２において行われる信頼度の設定処理を実行する必要がないため実行せずに、受信された受信語から信頼度計算が行われる。そして、ステップＳ１５において、信頼度計算が行われると、その結果が用いられて、ステップＳ１６において、重複度計算が実行される。
【０１６４】
このように、短縮符号でない場合には、受信された受信語が用いられてリスト復号の処理が実行される。
【０１６５】
次に、ステップＳ１７以降の処理について説明する。ステップＳ１７において、受信語は、符号化方式１（生成多項式符号化方式）で符号化されたデータであるか否かが、判断部１０２により判断される。このような判断が行われるのは、上述したように、リスト復号は、通常、符号化方式２（符号化位置符号化方式）により符号化されたデータに対して行われるため、その符号化方式２以外の符号化方式で符号化されたデータであった場合、リスト復号が適用できるデータ、すなわち、符号化方式２で符号化されたデータと同等に扱えるデータに変換する必要があるからである。
【０１６６】
ステップＳ１７において、受信語は、符号化方式１で符号化されたデータであると判断された場合、ステップＳ１８に処理が進められ、符号化方式２で符号化されたデータと同等に扱うことができるデータに変換するための処理が実行される。一方、ステップＳ１７において、受信語は、符号化方式１で符号化されたデータではないと判断された場合、換言すれば、受信語は、符号化方式２で符号化されたデータであると判断された場合、データを変換する必要はないので、そのような変換の処理が実行されないステップＳ２２以降の処理に処理は進められる。
【０１６７】
［補間点の変更処理］
ステップＳ１８において、補間点の変更処理が実行される。この補間点とは、ステップＳ１９における補間処理で用いられる点のことである。まず、補間点と、その補間点を用いた補間処理について説明する前に、ステップＳ１８において補間点の変更の処理が実行されることにより、符号化方式１により符号化されたデータを符号化方式２により符号化されたデータとして扱うことができる原理について説明する。
【０１６８】
Ｇ−Ｓリスト符号やＫ−Ｖリスト復号では、符号化位置符号化方式（符号化方式２）が前提とされていることは、既に説明した。ここで生成多項式を、
【数２７】
2006042088.tif 000029
とする。これは、
【数２８】
2006042088.tif 000030
において、ｂ＝１と設定したときの生成多項式である。すなわち、解の開始インデックスをｂ＝１と設定したときの式である。
【０１６９】
上記した生成多項式ｇ（ｘ）により定義される原始ＲＳ符号ＲＳ1（２５５，２３９）は、符号位置｛１，α，α2，・・・，α254｝を用いて符号位置符号化を行った場合の符号ＲＳcl（２５５，２３９）空間として一致する。すなわち、任意のＲＳ1（２５５，２３９）の符号語ｃ＝（ｃ0，ｃ1，ｃ2，・・・，ｃ254）に対して、元の個数が２8個（＝２５６個）の有限体Ｆに含まれるｋ−１＝２３８次多項式ｈ（ｘ）が存在し、
符号語ｃ＝（ｃ0，ｃ1，ｃ2，・・・，ｃ254）
＝（ｈ（１），ｈ（α），ｈ（α2），・・・，ｈ（α254））
という関係が成り立つ。
【０１７０】
特に上記したような短縮符号の場合、
符号語ｃ＝（ｃ0，ｃ1，ｃ2，・・・，ｃ254）
＝（ｈ（１），ｈ（α），ｈ（α2），・・・，ｈ（α254））
＝（ｐ0，ｐ1，ｐ2，・・，ｐ15，ｆ0，ｆ1，・・，ｆ187，０，０，・・，０）
という関係がさらに成り立つ。
【０１７１】
符号語の各符号位置｛１，α，α2，・・・，α254｝に対応する受信語より得られる情報より、符号位置符号化ＲＳ符号ＲＳcl（２５５，２３９）の情報多項式ｈ（ｘ）を算出し、符号位置を代入することにより、符号語ｃを導出し、最終的に生成多項式ＲＳ符号ＲＳ1（２５５，２３９）の情報語ｆ＝（ｆ0，ｆ1，ｆ2，・・・，ｆ187）が得られる。
【０１７２】
さらに、任意の生成多項式
【数２９】
2006042088.tif 000031
により定義される原始ＲＳ符号ＲＳb（２５５，２３９）全体は、２５５×２５５の対角行列Ａ
【数３０】
2006042088.tif 000032
を乗算することによりＲ1（２５５，２３９）に写される。すなわち、
ＲＳb（２５５，２３９） → ＲＳ1（２５５，２３９）
ｃ    → ｃ’＝ｃＡ
となる。
【０１７３】
生成多項式符号化された任意のＲＳ符号ＲＳb（２５５，２３９）は、行列Ａにより変換されることによりリスト復号の対象とすることができる。行列Ａによる対応付けを用いることにより、任意の生成多項式により定義されたＲＳ符号のリスト復号は、
【数３１】
2006042088.tif 000033
すなわち、解の開始インデックスがｂ＝１に設定された場合に帰着されることがわかる。
【０１７４】
上記した信頼度計算や重複度計算は、解の開始インデックスがｂ＝１に設定されていることを前提、または、設定されることを前提として行われる。ここでは、このような解の開始インデックスをｂ＝１に設定するといった処理を、ステップＳ１８において行う。
【０１７５】
［補間点の変更処理１］
ここでステップＳ１８において実行される補間点の変更処理およびそれ以降の処理について説明を加える。
【０１７６】
まず、符号位置｛１，α，α2，・・・，αq―2｝（上記した具体例に対応させると、ｑは２５６（＝２8）である）に対して、
補間点
【数３２】
2006042088.tif 000034
および、
各補間点に対して重複度
【数３３】
2006042088.tif 000035
が与えられる。
【０１７７】
但し、Ｍは自然数であり、ｉpは、１≦ｉ1，ｉ2，・・・ｉM≦ｑ−２を満たす数である。また各βは、有限体Ｆqに含まれる元である。重複度は、ステップＳ１４において既に算出されているものが用いられる。
【０１７８】
次に、各補間点をｐ＝１，２，・・・，Ｍ
【数３４】
2006042088.tif 000036
と変換する。
【０１７９】
このように変換された補間点が用いられ、ステップＳ１９において、補間処理が、補間処理部１０５（図６）において実行される。補間処理は、変更された結果、与えられた全ての補間点を、与えられた重複度で通るような（１、ｋ−１）重み次数が最小になるような２変数多項式を決定することにより行われる。
【０１８０】
そして、ステップＳ２０において、因数分解処理部１０６（図６）は、因数分解の処理を実行する。この因数分解の処理（因子決定の処理）は、補間処理により決定された２変数多項式から、
【数３５】
2006042088.tif 000037
という形の因子を全て求めることにより行われる。
【０１８１】
求められた因子が用いられ、リスト作成処理が、ステップＳ２１において、リスト作成部１０７（図６）により行われる。リスト作成の処理は、因子決定の処理で求められた全ての因子ｙに対して、
（ｈ（１），α1-bｈ（α），・・・，α(q-2)(1-b)ｈ（αq-2））
という復号語を求め、その復号語のリストを作成することにより行われる。
【０１８２】
符号化方式１で符号化されたデータをリスト復号する場合、補間点の処理が行われるだけでなく、リストが作成されるときにも、変更の処理が行われる。
【０１８３】
［提案されているリスト復号について］の部分で一般的に提案されているリスト復号について説明したが、その部分のリスト作成の処理の説明の部分で、
“リスト作成の処理は、因子決定の処理で求められた全ての因子ｙに対して、
（ｈ（１），ｈ（α），ｈ（α2），・・・，ｈ（αn-1））
という復号語を求め、その復号語のリストを作成する”
と説明した。
【０１８４】
このように、一般的には、（ｈ（１），ｈ（α），ｈ（α2），・・・，ｈ（αn-1））という復号語が求められるのだが、受信語が符号化方式１で符号化されたデータであると判断されたときには、（ｈ（１），α1-bｈ（α），・・・，α(q-2)(1-b)ｈ（αq-2））という符号語が求められる。
【０１８５】
換言すれば、
復号語（ｄ0，ｄ1，・・・，ｄq-2）を、
復号語（ｄ0，α1-bｄ1，・・・，α(q-2)(1―b)ｄq-2）
に変換する処理が行われることにより、復号語が求められる。
【０１８６】
このように、受信語が符号化方式１で符号化されたデータであった場合、補間点を変更し、復号語を変換することにより、リスト復号が行われる。このような処理が実行されることにより、リスト復号に適していない符号化方式で符号化されたデータも、リスト復号することが可能となる。
【０１８７】
［実証］
ここで、このように、補間点や復号語を変換することにより、リスト復号に適していない符号化方式で符号化されたデータも、リスト復号することが可能となるということを実証する。
【０１８８】
ここでの実証においては、有限体として、元の個数が２4個（＝１６個）の有限体Ｆを考える。この有限体Ｆ上の生成多項式を、
【数３６】
2006042088.tif 000038
とする。この生成多項式におけるαは、有限体Ｆの原始元とする。
【０１８９】
上記した生成多項式を巡回符号として得られる［１５，１１］リードソロモン符号の符号語として、
（α2，α8，α9，α11，α6，α4，α1，
α9，α8，α7，α2，α11，α9，α12，α9）
が送信されたとする。
【０１９０】
受信側でリスト復号を行う場合、補間点とその重複度の組は、特に、Ｋ−Ｖリスト復号のような通信路の信頼度情報が用いられることにより次のように与えられる（計算される）。
【数３７】
2006042088.tif 000039
【０１９１】
このとき、補間点は、以下のように変換される。
【数３８】
2006042088.tif 000040
【０１９２】
変換された補間点が、与えられた重複度で通るような（１、ｋ−１）重み次数が最小になるような２変数多項式は、次式のように求められる。
【０１９３】
（ｘ3＋αｘ2＋α2ｘ）ｙ2
＋（（α3＋α2＋α）ｘ13＋αｘ12＋ｘ11＋（α2＋１）ｘ10＋（α3＋α＋１）ｘ9＋（α3＋α2＋１）ｘ8＋α3ｘ7＋（α3＋α2＋１）ｘ6＋αｘ5＋（α3＋α＋１）ｘ4＋（α＋１）ｘ3＋（α3＋α）ｘ2＋（α3＋α2）ｘ＋（α2＋α＋１））ｙ
＋（α3＋α2＋α＋１）ｘ23＋（α3＋α2＋α）ｘ22＋（α3＋α）ｘ21
＋（α3＋１）ｘ20＋（α2＋１）ｘ19＋（α3＋α＋１）ｘ18＋（α3＋α）ｘ17
＋（α＋１）ｘ16＋（α3＋α）ｘ15＋（α3＋α２）ｘ14＋（α3＋α2＋α）ｘ13
＋（α3＋α2＋α＋１）ｘ11＋（α2＋α）ｘ10＋（α2＋α）ｘ9
＋（α3＋α2＋α）ｘ8＋（α3＋α2＋１）ｘ7＋αｘ6＋（α3＋α＋１）ｘ5
＋（α2＋α）ｘ4＋（α3＋α＋１）ｘ3＋ｘ＋（α3＋α2＋１）
【０１９４】
補間処理より決定された２変数多項式より、次式のような因子が求められる。
【０１９５】
ｙ＋ｘ10＋ｘ9＋（α2＋α＋１）ｘ8＋（α＋１）ｘ7＋（α3＋α＋１）ｘ6
＋αｘ5＋（α3＋α2＋α＋１）ｘ4＋α3ｘ3＋α2ｘ2＋αｘ＋α3
【０１９６】
求められた全ての因子をもとに復号語が計算される。
【０１９７】
（α2，α1+7，α2+7，α3+8，α4+2，α5+14，α6+10，α7+2，α8+0，
α9+13，α10+7，α11+0，α12+12，α13+14，α14+10）
＝（α2，α8，α9，α11，α6，α4，α1，α9，α8，α7，α2，α11，α9，α12，α9）
【０１９８】
但し、ここでは、α15＝１を適用している。
【０１９９】
このように、送信された符号語が、受信側で正確に復号できることが確認される。
【０２００】
［補間点の変更処理２］
他の補間点の変更処理および、それ以降の処理について説明する。［補間点の変更処理１］と同じ部分については適宜省略して説明する。
【０２０１】
補間点の変更の処理に関し、上記した［補間点の変更処理１］では、各補間点をｐ＝１，２，・・・，Ｍ
【数３９】
2006042088.tif 000041
と変換した。ここでは、
【数４０】
2006042088.tif 000042
と変換する。すなわち、ｉp（ｂ−１）の部分を−ｂｉpとした。
【０２０２】
このように変換された補間点が用いられ、補間処理が実行される。補間処理は、変更された結果、与えられた全ての補間点を、与えられた重複度で通るような（１、ｑ−ｋ−２）重み次数が最小になるような２変数多項式を決定することにより行われる。
【０２０３】
そして因数分解の処理が実行される。この因数分解の処理（因子決定の処理）は、補間処理により決定された２変数多項式から、
【数４１】
2006042088.tif 000043
という形の因子を全て求めることにより行われる。
【０２０４】
求められた因子が用いられ、リスト作成処理が行われる。リスト作成処理は、因子決定の処理で求められた全ての因子ｙに対して、
（ｈ（１），αbｈ（α），・・・，αb(q-2)ｈ（αq-2））
という復号語を求め、その復号語のリストを作成することにより行われる。
【０２０５】
この場合も、［補間点の変更処理１］の部分で説明したように、復号語の変換の処理が同様に実行される。但し、この［補間点の変更処理２］においては、一般的に、
（ｈ（１），ｈ（α），ｈ（α2），・・・，ｈ（αn-1））
という復号語が求められるが、ここでは、
（ｈ（１），αbｈ（α），・・・，αb(q-2)ｈ（αq-2））という符号語が求められる。
【０２０６】
換言すれば、
復号語（ｄ0，ｄ1，・・・，ｄq-2）を、
復号語（ｄ0，αbｄ1，・・・，αb(q-2)ｄq-2）
に変換する処理が行われることにより、復号語が求められる。
【０２０７】
［補間点の変更処理３］
さらに他の補間点の変更処理および、それ以降の処理について説明する。
【０２０８】
この［補間点の変更処理３］における処理は、有限体Ｆq上の任意に与えられたＦq上（ｑm−１−ｋ）次生成多項式ｇ（ｘ）により、巡回符号として定義されるＦq上［ｑm−１，ｋ］原始ＢＣＨ符号に対して、補間を利用するリスト復号を適用する場合に適している。
【０２０９】
この［補間点の変更処理３］においては、補間点の変更処理などが実行される前の処理として、事前処理が実行される。まず、元の個数がｑ個の有限体Ｆを有限体Ｆqとし、元の個数がｑm個の有限体Ｆを有限体Ｆq'とする。
【０２１０】
有限体Ｆq上の生成多項式を有限体Ｆq'上で因数分解し、根が最も長く連続する因子の積からなる有限体Ｆq'上の多項式ｇR（ｘ）を求める。
【数４２】
2006042088.tif 000044
【０２１１】
符号位置
【数４３】
2006042088.tif 000045
に対して、
補間点
【数４４】
2006042088.tif 000046
および、
各補間点に対して重複度
【数４５】
2006042088.tif 000047
が与えられる。
【０２１２】
但し、Ｍは自然数であり、ｉpは、１≦ｉ1，ｉ2，・・・ｉM≦ｑm−２を満たす数である。また各αは、有限体Ｆq'の原始元であり、各βは、有限体Ｆqに含まれる元である。重複度は、ステップＳ１４において既に算出されているものが用いられる。
【０２１３】
このような事前処理が行われた後、補間点の変更処理が実行される。すなわち、各補間点が、ｐ＝１，２，・・・，Ｍ
【数４６】
2006042088.tif 000048
と変換される（［補間点の変更処理１］と同様の変換）。
【０２１４】
このように変換された補間点が用いられ、ステップＳ１９において、補間処理が、補間処理部１０５（図６）において実行される。補間処理は、変更された結果、与えられた全ての補間点を、与えられた重複度で通るような（１、ｋ’−１）重み次数が最小になるような２変数多項式を決定することにより行われる。
【０２１５】
そして、ステップＳ２０において、因数分解処理部１０６（図６）は、因数分解の処理を実行する。この因数分解の処理（因子決定の処理）は、補間処理により決定された２変数多項式から、
【数４７】
2006042088.tif 000049
という形の因子を全て求めることにより行われる。
【０２１６】
求められた因子が用いられ、リスト作成処理が、ステップＳ２１において、リスト作成部１０７（図６）により行われる。リスト作成の処理は、因子決定の処理で求められた全ての因子ｙに対して、
【数４８】
2006042088.tif 000050
という復号語を求め、その復号語のリスト（リスト１とする）を作成することにより行われる。
【０２１７】
このような補間点や復号語に関する変換の処理を含むリスト復号は、ＢＣＨ符号の符号語リストを作成する際に有効である。そこで、リスト作成の処理として、さらに、ＢＣＨ符号の復号語リスト（リスト２とする）が作成されるようにする。そのリスト２は、リスト１から全成分が有限体Ｆqに含まれるものが選ばれることにより作成される。
【０２１８】
［検証］
ここで、［補間点の変更処理３］として上述した補間点や復号語を変換することにより、リスト復号に適していない符号化方式で符号化されたデータも、リスト復号することが可能となるということを、具体的な例を挙げて検証する。
【０２１９】
まずここでは、生成多項式として、
ｇ（ｘ）＝ｘ8＋ｘ7＋ｘ6＋ｘ4＋１
とする有限体Ｆ2上の［１５，７］原始ＢＣＨ符号を考える。
【０２２０】
【数４９】
2006042088.tif 000051
上の多項式ｇ（ｘ）は、
ｇ（ｘ）＝（ｘ−α）（ｘ−α2）（ｘ−α3）（ｘ−α4）
（ｘ−α6）（ｘ−α8）（ｘ−α9）（ｘ−α12）
と因数分解される。
【０２２１】
根が最も長く連続する部分の因子として、
【数５０】
2006042088.tif 000052
が求められる。
【０２２２】
以下、このｇ（ｘ）を生成多項式とし巡回符号として符号化される［１５，１１］ＲＳ符号に対して、［補間点の変更処理１］のところで説明した、補間点の変更処理、補間処理、因子決定処理、リスト作成処理が、順次行われればよい。但し、ｂ＝１と設定されて行われる。
【０２２３】
［補間点の変更処理４］
さらに他の補間点の変更処理およびそれ以降の処理について説明する。
【０２２４】
この［補間点の変更処理４］における処理は、有限体Ｆq上に任意に与えられたＦq上（ｑm−１−ｋ）次生成多項式ｇ（ｘ）により、巡回符号として定義される有限体Ｆq上［ｑm−１，ｋ］原始ＢＣＨ符号の［ｑm−１，ｑm−ｋ―１］双対符号に対して、補間を利用するリスト復号を適用する場合に適している。
【０２２５】
この［補間点の変更処理４］は、［補間点の変更処理３］と同様の事前処理が実行される。そして、事前処理が実行された後、以下の補間点の変更処理が実行される。
【０２２６】
各補間点をｐ＝１，２，・・・，Ｍ
【数５１】
2006042088.tif 000053
と変換する。この変換は、［補間点の変更処理２］のところで説明した変換と同様である。
【０２２７】
このように変換された補間点が用いられ、ステップＳ１９において、補間処理が、補間処理部１０５（図６）において実行される。補間処理は、変更された結果、与えられた全ての補間点を、与えられた重複度で通るような（１、ｑ−ｋ’−２）重み次数が最小になるような２変数多項式を決定することにより行われる。
【０２２８】
そして、ステップＳ２０において、因数分解処理部１０６（図６）は、因数分解の処理を実行する。この因数分解の処理（因子決定の処理）は、補間処理により決定された２変数多項式から、
【数５２】
2006042088.tif 000054
という形の因子を全て求めることにより行われる。
【０２２９】
求められた因子が用いられ、リスト作成処理が、ステップＳ２１において、リスト作成部１０７（図６）により行われる。リスト作成の処理は、因子決定の処理で求められた全ての因子ｙに対して、
（ｈ（１），αbｈ（α），・・・，αb(q-2)ｈ（αq-2））
という復号語を求め、その復号語のリスト（リスト１とする）を作成することにより行われる。
【０２３０】
この場合も、［補間点の変更処理２］の部分で説明した場合と同様に、復号語が変更される。すなわち、
復号語（ｄ0，ｄ1，・・・，ｄq-2）を、
復号語（ｄ0，αbｄ1，・・・，αb(q-2)ｄq-2）
に変換する処理が行われることにより、復号語が求められる。
【０２３１】
このような補間点や復号語に関する変換の処理を含むリスト復号は、ＢＣＨ符号の符号語リストを作成する際に有効である。そこで、リスト作成の処理として、さらに、ＢＣＨ符号の復号語リスト（リスト２とする）が作成されるようにする。そのリスト２は、リスト１から全成分が有限体Ｆqに含まれるものが選ばれることにより作成される。
【０２３２】
このように、補間点や復号語が変換されることにより、リスト復号に適した符号化方式で符号化されていないデータであっても、リスト復号を適用することが可能となる。リスト復号が行えるようになることにより、より精度良くエラー訂正ができるようになる。
【０２３３】
［リストからの復号語の抽出について］
図７のフローチャートの説明に戻り、ステップＳ１７において、受信語は、符号化方式１で符号化されたデータであると判断された場合、上記した［補間点の変更処理１］乃至［補間点の変更処理４］のうちのいずれかの方式に基づく処理が実行される。いずれかの処理とは、符号化方式などの条件に最も適している処理が適用されることを意味する。勿論、いずれかの方法が選択されるような機能（例えば、ステップＳ１７とステップＳ１８の間の処理として、最も適している変換処理を決定するといったような処理を設ける）をリスト符号化部４３に備えるようにしても良い。
【０２３４】
一方、ステップＳ１７において、受信語は、符号化方式１で符号化されたデータではないと判断された場合、換言すれば、受信語は、符号化方式２で符号化されたデータ（リスト復号に適した符号化方式で符号化されたデータ）であると判断された場合、ステップＳ２２に処理が進められる。
【０２３５】
ステップＳ２２において補間処理、ステップＳ２３において因数分解処理、ステップＳ２４においてリスト作成処理が、それぞれ実行される。この場合、リスト復号に適した方式で符号化されたデータを扱うため、補間処理、因数分解処理、および、リスト作成処理は、通常のＫ−Ｖリスト復号などの処理（ステップＳ１８の補間点の変更処理などが行われないリスト復号の処理）が実行される。
【０２３６】
ステップＳ２１またはステップＳ２４において作成された復号語リストから、１つの復号語が、復号結果として抽出（選択）される。その抽出方法は、例えば、ユークリッド（Euclid）距離が最小である符号語１つに復号が行われる（最尤復号）ことにより行われる。
【０２３７】
この最尤復号が行われる前の処理として、復号語リストに含まれる復号語のうち、既知シンボル（ステップＳ１２の処理として信頼度を設定したシンボル）に該当する箇所と、既知シンボルを比較し、異なるシンボルに復号されている復号語は、リストから除外する。このような処理を実行することにより、復号結果として検討しなくてはならないシンボルの数を減らすことができ、処理を低減させることが可能となる。
【０２３８】
図９は、図７のフローチャートの処理が実行されることによりリスト復号される場合に、エラー訂正能力が通常復号のときよりも向上していることを説明するためのグラフである。図９に示したグラフは、短縮ＲＳ符号（２０４，１８８）を、硬判定通常復号した場合と、上記したリスト復号（［リスト復号部の処理１について］の部分で説明した復号）の処理で復号した場合の復号性能を比較したときのグラフである。
【０２３９】
上記下リスト復号に関するグラフの方は、既知シンボルの信頼度を１として設定し、Ｋ−Ｖリスト復号を実行したときのものである。図９においては、このようなときのフレームエラー率（ＦＥＲ）と、通常復号時のフレームエラー率が、比較されている。図９に示したように、本発明を適用してリスト復号を実行した方が、硬判定通常復号したときより、エラー訂正能力が向上していることがわかる。
【０２４０】
図９に示したグラフのリスト復号の結果は、リストサイズを４と設定したときのものである。リストサイズを４より大きくした場合、よりエラー訂正能力が向上すると考えられる。ただし、リストサイズを大きくすると、その分、エラー訂正能力は向上するが、復号結果の候補が増加することになり、増加した候補を扱うことになるため、処理も増加することが考えられるため、適切なリストサイズは、例えば、復号器２の処理能力などを考慮して決定されれば良い。
【０２４１】
ここで、［リスト復号部の処理１について］という部分で説明したリスト復号に関する処理についてさらに説明を加える。
【０２４２】
上記したリスト復号部４３において実行されるリスト復号は、有限体Ｆq上の（ｎ，ｋ）ＲＳ符号、Ｆq上で定義された生成多項式
【数５３】
2006042088.tif 000055
に対して適用することができる。
【０２４３】
２変数多項式の補間条件の抽出方法は、Ｋ−Ｖリスト復号手順Π→Ｍ（［重複度行列について］の部分で説明した手順）ではなく、他の任意の手法を用いて上記リスト復号が実行されるようにしても良い。
【０２４４】
復号語リストが作成された後、１つの符号語に復号する過程は、最尤復号に限らず、任意の復号方法を用いても良い。
【０２４５】
短縮部に相当する部分（受信語として受信されない部分）に充当する値は０に限らず、任意の値でも良い。例えば、任意の既知列｛ｃ204，ｃ205，ｃ206，・・・，ｃ254｝＝｛ａ204，ａ205，ａ206，・・・，ａ254｝とし、それらに対応する受信語｛ｙ204，ｙ205，ｙ206，・・・，ｙ254｝の信頼度を、
Ｐｒ（ａ｜ｙi）＝１（ｉｆ  ａ＝ａj）
＝０（otherwise）
と設定するようにしてもよい。
【０２４６】
上記した例では、短縮部のシンボル列が、連続的に符号語内に存在している例を示したが、連続的に符号語内に存在しておらず、既知の任意の箇所で短縮化されているような場合でも（既知の任意の箇所が複数分布して存在しているような場合も含む）、本実施の形態を適用することができる。短縮部のシンボルが連続的に符号語内に存在していないような場合、予め何らかの規則が設定され、その規則に基づいて、復号側は、どの部分が既知であり、その既知の部分の値がどのような値であるか判断できるようにしても良い。または、例えば、受信語に含まれるヘッダ内に、どの部分が既知であり、その既知の部分の値がどのような値であるのかを示す情報が含まれ、その情報が用いられて、信頼度の設定の処理などが行えるようにしても良い。
【０２４７】
さらに、送信側（符号化器１側）で実行される符号化方法が、符号位置符号化であれば、上記したように、リスト復号を行うことが可能である。また、送信側で実行される符号化方式が、符号位置符号化でなくても、符号位置符号化されたＲＳ符号とｎ×ｎ対角正則行列で写り合うような符号であれば、上記したように本実施の形態におけるリスト復号を適用することができる。
【０２４８】
有限体Ｆq上の（ｎ，ｋ）ＢＣＨ符号の場合においては、Ｆp上で定義された生成多項式ｇ（ｘ）に対して、上記したようなリスト復号の方式を適用することができる。この時、各符号シンボルの取り得る範囲は、Ｆp内に含まれるため、信頼度行列や重複度行列は、ｐ×ｎ行列となる。一般のＢＣＨ符号に対しても、上記したリスト復号の処理を適用することは可能である。
【０２４９】
上記したリスト復号に関する手法は、例示した符号のみに適用できることを示すのではなく、任意の代数幾何符号の復号に適用することができる。
【０２５０】
［リスト復号部の処理２について］
次に、図６に示したリスト復号部４３において実行される他の処理について、図１０のフローチャートを参照して説明する。図７に示したフローチャートの処理と同様な処理を行う部分は、適宜省略して説明する。
【０２５１】
図１０に示したフローチャートの処理と、図７に示したフローチャートの処理を比較するに、図１０に示したフローチャートの処理に基づいた場合、既知シンボルに対して信頼度が設定される（ステップＳ１２（図７）の処理を実行する）のではなく、重複度が設定される（ステップＳ４３（図１０））点が異なる。その重複度の設定に係わる処理を中心に、具体的な例を挙げて説明する。
【０２５２】
すなわち、ステップＳ４１において、受信語は短縮符号であると判断された場合、ステップＳ４２において、信頼度計算が実行される。ここでは、［リスト復号部の処理１について］のところと同様に、ＲＳ符号ＲＳ1（２０４，１８８）を扱う場合を例に挙げて説明する。
【０２５３】
短縮化された符号語ｃ＝（ｃ0，ｃ1，ｃ2，・・・，ｃ203）に対応する受信語ｙ＝（ｙ0，ｙ1，ｙ2，・・・，ｙ203）が受信された場合、受信された受信語の各シンボルに対して信頼度が計算され、信頼度行列が生成される。
【数５４】
2006042088.tif 000056
【０２５４】
この信頼度行列は、［リスト復号部の処理１について］の部分で、信頼度行列Ａと称した行列であり、受信語が存在する部分に対して、その受信された受信語から信頼度が計算され、その計算された結果が用いられて生成される行列である。
【０２５５】
このようにして生成された信頼度行列Ａが用いられ、重複度計算が行われるが、ここでは、重複度計算が行われると共に、重複度の設定の処理も行われる。ステップＳ４３において、重複度の設定処理が実行される。この処理は、受信されていない受信語に対して重複度を設定する処理である。短縮化された全てのシンボルに対する補間条件は、
（α204，０）で重複度ｍ
（α205，０）で重複度ｍ
（α206，０）で重複度ｍ
・・・・・・・・
（α254，０）で重複度ｍ
と設定される。
【０２５６】
この短縮化された全てのシンボルに対する補間条件は、復号器２側で設定される。すなわち、図６に示したリスト復号部４３において、判断部１０２が、受信された受信語は、短縮符号であると判断した場合、判断部１０２は、重複度計算部１０４に、そのことを知らせる（そのようなことを示すデータを出力する）。重複度計算部１０４は、そのような知らせを受けた場合、入力される信頼度行列から、重複度を計算すると共に、入力されないシンボル（受信語として受信されない既知のシンボル）の重複度を重複度ｍと設定する。
【０２５７】
この設定される重複度ｍは、例えば、
ｍ＝ｍａｘ｛未知シンボルに対応する全ての重複度｝＋γ
と設定される。ここで、未知シンボルとは、受信された受信語のことであり、どのような値が設定されているか（どのような値が符号化されたものか）わからないシンボルのことである。
【０２５８】
既知のシンボルに対して設定される重複度ｍは、未知シンボルから算出された重複度のうち、最大値を取り出し、その最大値に、所定の値γ（例えば、１）を加算した値とする。この重複度ｍの設定の仕方は、一例であり、他の設定の仕方でも良い。
【０２５９】
このような既知シンボルの補間条件を、未知シンボルの補間条件と合わせて、符号語全体の補間条件とし、ステップＳ４４における重複度計算が行われる。重複度計算が行われる結果、重複度行列が生成される。この重複度計算や重複度行列は、例えば、［重複度行列について］の部分で説明したような処理が実行されることにより、その計算および生成が行われる。
【０２６０】
なお、ここでは、説明の都合上、ステップＳ４３において重複度の設定、ステップＳ４４において重複度の計算が行われるとしたが、上述したように、重複度を設定するには、未知シンボルの重複度が用いられるため、必ずしも、既知シンボルに対して重複度が設定されてから、重複度が計算されるという処理の順番に限定されることを示すものではなく、その処理の順番は、適宜変更可能であると共に、並列的に処理するようにすることも勿論可能である。他の処理について、同様である。
【０２６１】
ここでは、重複度の計算および設定、その結果が用いられ重複度行列が生成されるという順番で処理が行われるとする。
【０２６２】
このようにして、既知シンボル（受信されていないシンボル）に対して、重複度を復号側で設定することにより、例えば、２５５シンボルに対応したリスト復号を適用してリスト復号を行うことが可能となる。
【０２６３】
ステップＳ４４において、重複度が計算され、重複度行列が生成されると、その結果が用いら、それ以降の処理が実行される。
【０２６４】
ステップＳ４５以下の処理は、図７のステップＳ１５以下の処理と基本的に同様であるので、その説明は省略する。
【０２６５】
図１１は、図１０のフローチャートの処理が実行されることによりリスト復号される場合に、エラー訂正能力が通常復号のときよりも向上していることを説明するためのグラフである。図１１に示したグラフは、短縮ＲＳ符号（２０４，１８８）を、硬判定通常復号した場合と、上記したリスト復号（［リスト復号部の処理２について］の部分で説明した復号）の処理で復号した場合の復号性能を比較したときのグラフである。
【０２６６】
上記下リスト復号に関するグラフの方は、既知シンボルの重複度を、上記したように、  ｍ＝ｍａｘ｛未知シンボルに対応する全ての重複度｝＋γ
とし、所定の値γを１として設定し、Ｋ−Ｖリスト復号を実行したときのものである。図１１においては、このようなときのフレームエラー率（ＦＥＲ）と、通常復号時のフレームエラー率が、比較されている。図９に示したように、本発明を適用してリスト復号を実行した方が、硬判定通常復号したときより、エラー訂正能力が向上していることがわかる。
【０２６７】
図１１に示したグラフのリスト復号の結果は、リストサイズを４と設定したときのものである。リストサイズを４より大きくした場合、よりエラー訂正能力が向上すると考えられる。ただし、リストサイズを大きくすると、その分、エラー訂正能力は向上するが、復号結果の候補が増加することになり、増加した候補を扱うことになるため、処理も増加することが考えられるため、適切なリストサイズは、例えば、復号器２の処理能力などを考慮して決定されれば良い。
【０２６８】
ここで、［リスト復号部の処理２について］という部分で上述したリスト復号に関する処理についてさらに説明を加える。
【０２６９】
上記したリスト復号部４３において実行されるリスト復号は、有限体Ｆq上の（ｎ，ｋ）ＲＳ符号、Ｆq上で定義された生成多項式
【数５５】
2006042088.tif 000057
に対して適用することができる。
【０２７０】
２変数多項式の補間条件の抽出方法は、Ｋ−Ｖリスト復号手順Π→Ｍ（［重複度行列について］の部分で説明した手順）ではなく、他の任意の手法を用いて上記リスト復号が実行されるようにしても良い。
【０２７１】
復号語リストが作成された後、１つの符号語に復号する仮定は、最尤復号に限らず、任意の復号方法を用いても良い。
【０２７２】
短縮部に相当する部分（受信語として受信されない部分）に充当する値は０に限らず、任意の値でも良い。例えば、任意の既知列｛ｃ204，ｃ205，ｃ206，・・・，ｃ254｝＝｛ａ204，ａ205，ａ206，・・・，ａ254｝とし、それらに対応する補間点（α204，ａ204），（α205，ａ205），・・・，（α254，ａ254）の重複度を重複度ｍと設定するようにしてもよい。
【０２７３】
上記した例では、短縮部のシンボル列が、連続的に符号語内に存在している例を示したが、連続的に符号語内に存在しておらず、既知の任意の箇所で短縮化されているような場合でも（既知の任意の箇所が複数分布して存在しているような場合も含む）、本実施の形態を適用することができる。短縮部のシンボルが連続的に符号語内に存在していないような場合、予め何らかの規則が設定され、その規則に基づいて、復号側は、どの部分が既知であり、その既知の部分の値がどのような値であるか判断できるようにしても良い。または、例えば、受信語に含まれるヘッダ内に、どの部分が既知であり、その既知の部分の値がどのような値であるのかを示す情報が含まれ、その情報が用いられて、信頼度の設定の処理などが行えるようにしても良い。
【０２７４】
さらに、送信側（符号化器１側）で実行される符号化方法が、符号位置符号化であれば、上記したように、リスト復号を行うことが可能である。また、送信側で実行される符号化方式が、符号位置符号化でなくても、符号位置符号化されたＲＳ符号とｎ×ｎ対角正則行列で写り合うような符号であれば、上記したように本実施の形態におけるリスト復号を適用することができる。
【０２７５】
有限体Ｆq上の（ｎ，ｋ）ＢＣＨ符号の場合においては、Ｆp上で定義された生成多項式ｇ（ｘ）に対して、上記したようなリスト復号の方式を適用することができる。この時、各符号シンボルの取り得る範囲は、Ｆp内に含まれるため、信頼度行列や重複度行列は、ｐ×ｎ行列となる。一般のＢＣＨ符号に対しても、上記したリスト復号の処理を適用することは可能である。
【０２７６】
上記したリスト復号に関する手法は、例示した符号のみに適用できることを示すのではなく、任意の代数幾何符号の復号に適用することができる。
【０２７７】
［リスト復号部の処理３について］
次に、図６に示したリスト復号部４３のさらに他の処理について、図１２のフローチャートを参照して説明する。ステップＳ７１において、受信された受信語は、短縮符号であるか否かが判断され、短縮符号であると判断された場合、ステップＳ７２に処理が進められる。ステップＳ７２において、硬判定語の算出が行われ、ステップＳ７３において、硬判定語の設定処理が行われる。
【０２７８】
図１２に示したフローチャートの処理は、図７や図１０に示したフローチャートの処理と比較し、硬判定語の算出をし、硬判定語に対して、受信されていないシンボル（既知シンボル）に対する充当などの処理が実行される点が異なる。
【０２７９】
一方、ステップＳ７１において、受信された受信語は、短縮符号ではないと判断された場合、ステップＳ７４において、硬判定語の算出が行われる。この場合、短縮符号ではないので、既知シンボルに対する充当などの処理は実行されない。換言すれば、通常の硬判定語の算出が実行される。
【０２８０】
ステップＳ７３またはステップＳ７４において、硬判定語が算出されると、ステップＳ７５に処理が進められる。ステップＳ７５以降の処理は、図７に示したフローチャートのステップＳ１７以降の処理と基本的に同様であるので、その説明は省略する。
【０２８１】
［リスト復号部の処理３に対する具体例］
ここで、具体例を挙げて説明を加える。有限体として、元の個数が２8個（＝２５６個）の有限体Ｆを考える。また、線形符号ｃとして符号長が２４８、情報長が２１６の（２４８，２１６）ＲＳ符号を考える。このときの生成多項式を、
【数５６】
2006042088.tif 000058
情報語をｆ＝（ｆ0，ｆ1，ｆ2，・・・，ｆ215）、
対応する情報多項式を
ｆ（ｘ）＝ｆ0＋ｆ1ｘ＋ｆ2ｘ2＋・・・＋ｆ215ｘ215
とする。
【０２８２】
このようなとき、組織的符号化による符号語ｃ＝（ｃ0，ｃ1，ｃ2，・・・，ｃ247）に対応する符号多項式は、
ｃ（ｘ）＝ｃ0＋ｃ1ｘ＋ｃ2ｘ2＋・・・＋ｃ247ｘ247
＝ｑ（ｘ）ｆ（ｘ）    ｍｏｄ（ｘ255−１）
＝ｆ（ｘ）ｘ32＋ｐ（ｘ）    ｍｏｄ（ｘ255−１）
ここで ｑ（ｘ），ｐ（ｘ） は、それぞれ ｆ（ｘ）ｘ32 を ｇ（ｘ） で除算したとき商と余りである。
【０２８３】
これは原始的な符号ＲＳ（２５５，２３９）のリードソロモン符号の５１シンボルに０を充当した情報語や符号語、例えば、
ｆp＝（ｆ0，ｆ1，ｆ2，・・・，ｆ215，ｆ216，ｆ217，・・・，ｆ238）
＝（ｆ0，ｆ1，ｆ2，・・・，ｆ215，０，０，０，・・・，０）
ｃp＝（ｃ0，ｃ1，・・，ｃ15，ｃ16，ｃ17，・・，ｃ247，ｃ248，・・ｃ254）
＝（ｐ0，ｐ1，・・，ｐ31，ｆ0，ｆ1，・・・，ｆ215，０，０，・・・，０）
と見なすことができる。
【０２８４】
このように０が充当された場合、シフトレジスタによる符号化器（例えば、図２のＲＳ符号化部２１）のレジスタ初期値を０に設定することで、実質的な情報語ｆ＝（ｆ0，ｆ1，ｆ2，・・・，ｆ215）を符号化器に入力し、符号語ｃ＝（ｃ0，ｃ1，・・・，ｃ247）を取得し、それら２４８シンボル分を送信することにより短縮符号の送信は実現されている。
【０２８５】
このようにして送信されてきた２４８シンボルのデータを受信した復号器２は、上述したような処理を実行する。すなわち、ステップＳ７２において、硬判定語の算出が行われる。
【０２８６】
短縮化された符号語ｃ＝（ｃ0，ｃ1，ｃ2，・・・，ｃ247）に対応する受信語ｙ＝（ｙ0，ｙ1，ｙ2，・・・，ｙ247）が受信された場合、受信語の各シンボルに対して硬判定語ｄ＝（ｄ0，ｄ1，ｄ2，・・・，ｄ247）が算出される。その算出は、
ｄj＝Ａｒｇｍａｘi（Ｐｒ（ｉ｜ｙj））
という式に値が順次代入されることにより行われる（ステップＳ７２の処理）。
【０２８７】
さらに、短縮化されて０が充当されたシンボルに対応する受信語（受信されていない受信語であり、既知シンボルと称しているシンボル）ｙ＝（ｙ248，ｙ249，ｙ250，・・・，ｙ254）に対し、硬判定結果として０を充当する。すなわち、硬判定語ｄ＝（ｄ248，ｄ249，ｄ250，・・・，ｄ254）＝（０，０，０，・・・，０）と設定される（ステップＳ７３の処理）。
【０２８８】
このようにして、硬判定語が設定されたものが用いられ、後段の処理が実行される。すなわち、原始的なＲＳ復号ＲＳ1（２５５，２３９）の符号に対応する受信語ｙ＝（ｙ0，ｙ1，ｙ2，・・・，ｙ254）の硬判定語としてｄ＝（ｄ0，ｄ1，ｄ2，・・・，ｄ254）＝（ｄ0，ｄ1，ｄ2，・・・，ｄ247，０，０，・・・，０）が得られたという仮定の下、Ｇ−Ｓリスト復号やＫ−Ｖリスト復号に基づく、２変数多項式補間条件の抽出、２変数多項式の補間、補間多項式の因数分解、そして、因数分解の結果に基づく復号語リストの作成の処理が実行される（ステップＳ７５以下の処理）。
【０２８９】
このような処理が実行されることにより作成された復号語リストから、１つの復号語が、復号結果として抽出（選択）される。その抽出方法は、例えば、ユークリッド（Euclid）距離が最小である符号語１つに復号が行われる（最尤復号）。
【０２９０】
この最尤復号が行われる前の処理として、復号語リストに含まれる復号語のうち、既知シンボル（ステップＳ７３の処理として硬判定語を設定したシンボル）に該当する箇所と、既知シンボルを比較し、異なるシンボルに復号されている復号語は、リストから除外する。また、仮に符号が短縮化されずに、既知シンボルの該当する箇所に関する送信があったとしても、その実際の硬判定結果にかかわらず、既知シンボルを硬判定シンボルとしても良い。
【０２９１】
このような処理を実行することにより、復号結果として検討しなくてはならないシンボルの数を減らすことができ、処理を低減させることが可能となる。
【０２９２】
ここで、［リスト復号部の処理３について］という部分で説明したリスト復号に関する処理についてさらに説明を加える。
【０２９３】
上記したリスト復号部４３において実行されるリスト復号は、有限体Ｆq上の（ｎ，ｋ）ＲＳ符号、Ｆq上で定義された生成多項式
【数５７】
2006042088.tif 000059
に対して適用することができる。
【０２９４】
２変数多項式の補間条件の抽出方法は、Ｋ−Ｖリスト復号手順Π→Ｍに従わなくても良く、任意の手法を用いて上記リスト復号が実行されるようにしても良い。
【０２９５】
復号語リストが作成された後、１つの符号語に復号する過程は、最尤復号に限らず、任意の復号方法を用いても良い。
【０２９６】
短縮部に相当する部分（受信語として受信されない部分）に充当する値は０に限らず、任意の値でも良い。例えば、任意の既知列｛ｃ248，ｃ249，ｃ260，・・・，ｃ254｝＝｛ａ248，ａ249，ａ260，・・・，ａ254｝としても良い。
【０２９７】
上記した例では、短縮部のシンボル列が、連続的に符号語内に分布している例を示したが、連続的に符号語内に分布しておらず、既知の任意の箇所で短縮化されているような場合でも、本実施の形態を適用することができる。短縮部のシンボルが連続的に符号語内に分布していないような場合、例えば、受信語に含まれるヘッダ内に、どの部分が既知であり、その既知の部分の値がどのような値であるのかを示す情報が含まれ、その情報が用いられて、信頼度の設定の処理などが行えるようにしても良い。
【０２９８】
有限体Ｆq上の（ｎ，ｋ）ＢＣＨ符号の場合においては、Ｆp上で定義された生成多項式ｇ（ｘ）に対して、上記したようなリスト復号の方式を適用することができる。この時、各符号シンボルの取り得る範囲は、Ｆp内に含まれるため、信頼度行列や重複度行列は、ｐ×ｎ行列となる。一般のＢＣＨ符号に対しても、上記したリスト復号の処理を適用することは可能である。
【０２９９】
上記したリスト復号に関する手法は、例示した符号のみに適用できることを示すのではなく、任意の代数幾何符号の復号に適用することができる。
【０３００】
上述したように、本実施の形態によれば、符号化側で適用される符号化方式にかかわらず、復号側で、リスト復号を行うことが可能となる。リスト復号が行うことで、硬判定通常復号などと比較して、より高いエラー訂正機能を実現することが可能となる。
【０３０１】
また、上述したように、本実施の形態によれば、符号化側の符号化方式によらず、復号側でリスト復号を行うことができるので、符号化側（送信側）の装置をリスト復号に適用できる符号化方式で符号化できる装置に切り替えるといったようなことを行わなくて良く、送信側の装置としては既存の装置を用いることができる。
【０３０２】
また、送信側として、リスト復号に適していない符号化を行う装置とリスト復号に適している符号化を行う装置が混在しているような場合でも、例えば、図７のフローチャートに示したステップＳ１７の処理が実行されるようにすれば、異なる方式で符号化されたデータも復号側で扱うことが可能となる。
【０３０３】
ここまでの説明においては、リスト復号できるように復号側で処理を実行するとした。以下の説明においては、符号化側でリスト復号に適した符号化を行い、復号側では、通常のリスト復号（例えば、［Ｇ−Ｓリスト復号について］の部分や［Ｋ−Ｖリスト復号について］の部分で説明したようなリスト復号）を行えるようにしても良い。以下に、符号化側でリスト復号に適した復号化を行う場合について説明する。
【０３０４】
［リスト復号に適した符号化への変更処理１］
この［リスト復号に適した符号化への変更処理１］は、有限体上で与えられる任意の［ｑ−１，ｋ］リードソロモン符号化を行う符号化装置に適用でき、情報ビットを係数にもつLaurent多項式の、所定の符号位置における値を符号語の各要素とする符号化を行うことを特徴とする。
【０３０５】
ここで、情報語ｆ＝（ｆ0，ｆ1，ｆ2，・・・，ｆk-1）とし、
【数５８】
2006042088.tif 000060
とする。
【０３０６】
ここで、ｘ-b+1+iとすることにより、リスト復号に適した符号化を実現することが可能となる。
【０３０７】
このとき、ｆ（ｘ）を符号位置で評価し、符号語とする。
（ｆ（１），ｆ（α），ｆ（α2），・・・，ｆ（αq-2））
但し、αは、有限体Ｆqの原始元とする。
【０３０８】
［リスト復号に適した符号化への変更処理１に対する検証］
上記したように、“ｘ-b+1+iとすることにより、リスト復号に適した符号化を実現することが可能となる”ということについて検証を行う。
【０３０９】
有限体として、元の個数が２4個（＝１６個）の有限体Ｆを考える。有限体Ｆ上の生成多項式を
【数５９】
2006042088.tif 000061
とする。また、αは、有限体Ｆの原始元とする。このような式を生成多項式として巡回符号として得られる［１５，１１］ＲＳ符号は、次のようにして符号化される。
【０３１０】
情報語ｆ＝（ｆ0，ｆ1，ｆ2，ｆ3，ｆ4，ｆ5，ｆ6，ｆ7，ｆ8，ｆ9，ｆ10）
に対し、
【数６０】
2006042088.tif 000062
が作られる。そして、（ｆ（１），ｆ（α），ｆ（α2），・・・，ｆ（α14））と符号化される。
【０３１１】
このようにして定義された符号の生成多項式は、
【数６１】
2006042088.tif 000063
で与えられること、また、巡回符号であることを、以下のようにして確認する。まず、生成多項式が、
【数６２】
2006042088.tif 000064
であることについて確認する。
【０３１２】
この確認は、任意の情報（情報多項式）による符号多項式
【数６３】
2006042088.tif 000065
の共通零点が１，α，α2，α3であることが示されれば良い。
【０３１３】
そこで、
【数６４】
2006042088.tif 000066
とする。
【０３１４】
このとき、
【数６５】
2006042088.tif 000067
となることから、０≦ｊ≦１０に対して、ｌ＝０，１，２，３のとき、また、そのようなときに限り、１≦１＋ｊ＋ｌ≦１４が満足され、ｃ（αl）＝０となることがわかる。よって、生成多項式は、
【数６６】
2006042088.tif 000068
であることが確認された。
【０３１５】
次に、巡回符号であることを確認する。
【０３１６】
生成行列Ｇは、
【数６７】
2006042088.tif 000069
である。
【０３１７】
この生成行列Ｇの形から、生成行列Ｇの各行を巡回置換したものが、その各行のスカラー倍になっていることがわかり、巡回符号であることがわかる。そのことを示す一例とし、ここで、上記した生成行列Ｇの第２行目を右に巡回する例を示す。
【０３１８】
（α28，１，α2，α4，α6，α8，α10，α12，α14，α18，α20，α22，α24，α26）
＝α28（１，α―28，α―26，α―24，α―22，α―20，α―18，α―16，α―14，α―12，α―10，α―8，α―6，α―4，α―2）
＝（１，α2，α4，α6，α8，α10，α12，α14，α16，α18，α20，α22，α24，α26，α28）
となる。なお、ここでは、α15＝１としている。
【０３１９】
このように、生成多項式であること、巡回符号であることが確認された。
【０３２０】
このように、任意の生成多項式により巡回符号として得られる符号と、同一の符号を符号位置の評価により符号化することが可能となる。
【０３２１】
［リスト復号に適した符号化への変更処理２］
次に、他の復号化の方法について説明する。この［リスト復号に適した符号化への変更処理２］は、有限体上で与えられる任意の［ｑ−１，ｋ］リードソロモン符号の双対符号の符号化を行う符号化装置に適用でき、情報ビットを係数にもつ多項式の、所定の符号位置における値を符号語の各要素とする符号化を行うことを特徴とする。
【０３２２】
ここで、情報語ｆ＝（ｆ0，ｆ1，ｆ2，・・・，ｆq-k-2）とし、
【数６８】
2006042088.tif 000070
とする。
【０３２３】
ここで、ｘj+bとすることにより、リスト復号に適した符号化を実現することが可能となる。
【０３２４】
このとき、ｆ（ｘ）を符号位置で評価し、符号語とする。
（ｆ（１），ｆ（α），ｆ（α2），・・・，ｆ（αq-2））
但し、αは、有限体Ｆqの原始元とする。
【０３２５】
［リスト復号に適した符号化への変更処理２に対する検証］
上記したように、“ｘj+bとすることにより、リスト復号に適した符号化を実現することが可能となる”ということについて検証を行う。
【０３２６】
有限体として、元の個数が２4個（＝１６個）の有限体Ｆを考える。有限体Ｆ上の生成多項式を
【数６９】
2006042088.tif 000071
とする。また、αは、有限体Ｆの原始元とする。このような式を生成多項式として巡回符号として得られる［１５，１１］ＲＳ符号の双対符号［１５，４］は、次のようにして符号化される。
【０３２７】
情報語ｆ＝（ｆ0，ｆ1，ｆ2，ｆ3）
に対し、
【数７０】
2006042088.tif 000072
が作られる。そして、（ｆ（１），ｆ（α），ｆ（α2），・・・，ｆ（α14））と符号化される。
【０３２８】
このようにして定義された符号の生成多項式が［１５，１１］ＲＳ符号の双対符号であることをここで確認する。
【０３２９】
［リスト復号に適した符号化への変更処理２］として説明した方法により符号化された双対符号は、基底として、
（１，αl，α2l，・・・，α14l）
が取れる。ｌは、０，１，２，３のいずれかの値である。
【０３３０】
そこで、［１５，１１］ＲＳ符号の符号語ｃ＝（ｃ0，ｃ1，ｃ2，・・・，ｃ14）との内積を考えると、［１５，１１］の符号多項式の共通根が、１，α，α2，α3であることから、
【数７１】
2006042088.tif 000073
が成り立つことがわかる。
【０３３１】
このことにより、［リスト復号に適した符号化への変更処理２］として定義した符号化方式が、ＲＳ符号の双対符号であることが確認される。
【０３３２】
このように、任意の生成多項式により巡回符号として得られる符号の双対符号を符号位置の評価により符号化することが可能となる。
【０３３３】
本実施の形態として説明した符号化や復号に関することは、環Ｒ上代数符号、それと同型な符号、その部分体部分符号などに関する符号化や復号に適用することが可能である。
【０３３４】
［記録媒体について］
上述した一連の処理は、それぞれの機能を有するハードウェアにより実行させることもできるが、ソフトウェアにより実行させることもできる。一連の処理をソフトウェアにより実行させる場合には、そのソフトウェアを構成するプログラムが専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどに、記録媒体からインストールされる。
【０３３５】
図１３は、汎用のパーソナルコンピュータの内部構成例を示す図である。パーソナルコンピュータのＣＰＵ（Central Processing Unit）２０１は、ＲＯＭ（Read Only Memory）２０２に記憶されているプログラムに従って各種の処理を実行する。ＲＡＭ（Random Access Memory）２０３には、ＣＰＵ２０１が各種の処理を実行する上において必要なデータやプログラムなどが適宜記憶される。入出力インタフェース２０５は、キーボードやマウスから構成される入力部２０６が接続され、入力部２０６に入力された信号をＣＰＵ２０１に出力する。また、入出力インタフェース２０５には、ディスプレイやスピーカなどから構成される出力部２０７も接続されている。
【０３３６】
さらに、入出力インタフェース２０５には、ハードディスクなどから構成される記憶部２０８、および、インターネットなどのネットワークを介して他の装置とデータの授受を行う通信部２０９も接続されている。ドライブ２１０は、磁気ディスク２２１、光ディスク２２２、光磁気ディスク２２３、半導体メモリ２２４などの記録媒体からデータを読み出したり、データを書き込んだりするときに用いられる。
【０３３７】
記録媒体は、図１３に示すように、パーソナルコンピュータとは別に、ユーザにプログラムを提供するために配布される、プログラムが記録されている磁気ディスク２２１（フレキシブルディスクを含む）、光ディスク２２２（CD-ROM（Compact Disc-Read Only Memory），DVD（Digital Versatile Disc）を含む）、光磁気ディスク２２３（MD（Mini-Disc）（登録商標）を含む）、若しくは半導体メモリ２２４などよりなるパッケージメディアにより構成されるだけでなく、コンピュータに予め組み込まれた状態でユーザに提供される、プログラムが記憶されているＲＯＭ２０２や記憶部２０８が含まれるハードディスクなどで構成される。
【０３３８】
なお、本明細書において、媒体により提供されるプログラムを記述するステップは、記載された順序に従って、時系列的に行われる処理は勿論、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０３３９】
また、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【図面の簡単な説明】
【０３４０】
【図１】本発明が適用されるシステムの一実施の形態の構成を示す図である。
【図２】システムの構成例を示す図である。
【図３】システムの構成例を示す図である。
【図４】システムの構成例を示す図である。
【図５】システムの構成例を示す図である。
【図６】リスト復号部の内部構成例を示す図である。
【図７】リスト復号部の動作を説明するフローチャートである。
【図８】補間について説明するための図である。
【図９】エラー訂正能力の向上について説明するための図である。
【図１０】リスト復号部の他の動作を説明するフローチャートである。
【図１１】エラー訂正能力の向上について説明するための図である。
【図１２】リスト復号部のさらに他の動作を説明するフローチャートである。
【図１３】媒体を説明する図である。
【符号の説明】
【０３４１】
１  符号化器，  ２  復号器，  ３  記録媒体，  ２１  ＲＤ符号化部，  ２２  インタリーブ部，  ２３  畳み込み符号化部，  ３１  チャネル，  ４１  畳み込み復号部，  ４２  デインタリーブ部，  ４３  リスト復号部，  １０１  入力部，  １０２  判断部，  １０３  信頼度計算部，  １０４  重複度計算部，  １０５  補間処理部，  １０６  因数分解処理部，  １０７  リスト作成部，  １０８  出力部
【図１】
2006042088.tif 000080
【図２】
2006042088.tif 000081
【図３】
2006042088.tif 000082
【図４】
2006042088.tif 000083
【図５】
2006042088.tif 000084
【図６】
2006042088.tif 000085
【図７】
2006042088.tif 000086
【図８】
2006042088.tif 000087
【図９】
2006042088.tif 000088
【図１０】
2006042088.tif 000089
【図１１】
2006042088.tif 000090
【図１２】
2006042088.tif 000091
【図１３】
2006042088.tif 000092