(57)【特許請求の範囲】
【請求項１】
低密度パリティ検査符号を定める検査行列の複数列にそれぞれ対応する複数の変数ノードと、前記検査行列の複数行にそれぞれ対応する複数のチェックノードとの間で演算結果を伝搬させるメッセージパッシング・アルゴリズムに基づいた行演算及び列演算を繰り返し行う誤り訂正復号装置であって、
前記行演算を実行して対数外部値比を算出する行演算部と、
前記対数外部値比を用いた前記列演算を実行して対数事前値比を算出する列演算部と
を備え、
前記行演算部は、
前記各チェックノード及び前記各変数ノードの組について、前記複数の変数ノードのうち当該各変数ノードを除く他の変数ノードから、前記検査行列の非零要素に対応するエッジを介して当該各チェックノードへ伝搬される一群の対数事前値比の絶対値の中から、値の小さい順に所定個数の絶対値を検出する値検出部と、
第１の変換テーブルを用いて、当該検出された所定個数の絶対値をそれぞれ複数の第１テーブル変換値に変換する第１テーブル変換部と、
前記複数の第１テーブル変換値を乗算する乗算器と、
第２の変換テーブルを用いて、前記乗算器の出力値を第２テーブル変換値に変換する第２テーブル変換部と、
前記第２テーブル変換値に符号を付加して前記対数外部値比を生成する符号付加部と
を含む誤り訂正復号装置。
【請求項２】
請求項１記載の誤り訂正復号装置であって、前記第１の変換テーブルは、入力値に対して、単調増加関数の関数値を前記第１テーブル変換値として与えることを特徴とする誤り訂正復号装置。
【請求項３】
請求項２記載の誤り訂正復号装置であって、前記単調増加関数が双曲線正接関数であることを特徴とする誤り訂正復号装置。
【請求項４】
請求項２または請求項３記載の誤り訂正復号装置であって、前記第２の変換テーブルは、入力値に対して、前記単調増加関数の逆関数の関数値を前記第２テーブル変換値として与えることを特徴とする誤り訂正復号装置。
【請求項５】
請求項１から請求項４のうちのいずれか１項記載の誤り訂正復号装置であって、
前記検査行列は、全ての行について一定の行重みを有する行列であり、
前記検査行列の各行における行列要素の配列は、当該各行に隣接する行における行列要素の配列を一定の巡回シフト量だけ巡回的にシフトさせた配列と一致する、
ことを特徴とする誤り訂正復号装置。
【請求項６】
請求項５記載の誤り訂正復号装置であって、
バッファメモリに対するデータの読み出し及び書き込みを制御するメモリ制御部と、
前記検査行列の行重みの個数分の相対アドレスを格納するアドレスレジスタと
を更に備え、
前記対数事前値比は、前記バッファメモリの特定のデータ格納領域に記憶されており、
前記メモリ制御部は、前記巡回シフト量及び行番号の組み合わせに対応するオフセットを前記相対アドレスに加算して巡回アドレスを生成し、該巡回アドレスに基準アドレスを加算することにより前記特定のデータ格納領域から前記対数事前値比を読み出すための読出アドレスを生成する、
ことを特徴とする誤り訂正復号装置。
【請求項７】
請求項５または請求項６記載の誤り訂正復号装置であって、前記検査行列は、ユークリッド幾何符号または射影幾何符号を用いて生成された行列であることを特徴とする誤り訂正復号装置。
【請求項８】
請求項１から請求項７のうちのいずれか１項記載の誤り訂正復号装置であって、前記行演算部は、前記一群の対数事前値比の符号の組み合わせに応じて、前記第２テーブル変換値に付加すべき符号を決定する符号決定部を更に含むことを特徴とする誤り訂正復号装置。
【請求項９】
通信路から変調信号を受信する受信器と、
前記受信器の出力を復調して受信信号を出力する復調器と、
前記受信信号を復号する請求項１から請求項８のうちのいずれか１項記載の誤り訂正復号装置と
を備えることを特徴とする受信装置。
【請求項１０】
低密度パリティ検査符号を定める検査行列の複数列にそれぞれ対応する複数の変数ノードと、前記検査行列の複数行にそれぞれ対応する複数のチェックノードとの間で演算結果を伝搬させるメッセージパッシング・アルゴリズムに基づいた行演算及び列演算を演算回路において繰り返し行う誤り訂正復号方法であって、
前記行演算を実行して対数外部値比を算出するステップと、
前記対数外部値比を用いた前記列演算を実行して対数事前値比を算出するステップと
を備え、
前記行演算は、
前記各チェックノードと前記各変数ノードとの組について、前記複数の変数ノードのうち当該各変数ノードを除く他の変数ノードから、前記検査行列の非零要素に対応するエッジを介して当該各チェックノードへ伝搬される一群の対数事前値比の絶対値の中から、値の小さい順に所定個数の絶対値を検出するステップと、
第１の変換テーブルを用いて、当該検出された所定個数の絶対値をそれぞれ複数の第１テーブル変換値に変換するステップと、
前記複数の第１テーブル変換値を乗算して乗算値を算出するステップと、
第２の変換テーブルを用いて、前記乗算値を第２テーブル変換値に変換するステップと、
前記第２テーブル変換値に符号を付加して前記対数外部値比を生成するステップと
を含むことを特徴とする誤り訂正復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、低密度パリティ検査符号（ＬＤＰＣ：Low-Density Parity Check codes）の誤り訂正技術及びこれを用いた通信技術に関する。
【背景技術】
【０００２】
低密度パリティ検査符号（以下「ＬＤＰＣ符号」という。）は、非零の行列要素の密度が非常に低い疎なパリティ検査行列（以下「検査行列」ともいう。）で定義される線形符号であり、１９６２年にギャラガー（Gallager）によって最初に提案されたものである（下記非特許文献１）。
【０００３】
ＬＤＰＣ符号は、一般に、検査行列の各列の重み（以下「列重み」という。）が全て一定となり且つ検査行列の各行の重み（以下「行重み」という。）も全て一定となる正則ＬＤＰＣ符号（レギュラーＬＤＰＣ符号）と、この正則ＬＤＰＣ符号以外の非正則ＬＤＰＣ符号（イレギュラーＬＤＰＣ符号）とに大別される。列重みは、検査行列の各列における非零要素の総和を意味し、行重みは、検査行列の各行における非零要素の総和を意味する。
【０００４】
図１は、３行６列の検査行列Ｈの一例を示す図である。この検査行列の場合、１行目の行重み（＝４）と３行目の行重み（＝３）とが互いに異なり、また、１列目の列重み（＝１）と４列目の列重み（＝３）も互いに異なる。このため、図１に示した検査行列Ｈで定義されるＬＤＰＣ符号は、非正則である。なお、実際の回路実装の際には、行数及び列数がそれぞれ数百〜数万となる検査行列が使用される場合がある。
【０００５】
通常、非正則ＬＤＰＣ符号の方が、正則ＬＤＰＣ符号よりも、検査行列の選択の仕方次第で良い誤り訂正復号性能を得ることができる。しかしながら、非正則ＬＤＰＣ符号では、エラーフロア（error floor）と呼ばれる現象が生じ易い。そのため、エラーフロアの発生を抑制する必要がある通信システムでは、正則ＬＤＰＣ符号を使用するとともに、符号長を長くし且つ列重みの大きな符号を用いることにより誤り訂正復号性能の劣化抑制が図られている。ここで、エラーフロアとは、低いＳＮＲ（信号対雑音電力比）の領域では、雑音電力が低下するにつれて復号誤り率が向上するのに対し、高いＳＮＲの領域では、雑音電力が低下するにもかかわらず、復号誤り率が殆ど向上しなくなる現象をいう。
【０００６】
ＬＤＰＣの誤り訂正復号法（以下「ＬＤＰＣ復号法」ともいう。）としては、高い復号性能を実現できるSum-Productアルゴリズムによる方法が知られている。Sum-Productアルゴリズムは、メッセージパッシング（Message Passing）・アルゴリズムまたは確率伝搬法（Belief Propagation）と呼ばれる復号アルゴリズムの一種であり、メッセージパッシング・アルゴリズムは、確率伝搬法と等価であることが知られている。Sum-Productアルゴリズムは、複雑な演算処理を必要とするので、回路実装が難しい。そこで、Sum-Productアルゴリズムに代えて、Min-SumアルゴリズムやオフセットMin-Sumアルゴリズムといった、Sum-Productアルゴリズムから派生した近似アルゴリズムが一般に使用されている。この種の近似アルゴリズムを用いた復号法は、たとえば、特許文献１（特開２０１１−４２２９号公報）に開示されている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０１１−４２２９号公報（たとえば、段落００２５、並びに図７及び段落００３９〜００４３）
【非特許文献】
【０００８】
【非特許文献１】R.G. Gallager, "Low-density parity-check codes," IRE Transactions on Information Theory, vol. 8, pp. 21-28, January 1962.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
上記の近似アルゴリズムを用いたＬＤＰＣ復号法では、検査行列の列重みが大きいと、この検査行列の各行における非零要素の個数が多くなり、復号の際の行演算すなわちチェックノード演算の計算量が増大する。これにより、計算値の誤差が拡大したり、近似演算に起因する復号特性の劣化量が増大したりするおそれがある。
【００１０】
たとえば、特許文献１には、オフセットMin-Sumアルゴリズムの改良版を用いた復号法が開示されている。この復号法は、行演算において、各行ごとに、列ＬＬＲと呼ばれる複数個の対数事前値比の絶対値の中から最小値と２番目に小さい値とを検出し、この最小値または２番目に小さい値を用いて、行ＬＬＲと呼ばれる対数外部値比を算出している。この行演算の計算量は、検査行列の列重みが大きいほど増大するので、行ＬＬＲの誤差を大きくする可能性が高い。
【００１１】
上記に鑑みて本発明の目的は、エラーフロアの発生を抑制するために、ＬＤＰＣ符号を定める検査行列の列重みを大きくした場合でも、復号特性の劣化を抑制することができる誤り訂正復号装置、受信装置及び誤り訂正復号方法を提供する点にある。
【課題を解決するための手段】
【００１２】
本発明の一態様による誤り訂正復号装置は、低密度パリティ検査符号を定める検査行列の複数列にそれぞれ対応する複数の変数ノードと、前記検査行列の複数行にそれぞれ対応する複数のチェックノードとの間で演算結果を伝搬させるメッセージパッシング・アルゴリズムに基づいた行演算及び列演算を繰り返し行う誤り訂正復号装置であって、前記行演算を実行して対数外部値比を算出する行演算部と、前記対数外部値比を用いた前記列演算を実行して対数事前値比を算出する列演算部とを備え、前記行演算部は、前記各チェックノード及び前記各変数ノードの組について、前記複数の変数ノードのうち当該各変数ノードを除く他の変数ノードから、前記検査行列の非零要素に対応するエッジを介して当該各チェックノードへ伝搬される一群の対数事前値比の絶対値の中から、値の小さい順に所定個数の絶対値を検出する値検出部と、第１の変換テーブルを用いて、当該検出された所定個数の絶対値をそれぞれ複数の第１テーブル変換値に変換する第１テーブル変換部と、前記複数の第１テーブル変換値を乗算する乗算器と、第２の変換テーブルを用いて、前記乗算器の出力値を第２テーブル変換値に変換する第２テーブル変換部と、前記第２テーブル変換値に符号を付加して前記対数外部値比を生成する符号付加部とを含むことを特徴とする。
【００１３】
本発明の他の態様による受信装置は、通信路から変調信号を受信する受信器と、前記受信器の出力を復調して受信信号を出力する復調器と、前記誤り訂正復号装置とを備えることを特徴とする。
【００１４】
本発明の更に他の態様による誤り訂正復号方法は、低密度パリティ検査符号を定める検査行列の複数列にそれぞれ対応する複数の変数ノードと、前記検査行列の複数行にそれぞれ対応する複数のチェックノードとの間で演算結果を伝搬させるメッセージパッシング・アルゴリズムに基づいた行演算及び列演算を演算回路において繰り返し行う誤り訂正復号方法であって、前記行演算を実行して対数外部値比を算出するステップと、前記対数外部値比を用いた前記列演算を実行して対数事前値比を算出するステップとを備え、前記行演算は、前記各チェックノードと前記各変数ノードとの組について、前記複数の変数ノードのうち当該各変数ノードを除く他の変数ノードから、前記検査行列の非零要素に対応するエッジを介して当該各チェックノードへ伝搬される一群の対数事前値比の絶対値の中から、値の小さい順に所定個数の絶対値を検出するステップと、第１の変換テーブルを用いて、当該検出された所定個数の絶対値をそれぞれ複数の第１テーブル変換値に変換するステップと、前記複数の第１テーブル変換値を乗算して乗算値を算出するステップと、第２の変換テーブルを用いて、前記乗算値を第２テーブル変換値に変換するステップと、前記第２テーブル変換値に符号を付加して前記対数外部値比を生成するステップとを含むことを特徴とする。
【発明の効果】
【００１５】
本発明によれば、行演算において、演算量の増大を抑制しつつ、Sum-Productアルゴリズムによる演算結果に近い演算結果を得ることができるので、エラーフロアの発生抑制のために検査行列の列重みを大きくしても、復号特性の劣化を効果的に抑制することができる。
【図面の簡単な説明】
【００１６】
【図１】３行６列の検査行列の一例を示す図である。
【図２】本発明に係る実施の形態１の受信装置を含むディジタル通信システムの概略構成を示す機能ブロック図である。
【図３】図１に示した検査行列に対応する２部グラフを示す図である。
【図４】実施の形態１のＬＤＰＣ復号器による復号処理の手順を概略的に示すフローチャートである。
【図５】実施の形態１に係る行演算におけるメッセージ伝搬を概念的に示す図である。
【図６】実施の形態１に係る列演算におけるメッセージ伝搬を概念的に示す図である。
【図７】実施の形態１に係る行演算の処理手順の詳細を示すフローチャートである。
【図８】実施の形態１のＬＤＰＣ復号器の構成の一例を概略的に示す機能ブロック図である。
【図９】実施の形態１の行演算器の構成例を概略的に示す機能ブロック図である。
【図１０】ユークリッド幾何符号を用いて構成された検査行列の一例を示す図である。
【図１１】（Ａ），（Ｂ）は、列ＬＬＲのデータ格納領域を概念的に示す図である。
【図１２】実施の形態２のメモリ制御部の構成のうちアドレス発生回路部分を示す図である。
【発明を実施するための形態】
【００１７】
以下、図面を参照しつつ、本発明に係る種々の実施の形態について詳細に説明する。
【００１８】
実施の形態１．
図２は、本発明に係る実施の形態１の受信装置２０を含むディジタル通信システム１の概略構成を示す機能ブロック図である。図２に示されるように、このディジタル通信システム１は、送信装置１０と受信装置２０とで構成される。送信装置１０は、低密度パリティ検査符号化により送信符号語ｃを生成するＬＤＰＣ（低密度パリティ検査）符号化器１１と、送信符号語ｃを変調して変調信号を生成する変調器１２と、この変調信号を通信路ＣＨに送出する送信器１３とを備えている。通信路ＣＨは、無線通信路または有線通信路のいずれでもよい。
【００１９】
ＬＤＰＣ符号化器１１は、たとえばＫ行Ｎ列（Ｋ，Ｎは正整数）の生成行列Ｇを用いて、情報長Ｋの情報ビット列ｓ＝（ｓ１，ｓ２，…，ｓＫ）を符号化して符号語長Ｎの送信符号語ｃ＝（ｃ１，ｃ２，…，ｃＮ）を生成することができる。ここで、ＬＤＰＣ符号を定めるＭ行Ｎ列（Ｍは正整数）の検査行列をＨで表すとき、生成行列Ｇと検査行列Ｈの転置との積（＝Ｇ・ＨＴ）は、零行列となる。
【００２０】
変調器１２は、ＢＰＳＫ（Binary Phase Shift Keying），π／２シフトＢＰＳＫ，多値ＰＳＫ（M-ary Phase Shift Keying）または多値ＱＡＭ（M-ary Quadrature Amplitude Modulation）などの公知のディジタル変調方式に従い、送信符号語ｃを変調して変調信号を生成することができる。
【００２１】
一方、受信装置２０は、通信路ＣＨから送信信号を受信する受信器２１と、受信器２１の出力を復調して受信信号系列ｄを出力する復調器２２と、この受信信号系列ｄに誤り訂正復号を施して推定語ｅを出力するＬＤＰＣ誤り訂正復号器２３（以下「誤り訂正復号器２３」ともいう。）と、この推定語ｅから情報ビット列ｒを抽出する情報ビット出力部２４とを備えている。
【００２２】
誤り訂正復号器２３は、メッセージパッシング・アルゴリズムに基づいて受信信号系列ｄ＝（ｄ１，ｄ２，…，ｄＮ）を復号して推定語ｅ＝（ｅ１，ｅ２，…，ｅＮ）を生成する。一般に、メッセージパッシング・アルゴリズムは、検査行列ＨのＮ個の列にそれぞれ対応するＮ個の変数ノードと、検査行列ＨのＭ個の行にそれぞれ対応するＭ個のチェックノードとで表現される２部グラフ（タナーグラフともいう。）において、これら変数ノードとチェックノードとの間で演算結果をメッセージとして伝搬させて送信符号語を推定するアルゴリズムをいう。
【００２３】
図３は、図１に示した３行６列の検査行列Ｈに対応する２部グラフを示す図である。図３に示される２部グラフは、図１の検査行列Ｈの第１列〜第６列にそれぞれ対応する変数ノードｂ１〜ｂ６と、その検査行列Ｈの第１行〜第３行にそれぞれ対応するチェックノードａ１〜ａ３とを有する。また、２部グラフには、図１の検査行列Ｈの非零要素（＝１）の各々に対応するノード間接続が存在し、このノード間接続は「エッジ」、「辺」または「枝」と呼ばれている。検査行列Ｈにおけるｍ行ｎ列目の要素Ｈｍｎが非零要素であるときは、ｍ番目のチェックノードａｍとｎ番目の変数ノードｂｎとの間を接続するエッジが存在すると解釈される。
【００２４】
誤り訂正復号器２３から出力される推定語ｅが、情報ビット列とパリティビット列とを含む組織符号である場合、情報ビット出力部２４は、推定語ｅから情報ビット列ｒ＝（ｒ１，ｒ２，…，ｒＫ）を抽出することができる。
【００２５】
次に、図４を参照しつつ、上記の誤り訂正復号器２３の動作を説明する。図４は、誤り訂正復号器２３による復号処理の手順を概略的に示すフローチャートである。
【００２６】
誤り訂正復号器２３は、受信信号系列ｄに基づいて受信ＬＬＲ（受信対数尤度比：Received Log-Likelihood Ratio）の系列λ＝（λ１，λ２，…，λＮ）を算出する（ステップＳＴ１）。情報ビット｛０，１｝がそれぞれ｛１，−１｝として変調されていた場合、通信路ＣＨのモデルがＡＷＧＮ（Additive White Gaussian Noise）チャネルであると仮定すると、次式（１）に従って受信ＬＬＲ系列λを算出することができる。
λｎ＝（２／σ２）×ｄｎ                （１）
【００２７】
ここで、σ２は、ガウス雑音の分散である。ただし、通信路ＣＨのモデルはＡＷＧＮチャネルに限定されるものではなく、実際の通信環境に合わせて通信路ＣＨのモデルを適宜選択すればよい。
【００２８】
次に、誤り訂正復号器２３は、初期化を行う（ステップＳＴ２）。具体的には、誤り訂正復号器２３は、繰り返し回数ｐを「１」の値に、最大繰り返し回数ｐｍａｘを予め決められた値に、対数事前値比の初期値βｍｎ（０）を受信ＬＬＲλｎにそれぞれ設定する。
【００２９】
その後、誤り訂正復号器２３は、各行番号ｍについて行番号の昇順（すなわち、１，２，…，Ｍの順番）で、対数事前値比βｍｎ（ｐ−１）を用いて、メッセージパッシング・アルゴリズムに基づく行演算すなわちチェックノード演算を実行して対数外部値比αｍｎ（ｐ）を算出する（ステップＳＴ３）。対数外部値比αｍｎ（ｐ）は、２部グラフにおいてチェックノードａｍから変数ノードｂｎへ伝搬されるメッセージである。本明細書では、以下、対数外部値比を「行ＬＬＲ」とも呼ぶこととする。また、対数事前値比βｍｎ（ｐ−１）は、２部グラフにおいて変数ノードｂｎからチェックノードａｍへ伝搬されるメッセージである。本明細書では、以下、対数事前値比を「列ＬＬＲ」とも呼ぶこととする。
【００３０】
本実施の形態に係る行演算（ステップＳＴ３）は、公知のSum-Productアルゴリズムに対する近似アルゴリズムに従って行われる。Sum-Productアルゴリズムは、メッセージパッシング・アルゴリズムの一種である。Sum-Productアルゴリズムによれば、次式（２）による行演算を実行して行ＬＬＲαｍｎ（ｐ）を算出することができる。
0006395658.tif 000002
【００３１】
ここで、ｔａｎｈ（ｘ）は、変数ｘに関する双曲線正接関数を意味し、ａｒｃｔａｎｈ（ｘ）は、変数ｘに関する逆双曲線正接関数、すなわち双曲線正接関数ｔａｎｈ（ｘ）の逆関数を意味する。
【００３２】
上式（２）中、Ａ（ｍ）は、検査行列Ｈの第ｍ行に存在する非零要素の列番号（言い換えれば、第ｍ行において「１」が立っている列番号）の集合であり、Ａ（ｍ）＼ｎは、集合Ａ（ｍ）に属する要素のうち列番号ｎ以外の要素の集合をいう。たとえば、図１に示した検査行列Ｈの場合、第１行における非零要素は、第１列、第２列、第３列及び第４列に存在するので、集合Ａ（１）＝｛１，２，３，４｝となる。Ａ（１）＼２＝｛１，３，４｝である。また、第２行における非零要素は、第３列及び第４列に存在するので、集合Ａ（２）＝｛３，４｝となる。Ａ（２）＼３＝｛４｝である。
【００３３】
また、集合Ａ（ｍ）は、ｍ番目のチェックノードａｍから延びるエッジの終端に存在する変数ノードｂｊの番号ｊの集合ということもできる。たとえば、図３に示した２部グラフの場合、チェックノードａ１から延びるエッジの終端には、変数ノードｂ１，ｂ２，ｂ３，ｂ４が存在するので、Ａ（１）＝｛１，２，３，４｝となる。
【００３４】
上式（２）を次式（３）に変形することができる。
0006395658.tif 000003
【００３５】
ここで、ｓｇｎ（ｘ）は、次式（４）で定義される。
0006395658.tif 000004
【００３６】
公知のMin-Sumアルゴリズムでは、式（３）は、次式（５）で近似される。
0006395658.tif 000005
【００３７】
これに対し、本実施の形態に係る近似アルゴリズムでは、上記の変形式（３）における双曲線正接関数ｔａｎｈ（）の部分がテーブル変換πに置き換えられ、逆双曲線正接関数ａｒｃｔａｎｈ［］の部分がテーブル変換φに置き換えられる。具体的には、本実施の形態に係る行演算（ステップＳＴ３）は、次式（６）に基づいて行われる。
0006395658.tif 000006
【００３８】
ここで、ＭＩＮｑは、行番号ｍと集合Ａ（ｍ）＼ｎに属する列番号ｊとの組（ｍ，ｊ）をインデックスとする列ＬＬＲβｍｊ（ｐ−１）の絶対値の中から、値の小さい順に選択されたｋ個の絶対値のうちのｑ番目の値である。すなわち、列ＬＬＲβｍｊ（ｐ−１）の絶対値が昇順に並べ替えられたとき、当該絶対値のうちの上位ｋ個の値が、ＭＩＮ１，…，ＭＩＮｋとなる。
【００３９】
メッセージパッシング・アルゴリズムによれば、行ＬＬＲαｍｎ（ｐ）の算出に使用される列ＬＬＲβｍｊ（ｐ−１）は、図５に示されるように、集合Ａ（ｍ）＼ｎに属する列番号ｊに対応する変数ノードｂｊからエッジを介してチェックノードａｍへ伝搬されるメッセージであると解釈される。また、行ＬＬＲαｍｎ（ｐ）は、チェックノードａｍから変数ノードｂｎへ伝搬されるメッセージであると解釈される。
【００４０】
上記した行演算（ステップＳＴ３）の実行後、誤り訂正復号器２３は、各列番号ｎについて列番号の昇順（すなわち、１，２，…，Ｎの順番）で、行ＬＬＲαｍｎ（ｐ）を用いて、メッセージパッシング・アルゴリズムに基づく列演算すなわち変数ノード演算を実行して列ＬＬＲβｍｎ（ｐ）を算出する（ステップＳＴ４）。
【００４１】
具体的には、本実施の形態の列演算は、次式（７）に基づいて行われる。
0006395658.tif 000007
【００４２】
ここで、Ｂ（ｎ）は、検査行列Ｈの第ｎ列に存在する非零要素の行番号（言い換えれば、第ｎ列において「１」が立っている行番号）の集合であり、Ｂ（ｎ）＼ｍは、集合Ｂ（ｎ）に属する要素のうち行番号ｍ以外の要素の集合をいう。たとえば、図１に示した検査行列Ｈの場合、第３列における非零要素は、第１行及び第２行に存在するので、Ｂ（３）＝｛１，２｝となる。また、第４列における非零要素は、第１行、第２行及び第３行に存在するので、Ｂ（４）＝｛１，２，３｝となる。
【００４３】
また、集合Ｂ（ｎ）は、ｎ番目の変数ノードｂｎから延びるエッジの終端に存在するチェックノードａｉの番号ｉの集合ということもできる。たとえば、図３に示した２部グラフの場合、変数ノードｂ３から延びるエッジの終端には、チェックノードａ１，ａ２が存在するので、Ｂ（３）＝｛１，２｝となる。
【００４４】
メッセージパッシング・アルゴリズムによれば、列ＬＬＲβｍｎ（ｐ）の算出に使用される行ＬＬＲαｉｎ（ｐ−１）は、図６に示されるように、集合Ｂ（ｎ）＼ｍに属する行番号ｉに対応するチェックノードａｉからエッジを介して変数ノードｂｎへ伝搬されるメッセージであると解釈される。また、列ＬＬＲβｍｎ（ｐ）は、変数ノードｂｎからチェックノードａｍへ伝搬されるメッセージであると解釈される。
【００４５】
上記の列演算（ステップＳＴ４）の実行後、誤り訂正復号器２３は、行ＬＬＲαｉｎ（ｐ）及び受信ＬＬＲλｎに基づいて一時推定ビット列を算出する（ステップＳＴ５）。具体的には、先ず、次式（８）に従って対数事後確率比Ｑ１，…，ＱＮが算出される。
0006395658.tif 000008
【００４６】
次いで、次式（９）に従って対数事後確率比Ｑ１，…，ＱＮの各々を硬判定することにより、一時推定ビット列ｅ＝（ｅ１，…，ｅＮ）が算出される。
0006395658.tif 000009
【００４７】
その後、誤り訂正復号器２３は、復号条件が成立するか否かを判定する（ステップＳＴ６）。具体的には、一時推定ビット列ｅに関するシンドロームＳが次式（１０）を満たすという条件、または、繰り返し回数ｐが最大繰り返し回数ｐｍａｘに到達したという条件のいずれか一方が成立するか否かが判定される。
Ｓ＝Ｈ・ｃＴ＝０            （１０）
【００４８】
そして、シンドロームＳが上式（１０）を満たしておらず、且つ、繰り返し回数ｐが最大繰り返し回数ｐｍａｘに到達していない場合は（ステップＳＴ６のＮＯ）、繰り返し回数ｐがインクリメントされ（ステップＳＴ７）、その後、復号処理はステップＳＴ３に戻る。一方、シンドロームＳが上式（１０）を満たす場合、または、繰り返し回数ｐが最大繰り返し回数ｐｍａｘに到達した場合は（ステップＳＴ６のＹＥＳ）、誤り訂正復号器２３は、一時推定ビット列ｅを推定語として出力する（ステップＳＴ８）。
【００４９】
次に、上記ステップＳＴ３の行演算について更に詳細に説明する。図７は、行演算（ステップＳＴ３）の処理手順の詳細を示すフローチャートである。
【００５０】
図７を参照すると、誤り訂正復号器２３は、外側ループ（以下「行ループ」）の始端ＲＬｓと終端ＲＬｅとの間の処理を、各行番号ｍについて行番号の昇順（すなわち、１，２，…，Ｍの順）で繰り返し実行し、また、内側ループ（以下「列ループ」）の始端ＣＬｓと終端ＣＬｅとの間の処理を各列番号ｎについて列番号の昇順（すなわち、１，２，…，Ｎの順）で繰り返し実行する。行ループは、行番号ｍ＝Ｍについての処理が完了するまで続行され、列ループは、列番号ｎ＝Ｎについての処理が完了するまで続行される。
【００５１】
誤り訂正復号器２３は、上記のとおり、集合Ａ（ｍ）＼ｎに属する列番号ｊをインデックスとする列ＬＬＲβｍｊ（ｐ−１）の絶対値の中から、値の小さい順にｋ個の絶対値ＭＩＮ１，…，ＭＩＮｋを検出する（ステップＳＴ３３）。ここで、ｋは、予め定められた正整数値であり、検査行列Ｈの列重みの最小値以下の値となるように設定される。
【００５２】
次に、誤り訂正復号器２３は、絶対値ＭＩＮ１，…，ＭＩＮｋのテーブル変換πを実行してテーブル変換値π（ＭＩＮ１），…，π（ＭＩＮｋ）を生成する（ステップＳＴ３４）。具体的には、絶対値ＭＩＮ１，…，ＭＩＮｋは、予め用意された変換テーブルＴｑを用いてテーブル変換値π（ＭＩＮ１），…，π（ＭＩＮｋ）へ変換される。
【００５３】
次に、誤り訂正復号器２３は、ステップＳＴ３４で生成されたｋ個のテーブル変換値π（ＭＩＮ１），…，π（ＭＩＮｋ）を互いに乗算して乗算値ｚを生成する（ステップＳＴ３５）。その後、誤り訂正復号器２３は、乗算値ｚのテーブル変換φを実行してテーブル変換値φ（ｚ）を生成する（ステップＳＴ３６）。具体的には、乗算値ｚは、予め用意された変換テーブルＴＢＬを用いてテーブル変換値φ（ｚ）へ変換される。
【００５４】
上記のテーブル変換π，φを実現する変換テーブルＴｑ，ＴＢＬとしては、入力値に対応するテーブル変換値を格納しているルックアップテーブルを使用すればよい。また、テーブル変換値が記憶されたメモリ回路をルックアップテーブルとして使用してもよい。この種のメモリ回路は、入力値によってアドレス指定された記憶領域から、所定ビット長のテーブル変換値を読み出すように構成される。テーブル変換値としては、たとえば、単調増加関数の関数値を固定ビット長の値に変換して使用することができる。また、必要に応じてその関数値を正規化してもよい。
【００５５】
テーブル変換πは、上述のとおり、上式（３）中の双曲線正接関数ｔａｎｈ（）の部分に対する近似であるので、変換テーブルＴｑ作成用の単調増加関数ｆ（ｘ）としては、双曲線正接関数を使用することが望ましい。これにより、Sum-Productアルゴリズムによる行演算結果に近い演算結果を得ることができる。
【００５６】
また、双曲線正接関数は、正の入力変数の値が大きくなるにつれて関数値の増加分が小さくなる関数である。このため、たとえ単調増加関数ｆ（ｘ）として双曲線正接関数を使用しない場合でも、単調増加関数ｆ（ｘ）は、正の入力変数ｘの値が大きくなるにつれて関数値の増加分が小さくなる関数であることが望ましい。
【００５７】
一方、テーブル変換φは、上述のとおり、上式（３）中の逆双曲線正接関数ａｒｃｔａｎｈ［］の部分に対する近似である。このため、変換テーブルＴＢＬ作成用の単調増加関数としては、変換テーブルＴｑ作成用の単調増加関数ｆ（ｘ）の逆関数ｆ−１（ｘ）を使用することが望ましく、特に、逆双曲線正接関数ａｒｃｔａｎｈ（ｘ）を使用することが望ましい。
【００５８】
上記ステップＳＴ３６の実行後、誤り訂正復号器２３は、集合Ａ（ｍ）＼ｎに属する列番号ｊをインデックスとする列ＬＬＲβｍｊ（ｐ−１）の符号の組み合わせに応じて、算出すべき行ＬＬＲαｍｎ（ｐ）の符号が正符号または負符号のいずれであるかを決定する（ステップＳＴ３７）。たとえば、上式（６）に示すｓｇｎ（βｍｊ（ｐ−１））の乗算結果ｓｇｎｍｎの符号を、算出すべき行ＬＬＲαｍｎ（ｐ）の符号とすることができる。あるいは、ｓｇｎ（βｍｊ（ｐ−１））の符号ビットの排他的論理和演算を実行して行ＬＬＲαｍｎ（ｐ）の符号ビットを決定してもよい。
【００５９】
そして、誤り訂正復号器２３は、ステップＳＴ３７で決定された符号をテーブル変換値φ（ｚ）に付加して行ＬＬＲαｍｎ（ｐ）を生成する（ステップＳＴ３８）。たとえば、テーブル変換値φ（ｚ）を示すビットに符号ビットを付加することで、行ＬＬＲαｍｎ（ｐ）を示すビットを生成することができる。上記のステップＳＴ３３〜ＳＴ３８の処理は、行番号ｍが最大値Ｍに到達し、且つ列番号ｎが最大値Ｎに到達するときまで繰り返し実行される。
【００６０】
次に、図８を参照しつつ、上記復号処理を実行し得る誤り訂正復号器２３の内部構成について説明する。図８は、誤り訂正復号器２３の構成の一例を概略的に示す機能ブロック図である。
【００６１】
図８に示される誤り訂正復号器２３は、復号部３０、メモリ制御部３８及びバッファメモリ３９を備えて構成されており、復号部３０は、入力回路３１、ＬＬＲ演算器３２、行演算器３３、列演算器３４、ビット推定器３５、繰り返し制御器３６及び出力回路３７を有する。なお、図８に示した構成は一例である。特に、行演算器３３の構成に特徴があり、行演算器３３以外の構成が限定されるものではない。
【００６２】
バッファメモリ３９は、受信ＬＬＲ系列λのデータ格納領域６１と、行ＬＬＲ群｛αｍｎ（ｐ）｝のデータ格納領域６２と、列ＬＬＲ群｛βｍｎ（ｐ）｝のデータ格納領域６３とを有している。メモリ制御部３８は、バッファメモリ３９に対するデータの読み出し及び書き込みを制御するインタフェース回路である。復号部３０は、メモリ制御部３８を介してバッファメモリ３９にデータを記憶させたり、メモリ制御部３８を介してバッファメモリ３９からデータを取得したりすることができる。
【００６３】
入力回路３１は、復調器２２からの入力ビット列を符号語単位で分割して、受信信号系列ｄ＝（ｄ１，ｄ２，…，ｄＮ）を適切なタイミングでＬＬＲ演算器３２に出力する。
【００６４】
ＬＬＲ演算器３２は、上記のとおり、受信信号系列ｄに基づいて受信ＬＬＲ系列λ＝（λ１，λ２，…，λＮ）を算出し（図４のステップＳＴ１）、この受信ＬＬＲ系列λをメモリ制御部３８を介してバッファメモリ３９のデータ格納領域６１に記憶させる。
【００６５】
また、初期化が行われる（ステップＳＴ２）。すなわち、繰り返し制御器３６は、繰り返し回数ｐを初期値「１」に設定し、最大繰り返し回数ｐｍａｘを予め決められた値に設定する。また、繰り返し制御器３６は、行演算器３３に初期化情報を通知する。なお、本実施の形態では、受信ＬＬＲ系列λの算出（ステップＳＴ１）の後に初期化（ステップＳＴ２）が実行されているが、これに限定されるものではない。受信ＬＬＲ系列λの算出の前に初期化が実行されてもよいし、または、受信ＬＬＲ系列λの算出と初期化とが同時並列に実行されてもよい。
【００６６】
行演算器３３は、初期化情報の通知に応じて、メモリ制御部３８を介してバッファメモリ３９のデータ格納領域６１から受信ＬＬＲ系列λを読み出す。続いて、行演算器３３は、この受信ＬＬＲ系列λを列ＬＬＲの初期値βｍｎ（ｐ−１）として用いた行演算を実行して行ＬＬＲαｍｎ（ｐ）を算出し（ステップＳＴ３）、この行ＬＬＲαｍｎ（ｐ）を、メモリ制御部３８を介してバッファメモリ３９のデータ格納領域６２に記憶させる。
【００６７】
図９は、行演算器３３の構成例を概略的に示す機能ブロック図である。図９に示されるように、行演算器３３は、入力回路４１、最小ｋ値検出部４２、第１テーブル変換部４３、乗算器４５、第２テーブル変換部４６、符号決定部４７、符号付加部４８及び出力回路４９を有する。入力回路４１は、上記の集合Ａ（ｍ）＼ｎに属する列番号ｊをインデックスとする列ＬＬＲ群｛βｍｊ（ｐ−１）｝をバッファメモリ３９から読み出し、最小ｋ値検出部４２及び符号決定部４７にそれぞれ供給する。
【００６８】
最小ｋ値検出部４２は、列ＬＬＲ群｛βｍｊ（ｐ−１）｝の絶対値の中から、値の小さい順にｋ個の絶対値ＭＩＮ１，…，ＭＩＮｋを検出する（図７のステップＳＴ３３）。
【００６９】
第１テーブル変換部４３は、同時並列に動作するｋ個の変換器４４１，４４２，…，４４ｋからなり、これら変換器４４１，４４２，…，４４ｋは同一の変換テーブルＴｑを有する。変換器４４１，４４２，…，４４ｋは、変換テーブルＴｑを用いて、それぞれ絶対値ＭＩＮ１，ＭＩＮ２，…，ＭＩＮｋのテーブル変換を実行してテーブル変換値π（ＭＩＮ１），π（ＭＩＮ２），…，π（ＭＩＮｋ）を生成し（ステップＳＴ３４）、これらテーブル変換値π（ＭＩＮ１），π（ＭＩＮ２），…，π（ＭＩＮｋ）を乗算器４５に並列に出力する。
【００７０】
乗算器４５は、入力されたテーブル変換値π（ＭＩＮ１），π（ＭＩＮ２），…，π（ＭＩＮｋ）を乗算して乗算値ｚを生成し（ステップＳＴ３５）、この乗算値ｚを第２テーブル変換部４６に出力する。第２テーブル変換部４６は、変換テーブルＴＢＬを用いて、乗算値ｚのテーブル変換を実行してテーブル変換値φ（ｚ）を生成し（ステップＳＴ３６）、このテーブル変換値φ（ｚ）を符号付加部４８に出力する。
【００７１】
一方、符号決定部４７は、列ＬＬＲ群｛βｍｊ（ｐ−１）｝の符号の組み合わせに応じて、算出すべき行ＬＬＲαｍｎ（ｐ）の符号を決定する（ステップＳＴ３７）。その後、符号付加部４８は、符号決定部４７で決定された符号をテーブル変換値φ（ｚ）に付加して行ＬＬＲαｍｎ（ｐ）を生成することができる（ステップＳＴ３８）。出力回路４９は、バッファメモリ３９のデータ格納領域６２に行ＬＬＲαｍｎ（ｐ）を上書きすることにより、データ格納領域６２に記憶されている行ＬＬＲαｍｎ（ｐ−１）を行ＬＬＲαｍｎ（ｐ）へ更新する。
【００７２】
上記した行演算の実行後、図８の列演算器３４は、メモリ制御部３８を介してバッファメモリ３９のデータ格納領域６２から行ＬＬＲαｍｎ（ｐ）を読み出し、これら行ＬＬＲαｍｎ（ｐ）を用いた列演算を実行して列ＬＬＲβｍｎ（ｐ）を算出する（ステップＳＴ４）。更に、列演算器３４は、この列ＬＬＲβｍｎ（ｐ）を、メモリ制御部３８を介してバッファメモリ３９のデータ格納領域６３に記憶させる。
【００７３】
列演算の実行後は、ビット推定器３５は、行ＬＬＲαｍｎ（ｐ）及び受信ＬＬＲλｎに基づいて一時推定ビット列ｅ＝（ｅ１，…，ｅＮ）を算出し（ステップＳＴ５）、一時推定ビット列ｅを繰り返し制御器３６に供給する。
【００７４】
その後、繰り返し制御器３６は、復号条件が成立するか否かを判定する（ステップＳＴ６）。すなわち、繰り返し制御器３６は、一時推定ビット列ｅに基づいてシンドロームＳ（＝Ｈ・ｃＴ）を算出し、このシンドロームＳの要素の全てが零であるか否か、また、繰り返し回数ｐが最大繰り返し回数ｐｍａｘに到達したか否かを判定する。
【００７５】
復号条件が成立しない場合（ステップＳＴ６のＮＯ）、繰り返し制御器３６は、繰り返し回数ｐをインクリメントして（ステップＳＴ７）、行演算器３３に行演算を指示する。
【００７６】
行演算器３３は、繰り返し制御器３６からの指示に応じて、メモリ制御部３８を介してバッファメモリ３９のデータ格納領域６３から列ＬＬＲβｍｎ（ｐ−１）を読み出し、これら列ＬＬＲβｍｎ（ｐ−１）を用いた行演算を実行して行ＬＬＲαｍｎ（ｐ）を算出する（ステップＳＴ３）。更に、行演算器３３は、バッファメモリ３９のデータ格納領域６２に行ＬＬＲαｍｎ（ｐ）を上書きすることにより、データ格納領域６２に記憶されている行ＬＬＲαｍｎ（ｐ−１）を行ＬＬＲαｍｎ（ｐ）へ更新する。
【００７７】
その後、列演算器３４は、メモリ制御部３８を介してバッファメモリ３９のデータ格納領域６２から行ＬＬＲαｍｎ（ｐ）を読み出し、これら行ＬＬＲαｍｎ（ｐ）を用いた列演算を実行して列ＬＬＲβｍｎ（ｐ）を算出する（ステップＳＴ４）。更に、列演算器３４は、バッファメモリ３９のデータ格納領域６３に列ＬＬＲβｍｎ（ｐ）を上書きすることにより、データ格納領域６３に記憶されている列ＬＬＲβｍｎ（ｐ−１）を列ＬＬＲβｍｎ（ｐ）へ更新する。
【００７８】
その後、ビット推定器３５は、行ＬＬＲαｍｎ（ｐ）及び受信ＬＬＲλｎに基づいて一時推定ビット列ｅを算出する（ステップＳＴ５）。繰り返し制御器３６は、上記の復号条件が成立するか否かを判定し（ステップＳＴ６）、復号条件が成立しないときは（ステップＳＴ６のＮＯ）、行演算及び列演算を行演算器３３及び列演算器３４に繰り返し実行させる。
【００７９】
最終的に、復号条件が成立したとき（ステップＳＴ６のＹＥＳ）、繰り返し制御器３６は、一時推定ビット列ｅを推定語として出力回路３７から外部へ出力させる。同時に、繰り返し制御器３６は、次の受信信号系列ｄの出力を入力回路３１に指示し、また、行演算器３３に初期化情報を通知する。これにより、次の受信信号系列ｄに対する復号処理が行われる。
【００８０】
以上に説明したように実施の形態１のＬＤＰＣ誤り訂正復号器２３は、行演算において、図７に示したように、列ＬＬＲβｍｊ（ｐ−１）の絶対値の中から、値の小さい順に所定個数の絶対値ＭＩＮ１〜ＭＩＮｋを検出し（ステップＳＴ３３）、これら絶対値ＭＩＮ１〜ＭＩＮｋのテーブル変換πを実行してテーブル変換値π（ＭＩＮ１）〜π（ＭＩＮｋ）を生成し（ステップＳＴ３４）、これらテーブル変換値π（ＭＩＮ１）〜π（ＭＩＮｋ）を乗算し（ステップＳＴ３５）、その乗算結果ｚのテーブル変換φを実行してテーブル変換値φ（ｚ）を生成している（ステップＳＴ３６）。このため、Min-SumアルゴリズムやオフセットMin-Sumアルゴリズムといった従来の近似アルゴリズムと比べると、演算量の増大を抑制しつつ、Sum-Productアルゴリズムによる演算結果に近い演算結果を得ることができる。したがって、エラーフロアの発生抑制のために検査行列Ｈの列重みを大きくしても、誤り訂正符号の復号特性の劣化を効果的に抑制することができる。
【００８１】
なお、実施の形態１の行演算器３３は、図９に示した回路構成に限定されるものではない。たとえば、変換器４４１〜４４ｋは、並列処理を実行しているが、この並列処理に代えて時分割処理を行う回路構成を採用することができる。
【００８２】
また、回路規模を小さくする観点からは、変換器４４１〜４４ｋは、入力ビット幅よりも小さい出力ビット幅を有するメモリ回路として構成されることが好ましい。これにより、乗算器４５及び第２テーブル変換部４６の回路規模を小さくすることができる。
【００８３】
実施の形態２．
次に、本発明に係る実施の形態２について説明する。
【００８４】
上記実施の形態１では、図８の行演算器３３は、集合Ａ（ｍ）＼ｎに属する列番号ｊをインデックスとする列ＬＬＲβｍｊ（ｐ−１）を、メモリ制御部３８を介してバッファメモリ３９から選択的に読み出す必要がある（図７のステップＳＴ３３）。上述したように、集合Ａ（ｍ）＼ｎは、検査行列Ｈの第ｍ行に存在する非零要素（＝１）の列番号（言い換えれば、第ｍ行において「１」が立っている列番号）の集合のうち、ｎ以外の列番号の集合をいう。このため、メモリ制御部３８は、当該列ＬＬＲβｍｊ（ｐ−１）の読み出しに必要なアドレス情報を予め保持しておく必要がある。本実施の形態は、このようなアドレス情報の保持に必要なメモリ容量の削減を可能とするものである。
【００８５】
先ず、本実施の形態で使用される検査行列Ｈは、全ての行について一定の行重みｗｒを有する。また、検査行列Ｈは、各行における非零要素（＝１）の配列が、当該各行に隣接する行における非零要素の配列を一定のシフト量だけ巡回的にシフトさせた配列と一致するように構成されている。このような検査行列Ｈは、ユークリッド幾何符号または射影幾何符号を用いて構成することが可能である。
【００８６】
Ｙ．Ｋｏｕ等の論文（Y. Kou, S. Lin, and M. P. C. Fossorier, "Low Density Parity Check Codes Based on Finite Geometries: A Rediscovery," ISIT2000, pp. 200, Sorrento, Itary, June 25-30, 2000.）で提案された方法によれば、ユークリッド幾何符号ＥＧ（２，２６）を用いて、図１０に示す検査行列Ｈを構成することができる。図１０の検査行列Ｈは、行重みｗｒ＝４，列重みｗｃ＝４の構造を有する。また、この検査行列Ｈの各行における非零要素の配列は、当該各行に隣接する行における非零要素の配列を１列だけ巡回的にシフトさせた配列と一致する。
【００８７】
図１１（Ａ），（Ｂ）は、列ＬＬＲβｍｎ（ｐ−１）のデータ格納領域６３を概念的に示す図である。図１１（Ａ）に示されるように、このデータ格納領域６３は、列ＬＬＲβｍｎ（ｐ−１）を行単位で保持するＭ個のブロック領域６３１，…，６３ｍ，…，６３Ｍを有する。ｍ番目のブロック領域６３ｍには、図１１（Ｂ）に示されるように、列ＬＬＲ系列βｍ１（ｐ−１），βｍ２（ｐ−１），…，βｍＮ（ｐ−１）が連続的に格納されており、列ＬＬＲβｍ１（ｐ−１），βｍ２（ｐ−１），…，βｍＮ（ｐ−１）の記憶領域に対しては、それぞれ、アドレスＡｄ（ｍ，１），Ａｄ（ｍ，２），…，Ａｄ（ｍ，Ｎ）が割り当てられている。
【００８８】
図１２は、メモリ制御部３８の構成のうちアドレス発生回路部分を示す図である。図１２に示されるように、メモリ制御部３８は、基準アドレスレジスタ５０、相対アドレスレジスタ５１及び加算器５２，５３を含む。相対アドレスレジスタ５１には、行重みｗｒ（＝４）の個数分の相対アドレスＲ１，Ｒ２，Ｒ３，Ｒ４が記憶されている。これら相対アドレスＲ１，Ｒ２，Ｒ３，Ｒ４は、検査行列Ｈの第１行における非零要素（＝１）の列番号にそれぞれ対応するように設定されたものである。
【００８９】
基準アドレスレジスタ５０には基準アドレスが記憶されている。本実施の形態では、基準アドレスとして、各ブロック領域６３ｍ内の先頭の列ＬＬＲβｍ１（ｐ−１）に対応する先頭アドレスＡｄ（ｍ，１）が使用されるが、これに限定されるものではない。
【００９０】
今、バッファメモリ３９のデータ格納領域６３から、集合Ａ（ｍ）＼ｎに属する列番号ｊをインデックスとする列ＬＬＲβｍｊ（ｐ−１）が読み出される場合を考える。この場合、相対アドレスレジスタ５１は、当該列番号ｊに対応する相対アドレスＲｘ（ｘは、１〜４のうちいずれか）を出力する。加算器５２は、巡回シフト量及び行番号ｍの組み合わせ（たとえば、巡回シフト量のｍ倍）に対応するオフセットＯ（ｍ）を相対アドレスＲｘに加算して巡回アドレスＣＡを生成する。ここで、巡回アドレスＣＡは、一定のアドレス空間内を巡回するように生成される。そして、加算器５３は、基準アドレスレジスタ５０から出力された先頭アドレスＡｄ（ｍ，１）に巡回アドレスＣＡを加算して読出アドレスＡｄ（ｍ，ｊ）を生成する。この読出アドレスＡｄ（ｍ，ｊ）で指定される記憶領域から列ＬＬＲβｍｊ（ｐ−１）を読み出すことができる。
【００９１】
このように実施の形態２は、基準アドレスを保持する基準アドレスレジスタ５０と、検査行列Ｈの行重みの個数分の相対アドレスを保持する相対アドレスレジスタ５１とを用いて読出アドレスを生成することができるので、検査行列Ｈの非零要素の全てについて、列ＬＬＲβｍｎ（ｐ−１）の読み出しに必要なアドレス情報を保持する必要がない。したがって、アドレス情報の保持のためのメモリ容量を少なくし、回路規模を削減することができる。
【００９２】
以上、図面を参照して本発明に係る種々の実施の形態について述べたが、これら実施の形態は本発明の例示であり、これら実施の形態以外の様々な変形例を採用することができる。
【００９３】
たとえば、実施の形態１では、図４のステップＳＴ６における復号条件として、一時推定ビット列ｅに関するシンドロームＳが式（１０）を満たすという第１の条件と、繰り返し回数ｐが最大繰り返し回数ｐｍａｘに到達したという第２の条件が採用されたが、第１の条件を採用せずに第２の条件のみを復号条件として採用してもよい。
【００９４】
また、上記ＬＤＰＣ誤り訂正復号器２３は、図４及び図７に示した各ステップを、ＣＰＵ（Central Processing Unit）を含むプロセッサに実行させるコンピュータプログラムにより実現されてもよい。上記ＬＤＰＣ誤り訂正復号器２３は、ＬＳＩ（Large-Scale Integration）回路やＦＰＧＡ（Field-Programmable Gate Array）回路としても構成可能である。
【００９５】
また、本発明に係る誤り訂正復号装置、受信装置及び誤り訂正復号方法は、たとえば、移動体通信システムや衛星通信システムなどのディジタル通信システム、ＬＡＮ（Local Area Network）、大容量記録媒体（たとえば、ハードディスクドライブや光ディスク）用の情報再生装置、及び量子暗号に適用可能である。
【００９６】
なお、本発明の範囲内において、上記実施の形態の自由な組み合わせ、各実施の形態の任意の構成要素の変形、または各実施の形態の任意の構成要素の省略が可能である。
【符号の説明】
【００９７】
１  ディジタル通信システム、  １０  送信装置、  １１  ＬＤＰＣ符号化器、  １２  変調器、  １３  送信器、  ２０  受信装置、  ２１  受信器、  ２２  復調器、  ２３  ＬＤＰＣ誤り訂正復号器、  ２４  情報ビット出力部、  ３０  復号部、  ３１  入力回路、  ３２  ＬＬＲ演算器、  ３３  行演算器（行演算部）、  ３４  列演算器（列演算部）、  ３５  ビット推定器、  ３６  繰り返し制御器、  ３７  出力回路、  ３８  メモリ制御部、  ３９  バッファメモリ、  ４１  入力回路、  ４２  最小ｋ値検出部、  ４３  第１テーブル変換部、  ４４１，４４２，…，４４ｋ  変換器、  ４５  乗算器、  ４６  第２テーブル変換部、  ４７  符号決定部、  ４８  符号付加部、  ４９  出力回路、  ５０  基準アドレスレジスタ、  ５１  相対アドレスレジスタ、  ５２，５３  加算器、  ６１，６２，６３  データ格納領域。
【図１】
0006395658.tif 000010
【図２】
0006395658.tif 000011
【図３】
0006395658.tif 000012
【図４】
0006395658.tif 000013
【図５】
0006395658.tif 000014
【図６】
0006395658.tif 000015
【図７】
0006395658.tif 000016
【図８】
0006395658.tif 000017
【図９】
0006395658.tif 000018
【図１０】
0006395658.tif 000019
【図１１】
0006395658.tif 000020
【図１２】
0006395658.tif 000021