(57)【要約】【課題】  複数のフレームのLDPC符号を同時に復号する。【解決手段】  制御部４０１は、奇数フレームと偶数フレームを交互に選択し、その選択したフレームのLDPC符号をバリアブルノード計算器３０３に供給するよう制御する制御信号D410をセレクタ４０４に供給する。セレクタ４０４は、制御信号D410に基づいて、奇数フレームまたは偶数フレームのLDPC符号をバリアブルノード計算器３０３に供給する。バリアブルノード計算器３０３は、制御部４０１により選択されたフレームのLDPC符号の復号のためのバリアブルノードの演算を行う。また、チェックノード計算器３０１は、制御部４０１により選択されていないフレームのLDPC符号の復号のためのチェックノードの演算を行う。本発明は、LDPC符号を復号する復号装置に適用することができる。【選択図】図１５
2005064735.tif 000002
【特許請求の範囲】
【請求項１】
LDPC(Low Density Parity Check)符号をフレーム単位で復号する復号装置であって、
前記LDPC符号の第１のフレームと第２のフレームを交互に選択する選択手段と、
前記第１のフレームと前記第２のフレームのうちの、前記選択手段により選択されていないフレームの前記LDPC符号の復号のためのチェックノードの演算を行うチェックノード計算手段と、
前記第１のフレームと前記第２のフレームのうちの、前記選択手段により選択されたフレームの前記LDPC符号の復号のためのバリアブルノードの演算を行うバリアブルノード計算手段と
を備えることを特徴とする復号装置。
【請求項２】
請求項１に記載の復号装置であって、
前記第１のフレームと前記第２のフレームの前記LDPC符号を記憶するフレーム記憶手段と、
前記フレーム記億手段に記憶された前記第１のフレームまたは前記第２のフレームのうちの、前記選択手段により選択されたフレームの前記LDPC符号を前記バリアブルノード計算手段に供給する供給手段と
をさらに備える
ことを特徴とする復号装置。
【請求項３】
請求項１に記載の復号装置であって、
前記チェックノード計算手段により前記第１のフレームと前記第２のフレームのうちの一方のフレームのチェックノードの演算が行われるとき、前記バリアブルノード計算手段は、他方のフレームのバリアブルノードの演算を行う
ことを特徴とする復号装置。
【請求項４】
請求項１に記載の復号装置であって、
前記チェックノードの演算、または前記バリアブルノードの演算のうちの一方の演算に用いられる枝に対応するメッセージデータの読み出しと、他方の演算の結果得られる枝に対応するメッセージデータの書き込みとが同時に行われるメッセージ記憶手段をさらに備える
ことを特徴とする復号装置。
【請求項５】
請求項４に記載の復号装置であって、
前記メッセージ記憶手段は、デュアルポートRAM（Random Access Memory）である
ことを特徴とする復号装置。
【請求項６】
請求項１に記載の復号装置であって、
前記第１のフレームと前記第２のフレームは、連続する２つのフレームである
ことを特徴とする復号装置。
【請求項７】
LDPC(Low Density Parity Check)符号をフレーム単位で復号する復号装置の復号方法であって、
前記LDPC符号の第１のフレームと第２のフレームを交互に選択する選択ステップと、
前記第１のフレームと前記第２のフレームのうちの、前記選択ステップの処理により選択されていないフレームの前記LDPC符号の復号のためのチェックノードの演算を行うチェックノード計算ステップと、
前記第１のフレームと前記第２のフレームのうちの、前記選択ステップの処理により選択されたフレームの前記LDPC符号の復号のためのバリアブルノードの演算を行うバリアブルノード計算ステップと
を含むことを特徴とする復号方法。
【請求項８】
LDPC(Low Density Parity Check)符号のフレーム単位の復号をコンピュータに行わせるプログラムであって、
前記LDPC符号の第１のフレームと第２のフレームを交互に選択する選択ステップと、
前記第１のフレームと前記第２のフレームのうちの、前記選択ステップの処理により選択されていないフレームの前記LDPC符号の復号のためのチェックノードの演算を行うチェックノード計算ステップと、
前記第１のフレームと前記第２のフレームのうちの、前記選択ステップの処理により選択されたフレームの前記LDPC符号の復号のためのバリアブルノードの演算を行うバリアブルノード計算ステップと
を備えることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、復号装置および復号方法、並びにプログラムに関し、特に、低密度パリティ検査符号による符号化が施された符号の復号を行う復号装置および復号方法、並びにプログラムに関する。
【背景技術】
【０００２】
近年、例えば、移動体通信や深宇宙通信といった通信分野、及び地上波又は衛星ディジタル放送といった放送分野の研究が著しく進められているが、それに伴い、誤り訂正符号化及び復号の効率化を目的として符号理論に関する研究も盛んに行われている。
【０００３】
符号性能の理論的限界としては、いわゆるシャノン(C. E. Shannon)の通信路符号化定理によって与えられるシャノン限界が知られている。符号理論に関する研究は、このシャノン限界に近い性能を示す符号を開発することを目的として行われている。近年では、シャノン限界に近い性能を示す符号化方法として、例えば、並列連接畳み込み符号(PCCC(Parallel Concatenated Convolutional Codes))や、縦列連接畳み込み符号(SCCC(Serially Concatenated Convolutional Codes))といった、いわゆるターボ符号化(Turbo coding)と呼ばれる手法が開発されている。また、これらのターボ符号が開発される一方で、古くから知られる符号化方法である低密度パリティ検査符号(Low Density Parity Check codes)（以下、LDPC符号という）が脚光を浴びつつある。
【０００４】
LDPC符号は、R. G. Gallagerによる「R. G. Gallager, "Low Density Parity Check Codes", Cambridge, Massachusetts: M. I. T. Press, 1963」において最初に提案されたものであり、その後、「D. J. C. MacKay, "Good error correcting codes based on very sparse matrices", Submitted to IEEE Trans. Inf. Theory, IT-45, pp. 399-431, 1999」や、「M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi and D. A. Spielman, "Analysis of low density codes and improved designs using irregular graphs", in Proceedings of ACM Symposium on Theory of Computing, pp. 249-258, 1998」等において再注目されるに至ったものである。
【０００５】
LDPC符号は、近年の研究により、ターボ符号等と同様に、符号長を長くしていくにしたがって、シャノン限界に近い性能が得られることがわかりつつある。また、LDPC符号は、最小距離が符号長に比例するという性質があることから、その特徴として、ブロック誤り確率特性がよく、さらに、ターボ符号等の復号特性において観測される、いわゆるエラーフロア現象が殆ど生じないことも利点として挙げられる。
【０００６】
以下、このようなLDPC符号について具体的に説明する。なお、LDPC符号は、線形符号であり、必ずしも２元である必要はないが、ここでは、２元であるものとして説明する。
【０００７】
LDPC符号は、そのLDPC符号を定義する検査行列(parity check matrix)が疎なものであることを最大の特徴とするものである。ここで、疎な行列とは、行列のコンポーネントの"1"の個数が非常に少なく構成されるものであり、疎な検査行列をHで表すものとすると、そのような検査行列としては、例えば、図１に示すように、各列のハミング重み（"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ビットからなる情報メッセージ（ベクトルｕ）を乗算し、nビットからなる符号語ｃ（＝ｕＧ）を生成する。この符号化装置によって生成された符号語は、値が"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が求められる。
【００１４】
【数１】
2005064735.tif 000003
・・・（１）
【００１５】
【数２】
2005064735.tif 000004
・・・（２）
【００１６】
ここで、式（１）と式（２）におけるdvとdcは、それぞれ、検査行列Hの縦方向（列）と横方向（行）の"1"の個数を示す任意に選択可能とされるパラメータであり、例えば、(3,6)符号の場合には、dv=3，dc=6となる。
【００１７】
なお、式（１）または（２）の演算においては、それぞれ、メッセージを出力しようとする枝(edge)から入力されたメッセージを、和または積演算のパラメータとしては用いないことから、和または積演算の範囲が、１乃至dv-1または１乃至dc-1となっている。また、式（２）に示す演算は、実際には、２入力v1，v2に対する１出力で定義される式（３）に示す関数R(v1,v2)のテーブルを予め作成しておき、これを式（４）に示すように連続的（再帰的）に用いることによって行われる。
【００１８】
【数３】
2005064735.tif 000005
・・・（３）
【００１９】
【数４】
2005064735.tif 000006
・・・（４）
【００２０】
ステップＳ１２では、さらに、変数kが"1"だけインクリメントされ、ステップＳ１３に進む。ステップＳ１３では、変数kが所定の繰り返し復号回数N以上であるか否かが判定される。ステップＳ１３において、変数kがN以上ではないと判定された場合、ステップＳ１２に戻り、以下、同様の処理が繰り返される。
【００２１】
また、ステップＳ１３において、変数kがN以上であると判定された場合、ステップＳ１４に進み、式（５）に示す演算を行うことによって最終的に出力する復号結果としてのメッセージviが求められて出力され、LDPC符号の復号処理が終了する。
【００２２】
【数５】
2005064735.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である。
【００３０】
【数６】
2005064735.tif 000008
・・・（６）
【００３１】
更に、x≧0において、φ(x)=ln(tanh(x/2))と定義すると、φ-1(x)=2tanh-1(e-x)であるから、式（６）は、式（７）のように書くことができる。
【００３２】
【数７】
2005064735.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（i＝１からｉ＝ｄcまでのΣφ(|vi|)）を選択し、値D125として、レジスタ１２５に出力して格納させる。レジスタ１２５は、格納している値D125を、９ビットの値D126として、セレクタ１２４と加算器１２６に供給する。制御信号D106が「０」の場合、セレクタ１２４は、レジスタ１２５から供給された値D126を選択し、レジスタ１２５に出力して再格納させる。即ち、検査行列の１行に亘る全ての枝からのメッセージD101（メッセージvi）から求められたφ(|vi|)が積算されるまで、レジスタ１２５は、前回積算されたφ(|vi|)を、セレクタ１２４と加算器１２６に供給する。
【００５５】
一方、FIFOメモリ１２７は、レジスタ１２５から新たな値D126（i＝１からｉ＝ｄcまでのΣφ(|vi|)）が出力されるまでの間、LUT１２１が出力した演算結果D123（φ(|vi|)）を遅延し、５ビットの値D127として減算器１２６に供給する。減算器１２６は、レジスタ１２５から供給された値D126から、FIFOメモリ１２７から供給された値D127を減算し、その減算結果を、５ビットの減算値D128としてLUT１２８に供給する。即ち、減算器１２６は、検査行列の1行に亘る全ての枝からのメッセージD101（メッセージvi）から求められたφ(|vi|)の積算値から、求めたい枝からのメッセージD101（メッセージvi）から求められたφ(|vi|)を減算して、その減算値（i＝１からｉ＝ｄc−１までのΣφ(|vi|)）を減算値D128としてLUT１２８に供給する。
【００５６】
LUT１２８は、減算値D128（i＝１からｉ＝ｄ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（i＝１からｉ＝ｄcまでのΠsign(vi)）を選択し、１ビットの値D132としてレジスタ１３２に出力して格納させる。レジスタ１３２は、格納している値D132を、１ビットの値D133としてセレクタ１３１とEXOR回路１３４に供給する。制御信号D106が「０」の場合、セレクタ１３１は、レジスタ１３２から供給された値D133を選択し、レジスタ１３２に出力して再格納させる。即ち、検査行列の１行に亘る全ての枝からのメッセージD101（メッセージvi）の符号ビットD121が乗算されるまで、レジスタ１３２は、前回格納した値を、セレクタ１３１とEXOR回路１３４に供給する。
【００６０】
一方、FIFOメモリ１３３は、レジスタ１３２から新たな値D133（i＝１からｉ＝ｄcまでのΠsign(vi)）がEXOR回路１３４に供給されるまでの間、符号ビットD121を遅延し、１ビットの値D134としてEXOR回路１３４に供給する。EXOR回路１３４は、レジスタ１３２から供給された値D133と、FIFOメモリ１３３から供給された値D134との排他的論理和を演算することにより、値D133を、値D134で除算し、１ビットの除算結果を除算値D135として出力する。即ち、EXOR回路１３４は、検査行列の１行に亘る全ての枝からのメッセージD101の符号ビットD121（sign(|vi|)）の乗算値を、求めたい枝からのメッセージD101の符号ビットD121（sign(|vi|)）で除算して、その除算値（i＝１からｉ＝ｄ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（i＝１から８までのΣφ(|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
【発明の開示】
【発明が解決しようとする課題】
【０１１２】
上述したように、図９の復号装置を繰り返し用いて、LDPC符号の復号を行う場合、1フレームに対するチェックノード演算とバリアブルノード演算とは交互に行われる。即ち、図９の復号装置では、チェックノード計算器１０１とバリアブルノード計算器１０３のうちの一方の演算が終了し、その演算結果が枝用メモリ１０２または１００に格納されるまで、チェックノード計算器１０１とバリアブルノード計算器１０３のうちの他方は、待機する必要があった。
【０１１３】
従って、図９の復号装置では、チェックノード計算器１０１とバリアブルノード計算器１０３のうちのどちらか一方が演算を行っている時間には、他方は演算を行わないことになり、必要なスループットを満たした上で、復号回数を増やすためには、復号装置を高速に動作させる必要があった。
【０１１４】
しかしながら、復号装置を高速に動作させる場合、復号装置の動作周波数が高くなるため、消費電力が大となり、さらに、装置を構成する部分としても、高速動作に対応することができるものを用いる必要がある。一方、復号装置の動作周波数を抑えるために復号回数を抑えると、復号装置の復号性能を向上させることが困難であった。
【０１１５】
本発明は、このような状況に鑑みてなされたものであり、動作周波数および回路規模を抑えつつ、復号性能を向上させることができるようにするものである。
【課題を解決するための手段】
【０１１６】
本発明の復号装置は、LDPC符号の第１のフレームと第２のフレームを交互に選択する選択手段と、第１のフレームと第２のフレームのうちの、選択手段により選択されていないフレームのLDPC符号の復号のためのチェックノードの演算を行うチェックノード計算手段と、第１のフレームと第２のフレームのうちの、選択手段により選択されたフレームのLDPC符号の復号のためのバリアブルノードの演算を行うバリアブルノード計算手段とを備えることを特徴とする。
【０１１７】
第１のフレームと第２のフレームのLDPC符号を記憶するフレーム記憶手段と、フレーム記億手段に記憶された第１のフレームまたは第２のフレームのうちの、選択手段により選択されたフレームのLDPC符号をバリアブルノード計算手段に供給する供給手段とをさらに備えるようにすることができる。
【０１１８】
チェックノード計算手段により第１のフレームと第２のフレームのうちの一方のフレームのチェックノードの演算が行われるとき、バリアブルノード計算手段は、他方のフレームのバリアブルノードの演算を行うようにすることができる。
【０１１９】
チェックノードの演算、またはバリアブルノードの演算のうちの一方の演算に用いられる枝に対応するメッセージデータの読み出しと、他方の演算の結果得られる枝に対応するメッセージデータの書き込みとが同時に行われるメッセージ記憶手段をさらに備えるようにすることができる。
【０１２０】
メッセージ記憶手段は、デュアルポートRAM（Random Access Memory）であるようにすることができる。
【０１２１】
第１のフレームと第２のフレームは、連続する２つのフレームであるようにすることができる。
【０１２２】
本発明の復号方法は、LDPC符号の第１のフレームと第２のフレームを交互に選択する選択ステップと、第１のフレームと第２のフレームのうちの、選択ステップの処理により選択されていないフレームのLDPC符号の復号のためのチェックノードの演算を行うチェックノード計算ステップと、第１のフレームと第２のフレームのうちの、選択ステップの処理により選択されたフレームのLDPC符号の復号のためのバリアブルノードの演算を行うバリアブルノード計算ステップとを含むことを特徴とする。
【０１２３】
本発明のプログラムは、LDPC符号の第１のフレームと第２のフレームを交互に選択する選択ステップと、第１のフレームと第２のフレームのうちの、選択ステップの処理により選択されていないフレームのLDPC符号の復号のためのチェックノードの演算を行うチェックノード計算ステップと、第１のフレームと第２のフレームのうちの、選択ステップの処理により選択されたフレームのLDPC符号の復号のためのバリアブルノードの演算を行うバリアブルノード計算ステップとを備えることを特徴とする。
【０１２４】
本発明においては、LDPC符号の第１のフレームと第２のフレームを交互に選択される。そして、第１のフレームと第２のフレームのうちの、選択されていないフレームのLDPC符号の復号のためのチェックノードの演算が行われ、第１のフレームと第２のフレームのうちの、選択されたフレームのLDPC符号の復号のためのバリアブルノードの演算が行われる。
【発明の効果】
【０１２５】
本発明によれば、２つのフレームのLDPC符号の復号処理を行なうことができるので、LDPC符号の復号を効率よく行うようにすることができ、また、復号性能を向上させることが可能となる。
【発明を実施するための最良の形態】
【０１２６】
以下に本発明の実施の形態を説明するが、請求項に記載の構成要件と、発明の実施の形態における具体例との対応関係を例示すると、次のようになる。この記載は、請求項に記載されている発明をサポートする具体例が、発明の実施の形態に記載されていることを確認するためのものである。従って、発明の実施の形態中には記載されているが、構成要件に対応するものとして、ここには記載されていない具体例があったとしても、そのことは、その具体例が、その構成要件に対応するものではないことを意味するものではない。逆に、具体例が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その具体例が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。
【０１２７】
さらに、この記載は、発明の実施の形態に記載されている具体例に対応する発明が、請求項に全て記載されていることを意味するものではない。換言すれば、この記載は、発明の実施の形態に記載されている具体例に対応する発明であって、この出願の請求項には記載されていない発明の存在、すなわち、将来、分割出願されたり、補正により追加される発明の存在を否定するものではない。
【０１２８】
請求項１に記載の復号装置（例えば、図１５の復号装置４００）は、LDPC(Low Density Parity Check)符号をフレーム単位で復号する復号装置であって、前記LDPC符号の第１のフレーム（例えば、奇数フレーム）と第２のフレーム（例えば、偶数フレーム）を交互に選択する選択手段（例えば、図１５の制御部４０１）と、前記第１のフレームと前記第２のフレームのうちの、前記選択手段により選択されていないフレームの前記LDPC符号の復号のためのチェックノードの演算を行うチェックノード計算手段（例えば、図１５のチェックノード計算器３０１）と、前記第１のフレームと前記第２のフレームのうちの、前記選択手段により選択されたフレームの前記LDPC符号の復号のためのバリアブルノードの演算を行うバリアブルノード計算手段（例えば、図１５のバリアブルノード計算器３０３）とを備えることを特徴とする。
【０１２９】
請求項２に記載の復号装置は、請求項１に記載の復号装置であって、前記第１のフレームと前記第２のフレームの前記LDPC符号を記憶するフレーム記憶手段（例えば、奇数フレーム受信用メモリ４０２と偶数フレーム受信用メモリ４０３）と、前記フレーム記億手段に記憶された前記第１のフレームまたは前記第２のフレームのうちの、前記選択手段により選択されたフレームの前記LDPC符号を前記バリアブルノード計算手段に供給する供給手段（例えば、セレクタ４０４）とをさらに備えることを特徴とする。
【０１３０】
請求項４に記載の復号装置は、請求項１に記載の復号装置であって、前記チェックノードの演算、または前記バリアブルノードの演算のうちの一方の演算に用いられる枝に対応するメッセージデータの読み出しと、他方の演算の結果得られる枝に対応するメッセージデータの書き込みとが同時に行われるメッセージ記憶手段（例えば、図１５の枝用メモリ３００と枝用メモリ３０２）をさらに備えることを特徴とする。
【０１３１】
請求項７に記載の復号方法は、LDPC(Low Density Parity Check)符号をフレーム単位で復号する復号装置の復号方法であって、前記LDPC符号の第１のフレームと第２のフレームを交互に選択する選択ステップ（例えば、図１６のステップＳ２２、ステップＳ２８）と、前記第１のフレームと前記第２のフレームのうちの、前記選択ステップの処理により選択されていないフレームの前記LDPC符号の復号のためのチェックノードの演算を行うチェックノード計算ステップ（例えば、図１７のステップＳ４２）と、前記第１のフレームと前記第２のフレームのうちの、前記選択ステップの処理により選択されたフレームの前記LDPC符号の復号のためのバリアブルノードの演算を行うバリアブルノード計算ステップ（例えば、図１８のステップＳ６２）とを含むことを特徴とする。
【０１３２】
請求項８に記載のプログラムの各ステップの具体例も、請求項７に記載の復号方法の各ステップの発明の実施の形態における具体例と同様である。
【０１３３】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。
【０１３４】
図１５は、本発明を適用した復号装置４００の構成例を示すブロック図である。
【０１３５】
復号装置４００は、枝用メモリ３００、チェックノード計算器３０１、枝用メモリ３０２、バリアブルノード計算器３０３、制御部４０１、奇数フレーム受信用メモリ４０２、偶数フレーム受信用メモリ４０３、およびセレクタ４０４から構成される。
【０１３６】
復号装置４００では、１つの枝に対応するメッセージを1つずつ計算し、２フレームの受信データの復号を同時に行う。
【０１３７】
即ち、復号装置４００では、チェックノード計算器３０１が、枝用メモリ３００からメッセージデータを1つずつ読み出し、そのメッセージデータを用いて、チェックノード演算を行うと同時に、バリアブルノード計算器３０３が、枝用メモリ３０２からメッセージデータを１つずつ読み出し、そのメッセージデータを用いて、バリアブルノード演算を行う。そして、チェックノード計算器３０１が、チェックノード演算の結果得られるメッセージデータを1つずつ枝用メモリ３０２に格納すると同時に、バリアブルノード計算器３０３が、バリアブルノード演算の結果得られるメッセージデータを1つずつ枝用メモリ３００に格納する。なお、チェックノード計算器３０１とバリアブルノード計算器３０３は、図１０に示したチェックノード計算器１０１とバリアブルノード計算器１０３とそれぞれ同様に構成される。但し、チェックノード計算器３０１とバリアブルノード計算器３０３は、制御部４０１の制御にしたがい、あるフレームのチェックノード演算と、他のフレームのバリアブルノード演算を同時に（同一のタイミングで）行うようになっている。
【０１３８】
枝用メモリ３００は、バリアブルノード計算器３０３によるバリアブルノード演算の結果得られる枝に対応するメッセージ（データ）を格納し、既に格納してあるメッセージをチェックノード計算器３０１に供給する。即ち、枝用メモリ３００は、バリアブルノード計算器３０３から供給され、チェックノード計算器３０１が演算する順番に格納してあるメッセージD401を１つずつ読み出し、チェックノード計算器３０１に供給すると同時に、バリアブルノード計算器３０３が出力するメッセージD405をメッセージD400として受信し、枝用メモリ３００の既に読み出されたメッセージ（メッセージD401）が記憶されていたアドレスに書き込む。即ち、枝用メモリ３００は、チェックノード演算に用いられるメッセージ（データ）D401の読み出しと、バリアブルノード演算の結果得られるメッセージ（データ）D400の書き込みとを、同時に行う。
【０１３９】
なお、枝用メモリ３００には、バリアブルノード計算器３０３のバリアブルノード演算により演算された枝に対応するメッセージが格納されるので、枝用メモリ３００に格納されるデータ量、即ち、枝用メモリ３００に必要とされる記憶容量は、メッセージの量子化ビット数と、全枝数との乗算値となる。このことは、前述の図９の枝用メモリ１００についても同様である。
【０１４０】
チェックノード計算器３０１には、枝用メモリ３００からメッセージD401が供給されるとともに、制御部４０１から制御信号D408が供給される。チェックノード計算器３０１は、制御部４０１から供給される制御信号D408に基づき、前述の図９のチェックノード計算器１０１と同様に、枝用メモリ３００から供給されるメッセージD401を用い、式（７）にしたがって、LDPC符号の復号のためのチェックノードの演算を行い、その演算によって求められたメッセージD402を、枝用メモリ３０２に供給する。チェックノード計算器３０１の詳細構成は、図１０に示したチェックノード計算器１０１と同様である。
【０１４１】
枝用メモリ３０２は、チェックノード計算器３０１によるチェックノード演算の結果得られる枝に対応するメッセージ（データ）を格納し、既に格納してあるメッセージをバリアブルノード計算器３０３に供給する。即ち、枝用メモリ３０２は、チェックノード計算器３０１から供給され、バリアブルノード計算器３０３が演算する順番に格納してあるメッセージD403を1つずつ読み出し、バリアブルノード計算器３０３に供給すると同時に、チェックノード計算器３０１が出力するメッセージD402を受信し、枝用メモリ３０２の既に読み出されたメッセージ（メッセージD403）が記憶されていたアドレスに書き込む。即ち、枝用メモリ３０２は、バリアブルノード演算に用いられるメッセージ（データ）D403の読み出しと、チェックノード演算の結果得られるメッセージ（データ）D402の書き込みとを、同時に行う。
【０１４２】
なお、枝用メモリ３０２には、チェックノード計算器３０１のチェックノード演算により演算された枝に対応するメッセージが格納されるので、枝用メモリ３０１に格納されるデータ量、即ち、枝用メモリ３０２に必要とされる記憶容量は、メッセージの量子化ビット数と、全枝数との乗算値となる。このことは、前述の図９の枝用メモリ１０２についても同様である。
【０１４３】
なお、枝用メモリ３００と３０２は、同時に読み書き可能な、例えば、デュアルポートRAMで構成することができる。
【０１４４】
バリアブルノード計算器３０３には、枝用メモリ３０２からメッセージD403が供給される。また、バリアブルノード計算器３０３には、制御部４０１から制御信号D409が供給されるとともに、セレクタ４０４からLDPC符号の受信データD404が供給される。バリアブルノード計算器３０３は、制御信号D409に基づき、前述の図９のバリアブルノード計算器１０３と同様に、枝用メモリ３０２から供給されるメッセージD403とセレクタ４０４から供給される受信データD404を用い、式（１）にしたがって、LDPC符号の復号のためのバリアブルノード演算を行い、その演算の結果得られる枝に対応するメッセージD405を、メッセージD400として枝用メモリ３００に供給する。バリアブルノード計算器３０３の詳細構成は、図１１に示したバリアブルノード計算器１０３と同様である。
【０１４５】
制御部４０１は、制御信号D408をチェックノード計算器３０１に、制御信号D409をバリアブルノード計算器３０３に、制御信号D410をセレクタ４０４にそれぞれ供給することにより制御する。
【０１４６】
奇数フレーム受信用メモリ４０２は、例えば、最初のフレームから奇数番目のフレーム（以下、適宜、奇数フレームと称する）のLDPC符号化された受信データ（LDPC符号）D406を格納（記億）する。また、奇数フレーム受信用メモリ４０２は、既に格納されている受信データD406を読み出し、セレクタ４０４に供給する。
【０１４７】
偶数フレーム受信用メモリ４０３は、例えば、最初のフレームから偶数番目のフレーム（以下、適宜、偶数フレームと称する）のLDPC符号化された受信データ（LDPC符号）D407を格納（記億）する。また、偶数フレーム受信用メモリ４０３は、既に格納されている受信データD407を読み出し、セレクタ４０４に供給する。
【０１４８】
なお、フレーム単位の受信データは、図示せぬ受信部から奇数フレーム受信用メモリ４０２と偶数フレーム受信用メモリ４０３に供給されて記憶される。また、奇数フレーム受信用メモリ４０２と偶数フレーム受信用メモリ４０３に格納されるデータ量、即ち、奇数フレーム受信用メモリ４０２と偶数フレーム受信用メモリ４０３に必要とされる記憶容量は、LDPC符号の符号長と、受信データの量子化ビット数との乗算値である。
【０１４９】
セレクタ４０４は、制御部４０１から供給される制御信号D410に基づいて、奇数フレーム受信用メモリ４０２から供給される受信データD406、または偶数フレーム受信用メモリ４０３から供給される受信データD407のうちのどちらか一方を、受信データD404として、バリアブルノード計算器３０３と、上述した式（５）の演算を行う不図示のブロックに供給する。
【０１５０】
図１６は、図１５の復号装置４００の復号処理を説明するフローチャートである。この処理は、例えば、奇数フレーム受信用メモリ４０２と偶数フレーム受信用メモリ４０３に、奇数フレームである1番目のフレームと偶数フレームである２番目のフレームの受信データが格納されたとき、開始される。このとき、奇数フレーム受信用メモリ４０２が、格納している奇数フレームである1番目のフレームの受信データD406を読み出して、セレクタ４０４に供給するとともに、偶数フレーム受信用メモリ４０３が、格納している偶数フレームである２番目のフレームの受信データD407を読み出して、セレクタ４０４に供給する。
【０１５１】
なお、復号装置４００の復号回数Ｎは、例えば、あるフレームの受信データすべてが受信されてから、次のフレームの受信データすべてが受信されるまでの時間と、復号装置４００の動作周波数とに基づいて、あらかじめ設定されている。また、ここでは、２フレームの受信後、その２フレームの復号を、次の２フレームを受信するまでの間、繰り返し行うものとする。
【０１５２】
ステップＳ２１において、制御部４０１は、不図示のカウンタの値Ｋを０に初期化し、ステップＳ２２に進む。ステップＳ２２において、制御部４０１は、バリアブルノード計算器３０３の対象フレームとして、奇数フレーム（第１のフレーム）または偶数フレーム（第２のフレーム）のうちの奇数フレームを選択し、制御信号D410が奇数フレームを選択するように設定する。即ち、制御部４０１は、奇数フレームの選択を表す制御信号D410をセレクタ４０４に供給する。このとき、セレクタ４０４は、制御部４０１から供給された制御信号D410にしたがい、奇数フレーム受信用メモリ４０２から供給された奇数フレームの受信データD406、または偶数フレーム受信用メモリ４０３から供給された偶数フレームの受信データD407のうちの対象フレーム（いまの場合、奇数フレーム）となっている受信データを選択し、受信データD404としてバリアブルノード計算器３０３に供給する。そして、制御部４０１は、ステップＳ２２から、ステップＳ２３−１とステップＳ２３−２に進む。
【０１５３】
なお、ステップＳ２３−１乃至ステップＳ２７−１と、ステップＳ２３−２乃至ステップＳ２７−２は、同時に行われる。
【０１５４】
ステップＳ２３−１において、制御部４０１は、制御信号D408を０に設定し、チェックノード計算器３０１に供給し、ステップＳ２４−１に進む。
【０１５５】
ステップＳ２４−１において、チェックノード計算器３０１は、枝用メモリ３００から後述するステップＳ３０−２で格納された、対象フレームとして選択されていない方のフレーム（以下、適宜、非対象フレームという）である偶数フレームに対するバリアブルノード演算の結果得られるメッセージviを読み出し、式（７）にしたがって、非対象フレームに対するチェックノード演算を行う。
【０１５６】
ステップＳ２４−１の処理後は、ステップＳ２５−１に進み、制御部４０１は、チェックノード計算器３０１が、検査行列の１行分のメッセージviを読み出したかどうかを判定し、検査行列の１行分のメッセージviを読み出していないと判定した場合、ステップＳ２４−１に戻り、上述した処理を繰り返す。
【０１５７】
ステップＳ２５−１において、制御部４０１は、検査行列の１行に亘るメッセージviを読み出したと判定した場合、ステップＳ２６−１に進み、制御信号D408を１に設定する。
例えば、検査行列の行の重みが「９」である場合、制御部４０１は、ステップＳ２４−１とステップＳ２５−１の処理を９回繰り返し行い、ステップＳ２５−１からステップＳ２６−１に進む。
【０１５８】
ステップＳ２６−１の処理後は、ステップＳ２７−１に進み、制御部４０１は、１フレーム分の受信データに対するチェックノード演算が終了したかどうかを判定する。ステップＳ２６−１において、制御部４０１は、１フレーム分の受信データに対するチェックノード演算が終了していないと判定した場合、ステップＳ２３−１に戻り、上述した処理を繰り返す。
【０１５９】
ステップＳ２７−１において、制御部４０１は、１フレーム分の受信データに対するチェックノード演算が終了したと判定した場合、ステップＳ２８に進む。
【０１６０】
なお、カウンタの値Ｋが０である場合、非対象フレームに対して、後述するステップＳ３０−２の処理が行われていないので、上述したステップＳ２３−１乃至Ｓ２７−１の処理は行なわれない。
【０１６１】
一方、ステップＳ２３−２において、制御部４０１は、制御信号D409を０に設定し、バリアブルノード計算器３０３に供給して、ステップＳ２４−２に進む。
【０１６２】
ステップＳ２４−２において、バリアブルノード計算器３０３は、枝用メモリ３０２から、後述するステップＳ３０−１で格納された、対象フレームである奇数フレームに対するチェックノード演算の結果得られるメッセージujを読み出し、式（１）にしたがって、対象フレームに対するバリアブルノード演算を行う。なお、バリアブルノード計算器３０３は、最初のバリアブルノード演算を行う場合、即ち、カウンタの値Ｋが０である場合、まだステップＳ３０−１の処理が行なわれていないので、メッセージujを初期値に設定し、バリアブルノード演算を行う。そして、バリアブルノード計算器３０３は、バリアブルノード演算の結果得られるメッセージviを枝用メモリ３００に格納する。
【０１６３】
ステップＳ２４−２の処理後は、ステップＳ２５−２に進み、制御部４０１は、バリアブルノード計算器３０３が、検査行列の１列分のメッセージujを読み出したかどうかを判定し、検査行列の１列分のメッセージujを読み出していないと判定した場合、ステップＳ２４−２に戻り、上述した処理を繰り返す。
【０１６４】
ステップＳ２５−２において、制御部４０１は、検査行列の１列分のメッセージujを読み出したと判定した場合、ステップＳ２６−２に進み、制御信号D409を１に設定する。
例えば、検査行列の列の重みが「５」である場合、制御部４０１は、ステップＳ２４−２とステップＳ２５−２の処理を５回繰り返し行い、ステップＳ２５−２からステップＳ２６−２に進む。
【０１６５】
ステップＳ２６−２の処理後は、ステップＳ２７−２に進み、制御部４０１は、１フレーム分の受信データに対するバリアブルノード演算が終了したかどうかを判定する。ステップＳ２６−２において、制御部４０１は、１フレーム分の受信データに対するバリアブルノード演算が終了していないと判定した場合、ステップＳ２３−２に戻り、上述した処理を繰り返す。
【０１６６】
ステップＳ２７−２において、制御部４０１は、１フレーム分の受信データに対するバリアブルノード演算が終了したと判定した場合、ステップＳ２８に進む。
【０１６７】
ステップＳ２３−１乃至ステップＳ２７−１およびステップＳ２３−２乃至ステップＳ２７−２のように、復号装置４００では、チェックノード計算器３０１による非対象フレームである偶数フレームに対するチェックノード演算と、バリアブルノード計算器３０３による対象フレームである奇数フレームに対するバリアブルノード演算とが、同時に行われる。
【０１６８】
ステップＳ２８において、制御部４０１は、バリアブルノード計算器３０３の対象フレームとして、奇数フレーム（第１のフレーム）または偶数フレーム（第２のフレーム）のうちの偶数フレームを選択し、制御信号D410が偶数フレームを選択するように設定する。即ち、制御部４０１は、偶数フレームの選択を表す制御信号D410をセレクタ４０４に供給する。このとき、セレクタ４０４は、制御部４０１から供給された制御信号D410にしたがい、奇数フレーム受信用メモリ４０２から供給された奇数フレームの受信データD406、または偶数フレーム受信用メモリ４０３から供給された偶数フレームの受信データD407のうちの対象フレーム（いまの場合、偶数フレーム）となっている受信データを選択し、受信データD404としてバリアブルノード計算器３０３に供給する。そして、制御部４０１は、ステップＳ２８から、ステップＳ２９−１とステップＳ２９−２に進む。
【０１６９】
なお、ステップＳ２９−１乃至ステップＳ３３−１と、ステップＳ２９−２乃至ステップＳ３３−２とは、同時に行われる。
【０１７０】
ステップＳ２９−１において、制御部４０１は、制御信号D408を０に設定し、チェックノード計算器３０１に供給し、ステップＳ３０−１に進む。
【０１７１】
ステップＳ３０−１において、チェックノード計算器３０１は、枝用メモリ３００から、ステップＳ２４−２で格納された、非対象フレームである奇数フレームに対するバリアブルノード演算の結果得られるメッセージviを読み出し、式（７）にしたがって、非対象フレームに対するチェックノード演算を行う。そして、チェックノード計算器３０１は、チェックノード演算の結果得られるメッセージujを枝用メモリ３０２に格納する。
【０１７２】
ステップＳ３０−１の処理後は、ステップＳ３１−１に進み、制御部４０１は、チェックノード計算器３０１が、検査行列の１行分のメッセージviを読み出したかどうかを判定し、検査行列の１行分のメッセージviを読み出していないと判定した場合、ステップＳ３０−１に戻り、上述した処理を繰り返す。
【０１７３】
ステップＳ３１−１において、制御部４０１は、検査行列の１行分のメッセージviを読み出したと判定した場合、ステップＳ３２−１に進み、制御信号D408を１に設定する。
例えば、検査行列の行の重みが「９」である場合、制御部４０１は、ステップＳ３０−１とステップＳ３１−１の処理を９回繰り返し行い、ステップＳ３１−１からステップＳ３２−１に進む。
【０１７４】
ステップＳ３２−１の処理後は、ステップＳ３３−１に進み、制御部４０１は、１フレーム分の受信データに対するチェックノード演算が終了したかどうかを判定する。ステップＳ３２−１において、制御部４０１は、１フレーム分の受信データに対するチェックノード演算が終了していないと判定した場合、ステップＳ２９−１に戻り、上述した処理を繰り返す。
【０１７５】
ステップＳ３３−１において、制御部４０１は、１フレーム分の受信データに対するチェックノード演算が終了したと判定した場合、ステップＳ３４に進む。
【０１７６】
一方、ステップＳ２９−２において、制御部４０１は、制御信号D409を０に設定し、バリアブルノード計算器３０３に供給し、ステップＳ３０−２に進む。
【０１７７】
ステップＳ３０−２において、バリアブルノード計算器３０３は、枝用メモリ３０２から、ステップＳ２４−１で格納された、対象フレームである偶数フレームに対するチェックノード演算の結果得られるメッセージujを読み出し、式（１）にしたがって、対象フレームに対するバリアブルノード演算を行う。そして、バリアブルノード計算器３０３は、バリアブルノード演算の結果得られるメッセージviを枝用メモリ３００に格納する。
【０１７８】
ステップＳ３０−２の処理後は、ステップＳ３１−２に進み、制御部４０１は、バリアブルノード計算器３０３が、検査行列の１列分のメッセージujを読み出したかどうかを判定し、検査行列の１列分のメッセージujを読み出していないと判定した場合、ステップＳ３０−２に戻り、上述した処理を繰り返す。
【０１７９】
ステップＳ３１−２において、制御部４０１は、検査行列の１列分のメッセージujを読み出したと判定した場合、ステップＳ３２−２に進み、制御信号D409を１に設定する。
例えば、検査行列の列の重みが「５」である場合、制御部４０１は、ステップＳ３０−２とステップＳ３１−２の処理を５回繰り返し行い、ステップＳ３１−２からステップＳ３２−２に進む。
【０１８０】
ステップＳ３２−２の処理後は、ステップＳ３３−２に進み、制御部４０１は、１フレーム分の受信データに対するバリアブルノード演算が終了したかどうかを判定する。ステップＳ３３−２において、制御部４０１は、１フレーム分の受信データに対するバリアブルノード演算が終了していないと判定した場合、ステップＳ２９−２に戻り、上述した処理を繰り返す。
【０１８１】
ステップＳ３３−２において、制御部４０１は、１フレーム分の受信データに対するバリアブルノード演算が終了したと判定した場合、ステップＳ３４に進む。
【０１８２】
ステップＳ２９−１乃至ステップＳ３３−１およびステップＳ２９−２乃至ステップＳ３３−２のように、復号装置４００では、チェックノード計算器３０１による非対象フレームである奇数フレームに対するチェックノード演算とバリアブルノード計算器３０３による対象フレームである偶数フレームに対するバリアブルノード演算とが、同時に行われる。
【０１８３】
ステップＳ３４において、制御部４０１は、復号回数を表わすカウンタの値Ｋを１だけインクリメントし、ステップＳ３５に進む。ステップＳ３５において、制御部４０１は、カウンタの値Ｋが、予め設定された復号回数Ｎ以上であるかどうかを判定する。
【０１８４】
ステップＳ３５において、カウンタの値Ｋが、復号回数Ｎ以上ではない（Ｎより小さい）と判定した場合、ステップＳ２２に戻り、制御部４０１は、対象フレームを奇数フレームに変更し、制御信号D410が奇数フレームを選択するように設定される。従って、制御部４０１は、奇数フレームと偶数フレームを交互に、対象フレームとして選択する。そして、制御部４０１は、ステップＳ２２からステップＳ２３−１とステップＳ２３−２に進み、上述した処理を繰り返す。
【０１８５】
以上のように、制御部４０１が、奇数フレームと偶数フレームを交互に、対象フレームとして選択し、バリアブルノード計算器３０３が、その選択された対象フレームのバリアブルノード演算を行うとともに、チェックノード計算器３０１が、奇数フレームと偶数フレームのうちの、非対象フレームのチェックノード演算を行うので、バリアブルノード計算器３０３では、奇数フレームと偶数フレームのバリアブルノードの演算が交互に行われ、チェックノード計算器３０１では、偶数フレームと奇数フレームのチェックノード演算が交互に行われる。
【０１８６】
従って、奇数フレームと偶数フレームのうちの一方のバリアブルノード演算と他方のチェックノード演算とが同時に行われ、その後、他方のバリアブルノード演算と一方のチェックノード演算とが同時に行われることが繰り返される。
【０１８７】
一方、ステップＳ３５において、制御部４０１は、カウンタの値ＫがＮ以上であると判定した場合、即ち、奇数フレームのＮ回の復号が終了した場合、ステップＳ３５からステップＳ３６に進む。このとき、不図示のブロックは、Ｎ回の復号が終了した奇数フレームについて、上述した式（５）にしたがって演算を行い、その演算結果をその奇数フレームの最終的な復号結果として出力するとともに、チェックノード計算器３０１は、偶数フレームに対して最後のチェックノード演算を行う。そして、偶数フレームのＮ回の復号が終了され、不図示のブロックは、そのＮ回の復号が終了した偶数フレームについて、上述した式（５）にしたがって演算を行い、その演算結果を、その偶数フレームの最終的な復号結果として出力する。
【０１８８】
ステップＳ３６において、制御部４０１は、復号すべき受信データが、まだ存在するかどうかを判定し、存在すると判定した場合、即ち、次の奇数フレームと偶数フレームの受信データが受信され、奇数フレーム受信用メモリ４０２と偶数フレーム受信用メモリ４０３にそれぞれ供給された場合、奇数フレーム受信用メモリ４０２と偶数フレーム受信用メモリ４０３は、その奇数フレームと偶数フレームの受信データをそれぞれ記憶し、記憶した奇数フレームの受信データD406と偶数フレームの受信データD407をセレクタ４０４に供給して、ステップＳ２１に戻り、以下、同様の処理が繰り返される。
【０１８９】
一方、ステップＳ３６において、制御部４０１は、復号すべきフレームの受信データが存在しないと判定した場合、処理を終了する。
【０１９０】
次に、図１７と図１８のフローチャートを用いて、図１５のチェックノード計算器３０１とバリアブルノード計算器３０３の演算処理について説明する。なお、図１７のチェックノード計算器３０１のチェックノード演算処理と、図１８のバリアブルノード計算器３０３のバリアブルノード演算処理は、同時に行なわれる。
【０１９１】
図１７は、図１５のチェックノード計算器３０１のチェックノード演算処理を説明するフローチャートである。
【０１９２】
ステップＳ４１において、チェックノード計算器３０１は、枝用メモリ３００から、バリアブルノード計算器３０３によるバリアブルノード演算の結果得られる枝に対応するメッセージD405（メッセージｖ）を取得し（読み出し）、ステップＳ４２に進む。
【０１９３】
ステップＳ４２において、チェックノード計算器３０１は、制御部４０１から供給される制御信号D408に基づき、メッセージD405を用いて、上述した式（７）にしたがって、チェックノード演算を行う。
【０１９４】
即ち、チェックノード計算器３０１は、既に枝用メモリ３００に格納されているメッセージ、つまり、バリアブルノード計算器３０３の前回の処理対象である対象フレーム（奇数フレームと偶数フレームのうち、今回、対象フレームとして、制御部４０１により選択されていない非対象フレーム）に対するバリアブルノード演算の結果得られる枝に対応するメッセージD405を用いてチェックノード演算を行う。
【０１９５】
ステップＳ４２の処理後は、ステップＳ４３に進み、チェックノード計算器３０１は、チェックノード演算の結果得られる枝に対応するメッセージD402（メッセージu）を、枝用メモリ３０２に供給して格納し（書き込み）、いま非対象フレームとなっているフレームに対する処理を終了する。
【０１９６】
図１８は、図１５のバリアブルノード計算器３０３のバリアブルノード演算処理を説明するフローチャートである。
【０１９７】
ステップＳ６１において、バリアブルノード計算器３０３は、枝用メモリ３０２から、チェックノード計算器３０１によるチェックノード演算の結果得られる枝に対応するメッセージD403（メッセージu）を取得するとともに、セレクタ４０４を介して、奇数フレーム受信用メモリ４０２または偶数フレーム受信用メモリ４０３から対象フレームの受信データD404を取得する。なお、セレクタ４０４を介して供給された受信データD404のフレーム（対象フレーム）に対して、まだチェックノード演算が行われておらず、枝用メモリ３０２にメッセージD403が格納されていない場合、バリアブルノード計算器３０３は、メッセージD403を取得する代わりに、メッセージuを初期値に設定する。
【０１９８】
ステップＳ６１の処理後は、ステップＳ６２に進み、バリアブルノード計算器３０３は、制御部４０１から供給される制御信号D409に基づいて、メッセージD403と対象フレームの受信データD404を用いて、上述した式（１）にしたがってバリアブルノード演算を行う。そして、バリアブルノード計算器３０３は、ステップＳ６２からステップＳ６３に進み、バリアブルノード演算の結果得られる枝に対応するメッセージD405（メッセージｖ）を枝用メモリ３００に供給して格納し、いま対象フレームとなっているフレームに対する処理を終了する。
【０１９９】
以上のように、チェックノード計算器３０１において、２つのフレームのチェックノード演算を交互に行うとともに、バリアブルノード計算器３０３において、その２つのフレームのバリアブルノード演算を交互に行うことにより、チェックノード計算器３０１とバリアブルノード計算器３０３では、２つのフレームのうちの一方のチェックノード演算またはバリアブルノード演算と、他方のバリアブルノード演算またはチェックノード演算とが、同時に演算が行われるので、理論的には、前述の図９の場合の２倍の回数の復号を行うことができる。
【０２００】
なお、図１６では、奇数フレームと偶数フレームの２つのフレームの受信データの復号を、次の２つのフレームの受信データすべてを受信するまでの間行うようにしたが、１つのフレームの受信データの受信後、その受信データの復号を、その後の２つのフレームの受信データすべてを受信するまでの間行うこともできる。
【０２０１】
図１９は、１フレームの受信データすべてを受信し終わるごとに、その１フレームの受信データの復号を開始し、各フレームにつき、次の２フレームの受信データすべてを受信するまで、復号を行う場合の、図１５の復号装置４００の処理の概要を説明するタイミングチャートである。
【０２０２】
なお、図１９において（後述する図２０においても同様）、横軸は、時間を表している。また、図１９では、復号回数は８回に設定されている。
【０２０３】
図１９上から１番目は、復号装置４００が受信する受信データのフレームを表している。なお、ｎ番目のフレームを、フレーム＃ｎと表わすこととする。
【０２０４】
いま、フレーム＃ｎに注目すると、復号装置４００は、フレーム＃ｎの受信データのすべての受信が完了し、その次の（連続する）フレーム＃ｎ＋１の受信データの受信が開始されると、フレーム＃ｎの復号を開始する。
【０２０５】
即ち、復号装置４００では、バリアブルノード計算器３０３が、まず、フレーム＃ｎの受信データを用いて、フレーム＃ｎの１回目のバリアブルノード演算を行い、その演算結果としてのメッセージを得る（図１９上から３番目）。さらに、チェックノード計算器３０１が、１回目のバリアブルノード演算結果としてのメッセージを用いて、フレーム＃ｎの１回目のチェックノード演算を行い、その演算結果としてのメッセージを得る（図１９上から２番目）。そして、バリアブルノード計算器３０３が、１回目のチェックノード演算結果としてのメッセージと、フレーム＃ｎの受信データを用いて、フレーム＃ｎの２回目のバリアブルノード演算を行い、その演算結果としてのメッセージを得る。さらに、チェックノード計算器３０１が、２回目のバリアブルノード演算結果としてのメッセージを用いて、フレーム＃ｎの２回目のチェックノード演算を行い、その演算結果としてのメッセージを得る。以下、同様にして、復号装置４００では、フレーム＃ｎに対して、４回ずつのバリアブルノード演算とチェックノード演算が行われる。
【０２０６】
その後、フレーム＃ｎ＋１の受信データのすべての受信が完了する直前において、バリアブルノード計算器３０３が、４回目のチェックノード演算結果としてのメッセージと、フレーム＃ｎの受信データを用いて、フレーム＃ｎの５回目のバリアブルノード演算を行い、その演算結果としてのメッセージを得る（図１９上から３番目）。
【０２０７】
そして、フレーム＃ｎ＋１の受信データのすべての受信が完了し、その次のフレーム＃ｎ＋２の受信データの受信が開始されると（図１９上から１番目）、チェックノード計算器３０１が、５回目のバリアブルノード演算結果としてのメッセージを用いて、フレーム＃ｎの５回目のチェックノード演算を行い、その演算結果としてのメッセージを得る（図１９上から２番目）。さらに、バリアブルノード計算器３０３が、５回目のチェックノード演算結果としてのメッセージと、フレーム＃ｎの受信データを用いて、フレーム＃ｎの６回目のバリアブルノード演算を行い、その演算結果としてのメッセージを得る。さらに、チェックノード計算器３０１が、６回目のバリアブルノード演算結果としてのメッセージを用いて、フレーム＃ｎの６回目のチェックノード演算を行い、その演算結果としてのメッセージを得る。以下、同様にして、復号装置４００では、フレーム＃ｎに対して、延べ８回ずつのバリアブルノード演算とチェックノード演算が行われる。
【０２０８】
その後、復号装置４００では、８回目のチェックノード演算結果としてのメッセージと、フレーム＃ｎの受信データを用いて、式（５）の演算が行われ、これにより、フレーム＃ｎの最終的な復号結果が求められる（図１９下から１番目）。
【０２０９】
一方、復号装置４００では、フレーム＃ｎ＋１の受信データのすべての受信が完了し、その次のフレーム＃ｎ＋２の受信データの受信が開始されると（図１９上から１番目）、フレーム＃ｎの復号と並列して、フレーム＃ｎ＋１の復号が開始される。
【０２１０】
即ち、フレーム＃ｎ＋２の受信データの受信が開始されると、上述したように、チェックノード計算器３０１が、フレーム＃ｎの５回目のバリアブルノード演算結果としてのメッセージを用いて、フレーム＃ｎの５回目のチェックノード演算を行い、その演算結果としてのメッセージを得るが（図１９上から２番目）、そのタイミングでは、バリアブルノード計算器３０３が、直前に受信が完了したフレーム＃ｎ＋１の受信データを用いて、フレーム＃ｎ＋１の１回目のバリアブルノード演算を行い、その演算結果としてのメッセージを得る（図１９上から３番目）。つまり、フレーム＃ｎの５回目のチェックノード演算と、フレーム＃ｎ＋１の１回目のバリアブルノード演算とが、同時に行われる。
【０２１１】
その後、上述したように、バリアブルノード計算器３０３が、フレーム＃ｎの５回目のチェックノード演算結果としてのメッセージと、フレーム＃ｎの受信データを用いて、フレーム＃ｎの６回目のバリアブルノード演算を行い、その演算結果としてのメッセージを得るが（図１９上から３番目）、そのタイミングでは、チェックノード計算器３０１が、フレーム＃ｎ＋１の１回目のバリアブルノード演算結果としてのメッセージを用いて、フレーム＃ｎ＋１の１回目のチェックノード演算を行い、その演算結果としてのメッセージを得る（図１９上から２番目）。つまり、フレーム＃ｎの６回目のバリアブルノード演算と、フレーム＃ｎ＋１の１回目のチェックノード演算とが、同時に行われる。
【０２１２】
以下、同様にして、フレーム＃ｎのチェックノード演算と、フレーム＃ｎ＋１のバリアブルノード演算とが同時に行われることと、フレーム＃ｎのバリアブルノード演算と、フレーム＃ｎ＋１のチェックノード演算とが同時に行われることが、交互に繰り返される。
【０２１３】
そして、フレーム＃ｎに対して、延べ８回ずつのバリアブルノード演算とチェックノード演算が行われると、上述したように、８回目のチェックノード演算結果としてのメッセージと、フレーム＃ｎの受信データを用いて、式（５）の演算が行われ、これにより、フレーム＃ｎの最終的な復号結果が求められる（図１９下から１番目）。
【０２１４】
フレーム＃ｎに対して、延べ８回ずつのバリアブルノード演算とチェックノード演算が行われた時点では、フレーム＃ｎ＋１に対しては、４回ずつバリアブルノード演算とチェックノード演算が行われている。そして、フレーム＃ｎの最終的な復号結果が得られると、バリアブルノード計算器３０３が、フレーム＃ｎ＋１の４回目のチェックノード演算結果としてのメッセージと、フレーム＃ｎ＋１の受信データを用いて、フレーム＃ｎ＋１の５回目のバリアブルノード演算を行い、その演算結果としてのメッセージを得る（図１９上から３番目）。
【０２１５】
この時点で、フレーム＃ｎ＋２の受信データのすべての受信が完了し（図１９上から１番目）、その次のフレーム＃ｎ＋３の受信データの受信が開始され、チェックノード計算器３０１が、フレーム＃ｎ＋１の５回目のバリアブルノード演算結果としてのメッセージを用いて、フレーム＃ｎ＋１の５回目のチェックノード演算を行い、その演算結果としてのメッセージを得る（図１９上から２番目）。そのタイミングでは、バリアブルノード計算器３０３が、直前に受信が完了したフレーム＃ｎ＋２の受信データを用いて、フレーム＃ｎ＋２の１回目のバリアブルノード演算を行い、その演算結果としてのメッセージを得る（図１９上から３番目）。つまり、フレーム＃ｎ＋１の５回目のチェックノード演算と、フレーム＃ｎ＋２の１回目のバリアブルノード演算とが、同時に行われる。
【０２１６】
以下、同様にして、フレーム＃ｎ＋１のチェックノード演算と、フレーム＃ｎ＋２のバリアブルノード演算とが同時に行われることと、フレーム＃ｎ＋１のバリアブルノード演算と、フレーム＃ｎ＋２のチェックノード演算とが同時に行われることが、交互に繰り返される。
【０２１７】
そして、フレーム＃ｎ＋１に対して、延べ８回ずつのバリアブルノード演算とチェックノード演算が行われると、８回目のチェックノード演算結果としてのメッセージと、フレーム＃ｎ＋１の受信データを用いて、式（５）の演算が行われ、これにより、フレーム＃ｎ＋１の最終的な復号結果が求められる（図１９下から１番目）。
【０２１８】
フレーム＃ｎ＋２以降のフレームも、同様にして復号されていく。
【０２１９】
以上のように、２つのフレームのうちの一方のチェックノード演算と、他方のバリアブルノード演算とを同時に行い、その後、他方のバリアブルノード演算と、一方のチェックノード演算とを同時に行うことを繰り返すことにより、１つのフレームのバリアブルノード演算だけを行い、その後、その１つのフレームのチェックノード演算だけを行うことを繰り返す場合に比較して、単純には、復号回数を２倍にすることができる。
【０２２０】
即ち、図２０は、１つのフレームのバリアブルノード演算だけを行い、その後、その１つのフレームのチェックノード演算だけを行うことを繰り返す復号を行う従来の復号装置（例えば、図９の復号装置）の復号処理を説明するタイミングチャートである。
【０２２１】
なお、図２０では、１フレームの受信データを受信するのに要する時間と、復号の動作周波数のいずれも、図１９における場合と同一であるとする。
【０２２２】
図２０上から１番目は、従来の復号装置が受信する受信データのフレームを表しており、いまの場合、図１９上から１番目と同一である。
【０２２３】
いま、フレーム＃ｎに注目すると、従来の復号装置は、フレーム＃ｎの受信データのすべての受信が完了し、その次のフレーム＃ｎ＋１の受信データの受信が開始されると、フレーム＃ｎの復号を開始する。
【０２２４】
即ち、従来の復号装置では、まず、フレーム＃ｎの受信データを用いて、フレーム＃ｎの１回目のバリアブルノード演算が行われ、その演算結果としてのメッセージが得られる（図２０上から３番目）。さらに、フレーム＃ｎの１回目のバリアブルノード演算結果としてのメッセージを用いて、フレーム＃ｎの１回目のチェックノード演算が行われ、その演算結果としてのメッセージが得られる(図２０上から２番目)。そして、フレーム＃ｎの１回目のチェックノード演算結果としてのメッセージと、フレーム＃ｎの受信データを用いて、フレーム＃ｎの２回目のバリアブルノード演算が行われ、その演算結果としてのメッセージが得られる。さらに、フレーム＃ｎの２回目のバリアブルノード演算結果としてのメッセージを用いて、フレーム＃ｎの２回目のチェックノード演算が行われ、その演算結果としてのメッセージが得られる。以下、同様にして、従来の復号装置では、フレーム＃ｎに対して、４回ずつのバリアブルノード演算とチェックノード演算が行われる。
【０２２５】
その後、フレーム＃ｎ＋１の受信データのすべての受信が完了する直前において、フレーム＃ｎの４回目のチェックノード演算結果としてのメッセージと、フレーム＃ｎの受信データを用いて、式（５）の演算が行われ、これにより、フレーム＃ｎの最終的な復号結果が求められる（図２０下から１番目）。
【０２２６】
即ち、従来の復号装置では、フレーム＃ｎのバリアブルノード演算またはチェックノード演算のいずれか一方が行われている間、他方の演算は行われない。このため、フレーム＃ｎの受信データの復号は、例えば、その次のフレーム＃ｎ＋１の受信データすべての受信が完了するまでの１フレームの期間に完了しなければならず、このため、フレーム＃ｎについては、４回、即ち、図１９における場合の1/2の回数の復号しか行うことができない。
【０２２７】
フレーム＃ｎの最終的な復号結果が求められた後、フレーム＃ｎ＋１の受信データのすべての受信が完了し、その次のフレーム＃ｎ＋２の受信データの受信が開始されると、従来の復号装置は、上述したフレーム＃ｎの復号を行う場合と同様に、フレーム＃ｎ＋１の復号を開始する。従って、フレーム＃ｎ＋１についても、図１９における場合の1/2の回数である4回の復号しか行うことができない。
【０２２８】
フレーム＃ｎ＋２以降のフレームも、同様にして復号されていくため、やはり、図１９における場合の1/2の回数である4回の復号しか行うことができない。
【０２２９】
逆に言えば、図１５の復号装置４００は、従来の復号装置の２倍の回数の復号を行うことができる。
【０２３０】
なお、図１６のフローチャートで説明したように、２フレームの受信データすべてが受信されるのを待って、その２フレームの受信データの復号を、その次の２フレームの受信データすべてが受信されるまでの間行う場合であっても、また、図１９で説明したように、１フレームの受信データすべてを受信するたびに、その１フレームの受信データの復号を、その次の２フレームの受信データすべてが受信されるまでの間行う場合であっても、復号回数は、従来の復号装置の２倍の回数とすることができる。但し、１フレームの受信データすべてを受信するたびに、その１フレームの受信データの復号を、その次の２フレームの受信データすべてが受信されるまでの間行う場合は、２フレームの受信データすべてが受信されるのを待って、その２フレームの受信データの復号を、その次の２フレームの受信データすべてが受信されるまでの間行う場合よりも、最初の１フレーム目の復号結果を、早期に得ることができる。
【０２３１】
以上のように、復号装置４００では、図９の復号装置の受信用メモリ１０４を、２つの奇数フレーム受信用メモリ４０２と偶数フレーム受信用メモリ４０３に変更するとともに、図９の制御部１０５を、制御部４０１に変更し、セレクタ４０４を新たに設けるという、僅かな変更を加えるだけで、従来に比べて効率の良い復号を行うことができる。
【０２３２】
また、復号装置４００では、同一の動作周波数で、従来の２倍の復号回数の復号を行うことができ、これにより、復号性能を改善することができる。また、従来と同一の復号回数にした場合、復号装置４００では、動作周波数を半分にすることができ、消費電力を抑えることがきる。従って、復号装置４００では、消費電力を抑えて、従来と同一の性能の復号を行うことができる。
【０２３３】
なお、復号装置４００は、全ての枝のメッセージを同時に行う復号装置やＰ個の枝のメッセージを同時に行う復号装置にも適用することができる。
【０２３４】
さらに、枝用メモリ３００と枝用メモリ３０２は、デュアルポートRAMではなく、複数個のシングルポートRAMから構成されるようにしてもよい。この場合、１つのシングルポートRAMへの読み出しと書き込みが同時に重ならないように制御を行う必要がある。複数個のシングルポートRAMを用いた場合、デュアルポートRAMを用いる場合に比べて、復号装置４００の回路規模を小さくすることができる。
【０２３５】
また、上述した説明では、奇数フレームと偶数フレームの２つのフレームの復号処理（バリアブルノードとチェックノードの演算）を同時に行うようにしたが、復号装置４００を複数個接続することにより、３つ以上のフレームの復号処理を同時に行うようにすることもできる。
【０２３６】
次に、上述した一連の処理は、ハードウェアにより行うこともできるし、ソフトウェアにより行うこともできる。一連の処理をソフトウェアによって行う場合には、そのソフトウェアを構成するプログラムが、汎用のコンピュータ等にインストールされる。
【０２３７】
そこで、図２１は、上述した一連の処理を実行するプログラムがインストールされるコンピュータの一実施の形態の構成例を示している。
【０２３８】
プログラムは、コンピュータに内蔵されている記録媒体としてのハードディスク９０５やＲＯＭ９０３に予め記録しておくことができる。
【０２３９】
あるいはまた、プログラムは、フレキシブルディスク、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)やスピーカ等で構成される出力部９０６から出力、あるいは、通信部９０８から送信、さらには、ハードディスク９０５に記録等させる。
【０２４２】
ここで、本明細書において、コンピュータに各種の処理を行わせるためのプログラムを記述する処理ステップは、必ずしもフローチャートとして記載された順序に沿って時系列に処理する必要はなく、並列的あるいは個別に実行される処理（例えば、並列処理あるいはオブジェクトによる処理）も含むものである。
【０２４３】
また、プログラムは、１のコンピュータにより処理されるものであっても良いし、複数のコンピュータによって分散処理されるものであっても良い。さらに、プログラムは、遠方のコンピュータに転送されて実行されるものであっても良い。
【図面の簡単な説明】
【０２４４】
【図１】LDPC符号の検査行列Hを説明する図である。
【図２】LDPC符号の復号手順を説明するフローチャートである。
【図３】メッセージの流れを説明する図である。
【図４】LDPC符号の検査行列の例を示す図である。
【図５】検査行列のタナーグラフを示す図である。
【図６】バリアブルノードを示す図である。
【図７】チェックノードを示す図である。
【図８】LDPC符号の検査行列の例を示す図である。
【図９】ノード演算を１つずつ行うLDPC符号の復号装置の構成例を示すブロック図である。
【図１０】メッセージを１つずつ計算するチェックノード計算器の構成例を示すブロック図である。
【図１１】メッセージを１つずつ計算するバリアブルノード計算器の構成例を示すブロック図である。
【図１２】ノード演算を全て同時に行うLDPC符号の復号装置の構成例を示すブロック図である。
【図１３】メッセージを同時に計算するチェックノード計算器の構成例を示すブロック図である。
【図１４】メッセージを同時に計算するバリアブルノード計算器の構成例を示すブロック図である。
【図１５】本発明を適用した復号装置の一実施の形態の構成例を示すブロック図である。
【図１６】図１５の復号装置の復号処理を説明するフローチャートである。
【図１７】図１５のチェックノード計算器のチェックノード演算処理を説明するフローチャートである。
【図１８】図１５のバリアブルノード計算器のバリアブルノード演算処理を説明するフローチャートである。
【図１９】図１５の復号装置の復号処理を説明するタイミングチャートである。
【図２０】１つのフレームのチェックノード演算とバリアブルノード演算を交互に行う復号装置の処理を説明するタイミングチャートである。
【図２１】本発明を適用したコンピュータの一実施の形態の構成例を示すブロック図である。
【符号の説明】
【０２４５】
３００  枝用メモリ，  ３０１  チェックノード計算器，  ３０２  枝用メモリ，  ３０３  バリアブルノード計算器，  ４００  復号装置，  ４０１  制御部，  ４０２  奇数フレーム受信用メモリ，  ４０３  偶数フレーム受信用メモリ，  ４０４  セレクタ，  ９０１  バス，  ９０２  CPU，  ９０３  ROM，  ９０４  RAM，  ９０５  ハードディスク，  ９０６  出力部，  ９０７  入力部，  ９０８  通信部，  ９０９  ドライブ，  ９１０  入出力インタフェース，  ９１１  リムーバブル記録媒体
【図１】
2005064735.tif 000010
【図２】
2005064735.tif 000011
【図３】
2005064735.tif 000012
【図４】
2005064735.tif 000013
【図５】
2005064735.tif 000014
【図６】
2005064735.tif 000015
【図７】
2005064735.tif 000016
【図８】
2005064735.tif 000017
【図９】
2005064735.tif 000018
【図１０】
2005064735.tif 000019
【図１１】
2005064735.tif 000020
【図１２】
2005064735.tif 000021
【図１３】
2005064735.tif 000022
【図１４】
2005064735.tif 000023
【図１５】
2005064735.tif 000024
【図１６】
2005064735.tif 000025
【図１７】
2005064735.tif 000026
【図１８】
2005064735.tif 000027
【図１９】
2005064735.tif 000028
【図２０】
2005064735.tif 000029
【図２１】
2005064735.tif 000030