(57)【特許請求の範囲】
【請求項１】
環Ｒ上線形符号の復号装置であって、
複数の記憶媒体と、
処理部と、を有し、
上記処理部は、
各シンボルの信頼性を高める繰り返し復号の過程において前回の全シンボルの信頼性の一部を各シンボルの信頼性更新に用い、さらに保持する信頼性情報の更新に用いられる部分と用いられない部分を２つの別な記憶媒体に保持する
復号装置。
【請求項２】
上記処理部は、
上記繰り返し復号として信頼性伝播（Belief Propagation：BP）を用い、さらに信頼性更新の際にＵＭＰ(Uniformly Most Powerful)復号法による近似を用いる
請求項１記載の復号装置。
【請求項３】
上記処理部は、
受信語の信頼性を求め、求められた信頼性を元にパリティ検査行列の対角化優先順位を決め、で求められた優先順位を元にパリティ検査行列を対角化し、求められたパリティ検査行列を用いて信頼性伝播（ＢＰ）を１回、もしくは複数回行い受信語の信頼性を更新する
請求項２記載の復号装置。
【請求項４】
上記複数の記憶媒体にはレジスタと半導体メモリを含み、
上記処理部は、
信頼性更新に用いられる部分を上記レジスタに保持し、用いられない部分を上記半導体メモリに保持する
請求項２記載の復号装置。
【請求項５】
上記複数の記憶媒体にはレジスタと半導体メモリを含み、
上記処理部は、
信頼性更新に用いられる部分を上記レジスタに保持し、用いられない部分を上記半導体メモリに保持する
請求項３記載の復号装置。
【請求項６】
線形符号として有限体上代数幾何符号もしくはその同型を用いる
請求項５記載の復号装置。
【請求項７】
代数幾何符号としてリードソロモン（Reed-Solomon）もしくはＢＣＨ符号、それらの同型を用い、さらに複数回の更新により得られた信頼性を入力受信語として後段で限界距離復号を行う
請求項６記載の復号装置。
【請求項８】
代数幾何符号としてリードソロモン（Reed-Solomon）もしくはＢＣＨ符号、それらの同型を用い、複数回の更新により得られた信頼性を入力受信語として所定のアルゴリズムによる硬判定リスト復号を行う
請求項６記載の復号装置。
【請求項９】
代数幾何符号としてリードソロモン（Reed-Solomon）もしくはＢＣＨ符号、それらの同型を用い、複数回の更新により得られた信頼性を入力受信語として所定のアルゴリズムによる重複度設定、および軟判定リスト復号を行う
請求項６記載の復号装置。
【請求項１０】
環Ｒ上線形符号の復号方法であって、
各シンボルの信頼性を高める繰り返し復号の過程において前回の全シンボルの信頼性の一部を各シンボルの信頼性更新に用い、さらに保持する信頼性情報の更新に用いられる部分と用いられない部分を２つの別な記憶媒体に保持する
復号方法。
【請求項１１】
上記繰り返し復号として信頼性伝播（Belief Propagation：BP）を用い、さらに信頼性更新の際にＵＭＰ(Uniformly Most Powerful)復号法による近似を用いる
請求項１０記載の復号方法。
【請求項１２】
受信語の信頼性を求め、求められた信頼性を元にパリティ検査行列の対角化優先順位を決め、で求められた優先順位を元にパリティ検査行列を対角化し、求められたパリティ検査行列を用いて信頼性伝播（ＢＰ）を１回、もしくは複数回行い受信語の信頼性を更新する
請求項１１記載の復号方法。
【請求項１３】
信頼性更新に用いられる部分をレジスタに保持し、用いられない部分を半導体メモリに保持する
請求項１１記載の復号方法。
【請求項１４】
信頼性更新に用いられる部分をレジスタに保持し、用いられない部分を半導体メモリに保持する
請求項１２記載の復号方法。
【請求項１５】
ＲＳまたはＢＣＨ符号化器および畳み込み符号化器を連接した装置から送信された信号を受信する受信装置であって、
請求項７,８,または９における信頼性更新、および復号方法を用いた復号装置を有する  受信装置。
【請求項１６】
ＲＳまたはＢＣＨ符号化器および畳み込み符号化器を連接した装置から送信された信号を受信する受信装置であって、
請求項７,８,または９における信頼性更新、および復号方法を用いた繰り返し復号装置を有する
受信装置。
【請求項１７】
ＲＳまたはＢＣＨ符号を用いてｎ次元積符号化された信号の記憶媒体再生装置であって、
請求項７,８,または９における信頼性更新、および復号方法を用いた復号装置を有する  記憶媒体再生装置。
【請求項１８】
ＲＳまたはＢＣＨ符号を用いてｎ次元積符号化された信号の記憶媒体再生装置であって、
請求項７,８,または９における信頼性更新、および復号方法を用いた繰り返し復号装置を有する
記憶媒体再生装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、たとえば代数的手法を用いた誤り訂正符号技術を実現するための回路およびプログラム記憶媒体に関して適用される復号装置、復号方法、受信装置、および記憶媒体再生装置に関するものである。
【背景技術】
【０００２】
代数幾何符号、たとえばリードソロモン（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ）符号やその部分体部分符号としてのＢＣＨ符号には、その代数的性質を利用した、性能・計算コスト共に良い復号法が知られている。
【０００３】
たとえば、符号長ｎ、情報長ｋ、定義体ＧＦ（ｑ）（ｑ＝ｐｍ，ｐ：素数）、最小距離ｄ＝ｎ−ｋのＲｅｅｄ−Ｓｏｌｏｍｏｎ符号をＲＳ（ｎ，ｋ）とすると、硬判定受信語をハミング（Ｈａｍｍｉｎｇ）距離が最小の符号語に復号する最小距離復号（通常復号）はｔ＜ｄ／２を満たすｔ個の誤りシンボルの訂正を保証するものとして良く知られている。
【０００４】
また、グルスワミ−スーダン（Ｇｕｒｕｓｗａｍｉ−Ｓｕｄａｎ）によるリスト復号（以下Ｇ−Ｓリスト復号）は、ｔ＜√ｎｋを満たすｔ個の誤りシンボルの訂正を保証している（非特許文献１参照）。
【０００５】
Ｇｕｒｕｓｗａｍｉ−Ｓｕｄａｎのリスト復号の拡張版として軟判定受信語を用いたコータ−バルディ（Ｋｏｅｔｔｅｒ−Ｖａｒｄｙ）によるリスト復号（以下Ｋ−Ｖリスト復号）は、Ｇｕｒｕｓｗａｍｉ−Ｓｕｄａｎ同様に（１）受信情報から各シンボルの信頼性を算出、（２）信頼性から２変数多項式補間条件の抽出、（３）２変数多項式の補間、（４）補間多項式の因数分解を行い復号語リスト作成、の４つの手順により構成され、硬判定復号時に比べてより高い性能を持つことが知られている（非特許文献２参照）。
【０００６】
また、リエンコード（Ｒｅ−ｅｎｃｏｄｅ）により、その計算コストも現実的な範囲まで削減できることが知られている（非特許文献３参照）。
【０００７】
一方、線形符号としては、信頼性伝播（ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を用いた繰り返し復号により限界性能に近い高性能を得られる低密度パリティ検査符号（Ｌｏｗ  ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ−ｃｈｅｃｋ  ｃｏｄｅ，ＬＤＰＣ符号）が昨今注目されている（非特許文献４参照）。
【０００８】
ＬＤＰＣ符号に用いられる信頼性伝播（ＢＰ）は、一般に低密度なパリティ検査行列を持つ線形符号にしか有効でないことが理論的に知られており、また、Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号やＢＣＨ符号のパリティ検査行列を低密度化することはＮＰ−ｈａｒｄであることが知られている（非特許文献５参照）。
【０００９】
よって、Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号やＢＣＨ符号に信頼性伝播（ＢＰ）を適用することは困難であるとされてきた。
【００１０】
しかし、２００４年、受信語の信頼性に応じて対角化を行ったパリティ検査行列を用いてＲｅｅｄ−Ｓｏｌｏｍｏｎ符号やＢＣＨ符号、その他低密度でないパリティ検査行列を持つ線形符号への信頼性伝播（ＢＰ）の適用が効果的であることがナラヤナン(Ｎａｒａｙａｎａｎ)等によって紹介された（非特許文献６参照）。
【００１１】
この手法は、適応的信頼性伝播（ＡＢＰ：Ａｄａｐｔｉｖｅ  Ｂｅｌｉｅｆ  Ｐｒｏｐａｇａｔｉｏｎ）復号と呼ばれる。以下、このＡＢＰ復号法について説明する。
【００１２】
たとえば、符号長ｎ＝６、情報長ｋ＝３、符号化率ｒ＝１／２の符号で、以下の３×６行列Ｈをパリティ検査行列として持つような線形符号Ｃを考える。
【００１３】
【数１】
0004412401.tif 000002
【００１４】
符号空間Ｃは、次のように表される。
【００１５】
【数２】
0004412401.tif 000003
【００１６】
ある符号語があるチャネル、たとえばＢＰＳＫ変調＋ＡＷＧＮチャネル（Ａｄｄｉｔｉｖｅ  Ｗｈｉｔｅ  Ｇａｕｓｓｉａｎ  Ｎｏｉｓｅチャネル）を通った後、次のような受信語ｒとして受信機が受け取ったとする。
【００１７】
【数３】
0004412401.tif 000004
【００１８】
このとき、受信値の各絶対値の大きさは受信語の信頼性の高さを表す。つまり、信頼性の低い順に番号をつけると以下のようになる。
【００１９】
【数４】
0004412401.tif 000005
【００２０】
次に、信頼性の低いシンボルに対応する列より順にパリティ検査行列Ｈの対角化を行う。この例においては、信頼性の低いシンボルに対応する列は順に第３列、第５列、第１列、第４または第６列、第２列となるので、その優先順位に従ってＨの対角化を行う。
【００２１】
【数５】
0004412401.tif 000006
【００２２】
【数６】
0004412401.tif 000007
【００２３】
【数７】
0004412401.tif 000008
【００２４】
対角化を試みた列がそれ以前に対角化した列と線形従属であった場合は、その列はそのまま残し、次の順位の列で対角化を試みる。
このようにして行列Ｈのランク分対角化が行われた結果得られる新たなパリティ検査行列Ｈｎｅｗを用いて、信頼性伝播（ＢＰ）による信頼性の更新を行う。
【００２５】
図１はパリティ検査行列Ｈｎｅｗに対応するタナーグラフである。
信頼性伝播（ＢＰ）はタナーグラフのエッジに沿ってメッセージ、つまりＬＬＲ（ＬｏｇＬｉｋｅｈｏｏｄ  Ｒａｔｉｏ）を行き来させることによって実現される。
特に、ＢＰＳＫ変調で加法的ガウス雑音チャネル間を送受信した場合、各ビットのＬＬＲ Ｒｉは、次式で与えられる。
【００２６】
［数８］
Ｒｉ＝（２／σ）・ｒｉ
【００２７】
ここで、σはガウス雑音の分散、ｒｉは受信値を示す。
行列の各列に対応するノードを可変（ｖａｒｉａｂｌｅ：バリアブル）ノード、各行に対応するノードを検査（ｃｈｅｃｋ：チェック）ノードと呼ぶ。
【００２８】
ｉ番目のバリアブルノードからｊ番目のチェックノードへのメッセージをＱi,j、ｊ番目のチェックノードからｉ番目のバリアブルノードへのメッセージをＲｉ,j、さらにｉ番目のバリアブルノードに連接するチェックノードのインデックス集合をＪ（ｉ）、ｊ番目のチェックノードに連接するバリアブルノードのインデックス集合をＩ（ｊ）とした場合、それぞれの更新式は以下のようになる。
【００２９】
【数９】
0004412401.tif 000009
【００３０】
ここで、θはバーティカルステップダンピングファクタ（ｖｅｒｔｉｃａｌ  ｓｔｅｐ  ｄａｍｐｉｎｇ  ｆａｃｔｏｒ）と呼ばれる係数を示し、０＜θ≦１なる条件を満足する。さらに、ｆ（Ｘ）＝ｌｎ｛（exp(x)＋1）／（exp(x)−1）である。
Ｑi,jの初期値はｒjが設定され、外部情報（ｅｘｔｒｉｎｓｉｃ  ｉｎｆｏｒｍａｔｉｏｎ）Λｉｘ更新は次式により行われる。
【００３１】
【数１０】
0004412401.tif 000010
【００３２】
さらに、各符号ビットのＬＬＲΛｉｑの更新は、次式により行われる。
【００３３】
【数１１】
0004412401.tif 000011
【００３４】
ここで、α１は適応的信頼性伝播ダンピングファクタ（ａｄａｐｔｉｖｅ  ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ  ｄａｍｐｉｎｇ  ｆａｃｔｏｒ）と呼ばれる係数を示し、０＜α１≦１なる条件を満足する。
この信頼性伝播（ＢＰ）によるＬＬＲの更新は事前に用意された繰り返し停止条件を満たすまで、たとえば最大繰り返し数ＩｔＨに達成するまで繰り返される。
【００３５】
信頼性伝播（ＢＰ）によって更新されたＬＬＲの信頼性を用いて、つまり、ＬＬＲの絶対値の大きさを信頼性として、信頼性の低いシンボルに対応する列順に対角化を行うことにより、新たな信頼性伝播（ＢＰ）による繰り返し復号を行うことができる。
これを内側繰り返し復号と呼ぶ。このＬＬＲの更新は事前に用意された内側繰り返し復号停止条件ＳＣ１を満たすまで繰り返される。
【００３６】
さらに、パリティ検査行列の列の対角化優先順位の初期値として、受信値の信頼性順以外の順位を複数用意する。複数の順位を用いて、シリアルもしくはパラレルに繰り返し内側繰り返し復号を行う。
これを外側繰り返し復号と呼ぶ。このＬＬＲ更新は事前に用意された外側繰り返し復号停止条件ＳＣ２を満たすまで繰り返される。
【００３７】
以上のＡＢＰ（ａｄａｐｔｉｖｅ  ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ）手順により繰り返し更新されたＬＬＲを入カとして、復号器により復号を行う。
今、対象となる線形符号がＲｅｅｄ−Ｓｏｌｏｍｏｎ符号であった場合、繰り返し復号停止条件ＳＣ１、ＳＣ２として、たとえば以下のものが考えられる。
【００３８】
（Ａ）  Ｈ・ｄ  ＝＝  ０または繰り返し数ｔ≧Ｎ、
（Ｂ）  限界距離復号成功または繰り返し数ｔ≧Ｎ、
（Ｃ）  Ｋｏｅｔｔｅｒ−Ｖａｒｄｙ軟判定リスト復号成功または繰り返し数ｔ≧Ｎ。
【００３９】
ここで、ｄ＝（ｄ１，ｄ２，・・・，ｄ６）はΛｉの硬判定結果、ｄｉ＝｛Λｉｑ＞０なら１，Λｉｑ≦０なら０｝であり、Ｎは事前に決めた最大繰り返し回数である。
また、復号方法として、たとえば以下のものが考えられる。
【００４０】
（ａ）  硬判定復号
（ｂ）  限界距離復号
（ｃ）  Ｋｏｅｔｔｅｒ−Ｖａｒｄｙ軟判定リスト復号
【００４１】
また、信頼性伝播（ＢＰ）には、ＵＭＰ（Ｕｎｉｆｏｒｍｌｙ Ｍｏｓｔ Ｐｏｗｅｒｆｕｌ）復号法というチェックノードメッセージ計算時の近似法が知られている（非特許文献７参照。）
計算式を以下に示す。
【００４２】
【数１２】
0004412401.tif 000012
【００４３】
ＵＭＰ復号法を用いると、複雑なｆ関数の計算が最小値探索に置き換えられることにより計算量が軽減される一方、近似による性能劣化が見られる場合もある。
また、ＵＭＰ復号はチェックノードにおけるメッセージの最小値検索とバリアブル（variable）ノードにおけるメッセージの足し合わせによってのみ実現される為、加法的ガウス雑音チャネル上ＢＰＳＫ変調での送受信を行った場合、チャネル情報σが無くても、受信値riをＬＬＲの様に用いることで信頼性伝播（ＢＰ）が可能となる。
【００４４】
【非特許文献１】Ｖ．Ｇｕｒｕｓｗａｍｉ，Ｍ．Ｓｕｄａｎ，Ｉｍｐｒｏｖｅ  ｄｅｃｏｄｉｎｇ  ｏｆ  Ｒｅｅｄ−Ｓｏｌｏｍｏｎ  ａｎｄ  Ａｌｇｅｂｒａｉｃ−Ｇｅｏｍｅｔｒｙ  ｃｏｄｅｓ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ｖｏｌ．４５，ｐｐ．１７５７−１７６７，１９９９
【非特許文献２】Ｒ．Ｋｏｅｔｔｅｒ，Ａ．Ｖａｒｄｙ，Ａｌｇｅｂｒａｉｃ  ｓｏｆｔ−ｄｅｃｉｓｉｏｎ  ｄｅｃｏｄｉｎｇ  ｏｆ  Ｒｅｅｄ−Ｓｏｌｏｍｏｎ  ｃｏｄｅｓ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，２００１
【非特許文献３】Ｒ．Ｋｏｅｔｔｅｒ，Ｊ．Ｍａ，Ａ．Ｖａｒｄｙ，Ａ，Ａｈｍｅｄ，Ｅｆｆｃｉｅｎｔ  Ｉｎｔｅｒｐｏｌａｔｉｏｎ  ａｎｄ  Ｆａｃｔｏｒｉｚａｔｉｏｎ  ｉｎ  Ａｌｇｅｂｒａｉｃ  Ｓｏｆｔ−Ｄｅｃｉｓｉｏｎ  Ｄｅｃｏｄｉｎｇ  ｏｆ  Ｒｅｅｄ−Ｓｏｌｏｍｏｎ  ｃｏｄｅｓ，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＩＳＩＴ２００３
【非特許文献４】Ｄ．ＭａｃＫａｙ，Ｇｏｏｄ  Ｅｒｒｏｒ−Ｃｏｒｒｅｃｔｉｎｇ  Ｃｏｄｅｓ  Ｂａｓｅｄ  ｏｎ  Ｖｅｒｙ  Ｓｐａｒｓｅ  Ｍａｔｒｉｃｅｓ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，１９９９
【非特許文献５】Ｂｅｒｌｅｋａｍｐ，Ｒ．ＭｃＥｌｉｅｃｅ，Ｈ．ｖａｎ  Ｔｉｌｂｏｒｇ，Ｏｎ  ｔｈｅ  ｉｎｈｅｒｅｎｔ  ｉｎｔｒａｃｔａｂｉｌｉｔｙ  ｏｆ  ｃｅｒｔａｉｎ  ｃｏｄｉｎｇ  ｐｒｏｂｌｅｍｓ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ｖｏｌ．２４，ｐｐ．３８４−３８６，Ｍａｙ，１９７８）。
【非特許文献６】Ｊｉｎｇ  Ｊｉａｎｇ，Ｋ．Ｒ．Ｎａｒａｙａｎ，Ｓｏｆｔ  Ｄｅｃｉｓｉｏｎ  Ｄｅｃｏｄｉｎｇ  ｏｆ  ＲＳ  Ｃｏｄｅｓ  Ｕｓｉｎｇ  Ａｄａｐｔｉｖｅ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ  Ｍａｔｒｉｃｅｓ，Ｐｒｏｃｅｅｄｉｎｇ  ｏｆ  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ  ２００４
【非特許文献７】Ｍ．Ｐ.Ｃ.Ｆｏｓｓｏｒｉｅｒ, Ｍ.Ｍｉｈａｌｊｅｖｉｃ,Ｈ.Ｉｍａｉ, Ｒｅｄｕｃｅｄ Ｃｏｍｐｌｅｘｉｔｙ Ｉｔｅｒａｔｉｖｅ Ｄｅｃｏｄｉｎｇ ｏｆ Ｌｏｗ-Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ Ｃｏｄｅｓ Ｂａｓｅｄ ｏｎ Ｂｅｌｉｅｆ Ｐｒｏｐａｇａｔｉｏｎ}, ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ, Ｖｏｌ.４７, Ｎｏ５, Ｍａｙ １９９９.
【発明の開示】
【発明が解決しようとする課題】
【００４５】
ところで、一般のＬＣＰＣ符号の復号器実装に関しては、想定する符号がＱｕａｓｉ-ｃｙｃｌｉｃである場合にその構造をいかしたパラレル復号実装法が幾つか知られている。
一方、ＡＢＰ復号法にその手法の適応を試みた場合、様々な困難が生じる。たとえば、ＡＢＰ復号過程で得られるパリティ検査行列はＱｕａｓｉ-ｃｙｃｌｉｃではないため効率的なパラレル実装が不可能である。また、同行列は対角部を除いて低密度ではないため、各ノードのメッセージ更新の計算量が膨大となる。また、各メッセージを保持するメモリ量も膨大となる。
【００４６】
従来のＡＢＰを用いた復号器では、扱う符号が低密度で無い場合においても現実的なスループット（ｔｈｒｏｕｇｈｔｐｕｔ）を実現するために各チェックノードメッセージ更新時に多くの信頼性情報を一度に読み出す必要があり、それには信頼性情報をレジスタで保持する必要があった。
【００４７】
しかし、全信頼性情報をレジスタで保持した場合、実装時のメモリ面積が膨大となることが懸念される。
一方、同じ情報量を半導体メモリ、たとえばＲＡＭに格納する場合は、フリップフロップ等により構成されるレジスタ実装に比べて遥かに小さく実現可能であるが、一度に取出せるデータの量は１ワード（１ｗｏｒｄ）に限定され上記目的には適していない。
【００４８】
本発明は、回路規模を削減することが可能な復号装置、復号方法、受信装置、および記憶媒体再生装置を提供することにある。
【課題を解決するための手段】
【００４９】
本発明の第１の観点は、環Ｒ上線形符号の復号装置であって、複数の記憶媒体と、処理部と、を有し、上記処理部は、各シンボルの信頼性を高める繰り返し復号の過程において前回の全シンボルの信頼性の一部を各シンボルの信頼性更新に用い、さらに保持する信頼性情報の更新に用いられる部分と用いられない部分を２つの別な記憶媒体に保持する。
【００５０】
好適には、上記処理部は、上記繰り返し復号として信頼性伝播（Belief Propagation：BP）を用い、さらに信頼性更新の際にＵＭＰ(Uniformly Most Powerful)復号法による近似を用いる。
【００５１】
好適には、上記処理部は、受信語の信頼性を求め、求められた信頼性を元にパリティ検査行列の対角化優先順位を決め、で求められた優先順位を元にパリティ検査行列を対角化し、求められたパリティ検査行列を用いて信頼性伝播（ＢＰ）を１回、もしくは複数回行い受信語の信頼性を更新する。
【００５２】
好適には、上記複数の記憶媒体にはレジスタと半導体メモリを含み、上記処理部は、信頼性更新に用いられる部分を上記レジスタに保持し、用いられない部分を上記半導体メモリに保持する。
【００５３】
好適には、線形符号として有限体上代数幾何符号もしくはその同型を用いる。
【００５４】
好適には、代数幾何符号としてリードソロモン（Reed-Solomon）もしくはＢＣＨ符号、それらの同型を用い、さらに複数回の更新により得られた信頼性を入力受信語として後段で限界距離復号を行う。
【００５５】
好適には、代数幾何符号としてリードソロモン（Reed-Solomon）もしくはＢＣＨ符号、それらの同型を用い、複数回の更新により得られた信頼性を入力受信語として所定のアルゴリズムによる硬判定リスト復号を行う。
【００５６】
好適には、代数幾何符号としてリードソロモン（Reed-Solomon）もしくはＢＣＨ符号、それらの同型を用い、複数回の更新により得られた信頼性を入力受信語として所定のアルゴリズムによる重複度設定、および軟判定リスト復号を行う。
【００５７】
本発明の第２の観点は、環Ｒ上線形符号の復号方法であって、各シンボルの信頼性を高める繰り返し復号の過程において前回の全シンボルの信頼性の一部を各シンボルの信頼性更新に用い、さらに保持する信頼性情報の更新に用いられる部分と用いられない部分を２つの別な記憶媒体に保持する。
【００５８】
本発明の第３の観点は、ＲＳまたはＢＣＨ符号化器および畳み込み符号化器を連接した装置から送信された信号を受信する受信装置であって、上述した信頼性更新、および復号方法を用いた復号装置を有する。
【００５９】
本発明の第４の観点は、ＲＳまたはＢＣＨ符号化器および畳み込み符号化器を連接した装置から送信された信号を受信する受信装置であって、上述した信頼性更新、および復号方法を用いた繰り返し復号装置を有する。
【００６０】
本発明の第５の観点は、ＲＳまたはＢＣＨ符号を用いてｎ次元積符号化された信号の記憶媒体再生装置であって、上述した信頼性更新、および復号方法を用いた復号装置を有する。
【００６１】
好適には、ＲＳまたはＢＣＨ符号を用いてｎ次元積符号化された信号の記憶媒体再生装置であって、上述した信頼性更新、および復号方法を用いた繰り返し復号装置を有する。
【００６２】
本発明によれば、信頼性更新に用いられる部分を上記レジスタに保持し、用いられない部分を上記半導体メモリに保持することにより、小さな回路規模で実装可能となる。
【発明の効果】
【００６３】
本発明によれば、回路規模を削減することが可能となる。
【発明を実施するための最良の形態】
【００６４】
以下、本発明の実施形態を図面に関連付けて説明する。
【００６５】
本発明の実施形態に係る復号装置は、代数的手法を用いた誤り訂正符号技術を実現するための回路、たとえば適応的信頼性伝播（Ａｄａｐｔｉｖｅ  Ｂｅｌｉｅｆ  Ｐｒｏｐａｇａｔｉｏｎ：ＡＢＰ）復号器に応用できる。
ＡＢＰ復号は、リードソロモン（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ：ＲＳ）符号やＢＣＨ符号、その他低密度でないパリティ検査行列を持つ線形符号に対する復号法であり、ある伝送路から符号語を受信すると、その受信語をより信頼できる値に更新する。
また、本実施形態においては、信頼性伝播（ＢＰ）による受信値の信頼性の更新をＵＭＰ（Ｕｎｉｆｏｒｍｌｙ  Ｍｏｓｔ  Ｐｏｗｅｒｆｕｌ）復号を用いた近似値による更新で実現する。
【００６６】
本実施形態に係るＡＢＰ復号器は、各シンボルの信頼性を高める繰り返し復号の過程において前回の全シンボルの信頼性の一部を各シンボルの信頼性更新に用い、さらに保持する信頼性情報の更新に用いられる部分と用いられない部分を２つの別な記憶媒体、具体的には、フリップフロップ等からなるレジスタと半導体メモリ、たとえばＲＡＭに保持する。
本実施形態においては、信頼性更新に用いられる部分をレジスタに保持し、用いられない部分をＲＡＭに保持する。
また、本実施形態に係るＡＢＰ復号器は、受信語の信頼性を求め、求められた信頼性を元にパリティ検査行列の対角化優先順位を決め、で求められた優先順位を元にパリティ検査行列を対角化し、求められたパリティ検査行列を用いて信頼性伝播（ＢＰ）を１回、もしくは複数回行い受信語の信頼性を更新する。
【００６７】
以下に、本発明の第１の実施形態としてＡＢＰ復号器の具体的な構成および機能の一例について説明する。
【００６８】
＜第１実施形態＞
図２は、本発明の実施形態に係るＡＢＰ復号器（復号装置）の構成例を示すブロック図である。
【００６９】
本ＡＢＰ復号器１００は、図２に示すように、ソート回路(ＳＯＲＴ)１１０、対角化回路（ＤＡＩＧ）１２０、行列格納メモリ（ＭＡＴ）１３０、ＬＬＲ格納メモリ１４０、およびＵＭＰ復号器１５０を有する。
なお、これらのソート回路(ＳＯＲＴ)１１０、対角化回路（ＤＡＩＧ）１２０、行列格納メモリ（ＭＡＴ）１３０、ＬＬＲ格納メモリ１４０、およびＵＭＰ復号器１５０により本発明の処理部が構成される。
【００７０】
ソート回路１１０はセレクタ１１１を有し、ＬＬＲ格納メモリ１４０はレジスタ１４１およびＲＡＭ１４２を有する。
【００７１】
ソート回路１１０のソートアルゴリズムとしてバケツソートや逆写像ソートbitonicソートなどを用いることが可能である。
また、対角化回路１２０として、ガウスの消去法をシリアル、もしくはパラレルに行うような回路を用いることが可能である。
【００７２】
さらに、ＵＭＰ復号のチェック（ｃｈｅｃｋ）ノード演算時に用いるダンピングファクタ（ｄａｍｐｉｎｇ ｆａｃｔｏｒ） α1を調整することによりレジスタ１４１に格納するＬＬＲ情報を２ビット、そのうち１ビットは符号、１ビットは信頼性の大きさとし、信頼性の最小値探索をＡＮＤゲートのみで実装することも可能である。
また、更新されるＬＬＲは１２８ビット分より多くても少なくても良い。
【００７３】
ここでは、有限体としてＦ２8、線形符号cとして（204,188）Reed-Solomon符号を考える。
生成多項式を次式とし、
【００７４】
【数１３】
0004412401.tif 000013
【００７５】
情報語をf=(f０,f１,f２,…f１８７)とし、対応する情報多項式を次式としたとき、
【００７６】
【数１４】
0004412401.tif 000014
【００７７】
組織的符号化による符号語c=(c０,c１,c２,…,c２０３)に対応する符号多項式は次式で与えれる。
【００７８】
【数１５】
0004412401.tif 000015
【００７９】
符号語ｃをビット展開した後ＢＰＳＫ変調、加法的ガウス雑音伝送路間で送受信する。
(204,188)Reed-Solomon符号は１シンボル８ビットであるため、２０４シンボル分の情報は各シンボル８ビットに展開され全１６３２ビットの情報としてＢＰＳＫ変調される。ｃのビット展開に対応する受信語をd=(d０,d１,d２,…,d１６３１)とする。
本実施形態においては、この受信語に対してＵＭＰ復号の近似を用いたＡＢＰ復号を行う。
【００８０】
第一に、ソート回路１１０において得られた１６３２の受信値をその信頼性、つまり絶対値の大きさ順に並べ替える。ＵＭＰ復号を行うため、ここで伝送路情報を用いてＬＬＲを算出する必要はない。
【００８１】
第二に、信頼性の大きい１２８ビットに対応するパリティ検査行列の列に対して対角化回路１２０で対角化を行う。
【００８２】
第三に、対角化がなされたパリティ検査行列を用いてＵＭＰを用いた信頼性伝播（ＢＰ）復号を行う。現実的な実装を実現するため、また、信頼性の低いビット程繰り返し復号によりＬＬＲ更新される必要が高いため、１６３２ビット中対角化のなされた１２８ビットに対してのみＬＬＲ更新を行うこととする。
【００８３】
また、チェック（ｃｈｅｃｋ）ノードメッセージ算出に用いられるＡＢＰダンピングファクタ（ｄａｍｐｉｎｇ ｆａｃｔｏｒ） α１を２の冪乗分の１、たとえばα１=1/8とすることとし、ビットシフトによりα１の乗算を実現することとする。行列の１変更に対応する繰り返し復号の回数ＩｔＨを１とした場合、各ビットのＬＬＲ更新に必要な計算は以下の通りとなる。
【００８４】
【数１６】
0004412401.tif 000016
【００８５】
ここで、パリティ検査行列が対角化された結果ｉ列目はｊ行目にのみ１が立っているものとする。
各チェック（ｃｈｅｃｋ）ノードに連結されるバリアブル（ｖａｒｉａｂｌｅ）ノードのインデックスの集合I(j)は対角化がなされる度に変化するため、さらに全インデックス中約半分がI(j)のメンバーとなるため、各ビットの信頼性更新にほぼ全てのＬＬＲ情報が必要となり、それらＬＬＲはメモリに保持されていなくてはならない。
さらに、現実的なスループット（throughput）を実現するためには１つのチェックノードメッセージ更新に多くのクロック数を費やす訳にはいかない。
たとえば、１クロックでチェックノードのメッセージを更新することとすると、I(i)のメンバーをインデックスとするようなメッセージを一度に取出して最小値探索を行い、得られた最小値の下位３ビット以外部分、たとえばメッセージが全５ビットで表されていたとするとその上位２ビットを受信値に加算することによりＡＢＰ復号は実現される。
【００８６】
ここで、各ビットの信頼性５ビットのうち、上位２ビットをレジスタに、下位３ビットをＲＡＭ１４２に格納する。すると、各ビットのＬＬＲ更新に必要とされうる全ビットのＬＬＲ上位２ビットは毎クロック同時にアクセス可能となり、自身の更新時のみ必要とされる下位３ビットはＲＡＭ１４２から１クロックに付き１ＬＬＲ分ずつアクセス可能となる。
このとき、レジスタ１４１に格納されて随時アクセス可能な上位２ビットと合わせてＬＬＲ更新に用いる。
【００８７】
以上の手法により、１クロックに１ＬＬＲ更新可能なＵＭＰ復号が実現され、全情報をレジスタに格納した場合に比べると部分的にＲＡＭ１４２を用いることにより回路規模が大幅に削減される。
【００８８】
なお、代数幾何符号としてリードソロモン（Reed-Solomon）もしくはＢＣＨ符号、それらの同型を用い、さらに複数回の更新により得られた信頼性を入力受信語として後段で限界距離復号を行うことが可能である。
あるいは、代数幾何符号としてリードソロモン（Reed-Solomon）もしくはＢＣＨ符号、それらの同型を用い、複数回の更新により得られた信頼性を入力受信語としてSudan,Grusuwami-Sudan、もしくはその他のアルゴリズムによる硬判定リスト復号を行うことが可能である。
あるいは、代数幾何符号としてリードソロモン（Reed-Solomon）もしくはＢＣＨ符号、それらの同型を用い、複数回の更新により得られた信頼性を入力受信語としてKoetter-Vardy,ElKhamy-McEliece、もしくはその他のアルゴリズムによる重複度設定、および軟判定リスト復号を行うことが可能である。
【００８９】
また、システム全体としては、図２のＡＢＰ復号器を複数個持ち、それぞれをパラレルにもちいることによってスループット（throughput）を上げるような構造を持つＡＢＰ復号器として用いることも可能である。
【００９０】
以下に、第２〜第６の実施形態として、第１の実施形態に係るＡＢＰ復号器を採用可能な各種装置（受信装置および記憶媒体再生装置）について説明する。
【００９１】
＜第２実施形態＞
図３は、デジタル信号受信機（受信装置）、たとえばデジタルテレビなどの誤り訂正システムにＡＢＰ復号器を用いた第２の実施形態に係る通信システムの構成例を示す図である。
【００９２】
本通信システム２００は、図３に示すように、ＲＳ符号化器２１０、インタリーバ２２０、畳み込み符号化器２３０、畳み込み符号の軟出力復号器２４０、デインタリーバ２５０、ＲＳ符号のレジスタとＲＡＭを併用したＡＢＰ復号器２６０、およびチャネル２７０を有する。
【００９３】
本第２の実施形態レジスタの通信システム２００は、ＲＡＭを併用したＡＢＰ復号器を採用していることか回路規模が大幅に削減される。
【００９４】
本通信システム２００では、ＲＳ符号化、畳み込み符号化された送信語に対して、畳み込み符号の軟出力復号をした後に、レジスタとＲＡＭを併用したＡＢＰ復号器２６０においてＡＢＰ復号を行っている。
ここで言う畳み込み符号の軟出力復号とは、たとえばＢＣＪＲアルゴリズムやＳＯＶＡによる復号のことである。
レジスタとＲＡＭを併用したＡＢＰ復号器２６０においては、ＡＢＰによる信頼性の更新後、硬判定後限界距離復号、リスト復号、もしくは、軟値をそのまま入力として軟判定リスト復号を行う。
【００９５】
本第２の実施形態レジスタの通信システム２００は、ＲＡＭを併用したＡＢＰ復号器を採用していることか回路規模が大幅に削減される。
【００９６】
＜第３実施形態＞
図４は、デジタル信号受信機（受信装置）、たとえばデジタルテレビなどの誤り訂正システムにＡＢＰ復号器を用いた第３の実施形態に係る通信システムの構成例を示す図である。
【００９７】
本第３の実施形態の通信システム２００Ａが第２の実施形態の通信システム１００と異なる点は、受信語に対して、畳み込み符号の軟出力復号を行った後に、レジスタとＲＡＭを併用したＡＢＰ復号器２６０を備え、ＡＢＰ復号をインタリーバ２８０、デインタリーバ２５０を介して繰り返し行うシステムとして構成されていることにある。
ここで言う畳み込み符号の軟出力復号とは、たとえばＢＣＪＲアルゴリズムやＳＯＶＡによる復号のことである。
【００９８】
本第３の実施形態レジスタの通信システム２００Ａは、ＲＡＭを併用したＡＢＰ復号器を採用していることか回路規模が大幅に削減される。
【００９９】
＜第４実施形態＞
図５は、レジスタとＲＡＭを併用したＡＢＰ復号器を採用した第４の実施形態に係るデジタル記憶媒体再生器の構成例を示す図である。
【０１００】
デジタル記憶媒体再生器（記憶媒体再生装置）３００としては、たとえばＤＶＤプレイヤーなどを例示することができる。
【０１０１】
本デジタル記憶媒体再生器３００は、ｎ次元ＲＳ積符号化された送信語に対して処理可能で、各ｎ次元目に関するＲＳ符号化器３１０−１〜３１０−ｎ、チャネル３２０、およびそれぞれ各ｎ次元目に対応するレジスタとＲＡＭ併用ＡＢＰ復号器３３０−１〜３３０−ｎを有する。
ｎ次元ＲＳ積符号化された信号に対して硬判定後ｎ次元の各ｎ次元目に対応するレジスタとＲＡＭ併用ＡＢＰ復号器３３０−１〜３３０−ｎによりＡＢＰ復号が行わる。
【０１０２】
本第４の実施形態レジスタのデジタル記憶媒体再生器３００は、ＲＡＭを併用したＡＢＰ復号器を採用していることか回路規模が大幅に削減される。
【０１０３】
＜第５実施形態＞
図６は、レジスタとＲＡＭを併用したＡＢＰ復号器を採用した第５の実施形態に係るデジタル記憶媒体再生器の構成例を示す図である。
【０１０４】
本第５の実施形態に係るデジタル記憶媒体再生器３００Ａが第４の実施形態に係るデジタル記憶媒体再生器３００と異なる点は、各ｎ次元目に対応する１度目の既知情報入りＲＳリスト復号を行うレジスタとＲＡＭ併用ＡＢＰ復号器３３０−１〜３３０−ｎに加えて、各ｎ次元目に対応するm-1度目の既知情報入りＲＳリスト復号を行うレジスタとＲＡＭ併用ＡＢＰ復号器３３１−１〜３３１−ｎ、・・・、３３ｍ−１〜３３ｍ−ｎを設けたことにある。
【０１０５】
本第５の実施形態に係るデジタル記憶媒体再生器３００Ａにおいては、受信語に対して、レジスタとＲＡＭ併用ＡＢＰ復号器によるＡＢＰ復号を各次元に対して繰り返しm-1回行う。
【０１０６】
本第５の実施形態レジスタのデジタル記憶媒体再生器３００Ａは、ＲＡＭを併用したＡＢＰ復号器を採用していることか回路規模が大幅に削減される。
【０１０７】
なお、以上詳細に説明した方法は、上記手順に応じたプログラムとして形成し、ＣＰＵ等のコンピュータで実行するように構成することも可能である。
また、このようなプログラムは、半導体メモリ、磁気ディスク、光ディスク、フロッピー（登録商標）ディスク等の記録媒体、この記録媒体をセットしたコンピュータによりアクセスし上記プログラムを実行するように構成可能である。
【図面の簡単な説明】
【０１０８】
【図１】パリティ検査行列Ｈｎｅｗに対応するタナーグラフである。
【図２】本発明の実施形態に係るＡＢＰ復号器（復号装置）の構成例を示すブロック図である。
【図３】デジタル信号受信機、たとえばデジタルテレビなどの誤り訂正システムにＡＢＰ復号器を用いた第２の実施形態に係る通信システムの構成例を示す図である。
【図４】デジタル信号受信機、たとえばデジタルテレビなどの誤り訂正システムにＡＢＰ復号器を用いた第３の実施形態に係る通信システムの構成例を示す図である。
【図５】レジスタとＲＡＭを併用したＡＢＰ復号器を採用した第４の実施形態に係るデジタル記憶媒体再生器の構成例を示す図である。
【図６】レジスタとＲＡＭを併用したＡＢＰ復号器を採用した第５の実施形態に係るデジタル記憶媒体再生器の構成例を示す図である。
【符号の説明】
【０１０９】
１００・・・ＡＢＰ復号器、１１０・・・ソート回路(ＳＯＲＴ)、１２０・・・対角化回路（ＤＡＩＧ）、１３０・・・行列格納メモリ（ＭＡＴ）、１４０・・・ＬＬＲ格納メモリ、１５０・・・ＵＭＰ復号器、２００，２００Ａ・・・通信システム、２１０・・・ＲＳ符号化器、２２０，２８０・・・インタリーバ、２３０・・・畳み込み符号器、２４０・・・畳み込み符号の軟出力復号器、２５０・・・デインタリーバ、２６０・・・レジスタとＲＡＭを併用したＡＢＰ復号器、２７０・・・チャネル、３００，３００Ａ・・・デジタル記憶媒体再生器、３１０−１〜３１０−ｎ・・・ＲＳ符号化器、３２０・・・チャネル、３３０−１〜３３０−ｎ，３３１−１〜３３１−ｎ，３３ｍ−１〜３３ｍ−ｎ・・・レジスタとＲＡＭ併用ＡＢＰ復号器。
【図１】
0004412401.tif 000017
【図２】
0004412401.tif 000018
【図３】
0004412401.tif 000019
【図４】
0004412401.tif 000020
【図５】
0004412401.tif 000021
【図６】
0004412401.tif 000022