(57)【要約】【課題】  回路規模を抑制しつつ、動作周波数も十分実現可能な範囲に抑え、メモリアクセスの制御も容易に行うことができるLDPC符号の復号を実現する。【解決手段】  LDPC符号の検査行列は、P×Pの単位行列、その単位行列の１のうちの１個からから数個が０になった行列、それらのサイクリックシフト、それらの複数の和、P×Pの０行列の組合せで構成される。チェックノード計算部３１３は、チェックノードの演算を、P個同時に行い、バリアブルノード計算部３１９は、バリアブルノードの演算を、P個同時に行う。【選択図】図１６
2004364233.tif 000002
【特許請求の範囲】
【請求項１】
LDPC(Low Density Parity Check)符号の復号装置であって、
P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、前記LDPC符号の検査行列が、複数の前記構成行列の組合せで表される場合において、
前記LDPC符号の復号のためのP個のチェックノードの演算を同時に行う第１の演算手段と、
前記LDPC符号の復号のためのP個のバリアブルノードの演算を同時に行う第２の演算手段と
を備えることを特徴とする復号装置。
【請求項２】
請求項１に記載の復号装置であって、
前記第１の演算手段は、チェックノードの演算を行うP個のチェックノード計算器を有し、
前記第２の演算手段は、バリアブルノードの演算を行うP個のバリアブルノード計算器を有する
ことを特徴とする復号装置。
【請求項３】
請求項１に記載の復号装置であって、
前記P個のチェックノードの演算、または前記P個のバリアブルノードの演算の結果得られるP個の枝に対応するメッセージデータを同時に読み書きするメッセージ記憶手段をさらに備える
ことを特徴とする復号装置。
【請求項４】
請求項３に記載の復号装置であって、
前記メッセージ記憶手段は、チェックノードの演算時に読み出される枝に対応するメッセージデータを、検査行列の１を行方向に詰めるように格納する
ことを特徴とする復号装置。
【請求項５】
請求項３に記載の復号装置であって、
前記メッセージ記憶手段は、バリアブルノード演算時に読み出される枝に対応するメッセージデータを、検査行列の１を列方向に詰めるように格納する
ことを特徴とする復号装置。
【請求項６】
請求項３に記載の復号装置であって、
前記メッセージ記憶手段は、前記検査行列を表す構成行列のうちの、重みが２以上の構成行列について、その構成行列を、重みが１の単位行列、準単位行列、またはシフト行列の和の形で表現したときの、その重みが１の単位行列、準単位行列、またはシフト行列に属するP個の枝に対応するメッセージを、同一のアドレスに格納する
ことを特徴とする復号装置。
【請求項７】
請求項３に記載の復号装置であって、
前記メッセージ記憶手段は、行数／P個のFIFOと、列数／P個のFIFOとで構成され、
前記行数／P個のFIFOと列数／P個のFIFOは、それぞれ、前記検査行列の行と列の重みに対応するワード数を有する
ことを特徴とする復号装置。
【請求項８】
請求項３に記載の復号装置であって、
前記メッセージ記憶手段は、RAM(Random Access Memory)で構成され、
前記RAMは、前記メッセージデータを、読み出される順番に詰めて格納し、格納位置順に読み出す
ことを特徴とする復号装置。
【請求項９】
請求項１に記載の復号装置であって、
LDPC符号の受信情報を格納するとともに、P個の前記受信情報を同時に読み出す受信情報記憶手段をさらに備える
ことを特徴とする復号装置。
【請求項１０】
請求項９に記載の復号装置であって、
前記受信情報記憶手段は、前記受信情報を、前記バリアブルノードの演算に必要となる順番に読み出すことができるように格納する
ことを特徴とする復号装置。
【請求項１１】
請求項１に記載の復号装置であって、
前記P個のチェックノードの演算、または前記P個のバリアブルノードの演算の結果得られるメッセージを並べ替える並べ替え手段をさらに備える
ことを特徴とする復号装置。
【請求項１２】
請求項１１に記載の復号装置であって、
前記並べ替え手段は、バレルシフタで構成される
ことを特徴とする復号装置。
【請求項１３】
請求項１に記載の復号装置であって、
前記第１の演算手段と前記第２の演算手段は、P個の枝に対応するメッセージを求める
ことを特徴とする復号装置。
【請求項１４】
請求項１に記載の復号装置であって、
前記第１の演算手段は、前記P個のチェックノードの演算と前記P個のバリアブルノードの演算の一部とを行い、
前記第２の演算手段は、前記P個のバリアブルノードの演算の他の一部を行う
ことを特徴とする復号装置。
【請求項１５】
請求項１４に記載の復号装置であって、
前記第１の演算手段は、前記P個のチェックノードの演算と前記P個のバリアブルノードの演算の一部を行うP個の計算器を有し、
前記第２の演算手段は、前記P個のバリアブルノードの演算の他の一部を行うP個の計算器を有する
ことを特徴とする復号装置。
【請求項１６】
請求項１４に記載の復号装置であって、
前記第１の演算手段が前記P個のチェックノードの演算と前記P個のバリアブルノードの演算の一部を行うことにより得られるP個の枝に対応する第１の復号途中結果を同時に読み書きする第１の復号途中結果記憶手段をさらに備える
ことを特徴とする復号装置。
【請求項１７】
請求項１６に記載の復号装置であって、
前記第１の復号途中記憶手段は、前記P個のバリアブルノードの演算の他の一部を行う時に読み出される枝に対応する前記第１の復号途中結果を、検査行列の１を行方向に詰めるように格納する
ことを特徴とする復号装置。
【請求項１８】
請求項１６に記載の復号装置であって、
前記第１の復号途中結果記憶手段は、２個のシングルポートRAM(Random Access Memory)である
ことを特徴とする復号装置。
【請求項１９】
請求項１８に記載の復号装置であって、
前記２個のシングルポートRAMは、前記第1の復号途中結果を前記検査行列のＰ行の枝に対応する前記第１の復号途中結果ずつ交互に格納する
ことを特徴とする復号装置。
【請求項２０】
請求項１８に記載の復号装置であって、
前記２個のシングルポートRAM(Random Access Memory)は、それぞれ同一のアドレスに格納している前記第１の復号途中結果を読み出す
ことを特徴とする復号装置。
【請求項２１】
請求項１６記載の復号装置であって、
前記第１の復号途中結果記憶手段は、前記検査行列を表す構成行列のうちの、重みが２以上の構成行列について、その構成行列を、重みが１の単位行列、準単位行列、またはシフト行列の和の形で表現したときの、その重みが１の単位行列、準単位行列、またはシフト行列に属するP個の枝に対応する前記第１の復号途中結果を、同一のアドレスに格納する
ことを特徴とする復号装置。
【請求項２２】
請求項１４に記載の復号装置であって、
前記第２の演算手段が前記P個のバリアブルノードの演算の他の一部を行うことにより得られるP個の枝に対応する前記第２の復号途中結果を同時に読み書きする第２の復号途中結果記憶手段をさらに備える
ことを特徴とする復号装置。
【請求項２３】
請求項１４に記載の復号装置であって、
LDPC符号の受信情報を格納するとともに、P個の前記受信情報を同時に読み出す受信情報記憶手段をさらに備える
ことを特徴とする復号装置。
【請求項２４】
請求項２３に記載の復号装置であって、
前記受信情報記憶手段は、前記受信情報を、前記P個のバリアブルノードの演算の他の一部の演算に必要となる順番に読み出すことができるように格納する
ことを特徴とする復号装置。
【請求項２５】
請求項１４に記載の復号装置であって、
前記第１の演算手段が前記P個のチェックノードの演算と前記P個のバリアブルノードの演算の一部を行うことにより得られる第１の復号途中結果、または前記第２の演算手段が前記P個のバリアブルノードの演算の他の一部を行うことにより得られる第２の復号途中結果を並べ替える並べ替え手段をさらに備える
ことを特徴とする復号装置。
【請求項２６】
請求項２５に記載の復号装置であって、
前記並べ替え手段は、バレルシフタで構成される
ことを特徴とする復号装置。
【請求項２７】
請求項１に記載の復号装置であって、
前記第１の演算手段は、前記P個のチェックノードの演算の一部を行い、
前記第２の演算手段は、前記P個のチェックノードの演算の他の一部と、前記P個のバリアブルノードの演算とを行う
ことを特徴とする復号装置。
【請求項２８】
請求項２７に記載の復号装置であって、
前記第１の演算手段は、前記P個のチェックノードの演算の一部を行うP個の計算器を有し、
前記第２の演算手段は、前記P個のチェックノードの演算の他の一部と、前記P個のバリアブルノードの演算を行うP個の計算器を有する
ことを特徴とする復号装置。
【請求項２９】
請求項２７に記載の復号装置であって、
前記第１の演算手段が前記P個のチェックノードの演算の一部を行うことにより得られるP個の枝に対応する第１の復号途中結果を同時に読み書きする第１の復号途中結果記憶手段をさらに備える
ことを特徴とする復号装置。
【請求項３０】
請求項２７に記載の復号装置であって、
前記第２の演算手段が前記P個のチェックノードの演算の他の一部と、前記P個のバリアブルノードの演算を行うことにより得られるP個の枝に対応する第２の復号途中結果を同時に読み書きする第２の復号途中結果記憶手段をさらに備える
ことを特徴とする復号装置。
【請求項３１】
請求項３０に記載の復号装置であって、
前記第２の復号途中結果記憶手段は、前記P個のチェックノードの演算の他の一部と、前記P個のバリアブルノードの演算を行う時に読み出される枝に対応する前記第２の復号途中結果を、検査行列の１を列方向に詰めるように格納する
ことを特徴とする復号装置。
【請求項３２】
請求項３０に記載の復号装置であって、
前記第２の復号途中結果記憶手段は、２個のシングルポートRAM(Random Access Memory)である
ことを特徴とする復号装置。
【請求項３３】
請求項３２に記載の復号装置であって、
前記２個のシングルポートRAMは、前記第２の復号途中結果を前記検査行列のＰ列の枝に対応する前記第２の復号途中結果ずつ交互に格納する
ことを特徴とする復号装置。
【請求項３４】
請求項３２に記載の復号装置であって、
前記２個のシングルポートRAM(Random Access Memory)は、それぞれ同一のアドレスに格納している前記第２の復号途中結果を読み出す
ことを特徴とする復号装置。
【請求項３５】
請求項３０に記載の復号装置であって、
前記第２の復号途中結果記憶手段は、前記検査行列を表す構成行列のうちの、重みが２以上の構成行列について、その構成行列を、重みが１の単位行列、準単位行列、またはシフト行列の和の形で表現したときの、その重みが１の単位行列、準単位行列、またはシフト行列に属するP個の枝に対応する前記第２の復号途中結果を、同一のアドレスに格納する
ことを特徴とする復号装置。
【請求項３６】
請求項２７に記載の復号装置であって、
LDPC符号の受信情報を格納するとともに、P個の前記受信情報を同時に読み出す受信情報記憶手段をさらに備える
ことを特徴とする復号装置。
【請求項３７】
請求項３６に記載の復号装置であって、
前記受信情報記憶手段は、前記受信情報を、前記P個のチェックノードの演算の他の一部と、前記P個のバリアブルノードの演算に必要となる順番に読み出すことができるように格納する
ことを特徴とする復号装置。
【請求項３８】
請求項２７に記載の復号装置であって、
前記第１の演算手段が前記P個のチェックノードの演算の一部を行うことにより得られる第１の復号途中結果、または前記第２の演算が前記P個のチェックノードの演算の他の一部と、前記P個のバリアブルノードの演算を行うことにより得られる第２の復号途中結果を並べ替える並べ替え手段をさらに備える
ことを特徴とする復号装置。
【請求項３９】
請求項３８に記載の復号装置であって、
前記並べ替え手段は、バレルシフタで構成される
ことを特徴とする復号装置。
【請求項４０】
LDPC(Low Density Parity Check)符号の復号装置の復号方法であって、
P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、前記LDPC符号の検査行列が、複数の前記構成行列の組合せで表される場合において、
前記LDPC符号の復号のためのP個のチェックノードの演算を同時に行う第１の演算ステップと、
前記LDPC符号の復号のためのP個のバリアブルノードの演算を同時に行う第２の演算ステップと
を含むことを特徴とする復号方法。
【請求項４１】
LDPC(Low Density Parity Check)符号の復号をコンピュータに行わせるプログラムであって、
前記LDPC符号の復号のためのP個のチェックノードの演算を同時に行う第１の演算ステップと、
前記LDPC符号の復号のための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", Submitted to IEEE Trans. Inf. Theory, IT-45, pp. 399-431, 1999」や、「M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi and D. A. Spielman, "Analysis of low density codes and improved designs using irregular graphs", in Proceedings of ACM Symposium on Theory of Computing, pp. 249-258, 1998」等において再注目されるに至ったものである。
【０００５】
LDPC符号は、近年の研究により、ターボ符号等と同様に、符号長を長くしていくにしたがって、シャノン限界に近い性能が得られることがわかりつつある。また、LDPC符号は、最小距離が符号長に比例するという性質があることから、その特徴として、ブロック誤り確率特性がよく、さらに、ターボ符号等の復号特性において観測される、いわゆるエラーフロア現象が殆ど生じないことも利点として挙げられる。
【０００６】
以下、このようなLDPC符号について具体的に説明する。なお、LDPC符号は、線形符号であり、必ずしも２元である必要はないが、ここでは、２元であるものとして説明する。
【０００７】
LDPC符号は、そのLDPC符号を定義する検査行列(parity check matrix)が疎なものであることを最大の特徴とするものである。ここで、疎な行列とは、行列のコンポーネントの"1"の個数が非常に少なく構成されるものであり、疎な検査行列をHで表すものとすると、そのような検査行列としては、例えば、図１に示すように、各列のハミング重み（"1"の数）(weight)が"3"であり、且つ、各行のハミング重みが"6"であるもの等がある。
【０００８】
このように、各行及び各列のハミング重みが一定である検査行列Hによって定義されるLDPC符号は、レギュラーLDPC符号と称される。一方、各行及び各列のハミング重みが一定でない検査行列Hによって定義されるLDPC符号は、イレギュラーLDPC符号と称される。
【０００９】
このようなLDPC符号による符号化は、検査行列Hに基づいて生成行列Gを生成し、この生成行列Gを２元の情報メッセージに対して乗算することによって符号語を生成することで実現される。具体的には、LDPC符号による符号化を行う符号化装置は、まず、検査行列Hの転置行列HTとの間に、式GHT=0が成立する生成行列Gを算出する。ここで、生成行列Gが、k×n行列である場合には、符号化装置は、生成行列Gに対してkビットからなる情報メッセージ（ベクトルu）を乗算し、nビットからなる符号語ｃ（＝uＧ）を生成する。この符号化装置によって生成された符号語は、値が"0"の符号ビットが"+1"に、値が"1"の符号ビットが"−1"にといったようにマッピングされて送信され、所定の通信路を介して受信側において受信されることになる。
【００１０】
一方、LDPC符号の復号は、Gallagerが確率復号(Probabilistic Decoding)と称して提案したアルゴリズムであって、バリアブルノード(variable node（メッセージノード(message node)とも呼ばれる。）)と、チェックノード(check node)とからなる、いわゆるタナーグラフ(Tanner graph)上での確率伝播(belief propagation)によるメッセージ・パッシング・アルゴリズムによって行うことが可能である。ここで、以下、適宜、バリアブルノードとチェックノードを、単に、ノードともいう。
【００１１】
しかしながら、確率復号においては、各ノード間で受け渡されるメッセージが実数値であることから、解析的に解くためには、連続した値をとるメッセージの確率分布そのものを追跡する必要があり、非常に困難を伴う解析を必要とすることになる。そこで、Gallagerは、LDPC符号の復号アルゴリズムとして、アルゴリズムＡ又はアルゴリズムＢを提案している。
【００１２】
LDPC符号の復号は、一般的には、図２に示すような手順にしたがって行われる。なお、ここでは、受信値をU0(u0i)とし、チェックノードから出力されるメッセージをujとし、バリアブルノードから出力されるメッセージをviとする。また、ここでは、メッセージとは、値の"0"らしさを、いわゆる対数尤度比(log likelihood ratio)で表現した実数値である。
【００１３】
まず、LDPC符号の復号においては、図２に示すように、ステップＳ１１において、受信値U0(u0i)が受信され、メッセージujが"0"に初期化されるとともに、繰り返し処理のカウンタとしての整数をとる変数kが"0"に初期化され、ステップＳ１２に進む。ステップＳ１２において、受信値U0(u0i)に基づいて、式（１）に示す演算を行うことによってメッセージviが求められ、さらに、このメッセージviに基づいて、式（２）に示す演算を行うことによってメッセージujが求められる。
【００１４】
【数１】
2004364233.tif 000003
・・・（１）
【００１５】
【数２】
2004364233.tif 000004
・・・（２）
【００１６】
ここで、式（１）と式（２）におけるdvとdcは、それぞれ、検査行列Hの縦方向（行方向）と横方向（列方向）の"1"の個数を示す任意に選択可能とされるパラメータであり、例えば、(3,6)符号の場合には、dv=3，dc=6となる。
【００１７】
なお、式（１）または（２）の演算においては、それぞれ、メッセージを出力しようとする枝(edge)から入力されたメッセージを、和または積演算のパラメータとしては用いないことから、和または積演算の範囲が、１乃至dv-1または１乃至dc-1となっている。また、式（２）に示す演算は、実際には、２入力v1，v2に対する１出力で定義される式（３）に示す関数R(v1,v2)のテーブルを予め作成しておき、これを式（４）に示すように連続的（再帰的）に用いることによって行われる。
【００１８】
【数３】
2004364233.tif 000005
・・・（３）
【００１９】
【数４】
2004364233.tif 000006
・・・（４）
【００２０】
ステップＳ１２では、さらに、変数kが"1"だけインクリメントされ、ステップＳ１３に進む。ステップＳ１３では、変数kが所定の繰り返し復号回数N以上であるか否かが判定される。ステップＳ１３において、変数kがN以上ではないと判定された場合、ステップＳ１２に戻り、以下、同様の処理が繰り返される。
【００２１】
また、ステップＳ１３において、変数kがN以上であると判定された場合、ステップＳ１４に進み、式（５）に示す演算を行うことによって最終的に出力する復号結果としてのメッセージvが求められて出力され、LDPC符号の復号処理が終了する。
【００２２】
【数５】
2004364233.tif 000007
・・・（５）
【００２３】
ここで、式（５）の演算は、式（１）の演算とは異なり、バリアブルノードに接続している全ての枝からの入力メッセージを用いて行われる。
【００２４】
このようなLDPC符号の復号は、例えば(3,6)符号の場合には、図３に示すように、各ノード間でメッセージの授受が行われる。なお、図３における"="で示すノード（バリアブルノード）では、式（１）に示した演算が行われ、"+"で示すノード（チェックノード）では、式（２）に示した演算が行われる。特に、アルゴリズムＡにおいては、メッセージを２元化し、"+"で示すノードにて、dc-1個の入力メッセージの排他的論理和演算を行い、"="で示すノードにて、受信値Rに対して、dv-1個の入力メッセージが全て異なるビット値であった場合には、符号を反転して出力する。
【００２５】
また、一方で、近年、LDPC符号の復号の実装法に関する研究も行われている。実装方法について述べる前に、まず、LDPC符号の復号を摸式化して説明する。
【００２６】
図４は、(3,6)LDPC符号（符号化率1/2、符号長12）の検査行列(parity check matrix)の例である。LDPC符号の検査行列は、図５のように、タナーグラフを用いて書き表すことができる。ここで、図５において、"+"で表わされるのが、チェックノードであり、"="で表わされるのが、バリアブルノードである。チェックノードとバリアブルノードは、それぞれ、検査行列の行と列に対応する。チェックノードとバリアブルノードとの間の結線は、枝(edge)であり、検査行列の"1"に相当する。即ち、検査行列の第ｊ行第ｉ列のコンポーネントが１である場合には、図５において、上からｉ番目のバリアブルノード（"="のノード）と、上からｊ番目のチェックノード（"+"のノード）とが、枝により接続される。枝は、バリアブルノードに対応する符号ビットが、チェックノードに対応する拘束条件を持つことを表わす。なお、図５は、図４の検査行列のタナーグラフとなっている。
【００２７】
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である。
【００３０】
【数６】
2004364233.tif 000008
・・・（６）
【００３１】
更に、x≧0において、φ(x)=ln(tanh(x/2))と定義すると、φ-1(x)=2tanh-1(e-x)であるから、式（６）は、式（７）のように書くことができる。
【００３２】
【数７】
2004364233.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となる。
【００３５】
サムプロダクトアルゴリズムをハードウェアに実装する場合、式（１）で表わされるバリアブルノード演算および式（７）で表わされるチェックノード演算とを、適度な回路規模と動作周波数で繰り返し行うことが必要である。
【００３６】
復号装置の実装の例として、まず、単純に各ノードの演算を一つずつ順次行うことによって復号を行う場合(full serial decoding)の実装法について説明する。
【００３７】
なお、ここでは、例えば、図８の、３０（行）×９０（列）の検査行列で表現される符号（符号化率2/3、符号長90）を復号することとする。図８の検査行列の１の数は２６９であり、従って、そのタナーグラフでは、枝の数は２６９個となる。ここで、図８の検査行列では、０を、"."で表現している。
【００３８】
図９は、LDPC符号の１回復号を行う復号装置の構成例を示している。
【００３９】
図９の復号装置では、その動作する１クロック(clock)ごとに、１つの枝に対応するメッセージが計算される。
【００４０】
即ち、図９の復号装置は、２つの枝用メモリ１００および１０２、１つのチェックノード計算器１０１、１つのバリアブルノード計算器１０３、１つの受信用メモリ１０４、１つの制御部１０５からなる。
【００４１】
図９の復号装置では、枝用メモリ１００または１０２からメッセージデータが１つずつ読み出され、そのメッセージデータを用いて、所望の枝に対応するメッセージデータが計算される。そして、その計算によって求められたメッセージデータが１つずつ後段の枝用メモリ１０２または１００に格納されていく。繰り返し復号を行う際には、この１回復号を行う図９の復号装置を複数個縦列に連接するか、もしくは図９の復号装置を繰り返し用いることによって、繰り返し復号を実現する。なお、ここでは、例えば、図９の復号装置が複数個接続されているものとする。
【００４２】
枝用メモリ１００は、前段の復号装置（図示せず）のバリアブルノード計算器１０３から供給されるメッセージD100を、後段のチェックノード計算器１０１が読み出す順番に格納していく。そして、枝用メモリ１００は、チェックノード計算のフェーズでは、メッセージD100を、格納してある順番通りに、メッセージD101として、チェックノード計算器１０１に供給する。
【００４３】
チェックノード計算器１０１は、制御部１０５から供給される制御信号D106に基づき、枝用メモリ１００から供給されるメッセージD101を用いて、式（７）に従って演算を行い、その演算によって求められたメッセージD102を、後段の枝用メモリ１０２に供給する。
【００４４】
枝用メモリ１０２は、前段のチェックノード計算器１０１から供給されるメッセージD102を、後段のバリアブルノード計算器１０３が読み出す順番に格納していく。そして、枝用メモリ１０２は、バリアブルノード計算のフェーズでは、メッセージD102を、格納してある順番通りに、メッセージD103として、バリアブルノード計算器１０３に供給する。
【００４５】
さらに、バリアブルノード計算器１０３には、制御部１０５から制御信号D107が供給されるとともに、受信用メモリ１０４から受信データD104が供給される。バリアブルノード計算器１０３は、制御信号D107に基づき、枝用メモリ１００から供給されるメッセージD103と受信用メモリ１００から供給される受信データD104を用い、式（１）に従って演算を行い、その演算の結果得られるメッセージD105を、図示せぬ後段の復号装置の枝用メモリ１００に供給する。
【００４６】
受信用メモリ１０４には、LDPC符号化された受信データ（LDPC符号）が格納される。制御部１０５は、バリアブルノード演算を制御する制御信号D106と、チェックノード演算を制御する制御信号D107を、それぞれチェックノード計算器１０１とバリアブルノード計算器１０３に供給する。制御部１０５は、枝用メモリ１００に全ての枝のメッセージが格納されたとき、チェックノード計算器１０１に制御信号D106を供給し、枝用メモリ１０２に全ての枝のメッセーが格納されたとき、バリアブルノード計算器１０３に制御信号D107を供給する。
【００４７】
図１０は、チェックノード演算を１つずつ行う図９のチェックノード計算器１０１の構成例を示している。
【００４８】
なお、図１０では、各メッセージが符号ビットを合わせて合計６ビット(bit)に量子化されているものとして、チェックノード計算器１０１を表している。また、図１０では、図８の検査行列で表わされるLDPC符号のチェックノード演算が行われる。さらに、図１０のチェックノード演算器１０１には、クロックｃｋが供給され、このクロックｃｋは、必要なブロックに供給されるようになっている。そして、各ブロックは、クロックｃｋに同期して処理を行う。
【００４９】
図１０のチェックノード計算器１０１は、制御部１０５から供給される、例えば、1ビットの制御信号D106に基づき、枝用メモリ１００から１つずつ読み込まれるメッセージD101を用いて、式（７）にしたがって演算を行う。
【００５０】
即ち、チェックノード計算器１０１では、検査行列の各列に対応するバリアブルノードからの６ビットのメッセージD101（メッセージvi）が１つずつ読み込まれ、その下位ビットである絶対値D122(|vi|)がLUT１２１に、その最上位ビットである符号ビットD121がEXOR回路１２９とFIFO(First In First Out)メモリ１３３にそれぞれ供給される。また、チェックノード計算器１０１には、制御部１０５から制御信号D106が供給され、その制御信号D106は、セレクタ１２４とセレクタ１３１に供給される。
【００５１】
LUT１２１は、絶対値D122(|vi|)に対して、式（７）におけるφ(|vi|)の演算を行った５ビットの演算結果D123（φ(|vi|)）を読み出し、加算器１２２とFIFOメモリ１２７に供給する。
【００５２】
加算器１２２は、演算結果D123（φ(|vi|)）とレジスタ１２３に格納されている９ビットの値D124とを加算することにより、演算結果D123を積算し、その結果得られる９ビットの積算値をレジスタ１２３に再格納する。なお、検査行列の1行に亘る全ての枝からのメッセージD101の絶対値D122(|vi|)に対する演算結果が積算された場合、レジスタ１２３はリセットされる。
【００５３】
検査行列の1行に亘るメッセージD101が１つずつ読み込まれ、レジスタ１２３に1行分の演算結果D123が積算された積算値が格納された場合、制御部１０５から供給される制御信号D106は、０から１に変化する。例えば、行の重み（row weight）が「９」である場合、制御信号D106は、１から８クロック目までは、「０」となり、９クロック目では「１」となる。
【００５４】
制御信号D106が「１」の場合、セレクタ１２４は、レジスタ１２３に格納されている値、即ち、検査行列の１行に亘る全ての枝からのメッセージD101（メッセージvi）から求められたφ(|vi|)が積算された９ビットの値D124（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）を選択し、値D125として、レジスタ１２５に出力して格納させる。レジスタ１２５は、格納している値D125を、９ビットの値D126として、セレクタ１２４と加算器１２６に供給する。制御信号D106が「０」の場合、セレクタ１２４は、レジスタ１２５から供給された値D126を選択し、レジスタ１２５に出力して再格納させる。即ち、検査行列の１行に亘る全ての枝からのメッセージD101（メッセージvi）から求められたφ(|vi|)が積算されるまで、レジスタ１２５は、前回積算されたφ(|vi|)を、セレクタ１２４と加算器１２６に供給する。
【００５５】
一方、FIFOメモリ１２７は、レジスタ１２５から新たな値D126（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）が出力されるまでの間、LUT１２１が出力した演算結果D123（φ(|vi|)）を遅延し、５ビットの値D127として減算器１２６に供給する。減算器１２６は、レジスタ１２５から供給された値D126から、FIFOメモリ１２７から供給された値D127を減算し、その減算結果を、５ビットの減算値D128としてLUT１２８に供給する。即ち、減算器１２６は、検査行列の1行に亘る全ての枝からのメッセージD101（メッセージvi）から求められたφ(|vi|)の積算値から、求めたい枝からのメッセージD101（メッセージvi）から求められたφ(|vi|)を減算して、その減算値（ｉ＝１からｉ＝ｄc−１までのΣφ(|vi|)）を減算値D128としてLUT１２８に供給する。
【００５６】
LUT１２８は、減算値D128（ｉ＝１からｉ＝ｄc−１までのΣφ(|vi|)）に対して、式（７）におけるφ-1（Σφ(|vi|)）の演算を行った５ビットの演算結果D129（φ-1(Σφ(|vi|)))を出力する。
【００５７】
以上の処理と並行して、EXOR回路１２９は、レジスタ１３０に格納されている１ビットの値D131と符号ビットD121との排他的論理和を演算することにより、符号ビットどうしの乗算を行い、１ビットの乗算結果D130をレジスタ１３０に再格納する。なお、検査行列の1行に亘る全ての枝からのメッセージD101の符号ビットD121が乗算された場合、レジスタ１３０はリセットされる。
【００５８】
検査行列の1行に亘る全ての枝からのメッセージD101の符号ビットD121が乗算された乗算結果D130（ｉ＝１からｄcまでのΠsign(vi)）がレジスタ１３０に格納された場合、制御部１０５から供給される制御信号D106は、「０」から「１」に変化する。
【００５９】
制御信号D106が「１」の場合、セレクタ１３１は、レジスタ１３０に格納されている値、即ち、検査行列の１行に亘る全ての枝からのメッセージD101の符号ビットD121が乗算された値D131（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）を選択し、１ビットの値D132としてレジスタ１３２に出力して格納させる。レジスタ１３２は、格納している値D132を、１ビットの値D133としてセレクタ１３１とEXOR回路１３４に供給する。制御信号D106が「０」の場合、セレクタ１３１は、レジスタ１３２から供給された値D133を選択し、レジスタ１３２に出力して再格納させる。即ち、検査行列の１行に亘る全ての枝からのメッセージD101（メッセージvi）の符号ビットD121が乗算されるまで、レジスタ１３２は、前回格納した値を、セレクタ１３１とEXOR回路１３４に供給する。
【００６０】
一方、FIFOメモリ１３３は、レジスタ１３２から新たな値D133（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）がEXOR回路１３４に供給されるまでの間、符号ビットD121を遅延し、１ビットの値D134としてEXOR回路１３４に供給する。EXOR回路１３４は、レジスタ１３２から供給された値D133と、FIFOメモリ１３３から供給された値D134との排他的論理和を演算することにより、値D133を、値D134で除算し、１ビットの除算結果を除算値D135として出力する。即ち、EXOR回路１３４は、検査行列の１行に亘る全ての枝からのメッセージD101の符号ビットD121（sign(|vi|)）の乗算値を、求めたい枝からのメッセージD101の符号ビットD121（sign(|vi|)）で除算して、その除算値（ｉ＝１からｉ＝ｄc−１までのΠsign(|vi|)）を除算値D135として出力する。
【００６１】
チェックノード計算器１０１では、LUT１２８から出力された５ビットの演算結果D129を下位５ビットとするとともに、EXOR回路１３４から出力された１ビットの除算値D135を最上位ビットとする合計６ビットがメッセージD102（メッセージuj）として出力される。
【００６２】
以上のように、チェックノード計算器１０１では、式（７）の演算が行われ、メッセージujが求められる。
【００６３】
なお、図８の検査行列の行の重みの最大は９であるため、即ち、チェックノードに供給されるメッセージの最大数は９であるため、チェックノード計算器１０１は、９個のメッセージ（φ(|vi|)）を遅延させるFIFOメモリ１２７とFIFOメモリ１３３を有している。行の重みが９未満の行のメッセージを計算するときには、FIFOメモリ１２７とFIFOメモリ１３３における遅延量が、その行の重みの値に減らされる。
【００６４】
図１１は、バリアブルノード演算を１つずつ行う図９のバリアブルノード計算器１０３の構成例を示している。
【００６５】
なお、図１１では、各メッセージが符号ビットを合わせて合計６ビット(bit)に量子化されているものとして、バリアブルノード計算器１０３を表している。また、図１１では、図８の検査行列で表わされるLDPC符号のバリアブルノード演算が行われる。さらに、図１１のバリアブルノード計算機１０３には、クロックｃｋが供給され、クロックｃｋは、必要なブロックに供給されるようになっている。そして、各ブロックは、クロックｃｋに同期して処理を行う。
【００６６】
図１１のバリアブルノード計算器１０３は、制御部１０５から供給される、例えば、１ビットの制御信号D107に基づき、枝用メモリ１０２から１つずつ読み込まれるメッセージD103と、受信用メモリ１０４から読み込まれる受信データD104を用いて、式（１）にしたがって演算を行う。
【００６７】
即ち、バリアブルノード計算器１０３では、検査行列の各行に対応するチェックノードからの６ビットのメッセージD103（メッセージuj）が１つずつ読み込まれ、そのメッセージD103が、加算器１５１とFIFOメモリ１５５に供給される。また、バリアブルノード計算器１０３では、受信用メモリ１０４から６ビットの受信データD104が1つずつ読み込まれ、加算器１５６に供給される。さらに、バリアブルノード計算器１０３には、制御部１０５から制御信号D107が供給され、その制御信号D107は、セレクタ１５３に供給される。
【００６８】
加算器１５１は、メッセージD103（メッセージuj）とレジスタ１５２に格納されている９ビットの値D151とを加算することにより、メッセージD103を積算し、その結果得られる９ビットの積算値を、レジスタ１５２に再格納する。なお、検査行列の1列に亘る全ての枝からのメッセージD103が積算された場合、レジスタ１５２はリセットされる。
【００６９】
検査行列の1列に亘るメッセージD103が１つずつ読み込まれ、レジスタ１５２に1列分のメッセージD103が積算された値が格納された場合、制御部１０５から供給される制御信号D107は、「０」から「１」に変化する。例えば、列の重みが「５」である場合、制御信号D107は、１から４クロック目までは「０」となり、５クロック目では「１」となる。
【００７０】
制御信号D107が「１」の場合、セレクタ１５３は、レジスタ１５２に格納されている値、即ち、検査行列の１列に亘る全ての枝からのメッセージD103（メッセージuj）が積算された９ビットの値D151（ｊ＝１からｄVまでのΣuj)を選択し、レジスタ１５４に出力して格納させる。レジスタ１５４は、格納している値D151を、９ビットの値D152として、セレクタ１５３と加減算器１５６に供給する。制御信号D107が「０」の場合、セレクタ１５３は、レジスタ１５４から供給された値D152を選択し、レジスタ１５４に出力し再格納させる。即ち、検査行列の１列に亘る全ての枝からのメッセージD103（メッセージuj）が積算されるまで、レジスタ１５４は、前回積算された値を、セレクタ１５３と加減算器１５６に供給する。
【００７１】
一方、FIFOメモリ１５５は、レジスタ１５４から新たな値D152（ｊ＝１からｄVまでのΣuj)が出力されるまでの間、チェックノードからのメッセージD103を遅延し、６ビットの値D153として加減算器１５６に供給する。加減算器１５６は、レジスタ１５４から供給された値D152から、FIFOメモリ１５５から供給された値D153を減算する。即ち、加減算器１５６は、検査行列の1列に亘る全ての枝からのメッセージD103（メッセージuj）の積算値から、求めたい枝からのメッセージujを減算して、その減算値（ｊ＝１からｄv−１までのΣuj）を求める。さらに、加減算器１５６には、その減算値（ｊ＝１からｄv−１までのΣuj）に、受信用メモリ１０４から供給された受信データD104を加算して、その結果得られる６ビットの値をメッセージD105（メッセージvi）として出力する。
【００７２】
以上のように、バリアブルノード計算器１０３では、式（１）の演算が行われ、メッセージviが求められる。
【００７３】
なお、図８の検査行列の列の重みの最大は５であるため、即ち、バリアブルノードに供給されるメッセージの最大数は５であるため、バリアブルノード計算器１０３は、５個のメッセージ（uj）を遅延させるFIFOメモリ１５５を有している。列の重みが５未満の列のメッセージを計算するときには、FIFOメモリ１５５における遅延量が、その列の重みの値に減らされる。
【００７４】
図９の復号装置では、検査行列の重みにしたがって、制御部１０５から制御信号が与えられる。そして、図９の復号装置によれば、枝用メモリ１００および１０２、並びにチェックノード計算器１０１およびバリアブルノード計算器１０３のFIFOメモリ１２７，１３３，１５５の容量さえ足りれば、制御信号のみを変えることで様々な検査行列のLDPC符号を復号することができる。
【００７５】
なお、図示しないが、図９の復号装置において、復号の最終段においては、式（１）のバリアブルノード演算の代わりに、式（５）の演算が行われ、その演算結果が、最終的な復号結果として出力される。
【００７６】
図９の復号装置を繰り返し用いて、LDPC符号を復号する場合には、チェックノード演算とバリアブルノード演算とが交互に行われる。即ち、図９の復号装置では、チェックノード計算器１０１によるチェックノード演算の結果を用いて、バリアブルノード計算器１０３によりバリアブルノード演算が行われ、バリアブルノード計算器１０３によるバリアブルノード演算の結果を用いて、チェックノード計算器１０１によりチェックノード演算が行われる。
【００７７】
従って、２６９の枝を有する図８の検査行列を用いた１回の復号に、269×2=538クロック(clock)を必要とする。例えば、５０回の繰り返し復号を行うためには、符号長である９０個の符号（受信データ）を1フレームとして、その1フレームを受信する間に、538×50=26900クロック動作することが必要であり、受信周波数の約３００（≒26900/90）倍の高速動作が必要になる。受信周波数が数十MHzであるとすると、GHz以上の速度での動作を要求されることになる
【００７８】
また、図９の復号装置を、例えば、５０台連接して、LDPC符号を復号する場合には、１フレーム(frame)目のバリアブルノード演算を行っている間に、２フレーム目のチェックノード演算を行い、３フレーム目のバリアブルノード演算を行う、というように、複数のバリアブルノード演算とチェックノード演算とを同時に行うことができる。この場合、９０個の符号を受信する間に、２６９個の枝を計算すればよいので、復号装置は、受信周波数の約３（≒269/90）倍の周波数で動作すればよいことになり、十分に実現可能である。しかしながら、この場合、回路規模が、単純には、図９の復号装置の５０倍になる。
【００７９】
次に、全ノードの演算を同時に行うことによって復号を行う場合(full parallel decoding)の復号装置の実装法について説明する。
【００８０】
この実装法については、例えば、非特許文献１に記載されている。
【００８１】
図１２は、図８の検査行列で表現される符号（符号化率2/3、符号長90）を復号する復号装置の一例の構成を示している。
【００８２】
図１２の復号装置では、枝用メモリ２０２または２０６から、２６９個ある枝に対応するメッセージデータを全て同時に読み出し、そのメッセージデータを用いて、２６９個の枝に対応する新たなメッセージデータを演算する。さらに、その演算の結果求められた新たなメッセージデータが全て同時に後段の枝用メモリ２０６または２０２に格納されていく。そして、図１２の復号装置を繰り返し用いることで繰り返し復号が実現される。
【００８３】
図１２において、復号装置は、１つの受信用メモリ２０５、２つの枝入れ替え装置２００および２０３、２つの枝用メモリ２０２および２０６、３０個のチェックノード計算器２０１1乃至２０１30、９０個のバリアブルノード計算器２０４1乃至２０４90からなる。以下、各部について詳細に説明する。
【００８４】
枝用メモリ２０６は、前段のバリアブルノード計算器２０４1乃至２０４90からのメッセージD2061乃至D20690を全て同時に格納し、次の時刻（次のクロックのタイミング）に、メッセージD2061乃至D20690を、メッセージD2071乃至D20790として読み出し、次段の枝入れ替え装置２００に、メッセージD200(D2001乃至D20090)として供給する。枝入れ替え装置２００は、枝用メモリ２０６から供給されたメッセージD2001乃至D20090の順番を、図８の検査行列にしたがって並び替え（入れ替え）、チェックノード計算器２０１1乃至２０１30に、メッセージD2011乃至D20130として供給する。
【００８５】
チェックノード計算器２０１1乃至２０１30は、枝入れ替え装置２００から供給されるメッセージD2011乃至D20130を用いて式（７）にしたがって演算を行い、その演算の結果得られるメッセージD2021乃至D20230を、枝用メモリ２０２に供給する。
【００８６】
枝用メモリ２０２は、前段のチェックノード計算器２０１1乃至２０１30から供給されるメッセージD2021乃至D20230を全て同時に格納し、次の時刻に、そのすべてのメッセージD2021乃至D20230を、メッセージD2031乃至D20330として、次段の枝入れ替え装置２０３に供給する。
【００８７】
枝入れ替え装置２０３は、枝用メモリ２０２から供給されたメッセージD2031乃至D20330の順番を図８の検査行列にしたがって並び替え、バリアブルノード計算器２０４1乃至２０４90に、メッセージD2041乃至D20490として供給する。
【００８８】
バリアブルノード計算器２０４1乃至２０４90は、枝入れ替え装置２０３から供給されるメッセージD2041乃至D20490と、受信用メモリ２０５から供給される受信データD2051乃至D20590を用いて式（１）にしたがって演算を行い、その演算の結果得られるメッセージD2061乃至D20690を、次段の枝用メモリ２０６に供給する。
【００８９】
図１３は、チェックノード演算を同時に行う図１２のチェックノード計算器２０１m（ｍ＝１，２，・・・，３０）の構成例を示している。
【００９０】
図１３のチェックノード計算器２０１mでは、図１０のチェックノード計算器１０１と同様にして、式（７）のチェックノード演算が行われるが、そのチェックノード演算が、すべての枝について同時に行われる。
【００９１】
即ち、図１３のチェックノード計算器２０１mでは、枝入れ替え装置２００から供給される図８の検査行列の各列に対応するバリアブルノードからのメッセージD2211乃至D2219（vi）が全て同時に読み込まれ、それぞれの下位５ビットである絶対値D2221乃至D2229（|vi|）がLUT２２１1乃至２２１9にそれぞれ供給される。また、メッセージD2211乃至D2219（vi）の最上位ビットである１ビットの符号ビットD2231乃至D2239が、EXOR回路２２６1乃至２２６9にそれぞれ供給されるとともに、EXOR回路２２５に供給される。
【００９２】
LUT２２１1乃至２２１9は、絶対値D2221乃至D2229（|vi|）に対して、式（７）におけるφ(|vi|)の演算を行った５ビットの演算結果D2241乃至D2249（φ（|vi|））をそれぞれ読み出し、それぞれを減算器２２３1乃至２２３9に供給する。また、LUT２２１1乃至２２１9は、演算結果D2241乃至D2249（φ（|vi|））を加算器２２２に供給する。
【００９３】
加算器２２２は、演算結果D2241乃至D2249（φ（|vi|））の値の総和（１行分の演算結果の総和）を演算し、９ビットの演算結果D225（ｉ＝１から９のΣφ（|vi|））を、減算器２２３1乃至２２３9に供給する。減算器２２３1乃至２２３9は、演算結果D225から、演算結果D2241乃至D2249（φ（|vi|））をそれぞれ減算し、５ビットの減算値D2271乃至D2279を、LUT２２４1乃至２２４9に供給する。即ち、減算器２２３1乃至２２３9は、全ての枝からのメッセージviから求められたφ(|vi|)の積算値から、求めたい枝からのメッセージviから求められたφ(|vi|)を減算して、その減算値D2271乃至D2279（ｉ＝１から８までのΣφ(|vi|)）をLUT２２４1乃至２２４9にそれぞれ供給する。LUT２２４1乃至２２４9は、減算値D2271乃至D2279に対して、式（７）におけるφ-1(Σφ(|vi|))の演算を行った５ビットの演算結果D2281乃至D2289を読み出して出力する。
【００９４】
一方、EXOR回路２２５は、全ての符号ビットD2231乃至D2239の排他的論理和を演算することにより、符号ビットD2231乃至D2239の乗算を行い、１ビットの乗算値D226（１行分の符号ビットの乗算値（ｉ＝１から９までのΠsign（vi）））をEXOR回路２２６1乃至２２６9にそれぞれ供給する。EXOR回路２２６1乃至２２６9は、乗算値D226と符号ビットD2231乃至D2239それぞれとの排他的論理を演算することにより、乗算値D226を、符号ビットD2231乃至D2239それぞれで除算した１ビットの除算値D2291乃至D2299（ｉ＝１から８までのΠsign（vi））を求めて出力する。
【００９５】
チェックノード計算器２０１mでは、LUT２２４1乃至２２４9から出力された５ビットの演算結果D2281乃至D2289それぞれを下位５ビットとするとともに、EXOR回路２２６1乃至２２６9から出力された除算値D2291乃至D2299それぞれを最上位ビットとする合計６ビットが、チェックノード演算の結果得られるメッセージD2301乃至D2309として出力される。
【００９６】
以上のように、チェックノード計算器２０１mでは、式（７）の演算が行われ、メッセージujが求められる。
【００９７】
なお、図１３では、各メッセージが符号ビットを合わせて合計６ビットに量子化されているものとして、チェックノード計算器２０１mを表している。また、図１３の回路は１つのチェックノードに相当する。ここで処理の対象としている図８の検査行列については、その行数である３０行のチェックノードが存在するため、図１２の復号装置は、図１３に示したようなチェックノード計算器２０１mを３０個有している。
【００９８】
ここで、図１３のチェックノード計算器２０１mでは、９個のメッセージを同時に計算することができる。そして、ここで処理の対象としている図８の検査行列の行の重みは、第１行が８で、第２乃至第３０行が９であるため、即ち、チェックノードに供給されるメッセージの数が、８のケースが１つと、９のケースが２９あるため、チェックノード計算器２０１1は、図１３の回路と同様の８つのメッセージを同時に計算することができる回路構成となっており、残りのチェックノード計算器２０１2乃至２０１30は、図１３の回路と同一構成となっている。
【００９９】
図１４は、バリアブルノード演算を同時に行う図１２のバリアブルノード計算器２０４p（ｐ＝１，２，・・・，９０）の構成例を示している。
【０１００】
図１４のバリアブルノード計算器２０４pでは、図１１のバリアブルノード計算器１０３と同様にして、式（１）のバリアブルノード演算が行われるが、そのバリアブルノード演算が、すべての枝について同時に行われる。
【０１０１】
即ち、図１４のバリアブルノード計算器２０４pでは、枝入れ替え装置２０３から供給される、検査行列の各行に対応するチェックノードからの６ビットのメッセージD2511乃至D2515（メッセージuj）が全て同時に読み込まれ、それぞれ加算器２５２1乃至２５２5に供給されるとともに、加算器２５１に供給される。また、バリアブルノード計算器２０４pには、受信用メモリ２０５から受信データD271が供給され、その受信データD271は、加減算器２５２1乃至２５２5に供給される。
【０１０２】
加算器２５１は、全てのメッセージD2511乃至D2515（メッセージuj）を積算し、９ビットの積算値D252（1列分のメッセージの総和値（ｊ＝１から５までのΣuj））を加減算器２５２1乃至２５２5に供給する。加減算器２５２1乃至２５２5は、加算値D252から、メッセージD2511乃至D2515（メッセージuj）をそれぞれ減算する。即ち、加減算器２５２1乃至２５２5は、全ての枝からのメッセージujの積算値D252から、求めたい枝からのメッセージD2511乃至D2515（メッセージuj）をそれぞれ減算して、その減算値（ｊ＝１から４までのΣuj）を求める。
【０１０３】
さらに、加減算器２５２1乃至２５２5は、減算値（ｊ＝１から４までのΣuj）に、受信データD271（u0i）を加算して、６ビットの加算値D2531乃至D2535を、バリアブルノード演算の結果として出力する。
【０１０４】
以上のように、バリアブルノード計算器２０４pでは、式（１）の演算が行われ、メッセージviが求められる。
【０１０５】
なお、図１４では、各メッセージが符号ビットを合わせて合計６ビットに量子化されているものとして、バリアブルノード計算器２０４pを表している。また、図１４の回路は１つのバリアブルノードに相当する。ここで処理の対象としている図８の検査行列については、その列数である９０列のバリアブルノードが存在するから、図１２の復号装置は、図１４に示したような回路を９０個有している。
【０１０６】
ここで、図１４のバリアブルノード計算器２０４pでは、５個のメッセージを同時に計算することができる。そして、ここで処理の対象としている図８の検査行列は、重みが５，３，２，１の列が、それぞれ、１５列、４５列、２９列、１列あるので、バリアブルノード計算器２０４1乃至２０４90のうちの１５個は、図１４の回路と同一構成となっており、残りの４５個、２９個、１個は、図１４の回路と同様の３，２，１つのメッセージをそれぞれ同時に計算することができる回路構成となっている。
【０１０７】
なお、図示しないが、図１２の復号装置においても、図９における場合と同様に、復号の最終段においては、式（１）のバリアブルノード演算の代わりに、式（５）の演算が行われ、その演算結果が最終的な復号結果として出力される。
【０１０８】
図１２の復号装置によれば、２６９個ある枝に対応するメッセージすべてを１クロックで同時に計算することができる。
【０１０９】
図１２の復号装置を繰り返し用いて復号する場合には、チェックノード演算とバリアブルノード演算とを交互に行い、１回の復号を２クロックで行うことができる。従って、例えば、５０回の復号を行うためには、符号長が９０個の符号を1フレームとする受信データを受信する間に2×50=100クロック動作すれば良いことになり、ほぼ受信周波数と同一の動作周波数でよいことになる。一般的に、LDPC符号は、符号長が数千から数万と大きいことから、図１２の復号装置を用いれば、復号回数を極めて多くすることができ、誤り訂正性能の向上を期待することができる。
【０１１０】
しかしながら、図１２の復号装置は、タナーグラフのすべての枝に対応するメッセージの演算を、並列で行うため、回路規模が、符号長に比例して大きくなる。また、図１２の復号装置を、ある符号長の、ある符号化率の、ある検査行列を持つLDPC符号の復号を行う装置として構成した場合、その復号装置において、他の符号長や、他の符号化率、他の検査行列を持つLDPC符号の復号を行うことは困難となる。即ち、図１２の復号装置は、図９の復号装置のように、制御信号を変えるだけでは、様々な符号を復号することに対処することが困難であり、符号依存性が高い。
【０１１１】
図９および図１２の復号装置の他に、一つでも全てでもなく、４つずつのメッセージの計算を同時に行う実装法について、例えば、非特許文献２に述べられているが、この場合、メモリの異なるアドレスからの同時読み出し、もしくは同時書き込みを避けることが一般的には容易でなく、メモリアクセス制御が困難であるという問題がある。
【０１１２】
また、サムプロダクトアルゴリズムを近似して実装する方法なども提案されているが、この方法では、性能の劣化を招いてしまう。
【非特許文献１】C. Howland and A. Blanksby, "Parallel Decoding Architectures for Low Density Parity Check Codes", Symposium on Circuits and Systems, 2001
【非特許文献２】E. Yeo, P. Pakzad, B. Nikolic and V. Anantharam, "VLSI Architectures for iterative Decoders in Magnetic Recording Channels", IEEE Transactions on Magnetics, Vol. 37, No. 2, March 2001
【発明の開示】
【発明が解決しようとする課題】
【０１１３】
サムプロダクトアルゴリズムをハードウェアに実装する場合には、上述したように、枝に対応するメッセージの演算（チェックノード演算とビットノード(bit node)計算）を、１つずつシリアル(serial)に行う方法、すべて並列（フルパラレル(full parallel)）に行う方法、幾つかずつ並列（パラレル(parallel)）に行う方法がある。
【０１１４】
しかしながら、枝に対応するメッセージの演算を１つずつ行う方法では、高い動作周波数が必要となる。そこで、スループット(throughput)を上げる方法として、装置を、パイプライン(pipeline)化する方法があるが、この場合、回路規模、特にメモリ（の容量）が大きくなってしまう。
【０１１５】
また、メッセージの演算を全て並列に行う方法では、ロジック(logic)の回路規模が大きくなるとともに、符号依存性が高くなる。
【０１１６】
さらに、メッセージの演算を、幾つかずつ並列に行う方法では、メモリアクセスの制御が難しくなる。
【０１１７】
本発明は、このような状況に鑑みてなされたものであり、ロジック、メモリ共に回路規模を抑制しつつ、動作周波数も十分実現可能な範囲に抑え、メモリアクセスの制御も容易に行うことができるようにするものである。
【課題を解決するための手段】
【０１１８】
本発明の復号装置は、P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、LDPC符号の検査行列が、複数の構成行列の組合せで表される場合において、LDPC符号の復号のためのP個のチェックノードの演算を同時に行う第１の演算手段と、LDPC符号の復号のためのP個のバリアブルノードの演算を同時に行う第２の演算手段とを備えることを特徴とする。
【０１１９】
第１の演算手段は、チェックノードの演算を行うP個のチェックノード計算器を有し、第２の演算手段は、バリアブルノードの演算を行うP個のバリアブルノード計算器を有するようにすることができる。
【０１２０】
P個のチェックノードの演算、またはP個のバリアブルノードの演算の結果得られるP個の枝に対応するメッセージデータを同時に読み書きするメッセージ記憶手段をさらに備えるようにすることができる。
【０１２１】
メッセージ記憶手段は、チェックノードの演算時に読み出される枝に対応するメッセージデータを、検査行列の１を行方向に詰めるように格納するようにすることができる。
【０１２２】
メッセージ記憶手段は、バリアブルノード演算時に読み出される枝に対応するメッセージデータを、検査行列の１を列方向に詰めるように格納するようにすることができる。
【０１２３】
メッセージ記憶手段は、検査行列を表す構成行列のうちの、重みが２以上の構成行列について、その構成行列を、重みが１の単位行列、準単位行列、またはシフト行列の和の形で表現したときの、その重みが１の単位行列、準単位行列、またはシフト行列に属するP個の枝に対応するメッセージを、同一のアドレスに格納するようにすることができる。
【０１２４】
メッセージ記憶手段は、行数／P個のFIFOと、列数／P個のFIFOとで構成され、行数／P個のFIFOと列数／P個のFIFOは、それぞれ、検査行列の行と列の重みに対応するワード数を有するようにすることができる。
【０１２５】
メッセージ記憶手段は、RAM(Random Access Memory)で構成され、RAMは、メッセージデータを、読み出される順番に詰めて格納し、格納位置順に読み出すようにすることができる。
【０１２６】
LDPC符号の受信情報を格納するとともに、P個の受信情報を同時に読み出す受信情報記憶手段をさらに備えるようにすることができる。
【０１２７】
受信情報記憶手段は、受信情報を、バリアブルノードの演算に必要となる順番に読み出すことができるように格納するようにすることができる。
【０１２８】
P個のチェックノードの演算、またはP個のバリアブルノードの演算の結果得られるメッセージを並べ替える並べ替え手段をさらに備えるようにすることができる。
【０１２９】
並べ替え手段は、バレルシフタで構成されるようにすることができる。
【０１３０】
第１の演算手段と第２の演算手段は、P個の枝に対応するメッセージを求めるようにすることができる。
【０１３１】
第１の演算手段は、P個のチェックノードの演算とP個のバリアブルノードの演算の一部とを行い、第２の演算手段は、P個のバリアブルノードの演算の他の一部を行うようにすることができる。
【０１３２】
第１の演算手段は、P個のチェックノードの演算とP個のバリアブルノードの演算の一部を行うP個の計算器を有し、第２の演算手段は、P個のバリアブルノードの演算の他の一部を行うP個の計算器を有するようにすることができる。
【０１３３】
第１の演算手段がP個のチェックノードの演算とP個のバリアブルノードの演算の一部を行うことにより得られるP個の枝に対応する第１の復号途中結果を同時に読み書きする第１の復号途中結果記憶手段をさらに備えるようにすることができる。
【０１３４】
第１の復号途中記憶手段は、P個のバリアブルノードの演算の他の一部を行う時に読み出される枝に対応する第１の復号途中結果を、検査行列の１を行方向に詰めるように格納するようにすることができる。
【０１３５】
第１の復号途中結果記憶手段は、２個のシングルポートRAM(Random Access Memory)であるようにすることができる。
【０１３６】
２個のシングルポートRAMは、第1の復号途中結果をＰ個ずつ交互に格納するようにすることができる。
【０１３７】
２個のシングルポートRAM(Random Access Memory)は、それぞれ同一のアドレスに格納している第１の復号途中結果を読み出すようにすることができる。
【０１３８】
第１の復号途中結果記憶手段は、検査行列を表す構成行列のうちの、重みが２以上の構成行列について、その構成行列を、重みが１の単位行列、準単位行列、またはシフト行列の和の形で表現したときの、その重みが１の単位行列、準単位行列、またはシフト行列に属するP個の枝に対応する第１の復号途中結果を、同一のアドレスに格納するようにすることができる。
【０１３９】
第２の演算手段がP個のバリアブルノードの演算の他の一部を行うことにより得られるP個の枝に対応する第２の復号途中結果を同時に読み書きする第２の復号途中結果記憶手段をさらに備えるようにすることができる。
【０１４０】
LDPC符号の受信情報を格納するとともに、P個の受信情報を同時に読み出す受信情報記憶手段をさらに備えるようにすることができる。
【０１４１】
受信情報記憶手段は、受信情報を、P個のバリアブルノードの演算の他の一部の演算に必要となる順番に読み出すことができるように格納するようにすることができる。
【０１４２】
第１の演算手段がP個のチェックノードの演算とP個のバリアブルノードの演算の一部を行うことにより得られる第１の復号途中結果、または第２の演算手段がP個のバリアブルノードの演算の他の一部を行うことにより得られる第２の復号途中結果を並べ替える並べ替え手段をさらに備えるようにすることができる。
【０１４３】
並べ替え手段は、バレルシフタで構成されるようにすることができる。
【０１４４】
第１の演算手段は、P個のチェックノードの演算の一部を行い、第２の演算手段は、P個のチェックノードの演算の他の一部と、P個のバリアブルノードの演算とを行うようにすることができる。
【０１４５】
第１の演算手段は、P個のチェックノードの演算の一部を行うP個の計算器を有し、第２の演算手段は、P個のチェックノードの演算の他の一部と、P個のバリアブルノードの演算を行うP個の計算器を有することができる。
【０１４６】
第１の演算手段がP個のチェックノードの演算の一部を行うことにより得られるP個の枝に対応する第１の復号途中結果を同時に読み書きする第１の復号途中結果記憶手段をさらに備えるようにすることができる。
【０１４７】
第２の演算手段がP個のチェックノードの演算の他の一部と、P個のバリアブルノードの演算を行うことにより得られるP個の枝に対応する第２の復号途中結果を同時に読み書きする第２の復号途中結果記憶手段をさらに備えるようにすることができる。
【０１４８】
第２の復号途中結果記憶手段は、P個のチェックノードの演算の他の一部と、P個のバリアブルノードの演算を行う時に読み出される枝に対応する第２の復号途中結果を、検査行列の１を列方向に詰めるように格納するようにすることができる。
【０１４９】
第２の復号途中結果記憶手段は、２個のシングルポートRAM(Random Access Memory)であるようにすることができる。
【０１５０】
２個のシングルポートRAMは、第２の復号途中結果をＰ個ずつ交互に格納するようにすることができる。
【０１５１】
２個のシングルポートRAM(Random Access Memory)は、それぞれ同一のアドレスに格納している第２の復号途中結果を読み出すようにすることができる。
【０１５２】
第２の復号途中結果記憶手段は、検査行列を表す構成行列のうちの、重みが２以上の構成行列について、その構成行列を、重みが１の単位行列、準単位行列、またはシフト行列の和の形で表現したときの、その重みが１の単位行列、準単位行列、またはシフト行列に属するP個の枝に対応する第２の復号途中結果を、同一のアドレスに格納するようにすることができる。
【０１５３】
LDPC符号の受信情報を格納するとともに、P個の受信情報を同時に読み出す受信情報記憶手段をさらに備えるようにすることができる。
【０１５４】
請求項３６に記載の復号装置であって、受信情報記憶手段は、受信情報を、P個のチェックノードの演算の他の一部と、P個のバリアブルノードの演算に必要となる順番に読み出すことができるように格納するようにすることができる。
【０１５５】
第１の演算手段がP個のチェックノードの演算の一部を行うことにより得られる第１の復号途中結果、または第２の演算がP個のチェックノードの演算の他の一部と、P個のバリアブルノードの演算を行うことにより得られる第２の復号途中結果を並べ替える並べ替え手段をさらに備えるようにすることができる。
【０１５６】
並べ替え手段は、バレルシフタで構成されるようにすることができる。
【０１５７】
本発明の復号方法は、P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、LDPC符号の検査行列が、複数の構成行列の組合せで表される場合において、LDPC符号の復号のためのP個のチェックノードの演算を同時に行う第１の演算ステップと、LDPC符号の復号のためのP個のバリアブルノードの演算を同時に行う第２の演算ステップとを含むことを特徴とする。
【０１５８】
本発明のプログラムは、LDPC符号の復号のためのP個のチェックノードの演算を同時に行う第１の演算ステップと、LDPC符号の復号のためのP個のバリアブルノードの演算を同時に行う第２の演算ステップとを含むことを特徴とする。
【０１５９】
本発明においては、P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、LDPC符号の検査行列が、複数の構成行列の組合せで表される場合において、LDPC符号の復号のためのP個のチェックノードの演算が同時に行われ、LDPC符号の復号のためのP個のバリアブルノードの演算が同時に行われる。
【発明の効果】
【０１６０】
本発明によれば、回路規模を抑制しつつ、動作周波数も十分実現可能な範囲に抑え、メモリアクセスの制御も容易に行うことが可能となる。また、LDPC符号の復号装置の回路規模を小さくすることができるので、コストを削減し、装置の消費電力を削減することができる。
【発明を実施するための最良の形態】
【０１６１】
以下に本発明の実施の形態を説明するが、請求項に記載の構成要件と、発明の実施の形態における具体例との対応関係を例示すると、次のようになる。この記載は、請求項に記載されている発明をサポートする具体例が、発明の実施の形態に記載されていることを確認するためのものである。従って、発明の実施の形態中には記載されているが、構成要件に対応するものとして、ここには記載されていない具体例があったとしても、そのことは、その具体例が、その構成要件に対応するものではないことを意味するものではない。逆に、具体例が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その具体例が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。
【０１６２】
さらに、この記載は、発明の実施の形態に記載されている具体例に対応する発明が、請求項に全て記載されていることを意味するものではない。換言すれば、この記載は、発明の実施の形態に記載されている具体例に対応する発明であって、この出願の請求項には記載されていない発明の存在、すなわち、将来、分割出願されたり、補正により追加される発明の存在を否定するものではない。
【０１６３】
請求項１に記載の復号装置は、LDPC(Low Density Parity Check)符号の復号装置であって、P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、前記LDPC符号の検査行列が、複数の前記構成行列の組合せで表される場合において、前記LDPC符号の復号のためのP個のチェックノードの演算を同時に行う第１の演算手段（例えば、図１６のチェックノード計算部３１３）と、前記LDPC符号の復号のためのP個のバリアブルノードの演算を同時に行う第２の演算手段（例えば、図１６のバリアブルノード計算部３１９）とを備えることを特徴とする。
【０１６４】
請求項２に記載の復号装置は、請求項１に記載の復号装置であって、前記第１の演算手段は、チェックノードの演算を行うP個のチェックノード計算器（例えば、図１６のチェックノード計算器３１３1）を有し、前記第２の演算手段は、バリアブルノードの演算を行うP個のバリアブルノード計算器（例えば、図１６のバリアブルノード計算器３１９1）を有することを特徴とする。
【０１６５】
請求項３に記載の復号装置は、請求項１に記載の復号装置であって、前記P個のチェックノードの演算、または前記P個のバリアブルノードの演算の結果得られるP個の枝に対応するメッセージデータを同時に読み書きするメッセージ記憶手段（例えば、図１６の枝データ格納メモリ３１１または３１６）をさらに備えることを特徴とする。
【０１６６】
請求項９に記載の復号装置は、請求項１に記載の復号装置であって、LDPC符号の受信情報を格納するとともに、P個の前記受信情報を同時に読み出す受信情報記憶手段（例えば、図１６の受信データ用メモリ３１８）をさらに備えることを特徴とする。
【０１６７】
請求項１１に記載の復号装置は、請求項１に記載の復号装置であって、前記P個のチェックノードの演算、または前記P個のバリアブルノードの演算の結果得られるメッセージを並べ替える並べ替え手段（例えば、図１６のサイクリックシフト回路３１４または３２０）をさらに備えることを特徴とする。
【０１６８】
請求項１５に記載の復号装置は、請求項１４に記載の復号装置であって、前記第１の演算手段は、前記P個のチェックノードの演算と前記P個のバリアブルノードの演算の一部を行うP個の計算器（例えば、計算器４１２1）を有し、前記第２の演算手段は、前記P個のバリアブルノードの演算の他の一部を行うP個の計算器（例えば、計算器４１５1）を有することを特徴とする。
【０１６９】
請求項１６に記載の復号装置は、請求項１４に記載の復号装置であって、前記第１の演算手段が前記P個のチェックノードの演算と前記P個のバリアブルノードの演算の一部を行うことにより得られるP個の枝に対応する第１の復号途中結果を同時に読み書きする第１の復号途中結果記憶手段（例えば、図１８の復号途中結果格納用メモリ４１３）をさらに備えることを特徴とする。
【０１７０】
請求項１８に記載の復号装置は、請求項１６に記載の復号装置であって、前記第１の復号途中結果記憶手段は、２個のシングルポートRAM(Random Access Memory)（例えば、図２３の復号途中結果格納用RAM５０２または５０３）であるようにすることができる。
【０１７１】
請求項２２に記載の復号装置は、請求項１４に記載の復号装置であって、前記第２の演算手段が前記P個のバリアブルノードの演算の他の一部を行うことにより得られるP個の枝に対応する前記第２の復号途中結果を同時に読み書きする第２の復号途中結果記憶手段（例えば、図１８の復号途中結果格納用メモリ４１０）をさらに備えることを特徴とする。
【０１７２】
請求項２３に記載の復号装置は、請求項１４に記載の復号装置であって、LDPC符号の受信情報を格納するとともに、P個の前記受信情報を同時に読み出す受信情報記憶手段（例えば、図１８の受信用メモリ４１６）をさらに備えることを特徴とする。
【０１７３】
請求項２５に記載の復号装置は、請求項１４に記載の復号装置であって、前記第１の演算手段が前記P個のチェックノードの演算と前記P個のバリアブルノードの演算の一部を行うことにより得られる第１の復号途中結果、または前記第２の演算手段が前記P個のバリアブルノードの演算の他の一部を行うことにより得られる第２の復号途中結果を並べ替える並べ替え手段（例えば、図１８のサイクリックシフト回路４１１または４１４）をさらに備えることを特徴とする。
【０１７４】
請求項２８に記載の復号装置は、請求項２７に記載の復号装置であって、前記第１の演算手段は、前記P個のチェックノードの演算の一部を行うP個の計算器（例えば、図２６の計算器６１２1）を有し、前記第２の演算手段は、前記P個のチェックノードの演算の他の一部と、前記P個のバリアブルノードの演算を行うP個の計算器（例えば、図２６の計算器６１５1）を有することを特徴とする。
【０１７５】
請求項２９に記載の復号装置は、請求項２７に記載の復号装置であって、前記第１の演算手段が前記P個のチェックノードの演算の一部を行うことにより得られるP個の枝に対応する第１の復号途中結果を同時に読み書きする第１の復号途中結果記憶手段（例えば、図２６の復号途中結果格納用メモリ６１３）をさらに備えることを特徴とする。
【０１７６】
請求項３０に記載の復号装置は、請求項２７に記載の復号装置であって、前記第２の演算手段が前記P個のチェックノードの演算の他の一部と、前記P個のバリアブルノードの演算を行うことにより得られるP個の枝に対応する第２の復号途中結果を同時に読み書きする第２の復号途中結果記憶手段（例えば、図２６の復号途中結果格納用メモリ６１０）をさらに備えることを特徴とする。
【０１７７】
請求項３２に記載の復号装置は、請求項３０に記載の復号装置であって、前記第２の復号途中結果記憶手段は、２個のシングルポートRAM(Random Access Memory)（例えば、図３１の復号途中結果格納用RAM７０２と７０３）であることを特徴とする。
【０１７８】
請求項３６に記載の復号装置は、請求項２７に記載の復号装置であって、LDPC符号の受信情報を格納するとともに、P個の前記受信情報を同時に読み出す受信情報記憶手段（例えば、図２６の受信用メモリ６１６）をさらに備えることを特徴とする。
【０１７９】
請求項３８に記載の復号装置は、請求項２７に記載の復号装置であって、前記第１の演算手段が前記P個のチェックノードの演算の一部を行うことにより得られる第１の復号途中結果、または前記第２の演算が前記P個のチェックノードの演算の他の一部と、前記P個のバリアブルノードの演算を行うことにより得られる第２の復号途中結果を並べ替える並べ替え手段（例えば、図２６のサイクリックシフト回路６１１または６１４）をさらに備えることを特徴とする。
【０１８０】
請求項４０に記載の復号方法は、LDPC(Low Density Parity Check)符号の復号装置の復号方法であって、P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、前記LDPC符号の検査行列が、複数の前記構成行列の組合せで表される場合において、前記LDPC符号の復号のためのP個のチェックノードの演算を同時に行う第１の演算ステップ（例えば、図１７のステップＳ３６）と、前記LDPC符号の復号のためのP個のバリアブルノードの演算を同時に行う第２の演算ステップ（例えば、図１７のステップＳ３１）とを含むことを特徴とする。
【０１８１】
請求項４１に記載のプログラムの各ステップの具体例も、請求項４０に記載の復号方法の各ステップの発明の実施の形態における具体例と同様である。
【０１８２】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。
【０１８３】
図１５は、５×５の行列の単位に間隔を空けた３０×９０の検査行列の例を示している。なお、図１５の検査行列自体は、図８に示した検査行列と同一である。
【０１８４】
図１５においては、検査行列は、５×５の単位行列、その単位行列の１のうち１個以上が０になった行列（以下、適宜、準単位行列という）、単位行列または準単位行列をサイクリックシフト(cyclic shift)した行列（以下、適宜、シフト行列という）、単位行列、準単位行列、またはシフト行列のうちの２以上(複数)の和（以下、適宜、和行列という）、５×５の０行列の組合わせで表わされている。なお、図１５の検査行列で表現されるLDPC符号は、符号化率2/3、符号長90である。
【０１８５】
図１５の検査行列は、５×５の単位行列、準単位行列、シフト行列、和行列、０行列で構成されているということができる。そこで、検査行列を構成する、これらの５×５の行列を、以下、適宜、構成行列という。
【０１８６】
図１６は、図１５の検査行列で表現されるLDPC符号を復号する復号装置の一実施の形態の構成例を示している。
【０１８７】
図１６の復号装置３００は、スイッチ３１０および３１５、６つのFIFO３１１1乃至３１１6からなる枝データ格納メモリ３１１、セレクタ３１２、５つのチェックノード計算器３１３1乃至３１３5からなるチェックノード計算部３１３、２つのサイクリックシフト回路３１４および３２０、１８個のFIFO３１６1乃至３１６18からなる枝データ格納メモリ３１６、セレクタ３１７、受信情報を格納する受信データ用メモリ３１８、バリアブルノード計算部３１９、制御部３２１から構成される。
【０１８８】
この復号装置３００の各部について詳細に説明する前に、まず、枝データ格納メモリ３１１と３１６へのデータの格納方法について説明する。
【０１８９】
枝データ格納メモリ３１１は、検査行列の行数３０を構成行列の行数５で除算した数である６つのFIFO３１１1乃至３１１6から構成されている。FIFO３１１y（ｙ＝１，２，・・・，６）は、構成行列の行数および列数である５つの枝に対応するメッセージを同時に読み出しもしくは書き込むことができるようになっており、その長さ（段数）は、検査行列の行方向の１の数（ハミング重み）の最大数である９になっている。
【０１９０】
FIFO３１１1には、図１５の検査行列の第１行目から第５行目までの１の位置に対応するデータが、各行共に横方向（列方向）に詰めた形に（０を無視した形で）格納される。すなわち、第ｊ行第ｉ列を、(j,i)と表すこととすると、FIFO３１１1の第１の要素（第１段）には、検査行列の(1,1)から(5,5)の５×５の単位行列の１の位置に対応するデータが格納される。第２の要素には、検査行列の構成行列である(1,21)から(5,25)のシフト行列（５×５の単位行列を右方向に３つだけサイクリックシフトしたシフト行列）の１の位置に対応するデータが格納される。第３から第８の要素も同様に検査行列の構成行列と対応づけてデータが格納される。そして、第９の要素には、検査行列の(1,86)から(5,90)のシフト行列（５×５の単位行列のうちの１行目の１を０に置き換えて１つだけ左にサイクリックシフトしたシフト行列）の１の位置に対応するデータが格納される。ここで、検査行列の(1,86)から(5,90)のシフト行列においては、１行目に１がないため、FIFO３１１1の１行目のみ要素数は８、残りの行は要素数が９となる。
【０１９１】
FIFO３１１2には、図１５の検査行列の第６行目から第１０行目までの１の位置に対応するデータが格納される。すなわち、FIFO３１１2の第１の要素には、検査行列の(6,1)から(10,5)の和行列（５×５の単位行列を右に１つだけサイクリックシフトした第１のシフト行列と、右に２つだけサイクリックシフトした第２のシフト行列の和である和行列）を構成する第１のシフト行列の１の位置に対応するデータが格納される。また、第２の要素には、検査行列の(6,1)から(10,5)の和行列を構成する第２のシフト行列の１の位置に対応するデータが格納される。
【０１９２】
即ち、重みが２以上の構成行列については、その構成行列を、重みが１であるP×Pの単位行列、そのコンポーネントである１のうち１個以上が０になった準単位行列、または単位行列もしくは準単位行列をサイクリックシフトしたシフト行列のうちの複数の和の形で表現したときの、その重みが１の単位行列、準単位行列、またはシフト行列の１の位置に対応するデータ（単位行列、準単位行列、またはシフト行列に属する枝に対応するメッセージ）は、同一アドレス（FIFO３１１1乃至３１１6のうちの同一のFIFO）に格納される。
【０１９３】
以下、第３から第９の要素についても、検査行列に対応づけてデータが格納される。FIFO３１１2は全行共に要素数は９となる。
【０１９４】
FIFO３１１3乃至３１１6も同様に検査行列に対応づけてデータを格納し、各FIFO３１１3乃至３１１6それぞれの長さは９である。
【０１９５】
枝データ格納メモリ３１６は、検査行列の列数９０を、構成行列の列数である５で割った１８個のFIFO３１６1乃至３１６18から構成されている。FIFO３１６x（ｘ＝１，２，・・・，１８）は、構成行列の行数および列数である５つの枝に対応するメッセージを同時に読み出しもしくは書き込むことができるようになっている。
【０１９６】
FIFO３１６1には、図１５の検査行列の第１列目から第５列目までの１の位置に対応するデータが、各列共に縦方向（行方向）に詰めた形に（０を無視した形で）格納される。すなわち、FIFO３１６1の第１の要素（第１段）には、検査行列の(1,1)から(5,5)の５×５の単位行列の１の位置に対応するデータが格納される。第２の要素には、検査行列の(6,1)から(10,5)の和行列（５×５の単位行列を右に１つだけサイクリックシフトした第１のシフト行列と、右に２つだけサイクリックシフトした第２のシフト行列との和である和行列）を構成する第１のシフト行列の１の位置に対応するデータが格納される。また、第３の要素には、検査行列の(6,1)から(10,5)の和行列を構成する第２のシフト行列の１の位置に対応するデータが格納される。
【０１９７】
即ち、重みが２以上の構成行列については、その構成行列を、重みが１であるP×Pの単位行列、そのコンポーネントである１のうち１個以上が０になった準単位行列、または単位行列もしくは準単位行列をサイクリックシフトしたシフト行列のうちの複数の和の形で表現したときの、その重みが１の単位行列、準単位行列、またはシフト行列の１の位置に対応するデータ（単位行列、準単位行列、またはシフト行列に属する枝に対応するメッセージ）は、同一アドレス（FIFO３１６1乃至３１６18のうちの同一のFIFO）に格納される。
【０１９８】
以下、第４および第５の要素についても、検査行列に対応づけて、データが格納される。このFIFO３１６1の要素数（段数）は、検査行列の第１列から第５列における行方向の１の数（ハミング重み）の最大数である５になっている。
【０１９９】
FIFO３１６2と３１６3も同様に検査行列に対応づけてデータを格納し、それぞれの長さ（段数）は、５である。FIFO３１６4乃至３１６12も同様に検査行列に対応づけてデータを格納し、それぞれの長さは３である。FIFO３１６13乃至３１６18も同様に検査行列に対応づけてデータを格納し、それぞれの長さは２である。但し、FIFO３１６18の第１の要素は、検査行列の(1,86)から(5,90)に相当し、第５列目（検査行列の(1,90)から(5,90)）に１がないため、データは格納されない。
【０２００】
以下、図１６の復号装置３００の各部の動作について詳細に説明する。
【０２０１】
スイッチ３１０には、サイクリックシフト回路３２０から５つのメッセージ（データ）D319が供給されるとともに、制御部３２１から検査行列のどの行に属するかの情報（Matrixデータ）を表す制御信号D320が供給される。制御信号D320にしたがって、５つのメッセージ（データ）D319を格納するFIFOを、FIFO３１１1乃至３１１6の中から選択し、選択したFIFOに５つのメッセージデータD319をまとめて順番に供給していく。
【０２０２】
枝データ格納メモリ３１１は、６つのFIFO３１１1乃至３１１6からなる。枝データ格納メモリ３１１のFIFO３１１1乃至３１１6には、スイッチ３１０から、５つのメッセージD319がまとめて順番に供給され、FIFO３１１1乃至３１１6は、５つのメッセージD319をまとめて順番に（同時に）格納していく。また、枝データ格納メモリ３１１は、データを読み出す際には、FIFO３１１1から５つのメッセージ（データ）D3111を順番に読み出し、次段のセレクタ３１２に供給する。枝データ格納メモリ３１１は、FIFO３１１1からのメッセージD3111の読み出しの終了後、FIFO３１１2乃至３１１6からも、順番に、メッセージD3111乃至D3116をそれぞれ読み出し、セレクタ３１２に供給する。
【０２０３】
セレクタ３１２には、制御部３２１から、FIFO３１１1乃至３１１6のうち、メッセージデータを読み出すFIFO（現在データが読み出されているFIFO）の選択を表す選択信号D321が供給されるとともに、枝データ格納メモリ３１１から５つのメッセージ（データ）D3111乃至D3116が供給される。セレクタ３１２は、選択信号D321にしたがって、FIFO３１１1乃至３１１6のうちの、現在データが読み出されているFIFOを選択し、その選択したFIFOから供給された５つのメッセージデータを、メッセージD312として、チェックノード計算部３１３に供給する。
【０２０４】
チェックノード計算部３１３は、５つのチェックノード計算器３１３1乃至３１３5からなる。チェックノード計算部３１３には、セレクタ３１２を介して５つのメッセージD312が供給され、そのメッセージD312が、チェックノード計算器３１３1乃至３１３5のそれぞれに１つずつ供給される。また、チェックノード計算部３１３には、制御部３２１から制御信号D322が供給され、その制御信号D322が、チェックノード計算器３１３1乃至３１３5に供給される。チェックノード計算器３１３1乃至３１３5は、メッセージD312を用いて、式（７）にしたがって同時に演算を行い、その演算の結果、５個の枝に対応するメッセージD313を求める。チェックノード計算部３１３は、チェックノード計算器３１３1乃至３１３5による演算の結果得られる５つのメッセージD313をサイクリックシフト回路３１４に供給する。
【０２０５】
ここで、制御部３２１からチェックノード計算部３１３に供給される制御信号D322は、図１０の制御信号D106に対応するものであり、チェックノード計算部３１３1乃至３１３5それぞれは、図１０に示したチェックノード計算器１０１と同様に構成される。
【０２０６】
サイクリックシフト回路３１４には、チェックノード計算部３１３で計算された５つのメッセージD313が供給されるとともに、制御部３２１から、そのメッセージD313に対応する枝が検査行列において元となる単位行列などを幾つサイクリックシフトしたものであるかの情報（Matrixデータ）を表す制御信号D323が供給される。サイクリックシフト回路３１４は、制御信号D323を元に、５つのメッセージD313を並べ替えるサイクリックシフトを行い、その結果をメッセージD314として、スイッチ３１５に供給する。
【０２０７】
スイッチ３１５には、サイクリックシフト回路３１４から供給される５つのメッセージ（データ）D314が検査行列のどの列に属するかの情報を表す制御信号D324が供給されるとともに、サイクリックシフト回路３１４から、メッセージD314が供給される。スイッチ３１５は、制御信号D324にしたがって、メッセージD314を格納するFIFOを、FIFO３１６1乃至３１６18の中から選択し、選択したFIFOに５つのメッセージD314をまとめて順番に供給していく。
【０２０８】
枝データ格納メモリ３１６は、１８個のFIFO３１６1乃至３１６18からなる。枝データ格納メモリ３１６のFIFO３１６1乃至３１６18には、スイッチ３１５から５つのメッセージD314がまとめて順番に（同時に）供給され、FIFO３１６1乃至３１６18は、その５つのメッセージD314をまとめて順番に格納していく。また、枝データ格納メモリ３１６は、データを読み出す際には、FIFO３１６1から５つのメッセージD3151を順番に読み出し、次段のセレクタ３１７に供給する。枝データ格納メモリ３１６は、FIFO３１６1からのデータの読み出しの終了後、FIFO３１６2乃至３１６18からも、順番に、メッセージD3152乃至D313１８を読み出し、セレクタ３１７に供給する。
【０２０９】
セレクタ３１７には、制御部３２１からFIFO３１６1乃至３１６18のうち、メッセージデータを読み出すFIFO（現在データが読み出されているFIFO）の選択を表す選択信号D325が供給されるとともに、枝データ格納メモリ３１６からメッセージデータD3151乃至D313１８が供給される。セレクタ３１７は、選択信号D325にしたがって、FIFO３１６1乃至３１６18のうちの、現在データが読み出されているFIFOを選択し、その選択したFIFOから供給される５つのメッセージデータを、メッセージD316として、バリアブルノード計算部３１９と上述した式（５）の演算を行う不図示のブロックに供給する。
【０２１０】
一方、受信データ用メモリ３１８は、通信路を通して受信した受信信号から、受信LLR（対数尤度比）を計算しており、その計算した受信LLRを５つまとめて（同時に）受信データD317（LDPC符号）としてバリアブルノード計算部３１９と、式（５）の演算を行う不図示のブロックに供給する。なお、受信データ用メモリ３１８は、バリアブルノード計算部３１９のバリアブルノード演算に必要となる順番に、受信データD317を読み出す。
【０２１１】
バリアブルノード計算部３１９は、５つのバリアブルノード計算器３１９1乃至３１９5からなる。バリアブルノード計算部３１９には、セレクタ３１７を介して５つのメッセージD316が供給され、そのメッセージD316が、バリアブルノード計算器３１９1乃至３１９5のそれぞれに１つずつ供給される。また、バリアブルノード計算部３１９には、受信データ用メモリ３１８から５つの受信データD317が供給され、その受信データD317が、バリアブルノード計算器３１９1乃至３１９5のそれぞれに１つずつ供給される。さらに、バリアブルノード計算部３１９には、制御部３２１から制御信号D326が供給され、その制御信号D326がバリアブルノード計算器３１９1乃至３１９5に供給される。
【０２１２】
バリアブルノード計算器３１９1乃至３１９5は、メッセージD316と、受信データD317を用いて、式（１）にしたがって同時に演算を行い、その演算の結果、５個の枝に対応するメッセージD318を求める。バリアブルノード計算部３１９は、バリアブルノード計算器３１９1乃至３１９5の結果得られる５つのメッセージD318を、サイクリックシフト回路３２０に供給する。
【０２１３】
ここで、制御部５２１からバリアブルノード計算部３１９に供給される制御信号D326は、図１１の制御信号D107に対応するものであり、バリアブルノード計算器３１９1乃至３１９5それぞれは、図１１のバリアブルノード計算器１０３と同様に構成される。
【０２１４】
サイクリックシフト回路３２０には、バリアブルノード計算部３１９から５つのメッセージD318が供給されるとともに、制御部３２１から、そのメッセージD318に対応する枝が検査行列において元となる単位行列などを幾つサイクリックシフトしたものであるかの情報を表す制御信号D327が供給される。サイクリックシフト回路３２０は、制御信号D327を元に、メッセージD327を並べ替えるサイクリックシフトを行い、その結果をメッセージD319として、スイッチ３１０に供給する。
【０２１５】
なお、制御部３２１は、制御信号D320をスイッチ３１０に、選択信号D321をセレクタ３１２に供給することにより、それぞれを制御する。また制御部３２１は、制御信号D322をチェックノード計算部３１３に、制御信号D323をサイクリックシフト回路３１４に、制御信号D324をスイッチ３１５に供給することにより、それぞれを制御する。さらに、制御部３２１は、選択信号D325をセレクタ３１７、制御信号D326をバリアブルノード計算部３１９に、制御信号D327をサイクリックシフト回路３２０に供給することにより、それぞれを制御する。
【０２１６】
以上の動作を１巡することで、LDPC符号の１回の復号を行うことができる。図１６の復号装置３００は、所定の回数だけLDPC符号を復号した後、図示しないが、式（５）にしたがって最終的な復号結果を求めて出力する。
【０２１７】
なお、枝データ（枝に対応するメッセージ）が欠けている箇所に関しては、メモリ格納時（枝データ格納メモリ３１１と３１６へのデータ格納時）には、何のメッセージも格納せず、また、ノード演算時（チェックノード計算部３１３でのチェックノード演算時とバリアブルノード計算部３１９でのバリアブルノード演算時）にも何の演算も行わない。
【０２１８】
図１７は、図１６の復号装置３００の復号処理を説明するフローチャートである。この処理は、例えば、受信データ用メモリ３１８に復号すべき受信データが格納されたとき、開始される。
【０２１９】
ステップＳ３１において、バリアブルノード計算部３１９は、バリアブルノード演算を行う。
【０２２０】
具体的には、バリアブルノード計算部３１９には、セレクタ３１７を介して、５つのメッセージD316（メッセージuj）が供給される。即ち、枝データ格納メモリ３１６は、後述するステップＳ３９で格納されたFIFO３１６1から５つのメッセージD3161を順番に読み出し、その後、FIFO３１６2乃至３１６18からも、順番に、メッセージD3162乃至D31618を読み出して、セレクタ３１７に供給する。
【０２２１】
セレクタ３１７には、制御部３２１からFIFO３１６1乃至３１６18のうち、メッセージ（データ）を読み出すFIFO（現在データが読み出されているFIFO）の選択を表す選択信号D307が供給されるとともに、枝データ格納メモリ３１６からメッセージデータD3161乃至D31618が供給される。セレクタ３１７は、選択信号D307にしたがって、FIFO３１６1乃至３１６18のうちの、現在データが読み出されているFIFOを選択し、その選択したFIFOから供給される５つのメッセージデータを、メッセージD316として、バリアブルノード計算部３１９に供給する。
【０２２２】
なお、受信データ用メモリ３０６から供給された受信データD309に対して、まだチェックノード演算が行われておらず、枝データ格納メモリ３１６にメッセージD304が格納されていない場合、バリアブルノード計算部３１９は、バリアブルノード演算に用いるメッセージujを初期値に設定する。
【０２２３】
また、バリアブルノード計算部３１９には、受信データ用メモリ３１８から５つの受信データD309（受信値u0i）が供給され、その受信データD309が、バリアブルノード計算器３１９1乃至３１９5のそれぞれに１つずつ供給される。さらに、バリアブルノード計算部３１９には、制御部３２１から制御信号D315が供給され、その制御信号D315がバリアブルノード計算器３１９1乃至３１９5に供給される。
【０２２４】
バリアブルノード計算器３１９1乃至３１９5は、メッセージD316と、受信データD309を用いて、制御信号D315に基づいて、式（１）にしたがって同時に演算を行い、その演算の結果５つのメッセージD319を求める。
【０２２５】
即ち、制御部３２１がバリアブルノード計算部３１９に供給する制御信号D315は、前述の図１１で説明した制御信号D107に対応するものであり、バリアブルノード計算器３１９1乃至３１９5は、制御信号D309にしたがい、セレクタ３１７を介して、枝データ格納メモリ３１６から必要なメッセージD314（D316）を、それぞれ１つずつ読み出すとともに、受信データ用メモリ３１８から供給された５つの受信データD309を、それぞれ１つずつ読み出して、バリアブルノード演算を行い、その演算の結果５つのメッセージD319を同時に求める。
【０２２６】
ステップＳ３１の処理後は、ステップＳ３２に進み、バリアブルノード計算部３１９は、バリアブルノード計算器３１９1乃至３１９5のバリアブルノード演算の結果得られる５つのメッセージD319（メッセージvi）をサイクリックシフト回路３２０に供給し、ステップＳ３３に進む。
【０２２７】
ステップＳ３３において、サイクリックシフト回路３２０は、バリアブルノード計算部３１９から供給された５つのメッセージD318を、サイクリックシフトする（並べ替える）。
【０２２８】
具体的には、サイクリックシフト回路３２０には、バリアブルノード計算部３１９からメッセージD318が供給されるとともに、制御部３２１から、そのメッセージD318に対応する枝が検査行列において元となる単位行列などを幾つサイクリックシフトしたものであるかの情報（Matrixデータ）を表す制御信号D327が供給される。サイクリックシフト回路３２０は、制御信号D327を元に、５つのメッセージD327をサイクリックシフトし、その結果をメッセージD319として、スイッチ３１０に供給する。
【０２２９】
ステップＳ３３の処理後は、ステップＳ３４に進み、スイッチ３１０は、サイクリックシフト回路３２０から供給される５つのメッセージD319を枝データ格納メモリ３１１に供給する。
【０２３０】
具体的には、スイッチ３１０には、サイクリックシフト回路３２０からメッセージ（データ）D304が供給されるとともに、そのメッセージD304が検査行列のどの行に属するかの情報を表す制御信号D312が供給される。スイッチ３１０は、制御信号D312にしたがって、メッセージD304を格納するFIFOを、枝データ格納メモリ３１１のFIFO３００1乃至３００6の中から選択し、選択したFIFOに５つのメッセージデータD304をまとめて順番に供給していく。
【０２３１】
そして、枝データ格納メモリ３１１のFIFO３００1乃至３００18は、スイッチ３１０から供給された５つのメッセージデータD304をまとめて順番に格納していく。
【０２３２】
ステップＳ３４の処理後は、ステップＳ３５に進み、制御部３２１は、バリアブルノード計算部３１９により、全枝数のメッセージが演算されたかどうかを判定し、全枝数のメッセージが演算されていないと判定した場合、ステップＳ３１に戻り、上述した処理を繰り返す。
【０２３３】
一方、ステップＳ３５において、バリアブルノード計算部３１９は、全枝数のメッセージが演算されたと判定した場合、ステップＳ３６に進み、チェックノード計算部３１３は、チェックノード演算を行う。
【０２３４】
具体的には、チェックノード計算部３１３には、セレクタ３１２を介して、５つのメッセージD302が供給される。即ち、枝データ格納メモリ３１１は、ステップＳ３４で格納されたFIFO３１１1から５つのメッセージD3111（メッセージvi）を順番に読み出し、その後、FIFO３１１2乃至３１１6からも、順番に、メッセージデータD3112乃至D3116を読み出し、セレクタ３１２に供給する。
【０２３５】
セレクタ３１２には、制御部３２１からFIFO３１１1乃至３１１6のうち、メッセージデータを読み出すFIFO（現在データが読み出されているFIFO）の選択を表す選択信号D321が供給されるとともに、枝データ格納メモリ３１１からメッセージデータD3111乃至D3116が供給される。セレクタ３０１は、選択信号D321にしたがって、FIFO３１１1乃至３１１6のうちの、現在データが読み出されているFIFOを選択し、その選択したFIFOから供給される５つのメッセージデータを、メッセージD311として、チェックノード計算部３１３に供給する。
【０２３６】
また、チェックノード計算部３１３には、制御部３２１から制御信号D322が供給される。チェックノード計算部３１３のチェックノード計算器３１３1乃至３１３5は、制御信号D322に基づいて、メッセージD302を用いて、上述した式（７）にしたがって同時にチェックノード演算を行い、その演算結果である５つのメッセージD303（メッセージuj）を求める。
【０２３７】
即ち、制御部３２１がチェックノード計算部３１３に供給する制御信号D322は、前述の図１０で説明した制御信号D106に対応するものであり、チェックノード計算器３１３1乃至３１３5は、制御信号D322にしたがい、セレクタ３１２を介して、枝データ格納メモリ３１１から必要なメッセージD311（D312）を、それぞれ１つずつ読み出しながら、チェックノード演算を行い、その演算の結果５つのメッセージD313を同時に求める。
【０２３８】
ステップＳ３７の処理後は、ステップＳ３８に進み、チェックノード計算部３１３は、チェックノードの演算の結果得られる５つのメッセージD313をサイクリックシフト回路３１４に出力して、ステップＳ３８に進む。
【０２３９】
ステップＳ３８において、サイクリックシフト回路３１４は、チェックノード計算部３１３から供給された５つのメッセージD313を、サイクリックシフトする。
【０２４０】
具体的には、サイクリックシフト回路３１４には、チェックノード計算部３１３からメッセージD313が供給されるとともに、制御部３２１から、そのメッセージD313に対応する枝が検査行列において元となる単位行列などを幾つサイクリックシフトしたものであるかの情報（Matrixデータ）を表す制御信号D314が供給される。サイクリックシフト回路３１４は、制御信号D314を元に、５つのメッセージD313をサイクリックシフトし、その結果をメッセージD304として、スイッチ３１５に供給する。
【０２４１】
ステップＳ３８の処理後は、ステップＳ３９に進み、スイッチ３１５は、サイクリックシフト回路３１４から供給される５つのメッセージD304を枝データ格納メモリ３１６に格納する。
【０２４２】
具体的には、スイッチ３１６には、サイクリックシフト回路３１４から、５つのメッセージ（データ）D304が供給されるとともに、そのメッセージ（データ）D304が検査行列のどの列に属するかの情報を表す制御信号D324が供給される。スイッチ３１６は、制御信号D324にしたがって、メッセージD304を格納するFIFOを、枝データ格納メモリ３１６のFIFO３１６1乃至３１６18の中から選び、選んだFIFOに５つのメッセージデータD304をまとめて順番に供給していく。
【０２４３】
そして、枝データ格納メモリ３１６のFIFO３１６1乃至３１６18は、スイッチ３１６から供給された５つのメッセージデータD304をまとめて順番に格納していく。
【０２４４】
ステップＳ３９の処理後は、ステップＳ４０に進み、制御部３２１は、チェックノード計算部３１３により、全枝数のメッセージが演算されたかどうかを判定し、全枝数のメッセージが演算されていないと判定した場合、ステップＳ３６に戻り、上述した処理を繰り返す。
【０２４５】
一方、ステップＳ４０において、制御部３２１は、チェックノード計算部３１３により、全枝数のメッセージが演算されたと判定した場合、処理を終了する。
【０２４６】
なお、復号装置３００は、復号回数だけ図１７の復号処理を繰り返し行ない、チェックノード計算部３１３が、最後のチェックノード演算を行った場合、チェックノード演算の結果得られるメッセージD304が、枝データ格納メモリ３１６から、セレクタ３１７を介して、上述した式（５）の演算を行う不図示のブロックに供給される。不図示のブロックには、さらに受信データ用メモリ３０６から受信データD309が供給され、不図示のブロックは、メッセージD304と受信データD309を用いて、式（５）の演算を行い、その演算結果を最終的な復号結果として出力する。
【０２４７】
上記説明には、枝データ格納にFIFOを用いたが（枝データ格納メモリ３１１と３１６をFIFOで構成するようにしたが）、FIFOの代わりにRAMを用いても構わない。その場合、RAMには、P個の枝情報（枝に対応するメッセージ）を同時に読み出すことの出来るビット幅と、枝総数/Pのワード(word)数が必要となる。さらに、RAMへの書き込みは、検査行列の情報から、書き込もうとしているデータが次に読み出される際に何番目に読み出されるかを求め、その位置に書き込む。また、RAMからの読み出しの際には、アドレスの先頭から順次データを読み出す。即ち、RAMは、メッセージデータを読み出される順番に詰めて格納し、格納位置順に読み出す。FIFOの代わりにRAMを用いると、セレクタ３１２および３１７は不要になる。
【０２４８】
なお、FIFOやRAMの物理的なビット幅が足りない場合には、複数のRAMを用いて同じ制御信号を与えることで、論理的に１つのRAMとみなすことができる。
【０２４９】
ところで、図１６の復号装置３００では、チェックノード演算の結果得られるメッセージujを用いて、バリアブルノード演算が行われ、その演算の結果得られるメッセージviを用いて、チェックノード演算が行われるため、チェックノード演算の結果得られる枝に対応するメッセージujとバリアブルノード演算の結果得られる枝に対応するメッセージviをすべて格納する枝データ格納メモリ３１１と枝データ格納メモリ３１６が必要である。即ち、復号装置では、検査行列Hの“１”の数の２倍のメッセージを格納するために必要な容量のメモリが必要である。
【０２５０】
そこで、復号装置の回路規模さらに小さくするため、図１６の復号装置３００に比べて、さらにメモリの容量を減らした復号装置を以下に示す。
【０２５１】
図１８は、本発明を適用した図１５の検査行列で表現されるLDPC符号を復号する復号装置の他の一実施の形態の構成例を示すブロック図である。
【０２５２】
図１８の復号装置４００では、図１６の枝データ格納メモリ３１1が、枝データ格納メモリ３１１に比べて容量の小さい復号途中結果格納用メモリ４１０になっている。
【０２５３】
復号装置４００は、復号途中結果格納用メモリ４１０、サイクリックシフト回路４１１、５つの計算器４１２1乃至計算器４１２5からなる計算部４１２、復号途中結果格納用メモリ４１３、サイクリックシフト回路４１４、５つの計算器４１５1乃至計算器４１５5からなる計算部４１５、受信用メモリ４１６、および制御部４１７から構成される。
【０２５４】
ここで、図１９乃至図２２を用いて、図１８の計算部４１２の計算器４１２1乃至計算器４１２5、および計算部４１５の計算器４１５1乃至計算器４１５5と図１０のチェックノード計算器１０１と図１１のバリアブルノード計算器１０３との関係について説明する。
【０２５５】
図１９と図２０は、前述の図１０のチェックノード計算器１０１と図１１のバリアブルノード計算器１０３とそれぞれ同一の図である。また、図２１は、計算部４１２k（k=1,2,・・・，5）の構成例を示しており、図２２は、計算部４１５k（k=1,2,・・・，5）の構成例を示している。
【０２５６】
図１８の復号装置４００では、計算器４１２kがチェックノード演算を行い、計算部４１５kが、バリアブルノード演算をおこなうのではなく、計算器４１２kがチェックノード演算とバリアブルノード演算の一部を、計算器４１５kがバリアブルノード演算の他の一部を行う。
【０２５７】
即ち、図２１の計算器４１２kは、ブロックＡ'とブロックＢ'から構成されている。ブロックＡ‘は、図１９のチェックノード計算器１０１のチェックノード演算を行うブロックＡと同様に構成されている。また、ブロックＢ’は、図２０のバリアブルノード計算器１０３の一部である、検査行列の各列の全ての枝に対応するメッセージujの積算値から、求めたい枝に対応するメッセージujを減算するブロックＢと同様に構成されている。一方、図２２の計算器４１５kは、ブロックＣ'から構成されている。ブロックＣ'は、図２０のバリアブルノード計算器１０３の他の一部である、検査行列の各列の枝に対応するメッセージujを積算し、その積算値に受信値u0iを加算するブロックＣと同様に構成されている。
【０２５８】
そして、図２１の計算器４１２kは、ブロックＡとブロックＢによる演算の結果、即ち、チェックノード演算とバリアブルノード演算の一部を行った復号途中結果ujを復号途中結果格納用メモリ４１３に供給し、図２２の計算器４１５kは、バリアブルノード演算の他の一部を行った復号途中結果vを復号途中結果格納用メモリ４１０に供給する。
【０２５９】
従って、図１８の復号装置４００は、計算器４１２kの演算と計算器４１５kの演算とを交互に行うことにより、チェックノード演算とバリアブルノード演算を行い、復号を行うことができる。
【０２６０】
なお、図２２の計算器４１２kでは、復号途中結果格納用メモリ４１３に格納されている求めたい枝に対応する復号途中結果ujを用いて、ブロックＢで、計算器４１５kの演算の結果得られる復号途中結果vから、求めたい枝に対応する復号途中結果ujを減算するので、図２０のFIFOメモリ１５５が必要ない。
【０２６１】
次に、計算器４１２kで行われる演算と、計算器４１５kで行われる演算について、式を用いて説明する。
【０２６２】
具体的には、計算部４１２は、上述した式（７）と、以下に表す式（８）にしたがう第１の演算を行い、その第１の演算の結果である復号途中結果ujを復号途中結果格納用メモリ４１０に供給して格納させる。計算部４１５は、上述した式（５）にしたがう第２の演算を行い、その第２の演算の結果である復号途中結果vを復号途中結果格納用メモリ４１０に供給して格納させる。
【０２６３】
【数８】
2004364233.tif 000010
・・・（８）
【０２６４】
なお、式（８）のudvは、検査行列Hのｉ列のメッセージを求めようとする枝からのチェックノード演算の途中結果（ここでは、チェックノード演算結果そのもの）を表している。即ち、udvは、求めたい枝に対応する復号途中結果である。
【０２６５】
即ち、上述した式（５）にしたがう第２の演算の結果得られる復号途中結果vは、受信値u0iと検査行列Hのｉ列の各行の１に対応するすべての枝からのチェックノード演算の復号途中結果ujとを加算したものであるので、上述した式（７）に用いられる値viは、式（５）にしたがう第２の演算の結果得られる復号途中結果vから、検査行列Hのｉ列の、各行の１に対応する枝からのチェックノード演算の復号途中結果ujのうち、メッセージを求めようとする枝からのチェックノード演算の復号途中結果udvを引いた値となる。つまり、式（７）の演算に用いられる値viを求める式（１）の演算は、上述した式（５）と式（８）を組み合わせた演算である。
【０２６６】
従って、復号装置４００では、計算部４１２による式（７）および式（８）にしたがう第１の演算と、計算部４１５による式（５）にしたがう第２の演算とが交互に行われ、計算部４１５が、最後の第２の演算の結果を復号結果として出力することにより、LDPC符号の繰り返し復号を行うことができる。
【０２６７】
なお、ここでは、式（７）と式（８）にしたがう第１の演算結果を、復号途中結果ujを復号途中結果ujと記載するが、この復号途中結果ujは、式（７）のチェックノード演算結果ｕjに等しい。
【０２６８】
また、第２の演算により求められる式（５）のvは、式（１）のバリアブルノード演算結果viに対して、メッセージを求めようとする枝からのチェックノード演算結果ujを加算したものであるから、検査行列Hの1列（１つのバリアブルノード）に対して、１つだけ求められる。
【０２６９】
復号装置４００では、計算部４１２が、計算部４１５による第２の演算の結果である検査行列Hの列に対応する復号途中結果v（第２の復号途中結果）を用いて、第１の演算を行い、その演算の結果得られる検査行列Hのｉ列の、各行の１に対応する枝のメッセージ（各チェックノードが各枝に出力するメッセージ）の枝からのチェックノード演算の復号途中結果uj（第１の復号途中結果）を復号途中結果格納用メモリ４１３に格納する。従って、復号途中結果格納用メモリ４１３の容量は、チェックノード演算の結果を格納する図１６の枝データ格納メモリ３１６と同様に、検査行列の１の数（全枝数）とメッセージの量子化ビット数とを乗算した値となる。一方、計算部４１５は、計算部４１２による第１の演算の結果である検査行列Hのｉ列の、各行の“１”に対応する復号途中結果ujと受信値u0iを用いて、第２の演算を行い、その演算の結果得られるｉ列に対応する復号途中結果vを復号途中結果格納用メモリ４１０に格納する。従って、復号途中結果格納用メモリ４１０に必要な容量は、検査行列の“１”の数より少ない検査行列の列数、即ち、LDPC符号の符号長と復号途中結果vの量子化ビット数とを乗算した値となる。
【０２７０】
従って、検査行列Hにおける１が疎らなLDPC符号を復号する復号装置４００では、図１６の枝データ格納メモリ３１１に比べて、復号途中結果格納用メモリ４１０のメモリの容量を削減することができ、これにより、復号装置４００の回路規模を小さくすることができる。
【０２７１】
さらに、復号装置４００では、計算部４１５が、式（５）にしたがう第２の演算を行うので、復号装置４００は、図１６の復号装置３００において最終的な復号結果を演算する式（５）の演算を行う不図示のブロックを有する必要がなく、図１６の復号装置３００に比べて、図１８の復号装置の回路規模を小さくすることができる。
【０２７２】
以下、図１８の復号装置４００の各部の動作について詳細に説明する。
【０２７３】
復号途中結果格納用メモリ４１０には、計算部４１５から、計算部４１５による第２の演算の結果である検査行列の５つの列に対応する５つの復号途中結果D415が供給され、復号途中結果格納用メモリ４１０は、計算部４１５から供給された５つの復号途中結果D415を、第１アドレスから順に格納（記憶）する。
【０２７４】
即ち、復号途中結果格納用メモリ４１０の第１アドレスには、検査行列の列に対応する復号途中結果のうち、第１列目から第５列目の復号途中結果vが格納される。そして、同様に、第２アドレスには、第６列目から第１０列目の復号途中結果vが格納され、第３アドレスには、第１１列目から第１５列目の復号途中結果が格納される。以後、同様に、第１６列目から第９０列目までの復号途中結果vが、５個ずつ、第４アドレスから第１８アドレスまで格納され、計９０個の復号途中結果vが復号途中結果格納用メモリ４１０に格納される。従って、復号途中結果格納用メモリ４１０のワード（word）数は、図１５の検査行列Hの列数（LDPC符号の符号長）である９０を、同時に読み書きする復号途中結果の数である５で割り算した１８となる。
【０２７５】
また、復号途中結果格納用メモリ４１０は、既に格納してある復号途中結果D415から、後段の計算部４１２が求めようとする復号途中結果ujの対応する検査行列Hの行において“１”になっている復号途中結果vを５つ同時に読み出し、復号途中結果D410として、サイクリックシフト回路４１１に供給する。
【０２７６】
なお、復号途中結果格納用メモリ４１０は、例えば、５つの復号途中結果を同時に読み書き可能なシングルポートRAMで構成される。また、復号途中結果格納用メモリ４１０には、計算部４１５の第２の演算により演算された列に対応する復号途中結果vが格納されるので、復号途中結果格納用メモリ４１０に格納されるデータ量、即ち、復号途中結果格納用メモリ４１０に必要とされる記憶容量は、復号途中結果の量子化ビット数と、検査行列Hの列数（LDPC符号の符号長）との乗算値である。
【０２７７】
サイクリックシフト回路４１１には、復号途中結果格納用メモリ４１０から５つの復号途中結果D410が供給されるとともに、制御部４１７から、その復号途中結果D410に対応する検査行列の１が、検査行列において元となる単位行列などを幾つサイクリックシフトであるかの情報（Matrixデータ）を表す制御信号D619が供給される。サイクリックシフト回路６１１は、制御信号D619を元に、５つの復号結果D410を並べ替えるサイクリックシフトを行い、その結果を復号途中結果D411として、計算部４１２に供給する。
【０２７８】
計算部４１２は、５つの計算器４１２1乃至４１２5からなる。計算部４１２には、サイクリックシフト回路４１１から、計算部４１５による第２の演算の結果得られた５つの復号途中結果D411（第２の復号途中結果）vが供給されるとともに、復号途中結果格納用メモリ４１３から、前回、計算器４１２1乃至４１２5による第１の演算の結果得られた５つの復号途中結果D413（第１の復号途中結果）ujが供給され、その５つの復号途中結果D411と５つの復号途中結果D413が、計算器４１２1乃至４１２5にそれぞれ供給される。また、計算部４１２には、制御部４１７から制御信号D419が供給され、その制御信号D419が、計算器４１２1乃至４１２5に供給される。なお、制御信号D419は、５つの計算器４１２1乃至４１２5に共通の信号である。
【０２７９】
計算器４１２1乃至４１２5は、それぞれ復号途中結果D411と復号途中結果D413を用いて、式（７）と式（８）にしたがって第１の演算を行い、復号途中結果D412（vi）を求める。計算部４１２は、計算器４１２1乃至４１２5による演算の結果得られる検査行列の５つの１に対応する５つの復号途中結果D412を復号途中結果格納用メモリ４１３に供給する。
【０２８０】
復号途中結果格納用メモリ４１３は、例えば、５つの復号途中結果を同時に読み書き可能な、２つのシングルポートRAMから構成される。復号途中結果格納用メモリ４１３には、計算部４１２から５つの復号途中結果D412が供給されるとともに、制御部４１７から復号途中結果４１３の読み書きを制御する制御信号D420が供給される。
【０２８１】
復号途中結果格納用メモリ４１３は、制御信号D420に基づいて、計算部４１２から供給される５つの復号途中結果D412をまとめて格納すると同時に、既に格納してある５つの復号途中結果D412を読み出し、復号途中結果D413として、計算部４１２とサイクリックシフト回路４１４に供給する。即ち、復号途中結果格納用メモリ４１３は、計算部４１２とサイクリックシフト回路４１４に供給する復号途中結果D413の読み出しと、計算部４１２から供給される復号途中結果D412の書き込みとを、同時に行う。
【０２８２】
なお、復号途中結果格納用メモリ４１３には、計算部４１２の第１の演算により演算された検査行列Hのｉ列の、各行の１に対応する枝からのチェックノード演算の復号途中結果ujが格納されるので、復号途中結果格納用メモリ４１３に格納されるデータ量、即ち、復号途中結果格納用メモリ４１３に必要とされる記憶容量は、復号途中結果の量子化ビット数と、検査行列の１の数との乗算値となる。
【０２８３】
サイクリックシフト回路４１４には、復号途中結果格納用メモリ４１３から５つの復号途中結果D413（復号途中結果uj）が供給されるとともに、制御部４１７から、その復号途中結果D413に対応する検査行列の１が検査行列において元となる単位行列などを幾つサイクリックシフトしたものであるかの情報（Matrixデータ）を表す制御信号D421が供給される。サイクリックシフト回路４１４は、制御信号D421を元に、５つの復号途中結果D413を並べ替えるサイクリックシフトを行い、その結果を復号途中結果D414として、計算部４１５に供給する。
【０２８４】
計算部４１５は、５つの計算器４１５1乃至４１５5からなる。計算部４１５には、サイクリックシフト回路４１４から５つの復号途中結果D414が供給され、その復号途中結果D414が、計算器４１５1乃至４１５5のそれぞれに供給される。また、計算部４１５には、受信用メモリ４１７から５つの受信データD417（LDPC符号）が供給され、その受信データD417が、計算器４１５1乃至４１５5のそれぞれに供給される。さらに、計算部４１７には、制御部４１７から制御信号D422が供給され、その制御信号D422が計算器４１５1乃至４１５5に供給される。なお、制御信号D422は、５つの計算器４１７1乃至４１７5に共通の信号である。
【０２８５】
計算器４１５1乃至４１５5は、それぞれ復号途中結果D414と受信データD417とを用いて、式（５）にしたがって、それぞれ第２の演算を行い、復号途中結果D415を求める。計算部４１５は、計算器４１５1乃至４１５5の第２の演算の結果得られる５つの復号途中結果D415(v)を、復号途中結果格納用メモリ４１０に供給する。また、計算部４１５は、いま行う演算が最後の第２の演算である場合、その演算の結果得られる５つの復号途中結果D415を、最終的な復号結果として出力する。
【０２８６】
受信用メモリ４１６は、通信路を通して受信した受信値（符号ビット）D416から計算した符号ビットの０らしさの値である受信LLR（対数尤度比）を、受信データD417として格納する。
【０２８７】
即ち、受信用メモリ４１６の第１のアドレスには、検査行列の列に対応する受信データD417のうち、検査行列の第１列目から第５列目までに対応する受信データD417が格納される。そして、第２のアドレスには、検査行列の第６列目から第１０列目までに対応する受信データD417が格納され、第３アドレスには、検査行列の第１１列目から第１６列目までに対応する受信データD417が格納される。以後、同様に、第４アドレスから第１８アドレスまでに、検査行列の第１７列目から第９０列目までに対応する受信データD417が、５つずつ格納される。
【０２８８】
そして、受信用メモリ６１６は、既に格納している受信データD417を、バリアブルノード演算に必要となる順番に５つずつ読み出し、計算部４１５に供給する。
【０２８９】
なお、受信用メモリ４１６は、例えば、５つの受信データを同時に読み書き可能なシングルポートRAMから構成される。また、受信用メモリ４１６に格納されるデータ量、即ち、受信用メモリ３１５に必要とされる記憶容量は、LDPC符号の符号長と、受信データの量子化ビット数との乗算値である。さらに、受信用メモリ４１６のワード（word）数は、LDPC符号の符号長、即ち、検査行列の列数である９０を、同時に読み出す受信データD417の数である５で割り算した値の１８である。
【０２９０】
制御部４１７は、制御信号D418をサイクリックシフト回路４１１に、制御信号D419を計算部４１２に供給することにより、それぞれを制御する。また、制御部４１７は、制御信号D420を復号途中結果格納用メモリ４１３に、制御信号D421をサイクリックシフト回路４１４に、制御信号D421を計算部４１５にそれぞれ供給することにより、それぞれを制御する。
【０２９１】
復号途中結果格納用メモリ４１０、サイクリックシフト回路４１１、計算部４１２、復号途中結果格納用メモリ４１３、サイクリックシフト回路４１４、計算部４１５の順で、データが一巡することで、復号装置４００は、１回の復号を行うことができる。復号装置４００では、所定の回数だけ繰り返して復号が行われた後、計算部４１５による第２の演算の結果である復号途中結果D415が、最終的な復号結果として出力される。
【０２９２】
図２１は、図１８の計算部４１２の計算器４１２1の構成例を示すブロック図である。
【０２９３】
なお、図２１では、計算器４１２1について説明するが、計算器４１２2乃至計算器４１２5も同様に構成される。
【０２９４】
また、図２１では、前回の計算部４１２による第１の演算の結果得られる各復号途中結果(udv)が符号ビットを合わせて合計６ビット(bit)に量子化され、計算器４１５による第２の演算の結果得られる各復号途中結果（v）が９ビットに量子化されているものとして、計算器４１２1を表している。さらに、図２１の計算器４１２1には、クロックｃｋが供給され、このクロックｃｋは、必要なブロックに供給されるようになっている。そして、各ブロックは、クロックｃｋに同期して処理を行う。
【０２９５】
図２１の計算器４１２1は、制御部４１７から供給される制御信号D419に基づいて、復号途中結果格納用メモリ４１３から１つずつ読み込まれる、前回の計算部４１２による第１の演算の結果得られた復号途中結果D413（udv）と、サイクリックシフト回路４１１から1つずつ読み込まれる復号途中結果D411（v）とを用いて、式（７）と式（８）にしたがう第１の演算を行う。
【０２９６】
即ち、計算器４１２1には、サイクリックシフト回路４１１から供給される５つの９ビットの復号途中結果D411(v)のうちの、１つの復号途中結果D411が供給されるとともに、復号途中結果格納用メモリ４１３から供給される、前回の計算部４１２による演算の結果である５つの６ビットの復号途中結果D413（uj）のうちの、前回の計算部４１２による演算の結果である１つの復号途中結果D413が供給され、その９ビットの復号途中結果D411（v）と６ビットの復号途中結果D413（udv）が、減算器４３１に供給される。また、計算器４１２1には、制御部４１７から制御信号D419が供給され、その制御信号D419がセレクタ４３５とセレクタ４４２に供給される。
【０２９７】
減算器４３１は、９ビットの復号途中結果D411（v）から６ビットの復号途中結果D413（uj）を減算し、その６ビットの減算値D431を出力する。即ち、減算器４３１は、式（８）にしたがって演算を行い、その演算の結果である減算値D431（vi）を出力する。
【０２９８】
減算器４３１により出力された６ビットの減算値D431のうち、最上位ビットの正負を示す符号ビットD432（sign（vi））がEXOR回路４４０に供給され、下位５ビットの絶対値D433（|vi|）がLUT４３２に供給される。
【０２９９】
LUT４３２は、絶対値D433(|vi|)に対して、式（７）におけるφ(|vi|)の演算を行った５ビットの演算結果D434（φ(|vi|)）を読み出し、加算器４３３とFIFOメモリ４３８に供給する。
【０３００】
加算器４３３は、演算結果D434（φ(|vi|)）とレジスタ４３４に格納されている９ビットの値D435とを加算することにより、演算結果D434を積算し、その結果得られる９ビットの積算値をレジスタ４３４に再格納する。なお、検査行列の1行に亘る全ての１に対応する復号途中結果D411から求められた絶対値D433(|vi|)に対する演算結果が積算された場合、レジスタ４３４はリセットされる。
【０３０１】
検査行列の1行に亘る復号途中結果D411が１つずつ読み込まれ、レジスタ４３４に1行分の演算結果D434が積算された積算値が格納された場合、制御部４１７から供給される制御信号D419は、０から１に変化する。例えば、行の重み（row weight）が「９」である場合、制御信号D419は、１から８クロック目までは、「０」となり、９クロック目では「１」となる。
【０３０２】
制御信号D419が「１」の場合、セレクタ４３５は、レジスタ４３４に格納されている値、即ち、検査行列の1行に亘る全ての１に対応する復号途中結果D411（復号途中結果v）から求められたφ(|vi|)が積算された９ビットの値D435（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）を選択し、値D436として、レジスタ４３６に出力して格納させる。レジスタ４３６は、格納している値D436を、９ビットの値D437として、セレクタ４３５と加算器４３７に供給する。制御信号D419が「０」の場合、セレクタ４３５は、レジスタ４３６から供給された値D437を選択し、レジスタ４３６に出力して再格納させる。即ち、検査行列の1行に亘る全ての１に対応する復号途中結果D411（復号途中結果v）から求められたφ(|vi|)が積算されるまで、レジスタ４３６は、前回積算されたφ(|vi|)を、セレクタ４３５と加算器４３７に供給する。
【０３０３】
一方、FIFOメモリ４３８は、レジスタ４３６から新たな値D437（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）が出力されるまでの間、LUT４３２が出力した演算結果D434（φ(|vi|)）を遅延し、５ビットの値D438として減算器４３７に供給する。減算器４３７は、レジスタ４３６から供給された値D437から、FIFOメモリ４３８から供給された値D438を減算し、その減算結果を、５ビットの減算値D439としてLUT４３９に供給する。即ち、減算器４３７は、検査行列の1行に亘る全ての１に対応する復号途中結果D411（復号途中結果v）から求められたφ(|vi|)の積算値から、求めたい枝に対応する復号途中結果、即ち、検査行列の所定の１に対応する復号途中結果D411（復号途中結果v）から求められたφ(|vi|)を減算して、その減算値（ｉ＝１からｉ＝ｄc−１までのΣφ(|vi|)）を減算値D439としてLUT４３９に供給する。
【０３０４】
LUT４３９は、減算値D439（ｉ＝１からｉ＝ｄc−１までのΣφ(|vi|)）に対して、式（７）におけるφ-1（Σφ(|vi|)）の演算を行った５ビットの演算結果D440（φ-1(Σφ(|vi|)))を出力する。
【０３０５】
以上の処理と並行して、EXOR回路４４０は、レジスタ４４１に格納されている１ビットの値D442と符号ビットD432との排他的論理和を演算することにより、符号ビットどうしの乗算を行い、１ビットの乗算結果D441をレジスタ４４１に再格納する。なお、検査行列の1行に亘る全ての１に対応する復号途中結果D411から求められた符号ビットD432が乗算された場合、レジスタ４４１はリセットされる。
【０３０６】
検査行列の1行に亘る全ての１に対応する復号途中結果D411から求められた符号ビットD432が乗算された乗算結果D441（ｉ＝１からｄcまでのΠsign(vi)）がレジスタ４４１に格納された場合、制御部４１７から供給される制御信号D419は、「０」から「１」に変化する。
【０３０７】
制御信号D419が「１」の場合、セレクタ４４２は、レジスタ４４１に格納されている値、即ち、検査行列の1行に亘る全ての１に対応する復号途中結果D411から求められた符号ビットD432が乗算された値D442（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）を選択し、１ビットの値D443としてレジスタ４４３に出力して格納させる。レジスタ４４３は、格納している値D443を、１ビットの値D444としてセレクタ４４２とEXOR回路４４５に供給する。制御信号D419が「０」の場合、セレクタ４４２は、レジスタ４４３から供給された値D444を選択し、レジスタ４４３に出力して再格納させる。即ち、検査行列の1行に亘る全ての１に対応する復号途中結果D411（復号途中結果v）から求められた符号ビットD432が乗算されるまで、レジスタ４４３は、前回格納した値を、セレクタ４４２とEXOR回路４４５に供給する。
【０３０８】
一方、FIFOメモリ４４４は、レジスタ４４３から新たな値D444（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）がEXOR回路４４５に供給されるまでの間、符号ビットD432を遅延し、１ビットの値D445としてEXOR回路４４５に供給する。EXOR回路４４５は、レジスタ４４３から供給された値D444と、FIFOメモリ４４４から供給された値D445との排他的論理和を演算することにより、値D444を、値D445で除算し、１ビットの除算結果を除算値D446として出力する。即ち、EXOR回路４４５は、検査行列の1行に亘る全ての１に対応する復号途中結果D411から求められた符号ビットD432（sign(vi)）の乗算値を、検査行列の所定の１に対応する復号途中結果D411から求められた符号ビットD432（sign(vi)）で除算して、その除算値（ｉ＝１からｉ＝ｄc−１までのΠsign(vi)）を除算値D446として出力する。
【０３０９】
計算器４１２1では、LUT４３９から出力された５ビットの演算結果D440を下位５ビットとするとともに、EXOR回路４４５から出力された１ビットの除算値D446を最上位ビットとする合計６ビットが復号途中結果D412（復号途中結果uj）として出力される。
【０３１０】
以上のように、計算器４１２1では、式（７）と式（８）の演算が行われ、復号途中結果ujが求められる。
【０３１１】
なお、図１５の検査行列の行の重みの最大は９であるため、即ち、計算器４１２1に供給される復号途中結果D411（v）と復号途中結果D413（udv）の最大数は９であるため、計算器４１２1は、９個の復号途中結果D411から求められる９個の演算結果D434（φ(|vi|)）を遅延させるFIFOメモリ４３８と、９個の符号ビットD432を遅延させるFIFOメモリ４４４を有している。行の重みが９未満の行のメッセージを計算するときには、FIFOメモリ４３８とFIFOメモリ４４４における遅延量が、その行の重みの値に減らされる。
【０３１２】
図２２は、図１８の計算部４１５の計算器４１５1の構成例を示すブロック図である。
【０３１３】
なお、図２２では、計算器４１５1について説明するが、計算器４１５2乃至計算器４１５5も同様に構成される。
【０３１４】
また、図２２では、計算器４１２による第１の演算の結果得られる各復号途中結果（uj）が符号ビットを合わせて合計６ビットに量子化されているものとして、計算器４１５1を表している。さらに、図２２の計算器４１５1には、クロックｃｋが供給され、このクロックｃｋは、必要なブロックに供給されるようになっている。そして、各ブロックは、クロックｃｋに同期して処理を行う。
【０３１５】
図２２の計算器４１５1は、制御部４１７から供給される制御信号D422に基づいて、受信用メモリ４１６から１つずつ読み込まれる受信データD417（受信値u0i）と、サイクリックシフト回路４１４から１つずつ読み込まれる復号途中結果D414（uj）とを用いて、式（５）にしたがう第２の演算を行う。
【０３１６】
即ち、計算器４１５1では、サイクリックシフト回路４１４から、検査行列の各行の１に対応する６ビットの復号途中結果D414（復号途中結果uj）が１つずつ読み込まれ、その復号途中結果D414が、加算器４７１に供給される。また、計算器４１５1では、受信用メモリ４１６から６ビットの受信データD417が１つずつ読み込まれ、加算器４７５に供給される。さらに、計算器４１５1には、制御部４１７から制御信号D422が供給され、その制御信号D422は、セレクタ４７３に供給される。
【０３１７】
加算器４７１は、復号途中結果D414（復号途中結果uj）とレジスタ４７２に格納されている９ビットの値D471とを加算することにより、復号途中結果D414を積算し、その結果得られる９ビットの積算値を、レジスタ４７２に再格納する。なお、検査行列の１列に亘る全ての１に対応する復号途中結果D414が積算された場合、レジスタ４７２はリセットされる。
【０３１８】
検査行列の１列に亘る復号途中結果D414が１つずつ読み込まれ、レジスタ４７２に１列分の復号途中結果D414が積算された値が格納された場合、制御部４１７から供給される制御信号D422は、「０」から「１」に変化する。例えば、列の重みが「５」である場合、制御信号D422は、１から４クロック目までは「０」となり、５クロック目では「１」となる。
【０３１９】
制御信号D422が「１」の場合、セレクタ４７３は、レジスタ４７２に格納されている値、即ち、検査行列の１列に亘る全ての枝からの復号途中結果D414（復号途中結果uj）が積算された９ビットの値D471（ｊ＝１からｄVまでのΣuj)を選択し、レジスタ４７４に出力して格納させる。レジスタ４７４は、格納している値D471を、９ビットの値D472として、セレクタ４７１と加算器４７５に供給する。制御信号D422が「０」の場合、セレクタ４７３は、レジスタ４７４から供給された値D472を選択し、レジスタ４７４に出力し再格納させる。即ち、検査行列の１列に亘る全ての枝からの復号途中結果D414（復号途中結果uj）が積算されるまで、レジスタ４７４は、前回積算された値を、セレクタ４７３と加算器４７５に供給する。
【０３２０】
加算器４７５は、９ビットの値D472と、受信用メモリ４１６から供給された６ビットの受信データD417とを加算して、その結果得られる６ビットの値を復号途中結果D415（復号途中結果v）として出力する。
【０３２１】
以上のように、計算器４１５1では、式（５）の演算が行われ、復号途中結果vが求められる。
【０３２２】
なお、図８の検査行列の列の重みの最大は５であるため、即ち、計算器４１５1に供給される復号途中結果ujの最大数は５であるため、計算器４１５1は、６ビットの復号途中結果ujを最大５個加算する。従って、計算器４１５1の出力は、９ビットの値となっている。
【０３２３】
図２３は、図１８の復号途中結果格納用メモリ４１３の構成例を示すブロック図である。
【０３２４】
復号途中結果格納用メモリ４１３は、スイッチ５０１と５０４、および２つのシングルポートRAMである復号途中結果格納用RAM５０２と５０３から構成される。
【０３２５】
この復号途中結果格納用メモリ４１３の各部について詳細に説明する前に、まず、復号途中結果格納用RAM５０２と５０３へのデータの格納方法について説明する。
【０３２６】
復号途中結果格納用RAM５０２と５０３は、計算部４１２による第１の演算の結果得られ、スイッチ５０１を介して供給された復号途中結果D412を格納する。
【０３２７】
具体的には、復号途中結果格納用RAM５０２の第１アドレスから第９アドレスには、図１５の検査行列Hの第１行目から第５行目までの１に対応する復号途中結果D412(D501)が、各行ともに横方向（列方向）に詰めた形に（０を無視した形で）格納される。
【０３２８】
即ち、第ｊ行第ｉ列を、(j,ｉ)と表すこととすると、復号途中結果格納用RAM５０２の第１アドレスには、図１５の検査行列の構成行列である(1,1)から(5,5)の５×５の単位行列の１に対応するデータが、第２アドレスには、図１５の検査行列の構成行列である(1,21)から(5,25)のシフト行列（５×５の単位行列を右方向に３つだけサイクリックシフトしたシフト行列）の１に対応するデータが格納される。第３アドレスから第８アドレスも同様に図１５の検査行列の構成行列と対応づけてデータが格納される。そして、第９アドレスには、検査行列の(1,86)から(5,90)のシフト行列（５×５の単位行列のうちの１行目の１を０に置き換えて１つだけ左にサイクリックシフトしたシフト行列）の１に対応するデータが格納される。ここで、図１５の検査行列の(1,86)から(5,90)のシフト行列においては、１行目に１がないため、第９アドレスにはデータが格納されない。
【０３２９】
復号途中格納用RAM５０２の第１０アドレスから第１８アドレスには、図１５の検査行列の第１１行目から第１５行目までの１に対応するデータが格納される。即ち、第１０アドレスには、検査行列の(11,6)から(15,10)の５×５の単位行列を右に３つだけサイクリックシフトした行列の１に対応するデータが格納され、第１１アドレスには、検査行列の(11,11)から（15,15）の和行列（５×５の単位行列と、５×５の単位行列を右に３つだけサイクリックシフトしたシフト行列との和である和行列）を構成するシフト行列の１に対応するデータが格納される。また、第１２アドレスには、検査行列の(11,6)から(15,10)の和行列を構成する単位行列の１に対応するデータが格納される。以下、第１３アドレスから第１８アドレスについても、検査行列に対応づけてデータが格納される。
【０３３０】
即ち、重みが２以上の構成行列については、その構成行列を、重みが１であるP×Pの単位行列、そのコンポーネントである１のうち１個以上が０になった準単位行列、または単位行列もしくは準単位行列をサイクリックシフトしたシフト行列のうちの複数の和の形で表現したときの、その重みが１の単位行列、準単位行列、またはシフト行列の１の位置に対応するデータ（単位行列、準単位行列、またはシフト行列に属する枝に対応するメッセージの復号途中結果）は、同一アドレスに格納される。
【０３３１】
同様に、復号途中格納用RAM５０２の第１９アドレスから第２７アドレスには、図１５の検査行列に対応づけて、第２１行目から第２５行目までの１に対応するデータが格納される。即ち、復号途中結果格納用RAM５０２のワード数は、２７である。
【０３３２】
復号途中結果格納用RAM５０３の第１アドレスから第９アドレスには、図１５の検査行列Hの第６行目から第１０行目までの１に対応する復号途中結果D412(D502)が、各行ともに横方向（列方向）に詰めた形に（０を無視した形で）格納される。
【０３３３】
即ち、復号途中結果格納用RAM５０３の第１アドレスには、検査行列の構成行列である(6,1)から(10,5)の和行列（５×５の単位行列を右に１つだけサイクリックシフトした第１のシフト行列と、右に２つだけサイクリックシフトした第２のシフト行列の和である和行列）を構成する第１のシフト行列の１に対応するデータが、第２アドレスには、検査行列の構成行列である(6,1)から(10,5)の和行列を構成する第２のシフト行列の１に対応するデータが格納される。以下、第３アドレスから第９アドレスも同様に検査行列の構成行列と対応づけてデータが格納される。
【０３３４】
同様に、復号途中格納用RAM５０３の第１０アドレスから第１８アドレスには、図１５の検査行列の第１６行目から第２０行目までの１に対応するデータが、第１９アドレスから第２７アドレスには、検査行列の第２６行目から第３０行目までの1に対応するデータが、図１５の検査行列に対応づけて格納される。即ち、復号途中結果格納用RAM５０３のワード数は、２７である。
【０３３５】
上述したように、復号途中結果格納用RAM５０２と５０３のワード(word)数は、２７である。即ち、ワード数は、検査行列の行の重み(row weight)の９と行数の３０とを乗算し、その乗算結果(検査行列の１の数)を、同時に読み出す復号途中結果D501の数の５で除算し、さらに、復号途中結果格納用メモリ４１３が有する復号途中結果格納用RAMの個数の２で除算した値となる。
【０３３６】
以下、図２３の復号途中結果格納用メモリ４１３の各部の動作について詳細に説明する。
【０３３７】
復号途中結果格納用メモリ４１３には、計算部４１２により第１の演算が行われる場合、計算部４１２から第１の演算の結果得られる復号途中結果D412（uj）が供給され、その復号途中結果D412が復号途中結果格納用RAM５０２または復号途中結果格納用RAM５０３のうちの一方の所定のアドレスに書き込まれると同時に、他方から、前回の計算部４１２による第１の演算の結果得られた復号途中結果D412（uj）が読み出され、計算部４１２に出力される。一方、計算部４１５により第２の演算が行われる場合、復号途中結果格納用メモリ４１３は、復号途中結果格納用RAM５０２または復号途中結果格納用RAM５０３に書き込みを行わず、どちらか一方のRAMの所定のアドレスから復号途中結果を読み出して、サイクリックシフト回路４１４に供給する。
【０３３８】
スイッチ５０１には、計算部４１２から５つの復号途中結果D412が供給されるとともに、その復号途中結果D412を書き込むメモリとして、復号途中結果格納用RAM５０２または復号途中結果格納用RAM５０３の一方の選択を表す制御信号D4201が制御部４１７から供給される。スイッチ５０１は、制御信号D4201に基づいて、復号途中結果格納用RAM５０２または復号途中結果格納用RAM５０３の一方を選択し、その選択した一方に、５つの復号途中結果D412を供給する。
【０３３９】
復号途中結果格納用RAM５０２には、スイッチ５０１から５つの復号途中結果D412が、復号途中結果D501として供給されるとともに、制御部４１７からアドレスを表す制御信号D4202が供給される。復号途中結果格納用RAM５０２は、制御信号D4022が表すアドレスに既に格納されている前回の計算部４１２による第１の演算の結果得られた５つの復号途中結果D501を読み出し、復号途中結果D503としてスイッチ５０４に供給する。また、復号途中結果格納用RAM５０２は、制御信号D4022が表すアドレスに、スイッチ５０１から供給された５つの復号途中結果D501を格納する(書き込む)。
【０３４０】
復号途中結果格納用RAM５０３には、スイッチ５０１から５つの復号途中結果D412が、復号途中結果D502として供給されるとともに、制御部４１７からアドレスを表す制御信号D4203が供給される。復号途中結果格納用RAM５０３は、制御信号D4203が表すアドレスに既に格納されている前回の計算部４１２による第１の演算の結果得られた５つの復号途中結果D502を読み出し、復号途中結果D504としてスイッチ５０４に供給する。また、復号途中結果格納用RAM５０２は、制御信号D4203が表すアドレスに、スイッチ５０１から供給された５つの復号途中結果D502を格納する(書き込む)。
【０３４１】
スイッチ５０４には、復号途中結果格納用RAM５０２から復号途中結果D503が供給されるか、あるいは復号途中結果格納用RAM503から復号途中結果D504が供給される。また、制御部４１７から、復号途中結果格納用RAM５０２または復号途中結果格納用RAM５０３の一方の選択を表す制御信号D4204が供給される。スイッチ５０４は、制御信号D4201に基づいて、復号途中結果格納用RAM５０２または復号途中結果格納用RAM５０３の一方を選択し、その選択した一方から供給された５つの復号途中結果を、５つの復号途中結果D413として計算部４１２とサイクリックシフト回路４１４に供給する。
【０３４２】
図２４は、復号途中結果格納用メモリ４１３の復号途中結果格納用RAM５０２と復号途中結果格納用RAM５０３の読み出しと書き込みの動作を説明するタイミングチャートである。
【０３４３】
なお、図２４において、横軸は、時間（ｔ）を表している。
【０３４４】
復号途中結果格納用メモリ４１３では、計算部４１２により第１の演算が行われる場合、復号途中結果格納用RAM５０２が、制御信号D4202に基づいて、既に格納している、前回の計算部４１２の第１の演算の結果得られた復号途中結果D501のうち、同一アドレスに格納している検査行列の第１行目から第５行目までの１に対応する復号途中結果D501を、５つ単位で９回読み出し、スイッチ５０４を介して、計算部４１２に供給する。即ち、図１５の検査行列Hの行重みは、９であるため、検査行列Hの各行の１に対応する復号途中結果は９つあり、復号途中結果格納用RAM５０２は、第１行目から第５行目までの１に対応する５つの復号途中結果D501を、５つ単位で９回読み出す。
【０３４５】
次に、復号途中結果格納用RAM５０３は、制御信号D4203に基づいて、既に格納している、前回の計算部４１２による第１の演算の結果得られた復号途中結果D502のうち、同一アドレスに格納している検査行列の第６行目から第１０行目までの１に対応する復号途中結果D502を、５つ単位で９回続けて読み出し、スイッチ５０４を介して、計算部４１２に供給する。それと同時に、復号途中結果格納用RAM５０２には、計算部４１２により、いま行われている第１の演算の結果得られる検査行列の第１行目から第５行目までの１に対応する５つの復号途中結果D412がスイッチ５０１を介して、復号途中結果D501として供給され、復号途中結果格納用RAM５０２は、その復号途中結果D501を、制御信号D4202に基づいて、既に読み出された復号途中結果D503が格納されていたアドレスに９回続けて格納する。
【０３４６】
その後、復号途中結果格納用RAM５０２は、制御信号D4202に基づいて、既に格納している、前回の計算部４１２による第１の演算の結果得られた復号途中結果D501のうち、同一アドレスに格納している検査行列の第１１行目から第１５行目までの１に対応する復号途中結果D501を、５つ単位で９回続けて読み出し、スイッチ５０４を介して、計算部４１２に供給する。それと同時に、復号途中結果格納用RAM５０３には、計算部４１２により、いま行われている第１の演算の結果得られる検査行列の第６行目から第１０行目までの１に対応する５つの復号途中結果D412がスイッチ５０１を介して、復号途中結果D502として供給され、復号途中結果格納用RAM５０３は、その復号途中結果D502を、制御信号D4203に基づいて、既に読み出された復号途中結果D504が格納されていたアドレスに９回続けて格納する。
【０３４７】
以後、同様に、計算部４１２による第１の演算の結果得られる検査行列の全ての１に対応する復号途中結果が、復号途中結果格納用RAM５０２または復号途中結果格納用RAM５０３に格納されるまで、復号途中結果格納用RAM５０２と復号途中結果格納用RAM５０３は、９回ずつの読み出しまたは書き込みを交互に行う。
【０３４８】
復号途中結果格納用メモリ４１３では、計算部４１５による第２の演算が行われる場合、制御信号D4202に基づいて、復号途中結果格納用RAM５０２から既に格納されている第１の演算の結果得られる復号途中結果D503を読み出すか、あるいは制御信号D4203に基づいて、復号途中結果格納用RAM５０３から、既に格納されている第１の演算の結果得られる復号途中結果D504を読み出し、その読み出した復号途中結果をスイッチ５０４を介して、サイクリックシフト回路４１４に供給する。
【０３４９】
図２５は、図１８の復号装置４００の復号処理を説明するフローチャートである。この処理は、例えば、受信用メモリ４１６に復号すべき受信データが格納されたとき、開始される。
【０３５０】
ステップＳ５０において、サイクリックシフト回路４１４は、復号途中結果格納用メモリ４１３から供給された後述するステップＳ５６で格納される５つの復号途中結果D413を、サイクリックシフトし、計算部４１５に供給する。
【０３５１】
具体的には、サイクリックシフト回路４１４には、復号途中結果格納用メモリ４１３から５つの復号途中結果D413が供給されるとともに、制御部４１７から、その復号途中結果D413に対応する検査行列の１が検査行列において元となる単位行列などを幾つサイクリックシフトしたものであるかの情報（Matrixデータ）を表す制御信号D421が供給される。サイクリックシフト回路４１４は、制御信号D421を元に、５つの復号途中結果D413をサイクリックシフトし（並べ替え）、その結果を復号途中結果D414として、計算部４１５に供給する。
【０３５２】
なお、受信用メモリ４１６から供給された受信データD417に対して、まだ第１の演算が行われておらず、復号途中結果格納用メモリ４１３に復号途中結果D413が格納されていない場合、計算部４１５は、復号途中結果ujを初期値に設定する。
【０３５３】
ステップＳ５１において、計算部４１５は、第２の演算を行い、その演算の結果である復号途中結果D415を復号途中結果格納用メモリ４１０に供給する。
【０３５４】
具体的には、計算部４１５には、ステップＳ５０でサイクリックシフト回路４１４から５つの復号途中結果D414が供給されるとともに、受信データ用メモリ４１６から５つの受信データD417が供給され、復号途中結果D415と受信データD417が、計算部４１５の計算器４１５1乃至４１５5それぞれに１つずつ供給される。さらに、計算部４１５には、制御部４１７から制御信号D422が供給され、その制御信号D422が計算器４１５1乃至４１５5に供給される。
【０３５５】
計算器４１５1乃至４１５5は、復号途中結果D414と受信データD417を用いて、制御信号D422に基づいて、式（５）にしたがって、それぞれ演算を行い、その演算の結果得られる検査行列の列に対応する復号途中結果D415(v)を復号途中結果格納用メモリ４１０に供給する。
【０３５６】
ステップＳ５１の処理後は、ステップＳ５２に進み、復号途中結果格納用メモリ４１０は、ステップＳ５１で計算部４１５から供給された復号途中結果D415を、同一アドレスに格納し、ステップＳ５３に進む。
【０３５７】
ステップＳ５３において、制御部４１７は、計算部４１５により、検査行列の列に対応する全ての復号途中結果D415が演算されたかどうかを判定し、全ての復号途中結果D415が演算されていないと判定した場合、ステップＳ５０に戻り、上述した処理を繰り返す。
【０３５８】
一方、ステップＳ５３において、制御部４１７は、計算部４１５により、検査行列の列に対応する全ての復号途中結果D415が演算されたと判定した場合、ステップＳ５４に進み、サイクリックシフト回路４１１は、復号途中結果格納用メモリ４１０から供給される復号途中結果D410(v)をサイクリックシフトする。
【０３５９】
具体的には、サイクリックシフト回路４１１には、復号途中結果格納用メモリ４１０から５つの復号途中結果D410が供給されるとともに、制御部４１７から、その復号途中結果D410に対応する検査行列の１が検査行列において元となる単位行列などを幾つサイクリックシフトしたものであるかの情報（Matrixデータ）を表す制御信号D418が供給される。サイクリックシフト回路４１１は、制御信号D418を元に、５つの復号途中結果D410をサイクリックシフトし（並べ替え）、その結果を復号途中結果D411として、計算部４１２に供給する。
【０３６０】
ステップＳ５４の処理後は、ステップＳ５５に進み、計算部４１２は、第１の演算を行い、その演算結果である復号途中結果D412をサイクリックシフト回路４１４に供給する。
【０３６１】
具体的には、計算部４１２には、ステップＳ５４でサイクリックシフト回路４１１から５つの復号途中結果D411(v)が供給されるとともに、後述するステップＳ５６で既に格納された前回の計算部４１２による第１の演算の結果得られた５つの復号途中結果D412（D413）(uj)が供給され、その復号途中結果D411と復号途中結果D413が、計算部４１２の計算器４１２1乃至４１２5のそれぞれに１つずつ供給される。さらに、計算部４１２には、制御部４１７から制御信号D419が供給され、その制御信号D419が計算器４１２1乃至４１２5に供給される。
【０３６２】
計算器４１２1乃至４１２5は、それぞれ復号途中結果D411と復号途中結果D413とを用いて、制御信号D419に基づいて、式（７）と式（８）にしたがって、それぞれ演算を行い、その演算の結果得られる復号途中結果D412（uj）を復号途中結果格納用メモリ４１３に供給する。
【０３６３】
ステップＳ５５の処理後は、ステップＳ５６に進み、復号途中結果格納用メモリ４１３は、ステップＳ５５で計算部４１２から供給された５つの復号途中結果D412を、同一のアドレスに格納し、ステップＳ５７に進む。
【０３６４】
ステップＳ５７において、制御部４１７は、計算部４１２により、検査行列の全ての1に対応する復号途中結果D412が演算されたかどうかを判定し、全ての復号途中結果が演算されていないと判定した場合、ステップＳ５４に戻り、上述した処理を繰り返す。
【０３６５】
一方、ステップＳ５７において、制御部４１７は、計算部４１２により、全ての１に対応する復号途中結果D412が演算されたと判定した場合、処理を終了する。
【０３６６】
なお、復号装置４００は、復号回数だけ図２５の復号処理を繰り返し行ない、最後の第２の演算の結果得られるメッセージD415が、最終的な復号結果として出力される。
【０３６７】
上述した説明では、復号途中結果格納用メモリ４１３は、２つのシングルポートRAMから構成にしたが、１つのRAMに対して読み出しと書き込みが同時に起こらないようにすれば、３つ以上のRAMから構成してもよい。例えば、RAMの物理的なビットが足りない場合には、複数のRAMを用いて同じ制御信号を与えることで、論理的に１つのRAMとみなすことができる。
【０３６８】
また、枝データ（枝に対応するメッセージ）が欠けている箇所に関しては、メモリ格納時（復号途中結果格納用メモリ４１０と４１３へのデータ格納時）には、何のメッセージも格納せず、また、演算時（計算部４１２での第１の演算時と計算部４１５での第２の演算時）にも何の演算も行わない。
【０３６９】
図２６は、本発明を適用した図１５の検査行列で表現されるLDPC符号を復号する復号装置の他の一実施の形態の構成例を示すブロック図である。
【０３７０】
図２６の復号装置６００では、図１６の枝データ格納メモリ３１６が、枝データ格納メモリ３１６に比べて容量の小さい復号途中結果格納用メモリ６１３になっている。
【０３７１】
復号装置６００は、復号途中結果格納用メモリ６１０、サイクリックシフト回路６１１、５つの計算器６１２1乃至計算器６１２5からなる計算部６１２、復号途中結果格納用メモリ６１３、サイクリックシフト回路６１４、５つの計算器６１５1乃至計算器６１５5からなる計算部６１５、受信用メモリ６１６、および制御部６１７から構成される。
【０３７２】
ここで、図２７乃至図３０を用いて、図２６の計算部６１２の計算器６１２1乃至計算器６１２5、および図３０の計算部６１５の計算器６１５1乃至計算器６１５5と、図１０のチェックノード計算器１０１および図１１のバリアブルノード計算器１０３との関係について説明する。
【０３７３】
図２７と図２８は、前述の図１０のチェックノード計算器１０１と図１１のバリアブルノード計算器１０３とそれぞれ同一の図である。また、図２９は、計算器６１２k（k=1,2,・・・,5）の構成例を示しており、図３０は、計算器６１５k（k=1,2,・・・,5）の構成例を示している。
【０３７４】
図２６の復号装置６００では、計算器６１２kがチェックノード演算を行い、計算部６１５kが、バリアブルノード演算をおこなうのではなく、計算器６１２kがチェックノード演算の一部を、計算器６１５kがチェックノード演算の他の一部とバリアブルノード演算を行う。
【０３７５】
即ち、図２９の計算器６１２kは、ブロックＤ'とＥ'から構成される。ブロックＤ'は、図２７のチェックノード計算器１０１の一部である、検査行列の各列の全ての枝に対応するメッセージviの絶対値に対してφの演算を行った値を積算するブロックＤと同様に構成されている。また、ブロックＥ'は、検査行列の各列の全ての枝に対応するメッセージviの符号ビットを乗算するブロックＥと同様に構成されている。
【０３７６】
一方、図３０の計算器６１５kは、ブロックＦ'、Ｇ'、Ｈ'とから構成される。ブロックＦ'は、図１９のチェックノード計算器１０１の他の一部である、検査行列の各列の全ての枝に対応するメッセージviの符号ビットの乗算値から、求めたい枝に対応するメッセージviの符号ビットを除算するとともに、検査行列の各列の全ての枝に対応するメッセージviの絶対値に対してφの演算を行った値の積算値から、求めたい枝に対応するメッセージviの絶対値に対してφの演算を行った値を減算した値に対して、φ-1の演算を行うブロックＦと同様に構成されている。また、ブロックＧ'は、メッセージviの絶対値に対してφの演算を行うブロックＧと同様に構成され、ブロックＨ'は、図２０のバリアブルノード計算器１０３のバリアブルノード演算を行うブロックＨと同様に構成されている。
【０３７７】
そして、図２９の計算器６１２kは、ブロックＡとブロックＢによる演算の結果、即ち、チェックノード演算の一部を行った復号途中結果wを復号途中結果格納用メモリ６１３に供給し、図３０の計算器６１５kは、チェックノード演算の他の一部とバリアブルノード演算を行った復号途中結果vi'を復号途中結果格納用メモリ６１０に供給する。
【０３７８】
従って、図２６の復号装置６００は、計算器６１２kの演算と計算器６１５kの演算とを交互に行うことにより、チェックノード演算とバリアブルノード演算を行い、復号を行うことができる。
【０３７９】
なお、図３０の計算器６１５kでは、復号途中結果格納用メモリ６１０に格納されている求めたい枝に対応する復号途中結果vi'を用いて、ブロックＣで、計算器６１２kの演算の結果得られる復号途中結果wの絶対値から、求めたい枝に対応する復号途中結果vi'を減算するとともに、復号途中結果wの符号ビットと、求めたい枝に対応する復号途中結果vi'の符号ビットを乗算するので、図２７のFIFOメモリ１２７とFIFOメモリ１３３が必要ない。
【０３８０】
次に、計算部６１２の計算器６１２1乃至計算器６１２5で行われる演算と、計算部６１５の計算器６１５1乃至計算器６１５5で行われる演算について、式を用いて説明する。
【０３８１】
計算部６１２は、以下の式（９）にしたがう第１の演算を行い、その第１の演算の結果である復号途中結果wを復号途中結果格納用メモリ６１３に供給して格納させる。計算部６１５は、上述した式（１）と、以下の式（１０）と（１１）にしたがう第２の演算を行い、その第２の演算の結果である復号途中結果vi'を復号途中結果格納用メモリ６１０に供給して格納させる。
【０３８２】
【数９】
2004364233.tif 000011
・・・（９）
【０３８３】
【数１０】
2004364233.tif 000012
・・・（１０）
【０３８４】
【数１１】
2004364233.tif 000013
・・・（１１）
【０３８５】
即ち、式（９）にしたがう第１の演算の結果得られる復号途中結果ｗは、式（１）、式（１０）、式（１１）にしたがう第２の演算の結果得られる検査行列Hのｊ行のすべての１に対応するチェックノード演算の復号途中結果vi'の絶対値|vi'|の総和と符号ビットsign（vi'）の乗算値とを乗算したものであるので、上述した式（７）にしたがうチェックノード演算によって求められるujは、式（１０）に示すように、式（９）にしたがう第１の演算の結果得られる復号途中結果ｗの絶対値|w|から、検査行列Hのｊ行の、各列の“１”（枝）に対応する（複数の）復号途中結果vi'のうち、メッセージを求めたい枝に対応する復号途中結果vi'の絶対値|vi'|を引いた値を用いて表すことができる。
【０３８６】
復号装置６００では、計算部６１２による式（９）にしたがう第１の演算と、計算部６１５による式（１）、式（１０）、式（１１）にしたがう第２の演算とが交互に行われ、計算部６１５が、最後の第１の演算の結果を用いて、式（５）にしたがう演算を行い、その演算結果を復号結果として出力することにより、LDPC符号の繰り返し復号を行う。
【０３８７】
即ち、復号装置６００では、計算部６１２が、計算部６１５による第２の演算の結果である検査行列Hのｊ行のすべての1に対応する復号途中結果vi'を用いて、第１の演算を行い、その演算の結果得られる検査行列の各行に対応する復号途中結果wを復号途中結果格納用メモリ６１３に格納する。従って、復号途中結果格納用メモリ６１３の容量は、検査行列の“１”の数より少ない検査行列の行数と復号途中結果wの量子化ビット数とを乗算した値となる。なお、計算部６１５は、計算部６１２による第１の演算の結果である検査行列Hのｉ列の各行に対応する復号途中結果wと受信値u0iを用いて、第２の演算を行い、その演算の結果得られる検査行列のｉ列の１（枝）に対応するチェックノード演算の復号途中結果vi'を復号途中結果格納用メモリ６１０に格納する。従って、復号途中結果格納用メモリ６１０に必要な容量は、バリアブルノード演算の結果を格納する図１６の枝データ格納メモリ３１１と同様に、検査行列の１の数と復号途中結果vi'の量子化ビット数とを乗算した値となる。
【０３８８】
従って、復号装置６００では、図１６の枝データ格納メモリ３１１に比べて、復号途中結果格納用メモリ６１０のメモリの容量を削減することができ、これにより、復号装置６００の回路規模を小さくすることができる。
【０３８９】
以下、図２６の復号装置６００の各部の動作について詳細に説明する。
【０３９０】
復号途中結果格納用メモリ６１０は、制御信号D618に基づいて、計算部６１５から供給される５つの復号途中結果D615をまとめて格納すると同時に、既に格納してある５つの復号途中結果D615を読み出し、復号途中結果D610として、サイクリックシフト回路６１１と計算部６１５に供給する。即ち、復号途中結果格納用メモリ６１０は、サイクリックシフト回路６１１に供給する復号途中結果D610の読み出しと、計算部６１５から供給される復号途中結果D615の書き込みとを、同時に行う。
【０３９１】
なお、復号途中結果格納用メモリ６１０には、計算部６１５の第２の演算により演算された検査行列の１（枝）に対応する復号途中結果vi'（第２の復号途中結果）が格納されるので、復号途中結果格納用メモリ６１０に格納されるデータ量、即ち、復号途中結果格納用メモリ６１０に必要とされる記憶容量は、復号途中結果の量子化ビット数と、検査行列の１の数（全枝数）との乗算値となる。
【０３９２】
復号途中結果格納用メモリ６１０は、例えば、５つの復号途中結果を同時に読み書き可能な、２つのシングルポートRAMから構成される。復号途中結果格納用メモリ６１０には、計算部６１５から５つの復号途中結果D615が供給されるとともに、制御部６１７から復号途中結果D615の読み書きを制御する制御信号D618が供給される。
【０３９３】
サイクリックシフト回路６１１には、復号途中結果格納用メモリ６１０から５つの復号途中結果D610が供給されるとともに、制御部６１７から、その復号途中結果D610に対応する検査行列の１が、検査行列において元となる単位行列などを幾つサイクリックシフトであるかの情報（Matrixデータ）を表す制御信号D619が供給される。サイクリックシフト回路６１１は、制御信号D619を元に、５つの復号結果D610を並べ替えるサイクリックシフトを行い、その結果を復号途中結果D611として、計算部６１２に供給する。
【０３９４】
計算部６１２は、５つの計算器６１２1乃至６１２5からなる。計算部６１２には、サイクリックシフト回路６１１から５つの復号途中結果D611（第２の復号途中結果）（vi'）が供給され、その５つの復号途中結果D611（第１の復号途中結果）（w）が、計算器６１２1乃至６１２5のそれぞれに供給される。また、計算部６１２には、制御部６１７から制御信号D620が供給され、その制御信号D620が、計算器６１２1乃至６１２5に供給される。なお、制御信号D620は、５つの計算器６１２1乃至６１２5に共通の信号である。
【０３９５】
計算器６１２1乃至６１２5は、それぞれ復号途中結果D611を用いて、式（９）にしたがって第１の演算を行い、復号途中結果D612(w)を求める。計算部６１２は、計算器６１２1乃至６１２5による演算の結果得られる５つの復号途中結果D612を復号途中結果格納用メモリ６１３に供給する。
【０３９６】
復号途中結果格納用メモリ６１３には、計算部６１２から、計算部６１２による第１の演算の結果である検査行列の行に対応する５つの復号途中結果D612が供給され、復号途中結果格納用メモリ６１３は、計算部６１２から供給された５つの復号途中結果D612を、第１アドレスから順に格納（記憶）する。
【０３９７】
即ち、復号途中結果格納用メモリ６１３の第１アドレスには、検査行列の行に対応する復号途中結果のうち、第１行目から第５行目の復号途中結果wが格納される。そして、同様に、第２アドレスには、第６行目から第１０行目の復号途中結果wが格納され、第３アドレスには、第１１行目から第１５行目の復号途中結果wが格納される。以後、同様に、第１６行目から第３０行目までの復号途中結果wが、５個ずつ、第４アドレスから第６アドレスまで格納され、計６０個の復号途中結果wが復号途中結果格納用メモリ６１３に格納される。従って、復号途中結果格納用メモリ６１０のワード（word）数は、図１５の検査行列Hの行数である３０を、同時に読み書きする復号途中結果の数である５で割り算した６となる。
【０３９８】
また、復号途中結果格納用メモリ６１３は、既に格納してある５つの復号途中結果D613から、計算部６１５が求めようとする復号途中結果vi'の対応する検査行列Hの列において“１”になっている復号途中結果wを５つ同時に読み出し、復号途中結果D613として、サイクリックシフト回路６１４に供給する。
【０３９９】
なお、復号途中結果格納用メモリ６１３は、例えば、5つの復号途中結果を同時に読み書き可能な、シングルポートRAMで構成される。また、復号途中結果格納用メモリ６１３には、計算部６１２の第１の演算により演算された行に対応する復号途中結果wが格納されるので、復号途中結果格納用メモリ６１３に格納されるデータ量、即ち、復号途中結果格納用メモリ６１３に必要とされる記憶容量は、復号途中結果の量子化ビット数と、検査行列Hの行数との乗算値である。
【０４００】
サイクリックシフト回路６１４には、復号途中結果格納用メモリ６１３から５つの復号途中結果D613（復号途中結果w）が供給されるとともに、制御部６１７から、その復号途中結果D613に対応する検査行列の１が検査行列において元となる単位行列などを幾つサイクリックシフトしたものであるかの情報（Matrixデータ）を表す制御信号D621が供給される。サイクリックシフト回路６１４は、制御信号D621を元に、５つの復号途中結果D613を並べ替えるサイクリックシフトを行い、その結果を復号途中結果D614として、計算部６１５に供給する。
【０４０１】
計算部６１５は、５つの計算器６１５1乃至６１５5からなる。バリアブルノード計算部６１５には、サイクリックシフト回路６１４から５つの復号途中結果D614(w)が供給されるとともに、復号途中結果格納用メモリ６１０から５つの復号途中結果D610（vi'）が供給され、その復号途中結果D614と復号途中結果D610が、計算器６１５1乃至６１５5のそれぞれに供給される。また、計算部６１５には、受信用メモリ６１７から５つの受信データD617が供給され、その受信データD617が、計算器６１５1乃至６１５5のそれぞれに供給される。さらに、計算部６１７には、制御部６１７から制御信号D622が供給され、その制御信号D622が計算器６１５1乃至６１５5に供給される。なお、制御信号D622は、５つの計算器６１７1乃至６１７5に共通の信号である。
【０４０２】
計算器６１５1乃至６１５5は、それぞれ復号途中結果D614とD611、受信データD617（LDPC符号）とを用いて、式（１）、式（１０）、式（１１）にしたがって、それぞれ第２の演算を行い、検査行列の各列の１に対応する５つの復号途中結果D615（vi'）を求める。計算部６１５は、計算器６１５1乃至６１５5の第２の演算の結果得られる５つの復号途中結果D615を、復号途中結果格納用メモリ６１０に供給する。
【０４０３】
受信用メモリ６１６は、通信路を通して受信した受信値（符号ビット）D616から計算した符号ビットの０らしさの値である受信LLR（対数尤度比）を、受信データD617として格納する。
【０４０４】
即ち、受信用メモリ６１６の第１のアドレスには、検査行列の列に対応する受信データD617のうち、検査行列の第１列目から第５列目までに対応する受信データD617が格納される。そして、第２のアドレスには、検査行列の第６列目から第１０列目までに対応する受信データD617が格納され、第３アドレスには、検査行列の第１１列目から第１６列目までに対応する受信データD617が格納される。以後、同様に、第４アドレスから第１８アドレスまでに、検査行列の第１７列目から第９０列目までに対応する受信データD617が、５つずつ格納される。
【０４０５】
そして、受信用メモリ６１６は、既に格納している受信データD617を計算部６１５による第２の演算に必要となる順番に５つずつ同時に読み出し、計算部６１５に供給する。
【０４０６】
なお、受信用メモリ６１６は、例えば、シングルポートRAMから構成される。また、受信用メモリ６１６に格納されるデータ量、即ち、受信用メモリ６１６に必要とされる記憶容量は、LDPC符号の符号長と、受信データの量子化ビット数との乗算値である。さらに、受信用メモリ６１６のワード（word）数は、LDPC符号の符号長、即ち、検査行列の列数である９０を、同時に読み出す受信データD617の数である５で割り算した値の１８である。
【０４０７】
制御部６１７は、制御信号D618を復号途中結果格納用メモリ６１０に、制御信号D619をサイクリックシフト回路６１１に供給することにより、それぞれを制御する。また、制御部６１７は、制御信号D620を計算部６１２に、制御信号D621をサイクリックシフト回路６１４に、制御信号D622を計算部６１５に供給することにより、それぞれを制御する。
【０４０８】
復号途中結果格納用メモリ６１０、サイクリックシフト回路６１１、計算部６１２、復号途中結果格納用メモリ６１３、サイクリックシフト回路６１４、計算部６１５の順で、データが一巡することで、復号装置６００は、１回の復号を行うことができる。復号装置６００では、所定の回数だけ繰り返して復号が行われた後、計算部６１５が、式（５）にしたがう演算を行い、その演算結果が最終的な復号結果として出力される。
【０４０９】
図２９は、図２６の計算部６１２の計算器６１２1の構成例を示すブロック図である。
【０４１０】
なお、図２９では、計算器６１２1について説明するが、計算器６１２2乃至計算器６１２5も同様に構成される。
【０４１１】
また、図２９では、計算器６１５による第２の演算の結果得られる各復号途中結果（vi'）が６ビットに量子化されているものとして、計算器６１２1を表している。さらに、図２９の計算器６１２1には、クロックｃｋが供給され、このクロックｃｋは、必要なブロックに供給されるようになっている。そして、各ブロックは、クロックｃｋに同期して処理を行う。
【０４１２】
図２９の計算器６１２1は、制御部６１７から供給される制御信号D620に基づいて、サイクリックシフト回路６１１から１つずつ読み込まれる復号途中結果D611（vi'）を用いて、式（９）にしたがう第１の演算を行う。
【０４１３】
即ち、計算器６１２1には、サイクリックシフト回路６１１から供給される５つの６ビットの復号途中結果D611(vi')のうちの、１つの復号途中結果D611が供給され、最上位ビットの符号ビットD631がEXOR回路６３５に供給されるとともに、その６ビットの復号途中結果D611（vi'）の下位５ビットの絶対値D632（|vi'|）が、加算器６３１に供給される。また、計算器６１２1には、制御部６１７から制御信号D620が供給され、その制御信号D620がセレクタ６３３とセレクタ６３７に供給される。
【０４１４】
加算器６３１は、絶対値D632（|vi'|）とレジスタ６３２に格納されている９ビットの値D633とを加算することにより、絶対値D632（|vi'|）を積算し、その結果得られる９ビットの積算値をレジスタ６３２に再格納する。なお、検査行列の１行に亘る全ての１に対応する復号途中結果D611から求められた絶対値D632(|vi|)が積算された場合、レジスタ６３２はリセットされる。
【０４１５】
検査行列の1行に亘る復号途中結果D611が１つずつ読み込まれ、レジスタ６３２に1行分の絶対値D632が積算された積算値が格納された場合、制御部６１７から供給される制御信号D620は、０から１に変化する。例えば、行の重み（row weight）が「９」である場合、制御信号D620は、１から８クロック目までは、「０」となり、９クロック目では「１」となる。
【０４１６】
制御信号D620が「１」の場合、セレクタ６３３は、レジスタ６３２に格納されている値、即ち、検査行列の1行に亘る全ての１に対応する復号途中結果D611（復号途中結果vi'）の絶対値D632（|vi'|）が積算された９ビットの値D633（ｉ＝１からｉ＝ｄcまでのΣ|vi'|）を選択し、値D634として、レジスタ６３４に出力して格納させる。レジスタ６３４は、格納している値D634を、９ビットの値D635として、セレクタ６３３に供給するとともに、出力する。制御信号D620が「０」の場合、セレクタ６３３は、レジスタ６３４から供給された値D635を選択し、レジスタ６３４に出力して再格納させる。即ち、検査行列の1行に亘る全ての１に対応する復号途中結果D611（復号途中結果vi'）の絶対値D632（|vi'|）が積算されるまで、レジスタ６３４は、前回積算された|vi'|を、セレクタ６３３に供給するとともに、出力する。
【０４１７】
以上の処理と並行して、EXOR回路６３５は、レジスタ６３６に格納されている１ビットの値D637と符号ビットD631との排他的論理和を演算することにより、符号ビットどうしの乗算を行い、１ビットの乗算結果D636をレジスタ６３６に再格納する。なお、検査行列の1行に亘る全ての１に対応する復号途中結果D611の符号ビットD631が乗算された場合、レジスタ６３６はリセットされる。
【０４１８】
検査行列の1行に亘る全ての１に対応する復号途中結果D611から求められた符号ビットD631が乗算された乗算結果D636（ｉ＝１からｄcまでのΠsign(vi')）がレジスタ６３６に格納された場合、制御部６１７から供給される制御信号D620は、「０」から「１」に変化する。
【０４１９】
制御信号D620が「１」の場合、セレクタ６３７は、レジスタ６３６に格納されている値、即ち、検査行列の1行に亘る全ての１に対応する復号途中結果D611の符号ビットD631が乗算された値D637（ｉ＝１からｉ＝ｄcまでのΠsign(vi')）を選択し、１ビットの値D638としてレジスタ６３８に出力して格納させる。レジスタ６３８は、格納している値D638を、１ビットの値D639としてセレクタ６３７に供給するとともに、出力する。制御信号D620が「０」の場合、セレクタ６３７は、レジスタ６３８から供給された値D639を選択し、レジスタ６３８に出力して再格納させる。即ち、検査行列の1行に亘る全ての１に対応する復号途中結果D611（復号途中結果vi'）の符号ビットD631が乗算されるまで、レジスタ６３８は、前回格納した値を、セレクタ６３７に供給するとともに、出力する。
【０４２０】
計算器６１２1では、レジスタ６３４から出力された９ビットの値D635（ｉ＝１からｉ＝ｄcまでのΣ|vi'|）を下位９ビットとするとともに、レジスタ６３８から出力された１ビットの値D639（sign（vi'））を最上位ビットとする合計１０ビットが復号途中結果D612（復号途中結果w）として出力される。
【０４２１】
以上のように、計算器６１２1では、式（９）の演算が行われ、復号途中結果wが求められる。
【０４２２】
図３０は、図２６の計算部６１５の計算器６１５1の構成例を示すブロック図である。
【０４２３】
なお、図３０では、計算器６１５1について説明するが、計算器６１５2乃至計算器６１５5も同様に構成される。
【０４２４】
また、図３０では、計算器６１２による第１の演算の結果得られる各復号途中結果（w）が符号ビットを合わせて合計１０ビットに量子化され、復号途中結果格納用メモリ６１０から供給される、前回の第２の演算の結果得られた各復号途中結果(uj)が符号ビットを合わせて６ビットに量子化されているものとして、計算器６１５1を表している。さらに、図３０の計算器６１５1には、クロックｃｋが供給され、このクロックｃｋは、必要なブロックに供給されるようになっている。そして、各ブロックは、クロックｃｋに同期して処理を行う。
【０４２５】
図３０の計算器６１５1は、制御部６１７から供給される制御信号D622に基づいて、受信用メモリ６１６から１つずつ読み込まれる受信データD617（受信値u0i）、サイクリックシフト回路６１４から１つずつ読み込まれる復号途中結果D614（w）、および復号途中結果格納用メモリ６１０から１つずつ読み込まれる前回の計算部６１５による第２の演算の結果得られた復号途中結果D610（vi'）とを用いて、式（１）、式（１０）、式（１１）にしたがう第２の演算を行う。
【０４２６】
即ち、計算器６１５1では、サイクリックシフト回路６１４から、検査行列の行に対応する１０ビットの復号途中結果D614（復号途中結果w）が１つずつ読み込まれとともに、復号途中結果格納用メモリ６１０から、前回の計算部６１５による第２の演算の結果得られた６ビットの復号途中結果D610（復号途中結果vi'）が1つずつ読み込まれ、その復号途中結果D614の最上位ビットの符号ビットD651（sign(w)）と復号途中結果D610の最上位ビットの符号ビットD653（sign（uj））が、EXOR回路６５３に供給されるとともに、その復号途中結果D614の下位９ビットの絶対値D652（|w|））と復号途中結果D610の下位９ビットの符号ビットD653（|vi'|）が、減算器６５１に供給される。また、計算器６１５1では、受信用メモリ６１６から６ビットの受信データD617が１つずつ読み込まれ、加算器６５８に供給される。さらに、計算器６１５1には、制御部６１７から制御信号D622が供給され、その制御信号D622は、セレクタ６５６に供給される。
【０４２７】
減算器６５１は、絶対値D652から絶対値D654を減算し、その５ビットの減算値D655をLUT６５２に供給する。LUT６５２は、その減算値D655に対して、φ-1の演算を行った５ビットの演算結果D656（φ-1（|w|−｜vi'｜））を出力する。
【０４２８】
一方、EXOR回路６５３は、符号ビットD651（sign（w））と符号ビットD653（sign（vi'））との排他的論理和を演算することにより、符号ビットD651と符号ビットD653を乗算し、１ビットの乗結果を乗算値D657として出力する。そして、LUT６５２から供給される５ビットの演算結果D656を下位５ビット（φ-1（|w|−｜vi'｜））とするとともに、EXOR回路６５３から供給される１ビットの値D657（sign（w）×sign（vi'））を最上位ビットとした６ビットの値D658が、加算器６５４に供給されるとともに、FIFOメモリ６５９に供給される。
【０４２９】
以上のように、式（１０）にしたがう演算が行われ、その演算の結果である６ビットの値D658（uj）が、加算器６５４に供給されるとともに、FIFOメモリ６５９に供給される。
【０４３０】
加算器６５４は、６ビットの値D658（uj）とレジスタ６５５に格納されている９ビットの値D659とを加算することにより、値D658を積算し、その結果得られる９ビットの積算値を、レジスタ６５５に再格納する。なお、検査行列の１列に亘る全ての１に対応する値D658が積算された場合、レジスタ６５５はリセットされる。
【０４３１】
検査行列の１列に亘る値D658が１つずつ読み込まれ、レジスタ６５５に１列分の値D658が積算された値が格納された場合、制御部６１７から供給される制御信号D622は、「０」から「１」に変化する。例えば、列の重みが「５」である場合、制御信号D622は、１から４クロック目までは「０」となり、５クロック目では「１」となる。
【０４３２】
制御信号D622が「１」の場合、セレクタ６５６は、レジスタ６５５に格納されている値、即ち、検査行列の１列に亘る１に対応する値D658（uj）が積算された９ビットの値D659（ｊ＝１からｄVまでのΣuj）を選択し、レジスタ６５７に出力して格納させる。レジスタ６５７は、格納している値D659を、９ビットの値D660として、セレクタ４７１と加算器６５８に供給する。制御信号D622が「０」の場合、セレクタ６５６は、レジスタ６５７から供給された値D660を選択し、レジスタ６５７に出力し再格納させる。即ち、検査行列の１列に亘る１に対応する値D658（uj）が積算されるまで、レジスタ６５７は、前回積算された値を、セレクタ６５６と加算器６５８に供給する。
【０４３３】
加算器６５８は、９ビットの値D660と、受信用メモリ６１６から供給された６ビットの受信データD617とを加算して、その結果得られる９ビットの値D661を供給する。
【０４３４】
計算器６１５では、最後の演算を行う場合、加算器６５８が、９ビットの値D661を最終的な復号結果として出力する。即ち、計算部６１５は、式（５）にしたがって演算を行う。
【０４３５】
一方、FIFOメモリ６５９は、レジスタ６６５から新たな値D660（ｊ＝１からｊ＝ｄvまでのΣuj）が出力されるまでの間、６ビットの値D658(uj)を遅延し、６ビットの値D662として減算器６６０に供給する。減算器６６０は、９ビットの値D660から６ビットの値D662を減算し、その減算値D663を出力する。即ち、減算器６６０は、検査行列の１列に亘る１に対応する値D658の積算値から、求めたい枝に対応する値、即ち検査行列の所定の１に対応する値D658（uj）を減算して、その減算値（ｉ＝１からｉ＝ｄv−１までのΣuj）を６ビットの減算値D663として出力する。
【０４３６】
以上のように、式（１）にしたがう演算が行われ、その演算の結果である６ビットの減算値D663（vi）が出力される。そして、減算器６６０から出力された６ビットの減算値D663の下位５ビットの絶対値（|vi|）が、LUT６６１に供給されるとともに、最上位ビットの符号ビット（sign（vi））が値D665として出力される。
【０４３７】
LUT６６１は、絶対値（|vi|）に対して、φの演算を行った５ビットの演算結果D666（φ（｜vi｜））を出力する。そして、LUT６６１から出力された５ビットの演算結果D666（φ（｜vi｜））を下位５ビットとするとともに、値D665（sign（vi））を最上位ビットとした合計６ビットを、復号途中結果（vi'）として復号途中結果格納用メモリ６１０に供給する。
【０４３８】
以上のように、計算器６１５1では、式（１）、式（１０）、式（１１）の演算が行われ、復号途中結果vi'が求められる。
【０４３９】
なお、図１５の検査行列の列の重みの最大は５であるため、即ち、計算器６１５1に供給される復号途中結果D614（w）と復号途中結果D610（vi'）の最大数は５であるため、計算器６１５1は、５個の復号途中結果D614と復号途中結果D610から求められる５個の演算結果D658（uj）を遅延させるFIFOメモリ６５９を有している。列の重みが５未満の行のメッセージを計算するときには、FIFOメモリ６５９における遅延量が、その列の重みの値に減らされる。
【０４４０】
図３１は、図２６の復号途中結果格納用メモリ６１０の構成例を示すブロック図である。
【０４４１】
復号途中結果格納用メモリ６１０は、スイッチ７０１と７０４、および２つのシングルポートRAMである復号途中結果格納用RAM７０２と７０３から構成される。
【０４４２】
この復号途中結果格納用メモリ６１０の各部について詳細に説明する前に、まず、復号途中結果格納用RAM７０２と７０３へのデータの格納方法について説明する。
【０４４３】
復号途中結果格納用RAM７０２と７０３は、計算部６１２による第１の演算の結果得られ、スイッチ７０１を介して供給された復号途中結果D615を格納する。
【０４４４】
具体的には、復号途中結果格納用RAM７０２の第１アドレスから第５アドレスには、図１５の検査行列Hの第１列目から第５列目までの１に対応する復号途中結果D615(D701)が、各行ともに横方向（列方向）に詰めた形に（０を無視した形で）格納される。
【０４４５】
即ち、第ｊ行第ｉ列を、(j,ｉ)と表すこととすると、復号途中結果格納用RAM７０２の第１アドレスには、図１５の検査行列の(1,1)から(5,5)の５×５の単位行列の１に対応するデータが、第２アドレスには、図１５の検査行列の(6,1)から(10,5)の和行列（５×５の単位行列を右に１つだけサイクリックシフトした第１のシフト行列と、右に２つだけサイクリックシフトした第２のシフト行列との和である和行列）を構成する第１のシフト行列の１の位置に対応するデータが格納される。また、第３アドレスには、検査行列の(6,1)から(10,5)の和行列を構成する第２のシフト行列の１の位置に対応するデータが格納される。以下、第４アドレスおよび第５アドレスについても、図１５の検査行列に対応づけて、データが格納される。
【０４４６】
復号途中格納用RAM７０２の第６アドレスから第１０アドレスには、図１５の検査行列の第１１列目から第１５列目までの１に対応するデータが格納される。即ち、第６アドレスには、検査行列の(11,11)から(15,15)の和行列（５×５の単位行列と、５×５の単位行列を右に３つだけサイクリックシフトした第１のシフト行列との和である和行列）を構成する第１のシフト行列の１の位置に対応するデータが格納され、第７アドレスには、検査行列の(11,11)から(15,15)の和行列を構成する単位行列の１に対応するデータが格納される。以下、第８アドレスから第１０アドレスについても、検査行列に対応づけてデータが格納される。
【０４４７】
同様に、復号途中格納用RAM７０２の第１０アドレスから第２８アドレスには、図１５の検査行列に対応づけて、第２１列目から第２５列目まで、第３１列目から第３５列目まで、第４１列目から第４５列目まで、第５１列目から第５５列目まで、第６１列目から第６５列目まで、第７１列目から第７５列目まで、第８１列目から第８５列目までの１に対応するデータが格納される。即ち、復号途中結果格納用RAM７０２のワード数は、２８である。
【０４４８】
復号途中結果格納用RAM７０３の第１アドレスから第５アドレスには、図１５の検査行列Hの第６列目から第１０列目までの１に対応する復号途中結果D615(D702)が、各行ともに横方向（列方向）に詰めた形に（０を無視した形で）格納される。
【０４４９】
即ち、復号途中結果格納用RAM７０３の第１アドレスには、検査行列の構成行列である(6,1)から(10,5)の和行列（５×５の単位行列を右に１つだけサイクリックシフトした第１のシフト行列と、右に２つだけサイクリックシフトした第２のシフト行列の和である和行列）を構成する第１のシフト行列の１に対応するデータが、第２アドレスには、検査行列の構成行列である(6,1)から(10,5)の和行列を構成する第２のシフト行列の１に対応するデータが格納される。以下、第３アドレスから第５アドレスも同様に検査行列の構成行列と対応づけてデータが格納される。
【０４５０】
同様に、復号途中格納用RAM７０３の第６アドレスから第２６アドレスには、図１５の検査行列の第１６列目から第２０列目まで、第２６列目から第３０列目まで、第３６列目から第４０列目まで、第４６列目から第５０列目まで、第５６列目から第６０列目まで、第６６列目から第７０列目まで、第７６列目から第８０列目まで、第８６列目から第９０列目までの１に対応するデータが、図１５の検査行列に対応づけて格納される。即ち、復号途中結果格納用RAM７０３のワード数は、２６である。
【０４５１】
上述したように、復号途中結果格納用RAM７０２のワード(word)数は、２８であり、復号途中結果格納用RAM７０３のワード数は、２６である。
【０４５２】
図３２は、復号途中結果格納用メモリ６１０の復号途中結果格納用RAM７０２と復号途中結果格納用RAM７０３の読み出しと書き込みの動作を説明するタイミングチャートである。
【０４５３】
なお、図３２において、横軸は、時間（ｔ）を表している。
【０４５４】
復号途中結果格納用メモリ６１０では、計算部６１２による第１の演算が行われる場合、制御部６１７から供給される制御信号D7202に基づいて、復号途中結果格納用RAM７０２から既に格納されている第２の演算の結果得られる復号途中結果D703を読み出すか、あるいは制御部６１７から供給される制御信号D7203に基づいて、復号途中結果格納用RAM７０３から、既に格納されている第２の演算の結果得られる復号途中結果D704を読み出し、その読み出した復号途中結果をスイッチ７０４を介して、サイクリックシフト回路６１４に供給する。
【０４５５】
復号途中結果格納用メモリ６１０には、計算部６１５により第２の演算が行われる場合、計算部６１５から第２の演算の結果得られる復号途中結果D615（vi'）が供給され、その復号途中結果D615が復号途中結果格納用RAM７０２または復号途中結果格納用RAM７０３のうちの一方の所定のアドレスに書き込まれると同時に、他方から、前回の計算部６１５による第２の演算の結果得られた復号途中結果D610（vi'）が読み出され、サイクリックシフト回路６１４を介して、計算部６１５に出力される。
【０４５６】
スイッチ７０１には、計算部６１５から５つの復号途中結果D615が供給されるとともに、その復号途中結果D615を書き込むメモリとして、復号途中結果格納用RAM７０２または復号途中結果格納用RAM７０３の一方の選択を表す制御信号D7201が供給される。スイッチ７０１は、制御信号D7201に基づいて、復号途中結果格納用RAM７０２または復号途中結果格納用RAM７０３の一方を選択し、その選択した一方に、５つの復号途中結果D612を供給する。
【０４５７】
復号途中結果格納用RAM７０２には、スイッチ７０１から５つの復号途中結果D612が、復号途中結果D701として供給されるとともに、制御部６１７からアドレスを表す制御信号D7022が供給される。復号途中結果格納用RAM７０２は、制御信号D7202が表すアドレスに既に格納されている前回の計算部６１５による第２の演算の結果得られた５つの復号途中結果D701を読み出し、復号途中結果D703としてスイッチ７０４に供給する。また、復号途中結果格納用RAM７０２は、制御信号D7202が表すアドレスに、スイッチ７０１から供給された５つの復号途中結果D702を格納する(書き込む)。
【０４５８】
復号途中結果格納用RAM７０３には、スイッチ７０１から５つの復号途中結果D615が、復号途中結果D702として供給されるとともに、制御部６１７からアドレスを表す制御信号D7203が供給される。復号途中結果格納用RAM７０３は、制御信号D7203が表すアドレスに既に格納されている前回の計算部６１５による第２の演算の結果得られた５つの復号途中結果D702を読み出し、復号途中結果D704としてスイッチ７０４に供給する。また、復号途中結果格納用RAM７０２は、制御信号D7203が表すアドレスに、スイッチ７０１から供給された５つの復号途中結果D702を格納する(書き込む)。
【０４５９】
スイッチ７０４には、復号途中結果格納用RAM７０２から復号途中結果D703が供給されるか、あるいは復号途中結果格納用RAM７０３から復号途中結果D704が供給される。また、制御部６１７から、復号途中結果格納用RAM７０２または復号途中結果格納用RAM７０３の一方の選択を表す制御信号D7204が供給される。スイッチ７０４は、制御信号D7204に基づいて、復号途中結果格納用RAM７０２または復号途中結果格納用RAM７０３の一方を選択し、その選択した一方から供給された５つの復号途中結果を、５つの復号途中結果D610として計算部６１５に供給する。
【０４６０】
復号途中結果格納用メモリ６１０では、計算部６１５により第２の演算が行われる場合、復号途中結果格納用RAM７０２が、制御信号D7202に基づいて、既に格納している、前回の計算部６１５の第２の演算の結果得られた復号途中結果D701のうち、同一アドレスに格納している検査行列の第１列目から第５列目までの１に対応する復号途中結果D701を、５つ単位で、５回読み出し、スイッチ７０４を介して、計算部６１５に供給する。即ち、図１５の検査行列Hの列重みは、５であるため、検査行列Hの各列の１に対応する復号途中結果は５つあり、復号途中結果格納用RAM７０２は、第１行列目から第５列目までの１に対応する復号途中結果D701を、５つ単位で５回読み出す。
【０４６１】
次に、復号途中結果格納用RAM７０３は、制御信号D7203に基づいて、既に格納している、前回の計算部６１５による第２の演算の結果得られた復号途中結果D702のうち、同一アドレスに格納している検査行列の第６列目から第１０列目までの１に対応する５つの復号途中結果D702を、５回続けて読み出し、スイッチ７０４とサイクリックシフト回路６１４を介して、計算部６１５に供給する。それと同時に、復号途中結果格納用RAM７０２には、計算部６１５により、いま行われている第２の演算の結果得られる検査行列の第１列目から第５列目までの１に対応する５つの復号途中結果D615がスイッチ７０１を介して、復号途中結果D701として供給され、復号途中結果格納用RAM７０２は、その復号途中結果D701を、制御信号D7202に基づいて、既に読み出された復号途中結果D703が格納されていたアドレスに５回続けて格納する。
【０４６２】
その後、復号途中結果格納用RAM７０２は、制御信号D7202に基づいて、既に格納している、前回の計算部６１５による第２の演算の結果得られた復号途中結果D701のうち、同一アドレスに格納している検査行列の第１１列目から第１５列目までの１に対応する復号途中結果D701を、５つ単位で５回続けて読み出し、スイッチ７０４を介して、計算部６１５に供給する。それと同時に、復号途中結果格納用RAM７０３には、計算部６１５により、いま行われている第２の演算の結果得られる検査行列の第６列目から第１０列目までの１に対応する５つの復号途中結果D612がスイッチ７０１を介して、復号途中結果D702として供給され、復号途中結果格納用RAM７０３は、その復号途中結果D702を、制御信号D7203に基づいて、既に読み出された復号途中結果D704が格納されていたアドレスに５回続けて格納する。
【０４６３】
以後、同様に、計算部６１５による第２の演算の結果得られる検査行列の全ての１に対応する復号途中結果が、復号途中結果格納用RAM７０２または復号途中結果格納用RAM７０３に格納されるまで、復号途中結果格納用RAM７０２と復号途中結果格納用RAM７０３は、５回ずつの読み出しまたは書き込みを交互に行う。
【０４６４】
図３３は、図２６の復号装置６００の復号処理を説明するフローチャートである。この処理は、例えば、受信用メモリ６１６に復号すべき受信データが格納されたとき、開始される。
【０４６５】
ステップＳ７０において、サイクリックシフト回路６１４は、復号途中結果格納用メモリ６１３から供給された後述するステップＳ７６で格納された５つの復号途中結果D613を、並べ替えてサイクリックシフトを行い、計算部６１５に供給する。
【０４６６】
具体的には、サイクリックシフト回路６１４には、復号途中結果格納用メモリ６１３から５つの復号途中結果D613が供給されるとともに、制御部６１７から、その復号途中結果D613に対応する検査行列の１が検査行列において元となる単位行列などを幾つサイクリックシフトしたものであるかの情報（Matrixデータ）を表す制御信号D621が供給される。サイクリックシフト回路６１４は、制御信号D621を元に、５つの復号途中結果D613をサイクリックシフトし（並べ替え）、その結果を復号途中結果D614として、計算部６１５に供給する。
【０４６７】
なお、受信用メモリ６１６から供給された受信データD617に対して、まだ第１の演算が行われておらず、復号途中結果格納用メモリ６１３に復号途中結果D612が格納されていない場合、計算部６１５は、初期値に設定する。
【０４６８】
ステップＳ７１において、計算部６１５は、第２の演算を行い、その演算の結果である復号途中結果D615を復号途中結果格納用メモリ６１０に供給する。
【０４６９】
具体的には、計算部６１５には、ステップＳ７０でサイクリックシフト回路６１４から５つの復号途中結果D614が供給されるとともに、直前の後述するステップＳ７２で復号途中結果格納用メモリ６１０から復号途中結果D610が供給される。また、受信データ用メモリ６１６から５つの受信データD617が供給され、５つの復号途中結果D615とD610、受信データD617が、計算部６１５の計算器６１５1乃至６１５5のそれぞれに１つずつ供給される。さらに、計算部６１５には、制御部６１７から制御信号D622が供給され、その制御信号D622が計算器６１５1乃至６１５5に供給される。
【０４７０】
計算器６１５1乃至６１５5は、復号途中結果D614とD610と、受信データD617とを用いて、制御信号D622に基づいて、式（１）、式（１０）、式（１１）にしたがって、それぞれ演算を行い、その演算の結果得られる検査行列の各列の１に対応する復号途中結果D615(vi')を復号途中結果格納用メモリ６１０に供給する。
【０４７１】
ステップＳ７１の処理後は、ステップＳ７２に進み、復号途中結果格納用メモリ６１０は、ステップＳ７１で計算部６１５から供給された復号途中結果D615を、同一アドレスに格納するとともに、既に格納している復号途中結果D615（D610）を読み出して、サイクリックシフト回路６１１と計算部６１５に供給する。
【０４７２】
ステップＳ７２の処理後は、ステップＳ７３に進み、制御部６１７は、計算部６１５により、検査行列の各列の１に対応する全ての復号途中結果D615が演算されたかどうかを判定し、全ての復号途中結果D615が演算されていないと判定した場合、ステップＳ７０に戻り、上述した処理を繰り返す。
【０４７３】
一方、ステップＳ７３において、制御部６１７は、計算部６１５により、全ての復号途中結果D615が演算されたと判定した場合、ステップＳ７４に進み、サイクリックシフト回路６１１は、復号途中結果格納用メモリ６１０から供給される復号途中結果D610(vi')をサイクリックシフトする。
【０４７４】
具体的には、サイクリックシフト回路６１１には、復号途中結果格納用メモリ６１０から５つの復号途中結果D610が供給されるとともに、制御部６１７から、その復号途中結果D610に対応する検査行列の１が検査行列において元となる単位行列などを幾つサイクリックシフトしたものであるかの情報（Matrixデータ）を表す制御信号D619が供給される。サイクリックシフト回路６１１は、制御信号D619を元に、５つの復号途中結果D610をサイクリックシフトし（並べ替え）、その結果を復号途中結果D611として、計算部６１２に供給する。
【０４７５】
ステップＳ７４の処理後は、ステップＳ７５に進み、計算部６１２は、第１の演算を行い、その演算結果である復号途中結果D612をサイクリックシフト回路６１４に供給する。
【０４７６】
具体的には、計算部６１２には、ステップＳ７４でサイクリックシフト回路６１１から５つの復号途中結果D611(vi')が供給され、その復号途中結果D611が、計算部６１２の計算器６１２1乃至６１２5のそれぞれに１つずつ供給される。さらに、計算部６１２には、制御部６１７から制御信号D621が供給され、その制御信号D621が計算器６１２1乃至６１２5に供給される。
【０４７７】
計算器６１２1乃至６１２5は、それぞれ復号途中結果D611を用いて、制御信号D619に基づいて、式（９）にしたがって、それぞれ演算を行い、その演算の結果得られる検査行列の行に対応する復号途中結果D612（w）を復号途中結果格納用メモリ６１３に供給する。
【０４７８】
ステップＳ７５の処理後は、ステップＳ７６に進み、復号途中結果格納用メモリ６１３は、ステップＳ７５で計算部６１２から供給された復号途中結果D612を、同一アドレスに格納し、ステップＳ７７に進む。
【０４７９】
ステップＳ７７において、制御部６１７は、計算部６１２により、検査行列の全ての行に対応する復号途中結果D612が演算されたかどうかを判定し、全ての復号途中結果が演算されていないと判定した場合、ステップＳ７４に戻り、上述した処理を繰り返す。
【０４８０】
一方、ステップＳ７７において、制御部６１７は、計算部６１２により、全ての行に対応する復号途中結果D612が演算されたと判定した場合、処理を終了する。
【０４８１】
なお、復号装置６００は、復号回数だけ図３３の復号処理を繰り返し行ない、計算部６２１により上述した式（５）にしたが演算の結果得られる値D661が、最終的な復号結果として出力される。
【０４８２】
上述した説明では、復号途中結果格納用メモリ６１０は、２つのシングルポートRAMから構成したが、１つのRAMに対して読み出しと書き込みが同時に起こらないようにすれば、３つ以上のRAMから構成してもよい。例えば、RAMの物理的なビットが足りない場合には、複数のRAMを用いて同じ制御信号を与えることで、論理的に１つのRAMとみなすことができる。
【０４８３】
また、枝データ（枝に対応するメッセージ）が欠けている箇所に関しては、メモリ格納時（復号途中結果格納用メモリ６１０と６１３へのデータ格納時）には、何のメッセージも格納せず、また、演算時（計算部６１２での第１の演算時と計算部６１５での第２の演算時）にも何の演算も行わない。
【０４８４】
また、図１６のサイクリックシフト回路３１４および３２０、図１８のサイクリックシフト回路４１１および４１４、図２６のサイクリックシフト回路６１１および６１４には、バレルシフタを用いると回路規模を小さくしながら所望の操作を実現できる。
【０４８５】
上述の場合には、説明を簡単にするために、Pが５の場合、即ち、検査行列を構成する構成行列の行数および列数が５の場合を例に挙げたが、構成行列の行数および列数Pは必ずしも５である必要はなく、検査行列によって異なる値を取ることもあり得る。例えば、Pは３６０や３９２であってもよい。
【０４８６】
また、本実施の形態では、符号長90、符号化率2/3のLDPC符号を用いたが、LDPC符号の符号長や符号化率は、幾つであっても構わない。例えば、構成行列の行数および列数Pが5の場合、枝総数が５以下であれば、どんな符号長、符号化率のLDPC符号でも、制御信号を代えるだけで、図１６の復号装置３００、図１８の復号装置４００、図２６の復号装置６００を用いて復号可能である。
【０４８７】
さらに、構成行列の行数および列数Pが所定の値で、枝の総数がある値以下、という条件を満たすあるLDPC符号の復号装置は、その条件を満たす、任意の符号長で、任意の符号化率のLDPC符号を復号することができる。
【０４８８】
検査行列が、構成行列の行数および列数Pの倍数でない場合は、検査行列の端数の外側にすべて０(all 0)の成分を付けてPの倍数とみなして適用できることがある。
【０４８９】
次に、上述した一連の処理は、ハードウェアにより行うこともできるし、ソフトウェアにより行うこともできる。一連の処理をソフトウェアによって行う場合には、そのソフトウェアを構成するプログラムが、汎用のコンピュータ等にインストールされる。
【０４９０】
そこで、図３４は、上述した一連の処理を実行するプログラムがインストールされるコンピュータの一実施の形態の構成例を示している。
【０４９１】
プログラムは、コンピュータに内蔵されている記録媒体としてのハードディスク９０５やＲＯＭ９０３に予め記録しておくことができる。
【０４９２】
あるいはまた、プログラムは、フレキシブルディスク、CD-ROM(Compact Disc Read Only Memory)，MO(Magneto Optical)ディスク，DVD(Digital Versatile Disc)、磁気ディスク、半導体メモリなどのリムーバブル記録媒体９１１に、一時的あるいは永続的に格納（記録）しておくことができる。このようなリムーバブル記録媒体９１１は、いわゆるパッケージソフトウエアとして提供することができる。
【０４９３】
なお、プログラムは、上述したようなリムーバブル記録媒体９１１からコンピュータにインストールする他、ダウンロードサイトから、ディジタル衛星放送用の人工衛星を介して、コンピュータに無線で転送したり、LAN(Local Area Network)、インターネットといったネットワークを介して、コンピュータに有線で転送し、コンピュータでは、そのようにして転送されてくるプログラムを、通信部９０８で受信し、内蔵するハードディスク９０５にインストールすることができる。
【０４９４】
コンピュータは、CPU(Central Processing Unit)９０２を内蔵している。CPU９０２には、バス９０１を介して、入出力インタフェース９１０が接続されており、CPU９０２は、入出力インタフェース９１０を介して、ユーザによって、キーボードや、マウス、マイク等で構成される入力部９０７が操作等されることにより指令が入力されると、それにしたがって、ROM(Read Only Memory)９０３に格納されているプログラムを実行する。あるいは、また、CPU９０２は、ハードディスク９０５に格納されているプログラム、衛星若しくはネットワークから転送され、通信部９０８で受信されてハードディスク９０５にインストールされたプログラム、またはドライブ９０９に装着されたリムーバブル記録媒体９１１から読み出されてハードディスク９０５にインストールされたプログラムを、RAM(Random Access Memory)９０４にロードして実行する。これにより、CPU９０２は、上述したフローチャートにしたがった処理、あるいは上述したブロック図の構成により行われる処理を行う。そして、CPU９０２は、その処理結果を、必要に応じて、例えば、入出力インタフェース９１０を介して、LCD(Liquid Crystal Display)やスピーカ等で構成される出力部９０６から出力、あるいは、通信部９０８から送信、さらには、ハードディスク９０５に記録等させる。
【０４９５】
ここで、本明細書において、コンピュータに各種の処理を行わせるためのプログラムを記述する処理ステップは、必ずしもフローチャートとして記載された順序に沿って時系列に処理する必要はなく、並列的あるいは個別に実行される処理（例えば、並列処理あるいはオブジェクトによる処理）も含むものである。
【０４９６】
また、プログラムは、１のコンピュータにより処理されるものであっても良いし、複数のコンピュータによって分散処理されるものであっても良い。さらに、プログラムは、遠方のコンピュータに転送されて実行されるものであっても良い。
【０４９７】
以上のように、P×Pの単位行列、そのコンポーネントの１のうち１個以上が０になった準単位行列、単位行列もしくは準単位行列をサイクリックシフトしたシフト行列、単位行列、準単位行列、もしくはシフト行列の複数の和である和行列、P×Pの０行列の組合せで表わすことができる検査行列を持つLDPC符号の復号を、チェックノードとバリアブルノードの演算をP個同時に行うアーキテクチャ(architecture)を採用することにより、ノード演算を、P個同時に行うことで動作周波数を実現可能な範囲に抑えることができ、多数の繰り返し復号を行うことを可能にしつつ、メモリ（FIFOやRAM）への書き込みと読み出し時に、異なるアドレスへの同時アクセスが起きることを防止することができる。
【０４９８】
さらに、図１６の復号装置３００を繰り返し用いて、図１５の検査行列で表わされるLDPC符号を復号する場合には、２６９個の枝をチェックノード、バリアブルノード毎に５個ずつ演算することが可能であることから、１回の復号に、269/5×2≒１０８クロック動作すればよいことになる。５０回の復号には、９０個の符号情報を受信する間に、108×50=5400クロック動作すればよいことになり、受信周波数の約６０倍の動作周波数でよいことになる。従って、図１６の復号装置３００によれば、各ノード演算を一つずつ行う図９の復号装置に比べて、1/5の動作周波数で済むことになる。また、回路規模の面から見ても、メモリの大きさは同じであるため、論理回路が多少大きくなっても全体への影響は小さいと言える。
【０４９９】
さらに、図１８の復号装置４００と図２６の復号装置６００は、図１６の復号装置３００に比べて、メモリの容量が小さくなっている。
【０５００】
例えば、LDPC符号の検査行列が図１５の検査行列であり、LDPC符号の量子化ビット数が６ビットである場合、図１６の復号装置３００では、枝データ格納メモリに、全枝数の２６９×６＝１６１４ビットの容量を有するRAM２つ、即ち、２つのRAMで１６１４×２＝３２２８ビットの容量が必要であった。これに対して、例えば、復号途中結果vの量子化ビット数が９ビットである場合、図１８の復号装置４００では、復号途中結果格納用メモリ４１３に、全枝数の１６１４ビットの容量を有するRAMと、復号途中結果格納用メモリ４１０に、LDPC符号の符号長（検査行列の列数）と復号途中結果vの量子化ビット数との乗算値、即ち９０×９＝８１０ビットの容量を有するRAMを備えればよく、復号装置の回路規模を小さくすることができる。さらに、図１８の復号装置４００では、第２の演算を行う計算部４１５において、FIFOメモリを有する必要がないので、ロジックの回路規模を小さくすることができる。
【０５０１】
また、例えば、LDPC符号の検査行列が図１５の検査行列で、復号途中結果vの量子化ビット数が１０ビットである場合、図２６の復号装置６００では、復号途中結果格納用メモリ６１０に、全枝数の１６１４ビットの容量を有するRAMと、復号途中結果格納用メモリ６１３に、検査行列の行数と復号途中結果vとの乗算値、即ち３０×１０＝３００ビットの容量を有するRAMを備えればよく、復号装置の回路規模を小さくすることができる。さらに、図２６の復号装置６００では、第１の演算を行う計算部６１２において、FIFOメモリを有する必要がないので、ロジックの回路規模を小さくすることができる。
【０５０２】
一般的に、LDPC符号は符号長が数千から数万と大きいため、Pの値も数百の大きさを持つものが使われる。その場合には、更に本発明に係る復号装置を用いる効果は大きくなる。
【０５０３】
また、本発明に係る復号装置は、サムプロダクトアルゴリズムを忠実に実装するものであるため、メッセージの量子化以外の復号損失が起きることはない。
【０５０４】
以上の観点から、本発明に係る復号装置を用いることで、高性能な復号が可能になる。
【図面の簡単な説明】
【０５０５】
【図１】LDPC符号の検査行列Hを説明する図である。
【図２】LDPC符号の復号手順を説明するフローチャートである。
【図３】メッセージの流れを説明する図である。
【図４】LDPC符号の検査行列の例を示す図である。
【図５】検査行列のタナーグラフを示す図である。
【図６】バリアブルノードを示す図である。
【図７】チェックノードを示す図である。
【図８】LDPC符号の検査行列の例を示す図である。
【図９】ノード演算を一つずつ行うLDPC符号の復号装置の構成例を示すブロック図である。
【図１０】メッセージを一つずつ計算するチェックノード計算器の構成例を示すブロック図である。
【図１１】メッセージを一つずつ計算するバリアブルノード計算器の構成例を示すブロック図である。
【図１２】ノード演算を全て同時に行うLDPC符号の復号装置の構成例を示すブロック図である。
【図１３】メッセージを同時に計算するチェックノード計算器の構成例を示すブロック図である。
【図１４】メッセージを同時に計算するバリアブルノード計算器の構成例を示すブロック図である。
【図１５】５×５単位に分割した検査行列を示す図である。
【図１６】本発明を適用した復号装置の一実施の形態の構成例を示すブロック図である。
【図１７】図１６の復号装置の復号処理を説明するフローチャートである。
【図１８】本発明を適用した復号装置の一実施の形態の構成例を示すブロック図である。
【図１９】チェックノード計算器の構成例を示すブロック図である。
【図２０】バリアブルノード計算器の構成例を示すブロック図である。
【図２１】図１８の計算器の構成例を示すブロック図である。
【図２２】図１８の計算器の構成例を示すブロック図である。
【図２３】図１８の復号途中結果格納用メモリの構成例を示すブロック図である。
【図２４】図１８の復号途中結果格納用RAMの動作を説明するタイミングチャートである。
【図２５】図１８の復号装置の復号処理を説明するフローチャートである。
【図２６】本発明を適用した復号装置の一実施の形態の構成例を示すブロック図である。
【図２７】チェックノード計算器の構成例を示すブロック図である。
【図２８】バリアブルノード計算器の構成例を示すブロック図である。
【図２９】図２６の計算器の構成例を示すブロック図である。
【図３０】図２６の計算器の構成例を示すブロック図である。
【図３１】図２６の復号途中結果格納用メモリの構成例を示すブロック図である。
【図３２】図３１の復号途中結果格納用RAMの動作を説明するタイミングチャートである。
【図３３】図２６の復号装置の復号処理を説明するフローチャートである。
【図３４】本発明を適用したコンピュータの一実施の形態の構成例を示すブロック図である。
【符号の説明】
【０５０６】
３００  スイッチ，３１１  枝データ格納用メモリ，  ３１２  セレクタ，  ３１３  チェックノード計算部，  ３１４  サイクリックシフト回路，  ３１５  スイッチ，  ３１６  枝データ格納用メモリ，  ３１７  セレクタ，  ３１８  受信データ用メモリ，  ３１９  バリアブルノード計算部，  ３２０  サイクリックシフト回路，  ９０１  バス，  ９０２  CPU，  ９０３  ROM，  ９０４  RAM，  ９０５  ハードディスク，  ９０６  出力部，  ９０７  入力部，  ９０８  通信部，  ９０９  ドライブ，  ９１０  入出力インタフェース，  ９１１  リムーバブル記録媒体
【図１】
2004364233.tif 000014
【図２】
2004364233.tif 000015
【図３】
2004364233.tif 000016
【図４】
2004364233.tif 000017
【図５】
2004364233.tif 000018
【図６】
2004364233.tif 000019
【図７】
2004364233.tif 000020
【図８】
2004364233.tif 000021
【図９】
2004364233.tif 000022
【図１０】
2004364233.tif 000023
【図１１】
2004364233.tif 000024
【図１２】
2004364233.tif 000025
【図１３】
2004364233.tif 000026
【図１４】
2004364233.tif 000027
【図１５】
2004364233.tif 000028
【図１６】
2004364233.tif 000029
【図１７】
2004364233.tif 000030
【図１８】
2004364233.tif 000031
【図１９】
2004364233.tif 000032
【図２０】
2004364233.tif 000033
【図２１】
2004364233.tif 000034
【図２２】
2004364233.tif 000035
【図２３】
2004364233.tif 000036
【図２４】
2004364233.tif 000037
【図２５】
2004364233.tif 000038
【図２６】
2004364233.tif 000039
【図２７】
2004364233.tif 000040
【図２８】
2004364233.tif 000041
【図２９】
2004364233.tif 000042
【図３０】
2004364233.tif 000043
【図３１】
2004364233.tif 000044
【図３２】
2004364233.tif 000045
【図３３】
2004364233.tif 000046
【図３４】
2004364233.tif 000047