(57)【要約】【課題】  メッセージパッシングアルゴリズムの対数領域での演算の実現に際し、チェックノードから変数ノードへのメッセージの演算結果を、回路又は計算機により容易に求める。【解決手段】  メッセージパッシングアルゴリズムを用いてＬＤＰＣ符号を復号する復号装置は、メッセージを、２の冪乗からなる実数ａを底とした対数尤度比とし、ビットノードからのメッセージＱｍ，ｎを受け取り、チェックノードからのメッセージＲｍ，ｎを算出するチェックノード処理演算器を有する。チェックノード処理演算器は、メッセージＱｍ，ｎの絶対値ｘを変換してｆＱ（ｘ）を出力する変換器１１ｔと、一のビットノードを除く全ビットノードからのＱｍ，ｎの絶対値ｘを変換器１１ｔにより変換した総和を入力ｙとし、該入力ｙを所定区間に区分し、この区間内の数値をｇＱ（ｙ）に変換する変換器１４ｔとを有し、ｆＱ（ｘ）及び入力ｙの区間の境界値を２の冪乗で表現する。【選択図】図６
2005223440.tif 000002
【特許請求の範囲】
【請求項１】
低密度パリティ検査行列に対応した複数のチェックノード及び複数の変数ノードの間でメッセージを伝搬させるメッセージパッシングアルゴリズムを用いて低密度パリティ検査符号を復号する復号装置において、
上記メッセージを、２の冪乗である実数ａを底とした対数尤度比とし、
変数ノードからチェックノードへ渡される第１のメッセージを受け取り、チェックノードから変数ノードへ渡す第２のメッセージを算出するチェックノード処理演算器と、
上記チェックノード処理演算器により算出された上記第２のメッセージを受け取り上記第１のメッセージを算出する変数ノード処理演算器とを有し、
上記チェックノード処理演算器は、上記第１のメッセージの絶対値ｘを変換し、２の冪乗の値として出力する第１の変換回路を有する
ことを特徴とする復号装置。
【請求項２】
上記第１の変換回路は、関数Ｆ（ｘ）＝２Ｃａ−ｘ（Ｃは任意の定数）により上記第１のメッセージの絶対値ｘを変換する
ことを特徴とする請求項１記載の復号装置。
【請求項３】
上記チェックノード処理演算器は、一の変数ノードを除く全変数ノードからの上記第１のメッセージの絶対値ｘを上記第１の変換回路により変換した値の総和を入力ｙとし、当該入力ｙを２の冪乗を境界値として規定した区間に区分し、該区間内の数値を整数に変換する第２の変換回路を有する
ことを特徴とする請求項１記載の復号装置。
【請求項４】
上記チェックノード処理演算器は、一の変数ノードを除く全変数ノードからの上記第１のメッセージの絶対値ｘを上記第１の変換回路により変換した値の総和を入力ｙとし、当該入力ｙを２の冪乗を境界値として規定した区間に区分し、該区間内の数値を上記関数Ｆ（ｘ）の逆関数Ｇ（ｙ）により整数に変換する第２の変換回路を有する
ことを特徴とする請求項２記載の復号装置。
【請求項５】
上記第１のメッセージの絶対値ｘは、０を含み一定の間隔を有する離散値から該間隔の１／２だけオフセットした値のいずれかである
ことを特徴とする請求項１記載の復号装置。
【請求項６】
入力となる上記メッセージの事前確率は、０を含み一定の間隔を有する離散値から該間隔の１／２だけオフセットした値のいずれかである
ことを特徴とする請求項１記載の復号装置。
【請求項７】
変数ノードｎからチェックノードｍへ渡されるメッセージが０及び１である確率をそれぞれｑ０ｍ，ｎ、ｑ１ｍ，ｎとし、チェックノードｍから変数ノードｎへ渡されるメッセージが０及び１である確率をそれぞれｒ０ｍ，ｎ、ｒ１ｍ，ｎとしたとき、
上記第１のメッセージＱｍ，ｎ及び第２のメッセージＲｍ，ｎは上記確率ｑ０ｍ，ｎ、ｑ１ｍ，ｎ及び上記確率ｒ０ｍ，ｎ、ｒ１ｍ，ｎを、底が実数ａの対数尤度比で表現したものであって、
上記関数Ｆ（ｘ）は、上記第１のメッセージＱｍ，ｎの絶対値ｘ（＝｜ｌｏｇａ（ｑ０ｍ，ｎ／ｑ１ｍ，ｎ）｜）をｆ（ｘ）（＝−Ｃｌｎ｜ｑ０ｍ，ｎ−ｑ１ｍ，ｎ｜）の近似値に変換するものである
ことを特徴とする請求項２記載の復号装置。
【請求項８】
上記チェックノード処理演算器は、一の変数ノードを除く全変数ノードからの上記第１のメッセージを上記第１の変換回路により変換した総和を入力ｙとし、当該入力ｙを２の冪乗を境界値として規定した区間に区分し、該区間内の数値を上記関数Ｆ（ｘ）の逆関数Ｇ（ｙ）により整数に変換する第２の変換回路を有し、
上記逆関数Ｇ（ｙ）は、上記区間内の数値を、ｙ（＝−Ｃｌｎ｜ｒ０ｍ，ｎ−ｒ１ｍ，ｎ｜）からｇ（ｙ）（＝｜ｌｏｇａ（ｒ０ｍ，ｎ／ｒ１ｍ，ｎ）｜）の近似値に変換するものである
ことを特徴とする請求項７記載の復号装置。
【請求項９】
上記第１の変換回路は、上記第１のメッセージの絶対値ｘに基づき上記２の冪乗の値を出力する出力部を有する
ことを特徴とする請求項１記載の復号装置。
【請求項１０】
上記第１の変換回路は、実数ａ＝２Ｎ（Ｎは正の整数）としたとき、上記２の冪乗の値の仮数部を１、上記２の冪乗の値の指数部を上記第１のメッセージの絶対値ｘの整数部分×Ｎ×（−１）として出力する出力部を有する
ことを特徴とする請求項１記載の復号装置。
【請求項１１】
上記第２の変換回路は、上記入力ｙが属する区間を判定する判定部と、該判定結果に基づき整数を出力する出力部とを有する
ことを特徴とする請求項３記載の復号装置。
【請求項１２】
上記第２の変換回路は、実数ａ＝２Ｎ（Ｎは正の整数）としたとき、上記入力ｙの指数部分を取り出す指数部分取出部と、該取り出した指数部分をＮで除した値を超えない最大の整数の絶対値を出力する出力部とを有する
ことを特徴とする請求項３記載の復号装置。
【請求項１３】
上記変数ノード処理演算器により算出された上記第２のメッセージから事後確率を算出し、該事後確率の硬判定復号結果を符号検出結果として出力する復号手段を有する
ことを特徴とする請求項１記載の復号装置。
【請求項１４】
低密度パリティ検査行列に対応した複数のチェックノード及び複数の変数ノードの間でメッセージを伝搬させるメッセージパッシングアルゴリズムを用いて低密度パリティ検査符号を復号する復号方法において、
上記メッセージを、２の冪乗である実数ａを底とした対数尤度比とし、
変数ノードからチェックノードへ渡される第１のメッセージを受け取り、チェックノードから変数ノードへ渡す第２のメッセージを算出するチェックノード処理演算工程と、
上記チェックノード処理演算工程にて算出された上記第２のメッセージを受け取り上記第１のメッセージを算出する変数ノード処理演算工程とを有し、
上記チェックノード処理演算工程は、上記第１のメッセージの絶対値ｘを変換して２の冪乗の値として出力する第１の変換工程を有する
ことを特徴とする復号方法。
【請求項１５】
上記第１の変換工程では、関数Ｆ（ｘ）＝２Ｃａ−ｘ（Ｃは任意の定数）により上記第１のメッセージの絶対値ｘを変換する
ことを特徴とする請求項１４記載の復号方法。
【請求項１６】
上記チェックノード処理演算工程は、一の変数ノードを除く全変数ノードからの上記第１のメッセージの絶対値ｘを上記第１の変換工程にて変換した値の総和を入力ｙとし、当該入力ｙを２の冪乗を境界値として規定した区間に区分し、該区間内の数値を整数に変換する第２の変換工程を有する
ことを特徴とする請求項１５記載の復号方法。
【請求項１７】
上記チェックノード処理演算工程は、一の変数ノードを除く全変数ノードからの上記第１のメッセージの絶対値ｘを上記第１の変換工程にて変換した値の総和を入力ｙとし、当該入力ｙを２の冪乗を境界値として規定した区間に区分し、該区間内の数値を上記関数Ｆ（ｘ）の逆関数Ｇ（ｙ）により整数に変換する第２の変換工程を有する
ことを特徴とする請求項１５記載の復号方法。
【請求項１８】
上記第１のメッセージの絶対値ｘは、整数値から０．５オフセットした値である
ことを特徴とする請求項１７記載の復号方法。
【請求項１９】
低密度パリティ検査行列に対応した複数のチェックノード及び複数の変数ノードの間でメッセージを伝搬させるメッセージパッシングアルゴリズムを用いて低密度パリティ検査符号を復号する復号装置において、
上記メッセージを、２の冪乗である実数ａを底とした対数尤度比とし、
変数ノードからチェックノードへ渡される第１のメッセージを受け取り、チェックノードから変数ノードへ渡す第２のメッセージを算出するチェックノード処理演算器と、
上記チェックノード処理演算器により算出された上記第２のメッセージを受け取り上記第１のメッセージを算出する変数ノード処理演算器とを有し、
上記チェックノード処理演算器は、上記第１のメッセージの絶対値ｘを変換して出力する第１の変換回路と、一の変数ノードを除く全変数ノードからの上記第１のメッセージの絶対値ｘを該第１の変換回路により変換した総和を入力ｙとし、当該入力ｙを２の冪乗を境界値として規定した区間に区分し、該区間内の数値を整数に変換する第２の変換回路とを有する
ことを特徴とする復号装置。
【請求項２０】
低密度パリティ検査行列に対応した複数のチェックノード及び複数の変数ノードの間でメッセージを伝搬させるメッセージパッシングアルゴリズムを用いて低密度パリティ検査符号を復号する復号方法において、
上記メッセージを、２の冪乗である実数ａを底とした対数尤度比とし、
変数ノードからチェックノードへ渡される第１のメッセージを受け取り、チェックノードから変数ノードへ渡す第２のメッセージを算出するチェックノード処理演算工程と、
上記チェックノード処理演算工程にて算出された上記第２のメッセージを受け取り上記第１のメッセージを算出する変数ノード処理演算工程とを有し、
上記チェックノード処理演算工程は、変数ノードからの第１のメッセージの絶対値ｘを変換して出力する第１の変換工程と、一の変数ノードを除く全変数ノードからの第１のメッセージの絶対値ｘを該第１の変換工程にて変換した総和を入力ｙとし、当該入力ｙを２の冪乗を境界値として規定した区間に区分し、該区間内の数値を整数に変換する第２の変換工程とを有する
ことを特徴とする復号方法。
【請求項２１】
低密度パリティ検査符号に符号化され記録されたデータを再生する情報処理装置において、
低密度パリティ検査符号に符号化して記録されたデータを読み出し、低密度パリティ検査行列に対応した複数のチェックノード及び複数の変数ノードの間でメッセージを伝搬させるメッセージパッシングアルゴリズムを用いて上記データを復号して再生する再生手段を有し、
上記再生手段は、
上記メッセージを、２の冪乗である実数ａを底とした対数尤度比とし、
変数ノードからチェックノードへ渡される第１のメッセージを受け取り、チェックノードから変数ノードへ渡す第２のメッセージを算出するチェックノード処理演算器と、
上記チェックノード処理演算器により算出された上記第２のメッセージを受け取り上記第１のメッセージを算出する変数ノード処理演算器とを有し、
上記チェックノード処理演算器は、変数ノードからの第１のメッセージの絶対値ｘを変換して２の冪乗の値として出力する第１の変換回路を有する
ことを特徴とする情報処理装置。
【請求項２２】
上記低密度パリティ検査符号に符号化する符号化手段と、
上記低密度パリティ検査符号に符号化されたデータを記録する記録手段とを有する
ことを特徴とする請求項２１記載の情報処理装置。
【請求項２３】
低密度パリティ検査符号に符号化され記録されたデータを再生する情報処理方法において、
低密度パリティ検査符号に符号化して記録されたデータを読み出し、低密度パリティ検査行列に対応した複数のチェックノード及び複数の変数ノードの間でメッセージを伝搬させるメッセージパッシングアルゴリズムを用いて上記データを復号して再生する再生工程を有し、
上記再生工程は、
上記メッセージを、２の冪乗である実数ａを底とした対数尤度比とし、
変数ノードからチェックノードへ渡される第１のメッセージを受け取り、チェックノードから変数ノードへ渡す第２のメッセージを算出するチェックノード処理演算工程と、
上記チェックノード処理演算工程にて算出された上記第２のメッセージを受け取り上記第１のメッセージを算出する変数ノード処理演算工程とを有し、
上記チェックノード処理演算工程は、変数ノードからの第１のメッセージの絶対値ｘを変換して２の冪乗の値として出力する第１の変換工程を有する
ことを特徴とする情報処理方法。
【請求項２４】
上記低密度パリティ検査符号に符号化する符号化工程と、
上記低密度パリティ検査符号に符号化されたデータを記録する記録工程とを有する
ことを特徴とする請求項２３記載の情報処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、低密度パリティ検査符号（ＬＤＰＣ：low density parity check code）の軟判定復号を行うための復号装置及び方法、並びに復号装置を利用した情報処理装置及び方法に関する。
【背景技術】
【０００２】
低密度パリティ検査符号（以下、ＬＤＰＣ符号という。）は、１９６２年、Robert G. Gallagerによって発表された線形符号の一種であり、そのパリティ検査行列の非零の要素数が全要素数に対して少ない（低密度である）ことが特徴となっている（下記非特許文献１参照）。
【０００３】
また、ＬＤＰＣ符号はパリティ検査行列の２部グラフ（bipartite graph）に、短いサイクルが含まれないことから、繰り返し復号によって良好なビットエラー特性を示すことが知られている。
【０００４】
雑音や消失のある通信路では、情報語が受信側で正しく推定されるように誤り訂正符号を用いることが一般的である。図２３は、ＬＤＰＣ符号を用いた通信システムを示す一例である。図２３に示すように、通信装置２００は、情報語（メッセージ）からＬＤＰＣ符号を生成するＬＤＰＣ符号化部２０１と、符号語を伝送する通信路２０２と、通信路２０２からの受信語を受け取り符号を検出するＬＤＰＣ復号部２０３とを有する。
【０００５】
送信側では情報語をＬＤＰＣ符号化し、通信路２０１に送る。受信側では通信路２０１で付加された雑音を含む信号を受信し、送信側で行った符号化の規則に基づき復号を行い、情報語を推定する。ＬＤＰＣ符号を用いた場合は、通常、軟判定情報を使用した繰り返し復号が行われる。また、ＬＤＰＣ符号とよく似た性質をもつターボ符号などにおいても軟判定情報を使用した繰り返し復号が行われる。
【０００６】
また、ＬＤＰＣ符号は上記通信システムに限らず、記録再生チャネルにも応用することができる。図２４は、ＬＤＰＣ符号を用いた記録再生システムを示すブロック図である。図２４に示すように、記録再生システム２１０は、音楽又は映像等のメッセージにからＬＤＰＣ符号を生成するＬＤＰＣ符号化部２１１と、生成されたＬＤＰＣ符号をチャネル符号化して記録し、また、記録された信号を読み出してチャネル復号を行う記録／再生部２１２と、チャネル復号されたデータから符号検出するＬＤＰＣ復号部２１３とを有する。ＬＤＰＣ復号部２１３にて符号検出されたデータは、メッセージに復号される。
【０００７】
すなわち、記録時には情報後をＬＤＰＣ符号化し、記録媒体に記録する。再生時には雑音を含んだ信号を記録媒体から読み取り、必要に応じてチャネルの符号間干渉に応じたチャネル検出、および、記録時に行ったチャネル符号化の復号を行った後、記録時に行ったＬＤＰＣ符号化の規則に基づき復号を行い、情報語を推定する。
【０００８】
次に、これらの通信システム又は記録再生システムなどに使用されるＬＤＰＣ符号について詳細に説明する。符号長ＮのＬＤＰＣ符号の任意の符号語ベクトルｃは、Ｍ行Ｎ列のパリティ検査行列をＨとすると、下記式（１）を満たす。
【０００９】
【数１】
2005223440.tif 000003
【００１０】
上式（１）は、Ｍ個のパリティ検査方程式を表している。Ｈの階数（rank）が（Ｎ−Ｋ）（Ｋは次元）で与えられるとき、このＬＤＰＣ符号の符号化率はＫ／Ｎで与えられる。Ｍ＞Ｎ−Ｋの場合、冗長なパリティ検査方程式があることを意味する。
【００１１】
図１は、２元（binary）ＬＤＰＣ符号のパリティ検査行列の例である。この７行２１列の行列の階数は６であり、これによって定まる符号は符号長Ｎ＝２１、次元Ｋ＝１５の線形符号となる。この行列において各行における非零の要素数（“１”の数）（ハミング重み）Ｗｒは全て６、各列における非零の要素数（“１”の数）（ハミング重み）Ｗｃは全て２である。このようにＷｒ、Ｗｃが均一なパリティ検査行列を持つＬＤＰＣ符号はレギュラー（regular）ＬＤＰＣ符号と呼ばれる。
【００１２】
ＬＤＰＣ符号は、線形符号であり、２元に限るものではなく、２元符号以外の場合においても同様の議論ができることは勿論であるが、以下の説明においては、全て２元符号の場合を例に説明する。
【００１３】
上述したような通信システム又は記録再生システムにおいて、ＬＤＰＣ符号化部２０１または２１１では、ＬＤＰＣ符号復号部２０３又はＬＤＰＣ符号復号部２１３においてパリティ検査行列によって符号検出するために、情報語（メッセージ）をＬＤＰＣ符号化する。ＬＤＰＣ符号を得るためには、始めに、Ｍ行Ｎ列、Ｋ次元のパリティ検査行列Ｈから、Ｋ行Ｎ列の生成行列Ｇ（ＧＨＴ＝０を満たす）を求めておく。そして、Ｋビットの２元メッセージ（ｍ０ｍ１・・・ｍＫ―１）に生成行列Ｇを乗算することによりＮビットの符号語（（ｍ０ｍ１・・・ｍＫ−１）Ｇ＝（ｃ０ｃ１・・・ｃＮ−１））を得る。このようにして得られた符号語は、変調器を介して通信路へ送出され、受信側で受信信号として受信される。この受信信号が復調されたのち、パリティ検査行列により復号され、送信メッセージの推定値（Ｋビット（ｍ０＾ｍ１＾・・・ｍＫ−１＾）（＾はハットを示す。以下同じ。））として出力される。
【００１４】
次に、受信された受信信号から符号を検出する符号検出方法について説明する。ＬＤＰＣ符号は、パリティ検査行列或いは２部グラフを元に、メッセージパッシング（message-passing）アルゴリズムによって符号検出可能なことが知られている。Ｍ行Ｎ列のパリティ検査行列を表現した２部グラフは、チェック（check）に対応するＭ個のノード（node）（チェックノード）、変数（variable）に対応するＮ個のノード（変数ノード）、及びノードを接続するエッジ（edge）により構成される。エッジはパリティ検査行列の非零要素の場所に対応しており、第ｍ行第ｎ列の要素が零でない場合にのみｍ番目のチェックノードとｎ番目の変数ノードとがエッジで接続される。上述したように、ここでは２元符号の場合について説明するため、以降では、変数ノードをビットノードと表現する。
【００１５】
図２は、図１のパリティ検査行列に対応した２部グラフを示しており、丸（〇）で表された７個のチェックノードＸｍ（Ｘ０〜Ｘ６）と、四角（□）で表された２１個のビットノードＹｎ（Ｙ０〜Ｙ２０）とで構成されている。各チェックノードＸｍには６本のエッジが、各ビットノードＹｎには２本のエッジがそれぞれ接続されている。
【００１６】
ＬＤＰＣ符号は、エッジで接続されたチェックノードＸｍとビットノードＹｎとのノード間にメッセージを伝搬させ、ビットノードＸｍからチェックノードＹｎ、チェックノードＹｎからビットノードＸｍへのメッセージ交換を繰り返して行う、メッセージパッシングアルゴリズム（あるいはsum-productアルゴリズム）によるＳＩＳＯ（Soft-In Soft-Out）復号方法により符号検出することができる。このメッセージパッシングアルゴリズムは、次のような手順を繰り返すことで実現される。
【００１７】
［１］手順０−初期化
各ビットノードＹｎから出るすべてのエッジについて、ビットノードＹｎからチェックノードＸｍに伝搬されるメッセージｑ０ｍ，ｎ，ｑ１ｍ，ｎを事前確率ｐ０ｎ，ｐ１ｎに初期化する。ここでｐｘｎとはビットｎが“x”である事前確率を表すものとする。
【００１８】
［２］手順１−チェックノードにおける処理
各チェックノードＸｍから出るすべてのエッジについて、チェックノードＸｍからビットノードＹｎに伝搬されるメッセージr０ｍ，ｎ，r１ｍ，ｎを次式に従って求める。
【００１９】
【数２】
2005223440.tif 000004
【００２０】
［３］手順２−ビットノードにおける処理
必要に応じて各ビットの事後確率ｑ０ｎ、ｑ１ｎを、次式により求める。
【００２１】
【数３】
2005223440.tif 000005
【００２２】
更に繰り返しが必要な場合、次式に従ってビットノードＹｎからチェックノードＸｍに伝搬されるメッセージを計算する。
【００２３】
【数４】
2005223440.tif 000006
【００２４】
メッセージパッシングアルゴリズムによる復号は、終了条件を満たすまで手順１と手順２とを繰り返し、最後に硬判定復号で情報語が推定される。繰り返しの終了条件は、
１）繰り返しが予め定めた回数に達した時点で終了
２）予め定めた繰り返し回数に達していない場合でも硬判定結果がパリティチェックを満たせば終了
等が一般的である。ここで、パリティチェックは、下記式（５）のように示される。
【００２５】
【数５】
2005223440.tif 000007
【００２６】
ここで、上記のアルゴリズムと等価な計算方法として、対数尤度比ＬＬＲ（Log-Likelihood Ratio）を用いて対数領域での計算式に変形すれば、乗算に相当する演算は、全て加算に置き換えられ、ハードウェアやソフトウェアによる処理を簡略化できる。対数領域における演算のアルゴリズムを以下に示す。
【００２７】
［１］手順０−初期化
各ビットノードＹｎから出るすべてのエッジについて、エッジを伝搬するメッセージＱｍ，ｎを各ビットの事前対数尤度比Ｐｎで初期化する。ここで、エッジを伝搬するメッセージＱｍ，ｎ及び各ビットの事前対数尤度比Ｐｎは、夫々下記式（６−１）及び（６−２）のように定義される。
【００２８】
【数６】
2005223440.tif 000008
【００２９】
［２］手順１−チェックノードにおける処理
各チェックノードＸｍから出るすべてのエッジについて、エッジを伝搬するメッセージＲｍ，ｎを下記式（７−１）により計算する。ここで、Ａｍ、Ｂｍ、及びメッセージＲｍ，ｎは下記（７−２）乃至（７−４）のように定義され、関数ｆ、関数ｇ、αｍ，ｎ、及びβｍ，ｎは下記（７−５）乃至（７−８）で示される。
【００３０】
【数７】
2005223440.tif 000009
【００３１】
［３］手順２−ビットノードにおける処理
各ビットの下記式（８）に定義される事後対数尤度比Ｑｎを、下記式（９）により求める。
【００３２】
【数８】
2005223440.tif 000010
【００３３】
【数９】
2005223440.tif 000011
【００３４】
更に繰り返しが必要な場合、下記式（１０）に従ってビットノードＹｎからチェックノードＸｍに伝搬されるメッセージＱｍ，ｎを計算する。
【００３５】
【数１０】
2005223440.tif 000012
【００３６】
次に、以上のような手順１及び手順２の演算を繰り返し行ってＬＤＣＰ符号を復号する復号装置の一具体例について説明する。図２５は、T. Zhang等による下記非特許文献２に記載の復号装置を示すブロック図である。
【００３７】
図２５に示すように、復号装置３００は、事前値を格納するメモリ３０１と、ビットノードＹｎにおける演算を行うビットノード処理演算器３０２と、チェックノードＸｍにおける演算を行うチェックノード処理演算器３０３と、ビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎ及びチェックノードＸｍからビットノードＹｎへのメッセージＲｍ，ｎを格納するメモリ３０４と、ビットノード処理演算器３０２の結果に応じて硬判定復号を行い、推定された情報語を出力する硬判定復号器３０５とから構成される。この復号装置３００は、繰り返し毎に同じ演算器を使用し、且つ各演算器が時分割で複数のノードの処理を行うものである。
【００３８】
このようなＬＤＰＣ符号復号装置３００には雑音を含んだ受信語または再生信号が入力され、事前値を格納するメモリ３０１に保管される。先に示した手順２の処理を行うビットノード処理演算器３０２と、手順１の処理を行うチェックノード処理演算器３０３との間にて、メッセージを格納するメモリ３０４を介して繰り返しメッセージ伝搬を行い、最後に硬判定復号器３０５にて硬判定復号を行って情報語を推定する。なお、図２５では初期化や繰り返し終了条件の判定部は省略している。
【００３９】
次に、上述した手順１に従って、メモリ３０４からビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎを読み出し、チェックノードＸｍからビットノードＹｎへ渡すメッセージＲｍ，ｎを計算するチェックノード処理演算器３０３の構成について具体的に説明する。
【００４０】
図２６は、チェックノード処理演算器の主要部の一例を示す回路図である。ここでは、特に図１に示すパリティ検査行列の第１行目のチェックに対応する演算器の例を示す。
【００４１】
図２６に示すように、チェックノード処理演算器４００は、対応する位置のメッセージＱｍ，ｎの絶対値βｍ，ｎを関数ｆに変換する変換器４０１ｔ（図２６では、４０１０〜４０１５）と、これらの和である上記式（７−３）に示すＢｍを求める加算器４０２と、Ｂｍと対応するメッセージＱｍ，ｎから得られた関数ｆとの差を求める加算器４０３ｔと、加算器４０３ｔの出力を関数ｇに変換する変換器４０４ｔと、メッセージＱｍ，ｎの符号αｍ，ｎを全て乗算して上記式（７−２）に示すＡｍを求める乗算器４０７と、乗算器４０７の出力（Ａｍ）と対応するメッセージＱｍ，ｎの符号αｍ，ｎとを乗算する乗算器４０６ｔと、変換器４０４ｔと乗算器４０６ｔとの出力を乗算してメッセージＲｍ，ｎを出力する乗算器４０５ｔとを有する。
【００４２】
ここで、チェックノードＸｍからビットノードＹｎへのメッセージＲｍ，ｎを求める際に用いる関数ｆは、対数尤度比｜ｌｎ（ｑ０ｍ，ｎ／ｑ１ｍ，ｎ）｜を、−ｌｎ｜ｑ０ｍ，ｎ−ｑ１ｍ，ｎ｜へ変換する関数である。また関数ｇは、関数ｆの逆の変換であり、−ｌｎ｜ｒ０ｍ，ｎ−ｒ１ｍ，ｎ｜を対数尤度比｜ｌｎ（ｒ０ｍ，ｎ／ｒ１ｍ，ｎ）｜へ変換する関数となっている。関数ｆ及び関数ｇは、双曲線関数や対数関数を含む複雑な形となるため、実際には近似値で実現することが多い。また、回路やソフトウェアでＬＤＰＣ符号の復号を行う場合は、ノード間を伝搬するメッセージが取り得る値を有限個の離散値に限定して扱うのが一般的である。
【００４３】
例えば下記特許文献１においては、関数ｆ（ｘ）の近似として、変換後の値を有限個の離散値で表したｆＱ（ｘ）を下記（１１）のように定義している。
【００４４】
【数１１】
2005223440.tif 000013
【００４５】
この式（１１）に示すようなｆＱ（ｘ）を実現するためには、例えば上述の変換器４０１ｔにおいて、ｘの取り得るすべての値をインデックスとしてｆＱ（ｘ）をテーブル化しておき、このテーブルを参照して与えられるｘ（＝メッセージＱｍ，ｎの絶対値βｍ，ｎ）に対応するｆＱ（ｘ）を出力する方法や、次に説明するように、ｘがどの区間に属するかを演算により求めてそれに応じて値を出力する方法などが考えられる。
【００４６】
図２７は、入力ｘからｆＱ（ｘ）を出力する変換器の一例を示す回路図である。変換器４１０は、与えられるｘを、それぞれ０．１，０．３５，０．６０，０．９０，１．２，１．６，２．３以下かを判定する比較部４１１０〜４１１６と、比較部４１１の判定値とその前段の判定値の反転出力とのＡＮＤを出力するＡＮＤゲート４１２１〜４１２６と、最後段の比較部４１１６の判定値を反転して出力するＮＯＴゲート４１５と、最前段の比較部４１１０、ＡＮＤゲート４１２１〜４１２６、及びＮＯＴゲート４１５の出力が入力され、それらの出力に応じてｆＱ（ｘ）を選択する選択回路４１６とを有している。すなわち、先ず、ｘが上記式（１１）の８つの範囲のうちどの範囲に入るかを判定し、その結果に基づき選択回路４１６がｆＱ（ｘ）の値を選択し、これを示す値を出力する。
【００４７】
【非特許文献１】Ｒ．Ｇ．ギャラガ（R. G. Gallager）著，「ＬＤＣＰ符号（Low Density Parity Check Codes）」，エムアイティープレス（MIT Press），１９６３年
【非特許文献２】T. Zhang and K. K. Parhi著,“A 54 MBP （3,6）-REGULAR FPGA LDPC DECODER”，アイイーイーイー・ワークショップ・オン・シグナル・プロセッシング・システムズ（IEEE Workshop on Signal Processing Systems），２００２年，ｐｐ  １２７−１３２
【特許文献１】特開２００２−１１８４７４号公報
【発明の開示】
【発明が解決しようとする課題】
【００４８】
しかしながら、チェックノード処理演算器における関数ｆの変換、及びその逆変換ｇにおいて、上述したようにｘの取り得るすべての値をインデックスとし、ｆＱ（ｘ）をテーブル化してＲＯＭや配列などに格納しておき読み出す方法は、ｘの量子化の単位が小さくなるに従いテーブルが長くなるため、必要となるＲＯＭや配列が大きくなるという問題点がある。また、ｘがどの範囲に入るかを図２７に示すような回路により判定すると、ｘの区間の数（上記式（１１）に示すｆＱ（ｘ）の場合は８）に応じて比較部４１１ｔの数が多くなり、また、出力値を選択する選択回路４１６の構造が複雑になるという問題点がある。また、関数ｇも関数ｆと同じ関数で与えられるため、同様の問題点がある。
【００４９】
本発明は、このような従来の実情に鑑みて提案されたものであり、メッセージパッシングアルゴリズムの対数領域での演算の実現に際し、チェックノードから変数ノードへのメッセージの演算結果を、回路又は計算機により容易に求めることができる復号装置及び方法、並びに情報処理装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【００５０】
上述した目的を達成するために、本発明に係る復号装置は、低密度パリティ検査行列に対応した複数のチェックノード及び複数の変数ノードの間でメッセージを伝搬させるメッセージパッシングアルゴリズムを用いて低密度パリティ検査符号を復号する復号装置において、上記メッセージを、２の冪乗である実数ａを底とした対数尤度比とし、変数ノードからチェックノードへ渡される第１のメッセージを受け取り、チェックノードから変数ノードへ渡す第２のメッセージを算出するチェックノード処理演算器と、上記チェックノード処理演算器により算出された上記第２のメッセージを受け取り上記第１のメッセージを算出する変数ノード処理演算器とを有し、上記チェックノード処理演算器は、上記第１のメッセージの絶対値ｘを変換し、２の冪乗の値として出力する第１の変換回路を有することを特徴とする。
【００５１】
本発明においては、第１の変換回路にて変換した値を２の冪乗の値として出力することにより、出力する値を２進数表現に適した値とすることで、第１の変換回路における演算を簡略化するか又は回路構成を簡略化することができる。
【００５２】
また、上記第１の変換回路は、関数Ｆ（ｘ）＝２Ｃａ−ｘ（Ｃは任意の定数）により上記第１のメッセージの絶対値ｘを変換することができ、定数Ｃを適宜選択することで、第１のメッセージの絶対値ｘの関数Ｆ（ｘ）による変換値を２の冪乗とすることができる。
【００５３】
更に、上記チェックノード処理演算器は、一の変数ノードを除く全変数ノードからの上記第１のメッセージの絶対値ｘを上記第１の変換回路により変換した値の総和を入力ｙとし、当該入力ｙを２の冪乗を境界値として規定した区間に区分し、該区間内の数値を整数に変換する第２の変換回路を有することができる。この第２の変換回路は、入力ｙを複数の区間に区分して各区間内の数値を代表値である整数に変換して出力するものであるが、上記区間の境界値を２進数表現に適した数値である２の冪乗で表現したため、入力ｙがどの区間に該当するかを簡単に判別することができ、第２の変換回路における演算を簡略化するか又は回路構成を簡略化することができる。
【００５４】
更にまた、上記チェックノード処理演算器は、一の変数ノードを除く全変数ノードからの上記第１のメッセージの絶対値ｘを上記第１の変換回路により変換した値の総和を入力ｙとし、当該入力ｙを２の冪乗を境界値として規定した区間に区分し、該区間内の数値を上記関数Ｆ（ｘ）の逆関数Ｇ（ｙ）により整数に変換する第２の変換回路を有することができ、定数Ｃを適宜選択することで、当該入力ｙを区分する区間の境界値を２の冪乗とすることができる。
【００５５】
また、上記第１のメッセージの絶対値ｘは、０を含み一定の間隔を有する離散値から該間隔の１／２だけオフセットした値のいずれかとすることができ、メッセージの絶対値ｘを整数値から０．５オフセットした離散的な値とすれば、メッセージの対数尤度比表現における底ａが２の冪乗となるいかなる場合においても、定数Ｃを適切に選択することにより関数Ｆ（ｘ）、Ｇ（ｙ）の実現を簡略化できると共に、関数Ｆ（ｘ）を使用したときの近似による誤差を小さくすることができる。
【００５６】
更に、上記第１の変換回路は、上記第１のメッセージの絶対値ｘに基づき上記２の冪乗の値を出力する出力部を有するものとすれば、出力を２進数の固定小数点で表現することができ、実数ａ＝２Ｎ（Ｎは正の整数）としたとき、上記２の冪乗の値の仮数部を１、上記２の冪乗の値の指数部を上記第１のメッセージの絶対値ｘの整数部分×Ｎ×（−１）として出力する出力部を有するものとすれば、出力を２進数の浮動小数点で表現することができる。
【００５７】
更にまた、上記第２の変換回路は、上記入力ｙが属する区間を判定する判定部と、該判定結果に基づき整数を出力する出力部とを有するものとすることができる。入力ｙが２進数の固定小数点で表現されている場合、入力ｙは２の冪乗を境界値として規定した区間に区分しているため、判定部は、入力ｙのビットパターンに基づきｙが属する区間を判定するのみでよく、ビットパターンの最上位ビット（ＭＳＢ）から連続する０の個数をカウントすることで容易に入力ｙの区間を判定して整数の代表値を出力することができる。
【００５８】
また、上記第２の変換回路は、実数ａ＝２Ｎ（Ｎは任意の整数）としたとき、上記入力ｙの指数部分を取り出す指数部分取出部と、（該取り出した指数部分／Ｎ）を超えない最大の整数の絶対値を出力する出力部とを有することができ、入力ｙが２進数の浮動小数点で表現されている場合には、取り出した指数部分の値に基づき整数の代表値を出力することができる。
【００５９】
本発明に係る他の復号装置は、低密度パリティ検査行列に対応した複数のチェックノード及び複数の変数ノードの間でメッセージを伝搬させるメッセージパッシングアルゴリズムを用いて低密度パリティ検査符号を復号する復号装置において、上記メッセージを、２の冪乗である実数ａを底とした対数尤度比とし、変数ノードからチェックノードへ渡される第１のメッセージを受け取り、チェックノードから変数ノードへ渡す第２のメッセージを算出するチェックノード処理演算器と、上記チェックノード処理演算器により算出された上記第２のメッセージを受け取り上記第１のメッセージを算出する変数ノード処理演算器とを有し、上記チェックノード処理演算器は、上記第１のメッセージの絶対値ｘを変換して出力する第１の変換回路と、一の変数ノードを除く全変数ノードからの上記第１のメッセージの絶対値ｘを該第１の変換回路により変換した総和を入力ｙとし、当該入力ｙを２の冪乗を境界値として規定した区間に区分し、該区間内の数値を整数に変換する第２の変換回路とを有することを特徴とする。
【００６０】
本発明においては、入力ｙを区分し、区間内の数値を代表値に変換する第２の変換回路において、各区間の境界値を２の冪乗として２進数表現に適した数値とすることができ、したがって入力ｙがどの区間に該当するかを簡単に判別することができるので、第２の変換回路における演算を簡略化するか又は回路構成を簡略化することができる。
【００６１】
本発明に係る情報処理装置は、低密度パリティ検査符号に符号化され記録されたデータを再生する情報処理装置において、低密度パリティ検査符号に符号化して記録されたデータを読み出し、低密度パリティ検査行列に対応した複数のチェックノード及び複数の変数ノードの間でメッセージを伝搬させるメッセージパッシングアルゴリズムを用いて上記データを復号して再生する再生手段を有し、上記再生手段は、上記メッセージを、２の冪乗である実数ａを底とした対数尤度比とし、変数ノードからチェックノードへ渡される第１のメッセージを受け取り、チェックノードから変数ノードへ渡す第２のメッセージを算出するチェックノード処理演算器と、上記チェックノード処理演算器により算出された上記第２のメッセージを受け取り上記第１のメッセージを算出する変数ノード処理演算器とを有し、上記チェックノード処理演算器は、変数ノードからの第１のメッセージの絶対値ｘを変換して２の冪乗の値として出力する第１の変換回路を有することを特徴とする。
【発明の効果】
【００６２】
本発明に係る復号装置及び方法によれば、低密度パリティ検査行列に対応した複数のチェックノード及び複数の変数ノードの間でメッセージを伝搬させるメッセージパッシングアルゴリズムを用いて低密度パリティ検査符号を復号する。この場合、上記メッセージを、２の冪乗である実数ａを底とした対数尤度比とし、変数ノードからチェックノードへ渡される第１のメッセージを受け取り、チェックノードから変数ノードへ渡す第２のメッセージを算出するチェックノード処理演算器（演算工程）と、上記チェックノード処理演算器により算出された上記第２のメッセージを受け取り上記第１のメッセージを算出する変数ノード処理演算器（演算工程）とにより、メッセージを算出する。ここで、チェックノード処理演算器（演算工程）は、変数ノードからの第１のメッセージの絶対値ｘを変換して出力する第１の変換回路（変換工程）と、一の変数ノードを除く全変数ノードからの第１のメッセージを該第１の変換回路により変換した総和を入力ｙとし、該入力ｙを所定区間に区分し、該区間内の数値を代表値に変換する第２の変換回路（変換工程）とを有し、第１の変換回路（変換工程）の出力又は入力ｙの区間の境界値の少なくともいずれか一方を２の冪乗で表現し、２進数での表現に適した値とすることで、チェックノード処理演算器における演算又は回路構成を簡略化することができる。
【００６３】
本発明に係る情報処理装置及び方法によれば、上述のようなＬＤＰＣ符号の復号装置又は復号方法を適用することで、演算器の演算又は回路構成を簡略化した情報処理装置及び方法を提供することができる。
【発明を実施するための最良の形態】
【００６４】
以下、本発明を適用した最良の実施の形態について、図面を参照しながら詳細に説明する。この実施の形態は、本発明を、メッセージパッシングアルゴリズムを用いてＬＤＰＣ符号を検出する際のチェックノード処理演算器の回路構成を極めて簡素化した復号装置及びこれを備える各種情報処理装置に適用したものである。
【００６５】
具体的には、チェックノード処理演算器において、チェックノードからビットノードへのメッセージを演算するときに使用する関数ｆ及びその逆関数ｇの演算を工夫するものであるが、その演算方法を説明する前に、本発明の理解を容易にするため、メッセージパッシングアルゴリズムによる符号検出方法について説明しておく。
【００６６】
（１）パリティ検査行列
図１は、７行２１列のパリティ検査行列を示す図である。図１に示すパリティ検査行列は、階数が６、これによって定まる符号は符号長Ｎ＝２１、次元Ｋ＝１５の線形符号となる。この行列において各行における非零、即ち１の要素数Ｗｒは全て６で一定であり、各列における非零、即ち１の要素数Ｗｃは全て２で一定であるregular ＬＤＰＣ符号である。
【００６７】
図２は、図１に示すパリティ検査行列に対応した２部グラフ示す図である。図２に示すように、Ｍ行Ｎ列のパリティ検査行列を表現した２部グラフは、チェックに対応するＭ個のノード（チェックノードＸｍ）、変数に対応するＮ個のノード（ビットノード（変数ノード）Ｙｎ）、及びチェックノードＸｍとビットノードＹｎとを接続するエッジにより構成される。エッジはパリティ検査行列の非零要素の場所に対応しており、第ｍ行第ｎ列の要素が零でない場合にのみｍ番目のチェックノードＸｍとｎ番目のビットノードＹｎとがエッジで接続される。
【００６８】
（２）メッセージパッシングアルゴリズム
ここでは先ず、本発明の理解を容易とするため、エッジで接続されたチェックノードＸｍとビットノードＹｎとのノード間にメッセージを伝搬させる通常のメッセージパッシングアルゴリズムによるＬＤＰＣ符号の符号検出方法について説明する。メッセージパッシングアルゴリズムによるＬＤＰＣ符号の符号検出は、次のような手順を繰り返すことで実現される。
【００６９】
［１］手順０−初期化
各ビットノードＹｎから出るすべてのエッジについて、ビットノードＹｎからチェックノードＸｍに伝搬されるメッセージｑ０ｍ，ｎ，ｑ１ｍ，ｎを事前確率ｐ０ｎ，ｐ１ｎに初期化する。ここでｐｘｎとはビットｎが“ｘ”である事前確率を表すものとする。
【００７０】
［２］手順１−チェックノードにおける処理
各チェックノードＸｍから出るすべてのエッジについて、チェックノードＸｍからビットノードＹｎに伝搬されるメッセージr０ｍ，ｎ，r１ｍ，ｎを次式に従って求める。
【００７１】
【数１２】
2005223440.tif 000014
【００７２】
［３］手順２−ビットノードにおける処理
必要に応じて各ビットの事後確率ｑ０ｎ、ｑ１ｎを、次式により求める。
【００７３】
【数１３】
2005223440.tif 000015
【００７４】
更に繰り返しが必要な場合、次式に従ってビットノードＹｎからチェックノードＸｍに伝搬されるメッセージを計算する。
【００７５】
【数１４】
2005223440.tif 000016
【００７６】
メッセージパッシングアルゴリズムによる復号は、終了条件を満たすまで手順１と手順２とを繰り返し、最後に硬判定復号で情報語が推定される。繰り返しの終了条件は、
１）繰り返しが予め定めた回数に達した時点で終了
２）予め定めた繰り返し回数に達していない場合でも硬判定結果がパリティチェックを満たせば終了
等が一般的である。ここで、パリティチェックは、下記式（５）のように示される。
【００７７】
【数１５】
2005223440.tif 000017
【００７８】
終了条件が上記の１番目としたときの、復号アルゴリズムのフローチャートを図３に示す。即ち、図３に示すように、ビットノードＹｎからチェックノードＸｍへのメッセージｑ０ｍ，ｎ，ｑ１ｍ，ｎを事前確率ｐ０ｎ，ｐ１ｎに初期化する。（ステップＳ１：手順０）。
【００７９】
次に、各チェックノードＸｍからビットノードＹｎへのメッセージr０ｍ，ｎ，r１ｍ，ｎを計算する（ステップＳ２：手順１）。
【００８０】
そして、各ビットノードＹｎにおいて、事後確率ｑ０ｎ、ｑ１ｎ及び硬判定結果ｃ＾を計算し、更にチェックノードＸｍへのメッセージｑ０ｍ，ｎ，ｑ１ｍ，ｎを計算する（ステップＳ３：手順２）。
【００８１】
その後、規定の繰り返し回数に達しているか否かを判定し（ステップＳ４）、規定の繰り返し回数を超えない場合は、ステップＳ２〜ステップＳ３の処理を繰り返し、規定の繰り返し回数を超えた場合には、硬判定復号し（ステップＳ５）、処理を終了する。また、上述した如く、予め定めた繰り返し回数に達していない場合であっても、硬判定結果ｃ＾がパリティチェックＨｃ＾＝０を満たしている場合は、処理を終了するようにしてもよい。
【００８２】
このようなアルゴリズムと等価な計算方法として、対数尤度比ＬＬＲ（Log-Likelihood Ratio）を用いて対数領域での計算式に変形すれば、乗算に相当する演算は、全て加算に置き換えられ、ハードウェアやソフトウェアによる処理を簡略化できる。対数領域における演算のアルゴリズムを以下に示す。
【００８３】
［１］手順０−初期化
各ビットノードＹｎから出るすべてのエッジについて、エッジを伝搬するメッセージＱｍ，ｎを各ビットの事前対数尤度比Ｐｎで初期化する。ここで、エッジを伝搬するメッセージＱｍ，ｎ及び各ビットの事前対数尤度比Ｐｎは、夫々下記式（６−１）及び（６−２）のように定義される。
【００８４】
【数１６】
2005223440.tif 000018
【００８５】
［２］手順１−チェックノードにおける処理
各チェックノードＸｍから出るすべてのエッジについて、エッジを伝搬するメッセージＲｍ，ｎを下記式（７−１）により計算する。ここで、Ａｍ、Ｂｍ、及びメッセージＲｍ，ｎは下記式（７−２）乃至（７−４）のように定義され、関数ｆ、関数ｇ、αｍ，ｎ、及びβｍ，ｎは下記（７−５）乃至（７−８）で示される。
【００８６】
【数１７】
2005223440.tif 000019
【００８７】
［３］手順２−ビットノードにおける処理
各ビットの下記式（８）に定義される事後対数尤度比Ｑｎを、下記式（９）により求める。
【００８８】
【数１８】
2005223440.tif 000020
【００８９】
【数１９】
2005223440.tif 000021
【００９０】
更に繰り返しが必要な場合、下記式（１０）に従ってビットノードＹｎからチェックノードＸｍに伝搬されるメッセージＱｍ，ｎを計算する。
【００９１】
【数２０】
2005223440.tif 000022
【００９２】
ここで、チェックノードＸｍからビットノードＹｎへのメッセージＲｍ，ｎを求める際に使用される、上記（７−２）及び（７−３）にて定義されるＡｍ、Ｂｍの物理的な意味については次のように解釈できる。Ａｍｆ（Ｂｍ）を計算すると、下記式（１２）のように書ける。
【００９３】
【数２１】
2005223440.tif 000023
【００９４】
ここで、ｒ０ｍ、ｒ１ｍを、以下式（１３−１）及び（１３−２）のように定義した。
【００９５】
【数２２】
2005223440.tif 000024
【００９６】
ビットノードＹｎからチェックノードＸｍへのメッセージｑ０ｍ，ｎ及びｑ１ｍ，ｎを夫々下記（１４−１）及び（１４−２）としたとき、上記式（１３−１）に示すｒ０ｍは、チェックを満たす確率に相当する。
【００９７】
【数２３】
2005223440.tif 000025
【００９８】
即ち、Ａｍ、Ｂｍは、各ビットノードＹｎ（ｎ∈Ｎ（ｍ））からチェックノードＸｍへのメッセージＱｍ，ｎ又はｑ０ｍ，ｎ、ｑ１ｍ，ｎに基づいた、チェックを満たす確率の間接的な表現に相当する。
【００９９】
以上の対数尤度比を用いた場合であって、終了条件が上記の１番目、即ち、手順１と手順２の繰り返しが予め定めた回数に達した時点で終了としたときの、復号アルゴリズムのフローチャートを図４に示す。即ち、図４に示すように、ビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎを事前対数尤度比Ｐｎに初期化する。（ステップＳ１１：手順０）。
【０１００】
次に、各チェックノードＸｍからビットノードＹｎへのメッセージＲｍ，ｎを計算する（ステップＳ１２：手順１）。
【０１０１】
そして、各ビットノードＹｎにおいて、事後対数尤度比Ｑｎ及び硬判定結果ｃ＾を計算し、更にチェックノードＸｍへのメッセージＱｍ，ｎを計算する（ステップＳ１３：手順２）。
【０１０２】
その後、規定の繰り返し回数に達しているか否かを判定し（ステップＳ１４）、規定の繰り返し回数を超えない場合は、ステップＳ１２〜ステップＳ１３の処理を繰り返し、規定の繰り返し回数を超えた場合には、硬判定復号し（ステップＳ１５）、処理を終了する。また、上述した如く、予め定めた繰り返し回数に達していない場合であっても、硬判定結果ｃ＾がパリティチェックＨｃ＾＝０を満たしている場合は、処理を終了するようにしてもよい。
【０１０３】
（３）実施の形態
次に、本発明の実施の形態について詳細に説明する。先ず、以上のような手順１及び手順２の演算を繰り返し行ってＬＤＣＰ符号を復号する復号装置の一具体例について説明する。図５は、本実施の形態における復号装置を示すブロック図である。
【０１０４】
図５に示すように、復号装置１は、事前値が入力され、事前値を格納するメモリ２と、ビットノードＹｎにおける演算を行うビットノード処理演算器３と、チェックノードＸｍにおける演算を行うチェックノード処理演算器４と、ビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎ及びチェックノードＸｍからビットノードＹｎへのメッセージＲｍ，ｎを格納するメモリ５と、ビットノード処理演算器３の結果に応じて硬判定復号を行い、推定された情報語を出力する硬判定復号器６とから構成される。この復号装置１は、繰り返し毎に同じ演算器を使用し、且つ各演算器が時分割で複数のノードの処理を行うものである。
【０１０５】
このようなＬＤＰＣ符号復号装置１には雑音を含んだ受信語または再生信号が入力され、事前値を格納するメモリ２に保管される。そして先に示した手順２の処理を行うビットノード処理演算器３と手順１の処理を行うチェックノード処理演算器４との間にて、メッセージを格納するメモリ５を介してメッセージを繰り返し伝搬し、最後に硬判定復号器６にて硬判定復号を行って情報語を推定する。なお、図５では初期化や繰り返し終了条件の判定部は省略している。
【０１０６】
また、図５では、メモリ５は、ビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎ及びチェックノードＸｍからビットノードＹｎへのメッセージＲｍ，ｎを格納するものとしたが、メッセージＱｍ，ｎを格納するメモリと、メッセージＲｍ，ｎを格納するメモリとを別々に設けてもよい。
【０１０７】
図６は、チェックノード処理演算器の主要部の一例を示す回路図である。ここでは、特に図１に示すパリティ検査行列の第１行目のチェックに対応する演算器の例を示す。
【０１０８】
図６に示すように、チェックノード処理演算器１０は、対応する位置のメッセージＱｍ，ｎの絶対値βｍ，ｎが入力され、これを関数ｆにより変換する第１の変換回路としての変換器１１ｔ（１１０〜１１５）と、これらの和からＢｍを求める加算器１２と、対応するメッセージＱｍ，ｎの絶対値βｍ，ｎから得られる関数ｆ（βｍ，ｎ）を加算器１２の出力であるＢｍから減算する加算器１３ｔと、加算器１３ｔの加算結果を関数ｇにより変換する第２の変換回路としての変換器１４ｔと、メッセージＱｍ，ｎの符号αｍ，ｎを全て乗算してＡｍを求める乗算器１７と、乗算器１７の出力であるＡｍに、対応するメッセージＱｍ，ｎの符号αｍ，ｎを乗算する乗算器１６ｔと、変換器１４ｔの出力と乗算器１６ｔの出力とを乗算してメッセージＲｍ，ｎを出力する乗算器１５ｔとを有する。
【０１０９】
例えば、変換器１１ｔにより、一のチェックノードに接続された全ビットノードからのメッセージＱｍ，ｎの絶対値βｍ，ｎの変換値を求め、加算器１２によりこれらの総和を求め、この総和（Ｂｍ）から、上記一のチェックノードからメッセージを渡される所定のビットノードのメッセージＱｍ，ｎの絶対値βｍ，ｎの変換器１１ｔによる変換値のみが減算された値が変換器１４ｔの入力ｙとなり、これより当該所定のビットノードに渡されるメッセージＲｍ，ｎを乗算器１５ｔから出力する。具体的には、図１に示すパリティ検査行列に対応する場合、例えば加算器１３０は、加算器１２から出力されるＢｍからメッセージＱ０，０の絶対値β０，０を変換した値のみを減算し、この値を変換器１４０の入力とする。そしてこの出力から乗算器１５０を介して１番目のビットノードＹ０に出力するメッセージＲ０，０を出力する。
【０１１０】
このチェックノード処理演算器１０に入力されるメッセージＱｍ，ｎは、対数尤度比として表現されており、チェックノード処理における式（２−１）及び（２−２）の乗算に対応する演算を式（７−１）、あるいは式（７−１）及び（７−３）の加算に対応する演算に置き換えて簡単にするために、このチェックノード処理演算器１０では、先ず変換器１１ｔにより、対数尤度比で示される、第１のメッセージとしてのメッセージＱｍ，ｎの絶対値βｍ，ｎを関数ｆにより変換する。そして、所定の演算を行った後、関数ｆの加算の形で表現されている値を変換器１４ｔにより再び対数尤度比に変換する。
【０１１１】
ここで、本実施の形態においては、関数ｆによる変換処理、及びその逆関数ｇによる変換処理、すなわち変換器１１ｔ、１４ｔにおける出力値や入力を区分する境界値を回路や計算機にて扱いやすい値とすることでチェックノード処理演算器４の構成を簡素化するものである。具体的には、メッセージＱｍ，ｎ及びＲｍ，ｎを、２の冪乗からなる実数ａを底とした対数尤度比で表し、関数ｆを２Ｃａ−ｘ（Ｃは任意の定数）に近似する。この際、定数Ｃ、実数ａの値を適切に選択することで、メッセージＱｍ，ｎの絶対値βｍ，ｎを関数ｆの近似式で変換した値ｆＱ（ｘ）を２の冪乗として２進数表現に適した値にすると共に、ｆＱ（ｘ）の加算値を入力ｙとし、関数ｆの近似式の逆関数ｇＱ（ｙ）を求める際に、整数値ｇＱ（ｙ）を出力するｙの区間の境界値を２の冪乗で表すことで、チェックノード処理演算器１０における回路構成を簡素化するものである。
【０１１２】
次に、その具体的な方法について説明する。上述したように、図６に示す変換器１１ｔは、所定の関数を使用し、式（２−１）及び（２−２）の乗算を式（７−１）、あるいは式（７−１）及び（７−３）の加算に変換するための関数により演算を行うものであり、変換器１４ｔは、変換器１１ｔによる変換後に行った演算の結果を対数尤度比に戻す関数を使用して演算を行うものである。すなわち、変換器１１ｔは、メッセージＱｍ，ｎの絶対値βｍ，ｎを入力として、所定の関数を用いて対数尤度比｜ｌｏｇａ（ｑ０ｍ，ｎ／ｑ１ｍ，ｎ）｜から−Ｃｌｎ｜ｑ０ｍ，ｎ−ｑ１ｍ，ｎ｜への変換を行うものであり、変換器１４ｔは、変換器１１ｔの出力の加減値を入力として、変換器１１ｔに使用された関数の逆関数を用いて、−Ｃｌｎ｜ｒ０ｍ，ｎ−ｒ１ｍ，ｎ｜から対数尤度比｜ｌｏｇａ（ｒ０ｍ，ｎ／ｒ１ｍ，ｎ）｜への変換を行うものである。
【０１１３】
従来の関数ｆは、上記式（７−５）のように定義されている。ここで、関数ｆをｅ−ｘでテイラー展開し、１次の項で打ち切ると２ｅ−ｘとなり、ｘが大きくなるに従いｆ（ｘ）は２ｅ−ｘに近づくことがわかる。
【０１１４】
図７は、縦軸を対数軸としたときのｆ（ｘ）及び２ｅ−ｘを示すグラフ図である。この図７に示すように、ｘが大きくなるに従ってｆ（ｘ）は２ｅ−ｘに漸近しており、よく近似できていることがわかる。ここで、対数尤度比を一般的に下記式（１５−１）〜（１５−４）のように定義し直す。ａは任意の実数を示す。
【０１１５】
【数２４】
2005223440.tif 000026
【０１１６】
つまり、対数の底をすべて実数ａに変換する。このとき、上記アルゴリズムにおける関数ｆは例えば下記式（１６）のように定義することができる。
【０１１７】
【数２５】
2005223440.tif 000027
【０１１８】
ここで、Ｃは任意の定数を示す。図８は、ａ＝２、Ｃ＝１／√２（＝２−０．５）としたときのｆ（ｘ）及び近似式Ｆ（ｘ）＝２Ｃａ−ｘ＝２０．５−ｘを示すグラフ図である。この図８に示すように、ｆ（ｘ）は先の議論と同様に、近似式Ｆ（ｘ）＝２Ｃａ−ｘに漸近することが確かめられる。
【０１１９】
ここで、以下の説明においては、下記式（１７）に示すように、このｆ（ｘ）の近似式をＦ（ｘ）ということとする。
【０１２０】
【数２６】
2005223440.tif 000028
【０１２１】
通常、回路や計算機で数値を表現する際には、固定小数点や浮動小数点が用いられる。いずれの表現方法においても数値表現のビット数は限られており、表現できる数値の精度（仮数部のビット数、あるいは有効桁数）には制限がある。そのため、回路や計算機において表すことのできる数値は離散的なものとなる。上記式（１７）で示した関数の近似式Ｆ（ｘ）は連続な関数として定義できるが、ｘの取り得る値が離散的で且つ有限であるため、近似式Ｆ（ｘ）の出力も離散的な有限個の値しか取り得ない。以下では有限個の離散値をとるＦ（ｘ）を、ｆＱ（ｘ）として区別して書く場合がある。ここで、ｘが取りうる離散値を、０を含み一定の間隔を有する離散値のいずれかである場合と、０を含み一定の間隔を有する離散値から該間隔の１／２だけオフセットした値のいずれかである場合とで効果が異なる。本実施の形態においては、この２通りの場合について、一定の間隔を１として説明する。すなわち、離散値として整数をとる場合と、整数から０．５（整数の１／２）だけオフセットした場合とについて説明する。
【０１２２】
図６に示す変換器１１ｔは、メッセージＱｍ，ｎの絶対値βｍ，ｎ（以下、ｘともいう。）を関数ｆの近似式Ｆ（ｘ）により変換し、その変換した値＝ｆＱ（ｘ）を出力する。また、変換器１４ｔは、対応する位置以外の変換器１１ｔの出力であるｆＱ（ｘ）を加算した総和を入力ｙとし、この入力ｙを所定区間に区切り、各区間内の値を関数ｆの近似式Ｆ（ｘ）の逆関数Ｇ（ｙ）（＝Ｆ−１（ｘ））により変換して各区間の代表値＝ｇＱ（ｙ）として出力する。
【０１２３】
本実施の形態においては、変換器１１ｔの出力ｆＱ（ｘ）、及び変換器１４ｔの入力ｙの各区間の境界値を２の冪乗で表すことを目的とする。これらの値を２の冪乗で表現するためには、実数ａを２の冪乗とし、定数Ｃの値を適宜選択する。さらに、ビットノード処理演算器−チェックノード処理演算器間でやり取りするメッセージＱｍ，ｎ、Ｒｍ，ｎの取り得る値を適切な離散値に設定する。
【０１２４】
ここでは、先ず、メッセージＱｍ，ｎの絶対値βｍ，ｎであるｘが下記式（１８）に示すように整数値をとる場合について説明する。
【０１２５】
【数２７】
2005223440.tif 000029
【０１２６】
このようにｘを整数とした場合であって、例えば定数Ｃ＝１、実数ａ＝４とした場合、ｆ（ｘ）≒Ｆ（ｘ）＝２１−２ｘと近似することができる。この場合、ｘの変換値ｆＱ（ｘ）は、下記式（１９）のように表すことができ、全て２の冪で表現できるため、回路や計算機での数値表現に適している。
【０１２７】
【数２８】
2005223440.tif 000030
【０１２８】
また、関数ｆの近似式Ｆ（ｘ）の逆変換であるＧ（ｙ）により、入力ｙの各区間を整数の代表値ｇＱ（ｙ）に変換する場合の、入力ｙの区間は、下記式（２０）のように表せる。
【０１２９】
【数２９】
2005223440.tif 000031
【０１３０】
このようにｘを整数値とした場合で、且つ実数ａが２の偶数乗で表現される場合、定数Ｃを適切に選択すればｆＱ（ｘ）、及び整数値を出力するｇＱ（ｙ）におけるｙの区間の境界値を共に２の冪乗で表すことができる。この場合、下記式（２１）に示すように、定数Ｃは２の冪乗（０．５×偶数乗）とすればよい。ここで、ｉ、ｋは任意の整数を示す。
【０１３１】
【数３０】
2005223440.tif 000032
【０１３２】
一方、ｘを整数とした場合であって、実数ａが２の奇数乗で表現される場合、例えばａ＝２などの場合には、定数Ｃをどのように選択してもｆＱ（ｘ）、及び整数値を出力するｇＱ（ｙ）におけるｙの区間の境界値を共に２の冪乗で表現することができない。
【０１３３】
なお、ｘを整数値とした場合で、且つ実数ａが２の奇数乗で表現される場合、定数Ｃを２の０．５×奇数乗とすると、変換器１１ｔの出力ｆＱ（ｘ）を２の冪乗で表すことができないものの、整数値を出力するｇＱ（ｙ）におけるｙの区間の境界値は２の冪乗で表現することができる。
【０１３４】
すなわち、例えば、定数Ｃ＝１／√２とし、実数ａ＝２としたとき、ｆ（ｘ）の近似式はＦ（ｘ）＝２０．５―ｘとなる。ｘを上記式（１８）のように整数とした場合、変換値ｆＱ（ｘ）は下記式（２２）のようになり、２の冪乗で表現することができない。したがって、２進数の場合、有限のビット数でこれらの値を正確に表現することができない。
【０１３５】
【数３１】
2005223440.tif 000033
【０１３６】
これをグラフにして示すと図９のようになる。すなわち、図９は、定数Ｃ＝１／√２、実数ａ＝２とした場合における、整数ｘと、その変換値ｆＱ（ｘ）との関係を示す。
【０１３７】
一方、このように、ｘを整数値とした場合で、且つ実数ａが２の奇数乗で表現される場合、定数Ｃを２の０．５×奇数乗とすれば、その変換値ｆＱ（ｘ）は２の冪乗で表せないものの、整数値ｇＱ（ｙ）に変換するためのｙが属する区間の境界値は、下記式（２３）のようになり、２の冪乗で表現することができる。
【０１３８】
【数３２】
2005223440.tif 000034
【０１３９】
これをグラフにして示すと図１０のようになる。すなわち、図１０は、定数Ｃ＝１／√２、実数ａ＝２とした場合における、整数値ｇＱ（ｙ）と対応するｙの区間との関係を示す。
【０１４０】
また、同じくｘを整数値とした場合で、且つ実数ａが２の奇数乗で表現される場合、定数Ｃを２の冪乗（０．５×偶数乗）としたとき、整数値ｘの変換値ｆＱ（ｘ）を２の冪乗で表すことができるが、整数値ｇＱ（ｙ）に変換するためのｙの各区間の境界値は２の冪乗で表現することができなくなる。
【０１４１】
すなわち、例えば、定数Ｃ＝１とし、実数ａ＝２としたとき、ｆ（ｘ）の近似式Ｆ（ｘ）＝２１−ｘとなる。ｘが上記式（１８）のように整数とした場合、その変換値ｆＱ（ｘ）は、下記式（２４）のように、２の冪乗で表すことができる。一方、ｇＱ（ｙ）に変換するためのｙの値が属する各区間の境界値は下記式（２５）のようになり、２の冪乗で表すことができない。下記式（２５）に示すように、各区間の境界値が２の冪乗とならない場合は、ｙが属する区間を判別するための回路が非常に複雑化してしまう
【０１４２】
【数３３】
2005223440.tif 000035
【０１４３】
【数３４】
2005223440.tif 000036
【０１４４】
以上のように、整数値ｘの変換値ｆＱ（ｘ）が２の冪乗となるよう定数Ｃを選択すると、整数値ｇＱ（ｙ）に変換される入力ｙが属する各区間の境界値が２の冪乗で表現できず、一方、整数値ｇＱ（ｙ）に変換される入力ｙの区間の境界値を２の冪乗で表現できるようにするとｆＱ（ｘ）が２の冪乗では表現できなくなる場合がある。したがって、いずれの値も２の冪乗で表現できるようにするためには、実数ａを２の偶数乗とし、且つ適切な定数Ｃを選択する必要がある。
【０１４５】
このように、いずれか一方が２の冪乗で表現できないような場合には、いずれも２の冪乗で表現できる回路とは異なり、ｆＱ（ｘ）、ｇＱ（ｙ）を出力する回路が複雑化する。この場合、ｆＱ（ｘ）、ｇＱ（ｙ）を出力する回路の複雑化を防止し、演算を簡単化するために、例えばｙの区間の境界値が２の冪乗で表現できない場合に適当な近似値を使用するなどの手法も考えうるが、近似による誤差が大きくなったり、２の冪乗ではない値を境界値の近似値として用いた場合には、ｙの属する区間を判別する回路（上述の図２７）が、境界値が２の冪乗である場合の後述する回路（例えば図１４）に比べて複雑になるため、変換器１１ｔの出力ｆＱ（ｘ）、及び変換器１２ｔの入力ｙが属する各区間を示す境界値のいずれも２の冪乗で表現できるようにすることが好ましい。
【０１４６】
そこで、本願発明者等が鋭意研究した結果、メッセージＱｍ，ｎの絶対値を整数から０．５オフセットさせることで、実数ａが２の奇数乗であっても偶数乗であっても、２の冪乗であれば、メッセージの絶対値ｘの変換値ｆＱ（ｘ）、及び整数値ｇＱ（ｙ）に変換されるｙが属する各区間の境界値を共に２の冪乗で示すことができることを知見した。この方法では、下記式（２６）に示すように、メッセージＱｍ，ｎの絶対値βｍ，ｎを整数から０．５だけオフセットした値をとるようにする。これにより、実数ａが２の冪乗でありさえすれば、ｆＱ（ｘ）、及びｙの区間の境界値の２の冪乗表現を共に実現すると共に、関数ｆ及び関数ｇの近似による誤差を最小限にすることができる。以下、この方法について具体的に説明する。なお、上述したように、ここで絶対値ｘを整数から０．５だけオフセットさせるのは、絶対値ｘが取りうる離散値の間隔を１としたためであり、例えば間隔２の離散値（０，２，４，・・・）であれば、その間隔の１／２だけオフセットした値（１，３，５，・・・）とすることで同様の効果を奏することは言うまでもない。
【０１４７】
【数３５】
2005223440.tif 000037
【０１４８】
例えば、ｘを整数から０．５だけオフセットした値とした場合であって、実数ａ＝２とした場合、例えば定数Ｃ＝１／√２とすれば、ｆ（ｘ）≒Ｆ（ｘ）＝２０．５−ｘと近似することができる。この場合、変換したｆＱ（ｘ）は、下記式（２７）のように表すことができ、全て２の冪で表現できるため、回路や計算機での数値表現に適している。
【０１４９】
【数３６】
2005223440.tif 000038
【０１５０】
これをグラフにして示すと図１１のようになる。すなわち、図１１は、実数ａ＝２とした場合で、定数Ｃ＝１／√２としたときの、整数から０．５だけオフセットしたｘと、変換したｆＱ（ｘ）との関係を示す。
【０１５１】
次に、このｆＱ（ｘ）を出力するための回路について説明する。ｆＱ（ｘ）の値は上記式（２７）に示すように、すべて２の冪であり、２進数での表現に適している。ここで、上記式（２６）、（２７）において、通信路特性や回路要求などに応じてｘの取り得る値の最大値を制限し、ｘの取り得る値の数を有限とすることが望ましい。上記式（２７）に示すようなｆＱ（ｘ）を実現する回路は例えば次のようになる。
【０１５２】
図１２は、出力を２進数の固定小数点で表現する場合で、ｘの取り得る値を７つ以下に制限した場合における、入力ｘをｆＱ（ｘ）に変換する変換回路の一例を示す回路図である。変換回路２０は、入力ｘが０．５,１．５,・・・，６．５のいずれかを判定する７つの判定部２１０〜２１６からなる判定ブロック２１ｔを有する。この判定ブロック２１ｔが２の冪乗の値を出力する出力部を構成する。
【０１５３】
各判定部２１０〜２１６に入力される値ｘは、メッセージＱｍ，ｎの絶対値βｍ，ｎであり、このβｍ，ｎ（＝｜Ｑｍ，ｎ｜）が例えば１．５である場合は、判定部２１１のみが１を出力し、他の判定部２１０、２１２〜２１６が０を出力する。
【０１５４】
ｆＱ（ｘ）を２進数の固定小数点で表現する場合は、入力ｘを判定する判定ブロック２１ｔを構成する判定部２１０〜２１６の出力がそれぞれｆＱ（ｘ）の最上位ビット（most significant bit：ＭＳＢ）から最下位ビット（least significant bit：ＬＳＢ）を示す。すなわち、判定ブロック２１ｔから出力される各ビットそのものがｆＱ（ｘ）を示すものとなり、図２５に示すような選択回路を必要としないため、回路構成が極めて簡単となる。
【０１５５】
また、出力を２進数の浮動小数点で表現する場合の回路構成は、図１３のようになる。図１３に示すように、浮動小数点の場合の変換回路３０は、ｘの整数部分を取り出す整数部分取出部３１と、取り出した整数部分に基づきｆＱ（ｘ）の指数部の値を出力する乗算器３２と、ｆＱ（ｘ）の仮数部の値として１を出力する出力部（図示せず）とを有する。このように、ｘの整数部分を［ｘ］（本明細書においては、［ｘ］は、ｘを超えない最大の整数を表すものとする。）と表すとき、変換回路３０は、仮数部を常に１として出力する。また、対数の底となる実数ａ＝２Ｎ（Ｎは、正の整数）と表すとき、乗算器３２には、（−Ｎ）とｘの整数部分である［ｘ］とが入力され、これらの積＝−Ｎ×［ｘ］が指数部として出力される。ここでは、実数ａ＝２の例であるので、Ｎ＝１であり、乗算器３２には（−Ｎ）＝−１が入力される。こうして、仮数部が１、指数部が（−Ｎ）×［ｘ］としてｆＱ（ｘ）を出力することができる。
【０１５６】
これらの回路は、出力する値ｆＱ（ｘ）が全て２の冪乗で表現されるため、従来の構成、例えば図２７に比べると容易に実現することができる。また回路のみならず、ソフトウェアによる実現でも同様に演算が簡略化できる。
【０１５７】
以上のように、ビットノード−チェックノード間のメッセージを底を２の冪乗となる実数ａの対数尤度比で、さらに図５に示すチェックノード処理演算器４の受け取るメッセージの絶対値が取り得る値を整数値から０．５だけオフセットさせたものとして、上記式（１６）で定義される関数ｆ（ｘ）を２Ｃａ−ｘと近似し、定数Ｃを適切に選択することで、ｆ（ｘ）の近似式による変換を、数値を２進数で表現する回路や計算機に適した形にすることができる。
【０１５８】
また、ｆ（ｘ）の逆変換であるｇ（ｙ）について、ｆ（ｘ）の近似式Ｆ（ｘ）＝２Ｃａ−ｘの逆関数を整数の代表値で出力するｇＱ（ｙ）は、同じく定数Ｃ＝１／√２、実数ａ＝２とした場合、下記式（２８）のように表せる。
【０１５９】
【数３７】
2005223440.tif 000039
【０１６０】
上記式（２８）に示すように、各ｙの区間の境界値がいずれも２の冪で表現できるため、回路や計算機での演算に適している。与えられた値ｙを上記のｇＱ（ｙ）に変換する回路は次のようになる。
【０１６１】
図１４は、入力ｙが２進数の固定小数点の場合のｇＱ（ｙ）を得るための変換回路を示す回路図である。図１４においては、ｇＱ（ｙ）の取り得る値の最大値を６に制限した場合のｇＱ（ｙ）を出力する回路の一例を示す。変換回路４０は、入力ｙのビットパターンを比較して一致するかを判定する７つの判定部４１０〜４１６からなる判定ブロック４１ｔと、判定ブロック４１ｔの出力から０〜６のいずれかの値を選択してｇＱ（ｙ）として出力する出力部としての選択回路４２とを有する。ここで、判定ブロック４１ｔにおけるｙの区間の判別はｙの最上位ビット（ＭＳＢ）から連続する０の数を数えることにより行うことができる。図中の判定ブロック４１ｔの条件で、ｘはドントケアを意味する。例えば、判定部４１０は最上位ビットが１、すなわち０が１つもないときに１を出力する。また、判定部４１１は最上位ビットが０で且つその下のビットが１、すなわち０が１つだけ連続するときに１を出力する。各判定部４１０〜４１６の条件は排他的であり、また必ず１つだけ真となるので、いかなるｙの値に対しても選択回路４２はただ１つの値を選択し、ｇＱ（ｙ）として出力する。
【０１６２】
また、入力ｙが２進数の浮動小数点で表現されている場合の回路構成を図１５に示す。図１５に示すように、変換回路５０は、入力ｙの指数部分Ａを取り出す指数部分取出部５１と、指数部分取出部５１の出力結果に基づき整数の代表値としてｇＱ（ｙ）を出力する出力部５２とを有する。ここで、上述と同様、対数の底となる実数ａ＝２Ｎ（Ｎは正の整数）としたとき、出力部５２は、指数部分取出部５１により取り出された指数部分Ａにより求まるＡ／Ｎの値を超えない最大の整数の絶対値をｇＱ（ｙ）として出力する。ここでは、実数ａ＝２の例であるので、Ｎ＝１であり、出力部５２は、単に指数部分取出部５１の出力Ａの絶対値を出力するものとなっている。このように、浮動小数点で表現されている場合には、ｙの指数部分の絶対値を求めれば、ｇＱ（ｙ）が得られる。
【０１６３】
これらの回路は従来の構成、例えば図２７に比べると容易に実現することができる。また回路のみならず、ソフトウェアによる実現でも演算が極めて簡略化できる。
【０１６４】
このようにｆＱ（ｘ）、及び整数値ｇＱ（ｙ）を出力するｙの区間の境界値を共に２の冪乗で示すためには、定数Ｃを適宜選択すればよい。上記定数Ｃ＝１／√２、実数ａ＝２の例は、実数ａが２の奇数乗の場合であり、下記式（２９）に示すように、定数Ｃは２の０．５×奇数乗とすればよい。ここでｉ、ｋは任意の整数を示す。
【０１６５】
【数３８】
2005223440.tif 000040
【０１６６】
上述したように、ｘの値を整数とした上述の場合においては、実数ａが２の奇数乗である場合には、量子化したｘの変換値ｆＱ（ｘ）を２の冪乗で表すことができなかったが、ｘを整数値から０.５オフセットさせることにより、上述の如く、実数ａが２の奇数乗であっても２の冪乗であれば、ｆＱ（ｘ）及び整数値ｇＱ（ｙ）を出力するｙの区間の境界値を同時に２の冪乗で表現することが可能となる。
【０１６７】
また、関数ｆの近似式Ｆ（ｘ）により得られる変換値ｆＱ（ｘ）、及び近似式Ｆ（ｘ）の逆関数Ｇ（ｙ）によりｇＱ（ｙ）に変換する際の入力ｙの各区間を規定する境界値が計算機や回路に適した形となることは、対数の底ａが２の奇数乗の場合のみならず、２の冪乗であればよく、実数ａ＝４，８，１６，・・・など、上述したｘの値を整数とした場合と同様、２の偶数乗になるよう選択しても同様の効果が得られる。この場合、下記式（３０）に示すように、定数Ｃは２の冪乗（０．５×偶数乗）とする。
【０１６８】
【数３９】
2005223440.tif 000041
【０１６９】
例えば実数ａ＝４、定数Ｃ＝１としたときのｆ（ｘ）の近似式は２１−２ｘと表せる。ここで、ｘを上記式（２６）と同様、整数から０.５オフセットさせて{０．５，１．５，２．５，・・・}の値としたとき、下記式（３１）に示すように、ｆＱ（ｘ）がすべて２の冪で表現できる。また、このとき、整数値ｇＱ（ｙ）に変換するための入力ｙの区間を示す境界値は下記式（３２）のように全て２の冪乗で表現することができる。
【０１７０】
【数４０】
2005223440.tif 000042
【０１７１】
【数４１】
2005223440.tif 000043
【０１７２】
このように、ｘを整数から０．５オフセットした値とし、実数ａ、すなわちメッセージＱｍ，ｎ、Ｒｍ，ｎの対数尤度比の底が２の偶数乗である場合においても、ｆＱ（ｘ）を２の冪乗で表すことができ、また、ｇＱ（ｙ）を整数として出力するためのｙの値の区間の境界値を２の冪乗で表すことができ、これらの表現方法により、対数の底ａ＝２とした場合と同様の簡単な演算とし、チェックノード処理演算器を簡単な回路構成とすることができる。
【０１７３】
図１６は、縦軸を対数軸とし、対数尤度比の底を４、定数Ｃを１としたときのｆ（ｘ）及び近似式の値を示すグラフ図である。ｘが大きくなるに従ってｆ（ｘ）はｅ１−２ｘに漸近しており、よく近似できていることがわかる。
【０１７４】
図１７は、出力を２進数の固定小数点で表現する場合で、メッセージＱｍ，ｎの絶対値を固定小数点で表現した場合であって、ｘが取り得る値を７つ以下に制限した場合における、ｘをｆＱ（ｘ）に変換する変換回路を示す回路図である。図１７に示すように、変換回路６０は、入力値ｘが０．５，１．５，・・・，６．５のいずれかを判定する７つの判定部６１０〜６１６からなる判定ブロック６１ｔを有する。この、ｆＱ（ｘ）を出力する出力部としての判定ブロック６１ｔの出力は、図１２に示す判定ブロック２１ｔと若干異なり、各判定部６１０〜６１６の出力値の間にそれぞれ値０のビットを出力する出力部（図示せず）を有している。これは、ｆＱ（ｘ）の値が{２０，２−２，２−４，・・・}となり、２の偶数乗で表現されるためであり、各判定部６１０〜６１６の出力値とその間の値０のビットとにより、ｆＱ（ｘ）のＭＳＢからＬＳＢが示される。その他の点は、図１２に示す回路と同様である。
【０１７５】
この場合においても、ｘの値を判定した判定結果として出力される各ビットがｆＱ（ｘ）を示すこととなり、図２５に示すような選択回路を必要としないため、回路構成が極めて簡単となる。
【０１７６】
また、出力を２進数の浮動小数点で表現する場合の、ｘをｆＱ（ｘ）に変換する変換回路の構成は、図１８のようになる。図１８に示すように、浮動小数点の場合の変換回路７０は、ｘの整数部分を取り出す整数部分取出部７１と、取り出した整数部分に基づきｆＱ（ｘ）の指数部分として出力する乗算器７２と、１をｆＱ（ｘ）の仮数部分として出力する出力部（図示せず）とを有する。図１３に示す回路と同様、対数の底となる実数ａ＝２Ｎ（Ｎは、正の整数）と表すとき、乗算器７２には、（−Ｎ）とｘの整数部分である［ｘ］とが入力され、これらの積＝−Ｎ×［ｘ］が指数部として出力されるため、ここでは、ａ＝４であり、Ｎ＝２であるため、乗算器７２には、（−Ｎ）＝−２が入力され、ｘの整数部分に乗算されｆＱ（ｘ）の指数部として出力される。
【０１７７】
また、図１９は、ｘを整数から０．５オフセットした値とし、実数ａ＝４、定数Ｃ＝１としたときのｇＱ（ｙ）を得るための変換回路を示す回路図である。図１９においては、入力ｙが２進数の固定小数点で表現されている場合で、ｇＱ（ｙ）が取り得る値の最大値を３に制限した場合のｇＱ（ｙ）を出力する回路の一例を示す。変換回路８０は、入力ｙのビットパターンから入力ｙの属する区間を判定する７つの判定部８１０〜８１６からなる判定ブロック８１ｔと、判定ブロック８１ｔの出力から０〜３のいずれかの値を選択してｇＱ（ｙ）として出力する出力部としての選択回路８２とを有する。ここで、判定ブロック８１ｔにおけるｙの区間の判別は、区間を示す境界値が２の冪乗で表現されているため、ｙの最上位ビット（ＭＳＢ)から連続する０の数を数えるのみで入力ｙが属する区間を判定することができるのは、上述の図１４に示す回路と同様であり、連続する０の数が０のときが０、連続する０の数が１及び２のときが１、連続する０の数が３及び４のときが２、連続する０の数が５及び６のときが３を出力する構成となっている。
【０１７８】
また、入力ｙが２進数の浮動小数点で表現されている場合におけるｇＱ（ｙ）を出力する回路構成を図２０に示す。実数ａが２の偶数乗であっても、上述の図１５に示す実数ａが２の奇数乗である場合と同様に、図２０に示すように、変換回路９０は、入力ｙの指数部分Ａを取り出す指数部分取出部９１と、その出力結果Ａに基づき整数の代表値ｇＱ（ｙ）を出力する出力部９２とを有する。ここで、上述と同様、対数の底となる実数ａ＝２Ｎ（Ｎは正の整数）としたとき、出力部９２は、指数部分取出部５１により取り出された指数部分Ａにより求まるＡ／Ｎの値を超えない最大の整数を出力する整数出力部９２ａと、整数出力部９２ａの出力の絶対値をｇＱ（ｙ）として出力する絶対値出力部９２ｂとからなる。ここでは、実数ａ＝４の例であるので、Ｎ＝２であり、整数出力部９２ａは、［Ａ／２］（Ａ／２を超えない最大の整数）を出力し、絶対値出力部９２ｂは、［Ａ／２］の絶対値をｇＱ（ｙ）として出力する。このように、浮動小数点で表現されている場合には、更に容易にｇＱ（ｙ）を得ることができる。
【０１７９】
これらの回路は従来の構成、例えば図２５に比べると容易に実現することができる。また回路のみならず、ソフトウェアによる実現でも演算が極めて簡略化できる。
【０１８０】
このように、メッセージＱｍ，ｎの絶対値ｘを、ｆ（ｘ）の近似式Ｆ（ｘ）により変換した値ｆＱ（ｘ）を上記式（２７）、（３１）に示すように２の冪乗とし、ｇＱ（ｙ）へ変換するための変換回路へ入力するｙの区間の境界値を上記式（２８）、（３２）に示すように２の冪乗とすることで、いずれの変換回路においても演算器の演算又は回路構成が簡単化する。また、メッセージＱｍ，ｎの絶対値ｘを整数値から０．５だけオフセットした値とすることにより、実数ａが２の奇数乗であっても、２の偶数乗であっても、ｆＱ（ｘ）及び整数値ｇＱ（ｙ）を出力するｙの区間の境界値を２の冪乗とすることができ、絶対値βｍ，ｎを整数から０．５だけオフセットした値とすることで実数ａの選択肢を広げることができる。
【０１８１】
ここで、対数尤度比の底となる実数ａは２の冪乗とすることができるが、実数ａを大きくすることは、量子化ステップを大きくすることに相当し、したがって演算精度は低くなるものの回路構成を簡単化し演算を高速化することができる。一方、実数ａを小さくして量子化ステップを小さくすれば、演算精度が高くなるため極めて良好なビットエラーレートを得ることができる。すなわち、システムが要求するビットエラーレート、受信する受信値の信号対雑音電力比などに応じて適宜量子化ステップに相当する実数ａの値を選択すればよい。また、ある程度量子化ステップを大きくした場合には、例えば繰り返し回数を増やすことで実数ａを小さい値としたときと同等なビットエラーレートを得るようにすることも可能である。
【０１８２】
更に、ビットノードからチェックノードへのメッセージＱｍ，ｎを整数値から０．５だけオフセットした値（０を含み一定間隔を有する離散値からその間隔の１／２だけオフセットさせた値）を取ると、ｆ（ｘ）の近似式Ｆ（ｘ）を使用してｆＱ（ｘ）へ変換する際の誤差を小さくすることができる。以下、この効果について説明する。
【０１８３】
メッセージＱｍ，ｎを整数値から０．５だけオフセットさせた値をとるとした場合、上記式（１６）に示すｆ（ｘ）と、ｆＱ（ｘ）との誤差は、｜Ｑｍ，ｎ｜＝０．５のときが最大となり、下記式（３３）のように計算できる。この最大誤差Ｅｍａｘ１を図１１に示す。
【０１８４】
【数４２】
2005223440.tif 000044
【０１８５】
一方、メッセージＱｍ，ｎの絶対値を整数値とした場合、上記式（１５）に示すｆ（ｘ）とｆＱ（ｘ）との誤差は、｜Ｑｍ，ｎ｜＝０のときが最大となり、ｆ（ｘ）は無限大に発散するため、図９に示すように、最大誤差Ｅｍａｘ２は無限大となってしまう。
【０１８６】
このように、メッセージＱｍ，ｎを整数値から０．５だけオフセットさせることで、ｆ（ｘ）からｆＱ（ｘ）への変換の誤差を小さく抑えることができる。
【０１８７】
ここで、メッセージＱｍ，ｎは上記式（１０）により計算されるが、上記式（１５―１）にて定義し直されるＰｎを、整数値から０．５だけオフセットした値を取るようにし、ｇＱ（ｙ）の変換において、ｇＱ（ｙ）が整数値を取るようにすれば、メッセージＱｍ，ｎ、の絶対値βｍ，ｎ（入力ｘ）は、初期化の際及び繰り返し演算で更新される際においても整数値から常に０．５だけオフセットした値をとるようにすることができ、チェックノード処理演算器における演算処理及び回路構成を簡単化し、かつ導入する近似式における誤差を小さくして正確な値を出力することができる。
【０１８８】
つまり、前述の手順に従えば次のようになる。手順０ではＱｍ，ｎは整数値から０．５だけオフセットした値Ｐｎに初期化される。手順１では上記式（７−１）に示すようにメッセージの絶対値βｍ,ｎがｆＱ（ｘ）に変換され、これらの加算値ｙから整数値ｇＱ（ｙ）を得る。これとは別に求めた符号とｇＱ（ｙ）を掛け合わせて整数値Ｒｍ，ｎを得て、チェックノードからビットノードへのメッセージとする。そして手順２において、上記式（９）に示されるＱｎを求め、上記式（１０）によってＱｍ，ｎを更新する。Ｐｎは整数値から０．５オフセットした値であり、Ｒｍ，ｎは整数値であるので、上記式（９）、式（１０）からＱｎ及びＱｍ，ｎは常に整数値から０．５オフセットした値となる。
【０１８９】
また、この事前確率Ｐｎを０．５だけオフセットした値とするのは、Ｐｎを間隔１の離散値としているためであって、上述したように、例えば間隔２の離散値とする場合には、０を含む間隔２の離散値、すなわち、−２，０，２，４・・・から、間隔の１／２の値オフセットした値、すなわち、−３，−１，１，３，・・とすればよい。
【０１９０】
なお、ｆ（ｘ）を２Ｃａ−ｘに近似した際の誤差は、ｘが小さい範囲で大きくなる。近似した場合には、例えば図８のグラフに示すように、例えばｘが１より小さい領域で実際のｆ（ｘ）の値より小さい値に変換されることになる。ここで、横軸ｘが０付近の値を取るということは、例えば受信する受信語のＳＮ比（signal-to-noise ratio：ＳＮＲ）が小さい場合に相当し、大きな雑音の影響を受けていることとなる。例えばディジタル放送などの受信装置により受信された信号を復号するための復号装置として使用される場合で、その入力のＳＮ比が十分高いような場合、例えば１０−５程度のビットエラーレートの受信語を復号する際には、メッセージの絶対値ｘが０付近の値を取ることは稀であり、上述の近似による誤差はほとんど影響がない。
【０１９１】
一方、例えば携帯電話などのモバイル装置で、受信状況が悪くビットエラーレートが大きい信号が受信される場合には、上述したように、メッセージＱｍ，ｎの絶対値βｍ，ｎを整数から０．５オフセットした値とすることで、ｘが小さい範囲の誤差をより小さくすることができ、良好なビットエラーレートを得ることができる。
【０１９２】
また、本発明は上述した実施の形態のみに限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能であることは勿論である。例えば、以上説明した復号装置を利用したストレージ（記憶装置）、記録再生を行う情報処理装置、送受信装置等に適用することができる。
【０１９３】
図２１及び図２２は、本実施の形態における符号検出装置（復号装置）を備える記録再生装置を示すブロック図である。図２１に示すように、記録再生装置１００は、音楽又は映像等のメッセージにＬＤＰＣ符号を生成するための生成行列を乗算してＬＤＰＣ符号を生成するＬＤＰＣ符号化部１０１と、生成されたＬＤＰＣ符号をチャネル符号化する符号化部１０２と、チャネル符号化されたデータを記録し、記録された符号を読み出す記録／再生部１０３と、読み出したデータからチャネル特性、チャネル符号に応じて検出及び復号するチャネル復号部１０４と、チャネル復号されたデータから符号検出するＬＰＤＣ復号部１０５とを有する。ＬＰＤＣ復号部１０５にて符号検出されたデータは、メッセージに復号される。
【０１９４】
また、図２２に示す他の記録再生装置１１０は、音楽又は映像等のメッセージをチャネル符号化する符号化部１１１と、チャネル符号化された符号語に対するＬＤＰＣパリティを生成するパリティ生成部１１２と、チャネル符号化部１１１の出力にパリティ生成部１１２が生成したＬＤＰＣパリティを挿入した符号語を生成するパリティ挿入部１１３と、パリティが挿入された符号語を記録し、記録された符号語を読み出す記録／再生部１１４と、読み出した符号語からチャネル特性に応じた検出を行うチャネル検出部１１５と、チャネル検出されたデータに対して符号検出するＬＰＤＣ復号部１１６と、ＬＰＤＣ復号部１１６にて符号検出されたデータからパリティを除去するパリティ除去部１１７と、パリティが除去されたデータをチャネル復号するチャネル復号部１１８とを有する。
【０１９５】
このように、本実施の形態における情報処理装置は、通信路を介して送受信されるようなデータの雑音の影響を除去するような受信装置や、記録再生時の書き込みエラーや、読み出しの際の信号の訛り等による誤りを訂正する各種再生装置等に、上述した復号装置を適用したものとすることができ、この復号装置を適用することにより、各種情報処理装置の回路構成を簡略化することができ、各種情報処理装置を小型化して生産性を向上するなどすることができる。
【図面の簡単な説明】
【０１９６】
【図１】２元（binary）ＬＤＰＣ符号のパリティ検査行列を示す図である。
【図２】図１に示すパリティ検査行列に対応した２部グラフ示す図である。
【図３】チェックノードＸｍとビットノードＹｎとのノード間にメッセージを伝搬させる繰り返し復号方法（メッセージパッシングアルゴリズム）を示すフローチャートである。
【図４】チェックノードＸｍとビットノードＹｎとのノード間にメッセージを伝搬させる繰り返し復号方法（メッセージパッシングアルゴリズム）であって、対数尤度比を用いた場合の復号方法を示すフローチャートである。
【図５】本発明の実施の形態における復号装置を示すブロック図である。
【図６】チェックノード処理演算器の主要部の一例を示す回路図である。
【図７】縦軸を対数軸としたときのｆ（ｘ）及び２ｅ−ｘを示すグラフ図である。
【図８】ａ＝２、Ｃ＝１／√２（２−０．５）としたときのｆ（ｘ）及び近似式Ｆ（ｘ）＝２Ｃａ−ｘ＝２０．５−ｘを示すグラフ図である。
【図９】実数ａ＝２、定数Ｃ＝１／√２とした場合における、整数ｘと、その変換値ｆＱ（ｘ）との関係を示すグラフ図である。
【図１０】実数ａ＝２、定数Ｃ＝１／√２とした場合における、ｇＱ（ｙ）と対応するｙの区間との関係を示すグラフ図である。
【図１１】縦軸を対数軸とし、実数ａ＝２、定数Ｃ＝１／√２とした場合における、整数から０．５だけオフセットした値ｘとｆＱ（ｘ）との関係を示すグラフ図である。
【図１２】実数ａ＝２、定数Ｃ＝１／√２で、出力ｆＱ（ｘ）を２進数の固定小数点で表現する場合であって、ｘの取り得る値を７つ以下に制限した場合における、ｘをｆＱ（ｘ）に変換する変換回路の一例を示す回路図である。
【図１３】実数ａ＝２、定数Ｃ＝１／√２で、出力ｆＱ（ｘ）を２進数の浮動小数点で表現する場合におけるｘをｆＱ（ｘ）に変換する変換回路の一例を示す回路図である。
【図１４】実数ａ＝２、定数Ｃ＝１／√２で、入力ｙが２進数の固定小数点で表現されている場合におけるｇＱ（ｙ）を得るための変換回路の一例を示す回路図である。
【図１５】実数ａ＝２、定数Ｃ＝１／√２で、入力ｙが２進数の浮動小数点で表現されている場合におけるｇＱ（ｙ）を得るための変換回路の一例を示す回路図である。
【図１６】縦軸を対数軸とし、実数ａ＝４、定数Ｃ＝２とした場合におけるｆ（ｘ）及び近似式Ｆ（ｘ）を示すグラフ図である。
【図１７】実数ａ＝４、定数Ｃ＝２で、出力ｆＱ（ｘ）を２進数の固定小数点で表現する場合であって、ｘが取り得る値を７つ以下に制限した場合における、ｘをｆＱ（ｘ）に変換する変換回路の一例を示す回路図である。
【図１８】実数ａ＝４、定数Ｃ＝２で、出力ｆＱ（ｘ）を２進数の浮動小数点で表現する場合におけるｘをｆＱ（ｘ）に変換する変換回路の一例を示す回路図である。
【図１９】実数ａ＝４、定数Ｃ＝２で、入力ｙが２進数の固定小数点で表現されている場合におけるｇＱ（ｙ）を得るための変換回路の一例を示す回路図である。
【図２０】実数ａ＝４、定数Ｃ＝２で、入力ｙが２進数の浮動小数点で表現されている場合におけるｇＱ（ｙ）を出力する変換回路の一例を示す回路図である。
【図２１】本発明の実施の形態における符号検出装置を備える情報処理装置を示すブロック図である。
【図２２】本発明の実施の形態における符号検出装置を備える情報処理装置の他の例を示すブロック図である。
【図２３】ＬＤＰＣ符号を用いた通信システムの一例を示すブロック図である。
【図２４】ＬＤＰＣ符号を用いた記録再生システムを示すブロック図である。
【図２５】T. Zhang等による非特許文献２に記載の復号装置を示すブロック図である。
【図２６】従来のチェックノード処理演算器の主要部の一例を示す回路図である。
【図２７】従来のｘからｆＱ（ｘ）を出力するための回路一例を示すブロック図である。
【符号の説明】
【０１９７】
１  復号装置、２、３０１  メモリ、３，３０２  ビットノード処理演算器、４，１０，３０３  チェックノード処理演算器、６  硬判定復号器、１１ｔ、１４ｔ  変換器、１２、１３ｔ  加算器、１５ｔ、１６ｔ、１７  乗算器、２０、３０、４０、５０  変換回路、３１，７１  整数部分取出部、２１０〜２１６，４１０〜４１６，６１０〜６１６，８１０〜８１６  判定部、２１ｔ，４１ｔ，６１ｔ，８１ｔ  判定ブロック、５１，９１  指数部分取出部、５２，９２  出力部
【図１】
2005223440.tif 000045
【図２】
2005223440.tif 000046
【図３】
2005223440.tif 000047
【図４】
2005223440.tif 000048
【図５】
2005223440.tif 000049
【図６】
2005223440.tif 000050
【図７】
2005223440.tif 000051
【図８】
2005223440.tif 000052
【図９】
2005223440.tif 000053
【図１０】
2005223440.tif 000054
【図１１】
2005223440.tif 000055
【図１２】
2005223440.tif 000056
【図１３】
2005223440.tif 000057
【図１４】
2005223440.tif 000058
【図１５】
2005223440.tif 000059
【図１６】
2005223440.tif 000060
【図１７】
2005223440.tif 000061
【図１８】
2005223440.tif 000062
【図１９】
2005223440.tif 000063
【図２０】
2005223440.tif 000064
【図２１】
2005223440.tif 000065
【図２２】
2005223440.tif 000066
【図２３】
2005223440.tif 000067
【図２４】
2005223440.tif 000068
【図２５】
2005223440.tif 000069
【図２６】
2005223440.tif 000070
【図２７】
2005223440.tif 000071