(57)【要約】【課題】LDPC符号を復号する場合において、回路規模を削減する。【解決手段】入力バッファ５１３は、間欠的に入力されるLDPC符号の受信値を一時的に記憶し、記憶している受信値を連続的に読み出す。受信値格納用メモリ５１４は、入力バッファ５１３により連続的に読み出される受信値を記憶し、記憶している受信値を６つ単位で読み出す。計算器は、受信値格納用メモリ５１４により６つ単位で読み出された受信値を、６つ単位で復号する。なお、入力バッファ５１３のビット幅は、受信値格納用メモリ５１４のビット幅より小さい。本発明は、例えば、衛星放送を受信するチューナに適用できる。【選択図】図１８
2008278191.tif 000002
【特許請求の範囲】
【請求項１】
LDPC(Low Density Parity Check)符号を復号する復号装置であって、
間欠的に入力される前記LDPC符号の受信値を一時的に記憶し、記憶している前記受信値を連続的に読み出す第１の記憶手段と、
前記第１の記憶手段により連続的に読み出される受信値を記憶し、記憶している前記受信値を所定の単位ごとに読み出す第２の記憶手段と、
前記第２の記憶手段により所定の単位ごとに読み出された受信値を、前記所定の単位ごとに復号する復号手段と
を備え、
前記第１の記憶手段のビット幅は、前記第２の記憶手段のビット幅より小さい
復号装置。
【請求項２】
前記第１の記憶手段から前記受信値が読み出され、その受信値が前記第２の記憶手段に記憶される転送時間は、前記LDPC符号の符号語単位の受信値内の値のない時間である無効時間以内である
請求項１に記載の復号装置。
【請求項３】
前記第１の記憶手段は、前記受信値を前記符号語単位で読み出す
請求項２に記載の復号装置。
【請求項４】
前記間欠的に入力されるLDPC符号の受信値を前記転送時間に一時的に記憶する第３の記憶手段
をさらに備え、
前記第１の記憶手段は、前記第３の記憶手段から連続的に読み出された受信値または前記間欠的に入力されるLDPC符号の受信値を一時的に記憶する
請求項３に記載の復号装置。
【請求項５】
前記第１の記憶手段は、前記受信値を前記符号語単位で読み出す前に、前回の読み出し対象である受信値の復号の終了を要求する復号終了要求信号を前記復号手段に供給し、その後、所定の時間経過後に、前記受信値を前記符号語単位で読み出し、
前記復号手段は、前記復号終了要求信号に応じて、前記前回の読み出し対象である受信値の復号を終了し、
前記所定の時間と前記転送時間の和は、前記無効時間以内である
請求項３に記載の復号装置。
【請求項６】
前記間欠的に入力されるLDPC符号の受信値を、前記転送時間と前記所定の時間に一時的に記憶する第３の記憶手段
をさらに備え、
前記第１の記憶手段は、前記第３の記憶手段から連続的に読み出された受信値または前記間欠的に入力されるLDPC符号の受信値を一時的に記憶する
請求項５に記載の復号装置。
【請求項７】
間欠的に入力されるLDPC符号の受信値を一時的に記憶する第１の記憶手段と、前記第１の記憶手段により連続的に読み出される受信値を記憶する第２の記憶手段と、前記第２の記憶手段により所定の単位ごとに読み出された受信値を、前記所定の単位ごとに復号する復号手段とを備え、前記LDPC符号を復号する復号装置の復号方法であって、
前記第２の記憶手段よりビット幅が小さい前記第１の記憶手段が、前記間欠的に入力されるLDPC符号の受信値を一時的に記憶し、
前記第１の記憶手段が、記憶している前記受信値を連続的に読み出し、
前記第２の記憶手段が、前記第１の記憶手段により連続的に読み出される受信値を記憶し、
前記第２の記憶手段が、記憶している前記受信値を前記所定の単位ごとに読み出し、
前記復号手段が、前記第２の記憶手段により所定の単位ごとに読み出された受信値を、前記所定の単位ごとに復号する
ステップを含む復号方法。
【請求項８】
LDPC(Low Density Parity Check)符号を復号する復号装置であって、
間欠的に入力される前記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による非特許文献１において最初に提案されたものであり、その後、非特許文献２等において再注目されるに至ったものである。
【０００５】
LDPC符号は、近年の研究により、ターボ符号等と同様に、符号長を長くしていくにしたがって、シャノン限界に近い性能が得られることがわかりつつある。また、LDPC符号は、最小距離が符号長に比例するという性質があることから、その特徴として、ブロック誤り確率特性がよく、さらに、ターボ符号等の復号特性において観測される、いわゆるエラーフロア現象が殆ど生じないことも利点として挙げられる。
【０００６】
以上のような利点により、LDPC符号にBCH符号が連接された誤り訂正方式が、ETSI(European Telecommunication Standard Institute)により規格化されたDVB-S2（Digital Video Broadcasting S2）規格等にも採用され、DVB-S2規格は、この誤り訂正方式と、8PSK（8-Phase Shift Keying）以上の多値変調とが組み合わされた規格となっている。また、受信機の性能が同一である場合、DVB-S2規格では、畳み込み符号とリードソロモン符号を連接した方式を採用するDVB-S規格に対して、帯域あたりの伝送容量が25%から30%程度に向上されることが見込まれている。
【０００７】
ところで、LDPC符号の復号は、Gallagerが確率復号(Probabilistic Decoding)と称して提案したアルゴリズムであって、バリアブルノード(variable node（メッセージノード(message node)とも呼ばれる。）)と、チェックノード(check node)とからなる、いわゆるタナーグラフ(Tanner graph)上での確率伝播(belief propagation)によるメッセージ・パッシング・アルゴリズムによって行うことが可能である。なお、以下、適宜、バリアブルノードとチェックノードを、単に、ノードともいう。
【０００８】
しかしながら、確率復号においては、各ノード間で受け渡されるメッセージが実数値であることから、解析的に解くためには、連続した値をとるメッセージの確率分布そのものを追跡する必要があり、非常に困難を伴う解析を必要とすることになる。そこで、Gallagerは、LDPC符号の復号アルゴリズムとして、アルゴリズムＡ又はアルゴリズムＢを提案している。
【０００９】
LDPC符号の復号は、一般的には、図１に示すような手順にしたがって行われる。なお、ここでは、フレーム単位でLDPC符号化されたLDPC符号を受信値U0とし、チェックノードから出力されるメッセージをujとし、バリアブルノードから出力されるメッセージをviとする。メッセージとは、値の"0"らしさを、いわゆる対数尤度比(log likelihood ratio)で表現した実数値である。また、ここでは、受信値U0の"0"らしさの対数尤度比を、受信値u0iと表すこととする。
【００１０】
まず、LDPC符号の復号においては、図１に示すように、ステップＳ１１において、受信値U0(受信値u0i)が受信され、メッセージujが"0"に初期化されるとともに、繰り返し処理のカウンタとしての整数をとる変数kが"0"に初期化される。ステップＳ１２において、受信値u0iに基づいて、式（１）に示す演算を行うことによってメッセージviが求められ、さらに、このメッセージviに基づいて、式（２）に示す演算を行うことによってメッセージujが求められる。
【００１１】
【数１】
2008278191.tif 000003
・・・（１）
【００１２】
【数２】
2008278191.tif 000004
・・・（２）
【００１３】
なお、式（１）と式（２）におけるdvとdcは、それぞれ、検査行列Hの縦方向（行方向）と横方向（列方向）の"1"の個数を示す任意に選択可能とされるパラメータであり、例えば、(3,6)符号の場合には、dv=3，dc=6となる。
【００１４】
また、式（１）または（２）の演算においては、それぞれ、メッセージを出力しようとする枝(edge)から入力されたメッセージを、和または積演算のパラメータとしては用いないことから、和または積演算の範囲が、１乃至dv-1または１乃至dc-1となっている。さらに、式（２）に示す演算は、実際には、２入力v1，v2に対する１出力で定義される式（３）に示す関数R(v1,v2)のテーブルを予め作成しておき、これを式（４）に示すように連続的（再帰的）に用いることによって行われる。
【００１５】
【数３】
2008278191.tif 000005
・・・（３）
【００１６】
【数４】
2008278191.tif 000006
・・・（４）
【００１７】
ステップＳ１２では、さらに、変数kが"1"だけインクリメントされる。ステップＳ１３では、変数kが所定の繰り返し復号回数N以上であるか否かが判定される。ステップＳ１３において、変数kがN以上ではないと判定された場合、処理はステップＳ１２に戻り、以下、同様の処理が繰り返される。
【００１８】
一方、ステップＳ１３において、変数kがN以上であると判定された場合、ステップＳ１４において、式（５）に示す演算を行うことによって、最終的に出力する復号結果としてのメッセージvが求められて出力され、LDPC符号の復号処理が終了する。
【００１９】
【数５】
2008278191.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のタナーグラフとなっている。
【００２４】
確率伝播（Belief Propagation）、サムプロダクトアルゴリズム(Sum Product Algorithm)等と呼ばれるLDPC符号の復号方法は、バリアブルノードの演算とチェックノードの演算とを繰り返し行う。
【００２５】
バリアブルノードでは、図５のように、式（１）の演算を行う。すなわち、図５において、計算しようとしている枝に対応するメッセージviは、バリアブルノードに繋がっている残りの枝からのメッセージu1およびu2と、受信情報u0iを用いて計算される。他の枝に対応するメッセージも同様に計算される。
【００２６】
チェックノードの演算について説明する前に、式（２）を、式a×b=exp{ln(|a|)+ln(|b|)}×sign(a)×sign(b)の関係を用いて、式（６）のように書き直す。但し、sign(x)は、x≧0のとき1であり、x＜0のとき-1である。
【００２７】
【数６】
2008278191.tif 000008
・・・（６）
【００２８】
更に、x≧0において、φ(x)=−ln(tanh(x/2))と定義すると、φ-1(x)=2tanh-1(e-x)であるから、式（６）は、式（７）のように書くことができる。
【００２９】
【数７】
2008278191.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では、０を、"."で表現している。
【００３５】
図８は、各ノードの演算を１つずつ順次行う復号装置の構成例を示している。
【００３６】
図８の復号装置では、動作クロックの１クロック(clock)ごとに、１つの枝に対応するメッセージが計算される。
【００３７】
即ち、図８の復号装置は、２つの枝用メモリ１００および１０２、１つのチェックノード計算器１０１、１つのバリアブルノード計算器１０３、１つの受信用メモリ１０４、１つの制御部１０５からなる。
【００３８】
図８の復号装置では、枝用メモリ１００または１０２からメッセージデータが１つずつ読み出され、そのメッセージデータを用いて、所望の枝に対応するメッセージデータが計算される。そして、その計算によって求められたメッセージデータが１つずつ後段の枝用メモリ１０２または１００に格納されていく。繰り返し復号を行うことにより、高い誤り訂正能力を実現する際には、この１回復号を行う図８の復号装置を複数個縦列に連接するか、もしくは図８の復号装置を繰り返し用いることによって、繰り返し復号を実現する。なお、ここでは、例えば、図８の復号装置が複数個接続されているものとする。
【００３９】
枝用メモリ１００は、前段の復号装置（図示せず）のバリアブルノード計算器１０３から供給されるメッセージD100を、後段のチェックノード計算器１０１が読み出す順番に格納していく。そして、枝用メモリ１００は、チェックノード計算のフェーズでは、メッセージD100を、格納してある順番通りに、メッセージD101として、チェックノード計算器１０１に供給する。
【００４０】
チェックノード計算器１０１は、制御部１０５から供給される制御信号D106に基づき、枝用メモリ１００から供給されるメッセージD101を用いて、式（７）に従って演算を行い、その演算によって求められたメッセージD102を、後段の枝用メモリ１０２に供給する。
【００４１】
枝用メモリ１０２は、前段のチェックノード計算器１０１から供給されるメッセージD102を、後段のバリアブルノード計算器１０３が読み出す順番に格納していく。そして、枝用メモリ１０２は、バリアブルノード計算のフェーズでは、メッセージD102を、格納してある順番通りに、メッセージD103として、バリアブルノード計算器１０３に供給する。
【００４２】
さらに、バリアブルノード計算器１０３には、制御部１０５から制御信号D107が供給されるとともに、受信用メモリ１０４から受信値D104が供給される。バリアブルノード計算器１０３は、制御信号D107に基づき、枝用メモリ１００から供給されるメッセージD103と受信用メモリ１０４から供給される受信値D104を用い、式（１）に従って演算を行い、その演算の結果得られるメッセージD105を、図示せぬ後段の復号装置の枝用メモリ１００に供給する。
【００４３】
受信用メモリ１０４には、通信路を通して受信されたLDPC符号から計算された、符号ビットの０らしさを表す受信LLR(対数尤度比)である受信値D108を受信し、格納する。なお、LDPC符号は、フレーム単位でLDPC符号化されている。受信用メモリ１０４は、格納している受信値D108を読み出し、受信値D104としてバリアブルノード計算器１０３に供給する。
【００４４】
制御部１０５は、バリアブルノード演算を制御する制御信号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個の符号からなる１フレーム分の符号語を、受信値として受信する間に、646×50=32300クロック動作することが必要であり、受信周波数の約３００（≒32300/108）倍の高速動作が必要になる。受信周波数が数十MHzであるとすると、GHz以上の速度での動作を要求されることになる。
【００７８】
また、図８の復号装置を、例えば、５０台連接して、LDPC符号を復号する場合には、１フレーム目のバリアブルノード演算を行っている間に、２フレーム目のチェックノード演算を行い、３フレーム目のバリアブルノード演算を行う、というように、複数のバリアブルノード演算とチェックノード演算とを同時に行うことができる。この場合、108個の符号を受信する間に、323個の枝を計算すればよいので、復号装置は、受信周波数の約３（≒323/108）倍の周波数で動作すればよいことになり、十分に実現可能である。しかしながら、この場合、回路規模が、単純には、図８の復号装置の５０倍になる。
【００７９】
そこで、図８の復号装置の他に、４つずつのメッセージの計算を同時に行う実装方法について、例えば、非特許文献３に述べられているが、この場合、メモリの異なるアドレスからの同時読み出し、もしくは同時書き込みを避けることが一般的には容易でなく、メモリアクセス制御が困難であるという問題がある。
【００８０】
この問題を解決するため、例えば、非特許文献４、“非特許文献５などに、ランダムな符号ではなく、部分的にパラレルな復号器の実装に親和性の高い符号および復号装置について報告されている。しかしながら、非特許文献４や５などに記載されている復号装置の実現方法は特定の符号のみに対応するものであり、１つの復号器で様々な符号長、符号化率の符号を復号することは困難である。
【００８１】
また、Ｐ×Ｐの単位行列、その単位行列の１のうち１個以上が０になった行列（以下、適宜、準単位行列という）、単位行列または準単位行列をサイクリックシフト(cyclic shift)した行列（以下、適宜、シフト行列という）、単位行列、準単位行列、またはシフト行列のうちの２以上(複数)の和（以下、適宜、和行列という）、Ｐ×Ｐの０行列の組み合わせで表すことが可能な検査行列Hを有するLDPC符号、もしくは行や列の置換により、これらの行列の組み合わせで表すことが可能な検査行列Hを有するLDPC符号であれば、符号長、符号化率が異なる符号であっても復号可能な復号装置が考案されている。
【００８２】
この復号装置では、チェックノード演算を行うチェックノード計算器とバリアブルノード演算を行うバリアブルノード計算器がＰ個ずつ設けられ、チェックノード演算とバリアブルノード演算がＰ個ずつ並列に行われることにより、復号が行われる。
【００８３】
さらに、サムプロダクトアルゴリズムを近似して実装する方法なども提案されているが、この方法では、性能の劣化を招いてしまう。
【００８４】
ところで、復号装置を構成する受信用メモリが、受信値u0iを格納する１つのメモリから構成される場合、受信用メモリは、読み出しと書き込みを同時に行うことができないため、受信値u0iの記憶と、その受信値u0iを用いた復号のいずれか一方を行っている間、他方を行うことはできない。従って、受信用メモリの使用効率が悪く、スループットが低下してしまう。
【００８５】
そこで、受信用メモリに、受信値u0iを格納する複数のメモリを設け、読み出しと書き込みを同時に行うようにすることが考えられている。
【００８６】
図１１は、２個のメモリが設けられた受信用メモリ２００の構成の一例を示している。
【００８７】
図１１の受信用メモリ２００は、スイッチ２１１および２１４、並びに受信値格納用メモリ２１２および２１３から構成される。
【００８８】
スイッチ２１１には、通信路を通して受信されたLDPC符号から計算された、符号ビットの０らしさを表す受信LLRである受信値D211が供給されるとともに、復号装置を構成する制御部から、受信値格納用メモリ２１２および２１３のいずれか一方の選択を表す制御信号D2101が供給される。スイッチ２１１は、制御信号D2101に基づいて、受信値D211を、受信値D212として受信値格納用メモリ２１２に、または受信値D213として受信値格納用メモリ２１３に供給する。
【００８９】
受信値格納用メモリ２１２は、スイッチ２１１からの受信値D212を格納したり、既に格納している受信値D212を、受信値D214としてスイッチ２１４に供給する。受信値格納用メモリ２１３は、受信値格納用メモリ２１２と同様に、スイッチ２１１からの受信値D213を格納したり、既に格納している受信値D215をスイッチ２１４に供給する。
【００９０】
なお、受信値格納用メモリ２１２および２１３は、例えば、シングルポートRAM（Random Access Memory）で構成される。また、受信値格納用メモリ２１２および２１３のそれぞれに格納されるデータ量、即ち、受信値格納用メモリ２１２および２１３のそれぞれに必要とされる記憶容量は、LDPC符号の符号長と、受信値の量子化ビット数との乗算値である。
【００９１】
スイッチ２１４には、復号装置を構成する制御部から、受信値格納用メモリ２１２と２１３の一方の選択を表す制御信号D2102が供給され、スイッチ２１４は、その制御信号D2102に基づいて、受信値格納用メモリ２１２から読み出された受信値D214または受信値格納用メモリ２１３から読み出された受信値D215を、受信値D216としてバリアブルノード計算器に出力する。
【００９２】
なお、制御信号D2101は、受信値格納用メモリ２１２および２１３の一方の選択を表し、制御信号D2102は、他方の選択を表す。従って、受信値格納用メモリ２１２および２１３の一方で書き込みが行われている間、他方で読出しが行われる。
【００９３】
以上のように、受信用メモリ２００では、２つの受信値格納用メモリ２１２および２１３が設けられているので、一方で入力される受信値D211を格納している間に、他方で既に格納されている受信値D216を出力することができる。その結果、受信用メモリ２００では、連続して入力される受信値D211を、受信値D216として連続出力することができる。
【００９４】
【非特許文献１】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
【非特許文献３】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
【発明の開示】
【発明が解決しようとする課題】
【００９５】
上述したチェックノード演算とバリアブルノード演算をＰ個ずつ並列に行う復号装置では、Ｐ個のバリアブルノード計算器のそれぞれが、受信用メモリ２００に記憶されている受信値u0iをそれぞれ用いて同時にバリアブルノード演算を行うので、受信用メモリ２００からＰ個の受信値u0iを同時に読み出す必要がある。従って、受信値格納用メモリ２１２および２１３のそれぞれに必要なビット幅は、Ｐビットであり、Ｐが大きい場合、受信値格納用メモリ２１２および２１３に必要なビット幅は大きくなる。
【００９６】
例えば、DVB-S2規格に準拠した、符号長が64800であるLDPC符号を復号する場合、LDPC符号の量子化ビット数が5ビットであり、Ｐが360であるとき、受信値格納用メモリ２１２および２１３に必要なビット幅は、1800(=360×5)ビットとなり、ワード数は180(=64800/360)ワードとなる。
【００９７】
そして、受信値格納用メモリ２１２および２１３を構成するRAM（Random Access Memory）マクロなどのビット幅は、数百ビット程度であるため、大きいビット幅を確保するためには、受信値格納用メモリ２１２および２１３を構成するRAMマクロの数が多くなり、受信用メモリ２００の回路規模が増大する。
【００９８】
本発明は、このような状況に鑑みてなされたものであり、LDPC符号を復号する場合において、回路規模を削減することができるようにするものである。
【課題を解決するための手段】
【００９９】
本発明の第１の側面の復号装置は、LDPC(Low Density Parity Check)符号を復号する復号装置であって、間欠的に入力される前記LDPC符号の受信値を一時的に記憶し、記憶している前記受信値を連続的に読み出す第１の記憶手段と、前記第１の記憶手段により連続的に読み出される受信値を記憶し、記憶している前記受信値を所定の単位ごとに読み出す第２の記憶手段と、前記第２の記憶手段により所定の単位ごとに読み出された受信値を、前記所定の単位ごとに復号する復号手段とを備え、前記第１の記憶手段のビット幅は、前記第２の記憶手段のビット幅より小さい。
【０１００】
本発明の第１の側面の復号装置においては、前記第１の記憶手段から前記受信値が読み出され、その受信値が前記第２の記憶手段に記憶される転送時間は、前記LDPC符号の符号語単位の受信値内の値のない時間である無効時間以内であるようにすることができる。
【０１０１】
本発明の第１の側面の復号装置においては、前記第１の記憶手段は、前記受信値を前記符号語単位で読み出すことができる。
【０１０２】
本発明の第１の側面の復号装置は、前記間欠的に入力されるLDPC符号の受信値を前記転送時間に一時的に記憶する第３の記憶手段をさらに設け、前記第１の記憶手段は、前記第３の記憶手段から連続的に読み出された受信値または前記間欠的に入力されるLDPC符号の受信値を一時的に記憶することができる。
【０１０３】
本発明の第１の側面の復号装置においては、前記第１の記憶手段は、前記受信値を前記符号語単位で読み出す前に、前回の読み出し対象である受信値の復号の終了を要求する復号終了要求信号を前記復号手段に供給し、その後、所定の時間経過後に、前記受信値を前記符号語単位で読み出し、前記復号手段は、前記復号終了要求信号に応じて、前記前回の読み出し対象である受信値の復号を終了し、前記所定の時間と前記転送時間の和は、前記無効時間以内であるようにすることができる。
【０１０４】
本発明の第１の側面の復号装置は、前記間欠的に入力されるLDPC符号の受信値を、前記転送時間と前記所定の時間に一時的に記憶する第３の記憶手段をさらに設け、前記第１の記憶手段は、前記第３の記憶手段から連続的に読み出された受信値または前記間欠的に入力されるLDPC符号の受信値を一時的に記憶することができる。
【０１０５】
本発明の第１の側面の復号方法は、LDPC(Low Density Parity Check)符号を復号する復号装置の復号方法であって、間欠的に入力される前記LDPC符号の受信値を一時的に記憶し、記憶している前記受信値を連続的に読み出し、その連続的に読み出される受信値を記憶し、記憶している前記受信値を所定の単位ごとに読み出し、その所定の単位ごとに読み出された受信値を、前記所定の単位ごとに復号するステップを含む。
【０１０６】
本発明の第２の側面の復号装置は、LDPC(Low Density Parity Check)符号を復号する復号装置であって、間欠的に入力される前記LDPC符号の受信値を一時的に記憶し、記憶している前記受信値を連続的に読み出す第１の記憶手段と、前記第１の記憶手段により連続的に読み出される受信値を記憶し、記憶している前記受信値を所定の単位ごとに読み出す第２の記憶手段と、前記第２の記憶手段により所定の単位ごとに読み出された受信値を、前記所定の単位ごとに復号する復号手段とを備え、前記第１の記憶手段と前記第２の記憶手段は、直列に接続される。
【０１０７】
本発明の第１の側面においては、第２の記憶手段よりビット幅が小さい第１の記憶手段が、間欠的に入力されるLDPC符号の受信値を一時的に記憶し、第１の記憶手段が、記憶している受信値を連続的に読み出し、第２の記憶手段が、第１の記憶手段により連続的に読み出される受信値を記憶し、第２の記憶手段が、記憶している受信値を所定の単位ごとに読み出し、復号手段が、第２の記憶手段により所定の単位ごとに読み出された受信値を、所定の単位ごとに復号する。
【０１０８】
本発明の第２の側面においては、間欠的に入力されるLDPC符号の受信値を一時的に記憶し、記憶している受信値を連続的に読み出す第１の記憶手段と、第１の記憶手段により連続的に読み出される受信値を記憶し、記憶している受信値を所定の単位ごとに読み出す第２の記憶手段が、直列に接続される。
【発明の効果】
【０１０９】
以上のように、本発明の第１の側面および第２の側面によれば、LDPC符号を復号する場合において、回路規模を削減することができる。
【発明を実施するための最良の形態】
【０１１０】
以下に本発明の実施の形態を説明するが、請求項に記載の構成要件と、発明の実施の形態における具体例との対応関係を例示すると、次のようになる。この記載は、請求項に記載されている発明をサポートする具体例が、発明の実施の形態に記載されていることを確認するためのものである。従って、発明の実施の形態中には記載されているが、構成要件に対応するものとして、ここには記載されていない具体例があったとしても、そのことは、その具体例が、その構成要件に対応するものではないことを意味するものではない。逆に、具体例が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その具体例が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。
【０１１１】
さらに、この記載は、発明の実施の形態に記載されている具体例に対応する発明が、請求項に全て記載されていることを意味するものではない。換言すれば、この記載は、発明の実施の形態に記載されている具体例に対応する発明であって、この出願の請求項には記載されていない発明の存在、すなわち、将来、分割出願されたり、補正により追加される発明の存在を否定するものではない。
【０１１２】
本発明の第１の側面の復号装置は、
LDPC(Low Density Parity Check)符号を復号する復号装置(例えば、図１２の復号装置４００)であって、
間欠的に入力される前記LDPC符号の受信値を一時的に記憶し、記憶している前記受信値を連続的に読み出す第１の記憶手段（例えば、図１８の入力バッファ５１３）と、
前記第１の記憶手段により連続的に読み出される受信値を記憶し、記憶している前記受信値を所定の単位ごとに読み出す第２の記憶手段（例えば、図１８の受信値格納用メモリ５１４）と、
前記第２の記憶手段により所定の単位ごとに読み出された受信値を、前記所定の単位ごとに復号する復号手段（例えば、図１２の計算部４１２，４１５）と
を備え、
前記第１の記憶手段のビット幅は、前記第２の記憶手段のビット幅より小さい。
【０１１３】
本発明の第１の側面の復号装置は、
前記間欠的に入力されるLDPC符号の受信値を前記転送時間に一時的に記憶する第３の記憶手段（例えば、図１８のプリバッファ５１１）
をさらに備え、
前記第１の記憶手段は、前記第３の記憶手段から連続的に読み出された受信値または前記間欠的に入力されるLDPC符号の受信値を一時的に記憶する。
【０１１４】
本発明の第１の側面の復号装置は、
前記間欠的に入力されるLDPC符号の受信値を、前記転送時間と前記所定の時間に一時的に記憶する第３の記憶手段（例えば、図２３のプリバッファ５１１）
をさらに備え、
前記第１の記憶手段は、前記第３の記憶手段から連続的に読み出された受信値または前記間欠的に入力されるLDPC符号の受信値を一時的に記憶する。
【０１１５】
本発明の第１の側面の復号方法は、
間欠的に入力されるLDPC符号の受信値を一時的に記憶する第１の記憶手段(例えば、図１８の入力バッファ５１３)と、前記第１の記憶手段により連続的に読み出される受信値を記憶する第２の記憶手段（例えば、図１８の受信値格納用メモリ５１４）と、前記第２の記憶手段により所定の単位ごとに読み出された受信値を、前記所定の単位ごとに復号する復号手段（例えば、図１２の計算部４１２，４１５）とを備え、前記LDPC符号を復号する復号装置(例えば、図１２の復号装置４００)の復号方法であって、
前記第２の記憶手段よりビット幅が小さい前記第１の記憶手段が、前記間欠的に入力されるLDPC符号の受信値を一時的に記憶し（例えば、図２０のステップＳ２５）、
前記第１の記憶手段が、記憶している前記受信値を連続的に読み出し（例えば、図２０のステップＳ３１）、
前記第２の記憶手段が、前記第１の記憶手段により連続的に読み出される受信値を記憶し（例えば、図２０のステップＳ３２）、
前記第２の記憶手段が、記憶している前記受信値を前記所定の単位ごとに読み出し（例えば、図２０のステップＳ３７）、
前記復号手段が、前記第２の記憶手段により所定の単位ごとに読み出された受信値を、前記所定の単位ごとに復号する（例えば、図２１のステップＳ５１）
ステップを含む。
【０１１６】
本発明の第２の側面の復号装置は、
LDPC(Low Density Parity Check)符号を復号する復号装置（例えば、図１２の復号装置４００）であって、
間欠的に入力される前記LDPC符号の受信値を一時的に記憶し、記憶している前記受信値を連続的に読み出す第１の記憶手段（例えば、図１８の入力バッファ５１３）と、
前記第１の記憶手段により連続的に読み出される受信値を記憶し、記憶している前記受信値を所定の単位ごとに読み出す第２の記憶手段（例えば、図１８の受信値格納用メモリ５１４）と、
前記第２の記憶手段により所定の単位ごとに読み出された受信値を、前記所定の単位ごとに復号する復号手段（例えば、図１２の計算部４１２，４１５）と
を備え、
前記第１の記憶手段と前記第２の記憶手段は、直列に接続される。
【０１１７】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。
【０１１８】
図１２は、本発明を適用した復号装置の第１の実施の形態の構成例を示している。
【０１１９】
なお、ここでは、図１３に示す、６×６の単位行列、準単位行列、シフト行列、和行列、６×６の０行列の組み合わせで表すことが可能な検査行列Hを有するLDPC符号、もしくは行や列の置換により、これらの行列の組み合わせで表すことが可能な検査行列Hを有するLDPC符号を復号することとする。
【０１２０】
図１３の検査行列Hは、図７に示した検査行列Hを、６×６の行列の単位に間隔を空けて表したものである。また、図１３の検査行列Hを構成する６×６の単位行列、準単位行列、シフト行列、和行列、０行列を、以下、適宜、構成行列という。
【０１２１】
図１２の復号装置４００は、復号途中結果格納用メモリ４１０、サイクリックシフト回路４１１、６つの計算器４１２1乃至計算器４１２6からなる計算部４１２、復号途中結果格納用メモリ４１３、サイクリックシフト回路４１４、６つの計算器４１５1乃至計算器４１５6からなる計算部４１５、スイッチ４１６、受信用メモリ４１７、および制御部４１８から構成され、LDPC符号を６つずつ復号する。
【０１２２】
ここで、計算器４１２k（k=1,2,・・・，6）で行われる演算と、計算器４１５kで行われる演算について、式を用いて説明する。
【０１２３】
具体的には、計算部４１２は、上述した式（７）と、以下に表す式（８）にしたがう第１の演算を行い、その第１の演算の結果である復号途中結果ujを復号途中結果格納用メモリ４１０に供給して格納させる。計算部４１５は、上述した式（５）にしたがう第２の演算を行い、その第２の演算の結果である復号途中結果vを復号途中結果格納用メモリ４１０に供給して格納させる。
【０１２４】
【数８】
2008278191.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の列数、即ち、LDPC符号の符号長と復号途中結果vの量子化ビット数とを乗算した値となる。
【０１３２】
その結果、バリアブルノード演算の結果を格納する場合に比べて、復号途中結果格納用メモリ４１０のメモリ容量を削減することができ、これにより、復号装置４００の回路規模を小さくすることができる。
【０１３３】
以下、図１２の復号装置４００の各部の動作について詳細に説明する。
【０１３４】
復号途中結果格納用メモリ４１０には、スイッチ４１６から、計算部４１５による第２の演算の結果である検査行列Hの６つの列に対応する６つの復号途中結果D415が復号途中結果D416として供給され、復号途中結果格納用メモリ４１０は、計算部４１５から供給された６つの復号途中結果D416(ｖi)を、第１アドレスから順に格納する。
【０１３５】
即ち、復号途中結果格納用メモリ４１０の第１アドレスには、検査行列Hの列に対応する復号途中結果D416のうち、第１列目から第６列目の復号途中結果D416が格納される。そして、同様に、第２アドレスには、第７列目から第１２列目の復号途中結果D416が格納され、第３アドレスには、第１３列目から第１８列目の復号途中結果D416が格納される。以後、同様に、第１０３列目から第１０８列目までの復号途中結果D416が、６個ずつ、第４アドレスから第１８アドレスまで格納され、計１０８個の復号途中結果D416が復号途中結果格納用メモリ４１０に格納される。従って、復号途中結果格納用メモリ４１０のワード（word）数は、図１３の検査行列Hの列数（LDPC符号の符号長）である１０８を、同時に読み書きする復号途中結果の数である６で割り算した１８となる。
【０１３６】
また、復号途中結果格納用メモリ４１０は、既に格納してある復号途中結果D416から、後段の計算部４１２が求めようとする復号途中結果ujの対応する検査行列Hの行において“１”になっている復号途中結果D146を６つ同時に読み出し、復号途中結果D410として、サイクリックシフト回路４１１に供給する。
【０１３７】
なお、復号途中結果格納用メモリ４１０は、例えば、６つの復号途中結果を同時に読み書き可能なシングルポートRAMで構成される。また、復号途中結果格納用メモリ４１０には、計算部４１５の第２の演算により演算された列に対応する復号途中結果D416が格納されるので、復号途中結果格納用メモリ４１０に格納されるデータ量、即ち、復号途中結果格納用メモリ４１０に必要とされる記憶容量は、復号途中結果D414の量子化ビット数と、検査行列Hの列数（LDPC符号の符号長）との乗算値である。
【０１３８】
サイクリックシフト回路４１１には、復号途中結果格納用メモリ４１０から６つの復号途中結果D410が供給されるとともに、制御部４１８から、その復号途中結果D410に対応する検査行列Hの１が、検査行列Hにおいて元となる単位行列などを幾つサイクリックシフトであるかの情報（Matrixデータ）を表す制御信号D420が供給される。サイクリックシフト回路４１１は、制御信号D420を基に、６つの復号途中結果D410を並べ替えるサイクリックシフトを行い、その結果を復号途中結果D411として、計算部４１２に供給する。
【０１３９】
計算部４１２は、６つの計算器４１２1乃至４１２6からなる。計算部４１２には、サイクリックシフト回路４１１から、計算部４１５による第２の演算の結果得られた６つの復号途中結果D411（vi）が供給されるとともに、復号途中結果格納用メモリ４１３から、前回、計算器４１２1乃至４１２6による第１の演算の結果得られた６つの復号途中結果D413（uj）が供給され、その６つの復号途中結果D411と６つの復号途中結果D413が、計算器４１２1乃至４１２6にそれぞれ供給される。また、計算部４１２には、制御部４１８から制御信号D421が供給され、その制御信号D421が、計算器４１２1乃至４１２6に供給される。なお、制御信号D421は、６つの計算器４１２1乃至４１２6に共通の信号である。
【０１４０】
計算器４１２1乃至４１２6は、それぞれ復号途中結果D411と復号途中結果D413を用いて、式（７）と式（８）にしたがって第１の演算を行い、復号途中結果D412（uj）を求める。計算部４１２は、計算器４１２1乃至４１２6による演算の結果得られる検査行列Hの６つの１に対応する６つの復号途中結果D412を復号途中結果格納用メモリ４１３に供給する。なお、計算器４１２1乃至４１２6の詳細については、後述する図１４を参照して説明する。
【０１４１】
復号途中結果格納用メモリ４１３は、例えば、６つの復号途中結果を同時に読み書き可能な、２つのシングルポートRAMから構成される。復号途中結果格納用メモリ４１３には、計算部４１２から６つの復号途中結果D412が供給されるとともに、制御部４１８から復号途中結果格納用メモリ４１３の読み書きを制御する制御信号D422が供給される。
【０１４２】
復号途中結果格納用メモリ４１３は、制御信号D422に基づいて、計算部４１２から供給される６つの復号途中結果D412をまとめて格納すると同時に、既に格納してある６つの復号途中結果D412を読み出し、復号途中結果D413として、計算部４１２とサイクリックシフト回路４１４に供給する。即ち、復号途中結果格納用メモリ４１３は、計算部４１２とサイクリックシフト回路４１４に供給する復号途中結果D413の読み出しと、計算部４１２から供給される復号途中結果D412の書き込みとを、同時に行う。
【０１４３】
なお、復号途中結果格納用メモリ４１３には、計算部４１２の第１の演算により演算された検査行列Hのｉ列の、各行の１に対応する枝からの第１の演算の復号途中結果D412が格納されるので、復号途中結果格納用メモリ４１３に格納されるデータ量、即ち、復号途中結果格納用メモリ４１３に必要とされる記憶容量は、復号途中結果D412の量子化ビット数と、検査行列Hの１の数との乗算値となる。この復号途中結果格納用メモリ４１３の詳細については、後述する図１６を参照して説明する。
【０１４４】
サイクリックシフト回路４１４には、復号途中結果格納用メモリ４１３から６つの復号途中結果D413（uj）が供給されるとともに、制御部４１８から、その復号途中結果D413に対応する検査行列Hの１が検査行列Hにおいて元となる単位行列などを幾つサイクリックシフトしたものであるかの情報（Matrixデータ）を表す制御信号D423が供給される。サイクリックシフト回路４１４は、制御信号D423を基に、６つの復号途中結果D413を並べ替えるサイクリックシフトを行い、その結果を復号途中結果D414として、計算部４１５に供給する。
【０１４５】
計算部４１５は、６つの計算器４１５1乃至４１５6からなる。計算部４１５には、サイクリックシフト回路４１４から６つの復号途中結果D414が供給され、その復号途中結果D414が、計算器４１５1乃至４１５6のそれぞれに供給される。また、計算部４１５には、受信用メモリ４１７から６つの受信値D419が同時に供給され、その受信値D419が、計算器４１５1乃至４１５6のそれぞれに供給される。さらに、計算部４１５には、制御部４１８から制御信号D424が供給され、その制御信号D424が計算器４１５1乃至４１５6に供給される。なお、制御信号D424は、６つの計算器４１５1乃至４１５6に共通の信号である。
【０１４６】
計算器４１５1乃至４１５6は、それぞれ復号途中結果D414と受信値D419とを用いて、式（５）にしたがって、それぞれ第２の演算を同時に行い、復号途中結果D415を求める。計算部４１５は、計算器４１５1乃至４１５6の第２の演算の結果得られる６つの復号途中結果D415(v)を、スイッチ４１６に供給する。なお、計算器４１５1乃至４１５6の詳細については、後述する図１５を参照して説明する。
【０１４７】
以上のように、復号途中結果格納用メモリ４１０、サイクリックシフト回路４１１、計算部４１２、復号途中結果格納用メモリ４１３、サイクリックシフト回路４１４、計算部４１５の順で、データが一巡することで、復号装置４００は、１回の復号を行うことができる。
【０１４８】
スイッチ４１６は、制御部４１８から供給される、復号結果の出力を表す制御信号D425に応じて、計算部４１５から供給される６つの復号途中結果D415の出力先を変更する。具体的には、スイッチ４１６は、制御信号D425が供給されない場合、６つの復号途中結果D415を、復号途中結果D416として、復号途中結果格納用メモリ４１０に供給する。一方、スイッチ４１６は、制御信号D425が供給される場合、６つの復号途中結果D415を、最終的な復号結果D417として出力する。
【０１４９】
受信用メモリ４１７には、通信路を通して受信されたLDPC符号から計算された、符号ビットの０らしさを表す受信LLRである受信値D418が入力される。
【０１５０】
なお、ここでは、通信路を通して、例えば、DVB-S2規格に準拠したLDPC符号が受信されるものとする。この場合、各フレームの実際の値の先頭に、ヘッダが設けられ、また復号装置４００の前段の復調処理の同期性能改善のために各フレームの実際の値の途中にパイロットが挿入されるため、このヘッダとパイロットの区間が、実際の値のない無効時間となり、受信されたLDPC符号から計算された受信値D418は、間欠的になる。さらに、復号装置４００の動作クロックは、一般的に、前段の復調処理の動作クロックより高速であるため、動作クロックの乗り換えによっても無効時間が発生し、受信値D418は間欠的になる。
【０１５１】
受信用メモリ４１７は、間欠的に入力された受信値D418を格納する。そして、受信用メモリ４１７は、既に格納している受信値D418を、バリアブルノード演算に必要となる順番に６つずつ読み出し、受信値D419として計算部４１５に供給する。なお、受信用メモリ４１７の詳細については、後述する図１８を参照して説明する。
【０１５２】
制御部４１８は、予め設定された所定の回数だけ繰り返して復号が行われるように、各部を制御する。具体的には、制御部４１８は、制御信号D420をサイクリックシフト回路４１１に、制御信号D421を計算部４１２に供給することにより、それぞれを制御する。また、制御部４１８は、制御信号D422を復号途中結果格納用メモリ４１３に、制御信号D423をサイクリックシフト回路４１４に、制御信号D424を計算部４１５にそれぞれ供給することにより、それぞれを制御する。さらに、制御部４１８は、所定のタイミングで、制御信号D425をスイッチ４１６に供給することにより、所定の回数だけ繰り返し行われた第２の演算の最後の結果として得られる復号途中結果D415を、復号結果D417として出力させるように、スイッチ４１６を制御する。
【０１５３】
図１４は、図１２の計算部４１２の計算器４１２1の詳細構成例を示すブロック図である。
【０１５４】
なお、図１４では、計算器４１２1について説明するが、計算器４１２2乃至計算器４１２6も同様に構成される。
【０１５５】
また、図１４では、前回の計算部４１２による第１の演算の結果得られる各復号途中結果(udv)が符号ビットを合わせて合計６ビット(bit)に量子化され、計算部４１５による第２の演算の結果得られる各復号途中結果（v）が９ビットに量子化されているものとして、計算器４１２1を表している。さらに、図１４の計算器４１２1には、クロックｃｋが供給され、このクロックｃｋは、必要なブロックに供給されるようになっている。そして、各ブロックは、クロックｃｋに同期して処理を行う。
【０１５６】
図１４の計算器４１２1は、制御部４１８から供給される制御信号D421に基づいて、復号途中結果格納用メモリ４１３から１つずつ読み込まれる、前回の計算部４１２による第１の演算の結果得られた復号途中結果D413（udv）と、サイクリックシフト回路４１１から1つずつ読み込まれる復号途中結果D411（v）とを用いて、式（７）と式（８）にしたがう第１の演算を行う。
【０１５７】
即ち、計算器４１２1には、サイクリックシフト回路４１１から供給される６つの９ビットの復号途中結果D411(v)のうちの、１つの復号途中結果D411が供給されるとともに、復号途中結果格納用メモリ４１３から供給される、前回の計算部４１２による演算の結果である６つの６ビットの復号途中結果D413（uj）のうちの、１つの復号途中結果D413が供給され、その９ビットの復号途中結果D411（v）と６ビットの復号途中結果D413（udv）が、減算器４３１に供給される。また、計算器４１２1には、制御部４１８から制御信号D421が供給され、その制御信号D421がセレクタ４３５とセレクタ４４２に供給される。
【０１５８】
減算器４３１は、９ビットの復号途中結果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が積算された積算値が格納された場合、制御部４１８から供給される制御信号D421は、０から１に変化する。例えば、行の重み（row weight）が「９」である場合、制御信号D421は、１から８クロック目までは、「０」となり、９クロック目では「１」となる。
【０１６３】
制御信号D421が「１」の場合、セレクタ４３５は、レジスタ４３４に格納されている値、即ち、検査行列Hの1行に亘る全ての１に対応する復号途中結果D411（復号途中結果v）から求められたφ(|vi|)が積算された９ビットの値D435（ｉ＝１からｉ＝ｄcまでのΣφ(|vi|)）を選択し、値D436として、レジスタ４３６に出力して格納させる。レジスタ４３６は、格納している値D436を、９ビットの値D437として、セレクタ４３５と加減算器４３７に供給する。制御信号D421が「０」の場合、セレクタ４３５は、レジスタ４３６から供給された値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)）がレジスタ４４１に格納された場合、制御部４１８から供給される制御信号D421は、「０」から「１」に変化する。
【０１６８】
制御信号D421が「１」の場合、セレクタ４４２は、レジスタ４４１に格納されている値、即ち、検査行列Hの1行に亘る全ての１に対応する復号途中結果D411から求められた符号ビットD432が乗算された値D442（ｉ＝１からｉ＝ｄcまでのΠsign(vi)）を選択し、１ビットの値D443としてレジスタ４４３に出力して格納させる。レジスタ４４３は、格納している値D443を、１ビットの値D444としてセレクタ４４２とEXOR回路４４５に供給する。制御信号D421が「０」の場合、セレクタ４４２は、レジスタ４４３から供給された値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は、制御部４１８から供給される制御信号D424に基づいて、受信用メモリ４１７から１つずつ読み込まれる受信値D419（u0i）と、サイクリックシフト回路４１４から１つずつ読み込まれる復号途中結果D414（uj）とを用いて、式（５）にしたがう第２の演算を行う。
【０１７７】
即ち、計算器４１５1では、サイクリックシフト回路４１４から、検査行列Hの各行の１に対応する６ビットの復号途中結果D414（uj）が１つずつ読み込まれ、その復号途中結果D414が、加算器４７１に供給される。また、計算器４１５1では、受信用メモリ４１７から６ビットの受信値D419が１つずつ読み込まれ、加算器４７５に供給される。さらに、計算器４１５1には、制御部４１８から制御信号D424が供給され、その制御信号D424は、セレクタ４７３に供給される。
【０１７８】
加算器４７１は、復号途中結果D414（uj）とレジスタ４７２に格納されている９ビットの値D471とを加算することにより、復号途中結果D414を積算し、その結果得られる９ビットの積算値を、レジスタ４７２に再格納する。なお、検査行列Hの１列に亘る全ての１に対応する復号途中結果D414が積算された場合、レジスタ４７２はリセットされる。
【０１７９】
検査行列Hの１列に亘る復号途中結果D414が１つずつ読み込まれ、レジスタ４７２に１列分の復号途中結果D414が積算された値が格納された場合、制御部４１８から供給される制御信号D424は、「０」から「１」に変化する。例えば、列の重みが「５」である場合、制御信号D424は、１から４クロック目までは「０」となり、５クロック目では「１」となる。
【０１８０】
制御信号D424が「１」の場合、セレクタ４７３は、レジスタ４７２に格納されている値、即ち、検査行列Hの１列に亘る全ての枝からの復号途中結果D414（uj）が積算された９ビットの値D471（ｊ＝１からｄVまでのΣuj)を選択し、レジスタ４７４に出力して格納させる。レジスタ４７４は、格納している値D471を、９ビットの値D472として、セレクタ４７３と加算器４７５に供給する。制御信号D424が「０」の場合、セレクタ４７３は、レジスタ４７４から供給された値D472を選択し、レジスタ４７４に出力し再格納させる。即ち、検査行列Hの１列に亘る全ての枝からの復号途中結果D414（uj）が積算されるまで、レジスタ４７４は、前回積算された値を、セレクタ４７３と加算器４７５に供給する。
【０１８１】
加算器４７５は、９ビットの値D472と、受信用メモリ４１７から供給された６ビットの受信値D419とを加算して、その結果得られる６ビットの値を復号途中結果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に対応づけてデータが格納される。
【０１９１】
即ち、重みが２以上の構成行列については、その構成行列を、重みが１であるＰ×Ｐの単位行列、そのコンポーネントである１のうち１個以上が０になった準単位行列、または単位行列もしくは準単位行列をサイクリックシフトしたシフト行列のうちの複数の和の形で表現したときの、その重みが１の単位行列、準単位行列、またはシフト行列の１の位置に対応するデータ（単位行列、準単位行列、またはシフト行列に属する枝に対応するメッセージの復号途中結果）は、同一アドレスに格納される。
【０１９２】
同様に、復号途中結果格納用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５０３の一方の選択を表す制御信号D4221が制御部４１８から供給される。スイッチ５０１は、制御信号D4221に基づいて、復号途中結果格納用RAM５０２または復号途中結果格納用RAM５０３の一方を選択し、その選択した一方に、６つの復号途中結果D412を供給する。
【０２００】
復号途中結果格納用RAM５０２には、スイッチ５０１から６つの復号途中結果D412が、復号途中結果D501として供給されるとともに、制御部４１８からアドレスを表す制御信号D4222が供給される。復号途中結果格納用RAM５０２は、制御信号D4222が表すアドレスに既に格納されている前回の計算部４１２による第１の演算の結果得られた６つの復号途中結果D501を読み出し、復号途中結果D503としてスイッチ５０４に供給する。また、復号途中結果格納用RAM５０２は、制御信号D4222が表すアドレスに、スイッチ５０１から供給された６つの復号途中結果D501を格納する。
【０２０１】
復号途中結果格納用RAM５０３には、スイッチ５０１から６つの復号途中結果D412が、復号途中結果D502として供給されるとともに、制御部４１８からアドレスを表す制御信号D4223が供給される。復号途中結果格納用RAM５０３は、制御信号D4223が表すアドレスに既に格納されている前回の計算部４１２による第１の演算の結果得られた６つの復号途中結果D502を読み出し、復号途中結果D504としてスイッチ５０４に供給する。また、復号途中結果格納用RAM５０３は、制御信号D4223が表すアドレスに、スイッチ５０１から供給された６つの復号途中結果D502を格納する。
【０２０２】
スイッチ５０４には、復号途中結果格納用RAM５０２から復号途中結果D503が供給されるか、あるいは復号途中結果格納用RAM５０３から復号途中結果D504が供給される。また、制御部４１８から、復号途中結果格納用RAM５０２または復号途中結果格納用RAM５０３の一方の選択を表す制御信号D4224が供給される。スイッチ５０４は、制御信号D4224に基づいて、復号途中結果格納用RAM５０２または復号途中結果格納用RAM５０３の一方を選択し、その選択した一方から供給された６つの復号途中結果を、６つの復号途中結果D413として計算部４１２とサイクリックシフト回路４１４に供給する。
【０２０３】
図１７は、復号途中結果格納用メモリ４１３の復号途中結果格納用RAM５０２と復号途中結果格納用RAM５０３の読み出しと書き込みの動作を説明するタイミングチャートである。
【０２０４】
なお、図１７において、横軸は、時間（ｔ）を表している。また、図１７では、左上から順に右下方向になるに連れて大きくなるように構成行列に付された数字ｉの構成行列の１に対応するデータの読み出しをRiと表し、そのデータの書き込みをWiと表す。
【０２０５】
復号途中結果格納用メモリ４１３では、計算部４１２により第１の演算が行われる場合、復号途中結果格納用RAM５０２が、制御信号D4222に基づいて、既に格納している、前回の計算部４１２の第１の演算の結果得られた復号途中結果D501のうち、同一アドレスに格納している検査行列Hの第１行目から第６行目までの１に対応する復号途中結果D501を、1クロックに６つずつ、９回（９クロック分）連続して読み出し（Ｒ０乃至Ｒ８）、スイッチ５０４を介して、計算部４１２に供給する。即ち、図１３の検査行列Hの行重みは、９であるため、検査行列Hの各行の１に対応する復号途中結果は９つあり、復号途中結果格納用RAM５０２は、第１行目から第６行目までの１に対応する６つの復号途中結果D501を、６つ単位で９回連続して読み出し、計算部４１２に供給する。
【０２０６】
次に、復号途中結果格納用RAM５０３は、制御信号D4223に基づいて、既に格納している、前回の計算部４１２による第１の演算の結果得られた復号途中結果D502のうち、同一アドレスに格納している検査行列Hの第７行目から第１２行目までの１に対応する復号途中結果D502を、６つ単位で９回連続して読み出し（Ｒ９乃至Ｒ１７）、スイッチ５０４を介して、計算部４１２に供給する。そして、以降も同様に、復号途中結果格納用RAM５０２および５０３は、交互に、復号途中結果D501またはD502を、６つ単位で９回連続して読み出し、計算部４１２に供給する。
【０２０７】
ところで、ノードを１つずつ計算する計算器４１２1乃至４１２6または４１５1乃至４１５6では、ノード次数(node degree)分の遅延が生じる。例えば、計算器４１２1乃至４１２6では９クロック分の遅延が生じる。また、復号装置４００が100MHzを超える高速動作を行う場合、計算器４１２1乃至４１２6では、さらに３クロック分程度の遅延が生じ、３クロック分程度のパイプライン化が必要となる。
【０２０８】
即ち、計算部４１２が第１の演算を行うために必要な時間、即ち復号途中結果格納用メモリ４１３から復号途中結果D413が読み出されてから、その復号途中結果D413を用いた第１の演算の結果得られる復号途中結果D412が復号途中結果格納用メモリ４１３に供給されるまでの時間は、１２クロック分の時間Ｔ１となる。
【０２０９】
この場合、復号途中結果格納用RAM５０２から復号途中結果D503の１回目の読み出し（Ｒ０）が開始されてから時間Ｔ１後に、計算部４１２から復号途中結果格納用メモリ４１３への、第１の演算の結果得られる検査行列Hの第１行目から第６行目までの１に対応する６つの復号途中結果D412の供給が開始される。その復号途中結果D413は、スイッチ５０１を介して復号途中結果D501として復号途中結果格納用RAM５０２に供給され、復号途中結果格納用RAM５０２は、その復号途中結果D501を、制御信号D4222に基づいて、既に読み出された復号途中結果D503が格納されていたアドレスに９回続けて格納する（Ｗ０乃至Ｗ８）。
【０２１０】
即ち、復号途中結果格納用RAM５０２により復号途中結果D503の９回の読み出し（Ｒ０乃至Ｒ８）が終了してから、復号途中結果格納用RAM５０２により復号途中結果D501の９回の格納（Ｗ０乃至Ｗ８）が開始されるまでに、３クロック分の時間Ｔｗ（＝Ｔ１−９）の待ち時間が生じる。
【０２１１】
その結果、復号途中結果格納用RAM５０３からの９回の読み出し(Ｒ９乃至Ｒ１７)が終了してから、時間Ｔｗが経過後に復号途中結果格納用RAM５０２への９回の格納（Ｗ０乃至Ｗ８）が終了する。従って、復号途中結果格納用RAM５０３からの９回の読み出し（Ｒ９乃至Ｒ１７）が終了してから、復号途中結果格納用RAM５０２からの９回の読み出し（Ｒ１８乃至Ｒ２６）を開始するまでに、時間Ｔｗの待ち時間が必要となる。
【０２１２】
図１８は、図１２の受信用メモリ４１７の詳細構成例を示している。
【０２１３】
図１８の受信用メモリ４１７は、プリバッファ５１１、スイッチ５１２、入力バッファ５１３、および受信値格納用メモリ５１４により構成される。受信用メモリ４１７には、受信値D418が間欠的に入力され、この受信値D418は、プリバッファ５１１とスイッチ５１２の端子５１２Ａに供給される。
【０２１４】
プリバッファ５１１には、入力バッファ５１３から、プリバッファ５１１の選択を表す制御信号D515が供給される。プリバッファ５１１は、その制御信号D515に応じて、受信値D418を一時的に記憶する。なお、プリバッファ５１１の記憶容量は、入力バッファ５１３から受信値格納用メモリ５１４へ１フレーム分の受信値D513を転送するために必要な時間内に、受信可能な受信値D418の最大数Ｍと、量子化ビット数との乗算値である。
【０２１５】
これに対して、後述するように、入力バッファ５１３と受信値格納用メモリ５１４の記憶容量は、１フレーム分の受信値のデータ量、即ち、符号長と量子化ビット数の乗算値であるので、プリバッファ５１１の記憶容量は、入力バッファ５１３と受信値格納用メモリ５１４の記憶容量に比べて十分に小さい。
【０２１６】
また、プリバッファ５１１は、記憶している受信値D418を受信値D511として連続的に読み出し、スイッチ５１２を介して入力バッファ５１３に供給する。さらに、プリバッファ５１１は、読み出し済みの受信値D418を削除する。プリバッファ５１１は、記憶している受信値D418がなくなった場合、スイッチ５１２に、端子５１２Ａの選択を表す制御信号D514を供給する。
【０２１７】
スイッチ５１２は、３つの端子５１２Ａ乃至５１２Ｃを有している。端子５１２Ａには受信値D418が入力され、端子５１２Ｂにはプリバッファ５１１が接続され、端子５１２Ｃには入力バッファ５１３が接続される。スイッチ５１２は、プリバッファ５１１から供給される制御信号D514に応じて、端子５１２Ａと端子５１２Ｃを接続し、端子５１２Ａに入力される受信値D418を、受信値D512として入力バッファ５１３に入力する。また、スイッチ５１２は、入力バッファ５１３から供給される制御信号D515に応じて、端子５１２Ｂと端子５１２Ｃを接続し、プリバッファ５１１から読み出された受信値D511を、受信値D512として入力バッファ５１３に入力する。
【０２１８】
入力バッファ５１３の記憶容量は、例えば、符号長と量子化ビット数の乗算値であり、入力バッファ５１３は、スイッチ５１２により入力される受信値D512を、一時的に１フレーム分記憶する。なお、ここでは、入力バッファ５１３のビット幅は、受信値格納用メモリ５１４のビット幅の1/N（Nは2以上の整数）倍であり、ワード数は、受信値格納用メモリ５１４のワード数のN倍であるものとするが、入力バッファ５１３のビット幅は、受信値格納用メモリ５１４のビット幅より小さければ、1/N倍である必要はない。
【０２１９】
入力バッファ５１３は、1フレーム分の受信値D512の書き込みを完了した場合、例えば、入力バッファ５１３の空き容量がゼロになった場合、プリバッファ５１１とスイッチ５１２に制御信号D515を入力する。そして、入力バッファ５１３は、記憶している１フレーム分の受信値D512を、受信値D513として連続的に読み出し、受信値格納用メモリ５１４に転送する。即ち、入力バッファ５１３は、１フレーム単位、つまり、符号語単位で、受信値D512を連続的に読み出し、受信値格納用メモリ５１４に転送する。
【０２２０】
受信値格納用メモリ５１４は、入力バッファ５１３に直列に接続され、受信値格納用メモリ５１４の記憶容量は、符号長と量子化ビット数の乗算値である。受信値格納用メモリ５１４は、入力バッファ５１３から転送されてくる１フレーム分の受信値D513を、第１アドレスから順に格納する。
【０２２１】
なお、上述したように、６つの計算器４１５1乃至４１５6は、同時に第２の演算を行うので、受信値格納用メモリ５１４は、６つの受信値D419を同時に計算器４１５1乃至４１５6のそれぞれに供給する必要がある。従って、受信値格納用メモリ５１４は、例えば、６つの受信値D419を同時に読み出し可能なシングルポートRAMで構成され、受信値格納用メモリ５１４のビット幅は、量子化ビット数の６倍のビットであり、ワード数は、符号長（いまの場合、108）から６を除算した値（いまの場合、18）である。
【０２２２】
具体的には、受信値格納用メモリ５１４の第１アドレスには、検査行列Hの列に対応する受信値D513のうち、第１列から第６列目の受信値D513が格納される。そして、同様に、第２アドレスには、第７列目から第１２列目の受信値D513が格納され、第３アドレスには、第１３列目から第１８列目の受信値D513が格納される。以後、同様に、第１０３列目から第１０８列目までの受信値D513が、６個ずつ、第４アドレスから第１８アドレスまで格納され、計１０８個の受信値D513が受信値格納用メモリ５１４格納される。
【０２２３】
受信値格納用メモリ５１４は、記憶している１フレーム分の受信値D513を、ワード単位で６つずつ読み出し、その読み出した６つの受信値D513を６つの受信値D419として計算部４１５（図１２）に供給する。
【０２２４】
以上のように、受信用メモリ４１７では、入力バッファ５１３と受信値格納用メモリ５１４が直列に接続され、計算部４１５への受信値D419の出力が、１つの受信値格納用メモリ５１４で行われるので、入力バッファ５１３は、６つの受信値D419を同時に読み出す必要がなく、入力バッファ５１３のビット幅を、量子化ビット数の６倍のビットより小さくすることができる。その結果、量子化ビット数の６倍のビット幅を有する２つの受信値格納用メモリ２１２および２１３から構成される従来の受信用メモリ１０４（図１１）に比べて、受信用メモリ４１７を構成するRAMマクロの数を削減し、これにより、受信用メモリ４１７の回路規模を削減することができる。
【０２２５】
次に、図１９を参照して、図１８の受信用メモリ４１７におけるタイミングについて説明する。
【０２２６】
図１９Ａに示すように、時刻ｔAにおいて、受信用メモリ４１７に対する、先頭からｉ番目のフレームであるフレーム＃ｉの受信値D418の間欠的な入力が開始されると、図１９Ｂに示すように、プリバッファ５１１は、入力バッファ５１３からの制御信号D515に応じて、受信値D418の書き込みを開始し、後述するフレーム＃ｉの１つ前のフレーム＃ｉ−１の受信値D513の、受信値格納用メモリ５１４への転送が終了する時刻ｔBまでの時間Ａの間、受信値D418の書き込みのみを行う（図中、Wi）。なお、フレーム＃ｉの受信値D418の先頭には、上述したように、実際の値の前にヘッダが付加されているので、プリバッファ５１１は、実際の値が受信される時刻ｔA´から書き込みを開始する。
【０２２７】
また、時刻ｔA´から時刻ｔBまでの間、図１９Ｄに示すように、スイッチ５１２は、入力バッファ５１３からの制御信号D515に応じて、プリバッファ５１１を選択するが、図１９Ｂに示したように、プリバッファ５１１は読み出しを行わない。従って、図１９Ｃに示すように、プリバッファ５１１からスイッチ５１２には何も供給されず、図１９Ｅに示すように、スイッチ５１２から入力バッファ５１３にも何も供給されない。
【０２２８】
一方、図１９Ｆに示すように、時刻ｔAにおいて、入力バッファ５１３は、既に記憶しているフレーム＃ｉ−１の受信値D512の読み出し、および、その受信値D512の受信値格納用メモリ５１４への転送を開始し（図中、Ri-1）、これにより、図１９Ｇに示すように、受信値格納用メモリ５１４には、フレーム＃ｉ−１の受信値D512が受信値D513として供給される。そして、図１９Ｈに示すように、受信値格納用メモリ５１４は、入力バッファ５１３から供給される、フレーム＃ｉ−１の受信値D513の書き込みを開始する（図中、Wi-1）。
【０２２９】
時刻ｔAから時間Ａ後の時刻ｔBにおいて、図１９Ｆ乃至図１９Ｈに示すように、入力バッファ５１３から受信値格納用メモリ５１４へのフレーム＃ｉ−１の受信値D513の転送が終了すると、図１９Ｂに示すように、プリバッファ５１１は、間欠的に供給されるフレーム＃ｉの受信値D418の書き込みと、既に書き込まれているフレーム＃ｉの受信値D418の連続的な読み出しの両方を開始する（図中、Wi＆Ri）。従って、図１９Ｃに示すように、プリバッファ５１１からスイッチ５１２には、フレーム＃ｉの受信値D418が、無効時間分を詰めた状態で受信値D511として入力される。
【０２３０】
このとき、図１９Ｄに示すように、スイッチ５１２は、プリバッファ５１１を選択したままであり、図１９Ｅに示すように、プリバッファ５１１から読み出されたフレーム＃ｉの受信値D511を、受信値D512として入力バッファ５１３に供給する。また、図１９Ｆに示すように、時刻ｔBにおいて、入力バッファ５１３は、フレーム＃ｉ−１の受信値D513の読み出しを終了し、スイッチ５１２から供給される、フレーム＃ｉの受信値D512の書き込みを開始する（図中、Wi）。従って、図１９Ｇに示すように、受信値格納用メモリ５１４には、受信値D513が入力されなくなる。このとき、図１９Ｈに示すように、受信値格納用メモリ５１４は、時間Ａに書き込んだフレーム＃ｉ−１の受信値D513を6個単位で受信値D419として読み出し、計算部４１５に供給する。その結果、フレーム＃ｉ−１の繰り返し復号が行われる（繰り返し復号＃ｉ−１）。
【０２３１】
ところで、プリバッファ５１１には受信値D418が間欠的に供給されるが、プリバッファ５１１からは受信値D418が連続的に読み出されるので、受信値D418の書き込みと読み出しを両方行うと、所定の時間経過後にプリバッファ５１１が空になる。図１９の例では、この所定の時間は時間Ｂであるものとする。
【０２３２】
従って、図１９Ｂに示すように、プリバッファ５１１は、時刻ｔBから時間Ｂ後の時刻ｔCにおいて、受信値D418の書き込みと読み出しを終了し（図中、NO）、これにより、図１９Ｃに示すように、プリバッファ５１１からスイッチ５１２への受信値D511の供給が終了される。このとき、プリバッファ５１１は、制御信号D514をスイッチ５１２に供給し、スイッチ５１２は、図１９Ｄに示すように、その制御信号D514に応じて端子５１２Ａを選択する。その結果、図１９Ｅに示すように、間欠的に入力されるフレーム＃ｉの受信値D418が、そのまま受信値D512として入力バッファ５１３に入力される。
【０２３３】
また、図１９Ｆに示すように、時刻ｔCにおいても、入力バッファ５１３は、スイッチ５１２から入力される、フレーム＃ｉの受信値D512の書き込みを続け、時刻ｔDにおいて、フレーム＃ｉの受信値D512のすべての書き込みを完了すると、書き込みを終了する。即ち、入力バッファ５１３は、時刻ｔBから時刻ｔCまでの時間Ｂの間、プリバッファ５１１から連続的に入力される受信値D511を受信値D512として書き込み、時刻ｔCから時刻ｔDまでの時間Ｃの間、プリバッファ５１１を介さずに間欠的に直接入力される受信値D418を受信値D512として書き込むことにより、フレーム＃ｉのすべての受信値D418を書き込む。
【０２３４】
このように、時間ＢとＣの間、入力バッファ５１３は書き込みを行っており、読み出しを行わないので、図１９Ｇに示すように、時刻ｔCから時間Ｃの間においても、入力バッファ５１３から受信値格納用メモリ５１４に受信値D513は供給されない。従って、時刻ｔCから時間Ｃの間においても、フレーム＃ｉ−１の繰り返し復号は行われ続ける。そして、時刻ｔCから時間Ｃ後の時刻ｔDにおいて、フレーム＃ｉ−１の所定の回数の復号が完了すると、その復号は終了される。
【０２３５】
次に、図１９Ａに示すように、時刻ｔDにおいて、受信用メモリ４１７に対する、フレーム＃ｉの次のフレーム＃ｉ＋１の受信値D418の間欠的な入力が開始されると、時刻ｔAから時刻ｔDまでの時間Ａ乃至Ｃと同様に処理が行われる。
【０２３６】
即ち、時刻ｔDから時刻ｔEまでの時間Ａの間、図１９Ｆ乃至図１９Ｈに示すように、時刻ｔBから時刻ｔDまでの間に入力バッファ５１３に書き込まれたフレーム＃ｉの受信値D512の読み出し、および、その受信値D512の受信値格納用メモリ５１４への転送が行われるとともに（図中、Ri）、受信値格納用メモリ５１４からの６つの受信値D419の書き込みが行われる（図中、Wi）。また、図１９Ｂに示すように、フレーム＃ｉ＋１の実際の値が受信される時刻ｔD´から時刻ｔEまでの間、プリバッファ５１１は、フレーム＃ｉ＋１の受信値D418の書き込みのみを行い（図中、Wi+1）、図１９Ｄに示すように、スイッチ５１２は、入力バッファ５１３からの制御信号D515に応じて、プリバッファ５１１を選択するので、図１９Ｃと図１９Ｅに示すように、プリバッファ５１１から入力バッファ５１３には何も供給されない。
【０２３７】
そして、図１９Ｂ乃至図１９Ｆに示すように、時刻ｔEから時刻ｔFまでの時間Ｂおよび時刻ｔFから時刻ｔGまでの時間Ｃの間、時刻ｔDからプリバッファ５１１に書き込まれるフレーム＃ｉ＋１の受信値D418と、プリバッファ５１１に書き込まれずに直接供給されるフレーム＃ｉ＋１の受信値D418が入力バッファ５１３に書き込まれ（図中、Wi+1）、この間、フレーム＃ｉの復号が所定の回数繰り返される(図中、繰り返し復号＃ｉ)。
【０２３８】
以上のように、受信値D418は間欠的に供給されるので、連続的にプリバッファ５１１から読み出される、時間ＡとＢの間に受信される各フレームの受信値D418の無効時間を利用して、その無効時間以内であれば、入力バッファ５１３から受信値格納用メモリ５１４に受信値D513を転送することができる。従って、受信用メモリ４１７では、入力バッファ５１３と受信値格納用メモリ５１４を直列に接続することができ、その結果、上述したように回路規模を削減することができる。
【０２３９】
なお、受信値D513を転送する時間Ａが、時間ＢおよびＣと比較して十分に短くなるように設計することは容易である。この設計により、時間Ａが長いことによる復号劣化を抑制することができる。
【０２４０】
次に、図２０を参照して、図１８の受信用メモリ４１７における受信値処理について説明する。この受信値処理は、例えば、各フレームの受信値D418が受信用メモリ４１７に間欠的に入力されたとき、開始される。
【０２４１】
ステップＳ２１において、プリバッファ５１１は、間欠的に入力される受信値D418の書き込みを開始する。ステップＳ２２において、スイッチ５１２は、前のフレームに対するステップＳ３１の処理で、入力バッファ５１３から制御信号D515が入力されたかどうかを判定する。
【０２４２】
ステップＳ２２において、制御信号D515が入力されていないと判定された場合、即ち、前のフレームの受信値D512の入力バッファ５１３への書き込みが終了していない場合、スイッチ５１２は、制御信号D515が入力されるまで待機する。一方、ステップＳ２２において、制御信号D515が入力されたと判定された場合、即ち、前のフレームの受信値D512の入力バッファ５１３への書き込みが終了した場合、ステップＳ２３において、スイッチ５１２は、その制御信号D515に応じて、プリバッファ５１１と入力バッファ５１３を接続する。
【０２４３】
ステップＳ２４において、プリバッファ５１１は、制御信号D515に応じて、既に書き込まれている受信値D418の受信値D511としての連続的な読み出しを開始する。即ち、プリバッファ５１１は、受信値D418の書き込みを行うとともに、受信値D511の読み出しを行う。プリバッファ５１１から読み出された受信値D511は、スイッチ５１２に供給され、受信値D512として入力バッファ５１３に供給される。
【０２４４】
ステップＳ２５において、入力バッファ５１３は、スイッチ５１２を介してプリバッファ５１１から供給される受信値D512の書き込みを開始する。ステップＳ２６において、プリバッファ５１１は、プリバッファ５１１が空になったかどうか、即ち、プリバッファ５１１に書き込まれた受信値D418がすべて読み出されたかどうかを判定し、プリバッファ５１１が空になっていないと判定した場合、空になるまで待機する。
【０２４５】
一方、ステップＳ２６において、プリバッファ５１１が空になったと判定された場合、ステップＳ２７において、プリバッファ５１１は、受信値D418の書き込みと読み出しを終了する。ステップＳ２８において、プリバッファ５１１は、制御信号D514をスイッチ５１２に出力する。ステップＳ２９において、スイッチ５１２は、プリバッファ５１１から供給される制御信号D514に応じて、端子５１２Ａと入力バッファ５１３を接続する。
【０２４６】
ステップＳ３０において、入力バッファ５１３は、1フレーム分の受信値D512が書き込まれたかどうか、即ち、入力バッファ５１３の空き容量がゼロになったかどうかを判定する。ステップＳ３０で1フレーム分の受信値D512がまだ書き込まれていないと判定された場合、１フレーム分の受信値D512がすべて書き込まれるまで待機する。
【０２４７】
一方、ステップＳ３０で1フレーム分の受信値D512が書き込まれたと判定された場合、ステップＳ３１において、入力バッファ５１３は、制御信号D515をプリバッファ５１１とスイッチ５１２に出力する。この制御信号D515は、いま入力バッファ５１３に書き込まれた受信値D512に対応するフレームの次のフレームに対する、ステップＳ２２の処理で、スイッチ５１２に入力されたかどうかが判定される。
【０２４８】
ステップＳ３２において、入力バッファ５１３は、書き込まれている1フレーム分の受信値D512を受信値D513として読み出し、その受信値D513の受信値格納用メモリ５１４への転送を開始する。
【０２４９】
ステップＳ３３において、受信値格納用メモリ５１４は、入力バッファ５１３から転送されてきた受信値D513の書き込みを開始する。ステップＳ３４において、入力バッファ５１３は、1フレーム分の受信値D513の転送が完了したかどうか、即ち、書き込まれている受信値D513のすべてを転送したかどうかを判定し、1フレーム分の受信値D513の転送がまだ完了していないと判定した場合、転送が完了するまで待機する。
【０２５０】
一方、ステップＳ３４で1フレーム分の受信値D513の転送が完了したと判定された場合、ステップＳ３５において、入力バッファ５１３は、受信値D513の転送を終了する。ステップＳ３６において、受信値格納用メモリ５１４は、入力バッファ５１３から転送されてきた受信値D513の書き込みを終了する。
【０２５１】
ステップＳ３７において、受信値格納用メモリ５１４は、書き込まれた受信値D513を、ワード単位で６つずつ読み出し、受信値D419として、計算部４１５に出力する。そして、処理は終了する。
【０２５２】
次に、図２１を参照して、図１２の復号装置４００における復号処理について説明する。この復号処理は、例えば、受信用メモリ４１７から各フレームの受信値D419が６つ単位で読み出されたとき、開始される。
【０２５３】
ステップＳ４９において、制御部４１８は、復号途中結果格納用RAM５０２および５０３（図１６）のうちのいずれか１つを読み出しメモリとして選択し、その選択を表す制御信号D4224をスイッチ５０４に供給する。スイッチ５０４は、制御信号D4224に基づいて、復号途中結果格納用RAM５０２または５０３を選択し、その選択した復号途中結果格納用RAM５０２または５０３から６つ単位で供給される復号途中結果D503またはD504を、復号途中結果D413としてサイクリックシフト回路４１４と計算部４１２に供給する。
【０２５４】
ステップＳ４９の処理後は、ステップＳ５０に進み、サイクリックシフト回路４１４は、復号途中結果格納用メモリ４１３のスイッチ５０４から供給される６つの復号途中結果D413（uj）をサイクリックシフトし、計算部４１５に供給する。
【０２５５】
具体的には、サイクリックシフト回路４１４には、復号途中結果格納用メモリ４１３から６つ単位で復号途中結果D413が供給されるとともに、制御部４１８から、その復号途中結果D413に対応するMatrixデータを表す制御信号D423が供給される。サイクリックシフト回路４１４は、制御信号D423を基に、６つの復号途中結果D413をサイクリックシフトし、その結果を復号途中結果D414として、計算部４１５に供給する。
【０２５６】
ステップＳ５１において、計算部４１５は、第２の演算を行い、その演算の結果である復号途中結果D415をスイッチ４１６に供給する。
【０２５７】
具体的には、計算部４１５には、ステップＳ５０でサイクリックシフト回路４１４から６つの復号途中結果D414が供給されるとともに、受信用メモリ４１７から６つの受信値D419が供給され、復号途中結果D414と受信値D419が、計算部４１５の計算器４１５1乃至４１５6それぞれに１つずつ供給される。さらに、計算部４１５には、制御部４１８から制御信号D424が供給され、その制御信号D424が計算器４１５1乃至４１５6に供給される。
【０２５８】
計算器４１５1乃至４１５6は、復号途中結果D414と受信値D419を用いて、制御信号D424に基づいて、式（５）にしたがって、それぞれ第２の演算を行い、その第２の演算の結果得られる検査行列Hの列に対応する復号途中結果D415(v)をスイッチ４１６に供給する。
【０２５９】
なお、受信用メモリ４１７から供給された受信値D419に対して、まだ第１の演算が行われておらず、復号途中結果格納用メモリ４１３に復号途中結果D412が格納されていない場合、計算部４１５は、復号途中結果ujを初期値に設定し、第２の演算を行う。
【０２６０】
ステップＳ５２において、制御部４１８は、予め設定された所定の回数だけ復号が行われたかどうか、即ち、予め設定された所定の回数だけ第１の演算と第２の演算が行われたかどうかを判定する。ステップＳ５２で、所定の回数だけまだ復号が行われていないと判定された場合、ステップＳ５３において、スイッチ４１６は、計算部４１５から供給される６つの復号途中結果D415(ｖ)を復号途中結果格納用メモリ４１０に供給する。
【０２６１】
ステップＳ５４において、復号途中結果格納用メモリ４１０は、スイッチ４１６から供給された６つの復号途中結果D415(v)を、同一アドレスに格納する。
【０２６２】
ステップＳ５５において、制御部４１８は、計算部４１５により、検査行列Hの列に対応する全ての復号途中結果D415が演算されたかどうかを判定し、全ての復号途中結果D415が演算されていないと判定した場合、ステップＳ４９に戻り、上述した処理を繰り返す。
【０２６３】
一方、ステップＳ５５において、制御部４１８は、計算部４１５により、検査行列Hの列に対応する全ての復号途中結果D415が演算されたと判定した場合、ステップＳ５６において、サイクリックシフト回路４１１は、制御部４１８から供給される制御信号D420を基に、復号途中結果格納用メモリ４１０から供給される６つの復号途中結果D410(v)をサイクリックシフトし、その結果を6つ単位で復号途中結果D411として、計算部４１２に供給する。
【０２６４】
ステップＳ５７において、計算部４１２は、第１の演算を行い、その第１の演算の結果である復号途中結果D412を復号途中結果格納用メモリ４１３に供給する。
【０２６５】
具体的には、計算部４１２には、ステップＳ５６でサイクリックシフト回路４１１から６つの復号途中結果D411(v)が供給されるとともに、後述するステップＳ５９で既に格納された前回の計算部４１２による第１の演算の結果得られた６つの復号途中結果D413(uj)が供給され、その復号途中結果D411とD413が、計算部４１２の計算器４１２1乃至４１２6のそれぞれに１つずつ供給される。さらに、計算部４１２には、制御部４１８から制御信号D421が供給され、その制御信号D421が計算器４１２1乃至４１２6に供給される。
【０２６６】
計算器４１２1乃至４１２6は、それぞれ復号途中結果D411とD413を用いて、制御信号D421に基づいて、式（７）と式（８）にしたがって、それぞれ第１の演算を行い、その第１の演算の結果得られる復号途中結果D412（uj）を復号途中結果格納用メモリ４１３に供給する。
【０２６７】
なお、受信用メモリ４１７から供給された受信値D419に対して、まだ第１の演算が行われておらず、復号途中結果格納用メモリ４１３に復号途中結果D412が格納されていない場合、計算部４１２は復号途中結果udvを０に設定する。具体的には、例えば、受信値D419に対する復号を行う前に、復号途中結果格納用メモリ４１３が０に初期化されるか、または計算部４１２が復号途中結果格納用メモリ４１３からの入力を０にマスクする。
【０２６８】
ステップＳ５８において、制御部４１８は、復号途中結果格納用RAM５０２および５０３のうちのいずれか１つを格納メモリとして選択し、その選択を表す制御信号D4221をスイッチ５０１（図１６）に供給する。スイッチ５０１は、制御信号D4221に基づいて、６つの復号途中結果D412を格納する復号途中結果格納用RAM５０２または５０３を選択し、その選択した復号途中結果格納用RAM５０２または５０３に、復号途中結果D412を復号途中結果D501またはD502として供給する。
【０２６９】
ステップＳ５９において、復号途中結果格納用RAM５０２または５０３は、ステップＳ５８でスイッチ５０１から供給された６つの復号途中結果D501またはD502(uj)を、同一のアドレスに格納する。
【０２７０】
ステップＳ６０において、制御部４１８は、計算部４１２により、検査行列Hの全ての1に対応する復号途中結果D412が演算されたかどうかを判定し、全ての復号途中結果D412が演算されていないと判定した場合、処理はステップＳ５６に戻り、上述した処理が繰り返される。
【０２７１】
一方、ステップＳ６０において、計算部４１２により、全ての１に対応する復号途中結果D412が演算されたと判定された場合、処理はステップＳ４９に戻り、上述した処理が繰り返される。
【０２７２】
また、ステップＳ５２で所定の回数だけ復号が行われたと判定された場合、ステップＳ６１において、制御部４１８は、制御信号D425をスイッチ４１６に出力する。ステップＳ６２において、スイッチ４１６は、直前のステップＳ５１で得られる復号途中結果D415を、最終的な復号結果D417として出力する。
【０２７３】
図２２は、本発明を適用した復号装置の第２の実施の形態の構成例を示している。
【０２７４】
図２２の復号装置６００は、復号途中結果格納用メモリ４１０、サイクリックシフト回路４１１、６つの計算器４１２1乃至計算器４１２6からなる計算部４１２、復号途中結果格納用メモリ４１３、サイクリックシフト回路４１４、６つの計算器４１５1乃至計算器４１５6からなる計算部４１５、スイッチ４１６、受信用メモリ６１１、および制御部６１２から構成され、制御部６１２は、受信用メモリ６１１から供給される、復号の終了を要求する復号終了要求信号D601に応じて、制御信号D425をスイッチ４１６に供給する。なお、図１２と同一のものには同一の符号を付してあり、説明は繰り返しになるので省略する。
【０２７５】
受信用メモリ６１１には、図１２の受信用メモリ４１７と同様に、受信値D418が入力され、受信用メモリ６１１は、その受信値D418を格納する。そして、受信用メモリ６１１は、既に格納している受信値D418を、バリアブルノード演算に必要となる順番に６つずつ読み出し、受信値D419として計算部４１５に供給する。また、受信用メモリ６１１は、いまの復号対象の次のフレームの受信値D418が読み出し可能な状態となったとき、復号終了要求信号D601を制御部６１２に供給する。なお、受信用メモリ６１１の詳細については、後述する図２３を参照して説明する。
【０２７６】
制御部６１２は、受信用メモリ６１１から復号終了要求信号D601が供給されるまで繰り返して復号が行われるように、各部を制御する。具体的には、制御部６１２は、制御信号D420をサイクリックシフト回路４１１に、制御信号D421を計算部４１２に供給することにより、それぞれを制御する。また、制御部６１２は、制御信号D422を復号途中結果格納用メモリ４１３に、制御信号D423をサイクリックシフト回路４１４に、制御信号D424を計算部４１５にそれぞれ供給することにより、それぞれを制御する。さらに、制御部６１２は、復号終了要求信号D601に応じて、制御信号D425をスイッチ４１６に供給することにより、復号終了要求信号D601が供給されるまでに繰り返し行われた、第２の演算の最後の結果として得られる復号途中結果D415を、復号結果D417として出力させるように、スイッチ４１６を制御する。
【０２７７】
図２３は、図２２の受信用メモリ６１１の詳細構成例を示している。
【０２７８】
図２３の受信用メモリ６１１は、プリバッファ５１１、スイッチ５１２、受信値格納用メモリ５１４、および入力バッファ６２１により構成される。なお、図２３において、図１８と同一のものには同一の符号を付してあり、説明は繰り返しになるので省略する。
【０２７９】
入力バッファ６２１の記憶容量は、図１８の入力バッファ５１３と同様に、例えば、符号長と量子化ビット数の乗算値であり、入力バッファ６２１は、スイッチ５１２により入力される受信値D512を、一時的に１フレーム分記憶する。なお、入力バッファ６２１のビット幅は、入力バッファ５１３と同様に、受信値格納用メモリ５１４のビット幅の1/N倍であり、ワード数は、受信値格納用メモリ５１４のN倍であるものとする。
【０２８０】
入力バッファ６２１は、1フレーム分の受信値D512の書き込みを完了した場合、その受信値D512に対応するフレームを復号対象とするため、そのフレームの１つ前のフレームの復号終了要求信号D601を制御部６１２に供給する。その後、所定の時間が経過したとき、入力バッファ６２１は、いま書き込みが完了したフレームの前のフレームの復号が終了されたと判定し、プリバッファ５１１とスイッチ５１２に制御信号D515を入力するとともに、記憶している１フレーム分の受信値D512を、受信値D513として読み出し、受信値格納用メモリ５１４に転送する。これにより、復号対象とするフレームが変更される。
【０２８１】
次に、図２４を参照して、図２３の受信用メモリ６１１におけるタイミングについて説明する。
【０２８２】
なお、図２４Ａ乃至図２４Ｅは、図１９Ａ乃至図１９Ｅと同様であるので、説明は適宜省略する。
【０２８３】
図２４Ａに示すように、時刻ｔAにおいて、受信用メモリ６１１に対する、フレーム＃ｉの受信値D418の間欠的な入力が開始される、即ち、フレーム＃ｉ−１の入力バッファ６２１への書き込みが完了すると、図２４Ｈに示すように、入力バッファ６２１は、フレーム＃ｉ−１の前のフレーム＃ｉ−２の復号終了要求信号D601を制御部６１２に供給し、図２４Ｆに示すように、入力バッファ６２１は、所定の時間Ｄが経過するまで待機する。
【０２８４】
そして、所定の時間Ｄが経過した時刻ｔHにおいて、図２４Ｆに示すように、入力バッファ６２１は、書き込みが完了しているフレーム＃ｉ−１の受信値D512の読み出し、および、その受信値D512の受信値格納用メモリ５１４への転送を開始し（図中、Ri-1）、これにより、図２４Ｇに示すように、受信値格納用メモリ５１４には、フレーム＃ｉ−１の受信値D512が受信値D513として供給される。そして、図２４Ｉに示すように、受信値格納用メモリ５１４は、入力バッファ６２１から供給される、フレーム＃ｉ−１の受信値D513の書き込みを開始する（図中、Wi-1）。
【０２８５】
なお、時刻ｔAから時間Ａ後の時刻ｔBから、時刻ｔDまでの時間ＢおよびＣの間の処理は、図１９Ａ乃至図１９Ｈで示した場合と同様であるので、説明は省略する。
【０２８６】
次に、図２４Ａに示すように、時刻ｔDにおいて、受信用メモリ６１１に対する、フレーム＃ｉ＋１の受信値D418の間欠的な入力が開始されると、時刻ｔAから時刻ｔDまでの時間Ａ乃至Ｃと同様に処理が行われる。
【０２８７】
即ち、時刻ｔDにおいて、図２４Ｈに示すように、入力バッファ６２１は、時刻ｔBから時刻ｔDまでに書き込んだフレーム＃ｉの前のフレーム＃ｉ−１の復号終了要求信号D601を制御部６１２に供給し、図２４Ｆに示すように、入力バッファ６２１は、所定の時間Ｄが経過するまで待機する。
【０２８８】
そして、所定の時間Ｄが経過した時刻ｔJにおいて、入力バッファ６２１は、時刻ｔBから時刻ｔDまでの間に書き込んだフレーム＃ｉの受信値D512の読み出し、および、その受信値D512の受信値格納用メモリ５１４への転送を開始し（図中、Ri）、図２４Ｉに示すように、受信値格納用メモリ５１４は、入力バッファ６２１から供給される、フレーム＃ｉの受信値D513の書き込みを開始する（図中、Wi）。なお、フレーム＃ｉ−１の復号は、図２４Ｉに示すように、復号終了要求信号D601が出力された後終了される。図２４の例では、復号終了要求信号D601が出力されてから、所定の時間Ｄが経過した時刻ｔJに、復号が終了されている。
【０２８９】
以上のように、受信値D418は間欠的に供給されるので、連続的にプリバッファ５１１から読み出される、時間ＡとＢの間に受信される各フレームの受信値D418の無効時間を利用して、その無効時間以内であれば、復号終了要求信号D601を出力して所定の時間待機し、その後、入力バッファ６２１から受信値格納用メモリ５１４に受信値D513を転送することができる。
【０２９０】
また、受信用メモリ６１１は、復号終了要求信号D601を制御部６１２に供給し、制御部６１２は、その復号終了要求信号D601が供給されるまで復号を繰り返して行うように各部を制御するので、可能な限り多くの回数の復号を行うことができる。その結果、予め設定された所定の回数だけ復号を繰り返し行う場合に比べて、さらに復号性能を向上させることができる。また、復号の回数を予め設定しておく手間を省くことができる。
【０２９１】
次に、図２５を参照して、図２３の受信用メモリ６１１における受信値処理について説明する。この受信値処理は、例えば、各フレームの受信値D418が受信用メモリ６１１に間欠的に入力されたとき、開始される。
【０２９２】
ステップＳ１１１乃至Ｓ１２１の処理は、図２０のステップＳ２１乃至Ｓ３１の処理と同様であるので、説明は省略する。
【０２９３】
ステップＳ１２２において、入力バッファ６２１は、復号終了要求信号D601を制御部６１２に出力する。ステップＳ１２３において、入力バッファ６２１は、ステップＳ１２２で復号終了要求信号D601を出力してから、所定の時間が経過したかどうかを判定し、所定の時間が経過していないと判定した場合、所定の時間が経過するまで待機する。
【０２９４】
ステップＳ１２３において、ステップＳ１２２で復号終了要求信号D601を出力してから、所定の時間が経過したと判定された場合、ステップＳ１２４において、入力バッファ６２１は、図２０のステップＳ３２の処理と同様に、書き込まれている1フレーム分の受信値D512を受信値D513として読み出し、その受信値D513の受信値格納用メモリ５１４への転送を開始する。
【０２９５】
ステップＳ１２４乃至Ｓ１２９の処理は、図２０のステップＳ３２乃至Ｓ３７の処理と同様であるので、説明は省略する。
【０２９６】
次に、図２６を参照して、図２２の復号装置６００における復号処理について説明する。この復号処理は、例えば、受信用メモリ６１１から各フレームの受信値D419が６つ単位で読み出されたとき、開始される。
【０２９７】
ステップＳ１４９乃至Ｓ１５１の処理は、図２１のステップＳ４９乃至Ｓ５１の処理と同様であるので説明は省略する。
【０２９８】
ステップＳ１５２において、制御部６１２は、受信用メモリ６１１の入力バッファ６２１から復号終了要求信号が供給されたかどうかを判定し、復号終了要求信号が供給されていないと判定した場合、ステップＳ１５３において、スイッチ４１６は、図２１のステップＳ５３の処理と同様に、計算部４１５から供給される６つの復号途中結果D415(ｖ)を復号途中結果格納用メモリ４１０に供給する。ステップＳ１５４乃至Ｓ１６０の処理は、図２１のステップＳ５４乃至Ｓ６０の処理と同様であるので、説明は省略する。
【０２９９】
一方、ステップＳ１５２で入力バッファ６２１から復号終了要求信号が供給されたと判定された場合、ステップＳ１６１において、制御部６１２は、図２１のステップＳ６１の処理と同様に、制御信号D425を出力する。ステップＳ１６２において、スイッチ４１６は、図２１のステップＳ６２の処理と同様に、直前のステップＳ５１で得られる復号途中結果D415を、最終的な復号結果D417として出力する。
【０３００】
なお、図１２の復号装置４００および図２２の復号装置６００では、第１の演算と第２の演算を繰り返し行うことにより復号を行ったが、チェックノード演算とバリアブルノード演算を繰り返し行うことにより復号を行うようにすることもできる。
【０３０１】
また、上述の場合には、説明を簡単にするために、Ｐが6の場合、即ち、検査行列Hを構成する構成行列の行数および列数が6の場合を例に挙げたが、構成行列の行数および列数Ｐは必ずしも6である必要はなく、検査行列Hによって異なる値を取ることもあり得る。例えば、Ｐは360や392であってもよい。
【０３０２】
例えば、Ｐが360である場合、量子化ビット数が5ビットであり、DVB-S2規格に準拠した、符号長が64800であるLDPC符号を復号するとすると、図１８の受信用メモリ４１７や図２３の受信用メモリ６１１では、受信値格納用メモリ５１４のビット幅が、1800(=360×5)ビットとなり、ワード数が、180(=64800/360)ワードとなる。即ち、受信値格納用メモリ５１４は、ビット幅とワード数の比が10対1の多ビット小ワードのメモリとなる。ここで、例えばNが10であるとすると、入力バッファ５１３や６２１のビット幅は、180(=1800/10)ビットとなり、ワード数は1800（=180×10）ワードとなる。即ち、入力バッファ５１３は、ビット幅とワード数の比が1対10の小ビット多ワードのメモリとなる。
【０３０３】
これに対して、従来の図１１の受信用メモリ２００では、上述したように、受信値格納用メモリ２１２および２１３の両方のビット幅が、1800(=360×5)ビットとなり、ワード数が180(=5×1800/360)ワードとなる。即ち、受信値格納用メモリ２１２および２１３は、両方とも、ビット幅とワード数の比が10対1の多ビット小ワードのメモリとなる。
【０３０４】
以上のように、図１８の受信用メモリ４１７や図２３の受信用メモリ６１１では、多ビット小ワードの受信値格納用メモリ５１４と、小ビット多ワードの入力バッファ５１３を1つずつ設ければよいので、図１１に示した多ビット小ワードの受信値格納用メモリ２１２および２１３を両方設ける必要のある受信用メモリ２００に比べて、受信用メモリ４１７（６１１）を構成するマクロの数を削減することができる。その結果、受信用メモリ４１７（６１１）の回路規模を削減することができる。
【０３０５】
また、図１８の受信用メモリ４１７および図２３の受信用メモリ６１１は、全ノードの演算を同時に行うことによって復号を行う場合(full parallel decoding)の復号装置にも適用することができる。
【０３０６】
この復号装置の実装法については、例えば、C. Howland and A. Blanksby, "Parallel Decoding Architectures for Low Density Parity Check Codes", Symposium on Circuits and Systems, 2001に記載されている。
【０３０７】
図２７は、全ノードの演算を同時に行う本発明を適用した復号装置の第３の実施の形態の構成例を示している。
【０３０８】
なお、ここでも、図１３の検査行列Hで表現される符号（符号化率2/3、符号長108）を復号するものとする。
【０３０９】
図２７の復号装置1100では、枝用メモリ1202または1206から、３２３個ある枝に対応するメッセージデータを全て同時に読み出し、そのメッセージデータを用いて、３２３個の枝に対応する新たなメッセージデータを演算する。さらに、その演算の結果求められた新たなメッセージデータが全て同時に後段の枝用メモリ1206または1202に格納されていく。そして、図２７の復号装置1100を繰り返し用いることで繰り返し復号が実現される。
【０３１０】
図２７において、復号装置1100は、１つの受信用メモリ1205、２つの枝入れ替え装置1200および1203、２つの枝用メモリ1202および1206、３６個のチェックノード計算器12011乃至120136、１０８個のバリアブルノード計算器12041乃至1204108からなる。以下、各部について詳細に説明する。
【０３１１】
枝用メモリ1206は、前段のバリアブルノード計算器12041乃至1204108からのメッセージD12061乃至D1206108を全て同時に格納し、次の時刻（次のクロックのタイミング）に、メッセージD12061乃至D1206108を、メッセージD12071乃至D1207108として読み出し、次段の枝入れ替え装置1200に、メッセージD1200(D12001乃至D1200108)として供給する。枝入れ替え装置1200は、枝用メモリ1206から供給されたメッセージD12001乃至D1200108の順番を、図１３の検査行列Hにしたがって並び替え、チェックノード計算器12011乃至120136に、メッセージD12011乃至D120136として供給する。
【０３１２】
チェックノード計算器12011乃至120136は、枝入れ替え装置1200から供給されるメッセージD12011乃至D120136を用いて式（７）にしたがって演算を行い、その演算の結果得られるメッセージD12021乃至D120236を、枝用メモリ1202に供給する。
【０３１３】
枝用メモリ1202は、前段のチェックノード計算器12011乃至120136から供給されるメッセージD12021乃至D120236を全て同時に格納し、次の時刻に、そのすべてのメッセージD12021乃至D120236を、メッセージD12031乃至D120336として、次段の枝入れ替え装置1203に供給する。
【０３１４】
枝入れ替え装置1203は、枝用メモリ1202から供給されたメッセージD12031乃至D120336の順番を図１３の検査行列Hにしたがって並び替え、バリアブルノード計算器12041乃至1204108に、メッセージD12041乃至D1204108として供給する。
【０３１５】
バリアブルノード計算器12041乃至1204108は、枝入れ替え装置1203から供給されるメッセージD12041乃至D1204108と、受信用メモリ1205から供給される受信値D12051乃至D1205108を用いて式（１）にしたがって演算を行い、その演算の結果得られるメッセージD12061乃至D1206108を、次段の枝用メモリ1206に供給する。
【０３１６】
受信用メモリ1205は、図１８の受信用メモリ４１７または図２３の受信用メモリ６１１と同様に構成される。即ち、図示は省略するが、受信用メモリ1205は、プリバッファ、スイッチ、入力バッファ、および受信値格納用メモリにより構成され、受信値格納用メモリのビット幅は、バリアブルノード数である108個と量子化ビット数の乗算値であり、入力バッファのビット幅は、その乗算値の1/N倍である。
【０３１７】
受信用メモリ1205には、通信路を通して受信されたLDPC符号から計算された、符号ビットの０らしさを表す受信LLRである受信値D12051乃至D1205108が入力される。受信用メモリ1205は、その受信値12051乃至D1205108を格納する。そして、受信用メモリ1205は、既に格納している108個の受信値D12051乃至D1205108をすべて同時に読み出し、受信値D12051乃至D1205108としてバリアブルノード計算器12041乃至1204108に供給する。なお、受信用メモリ1205が図２３の受信用メモリ６１１と同様に構成される場合には、復号終了要求信号が、各部を制御する制御部（図示せず）に出力される。
【０３１８】
図２８は、チェックノード演算を同時に行う図２７のチェックノード計算器1201m（ｍ＝１，２，・・・，３６）の構成例を示している。
【０３１９】
図２８のチェックノード計算器1201mでは、図９のチェックノード計算器１０１と同様にして、式（７）のチェックノード演算が行われるが、そのチェックノード演算が、すべての枝について同時に行われる。
【０３２０】
即ち、図２８のチェックノード計算器1201mでは、枝入れ替え装置1200から供給される図１３の検査行列Hの各列に対応するバリアブルノードからのメッセージD12211乃至D12219（vi）が全て同時に読み込まれ、それぞれの下位５ビットである絶対値D1222乃至D12229（|vi|）がLUT12211乃至12219にそれぞれ供給される。また、メッセージD12211乃至D12219（vi）の最上位ビットである１ビットの符号ビットD12231乃至D12239が、EXOR回路12261乃至12269にそれぞれ供給されるとともに、EXOR回路1225に供給される。
【０３２１】
LUT12211乃至12219は、絶対値D1222乃至D12229（|vi|）に対して、式（７）におけるφ(|vi|)の演算を行った５ビットの演算結果D12241乃至D12249（φ（|vi|））をそれぞれ読み出し、それぞれを減算器12231乃至12239に供給する。また、LUT12211乃至12219は、演算結果D12241乃至D12249（φ（|vi|））を加算器1222に供給する。
【０３２２】
加算器1222は、演算結果D12241乃至D12249（φ（|vi|））の値の総和（１行分の演算結果の総和）を演算し、９ビットの演算結果D1225（ｉ＝１から９のΣφ（|vi|））を、減算器12231乃至12239に供給する。減算器12231乃至12239は、演算結果D1225から、演算結果D12241乃至D12249（φ（|vi|））をそれぞれ減算し、５ビットの減算値D12271乃至D12279を、LUT12241乃至12249に供給する。即ち、減算器12231乃至12239は、全ての枝からのメッセージviから求められたφ(|vi|)の積算値から、求めたい枝からのメッセージviから求められたφ(|vi|)を減算して、その減算値D12271乃至D12279（ｉ＝１から８までのΣφ(|vi|)）をLUT12241乃至12249にそれぞれ供給する。LUT12241乃至12249は、減算値D12271乃至D12279に対して、式（７）におけるφ-1(Σφ(|vi|))の演算を行った５ビットの演算結果D12281乃至D12289を読み出して出力する。
【０３２３】
一方、EXOR回路1225は、全ての符号ビットD12231乃至D12239の排他的論理和を演算することにより、符号ビットD12231乃至D12239の乗算を行い、１ビットの乗算値D1226（１行分の符号ビットの乗算値（ｉ＝１から９までのΠsign（vi）））をEXOR回路12261乃至12269にそれぞれ供給する。EXOR回路12261乃至12269は、乗算値D1226と符号ビットD12231乃至D12239それぞれとの排他的論理を演算することにより、乗算値D1226を、符号ビットD12231乃至D12239それぞれで除算した１ビットの除算値D12291乃至D12299（ｉ＝１から８までのΠsign（vi））を求めて出力する。
【０３２４】
チェックノード計算器1201mでは、LUT12241乃至12249から出力された５ビットの演算結果D12281乃至D12289それぞれを下位５ビットとするとともに、EXOR回路12261乃至12269から出力された除算値D12291乃至D12299それぞれを最上位ビットとする合計６ビットが、チェックノード演算の結果得られるメッセージD12301乃至D12309として出力される。
【０３２５】
以上のように、チェックノード計算器1201mでは、式（７）の演算が行われ、メッセージujが求められる。
【０３２６】
なお、図２８では、各メッセージが符号ビットを合わせて合計６ビットに量子化されているものとして、チェックノード計算器1201mを表している。また、図２８の回路は１つのチェックノードに相当する。ここで処理の対象としている図１３の検査行列Hについては、その行数である３６行のチェックノードが存在するため、図２７の復号装置1100は、図２８に示したようなチェックノード計算器1201mを３６個有している。
【０３２７】
また、図２８のチェックノード計算器1201mでは、９個のメッセージを同時に計算することができる。そして、ここで処理の対象としている図１３の検査行列Hの行の重みは、第１行が８で、第２乃至第３６行が９であるため、即ち、チェックノードに供給されるメッセージの数が、８のケースが１つと、９のケースが２９あるため、チェックノード計算器12011は、図２８の回路と同様の８つのメッセージを同時に計算することができる回路構成となっており、残りのチェックノード計算器12012乃至120136は、図２８の回路と同一構成となっている。
【０３２８】
図２９は、バリアブルノード演算を同時に行う図２７のバリアブルノード計算器1204p（ｐ＝１，２，・・・，１０８）の構成例を示している。
【０３２９】
図２９のバリアブルノード計算器1204pでは、図１０のバリアブルノード計算器１０３と同様にして、式（１）のバリアブルノード演算が行われるが、そのバリアブルノード演算が、すべての枝について同時に行われる。
【０３３０】
即ち、図２９のバリアブルノード計算器1204pでは、枝入れ替え装置1203から供給される、検査行列Hの各行に対応するチェックノードからの６ビットのメッセージD12511乃至D12515（メッセージuj）が全て同時に読み込まれ、それぞれ加減算器12521乃至12525に供給されるとともに、加算器1251に供給される。また、バリアブルノード計算器1204pには、受信用メモリ1205から受信値D1271が供給され、その受信値D1271は、加減算器12521乃至12525に供給される。
【０３３１】
加算器1251は、全てのメッセージD12511乃至D12515（メッセージuj）を積算し、９ビットの積算値D1252（1列分のメッセージの総和値（ｊ＝１から５までのΣuj））を加減算器12521乃至12525に供給する。加減算器12521乃至12525は、積算値D1252から、メッセージD12511乃至D12515（メッセージuj）をそれぞれ減算する。即ち、加減算器12521乃至12525は、全ての枝からのメッセージujの積算値D1252から、求めたい枝からのメッセージD12511乃至D12515（メッセージuj）をそれぞれ減算して、その減算値（ｊ＝１から４までのΣuj）を求める。
【０３３２】
さらに、加減算器12521乃至12525は、減算値（ｊ＝１から４までのΣuj）に、受信値D1271（u0i）を加算して、６ビットの加算値D12531乃至D12535を、バリアブルノード演算の結果として出力する。
【０３３３】
以上のように、バリアブルノード計算器1204pでは、式（１）の演算が行われ、メッセージviが求められる。
【０３３４】
なお、図２９では、各メッセージが符号ビットを合わせて合計６ビットに量子化されているものとして、バリアブルノード計算器1204pを表している。また、図２９の回路は１つのバリアブルノードに相当する。ここで処理の対象としている図１３の検査行列Hについては、その列数である１０８列のバリアブルノードが存在するから、図２７の復号装置1100は、図２９に示したような回路を１０８個有している。
【０３３５】
また、図２９のバリアブルノード計算器1204pでは、５個のメッセージを同時に計算することができる。そして、ここで処理の対象としている図１３の検査行列Hは、重みが５，３，２，１の列が、それぞれ、１８列、５４列、３５列、１列あるので、バリアブルノード計算器12041乃至1204108のうちの１８個は、図２９の回路と同一構成となっており、残りの５４個、３５個、１個は、図２９の回路と同様の３，２，１つのメッセージをそれぞれ同時に計算することができる回路構成となっている。
【０３３６】
なお、図示しないが、図２７の復号装置1100においても、図８における場合と同様に、復号の最終段においては、式（１）のバリアブルノード演算の代わりに、式（５）の演算が行われ、その演算結果が最終的な復号結果として出力される。
【０３３７】
図２７の復号装置1100によれば、３２３個ある枝に対応するメッセージすべてを１クロックで同時に計算することができる。
【０３３８】
図２７の復号装置1100を繰り返し用いて復号する場合には、チェックノード演算とバリアブルノード演算とを交互に行い、１回の復号を２クロックで行うことができる。従って、例えば、５０回の復号を行うためには、符号長である108個の符号からなる１フレーム分の符号語を、受信値として受信する間に、2×50=100クロック動作すれば良いことになり、ほぼ受信周波数と同一の動作周波数でよいことになる。一般的に、LDPC符号は、符号長が数千から数万と大きいことから、図２７の復号装置1100を用いれば、復号回数を極めて多くすることができ、誤り訂正性能の向上を期待することができる。
【０３３９】
但し、図２７の復号装置1100は、タナーグラフのすべての枝に対応するメッセージの演算を、並列で行うため、回路規模が、符号長に比例して大きくなる。また、図２７の復号装置1100を、ある符号長の、ある符号化率の、ある検査行列Hを持つLDPC符号の復号を行う装置として構成した場合、その復号装置1100において、他の符号長や、他の符号化率、他の検査行列Hを持つLDPC符号の復号を行うことは困難となる。
【０３４０】
なお、本実施の形態では、符号長108、符号化率2/3のLDPC符号を用いたが、LDPC符号の符号長や符号化率は、どのような値であってもよい。
【０３４１】
また、検査行列Hが、構成行列の行数および列数Ｐの倍数でない場合は、検査行列Hの端数の外側にすべて０(all 0)の成分を付けてＰの倍数とみなして適用することができる場合がある。
【０３４２】
一般的に、LDPC符号は符号長が数千から数万と大きいため、Ｐの値も数百の大きさを持つものが使われる。その場合には、更に本発明に係る復号装置を用いる効果は大きくなる。
【０３４３】
なお、上述したLDPC符号を復号する復号装置は、例えば、（ディジタル）衛星放送を受信するチューナなどに適用することができる。
【図面の簡単な説明】
【０３４４】
【図１】LDPC符号の復号手順を説明するフローチャートである。
【図２】メッセージの流れを説明する図である。
【図３】LDPC符号の検査行列Hの例を示す図である。
【図４】検査行列Hのタナーグラフを示す図である。
【図５】バリアブルノードを示す図である。
【図６】チェックノードを示す図である。
【図７】LDPC符号の検査行列Hの例を示す図である。
【図８】ノード演算を１つずつ行うLDPC符号の復号装置の構成の一例を示すブロック図である。
【図９】図８のチェックノード計算器の詳細構成例を示すブロック図である。
【図１０】図８のバリアブルノード計算器の詳細構成例を示すブロック図である。
【図１１】２個のメモリが設けられた受信用メモリの構成の一例を示すブロック図である。
【図１２】本発明を適用した復号装置の第１の実施の形態の構成例を示すブロック図である。
【図１３】６×６単位に分割した検査行列Hの例を示す図である。
【図１４】図１２の計算器の詳細構成例を示すブロック図である。
【図１５】図１２の計算器の詳細構成例を示すブロック図である。
【図１６】図１２の復号途中結果格納用メモリの構成例を示すブロック図である。
【図１７】図１２の復号途中結果格納用RAMの動作を説明するタイミングチャートである。
【図１８】図１２の受信用メモリの詳細構成例を示している。
【図１９】図１８の受信用メモリにおけるタイミングを説明するタイミングチャートである。
【図２０】図１８の受信用メモリにおける受信値処理について説明するフローチャートである。
【図２１】図１２の復号装置における復号処理について説明するフローチャートである。
【図２２】本発明を適用した復号装置の第２の実施の形態の構成例を示すブロック図である。
【図２３】図２２の受信用メモリの詳細構成例を示すブロック図である。
【図２４】図２３の受信用メモリにおけるタイミングについて説明するタイミングチャートである。
【図２５】図２３の受信用メモリにおける受信値処理について説明するフローチャートである。
【図２６】図２２の復号装置における復号処理について説明するフローチャートである。
【図２７】本発明を適用した復号装置の第３の実施の形態の構成例を示すブロック図である。
【図２８】図２７のチェックノード計算器の構成例を示すブロック図である。
【図２９】図２７のバリアブルノード計算器の構成例を示すブロック図である。
【符号の説明】
【０３４５】
４００  復号装置，  ４１２，４１５  計算部，  ４１７  受信用メモリ，  ５１１  プリバッファ，  ５１３  入力バッファ，  ５１４  受信値格納用メモリ，  ６００  復号装置，  ６１１  受信用メモリ，  ６２１  入力バッファ，  １１００  復号装置，  １２０５  受信用メモリ，  １２０１  チェックノード計算器，  １２０４  バリアブルノード計算器
【図１】
2008278191.tif 000011
【図２】
2008278191.tif 000012
【図３】
2008278191.tif 000013
【図４】
2008278191.tif 000014
【図５】
2008278191.tif 000015
【図６】
2008278191.tif 000016
【図７】
2008278191.tif 000017
【図８】
2008278191.tif 000018
【図９】
2008278191.tif 000019
【図１０】
2008278191.tif 000020
【図１１】
2008278191.tif 000021
【図１２】
2008278191.tif 000022
【図１３】
2008278191.tif 000023
【図１４】
2008278191.tif 000024
【図１５】
2008278191.tif 000025
【図１６】
2008278191.tif 000026
【図１７】
2008278191.tif 000027
【図１８】
2008278191.tif 000028
【図１９】
2008278191.tif 000029
【図２０】
2008278191.tif 000030
【図２１】
2008278191.tif 000031
【図２２】
2008278191.tif 000032
【図２３】
2008278191.tif 000033
【図２４】
2008278191.tif 000034
【図２５】
2008278191.tif 000035
【図２６】
2008278191.tif 000036
【図２７】
2008278191.tif 000037
【図２８】
2008278191.tif 000038
【図２９】
2008278191.tif 000039