(57)【特許請求の範囲】
【請求項１】
LDPC(Low Density Parity Check)符号を復号する復号装置であって、
間欠的に入力される前記LDPC符号の受信値を一時的に記憶し、記憶している前記受信値を連続的に読み出す第１の記憶手段と、
前記第１の記憶手段により連続的に読み出される受信値を記憶し、記憶している前記受信値を所定の単位ごとに読み出す第２の記憶手段と、
前記第２の記憶手段により所定の単位ごとに読み出された受信値を、前記所定の単位ごとに復号する復号手段と、
前記受信値が前記第１の記憶手段から読み出され、前記第２の記憶手段に記憶される間である転送期間に間欠的に入力される前記受信値を一時的に記憶し、記憶している前記受信値を読み出す第３の記憶手段と
を備え、
前記第１の記憶手段は、前記第３の記憶手段により読み出される前記受信値と、前記転送期間以外に間欠的に入力される前記受信値を一時的に記憶し、
前記第２の記憶手段は、さらに、前記復号の途中結果を記憶し、記憶している前記復号の途中結果を前記所定の単位ごとに読み出して前記復号手段に出力し、
前記第１の記憶手段のビット幅は、前記第２の記憶手段のビット幅より小さい
復号装置。
【請求項２】
前記第２の記憶手段は、
前記第１の記憶手段により連続的に読み出される受信値を記憶する受信値記憶手段と、
前記復号の途中結果を記憶する途中結果記憶手段と
を備え、
前記受信値記憶手段と前記途中結果記憶手段は、ワード方向に接続される
請求項１に記載の復号装置。
【請求項３】
間欠的に入力されるLDPC符号の受信値を一時的に記憶する第１の記憶手段と、前記第１の記憶手段により連続的に読み出される受信値を記憶する第２の記憶手段と、前記第２の記憶手段により所定の単位ごとに読み出された受信値を、前記所定の単位ごとに復号する復号手段と、前記受信値が前記第１の記憶手段から読み出され、前記第２の記憶手段に記憶される間である転送期間に間欠的に入力される前記受信値を一時的に記憶する第３の記憶手段とを備え、前記LDPC符号を復号する復号装置の復号方法であって、
前記第３の記憶手段が、前記転送期間に間欠的に入力される前記受信値を一時的に記憶し、
前記第３の記憶手段が、記憶している前記受信値を読み出し、
前記第２の記憶手段よりビット幅が小さい前記第１の記憶手段が、前記第３の記憶手段により読み出される前記受信値と、前記転送期間以外に間欠的に入力される前記受信値を一時的に記憶し、
前記第１の記憶手段が、記憶している前記受信値を連続的に読み出し、
前記第２の記憶手段が、前記第１の記憶手段により連続的に読み出される受信値を記憶し、
前記第２の記憶手段が、記憶している前記受信値を前記所定の単位ごとに読み出し、
前記復号手段が、前記第２の記憶手段により所定の単位ごとに読み出された受信値を、前記所定の単位ごとに復号し、
前記第２の記憶手段が、前記復号の途中結果を記憶し、
前記第２の記憶手段が、記憶している前記復号の途中結果を前記所定の単位ごとに読み出して前記復号手段に出力する
ステップを含む復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、復号装置および復号方法に関し、特に、低密度パリティ検査符号（LDPC符号）を復号する場合において、復号性能を劣化させずに、回路規模を削減することができるようにした復号装置および復号方法に関する。
【背景技術】
【０００２】
近年、例えば、移動体通信や深宇宙通信といった通信分野、及び地上波又は衛星ディジタル放送といった放送分野の研究が著しく進められているが、それに伴い、誤り訂正符号化及び復号の効率化を目的として符号理論に関する研究も盛んに行われている。
【０００３】
符号性能の理論的限界としては、いわゆるシャノン(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による非特許文献１において最初に提案されたものであり、その後、非特許文献２等において再注目されるに至ったものである。
【０００５】
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符号化されたLDPC符号を受信値U0とし、チェックノードから出力されるメッセージをujとし、バリアブルノードから出力されるメッセージをviとする。メッセージとは、値の"0"らしさを、いわゆる対数尤度比(log likelihood ratio)で表現した実数値である。また、ここでは、受信値U0の"0"らしさの対数尤度比を、受信値u0iと表すこととする。
【００１３】
まず、LDPC符号の復号においては、図２に示すように、ステップＳ１１において、受信値U0(受信値u0i)が受信され、メッセージujが"0"に初期化されるとともに、繰り返し処理のカウンタとしての整数をとる変数kが"0"に初期化される。ステップＳ１２において、受信値u0iに基づいて、式（１）に示す演算を行うことによってメッセージviが求められ、さらに、このメッセージviに基づいて、式（２）に示す演算を行うことによってメッセージujが求められる。
【００１４】
【数１】
0004821724.tif 000002
・・・（１）
【００１５】
【数２】
0004821724.tif 000003
・・・（２）
【００１６】
なお、式（１）と式（２）におけるdvとdcは、それぞれ、検査行列Hの縦方向（行方向）と横方向（列方向）の"1"の個数を示す任意に選択可能とされるパラメータであり、例えば、(3,6)符号の場合には、dv=3，dc=6となる。
【００１７】
また、式（１）または（２）の演算においては、それぞれ、メッセージを出力しようとする枝(edge)から入力されたメッセージを、和または積演算のパラメータとしては用いないことから、和または積演算の範囲が、１乃至dv-1または１乃至dc-1となっている。さらに、式（２）に示す演算は、実際には、２入力v1，v2に対する１出力で定義される式（３）に示す関数R(v1,v2)のテーブルを予め作成しておき、これを式（４）に示すように連続的（再帰的）に用いることによって行われる。
【００１８】
【数３】
0004821724.tif 000004
・・・（３）
【００１９】
【数４】
0004821724.tif 000005
・・・（４）
【００２０】
ステップＳ１２では、さらに、変数kが"1"だけインクリメントされる。ステップＳ１３では、変数kが所定の繰り返し復号回数N以上であるか否かが判定される。ステップＳ１３において、変数kがN以上ではないと判定された場合、処理はステップＳ１２に戻り、以下、同様の処理が繰り返される。
【００２１】
一方、ステップＳ１３において、変数kがN以上であると判定された場合、ステップＳ１４において、式（５）に示す演算を行うことによって、最終的に出力する復号結果としてのメッセージvが求められて出力され、LDPC符号の復号処理が終了する。
【００２２】
【数５】
0004821724.tif 000006
・・・（５）
【００２３】
なお、式（５）の演算は、式（１）の演算とは異なり、バリアブルノードに接続している全ての枝からの入力メッセージを用いて行われる。
【００２４】
このようなLDPC符号の復号では、例えば(3,6)符号の場合には、図３に示すように、各ノード間でメッセージの授受が行われる。なお、図３における"="で示すノード（バリアブルノード）では、式（１）に示した演算が行われ、"+"で示すノード（チェックノード）では、式（２）に示した演算が行われる。特に、アルゴリズムＡにおいては、メッセージを２元化し、"+"で示すノードにて、dc-1個の入力メッセージの排他的論理和演算を行い、"="で示すノードにて、受信値Rに対して、dv-1個の入力メッセージが全て異なるビット値であった場合には、符号を反転して出力する。
【００２５】
また、一方で、近年、LDPC符号の復号の実装方法に関する研究も行われている。実装方法について述べる前に、まず、LDPC符号の復号を模式化して説明する。
【００２６】
図４は、(3,6)LDPC符号（符号化率1/2、符号長12）の検査行列(parity check matrix)Hの例である。LDPC符号の検査行列Hは、図５のように、タナーグラフを用いて書き表すことができる。なお、図５において、"+"で表わされるのが、チェックノードであり、"="で表わされるのが、バリアブルノードである。チェックノードとバリアブルノードは、それぞれ、検査行列Hの行と列に対応する。チェックノードとバリアブルノードとの間の結線は、枝(edge)であり、検査行列Hの"1"に相当する。即ち、検査行列Hの第ｊ行第ｉ列のコンポーネントが１である場合には、図５において、上からｉ番目のバリアブルノード（"="のノード）と、上からｊ番目のチェックノード（"+"のノード）とが、枝により接続される。枝は、バリアブルノードに対応する符号ビットが、チェックノードに対応する拘束条件を持つことを表わす。なお、図５は、図４の検査行列Hのタナーグラフとなっている。
【００２７】
確率伝播（Belief Propagation）、サムプロダクトアルゴリズム(Sum Product Algorithm)等と呼ばれるLDPC符号の復号方法は、バリアブルノードの演算とチェックノードの演算とを繰り返し行う。
【００２８】
バリアブルノードでは、図６のように、式（１）の演算を行う。すなわち、図６において、計算しようとしている枝に対応するメッセージviは、バリアブルノードに繋がっている残りの枝からのメッセージu1およびu2と、受信情報u0iを用いて計算される。他の枝に対応するメッセージも同様に計算される。
【００２９】
チェックノードの演算について説明する前に、式（２）を、式a×b=exp{ln(|a|)+ln(|b|)}×sign(a)×sign(b)の関係を用いて、式（６）のように書き直す。但し、sign(x)は、x≧0のとき1であり、x＜0のとき-1である。
【００３０】
【数６】
0004821724.tif 000007
・・・（６）
【００３１】
更に、x≧0において、非線形関数φ(x)=−ln(tanh(x/2))と定義すると、φ-1(x)=2tanh-1(e-x)であるから、式（６）は、式（７）のように書くことができる。
【００３２】
【数７】
0004821724.tif 000008
・・・（７）
【００３３】
チェックノードでは、図７のように、式（７）の演算を行う。すなわち、図７において、計算しようとしている枝に対応するメッセージ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となる。
【００３５】
サムプロダクトアルゴリズムをハードウェアに実装する場合、式（１）で表わされるバリアブルノード演算および式（７）で表わされるチェックノード演算を、適度な回路規模と動作周波数で繰り返し行うことが必要である。
【００３６】
なお、バリアブルノードで行われる式（１）に示した演算は、上述した式（５）と以下の式（８）を組み合わせたものとして考えることができる。
【００３７】
【数８】
0004821724.tif 000009
・・・（８）
【００３８】
即ち、上述した式（１）にしたがうバリアブルノード演算と式（７）にしたがうチェックノード演算とを行うのではなく、上述した式（７）と式（８）にしたがう第１の演算と、上述した式（５）にしたがう第２の演算とを行うことにより、LDPC符号を復号することもできる。
【００３９】
復号装置の実装の例としては、各ノードの演算を１つずつ順次行うことによって復号を行う復号装置(full serial decoder)、全ノードの演算を同時に行うことによって復号を行う復号装置(full parallel decoder)、１つでも全てでもなく、いくつかのノードの演算を同時に行うことによって復号を行う復号装置（party parallel decoder）などがある。
【００４０】
このうち、いくつかのノードの演算を同時に行うことによって復号を行う復号装置（party parallel decoder）は、メモリの異なるアドレスからの同時読み出し、もしくは同時書き込みを避けることが一般的には容易でなく、メモリアクセス制御が困難であるという問題がある。
【００４１】
しかしながら、Ｐ×Ｐの単位行列、その単位行列の１のうち１個以上が０になった行列（以下、適宜、準単位行列という）、単位行列または準単位行列をサイクリックシフト(cyclic shift)した行列（以下、適宜、シフト行列という）、単位行列、準単位行列、またはシフト行列のうちの２以上(複数)の和（以下、適宜、和行列という）、Ｐ×Ｐの０行列の組み合わせで表すことが可能な検査行列Hを有するLDPC符号、もしくは行や列の置換により、これらの行列の組み合わせで表すことが可能な検査行列Hを有するLDPC符号の場合、チェックノード演算とバリアブルノード演算をＰ個ずつ同時に行う復号装置が実現可能であることが知られている。
【００４２】
図８は、チェックノード演算とバリアブルノード演算をＰ個ずつ同時に行う復号装置の構成例を示している。
【００４３】
図８の復号装置１０では、動作クロックの１クロック(clock)ごとに、Ｐ個の枝に対応するメッセージが計算される。
【００４４】
即ち、図８の復号装置１０は、メッセージ計算部１１、メッセージメモリ１２、受信用メモリ１３、および制御部１４からなる。
【００４５】
図８の復号装置１０では、メッセージメモリ１２からメッセージ計算部１１に、入力メッセージがＰ個ずつ読み出され、メッセージ計算部１１において、各入力メッセージを用いて、所望のＰ個の枝に対応するＰ個の出力メッセージが計算される。そして、その計算によって求められたＰ個の出力メッセージが、メッセージメモリ１２に格納されていく。図８の復号装置１０では、以上の処理が繰り返し行われ、いわゆる繰り返し復号が行われる。
【００４６】
即ち、受信用メモリ１３には、通信路を介して送信されてきたLDPC符号を受信することにより得られる、符号の0（または1）らしさを表す対数尤度比である受信値D10が間欠的に供給され、受信用メモリ１３は、その受信値D10を格納する。
【００４７】
具体的には、受信用メモリ１３は、２つのスイッチ２０および２３と、２つの受信値メモリ２１および２２により構成される。スイッチ２０は、制御部１４から供給される制御信号D18にしたがって、１フレームごとに、受信値D10を受信値メモリ２１または受信値メモリ２２に交互に供給する。
【００４８】
受信値メモリ２１と２２は、１フレーム分の受信値D10を格納可能であり、Ｐ個の受信値D10を同時に読み書き可能なRAM（Random Access Memory）により構成される。受信値メモリ２１には、スイッチ２０から１フレーム分の受信値D10が受信値D11として供給され、受信値メモリ２１は、１フレーム分の受信値D11を格納する。また、受信値メモリ２１は、既に格納してある１フレーム分の受信値D11を、Ｐ個ずつ受信値D13として読み出し、スイッチ２３に供給する。
【００４９】
受信値メモリ２２には、スイッチ２０から１フレーム分の受信値D10が受信値D12として供給され、受信値メモリ２２は、１フレーム分の受信値D12を格納する。また、受信値メモリ２２は、既に格納してある１フレーム分の受信値D12を、Ｐ個ずつ受信値D14として読み出し、スイッチ２３に供給する。
【００５０】
スイッチ２３は、制御部１４から供給される制御信号D18にしたがって、バリアブルノード演算時に、Ｐ個の受信値D13または受信値D14を、Ｐ個の受信値D15としてメッセージ計算部１１に供給する。
【００５１】
また、バリアブルノード演算時には、メッセージメモリ１２は、制御部１４から供給される制御信号D20にしたがって、記憶しているＰ個のメッセージD16を読み出し、メッセージ計算部１１に供給する。なお、メッセージメモリ１２は、検査行列Hの１の数（全枝数）分のメッセージD17を格納可能であり、Ｐ個のメッセージD17を同時に読み書き可能なRAMにより構成される。さらに、バリアブルノード演算時には、制御部１４は、制御信号D19として、バリアブルノード演算を指示する制御信号を、メッセージ計算部１１に供給する。
【００５２】
メッセージ計算部１１は、Ｐ個のメッセージ計算器１１1乃至１１Pにより構成される。各メッセージ計算器１１1乃至１１Pは、メッセージメモリ１２から供給されるＰ個のメッセージD16と、受信用メモリ１３のスイッチ２３から供給されるＰ個の受信値D15を１つずつ用いて、制御部１４からの制御信号D19にしたがって、式（１）のバリアブルノード演算を行い、そのバリアブルノード演算の結果得られたＰ個の出力メッセージ（バリアブルノードメッセージ）viを、Ｐ個のメッセージD17として、メッセージメモリ１２に供給する。
【００５３】
そして、メッセージメモリ１２は、制御部１４から供給される制御信号D20にしたがって、以上のようにしてメッセージ計算部１１から供給されるＰ個のメッセージD17を記憶する。
【００５４】
一方、チェックノード演算時には、メッセージメモリ１２は、制御部１４から供給される制御信号D20にしたがって、記憶しているＰ個のバリアブルノードメッセージviを、Ｐ個のメッセージD16として読み出し、メッセージ計算部１１に供給する。さらに、チェックノード演算時には、制御部１４は、制御信号D19として、チェックノード演算を指示する制御信号を、メッセージ計算部１１に供給する。
【００５５】
メッセージ計算部１１の各メッセージ計算器１１1乃至１１Pは、メッセージメモリ１２から供給されるＰ個のメッセージD16の１つを用いて、制御部１４からの制御信号D19にしたがって、式（７）のチェックノード演算を行い、そのチェックノード演算によって求められたＰ個の出力メッセージ（チェックノードメッセージ）ujを、Ｐ個のメッセージD17として、メッセージメモリ１２に供給する。そして、メッセージメモリ１２は、制御部１４から供給される制御信号D20にしたがって、以上のようにしてメッセージ計算部１１から供給されるＰ個のメッセージD17を記憶する。
【００５６】
メッセージメモリ１２が記憶した、メッセージ計算部１１から６個ずつ供給されたチェックノードメッセージujとしてのメッセージD17は、次のバリアブルノード演算時に、メッセージD16として読み出され、メッセージ計算部１１に供給される。
【００５７】
次に、図９は、図８の受信値メモリ２１および２２、並びにメッセージメモリ１２に対する読み書きのタイミングを示すタイミングチャートである。
【００５８】
図９においては、まず最初に、時間Ａの間、あるフレームであるフレーム＃１の受信値D11が、受信値メモリ２１に書き込まれる(フレーム＃１入力)。その書き込みの終了後、時間Ｂの間、フレーム＃１の受信値D11が、受信値D13として、受信値メモリ２１からＰ個ずつ読み出され、その読み出されたフレーム＃１の受信値D13が受信値D15として復号される（フレーム＃１復号）。即ち、時間Ｂの間、Ｐ個の受信値D15と、メッセージメモリ１２から読み出されるＰ個のメッセージD16を１つずつ用いて、バリアブルノード演算とチェックノード演算がＰ個単位で繰り返し行われ、これらの演算の結果得られるメッセージD17が、メッセージメモリ１２に書き込まれる。
【００５９】
また、時間Ｂの間、フレーム＃１の次のフレームであるフレーム＃２の受信値D12が、受信値メモリ２２に書き込まれる（フレーム＃２入力）。その書き込みの終了後、時間Ｃの間、フレーム＃２の受信値D12が、受信値D14として、受信値メモリ２２から読み出され、その読み出されたフレーム＃２の受信値D14が、受信値D15として復号される（フレーム＃２復号）。これにより、時間Ｃの間、メッセージメモリ１２には、フレーム＃２の受信値D15の復号におけるメッセージD17が書き込まれる。
【００６０】
その書き込みの終了後、時間Ｃの間、フレーム＃２の次のフレームであるフレーム＃３の受信値D11が、受信値メモリ２１に書き込まれる（フレーム＃３入力）。以下、同様にして、受信値メモリ２１および２２、並びにメッセージメモリ１２のそれぞれに対する読み書きが行われていく。
【００６１】
次に、図１０は、式（１）のバリアブルノード演算時における、受信用メモリ１３とメッセージメモリ１２に対する読み書きのタイミングを示すタイミングチャートである。なお、図１０では、ノード次数(node degree)が９であるものとする。
【００６２】
図１０においては、まず最初に、あるフレームの受信値D15（u0i）がＰ個ずつ受信用メモリ１３から読み出されるとともに、Ｐ個のチェックノードメッセージｕ0としてのメッセージD16が、メッセージメモリ１２から同時に読み出される。その読み出しの終了後、Ｐ個のチェックノードメッセージｕ1としてのメッセージD16が、メッセージメモリ１２から同時に読み出される。以下、同様にして、Ｐ個の各チェックノードメッセージｕ2乃至ｕ8としてのメッセージD16が、Ｐ個単位で順にメッセージメモリ１２から同時に読み出される。
【００６３】
そして、メッセージ計算器１１1乃至１１Pは、それぞれ、受信用メモリ１３から読み出されたＰ個の受信値D15（u0i）の１つと、メッセージメモリ１２から読み出されたＰ個のチェックノードメッセージｕ0乃至ｕ8としてのメッセージD16の１つとを用いて、チェックノード演算を行う。なお、メッセージ計算器１１1乃至１１Pは、それぞれ、チェックノードメッセージｕ0乃至ｕ8を積算するので、メッセージ計算器１１1乃至１１Pでは、ノード次数分、即ち9クロック分以上の遅延が生じる。図１０の例では、12クロック分の遅延が生じている。
【００６４】
従って、Ｐ個のチェックノードメッセージｕ0としてのメッセージD16が読み出されてから、12クロック後には、メッセージD16と受信値D15を用いたバリアブルノード演算の結果得られる、Ｐ個のバリアブルノードメッセージv0としてのメッセージD17が、メッセージメモリ１２に書き込まれる。以下、同様にして、Ｐ個のバリアブルノードメッセージv1乃至v8としてのメッセージD17が、Ｐ個単位で順にメッセージメモリ１２に書き込まれる。
【００６５】
なお、図示は省略するが、式（７）のチェックノード演算や、式（５）に示す演算における読み書きのタイミングも、同様のタイミングでＰ個ずつ行われる。
【００６６】
【非特許文献１】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
【発明の開示】
【発明が解決しようとする課題】
【００６７】
上述した復号装置１０では、復号をＰ個ずつ並列に行うので、メッセージメモリ１２と、受信用メモリ１３を構成する受信値メモリ２１および２２とからは、それぞれ、Ｐ個のメッセージD16または受信値D15を同時に読み出す必要がある。従って、メッセージメモリ１２、並びに受信値メモリ２１および２２のそれぞれに必要なビット幅は、Ｐ×ｍビット（ｍは受信値およびメッセージの量子化ビット数）であり、Ｐが大きい場合、メッセージメモリ１２、並びに受信値メモリ２１および２２に必要なビット幅は大きくなる。
【００６８】
ところで、物理的なRAMマクロのビット幅は、高々数百ビット程度しかないため、数千ビット幅のメッセージメモリ１２、並びに受信値メモリ２１および２２は、それぞれ、このRAMマクロを複数個組み合わせて実現することになる。そして、RAMマクロには、指定されたアドレスに読み書きを行うための制御回路が内蔵されているため、使用するRAMマクロの個数が多くなればなるほど、メッセージメモリ１２、並びに受信値メモリ２１および２２の回路規模は増大する。
【００６９】
例えば、LDPC符号の量子化ビット数が5ビットであり、Ｐが360であるとき、メッセージメモリ１２、並びに受信値メモリ２１および２２に必要なビット幅は、それぞれ、1800(=360×5)ビットとなる。従って、RAMマクロのビット幅の上限が120ビットであるとすると、受信用メモリ１３とメッセージメモリ１２を構成するRAMマクロの総数は、45(=1800/120×3)個となる。このように、RAMマクロの総数が多い場合、メッセージメモリ１２、並びに受信値メモリ２１および２２の回路規模が増大し、これにより、復号装置１０の回路規模が増大する。
【００７０】
なお、受信値やメッセージの量子化ビット数を少なくすることにより、RAMマクロの個数を減らすことができるが、復号性能は劣化する。
【００７１】
本発明は、このような状況に鑑みてなされたものであり、LDPC符号を復号する場合において、復号性能を劣化させずに、回路規模を削減することができるようにするものである。
【課題を解決するための手段】
【００７２】
本発明の一側面の復号装置は、LDPC(Low Density Parity Check)符号を復号する復号装置であって、間欠的に入力される前記LDPC符号の受信値を一時的に記憶し、記憶している前記受信値を連続的に読み出す第１の記憶手段と、前記第１の記憶手段により連続的に読み出される受信値を記憶し、記憶している前記受信値を所定の単位ごとに読み出す第２の記憶手段と、前記第２の記憶手段により所定の単位ごとに読み出された受信値を、前記所定の単位ごとに復号する復号手段と、前記受信値が前記第１の記憶手段から読み出され、前記第２の記憶手段に記憶される間である転送期間に間欠的に入力される前記受信値を一時的に記憶し、記憶している前記受信値を読み出す第３の記憶手段とを備え、前記第１の記憶手段は、前記第３の記憶手段により読み出される前記受信値と、前記転送期間以外に間欠的に入力される前記受信値を一時的に記憶し、前記第２の記憶手段は、さらに、前記復号の途中結果を記憶し、記憶している前記復号の途中結果を前記所定の単位ごとに読み出して前記復号手段に出力し、前記第１の記憶手段のビット幅は、前記第２の記憶手段のビット幅より小さい。
【００７３】
本発明の一側面の復号装置においては、前記第２の記憶手段は、前記第１の記憶手段により連続的に読み出される受信値を記憶する受信値記憶手段と、前記復号の途中結果を記憶する途中結果記憶手段とを備え、前記受信値記憶手段と前記途中結果記憶手段は、ワード方向に接続されることができる。
【００７４】
本発明の一側面の復号方法は、間欠的に入力されるLDPC符号の受信値を一時的に記憶する第１の記憶手段と、前記第１の記憶手段により連続的に読み出される受信値を記憶する第２の記憶手段と、前記第２の記憶手段により所定の単位ごとに読み出された受信値を、前記所定の単位ごとに復号する復号手段と、前記受信値が前記第１の記憶手段から読み出され、前記第２の記憶手段に記憶される間である転送期間に間欠的に入力される前記受信値を一時的に記憶する第３の記憶手段とを備え、前記LDPC符号を復号する復号装置の復号方法であって、前記第３の記憶手段が、前記転送期間に間欠的に入力される前記受信値を一時的に記憶し、前記第３の記憶手段が、記憶している前記受信値を読み出し、前記第２の記憶手段よりビット幅が小さい前記第１の記憶手段が、前記第３の記憶手段により読み出される前記受信値と、前記転送期間以外に間欠的に入力される前記受信値を一時的に記憶し、前記第１の記憶手段が、記憶している前記受信値を連続的に読み出し、前記第２の記憶手段が、前記第１の記憶手段により連続的に読み出される受信値を記憶し、前記第２の記憶手段が、記憶している前記受信値を前記所定の単位ごとに読み出し、前記復号手段が、前記第２の記憶手段により所定の単位ごとに読み出された受信値を、前記所定の単位ごとに復号し、前記第２の記憶手段が、前記復号の途中結果を記憶し、前記第２の記憶手段が、記憶している前記復号の途中結果を前記所定の単位ごとに読み出して前記復号手段に出力するステップを含む。
【００７５】
本発明の一側面においては、第３の記憶手段が、間欠的に入力されるLDPC符号の受信値が第１の記憶手段から読み出され、第２の記憶手段に記憶される間である転送期間に間欠的に入力される受信値を一時的に記憶し、第３の記憶手段が、記憶している受信値を読み出し、第２の記憶手段よりビット幅が小さい第１の記憶手段が、第３の記憶手段により読み出される受信値と、転送期間以外に間欠的に入力される受信値を一時的に記憶し、第１の記憶手段が、記憶している受信値を連続的に読み出し、第２の記憶手段が、第１の記憶手段により連続的に読み出される受信値を記憶し、第２の記憶手段が、記憶している受信値を所定の単位ごとに読み出し、復号手段が、第２の記憶手段により所定の単位ごとに読み出された受信値を、所定の単位ごとに復号し、第２の記憶手段が、復号の途中結果を記憶し、第２の記憶手段が、記憶している復号の途中結果を所定の単位ごとに読み出して復号手段に出力する。
【発明の効果】
【００７６】
以上のように、本発明の一側面によれば、LDPC符号を復号する場合において、復号性能を劣化させずに、回路規模を削減することができる。
【発明を実施するための最良の形態】
【００７７】
以下に本発明の実施の形態を説明するが、請求項に記載の構成要件と、発明の実施の形態における具体例との対応関係を例示すると、次のようになる。この記載は、請求項に記載されている発明をサポートする具体例が、発明の実施の形態に記載されていることを確認するためのものである。従って、発明の実施の形態中には記載されているが、構成要件に対応するものとして、ここには記載されていない具体例があったとしても、そのことは、その具体例が、その構成要件に対応するものではないことを意味するものではない。逆に、具体例が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その具体例が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。
【００７８】
さらに、この記載は、発明の実施の形態に記載されている具体例に対応する発明が、請求項に全て記載されていることを意味するものではない。換言すれば、この記載は、発明の実施の形態に記載されている具体例に対応する発明であって、この出願の請求項には記載されていない発明の存在、すなわち、将来、分割出願されたり、補正により追加される発明の存在を否定するものではない。
【００７９】
本発明の一側面の復号装置は、
LDPC(Low Density Parity Check)符号を復号する復号装置（例えば、図１１の復号装置１００）であって、
間欠的に入力される前記LDPC符号の受信値を一時的に記憶し、記憶している前記受信値を連続的に読み出す第１の記憶手段（例えば、図１３の入力バッファ５１３）と、
前記第１の記憶手段により連続的に読み出される受信値を記憶し、記憶している前記受信値を所定の単位ごとに読み出す第２の記憶手段（例えば、図１３の連結メモリ５１４）と、
前記第２の記憶手段により所定の単位ごとに読み出された受信値を、前記所定の単位ごとに復号する復号手段（例えば、図１１のメッセージ計算部１０２）と、
前記受信値が前記第１の記憶手段から読み出され、前記第２の記憶手段に記憶される間である転送期間に間欠的に入力される前記受信値を一時的に記憶し、記憶している前記受信値を読み出す第３の記憶手段と
を備え、
前記第１の記憶手段は、前記第３の記憶手段により読み出される前記受信値と、前記転送期間以外に間欠的に入力される前記受信値を一時的に記憶し、
前記第２の記憶手段は、さらに、前記復号の途中結果を記憶し、記憶している前記復号の途中結果を前記所定の単位ごとに読み出して前記復号手段に出力し、
前記第１の記憶手段のビット幅は、前記第２の記憶手段のビット幅より小さい。
【００８０】
本発明の一側面の復号装置において、
前記第２の記憶手段は、
前記第１の記憶手段により連続的に読み出される受信値を記憶する受信値記憶手段（例えば、図１３の受信値メモリ６０１）と、
前記復号の途中結果を記憶する途中結果記憶手段（例えば、図１３のメッセージメモリ６０２）と
を備え、
前記受信値記憶手段と前記途中結果記憶手段は、ワード方向に接続される。
【００８１】
本発明の一側面の復号方法は、
間欠的に入力されるLDPC符号の受信値を一時的に記憶する第１の記憶手段（例えば、図１３の入力バッファ５１３）と、前記第１の記憶手段により連続的に読み出される受信値を記憶する第２の記憶手段（例えば、図１３の連結メモリ５１４）と、前記第２の記憶手段により所定の単位ごとに読み出された受信値を、前記所定の単位ごとに復号する復号手段(例えば、図１１のメッセージ計算部１０２)と、前記受信値が前記第１の記憶手段から読み出され、前記第２の記憶手段に記憶される間である転送期間に間欠的に入力される前記受信値を一時的に記憶する第３の記憶手段とを備え、前記LDPC符号を復号する復号装置（例えば、図１１の復号装置１００）の復号方法であって、
前記第３の記憶手段が、前記転送期間に間欠的に入力される前記受信値を一時的に記憶し、
前記第３の記憶手段が、記憶している前記受信値を読み出し、
前記第２の記憶手段よりビット幅が小さい前記第１の記憶手段が、前記第３の記憶手段により読み出される前記受信値と、前記転送期間以外に間欠的に入力される前記受信値を一時的に記憶し（例えば、図１６のステップＳ２５）、
前記第１の記憶手段が、記憶している前記受信値を連続的に読み出し（例えば、図１７のステップＳ３２）、
前記第２の記憶手段が、前記第１の記憶手段により連続的に読み出される受信値を記憶し（例えば、図１７のステップＳ３３）、
前記第２の記憶手段が、記憶している前記受信値を前記所定の単位ごとに読み出し、
前記復号手段が、前記第２の記憶手段により所定の単位ごとに読み出された受信値を、前記所定の単位ごとに復号し(例えば、図１８の復号処理)、
前記第２の記憶手段が、前記復号の途中結果を記憶し（例えば、図１７のステップＳ３９またはＳ４１）、
前記第２の記憶手段が、記憶している前記復号の途中結果を前記所定の単位ごとに読み出して前記復号手段に出力する（例えば、図１７のステップＳ３８またはＳ４０）
ステップを含む。
【００８２】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。
【００８３】
図１１は、本発明を適用した復号装置の一実施の形態の構成例を示している。
【００８４】
なお、ここでは、Ｐ×Ｐの単位行列、準単位行列、単位行列と準単位行列の和、Ｐ×Ｐの０行列の組み合わせで表すことが可能な検査行列Hを有するLDPC符号、もしくは行や列の置換により、これらの行列の組み合わせで表すことが可能な検査行列Hを有するLDPC符号を復号することとする。
【００８５】
図１１の復号装置１００は、メモリ１０１、メッセージ計算部１０２、および制御部１０３により構成される。なお、図８と同一のものには同一の符号を付してあり、説明は繰り返しになるので、適宜省略する。
【００８６】
図１１の復号装置１００では、メモリ１０１からメッセージ計算部１０２に、入力メッセージがＰ個ずつ読み出され、メッセージ計算部１０２において、各入力メッセージを用いて、所望のＰ個の枝に対応するＰ個の出力メッセージが計算される。そして、その計算によって求められたＰ個の出力メッセージが、メモリ１０１に格納されていく。図１１の復号装置１００では、以上の処理が繰り返し行われ、いわゆる繰り返し復号が行われる。
【００８７】
即ち、メモリ１０１には、通信路を介して送信されてきたLDPC符号を受信することにより得られる、符号の0（または1）らしさを表す対数尤度比である受信値D10が間欠的に供給され、メモリ１０１は、その受信値D10を格納する。
【００８８】
バリアブルノード演算時には、メモリ１０１は、制御部１０３から供給されるアドレスを表す制御信号D103にしたがって、記憶しているＰ個の受信値D10を読み出し、Ｐ個の値D101として、メッセージ計算部１０２に供給する。
【００８９】
また、バリアブルノード演算時には、メモリ１０１は、制御部１０３から供給される制御信号D103にしたがって、記憶しているＰ個のメッセージD17をＰ個の値D101として読み出し、メッセージ計算部１０２に供給する。なお、メモリ１０１の詳細については、後述する図１３を参照して説明する。さらに、バリアブルノード演算時には、制御部１０３は、制御信号D19として、バリアブルノード演算を指示する制御信号を、メッセージ計算部１０２に供給する。
【００９０】
メッセージ計算部１０２の各メッセージ計算器１０２1乃至１０２Pは、メモリ１０１から値D101として供給されるＰ個のメッセージとＰ個の受信値を１つずつ用いて、制御部１０３からの制御信号D19にしたがって、式（１）のバリアブルノード演算を行い、そのバリアブルノード演算の結果得られた復号の途中結果であるＰ個の出力メッセージ（バリアブルノードメッセージ）viを、Ｐ個のメッセージD17として、メモリ１０１に供給する。
【００９１】
そして、メモリ１０１は、制御部１０３から供給される制御信号D103にしたがって、以上のようにしてメッセージ計算部１０２から供給されるＰ個のメッセージD17を記憶する。
【００９２】
一方、チェックノード演算時には、メモリ１０１は、制御部１０３から供給される制御信号D103にしたがって、記憶しているＰ個のバリアブルノードメッセージviを、Ｐ個の値D101として読み出し、メッセージ計算部１０２に供給する。さらに、チェックノード演算時には、制御部１０３は、制御信号D19として、チェックノード演算を指示する制御信号を、メッセージ計算部１０２に供給する。
【００９３】
メッセージ計算部１０２の各メッセージ計算器１０２1乃至１０２Pは、メモリ１０１から値D101として供給されるＰ個のメッセージの１つを用いて、制御部１０３からの制御信号D19にしたがって、式（７）のチェックノード演算を行い、そのチェックノード演算によって求められた復号の途中結果であるＰ個の出力メッセージ（チェックノードメッセージ）ujを、Ｐ個のメッセージD17として、メモリ１０１に供給する。そして、メモリ１０１は、制御部１０３から供給される制御信号D103にしたがって、以上のようにしてメッセージ計算部１０２から供給されるＰ個のメッセージD17を記憶する。
【００９４】
メモリ１０１が記憶したメッセージ計算部１０２からの６個のチェックノードメッセージujとしてのメッセージD17は、次のバリアブルノード演算時に、値D101として読み出され、メッセージ計算部１０２に供給される。
【００９５】
次に、図１２は、図１１のメッセージ計算器１０２1の構成例を示している。
【００９６】
なお、図１２では、メッセージ計算器１０２1について説明するが、他のメッセージ計算器１０２2乃至１０２Pも同様に構成される。
【００９７】
メッセージ計算器１０２1は、外部から受信値またはメッセージが入力される入力ポートとして、入力ポートP201を有する。また、メッセージ計算器１０２1は、外部にメッセージを出力するポートとして、出力ポートP202を有している。さらに、メッセージ計算器１０２1は、外部から制御信号が入力される入力ポートとして、入力ポートP203を有している。
【００９８】
メッセージ計算器１０２1は、入力ポートP201から入力される値D101を用い、入力ポートP203から入力される制御信号D19にしたがって、式（１）のバリアブルノード演算または式（７）のチェックノード演算を選択的に行い、その結果得られるメッセージD17を、出力ポートP202から出力する。
【００９９】
即ち、入力ポートP201には、メモリ１０１から読み出された受信値が、値D101として供給される。また、入力ポートP201には、メモリ１０１から読み出されたメッセージ（チェックノードメッセージujまたはバリアブルノードメッセージvi）が、値D101として供給される。さらに、入力ポートP203には、制御部１０３からの制御信号D19が供給される。
【０１００】
そして、入力ポートP201に供給された値D101は、セレクタ３０１のv端子に供給される。さらに、入力ポートP201に値D101として供給されたメッセージのうちの最上位ビットを除く下位ビット、即ち、メッセージの絶対値は、絶対値D303として、LUT３００に供給され、メッセージのうちの最上位ビット、即ち、メッセージの符号ビットは、符号ビットD304として、EXOR回路３０６とFIFOメモリ３２０に供給される。
【０１０１】
また、入力ポートP203に供給された制御信号D19は、セレクタ３０１および３１６に供給される。
【０１０２】
セレクタ３０１および３１６は、v端子とc端子とを有し、制御信号D19にしたがい、v端子またはc端子のうちのいずれかに供給される値を選択して、後段に出力する。即ち、セレクタ３０１および３１６は、制御信号D19がバリアブルノード演算を指示する制御信号である場合には、v端子に供給される値を選択して後段に出力し、制御信号D19がチェックノード演算を指示する制御信号である場合には、c端子に供給される値を選択して後段に出力する。
【０１０３】
その結果、メッセージ計算器１０２1は、バリアブルノード演算と、チェックノード演算を行う。
【０１０４】
即ち、メッセージ計算器１０２1では、以下のようにして、バリアブルノード演算が行われる。
【０１０５】
バリアブルノード演算時においては、入力ポートP201には、メモリ１０１からＰ個ずつ読み出された受信値のうちの１つと、メモリ１０１からＰ個ずつ読み出された、検査行列の各行に対応するチェックノード（出力メッセージviを求めようとしているバリアブルノードに対応する列の、各行に対応するチェックノード）からのチェックノードメッセージujの１つが、順次、値D101として供給される。
【０１０６】
入力ポートP201に値D101として供給された受信値とメッセージ（チェックノードメッセージuj）は、セレクタ３０１のv端子に供給され、バリアブルノード演算時にはv端子を選択しているセレクタ３０１から、値D306として、演算器３０２とFIFOメモリ３２０に供給される。
【０１０７】
演算器３０２は、セレクタ３０１からの値D306（受信値u0iまたはチェックノードメッセージuj）とレジスタ３０３に格納されている積算値D307とを加算することにより、値D306を積算し、その結果得られる積算値を、レジスタ３０３に再格納する。なお、受信値と検査行列の1列に亘る全ての枝からのメッセージが値D306として積算された場合、レジスタ３０３はリセットされる。
【０１０８】
受信値と検査行列の1列に亘るメッセージが値D306として１つずつ読み込まれ、レジスタ３０３に受信値と1列分のメッセージが積算された値が格納された場合、即ち、レジスタ３０３に、受信値と検査行列の１列に亘る全ての枝からのメッセージ（チェックノードメッセージuj）が積算された積算値（ｊ＝１からｄVまでのΣujとu0iの和)が格納された場合、セレクタ３０４は、レジスタ３０３に格納されている値、即ち、受信値と検査行列の１列に亘る全ての枝からのメッセージが積算された積算値D307（ｊ＝１からｄVまでのΣujとu0iの和)を選択し、レジスタ３０５に出力して格納させる。
【０１０９】
レジスタ３０５は、格納している積算値D307を、値D308として、セレクタ３０４と演算器３１２に供給する。レジスタ３０３に受信値と1列分のメッセージが積算された値が格納される直前までは、セレクタ３０４は、レジスタ３０５から供給された値D308を選択し、レジスタ３０５に出力し再格納させる。即ち、受信値u0iと検査行列の１列に亘る全ての枝からのメッセージ（チェックノードメッセージuj）が積算されるまで、レジスタ３０５は、前回積算された値を、セレクタ３０４と演算器３１２に供給する。
【０１１０】
一方、FIFOメモリ３２０は、レジスタ３０５から新たな値D308（ｊ＝１からｄVまでのΣujとu0iの和）が出力されるまでの間、セレクタ３０１が出力した値D306を遅延し、値D315として演算器３１２に供給する。演算器３１２は、レジスタ３０５から供給された値D308から、FIFOメモリ３２０から供給された値D315を減算する。即ち、演算器３１２は、受信値u0iと検査行列の1列に亘る全ての枝からのメッセージ（チェックノードメッセージuj）の積算値D308（ｊ＝１からｄVまでのΣujとu0iの和）から、求めたい枝からのメッセージ（チェックノードメッセージuj）を減算して、減算値D316（バリアブルノードメッセージvi）を求め、セレクタ３１６のv端子に供給する。
【０１１１】
セレクタ３１６は、バリアブルノード演算時にはv端子を選択しており、そのv端子に供給される演算器３１２からの減算値D316を、メッセージD17（バリアブルノードメッセージvi）として、出力ポートP202から出力する。
【０１１２】
以上のように、セレクタ３０１および３１６がv端子を選択しているメッセージ計算器１０２1では、式（１）のバリアブルノード演算が行われ、その結果得られるメッセージ（バリアブルノードメッセージ）viが、出力ポートP202から出力される。
【０１１３】
また、メッセージ計算器１０２1では、以下のようにして、チェックノード演算が行われる。
【０１１４】
即ち、チェックノード演算時においては、入力ポートP201には、メモリ１０１からＰ個ずつ読み出された、検査行列の各列に対応するバリアブルノード（出力メッセージujを求めようとしているチェックノードに対応する行の、各列に対応するバリアブルノード）からのバリアブルノードメッセージviの１つが、順次、値D101として供給される。
【０１１５】
入力ポートP201に値D101として供給されたメッセージ（バリアブルノードメッセージvi）のうちの最上位ビットを除く下位ビット、つまり、メッセージの絶対値D303(|vi|)は、LUT３００に供給され、最上位ビット、つまりメッセージの符号ビット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行に亘る全ての枝からのメッセージの絶対値D303(|vi|)に対する演算結果（φ(|vi|)）が積算された場合、レジスタ３０３はリセットされる。
【０１１９】
検査行列の1行に亘るメッセージが値D101として１つずつ読み込まれ、レジスタ３０３に1行分の演算結果が積算された積算値が格納された場合、セレクタ３０４は、レジスタ３０３に格納されている値、即ち、検査行列の１行に亘る全ての枝からのメッセージ（バリアブルノードメッセージvi）から求められたφ(|vi|)が積算された積算値D307（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）を選択し、レジスタ３０５に出力して格納させる。レジスタ３０５は、格納している積算値D307を、値D308として、セレクタ３０４と演算器３１２に供給する。
【０１２０】
レジスタ３０３に1行分の演算結果が積算された積算値が格納される直前までは、セレクタ３０４は、レジスタ３０５から供給された値D308を選択し、レジスタ３０５に出力して再格納させる。即ち、検査行列の１行に亘る全ての枝からのメッセージ（バリアブルノードメッセージvi）から求められたφ(|vi|)が積算されるまで、レジスタ３０５は、前回積算されたφ(|vi|)の積算値を、セレクタ３０４と演算器３１２に供給する。
【０１２１】
一方、FIFOメモリ３２０は、レジスタ３０５から新たな値D308（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）が出力されるまでの間、LUT３００がセレクタ３０１を介して出力した値D306（φ(|vi|)）を遅延し、値D315として演算器３１２に供給する。演算器３１２は、レジスタ３０５から供給された値D308から、FIFOメモリ３２０から供給された値D315を減算し、その減算結果を、減算値D316としてLUT３１４に供給する。即ち、演算器３１２は、検査行列の1行に亘る全ての枝からのメッセージ（バリアブルノードメッセージvi）から求められたφ(|vi|)の積算値（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）から、求めたい枝からのメッセージ（バリアブルノードメッセージ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行に亘る全ての枝からのメッセージの符号ビットD304が乗算された場合、レジスタ３０７はリセットされる。
【０１２５】
検査行列の1行に亘る全ての枝からのメッセージの符号ビットD304が乗算された乗算結果D309（ｉ＝１からｄcまでのΠsign(vi)）がレジスタ３０７に格納された場合、セレクタ３０８は、レジスタ３０７に格納されている値、即ち、検査行列の１行に亘る全ての枝からのメッセージの符号ビットD304が乗算された値D310（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）を選択し、レジスタ３０９に出力して格納させる。レジスタ３０９は、格納している値D311を、セレクタ３０８とEXOR回路３１５に供給する。
【０１２６】
検査行列の1行に亘る全ての枝からのメッセージの符号ビットD304が乗算された乗算結果D309（ｉ＝１からｄcまでのΠsign(vi)）がレジスタ３０７に格納される直前までは、セレクタ３０８は、レジスタ３０９から供給された値D311を選択し、レジスタ３０９に出力して再格納させる。即ち、検査行列の１行に亘る全ての枝からのメッセージ（バリアブルノードメッセージvi）の符号ビットD304が乗算されるまで、レジスタ３０９は、前回格納した値を、セレクタ３０８とEXOR回路３１５に供給する。
【０１２７】
一方、FIFOメモリ３２０は、レジスタ３０９から新たな値D311（ｉ＝１からｉ＝ｄcま
でのΠsign(vi)）がEXOR回路３１５に供給されるまでの間、符号ビットD304を遅延し、１ビットの値D313としてEXOR回路３１５に供給する。EXOR回路３１５は、レジスタ３０９から供給された値D311と、FIFOメモリ３２０から供給された値D313との排他的論理和を演算することにより、値D311を、値D313で除算し、除算結果を除算値D319として出力する。即ち、EXOR回路３１５は、検査行列の１行に亘る全ての枝からのメッセージの符号ビットD304（sign(vi)）の乗算値（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）を、求めたい枝からのメッセージの符号ビットD304（sign(vi)）で除算して、その除算値（ｉ＝１からｉ＝ｄc−１までのΠsign(vi)）を除算値D319として出力する。
【０１２８】
そして、メッセージ計算器１０２1では、LUT３１４から出力された演算結果D318を下位ビットとするとともに、EXOR回路３１５から出力された除算値D319を最上位ビット（符号ビット）とするビット列D320（チェックノードメッセージuj）が、セレクタ３１６のc端子に供給される。
【０１２９】
セレクタ３１６は、チェックノード演算時にはc端子を選択しており、そのc端子に供給されるビット列D320（チェックノードメッセージuj）を、メッセージD17として、出力ポートP202から出力する。
【０１３０】
以上のように、セレクタ３０１および３１６がc端子を選択しているメッセージ計算器１０２1では、式（７）のチェックノード演算が行われ、その結果得られるメッセージ（チェックノードメッセージ）ujが、出力ポートP202から出力される。
【０１３１】
なお、図示しないが、図１１の復号装置１００では、復号の最終段において、式（１）のバリアブルノード演算の代わりに、式（５）の演算が行われ、その演算結果が、最終的な復号結果として出力される。
【０１３２】
図１３は、図１１のメモリ１０１の詳細構成例を示している。
【０１３３】
図１３のメモリ１０１は、プリバッファ５１１、スイッチ５１２、入力バッファ５１３、および連結メモリ５１４により構成される。メモリ１０１には、受信値D10が間欠的に入力され、この受信値D10は、プリバッファ５１１とスイッチ５１２の端子５１２Ａに供給される。
【０１３４】
プリバッファ５１１には、入力バッファ５１３に１フレーム分の受信値D512が書き込まれたとき、即ち、入力バッファ５１３から連絡メモリ５１４への転送が開始されるとき、入力バッファ５１３から、プリバッファ５１１の選択を表す制御信号D515が供給される。プリバッファ５１１は、その制御信号D515に応じて、受信値D10を一時的に記憶する。なお、プリバッファ５１１の記憶容量は、入力バッファ５１３から連結メモリ５１４へ１フレーム分の受信値D513を転送するために必要な時間内に、受信可能な受信値D10の最大数Ｍと、量子化ビット数との乗算値である。
【０１３５】
これに対して、後述するように、入力バッファ５１３と、連結メモリ５１４の受信値D513を記憶する受信値メモリ６０１（後述する）の記憶容量は、それぞれ、１フレーム分の受信値のデータ量、即ち、符号長と量子化ビット数の乗算値であるので、プリバッファ５１１の記憶容量は、入力バッファ５１３と受信値メモリ６０１のそれぞれの記憶容量に比べて十分に小さい。
【０１３６】
また、プリバッファ５１１は、記憶している受信値D10を受信値D511として連続的に読み出し、スイッチ５１２を介して入力バッファ５１３に供給する。さらに、プリバッファ５１１は、読み出し済みの受信値D10を削除する。プリバッファ５１１は、記憶している受信値D10がなくなった場合、受信値D10の読み出しと書き込みを停止し、スイッチ５１２に、端子５１２Ａの選択を表す制御信号D514を供給する。これにより、間欠的に入力される受信値D10が、端子５１２Ａを介して入力バッファ５１３に供給される。
【０１３７】
スイッチ５１２は、３つの端子５１２Ａ乃至５１２Ｃを有している。端子５１２Ａには受信値D10が間欠的に入力され、端子５１２Ｂにはプリバッファ５１１が接続され、端子５１２Ｃには入力バッファ５１３が接続される。スイッチ５１２は、プリバッファ５１１から供給される制御信号D514に応じて、端子５１２Ａと端子５１２Ｃを接続し、端子５１２Ａに入力される受信値D10を、受信値D512として入力バッファ５１３に入力する。また、スイッチ５１２は、入力バッファ５１３から供給される制御信号D515に応じて、端子５１２Ｂと端子５１２Ｃを接続し、プリバッファ５１１から読み出された受信値D511を、受信値D512として入力バッファ５１３に入力する。
【０１３８】
入力バッファ５１３の記憶容量は、例えば、符号長と量子化ビット数の乗算値であり、入力バッファ５１３は、スイッチ５１２により入力される受信値D512を、一時的に１フレーム分記憶する。なお、ここでは、入力バッファ５１３のビット幅は、連結メモリ５１４のビット幅の1/N（Nは2以上の整数）倍であり、ワード数は、連結メモリ５１４の受信値メモリ６０１のワード数のN倍であるものとするが、入力バッファ５１３のビット幅は、連結メモリ５１４のビット幅より小さければ、1/N倍である必要はない。
【０１３９】
入力バッファ５１３は、1フレーム分の受信値D512の書き込みを完了した場合、例えば、入力バッファ５１３の空き容量がゼロになった場合、プリバッファ５１１とスイッチ５１２に制御信号D515を入力する。そして、入力バッファ５１３は、記憶している１フレーム分の受信値D512を、受信値D513として連続的に読み出し、連結メモリ５１４に転送する。即ち、入力バッファ５１３は、１フレーム単位、つまり、符号語単位で、受信値D512を連続的に読み出し、連結メモリ５１４に転送する。
【０１４０】
このように、入力バッファ５１３は、受信値D512を一時的に記憶し、その受信値D512を１フレーム単位で受信値D513として連結メモリ５１４に転送するので、連結メモリ５１４が、記憶している受信値D513をＰ個ずつ読み出すことにより復号が行われている間も、入力バッファ５１３により、次のフレームの受信値D512を記憶することができる。これにより、受信用メモリ１０１では、受信値D512を連続して記憶することができ、その結果、スループットが向上する。
【０１４１】
連結メモリ５１４は、入力バッファ５１３に直列に接続され、受信値メモリ６０１と、メッセージメモリ６０２がワード方向に接続されることにより構成される。連結メモリ５１４は、制御部１０３から供給される制御信号D103にしたがって、入力バッファ５１３から転送されてくる１フレーム分の受信値D513を、受信値メモリ６０１に格納し、メッセージ計算部１０２からＰ個ずつ出力される検査行列Hの１の数分のメッセージD17を、メッセージメモリ６０２に格納する。
【０１４２】
従って、連結メモリ５１４の受信値メモリ６０１の記憶容量は、符号長と、量子化ビット数との乗算値であり、メッセージメモリ６０２の記憶容量は、検査行列Hの１の数と、量子化ビット数との乗算値である。
【０１４３】
また、連結メモリ５１４は、制御信号D103にしたがって、受信値メモリ６０１に格納している受信値D513をＰ個ずつ読み出すか、メッセージメモリ６０２に格納しているメッセージD17をＰ個ずつ読み出し、値D101としてメッセージ計算部１０２に供給する。
【０１４４】
以上のように、メモリ１０１では、入力バッファ５１３と連結メモリ５１４が直列に接続され、メッセージ計算部１０２への値D101の出力が、１つの連結メモリ５１４で行われるので、入力バッファ５１３は、Ｐ個の受信値D513を同時に読み出す必要がなく、入力バッファ５１３のビット幅を、量子化ビット数のＰ倍のビットより小さくすることができる。その結果、量子化ビット数のＰ倍のビット幅を有する２つの受信値メモリ２１および２２から構成される従来の受信用メモリ１３（図８）に比べて、メモリ１０１を構成するRAMマクロの数を削減し、これにより、メモリ１０１の回路規模を削減することができる。
【０１４５】
また、連結メモリ５１４は、受信値D513またはメッセージD17のいずれか一方をＰ個ずつ同時に読み出すので、連結メモリ５１４全体のビット幅は、量子化ビット数のＰ倍のビットとなり、ワード数は、符号長と検査行列Hの１の数の和からＰを除算した値となる。
【０１４６】
従って、図１１の復号装置１００では、メッセージメモリ１２と受信用メモリ１３を別々に設ける従来の復号装置１０（図８）に比べて、復号装置を構成するメモリのビット幅を削減することができる。即ち、図８の復号装置１０を構成するメモリ全体のビット幅は、同時に読み出す必要がある受信値D15とメッセージD16の数である２倍のＰ個と量子化ビット数の乗算値であるが、図１１の復号装置１００を構成するメモリ全体のビット幅は、同時に値D101として読み出す必要がある受信値またはメッセージのいずれか一方の数であるＰ個と、量子化ビット数の乗算値で済む。その結果、復号装置１００を構成するRAMマクロの数を削減し、これにより、復号装置１００の回路規模を削減することができる。
【０１４７】
例えば、LDPC符号の量子化ビット数が5ビットであり、Ｐが360であるとき、連結メモリ５１４としては、1800（=360×5）ビット幅のRAMが１つ必要になる。また、入力バッファ５１３のビット幅が、連結メモリ５１４のビット幅の1/10倍である(N=1/10)とき、入力バッファ５１３としては、180(=1800/10)ビット幅のRAMが１つ必要になる。従って、RAMマクロのビット幅の上限が120ビットであるとすると、メモリ１０１を構成するRAMマクロの総数は、連結メモリ５１４を構成するRAMマクロの数である15(=1800/120)個と、入力バッファ５１３を構成するRAMマクロの数である2(=180/120（小数点繰上げ）)個の和である17個となる。
【０１４８】
このように、復号装置１００において必要なRAMマクロの数は17個であり、従来の復号装置１０において必要なRAMマクロの数である45個と比べて、RAMマクロの数を大幅に削減することができる。
【０１４９】
次に、図１４は、図１３の入力バッファ５１３と連結メモリ５１４に対する受信値の読み書きのタイミングを示すタイミングチャートである。
【０１５０】
図１４においては、まず最初に、時間Ｐの間、あるフレームであるフレーム＃１の受信値D512が、入力バッファ５１３に書き込まれる(フレーム＃１入力)。その書き込みの終了後、時間Ｑの間、時間Ｐの間に書き込まれたフレーム＃１の受信値D512が、受信値D513として、入力バッファ５１３から連結メモリ５１４に転送され、連絡メモリ５１４の受信値メモリ６０１に書き込まれる（転送）。
【０１５１】
そして、その転送の終了後、時間Ｒの間、フレーム＃１の次のフレームであるフレーム＃２の受信値D512が、入力バッファ５１３に書き込まれる(フレーム＃２入力)とともに、時間Ｑの間に連結メモリ５１４に転送されたフレーム＃１の受信値D513が、値D101として、連結メモリ５１４の受信値メモリ６０１からＰ個ずつ読み出されて復号される（フレーム＃１復号）。即ち、時間Ｒの間、受信値メモリ６０１から値D101としてＰ個ずつ読み出された受信値と、メッセージメモリ６０２から値D101としてＰ個ずつ読み出されたメッセージのそれぞれとを用いて、バリアブルノード演算とチェックノード演算がＰ個単位で繰り返し行われ、これらの演算の結果得られるメッセージD17は、連結メモリ５１４のメッセージメモリ６０２に書き込まれる。
【０１５２】
次に、時間Ｓの間、時間Ｒの間に書き込まれたフレーム＃２の受信値D512が、受信値D513として、入力バッファ５１３から連結メモリ５１４に転送され、連結メモリ５１４の受信値メモリ６０１に書き込まれる(転送)。その転送の終了後、時間Ｔの間、フレーム＃２の次のフレームであるフレーム＃３の受信値D512が、入力バッファ５１３に書き込まれる(フレーム＃３入力)とともに、時間Ｓの間に連結メモリ５１４に転送されたフレーム＃２の受信値D513が、値D101として、連結メモリ５１４から読み出されて復号される（フレーム＃２復号）。以下、同様にして、入力バッファ５１３と連結メモリ５１４のそれぞれに対する受信値の読み書きが行われていく。
【０１５３】
次に、図１５は、図１４の時間Ｒや時間Ｔに行われるバリアブルノード演算における、連結メモリ５１４に対するメッセージの読み書きのタイミングを示すタイミングチャートである。なお、図１５では、ノード次数が９であるものとする。
【０１５４】
図１５においては、まず最初に、あるフレームの受信値（u0i）がＰ個ずつ値D101として連結メモリ５１４の受信値メモリ６０１から読み出される。その後、Ｐ個のチェックノードメッセージu0としての値D101が、連結メモリ５１４のメッセージメモリ６０２から同時に読み出される。以下、同様にして、Ｐ個の各チェックノードメッセージｕ1乃至ｕ8としての値D101が、Ｐ個単位で順に連結メモリ５１４のメッセージメモリ６０２から同時に読み出される。このように、連結メモリ５１４は、受信値またはメッセージのうちのいずれか一方を、値D101としてＰ個同時に読み出す。
【０１５５】
そして、メッセージ計算器１０２1乃至１０２Pは、それぞれ、受信値メモリ６０１から値D101として読み出されたＰ個の受信値（u0i）の１つと、Ｐ個の各チェックノードメッセージｕ0乃至ｕ8の１つとを用いて、チェックノード演算を行う。なお、上述したように、メッセージ計算器１０２1乃至１０２Pは、それぞれ、チェックノードメッセージｕ0乃至ｕ8を積算するので、メッセージ計算器１０２1乃至１０２Pでは、受信値ｕ0iが入力されてからノード次数分の遅延、即ち10(=1+9)クロック分の遅延以上の遅延が生じる。即ち、図１１の復号装置１００では、受信値ｕ0iとチェックノードメッセージｕ0を同時に読み出さないため、図８の復号装置１０に比べて、1クロック分遅延が多くなる。
【０１５６】
ここで、図１５の例では、13クロック分の遅延が生じるものとする。従って、Ｐ個のチェックノードメッセージｕ0としての値D101が読み出されてから、12クロック後には、値D101として読み出されたメッセージと受信値を用いたバリアブルノード演算の結果得られる、Ｐ個のバリアブルノードメッセージv0としてのメッセージD17が、連結メモリ５１４のメッセージメモリ６０２に書き込まれる。以下、同様にして、Ｐ個のバリアブルノードメッセージv1乃至v8としてのメッセージD17が、Ｐ個単位で順にメッセージメモリ６０２に書き込まれる。
【０１５７】
なお、図示は省略するが、図１１の復号装置１００の式（７）のチェックノード演算や、式（５）に示す演算における読み書きのタイミングも、同様のタイミングでＰ個ずつ行われる。復号装置１００では、式（５）に示す演算における遅延は、図８の復号装置１０に比べて1クロック分多くなるが、チェックノード演算における遅延は、図８の復号装置１０と同一である。
【０１５８】
次に、図１６と図１７を参照して、図１３のメモリ１０１における受信値処理について説明する。この受信値処理は、例えば、各フレームの受信値D10がメモリ１０１に間欠的に入力されたとき、開始される。
【０１５９】
ステップＳ２１において、プリバッファ５１１は、制御信号D515に応じて、間欠的に入力される受信値D10の書き込みを開始する。ステップＳ２２において、スイッチ５１２は、制御信号D515に応じて、プリバッファ５１１と入力バッファ５１３を接続する。即ち、あるフレームの受信値D10がメモリ１０１に間欠的に入力されるとき、その前のフレームの受信値D512の入力バッファ５１３への書き込みが終了しており、入力バッファ５１３から制御信号D515が出力される。従って、プリバッファ５１１は、その制御信号D515に応じて、受信値D10の書き込みを開始し、スイッチ５１２は、プリバッファ５１１と入力バッファ５１３を接続する。
【０１６０】
ステップＳ２３において、プリバッファ５１１は、入力バッファ５１３から連絡メモリ５１４への１フレーム分の受信値D513の転送に要する時間として予め設定された、所定の時間が経過したかどうかを判定する。ステップＳ２３で所定の時間が経過していないと判定された場合、プリバッファ５１１は、所定の時間が経過するまで待機する。
【０１６１】
ステップＳ２３で所定の時間が経過したと判定された場合、ステップＳ２４において、プリバッファ５１１は、既に書き込まれている受信値D10の受信値D511としての連続的な読み出しを開始する。即ち、プリバッファ５１１は、受信値D10の書き込みを行うとともに、受信値D511の読み出しを行う。プリバッファ５１１から読み出された受信値D511は、スイッチ５１２に供給され、受信値D512として入力バッファ５１３に供給される。
【０１６２】
ステップＳ２５において、入力バッファ５１３は、スイッチ５１２を介してプリバッファ５１１から供給される受信値D512の書き込みを開始する。ステップＳ２６において、プリバッファ５１１は、プリバッファ５１１が空になったかどうか、即ち、プリバッファ５１１に書き込まれた受信値D10がすべて読み出されたかどうかを判定し、プリバッファ５１１が空になっていないと判定した場合、空になるまで待機する。
【０１６３】
一方、ステップＳ２６において、プリバッファ５１１が空になったと判定された場合、ステップＳ２７において、プリバッファ５１１は、受信値D10の書き込みと読み出しを終了する。ステップＳ２８において、プリバッファ５１１は、制御信号D514をスイッチ５１２に出力する。ステップＳ２９において、スイッチ５１２は、プリバッファ５１１から供給される制御信号D514に応じて、端子５１２Ａと入力バッファ５１３を接続する。
【０１６４】
ステップＳ３０において、入力バッファ５１３は、1フレーム分の受信値D512が書き込まれたかどうか、即ち、入力バッファ５１３の空き容量がゼロになったかどうかを判定する。ステップＳ３０で1フレーム分の受信値D512がまだ書き込まれていないと判定された場合、１フレーム分の受信値D512がすべて書き込まれるまで待機する。
【０１６５】
一方、ステップＳ３０で1フレーム分の受信値D512が書き込まれたと判定された場合、ステップＳ３１において、入力バッファ５１３は、制御信号D515をプリバッファ５１１とスイッチ５１２に出力する。
【０１６６】
次に、図１７のステップＳ３２において、入力バッファ５１３は、書き込まれている1フレーム分の受信値D512を受信値D513として読み出し、その受信値D513の連結メモリ５１４への転送を開始する。
【０１６７】
ステップＳ３３において、連結メモリ５１４は、入力バッファ５１３から転送されてきた受信値D513の受信値メモリ６０１への書き込みを開始する。ステップＳ３４において、入力バッファ５１３は、1フレーム分の受信値D513の転送が完了したかどうか、即ち、書き込まれている受信値D513のすべてを転送したかどうかを判定し、1フレーム分の受信値D513の転送がまだ完了していないと判定した場合、転送が完了するまで待機する。
【０１６８】
一方、ステップＳ３４で1フレーム分の受信値D513の転送が完了したと判定された場合、ステップＳ３５において、入力バッファ５１３は、受信値D513の転送を終了する。ステップＳ３６において、連結メモリ５１４は、入力バッファ５１３から転送されてきた受信値D513の受信値メモリ６０１への書き込みを終了する。
【０１６９】
ステップＳ３７において、連結メモリ５１４は、制御部１０３から供給される制御信号D103にしたがって、受信値メモリ６０１に書き込まれた受信値D513を、ワード単位でＰ個ずつ読み出し、値D101として、メッセージ計算部１０２に出力する。
【０１７０】
ステップＳ３８において、連結メモリ５１４は、制御部１０３から供給される制御信号D103にしたがって、チェックノードメッセージｕjとしてのメッセージD17を値D101としてＰ個ずつ読み出し、メッセージ計算部１０２に出力する。これにより、メッセージ計算部１０２では、ステップＳ３７で出力された値D101としての受信値と、ステップＳ３８で出力された値D101としてのメッセージを用いて、Ｐ個同時にバリアブルノード演算が行われる。そして、メッセージ計算部１０２から、バリアブルノード演算の結果得られたバリアブルノードメッセージｖiとしてのメッセージD17がＰ個ずつ連結メモリ５１４に供給される。
【０１７１】
ステップＳ３９において、連結メモリ５１４は、制御部１０３から供給される制御信号D103にしたがって、メッセージ計算部１０２からＰ個ずつ供給されるバリアブルノードメッセージｖiとしてのメッセージD17をメッセージメモリ６０２に記憶する。ステップＳ４０において、連結メモリ５１４は、制御部１０３から供給される制御信号D103にしたがって、ステップＳ３９で記憶されたバリアブルノードメッセージｖiとしてのメッセージD17を、Ｐ個ずつ値D101としてメッセージメモリ６０２から読み出し、メッセージ計算部１０２に出力する。
【０１７２】
これにより、メッセージ計算部１０２では、ステップＳ４０で出力されたバリアブルノードメッセージｖiとしての値D101を用いて、Ｐ個同時にチェックノード演算が行われる。そして、メッセージ計算部１０２から、チェックノード演算の結果得られたチェックノードメッセージｕjとしてのメッセージD17がＰ個ずつ連結メモリ５１４に供給される。
【０１７３】
ステップＳ４１において、連結メモリ５１４は、制御部１０３から供給される制御信号D103にしたがって、メッセージ計算部１０２からＰ個ずつ供給されるチェックノードメッセージｕjとしてのメッセージD17をメッセージメモリ６０２に記憶し、処理は終了する。
【０１７４】
なお、ステップＳ３７乃至Ｓ４１の処理は、所定の復号回数分繰り返される。また、最後のステップＳ３７の処理により読み出される受信値D513と、最後のステップＳ３８の処理により値D101として読み出されるチェックノードメッセージｕjは、式（５）に示した演算に用いられ、その演算の結果得られるメッセージｖは、復号結果として復号装置１００から出力される。
【０１７５】
次に、図１８を参照して、図１１の復号装置１００における復号処理について説明する。この復号処理は、例えば、メモリ１０１から受信値と、チェックノードメッセージｕjが、値D101としてＰ個ずつ読み出されたとき、開始される。
【０１７６】
ステップＳ５１において、メッセージ計算部１０２は、メモリ１０１から値D101としてＰ個ずつ読み出される受信値と、チェックノードメッセージｕjとを用いて、式（１）のバリアブルノード演算をＰ個ずつ行い、バリアブルノードメッセージｖiとしてのメッセージD17をＰ個ずつ求める。
【０１７７】
ステップＳ５２において、メッセージ計算部１０２は、求められたバリアブルノードメッセージｖiとしてのメッセージD17をＰ個ずつメモリ１０１に供給する。これにより、メモリ１０１のメッセージメモリ６０２には、バリアブルノードメッセージｖiとしてのメッセージD17が記憶され、そのメッセージD17が、値D101としてＰ個ずつ読み出される。
【０１７８】
ステップＳ５３において、メッセージ計算部１０２は、メッセージメモリ６０２から値D101としてＰ個ずつ読み出された、バリアブルノードメッセージｖiを用いて、式（７）のチェックノード演算をＰ個ずつ行い、チェックノードメッセージｕjとしてのメッセージD17をＰ個ずつ求める。
【０１７９】
ステップＳ５４において、メッセージ計算部１０２は、求められたチェックノードメッセージｕjとしてのメッセージD17をＰ個ずつメモリ１０１に供給する。これにより、メモリ１０１のメッセージメモリ６０２には、チェックノードメッセージｕjとしてのメッセージD17が記憶され、そのメッセージD17が、ステップＳ５１のバリアブルノード演算に用いられる。
【０１８０】
なお、図１８の復号処理は、１フレームの受信値に対して復号回数繰り返して行われる。そして、最後のステップＳ５４の処理によりメモリ１０１に供給されるチェックノードメッセージｕjとしてのメッセージD17と、受信値は、式（５）に示した演算に用いられ、その演算の結果得られるメッセージｖは、復号結果として復号装置１００から出力される。
【０１８１】
なお、図１１の復号装置１００では、Ｐ×Ｐの単位行列、準単位行列、単位行列と準単位行列の和、Ｐ×Ｐの０行列の組み合わせで表すことが可能な検査行列Hを有するLDPC符号、もしくは行や列の置換により、これらの行列の組み合わせで表すことが可能な検査行列Hを有するLDPC符号を復号することとしたが、Ｐ×Ｐの単位行列、準単位行列、単位行列、準単位行列、またはシフト行列のうちの２以上(複数)の和（以下、適宜、和行列という）、Ｐ×Ｐの０行列の組み合わせで表すことが可能な検査行列Hを有するLDPC符号、もしくは行や列の置換により、これらの行列の組み合わせで表すことが可能な検査行列Hを有するLDPC符号を復号するようにしてもよい。この場合、メモリ１０１とメッセージ計算部１０２の間に、値D101としてのメッセージをサイクリックシフトするサイクリックシフト回路が設けられる。
【０１８２】
また、一般的に、LDPC符号は符号長が数千から数万と大きいため、Ｐの値も数百の大きさを持つものが使われる。その場合には、更に本発明に係る復号装置を用いる効果は大きくなる。
【０１８３】
なお、上述したLDPC符号を復号する復号装置は、例えば、（ディジタル）衛星放送を受信するチューナなどに適用することができる。
【図面の簡単な説明】
【０１８４】
【図１】LDPC符号の検査行列Hを説明する図である。
【図２】LDPC符号の復号手順を説明するフローチャートである。
【図３】メッセージの流れを説明する図である。
【図４】LDPC符号の検査行列Hの例を示す図である。
【図５】検査行列Hのタナーグラフを示す図である。
【図６】バリアブルノードを示す図である。
【図７】チェックノードを示す図である。
【図８】チェックノード演算とバリアブルノード演算をＰ個ずつ同時に行う復号装置の構成の一例を示すブロック図である。
【図９】図８の受信値メモリおよびメッセージメモリに対する読み書きのタイミングを示すタイミングチャートである。
【図１０】図８の受信用メモリとメッセージメモリに対する読み書きのタイミングを示すタイミングチャートである。
【図１１】本発明を適用した復号装置の一実施の形態の構成例を示すブロック図である。
【図１２】図１１のメッセージ計算器の詳細構成例を示すブロック図である。
【図１３】図１１のメモリの詳細構成例を示すブロック図である。
【図１４】図１３の入力バッファと連結メモリに対する受信値の読み書きのタイミングを示すタイミングチャートである。
【図１５】図１３の連結メモリに対するメッセージの読み書きのタイミングを示すタイミングチャートである。
【図１６】図１３のメモリにおける受信値処理について説明するフローチャートである。
【図１７】図１３のメモリにおける受信値処理について説明するフローチャートである。
【図１８】図１１の復号装置における復号処理について説明するフローチャートである。
【符号の説明】
【０１８５】
１００  復号装置，  １０１  メモリ，  １０２  メッセージ計算部,  ５１１  プリバッファ，  ５１３  入力バッファ，  ５１４  連結メモリ，  ６０１  受信値メモリ，  ６０２  メッセージメモリ
【図１】
0004821724.tif 000010
【図２】
0004821724.tif 000011
【図３】
0004821724.tif 000012
【図４】
0004821724.tif 000013
【図５】
0004821724.tif 000014
【図６】
0004821724.tif 000015
【図７】
0004821724.tif 000016
【図８】
0004821724.tif 000017
【図９】
0004821724.tif 000018
【図１０】
0004821724.tif 000019
【図１１】
0004821724.tif 000020
【図１２】
0004821724.tif 000021
【図１３】
0004821724.tif 000022
【図１４】
0004821724.tif 000023
【図１５】
0004821724.tif 000024
【図１６】
0004821724.tif 000025
【図１７】
0004821724.tif 000026
【図１８】
0004821724.tif 000027