JP2007036776A - 復号装置および復号方法 - Google Patents

Abstract

【課題】 復号装置のスループットを向上させる。
【解決手段】 受信部８１１は、受信データD416を２個ずつ同時に記憶し、既に記憶している受信データD811を６個ずつ計算部４１５に供給する。計算部４１５は、受信データD811と第１の演算の結果得られる復号途中結果D414とを用いて第２の演算を行い、計算部４１２は、第２の演算の結果得られる復号途中結果D411と前回の第１の演算の結果得られる復号途中結果D413とを用いて第１の演算を行う。最後の第２の演算の結果得られる復号途中結果D415は、出力部８１２に供給され、出力部８１２は、その復号途中結果D415を記憶する。出力部８１２は、既に記憶している復号途中結果D415を２つずつ復号結果として同時に読み出し、出力する。本発明は、例えば、衛星放送を受信するチューナに適用できる。
【選択図】 図１５

Description

本発明は、復号装置および復号方法に関し、特に、低密度パリティ検査符号（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", 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の転置行列H^Tとの間に、式GH^T=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符号の復号は、一般的には、図３に示すような手順にしたがって行われる。なお、ここでは、受信値をU₀とし、チェックノードから出力されるメッセージをu_jとし、バリアブルノードから出力されるメッセージをv_iとする。また、ここでは、メッセージとは、値の"0"らしさを、いわゆる対数尤度比(log likelihood ratio)で表現した実数値である。さらに、受信値U₀の"0"らしさの対数尤度比を、受信データu_0iと表すこととする。

まず、LDPC符号の復号においては、図３に示すように、ステップＳ１１において、受信値U₀(受信データu_0i)が受信され、メッセージu_jが"0"に初期化されるとともに、繰り返し処理のカウンタとしての整数をとる変数kが"0"に初期化され、ステップＳ１２に進む。ステップＳ１２において、受信値U₀(受信データu_0i)に基づいて、式（１）に示す演算を行うことによってメッセージv_iが求められ、さらに、このメッセージv_iに基づいて、式（２）に示す演算を行うことによってメッセージu_jが求められる。

・・・（１）

・・・（２）

ここで、式（１）と式（２）におけるd_vとd_cは、それぞれ、検査行列Hの縦方向（行方向）と横方向（列方向）の"1"の個数を示す任意に選択可能とされるパラメータであり、例えば、(3,6)符号の場合には、d_v=3，d_c=6となる。

なお、式（１）または（２）の演算においては、それぞれ、メッセージを出力しようとする枝(edge)から入力されたメッセージを、和または積演算のパラメータとしては用いないことから、和または積演算の範囲が、１乃至d_v-1または１乃至d_c-1となっている。また、式（２）に示す演算は、実際には、２入力v₁，v₂に対する１出力で定義される式（３）に示す関数R(v₁,v₂)のテーブルを予め作成しておき、これを式（４）に示すように連続的（再帰的）に用いることによって行われる。

・・・（３）

・・・（４）

ステップＳ１２では、さらに、変数kが"1"だけインクリメントされ、ステップＳ１３に進む。ステップＳ１３では、変数kが所定の繰り返し復号回数N以上であるか否かが判定される。ステップＳ１３において、変数kがN以上ではないと判定された場合、ステップＳ１２に戻り、以下、同様の処理が繰り返される。

また、ステップＳ１３において、変数kがN以上であると判定された場合、ステップＳ１４に進み、式（５）に示す演算を行うことによって最終的に出力する復号結果としてのメッセージvが求められて出力され、LDPC符号の復号処理が終了する。

・・・（５）

ここで、式（５）の演算は、式（１）の演算とは異なり、バリアブルノードに接続している全ての枝からの入力メッセージを用いて行われる。

このようなLDPC符号の復号は、例えば(3,6)符号の場合には、図４に示すように、各ノード間でメッセージの授受が行われる。なお、図４における"="で示すノード（バリアブルノード）では、式（１）に示した演算が行われ、"+"で示すノード（チェックノード）では、式（２）に示した演算が行われる。特に、アルゴリズムＡにおいては、メッセージを２元化し、"+"で示すノードにて、d_c-1個の入力メッセージの排他的論理和演算を行い、"="で示すノードにて、受信値Rに対して、d_v-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)は、バリアブルノードの演算とチェックノードの演算とを繰り返し行う。

バリアブルノードでは、図７のように、式（１）の演算を行う。すなわち、図７において、計算しようとしている枝に対応するメッセージv_iは、バリアブルノードに繋がっている残りの枝からのメッセージu₁およびu₂と、受信データu_0iを用いて計算される。他の枝に対応するメッセージも同様に計算される。

チェックノードの演算について説明する前に、式（２）を、式a×b=exp{ln(|a|)+ln(|b|)}×sign(a)×sign(b)の関係を用いて、式（６）のように書き直す。但し、sign(x)は、x≧0のとき1であり、x＜0のとき-1である。

・・・（６）

更に、x≧0において、φ(x)=ln(tanh(x/2))と定義すると、φ^-1(x)=2tanh^-1(e^-x)であるから、式（６）は、式（７）のように書くことができる。

・・・（７）

チェックノードでは、図８のように、式（７）の演算を行う。すなわち、図８において、計算しようとしている枝に対応するメッセージu_jは、チェックノードに繋がっている残りの枝からのメッセージv₁,v₂,v₃,v₄,v₅を用いて計算される。他の枝に対応するメッセージも同様に計算される。

なお、関数φ(x)は、φ(x)=ln((e^x+1)/(e^x-1))とも表すことができ、x＞0において、φ(x)=φ^-1(x)である。関数φ(x)およびφ^-1(x)をハードウェアに実装する際には、LUT(Look Up Table)を用いて実装される場合があるが、両者共に同一のLUTとなる。

サムプロダクトアルゴリズムをハードウェアに実装する場合、式（１）で表されるバリアブルノード演算および式（７）で表されるチェックノード演算を、適度な回路規模と動作周波数で繰り返し行うことが必要である。

復号装置の実装の例としては、各ノードの演算を１つずつ順次行うことによって、LDPC符号の復号を行う(full serial decoding)復号装置、各ノードの演算を1つや全てでもない、ある数のノードの演算を同時に行う(partly parallel decoding)復号装置(特許文献１)、および全ノードの演算を同時に行うことによって復号を行う(full parallel decoding)復号装置(非特許文献１)が提案されている。

以下では、各ノードの演算を複数個ずつ順次行うことによって復号を行う場合(partly parallel decoding)の実装法について説明する。

なお、ここでは、例えば、図９の、３６（行）×１０８（列）の検査行列Hで表現される符号（符号化率2/3、符号長108）を復号することとする。図９の検査行列Hの１の数は３２３であり、従って、そのタナーグラフでは、枝の数は３２３個となる。ここで、図９の検査行列Hでは、０を、"."で表している。また、図９の検査行列Hは、６×６行列の単位に間隔を空けて表している。

図９においては、検査行列Hは、６×６の単位行列、その単位行列の１のうち１個以上が０になった行列（以下、適宜、準単位行列という）、単位行列または準単位行列をサイクリックシフト(cyclic shift)した行列（以下、適宜、シフト行列という）、単位行列、準単位行列、またはシフト行列のうちの２以上(複数)の和（以下、適宜、和行列という）、６×６の０行列の組み合わせで表されている。

なお、図９の検査行列Hを構成する６×６の単位行列、準単位行列、シフト行列、和行列、０行列を、以下、適宜、構成行列という。

図１０を参照して、図９の検査行列Hで表現されるLDPC符号を復号する復号装置について説明する。

図１０は、図９の検査行列Hで表現されるLDPC符号を復号する復号装置４００の構成の一例を示すブロック図である。

復号装置４００は、復号途中結果格納用メモリ４１０、サイクリックシフト回路４１１、６つの計算器４１２₁乃至計算器４１２₆からなる計算部４１２、復号途中結果格納用メモリ４１３、サイクリックシフト回路４１４、６つの計算器４１５₁乃至計算器４１５₆からなる計算部４１５、受信用メモリ４１６、および制御部４１７から構成される。

ここで、計算器４１２_k（k=1,2,・・・，6）で行われる演算と、計算器４１５_kで行われる演算について、式を用いて説明する。

計算部４１２は、上述した式（７）と、以下に表す式（８）とにしたがう第１の演算を行い、その第１の演算の結果である復号途中結果u_jを復号途中結果格納用メモリ４１３に供給して格納させる。計算部４１５は、上述した式（５）にしたがう第２の演算を行い、その第２の演算の結果である復号途中結果vを復号途中結果格納用メモリ４１０に供給して格納させる。

・・・（８）

なお、式（８）のu_dvは、検査行列Hのｉ列のメッセージを求めようとする枝からのチェックノード演算の途中結果（ここでは、チェックノードのメッセージそのもの）を表している。即ち、u_dvは、求めたい枝に対応する復号途中結果である。

上述した式（５）にしたがう第２の演算の結果得られる復号途中結果vは、受信データu_0iと検査行列Hのｉ列の各行の１に対応するすべての枝からのチェックノード演算の復号途中結果u_jとを加算したものであるので、上述した式（７）に用いられる値v_iは、式（５）にしたがう第２の演算の結果得られる復号途中結果vから、検査行列Hのｉ列の、各行の１に対応する枝からのチェックノード演算の復号途中結果u_jのうち、メッセージを求めようとする枝からのチェックノード演算の復号途中結果u_dvを引いた値となる。つまり、式（７）の演算に用いられる値v_iを求める式（１）の演算は、上述した式（５）と式（８）を組み合わせた演算である。

従って、復号装置４００では、計算部４１２による式（７）および式（８）にしたがう第１の演算と、計算部４１５による式（５）にしたがう第２の演算とが交互に行われ、計算部４１５が、最後の第２の演算の結果を復号結果として出力することにより、LDPC符号の繰り返し復号を行うことができる。

なお、ここでは、式（７）と式（８）にしたがう第１の演算結果を、復号途中結果u_jと記載するが、この復号途中結果u_jは、式（７）のチェックノードのメッセージｕ_jに等しい。

また、第２の演算により求められる式（５）のvは、式（１）のバリアブルノード演算結果v_iに対して、メッセージを求めようとする枝からのチェックノードのメッセージu_jを加算したものであるから、検査行列Hの1列（１つのバリアブルノード）に対して、１つだけ求められる。

復号装置４００では、計算部４１２が、計算部４１５による第２の演算の結果である検査行列Hの列に対応する復号途中結果vを用いて、第１の演算を行い、その演算の結果得られる検査行列Hのｉ列の、各行の１に対応する枝のメッセージ（各チェックノードが各枝に出力するメッセージ）の枝からのチェックノード演算の復号途中結果u_jを復号途中結果格納用メモリ４１３に格納する。従って、復号途中結果格納用メモリ４１３の容量は、チェックノード演算の結果を格納する場合と同様に、検査行列Hの１の数（全枝数）と量子化ビット数とを乗算した値となる。

一方、計算部４１５は、計算部４１２による第１の演算の結果である検査行列Hのｉ列の、各行の“１”に対応する復号途中結果u_jと受信データu_0iを用いて、第２の演算を行い、その演算の結果得られるｉ列に対応する復号途中結果vを復号途中結果格納用メモリ４１０に格納する。従って、復号途中結果格納用メモリ４１０に必要な容量は、検査行列Hの“１”の数より少ない検査行列Hの列数、即ち、LCPC符号の符号長と復号途中結果vの量子化ビット数とを乗算した値となる。

その結果、バリアブルノード演算の結果を格納する場合に比べて、復号途中結果格納用メモリ４１０のメモリ容量を削減することができ、これにより、復号装置４００の回路規模を小さくすることができる。

以下、図１０の復号装置４００の各部の動作について詳細に説明する。

復号途中結果格納用メモリ４１０には、計算部４１５から、計算部４１５による第２の演算の結果である検査行列Hの６つの列に対応する６つの復号途中結果D415が供給され、復号途中結果格納用メモリ４１０は、計算部４１５から供給された６つの復号途中結果D415を、第１アドレスから順に格納（記憶）する。

即ち、復号途中結果格納用メモリ４１０の第１アドレスには、検査行列Hの列に対応する復号途中結果のうち、第１列目から第６列目の復号途中結果vが格納される。そして、同様に、第２アドレスには、第７列目から第１２列目の復号途中結果vが格納され、第３アドレスには、第１３列目から第１８列目の復号途中結果が格納される。以後、同様に、第１０３列目から第１０８列目までの復号途中結果vが、６個ずつ、第４アドレスから第１８アドレスまで格納され、計１０８個の復号途中結果vが復号途中結果格納用メモリ４１０に格納される。従って、復号途中結果格納用メモリ４１０のワード（word）数は、図９の検査行列Hの列数（LDPC符号の符号長）である１０８を、同時に読み書きする復号途中結果の数である６で割り算した１８となる。

また、復号途中結果格納用メモリ４１０は、既に格納してある復号途中結果D415から、後段の計算部４１２が求めようとする復号途中結果u_jの対応する検査行列Hの行において“１”になっている復号途中結果vを６つ同時に読み出し、復号途中結果D410として、サイクリックシフト回路４１１に供給する。

なお、復号途中結果格納用メモリ４１０は、例えば、６つの復号途中結果vを同時に読み書き可能なシングルポートRAMで構成される。また、復号途中結果格納用メモリ４１０には、計算部４１５の第２の演算により演算された列に対応する復号途中結果D415が格納されるので、復号途中結果格納用メモリ４１０に格納されるデータ量、即ち、復号途中結果格納用メモリ４１０に必要とされる記憶容量は、復号途中結果D415の量子化ビット数と、検査行列Hの列数（LDPC符号の符号長）との乗算値である。

サイクリックシフト回路４１１には、復号途中結果格納用メモリ４１０から６つの復号途中結果D410が供給されるとともに、制御部４１７から、その復号途中結果D410に対応する検査行列Hの１が、検査行列Hにおいて元となる単位行列などを幾つサイクリックシフトであるかの情報（Matrixデータ）を表す制御信号D418が供給される。サイクリックシフト回路６１１は、制御信号D418を元に、６つの復号途中結果D410を並べ替えるサイクリックシフトを行い、その結果を復号途中結果D411（D411₁乃至D411₆）として、計算部４１２に供給する。

計算部４１２は、６つの計算器４１２₁乃至４１２₆からなる。計算部４１２には、サイクリックシフト回路４１１から、計算部４１５による第２の演算の結果得られた６つの復号途中結果D411（v）が供給されるとともに、復号途中結果格納用メモリ４１３から、前回、計算器４１２₁乃至４１２₆による第１の演算の結果得られた６つの復号途中結果D413（D413₁乃至D413₆）（u_j）が供給され、その６つの復号途中結果D411と６つの復号途中結果D413が、計算器４１２₁乃至４１２₆にそれぞれ供給される。また、計算部４１２には、制御部４１７から制御信号D419が供給され、その制御信号D419が、計算器４１２₁乃至４１２₆に供給される。なお、制御信号D419は、６つの計算器４１２₁乃至４１２₆に共通の信号である。

計算器４１２₁乃至４１２₆は、それぞれ復号途中結果D411と復号途中結果D413を用いて、式（７）と式（８）にしたがって第１の演算を行い、復号途中結果D412（D412₁乃至D412₆）（u_j）を求める。計算部４１２は、計算器４１２₁乃至４１２₆による演算の結果得られる検査行列Hの６つの１に対応する６つの復号途中結果D412を復号途中結果格納用メモリ４１３に供給する。

復号途中結果格納用メモリ４１３は、例えば、６つの復号途中結果D412を同時に読み書き可能な、２つのシングルポートRAMから構成される。復号途中結果格納用メモリ４１３には、計算部４１２から６つの復号途中結果D412が供給されるとともに、制御部４１７から復号途中結果４１３の読み書きを制御する制御信号D420（D420₁乃至D420₄）が供給される。

復号途中結果格納用メモリ４１３は、制御信号D420に基づいて、計算部４１２から供給される６つの復号途中結果D412をまとめて格納すると同時に、既に格納してある６つの復号途中結果D412を読み出し、復号途中結果D413として、計算部４１２とサイクリックシフト回路４１４に供給する。即ち、復号途中結果格納用メモリ４１３は、計算部４１２とサイクリックシフト回路４１４に供給する復号途中結果D413の読み出しと、計算部４１２から供給される復号途中結果D412の書き込みとを、同時に行う。

なお、復号途中結果格納用メモリ４１３には、計算部４１２の第１の演算により演算された検査行列Hのｉ列の、各行の１に対応する枝からの第１の演算の復号途中結果D412が格納されるので、復号途中結果格納用メモリ４１３に格納されるデータ量、即ち、復号途中結果格納用メモリ４１３に必要とされる記憶容量は、復号途中結果D412の量子化ビット数と、検査行列Hの１の数との乗算値となる。

サイクリックシフト回路４１４には、復号途中結果格納用メモリ４１３から６つの復号途中結果D413（復号途中結果u_j）が供給されるとともに、制御部４１７から、その復号途中結果D413に対応する検査行列Hの１が検査行列Hにおいて元となる単位行列などを幾つサイクリックシフトしたものであるかの情報（Matrixデータ）を表す制御信号D421が供給される。サイクリックシフト回路４１４は、制御信号D421を元に、６つの復号途中結果D413を並べ替えるサイクリックシフトを行い、その結果を復号途中結果D414として、計算部４１５に供給する。

計算部４１５は、６つの計算器４１５₁乃至４１５₆からなる。計算部４１５には、サイクリックシフト回路４１４から６つの復号途中結果D414（D414₁乃至D414₆）が供給され、その復号途中結果D414が、計算器４１５₁乃至４１５₆のそれぞれに供給される。また、計算部４１５には、受信用メモリ４１７に記憶されている６つの受信データD416が、受信データD417（LDPC符号）（D417₁乃至D417₆）として供給され、その受信データD417が、計算器４１５₁乃至４１５₆のそれぞれに供給される。さらに、計算部４１７には、制御部４１７から制御信号D422が供給され、その制御信号D422が計算器４１５₁乃至４１５₆に供給される。なお、制御信号D422は、６つの計算器４１７₁乃至４１７₆に共通の信号である。

計算器４１５₁乃至４１５₆は、それぞれ復号途中結果D414と受信データD417とを用いて、式（５）にしたがって、それぞれ第２の演算を行い、復号途中結果D415（D415₁乃至D415₆）を求める。計算部４１５は、計算器４１５₁乃至４１５₆の第２の演算の結果得られる６つの復号途中結果D415(v)を、復号途中結果格納用メモリ４１０に供給する。また、計算部４１５は、いま行う演算が最後の第２の演算である場合、その演算の結果得られる６つの復号途中結果D415を、最終的な復号結果として出力する。

受信用メモリ４１６は、通信路を通して受信した受信値（符号のビット）U₀から計算した符号のビットの０らしさの値である受信LLR（対数尤度比）のデータ（受信データ）D416（ｕ_0i）を１つずつ格納する。

即ち、受信用メモリ４１６の第１のアドレスには、検査行列Hの列に対応する受信データD416のうち、検査行列Hの第１列目から第６列目までに対応する受信データD416が格納される。そして、第２のアドレスには、検査行列Hの第７列目から第１２列目までに対応する受信データD416が格納され、第３アドレスには、検査行列Hの第１３列目から第１８列目までに対応する受信データD416が格納される。以後、同様に、第４アドレスから第１８アドレスまでに、検査行列Hの第１９列目から第１０８列目までに対応する受信データD416が、６つずつ格納される。

そして、受信用メモリ６１６は、既に格納している受信データD416を、バリアブルノード演算に必要となる順番に６つずつ読み出し、受信データD417₁乃至D417₆として計算部４１５に供給する。

なお、受信用メモリ４１６は、例えば、６つの受信データD416を同時に読み書き可能なシングルポートRAMから構成される。また、受信用メモリ４１６に格納されるデータ量、即ち、受信用メモリ３１５に必要とされる記憶容量は、LDPC符号の符号長と、受信データD416の量子化ビット数との乗算値である。さらに、受信用メモリ４１６のワード（word）数は、LDPC符号の符号長、即ち、検査行列Hの列数である１０８を、同時に読み出す受信データD417(D416)の数である６で割り算した値の１８である。

制御部４１７は、制御信号D418をサイクリックシフト回路４１１に、制御信号D419を計算部４１２に供給することにより、それぞれを制御する。また、制御部４１７は、制御信号D420を復号途中結果格納用メモリ４１３に、制御信号D421をサイクリックシフト回路４１４に、制御信号D422を計算部４１５にそれぞれ供給することにより、それぞれを制御する。

復号途中結果格納用メモリ４１０、サイクリックシフト回路４１１、計算部４１２、復号途中結果格納用メモリ４１３、サイクリックシフト回路４１４、計算部４１５の順で、データが一巡することで、復号装置４００は、１回の復号を行うことができる。復号装置４００では、所定の回数だけ繰り返して復号が行われた後、計算部４１５による第２の演算の結果である復号途中結果D415が、最終的な復号結果として１つずつ出力される。

また、サムプロダクトアルゴリズムを近似して実装する方法なども提案されているが、この方法では、性能の劣化を招いてしまう。

特開２００４−３６４２３３号公報 C. Howland and A. Blanksby, "Parallel Decoding Architectures for Low Density Parity Check Codes", Symposium on Circuits and Systems, 2001

しかしながら、図１０の復号装置４００において、受信データD416の入力、または復号結果の出力を、複数個ずつ同時に行い、スループットを向上させることは提案されていなかった。

本発明は、このような状況に鑑みてなされたものであり、復号装置のスループットを向上させることができるようにするものである。

本発明の一側面の復号装置は、LDPC(Low Density Parity Check)符号を復号する復号装置であって、P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、前記LDPC符号の検査行列が、複数の前記構成行列の組み合わせで表される場合、または前記LDPC符号の検査行列が、行または列の置換により、複数の前記構成行列の組み合わせで表される場合において、前記LDPC符号を記憶する符号記憶手段と、前記符号記憶手段に記憶される前記LDPC符号を復号する復号手段と、前記復号手段により復号された結果得られる復号結果を記憶し、既に記憶してある復号結果を読み出す復号結果記憶手段とを備え、前記符号記憶手段は、前記LDPC符号を前記P個以下の複数個ずつ同時に記憶するか、前記復号結果記憶手段は、前記復号結果を前記P個以下の複数個ずつ同時に読み出すか、または前記符号記憶手段は前記LDPC符号を前記P個以下の複数個ずつ同時に記憶し、かつ前記復号結果記憶手段は、前記復号結果を前記P個以下の複数個ずつ同時に読み出す。

前記符号記憶手段は、前記LDPC符号を前記Pの約数個ずつ同時に記憶するか、前記復号結果記憶手段は、前記復号結果を前記Pの約数個ずつ同時に読み出すか、または前記符号記憶手段は前記LDPC符号を前記Pの約数個ずつ同時に記憶し、かつ前記復号結果記憶手段は、前記復号結果を前記Pの約数個ずつ同時に読み出すことができる。

前記符号記憶手段は、前記Pの約数個の前記LDPC符号を同時に読み書き可能なメモリにより構成され、前記復号結果記憶手段は、前記Pの約数個の前記復号結果を同時に読み書き可能なメモリにより構成されることができる。

前記復号装置は、前記符号記憶手段に前記LDPC符号を入力する第１の外部装置、および前記復号結果記憶手段から読み出された復号結果を出力する第２の外部装置の動作クロックに比べて、高速の動作クロックで動作を行うことができる。

前記符号記憶手段は、前記行または列の置換後の前記検査行列の前記P個の列に対応する前記LDPC符号を、同時に読出可能な順に記憶することができる。

前記符号記憶手段は、RAM（Random Access Memory）であり、そのRAMの各アドレスに、前記行または列の置換後の前記検査行列の前記P個の列に対応する前記LDPC符号を記憶することができる。

前記復号装置は、前記符号記憶手段に記憶される前の前記LDPC符号、または前記復号結果記憶手段から読み出された後の前記復号結果の少なくとも一方の順序を制御する順序制御手段をさらに儲けることができる。

前記順序制御手段は、前記LDPC符号を記憶する順序符号記憶手段と、前記順序符号記憶手段に記憶される前記LDPC符号を選択して出力する選択手段とを設けることができる。

前記順序制御手段は、前記復号結果を記憶する順序復号結果記憶手段と、前記順序復号結果記憶手段に記憶される前記復号結果を選択して出力する選択手段とを設けることができる。

本発明の一側面の復号方法は、LDPC(Low Density Parity Check)符号を復号する復号装置の復号方法であって、P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、前記LDPC符号の検査行列が、複数の前記構成行列の組み合わせで表される場合、または前記LDPC符号の検査行列が、行または列の置換により、複数の前記構成行列の組み合わせで表される場合において、前記LDPC符号を記憶させる符号記憶ステップと、前記符号記憶ステップの処理により記憶される前記LDPC符号を復号する復号ステップと、前記復号ステップの処理により復号された結果得られる復号結果を記憶させ、既に記憶されている復号結果を読み出す復号結果記憶ステップとを含み、前記符号記憶ステップの処理は、前記LDPC符号を前記P個以下の複数個ずつ同時に記憶させるか、または前記復号結果記憶ステップの処理は、前記復号結果を前記P個以下の複数個ずつ同時に読み出すか、もしくは前記符号記憶ステップの処理は前記LDPC符号を前記P個以下の複数個ずつ同時に記憶させ、かつ前記復号結果記憶ステップの処理は、前記復号結果を前記P個以下の複数個ずつ同時に読み出す。

本発明の一側面においては、LDPC符号をP個以下の複数個ずつ同時に記憶するか、復号結果を前記P個以下の複数個ずつ同時に読み出すか、または前記LDPC符号を前記P個以下の複数個ずつ同時に記憶し、かつ前記復号結果を前記P個以下の複数個ずつ同時に読み出す。

以上のように、本発明の一側面によれば、復号装置のスループットを向上させることができる。

以下に本発明の実施の形態を説明するが、本発明の構成要件と、発明の詳細な説明に記載の実施の形態との対応関係を例示すると、次のようになる。この記載は、本発明をサポートする実施の形態が、発明の詳細な説明に記載されていることを確認するためのものである。従って、発明の詳細な説明中には記載されているが、本発明の構成要件に対応する実施の形態として、ここには記載されていない実施の形態があったとしても、そのことは、その実施の形態が、その構成要件に対応するものではないことを意味するものではない。逆に、実施の形態が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その実施の形態が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。

本発明の一側面の復号装置は、
LDPC(Low Density Parity Check)符号を復号する復号装置（例えば、図１５の復号装置８００）であって、
P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、前記LDPC符号の検査行列が、複数の前記構成行列の組み合わせで表される場合、または前記LDPC符号の検査行列が、行または列の置換により、複数の前記構成行列の組み合わせで表される場合において、
前記LDPC符号を記憶する符号記憶手段(例えば、図１６の受信メモリ８３４)と、
前記符号記憶手段に記憶される前記LDPC符号を復号する復号手段（例えば、図１５の計算部４１２と４１５）と、
前記復号手段により復号された結果得られる復号結果を記憶し、既に記憶してある復号結果を読み出す復号結果記憶手段(例えば、図２４の復号結果メモリ９０１)と
を備え、
前記符号記憶手段は、前記LDPC符号を前記P個以下の複数個ずつ同時に記憶するか、前記復号結果記憶手段は、前記復号結果を前記P個以下の複数個ずつ同時に読み出すか、または前記符号記憶手段は前記LDPC符号を前記P個以下の複数個ずつ同時に記憶し、かつ前記復号結果記憶手段は、前記復号結果を前記P個以下の複数個ずつ同時に読み出す（例えば、図２９のステップＳ３５の処理、図３１のステップＳ７１の処理）。

前記復号装置は、前記符号記憶手段に前記LDPC符号を入力する第１の外部装置（例えば、図１６のインターリーバ８３１とセレクタ８３２）、および前記復号結果記憶手段から読み出された復号結果を出力する第２の外部装置(例えば、図２４のデインターリーバ９０３とセレクタ９０４)の動作クロック(例えば、低速クロックＣＫ₁またはＣＫ₃)に比べて、高速の動作クロック（例えば、高速クロックＣＫ₂）で動作を行う。

前記符号記憶手段に記憶される前の前記LDPC符号、または前記復号結果記憶手段から読み出された後の前記復号結果の少なくとも一方の順序を制御する順序制御手段（例えば、図１６のインターリーバ８３１）
をさらに設ける。

前記順序制御手段(例えば、図１７のインターリーバ８３１)は、
前記LDPC符号を記憶する順序符号記憶手段(例えば、図１７のレジスタ８５１−１乃至８５１−５および８５２−１乃至８５２−５)と、
前記順序符号記憶手段に記憶される前記LDPC符号を選択して出力する選択手段(例えば、図１７のセレクタ８５３)と
を設ける

前記順序制御手段(例えば、図２６のデインターリーバ９０３)は、
前記復号結果を記憶する順序復号結果記憶手段(例えば、レジスタ９２１−１乃至９２１−５と９２２−１乃至９２２−５)と、
前記順序復号結果記憶手段に記憶される前記復号結果を選択して出力する選択手段（例えば、図２６のセレクタ９２３）と
を設ける。

本発明の一側面の復号方法は、
LDPC(Low Density Parity Check)符号を復号する復号装置(例えば、図１５の復号装置８００)の復号方法であって、
P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、前記LDPC符号の検査行列が、複数の前記構成行列の組み合わせで表される場合、または前記LDPC符号の検査行列が、行または列の置換により、複数の前記構成行列の組み合わせで表される場合において、
前記LDPC符号を記憶させる符号記憶ステップ（例えば、図２９のステップＳ３５）と、
前記符号記憶ステップの処理により記憶される前記LDPC符号を復号する復号ステップ（例えば、図３０の復号処理）と、
前記復号ステップの処理により復号された結果得られる復号結果を記憶させ、既に記憶されている復号結果を読み出す復号結果記憶ステップ（例えば、図３１のステップＳ７１）と
を含み、
前記符号記憶ステップの処理は、前記LDPC符号を前記P個以下の複数個ずつ同時に記憶させるか、または前記復号結果記憶ステップの処理は、前記復号結果を前記P個以下の複数個ずつ同時に読み出すか、もしくは前記符号記憶ステップの処理は前記LDPC符号を前記P個以下の複数個ずつ同時に記憶させ、かつ前記復号結果記憶ステップの処理は、前記復号結果を前記P個以下の複数個ずつ同時に読み出す(例えば、図２９のステップＳ３５の処理、図３１のステップＳ７１の処理)。

図１１は、LDPC符号の復号に用いる検査行列Hの例を示している。

図１１の検査行列Hは、n=108，k=72の符号語ｃ（符号化率2/3、符号長108）を得るための検査行列Hであり、３６(行)×１０８（列）の行列である。なお、図１１の検査行列Hでは(後述する図１２乃至１４の行列においても同様)、０を、"."で表現している。また、図１１の検査行列Hは、６×６の行列の単位に間隔を空けて表したものである。

即ち、検査行列Hは、３６（=n-k）行７２（=k）列の情報部と、３６(=n-k)行３６（=n-k）列のパリティ部とから構成される。

図１１の検査行列Hでは、LDPC符号の情報語ｉに対応する情報部の各行は、７個の“１”と、１０１個の“０”から構成される。パリティ部は、下三角状の構造を有する行列（下三角行列）となっている。即ち、図１１の検査行列Hのパリティ部は、行列の対角線の右上が全て“０”とされた行列となっており、下三角状の構造を有している。

図１２と図１３は、図１１の検査行列Hを行置換または列置換した後の検査行列H´を示している。

図１２の検査行列H´では、情報部を、P×P（図１２の例の場合、P＝６）の単位行列、その単位行列の１のうち１個以上が０になった準単位行列、単位行列または準単位行列をサイクリックシフトしたシフト行列、単位行列、準単位行列、またはシフト行列のうちの２以上(複数)の和である和行列、P×Pの０行列の組み合わせで表すことができる。即ち、図１２の検査行列H´は、６×６の構成行列の組み合わせで表すことができる。

図１３の検査行列H´は、図１２に示した検査行列H´を、６×６の構成行列の単位に間隔を空けて表したものである。検査行列H´を構成する横方向の構成行列の数をｎ₀個とし、検査行列H´の情報部を構成する横方向の構成行列の数をｋ₀個とすると、ｎ₀（=n/P=108/6）は18となり、ｋ₀（=k/P=72/6）は12となる。

即ち、図１２や図１３の検査行列H´では、縦方向に６（=ｎ₀-ｋ₀=18-12）個の構成行列が、横方向にｎ₀(=18)個の構成行列が並んでいる。

また、図１１の検査行列Hのパリティ部の一番左の列（先頭列）を０列目とすると、検査行列Hのパリティ部の（n₀-k₀）×v＋w（0≦v≦P-1,0≦ｗ≦n₀-k₀-1）列目の列は、図１２や図１３の検査行列H´のパリティ部では、P×w+v列目の列となっている。

以上のように、図１２や図１３の検査行列H´は構成行列で構成されるため、検査行列H´を用いてLDPC符号の復号が行われる場合、LDPC符号の復号に必要な、第１の演算の結果得られる復号途中結果u_jの第２の演算に用いられる順序での読出、および第２の演算の結果得られる復号途中結果vの第１の演算に用いられる順序での読出を、６個単位で復号途中結果u_jとvをサイクリックシフトすることにより行うことができる。また、６個単位で復号途中結果u_jをサイクリックシフトすることにより、第２の演算における復号途中結果u_jと検査行列H´の行との積を、６個同時に計算することができる。

図１４Ａ乃至図１４Ｂは、図１１の検査行列Hと図１２や図１３の検査行列H´のパリティ部を示している。

図１４Ａに示すように、図１１の検査行列Hのパリティ部は、行列の対角線の右上が全て“０”とされた行列となっており、下三角状の構造を有している。また、パリティ部は、下三角行列の対角成分とその成分の直下の成分が１であり、それ以外の成分が０となっている。

図１４Ｂに示すように、図１２や図１３の検査行列H´のパリティ部では、対角成分が６×６の単位行列の対角成分となるように、６×６の単位行列が対角方向に配置され、その単位行列の直下にも６×６の単位行列が配置されている。さらに、パリティ部では、右上に、６×６の単位行列の最上行の１が０になった行列を左に１だけサイクリックシフトした行列が配置されている。以上の他は、６×６の０行列が配置されている。図１４Ｂのパリティ部では、図１４Ａのパリティ部の（n₀-k₀）×v＋w列目の行が、P×w＋v列目の列となる。

図１５は、本発明の一実施の形態の、LDPC符号を復号する復号装置８００の構成例を示している。なお、図中、図１０の復号装置４００と対応する部分については、同一の符号を付してあり、以下では、その説明は、適宜省略する。

図１５の復号装置８００は、復号途中結果格納用メモリ４１０、サイクリックシフト回路４１１、６つの計算器４１２₁乃至計算器４１２₆からなる計算部４１２、復号途中結果格納用メモリ４１３、サイクリックシフト回路４１４、６つの計算器４１５₁乃至計算器４１５₆からなる計算部４１５、および制御部４１７が設けられている点で、図１０の復号装置４００と共通するが、受信用メモリ４１６に代えて受信部８１１が設けられ、新たに出力部８１２が設けられている点で、図１０の復号装置４００と相違している。

ここで、図１５の復号装置８００では、例えば、図１１に示した検査行列Hで表されるLDPC符号（符号化率2/3、符号長108）の復号が行われることとする。

図１５の復号装置８００では、受信データD416が検査行列H´に対応する順に並び替えられ、その並び替え後の受信データD811を用いて、計算部４１５が検査行列H´に対応する第２の演算を６個ずつ行い、計算部４１２が検査行列H´に対応する第１の演算を６個ずつ行い、これらの第１の演算と第２の演算とが交互に行われる。そして、最後の第２の演算の結果得られる復号途中結果D415を、検査行列Hに対応する順に並び替えることによって、LDPC符号が復号される。

即ち、受信部８１１には、検査行列Hで表されるLDPC符号の受信値U₀が受信され、受信データD416（u_0i）が供給されて、記憶される。そして、受信部８１１は、既に記憶している受信データD416から、検査行列H´に対応する第２の演算に必要となる順に６つの受信データD416を読み出し、受信データD811₁乃至D811₆（D811）として計算部４１５に供給する。換言すれば、受信部８１１は、検査行列Hに対応する順に供給される受信データD416を、検査行列H´に対応する順に並び替えて受信データD811として計算部４１５に供給する。

そして、計算部４１５は、LDPC符号の復号のための検査行列H´に対応する第２の演算を行う。

即ち、復号途中結果格納用メモリ４１３には、後述する計算部４１２による第１の演算の結果としての復号途中結果D412₁乃至D412₆（D412）（u_j）が格納されており、復号途中結果格納用メモリ４１３は、既に格納してある復号途中結果D412のうち、６つの復号途中結果D412を、復号途中結果D413₁乃至D413₆（D413）として、サイクリックシフト回路４１４と計算部４１２に供給する。

サイクリックシフト回路４１４は、制御部４１７からの制御信号D421に基づき、復号途中結果D413をサイクリックシフトし、その結果を復号途中結果D414₁乃至D414₆（D414）として計算部４１５に供給する。さらに、計算部４１５には、制御部４１７から制御信号D422が供給されるとともに、受信部８１１から６つの受信データD811が供給される。

計算器４１５は、計算器４１５₁乃至４１５₆から構成される。各計算器４１５_kは、制御信号D422に基づき、サイクリックシフト回路４１４から供給される復号途中結果D414_k（u_j）と、受信部８１１から供給される受信データD811_k（u_0i）とを用い、式（５）にしたがって第２の演算を行う。そして、各計算器４１５_kは、第２の演算の結果得られる復号途中結果D415_k（v）を、復号途中結果格納用メモリ４１０に供給する。

復号途中結果格納用メモリ４１０は、計算部４１５から供給される、６つの第２の演算の結果である復号途中結果D415₁乃至D415₆（D415）（v）を格納していく。そして、復号途中結果格納用メモリ４１０は、既に格納してある復号途中結果D415から、６つの復号途中結果D415を、復号途中結果D410として読み出し、サイクリックシフト回路４１１に供給する。サイクリックシフト回路４１１は、制御部４１７から供給される制御信号D418に基づき、６つの復号途中結果D410をサイクリックシフトし、その結果を復号途中結果D411₁乃至D411₆（D411）として計算部４１２に供給する。

計算部４１２は、LDPC符号の復号のための検査行列H´に対応する第１の演算を行う。

即ち、計算部４１２は、計算器４１２₁乃至４１２₆から構成される。各計算器４１２_kは、制御部４１７から供給される制御信号D419に基づき、サイクリックシフト回路４１１から供給される復号途中結果D411_kと、復号途中結果格納用メモリ４１３から供給される、前回の計算部４１２による第１の演算の結果得られた復号途中結果D413_kとを用いて、式（７）と式（８）にしたがって第１の演算を行い、その第１の演算によって求められた６つの復号途中結果D412_k（u_j）を、復号途中結果格納用メモリ４１３に供給する。

復号途中結果格納用メモリ４１３は、計算部４１２から供給される復号途中結果D412₁乃至D412₆を格納していく。そして、復号途中結果格納用メモリ４１３に記憶された復号途中結果D412は、上述したように復号途中結果D413₁乃至D413₆として読み出され、サイクリックシフト回路４１４と計算部４１２に供給される。

以上のように、第１の演算と第２の演算とが交互に所定の回数だけ繰り返し行われた後、計算部４１５による第２の演算の結果得られる復号途中結果D415が、出力部８１２に供給される。

出力部８１２は、計算部４１５から供給される、検査行列H´に対応する第２の演算の結果得られる復号途中結果D415を記憶する。そして、出力部８１２は、既に記憶してある復号途中結果D415を検査行列Hに対応する順に読み出し、復号結果として出力する。即ち、出力部８１２は、検査行列H´に対応する順に供給される復号途中結果D415を、検査行列Hに対応する順に並び替え、復号結果として出力する。これにより、検査行列Hで表されるLDPC符号の繰り返し復号の結果を出力することができる。

図１６は、図１５の受信部８１１の詳細構成例を示すブロック図である。

図１６の受信部８１１は、インターリーバ８３１、セレクタ８３２、ビット幅調整回路８３３、受信メモリ８３４、および制御部８３５から構成される。

なお、図１６では、インターリーバ８３１とセレクタ８３２は、低速クロックＣＫ₁で動作し、ビット幅調整回路８３３、受信メモリ８３４、および制御部８３５は、高速クロックＣＫ₂（ＣＫ₂＞ＣＫ₁）で動作する。

また、受信部８１１には、受信値U₀から生成された受信データD416が２つずつ供給されるものとする。即ち、受信部８１１には、受信データD416が検査行列Hに対応する順序で２つずつ供給され、その受信データD416は、インターリーバ８３１とセレクタ８３２に供給される。

インターリーバ８３１は、低速クロックＣＫ₁に同期して、制御部８３５からの制御信号D834に基づいて、２つの受信データD416の順序を制御する。具体的には、受信データD416の、受信値U₀の情報メッセージｕに対応する成分、即ち検査行列Hの情報部に対応する成分（以下、情報成分という）が、インターリーバ８３１に供給される場合、制御信号D834は「０」となり、パリティビットに対応する成分、即ち検査行列Hのパリティ部に対応する成分（以下、パリティ成分という）がインターリーバ８３１に供給される場合、制御信号D834は「１」となる。

制御信号D834が「０」である場合、インターリーバ８３１は、２つの受信データD416をそのまま受信データD831としてセレクタ８３２に供給する。一方、制御信号D834が「１」である場合、インターリーバ８３１は、２つの受信データD416を検査行列H´に対応する順序に並び替え、並び替え後の２つの受信データD831をセレクタ８３２に供給する。即ち、インターリーバ８３１は、２つの受信データD416のパリティ成分の順序を制御する。

セレクタ８３２は、低速クロックＣＫ₁に同期して、制御部８３５からの制御信号D835に基づいて、２つの受信データD416またはインターリーバ８３１からの２つの受信データD831のいずれか一方を選択し、その選択した２つの受信データD416またはD831を、２つの受信データD832としてビット幅調整回路８３３にパラレルに供給する。

具体的には、高速クロックＣＫ₂の速度が低速クロックＣＫ₁の速度の２倍未満であるとき、制御信号D835は「０」となり、高速クロックの速度が低速クロックの速度の２倍以上であるとき、制御信号D835は「１」となる。制御信号D835が「０」である場合、セレクタ８３２は、インターリーバ８３１からの２つの受信データD831を選択し、制御信号D835が「１」である場合、セレクタ８３２は、２つの受信データD416を選択する。

ビット幅調整回路８３３は、高速クロックＣＫ₂に同期して、制御部８３５からの制御信号D835に基づいて、セレクタ８３２からの受信データD832のビット幅を調整する。具体的には、制御信号D835が「０」である場合、ビット幅調整回路８３３は、例えば低速クロックＣＫ₁の1クロックに同期してパラレルに供給される２つの受信データD832を、高速クロックＣＫ₂の1クロックに同期して、２つの受信データD833として、パラレルに受信メモリ８３４に供給する。

一方、制御信号D835が「１」である場合、ビット幅調整回路８３３は、低速クロックＣＫ₁の１クロックに同期してパラレルに供給される２つの受信データD832のビット幅を調整し、高速クロックＣＫ₂の１クロックに同期して、１つずつ、受信データD833としてシリアルに受信メモリ８３４に供給する。即ち、ビット幅調整回路８３３は、高速クロックＣＫ₂の２クロック間で、２つの受信データD833をシリアルに受信メモリ８３４に供給する。

受信メモリ８３４は、例えば、RAM（Random Access Memory）により構成され、２つの受信データD833を同時に書き込んだり、６つの受信データD811を同時に読み出すことが可能である。なお、受信メモリ８３４のビット数はP（=6）と受信データD833の量子化ビット数を乗算した値であり、ワード数はn/P(=n₀=18)である。受信メモリ８３４は、高速クロックＣＫ₂に同期して、制御部８３５からの制御信号D834に基づいて、ビット幅調整回路８３３から供給される受信データD833を、検査行列H´の６つの列に対応するものを同時に読出可能な順に、ビット方向（縦方向）（後述する図１８）またはワード方向（横方向）に書き込む。

具体的には、制御信号D834が「０」である場合、受信メモリ８３４は、受信データD833をビット方向に書き込む。一方、制御信号D834が「１」である場合、受信メモリ８３４は、受信データD833をワード方向に書き込む。即ち、情報成分に対応する受信データD833はビット方向に書き込まれ、パリティ成分に対応する受信データD833は、ワード方向に書き込まれる。

受信メモリ８３４は、高速クロックＣＫ₂に同期して、既に記憶してある受信データD833を、ビット方向に６つ単位で読み出し、受信データD811として計算部４１５に供給する。

制御部８３５は、低速クロックＣＫ₁に同期して、制御信号D834をインターリーバ８３１に供給するとともに、高速クロックＣＫ₂に同期して、制御信号D834を受信メモリ８３４に供給する。また、制御部８３５は、低速クロックＣＫ₁に同期して、制御信号D835をセレクタ８３２に供給する。

図１７は、図１６のインターリーバ８３１の詳細構成例を示す図である。

図１７のインターリーバ８３１は、５つのレジスタ８５１−１乃至８５１−５および５つのレジスタ８５２−１乃至８５２−５、並びにセレクタ８５３から供給される。

インターリーバ８３１には、受信データD416が２つずつ供給され、そのうちの１つが受信データD851としてレジスタ８５１−１乃至８５１−５に順に記憶される。また、他の１つが受信データD852としてレジスタ８５２−１乃至８５２−５に順に記憶される。レジスタ８５１−１乃至８５１−５とレジスタ８５２−１乃至８５２−５は、記憶している受信データD851またはD852をそれぞれセレクタ８５３に供給する。また、２つの受信データD416は、それぞれ受信データD851またはD852として、セレクタ８５３に直接供給される。

セレクタ８５３は、レジスタ８５１−１乃至８５１−５とレジスタ８５２−1乃至８５２−５のそれぞれから供給される５つの受信データD851またはD852と、直接供給される受信データD851またはD852のうち、いずれか２つの受信データD851またはD852を選択し、受信データD853とD854として出力する。受信データD853とD854は合わせられ、２つの受信データD831としてセレクタ８３２に供給される。

以上のように、インターリーバ８３１では、レジスタ８５１−１乃至８５１−５およびレジスタ８５２−１乃至８５２−５が、入力された受信データD416（受信データD851またはD852）を記憶し、セレクタ８５３が、そのレジスタ８５１−１乃至８５１−５およびレジスタ８５２−１乃至８５２−５に記憶されている受信データD416を選択して、受信データD831（受信データD853とD854）として出力することにより、入力される受信データD416と出力される受信データD831の順序を入れ替える。

次に、図１８と図１９を参照して、図１６の受信メモリ８３４に記憶される受信データD833について説明する。

なお、以下の説明に用いる受信メモリ８３４のワード方向とは、図１８に示すように、図中横方向であり、左端から順に０番アドレス、１番アドレス、２番アドレス、・・・という。また、受信メモリ８３４のビット方向とは、図中縦方向であり、上から順に０ビット目、１ビット目、２ビット目、・・・という。

また、以下では、検査行列Hの情報部のｍ列目に対応する受信データD833の情報成分を、受信データＩ_mとも表し、検査行列Hのパリティ部のｍ列目に対応する受信データD833のパリティ成分を、受信データＤ_mとも表す。

図１９を参照して、受信メモリ８３４について説明する。なお、図１９では、説明の便宜上、受信メモリ８３４のビットを、受信データD833の量子化ビットが１ビットであるとして説明する。

図１９に示すように、受信メモリ８３４のビット数は、Ｐ(=6)と受信データD833の量子化ビット数を乗算した値であり、ワード数は、n/p（=18）である。

まず最初に、受信メモリ８３４は、制御部８３５から供給される制御信号D834に基づいて、ビット幅調整回路８３３から供給される２つの受信データＩ₀とＩ₁を、０番アドレスの０ビット目と１ビット目にそれぞれ記憶する。

次に、受信メモリ８３４は、制御信号D834に基づいて、ビット幅調整回路８３３からの２つの受信データＩ₂とＩ₃を、０番アドレスの２ビット目と３ビット目にそれぞれ記憶する。

そして、同様の処理が繰り返され、受信メモリ８３４の０番アドレスの０乃至５ビット目には、受信データＩ₀乃至Ｉ₅がビット方向にそれぞれ記憶され、受信メモリ８３４の１番アドレスの０乃至５ビット目には、受信データＩ₆乃至Ｉ₁₁がビット方向にそれぞれ記憶される。以降も同様にして、受信メモリ８３４の２乃至１１（=k₀-1）番アドレスに、受信データＩ₁₂乃至Ｉ₇₁が記憶される。

次に、受信メモリ８３４は、制御部８３５から供給される制御信号D834に基づいて、ビット幅調整回路８３３から供給される受信データＤ₀を、１２番アドレスの０ビット目に記憶する。また、受信メモリ８３４は、制御信号D834に基づいて、ビット幅調整回路８３３からの受信データＤ₁を１３番アドレスの０ビット目に記憶する。

そして、同様の処理が繰り返され、受信メモリ８３４の１２乃至１７（=n₀-1）番アドレスの０ビット目には、受信データＤ₀乃至Ｄ₅がワード方向にそれぞれ記憶され、受信メモリ８３４の１２乃至１７番アドレスの１ビット目には、受信データＤ₆乃至Ｄ₁₁がワード方向にそれぞれ記憶される。以降も同様にして、受信メモリ８３４の２乃至６ビット目に、受信データＤ₁₂乃至Ｄ₃₅が記憶される。

ここで、１２乃至１７番アドレスの、ワード方向での順番が（n₀-k₀）×x+y（x=0,1,・・・，5，y=0,1,・・・，5）番目の受信データＤ_mは、ビット方向での順番がP×y+x番目となる。なお、ビット方向の順番は、各番号アドレスの５ビット目の次が、右隣のアドレス（次の番号のアドレス）の０ビット目となるものとする。また、ワード方向の順番は、各ビットの５番アドレスの次が、直下のビット(次のビット)の０番アドレスとなるものとする。例えば、ビット方向での順番が６番目の受信データD833は、受信データＤ₁となり、ワード方向での順番が６番目の受信データD833は受信データＤ₆となる。

上述したように、図１１の検査行列Hのパリティ部の（n₀-k₀）×v＋w列目の列は、図１２の検査行列H´のパリティ部では、P×w+v列目の列となる。即ち、検査行列H´のパリティ部のP×w+v列目の列は、検査行列Hのパリティ部の（n₀-k₀）×v＋w列目の列である。従って、受信メモリ８３４のワード方向に記憶される、検査行列Hのパリティ部の０列目から順に対応する受信データＤ_mは、ビット方向の順番に見ると、検査行列H´のパリティ部の０列目から順に対応する受信データＤ_mとなる。

即ち、復号装置８００では、検査行列H´の列に対応する受信データD811を用いて第２の演算を行うため、検査行列Hの列に対応する順に供給される受信データD416の順番を、検査行列H´の列に対応する順番に入れ替える必要がある。上述したように、検査行列Hと検査行列H´の列の順番は、情報部においては同一であるが、パリティ部においては異なる。従って、受信メモリ８３４は、受信データD831のパリティ成分をワード方向に記憶し、ビット方向に読み出すことにより、第２の演算を行う計算部４１５に、検査行列H´の６つの列に対応する受信データD811を同時に供給することができる。

以上のように、図１９の受信メモリ８３４のアドレスは、検査行列H´の６つの列に対応しており、受信メモリ８３４は、同一のアドレスの受信データD831をビット方向に読み出すことにより、検査行列H´の６つの列に対応する受信データD811を読み出すことができる。

次に、図２０と図２１を参照して、図１６の受信部８１１への受信データD416のパリティ成分の入力と、受信メモリ８３４への受信データＤ_mの書き込みとを説明する。図２０と図２１において、横軸は時間を表している。

なお、以下では、検査行列Hのｍ列に対応する受信データD416のパリティ成分を、受信データＡ_mともいう。

図２０は、高速クロックＣＫ₂の速度が低速クロックＣＫ₁の速度の２倍以上である場合の、受信データＡ_mの入力と、受信データＤ_mの書き込みとを説明するタイミングチャートである。

図２０に示すように、受信部８１１には、受信データＡ_mが、２つずつ入力される。例えば、受信部８１１には、受信データＡ₀とＡ₁、受信データＡ₂とＡ₃、受信データＡ₄とＡ₅、受信データＡ₆とＡ₇・・・が順にパラレルに入力される。

図２０では、高速クロックＣＫ₂の速度が低速クロックＣＫ₁の速度の２倍以上である、即ち制御信号D835が「１」であるので、セレクタ８３２は、受信部８１１に入力される２つの受信データＡ_mを、ビット幅調整回路８３３に供給する。

図２０に示すように、ビット幅調整回路８３３は、セレクタ８３２から低速クロックＣＫ₁の１クロックに同期してパラレルに入力される２つの受信データＡ_mを、高速クロックＣＫ₂の１クロックに同期して、１つずつ、受信データＤ_mとして受信メモリ８３４にシリアルに供給し、書き込ませる。

例えば、受信部８１１に低速クロックＣＫ₁に同期して、受信データＡ₀とＡ₁がパラレルに入力される場合、受信メモリ８３４は、高速クロックＣＫ₂の１クロックに同期して、受信データＤ₀を１２番アドレスの０ビット目に書き込んだ後、次の１クロックに同期して受信データＤ₁を１３番アドレスの０ビット目に書き込む。

以上のように、図２０では、受信メモリ８３４以外のインターリーバ８３１やセレクタ８３２の動作クロックである低速クロックＣＫ₁の、２倍以上の速度の高速クロックＣＫ₂で受信メモリ８３４が動作するので、低速クロックＣＫ₁の１クロックの間に、２つの受信データＤ_mを異なるアドレスに書き込むことができる。

その結果、復号装置８００に受信データＡ_mを２個ずつ同時に入力し、スループットを向上させることができる。

図２１は、高速クロックＣＫ₂の速度が低速クロックＣＫ₁の速度の２倍未満である場合の、受信データＡ_mの入力と、受信データＤ_mの書き込みとを説明するタイミングチャートである。

図２１に示すように、受信部８１１には、図２０と同様に、受信データＡ₀とＡ₁、受信データＡ₂とＡ₃、受信データＡ₄とＡ₅、受信データＡ₆とＡ₇・・・が順にパラレルに入力される。

図２１では、高速クロックＣＫ₂の速度が低速クロックＣＫ₁の速度の２倍未満である、即ち制御信号D835が「０」であるので、セレクタ８３２は、インターリーバ８３１から供給される受信データD831を、ビット幅調整回路８３３を介して受信メモリ８３４に供給する。

即ち、インターリーバ８３１（図１７）には、受信データＡ₀とＡ₁、受信データＡ₂とＡ₃、受信データＡ₄とＡ₅、受信データＡ₆とＡ₇・・・がパラレルに順に入力され、レジスタ８５１−１乃至８５１−５は、パラレルに入力された２つの受信データＡ_mのうちの一方（例えば、受信データＡ₀、Ａ₂，Ａ₄，Ａ₆，・・・）を受信データD851として記憶し、レジスタ８５１−２乃至８５２−５は、他方（例えば、受信データＡ₁、Ａ₃，Ａ₅，Ａ₇，・・・）を受信データD852として記憶する。そして、レジスタ８５１−１乃至８５１−５と８５２−１乃至８５２−５は、受信データＡ_m（受信データD851またはD852）をそれぞれセレクタ８５３に供給する。また、２つの受信データＡ_mは、それぞれ、受信データD851またはD852として、直接セレクタ８５３に供給される。

セレクタ８５３は、まず最初に、受信データＡ₀とＡ₆を選択し、受信データD853とD854としてそれぞれ出力する。次に、セレクタ８５３は、受信データＡ₁とＡ₇を選択し、受信データD853とD854としてそれぞれ出力する。その後、セレクタ８５３は、受信データＡ₂とＡ₈、受信データＡ₃とＡ₉・・・の順に選択して出力する。

即ち、インターリーバ８３１にパラレルで入力される２つの受信データＡ_mを、６（=n₀-k₀）つ単位（３回のパラレル入力単位）で交互に系列＃１または系列＃２というと、セレクタ８５３は、系列＃１（例えば、受信データＡ₀乃至Ａ₅）と系列＃２（例えば、受信データＡ₆乃至Ａ₁₁）を、受信データＡ₀とＡ₆から、入力された順に２つずつ選択し、出力する。即ち、セレクタ８５３は、受信メモリ８３４のビット方向に書き込まれる受信データＤ_mに対応する受信データＡ_mを、２つずつ選択して出力する。

インターリーバ８３１のセレクタ８５３により出力された２つの受信データＡ_mは、セレクタ８３２とビット幅調整回路８３３を介して、２つの受信データＤ_mとして受信メモリ８３４に供給される。そして、受信メモリ８３４は、高速クロックＣＫ₂の1クロックに同期して、２つの受信データＡ_mを同一のアドレスにパラレルに書き込む。

具体的には、図２１に示すように、受信メモリ８３４には、受信データＤ₀とＤ₆、受信データＤ₁とＤ₇、受信データＤ₂とＤ₈、受信データＤ₃とＤ₉・・・が順にパラレルに供給される。そして、受信メモリ８３４は、まず最初に、高速クロックＣＫ₂の１クロックに同期して、２つの受信データＤ₀とＤ₆を、１２番アドレスの０ビット目と１ビット目にパラレルに書き込む。以降同様にして、受信メモリ８３４は、受信データＤ₁とＤ₇、受信データＤ₂とＤ₈、受信データＤ₃とＤ₉・・・を、１３番アドレス、１４番アドレス、１５番アドレス・・・の０ビット目と１ビット目にパラレルで書き込む。

以上のように、インターリーバ８３１は、受信メモリ８３４のビット方向に書き込まれる受信データＤ_mに対応する受信データＡ_mを、２つずつ選択して出力するので、受信メモリ８３４は、２つの受信データＤ_mをパラレルに書き込むことができる。これにより、高速クロックＣＫ₂が、低速クロックＣＫ₁の２倍未満である場合においても、低速クロックＣＫ₁の１クロックの間に、２つの受信データＤ_mを書き込むことができる。

その結果、高速クロックＣＫ₂の速度を低速クロックＣＫ₁の速度の２倍以上に上げずに、復号装置８００のスループットを向上させることができる。

図２２は、図１５の計算部４１２の計算器４１２_kの構成例を示すブロック図である。

図２２では、前回の計算部４１２による第１の演算の結果得られる各復号途中結果D412_k（D413_k）(u_dv)が符号ビットを合わせて合計６ビット(bit)に量子化され、計算部４１５による第２の演算の結果得られる各復号途中結果D415（D411_k）（v）が９ビットに量子化されているものとして、計算器４１２_kを表している。さらに、図２２の計算器４１２_kには、高速クロックＣＫ₂が供給され、この高速クロックＣＫ₂は、必要なブロックに供給されるようになっている。そして、各ブロックは、高速クロックＣＫ₂に同期して処理を行う。

図２２の計算器４１２_kは、制御部４１７から供給される制御信号D419に基づいて、復号途中結果格納用メモリ４１３から１つずつ読み込まれる、前回の計算部４１２による第１の演算の結果得られた復号途中結果D413_k（u_dv）と、サイクリックシフト回路４１１から1つずつ読み込まれる復号途中結果D411_k（v）とを用いて、式（７）と式（８）にしたがう第１の演算を行う。

即ち、計算器４１２_kには、サイクリックシフト回路４１１から供給される６つの９ビットの復号途中結果D411₁乃至D411₆(v)のうちの、１つの復号途中結果D411_kが供給されるとともに、復号途中結果格納用メモリ４１３から供給される、前回の計算部４１２による演算の結果である６つの６ビットの復号途中結果D413₁乃至D413₆（u_j）のうちの、前回の計算部４１２による演算の結果である１つの復号途中結果D413_kが供給され、その９ビットの復号途中結果D411_k（v）と６ビットの復号途中結果D413_k（u_dv）が、減算器４３１に供給される。また、計算器４１２_kには、制御部４１７から制御信号D419が供給され、その制御信号D419がセレクタ４３５とセレクタ４４２に供給される。

減算器４３１は、９ビットの復号途中結果D411_k（v）から６ビットの復号途中結果D413_k（u_j）を減算し、その６ビットの減算値D431（v_i）を出力する。即ち、減算器４３１は、式（８）にしたがって演算を行い、その演算の結果である減算値D431を出力する。

減算器４３１により出力された６ビットの減算値D431のうち、最上位ビットの正負を示す符号ビットD432（sign（v_i））がEXOR回路４４０に供給され、下位５ビットの絶対値D433（|v_i|）がLUT４３２に供給される。

LUT４３２は、絶対値D433(|v_i|)に対して、式（７）におけるφ(|v_i|)の演算を行った５ビットの演算結果D434（φ(|v_i|)）を読み出し、加算器４３３とFIFOメモリ４３８に供給する。

加算器４３３は、演算結果D434（φ(|v_i|)）とレジスタ４３４に格納されている９ビットの値D435とを加算することにより、演算結果D434を積算し、その結果得られる９ビットの積算値をレジスタ４３４に再格納する。なお、検査行列H´の1行に亘る全ての１に対応する復号途中結果D411_kから求められた絶対値D433(|v_i|)に対する演算結果D434が積算された場合、レジスタ４３４はリセットされる。

検査行列H´の1行に亘る復号途中結果D411_kが１つずつ読み込まれ、レジスタ４３４に1行分の演算結果D434が積算された積算値が格納された場合、制御部４１７から供給される制御信号D419は、０から１に変化する。例えば、行の重み（row weight）が「９」である場合、制御信号D419は、１から８クロック目までは、「０」となり、９クロック目では「１」となる。

制御信号D419が「１」の場合、セレクタ４３５は、レジスタ４３４に格納されている値、即ち、検査行列H´の1行に亘る全ての１に対応する復号途中結果D411_k（v）から求められたφ(|v_i|)が積算された９ビットの値D435（ｉ＝１からｉ＝ｄ_cまでのΣφ(|v_i|)）を選択し、値D436として、レジスタ４３６に出力して格納させる。レジスタ４３６は、格納している値D436を、９ビットの値D437として、セレクタ４３５と加算器４３７に供給する。制御信号D419が「０」の場合、セレクタ４３５は、レジスタ４３６から供給された値D437を選択し、レジスタ４３６に出力して再格納させる。即ち、検査行列H´の1行に亘る全ての１に対応する復号途中結果D411_k（v）から求められたφ(|v_i|)が積算されるまで、レジスタ４３６は、前回積算されたφ(|v_i|)を、セレクタ４３５と加算器４３７に供給する。

一方、FIFOメモリ４３８は、レジスタ４３６から新たな値D437（ｉ＝１からｉ＝ｄ_cまでのΣφ(|v_i|)）が出力されるまでの間、LUT４３２が出力した演算結果D434（φ(|v_i|)）を遅延し、５ビットの値D438として減算器４３７に供給する。減算器４３７は、レジスタ４３６から供給された値D437から、FIFOメモリ４３８から供給された値D438を減算し、その減算結果を、５ビットの減算値D439としてLUT４３９に供給する。即ち、減算器４３７は、検査行列H´の1行に亘る全ての１に対応する復号途中結果D411_k（v）から求められたφ(|v_i|)の積算値から、求めたい枝に対応する復号途中結果、即ち、検査行列H´の所定の１に対応する復号途中結果D411_k（v）から求められたφ(|v_i|)を減算して、その減算値（ｉ＝１からｉ＝ｄ_c−１までのΣφ(|v_i|)）を減算値D439としてLUT４３９に供給する。

LUT４３９は、減算値D439（ｉ＝１からｉ＝ｄ_c−１までのΣφ(|v_i|)）に対して、式（７）におけるφ^-1（Σφ(|v_i|)）の演算を行った５ビットの演算結果D440（φ^-1(Σφ(|v_i|)))を出力する。

以上の処理と並行して、EXOR回路４４０は、レジスタ４４１に格納されている１ビットの値D442と符号ビットD432との排他的論理和を演算することにより、符号ビットどうしの乗算を行い、１ビットの乗算結果D441をレジスタ４４１に再格納する。なお、検査行列H´の1行に亘る全ての１に対応する復号途中結果D411_kから求められた符号ビットD432が乗算された場合、レジスタ４４１はリセットされる。

検査行列H´の1行に亘る全ての１に対応する復号途中結果D411から求められた符号ビットD432が乗算された乗算結果D441（ｉ＝１からｄ_cまでのΠsign(v_i)）がレジスタ４４１に格納された場合、制御部４１７から供給される制御信号D419は、「０」から「１」に変化する。

制御信号D419が「１」の場合、セレクタ４４２は、レジスタ４４１に格納されている値、即ち、検査行列H´の1行に亘る全ての１に対応する復号途中結果D411_kから求められた符号ビットD432が乗算された値D442（ｉ＝１からｉ＝ｄ_cまでのΠsign(v_i)）を選択し、１ビットの値D443としてレジスタ４４３に出力して格納させる。レジスタ４４３は、格納している値D443を、１ビットの値D444としてセレクタ４４２とEXOR回路４４５に供給する。制御信号D419が「０」の場合、セレクタ４４２は、レジスタ４４３から供給された値D444を選択し、レジスタ４４３に出力して再格納させる。即ち、検査行列H´の1行に亘る全ての１に対応する復号途中結果D411_k（v）から求められた符号ビットD432が乗算されるまで、レジスタ４４３は、前回格納した値を、セレクタ４４２とEXOR回路４４５に供給する。

一方、FIFOメモリ４４４は、レジスタ４４３から新たな値D444（ｉ＝１からｉ＝ｄ_cまでのΠsign(v_i)）がEXOR回路４４５に供給されるまでの間、符号ビットD432を遅延し、１ビットの値D445としてEXOR回路４４５に供給する。EXOR回路４４５は、レジスタ４４３から供給された値D444と、FIFOメモリ４４４から供給された値D445との排他的論理和を演算することにより、値D444を、値D445で除算し、１ビットの除算結果を除算値D446として出力する。即ち、EXOR回路４４５は、検査行列H´の1行に亘る全ての１に対応する復号途中結果D411_kから求められた符号ビットD432（sign(v_i)）の乗算値を、検査行列H´の所定の１に対応する復号途中結果D411_kから求められた符号ビットD432（sign(v_i)）で除算して、その除算値（ｉ＝１からｉ＝ｄ_c−１までのΠsign(v_i)）を除算値D446として出力する。

計算器４１２_kでは、LUT４３９から出力された５ビットの演算結果D440を下位５ビットとするとともに、EXOR回路４４５から出力された１ビットの除算値D446を最上位ビットとする合計６ビットが復号途中結果D412_k（u_j）として出力される。

以上のように、計算器４１２_kでは、式（７）と式（８）の演算が行われ、復号途中結果u_jが求められる。

なお、図１２の検査行列H´の行の重みの最大は９であるため、即ち、計算器４１２_kに供給される復号途中結果D411_k（v）と復号途中結果D413_k（u_dv）の最大数は９であるため、計算器４１２_kは、９個の復号途中結果D411_kから求められる９個の演算結果D434（φ(|v_i|)）を遅延させるFIFOメモリ４３８と、９個の符号ビットD432を遅延させるFIFOメモリ４４４を有している。行の重みが９未満の行のメッセージを計算するときには、FIFOメモリ４３８とFIFOメモリ４４４における遅延量が、その行の重みの値に減らされる。

図２３は、図１５の計算部４１５の計算器４１５_kの構成例を示すブロック図である。

なお、図２３では、計算部４１２による第１の演算の結果得られる各復号途中結果D412_k（D414_k）（u_j）が符号ビットを合わせて合計６ビットに量子化されているものとして、計算器４１５_kを表している。さらに、図２３の計算器４１５_kには、高速クロックＣＫ₂が供給され、この高速クロックＣＫ₂は、必要なブロックに供給されるようになっている。そして、各ブロックは、高速クロックＣＫ₂に同期して処理を行う。

図２３の計算器４１５_kは、制御部４１７から供給される制御信号D422に基づいて、受信用メモリ４１６から１つずつ読み込まれる受信データD811_k（u_0i）と、サイクリックシフト回路４１４から１つずつ読み込まれる復号途中結果D414_k（u_j）とを用いて、式（５）にしたがう第２の演算を行う。

即ち、計算器４１５_kでは、サイクリックシフト回路４１４から、検査行列H´の各行の１に対応する６ビットの復号途中結果D414_k（u_j）が１つずつ読み込まれ、その復号途中結果D414が、加算器４７１に供給される。また、計算器４１５_kでは、受信用メモリ４１６から６ビットの受信データD811_kが１つずつ読み込まれ、加算器４７５に供給される。さらに、計算器４１５_kには、制御部４１７から制御信号D422が供給され、その制御信号D422は、セレクタ４７３に供給される。

加算器４７１は、復号途中結果D414_k（u_j）とレジスタ４７２に格納されている９ビットの値D471とを加算することにより、復号途中結果D414_kを積算し、その結果得られる９ビットの積算値を、レジスタ４７２に再格納する。なお、検査行列H´の１列に亘る全ての１に対応する復号途中結果D414_kが積算された場合、レジスタ４７２はリセットされる。

検査行列H´の１列に亘る復号途中結果D414_kが１つずつ読み込まれ、レジスタ４７２に１列分の復号途中結果D414_kが積算された値が格納された場合、制御部４１７から供給される制御信号D422は、「０」から「１」に変化する。例えば、列の重みが「５」である場合、制御信号D422は、１から４クロック目までは「０」となり、５クロック目では「１」となる。

制御信号D422が「１」の場合、セレクタ４７３は、レジスタ４７２に格納されている値、即ち、検査行列H´の１列に亘る全ての枝からの復号途中結果D414_k（u_j）が積算された９ビットの値D471（ｊ＝１からｄ_VまでのΣu_j)を選択し、レジスタ４７４に出力して格納させる。レジスタ４７４は、格納している値D471を、９ビットの値D472として、セレクタ４７３と加算器４７５に供給する。制御信号D422が「０」の場合、セレクタ４７３は、レジスタ４７４から供給された値D472を選択し、レジスタ４７４に出力し再格納させる。即ち、検査行列H´の１列に亘る全ての枝からの復号途中結果D414_k（u_j）が積算されるまで、レジスタ４７４は、前回積算された値を、セレクタ４７３と加算器４７５に供給する。

加算器４７５は、９ビットの値D472と、受信用メモリ４１６から供給された６ビットの受信データD811_kとを加算して、その結果得られる６ビットの値を復号途中結果D415_k（v）として出力する。

以上のように、計算器４１５_kでは、式（５）の演算が行われ、復号途中結果vが求められる。

なお、図１２の検査行列H´の列の重みの最大は５であるため、即ち、計算器４１５_kに供給される復号途中結果u_jの最大数は５であるため、計算器４１５_kは、６ビットの復号途中結果u_jを最大５個加算する。従って、計算器４１５_kの出力は、９ビットの値となっている。

図２４は、図１５の出力部８１２の詳細構成例を示している。

図２４の出力部８１２は、復号結果メモリ９０１、ビット幅調整回路９０２、デインターリーバ９０３、セレクタ９０４、および制御部９０５から構成される。

なお、図２４では、復号結果メモリ９０１、ビット幅調整回路９０２、および制御部９０５は、高速クロックＣＫ₂（ＣＫ₂＞ＣＫ₃）で動作し、デインターリーバ９０３とセレクタ９０４は低速クロックＣＫ₃で動作する。なお、図１６の低速クロックＣＫ₁と図２４の低速クロックＣＫ₃は同一であっても異なっていてもよい。

出力部８１２には、計算部４１５（図２３）から、６つの復号途中結果D415が検査行列H´に対応する順に供給され、復号結果メモリ９０１に供給される。

復号結果メモリ９０１は、例えば、RAMにより構成され、６つの復号途中結果D415を同時に書き込んだり、２つの復号結果D901を同時に読み出すことが可能である。なお、復号結果メモリ９０１のビット数はP（=6）と復号途中結果D415の量子化ビット数を乗算した値であり、ワード数はn/P(=18)である。復号結果メモリ９０１は、高速クロックＣＫ₂に同期して、復号途中結果D415をビット方向に書き込む。

また、復号結果メモリ９０１は、高速クロックＣＫ₂に同期して、既に記憶してある復号途中結果D415を、制御部９０５から供給される制御信号D906に基づいて、ビット方向またはワード方向に読み出し、復号結果D901としてビット幅調整回路９０２に供給する。

具体的には、受信データD416の情報成分を用いて求められた復号途中結果D415が、復号結果メモリ９０１に供給される場合、制御信号D906は「０」となり、パリティ成分を用いて求められた復号途中結果D415が復号結果メモリ９０１に供給される場合、制御信号D906は「１」となる。

制御信号D906が「０」である場合、復号結果メモリ９０１は、復号途中結果D415をビット方向に読み出す。一方、制御信号D906が「１」である場合、復号結果メモリ９０１は、復号途中結果D415をワード方向に読み出す。即ち、情報成分を用いて求められた復号途中結果D415はビット方向に読み出され、パリティ成分を用いて求められた復号途中結果D415は、ワード方向に読み出される。

なお、高速クロックＣＫ₂の速度が低速クロックＣＫ₃の速度の２倍以上である場合、復号結果メモリ９０１は、例えば高速クロックＣＫ₂の１クロックに同期して、１つの復号結果D901をシリアルに出力し、高速クロックＣＫ₂の速度が低速クロックＣＫ₃の速度の２倍未満である場合、復号結果メモリ９０１は、高速クロックＣＫ₂の１クロックに同期して、２つの復号結果D901をパラレルに出力する。

ビット幅調整回路９０２は、高速クロックＣＫ₂に同期して、制御部９０５からの制御信号D905に基づいて、復号結果メモリ９０１からの復号結果D901のビット幅を調整する。具体的には、高速クロックＣＫ₂の速度が低速クロックＣＫ₃の速度の２倍未満であるとき、制御信号D905は「０」となり、高速クロックＣＫ₂の速度が低速クロックＣＫ₃の速度の２倍以上であるとき、制御信号D905は「１」となる。

制御信号D905が「０」である場合、ビット幅調整回路９０２は、例えば高速クロックＣＫ₂の1クロックに同期してパラレルに供給される２つの復号結果D901を、低速クロックＣＫ₃の1クロックに同期して、２つの復号結果D902として、パラレルにデインターリーバ９０３とセレクタ９０４に供給する。

一方、制御信号D905が「１」である場合、ビット幅調整回路９０２は、高速クロックＣＫ₂の１クロックに同期してシリアルに供給される１つの復号結果D901のビット幅を調整し、低速クロックＣＫ₃の１クロックに同期して、復号結果D901を２つずつ、復号結果D902としてパラレルにデインターリーバ９０３とセレクタ９０４に供給する。即ち、ビット幅調整回路９０２は、高速クロックＣＫ₂の２クロック間に供給される２つの復号結果D901を、パラレルにデインターリーバ９０３とセレクタ９０４に供給する。

デインターリーバ９０３は、低速クロックＣＫ₃に同期して、制御部９０５からの制御信号D906に基づいて、ビット幅調整回路９０２から供給される２つの復号結果D902の順序を制御する。

具体的には、制御信号D906が「０」である場合、デインターリーバ９０３は、２つの復号結果D902をそのまま復号結果D903としてセレクタ９０４に供給する。一方、制御信号D906が「１」である場合、デインターリーバ９０３は、２つの復号結果D902を検査行列Hに対応する順序に並び替え、並び替え後の２つの復号結果D903をセレクタ９０４に供給する。即ち、デインターリーバ９０３は、受信データD416のパリティ成分を用いて求められた２つの復号途中結果D415に対応する復号結果D902の順序を制御する。

セレクタ９０４には、低速クロックＣＫ₃に同期して、制御部９０５からの制御信号D905に基づいて、２つの復号結果D902またはデインターリーバ９０３からの２つの復号結果D903のいずれか一方を選択し、その選択した２つの復号結果D902またはD903を、復号結果D812として出力する。

具体的には、制御信号D905が「０」である場合、セレクタ９０４は、デインターリーバ９０３からの２つの復号結果D903を選択し、制御信号D905が「１」である場合、セレクタ９０４は、２つの復号結果D902を選択する。

制御部９０５は、低速クロックＣＫ₃に同期して、制御信号D905をセレクタ９０４に供給する。また、制御部９０５は、高速クロックＣＫ₂に同期して、制御信号D906を復号結果メモリ９０１に供給するとともに、低速クロックＣＫ₃に同期して、制御信号D906をデインターリーバ９０３に供給する。

次に、図２５を参照して、図２４の復号結果メモリ９０１について説明する。

なお、図２５では、説明の便宜上、復号結果メモリ９０１のビットを、復号途中結果D415の量子化ビットが１ビットであるとして説明する。

また、以下では、検査行列H´の情報部のｍ列目に対応する、受信データD416の情報成分を用いて求められた復号途中結果D415を、復号途中結果Ｂ_mとも表し、検査行列H´のパリティ部のｍ列目に対応する、受信データD416のパリティ成分を用いて求められた復号途中結果D415を、復号途中結果Ｃ_mとも表す。

図２５に示すように、復号結果メモリ９０１のビット数は、Ｐ(=6)と復号結果D415の量子化ビット数を乗算した値であり、ワード数は、n/p（=18）である。

まず最初に、復号結果メモリ９０１は、計算部４１５から供給される６つの復号結果Ｂ₀乃至Ｂ₅を、０番アドレスの０乃至５ビット目に、それぞれビット方向に記憶する。次に、復号結果メモリ９０１は、計算部４１５からの６つの復号結果Ｂ₆乃至Ｂ₁₁を、１番アドレスの０乃至５ビット目に、それぞれビット方向に記憶する。

以降同様にして、復号結果メモリ９０１の２乃至１１（=k₀-1）番アドレスの０乃至５ビット目に、復号結果Ｂ₁₂乃至Ｂ₇₁が記憶される。

次に、復号結果メモリ９０１は、計算部４１５から供給される６つの復号結果Ｃ₀乃至Ｃ₅を、１２番アドレスの０乃至５ビット目に、それぞれビット方向に記憶する。また、復号結果メモリ９０１は、計算部４１５からの６つの復号結果Ｃ₆乃至Ｃ₁₁を、１３番アドレスの０乃至５ビット目に、それぞれビット方向に記憶する。そして、同様の処理が繰り返され、復号結果メモリ９０１の１４番アドレス乃至１７番アドレスの０乃至５ビット目に、復号結果Ｃ₁₂乃至Ｃ₃₅が記憶される。

ここで、１２乃至１７番アドレスの、ビット方向での順番がP×y+x番目の復号結果Ｃ_mは、ワード方向での順番が（n₀-k₀）×x+y番目となる。

上述したように、図１２の検査行列H´のパリティ部のP×w+v列目の列は、図１１の検査行列Hのパリティ部の（n₀-k₀）×v＋w列目の列である。従って、復号結果メモリ９０１のビット方向に記憶される、検査行列H´のパリティ部の０列目から順に対応する復号結果Ｃ_mは、ワード方向の順番に見ると、検査行列Hのパリティ部の０列目から順に対応する復号結果Ｃ_mとなる。

即ち、復号装置８００では、検査行列H´を用いて第１と第２の演算を行うため、検査行列H´に対応する順に求められる復号途中結果D415の順番を、検査行列Hに対応する順番に入れ替えて復号結果D812として出力する必要がある。上述したように、検査行列Hと検査行列H´の列の順番は、情報部においては同一であるが、パリティ部においては異なる。従って、復号結果メモリ９０１は、復号結果Ｃ_mをビット方向に記憶し、ワード方向に読み出すことにより、検査行列Hに対応する復号結果Ｃ_mを出力することができる。

図２６は、図２４のデインターリーバ９０３の詳細構成例を示す図である。

図２６のデインターリーバ９０３は、５つのレジスタ９２１−１乃至９２１−５および５つのレジスタ９２２−１乃至９２２−５、並びにセレクタ９２３から供給される。

デインターリーバ９０３には、ビット幅調整回路９０２から復号結果D902が２つずつ供給され、そのうちの１つが復号結果D921としてレジスタ９２１−１乃至９２１−５に順に記憶される。また、他の１つが復号結果D922としてレジスタ９２２−１乃至９２２−５に順に記憶される。レジスタ９２１−１乃至９２１−５とレジスタ９２２−１乃至９２２−５は、記憶している復号結果D921またはD922をそれぞれセレクタ９２３に供給する。また、ビット幅調整回路９０２からの２つの復号結果D902は、それぞれ復号結果D921またはD922として、セレクタ９２３に直接供給される。

セレクタ９２３は、レジスタ９２１−１乃至９２１−５とレジスタ９２２−１乃至９２２−５のそれぞれから供給される５つの復号結果D921またはD922と、ビット幅調整回路９０２から直接供給される復号結果D921またはD922のうち、いずれか２つの復号結果D921またはD922を選択し、復号結果D923とD924として出力する。復号結果D923とD924は合わせられ、２つの復号結果D903としてセレクタ９０４に供給される。

以上のように、デインターリーバ９０３では、レジスタ９２１−１乃至９２１−５およびレジスタ９２２−１乃至９２２−５が、入力された復号結果D902（復号結果D921またはD922）を記憶し、セレクタ９２３が、そのレジスタ９２１−１乃至９２１−５およびレジスタ９２２−１乃至９２２−５に記憶されている復号結果D902を選択して、復号結果D903（復号結果D923とD924）として出力することにより、入力される復号結果D902と出力される復号結果D903の順序を入れ替える。

次に、図２７と図２８を参照して、図２４の復号結果メモリ９０１からの復号結果Ｃ_mの読み出しと、出力部８１２からの復号結果D812の出力とを説明する。図２７と図２８において、横軸は時間を表している。

なお、以下では、検査行列Hのパリティ部のｍ列に対応する復号結果D812を、復号結果Ｅ_mともいう。

図２７は、高速クロックＣＫ₂の速度が低速クロックＣＫ₃の速度の２倍以上である場合の、復号結果Ｃ_mの読み出しと復号結果Ｅ_mの出力とを説明するタイミングチャートである。

図２７に示すように、復号結果メモリ９０１は、既に記憶している復号結果Ｃ_mを、高速クロックＣＫ₂の１クロックに同期して、１２番アドレスの０ビット目から順に、１つずつワード方向に読み出す。例えば、復号結果メモリ９０１は、復号結果Ｃ₀,Ｃ₆，Ｃ₁₂，Ｃ₁₈、Ｃ₂₄，Ｃ₃₀，Ｃ₁，Ｃ₇・・・を順にシリアルに読み出す。

そして、ビット幅調整回路９０２は、復号結果メモリ９０１から連続して読み出された２つの復号結果Ｃ_mを、低速クロックＣＫ₃の１クロックに同期して、２つの復号結果D902として、パラレルにデインターリーバ９０３とセレクタ９０４に供給する。

図２７では、高速クロックＣＫ₂の速度が低速クロックＣＫ₃の速度の２倍以上である、即ち制御部９０５から供給される制御信号D905が１であるので、セレクタ９０４は、ビット幅調整回路９０２からの２つの復号結果D902を、復号結果Ｅ_mとして、そのまま出力する。

即ち、図２７に示すように、出力部８１２のセレクタ９０４は、復号結果Ｅ₀とＥ₆，Ｅ₁₂とＥ₁₈，Ｅ₂₄とＥ₃₀，Ｅ₁とＥ₇・・・を、順にパラレルに出力する。ここで、上述したように、図１２の検査行列H´のパリティ部のP×w+v列目の列は、図１１の検査行列Hのパリティ部では、（n₀-k₀）×v＋w列目の列となるので、出力部８１２により出力される復号結果Ｅ₀とＥ₆，Ｅ₁₂とＥ₁₈，Ｅ₂₄とＥ₃₀，Ｅ₁とＥ₇・・・は、検査行列Hのパリティ部の０列目乃至３５列目に対応する復号結果D812となる。即ち、出力部８１２は、検査行列Hの０列目から順に、検査行列Hの各列に対応する復号結果Ｅ_mを２つずつ出力する。

以上のように、復号装置８００は受信データＥ_mを２個ずつ同時に出力し、スループットを向上させることができる。

図２８は、高速クロックＣＫ₂の速度が低速クロックＣＫ₃の速度の２倍未満である場合の、復号結果メモリ９０１からの復号結果Ｃ_mの読み出しと、出力部８１２からの復号結果Ｅ_mの出力とを説明するタイミングチャートである。

図２８に示すように、復号結果メモリ９０１は、既に記憶している復号結果Ｃ_mを、高速クロックＣＫ₂の１クロックに同期して、１２番アドレスの０ビット目と１ビット目から順に、２つずつワード方向にシリアルに読み出す。例えば、復号結果メモリ９０１は、復号結果Ｃ₀とＣ₁，Ｃ₆とＣ₇、Ｃ₁₂とＣ₁₃，Ｃ₁₈とＣ₁₉・・・を順にパラレルに読み出す。

そして、復号結果メモリ９０１から出力される復号結果Ｃ_mは、ビット幅調整回路９０２を介して、デインターリーバ９０３とセレクタ９０４に供給される。

図２８では、高速クロックＣＫ₂の速度が低速クロックＣＫ₃の速度の２倍未満である、即ち制御信号D905が「０」であるので、セレクタ９０４は、デインターリーバ９０３から供給される復号結果D903を、復号結果D812として出力する。

即ち、復号結果メモリ９０１は、異なるアドレスの復号結果Ｃ_mを読み出すこと、即ちワード方向にパラレルに復号結果Ｃ_mを読み出すことはできないので、復号装置８００では、デインターリーバ９０３が、復号結果メモリ９０１からビット方向にパラレルに読み出された２つの復号結果Ｃ_mの順序を制御し、セレクタ９０４を介して、ワード方向に記憶される順にパラレルに２つの復号結果Ｃ_mに対応する復号結果D812を出力する。

具体的には、デインターリーバ９０３（図２６）には、復号結果Ｃ₀とＣ₁、復号結果Ｃ₆とＣ₇、復号結果Ｃ₁₂とＣ₁₃、復号結果Ｃ₁₈とＣ₁₉・・・がパラレルに復号結果D902として順に入力され、レジスタ９２１−１乃至９２１−５は、復号結果D902としてパラレルに入力された２つの復号結果Ｃ_mのうちの一方(例えば、復号結果Ｃ₀，Ｃ₆，Ｃ₁₂，Ｃ₁₈)を、復号結果D921として記憶し、レジスタ９２２−１乃至９２２−５は、他方(例えば、復号結果Ｃ₁，Ｃ₇，Ｃ₁₃，Ｃ₁₉)を復号結果D922として記憶する。そして、レジスタ９２１−１乃至９２１−５と９２２−１乃至９２２−５は、復号結果Ｃ_m（復号結果D921またはD922）をそれぞれセレクタ９２３に供給する。また、２つの復号結果D902は、それぞれ復号結果D921またはD922として、セレクタ９２３に直接供給される。

セレクタ９２３は、まず最初に、復号結果Ｃ₀とＣ₆を選択し、受信データD853とD854としてそれぞれ出力する。次に、セレクタ９２３は、復号結果Ｃ₁₂とＣ₁₈を選択し、受信データD853とD854としてそれぞれ出力する。その後、セレクタ９２３は、復号結果Ｃ₂₄とＣ₃₀、復号結果Ｃ₁とＣ₇・・・の順に選択して出力する。

即ち、デインターリーバ９０３にパラレルで入力される２つの復号結果Ｃ_mの一方を系列＃１´といい、他方を系列＃２´というと、セレクタ９２３は、６回のパラレル入力単位で交互に系列＃１´(例えば、復号結果Ｃ₀，Ｃ₆，Ｃ₁₂，Ｃ₁₈，Ｃ₂₄，Ｃ₃₀)と系列＃２´(例えば、復号結果Ｃ₁，Ｃ₇，Ｃ₁₃，Ｃ₁₉，Ｃ₂₅，Ｃ₃₁)から、入力された順に２つずつ選択し、出力する。即ち、セレクタ９２３は、復号結果メモリ９０１のワード方向に書き込まれる受信データＣ_mを、２つずつ選択してセレクタ９０４に供給する。

デインターリーバ９０３のセレクタ９２３により出力された２つの復号結果Ｃ_mは、セレクタ９０４を介して、２つの受信データＥ_mとしてパラレルに出力される。

具体的には、図２８に示すように、セレクタ９０４は、低速クロックＣＫ₃に同期して、復号結果Ｅ₀とＥ₆、Ｅ₁₂とＥ₁₈、Ｅ₂₄とＥ₃₀、Ｅ₁とＥ₇・・・を順にパラレルに出力する。

以上のように、デインターリーバ９０３は、復号結果メモリ９０１からビット方向に読み出された復号結果Ｃ_mを、ワード方向に記憶される順に、２つずつパラレルに出力するので、出力部８１２は、検査行列Hに対応する復号結果Ｅ_mを２つずつパラレルに出力することができる。これにより、高速クロックＣＫ₂が、低速クロックＣＫ₃の２倍未満である場合においても、低速クロックＣＫ₃の１クロックの間に、２つの復号結果Ｅ_mを出力することができる。その結果、復号装置８００では、高速クロックＣＫ₂の速度を低速クロックＣＫ₃の速度の２倍以上に上げずに、復号装置８００のスループットを向上させることができる。

次に、図２９を参照して、図１６の受信部８１１が受信データD811を出力する受信データ出力処理について説明する。この受信データ出力処理は、例えば、受信部８１１のインターリーバ８３１とセレクタ８３２に、２つの受信データD416が供給されたとき開始される。

ステップＳ３１において、インターリーバ８３１は、２つの受信データD416の順序を制御し、その結果得られる２つの受信データD831をセレクタ８３２に供給し、ステップＳ３２に進む。

ステップＳ３２において、セレクタ８３２は、制御部８３５からの制御信号D835に基づいて、２つの受信データD416またはステップＳ３１で供給される２つの受信データD831のいずれかを選択し、２つの受信データD832としてビット幅調整回路８３３に供給する。

ステップＳ３２の処理後は、ステップＳ３３に進み、ビット幅調整回路８３３は、制御部８３５からの制御信号D835に基づいて、ステップＳ３２で供給される２つの受信データD832のビット幅を調整し、その結果得られる受信データD833を受信メモリ８３４に供給する。

ステップＳ３３の処理後は、ステップＳ３４に進み、受信メモリ８３４は、制御部８３５からの制御信号D834に基づいて、ステップＳ３３で供給される受信データD833をビット方向またはワード方向に記憶し、処理を終了する。

なお、ステップＳ３４の処理により、LDPC符号に対応する受信データD833がすべて記憶された後、受信メモリ８３４は、既に記憶してある受信データD833をビット方向に６つ単位で読み出し、受信データD811として計算部４１５に供給する。

図３０は、図１５の復号装置８００の復号処理を説明するフローチャートである。この処理は、例えば、受信データD811が計算部４１５に供給されたとき、開始される。

ステップＳ５０において、サイクリックシフト回路４１４は、復号途中結果格納用メモリ４１３から供給された後述するステップＳ５６で格納される６つの復号途中結果D413（u_j）を、サイクリックシフトし、計算部４１５に供給する。

具体的には、サイクリックシフト回路４１４には、復号途中結果格納用メモリ４１３から６つの復号途中結果D413₁乃至D413₆が供給されるとともに、制御部４１７から、その復号途中結果D413に対応する検査行列H´の１が検査行列H´において元となる単位行列などを幾つサイクリックシフトしたものであるかの情報（Matrixデータ）を表す制御信号D421が供給される。サイクリックシフト回路４１４は、制御信号D421を元に、６つの復号途中結果D413₁乃至D413₆をサイクリックシフトし（並べ替え）、その結果を復号途中結果D414₁乃至D414₆として、計算部４１５に供給する。

なお、受信部８１１から供給された受信データD811に対して、まだ第１の演算が行われておらず、復号途中結果格納用メモリ４１３に復号途中結果D412が格納されていない場合、計算部４１５は、復号途中結果u_jを初期値（例えば、受信データD811）に設定する。

ステップＳ５０の処理後は、ステップＳ５１に進み、計算部４１５は、第２の演算を行い、その演算の結果である復号途中結果D415₁乃至D415₆を復号途中結果格納用メモリ４１０に供給する。

具体的には、計算部４１５には、ステップＳ５０でサイクリックシフト回路４１４から６つの復号途中結果D414₁乃至D414₆が供給されるとともに、受信部８１１から６つの受信データD811₁乃至D811₆が供給され、復号途中結果D415₁乃至D415₆と受信データD811₁乃至D811₆が、計算部４１５の計算器４１５₁乃至４１５₆それぞれに１つずつ供給される。さらに、計算部４１５には、制御部４１７から制御信号D422が供給され、その制御信号D422が計算器４１５₁乃至４１５₆に供給される。

各計算器４１５_kは、復号途中結果D414_kと受信データD811_kを用いて、制御信号D422に基づいて、式（５）にしたがう第２の演算を行い、その演算の結果得られる検査行列H´の列に対応する復号途中結果D415_k(v)を復号途中結果格納用メモリ４１０に供給する。

ステップＳ５１の処理後は、ステップＳ５２に進み、復号途中結果格納用メモリ４１０は、ステップＳ５１で計算部４１５から供給された６つの復号途中結果D415₁乃至D415₆を、同一アドレスに格納し、ステップＳ５３に進む。

ステップＳ５３において、制御部４１７は、計算部４１５により、検査行列H´の列に対応する全ての復号途中結果D415が演算されたかどうかを判定し、全ての復号途中結果D415が演算されていないと判定した場合、ステップＳ５０に戻り、上述した処理を繰り返す。

一方、ステップＳ５３において、制御部４１７は、計算部４１５により、検査行列H´の列に対応する全ての復号途中結果D415が演算されたと判定した場合、ステップＳ５４に進み、サイクリックシフト回路４１１は、復号途中結果格納用メモリ４１０から供給される復号途中結果D410(v)をサイクリックシフトする。

具体的には、サイクリックシフト回路４１１には、復号途中結果格納用メモリ４１０から６つの復号途中結果D410が供給されるとともに、制御部４１７から、その復号途中結果D410に対応する検査行列H´の１が検査行列H´において元となる単位行列などを幾つサイクリックシフトしたものであるかの情報（Matrixデータ）を表す制御信号D418が供給される。サイクリックシフト回路４１１は、制御信号D418を元に、６つの復号途中結果D410をサイクリックシフトし（並べ替え）、その結果を復号途中結果D411₁乃至D411₆として、計算部４１２に供給する。

ステップＳ５４の処理後は、ステップＳ５５に進み、計算部４１２は、上述した図２２で説明したように、６個の第１の演算を同時に行い、その演算結果である復号途中結果D412₁乃至D412₆を復号途中結果格納用メモリ４１３に供給する。

ステップＳ５５の処理後は、ステップＳ５６に進み、復号途中結果格納用メモリ４１３は、ステップＳ５５で計算部４１２から供給された６つの復号途中結果D412₁乃至D412₆を、同一のアドレスに格納し、ステップＳ５７に進む。

ステップＳ５７において、制御部４１７は、計算部４１２により、検査行列H´の全ての１に対応する復号途中結果D412が演算されたかどうかを判定し、全ての復号途中結果D412が演算されていないと判定した場合、ステップＳ５４に戻り、上述した処理を繰り返す。

一方、ステップＳ５７において、制御部４１７は、計算部４１２により、全ての１に対応する復号途中結果D412が演算されたと判定した場合、処理を終了する。

なお、復号装置８００は、所定の復号回数だけ図３０の復号処理を繰り返し行う。そして、計算部４１５は、最後の第２の演算の結果得られる復号途中結果D415を、出力部８１２に供給する。

なお、復号装置４００は、所定の復号回数だけ、図３０の復号処理を繰り返し行うのではなく、復号途中結果D415の硬判定値のシンドローム演算を行い、その結果得られるシンドロームが０になるか、または復号回数が所定の回数になるまで、復号処理を繰り返すようにしてもよい。

次に、図３１を参照して、図２４の出力部８１２が復号結果D812を出力する復号結果出力処理について説明する。この復号結果出力処理は、例えば、計算部４１５から、出力部８１２の復号結果メモリ９０１に復号途中結果D415が供給されたとき、開始される。

ステップＳ７１において、復号結果メモリ９０１は、計算部４１５からの復号途中結果D415を記憶する。そして、復号結果メモリ９０１は、制御部９０５からの制御信号D906に基づいて、既に記憶している復号途中結果D415を読み出し、復号結果D901として、ビット幅調整回路９０２に供給する。

ステップＳ７１の処理後は、ステップＳ７２に進み、ビット幅調整回路９０２は、制御部９０５からの制御信号D905に基づいて、ステップＳ７１で供給される復号結果D901のビット幅を調整し、その結果得られる復号途中結果D902をデインターリーバ９０３とセレクタ９０４に供給する。

ステップＳ７２の処理後は、ステップＳ７３に進み、デインターリーバ９０３は、制御部９０５からの制御信号D906に基づいて、ステップＳ７２で供給される復号結果D902の順序を制御し、その結果得られる復号結果D903をセレクタ９０４に供給する。

ステップＳ７３の処理後は、ステップＳ７４に進み、セレクタ９０４は、制御部９０５からの制御信号D905に基づいて、ステップＳ７２で供給される復号結果D902またはステップＳ７３で供給される復号結果D903のいずれかを選択し、復号結果D812として出力して、処理を終了する。

以上のように、図１５の復号装置８００は、２つずつ入力される受信データD416を、繰り返し復号し、その結果得られる復号結果D812を２つずつ出力する。

なお、復号装置８００に対する入力と出力の両方が２つずつ行われるのではなく、いずれか一方のみが２つずつ行われるようにしてもよい。

上述の場合には、説明を簡単にするために、Pが６の場合、即ち、検査行列Hを構成する構成行列の行数および列数が６の場合を例に挙げたが、構成行列の行数および列数Pは必ずしも６である必要はなく、検査行列Hによって異なる値を取ることもあり得る。例えば、Pは３６０や３９２であってもよい。

また、図１５の復号装置８００では、受信部８１１に同時に入力される受信データD416と出力部８１２から同時に出力される復号結果D812は２つであるが、同時に入力される受信データD416と同時に出力される復号結果D812の数Ｎ_pは、これに限定されず、P個以下の数（例えば、Pの約数など）とすることができる。この場合、高速クロックＣＫ₂の速度が、低速クロックＣＫ₁またはＣＫ₃の速度のＮ_p倍以上であるかどうかに基づいて、制御信号D835とD905が決定される。

さらに、図１５の復号装置８００では、符号長108、符号化率2/3のLDPC符号を用いたが、LDPC符号の符号長や符号化率は、どのような値であってもよい。例えば、構成行列の行数および列数Pが６の場合、枝総数が６以下であれば、どのような符号長、符号化率のLDPC符号でも、制御信号を代えるだけで、復号装置８００を用いて復号可能である。

また、受信メモリ８３４と復号結果メモリ９０１のビット数とワード数は、上述した数に限定されない。

さらに、本発明は、第１の演算と第２の演算を交互に行う復号装置８００ではなく、チェックノード演算とバリアブルノード演算を交互に行う復号装置にも適用することができる。この場合、チェックノード演算を行うチェックノード演算器は、図２２の計算器４１２_kの減算器４３１を削除することにより構成され、バリアブルノード演算を行うバリアブルノード演算器は、図２３の計算器４１５_kの最後に減算器４３１を加えることにより構成される。

以上のように、図１５の復号装置８００では、受信メモリ８３４が受信データD833を２個ずつ同時に記憶し、復号結果メモリ９０１が、復号結果D901を２個ずつ同時に読み出すので、復号装置のスループットを向上させることができる。

また、本発明に係る復号装置８００は、サムプロダクトアルゴリズムを忠実に実装するものであるため、メッセージの量子化以外の復号損失が起きることはない。

なお、上述したLDPC符号を復号する復号装置は、例えば、（ディジタル）衛星放送を受信するチューナなどに適用することができる。

また、本明細書において、処理を記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。

さらに、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。

LDPC符号の検査行列Hを説明する図である。 パリティ部が下三角行列になっている検査行列Hを示す図である。 LDPC符号の復号手順を説明するフローチャートである。 メッセージの流れを説明する図である。 LDPC符号の検査行列Hの例を示す図である。 検査行列Hのタナーグラフを示す図である。 バリアブルノードを示す図である。 チェックノードを示す図である。 LDPC符号の検査行列Hの例を示す図である。 ノード演算を６個同時に行う復号装置の構成例を示すブロック図である。 LDPC符号に用いる検査行列Hの例を示す図である。 図１１の検査行列Hを行置換または列置換した後の検査行列H´を示す図である。 図１１の検査行列Hを行置換または列置換した後の検査行列H´を示す図である。 図１１の行列Hと図１２の検査行列H´のパリティ部を示す図である。 本発明の一実施の形態の、LDPC符号を復号する復号装置の構成例を示す図である。 図１５の受信部の詳細構成例を示すブロック図である。 図１６のインターリーバの詳細構成例を示すブロック図である。 RAMのビット方向とワード方向について説明する図である。 図１６の受信メモリに記憶される受信データについて説明する図である。 図１６の受信部への入力と、受信メモリへの書き込みとを説明するタイミングチャートである。 図１６の受信部への入力と、受信メモリへの書き込みとを説明するタイミングチャートである。 図１５の計算器の構成例を示すブロック図である。 図１５の計算器の構成例を示すブロック図である。 図１５の出力部の詳細構成例を示すブロック図である。 図２４の復号結果メモリについて説明する図である。 図２４のデインターリーバの詳細構成例を示すブロック図である。 図２４の復号結果メモリからの読み出しと、出力部からの出力とを説明するタイミングチャートである。 図２４の復号結果メモリからの読み出しと、出力部からの出力とを説明するタイミングチャートである。 受信データ出力処理について説明するフローチャートである。 復号処理を説明するフローチャートである。 復号結果出力処理について説明するフローチャートである。

符号の説明

４１０ 復号途中結果格納用メモリ, ４１１ サイクリックシフト回路, ４１２ 計算部， ４１３ 復号途中結果格納用メモリ, ４１４ サイクリックシフト回路， ４１５ 計算部， ４１７ 制御部, ８００ 復号装置, ８１１ 受信部， ８１２ 出力部, ８３１ インターリーバ， ８３２ セレクタ， ８３３ ビット幅調整回路， ８３４ 受信メモリ， ８３５ 制御部， ９０１ 復号結果メモリ， ９０２ ビット幅調整回路， ９０３ デインターリーバ， ９０４ セレクタ， ９０５ 制御部

Claims (10)

1. LDPC(Low Density Parity Check)符号を復号する復号装置であって、
   P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、前記LDPC符号の検査行列が、複数の前記構成行列の組み合わせで表される場合、または前記LDPC符号の検査行列が、行または列の置換により、複数の前記構成行列の組み合わせで表される場合において、
   前記LDPC符号を記憶する符号記憶手段と、
   前記符号記憶手段に記憶される前記LDPC符号を復号する復号手段と、
   前記復号手段により復号された結果得られる復号結果を記憶し、既に記憶してある復号結果を読み出す復号結果記憶手段と
   を備え、
   前記符号記憶手段は、前記LDPC符号を前記P個以下の複数個ずつ同時に記憶するか、前記復号結果記憶手段は、前記復号結果を前記P個以下の複数個ずつ同時に読み出すか、または前記符号記憶手段は前記LDPC符号を前記P個以下の複数個ずつ同時に記憶し、かつ前記復号結果記憶手段は、前記復号結果を前記P個以下の複数個ずつ同時に読み出す
   復号装置。
2. 前記符号記憶手段は、前記LDPC符号を前記Pの約数個ずつ同時に記憶するか、前記復号結果記憶手段は、前記復号結果を前記Pの約数個ずつ同時に読み出すか、または前記符号記憶手段は前記LDPC符号を前記Pの約数個ずつ同時に記憶し、かつ前記復号結果記憶手段は、前記復号結果を前記Pの約数個ずつ同時に読み出す
   請求項１に記載の復号装置。
3. 前記符号記憶手段は、前記Pの約数個の前記LDPC符号を同時に読み書き可能なメモリから構成され、
   前記復号結果記憶手段は、前記Pの約数個の前記復号結果を同時に読み書き可能なメモリから構成される
   請求項２に記載の復号装置。
4. 前記復号装置は、前記符号記憶手段に前記LDPC符号を入力する第１の外部装置、および前記復号結果記憶手段から読み出された復号結果を出力する第２の外部装置の動作クロックに比べて、高速の動作クロックで動作を行う
   請求項３に記載の復号装置。
5. 前記符号記憶手段は、前記行または列の置換後の前記検査行列の前記P個の列に対応する前記LDPC符号を、同時に読出可能な順に記憶する
   請求項４に記載の復号装置。
6. 前記符号記憶手段は、RAM（Random Access Memory）であり、そのRAMの各アドレスに、前記行または列の置換後の前記検査行列の前記P個の列に対応する前記LDPC符号を記憶する
   請求項５に記載の復号装置。
7. 前記符号記憶手段に記憶される前の前記LDPC符号、または前記復号結果記憶手段から読み出された後の前記復号結果の少なくとも一方の順序を制御する順序制御手段
   をさらに備える
   請求項４に記載の復号装置。
8. 前記順序制御手段は、
   前記LDPC符号を記憶する順序符号記憶手段と、
   前記順序符号記憶手段に記憶される前記LDPC符号を選択して出力する選択手段と
   を備える
   請求項７に記載の復号装置。
9. 前記順序制御手段は、
   前記復号結果を記憶する順序復号結果記憶手段と、
   前記順序復号結果記憶手段に記憶される前記復号結果を選択して出力する選択手段と
   を備える
   請求項７に記載の復号装置。
10. LDPC(Low Density Parity Check)符号を復号する復号装置の復号方法であって、
    P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、前記LDPC符号の検査行列が、複数の前記構成行列の組み合わせで表される場合、または前記LDPC符号の検査行列が、行または列の置換により、複数の前記構成行列の組み合わせで表される場合において、
    前記LDPC符号を記憶させる符号記憶ステップと、
    前記符号記憶ステップの処理により記憶される前記LDPC符号を復号する復号ステップと、
    前記復号ステップの処理により復号された結果得られる復号結果を記憶させ、既に記憶されている復号結果を読み出す復号結果記憶ステップと
    を含み、
    前記符号記憶ステップの処理は、前記LDPC符号を前記P個以下の複数個ずつ同時に記憶させるか、または前記復号結果記憶ステップの処理は、前記復号結果を前記P個以下の複数個ずつ同時に読み出すか、もしくは前記符号記憶ステップの処理は前記LDPC符号を前記P個以下の複数個ずつ同時に記憶させ、かつ前記復号結果記憶ステップの処理は、前記復号結果を前記P個以下の複数個ずつ同時に読み出す
    復号方法。

Images