(57)【特許請求の範囲】
【請求項１】
LDPC(Low Density Parity Check)符号を復号する復号装置であって、
供給されるメッセージを用いて、前記LDPC符号の復号のためのバリアブルノードの演算と、チェックノードの演算とを、選択的に行い、演算の結果得られるメッセージを出力するメッセージ計算手段と、
前記メッセージを記憶する記憶手段と、
前記メッセージ計算手段が出力するメッセージを前記記憶手段に書き込む書き込み制御と、前記メッセージ計算手段での演算に用いられる同一のメッセージを、前記記憶手段から２回読み出し、前記メッセージ計算手段に供給する読み出し制御とを行う制御手段と
を備え、
前記メッセージ計算手段において、バリアブルノードの演算を行う回路と、チェックノードの演算を行う回路との一部が共有化されている
復号装置。
【請求項２】
前記メッセージ計算手段は、前記記憶手段から２回読み出される同一のメッセージのうちの１回目に読み出されるメッセージが供給されるポートと、２回目に読み出されるメッセージが供給されるポートとの２つのポートを有する
請求項１に記載の復号装置。
【請求項３】
前記メッセージ計算手段は、
チェックノードに入力される入力データxに対して、非線形関数φ(x)=-ln(tanh(x/2))の演算結果を出力する１のLUT(Look Up Table)と、
チェックノードから出力された出力データxに対して、前記非線形関数の逆関数φ-1(x)=2tanh-1(e-x)の演算結果を出力する他の１のLUTと
を有し、
チェックノードの演算時には、データを、前記１のLUTと他の１のLUTを経由させ、
バリアブルノードの演算時には、データを、前記１のLUTと他の１のLUTをバイパスさせる
請求項１に記載の復号装置。
【請求項４】
前記メッセージ計算手段は、チェックノードに入力される入力データxに対して、逆関数φ-1(x)=2tanh-1(e-x)と同一の演算結果が得られる非線形関数φ(x)=-ln(tanh(x/2))の演算結果を出力するとともに、バリアブルノードに入力される入力データxに対して、前記逆関数φ-1(x)の演算結果を出力するLUT(Look Up Table)を有する
請求項１に記載の復号装置。
【請求項５】
前記メッセージ計算手段は、バリアブルノードから出力された出力データxに対して、逆関数φ-1(x)=2tanh-1(e-x)と同一の演算結果が得られる非線形関数φ(x)=-ln(tanh(x/2))の演算結果を出力するとともに、チェックノードから出力された出力データxに対して、前記逆関数φ-1(x)の演算結果を出力するLUT(Look Up Table)を有する
請求項１に記載の復号装置。
【請求項６】
前記記憶手段は、２以上のバンクを有する
請求項１に記載の復号装置。
【請求項７】
LDPC(Low Density Parity Check)符号を復号する復号装置を制御する制御方法であって、
前記復号装置は、
供給されるメッセージを用いて、前記LDPC符号の復号のためのバリアブルノードの演算と、チェックノードの演算とを、選択的に行い、演算の結果得られるメッセージを出力するメッセージ計算手段と、
前記メッセージを記憶する記憶手段と
を備え、
前記メッセージ計算手段において、バリアブルノードの演算を行う回路と、チェックノードの演算を行う回路との一部が共有化されており、
前記メッセージ計算手段が出力するメッセージを前記記憶手段に書き込む書き込み制御と、前記メッセージ計算手段での演算に用いられる同一のメッセージを、前記記憶手段から２回読み出し、前記メッセージ計算手段に供給する読み出し制御とを行うステップを含む
制御方法。
【請求項８】
LDPC(Low Density Parity Check)符号を復号する復号装置としてコンピュータを機能させるプログラムであって、
LDPC(Low Density Parity Check)符号を復号する復号装置であって、
供給されるメッセージを用いて、前記LDPC符号の復号のためのバリアブルノードの演算と、チェックノードの演算とを、選択的に行い、演算の結果得られるメッセージを出力するメッセージ計算手段と、
前記メッセージを記憶する記憶手段と、
前記メッセージ計算手段が出力するメッセージを前記記憶手段に書き込む書き込み制御と、前記メッセージ計算手段での演算に用いられる同一のメッセージを、前記記憶手段から２回読み出し、前記メッセージ計算手段に供給する読み出し制御とを行う制御手段と
して、コンピュータを機能させるためのプログラムであり、
前記メッセージ計算手段において、バリアブルノードの演算を行う回路と、チェックノードの演算を行う回路との一部が共有化されている
プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、復号装置、制御方法、およびプログラムに関し、特に、例えば、LDPC(Low Density Parity Check)符号を復号する復号装置の規模を削減することができるようにする復号装置、制御方法、およびプログラムに関する。
【背景技術】
【０００２】
近年、例えば、移動体通信や深宇宙通信といった通信分野、及び地上波又は衛星ディジタル放送といった放送分野の研究が著しく進められているが、それに伴い、誤り訂正符号化及び復号の効率化を目的として符号理論に関する研究も盛んに行われている。
【０００３】
符号性能の理論的限界としては、いわゆるシャノン(C. E. Shannon)の通信路符号化定理によって与えられるシャノン限界が知られている。符号理論に関する研究は、このシャノン限界に近い性能を示す符号を開発することを目的として行われている。近年では、シャノン限界に近い性能を示す符号化方法として、例えば、並列連接畳み込み符号(PCCC(Parallel Concatenated Convolutional Codes))や、縦列連接畳み込み符号(SCCC(Serially Concatenated Convolutional Codes))といった、いわゆるターボ符号化(Turbo coding)と呼ばれる手法が開発されている。また、これらのターボ符号が開発される一方で、古くから知られる符号化方法である低密度パリティ検査符号(Low Density Parity Check codes)（以下、LDPC符号という）が脚光を浴びつつある。
【０００４】
LDPC符号は、R. G. Gallagerによる「R. G. Gallager, "Low Density Parity Check Codes", Cambridge, Massachusetts: M. I. T. Press, 1963」において最初に提案されたものであり、その後、「D. J. C. MacKay, "Good error correcting codes based on very sparse matrices", Submitted to IEEE Trans. Inf. Theory, IT-45, pp. 399-431, 1999」や、「M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi and D. A. Spielman, "Analysis of low density codes and improved designs using irregular graphs", in Proceedings of ACM Symposium on Theory of Computing, pp. 249-258, 1998」等において再注目されるに至ったものである。
【０００５】
LDPC符号は、近年の研究により、ターボ符号等と同様に、符号長を長くしていくにしたがって、シャノン限界に近い性能が得られることがわかりつつある。また、LDPC符号は、最小距離が符号長に比例するという性質があることから、その特徴として、ブロック誤り確率特性がよく、さらに、ターボ符号等の復号特性において観測される、いわゆるエラーフロア現象が殆ど生じないことが利点として挙げられる。
【０００６】
以下、このようなLDPC符号について具体的に説明する。なお、LDPC符号は、線形符号であり、必ずしも２元である必要はないが、ここでは、２元であるものとして説明する。
【０００７】
LDPC符号は、そのLDPC符号を定義する検査行列(parity check matrix)が疎なものであることを最大の特徴とするものである。ここで、疎な行列とは、行列のコンポーネントの"1"の個数が非常に少なく構成されるものであり、疎な検査行列をHで表すものとすると、そのような検査行列Hとしては、例えば、図１に示すように、各列のハミング重み（"1"の数）(weight)が"3"であり、且つ、各行のハミング重みが"6"であるもの等がある。
【０００８】
このように、各行及び各列のハミング重みが一定である検査行列Hによって定義されるLDPC符号は、レギュラーLDPC符号と称される。一方、各行及び各列のハミング重みが一定でない検査行列Hによって定義されるLDPC符号は、イレギュラーLDPC符号と称される。
【０００９】
このようなLDPC符号による符号化は、検査行列Hに基づいて生成行列Gを生成し、この生成行列Gを２元の情報メッセージに対して乗算することによって符号語を生成することで実現される。具体的には、LDPC符号による符号化を行う符号化装置は、まず、検査行列Hの転置行列HTとの間に、式GHT=0が成立する生成行列Gを算出する。ここで、生成行列Gが、k×n行列である場合には、符号化装置は、生成行列Gに対してkビットからなる情報メッセージ（ベクトルu）を乗算し、nビットからなる符号語ｃ（＝uＧ）を生成する。この符号化装置によって生成された符号語は、値が"0"の符号ビットが"+1"に、値が"1"の符号ビットが"−1"にといったようにマッピングされて送信され、所定の通信路を介して受信側において受信されることになる。
【００１０】
一方、LDPC符号の復号は、Gallagerが確率復号(Probabilistic Decoding)と称して提案したアルゴリズムであって、バリアブルノード(variable node（メッセージノード(message node)とも呼ばれる。）)と、チェックノード(check node)とからなる、いわゆるタナーグラフ(Tanner graph)上での確率伝播(belief propagation)によるメッセージ・パッシング・アルゴリズムによって行うことが可能である。ここで、以下、適宜、バリアブルノードとチェックノードを、単に、ノードともいう。
【００１１】
しかしながら、確率復号においては、各ノード間で受け渡されるメッセージが実数値であることから、解析的に解くためには、連続した値をとるメッセージの確率分布そのもを追跡する必要があり、非常に困難を伴う解析を必要とすることになる。そこで、Gallagerは、LDPC符号の復号アルゴリズムとして、アルゴリズムＡ又はアルゴリズムＢを提案している。
【００１２】
LDPC符号の復号は、例えば、図２に示すような手順にしたがって行われる。なお、ここでは、符号長の長さのLDPC符号の受信データのi番目をU0(u0i)とし、チェックノードから出力されるj番目のメッセージ（チェックノードに接続しているj番目の枝から出力されるメッセージ）をujとし、バリアブルノードから出力されるi番目のメッセージ（バリアブルノードに接続しているi番目の枝から出力されるメッセージ）をviとする。また、ここでは、メッセージとは、値の"0"らしさを、いわゆる対数尤度比(log likelihood ratio)で表現した実数値である。
【００１３】
まず、LDPC符号の復号においては、図２に示すように、ステップＳ１１において、受信データU0(u0i)が受信され、メッセージujが"0"に初期化されるとともに、繰り返し処理のカウンタとしての整数をとる変数kが"0"に初期化され、ステップＳ１２に進む。ステップＳ１２において、受信データU0(u0i)に基づいて、式（１）に示すバリアブルノードの演算を行うことによってメッセージviが求められ、さらに、このメッセージviに基づいて、式（２）に示すチェックノードの演算を行うことによってメッセージujが求められる。
【００１４】
【数１】
0004807063.tif 000002
・・・（１）
【００１５】
【数２】
0004807063.tif 000003
・・・（２）
【００１６】
ここで、式（１）と式（２）におけるdvとdcは、それぞれ、検査行列Hの縦方向（列）と横方向（行）の"1"の個数を示す任意に選択可能とされるパラメータであり、例えば、(3,6)符号の場合には、dv=3，dc=6となる。
【００１７】
なお、式（１）または（２）の演算においては、それぞれ、メッセージを出力しようとする枝(edge)から入力されたメッセージを、和または積演算の対象としては用いないことから、和または積演算の範囲が、１乃至dv-1または１乃至dc-1となっている。また、式（２）に示す演算は、２入力v1，v2に対する１出力で定義される式（３）に示す関数R(v1,v2)のテーブルを予め作成しておき、これを式（４）に示すように連続的（再帰的）に用いることによって行うことができる。
【００１８】
【数３】
0004807063.tif 000004
・・・（３）
【００１９】
【数４】
0004807063.tif 000005
・・・（４）
【００２０】
ステップＳ１２では、さらに、変数kが"1"だけインクリメントされ、ステップＳ１３に進む。ステップＳ１３では、変数kが所定の繰り返し復号回数N以上であるか否かが判定される。ステップＳ１３において、変数kがN以上ではないと判定された場合、ステップＳ１２に戻り、以下、同様の処理が繰り返される。
【００２１】
また、ステップＳ１３において、変数kがN以上であると判定された場合、ステップＳ１４に進み、式（５）に示す演算を行うことによって最終的に出力する復号結果としてのメッセージvが求められて出力され、LDPC符号の復号処理が終了する。
【００２２】
【数５】
0004807063.tif 000006
・・・（５）
【００２３】
ここで、式（５）の演算は、式（１）の演算とは異なり、バリアブルノードに接続している全ての枝からのメッセージujを用いて行われる。
【００２４】
このようなLDPC符号の復号は、例えば(3,6)符号の場合には、図３に示すように、各ノード間でメッセージの授受が行われる。なお、図３において"="で示すノードは、バリアブルノードを表し、式（１）に示したバリアブルノードの演算が行われる。また、図３において"+"で示すノードは、チェックノードを表し、式（２）に示したチェックノードの演算が行われる。特に、アルゴリズムＡにおいては、メッセージを２元化し、"+"で示すチェックノードにて、dc-1個の入力メッセージ（チェックノードに入力されるメッセージvi）の排他的論理和演算を行い、"="で示すバリアブルノードにて、受信データRに対して、dv-1個の入力メッセージ（バリアブルノードに入力されるメッセージuj）が全て異なるビット値であった場合には、符号を反転して出力する。
【００２５】
また、一方で、近年、LDPC符号の復号の実装法に関する研究も行われている。実装方法について述べる前に、まず、LDPC符号の復号を摸式化して説明する。
【００２６】
図４は、(3,6)LDPC符号（符号化率1/2、符号長12）の検査行列(parity check matrix)Hの例である。LDPC符号の検査行列Hは、図５のように、タナーグラフを用いて書き表すことができる。ここで、図５において、"+"で表されるのが、チェックノードであり、"="で表されるのが、バリアブルノードである。チェックノードとバリアブルノードは、それぞれ、検査行列の行と列に対応する。チェックノードとバリアブルノードとの間の結線は、枝(edge)であり、検査行列Hの"1"に相当する。即ち、検査行列の第ｊ行第ｉ列のコンポーネントが１である場合には、図５において、上からｉ番目のバリアブルノード（"="のノード）と、上からｊ番目のチェックノード（"+"のノード）とが、枝により接続される。枝は、バリアブルノードに対応するLDPC符号（の受信データ）のビットが、チェックノードに対応する拘束条件を持つことを表す。なお、図５は、図４の検査行列Hのタナーグラフとなっている。
【００２７】
LDPC符号の復号方法であるサムプロダクトアルゴリズム(Sum Product Algorithm)は、バリアブルノードの演算とチェックノードの演算とを繰り返し行う。
【００２８】
バリアブルノードでは、図６のように、式（１）のバリアブルノードの演算を行う。すなわち、図６において、計算しようとしている枝（バリアブルノードに接続している枝のうちのi番目の枝）に対応するメッセージviは、バリアブルノードに繋がっている残りの枝からのメッセージu1およびu2と、受信データu0iを用いて計算される。他の枝に対応するメッセージも同様に計算される。
【００２９】
チェックノードの演算について説明する前に、式（２）を、式a×b=exp{ln(|a|)+ln(|b|)}×sign(a)×sign(b)の関係を用いて、式（６）のように書き直す。但し、sign(x)は、x≧0のとき1（論理０）であり、x＜0のとき-1（論理１）である。
【００３０】
【数６】
0004807063.tif 000007
・・・（６）
【００３１】
更に、x≧0において、非線形関数φ(x)=-ln(tanh(x/2))を定義すると、その逆関数φ-1(x)は、式φ-1(x)=2tanh-1(e-x)で表されるから、式（６）は、式（７）のように書くことができる。
【００３２】
【数７】
0004807063.tif 000008
・・・（７）
【００３３】
チェックノードでは、図７のように、式（７）のチェックノードの演算を行う。すなわち、図７において、計算しようとしている枝（チェックノードに接続している枝のうちのj番目の枝）に対応するメッセージujは、チェックノードに繋がっている残りの枝からのメッセージv1,v2,v3,v4,v5を用いて計算される。他の枝に対応するメッセージも同様に計算される。
【００３４】
なお、関数φ(x)は、φ(x)=ln((ex+1)/(ex-1))とも表すことができ、x＞0において、φ(x)=φ-1(x)、即ち、非線形関数φ(x)の演算結果と、その逆関数φ-1(x)の演算結果とは同一である。関数φ(x)およびφ-1(x)をハードウェアに実装する際には、LUT(Look Up Table)を用いて実装される場合があるが、両者は共に同一のLUTとなる。
【００３５】
また、式（１）のバリアブルノードの演算は、式（５）と、次の式（８）とに分けることができる。
【００３６】
【数８】
0004807063.tif 000009
・・・（８）
【００３７】
従って、式（５）および式（８）と、式（７）の演算を繰り返し行うことにより、式（１）のバリアブルノードの演算と、式（７）のチェックノードの演算を繰り返し行うことができる。この場合、式（５）および式（８）のバリアブルノードの演算のうちの、式（５）の演算の結果を、そのまま、最終的な復号結果とすることができる。
【００３８】
サムプロダクトアルゴリズムをハードウェアに実装する場合、式（１）（、または式（５）および式（８））で表されるバリアブルノード演算（バリアブルノードの演算）および式（７）で表されるチェックノード演算（チェックノードの演算）を、適度な回路規模と動作周波数で繰り返し行うことが必要である。
【００３９】
復号装置の実装の例として、単純に各ノードの演算を一つずつ順次行うことによって復号を行うフルシリアルの復号(full serial decoding)の実装法について説明する。
【００４０】
図８は、LDPC符号の復号を行う復号装置の構成例を示している。
【００４１】
図８の復号装置では、動作クロックの１クロック(clock)ごとに、１つの枝に対応するメッセージが計算される。
【００４２】
即ち、図８の復号装置は、メッセージ計算部１０１、メッセージメモリ１０４、受信データメモリ１０５、制御部１０６からなる。また、メッセージ計算部１０１は、バリアブルノード計算器１０２とチェックノード計算器１０３とから構成されている。
【００４３】
図８の復号装置では、メッセージメモリ１０４からメッセージ計算部１０１に、メッセージが１つずつ読み出され、メッセージ計算部１０１において、そのメッセージを用いて、所望の枝に対応するメッセージが計算される。そして、その計算によって求められたメッセージが、メッセージメモリ１０４に格納されていく。図８の復号装置では、以上の処理が繰り返し行われ、いわゆる繰り返し復号が行われる。
【００４４】
即ち、受信データメモリ１０５には、送信されてきたLDPC符号を受信することにより得られる、符号の0（または1）らしさを表す対数尤度比である受信データ（LDPC符号）D100が供給され、受信データメモリ１０５は、その受信データD100を格納（記憶）する。
【００４５】
バリアブルノード演算時には、受信データメモリ１０５は、制御部１０６から供給される制御信号にしたがって、記憶している受信データを読み出し、受信データD101として、メッセージ計算部１０１のバリアブルノード計算器１０３に供給する。
【００４６】
また、バリアブルノード演算時には、メッセージメモリ１０４は、制御部１０６から供給される制御信号にしたがって、記憶しているメッセージ（チェックノードメッセージuj）D102を読み出し、バリアブルノード計算器１０２に供給する。バリアブルノード計算器１０２は、メッセージメモリ１０４から供給されるメッセージD102と受信データメモリ１０５から供給される受信データD101を用い、式（１）のバリアブルノード演算を行い、そのバリアブルノード演算の結果得られたメッセージ（バリアブルノードメッセージ）viを、メッセージD103として、メッセージメモリ１０４に供給する。
【００４７】
そして、メッセージメモリ１０４は、以上のようにしてバリアブルノード計算器１０２から供給されるメッセージD103を記憶する。
【００４８】
一方、チェックノード演算時には、メッセージメモリ１０４は、制御部１０６から供給される制御信号にしたがって、記憶しているバリアブルノードメッセージviを、メッセージD104として読み出し、チェックノード計算器１０３に供給する。
【００４９】
チェックノード計算器１０３は、メッセージメモリ１０４から供給されるメッセージD104を用いて、式（７）のチェックノード演算を行い、そのチェックノード演算によって求められたメッセージ（チェックノードメッセージ）ujを、メッセージD105として、メッセージメモリ１０４に供給する。
【００５０】
そして、メッセージメモリ１０４は、以上のようにしてチェックノード計算器１０３から供給されるメッセージD105を記憶する。
【００５１】
メッセージメモリ１０４が記憶したチェックノード計算器１０３からのメッセージD105、即ち、チェックノードメッセージujは、次のバリアブルノード演算時に、メッセージD102として読み出され、バリアブルノード計算器１０２に供給される。
【００５２】
図９は、バリアブルノード演算を１つずつ行う図８のバリアブルノード計算器１０２の構成例を示している。
【００５３】
バリアブルノード計算器１０２は、外部からメッセージ（データ）が供給（入力）される入力ポートとして、２つの入力ポートP101とP102を有し、外部にメッセージを供給（出力）するポートとして、１の出力ポートP103を有している。そして、バリアブルノード計算器１０２は、入力ポートP101とP102それぞれから入力されるメッセージを用いて、式（１）のバリアブルノード演算を行い、その結果得られるメッセージを、出力ポートP103から出力する。
【００５４】
即ち、入力ポートP101には、受信データメモリ１０５から読み出された受信データD101が供給される。また、入力ポートP102には、メッセージメモリ１０４から読み出されたメッセージD102（チェックノードメッセージuj）が供給される。
【００５５】
バリアブルノード計算器１０２では、検査行列の各行に対応するチェックノードからのメッセージD102（メッセージuj）が入力ポートP102から１つずつ読み込まれ、そのメッセージD102が、演算器１５１とFIFOメモリ１５５に供給される。また、バリアブルノード計算器１０２では、受信データメモリ１０５から受信データD101が入力ポートP101から1つずつ読み込まれ、演算器１５７に供給される。
【００５６】
演算器１５１は、メッセージD102（メッセージuj）とレジスタ１５２に格納されている値D151とを加算することにより、メッセージD102を積算し、その結果得られる積算値を、レジスタ１５２に再格納する。なお、検査行列の1列に亘る全ての枝からのメッセージD102が積算された場合、レジスタ１５２は０にリセットされる。
【００５７】
検査行列の1列に亘るメッセージD102が１つずつ読み込まれ、レジスタ１５２に1列分のメッセージD102が積算された値が格納された場合、即ち、レジスタ１５２に、検査行列の１列に亘る全ての枝からのメッセージD102（メッセージuj）が積算された積算値（ｊ＝１からｄVまでのΣuj)が格納された場合、セレクタ１５３は、レジスタ１５２に格納されている値、即ち、検査行列の１列に亘る全ての枝からのメッセージD102（メッセージuj）が積算された積算値D151（ｊ＝１からｄVまでのΣuj)を選択し、レジスタ１５４に出力して格納させる。
【００５８】
レジスタ１５４は、格納している値D151を、値D152として、セレクタ１５３と演算器１５６に供給する。レジスタ１５２に1列分のメッセージD102が積算された値が格納される直前までは、セレクタ１５３は、レジスタ１５４から供給された値D152を選択し、レジスタ１５４に出力し再格納させる。即ち、検査行列の１列に亘る全ての枝からのメッセージD102（メッセージuj）が積算されるまで、レジスタ１５４は、前回積算された値を、セレクタ１５３と演算器１５６に供給する。
【００５９】
一方、FIFOメモリ１５５は、レジスタ１５４から新たな値D152（ｊ＝１からｄVまでのΣuj)が出力されるまでの間、チェックノードからのメッセージD102を遅延し、値D153として演算器１５６に供給する。演算器１５６は、レジスタ１５４から供給された値D152から、FIFOメモリ１５５から供給された値D153を減算する。即ち、演算器１５６は、検査行列の1列に亘る全ての枝からのメッセージD102（メッセージuj）の積算値（ｊ＝１からｄVまでのΣuj）から、求めたい枝からのメッセージujを減算して、その減算値（ｊ＝１からｄv−１までのΣuj）を求め、演算器１５７に供給する。
【００６０】
演算器１５７は、入力ポートP101からの受信データD101と、演算器１５６からの減算値（ｊ＝１からｄv−１までのΣuj）とを加算し、その結果得られる加算値をメッセージD103（メッセージvi）として、出力ポートP103から出力する。
【００６１】
以上のように、バリアブルノード計算器１０２では、式（１）のバリアブルノード演算（vi=uoi＋Σuj）が行われ、その結果得られるメッセージ（バリアブルノードメッセージ）viが、出力ポートP103から出力される。
【００６２】
図１０は、チェックノード演算を１つずつ行う図８のチェックノード計算器１０３の構成例を示している。
【００６３】
チェックノード計算器１０３は、外部からメッセージ（データ）が供給（入力）される入力ポートとして、１つの入力ポートP111を有し、外部にメッセージを供給（出力）するポートとして、１の出力ポートP112を有している。そして、チェックノード計算器１０３は、入力ポートP111から入力されるメッセージを用いて、式（７）のチェックノード演算を行い、その結果得られるメッセージを、出力ポートP112から出力する。
【００６４】
即ち、入力ポートP111には、メッセージメモリ１０４から読み出されたメッセージD104（バリアブルノードメッセージvi）が供給される。
【００６５】
チェックノード計算器１０３では、検査行列の各列に対応するバリアブルノードからのメッセージD104（メッセージvi）が入力ポートP111から１つずつ読み込まれ、その最上位ビットを除く下位ビット、つまり、メッセージD104の絶対値D122(|vi|)が、LUT１２１に供給されるとともに、最上位ビット、つまりメッセージD104の符号ビットD121が、EXOR回路１２９とFIFO(First In First Out)メモリ１３３にそれぞれ供給される。
【００６６】
LUT１２１は、そこに入力される値を引数xとして、式（７）のチェックノード演算における非線形関数φ(x)の演算結果を出力するLUTであり、絶対値D122(|vi|)の供給に対して、非線形関数φ(|vi|)の演算を行った演算結果D123（φ(|vi|)）を読み出し、演算器１２２とFIFOメモリ１２７に供給する。
【００６７】
演算器１２２は、演算結果D123（φ(|vi|)）とレジスタ１２３に格納されている値D124とを加算することにより、演算結果D123を積算し、その結果得られる積算値をレジスタ１２３に再格納する。なお、検査行列の1行に亘る全ての枝からのメッセージD104の絶対値D122(|vi|)に対する演算結果D123（φ(|vi|)）が積算された場合、レジスタ１２３は０にリセットされる。
【００６８】
検査行列の1行に亘るメッセージD104が１つずつ読み込まれ、レジスタ１２３に1行分の演算結果D123が積算された積算値が格納された場合、セレクタ１２４は、レジスタ１２３に格納されている値、即ち、検査行列の１行に亘る全ての枝からのメッセージD104（メッセージvi）から求められたφ(|vi|)が積算された積算値D124（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）を選択し、値D125として、レジスタ１２５に出力して格納させる。レジスタ１２５は、格納している値D125を、値D126として、セレクタ１２４と演算器１２６に供給する。
【００６９】
レジスタ１２３に1行分の演算結果D123が積算された積算値が格納される直前までは、セレクタ１２４は、レジスタ１２５から供給された値D126を選択し、レジスタ１２５に出力して再格納させる。即ち、検査行列の１行に亘る全ての枝からのメッセージD104（メッセージvi）から求められたφ(|vi|)が積算されるまで、レジスタ１２５は、前回積算されたφ(|vi|)の積算値を、セレクタ１２４と演算器１２６に供給する。
【００７０】
一方、FIFOメモリ１２７は、レジスタ１２５から新たな値D126（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）が出力されるまでの間、LUT１２１が出力した演算結果D123（φ(|vi|)）を遅延し、値D127として演算器１２６に供給する。演算器１２６は、レジスタ１２５から供給された値D126から、FIFOメモリ１２７から供給された値D127を減算し、その減算結果を、減算値D128としてLUT１２８に供給する。即ち、演算器１２６は、検査行列の1行に亘る全ての枝からのメッセージD104（メッセージvi）から求められたφ(|vi|)の積算値（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）から、求めたい枝からのメッセージ（ｉ＝ｄcのメッセージvi）から求められたφ(|vi|)を減算して、その減算値（ｉ＝１からｉ＝ｄc−１までのΣφ(|vi|)）を減算値D128としてLUT１２８に供給する。
【００７１】
LUT１２８は、そこに入力される値を引数xとして、式（７）のチェックノード演算における非線形関数φ(x)の逆関数φ-1(x)の演算結果を出力するLUTであり、演算器１２６からの減算値D128（ｉ＝１からｉ＝ｄc−１までのΣφ(|vi|)）の供給に対して、逆関数φ-1（Σφ(|vi|)）の演算を行った演算結果D129（φ-1(Σφ(|vi|)))を出力する。
【００７２】
なお、上述したように、非線形関数φ(x)の演算結果と逆関数φ-1(x)の演算結果とは等しいので、LUT１２１と１２８とは、同一構成のLUTとなっている。
【００７３】
以上の処理と並行して、EXOR回路１２９は、レジスタ１３０に格納されている値D131と符号ビット（正負を表すビット）D121との排他的論理和を演算することにより、メッセージD104の符号ビットD121どうしの乗算を行い、乗算結果D130をレジスタ１３０に再格納する。なお、検査行列の1行に亘る全ての枝からのメッセージD104の符号ビットD121が乗算された場合、レジスタ１３０はリセットされる。
【００７４】
検査行列の1行に亘る全ての枝からのメッセージD104の符号ビットD121が乗算された乗算結果D130（ｉ＝１からｄcまでのΠsign(vi)）がレジスタ１３０に格納された場合、セレクタ１３１は、レジスタ１３０に格納されている値、即ち、検査行列の１行に亘る全ての枝からのメッセージD104の符号ビットD121が乗算された値D131（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）を選択し、値D132としてレジスタ１３２に出力して格納させる。レジスタ１３２は、格納している値D132を、値D133としてセレクタ１３１とEXOR回路１３４に供給する。
【００７５】
検査行列の1行に亘る全ての枝からのメッセージD104の符号ビットD121が乗算された乗算結果D130（ｉ＝１からｄcまでのΠsign(vi)）がレジスタ１３０に格納される直前までは、セレクタ１３１は、レジスタ１３２から供給された値D133を選択し、レジスタ１３２に出力して再格納させる。即ち、検査行列の１行に亘る全ての枝からのメッセージD104（メッセージvi）の符号ビットD121が乗算されるまで、レジスタ１３２は、前回格納した値を、セレクタ１３１とEXOR回路１３４に供給する。
【００７６】
一方、FIFOメモリ１３３は、レジスタ１３２から新たな値D133（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）がEXOR回路１３４に供給されるまでの間、符号ビットD121を遅延し、１ビットの値D134としてEXOR回路１３４に供給する。EXOR回路１３４は、レジスタ１３２から供給された値D133と、FIFOメモリ１３３から供給された値D134との排他的論理和を演算することにより、値D133を、値D134で除算し、除算結果を除算値D135として出力する。即ち、EXOR回路１３４は、検査行列の１行に亘る全ての枝からのメッセージD104の符号ビットD121（sign(vi)）の乗算値を、求めたい枝からのメッセージD104の符号ビットD121（sign(vi)）で除算して、その除算値（ｉ＝１からｉ＝ｄc−１までのΠsign(vi)）を除算値D135として出力する。
【００７７】
そして、チェックノード計算器１０３では、LUT１２８から出力された演算結果D129を下位ビットとするとともに、EXOR回路１３４から出力された除算値D135を最上位ビット（符号ビット）とするビット列がメッセージD105（メッセージuj）として、出力ポートP112から出力される。
【００７８】
以上のように、チェックノード計算器１０３では、式（７）の演算が行われ、メッセージ（チェックノードメッセージ）ujが求められる。
【００７９】
なお、図示しないが、図８の復号装置では、復号の最終段において、式（１）のバリアブルノード演算の代わりに、式（５）の演算が行われ、その演算結果が、最終的な復号結果として出力される。
【００８０】
図８の復号装置によれば、メッセージメモリ１０４（図８）、バリアブルノード計算器１０２（図９）のFIFOメモリ１５５、チェックノード計算器１０３（図１０）のFIFOメモリ１２７および１３３の容量さえ足りれば、様々な検査行列のLDPC符号を復号することができる。
【００８１】
次に、図１１は、図８の復号装置のメッセージメモリ１０４に対するメッセージの読み書きのタイミングを示すタイミングチャートである。
【００８２】
図８の復号装置において、バリアブルノード演算時には、メッセージメモリ１０４から、チェックノードからのメッセージ（チェックノードメッセージ）ujが読み出され、メッセージ計算部１０１のバリアブルノード計算器１０２が、メッセージメモリ１０４から読み出されたメッセージujを用いてバリアブルノード演算を行う一方で、そのバリアブルノード演算の結果得られるメッセージ（バリアブルノードメッセージ）viが、メッセージメモリ１０４に書き込まれる。
【００８３】
また、チェックノード演算時には、メッセージメモリ１０４から、バリアブルノードからのメッセージ（バリアブルノードメッセージ）viが読み出され、メッセージ計算部１０１のチェックノード計算器１０３が、メッセージメモリ１０４から読み出されたメッセージviを用いてチェックノード演算を行う一方で、そのチェックノード演算の結果得られるメッセージ（チェックノードメッセージ）ujが、メッセージメモリ１０４に書き込まれる。
【００８４】
従って、図８の復号装置では、バリアブルノード演算時であっても、チェックノード演算時であっても、メッセージメモリ１０４からのメッセージの読み出しと、そのメッセージを用いたバリアブルノード演算またはチェックノード演算（以下、適宜、両方まとめて、単に、ノード演算ともいう）の結果得られるメッセージの書き込みとを同時に行う必要がある。
【００８５】
このため、メッセージメモリ１０４は、例えば、１つのバンク（メモリバンク）としての１つのRAM(Random Access Memory)#Aと、他の１つのバンクとしての他の１つのRAM#Bとから構成され、RAM#AとRAM#Bのそれぞれにアクセスすることにより、メッセージメモリ１０４に対しては、見かけ上、同時に、２つのアクセスを行うことが可能になっている。
【００８６】
図１１のタイミングチャートは、メッセージメモリ１０４を構成するRAM#AとRAM#Bのそれぞれに対する読み書きのタイミングを表している。
【００８７】
図１１においては、まず最初に、RAM#Aから、あるチェックノードまたはバリアブルノード（以下、適宜、両方まとめて、単に、ノードともいう）node#1の枝に対応するメッセージを求めるのに必要なメッセージが読み出され(R(node#1))、そのメッセージを用いてノード演算が行われる。そして、そのノード演算の結果得られる、ノードnode#1の枝に対応するメッセージがRAM#Aに書き込まれる(W(node#1))のと同時に、RAM#Bから、次のノードnode#2の枝に対応するメッセージを求めるのに必要なメッセージが読み出され(R(node#2))、ノード演算が行われる。
【００８８】
さらに、そのノード演算の結果得られる、ノードnode#2の枝に対応するメッセージがRAM#Bに書き込まれる(W(node#2))のと同時に、RAM#Aから、次のノードnode#3の枝に対応するメッセージを求めるのに必要なメッセージが読み出され(R(node#3)、ノード演算が行われる。以下、同様にして、メッセージメモリ１０４を構成するRAM#AとRAM#Bのそれぞれに対するメッセージの読み書きが行われていく。
【００８９】
なお、図８の復号装置において、チェックノード演算とバリアブルノード演算とを交互に行う繰り返し復号によって、LDPC符号を復号する場合には、１回の復号（１セットのチェックノード演算とバリアブルノード演算）に、メッセージの数の２倍のクロック数が必要となり、高速な動作が要求されることになる。
【００９０】
そこで、特定の検査行列のLDPC符号については、メッセージ計算部１０１を複数であるp個設けることによって、p個のノードについてメッセージを同時に求め、１回の復号を、図８の復号装置の場合の1/pのクロック数で行うことができる復号装置、即ち、それほど高くない動作周波数での動作が可能な復号装置が提案されている（例えば、特許文献１参照）。
【００９１】
【特許文献１】特開2004-364233号公報
【発明の開示】
【発明が解決しようとする課題】
【００９２】
ところで、上述したように、メッセージ計算部１０１を構成するバリアブルノード計算器１０２（図９）には、演算器１５１およびレジスタ１５２でのメッセージの積算が終了するまでメッセージを遅延するFIFOメモリ１５５が設けられている。同様に、チェックノード計算器１０３（図１０）にも、演算器１２２およびレジスタ１２３での積算が終了するまでφ(|vi|)を遅延するFIFOメモリ１２７と、EXOR回路１２９およびレジスタ１３０での符号ビットの相乗積の算出が終了するまで符号ビットを遅延するFIFOメモリ１３３が設けられている。このように、LDPC符号を復号する復号装置においては、データ（メッセージ）を遅延するためのメモリが必要となる。
【００９３】
特に、ノードの数(degree)が多いLDPC符号を復号する復号装置を、それほど高くない動作周波数で動作させるためには、復号装置を、複数のノードのメッセージを並列で求めるのに複数のメッセージ計算部１０１を設けて構成する必要があり、この場合、データを遅延するためのメモリがさらに必要となって、復号装置が大規模化することになる。
【００９４】
本発明は、このような状況に鑑みてなされたものであり、LDPC符号を復号する復号装置の規模を削減することができるようにするものである。
【課題を解決するための手段】
【００９５】
本発明の一側面の復号装置、又は、プログラムは、LDPC(Low Density Parity Check)符号を復号する復号装置であり、供給されるメッセージを用いて、前記LDPC符号の復号のためのバリアブルノードの演算と、チェックノードの演算とを、選択的に行い、演算の結果得られるメッセージを出力するメッセージ計算手段と、前記メッセージを記憶する記憶手段と、前記メッセージ計算手段が出力するメッセージを前記記憶手段に書き込む書き込み制御と、前記メッセージ計算手段での演算に用いられる同一のメッセージを、前記記憶手段から２回読み出し、前記メッセージ計算手段に供給する読み出し制御とを行う制御手段とを備え、前記メッセージ計算手段において、バリアブルノードの演算を行う回路と、チェックノードの演算を行う回路との一部が共有化されている復号装置、又は、復号装置として、コンピュータを機能させるためのプログラムである。
【００９６】
本発明の一側面の制御方法は、LDPC(Low Density Parity Check)符号を復号する復号装置を制御する制御方法であり、前記復号装置は、供給されるメッセージを用いて、前記LDPC符号の復号のためのバリアブルノードの演算と、チェックノードの演算とを、選択的に行い、演算の結果得られるメッセージを出力するメッセージ計算手段と、前記メッセージを記憶する記憶手段とを備え、前記メッセージ計算手段において、バリアブルノードの演算を行う回路と、チェックノードの演算を行う回路との一部が共有化されており、前記メッセージ計算手段が出力するメッセージを前記記憶手段に書き込む書き込み制御と、前記メッセージ計算手段での演算に用いられる同一のメッセージを、前記記憶手段から２回読み出し、前記メッセージ計算手段に供給する読み出し制御とを行うステップを含む制御方法である。
【００９７】
本発明の一側面の復号装置、制御方法、またはプログラムにおいては、前記メッセージ計算手段が出力するメッセージを前記記憶手段に書き込む書き込み制御と、前記メッセージ計算手段での演算に用いられる同一のメッセージを、前記記憶手段から２回読み出し、前記メッセージ計算手段に供給する読み出し制御とが行われる。
【発明の効果】
【００９８】
本発明の一側面によれば、LDPC符号を復号する復号装置の規模を削減することができる。
【発明を実施するための最良の形態】
【０１０２】
また、前記メッセージ計算手段には、
バリアブルノードの演算を行うバリアブルノード計算手段（例えば、図１２のバリアブルノード計算器１７２）と、
チェックノードの演算を行うチェックノード計算手段（例えば、図１２のチェックノード計算器１７３）と
を設けることができる。
【０１０５】
前記メッセージ計算手段には、バリアブルノードから出力された出力データxに対して、逆関数φ-1(x)=2tanh-1(e-x)と同一の演算結果が得られる非線形関数φ(x)=-ln(tanh(x/2))の演算結果を出力するとともに、チェックノードから出力された出力データxに対して、前記逆関数φ-1(x)の演算結果を出力するLUT(Look Up Table)（例えば、図３２のLUT７１３）を設けることができる。
【０１０７】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。
【０１０８】
図１２は、本発明を適用した復号装置の第１実施の形態の構成例を示すブロック図である。
【０１０９】
なお、図中、図８の復号装置と対応する部分については、同一の符号を付してあり、以下では、その説明は、適宜省略する。即ち、図１２の復号装置は、メッセージ計算部１０１に代えてメッセージ計算部１７１が設けられているとともに、制御部１０６に代えて制御部１７４が設けられている他は、図８の復号装置と同様に構成されている。
【０１１０】
図１２の復号装置は、図８の復号装置と同様に、フルシリアルの復号を繰り返し行う。
【０１１１】
即ち、図１２の復号装置は、メッセージメモリ１０４、受信データメモリ１０５、メッセージ計算部１７１、制御部１７４からなる。また、メッセージ計算部１７１は、バリアブルノード計算器１７２とチェックノード計算器１７３とから構成されている。
【０１１２】
図１２の復号装置では、メッセージメモリ１０４から、メッセージが１つずつ読み出され、メッセージ計算部１７１において、そのメッセージを用いて、所望の枝に対応するメッセージが計算される。そして、その計算によって求められたメッセージが、メッセージメモリ１０４に格納されていく。図１２の復号装置では、以上の処理が繰り返し行われることで、繰り返し復号が行われる。
【０１１３】
即ち、受信データメモリ１０５には、送信されてきたLDPC符号を受信することにより得られる、符号の0（または1）らしさを表す対数尤度比である受信データ（LDPC符号）D100が供給され、受信データメモリ１０５は、その受信データD100を格納（記憶）する。
【０１１４】
バリアブルノード演算時には、受信データメモリ１０５は、制御部１７４から供給される制御信号にしたがって、記憶している受信データを読み出し、受信データD101として、メッセージ計算部１７１のバリアブルノード計算器１７３に供給する。
【０１１５】
また、バリアブルノード演算時には、メッセージメモリ１０４は、制御部１７４から供給される制御信号にしたがい、記憶している同一のメッセージを２回読み出して、（注目しているバリアブルノードから出力されるバリアブルノードメッセージviを求めるのに必要なチェックノードメッセージ（注目しているバリアブルノードに接続されているチェックノードからのチェックノードメッセージ）ujを、２回繰り返し読み出して）１回目に読み出したメッセージをメッセージD102として、バリアブルノード計算器１７２に供給し、２回目に読み出したメッセージをメッセージDD102として、バリアブルノード計算器１７２に供給する。バリアブルノード計算器１７２は、メッセージメモリ１０４から供給されるメッセージD102とDD102、および受信データメモリ１０５から供給される受信データD101を用い、式（１）のバリアブルノード演算を行い、そのバリアブルノード演算の結果得られたメッセージ（バリアブルノードメッセージ）viを、メッセージD103として、メッセージメモリ１０４に供給する。
【０１１６】
そして、メッセージメモリ１０４は、制御部１７４から供給される制御信号にしたがい、バリアブルノード計算器１７２から供給されるメッセージD103を記憶する（書き込む）。
【０１１７】
一方、チェックノード演算時には、メッセージメモリ１０４は、制御部１７４から供給される制御信号にしたがって、記憶している同一のメッセージ（バリアブルノードメッセージvi）を２回読み出して（注目しているチェックノードから出力されるチェックノードメッセージujを求めるのに必要なバリアブルノードメッセージ（注目しているチェックノードに接続されているバリアブルノードからのバリアブルノードメッセージ）viを、２回繰り返し読み出して）、１回目に読み出したメッセージをメッセージD104として、チェックノード計算器１７３に供給し、２回目に読み出したメッセージをメッセージDD104として、チェックノード計算器１７３に供給する。
【０１１８】
チェックノード計算器１７３は、メッセージメモリ１０４から供給されるメッセージD104とDD104を用いて、式（７）のチェックノード演算を行い、そのチェックノード演算によって求められたメッセージ（チェックノードメッセージ）ujを、メッセージD105として、メッセージメモリ１０４に供給する。
【０１１９】
そして、メッセージメモリ１０４は、制御部１７４から供給される制御信号にしたがい、チェックノード計算器１７３から供給されるメッセージD105を記憶する（書き込む）。
【０１２０】
メッセージメモリ１０４が記憶したチェックノード計算器１７３からのメッセージD105、即ち、チェックノードメッセージujは、次のバリアブルノード演算時に、メッセージD102およびDD102として読み出され、バリアブルノード計算器１７２に供給される。
【０１２１】
図１３は、図１２のバリアブルノード計算器１７２の構成例を示している。
【０１２２】
なお、図中、図９のバリアブルノード計算器１０２と対応する部分については、同一の符号を付してあり、以下では、その説明は、適宜省略する。
【０１２３】
バリアブルノード計算器１７２は、データを遅延するためのメモリ（図９のバリアブルノード計算器１０２に設けられているFIFOメモリ１５５）を設けずに構成されている。
【０１２４】
但し、バリアブルノード計算器１７２は、外部からメッセージ（データ）が供給（入力）される入力ポートとして、３つの入力ポートP101,P102,PD102を有している。
【０１２５】
入力ポートP101には、受信データメモリ１０５から読み出された受信データD101が供給（入力）される。また、入力ポートP102には、メッセージメモリ１０４から２回読み出される同一のメッセージD102およびDD102のうちの１回目に読み出されるメッセージD102が供給（入力）され、入力ポートPD102には、２回目に読み出されるメッセージDD102が供給される。
【０１２６】
チェックノード計算器１７３は、入力ポートP101,P102,PD102それぞれから入力されるメッセージを用いて、式（１）のバリアブルノード演算を行い、その結果得られるメッセージを、出力ポートP103から出力する。
【０１２７】
即ち、入力ポートP101には、受信データメモリ１０５から読み出された受信データD101が供給される。また、入力ポートP102には、メッセージメモリ１０４から読み出されたメッセージD102（チェックノードメッセージuj）が供給される。
【０１２８】
そして、バリアブルノード計算器１７２では、検査行列の各行に対応するチェックノードからのメッセージD102、即ち、メッセージメモリ１０４から１回目に読み出されたメッセージujが、入力ポートP102から１つずつ入力され、そのメッセージD102が、演算器１５１に供給される。
【０１２９】
また、バリアブルノード計算器１７２では、受信データメモリ１０５から受信データD101が入力ポートP101から1つずつ読み込まれ、演算器１５７に供給される。
【０１３０】
演算器１５１は、メッセージD102（メッセージuj）とレジスタ１５２に格納されている値D151とを加算することにより、メッセージD102を積算し、その結果得られる積算値を、レジスタ１５２に再格納する。なお、検査行列の1列に亘る全ての枝からのメッセージD102が積算された場合、レジスタ１５２はリセットされる。
【０１３１】
検査行列の1列に亘るメッセージD102が１つずつ読み込まれ、レジスタ１５２に1列分のメッセージD102が積算された値が格納された場合、即ち、レジスタ１５２に、検査行列の１列に亘る全ての枝からのメッセージD102（メッセージuj）が積算された積算値（ｊ＝１からｄVまでのΣuj)が格納された場合、セレクタ１５３は、レジスタ１５２に格納されている値、即ち、検査行列の１列に亘る全ての枝からのメッセージD102（メッセージuj）が積算された積算値D151（ｊ＝１からｄVまでのΣuj)を選択し、レジスタ１５４に出力して格納させる。
【０１３２】
レジスタ１５４は、格納している値D151を、値D152として、セレクタ１５３と演算器１５６に供給する。レジスタ１５２に1列分のメッセージD102が積算された値が格納される直前までは、セレクタ１５３は、レジスタ１５４から供給された値D152を選択し、レジスタ１５４に出力し再格納させる。即ち、検査行列の１列に亘る全ての枝からのメッセージD102（メッセージuj）が積算されるまで、レジスタ１５４は、前回積算された値を、セレクタ１５３と演算器１５６に供給する。
【０１３３】
一方、レジスタ１５４から新たな値D152（ｊ＝１からｄVまでのΣuj)の出力が開始されると、即ち、レジスタ１５２に1列分のメッセージD102が積算された積算値（ｊ＝１からｄVまでのΣuj)が格納された直後、バリアブルノード計算器１７２においては、メッセージD102（メッセージuj）と同一のメッセージDD102、即ち、メッセージメモリ１０４から２回目に読み出されたメッセージujが、入力ポートPD102から１つずつ入力され、そのメッセージDD102が、演算器１５６に供給される。
【０１３４】
演算器１５６は、レジスタ１５４から供給された積算値D152から、入力ポートPD102からのメッセージDD102を減算する。即ち、演算器１５６では、検査行列の1列に亘る全ての枝からのメッセージD102（メッセージuj）の積算値D152（ｊ＝１からｄvまでのΣuj）から、求めたい枝からのメッセージuj（ｊ＝ｄvのuj）としてのメッセージDD102を減算して、減算値（ｊ＝１からｄv−１までのΣuj）を求め、演算器１５７に供給する。
【０１３５】
演算器１５７は、入力ポートP101からの受信データD101と、演算器１５６からの減算値（ｊ＝１からｄv−１までのΣuj）とを加算し、その結果得られる加算値をメッセージD103（メッセージvi）として、出力ポートP103から出力する。
【０１３６】
以上のように、バリアブルノード計算器１７２では、式（１）のバリアブルノード演算が行われ、その結果得られるメッセージ（バリアブルノードメッセージ）viが、出力ポートP103から出力される。
【０１３７】
図１４は、図１２のチェックノード計算器１７３の構成例を示している。
【０１３８】
なお、図中、図１０のチェックノード計算器１０３と対応する部分については、同一の符号を付してあり、以下では、その説明は、適宜省略する。
【０１３９】
チェックノード計算器１７３は、データを遅延するためのメモリ（図１０のチェックノード計算器１０３に設けられているFIFOメモリ１２７および１３３）を設けずに構成されている。
【０１４０】
但し、チェックノード計算器１７３は、外部からメッセージ（データ）が供給（入力）される入力ポートとして、２つの入力ポートP111とPD111を有している。
【０１４１】
入力ポートP111には、メッセージメモリ１０４から２回読み出される同一のメッセージD104およびDD104のうちの１回目に読み出されるメッセージD104が供給（入力）され、入力ポートPD111には、２回目に読み出されるメッセージDD104が供給される。
【０１４２】
チェックノード計算器１７３は、入力ポートP111とPD111それぞれから入力されるメッセージを用いて、式（７）のチェックノード演算を行い、その結果得られるメッセージを、出力ポートP112から出力する。
【０１４３】
即ち、入力ポートP111には、メッセージメモリ１０４から読み出されたメッセージD104（バリアブルノードメッセージuj）が供給される。
【０１４４】
そして、チェックノード計算器１７３では、検査行列の各列に対応するバリアブルノードからのメッセージD104（メッセージvi）が入力ポートP111から１つずつ入力され、その最上位ビットを除く下位ビット、つまり、メッセージD104の絶対値D122(|vi|)が、LUT１２１に供給されるとともに、最上位ビット、つまりメッセージD104の符号ビットD121が、EXOR回路１２９に供給される。
【０１４５】
LUT１２１は、絶対値D122(|vi|)を引数として、非線形関数φ(|vi|)の演算を行った演算結果D123（φ(|vi|)）を読み出し、演算器１２２に供給する。
【０１４６】
演算器１２２は、演算結果D123（φ(|vi|)）とレジスタ１２３に格納されている値D124とを加算することにより、演算結果D123を積算し、その結果得られる積算値をレジスタ１２３に再格納する。なお、検査行列の1行に亘る全ての枝からのメッセージD104の絶対値D122(|vi|)に対する演算結果D123（φ(|vi|)）が積算された場合、レジスタ１２３はリセットされる。
【０１４７】
検査行列の1行に亘るメッセージD104が１つずつ読み込まれ、レジスタ１２３に1行分の演算結果D123が積算された積算値が格納された場合、セレクタ１２４は、レジスタ１２３に格納されている値、即ち、検査行列の１行に亘る全ての枝からのメッセージD104（メッセージvi）から求められたφ(|vi|)が積算された積算値D124（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）を選択し、積算値D125として、レジスタ１２５に出力して格納させる。レジスタ１２５は、格納している積算値D125を、値D126として、セレクタ１２４と演算器１２６に供給する。
【０１４８】
レジスタ１２３に1行分の演算結果D123が積算された積算値が格納される直前までは、セレクタ１２４は、レジスタ１２５から供給された値D126を選択し、レジスタ１２５に出力して再格納させる。即ち、検査行列の１行に亘る全ての枝からのメッセージD104（メッセージvi）から求められたφ(|vi|)が積算されるまで、レジスタ１２５は、前回積算されたφ(|vi|)の積算値を、セレクタ１２４と演算器１２６に供給する。
【０１４９】
一方、レジスタ１２５から新たな値D126（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）の出力が開始されると、即ち、レジスタ１２５に1行分の演算結果D123が積算された積算値（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）が格納された直後、チェックノード計算器１７３において、メッセージD104（メッセージvi）と同一のメッセージDD104、即ち、メッセージメモリ１０４から２回目に読み出されたメッセージviが、入力ポートPD104から１つずつ入力され、そのメッセージDD104のうちのその最上位ビットを除く下位ビット、つまり、メッセージDD104の絶対値(|vi|)が、LUT１３５に供給されるとともに、最上位ビット、つまりメッセージDD104の符号ビットが、EXOR回路１３４に供給される。
【０１５０】
LUT１３５は、LUT１２１と同様のLUTで、メッセージDD104の絶対値(|vi|)を引数として、非線形関数φ(|vi|)の演算を行った演算結果（φ(|vi|)）を読み出し、演算器１２６に供給する。
【０１５１】
演算器１２６は、レジスタ１２５から供給された値D126から、LUT１３５からの演算結果（φ(|vi|)）を減算し、減算結果を、減算値D128としてLUT１２８に供給する。即ち、演算器１２６は、検査行列の1行に亘る全ての枝からのメッセージD104（メッセージvi）から求められたφ(|vi|)の積算値（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）から、求めたい枝からのメッセージvi（ｉ＝ｄcのvi）としてのメッセージDD104から求められたφ(|vi|)を減算して、その減算値（ｉ＝１からｉ＝ｄc−１までのΣφ(|vi|)）を減算値D128としてLUT１２８に供給する。
【０１５２】
LUT１２８は、演算器１２６からの減算値D128（ｉ＝１からｉ＝ｄc−１までのΣφ(|vi|)）を引数として、逆関数φ-1（Σφ(|vi|)）の演算を行った演算結果D129（φ-1(Σφ(|vi|)))を出力する。
【０１５３】
以上の処理と並行して、EXOR回路１２９は、レジスタ１３０に格納されている値D131と符号ビット（正負を表すビット）D121との排他的論理和を演算することにより、符号ビットどうしの乗算を行い、乗算結果D130をレジスタ１３０に再格納する。なお、検査行列の1行に亘る全ての枝からのメッセージD104の符号ビットD121が乗算された場合、レジスタ１３０はリセットされる。
【０１５４】
検査行列の1行に亘る全ての枝からのメッセージD104の符号ビットD121が乗算された乗算結果D130（ｉ＝１からｄcまでのΠsign(vi)）がレジスタ１３０に格納された場合、セレクタ１３１は、レジスタ１３０に格納されている値、即ち、検査行列の１行に亘る全ての枝からのメッセージD104の符号ビットD121が乗算された値D131（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）を選択し、値D132としてレジスタ１３２に出力して格納させる。レジスタ１３２は、格納している値D132を、値D133としてセレクタ１３１とEXOR回路１３４に供給する。
【０１５５】
検査行列の1行に亘る全ての枝からのメッセージD104の符号ビットD121が乗算された乗算結果D130（ｉ＝１からｄcまでのΠsign(vi)）がレジスタ１３０に格納される直前までは、セレクタ１３１は、レジスタ１３２から供給された値D133を選択し、レジスタ１３２に出力して再格納させる。即ち、検査行列の１行に亘る全ての枝からのメッセージD104（メッセージvi）の符号ビットD121が乗算されるまで、レジスタ１３２は、前回格納した値を、セレクタ１３１とEXOR回路１３４に供給する。
【０１５６】
一方、レジスタ１３２から新たな値D133（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）がEXOR回路１３４に供給されたとき、即ち、レジスタ１３０に１行に亘る全ての枝からのメッセージD104の符号ビットD121が乗算された値D131（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）が格納されたとき、上述したように、レジスタ１２５には、1行分の演算結果D123が積算された積算値（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）が格納される。
【０１５７】
レジスタ１２５に1行分の演算結果D123が積算された積算値（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）が格納されると、上述したように、チェックノード計算器１７３において、メッセージD104（メッセージvi）と同一のメッセージDD104、即ち、メッセージメモリ１０４から２回目に読み出されたメッセージviが、入力ポートPD104から１つずつ入力され、そのメッセージDD104のうちのその最上位ビットを除く下位ビット、つまり、メッセージDD104の絶対値(|vi|)が、LUT１３５に供給されるとともに、最上位ビット、つまりメッセージDD104の符号ビットが、EXOR回路１３４に供給される。
【０１５８】
EXOR回路１３４は、レジスタ１３２から供給された値D133と、入力ポートPD104からのメッセージDD104の符号ビットとの排他的論理和を演算することにより、値D133を、メッセージDD104の符号ビットで除算し、除算結果を除算値D135として出力する。即ち、EXOR回路１３４は、検査行列の１行に亘る全ての枝からのメッセージD104の符号ビットD121の乗算値（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）を、求めたい枝からのメッセージviとしてのメッセージDD104の符号ビットD121（ｉ＝ｄcのsign(vi)）で除算して、その除算値（ｉ＝１からｉ＝ｄc−１までのΠsign(vi)）を除算値D135として出力する。
【０１５９】
そして、チェックノード計算器１７３では、LUT１２８から出力された演算結果D129を下位ビットとするとともに、EXOR回路１３４から出力された除算値D135を最上位ビット（符号ビット）とするビット列がメッセージD105（メッセージuj）として、出力ポートP112から出力される。
【０１６０】
以上のように、チェックノード計算器１７３では、式（７）の演算が行われ、メッセージ（チェックノードメッセージ）ujが求められる。
【０１６１】
なお、図示しないが、図１２の復号装置では、復号の最終段において、式（１）のバリアブルノード演算の代わりに、式（５）の演算が行われ、その演算結果が、最終的な復号結果として出力される。
【０１６２】
次に、図１５のフローチャートを参照して、図１２の復号装置の制御部１７４によるメッセージメモリ１０４に対するメッセージ（データ）の読み書き制御の処理について説明する。
【０１６３】
なお、以下、適宜、ノードにおいてメッセージを求めるのに用いられる、そのノードに入力されるメッセージを、入力メッセージというとともに、ノードにおいて、入力メッセージを用いて求められて出力されるメッセージを、出力メッセージという。
【０１６４】
ステップＳ１０１において、制御部１７４は、ある注目しているノード（注目ノード）から出力される出力メッセージ（注目ノードに接続している枝から出力されるメッセージ）を求めるのに必要な入力メッセージ、即ち、注目ノードに接続している枝から入力されるメッセージを読み出し、メッセージ計算部１７１に供給するように（入力メッセージの１回目の読み出しを行うように）、メッセージメモリ１０４を制御して、ステップＳ１０２に進む。
【０１６５】
ステップＳ１０２では、制御部１７４は、直前のステップＳ１０１でメッセージメモリ１０４から読み出したのと同一の入力メッセージを読み出し、メッセージ計算部１７１に供給するように（入力メッセージの２回目の読み出しを行うように）、メッセージメモリ１０４を制御して、ステップＳ１０３に進む。
【０１６６】
即ち、ステップＳ１０１およびＳ１０２では、メッセージ計算部１７１での演算（チェックノード演算またはバリアブルノード演算）に用いられる同一の入力メッセージを、メッセージメモリ１０４から２回読み出し、メッセージ計算部１７１に供給する読み出し制御が行われる。
【０１６７】
ステップＳ１０３では、制御部１７４は、メッセージ計算部１７１がステップＳ１０１とＳ１０２でメッセージメモリ１０４から読み出された入力メッセージを用いて演算を行うことにより求めた出力メッセージを書き込むように、メッセージメモリ１０４を制御する。
【０１６８】
即ち、ステップＳ１０３では、メッセージ計算部１７１が式（１）または式（７）の演算を行うことによって出力する出力メッセージをメッセージメモリ１０４に書き込む書き込み制御が行われる。
【０１６９】
そして、ステップＳ１０３からステップＳ１０１に戻り、制御部１７４は、他のノードを新たな注目ノードとし、その新たな注目ノードから出力される出力メッセージを求めるのに必要な入力メッセージを読み出して、メッセージ計算部１７１に供給するように、メッセージメモリ１０４を制御し、以下、同様の処理を繰り返す。
【０１７０】
メッセージメモリ１０４は、前述したように、RAM#AとRAM#Bとの２バンク構成になっており、制御部１７４は、そのRAM#AとRAM#Bのそれぞれを対象に、図１５で説明した読み書き制御を行う。
【０１７１】
即ち、図１６は、図１２の復号装置のメッセージメモリ１０４に対するメッセージの読み書きのタイミングを示すタイミングチャートである。
【０１７２】
図１６のタイミングチャートは、前述の図１１のタイミングチャートと同様に、メッセージメモリ１０４を構成するRAM#AとRAM#Bのそれぞれに対する読み書きのタイミングを表している。
【０１７３】
図１６においては、まず最初に、あるノードnode#1からの出力メッセージを求めるのに必要な入力メッセージの、RAM#Aからの１回目の読み出しが行われる(R1(node#1))。その読み出しの終了後、ノードnode#1からの出力メッセージを求めるのに必要な入力メッセージの、RAM#Aからの２回目の読み出しが行われる(R2(node#1))のと同時に、次のノードnode#2からの出力メッセージを求めるのに必要な入力メッセージの、RAM#Bからの１回目の読み出しが行われる(R1(node#2))。
【０１７４】
ノードnode#1からの出力メッセージを求めるのに必要な入力メッセージの、RAM#Aからの２回目の読み出しが終了し、メッセージ計算部１７１において、ノードnode#1からの出力メッセージが求められると、そのノードnode#1からの出力メッセージがRAM#Aに書き込まれる(W(node#1))のと同時に、ノードnode#2からの出力メッセージを求めるのに必要な入力メッセージの、RAM#Bからの２回目の読み出しが行われる(R2(node#2))。
【０１７５】
ノードnode#2からの出力メッセージを求めるのに必要な入力メッセージの、RAM#Bからの２回目の読み出しが終了し、メッセージ計算部１７１において、ノードnode#2からの出力メッセージが求められると、そのノードnode#2からの出力メッセージがRAM#Bに書き込まれる(W(node#2))のと同時に、次のノードnode#3からの出力メッセージを求めるのに必要な入力メッセージの、RAM#Aからの１回目の読み出しが行われる(R1(node#3))。
【０１７６】
ノードnode#2からの出力メッセージのRAM#Bへの書き込みと、ノードnode#3からの出力メッセージを求めるのに必要な入力メッセージの、RAM#Aからの１回目の読み出しとが終了すると、ノードnode#3からの出力メッセージを求めるのに必要な入力メッセージの、RAM#Aからの２回目の読み出しが行われる(R2(node#3))のと同時に、次のノードnode#4からの出力メッセージを求めるのに必要な入力メッセージの、RAM#Bからの１回目の読み出しが行われる(R1(node#4))。
【０１７７】
ノードnode#3からの出力メッセージを求めるのに必要な入力メッセージの、RAM#Aからの２回目の読み出しが終了し、メッセージ計算部１７１において、ノードnode#3からの出力メッセージが求められると、そのノードnode#3からの出力メッセージがRAM#Aに書き込まれる(W(node#3))のと同時に、ノードnode#4からの出力メッセージを求めるのに必要な入力メッセージの、RAM#Bからの２回目の読み出しが行われる(R2(node#4))。
【０１７８】
以下、同様にして、メッセージメモリ１０４を構成するRAM#AとRAM#Bのそれぞれに対するメッセージの読み書きが行われていく。
【０１７９】
図１２の復号装置によれば、メッセージ計算部１７１において出力メッセージを求めるのに必要な（同一の）入力メッセージを、メッセージメモリ１０４から２回読み出すことによって、メッセージ計算部１７１の内部において、入力メッセージを遅延せずに済むので、メッセージ計算部１７１を、データを遅延するためだけのメモリ（図９のバリアブルノード計算器１０２に設けられているFIFOメモリ１５５、並びに図１０のチェックノード計算器１０３に設けられているFIFOメモリ１２７および１３３）を設けずに構成することができる。そして、その結果、復号装置の規模を削減することができる
【０１８０】
なお、データを遅延するためだけのメモリ（以下、適宜、遅延メモリという）を設けずに、メッセージメモリ１０４から同一の入力メッセージを２回読み出す図１２の復号装置におけるメッセージメモリ１０４に対するメッセージの読み書きのタイミング（図１６）と、遅延メモリを設けて、メッセージメモリ１０４から入力メッセージを１回だけ読み出す図８の復号装置におけるメッセージメモリ１０４に対するメッセージの読み書きのタイミング（図１１）とを比較して分かるように、図１２の復号装置は、あるノードからの出力メッセージを求めるのに、図８の復号装置の1.5倍程度の時間を要し、その分だけ高速に動作することが要求される（高速な動作クロックを必要とする）。
【０１８１】
しかしながら、特に、ノードすべてについて、出力メッセージを求める演算を同時（並列）に行うフルパラレルの復号(full parallel decoding)を行う復号装置や、１つでもなくすべてでもないp個のノードについて、出力メッセージを求める演算を同時に行う一部並列の復号（例えば、特許文献１に記載の復号）を行う復号装置を、遅延メモリを設けて構成した場合には、多数の遅延メモリが必要となり、装置全体の規模に大きく影響する。
【０１８２】
かかる復号装置において、図１２の復号装置のように、メッセージメモリ１０４から同一の入力メッセージを２回読み出して、出力メッセージを求めることにより、遅延メモリを不要とする構成を採用することにより、復号装置において多少の高速な動作が要求されることにはなるが、その代償として、極めて大きな装置規模の削減の効果を得ることができる。
【０１８３】
なお、本明細書では、説明を簡単にするために、フルシリアルの復号装置を説明するが、図１２の復号装置を含め、以下説明する復号装置の構成や処理の方法は、フルパラレルの復号を行う復号装置や、一部並列の復号を行う復号装置に適用することができ、そのような復号装置に適用した場合に、特に大きな装置規模の削減の効果を得ることができる。
【０１８４】
ところで、図１２の復号装置では、出力メッセージを求める手段としてのメッセージ計算部１７１を、バリアブルノード演算を行うバリアブルノード計算器１７２と、チェックノード演算を行うチェックノード計算器１７３とで構成するようにしたが、出力メッセージを求める手段は、バリアブルノード演算を行う回路と、チェックノード演算を行う回路との一部を共有化して構成し、バリアブルノード演算とチェックノード演算とを、選択的に行うようにすることができる。
【０１８５】
そこで、次に、バリアブルノード演算を行う回路と、チェックノード演算を行う回路との一部を共有化し、かつ、遅延メモリを設けずに構成された復号装置について説明するが、その前段階の準備として、バリアブルノード演算を行う回路と、チェックノード演算を行う回路との一部が共有化され、かつ、遅延メモリが設けられた復号装置について説明する。
【０１８６】
即ち、図１７は、そのような復号装置の構成例を示すブロック図である。
【０１８７】
なお、図中、図８の復号装置と対応する部分については、同一の符号を付してあり、以下では、その説明は、適宜省略する。即ち、図１７の復号装置は、メッセージ計算部１０１に代えてメッセージ計算部１９１が設けられているとともに、制御部１０６に代えて制御部１９２が設けられている他は、図８の復号装置と同様に構成されている。
【０１８８】
図１７の復号装置は、図８の復号装置と同様に、フルシリアルの復号を繰り返し行う。
【０１８９】
図１７の復号装置では、メッセージメモリ１０４からメッセージ計算部１９１に、入力メッセージが１つずつ読み出され、メッセージ計算部１９１において、その入力メッセージを用いて、所望の枝に対応する出力メッセージが計算される。そして、その計算によって求められた出力メッセージが、メッセージメモリ１０４に格納されていく。図１７の復号装置では、以上の処理が繰り返し行われ、いわゆる繰り返し復号が行われる。
【０１９０】
即ち、受信データメモリ１０５には、送信されてきたLDPC符号を受信することにより得られる、符号の0（または1）らしさを表す対数尤度比である受信データ（LDPC符号）D100が供給され、受信データメモリ１０５は、その受信データD100を記憶する。
【０１９１】
バリアブルノード演算時には、受信データメモリ１０５は、制御部１９２から供給される制御信号にしたがって、記憶している受信データを読み出し、受信データD101として、メッセージ計算部１９１に供給する。
【０１９２】
また、バリアブルノード演算時には、メッセージメモリ１０４は、制御部１９２から供給される制御信号にしたがって、記憶しているメッセージD201を読み出し、メッセージ計算部１９１に供給する。さらに、バリアブルノード演算時には、制御部１９２は、制御信号D203として、バリアブルノード演算を指示する制御信号を、メッセージ計算部１９１に供給する。
【０１９３】
メッセージ計算部１９１は、メッセージメモリ１０４から供給される入力メッセージD201と受信データメモリ１０５から供給される受信データD101を用い、制御部１９２からの制御信号D203にしたがって、式（１）のバリアブルノード演算を行い、そのバリアブルノード演算の結果得られた出力メッセージ（バリアブルノードメッセージ）viを、メッセージD202として、メッセージメモリ１０４に供給する。
【０１９４】
そして、メッセージメモリ１０４は、以上のようにしてメッセージ計算部１９１から供給されるメッセージD202を記憶する。
【０１９５】
一方、チェックノード演算時には、メッセージメモリ１０４は、制御部１９２から供給される制御信号にしたがって、記憶しているバリアブルノードメッセージviを、入力メッセージD201として読み出し、メッセージ計算部１９１に供給する。
【０１９６】
さらに、チェックノード演算時には、制御部１９２は、制御信号D203として、チェックノード演算を指示する制御信号を、メッセージ計算部１９１に供給する。
【０１９７】
メッセージ計算部１９１は、メッセージメモリ１０４から供給される入力メッセージD201を用い、制御部１９２からの制御信号D203にしたがって、式（７）のチェックノード演算を行い、そのチェックノード演算にって求められた出力メッセージ（チェックノードメッセージ）ujを、メッセージD202として、メッセージメモリ１０４に供給する。
【０１９８】
そして、メッセージメモリ１０４は、以上のようにしてメッセージ計算部１９１から供給されるメッセージD202を記憶する。
【０１９９】
メッセージメモリ１０４が記憶したメッセージ計算部１９１からのチェックノードメッセージujとしてのメッセージD202は、次のバリアブルノード演算時に、メッセージD201として読み出され、メッセージ計算部１９１に供給される。
【０２００】
次に、図１８は、図１７のメッセージ計算部１９１の構成例を示している。
【０２０１】
メッセージ計算部１９１は、外部からメッセージ（データ）が供給（入力）される入力ポートとして、２つの入力ポートP101とP201を有し、外部にメッセージを供給（出力）するポートとして、１の出力ポートP202を有している。さらに、メッセージ計算部１９１は、外部から制御信号が供給（入力）される入力ポートとして、１つの入力ポートP203を有している。
【０２０２】
メッセージ計算部１９１は、入力ポートP201から入力されるメッセージ、さらには、必要に応じて、入力ポートP101から入力されるメッセージ（受信データ）を用い、入力ポートP203から入力される制御信号D203にしたがって、式（１）のバリアブルノード演算または式（７）のチェックノード演算を選択的に行い、その結果得られるメッセージを、出力ポートP202から出力する。
【０２０３】
即ち、入力ポートP101には、受信データメモリ１０５から読み出された受信データD101が供給される。また、入力ポートP201には、メッセージメモリ１０４から読み出されたメッセージD201（チェックノードメッセージujまたはバリアブルノードメッセージvi）が供給される。さらに、入力ポートP203には、制御部１９２からの制御信号D203が供給される。
【０２０４】
そして、入力ポートP101に供給された受信データD101は、演算器３１３に供給され、入力ポートP201に供給されたメッセージD201は、セレクタ３０１のv端子に供給される。さらに、入力ポートP201に供給されたメッセージD201のうちの最上位ビットを除く下位ビット、即ち、メッセージD201の絶対値は、値D303として、LUT３００に供給され、メッセージD201のうちの最上位ビット、即ち、メッセージD201の符号ビットは、値D304として、EXOR回路３０６とFIFOメモリ３２０に供給される。
【０２０５】
また、入力ポートP203に供給された制御信号D203は、セレクタ３０１および３１６に供給される。
【０２０６】
セレクタ３０１および３１６は、v端子とc端子とを有し、制御信号D203にしたがい、v端子またはc端子のうちのいずれかに供給される値を選択して、後段に出力する。即ち、セレクタ３０１および３１６は、制御信号D203がバリアブルノード演算を指示する制御信号である場合には、v端子に供給される値を選択して後段に出力し、制御信号D203がチェックノード演算を指示する制御信号である場合には、c端子に供給される値を選択して後段に出力する。
【０２０７】
その結果、メッセージ計算部１９１は、バリアブルノード演算時には、実質的に、図１９に示す構成となって、バリアブルノード演算を行い、チェックノード演算時には、実質的に、図２０に示す構成となって、チェックノード演算を行う。
【０２０８】
即ち、図１９は、バリアブルノード演算時のメッセージ計算部１９１の実質的な構成例を示している。
【０２０９】
なお、上述したように、バリアブルノード演算時には、セレクタ３０１および３１６はv端子を選択するが、図１９では、図１８に図示した構成のうちの、セレクタ３０１および３１６がv端子を選択することによってバリアブルノード演算時に（実質的に）機能しない部分（バリアブルノード演算に関係がない部分）の図示を省略してある。
【０２１０】
バリアブルノード演算時においては、入力ポートP101には、受信データメモリ１０５から１つずつ読み出された受信データD101が供給される。また、入力ポートP201には、メッセージメモリ１０４から１つずつ読み出された、検査行列の各行に対応するチェックノード（出力メッセージviを求めようとしているバリアブルノードに対応する列の、各行に対応するチェックノード）からのチェックノードメッセージujが、順次、メッセージD201として供給される。
【０２１１】
入力ポートP101に供給された受信データD101は、演算器３１３に供給される。
【０２１２】
また、入力ポートP201に供給されたメッセージD201（メッセージuj）は、セレクタ３０１のv端子に供給され、バリアブルノード演算時にはv端子を選択しているセレクタ３０１から、メッセージD306として、演算器３０２とFIFOメモリ３２０に供給される。
【０２１３】
演算器３０２は、セレクタ３０１からのメッセージD306（メッセージuj）とレジスタ３０３に格納されている値D307とを加算することにより、メッセージD306を積算し、その結果得られる積算値を、レジスタ３０３に再格納する。なお、検査行列の1列に亘る全ての枝からのメッセージD306が積算された場合、レジスタ３０３はリセットされる。
【０２１４】
検査行列の1列に亘るメッセージD306が１つずつ読み込まれ、レジスタ３０３に1列分のメッセージD306が積算された値が格納された場合、即ち、レジスタ３０３に、検査行列の１列に亘る全ての枝からのメッセージD306（メッセージuj）が積算された積算値（ｊ＝１からｄVまでのΣuj)が格納された場合、セレクタ３０４は、レジスタ３０３に格納されている値、即ち、検査行列の１列に亘る全ての枝からのメッセージD306（メッセージuj）が積算された積算値D307（ｊ＝１からｄVまでのΣuj)を選択し、レジスタ３０５に出力して格納させる。
【０２１５】
レジスタ３０５は、格納している値D307を、値D308として、セレクタ３０４と演算器３１２に供給する。レジスタ３０３に1列分のメッセージD306が積算された値が格納される直前までは、セレクタ３０４は、レジスタ３０５から供給された値D308を選択し、レジスタ３０５に出力し再格納させる。即ち、検査行列の１列に亘る全ての枝からのメッセージD306（メッセージuj）が積算されるまで、レジスタ３０５は、前回積算された値を、セレクタ３０４と演算器３１２に供給する。
【０２１６】
一方、FIFOメモリ３２０は、レジスタ３０５から新たな値D308（ｊ＝１からｄVまでのΣuj）が出力されるまでの間、セレクタ３０１が出力したチェックノードからのメッセージD306を遅延し、値D315として演算器３１２に供給する。演算器３１２は、レジスタ３０５から供給された値D308から、FIFOメモリ３２０から供給された値D315を減算する。即ち、演算器３１２は、検査行列の1列に亘る全ての枝からのメッセージD306（メッセージuj）の積算値D308（ｊ＝１からｄVまでのΣuj）から、求めたい枝からのメッセージD315（uj）を減算して、減算値D316（ｊ＝１からｄv−１までのΣuj）を求め、演算器３１３に供給する。
【０２１７】
演算器３１３は、入力ポートP101からの受信データD101と、演算器３１２からの減算値D316（ｊ＝１からｄv−１までのΣuj）とを加算し、その結果得られる加算値D317（バリアブルノードメッセージvi）を、セレクタ３１６のv端子に供給する。
【０２１８】
セレクタ３１６は、バリアブルノード演算時にはv端子を選択しており、そのv端子に供給される演算器３１３からの加算値D317を、メッセージD202（メッセージvi）として、出力ポートP202から出力する。
【０２１９】
以上のように、セレクタ３０１および３０４がv端子を選択しているメッセージ計算部１９１では、式（１）のバリアブルノード演算が行われ、その結果得られるメッセージ（バリアブルノードメッセージ）viが、出力ポートP202から出力される。
【０２２０】
図２０は、チェックノード演算時の図１８のメッセージ計算部１９１の実質的な構成例を示している。
【０２２１】
なお、上述したように、チェックノード演算時には、セレクタ３０１および３１６はc端子を選択するが、図２０では、図１８に図示した構成のうちの、セレクタ３０１および３１６がc端子を選択することによってチェックノード演算時に（実質的に）機能しない部分（チェックノード演算に関係がない部分）の図示を省略してある。
【０２２２】
チェックノード演算時においては、入力ポートP201には、メッセージメモリ１０４から１つずつ読み出された、検査行列の各列に対応するバリアブルノード（出力メッセージujを求めようとしているチェックノードに対応する行の、各列に対応するバリアブルノード）からのバリアブルノードメッセージviが、順次、メッセージD201として供給される。
【０２２３】
入力ポートP201に供給されたメッセージD201（メッセージuj）のうちの最上位ビットを除く下位ビット、つまり、メッセージD201の絶対値D303(|vi|)は、LUT３００に供給され、最上位ビット、つまりメッセージD201の符号ビットD304は、EXOR回路３０６とFIFOメモリ３２０にそれぞれ供給される。
【０２２４】
LUT３００は、そこに入力される値を引数xとして、式（７）のチェックノード演算における非線形関数φ(x)の演算結果を出力するLUTであり、絶対値D303(|vi|)を引数として、非線形関数φ(|vi|)の演算を行った演算結果D305（φ(|vi|)）を読み出し、セレクタ３０１のc端子に供給する。
【０２２５】
セレクタ３０１は、チェックノード演算時にはc端子を選択しており、そのc端子に供給されるLUT３００からの演算結果D305（φ(|vi|)）を、演算結果D306（φ(|vi|)）として、演算器３０２とFIFOメモリ３２０に供給する。
【０２２６】
演算器３０２は、演算結果D306（φ(|vi|)）とレジスタ３０３に格納されている値D307とを加算することにより、演算結果D306を積算し、その結果得られる積算値をレジスタ３０３に再格納する。なお、検査行列の1行に亘る全ての枝からのメッセージD201の絶対値D303(|vi|)に対する演算結果D306（φ(|vi|)）が積算された場合、レジスタ３０３はリセットされる。
【０２２７】
検査行列の1行に亘るメッセージD201が１つずつ読み込まれ、レジスタ３０３に1行分の演算結果D306が積算された積算値が格納された場合、セレクタ３０４は、レジスタ３０３に格納されている値、即ち、検査行列の１行に亘る全ての枝からのメッセージD201（メッセージvi）から求められたφ(|vi|)が積算された積算値D307（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）を選択し、レジスタ３０５に出力して格納させる。レジスタ３０５は、格納している積算値D307を、値D308として、セレクタ３０４と演算器３１２に供給する。
【０２２８】
レジスタ３０３に1行分の演算結果D306が積算された積算値が格納される直前までは、セレクタ３０４は、レジスタ３０５から供給された値D308を選択し、レジスタ３０５に出力して再格納させる。即ち、検査行列の１行に亘る全ての枝からのメッセージD201（メッセージvi）から求められたφ(|vi|)が積算されるまで、レジスタ３０５は、前回積算されたφ(|vi|)の積算値を、セレクタ３０４と演算器３１２に供給する。
【０２２９】
一方、FIFOメモリ３２０は、レジスタ３０５から新たな値D308（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）が出力されるまでの間、LUT３００が出力した演算結果D306（φ(|vi|)）を遅延し、値D315として演算器３１２に供給する。演算器３１２は、レジスタ３０５から供給された値D308から、FIFOメモリ３２０から供給された値D315を減算し、その減算結果を、減算値D316としてLUT３１４に供給する。即ち、演算器３１２は、検査行列の1行に亘る全ての枝からのメッセージD201（メッセージvi）から求められたφ(|vi|)の積算値（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）から、求めたい枝からのメッセージD201（メッセージvi）から求められたφ(|vi|)を減算して、その減算値（ｉ＝１からｉ＝ｄc−１までのΣφ(|vi|)）を減算値D316としてLUT３１４に供給する。
【０２３０】
LUT３１４は、そこに入力される値を引数xとして、式（７）のチェックノード演算における非線形関数φ(x)の逆関数φ-1(x)の演算結果を出力するLUTであり、演算器３１２からの減算値D316（ｉ＝１からｉ＝ｄc−１までのΣφ(|vi|)）を引数として、逆関数φ-1（Σφ(|vi|)）の演算を行った演算結果D318（φ-1(Σφ(|vi|)))を出力する。
【０２３１】
なお、上述したように、非線形関数φ(x)の演算結果と逆関数φ-1(x)の演算結果とは等しいので、LUT３００と３１４とは、同一構成のLUTとなっている。
【０２３２】
以上の処理と並行して、EXOR回路３０６は、レジスタ３０７に格納されている値D310と符号ビット（正負を表すビット）D304との排他的論理和を演算することにより、符号ビットどうしの乗算を行い、乗算結果D309を、レジスタ３０７に再格納する。なお、検査行列の1行に亘る全ての枝からのメッセージD201の符号ビットD304が乗算された場合、レジスタ３０７はリセットされる。
【０２３３】
検査行列の1行に亘る全ての枝からのメッセージD201の符号ビットD304が乗算された乗算結果D309（ｉ＝１からｄcまでのΠsign(vi)）がレジスタ３０７に格納された場合、セレクタ３０８は、レジスタ３０７に格納されている値、即ち、検査行列の１行に亘る全ての枝からのメッセージD201の符号ビットD304が乗算された値D310（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）を選択し、レジスタ３０９に出力して格納させる。レジスタ３０９は、格納している値D311を、セレクタ３０８とEXOR回路３１５に供給する。
【０２３４】
検査行列の1行に亘る全ての枝からのメッセージD201の符号ビットD304が乗算された乗算結果D309（ｉ＝１からｄcまでのΠsign(vi)）がレジスタ３０７に格納される直前までは、セレクタ３０８は、レジスタ３０９から供給された値D311を選択し、レジスタ３０９に出力して再格納させる。即ち、検査行列の１行に亘る全ての枝からのメッセージD201（メッセージvi）の符号ビットD304が乗算されるまで、レジスタ３０９は、前回格納した値を、セレクタ３０８とEXOR回路３１５に供給する。
【０２３５】
一方、FIFOメモリ３２０は、レジスタ３０９から新たな値D311（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）がEXOR回路３１５に供給されるまでの間、符号ビットD304を遅延し、１ビットの値D313としてEXOR回路３１５に供給する。EXOR回路３１５は、レジスタ３０９から供給された値D311と、FIFOメモリ３２０から供給された値D313との排他的論理和を演算することにより、値D311を、値D313で除算し、除算結果を除算値D319として出力する。即ち、EXOR回路３１５は、検査行列の１行に亘る全ての枝からのメッセージD201の符号ビットD304（sign(vi)）の乗算値（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）を、求めたい枝からのメッセージD201の符号ビットD304（sign(vi)）で除算して、その除算値（ｉ＝１からｉ＝ｄc−１までのΠsign(vi)）を除算値D319として出力する。
【０２３６】
そして、メッセージ計算部１９１では、LUT３１４から出力された演算結果D318を下位ビットとするとともに、EXOR回路３１５から出力された除算値D319を最上位ビット（符号ビット）とするビット列D320（チェックノードメッセージuj）が、セレクタ３１６のc端子に供給される。
【０２３７】
セレクタ３１６は、チェックノード演算時にはc端子を選択しており、そのc端子に供給されるビット列D320（メッセージuj）を、メッセージD202（メッセージvi）として、出力ポートP202から出力する。
【０２３８】
以上のように、セレクタ３０１および３０４がc端子を選択しているメッセージ計算部１９１では、式（７）のチェックノード演算が行われ、その結果得られるメッセージ（チェックノードメッセージ）ujが、出力ポートP202から出力される。
【０２３９】
なお、図示しないが、図１７の復号装置では、復号の最終段において、式（１）のバリアブルノード演算の代わりに、式（５）の演算が行われ、その演算結果が、最終的な復号結果として出力される。
【０２４０】
図１７の復号装置によれば、メッセージメモリ１０４と、メッセージ計算部１９１のFIFOメモリ３２０の容量さえ足りれば、様々な検査行列のLDPC符号を復号することができる。
【０２４１】
また、図１７の復号装置のメッセージ計算部１９１（図１８）では、図１９と図２０とを比較して分かるように、値の積算を行って積算値を出力する演算器３０２およびレジスタ３０３、積算値から、ある値を減算して減算値を出力するセレクタ３０４、レジスタ３０５、および演算器３１２、並びに値を遅延する遅延メモリとしてのFIFOメモリ３２０が、バリアブルノード演算とチェックノード演算とで共有されているので、例えば、図８の復号装置のように、独立のバリアブルノード計算器１０２とチェックノード計算器１０３とを有するメッセージ計算部１０１よりも回路規模を小さくすることができる。
【０２４２】
次に、図２１は、本発明を適用した復号装置の第２実施の形態の構成例を示すブロック図である。なお、図中、図１７の復号装置の場合と対応する部分については、同一の符号を付してあり、以下では、その説明は、適宜省略する。即ち、図２１の復号装置は、メッセージ計算部１９１に代えて、メッセージ計算部２０１が設けられているとともに、制御部１９２に代えて、制御部２０２が設けられている他は、図１７の復号装置と同様に構成されている。
【０２４３】
図２１の復号装置では、メッセージ計算部２０１が、図１７の復号装置のメッセージ計算部１９１と同様に、バリアブルノード演算を行う回路と、チェックノード演算を行う回路との一部を共有する構成となっている。さらに、図２１の復号装置は、バリアブルノード演算とチェックノード演算とを行うメッセージ計算部２０１が、遅延メモリ（図１８のメッセージ計算部１９１のFIFOメモリ３２０に相当するメモリ）を設けずに構成されている。
【０２４４】
図２１の復号装置では、メッセージメモリ１０４からメッセージ計算部２０１に、入力メッセージが１つずつ読み出され、メッセージ計算部２０１において、その入力メッセージを用いて、所望の枝に対応する出力メッセージが計算される。そして、その計算によって求められた出力メッセージが、メッセージメモリ１０４に格納されていく。図２１の復号装置では、以上の処理が繰り返し行われ、フルシリアルの繰り返し復号が行われる。
【０２４５】
即ち、受信データメモリ１０５には、送信されてきたLDPC符号を受信することにより得られる、符号の0（または1）らしさを表す対数尤度比である受信データ（LDPC符号）D100が供給され、受信データメモリ１０５は、その受信データD100を格納（記憶）する。
【０２４６】
バリアブルノード演算時には、受信データメモリ１０５は、制御部２０２から供給される制御信号にしたがって、記憶している受信データを読み出し、受信データD101として、メッセージ計算部２０１に供給する。
【０２４７】
また、バリアブルノード演算時には、メッセージメモリ１０４は、制御部２０２から供給される制御信号にしたがい、記憶している同一のメッセージを２回読み出して、１回目に読み出したメッセージをメッセージD201として、メッセージ計算部２０１に供給し、２回目に読み出したメッセージをメッセージDD201として、メッセージ計算部２０１に供給する。メッセージ計算部２０１は、メッセージメモリ１０４から供給されるメッセージD201とDD201、および受信データメモリ１０５から供給される受信データD101を用い、制御部２０２から供給される制御信号D203が表すバリアブルノード演算の指示にしたがって、式（１）のバリアブルノード演算を行い、そのバリアブルノード演算の結果得られたメッセージ（バリアブルノードメッセージ）viを、メッセージD202として、メッセージメモリ１０４に供給する。
【０２４８】
そして、メッセージメモリ１０４は、制御部２０２から供給される制御信号にしたがい、メッセージ計算部２０１から供給されるメッセージD202（バリアブルノードメッセージvi）を記憶する。
【０２４９】
一方、チェックノード演算時には、メッセージメモリ１０４は、制御部２０２から供給される制御信号にしたがって、記憶している同一のメッセージ（バリアブルノードメッセージvi）を２回読み出して、１回目に読み出したメッセージをメッセージD201として、メッセージ計算部２０１に供給し、２回目に読み出したメッセージをメッセージDD201として、メッセージ計算部２０１に供給する。
【０２５０】
メッセージ計算部２０１は、メッセージメモリ１０４から供給されるメッセージD201とDD201を用い、制御部２０２からの制御信号Ｄ203が表すチェックノード演算の指示にしたがって、式（７）のチェックノード演算を行い、そのチェックノード演算によって求められたメッセージ（チェックノードメッセージ）ujを、メッセージD202として、メッセージメモリ１０４に供給する。
【０２５１】
そして、メッセージメモリ１０４は、制御部２０２から供給される制御信号にしたがい、メッセージ計算部２０１から供給されるメッセージD202（チェックノードメッセージuj）を記憶する。
【０２５２】
メッセージメモリ１０４が記憶したメッセージ計算部２０１からのメッセージD202、即ち、チェックノードメッセージujは、次のバリアブルノード演算時に、メッセージD201およびDD201として読み出され、メッセージ計算部２０１に供給される。
【０２５３】
図２２は、図２１のメッセージ計算部２０１の構成例を示している。
【０２５４】
なお、図中、図１８のメッセージ計算部１９１と対応する部分については、同一の符号を付してあり、以下では、その説明は、適宜省略する。
【０２５５】
メッセージ計算部２０１は、データを遅延するための遅延メモリ（図１８のメッセージ計算部１９１に設けられているFIFOメモリ３２０）を設けずに構成されている。
【０２５６】
その代わり、メッセージ計算部２０１は、外部からメッセージ（データ）が供給（入力）される入力ポートとして、入力ポートP101およびP201の他に、入力ポートPD201を有しているとともに、LUT３１０およびセレクタ３１１を有している。
【０２５７】
入力ポートP101には、受信データメモリ１０５から読み出された受信データD101が供給（入力）される。また、入力ポートP201には、メッセージメモリ１０４から２回読み出される同一のメッセージD201およびDD201のうちの１回目に読み出されるメッセージ（以下、適宜、１回目のメッセージともいう）D201が供給（入力）され、入力ポートPD201には、２回目に読み出されるメッセージ（以下、適宜、２回目のメッセージともいう）DD201が供給される。
【０２５８】
メッセージ計算部２０１は、入力ポートP201から入力される１回目のメッセージD201と、入力ポートPD201から入力される２回目のメッセージDD201、さらには、必要に応じて、入力ポートP101から入力されるメッセージ（受信データ）を用い、入力ポートP203から入力される制御信号D203にしたがって、式（１）のバリアブルノード演算または式（７）のチェックノード演算を行い、その結果得られるメッセージを、出力ポートP202から出力する。
【０２５９】
即ち、入力ポートP101に供給された受信データD101は、演算器３１３に供給され、入力ポートP201に供給された１回目のメッセージD201は、セレクタ３０１のv端子に供給される。
【０２６０】
さらに、入力ポートP201に供給された１回目のメッセージD201のうちの最上位ビットを除く下位ビット、即ち、メッセージD201の絶対値は、値D303として、LUT３００に供給され、１回目のメッセージD201のうちの最上位ビット、即ち、メッセージD201の符号ビットは、値D304として、EXOR回路３０６に供給される。
【０２６１】
また、入力ポートPD201に供給された２回目のメッセージDD201は、セレクタ３１１のv端子に供給される。さらに、入力ポートPD201に供給された２回目のメッセージDD201のうちの最上位ビットを除く下位ビット、即ち、メッセージDD201の絶対値は、値D312として、LUT３１０に供給され、２回目のメッセージDD201のうちの最上位ビット、即ち、メッセージDD201の符号ビットは、値D313として、EXOR回路３０６に供給される。
【０２６２】
また、入力ポートP203に供給された制御信号D203は、セレクタ３０１，３１１、および３１６に供給される。
【０２６３】
セレクタ３０１，３１１、および３１６は、v端子とc端子とを有し、制御信号D203にしたがい、v端子またはc端子のうちのいずれかに供給される値を選択して、後段に出力する。即ち、セレクタ３０１，３１１、および３１６は、制御信号D203がバリアブルノード演算を指示する制御信号である場合には、v端子に供給される値を選択して後段に出力し、制御信号D203がチェックノード演算を指示する制御信号である場合には、c端子に供給される値を選択して後段に出力する。
【０２６４】
その結果、図２２のメッセージ計算部２０１では、制御信号D203がバリアブルノード演算を指示しているときには、バリアブルノード演算が行われ、制御信号D203がチェックノード演算を指示しているときには、チェックノード演算が行われる。
【０２６５】
ここで、図２３を参照して、図２２のメッセージ計算部２０１で行われるバリアブルノード演算とチェックノード演算について説明する。
【０２６６】
図２３左側は、式（１）のバリアブルノード演算を行うバリアブルノードと、式（７）のチェックノード演算を行うチェックノードとを模式的に示している。
【０２６７】
バリアブルノードでは、計算しようとしている枝（バリアブルノードに接続している枝のうちのi番目の枝）に対応するメッセージviが、バリアブルノードに繋がっている残りの枝からのメッセージu1,u2,・・・を、式（１）に示したように加算することによって求められる。
【０２６８】
また、チェックノードでは、計算しようとしている枝（チェックノードに接続している枝のうちのj番目の枝）に対応するメッセージujが、式（７）に示したように、チェックノードに繋がっている残りの枝からのメッセージv1,v2,・・・を引数xとする非線形関数φ(x)の演算結果を積算し、その結果得られる積算値を引数xとする逆関数φ-1(x)を演算することによって求められる。
【０２６９】
いま、ノードに入力されるデータ（入力前のデータ）を入力データというとともに、ノードから出力されるデータ（出力前のデータ）を出力データということとすると、図２３左側のバリアブルノードおよびチェックノードでの演算は、図２３右側に示す演算と等価である。
【０２７０】
即ち、図２３右側では、バリアブルノードにおいて、図２３左側のバリアブルノードと同一の演算によって、メッセージviが求められている。また、図２３右側では、チェックノードにおいて非線形関数φ(x)の演算を行うのではなく、チェックノードに入力される入力データ（入力前のメッセージv1,v2,・・・）に、非線形関数φ(x)の演算を施してから、その演算結果が、チェックノードに入力され、チェックノードにおいて、非線形関数φ(x)の演算結果が積算されている。さらに、図２３右側では、チェックノードにおいて逆関数φ-1(x)の演算を行うのではなく、チェックノードから出力された出力データ（逆関数φ-1(x)の演算が施される前の、非線形関数φ(x)の演算結果の積算値）に、逆関数φ-1(x)の演算が施され、これにより、メッセージujが求められている。
【０２７１】
図２２のメッセージ計算部２０１では、図２３右側に示したようにメッセージviとujを求めるバリアブルノード演算とチェックノード演算が行われる。
【０２７２】
ここで、図２３右側のバリアブルノードについては、バリアブルノードに入力される入力データと、バリアブルノードから出力された出力データのいずれに対しても、非線形関数φ(x)および逆関数φ-1(x)の演算は施されない。一方、チェックノードについては、入力データに、非線形関数φ(x)の演算が施され、出力データに、逆関数φ-1(x)の演算が施される。
【０２７３】
このため、バリアブルノード演算とチェックノード演算の両方を行う図２２のメッセージ計算部２０１には、非線形関数φ(x)の演算を行う（演算結果を出力する）LUT３００および３１０と、逆関数φ-1(x)の演算を行う（演算結果を出力する）LUT３１４とが設けられている。
【０２７４】
そして、メッセージ計算部２０１は、バリアブルノード演算時には、実質的に、バリアブルノードに対する入力データおよび出力データを、LUT３００，３１０、および３１４をバイパスさせる構成（後述する図２４の構成）となって、図２３右側でバリアブルノードについて説明した演算を行う。
【０２７５】
また、メッセージ計算部２０１は、チェックノード演算時には、チェックノードに入力される入力データを、LUT３００または３１０を経由させるとともに、チェックノードから出力された出力データを、LUT３１４を経由させる構成（後述する図２５の構成）となって、図２３右側でチェックノードについて説明した演算を行う。
【０２７６】
図２４は、図２３右側に示したバリアブルノード演算時の図２２のメッセージ計算部２０１の実質的な構成例を示している。
【０２７７】
なお、上述したように、バリアブルノード演算時には、セレクタ３０１，３１１、および３１６はv端子を選択するが、図２４では、図２２に図示した構成のうちの、セレクタ３０１，３１１、および３１６がv端子を選択することによってバリアブルノード演算時に機能しない部分（バリアブルノード演算に関係がない部分）の図示を省略してある。
【０２７８】
メッセージ計算部２０１は、入力ポートP101,P201,PD201それぞれから入力されるメッセージを用いて、式（１）のバリアブルノード演算を行い、その結果得られるメッセージD202を、出力ポートP202から出力する。
【０２７９】
即ち、入力ポートP101には、受信データメモリ１０５から読み出された受信データD101が供給される。また、入力ポートP201には、メッセージメモリ１０４から１つずつ読み出された、検査行列の各行に対応するチェックノードからの１回目のメッセージD201（チェックノードメッセージuj）が供給される。
【０２８０】
入力ポートP101に供給された受信データD101は、演算器３１３に供給される。
【０２８１】
また、入力ポートP201に供給されたメッセージD201（メッセージuj）は、セレクタ３０１のv端子に供給され、バリアブルノード演算時にはv端子を選択しているセレクタ３０１から、メッセージD306として、演算器３０２に供給される。
【０２８２】
そして、演算器３０２、レジスタ３０３、セレクタ３０４、およびレジスタ３０５では、図１９で説明したメッセージ計算部１９１と同様の処理が行われる。
【０２８３】
即ち、演算器３０２は、セレクタ３０１からのメッセージD306（メッセージuj）とレジスタ３０３に格納されている値D307とを加算することにより、メッセージD306を積算し、その結果得られる積算値を、レジスタ３０３に再格納する。なお、検査行列の1列に亘る全ての枝からのメッセージD306が積算された場合、レジスタ３０３はリセットされる。
【０２８４】
検査行列の1列に亘るメッセージD306が１つずつ読み込まれ、レジスタ３０３に1列分のメッセージD306が積算された値が格納された場合、即ち、レジスタ３０３に、検査行列の１列に亘る全ての枝からのメッセージD306（メッセージuj）が積算された積算値（ｊ＝１からｄVまでのΣuj)が格納された場合、セレクタ３０４は、レジスタ３０３に格納されている値、即ち、検査行列の１列に亘る全ての枝からのメッセージD306（メッセージuj）が積算された積算値D307（ｊ＝１からｄVまでのΣuj)を選択し、レジスタ３０５に出力して格納させる。
【０２８５】
レジスタ３０５は、格納している値D307を、値D308として、セレクタ３０４と演算器３１２に供給する。レジスタ３０３に1列分のメッセージD306が積算された値が格納される直前までは、セレクタ３０４は、レジスタ３０５から供給された値D308を選択し、レジスタ３０５に出力し再格納させる。即ち、検査行列の１列に亘る全ての枝からのメッセージD306（メッセージuj）が積算されるまで、レジスタ３０５は、前回積算された値を、セレクタ３０４と演算器３１２に供給する。
【０２８６】
一方、レジスタ３０５から新たな値D308（ｊ＝１からｄVまでのΣuj)の出力が開始されると、即ち、レジスタ３０３に1列分のメッセージD201が積算された積算値（ｊ＝１からｄVまでのΣuj)が格納された直後、メッセージ計算部２０１においては、メッセージD201（メッセージuj）と同一のメッセージDD201、即ち、メッセージメモリ１０４からの２回目のメッセージujが、入力ポートPD201から１つずつ入力され、そのメッセージDD201が、セレクタ３１１のv端子に供給される。
【０２８７】
セレクタ３１１は、バリアブルノード演算時には、v端子を選択しており、そのv端子に供給されるメッセージ（２回目のメッセージuj）DD201を、演算器３１２に供給する。
【０２８８】
演算器３１２は、レジスタ３０５から供給された積算値D308から、入力ポートPD201からセレクタ３１１を介して供給されたメッセージDD201を減算する。即ち、演算器３１２では、検査行列の1列に亘る全ての枝からのメッセージD201（メッセージuj）の積算値D308（ｊ＝１からｄvまでのΣuj）から、求めたい枝からのメッセージuj（ｊ＝ｄvのuj）としてのメッセージDD201を減算して、減算値（ｊ＝１からｄv−１までのΣuj）を求め、演算器３１３に供給する。
【０２８９】
演算器３１３は、入力ポートP101からの受信データD101と、演算器３１２からの減算値（ｊ＝１からｄv−１までのΣuj）とを加算し、その結果得られる加算値D317（バリアブルノードメッセージvi）を、セレクタ３１６のv端子に供給する。
【０２９０】
セレクタ３１６は、バリアブルノード演算時にはv端子を選択しており、そのv端子に供給される演算器３１３からの加算値D317を、メッセージD202（メッセージvi）として、出力ポートP202から出力する。
【０２９１】
以上のように、セレクタ３０１および３０４がv端子を選択しているメッセージ計算部２０１では、式（１）のバリアブルノード演算が行われ、その結果得られるメッセージ（バリアブルノードメッセージ）viが、出力ポートP202から出力される。
【０２９２】
図２５は、図２３右側に示したチェックノード演算時の図２２のメッセージ計算部２０１の実質的な構成例を示している。
【０２９３】
なお、上述したように、チェックノード演算時には、セレクタ３０１，３１１、および３１６はc端子を選択するが、図２５では、図２２に図示した構成のうちの、セレクタ３０１，３１１、および３１６がc端子を選択することによってチェックノード演算時に機能しない部分（チェックノード演算に関係がない部分）の図示を省略してある。
【０２９４】
チェックノード演算時においては、入力ポートP201には、メッセージメモリ１０４から１つずつ読み出された、検査行列の各列に対応するバリアブルノードからのバリアブルノードメッセージviが、順次、メッセージD201として供給される。
【０２９５】
そして、LUT３００、セレクタ３０１、演算器３０２、レジスタ３０３、セレクタ３０４、レジスタ３０５、EXOR回路３０６、レジスタ３０７、セレクタ３０８、レジスタ３０９、演算器３１２、LUT３１４、およびEXOR回路３１５において、図２０で説明したメッセージ計算部１９１と同様の処理が行われる。
【０２９６】
即ち、入力ポートP201に供給されたメッセージD201（メッセージuj）のうちの最上位ビットを除く下位ビット、つまり、メッセージD201の絶対値D303(|vi|)は、LUT３００に供給され、最上位ビット、つまりメッセージD201の符号ビットD304は、EXOR回路３０６に供給される。
【０２９７】
LUT３００は、絶対値D303(|vi|)を引数として、非線形関数φ(|vi|)の演算を行った演算結果D305（φ(|vi|)）を読み出し、セレクタ３０１のc端子に供給する。
【０２９８】
セレクタ３０１は、チェックノード演算時にはc端子を選択しており、そのc端子に供給されるLUT３００からの演算結果D305（φ(|vi|)）を、演算結果D306（φ(|vi|)）として、演算器３０２に供給する。
【０２９９】
演算器３０２は、演算結果D306（φ(|vi|)）とレジスタ３０３に格納されている値D307とを加算することにより、演算結果D306を積算し、その結果得られる積算値をレジスタ３０３に再格納する。なお、検査行列の1行に亘る全ての枝からのメッセージD201の絶対値D303(|vi|)に対する演算結果D306（φ(|vi|)）が積算された場合、レジスタ３０３はリセットされる。
【０３００】
検査行列の1行に亘るメッセージD201が１つずつ読み込まれ、レジスタ３０３に1行分の演算結果D306が積算された積算値が格納された場合、セレクタ３０４は、レジスタ３０３に格納されている値、即ち、検査行列の１行に亘る全ての枝からのメッセージD201（メッセージvi）から求められたφ(|vi|)が積算された積算値D307（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）を選択し、レジスタ３０５に出力して格納させる。レジスタ３０５は、格納している積算値D307を、値D308として、セレクタ３０４と演算器３１２に供給する。
【０３０１】
レジスタ３０３に1行分の演算結果D306が積算された積算値が格納される直前までは、セレクタ３０４は、レジスタ３０５から供給された値D308を選択し、レジスタ３０５に出力して再格納させる。即ち、検査行列の１行に亘る全ての枝からのメッセージD201（メッセージvi）から求められたφ(|vi|)が積算されるまで、レジスタ３０５は、前回積算されたφ(|vi|)の積算値を、セレクタ３０４と演算器３１２に供給する。
【０３０２】
一方、レジスタ３０５から新たな値D308（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）の出力が開始されると、即ち、レジスタ３０５に1行分の演算結果D306が積算された積算値（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）が格納された直後、メッセージ計算部２０１において、メッセージD201（メッセージvi）と同一のメッセージDD201、即ち、メッセージメモリ１０４からの２回目のメッセージviが、入力ポートPD201から１つずつ入力され、そのメッセージDD201のうちのその最上位ビットを除く下位ビット、つまり、メッセージDD201の絶対値D312(|vi|)が、LUT３１０に供給されるとともに、最上位ビット、つまりメッセージDD201の符号ビットD313が、EXOR回路３１５に供給される。
【０３０３】
LUT３１０は、LUT３００と同様のLUTで、メッセージDD201の絶対値D312(|vi|)を引数として、非線形関数φ(|vi|)の演算を行った演算結果D314（φ(|vi|)）を読み出し、セレクタ３１１のc端子に供給する。
【０３０４】
セレクタ３１１は、チェックノード演算時にはc端子を選択しており、そのc端子に供給されるLUT３１０からの演算結果D314（φ(|vi|)）を、演算結果D315（φ(|vi|)）として、演算器３１２に供給する。
【０３０５】
演算器３１２は、レジスタ３０５から供給された値D308から、セレクタ３１１から供給された値D315を減算し、その減算結果を、減算値D316としてLUT３１４に供給する。即ち、演算器３１２は、検査行列の1行に亘る全ての枝からのメッセージD201（メッセージvi）から求められたφ(|vi|)の積算値D308（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）から、求めたい枝からのメッセージDD201（メッセージvi）から求められたφ(|vi|)の値D315を減算して、その減算値（ｉ＝１からｉ＝ｄc−１までのΣφ(|vi|)）を減算値D316としてLUT３１４に供給する。
【０３０６】
LUT３１４は、演算器３１２からの減算値D316（ｉ＝１からｉ＝ｄc−１までのΣφ(|vi|)）を引数として、逆関数φ-1（Σφ(|vi|)）の演算を行った演算結果D318（φ-1(Σφ(|vi|)))を出力する。
【０３０７】
以上の処理と並行して、EXOR回路３０６は、レジスタ３０７に格納されている値D310と符号ビット（正負を表すビット）D304との排他的論理和を演算することにより、符号ビットどうしの乗算を行い、乗算結果D309を、レジスタ３０７に再格納する。なお、検査行列の1行に亘る全ての枝からのメッセージD201の符号ビットD304が乗算された場合、レジスタ３０７はリセットされる。
【０３０８】
検査行列の1行に亘る全ての枝からのメッセージD201の符号ビットD304が乗算された乗算結果D309（ｉ＝１からｄcまでのΠsign(vi)）がレジスタ３０７に格納された場合、セレクタ３０８は、レジスタ３０７に格納されている値、即ち、検査行列の１行に亘る全ての枝からのメッセージD201の符号ビットD304が乗算された値D310（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）を選択し、レジスタ３０９に出力して格納させる。レジスタ３０９は、格納している値D311を、セレクタ３０８とEXOR回路３１５に供給する。
【０３０９】
検査行列の1行に亘る全ての枝からのメッセージD201の符号ビットD304が乗算された乗算結果D309（ｉ＝１からｄcまでのΠsign(vi)）がレジスタ３０７に格納される直前までは、セレクタ３０８は、レジスタ３０９から供給された値D311を選択し、レジスタ３０９に出力して再格納させる。即ち、検査行列の１行に亘る全ての枝からのメッセージD201（メッセージvi）の符号ビットD304が乗算されるまで、レジスタ３０９は、前回格納した値を、セレクタ３０８とEXOR回路３１５に供給する。
【０３１０】
一方、レジスタ３０９から新たな値D311（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）がEXOR回路３１５に供給されたとき、即ち、レジスタ３０７に１行に亘る全ての枝からのメッセージD201の符号ビットD304が乗算された値D310（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）が格納されたとき、レジスタ３０５には、上述したように、1行分の演算結果D306が積算された積算値（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）が格納される。
【０３１１】
レジスタ３０５に1行分の演算結果D306が積算された積算値（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）が格納されると、上述したように、メッセージ計算部２０１において、メッセージD201（メッセージvi）と同一のメッセージDD201、即ち、メッセージメモリ１０４からの２回目のメッセージviが、入力ポートPD201から１つずつ入力され、そのメッセージDD201のうちのその最上位ビットを除く下位ビット、つまり、メッセージDD201の絶対値(|vi|)が、LUT３１０に供給されるとともに、最上位ビット、つまりメッセージDD201の符号ビットD313が、EXOR回路３１５に供給される。
【０３１２】
EXOR回路３１５は、レジスタ３０９から供給された値D311と、入力ポートPD201からのメッセージDD201の符号ビットとの排他的論理和を演算することにより、値D311を、メッセージDD201の符号ビットで除算し、除算結果を除算値D319として出力する。即ち、EXOR回路３１５は、検査行列の１行に亘る全ての枝からのメッセージD201の符号ビットD304の乗算値（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）を、求めたい枝からのメッセージviとしてのメッセージDD201の符号ビットD304（ｉ＝ｄcのsign(vi)）で除算して、その除算値（ｉ＝１からｉ＝ｄc−１までのΠsign(vi)）を除算値D319として出力する。
【０３１３】
そして、メッセージ計算部２０１では、LUT３１４から出力された演算結果D318を下位ビットとするとともに、EXOR回路３１５から出力された除算値D319を最上位ビット（符号ビット）とするビット列D320（メッセージuj）が、セレクタ３１６のc端子に供給される。
【０３１４】
セレクタ３１６は、チェックノード演算時にはc端子を選択しており、そのc端子に供給されるビット列D320（メッセージuj）を、メッセージD202として、出力ポートP202から出力する。
【０３１５】
以上のように、セレクタ３０１，３１１、および３０４がc端子を選択しているメッセージ計算部２０１では、式（７）のチェックノード演算が行われ、その結果得られるメッセージ（チェックノードメッセージ）ujが、出力ポートP202から出力される。
【０３１６】
なお、図示しないが、図２１の復号装置では、復号の最終段において、式（１）のバリアブルノード演算の代わりに、式（５）の演算が行われ、その演算結果が、最終的な復号結果として出力される。
【０３１７】
また、図２１の復号装置において、制御部２０２は、メッセージメモリ１０４に対するメッセージ（データ）の読み書き制御として、図１５のフローチャートで説明したように、図１２の復号装置の制御部１７４と同様の読み書き制御を行う。
【０３１８】
また、図２１の復号装置のメッセージメモリ１０４に対するメッセージの読み書きのタイミングも、図１２の復号装置について説明した図１６の場合と同様であり、図２１の復号装置についても、多少の高速動作が必要となるが、遅延メモリを設ける必要がない分、装置規模を低減することができる。さらに、図２１の復号装置では、メッセージ計算部２０１において、バリアブルノードの演算を行う回路と、チェックノードの演算を行う回路との一部（演算器３０２、レジスタ３０３、セレクタ３０４、レジスタ３０５、および演算器３１２）が共有化されているので、その共有化の分だけ、図１２の復号装置よりも規模を削減することができる。
【０３１９】
次に、図２６は、本発明を適用した復号装置の第３実施の形態の構成例を示すブロック図である。なお、図中、図２１の復号装置の場合と対応する部分については、同一の符号を付してあり、以下では、その説明は、適宜省略する。即ち、図２６の復号装置は、メッセージ計算部２０１に代えて、メッセージ計算部２１１が設けられているとともに、制御部２０２に代えて、制御部２１２が設けられている他は、図２１の復号装置と同様に構成されている。
【０３２０】
図２６の復号装置では、メッセージ計算部２１１が、バリアブルノード演算を行う回路と、チェックノード演算を行う回路との一部を共有する構成となっており、さらに、遅延メモリを設けずに構成されている。
【０３２１】
図２６の復号装置では、メッセージメモリ１０４に記憶されているメッセージが１つずつ読み出され、メッセージ計算部２１１に供給される。メッセージ計算部２１１は、メッセージメモリ１０４からのメッセージを用いて演算が行われ、その演算によって求められたメッセージが、メッセージメモリ１０４に格納される。図２６の復号装置では、以上の処理が繰り返し行われ、フルシリアルの繰り返し復号が行われる。
【０３２２】
即ち、受信データメモリ１０５には、送信されてきたLDPC符号を受信することにより得られる、符号の0（または1）らしさを表す対数尤度比である受信データ（LDPC符号）D100が供給され、受信データメモリ１０５は、その受信データD100を記憶する。
【０３２３】
バリアブルノード演算時には、受信データメモリ１０５は、制御部２１２から供給される制御信号にしたがって、記憶している受信データを読み出し、受信データD101として、メッセージ計算部２１１に供給する。
【０３２４】
また、バリアブルノード演算時には、メッセージメモリ１０４は、制御部２１２から供給される制御信号にしたがい、記憶している同一のメッセージを２回読み出して、１回目に読み出したメッセージをメッセージD601として、メッセージ計算部２１１に供給し、２回目に読み出したメッセージをメッセージDD601として、メッセージ計算部２１１に供給する。さらに、制御部２１２が、バリアブルノード演算を指示する制御信号D603を、メッセージ計算部２１１に供給する。メッセージ計算部２１１は、メッセージメモリ１０４から供給されるメッセージD601とDD601、および受信データメモリ１０５から供給される受信データD101を用い、制御部２１２から供給される制御信号D603にしたがって、バリアブルノード演算を行い、そのバリアブルノード演算の結果得られたメッセージを、メッセージD622として、メッセージメモリ１０４に供給する。
【０３２５】
そして、メッセージメモリ１０４は、制御部２１２から供給される制御信号にしたがい、メッセージ計算部２１１から供給されるメッセージD622を記憶する。
【０３２６】
一方、チェックノード演算時には、メッセージメモリ１０４は、制御部２１２から供給される制御信号にしたがって、記憶している同一のメッセージを２回読み出して、１回目に読み出したメッセージをメッセージD601として、メッセージ計算部２１１に供給し、２回目に読み出したメッセージをメッセージDD601として、メッセージ計算部２１１に供給する。さらに、制御部２１２が、チェックノード演算を指示する制御信号D603を、メッセージ計算部２１１に供給する。
【０３２７】
メッセージ計算部２１１は、メッセージメモリ１０４から供給されるメッセージD601とDD601を用い、制御部２１２からの制御信号D603にしたがって、チェックノード演算を行い、そのチェックノード演算によって求められたメッセージを、メッセージD622として、メッセージメモリ１０４に供給する。
【０３２８】
そして、メッセージメモリ１０４は、制御部２１２から供給される制御信号にしたがい、メッセージ計算部２１１から供給されるメッセージD622を記憶する。
【０３２９】
ここで、図２６のメッセージ計算部２１１で行われる演算について説明する。
【０３３０】
いま、チェックノードに接続している枝のうちのj番目の枝から出力されるメッセージ（データ）として、式u'j=φ(|uj|)×sign(uj)で表されるメッセージu'jを導入すると、式（１）と式（７）は、それぞれ、式（９）と式（１０）に書き直すことができる。
【０３３１】
【数９】
0004807063.tif 000010
・・・（９）
【０３３２】
【数１０】
0004807063.tif 000011
・・・（１０）
【０３３３】
ここで、式u'j=φ(|uj|)×sign(uj)を、メッセージujについて書き直すと、式uj=φ-1(|u'j|)×sign(u'j)となる。この式uj=φ-1(|u'j|)×sign(u'j)を、バリアブルノード演算の式（１）に代入することにより、新たなバリアブルノード演算の式としての式（９）を得ることができる。
【０３３４】
また、式u'j=φ(|uj|)×sign(uj)に、チェックノード演算の式（７）を代入することにより、新たなチェックノード演算の式としての式（１０）を得ることができる。
【０３３５】
式（９）のバリアブルノード演算では、入力データ（メッセージ）u'jの絶対値|u'j|を引数とする逆関数φ-1(|u'j|)の演算が行われ、式（１０）のチェックノード演算では、入力データviの絶対値|vi|を引数とする非線形関数φ(|vi|)の演算が行われる。ここで、非線形関数φ(x)とその逆関数φ-1(x)とは、x＞0において等しい。従って、式（９）および式（１０）のいずれでも、入力データxの絶対値|x|を引数として、関数φ(x)の演算が行われる。
【０３３６】
そして、式（９）では、関数φ(x)の演算結果（φ-1(|u'j|)の演算結果）に入力データu'jの符号（sign(u'j)）を考慮した値（φ-1(|u'j|)×sign(u'j)）を積算し、さらに、受信データu0iを加算して、メッセージviが求められる。
【０３３７】
また、式（１０）では、関数φ(x)の演算結果（φ(|uj|)の演算結果）を積算し、それとは別に、入力データviの符号ビットの相乗積（Πsign(vi)）を求め、関数φ(x)の演算結果の積算値と、符号ビットの相乗積とを乗算して、メッセージu'jが求められる。
【０３３８】
図２６のメッセージ計算部２１１では、式（９）のバリアブルノード演算と、式（１０）のチェックノード演算とが行われる。
【０３３９】
図２７は、図２６のメッセージ計算部２１１の構成例を示している。
【０３４０】
メッセージ計算部２１１は、図２２のメッセージ計算部２０１と同様に、遅延メモリを設けずに構成されている。また、メッセージ計算部２１１には、入力ポートP101,P601,PD601,P603と、出力ポートP622が設けられている。
【０３４１】
入力ポートP101には、受信データメモリ１０５から読み出された受信データD101が供給（入力）される。入力ポートP601には、メッセージメモリ１０４から２回読み出される同一のメッセージD601およびDD601のうちの１回目に読み出されるメッセージ（１回目のメッセージ）D601が供給（入力）され、入力ポートPD601には、２回目に読み出されるメッセージ（２回目のメッセージ）DD601が供給される。また、入力ポートP603には、制御部２１２（図２６）からの制御信号D603が供給される。
【０３４２】
メッセージ計算部２１１は、入力ポートP601から入力される１回目のメッセージD601と、入力ポートPD601から入力される２回目のメッセージDD601、さらには、必要に応じて、入力ポートP101から入力されるメッセージ（受信データ）を用い、入力ポートP603から入力される制御信号D603にしたがって、式（９）のバリアブルノード演算または式（１０）のチェックノード演算を行い、その結果得られるメッセージD622を、出力ポートP622から出力する。
【０３４３】
ここで、図２８を参照して、図２７のメッセージ計算部２１１で行われるバリアブルノード演算とチェックノード演算について説明する。
【０３４４】
図２８左側は、式（１）のバリアブルノード演算を行うバリアブルノードと、式（７）のチェックノード演算を行うチェックノードとを模式的に示しており、図２３右側と同一の図である。
【０３４５】
図２８左側では、図２３右側で説明したように、チェックノードに入力される入力データに、非線形関数φ(x)の演算を施してから、その演算結果が、チェックノードに入力され、チェックノードにおいて、非線形関数φ(x)の演算結果が積算されている。さらに、チェックノードから出力された出力データ（逆関数φ-1(x)の演算が施される前の、非線形関数φ(x)の演算結果の積算値）に、逆関数φ-1(x)の演算が施され、これにより、メッセージujが求められている。
【０３４６】
このメッセージujは、入力データとして、バリアブルノードに入力され、バリアブルノード演算に用いられる。
【０３４７】
従って、図２８左側に示したように、チェックノードから出力された出力データxに、逆関数φ-1(x)の演算を施す代わりに、図２８右側に示すように、バリアブルノードに入力される入力データxに、逆関数φ-1(x)の演算を施しても、バリアブルノード演算とチェックノード演算を行うことができる。
【０３４８】
即ち、図２８右側では、式（９）で説明したように、バリアブルノードに入力される入力データに、逆関数φ-1(x)の演算が施され、バリアブルノードにおいて、その逆関数φ-1(x)の演算結果を積算することにより、メッセージviが求められている。また、図２８右側では、式（１０）で説明したように、チェックノードに入力される入力データに、非線形関数φ(x)の演算が施され、チェックノードにおいて、その非線形関数φ(x)の演算結果が積算されている。さらに、図２８右側では、チェックノードにおいて、非線形関数φ(x)の演算結果を積算して得られる積算値が、（逆関数φ-1(x)の演算が施されずに）そのまま出力データu'jとして出力されている。
【０３４９】
図２７のメッセージ計算部２１１では、図２８右側に示したようにメッセージviとu'jを求める式（９）のバリアブルノード演算と式（１０）のチェックノード演算が行われる。
【０３５０】
このように、メッセージ計算部２１１は、図２８右側に示したメッセージviとu'jを求める式（９）のバリアブルノード演算と式（１０）のチェックノード演算の両方を行うため、メッセージ計算部２１１（図２７）には、チェックノードに入力される入力データxに対して、逆関数φ-1(x)と同一の演算結果が得られる非線形関数φ(x)の演算結果を出力するとともに、バリアブルノードに入力される入力データxに対して、逆関数φ-1(x)の演算結果を出力するLUT６００（およびLUT６１０）が設けられている。
【０３５１】
そして、メッセージ計算部２１１は、入力ポートP603に供給された制御信号D603にしたがって、その実質的な構成を変えて、式（９）のバリアブルノード演算と式（１０）のチェックノード演算を選択的に行う。
【０３５２】
即ち、メッセージ計算部２１１（図２７）は、セレクタ６０１，６１１、および６１５を有しており、入力ポートP603に供給された制御信号D603は、セレクタ６０１，６１１、および６１５に供給される。
【０３５３】
セレクタ６０１，６１１、および６１５は、v端子とc端子とを有し、制御信号D603にしたがい、v端子またはc端子のうちのいずれかに供給される値を選択して、後段に出力する。即ち、セレクタ６０１，６１１、および６１５は、制御信号D603がバリアブルノード演算を指示する制御信号である場合には、v端子に供給される値を選択して後段に出力し、制御信号D603がチェックノード演算を指示する制御信号である場合には、c端子に供給される値を選択して後段に出力する。
【０３５４】
その結果、図２７のメッセージ計算部２１１では、制御信号D603がバリアブルノード演算を指示しているときには、バリアブルノード演算が行われ、制御信号D603がチェックノード演算を指示しているときには、チェックノード演算が行われる。
【０３５５】
即ち、図２９は、図２８右側に示したバリアブルノード演算時の図２７のメッセージ計算部２１１の実質的な構成例を示している。
【０３５６】
なお、上述したように、バリアブルノード演算時には、セレクタ６０１，６１１、および６１５はv端子を選択するが、図２９では、図２７に図示した構成のうちの、セレクタ６０１，６１１、および６１５がv端子を選択することによってバリアブルノード演算時に機能しない部分（バリアブルノード演算に関係がない部分）の図示を省略してある。
【０３５７】
メッセージ計算部２１１は、入力ポートP101,P601,PD601それぞれから入力されるメッセージを用いて、式（９）のバリアブルノード演算を行い、その結果得られるメッセージD622を、出力ポートP622から出力する。
【０３５８】
即ち、入力ポートP101には、受信データメモリ１０５から読み出された受信データD101が供給される。また、入力ポートP601には、メッセージメモリ１０４から１つずつ読み出された、検査行列の各行に対応するチェックノードからの１回目のメッセージD601（メッセージu'j）が供給される。
【０３５９】
入力ポートP101に供給された受信データD101は、演算器６１３に供給される。
【０３６０】
また、入力ポートP601に供給されたメッセージD601（メッセージu'j）のうちの最上位ビットを除く下位ビット、つまり、メッセージD601の絶対値D603(|u'j|)は、LUT６００に供給される。
【０３６１】
LUT６００は、絶対値D603(|u'j|)を引数として、逆関数φ(|u'j|)の演算を行った演算結果D605（φ-1(|u'j|)）を読み出して出力する。LUT６００が出力する演算結果D605（φ-1(|u'j|)）は、その最上位ビットに、入力ポートP601に供給されたメッセージD601（メッセージu'j）のうちの最上位ビット、つまりメッセージD601の符号ビットD604(sign(u'j))が付加されることにより、メッセージD606（チェックノードメッセージuj）とされ、セレクタ６０１のv端子に供給される。
【０３６２】
セレクタ６０１は、上述したように、バリアブルノード演算時にはv端子を選択しており、そのv端子に供給されたメッセージD606（チェックノードメッセージuj）は、メッセージD607として、演算器６０２に供給される。
【０３６３】
演算器６０２は、セレクタ６０１からのメッセージD607（メッセージuj）とレジスタ６０３に格納されている値D608とを加算することにより、メッセージD607を積算し、その結果得られる積算値を、レジスタ６０３に再格納する。なお、検査行列の1列に亘る全ての枝からの（メッセージu'jから得られた）メッセージD607が積算された場合、レジスタ６０３はリセットされる。
【０３６４】
検査行列の1列に亘るメッセージD607が１つずつ読み込まれ、レジスタ６０３に1列分のメッセージD607が積算された値が格納された場合、即ち、レジスタ６０３に、検査行列の１列に亘る全ての枝からのメッセージD607（メッセージuj）が積算された積算値（ｊ＝１からｄVまでのΣuj)が格納された場合、セレクタ６０４は、レジスタ６０３に格納されている値、即ち、検査行列の１列に亘る全ての枝からのメッセージD607（メッセージuj）が積算された積算値D608（ｊ＝１からｄVまでのΣuj)を選択し、レジスタ６０５に出力して格納させる。
【０３６５】
レジスタ６０５は、格納している値D608を、値D609として、セレクタ６０４と演算器６１２に供給する。レジスタ６０３に1列分のメッセージD607が積算された値が格納される直前までは、セレクタ６０４は、レジスタ６０５から供給された値D609を選択し、レジスタ６０５に出力し再格納させる。即ち、検査行列の１列に亘る全ての枝からのメッセージD607（メッセージuj）が積算されるまで、レジスタ６０５は、前回積算された値を、セレクタ６０４と演算器６１２に供給する。
【０３６６】
一方、レジスタ６０５から新たな値D609（ｊ＝１からｄVまでのΣuj)の出力が開始されると、即ち、レジスタ６０３に1列分のメッセージD607が積算された積算値（ｊ＝１からｄVまでのΣuj)が格納された直後、メッセージ計算部２１１においては、メッセージD601（メッセージu'j）と同一のメッセージDD601、即ち、メッセージメモリ１０４からの２回目のメッセージu'jが、入力ポートPD601から１つずつ入力され、そのメッセージDD601（メッセージu'j）のうちの最上位ビットを除く下位ビット、つまり、メッセージDD601の絶対値D613(|u'j|)が、LUT６１０に供給される。
【０３６７】
LUT６１０は、絶対値D613(|u'j|)を引数として、逆関数φ(|u'j|)の演算を行った演算結果D615（φ-1(|u'j|)）を読み出して出力する。LUT６００が出力する演算結果D605（φ-1(|u'j|)）は、その最上位ビットに、入力ポートPD601に供給されたメッセージDD601（メッセージu'j）のうちの最上位ビット、つまりメッセージDD601の符号ビットD304(sign(u'j))が付加されることにより、メッセージD616（チェックノードメッセージuj）とされ、セレクタ６１１のv端子に供給される。
【０３６８】
セレクタ６１１は、上述したように、バリアブルノード演算時にはv端子を選択しており、そのv端子に供給されたメッセージD616（チェックノードメッセージuj）は、メッセージD617として、演算器６１２に供給される。
【０３６９】
演算器６１２は、レジスタ６０５から供給された積算値D609（ｊ＝１からｄVまでのΣuj)から、セレクタ６１１からのメッセージD617（ｊ＝ｄVのメッセージuj）を減算する。即ち、演算器６１２では、検査行列の1列に亘る全ての枝からのメッセージD607（メッセージuj）の積算値D609（ｊ＝１からｄvまでのΣuj）から、求めたい枝からのメッセージuj（ｊ＝ｄvのuj）としてのメッセージD617を減算して、減算値D618（ｊ＝１からｄv−１までのΣuj）を求め、演算器６１３に供給する。
【０３７０】
演算器６１３は、入力ポートP101からの受信データD101と、演算器６１２からの減算値D618（ｊ＝１からｄv−１までのΣuj）とを加算することにより、メッセージD619（バリアブルノードメッセージvi）を求め、セレクタ６１５のv端子に供給する。
【０３７１】
セレクタ６１５は、バリアブルノード演算時にはv端子を選択しており、そのv端子に供給される演算器６１３からのメッセージD619（バリアブルノードメッセージvi）を、メッセージD622として、出力ポートP622から出力する。
【０３７２】
以上のように、セレクタ６０１，６１１、および６１５がv端子を選択しているメッセージ計算部２１１では、式（９）のバリアブルノード演算が行われ、その結果得られるメッセージ（バリアブルノードメッセージ）viが、出力ポートP622から出力される。
【０３７３】
次に、図３０は、図２８右側に示したチェックノード演算時の図２７のメッセージ計算部２１１の実質的な構成例を示している。
【０３７４】
なお、上述したように、チェックノード演算時には、セレクタ６０１，６１１、および６１５はc端子を選択するが、図３０では、図２７に図示した構成のうちの、セレクタ６０１，６１１、および６１５がc端子を選択することによってチェックノード演算時に機能しない部分（チェックノード演算に関係がない部分）の図示を省略してある。
【０３７５】
チェックノード演算時においては、入力ポートP601には、メッセージメモリ１０４から１つずつ読み出された、検査行列の各列に対応するバリアブルノードからのバリアブルノードメッセージviが、順次、メッセージD601として供給される。
【０３７６】
入力ポートP601に供給されたメッセージD601（メッセージvi）のうちの最上位ビットを除く下位ビット、つまり、メッセージD601の絶対値D603(|vi|)は、LUT６００に供給され、最上位ビット、つまりメッセージD601の符号ビットD604は、EXOR回路６０６に供給される。
【０３７７】
LUT６００は、絶対値D603(|vi|)を引数として、非線形関数φ(|vi|)の演算を行った演算結果D605（φ(|vi|)）を読み出し、セレクタ６０１のc端子に供給する。
【０３７８】
セレクタ６０１は、チェックノード演算時にはc端子を選択しており、そのc端子に供給されるLUT６００からの演算結果D605（φ(|vi|)）を、演算結果D607（φ(|vi|)）として、演算器６０２に供給する。
【０３７９】
演算器６０２は、演算結果D607（φ(|vi|)）とレジスタ６０３に格納されている値D608とを加算することにより、演算結果D607を積算し、その結果得られる積算値をレジスタ６０３に再格納する。なお、検査行列の1行に亘る全ての枝からのメッセージD601の絶対値D603(|vi|)に対する演算結果D607（φ(|vi|)）が積算された場合、レジスタ６０３はリセットされる。
【０３８０】
検査行列の1行に亘るメッセージD601が１つずつ読み込まれ、レジスタ６０３に1行分の演算結果D607が積算された積算値が格納された場合、セレクタ６０４は、レジスタ６０３に格納されている値、即ち、検査行列の１行に亘る全ての枝からのメッセージD601（メッセージvi）から求められたφ(|vi|)が積算された積算値D608（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）を選択し、レジスタ６０５に出力して格納させる。レジスタ６０５は、格納している積算値D608を、値D609として、セレクタ６０４と演算器６１２に供給する。
【０３８１】
レジスタ６０３に1行分の演算結果D607が積算された積算値が格納される直前までは、セレクタ６０４は、レジスタ６０５から供給された値D609を選択し、レジスタ６０５に出力して再格納させる。即ち、検査行列の１行に亘る全ての枝からのメッセージD601（メッセージvi）から求められたφ(|vi|)が積算されるまで、レジスタ６０５は、前回積算されたφ(|vi|)の積算値を、セレクタ６０４と演算器６１２に供給する。
【０３８２】
一方、レジスタ６０５から新たな値D609（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）の出力が開始されると、即ち、レジスタ６０５に1行分の演算結果D607が積算された積算値（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）が格納された直後、メッセージ計算部２１１において、メッセージD601（メッセージvi）と同一のメッセージDD601、即ち、メッセージメモリ１０４からの２回目のメッセージvi（１回目のメッセージviと同一のメッセージ）が、入力ポートPD601から１つずつ入力され、そのメッセージDD601のうちのその最上位ビットを除く下位ビット、つまり、メッセージDD601の絶対値D613(|vi|)が、LUT６１０に供給されるとともに、最上位ビット、つまりメッセージDD601の符号ビットD614が、EXOR回路６１４に供給される。
【０３８３】
LUT６１０は、メッセージDD601の絶対値D613(|vi|)を引数として、非線形関数φ(|vi|)の演算を行った演算結果D615（φ(|vi|)）を読み出し、セレクタ６１１のc端子に供給する。
【０３８４】
セレクタ６１１は、チェックノード演算時にはc端子を選択しており、そのc端子に供給されるLUT６１０からの演算結果D615（φ(|vi|)）を、演算結果D617（φ(|vi|)）として、演算器６１２に供給する。
【０３８５】
演算器６１２は、レジスタ６０５から供給された値D609から、セレクタ６１１から供給された値D617を減算し、その減算結果を、減算値D618として出力する。即ち、演算器６１２は、検査行列の1行に亘る全ての枝からのメッセージD601（メッセージvi）から求められたφ(|vi|)の積算値D609（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）から、求めたい枝からのメッセージDD601（メッセージvi）から求められたφ(|vi|)の値D617を減算して、その減算値（ｉ＝１からｉ＝ｄc−１までのΣφ(|vi|)）を減算値D618として出力する。
【０３８６】
以上の処理と並行して、EXOR回路６０６は、レジスタ６０７に格納されている値D611と、１回目のメッセージD601（メッセージvi）の最上位ビットである符号ビットD604との排他的論理和を演算することにより、符号ビットどうしの乗算を行い、乗算結果D610を、レジスタ６０７に再格納する。なお、検査行列の1行に亘る全ての枝からのメッセージD601の符号ビットD604が乗算された場合、レジスタ６０７はリセットされる。
【０３８７】
検査行列の1行に亘る全ての枝からのメッセージD601の符号ビットD604が乗算された乗算結果D610（ｉ＝１からｄcまでのΠsign(vi)）がレジスタ６０７に格納された場合、セレクタ６０８は、レジスタ６０７に格納されている値、即ち、検査行列の１行に亘る全ての枝からのメッセージD601の符号ビットD604が乗算された値D611（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）を選択し、レジスタ６０９に出力して格納させる。レジスタ６０９は、格納している値D612を、セレクタ６０８とEXOR回路６１４に供給する。
【０３８８】
検査行列の1行に亘る全ての枝からのメッセージD601の符号ビットD604が乗算された乗算結果D610（ｉ＝１からｄcまでのΠsign(vi)）がレジスタ６０７に格納される直前までは、セレクタ６０８は、レジスタ６０９から供給された値D612を選択し、レジスタ６０９に出力して再格納させる。即ち、検査行列の１行に亘る全ての枝からのメッセージD601（メッセージvi）の符号ビットD604が乗算されるまで、レジスタ６０９は、前回格納した値を、セレクタ６０８とEXOR回路６１４に供給する。
【０３８９】
一方、レジスタ６０９から新たな値D612（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）がEXOR回路６１４に供給されたとき、即ち、レジスタ６０７に１行に亘る全ての枝からのメッセージD601の符号ビットD604が乗算された値D611（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）が格納されたとき、レジスタ６０５には、上述したように、1行分の演算結果D607が積算された積算値（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）が格納される。
【０３９０】
レジスタ６０５に1行分の演算結果D607が積算された積算値（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）が格納されると、上述したように、メッセージ計算部２１１において、メッセージD601（メッセージvi）と同一のメッセージDD601、即ち、メッセージメモリ１０４からの２回目のメッセージviが、入力ポートPD601から１つずつ入力され、そのメッセージDD601のうちのその最上位ビットを除く下位ビット、つまり、メッセージDD601の絶対値(|vi|)が、LUT６１０に供給されるとともに、最上位ビット、つまりメッセージDD601の符号ビットD614が、EXOR回路６１４に供給される。
【０３９１】
EXOR回路６１４は、レジスタ６０９から供給された値D612と、入力ポートPD601からのメッセージDD601の符号ビットとの排他的論理和を演算することにより、値D612を、メッセージDD601の符号ビットで除算し、除算結果を除算値D620として出力する。即ち、EXOR回路６１４は、検査行列の１行に亘る全ての枝からのメッセージD601の符号ビットD604の乗算値（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）を、求めたい枝からのメッセージviとしてのメッセージDD601の符号ビットD614（ｉ＝ｄcのsign(vi)）で除算して、その除算値（ｉ＝１からｉ＝ｄc−１までのΠsign(vi)）を除算値D620として出力する。
【０３９２】
そして、メッセージ計算部２１１では、演算器６１２から出力された演算結果D618を下位ビットとするとともに、EXOR回路６１４から出力された除算値D620を最上位ビット（符号ビット）とするビット列D621（メッセージu'j）が、セレクタ６１５のc端子に供給される。
【０３９３】
セレクタ６１５は、チェックノード演算時にはc端子を選択しており、そのc端子に供給されるビット列D621（メッセージu'j）を、メッセージD622として、出力ポートP622から出力する。
【０３９４】
以上のように、セレクタ６０１，６１１、および６１５がc端子を選択しているメッセージ計算部２１１では、式（１０）のチェックノード演算が行われ、その結果得られるメッセージ（メッセージ）u'jが、出力ポートP622から出力される。
【０３９５】
なお、図２６の復号装置では、復号の最終段において、式（９）のバリアブルノード演算の代わりに、式（５）の演算が行われ、その演算結果が、最終的な復号結果として出力される。
【０３９６】
また、図２６の復号装置において、制御部２１２は、メッセージメモリ１０４に対するメッセージ（データ）の読み書き制御として、図１５のフローチャートで説明したように、図１２の復号装置の制御部１７４と同様の読み書き制御を行う。
【０３９７】
さらに、図２６の復号装置のメッセージメモリ１０４に対するメッセージの読み書きのタイミングも、図１２の復号装置について説明した図１６の場合と同様であり、図２６の復号装置についても、多少の高速動作が必要となるが、遅延メモリを設ける必要がない分、装置規模を低減することができる。さらに、図２６の復号装置では、メッセージ計算部２１１において、バリアブルノードの演算を行う回路と、チェックノードの演算を行う回路との一部（LUT６００、演算器６０２、レジスタ６０３、セレクタ６０４、レジスタ６０５、LUT６１０、および演算器６１２）が共有化されているので、その共有化の分だけ、図１２の復号装置よりも規模を削減することができる。
【０３９８】
また、図２６の復号装置のメッセージ計算部２１１では、ノードに入力される入力データxの絶対値|x|を引数として、同一の演算結果が得られる逆関数φ-1(x)と非線形関数φ(x)の演算をそれぞれ含む式（９）と式（１０）にそれぞれしたがって、バリアブルノード演算とチェックノード演算が行われる。
【０３９９】
従って、メッセージ計算部２１１には、図２７に示したように、入力ポートP601から供給される１回目のメッセージに対して、逆関数φ-1(x)および非線形関数φ(x)の演算を行うLUT６００と、入力ポートPD601から供給される２回目のメッセージに対して、逆関数φ-1(x)および非線形関数φ(x)の演算を行うLUT６１０との２つのLUTがあれば済み、図２２に示したように、１回目のメッセージに対して非線形関数φ(x)の演算を行うLUT３００、２回目のメッセージに対して非線形関数φ(x)の演算を行うLUT３１０、および逆関数φ-1(x)の演算を行うLUT３１４の３つのLUTを必要とするメッセージ計算部２０１よりも、規模を削減することができる。
【０４００】
次に、図３１は、本発明を適用した復号装置の第４実施の形態の構成例を示すブロック図である。なお、図中、図２１の復号装置の場合と対応する部分については、同一の符号を付してあり、以下では、その説明は、適宜省略する。即ち、図３１の復号装置は、メッセージ計算部２０１に代えて、メッセージ計算部２２１が設けられているとともに、制御部２０２に代えて、制御部２２２が設けられている他は、図２１の復号装置と同様に構成されている。
【０４０１】
図３１の復号装置では、メッセージ計算部２２１が、バリアブルノード演算を行う回路と、チェックノード演算を行う回路との一部を共有する構成となっており、さらに、遅延メモリを設けずに構成されている。
【０４０２】
図３１の復号装置では、メッセージメモリ１０４に記憶されているメッセージが１つずつ読み出され、メッセージ計算部２２１に供給される。メッセージ計算部２２１は、メッセージメモリ１０４からのメッセージを用いて演算が行われ、その演算によって求められたメッセージが、メッセージメモリ１０４に格納される。図３１の復号装置では、以上の処理が繰り返し行われ、フルシリアルの繰り返し復号が行われる。
【０４０３】
即ち、受信データメモリ１０５には、送信されてきたLDPC符号を受信することにより得られる、符号の0（または1）らしさを表す対数尤度比である受信データ（LDPC符号）D100が供給され、受信データメモリ１０５は、その受信データD100を記憶する。
【０４０４】
バリアブルノード演算時には、受信データメモリ１０５は、制御部２２２から供給される制御信号にしたがって、記憶している受信データを読み出し、受信データD101として、メッセージ計算部２２１に供給する。
【０４０５】
また、バリアブルノード演算時には、メッセージメモリ１０４は、制御部２２２から供給される制御信号にしたがい、記憶している同一のメッセージを２回読み出して、１回目に読み出したメッセージをメッセージD701として、メッセージ計算部２２１に供給し、２回目に読み出したメッセージをメッセージDD701として、メッセージ計算部２２１に供給する。さらに、制御部２２２が、バリアブルノード演算を指示する制御信号D703を、メッセージ計算部２２１に供給する。メッセージ計算部２２１は、メッセージメモリ１０４から供給されるメッセージD701とDD701、および受信データメモリ１０５から供給される受信データD101を用い、制御部２２２から供給される制御信号D703にしたがって、バリアブルノード演算を行い、そのバリアブルノード演算の結果得られたメッセージを、メッセージD722として、メッセージメモリ１０４に供給する。
【０４０６】
そして、メッセージメモリ１０４は、制御部２２２から供給される制御信号にしたがい、メッセージ計算部２２１から供給されるメッセージD722を記憶する。
【０４０７】
一方、チェックノード演算時には、メッセージメモリ１０４は、制御部２２２から供給される制御信号にしたがって、記憶している同一のメッセージを２回読み出して、１回目に読み出したメッセージをメッセージD701として、メッセージ計算部２２１に供給し、２回目に読み出したメッセージをメッセージDD701として、メッセージ計算部２２１に供給する。さらに、制御部２２２が、チェックノード演算を指示する制御信号D703を、メッセージ計算部２２１に供給する。
【０４０８】
メッセージ計算部２２１は、メッセージメモリ１０４から供給されるメッセージD701とDD701を用い、制御部２２２からの制御信号D703にしたがって、チェックノード演算を行い、そのチェックノード演算によって求められたメッセージを、メッセージD722として、メッセージメモリ１０４に供給する。
【０４０９】
そして、メッセージメモリ１０４は、制御部２２２から供給される制御信号にしたがい、メッセージ計算部２２１から供給されるメッセージD722を記憶する。
【０４１０】
ここで、図３１のメッセージ計算部２２１で行われる演算について説明する。
【０４１１】
いま、バリアブルノードに接続している枝のうちのi番目の枝から出力されるメッセージ（データ）として、式v'i=φ(|vi|)×sign(vi)で表されるメッセージv'iを導入すると、式（１）および式（７）は、式（１１）乃至式（１３）に書き直すことができる。
【０４１２】
【数１１】
0004807063.tif 000012
・・・（１１）
【０４１３】
【数１２】
0004807063.tif 000013
・・・（１２）
【０４１４】
【数１３】
0004807063.tif 000014
・・・（１３）
【０４１５】
ここで、式（１）のバリアブルノード演算は、式（１１）および式（１２）の演算に対応し、式（７）のチェックノード演算は、式（１３）の演算に対応する。
【０４１６】
式（１１）および式（１２）のバリアブルノード演算では、バリアブルノードに入力される入力データ（メッセージ）ujを、符号sign(uj)を含めて積算し（Σuj）、さらに、受信データu0iを加算して、その結果得られる加算値vi（=u0i+Σuj）の絶対値|vi|を引数とする非線形関数φ(|vi|)の演算を行うことにより、メッセージv'iが求められる。
【０４１７】
また、式（１３）のチェックノード演算では、チェックノードに入力される入力データ（メッセージ）v'iの絶対値|v'i|を積算し（Σ|v'i|）、その積算値Σ|v'i|を引数とする逆関数φ-1(Σ|v'i|)の演算を行う一方で、それとは別に、入力データv'iの符号ビットの相乗積（Πsign(v'i)）を求め、逆関数φ-1(Σ|v'i|)の演算結果と、入力データv'iの符号ビットの相乗積Πsign(v'i)とを乗算して、メッセージujが求められる。
【０４１８】
ここで、上述したように、非線形関数φ(x)とその逆関数φ-1(x)とは、x＞0において等しい。従って、式（１１）および式（１２）のバリアブルノード演算と、式（１３）のチェックノード演算のいずれでも、出力データxの絶対値|x|を引数として、関数φ(x)（φ-1(x)）の演算が行われることになる。
【０４１９】
図３１のメッセージ計算部２２１では、以上のような式（１１）および式（１２）のバリアブルノード演算と、式（１３）のチェックノード演算とが行われる。
【０４２０】
図３２は、図３１のメッセージ計算部２２１の構成例を示している。
【０４２１】
メッセージ計算部２２１は、図２２のメッセージ計算部２０１と同様に、遅延メモリを設けずに構成されている。また、メッセージ計算部２２１には、入力ポートP101,P701,PD701,P703と、出力ポートP722が設けられている。
【０４２２】
入力ポートP101には、受信データメモリ１０５から読み出された受信データD101が供給（入力）される。入力ポートP701には、メッセージメモリ１０４から２回読み出される同一のメッセージD701およびDD701のうちの１回目に読み出されるメッセージ（１回目のメッセージ）D701が供給（入力）され、入力ポートPD701には、２回目に読み出されるメッセージ（２回目のメッセージ）DD701が供給される。また、入力ポートP703には、制御部２２２（図３１）からの制御信号D703が供給される。
【０４２３】
メッセージ計算部２２１は、入力ポートP701から入力される１回目のメッセージD701と、入力ポートPD701から入力される２回目のメッセージDD701、さらには、必要に応じて、入力ポートP101から入力されるメッセージ（受信データ）D101を用い、入力ポートP703から入力される制御信号D703にしたがって、式（１１）および式（１２）のバリアブルノード演算、または式（１３）のチェックノード演算を行い、その結果得られるメッセージD722を、出力ポートP722から出力する。
【０４２４】
ここで、図３３を参照して、図３２のメッセージ計算部２２１で行われるバリアブルノード演算とチェックノード演算について説明する。
【０４２５】
図３３左側は、式（１）のバリアブルノード演算を行うバリアブルノードと、式（７）のチェックノード演算を行うチェックノードとを模式的に示しており、図２３右側と同一の図である。
【０４２６】
図３３左側では、図２３右側で説明したように、チェックノードに入力される入力データに、非線形関数φ(x)の演算を施してから、その演算結果が、チェックノードに入力され、チェックノードにおいて、非線形関数φ(x)の演算結果が積算されている。さらに、チェックノードから出力された出力データ（逆関数φ-1(x)の演算が施される前の、非線形関数φ(x)の演算結果の積算値）に、逆関数φ-1(x)の演算が施され、これにより、メッセージujが求められている。
【０４２７】
上述したように、図３３左側において、バリアブルノードから出力された出力データとしてのメッセージviは、チェックノードに入力される入力データxとして、非線形関数φ(x)の演算が施されてから、チェックノードに入力される。
【０４２８】
従って、図３３左側に示したように、チェックノードに入力される入力データxに、非線形関数φ(x)の演算を施す代わりに、図３３右側に示すように、バリアブルノードから出力された出力データx（バリアブルノードメッセージvi）に、非線形関数φ(x)の演算を施しても、バリアブルノード演算とチェックノード演算を行うことができる。
【０４２９】
即ち、図３３右側では、式（１１）および式（１２）で説明したように、バリアブルノードにおいて、そのバリアブルノードに入力される入力データujが積算されることにより、メッセージviが求められ、出力データとして出力されている。そして、バリアブルノードから出力された（メッセージvi）に、非線形関数φ(x)の演算が施され、メッセージv'iが求められている。このメッセージv'i（メッセージviに、非線形関数φ(x)の演算を施した演算結果）は、チェックノードに入力され、式（１３）で説明したように積算されて、出力データとして出力される。そして、その出力データ（メッセージviに、非線形関数φ(x)の演算を施した演算結果の積算値）に、逆関数φ-1(x)の演算が施されることにより、メッセージujが求められる。
【０４３０】
図３２のメッセージ計算部２２１では、図３３右側に示したようにメッセージv'iとujを求める式（１１）および式（１２）のバリアブルノード演算と式（１３）のチェックノード演算が行われる。
【０４３１】
このように、メッセージ計算部２２１は、図３３右側に示したメッセージv'iとujを求める式（１１）および式（１２）のバリアブルノード演算と式（１３）のチェックノード演算の両方を行うため、メッセージ計算部２２１には、バリアブルノードから出力された出力データxに対して、逆関数φ-1(x)と同一の演算結果が得られる非線形関数φ(x)の演算結果を出力するとともに、チェックノードから出力された出力データxに対して、逆関数φ-1(x)の演算結果を出力するLUT７１３が設けられている。
【０４３２】
そして、メッセージ計算部２２１は、入力ポートP703に供給された制御信号D703にしたがって、その実質的な構成を変えて、式（１１）および式（１２）のバリアブルノード演算と式（１３）のチェックノード演算を選択的に行う。
【０４３３】
即ち、メッセージ計算部２２１は、セレクタ７００，７０５，７１２、および７１５を有しており、入力ポートP703に供給された制御信号D703は、セレクタ７００，７０５，７１２、および７１５に供給される。
【０４３４】
セレクタ７００，７０５，７１２、および７１５は、v端子とc端子とを有し、制御信号D703にしたがい、v端子またはc端子のうちのいずれかに供給される値を選択して、後段に出力する。即ち、セレクタ７００，７０５，７１２、および７１５は、制御信号D703がバリアブルノード演算を指示する制御信号である場合には、v端子に供給される値を選択して後段に出力し、制御信号D703がチェックノード演算を指示する制御信号である場合には、c端子に供給される値を選択して後段に出力する。
【０４３５】
その結果、図３２のメッセージ計算部２２１では、制御信号D703がバリアブルノード演算を指示しているときには、バリアブルノード演算が行われ、制御信号D703がチェックノード演算を指示しているときには、チェックノード演算が行われる。
【０４３６】
即ち、図３４は、図３３右側に示したバリアブルノード演算時の図３２のメッセージ計算部２２１の実質的な構成例を示している。
【０４３７】
なお、上述したように、バリアブルノード演算時には、セレクタ７００，７０５，７１２、および７１５はv端子を選択するが、図３４では、図３２に図示した構成のうちの、セレクタ７００，７０５，７１２、および７１５がv端子を選択することによってバリアブルノード演算時に機能しない部分（バリアブルノード演算に関係がない部分）の図示を省略してある。
【０４３８】
メッセージ計算部２２１は、入力ポートP101,P701,PD701それぞれから入力されるメッセージを用いて、式（１１）および式（１２）のバリアブルノード演算を行い、その結果得られるメッセージD722を、出力ポートP722から出力する。
【０４３９】
即ち、入力ポートP101には、受信データメモリ１０５から読み出された受信データD101が供給される。また、入力ポートP701には、メッセージメモリ１０４から１つずつ読み出された、検査行列の各行に対応するチェックノードからの１回目のメッセージD701（メッセージuj）が供給される。
【０４４０】
入力ポートP101に供給された受信データD101は、演算器７１１に供給される。
【０４４１】
また、入力ポートP701に供給されたメッセージD701（メッセージuj）は、セレクタ７００のv端子に供給される。
【０４４２】
セレクタ７００は、上述したように、バリアブルノード演算時にはv端子を選択しており、そのv端子に供給されたメッセージD701（チェックノードメッセージuj）は、メッセージD705として、演算器７０１に供給される。
【０４４３】
演算器７０１は、セレクタ７００からのメッセージD705（メッセージuj）とレジスタ７０２に格納されている値D706とを加算することにより、メッセージD705を積算し、その結果得られる積算値を、レジスタ７０２に再格納する。なお、検査行列の1列に亘る全ての枝からのメッセージD705（メッセージuj）が積算された場合、レジスタ７０２はリセットされる。
【０４４４】
検査行列の1列に亘るメッセージD701（メッセージuj）が１つずつ読み込まれ、これにより、レジスタ７０２に1列分のメッセージD705（メッセージuj）が積算された値が格納された場合、即ち、レジスタ７０２に、検査行列の１列に亘る全ての枝からのメッセージD705（メッセージuj）が積算された積算値（ｊ＝１からｄVまでのΣuj)が格納された場合、セレクタ７０３は、レジスタ７０２に格納されている値、即ち、検査行列の１列に亘る全ての枝からのメッセージD705（メッセージuj）が積算された積算値D706（ｊ＝１からｄVまでのΣuj)を選択し、レジスタ７０４に出力して格納させる。
【０４４５】
レジスタ７０４は、格納している値D706を、値D707として、セレクタ７０３と演算器７１０に供給する。レジスタ７０２に1列分のメッセージD705（メッセージuj）が積算された値が格納される直前までは、セレクタ７０３は、レジスタ７０４から供給された値D707を選択し、レジスタ７０４に出力し再格納させる。即ち、検査行列の１列に亘る全ての枝からのメッセージD705（メッセージuj）が積算されるまで、レジスタ７０４は、前回積算された値を、セレクタ７０３と演算器７１０に供給する。
【０４４６】
一方、レジスタ７０４から新たな値D707（ｊ＝１からｄVまでのΣuj)の出力が開始されると、即ち、レジスタ７０２に1列分のメッセージD705（メッセージuj）が積算された積算値（ｊ＝１からｄVまでのΣuj)が格納された直後、メッセージ計算部２２１においては、メッセージD701（メッセージuj）と同一のメッセージDD701、即ち、メッセージメモリ１０４からの２回目のメッセージujが、入力ポートPD701から１つずつ入力され、そのメッセージDD701（メッセージuj）が、セレクタ７０５のv端子に供給される。
【０４４７】
セレクタ７０５は、上述したように、バリアブルノード演算時にはv端子を選択しており、そのv端子に供給されたメッセージDD701（チェックノードメッセージuj）は、メッセージD713として、演算器７１０に供給される。
【０４４８】
演算器７１０は、レジスタ７０４から供給された積算値D707（ｊ＝１からｄVまでのΣuj)から、セレクタ７０５からのメッセージD713（チェックノードメッセージuj）を減算する。即ち、演算器７１０では、検査行列の1列に亘る全ての枝からのメッセージD705（メッセージuj）の積算値D707（ｊ＝１からｄvまでのΣuj）から、求めたい枝からのメッセージuj（ｊ＝ｄvのuj）としてのメッセージD713を減算して、減算値D714（ｊ＝１からｄv−１までのΣuj）を求め、演算器７１１に供給する。
【０４４９】
演算器７１１は、入力ポートP101からの受信データD101と、演算器７１０からの減算値D714（ｊ＝１からｄv−１までのΣuj）とを加算することにより、メッセージD715（バリアブルノードメッセージvi）を求めて出力する。
【０４５０】
即ち、以上により、式（１１）の演算が行われ、演算器７１１からバリアブルノードメッセージviが出力される。
【０４５１】
演算器７１１が出力するメッセージD715（メッセージvi）のうちの最上位ビットを除く下位ビット、つまり、メッセージD715の絶対値D716(|vi|)は、セレクタ７１２のv端子に供給され、最上位ビット、つまりメッセージD715（メッセージvi）の符号ビットD717(sign(vi))は、セレクタ７１５のv端子に供給される。
【０４５２】
セレクタ７１２は、バリアブルノード演算時にはv端子を選択しており、そのv端子に供給される演算器７１１が出力するメッセージD715（メッセージvi）の絶対値D716(|vi|)を、絶対値D718として、LUT７１３に供給する。
【０４５３】
LUT７１３は、セレクタ７１２からの絶対値D718(|vi|)を引数として、非線形関数φ(|vi|)の演算を行った演算結果D719（φ(|vi|)）を読み出して出力する。
【０４５４】
セレクタ７１５も、バリアブルノード演算時にはv端子を選択しており、そのv端子に供給される演算器７１１が出力するメッセージD715（メッセージvi）の符号ビットD717(sign(vi))を、符号ビットD721(sign(vi))として出力する。
【０４５５】
メッセージ計算部２１１は、セレクタ７１５が出力する符号ビットD721(sign(vi))を、LUT７１３が出力する演算結果D719（φ(|vi|)）の符号ビットとして最上位ビットに付加することにより、メッセージD722（メッセージv'i）を得て、出力ポートP722から出力する。
【０４５６】
以上により、式（１２）の演算が行われ、メッセージv'iが求められる。
【０４５７】
以上のように、セレクタ７００，７０５，７１２、および７１５がv端子を選択しているメッセージ計算部２２１では、式（１１）および式（１２）のバリアブルノード演算が行われ、その結果得られるメッセージv'iが、出力ポートP722から出力される。
【０４５８】
次に、図３５は、図３３右側に示したチェックノード演算時の図３２のメッセージ計算部２２１の実質的な構成例を示している。
【０４５９】
なお、上述したように、チェックノード演算時には、セレクタ７００，７０５，７１２、および７１５はc端子を選択するが、図３５では、図３２に図示した構成のうちの、セレクタ７００，７０５，７１２、および７１５がc端子を選択することによってチェックノード演算時に機能しない部分（チェックノード演算に関係がない部分）の図示を省略してある。
【０４６０】
チェックノード演算時においては、入力ポートP701には、メッセージメモリ１０４から１つずつ読み出された、検査行列の各列に対応するバリアブルノードからのバリアブルノードメッセージviから得られたメッセージ（式（１１）および式（１２）のバリアブルノード演算によって求められたメッセージ）v'iが、順次、メッセージD701として供給される。
【０４６１】
入力ポートP701に供給されたメッセージD701（メッセージv'i）のうちの最上位ビットを除く下位ビット、つまり、メッセージD701の絶対値D703(|v'i|)は、セレクタ７００のc端子に供給され、最上位ビット、つまりメッセージD701の符号ビットD704は、EXOR回路７０６に供給される。
【０４６２】
セレクタ７００は、チェックノード演算時にはc端子を選択しており、そのc端子に供給される、メッセージD701の絶対値D703(|v'i|)を、絶対値D705（|v'i|）として、演算器７０１に供給する。
【０４６３】
演算器７０１は、絶対値D705（|v'i|）とレジスタ７０２に格納されている値D706とを加算することにより、絶対値D705を積算し、その結果得られる積算値をレジスタ７０２に再格納する。なお、検査行列の1行に亘る全ての枝からの（メッセージviから得られた）メッセージD701（v'i）の絶対値D705(D703)(|v'i|)が積算された場合、レジスタ７０２はリセットされる。
【０４６４】
検査行列の1行に亘る（メッセージviから得られた）メッセージD701が１つずつ読み込まれ、レジスタ７０２に1行分の絶対値D705が積算された積算値が格納された場合、セレクタ７０３は、レジスタ７０２に格納されている値、即ち、検査行列の１行に亘る全ての枝からのメッセージD701（メッセージv'i）が積算された積算値D706（ｉ＝１からｉ＝ｄcまでのΣ|v'i|）を選択し、レジスタ７０４に出力して格納させる。レジスタ７０４は、格納している積算値D706を、値D707として、セレクタ７０３と演算器７１０に供給する。
【０４６５】
レジスタ７０２に1行分の絶対値D705が積算された積算値が格納される直前までは、セレクタ７０３は、レジスタ７０４から供給された値D707を選択し、レジスタ７０４に出力して再格納させる。即ち、検査行列の１行に亘る全ての枝からのメッセージD701（メッセージv'i）の絶対値|v'i|が積算されるまで、レジスタ７０４は、前回積算された絶対値|v'i|の積算値を、セレクタ７０３と演算器７１０に供給する。
【０４６６】
一方、レジスタ７０４から新たな値D707（ｉ＝１からｉ＝ｄcまでのΣ|v'i|）の出力が開始されると、即ち、レジスタ７０４に1行分の絶対値D705（|v'i|）が積算された積算値（ｉ＝１からｉ＝ｄcまでのΣ|v'i|）が格納された直後、メッセージ計算部２２１において、メッセージD701（メッセージv'i）と同一のメッセージDD701、即ち、メッセージメモリ１０４からの２回目のメッセージv'i（１回目のメッセージv'iと同一のメッセージ）が、入力ポートPD701から１つずつ入力され、そのメッセージDD701(v'i)のうちのその最上位ビットを除く下位ビット、つまり、メッセージDD701の絶対値D711(|v'i|)が、セレクタ７０５のc端子に供給されるとともに、最上位ビット、つまりメッセージDD701(v'i)の符号ビットD712(sign(v'i))が、EXOR回路７１４に供給される。
【０４６７】
セレクタ７０５は、チェックノード演算時にはc端子を選択しており、そのc端子に供給されるメッセージDD701(v'i)の絶対値D711(|v'i|)を、絶対値D713（|v'i|）として、演算器７１０に供給する。
【０４６８】
演算器７１０は、レジスタ７０４から供給された値D707（Σ|v'i|）から、セレクタ７０５から供給された値D713(|v'i|)を減算し、その減算結果を、減算値D714として出力する。即ち、演算器７１０は、検査行列の1行に亘る全ての枝からのメッセージD701（メッセージv'i）の絶対値|v'i|の積算値D707（ｉ＝１からｉ＝ｄcまでのΣ|v'i|）から、求めたい枝からのメッセージDD701（i＝ｄcのv'i）の絶対値D713（|v'i|）を減算して、その減算値（ｉ＝１からｉ＝ｄc−１までのΣ|v'i|）を値D714として、セレクタ７１２のＣ端子に供給する。
【０４６９】
セレクタ７１２は、チェックノード演算時には、c端子を選択しており、そのc端子に供給される値D714（ｉ＝１からｉ＝ｄc−１までのΣ|v'i|）を、値D718として、LUT713に供給する。
【０４７０】
LUT７１３は、セレクタ７１２からの値D718(Σ|v'i|)を引数として、逆関数φ-1(Σ|v'i|)の演算を行った演算結果D719（φ-1(Σ|v'i|)）を読み出して出力する。
【０４７１】
以上の処理と並行して、EXOR回路７０６は、レジスタ７０７に格納されている値D709と、１回目のメッセージD701（メッセージv'i）の最上位ビットである符号ビットD704(sign(v'i))との排他的論理和を演算することにより、符号ビットD704どうしの乗算を行い、乗算結果D708を、レジスタ７０７に再格納する。なお、検査行列の1行に亘る全ての枝からのメッセージD701の符号ビットD704が乗算された場合、レジスタ７０７はリセットされる。
【０４７２】
検査行列の1行に亘る全ての枝からのメッセージD701の符号ビットD704が乗算された乗算結果D708（ｉ＝１からｄcまでのΠsign(v'i)）がレジスタ７０７に格納された場合、セレクタ７０８は、レジスタ７０７に格納されている値、即ち、検査行列の１行に亘る全ての枝からのメッセージD701の符号ビットD704が乗算された値D709（ｉ＝１からｉ＝ｄcまでのΠsign(v'i)）を選択し、レジスタ７０９に出力して格納させる。レジスタ７０９は、格納している値D710を、セレクタ７０８とEXOR回路７１４に供給する。
【０４７３】
検査行列の1行に亘る全ての枝からのメッセージD701の符号ビットD704が乗算された乗算結果D708（ｉ＝１からｄcまでのΠsign(v'i)）がレジスタ７０７に格納される直前までは、セレクタ７０８は、レジスタ７０９から供給された値D710を選択し、レジスタ７０９に出力して再格納させる。即ち、検査行列の１行に亘る全ての枝からのメッセージD701（メッセージv'i）の符号ビットD704が乗算されるまで、レジスタ７０９は、前回格納した値を、セレクタ７０８とEXOR回路７１４に供給する。
【０４７４】
一方、レジスタ７０９から新たな値D710（ｉ＝１からｉ＝ｄcまでのΠsign(v'i)）がEXOR回路７１４に供給されたとき、即ち、レジスタ７０７に１行に亘る全ての枝からのメッセージD701の符号ビットD704が乗算された値D709（ｉ＝１からｉ＝ｄcまでのΠsign(v'i)）が格納されたとき、レジスタ７０４には、上述したように、1行分の絶対値D705（|v'i|）が積算された積算値（ｉ＝１からｉ＝ｄcまでのΣ|v'i|）が格納される。
【０４７５】
レジスタ７０４に1行分の絶対値D705が積算された積算値（ｉ＝１からｉ＝ｄcまでのΣ|v'i|）が格納されると、上述したように、メッセージ計算部２２１において、メッセージD701（メッセージv'i）と同一のメッセージDD701、即ち、メッセージメモリ１０４からの２回目のメッセージv'iが、入力ポートPD701から１つずつ入力され、そのメッセージDD701のうちのその最上位ビットを除く下位ビット、つまり、メッセージDD701の絶対値(|v'i|)が、セレクタ７０５のc端子に供給されるとともに、最上位ビット、つまりメッセージDD701の符号ビットD712(sign(v'i))が、EXOR回路７１４に供給される。
【０４７６】
EXOR回路７１４は、レジスタ７０９から供給された値D710と、入力ポートPD701からのメッセージDD701の符号ビットD712との排他的論理和を演算することにより、値D710を、メッセージDD701の符号ビットD712で除算し、除算結果を除算値D720として、セレクタ７１５のc端子に供給する。即ち、EXOR回路７１４は、検査行列の１行に亘る全ての枝からのメッセージD701の符号ビットD704の乗算値（ｉ＝１からｉ＝ｄcまでのΠsign(v'i)）を、求めたい枝からのメッセージv'iとしてのメッセージDD701の符号ビットD712（ｉ＝ｄcのsign(v'i)）で除算して、その除算値（ｉ＝１からｉ＝ｄc−１までのΠsign(v'i)）を除算値D720として、セレクタ７１５のc端子に供給する。
【０４７７】
セレクタ７１５は、チェックノード演算時にはc端子を選択しており、そのc端子に供給される除算値D720（ｉ＝１からｉ＝ｄc−１までのΠsign(v'i)）を、符号ビットD721として出力する。
【０４７８】
そして、メッセージ計算部２２１では、以上のようにしてセレクタ７１５から出力されたD721（Πsign(v'i)）を、LUT７１３が出力する演算結果D719（φ-1(Σ|v'i|)）に符号ビットとして付加（乗算）することにより、式（１３）で表されるメッセージ（チェックノードメッセージ）ujを得て、メッセージD722として、出力ポートP722から出力する。
【０４７９】
以上のように、セレクタ７００，７０５，７１２、および７１５がc端子を選択しているメッセージ計算部２２１では、式（１３）のチェックノード演算が行われ、その結果得られるメッセージujが、出力ポートP722から出力される。
【０４８０】
なお、図３１の復号装置では、復号の最終段において、式（１１）および式（１２）のバリアブルノード演算の代わりに、式（５）の演算が行われ、その演算結果が、最終的な復号結果として出力される。
【０４８１】
また、図３１の復号装置において、制御部２２２は、メッセージメモリ１０４に対するメッセージ（データ）の読み書き制御として、図１５のフローチャートで説明したように、図１２の復号装置の制御部１７４と同様の読み書き制御を行う。
【０４８２】
さらに、図３１の復号装置のメッセージメモリ１０４に対するメッセージの読み書きのタイミングも、図１２の復号装置について説明した図１６の場合と同様であり、図３１の復号装置についても、多少の高速動作が必要となるが、遅延メモリを設ける必要がない分、装置規模を低減することができる。さらに、図３１の復号装置では、メッセージ計算部２２１において、バリアブルノードの演算を行う回路と、チェックノードの演算を行う回路との一部（演算器７０１、レジスタ７０２、セレクタ７０３、レジスタ７０４、演算器７１０、およびLUT７１３）が共有化されているので、その共有化の分だけ、図１２の復号装置よりも規模を削減することができる。
【０４８３】
また、図３１の復号装置のメッセージ計算部２２１では、ノードから出力された出力データxの絶対値|x|を引数として、同一の演算結果が得られる逆関数φ-1(x)と非線形関数φ(x)の演算をそれぞれ含む式（１２）と式（１３）をそれぞれ用いたバリアブルノード演算とチェックノード演算が行われる。
【０４８４】
従って、メッセージ計算部２２１には、図３２に示したように、出力データxの絶対値|x|に対して、逆関数φ-1(x)と非線形関数φ(x)の演算を行うLUT７１３の１つだけあれば済み、図２２に示したLUT３００，３１０、および３１４の３つのLUTを必要とするメッセージ計算部２０１、さらには、図２７に示したLUT６００および６１０の２つのLUTを必要とするメッセージ計算部２１１よりも、規模を削減することができる。
【０４８５】
次に、図３６は、本発明を適用した復号装置の第５実施の形態の構成例を示すブロック図である。なお、図中、図２１の復号装置の場合と対応する部分については、同一の符号を付してあり、以下では、その説明は、適宜省略する。即ち、図３６の復号装置は、メッセージ計算部２０１に代えて、メッセージ計算部２３１が設けられているとともに、制御部２０２に代えて、制御部２３２が設けられている他は、図２１の復号装置と同様に構成されている。
【０４８６】
図３６の復号装置では、メッセージ計算部２３１が、図２１の復号装置のメッセージ計算部２０１と同様に、バリアブルノード演算を行う回路と、チェックノード演算を行う回路との一部を共有する構成となっている。さらに、図３６の復号装置は、バリアブルノード演算とチェックノード演算とを行うメッセージ計算部２３１が、遅延メモリを設けずに構成されている。
【０４８７】
図３６の復号装置では、メッセージメモリ１０４からメッセージ計算部２３１に、入力メッセージが１つずつ読み出され、メッセージ計算部２３１において、その入力メッセージを用いて、所望の枝に対応する出力メッセージが計算される。そして、その計算によって求められた出力メッセージが、メッセージメモリ１０４に格納されていく。図３６の復号装置では、以上の処理が繰り返し行われ、フルシリアルの繰り返し復号が行われる。
【０４８８】
即ち、受信データメモリ１０５には、送信されてきたLDPC符号を受信することにより得られる、符号の0（または1）らしさを表す対数尤度比である受信データ（LDPC符号）D100が供給され、受信データメモリ１０５は、その受信データD100を格納（記憶）する。
【０４８９】
バリアブルノード演算時には、受信データメモリ１０５は、制御部２３２から供給される制御信号にしたがって、記憶している受信データを読み出し、受信データD101として、メッセージ計算部２３１に供給する。
【０４９０】
また、バリアブルノード演算時には、メッセージメモリ１０４は、制御部２３２から供給される制御信号にしたがい、記憶している同一のメッセージを２回読み出して、１回目に読み出したメッセージをメッセージD801として、メッセージ計算部２３１に供給し、２回目に読み出したメッセージもメッセージD801として、メッセージ計算部２３１に供給する。メッセージ計算部２３１は、メッセージメモリ１０４から２回供給されるメッセージD801、および受信データメモリ１０５から供給される受信データD101を用い、制御部２３２から供給される制御信号D203にしたがって、式（１）のバリアブルノード演算を行い、そのバリアブルノード演算の結果得られたメッセージ（バリアブルノードメッセージ）viを、メッセージD802として、メッセージメモリ１０４に供給する。
【０４９１】
そして、メッセージメモリ１０４は、制御部２３２から供給される制御信号にしたがい、メッセージ計算部２３１から供給されるメッセージD802（バリアブルノードメッセージvi）を記憶する。
【０４９２】
一方、チェックノード演算時には、メッセージメモリ１０４は、制御部２３２から供給される制御信号にしたがって、記憶している同一のメッセージ（バリアブルノードメッセージvi）を２回読み出して、１回目に読み出したメッセージをメッセージD801として、メッセージ計算部２３１に供給し、２回目に読み出したメッセージもメッセージD801として、メッセージ計算部２３１に供給する。
【０４９３】
メッセージ計算部２３１は、メッセージメモリ１０４から２回供給されるメッセージD801を用い、制御部２３２からの制御信号Ｄ203にしたがって、式（７）のチェックノード演算を行い、そのチェックノード演算によって求められたメッセージ（チェックノードメッセージ）ujを、メッセージD802として、メッセージメモリ１０４に供給する。
【０４９４】
そして、メッセージメモリ１０４は、制御部２３２から供給される制御信号にしたがい、メッセージ計算部２３１から供給されるメッセージD802（チェックノードメッセージuj）を記憶する。
【０４９５】
メッセージメモリ１０４が記憶したメッセージ計算部２３１からのメッセージD802、即ち、チェックノードメッセージujは、次のバリアブルノード演算時に、メッセージD801として２回読み出され、メッセージ計算部２３１に供給される。
【０４９６】
図３７は、図３６のメッセージ計算部２３１の構成例を示している。
【０４９７】
なお、図中、図２２のメッセージ計算部２０１と対応する部分については、同一の符号を付してあり、以下では、その説明は、適宜省略する。
【０４９８】
メッセージ計算部２３１は、図２２のメッセージ計算部２０１と同様に、遅延メモリを設けずに構成されている。
【０４９９】
また、図２２のメッセージ計算部２０１は、入力ポートP101およびP203の他に、外部から１回目のメッセージが供給（入力）される入力ポートP201と、２回目のメッセージが供給される入力ポートPD201を有していたが、メッセージ計算部２３１では、その２つの入力ポートP201とPD201に代えて、１つの入力ポートP801が設けられており、１回目のメッセージおよび２回目のメッセージのいずれも、入力ポートP801から入力されるようになっている。
【０５００】
入力ポートP101には、受信データメモリ１０５から読み出された受信データD101が供給（入力）される。また、入力ポートP801には、メッセージメモリ１０４から２回読み出される同一のメッセージD801（１回目のメッセージと２回目のメッセージ）が供給される。
【０５０１】
メッセージ計算部２３１は、入力ポートP801から入力される１回目のメッセージD801と２回目のメッセージD801、さらには、必要に応じて、入力ポートP101から入力されるメッセージ（受信データ）を用い、入力ポートP203から入力される制御信号D203にしたがって、式（１）のバリアブルノード演算または式（７）のチェックノード演算を行い、その結果得られるメッセージD802を、出力ポートP802から出力する。
【０５０２】
即ち、入力ポートP101に供給された受信データD101は、演算器３１３に供給され、入力ポートP801に供給された１回目のメッセージD801は、セレクタ３０１のv端子に供給される。
【０５０３】
さらに、入力ポートP801に供給された１回目のメッセージD801のうちの最上位ビットを除く下位ビット、即ち、メッセージD801の絶対値は、値D303として、LUT３００に供給され、１回目のメッセージD801のうちの最上位ビット、即ち、メッセージD801の符号ビットは、値D304として、EXOR回路３０６に供給されるとともに、値D313として、EXOR回路３１５に供給される。
【０５０４】
また、入力ポートPD801に供給された２回目のメッセージD801も、１回目のメッセージD801と同様に、メッセージ計算部２３１の各部に供給される。即ち、入力ポートP801に供給された２回目のメッセージD801は、セレクタ３０１のv端子に供給される。さらに、入力ポートP801に供給された２回目のメッセージD801の絶対値は、値D303として、LUT３００に供給され、２回目のメッセージD801の符号ビットは、値D304として、EXOR回路３０６に供給されるとともに、値D313として、EXOR回路３１５に供給される。
【０５０５】
また、入力ポートP203に供給された制御信号D203は、セレクタ３０１および３１６に供給される。
【０５０６】
セレクタ３０１および３１６は、v端子とc端子とを有し、制御信号D203にしたがい、v端子またはc端子のうちのいずれかに供給される値を選択して、後段に出力する。即ち、セレクタ３０１および３１６は、制御信号D203がバリアブルノード演算を指示する制御信号である場合には、v端子に供給される値を選択して後段に出力し、制御信号D203がチェックノード演算を指示する制御信号である場合には、c端子に供給される値を選択して後段に出力する。
【０５０７】
その結果、図３７のメッセージ計算部２３１では、図２２のメッセージ計算部２０１と同様に、制御信号D203がバリアブルノード演算を指示しているときには、バリアブルノード演算が行われ、制御信号D203がチェックノード演算を指示しているときには、チェックノード演算が行われる。
【０５０８】
図３８は、バリアブルノード演算時の図３７のメッセージ計算部２３１の実質的な構成例を示している。
【０５０９】
なお、上述したように、バリアブルノード演算時には、セレクタ３０１および３１６はv端子を選択するが、図３８では、図３７に図示した構成のうちの、セレクタ３０１および３１６がv端子を選択することによってバリアブルノード演算時に機能しない部分（バリアブルノード演算に関係がない部分）の図示を省略してある。
【０５１０】
メッセージ計算部２３１は、入力ポートP101,P801それぞれから入力されるメッセージを用いて、式（１）のバリアブルノード演算を行い、その結果得られるメッセージD802を、出力ポートP802から出力する。
【０５１１】
即ち、入力ポートP101には、受信データメモリ１０５から読み出された受信データD101が供給される。また、入力ポートP801には、メッセージメモリ１０４から１つずつ読み出された、検査行列の各行に対応するチェックノードからの１回目のメッセージD801（チェックノードメッセージuj）が供給される。
【０５１２】
入力ポートP101に供給された受信データD101は、演算器３１３に供給される。
【０５１３】
また、入力ポートP801に供給されたメッセージD801（メッセージuj）は、セレクタ３０１のv端子に供給され、バリアブルノード演算時にはv端子を選択しているセレクタ３０１から、メッセージD306として、演算器３０２（と演算器３１２）に供給される。
【０５１４】
演算器３０２は、セレクタ３０１からのメッセージD306（メッセージuj）とレジスタ３０３に格納されている値D307とを加算することにより、メッセージD306を積算し、その結果得られる積算値を、レジスタ３０３に再格納する。なお、検査行列の1列に亘る全ての枝からのメッセージD306が積算された場合、レジスタ３０３はリセットされる。
【０５１５】
検査行列の1列に亘るメッセージD801が１つずつ読み込まれ、レジスタ３０３に1列分のメッセージD306が積算された値が格納された場合、即ち、レジスタ３０３に、検査行列の１列に亘る全ての枝からのメッセージD306（メッセージuj）が積算された積算値（ｊ＝１からｄVまでのΣuj)が格納された場合、セレクタ３０４は、レジスタ３０３に格納されている値、即ち、検査行列の１列に亘る全ての枝からのメッセージD306（メッセージuj）が積算された積算値D307（ｊ＝１からｄVまでのΣuj)を選択し、レジスタ３０５に出力して格納させる。
【０５１６】
レジスタ３０５は、格納している値D307を、値D308として、セレクタ３０４と演算器３１２に供給する。レジスタ３０３に1列分のメッセージD306が積算された値が格納される直前までは、セレクタ３０４は、レジスタ３０５から供給された値D308を選択し、レジスタ３０５に出力し再格納させる。即ち、検査行列の１列に亘る全ての枝からのメッセージD306（メッセージuj）が積算されるまで、レジスタ３０５は、前回積算された値を、セレクタ３０４と演算器３１２に供給する。
【０５１７】
一方、レジスタ３０５から新たな値D308（ｊ＝１からｄVまでのΣuj)の出力が開始されると、即ち、レジスタ３０３に1列分のメッセージD801（uj）が積算された積算値（ｊ＝１からｄVまでのΣuj)が格納された直後、メッセージ計算部２３１においては、メッセージD801（メッセージuj）と同一のメッセージD801、即ち、メッセージメモリ１０４からの２回目のメッセージujが、入力ポートP801から１つずつ入力され、そのメッセージD801が、セレクタ３０１のv端子に供給される。
【０５１８】
セレクタ３０１は、上述したように、v端子を選択しており、そのv端子に供給されるメッセージ（２回目のメッセージuj）D801を、メッセージD315として、演算器３１２に供給する（とともに、メッセージD306として演算器３０２に供給する）。
【０５１９】
演算器３１２は、レジスタ３０５から供給された積算値D308から、入力ポートP801からセレクタ３０１を介して供給されたメッセージD315を減算する。即ち、演算器３１２では、検査行列の1列に亘る全ての枝からのメッセージD801（メッセージuj）の積算値D308（ｊ＝１からｄvまでのΣuj）から、求めたい枝からのメッセージuj（ｊ＝ｄvのuj）としてのメッセージD315を減算して、減算値（ｊ＝１からｄv−１までのΣuj）を求め、演算器３１３に供給する。
【０５２０】
演算器３１３は、入力ポートP101からの受信データD101と、演算器３１２からの減算値（ｊ＝１からｄv−１までのΣuj）とを加算し、その結果得られる加算値D317を、セレクタ３１６のv端子に供給する。
【０５２１】
セレクタ３１６は、バリアブルノード演算時にはv端子を選択しており、そのv端子に供給される演算器３１３からの加算値D317を、メッセージD802（メッセージvi）として、出力ポートP802から出力する。
【０５２２】
以上のように、セレクタ３０１および３０４がv端子を選択しているメッセージ計算部２３１では、式（１）のバリアブルノード演算が行われ、その結果得られるメッセージ（バリアブルノードメッセージ）viが、出力ポートP802から出力される。
【０５２３】
図３９は、チェックノード演算時の図３７のメッセージ計算部２３１の実質的な構成例を示している。
【０５２４】
なお、上述したように、チェックノード演算時には、セレクタ３０１および３１６はc端子を選択するが、図３９では、図３７に図示した構成のうちの、セレクタ３０１および３１６がc端子を選択することによってチェックノード演算時に機能しない部分（チェックノード演算に関係がない部分）の図示を省略してある。
【０５２５】
チェックノード演算時においては、入力ポートP801には、メッセージメモリ１０４から１つずつ読み出された、検査行列の各列に対応するバリアブルノードからのバリアブルノードメッセージviが、順次、メッセージD801として供給される。
【０５２６】
入力ポートP801に供給されたメッセージD801（メッセージuj）のうちの最上位ビットを除く下位ビット、つまり、メッセージD801の絶対値D303(|vi|)は、LUT３００に供給され、最上位ビット、つまりメッセージD801の符号ビットは、符号ビットD304として、EXOR回路３０６に供給される（とともに、値D313として、EXOR回路３１５に供給される）。
【０５２７】
LUT３００は、絶対値D303(|vi|)を引数として、非線形関数φ(|vi|)の演算を行った演算結果D305（φ(|vi|)）を読み出し、セレクタ３０１のc端子に供給する。
【０５２８】
セレクタ３０１は、チェックノード演算時にはc端子を選択しており、そのc端子に供給されるLUT３００からの演算結果D305（φ(|vi|)）を、演算結果D306（φ(|vi|)）として、演算器３０２に供給する（とともに、演算結果D315（φ(|vi|)）として、演算器３１２に供給する）。
【０５２９】
演算器３０２は、演算結果D306（φ(|vi|)）とレジスタ３０３に格納されている値D307とを加算することにより、演算結果D306を積算し、その結果得られる積算値をレジスタ３０３に再格納する。なお、検査行列の1行に亘る全ての枝からのメッセージD801の絶対値D303(|vi|)に対する演算結果D306（φ(|vi|)）が積算された場合、レジスタ３０３はリセットされる。
【０５３０】
検査行列の1行に亘るメッセージD801が１つずつ読み込まれ、レジスタ３０３に1行分の演算結果D306が積算された積算値が格納された場合、セレクタ３０４は、レジスタ３０３に格納されている値、即ち、検査行列の１行に亘る全ての枝からのメッセージD801（メッセージvi）から求められたφ(|vi|)が積算された積算値D307（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）を選択し、レジスタ３０５に出力して格納させる。レジスタ３０５は、格納している積算値D307を、値D308として、セレクタ３０４と演算器３１２に供給する。
【０５３１】
レジスタ３０３に1行分の演算結果D306が積算された積算値が格納される直前までは、セレクタ３０４は、レジスタ３０５から供給された値D308を選択し、レジスタ３０５に出力して再格納させる。即ち、検査行列の１行に亘る全ての枝からのメッセージD801（メッセージvi）から求められたφ(|vi|)が積算されるまで、レジスタ３０５は、前回積算されたφ(|vi|)の積算値を、セレクタ３０４と演算器３１２に供給する。
【０５３２】
一方、レジスタ３０５から新たな値D308（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）の出力が開始されると、即ち、レジスタ３０５に1行分の演算結果D306が積算された積算値（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）が格納された直後、メッセージ計算部２３１において、メッセージメモリ１０４からの２回目のメッセージD801（vi）が、入力ポートP801から１つずつ入力され、そのメッセージD801の絶対値D303(|vi|)が、LUT３００に供給され、メッセージD801の符号ビットが、符号ビットD313として、EXOR回路３１５に供給される（とともに、符号ビットD304として、EXOR回路３１５に供給される）。
【０５３３】
LUT３００は、メッセージD801の絶対値D303(|vi|)を引数として、非線形関数φ(|vi|)の演算を行った演算結果D305（φ(|vi|)）を読み出し、セレクタ３０１のc端子に供給する。
【０５３４】
セレクタ３０１は、チェックノード演算時にはc端子を選択しており、そのc端子に供給されるLUT３００からの演算結果D305（φ(|vi|)）を、演算結果D315（φ(|vi|)）として、演算器３１２に供給する（とともに、演算結果D306として、演算器３０２に供給する）。
【０５３５】
演算器３１２は、レジスタ３０５から供給された値D308から、セレクタ３０１から供給された値D315を減算し、その減算結果を、減算値D316としてLUT３１４に供給する。即ち、演算器３１２は、検査行列の1行に亘る全ての枝からのメッセージD801（メッセージvi）から求められたφ(|vi|)の積算値D308（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）から、求めたい枝からのメッセージD801（メッセージvi）から求められたφ(|vi|)の値D315を減算して、その減算値（ｉ＝１からｉ＝ｄc−１までのΣφ(|vi|)）を減算値D316としてLUT３１４に供給する。
【０５３６】
LUT３１４は、演算器３１２からの減算値D316（ｉ＝１からｉ＝ｄc−１までのΣφ(|vi|)）を引数として、逆関数φ-1（Σφ(|vi|)）の演算を行った演算結果D318（φ-1(Σφ(|vi|)))を出力する。
【０５３７】
以上の処理と並行して、EXOR回路３０６は、レジスタ３０７に格納されている値D310と符号ビットD304との排他的論理和を演算することにより、符号ビットどうしの乗算を行い、乗算結果D309を、レジスタ３０７に再格納する。なお、検査行列の1行に亘る全ての枝からのメッセージD801の符号ビットD304が乗算された場合、レジスタ３０７はリセットされる。
【０５３８】
検査行列の1行に亘る全ての枝からのメッセージD801の符号ビットD304が乗算された乗算結果D309（ｉ＝１からｄcまでのΠsign(vi)）がレジスタ３０７に格納された場合、セレクタ３０８は、レジスタ３０７に格納されている値、即ち、検査行列の１行に亘る全ての枝からのメッセージD801の符号ビットD304が乗算された値D310（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）を選択し、レジスタ３０９に出力して格納させる。レジスタ３０９は、格納している値D311を、セレクタ３０８とEXOR回路３１５に供給する。
【０５３９】
検査行列の1行に亘る全ての枝からのメッセージD801の符号ビットD304が乗算された乗算結果D309（ｉ＝１からｄcまでのΠsign(vi)）がレジスタ３０７に格納される直前までは、セレクタ３０８は、レジスタ３０９から供給された値D311を選択し、レジスタ３０９に出力して再格納させる。即ち、検査行列の１行に亘る全ての枝からのメッセージD801（メッセージvi）の符号ビットD304が乗算されるまで、レジスタ３０９は、前回格納した値を、セレクタ３０８とEXOR回路３１５に供給する。
【０５４０】
一方、レジスタ３０９から新たな値D311（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）がEXOR回路３１５に供給されたとき、即ち、レジスタ３０７に１行に亘る全ての枝からのメッセージD801の符号ビットD304が乗算された値D310（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）が格納されたとき、レジスタ３０５には、上述したように、1行分の演算結果D306(φ(|vi|))が積算された積算値（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）が格納される。
【０５４１】
レジスタ３０５に1行分の演算結果D306(φ(|vi|))が積算された積算値（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）が格納されると、上述したように、メッセージ計算部２３１において、メッセージメモリ１０４からの２回目のメッセージD801（vi）が、入力ポートP801から１つずつ入力され、その２回目のメッセージD801のD303絶対値(|vi|)が、LUT３００に供給され、２回目のメッセージD801の符号ビットが、符号ビットD313として、EXOR回路３１５に供給される（とともに、符号ビットD304として、EXOR回路３０６に供給される）。
【０５４２】
EXOR回路３１５は、レジスタ３０９から供給された値D311と、入力ポートP801からの２回目のメッセージD801の符号ビットD313との排他的論理和を演算することにより、値D311を、符号ビットD313で除算し、除算結果を除算値D319として出力する。即ち、EXOR回路３１５は、検査行列の１行に亘る全ての枝からのメッセージD801の符号ビットD304の乗算値（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）を、求めたい枝からのメッセージviの符号ビットD313（ｉ＝ｄcのsign(vi)）で除算して、その除算値（ｉ＝１からｉ＝ｄc−１までのΠsign(vi)）を除算値D319として出力する。
【０５４３】
そして、メッセージ計算部２３１では、LUT３１４から出力された演算結果D318を下位ビットとするとともに、EXOR回路３１５から出力された除算値D319を最上位ビット（符号ビット）とするビット列D320（メッセージuj）が、セレクタ３１６のc端子に供給される。
【０５４４】
セレクタ３１６は、チェックノード演算時にはc端子を選択しており、そのc端子に供給されるビット列D320（メッセージuj）を、メッセージD802（メッセージvi）として、出力ポートP802から出力する。
【０５４５】
以上のように、セレクタ３０１および３１６がc端子を選択しているメッセージ計算部２３１では、式（７）のチェックノード演算が行われ、その結果得られるメッセージ（チェックノードメッセージ）ujが、出力ポートP802から出力される。
【０５４６】
なお、図示しないが、図３６の復号装置では、復号の最終段において、式（１）のバリアブルノード演算の代わりに、式（５）の演算が行われ、その演算結果が、最終的な復号結果として出力される。
【０５４７】
また、図３６の復号装置において、制御部２３２は、メッセージメモリ１０４に対するメッセージ（データ）の読み書き制御として、図１５のフローチャートで説明したように、図１２の復号装置の制御部１７４と同様の読み書き制御を行う。
【０５４８】
但し、図３６の復号装置のメッセージメモリ１０４に対するメッセージの読み書きのタイミングは、メッセージ計算部２３１が、メッセージメモリ１０４からのメッセージを入力する入力ポートとして、１つの入力ポートP801しか有しないために、図１２の復号装置について説明した図１６の場合と異なる。
【０５４９】
即ち、図４０は、図３６の復号装置のメッセージメモリ１０４に対するメッセージの読み書きのタイミングを示すタイミングチャートである。
【０５５０】
図４０のタイミングチャートは、図１６のタイミングチャートと同様に、メッセージメモリ１０４を構成するRAM#AとRAM#Bのそれぞれに対する読み書きのタイミングを表している。
【０５５１】
図４０においては、まず最初に、あるノードnode#1からの出力メッセージを求めるのに必要な入力メッセージの、RAM#Aからの１回目の読み出しが行われる(R1(node#1))。その読み出しの終了後、ノードnode#1からの出力メッセージを求めるのに必要な入力メッセージの、RAM#Aからの２回目の読み出しが行われる(R2(node#1))。このとき、図１６では、次のノードnode#2からの出力メッセージを求めるのに必要な入力メッセージの、RAM#Bからの１回目の読み出しが行われる(R1(node#2))が、図３６の復号装置のメッセージ計算部２３１は、（メッセージメモリ１０４からのメッセージを入力する入力ポートとして）１つの入力ポートP801しか有しないため、図４０では、次のノードnode#2からの出力メッセージを求めるのに必要な入力メッセージの、RAM#Bからの１回目の読み出し(R1(node#2))は、まだ行われない。
【０５５２】
ノードnode#1からの出力メッセージを求めるのに必要な入力メッセージの、RAM#Aからの２回目の読み出しが終了し、メッセージ計算部２３１において、ノードnode#1からの出力メッセージが求められると、そのノードnode#1からの出力メッセージがRAM#Aに書き込まれる(W(node#1))のと同時に、ノードnode#2からの出力メッセージを求めるのに必要な入力メッセージの、RAM#Bからの１回目の読み出しが行われる(R1(node#2))。
【０５５３】
ノードnode#2からの出力メッセージを求めるのに必要な入力メッセージの、RAM#Bからの１回目の読み出しが終了すると、続けて、ノードnode#2からの出力メッセージを求めるのに必要な入力メッセージの、RAM#Bからの１回目の読み出しが行われ(R2(node#2))、メッセージ計算部２３１において、ノードnode#2からの出力メッセージが求められる、そして、ノードnode#2からの出力メッセージが求められると、そのノードnode#2からの出力メッセージがRAM#Bに書き込まれる(W(node#2))のと同時に、次のノードnode#3からの出力メッセージを求めるのに必要な入力メッセージの、RAM#Aからの１回目の読み出しが行われる(R1(node#3))。
【０５５４】
以下、同様にして、メッセージメモリ１０４を構成するRAM#AとRAM#Bのそれぞれに対するメッセージの読み書きが行われていく。
【０５５５】
図１６と図４０とを比較してわかるように、図３６の復号装置では、出力メッセージを求めるのに、図１６の場合よりも時間を要することになるが、それでも、遅延メモリなしで復号を行うことができるので、復号装置の規模を削減することができる。
【０５５６】
なお、メッセージ計算部２３１（図３７）のように、メッセージメモリ１０４からの入力メッセージが入力される入力ポートを１ポートとする構成は、図１２のメッセージ計算部１７１のバリアブルノード計算器１７２（図１３）およびチェックノード計算器１７３（図１４）や、図２２のメッセージ計算部２０１、図２７のメッセージ計算部２１１、図３２のメッセージ計算部２２１でも採用することが可能である。
【０５５７】
また、メッセージメモリ１０４は、RAM#AとRAM#Bとの２バンクで構成する他、３以上のRAMで３バンク以上に構成することも可能である。
【０５５８】
次に、制御部１７４（図１２）等が行う図１５に示したメッセージメモリ１０４に対する読み書き制御の処理は、専用のハードウェアにより行うこともできるし、ソフトウェアにより行うこともできる。一連の処理をソフトウェアによって行う場合には、そのソフトウェアを構成するプログラムが、マイクロコンピュータ（いわゆるマイコン）等のコンピュータにインストールされる。
【０５５９】
そこで、図４１は、上述した一連の処理を実行するプログラムがインストールされるコンピュータの一実施の形態の構成例を示している。
【０５６０】
プログラムは、コンピュータに内蔵されている記録媒体としての不揮発性メモリ９０５やＲＯＭ９０３に予め記録しておくことができる。
【０５６１】
あるいはまた、プログラムは、フレキシブルディスク、CD-ROM(Compact Disc Read Only Memory)，MO(Magneto Optical)ディスク，DVD(Digital Versatile Disc)、磁気ディスク、半導体メモリなどのリムーバブル記録媒体に、一時的あるいは永続的に格納（記録）しておくことができる。
【０５６２】
なお、プログラムは、上述したようなリムーバブル記録媒体９１１から、あるいはネットワークを経由してコンピュータにインストールすることができる。
【０５６３】
コンピュータは、CPU(Central Processing Unit)９０２を内蔵している。CPU９０２には、バス９０１を介して、入出力インタフェース９０６が接続されており、CPU９０２は、ROM(Read Only Memory)９０３や不揮発性メモリ９０５にインストールされたプログラムを、RAM(Random Access Memory)９０４にロードして実行する。これにより、CPU９０２は、入出力インタフェース９０６を介して、メッセージメモリ１０４に対する読み書き制御を行う。
【０５６４】
ここで、本明細書において、コンピュータに各種の処理を行わせるためのプログラムを記述する処理ステップは、必ずしもフローチャートとして記載された順序に沿って時系列に処理する必要はなく、並列的あるいは個別に実行される処理（例えば、並列処理あるいはオブジェクトによる処理）も含むものである。
【０５６５】
また、プログラムは、１のコンピュータにより処理されるものであっても良いし、複数のコンピュータによって分散処理されるものであっても良い。
【０５６６】
なお、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【図面の簡単な説明】
【０５６７】
【図１】LDPC符号の検査行列Hを説明する図である。
【図２】LDPC符号の復号手順を説明するフローチャートである。
【図３】メッセージの流れを説明する図である。
【図４】LDPC符号の検査行列の例を示す図である。
【図５】検査行列のタナーグラフを示す図である。
【図６】バリアブルノードを示す図である。
【図７】チェックノードを示す図である。
【図８】従来の復号装置の一例の構成を示すブロック図である。
【図９】メッセージを１つずつ計算するバリアブルノード計算器１０２の構成例を示すブロック図である。
【図１０】メッセージを１つずつ計算するチェックノード計算器１０３の構成例を示すブロック図である。
【図１１】メッセージメモリ１０４に対するメッセージの読み書きの従来のタイミングを示すタイミングチャートである。
【図１２】本発明を適用した復号装置の第１実施の形態の構成例を示すブロック図である。
【図１３】バリアブルノード計算器１７２の構成例を示すブロック図である。
【図１４】チェックノード計算器１７３の構成例を示すブロック図である。
【図１５】メッセージメモリ１０４に対する読み書き制御の処理を説明するフローチャートである。
【図１６】メッセージメモリ１０４に対するメッセージの読み書きのタイミングを示すタイミングチャートである。
【図１７】バリアブルノード演算を行う回路とチェックノード演算を行う回路との一部が共有化された復号装置の構成例を示すブロック図である。
【図１８】メッセージ計算部１９１の構成例を示すブロック図である。
【図１９】バリアブルノード演算時のメッセージ計算部１９１の実質的な構成を示すブロック図である。
【図２０】チェックノード演算時のメッセージ計算部１９１の実質的な構成を示すブロック図である。
【図２１】本発明を適用した復号装置の第２実施の形態の構成例を示すブロック図である。
【図２２】メッセージ計算部２０１の構成例を示すブロック図である。
【図２３】メッセージ計算部２０１が行うバリアブルノード演算とチェックノード演算を説明する図である。
【図２４】バリアブルノード演算時のメッセージ計算部２０１の実質的な構成を示すブロック図である。
【図２５】チェックノード演算時のメッセージ計算部２０１の実質的な構成を示すブロック図である。
【図２６】本発明を適用した復号装置の第３実施の形態の構成例を示すブロック図である。
【図２７】メッセージ計算部２１１の構成例を示すブロック図である。
【図２８】メッセージ計算部２１１が行うバリアブルノード演算とチェックノード演算を説明する図である。
【図２９】バリアブルノード演算時のメッセージ計算部２１１の実質的な構成を示すブロック図である。
【図３０】チェックノード演算時のメッセージ計算部２１１の実質的な構成を示すブロック図である。
【図３１】本発明を適用した復号装置の第４実施の形態の構成例を示すブロック図である。
【図３２】メッセージ計算部２２１の構成例を示すブロック図である。
【図３３】メッセージ計算部２２１が行うバリアブルノード演算とチェックノード演算を説明する図である。
【図３４】バリアブルノード演算時のメッセージ計算部２２１の実質的な構成を示すブロック図である。
【図３５】チェックノード演算時のメッセージ計算部２２１の実質的な構成を示すブロック図である。
【図３６】本発明を適用した復号装置の第５実施の形態の構成例を示すブロック図である。
【図３７】メッセージ計算部２３１の構成例を示すブロック図である。
【図３８】バリアブルノード演算時のメッセージ計算部２３１の実質的な構成を示すブロック図である。
【図３９】チェックノード演算時のメッセージ計算部２３１の実質的な構成を示すブロック図である。
【図４０】メッセージメモリ１０４に対するメッセージの読み書きのタイミングを示すタイミングチャートである。
【図４１】本発明を適用したコンピュータの一実施の形態の構成例を示すブロック図である。
【符号の説明】
【０５６８】
１０４  メッセージメモリ，  １０５  受信データメモリ，  １２１  LUT，  １２２  演算器，  １２３  レジスタ，  １２４  セレクタ，  １２５  レジスタ，  １２６  演算器，  １２８  LUT，  １２９  EXOR回路，  １３０  レジスタ，  １３１  セレクタ，  １３２  レジスタ，  １３４  EXOR回路，  １３５  LUT，  １５１  演算器，  １５２  レジスタ，  １５３  セレクタ，  １５４  レジスタ，  １５６，１５７  演算器，  １７１  メッセージ計算部，  １７２  バリアブルノード計算器，  １７３  チェックノード計算器，  １７４  制御部，  １９１  メッセージ計算部，  １９２  制御部，  ２０１  メッセージ計算部，  ２０２  制御部，  ２１１  メッセージ計算部，  ２１２  制御部，  ２２１  メッセージ計算部，  ２２２  制御部，  ２３１  メッセージ計算部，  ２３２  制御部，  ３００  LUT，  ３０１  セレクタ，  ３０２  演算器，  ３０３  レジスタ，  ３０４  セレクタ，  ３０５  レジスタ，  ３０６  EXOR回路，  ３０７  レジスタ，  ３０８  セレクタ，  ３０９  レジスタ，  ３１０  LUT，  ３１１  セレクタ，  ３１２，３１３  演算器，  ２１４  LUT，  ３１５  EXOR回路，  ３１６  セレクタ，  ３２０  FIFOメモリ，  ６００  LUT，  ６０１  セレクタ，  ６０２  演算器，  ６０３  レジスタ，  ６０４  セレクタ，  ６０５  レジスタ，  ６０６  EXOR回路，  ６０７  レジスタ，  ６０８  セレクタ，  ６０９  レジスタ，  ６１０  LUT，  ６１１  セレクタ，  ６１２，６１３  演算器，  ６１４  EXOR回路，  ６１５  セレクタ，  ７００  セレクタ，  ７０１  演算器，  ７０２  レジスタ，  ７０３  セレクタ，  ７０４  レジスタ，  ７０５  セレクタ，  ７０６  EXOR回路，  ７０７  レジスタ，  ７０８  セレクタ，  ７０９  レジスタ，  ７１０，７１１  演算器，  ７１２  セレクタ，  ７１３  LUT，  ７１４  EXOR回路，  ７１５  セレクタ，  ９０１  バス，  ９０２  CPU，  ９０３  ROM，  ９０４  RAM，  ９０５  不揮発性メモリ，  ９０６  入出力インタフェース
【図１】
0004807063.tif 000015
【図２】
0004807063.tif 000016
【図３】
0004807063.tif 000017
【図４】
0004807063.tif 000018
【図５】
0004807063.tif 000019
【図６】
0004807063.tif 000020
【図７】
0004807063.tif 000021
【図８】
0004807063.tif 000022
【図９】
0004807063.tif 000023
【図１０】
0004807063.tif 000024
【図１１】
0004807063.tif 000025
【図１２】
0004807063.tif 000026
【図１３】
0004807063.tif 000027
【図１４】
0004807063.tif 000028
【図１５】
0004807063.tif 000029
【図１６】
0004807063.tif 000030
【図１７】
0004807063.tif 000031
【図１８】
0004807063.tif 000032
【図１９】
0004807063.tif 000033
【図２０】
0004807063.tif 000034
【図２１】
0004807063.tif 000035
【図２２】
0004807063.tif 000036
【図２３】
0004807063.tif 000037
【図２４】
0004807063.tif 000038
【図２５】
0004807063.tif 000039
【図２６】
0004807063.tif 000040
【図２７】
0004807063.tif 000041
【図２８】
0004807063.tif 000042
【図２９】
0004807063.tif 000043
【図３０】
0004807063.tif 000044
【図３１】
0004807063.tif 000045
【図３２】
0004807063.tif 000046
【図３３】
0004807063.tif 000047
【図３４】
0004807063.tif 000048
【図３５】
0004807063.tif 000049
【図３６】
0004807063.tif 000050
【図３７】
0004807063.tif 000051
【図３８】
0004807063.tif 000052
【図３９】
0004807063.tif 000053
【図４０】
0004807063.tif 000054
【図４１】
0004807063.tif 000055