(57)【特許請求の範囲】
【請求項１】
ＬＤＰＣ (Low-Density Parity-Check) 符号により符号化されて伝送された系列に対して復号処理を実施する誤り訂正復号装置において、誤り訂正復号装置を構成する繰り返し復号演算手段は、その演算中間値保存回路に入力および出力される検査行列の特定の行番号に関連する演算中間値の保存位置が各繰り返し演算内で複数回、あらかじめ定められた規則で変動するように、入力および出力があらかじめ定められた規則に連動して制御される構成にされたことを特徴とする誤り訂正復号装置。
【請求項２】
演算中間値保存回路は、行演算素子Ａ→列演算素子→行演算素子Ｂと流れる一連の系統での遅延クロック数をｄとするとき、任意の時点ｔ、その時点ｔより遅延クロック数ｄまたは、それ以上の所定の前の時点、およびその時点ｔより遅延クロック数ｄ以上または、それ以上の所定の後の時点の間で、行番号ｍに対応する演算中間値の入出力が最大一回のみ実施されるように、入力および出力を制御する構成にされたことを特徴する請求項１記載の誤り訂正復号装置。
【請求項３】
演算中間値保存回路は、あらかじめ定められた遅延段数となっている複数のＦＩＦＯ (First-In/First-Out) により構成されていることを特徴する請求項１又は２に記載の誤り訂正復号装置。
【請求項４】
誤り訂正復号処理は、Sum-Product復号法に基づいて復号処理を実施する回路構成にされたことを特徴する請求項１乃至３の何れか１項に記載の誤り訂正復号装置。
【請求項５】
演算中間値保存回路にて保存される演算中間値が、保存する要素数が削減されるmin-sum復号法もしくは巡回近似MIN復号法などの簡易復号法に基づいて、算出されることを特徴する請求項１乃至３の何れか１項に記載の誤り訂正復号装置。
【請求項６】
演算中間値保存回路は、演算中間値の保存位置が繰り返し復号演算の実行が１回終了した時点で元の保存位置に戻るように構成されたことを特徴とする請求項１乃至５の何れか１項に記載の誤り訂正復号装置。
【請求項７】
ＬＤＰＣ(Low-Density Parity-Check) 符号により符号化されて伝送された系列に対して復号処理を実施する誤り訂正復号方法において、誤り訂正復号方法を構成する繰り返し復号演算工程は、演算中間値保存回路に入力および出力される検査行列の特定の行番号に関連する演算中間値の保存位置が各繰り返し演算内で複数回、あらかじめ定められた規則で変動するように、入力および出力があらかじめ定められた規則に連動して制御される方法にされたことを特徴とする誤り訂正復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ディジタル伝送システムやディジタル記録システムにおける誤り訂正復号技術に関するものである。
【背景技術】
【０００２】
以下、従来の誤り訂正復号技術について説明する。
【０００３】
非特許文献１のFig. 6に、ＬＤＰＣ(Low-Density Parity-Check) 符号の軟判定繰り返し復号回路が記載されている。図６に、その復号回路に含まれる繰り返し復号演算手段１０を記す。
【０００４】
ＬＤＰＣ符号は、符号語の各ビットに対応するvariable node（ビットノード）と、パリティ検査和に対応するcheck node（チェックノード）とを枝で結んだ形状のグラフ（Tanner graphと呼ばれる）で表現できる（非特許文献１のFig.2参照）。ＬＤＰＣ符号の復号では、これらのnodeにて、枝で結ばれた別のnodeから送られる信頼度情報に基づいて、ビットまたはパリティ検査和の信頼度を更新して、それを枝で結ばれた別のnodeへ送るという確率伝搬動作を複数回繰り返す。
【０００５】
ここで、従来の繰り返し復号演算手段１０の動作について数式を交えて説明する。なお、この従来技術に記載の数式の記号は非特許文献１の定義にあわせて記載する。従って、実施の形態の説明部分の数式の定義と異なっている。
【０００６】
variable nodeで実施する演算を列演算と呼ぶ。パリティ検査行列Ｈのｊ列目において、パリティ検査行列のｉ'行目に１が立っている場合（ｈｉ'ｊ ＝ １）、その個々のｉ'について、以下式（１）の演算を実施する。
【０００７】
【数１】
0004739086.tif 000002
【０００８】
なお、λ＊ｉｊ は、ｉ行目のcheck nodeからｊ列目のvariable nodeに受け渡される信頼度値である。図６では、式（１）の演算を実施する列演算素子１１が符号長Ｎ個分だけ存在する。
【０００９】
check nodeで実施する演算を行演算と呼ぶ。パリティ検査行列Ｈのｉ行目において、ｊ'列目に１が立っている場合（ｈｉｊ' ＝ １）、その個々のｊ'について、以下式（２）の演算を実施する。
【００１０】
【数２】
0004739086.tif 000003
【００１１】
なお、λｉｊ は、ｊ列目のvariable nodeからｉ行目のcheck nodeに受け渡される信頼度値である。図６では、式（２）の演算を実施する行演算素子１２がパリティ検査行列の行数Ｍ個分だけ存在する。
【００１２】
図６では、列演算素子１１の出力結果（式（１）のλｉ'ｊ）を、ＤＦＦ((D flip-flop)で実装された演算中間値保存回路１３に保存する。信頼度値λｉ'ｊの書き込み位置は固定される。つまり、ＤＦＦ Ｘ１に保存した （ｈｉ'ｊ ＝ １）の数値は、行演算素子１２、列演算素子１１を経由して（Ｙ１で示される経路１６）、再びＤＦＦ Ｘ１へ入力される。また、ＤＦＦ Ｗ１に保存した数値は、行演算素子１２、列演算素子１１を経由して（Ｚ１で示される経路１７）、再びＤＦＦ Ｗ１へ入力される。
【００１３】
式（１）の列演算は、符号長Ｎ回実施する必要がある。また、式（２）の行演算は、パリティ検査行列の行数Ｍ回実施する必要がある。非特許文献１に記載の従来技術では、個々の演算素子を完全に並列に実装している。しかしその場合、符号長Ｎが長くなると、実装が困難になる。
【００１４】
よって、演算素子数をＰ ＝ Ｎ ／ Ｃ （Ｎは符号長、Ｃは繰り返し演算1回あたりの動作クロック数）として、部分的に並列化することを考える。この部分並列化の技術は、非特許文献２のFig. 5, 6 に記載されている。この技術では、列演算素子および行演算素子を制限した個数のみ搭載する。繰り返し演算１回あたりの動作クロック数をＣとして、行演算および列演算を限られた素子を用いて、クロック数Ｃの時間で部分並列的に実施する。その部分並列演算順序制御を制御回路で実施している。また、演算素子と演算中間値保存回路との接続制御をアドレスデコーダで実施している。
【００１５】
【非特許文献１】A. J. Blanksby et. al., “A 690-mW 1Gb/s 1024-b, rate-1/2 low-density parity-check code decoder,” IEEE J Solid-State Circuits, vol. 37, Mar. 2002.
【非特許文献２】M. Karkooti, J. R. Cavallaro, “Semi-parallel reconfigurable architectures for real-time LDPC decoding,” Proc. IEEE International Conference on Information Technology: Coding and Computing 2004 (ITCC 2004), vol. 1, pp. 579-585, Apr. 2004.
【非特許文献３】和田山正, “低密度パリティ検査符号とその復号方法について,” 信学技報 MR 2001-83, pp. 39-46, Dec. 2001.
【非特許文献４】松本渉, 阪井塁, 吉田英夫 “巡回近似MINアルゴリズム,” 信学技報 RCS 2005-40, pp. 1-6, July 2005.
【発明の開示】
【発明が解決しようとする課題】
【００１６】
しかしながら、上記、従来の誤り訂正復号技術においては、演算中間値の保存場所を変数ごとに固定としている。よって、長い符号長のＬＤＰＣ符号の復号回路を構成するに当たり、演算中間値保存場所と演算素子との配線１４、１５およびアドレス制御が複雑になるという問題があった。
【００１７】
この発明は、上記に鑑みてなされたものであって、演算素子と演算中間値保存回路との配線およびアドレス制御を単純化することにより、長い符号長のＬＤＰＣ符号の復号回路を容易に構成することを目的とする。
【課題を解決するための手段】
【００１８】
この発明に係る誤り訂正復号装置は、
ＬＤＰＣ (Low-Density Parity-Check) 符号により符号化されて伝送された系列に対して復号処理を実施する誤り訂正復号装置において、誤り訂正復号装置を構成する繰り返し復号演算手段は、その演算中間値保存回路に入力および出力される検査行列の特定の行番号に関連する演算中間値の保存位置が各繰り返し演算内で複数回、あらかじめ定められた規則で変動するように、入力および出力があらかじめ定められた規則に連動して制御される構成にされる。
【発明の効果】
【００１９】
この発明の誤り訂正復号装置によれば、誤り訂正復号装置を構成する繰り返し復号演算手段が算出する各演算中間値とそれを保持するための保存回路との対応を固定せず、演算の過程で逐次変動させることにより、各演算素子と演算中間値保存回路との配線およびアドレス制御を単純化することができる。
【発明を実施するための最良の形態】
【００２０】
以下に、この発明にかかる誤り訂正復号方法および誤り訂正復号装置の実施の形態を図面に基づいて詳細に説明する。
実施の形態１．
図１はこの発明の誤り訂正復号装置の特長部分である繰り返し復号演算手段２０を示す構成図であり、図２は、この発明の誤り訂正復号装置を実施する伝送システムの構成図である。図３は図２における復号器４３を示す構成図であり、復号器４３がこの発明の誤り訂正復号装置で構成される。また、図４はこの発明の誤り訂正復号装置において実施される演算順序制御の好適な例を示したものである。なお、図５はこの発明の繰り返し復号演算手段２０について、演算中間値保存回路２３を特に強調して表示した構成図である。
【００２１】
なお、実施の形態１の説明にあたり、従来技術との比較を容易にするため、ＬＤＰＣ符号の復号方法として一般的に知られているSum-Product復号法に基づいて説明する。しかし、この発明はSum-Product復号法に限定されるものではなく、Sum-Product復号法に比べ簡易演算として知られるMin-Sum復号法などへの適用も可能である。また、実施の形態１の説明で利用する数式の定義は、従来技術の説明にて利用したものと一部異なっている。
【００２２】
ここで、図２の伝送システムについて、以下の通りに説明する。
【００２３】
図２において、符号化器３１で情報源からの情報語系列をＬＤＰＣ符号化し、その符号語系列を変調器３２で送信信号に変調して通信路３３で受信側に送信する。受信側では、復調器４１で受信信号をアナログ受信系列に復調し、アナログ／ディジタル変換器４２で量子化受信系列にＡ／Ｄ変換して復号器４３に入力する。復号器４３はＬＤＰＣ符号語系列を誤り訂正復号して推定符号語系列を算出し、この推定符号語系列から推定情報系列を抽出して出力する（受信者に渡す）。
なお、符号化器３１、変調器３２、通信路３３、復調器４１、アナログ／ディジタル変換器４２は、それぞれ一般的に利用されている装置である。この実施の形態１の誤り訂正復号装置は、復号器４３に適用されるものであり、その構成は図３のようになっている。
【００２４】
ここで、図３の誤り訂正復号装置である復号器４３について、以下の通りに説明する。
【００２５】
図３は、誤り訂正復号装置である復号器４３の構成を示したものである。図３において、対数尤度比演算手段５１で、受信系列から対数尤度比(Log-Likelihood Ratio: ＬＬＲ)の演算を実行する。対数尤度比演算手段５１は、ＬＬＲの演算をし、その結果の量子化された数値を保持するＬＬＲ演算ＲＯＭと、受信値からその受信値に対応するＬＬＲ演算ＲＯＭのアドレスを算出するＬＬＲ演算ＲＯＭアドレス生成回路により構成されている。
【００２６】
ＬＬＲ演算ＲＯＭには、軟判定受信系列ｙの各受信値ｙｎ，ｎ＝０，１，．．．，Ｎ−１から求められるビットごとの対数尤度比（ＬＬＲ）  λｎの算出結果がまとめて保持されている。ＬＬＲの算出方法は、変調方式、復調方式、通信路のＳＮＲ（Signal-to-Noise Ratio）によって異なる。ＢＰＳＫ（Binary Phase Shift Keying）変調、ＡＷＧＮ（Additive White Gaussian Noise）通信路の場合は、式（３）に基づいて算出する。ここで、送信符号語系列をｘ＝（ｘ０，ｘ１，．．．，ｘＮ−１）と定義する。
【００２７】
【数３】
0004739086.tif 000004
【００２８】
対数尤度比演算手段５１にて算出されたＬＬＲ  λｎは、対数尤度比保存手段５２に保存される。ＬＬＲ  λｎは、繰り返し復号演算の繰り返しごとにメモリから呼び出され、繰り返し復号演算手段２０へ入力される。
【００２９】
繰り返し復号演算手段２０では、入力されたＬＬＲ  λｎと、内部の演算中間値保存回路２３で保持している演算中間値から、繰り返し復号を実行して、推定符号語系列ｘ'＝（ｘ'０，ｘ'１，．．．，ｘ'Ｎ−１）を算出する。算出された推定符号語系列ｘ'は、一旦推定符号語系列保持手段５３に保存された後、推定情報系列を抽出して復号器４３から出力される。
【００３０】
ここで、図１の動作について、以下の通りに説明する。
図１は、この発明の繰り返し復号演算装置（復号器）４３の主要な要素である繰り返し復号演算手段２０の構成を示したものである。図１において行演算処理を実施する行演算素子２２を、演算過程を分割して、それぞれを行演算素子２２Ａおよび行演算素子２２Ｂと定義する。Sum-Product復号法の場合、行演算処理は信頼度値α（ｌ）ｍｎを式（４）で演算する。
【００３１】
【数４】
0004739086.tif 000005
【００３２】
ここで、数式の定義を以下に記す。
ｌ : 繰り返し数（Ｌの小文字）
Ａ（ｍ）：パリティ検査行列Ｈのｍ行目で、Ｈｍｎ＝１となる列番号ｎの集合
Ｂ（ｎ）：パリティ検査行列Ｈのｎ列目で、Ｈｍｎ＝１となる行番号ｍの集合
Ｈｍｎ : パリティ検査行列Ｈのｍ行ｎ列の要素
Ａ（ｍ）＼ｎ：集合Ａ（ｍ）から、要素ｎを除いた集合
α（ｌ）ｍｎ：繰り返し演算ｌ回目でｍ行目のチェックノードからｎ列目のビットノードへ受け渡す信頼度値
β（ｌ）ｍｎ：繰り返し演算ｌ回目でｎ列目のビットノードからｍ行目のチェックノードへ受け渡す信頼度値
｜Ａ（ｍ）｜：行番号ｍの行重み（Ｈｍｎ＝１となる列番号ｎの個数）
｜Ｂ（ｎ）｜：列番号ｎの列重み（Ｈｍｎ＝１となる行番号ｍの個数）
【００３３】
行演算処理の分割方法は、採用する復号方法、演算方法により様々な手法が考えられる。しかしどのような手法を採用しても、この発明にとって本質的な差異とはならず、この発明の適用は可能である。したがって、詳細な説明は割愛する。
【００３４】
列演算処理は信頼度値β（ｌ）ｍｎを式（５）で演算する。
【００３５】
【数５】
0004739086.tif 000006
【００３６】
ここで、
Ｂ（ｎ）は上述のパリティ検査行列Ｈのｎ列目で、Ｈｍｎ＝１となる行番号ｍの集合である。
【００３７】
列演算素子２１の個数をＰとする。行演算素子２２Ａおよび２２Ｂは、個々の列演算素子２１と関連付けられる枝数だけ設ける。ここで、Ｐ＜Ｎ（Ｎ＝符号長）として、部分並列演算を実施することを想定する。繰り返し演算１回あたりの動作クロック数をＣ＝Ｎ／Ｐとして、行演算および列演算を限られた素子を用いて、クロックＣの時間で部分並列的に実施する。
【００３８】
演算中間値保存回路２３は、行演算素子２２Ａに入力される数値を演算順序別に保存するＦＩＦＯ(First-In, First-Out)で実装する。このＦＩＦＯの個数は行演算素子２２Ａの個数と等しい。行重みの平均値をＭ（｜Ａ｜）とすると、ＦＩＦＯの遅延段数は平均的にほぼ Ｎ／（Ｐ＊Ｍ（｜Ａ｜））に近いが、個々のＦＩＦＯの遅延段数は繰り返し演算１回あたりの動作クロック数Ｃとパリティ検査行列Ｈとによって異なる。なお、演算中間値保存回路２３の構成は、複数のＦＩＦＯの集合で、各ＦＩＦＯの遅延段数Ｃｆが一定とは限らないという条件が論理的に成り立てばよく、物理的な構成方法を制約しない。
【００３９】
演算中間値保存回路２３を構成する複数のＦＩＦＯに含まれる各要素（１遅延分の保存領域）には、パリティ検査行列の特定の行番号ｍに関連する演算中間値を保存する。Sum-Product復号法の場合、α（ｌ）ｍｎ，β（ｌ）ｍｎのｍ行目に対応する数値を保存すればよい。その数値の個数はそれぞれ｜Ａ（ｍ）｜となる。また、α（ｌ）ｍｎ，β（ｌ）ｍｎのどちらか一方を１個にまとめた数値（α（ｌ）ｍまたはβ（ｌ）ｍ）としてもよい。
【００４０】
ＦＩＦＯ Ｗ２に保存された演算中間値は、行演算素子、列演算素子を経由して（Ｘ２で示される経路２６）更新される。しかし、更新された演算中間値の保存場所はＦＩＦＯ Ｗ２とは異なるＦＩＦＯ Ｙ２となる。そして、ＦＩＦＯ Ｙ２に保存された演算中間値は、前回とは異なる行演算素子、列演算素子を経由して（Ｚ２で示される経路２７）更新され、また別のＦＩＦＯへ保存される。
【００４１】
つまり、各演算中間値とそれを保持するための保存回路との対応を固定せず、演算の過程で逐次変動させるような構成としている。経路２６および経路２７のように演算中間値を鎖状に逐次動かす。この演算中間値の経路は、繰り返し回数が１回で再び元のＦＩＦＯの特定番地に戻る。またこの経路における遅延段数の総計はＣとなる。
【００４２】
繰り返し復号演算手段２０では、特定の演算中間値が、あらかじめ定められた時点で、あらかじめ定められた行演算素子および列演算素子により演算処理されるように、演算中間値保存回路２３のＦＩＦＯの段数と配線２４、配線２５および演算中間値保存回路２３の構成を決めておく必要がある。配線２４は、演算中間値保存回路２３の個々のＦＩＦＯの出力端子と行演算素子２２Ａ、列演算素子２１および行演算素子２２Ｂの各演算素子とを結ぶ配線であるが、これらは一対一に対応しており、配線としては単純な構成となる。また、配線２５は、行演算素子２２Ｂと演算中間値保存回路２３の個々のＦＩＦＯの入力端子とを結ぶ配線である。配線２５をどのように構成するかは、並列演算素子数Ｐ、パリティ検査行列Ｈなどの条件によって定められる。配線２４に比べて配線２５は若干複雑にはなるが、従来技術に比べてその複雑度は低減される。このような構成により、アドレス制御はＦＩＦＯに保存する演算中間値と、予め定められたた配線２４、２５の対応表を基に実行されるので、各演算素子と演算中間値保存回路２３との配線およびアドレス制御を単純化することができる。
【００４３】
この繰り返し復号演算手段２０では、列演算素子２１の個数Ｐ個の並列数で、列演算素子２１および行演算素子２２Ａ、２２Ｂが並べられた回路構成となっている。それを繰り返し演算１回あたりの動作クロック数Ｃで動作させるが、その各時点で演算される行番号ｍの制御を行う必要がある。それを実現する方法は、ある時点（クロック）で行番号ｍに対する演算が、Ｐ並列の演算素子の中で最大一箇所でのみ実施されるように、時点ｔ、演算素子の番号ｐおよび演算中間値の行番号ｍの組み合わせを検索することである。
【００４４】
図４に、時点ｔ、演算素子および演算中間値の行番号ｍの好適な組み合わせの例を示す。Ｐ個の部分並列に並べた列演算素子２１に、便宜的に演算素子番号ｐを、ｐ＝０，１，．．．，Ｐ−１とつける。また、演算中間値保存回路２３から行演算素子２２Ａを経由してそれぞれの列演算素子２１に入力される入力線（枝）に、便宜的に枝番号ｂをつける。この入力線の本数は、それぞれの列演算素子ｐが演算を担当する列番号の個数の最大値ＭＡＸｐ｛｜Ｂ（ｎ）｜｝となる。よって、ｂ＝０，１，．．．，ＭＡＸｐ｛｜Ｂ（ｎ）｜｝−１として番号を振る。
【００４５】
なお、列演算素子ｐが担当する列の列重みが不均等である場合は、｜Ｂ（ｎ'）｜＜ＭＡＸｐ｛｜Ｂ（ｎ）｜｝−１となる列ｎ'を演算する時点では、演算処理を無効にして、ＦＩＦＯに保存された数値の変更を行わずに、次のＦＩＦＯへ受け渡すようにする。
【００４６】
演算素子番号ｐと枝番号ｂを用いて、演算中間値保存回路２３の複数個あるＦＩＦＯに、便宜的にＦＩＦＯ番号ｐ−ｂを割り当てるようにする。
【００４７】
図５に、演算中間値保存回路２３の詳細な構成を記す。図の表記上、列演算素子２１および行演算素子２２Ａ、２２Ｂを一つの演算素子ｐ，ｐ＝０，１，．．．，Ｐ−１としてまとめて記述した。また、ＦＩＦＯからの出力→行演算素子２２Ａ→列演算素子２１→行演算素子２２Ｂと至る経路を経路２４Ｂと記す。
【００４８】
図４において、横軸に時点（クロック）ｔ，ｔ＝０，１，．．．Ｃ−１を取り、左から右へ時間が進むものとする。また、縦軸に列演算素子２１の演算素子番号ｐ，ｐ＝０，１，．．．，Ｐ−１と、それぞれの列演算素子２１の枝番号ｂ，ｂ＝０，１，．．．，ＭＡＸｐ｛｜Ｂ（ｎ）｜｝−１を並べる。各行が、ＦＩＦＯ番号ｐ−ｂのＦＩＦＯの出力端子に対応する。縦軸には、演算中間値保存回路２３に含まれる全てのＦＩＦＯの個数だけ行が並べられている。
【００４９】
図４では、一例として、Ｎ＝６４８００、Ｍ＝３２４００、Ｐ＝４５、Ｃ＝Ｎ／４５＝１４４０の場合を記した。また、列演算素子２１の演算素子番号ｐがｐ＝０，１，．．．，８のとき枝番号ｂはＭＡＸｐ｛｜Ｂ（ｎ）｜｝＝７、列演算素子２１の演算素子番号ｐがｐ＝９，．．．，２２のとき枝番号ｂはＭＡＸｐ｛｜Ｂ（ｎ）｜｝＝３、列演算素子２１の演算素子番号ｐがｐ＝２３，．．．，４４のとき枝番号ｂはＭＡＸｐ｛｜Ｂ（ｎ）｜｝＝２、としている。なお、これらの数値は一例であり、これ以外の数値でもこの実施の形態の構成は可能である。
【００５０】
図４の四角の枠の中に記された数値は、時点ｔの時に、ＦＩＦＯｐ−ｂから出力される演算中間値の対応する行番号ｍである。例えば、時点０にて、ＦＩＦＯ０−２から出力される演算中間値は、行番号ｍ＝１４３９２に対応するものである。また、時点ｔにて、ＦＩＦＯ１３−１から出力される演算中間値も、行番号ｍ＝１４３９２に対応するものである。このように、行番号ｍに対応する演算中間値は、あるＦＩＦＯｐ−ｂから出力されて、演算素子ｐにより演算処理され、その演算結果が別のＦＩＦＯｐ'−ｂ'に入力される。なお、同一のＦＩＦＯｐ−ｂに入力される場合もあるが、そのようなものは数少ないといえる。
【００５１】
繰り返し復号演算手段２０における好適な演算順序制御、すなわち演算素子ｐおよび演算中間値行番号ｍの組み合わせ最適化の条件は、図４の各列（すなわち特定の時点ｔ）において、演算中間値の行番号ｍが最大１個のみ存在するように、行番号ｍを割り振るようにすればよい。例えば、時点０にてＦＩＦＯ０−２から出力される演算中間値の行番号ｍ＝１４３９２が、時点０に対応する列には他に存在しないようにすればよい。このような条件が、時点０からＣ−１まで成立すればよいことになる。
【００５２】
なお、行演算素子２２Ａ→列演算素子２１→行演算素子２２Ｂと流れる一連の系統での遅延クロック数ｄが０よりも大きい（遅延クロックが１回でもある）場合、時点ｔにて演算処理される行番号ｍが、時点ｔ−ｄから時点ｔ＋ｄまで存在しないように割り振る必要がある。すなわち、ある演算素子ｐにおいて演算処理されている演算中間値が、他のどの演算素子ｐ'でも処理されていないように、演算中間値の行番号ｍを割り振る必要がある。
【００５３】
以上のように記した演算順序制御の条件を、図５に当てはめて見てみる。図５の各ＦＩＦＯの枠内に記載された数字は、時点０において保存されている演算中間値の行番号ｍを表している。Ａ３と記載のＦＩＦＯの出力直前部分の保存領域に含まれる演算中間値は、時点０でＦＩＦＯから出力される演算中間値で、図４の時点０（一番左端の列）に記載の行番号ｍのものに対応する。
【００５４】
時点０で、Ｗ３と記載のＦＩＦＯ０−２の出力値は、行番号ｍ＝１４３９２に対応する演算中間値である。この演算中間値は、配線２４Ｂ、配線２５を経路Ｘ３を経由して、Ｙ３と記載のＦＩＦＯ１３−１への入力とされる。
【００５５】
このとき、時点０、その時点０より所定時間ｄだけ前のｄ時点前、およびその時点０より所定時間ｄだけ後のｄ時点後で、Ａ３と記載のＦＩＦＯの出力および配線２４Ｂで処理されている演算中間値の中で、行番号ｍ＝１４３９２に対応するものは、経路Ｗ３→Ｘ３→Ｙ３に対応する部分のみにしか存在しないということが、演算順序制御の条件となる。
【００５６】
図４の例では、時点ｔ、ＦＩＦＯｐ−ｂに対する行番号ｍに対し、時点ｔ＋１、ＦＩＦＯｐ−ｂに対する行番号ｍ'が、ｍ'＝ｍ＋ｑ，ｑ＝９０となっている。これは、例として取り上げたＬＤＰＣ符号のパリティ検査行列Ｈの構造から、このような特長を有している。この特長は、パリティ検査行列Ｈを巡回置換行列（部分行列を単位行列およびそれの列毎右シフトした行列）で構成した場合などで見られる。このような特長を有している場合、時点０においてその前後の時点で演算処理される行番号ｍが重ならないようになっていれば、時点０から時点Ｃ−１時点までで必ず重ならないようになる。つまり、時点０におけるＦＩＦＯｐ−ｂと行番号ｍを好適に割り当てれば、時点０から時点Ｃ−１までで必ず好適になっていることを意味する。
【００５７】
その場合、時点０におけるＦＩＦＯｐ−ｂと行番号ｍを好適に割り当てること、またＦＩＦＯｐ−ｂからの出力値がＦＩＦＯｐ'―ｂ'に入るというリストを作成すること、そしてＦＩＦＯｐ−ｂのそれぞれの遅延段数を定めれば、演算順序制御として必要十分になる。
【００５８】
以上のように記したことを、図５に当てはめて見てみる。時点０でのＦＩＦＯ０−２の出力値は、行番号ｍ＝１４３９２に対応するが、時点１での出力値は、行番号ｍ＝１４３９２＋９０＝１４４８２となる。このような場合、矢印Ａ３で記した、時点０における各ＦＩＦＯからの出力値に対応する行番号の好適な探索を行えばよい。条件は、時点０、その時点０より所定時間ｄだけ後のｄ時点後つまり矢印Ａ３より上の段数ｄまで、そして配線２４ＢおよびＦＩＦＯ入力側に含まれる、時点０より所定時間ｄだけ前のｄ時点前までで、演算中間値の行番号ｍに重複がないこととする。
【００５９】
また、経路Ｘ３で示される、配線２５の対応表（ＦＩＦＯ０−２→ＦＩＦＯ１３−１というような、ＦＩＦＯ出力→ＦＩＦＯ入力のそれぞれのＦＩＦＯ番号）のリストを作成すればよい。
そしてＦＩＦＯｐ−ｂのそれぞれの遅延段数は、すでに作成した行番号ｍ割り振りとＦＩＦＯ出力→ＦＩＦＯ入力リスト、そしてパリティ検査行列Ｈとから、一意に定められる。
【００６０】
ここで、演算素子ｐで演算させる列番号ｎの集合を「ブロック」と定義する。例としては、符号長Ｎ=64800に対して列番号ｎ＝0から順番に360ビットごとに区切る。この場合、ブロックの総数180＞Ｐとなるが、ブロックを4個単位でまとめた「超ブロック」を定義して（この例では総数45＝Ｐ），それぞれを演算素子ｐへ割り当てる。それぞれのブロックごとに、時点０での演算開始列が異なるようにする。時点１以降では、前の時点での演算対象列の右隣を演算するようにする。（前の時点で右端の列を演算処理した場合は、次の時点で左端の列を演算する。）また、超ブロックを採用する場合は、超ブロック内での演算順序は、例えば４クロック毎にそれぞれ異なるブロックに対応する列番号nへの演算を実施する。
【００６１】
既に述べたパリティ検査行列（巡回置換行列で構成）の性質、および前記のブロックの定義から、演算順序制御は以下に述べる手法のみで可能となる。それは、ブロックごとの演算開始列番号を定めること、条件は、「時点ｔにて演算処理される行番号ｍが、時点ｔ−ｄから時点ｔ＋ｄまでで最大1回のみとなる」こと、であるが、ｔ＝０のみ満たせば、全ての時点で満たすといえる。このブロック毎演算開始列番号を計算機探索などによって求めることにより、矢印Ａ３での行番号ｍ割り振り、ＦＩＦＯ出力→ＦＩＦＯ入力リスト、ＦＩＦＯｐ−ｂのそれぞれの遅延段数は全て一意に算出できる。
【００６２】
ちなみに、特定の行番号ｍが図４に記される回数は、Ｈｍｎ＝１となる行番号ｍの個数｜B（ｍ）｜に等しい。また、特定の行番号ｍに対応する演算中間値が通過するＦＩＦＯの段数の総計はＣとなる。
【００６３】
以上のことを図５に当てはめると、Ｗ３と記載の演算中間値は、繰り返し演算１回あたり、行重み｜B（ｍ＝１４３９２）｜＝７回分だけ、ＦＩＦＯへの入出力をされる。また、繰り返し演算１回で、Ｗ３→Ｘ３→Ｙ３→Ｚ３→・・・→Ｖ３→Ｗ３と演算中間値が鎖状に遷移していく。この遷移の遅延段数はＣとなる。
【００６４】
なお、繰り返し復号の結果として出力する、推定符号語系列ｘ'＝（ｘ'０，ｘ'１，．．．，ｘ'Ｎ−１）の算出方法は、以下の式（６）に基づく。
【００６５】
【数６】
0004739086.tif 000007
【００６６】
ここで、ｓｉｇｎ（ｘ）は、ｘ＞０の場合は１、ｘ＜０の場合は−１となる関数である。
【００６７】
なお、繰り返し復号の停止方法は、全てのパリティ検査を満足したらすぐに停止させる、最大繰り返し回数ｌmaxを固定する、それらを複合させるなどの方式がある。
【００６８】
以上のように、この発明の実施の形態１では、各演算中間値とそれを保持するための保存回路との対応を固定せず、演算の過程で逐次変動させることにより、各演算素子と演算中間値保存回路との配線およびアドレス制御を単純化することができる。
【００６９】
実施の形態２．
実施の形態１では、sum-product復号法に基づいて復号回路を構成していた。sum-product復号法の簡易演算を実施する（特に式(2)の簡易化）min-sum復号法が一般的に知られている。実施の形態２では、この回路構成特にメモリ実装方法を、min-sum復号法に対して適用する。
【００７０】
min-sum復号法では、演算中間値として保存すべき数値を、sum-product復号法に比べて少なくすることができる。例えば、演算中間値α（ｌ）ｍｎは、min-sum復号法の場合、行番号ｍの行重み｜Ａ（ｍ）｜分を保持する必要はなく、その絶対値｜α（ｌ）ｍｎ｜の小さい最小２値だけ保持していればよい。行演算素子を分割することにより、β（ｌ）ｍｎを保持する必要もなくなる。ただし、シンドローム（パリティ検査和の演算結果）の保持、およびｓｉｇｎ（β（ｌ）ｍｎ）の行重み分の保持は必要である。
【００７１】
つまり、min-sum復号法では、大半の演算中間値を行数分もしくはその２倍程度の個数だけ保持すればよいことになる。繰り返し復号演算手段２０のＦＩＦＯの各要素の容量を小さくすることができることになる。
【００７２】
しかし、min-sum復号法はsum-product復号法に比べて性能劣化が大きいという問題がある。その対処方法として、非特許文献４に記載の巡回近似MIN復号法が知られている。この技術は、演算中間値α（ｌ）ｍｎを、絶対値の小さい最小２値だけでなく、最小３値以上、行重み未満だけ保持するというものである。行重み分保持する必要がなく、メモリ量を削減することができる。なおかつmin-sum復号法に比べて性能劣化を小さくすることが出来る。
【００７３】
以上のように、この発明の実施の形態２では、各演算中間値とそれを保持するための保存回路との対応を固定せず、演算の過程で逐次変動させることにより、かつ巡回近似MIN復号法を適用することにより、各演算素子と演算中間値保存回路との配線およびアドレス制御を単純化することができ、かつメモリ量の削減を図ることができるため、繰り返し復号回路の構造をより簡易にすることができる。
【産業上の利用可能性】
【００７４】
この発明は、ディジタル伝送システムやディジタル記録システムにおける誤り訂正復号方法およびその方法を実施する誤り訂正復号装置に適用されるものである。
【図面の簡単な説明】
【００７５】
【図１】この発明の誤り訂正復号装置の繰り返し復号演算回路を示す構成図である。
【図２】この発明を実施する伝送システムの構成図である。
【図３】この発明の誤り訂正復号装置の構成図である。
【図４】この発明の誤り訂正復号方法および誤り訂正復号装置において実施される演算順序制御の好適な例を示す説明図である。
【図５】この発明の繰り返し復号演算手段について、演算中間値保存回路を特に強調して表示した構成図である。
【図６】従来の軟判定繰り返し復号回路の繰り返し復号演算回路の構成図である。
【符号の説明】
【００７６】
１０，２０；繰り返し復号演算手段、１１，２１；列演算素子、１２，２２Ａ，２２Ｂ；行演算素子、１３，２３；演算中間値保存回路、１４，１５，２４，２５；配線、１６，１７，２６，２７；経路、３１；符号化器、３２；変調器、３３；通信路、４１；復調器、４２；アナログ／ディジタル変換器、４３；復号器、５１；対数尤度比演算手段、５２；対数尤度比保存手段、５３；推定符号語系列保持手段。
【図１】
0004739086.tif 000008
【図２】
0004739086.tif 000009
【図３】
0004739086.tif 000010
【図４】
0004739086.tif 000011
【図５】
0004739086.tif 000012
【図６】
0004739086.tif 000013