(57)【特許請求の範囲】
【請求項１】
ＬＤＰＣ（Low-Density Parity-Check）符号で符号化された符号語を復号する復号方法において、
前記ＬＤＰＣ符号の検査行列の行重みに対応する行ＬＬＲ（Log-Likelihood Ratio；対数尤度比）を算出する行演算ステップと、
前記行ＬＬＲから前記検査行列の列重みに対応する列ＬＬＲを算出する列演算ステップと、
前記列ＬＬＲを基にビットごとの推定を行って推定ビット列を算出するビット推定ステップと、
推定ビット列が前記符号語であるか否かを検査する検査ステップとを備え、
前記行演算ステップと前記列演算ステップを交互に繰り返して前記符号語を復号するにあたり、
前記行演算ステップにて、
前記列ＬＬＲの絶対値の最小値と予め設定された値との大きさ関係を判定し、当該最小値が予め設定された値以上である場合、前記列ＬＬＲの絶対値の最小値の大きさに応じて変動させたオフセット値を当該列ＬＬＲの絶対値の最小値から引いた値を、当該列ＬＬＲの列に対応する行ＬＬＲとすることを特徴とする復号方法。
【請求項２】
ＬＤＰＣ（Low-Density Parity-Check）符号で符号化された符号語を復号する復号方法において、
前記ＬＤＰＣ符号の検査行列の行重みに対応する行ＬＬＲ（Log-Likelihood Ratio；対数尤度比）を算出する行演算ステップと、
前記行ＬＬＲから前記検査行列の列重みに対応する列ＬＬＲを算出する列演算ステップと、
前記列ＬＬＲを基にビットごとの推定を行って推定ビット列を算出するビット推定ステップと、
推定ビット列が前記符号語であるか否かを検査する検査ステップとを備え、
Ｓｕｍ−Ｐｒｏｄｕｃｔ復号法のアルゴリズムを用いて、前記行演算ステップと前記列演算ステップを交互に繰り返して前記符号語を復号するにあたり、
前記行演算ステップにて、
前記列ＬＬＲの絶対値の最小値と予め設定された値との大きさ関係を判定し、当該最小値が予め設定された値以上である場合、前記Ｓｕｍ−Ｐｒｏｄｕｃｔ復号法のアルゴリズムの行演算で実行される２項演算の対象となる２値の最小値の大きさに応じて、前記２値の差を変数δとするδ−ｍｉｎ復号法で規定されるオフセット値を変動させ、当該オフセット値を前記２値の最小値から引いた差分値を前記２項演算の結果とすることを特徴とする復号方法。
【請求項３】
ＬＤＰＣ（Low-Density Parity-Check）符号で符号化された符号語を復号する復号方法において、
前記ＬＤＰＣ符号の検査行列の行重みに対応する行ＬＬＲ（Log-Likelihood Ratio；対数尤度比）を算出する行演算ステップと、
前記行ＬＬＲから前記検査行列の列重みに対応する列ＬＬＲを算出する列演算ステップと、
前記列ＬＬＲを基にビットごとの推定を行って推定ビット列を算出するビット推定ステップと、
推定ビット列が前記符号語であるか否かを検査する検査ステップとを備え、
前記行演算ステップと前記列演算ステップを交互に繰り返して前記符号語を復号するにあたり、
前記行演算ステップにて、
前記列ＬＬＲの絶対値の最小値と予め設定された値との大きさ関係を判定し、当該最小値が予め設定された値以上である場合、前記列ＬＬＲの絶対値の最小値、２番目に小さい値、及び３番目に小さい値である最小３値の大きさに応じて、前記最小３値のうちの２値の差を変数δとするδ−ｍｉｎ復号法で規定されるオフセット値を変動させ、当該オフセット値を前記列ＬＬＲの絶対値の最小値から引いた差分値を、当該列ＬＬＲの列に対応する行ＬＬＲとすることを特徴とする復号方法。
【請求項４】
ＬＤＰＣ（Low-Density Parity-Check）符号で符号化された符号語を復号する復号方法において、
前記ＬＤＰＣ符号の検査行列の行重みに対応する行ＬＬＲ（Log-Likelihood Ratio；対数尤度比）を算出する行演算ステップと、
前記行ＬＬＲから前記検査行列の列重みに対応する列ＬＬＲを算出する列演算ステップと、
前記列ＬＬＲを基にビットごとの推定を行って推定ビット列を算出するビット推定ステップと、
推定ビット列が前記符号語であるか否かを検査する検査ステップとを備え、
前記行演算ステップと前記列演算ステップを交互に繰り返して前記符号語を復号するにあたり、
前記行演算ステップにて、
絶対値が最小となる列ＬＬＲに対しては、当該最小値の大きさに応じたオフセット値を当該列ＬＬＲの絶対値の２番目に小さい値から引いた差分値を、当該列ＬＬＲの列に対応する行ＬＬＲとし、
絶対値が２番目に小さい列ＬＬＲに対しては、当該列ＬＬＲの絶対値の大きさに応じたオフセット値を当該列ＬＬＲの絶対値の最小値から引いた差分値を、当該列ＬＬＲの列に対応する行ＬＬＲとし、
上記以外の列に対しては、前記列ＬＬＲの絶対値の２番目に小さい値から前記列ＬＬＲの絶対値の最小値を引いた差を変数δとするδ−ｍｉｎ復号法で規定されるオフセット値を当該列ＬＬＲの絶対値の最小値から引いた差分値を、当該列に対応する行ＬＬＲとすることを特徴とする復号方法。
【請求項５】
ＬＤＰＣ（Low-Density Parity-Check）符号で符号化された符号語を復号する復号装置において、
前記ＬＤＰＣ符号の検査行列の行重みに対応する行ＬＬＲ（Log-Likelihood Ratio；対数尤度比）を算出する行演算手段と、
前記行演算手段で算出された行ＬＬＲから前記検査行列の列重みに対応する列ＬＬＲを算出する列演算手段と、
前記列演算手段で算出された列ＬＬＲを基にビットごとの推定を行って推定ビット列を算出するビット推定手段と、
前記ビット推定手段で算出された推定ビット列が前記符号語であるか否かを検査する検査手段とを備え、
前記行演算手段は、
前記列ＬＬＲの絶対値の最小値と予め設定された値との大きさ関係を判定し、当該最小値が予め設定された値以上である場合、前記列ＬＬＲの絶対値の最小値の大きさに応じて変動させたオフセット値を当該列ＬＬＲの絶対値の最小値から引いた値を、当該列ＬＬＲの列に対応する行ＬＬＲとすることを特徴とする復号装置。
【請求項６】
ＬＤＰＣ（Low-Density Parity-Check）符号で符号化された符号語を復号する復号装置において、
前記ＬＤＰＣ符号の検査行列の行重みに対応する行ＬＬＲ（Log-Likelihood Ratio；対数尤度比）を算出する行演算手段と、
前記行演算手段で算出された行ＬＬＲから前記検査行列の列重みに対応する列ＬＬＲを算出する列演算手段と、
前記列演算手段で算出された列ＬＬＲを基にビットごとの推定を行って推定ビット列を算出するビット推定手段と、
前記ビット推定手段で算出された推定ビット列が前記符号語であるか否かを検査する検査手段とを備え、
前記行演算手段は、
前記列ＬＬＲの絶対値の最小値と予め設定された値との大きさ関係を判定し、当該最小値が予め設定された値以上である場合、Ｓｕｍ−Ｐｒｏｄｕｃｔ復号法のアルゴリズムの行演算で実行される２項演算の対象となる２値の最小値の大きさに応じて、前記２値の差を変数δとするδ−ｍｉｎ復号法で規定されるオフセット値を変動させ、当該オフセット値を前記２値の最小値から引いた差分値を前記２項演算の結果とすることを特徴とする復号装置。
【請求項７】
ＬＤＰＣ（Low-Density Parity-Check）符号で符号化された符号語を復号する復号装置において、
前記ＬＤＰＣ符号の検査行列の行重みに対応する行ＬＬＲ（Log-Likelihood Ratio；対数尤度比）を算出する行演算手段と、
前記行演算手段で算出された行ＬＬＲから前記検査行列の列重みに対応する列ＬＬＲを算出する列演算手段と、
前記列演算手段で算出された列ＬＬＲを基にビットごとの推定を行って推定ビット列を算出するビット推定手段と、
前記ビット推定手段で算出された推定ビット列が前記符号語であるか否かを検査する検査手段とを備え、
前記行演算手段は、
前記列ＬＬＲの絶対値の最小値と予め設定された値との大きさ関係を判定し、当該最小値が予め設定された値以上である場合、前記列ＬＬＲの絶対値の最小値、２番目に小さい値、及び３番目に小さい値である最小３値の大きさに応じて、前記最小３値のうちの２値の差を変数δとするδ−ｍｉｎ復号法で規定されるオフセット値を変動させ、当該オフセット値を前記列ＬＬＲの絶対値の最小値から引いた差分値を、当該列ＬＬＲの列に対応する行ＬＬＲとすることを特徴とする復号装置。
【請求項８】
ＬＤＰＣ（Low-Density Parity-Check）符号で符号化された符号語を復号する復号装置において、
前記ＬＤＰＣ符号の検査行列の行重みに対応する行ＬＬＲ（Log-Likelihood Ratio；対数尤度比）を算出する行演算手段と、
前記行演算手段で算出された行ＬＬＲから前記検査行列の列重みに対応する列ＬＬＲを算出する列演算手段と、
前記列演算手段で算出された列ＬＬＲを基にビットごとの推定を行って推定ビット列を算出するビット推定手段と、
前記ビット推定手段で算出された推定ビット列が前記符号語であるか否かを検査する検査手段とを備え、
前記行演算手段は、
絶対値が最小となる列ＬＬＲに対しては、当該最小値の大きさに応じたオフセット値を当該列ＬＬＲの絶対値の２番目に小さい値から引いた差分値を、当該列ＬＬＲの列に対応する行ＬＬＲとし、
絶対値が２番目に小さい列ＬＬＲに対しては、当該列ＬＬＲの絶対値の大きさに応じたオフセット値を当該列ＬＬＲの絶対値の最小値から引いた差分値を、当該列ＬＬＲの列に対応する行ＬＬＲとし、
上記以外の列に対しては、前記列ＬＬＲの絶対値の２番目に小さい値から前記列ＬＬＲの絶対値の最小値を引いた差を変数δとするδ−ｍｉｎ復号法で規定されるオフセット値を当該列ＬＬＲの絶対値の最小値から引いた差分値を、当該列に対応する行ＬＬＲとすることを特徴とする復号装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、誤り訂正符号の復号方法及び復号装置に関するものである。
【背景技術】
【０００２】
低密度パリティ検査符号（Low-Density Parity-Check符号；以下、ＬＤＰＣ符号と称す）は、１の数が疎のｍ×ｎ行列で定義される誤り訂正符号である。この行列を検査行列と呼ぶ。ＬＤＰＣ符号の復号法として、Ｓｕｍ−Ｐｒｏｄｕｃｔ復号法が１９６０年代に考案されている。
しかしながら、Ｓｕｍ−Ｐｒｏｄｕｃｔ復号法は、復号性能が高い反面、演算量が大きく、回路実装は困難である。これに対して、非特許文献１に記載のＯｆｆｓｅｔ  ＢＰ−ｂａｓｅｄ復号法は、Ｓｕｍ−Ｐｒｏｄｕｃｔ復号法を近似計算することにより、演算量を大幅に削減している。
【０００３】
先ず、Ｓｕｍ−Ｐｒｏｄｕｃｔ復号法で行われる具体的な演算について説明する。
この復号法のアルゴリズムは、行演算と列演算と呼ばれる２つの演算からなり、これらの演算を交互に繰り返すことで復号を行う。
行演算は、検査行列の各行に対して行う演算である。
検査行列のｒ行で要素が１である列番号の集合をＮ（ｒ）とおく。Ｎ（ｒ）に含まれる各列ｃに対し、下記式（１）により行対数尤度比（Log-Likelihood Ratio；以下、ＬＬＲと称す）εr,cを計算する。なお、ｚr,cは、後に説明する列演算で計算される列ＬＬＲであるが、繰り返しの１回目は、受信系列からビットごとに計算されるＬＬＲであるλｃが格納される。ｃ’はｃ以外のＮ（ｒ）である。
0005489552.tif 000002
【０００４】
上記（１）式の各演算記号の定義は、下記式（２）〜（５）に示す通りである。
0005489552.tif 000003
0005489552.tif 000004
0005489552.tif 000005
0005489552.tif 000006
【０００５】
次に列演算について説明する。
行演算で求めた行ＬＬＲεr,cから下記式（６）を用い列ＬＬＲｚr,cを計算する。なお、λｃは、上述したＬＬＲである。また、検査行列のｃ列で要素が１である行番号の集合をＭ（ｃ）とおく。ｒ’はｒ以外のＭ（ｃ）である。
0005489552.tif 000007
【０００６】
また、送信ビットの推定を下記式（７）を用いて行う。下記式（７）による演算の結果として、ｚcが０以上であれば、受信系列のｃビット目を１とし、ｚcが０より小さければｃビット目を０と推定する。
0005489552.tif 000008
【０００７】
推定ビット列は、パリティチェックにより符号語であるか否かを判定できる。もし符号語でなければ、列演算で計算した列ＬＬＲを用いて行演算を行い、以降これまで説明した演算をやり直す。予め定めた繰り返し回数の上限に達したか、もしくは推定ビットが符号語であれば、推定ビット列を出力し復号は終了となる。Ｓｕｍ−Ｐｒｏｄｕｃｔ復号法では、上記式（１）で表した行演算に膨大な演算量が必要となる。
【０００８】
非特許文献１のＯｆｆｓｅｔ  ＢＰ−ｂａｓｅｄ復号法は、上記式（１）の代わりに、下記式（８）による行演算を行う。なお、オフセット値αは、検査行列ごとに求める定数であり、復号性能が最も高くなるαを、密度発展法（Density Evolution）を用いて算出する。Ｏｆｆｓｅｔ  ＢＰ−ｂａｓｅｄ復号法では、最小値を求めてオフセット値αを引くだけでよく、行演算の演算量は大幅に削減される。
0005489552.tif 000009
【０００９】
Ｏｆｆｓｅｔ  ＢＰ−ｂａｓｅｄ復号法は、Ｓｕｍ−Ｐｒｏｄｕｃｔ復号法の近似演算であることは既に述べたが、次にそのことをより詳しく説明する。行演算中に現れる上記式（４）で定義される２項演算は、下記式（９）と同値であることが知られている。
0005489552.tif 000010
【００１０】
Ｏｆｆｓｅｔ  ＢＰ−ｂａｓｅｄ復号法では、上記式（９）の第２項以降の対数関数を定数αで近似して得られる。なお、Ｓｕｍ−Ｐｒｏｄｕｃｔ復号法の行演算で用いる上記式（１）には、再帰演算（つまり、上記式（３）で示す演算）が含まれ、この再帰演算による影響をも定数αに包含して近似したものが、Ｏｆｆｓｅｔ  ＢＰ−ｂａｓｅｄ復号法の行演算に用いた上記式（８）である。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】J. Chen, A. Dholakia, E. Eleftheriou, M.P.C. Fossorier, and X.-Y. Hu, “Reduced-Complexity Decoding of LDPC Codes”, IEEE Trans. Communications, vol. 53, issue 8, pp.1288-1299, Aug. 2005.
【発明の概要】
【発明が解決しようとする課題】
【００１２】
上述したように、Ｏｆｆｓｅｔ  ＢＰ−ｂａｓｅｄ復号法では、対数関数及び再帰演算による影響を定数αで近似している。
しかしながら、Ｓｕｍ−Ｐｒｏｄｕｃｔ復号法による実際の数値は、行演算の変数によって大きく変動する。このため、Ｏｆｆｓｅｔ  ＢＰ−ｂａｓｅｄ復号法では、近似精度が低く、復号性能が十分ではないという課題があった。
【００１３】
この発明は、上記のような課題を解決するためになされたもので、Ｏｆｆｓｅｔ  ＢＰ−ｂａｓｅｄ復号法よりＳｕｍ−Ｐｒｏｄｕｃｔ復号法における行演算を高い精度で近似することができ、誤り訂正符号の復号性能を向上することができる復号方法及び復号装置を得ることを目的とする。
【課題を解決するための手段】
【００１４】
この発明に係る復号方法は、例えば、ＬＤＰＣ符号の検査行列の行重みに対応する行ＬＬＲを算出する行演算ステップと、行ＬＬＲから検査行列の列重みに対応する列ＬＬＲを算出する列演算ステップと、列ＬＬＲを基にビットごとの推定を行って推定ビット列を算出するビット推定ステップと、推定ビット列が符号語であるか否かを検査する検査ステップとを備え、行演算ステップと列演算ステップを交互に繰り返して符号語を復号するにあたり、行演算ステップにて、列ＬＬＲの絶対値の最小値と予め設定された値との大きさ関係を判定し、当該最小値が予め設定された値以上である場合、列ＬＬＲの絶対値の最小値の大きさに応じて変動させたオフセット値を当該列ＬＬＲの絶対値の最小値から引いた値を、当該列ＬＬＲの列に対応する行ＬＬＲとすることを特徴とするものである。
【発明の効果】
【００１５】
この発明によれば、行演算において、例えば、列ＬＬＲの絶対値の最小値と予め設定された値との大きさ関係を判定し、当該最小値が予め設定された値以上である場合、列ＬＬＲの絶対値の最小値の大きさに応じて変動させたオフセット値を当該列ＬＬＲの絶対値の最小値から引いた値を、当該列ＬＬＲの列に対応する行ＬＬＲとするので、Ｏｆｆｓｅｔ  ＢＰ−ｂａｓｅｄ復号法よりも、Ｓｕｍ−Ｐｒｏｄｕｃｔ復号法における行演算を高い精度で近似することができ、誤り訂正符号の復号性能を向上することができるという効果がある。
【図面の簡単な説明】
【００１６】
【図１】誤り訂正符号を用いたディジタル通信の手順を概略的に示す図である。
【図２】この発明の実施の形態１による誤り訂正復号方法の流れを示すフローチャートである。
【図３】ｇ（ｘ，δ）とｘの関係を示すグラフである。
【図４】実施の形態１による行演算の一例を示すフローチャートである。
【図５】実施の形態１によるディジタル通信システムの構成を示すブロック図である。
【図６】図５の復号器の構成を示すブロック図である。
【図７】図６の行演算器の構成を示すブロック図である。
【図８】この発明の実施の形態３による行演算器の構成を示すブロック図である。
【図９】この発明の実施の形態４による行演算器の構成を示すブロック図である。
【発明を実施するための形態】
【００１７】
実施の形態１．
図１は、誤り訂正符号を用いたディジタル通信の手順を概略的に示す図である。図１に示すように、ディジタル通信では、先ず送信ビット列を符号化し、符号語とする（手順Ａ）。次に、符号化したビット列を変調する（手順Ｂ）。送信された変調信号は、通信路を介して受信されると、受信側で復調されて受信信号値に変換される（手順Ｃ）。最後に、受信信号値に基づいて軟判定による復号を行い、推定ビット列を得る（手順Ｄ）。なお、この発明では、低密度パリティ検査符号（ＬＤＰＣ符号）を用いて符号化を行う。
【００１８】
図２は、この発明の実施の形態１による誤り訂正復号方法の流れを示すフローチャートである。先ず、図１に示す手順Ｃの復調によって得られた符号語長のビットのそれぞれの受信信号値から、ビットごとにＬＬＲを計算する（ステップＳＴ１）。次に、ステップＳＴ１で得られたＬＬＲを用いて行ＬＬＲを算出し（ステップＳＴ２）、この行ＬＬＲから列ＬＬＲを計算する（ステップＳＴ３）。
【００１９】
続いて、ステップＳＴ３で得られた列ＬＬＲを基にビットごとの推定を行い、推定ビット列を算出する（ステップＳＴ４）。この後、推定ビット列が符号語であるか否かを判定する（ステップＳＴ５）。このとき、符号語であれば（ステップＳＴ５；ＹＥＳ）、この推定ビット列を出力して（ステップＳＴ７）、処理を終了する。
【００２０】
また、推定ビット列が符号語ではないと判定すると（ステップＳＴ５；ＮＯ）、行演算以降の処理の繰り返し回数が最大繰り返し数に到達したか否かを判定する（ステップＳＴ６）。ここで、最大繰り返し数に到達している場合（ステップＳＴ６；ＹＥＳ）には、ステップＳＴ７に移行して推定ビット列を出力し、処理を終了する。
【００２１】
一方、最大繰り返し数に到達していなければ（ステップＳＴ６；ＮＯ）、ステップＳＴ２の行演算処理に戻り、これ以降の処理を繰り返す。ただし、２回目以降の行演算では、直前の列演算で算出した列ＬＬＲに基づいて行演算を行う。
【００２２】
次に、この実施の形態１による行演算の詳細を説明する。
上記式（４）は、ｘ＝ｍｉｎ｛ｘ，ｙ｝と仮定し、δ＝ｙ−ｘとすれば、代入操作によって下記式（１０）に変換することができる。
0005489552.tif 000011
【００２３】
さらに、上記式（１０）の第２項及び第３項を、下記式（１１）のようにｇ（ｘ，δ）とする。
0005489552.tif 000012
【００２４】
図３は、上記式（１１）で算出したｇ（ｘ，δ）とｘの関係を示すグラフであり、横軸がｘで縦軸がｇ（ｘ，δ）である。図３において、δは固定値とし、δ＝２，１，０．５，０．１，０のそれぞれの場合で、上記式（１１）を用いてｇ（ｘ，δ）を算出した結果を図示している。上述のようにＯｆｆｓｅｔ  ＢＰ−ｂａｓｅｄ復号法は、ｇ（ｘ，δ）を定数で近似する復号法であるが、図３に示すグラフから明らかなように、ｘが０に近い場合には、δの値に関わらず、ｇ（ｘ，δ）も０に近い値となる。
【００２５】
そこで、この実施の形態１では、ｘがある定数γより小さい場合にはｇ（ｘ，δ）＝０と近似し、ｘがγ以上の場合には、Ｏｆｆｓｅｔ  ＢＰ−ｂａｓｅｄ復号法と同様にｇ（ｘ，δ）を定数で近似する。以上では、上記式（４）における近似についての説明であるが、上記式（１）の再帰演算（つまり、上記式（３）の演算）の影響を考慮に入れれば、|ｚr,c'|の最小値がγ以上のときのみ|ｚr,c'|の最小値から定数のオフセット値βを引く近似が可能である。これを定式化して表したものが、下記式（１２）である。下記式（１２）中のｓｇr,cは、下記式（１３）で表される。
なお、βとγは、検査行列により異なる値をとる定数である。また、これらの定数は、密度発展法や復号シミュレーション、もしくはその他の手段によって復号性能が最大となる値を見出し、その値に予め設定する。
0005489552.tif 000013
0005489552.tif 000014
【００２６】
次に、上記式（１２）の行演算について説明する。
図４は、実施の形態１による行演算の一例を示すフローチャートであり、上記式（１２）に従った行演算を示している。なお、行演算は、各行それぞれに対して行うが、それを表したのが外側の行ループである。また、検査行列の行列要素が１となる列のそれぞれに対して、行演算では行ＬＬＲを計算する。これを表しているのが内側の列ループである。ここでは、ｒ行の行演算における列ｃに対する行ＬＬＲの演算方法を示す。
【００２７】
先ず、行ｒの行列要素が１の列（列ｃ以外）から列ＬＬＲの絶対値の最小値を計算する（ステップＳＴ１ａ）。この値を最小値ｍｉｎとおく。続いて、最小値ｍｉｎがγ以上であるか否かを判定する（ステップＳＴ２ａ）。最小値ｍｉｎがγ以上であると判定された場合（ステップＳＴ２ａ；ＹＥＳ）は、ステップＳＴ３ａの処理に移行して、当該最小値ｍｉｎから定数βを引いた（ｍｉｎ−β）が０より大きいか否かを判定する。
【００２８】
（ｍｉｎ−β）が０より大きい場合（ステップＳＴ３ａ；ＹＥＳ）、上記式（１３）に従って、ｓｇr,cを計算する（ステップＳＴ４ａ）。この後、ステップＳＴ４ａで算出したｓｇr,cに（ｍｉｎ−β）を掛け算した値であるｓｇr,c・（ｍｉｎ−β）を出力する（ステップＳＴ５ａ）。
【００２９】
一方、最小値ｍｉｎがγに満たない場合（ステップＳＴ２ａ；ＮＯ）は、ステップＳＴ４ａと同様に、上記式（１３）に従って、ｓｇr,cを計算する（ステップＳＴ６ａ）。この後、ｓｇr,cに最小値ｍｉｎを掛け算した値であるｓｇr,c・ｍｉｎを出力する（ステップＳＴ７ａ）。
【００３０】
また、（ｍｉｎ−β）が０以下である場合（ステップＳＴ３ａ；ＮＯ）、０を出力する（ステップＳＴ８ａ）。ここまでが、実施の形態１における行演算であるが、行演算結果が上記式（１２）と等価であれば、上記演算に限定されるものではない。
例えば、ステップＳＴ４ａとステップＳＴ６ａを共通化して、ステップＳＴ２ａの前段で処理を行ってもよい。また、γ≧βであれば、ステップＳＴ３ａ及びステップＳＴ８ａは必要なく、行わなくてもよい。
【００３１】
このようにすることで、Ｓｕｍ−Ｐｒｏｄｕｃｔ復号法における行演算を高い精度で近似でき、誤り訂正符号の復号性能を向上できる。また、演算量の小さいＯｆｆｓｅｔ  ＢＰ−ｂａｓｅｄ復号法と比べても比較演算が１回増加しただけのほぼ同じ演算量であり、Ｓｕｍ−Ｐｒｏｄｕｃｔ復号法に比べれば演算量を格段に削減できる。
【００３２】
次に、上述の誤り訂正復号方法を利用した誤り訂正符号化及び復号を実行するシステム及び当該復号を実行する復号器について説明する。
図５は、実施の形態１によるディジタル通信システムの構成を示すブロック図である。図５において、実施の形態１によるディジタル通信システム１は、送信側の構成として、符号化器２及び変調器３を備え、受信側の構成として、復調器５及び復号器６を備える。符号化器２は、送信ビット列を符号化し符号語とする。変調器３は、符号化器２で符号化されたビット列を変調信号に変換して通信路４へ送信する。受信側では、復調器５が、通信路４を介して受信された信号を復調し、受信信号値を得る。復号器６では、復調器５によって得られた符号語長のビットのそれぞれの受信信号値から推定ビット列を推定し出力する。
【００３３】
図６は、図５の復号器の構成を示すブロック図である。図６において、復号器６は、入力回路７、ＬＬＲ演算器８、行演算器（行演算手段）９、列演算器（列演算手段）１０、ビット推定器（ビット推定手段）１１、パリティ検査器（検査手段）１２、繰り返し回数判定回路１３及び出力回路１４を備える。各構成は、図６に示すように直列に接続されており、さらにパリティ検査器１２と出力回路１４との接続、及び繰り返し回数判定回路１３と行演算器９との接続もなされている。
【００３４】
なお、図６の構成は一例であり、他の構成も可能である。この発明では、行演算器９の内部構成に特徴があり、その他の構成を制約するものではない。例えば、列演算器１０とビット推定器１１（及びパリティ検査器１２）は並列に接続してもよいし、繰り返し回数判定回路１３をパリティ検査器１２の前段に配置しても構わない。
【００３５】
また、復号器６は、図２に示したフローチャートの復号処理を実行する。
復号器６では、復調器５による復調処理で得られた受信信号値を入力すると、入力回路７が、入力した受信信号値を符号語ごとの固まりに分け、適切なタイミングでＬＬＲ演算器８へ出力する。ＬＬＲ演算器８は、符号語長のビットごとの受信信号値から各ＬＬＲを計算する（図２；ステップＳＴ１）。
【００３６】
行演算器９は、ＬＬＲ演算器８で算出されたＬＬＲを用いて行ＬＬＲを計算する（図２；ステップＳＴ２）。ただし、繰り返し回数判定回路１３から処理が渡された場合は、列演算器１０が計算した直近の列ＬＬＲを用いて行ＬＬＲを計算する。列演算器１０は、行演算器９が算出した行ＬＬＲから列ＬＬＲを計算する（図２；ステップＳＴ３）。
【００３７】
ビット推定器１１は、列演算器１０が算出した列ＬＬＲから推定ビット列を計算する（図２；ステップＳＴ４）。パリティ検査器１２は、ビット推定器１１で算出された推定ビット列のパリティチェックを行い（図２；ステップＳＴ５）、推定ビット列が符号語であれば、出力回路１４に推定ビット列を送る。符号語でなければ、その旨を繰り返し回数判定回路１３へ通知する。
【００３８】
繰り返し回数判定回路１３は、行演算（もしくは列演算）を行った回数を符号語ごとにカウントしており、パリティ検査器１２から上記通知を受けると、予め定めた繰り返し回数に到達しているか否かを判定する（図２；ステップＳＴ６）。ここで、予め定めた繰り返し回数に到達していれば、繰り返し回数判定回路１３は、出力回路１４へ推定ビット列を送る。到達していなければ、行演算器９へ処理を渡す。出力回路１４は、上述のようにして得られた推定ビット列を復号器６の出力として出力する（図２；ステップＳＴ７）。
【００３９】
図７は、図６の行演算器の構成を示すブロック図である。図７において、実施の形態１による行演算器９は、入力回路１５、最小２値演算部１６、ｍｉｎのオフセット処理部１７、２ｎｄ  ｍｉｎのオフセット処理部１８、出力行ＬＬＲ選択部１９、ｓｇr,c演算部２０、掛け算回路２１及び出力回路２２を備える。入力回路１５は、行演算器９への入力データが最初に通る回路である。また、出力回路２２は、行演算器９の出力に繋がっている。
【００４０】
また、行演算器９は、図４のフローチャートに相当する行演算を実行する。
図７の構成では、行演算を１行ずつ行い、この行から各列に対して出力する行ＬＬＲを一度に演算する。
先ず、入力回路１５は、検査行列の対応する行において行列要素が１となる全ての列の列ＬＬＲを出力する。
最小２値演算部１６は、入力回路１５から入力した列ＬＬＲの絶対値から最小値ｍｉｎとその列ＬＬＲの列番号ｃ’、及び２番目に小さい値である２ｎｄ  ｍｉｎを計算して、出力する（図４；ステップＳＴ１ａ）。
【００４１】
ｍｉｎのオフセット処理部１７では、最小値ｍｉｎがγ以上であるか否かを判定（図４；ステップＳＴ２ａ）し、最小値ｍｉｎがγ未満であれば、最小値ｍｉｎをそのまま出力行ＬＬＲ選択部１９へ出力する。また、最小値ｍｉｎがγ以上であると、ｍｉｎのオフセット処理部１７は、（ｍｉｎ−β）が０よりも大きいか否かを判定する（図４；ステップＳＴ３ａ）。（ｍｉｎ−β）が０よりも大きい場合、ｍｉｎのオフセット処理部１７は、（ｍｉｎ−β）を出力行ＬＬＲ選択部１９へ出力する。一方、（ｍｉｎ−β）が０以下であれば、出力行ＬＬＲ選択部１９へ０を出力する。
なお、２ｎｄ  ｍｉｎのオフセット処理部１８においても、ｍｉｎのオフセット処理部１７と同様の動作をする。
【００４２】
出力行ＬＬＲ選択部１９では、列ｃ’に対する行ＬＬＲについては、２ｎｄ  ｍｉｎのオフセット処理部１８によるオフセット処理後の値（２ｎｄ  ｍｉｎ−β）、それ以外の列に対しては、ｍｉｎのオフセット処理部１７によるオフセット処理後の値（ｍｉｎ−β）が出力されるよう出力値を選択する。
【００４３】
ｓｇr,c演算部２０は、入力回路１５から列ＬＬＲの符号を入力し、上記式（１３）を用いて、ｓｇr,cの演算をそれぞれの列に対して行う（図４；ステップＳＴ４ａ、ステップＳＴ６ａ）。
掛け算回路２１は、各列に対して行ＬＬＲの絶対値とｓｇr,c（＝＋１又は−１）との掛け算を行い（図４；ステップＳＴ５ａ、ステップＳＴ７ａ）、行ＬＬＲの正負を決定する。出力回路２２は、掛け算回路２１による演算結果の行ＬＬＲの出力制御を行う。
【００４４】
なお、この実施の形態１による行演算器９は、図７に示した回路構成に限定されるものではない。例えば、図４のフローチャートに忠実に従って行演算を行う回路としてもよいし、演算内容が等価であれば他の手段による回路であってもよい。演算結果さえ同じであれば、等価な復号性能となる。
【００４５】
以上のように、この実施の形態１によれば、図７に示すような回路構成によって、図４の手順で行演算を行うことにより、Ｓｕｍ−Ｐｒｏｄｕｃｔ復号法における行演算を高い精度で近似することができ、誤り訂正符号の復号性能を向上させることができる。
また、Ｏｆｆｓｅｔ  ＢＰ−ｂａｓｅｄ復号法と比べて比較演算が１回増加しただけのほぼ同じ演算量であることから、回路規模の小さいＯｆｆｓｅｔ  ＢＰ−ｂａｓｅｄ復号法と同等の回路規模で実現できる。このため、Ｓｕｍ−Ｐｒｏｄｕｃｔ復号法に比べて、演算量を格段に削減できる上、回路規模の小規模化も実現することができる。
【００４６】
なお、上記実施の形態１では、γによって２通りに場合分けしたが、より多くの場合分けをすることも可能である。つまり、|ｚr,c'|の最小値の大きさによってオフセット値を変動させ、|ｚr,c'|の最小値からそれぞれの場合に応じたオフセット値を引くという方法が可能である。場合分けを多くすることによって演算量は大きくなるが、より近似精度が高くなり復号性能は向上する。
【００４７】
実施の形態２．
上記実施の形態１で近似を行った関数ｇ（ｘ，δ）は、上記式（１１）の通り、ｘとδを変数としている。この関数ｇ（ｘ，δ）において、上記実施の形態１では、変数ｘの値の変動を考慮して近似を行った。
しかしながら、上記実施の形態１で示した図３のグラフから明らかなように、変数ｘがある程度大きい領域では関数ｇ（ｘ，δ）の値が変数δの影響によって大きく変動する。上記実施の形態１は、この変動を無視してオフセット値βを定数として近似している。
【００４８】
そこで、この実施の形態２では、変数δの値によってオフセット値を変動させる方法について述べる。なお、変数δによってオフセット値を変動させる技術としては、例えば、参考文献１に記載のδ−ｍｉｎ復号法がある。
（参考文献１）阪井塁、松本渉、吉田英夫、“更新式の近似に基づくＬｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ−Ｃｈｅｃｋ  符号簡易復号法の検討”，電子情報通信学会論文誌Ａ，ｖｏｌ．Ｊ９０−Ａ，ｎｏ．２，ｐｐ．８３−９１，Ｆｅｂ．２００７．
【００４９】
参考文献１に記載のδ−ｍｉｎ復号法は、変数ｘによる関数ｇ（ｘ，δ）の変動を無視し、変数δのみからオフセット値を決定する手法であるため、図３のグラフで示したように変数ｘが０に近い値のときの近似精度が低い。
そこで、この実施の形態２では、ｘの値がγ未満ときは、ｇ（ｘ，δ）＝０と近似し、γ以上の場合は、δ−ｍｉｎ復号法で用いられているオフセット値Ｄ（δ）を用いる。つまり、下記式（１４）のようにする。なお、Ｄ（δ）は、下記式（１５）に示す関数である。変数δはδ＝ｙ−ｘである。
0005489552.tif 000015
0005489552.tif 000016
【００５０】
以上のように、この実施の形態２によれば、上記式（１４）で上記式（４）の２項演算を置き換え、ｇ（ｘ，δ）を上述のように近似することで、上記実施の形態１における行演算よりも近似精度が向上し、復号性能を高くすることができる。
【００５１】
実施の形態３．
上記実施の形態２は関数ｇ（ｘ，δ）のみを近似したが、この実施の形態３では、上記実施の形態１のように、行演算の再帰演算（上記式（３）の演算）も近似する。つまり、上記実施の形態１の行演算（上記式（１２）の演算）のオフセット値βを、上記実施の形態２におけるＤ（δ）で置き換えた下記式（１６）を利用する。ただし、δは|ｚr,c'|の最小値と２番目に小さい値との差とする。このように行演算を近似することによって、行演算の近似精度と復号性能が上記実施の形態１よりも高く、演算量が上記実施の形態２よりも小さくなる。
0005489552.tif 000017
図８は、この発明の実施の形態３による行演算器の構成を示すブロック図であり、既に説明した図６における行演算器の内部を実施の形態３に合わせて図示したものである。図８において、実施の形態３による行演算器（行演算手段）９Ａは、入力回路１５、ｓｇr,c演算部２０、掛け算回路２１、出力回路２２、最小３値演算部２３、オフセット処理部２４及び出力行ＬＬＲ選択部２５を備える。入力回路１５、ｓｇr,c演算部２０、掛け算回路２１及び出力回路２２の動作は、上記実施の形態１と同じであるので、異なる部分について説明する。
【００５２】
最小３値演算部２３は、列ＬＬＲの絶対値のうち、最小値ｍｉｎとその列番号ｃ’、２番目に小さい値２ｎｄ  ｍｉｎとその列番号ｃ’’、そして３番目に小さい値３ｒｄ  ｍｉｎを演算して出力する。
【００５３】
オフセット処理部２４は、上記式（１６）に従ってオフセット値を計算してオフセット処理を行うが、次の３つを出力する。
１つは、ｍｉｎと２ｎｄ  ｍｉｎから計算するｍｉｎのオフセット処理後の値であり、ｍｉｎがγ未満ならｍｉｎを出力し、ｍｉｎがγ以上ならδ＝２ｎｄ  ｍｉｎ−ｍｉｎとして、ｍｉｎ−Ｄ（δ）もしくは０を出力する。
残りの２つの出力も同様であり、ｍｉｎと３ｒｄ  ｍｉｎから計算するｍｉｎのオフセット処理後の値、２ｎｄ  ｍｉｎと３ｒｄ  ｍｉｎから計算する２ｎｄ  ｍｉｎのオフセット処理後の値をそれぞれ計算し出力する。
【００５４】
出力行ＬＬＲ選択部２５は、列ｃ’に対する行ＬＬＲとして２ｎｄ  ｍｉｎと３ｒｄ  ｍｉｎとから計算した２ｎｄ  ｍｉｎのオフセット処理後の値を選択する。また、列ｃ’’に対する行ＬＬＲとしては、３ｒｄ  ｍｉｎとｍｉｎとから計算したｍｉｎのオフセット処理後の値を選択し、それ以外の列に対しては、２ｎｄ  ｍｉｎとｍｉｎとから計算したｍｉｎのオフセット処理後の値を選択し、それぞれを出力する。
【００５５】
以上のように、この実施の形態３によれば、図８に示すような回路構成で、上記式（１６）を利用した行演算を行うことにより、上記実施の形態１よりも、Ｓｕｍ−Ｐｒｏｄｕｃｔ復号法における行演算を高い精度で近似することができ、誤り訂正符号の復号性能を向上させることができる。
【００５６】
実施の形態４．
上記実施の形態３は復号能力が高いものの、最小３値を演算する必要があり、回路規模が大きくなる。そこで、この実施の形態４では、上記実施の形態１と同様に、最小２値の演算を行いながら、上記実施の形態３と同様のδによるオフセット処理を部分的に行う構成について述べる。
【００５７】
図９は、この発明の実施の形態４による行演算器の構成を示すブロック図である。図９において、実施の形態４による行演算器（行演算手段）９Ｂは、入力回路１５、ｓｇr,c演算部２０、掛け算回路２１、出力回路２２、最小２値演算部１６ａ、オフセット処理部２４ａ及び出力行ＬＬＲ選択部２５ａを備える。入力回路１５、ｓｇr,c演算部２０、掛け算回路２１及び出力回路２２の動作は、上記実施の形態１及び上記実施の形態３と同じである。最小２値演算部１６ａ、オフセット処理部２４ａ及び出力行ＬＬＲ選択部２５ａの動作が、上記実施の形態３と異なる。
【００５８】
最小２値演算部１６ａは、上記実施の形態１で示した最小２値演算部１６と一部異なり、最小値ｍｉｎとその列番号ｃ’、２番目に小さい値２ｎｄ  ｍｉｎに加えて、２ｎｄ  ｍｉｎの列番号ｃ’’も出力する。
【００５９】
また、オフセット処理部２４ａは、３つの出力を行う。
１つは、ｍｉｎに対して、オフセット値を定数βとして上記実施の形態１と同様の処理を行って得られた値（ｍｉｎ−β）である。
２つ目は、２ｎｄ  ｍｉｎに対しても同様に、オフセット値を定数βとして、上記実施の形態１と同様の処理を行って得られた値（２ｎｄ  ｍｉｎ−β）である。
３つ目は、上記実施の形態３と同様の処理で、δ＝２ｎｄ  ｍｉｎ−ｍｉｎとし、オフセット値をＤ（δ）としてオフセット処理を行って得られた値（ｍｉｎ−Ｄ（δ））である。
【００６０】
出力行ＬＬＲ選択部２５ａは、列ｃ’に対しては、２ｎｄ  ｍｉｎにβによってオフセット処理をした値（２ｎｄ  ｍｉｎ−β）を選択する。また、列ｃ’’に対しては、ｍｉｎにβによってオフセット処理をした値（ｍｉｎ−β）を選択し、それ以外の列に対しては、ｍｉｎにＤ（δ）でオフセット処理をした値（ｍｉｎ−Ｄ（δ））を選択する。出力行ＬＬＲ選択部２５ａの後段における処理は、上記実施の形態１と同様である。
【００６１】
以上のように、この実施の形態４によれば、図９に示すような回路構成で、上記の行演算を行うことで、上記実施の形態１による行演算よりも、列ｃ’、列ｃ’’以外に対する近似精度が高くなり、復号性能を向上できる。また、最小３値の演算を最小２値の演算に抑えることができることから、上記実施の形態３よりも回路規模を小さくできる。
【符号の説明】
【００６２】
１  ディジタル通信システム、２  符号化器、３  変調器、４  通信路、５  復調器、６  復号器、７  入力回路、８  ＬＬＲ演算器、９，９Ａ，９Ｂ  行演算器（行演算手段）、１０  列演算器（列演算手段）、１１  ビット推定器（ビット推定手段）、１２  パリティ検査器（検査手段）、１３  繰り返し回数判定回路、１４  出力回路、１５  入力回路、１６，１６ａ  最小２値演算部、１７  ｍｉｎのオフセット処理部、１８  ２ｎｄ  ｍｉｎのオフセット処理部、１９，２５，２５ａ  出力行ＬＬＲ選択部、２０  ｓｇr,c演算部、２１  掛け算回路、２２  出力回路、２３  最小３値演算部、２４，２４ａ  オフセット処理部。
【図１】
0005489552.tif 000018
【図２】
0005489552.tif 000019
【図３】
0005489552.tif 000020
【図４】
0005489552.tif 000021
【図５】
0005489552.tif 000022
【図６】
0005489552.tif 000023
【図７】
0005489552.tif 000024
【図８】
0005489552.tif 000025
【図９】
0005489552.tif 000026