(57)【特許請求の範囲】
【請求項１】
LDPC(Low Density Parity Check)符号の復号装置であって、
前記LDPC符号の復号のためのP（１より大きい整数）個の演算を同時に行う演算手段
を備え、
前記演算手段は、
複数のデータを積算し、前記複数のデータの積算値から、前記複数のデータそれぞれを減算する演算を含むチェックノードの演算を行う前記P個の演算器と、
前記積算値から減算する前記複数のデータを記憶する、ビット幅が、前記データの量子化幅のP倍で、ワード数が前記LDPC符号の検査行列の行の重みに等しい１個の遅延用の記憶手段と
を備え、
前記演算器は、前記記憶手段を用いて、前記複数のデータの積算値から、前記記憶手段で遅延された前記複数のデータそれぞれを減算する
復号装置。
【請求項２】
前記記憶手段は、RAM（Random Access Memory）である
請求項１に記載の復号装置。
【請求項３】
前記記憶手段は、FIFO（First In First Out）である
請求項１に記載の復号装置。
【請求項４】
前記記憶手段は、レジスタファイルである
請求項１に記載の復号装置。
【請求項５】
LDPC(Low Density Parity Check)符号の復号のためのP（１より大きい整数）個の演算を同時に行う演算手段を備え、
前記演算手段は、
複数のデータを積算し、前記複数のデータの積算値から、前記複数のデータそれぞれを減算する演算を含むチェックノードの演算を行う前記P個の演算器と、
前記積算値から減算する前記複数のデータを記憶する、ビット幅が、前記データの量子化幅のP倍で、ワード数が前記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による「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行列（ｋ行ｎ列の行列）である場合には、検査行列Hは、n-k行ｎ列の行列である。
【００１０】
なお、例えば、nビットの符号語cが、kビットの情報メッセージuに続けて、n-kビットのパリティビットを配置したビット列に一致する組織符号である場合に、n-k行n列の検査行列Hにおいて、nビットの符号語cのうちのkビットの情報メッセージuに対応するn-k行k列の部分を情報部というとともに、n-kビットのパリティビットに対応するn-k行n-k列の部分をパリティ部ということとすると、パリティ部が、下三角行列または上三角行列になっていれば、情報メッセージuのLDPC符号への符号化は、検査行列Hを用いて行うことができる。
【００１１】
即ち、例えば、検査行列Hが、図２に示すように、情報部と、下三角行列のパリティ部とで構成され、パリティ部の下三角の部分の要素が、すべて1であるとすると、符号語cのパリティビットの１番目のビットは、情報メッセージuのうちの、検査行列Hの情報部の第１行において1になっている要素に対応するビットのEXOR（排他的論理和）を演算した値となる。
【００１２】
また、符号語cのパリティビットの２番目のビットは、情報メッセージuのうちの、検査行列Hの情報部の第２行において1になっている要素に対応するビットと、パリティビットの１番目のビットのEXORを演算した値となる。
【００１３】
さらに、符号語cのパリティビットの３番目のビットは、情報メッセージuのうちの、検査行列Hの情報部の第３行において1になっている要素に対応するビットと、パリティビットの１番目および２番目のビットのEXORを演算した値となる。
【００１４】
以下、同様にして、符号語cのパリティビットのi番目のビットは、情報メッセージuのうちの、検査行列Hの情報部の第i行において1になっている要素に対応するビットと、パリティビットの１乃至i-1番目のビットのEXORを演算した値となる。
【００１５】
以上のようにして、n-kビットのパリティビットを求め、kビットの情報メッセージuに続けて配置することにより、nビットの符号語cを得ることができる。
【００１６】
一方、LDPC符号の復号は、Gallagerが確率復号(Probabilistic Decoding)と称して提案したアルゴリズムであって、バリアブルノード(variable node（メッセージノード(message node)とも呼ばれる。）)と、チェックノード(check node)とからなる、いわゆるタナーグラフ(Tanner graph)上での確率伝播(belief propagation)によるメッセージ・パッシング・アルゴリズムによって行うことが可能である。ここで、以下、適宜、バリアブルノードとチェックノードを、単に、ノードともいう。
【００１７】
しかしながら、確率復号においては、各ノード間で受け渡されるメッセージが実数値であることから、解析的に解くためには、連続した値をとるメッセージの確率分布そのものを追跡する必要があり、非常に困難を伴う解析を必要とすることになる。そこで、Gallagerは、LDPC符号の復号アルゴリズムとして、アルゴリズムＡ又はアルゴリズムＢを提案している。
【００１８】
LDPC符号の復号は、一般的には、図３に示すような手順にしたがって行われる。なお、ここでは、受信値をU0とし、チェックノードから出力されるメッセージをujとし、バリアブルノードから出力されるメッセージをviとする。また、ここでは、メッセージとは、値の”0”らしさを、いわゆる対数尤度比(log likelihood ratio)で表現した実数値である。さらに、受信値U0の”0”らしさの対数尤度比を、受信データu0iと表すこととする。
【００１９】
まず、LDPC符号の復号においては、図３に示すように、ステップＳ１１において、受信値U0(受信データu0i)が受信され、メッセージujが”0”に初期化されるとともに、繰り返し処理のカウンタとしての整数をとる変数kが”0”に初期化され、ステップＳ１２に進む。ステップＳ１２において、受信値U0(受信データu0i)に基づいて、式（１）に示す演算を行うことによってメッセージviが求められ、さらに、このメッセージviに基づいて、式（２）に示す演算を行うことによってメッセージujが求められる。
【００２０】
【数１】
0004730592.tif 000002
・・・（１）
【００２１】
【数２】
0004730592.tif 000003
・・・（２）
【００２２】
ここで、式（１）と式（２）におけるdvとdcは、それぞれ、検査行列Hの縦方向（行方向）と横方向（列方向）の”1”の個数を示す任意に選択可能とされるパラメータであり、例えば、(3,6)符号の場合には、dv=3，dc=6となる。
【００２３】
なお、式（１）または（２）の演算においては、それぞれ、メッセージを出力しようとする枝(edge)から入力されたメッセージを、和または積演算のパラメータとしては用いないことから、和または積演算の範囲が、１乃至dv-1または１乃至dc-1となっている。また、式（２）に示す演算は、実際には、２入力v1，v2に対する１出力で定義される式（３）に示す関数R(v1,v2)のテーブルを予め作成しておき、これを式（４）に示すように連続的（再帰的）に用いることによって行われる。
【００２４】
【数３】
0004730592.tif 000004
・・・（３）
【００２５】
【数４】
0004730592.tif 000005
・・・（４）
【００２６】
ステップＳ１２では、さらに、変数kが”1”だけインクリメントされ、ステップＳ１３に進む。ステップＳ１３では、変数kが所定の繰り返し復号回数N以上であるか否かが判定される。ステップＳ１３において、変数kがN以上ではないと判定された場合、ステップＳ１２に戻り、以下、同様の処理が繰り返される。
【００２７】
また、ステップＳ１３において、変数kがN以上であると判定された場合、ステップＳ１４に進み、式（５）に示す演算を行うことによって最終的に出力する復号結果としてのメッセージvが求められて出力され、LDPC符号の復号処理が終了する。
【００２８】
【数５】
0004730592.tif 000006
・・・（５）
【００２９】
ここで、式（５）の演算は、式（１）の演算とは異なり、バリアブルノードに接続している全ての枝からの入力メッセージを用いて行われる。
【００３０】
このようなLDPC符号の復号は、例えば(3,6)符号の場合には、図４に示すように、各ノード間でメッセージの授受が行われる。なお、図４における”=”で示すノード（バリアブルノード）では、式（１）に示した演算が行われ、”+”で示すノード（チェックノード）では、式（２）に示した演算が行われる。特に、アルゴリズムＡにおいては、メッセージを２元化し、”+”で示すノードにて、dc-1個の入力メッセージの排他的論理和演算を行い、”=”で示すノードにて、受信値Rに対して、dv-1個の入力メッセージが全て異なるビット値であった場合には、符号を反転して出力する。
【００３１】
また、一方で、近年、LDPC符号の復号の実装法に関する研究も行われている。実装方法について述べる前に、まず、LDPC符号の復号を摸式化して説明する。
【００３２】
図５は、(3,6)LDPC符号（符号化率1/2、符号長12）の検査行列H(parity check matrix)の例である。LDPC符号の検査行列Hは、図６のように、タナーグラフを用いて書き表すことができる。ここで、図６において、”+”で表わされるのが、チェックノードであり、”=”で表わされるのが、バリアブルノードである。チェックノードとバリアブルノードは、それぞれ、検査行列Hの行と列に対応する。チェックノードとバリアブルノードとの間の結線は、枝(edge)であり、検査行列Hの”1”に相当する。即ち、検査行列Hの第ｊ行第ｉ列のコンポーネントが１である場合には、図６において、上からｉ番目のバリアブルノード（”=”のノード）と、上からｊ番目のチェックノード（”+”のノード）とが、枝により接続される。枝は、バリアブルノードに対応する符号ビットが、チェックノードに対応する拘束条件を持つことを表わす。なお、図６は、図５の検査行列Hのタナーグラフとなっている。
【００３３】
LDPC符号の復号方法であるサムプロダクトアルゴリズム(Sum Product Algorithm)は、バリアブルノードの演算とチェックノードの演算とを繰り返し行う。
【００３４】
バリアブルノードでは、図７のように、式（１）の演算を行う。すなわち、図７において、計算しようとしている枝に対応するメッセージviは、バリアブルノードに繋がっている残りの枝からのメッセージu1およびu2と、受信データu0iを用いて計算される。他の枝に対応するメッセージも同様に計算される。
【００３５】
チェックノードの演算について説明する前に、式（２）を、式a×b=exp{ln(|a|)+ln(|b|)}×sign(a)×sign(b)の関係を用いて、式（６）のように書き直す。但し、sign(x)は、x≧0のとき1であり、x＜0のとき-1である。
【００３６】
【数６】
0004730592.tif 000007
・・・（６）
【００３７】
更に、x≧0において、φ(x)=ln(tanh(x/2))と定義すると、φ-1(x)=2tanh-1(e-x)であるから、式（６）は、式（７）のように書くことができる。
【００３８】
【数７】
0004730592.tif 000008
・・・（７）
【００３９】
チェックノードでは、図８のように、式（７）の演算を行う。すなわち、図８において、計算しようとしている枝に対応するメッセージujは、チェックノードに繋がっている残りの枝からのメッセージv1,v2,v3,v4,v5を用いて計算される。他の枝に対応するメッセージも同様に計算される。
【００４０】
なお、関数φ(x)は、φ(x)=ln((ex+1)/(ex-1))とも表すことができ、x＞0において、φ(x)=φ-1(x)である。関数φ(x)およびφ-1(x)をハードウェアに実装する際には、LUT(Look Up Table)を用いて実装される場合があるが、両者共に同一のLUTとなる。
【００４１】
サムプロダクトアルゴリズムをハードウェアに実装する場合、式（１）で表わされるバリアブルノード演算および式（７）で表わされるチェックノード演算を、適度な回路規模と動作周波数で繰り返し行うことが必要である。
【００４２】
復号装置の実装の例として、各ノードの演算を複数個ずつ順次行うことによって復号を行う場合(partly parallel decoding)の実装法について説明する。
【００４３】
なお、ここでは、例えば、図９の、３６（行）×１０８（列）の検査行列Hで表現される符号（符号化率2/3、符号長108）を復号することとする。図９の検査行列Hの１の数は３２３であり、従って、そのタナーグラフでは、枝の数は３２３個となる。ここで、図９の検査行列Hでは、０を、”.”で表している。また、図９の検査行列Hは、６×６行列の単位に間隔を空けて表している。
【００４４】
図９においては、検査行列Hは、６×６の単位行列、その単位行列の１のうち１個以上が０になった行列（以下、適宜、準単位行列という）、単位行列または準単位行列をサイクリックシフト(cyclic shift)した行列（以下、適宜、シフト行列という）、単位行列、準単位行列、またはシフト行列のうちの２以上(複数)の和（以下、適宜、和行列という）、６×６の０行列の組み合わせで表されている。
【００４５】
なお、図９の検査行列Hを構成する６×６の単位行列、準単位行列、シフト行列、和行列、０行列を、以下、適宜、構成行列という。
【００４６】
図１０乃至図１４を参照して、図９の検査行列Hで表現されるLDPC符号を復号する復号装置について説明する。
【００４７】
図１０は、図９の検査行列Hで表現されるLDPC符号を復号する復号装置４００の構成の一例を示すブロック図である。
【００４８】
復号装置４００は、復号途中結果格納用メモリ４１０、サイクリックシフト回路４１１、６つの計算器４１２1乃至計算器４１２6からなる計算部４１２、復号途中結果格納用メモリ４１３、サイクリックシフト回路４１４、６つの計算器４１５1乃至計算器４１５6からなる計算部４１５、受信用メモリ４１６、および制御部４１７から構成される。
【００４９】
ここで、計算器４１２k（k=1,2,・・・，6）で行われる演算と、計算器４１５kで行われる演算について、式を用いて説明する。
【００５０】
計算部４１２は、上述した式（７）と、以下に表す式（８）とにしたがう第１の演算を行い、その第１の演算の結果である復号途中結果ujを復号途中結果格納用メモリ４１３に供給して格納させる。計算部４１５は、上述した式（５）にしたがう第２の演算を行い、その第２の演算の結果である復号途中結果vを復号途中結果格納用メモリ４１０に供給して格納させる。
【００５１】
【数８】
0004730592.tif 000009
・・・（８）
【００５２】
なお、式（８）のudvは、検査行列Hのｉ列のメッセージを求めようとする枝からのチェックノード演算の途中結果（ここでは、チェックノードのメッセージそのもの）を表している。即ち、udvは、求めたい枝に対応する復号途中結果である。
【００５３】
上述した式（５）にしたがう第２の演算の結果得られる復号途中結果vは、受信データu0iと検査行列Hのｉ列の各行の１に対応するすべての枝からのチェックノード演算の復号途中結果ujとを加算したものであるので、上述した式（７）に用いられる値viは、式（５）にしたがう第２の演算の結果得られる復号途中結果vから、検査行列Hのｉ列の、各行の１に対応する枝からのチェックノード演算の復号途中結果ujのうち、メッセージを求めようとする枝からのチェックノード演算の復号途中結果udvを引いた値となる。つまり、式（７）の演算に用いられる値viを求める式（１）の演算は、上述した式（５）と式（８）を組み合わせた演算である。
【００５４】
従って、復号装置４００では、計算部４１２による式（７）および式（８）にしたがう第１の演算と、計算部４１５による式（５）にしたがう第２の演算とが交互に行われ、計算部４１５が、最後の第２の演算の結果を復号結果として出力することにより、LDPC符号の繰り返し復号を行うことができる。
【００５５】
なお、ここでは、式（７）と式（８）にしたがう第１の演算結果を、復号途中結果ujと記載するが、この復号途中結果ujは、式（７）のチェックノードのメッセージｕjに等しい。
【００５６】
また、第２の演算により求められる式（５）のvは、式（１）のバリアブルノード演算結果viに対して、メッセージを求めようとする枝からのチェックノードのメッセージujを加算したものであるから、検査行列Hの1列（１つのバリアブルノード）に対して、１つだけ求められる。
【００５７】
復号装置４００では、計算部４１２が、計算部４１５による第２の演算の結果である検査行列Hの列に対応する復号途中結果vを用いて、第１の演算を行い、その演算の結果得られる検査行列Hのｉ列の、各行の１に対応する枝のメッセージ（各チェックノードが各枝に出力するメッセージ）の枝からのチェックノード演算の復号途中結果ujを復号途中結果格納用メモリ４１３に格納する。従って、復号途中結果格納用メモリ４１３の容量は、チェックノード演算の結果を格納する場合と同様に、検査行列Hの１の数（全枝数）と量子化ビット数とを乗算した値となる。
【００５８】
一方、計算部４１５は、計算部４１２による第１の演算の結果である検査行列Hのｉ列の、各行の”１”に対応する復号途中結果ujと受信データu0iを用いて、第２の演算を行い、その演算の結果得られるｉ列に対応する復号途中結果vを復号途中結果格納用メモリ４１０に格納する。従って、復号途中結果格納用メモリ４１０に必要な容量は、検査行列Hの”１”の数より少ない検査行列Hの列数、即ち、LCPC符号の符号長と復号途中結果vの量子化ビット数とを乗算した値となる。
【００５９】
その結果、バリアブルノード演算の結果を格納する場合に比べて、復号途中結果格納用メモリ４１０のメモリ容量を削減することができ、これにより、復号装置４００の回路規模を小さくすることができる。
【００６０】
以下、図１０の復号装置４００の各部の動作について詳細に説明する。
【００６１】
復号途中結果格納用メモリ４１０には、計算部４１５から、計算部４１５による第２の演算の結果である検査行列Hの６つの列に対応する６つの復号途中結果D415が供給され、復号途中結果格納用メモリ４１０は、計算部４１５から供給された６つの復号途中結果D415を、第１アドレスから順に格納（記憶）する。
【００６２】
即ち、復号途中結果格納用メモリ４１０の第１アドレスには、検査行列Hの列に対応する復号途中結果のうち、第１列目から第６列目の復号途中結果vが格納される。そして、同様に、第２アドレスには、第７列目から第１２列目の復号途中結果vが格納され、第３アドレスには、第１３列目から第１８列目の復号途中結果が格納される。以後、同様に、第１０３列目から第１０８列目までの復号途中結果vが、６個ずつ、第４アドレスから第１８アドレスまで格納され、計１０８個の復号途中結果vが復号途中結果格納用メモリ４１０に格納される。従って、復号途中結果格納用メモリ４１０のワード（word）数は、図９の検査行列Hの列数（LDPC符号の符号長）である１０８を、同時に読み書きする復号途中結果の数である６で割り算した１８となる。
【００６３】
また、復号途中結果格納用メモリ４１０は、既に格納してある復号途中結果D415から、後段の計算部４１２が求めようとする復号途中結果ujの対応する検査行列Hの行において”１”になっている復号途中結果vを６つ同時に読み出し、復号途中結果D410として、サイクリックシフト回路４１１に供給する。
【００６４】
なお、復号途中結果格納用メモリ４１０は、例えば、６つの復号途中結果vを同時に読み書き可能なシングルポートRAMで構成される。また、復号途中結果格納用メモリ４１０には、計算部４１５の第２の演算により演算された列に対応する復号途中結果D415が格納されるので、復号途中結果格納用メモリ４１０に格納されるデータ量、即ち、復号途中結果格納用メモリ４１０に必要とされる記憶容量は、復号途中結果D415の量子化ビット数と、検査行列Hの列数（LDPC符号の符号長）との乗算値である。
【００６５】
サイクリックシフト回路４１１には、復号途中結果格納用メモリ４１０から６つの復号途中結果D410が供給されるとともに、制御部４１７から、その復号途中結果D410に対応する検査行列Hの１が、検査行列Hにおいて元となる単位行列などを幾つサイクリックシフトであるかの情報（Matrixデータ）を表す制御信号D418が供給される。サイクリックシフト回路６１１は、制御信号D418を元に、６つの復号途中結果D410を並べ替えるサイクリックシフトを行い、その結果を復号途中結果D411（D4111乃至D4116）として、計算部４１２に供給する。
【００６６】
計算部４１２は、６つの計算器４１２1乃至４１２6からなる。計算部４１２には、サイクリックシフト回路４１１から、計算部４１５による第２の演算の結果得られた６つの復号途中結果D411（v）が供給されるとともに、復号途中結果格納用メモリ４１３から、前回、計算器４１２1乃至４１２6による第１の演算の結果得られた６つの復号途中結果D413（D4131乃至D4136）（uj）が供給され、その６つの復号途中結果D411と６つの復号途中結果D413が、計算器４１２1乃至４１２6にそれぞれ供給される。また、計算部４１２には、制御部４１７から制御信号D419が供給され、その制御信号D419が、計算器４１２1乃至４１２6に供給される。なお、制御信号D419は、６つの計算器４１２1乃至４１２6に共通の信号である。
【００６７】
計算器４１２1乃至４１２6は、それぞれ復号途中結果D411と復号途中結果D413を用いて、式（７）と式（８）にしたがって第１の演算を行い、復号途中結果D412（D4121乃至D4126）（uj）を求める。計算部４１２は、計算器４１２1乃至４１２6による演算の結果得られる検査行列Hの６つの１に対応する６つの復号途中結果D412を復号途中結果格納用メモリ４１３に供給する。
【００６８】
復号途中結果格納用メモリ４１３は、例えば、６つの復号途中結果D412を同時に読み書き可能な、２つのシングルポートRAMから構成される。復号途中結果格納用メモリ４１３には、計算部４１２から６つの復号途中結果D412が供給されるとともに、制御部４１７から復号途中結果４１３の読み書きを制御する制御信号D420（D4201乃至D4204）が供給される。
【００６９】
復号途中結果格納用メモリ４１３は、制御信号D420に基づいて、計算部４１２から供給される６つの復号途中結果D412をまとめて格納すると同時に、既に格納してある６つの復号途中結果D412を読み出し、復号途中結果D413として、計算部４１２とサイクリックシフト回路４１４に供給する。即ち、復号途中結果格納用メモリ４１３は、計算部４１２とサイクリックシフト回路４１４に供給する復号途中結果D413の読み出しと、計算部４１２から供給される復号途中結果D412の書き込みとを、同時に行う。
【００７０】
なお、復号途中結果格納用メモリ４１３には、計算部４１２の第１の演算により演算された検査行列Hのｉ列の、各行の１に対応する枝からの第１の演算の復号途中結果D412が格納されるので、復号途中結果格納用メモリ４１３に格納されるデータ量、即ち、復号途中結果格納用メモリ４１３に必要とされる記憶容量は、復号途中結果D412の量子化ビット数と、検査行列Hの１の数との乗算値となる。
【００７１】
サイクリックシフト回路４１４には、復号途中結果格納用メモリ４１３から６つの復号途中結果D413（復号途中結果uj）が供給されるとともに、制御部４１７から、その復号途中結果D413に対応する検査行列Hの１が検査行列Hにおいて元となる単位行列などを幾つサイクリックシフトしたものであるかの情報（Matrixデータ）を表す制御信号D421が供給される。サイクリックシフト回路４１４は、制御信号D421を元に、６つの復号途中結果D413を並べ替えるサイクリックシフトを行い、その結果を復号途中結果D414として、計算部４１５に供給する。
【００７２】
計算部４１５は、６つの計算器４１５1乃至４１５6からなる。計算部４１５には、サイクリックシフト回路４１４から６つの復号途中結果D414（D4141乃至D4146）が供給され、その復号途中結果D414が、計算器４１５1乃至４１５6のそれぞれに供給される。また、計算部４１５には、受信用メモリ４１７に記憶されている６つの受信データD416が、受信データD417（LDPC符号）（D4171乃至D4176）として供給され、その受信データD417が、計算器４１５1乃至４１５6のそれぞれに供給される。さらに、計算部４１７には、制御部４１７から制御信号D422が供給され、その制御信号D422が計算器４１５1乃至４１５6に供給される。なお、制御信号D422は、６つの計算器４１７1乃至４１７6に共通の信号である。
【００７３】
計算器４１５1乃至４１５6は、それぞれ復号途中結果D414と受信データD417とを用いて、式（５）にしたがって、それぞれ第２の演算を行い、復号途中結果D415（D4151乃至D4156）を求める。計算部４１５は、計算器４１５1乃至４１５6の第２の演算の結果得られる６つの復号途中結果D415(v)を、復号途中結果格納用メモリ４１０に供給する。また、計算部４１５は、いま行う演算が最後の第２の演算である場合、その演算の結果得られる６つの復号途中結果D415を、最終的な復号結果として出力する。
【００７４】
受信用メモリ４１６は、通信路を通して受信した受信値（符号のビット）U0から計算した符号のビットの０らしさの値である受信LLR（対数尤度比）のデータ（受信データ）D416（ｕ0i）を格納する。
【００７５】
即ち、受信用メモリ４１６の第１のアドレスには、検査行列Hの列に対応する受信データD416のうち、検査行列Hの第１列目から第６列目までに対応する受信データD416が格納される。そして、第２のアドレスには、検査行列Hの第７列目から第１２列目までに対応する受信データD416が格納され、第３アドレスには、検査行列Hの第１３列目から第１８列目までに対応する受信データD416が格納される。以後、同様に、第４アドレスから第１８アドレスまでに、検査行列Hの第１９列目から第１０８列目までに対応する受信データD416が、６つずつ格納される。
【００７６】
そして、受信用メモリ６１６は、既に格納している受信データD416を、バリアブルノード演算に必要となる順番に６つずつ読み出し、受信データD4171乃至D4176として計算部４１５に供給する。
【００７７】
なお、受信用メモリ４１６は、例えば、６つの受信データD416を同時に読み書き可能なシングルポートRAMから構成される。また、受信用メモリ４１６に格納されるデータ量、即ち、受信用メモリ３１５に必要とされる記憶容量は、LDPC符号の符号長と、受信データD416の量子化ビット数との乗算値である。さらに、受信用メモリ４１６のワード（word）数は、LDPC符号の符号長、即ち、検査行列Hの列数である１０８を、同時に読み出す受信データD417（D416）の数である６で割り算した値の１８である。
【００７８】
制御部４１７は、制御信号D418をサイクリックシフト回路４１１に、制御信号D419を計算部４１２に供給することにより、それぞれを制御する。また、制御部４１７は、制御信号D420を復号途中結果格納用メモリ４１３に、制御信号D421をサイクリックシフト回路４１４に、制御信号D422を計算部４１５にそれぞれ供給することにより、それぞれを制御する。
【００７９】
復号途中結果格納用メモリ４１０、サイクリックシフト回路４１１、計算部４１２、復号途中結果格納用メモリ４１３、サイクリックシフト回路４１４、計算部４１５の順で、データが一巡することで、復号装置４００は、１回の復号を行うことができる。復号装置４００では、所定の回数だけ繰り返して復号が行われた後、計算部４１５による第２の演算の結果である復号途中結果D415が、最終的な復号結果として出力される。
【００８０】
図１１は、図１０の計算部４１２の詳細構成例を示すブロック図である。
【００８１】
図１１の計算部４１２には、サイクリックシフト回路４１１から、６つの復号途中結果D4111乃至D4116が供給されるとともに、復号途中結果格納用メモリ４１３から、前回、計算器４１２1乃至４１２6による第１の演算の結果得られた６つの復号途中結果D4131乃至D4136が供給され、その６つの復号途中結果D4111乃至D4116と６つの復号途中結果D4131乃至D4136が、計算器４１２1乃至４１２6にそれぞれ供給される。
【００８２】
また、計算部４１２には、制御部４１７から制御信号D419が供給され、その制御信号D419が、計算器４１２1乃至４１２6に供給される。計算器４１２1乃至４１２6は、それぞれ復号途中結果D411k（ｋ＝1,2,・・・,6）と復号途中結果D413kを用いて、式（７）と式（８）にしたがって第１の演算を行い、復号途中結果D413kを求める。計算部４１２は、計算器４１２1乃至４１２6による演算の結果得られる検査行列Hの６つの１に対応する６つの復号途中結果D4121乃至D4126を復号途中結果格納用メモリ４１３に供給する。
【００８３】
図１２は、図１０の計算部４１２の計算器４１２kの構成例を示すブロック図である。
【００８４】
図１２では、前回の計算部４１２による第１の演算の結果得られる各復号途中結果D412k（D413k）(udv)が符号ビットを合わせて合計６ビット(bit)に量子化され、計算部４１５による第２の演算の結果得られる各復号途中結果D415（D411k）（v）が９ビットに量子化されているものとして、計算器４１２kを表している。さらに、図１２の計算器４１２kには、クロックｃｋが供給され、このクロックｃｋは、必要なブロックに供給されるようになっている。そして、各ブロックは、クロックｃｋに同期して処理を行う。
【００８５】
図１２の計算器４１２kは、制御部４１７から供給される制御信号D419に基づいて、復号途中結果格納用メモリ４１３から１つずつ読み込まれる、前回の計算部４１２による第１の演算の結果得られた復号途中結果D413k（udv）と、サイクリックシフト回路４１１から1つずつ読み込まれる復号途中結果D411k（v）とを用いて、式（７）と式（８）にしたがう第１の演算を行う。
【００８６】
即ち、計算器４１２kには、サイクリックシフト回路４１１から供給される６つの９ビットの復号途中結果D4111乃至D4116(v)のうちの、１つの復号途中結果D411kが供給されるとともに、復号途中結果格納用メモリ４１３から供給される、前回の計算部４１２による演算の結果である６つの６ビットの復号途中結果D4131乃至D4136（uj）のうちの、前回の計算部４１２による演算の結果である１つの復号途中結果D413kが供給され、その９ビットの復号途中結果D411k（v）と６ビットの復号途中結果D413k（udv）が、減算器４３１に供給される。また、計算器４１２kには、制御部４１７から制御信号D419が供給され、その制御信号D419がセレクタ４３５とセレクタ４４２に供給される。
【００８７】
減算器４３１は、９ビットの復号途中結果D411k（v）から６ビットの復号途中結果D413k（uj）を減算し、その６ビットの減算値D431（vi）を出力する。即ち、減算器４３１は、式（８）にしたがって演算を行い、その演算の結果である減算値D431を出力する。
【００８８】
減算器４３１により出力された６ビットの減算値D431のうち、最上位ビットの正負を示す符号ビットD432（sign（vi））がEXOR回路４４０に供給され、下位５ビットの絶対値D433（|vi|）がLUT４３２に供給される。
【００８９】
LUT４３２は、絶対値D433(|vi|)に対して、式（７）におけるφ(|vi|)の演算を行った５ビットの演算結果D434（φ(|vi|)）を読み出し、加算器４３３とFIFOメモリ４３８に供給する。
【００９０】
加算器４３３は、演算結果D434（φ(|vi|)）とレジスタ４３４に格納されている９ビットの値D435とを加算することにより、演算結果D434を積算し、その結果得られる９ビットの積算値をレジスタ４３４に再格納する。なお、検査行列Hの1行に亘る全ての１に対応する復号途中結果D411kから求められた絶対値D433(|vi|)に対する演算結果D434が積算された場合、レジスタ４３４はリセットされる。
【００９１】
検査行列Hの1行に亘る復号途中結果D411kが１つずつ読み込まれ、レジスタ４３４に1行分の演算結果D434が積算された積算値が格納された場合、制御部４１７から供給される制御信号D419は、０から１に変化する。例えば、行の重み（row weight）が「９」である場合、制御信号D419は、１から８クロック目までは、「０」となり、９クロック目では「１」となる。
【００９２】
制御信号D419が「１」の場合、セレクタ４３５は、レジスタ４３４に格納されている値、即ち、検査行列Hの1行に亘る全ての１に対応する復号途中結果D411k（v）から求められたφ(|vi|)が積算された９ビットの値D435（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）を選択し、値D436として、レジスタ４３６に出力して格納させる。レジスタ４３６は、格納している値D436を、９ビットの値D437として、セレクタ４３５と加算器４３７に供給する。制御信号D419が「０」の場合、セレクタ４３５は、レジスタ４３６から供給された値D437を選択し、レジスタ４３６に出力して再格納させる。即ち、検査行列Hの1行に亘る全ての１に対応する復号途中結果D411k（v）から求められたφ(|vi|)が積算されるまで、レジスタ４３６は、前回積算されたφ(|vi|)を、セレクタ４３５と加算器４３７に供給する。
【００９３】
一方、FIFOメモリ４３８は、レジスタ４３６から新たな値D437（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）が出力されるまでの間、LUT４３２が出力した演算結果D434（φ(|vi|)）を遅延し、５ビットの値D438として減算器４３７に供給する。減算器４３７は、レジスタ４３６から供給された値D437から、FIFOメモリ４３８から供給された値D438を減算し、その減算結果を、５ビットの減算値D439としてLUT４３９に供給する。即ち、減算器４３７は、検査行列Hの1行に亘る全ての１に対応する復号途中結果D411k（v）から求められたφ(|vi|)の積算値から、求めたい枝に対応する復号途中結果、即ち、検査行列Hの所定の１に対応する復号途中結果D411k（v）から求められたφ(|vi|)を減算して、その減算値（ｉ＝１からｉ＝ｄc−１までのΣφ(|vi|)）を減算値D439としてLUT４３９に供給する。
【００９４】
LUT４３９は、減算値D439（ｉ＝１からｉ＝ｄc−１までのΣφ(|vi|)）に対して、式（７）におけるφ-1（Σφ(|vi|)）の演算を行った５ビットの演算結果D440（φ-1(Σφ(|vi|)))を出力する。
【００９５】
以上の処理と並行して、EXOR回路４４０は、レジスタ４４１に格納されている１ビットの値D442と符号ビットD432との排他的論理和を演算することにより、符号ビットどうしの乗算を行い、１ビットの乗算結果D441をレジスタ４４１に再格納する。なお、検査行列Hの1行に亘る全ての１に対応する復号途中結果D411kから求められた符号ビットD432が乗算された場合、レジスタ４４１はリセットされる。
【００９６】
検査行列Hの1行に亘る全ての１に対応する復号途中結果D411から求められた符号ビットD432が乗算された乗算結果D441（ｉ＝１からｄcまでのΠsign(vi)）がレジスタ４４１に格納された場合、制御部４１７から供給される制御信号D419は、「０」から「１」に変化する。
【００９７】
制御信号D419が「１」の場合、セレクタ４４２は、レジスタ４４１に格納されている値、即ち、検査行列Hの1行に亘る全ての１に対応する復号途中結果D411kから求められた符号ビットD432が乗算された値D442（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）を選択し、１ビットの値D443としてレジスタ４４３に出力して格納させる。レジスタ４４３は、格納している値D443を、１ビットの値D444としてセレクタ４４２とEXOR回路４４５に供給する。制御信号D419が「０」の場合、セレクタ４４２は、レジスタ４４３から供給された値D444を選択し、レジスタ４４３に出力して再格納させる。即ち、検査行列Hの1行に亘る全ての１に対応する復号途中結果D411k（v）から求められた符号ビットD432が乗算されるまで、レジスタ４４３は、前回格納した値を、セレクタ４４２とEXOR回路４４５に供給する。
【００９８】
一方、FIFOメモリ４４４は、レジスタ４４３から新たな値D444（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）がEXOR回路４４５に供給されるまでの間、符号ビットD432を遅延し、１ビットの値D445としてEXOR回路４４５に供給する。EXOR回路４４５は、レジスタ４４３から供給された値D444と、FIFOメモリ４４４から供給された値D445との排他的論理和を演算することにより、値D444を、値D445で除算し、１ビットの除算結果を除算値D446として出力する。即ち、EXOR回路４４５は、検査行列Hの1行に亘る全ての１に対応する復号途中結果D411kから求められた符号ビットD432（sign(vi)）の乗算値を、検査行列Hの所定の１に対応する復号途中結果D411kから求められた符号ビットD432（sign(vi)）で除算して、その除算値（ｉ＝１からｉ＝ｄc−１までのΠsign(vi)）を除算値D446として出力する。
【００９９】
計算器４１２kでは、LUT４３９から出力された５ビットの演算結果D440を下位５ビットとするとともに、EXOR回路４４５から出力された１ビットの除算値D446を最上位ビットとする合計６ビットが復号途中結果D412k（uj）として出力される。
【０１００】
以上のように、計算器４１２kでは、式（７）と式（８）の演算が行われ、復号途中結果ujが求められる。
【０１０１】
なお、図９の検査行列Hの行の重みの最大は９であるため、即ち、計算器４１２kに供給される復号途中結果D411k（v）と復号途中結果D413k（udv）の最大数は９であるため、計算器４１２kは、９個の復号途中結果D411kから求められる９個の演算結果D434（φ(|vi|)）を遅延させるFIFOメモリ４３８と、９個の符号ビットD432を遅延させるFIFOメモリ４４４を有している。行の重みが９未満の行のメッセージを計算するときには、FIFOメモリ４３８とFIFOメモリ４４４における遅延量が、その行の重みの値に減らされる。
【０１０２】
以上のように、図１２の計算器４１２kでは、FIFOメモリ４３８と４４４が、演算結果D434または符号ビットD432を格納することにより遅延を行うため、チェックノード次数（検査行列Hの行の重み）が大きい場合、FIFOメモリ４３８と４４４以外の演算を行う論理回路に比べて、FIFOメモリ４３８と４４４を構成するメモリの回路規模が膨大になる。
【０１０３】
例えば、各計算器４１２kのFIFOメモリ４３８と４４４がシフトレジスタを用いて構成される場合、FIFOメモリ４３８と４４４は、格納する演算結果D434または符号ビットD432のビット数分のフリップフロップを必要とし、回路規模が膨大になる。また、FIFOメモリ４３８と４４４が、FIFOやRAM（Random Access Memory）などのメモリマクロを用いて構成される場合、一般的に、小さいメモリマクロは、格納する演算結果D434または符号ビットD432のビット数に対して相対的に大きくなるため、回路規模が膨大になる。
【０１０４】
図１３は、図１０の計算部４１５の計算器４１５kの構成例を示すブロック図である。
【０１０５】
なお、図１３では、計算部４１２による第１の演算の結果得られる各復号途中結果D412k（D414k）（uj）が符号ビットを合わせて合計６ビットに量子化されているものとして、計算器４１５kを表している。さらに、図１３の計算器４１５kには、クロックｃｋが供給され、このクロックｃｋは、必要なブロックに供給されるようになっている。そして、各ブロックは、クロックｃｋに同期して処理を行う。
【０１０６】
図１３の計算器４１５kは、制御部４１７から供給される制御信号D422に基づいて、受信用メモリ４１６から１つずつ読み込まれる受信データD417k（u0i）と、サイクリックシフト回路４１４から１つずつ読み込まれる復号途中結果D414k（uj）とを用いて、式（５）にしたがう第２の演算を行う。
【０１０７】
即ち、計算器４１５kでは、サイクリックシフト回路４１４から、検査行列Hの各行の１に対応する６ビットの復号途中結果D414k（uj）が１つずつ読み込まれ、その復号途中結果D414が、加算器４７１に供給される。また、計算器４１５kでは、受信用メモリ４１６から６ビットの受信データD417kが１つずつ読み込まれ、加算器４７５に供給される。さらに、計算器４１５kには、制御部４１７から制御信号D422が供給され、その制御信号D422は、セレクタ４７３に供給される。
【０１０８】
加算器４７１は、復号途中結果D414k（uj）とレジスタ４７２に格納されている９ビットの値D471とを加算することにより、復号途中結果D414kを積算し、その結果得られる９ビットの積算値を、レジスタ４７２に再格納する。なお、検査行列Hの１列に亘る全ての１に対応する復号途中結果D414kが積算された場合、レジスタ４７２はリセットされる。
【０１０９】
検査行列Hの１列に亘る復号途中結果D414kが１つずつ読み込まれ、レジスタ４７２に１列分の復号途中結果D414kが積算された値が格納された場合、制御部４１７から供給される制御信号D422は、「０」から「１」に変化する。例えば、列の重みが「５」である場合、制御信号D422は、１から４クロック目までは「０」となり、５クロック目では「１」となる。
【０１１０】
制御信号D422が「１」の場合、セレクタ４７３は、レジスタ４７２に格納されている値、即ち、検査行列Hの１列に亘る全ての枝からの復号途中結果D414k（uj）が積算された９ビットの値D471（ｊ＝１からｄVまでのΣuj)を選択し、レジスタ４７４に出力して格納させる。レジスタ４７４は、格納している値D471を、９ビットの値D472として、セレクタ４７３と加算器４７５に供給する。制御信号D422が「０」の場合、セレクタ４７３は、レジスタ４７４から供給された値D472を選択し、レジスタ４７４に出力し再格納させる。即ち、検査行列Hの１列に亘る全ての枝からの復号途中結果D414k（uj）が積算されるまで、レジスタ４７４は、前回積算された値を、セレクタ４７３と加算器４７５に供給する。
【０１１１】
加算器４７５は、９ビットの値D472と、受信用メモリ４１６から供給された６ビットの受信データD417kとを加算して、その結果得られる６ビットの値を復号途中結果D415k（v）として出力する。
【０１１２】
以上のように、計算器４１５kでは、式（５）の演算が行われ、復号途中結果vが求められる。
【０１１３】
なお、図９の検査行列Hの列の重みの最大は５であるため、即ち、計算器４１５kに供給される復号途中結果ujの最大数は５であるため、計算器４１５kは、６ビットの復号途中結果ujを最大５個加算する。従って、計算器４１５kの出力は、９ビットの値となっている。
【０１１４】
図１４は、図１０の復号途中結果格納用メモリ４１３の構成例を示すブロック図である。
【０１１５】
復号途中結果格納用メモリ４１３は、スイッチ５０１と５０４、および２つのシングルポートRAMである復号途中結果格納用RAM５０２と５０３から構成される。
【０１１６】
この復号途中結果格納用メモリ４１３の各部について詳細に説明する前に、まず、復号途中結果格納用RAM５０２と５０３へのデータの格納方法について説明する。
【０１１７】
復号途中結果格納用RAM５０２と５０３は、計算部４１２による第１の演算の結果得られ、スイッチ５０１を介して供給された６つの復号途中結果D412（D4121乃至D4126）（uj）を格納する。
【０１１８】
具体的には、復号途中結果格納用RAM５０２の第１アドレスから第９アドレスには、図９の検査行列Hの第１行目から第６行目までの１に対応する復号途中結果D412(D501)が、各行ともに横方向（列方向）に詰めた形に（０を無視した形で）格納される。
【０１１９】
即ち、第ｊ行第ｉ列を、(j,ｉ)と表すこととすると、復号途中結果格納用RAM５０２の第１アドレスには、図９の検査行列Hの構成行列である(1,1)から(6,6)の６×６の単位行列の１に対応するデータが、第２アドレスには、図９の検査行列Hの構成行列である(1,25)から(6,30)のシフト行列（６×６）の単位行列を右方向に５つだけサイクリックシフトしたシフト行列）の１に対応するデータが格納される。第３アドレスから第８アドレスも同様に図９の検査行列Hの構成行列と対応づけてデータが格納される。そして、第９アドレスには、検査行列Hの(1,102)から(6,108)のシフト行列（６×６の単位行列のうちの１行目の１を０に置き換えて１つだけ左方向にサイクリックシフトしたシフト行列）の１に対応するデータが格納される。ここで、図９の検査行列Hの(1,102)から(6,108)のシフト行列においては、１行目に１がないため、第９アドレスにはデータが格納されない。
【０１２０】
また、復号途中結果格納用RAM５０２の第１０アドレスから第１８アドレスには、図９の検査行列Hの第１３行目から第１８行目までの１に対応するデータが格納される。即ち、第１０アドレスには、検査行列Hの(13,7)から(18,12)の６×６の単位行列を右方向に５つだけサイクリックシフトした行列の１に対応するデータが格納され、第１１アドレスには、検査行列Hの(13,13)から（18,18）の和行列（６×６の単位行列と、６×６の単位行列を右方向に１つだけサイクリックシフトしたシフト行列との和である和行列）を構成するシフト行列の１に対応するデータが格納される。また、第１２アドレスには、検査行列Hの(13,13)から（18,18）の和行列を構成する単位行列の１に対応するデータが格納される。以下、第１３アドレスから第１８アドレスについても、検査行列Hに対応づけてデータが格納される。
【０１２１】
即ち、重みが２以上の構成行列については、その構成行列を、重みが１であるP×Pの単位行列、そのコンポーネントである１のうち１個以上が０になった準単位行列、または単位行列もしくは準単位行列をサイクリックシフトしたシフト行列のうちの複数の和の形で表現したときの、その重みが１の単位行列、準単位行列、またはシフト行列の１の位置に対応するデータ（単位行列、準単位行列、またはシフト行列に属する枝に対応するメッセージの復号途中結果D501）は、同一アドレスに格納される。
【０１２２】
同様に、復号途中結果格納用RAM５０２の第１９アドレスから第２７アドレスには、図９の検査行列Hに対応づけて、第２５行目から第３０行目までの１に対応するデータが格納される。即ち、復号途中結果格納用RAM５０２のワード数は、２７である。
【０１２３】
復号途中結果格納用RAM５０３の第１アドレスから第９アドレスには、図９の検査行列Hの第７行目から第１２行目までの１に対応する復号途中結果D412(D502)が、各行ともに横方向（列方向）に詰めた形に（０を無視した形で）格納される。
【０１２４】
即ち、復号途中結果格納用RAM５０３の第１アドレスには、検査行列Hの構成行列である(7,1)から(12,6)の和行列（６×６の単位行列を右方向に２つだけサイクリックシフトした第１のシフト行列と、右方向に４つだけサイクリックシフトした第２のシフト行列の和である和行列）を構成する第１のシフト行列の１に対応するデータが、第２アドレスには、検査行列Hの構成行列である(7,1)から(12,6)の和行列を構成する第２のシフト行列の１に対応するデータが格納される。以下、第３アドレスから第９アドレスも同様に検査行列Hの構成行列と対応づけてデータが格納される。
【０１２５】
同様に、復号途中結果格納用RAM５０３の第１０アドレスから第１８アドレスには、図９の検査行列Hの第１９行目から第２４行目までの１に対応するデータが、第１９アドレスから第２７アドレスには、検査行列Hの第３１行目から第３６行目までの1に対応するデータが、図９の検査行列Hに対応づけて格納される。即ち、復号途中結果格納用RAM５０３のワード数は、２７である。
【０１２６】
上述したように、復号途中結果格納用RAM５０２と５０３のワード(word)数は、２７である。即ち、ワード数は、検査行列Hの行の重み(row weight)の９と行数の３６とを乗算し、その乗算結果(検査行列Hの１の数)を、同時に読み出す復号途中結果D413kの数の６で除算し、さらに、復号途中結果格納用メモリ４１３が有する復号途中結果格納用RAMの個数の２で除算した値となる。
【０１２７】
以下、図１４の復号途中結果格納用メモリ４１３の各部の動作について詳細に説明する。
【０１２８】
復号途中結果格納用メモリ４１３には、計算部４１２により第１の演算が行われる場合、計算部４１２から第１の演算の結果得られる６つの復号途中結果D412（uj）が供給され、その復号途中結果D412が復号途中結果格納用RAM５０２または復号途中結果格納用RAM５０３のうちの一方の所定のアドレスに書き込まれると同時に、他方から、前回の計算部４１２による第１の演算の結果得られた復号途中結果D412（uj）が読み出され、復号途中結果D413kとして計算部４１２に出力される。一方、計算部４１５により第２の演算が行われる場合、復号途中結果格納用メモリ４１３は、復号途中結果格納用RAM５０２または復号途中結果格納用RAM５０３に書き込みを行わず、どちらか一方のRAMの所定のアドレスから復号途中結果D503またはD504を読み出して、復号途中結果D413としてサイクリックシフト回路４１４に供給する。
【０１２９】
スイッチ５０１には、計算部４１２から６つの復号途中結果D412が供給されるとともに、その復号途中結果D412を書き込むメモリとして、復号途中結果格納用RAM５０２または復号途中結果格納用RAM５０３の一方の選択を表す制御信号D4201が制御部４１７から供給される。スイッチ５０１は、制御信号D4201に基づいて、復号途中結果格納用RAM５０２または復号途中結果格納用RAM５０３の一方を選択し、その選択した一方に、６つの復号途中結果D412を供給する。
【０１３０】
復号途中結果格納用RAM５０２には、スイッチ５０１から６つの復号途中結果D412が、復号途中結果D501として供給されるとともに、制御部４１７からアドレスを表す制御信号D4202が供給される。復号途中結果格納用RAM５０２は、制御信号D4202が表すアドレスに既に格納されている前回の計算部４１２による第１の演算の結果得られた６つの復号途中結果D501を読み出し、復号途中結果D503としてスイッチ５０４に供給する。また、復号途中結果格納用RAM５０２は、制御信号D4202が表すアドレスに、スイッチ５０１から供給された６つの復号途中結果D501を格納する(書き込む)。
【０１３１】
復号途中結果格納用RAM５０３には、スイッチ５０１から６つの復号途中結果D412が、復号途中結果D502として供給されるとともに、制御部４１７からアドレスを表す制御信号D4203が供給される。復号途中結果格納用RAM５０３は、制御信号D4203が表すアドレスに既に格納されている前回の計算部４１２による第１の演算の結果得られた６つの復号途中結果D502を読み出し、復号途中結果D504としてスイッチ５０４に供給する。また、復号途中結果格納用RAM５０３は、制御信号D4203が表すアドレスに、スイッチ５０１から供給された６つの復号途中結果D502を格納する(書き込む)。
【０１３２】
スイッチ５０４には、復号途中結果格納用RAM５０２から復号途中結果D503が供給されるか、あるいは復号途中結果格納用RAM503から復号途中結果D504が供給される。また、制御部４１７から、復号途中結果格納用RAM５０２または復号途中結果格納用RAM５０３の一方の選択を表す制御信号D4204が供給される。スイッチ５０４は、制御信号D4204に基づいて、復号途中結果格納用RAM５０２または復号途中結果格納用RAM５０３の一方を選択し、その選択した一方から供給された６つの復号途中結果D503またはD504を、６つの復号途中結果D413として計算部４１２とサイクリックシフト回路４１４に供給する。
【０１３３】
ところで、近年、連接符号の内符号の復号出力や繰り返し復号法の各繰り返しの出力を軟出力とすることで、シンボル誤り確率を小さくする研究がなされており、それに適した復号方法としてBCJRアルゴリズムが注目されている。
【０１３４】
そこで、チェックノード演算を行う方法として、上述したGallagerにより提案されたLDPC符号の復号アルゴリズムではなく、検査行列Hの１行に対応するLDPC符号を１つのパリティ検査符号とみなして、そのパリティ検査符号の２つのステート(遷移状態)のトレリスに基づいて、Bahlらにより提案されたBCJRアルゴリズムを適用する方法が考案されている(例えば、非特許文献１参照)。
【０１３５】
BCJRアルゴリズムにおいては、復号結果として各シンボルを出力するのではなく、各シンボルの尤度を出力することができる。即ち、軟出力（Soft-output）を行うことができる。
【０１３６】
以下、BCJRアルゴリズムについて説明する。
【０１３７】
まず最初に、トレリス線図で表すことが可能な符号(以下、トレリス符号という)のＭ個のステートをｍ(=0,1,・・・,M-1)とし、時刻ｔのステートをＳtとする。また、時刻ｔにおける入力をｉt、出力をＸt、出力系列をＸt´t（=Ｘt,Ｘt+1,・・・,Ｘt´）とする。このとき、時刻ｔにおける各ステート間の遷移確率ｐt（m|m´）は、以下の式（９）で表される。
【０１３８】
【数９】
0004730592.tif 000010
・・・（９）
【０１３９】
なお、Pr｛A|B｝は、Ｂが起こった条件のもとでのＡが起こる条件付き確率を表すものとする。また、トレリス符号化は、ステートS0（=0）から始まり、出力系列Ｘτ1を出力して、ステートSτ（=0）で終了するものとする。
【０１４０】
トレリス符号化を行う符号化装置が出力する出力系列Ｘτ1は、雑音のある無記憶通信路を介して、受信語Ｙτ1（=Ｙt,Ｙt+1,・・・,Ｙt´）として、トレリス復号を行う復号装置で受信される。即ち、雑音のある無記憶通信路では、出力系列Ｘτ1が入力され、受信語Ｙτ1が復号装置に出力される。このとき、雑音のある無記憶通信路の遷移確率は、すべてのｔ（1≦t≦τ）について、以下の式（１０）を満たすＷによって定義される。
【０１４１】
【数１０】
0004730592.tif 000011
・・・（１０）
【０１４２】
いま、λtを以下の式（１１）で定義すると、λtは受信語Ｙτ1が復号装置で受信されたときの、時刻ｔでの入力ｉtの尤度を表し、復号装置で復号結果として出力される軟出力となる。
【０１４３】
【数１１】
0004730592.tif 000012
・・・（１１）
【０１４４】
ここで、確率αt（ｍ）,βt（ｍ）、およびγt（ｍ´,ｍ,ｉ）を、以下の式（１２）乃至（１４）で定義する。
【０１４５】
【数１２】
0004730592.tif 000013
・・・（１２）
【０１４６】
【数１３】
0004730592.tif 000014
・・・（１３）
【０１４７】
【数１４】
0004730592.tif 000015
・・・（１４）
【０１４８】
なお、Pr｛A；B｝はＡとＢが共に起こる確率を表すものとする。
【０１４９】
図１５に示すように、式（１２）で定義された確率αt-1（ｍ）は、トレリス符号化が開始されるときのステートS0（=0）から、復号装置で受信される受信語Ｙt1を基に、時系列順に算出した時刻t-1における各ステートｍの通過確率を表している。
【０１５０】
また、式（１３）で定義された確率βt（ｍ）は、トレリス符号化が終了するときのステートSτ（=0）から、復号装置で受信される受信語Ｙτt+1を基に、時系列の逆順に算出した時刻ｔにおける各ステートｍの通過確率を表している。
【０１５１】
さらに、式（１４）で定義された確率γt（ｍ´,ｍ,ｉ）は、時刻ｔにおける受信語Ｙtと入力ｉtの確率を基に算出した、時刻ｔにステートｍとｍ´間を遷移する各枝の出力の受信確率を表している。
【０１５２】
ここで、確率αt（ｍ）,βt（ｍ）、およびγt（ｍ´,ｍ,ｉ）を用いると、軟出力λtは、以下の式（１５）で表される。
【０１５３】
【数１５】
0004730592.tif 000016
・・・（１５）
【０１５４】
また、確率αt（ｍ）,βt（ｍ）、およびγt（ｍ´,ｍ,ｉ）は、以下の式（１６）乃至（１８）でも表される。
【０１５５】
【数１６】
0004730592.tif 000017
・・・（１６）
【０１５６】
【数１７】
0004730592.tif 000018
・・・（１７）
【０１５７】
【数１８】
0004730592.tif 000019
・・・（１８）
【０１５８】
従って、復号装置では、式（１５）乃至（１８）を用いて、軟出力λtを求めることができる。具体的には、まず最初に、復号装置は、受信語Ｙtを受信するごとに、式（１６）と式（１８）を用いて、確率γt（ｍ´,ｍ,ｉ）とαt（ｍ）を求める。そして、復号装置は、受信語Ｙτ1をすべて受信した後、式（１７）を用いて、すべての時刻ｔ,ステートｍについて、確率βt（ｍ）を求める。最後に、復号装置は、式（１５）を用いて、軟出力λtを求める。以上のようにして、BCJRアルゴリズムでは、軟出力λtが求められる。
【０１５９】
次に、BCJRアルゴリズムを適用してチェックノード演算を行う方法について説明する。
【０１６０】
図１６は、符号長が７のパリティ検査符号のトレリスを示している。
【０１６１】
図１６に示すように、トレリス符号化が開始されるときのステートS0は０である。また、トレリスの時刻ｔ（図１６の場合、ｔ=0,1,・・・,7）（トレリスセクション）に対応するパリティ検査符号の符号ビットが０である場合、ステートStは前のステートｍと同一のステートｍに留まり（St=St-1）、符号ビットが１である場合、ステートStは前のステートｍと異なるステートｍに遷移する（St≠St-1）。そして、最後のステートであるステートＳ7は０となる。即ち、パリティ検査符号の「１」の数は、偶数である。
【０１６２】
図１６のトレリスでは、確率αtとβtは、上述した式（１２）と（１３）で表される。一方、パリティ検査符号のビットが１である確率とステートｍが遷移する確率が等しいので、確率γtは、以下の式（１９）で定義される。
【０１６３】
【数１９】
0004730592.tif 000020
・・・（１９）
【０１６４】
従って、図１６のトレリスでは、上述した式（１２）、（１３）、および（１９）を用いて、軟出力λtを求めることができる。
【０１６５】
ここで、Δαt,Δβt、Δγt、Δλt、およびＱを、確率αt,βt、およびγtの対数を用いて、以下の式（２０）乃至（２４）で定義する。
【０１６６】
【数２０】
0004730592.tif 000021
・・・（２０）
【０１６７】
【数２１】
0004730592.tif 000022
・・・（２２）
【０１６８】
【数２２】
0004730592.tif 000023
・・・（２２）
【０１６９】
【数２３】
0004730592.tif 000024
・・・（２３）
【０１７０】
【数２４】
0004730592.tif 000025
・・・（２４）
【０１７１】
このとき、ΔαとΔβの更新式は、以下の式（２５）と（２６）で表される。
【０１７２】
【数２５】
0004730592.tif 000026
・・・（２５）
【０１７３】
【数２６】
0004730592.tif 000027
・・・（２６）
【０１７４】
また、外部情報（Extrinsic Information）ΔλEtは以下の式（２７）で表される。
【０１７５】
【数２７】
0004730592.tif 000028
・・・（２７）
【０１７６】
外部情報ΔλEtは、式（２４）のＱを再帰的に用いて以下の式（２８）で表すことができる。
【０１７７】
【数２８】
0004730592.tif 000029
・・・（２８）
【０１７８】
ここで、Ｑ(x,y)については、以下の式（２９）が成り立つ。
【０１７９】
【数２９】
0004730592.tif 000030
・・・（２９）
【０１８０】
そこで、式（２８）のΔγ0,・・・, Δγt-1,Δγt+1,・・・,Δγτ―1をメッセージv1,・・・, vdc-1に、外部情報ΔλEtをメッセージujに置換し、置換後の式（２８）を、式（２９）を用いて変形すると、メッセージujは、以下の式（３０）で表される。
【０１８１】
【数３０】
0004730592.tif 000031
・・・（３０）
【０１８２】
なお、式（２４）のＱ(x,y)は式（３）のＲ(x,y)と等しいため、式（３０）は、上述した式（４）と等価である。従って、復号装置は、Δγtをメッセージviとするとともに、外部情報ΔλEtをメッセージujとして、式（２７）で表される外部情報ΔλEt(メッセージuj)の演算を行うことにより、BCJRアルゴリズムを用いて、チェックノード演算を行うことができる。
【０１８３】
次に、図１７を参照して、BCJRアルゴリズムを用いてチェックノード演算を行う復号装置６００について説明する。
【０１８４】
図１７は、復号装置６００の構成の一例を示している。なお、図１０と同一のものには同一の符号を付してあり、説明は適宜省略する。
【０１８５】
図１７の復号装置６００は、復号途中結果格納用メモリ４１０、サイクリックシフト回路４１１、復号途中結果格納用メモリ４１３、サイクリックシフト回路４１４、６つの計算器４１５1乃至計算器４１５6からなる計算部４１５、および受信用メモリ４１６が設けられている点で、図１０の復号装置４００と共通するが、６つの計算器６１１1乃至計算器６１１6からなる計算部６１１と制御部６１２が新たに設けられている点で、図１０の復号装置４００と異なっている。
【０１８６】
計算部６１１は、６つの計算器６１１1乃至６１１6からなる。計算部６１１には、サイクリックシフト回路４１１から、計算部４１５による第２の演算の結果得られた６つの復号途中結果D4111乃至D4116（v）が供給されるとともに、復号途中結果格納用メモリ４１３から、前回、計算器４１２1乃至４１２6による第１の演算の結果得られた６つの復号途中結果D413（D4131乃至D4136）（uj）が供給され、復号途中結果D411kと復号途中結果D413kが、計算器４１２1乃至４１２6にそれぞれ供給される。
【０１８７】
また、計算部６１１には、制御部６１２から制御信号D611とD612が供給され、その制御信号D611とD612が、計算器６１１1乃至６１１6に供給される。なお、制御信号D611とD612は、６つの計算器６１１1乃至６１１6に共通の信号である。
【０１８８】
各計算器６１１kは、復号途中結果D411kと復号途中結果D413kを用いて、BCJRアルゴリズムに基づく式（２５）乃至式（２７）にしたがうチェックノード演算と、式（８）の演算とからなる第３の演算を行い、復号途中結果D412（D4121乃至D4126）（uj）を求める。計算部６１１は、計算器６１１1乃至６１１6による演算の結果得られる検査行列Hの６つの１に対応する６つの復号途中結果D4121乃至D4126を、復号途中結果格納用メモリ４１３に供給する。
【０１８９】
制御部６１２は、制御信号D418をサイクリックシフト回路４１１に、制御信号D611とD612を計算部６１１に供給することにより、それぞれを制御する。また、制御部６１２は、制御信号D420を復号途中結果格納用メモリ４１３に、制御信号D421をサイクリックシフト回路４１４に、制御信号D422を計算部４１５にそれぞれ供給することにより、それぞれを制御する。
【０１９０】
図１８は、図１７の計算部６１１の計算器６１１kの構成例を示すブロック図である。
【０１９１】
図１８の計算器６１１kは、制御部６１２から供給される制御信号D611に基づいて、復号途中結果格納用メモリ４１３から１つずつ読み込まれる、前回の計算部６１１による第１の演算の結果得られた復号途中結果D413k（udv）と、サイクリックシフト回路４１１から1つずつ読み込まれる復号途中結果D411k（v）とを用いて、式（２５）乃至式（２８）にしたがうチェックノード演算と、式（８）にしたがう演算とからなる第３の演算を行う。
【０１９２】
即ち、計算器６１１kには、サイクリックシフト回路４１１から供給される６つの復号途中結果D4111乃至D4116(v)のうちの、１つの復号途中結果D411kが供給されるとともに、復号途中結果格納用メモリ４１３から供給される、前回の計算部６１１による演算の結果である６つの復号途中結果D4131乃至D4136（uj）のうちの、前回の計算部６１１による演算の結果である１つの復号途中結果D413kが供給され、その復号途中結果D411k（v）と６ビットの復号途中結果D413k（udv）が、減算器６３１に供給される。また、計算器６１１１kには、制御部６１２から制御信号D611とD612が供給され、その制御信号D611がセレクタ６３３と６４０に供給され、制御信号D612がセレクタ６３７に供給される。
【０１９３】
減算器６３１は、復号途中結果D411k（v）から復号途中結果D413k（uj）を減算し、その減算値D621を出力する。即ち、減算器４３１は、式（８）にしたがって演算を行い、その演算の結果である減算値D621（vi）（Δγt）を出力する。減算器６３１により出力された減算値D621は、Ｑ演算回路６３２、セレクタ６３３、およびLIFO（Last In First Out）メモリ６３８に供給される。
【０１９４】
Ｑ演算回路６３２は、減算器６３１からの減算値D621と、レジスタ６３４から供給される値D624（Δαt）とを用いて、式（２５）にしたがう演算（Ｑ（Δαt-1,Δγt-1））（以下、α演算という）を行い、その結果得られる演算結果D622(Δαt)をセレクタ６３３に供給する。
【０１９５】
検査行列Hの1行に亘る復号途中結果D411kが１つ読み込まれ、最初の復号途中結果D411kの減算値D621が減算器６３１から出力される場合、制御部６１２から供給される制御信号D611は、０から１に変化する。例えば、行の重みが「６」である場合、制御信号D611は、１クロック目が、「１」となり、２乃至６クロック目では「０」となる。
【０１９６】
制御信号D611が「１」の場合、セレクタ６３３は、減算器６３１からの減算値D621（Δγ1）を選択し、値D623（Δα1）として、レジスタ６３３に出力して格納させる。一方、制御信号D611が「０」の場合、セレクタ６３３は、Ｑ演算回路６３２から供給された演算結果D622を選択し、値D623としてレジスタ６３４に出力して格納させる。
【０１９７】
レジスタ６３４は、セレクタ６３３からの値D623をＱ演算回路６３２とLIFOメモリ６３５に供給する。LIFOメモリ６３５は、例えば、シフトレジスタを用いて構成され、少なくともチェックノード次数（Check node degree）と量子化ビット数とを乗算した値分のフリップフロップを必要とする。
【０１９８】
LIFOメモリ６３５は、レジスタ６３４からの値D623を記憶する。LIFOメモリ６３５は、既に記憶している、検査行列Hの１行に対応する値D623（同一のチェックノードに属する値D623）を、入力された順番とは逆の順番で最後に記憶されたものから順に、値D625としてＱ演算器６３６とセレクタ６３７に供給する。
【０１９９】
Ｑ演算器６３６は、LIFOメモリ６３５からの値D625（Δγt）と、レジスタ６４１からの値D630と（Δβt-1）を用いて、式（２８）にしたがう演算（Ｑ（Δαt,Δβt+1））（以下、λE演算という）を行い、その演算の結果得られる演算結果D626（外部情報ΔλEt）をセレクタ６３７に供給する。
【０２００】
以上の処理と並行して、LIFOメモリ６３８は、減算器６３１からの減算値D621を記憶する。なお、LIFOメモリ６３８は、LIFOメモリ６３５と同様に、例えば、シフトレジスタを用いて構成され、少なくともチェックノード次数（Check node degree）と量子化ビット数とを乗算した値分のフリップフロップを必要とする。
【０２０１】
LIFOメモリ６３８は、既に記憶している、検査行列Hの１行に対応する減算値D621を、入力された順番とは逆の順番で最後に記憶されたものから順に、値D627としてＱ演算器６３９とセレクタ６４０に供給する。
【０２０２】
Ｑ演算回路６３９は、LIFOメモリ６３８から値D627（Δγt）と、レジスタ６４０から供給される値D630（Δβt+1）とを用いて、式（２６）にしたがう演算（Ｑ（Δβt+1,Δγt））（以下、β演算という）を行い、その結果得られる演算結果D628(Δβt)をセレクタ６４０に供給する。
【０２０３】
制御信号D611が「１」の場合、即ち検査行列Hの1行に亘る復号途中結果D411kのうちの、最後に計算器６１１kに供給される復号途中結果D411kに対応する値D627がLIFOメモリ６３８から出力される場合、セレクタ６４０は、LIFOメモリ６３８からの値D627（Δγτ-1）を選択し、値D629（Δβτ-1）として、レジスタ６４１に出力して格納させる。一方、制御信号D611が「０」の場合、セレクタ６４０は、Ｑ演算回路６３９から供給された演算結果D628を選択し、値D629としてレジスタ６４１に出力して格納させる。
【０２０４】
レジスタ６４１は、セレクタ６４０からの値D629を、値D630としてＱ演算回路６３６と６３９、並びにセレクタ６３７に供給する。
【０２０５】
検査行列Hの1行に亘る復号途中結果D411が１つ供給され、最初の復号途中結果D411kに対応する値D630がレジスタ６４１から出力される場合、制御部６１２から供給される制御信号D612は、０から１に変化する。次に、検査行列Hの１行に亘る復号途中結果D411kが１つずつ供給され、最後の復号途中結果D411に対応する値D625がLIFOメモリ６３５から出力されるまで、制御信号D612は０となる。そして、最後の復号途中結果D411kに対応する値D625がLIFOメモリ６３５から出力される場合、制御信号D612は２となる。
【０２０６】
制御信号D612が「１」の場合、セレクタ６３７は、レジスタ６４１からの値D625（Δα1）を選択し、値D631（ΔλE1）として、レジスタ６４２に出力して格納させる。また、制御信号D612が「０」の場合、セレクタ６３７は、Ｑ演算回路６３２から供給された演算結果D626を選択し、値D631としてレジスタ６３４に出力して格納させる。さらに、制御信号D612が「２」の場合、セレクタ６３７は、LIFOメモリ６３５からの値D630（Δβτ―1）を選択し、値D631（ΔλEτ-1）として、レジスタ６４２に出力して格納させる。
【０２０７】
レジスタ６４２は、セレクタ６３７からの値D631（外部情報ΔλEt）を記憶する。レジスタ６４２は、既に記憶している値D631を、復号途中結果D412k（uj）として出力する。
【０２０８】
以上のように、計算器６１１kでは、第３の演算が行われ、復号途中結果ujが求められる。
【０２０９】
上述したように、図１８の計算器６１１kでは、LIFOメモリ６３５と６３８が、値D624または減算値D621を格納することにより入出力の順番を逆にするため、チェックノード次数が大きい場合、LIFOメモリ６３５と６３８以外の演算を行う論理回路に比べて、LIFOメモリ６３５と６３８を構成するメモリの回路規模が膨大になる。
【０２１０】
例えば、各計算器６１１kのLIFOメモリ６３５と６３８がシフトレジスタを用いて構成される場合、LIFOメモリ６３５と６３８は、格納する値D624または減算値D621のビット数分のフリップフロップを必要とし、回路規模が膨大になる。また、LIFOメモリ６３５と６３８が、LIFOやRAMなどのメモリマクロを用いて構成される場合、一般的に、小さいメモリマクロは、格納する値D624または減算値D621のビット数に対して相対的に大きくなるため、回路規模が膨大になる。
【０２１１】
なお、上述した図１０と図１７は、復号装置の実装の例として、各ノードの演算を1つや全てでもない、ある数のノードの演算を同時に行う(partly parallel decoding)復号装置４００と６００であるが、その他各ノードの演算を１つずつ順次行うことによって、LDPC符号の復号を行う(full serial decoding)復号装置や、全ノードの演算を同時に行うことによって復号を行う(full parallel decoding)復号装置(非特許文献２)も提案されている。
【０２１２】
また、サムプロダクトアルゴリズムを近似して実装する方法なども提案されているが、この方法では、性能の劣化を招いてしまう。
【０２１３】
【非特許文献１】Bahl,Cocke,Jelinek and Raviv,”Optimal decoding of linear codes for minimizing symbol error rate”,IEEE Trans Inf.Theory,vol.IT-20,pp.284-287,Mar.1974
【非特許文献２】C. Howland and A. Blanksby, ”Parallel Decoding Architectures for Low Density Parity Check Codes”, Symposium on Circuits and Systems, 2001
【発明の開示】
【発明が解決しようとする課題】
【０２１４】
上述した図１０の復号装置４００では、各計算器４１２kは、２つのFIFOメモリ４３８と４４４から構成されるので、計算器４１２kの数に比例して、FIFOメモリ４３８と４４４の数が多くなる。その結果、計算部４１２のメモリの回路規模が大きくなり、復号装置４００全体の回路規模が大きくなる。
【０２１５】
同様に、図１７の復号装置６００では、各計算器６１１kが、２つのLIFOメモリ６３５と６３８から構成されるので、計算器６１１kの数に比例して、計算部６１１のメモリの回路規模が大きくなり、復号装置６００全体の回路規模が大きくなる。
【０２１６】
本発明は、このような状況に鑑みてなされたものであり、LDPC符号の復号性能を損なうことなく、復号装置の回路規模の削減を行うことができるようにするものである。
【課題を解決するための手段】
【０２１７】
本発明の一側面の復号装置は、LDPC(Low Density Parity Check)符号の復号装置であって、前記LDPC符号の復号のためのP（１より大きい整数）個の演算を同時に行う演算手段を備え、前記演算手段は、複数のデータを積算し、前記複数のデータの積算値から、前記複数のデータそれぞれを減算する演算を含むチェックノードの演算を行う前記P個の演算器と、前記積算値から減算する前記複数のデータを記憶する、ビット幅が、前記データの量子化幅のP倍で、ワード数が前記LDPC符号の検査行列の行の重みに等しい１個の遅延用の記憶手段とを備え、前記演算器は、前記記憶手段を用いて、前記複数のデータの積算値から、前記記憶手段で遅延された前記複数のデータそれぞれを減算する復号装置である。
【０２２６】
本発明の一側面の復号方法は、LDPC(Low Density Parity Check)符号の復号のためのP（１より大きい整数）個の演算を同時に行う演算手段を備え、前記演算手段は、複数のデータを積算し、前記複数のデータの積算値から、前記複数のデータそれぞれを減算する演算を含むチェックノードの演算を行う前記P個の演算器と、前記積算値から減算する前記複数のデータを記憶する、ビット幅が、前記データの量子化幅のP倍で、ワード数が前記LDPC符号の検査行列の行の重みに等しい１個の遅延用の記憶手段とを備えるLDPC符号の復号装置の前記演算器が、前記記憶手段を用いて、前記複数のデータの積算値から、前記記憶手段で遅延された前記複数のデータそれぞれを減算するステップを含む復号方法である。
【０２２７】
本発明の一側面においては、ビット幅が、前記データの量子化幅のP倍で、ワード数が前記LDPC符号の検査行列の行の重みに等しい１個の遅延用の記憶手段において、前記積算値から減算する前記複数のデータが記憶される。そして、前記演算器において、前記記憶手段を用いて、前記複数のデータの積算値から、前記記憶手段で遅延された前記複数のデータそれぞれが減算される。
【発明の効果】
【０２２８】
本発明の一側面によれば、LDPC符号の復号性能を損なうことなく、復号装置の回路規模の削減を行うことができる。
【発明を実施するための最良の形態】
【０２３４】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。
【０２３５】
図１９は、本発明の一実施の形態の、LDPC符号を復号する復号装置８００の第１の構成例を示している。なお、図中、図１０の復号装置４００と対応する部分については、同一の符号を付してあり、以下では、その説明は、適宜省略する。
【０２３６】
図１９の復号装置８００は、復号途中結果格納用メモリ４１０、サイクリックシフト回路４１１、復号途中結果格納用メモリ４１３、サイクリックシフト回路４１４、６つの計算器４１５1乃至計算器４１５6からなる計算部４１５、受信用メモリ４１６、および制御部４１７が設けられている点で、図１０の復号装置４００と共通するが、計算部４１２に代えて計算部８１１が設けられている点で、図１０の復号装置４００と相違している。
【０２３７】
ここで、図１９の復号装置８００では、例えば、前述の図９に示した検査行列Hで表されるLDPC符号（符号化率2/3、符号長108）の復号が行われることとする。後述する図２７の復号装置８００においても同様である。
【０２３８】
図１９の復号装置８００では、計算部８１１が第１の演算を６個ずつ行い、計算部４１５が第２の演算を６個ずつ行い、これらの第１の演算と第２の演算とが交互に行われることによって、LDPC符号が復号される。
【０２３９】
即ち、受信用メモリ４１６には、LDPC符号の受信値U0が受信され、受信データD416（u0i）が供給されて、記憶される。そして、受信用メモリ４１６は、既に記憶している受信データD416から、第２の演算に必要となる順に６つの受信データD416を読み出し、受信データD4171乃至D4176（D417）として計算部４１５に供給する。
【０２４０】
そして、計算部４１５は、LDPC符号の復号のための第２の演算を行う。
【０２４１】
即ち、復号途中結果格納用メモリ４１３には、後述する計算部８１１による第１の演算の結果としての復号途中結果D4121乃至D4126（uj）が格納されており、復号途中結果格納用メモリ４１３は、既に格納してある復号途中結果D412のうち、６つの復号途中結果D4121乃至D4126を、復号途中結果D4131乃至D4136として、サイクリックシフト回路４１４と計算部８１１に供給する。
【０２４２】
サイクリックシフト回路４１４は、制御部４１７からの制御信号D421に基づき、復号途中結果D4131乃至D4136をサイクリックシフトし、その結果を復号途中結果D4141乃至D4146として計算部４１５に供給する。さらに、計算部４１５には、制御部４１７から制御信号D422が供給されるとともに、受信用メモリ４１６から６つの受信データD4171乃至D4176が供給される。
【０２４３】
計算器４１５は、計算器４１５1乃至４１５6から構成され、各計算器４１５kは前述の図１３に示したように構成されている。各計算器４１５kは、制御信号D422に基づき、サイクリックシフト回路４１４から供給される復号途中結果D414k（uj）と、受信用メモリ４１６から供給される受信データD417k（u0i）とを用い、式（５）にしたがって第２の演算を行う。そして、各計算器４１５kは、第２の演算の結果得られる復号途中結果D415k（v）を、復号途中結果格納用メモリ４１０に供給する。
【０２４４】
復号途中結果格納用メモリ４１０は、計算部４１５から供給される、６つの第２の演算の結果である復号途中結果D4151乃至D4156（D415）（v）を格納していく。そして、復号途中結果格納用メモリ４１０は、既に格納してある復号途中結果D415から、６つの復号途中結果D415を、復号途中結果D410として読み出し、サイクリックシフト回路４１１に供給する。サイクリックシフト回路４１１は、制御部４１７から供給される制御信号D418に基づき、６つの復号途中結果D410をサイクリックシフトし、その結果を復号途中結果D4111乃至D4116として計算部８１１に供給する。
【０２４５】
計算部８１１は、LDPC符号の復号のための第１の演算を行う。
【０２４６】
即ち、計算部８１１は、制御部４１７から供給される制御信号D419に基づき、サイクリックシフト回路４１１から供給される６つの復号途中結果D4111乃至D4116（v）と、復号途中結果格納用メモリ４１３から供給される、前回の計算部８１１による第１の演算の結果得られた復号途中結果D4131乃至D4136とを用いて、式（７）と式（８）にしたがって第１の演算を行い、その第１の演算によって求められた６つの復号途中結果D4121乃至D4126（uj）を、復号途中結果格納用メモリ４１３に供給する。
【０２４７】
復号途中結果格納用メモリ４１３は、計算部８１１から供給される復号途中結果D4121乃至D4126を格納していく。そして、復号途中結果格納用メモリ４１３に記憶された復号途中結果D412は、上述したように復号途中結果D4131乃至D4136として読み出され、サイクリックシフト回路４１４と計算部８１１に供給される。
【０２４８】
図２０は、図１９の計算部８１１の詳細構成例を示すブロック図である。
【０２４９】
図２０の計算部８１１は、６つの計算器８２１1乃至８２１6とFIFOメモリ８２２から構成される。
【０２５０】
図２０の計算部８１１は、６つの復号途中結果D411乃至D4116と６つの復号途中結果D4131乃至D4136とを用いて第１の演算を行う点で、前述の図１１の計算部４１２と共通するが、各計算器４１２1乃至４１２6ごとに設けられるFIFOメモリ４３８と４４４の代わりに、６つの計算器８２１1乃至８２１6に共通の１つのFIFOメモリ８２２が新たに設けられている点で、図１１の計算部４１２と異なっている。
【０２５１】
即ち、計算部８１１には、サイクリックシフト回路４１１から６つの６ビットの復号途中結果D4111乃至D4116が供給されるとともに、復号途中結果格納用メモリ４１３から６つの６ビットの復号途中結果D4131乃至D4136が供給され、それぞれ、計算器８２１1乃至８２１6に１つずつ供給される。また、計算部８１１には、制御部４１７から1ビットの制御信号D419が供給され、計算器８２１1乃至８２１6に供給される。
【０２５２】
各計算器８２１kは、積算前演算器８３１k、積算器８３２k、および積算後演算器８３３kから構成される。
【０２５３】
積算前演算器８３１kは、６ビットの復号途中結果D411kとD413kを用いて、式（８）の演算とφ(|vi|)の演算（以下、積算前演算という）を行う。そして、積算前演算器８３１kは、積算前演算の結果得られる６ビットの演算結果D831k（φ(|vi|)）をFIFOメモリ８２２に供給するとともに、積算部８３３kに供給する。
【０２５４】
積算器８３２kは、積算前演算器８３１kからの演算結果D831kを用いて、制御信号D419に基づいて、ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)の演算と、ｉ＝１からｉ＝ｄcまでのΠsign(vi)の演算（以下、積算演算という）を行う。積算器８３２kは、積算演算のｉ＝１からｉ＝ｄcまでのΣφ(|vi|)の演算の結果得られる９ビットの値D437k（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）と、ｉ＝１からｉ＝ｄcまでのΠsign(vi)の演算の結果得られる５ビットの値D438k（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）とを、積算後演算器８３３kに供給する。
【０２５５】
積算後演算器８３３kは、積算器８３２kからの値D437k（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）と値D438k（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）、並びにFIFOメモリ８２２からの６ビットの演算結果D832kを用いて、ｉ＝１からｉ＝ｄc−１までのΣφ(|vi|)に対する、式（７）におけるφ-1（Σφ(|vi|)）の演算と、ｉ＝１からｉ＝ｄc−１までのΠsign(vi)の演算（以下、積算後演算という）を行う。そして、積算後演算器８３３kは、積算後演算の結果得られる復号途中結果D412k（uj）を出力する。
【０２５６】
FIFOメモリ８２２は、例えば、RAMなどのメモリマクロから構成される。FIFOメモリ８２２のビット幅は、量子化ビット数と、積算前演算器８３１kから供給される演算結果D831kの数である６とを乗算した値であり、ワード数は、チェックノード次数である。
【０２５７】
FIFOメモリ８２２は、６つの積算前演算器８３１1乃至８３１6からそれぞれ供給される６ビットの６つの演算結果D8311乃至D8316、即ち計３６ビットの演算結果D8311乃至D8316を格納し、９クロック分遅延する。そして、FIFOメモリ８２２は、既に格納されている計３６ビットの演算結果D8311乃至D8316を、演算結果D8321乃至D8326として読み出し、６ビットの演算結果D832kを１つずつ積算後演算器８３３1乃至８３３6に供給する。
【０２５８】
以上のように、計算部４１２kでは、式（７）と式（８）にしたがう第１の演算が行われ、復号途中結果ujが求められる。
【０２５９】
図２０の計算部８１１では、計算器８２１1乃至８２１6に共通のFIFOメモリ８２２が設けられるので、計算器４１２1乃至４１２6のそれぞれにFIFOメモリ４３８と４４４が設けられる図１２の計算部４１２に比べて、計算部８１１の回路規模を小さくすることができる。
【０２６０】
即ち、一般的に、RAMなどのメモリマクロは、同一のビット数とワード数で構成される場合、それを構成するメモリマクロの数が少ないほど、回路規模は小さくなる。従って、復号装置８００の計算部８１１において、６つのFIFOメモリ４３８と４４４に代えて、共通の１つのFIFOメモリ８２２を設けることにより、復号装置８００の復号性能を損なうことなく、回路規模を削減することができる。
【０２６１】
なお、６つのFIFOメモリ４３８または４４４のビット数またはワード数が多く、６つのFIFOメモリ４３８と４４４を、共通の１つのFIFOメモリ８２２で構成させることができない場合、１つではなく、計算器８２１kの数である６よりも少ない複数のFIFOメモリ８２２で構成させるようにしてもよい。
【０２６２】
ここで、図２１を参照して、図２０の計算器８２１kと、前述の図１２の計算器４１２kとの関係を説明する。
【０２６３】
図２１は、前述の図１２と同一の図である。
【０２６４】
図２１に示すように、復号途中結果D411kが入力されてから、FIFOメモリ４３８と４４４に演算結果D434または符号ビットD432が供給されるまでの積算前演算を行うブロックＡが、積算前演算器８３１kに対応している。
【０２６５】
また、FIFOメモリ４３８による遅延と並行してｉ＝１からｉ＝ｄcまでのΣφ(|vi|)の演算を行うブロックＢ１と、FIFOメモリ４４４による遅延と並行してｉ＝１からｉ＝ｄcまでのΠsign(vi)の演算を行うブロックＢ２が、積算器８３２kに対応している。即ち、積算演算を行うブロックＢ１とＢ２が、積算器８３２kに対応している。
【０２６６】
さらに、FIFOメモリ４３８と４４４により遅延された値D438またはD445が出力されてから積算後演算を行うブロックＣが、積算後演算器８３３kに対応している。
【０２６７】
即ち、積算前演算器８３１kは、図２２に示すように構成される。なお、図１２と同一のものには、同一の符号を付してあり、説明は適宜省略する。このことは、後述する図２３と図２４においても同様である。
【０２６８】
図２２の積算前演算器８３１kは、減算器４３１とLUT４３２から構成される。
【０２６９】
減算器４３１は、式（８）にしたがって、９ビットの復号途中結果D411k（v）から６ビットの復号途中結果D413k（uj）を減算し、その６ビットの減算値D431（vi）を出力する。
【０２７０】
減算器４３１により出力された６ビットの減算値D431のうち、下位５ビットの絶対値D433（|vi|）がLUT４３２に供給される。
【０２７１】
LUT４３２は、絶対値D433(|vi|)に対して、式（７）におけるφ(|vi|)の演算を行った５ビットの演算結果D434（φ(|vi|)）を読み出し、出力する。
【０２７２】
これにより、LUT４３２により出力された５ビットの演算結果D434を下位５ビットとするとともに、減算器４３１から出力された減算値D431のうちの、最上位ビットの正負を示す符号ビットD432（sign（vi））を最上位ビットとする合計６ビットが、積算前演算の演算結果D831k（φ(|vi|)×sign（vi））として出力される。
【０２７３】
また、積算器８３２kは、図２３に示すように構成される。
【０２７４】
図２３の積算器８３２kは、レジスタ４３４、セレクタ４３５、レジスタ４３６、レジスタ４４１、セレクタ４４３、レジスタ４４３、加算器８５１、およびEXOR回路８５２から構成される。
【０２７５】
積算器８３２kには、積算前演算器８３１kから６ビットの演算結果D831k（φ(|vi|)×sign（vi））が供給される。そして、６ビットの演算結果D831kのうち下位５ビットが、演算結果D851（φ(|vi|)）として、加算器８５１に供給され、最上位ビットの符号ビットが、符号ビットD852（sign（vi））としてEXOR回路８５２に供給される。即ち、演算結果D851は、演算結果D434と同一であり、符号ビットD852は符号ビットD432と同一である。
【０２７６】
また、積算器８３２kには、制御部４１７から制御信号D419が供給され、セレクタ４３５と４４２に供給される。
【０２７７】
加算器８５１は、図１２の加算器４３３と同様に、５ビットの演算結果D851（φ(|vi|)）とレジスタ４３４に格納されている９ビットの値D435とを加算することにより、演算結果D851を積算し、その結果得られる９ビットの積算値をレジスタ４３４に再格納する。
【０２７８】
制御信号D419が「１」である場合、セレクタ４３５は、レジスタ４３４に格納されている値、即ち、検査行列Hの1行に亘る全ての１に対応する復号途中結果D411k（v）から求められたφ(|vi|)が積算された９ビットの値D435（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）を選択し、値D436として、レジスタ４３６に出力して格納させる。
【０２７９】
制御信号D419が「０」の場合、セレクタ４３５は、レジスタ４３６から供給された値D437を選択し、レジスタ４３６に出力して再格納させる。レジスタ４３６は、格納している値D436を、９ビットの値D437として、セレクタ４３５と積算後演算器８３３kに供給する。
【０２８０】
以上の処理と並行して、EXOR回路８５２は、図１０のEXOR回路４４０と同様に、レジスタ４４１に格納されている１ビットの値D442と符号ビットD852との排他的論理和を演算することにより、符号ビットどうしの乗算を行い、１ビットの乗算結果D441をレジスタ４４１に再格納する。
【０２８１】
制御信号D419が「１」の場合、セレクタ４４２は、レジスタ４４１に格納されている値、即ち、検査行列Hの1行に亘る全ての１に対応する復号途中結果D411kから求められた符号ビットD432が乗算された値D442（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）を選択し、１ビットの値D443としてレジスタ４４３に出力して格納させる。
【０２８２】
制御信号D419が「０」の場合、セレクタ４４２は、レジスタ４４３から供給された値D444を選択し、レジスタ４４３に出力して再格納させる。レジスタ４４３は、格納している値D443を、１ビットの値D444としてセレクタ４４２と積算後演算器８３３kに供給する。
【０２８３】
さらに、積算後演算器８３３kは、図２４に示すようになる。
【０２８４】
図２４の積算後演算器８３３kは、LUT４３９、減算器８７１、およびEXOR回路８７２から構成される。
【０２８５】
減算器８７１は、図１２の減算器４３７と同様に構成される。減算器８７１には、積算器８３２kから供給される値D437と、FIFOメモリ８２２から供給される演算結果D832k（φ(|vi|)×sign（vi））のうちの下位５ビットである値D871（φ(|vi|)）とが供給される。減算器８７１は、値D437（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）から演算結果D871を減算し、その減算結果を、５ビットの減算値D439（ｉ＝１からｉ＝ｄc-1までのΣφ(|vi|)）としてLUT４３９に供給する。
【０２８６】
LUT４３９は、減算値D439（ｉ＝１からｉ＝ｄc−１までのΣφ(|vi|)）に対して、式（７）におけるφ-1（Σφ(|vi|)）の演算を行った５ビットの演算結果D440（φ-1(Σφ(|vi|)))を出力する。
【０２８７】
EXOR回路８７２は、図１０のEXOR回路４４５と同様に構成される。EXOR回路８７２には、FIFOメモリ８２２から演算結果D832kのうちの最上位である符号ビットD872（sign（vi））が供給されるとともに、積算器８３２1から値D444が供給される。EXOR回路８７２は、符号ビットD872と値D444との排他的論理和を演算することにより、値D444を、符号ビットD872で除算し、１ビットの除算結果を除算値D446（ｉ＝１からｉ＝ｄc−１までのΠsign(vi)）として出力する。
【０２８８】
以上により、LUT４３９から出力された５ビットの演算結果D440を下位５ビットとするとともに、EXOR回路４４５から出力された１ビットの除算値D446を最上位ビットとする合計６ビットが復号途中結果D412k（uj）として出力される。
【０２８９】
図２５は、図１９の復号装置８００の復号処理を説明するフローチャートである。この処理は、例えば、受信用メモリ４１６に復号すべき受信データD416が格納されたとき、開始される。
【０２９０】
ステップＳ５０において、サイクリックシフト回路４１４は、復号途中結果格納用メモリ４１３から供給された後述するステップＳ５６で格納される６つの復号途中結果D413（uj）を、サイクリックシフトし、計算部４１５に供給する。
【０２９１】
具体的には、サイクリックシフト回路４１４には、復号途中結果格納用メモリ４１３から６つの復号途中結果D4131乃至D4136が供給されるとともに、制御部４１７から、その復号途中結果D413に対応する検査行列の１が検査行列において元となる単位行列などを幾つサイクリックシフトしたものであるかの情報（Matrixデータ）を表す制御信号D421が供給される。サイクリックシフト回路４１４は、制御信号D421を元に、６つの復号途中結果D4131乃至D4136をサイクリックシフトし（並べ替え）、その結果を復号途中結果D4141乃至D4146として、計算部４１５に供給する。
【０２９２】
なお、受信用メモリ４１６から供給された受信データD417に対して、まだ第１の演算が行われておらず、復号途中結果格納用メモリ４１３に復号途中結果D412が格納されていない場合、計算部４１５は、復号途中結果ujを初期値に設定する。
【０２９３】
ステップＳ５０の処理後は、ステップＳ５１に進み、計算部４１５は、第２の演算を行い、その演算の結果である復号途中結果D4151乃至D4156を復号途中結果格納用メモリ４１０に供給する。
【０２９４】
具体的には、計算部４１５には、ステップＳ５０でサイクリックシフト回路４１４から６つの復号途中結果D4141乃至D4146が供給されるとともに、受信データ用メモリ４１６から６つの受信データD4171乃至D4176が供給され、復号途中結果D4151乃至D4156と受信データD4171乃至D4176が、計算部４１５の計算器４１５1乃至４１５6それぞれに１つずつ供給される。さらに、計算部４１５には、制御部４１７から制御信号D422が供給され、その制御信号D422が計算器４１５1乃至４１５6に供給される。
【０２９５】
各計算器４１５kは、復号途中結果D414kと受信データD417kを用いて、制御信号D422に基づいて、式（５）にしたがう第２の演算を行い、その演算の結果得られる検査行列の列に対応する復号途中結果D415k(v)を復号途中結果格納用メモリ４１０に供給する。
【０２９６】
ステップＳ５１の処理後は、ステップＳ５２に進み、復号途中結果格納用メモリ４１０は、ステップＳ５１で計算部４１５から供給された６つの復号途中結果D4151乃至D4156を、同一アドレスに格納し、ステップＳ５３に進む。
【０２９７】
ステップＳ５３において、制御部４１７は、計算部４１５により、検査行列の列に対応する全ての復号途中結果D415が演算されたかどうかを判定し、全ての復号途中結果D415が演算されていないと判定した場合、ステップＳ５０に戻り、上述した処理を繰り返す。
【０２９８】
一方、ステップＳ５３において、制御部４１７は、計算部４１５により、検査行列の列に対応する全ての復号途中結果D415が演算されたと判定した場合、ステップＳ５４に進み、サイクリックシフト回路４１１は、復号途中結果格納用メモリ４１０から供給される復号途中結果D410(v)をサイクリックシフトする。
【０２９９】
具体的には、サイクリックシフト回路４１１には、復号途中結果格納用メモリ４１０から６つの復号途中結果D410が供給されるとともに、制御部４１７から、その復号途中結果D410に対応する検査行列の１が検査行列において元となる単位行列などを幾つサイクリックシフトしたものであるかの情報（Matrixデータ）を表す制御信号D418が供給される。サイクリックシフト回路４１１は、制御信号D418を元に、６つの復号途中結果D410をサイクリックシフトし（並べ替え）、その結果を復号途中結果D4111乃至D4116として、計算部８１１に供給する。
【０３００】
ステップＳ５４の処理後は、ステップＳ５５に進み、計算部８１１は、６個の第１の演算を同時に行い、その演算結果である復号途中結果D4121乃至D4126を復号途中結果格納用メモリ４１３に供給する。なお、この第１の演算の処理の詳細については、図２６を参照して後述する。
【０３０１】
ステップＳ５５の処理後は、ステップＳ５６に進み、復号途中結果格納用メモリ４１３は、ステップＳ５５で計算部４１２から供給された６つの復号途中結果D4121乃至D4126を、同一のアドレスに格納し、ステップＳ５７に進む。
【０３０２】
ステップＳ５７において、制御部４１７は、計算部４１２により、検査行列の全ての1に対応する復号途中結果D412が演算されたかどうかを判定し、全ての復号途中結果D412が演算されていないと判定した場合、ステップＳ５４に戻り、上述した処理を繰り返す。
【０３０３】
一方、ステップＳ５７において、制御部４１７は、計算部４１２により、全ての１に対応する復号途中結果D412が演算されたと判定した場合、処理を終了する。
【０３０４】
なお、復号装置４００は、復号回数だけ図２５の復号処理を繰り返し行ない、最後の第２の演算の結果得られる復号途中結果D415が、最終的な復号結果として出力される。
【０３０５】
図２６は、図２５のステップＳ５５の第１の演算処理を説明するフローチャートである。なお、この第１の演算処理は、各計算器８１２kごとに行われる。
【０３０６】
ステップＳ６１において、図２５のステップＳ５４でサイクリックシフト回路４１１から供給される復号途中結果D411k(v)と、図２５のステップＳ５６で既に格納された前回の計算部８１１による第１の演算の結果得られた復号途中結果D413k（uj)とを用いて、積算前演算を行い、その結果得られる演算結果D831kを共通のFIFOメモリ８２２と積算器８３２に供給する。
【０３０７】
ステップＳ６１の処理後は、ステップＳ６２に進み、FIFOメモリ８２２は、ステップＳ６１で供給される演算結果D831kを格納し、９クロック分の遅延を行うとともに、積算器８３２kは、制御部４１７からの制御信号D419と演算結果D831kを用いて、積算演算を行い、その結果得られる値D437kとD444kを積算後演算器８３３kに供給する。
【０３０８】
ステップＳ６３の処理後は、ステップＳ６４に進み、積算後演算器８３３kは、ステップＳ６２で供給される値D437とD444、並びにFIFOメモリ８２２から供給される演算結果D832k（D831k）を用いて、積算後演算を行い、その演算の結果得られる復号途中結果D412k（uj）を復号途中結果格納用メモリ４１３に供給して、処理を終了する。
【０３０９】
図２７は、本発明の一実施の形態の、LDPC符号を復号する復号装置８００の第２の構成例を示している。なお、図中、図１７の復号装置６００と対応する部分については、同一の符号を付してあり、以下では、その説明は、適宜省略する。
【０３１０】
図２７の復号装置８００は、復号途中結果格納用メモリ４１０、サイクリックシフト回路４１１、復号途中結果格納用メモリ４１３、サイクリックシフト回路４１４、６つの計算器４１５1乃至計算器４１５6からなる計算部４１５、受信用メモリ４１６、および制御部６１２が設けられている点で、図１７の復号装置６００と共通するが、計算部６１１に代えて計算部1001が新たに設けられている点で、図１７の復号装置６００と相違している。
【０３１１】
図２７の復号装置８００では、計算部1001がBCJRアルゴリズムに基づいて、第３の演算を６個ずつ行い、計算部４１５が第２の演算を６個ずつ行い、これらの第３の演算と第２の演算とが交互に行われることによって、LDPC符号が復号される。
【０３１２】
即ち、計算部1001には、LDPC符号の復号のための第３の演算を行う。サイクリックシフト回路４１１から、計算部４１５による第２の演算の結果得られた６つの復号途中結果D4111乃至D4116（v）が供給されるとともに、復号途中結果格納用メモリ４１３から、前回の計算部1001による第３の演算の結果得られた６つの復号途中結果D4131乃至D4136（uj）が供給される。また、計算部1001には、制御部６１２から制御信号D611とD612が供給される。
【０３１３】
計算部８１１は、制御信号D611に基づき、６つの復号途中結果D4111乃至D4116（v）と復号途中結果D4131乃至D4136とを用いて、式（２５）乃至（２７）にしたがうチェックノード演算と、式（８）にしたがう演算とからなる第３の演算を行い、その第３の演算によって求められた６つの復号途中結果D4121乃至D4126（uj）を、復号途中結果格納用メモリ４１３に供給する。
【０３１４】
図２８は、図２７の計算部1001の詳細構成例を示すブロック図である。
【０３１５】
図２８の計算部1001は、６つの計算器1110k、並びにLIFOメモリ1111と1112から構成される。
【０３１６】
図２８の計算部1001は、６つの復号途中結果D411乃至D4116を用いて、６つのD4121乃至D4126を同時に求める点で、前述の図１７の計算部６１１と共通するが、各計算器６１１1乃至６１１6ごとに設けられるLIFOメモリ６３５と６３８の代わりに、６つの計算器11101乃至11106に共通のLIFOメモリ1111と1112が新たに設けられている点で、図１７の計算部６１１と異なっている。
【０３１７】
即ち、計算部1001には、サイクリックシフト回路４１１から６つの６ビットの復号途中結果D4111乃至D4116が供給されるとともに、復号途中結果格納用メモリ４１３から６つの６ビットの復号途中結果D4131乃至D4136が供給され、それぞれ、計算器11101乃至11106に１つずつ供給される。また、計算部８１１には、制御部６１２から制御信号D611とD612が供給され、計算器11101乃至11106に供給される。
【０３１８】
各計算器1110kは、減算器1121k、α演算器1122k、β演算器1123k、およびλE演算器1124kから構成される。
【０３１９】
減算器1121kは、６ビットの復号途中結果D411k（v）とD413k（uj）を用いて、式（８）の演算を行う。そして、減算器1121kは、式（８）の演算の結果得られる６つの減算値D6211乃至D6216（vi）（Δγt）を、α演算器1122kに供給するとともに、減算値D6211乃至D6216をLIFOメモリ1112に供給する。
【０３２０】
α演算器1122kは、制御信号D611に基づいて、減算器1121kからの減算値D621kを用いて、α演算を行い、その結果得られる値D624k(Δαt)をLIFOメモリ1111に供給する。
【０３２１】
LIFOメモリ1111は、例えば、RAMなどのメモリマクロから構成される。LIFOメモリ1111のビット幅は、量子化ビット数と、α演算器1122kから供給される値D624kの数である６とを乗算した値であり、ワード数は、チェックノード次数である。LIFOメモリ1111は、α演算器11221乃至11226から供給される値D6241乃至D6246を記憶する。
【０３２２】
LIFOメモリ1111は、既に記憶している値D6241乃至D6246を、入力された順番とは逆の順番に、値D6251乃至D6256として読み出し、１つずつ、λE演算器11241乃至11246に供給する。
【０３２３】
以上の処理と並行して、LIFOメモリ1112は、減算器11211乃至11216から供給される６つの減算値D6211乃至D6216(Δγt)を格納する。なお、LIFOメモリ1112は、LIFOメモリ1111と同様に、例えば、RAMなどのメモリマクロから構成され、LIFOメモリ1111のビット幅は、量子化ビット数と、減算器1121kから供給される減算値D621kのビット数である６とを乗算した値であり、ワード数は、チェックノード次数である。
【０３２４】
LIFOメモリ1112は、既に記憶している６つの減算値D6211乃至D6216を、入力された順番とは逆の順番に、値D6171乃至D6176として読み出し、１つずつ、β演算器11231乃至11236に供給する。
【０３２５】
β演算器1123kは、制御信号D611に基づいて、値D617k（Δγt）を用いて、β演を行い、その結果得られる値D630k(Δβt)をλE演算器1124kに供給する。
【０３２６】
λE演算器1124kは、制御信号D611に基づき、LIFOメモリ１１３からの値D625k（Δγt）とβ演算器1123kからの値D630k（Δβt-1）とを用いて、λE演算を行い、その演算の結果得られる復号途中結果D412k（外部情報ΔλEt）（uj）を出力する。
【０３２７】
以上のように、計算部1101では、第３の演算が行われ、復号途中結果ujが求められる。
【０３２８】
図２８の計算部1101では、計算器11101乃至11106に共通のLIFOメモリ1111と1112が設けられるので、計算器６１１1乃至６１１6のそれぞれにLIFOメモリ６３５と６３８が設けられる図１７の計算部６１１に比べて、計算部1001の回路規模を小さくすることができる。
【０３２９】
即ち、一般的に、RAMなどのメモリマクロは、同一のビット数とワード数で構成される場合、それを構成するメモリマクロの数が少ないほど、回路規模は小さくなる。従って、復号装置８００の計算部1101において、６つのLIFOメモリ６３５と６３８に代えて、共通のLIFOメモリ111１と1112を設けることにより、復号装置８００の復号性能を損なうことなく、回路規模を削減することができる。
【０３３０】
なお、６つのLIFOメモリ６３５または６３８のビット数またはワード数が多く、６つのLIFOメモリ６３５と６３８を、共通のLIFOメモリ1111と1112で構成させることができない場合、１つずつではなく、計算器1110kの数である６よりも少ない複数ずつのLIFOメモリ1111と1112で構成させるようにしてもよい。
【０３３１】
ここで、図２９を参照して、図２８の計算器1110kと、前述の図１８の計算器６１１kとの関係を説明する。
【０３３２】
図２９は、前述の図１８と同一の図である。
【０３３３】
図２９に示すように、復号途中結果D411kが入力されてから、LIFOメモリ６３８に減算値D621が供給されるまでの式（８）の演算を行うブロックＰが、計算器1110kの減算器1121kに対応している。
【０３３４】
また、式（８）の演算が行われてから、LIFOメモリ６３５に値D624が供給されるまでのα演算を行うブロックＱが、α演算器1122kに対応している。
【０３３５】
さらに、LIFOメモリ６３８から値D627が出力されてから、Ｑ演算器６３６に値D630が供給されるまでのβ演算を行うブロックＲが、β演算器1123kに対応している。
【０３３６】
また、Ｑ演算器６３６に値D625と値D630が供給されてから、復号途中結果D412kを出力するまでのλE演算を行うブロックＳが、λE演算器1124kに対応している。
【０３３７】
即ち、減算器1121kは、図３０に示すように構成される。なお、図１８と同一のものには、同一の符号を付してあり、説明は適宜省略する。このことは、後述する図３１乃至図３３においても同様である。
【０３３８】
図３０の減算器1121kは、減算器６３１から構成される。
【０３３９】
減算器1121kには、サイクリックシフト回路４１１から供給される６つの復号途中結果D4111乃至D4116(v)のうちの、１つの復号途中結果D411kが供給されるとともに、復号途中結果格納用メモリ４１３から供給される、前回の計算部1001による演算の結果である６つの復号途中結果D4131乃至D4136（uj）のうちの、１つの復号途中結果D413kが供給される。
【０３４０】
減算器６３１は、式（８）にしたがって、復号途中結果D411k（v）から復号途中結果D413k（uj）を減算し、その結果得られる減算値D621k（vi）（Δγt）をLIFOメモリ1112とα演算器1122kに供給する。
【０３４１】
また、α演算器1122kは、図３１に示すように構成される。図３１のα演算器1122kは、Ｑ演算回路６３２、セレクタ６３３、およびレジスタ６３４から構成される。
【０３４２】
Ｑ演算回路６３２は、減算器1121kからの減算値D621k（Δγt-1）と、レジスタ６３４から供給される値D624k（Δαt-1）とを用いて、α演算（Ｑ（Δαt-1,Δγt-1））を行い、その結果得られる演算結果D622(Δαt)をセレクタ６３３に供給する。
【０３４３】
制御信号D611が「１」の場合、セレクタ６３３は、減算器６３１からの減算値D621（Δγ1）を選択し、値D623（Δα1）として、レジスタ６３３に出力して格納させる。一方、制御信号D611が「０」の場合、セレクタ６３３は、Ｑ演算回路６３２から供給された演算結果D622を選択し、値D623としてレジスタ６３４に出力して格納させる。
【０３４４】
レジスタ６３４は、セレクタ６３３からの値D623を、値D624kとして、Ｑ演算回路６３２とLIFOメモリ1111に供給する。
【０３４５】
さらに、β演算器1123kは、図３２に示すように構成される。図３２のβ演算器1123kは、Ｑ演算回路６３９、セレクタ６４０、およびレジスタ６４１から構成される。
【０３４６】
β演算器1123kには、LIFOメモリ1112から値D627kが供給される。
【０３４７】
Ｑ演算回路６３９は、LIFOメモリ1112からの値D627（Δγt）と、レジスタ６４１から供給される値D630k（Δβt）とを用いて、β演算（Ｑ（Δβt+1,Δγt））を行い、その結果得られる演算結果D628(Δβt)をセレクタ６４０に供給する。
【０３４８】
制御信号D611が「１」の場合、セレクタ６４０は、LIFOメモリ６３８からの値D627k（Δγτ-1）を選択し、値D629（Δβτ-1）として、レジスタ６４１に出力して格納させる。一方、制御信号D611が「０」の場合、セレクタ６４０は、Ｑ演算回路６３９から供給された演算結果D628(Δβt)を選択し、値D629(Δβt)としてレジスタ６４１に出力して格納させる。
【０３４９】
レジスタ６４１は、セレクタ６４０からの値D629を、値D630k(Δβt+1)として、Ｑ演算回路６３９とλE演算器1124kに供給する。
【０３５０】
また、λE演算器1124kは、図３３に示すように構成される。λE演算器1124kは、Ｑ演算回路６３６、セレクタ６３７、およびレジスタ６４２から構成される。
【０３５１】
λE演算器1124kには、LIFOメモリ1111から値D625k（Δαt）が供給されるとともに、β演算器1123kから値D630k（Δβt+1）が供給される。
【０３５２】
Ｑ演算回路６３６は、値D625kとD630kを用いて、λE演算（Ｑ（Δαt,Δβt+1））を行い、その演算の結果得られる演算結果D626（外部情報ΔλEt）をセレクタ６３７に供給する。
【０３５３】
制御信号D611が「１」の場合、セレクタ６３７は、β演算器1123kからの値D625k（Δα1）を選択し、値D631（外部情報ΔλEt）として、レジスタ６４２に出力して格納させる。また、制御信号D611が「０」の場合、セレクタ６３３は、Ｑ演算回路６３２から供給された演算結果D626を選択し、値D631としてレジスタ６３４に出力して格納させる。さらに、制御信号D611が「２」の場合、セレクタ６３７は、LIFOメモリ６３５からの値D630（Δβτ―1）を選択し、値D631（外部情報ΔλEt）として、レジスタ６４２に出力して格納させる。
【０３５４】
レジスタ６４２は、セレクタ６３７からの値D631を記憶する。レジスタ６４２は、既に記憶している値D631（外部情報ΔλEt）を、復号途中結果D412k（uj）として出力する。
【０３５５】
以上のように、計算器1110kでは、第３の演算が行われ、復号途中結果ujが求められる。
【０３５６】
次に、図３４を参照して、図２８の計算部1001による第３の演算処理を説明する。なお、この第３の演算処理は、各計算器1110kごとに行われる。
【０３５７】
ステップＳ８１において、減算器1121kは、サイクリックシフト回路４１１から供給される復号途中結果D411k(v)と、既に格納された前回の計算部1110による第３の演算の結果得られた復号途中結果D413k（uj)とを用いて、式（８）にしたがう演算（減算）を行い、その結果得られる減算値D621kを、α演算器1122kと共通のLIFOメモリ1112に供給する。
【０３５８】
ステップＳ８１の処理後は、ステップＳ８２に進み、α演算器1122kは、制御部６１２からの制御信号D611と、ステップＳ８１で供給される減算値D621kとを用いて、α演算を行い、その結果得られる値D624kをLIFOメモリ1111に出力する。LIFOメモリ1111は、値D624kを記憶し、既に記憶している値D624kを、入力された順番と逆の順番で値D625kとして読み出して、λE演算器1124kに供給する。
【０３５９】
この処理と並行して、LIFOメモリ1112は、ステップＳ８１で供給される減算値D621kを記憶し、既に記憶している減算値D621kを値D627kとして、入力された順番と逆の順番でβ演算器1123kに供給する。β演算器1123は、制御部６１２からの制御信号D611と値D627kとを用いてβ演算を行い、その結果得られる値D630kをλE演算器1124kに供給する。
【０３６０】
ステップＳ８２の処理後は、ステップＳ８３に進み、λE演算器1124kは、制御信号６１２からの制御信号D612、並びにステップＳ８２で供給される値D624kとD630kを用いてλE演算を行い、その結果得られる復号途中結果D412kを復号途中結果格納用メモリ４１３に供給して、処理を終了する。
【０３６１】
上述の場合には、説明を簡単にするために、Pが６の場合、即ち、検査行列Hを構成する構成行列の行数および列数が６の場合を例に挙げたが、構成行列の行数および列数Pは必ずしも６である必要はなく、検査行列Hによって異なる値を取ることもあり得る。例えば、Pは３６０や３９２であってもよい。
【０３６２】
また、本実施の形態では、符号長108、符号化率2/3のLDPC符号を用いたが、LDPC符号の符号長や符号化率は、どのような値であってもよい。例えば、構成行列の行数および列数Pが６の場合、枝総数が６以下であれば、どのような符号長、符号化率のLDPC符号でも、制御信号を代えるだけで、復号装置８００を用いて復号可能である。
【０３６３】
さらに、構成行列の行数および列数Pが所定の値で、枝の総数がある値以下、という条件を満たす、あるLDPC符号の復号装置は、その条件を満たす、任意の符号長で、任意の符号化率のLDPC符号を復号することができる。
【０３６４】
また、計算部８１１を構成する計算器８２１kの数および計算器８２１kの回路の構成は、上述した例に限定されない。また、FIFOメモリ８２２は、RAMに限定されず、レジスタファイルやFIFOなど、その他のメモリマクロにより構成されるようにしてもよい。
【０３６５】
同様に、計算部1101を構成する計算器1110kの数および計算器1110kの回路の構成は、上述した例に限定されない。また、LIFOメモリ1111と1112は、RAMに限定されず、レジスタファイルやLIFOなど、その他のメモリマクロにより構成されるようにしてもよい。
【０３６６】
また、本発明は、第１の演算と第２の演算を交互に行う復号装置８００ではなく、チェックノード演算とバリアブルノード演算を交互に行う復号装置にも適用することができる。この場合、チェックノード演算を行うチェックノード演算器は、図２２の積算前演算器８３１kの減算器４３１を削除するか、または図２８の減算器1121kを削除することにより、構成され、バリアブルノード演算を行うバリアブルノード演算器は、図１３の計算器４１５kの最後に減算器４３１（６３１）を加えることにより構成される。
【０３６７】
以上のように、図１９と図２７の復号装置８００では、計算部８１１（１００１）が、計算器８２１k（計算器1110k）の数である６個より少ない数の遅延用のFIFOメモリ８２２（LIFOメモリ1111と1112）を備えるので、LDPC符号の復号性能を損なうことなく、復号装置８００の回路規模の削減を行うことができる。
【０３６８】
一般的に、LDPC符号は符号長が数千から数万と大きいため、Pの値も数百の大きさを持つものが使われる。その場合には、更に本発明に係る復号装置８００を用いる効果は大きくなる。
【０３６９】
また、本発明に係る復号装置８００は、サムプロダクトアルゴリズムを忠実に実装するものであるため、メッセージの量子化以外の復号損失が起きることはない。
【０３７０】
なお、上述したLDPC符号を復号する復号装置は、例えば、（ディジタル）衛星放送を受信するチューナなどに適用することができる。
【図面の簡単な説明】
【０３７１】
【図１】LDPC符号の検査行列Hを説明する図である。
【図２】パリティ部が下三角行列になっている検査行列Hを示す図である。
【図３】LDPC符号の復号手順を説明するフローチャートである。
【図４】メッセージの流れを説明する図である。
【図５】LDPC符号の検査行列Hの例を示す図である。
【図６】検査行列Hのタナーグラフを示す図である。
【図７】バリアブルノードを示す図である。
【図８】チェックノードを示す図である。
【図９】LDPC符号の検査行列Hの例を示す図である。
【図１０】ノード演算を６個同時に行う復号装置の構成例を示すブロック図である。
【図１１】図１０の計算部の構成例を示すブロック図である。
【図１２】図１１の計算器の構成例を示すブロック図である。
【図１３】図１０の計算器の構成例を示すブロック図である。
【図１４】図１０の復号途中結果格納用メモリの構成例を示すブロック図である。
【図１５】トレリスを説明する図である。
【図１６】パリティ検査符号のトレリスを説明する図である。
【図１７】BCJRアルゴリズムを用いてチェックノード演算を行う復号装置の構成例を示すブロック図である。
【図１８】図１７の計算器の構成例を示すブロック図である。
【図１９】本発明の一実施の形態の、LDPC符号を復号する復号装置の第１の構成例を示すブロック図である。
【図２０】図１９の計算部の詳細構成例を示すブロック図である。
【図２１】図２０の計算器と図１２の計算器との関係を説明する図である。
【図２２】積算前演算器の構成例を示すブロック図である。
【図２３】積算器の構成例を示すブロック図である。
【図２４】積算後演算器の構成例を示すブロック図である。
【図２５】図１９の復号装置の復号処理を説明するフローチャートである。
【図２６】図２５のステップＳ５５の第１の演算処理を説明するフローチャートである。
【図２７】本発明の一実施の形態の、LDPC符号を復号する復号装置の第２の構成例を示すブロック図である。
【図２８】図２７の計算部の詳細構成例を示すブロック図である。
【図２９】図２８の計算器と図１８の計算器との関係を説明する図である。
【図３０】減算器の構成例を示すブロック図である。
【図３１】α演算器の構成例を示すブロック図である。
【図３２】β演算器の構成例を示すブロック図である。
【図３３】λE演算器の構成例を示すブロック図である。
【図３４】図２８の計算部による第３の演算処理を説明するフローチャートである。
【符号の説明】
【０３７２】
４１０  復号途中結果格納用メモリ,  ４１１  サイクリックシフト回路,  ４１３  復号途中結果格納用メモリ,  ４１４  サイクリックシフト回路，  ４１５  計算部，  ４１６  受信用メモリ，  ４１７  制御部,  ６１２  制御部,  ８００  復号装置,  ８１１  計算部,  ８２１  計算器,  ８２２  FIFOメモリ,  ８３１  積算前演算器,  ８３２  積算器,  ８３３  積算後演算器,  １００１  計算部，  １１１０  計算器,  １１１１,１１１２  LIFOメモリ,  １１２１  減算器,１１２２  α演算器,  １１２３  β演算器,  １１２４  λE演算器
【図１】
0004730592.tif 000032
【図２】
0004730592.tif 000033
【図３】
0004730592.tif 000034
【図４】
0004730592.tif 000035
【図５】
0004730592.tif 000036
【図６】
0004730592.tif 000037
【図７】
0004730592.tif 000038
【図８】
0004730592.tif 000039
【図９】
0004730592.tif 000040
【図１０】
0004730592.tif 000041
【図１１】
0004730592.tif 000042
【図１２】
0004730592.tif 000043
【図１３】
0004730592.tif 000044
【図１４】
0004730592.tif 000045
【図１５】
0004730592.tif 000046
【図１６】
0004730592.tif 000047
【図１７】
0004730592.tif 000048
【図１８】
0004730592.tif 000049
【図１９】
0004730592.tif 000050
【図２０】
0004730592.tif 000051
【図２１】
0004730592.tif 000052
【図２２】
0004730592.tif 000053
【図２３】
0004730592.tif 000054
【図２４】
0004730592.tif 000055
【図２５】
0004730592.tif 000056
【図２６】
0004730592.tif 000057
【図２７】
0004730592.tif 000058
【図２８】
0004730592.tif 000059
【図２９】
0004730592.tif 000060
【図３０】
0004730592.tif 000061
【図３１】
0004730592.tif 000062
【図３２】
0004730592.tif 000063
【図３３】
0004730592.tif 000064
【図３４】
0004730592.tif 000065