(57)【要約】【課題】復号の性能を向上させ、さらに消費電力を削減する。【解決手段】計算部1102は、チェックノードの演算とバリアブルノードの演算の一部である第１の演算を行う。計算部４１５は、バリアブルノードの演算の他の一部である第２の演算を行う。第１と第２の演算が繰り返し行われることにより、LDPC符号の復号が行われる。また、シンドローム判定部2001は、第２の演算の結果得られる復号途中結果D2000のシンドロームを演算する。制御部2003は、シンドローム判定部2001により得られるシンドロームに基づいて、復号を終了させる。本発明は、例えば、衛星放送を受信するチューナに適用できる。【選択図】図３４
2006304131.tif 000002
【特許請求の範囲】
【請求項１】
LDPC(Low Density Parity Check)符号の復号装置であって、
前記LDPC符号の復号のためのチェックノードの演算とバリアブルノードの演算の一部である第１の演算を行う第１の演算手段と、
前記LDPC符号の復号のための前記バリアブルノードの演算の他の一部である第２の演算を行う第２の演算手段と、
前記第２の演算手段により得られる演算結果のシンドロームを演算するシンドローム演算手段と、
前記第１と第２の演算手段を制御する制御手段と
を備え、
前記第１と第２の演算手段は、前記第１と第２の演算を繰り返し行うことにより、前記LDPC符号の復号を行い、
前記制御手段は、前記シンドローム演算手段により得られるシンドロームに基づいて、前記復号を終了させる
ことを特徴とする復号装置。
【請求項２】
前記シンドローム演算手段は、前記第１の演算手段による第１の演算と同時に、前記シンドロームを演算する
ことを特徴とする請求項１に記載の復号装置。
【請求項３】
前記シンドローム演算手段は、前記LDPC符号の受信情報のシンドロームも演算し、
前記制御手段は、さらに、前記シンドローム演算手段により得られる前記受信情報のシンドロームに基づいて、前記第１と第２の演算手段に前記第１と第２の演算を行わせずに、前記受信情報を前記LDPC符号の復号結果とする
ことを特徴とする請求項１に記載の復号装置。
【請求項４】
前記受信情報を記憶する受信情報記憶手段と、
前記第２の演算手段により得られる演算結果を記憶する演算結果記憶手段と
をさらに備える
ことを特徴とする請求項３に記載の復号装置。
【請求項５】
前記制御手段は、前記シンドローム演算手段により得られる前記受信情報のシンドロームに基づいて、前記受信情報記憶手段に記憶されている前記受信情報を、前記演算結果記憶手段に記憶させる
ことを特徴とする請求項４に記載の復号装置。
【請求項６】
前記制御手段は、前記受信情報を、前記第２の演算手段を介して前記演算結果記憶手段に記憶させる
ことを特徴とする請求項５に記載の復号装置。
【請求項７】
LDPC(Low Density Parity Check)符号の復号装置の復号方法であって、
前記LDPC符号の復号のためのチェックノードの演算とバリアブルノードの演算の一部である第１の演算を行う第１の演算ステップと、
前記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で表すものとすると、そのような検査行列Hとしては、例えば、図１に示すように、各列のハミング重み（"1"の数）(weight)が"3"であり、且つ、各行のハミング重みが"6"であるもの等がある。
【０００８】
このように、各行及び各列のハミング重みが一定である検査行列Hによって定義されるLDPC符号は、レギュラーLDPC符号と称される。一方、各行及び各列のハミング重みが一定でない検査行列Hによって定義されるLDPC符号は、イレギュラーLDPC符号と称される。
【０００９】
このようなLDPC符号による符号化は、検査行列Hに基づいて生成行列Gを生成し、この生成行列Gを２元の情報メッセージに対して乗算することによって符号語を生成することで実現される。具体的には、LDPC符号による符号化を行う符号化装置は、まず、検査行列Hの転置行列HTとの間に、式GHT=0が成立する生成行列Gを算出する。ここで、生成行列Gが、k×n行列（ｋ行ｎ列の行列）である場合には、検査行列Hは、n-k行ｎ列の行列である。
【００１０】
なお、例えば、nビットの符号語cが、kビットの情報メッセージuに続けて、n-kビットのパリティビットを配置したビット列に一致する組織符号である場合に、n-k行n列の検査行列Hにおいて、nビットの符号語cのうちのkビットの情報メッセージuに対応するn-k行k列の部分を情報部というとともに、n-kビットのパリティビットに対応するn-k行n-k列の部分をパリティ部ということとすると、パリティ部が、下三角行列または上三角行列になっていれば、情報メッセージuのLDPC符号への符号化は、検査行列Hを用いて行うことができる。
【００１１】
即ち、例えば、検査行列Hが、図２に示すように、情報部と、下三角行列のパリティ部とで構成され、パリティ部の下三角の部分の要素が、すべて1であるとすると、符号語cのパリティビットの１番目のビットは、情報メッセージuのうちの、検査行列Hの情報部の第１行において1になっている要素に対応するビットのEXOR（排他的論理和）を演算した値となる。
【００１２】
また、符号語cのパリティビットの２番目のビットは、情報メッセージuのうちの、検査行列Hの情報部の第２行において1になっている要素に対応するビットと、パリティビットの１番目のビットのEXORを演算した値となる。
【００１３】
さらに、符号語cのパリティビットの３番目のビットは、情報メッセージuのうちの、検査行列Hの情報部の第３行において1になっている要素に対応するビットと、パリティビットの１番目および２番目のビットのEXORを演算した値となる。
【００１４】
以下、同様にして、符号語cのパリティビットのi番目のビットは、情報メッセージuのうちの、検査行列Hの情報部の第i行において1になっている要素に対応するビットと、パリティビットの１乃至i-1番目のビットのEXORを演算した値となる。
【００１５】
以上のようにして、n-kビットのパリティビットを求め、kビットの情報メッセージuに続けて配置することにより、nビットの符号語cを得ることができる。
【００１６】
一方、LDPC符号の復号は、Gallagerが確率復号(Probabilistic Decoding)と称して提案したアルゴリズムであって、バリアブルノード(variable node（メッセージノード(message node)とも呼ばれる。）)と、チェックノード(check node)とからなる、いわゆるタナーグラフ(Tanner graph)上での確率伝播(belief propagation)によるメッセージ・パッシング・アルゴリズムによって行うことが可能である。ここで、以下、適宜、バリアブルノードとチェックノードを、単に、ノードともいう。
【００１７】
しかしながら、確率復号においては、各ノード間で受け渡されるメッセージが実数値であることから、解析的に解くためには、連続した値をとるメッセージの確率分布そのものを追跡する必要があり、非常に困難を伴う解析を必要とすることになる。そこで、Gallagerは、LDPC符号の復号アルゴリズムとして、アルゴリズムＡ又はアルゴリズムＢを提案している。
【００１８】
LDPC符号の復号は、一般的には、図３に示すような手順にしたがって行われる。なお、ここでは、受信値をU0(u0i)とし、チェックノードから出力されるメッセージをujとし、バリアブルノードから出力されるメッセージをviとする。また、ここでは、メッセージとは、値の"0"らしさを、いわゆる対数尤度比(log likelihood ratio)で表現した実数値である。さらに、受信値U0の"0"らしさの対数尤度比を、受信データu0iと表すこととする。
【００１９】
まず、LDPC符号の復号においては、図３に示すように、ステップＳ１１において、受信値U0(u0i)が受信され、メッセージujが"0"に初期化されるとともに、繰り返し処理のカウンタとしての整数をとる変数kが"0"に初期化され、ステップＳ１２に進む。ステップＳ１２において、受信値U0(u0i)に基づいて、式（１）に示す演算を行うことによってメッセージviが求められ、さらに、このメッセージviに基づいて、式（２）に示す演算を行うことによってメッセージujが求められる。
【００２０】
【数１】
2006304131.tif 000003
・・・（１）
【００２１】
【数２】
2006304131.tif 000004
・・・（２）
【００２２】
ここで、式（１）と式（２）におけるdvとdcは、それぞれ、検査行列Hの縦方向（行方向）と横方向（列方向）の"1"の個数を示す任意に選択可能とされるパラメータであり、例えば、(3,6)符号の場合には、dv=3，dc=6となる。
【００２３】
なお、式（１）または（２）の演算においては、それぞれ、メッセージを出力しようとする枝(edge)から入力されたメッセージを、和または積演算のパラメータとしては用いないことから、和または積演算の範囲が、１乃至dv-1または１乃至dc-1となっている。また、式（２）に示す演算は、実際には、２入力v1，v2に対する１出力で定義される式（３）に示す関数R(v1,v2)のテーブルを予め作成しておき、これを式（４）に示すように連続的（再帰的）に用いることによって行われる。
【００２４】
【数３】
2006304131.tif 000005
・・・（３）
【００２５】
【数４】
2006304131.tif 000006
・・・（４）
【００２６】
ステップＳ１２では、さらに、変数kが"1"だけインクリメントされ、ステップＳ１３に進む。ステップＳ１３では、変数kが所定の繰り返し復号回数N以上であるか否かが判定される。ステップＳ１３において、変数kがN以上ではないと判定された場合、ステップＳ１２に戻り、以下、同様の処理が繰り返される。
【００２７】
また、ステップＳ１３において、変数kがN以上であると判定された場合、ステップＳ１４に進み、式（５）に示す演算を行うことによって最終的に出力する復号結果としてのメッセージvが求められて出力され、LDPC符号の復号処理が終了する。
【００２８】
【数５】
2006304131.tif 000007
・・・（５）
【００２９】
ここで、式（５）の演算は、式（１）の演算とは異なり、バリアブルノードに接続している全ての枝からの入力メッセージを用いて行われる。
【００３０】
このようなLDPC符号の復号は、例えば(3,6)符号の場合には、図４に示すように、各ノード間でメッセージの授受が行われる。なお、図４における"="で示すノード（バリアブルノード）では、式（１）に示した演算が行われ、"+"で示すノード（チェックノード）では、式（２）に示した演算が行われる。特に、アルゴリズムＡにおいては、メッセージを２元化し、"+"で示すノードにて、dc-1個の入力メッセージの排他的論理和演算を行い、"="で示すノードにて、受信値Rに対して、dv-1個の入力メッセージが全て異なるビット値であった場合には、符号を反転して出力する。
【００３１】
また、一方で、近年、LDPC符号の復号の実装法に関する研究も行われている。実装方法について述べる前に、まず、LDPC符号の復号を摸式化して説明する。
【００３２】
図５は、(3,6)LDPC符号（符号化率1/2、符号長12）の検査行列H(parity check matrix)の例である。LDPC符号の検査行列Hは、図６のように、タナーグラフを用いて書き表すことができる。ここで、図６において、"+"で表されるのが、チェックノードであり、"="で表されるのが、バリアブルノードである。チェックノードとバリアブルノードは、それぞれ、検査行列Hの行と列に対応する。チェックノードとバリアブルノードとの間の結線は、枝(edge)であり、検査行列Hの"1"に相当する。即ち、検査行列Hの第ｊ行第ｉ列のコンポーネントが１である場合には、図６において、上からｉ番目のバリアブルノード（"="のノード）と、上からｊ番目のチェックノード（"+"のノード）とが、枝により接続される。枝は、バリアブルノードに対応する符号ビットが、チェックノードに対応する拘束条件を持つことを表す。なお、図６は、図５の検査行列Hのタナーグラフとなっている。
【００３３】
LDPC符号の復号方法であるサムプロダクトアルゴリズム(Sum Product Algorithm)は、バリアブルノードの演算とチェックノードの演算とを繰り返し行う。
【００３４】
バリアブルノードでは、図７のように、式（１）の演算を行う。すなわち、図７において、計算しようとしている枝に対応するメッセージviは、バリアブルノードに繋がっている残りの枝からのメッセージu1およびu2と、受信情報u0iを用いて計算される。他の枝に対応するメッセージも同様に計算される。
【００３５】
チェックノードの演算について説明する前に、式（２）を、式a×b=exp{ln(|a|)+ln(|b|)}×sign(a)×sign(b)の関係を用いて、式（６）のように書き直す。但し、sign(x)は、x≧0のとき1であり、x＜0のとき-1である。
【００３６】
【数６】
2006304131.tif 000008
・・・（６）
【００３７】
更に、x≧0において、φ(x)=ln(tanh(x/2))と定義すると、φ-1(x)=2tanh-1(e-x)であるから、式（６）は、式（７）のように書くことができる。
【００３８】
【数７】
2006304131.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)の実装法について説明する。
【００４３】
なお、ここでは、例えば、図９の、３６（行）×１０８（列）の検査行列Hで表現される符号（符号化率2/3、符号長108）を復号することとする。図９の検査行列Hの１の数は３２３であり、従って、そのタナーグラフでは、枝の数は３２３個となる。ここで、図９の検査行列Hでは、０を、"."で表現している。
【００４４】
図１０は、LDPC符号の１回復号を行う復号装置の構成例を示している。
【００４５】
図１０の復号装置では、その動作する１クロック(clock)ごとに、１つの枝に対応するメッセージが計算される。
【００４６】
即ち、図１０の復号装置は、２つの枝用メモリ１００および１０２、１つのチェックノード計算器１０１、１つのバリアブルノード計算器１０３、１つの受信用メモリ１０４、１つの制御部１０５からなる。
【００４７】
図１０の復号装置では、枝用メモリ１００または１０２からメッセージデータが１つずつ読み出され、そのメッセージデータを用いて、所望の枝に対応するメッセージデータが計算される。そして、その計算によって求められたメッセージデータが１つずつ後段の枝用メモリ１０２または１００に格納されていく。繰り返し復号を行う際には、この１回復号を行う図１０の復号装置を複数個縦列に連接するか、もしくは図１０の復号装置を繰り返し用いることによって、繰り返し復号を実現する。なお、ここでは、例えば、図１０の復号装置が複数個接続されているものとする。
【００４８】
枝用メモリ１００は、前段の復号装置（図示せず）のバリアブルノード計算器１０３から供給されるメッセージD100を、後段のチェックノード計算器１０１が読み出す順番に格納していく。そして、枝用メモリ１００は、チェックノード計算のフェーズでは、メッセージD100を、格納してある順番通りに、メッセージD101として、チェックノード計算器１０１に供給する。
【００４９】
チェックノード計算器１０１は、制御部１０５から供給される制御信号D106に基づき、枝用メモリ１００から供給されるメッセージD101を用いて、式（７）に従って演算を行い、その演算によって求められたメッセージD102を、後段の枝用メモリ１０２に供給する。
【００５０】
枝用メモリ１０２は、前段のチェックノード計算器１０１から供給されるメッセージD102を、後段のバリアブルノード計算器１０３が読み出す順番に格納していく。そして、枝用メモリ１０２は、バリアブルノード計算のフェーズでは、メッセージD102を、格納してある順番通りに、メッセージD103として、バリアブルノード計算器１０３に供給する。
【００５１】
さらに、バリアブルノード計算器１０３には、制御部１０５から制御信号D107が供給されるとともに、受信用メモリ１０４から受信データD104が供給される。バリアブルノード計算器１０３は、制御信号D107に基づき、枝用メモリ１００から供給されるメッセージD103と受信用メモリ１００から供給される受信データD104を用い、式（１）に従って演算を行い、その演算の結果得られるメッセージD105を、図示せぬ後段の復号装置の枝用メモリ１００に供給する。
【００５２】
受信用メモリ１０４には、LDPC符号化された受信データ（LDPC符号）が格納される。制御部１０５は、バリアブルノード演算を制御する制御信号D106と、チェックノード演算を制御する制御信号D107を、それぞれチェックノード計算器１０１とバリアブルノード計算器１０３に供給する。制御部１０５は、枝用メモリ１００に全ての枝のメッセージが格納されたとき、チェックノード計算器１０１に制御信号D106を供給し、枝用メモリ１０２に全ての枝のメッセーが格納されたとき、バリアブルノード計算器１０３に制御信号D107を供給する。
【００５３】
図１１は、チェックノード演算を１つずつ行う図１０のチェックノード計算器１０１の構成例を示している。
【００５４】
なお、図１１では、各メッセージが符号ビットを合わせて合計６ビット(bit)に量子化されているものとして、チェックノード計算器１０１を表している。また、図１１では、図９の検査行列Hで表されるLDPC符号のチェックノード演算が行われる。さらに、図１１のチェックノード演算器１０１には、クロックｃｋが供給され、このクロックｃｋは、必要なブロックに供給されるようになっている。そして、各ブロックは、クロックｃｋに同期して処理を行う。
【００５５】
図１１のチェックノード計算器１０１は、制御部１０５から供給される、例えば、1ビットの制御信号D106に基づき、枝用メモリ１００から１つずつ読み込まれるメッセージD101を用いて、式（７）にしたがって演算を行う。
【００５６】
即ち、チェックノード計算器１０１では、検査行列Hの各列に対応するバリアブルノードからの６ビットのメッセージ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を積算し、その結果得られる９ビットの積算値をレジスタ１２３に再格納する。なお、検査行列Hの1行に亘る全ての枝からのメッセージD101の絶対値D122(|vi|)に対する演算結果が積算された場合、レジスタ１２３はリセットされる。
【００５９】
検査行列Hの1行に亘るメッセージD101が１つずつ読み込まれ、レジスタ１２３に1行分の演算結果D123が積算された積算値が格納された場合、制御部１０５から供給される制御信号D106は、０から１に変化する。例えば、行の重み（row weight）が「９」である場合、制御信号D106は、１から８クロック目までは、「０」となり、９クロック目では「１」となる。
【００６０】
制御信号D106が「１」の場合、セレクタ１２４は、レジスタ１２３に格納されている値、即ち、検査行列Hの１行に亘る全ての枝からのメッセージD101（メッセージvi）から求められたφ(|vi|)が積算された９ビットの値D124（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）を選択し、値D125として、レジスタ１２５に出力して格納させる。レジスタ１２５は、格納している値D125を、９ビットの値D126として、セレクタ１２４と加算器１２６に供給する。制御信号D106が「０」の場合、セレクタ１２４は、レジスタ１２５から供給された値D126を選択し、レジスタ１２５に出力して再格納させる。即ち、検査行列Hの１行に亘る全ての枝からのメッセージD101（メッセージvi）から求められたφ(|vi|)が積算されるまで、レジスタ１２５は、前回積算されたφ(|vi|)を、セレクタ１２４と加算器１２６に供給する。
【００６１】
一方、FIFOメモリ１２７は、レジスタ１２５から新たな値D126（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）が出力されるまでの間、LUT１２１が出力した演算結果D123（φ(|vi|)）を遅延し、５ビットの値D127として減算器１２６に供給する。減算器１２６は、レジスタ１２５から供給された値D126から、FIFOメモリ１２７から供給された値D127を減算し、その減算結果を、５ビットの減算値D128としてLUT１２８に供給する。即ち、減算器１２６は、検査行列Hの1行に亘る全ての枝からのメッセージD101（メッセージvi）から求められたφ(|vi|)の積算値から、求めたい枝からのメッセージD101（メッセージvi）から求められたφ(|vi|)を減算して、その減算値（ｉ＝１からｉ＝ｄc−１までのΣφ(|vi|)）を減算値D128としてLUT１２８に供給する。
【００６２】
なお、減算器１２６は、レジスタ１２５から供給される９ビットの値D126から、FIFOメモリ１２７から供給される５ビットの値D127を減算するから、その減算結果は、最大で９ビットとなり得るのに対して、５ビットの減算値D128を出力する。このため、レジスタ１２５から供給される９ビットの値D126から、FIFOメモリ１２７から供給される５ビットの値D127を減算した減算結果が、５ビットで表せない場合、つまり、減算結果が、５ビットで表すことができる最大値（３１（２進数では１１１１１））を越える場合には、減算器１２６は、減算結果を、５ビットで表すことができる最大値にクリッピングし、５ビットの減算値D128を出力する。
【００６３】
LUT１２８は、減算値D128（ｉ＝１からｉ＝ｄc−１までのΣφ(|vi|)）に対して、式（７）におけるφ-1（Σφ(|vi|)）の演算を行った５ビットの演算結果D129（φ-1(Σφ(|vi|)))を出力する。
【００６４】
以上の処理と並行して、EXOR回路１２９は、レジスタ１３０に格納されている１ビットの値D131と符号ビットD121との排他的論理和を演算することにより、符号ビットどうしの乗算を行い、１ビットの乗算結果D130をレジスタ１３０に再格納する。なお、検査行列Hの1行に亘る全ての枝からのメッセージD101の符号ビットD121が乗算された場合、レジスタ１３０はリセットされる。
【００６５】
検査行列Hの1行に亘る全ての枝からのメッセージD101の符号ビットD121が乗算された乗算結果D130（ｉ＝１からｄcまでのΠsign(vi)）がレジスタ１３０に格納された場合、制御部１０５から供給される制御信号D106は、「０」から「１」に変化する。
【００６６】
制御信号D106が「１」の場合、セレクタ１３１は、レジスタ１３０に格納されている値、即ち、検査行列Hの１行に亘る全ての枝からのメッセージD101の符号ビットD121が乗算された値D131（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）を選択し、１ビットの値D132としてレジスタ１３２に出力して格納させる。レジスタ１３２は、格納している値D132を、１ビットの値D133としてセレクタ１３１とEXOR回路１３４に供給する。制御信号D106が「０」の場合、セレクタ１３１は、レジスタ１３２から供給された値D133を選択し、レジスタ１３２に出力して再格納させる。即ち、検査行列Hの１行に亘る全ての枝からのメッセージD101（メッセージvi）の符号ビットD121が乗算されるまで、レジスタ１３２は、前回格納した値を、セレクタ１３１とEXOR回路１３４に供給する。
【００６７】
一方、FIFOメモリ１３３は、レジスタ１３２から新たな値D133（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）がEXOR回路１３４に供給されるまでの間、符号ビットD121を遅延し、１ビットの値D134としてEXOR回路１３４に供給する。EXOR回路１３４は、レジスタ１３２から供給された値D133と、FIFOメモリ１３３から供給された値D134との排他的論理和を演算することにより、値D133を、値D134で除算し、１ビットの除算結果を除算値D135として出力する。即ち、EXOR回路１３４は、検査行列Hの１行に亘る全ての枝からのメッセージD101の符号ビットD121（sign(|vi|)）の乗算値を、求めたい枝からのメッセージD101の符号ビットD121（sign(|vi|)）で除算して、その除算値（ｉ＝１からｉ＝ｄc−１までのΠsign(|vi|)）を除算値D135として出力する。
【００６８】
チェックノード計算器１０１では、LUT１２８から出力された５ビットの演算結果D129を下位５ビットとするとともに、EXOR回路１３４から出力された１ビットの除算値D135を最上位ビットとする合計６ビットがメッセージD102（メッセージuj）として出力される。
【００６９】
以上のように、チェックノード計算器１０１では、式（７）の演算が行われ、メッセージujが求められる。
【００７０】
なお、図９の検査行列Hの行の重みの最大は９であるため、即ち、チェックノードに供給されるメッセージの最大数は９であるため、チェックノード計算器１０１は、９個のメッセージ（φ(|vi|)）を遅延させるFIFOメモリ１２７とFIFOメモリ１３３を有している。行の重みが９未満の行のメッセージを計算するときには、FIFOメモリ１２７とFIFOメモリ１３３における遅延量が、その行の重みの値に減らされる。
【００７１】
図１２は、バリアブルノード演算を１つずつ行う図１０のバリアブルノード計算器１０３の構成例を示している。
【００７２】
なお、図１２では、各メッセージが符号ビットを合わせて合計６ビット(bit)に量子化されているものとして、バリアブルノード計算器１０３を表している。また、図１２では、図９の検査行列Hで表されるLDPC符号のバリアブルノード演算が行われる。さらに、図１２のバリアブルノード計算機１０３には、クロックｃｋが供給され、クロックｃｋは、必要なブロックに供給されるようになっている。そして、各ブロックは、クロックｃｋに同期して処理を行う。
【００７３】
図１２のバリアブルノード計算器１０３は、制御部１０５から供給される、例えば、１ビットの制御信号D107に基づき、枝用メモリ１０２から１つずつ読み込まれるメッセージD103と、受信用メモリ１０４から読み込まれる受信データD104を用いて、式（１）にしたがって演算を行う。
【００７４】
即ち、バリアブルノード計算器１０３では、検査行列Hの各行に対応するチェックノードからの６ビットのメッセージD103（メッセージuj）が１つずつ読み込まれ、そのメッセージD103が、加算器１５１とFIFOメモリ１５５に供給される。また、バリアブルノード計算器１０３では、受信用メモリ１０４から６ビットの受信データD104が1つずつ読み込まれ、加算器１５６に供給される。さらに、バリアブルノード計算器１０３には、制御部１０５から制御信号D107が供給され、その制御信号D107は、セレクタ１５３に供給される。
【００７５】
加算器１５１は、メッセージD103（メッセージuj）とレジスタ１５２に格納されている９ビットの値D151とを加算することにより、メッセージD103を積算し、その結果得られる９ビットの積算値を、レジスタ１５２に再格納する。なお、検査行列Hの1列に亘る全ての枝からのメッセージD103が積算された場合、レジスタ１５２はリセットされる。
【００７６】
検査行列Hの1列に亘るメッセージD103が１つずつ読み込まれ、レジスタ１５２に1列分のメッセージD103が積算された値が格納された場合、制御部１０５から供給される制御信号D107は、「０」から「１」に変化する。例えば、列の重みが「５」である場合、制御信号D107は、１から４クロック目までは「０」となり、５クロック目では「１」となる。
【００７７】
制御信号D107が「１」の場合、セレクタ１５３は、レジスタ１５２に格納されている値、即ち、検査行列Hの１列に亘る全ての枝からのメッセージD103（メッセージuj）が積算された９ビットの値D151（ｊ＝１からｄVまでのΣuj)を選択し、レジスタ１５４に出力して格納させる。レジスタ１５４は、格納している値D151を、９ビットの値D152として、セレクタ１５３と加減算器１５６に供給する。制御信号D107が「０」の場合、セレクタ１５３は、レジスタ１５４から供給された値D152を選択し、レジスタ１５４に出力し再格納させる。即ち、検査行列Hの１列に亘る全ての枝からのメッセージD103（メッセージuj）が積算されるまで、レジスタ１５４は、前回積算された値を、セレクタ１５３と加減算器１５６に供給する。
【００７８】
一方、FIFOメモリ１５５は、レジスタ１５４から新たな値D152（ｊ＝１からｄVまでのΣuj)が出力されるまでの間、チェックノードからのメッセージD103を遅延し、６ビットの値D153として加減算器１５６に供給する。加減算器１５６は、レジスタ１５４から供給された値D152から、FIFOメモリ１５５から供給された値D153を減算する。即ち、加減算器１５６は、検査行列Hの1列に亘る全ての枝からのメッセージD103（メッセージuj）の積算値から、求めたい枝からのメッセージujを減算して、その減算値（ｊ＝１からｄv−１までのΣuj）を求める。さらに、加減算器１５６には、その減算値（ｊ＝１からｄv−１までのΣuj）に、受信用メモリ１０４から供給された受信データD104を加算して、その結果得られる６ビットの値をメッセージD105（メッセージvi）として出力する。
【００７９】
以上のように、バリアブルノード計算器１０３では、式（１）の演算が行われ、メッセージviが求められる。
【００８０】
なお、図９の検査行列Hの列の重みの最大は５であるため、即ち、バリアブルノードに供給されるメッセージの最大数は５であるため、バリアブルノード計算器１０３は、５個のメッセージ（uj）を遅延させるFIFOメモリ１５５を有している。列の重みが５未満の列のメッセージを計算するときには、FIFOメモリ１５５における遅延量が、その列の重みの値に減らされる。
【００８１】
また、加減算器１５６は、レジスタ１５４から供給される９ビットの値D152から、FIFOメモリ１５５から供給される６ビットの値D153を減算するとともに、受信用メモリ１０４から供給される６ビットの受信データD104を加算する演算を行うから、その演算結果は、６ビットのメッセージD105で表すことができる最小値未満となるか、または最大値を越えることがある。加減算器１５６は、演算結果が、６ビットのメッセージD105で表すことができる最小値未満である場合には、その最小値にクリッピングし、演算結果が、６ビットのメッセージD105で表すことができる最大値を越える場合には、その最大値にクリッピングする。
【００８２】
図１０の復号装置では、検査行列Hの重みにしたがって、制御部１０５から制御信号が与えられる。そして、図１０の復号装置によれば、枝用メモリ１００および１０２、並びにチェックノード計算器１０１およびバリアブルノード計算器１０３のFIFOメモリ１２７，１３３，１５５の容量さえ足りれば、制御信号のみを変えることで様々な検査行列HのLDPC符号を復号することができる。
【００８３】
なお、図示しないが、図１０の復号装置において、復号の最終段においては、式（１）のバリアブルノード演算の代わりに、式（５）の演算が行われ、その演算結果が、最終的な復号結果として出力される。
【００８４】
図１０の復号装置を繰り返し用いて、LDPC符号を復号する場合には、チェックノード演算とバリアブルノード演算とが交互に行われる。即ち、図１０の復号装置では、チェックノード計算器１０１によるチェックノード演算の結果を用いて、バリアブルノード計算器１０３によりバリアブルノード演算が行われ、バリアブルノード計算器１０３によるバリアブルノード演算の結果を用いて、チェックノード計算器１０１によりチェックノード演算が行われる。
【００８５】
従って、３２３の枝を有する図９の検査行列Hを用いた１回の復号に、323×2=646クロック(clock)を必要とする。例えば、５０回の繰り返し復号を行うためには、符号長である108個の符号（受信データ）を1フレームとして、その1フレームを受信する間に、646×50=32300クロック動作することが必要であり、受信周波数の約３００（≒32300/108）倍の高速動作が必要になる。受信周波数が数十MHzであるとすると、GHz以上の速度での動作を要求されることになる
【００８６】
また、図１０の復号装置を、例えば、５０台連接して、LDPC符号を復号する場合には、１フレーム(frame)目のバリアブルノード演算を行っている間に、２フレーム目のチェックノード演算を行い、３フレーム目のバリアブルノード演算を行う、というように、複数のバリアブルノード演算とチェックノード演算とを同時に行うことができる。この場合、108個の符号を受信する間に、323個の枝を計算すればよいので、復号装置は、受信周波数の約３（≒323/108）倍の周波数で動作すればよいことになり、十分に実現可能である。しかしながら、この場合、回路規模が、単純には、図１０の復号装置の５０倍になる。
【００８７】
次に、全ノードの演算を同時に行うことによって復号を行う場合(full parallel decoding)の復号装置の実装法について説明する。
【００８８】
この実装法については、例えば、非特許文献１に記載されている。
【００８９】
図１３は、図９の検査行列Hで表現される符号（符号化率2/3、符号長108）を復号する復号装置の一例の構成を示している。
【００９０】
図１３の復号装置では、枝用メモリ２０２または２０６から、３２３個ある枝に対応するメッセージデータを全て同時に読み出し、そのメッセージデータを用いて、３２３個の枝に対応する新たなメッセージデータを演算する。さらに、その演算の結果求められた新たなメッセージデータが全て同時に後段の枝用メモリ２０６または２０２に格納されていく。そして、図１３の復号装置を繰り返し用いることで繰り返し復号が実現される。
【００９１】
図１３において、復号装置は、１つの受信用メモリ２０５、２つの枝入れ替え装置２００および２０３、２つの枝用メモリ２０２および２０６、３６個のチェックノード計算器２０１1乃至２０１36、１０８個のバリアブルノード計算器２０４1乃至２０４108からなる。以下、各部について詳細に説明する。
【００９２】
枝用メモリ２０６は、前段のバリアブルノード計算器２０４1乃至２０４108からのメッセージD2061乃至D206108を全て同時に格納し、次の時刻（次のクロックのタイミング）に、メッセージD2061乃至D206108を、メッセージD2071乃至D207108として読み出し、次段の枝入れ替え装置２００に、メッセージD200(D2001乃至D200108)として供給する。枝入れ替え装置２００は、枝用メモリ２０６から供給されたメッセージD2001乃至D200108の順番を、図９の検査行列Hにしたがって並び替え（入れ替え）、チェックノード計算器２０１1乃至２０１36に、メッセージD2011乃至D20136として供給する。
【００９３】
チェックノード計算器２０１1乃至２０１36は、枝入れ替え装置２００から供給されるメッセージD2011乃至D20136を用いて式（７）にしたがって演算を行い、その演算の結果得られるメッセージD2021乃至D20236を、枝用メモリ２０２に供給する。
【００９４】
枝用メモリ２０２は、前段のチェックノード計算器２０１1乃至２０１36から供給されるメッセージD2021乃至D20236を全て同時に格納し、次の時刻に、そのすべてのメッセージD2021乃至D20236を、メッセージD2031乃至D20336として、次段の枝入れ替え装置２０３に供給する。
【００９５】
枝入れ替え装置２０３は、枝用メモリ２０２から供給されたメッセージD2031乃至D20336の順番を図９の検査行列Hにしたがって並び替え、バリアブルノード計算器２０４1乃至２０４108に、メッセージD2041乃至D204108として供給する。
【００９６】
バリアブルノード計算器２０４1乃至２０４108は、枝入れ替え装置２０３から供給されるメッセージD2041乃至D204108と、受信用メモリ２０５から供給される受信データD2051乃至D205108を用いて式（１）にしたがって演算を行い、その演算の結果得られるメッセージD2061乃至D206108を、次段の枝用メモリ２０６に供給する。
【００９７】
図１４は、チェックノード演算を同時に行う図１３のチェックノード計算器２０１m（ｍ＝１，２，・・・，３６）の構成例を示している。
【００９８】
図１４のチェックノード計算器２０１mでは、図１１のチェックノード計算器１０１と同様にして、式（７）のチェックノード演算が行われるが、そのチェックノード演算が、すべての枝について同時に行われる。
【００９９】
即ち、図１４のチェックノード計算器２０１mでは、枝入れ替え装置２００から供給される図９の検査行列Hの各列に対応するバリアブルノードからのメッセージ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を表している。また、図１４の回路は１つのチェックノードに相当する。ここで処理の対象としている図９の検査行列Hについては、その行数である３６行のチェックノードが存在するため、図１３の復号装置は、図１４に示したようなチェックノード計算器２０１mを３６個有している。
【０１０６】
ここで、図１４のチェックノード計算器２０１mでは、９個のメッセージを同時に計算することができる。そして、ここで処理の対象としている図９の検査行列Hの行の重みは、第１行が８で、第２乃至第３６行が９であるため、即ち、チェックノードに供給されるメッセージの数が、８のケースが１つと、９のケースが２９あるため、チェックノード計算器２０１1は、図１４の回路と同様の８つのメッセージを同時に計算することができる回路構成となっており、残りのチェックノード計算器２０１2乃至２０１36は、図１４の回路と同一構成となっている。
【０１０７】
図１５は、バリアブルノード演算を同時に行う図１３のバリアブルノード計算器２０４p（ｐ＝１，２，・・・，１０８）の構成例を示している。
【０１０８】
図１５のバリアブルノード計算器２０４pでは、図１２のバリアブルノード計算器１０３と同様にして、式（１）のバリアブルノード演算が行われるが、そのバリアブルノード演算が、すべての枝について同時に行われる。
【０１０９】
即ち、図１５のバリアブルノード計算器２０４pでは、枝入れ替え装置２０３から供給される、検査行列Hの各行に対応するチェックノードからの６ビットのメッセージ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を表している。また、図１５の回路は１つのバリアブルノードに相当する。ここで処理の対象としている図９の検査行列Hについては、その列数である１０８列のバリアブルノードが存在するから、図１３の復号装置は、図１５に示したような回路を１０８個有している。
【０１１４】
ここで、図１５のバリアブルノード計算器２０４pでは、５個のメッセージを同時に計算することができる。そして、ここで処理の対象としている図９の検査行列Hは、重みが５，３，２，１の列が、それぞれ、１８列、５４列、３５列、１列あるので、バリアブルノード計算器２０４1乃至２０４108のうちの１８個は、図１５の回路と同一構成となっており、残りの５４個、３５個、１個は、図１５の回路と同様の３，２，１つのメッセージをそれぞれ同時に計算することができる回路構成となっている。
【０１１５】
なお、図示しないが、図１３の復号装置においても、図１０における場合と同様に、復号の最終段においては、式（１）のバリアブルノード演算の代わりに、式（５）の演算が行われ、その演算結果が最終的な復号結果として出力される。
【０１１６】
図１３の復号装置によれば、３２３個ある枝に対応するメッセージすべてを１クロックで同時に計算することができる。
【０１１７】
図１３の復号装置を繰り返し用いて復号する場合には、チェックノード演算とバリアブルノード演算とを交互に行い、１回の復号を２クロックで行うことができる。従って、例えば、５０回の復号を行うためには、符号長が１０８個の符号を1フレームとする受信データを受信する間に2×50=100クロック動作すれば良いことになり、ほぼ受信周波数と同一の動作周波数でよいことになる。一般的に、LDPC符号は、符号長が数千から数万と大きいことから、図１３の復号装置を用いれば、復号回数を極めて多くすることができ、誤り訂正性能の向上を期待することができる。
【０１１８】
しかしながら、図１３の復号装置は、タナーグラフのすべての枝に対応するメッセージの演算を、並列で行うため、回路規模が、符号長に比例して大きくなる。また、図１３の復号装置を、ある符号長の、ある符号化率の、ある検査行列Hを持つLDPC符号の復号を行う装置として構成した場合、その復号装置において、他の符号長や、他の符号化率、他の検査行列Hを持つLDPC符号の復号を行うことは困難となる。即ち、図１３の復号装置は、図１０の復号装置のように、制御信号を変えるだけでは、様々な符号を復号することに対処することが困難であり、符号依存性が高い。
【０１１９】
図１０および図１３の復号装置の他に、一つでも全てでもなく、４つずつのメッセージの計算を同時に行う実装法について、例えば、非特許文献２に述べられているが、この場合、メモリの異なるアドレスからの同時読み出し、もしくは同時書き込みを避けることが一般的には容易でなく、メモリアクセス制御が困難であるという問題がある。
【０１２０】
この問題を解決するため、ランダムな符号ではなく、部分的にパラレルな復号器の実装に親和性の高い符号および復号装置について報告されている（例えば、非特許文献３と４参照）。しかしながら、非特許文献３に記載されている復号装置の実現方法は特定の符号のみに対応するものであり、１つの復号器で様々な符号長、符号化率の符号を復号することは困難である。
【０１２１】
また、図１６に示すように、６×６の単位行列、その単位行列の１のうち１個以上が０になった行列（以下、適宜、準単位行列という）、単位行列または準単位行列をサイクリックシフト(cyclic shift)した行列（以下、適宜、シフト行列という）、単位行列、準単位行列、またはシフト行列のうちの２以上(複数)の和（以下、適宜、和行列という）、６×６の０行列の組み合わせで表すことが可能な検査行列Hを有するLDPC符号、もしくは行や列の置換により、これらの行列の組み合わせで表すことが可能な検査行列Hを有するLDPC符号であれば、符号長、符号化率が異なる符号であっても復号可能な復号装置がある(例えば、特許文献１参照)。
【０１２２】
なお、図１６の検査行列Hは、図９に示した検査行列Hを、６×６の行列の単位に間隔を空けて表している。また、図１６の検査行列Hを構成する６×６の単位行列、準単位行列、シフト行列、和行列、０行列を、以下、適宜、構成行列という。
【０１２３】
図１７乃至図２２を参照して、図１６の検査行列Hで表現されるLDPC符号を復号する復号装置について説明する。
【０１２４】
図１７は、図１６の検査行列Hで表現されるLDPC符号を復号する復号装置４００の構成の一例を示すブロック図である。
【０１２５】
復号装置４００は、復号途中結果格納用メモリ４１０、サイクリックシフト回路４１１、６つの計算器４１２1乃至計算器４１２6からなる計算部４１２、復号途中結果格納用メモリ４１３、サイクリックシフト回路４１４、６つの計算器４１５1乃至計算器４１５6からなる計算部４１５、受信用メモリ４１６、および制御部４１７から構成される。
【０１２６】
ここで、計算器４１２k（k=1,2,・・・，6）で行われる演算と、計算器４１５kで行われる演算について、式を用いて説明する。
【０１２７】
具体的には、計算部４１２は、上述した式（７）と、以下に表す式（８）にしたがう第１の演算を行い、その第１の演算の結果である復号途中結果ujを復号途中結果格納用メモリ４１０に供給して格納させる。計算部４１５は、上述した式（５）にしたがう第２の演算を行い、その第２の演算の結果である復号途中結果vを復号途中結果格納用メモリ４１０に供給して格納させる。
【０１２８】
【数８】
2006304131.tif 000010
・・・（８）
【０１２９】
なお、式（８）のudvは、検査行列Hのｉ列のメッセージを求めようとする枝からのチェックノード演算の途中結果（ここでは、チェックノード演算結果そのもの）を表している。即ち、udvは、求めたい枝に対応する復号途中結果である。
【０１３０】
即ち、上述した式（５）にしたがう第２の演算の結果得られる復号途中結果vは、受信値u0iと検査行列Hのｉ列の各行の１に対応するすべての枝からのチェックノード演算の復号途中結果ujとを加算したものであるので、上述した式（７）に用いられる値viは、式（５）にしたがう第２の演算の結果得られる復号途中結果vから、検査行列Hのｉ列の、各行の１に対応する枝からのチェックノード演算の復号途中結果ujのうち、メッセージを求めようとする枝からのチェックノード演算の復号途中結果udvを引いた値となる。つまり、式（７）の演算に用いられる値viを求める式（１）の演算は、上述した式（５）と式（８）を組み合わせた演算である。
【０１３１】
従って、復号装置４００では、計算部４１２による式（７）および式（８）にしたがう第１の演算と、計算部４１５による式（５）にしたがう第２の演算とが交互に行われ、計算部４１５が、最後の第２の演算の結果を復号結果として出力することにより、LDPC符号の繰り返し復号を行うことができる。
【０１３２】
なお、ここでは、式（７）と式（８）にしたがう第１の演算結果を、復号途中結果ujと記載するが、この復号途中結果ujは、式（７）のチェックノード演算結果ｕjに等しい。
【０１３３】
また、第２の演算により求められる式（５）のvは、式（１）のバリアブルノード演算結果viに対して、メッセージを求めようとする枝からのチェックノード演算結果ujを加算したものであるから、検査行列Hの1列（１つのバリアブルノード）に対して、１つだけ求められる。
【０１３４】
復号装置４００では、計算部４１２が、計算部４１５による第２の演算の結果である検査行列Hの列に対応する復号途中結果vを用いて、第１の演算を行い、その演算の結果得られる検査行列Hのｉ列の、各行の１に対応する枝のメッセージ（各チェックノードが各枝に出力するメッセージ）の枝からのチェックノード演算の復号途中結果ujを復号途中結果格納用メモリ４１３に格納する。従って、復号途中結果格納用メモリ４１３の容量は、チェックノード演算の結果を格納する場合と同様に、検査行列Hの１の数（全枝数）と量子化ビット数とを乗算した値となる。
【０１３５】
一方、計算部４１５は、計算部４１２による第１の演算の結果である検査行列Hのｉ列の、各行の“１”に対応する復号途中結果ujと受信値u0iを用いて、第２の演算を行い、その演算の結果得られるｉ列に対応する復号途中結果vを復号途中結果格納用メモリ４１０に格納する。従って、復号途中結果格納用メモリ４１０に必要な容量は、検査行列Hの“１”の数より少ない検査行列Hの列数、即ち、LCPC符号の符号長と復号途中結果vの量子化ビット数とを乗算した値となる。
【０１３６】
その結果、バリアブルノード演算の結果を格納する場合に比べて、復号途中結果格納用メモリ４１０のメモリ容量を削減することができ、これにより、復号装置４００の回路規模を小さくすることができる。
【０１３７】
以下、図１７の復号装置４００の各部の動作について詳細に説明する。
【０１３８】
復号途中結果格納用メモリ４１０には、計算部４１５から、計算部４１５による第２の演算の結果である検査行列Hの６つの列に対応する６つの復号途中結果D415が供給され、復号途中結果格納用メモリ４１０は、計算部４１５から供給された６つの復号途中結果D415を、第１アドレスから順に格納（記憶）する。
【０１３９】
即ち、復号途中結果格納用メモリ４１０の第１アドレスには、検査行列Hの列に対応する復号途中結果のうち、第１列目から第６列目の復号途中結果vが格納される。そして、同様に、第２アドレスには、第７列目から第１２列目の復号途中結果vが格納され、第３アドレスには、第１３列目から第１８列目の復号途中結果が格納される。以後、同様に、第１０３列目から第１０８列目までの復号途中結果vが、６個ずつ、第４アドレスから第１８アドレスまで格納され、計１０８個の復号途中結果vが復号途中結果格納用メモリ４１０に格納される。従って、復号途中結果格納用メモリ４１０のワード（word）数は、図１６の検査行列Hの列数（LDPC符号の符号長）である１０８を、同時に読み書きする復号途中結果の数である６で割り算した１８となる。
【０１４０】
また、復号途中結果格納用メモリ４１０は、既に格納してある復号途中結果D415から、後段の計算部４１２が求めようとする復号途中結果ujの対応する検査行列Hの行において“１”になっている復号途中結果vを６つ同時に読み出し、復号途中結果D410として、サイクリックシフト回路４１１に供給する。
【０１４１】
なお、復号途中結果格納用メモリ４１０は、例えば、６つの復号途中結果を同時に読み書き可能なシングルポートRAMで構成される。また、復号途中結果格納用メモリ４１０には、計算部４１５の第２の演算により演算された列に対応する復号途中結果D414が格納されるので、復号途中結果格納用メモリ４１０に格納されるデータ量、即ち、復号途中結果格納用メモリ４１０に必要とされる記憶容量は、復号途中結果D414の量子化ビット数と、検査行列Hの列数（LDPC符号の符号長）との乗算値である。
【０１４２】
サイクリックシフト回路４１１には、復号途中結果格納用メモリ４１０から６つの復号途中結果D410が供給されるとともに、制御部４１７から、その復号途中結果D410に対応する検査行列Hの１が、検査行列Hにおいて元となる単位行列などを幾つサイクリックシフトであるかの情報（Matrixデータ）を表す制御信号D619が供給される。サイクリックシフト回路６１１は、制御信号D619を元に、６つの復号結果D410を並べ替えるサイクリックシフトを行い、その結果を復号途中結果D411として、計算部４１２に供給する。
【０１４３】
計算部４１２は、６つの計算器４１２1乃至４１２6からなる。計算部４１２には、サイクリックシフト回路４１１から、計算部４１５による第２の演算の結果得られた６つの復号途中結果D411（v）が供給されるとともに、復号途中結果格納用メモリ４１３から、前回、計算器４１２1乃至４１２6による第１の演算の結果得られた６つの復号途中結果D413（uj）が供給され、その６つの復号途中結果D411と６つの復号途中結果D413が、計算器４１２1乃至４１２6にそれぞれ供給される。また、計算部４１２には、制御部４１７から制御信号D419が供給され、その制御信号D419が、計算器４１２1乃至４１２6に供給される。なお、制御信号D419は、６つの計算器４１２1乃至４１２6に共通の信号である。
【０１４４】
計算器４１２1乃至４１２6は、それぞれ復号途中結果D411と復号途中結果D413を用いて、式（７）と式（８）にしたがって第１の演算を行い、復号途中結果D412（vi）を求める。計算部４１２は、計算器４１２1乃至４１２6による演算の結果得られる検査行列Hの６つの１に対応する６つの復号途中結果D412を復号途中結果格納用メモリ４１３に供給する。
【０１４５】
復号途中結果格納用メモリ４１３は、例えば、６つの復号途中結果を同時に読み書き可能な、２つのシングルポートRAMから構成される。復号途中結果格納用メモリ４１３には、計算部４１２から６つの復号途中結果D412が供給されるとともに、制御部４１７から復号途中結果４１３の読み書きを制御する制御信号D420が供給される。
【０１４６】
復号途中結果格納用メモリ４１３は、制御信号D420に基づいて、計算部４１２から供給される６つの復号途中結果D412をまとめて格納すると同時に、既に格納してある６つの復号途中結果D412を読み出し、復号途中結果D413として、計算部４１２とサイクリックシフト回路４１４に供給する。即ち、復号途中結果格納用メモリ４１３は、計算部４１２とサイクリックシフト回路４１４に供給する復号途中結果D413の読み出しと、計算部４１２から供給される復号途中結果D412の書き込みとを、同時に行う。
【０１４７】
なお、復号途中結果格納用メモリ４１３には、計算部４１２の第１の演算により演算された検査行列Hのｉ列の、各行の１に対応する枝からの第１の演算の復号途中結果D412が格納されるので、復号途中結果格納用メモリ４１３に格納されるデータ量、即ち、復号途中結果格納用メモリ４１３に必要とされる記憶容量は、復号途中結果D412の量子化ビット数と、検査行列Hの１の数との乗算値となる。
【０１４８】
サイクリックシフト回路４１４には、復号途中結果格納用メモリ４１３から６つの復号途中結果D413（復号途中結果uj）が供給されるとともに、制御部４１７から、その復号途中結果D413に対応する検査行列Hの１が検査行列Hにおいて元となる単位行列などを幾つサイクリックシフトしたものであるかの情報（Matrixデータ）を表す制御信号D421が供給される。サイクリックシフト回路４１４は、制御信号D421を元に、６つの復号途中結果D413を並べ替えるサイクリックシフトを行い、その結果を復号途中結果D414として、計算部４１５に供給する。
【０１４９】
計算部４１５は、６つの計算器４１５1乃至４１５6からなる。計算部４１５には、サイクリックシフト回路４１４から６つの復号途中結果D414が供給され、その復号途中結果D414が、計算器４１５1乃至４１５6のそれぞれに供給される。また、計算部４１５には、受信用メモリ４１７から６つの受信データD417（LDPC符号）が供給され、その受信データD417が、計算器４１５1乃至４１５6のそれぞれに供給される。さらに、計算部４１７には、制御部４１７から制御信号D422が供給され、その制御信号D422が計算器４１５1乃至４１５6に供給される。なお、制御信号D422は、６つの計算器４１７1乃至４１７6に共通の信号である。
【０１５０】
計算器４１５1乃至４１５6は、それぞれ復号途中結果D414と受信データD417とを用いて、式（５）にしたがって、それぞれ第２の演算を行い、復号途中結果D415を求める。計算部４１５は、計算器４１５1乃至４１５6の第２の演算の結果得られる６つの復号途中結果D415(v)を、復号途中結果格納用メモリ４１０に供給する。また、計算部４１５は、いま行う演算が最後の第２の演算である場合、その演算の結果得られる６つの復号途中結果D415を、最終的な復号結果として出力する。
【０１５１】
受信用メモリ４１６は、通信路を通して受信した受信値（符号ビット）D416から計算した符号ビットの０らしさの値である受信LLR（対数尤度比）のデータ（受信データ）D416を格納する。
【０１５２】
即ち、受信用メモリ４１６の第１のアドレスには、検査行列Hの列に対応する受信データD416のうち、検査行列Hの第１列目から第６列目までに対応する受信データD416が格納される。そして、第２のアドレスには、検査行列Hの第７列目から第１２列目までに対応する受信データD416が格納され、第３アドレスには、検査行列Hの第１３列目から第１８列目までに対応する受信データD416が格納される。以後、同様に、第４アドレスから第１８アドレスまでに、検査行列Hの第１９列目から第１０８列目までに対応する受信データD416が、６つずつ格納される。
【０１５３】
そして、受信用メモリ６１６は、既に格納している受信データD416を、バリアブルノード演算に必要となる順番に６つずつ読み出し、受信データD417として計算部４１５に供給する。
【０１５４】
なお、受信用メモリ４１６は、例えば、６つの受信データを同時に読み書き可能なシングルポートRAMから構成される。また、受信用メモリ４１６に格納されるデータ量、即ち、受信用メモリ３１５に必要とされる記憶容量は、LDPC符号の符号長と、受信データD416の量子化ビット数との乗算値である。さらに、受信用メモリ４１６のワード（word）数は、LDPC符号の符号長、即ち、検査行列Hの列数である１０８を、同時に読み出す受信データD417の数である６で割り算した値の１８である。
【０１５５】
制御部４１７は、制御信号D418をサイクリックシフト回路４１１に、制御信号D419を計算部４１２に供給することにより、それぞれを制御する。また、制御部４１７は、制御信号D420を復号途中結果格納用メモリ４１３に、制御信号D421をサイクリックシフト回路４１４に、制御信号D421を計算部４１５にそれぞれ供給することにより、それぞれを制御する。
【０１５６】
復号途中結果格納用メモリ４１０、サイクリックシフト回路４１１、計算部４１２、復号途中結果格納用メモリ４１３、サイクリックシフト回路４１４、計算部４１５の順で、データが一巡することで、復号装置４００は、１回の復号を行うことができる。復号装置４００では、所定の回数だけ繰り返して復号が行われた後、計算部４１５による第２の演算の結果である復号途中結果D415が、最終的な復号結果として出力される。
【０１５７】
図１８は、図１７の計算部４１２の計算器４１２1の構成例を示すブロック図である。
【０１５８】
なお、図１８では、計算器４１２1について説明するが、計算器４１２2乃至計算器４１２6も同様に構成される。
【０１５９】
また、図１８では、前回の計算部４１２による第１の演算の結果得られる各復号途中結果(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を積算し、その結果得られる９ビットの積算値をレジスタ４３４に再格納する。なお、検査行列Hの1行に亘る全ての１に対応する復号途中結果D411から求められた絶対値D433(|vi|)に対する演算結果が積算された場合、レジスタ４３４はリセットされる。
【０１６６】
検査行列Hの1行に亘る復号途中結果D411が１つずつ読み込まれ、レジスタ４３４に1行分の演算結果D434が積算された積算値が格納された場合、制御部４１７から供給される制御信号D419は、０から１に変化する。例えば、行の重み（row weight）が「９」である場合、制御信号D419は、１から８クロック目までは、「０」となり、９クロック目では「１」となる。
【０１６７】
制御信号D419が「１」の場合、セレクタ４３５は、レジスタ４３４に格納されている値、即ち、検査行列Hの1行に亘る全ての１に対応する復号途中結果D411（復号途中結果v）から求められたφ(|vi|)が積算された９ビットの値D435（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）を選択し、値D436として、レジスタ４３６に出力して格納させる。レジスタ４３６は、格納している値D436を、９ビットの値D437として、セレクタ４３５と加算器４３７に供給する。制御信号D419が「０」の場合、セレクタ４３５は、レジスタ４３６から供給された値D437を選択し、レジスタ４３６に出力して再格納させる。即ち、検査行列Hの1行に亘る全ての１に対応する復号途中結果D411（復号途中結果v）から求められたφ(|vi|)が積算されるまで、レジスタ４３６は、前回積算されたφ(|vi|)を、セレクタ４３５と加算器４３７に供給する。
【０１６８】
一方、FIFOメモリ４３８は、レジスタ４３６から新たな値D437（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）が出力されるまでの間、LUT４３２が出力した演算結果D434（φ(|vi|)）を遅延し、５ビットの値D438として減算器４３７に供給する。減算器４３７は、レジスタ４３６から供給された値D437から、FIFOメモリ４３８から供給された値D438を減算し、その減算結果を、５ビットの減算値D439としてLUT４３９に供給する。即ち、減算器４３７は、検査行列Hの1行に亘る全ての１に対応する復号途中結果D411（復号途中結果v）から求められたφ(|vi|)の積算値から、求めたい枝に対応する復号途中結果、即ち、検査行列Hの所定の１に対応する復号途中結果D411（復号途中結果v）から求められたφ(|vi|)を減算して、その減算値（ｉ＝１からｉ＝ｄc−１までのΣφ(|vi|)）を減算値D439としてLUT４３９に供給する。
【０１６９】
LUT４３９は、減算値D439（ｉ＝１からｉ＝ｄc−１までのΣφ(|vi|)）に対して、式（７）におけるφ-1（Σφ(|vi|)）の演算を行った５ビットの演算結果D440（φ-1(Σφ(|vi|)))を出力する。
【０１７０】
以上の処理と並行して、EXOR回路４４０は、レジスタ４４１に格納されている１ビットの値D442と符号ビットD432との排他的論理和を演算することにより、符号ビットどうしの乗算を行い、１ビットの乗算結果D441をレジスタ４４１に再格納する。なお、検査行列Hの1行に亘る全ての１に対応する復号途中結果D411から求められた符号ビットD432が乗算された場合、レジスタ４４１はリセットされる。
【０１７１】
検査行列Hの1行に亘る全ての１に対応する復号途中結果D411から求められた符号ビットD432が乗算された乗算結果D441（ｉ＝１からｄcまでのΠsign(vi)）がレジスタ４４１に格納された場合、制御部４１７から供給される制御信号D419は、「０」から「１」に変化する。
【０１７２】
制御信号D419が「１」の場合、セレクタ４４２は、レジスタ４４１に格納されている値、即ち、検査行列Hの1行に亘る全ての１に対応する復号途中結果D411から求められた符号ビットD432が乗算された値D442（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）を選択し、１ビットの値D443としてレジスタ４４３に出力して格納させる。レジスタ４４３は、格納している値D443を、１ビットの値D444としてセレクタ４４２とEXOR回路４４５に供給する。制御信号D419が「０」の場合、セレクタ４４２は、レジスタ４４３から供給された値D444を選択し、レジスタ４４３に出力して再格納させる。即ち、検査行列Hの1行に亘る全ての１に対応する復号途中結果D411（復号途中結果v）から求められた符号ビットD432が乗算されるまで、レジスタ４４３は、前回格納した値を、セレクタ４４２とEXOR回路４４５に供給する。
【０１７３】
一方、FIFOメモリ４４４は、レジスタ４４３から新たな値D444（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）がEXOR回路４４５に供給されるまでの間、符号ビットD432を遅延し、１ビットの値D445としてEXOR回路４４５に供給する。EXOR回路４４５は、レジスタ４４３から供給された値D444と、FIFOメモリ４４４から供給された値D445との排他的論理和を演算することにより、値D444を、値D445で除算し、１ビットの除算結果を除算値D446として出力する。即ち、EXOR回路４４５は、検査行列Hの1行に亘る全ての１に対応する復号途中結果D411から求められた符号ビットD432（sign(vi)）の乗算値を、検査行列Hの所定の１に対応する復号途中結果D411から求められた符号ビットD432（sign(vi)）で除算して、その除算値（ｉ＝１からｉ＝ｄc−１までのΠsign(vi)）を除算値D446として出力する。
【０１７４】
計算器４１２1では、LUT４３９から出力された５ビットの演算結果D440を下位５ビットとするとともに、EXOR回路４４５から出力された１ビットの除算値D446を最上位ビットとする合計６ビットが復号途中結果D412（復号途中結果uj）として出力される。
【０１７５】
以上のように、計算器４１２1では、式（７）と式（８）の演算が行われ、復号途中結果ujが求められる。
【０１７６】
なお、図１６の検査行列Hの行の重みの最大は９であるため、即ち、計算器４１２1に供給される復号途中結果D411（v）と復号途中結果D413（udv）の最大数は９であるため、計算器４１２1は、９個の復号途中結果D411から求められる９個の演算結果D434（φ(|vi|)）を遅延させるFIFOメモリ４３８と、９個の符号ビットD432を遅延させるFIFOメモリ４４４を有している。行の重みが９未満の行のメッセージを計算するときには、FIFOメモリ４３８とFIFOメモリ４４４における遅延量が、その行の重みの値に減らされる。
【０１７７】
図１９は、図１７の計算部４１５の計算器４１５1の構成例を示すブロック図である。
【０１７８】
なお、図１９では、計算器４１５1について説明するが、計算器４１５2乃至計算器４１５6も同様に構成される。
【０１７９】
また、図１９では、計算部４１２による第１の演算の結果得られる各復号途中結果（uj）が符号ビットを合わせて合計６ビットに量子化されているものとして、計算器４１５1を表している。さらに、図１９の計算器４１５1には、クロックｃｋが供給され、このクロックｃｋは、必要なブロックに供給されるようになっている。そして、各ブロックは、クロックｃｋに同期して処理を行う。
【０１８０】
図１９の計算器４１５1は、制御部４１７から供給される制御信号D422に基づいて、受信用メモリ４１６から１つずつ読み込まれる受信データD417（受信値u0i）と、サイクリックシフト回路４１４から１つずつ読み込まれる復号途中結果D414（uj）とを用いて、式（５）にしたがう第２の演算を行う。
【０１８１】
即ち、計算器４１５1では、サイクリックシフト回路４１４から、検査行列Hの各行の１に対応する６ビットの復号途中結果D414（復号途中結果uj）が１つずつ読み込まれ、その復号途中結果D414が、加算器４７１に供給される。また、計算器４１５1では、受信用メモリ４１６から６ビットの受信データD417が１つずつ読み込まれ、加算器４７５に供給される。さらに、計算器４１５1には、制御部４１７から制御信号D422が供給され、その制御信号D422は、セレクタ４７３に供給される。
【０１８２】
加算器４７１は、復号途中結果D414（復号途中結果uj）とレジスタ４７２に格納されている９ビットの値D471とを加算することにより、復号途中結果D414を積算し、その結果得られる９ビットの積算値を、レジスタ４７２に再格納する。なお、検査行列Hの１列に亘る全ての１に対応する復号途中結果D414が積算された場合、レジスタ４７２はリセットされる。
【０１８３】
検査行列Hの１列に亘る復号途中結果D414が１つずつ読み込まれ、レジスタ４７２に１列分の復号途中結果D414が積算された値が格納された場合、制御部４１７から供給される制御信号D422は、「０」から「１」に変化する。例えば、列の重みが「５」である場合、制御信号D422は、１から４クロック目までは「０」となり、５クロック目では「１」となる。
【０１８４】
制御信号D422が「１」の場合、セレクタ４７３は、レジスタ４７２に格納されている値、即ち、検査行列Hの１列に亘る全ての枝からの復号途中結果D414（復号途中結果uj）が積算された９ビットの値D471（ｊ＝１からｄVまでのΣuj)を選択し、レジスタ４７４に出力して格納させる。レジスタ４７４は、格納している値D471を、９ビットの値D472として、セレクタ４７１と加算器４７５に供給する。制御信号D422が「０」の場合、セレクタ４７３は、レジスタ４７４から供給された値D472を選択し、レジスタ４７４に出力し再格納させる。即ち、検査行列Hの１列に亘る全ての枝からの復号途中結果D414（復号途中結果uj）が積算されるまで、レジスタ４７４は、前回積算された値を、セレクタ４７３と加算器４７５に供給する。
【０１８５】
加算器４７５は、９ビットの値D472と、受信用メモリ４１６から供給された６ビットの受信データD417とを加算して、その結果得られる６ビットの値を復号途中結果D415（復号途中結果v）として出力する。
【０１８６】
以上のように、計算器４１５1では、式（５）の演算が行われ、復号途中結果vが求められる。
【０１８７】
なお、図９の検査行列Hの列の重みの最大は５であるため、即ち、計算器４１５1に供給される復号途中結果ujの最大数は５であるため、計算器４１５1は、６ビットの復号途中結果ujを最大５個加算する。従って、計算器４１５1の出力は、９ビットの値となっている。
【０１８８】
図２０は、図１７の復号途中結果格納用メモリ４１３の構成例を示すブロック図である。
【０１８９】
復号途中結果格納用メモリ４１３は、スイッチ５０１と５０４、および２つのシングルポートRAMである復号途中結果格納用RAM５０２と５０３から構成される。
【０１９０】
この復号途中結果格納用メモリ４１３の各部について詳細に説明する前に、まず、復号途中結果格納用RAM５０２と５０３へのデータの格納方法について説明する。
【０１９１】
復号途中結果格納用RAM５０２と５０３は、計算部４１２による第１の演算の結果得られ、スイッチ５０１を介して供給された復号途中結果D412を格納する。
【０１９２】
具体的には、復号途中結果格納用RAM５０２の第１アドレスから第９アドレスには、図１６の検査行列Hの第１行目から第６行目までの１に対応する復号途中結果D412(D501)が、各行ともに横方向（列方向）に詰めた形に（０を無視した形で）格納される。
【０１９３】
即ち、第ｊ行第ｉ列を、(j,ｉ)と表すこととすると、復号途中結果格納用RAM５０２の第１アドレスには、図１６の検査行列Hの構成行列である(1,1)から(6,6)の６×６の単位行列の１に対応するデータが、第２アドレスには、図１６の検査行列Hの構成行列である(1,25)から(6,30)のシフト行列（６×６）の単位行列を右方向に５つだけサイクリックシフトしたシフト行列）の１に対応するデータが格納される。第３アドレスから第８アドレスも同様に図１６の検査行列Hの構成行列と対応づけてデータが格納される。そして、第９アドレスには、検査行列Hの(1,102)から(6,108)のシフト行列（６×６の単位行列のうちの１行目の１を０に置き換えて１つだけ左方向にサイクリックシフトしたシフト行列）の１に対応するデータが格納される。ここで、図１６の検査行列Hの(1,102)から(6,108)のシフト行列においては、１行目に１がないため、第９アドレスにはデータが格納されない。
【０１９４】
また、復号途中結果格納用RAM５０２の第１０アドレスから第１８アドレスには、図１６の検査行列Hの第１３行目から第１８行目までの１に対応するデータが格納される。即ち、第１０アドレスには、検査行列Hの(13,7)から(18,12)の６×６の単位行列を右方向に５つだけサイクリックシフトした行列の１に対応するデータが格納され、第１１アドレスには、検査行列Hの(13,13)から（18,18）の和行列（６×６の単位行列と、６×６の単位行列を右方向に１つだけサイクリックシフトしたシフト行列との和である和行列）を構成するシフト行列の１に対応するデータが格納される。また、第１２アドレスには、検査行列Hの(13,13)から（18,18）の和行列を構成する単位行列の１に対応するデータが格納される。以下、第１３アドレスから第１８アドレスについても、検査行列Hに対応づけてデータが格納される。
【０１９５】
即ち、重みが２以上の構成行列については、その構成行列を、重みが１であるP×Pの単位行列、そのコンポーネントである１のうち１個以上が０になった準単位行列、または単位行列もしくは準単位行列をサイクリックシフトしたシフト行列のうちの複数の和の形で表現したときの、その重みが１の単位行列、準単位行列、またはシフト行列の１の位置に対応するデータ（単位行列、準単位行列、またはシフト行列に属する枝に対応するメッセージの復号途中結果）は、同一アドレスに格納される。
【０１９６】
同様に、復号途中結果格納用RAM５０２の第１９アドレスから第２７アドレスには、図１６の検査行列Hに対応づけて、第２５行目から第３０行目までの１に対応するデータが格納される。即ち、復号途中結果格納用RAM５０２のワード数は、２７である。
【０１９７】
復号途中結果格納用RAM５０３の第１アドレスから第９アドレスには、図１６の検査行列Hの第７行目から第１２行目までの１に対応する復号途中結果D412(D502)が、各行ともに横方向（列方向）に詰めた形に（０を無視した形で）格納される。
【０１９８】
即ち、復号途中結果格納用RAM５０３の第１アドレスには、検査行列Hの構成行列である(7,1)から(12,6)の和行列（６×６の単位行列を右方向に２つだけサイクリックシフトした第１のシフト行列と、右方向に４つだけサイクリックシフトした第２のシフト行列の和である和行列）を構成する第１のシフト行列の１に対応するデータが、第２アドレスには、検査行列Hの構成行列である(7,1)から(12,6)の和行列を構成する第２のシフト行列の１に対応するデータが格納される。以下、第３アドレスから第９アドレスも同様に検査行列Hの構成行列と対応づけてデータが格納される。
【０１９９】
同様に、復号途中結果格納用RAM５０３の第１０アドレスから第１８アドレスには、図１６の検査行列Hの第１９行目から第２４行目までの１に対応するデータが、第１９アドレスから第２７アドレスには、検査行列Hの第３１行目から第３６行目までの1に対応するデータが、図１６の検査行列Hに対応づけて格納される。即ち、復号途中結果格納用RAM５０３のワード数は、２７である。
【０２００】
上述したように、復号途中結果格納用RAM５０２と５０３のワード(word)数は、２７である。即ち、ワード数は、検査行列Hの行の重み(row weight)の９と行数の３６とを乗算し、その乗算結果(検査行列Hの１の数)を、同時に読み出す復号途中結果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５０２は、制御信号D4202が表すアドレスに既に格納されている前回の計算部４１２による第１の演算の結果得られた６つの復号途中結果D501を読み出し、復号途中結果D503としてスイッチ５０４に供給する。また、復号途中結果格納用RAM５０２は、制御信号D4202が表すアドレスに、スイッチ５０１から供給された６つの復号途中結果D501を格納する(書き込む)。
【０２０５】
復号途中結果格納用RAM５０３には、スイッチ５０１から６つの復号途中結果D412が、復号途中結果D502として供給されるとともに、制御部４１７からアドレスを表す制御信号D4203が供給される。復号途中結果格納用RAM５０３は、制御信号D4203が表すアドレスに既に格納されている前回の計算部４１２による第１の演算の結果得られた６つの復号途中結果D502を読み出し、復号途中結果D504としてスイッチ５０４に供給する。また、復号途中結果格納用RAM５０３は、制御信号D4203が表すアドレスに、スイッチ５０１から供給された６つの復号途中結果D502を格納する(書き込む)。
【０２０６】
スイッチ５０４には、復号途中結果格納用RAM５０２から復号途中結果D503が供給されるか、あるいは復号途中結果格納用RAM503から復号途中結果D504が供給される。また、制御部４１７から、復号途中結果格納用RAM５０２または復号途中結果格納用RAM５０３の一方の選択を表す制御信号D4204が供給される。スイッチ５０４は、制御信号D4204に基づいて、復号途中結果格納用RAM５０２または復号途中結果格納用RAM５０３の一方を選択し、その選択した一方から供給された６つの復号途中結果を、６つの復号途中結果D413として計算部４１２とサイクリックシフト回路４１４に供給する。
【０２０７】
図２１は、復号途中結果格納用メモリ４１３の復号途中結果格納用RAM５０２と復号途中結果格納用RAM５０３の読み出しと書き込みの動作を説明するタイミングチャートである。
【０２０８】
なお、図２１において、横軸は、時間（ｔ）を表している。また、図２１では、図２２の○印内に記載された数字ｉの構成行列の１に対応するデータの読み出しをＲｉと表し、そのデータの書き込み（格納）をＷｉと表す。
【０２０９】
復号途中結果格納用メモリ４１３では、計算部４１２により第１の演算が行われる場合、復号途中結果格納用RAM５０２が、制御信号D4202に基づいて、既に格納している、前回の計算部４１２の第１の演算の結果得られた復号途中結果D501のうち、同一アドレスに格納している検査行列Hの第１行目から第６行目までの１に対応する復号途中結果D501を、1クロックに６つずつ、９回（９クロック分）読み出し（図中、Ｒ０乃至Ｒ８）、スイッチ５０４を介して、計算部４１２に供給する。即ち、図１６の検査行列Hの行重みは、９であるため、検査行列Hの各行の１に対応する復号途中結果は９つあり、復号途中結果格納用RAM５０２は、第１行目から第６行目までの１に対応する６つの復号途中結果D501を、６つ単位で９回読み出す。
【０２１０】
次に、復号途中結果格納用RAM５０３は、制御信号D4203に基づいて、既に格納している、前回の計算部４１２による第１の演算の結果得られた復号途中結果D502のうち、同一アドレスに格納している検査行列Hの第７行目から第１２行目までの１に対応する復号途中結果D502を、６つ単位で９回続けて読み出し（Ｒ９乃至Ｒ１７）、スイッチ５０４を介して、計算部４１２に供給する。
【０２１１】
ここで、ノードを１つずつ計算する計算器４１２1乃至４１２6または４１５1乃至４１５6では、ノード次数(node degree)分の遅延が生じる。例えば、計算器４１２1乃至４１２6では９クロック分の遅延が生じる。また、復号装置４００が100MHzを超える高速動作を行う場合、計算器４１２1乃至４１２6では、さらに３クロック分程度の遅延が生じ、３クロック分程度のパイプライン化が必要となる。
【０２１２】
即ち、計算部４１２が第１の演算を行うために必要な時間、即ち復号途中結果格納用メモリ４１３から復号途中結果D413が読み出されてから、その復号途中結果D413を用いた第１の演算の結果得られる復号途中結果D412が復号途中結果格納メモリ４１３に供給されるまでの時間は、１２クロック分の時間Ｔ１となる。
【０２１３】
この場合、復号途中結果格納用RAM５０２から復号途中結果D503の１回目の読み出し（Ｒ０）が開始されてからＴ１時間後に、計算部４１２から復号途中結果格納メモリ４１３への、第１の演算の結果得られる検査行列Hの第１行目から第６行目までの１に対応する６つの復号途中結果D412の供給が開始される。その復号途中結果D413は、スイッチ501を介して復号途中結果D501として復号途中結果格納用RAM５０２に供給され、復号途中結果格納用RAM５０２は、その復号途中結果D501を、制御信号D4202に基づいて、既に読み出された復号途中結果D503が格納されていたアドレスに９回続けて格納する（Ｗ０乃至Ｗ８）。
【０２１４】
即ち、復号途中結果格納用RAM５０２により復号途中結果D503の９回の読み出し（Ｒ０乃至Ｒ８）が終了してから、復号途中結果格納用RAM５０２により復号途中結果D501の９回の格納（Ｗ０乃至Ｗ８）が開始されるまでに、３クロック分の時間Ｔｗ（＝Ｔ１−９）の待ち時間が生じる。
【０２１５】
その結果、復号途中結果格納用RAM５０３からの９回の読み出し(Ｒ９乃至Ｒ１７)が終了してから、時間Ｔｗが経過後に復号途中結果格納用RAM５０２への９回の格納（Ｗ０乃至Ｗ８）が終了する。従って、復号途中結果格納用RAM５０３からの９回の読み出し（Ｒ９乃至Ｒ１７）が終了してから、復号途中結果格納用RAM５０２からの９回の読み出し（Ｒ１８乃至Ｒ２６）を開始するまでに、時間Ｔｗの待ち時間が必要となる。
【０２１６】
また、サムプロダクトアルゴリズムを近似して実装する方法なども提案されているが、この方法では、性能の劣化を招いてしまう。
【０２１７】
以上のように、サムプロダクトアルゴリズムをハードウェアに実装する場合には、上述したように、枝に対応するメッセージの演算（チェックノード演算とバリアブルノード演算、または第１の演算と第２の演算）を、１つずつシリアル(serial)に行う方法、すべて並列（フルパラレル(full parallel)）に行う方法、幾つかずつ並列（パラレル(parallel)）に行う方法がある。
【０２１８】
しかしながら、Ｐ個ずつ並列に行う方法では、Ｐの値が大きいとき、特に計算機４１２の回路規模が大きくなってしまう。例えば、Ｐが360、符号長が64800のときに、計算部４１２の回路規模は、復号装置４００の全体の２０％、復号装置４００のメモリ(例えば、復号途中結果格納用メモリ４１０、復号途中結果格納用メモリ４１３、受信用メモリ４１６など)を除いた論理回路の６０％に達する場合がある。
【０２１９】
また、図２１に示すように、復号途中結果格納用RAM５０２と５０３のいずれからも読み出しが行われない時間Ｔｗが生じる。即ち、時間Ｔｗの間、第１の演算を行う計算部４１２には、復号途中結果D413が供給されないので、計算部４１２は、第１の演算を行わない（遊んでしまう）。特に、ノード次数が小さい場合、時間Ｔｗは相対的に長くなり、計算部４１２を長い間無駄にしていることになる。
【０２２０】
さらに、上述した復号装置では、予め決められた所定の回数だけ復号が行われる。
【０２２１】
【非特許文献１】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
【非特許文献３】T.Zhang,K.K.Parhi,”Joint(3,k)-regular LDPC Code and decoder/encoder design,”IEEE Transactions on Signal Processing,Vol.52,No.4,pp.1065-1079,April 2004
【非特許文献４】M.M.Mansour,N.R.Shanbhag,”A novel design methodology for high-performance programmable decoder cores for AA-LDPC codes,”Proceedings of IEEE Workshop on Signal Processing Systems 2003(SIPS 2003),pp.29-34,Aug.2003
【特許文献１】特開２００４−３６４２３３号公報
【発明の開示】
【発明が解決しようとする課題】
【０２２２】
本発明は、このような状況に鑑みてなされたものであり、復号の性能を向上させ、さらに消費電力を削減することができるようにするものである。
【課題を解決するための手段】
【０２２３】
本発明の復号装置は、LDPC符号の復号のためのチェックノードの演算とバリアブルノードの演算の一部である第１の演算を行う第１の演算手段と、LDPC符号の復号のためのバリアブルノードの演算の他の一部である第２の演算を行う第２の演算手段と、第２の演算手段により得られる演算結果のシンドロームを演算するシンドローム演算手段と、第１と第２の演算手段を制御する制御手段とを備え、第１と第２の演算手段は、第１と第２の演算を繰り返し行うことにより、LDPC符号の復号を行い、制御手段は、シンドローム演算手段により得られるシンドロームに基づいて、復号を終了させることを特徴とする。
【０２２４】
本発明の復号方法は、LDPC符号の復号のためのチェックノードの演算とバリアブルノードの演算の一部である第１の演算を行う第１の演算ステップと、LDPC符号の復号のためのバリアブルノードの演算の他の一部である第２の演算を行う第２の演算ステップと、第２の演算ステップの処理により得られる演算結果のシンドロームを演算するシンドローム演算ステップと、第１と第２の演算ステップの処理を制御する制御ステップとを含み、第１と第２の演算ステップの処理は、第１と第２の演算を繰り返し行うことにより、LDPC符号の復号を行い、制御ステップの処理は、シンドローム演算ステップの処理により得られるシンドロームに基づいて、復号を終了させることを特徴とする。
【０２２５】
本発明においては、LDPC符号の復号のためのチェックノードの演算とバリアブルノードの演算の一部である第１の演算と、バリアブルノードの演算の他の一部である第２の演算を繰り返し行うことにより、LDPC符号の復号を行う。また、第２の演算の結果のシンドロームを演算し、そのシンドロームに基づいて、復号を終了させる。
【発明の効果】
【０２２６】
本発明によれば、復号の性能を向上させ、さらに消費電力を削減することが可能となる。
【発明を実施するための最良の形態】
【０２２７】
以下に本発明の実施の形態を説明するが、請求項に記載の構成要件と、発明の実施の形態における具体例との対応関係を例示すると、次のようになる。この記載は、請求項に記載されている発明をサポートする具体例が、発明の実施の形態に記載されていることを確認するためのものである。従って、発明の実施の形態中には記載されているが、構成要件に対応するものとして、ここには記載されていない具体例があったとしても、そのことは、その具体例が、その構成要件に対応するものではないことを意味するものではない。逆に、具体例が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その具体例が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。
【０２２８】
さらに、この記載は、発明の実施の形態に記載されている具体例に対応する発明が、請求項に全て記載されていることを意味するものではない。換言すれば、この記載は、発明の実施の形態に記載されている具体例に対応する発明であって、この出願の請求項には記載されていない発明の存在、すなわち、将来、分割出願されたり、補正により追加される発明の存在を否定するものではない。
【０２２９】
請求項１に記載の復号装置は、
LDPC(Low Density Parity Check)符号の復号装置(例えば、図３４の復号装置1000)であって、
前記LDPC符号の復号のためのチェックノードの演算とバリアブルノードの演算の一部である第１の演算を行う第１の演算手段(例えば、図３４の計算部1102)と、
前記LDPC符号の復号のための前記バリアブルノードの演算の他の一部である第２の演算を行う第２の演算手段（例えば、図３４の計算部415）と、
前記第２の演算手段により得られる演算結果のシンドロームを演算するシンドローム演算手段（例えば、図３４のシンドローム判定部2001）と、
前記第１と第２の演算手段を制御する制御手段（例えば、図３４の制御部2003）と
を備え、
前記第１と第２の演算手段は、前記第１と第２の演算を繰り返し行うことにより、前記LDPC符号の復号を行い（図３５のステップＳ７７とＳ８１の処理）、
前記制御手段は、前記シンドローム演算手段により得られるシンドロームに基づいて、前記復号を終了させる（例えば、図３５のステップＳ８６の処理）
ことを特徴とする。
【０２３０】
請求項７に記載の復号方法は、
LDPC(Low Density Parity Check)符号の復号装置(例えば、図３４の復号装置1000)の復号方法であって、
前記LDPC符号の復号のためのチェックノードの演算とバリアブルノードの演算の一部である第１の演算を行う第１の演算ステップ(例えば、図３５のステップＳ８１)と、
前記LDPC符号の復号のための前記バリアブルノードの演算の他の一部である第２の演算を行う第２の演算ステップ（例えば、図３５のステップＳ７７）と、
前記第２の演算ステップの処理により得られる演算結果のシンドロームを演算するシンドローム演算ステップ(例えば、図３５のステップＳ７２)と、
前記第１と第２の演算ステップの処理を制御する制御ステップ(例えば、図３５のステップＳ８６)と
を含み、
前記第１と第２の演算ステップの処理は、前記第１と第２の演算を繰り返し行うことにより、前記LDPC符号の復号を行い(例えば、図３５のステップＳ７７とＳ８１の処理)、
前記制御ステップの処理は、前記シンドローム演算ステップの処理により得られるシンドロームに基づいて、前記復号を終了させる（例えば、図３５のステップＳ８６の処理）
ことを特徴とする。
【０２３１】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。
【０２３２】
図２３は、図１６の検査行列Hで表現されるLDPC符号を復号する本発明を適用した復号装置の第１実施の形態の構成例を示している。
【０２３３】
図２３の復号装置1000は、サイクリックシフト回路４１４、計算部４１５、受信用メモリ４１６、サイクリックシフト回路1101、３つの計算器11021乃至11023からなる計算部1102、復号途中結果格納用メモリ1103、復号途中結果格納用メモリ1104、および制御部1105から構成される。なお、図１７と同一のものには、同一の符号を付してある。
【０２３４】
サイクリックシフト回路1101には、復号途中結果格納用メモリ1104から６つの復号途中結果D1104と、受信用メモリ４１６から６つの受信データD417（LDPC符号）が供給される。また、サイクリックシフト回路1101には、制御部1105から、その復号途中結果D1104に対応する検査行列Hの１が、検査行列Hにおいて元となる単位行列などを幾つサイクリックシフトしたものであるかの情報（Matrixデータ）を表し、さらに６つの復号途中結果D1104または受信データD417のいずれを選択するかの情報を表す制御信号D1106が供給される。
【０２３５】
サイクリックシフト回路1101は、制御信号D1106を元に、６つの復号途中結果D1104または受信データD417を選択し、並べ替えるサイクリックシフトを行う。サイクリックシフト回路110１は、６つの復号途中結果D1104または受信データD417をサイクリックシフトした結果のうち、構成行列の上半分（１行目乃至３行目）または下半分（４行目乃至６行目）の１に対応する３つを復号途中結果D1101として、計算部1102に供給する。
【０２３６】
計算部1102は、３つの計算器11021乃至11023からなる。計算部1102には、サイクリックシフト回路1101から、計算部４１５による第２の演算の結果得られた３つの復号途中結果D1101（v）が供給されるとともに、復号途中結果格納用メモリ1103から、前回計算器11021乃至11023による第１の演算の結果得られた構成行列の上半分または下半分の１に対応する３つの復号途中結果D1103（uj）が供給され、その３つの復号途中結果D1101と３つの復号途中結果D1103が、計算器11021乃至11023に供給される。また、計算部1102には、制御部1105から制御信号D1107がきょうきゅうされ、その制御信号D1107が、計算器11021乃至11023に供給される。なお、制御信号D1107は、３つの計算器11021乃至11023に共通の信号である。
【０２３７】
計算器11021乃至11023は、図１８に示した計算器４１２1と同様に構成され、それぞれ復号途中結果D1101とD1103を用いて、式（７）と式（８）にしたがって第１の演算を行い、復号途中結果D1102（vi）を求める。計算部1102は、計算器11021乃至11023による演算の結果得られる、構成行列の上半分または下半分の３つの１に対応する３つの復号途中結果D1102を復号途中結果格納用メモリ1103に供給する。
【０２３８】
復号途中結果格納用メモリ1103は、例えば、３つの復号途中結果D1102を同時に読み書き可能な、４つのシングルポートRAMから構成される。復号途中結果格納用メモリ４１３には、計算部４１２から３つの復号途中結果D1102が供給されるとともに、制御部1105から復号途中結果格納用メモリ1103の読み書きを制御する制御信号D1108が供給される。
【０２３９】
復号途中結果格納用メモリ1103は、制御信号D1108に基づいて、計算部1102から供給される３つの復号途中結果D1102をまとめて格納すると同時に、既に格納してある３つの復号途中結果D1102を読み出し、復号途中結果D1103として、計算部1102とサイクリックシフト回路４１４に供給する。即ち、復号途中結果格納用メモリ1103は、計算部1102とサイクリックシフト回路４１４に供給する復号途中結果D1103の読み出しと、計算部1103から供給される復号途中結果D1102の書き込みとを、同時に行う。
【０２４０】
なお、復号途中結果格納用メモリ1103には、計算部1102の第１の演算により演算された検査行列Hのｉ列の、各行の１に対応する枝からの第１の演算の復号途中結果D1102が格納されるので、復号途中結果格納用メモリ1103に格納されるデータ量、即ち、復号途中結果格納用メモリ1103に必要とされる記憶容量は、復号途中結果D1102の量子化ビット数と、検査行列Hの１の数との乗算値となる。
【０２４１】
サイクリックシフト回路４１４、計算部４１５、および受信用メモリ４１６は、図１７のそれらと同一であるので説明は省略する。なお、サイクリックシフト回路４１４は、復号途中結果格納用メモリ1103から３つずつ供給される６つの復号途中結果D1103をサイクリックシフトし、６つの復号途中結果D414を計算部４１５に供給する。
【０２４２】
復号途中結果格納用メモリ1104は、サイクリックシフト回路1101からの復号結果D1105を６つずつ、第１アドレスから順に格納したり、既に格納してある復号結果D1105を出力する。また、復号途中結果格納用メモリ1104は、計算部４１５から供給された第２の演算の結果である検査行列Hの６つの列に対応する６つの復号途中結果D415を、第１アドレスから順に格納（記憶）する。
【０２４３】
即ち、復号途中結果格納用メモリ1104の第１アドレスには、図１７の復号途中結果格納用メモリ410と同様に、検査行列Hの列に対応する復号途中結果のうち、第１列目から第６列目の復号途中結果vが格納される。そして、同様に、第２アドレスには、第７列目から第１２列目の復号途中結果vが格納され、第３アドレスには、第１３列目から第１８列目の復号途中結果が格納される。以後、同様に、第１９列目から第１０８列目までの復号途中結果vが、６個ずつ、第４アドレスから第１８アドレスまで格納され、計１０８個の復号途中結果vが復号途中結果格納用メモリ1104に格納される。
【０２４４】
従って、復号途中結果格納用メモリ1104のワード（word）数は、図１６の検査行列Hの列数（LDPC符号の符号長）である１０８を、同時に読み書きする復号途中結果の数である６で割り算した１８となる。
【０２４５】
復号途中結果格納用メモリ1104は、既に格納してある復号途中結果D415から、後段の計算部1102が求めようとする復号途中結果ujの対応する検査行列Hの行において“１”になっている復号途中結果vを６つ同時に読み出し、復号途中結果D1104として、サイクリックシフト回路1101に供給する。
【０２４６】
なお、復号途中結果格納用メモリ1104は、例えば、６つの復号途中結果を同時に読み書き可能なシングルポートRAMで構成される。また、復号途中結果格納用メモリ1104には、計算部４１５の第２の演算により演算された列に対応する復号途中結果D414が格納されるので、復号途中結果格納用メモリ４１０に格納されるデータ量、即ち、復号途中結果格納用メモリ４１０に必要とされる記憶容量は、復号途中結果D414の量子化ビット数と、検査行列Hの列数（LDPC符号の符号長）との乗算値である。
【０２４７】
制御部1105は、制御信号D1106をサイクリックシフト回路1101に、制御信号D1107を計算部1102に供給することにより、それぞれを制御する。また、制御部1105は、制御信号D1108を復号途中結果格納用メモリ1103に、制御信号D421をサイクリックシフト回路４１４に、制御信号D422を計算部４１５にそれぞれ供給することにより、それぞれを制御する。
【０２４８】
サイクリックシフト回路1101、計算部1102、復号途中結果格納用メモリ1103、サイクリックシフト回路４１４、計算部４１５、復号途中結果格納用メモリ1104の順で、データが一巡することで、復号装置1000は、１回の復号を行うことができる。復号装置1000では、例えば、所定の回数だけ繰り返して復号が行われた後、計算部４１５による第２の演算の結果である復号途中結果D1104が、最終的な復号結果として出力される。
【０２４９】
図２４は、図２３の復号途中結果格納用メモリ1103の構成例を示すブロック図である。
【０２５０】
復号途中結果格納用メモリ1103は、スイッチ1201と1206、並びに４つのシングルポートRAMである復号途中結果格納用RAM1202乃至1205から構成される。
【０２５１】
この復号途中結果格納用メモリ1103の各部について詳細に説明する前に、まず、復号途中結果格納用RAM1202乃至1205へのデータの格納方法について説明する。
【０２５２】
復号途中結果格納用RAM1202乃至1205は、計算部1102による第１の演算の結果得られ、スイッチ1201を介して供給された復号途中結果D1102を格納する。
【０２５３】
具体的には、復号途中結果格納用RAM1202の第１アドレスから第９アドレスには、図１６の検査行列Hの第１行目から第３行目までの１に対応する復号途中結果D1102(D1201)が、各行ともに横方向（列方向）に詰めた形に（０を無視した形で）格納される。
【０２５４】
即ち、第ｊ行第ｉ列を、(j,ｉ)と表すこととすると、復号途中結果格納用RAM1202の第１アドレスには、図１６の検査行列Hの構成行列である(1,1)から(6,6)の６×６の単位行列の上半分（1乃至３行目）の１に対応するデータが、第２アドレスには、図１６の検査行列Hの構成行列である(1,25)から(6,30)のシフト行列（６×６）の単位行列を右方向に５つだけサイクリックシフトしたシフト行列）の上半分の１に対応するデータが格納される。第３アドレスから第８アドレスも同様に図１６の検査行列Hの構成行列の上半分と対応づけてデータが格納される。
【０２５５】
そして、第９アドレスには、検査行列Hの(1,103)から(6,108)のシフト行列（６×６の単位行列のうちの１行目の１を０に置き換えて１つだけ左方向にサイクリックシフトしたシフト行列）の上半分の１に対応するデータが格納される。ここで、図１６の検査行列Hの(1,103)から(6,108)のシフト行列においては、１行目に１がないため、第９アドレスにはデータが格納されない。
【０２５６】
また、復号途中結果格納用RAM1202の第１０アドレスから第１８アドレスには、図１６の検査行列Hの第１３行目から第１５行目までの１に対応するデータが格納される。即ち、第１０アドレスには、検査行列Hの(13,7)から(18,12)の６×６の単位行列を右方向に５つだけサイクリックシフトした行列の上半分の１に対応するデータが格納され、第１１アドレスには、検査行列Hの(13,13)から（18,18）の和行列（６×６の単位行列と、６×６の単位行列を右方向に１つだけサイクリックシフトしたシフト行列との和である和行列）を構成するシフト行列の上半分の１に対応するデータが格納される。
【０２５７】
また、第１２アドレスには、検査行列Hの(13,13)から（18,18）の和行列を構成する単位行列の上半分の１に対応するデータが格納される。以下、第１３アドレスから第１８アドレスについても、検査行列Hの構成行列の上半分に対応づけてデータが格納される。
【０２５８】
同様に、復号途中結果格納用RAM1202の第１９アドレスから第２７アドレスには、図１６の検査行列Hに対応づけて、第２５行目から第２７行目までの１に対応するデータが格納される。即ち、復号途中結果格納用RAM1202のワード数は、２７である。
【０２５９】
また、復号途中結果格納用RAM1203の第１アドレスから第９アドレスには、図１６の検査行列Hの第４行目から第６行目までの１に対応する復号途中結果D1102(D1202)が、各行ともに横方向に詰めた形に格納される。
【０２６０】
即ち、復号途中結果格納用RAM1203の第１アドレスには、図１６の検査行列Hの構成行列である(1,1)から(6,6)の６×６の単位行列の下半分（４乃至６行目）の１に対応するデータが、第２アドレスには、図１６の検査行列Hの構成行列である(1,25)から(6,30)のシフト行列（６×６）の単位行列を右方向に５つだけサイクリックシフトしたシフト行列）の下半分の１に対応するデータが格納される。第３アドレスから第９アドレスも同様に図１６の検査行列Hの構成行列の下半分と対応づけてデータが格納される。
【０２６１】
また、復号途中結果格納用RAM1203の第１０アドレスから第１８アドレスには、図１６の検査行列Hの第１６行目から第１８行目までの１に対応するデータが格納される。即ち、第１０アドレスには、検査行列Hの(13,7)から(18,12)の６×６の単位行列を右方向に５つだけサイクリックシフトした行列の下半分の１に対応するデータが格納され、第１１アドレスには、検査行列Hの(13,13)から（18,18）の和行列（６×６の単位行列と、６×６の単位行列を右方向に１つだけサイクリックシフトしたシフト行列との和である和行列）を構成するシフト行列の下半分の１に対応するデータが格納される。また、第１２アドレスには、検査行列Hの(13,13)から（18,18）の和行列を構成する単位行列の下半分の１に対応するデータが格納される。以下、第１３アドレスから第１８アドレスについても、検査行列Hの構成行列の下半分に対応づけてデータが格納される。
【０２６２】
同様に、復号途中結果格納用RAM1203の第１９アドレスから第２７アドレスには、図１６の検査行列Hに対応づけて、第２８行目から第３０行目までの１に対応するデータが格納される。即ち、復号途中結果格納用RAM1203のワード数は、２７である。
【０２６３】
復号途中結果格納用RAM1204の第１アドレスから第９アドレスには、図１６の検査行列Hの第７行目から第９行目までの１に対応する復号途中結果D1102(D1203)が、各行ともに横方向に詰めた形に格納される。
【０２６４】
即ち、復号途中結果格納用RAM1204の第１アドレスには、検査行列Hの構成行列である(7,1)から(12,6)の和行列（６×６の単位行列を右方向に２つだけサイクリックシフトした第１のシフト行列と、右方向に４つだけサイクリックシフトした第２のシフト行列の和である和行列）を構成する第１のシフト行列の上半分（７乃至９行目）の１に対応するデータが、第２アドレスには、検査行列Hの構成行列である(7,1)から(12,6)の和行列を構成する第２のシフト行列の上半分の１に対応するデータが格納される。以下、第３アドレスから第９アドレスも同様に検査行列Hの構成行列の上半分と対応づけてデータが格納される。
【０２６５】
同様に、復号途中結果格納用RAM1204の第１０アドレスから第１８アドレスには、図１６の検査行列Hの第１９行目から第２１行目までの１に対応するデータが、第１９アドレスから第２７アドレスには、検査行列Hの第３１行目から第３３行目までの1に対応するデータが、図１６の検査行列Hに対応づけて格納される。即ち、復号途中結果格納用RAM1204のワード数は、２７である。
【０２６６】
復号途中結果格納用RAM1205の第１アドレスから第９アドレスには、図１６の検査行列Hの第１０行目から第１２行目までの１に対応する復号途中結果D1102(D1204)が、各行ともに横方向に詰めた形に格納される。
【０２６７】
即ち、復号途中結果格納用RAM1205の第１アドレスには、検査行列Hの構成行列である(7,1)から(12,6)の和行列（６×６の単位行列を右方向に２つだけサイクリックシフトした第１のシフト行列と、右方向に４つだけサイクリックシフトした第２のシフト行列の和である和行列）を構成する第１のシフト行列の下半分（１０乃至１２行目）の１に対応するデータが、第２アドレスには、検査行列Hの構成行列である(7,1)から(12,6)の和行列を構成する第２のシフト行列の下半分の１に対応するデータが格納される。以下、第３アドレスから第９アドレスも同様に検査行列Hの構成行列の下半分と対応づけてデータが格納される。
【０２６８】
同様に、復号途中結果格納用RAM1205の第１０アドレスから第１８アドレスには、図１６の検査行列Hの第２２行目から第２４行目までの１に対応するデータが、第１９アドレスから第２７アドレスには、検査行列Hの第３４行目から第３６行目までの1に対応するデータが、図１６の検査行列Hに対応づけて格納される。即ち、復号途中結果格納用RAM1205のワード数は、２７である。
【０２６９】
上述したように、復号途中結果格納用RAM1202乃至1204のワード(word)数は、２７である。即ち、ワード数は、検査行列Hの行の重み(row weight)の９と行数の３６とを乗算し、その乗算結果(検査行列Hの１の数)を、同時に読み出す復号途中結果D1201の数の３で除算し、さらに、復号途中結果格納用メモリ1103が有する復号途中結果格納用RAMの個数の４で除算した値となる。
【０２７０】
以下、図２４の復号途中結果格納用メモリ1103の各部の動作について詳細に説明する。
【０２７１】
復号途中結果格納用メモリ1103には、計算部1102により第１の演算が行われる場合、計算部1102から第１の演算の結果得られる復号途中結果D1102（uj）が供給され、その復号途中結果D1102が復号途中結果格納用RAM1202乃至1204のいずれか１つの所定のアドレスに書き込まれると同時に、その他の１つから、前回の計算部1102による第１の演算の結果得られた復号途中結果D1102が読み出され、復号途中結果D1103として計算部1102に出力される。一方、計算部４１５により第２の演算が行われる場合、復号途中結果格納用メモリ1103では、復号途中結果格納用RAM1202乃至1204の書き込みが行われず、いずれか１つの復号途中結果格納用RAM1202乃至1204の所定のアドレスから復号途中結果D1102を読み出して、復号途中結果D1103としてサイクリックシフト回路４１４に供給される。
【０２７２】
スイッチ1201には、計算部1102から３つの復号途中結果D1102が供給されるとともに、その復号途中結果D1102を書き込むメモリとして、復号途中結果格納用RAM1202乃至1205のいずれか１つの選択を表す制御信号D11081が制御部１１０５から供給される。スイッチ1201は、制御信号D11081に基づいて、復号途中結果格納用RAM1202乃至1205のいずれか１つを選択し、その選択した復号途中結果格納用RAM1202乃至1205に、３つの復号途中結果D1102を供給する。
【０２７３】
復号途中結果格納用RAM1202乃至1205には、スイッチ1201から３つの復号途中結果D1102が、それぞれ復号途中結果D1201乃至D1204として供給されるとともに、制御部1105からアドレスを表す制御信号D11082乃至D11085が供給される。復号途中結果格納用RAM1202乃至1205は、それぞれ制御信号D11082乃至D11085が表すアドレスに既に格納されている前回の計算部1102による第１の演算の結果得られた３つの復号途中結果D1201乃至D1204を読み出し、復号途中結果D1205乃至D1208としてスイッチ1206に供給する。また、復号途中結果格納用RAM1202乃至1205は、それぞれ、制御信号D11082乃至D11085が表すアドレスに、スイッチ1201から供給された３つの復号途中結果D1201乃至D1204を格納する(書き込む)。
【０２７４】
スイッチ1206には、復号途中結果格納用RAM1202からの復号途中結果D1205、復号途中結果格納用RAM1203からの復号途中結果D1206、復号途中結果格納用RAM1204からの復号途中結果D1207、または復号途中結果格納用RAM1205からの復号途中結果D1208が供給される。また、制御部1105から、復号途中結果格納用RAM1202乃至1205のいずれか１つの選択を表す制御信号D11086が供給される。スイッチ1206は、制御信号D11086に基づいて、復号途中結果格納用RAM1202乃至1205のいずれか１つを選択し、その選択した１つから供給された３つの復号途中結果D1205乃至D1208を、３つの復号途中結果D1103として計算部1102またはサイクリックシフト回路４１４に供給する。
【０２７５】
図２５は、復号途中結果格納用メモリ1103の復号途中結果格納用RAM1202と復号途中結果格納用RAM1204の読み出しと書き込みの動作を説明するタイミングチャートである。
【０２７６】
なお、図２５において、横軸は、時間（ｔ）を表している。また、図２５では、図２６の○印内に記載された数字ｉ0の構成行列の上半分の１に対応するデータの読み出しをＲｉ0と表し、そのデータの書き込み（格納）をＷｉ0と表す。さらに、図２６の○印内に記載された数字ｉ1の構成行列の下半分の１に対応するデータの読み出しをＲｉ1と表し、そのデータの書き込みをＷｉ1と表す。
【０２７７】
復号途中結果格納用メモリ1103では、計算部1102により第１の演算が行われる場合、復号途中結果格納用RAM1202が、制御信号D11082に基づいて、既に格納している、前回の計算部1102の第１の演算の結果得られた復号途中結果D1201のうち、同一アドレスに格納している検査行列Hの第１行目から第３行目までの１に対応する復号途中結果D1201(D1205)を、３つずつ９回（９クロック分）読み出し（Ｒ０0乃至Ｒ８0）、スイッチ1206を介して、復号途中結果D1103として計算部1102に供給する。即ち、図１６の検査行列Hの行重みは、９であるため、検査行列Hの各行の１に対応する復号途中結果は９つあり、復号途中結果格納用RAM1202は、第１行目から第３行目までの１に対応する３つの復号途中結果D1201を、３つ単位で９回読み出す。
【０２７８】
次に、復号途中結果格納用RAM1203は、制御信号D11083に基づいて、既に格納している、前回の計算部1102の第１の演算の結果得られた復号途中結果D1202のうち、同一アドレスに格納している検査行列Hの第４行目から第６行目までの１に対応する復号途中結果D1202を、３つ単位で９回続けて読み出し（図中、Ｒ０1乃至Ｒ８1）、スイッチ1206を介して、計算部1102に供給する。
【０２７９】
ここで、計算部1102が第１の演算を行うために必要な時間、即ち復号途中結果格納メモリ1103から復号途中結果D1103が読み出されてから、その復号途中結果D1103を用いた第１の演算の結果得られる復号途中結果D1102が復号途中結果格納メモリ1103に供給されるまでの時間は、１２クロック分の時間Ｔ１であるものとする。
【０２８０】
この場合、復号途中結果格納用RAM1202から復号途中結果D1205の１回目の読み出し（Ｒ０0）が開始されてからＴ１時間後に、計算部1102から復号途中結果格納用メモリ1103への、第１の演算の結果得られる検査行列Hの第１行目から第３行目までの１に対応する３つの復号途中結果D1102の供給が開始される。その復号途中結果D1102は、スイッチ1201を介して復号途中結果D1201として復号途中結果格納用RAM1202に供給され、復号途中結果格納用RAM1202は、その復号途中結果D1202を、制御信号D11082に基づいて、既に読み出された復号途中結果D1205が格納されていたアドレスに９回続けて格納する（Ｗ０0乃至Ｗ８0）。
【０２８１】
即ち、復号途中結果格納用RAM1202により復号途中結果D1205の９回の読み出し（Ｒ０0乃至Ｒ８0）が終了してから、復号途中結果格納用RAM1202により復号途中結果D1201の９回の格納（Ｗ０0乃至Ｗ８0）が開始されるまでに、３クロック分の時間Ｔｗ（＝Ｔ１−９）が生じる。その結果、復号途中結果格納用RAM1203からの９回の読み出し(Ｒ０1乃至Ｒ８1)が終了してから、時間Ｔｗが経過後に復号途中結果格納用RAM1202への９回の格納（Ｗ０0乃至Ｗ８0）が終了する。
【０２８２】
しかしながら、復号途中結果格納用メモリ1103では、次の第１の演算に用いられる検査行列Hの第７行目から第９行目までの１に対応する復号途中結果D1203が、復号途中結果格納用RAM1204に格納されているので、復号途中結果格納用RAM1203からの９回の読み出し（Ｒ０1乃至Ｒ８1）直後に、復号途中結果格納用RAM1204からの９回の読み出し（Ｒ９0乃至Ｒ１７0）を行うことができる。
【０２８３】
また、復号途中結果格納用RAM1203からの９回の読み出し（Ｒ０1乃至Ｒ８1）が終了してから時間Ｔｗ後に、復号途中結果格納用RAM1203により復号途中結果D1202の９回の格納（Ｗ０1乃至Ｗ８1）が開始される。
【０２８４】
次に、復号途中結果格納用RAM1204からの９回の読み出し（Ｒ９0乃至Ｒ１７0）が終了した直後に、次の第１の演算に用いられる検査行列Hの第１０行目から第１２行目までの１に対応する復号途中結果D1204が、復号途中結果格納用RAM1205から９回読み出される（Ｒ９1乃至Ｒ１７1）。また、復号途中結果格納用RAM1204からの９回の読み出し（Ｒ９0乃至Ｒ１７0）が終了してから時間Ｔｗ後に、復号途中結果格納用RAM1204により復号途中結果D1203の９回の格納（Ｗ９0乃至Ｗ１７0）が開始される。
【０２８５】
復号途中結果格納用RAM1205からの９回の読み出し（Ｒ９1乃至Ｒ１７1）が終了した直後に、次の第１の演算に用いられる検査行列Hの第１３行目から第１５行目までの１に対応する復号途中結果D1201が、復号途中結果格納用RAM1202から９回読み出される（Ｒ１８0乃至Ｒ２６0）。また、復号途中結果格納用RAM1205からの９回の読み出し（Ｒ９1乃至Ｒ１７1）が終了してから時間Ｔｗ後に、復号途中結果格納用RAM1205により復号途中結果D1204の９回の格納（Ｗ９1乃至Ｗ１７1）が開始される。そして、以降同様の処理が繰り返される。
【０２８６】
以上のように、復号途中結果格納用メモリ1103では、検査行列Hの３行分の１に対応する復号途中結果D1102が、４つの復号途中結果格納用RAM1202乃至1205に順に格納されるので、計算部1102が第１の演算を行うために時間Ｔ１が必要な場合であっても、復号途中結果D1103を計算部1102に連続して出力することができる。その結果、計算部1102では、連続して第１の演算を行うことができる。
【０２８７】
図２７は、図２３の復号装置1000の復号処理を説明するフローチャートである。この処理は、例えば、受信用メモリ４１６に復号すべき受信データが格納されたとき、開始される。
【０２８８】
ステップＳ４９において、制御部1105は、復号途中結果格納用RAM1202乃至1205のうちのいずれか１つを読み出しメモリとして選択し、その選択を表す制御信号D11086をスイッチ1206（図２４）に供給する。スイッチ1206は、制御信号D11086に基づいて、復号途中結果格納用RAM1202乃至1205を選択し、その選択した復号途中結果格納用RAM1202乃至1205から３つ単位で供給される復号途中結果D1205乃至D1208を、復号途中結果D1103としてサイクリックシフト回路４１４と計算部1102に供給する。
【０２８９】
ステップＳ４９の処理後は、ステップＳ５０に進み、サイクリックシフト回路４１４は、復号途中結果格納用メモリ1103（のスイッチ1206）から供給される、構成行列の上半分に対応する３つの復号途中結果D1103と下半分に対応する３つの復号途中結果D1103（uj）とを合わせて、サイクリックシフトし、計算部４１５に供給する。
【０２９０】
具体的には、サイクリックシフト回路４１４には、復号途中結果格納用メモリ1103から３つ単位で復号途中結果D1103が供給されるとともに、制御部1105から、その復号途中結果D1103に対応するMatrixデータを表す制御信号D421が供給される。サイクリックシフト回路４１４は、制御信号D421を元に、構成行列の上半分に対応する３つの復号途中結果D1103と下半分に対応する３つの復号途中結果D1103とを合わせて、サイクリックシフトし（並べ替え）、その結果を復号途中結果D414として、計算部４１５に供給する。
【０２９１】
ステップＳ５１において、計算部４１５は、第２の演算を行い、その演算の結果である復号途中結果D415を復号途中結果格納用メモリ1104に供給する。
【０２９２】
具体的には、計算部４１５には、ステップＳ５０でサイクリックシフト回路４１４から６つの復号途中結果D414が供給されるとともに、受信データ用メモリ４１６から６つの受信データD417が供給され、復号途中結果D414と受信データD417が、計算部４１５の計算器４１５1乃至４１５6それぞれに１つずつ供給される。さらに、計算部４１５には、制御部1105から制御信号D422が供給され、その制御信号D422が計算器４１５1乃至４１５6に供給される。
【０２９３】
計算器４１５1乃至４１５6は、復号途中結果D414と受信データD417を用いて、制御信号D422に基づいて、式（５）にしたがって、それぞれ第２の演算を行い、その第２の演算の結果得られる検査行列Hの列に対応する復号途中結果D415(v)を復号途中結果格納用メモリ1104に供給する。
【０２９４】
なお、受信用メモリ４１６から供給された受信データD417に対して、まだ第１の演算が行われておらず、復号途中結果格納用メモリ1103に復号途中結果D1103が格納されていない場合、計算部４１５は、復号途中結果ujを初期値に設定し、第２の演算を行う。
【０２９５】
ステップＳ５１の処理後は、ステップＳ５２に進み、復号途中結果格納用メモリ1104は、ステップＳ５１で計算部４１５から供給された復号途中結果D415(v)を、同一アドレスに格納し、ステップＳ５３に進む。
【０２９６】
ステップＳ５３において、制御部1105は、計算部４１５により、検査行列Hの列に対応する全ての復号途中結果D1104が演算されたかどうかを判定し、全ての復号途中結果D1104が演算されていないと判定した場合、ステップＳ４９に戻り、上述した処理を繰り返す。
【０２９７】
一方、ステップＳ５３において、制御部1105は、計算部４１５により、検査行列Hの列に対応する全ての復号途中結果D1104が演算されたと判定した場合、ステップＳ５４に進み、サイクリックシフト回路1101は、制御部1105から供給される制御信号D1106を元に、復号途中結果格納用メモリ1104から供給される６つの復号途中結果D1104(v)をサイクリックシフトし、その結果を３つ単位で復号途中結果D1101として、計算部1102に供給する。
【０２９８】
ステップＳ５４の処理後は、ステップＳ５５に進み、計算部1102は、第１の演算を行い、その第１の演算の結果である復号途中結果D1102を復号途中結果格納用メモリ1103に供給する。
【０２９９】
具体的には、計算部1102には、ステップＳ５４でサイクリックシフト回路1101から３つの復号途中結果D1101(v)が供給されるとともに、後述するステップＳ５７で既に格納された前回の計算部1102による第１の演算の結果得られた３つの復号途中結果D1102（D1103）(uj)が供給され、その復号途中結果D1101とD1103が、計算部1102の計算器11021乃至11023のそれぞれに１つずつ供給される。さらに、計算部1102には、制御部1105から制御信号D1107が供給され、その制御信号D1107が計算器11021乃至11023に供給される。
【０３００】
計算器11021乃至11023は、それぞれ復号途中結果D1101とD1103を用いて、制御信号D1107に基づいて、式（７）と式（８）にしたがって、それぞれ第１の演算を行い、その第１の演算の結果得られる復号途中結果D1102（uj）を復号途中結果格納用メモリ1103に供給する。
【０３０１】
なお、受信用メモリ４１６から供給された受信データD417に対して、まだ第１の演算が行われておらず、復号途中結果格納用メモリ1103に復号途中結果D1103が格納されていない場合、計算部1102は復号途中結果udvを０に設定する。具体的には、例えば、受信データD417に対する復号を行う前に、復号途中結果格納用メモリ1103が０に初期化されるか、または計算部1102が復号途中結果格納用メモリ1103からの入力を０にマスクする。
【０３０２】
ステップＳ５５の処理後は、ステップＳ５６に進み、制御部1105は、復号途中結果格納用RAM1202乃至1205のうちのいずれか１つを格納メモリとして選択し、その選択を表す制御信号D11081をスイッチ1201（図２４）に供給する。スイッチ1201は、制御信号D11081に基づいて、３つの復号途中結果D1102を格納する復号途中結果格納用RAM1202乃至1205を選択し、その選択した復号途中結果格納用RAM1202乃至1205に、復号途中結果D1102を供給する。
【０３０３】
ステップＳ５６の処理後は、ステップＳ５７に進み、復号途中結果格納用RAM1202乃至1205は、ステップＳ５６でスイッチ1201から供給された３つの復号途中結果D1201乃至D1204(D1102)を、同一のアドレスに格納し、ステップＳ５８に進む。
【０３０４】
ステップＳ５８において、制御部1105は、計算部1102により、検査行列Hの全ての1に対応する復号途中結果D1102が演算されたかどうかを判定し、全ての復号途中結果D1102が演算されていないと判定した場合、ステップＳ５４に戻り、上述した処理を繰り返す。
【０３０５】
一方、ステップＳ５７において、制御部1105は、計算部1102により、全ての１に対応する復号途中結果D1102が演算されたと判定した場合、処理を終了する。
【０３０６】
なお、復号装置1000は、復号回数だけ図２７の復号処理を繰り返し行い、最後の第２の演算の結果得られるメッセージD1104が、最終的な復号結果として出力される。
【０３０７】
上述した図２３の復号装置1000では、計算部1102が３つの計算器11021乃至11023から構成されたが、計算部1102ではなく、計算部415が３つの計算器4151乃至4153から構成されるようにしてもよい。この場合、３つ単位で第２の演算が行われ、復号途中結果格納用メモリ1104が３つ以上の復号途中結果格納用メモリから構成される。また、計算部415と計算部1102の両方が、それぞれ３つの計算器4151乃至4153、計算器11021乃至11023から構成されるようにしてもよい。
【０３０８】
以上のように、図２３の復号装置1000では、復号途中結果格納用メモリ1103が４つの復号途中結果格納用RAM1202乃至1205から構成され、計算部1102が３つ単位で第１の演算を行うので、動作周波数を損なうことなく、回路規模を削減することができる。
【０３０９】
例えば、従来の６つの計算器4121乃至4126を備える復号装置400では、計算器4121乃至4126による第１の演算が必要とするクロック数は72であるが、図２３の復号装置1000では、計算器11021乃至11023による第１の演算が必要とするクロック数は117であり、復号装置400の場合の1.6倍程度である。即ち、計算器11021乃至11023の数を半減させたにも関わらず、クロック数は２倍より小さい値となっている。
【０３１０】
また、計算器4151乃至4156による第２の演算が必要とするクロック数は５９クロックであるため、1回の復号に要する時間は、復号装置400と1000で131（＝72＋59）対176（＝117＋59）となり、復号装置1000の復号に要する時間は、復号装置400に比べて1.3倍程度である。即ち、復号装置1000の動作周波数は、復号装置400に比べて1.3倍程度で済む。
【０３１１】
さらに、第１の演算が必要とするクロック数が小さい場合には、復号装置400と1000における１回の復号に要する時間の比率は小さくなる。例えば、検査行列Hの各行の１の数が４である場合、復号装置400と1000における第１の演算に要する時間の比率は、37対52であり、復号装置1000における時間は、復号装置1000に比べて1.4倍程度となる。
【０３１２】
図２８は、本発明を適用した復号装置1000の第２実施の形態の構成例を示すブロック図である。
【０３１３】
図２８の復号装置1000では、図２３の復号装置1000の受信用メモリ４１６の代わりに、受信用メモリ1400が、復号途中結果格納用メモリ1104の代わりに復号途中結果格納用メモリ1401が、制御部1105の代わりに制御部1402が設けられている。受信用メモリ1400には、制御部1402から受信データ格納用メモリ1502と1503（後述する図２９）のいずれか一方の選択を表す制御信号D1400が供給される。復号途中結果格納用メモリ1401には、制御部1402から復号途中結果格納用メモリ1602と1603(後述する図３０)のいずれか一方の選択を表す制御信号D1401が供給される。
【０３１４】
図２９は、図２８の受信用メモリ1400の構成例を示すブロック図である。
【０３１５】
図２９の受信用メモリ1400は、スイッチ1501と1504、並びに受信データ格納用メモリ1502と1503から構成される。
【０３１６】
スイッチ1501には、通信路を通して受信した受信値（符号ビット）から計算した符号ビットの０らしさの値である受信LLR(対数尤度比)のデータ(受信データ)D416が供給されるとともに、制御部1105から受信データ格納用メモリ1502と1503のいずれか一方の選択を表す制御信号D14001が供給される。スイッチ1501は、制御信号D14001に基づいて、受信データD416を、受信データD1501として受信データ格納用メモリ1502に、または受信データD1502として受信データ格納用メモリ1503に供給する。
【０３１７】
受信データ格納用メモリ1502は、スイッチ1501からの受信データD1501を格納したり、既に格納している受信データD1501を、受信データD1503としてスイッチ1504に供給する。受信データ格納用メモリ1503は、受信データ格納用メモリ1502と同様に、スイッチ1501からの受信データD1502を格納したり、既に格納している受信データD1504をスイッチ1504に供給する。
【０３１８】
なお、受信データ格納用メモリ1502と1503のそれぞれに格納されるデータ量、即ち、受信データ格納用メモリ1502と1503のそれぞれに必要とされる記憶容量は、LDPC符号の符号長と、受信データの量子化ビット数との乗算値である。
【０３１９】
スイッチ1504には、制御部1105から受信データ格納用メモリ1502と1503の一方の選択を表す制御信号D14002が供給され、スイッチ1504は、その制御信号D14002に基づいて、受信データ格納用メモリ1502からの受信データD1503または受信データ格納用メモリ1503からの受信データD1504を、受信データD417としてサイクリックシフト回路1101と計算部４１５に供給する。
【０３２０】
なお、制御信号D14001は、受信データ格納用メモリ1502と1503の一方の選択を表し、制御信号D14002は、他方の選択を表す。即ち、受信データ格納用メモリ1502と1503の一方で書き込みが行われている間、他方で読出しが行われる。
【０３２１】
以上のように、受信用メモリ1400では、２つの受信データ格納用メモリ1502と1503が設けられているので、一方で入力される受信データD416を格納している間に、他方で既に格納されている受信データD417を出力することができる。その結果、受信用メモリ1400では、連続して入力される受信データD416を、受信データD417として連続出力することができる。
【０３２２】
図３０を参照して、図２８の復号途中結果格納用メモリ1401の構成を詳細に説明する。
【０３２３】
図３０の復号途中結果格納用メモリ1401は、スイッチ1601，1604、および1605、並びに復号途中結果格納用メモリ1602と1603から構成される。
【０３２４】
スイッチ1601には、計算部４１５から３つの復号途中結果D415が供給されるとともに、制御部1105から復号途中結果格納用メモリ1602と1603の一方の選択を表す制御信号D14011が供給される。スイッチ1601は、制御信号D14011に基づいて、復号途中結果D415を、復号途中結果D1601として復号途中結果格納用メモリ1602に、または復号途中結果D1602として復号途中結果格納用メモリ1603に供給する。
【０３２５】
復号途中結果格納用メモリ1602は、スイッチ1601からの復号途中結果D1601を格納する。また、復号途中結果格納用メモリ1602は、既に格納してある復号途中結果D1601を、復号途中結果D1603としてスイッチ1604に供給するとともに、復号途中結果D1604としてスイッチ1605に供給する。復号途中結果格納用メモリ1603は、復号途中結果格納用メモリ1602と同様に、スイッチ1601からの復号途中結果D1602を格納する。また、復号途中結果格納用メモリ1602は、既に格納してある復号途中結果D1602を、復号途中結果D1605としてスイッチ1604に供給するとともに、復号途中結果D1606としてスイッチ1605に供給する。
【０３２６】
なお、復号途中結果格納用メモリ1602と1603のそれぞれに格納されるデータ量、即ち、復号途中結果格納用メモリ1602と1603のそれぞれに必要とされる記憶容量は、LDPC符号の符号長と、復号途中結果D415の量子化ビット数との乗算値である。
【０３２７】
スイッチ1604には、制御部1105から復号途中結果格納用メモリ1602と1603の一方の選択を表す制御信号D14012が供給され、スイッチ1604は、その制御信号D14012に基づいて、復号途中結果格納用メモリ1602からの復号途中結果D1603または復号途中結果格納用メモリ1603からの復号途中結果D1605を、復号結果D1402（軟判定値）として出力する。
【０３２８】
スイッチ1605には、制御部1105から復号途中結果格納用メモリ1602と1603の一方の選択を表す制御信号D14013が供給され、スイッチ1605は、その制御信号D14013に基づいて、復号途中結果格納用メモリ1602からの復号途中結果D1604、または復号途中結果格納用メモリ1603からの復号途中結果D1606を、復号途中結果D1403としてサイクリックシフト回路1101に出力する。
【０３２９】
なお、制御信号D14012は、復号途中結果格納用メモリ1602と1603の一方の選択を表し、制御信号D14013は、他方の選択を表す。即ち、復号途中結果格納用メモリ1602と1603の一方に格納されている復号が完了した復号途中結果D1603またはD1605が、復号結果D1402として出力されている間、他方に格納されている復号途中の復号途中結果D1604またはD1606が、復号結果D1403として出力される。
【０３３０】
以上のように、復号途中結果格納用メモリ1401では、２つの復号途中結果格納用メモリ1602と1603が設けられているので、一方で復号途中の復号途中結果D1601またはD1602を格納し、他方で復号が完了した復号途中結果D1601またはD1602を格納することができる。その結果、復号途中結果格納用メモリ1401では、復号結果D1402を出力している間にも復号を行うことができ、これにより、例えば、連続して復号結果D1402を出力することができる。
【０３３１】
図３１は、受信用メモリ1400と復号途中結果格納用メモリ1401の読み出し(出力)と書き込み（格納）の動作を説明するタイミングチャートである。
【０３３２】
なお、図３１において、横軸は時間（ｔ）を表している。また、図３１において、受信データ＃ｉとは、受信用メモリ1400に供給されるｉ番目のフレームの受信データD416を表す。さらに、受信データ＃ｉの復号途中結果D1403を復号途中結果＃ｉと表し、受信データ＃ｉの復号結果D1402を復号結果＃ｉと表す。図３１において、受信データ＃ｉの受信が開始されてから終了するまでの時間に、１つの受信データに対する復号が終了するものとする。
【０３３３】
受信用メモリ1400に受信データ＃２が入力されると、受信データ＃２がすべて入力されるまでの時間Ｔａの間、その受信データ＃２がスイッチ1501を介して、受信用データ格納用メモリ1502に供給され、格納される。このとき、受信データ格納用メモリ1503から、既に格納されている受信データ＃１がスイッチ1504に供給され、スイッチ1504は受信データ＃１をサイクリックシフト回路1101および計算部４１５に出力される。そして、受信データ＃１の復号が行われる。
【０３３４】
また、復号途中結果格納用メモリ1401の復号途中結果格納用メモリ1602は、スイッチ1601を介して計算部４１５から供給される復号途中結果＃１を格納したり、既に格納してある復号途中結果＃１をサイクリックシフト回路1101に供給する。復号途中結果格納用メモリ1603は、スイッチ1604を介して、既に格納してある復号途中結果＃０を、復号結果＃０として出力する。即ち、時間Ｔａの間に復号途中結果格納用メモリ1401から復号途中結果＃０が出力される。
【０３３５】
時間Ｔａの後、受信用メモリ1400に受信データ＃３が入力され、受信データ＃３がすべて入力されるまでの時間Ｔｂの間、その受信データ＃３がスイッチ1501を介して、受信データ格納用メモリ1503に供給され、格納される。このとき、受信データ格納用メモリ1502は、時間Ｔａに格納された受信データ＃２を読み出し、スイッチ1504を介してサイクリックシフト回路1101および計算部４１５に出力する。そして、受信データ＃２の復号が行われる
【０３３６】
また、復号途中結果格納用メモリ1602は、時間Ｔａの間に格納された復号途中結果＃１を、復号結果＃１として出力する。即ち、時間Ｔａの後、時間Ｔｂの間に復号途中結果格納用メモリ1401から復号途中結果＃１が復号結果＃１として出力される。復号途中結果格納用メモリ1603は、スイッチ1601を介して計算部４１５から供給される復号途中結果＃２を格納したり、既に格納してある復号途中結果＃２をサイクリックシフト回路1101に供給する。
【０３３７】
時間Ｔｂの後、受信用メモリ1400に受信データ＃４が入力され、時間Ｔｃの間、時間Ｔａの場合と同様の処理が行われる。即ち、時間Ｔｂの後、時間Ｔｃの間、受信データ＃３がサイクリックシフト回路1101と計算部４１５に供給され、受信データ＃３の復号が行われる。また、時間Ｔｂの間に格納された復号途中結果＃２が、復号途中結果格納用メモリ1603から復号結果＃２として出力される。
【０３３８】
以上のように、図２８の復号装置1000では、連続して入力される受信データD417を順に復号し、その復号結果を連続して出力することができる。これにより、高速で復号を行うことができる。即ち、復号装置1000のスループットが向上する。
【０３３９】
なお、図２９の受信用メモリ1400の受信データ格納用メモリ1502（1503）の数と図３０の復号途中結果格納用メモリ1401の復号途中結果格納用メモリ1602（1603）の数は、２つに限定されない。受信データ格納用メモリ1502と復号途中結果格納用メモリ1602の数を増加させることにより、復号の繰り返し回数を増加させ、復号性能を改善することができる。
【０３４０】
例えば、受信データ格納用メモリ1502と復号途中結果格納用メモリ1602が、それぞれ３つずつ設けられる場合、１つの受信データ格納用メモリ1502を受信データD417の格納用に、１つの復号途中結果格納用メモリ1602を復号結果D1402の出力用に用い、残りの２つの受信データ格納用メモリ1502と復号途中結果格納用メモリ1602を復号用に用いることができる。この場合、計算部415と1102を２つずつ設ける必要があり、回路規模は増大するが、復号の繰り返し回数を２倍多くすることができる。
【０３４１】
図３２は、本発明を適用した復号装置1000の第３実施の形態の構成例を示すブロック図である。
【０３４２】
図３２の復号装置1000では、図２８の復号装置1000の復号途中結果格納用メモリ1401の代わりに、復号途中結果格納用メモリ1701が、制御部1402の代わりに、制御部1799が設けられている。復号途中結果格納用メモリ1701には、復号途中結果格納用メモリ1701の復号硬判定結果格納用メモリ1802と1803（後述する図３３）のいずれか一方の選択を表す制御信号D1701が供給される。復号途中結果格納用メモリ1701は、復号が完了した復号途中結果D415の硬判定値を復号結果D1702として出力し、復号途中の復号途中結果D415の軟判定値を復号途中結果D1703とし出力する。
【０３４３】
図３３は、図３２の復号途中結果格納用メモリ1701の構成例を示すブロック図である。
【０３４４】
図３２の復号途中結果格納用メモリ1701は、スイッチ1801，1805、および1806、復号硬判定結果格納用メモリ1802と1803、並びに復号軟判定結果格納用メモリ1804から構成される。
【０３４５】
スイッチ1801には、計算部４１５から３つの復号途中結果D415の硬判定値が復号硬判定結果D1801として供給されるとともに、制御部1702から復号硬判定結果格納用メモリ1801と1802の一方の選択を表す制御信号D17011が供給される。スイッチ1801は、制御信号D17011に基づいて、復号硬判定結果D1801を、復号硬判定結果D1803として復号硬判定結果格納用メモリ1802に、または復号硬判定結果D1804として復号硬判定結果格納用メモリ1803に供給する。
【０３４６】
復号硬判定結果格納用メモリ1802は、スイッチ1801からの復号途中結果D1803を格納しする。また、復号硬判定結果格納用メモリ1802は、既に格納してある復号途中結果D1803を、復号途中結果D1805としてスイッチ1805に供給するとともに、復号途中結果D1807としてスイッチD1806に供給する。
【０３４７】
復号途中結果格納用メモリ1803は、復号途中結果格納用メモリ1802と同様に、スイッチ1801からの復号途中結果D1804を格納する。また、復号途中結果格納用メモリ1803は、既に格納してある復号途中結果D1804を、復号途中結果D1806としてスイッチ1805に供給するとともに、復号途中結果D1808としてスイッチ1806に供給する。
【０３４８】
なお、復号硬判定結果格納用メモリ1802と1803のそれぞれに格納されるデータ量、即ち、復号硬判定結果格納用メモリ1802と1803のそれぞれに必要とされる記憶容量は、LDPC符号の符号長と、復号途中結果D415の硬判定値のビット数である１ビットとの乗算値である。
【０３４９】
復号軟判定結果格納用メモリ1804には、計算部４１５から３つの復号途中結果D415の上位１ビットを除く軟判定値が復号軟判定結果D1802として供給される。復号軟判定結果格納用メモリ1804は、復号軟判定結果D1802を格納したり、既に格納してある復号軟判定結果D1802を復号軟判定結果D1811として出力する。
【０３５０】
なお、復号軟判定結果格納用メモリ1804に格納されるデータ量、即ち復号軟判定結果格納用メモリ1804に必要とされる記憶容量は、LDPC符号の符号長と、軟判定値の上位１ビットを除く値のビット数（復号途中結果D415の量子化ビット数−１）との乗算値である。
【０３５１】
スイッチ1805には、制御部1702から復号硬判定結果格納用メモリ1802と1803の一方の選択を表す制御信号D17012が供給され、スイッチ1805は、その制御信号D17012に基づいて、復号硬判定結果格納用メモリ1802からの復号硬判定結果D1805または復号途中結果格納用メモリ1803からの復号硬判定結果D1806を、復号結果D1702（硬判定値）として出力する。
【０３５２】
スイッチ1806には、制御部1702から復号硬判定結果格納用メモリ1802と1803の一方の選択を表す制御信号D17013が供給され、スイッチ1805は、その制御信号D17013に基づいて、復号硬判定結果格納用メモリ1802からの復号硬判定結果D1807または復号硬判定結果格納用メモリ1803からの復号途中結果D1808を、復号硬判定結果D1810として出力する。スイッチ1806からの復号硬判定結果D1810を上位１ビットとし、その下位ビットを復号軟判定結果格納用メモリ1804からの復号軟判定結果D1811とすることにより得られる軟判定値が、復号途中結果D1703としてサイクリックシフト回路1101に出力される。
【０３５３】
なお、制御信号D17012は、復号途中結果格納用メモリ1802と1803の一方の選択を表し、制御信号D17013は、他方の選択を表す。即ち、復号途中結果格納用メモリ1802と1803の一方に格納されている復号が完了した復号途中結果D1805またはD1806が、復号結果D1702として出力されている間、他方に格納されている復号途中の復号途中結果D1807またはD1808が、復号硬判定結果D1810として出力される。
【０３５４】
以上のように、復号途中結果格納用メモリ1701では、復号途中結果D415の硬判定値を２つの復号硬判定結果格納用メモリ1802と1803に格納し、復号途中結果D415の上位１ビットを除く軟判定値を１つの復号軟判定結果格納用メモリ1804に格納するので、復号途中結果格納用メモリ1701は、LDPC符号の符号長と１ビットとの乗算値の２倍と、LDPC符号の符号長と（復号途中結果D415の量子化ビット数−１）との乗算値とを合計した記録容量を有すればよい。
【０３５５】
従って、復号途中結果格納用メモリ1701を有する図３２の復号装置1000では、LDPC符号の符号長と、復号途中結果D415の量子化ビット数との乗算値の２倍の記憶容量が必要である復号途中結果格納用メモリ1401を有する図２８の復号装置に比べて、回路規模を削減することができる。
【０３５６】
図３４は、本発明を適用した復号装置1000の第４実施の形態の構成例を示すブロック図である。
【０３５７】
図３４の復号装置1000は、３つのシンドローム判定器20011乃至20013からなるシンドローム判定部2001を設け、サイクリックシフト回路2000から出力される硬判定結果D2000のシンドローム演算を行い、その演算の結果に基づいて復号を終了する。
【０３５８】
サイクリックシフト回路2000は、制御信号D1106を元に、６つの復号途中結果D1104または受信データD417を選択し、並べ替えるサイクリックシフトを行い、その結果のうち、構成行列の上半分（１行目乃至３行目分）または下半分（４行目乃至６行目分）の１に対応する３つを復号途中結果D1999として、計算部４１２に供給する。また、サイクリックシフト回路2000は、６つの復号途中結果D1104または受信データD417をサイクリックシフトした結果の硬判定値を硬判定結果D2000としてシンドローム判定部2000に供給する。
【０３５９】
シンドローム判定部2001は、３つのシンドローム判定器20011乃至20013から構成される。シンドローム判定部2001には、サイクリックシフト回路2000から出力される硬判定結果D2000が供給されるとともに、制御部2003からシンドロームの演算を制御する制御信号D2001が供給され、シンドローム判定器20011乃至20013にそれぞれ供給される。
【０３６０】
シンドローム判定器20011乃至20013は、それぞれ制御信号D2001に基づいて、硬判定結果D2000のシンドロームの計算を行う。具体的には、シンドローム判定器20011乃至20013は、検査行列Hの行に対応する硬判定結果D2000の排他的論理和（EXOR）を計算し、その結果得られる値が、すべての行において０であるかどうかを判定する。シンドローム判定器20011乃至20013は、その判定結果D2002を制御部2003に供給する。
【０３６１】
なお、シンドローム判定部2001によるシンドロームの演算と計算部1102による第１の演算は、同時に行われるようにしてもよい。
【０３６２】
制御部2003は、シンドローム判定部2000から供給される判定結果D2002に応じて、復号を終了する。具体的には、制御部2003は、判定結果D2002に応じて、復号途中結果格納用メモリ2002に、復号途中結果D415または復号結果D1105を復号結果として出力させる制御信号D2003を供給する。復号途中結果格納用メモリ2002は、制御部2003からの制御信号D2003に基づいて、既に格納してある復号途中結果D415または復号結果D1105を復号結果として出力するか、または復号途中結果D415をサイクリックシフト回路2000に供給する。
【０３６３】
図３５は、図３４の復号装置1000の復号処理を説明するフローチャートである。この処理は、例えば、受信用メモリ４１６に復号すべき受信データD416が格納されたとき、開始される。
【０３６４】
ステップＳ７１において、制御部2003は、カウント値Ｋを０に設定し、ステップＳ７２に進む。ステップＳ７２において、シンドローム判定部2001（のシンドローム判定器20011乃至20013）は、サイクリックシフト回路2000から供給される硬判定結果D2000のシンドロームを演算する。なお、最初のステップＳ７２では、シンドローム判定部2001には、受信データD417がサイクリックシフトされた結果の硬判定値である硬判定結果D2000が供給され、シンドローム判定部2001は、受信データD417の硬判定結果D2000のシンドロームを演算する。
【０３６５】
ステップＳ７２の処理後は、ステップＳ７３に進み、制御部2003は、シンドローム判定部2001から供給される判定結果D2002に基づいて、シンドロームが０であるかどうかを判定し、シンドロームが０ではないと判定された場合、ステップＳ７４に進む。
【０３６６】
ステップＳ７４において、制御部2003は、カウント値Ｋが所定の回数Ｎ以上であるかどうかを判定し、所定の回数Ｎ以上ではないと判定した場合、ステップＳ７５に進む。
【０３６７】
ステップＳ７５乃至Ｓ８４の処理は、図２７のステップＳ４９乃至Ｓ５８の処理と同様であるので、説明は省略する。
【０３６８】
ステップＳ８４の処理後は、ステップＳ８５に進み、制御部2003は、カウント値Ｋを１つだけインクリメントし、ステップＳ７２に戻る。
【０３６９】
ステップＳ７３において、シンドロームが０であると判定された場合、ステップＳ８６に進み、制御部2003は復号を終了し、復号途中結果格納用メモリ2002に格納されている復号途中結果D415または復号結果D1105を復号結果として出力する。なお、最初のステップＳ７１でシンドロームが０であると判定された場合、復号が１度も行われず、計算部４１５に供給される受信データD417（復号結果D1105）が、復号途中結果格納用メモリ2002を介して、そのまま復号結果として出力される。
【０３７０】
また、ステップＳ７４において、カウント値Ｋが所定の回数Ｎ以上であると判定された場合にも、ステップＳ８６に進み、制御部2003は復号を終了し、復号途中結果格納用メモリ2002に格納されている復号途中結果D415を復号結果として出力する。
【０３７１】
以上のように、図３５の復号処理では、シンドロームが０になる場合、またはカウント値Ｋが所定の回数Ｎ以上になる場合（Ｎ回復号が行われた場合）、復号が終了される。これにより、シンドロームが０、即ち誤り数が０である復号途中結果D415がさらに復号されて、誤り数が再び増加することを防止することができる。また、受信データD416のSN（Signal Noise）比が大きい場合、復号性能を劣化させずに、復号回数を抑えることができるので、復号装置1000の消費電力を低減することができる。
【０３７２】
なお、シンドローム判定部2001の回路規模は一般的に小さく、シンドローム判定部2001を設けることによる復号装置1000の回路規模の増加は無視することができる程度に小さい。
【０３７３】
また、図３４の復号装置1000では、図２３の復号装置1000にシンドローム判定部2001が設けられたが、第１の演算と第２の演算によって復号を行う装置であれば、どのような装置にシンドローム判定部2001が設けられるようにしてもよい。例えば、図１７の復号装置400、もしくは図２８または図３２の復号装置1000にシンドローム判定部2001が設けられるようにしてもよい。
【０３７４】
本実施の形態では、復号途中結果格納メモリ1103は、４つの復号途中結果格納用RAM1202乃至1205から構成されるようにしたが、復号途中結果格納用RAM1202乃至1205の数は３つ以上であればどのような数であってもよい。復号途中結果格納用RAM1202乃至1205の数が増加すればするほど、復号装置の動作速度を速めることができる。
【０３７５】
また、図２３、図２８、および図３２の復号装置1000では、第１の演算と第２の演算を繰り返し行うことにより復号を行ったが、チェックノード演算とバリアブルノード演算を繰り返し行うことにより復号を行うようにすることもできる。
【０３７６】
なお、図２４の復号途中結果格納用RAM1202乃至1205、図２９の受信データ格納用メモリ1502と1503、図３０の復号途中結果格納用メモリ1602と1603、図３３の復号硬判定結果格納用メモリ1802と1803、並びに復号軟判定結果格納用メモリ1804は、例えば、RAMの物理的なビットが足りない場合には、複数のRAMを用いて同じ制御信号を与えることで、論理的に１つのRAMとみなすことができる。
【０３７７】
上述の場合には、説明を簡単にするために、Pが６の場合、即ち、検査行列Hを構成する構成行列の行数および列数が６の場合を例に挙げたが、構成行列の行数および列数Pは必ずしも６である必要はなく、検査行列Hによって異なる値を取ることもあり得る。例えば、Pは３６０や３９２であってもよい。
【０３７８】
また、本実施の形態では、符号長108、符号化率2/3のLDPC符号を用いたが、LDPC符号の符号長や符号化率は、どのような値であってもよい。例えば、構成行列の行数および列数Pが６の場合、枝総数が６以下であれば、どのような符号長、符号化率のLDPC符号でも、制御信号を代えるだけで、復号装置1000を用いて復号可能である。
【０３７９】
さらに、構成行列の行数および列数Pが所定の値で、枝の総数がある値以下、という条件を満たす、あるLDPC符号の復号装置は、その条件を満たす、任意の符号長で、任意の符号化率のLDPC符号を復号することができる。
【０３８０】
検査行列Hが、構成行列の行数および列数Pの倍数でない場合は、検査行列Hの端数の外側にすべて０(all 0)の成分を付けてPの倍数とみなして適用することができる場合がある。
【０３８１】
上述した復号装置1000では、計算部1102の計算器11021乃至11023の数をP/2（＝３）としたが、計算器11021乃至11023の数はP未満であればよい。なお、Pが大きな素数である場合においても、計算器11021乃至11023の数をPの整数部の１に近い整数個にすればよい。
【０３８２】
以上のように、P×Pの単位行列、そのコンポーネントの１のうち１個以上が０になった準単位行列、単位行列もしくは準単位行列をサイクリックシフトしたシフト行列、単位行列、準単位行列、もしくはシフト行列の複数の和である和行列、P×Pの０行列の組み合わせで表すことができる検査行列Hを持つLDPC符号の復号を、第１と第２の演算をP個またはN個（NはP未満の正の整数）同時に行うアーキテクチャ(architecture)を採用することにより、第１と第２の演算を、P個またはN個同時に行うことで動作周波数を実現可能な範囲に抑えることができ、多数の繰り返し復号を行うことを可能にしつつ、メモリ（FIFOやRAM）への書き込みと読み出し時に、異なるアドレスへの同時アクセスが起きることを防止することができる。
【０３８３】
また、第１または第２の演算をN個同時に行うことにより、第１と第２の演算をP個同時に行う場合に比べて、第１の演算を行う計算部1102を構成する計算器11021乃至11023または第２の演算を行う計算部415を構成する計算器４１５1乃至４１５6の数を削減し、回路規模を削減することができる。
【０３８４】
さらに、シンドローム判定部2000が、第２の演算の結果得られる復号途中結果の硬判定値である硬判定結果D2000のシンドロームの演算を行い、制御部2003が、そのシンドロームに基づいて、復号を終了させるので、復号の性能を向上させ、さらに消費電力を削減することができる。
【０３８５】
一般的に、LDPC符号は符号長が数千から数万と大きいため、Pの値も数百の大きさを持つものが使われる。その場合には、更に本発明に係る復号装置を用いる効果は大きくなる。
【０３８６】
また、本発明に係る復号装置は、サムプロダクトアルゴリズムを忠実に実装するものであるため、メッセージの量子化以外の復号損失が起きることはない。
【０３８７】
以上の観点から、本発明に係る復号装置を用いることで、高性能な復号が可能になる。
【０３８８】
なお、上述したLDPC符号を復号する復号装置は、例えば、（ディジタル）衛星放送を受信するチューナなどに適用することができる。
【図面の簡単な説明】
【０３８９】
【図１】LDPC符号の検査行列Hを説明する図である。
【図２】パリティ部が下三角行列になっている検査行列Hを示す図である。
【図３】LDPC符号の復号手順を説明するフローチャートである。
【図４】メッセージの流れを説明する図である。
【図５】LDPC符号の検査行列Hの例を示す図である。
【図６】検査行列Hのタナーグラフを示す図である。
【図７】バリアブルノードを示す図である。
【図８】チェックノードを示す図である。
【図９】LDPC符号の検査行列Hの例を示す図である。
【図１０】ノード演算を１つずつ行うLDPC符号の復号装置の構成例を示すブロック図である。
【図１１】図１０のチェックノード計算器の構成例を示すブロック図である。
【図１２】図１０のバリアブルノード計算器の構成例を示すブロック図である。
【図１３】ノード演算を全て同時に行うLDPC符号の復号装置の構成例を示すブロック図である。
【図１４】図１３のチェックノード計算器の構成例を示すブロック図である。
【図１５】図１３のバリアブルノード計算器の構成例を示すブロック図である。
【図１６】６×６単位に分割した検査行列Hを示す図である。
【図１７】ノード演算を６個同時に行う復号装置の構成例を示すブロック図である。
【図１８】図１７のチェックノード計算器の構成例を示すブロック図である。
【図１９】図１７のバリアブルノード計算器の構成例を示すブロック図である。
【図２０】図１７の復号途中結果格納用メモリの構成例を示すブロック図である。
【図２１】図１７の復号途中結果格納用RAMの動作を説明するタイミングチャートである。
【図２２】復号途中結果に対応する構成行列の位置を示す図である。
【図２３】本発明を適用した復号装置の第１実施の形態の構成例を示すブロック図である。
【図２４】図２３の復号途中結果格納メモリの構成例を示すブロック図である。
【図２５】図２４の復号途中結果格納用RAMの動作を説明するタイミングチャートである。
【図２６】復号途中結果に対応する構成行列の位置を示す図である。
【図２７】図２３の復号装置の復号処理を説明するフローチャートである。
【図２８】本発明を適用した復号装置の第２実施の形態の構成例を示すブロック図である。
【図２９】図２８の受信用メモリの構成例を示すブロック図である。
【図３０】図２８の復号途中結果格納用メモリの構成例を示すブロック図である。
【図３１】受信用メモリと復号途中結果格納用メモリの動作を説明するタイミングチャートである。
【図３２】本発明を適用した復号装置の第３実施の形態の構成例を示すブロック図である。
【図３３】図３２の復号途中結果格納用メモリの構成例を示すブロック図である。
【図３４】本発明を適用した復号装置の第４実施の形態の構成例を示すブロック図である。
【図３５】図３４の復号装置の復号処理を説明するフローチャートである。
【符号の説明】
【０３９０】
４１４  サイクリックシフト回路，  ４１５  計算部，  ４１６  受信用メモリ，  １０００  復号装置，  １１０１  サイクリックシフト回路，  １１０２  計算部，  １１０３，１１０４  復号途中結果格納用メモリ，  １１０５  制御部，  １２０２乃至１２０５  復号途中結果格納用RAM,  １４９９  制御部，  １５００  受信用メモリ，  １６００  復号途中結果格納用メモリ，  １５０２，１５０３  受信データ格納用メモリ，  １６０２，１６０３  復号途中結果格納用メモリ，  １７９９  制御部，  １８００  復号途中結果格納用メモリ，  １８０１，１８０２  復号硬判定結果格納用メモリ，  １８０３  復号軟判定結果格納用メモリ，  ２０００  サイクリックシフト回路，  ２００１  シンドローム判定部，  ２００２  復号途中結果格納用メモリ，  ２００３  制御部
【図１】
2006304131.tif 000011
【図２】
2006304131.tif 000012
【図３】
2006304131.tif 000013
【図４】
2006304131.tif 000014
【図５】
2006304131.tif 000015
【図６】
2006304131.tif 000016
【図７】
2006304131.tif 000017
【図８】
2006304131.tif 000018
【図９】
2006304131.tif 000019
【図１０】
2006304131.tif 000020
【図１１】
2006304131.tif 000021
【図１２】
2006304131.tif 000022
【図１３】
2006304131.tif 000023
【図１４】
2006304131.tif 000024
【図１５】
2006304131.tif 000025
【図１６】
2006304131.tif 000026
【図１７】
2006304131.tif 000027
【図１８】
2006304131.tif 000028
【図１９】
2006304131.tif 000029
【図２０】
2006304131.tif 000030
【図２１】
2006304131.tif 000031
【図２２】
2006304131.tif 000032
【図２３】
2006304131.tif 000033
【図２４】
2006304131.tif 000034
【図２５】
2006304131.tif 000035
【図２６】
2006304131.tif 000036
【図２７】
2006304131.tif 000037
【図２８】
2006304131.tif 000038
【図２９】
2006304131.tif 000039
【図３０】
2006304131.tif 000040
【図３１】
2006304131.tif 000041
【図３２】
2006304131.tif 000042
【図３３】
2006304131.tif 000043
【図３４】
2006304131.tif 000044
【図３５】
2006304131.tif 000045