(57)【特許請求の範囲】
【請求項１】
LDPC(Low Density Parity Check)符号の復号方法であって、
元の検査行列に対して、行置換と列置換のうちの一方または両方を行って得られる変換検査行列を用いて、前記LDPC符号を復号する復号ステップを備える
ことを特徴とする復号方法。
【請求項２】
請求項１に記載の復号方法であって、
P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、前記変換検査行列は、複数の前記構成行列の組合せで表される
ことを特徴とする復号方法。
【請求項３】
請求項１に記載の復号方法であって、
受信した前記LDPC符号の符号系列に対して、前記元の検査行列に対して行われた列置換と同一の列置換を行い、置換符号系列を出力する符号系列置換ステップをさらに備え、
前記復号ステップにおいて、前記変換検査行列と、前記置換符号系列とを用いて、前記符号系列を復号する
ことを特徴とする復号方法。
【請求項４】
LDPC(Low Density Parity Check)符号の復号装置であって、
元の検査行列に対して、行置換と列置換のうちの一方または両方を行って得られる変換検査行列を用いて、前記LDPC符号を復号する復号手段を備える
ことを特徴とする復号装置。
【請求項５】
請求項４に記載の復号装置であって、
P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、前記変換検査行列は、複数の前記構成行列の組合せで表される
ことを特徴とする復号装置。
【請求項６】
請求項５に記載の復号装置であって、
前記復号手段は、
前記LDPC符号の復号のためのP個のチェックノードの演算を同時に行うチェックノード計算手段と、
前記LDPC符号の復号のためのP個のバリアブルノードの演算を同時に行うバリアブルノード計算手段と
を有する
ことを特徴とする復号装置。
【請求項７】
請求項６に記載の復号装置であって、
前記チェックノード計算手段は、チェックノードの演算を行うP個のチェックノード計算器を有し、
前記バリアブルノード計算手段は、バリアブルノードの演算を行うP個のバリアブルノード計算器を有する
ことを特徴とする復号装置。
【請求項８】
請求項６に記載の復号装置であって、
前記復号手段は、前記P個のチェックノードの演算、または前記P個のバリアブルノードの演算の結果得られるP個の枝に対応するメッセージデータを同時に読み書きするメッセージ記憶手段をさらに有する
ことを特徴とする復号装置。
【請求項９】
請求項８に記載の復号装置であって、
前記メッセージ記憶手段は、チェックノード演算時に読み出される枝に対応するメッセージデータを、前記変換検査行列の１を行方向に詰めるように格納する
ことを特徴とする復号装置。
【請求項１０】
請求項８に記載の復号装置であって、
前記メッセージ記憶手段は、バリアブルノード演算時に読み出される枝に対応するメッセージデータを、前記変換検査行列の１を列方向に詰めるように格納する
ことを特徴とする復号装置。
【請求項１１】
請求項８に記載の復号装置であって、
前記メッセージ記憶手段は、前記変換検査行列を表す構成行列のうちの、重みが２以上の構成行列について、その構成行列を、重みが１の単位行列、準単位行列、またはシフト行列の和の形で表現したときの、その重みが１の単位行列、準単位行列、またはシフト行列に属するP個の枝に対応するメッセージを、同一のアドレスに格納する
ことを特徴とする復号装置。
【請求項１２】
請求項８に記載の復号装置であって、
前記メッセージ記憶手段は、行数／P個のFIFOと、列数／P個のFIFOとで構成され、
前記行数／P個のFIFOと列数／P個のFIFOは、それぞれ、前記検査行列の行と列の重みに対応するワード数を有する
ことを特徴とする復号装置。
【請求項１３】
請求項８に記載の復号装置であって、
前記メッセージ記憶手段は、RAM(Random Access Memory)で構成され、
前記RAMは、前記メッセージデータを、読み出される順番に詰めて格納し、格納位置順に読み出す
ことを特徴とする復号装置。
【請求項１４】
請求項６に記載の復号装置であって、
前記復号手段は、受信情報を格納するとともに、P個の前記受信情報を同時に読み出す受信情報記憶手段をさらに有する
ことを特徴とする復号装置。
【請求項１５】
請求項１４に記載の復号装置であって、
前記受信情報記憶手段は、前記受信情報を、前記バリアブルノードの演算に必要となる順番に読み出すことができるように格納する
ことを特徴とする復号装置。
【請求項１６】
請求項６に記載の復号装置であって、
前記復号手段は、前記P個のチェックノードの演算、または前記P個のバリアブルノードの演算の結果得られるメッセージをサイクリックシフトするサイクリックシフト手段をさらに有する
ことを特徴とする復号装置。
【請求項１７】
請求項１６に記載の復号装置であって、
前記サイクリックシフト手段は、バレルシフタで構成される
ことを特徴とする復号装置。
【請求項１８】
請求項４に記載の復号装置であって、
受信した前記LDPC符号の符号系列に対して、前記元の検査行列に対して行われた列置換と同一の列置換を行い、置換符号系列を出力する符号系列置換手段をさらに備え、
前記復号手段は、前記変換検査行列と、前記置換符号系列とを用いて、前記符号系列を復号する
ことを特徴とする復号装置。
【請求項１９】
請求項１８に記載の復号装置であって、
前記復号手段の出力に対して、前記元の検査行列に対して行われた列置換の逆置換を行い、最終的な復号結果を出力する逆置換手段をさらに備える
ことを特徴とする復号装置。
【請求項２０】
LDPC(Low Density Parity Check)符号の復号をコンピュータに行わせるプログラムであって、
元の検査行列に対して、行置換と列置換のうちの一方または両方を行って得られる変換検査行列を用いて、前記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が求められる。
【００１４】
【数１】
0004224777.tif 000002
0004224777.tif 000003
【００１５】
【数２】
0004224777.tif 000004
0004224777.tif 000005
【００１６】
ここで、式（１）と式（２）におけるdvとdcは、それぞれ、検査行列Hの縦方向（列）と横方向（行）の"1"の個数を示す任意に選択可能とされるパラメータであり、例えば、(3,6)符号の場合には、dv=3，dc=6となる。
【００１７】
なお、式（１）または（２）の演算においては、それぞれ、メッセージを出力しようとする枝(edge)（バリアブルノードとチェックノードとを結ぶ線）から入力されたメッセージを、和または積演算のパラメータとしては用いないことから、和または積演算の範囲が、１乃至dv-1または１乃至dc-1となっている。また、式（２）に示す演算は、実際には、２入力v1，v2に対する１出力で定義される式（３）に示す関数R(v1,v2)のテーブルを予め作成しておき、これを式（４）に示すように連続的（再帰的）に用いることによって行われる。
【００１８】
【数３】
0004224777.tif 000006
0004224777.tif 000007
【００１９】
【数４】
0004224777.tif 000008
0004224777.tif 000009
【００２０】
ステップＳ１２では、さらに、変数kが"1"だけインクリメントされ、ステップＳ１３に進む。ステップＳ１３では、変数kが所定の繰り返し復号回数Nよりも大きいか否かが判定される。ステップＳ１３において、変数kがNよりも大きくないと判定された場合、ステップＳ１２に戻り、以下、同様の処理が繰り返される。
【００２１】
また、ステップＳ１３において、変数kがNよりも大きいと判定された場合、ステップＳ１４に進み、式（５）に示す演算を行うことによって最終的に出力する復号結果としてのメッセージviが求められて出力され、LDPC符号の復号処理が終了する。
【００２２】
【数５】
0004224777.tif 000010
0004224777.tif 000011
【００２３】
ここで、式（５）の演算は、式（１）の演算とは異なり、バリアブルノードに接続している全ての枝からの入力メッセージを用いて行われる。
【００２４】
このような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である。
【００３０】
【数６】
0004224777.tif 000012
0004224777.tif 000013
【００３１】
更に、x≧0において、φ(x)=ln(tanh(x/2))と定義すると、φ-1(x)=2tanh-1(e-x)であるから、式（６）は、式（７）のように書くことができる。
【００３２】
【数７】
0004224777.tif 000014
0004224777.tif 000015
【００３３】
チェックノードでは、図７のように、式（７）の演算（チェックノード演算）を行う。すなわち、図７において、計算しようとしている枝に対応するメッセージ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として、チェックノード計算器１０１に供給する。チェックノード計算器１０１は、枝用メモリ１００から供給されるメッセージD101を用いて、式（７）に従って演算を行い、その演算によって求められたメッセージD102を、後段の枝用メモリ１０２に供給する。
【００４３】
ここで、図１０は、チェックノード計算を一つずつ行う図９のチェックノード計算器１０１の構成例を示している。
【００４４】
図１０のチェックノード計算器１０１では、枝用メモリ１００から供給される、検査行列の各列に対応するバリアブルノードからのメッセージviを一つずつ読み込み、式（７）におけるφ(|vi|)の演算をLUTによって行う。さらに、検査行列の１行に亘る各列に対応するバリアブルノードからのメッセージviから求められたφ(|vi|)が積算され、これにより、全ての枝からのメッセージviから求められたφ(|vi|)の積算値が求められる。その後、その積算値から、メッセージujを求めたい枝から求められてFIFO（FIFOメモリ）で遅延されたφ(|vi|)が減算され、これにより、メッセージujを求めたい枝について、式（７）におけるΣφ(|vi|)が求められる。即ち、チェックノードへの枝すべてからのメッセージの和から、メッセージujを求めたい枝からのメッセージを減算することで、メッセージujを求めたい枝へのメッセージが求められる。さらに、LUTによって、式（７）におけるφ-1(Σφ(|vi|))の演算が行われる。同時に、メッセージujの符号ビット、即ち、式（７）におけるΠsign(vi)も、EXOR回路を用いて同様に計算される。以上のようにして、式（７）の演算が行われ、メッセージujが求められる。
【００４５】
なお、図１０では、各メッセージが符号ビットを合わせて合計６ビット(bit)に量子化されているものとして、チェックノード計算器１０１を表している。また、ここで処理の対象としている図８の検査行列の行の重み(row weight)の最大は９であるため、即ち、チェックノードに供給されるメッセージの最大数は９であるため、チェックノード計算器１０１は、９個のメッセージ（φ(|vi|)）を遅延させるFIFO(First In First Out)を持っている。
【００４６】
図９に戻り、枝用メモリ１０２は、前段のチェックノード計算器１０１から供給される出力メッセージD102を、後段のバリアブルノード計算器１０３が読み出す順番に格納していく。そして、枝用メモリ１０２は、バリアブルノード計算のフェーズでは、メッセージ出力D102を、格納してある順番通りに、メッセージ出力D103として、バリアブルノード計算器１０３に供給する。
【００４７】
バリアブルノード計算器１０３は、枝用メモリ１０２から供給されるメッセージD103と受信用メモリ１０４から供給される受信データ（LDPC符号の受信値）D104を用いて式（１）に従って演算を行い、その演算の結果得られるメッセージD105を、図示せぬ後段の復号装置の枝用メモリ１００に供給する。
【００４８】
ここで、図１１は、バリアブルノード計算を一つずつ行う図９のバリアブルノード計算器１０３の構成例を示している。
【００４９】
図１１のバリアブルノード計算器１０３では、枝用メモリ１０２から供給される、検査行列の各行に対応するチェックノードからのメッセージujを一つずつ読み込み、検査行列の１列に亘る各行に対応するチェックノードからのメッセージを積算して、その積算値を求める。その後、その積算値から、メッセージviを求めたい枝から供給されてFIFOで遅延されたメッセージが減算される。さらに、その結果得られる減算値から、受信値u0iを加算することで、式（１）の演算が行われ、これにより、メッセージviが求められる。即ち、バリアブルノードへの枝すべてからのメッセージの和から、メッセージviを求めたい枝からのメッセージを減算することで、メッセージviを求めたい枝へのメッセージが求められる。
【００５０】
図１１においても、図１０における場合と同様に、各メッセージが符号ビットを合わせて合計６ビットに量子化されているものとして、バリアブルノード計算器１０３を表している。また、ここで処理の対象としている図８の検査行列においては、列の重み(column weight)の最大値が５であるため、バリアブル計算器１０３は、５個のメッセージを遅延させるFIFOを持っており、列の重みが５未満の列のメッセージを計算するときには、FIFOにおける遅延量が、その列の重みの値に減らされる。
【００５１】
再び、図９に戻り、復号装置には、検査行列の重みにしたがって、図示しない制御信号が与えられる。そして、図９の復号装置によれば、枝用メモリ１００および１０２、並びにチェックノード計算器１０１およびバリアブルノード計算器１０３のFIFOの容量さえ足りれば、制御信号のみを変えることで様々な符号を復号することができる。
【００５２】
なお、図示しないが、図９の復号装置において、復号の最終段においては、式（１）のバリアブルノード演算の代わりに、式（５）の演算が行われ、その演算結果が、最終的な復号結果として出力される。
【００５３】
図９の復号装置を繰り返し用いて、LDPC符号を復号する場合には、チェックノード演算とバリアブルノード演算とが交互に行われるため、２６９の枝を有する図８の検査行列を用いた１回の復号に、269×2=538クロック(clock)を必要とする。従って、例えば、５０回の繰り返し復号を行うためには、符号長である９０個の符号情報（受信値）を受信する間に、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を、枝用メモリ２０２に供給する。
【００６２】
ここで、図１３は、チェックノード演算を同時に行う図１２のチェックノード計算器２０１m（ｍ＝１，２，・・・，３０）の構成例を示している。
【００６３】
図１３のチェックノード計算器２０１mでは、図１０のチェックノード計算器１０１と同様にして、式（７）のチェックノード演算が行われるが、そのチェックノード演算が、すべての枝について同時に行われる。
【００６４】
即ち、図１３のチェックノード計算器２０１mでは、枝入れ替え装置２００から供給される図８の検査行列の各列に対応するバリアブルノードからのメッセージが全て同時に読み込まれ、式（７）におけるφ(|vi|)の演算がLUTによって行われる。さらに、検査行列の１行に亘る各列に対応するバリアブルノードからのメッセージviから求められたφ(|vi|)が積算され、これにより、全ての枝からのメッセージviから求められたφ(|vi|)の積算値が求められる。その後、その積算値から、メッセージujを求めたい枝から求められたφ(|vi|)が減算され、これにより、メッセージujを求めたい枝について、式（７）におけるΣφ(|vi|)が求められる。即ち、チェックノードへの枝すべてからのメッセージの和から、メッセージujを求めたい枝からのメッセージを減算することで、メッセージujを求めたい枝へのメッセージが求められる。さらに、LUTによって、式（７）におけるφ-1(Σφ(|vi|))の演算が行われる。同時に、メッセージujの符号ビット、即ち、式（７）におけるΠsign(vi)も、EXOR回路を用いて同様に計算される。以上のようにして、式（７）の演算が行われ、メッセージujが求められる。
【００６５】
なお、図１３では、各メッセージが符号ビットを合わせて合計６ビットに量子化されているものとして、チェックノード計算器２０１mを表している。また、図１３の回路は一つのチェックノードに相当する。ここで処理の対象としている図８の検査行列については、その行数である３０行のチェックノードが存在するから、図１２の復号装置は、図１３に示したようなチェックノード計算器２０１mを３０個有している。
【００６６】
ここで、図１３のチェックノード計算器２０１mでは、９個のメッセージを同時に計算することができる。そして、ここで処理の対象としている図８の検査行列の行の重みは、第１行が８で、第２乃至第３０行が９であるため、即ち、チェックノードに供給されるメッセージの数が、８のケースが１つと、９のケースが２９あるため、チェックノード計算器２０１1は、図１３の回路と同様の８つのメッセージを同時に計算することができる回路構成となっており、チェックノード計算器２０１2乃至２０１30は、図１３の回路と同一構成となっている。
【００６７】
図１２に戻り、枝用メモリ２０２は、前段のチェックノード計算器２０１1乃至２０１30から供給される出力メッセージD2021乃至D20230を全て同時に格納し、次の時刻に、そのすべてのメッセージD2021乃至D20230を、出力メッセージD2031乃至D20330として、次段の枝入れ替え装置２０３に供給する。
【００６８】
枝入れ替え装置２０３は、枝用メモリ２０２から供給されたメッセージD2031乃至D20330の順番を図８の検査行列に従って並び替え、バリアブルノード計算器２０４1乃至２０４90に、それぞれ必要なメッセージD2041乃至D20490を供給する。
【００６９】
バリアブルノード計算器２０４1乃至２０４90は、枝入れ替え装置２０３から供給されるメッセージD2041乃至D20490と、受信用メモリ２０５から供給される受信データ（受信値）D2051乃至D20590を用いて式（１）に従って演算を行い、その演算の結果得られるメッセージD2061乃至D20690を、次段の枝用メモリ２０６に供給する。
【００７０】
ここで、図１４は、バリアブルノード演算を同時に行う図１２のバリアブルノード計算器２０４p（ｐ＝１，２，・・・，９０）の構成例を示している。
【００７１】
図１４のバリアブルノード計算器２０４pでは、図１１のバリアブルノード計算器１０３と同様にして、式（７）のチェックノード演算が行われるが、そのチェックノード演算が、すべての枝について同時に行われる。
【００７２】
即ち、図１４のバリアブルノード計算器２０４pでは、枝入れ替え装置２０３から供給される、検査行列の各行に対応するチェックノードからのメッセージujが全て同時に読み込まれ、検査行列の１列に亘る各行に対応するチェックノードからのメッセージが積算されて、その積算値が求められる。その後、その積算値から、メッセージviを求めたい枝から供給されたメッセージが減算され、その結果得られる減算値から、受信値u0iを加算することで、式（１）の演算が行われ、これにより、メッセージviが求められる。即ち、バリアブルノードへの枝すべてからのメッセージの和から、メッセージviを求めたい枝からのメッセージを減算することで、メッセージviを求めたい枝へのメッセージが求められる。
【００７３】
なお、図１４では、各メッセージが符号ビットを合わせて合計６ビットに量子化されているものとして、バリアブルノード計算器２０４pを表している。また、図１４の回路は一つのバリアブルノードに相当する。ここで処理の対象としている図８の検査行列については、その列数である９０列のバリアブルノードが存在するから、図１２の復号装置は、図１４に示したようなバリアブルノード計算器２０４pを９０個有している。
【００７４】
ここで、図１４のバリアブルノード計算器２０４pでは、５個のメッセージを同時に計算することができる。そして、ここで処理の対象としている図８の検査行列は、重みが５，３，２，１の列が、それぞれ、１５列、４５列、２９列、１列あるので、バリアブルノード計算器２０４1乃至２０４90のうちの１５個は、図１４の回路と同一構成となっており、残りの４５，２９，１個は、図１４の回路と同様の３，２，１つのメッセージを同時にそれぞれ計算することができる回路構成となっている。
【００７５】
なお、図示しないが、図１２の復号装置においても、図９における場合と同様に、復号の最終段においては、式（１）のバリアブルノード演算の代わりに、式（５）の演算が行われ、その演算結果が復号結果として出力される。
【００７６】
図１２の復号装置によれば、２６９個ある枝に対応するメッセージすべてを１クロックで同時に計算することができる。
【００７７】
図１２の復号装置を繰り返し用いて復号する場合には、チェックノード演算とバリアブルノード演算とを交互に行い、１回の復号を２クロックで行うことができる。従って、例えば、５０回の復号を行うためには、９０個の符号情報を受信する間に  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
【００８３】
【発明が解決しようとする課題】
図１５は、符号長90、符号化率2/3のLDPC符号の検査行列の一例である。この検査行列で表されるLDPC符号の復号装置を実装することを考える場合、枝に対応するメッセージを一つずつ計算する復号装置、もしくは枝に対応するメッセージを全て同時に計算する復号装置の設計自体は難しいことではない。
【００８４】
しかしながら、その復号装置の実現は、回路規模や動作速度の面から見て、容易ではない。
【００８５】
また、図１５の検査行列で表される符号を、ある数P個の枝を同時に計算する復号装置を用いて復号する場合、枝データ（枝に対応するメッセージ）を格納するメモリにおいては、各行または各列毎に異なる位置（アドレス）からの読み出しまたは書き込みのアクセスが必要になるため、各行または各列毎に別々のFIFOを用いることが必要になる。更に、メッセージについては、チェックノード演算で計算された順序と、次のバリアブルノード演算で使われる順番が入れ替わることもあり、メッセージを格納するメモリを、単純にFIFOで実現することも容易ではない。
【００８６】
本発明は、このような状況に鑑みてなされたものであり、ロジック、メモリ共に回路規模を抑制しつつ、動作周波数も十分実現可能な範囲に抑え、メモリアクセスの制御も容易に行うことができるようにするものである。
【００８７】
【課題を解決するための手段】
本発明の復号方法は、元の検査行列に対して、行置換と列置換のうちの一方または両方を行って得られる変換検査行列を用いて、LDPC符号を復号する復号ステップを備えることを特徴とする。
【００８８】
本発明の復号装置は、元の検査行列に対して、行置換と列置換のうちの一方または両方を行って得られる変換検査行列を用いて、LDPC符号を復号する復号手段を備えることを特徴とする。
【００８９】
本発明のプログラムは、元の検査行列に対して、行置換と列置換のうちの一方または両方を行って得られる変換検査行列を用いて、LDPC符号を復号する復号ステップを備えることを特徴とする。
【００９０】
本発明においては、元の検査行列に対して、行置換と列置換のうちの一方または両方を行って得られる変換検査行列を用いて、LDPC符号が復号される。
【００９１】
【発明の実施の形態】
以下に本発明の実施の形態を説明するが、請求項に記載の構成要件と、発明の実施の形態における具体例との対応関係を例示すると、次のようになる。この記載は、請求項に記載されている発明をサポートする具体例が、発明の実施の形態に記載されていることを確認するためのものである。従って、発明の実施の形態中には記載されているが、構成要件に対応するものとして、ここには記載されていない具体例があったとしても、そのことは、その具体例が、その構成要件に対応するものではないことを意味するものではない。逆に、具体例が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その具体例が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。
【００９２】
さらに、この記載は、発明の実施の形態に記載されている具体例に対応する発明が、請求項に全て記載されていることを意味するものではない。換言すれば、この記載は、発明の実施の形態に記載されている具体例に対応する発明であって、この出願の請求項には記載されていない発明の存在、すなわち、将来、分割出願されたり、補正により追加される発明の存在を否定するものではない。
【００９３】
請求項４に記載の復号装置は、
LDPC(Low Density Parity Check)符号の復号装置であって、
元の検査行列に対して、行置換と列置換のうちの一方または両方を行って得られる変換検査行列を用いて、前記LDPC符号を復号する復号手段（例えば、図１８の枝データ格納メモリ３００および３０４、チェックノード計算部３０２、サイクリックシフト回路３０３および３０８、バリアブルノード計算部３０７、並びに復号語計算部３０９）を備えることを特徴とする。
【００９４】
請求項６に記載の復号装置は、
前記復号手段は、
前記LDPC符号の復号のためのP個のチェックノードの演算を同時に行うチェックノード計算手段（例えば、図１８のチェックノード計算部３０２）と、
前記LDPC符号の復号のためのP個のバリアブルノードの演算を同時に行うバリアブルノード計算手段（例えば、図１８のバリアブルノード計算部３０７）と
を有する
ことを特徴とする。
【００９５】
請求項７に記載の復号装置は、
前記チェックノード計算手段は、チェックノードの演算を行うP個のチェックノード計算器（例えば、図１８のチェックノード計算器３０２1乃至３０２5）を有し、
前記バリアブルノード計算手段は、バリアブルノードの演算を行うP個のバリアブルノード計算器（例えば、図１８のバリアブルノード計算器３０７1乃至３０７5）を有する
ことを特徴とする。
【００９６】
請求項８に記載の復号装置は、
前記復号手段は、前記P個のチェックノードの演算、または前記P個のバリアブルノードの演算の結果得られるP個の枝に対応するメッセージデータを同時に読み書きするメッセージ記憶手段（例えば、図１８の枝データ格納メモリ３００または３０４）をさらに有する
ことを特徴とする。
【００９７】
請求項１４に記載の復号装置は、
前記復号手段は、受信情報を格納するとともに、P個の前記受信情報を同時に読み出す受信情報記憶手段（例えば、図１８の受信データ用メモリ３０６）をさらに有する
ことを特徴とする。
【００９８】
請求項１６に記載の復号装置は、
前記復号手段は、前記P個のチェックノードの演算、または前記P個のバリアブルノードの演算の結果得られるメッセージをサイクリックシフトするサイクリックシフト手段（例えば、図１８のサイクリックシフト回路３０３または３０８）をさらに有する
ことを特徴とする。
【００９９】
請求項１８に記載の復号装置は、
受信した前記LDPC符号の符号系列に対して、前記元の検査行列に対して行われた列置換と同一の列置換を行い、置換符号系列を出力する符号系列置換手段（例えば、図１８の受信データ並べ替え部３１０）をさらに備え、
前記復号手段は、前記変換検査行列と、前記置換符号系列とを用いて、前記符号系列を復号する
ことを特徴とする。
【０１００】
請求項１９に記載の復号装置は、
前記復号手段の出力に対して、前記元の検査行列に対して行われた列置換の逆置換を行い、最終的な復号結果を出力する逆置換手段（例えば、図１８の復号データ並べ替え部３１１）をさらに備える
ことを特徴とする。
【０１０１】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。
【０１０２】
図１６は、図１５の検査行列に、式（８）の行置換と、式（９）の列置換を施して得られる検査行列を示している。
【０１０３】
行置換:6x+y+1行目→5y+x+1行目・・・（８）
【０１０４】
列置換:6s+t+61列目→5t+s+61列目・・・（９）
【０１０５】
但し、式（８）および（９）において、x，y，s，tは、それぞれ、０≦x＜５，０≦y＜６，０≦s＜５，０≦y＜６の範囲の整数である。
【０１０６】
式（８）の行置換によれば、６で割って余りが１になる１，７，１３，１９，２５行目を、それぞれ、１，２，３，４，５行目に、６で割って余りが２になる２，８，１４，２０，２６行目を、それぞれ、６，７，８，９，１０行目に、という具合に置換が行われる。
【０１０７】
また、式（９）の列置換によれば、６１列目以降に対して、６で割って余りが１になる６１，６７，７３，７９，８５列目を、それぞれ、６１，６２，６３，６４，６５列目に、６で割って余りが２になる６２，６８，７４，８０，８６列目を、それぞれ、６６，６７，６８，６９，７０列目に、という具合に置換が行われる。
【０１０８】
このようにして、図１５の検査行列に対して、行と列の置換を行って得られた行列(matrix)が、図１６の検査行列である。
【０１０９】
図１６の検査行列（以下、適宜、置換検査行列という）に対して、図１５の検査行列（以下、適宜、元の検査行列という）で表わされる符号（誤りのない元の符号）の符号語の系列に、式（９）と同一の置換を行ったものを乗じると、０ベクトルが出力されることは自明である。即ち、元の検査行列を行列Ｈで、置換検査行列を行列Ｈ’で、元の符号の符号語の系列を行ベクトルｃで、行ベクトルｃに式（９）の列置換を施して得られる行ベクトルをｃ’で、それぞれ表すこととすると、検査行列の性質から、ＨｃT（上付のＴは転置を表す）は、０ベクトルとなるから、Ｈ’ｃ’Tも、当然、０ベクトルとなる。
【０１１０】
そして、以上のことから、図１６の変換検査行列は、元の符号の符号語の系列ｃに、式（９）の列置換を行ったものを符号語とする符号ｃ’の検査行列になっている。
【０１１１】
従って、元の符号によって符号化されたデータを受信して復号する際に、受信した符号系列に、式（９）の列置換を行い、その列置換後の符号系列を、図１６の変換検査行列に基づく復号装置を用いて復号し、復号結果の系列に、式（２）の列置換の逆置換を行っても、元の符号の復号装置を用いた場合と復号結果に違いはないため、性能の劣化を招くことはないことになる。即ち、図１５の元の検査行列に基づく復号装置は、図１６の変換検査行列に基づく復号装置を用いて実現することができる。
【０１１２】
次に、図１７は、５×５の行列の単位に間隔を空けた、図１６の変換検査行列を示している。
【０１１３】
図１７においては、検査行列（変換検査行列）は、５×５の単位行列、その単位行列の１のうち１個以上が０になった行列（以下、適宜、準単位行列という）、単位行列または準単位行列をサイクリックシフト(cyclic shift)した行列（以下、適宜、シフト行列という）、単位行列、準単位行列、またはシフト行列のうちの２以上の和（以下、適宜、和行列という）、５×５の０行列の組合わせで表わされている。
【０１１４】
図１７の検査行列は、５×５の単位行列、準単位行列、シフト行列、和行列、０行列で構成されているということができる。そこで、検査行列を構成する、これらの５×５の行列を、以下、適宜、構成行列という。
【０１１５】
以上のようなP×Pの構成行列で表される検査行列で表される符号の復号には、チェックノードとバリアブルノードの計算を、P個同時に行うアーキテクチャ(architecture)を用いることができる。
【０１１６】
図１８は、そのような復号装置の一実施の形態の構成例を示すブロック図である。即ち、図１８は、図１５の元の検査行列に対して、行または列置換を行って得られる図１７の変換検査行列を用いて、LDPC符号の復号を行う復号装置の構成例を示している。
【０１１７】
この復号装置は、６つのFIFO３００1乃至３００6からなる枝データ格納用メモリ３００、FIFO３００1乃至３００6を選択するセレクタ３０１、チェックノード計算部３０２、２つのサイクリックシフト回路３０３および３０８、１８個のFIFO３０４1乃至３０４18からなる枝データ格納用メモリ３０４、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)）に１がないため、データは格納されない。
【０１３０】
以下、図１８の復号装置の各部の動作について詳細に説明する。
【０１３１】
枝データ格納用メモリ３００は、６つのFIFO３００1乃至３００6からなり、前段のサイクリックシフト回路３０８から供給される５つのメッセージデータD311が、検査行列どの行に属するかの情報（Matrixデータ）D312に従って、データを格納するFIFOを、FIFO３００1乃至３００6の中から選び、選んだFIFOに５つのメッセージデータD311をまとめて順番に格納していく。また、枝データ格納用メモリ３００は、データを読み出す際には、FIFO３００1から５つのメッセージデータD3001を順番に読み出し、次段のセレクタ３０１に供給する。枝データ格納用メモリ３００は、FIFO３００1からのメッセージデータの読み出しの終了後、FIFO３００2乃至３００6からも、順番に、メッセージデータを読み出し、セレクタ３０１に供給する。
【０１３２】
セレクタ３０１は、セレクト信号D301に従って、FIFO３００1乃至３００6のうちの、現在データが読み出されているFIFOからの５つのメッセージデータを選択し、メッセージデータD302として、チェックノード計算部３０２に供給する。
【０１３３】
チェックノード計算部３０２は、５つのチェックノード計算器３０２1乃至３０２5からなり、セレクタ３０１を通して供給されるメッセージD302(D3021乃至D3025)を用いて、式（７）に従って演算を行い、その演算の結果得られる５つのメッセージD303(D3031乃至D3035)をサイクリックシフト回路３０３に供給する。
【０１３４】
ここで、チェックノード計算器３０２1乃至３０２5それぞれは、図１０に示したチェックノード計算器１０１と同様に構成される。
【０１３５】
サイクリックシフト回路３０３は、チェックノード計算部３０２で計算された５つのメッセージD3031乃至D3035を、対応する枝が検査行列において元となる単位行列を幾つサイクリックシフトしたものであるかの情報（Matrixデータ）D305を元にサイクリックシフトし、その結果をメッセージD304として、枝データ格納用メモリ３０４に供給する。
【０１３６】
枝データ格納用メモリ３０４は、１８個のFIFO３０４1乃至３０４18からなり、前段のサイクリックシフト回路３０３から供給される５つのメッセージデータD304が検査行列のどの行に属するかの情報D305に従って、データを格納するFIFOを、FIFO３０４1乃至３０４18の中から選び、選んだFIFOに５つのメッセージデータD304をまとめて順番に格納していく。また、枝データ格納用メモリ３０４は、データを読み出す際には、FIFO３０４1から５つのメッセージD3061を順番に読み出し、次段のセレクタ３０５に供給する。枝データ格納用メモリ３０４は、FIFO３０４1からのデータの読み出しの終了後、FIFO３０４2乃至３０４18からも、順番に、メッセージデータを読み出し、セレクタ３０５に供給する。
【０１３７】
セレクタ３０５は、セレクト信号D307に従って、FIFO３０４1乃至３０４18のうちの、現在データが読み出されているFIFOからの５つのメッセージデータを選択し、メッセージデータD308として、バリアブルノード計算部３０７と復号語計算部３０９に供給する。
【０１３８】
一方、受信データ並べ替え部３１０は、通信路を通して受信したLDPC符号の符号系列（受信データ）D313を、式（９）の列置換を行うことにより並べ替え、符号系列D314として、受信用データメモリ３０６に供給する。受信データ用メモリ３０６は、受信データ並べ替え部３１０から供給される符号系列D314から、受信LLR（対数尤度比）を計算しており、その計算した受信LLRを５つまとめてデータD309として、バリアブルノード計算部３０７と復号語計算部３０９に供給する。
【０１３９】
バリアブルノード計算部３０７は、５つのバリアブルノード計算器３０７1乃至３０７5からなり、セレクタ３０５を通して供給されるメッセージD308(D3081乃至D3085)と、受信データ用メモリ３０６から供給される５つの受信LLR D309を用いて、式（１）に従って演算を行い、その演算の結果得られるメッセージD310(D3101乃至D3105)を、サイクリックシフト回路３０８に供給する。
【０１４０】
ここで、バリアブルノード計算器３０７1乃至３０７5それぞれは、図１１のバリアブルノード計算器１０３と同様に構成される。
【０１４１】
サイクリックシフト回路３０８は、バリアブルノード計算部３０７で計算されたメッセージD3101乃至D3105を、対応する枝が検査行列において元となる単位行列を幾つサイクリックシフトしたものであるかの情報を元にサイクリックシフトし、その結果をメッセージD311として、枝データ格納用メモリ３００に供給する。
【０１４２】
以上の動作を１巡することで、LDPC符号の１回の復号を行うことができる。図１８の復号装置は、所定の回数だけLDPC符号を復号した後、復号語計算部３０９および復号データ並べ替え部３１１において、最終的な復号結果を求めて出力する。
【０１４３】
即ち、復号語計算部３０９は、５つの復号語計算器３０９1乃至３０９5からなり、セレクタ３０５が出力する５つのメッセージD308(D3081乃至D3085)と、受信データ用メモリ３０６から供給される５つの受信LLR D309を用い、複数回の復号の最終段において、式（５）に基づいて、復号結果（復号語）を計算して、その結果得られる復号データD315を、復号データ並べ替え部３１１に供給する。
【０１４４】
復号データ並べ替え部３１１は、復号語計算部３０９から供給される復号データD315を対象に、式（９）の列置換の逆置換を行うことにより、その順序を並べ替え、最終的な復号結果D316として出力する。
【０１４５】
なお、枝データ（枝に対応するメッセージ）が欠ている箇所に関しては、メモリ格納時（枝データ格納用メモリ３００と３０４へのデータ格納時）には、何のメッセージも格納せず、また、ノード演算時（チェックノード計算部３０２でのチェックノード演算時とバリアブルノード計算部３０７でのバリアブルノード演算時）にも何の演算も行わない。
【０１４６】
また、サイクリックシフト回路３０３および３０８には、バレルシフタを用いると回路規模を小さくしながら所望の操作を実現できる。
【０１４７】
上記説明には、枝データ格納にFIFOを用いたが（枝データ格納メモリ３００と３０４をFIFOで構成するようにしたが）、FIFOの代わりにRAMを用いても構わない。その場合、RAMには、P個の枝情報（枝に対応するメッセージ）を同時に読み出すことの出来るビット幅と、枝総数/Pのワード(word)数が必要となる。さらに、RAMへの書き込みは、検査行列の情報から、書き込もうとしているデータが次に読み出される際に何番目に読み出されるかを求め、その位置に書き込む。また、RAMからの読み出しの際には、アドレスの先頭から順次データを読み出す。FIFOの代わりにRAMを用いると、セレクタ３０１および３０５は不要になる。
【０１４８】
なお、FIFOやRAMの物理的なビット幅が足りない場合には、複数のRAMを用いて同じ制御信号を与えることで、論理的に１つのRAMとみなすことができる。
【０１４９】
また、上述の場合には、説明を簡単にするために、Pが５の場合、即ち、検査行列を構成する構成行列の行数および列数が５の場合を例に挙げたが、構成行列の行数および列数Pは必ずしも５である必要はなく、検査行列によって異なる値を取ることもあり得る。例えば、Pは３６０や３９２であってもよい。
【０１５０】
また、本実施の形態では、符号長90、符号化率2/3のLDPC符号を用いたが、LDPC符号の符号長や符号化率は、幾つであっても構わない。例えば、構成行列の行数および列数Pが5の場合、枝総数が５以下であれば、どんな符号長、符号化率のLDPC符号でも、制御信号を代えるだけで、図１８の復号装置を用いて復号可能である。
【０１５１】
さらに、構成行列の行数および列数Pが所定の値で、枝の総数がある値以下、という条件を満たすあるLDPC符号の復号装置は、その条件を満たす、任意の符号長で、任意の符号化率のLDPC符号を復号することができる。
【０１５２】
以上のように、検査行列（元の検査行列）に対して、行置換と列置換うちの一方または両方を施し、P×Pの単位行列、そのコンポーネントの１のうち１個以上が０になった準単位行列、単位行列もしくは準単位行列をサイクリックシフトしたシフト行列、単位行列、準単位行列、もしくはシフト行列の複数の和である和行列、P×Pの０行列の組合せ、つまり、構成行列の組み合わせで表わすことができる検査行列（変換検査行列）に変換することで、LDPC符号の復号を、チェックノードとバリアブルノードの演算をP個同時に行うアーキテクチャ(architecture)を採用することが可能となり、これにより、ノード演算を、P個同時に行うことで動作周波数を実現可能な範囲に抑えることができ、多数の繰り返し復号を行うことを可能にしつつ、メモリ（FIFOやRAM）への書き込みと読み出し時に、異なるアドレスへの同時アクセスが起きることを防止することができる。
【０１５３】
即ち、上述した検査行列の行置換と列置換の双方もしくは片方を行うことで、チェックノードとバリアブルノードの演算をP個同時に行うことが可能となり、さらに、このようにノード演算をP個同時に行うことで、動作周波数を実現可能な範囲に抑えることができ、多数の繰り返し復号を行うことを可能にしつつ、メモリ（FIFOやRAM）への書き込みと読み出し時に、異なるアドレスへの同時アクセスが起きることを防止することができる。
【０１５４】
さらに、図１７の検査行列（変換検査行列）で表わされるLDPC符号を復号する場合には、２６９個の枝をチェックノード、バリアブルノード毎に５個ずつ演算することが可能であることから、１回の復号に、269/5×2≒１０８クロック動作すればよいことになる。５０回の復号には、９０個の符号情報を受信する間に、108×50=5400クロック動作すればよいことになり、受信周波数の約６０倍の動作周波数でよいことになる。従って、図１８の復号装置によれば、各ノード演算を一つずつ行う図９の復号装置に比べて、1/5の動作周波数で済むことになる。また、回路規模の面から見ても、メモリの大きさは同じであるため、論理回路が多少大きくなっても全体への影響は小さいと言える。
【０１５５】
一般的に、LDPC符号は符号長が数千から数万と大きいため、Pの値も数百の大きさを持つものが使われる。その場合には、更に本発明に係る復号装置を用いる効果は大きくなる。
【０１５６】
以上のように、ロジック、メモリ共に回路規模を抑制しつつ、動作周波数も十分実現可能な範囲に抑えることができ、メモリアクセスの制御も容易に行うことができる。
【０１５７】
また、LDPC符号の性質から、検査行列に行置換や列置換を施しても符号の性能は変わらない。従って、行置換または列置換によって、構成行列の組み合わせで表すことができる変換検査行列を得られる検査行列に対応する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)やスピーカ等で構成される出力部４０６から出力、あるいは、通信部４０８から送信、さらには、ハードディスク４０５に記録等させる。
【０１６７】
ここで、本明細書において、コンピュータに各種の処理を行わせるためのプログラムを記述する処理ステップは、必ずしもフローチャートとして記載された順序に沿って時系列に処理する必要はなく、並列的あるいは個別に実行される処理（例えば、並列処理あるいはオブジェクトによる処理）も含むものである。
【０１６８】
また、プログラムは、１のコンピュータにより処理されるものであっても良いし、複数のコンピュータによって分散処理されるものであっても良い。さらに、プログラムは、遠方のコンピュータに転送されて実行されるものであっても良い。
【０１６９】
【発明の効果】
以上の如く、本発明によれば、回路規模を抑制しつつ、動作周波数も十分実現可能な範囲に抑え、メモリアクセスの制御も容易に行うことが可能となる。
【図面の簡単な説明】
【図１】  LDPC符号の検査行列Hを説明する図である。
【図２】  LDPC符号の復号手順を説明するフローチャートである。
【図３】メッセージの流れを説明する図である。
【図４】  LDPC符号の検査行列の例を示す図である。
【図５】検査行列のタナーグラフを示す図である。
【図６】バリアブルノードを示す図である。
【図７】チェックノードを示す図である。
【図８】  LDPC符号の検査行列の例を示す図である。
【図９】ノード演算を一つずつ行うLDPC符号の復号装置の構成例を示すブロック図である。
【図１０】メッセージを一つずつ計算するチェックノード計算器の構成例を示すブロック図である。
【図１１】メッセージを一つずつ計算するバリアブルノード計算器の構成例を示すブロック図である。
【図１２】ノード演算を全て同時に行うLDPC符号の復号装置の構成例を示すブロック図である。
【図１３】メッセージを同時に計算するチェックノード計算器の構成例を示すブロック図である。
【図１４】メッセージを同時に計算するバリアブルノード計算器の構成例を示すブロック図である。
【図１５】  LDPC符号の検査行列の例を示す図である。
【図１６】検査行列に行置換と列置換を施した行列を示す図である。
【図１７】５×５単位に分割した検査行列を示す図である。
【図１８】本発明を適用した復号装置の一実施の形態の構成例を示すブロック図である。
【図１９】本発明を適用したコンピュータの一実施の形態の構成例を示すブロック図である。
【符号の説明】
３００  枝データ格納用メモリ，  ３０１  セレクタ，  ３０２  チェックノード計算部，  ３０３  サイクリックシフト回路，  ３０４  枝データ格納用メモリ，  ３０５  セレクタ，  ３０６  受信データ用メモリ，  ３０７  バリアブルノード計算部，  ３０８  サイクリックシフト回路，  ３０９  復号語計算部，  ３１０  受信データ並べ替え部，  ３１１  復号データ並べ替え部，  ４０１  バス，  ４０２  CPU，  ４０３  ROM，  ４０４  RAM，  ４０５  ハードディスク，  ４０６  出力部，  ４０７  入力部，  ４０８  通信部，  ４０９  ドライブ，  ４１０  入出力インタフェース，  ４１１  リムーバブル記録媒体
【図１】
0004224777.tif 000016
【図２】
0004224777.tif 000017
【図３】
0004224777.tif 000018
【図４】
0004224777.tif 000019
【図５】
0004224777.tif 000020
【図６】
0004224777.tif 000021
【図７】
0004224777.tif 000022
【図８】
0004224777.tif 000023
【図９】
0004224777.tif 000024
【図１０】
0004224777.tif 000025
【図１１】
0004224777.tif 000026
【図１２】
0004224777.tif 000027
【図１３】
0004224777.tif 000028
【図１４】
0004224777.tif 000029
【図１５】
0004224777.tif 000030
【図１６】
0004224777.tif 000031
【図１７】
0004224777.tif 000032
【図１８】
0004224777.tif 000033
【図１９】
0004224777.tif 000034