(57)【要約】【課題】  復号装置のスループットを向上させる。【解決手段】  受信部８１１は、受信データD416を２個ずつ同時に記憶し、既に記憶している受信データD811を６個ずつ計算部４１５に供給する。計算部４１５は、受信データD811と第１の演算の結果得られる復号途中結果D414とを用いて第２の演算を行い、計算部４１２は、第２の演算の結果得られる復号途中結果D411と前回の第１の演算の結果得られる復号途中結果D413とを用いて第１の演算を行う。最後の第２の演算の結果得られる復号途中結果D415は、出力部８１２に供給され、出力部８１２は、その復号途中結果D415を記憶する。出力部８１２は、既に記憶している復号途中結果D415を２つずつ復号結果として同時に読み出し、出力する。本発明は、例えば、衛星放送を受信するチューナに適用できる。【選択図】      図１５
2007036776.tif 000002
【特許請求の範囲】
【請求項１】
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符号）による符号化が施された符号の復号を行う復号装置および復号方法に関する。
【背景技術】
【０００２】
近年、例えば、移動体通信や深宇宙通信といった通信分野、及び地上波又は衛星ディジタル放送といった放送分野の研究が著しく進められているが、それに伴い、誤り訂正符号化及び復号の効率化を目的として符号理論に関する研究も盛んに行われている。
【０００３】
符号性能の理論的限界としては、いわゆるシャノン(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の転置行列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が求められる。
【００２０】
【数１】
2007036776.tif 000003
・・・（１）
【００２１】
【数２】
2007036776.tif 000004
・・・（２）
【００２２】
ここで、式（１）と式（２）におけるdvとdcは、それぞれ、検査行列Hの縦方向（行方向）と横方向（列方向）の"1"の個数を示す任意に選択可能とされるパラメータであり、例えば、(3,6)符号の場合には、dv=3，dc=6となる。
【００２３】
なお、式（１）または（２）の演算においては、それぞれ、メッセージを出力しようとする枝(edge)から入力されたメッセージを、和または積演算のパラメータとしては用いないことから、和または積演算の範囲が、１乃至dv-1または１乃至dc-1となっている。また、式（２）に示す演算は、実際には、２入力v1，v2に対する１出力で定義される式（３）に示す関数R(v1,v2)のテーブルを予め作成しておき、これを式（４）に示すように連続的（再帰的）に用いることによって行われる。
【００２４】
【数３】
2007036776.tif 000005
・・・（３）
【００２５】
【数４】
2007036776.tif 000006
・・・（４）
【００２６】
ステップＳ１２では、さらに、変数kが"1"だけインクリメントされ、ステップＳ１３に進む。ステップＳ１３では、変数kが所定の繰り返し復号回数N以上であるか否かが判定される。ステップＳ１３において、変数kがN以上ではないと判定された場合、ステップＳ１２に戻り、以下、同様の処理が繰り返される。
【００２７】
また、ステップＳ１３において、変数kがN以上であると判定された場合、ステップＳ１４に進み、式（５）に示す演算を行うことによって最終的に出力する復号結果としてのメッセージvが求められて出力され、LDPC符号の復号処理が終了する。
【００２８】
【数５】
2007036776.tif 000007
・・・（５）
【００２９】
ここで、式（５）の演算は、式（１）の演算とは異なり、バリアブルノードに接続している全ての枝からの入力メッセージを用いて行われる。
【００３０】
このような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である。
【００３６】
【数６】
2007036776.tif 000008
・・・（６）
【００３７】
更に、x≧0において、φ(x)=ln(tanh(x/2))と定義すると、φ-1(x)=2tanh-1(e-x)であるから、式（６）は、式（７）のように書くことができる。
【００３８】
【数７】
2007036776.tif 000009
・・・（７）
【００３９】
チェックノードでは、図８のように、式（７）の演算を行う。すなわち、図８において、計算しようとしている枝に対応するメッセージ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となる。
【００４１】
サムプロダクトアルゴリズムをハードウェアに実装する場合、式（１）で表されるバリアブルノード演算および式（７）で表されるチェックノード演算を、適度な回路規模と動作周波数で繰り返し行うことが必要である。
【００４２】
復号装置の実装の例としては、各ノードの演算を１つずつ順次行うことによって、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符号を復号する復号装置４００の構成の一例を示すブロック図である。
【００４９】
復号装置４００は、復号途中結果格納用メモリ４１０、サイクリックシフト回路４１１、６つの計算器４１２1乃至計算器４１２6からなる計算部４１２、復号途中結果格納用メモリ４１３、サイクリックシフト回路４１４、６つの計算器４１５1乃至計算器４１５6からなる計算部４１５、受信用メモリ４１６、および制御部４１７から構成される。
【００５０】
ここで、計算器４１２k（k=1,2,・・・，6）で行われる演算と、計算器４１５kで行われる演算について、式を用いて説明する。
【００５１】
計算部４１２は、上述した式（７）と、以下に表す式（８）とにしたがう第１の演算を行い、その第１の演算の結果である復号途中結果ujを復号途中結果格納用メモリ４１３に供給して格納させる。計算部４１５は、上述した式（５）にしたがう第２の演算を行い、その第２の演算の結果である復号途中結果vを復号途中結果格納用メモリ４１０に供給して格納させる。
【００５２】
【数８】
2007036776.tif 000010
・・・（８）
【００５３】
なお、式（８）の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が、最終的な復号結果として１つずつ出力される。
【００８１】
また、サムプロダクトアルゴリズムを近似して実装する方法なども提案されているが、この方法では、性能の劣化を招いてしまう。
【００８２】
【特許文献１】特開２００４−３６４２３３号公報
【非特許文献１】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符号を入力する第１の外部装置（例えば、図１６のインターリーバ８３１とセレクタ８３２）、および前記復号結果記憶手段から読み出された復号結果を出力する第２の外部装置(例えば、図２４のデインターリーバ９０３とセレクタ９０４)の動作クロック(例えば、低速クロックＣＫ1またはＣＫ3)に比べて、高速の動作クロック（例えば、高速クロックＣＫ2）で動作を行う。
【０１００】
前記符号記憶手段に記憶される前の前記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´を構成する横方向の構成行列の数をｎ0個とし、検査行列H´の情報部を構成する横方向の構成行列の数をｋ0個とすると、ｎ0（=n/P=108/6）は18となり、ｋ0（=k/P=72/6）は12となる。
【０１１１】
即ち、図１２や図１３の検査行列H´では、縦方向に６（=ｎ0-ｋ0=18-12）個の構成行列が、横方向にｎ0(=18)個の構成行列が並んでいる。
【０１１２】
また、図１１の検査行列Hのパリティ部の一番左の列（先頭列）を０列目とすると、検査行列Hのパリティ部の（n0-k0）×v＋w（0≦v≦P-1,0≦ｗ≦n0-k0-1）列目の列は、図１２や図１３の検査行列H´のパリティ部では、P×w+v列目の列となっている。
【０１１３】
以上のように、図１２や図１３の検査行列H´は構成行列で構成されるため、検査行列H´を用いてLDPC符号の復号が行われる場合、LDPC符号の復号に必要な、第１の演算の結果得られる復号途中結果ujの第２の演算に用いられる順序での読出、および第２の演算の結果得られる復号途中結果vの第１の演算に用いられる順序での読出を、６個単位で復号途中結果ujとvをサイクリックシフトすることにより行うことができる。また、６個単位で復号途中結果ujをサイクリックシフトすることにより、第２の演算における復号途中結果ujと検査行列H´の行との積を、６個同時に計算することができる。
【０１１４】
図１４Ａ乃至図１４Ｂは、図１１の検査行列Hと図１２や図１３の検査行列H´のパリティ部を示している。
【０１１５】
図１４Ａに示すように、図１１の検査行列Hのパリティ部は、行列の対角線の右上が全て“０”とされた行列となっており、下三角状の構造を有している。また、パリティ部は、下三角行列の対角成分とその成分の直下の成分が１であり、それ以外の成分が０となっている。
【０１１６】
図１４Ｂに示すように、図１２や図１３の検査行列H´のパリティ部では、対角成分が６×６の単位行列の対角成分となるように、６×６の単位行列が対角方向に配置され、その単位行列の直下にも６×６の単位行列が配置されている。さらに、パリティ部では、右上に、６×６の単位行列の最上行の１が０になった行列を左に１だけサイクリックシフトした行列が配置されている。以上の他は、６×６の０行列が配置されている。図１４Ｂのパリティ部では、図１４Ａのパリティ部の（n0-k0）×v＋w列目の行が、P×w＋v列目の列となる。
【０１１７】
図１５は、本発明の一実施の形態の、LDPC符号を復号する復号装置８００の構成例を示している。なお、図中、図１０の復号装置４００と対応する部分については、同一の符号を付してあり、以下では、その説明は、適宜省略する。
【０１１８】
図１５の復号装置８００は、復号途中結果格納用メモリ４１０、サイクリックシフト回路４１１、６つの計算器４１２1乃至計算器４１２6からなる計算部４１２、復号途中結果格納用メモリ４１３、サイクリックシフト回路４１４、６つの計算器４１５1乃至計算器４１５6からなる計算部４１５、および制御部４１７が設けられている点で、図１０の復号装置４００と共通するが、受信用メモリ４１６に代えて受信部８１１が設けられ、新たに出力部８１２が設けられている点で、図１０の復号装置４００と相違している。
【０１１９】
ここで、図１５の復号装置８００では、例えば、図１１に示した検査行列Hで表されるLDPC符号（符号化率2/3、符号長108）の復号が行われることとする。
【０１２０】
図１５の復号装置８００では、受信データD416が検査行列H´に対応する順に並び替えられ、その並び替え後の受信データD811を用いて、計算部４１５が検査行列H´に対応する第２の演算を６個ずつ行い、計算部４１２が検査行列H´に対応する第１の演算を６個ずつ行い、これらの第１の演算と第２の演算とが交互に行われる。そして、最後の第２の演算の結果得られる復号途中結果D415を、検査行列Hに対応する順に並び替えることによって、LDPC符号が復号される。
【０１２１】
即ち、受信部８１１には、検査行列Hで表されるLDPC符号の受信値U0が受信され、受信データD416（u0i）が供給されて、記憶される。そして、受信部８１１は、既に記憶している受信データD416から、検査行列H´に対応する第２の演算に必要となる順に６つの受信データD416を読み出し、受信データD8111乃至D8116（D811）として計算部４１５に供給する。換言すれば、受信部８１１は、検査行列Hに対応する順に供給される受信データD416を、検査行列H´に対応する順に並び替えて受信データD811として計算部４１５に供給する。
【０１２２】
そして、計算部４１５は、LDPC符号の復号のための検査行列H´に対応する第２の演算を行う。
【０１２３】
即ち、復号途中結果格納用メモリ４１３には、後述する計算部４１２による第１の演算の結果としての復号途中結果D4121乃至D4126（D412）（uj）が格納されており、復号途中結果格納用メモリ４１３は、既に格納してある復号途中結果D412のうち、６つの復号途中結果D412を、復号途中結果D4131乃至D4136（D413）として、サイクリックシフト回路４１４と計算部４１２に供給する。
【０１２４】
サイクリックシフト回路４１４は、制御部４１７からの制御信号D421に基づき、復号途中結果D413をサイクリックシフトし、その結果を復号途中結果D4141乃至D4146（D414）として計算部４１５に供給する。さらに、計算部４１５には、制御部４１７から制御信号D422が供給されるとともに、受信部８１１から６つの受信データD811が供給される。
【０１２５】
計算器４１５は、計算器４１５1乃至４１５6から構成される。各計算器４１５kは、制御信号D422に基づき、サイクリックシフト回路４１４から供給される復号途中結果D414k（uj）と、受信部８１１から供給される受信データD811k（u0i）とを用い、式（５）にしたがって第２の演算を行う。そして、各計算器４１５kは、第２の演算の結果得られる復号途中結果D415k（v）を、復号途中結果格納用メモリ４１０に供給する。
【０１２６】
復号途中結果格納用メモリ４１０は、計算部４１５から供給される、６つの第２の演算の結果である復号途中結果D4151乃至D4156（D415）（v）を格納していく。そして、復号途中結果格納用メモリ４１０は、既に格納してある復号途中結果D415から、６つの復号途中結果D415を、復号途中結果D410として読み出し、サイクリックシフト回路４１１に供給する。サイクリックシフト回路４１１は、制御部４１７から供給される制御信号D418に基づき、６つの復号途中結果D410をサイクリックシフトし、その結果を復号途中結果D4111乃至D4116（D411）として計算部４１２に供給する。
【０１２７】
計算部４１２は、LDPC符号の復号のための検査行列H´に対応する第１の演算を行う。
【０１２８】
即ち、計算部４１２は、計算器４１２1乃至４１２6から構成される。各計算器４１２kは、制御部４１７から供給される制御信号D419に基づき、サイクリックシフト回路４１１から供給される復号途中結果D411kと、復号途中結果格納用メモリ４１３から供給される、前回の計算部４１２による第１の演算の結果得られた復号途中結果D413kとを用いて、式（７）と式（８）にしたがって第１の演算を行い、その第１の演算によって求められた６つの復号途中結果D412k（uj）を、復号途中結果格納用メモリ４１３に供給する。
【０１２９】
復号途中結果格納用メモリ４１３は、計算部４１２から供給される復号途中結果D4121乃至D4126を格納していく。そして、復号途中結果格納用メモリ４１３に記憶された復号途中結果D412は、上述したように復号途中結果D4131乃至D4136として読み出され、サイクリックシフト回路４１４と計算部４１２に供給される。
【０１３０】
以上のように、第１の演算と第２の演算とが交互に所定の回数だけ繰り返し行われた後、計算部４１５による第２の演算の結果得られる復号途中結果D415が、出力部８１２に供給される。
【０１３１】
出力部８１２は、計算部４１５から供給される、検査行列H´に対応する第２の演算の結果得られる復号途中結果D415を記憶する。そして、出力部８１２は、既に記憶してある復号途中結果D415を検査行列Hに対応する順に読み出し、復号結果として出力する。即ち、出力部８１２は、検査行列H´に対応する順に供給される復号途中結果D415を、検査行列Hに対応する順に並び替え、復号結果として出力する。これにより、検査行列Hで表されるLDPC符号の繰り返し復号の結果を出力することができる。
【０１３２】
図１６は、図１５の受信部８１１の詳細構成例を示すブロック図である。
【０１３３】
図１６の受信部８１１は、インターリーバ８３１、セレクタ８３２、ビット幅調整回路８３３、受信メモリ８３４、および制御部８３５から構成される。
【０１３４】
なお、図１６では、インターリーバ８３１とセレクタ８３２は、低速クロックＣＫ1で動作し、ビット幅調整回路８３３、受信メモリ８３４、および制御部８３５は、高速クロックＣＫ2（ＣＫ2＞ＣＫ1）で動作する。
【０１３５】
また、受信部８１１には、受信値U0から生成された受信データD416が２つずつ供給されるものとする。即ち、受信部８１１には、受信データD416が検査行列Hに対応する順序で２つずつ供給され、その受信データD416は、インターリーバ８３１とセレクタ８３２に供給される。
【０１３６】
インターリーバ８３１は、低速クロックＣＫ1に同期して、制御部８３５からの制御信号D834に基づいて、２つの受信データD416の順序を制御する。具体的には、受信データD416の、受信値U0の情報メッセージｕに対応する成分、即ち検査行列Hの情報部に対応する成分（以下、情報成分という）が、インターリーバ８３１に供給される場合、制御信号D834は「０」となり、パリティビットに対応する成分、即ち検査行列Hのパリティ部に対応する成分（以下、パリティ成分という）がインターリーバ８３１に供給される場合、制御信号D834は「１」となる。
【０１３７】
制御信号D834が「０」である場合、インターリーバ８３１は、２つの受信データD416をそのまま受信データD831としてセレクタ８３２に供給する。一方、制御信号D834が「１」である場合、インターリーバ８３１は、２つの受信データD416を検査行列H´に対応する順序に並び替え、並び替え後の２つの受信データD831をセレクタ８３２に供給する。即ち、インターリーバ８３１は、２つの受信データD416のパリティ成分の順序を制御する。
【０１３８】
セレクタ８３２は、低速クロックＣＫ1に同期して、制御部８３５からの制御信号D835に基づいて、２つの受信データD416またはインターリーバ８３１からの２つの受信データD831のいずれか一方を選択し、その選択した２つの受信データD416またはD831を、２つの受信データD832としてビット幅調整回路８３３にパラレルに供給する。
【０１３９】
具体的には、高速クロックＣＫ2の速度が低速クロックＣＫ1の速度の２倍未満であるとき、制御信号D835は「０」となり、高速クロックの速度が低速クロックの速度の２倍以上であるとき、制御信号D835は「１」となる。制御信号D835が「０」である場合、セレクタ８３２は、インターリーバ８３１からの２つの受信データD831を選択し、制御信号D835が「１」である場合、セレクタ８３２は、２つの受信データD416を選択する。
【０１４０】
ビット幅調整回路８３３は、高速クロックＣＫ2に同期して、制御部８３５からの制御信号D835に基づいて、セレクタ８３２からの受信データD832のビット幅を調整する。具体的には、制御信号D835が「０」である場合、ビット幅調整回路８３３は、例えば低速クロックＣＫ1の1クロックに同期してパラレルに供給される２つの受信データD832を、高速クロックＣＫ2の1クロックに同期して、２つの受信データD833として、パラレルに受信メモリ８３４に供給する。
【０１４１】
一方、制御信号D835が「１」である場合、ビット幅調整回路８３３は、低速クロックＣＫ1の１クロックに同期してパラレルに供給される２つの受信データD832のビット幅を調整し、高速クロックＣＫ2の１クロックに同期して、１つずつ、受信データD833としてシリアルに受信メモリ８３４に供給する。即ち、ビット幅調整回路８３３は、高速クロックＣＫ2の２クロック間で、２つの受信データD833をシリアルに受信メモリ８３４に供給する。
【０１４２】
受信メモリ８３４は、例えば、RAM（Random Access Memory）により構成され、２つの受信データD833を同時に書き込んだり、６つの受信データD811を同時に読み出すことが可能である。なお、受信メモリ８３４のビット数はP（=6）と受信データD833の量子化ビット数を乗算した値であり、ワード数はn/P(=n0=18)である。受信メモリ８３４は、高速クロックＣＫ2に同期して、制御部８３５からの制御信号D834に基づいて、ビット幅調整回路８３３から供給される受信データD833を、検査行列H´の６つの列に対応するものを同時に読出可能な順に、ビット方向（縦方向）（後述する図１８）またはワード方向（横方向）に書き込む。
【０１４３】
具体的には、制御信号D834が「０」である場合、受信メモリ８３４は、受信データD833をビット方向に書き込む。一方、制御信号D834が「１」である場合、受信メモリ８３４は、受信データD833をワード方向に書き込む。即ち、情報成分に対応する受信データD833はビット方向に書き込まれ、パリティ成分に対応する受信データD833は、ワード方向に書き込まれる。
【０１４４】
受信メモリ８３４は、高速クロックＣＫ2に同期して、既に記憶してある受信データD833を、ビット方向に６つ単位で読み出し、受信データD811として計算部４１５に供給する。
【０１４５】
制御部８３５は、低速クロックＣＫ1に同期して、制御信号D834をインターリーバ８３１に供給するとともに、高速クロックＣＫ2に同期して、制御信号D834を受信メモリ８３４に供給する。また、制御部８３５は、低速クロックＣＫ1に同期して、制御信号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に基づいて、ビット幅調整回路８３３から供給される２つの受信データＩ0とＩ1を、０番アドレスの０ビット目と１ビット目にそれぞれ記憶する。
【０１５７】
次に、受信メモリ８３４は、制御信号D834に基づいて、ビット幅調整回路８３３からの２つの受信データＩ2とＩ3を、０番アドレスの２ビット目と３ビット目にそれぞれ記憶する。
【０１５８】
そして、同様の処理が繰り返され、受信メモリ８３４の０番アドレスの０乃至５ビット目には、受信データＩ0乃至Ｉ5がビット方向にそれぞれ記憶され、受信メモリ８３４の１番アドレスの０乃至５ビット目には、受信データＩ6乃至Ｉ11がビット方向にそれぞれ記憶される。以降も同様にして、受信メモリ８３４の２乃至１１（=k0-1）番アドレスに、受信データＩ12乃至Ｉ71が記憶される。
【０１５９】
次に、受信メモリ８３４は、制御部８３５から供給される制御信号D834に基づいて、ビット幅調整回路８３３から供給される受信データＤ0を、１２番アドレスの０ビット目に記憶する。また、受信メモリ８３４は、制御信号D834に基づいて、ビット幅調整回路８３３からの受信データＤ1を１３番アドレスの０ビット目に記憶する。
【０１６０】
そして、同様の処理が繰り返され、受信メモリ８３４の１２乃至１７（=n0-1）番アドレスの０ビット目には、受信データＤ0乃至Ｄ5がワード方向にそれぞれ記憶され、受信メモリ８３４の１２乃至１７番アドレスの１ビット目には、受信データＤ6乃至Ｄ11がワード方向にそれぞれ記憶される。以降も同様にして、受信メモリ８３４の２乃至６ビット目に、受信データＤ12乃至Ｄ35が記憶される。
【０１６１】
ここで、１２乃至１７番アドレスの、ワード方向での順番が（n0-k0）×x+y（x=0,1,・・・，5，y=0,1,・・・，5）番目の受信データＤmは、ビット方向での順番がP×y+x番目となる。なお、ビット方向の順番は、各番号アドレスの５ビット目の次が、右隣のアドレス（次の番号のアドレス）の０ビット目となるものとする。また、ワード方向の順番は、各ビットの５番アドレスの次が、直下のビット(次のビット)の０番アドレスとなるものとする。例えば、ビット方向での順番が６番目の受信データD833は、受信データＤ1となり、ワード方向での順番が６番目の受信データD833は受信データＤ6となる。
【０１６２】
上述したように、図１１の検査行列Hのパリティ部の（n0-k0）×v＋w列目の列は、図１２の検査行列H´のパリティ部では、P×w+v列目の列となる。即ち、検査行列H´のパリティ部のP×w+v列目の列は、検査行列Hのパリティ部の（n0-k0）×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ともいう。
【０１６７】
図２０は、高速クロックＣＫ2の速度が低速クロックＣＫ1の速度の２倍以上である場合の、受信データＡmの入力と、受信データＤmの書き込みとを説明するタイミングチャートである。
【０１６８】
図２０に示すように、受信部８１１には、受信データＡmが、２つずつ入力される。例えば、受信部８１１には、受信データＡ0とＡ1、受信データＡ2とＡ3、受信データＡ4とＡ5、受信データＡ6とＡ7・・・が順にパラレルに入力される。
【０１６９】
図２０では、高速クロックＣＫ2の速度が低速クロックＣＫ1の速度の２倍以上である、即ち制御信号D835が「１」であるので、セレクタ８３２は、受信部８１１に入力される２つの受信データＡmを、ビット幅調整回路８３３に供給する。
【０１７０】
図２０に示すように、ビット幅調整回路８３３は、セレクタ８３２から低速クロックＣＫ1の１クロックに同期してパラレルに入力される２つの受信データＡmを、高速クロックＣＫ2の１クロックに同期して、１つずつ、受信データＤmとして受信メモリ８３４にシリアルに供給し、書き込ませる。
【０１７１】
例えば、受信部８１１に低速クロックＣＫ1に同期して、受信データＡ0とＡ1がパラレルに入力される場合、受信メモリ８３４は、高速クロックＣＫ2の１クロックに同期して、受信データＤ0を１２番アドレスの０ビット目に書き込んだ後、次の１クロックに同期して受信データＤ1を１３番アドレスの０ビット目に書き込む。
【０１７２】
以上のように、図２０では、受信メモリ８３４以外のインターリーバ８３１やセレクタ８３２の動作クロックである低速クロックＣＫ1の、２倍以上の速度の高速クロックＣＫ2で受信メモリ８３４が動作するので、低速クロックＣＫ1の１クロックの間に、２つの受信データＤmを異なるアドレスに書き込むことができる。
【０１７３】
その結果、復号装置８００に受信データＡmを２個ずつ同時に入力し、スループットを向上させることができる。
【０１７４】
図２１は、高速クロックＣＫ2の速度が低速クロックＣＫ1の速度の２倍未満である場合の、受信データＡmの入力と、受信データＤmの書き込みとを説明するタイミングチャートである。
【０１７５】
図２１に示すように、受信部８１１には、図２０と同様に、受信データＡ0とＡ1、受信データＡ2とＡ3、受信データＡ4とＡ5、受信データＡ6とＡ7・・・が順にパラレルに入力される。
【０１７６】
図２１では、高速クロックＣＫ2の速度が低速クロックＣＫ1の速度の２倍未満である、即ち制御信号D835が「０」であるので、セレクタ８３２は、インターリーバ８３１から供給される受信データD831を、ビット幅調整回路８３３を介して受信メモリ８３４に供給する。
【０１７７】
即ち、インターリーバ８３１（図１７）には、受信データＡ0とＡ1、受信データＡ2とＡ3、受信データＡ4とＡ5、受信データＡ6とＡ7・・・がパラレルに順に入力され、レジスタ８５１−１乃至８５１−５は、パラレルに入力された２つの受信データＡmのうちの一方（例えば、受信データＡ0、Ａ2，Ａ4，Ａ6，・・・）を受信データD851として記憶し、レジスタ８５１−２乃至８５２−５は、他方（例えば、受信データＡ1、Ａ3，Ａ5，Ａ7，・・・）を受信データD852として記憶する。そして、レジスタ８５１−１乃至８５１−５と８５２−１乃至８５２−５は、受信データＡm（受信データD851またはD852）をそれぞれセレクタ８５３に供給する。また、２つの受信データＡmは、それぞれ、受信データD851またはD852として、直接セレクタ８５３に供給される。
【０１７８】
セレクタ８５３は、まず最初に、受信データＡ0とＡ6を選択し、受信データD853とD854としてそれぞれ出力する。次に、セレクタ８５３は、受信データＡ1とＡ7を選択し、受信データD853とD854としてそれぞれ出力する。その後、セレクタ８５３は、受信データＡ2とＡ8、受信データＡ3とＡ9・・・の順に選択して出力する。
【０１７９】
即ち、インターリーバ８３１にパラレルで入力される２つの受信データＡmを、６（=n0-k0）つ単位（３回のパラレル入力単位）で交互に系列＃１または系列＃２というと、セレクタ８５３は、系列＃１（例えば、受信データＡ0乃至Ａ5）と系列＃２（例えば、受信データＡ6乃至Ａ11）を、受信データＡ0とＡ6から、入力された順に２つずつ選択し、出力する。即ち、セレクタ８５３は、受信メモリ８３４のビット方向に書き込まれる受信データＤmに対応する受信データＡmを、２つずつ選択して出力する。
【０１８０】
インターリーバ８３１のセレクタ８５３により出力された２つの受信データＡmは、セレクタ８３２とビット幅調整回路８３３を介して、２つの受信データＤmとして受信メモリ８３４に供給される。そして、受信メモリ８３４は、高速クロックＣＫ2の1クロックに同期して、２つの受信データＡmを同一のアドレスにパラレルに書き込む。
【０１８１】
具体的には、図２１に示すように、受信メモリ８３４には、受信データＤ0とＤ6、受信データＤ1とＤ7、受信データＤ2とＤ8、受信データＤ3とＤ9・・・が順にパラレルに供給される。そして、受信メモリ８３４は、まず最初に、高速クロックＣＫ2の１クロックに同期して、２つの受信データＤ0とＤ6を、１２番アドレスの０ビット目と１ビット目にパラレルに書き込む。以降同様にして、受信メモリ８３４は、受信データＤ1とＤ7、受信データＤ2とＤ8、受信データＤ3とＤ9・・・を、１３番アドレス、１４番アドレス、１５番アドレス・・・の０ビット目と１ビット目にパラレルで書き込む。
【０１８２】
以上のように、インターリーバ８３１は、受信メモリ８３４のビット方向に書き込まれる受信データＤmに対応する受信データＡmを、２つずつ選択して出力するので、受信メモリ８３４は、２つの受信データＤmをパラレルに書き込むことができる。これにより、高速クロックＣＫ2が、低速クロックＣＫ1の２倍未満である場合においても、低速クロックＣＫ1の１クロックの間に、２つの受信データＤmを書き込むことができる。
【０１８３】
その結果、高速クロックＣＫ2の速度を低速クロックＣＫ1の速度の２倍以上に上げずに、復号装置８００のスループットを向上させることができる。
【０１８４】
図２２は、図１５の計算部４１２の計算器４１２kの構成例を示すブロック図である。
【０１８５】
図２２では、前回の計算部４１２による第１の演算の結果得られる各復号途中結果D412k（D413k）(udv)が符号ビットを合わせて合計６ビット(bit)に量子化され、計算部４１５による第２の演算の結果得られる各復号途中結果D415（D411k）（v）が９ビットに量子化されているものとして、計算器４１２kを表している。さらに、図２２の計算器４１２kには、高速クロックＣＫ2が供給され、この高速クロックＣＫ2は、必要なブロックに供給されるようになっている。そして、各ブロックは、高速クロックＣＫ2に同期して処理を行う。
【０１８６】
図２２の計算器４１２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の構成例を示すブロック図である。
【０２０４】
なお、図２３では、計算部４１２による第１の演算の結果得られる各復号途中結果D412k（D414k）（uj）が符号ビットを合わせて合計６ビットに量子化されているものとして、計算器４１５kを表している。さらに、図２３の計算器４１５kには、高速クロックＣＫ2が供給され、この高速クロックＣＫ2は、必要なブロックに供給されるようになっている。そして、各ブロックは、高速クロックＣＫ2に同期して処理を行う。
【０２０５】
図２３の計算器４１５kは、制御部４１７から供給される制御信号D422に基づいて、受信用メモリ４１６から１つずつ読み込まれる受信データD811k（u0i）と、サイクリックシフト回路４１４から１つずつ読み込まれる復号途中結果D414k（uj）とを用いて、式（５）にしたがう第２の演算を行う。
【０２０６】
即ち、計算器４１５kでは、サイクリックシフト回路４１４から、検査行列H´の各行の１に対応する６ビットの復号途中結果D414k（uj）が１つずつ読み込まれ、その復号途中結果D414が、加算器４７１に供給される。また、計算器４１５kでは、受信用メモリ４１６から６ビットの受信データD811kが１つずつ読み込まれ、加算器４７５に供給される。さらに、計算器４１５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と、受信用メモリ４１６から供給された６ビットの受信データD811kとを加算して、その結果得られる６ビットの値を復号途中結果D415k（v）として出力する。
【０２１１】
以上のように、計算器４１５kでは、式（５）の演算が行われ、復号途中結果vが求められる。
【０２１２】
なお、図１２の検査行列H´の列の重みの最大は５であるため、即ち、計算器４１５kに供給される復号途中結果ujの最大数は５であるため、計算器４１５kは、６ビットの復号途中結果ujを最大５個加算する。従って、計算器４１５kの出力は、９ビットの値となっている。
【０２１３】
図２４は、図１５の出力部８１２の詳細構成例を示している。
【０２１４】
図２４の出力部８１２は、復号結果メモリ９０１、ビット幅調整回路９０２、デインターリーバ９０３、セレクタ９０４、および制御部９０５から構成される。
【０２１５】
なお、図２４では、復号結果メモリ９０１、ビット幅調整回路９０２、および制御部９０５は、高速クロックＣＫ2（ＣＫ2＞ＣＫ3）で動作し、デインターリーバ９０３とセレクタ９０４は低速クロックＣＫ3で動作する。なお、図１６の低速クロックＣＫ1と図２４の低速クロックＣＫ3は同一であっても異なっていてもよい。
【０２１６】
出力部８１２には、計算部４１５（図２３）から、６つの復号途中結果D415が検査行列H´に対応する順に供給され、復号結果メモリ９０１に供給される。
【０２１７】
復号結果メモリ９０１は、例えば、RAMにより構成され、６つの復号途中結果D415を同時に書き込んだり、２つの復号結果D901を同時に読み出すことが可能である。なお、復号結果メモリ９０１のビット数はP（=6）と復号途中結果D415の量子化ビット数を乗算した値であり、ワード数はn/P(=18)である。復号結果メモリ９０１は、高速クロックＣＫ2に同期して、復号途中結果D415をビット方向に書き込む。
【０２１８】
また、復号結果メモリ９０１は、高速クロックＣＫ2に同期して、既に記憶してある復号途中結果D415を、制御部９０５から供給される制御信号D906に基づいて、ビット方向またはワード方向に読み出し、復号結果D901としてビット幅調整回路９０２に供給する。
【０２１９】
具体的には、受信データD416の情報成分を用いて求められた復号途中結果D415が、復号結果メモリ９０１に供給される場合、制御信号D906は「０」となり、パリティ成分を用いて求められた復号途中結果D415が復号結果メモリ９０１に供給される場合、制御信号D906は「１」となる。
【０２２０】
制御信号D906が「０」である場合、復号結果メモリ９０１は、復号途中結果D415をビット方向に読み出す。一方、制御信号D906が「１」である場合、復号結果メモリ９０１は、復号途中結果D415をワード方向に読み出す。即ち、情報成分を用いて求められた復号途中結果D415はビット方向に読み出され、パリティ成分を用いて求められた復号途中結果D415は、ワード方向に読み出される。
【０２２１】
なお、高速クロックＣＫ2の速度が低速クロックＣＫ3の速度の２倍以上である場合、復号結果メモリ９０１は、例えば高速クロックＣＫ2の１クロックに同期して、１つの復号結果D901をシリアルに出力し、高速クロックＣＫ2の速度が低速クロックＣＫ3の速度の２倍未満である場合、復号結果メモリ９０１は、高速クロックＣＫ2の１クロックに同期して、２つの復号結果D901をパラレルに出力する。
【０２２２】
ビット幅調整回路９０２は、高速クロックＣＫ2に同期して、制御部９０５からの制御信号D905に基づいて、復号結果メモリ９０１からの復号結果D901のビット幅を調整する。具体的には、高速クロックＣＫ2の速度が低速クロックＣＫ3の速度の２倍未満であるとき、制御信号D905は「０」となり、高速クロックＣＫ2の速度が低速クロックＣＫ3の速度の２倍以上であるとき、制御信号D905は「１」となる。
【０２２３】
制御信号D905が「０」である場合、ビット幅調整回路９０２は、例えば高速クロックＣＫ2の1クロックに同期してパラレルに供給される２つの復号結果D901を、低速クロックＣＫ3の1クロックに同期して、２つの復号結果D902として、パラレルにデインターリーバ９０３とセレクタ９０４に供給する。
【０２２４】
一方、制御信号D905が「１」である場合、ビット幅調整回路９０２は、高速クロックＣＫ2の１クロックに同期してシリアルに供給される１つの復号結果D901のビット幅を調整し、低速クロックＣＫ3の１クロックに同期して、復号結果D901を２つずつ、復号結果D902としてパラレルにデインターリーバ９０３とセレクタ９０４に供給する。即ち、ビット幅調整回路９０２は、高速クロックＣＫ2の２クロック間に供給される２つの復号結果D901を、パラレルにデインターリーバ９０３とセレクタ９０４に供給する。
【０２２５】
デインターリーバ９０３は、低速クロックＣＫ3に同期して、制御部９０５からの制御信号D906に基づいて、ビット幅調整回路９０２から供給される２つの復号結果D902の順序を制御する。
【０２２６】
具体的には、制御信号D906が「０」である場合、デインターリーバ９０３は、２つの復号結果D902をそのまま復号結果D903としてセレクタ９０４に供給する。一方、制御信号D906が「１」である場合、デインターリーバ９０３は、２つの復号結果D902を検査行列Hに対応する順序に並び替え、並び替え後の２つの復号結果D903をセレクタ９０４に供給する。即ち、デインターリーバ９０３は、受信データD416のパリティ成分を用いて求められた２つの復号途中結果D415に対応する復号結果D902の順序を制御する。
【０２２７】
セレクタ９０４には、低速クロックＣＫ3に同期して、制御部９０５からの制御信号D905に基づいて、２つの復号結果D902またはデインターリーバ９０３からの２つの復号結果D903のいずれか一方を選択し、その選択した２つの復号結果D902またはD903を、復号結果D812として出力する。
【０２２８】
具体的には、制御信号D905が「０」である場合、セレクタ９０４は、デインターリーバ９０３からの２つの復号結果D903を選択し、制御信号D905が「１」である場合、セレクタ９０４は、２つの復号結果D902を選択する。
【０２２９】
制御部９０５は、低速クロックＣＫ3に同期して、制御信号D905をセレクタ９０４に供給する。また、制御部９０５は、高速クロックＣＫ2に同期して、制御信号D906を復号結果メモリ９０１に供給するとともに、低速クロックＣＫ3に同期して、制御信号D906をデインターリーバ９０３に供給する。
【０２３０】
次に、図２５を参照して、図２４の復号結果メモリ９０１について説明する。
【０２３１】
なお、図２５では、説明の便宜上、復号結果メモリ９０１のビットを、復号途中結果D415の量子化ビットが１ビットであるとして説明する。
【０２３２】
また、以下では、検査行列H´の情報部のｍ列目に対応する、受信データD416の情報成分を用いて求められた復号途中結果D415を、復号途中結果Ｂmとも表し、検査行列H´のパリティ部のｍ列目に対応する、受信データD416のパリティ成分を用いて求められた復号途中結果D415を、復号途中結果Ｃmとも表す。
【０２３３】
図２５に示すように、復号結果メモリ９０１のビット数は、Ｐ(=6)と復号結果D415の量子化ビット数を乗算した値であり、ワード数は、n/p（=18）である。
【０２３４】
まず最初に、復号結果メモリ９０１は、計算部４１５から供給される６つの復号結果Ｂ0乃至Ｂ5を、０番アドレスの０乃至５ビット目に、それぞれビット方向に記憶する。次に、復号結果メモリ９０１は、計算部４１５からの６つの復号結果Ｂ6乃至Ｂ11を、１番アドレスの０乃至５ビット目に、それぞれビット方向に記憶する。
【０２３５】
以降同様にして、復号結果メモリ９０１の２乃至１１（=k0-1）番アドレスの０乃至５ビット目に、復号結果Ｂ12乃至Ｂ71が記憶される。
【０２３６】
次に、復号結果メモリ９０１は、計算部４１５から供給される６つの復号結果Ｃ0乃至Ｃ5を、１２番アドレスの０乃至５ビット目に、それぞれビット方向に記憶する。また、復号結果メモリ９０１は、計算部４１５からの６つの復号結果Ｃ6乃至Ｃ11を、１３番アドレスの０乃至５ビット目に、それぞれビット方向に記憶する。そして、同様の処理が繰り返され、復号結果メモリ９０１の１４番アドレス乃至１７番アドレスの０乃至５ビット目に、復号結果Ｃ12乃至Ｃ35が記憶される。
【０２３７】
ここで、１２乃至１７番アドレスの、ビット方向での順番がP×y+x番目の復号結果Ｃmは、ワード方向での順番が（n0-k0）×x+y番目となる。
【０２３８】
上述したように、図１２の検査行列H´のパリティ部のP×w+v列目の列は、図１１の検査行列Hのパリティ部の（n0-k0）×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ともいう。
【０２４７】
図２７は、高速クロックＣＫ2の速度が低速クロックＣＫ3の速度の２倍以上である場合の、復号結果Ｃmの読み出しと復号結果Ｅmの出力とを説明するタイミングチャートである。
【０２４８】
図２７に示すように、復号結果メモリ９０１は、既に記憶している復号結果Ｃmを、高速クロックＣＫ2の１クロックに同期して、１２番アドレスの０ビット目から順に、１つずつワード方向に読み出す。例えば、復号結果メモリ９０１は、復号結果Ｃ0,Ｃ6，Ｃ12，Ｃ18、Ｃ24，Ｃ30，Ｃ1，Ｃ7・・・を順にシリアルに読み出す。
【０２４９】
そして、ビット幅調整回路９０２は、復号結果メモリ９０１から連続して読み出された２つの復号結果Ｃmを、低速クロックＣＫ3の１クロックに同期して、２つの復号結果D902として、パラレルにデインターリーバ９０３とセレクタ９０４に供給する。
【０２５０】
図２７では、高速クロックＣＫ2の速度が低速クロックＣＫ3の速度の２倍以上である、即ち制御部９０５から供給される制御信号D905が１であるので、セレクタ９０４は、ビット幅調整回路９０２からの２つの復号結果D902を、復号結果Ｅmとして、そのまま出力する。
【０２５１】
即ち、図２７に示すように、出力部８１２のセレクタ９０４は、復号結果Ｅ0とＥ6，Ｅ12とＥ18，Ｅ24とＥ30，Ｅ1とＥ7・・・を、順にパラレルに出力する。ここで、上述したように、図１２の検査行列H´のパリティ部のP×w+v列目の列は、図１１の検査行列Hのパリティ部では、（n0-k0）×v＋w列目の列となるので、出力部８１２により出力される復号結果Ｅ0とＥ6，Ｅ12とＥ18，Ｅ24とＥ30，Ｅ1とＥ7・・・は、検査行列Hのパリティ部の０列目乃至３５列目に対応する復号結果D812となる。即ち、出力部８１２は、検査行列Hの０列目から順に、検査行列Hの各列に対応する復号結果Ｅmを２つずつ出力する。
【０２５２】
以上のように、復号装置８００は受信データＥmを２個ずつ同時に出力し、スループットを向上させることができる。
【０２５３】
図２８は、高速クロックＣＫ2の速度が低速クロックＣＫ3の速度の２倍未満である場合の、復号結果メモリ９０１からの復号結果Ｃmの読み出しと、出力部８１２からの復号結果Ｅmの出力とを説明するタイミングチャートである。
【０２５４】
図２８に示すように、復号結果メモリ９０１は、既に記憶している復号結果Ｃmを、高速クロックＣＫ2の１クロックに同期して、１２番アドレスの０ビット目と１ビット目から順に、２つずつワード方向にシリアルに読み出す。例えば、復号結果メモリ９０１は、復号結果Ｃ0とＣ1，Ｃ6とＣ7、Ｃ12とＣ13，Ｃ18とＣ19・・・を順にパラレルに読み出す。
【０２５５】
そして、復号結果メモリ９０１から出力される復号結果Ｃmは、ビット幅調整回路９０２を介して、デインターリーバ９０３とセレクタ９０４に供給される。
【０２５６】
図２８では、高速クロックＣＫ2の速度が低速クロックＣＫ3の速度の２倍未満である、即ち制御信号D905が「０」であるので、セレクタ９０４は、デインターリーバ９０３から供給される復号結果D903を、復号結果D812として出力する。
【０２５７】
即ち、復号結果メモリ９０１は、異なるアドレスの復号結果Ｃmを読み出すこと、即ちワード方向にパラレルに復号結果Ｃmを読み出すことはできないので、復号装置８００では、デインターリーバ９０３が、復号結果メモリ９０１からビット方向にパラレルに読み出された２つの復号結果Ｃmの順序を制御し、セレクタ９０４を介して、ワード方向に記憶される順にパラレルに２つの復号結果Ｃmに対応する復号結果D812を出力する。
【０２５８】
具体的には、デインターリーバ９０３（図２６）には、復号結果Ｃ0とＣ1、復号結果Ｃ6とＣ7、復号結果Ｃ12とＣ13、復号結果Ｃ18とＣ19・・・がパラレルに復号結果D902として順に入力され、レジスタ９２１−１乃至９２１−５は、復号結果D902としてパラレルに入力された２つの復号結果Ｃmのうちの一方(例えば、復号結果Ｃ0，Ｃ6，Ｃ12，Ｃ18)を、復号結果D921として記憶し、レジスタ９２２−１乃至９２２−５は、他方(例えば、復号結果Ｃ1，Ｃ7，Ｃ13，Ｃ19)を復号結果D922として記憶する。そして、レジスタ９２１−１乃至９２１−５と９２２−１乃至９２２−５は、復号結果Ｃm（復号結果D921またはD922）をそれぞれセレクタ９２３に供給する。また、２つの復号結果D902は、それぞれ復号結果D921またはD922として、セレクタ９２３に直接供給される。
【０２５９】
セレクタ９２３は、まず最初に、復号結果Ｃ0とＣ6を選択し、受信データD853とD854としてそれぞれ出力する。次に、セレクタ９２３は、復号結果Ｃ12とＣ18を選択し、受信データD853とD854としてそれぞれ出力する。その後、セレクタ９２３は、復号結果Ｃ24とＣ30、復号結果Ｃ1とＣ7・・・の順に選択して出力する。
【０２６０】
即ち、デインターリーバ９０３にパラレルで入力される２つの復号結果Ｃmの一方を系列＃１´といい、他方を系列＃２´というと、セレクタ９２３は、６回のパラレル入力単位で交互に系列＃１´(例えば、復号結果Ｃ0，Ｃ6，Ｃ12，Ｃ18，Ｃ24，Ｃ30)と系列＃２´(例えば、復号結果Ｃ1，Ｃ7，Ｃ13，Ｃ19，Ｃ25，Ｃ31)から、入力された順に２つずつ選択し、出力する。即ち、セレクタ９２３は、復号結果メモリ９０１のワード方向に書き込まれる受信データＣmを、２つずつ選択してセレクタ９０４に供給する。
【０２６１】
デインターリーバ９０３のセレクタ９２３により出力された２つの復号結果Ｃmは、セレクタ９０４を介して、２つの受信データＥmとしてパラレルに出力される。
【０２６２】
具体的には、図２８に示すように、セレクタ９０４は、低速クロックＣＫ3に同期して、復号結果Ｅ0とＥ6、Ｅ12とＥ18、Ｅ24とＥ30、Ｅ1とＥ7・・・を順にパラレルに出力する。
【０２６３】
以上のように、デインターリーバ９０３は、復号結果メモリ９０１からビット方向に読み出された復号結果Ｃmを、ワード方向に記憶される順に、２つずつパラレルに出力するので、出力部８１２は、検査行列Hに対応する復号結果Ｅmを２つずつパラレルに出力することができる。これにより、高速クロックＣＫ2が、低速クロックＣＫ3の２倍未満である場合においても、低速クロックＣＫ3の１クロックの間に、２つの復号結果Ｅmを出力することができる。その結果、復号装置８００では、高速クロックＣＫ2の速度を低速クロックＣＫ3の速度の２倍以上に上げずに、復号装置８００のスループットを向上させることができる。
【０２６４】
次に、図２９を参照して、図１６の受信部８１１が受信データD811を出力する受信データ出力処理について説明する。この受信データ出力処理は、例えば、受信部８１１のインターリーバ８３１とセレクタ８３２に、２つの受信データD416が供給されたとき開始される。
【０２６５】
ステップＳ３１において、インターリーバ８３１は、２つの受信データD416の順序を制御し、その結果得られる２つの受信データD831をセレクタ８３２に供給し、ステップＳ３２に進む。
【０２６６】
ステップＳ３２において、セレクタ８３２は、制御部８３５からの制御信号D835に基づいて、２つの受信データD416またはステップＳ３１で供給される２つの受信データD831のいずれかを選択し、２つの受信データD832としてビット幅調整回路８３３に供給する。
【０２６７】
ステップＳ３２の処理後は、ステップＳ３３に進み、ビット幅調整回路８３３は、制御部８３５からの制御信号D835に基づいて、ステップＳ３２で供給される２つの受信データD832のビット幅を調整し、その結果得られる受信データD833を受信メモリ８３４に供給する。
【０２６８】
ステップＳ３３の処理後は、ステップＳ３４に進み、受信メモリ８３４は、制御部８３５からの制御信号D834に基づいて、ステップＳ３３で供給される受信データD833をビット方向またはワード方向に記憶し、処理を終了する。
【０２６９】
なお、ステップＳ３４の処理により、LDPC符号に対応する受信データD833がすべて記憶された後、受信メモリ８３４は、既に記憶してある受信データD833をビット方向に６つ単位で読み出し、受信データD811として計算部４１５に供給する。
【０２７０】
図３０は、図１５の復号装置８００の復号処理を説明するフローチャートである。この処理は、例えば、受信データD811が計算部４１５に供給されたとき、開始される。
【０２７１】
ステップＳ５０において、サイクリックシフト回路４１４は、復号途中結果格納用メモリ４１３から供給された後述するステップＳ５６で格納される６つの復号途中結果D413（uj）を、サイクリックシフトし、計算部４１５に供給する。
【０２７２】
具体的には、サイクリックシフト回路４１４には、復号途中結果格納用メモリ４１３から６つの復号途中結果D4131乃至D4136が供給されるとともに、制御部４１７から、その復号途中結果D413に対応する検査行列H´の１が検査行列H´において元となる単位行列などを幾つサイクリックシフトしたものであるかの情報（Matrixデータ）を表す制御信号D421が供給される。サイクリックシフト回路４１４は、制御信号D421を元に、６つの復号途中結果D4131乃至D4136をサイクリックシフトし（並べ替え）、その結果を復号途中結果D4141乃至D4146として、計算部４１５に供給する。
【０２７３】
なお、受信部８１１から供給された受信データD811に対して、まだ第１の演算が行われておらず、復号途中結果格納用メモリ４１３に復号途中結果D412が格納されていない場合、計算部４１５は、復号途中結果ujを初期値（例えば、受信データD811）に設定する。
【０２７４】
ステップＳ５０の処理後は、ステップＳ５１に進み、計算部４１５は、第２の演算を行い、その演算の結果である復号途中結果D4151乃至D4156を復号途中結果格納用メモリ４１０に供給する。
【０２７５】
具体的には、計算部４１５には、ステップＳ５０でサイクリックシフト回路４１４から６つの復号途中結果D4141乃至D4146が供給されるとともに、受信部８１１から６つの受信データD8111乃至D8116が供給され、復号途中結果D4151乃至D4156と受信データD8111乃至D8116が、計算部４１５の計算器４１５1乃至４１５6それぞれに１つずつ供給される。さらに、計算部４１５には、制御部４１７から制御信号D422が供給され、その制御信号D422が計算器４１５1乃至４１５6に供給される。
【０２７６】
各計算器４１５kは、復号途中結果D414kと受信データD811kを用いて、制御信号D422に基づいて、式（５）にしたがう第２の演算を行い、その演算の結果得られる検査行列H´の列に対応する復号途中結果D415k(v)を復号途中結果格納用メモリ４１０に供給する。
【０２７７】
ステップＳ５１の処理後は、ステップＳ５２に進み、復号途中結果格納用メモリ４１０は、ステップＳ５１で計算部４１５から供給された６つの復号途中結果D4151乃至D4156を、同一アドレスに格納し、ステップＳ５３に進む。
【０２７８】
ステップＳ５３において、制御部４１７は、計算部４１５により、検査行列H´の列に対応する全ての復号途中結果D415が演算されたかどうかを判定し、全ての復号途中結果D415が演算されていないと判定した場合、ステップＳ５０に戻り、上述した処理を繰り返す。
【０２７９】
一方、ステップＳ５３において、制御部４１７は、計算部４１５により、検査行列H´の列に対応する全ての復号途中結果D415が演算されたと判定した場合、ステップＳ５４に進み、サイクリックシフト回路４１１は、復号途中結果格納用メモリ４１０から供給される復号途中結果D410(v)をサイクリックシフトする。
【０２８０】
具体的には、サイクリックシフト回路４１１には、復号途中結果格納用メモリ４１０から６つの復号途中結果D410が供給されるとともに、制御部４１７から、その復号途中結果D410に対応する検査行列H´の１が検査行列H´において元となる単位行列などを幾つサイクリックシフトしたものであるかの情報（Matrixデータ）を表す制御信号D418が供給される。サイクリックシフト回路４１１は、制御信号D418を元に、６つの復号途中結果D410をサイクリックシフトし（並べ替え）、その結果を復号途中結果D4111乃至D4116として、計算部４１２に供給する。
【０２８１】
ステップＳ５４の処理後は、ステップＳ５５に進み、計算部４１２は、上述した図２２で説明したように、６個の第１の演算を同時に行い、その演算結果である復号途中結果D4121乃至D4126を復号途中結果格納用メモリ４１３に供給する。  
【０２８２】
ステップＳ５５の処理後は、ステップＳ５６に進み、復号途中結果格納用メモリ４１３は、ステップＳ５５で計算部４１２から供給された６つの復号途中結果D4121乃至D4126を、同一のアドレスに格納し、ステップＳ５７に進む。
【０２８３】
ステップＳ５７において、制御部４１７は、計算部４１２により、検査行列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の約数など）とすることができる。この場合、高速クロックＣＫ2の速度が、低速クロックＣＫ1またはＣＫ3の速度のＮ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のビット方向とワード方向について説明する図である。
【図１９】図１６の受信メモリに記憶される受信データについて説明する図である。
【図２０】図１６の受信部への入力と、受信メモリへの書き込みとを説明するタイミングチャートである。
【図２１】図１６の受信部への入力と、受信メモリへの書き込みとを説明するタイミングチャートである。
【図２２】図１５の計算器の構成例を示すブロック図である。
【図２３】図１５の計算器の構成例を示すブロック図である。
【図２４】図１５の出力部の詳細構成例を示すブロック図である。
【図２５】図２４の復号結果メモリについて説明する図である。
【図２６】図２４のデインターリーバの詳細構成例を示すブロック図である。
【図２７】図２４の復号結果メモリからの読み出しと、出力部からの出力とを説明するタイミングチャートである。
【図２８】図２４の復号結果メモリからの読み出しと、出力部からの出力とを説明するタイミングチャートである。
【図２９】受信データ出力処理について説明するフローチャートである。
【図３０】復号処理を説明するフローチャートである。
【図３１】復号結果出力処理について説明するフローチャートである。
【符号の説明】
【０３０５】
４１０  復号途中結果格納用メモリ,  ４１１  サイクリックシフト回路,  ４１２  計算部，  ４１３  復号途中結果格納用メモリ,  ４１４  サイクリックシフト回路，  ４１５  計算部，  ４１７  制御部,  ８００  復号装置,  ８１１  受信部，  ８１２  出力部,  ８３１  インターリーバ，  ８３２  セレクタ，  ８３３  ビット幅調整回路，  ８３４  受信メモリ，  ８３５  制御部，  ９０１  復号結果メモリ，  ９０２  ビット幅調整回路，  ９０３  デインターリーバ，  ９０４  セレクタ，  ９０５  制御部
【図１】
2007036776.tif 000011
【図２】
2007036776.tif 000012
【図３】
2007036776.tif 000013
【図４】
2007036776.tif 000014
【図５】
2007036776.tif 000015
【図６】
2007036776.tif 000016
【図７】
2007036776.tif 000017
【図８】
2007036776.tif 000018
【図９】
2007036776.tif 000019
【図１０】
2007036776.tif 000020
【図１１】
2007036776.tif 000021
【図１２】
2007036776.tif 000022
【図１３】
2007036776.tif 000023
【図１４】
2007036776.tif 000024
【図１５】
2007036776.tif 000025
【図１６】
2007036776.tif 000026
【図１７】
2007036776.tif 000027
【図１８】
2007036776.tif 000028
【図１９】
2007036776.tif 000029
【図２０】
2007036776.tif 000030
【図２１】
2007036776.tif 000031
【図２２】
2007036776.tif 000032
【図２３】
2007036776.tif 000033
【図２４】
2007036776.tif 000034
【図２５】
2007036776.tif 000035
【図２６】
2007036776.tif 000036
【図２７】
2007036776.tif 000037
【図２８】
2007036776.tif 000038
【図２９】
2007036776.tif 000039
【図３０】
2007036776.tif 000040
【図３１】
2007036776.tif 000041