(57)【特許請求の範囲】
【請求項１】
ｉを０≦ｉ≦ｎ−１として、データストリームのノイズを含む受信値ｒ（ｉ）のベクトル入力と、該符号語の符号長ｎと、Ｊ個の非ゼロ係数を有し該巡回符号に対応するパリティ検査多項式ｈ（ｘ）とを受けとる入力手段と、
ノイズを含む各該受信値ｒ（ｉ）と定数との積を求め、各積を対数ゆう度比ＬＬＲ（ｉ）として出力するスケーラと、
ｊを０≦ｊ≦Ｊ−１として、且つｉを０≦ｉ≦ｎ−１として、全メトリック数がＪ×ｎ個のπｚ（ｉ，ｊ）メトリックを受けとり、該πｚ（ｉ，ｊ）メトリックに基づいて、全メトリック数がＪ×ｎ個のλｚ（ｉ，ｊ）メトリックを計算するためのＺプロセッサと、
ｊを０≦ｊ≦Ｊ−１として、且つｉを０≦ｉ≦ｎ−１として、全メトリック数がＪ×ｎ個のλｘ（ｉ，ｊ）メトリックを受けとり、該λｘ（ｉ，ｊ）メトリックと該対数ゆう度比ＬＬＲ（ｉ）とに基づき、ｎ個の事後値ｑ（ｉ）を計算し、該λｘ（ｉ，ｊ）メトリックと該事後値ｑ（ｉ）とに基づき、全メトリック数がＪ×ｎ個のπｘ（ｉ，ｊ）メトリックを計算し、該事後値ｑ（ｉ）に基づきｎ個の推定符号ビット
【数１】
0004389373.tif 000069
を決定するためのＸプロセッサと、
該パリティ検査多項式ｈ（ｘ）の巡回シフトに基づき該πｘ（ｉ，ｊ）メトリックを分配してπｚ（ｉ，ｊ）メトリックを生成し、該πｚ（ｉ，ｊ）メトリックを該Ｚプロセッサに渡すと共に、該パリティ検査多項式ｈ（ｘ）の逆順での巡回シフトに基づき該λｚ（ｉ，ｊ）メトリックを分配してλｘ（ｉ，ｊ）メトリックを生成し、該λｘ（ｉ，ｊ）メトリックを該Ｘプロセッサに渡すための情報交換制御手段と
を有することを特徴とする、巡回符号に基づき順次複数の符号語に符号化されノイズの発生している通信路を介して送信されてきたデータストリームを推定ビットへ復号するための復号器。
【請求項２】
前記Ｘプロセッサの出力と前記Ｚプロセッサの入力とに接続されたπＲＡＭと、
該Ｚプロセッサの出力と該Ｘプロセッサの入力とに接続されたλＲＡＭと
を、更に有し、
前記情報交換制御手段は、前記入力された符号長ｎ及びパリティ検査多項式ｈ（ｘ）に基づき該πＲＡＭをＪ列ｎ行の配列に形成し、該パリティ検査多項式ｈ（ｘ）の巡回シフトに基づき前記πｘ（ｉ，ｊ）メトリックを該Ｘプロセッサから該πＲＡＭへ分配し、該πＲＡＭの各列中のＪ個のπｘ（ｉ，ｊ）メトリックを、ｎ組のπｚ（ｉ，ｊ）メトリックの内の１つとして、該Ｚプロセッサへ転送し、
該情報交換制御手段は、また、入力された該符号長ｎ及び該パリティ検査多項式ｈ（ｘ）に基づき該λＲＡＭをＪ列ｎ行の配列に形成し、該パリティ検査多項式ｈ（ｘ）の逆順での巡回シフトに基づき該λｚ（ｉ，ｊ）メトリックを該Ｚプロセッサから該λＲＡＭへ分配し、該λＲＡＭの各列内のＪ個のλｚ（ｉ，ｊ）メトリックを、ｎ組のλｘ（ｉ，ｊ）メトリックの内の１つとして、該Ｘプロセッサへ転送する
ことを特徴とする請求項１記載の復号器。
【請求項３】
該Ｚプロセッサと該Ｘプロセッサと該情報交換制御手段とを互いに接続するバスを更に有し、該Ｚプロセッサは、個別のアドレスにて該バスに接続されたｎ個のＺｉプロセッサを有し、該Ｘプロセッサは、個別のアドレスにて該バスに接続されたｎ個のＸｉプロセッサを有し、該情報交換制御手段は、該バスを介して、該Ｘｉプロセッサからの該πｘ（ｉ，ｊ）メトリックを、該パリティ検査多項式ｈ（ｘ）の該巡回シフトに基づき決定されるＺｉプロセッサへπｚ（ｉ，ｊ）メトリックとして転送し、該Ｚｉプロセッサからの該λｚ（ｉ，ｊ）メトリックを、該パリティ検査多項式ｈ（ｘ）の該逆順での巡回シフトに基づき決定されるＸｉプロセッサへλｘ（ｉ，ｊ）メトリックとして転送するためのアドレス計算手段を備えていることを特徴とする請求項１記載の復号器。
【請求項４】
該Ｚプロセッサは、
【数２】
0004389373.tif 000070
及び、ＦＱ（ｘ）を、関数Ｆ（ｘ）＝ｌｏｇ［（ｅｘ＋１）／（ｅｘ−１）］の量子化バージョンとして、
【数３】
0004389373.tif 000071
に基づき該λｚ（ｉ，ｊ）メトリックを演算することを特徴とする請求項１記載の復号器。
【請求項５】
該Ｚプロセッサは、以下に示される関数Ｆ（ｘ）＝ｌｏｇ［（ｅｘ＋１）／（ｅｘ−１）］の量子化バージョン
【数４】
0004389373.tif 000072
を用いて該λｚ（ｉ，ｊ）メトリックを演算することを特徴とする請求項２記載の復号器。
【請求項６】
該Ｘプロセッサは、
【数５】
0004389373.tif 000073
に基づき該事後値ｑ（ｉ）を計算し、πｘ（ｉ、ｊ）＝ｑ（ｉ）−λｘ（ｉ、ｊ）に基づき該πｘ（ｉ，ｊ）メトリックを計算し、
【数６】
0004389373.tif 000074
に基づきｎ個の該推定符号ビットを決定することを特徴とする請求項１記載の復号器。
【請求項７】
該スケーラが用いる定数は、４／ノイズ通信路スペクトル密度Ｎ０と等しいことを特徴とする請求項１記載の復号器。
【請求項８】
該入力手段は、更に、反復の固定した回数の入力を受けとり、該Ｘプロセッサは、該固定した回数の反復の後に、該ｎ個の推定符号ビット
【数７】
0004389373.tif 000075
を決定することを特徴とする請求項１記載の復号器。
【請求項９】
該情報交換制御手段は、該パリティ検査多項式ｈ（ｘ）にｘ０〜ｘｎ−１を順々に掛けることにより該パリティ検査多項式ｈ（ｘ）の該巡回シフトを行ない、該パリティ検査多項式ｈ（ｘ）の相反多項式（reciprocal）ｈ−１（ｘ）（ｘｎｈ（ｘ−１））にｘ０〜ｘｎ−１を順々に掛けることにより該パリティ検査多項式ｈ（ｘ）の該逆順での巡回シフトを行なうことを特徴とする請求項１記載の復号器。
【請求項１０】
該Ｘプロセッサは、第１回目の反復において、該事後値ｑ（ｉ）に対して予備的に硬判定を行ない、高信頼性位置についての硬判定値を生成し、該情報交換制御手段は、該πｘ（ｉ，ｊ）メトリックと該λｚ（ｉ，ｊ）メトリックとを分配するときに該硬判定を用いることを特徴とする請求項１記載の復号器。
【請求項１１】
該Ｚプロセッサは事後値ｑ（ｉ）がしきい値Ｔを越えているか否かに基づき、該予備的な硬判定を行なうことを特徴とする請求項１０記載の復号器。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、２元巡回符号を反復型復号するための復号器に関する。
【０００２】
【従来の技術】
巡回符号は、符号化を組織的に行なえ、且つ、符号化を帰還接続を有するシフトレジスタを用いて簡単に実施化できるという点で魅力的である。
【０００３】
反復型軟判定復号器は、デジタル受信機内の整合フィルターの出力値を用いる。この点で、整合フィルターの出力値の符号（sign）に基づくビットを用いる硬判定復号器とは異なっている。軟判定復号器の性能は、硬判定復号器に比べ、ビットにおける信号対雑音比で約２ｄＢ程度優れている。２元巡回符号用の軟判定復号器は、ビタビ・アルゴリズムを、トレリスに適用して用いる。
【０００４】
【発明が解決しようとする課題】
互いに異なる多数の２元巡回符号を復号するための単一の軟判定復号器を作成することが考えられる。しかし、このような復号器には、各巡回符号に対して異なるトレリス構造が必要である。相異なるトレリスは、それぞれ、サイズ、即ち、状態の数や枝の数が異なっており、又、異なる構造を有している。したがって、大容量のメモリや大がかりなハードウエアが必要となる。
【０００５】
単一の復号器構成にて、特定のファミリー（family）の２元巡回符号のみならずより多くのファミリーの符号をも復号することができれば望ましい。
【０００６】
本発明者は、２元（ｎ、ｋ）巡回符号をビリーフプロパゲーション（belief propagation）に基づき反復復号しても、良い結果が得られないことを発見した。このようになるのは、２元（ｎ，ｋ）巡回符号の（ｎ−ｋ）行ｎ列のパリティ検査行列が、非常に低いハミング重みを有する列、即ち、非ゼロ要素を１つしか有しないような列を有しているためであると考えられる。
【０００７】
また、簡単な構成にて良い結果が得られるように２元巡回符号をビリーフプロパゲーション（belief propagation）に基づく反復型復号を用いて復号することができる復号器を作成することが望ましい。
【０００８】
そこで、本発明は、多くの異なる巡回符号のファミリーを復号可能な復号器を提供することを目的とする。
【０００９】
また、本発明は、ビリーフプロパゲーション（belief propagation）に基づく反復型復号を用いて２元巡回符号を復号し良好な結果を得ることができる復号器を作成することを目的とする。
【００１０】
本発明による復号器は、ノイズが発生している通信路からのデータストリームを、推定ビット（estimated bits）へ復号するためのものである。なお、このデータストリームは、ノイズの発生している通信路を介して送信される前に、符号器によって、巡回符号に従い複数の符号語へと順次符号化されたものである。
【００１１】
【課題を解決するための手段】
上記目的を達成するために、本発明の復号器は、入力手段、スケーラ、Ｚプロセッサ、Ｘプロセッサ、及び、情報交換制御手段を有している。
【００１２】
入力手段は、ｉを０≦ｉ≦ｎ−１として、データストリームのノイズを含む受信値ｒ（ｉ）のベクトル入力と、該符号語の符号長ｎと、該巡回符号に対応するパリティ検査多項式ｈ（ｘ）とを受けとる。該パリティ検査多項式ｈ（ｘ）は、Ｊ個の非ゼロ係数を有している。
【００１３】
スケーラは、ノイズを含む各受信値ｒ（ｉ）と定数との積を求め、各積を対数ゆう度比ＬＬＲ（ｉ）として出力する。
【００１４】
Ｚプロセッサは、ｊを０≦ｊ≦Ｊ−１として、且つｉを０≦ｉ≦ｎ−１として、全メトリック数がＪ×ｎ個のπｚ（ｉ，ｊ）メトリックを受けとる。Ｚプロセッサは、該πｚ（ｉ，ｊ）メトリックに基づいて、全メトリック数がＪ×ｎ個のλｚ（ｉ，ｊ）メトリックを計算する。
【００１５】
Ｘプロセッサは、ｊを０≦ｊ≦Ｊ−１として、且つｉを０≦ｉ≦ｎ−１として、全メトリック数がＪ×ｎ個のλｘ（ｉ，ｊ）メトリックを受けとる。Ｘプロセッサは、該λｘ（ｉ，ｊ）メトリックと該対数ゆう度比ＬＬＲ（ｉ）とに基づき、ｎ個の事後値ｑ（ｉ）を計算する。Ｘプロセッサは、該λｘ（ｉ，ｊ）メトリックと該事後値ｑ（ｉ）とに基づき、全メトリック数がＪ×ｎ個のπｘ（ｉ，ｊ）メトリックからなるｎ組のπｘ（ｉ，ｊ）メトリックを計算する。
Ｘプロセッサは、該事後値ｑ（ｉ）に基づきｎ個の推定符号ビット
【数８】
0004389373.tif 000002
を決定する。
【００１６】
情報交換制御手段は、該パリティ検査多項式ｈ（ｘ）の巡回シフトに基づき該πｘ（ｉ，ｊ）メトリックを分配してπｚ（ｉ，ｊ）メトリックを生成し、該πｚ（ｉ，ｊ）メトリックを該Ｚプロセッサに渡す。情報交換制御手段は、該パリティ検査多項式ｈ（ｘ）の逆順での巡回シフトに基づき該λｚ（ｉ，ｊ）メトリックを分配してλｘ（ｉ，ｊ）メトリックを生成し、該λｘ（ｉ，ｊ）メトリックを該Ｘプロセッサに渡す。
【００１７】
この構成によれば、多くの異なる巡回符号のファミリーに基づく巡回符号を、同一の簡単な構成を用いて反復軟判定復号することができる。２元巡回符号は、ビリーフプロパゲーション（belief propagation）に基づき反復的に復号され、良好な結果が得られる。
【００１８】
復号器は、更に、πＲＡＭとλＲＡＭとを有していることが望ましい。πＲＡＭは、Ｘプロセッサの出力とＺプロセッサの入力とに接続されている。λＲＡＭは、Ｚプロセッサの出力とＸプロセッサの入力とに接続されている。
【００１９】
情報交換制御手段は、入力された前記符号長ｎ及び入力されたパリティ検査多項式ｈ（ｘ）に基づき、該πＲＡＭをＪ列ｎ行の配列に形成する。情報交換制御手段は、該パリティ検査多項式ｈ（ｘ）の巡回シフトに基づき前記πｘ（ｉ，ｊ）メトリックを該Ｘプロセッサから該πＲＡＭへ分配し、該πＲＡＭの各列中のＪ個のπｘ（ｉ，ｊ）メトリックを、ｎ組のπｚ（ｉ，ｊ）メトリックの内の１つとして、該Ｚプロセッサへ転送する。
【００２０】
情報交換制御手段は、また、入力された該符号長ｎ及び入力された該パリティ検査多項式ｈ（ｘ）に基づき該λＲＡＭをＪ列ｎ行の配列に形成する。情報交換制御手段は、該パリティ検査多項式ｈ（ｘ）の逆順での巡回シフトに基づき該λｚ（ｉ，ｊ）メトリックを該Ｚプロセッサから該λＲＡＭへ分配し、該λＲＡＭの各列内のＪ個のλｚ（ｉ，ｊ）メトリックを、ｎ組のλｘ（ｉ，ｊ）メトリックの内の１つとして、該Ｘプロセッサへ転送する。
【００２１】
この構成によれば、本発明による復号器を、最小限のハードウェアによりシリアルな構成として実現することができる。
【００２２】
もしくは、復号器は、ＺプロセッサとＸプロセッサと情報交換制御手段とを互いに接続するバスを更に有していることが望ましい。この場合、該Ｚプロセッサは、個別のアドレスにて該バスに接続されたｎ個のＺｉプロセッサを有し、該Ｘプロセッサは、個別のアドレスにて該バスに接続されたｎ個のＸｉプロセッサを有している。該情報交換制御手段は、該バスを介して、該Ｘｉプロセッサからの該πｘ（ｉ，ｊ）メトリックを、該パリティ検査多項式ｈ（ｘ）の該巡回シフトに基づき決定されるＺｉプロセッサへπｚ（ｉ，ｊ）メトリックとして転送し、該Ｚｉプロセッサからの該λｚ（ｉ，ｊ）メトリックを、該パリティ検査多項式ｈ（ｘ）の逆順での該巡回シフトに基づき決定されるＸｉプロセッサへλｘ（ｉ，ｊ）メトリックとして転送するためのアドレス計算手段を有している。
【００２３】
この構成によれば、本発明による復号器を、処理の速いパラレルな構成として実現できる。
【００２４】
Ｚプロセッサは、
0004389373.tif 000003
及び、
ＦＱ（ｘ）を、関数Ｆ（ｘ）＝ｌｏｇ［（ｅｘ＋１）／（ｅｘ−１）］の量子化バージョン
として、
0004389373.tif 000004
に基づき該λｚ（ｉ、ｊ）メトリックを演算することが望ましい。
【００２５】
この構成によれば、λｚ（ｉ，ｊ）メトリックを信頼性よく計算することができる。この場合、Ｚプロセッサは、以下に示される関数Ｆ（ｘ）＝ｌｏｇ［（ｅｘ＋１）／（ｅｘ−１）］の量子化バージョン
0004389373.tif 000005
を用いて該λｚ（ｉ，ｊ）メトリックを演算することが好ましい。量子化されていない場合とほとんど同一の結果が得られ、しかも、演算がずっと簡単になるからである。
【００２６】
該Ｘプロセッサは、
0004389373.tif 000006
に基づき該事後値ｑ（ｉ）を計算し、πx(i,j)=q(i)-λx(i,j)に基づき該πｘ（ｉ，ｊ）メトリックを計算し、
0004389373.tif 000007
に基づきｎ個の該推定符号ビットを決定することが好ましい。この構成によれば、事後値ｑ（ｉ）を、信頼性よく計算することができる。
【００２７】
該スケーラが用いる定数は４／ノイズ通信路スペクトル密度Ｎ０と等しいことが望ましい。この構成によれば、“０”又は“１”である確率が１又は０に近くなりすぎてしまうオーバーフローが発生するのを高い信頼性で抑えることができる。
【００２８】
該入力手段は、更に、反復の固定した回数の入力を受けとることが望ましい。この場合には、該Ｘプロセッサは、該固定した回数の反復の後に、該ｎ個の推定符号ビット
0004389373.tif 000008
を決定する。この構成によれば、復号の遅延量は固定される。この結果、データをその送り先に送るときにバッファが必要とならなくなるため、ハードウェア構成を簡単化することができる。
【００２９】
該情報交換制御手段は、該パリティ検査多項式ｈ（ｘ）にｘ０〜ｘｎ−１を順々に掛けることにより該パリティ検査多項式ｈ（ｘ）の該巡回シフトを行ない、該パリティ検査多項式ｈ（ｘ）の相反多項式（reciprocal）ｈ−１（ｘ）（ｘｎｈ（ｘ−１））にｘ０〜ｘｎ−１を順々に掛けることにより該パリティ検査多項式ｈ（ｘ）の該逆順での巡回シフトを行なうことが好ましい。この構成によれば、パリティ検査行列全体を格納する必要がなく、入力しなければならないのはパリティ検査多項式と符号長だけになる。
【００３０】
また、該Ｘプロセッサは、第１回目の反復において、該事後値ｑ（ｉ）に対して予備的に硬判定を行ない、高信頼性位置についての硬判定値を生成することが好ましい。この場合には、該情報交換制御手段は、該πｘ（ｉ，ｊ）メトリックと該λｚ（ｉ，ｊ）メトリックとを分配するときに該硬判定を用いる。この構成により、復号エラーを特に増加させることなく、復号をより容易に行うことができる。この場合、該Ｚプロセッサは事後値ｑ（ｉ）がしきい値Ｔを越えているか否かに基づき、該予備的な硬判定を行なうことが好ましい。簡単な構成にて、高信頼性位置を特定することができるからである。
【００３１】
上述した本発明の目的、特徴、及び、効果を、以下の実施の形態の記載により、添付の図面を参照しながら、明確に説明する。
【００３２】
【発明の実施の形態】
本発明の実施の形態による復号器ついて、添付の図面に基づき説明する。
【００３３】
図１は本発明の実施の形態による復号器１の機能的構成を示すブロック図である。復号器１は、入力ユニット２、スケーラ（scaler）３、Ｘプロセッサ４、情報交換制御ユニット５、及びＺプロセッサ６を有している。
【００３４】
復号器１は、ノイズの発生しているチャンネルを介して送信されてきたデータストリームの２元送信を、ｎ個の推定ビット（estimated bits）
0004389373.tif 000009
へ復号するためのものである。本実施の形態では、１シンボル当たりエネルギーＥｓを伴う２元送信（すなわち、“０”や“１”が、それぞれ
0004389373.tif 000010
として送信される）が、片側スペクトル密度（one-sided spectral density）Ｎ０を伴う加法的白色ガウスノイズ（ＡＷＧＮ）通信路上で行なわれていると仮定する。
【００３５】
データストリームは、ノイズが生ずる通信路を介して送信される前に、符号器により従来の符号化方法にて２元巡回（ｎ，ｋ）符号Ｃに基づき複数の符号語へと順次符号化される。ここで、符号器がデータストリームを巡回（ｎ，ｋ）符号Ｃにより符号化する処理について、簡単に説明する。
【００３６】
巡回（ｎ，ｋ）符号Ｃは、符号長がｎで、メッセージ（情報系列）長がｋである。巡回符号Ｃは、生成多項式ｇ（ｘ）とパリティ検査多項式ｈ（ｘ）＝（ｘｎ−１）／ｇ（ｘ）＝ｈ０＋ｈ１ｘ＋…＋ｈｋｘｋとに関連付けられている。パリティ検査多項式ｈ（ｘ）は、次の等式で示されるパリティ検査行列Ｈで表される。
【００３７】
0004389373.tif 000011
【００３８】
等式（１）のパリティ検査行列Ｈの各行には、ｊ個の非ゼロ要素が含まれている。等式（１）のパリティ検査行列Ｈのｊ番目の行内の要素は、巡回シフトｘｊｈ（ｘ）ｍｏｄ（ｘｎ−１）の係数である（ここで、ｊ＝０，１，…，ｎ−ｋ−１である）。
【００３９】
符号器は、以下のように、データストリームを組織的に符号化する。符号化されるメッセージシンボルは、次数が（ｋ−１）の情報多項式ｍ（ｘ）＝ｍ０＋ｍ１ｘ＋…＋ｍｋ−１の係数
0004389373.tif 000012
である（ここで、
0004389373.tif 000013
である）。巡回符号Ｃの符号多項式ｃ（ｘ）は、情報多項式ｍ（ｘ）に対応している。
【００４０】
まず、第１のステップでは、複数の符号シンボル
0004389373.tif 000014
が複数の係数
0004389373.tif 000015
と同一とされる（ここで、
0004389373.tif 000016
符号は巡回構造を有しているため、後続のステップでは、以下のパリティ検査の関係により、（ｎ−ｋ）冗長シンボル
0004389373.tif 000017
が再帰的に得られる（ここで、
0004389373.tif 000018
とする）。
【００４１】
0004389373.tif 000019
【００４２】
ここで、加算はＧＦ（ｑ）上で行われ、
0004389373.tif 000020
はＧＦ（ｑ）上の乗算を意味し、
0004389373.tif 000021
は、パリティ検査行列Ｈの
0004389373.tif 000022
番目の行中のｊ番目の要素（entry）を意味している。
【００４３】
上述した巡回符号Ｃを用いた組織的な符号化の例では、符号化率ｋ／ｎは０．５以下であると仮定しており、したがって、符号化は、パリティ検査多項式ｈ（ｘ）を用いて再帰的に行われる。符号化率ｋ／ｎが０．５よりも大きい巡回（ｎ，ｋ）符号に対しては、符号化は、ｘｎ−ｋｍ（ｘ）を生成多項式ｇ（ｘ）で除算することにより、より効率的に行われる。
【００４４】
パリティ検査多項式ｈ（ｘ）を用いて再帰的に行う場合でも、生成多項式ｇ（ｘ）での除算によって行う場合でも、いずれの場合も、符号多項式の係数は組織的となり、最初のｋ番目までの係数はメッセージシンボル、残りのｎ−ｋ個の係数は冗長シンボルとなる。
【００４５】
例として、ｈ（ｘ）＝１＋ｘ＋ｘ２＋ｘ４というパリティ検査多項式と以下の等式で示されるパリティ検査行列Ｈとを備えた２元巡回（７，４）ハミング符号について考える。
【００４６】
0004389373.tif 000023
【００４７】
メッセージ
0004389373.tif 000024
を符号語
0004389373.tif 000025
として符号化する際、まず、
0004389373.tif 000026
とし、次に、冗長位置を以下のように求める。
【００４８】
0004389373.tif 000027
【００４９】
この符号化の過程に関しては、符号器は、従来の２元巡回符号の符号化のための符号器と同一である。しかし、本実施の形態によれば、この符号器を有する送信機は、さらに、２元巡回（ｎ，ｋ）符号Ｃに関する情報を、例えばヘッダー中に含めて、送信する。例えば、符号と関連付けられているパリティ検査多項式ｈ（ｘ）や、符号長、パリティ検査多項式中の係数の位置を、そして、さらに、パリティ検査多項式のハミング重みＪをも任意に、例えばヘッダー中に含めて、送信する。
【００５０】
復号器１の入力ユニット２は、このように符号化されたデータストリームを、ノイズの発生している通信路の影響を受けノイズが混じった受信（軟）シンボル値ｒ（ｉ）（０≦ｉ≦ｎ−１）のベクトルとして、受信する。又、入力ユニット２には、符号語の符号長ｎや２元巡回符号Ｃのパリティ検査多項式ｈ（ｘ）の係数位置といったパラメータも入力される。入力パラメータの総数は、整数でＪ＋２、もしくは、約（Ｊ＋２）ｌｏｇ２ｎビットである。パリティ検査多項式ｈ（ｘ）はハミング重みＪを有しているので、この値Ｊが任意に入力されるようにしてもいい。入力ユニット２には、反復回数Ｎｉｔｅｒを示す固定値も入力されるようにしてもよく、このＮｉｔｅｒが反復の行われる回数を設定する。
【００５１】
入力ユニット２は、受取った値ｒ（ｉ）（ｉ∈｛０，１，…，ｎ−１｝）をスケーラ（scaler）３へ送出し、パリティ検査多項式ｈ（ｘ）を情報交換制御ユニット５へ送出する。又、図１には示されていないが、入力ユニット２は符号長ｎ及び反復回数固定値Ｎｉｔｅｒを、スケーラ３、Ｘプロセッサ４、情報交換制御ユニット５、及び、Ｚプロセッサ６に送出する。
【００５２】
スケーラ３は、入力ユニット２からノイズの混じった受信値ｒ（ｉ）と符号長ｎとを受取り、ｉ∈｛０，１，…，ｎ−１｝について、ノイズの混じった各受信値ｒ（ｉ）に、ノイズ分散Ｎ０／２（＝σ２）に反比例する定数４／Ｎ０（＝２／σ２）を掛ける。スケーラ３は、得られた積を、対応する各受信シンボルｒ（ｉ）のゆう度比（likelihood ratio）の対数（logarithm）、即ち、対数ゆう度比（log-likelihood ratio）ＬＬＲ（ｉ）として算出し出力する。このスケーラ３の動作は、次式で表される。
【００５３】
0004389373.tif 000028
【００５４】
Ｘプロセッサ４は、スケーラ３からのＬＬＲ（ｉ）と、情報交換制御ユニット５からのλｘ−メトリックとに基づき、πｘ−メトリックを算出する。Ｚプロセッサ６は、情報交換制御ユニット５からのπｚ−メトリックに基づき、λｚ−メトリックを算出する。情報交換制御ユニット５は、入力ユニット２から受取ったパリティ検査多項式ｈ（ｘ）と符号長ｎとに基づき、Ｘプロセッサ４からのπｘ−メトリックをπｚ−メトリックとしてＺプロセッサ６へと分配し、Ｚプロセッサ６からのλｚ−メトリックをλｘ−メトリックとしてＸプロセッサ４へと分配する。
【００５５】
情報交換制御ユニット５におけるメトリックの交換方法は、巡回符号Ｃの拡張パリティ検査行列Ｈｅとこれに関連づけられたターナー（Ｔａｎｎｅｒ）グラフとで表すことにより、容易に理解することができる。情報交換制御ユニット５の動作を示すパリティ検査行列は、巡回（ｎ，ｋ）符号Ｃのパリティ検査行列Ｈをｋ行拡張しｎ行ｎ列の行列をＧＦ（ｑ）上に作ることによって作成される。この行列を、以下、拡張パリティ検査行列Ｈｅという。
【００５６】
例として、２元巡回（７，４）ハミング符号の拡張パリティ検査行列Ｈｅを、以下の等式で示す。
【００５７】
0004389373.tif 000029
【００５８】
一見して分かるように、加えられた各行の要素は、パリティ検査多項式の以下の巡回シフト：ｘｎ−ｋｈ（ｘ）、ｘｎ−ｋ＋１ｈ（ｘ）、…、ｘｎ−１ｈ（ｘ）の係数である。拡張パリティ検査行列Ｈｅのｎ個の行は、ｈ（ｘ）ｍｏｄｕｌｏ（ｘｎ−１）という全ｎ個の巡回シフトの係数を要素として含んでいる。換言すれば、拡張パリティ検査行列Ｈｅの行は、ｉを１つの符号語における個々の位置を表すものとすると、連続する巡回シフトｘｉｈ（ｘ）によって生成される。
【００５９】
複数のターナーグラフ及びそれらとパリティ検査行列との関連については、よく知られており、米国特許第４，２９５，２１８号に詳述されているので、併せて参照されたい。ターナーグラフは、符号語の複数の位置を示す複数の符号点（code nodes）からなる１組の符号点と、複数のパリティ検査等式を示す複数の検査点（check nodes）からなる１組の検査点とを備えた二部グラフである。複数の符号点は、同一のパリティ検査等式に係わっている場合にのみ、同一の検査点に接続される。符号点と検査点との間の接続は、符号のパリティ検査行列内の非ゼロ要素の位置によって決定される。例えば、図２に、２元巡回（７，４）符号のターナーグラフが示されている。符号点Ｘ０〜Ｘ６と検査点Ｚ０〜Ｚ２との間の接続は、等式（２）で示されるパリティ検査行列Ｈ内の非ゼロ（即ち、１）の係数の位置によって決定される。
【００６０】
拡張パリティ検査行列Ｈｅに関連付けられたターナーグラフを、図３（ａ）、３（ｂ）、及び、図４を参照して説明する。巡回符号（０≦ｍ≦ｎ）の拡張パリティ検査行列Ｈｅに関連付けられたターナーグラフにおいて、図３（ａ）は、１つの一般的な検査点とその複数の親（parent）符号点とが接続されている様子を示しており、図３（ｂ）は、１つの一般的な符号点とその複数の子（children）検査点とが接続されている様子を示している。ここで、添え字をｍｏｄｕｌｏ  ｎとする。図４に、２元巡回（７，４）ハミング符号に対する等式（３）の拡張パリティ行列Ｈｅに関連付けられたターナーグラフを示す。
【００６１】
拡張パリティ検査行列Ｈｅに関連付けられたターナーグラフでは、特定の１つの検査点Ｚｊ（ｊ＝０，１，…，ｎ−１）とその複数の親符号点
0004389373.tif 000030
との間の接続は、
0004389373.tif 000031
で示される。拡張パリティ検査行列Ｈｅが巡回構造をしていることより、添え字をｍｏｄｕｌｏ  ｎとして、次の検査点
0004389373.tif 000032
に対する接続が
0004389373.tif 000033
で示されることが導かれる。結果として、図３（ａ）に示すように、各検査点
0004389373.tif 000034
とその複数の親符号点との一般的な接続は、以下のように示される。
【００６２】
0004389373.tif 000035
【００６３】
かかる各検査点（ｊ）とその複数の親符号点との接続は、パリティ検査多項式ｘｊｈ（ｘ）の非ゼロ係数によって特定される。換言すれば、全ての検査点から全ての符号点への接続は、パリティ検査多項式ｈ（ｘ）のｎ回の巡回シフトにおける非ゼロ係数によって特定される。
【００６４】
同様に、ある特定の符号点ｘｉとその複数の子検査点
0004389373.tif 000036
との接続は、
0004389373.tif 000037
で示される。図３（ｂ）に示すように、任意の符号点
0004389373.tif 000038
とその複数の子検査点との接続は、一般に以下のように示される。
【００６５】
0004389373.tif 000039
【００６６】
これは、拡張パリティ検査行列Ｈｅの特別な特性、つまり、全ての要素がパリティ検査多項式ｈ（ｘ）の全ての、即ち、全ｎ個の逆順での巡回シフトの係数である、という特別な特性を有していることによる。このため、任意の符号点（ｉ）からその子検査点への接続は、パリティ検査多項式ｘｉ＋ｎ−１ｈ（ｘ−１）の非ゼロ係数によって特定することができる。換言すれば、全ての符号点から全ての検査点への接続は、多項式ｘｎ−１ｈ（ｘ−１）のｎ回の巡回シフトの非ゼロ係数によって特定することができる。
【００６７】
情報交換制御ユニット５は、πｚ−メトリック，πｘ−メトリック，λｚ−メトリック，及び，λｘ−メトリックを、Ｘプロセッサ４とＺプロセッサ６との間で交換する。この交換は、拡張パリティ検査行列Ｈｅと関連付けられたターナーグラフの符号点と検査点との間で情報の交換を行うために説明される方法により行われる。ここで、Ｘプロセッサ４が複数の符号点として機能し、Ｚプロセッサ６が複数の検査点として機能する。即ち、情報交換制御ユニット５は、パリティ検査多項式ｈ（ｘ）のｎ回巡回シフトの各シフト
0004389373.tif 000040
毎に、Ｘプロセッサ４が非ゼロ要素
0004389373.tif 000041
に対し計算したπｘメトリックを取込み、それらを、対応する検査点
0004389373.tif 000042
のためのπｚメトリックとしてＺプロセッサ６に分配する。情報交換制御ユニット５は、パリティ検査多項式ｈ（ｘ）の逆順でのｎ回巡回シフトの各シフト
0004389373.tif 000043
毎に、Ｚプロセッサ６が非ゼロ要素
0004389373.tif 000044
に対し計算したλｚメトリックを取込み、それらを、対応する符号点
0004389373.tif 000045
のためのλｘメトリックとしてＸプロセッサ４に分配する。
【００６８】
情報交換制御ユニット５は、パリティ検査多項式ｈ（ｘ）にｘ０〜ｘｎ−１のうちの１つを順次掛けていくことによって、パリティ検査多項式ｈ（ｘ）のｎ回巡回シフトを決定し、パリティ検査多項式ｈ（ｘ）の相反多項式（reciprocal）ｈ−１（ｘ）（ｘｎｈ（ｘ−１））にｘ０〜ｘｎ−１のうちの１つを順次掛けていくことによって、パリティ検査多項式ｈ（ｘ）の逆順でのｎ回巡回シフトを決定する。
【００６９】
既に着目したように、２元（ｎ，ｋ）巡回符号の（ｎ−ｋ）行ｎ列パリティ検査行列は、ハミング重みが非常に小さい列、即ち、非ゼロ要素が１つだけしかない列を有している。例えば、等式（２）のパリティ検査行列Ｈの最初の列と最後の２つの列には、非ゼロ要素が１つしかない。これは、ビリーフプロパゲーション（belief propagation）に基づく反復型復号が、関連するターナーグラフでは動作しないことを意味している。
【００７０】
しかし、パリティ検査行列Ｈをｋ行拡張することによって拡張パリティ検査行列Ｈｅを作ると、列のハミング重みが大きくなる。即ち、巡回符号Ｃの拡張パリティ検査行列Ｈｅは、各列についてハミング重みｗｃを有し、各行についてハミング重みｗｒを有しており、これらは、以下に示すパリティ検査多項式ｈ（ｘ）のハミング重みｗｈに等しい。
【００７１】
ｗｈ  ＝  ｜｛ｉ；ｈｉ≠０，０≦ｉ≦ｋ｝｜、ここで、｜Ｓ｜＝集合Ｓにおける要素の数である。例えば、巡回（７，４）ハミング符号についての等式３の拡張パリティ検査行列Ｈｅでは、ハミング重みは、ｗｒ＝ｗｃ＝ｗｈ＝４となる。
【００７２】
このように列の重みが増えることは、符号のシンボルが、より多く、チェック等式中に取り込まれ、ビリーフプロパゲーション（belief propagation）に基づく反復型復号がより良好に動作することを意味する。
【００７３】
加えて、拡張パリティ検査行列Ｈｅ中の拡張されたｋ行は、最初のｎ−ｋ上に対して線形に従属しており、符号の次元は同一のままである。即ち、パリティ検査行列の密度を増加させることなく、列のハミング重みが増加している。ここで、パリティ検査行列の密度とは、非ゼロ要素の数を要素の総数で割った値をいい、低密度のパリティ検査行列を備える符号に対してはビリーフプロパゲーション（belief propagation）に基づく反復型復号がよりよく動作することが知られている。このように、密度を増加させることなく列の重みが増加するため、ビリーフプロパゲーション（belief propagation）に基づく反復型復号は、拡張パリティ検査行列Ｈｅに関連付けられたターナーグラフ上の方が、パリティ検査行列Ｈに関連付けられたＴａｎｎｎｅｒグラフ上よりも良好に動作することになる。
【００７４】
復号器１の動作についてより詳細に説明する。先ず、情報交換制御ユニット５は、ｉ∈｛０，１，…，ｎ−１｝、ｊ∈｛０，１，…，Ｊ−１｝について、メトリックπｘ（ｉ，ｊ）を、スケーラ３からのＬＬＲ（ｉ）の値に初期化し、メトリックλｚ（ｉ，ｊ）を０に初期化する。そして、ｉ∈｛０，１，…，ｎ−１｝について、情報交換制御ユニット５は、情報交換の際転送先の点を決定するのに用いられることになるインデックスの組Ｉｘ（ｉ），Ｉｚ（ｉ）を、０に初期化する。
【００７５】
次に、情報交換制御ユニット５は、ｉ∈｛０，１，…，ｎ−１｝について、以下の方法により、メトリックを伝搬してゆく。図１には示されていないが、情報交換ユニット５は、π−メトリックを保持するための検査点メモリとλ−メトリックを保持するための符号点メモリーとを有している。
【００７６】
Ｘ（符号点）からＺ（検査点）への伝搬に対しては、情報交換制御ユニット５は、ｊ∈｛０，１，…，Ｊ−１｝に対し、検査点メモリー内に、π−メトリックを、πｚ（Ｐｘ（ｉ，ｊ），Ｉｘ（Ｐｘ（ｉ，ｊ）））  ＝  πｘ（ｉ，ｊ）、Ｉｘ（Ｐｘ（ｉ，ｊ））  ＝  Ｉｘ（Ｐｘ（ｉ，ｊ））＋１となるように、格納する。ここで、Ｐｘ（ｉ，ｊ）は、符号点ｘｉから検査点Ｐｘ（ｉ，ｊ）へのリンクを表す整数である。
【００７７】
Ｐｘ（ｉ，ｊ）は、パリティ検査多項式ｈ（ｘ）の（右側への）ｉ番目の巡回シフトを表している。ｊの値は、パリティ検査多項式の非ゼロ係数を示すインデックスとして機能し、したがって、１つの符号点ｉと１つの検査点との間の接続を決定する。各符号点はＪ個の検査点に接続されており、したがって、ｊの値は０からＪ−１までの範囲の値を採る。拡張パリティ検査行列Ｈｅで考えれば、等価的に、ｉは行を示すインデックスであり、ｊはその行におけるｊ番目の非ゼロ要素を示すインデックスである。各符号点ｉに対して、Ｐｘ（ｉ，ｊ）の値は０からｎ−１までの範囲を採り、Ｐｘ（ｉ，ｊ）の値は検査点を示すのに用いられる。
【００７８】
Ｚ（検査点）からＹ（符号点）への伝搬においては、情報交換制御ユニット５は、ｊ∈｛０，１，…，Ｊ−１｝に対し、λ−メトリックを、符号点メモリー内に、λｘ（Ｐｚ（ｉ，ｊ），Ｉｚ（Ｐｚ（ｉ，ｊ）））  ＝  λｚ（ｉ，ｊ）、Ｉｚ（Ｐｚ（ｉ，ｊ））  ＝  Ｉｚ（Ｐｚ（ｉ，ｊ））＋１となるように、格納する。ここで、Ｐｚ（ｉ，ｊ）は、検査点ｚｉから符号点Ｐｚ（ｉ，ｊ）へのリンクを表す整数である。
【００７９】
Ｐｚ（ｉ，ｊ）の値は、Ｐｘ（ｉ，ｊ）の値と同様に定義される。すなわち、Ｐｚ（ｉ，ｊ）の値は、１つの検査点ｉとこれに接続されたＪ個の符号点との接続を決定する役割を果たす。拡張パリティ検査行列Ｈｅで考えれば、ｉは列のインデックスであり、ｊは、ｊ番目の非ゼロ要素のインデックスである。
【００８０】
結果として、Ｚプロセッサ６は、０≦ｊ≦Ｊ−１について、各組にＪ個のメトリックπｚ（ｉ，ｊ）
0004389373.tif 000046
を含むｎ組のメトリックπｚ（ｉ，ｊ）を、情報交換制御ユニット５から受け取る。Ｚプロセッサ６は、このメトリックπｚ（ｉ，Ｊ）に基づき、各組にＪ個のメトリックλｚ（ｉ，ｊ）
0004389373.tif 000047
を含むｎ組のメトリックλｚ（ｉ，ｊ）を計算する。
【００８１】
Ｚプロセッサ６は、以下の式に基づき、各ｉ∈｛０，１，…，ｎ−１｝について、メトリックλｚ（ｉ，ｊ）を演算する。
【００８２】
0004389373.tif 000048
【００８３】
ここで、
ｘ＜０のときｓｇｎ（ｘ）＝１、  ｘ≧０のときｓｇｎ（ｘ）＝０であり、
｜ｘ｜は、ｘの絶対値（又は、大きさ）であり、
0004389373.tif 000049
また、
ＦＱ（ｘ）は、
0004389373.tif 000050
の量子化バージョンである。
【００８４】
ここで、復号器１は、Ｚプロセッサ６が以下に示される量子化バージョンＦＱ（ｘ）を用いてメトリックλｚ（ｉ，ｊ）の計算を行うことにより、量子化を行わない場合と実用上同等のエラーパフォーマンスを達成することができ、しかも、処理がずっと簡単になる。図５は、関数Ｆ（ｘ）を、量子化バージョンＦＱ（ｘ）と比較して示している。
【００８５】
0004389373.tif 000051
【００８６】
Ｘプロセッサ４は、スケーラ３から複数の対数ゆう度比ＬＬＲ（ｉ）を受け取り、これらと、情報交換制御ユニット５からのλｘ（ｉ，ｊ）メトリック
0004389373.tif 000052
とを用いて、各ｉ∈｛０，１，…，ｎ−１｝について、メトリックπｘ（ｉ，ｊ）
0004389373.tif 000053
とｎ個の推定符号ビット
0004389373.tif 000054
とを演算する。Ｘプロセッサは、入力ユニット２から受け取った固定値の回数だけ反復を行った後、ｎ個の推定符号ビット
0004389373.tif 000055
を決定する。
【００８７】
図６に示されるように、Ｘプロセッサ４は、事後値（a-posteriori values）ｑ（ｉ）計算器１０と、メトリックπｘ（ｉ，ｊ）計算器１１と、推定符号ビット
0004389373.tif 000056
決定器１２とを有している。事後値（a-posteriori values）ｑ（ｉ）計算器１０は、各組にＪ個のメトリックλｘ（ｉ，ｊ）を含むｎ組のメトリックλｘ（ｉ，ｊ）を、情報交換制御ユニット５から受け取る。そして、符号シンボル（「軟出力」）の事後対数ゆう度比（a-posteriori log-likelihood ratio）である、ｎ個の事後値（a-posteriori values）ｑ（ｉ）を計算する。事後値（a-posteriori values）ｑ（ｉ）計算器１０は、メトリックλｘ（ｉ，ｊ）、及び、スケーラ３から送られてきた対数ゆう度比（log-likelihood ratios）ＬＬＲ（ｉ）に基づき、事後値（a-posteriori values）ｑ（ｉ）を、以下の式で、計算する。
【００８８】
0004389373.tif 000057
【００８９】
πｘ（ｉ，ｊ）メトリック計算器１１は、メトリックλｘ（ｉ，ｊ）及び事後値（a-posteriori values）ｑ（ｉ）に基づき、各組にＪ個のメトリックπｘ（ｉ，ｊ）を含むｎ組のメトリックπｘ（ｉ，ｊ）を計算する。特に、πｘ（ｉ，ｊ）メトリック計算器１１は、以下の式に基づき、メトリックπｘ（ｉ，ｊ）を計算する。
【００９０】
0004389373.tif 000058
【００９１】
固定回数Ｎｉｔｅｒだけ、Ｘ、Ｙプロセッサ４、６はメトリックを計算し、情報交換制御ユニット５はこれらメトリックを分配する。反復の回数が固定されているため、復号遅延量は一定となる。このため、データを一定のレートで送り先（又は、情報源復号器）に伝達する場合には、バッファが必要にならず、ハードウエアの実施化を容易にすることができる。もしくは、入力した固定値に依る代わりに、反復回数が最大値に達したときに反復を停止するようにしてもよい。しかしながら、この場合には、復号遅延量は可変となり、また、停止させるための何らかのルールが必要となる。
【００９２】
一旦、所定回数の反復が完了すると、推定符号ビット
0004389373.tif 000059
決定器１２が、ｉ∈｛０，１，…，ｎ−１｝について、事後値（a-posteriori values）ｑ（ｉ）計算器１０からの事後値（a-posteriori values）ｑ（ｉ）に基づき、ｎ個の推定符号ビット
0004389373.tif 000060
を決定する。特に、推定符号ビット
0004389373.tif 000061
決定器１２は、以下の式に基づき、ＬＬＲの符号（sign）ビットとしてｎ個の推定符号ビットを決定する。
【００９３】
0004389373.tif 000062
【００９４】
図７には、（７，４）ハミング符号を４回の反復により復号したシミュレーション結果が示されている。ここでは、復号が復号器１のＨｅで示される方法によって行われた場合を、パリティ検査行列Ｈに関連付けられたターナーグラフによって表される方法により行われた場合と比較して示されている。また、図７には、参考として、この符号の最ゆう復号（ＭＬＤ）によるビットエラーレートにおけるユニオンバウンド（union bound）（ＵＢ）も示されている。
【００９５】
図８〜図１０には、２元巡回符号を復号器１の方法により復号したコンピュータシミュレーション結果が示されている。これらすべての場合において、メトリックは、パリティ検査多項式の巡回シフト、及び、逆順での巡回シフトに基づき分配された。対数ゆう度比、及び、浮動小数点精度を用いたパールアルゴリズム（Pearl’s algorithm）に基づく反復型復号を、Ｃプログラムによって実行した。
【００９６】
図８には、２元ＢＣＨ（１５，１１）符号のシミュレーション結果が示されており、図９には、２元ＢＣＨ（１５，７，５）符号のシミュレーション結果が示されており、図１０には、２元ＢＣＨ（１５，５，７）符号のシミュレーション結果が示されている。参考として、符号の重み分布に基づく最ゆう復号（ＭＬＤ）によって得られたビットエラーレートにおけるユニオンバウンド（union bound）が、これらの符号に対して示されている。
【００９７】
図１１には、２元（２７３，１９１）差集合（difference-set）（ＤＳ）符号を反復型復号したシミュレーション結果が示されている。これは、「有限幾何（Finite Geometries）に基づく低密度パリティ検査符号：再発見及び更なる発見」と題され、１９９９年１１月にハワイのホノルルで行われたＡＥＣＣ−１３会議において発表されたプレゼンテーションにおいて、Kouらによって導びき出された２元射影幾何（projective geometry）（ＰＧ）符号である。２元（２７３，１９１）差集合（difference-set）（ＤＳ）符号は、未知の重み分布を有しており、したがって、ユニオンバウンド（union bound）は図１１にはプロットされていない。
【００９８】
図８から図１１までに示される結果を比較すると、図１０のＢＣＨ（１５，５，７）符号についての反復動作は、非常にゆっくり収斂していることが分かる。他の巡回符号まで広範囲にシミュレーションした結果、高いレートの符号については、反復型復号は最ゆう復号へと非常に速く、すなわち、少ない回数の反復で、収斂するが、中程度から低いレートの符号については、反復型復号は多くの場合非常にゆっくりと収斂することが分かった。
【００９９】
次に、本実施の形態によるビリーフプロパゲーション（belief propagation）に基づく反復型復号器１についての構成例を、図１２乃至図１８に基づき説明する。図１２には、第１の実施例によるシリアル復号器１０が示されている。復号器１０は、スケーラ３０と、ＬＬＲバッファ３５と、Ｘプロセッサ４０と、バッファ４５と、Ｘ−ｔｏ−Ｚ伝搬ユニット５０Ａと、Ｚプロセッサ６０と、Ｚ−ｔｏ−Ｘ伝搬ユニット５０Ｂとを有している。図１３には、Ｘプロセッサ４０の構成の詳細が示されており、図１４には、Ｚプロセッサ６０の構成の詳細が示されている。
【０１００】
Ｘ−ｔｏ−Ｚ伝搬ユニット５０Ａは、πＲＡＭ制御器５１及びπＲＡＭ５２を有している。πＲＡＭ制御器５１はＸ−ｔｏ−Ｚアドレス発生器５１ａを有している。本実施の形態では、Ｘ−ｔｏ−Ｚアドレス発生器５１ａは、図１５（ａ）に示されるような循環バッファである。
【０１０１】
Ｚ−ｔｏ−Ｘ伝搬ユニット５０Ｂは、λＲＡＭ制御器５３及びλＲＡＭ５４を有している。λＲＡＭ制御器５３はＺ−ｔｏ−Ｘアドレス発生器５３ａを有している。本実施の形態では、Ｚ−ｔｏ−Ｘアドレス発生器５３ａは、図１５（ｂ）に示されるような循環バッファである。
【０１０２】
次に、シリアル復号器１０の動作の一例を示す。この例では、復号器１０は、ノイズの発生している通信路より、２元巡回（７，４）ハミング符号により符号化されたデータストリーム、即ち、パリティ検査行列Ｈを用いて符号化されたデータストリームを受信する。従って、復号器１０は、ノイズを含む受信値ｒ０…ｒ６のベクトルを受信し、そして、符号長７とパリティ検査多項式ｈ（ｘ）＝１＋ｘ＋ｘ２＋ｘ４との入力も受けとる。ノイズを含む受信値ｒ０…ｒ６はスケーラ３０に入力され、パリティ検査多項式ｈ（ｘ）＝１＋ｘ＋ｘ２＋ｘ４は、Ｘ−ｔｏ−Ｚ伝搬ユニット５０ＡとＺ−ｔｏ−Ｘ伝搬ユニット５０Ｂとに入力される。符号長７は全ての構成要素に入力される。
【０１０３】
パリティ検査多項式ｈ（ｘ）は４つ（Ｊ＝４）の非ゼロ係数を有しており、また、符号長は７（ｎ＝７）であるため、初期化を行っているときには、πＲＡＭ５２とλＲＡＭ５４とは、それぞれπＲＡＭ制御器５１とλＲＡＭ制御器５３によって、４列７行のアレイに組織化される。
【０１０４】
スケーラ３０は、ノイズを含む受信値ｒ０…ｒ６のそれぞれに、定数４／Ｎｏ（＝２／σ２）を掛け、対数ゆう度比ＬＬＲ（０）−ＬＬＲ（６）（ＬＬＲ（ｉ）、ここでｉ＝０，…，６である）を得る。対数ゆう度比ＬＬＲ（０）−ＬＬＲ（６）は、ＬＬＲバッファ３５内に格納される。
【０１０５】
次に、πＲＡＭ制御器５１内の全てのメトリックπｘ（ｉ，ｊ）が、ＬＬＲ（ｉ）へと初期化される。例えば、ｉ＝０のとき、４つのメトリックπｘ（０，ｊ：ｊ＝０〜３とする）はＬＬＲ（０）に初期化される。λＲＡＭ制御器５３内の全てのメトリックλｚ（ｉ，ｊ）（ここでｉ＝０〜７，ｊ＝０〜３）は、０へと初期化される。
【０１０６】
初期化の後、図１５（ａ）の一番上に示されているように、πＲＡＭ制御器５１のＸ−ｔｏ−Ｚアドレス発生器５１ａが、パリティ検査多項式ｈ（ｘ）＝１＋ｘ＋ｘ２＋ｘ４に対応するπＲＡＭ５２中のアドレスを発生する。πＲＡＭ制御器５１は、これらのアドレスに従い、πＲＡＭ５２中に、メトリックπｘ（０，ｊ）−πｘ（６，ｊ）（すなわち、ＬＬＲ（０）−ＬＬＲ（６））を分配する。即ち、πＲＡＭ５２の第１の列（ｉ＝０）は、パリティ検査多項式ｈ（ｘ）＝１＋ｘ＋ｘ２＋ｘ４に対応しており、このため、等式（３）の拡張パリティ検査行列Ｈｅの第１行に対応している。非ゼロ係数は、等式（３）の拡張パリティ検査行列Ｈｅの第１行中の、ｉ＝０，１，２，４の位置にある。従って、πＲＡＭ制御器５１は、０〜３の値を採るインデックスＩに関連付けながら、πＲＡＭ５２の第１列に、メトリックπｘ（０，０）、πｘ（１，０）、πｘ（２，０）、πｘ（４，０）を、この順番で格納する。
【０１０７】
次に、図１５（ａ）の第２番目に示されるように、Ｘ−ｔｏ−Ｚアドレス発生器５１ａは、パリティ検査多項式ｘｈ（ｘ）に対応するπＲＡＭ５２へのアドレスを発生する。πＲＡＭ５２の第２列（ｉ＝１）は、パリティ検査多項式ｘｈ（ｘ）に対応しており、等式（３）の拡張パリティ検査行列Ｈｅの第２行によって表されるからである。非ゼロ係数は、等式（３）の拡張パリティ検査行列Ｈｅの第２行中には、ｉ＝１，２，３及び５の位置にある。即ち、非ゼロ係数の位置は、第１行目の位置に対して巡回的にシフトされている。従って、πＲＡＭ制御器５１は、０〜３の値を採るインデックスＩに関連付けながら、πＲＡＭ５２の第２列目に、メトリックπｘ（１，１）、πｘ（２，１）、πｘ（３，０）、πｘ（５，０）をこの順で格納する。
【０１０８】
Ｘ−ｔｏ−Ｚアドレス発生器５１ａが、図１５（ａ）に示されるように、パリティ検査多項式ｈ（ｘ）における巡回シフトによりアドレスを発生している間に、πＲＡＭ制御器５１は、上述の第１、２列に対して行った方法と同一の方法によって、πＲＡＭ５２の第３列から第６列（ｉ＝２〜６）に対してメトリックπｘ（ｉ，ｊ）を分配する。図１５（ａ）に示されるＸ−ｔｏ−Ｚアドレス発生器５１ａの動作は、Ｐｘ（ｉ，ｊ）の値の変化に対応している。この結果、図１６に示されるように、πＲＡＭの４行７列のアレイ中にメトリックπｘ（ｉ，ｊ）が格納される。その後、πＲＡＭ５２中のメトリックπｘ（ｉ，ｊ）は、メトリックπｚ（ｉ，ｊ）としてＺプロセッサ６０に送られる。一例として、図１６中のπＲＡＭ５４の第１列（即ち、ｉ＝０）を用いると、メトリックπｘ（０，０）、πｘ（１，０）、πｘ（２，０）、πｘ（４，０）が、メトリックπｚ（０，０）、πｚ（０，１）、πｚ（０，２）、πｚ（０，３）としてＸプロセッサ４０へ送られる。
【０１０９】
次に、Ｚプロセッサ６０は、πＲＡＭ５２のｉ番目の列で、且つｊ番目の行にある値（ｉ，ｊ）をπｚ（ｉ，ｊ：ここで、ｉ＝０〜６、ｊ＝０〜３）として用い、等式（４）を用いてλｚ（ｉ，ｊ）を演算する。例えば、Ｚプロセッサ６０は、πＲＡＭ５２の第１列ｉ＝０中の４つの値をπｚ（０，ｊ：ここでｊ＝０〜３）として用いて、λｚ（０，０）、λｚ（０，１）、λｚ（０，２）、λｚ（０，３）を計算する。
【０１１０】
図１５（ｂ）の一番上に示されているように、λＲＡＭ制御器５３のＺ−ｔｏ−Ｘアドレス発生器５３ａは、パリティ検査多項式ｘ７ｈ（ｘ−１）に対応するλＲＡＭ５４内のアドレスを発生する。λＲＡＭ制御器５３は、これらのアドレスに従いλＲＡＭ５４中にλｚメトリック（ｉ，ｊ）（ここで、ｉ＝０〜６、ｊ＝０〜３）を格納する。即ち、λＲＡＭ５４の第１列（ｉ＝０）は、パリティ検査多項式ｘ７ｈ（ｘ−１）に対応しており、従って、等式（３）の拡張パリティ検査行列Ｈｅの第１列に対応している。非ゼロ係数は、等式（３）の拡張パリティ検査行列Ｈｅの第１列中の、ｉ＝０，３，５及び６の位置にある。従って、λＲＡＭ制御器５３は、０〜３の値を採るインデックスＩに関連付けながら、λＲＡＭ５４中の第１列目に、メトリックλｘ（０，０）、λｘ（３，０）、λｘ（５，０）、λｘ（６，０）をこの順で格納する。
【０１１１】
次に、図１５（ｂ）の第２番目に示されるように、Ｘ−ｔｏ−Ｚアドレス発生器５３ａは、パリティ検査多項式ｘ８ｈ（ｘ−１）に対応するλＲＡＭ５４へのアドレスを発生する。λＲＡＭ５４の第２列（ｉ＝１）は、パリティ検査多項式ｘ８ｈ（ｘ−１）に対応しており、等式（３）の拡張パリティ検査行列Ｈｅの第２列によって表されるからである。非ゼロ係数は、等式（３）の拡張パリティ検査行列Ｈｅの第２列中の、ｉ＝０，１，４及び６の位置にある。即ち、非ゼロ係数の位置は、等式（３）の拡張パリティ検査行列Ｈｅの第１列目の位置から巡回的にシフトしている。従って、λＲＡＭ制御器５３は、０〜３の値を採るインデックスＩに関連付けながら、λＲＡＭ５４の第２列目にメトリックλｘ（０，１）、λｘ（１，０）、λｘ（４，０）、λｘ（６，１）をこの順で各々格納する。
【０１１２】
Ｚ−ｔｏ−Ｘアドレス発生器５３ａが、図１５（ｂ）に示されるように、パリティ検査多項式ｘ７ｈ（ｘ−１）における巡回シフトによりアドレスを発生している間に、λＲＡＭ制御器５３は、上述の第１、２列に対して行った方法と同一の方法によって、λＲＡＭ５４の残りの第３列から第６列（ｉ＝２〜６）に対してメトリックλｚ（ｉ，ｊ）を分配する。図１５（ｂ）に示されるＺ−ｔｏ−Ｘアドレス発生器５３ａの動作は、Ｐｚ（ｉ，ｊ）の値の変化に対応している。この結果、図１７に示されるように、λＲＡＭ５４の４行７列のアレイにメトリックλｚ（ｉ，ｊ）が格納される。その後、λＲＡＭ５４中のメトリックλｚ（ｉ，ｊ）は、メトリックλｘ（ｉ，ｊ）としてＸプロセッサ４０に送られる。一例として、図１７中のλＲＡＭ５４の第１列（即ち、ｉ＝０）を用いると、メトリックλｚ（０，０）、λｚ（３，０）、λｚ（５，０）、λｚ（６，０）は、メトリックλｘ（０，０）、λｘ（０，１）、λｘ（０，２）、λｘ（０，３）としてＸプロセッサ４０へ送られる。
【０１１３】
復号器１０は、以下の方法に従い、反復の過程において第２のステップ、及び更に続く反復のステップを行う。Ｘプロセッサ４０は、λＲＡＭ５４中のｉ列、ｊ行の値を、メトリックλｘ（ｉ，ｊ）（ここでｉ＝０〜６，ｊ＝０〜３）として用い、等式（６）を用いて事後的値（a-posteriori values）ｑ（ｉ）を演算し、又、等式（７）を用いてメトリックπｘ（ｉ，ｊ）を演算する。例えば、Ｘプロセッサ４０は、λＲＡＭ５４中の第１列ｎ＝０の４つの値を、λｘ（０，ｊ）（ここで、ｊ＝０〜３）として用いて、事後的値（a-posteriori values）ｑ（０）を計算し、メトリックπｘ（０，ｊ）を計算する。Ｘ−ｔｏ−Ｚ伝搬ユニット５０Ａ、Ｚプロセッサ６０、Ｚ−ｔｏ−Ｘ伝搬ユニット５０Ｂは、全て、上述した第１の反復のステップと同一の処理を行う。
【０１１４】
反復が固定の反復回数Ｎｉｔｅｒ回行われた後、Ｘプロセッサ４０は、等式（８）に基づき、推定符号ビットｃｉ（ｉ＝０〜６とする）を決定し、これらを出力のためにバッファ４５に格納する。Ｘプロセッサ４０は、軟出力値（soft output values）ｑ（ｉ）をも、出力のためにバッファ４５中に格納する。軟出力値は、復号化されたビットの信頼性を表す。即ち、ｑ（ｉ）の絶対値が大きくなればなるほど、ビットの信頼性は高くなる。ｑ（ｉ）の値は、復号器の図示せぬ復調器へのフィードバック情報内で用いられる。
【０１１５】
図１８には、第２の実施例によるパラレル復号器１００が示されている。復号器１００は、ｎ個のＸプロセッサ４０００〜４００ｎ−１と、ｎ個のＺプロセッサ６０００〜６００ｎ−１と、アドレス計算ユニット（ＡＣＵ）５００とを有しており、これらは全てλバス５０３とπバス５０４とに接続されている。レジスタ５０５０〜５０５ｎ−１が設けられており、それぞれが、Ｘプロセッサ４０００〜４００ｎ−１の各々と接続されている。レジスタ５０５０〜５０５ｎ−１は、シリアル復号器１０のλＲＡＭ５４の複数の異なる列に対応している。同様に、レジスタ５０６０〜５０６ｎ−１が設けられており、それぞれが、Ｚプロセッサ６０００〜６００ｎ−１の各々と接続されている。レジスタ５０６０〜５０６ｎ−１は、シリアル復号器１０のπＲＡＭ５２の複数の異なる列に対応している。ＡＣＵ５００はＸ−ｔｏ−Ｚアドレス発生器５０１とＺ−ｔｏ−Ｘアドレス発生器５０２とを有しており、これらの機能は、基本的には、それぞれ、第１の実施例によるＸ−ｔｏ−Ｚアドレス発生器５１ａと、第１の実施例によるＺ−ｔｏ−Ｘアドレス発生器５３ａと同一である。Ｘプロセッサ、Ｚプロセッサの各々が、入力されたパリティ検査多項式のＮ回巡回シフトによって作られる拡張パリティ検査行列Ｈｅに関連付けられたターナーグラフ中の複数の点の１つに対応していること、及び、ＡＣＵ５００によって決定された点間で接続がなされることが、容易に理解できる。
【０１１６】
シリアル復号器１０は、パラレル復号器１００よりも簡単なハードウェア構成とすることができるが、パラレル復号器１００の方がシリアル復号器１０よりも速い。表１には、これらの２つの実施例による構成のパラメータの幾つかが、まとめられている。
【０１１７】
【表１】
0004389373.tif 000063
【０１１８】
表１において、Ｎｑは、メトリックに用いられる量子化ビットの数を表している。必要なメモリー素子の数を決定する際には、復号器中の全てのメトリック、即ち、通信路からの事前ＬＬＲ（a-priori LLR）、事後ＬＬＲ  ｑ（ｉ）、及びπ、λメトリックが、全て同一のビット数で表されていると仮定する。
【０１１９】
次に、本実施の形態の変形例について説明する。本変形例では、入来した通信路シンボルの事後対数ゆう度比ｑ（ｉ）に基づき予備的な硬判定がなされる。硬判定の値は、復号の過程を通して固定されたままとなる。このため、復号器のエラー量の重大な増加を起こさせることなく、複雑な処理を減じて、復号器の短時間当たりの情報処理量を増加させることができる。
【０１２０】
ここで、ＡＷＧＮ通信路における２元送信を仮定する。このとき、受信されたシンボルはｒｉ＝ｓｇｎ（ｒｉ）｜ｒｉ｜で与えられる。シンボルｒｉの信頼性は、その大きさ
0004389373.tif 000064
で定義することができる。本変形例によれば、信頼性が所定のしきい値Ｔを超える、即ち、ｒｅｌｉ＞Ｔである受信シンボルは、信頼性が高いと判断され、そのシンボルに関連付けられた符号点が、高信頼性位置（highly reliable position）（ＨＲＰ）として選択される。硬判定は、高信頼性があると判断された受信シンボルに対して行われる。シンボルｒｉの硬判定は
0004389373.tif 000065
で定義される。
【０１２１】
高信頼性位置（符号点）の集合が選択され、対応する受信シンボルがそれらの硬判定（ＨＤ）値に固定されると、メトリックπｘ（ｉ，ｊ）（０≦ｊ≦ｊ−１）の最大絶対値｜πＭＡＸ｜が、推定符号ビット
0004389373.tif 000066
としての受信通信路値の符号と共に、符号点構成（即ち、Ｘプロセッサ６）から出力される。換言すれば、高信頼性位置の符号点に関連付けられた構成は、復号処理では用いられない。この結果、入力値の内の幾つかが高信頼性であると推定できるため、検査点構成（即ち、Ｚプロセッサ６）は、Ｆ（｜｜）の値を足し合わせて総数Ｓを計算するときに、より少ない加算演算を行うだけで済む。これは、Ｆ（ｘ）の定義から、Ｆ（｜πＭＡＸ｜）＝０が得られるからである。実用化にあたっては、量子化された関数を用い、値ＦＱ（｜πＭＡＸ｜）＝０．１をＨＲＰに対して固定して反復過程全体を通して用いる。
【０１２２】
検査点構成（即ち、Ｚプロセッサ  ６）は、符号点構成（即ち、Ｘプロセッサ４）に対する入力用として、高信頼性位置に関連付けられたメトリックを計算する必要がないため、メッセージの伝達及びメトリックの計算を行うにあたり、より少ない計算を行えばよいことになる。メッセージの伝達については、高信頼性位置に関する符号点構成用のメトリックλｘが固定されているため、メトリックλｚを対応する検査点構成から伝達する必要がない。メトリックの演算については、符号点構成における高信頼性位置の高信頼性の故に、検査点構成におけるλメトリックの演算にこれらのπメトリックを含ませないで済む。等式（４）、（５）のλメトリックの計算においては、代わりに、高信頼性位置に対してはＦＱ（Ｘ）の最小値が常に用いられる。
【０１２３】
結果として、高信頼性位置についてのメッセージ伝達やメトリック演算に関する動作を大幅に減らすことができる。このことは、通信路の状況が良好であるとき、即ち、ノイズ出力レベルＮ０が低いときには、特に顕著である。メッセージの伝達においては、符号点構成用のＸからＺへの伝搬については同一のままである。しかしながら、前述のように、高信頼性位置においては、検査点構成から符号点構成へのＺからＸへの伝搬が必要ではなくなる。これらの値は、予め決定されているからである。このステップは、ｉ＝０，１，…，ｎ−１について、ｊ∈｛０，１，…，ｊ−１｝及び
0004389373.tif 000067
に対して、λメトリックが符号点メモリー中に次のように格納されるように、変更される。
【０１２４】
λｘ（Ｐｚ（ｉ，ｊ），Ｉｚ（Ｐｚ（ｉ，ｊ）））＝λｚ（ｉ，ｊ），Ｉｚ（Ｐｚ（ｉ，ｊ））＝Ｉｚ（Ｐｚ（ｉ，ｊ））＋１
【０１２５】
ここで、Ｌは高信頼性位置のインデックスの集合である。
【０１２６】
図１７の例を用いると、ｎ＝０が高信頼性位置として特定されるときには、Ｘプロセッサ４０へは、メトリックλｚ（０，０）、λｚ（３，０）、λｚ（５，０）、及び、λｚ（６，０）がメトリックλｘ（０，０）、λｘ（０，１）、λｘ（０，２）、及び、λｘ（０，３）として送られることはない。
【０１２７】
図１９は、高信頼性位置を示すための複数の異なるしきい値Ｔが、４回反復を行う２元ＢＣＨ（１５，７，５）符号の反復型復号のエラーパフォーマンスにどのように影響を及ぼすかを示している。比較例として、公知のバーレカンプ・マッシー（ｂｍ）アルゴリズムを用いた硬判定復号によるビットエラーレートと、ユニオンバウンド（union bound）（ＵＢ）とがそれぞれ示されている。しきい値Ｔ＝１．０は、高信頼性位置を用いない反復型復号のパフォーマンスよりたった０．１７ｄＢしか離れていない１０−４というビットエラーレートを得ており、優れたパフォーマンスを得ていることが分かる。換言すれば、平均５０％の位置において高い信頼性位置を設定することができ、それでもなお優れたパフォーマンスを達成している。更に、しきい値ＴがＴ＝１．５の場合には、高信頼性と考えられるシンボルがあたかも無い場合と実用上同等のパフォーマンスが得られており、ノイズ電力スペクトル密度（noise power spectral density）Ｎ０によっては、３０％の位置までが高信頼性位置となる。
【０１２８】
図２０は、異なるしきい値Ｔが、２元ＢＣＨ（１５，７，５）符号についての受信語内で高信頼性位置と判断される位置の平均パーセント値に、どのように影響するかを示している。
【０１２９】
位置が高信頼性であるか否かをを判断するのにしきい値を用いる代わりに、予め定められたＮｈａｒｄ個の最も高い信頼性のある受信シンボル値を、高信頼性であると判断することもできる。しかしながら、この場合には、Ｎｈａｒｄの最適値を決定するために、個々の符号毎に「細かいチューニング」が必要となる。実施化のためには、しきい値法の方が好ましい。ＨＲＰ値を固定するためには、受信通信路の信頼値を順番に並べることが必要となり、反復型復号器の構成を複雑にしてしまうからである。
【０１３０】
本発明について、具体的な実施の形態を参照しながら詳細にわたり説明してきたが、本発明は、特許請求の範囲に記載した本発明の範囲で種々の変形や改良が可能である。
【０１３１】
例えば、パリティ検査多項式を復号器に入力することに代えて、行列Ｈｅの構造を直接復号器に入力するようにしてもよい。しかしながら、この場合には、ｎｘＪの整数、又は、ｎｘＪｘｌｏｇ２ｎビットが必要となる。
【０１３２】
又、本実施の形態では、パリティ検査多項式ｈ（ｘ）、コード長、パリティ検査多項式の係数の位置、パリティ検査多項式のハミング重み、といった復号パラメータは、ヘッダー中に格納された状態で符号器を有する送信器から送信される。しかしながら、復号パラメータは、第２の通信路を介してサイド情報（side information）として送信されてもよい。若しくは、復号器を有する受信機のプロセッサが、復号ビットエラーの数が所定のしきい値より小さくなるまで、可能な限り全ての復号パラメータについて試してみるのでもよい。
【０１３３】
本実施の形態では、本発明を２元巡回符号の復号のための復号器に適用している。しかしながら、本発明を非２元巡回符号の復号のための復号器に適用することもできる。メモリーの容量がより多く必要となるが、非２元符号の反復型復号器も、その実施化は相対的には簡単である。
【図面の簡単な説明】
【図１】本発明の実施の形態による復号器の機能的構成を示すブロック図。
【図２】２元巡回（７，４）符号のターナーグラフ（Tanner graph）を示す図。
【図３】（ａ）は拡張パリティ検査行列Ｈｅに関連するターナーグラフ中の一般的な検査点とその親符号点との間の接続を示す概略図、（ｂ）は拡張パリティ検査行列Ｈｅに関連するターナーグラフ中の一般的な符号点とその子検査点との間の接続を示す概略図。
【図４】２元巡回（７，４）ハミングコードの拡張パリティ検査行列Ｈｅに関連したターナーグラフを示す図。
【図５】関数Ｆ（ｘ）をｚの量子化バージョンＦＱ（ｘ）と比較するグラフ。
【図６】図１に示される復号器のＸプロセッサの構成を示すブロック図。
【図７】本発明に従い反復を４回を行なうことにより復号を行って得られた、（７，４）ハミングコードの反復型復号のシュミレーション結果を示すグラフ。
【図８】本発明に従い２元ＢＣＨ（１５，１１）符号を復号したシュミレーション結果を示すグラフ。
【図９】本発明に従い２元ＢＣＨ（１５，７，５）符号を復号したシュミレーション結果を示すグラフ。
【図１０】本発明に従い２元ＢＣＨ（１５，５，７）符号を復号したシュミレーション結果を示すグラフ。
【図１１】本発明に従い２元ＢＣＨ（２７３，１９１）差集合（ＤＳ）コードを復号したシュミレーション結果を示すグラフ。
【図１２】本実施の形態の第１の実施例によるシリアル復号器を示すブロック図。
【図１３】図１２に示されるシリアル復号器のＸプロセッサを示すブロック図。
【図１４】図１２に示されるシリアル復号器のＺプロセッサを示すブロック図。
【図１５】（ａ）は、図１２に示されるシリアル復号器のＸ−ｔｏ−Ｚ伝搬ユニットのＸ−ｔｏ−Ｚアドレス発生器におけるアドレスの発生を示す概略図、（ｂ）は、図１２に示されるシリアル復号器のＺ−ｔｏ−Ｘ伝搬ユニットの、Ｚ−ｔｏ−Ｘアドレス発生器におけるアドレスの発生を示す概略図。
【図１６】図１２に示されたＸ−ｔｏ−Ｚ伝搬ユニットのπＲＡＭにメトリックπｘ（ｉ，ｊ）が記憶された状態を示す概略図。
【図１７】図１２に示されたＺ−ｔｏ−Ｘ伝搬ユニットのλＲＡＭにメトリックλｚ（ｉ，ｊ）が記憶された状態を示す概略図。
【図１８】本実施の形態の第２の実施例によるパラレル復号器を示すブロック図。
【図１９】高信頼性位置を示すための複数の異なるしきい値がエラーパフォーマンスにどのように影響を与えるかを示すグラフ。
【図２０】複数の異なるしきい値が、高信頼性位置であると判断される位置の平均パーセント値にどのように影響を与えるかを示すグラフ。
【符号の説明】
１  復号器
２  入力ユニット
３  スケーラ
４  Ｘプロセッサ
５  情報交換制御ユニット
６  Ｚプロセッサ
１０  事後値ｑ（ｉ）計算器
１１  πｘ（ｉ，ｊ）メトリック計算器
0004389373.tif 000068
３０  スケーラ
３５  ＬＬＲバッファ３５
４０  Ｘプロセッサ
４５  バッファ
５０Ａ  Ｘ−ｔｏ−Ｚ伝搬ユニット
５０Ｂ  Ｚ−ｔｏ−Ｘ伝搬ユニット
５１  πＲＡＭ制御器
５１ａ  Ｘ−ｔｏ−Ｚアドレス発生器
５２  πＲＡＭ
５３  λＲＡＭ制御器
５３ａ  Ｚ−ｔｏ−Ｘアドレス発生器
５４  λＲＡＭ
６０  Ｚプロセッサ
１００  パラレル復号器
４００  Ｘプロセッサ
５００  アドレス計算ユニット（ＡＣＵ）
５０１  Ｘ−ｔｏ−Ｚアドレス発生器
５０２  Ｚ−ｔｏ−Ｘアドレス発生器
５０３  λバス
５０４  πバス
５０５  レジスタ
５０６  レジスタ
６００  Ｚプロセッサ
【図１】
0004389373.tif 000076
【図２】
0004389373.tif 000077
【図３】
0004389373.tif 000078
【図４】
0004389373.tif 000079
【図５】
0004389373.tif 000080
【図６】
0004389373.tif 000081
【図７】
0004389373.tif 000082
【図８】
0004389373.tif 000083
【図９】
0004389373.tif 000084
【図１０】
0004389373.tif 000085
【図１１】
0004389373.tif 000086
【図１２】
0004389373.tif 000087
【図１３】
0004389373.tif 000088
【図１４】
0004389373.tif 000089
【図１５】
0004389373.tif 000090
【図１６】
0004389373.tif 000091
【図１７】
0004389373.tif 000092
【図１８】
0004389373.tif 000093
【図１９】
0004389373.tif 000094
【図２０】
0004389373.tif 000095