(57)【要約】【課題】重複度計算の複雑性を低減するように、ＲＳ復号化における重複度の計算方法及び計算装置を提供する。又、ＲＳ符号の代数的な軟判定復号の複雑性を低減するように、ＲＳ復号化方法及びＲＳ復号器を提供する。【解決手段】本発明に係る計算方法は、信頼度行列と重複度計算の目標値とを入力し、前記目標値を１つの独立変数の単調増加関数または単調減少関数で表すステップと、目標値が当該独立変数の単調増加関数または単調減少関数である特性を利用して、当該独立変数に対して高速反復を行って目標値に対応する独立変数値を計算し、前記信頼度行列と計算した前記独立変数値とに基づいて重複度行列を計算するステップと、を含む。また、ＲＳ復号化における重複度の計算装置、ＲＳ復号器およびその復号方法を開示している。本発明を応用することで、重複度計算の複雑性が顕著に低減でき、ＲＳ符号の代数的な軟判定復号の複雑性を低減できる。【選択図】図１
2008154238.tif 000002
【特許請求の範囲】
【請求項１】
ＲＳ復号化における重複度の計算方法であって、
信頼度行列と重複度計算の目標値とを入力し、前記目標値を１つの独立変数の単調増加関数または単調減少関数で表すステップと、
目標値が当該独立変数の単調増加関数または単調減少関数である特性を利用して、当該独立変数に対して高速反復を行って目標値に対応する独立変数値を計算し、前記信頼度行列と計算した前記独立変数値とに基づいて重複度行列を計算するステップと、
を含むことを特徴とするＲＳ復号化における重複度の計算方法。
【請求項２】
前記独立変数に対して高速反復を行うことは、
二分法のアルゴリズムまたは黄金分割法のアルゴリズムにより独立変数に対して高速反復を行うこと、
を含むことを特徴とする請求項１に記載のＲＳ復号化における重複度の計算方法。
【請求項３】
前記目標値は重複度計算の補間点の数であり、前記高速反復は、
独立変数に対して、目標値に対応する独立変数値より大きい上限値と、目標値に対応する独立変数値より小さい下限値とを取るステップＡ１と、
上限値と下限値との間の１点の目的関数値を計算し、当該点の目的関数値が前記補間点の数より小さいかどうかを判断し、小さい場合、当該点の独立変数値で下限値を更新し、小さくない場合、当該点の独立変数値で上限値を更新するステップＢ１と、
上限値と下限値との差が予め設定された閾値より小さいかどうかを判断し、小さい場合、前記高速反復を終了し、小さくない場合、ステップＢ１に戻るステップＣ１と、
を含むことを特徴とする請求項１に記載のＲＳ復号化における重複度の計算方法。
【請求項４】
前記下限値は
【数１】
2008154238.tif 000250
であり、前記上限値は
【数２】
2008154238.tif 000251
であり、且つ
【数３】
2008154238.tif 000252
ここで、ＮはＲＳ符号の符号長であり、ｓは前記補間点の数であり、 
【数４】
2008154238.tif 000253
は変調次数である、
ことを特徴とする請求項３に記載のＲＳ復号化における重複度の計算方法。
【請求項５】
前記目標値はコスト値であり、前記高速反復は、
独立変数に対して、目標値に対応する独立変数値より大きい上限値と、目標値に対応する独立変数値より小さい下限値とを取るステップＡ２と、
上限値と下限値との間の１点の目的関数値を計算し、当該点の目的関数値が前記コスト値より小さいかどうかを判断し、小さい場合、当該点の独立変数値で下限値を更新し、小さくない場合、当該点の独立変数値で上限値を更新するステップＢ２と、
上限値と下限値との差が予め設定された閾値より小さいかどうかを判断し、小さい場合、前記高速反復を終了し、小さくない場合、ステップＢ２に戻るステップＣ２と、
を含むことを特徴とする請求項１に記載のＲＳ復号化における重複度の計算方法。
【請求項６】
前記下限値は
【数５】
2008154238.tif 000254
であり、前記上限値は
【数６】
2008154238.tif 000255
であり、且つ、
【数７】
2008154238.tif 000256
ここで、ＮはＲＳ符号の符号長であり、Ｃは前記コスト値であり、
【数８】
2008154238.tif 000257
は変調次数であり、
【数９】
2008154238.tif 000258
は信頼度行列のｉ行目ｊ列目の要素である、
ことを特徴とする請求項５に記載のＲＳ復号化における重複度の計算方法。
【請求項７】
前記信頼度行列が信頼度完全行列または信頼度疎行列であることを特徴とする請求項１〜請求項６のいずれか１項に記載のＲＳ復号化における重複度の計算方法。
【請求項８】
ＲＳ復号化における重複度の計算装置であって、
信頼度行列と重複度計算の目標値とを受信する入力モジュールと、
前記目標値を１つの独立変数の単調関数で表す目標値表示モジュールと、
目標値が独立変数の単調関数である特性を利用して、当該独立変数に対して高速反復を行って目標値に対応する独立変数値を計算し、前記信頼度行列と計算した前記独立変数値とに基づいて重複度行列を計算する重複度行列計算モジュールと、
を備えることを特徴とするＲＳ復号化における重複度の計算装置。
【請求項９】
前記目標値表示モジュールが、前記目標値を１つの独立変数の単調増加関数で表し、または前記目標値を１つの独立変数の単調減少関数で表すことを特徴とする請求項８に記載のＲＳ復号化における重複度の計算装置。
【請求項１０】
前記入力モジュールが信頼度完全行列または信頼度疎行列を受信することを特徴とする請求項８に記載のＲＳ復号化における重複度の計算装置。
【請求項１１】
前記重複度行列計算モジュールが二分法のアルゴリズムまたは黄金分割法のアルゴリズムにより前記独立変数に対して高速反復を行うことを特徴とする請求項８〜請求項１０のいずれか１項に記載のＲＳ復号化における重複度の計算装置。
【請求項１２】
ＲＳ符号の復号器であって、
入力された信頼度行列と重複度計算の目標値とに基づいて重複度行列を計算し、ここで、目標値を１つの独立変数の単調関数で表し、目標値が独立変数の単調関数である特性を利用して、当該独立変数に対して高速反復を行って目標値に対応する独立変数値を計算し、計算した前記独立変数値と前記信頼度行列とに基づいて重複度行列を計算する重複度の計算装置と、
前記計算された重複度行列に基づいて、二変数多項式の係数を計算して二変数多項式を得る二変数多項式補間装置と、
得られた二変数多項式を分解して、リスト復号の候補コードワードを得る二変数多項式分解装置と、
を含むことを特徴とするＲＳ符号の復号器。
【請求項１３】
ＲＳ符号の復号方法であって、
信頼度行列と重複度計算の目標値とを入力し、前記目標値を１つの独立変数の単調関数で表し、目標値が当該独立変数の単調関数である特性を利用して、当該独立変数に対して高速反復を行って目標値に対応する独立変数値を計算し、前記信頼度行列と計算した前記独立変数値とに基づいて重複度行列を計算するステップと、
前記計算された重複度行列に基づいて二変数多項式の係数を計算して二変数多項式を得、得られた二変数多項式を分解してリスト復号の候補コードワードを得るステップと、
を含むことを特徴とするＲＳ符号の復号方法。
【請求項１４】
前記目標値は重複度計算の補間点の数であり、前記高速反復は、
独立変数に対して、目標値に対応する独立変数値より大きい上限値と、目標値に対応する独立変数値より小さい下限値とを取るステップＡ３と、
上限値と下限値との間の１点の目的関数値を計算し、当該点の目的関数値が前記補間点の数より小さいかどうかを判断し、小さい場合、当該点の独立変数値で下限値を更新し、小さくない場合、当該点の独立変数値で上限値を更新するステップＢ３と、
上限値と下限値との差が予め設定された閾値より小さいかどうかを判断し、小さい場合、前記高速反復を終了し、小さくない場合、ステップＢ３に戻るステップＣ３と、
を含むことを特徴とする請求項１３に記載のＲＳ符号の復号方法。
【請求項１５】
前記目標値はコスト値であり、前記高速反復は、
独立変数に対して、目標値に対応する独立変数値より大きい上限値と、目標値に対応する独立変数値より小さい下限値とを取るステップＡ４と、
上限値と下限値との間の１点の目的関数値を計算し、当該点の目的関数値が前記コスト値より小さいかどうかを判断し、小さい場合、当該点の独立変数値で下限値を更新し、小さくない場合、当該点の独立変数値で上限値を更新するステップＢ４と、
上限値と下限値との差が予め設定された閾値より小さいかどうかを判断し、小さい場合、前記高速反復を終了し、小さくない場合、ステップＢ４に戻るステップＣ４と、
を含むことを特徴とする請求項１３に記載のＲＳ符号の復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はＲＳ復号化技術分野に関し、特にＲＳ復号化における重複度（Ｍｕｌｔｉｐｌｉｃｉｔｙ）の計算方法、装置並びに復号器および復号方法に関する。
【背景技術】
【０００２】
リードソロモン（ＲＳ：Ｒｅｅｄ−Ｓｏｌｏｍｏｎ）符号は２０世紀１９６０年代に既に提出され、現在では、有線や無線および深宇宙通信（Ｄｅｅｐ  Ｓｐａｃｅ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ）システムなどのデジタル通信システム、データ記憶や符号圧縮などのシステムに幅広く応用されている。ＲＳ符号は線形ブロック符号（Ｌｉｎｅａｒ  ｂｌｏｃｋ  ｃｏｄｅｓ）の１種であり、そのコードワードが最大距離分離（ＭＤＳ：Ｍａｘｉｍｕｍ  Ｄｉｓｔａｎｃｅ  Ｓｅｐａｒａｂｌｅ）特性を有し、バーストエラーおよびチャネルフェージング（ｃｈａｎｎｅｌ  ｆａｄｉｎｇ）に対する良好な耐性を有する。
【０００３】
長年来、人々が硬判定または非代数的な軟判定の方法によりＲＳ符号を復号することで、ＲＳ符号の誤り訂正潜在力が充分に発揮されていない。したがって、ＲＳ符号の復号性能は長い間、シャノン（Ｓｈａｎｎｏｎ）限界に近いターボ（Ｔｕｒｂｏ）符号や低密度パリティ検査（ＬＤＰＣ：Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ）符号に匹敵できない。
【０００４】
最近、ＲＳ符号の代数的な軟判定（Ａｌｇｅｂｒａｉｃ  Ｓｏｆｔ  Ｄｅｃｉｓｉｏｎ）復号が若干の突破的な進展を見せていることによって、当該符号が、チャネルフェージング対策、ショートコード、情報源圧縮などを含む多くの応用分野において、Ｔｕｒｂｏ符号やＬＤＰＣ符号に比べてさらに性能メリットを有することが見られる。ＲＳ符号の代数的な軟判定復号の作業は１９９７年ＳｕｄａｎのＲＳ符号のリスト復号（ｌｉｓｔ  ｄｅｃｏｄｉｎｇ）の作業からスタートした。Ｓｕｄａｎのリスト復号の作業によりＲＳ符号の復号器の誤り訂正能力が極めて高められた。ＧｕｒｕｓｗａｍｉなどはＳｕｄａｎの作業を改良し、ＲＳ符号の復号器の誤り訂正性能をさらに強めている。ＧｕｒｕｓｗａｍｉとＳｕｄａｎの作業の上に、ＫｏｅｔｔｅｒとＶａｒｄｙは代数的な軟判定復号を提出したことによって、当該符号の復号性能がＴｕｒｂｏ符号やＬＤＰＣ符号に匹敵でき、ひいてはこれらの符号を超える可能性もある。
【０００５】
次に、ＲＳ符号の代数的な軟判定復号を説明する。ＲＳ符号の代数的な軟判定復号は、重複度計算と、二変数多項式の補間計算と、二変数多項式の分解との３つのキーステップを含む。重複度計算に対して、大多数の場合、ＲＳ復号器に入力される情報は受信シンボルの確率信頼度情報である。一般的に、当該情報は「ソフト情報」と呼ばれる。Ｇｕｒｕｓｗａｍｉ−Ｓｕｄａｎ（Ｇ−Ｓ）リスト復号を行うことができるように、確率ソフト情報はＧ−Ｓリスト復号の補間点の重複度に転換される必要がある。
【０００６】
硬判定復号および非代数的な軟判定復号に対して、ＲＳ符号の代数的な軟判定の復号器はさらに優れた復号性能を有しているが、その復号の複雑性もさらに高い。ＲＳ符号の代数的な軟判定復号の複雑性を低減するために、二変数多項式補間および二変数多項式分解に対して膨大な研究が行われ、分割統治法（ｄｉｖｉｄｅ  ａｎｄ  ｃｏｎｑｕｅｒ  ｍｅｔｈｏｄ）を含む種々の方法が研究された。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、若干の改良をしたにしても、従来技術における重複度計算ステップの複雑性がやはり高いため、ＲＳ符号の代数的な軟判定復号の複雑性がやはり非常に高い。また、従来技術では、ある方式を通じて重複度計算ステップの複雑性を制御することができるにしても、目標値を制御できないため、その結果、やはり、補間および分解ステップの複雑性の増大や、復号器性能の低下につながる恐れがある。この２つの場合とも実際的なシステムにおいて引き受けられないものである。
【０００８】
本発明は上記の事情に鑑みてなされたものである。本発明の主な目的は、重複度計算の複雑性を低減するように、ＲＳ復号化における重複度の計算方法を提供することである。
【０００９】
本発明のもう１つの目的は、重複度計算の複雑性を低減するように、ＲＳ復号化における重複度の計算装置を提供することである。
【００１０】
本発明のもう１つの目的は、ＲＳ符号の代数的な軟判定復号の複雑性を低減するように、ＲＳ復号器を提供することである。
【００１１】
本発明のもう１つの目的は、ＲＳ符号の代数的な軟判定復号の複雑性を低減するように、ＲＳ復号化方法を提供することである。
【課題を解決するための手段】
【００１２】
上記目的を達成するため、本発明の解決手段は下記のように実現されたものである。
【００１３】
ＲＳ復号化における重複度の計算方法であって、
信頼度行列（ｒｅｌｉａｂｉｌｉｔｙ  ｍａｔｒｉｘ）と重複度計算の目標値とを入力し、前記目標値を１つの独立変数の単調増加関数または単調減少関数で表すステップと、
目標値が当該独立変数の単調増加関数または単調減少関数である特性を利用して、当該独立変数に対して高速反復（ｉｔｅｒａｔｉｏｎ）を行って目標値に対応する独立変数値を計算し、前記信頼度行列と計算した前記独立変数値とに基づいて重複度行列を計算するステップと、を含む。
【００１４】
前記独立変数に対して高速反復を行うことは、二分法のアルゴリズムまたは黄金分割法のアルゴリズムにより独立変数に対して高速反復を行うことを含む。
【００１５】
前記目標値は重複度計算の補間点の数であり、前記高速反復は、具体的に、
独立変数に対して、目標値に対応する独立変数値より大きい上限値と、目標値に対応する独立変数値より小さい下限値とを取るステップＡ１と、
上限値と下限値との間の１点の目的関数値を計算し、当該点の目的関数値が前記補間点の数より小さいかどうかを判断し、小さい場合、当該点の独立変数値で下限値を更新し、小さくない場合、当該点の独立変数値で上限値を更新するステップＢ１と、
上限値と下限値との差が予め設定された閾値より小さいかどうかを判断し、小さい場合、前記高速反復を終了し、小さくない場合、ステップＢ１に戻るステップＣ１と、を含む。
【００１６】
前記下限値は
【数１】
2008154238.tif 000003
【００１７】
であり、前記上限値は
【数２】
2008154238.tif 000004
【００１８】
であり、
【数３】
2008154238.tif 000005
【００１９】
ここで、ＮはＲＳ符号の符号長であり、ｓは前記補間点の数であり、
【数４】
2008154238.tif 000006
【００２０】
は変調次数である。
【００２１】
前記目標値はコスト値であり、前記高速反復は、具体的に、
独立変数に対して、目標値に対応する独立変数値より大きい上限値と、目標値に対応する独立変数値より小さい下限値とを取るステップＡ２と、
上限値と下限値との間の１点の目的関数値を計算し、当該点の目的関数値が前記コスト値より小さいかどうかを判断し、小さい場合、当該点の独立変数値で下限値を更新し、小さくない場合、当該点の独立変数値で上限値を更新するステップＢ２と、
上限値と下限値との差が予め設定された閾値より小さいかどうかを判断し、小さい場合、前記高速反復を終了し、小さくない場合、ステップＢ２に戻るステップＣ２と、を含む。
【００２２】
前記下限値は
【数５】
2008154238.tif 000007
【００２３】
であり、前記上限値は
【数６】
2008154238.tif 000008
【００２４】
であり、且つ、
【数７】
2008154238.tif 000009
【００２５】
ここで、ＮはＲＳ符号の符号長であり、Ｃは前記コスト値であり、
【数８】
2008154238.tif 000010
【００２６】
は変調次数であり、
【数９】
2008154238.tif 000011
【００２７】
は信頼度行列のｉ行目ｊ列目の要素である。
【００２８】
前記信頼度行列は信頼度完全行列（ｒｅｌｉａｂｉｌｉｔｙ  ｆｕｌｌ  ｍａｔｒｉｘ）または信頼度疎行列（ｒｅｌｉａｂｉｌｉｔｙ  ｓｐａｒｓｅ  ｍａｔｒｉｘ）である。
【００２９】
ＲＳ復号化における重複度の計算装置であって、
信頼度行列と重複度計算の目標値とを受信する入力モジュールと、
前記目標値を１つの独立変数の単調関数で表す目標値表示モジュールと、
目標値が独立変数の単調関数である特性を利用して、当該独立変数に対して高速反復を行って目標値に対応する独立変数値を計算し、前記信頼度行列と計算した前記独立変数値とに基づいて重複度行列を計算する重複度行列計算モジュールと、を含む。
【００３０】
前記目標値表示モジュールは、前記目標値を１つの独立変数の単調増加関数で表し、または前記目標値を１つの独立変数の単調減少関数で表す。
【００３１】
前記入力モジュールは、信頼度完全行列または信頼度疎行列を受信する。
【００３２】
前記重複度行列計算モジュールは、二分法のアルゴリズムまたは黄金分割法のアルゴリズムにより前記独立変数に対して高速反復を行う。
【００３３】
ＲＳ符号の復号器であって、
入力された信頼度行列と重複度計算の目標値とに基づいて重複度行列を計算し、ここで、目標値を１つの独立変数の単調関数で表し、目標値が独立変数の単調関数である特性を利用して、当該独立変数に対して高速反復を行って目標値に対応する独立変数値を計算し、計算した前記独立変数値と前記信頼度行列とに基づいて重複度行列を計算する重複度の計算装置と、
前記計算された重複度行列に基づいて、二変数多項式の係数を計算して二変数多項式を得る二変数多項式補間装置と、
得られた二変数多項式を分解して、リスト復号の候補コードワードを得る二変数多項式分解装置と、を含む。
【００３４】
ＲＳ符号の復号方法であって、
信頼度行列と重複度計算の目標値とを入力し、前記目標値を１つの独立変数の単調関数で表し、目標値が当該独立変数の単調関数である特性を利用して、当該独立変数に対して高速反復を行って目標値に対応する独立変数値を計算し、前記信頼度行列と計算した前記独立変数値とに基づいて重複度行列を計算するステップと、
前記計算された重複度行列に基づいて二変数多項式の係数を計算して二変数多項式を得、得られた二変数多項式を分解してリスト復号の候補コードワードを得るステップと、を含む。
【００３５】
前記目標値は重複度計算の補間点の数であり、前記高速反復は、具体的に、
独立変数に対して、目標値に対応する独立変数値より大きい上限値と、目標値に対応する独立変数値より小さい下限値とを取るステップＡ３と、
上限値と下限値との間の１点の目的関数値を計算し、当該点の目的関数値が前記補間点の数より小さいかどうかを判断し、小さい場合、当該点の独立変数値で下限値を更新し、小さくない場合、当該点の独立変数値で上限値を更新するステップＢ３と、
上限値と下限値との差が予め設定された閾値より小さいかどうかを判断し、小さい場合、前記高速反復を終了し、小さくない場合、ステップＢ３に戻るステップＣ３と、を含む。
【００３６】
前記目標値はコスト値であり、前記高速反復は、具体的に、
独立変数に対して、目標値に対応する独立変数値より大きい上限値と、目標値に対応する独立変数値より小さい下限値とを取るステップＡ４と、
上限値と下限値との間の１点の目的関数値を計算し、当該点の目的関数値が前記コスト値より小さいかどうかを判断し、小さい場合、当該点の独立変数値で下限値を更新し、小さくない場合、当該点の独立変数値で上限値を更新するステップＢ４と、
上限値と下限値との差が予め設定された閾値より小さいかどうかを判断し、小さい場合、前記高速反復を終了し、小さくない場合、ステップＢ４に戻るステップＣ４と、を含む。
【発明の効果】
【００３７】
上記解決手段からわかるように、本発明において、目標値を１つの独立変数の単調関数で表し、目標値が当該独立変数の単調関数である特性を利用して、当該独立変数に対して高速反復を行って目標値に対応する独立変数値を計算し、前記信頼度行列と計算した前記独立変数値とに基づいて重複度行列を計算する。ここからわかるように、本発明では、単調関数特性をＲＳ符号の代数的な軟判定復号の重複度計算に導入して、適当な初期値を見付け、種々の高速反復アルゴリズムにより重複度行列を高速に計算することができる。したがって、重複度計算の複雑性が顕著に低減しており、これにより、ＲＳ符号の復号の複雑性が低減している。
【００３８】
また、本発明において、設定された独立変数の下限値と上限値との間に１つの点を選択し、当該点の関数値と目標値との大きさを比較し、当該比較結果に基づいて下限値または上限値を更新することにより、高速探索が実現されている。
【００３９】
なお、本発明において、採用された反復アルゴリズムは黄金分割法や二分法などのアルゴリズムを含む種々の高速反復アルゴリズムであってもよいため、種々の具体的な応用に非常に便利である。
【発明を実施するための最良の形態】
【００４０】
本発明の目的、解決手段およびメリットをさらに明確にするように、以下、図面および具体的な実施例を参照しながら本発明についてさらに詳しく説明する。
【００４１】
ＲＳ符号の代数的な軟判定復号は、伝統的な硬判定復号および非代数的な軟判定復号に比べて、さらに良い復号性能を有しているが、複雑性もさらに高い。重複度計算ステップの演算量は全体の代数的な軟判定復号器で相当な比重を占めている。
【００４２】
通常の場合、ＲＳ符号の代数的な軟判定復号を実現する重複度計算の計算量は
【数１０】
2008154238.tif 000012
【００４３】
である。ここで、
【数１１】
2008154238.tif 000013
【００４４】
は符号長である。変調次数ｑが比較的大きい場合、重複度計算に所要の計算量が大きい。常に選択可能なｑ値、例えば２５６に対して、重複度計算を実現する所要の演算操作（例えば、メモリのアクセス、比較など）数が
【数１２】
2008154238.tif 000014
【００４５】
に達する可能性がある。
【００４６】
本発明では重複度計算ステップの複雑性を低減することによって、ＲＳ符号の代数的な軟判定復号器の複雑性を明らかに低減することができる。
【００４７】
まず、本発明のアルゴリズム原理について詳しく説明する。
【００４８】
符号長
【数１３】
2008154238.tif 000015
【００４９】
、情報長
【数１４】
2008154238.tif 000016
【００５０】
のＲＳ符号に対して、情報多項式が
【数１５】
2008154238.tif 000017
【００５１】
であるとし、ここで、情報記号
【数１６】
2008154238.tif 000018
【００５２】
は有限体ＧＦ（ｑ）に定義される要素である。
【００５３】
有限体ＧＦ（ｑ）において、
【数１７】
2008154238.tif 000019
【００５４】
個の異なる非ゼロ要素を選択して、集合
【数１８】
2008154238.tif 000020
【００５５】
を得る。集合
【数１９】
2008154238.tif 000021
【００５６】
はＲＳ符号化に用いられることができる。
【００５７】
ＲＳコードワードの集合は下記のように記載されてよい。
【数２０】
2008154238.tif 000022
【００５８】
送信されるＲＳ符号系列が
【数２１】
2008154238.tif 000023
【００５９】
であるとする。
【００６０】
当該系列は、変調後チャネルに送られ、チャネル雑音および干渉の影響を受け、受信側に到着して系列
【数２２】
2008154238.tif 000024
【００６１】
となる。
【００６２】
ＲＳ符号の代数的な軟判定復号器は、受信した複素系列
【数２３】
2008154238.tif 000025
【００６３】
に基づいて、送信側の若干の最大の送信可能な情報多項式を再構築する。当該プロセスはリスト復号と呼ばれる。
【００６４】
ＲＳ符号のリスト復号を実現するために、受信した入力情報から補間点情報と補間点に対応する重複度情報とを抽出する必要がある。
【００６５】
実際的なシステムにおいて、受信側が得られる情報はいつも確率信頼度情報である。ＲＳ符号の代数的な軟判定復号を実現するために、これらの確率情報が補間点および対応の重複度情報に転換される必要がある。当該転換は、即ち重複度計算である。
【００６６】
復号器が多項式
【数２４】
2008154238.tif 000026
【００６７】
を列挙し、受信したベクトル
【数２５】
2008154238.tif 000027
【００６８】
に対応する確率信頼度行列が
【数２６】
2008154238.tif 000028
【００６９】
であるとする。
【００７０】
ここで、行列
【数２７】
2008154238.tif 000029
【００７１】
は、受信した系列が
【数２８】
2008154238.tif 000030
【００７２】
である条件で、送信された情報多項式が
【数２９】
2008154238.tif 000031
【００７３】
である場合に、第ｊ個の符号化シンボルがｉ−１である確率を表す。
【００７４】
ある
【数３０】
2008154238.tif 000032
【００７５】
であれば、補間点
【数３１】
2008154238.tif 000033
【００７６】
を得る。当該補間点は、重複度と呼ばれる非負整数
【数３２】
2008154238.tif 000034
【００７７】
に対応する。
【００７８】
補間点
【数３３】
2008154238.tif 000035
【００７９】
に対応する重複度が
【数３４】
2008154238.tif 000036
【００８０】
であれば、当該点に対して、ＲＳ符号の代数的な軟判定復号の補間ステップでは、
【数３５】
2008154238.tif 000037
【００８１】
個の拘束方程式が生じる。
【００８２】
行列
【数３６】
2008154238.tif 000038
【００８３】
に対応する重複度行列を
【数３７】
2008154238.tif 000039
【００８４】
とすれば、補間ステップで生じた拘束方程式の数は、
【数３８】
2008154238.tif 000040
【００８５】
となり、コストと呼ばれる。
【００８６】
コスト値が高ければ高いほど、補間および分解ステップで所要の複雑性も高くなる。
【００８７】
一方、重複度行列の各要素
【数３９】
2008154238.tif 000041
【００８８】
を確率と乗算した値が
【数４０】
2008154238.tif 000042
【００８９】
である。重複度行列
【数４１】
2008154238.tif 000043
【００９０】
に対応して
【数４２】
2008154238.tif 000044
【００９１】
個のこのような積が得られ、これらの積を加算して得られる値
【数４３】
2008154238.tif 000045
【００９２】
をスコアと定義する。Ｋｏｅｔｔｅｒなどの研究からわかるように、当該スコアが高ければ高いほど、代数的な軟判定復号器の出力性能が良くなる。
【００９３】
実際の復号器は有限の複雑性しか容認できない。。重複度計算は、補間および分解ステップの複雑性が一定である場合にスコアを最大化し、または、スコアが一定である場合に補間および分解ステップの複雑性を最小化する必要がある。
【００９４】
換言すれば、重複度計算は、コストが一定である場合にスコアを最大化し、または、スコアが一定である場合にコストを最小化する必要がある。前者は、重複度行列集合を
【数４４】
2008154238.tif 000046
【００９５】
とすれば、実際には行列
【数４５】
2008154238.tif 000047
【００９６】
を探すことである。
【００９７】
従来技術と本発明との区別をさらに明確に説明するように、まず、従来のＫｏｔｔｅｒアルゴリズムを概略的に説明する。最適な重複度行列を計算するために、Ｋｏｔｔｅｒなどによって以下のアルゴリズムが与えられている。
【００９８】
入力が、信頼度行列
【数４６】
2008154238.tif 000048
【００９９】
、および重複度で計算する補間点の数ｓである場合（第１場合）：
入力は、信頼度行列
【数４７】
2008154238.tif 000049
【０１００】
、および重複度で計算する補間点の数ｓで、出力は、
【数４８】
2008154238.tif 000050
【０１０１】
を満たす最適な重複度行列
【数４９】
2008154238.tif 000051
【０１０２】
である。ステップ１において、下記のように設定する。
【数５０】
2008154238.tif 000052
【０１０３】
ステップ２において、行列
【数５１】
2008154238.tif 000053
【０１０４】
内の最大値位置
【数５２】
2008154238.tif 000054
【０１０５】
に対応する位置
【数５３】
2008154238.tif 000055
【０１０６】
を探し、位置
【数５４】
2008154238.tif 000056
【０１０７】
に対応する値およびカウンター
【数５５】
2008154238.tif 000057
【０１０８】
を下記のように更新する。
【数５６】
2008154238.tif 000058
【０１０９】
ステップ３において、
【数５７】
2008154238.tif 000059
【０１１０】
であれば、戻って行列
【数５８】
2008154238.tif 000060
【０１１１】
を出力し、
【数５９】
2008154238.tif 000061
【０１１２】
であれば、ステップ２に戻る。
【０１１３】
入力が信頼度行列
【数６０】
2008154238.tif 000062
【０１１４】
およびコスト値
【数６１】
2008154238.tif 000063
【０１１５】
である場合（第２場合）：
入力は、信頼度行列およびコスト値
【数６２】
2008154238.tif 000064
【０１１６】
で、出力は、
【数６３】
2008154238.tif 000065
【０１１７】
を満たす最適な重複度行列
【数６４】
2008154238.tif 000066
【０１１８】
である。
【０１１９】
ステップ１において、下記のように設定する。
【数６５】
2008154238.tif 000067
【０１２０】
ステップ２において、行列
【数６６】
2008154238.tif 000068
【０１２１】
内の最大値位置
【数６７】
2008154238.tif 000069
【０１２２】
に対応する位置
【数６８】
2008154238.tif 000070
【０１２３】
を探し、位置
【数６９】
2008154238.tif 000071
【０１２４】
に対応する値を下記のように更新する。
【数７０】
2008154238.tif 000072
【０１２５】
ステップ３において、
【数７１】
2008154238.tif 000073
【０１２６】
であれば、
【数７２】
2008154238.tif 000074
【０１２７】
と設定してステップ２に戻り、
【数７３】
2008154238.tif 000075
【０１２８】
であれば、戻って行列
【数７４】
2008154238.tif 000076
【０１２９】
を出力する。
【０１３０】
第１場合においては、まず、補間点の数ｓおよび信頼度行列
【数７５】
2008154238.tif 000077
【０１３１】
を入力し、次に、
【数７６】
2008154238.tif 000078
【０１３２】
およびカウンター
【数７７】
2008154238.tif 000079
【０１３３】
に初期値を付与し、次に、行列
【数７８】
2008154238.tif 000080
【０１３４】
内の最大値位置
【数７９】
2008154238.tif 000081
【０１３５】
に対応する位置
【数８０】
2008154238.tif 000082
【０１３６】
を探し、且つ、行列
【数８１】
2008154238.tif 000083
【０１３７】
および重複度行列
【数８２】
2008154238.tif 000084
【０１３８】
の、位置
【数８３】
2008154238.tif 000085
【０１３９】
に対応する要素を更新する。次に、カウンターを１加算し、反復回数が指定の補間点の数ｓに達しているかどうかを判断し、達していなければ、続いて反復し、達していれば、反復を停止して重複度行列
【数８４】
2008154238.tif 000086
【０１４０】
を出力する。
【０１４１】
第２場合でのプロセスについては、第１場合と比べてその停止制御用パラメータのみが異なるため、そのアルゴリズムのステップの詳述を省略する。
【０１４２】
次に、Ｋｏｅｔｔｅｒなどのアルゴリズムの計算複雑性を検討する。第１場合と第２場合は同一のアルゴリズムに対応し、区別がただそれらの停止制御用パラメータのみであるため、第１場合の複雑性のみを考慮する。
【０１４３】
第１場合は、大きさ
【数８５】
2008154238.tif 000087
【０１４４】
の行列内でｓ回の最大値探索が行われる。ここでＲＳ符号に対しては
【数８６】
2008154238.tif 000088
【０１４５】
が成立する。従って、当該プロセスの複雑性は
【数８７】
2008154238.tif 000089
【０１４６】
となる。
【０１４７】
疎行列を考慮し、即ち、受信したシンボルごとに対して、当該受信した点の周囲にもっとも近い
【数８８】
2008154238.tif 000090
【０１４８】
個のパラメータ点の対応する確率のみを信頼度行列に入れると、信頼度行列の各列に
【数８９】
2008154238.tif 000091
【０１４９】
個の要素のみがあり、第１場合の計算複雑性が
【数９０】
2008154238.tif 000092
【０１５０】
となる。
【数９１】
2008154238.tif 000093
【０１５１】
を、Ｋｏｅｔｔｅｒなどのアルゴリズムの第１場合のｓ回目で生成した重複度行列とし、
【数９２】
2008154238.tif 000094
【０１５２】
の実行列に定義し、その
【数９３】
2008154238.tif 000095
【０１５３】
における要素
【数９４】
2008154238.tif 000096
【０１５４】
を満たす。
【０１５５】
Ｋｏｅｔｔｅｒなどは下記の定理を証明した。
【０１５６】
各正数
【数９５】
2008154238.tif 000097
【０１５７】
に対して、
【数９６】
2008154238.tif 000098
【０１５８】
を満たす非負整数が存在し、
逆に、各非負整数ｓに対して、上式を成立させる正実数
【数９７】
2008154238.tif 000099
【０１５９】
が存在する。
【０１６０】
上記定理に基づいて、下記のように分析する。
【０１６１】
当該定理によって、出願人は下記の推論を得ることができる（推論１および推論２）。
【０１６２】
（推論１）２つの正実数
【数９８】
2008154238.tif 000100
【０１６３】
を満たし、非負整数
【数９９】
2008154238.tif 000101
【０１６４】
がそれぞれ重複度行列
【数１００】
2008154238.tif 000102
【０１６５】
に対応するとすれば、
【数１０１】
2008154238.tif 000103
【０１６６】
が必ず成立する。
【数１０２】
2008154238.tif 000104
【０１６７】
とする。
【０１６８】
Ｋｏｅｔｔｅｒなどのアルゴリズムの第１場合に、各反復ステップは、その対応する重複度
【数１０３】
2008154238.tif 000105
【０１６９】
が１加算される唯一の１つの位置
【数１０４】
2008154238.tif 000106
【０１７０】
があるため、
【数１０５】
2008154238.tif 000107
【０１７１】
が成立する。
【数１０６】
2008154238.tif 000108
【０１７２】
に注意すれば、
【数１０７】
2008154238.tif 000109
【０１７３】
となる。すると、
【数１０８】
2008154238.tif 000110
【０１７４】
になる。
【０１７５】
（推論２）Ｋｏｅｔｔｅｒなどのアルゴリズムの第１場合の反復ステップ
【数１０９】
2008154238.tif 000111
【０１７６】
で生じた重複度行列
【数１１０】
2008154238.tif 000112
【０１７７】
に対応する
【数１１１】
2008154238.tif 000113
【０１７８】
を正数とすれば、コスト値
【数１１２】
2008154238.tif 000114
【０１７９】
がパラメータ
【数１１３】
2008154238.tif 000115
【０１８０】
に対して単調増加である。
【０１８１】
当該推論２は推論１により直接に得られることができるので、ここでその証明を省略する。
【０１８２】
したがって、ＲＳ符号の代数的な軟判定復号の重複度計算の目標値（重複度で計算する補間点の数ｓまたはコスト値
【数１１４】
2008154238.tif 000116
【０１８３】
）がパラメータ
【数１１５】
2008154238.tif 000117
【０１８４】
の単調増加関数で表されうるという結論が得られる。つまり、重複度計算は単調増加関数の目標値の解を求める問題に転化することができる。単調増加関数または単調減少関数の目標値の解を求めるには、複雑性の高い逐次反復法を採用することなく、高速に解を求めるように二分法や黄金分割法など方法を採用することができる。二分法や黄金分割法は、収束速度が速いので、その複雑性が低い。
【０１８５】
ＲＳ符号の代数的な軟判定復号の重複度計算ステップの目標値がある独立変数の単調増加関数で表されうる場合、単調増加関数
【数１１６】
2008154238.tif 000118
【０１８６】
に対して、目標値
【数１１７】
2008154238.tif 000119
【０１８７】
が与えられており、それぞれ
【数１１８】
2008154238.tif 000120
【０１８８】
を満たす２つの初期値
【数１１９】
2008154238.tif 000121
【０１８９】
を見付けることができれば、二分法や黄金分割法など種々の方法で方程式
【数１２０】
2008154238.tif 000122
【０１９０】
を解いて目標値を高速に計算することができる。
【０１９１】
本発明において、単調関数特性をＲＳ符号の代数的な軟判定復号の重複度計算に導入すると共に、適当な初期値を見付けることにより、二分法や黄金分割法など高速反復方法で重複度行列を高速に計算することができる。
【０１９２】
単調関数特性を導入したため、収束速度の速い二分法や黄金分割法を用いて、少ない反復ステップ数だけで所要の結果を得ることができる。本発明は、Ｋｏｅｔｔｅｒなどの方法の逐次探索による計算量が大きいという欠点を回避し、重複度計算の複雑性を極めて低減している。
【０１９３】
具体的に、本発明は、信頼度完全行列に対して、重複度計算に所要の複雑性はＫｏｅｔｔｅｒなどの方法の
【数１２１】
2008154238.tif 000123
【０１９４】
に低減し、信頼度疎行列に対して、所要の複雑性はＫｏｅｔｔｅｒなどの方法の
【数１２２】
2008154238.tif 000124
【０１９５】
の線形複雑度に低減する。
【０１９６】
本発明の所要する計算量は
【数１２３】
2008154238.tif 000125
【０１９７】
のオーダーにおいて低減するのみではなく、本発明はＫｏｅｔｔｅｒの方法と同じ入出力を持っているため、補間と分解ステップの複雑性の増大を招くことなく、復号器全体の復号性能を低下させることもない。
【０１９８】
次に、二分法を例として単調増加関数の目標値の高速探索を説明する。
【０１９９】
関数
【数１２４】
2008154238.tif 000126
【０２００】
が単調増加であり、且つ
【数１２５】
2008154238.tif 000127
【０２０１】
であり、目標値
【数１２６】
2008154238.tif 000128
【０２０２】
に対応する解
【数１２７】
2008154238.tif 000129
【０２０３】
が求めようとする値であると仮定する。まず、
【数１２８】
2008154238.tif 000130
【０２０４】
に対応する関数値を計算する。
【数１２９】
2008154238.tif 000131
【０２０５】
であるため、
【数１３０】
2008154238.tif 000132
【０２０６】
を新しい上限とし、
【数１３１】
2008154238.tif 000133
【０２０７】
に対応する関数値を計算する。
【数１３２】
2008154238.tif 000134
【０２０８】
であるため、
【数１３３】
2008154238.tif 000135
【０２０９】
を新しい下限とし、当該プロセスを繰り返して目標値を高速に得ることができる。
【０２１０】
二分法や黄金分割法を用いて重複度行列を計算するために、初期値を設定する必要もある。関数
【数１３４】
2008154238.tif 000136
【０２１１】
の増加関数であり、目標値
【数１３５】
2008154238.tif 000137
【０２１２】
が与えられたとし、方程式
【数１３６】
2008154238.tif 000138
【０２１３】
を満たす
【数１３７】
2008154238.tif 000139
【０２１４】
を求める。それぞれ
【数１３８】
2008154238.tif 000140
【０２１５】
を満たす２つの初期値
【数１３９】
2008154238.tif 000141
【０２１６】
が予め与えられることができれば、直ちに二分法や黄金分割法を用いて目標値の高速探索ができる。もちろん、初期値が設定されていない場合、単調増加関数または単調減少関数に対して、二分法や黄金分割法を用いて目標値を探索することもできるが、アルゴリズムの第１ステップで初期値を決定することが必要となるため、その複雑性が初期値設定済みの方法よりやや高い。
【０２１７】
重複度計算の初期値の設定について、下記の推論（推論３および推論４）がある。
【０２１８】
（推論３）信頼度行列
【数１４０】
2008154238.tif 000142
【０２１９】
と正整数ｓがあり、
【数１４１】
2008154238.tif 000143
【０２２０】
とが設定されるとする。非負整数
【数１４２】
2008154238.tif 000144
【０２２１】
がそれぞれ重複度行列
【数１４３】
2008154238.tif 000145
【０２２２】
に対応すれば、
【数１４４】
2008154238.tif 000146
【０２２３】
となる。
【数１４５】
2008154238.tif 000147
【０２２４】
となる。
【０２２５】
（推論４）信頼度行列
【数１４６】
2008154238.tif 000148
【０２２６】
と正実数
【数１４７】
2008154238.tif 000149
【０２２７】
があり、
【数１４８】
2008154238.tif 000150
【０２２８】
とが設定されるとする。
【数１４９】
2008154238.tif 000151
【０２２９】
と定義すれば、
不等式
【数１５０】
2008154238.tif 000152
【０２３０】
が成立する。
【数１５１】
2008154238.tif 000153
【０２３１】
の根の１つとなることを容易に検証できるため、
【数１５２】
2008154238.tif 000154
【０２３２】
即ち、左半部の不等式が成立する。
【０２３３】
次に、右半部の不等式を証明する。
【０２３４】
各正数
【数１５３】
2008154238.tif 000155
【０２３５】
に対して、
【数１５４】
2008154238.tif 000156
【０２３６】
を満たす非負整数ｓが存在し、逆に、各非負整数ｓに対して、上式を成立させる正実数
【数１５５】
2008154238.tif 000157
【０２３７】
が存在するという定理から、
【数１５６】
2008154238.tif 000158
【０２３８】
がわかる。
【０２３９】
ここで、
【数１５７】
2008154238.tif 000159
【０２４０】
と記すると、
【数１５８】
2008154238.tif 000160
【０２４１】
となる。そうすると、
【数１５９】
2008154238.tif 000161
【０２４２】
を得ることができる。
【０２４３】
当該式の最後の等式の第１項の値がちょうど
【数１６０】
2008154238.tif 000162
【０２４４】
であり、第３項が非負数である。
【０２４５】
第２項を単独に記すると、
【数１６１】
2008154238.tif 000163
【０２４６】
当該式を前の式と連立して
【数１６２】
2008154238.tif 000164
【０２４７】
を得る。
【０２４８】
推論３および推論４において、それぞれ目標値が補間点の数ｓおよびコスト値
【数１６３】
2008154238.tif 000165
【０２４９】
である際の初期値が与えられている。この２つの推論により、上記の式に従って初期値を設定すれば、求められた目標値
【数１６４】
2008154238.tif 000166
【０２５０】
が必ず
【数１６５】
2008154238.tif 000167
【０２５１】
との間にあることを説明した。
【０２５２】
上記詳しい分析から下記のことがわかる。
【０２５３】
ＲＳ符号の代数的な軟判定復号の重複度計算の目標値（重複度で計算する補間点の数ｓまたはコスト値
【数１６６】
2008154238.tif 000168
【０２５４】
）がパラメータ
【数１６７】
2008154238.tif 000169
【０２５５】
の単調増加関数または単調減少関数で表されうることが分かる。また、初期値の上限と下限を設定し、目標値ｓまたは
【数１６８】
2008154238.tif 000170
【０２５６】
に対応する
【数１６９】
2008154238.tif 000171
【０２５７】
が当該下限と上限との間にあるようにしてよい。すると、例えば二分法や黄金分割法を用いて重複度行列の高速計算を実現することが可能になる。
【０２５８】
上記のように、図１は本発明のＲＳ復号化における重複度の計算方法の例を示すフローチャートである。図１に示すように、当該方法は、下記のステップを含む。
【０２５９】
ステップ１０１において、信頼度行列と重数計算の目標値とを入力し、前記目標値を１つの独立変数の単調関数で表す。
【０２６０】
ここで、単調関数は単調増加関数であってもよく、単調減少関数であってもよい。また、信頼度行列は信頼度完全行列であってもよく、信頼度疎行列であってもよい。
【０２６１】
ステップ１０２において、目標値が当該独立変数の単調関数である特性を利用して、当該独立変数に対して高速反復を行って目標値に対応する独立変数値を計算し、前記信頼度行列と計算した前記独立変数値とに基づいて重複度行列を計算する。
【０２６２】
ここで、二分法のアルゴリズムや黄金分割法のアルゴリズムなど種々の高速反復アルゴリズムを用いて独立変数に対して高速反復を行うことができる。
【０２６３】
目標値が重複度計算の補間点の数である場合、高速反復は、具体的に、まず、独立変数に対して、目標値に対応する独立変数値より大きい上限値と、目標値に対応する独立変数値より小さい下限値とを取り、次に、上限値と下限値との間の１点の目的関数値を計算し、当該点の目的関数値が前記補間点の数より小さいかどうかを判断し、小さい場合、当該点の独立変数値で下限値を更新し、小さくない場合、当該点の独立変数値で上限値を更新し、次に、上限値と下限値との差が予め設定された閾値より小さいかどうかを判断し、小さい場合、前記高速反復を終了し、小さくない場合、続いて反復を行うことを含む。
【０２６４】
好ましくは、前記下限値が
【数１７０】
2008154238.tif 000172
【０２６５】
であり、前記上限値が
【数１７１】
2008154238.tif 000173
【０２６６】
であり、
【数１７２】
2008154238.tif 000174
【０２６７】
ここで、ＮはＲＳ符号の符号長であり、ｓは前記補間点の数であり、
【数１７３】
2008154238.tif 000175
【０２６８】
は変調次数である。
【０２６９】
目標値がコスト値である場合、高速反復は、具体的に、まず、独立変数に対して、目標値に対応する独立変数値より大きい上限値と、目標値に対応する独立変数値より小さい下限値とを取り、次に、上限値と下限値との間の１点の目的関数値を計算し、当該点の目的関数値が前記コスト値より小さいかどうかを判断し、小さい場合、当該点の独立変数値で下限値を更新し、小さくない場合、当該点の独立変数値で上限値を更新し、次に、上限値と下限値との差が予め設定された閾値より小さいかどうかを判断し、小さい場合、前記高速反復を終了し、小さくない場合、戻って続いて反復することを含む。
【０２７０】
好ましくは、前記下限値が
【数１７４】
2008154238.tif 000176
【０２７１】
であり、前記上限値が
【数１７５】
2008154238.tif 000177
【０２７２】
ここで、ＮはＲＳ符号の符号長であり、Ｃは前記コスト値であり、
【数１７６】
2008154238.tif 000178
【０２７３】
は変調次数であり、
【数１７７】
2008154238.tif 000179
【０２７４】
は信頼度行列のｉ行目ｊ列目の要素である。
【０２７５】
以下、本発明のアルゴリズムの計算複雑性を考察する。本発明の各反復ステップは
【数１７８】
2008154238.tif 000180
【０２７６】
回の加算操作、
【数１７９】
2008154238.tif 000181
【０２７７】
回の乗算操作および
【数１８０】
2008154238.tif 000182
【０２７８】
回の整数丸め（ｒｏｕｎｄ）操作が必要である。二分法や黄金分割法は少ない反復ステップだけで計算を完成できる（通常は、２０回より低い反復で要求が既に満たされる。コンピュータの有限語長効果（Ｆｉｎｉｔｅ  Ｗｏｒｄ  Ｌｅｎｇｔｈ  Ｅｆｆｅｃｔ）のため、より多くの反復回数は計算量を無駄に増加するだけで、実際の価値を有しない。）このように、本発明のアルゴリズムの計算複雑性は
【数１８１】
2008154238.tif 000183
【０２７９】
となる。
【０２８０】
疎行列を考慮し、即ち、受信したシンボルごとに対して、当該受信した点の周囲にもっとも近い
【数１８２】
2008154238.tif 000184
【０２８１】
個のパラメータ点の対応する確率のみを信頼度行列に入れると、信頼度行列の各列に
【数１８３】
2008154238.tif 000185
【０２８２】
個の要素のみがあり、本発明のアルゴリズムの計算複雑性は
【数１８４】
2008154238.tif 000186
【０２８３】
となる。
【０２８４】
上記は本発明のアルゴリズムを詳しく説明した。次に、上記アルゴリズムを参照しながら、本発明の好ましい実施例について詳しく説明する。
【０２８５】
入力が、信頼度行列
【数１８５】
2008154238.tif 000187
【０２８６】
、および重複度で計算する補間点の数ｓである第１場合に対して、以下、本発明の第１実施例を具体的に説明する。
【０２８７】
ここで、
入力は、信頼度行列
【数１８６】
2008154238.tif 000188
【０２８８】
、および重複度で計算する補間点の数ｓである。
【０２８９】
出力は、
【数１８７】
2008154238.tif 000189
【０２９０】
を満たす最適な重複度行列
【数１８８】
2008154238.tif 000190
【０２９１】
である。
【０２９２】
ステップ１において、下記のように設定する。
【数１８９】
2008154238.tif 000191
【０２９３】
ステップ２において、下記のように設定し、
【数１９０】
2008154238.tif 000192
【０２９４】
ステップ３において、
【数１９１】
2008154238.tif 000193
【０２９５】
図２は本発明の第１実施例によるＲＳ復号化における重複度の計算方法のフローチャートである。図２に示すように、当該方法は、下記のステップを含む。
【０２９６】
ステップ２０１において、補間点の数ｓ、信頼度行列
【数１９２】
2008154238.tif 000194
【０２９７】
、および予め設定されたパラメータ
【数１９３】
2008154238.tif 000195
【０２９８】
を入力する。
【０２９９】
ここで、
【数１９４】
2008154238.tif 000196
【０３００】
は予め設定された２つの正数である。パラメータ
【数１９５】
2008154238.tif 000197
【０３０１】
を満たすようにしてよく、二分法や黄金分割法に対応して、例えば、０．５や０．６１８に設定されてよい。
【数１９６】
2008154238.tif 000198
【０３０２】
は小さい正数であり、例えば、０．０００１であってよい。反復中で
【数１９７】
2008154238.tif 000199
【０３０３】
までの線分長さが
【数１９８】
2008154238.tif 000200
【０３０４】
以下となる場合、当該線分が既に１点に収束したものとする。従って、反復を停止してよい。
【０３０５】
ステップ２０２において、反復初期値を下記のように設定する。
【数１９９】
2008154238.tif 000201
【０３０６】
ステップ２０３において、
【数２００】
2008154238.tif 000202
【０３０７】
を計算する。
【０３０８】
ステップ２０４において、
【数２０１】
2008154238.tif 000203
【０３０９】
に対応する目的関数値
【数２０２】
2008154238.tif 000204
【０３１０】
を計算する。
【０３１１】
ステップ２０５において、当該目的関数値と入力された目標値ｓとを比較して、関数値が目標値より小さい場合、ステップ２０６において、
【数２０３】
2008154238.tif 000205
【０３１２】
の値を更新し、関数値が目標値より小さくない場合、ステップ２０７において、
【数２０４】
2008154238.tif 000206
【０３１３】
の値を更新する。
【０３１４】
ステップ２０８において、
【数２０５】
2008154238.tif 000207
【０３１５】
の値が予め設定された閾値
【数２０６】
2008154238.tif 000208
【０３１６】
より小さいかどうかをチェックする。
【数２０７】
2008154238.tif 000209
【０３１７】
より小さい場合、反復停止の条件が満たされたことを表し、ステップ２０９において、呼び出し元に戻って重複度行列
【数２０８】
2008154238.tif 000210
【０３１８】
を出力する。
【数２０９】
2008154238.tif 000211
【０３１９】
より小さくない場合、ステップ２０３に戻り、続いて反復する。
【０３２０】
入力が信頼度行列
【数２１０】
2008154238.tif 000212
【０３２１】
およびコスト値
【数２１１】
2008154238.tif 000213
【０３２２】
である第２場合に対して、以下、本発明の第２実施例を具体的に説明する。
【０３２３】
入力は、信頼度行列
【数２１２】
2008154238.tif 000214
【０３２４】
およびコスト値
【数２１３】
2008154238.tif 000215
【０３２５】
である。
【０３２６】
出力は、
【数２１４】
2008154238.tif 000216
【０３２７】
を満たす最適な重複度行列
【数２１５】
2008154238.tif 000217
【０３２８】
である。
【０３２９】
ステップ１において、下記のように設定する。
【数２１６】
2008154238.tif 000218
【０３３０】
ステップ２において、下記のように設定し、
【数２１７】
2008154238.tif 000219
【０３３１】
ステップ３において、
【数２１８】
2008154238.tif 000220
【０３３２】
である場合、ステップ２に戻る。
【０３３３】
図３は本発明の第２実施例によるＲＳ復号化における重複度の計算方法のフローチャートである。図３に示すように、当該方法は、下記のステップを含む。
【０３３４】
ステップ３０１において、コスト値
【数２１９】
2008154238.tif 000221
【０３３５】
、信頼度行列
【数２２０】
2008154238.tif 000222
【０３３６】
、および予め設定されたパラメータ
【数２２１】
2008154238.tif 000223
【０３３７】
を入力する。
【０３３８】
ここで、
【数２２２】
2008154238.tif 000224
【０３３９】
は予め設定された２つの正数である。パラメータ
【数２２３】
2008154238.tif 000225
【０３４０】
のように、二分法や黄金分割法に対応して、例えば、０．５や０．６１８に設定されてよい。
【数２２４】
2008154238.tif 000226
【０３４１】
は小さい正数であり、例えば、０．０００１であってよい。反復中で
【数２２５】
2008154238.tif 000227
【０３４２】
までの線分長さが
【数２２６】
2008154238.tif 000228
【０３４３】
以下となる場合、当該線分が１点に収束したものとする。従って、反復を停止してよい。
【０３４４】
ステップ３０２において、反復初期値を下記のように設定する。
【数２２７】
2008154238.tif 000229
【０３４５】
ステップ３０３において、
【数２２８】
2008154238.tif 000230
【０３４６】
を計算し、次に、ステップ３０４において、
【数２２９】
2008154238.tif 000231
【０３４７】
に対応する目的関数値
【数２３０】
2008154238.tif 000232
【０３４８】
を計算する。
【０３４９】
ステップ３０５において、当該目的関数値と入力された目標値
【数２３１】
2008154238.tif 000233
【０３５０】
とを比較して、関数値が目標値より小さい場合、ステップ３０６において、
【数２３２】
2008154238.tif 000234
【０３５１】
の値を更新し、関数値が目標値より小さくない場合、ステップ３０７において、
【数２３３】
2008154238.tif 000235
【０３５２】
の値を更新する。
【０３５３】
ステップ３０８において、
【数２３４】
2008154238.tif 000236
【０３５４】
の値が予め設定された閾値
【数２３５】
2008154238.tif 000237
【０３５５】
より小さいかどうかをチェックする。
【数２３６】
2008154238.tif 000238
【０３５６】
より小さい場合、反復停止の条件が満たされたことを表し、ステップ３０９において、呼び出し元に戻って重複度行列
【数２３７】
2008154238.tif 000239
【０３５７】
を出力する。
【数２３８】
2008154238.tif 000240
【０３５８】
より小さくない場合、ステップ３０３に戻り、続いて反復する。
【０３５９】
推論３および推論４において、ぞれぞれ目標値がｓおよび
【数２３９】
2008154238.tif 000241
【０３６０】
である際の初期値が与えられている。この２つの推論により、求められた目標
【数２４０】
2008154238.tif 000242
【０３６１】
にあることを説明した。図４は本発明の第１実施例における上限値と下限値の選択の例を示す図である。図５は本発明の第２実施例における上限値と下限値の選択の例を示す図である。
【０３６２】
また、上記アルゴリズムおよび処理フローに基づいて、本発明はＲＳ復号化における重複度の計算装置を提供している。図６は本発明によるＲＳ復号化における重複度の計算装置の例を示す構成図である。図６に示すように、当該装置６００は、
信頼度行列と重複度計算の目標値とを受信する入力モジュール６０１と、
前記目標値を１つの独立変数の単調関数で表す目標値表示モジュール６０２と、
目標値が独立変数の単調関数である特性を利用して、当該独立変数に対して高速反復を行って目標値に対応する独立変数値を計算し、前記信頼度行列と計算した前記独立変数値とに基づいて重複度行列を計算する重複度行列計算モジュール６０３と、を含む。
【０３６３】
ここで、目標値表示モジュール６０２は、前記目標値を１つの独立変数の単調増加関数で表し、または前記目標値を１つの独立変数の単調減少関数で表すように構成されてよい。入力モジュール６０１によって受信された信頼度行列は信頼度完全行列であってもよいし、信頼度疎行列であってもよい。
【０３６４】
好ましくは、重複度行列計算モジュール６０３が、二分法のアルゴリズムや黄金分割法のアルゴリズムにより前記独立変数に対して高速反復を行うように構成される。
【０３６５】
また、上記ＲＳ復号化における重複度の計算装置に基づいて、本発明はＲＳ符号の復号器を提供している。図７は本発明によるＲＳ復号器の例を示す構成図である。図７に示すように、当該装置７００は、
入力された信頼度行列と重複度計算の目標値とに基づいて重複度行列を計算し、ここで、目標値を１つの独立変数の単調関数で表し、目標値が独立変数の単調関数である特性を利用して、当該独立変数に対して高速反復を行って目標値に対応する独立変数値を計算し、計算した前記独立変数値と前記信頼度行列とに基づいて重複度行列を計算する重複度の計算装置７０１と、
前記計算された重複度行列に基づいて二変数多項式の係数を計算して、二変数多項式を得る二変数多項式補間装置７０２と、
得られた二変数多項式を分解してリスト復号の候補コードワードを得る二変数多項式分解装置７０３と、を含む。
【０３６６】
具体的に、符号長がＮ、情報長がＫであるＲＳ符号の復号を考慮し、
二変数多項式補間装置７０２は、補間点と各補間点に対応する重複度とが得られた後、係数が有限体ＧＦ（ｑ）に定義される若干の一次方程式を並べる。得られた連立一次方程式の未知数が二変数多項式Ｑ（ｘ，ｙ）の係数に対応するため、この連立一次方程式を解いて二元多項式Ｑ（ｘ，ｙ）の係数を得ることができる。Ｑ（ｘ，ｙ）の係数を求める演算がＱ（ｘ，ｙ）補間と呼ばれる。
【０３６７】
二変数多項式分解装置７０３は、二変数多項式Ｑ（ｘ，ｙ）が得られた後、Ｑ（ｘ，ｙ）の因子ｙ−ｆ（ｘ）を求める。ここで、ｆ（ｘ）は、ＧＦ（ｑ）に定義されるＫ−１次以下の多項式である。分解されたＫ−１次以下の各多項式はリスト復号の候補コードワード多項式であり、並べられたあらゆるコードワードと受信した系列とを比較して最適な復号語を得ることができる。
【０３６８】
また、本発明はＲＳ符号の復号方法を提供している。図８は本発明によるＲＳ復号化方法の例を示すフローチャートである。図８に示すように、当該方法は、
信頼度行列と重複度計算の目標値とを入力し、前記目標値を１つの独立変数の単調関数で表し、目標値が当該独立変数の単調関数である特性を利用して、当該独立変数に対して高速反復を行って目標値に対応する独立変数値を計算し、前記信頼度行列と計算した前記独立変数値とに基づいて重複度行列を計算するステップ８０１と、
前記計算された重複度行列に基づいて二変数多項式の係数を計算して二変数多項式を得、かつ、得られた二変数多項式を分解してリスト復号の候補コードワードを得るステップ８０２と、を含む。
【０３６９】
ここで、
目標値が重複度計算の補間点の数である場合、前記高速反復は、具体的に、下記のことを含む。
【０３７０】
まず、独立変数に対して、目標値に対応する独立変数値より大きい上限値と、目標値に対応する独立変数値より小さい下限値とを取り、次に、上限値と下限値との間の１点の目的関数値を計算し、当該点の目的関数値が前記補間点の数より小さいかどうかを判断し、小さい場合、当該点の独立変数値で下限値を更新し、小さくない場合、当該点の独立変数値で上限値を更新し、次に、上限値と下限値との差が予め設定された閾値より小さいかどうかを判断し、小さい場合、前記高速反復を終了し、小さくない場合、上限値と下限値との間の点の目的関数値の計算に戻り、続いて反復する。
【０３７１】
目標値がコスト値である場合、前記高速反復は、具体的に、下記のことを含む。
【０３７２】
まず、独立変数に対して、目標値に対応する独立変数値より大きい上限値と、目標値に対応する独立変数値より小さい下限値とを取り、次に、上限値と下限値との間の１点の目的関数値を計算し、当該点の目的関数値が前記コスト値より小さいかどうかを判断し、小さい場合、当該点の独立変数値で下限値を更新し、小さくない場合、当該点の独立変数値で上限値を更新し、次に、上限値と下限値との差が予め設定された閾値より小さいかどうかを判断し、小さい場合、前記高速反復を終了し、小さくない場合、上限値と下限値との間の点の目的関数値の計算に戻り、続いて反復する。
【０３７３】
次に、本発明の性能例を説明する。
【０３７４】
本方法による重複度計算の有効性を検証するために、Ｃ＋＋でプログラミングしてペンティアム（Ｐｅｎｔｉｕｍ）（登録商標）４  Ｗｉｎｄｏｗｓ（登録商標）  ＸＰプラットフォームでアルゴリズムの計算速度に対してシミュレーションを行うようにしてよい。アルゴリズムの実行結果と機器との相関性を排除するために、Ｋｏｅｔｔｅｒなどに提出された方法と本発明との所要する実行時間の比を考察する。
【０３７５】
実行時間を正確に計算するために、テスト対象アルゴリズムを複数回コールしてその平均時間を求めるようにしてよい。シミュレーションにおいて、コール回数の設定は、得られた実行時間が９９％の信頼度（ｃｏｎｆｉｄｅｎｃｅ  ｌｅｖｅｌ）を保証することを原則とする。ＲＳ符号を２つ選択して、１つは有限体ＧＦ（２５６）に定義される（２５５，１４４，１１２）であり、もう１つは有限体ＧＦ（６４）に定義される（６３，３２，３２）である。当該２つの符号を用いてシミュレーションを行い、その実行速度を観察する。加法的白色ガウス雑音（ＡＷＧＮ：Ａｄｄｉｔｉｖｅ  Ｗｈｉｔｅ  Ｇａｕｓｓｉａｎ  Ｎｏｉｓｅ）チャネルを用いてシミュレーションを行い、信号対雑音比（Ｅｂ／Ｎ０）が１０ｄＢである際の結果を観察する。受信したシンボルごとに対して、当該受信した点の周囲にもっとも近い
【数２４１】
2008154238.tif 000243
【０３７６】
個のパラメータ点の対応する確率を信頼度行列に入れる。
【０３７７】
第１実施例と第２実施例が同一のアルゴリズムの異なる目標値に対応するため、改良された第２実施例と従来技術の第２場合との実行時間のみを比較する。
【０３７８】
リスト復号に対して、そのコードワード数が
【数２４２】
2008154238.tif 000244
【０３７９】
を超えないとすると、Ｋｏｅｔｔｅｒなどの定義に従って、
【数２４３】
2008154238.tif 000245
【０３８０】
を情報長とし、目標値
【数２４４】
2008154238.tif 000246
【０３８１】
のように定義されてよい。パラメータ
【数２４５】
2008154238.tif 000247
【０３８２】
と設定する。若干のパラメータペア
【数２４６】
2008154238.tif 000248
【０３８３】
を選択してシミュレーションを行う。シミュレーションの結果は表１に示す通りである。本発明の方法は従来のＫｏｅｔｔｅｒなどのアルゴリズムと同じ入出力を持っている。
【０３８４】
表１は若干のＲＳ符号の実行時間の結果であり、列Ｓ−ＲはＫｏｅｔｔｅｒなどのアルゴリズムと本発明との重複度計算の時間比を表す。
【表１】
2008154238.tif 000249
【０３８５】
表１からわかるように、本発明の方法の実行速度は従来のアルゴリズムより遥かに高い。本発明は、ＲＳ符号の代数的な軟判定復号性能が変わらないことを保証すると共に、実現の複雑性を低減している。
【０３８６】
上記のように、ＲＳ符号の代数的な軟判定復号の重複度計算ステップの目標値は、ある独立変数の単調増加関数または単調減少関数で表されることができる。
【０３８７】
本発明は増加関数特性をＲＳ符号の代数的な軟判定復号の重複度計算に導入すると共に、適当な初期値を見付けるだけに、二分法や黄金分割法を採用して重複度行列を高速に計算することができる。増加関数特性を導入したため、収束速度の速い二分法や黄金分割法を用いて、少ない反復ステップ数だけで所要の結果を得ることができるようになる。これにより、Ｋｏｅｔｔｅｒなど方法の逐次探索による計算量が大きいという欠点を回避し、重複度計算の複雑性を極めて低減している。
【０３８８】
上記は、本発明の好ましい実施例にすぎず、本発明の保護範囲を限定するものではない。本発明の精神と原則で行われる種々の修正、均等切替、改良などは全て本発明の保護範囲に含まれるべきである。
【図面の簡単な説明】
【０３８９】
【図１】本発明のＲＳ復号化における重複度の計算方法の例を示すフローチャートである。
【図２】本発明の第１実施例によるＲＳ復号化における重複度の計算方法のフローチャートである。
【図３】本発明の第２実施例によるＲＳ復号化における重複度の計算方法のフローチャートである。
【図４】本発明の第１実施例における上限値と下限値の選択の例を示す図である。
【図５】本発明の第２実施例における上限値と下限値の選択の例を示す図である。
【図６】本発明によるＲＳ復号化における重複度の計算装置の例を示す構成図である。
【図７】本発明によるＲＳ復号器の例を示す構成図である。
【図８】本発明によるＲＳ復号化方法の例を示すフローチャートである。
【符号の説明】
【０３９０】
６００…重複度の計算装置、６０１…入力モジュール、６０２…目標値表示モジュール、６０３…重複度行列計算モジュール、７００…ＲＳ符号の復号器、７０１…重複度の計算装置、７０２…二変数多項式補間装置、７０３…二変数多項式分解装置
【図１】
2008154238.tif 000259
【図２】
2008154238.tif 000260
【図３】
2008154238.tif 000261
【図４】
2008154238.tif 000262
【図５】
2008154238.tif 000263
【図６】
2008154238.tif 000264
【図７】
2008154238.tif 000265
【図８】
2008154238.tif 000266