図面 (/)

技術 復号装置および復号方法

出願人 ソニー株式会社
発明者 横川峰志篠原雄二新谷修
出願日 2005年4月25日 (15年7ヶ月経過) 出願番号 2005-125963
公開日 2006年11月2日 (14年0ヶ月経過) 公開番号 2006-304130
状態 特許登録済
技術分野 符号誤り検出・訂正
主要キーワード 遅延回数 ビリーフ 深宇宙 確率伝播 受信用メモリ メッセージノード 除算値 イレギュラー
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2006年11月2日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (20)

課題

LDPC符号復号を、装置の大規模化を抑えつつ精度良く行う。

解決手段

チェックノード計算器171は、LDPC符号の復号のためのチェックノード演算であって、非線形関数φ(x)の演算および非線形関数の逆関数φ-1(x)の演算を含むチェックノード演算を行う。バリアブルノード計算器103は、LDPC符号の復号のためのバリアブルノードバリアブルノード演算を行う。そして、チェックノード計算器171およびバリアブルノード計算器103は、チェックノード演算およびバリアブルノード演算として行う処理のうちの、非線形関数φ(x)の演算後から逆関数φ-1(x)の演算までの処理では、第1の量子化値よりも精度の高い数値を表す第2の量子化値を使用し、他の処理では、第1の量子化値を使用する。本発明は、例えば、衛星放送を受信するチューナに適用できる。

概要

背景

近年、例えば、移動体通信深宇宙通信といった通信分野、及び地上波又は衛星ディジタル放送といった放送分野の研究が著しく進められているが、それに伴い、誤り訂正符号化及び復号の効率化を目的として符号理論に関する研究も盛んに行われている。

符号性能の理論的限界としては、いわゆるシャノン(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 toIEEE 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 ofACMSymposium on Theory of Computing, pp. 249-258, 1998」等において再注目されるに至ったものである。

LDPC符号は、近年の研究により、ターボ符号等と同様に、符号長を長くしていくにしたがって、シャノン限界に近い性能が得られることがわかりつつある。また、LDPC符号は、最小距離が符号長に比例するという性質があることから、その特徴として、ブロック誤り確率特性がよく、さらに、ターボ符号等の復号特性において観測される、いわゆるエラーフロア現象が殆ど生じないことも利点として挙げられる。

以下、このようなLDPC符号について具体的に説明する。なお、LDPC符号は、線形符号であり、必ずしも2元である必要はないが、ここでは、2元であるものとして説明する。

LDPC符号は、そのLDPC符号を定義する検査行列(parity check matrix)が疎なものであることを最大の特徴とするものである。ここで、疎な行列とは、行列のコンポーネントの"1"の個数が非常に少なく構成されるものであり、疎な検査行列をHで表すものとすると、そのような検査行列Hとしては、例えば、図1に示すように、各列のハミング重み("1"の数)(weight)が"3"であり、且つ、各行のハミング重みが"6"であるもの等がある。

このように、各行及び各列のハミング重みが一定である検査行列Hによって定義されるLDPC符号は、レギュラーLDPC符号と称される。一方、各行及び各列のハミング重みが一定でない検査行列Hによって定義されるLDPC符号は、イレギュラーLDPC符号と称される。

このようなLDPC符号による符号化は、検査行列Hに基づいて生成行列Gを生成し、この生成行列Gを2元の情報メッセージに対して乗算することによって符号語を生成することで実現される。具体的には、LDPC符号による符号化を行う符号化装置は、まず、検査行列Hの転置行列HTとの間に、式GHT=0が成立する生成行列Gを算出する。ここで、生成行列Gが、k×n行列(k行n列の行列)である場合には、検査行列Hは、n-k行n列の行列である。

符号化装置は、生成行列Gに対してkビットからなる情報メッセージ(ベクトル)uを乗算し、nビットからなる符号語(LDPC符号)c(=uG)を生成する。この符号化装置によって生成された符号語cは、値が"0"の符号ビットが"+1"に、値が"1"の符号ビットが"−1"にといったようにマッピングされて送信され、所定の通信路を介して受信側において受信されることになる。

なお、例えば、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が、図2に示すように、情報部と、下三角行列のパリティ部とで構成され、パリティ部の下三角の部分の要素が、すべて1であるとすると、符号語cのパリティビットの1番目のビットは、情報メッセージuのうちの、検査行列Hの情報部の第1行において1になっている要素に対応するビットのEXOR(排他的論理和)を演算した値となる。

また、符号語cのパリティビットの2番目のビットは、情報メッセージuのうちの、検査行列Hの情報部の第2行において1になっている要素に対応するビットと、パリティビットの1番目のビットのEXORを演算した値となる。

さらに、符号語cのパリティビットの3番目のビットは、情報メッセージuのうちの、検査行列Hの情報部の第3行において1になっている要素に対応するビットと、パリティビットの1番目および2番目のビットのEXORを演算した値となる。

以下、同様にして、符号語cのパリティビットのi番目のビットは、情報メッセージuのうちの、検査行列Hの情報部の第i行において1になっている要素に対応するビットと、パリティビットの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符号の復号アルゴリズムとして、アルゴリズムA又はアルゴリズムBを提案している。

LDPC符号の復号は、一般的には、図3に示すような手順にしたがって行われる。なお、ここでは、LDPC符号(符号化cの)受信値をU0とし、チェックノードから出力されるメッセージ(以下、適宜、チェックノードノードメッセージともいう)をujとし、バリアブルノードから出力されるメッセージ(以下、適宜、バリアブルノードメッセージともいう)をviとする。また、メッセージは、"0"らしさを、いわゆる対数尤度比(log likelihood ratio)で表現した実数値である。さらに、受信値U0の"0"らしさの対数尤度比を、受信データu0iと表すこととする。

まず、LDPC符号の復号においては、図3に示すように、ステップS11において、受信値U0(受信データu0i)が受信され、メッセージujが"0"に初期化されるとともに、繰り返し処理カウンタとしての整数をとる変数kが"0"に初期化され、ステップS12に進む。ステップS12において、受信データu0iに基づいて、式(1)に示す演算を行うことによってバリアブルノードメッセージviが求められ、さらに、このバリアブルノードメッセージviに基づいて、式(2)に示す演算を行うことによってチェックノードメッセージujが求められる。

・・・(1)

・・・(2)

ここで、式(1)と式(2)におけるdvとdcは、それぞれ、検査行列Hの縦方向行方向)と横方向(列方向)の"1"の個数を示す任意に選択可能とされるパラメータであり、例えば、(3,6)符号の場合には、dv=3,dc=6となる。

なお、式(1)または(2)の演算においては、それぞれ、メッセージを出力しようとする枝(edge)から入力されたメッセージを、和または積演算のパラメータとしては用いないことから、和または積演算の範囲が、1乃至dv-1または1乃至dc-1となっている。また、式(2)に示す演算は、実際には、2入力v1,v2に対する1出力で定義される式(3)に示す関数R(v1,v2)のテーブルを予め作成しておき、これを式(4)に示すように連続的(再帰的)に用いることによって行われる。

・・・(3)

・・・(4)

ステップS12では、さらに、変数kが"1"だけインクリメントされ、ステップS13に進む。ステップS13では、変数kが所定の繰り返し復号回数N以上であるか否かが判定される。ステップS13において、変数kがN以上ではないと判定された場合、ステップS12に戻り、以下、同様の処理が繰り返される。

また、ステップS13において、変数kがN以上であると判定された場合、ステップS14に進み、式(5)に示す演算を行うことによって最終的に出力する復号結果としてのメッセージvが求められて出力され、LDPC符号の復号処理が終了する。

・・・(5)

ここで、式(5)の演算は、式(1)の演算とは異なり、バリアブルノードに接続している全ての枝からのメッセージを用いて行われる。

このようなLDPC符号の復号は、例えば(3,6)符号の場合には、図4に示すように、各ノード間でメッセージの授受が行われる。なお、図4における"="で示すノード(バリアブルノード)では、式(1)に示した演算が行われ、"+"で示すノード(チェックノード)では、式(2)に示した演算が行われる。特に、アルゴリズムAにおいては、メッセージを2元化し、"+"で示すノードにて、そのノードに入力されるdc-1個のメッセージの排他的論理和演算を行い、"="で示すノードにて、受信データR(u0i)に対して、そのノードに入力されるdv-1個のメッセージが全て異なるビット値であった場合には、符号を反転して出力する。

また、一方で、近年、LDPC符号の復号の実装法に関する研究も行われている。実装方法について述べる前に、まず、LDPC符号の復号を摸式化して説明する。

図5は、(3,6)LDPC符号(符号化率1/2、符号長12)の検査行列(parity check matrix)の例である。LDPC符号の検査行列Hは、図6のように、タナーグラフを用いて書き表すことができる。ここで、図6において、"+"で表されるのが、チェックノードであり、"="で表されるのが、バリアブルノードである。チェックノードとバリアブルノードは、それぞれ、検査行列Hの行と列に対応する。チェックノードとバリアブルノードとの間の結線は、枝(edge)であり、検査行列の"1"に相当する。即ち、検査行列Hの第j行第i列のコンポーネントが1である場合には、図6において、上からi番目のバリアブルノード("="のノード)と、上からj番目のチェックノード("+"のノード)とが、枝により接続される。枝は、バリアブルノードに対応するLDPC符号のビットが、チェックノードに対応する拘束条件を持つことを表す。なお、図6は、図5の検査行列Hのタナーグラフとなっている。

LDPC符号の復号方法であるサムプロダクトアルゴリズム(Sum Product Algorithm)は、バリアブルノードの演算とチェックノードの演算とを繰り返し行う。

バリアブルノードでは、図7のように、式(1)の演算を行う。すなわち、図7において、計算しようとしている枝に対応するバリアブルノードメッセージviは、バリアブルノードに繋がっている残りの枝からのチェックノードメッセージu1およびu2と、受信情報u0iを用いて計算される。他の枝に対応するバリアブルノードメッセージも同様に計算される。

チェックノードの演算について説明する前に、式(2)を、式a×b=exp{ln(|a|)+ln(|b|)}×sign(a)×sign(b)の関係を用いて、式(6)のように書き直す。但し、sign(x)は、x≧0のとき1であり、x<0のとき-1である。

・・・(6)

更に、x≧0において、非線形な関数(非線形関数)φ(x)を、式φ(x)=ln(tanh(x/2))と定義すると(ln()は自然対数関数)、その非線形関数φ(x)の逆関数φ-1(x)は、式φ-1(x)=2tanh-1(e-x)で表されるから、式(6)は、式(7)のように書くことができる。

・・・(7)

チェックノードでは、図8のように、式(7)の演算を行う。すなわち、図8において、計算しようとしている枝に対応するチェックノードメッセージ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となる。

また、LDPC符号の復号方法は、サムプロダクトアルゴリズムの他、例えば、ビリーフプロパゲーション(Belief Propagation)などとも呼ばれるが、いずれにしても、行われる演算の内容は同様である。

復号装置へのサムプロダクトアルゴリズムの実装の例として、各ノードの演算を一つずつ順次行うことによって復号を行う場合(full serial decoding)の実装法について説明する。

なお、サムプロダクトアルゴリズムをハードウェアに実装する場合、式(1)で表されるバリアブルノード演算および式(7)で表されるチェックノード演算とを、適度な回路規模動作周波数で繰り返し行うことが必要である。

また、ここでは、例えば、図9の、36(行)×108(列)の検査行列Hで表現される符号(符号化率2/3、符号長108)を復号することとする。図9の検査行列Hの1の数は323であり、従って、そのタナーグラフでは、枝の数は323個となる。ここで、図9の検査行列では、0を、"."で表現している。

図10は、LDPC符号の1回復号を行う復号装置の構成例を示している。

図10の復号装置では、その動作する1クロック(clock)ごとに、1つの枝に対応するメッセージが計算される。

即ち、図10の復号装置は、2つの枝用メモリ100および102、1つのチェックノード計算器101、1つのバリアブルノード計算器103、1つの受信用メモリ104、1つの制御部105からなる。

図10の復号装置では、枝用メモリ100または102からメッセージが1つずつ読み出され、そのメッセージを用いて、所望の枝に対応するメッセージが計算される。そして、その計算によって求められたメッセージが1つずつ後段の枝用メモリ102または100に格納されていく。繰り返し復号を行う際には、この1回復号を行う図10の復号装置を複数個縦列に連接するか、もしくは図10の復号装置を繰り返し用いることによって、繰り返し復号を実現する。なお、ここでは、例えば、図10の復号装置が複数個接続されているものとする。

枝用メモリ100は、前段の復号装置(図示せず)のバリアブルノード計算器103から供給されるメッセージ(バリアブルノードメッセージ)D100を、後段のチェックノード計算器101が読み出す順番に格納していく。そして、枝用メモリ100は、チェックノード計算のフェーズでは、メッセージD100を、格納してある順番通りに、メッセージD101として、チェックノード計算器101に供給する。

チェックノード計算器101は、制御部105から供給される制御信号D106に基づき、枝用メモリ100から供給されるメッセージD101(バリアブルノードメッセージvi)を用いて、式(7)に従って演算(チェックノード演算)を行い、その演算によって求められたメッセージD102(チェックノードメッセージuj)を、後段の枝用メモリ102に供給する。

枝用メモリ102は、前段のチェックノード計算器101から供給されるメッセージD102を、後段のバリアブルノード計算器103が読み出す順番に格納していく。そして、枝用メモリ102は、バリアブルノード計算のフェーズでは、メッセージD102を、格納してある順番通りに、メッセージD103として、バリアブルノード計算器103に供給する。

さらに、バリアブルノード計算器103には、制御部105から制御信号D107が供給されるとともに、受信用メモリ104から受信データD104が供給される。バリアブルノード計算器103は、制御信号D107に基づき、枝用メモリ100から供給されるメッセージD103(チェックノードメッセージuj)と受信用メモリ100から供給される受信データD104(受信データu0i)を用い、式(1)に従って演算(バリアブルノード演算)を行い、その演算の結果得られるメッセージD105(バリアブルノードメッセージvi)を、図示せぬ後段の復号装置の枝用メモリ100に供給する。

受信用メモリ104には、LDPC符号の受信データu0iが格納される。制御部105は、バリアブルノード演算を制御する制御信号D106と、チェックノード演算を制御する制御信号D107を、それぞれチェックノード計算器101とバリアブルノード計算器103に供給する。制御部105は、枝用メモリ100に全ての枝のメッセージが格納されたとき、チェックノード計算器101に制御信号D106を供給し、枝用メモリ102に全ての枝のメッセーが格納されたとき、バリアブルノード計算器103に制御信号D107を供給する。

図11は、チェックノード演算を1つずつ行う図10のチェックノード計算器101の構成例を示している。

なお、図11では、各メッセージが符号ビット(正負を表すビット)を合わせて合計6ビット(bit)に量子化されているものとして、チェックノード計算器101を表している。即ち、メッセージは、所定の数値範囲を符号ビット付きの6ビットで表すことができる64値に均等に分割する各数値割り当てられた6ビットの量子化値で表される。

また、図11では、図9の検査行列Hで表されるLDPC符号のチェックノード演算が行われる。さらに、図11のチェックノード演算器101には、クロックckが供給され、このクロックckは、必要なブロックに供給されるようになっている。そして、各ブロックは、クロックckに同期して処理を行う。

図11のチェックノード計算器101は、制御部105から供給される、例えば、1ビットの制御信号D106に基づき、枝用メモリ100から1つずつ読み込まれるメッセージD101(バリアブルノードメッセージvi)を用いて、式(7)にしたがって演算を行う。

即ち、チェックノード計算器101では、検査行列Hの各列に対応するバリアブルノードからの6ビットのメッセージD101(バリアブルノードメッセージvi)が1つずつ読み込まれ、その下位5ビットである絶対値D122(|vi|)がLUT121に、その最上位ビットである符号ビットD121がEXOR回路129とFIFO(First In First Out)メモリ133にそれぞれ供給される。また、チェックノード計算器101には、制御部105から制御信号D106が供給され、その制御信号D106は、セレクタ124とセレクタ131に供給される。

LUT121は、絶対値D122(|vi|)に対して、式(7)における非線形関数φ(|vi|)の演算を行った5ビットの演算結果D123(φ(|vi|))を読み出し演算器122とFIFOメモリ127に供給する。

演算器122は、演算結果D123(φ(|vi|))とレジスタ123に格納されている9ビットの値D124とを加算することにより、演算結果D123を積算し、その結果得られる9ビットの積算値をレジスタ123に再格納する。なお、検査行列Hの1行に亘る全ての枝からのメッセージD101の絶対値D122(|vi|)に対する演算結果D123が積算された場合、レジスタ123はリセットされる。

ここで、演算器122およびレジスタ123では、LUT121から供給される5ビットの演算結果D123(φ(|vi|))が、最大で、FIFOメモリ127における最大の遅延回数分、即ち、検査行列Hの行の最大の重み分の回数だけ積算される。いま、図9の検査行列Hの行の最大の重みは9であり、従って、演算器122およびレジスタ123では、9ビットの演算結果D123(φ(|vi|))が、最大で、9回積算される(5ビットの値の9個分の積算が行われる)。このため、演算器122の出力以降においては、5ビットの値を9回積算した値を表すことができるように、量子化ビット数は、LUT121が出力する5ビットの演算結果D1123(φ(|vi|))よりも4ビット(9(回)を表すことができる最小のビット数)だけ多い9ビットになっている。

検査行列の1行に亘るメッセージD101(バリアブルノードメッセージvi)が1つずつ読み込まれ、レジスタ123に1行分の演算結果D123が積算された積算値が格納された場合、制御部105から供給される制御信号D106は、0から1に変化する。例えば、行の重み(row weight)が「9」である場合、制御信号D106は、1から8クロック目までは、「0」となり、9クロック目では「1」となる。

制御信号D106が「1」の場合、セレクタ124は、レジスタ123に格納されている値、即ち、検査行列Hの1行に亘る全ての枝からのメッセージD101(バリアブルノードメッセージvi)から求められたφ(|vi|)が積算された9ビットの値D124(i=1からi=dcまでのΣφ(|vi|))を選択し、値D125として、レジスタ125に出力して格納させる。レジスタ125は、格納している値D125を、9ビットの値D126として、セレクタ124と演算器126に供給する。制御信号D106が「0」の場合、セレクタ124は、レジスタ125から供給された値D126を選択し、レジスタ125に出力して再格納させる。即ち、検査行列Hの1行に亘る全ての枝からのメッセージD101(バリアブルノードメッセージvi)から求められたφ(|vi|)が積算されるまで、レジスタ125は、前回積算されたφ(|vi|)を、セレクタ124と演算器126に供給する。

一方、FIFOメモリ127は、レジスタ125から新たな値D126(i=1からi=dcまでのΣφ(|vi|))が出力されるまでの間、LUT121が出力した5ビットの演算結果D123(φ(|vi|))を遅延し、5ビットの値D127として演算器126に供給する。演算器126は、レジスタ125から供給された値D126から、FIFOメモリ127から供給された値D127を減算し、その減算結果を、5ビットの減算値D128としてLUT128に供給する。即ち、演算器126は、検査行列Hの1行に亘る全ての枝からのメッセージD101(バリアブルノードメッセージvi)から求められたφ(|vi|)の積算値から、チェックノードメッセージujを求めたい枝からのメッセージD101(バリアブルノードメッセージvi)から求められたφ(|vi|)を減算して、その減算値(i=1からi=dc−1までのΣφ(|vi|))を減算値D128としてLUT128に供給する。

なお、演算器126は、レジスタ125から供給される9ビットの値D126から、FIFOメモリ127から供給される5ビットの値D127を減算するから、その減算結果は、最大で9ビットとなり得るのに対して、5ビットの減算値D128を出力する。このため、レジスタ125から供給される9ビットの値D126から、FIFOメモリ127から供給される5ビットの値D127を減算した減算結果が、5ビットで表せない場合、つまり、減算結果が、5ビットで表すことができる最大値(31(2進数では11111))を越える場合には、演算器126は、減算結果を、5ビットで表すことができる最大値にクリッピングし、5ビットの減算値D128を出力する。

LUT128は、減算値D128(i=1からi=dc−1までのΣφ(|vi|))に対して、式(7)における逆関数φ-1(Σφ(|vi|))の演算を行った5ビットの演算結果D129(φ-1(Σφ(|vi|)))を出力する。

以上の処理と並行して、EXOR回路129は、レジスタ130に格納されている1ビットの値D131と符号ビットD121との排他的論理和を演算することにより、符号ビットどうしの乗算を行い、1ビットの乗算結果D130をレジスタ130に再格納する。なお、検査行列Hの1行に亘る全ての枝からのメッセージD101(バリアブルノードメッセージvi)の符号ビットD121が乗算された場合、レジスタ130はリセットされる。

検査行列Hの1行に亘る全ての枝からのメッセージD101の符号ビットD121が乗算された乗算結果D130(i=1からdcまでのΠsign(vi))がレジスタ130に格納された場合、制御部105から供給される制御信号D106は、「0」から「1」に変化する。

制御信号D106が「1」の場合、セレクタ131は、レジスタ130に格納されている値、即ち、検査行列Hの1行に亘る全ての枝からのメッセージD101の符号ビットD121が乗算された値D131(i=1からi=dcまでのΠsign(vi))を選択し、1ビットの値D132としてレジスタ132に出力して格納させる。レジスタ132は、格納している値D132を、1ビットの値D133としてセレクタ131とEXOR回路134に供給する。制御信号D106が「0」の場合、セレクタ131は、レジスタ132から供給された値D133を選択し、レジスタ132に出力して再格納させる。即ち、検査行列Hの1行に亘る全ての枝からのメッセージD101(バリアブルノードメッセージvi)の符号ビットD121が乗算されるまで、レジスタ132は、前回格納した値を、セレクタ131とEXOR回路134に供給する。

一方、FIFOメモリ133は、レジスタ132から新たな値D133(i=1からi=dcまでのΠsign(vi))がEXOR回路134に供給されるまでの間、符号ビットD121を遅延し、1ビットの値D134としてEXOR回路134に供給する。EXOR回路134は、レジスタ132から供給された値D133と、FIFOメモリ133から供給された値D134との排他的論理和を演算することにより、値D133を、値D134で除算し、1ビットの除算結果除算値D135として出力する。即ち、EXOR回路134は、検査行列Hの1行に亘る全ての枝からのメッセージD101の符号ビットD121(sign(|vi|))の乗算値を、チェックノードメッセージujを求めたい枝からのメッセージD101の符号ビットD121(sign(|vi|))で除算して、その除算値(i=1からi=dc−1までのΠsign(|vi|))を除算値D135として出力する。

チェックノード計算器101では、LUT128から出力された5ビットの演算結果D129を下位5ビットとするとともに、EXOR回路134から出力された1ビットの除算値D135を最上位ビット(符号ビット)とする合計6ビットがメッセージD102(チェックノードメッセージuj)として出力される。

以上のように、チェックノード計算器101では、式(7)の演算が行われ、チェックノードメッセージujが求められる。

なお、図9の検査行列Hの行の重みの最大は9であるため、即ち、チェックノードに供給されるバリアブルノードメッセージviの最大数は9であるため、チェックノード計算器101は、9個のチェックノードメッセージviの非線形関数の演算結果(φ(|vi|))を遅延させるFIFOメモリ127とFIFOメモリ133を有している。行の重みが9未満の行のチェックノードメッセージujを計算するときには、FIFOメモリ127とFIFOメモリ133における遅延量が、その行の重みの値に減らされる。

図12は、バリアブルノード演算を1つずつ行う図10のバリアブルノード計算器103の構成例を示している。

なお、図12でも、図11と同様に、各メッセージが符号ビットを合わせて合計6ビット(bit)に量子化されているものとして、バリアブルノード計算器103を表している。さらに、図12でも、図9の検査行列Hで表されるLDPC符号のバリアブルノード演算が行われる。また、図12のバリアブルノード計算器103には、クロックckが供給され、クロックckは、必要なブロックに供給されるようになっている。そして、各ブロックは、クロックckに同期して処理を行う。

図12のバリアブルノード計算器103は、制御部105から供給される、例えば、1ビットの制御信号D107に基づき、枝用メモリ102から1つずつ読み込まれるメッセージD103と、受信用メモリ104から読み込まれる受信データD104(u0i)を用いて、式(1)にしたがって演算(バリアブルノード演算)を行う。

即ち、バリアブルノード計算器103では、検査行列Hの各行に対応するチェックノードからの6ビットのメッセージD103(チェックノードメッセージuj)が1つずつ読み込まれ、そのメッセージD103が、演算器151とFIFOメモリ155に供給される。また、バリアブルノード計算器103では、受信用メモリ104から6ビットの受信データD104(u0i)が1つずつ読み込まれ、演算器156に供給される。さらに、バリアブルノード計算器103には、制御部105から制御信号D107が供給され、その制御信号D107は、セレクタ153に供給される。

演算器151は、6ビットのメッセージD103(チェックノードメッセージuj)とレジスタ152に格納されている9ビットの値D151とを加算することにより、6ビットのメッセージD103を積算し、その結果得られる9ビットの積算値を、レジスタ152に再格納する。なお、検査行列Hの1列に亘る全ての枝からのメッセージD103が積算された場合、レジスタ152はリセットされる。

ここで、演算器151およびレジスタ152では、6ビットのメッセージD103が、最大で、FIFOメモリ155における最大の遅延回数分、即ち、検査行列Hの列の最大の重み分の回数だけ積算される。いま、図9の検査行列Hの列の最大の重みは5であり、従って、演算器151およびレジスタ152では、6ビットのメッセージD103が、最大で、5回積算される(6ビットの値の5個分の積算が行われる)。このため、演算器151の出力以降においては、6ビットの値を5回積算した値を表すことができるように、量子化ビット数は、6ビットのメッセージD103よりも3ビット(5(回)を表すことができる最小のビット数)だけ多い9ビットになっている。

検査行列Hの1列に亘るメッセージD103が1つずつ読み込まれ、レジスタ152に1列分のメッセージD103が積算された値が格納された場合、制御部105から供給される制御信号D107は、「0」から「1」に変化する。例えば、列の重みが「5」である場合、制御信号D107は、1から4クロック目までは「0」となり、5クロック目では「1」となる。

制御信号D107が「1」の場合、セレクタ153は、レジスタ152に格納されている値、即ち、検査行列Hの1列に亘る全ての枝からのメッセージD103(チェックノードメッセージuj)が積算された9ビットの値D151(j=1からdVまでのΣuj)を選択し、レジスタ154に出力して格納させる。レジスタ154は、格納している値D151を、9ビットの値D152として、セレクタ153と演算器156に供給する。制御信号D107が「0」の場合、セレクタ153は、レジスタ154から供給された値D152を選択し、レジスタ154に出力し再格納させる。即ち、検査行列Hの1列に亘る全ての枝からのメッセージD103(チェックノードメッセージuj)が積算されるまで、レジスタ154は、前回積算された値を、セレクタ153と演算器156に供給する。

一方、FIFOメモリ155は、レジスタ154から新たな値D152(j=1からdVまでのΣuj)が出力されるまでの間、チェックノードからのメッセージD103を遅延し、6ビットの値D153として演算器156に供給する。演算器156は、レジスタ154から供給された値D152から、FIFOメモリ155から供給された値D153を減算する。即ち、演算器156は、検査行列Hの1列に亘る全ての枝からのメッセージD103(チェックノードメッセージuj)の積算値から、バリアブルノードメッセージviを求めたい枝からのチェックノードメッセージujを減算して、その減算値(j=1からdv−1までのΣuj)を求める。さらに、演算器156には、その減算値(j=1からdv−1までのΣuj)に、受信用メモリ104から供給された受信データD104(u0i)を加算して、その結果得られる6ビットの値をメッセージD105(バリアブルノードメッセージvi)として出力する。

以上のように、バリアブルノード計算器103では、式(1)の演算が行われ、バリアブルノードメッセージviが求められる。

なお、図9の検査行列Hの列の重みの最大は5であるため、即ち、バリアブルノードバリアブルノードに供給されるチェックノードメッセージujの最大数は5であるため、バリアブルノード計算器103は、5個のチェックノードメッセージujを遅延させるFIFOメモリ155を有している。列の重みが5未満の列のバリアブルノードメッセージviを計算するときには、FIFOメモリ155における遅延量が、その列の重みの値に減らされる。

また、演算器156は、レジスタ154から供給される9ビットの値D152から、FIFOメモリ155から供給される6ビットの値D153を減算するとともに、受信用メモリ104から供給される6ビットの受信データD104を加算する演算を行うから、その演算結果は、6ビットのメッセージD105で表すことができる最小値未満となるか、または最大値を越えることがある。演算器156は、演算結果が、6ビットのメッセージD105で表すことができる最小値未満である場合には、その最小値にクリッピングし、演算結果が、6ビットのメッセージD105で表すことができる最大値を越える場合には、その最大値にクリッピングする。

図10の復号装置では、検査行列Hの重みにしたがって、制御部105から制御信号が与えられる。図10の復号装置によれば、枝用メモリ100および102、並びにチェックノード計算器101およびバリアブルノード計算器103のFIFOメモリ127,133,155の容量さえ足りれば、制御信号のみを変えることで様々な検査行列HのLDPC符号を復号することができる。

なお、図示しないが、図10の復号装置において、復号の最終段においては、式(1)のバリアブルノード演算の代わりに、式(5)の演算が行われ、その演算結果が、最終的な復号結果として出力される。

図10の復号装置を繰り返し用いて、LDPC符号を復号する場合には、チェックノード演算とバリアブルノード演算とが交互に行われる。即ち、図10の復号装置では、チェックノード計算器101によるチェックノード演算の結果を用いて、バリアブルノード計算器103によりバリアブルノード演算が行われ、バリアブルノード計算器103によるバリアブルノード演算の結果を用いて、チェックノード計算器101によりチェックノード演算が行われる。

なお、図10は、復号装置の実装の例として、各ノードの演算を一つずつ順次行うことによって、LDPC符号の復号を行う(full serial decoding)復号装置であるが、その他、全ノードの演算を同時に行うことによって復号を行う(full parallel decoding)復号装置(非特許文献1)や、一つでも全てでもない、ある数のノードの演算を同時に行う(partly parallel decoding)復号装置(非特許文献2)も提案されている。

ところで、例えば、図10の復号装置では、受信データD104を記憶する受信用メモリ104の記憶容量としては、少なくとも、LDPC符号の符号長と、受信データD104を表す量子化値のビット数(量子化ビット数)との乗算値だけのビット数が必要である。また、メッセージを記憶する枝用メモリ100や102の記憶容量としては、少なくとも、枝の総数(全枝数)と、メッセージを表す量子化値のビット数(量子化ビット数)との乗算値だけのビット数が必要である。

従って、上述したように、符号長が108で、メッセージ(受信データD104を含む)を表す量子化値のビット数が6ビットで、枝の数が323である場合には、記憶容量が少なくとも648(=108×6)ビットの受信用メモリ104と、記憶容量が少なくとも1938(=323×6)ビットの枝用メモリ100および102とが必要となる。

なお、ここでは、説明を簡単にするために、符号長を108としたが、現実的には、LDPC符号の符号長としては、数千程度が採用される。

一方、LDPC符号の復号の精度を向上させるには、単純には、受信データD104を含むメッセージを表す量子化値として、ある程度のビット数の量子化値を採用する必要がある。

しかしながら、上述したように、枝用メモリ100および102、並びに受信用メモリ104の記憶容量は、メッセージを表す量子化値のビット数に比例するので、メッセージを、多くのビット数の量子化値で表すと、復号装置を構成するメモリとして、容量の大きなメモリが必要となり、装置の規模が大型化する。

C. Howland and A. Blanksby, "Parallel Decoding Architectures for Low Density Parity Check Codes", Symposium onCircuits and Systems, 2001
E. Yeo, P. Pakzad, B. Nikolic and V. Anantharam, "VLSIArchitectures for iterative Decoders in Magnetic Recording Channels",IEEE Transactions on Magnetics, Vol. 37, No. 2, March 2001

概要

LDPC符号の復号を、装置の大規模化を抑えつつ精度良く行う。チェックノード計算器171は、LDPC符号の復号のためのチェックノード演算であって、非線形関数φ(x)の演算および非線形関数の逆関数φ-1(x)の演算を含むチェックノード演算を行う。バリアブルノード計算器103は、LDPC符号の復号のためのバリアブルノードのバリアブルノード演算を行う。そして、チェックノード計算器171およびバリアブルノード計算器103は、チェックノード演算およびバリアブルノード演算として行う処理のうちの、非線形関数φ(x)の演算後から逆関数φ-1(x)の演算までの処理では、第1の量子化値よりも精度の高い数値を表す第2の量子化値を使用し、他の処理では、第1の量子化値を使用する。本発明は、例えば、衛星放送を受信するチューナに適用できる。

目的

効果

実績

技術文献被引用数
1件
牽制数
1件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

LDPC(Low Density Parity Check)符号の復号装置であって、前記LDPC符号復号のためのチェックノードチェックノード演算であって、非線形関数演算および前記非線形関数の逆関数の演算を含む前記チェックノード演算を行う第1の演算手段と、前記LDPC符号の復号のためのバリアブルノードバリアブルノード演算を行う第2の演算手段とを備え、前記第1の演算手段は、数値割り当てられた第1の量子化値を、前記第1の量子化値よりも精度の高い数値を表す第2の量子化値に変換する第1の変換手段と、前記第2の量子化値を、前記第1の量子化値に変換する第2の変換手段とを有し、前記第1および第2の演算手段は、前記チェックノード演算およびバリアブルノード演算として行う処理のうちの、前記非線形関数の演算後から前記逆関数の演算までの処理では、前記第2の量子化値を使用し、他の処理では、前記第1の量子化値を使用することを特徴とする復号装置。

請求項2

請求項1に記載の復号装置であって、前記第1の演算手段は、前記チェックノード演算と、前記バリアブルノード演算の一部とを行い、前記第2の演算手段は、前記バリアブルノード演算の他の一部を行うことを特徴とする復号装置。

請求項3

請求項1に記載の復号装置であって、前記第2の量子化値は、前記第1の量子化値が表す数値のダイナミックレンジより狭いダイナミックレンジの数値を表すことを特徴とする復号装置。

請求項4

請求項1に記載の復号装置であって、前記第2の量子化値は、前記第1の量子化値よりも量子化幅が小さい量子化値であることを特徴とする復号装置。

請求項5

請求項1に記載の復号装置であって、前記第2の量子化値は、前記第1の量子化値よりもビット数が多い量子化値であることを特徴とする復号装置。

請求項6

請求項1に記載の復号装置であって、前記第1の変換手段は、前記第1の量子化値を入力として、前記非線形関数を演算した結果を、前記第2の量子化値によって出力するLUT(Look Up Table)であり、前記第2の変換手段は、前記第2の量子化値を入力として、前記逆関数を演算した結果を、前記第1の量子化値によって出力するLUTであることを特徴とする復号装置。

請求項7

LDPC(Low Density Parity Check)符号の復号のためのチェックノードのチェックノード演算であって、非線形関数の演算および前記非線形関数の逆関数の演算を含む前記チェックノード演算を行う第1の演算手段と、前記LDPC符号の復号のためのバリアブルノードのバリアブルノード演算を行う第2の演算手段とを備える前記LDPC符号の復号装置の復号方法であって、数値に割り当てられた第1の量子化値を、前記第1の量子化値よりも精度の高い数値を表す第2の量子化値に変換する第1の変換ステップと、前記第2の量子化値を、前記第1の量子化値に変換する第2の変換ステップとを含み、前記第1および第2の演算手段において、前記チェックノード演算およびバリアブルノード演算として行う処理のうちの、前記非線形関数の演算後から前記逆関数の演算までの処理では、前記第2の量子化値を使用し、他の処理では、前記第1の量子化値を使用することを特徴とする復号方法。

技術分野

0001

本発明は、復号装置および復号方法に関し、特に、低密度パリティ検査符号LDPC符号)による符号化が施された符号の復号を、装置の大規模化を抑えつつ精度良く行うことができるようにする復号装置および復号方法に関する。

背景技術

0002

近年、例えば、移動体通信深宇宙通信といった通信分野、及び地上波又は衛星ディジタル放送といった放送分野の研究が著しく進められているが、それに伴い、誤り訂正符号化及び復号の効率化を目的として符号理論に関する研究も盛んに行われている。

0003

符号性能の理論的限界としては、いわゆるシャノン(C. E. Shannon)の通信路符号化定理によって与えられるシャノン限界が知られている。符号理論に関する研究は、このシャノン限界に近い性能を示す符号を開発することを目的として行われている。近年では、シャノン限界に近い性能を示す符号化方法として、例えば、並列連接畳み込み符号(PCCC(Parallel Concatenated Convolutional Codes))や、縦列連接畳み込み符号(SCCC(Serially Concatenated Convolutional Codes))といった、いわゆるターボ符号化(Turbo coding)と呼ばれる手法が開発されている。また、これらのターボ符号が開発される一方で、古くから知られる符号化方法である低密度パリティ検査符号(Low Density Parity Check codes)(以下、LDPC符号という)が脚光を浴びつつある。

0004

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 toIEEE 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 ofACMSymposium on Theory of Computing, pp. 249-258, 1998」等において再注目されるに至ったものである。

0005

LDPC符号は、近年の研究により、ターボ符号等と同様に、符号長を長くしていくにしたがって、シャノン限界に近い性能が得られることがわかりつつある。また、LDPC符号は、最小距離が符号長に比例するという性質があることから、その特徴として、ブロック誤り確率特性がよく、さらに、ターボ符号等の復号特性において観測される、いわゆるエラーフロア現象が殆ど生じないことも利点として挙げられる。

0006

以下、このようなLDPC符号について具体的に説明する。なお、LDPC符号は、線形符号であり、必ずしも2元である必要はないが、ここでは、2元であるものとして説明する。

0007

LDPC符号は、そのLDPC符号を定義する検査行列(parity check matrix)が疎なものであることを最大の特徴とするものである。ここで、疎な行列とは、行列のコンポーネントの"1"の個数が非常に少なく構成されるものであり、疎な検査行列をHで表すものとすると、そのような検査行列Hとしては、例えば、図1に示すように、各列のハミング重み("1"の数)(weight)が"3"であり、且つ、各行のハミング重みが"6"であるもの等がある。

0008

このように、各行及び各列のハミング重みが一定である検査行列Hによって定義されるLDPC符号は、レギュラーLDPC符号と称される。一方、各行及び各列のハミング重みが一定でない検査行列Hによって定義されるLDPC符号は、イレギュラーLDPC符号と称される。

0009

このようなLDPC符号による符号化は、検査行列Hに基づいて生成行列Gを生成し、この生成行列Gを2元の情報メッセージに対して乗算することによって符号語を生成することで実現される。具体的には、LDPC符号による符号化を行う符号化装置は、まず、検査行列Hの転置行列HTとの間に、式GHT=0が成立する生成行列Gを算出する。ここで、生成行列Gが、k×n行列(k行n列の行列)である場合には、検査行列Hは、n-k行n列の行列である。

0010

符号化装置は、生成行列Gに対してkビットからなる情報メッセージ(ベクトル)uを乗算し、nビットからなる符号語(LDPC符号)c(=uG)を生成する。この符号化装置によって生成された符号語cは、値が"0"の符号ビットが"+1"に、値が"1"の符号ビットが"−1"にといったようにマッピングされて送信され、所定の通信路を介して受信側において受信されることになる。

0011

なお、例えば、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を用いて行うことができる。

0012

即ち、例えば、検査行列Hが、図2に示すように、情報部と、下三角行列のパリティ部とで構成され、パリティ部の下三角の部分の要素が、すべて1であるとすると、符号語cのパリティビットの1番目のビットは、情報メッセージuのうちの、検査行列Hの情報部の第1行において1になっている要素に対応するビットのEXOR(排他的論理和)を演算した値となる。

0013

また、符号語cのパリティビットの2番目のビットは、情報メッセージuのうちの、検査行列Hの情報部の第2行において1になっている要素に対応するビットと、パリティビットの1番目のビットのEXORを演算した値となる。

0014

さらに、符号語cのパリティビットの3番目のビットは、情報メッセージuのうちの、検査行列Hの情報部の第3行において1になっている要素に対応するビットと、パリティビットの1番目および2番目のビットのEXORを演算した値となる。

0015

以下、同様にして、符号語cのパリティビットのi番目のビットは、情報メッセージuのうちの、検査行列Hの情報部の第i行において1になっている要素に対応するビットと、パリティビットの1乃至i-1番目のビットのEXORを演算した値となる。

0016

以上のようにして、n-kビットのパリティビットを求め、kビットの情報メッセージuに続けて配置することにより、nビットの符号語cを得ることができる。

0017

一方、LDPC符号の復号は、Gallagerが確率復号(Probabilistic Decoding)と称して提案したアルゴリズムであって、バリアブルノード(variable node(メッセージノード(message node)とも呼ばれる。))と、チェックノード(check node)とからなる、いわゆるタナーグラフ(Tanner graph)上での確率伝播(belief propagation)によるメッセージパッシング・アルゴリズムによって行うことが可能である。ここで、以下、適宜、バリアブルノードとチェックノードを、単に、ノードともいう。

0018

しかしながら、確率復号においては、各ノード間で受け渡されるメッセージが実数値であることから、解析的に解くためには、連続した値をとるメッセージの確率分布そのものを追跡する必要があり、非常に困難を伴う解析を必要とすることになる。そこで、Gallagerは、LDPC符号の復号アルゴリズムとして、アルゴリズムA又はアルゴリズムBを提案している。

0019

LDPC符号の復号は、一般的には、図3に示すような手順にしたがって行われる。なお、ここでは、LDPC符号(符号化cの)受信値をU0とし、チェックノードから出力されるメッセージ(以下、適宜、チェックノードノードメッセージともいう)をujとし、バリアブルノードから出力されるメッセージ(以下、適宜、バリアブルノードメッセージともいう)をviとする。また、メッセージは、"0"らしさを、いわゆる対数尤度比(log likelihood ratio)で表現した実数値である。さらに、受信値U0の"0"らしさの対数尤度比を、受信データu0iと表すこととする。

0020

まず、LDPC符号の復号においては、図3に示すように、ステップS11において、受信値U0(受信データu0i)が受信され、メッセージujが"0"に初期化されるとともに、繰り返し処理カウンタとしての整数をとる変数kが"0"に初期化され、ステップS12に進む。ステップS12において、受信データu0iに基づいて、式(1)に示す演算を行うことによってバリアブルノードメッセージviが求められ、さらに、このバリアブルノードメッセージviに基づいて、式(2)に示す演算を行うことによってチェックノードメッセージujが求められる。

0021

・・・(1)

0022

・・・(2)

0023

ここで、式(1)と式(2)におけるdvとdcは、それぞれ、検査行列Hの縦方向行方向)と横方向(列方向)の"1"の個数を示す任意に選択可能とされるパラメータであり、例えば、(3,6)符号の場合には、dv=3,dc=6となる。

0024

なお、式(1)または(2)の演算においては、それぞれ、メッセージを出力しようとする枝(edge)から入力されたメッセージを、和または積演算のパラメータとしては用いないことから、和または積演算の範囲が、1乃至dv-1または1乃至dc-1となっている。また、式(2)に示す演算は、実際には、2入力v1,v2に対する1出力で定義される式(3)に示す関数R(v1,v2)のテーブルを予め作成しておき、これを式(4)に示すように連続的(再帰的)に用いることによって行われる。

0025

・・・(3)

0026

・・・(4)

0027

ステップS12では、さらに、変数kが"1"だけインクリメントされ、ステップS13に進む。ステップS13では、変数kが所定の繰り返し復号回数N以上であるか否かが判定される。ステップS13において、変数kがN以上ではないと判定された場合、ステップS12に戻り、以下、同様の処理が繰り返される。

0028

また、ステップS13において、変数kがN以上であると判定された場合、ステップS14に進み、式(5)に示す演算を行うことによって最終的に出力する復号結果としてのメッセージvが求められて出力され、LDPC符号の復号処理が終了する。

0029

・・・(5)

0030

ここで、式(5)の演算は、式(1)の演算とは異なり、バリアブルノードに接続している全ての枝からのメッセージを用いて行われる。

0031

このようなLDPC符号の復号は、例えば(3,6)符号の場合には、図4に示すように、各ノード間でメッセージの授受が行われる。なお、図4における"="で示すノード(バリアブルノード)では、式(1)に示した演算が行われ、"+"で示すノード(チェックノード)では、式(2)に示した演算が行われる。特に、アルゴリズムAにおいては、メッセージを2元化し、"+"で示すノードにて、そのノードに入力されるdc-1個のメッセージの排他的論理和演算を行い、"="で示すノードにて、受信データR(u0i)に対して、そのノードに入力されるdv-1個のメッセージが全て異なるビット値であった場合には、符号を反転して出力する。

0032

また、一方で、近年、LDPC符号の復号の実装法に関する研究も行われている。実装方法について述べる前に、まず、LDPC符号の復号を摸式化して説明する。

0033

図5は、(3,6)LDPC符号(符号化率1/2、符号長12)の検査行列(parity check matrix)の例である。LDPC符号の検査行列Hは、図6のように、タナーグラフを用いて書き表すことができる。ここで、図6において、"+"で表されるのが、チェックノードであり、"="で表されるのが、バリアブルノードである。チェックノードとバリアブルノードは、それぞれ、検査行列Hの行と列に対応する。チェックノードとバリアブルノードとの間の結線は、枝(edge)であり、検査行列の"1"に相当する。即ち、検査行列Hの第j行第i列のコンポーネントが1である場合には、図6において、上からi番目のバリアブルノード("="のノード)と、上からj番目のチェックノード("+"のノード)とが、枝により接続される。枝は、バリアブルノードに対応するLDPC符号のビットが、チェックノードに対応する拘束条件を持つことを表す。なお、図6は、図5の検査行列Hのタナーグラフとなっている。

0034

LDPC符号の復号方法であるサムプロダクトアルゴリズム(Sum Product Algorithm)は、バリアブルノードの演算とチェックノードの演算とを繰り返し行う。

0035

バリアブルノードでは、図7のように、式(1)の演算を行う。すなわち、図7において、計算しようとしている枝に対応するバリアブルノードメッセージviは、バリアブルノードに繋がっている残りの枝からのチェックノードメッセージu1およびu2と、受信情報u0iを用いて計算される。他の枝に対応するバリアブルノードメッセージも同様に計算される。

0036

チェックノードの演算について説明する前に、式(2)を、式a×b=exp{ln(|a|)+ln(|b|)}×sign(a)×sign(b)の関係を用いて、式(6)のように書き直す。但し、sign(x)は、x≧0のとき1であり、x<0のとき-1である。

0037

・・・(6)

0038

更に、x≧0において、非線形な関数(非線形関数)φ(x)を、式φ(x)=ln(tanh(x/2))と定義すると(ln()は自然対数関数)、その非線形関数φ(x)の逆関数φ-1(x)は、式φ-1(x)=2tanh-1(e-x)で表されるから、式(6)は、式(7)のように書くことができる。

0039

・・・(7)

0040

チェックノードでは、図8のように、式(7)の演算を行う。すなわち、図8において、計算しようとしている枝に対応するチェックノードメッセージujは、チェックノードに繋がっている残りの枝からのバリアブルメッセージv1,v2,v3,v4,v5を用いて計算される。他の枝に対応するチェックノードメッセージも同様に計算される。

0041

なお、関数φ(x)は、φ(x)=ln((ex+1)/(ex-1))とも表すことができ、x>0において、φ(x)=φ-1(x)である。関数φ(x)およびφ-1(x)をハードウェアに実装する際には、LUT(Look Up Table)を用いて実装される場合があるが、両者共に同一のLUTとなる。

0042

また、LDPC符号の復号方法は、サムプロダクトアルゴリズムの他、例えば、ビリーフプロパゲーション(Belief Propagation)などとも呼ばれるが、いずれにしても、行われる演算の内容は同様である。

0043

復号装置へのサムプロダクトアルゴリズムの実装の例として、各ノードの演算を一つずつ順次行うことによって復号を行う場合(full serial decoding)の実装法について説明する。

0044

なお、サムプロダクトアルゴリズムをハードウェアに実装する場合、式(1)で表されるバリアブルノード演算および式(7)で表されるチェックノード演算とを、適度な回路規模動作周波数で繰り返し行うことが必要である。

0045

また、ここでは、例えば、図9の、36(行)×108(列)の検査行列Hで表現される符号(符号化率2/3、符号長108)を復号することとする。図9の検査行列Hの1の数は323であり、従って、そのタナーグラフでは、枝の数は323個となる。ここで、図9の検査行列では、0を、"."で表現している。

0046

図10は、LDPC符号の1回復号を行う復号装置の構成例を示している。

0047

図10の復号装置では、その動作する1クロック(clock)ごとに、1つの枝に対応するメッセージが計算される。

0048

即ち、図10の復号装置は、2つの枝用メモリ100および102、1つのチェックノード計算器101、1つのバリアブルノード計算器103、1つの受信用メモリ104、1つの制御部105からなる。

0049

図10の復号装置では、枝用メモリ100または102からメッセージが1つずつ読み出され、そのメッセージを用いて、所望の枝に対応するメッセージが計算される。そして、その計算によって求められたメッセージが1つずつ後段の枝用メモリ102または100に格納されていく。繰り返し復号を行う際には、この1回復号を行う図10の復号装置を複数個縦列に連接するか、もしくは図10の復号装置を繰り返し用いることによって、繰り返し復号を実現する。なお、ここでは、例えば、図10の復号装置が複数個接続されているものとする。

0050

枝用メモリ100は、前段の復号装置(図示せず)のバリアブルノード計算器103から供給されるメッセージ(バリアブルノードメッセージ)D100を、後段のチェックノード計算器101が読み出す順番に格納していく。そして、枝用メモリ100は、チェックノード計算のフェーズでは、メッセージD100を、格納してある順番通りに、メッセージD101として、チェックノード計算器101に供給する。

0051

チェックノード計算器101は、制御部105から供給される制御信号D106に基づき、枝用メモリ100から供給されるメッセージD101(バリアブルノードメッセージvi)を用いて、式(7)に従って演算(チェックノード演算)を行い、その演算によって求められたメッセージD102(チェックノードメッセージuj)を、後段の枝用メモリ102に供給する。

0052

枝用メモリ102は、前段のチェックノード計算器101から供給されるメッセージD102を、後段のバリアブルノード計算器103が読み出す順番に格納していく。そして、枝用メモリ102は、バリアブルノード計算のフェーズでは、メッセージD102を、格納してある順番通りに、メッセージD103として、バリアブルノード計算器103に供給する。

0053

さらに、バリアブルノード計算器103には、制御部105から制御信号D107が供給されるとともに、受信用メモリ104から受信データD104が供給される。バリアブルノード計算器103は、制御信号D107に基づき、枝用メモリ100から供給されるメッセージD103(チェックノードメッセージuj)と受信用メモリ100から供給される受信データD104(受信データu0i)を用い、式(1)に従って演算(バリアブルノード演算)を行い、その演算の結果得られるメッセージD105(バリアブルノードメッセージvi)を、図示せぬ後段の復号装置の枝用メモリ100に供給する。

0054

受信用メモリ104には、LDPC符号の受信データu0iが格納される。制御部105は、バリアブルノード演算を制御する制御信号D106と、チェックノード演算を制御する制御信号D107を、それぞれチェックノード計算器101とバリアブルノード計算器103に供給する。制御部105は、枝用メモリ100に全ての枝のメッセージが格納されたとき、チェックノード計算器101に制御信号D106を供給し、枝用メモリ102に全ての枝のメッセーが格納されたとき、バリアブルノード計算器103に制御信号D107を供給する。

0055

図11は、チェックノード演算を1つずつ行う図10のチェックノード計算器101の構成例を示している。

0056

なお、図11では、各メッセージが符号ビット(正負を表すビット)を合わせて合計6ビット(bit)に量子化されているものとして、チェックノード計算器101を表している。即ち、メッセージは、所定の数値範囲を符号ビット付きの6ビットで表すことができる64値に均等に分割する各数値割り当てられた6ビットの量子化値で表される。

0057

また、図11では、図9の検査行列Hで表されるLDPC符号のチェックノード演算が行われる。さらに、図11のチェックノード演算器101には、クロックckが供給され、このクロックckは、必要なブロックに供給されるようになっている。そして、各ブロックは、クロックckに同期して処理を行う。

0058

図11のチェックノード計算器101は、制御部105から供給される、例えば、1ビットの制御信号D106に基づき、枝用メモリ100から1つずつ読み込まれるメッセージD101(バリアブルノードメッセージvi)を用いて、式(7)にしたがって演算を行う。

0059

即ち、チェックノード計算器101では、検査行列Hの各列に対応するバリアブルノードからの6ビットのメッセージD101(バリアブルノードメッセージvi)が1つずつ読み込まれ、その下位5ビットである絶対値D122(|vi|)がLUT121に、その最上位ビットである符号ビットD121がEXOR回路129とFIFO(First In First Out)メモリ133にそれぞれ供給される。また、チェックノード計算器101には、制御部105から制御信号D106が供給され、その制御信号D106は、セレクタ124とセレクタ131に供給される。

0060

LUT121は、絶対値D122(|vi|)に対して、式(7)における非線形関数φ(|vi|)の演算を行った5ビットの演算結果D123(φ(|vi|))を読み出し演算器122とFIFOメモリ127に供給する。

0061

演算器122は、演算結果D123(φ(|vi|))とレジスタ123に格納されている9ビットの値D124とを加算することにより、演算結果D123を積算し、その結果得られる9ビットの積算値をレジスタ123に再格納する。なお、検査行列Hの1行に亘る全ての枝からのメッセージD101の絶対値D122(|vi|)に対する演算結果D123が積算された場合、レジスタ123はリセットされる。

0062

ここで、演算器122およびレジスタ123では、LUT121から供給される5ビットの演算結果D123(φ(|vi|))が、最大で、FIFOメモリ127における最大の遅延回数分、即ち、検査行列Hの行の最大の重み分の回数だけ積算される。いま、図9の検査行列Hの行の最大の重みは9であり、従って、演算器122およびレジスタ123では、9ビットの演算結果D123(φ(|vi|))が、最大で、9回積算される(5ビットの値の9個分の積算が行われる)。このため、演算器122の出力以降においては、5ビットの値を9回積算した値を表すことができるように、量子化ビット数は、LUT121が出力する5ビットの演算結果D1123(φ(|vi|))よりも4ビット(9(回)を表すことができる最小のビット数)だけ多い9ビットになっている。

0063

検査行列の1行に亘るメッセージD101(バリアブルノードメッセージvi)が1つずつ読み込まれ、レジスタ123に1行分の演算結果D123が積算された積算値が格納された場合、制御部105から供給される制御信号D106は、0から1に変化する。例えば、行の重み(row weight)が「9」である場合、制御信号D106は、1から8クロック目までは、「0」となり、9クロック目では「1」となる。

0064

制御信号D106が「1」の場合、セレクタ124は、レジスタ123に格納されている値、即ち、検査行列Hの1行に亘る全ての枝からのメッセージD101(バリアブルノードメッセージvi)から求められたφ(|vi|)が積算された9ビットの値D124(i=1からi=dcまでのΣφ(|vi|))を選択し、値D125として、レジスタ125に出力して格納させる。レジスタ125は、格納している値D125を、9ビットの値D126として、セレクタ124と演算器126に供給する。制御信号D106が「0」の場合、セレクタ124は、レジスタ125から供給された値D126を選択し、レジスタ125に出力して再格納させる。即ち、検査行列Hの1行に亘る全ての枝からのメッセージD101(バリアブルノードメッセージvi)から求められたφ(|vi|)が積算されるまで、レジスタ125は、前回積算されたφ(|vi|)を、セレクタ124と演算器126に供給する。

0065

一方、FIFOメモリ127は、レジスタ125から新たな値D126(i=1からi=dcまでのΣφ(|vi|))が出力されるまでの間、LUT121が出力した5ビットの演算結果D123(φ(|vi|))を遅延し、5ビットの値D127として演算器126に供給する。演算器126は、レジスタ125から供給された値D126から、FIFOメモリ127から供給された値D127を減算し、その減算結果を、5ビットの減算値D128としてLUT128に供給する。即ち、演算器126は、検査行列Hの1行に亘る全ての枝からのメッセージD101(バリアブルノードメッセージvi)から求められたφ(|vi|)の積算値から、チェックノードメッセージujを求めたい枝からのメッセージD101(バリアブルノードメッセージvi)から求められたφ(|vi|)を減算して、その減算値(i=1からi=dc−1までのΣφ(|vi|))を減算値D128としてLUT128に供給する。

0066

なお、演算器126は、レジスタ125から供給される9ビットの値D126から、FIFOメモリ127から供給される5ビットの値D127を減算するから、その減算結果は、最大で9ビットとなり得るのに対して、5ビットの減算値D128を出力する。このため、レジスタ125から供給される9ビットの値D126から、FIFOメモリ127から供給される5ビットの値D127を減算した減算結果が、5ビットで表せない場合、つまり、減算結果が、5ビットで表すことができる最大値(31(2進数では11111))を越える場合には、演算器126は、減算結果を、5ビットで表すことができる最大値にクリッピングし、5ビットの減算値D128を出力する。

0067

LUT128は、減算値D128(i=1からi=dc−1までのΣφ(|vi|))に対して、式(7)における逆関数φ-1(Σφ(|vi|))の演算を行った5ビットの演算結果D129(φ-1(Σφ(|vi|)))を出力する。

0068

以上の処理と並行して、EXOR回路129は、レジスタ130に格納されている1ビットの値D131と符号ビットD121との排他的論理和を演算することにより、符号ビットどうしの乗算を行い、1ビットの乗算結果D130をレジスタ130に再格納する。なお、検査行列Hの1行に亘る全ての枝からのメッセージD101(バリアブルノードメッセージvi)の符号ビットD121が乗算された場合、レジスタ130はリセットされる。

0069

検査行列Hの1行に亘る全ての枝からのメッセージD101の符号ビットD121が乗算された乗算結果D130(i=1からdcまでのΠsign(vi))がレジスタ130に格納された場合、制御部105から供給される制御信号D106は、「0」から「1」に変化する。

0070

制御信号D106が「1」の場合、セレクタ131は、レジスタ130に格納されている値、即ち、検査行列Hの1行に亘る全ての枝からのメッセージD101の符号ビットD121が乗算された値D131(i=1からi=dcまでのΠsign(vi))を選択し、1ビットの値D132としてレジスタ132に出力して格納させる。レジスタ132は、格納している値D132を、1ビットの値D133としてセレクタ131とEXOR回路134に供給する。制御信号D106が「0」の場合、セレクタ131は、レジスタ132から供給された値D133を選択し、レジスタ132に出力して再格納させる。即ち、検査行列Hの1行に亘る全ての枝からのメッセージD101(バリアブルノードメッセージvi)の符号ビットD121が乗算されるまで、レジスタ132は、前回格納した値を、セレクタ131とEXOR回路134に供給する。

0071

一方、FIFOメモリ133は、レジスタ132から新たな値D133(i=1からi=dcまでのΠsign(vi))がEXOR回路134に供給されるまでの間、符号ビットD121を遅延し、1ビットの値D134としてEXOR回路134に供給する。EXOR回路134は、レジスタ132から供給された値D133と、FIFOメモリ133から供給された値D134との排他的論理和を演算することにより、値D133を、値D134で除算し、1ビットの除算結果除算値D135として出力する。即ち、EXOR回路134は、検査行列Hの1行に亘る全ての枝からのメッセージD101の符号ビットD121(sign(|vi|))の乗算値を、チェックノードメッセージujを求めたい枝からのメッセージD101の符号ビットD121(sign(|vi|))で除算して、その除算値(i=1からi=dc−1までのΠsign(|vi|))を除算値D135として出力する。

0072

チェックノード計算器101では、LUT128から出力された5ビットの演算結果D129を下位5ビットとするとともに、EXOR回路134から出力された1ビットの除算値D135を最上位ビット(符号ビット)とする合計6ビットがメッセージD102(チェックノードメッセージuj)として出力される。

0073

以上のように、チェックノード計算器101では、式(7)の演算が行われ、チェックノードメッセージujが求められる。

0074

なお、図9の検査行列Hの行の重みの最大は9であるため、即ち、チェックノードに供給されるバリアブルノードメッセージviの最大数は9であるため、チェックノード計算器101は、9個のチェックノードメッセージviの非線形関数の演算結果(φ(|vi|))を遅延させるFIFOメモリ127とFIFOメモリ133を有している。行の重みが9未満の行のチェックノードメッセージujを計算するときには、FIFOメモリ127とFIFOメモリ133における遅延量が、その行の重みの値に減らされる。

0075

図12は、バリアブルノード演算を1つずつ行う図10のバリアブルノード計算器103の構成例を示している。

0076

なお、図12でも、図11と同様に、各メッセージが符号ビットを合わせて合計6ビット(bit)に量子化されているものとして、バリアブルノード計算器103を表している。さらに、図12でも、図9の検査行列Hで表されるLDPC符号のバリアブルノード演算が行われる。また、図12のバリアブルノード計算器103には、クロックckが供給され、クロックckは、必要なブロックに供給されるようになっている。そして、各ブロックは、クロックckに同期して処理を行う。

0077

図12のバリアブルノード計算器103は、制御部105から供給される、例えば、1ビットの制御信号D107に基づき、枝用メモリ102から1つずつ読み込まれるメッセージD103と、受信用メモリ104から読み込まれる受信データD104(u0i)を用いて、式(1)にしたがって演算(バリアブルノード演算)を行う。

0078

即ち、バリアブルノード計算器103では、検査行列Hの各行に対応するチェックノードからの6ビットのメッセージD103(チェックノードメッセージuj)が1つずつ読み込まれ、そのメッセージD103が、演算器151とFIFOメモリ155に供給される。また、バリアブルノード計算器103では、受信用メモリ104から6ビットの受信データD104(u0i)が1つずつ読み込まれ、演算器156に供給される。さらに、バリアブルノード計算器103には、制御部105から制御信号D107が供給され、その制御信号D107は、セレクタ153に供給される。

0079

演算器151は、6ビットのメッセージD103(チェックノードメッセージuj)とレジスタ152に格納されている9ビットの値D151とを加算することにより、6ビットのメッセージD103を積算し、その結果得られる9ビットの積算値を、レジスタ152に再格納する。なお、検査行列Hの1列に亘る全ての枝からのメッセージD103が積算された場合、レジスタ152はリセットされる。

0080

ここで、演算器151およびレジスタ152では、6ビットのメッセージD103が、最大で、FIFOメモリ155における最大の遅延回数分、即ち、検査行列Hの列の最大の重み分の回数だけ積算される。いま、図9の検査行列Hの列の最大の重みは5であり、従って、演算器151およびレジスタ152では、6ビットのメッセージD103が、最大で、5回積算される(6ビットの値の5個分の積算が行われる)。このため、演算器151の出力以降においては、6ビットの値を5回積算した値を表すことができるように、量子化ビット数は、6ビットのメッセージD103よりも3ビット(5(回)を表すことができる最小のビット数)だけ多い9ビットになっている。

0081

検査行列Hの1列に亘るメッセージD103が1つずつ読み込まれ、レジスタ152に1列分のメッセージD103が積算された値が格納された場合、制御部105から供給される制御信号D107は、「0」から「1」に変化する。例えば、列の重みが「5」である場合、制御信号D107は、1から4クロック目までは「0」となり、5クロック目では「1」となる。

0082

制御信号D107が「1」の場合、セレクタ153は、レジスタ152に格納されている値、即ち、検査行列Hの1列に亘る全ての枝からのメッセージD103(チェックノードメッセージuj)が積算された9ビットの値D151(j=1からdVまでのΣuj)を選択し、レジスタ154に出力して格納させる。レジスタ154は、格納している値D151を、9ビットの値D152として、セレクタ153と演算器156に供給する。制御信号D107が「0」の場合、セレクタ153は、レジスタ154から供給された値D152を選択し、レジスタ154に出力し再格納させる。即ち、検査行列Hの1列に亘る全ての枝からのメッセージD103(チェックノードメッセージuj)が積算されるまで、レジスタ154は、前回積算された値を、セレクタ153と演算器156に供給する。

0083

一方、FIFOメモリ155は、レジスタ154から新たな値D152(j=1からdVまでのΣuj)が出力されるまでの間、チェックノードからのメッセージD103を遅延し、6ビットの値D153として演算器156に供給する。演算器156は、レジスタ154から供給された値D152から、FIFOメモリ155から供給された値D153を減算する。即ち、演算器156は、検査行列Hの1列に亘る全ての枝からのメッセージD103(チェックノードメッセージuj)の積算値から、バリアブルノードメッセージviを求めたい枝からのチェックノードメッセージujを減算して、その減算値(j=1からdv−1までのΣuj)を求める。さらに、演算器156には、その減算値(j=1からdv−1までのΣuj)に、受信用メモリ104から供給された受信データD104(u0i)を加算して、その結果得られる6ビットの値をメッセージD105(バリアブルノードメッセージvi)として出力する。

0084

以上のように、バリアブルノード計算器103では、式(1)の演算が行われ、バリアブルノードメッセージviが求められる。

0085

なお、図9の検査行列Hの列の重みの最大は5であるため、即ち、バリアブルノードバリアブルノードに供給されるチェックノードメッセージujの最大数は5であるため、バリアブルノード計算器103は、5個のチェックノードメッセージujを遅延させるFIFOメモリ155を有している。列の重みが5未満の列のバリアブルノードメッセージviを計算するときには、FIFOメモリ155における遅延量が、その列の重みの値に減らされる。

0086

また、演算器156は、レジスタ154から供給される9ビットの値D152から、FIFOメモリ155から供給される6ビットの値D153を減算するとともに、受信用メモリ104から供給される6ビットの受信データD104を加算する演算を行うから、その演算結果は、6ビットのメッセージD105で表すことができる最小値未満となるか、または最大値を越えることがある。演算器156は、演算結果が、6ビットのメッセージD105で表すことができる最小値未満である場合には、その最小値にクリッピングし、演算結果が、6ビットのメッセージD105で表すことができる最大値を越える場合には、その最大値にクリッピングする。

0087

図10の復号装置では、検査行列Hの重みにしたがって、制御部105から制御信号が与えられる。図10の復号装置によれば、枝用メモリ100および102、並びにチェックノード計算器101およびバリアブルノード計算器103のFIFOメモリ127,133,155の容量さえ足りれば、制御信号のみを変えることで様々な検査行列HのLDPC符号を復号することができる。

0088

なお、図示しないが、図10の復号装置において、復号の最終段においては、式(1)のバリアブルノード演算の代わりに、式(5)の演算が行われ、その演算結果が、最終的な復号結果として出力される。

0089

図10の復号装置を繰り返し用いて、LDPC符号を復号する場合には、チェックノード演算とバリアブルノード演算とが交互に行われる。即ち、図10の復号装置では、チェックノード計算器101によるチェックノード演算の結果を用いて、バリアブルノード計算器103によりバリアブルノード演算が行われ、バリアブルノード計算器103によるバリアブルノード演算の結果を用いて、チェックノード計算器101によりチェックノード演算が行われる。

0090

なお、図10は、復号装置の実装の例として、各ノードの演算を一つずつ順次行うことによって、LDPC符号の復号を行う(full serial decoding)復号装置であるが、その他、全ノードの演算を同時に行うことによって復号を行う(full parallel decoding)復号装置(非特許文献1)や、一つでも全てでもない、ある数のノードの演算を同時に行う(partly parallel decoding)復号装置(非特許文献2)も提案されている。

0091

ところで、例えば、図10の復号装置では、受信データD104を記憶する受信用メモリ104の記憶容量としては、少なくとも、LDPC符号の符号長と、受信データD104を表す量子化値のビット数(量子化ビット数)との乗算値だけのビット数が必要である。また、メッセージを記憶する枝用メモリ100や102の記憶容量としては、少なくとも、枝の総数(全枝数)と、メッセージを表す量子化値のビット数(量子化ビット数)との乗算値だけのビット数が必要である。

0092

従って、上述したように、符号長が108で、メッセージ(受信データD104を含む)を表す量子化値のビット数が6ビットで、枝の数が323である場合には、記憶容量が少なくとも648(=108×6)ビットの受信用メモリ104と、記憶容量が少なくとも1938(=323×6)ビットの枝用メモリ100および102とが必要となる。

0093

なお、ここでは、説明を簡単にするために、符号長を108としたが、現実的には、LDPC符号の符号長としては、数千程度が採用される。

0094

一方、LDPC符号の復号の精度を向上させるには、単純には、受信データD104を含むメッセージを表す量子化値として、ある程度のビット数の量子化値を採用する必要がある。

0095

しかしながら、上述したように、枝用メモリ100および102、並びに受信用メモリ104の記憶容量は、メッセージを表す量子化値のビット数に比例するので、メッセージを、多くのビット数の量子化値で表すと、復号装置を構成するメモリとして、容量の大きなメモリが必要となり、装置の規模が大型化する。

0096

C. Howland and A. Blanksby, "Parallel Decoding Architectures for Low Density Parity Check Codes", Symposium onCircuits and Systems, 2001
E. Yeo, P. Pakzad, B. Nikolic and V. Anantharam, "VLSIArchitectures for iterative Decoders in Magnetic Recording Channels",IEEE Transactions on Magnetics, Vol. 37, No. 2, March 2001

発明が解決しようとする課題

0097

本発明は、このような状況に鑑みてなされたものであり、LDPC符号の復号を、装置の大規模化を抑えつつ精度良く行うことができるようにするものである。

課題を解決するための手段

0098

本発明は、数値に割り当てられた第1の量子化値を、第1の量子化値よりも精度の高い数値を表す第2の量子化値に変換する第1の変換手段/第1の変換ステップと、第2の量子化値を、第1の量子化値に変換する第2の変換手段/第2の変換ステップとを含み、第1および第2の演算手段において、LDPC符号の復号のためのチェックノード演算およびバリアブルノード演算として行う処理のうちの、非線形関数の演算後から逆関数の演算までの処理では、第2の量子化値を使用し、他の処理では、第1の量子化値を使用することを特徴とする。

0099

本発明においては、第1の量子化値が、第2の量子化値に変換される一方、第2の量子化値が、第1の量子化値に変換される。そして、LDPC符号の復号のためのチェックノード演算およびバリアブルノード演算として行う処理のうちの、非線形関数の演算後から逆関数の演算までの処理では、第1の量子化値よりも精度の高い数値を表す第2の量子化値が使用され、他の処理では、第1の量子化値が使用される。

発明の効果

0100

本発明によれば、LDPC符号の復号を、装置の大規模化を抑えつつ精度良く行うことができる。

発明を実施するための最良の形態

0101

以下に本発明の実施の形態を説明するが、特許請求の範囲に記載の構成要件と、発明の実施の形態における具体例との対応関係を例示すると、次のようになる。この記載は、特許請求の範囲に記載されている発明をサポートする具体例が、発明の実施の形態に記載されていることを確認するためのものである。従って、発明の実施の形態中には記載されているが、構成要件に対応するものとして、ここには記載されていない具体例があったとしても、そのことは、その具体例が、その構成要件に対応するものではないことを意味するものではない。逆に、具体例が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その具体例が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。

0102

さらに、この記載は、発明の実施の形態に記載されている具体例に対応する発明が、特許請求の範囲に全て記載されていることを意味するものではない。換言すれば、この記載は、発明の実施の形態に記載されている具体例に対応する発明であって、この出願の特許請求の範囲には記載されていない発明の存在、すなわち、将来、分割出願されたり、補正により追加される発明の存在を否定するものではない。

0103

請求項1に記載の復号装置は、
LDPC(Low Density Parity Check)符号の復号装置(例えば、図13図17の復号装置)であって、
前記LDPC符号の復号のためのチェックノードのチェックノード演算であって、非線形関数(例えば、φ(x))の演算および前記非線形関数の逆関数(例えば、φ-1(x))の演算を含む前記チェックノード演算を行う第1の演算手段(例えば、図13のチェックノード計算器171や、図17の準チェックノード計算器412)と、
前記LDPC符号の復号のためのバリアブルノードのバリアブルノード演算を行う第2の演算手段(例えば、図13のバリアブルノード計算器103や、図17の準バリアブルノード計算器415)と
を備え、
前記第1の演算手段は、
数値に割り当てられた第1の量子化値を、前記第1の量子化値よりも精度の高い数値を表す第2の量子化値に変換する第1の変換手段(例えば、図14のLUT1121や、図19のLUT432)と、
前記第2の量子化値を、前記第1の量子化値に変換する第2の変換手段(例えば、図14のLUT1128や、図19のLUT439)と
を有し、
前記第1および第2の演算手段は、前記チェックノード演算およびバリアブルノード演算として行う処理のうちの、前記非線形関数の演算後から前記逆関数の演算までの処理では、前記第2の量子化値を使用し、他の処理では、前記第1の量子化値を使用する
ことを特徴とする。

0104

請求項7に記載の復号方法は、
LDPC(Low Density Parity Check)符号の復号のためのチェックノードのチェックノード演算であって、非線形関数(例えば、φ(x))の演算および前記非線形関数の逆関数(例えば、φ-1(x))の演算を含む前記チェックノード演算を行う第1の演算手段(例えば、図13のチェックノード計算器171や、図17の準チェックノード計算器412)と、
前記LDPC符号の復号のためのバリアブルノードのバリアブルノード演算を行う第2の演算手段(例えば、図13のバリアブルノード計算器103や、図17の準バリアブルノード計算器415)と
を備える前記LDPC符号の復号装置(例えば、図13図17の復号装置)の復号方法であって、
数値に割り当てられた第1の量子化値を、前記第1の量子化値よりも精度の高い数値を表す第2の量子化値に変換する第1の変換ステップ(例えば、図15のステップS1)と、
前記第2の量子化値を、前記第1の量子化値に変換する第2の変換ステップ(例えば、図15のステップS5)と
を含み、
前記第1および第2の演算手段において、前記チェックノード演算およびバリアブルノード演算として行う処理のうちの、前記非線形関数の演算後から前記逆関数の演算までの処理では、前記第2の量子化値を使用し、他の処理では、前記第1の量子化値を使用する
ことを特徴とする。

0105

以下、図面を参照して、本発明の実施の形態について説明する。

0106

図13は、本発明の一実施の形態の、LDPC符号を復号する復号装置の第1の構成例を示している。なお、図中、図10の復号装置と対応する部分については、同一の符号を付してあり、以下では、その説明は、適宜省略する。

0107

図13の復号装置は、枝用メモリ100,102、バリアブルノード計算器103、受信用メモリ104、制御部105が設けられている点で、図10の復号装置と共通するが、チェックノード計算器101に代えてチェックノード計算器171が設けられている点で、図10の復号装置と相違している。

0108

ここで、図13の復号装置では、例えば、前述の図9に示した検査行列Hで表されるLDPC符号(符号化率2/3、符号長108)の復号が行われることとする。後述する図17の復号装置においても同様である。

0109

図13の復号装置では、チェックノード計算器171がチェックノード演算を行い、バリアブルノード計算器103がバリアブルノード演算を行い、これらのチェックノード演算とバリアブルノード演算とが交互に行われることによって、LDPC符号が復号される。

0110

即ち、受信用メモリ104には、LDPC符号の受信データu0iが、符号長(ここでは、上述したように108)の単位で順次供給されて記憶される。

0111

そして、バリアブルノード計算器103は、LDPC符号の復号のためのバリアブルノードのバリアブルノード演算を行う。

0112

即ち、枝用メモリ102には、後述するチェックノード計算器171によるチェックノード演算の結果としてのメッセージD102(チェックノードメッセージuj)が格納されており、枝用メモリ102は、そのメッセージD102を、メッセージD103として、バリアブルノード計算器103に供給する。さらに、バリアブルノード計算器103には、制御部105から制御信号D107が供給されるとともに、受信用メモリ104から受信データD104が供給される。

0113

バリアブルノード計算器103は、前述の図12に示したように構成されており、制御信号D107に基づき、枝用メモリ100から供給されるメッセージD103(チェックノードメッセージuj)と受信用メモリ100から供給される受信データD104(u0i)を用い、式(1)に従ってバリアブルノード演算を行い、そのバリアブルノード演算の結果得られるメッセージD105(バリアブルノードメッセージvi)を、メッセージD100として、枝用メモリ100に供給する。

0114

枝用メモリ100は、バリアブルノード計算器103から供給される、バリアブルノード演算の結果であるメッセージD100(バリアブルノードメッセージvi)を格納していく。そして、枝用メモリ100は、メッセージD100を、メッセージD101として読み出し、チェックノード計算器171に供給する。

0115

チェックノード計算器171は、LDPC符号の復号のためのチェックノードのチェックノード演算であって、非線形関数の演算および非線形関数の逆関数の演算を含むチェックノード演算を行う。

0116

即ち、チェックノード計算器171は、制御部105から供給される制御信号D106に基づき、枝用メモリ100から供給されるメッセージD101(バリアブルノードメッセージvi)を用いて、非線形関数φ(x)の演算およびその非線形関数φ(x)の逆関数φ-1(x)の演算を含む式(7)に従ってチェックノード演算を行い、そのチェックノード演算によって求められたメッセージD102(チェックノードメッセージuj)を、後段の枝用メモリ102に供給する。

0117

枝用メモリ102は、前段のチェックノード計算器171から供給されるメッセージD102を格納していく。そして、枝用メモリ102に記憶されたメッセージD102は、上述したようにメッセージD103として読み出され、バリアブルノード計算器103に供給される。

0118

図13の復号装置では、受信用メモリ104に記憶された符号長分の受信データu0iについて、バリアブルノード演算とチェックノード演算が、例えば、所定の複数回数だけ繰り返し行われ、また、最後の回には、式(1)のバリアブルノード演算の代わりに、式(5)の演算が行われ、その演算結果が、受信用メモリ104に記憶された符号長分の受信データu0i(LDPC符号)の最終的な復号結果として出力される。

0119

図13の復号装置は、チェックノード演算およびバリアブルノード演算を繰り返し行うことによって、LDPC符号を復号する点では、前述の図10の復号装置と共通する。

0120

但し、図13の復号装置は、チェックノード演算およびバリアブルノード演算として行う処理のうちの、非線形関数φ(x)の演算後から逆関数φ-1(x)の演算までの処理では、図10の復号装置が使用しているのと同様の量子化値(第1の量子化値)よりも精度の高い数値を表す量子化値(第2の量子化値)を使用し、他の処理では、図10の復号装置が使用しているのと同様の量子化値を使用する。

0121

ここで、図10の復号装置では、上述したように、メッセージ(受信データu0iも同様)は、所定の数値範囲を符号ビット付きの6ビットで表すことができる64値に均等に分割する各数値に割り当てられた6ビットの量子化値で表される。即ち、所定の数値範囲が−R/2から+R/2であるとすると(R>0)、メッセージを表す6ビットの各量子化値は、−R/2から+R/2−R/64までの、量子化幅であるR/64きざみの64の各数値に割り当てられ、その各数値を表す。いま、この、メッセージを表す6ビットの量子化値を、通常量子化値という。

0122

また、図13の復号装置において、非線形関数φ(x)の演算後から逆関数φ-1(x)の演算までの処理で使用される、通常量子化値よりも精度の高い数値を表す量子化値を、高精度量子化値という。

0123

高精度量子化値は、通常量子化値よりも精度の高い数値を表すから、量子化幅、即ち、ある量子化値に割り当てられた数値と、その量子化値よりも1だけ小さい量子化値に割り当てられた数値との差(の絶対値)が通常量子化値よりも小さい。

0124

従って、高精度量子化値のビット数を、通常量子化値のビット数(ここでは6ビット)と同一とすると、高精度量子化値によって表すことができる数値範囲は、通常量子化値によって表すことができる数値範囲よりも狭くなる。即ち、高精度量子化値によって表すことができる最大値と最小値との差(ダイナミックレンジ)は、通常量子化値によって表すことができる最大値と最小値との差(ダイナミックレンジ)よりも狭くなる

0125

また、高精度量子化値のビット数を、通常量子化値のビット数と同一とした場合の、高精度量子化値によって表すことができるダイナミックレンジを、Dy1と表すとともに、そのような高精度量子化値の量子化幅を、Qd1と表すと、例えば、高精度量子化値の量子化幅をQd1のままで、ダイナミックレンジがDy1よりも広いDy2の数値範囲を高精度量子化値で表し、あるいは高精度量子化値の量子化幅をQd1より小さいQd2として、ダイナミックレンジがDy1の数値範囲を高精度量子化値で表す場合には、高精度量子化値のビット数は、通常量子化値のビット数よりも多く必要となる。

0126

通常量子化値よりも精度の高い数値を表す量子化値、つまり、量子化幅が通常量子化値よりも小さい量子化値であれば、ダイナミックレンジやビット数にかかわらず、高精度量子化値として採用しうるが、ここでは、量子化幅が通常量子化値よりも小さい量子化値であって、ダイナミックレンジが通常量子化値よりも広く、ビット数も通常量子化値よりも多い量子化値を、高精度量子化値として採用することとする。

0127

いま、高精度量子化値のビット数を、6ビットの通常量子化値よりも多い、例えば、符号ビットを含む10ビットとすると、図13の復号装置は、非線形関数φ(x)の演算後から逆関数φ-1(x)の演算までの処理(以下、適宜、非線形関数演算間処理という)では、10ビットの高精度量子化値(第2の量子化値)を使用し、他の処理では、6ビットの通常量子化値(第1の量子化値)を使用する。

0128

そして、10ビットの高精度量子化値が使用される非線形関数演算間処理は、チェックノード演算の一部の処理であるため、枝用メモリ100と102に記憶されるメッセージにも、また、受信用メモリ104に記憶される受信データu0iにも、6ビットの通常量子化値が使用される。

0129

従って、図13の復号装置において、枝用メモリ100,102、および受信用メモリ104に必要な記憶容量は、図10の復号装置のそれと同一である。

0130

次に、図14は、図13のチェックノード計算器171の構成例を示している。なお、図中、図11のチェックノード計算器101と対応する部分については、同一の符号を付してあり、以下では、その説明は、適宜省略する。

0131

チェックノード計算器171は、図11のLUT121、演算器122、レジスタ123、セレクタ124、レジスタ125、演算器126、FIFOメモリ127、LUT128それぞれに代えて、LUT1121、演算器1122、レジスタ1123、セレクタ1124、レジスタ1125、演算器1126、FIFOメモリ1127、LUT1128が設けられており、さらに、図14において太線で示す部分のビット数が、高精度量子化値と通常量子化値とのビット数の差である4ビットだけ多くなっている点で、図11のチェックノード計算器101と相違している。

0132

図14のチェックノード計算器171も、図11のチェックノード計算器101と同様に、制御部105から供給される、例えば、1ビットの制御信号D106に基づき、枝用メモリ100から1つずつ読み込まれるメッセージD101(バリアブルノードメッセージvi)を用いて、式(7)にしたがってチェックノード演算を行う。

0133

即ち、図15は、チェックノード計算器171で行われる処理を示している。

0134

チェックノード計算器171では、検査行列Hの各列に対応するバリアブルノードからの6ビットのメッセージD101(バリアブルノードメッセージvi)が1つずつ読み込まれ、その下位5ビットである絶対値D122(|vi|)がLUT1121に、その最上位ビットである符号ビットD121がEXOR回路129とFIFO(First In First Out)メモリ133にそれぞれ供給される。また、チェックノード計算器171には、制御部105から制御信号D106が供給され、その制御信号D106は、セレクタ1124とセレクタ131に供給される。

0135

LUT1121は、5ビットの絶対値D122(|vi|)に対して、式(7)における非線形関数φ(|vi|)の演算結果D1123(φ(|vi|))を対応付けて記憶している。さらに、LUT1121では、絶対値D122(|vi|)は、通常量子化値で表されているのに対して、非線形関数φ(|vi|)の演算結果D1123(φ(|vi|))は、高精度量子化値で表されている。即ち、LUT1121は、通常量子化値で表される5ビットの絶対値D122(|vi|)に対して、例えば、高精度量子化値で表される9ビットの、非線形関数φ(|vi|)の演算結果D1123(φ(|vi|))を対応付けて記憶している。

0136

LUT1121は、ステップS1において、通常量子化値で表される5ビットの絶対値D122(|vi|)を入力として、それに対応付けられている、高精度量子化値で表される9ビットの、非線形関数φ(|vi|)の演算結果D1123(φ(|vi|))を読み出し、演算器1122とFIFOメモリ1127に出力する。

0137

従って、LUT1121は、ステップS1において、式(7)における非線形関数φ(|vi|)を演算する処理、および通常量子化値を高精度量子化値に変換する処理を、等価的に行い、以降は、後述するLUT1128において、高精度量子化値を通常量子化値に変換する処理が行われるまで、高精度量子化値を使用して処理が行われる。

0138

その後、ステップS2において、演算器1122は、9ビットの演算結果D1123(φ(|vi|))とレジスタ1123に格納されている13ビットの値D1124とを加算することにより、演算結果D1123を積算し、その結果得られる13ビットの積算値をレジスタ1123に再格納する。なお、検査行列Hの1行に亘る全ての枝からのメッセージD101の絶対値D122(|vi|)に対する演算結果が積算された場合、レジスタ1123はリセットされる。

0139

ここで、演算器1122およびレジスタ1123では、LUT1121から供給される9ビットの演算結果D1123(φ(|vi|))が、最大で、FIFOメモリ1127における最大の遅延回数分、即ち、検査行列Hの行の最大の重み分の回数だけ積算される。いま、図9の検査行列Hの行の最大の重みは9であり、従って、演算器1122およびレジスタ1123では、9ビットの高精度量子化値が、最大で、9回積算される(9ビットの高精度量子化値の9個分の積算が行われる)。このため、演算器1122の出力以降においては、9ビットの高精度量子化値を9回積算した値を表すことができるように、高精度量子化値のビット数は、LUT1121が出力する9ビットの演算結果D1123(φ(|vi|))よりも4ビット(9(回)を表すことができる最小のビット数)だけ多い13ビットになっている。

0140

検査行列Hの1行に亘るメッセージD101(バリアブルノードメッセージvi)が1つずつ読み込まれ、レジスタ1123に1行分の演算結果D1123が積算された積算値が格納された場合、制御部105から供給される制御信号D106は、0から1に変化する。例えば、検査行列Hの行の重み(row weight)が「9」である場合、制御信号D106は、1から8クロック目までは、「0」となり、9クロック目では「1」となる。

0141

制御信号D106が「1」の場合、セレクタ1124は、ステップS3において、レジスタ1123に格納されている値、即ち、検査行列Hの1行に亘る全ての枝からのメッセージD101(バリアブルノードメッセージvi)から求められたφ(|vi|)が積算された13ビットの積算値D1124(i=1からi=dcまでのΣφ(|vi|))を選択し、13ビットの値D1125として、レジスタ1125に出力して格納させる。レジスタ1125は、格納している値D1125を、13ビットの値D1126として、セレクタ1124と演算器1126に供給する。制御信号D106が「0」の場合、セレクタ1124は、レジスタ1125から供給された値D1126を選択し、レジスタ1125に出力して再格納させる。即ち、検査行列Hの1行に亘る全ての枝からのメッセージD101(バリアブルノードメッセージvi)から求められたφ(|vi|)が積算されるまで、レジスタ1125は、前回積算されたφ(|vi|)を、セレクタ1124と演算器1126に供給する。

0142

一方、FIFOメモリ1127は、レジスタ1125から新たな値D1126(i=1からi=dcまでのΣφ(|vi|))が出力されるまでの間、LUT1121が出力した9ビットの演算結果D1123(φ(|vi|))を遅延し、9ビットの値D1127として演算器1126に供給する。演算器1126は、ステップS4において、レジスタ1125から供給された13ビットの値D1126から、FIFOメモリ1127から供給された9ビットの値D1127を減算し、その減算結果を、9ビットの減算値D1128としてLUT1128に供給する。即ち、演算器1126は、検査行列Hの1行に亘る全ての枝からのメッセージD101(バリアブルノードメッセージvi)から求められたφ(|vi|)の積算値から、チェックノードメッセージujを求めたい枝からのメッセージD101(バリアブルノードメッセージvi)から求められたφ(|vi|)を減算して、その減算値(i=1からi=dc−1までのΣφ(|vi|))を減算値D1128としてLUT1128に供給する。

0143

なお、レジスタ1125から供給される13ビットの値D1126から、FIFOメモリ1127から供給される9ビットの値D1127を減算した減算結果としての量子化値(高精度量子化値)が、9ビットの減算値D1128で表すことができる最大値を越える場合には、演算器1126は、減算結果としての高精度量子化値を、9ビットの高精度量子化値で表すことができる最大値にクリッピングし、9ビットの減算値D1128を出力する。

0144

LUT1128は、減算値D1128(i=1からi=dc−1までのΣφ(|vi|))に対して、式(7)における逆関数φ-1(Σφ(|vi|))の演算を行った演算結果D1129(φ-1(Σφ(|vi|)))を対応付けて記憶している。さらに、LUT1128では、減算値D1128(i=1からi=dc−1までのΣφ(|vi|))は、高精度量子化値で表されているのに対して、逆関数φ-1(Σφ(|vi|))の演算結果D1129(φ-1(Σφ(|vi|)))は、通常量子化値で表されている。即ち、LUT1128は、高精度量子化値で表される9ビットの減算値D1128(i=1からi=dc−1までのΣφ(|vi|))に対して、通常量子化値で表される5ビットの、逆関数φ-1(Σφ(|vi|))の演算結果D1129(φ-1(Σφ(|vi|)))を対応付けて記憶している。

0145

LUT1128は、ステップS5において、高精度量子化値で表される9ビットの減算値D1128(i=1からi=dc−1までのΣφ(|vi|))を入力として、それに対応付けられている、通常量子化値で表される5ビットの、逆関数φ-1(Σφ(|vi|))の演算結果D1129(φ-1(Σφ(|vi|)))を読み出して出力する。

0146

従って、LUT1128は、ステップS5において、式(7)における逆関数φ-1(Σφ(|vi|))を演算する処理、および高精度量子化値を通常量子化値に変換する処理を、等価的に行い、以降は、上述したLUT1121において、通常量子化値を高精度量子化値に変換する処理が行われるまで、通常量子化値を使用して処理が行われる。

0147

以上の処理と並行して、EXOR回路129、レジスタ130、セレクタ131、レジスタ132、FIFOメモリ133、EXOR回路134では、図11のチェックノード計算器101と同様の処理が行われ、これにより、EXOR回路134は、検査行列Hの1行に亘る全ての枝からのメッセージD101(バリアブルノードメッセージvi)の符号ビットD121(sign(|vi|))の乗算値を、チェックノードメッセージujを求めたい枝からのメッセージD101の符号ビットD121(sign(|vi|))で除算して、その除算値(i=1からi=dc−1までのΠsign(|vi|))を除算値D135として出力する。

0148

そして、チェックノード計算器171では、LUT1128から出力された通常量子化値の5ビットの演算結果D1129を下位5ビットとするとともに、EXOR回路134から出力された1ビットの除算値D135を最上位ビット(符号ビット)とする合計6ビットの通常量子化値で表されるメッセージD102(チェックノードメッセージuj)が出力される。

0149

従って、チェックノード計算器171では、LUT1121において、通常量子化値を高精度量子化値に変換するとともに、LUT1128において、高精度量子化値を通常量子化値に変換することにより、チェックノード演算およびバリアブルノード演算として行う処理のうちの、非線形関数φ(x)の演算後からその逆関数φ-1(x)の演算までの処理では、高精度量子化値を使用し、他の処理では、通常量子化値を使用するので、LDPC符号の復号を、復号装置の大規模化を抑えつつ精度良く行うことができる。

0150

即ち、図16は、非線形関数φ(x)と、その逆関数φ-1(y)とを示している。なお、図16において、○印は、通常量子化値を採用した場合に、非線形関数φ(x)の演算結果とその引数xとがとり得る数値、および逆関数φ-1(y)とその引数yとがとり得る数値を示している。

0151

図16の左側は、非線形関数φ(x)を示しており、図16の右側は、その逆関数φ-1(y)を示している。

0152

図16の左側に示した非線形関数φ(x)は、その引数xが、ある程度の大きな数値以上となると、ほぼ0となる。

0153

一方、図16の右側に示した逆関数φ-1(y)は、その引数yが、数値0付近である場合に、急峻に変化する。

0154

従って、チェックノード演算である式(7)の演算において、非線形関数φ(|vi|)の演算後からその逆関数φ-1(x)の演算までの処理を、通常量子化値を使用して行った場合、演算精度劣化する。

0155

即ち、非線形関数φ(x)の演算結果を、通常量子化値で表すと、ある程度の大きな数値以上の引数xに対しては、すべて、非線形関数φ(x)の演算結果として、同一の数値0を表す通常量子化値が得られる。つまり、ある程度の大きな数値以上の引数xに対する非線形関数φ(x)の演算結果は、ほぼ0となるため、通常量子化値によって精度良く表すことが困難である。

0156

また、式(7)のチェックノード演算において、逆関数φ-1(y)の引数yとなるのは、非線形関数φ(|vi|)の積算値(i=1からi=dc−1までのΣφ(|vi|))であるが、非線形関数φ(|vi|)の演算結果を表す通常量子化値は、上述したように、ある程度の大きな数値以上の引数|vi|に対しては、すべて、数値0を表す通常量子化値となる。

0157

従って、積算の対象となる非線形関数φ(|vi|)の演算結果として、すべて、数値0を表す通常量子化値が得られた場合には、その積算値(i=1からi=dc−1までのΣφ(|vi|))も、数値0を表す通常量子化値となり、逆関数φ-1(y)の引数yとして、数値0を表す通常量子化値が与えられることになる。

0158

一方、逆関数φ-1(y)は、その引数yが、数値0付近である場合に急峻に変化するから、逆関数φ-1(y)の演算結果として、精度の良い演算結果を得るためには、特に、0付近の数値を精度良く表す量子化値によって、引数yを表現することが望ましい。

0159

しかしながら、通常量子化値を使用した場合には、上述したように、ある程度の大きな数値以上の引数|vi|に対しては、すべて、非線形関数φ(|vi|)の演算結果として、数値0を表す通常量子化値が得られ、その結果、逆関数φ-1(Σφ(|vi|))の引数となる積算値Σφ(|vi|)を表す通常量子化値も、数値0を表す通常量子化値となる。

0160

このため、積算値Σφ(|vi|)が数値0付近の値である場合には、その積算値Σφ(|vi|)が僅かに違えば、本来は、逆関数φ-1(Σφ(|vi|))の演算結果が大きく異なるはずなのに、0付近の積算値Σφ(|vi|)が、すべて数値0を表す通常量子化値で表されてしまうために、僅かに違う積算値Σφ(|vi|)に対し、逆関数φ-1(Σφ(|vi|))の演算結果として、同一の演算結果、つまり、誤差の大きな演算結果が得られることになる。

0161

これに対して、非線形関数φ(|vi|)の演算後からその逆関数φ-1(x)の演算までの処理を、高精度量子化値を使用して行う場合には、ある程度の大きな数値以上の引数xに対しても、非線形関数φ(x)の演算結果として、0付近の数値を精度良く表す高精度量子化値が得られる。さらに、その結果、逆関数φ-1(Σφ(|vi|))の引数となる積算値Σφ(|vi|)が、0付近の数値であっても、その数値を精度良く表す高精度量子化値が得られる。

0162

従って、積算値Σφ(|vi|)が数値0付近の値である場合であっても、その積算値Σφ(|vi|)が僅かに異なるごとに応じて異なる、精度の良い逆関数φ-1(Σφ(|vi|))の演算結果(を表す高精度量子化値)が得られることになる。そして、その結果、LDPC符号の復号を精度良く行うことができる。

0163

さらに、非線形関数φ(|vi|)の演算後からその逆関数φ-1(x)の演算までの処理を、高精度量子化値を使用し、他の処理を、通常量子化値を使用して行うので、チェックノード計算器171(図14)において高精度量子化値を使用する部分、即ち、LUT1121乃至LUT1128の規模が、高精度量子化値と通常量子化値とのビット数の差分の分だけ僅かに大きくなるだけであり、上述したように、図13の復号装置の枝用メモリ100,102、および受信用メモリ104に必要な記憶容量は、通常量子化値を使用する図10の復号装置のそれと変わらない。

0164

従って、LDPC符号の復号を、復号装置の大規模化を抑えつつ精度良く行うことができる。

0165

なお、図9の検査行列Hの行の重みの最大は9であるため、即ち、チェックノードに供給されるメッセージの最大数は9であるため、チェックノード計算器171(図14)は、9個のメッセージ(φ(|vi|))を遅延させるFIFOメモリ1127とFIFOメモリ133を有し、行の重みが9未満の行のメッセージを計算するときには、FIFOメモリ1127とFIFOメモリ133における遅延量が、その行の重みの値に減らされる。

0166

次に、図17は、本発明の一実施の形態の、LDPC符号を復号する復号装置の第2の構成例を示している。

0167

図17の復号装置は、LDPC符号の復号を、復号装置の大規模化を抑えつつ精度良く行い、さらに、図13の復号装置よりも、復号装置に必要となるメモリの記憶容量を低減することができるようになっている。

0168

なお、図17の復号装置では、例えば、上述の図13の復号装置と同様に、前述の図9に示した検査行列Hで表されるLDPC符号(符号化率2/3、符号長108)の復号が行われる。

0169

図17において、復号装置は、復号途中結果格納用メモリ410、スイッチ411、準チェックノード計算器412、枝用メモリ413、準バリアブルノード計算器415、受信用メモリ416、および制御部417から構成され、図13の復号装置と同様のチェックノード演算とバリアブルノード演算とを等価的に繰り返し行うことにより、LDPC符号を復号する。

0170

ここで、図17の復号装置の各部について説明する前に、上述の図14と、図18乃至図20を用いて、図17の準チェックノード計算器412および準バリアブルノード計算器415と、図13のチェックノード計算器171およびバリアブルノード計算器103との関係について説明する。

0171

図14は、上述したように、チェックノード演算を行う図13のチェックノード計算器171の構成例を示している。

0172

図18は、バリアブルノード演算を行う図13のバリアブルノード計算器103の構成例を示している。なお、図13のバリアブルノード計算器103は、図10のバリアブルノード計算器103と同一であり、従って、図18に示した図13のバリアブルノード計算器103は、図12に示した図10のバリアブルノード計算器103と同一構成となっている。

0173

但し、図18では、図12の演算器156を、2つの演算器1561と1562に分けて図示してある。即ち、図12の演算器156は、前述したように、レジスタ154から供給された値D152から、FIFOメモリ155から供給された値D153を減算し、さらに、その減算値に、受信用メモリ104から供給された受信データD104を加算して、その結果得られる6ビットの値をメッセージD105(バリアブルノードメッセージvi)として出力するから、演算器156が行う処理は、レジスタ154から供給された値D152を対象に、FIFOメモリ155から供給された値D153を減算する減算処理と、受信用メモリ104から供給された受信データD104を加算する加算処理とに分けることができる。

0174

そこで、図18では、図12の演算器156を、加算処理を行う演算器1561と、減算処理を行う演算器1562とに分けて図示してある。

0175

一方、図19は、図17の準チェックノード計算器412の構成例を示しており、図20は、図17の準バリアブルノード計算器415の構成例を示している。

0176

図17の復号装置では、準チェックノード計算器412がチェックノード演算そのものを行うとともに、準バリアブルノード計算器415kがバリアブルノード演算そのものを行うのではなく、準チェックノード計算器412がチェックノード演算とバリアブルノード演算の一部を行い、準バリアブルノード計算器415がバリアブルノード演算の他の一部を行う。

0177

即ち、図19の準チェックノード計算器412は、ブロックA'とブロックB'から構成されている。ブロックA’は、図14のチェックノード計算器171のチェックノード演算を行うブロックAに対応している。また、ブロックB’は、図18のバリアブルノード計算器103の一部である、検査行列Hの各列の全ての枝に対応するチェックノードメッセージujの積算値から、バリアブルノードメッセージviを求めたい枝に対応するチェックノードメッセージujを減算するブロックBに対応している。

0178

一方、図20の準バリアブルノード計算器415は、ブロックC'から構成されている。ブロックC'は、図18のバリアブルノード計算器103の他の一部である、検査行列Hの各列の枝に対応するチェックノードメッセージujを積算し、その積算値に受信データu0iを加算するブロックCに対応している。

0179

つまり、図13のチェックノード計算器171は、図14に示すように、チェックノード演算そのものを行うブロックAで構成される。また、図13のバリアブルノード計算器103は、図18に示すように、検査行列Hの各列の全ての枝に対応するチェックノードメッセージujの積算値から、バリアブルノードメッセージviを求めたい枝に対応するチェックノードメッセージujを減算する、バリアブルノード演算の一部を行うブロックBと、検査行列Hの各列の枝に対応するチェックノードメッセージujを積算し、その積算値に受信データu0iを加算する、バリアブルノード演算の他の一部を行うブロックCとに分けることができる。

0180

図19の準チェックノード計算器412は、図14のブロックAに対応するブロックA'と、図18のブロックBに対応するブロックB'から構成され、ブロックB’において、バリアブルノード演算の一部を行うとともに、ブロックAにおいて、チェックノード演算そのものを行う。ここで、準チェックノード計算器412で行われる、バリアブルノード演算の一部とチェックノード演算を、以下、適宜、準チェックノード演算という。

0181

一方、図20の準バリアブルノード計算器415は、図18のブロックCに対応するブロックC’で構成され、ブロックC’において、バリアブルノード演算の他の一部を行う。ここで、準バリアブルノード計算器415で行われる、バリアブルノード演算の他の一部を、以下、適宜、準バリアブルノード演算という。

0182

図17の復号装置では、準チェックノード計算器412が、復号途中結果格納用メモリ410の記憶内容等を用いて、準チェックノード演算(バリアブルノード演算の一部とチェックノード演算)を行い、その結果得られるチェックノードメッセージujを、枝用メモリ413に供給して記憶させる。さらに、準バリアブルノード計算器415が、枝用メモリ413に記憶されたチェックノードメッセージuj等を用いて、準バリアブルノード演算(バリアブルノード演算の他の一部)を行い、その結果得られる復号途中結果vを、復号途中結果格納用メモリ410に供給して記憶させる。

0183

従って、図17の復号装置では、準チェックノード計算器412による準チェックノード演算と、準バリアブルノード計算器415による準バリアブルノード演算とが交互に行われることにより、結局、チェックノード演算とバリアブルノード演算とが交互に行われ、これにより、LDPC符号の復号が行われる。

0184

なお、図18のバリアブルノード計算器103では、ブロックCにおいて、検査行列Hの各列の枝に対応するチェックノードメッセージujを積算し、その積算値に受信データu0iを加算する加算処理を行い、ブロックBにおいて、その加算処理の結果得られる値(検査行列Hの各列の全ての枝に対応するチェックノードメッセージujの積算値と、受信データu0iとの加算値)からバリアブルノードメッセージviを、求めたい枝からのチェックノードメッセージujを減算する減算処理を行うために、バリアブルノードメッセージviを求めたい枝からのチェックノードメッセージujを、検査行列Hの各列の枝に対応するチェックノードメッセージujの積算が終了するまで遅延するFIFOメモリ155が必要となる。

0185

一方、図19の準チェックノード計算器412のブロックB’では、対応するブロックB(図18)と同様に、検査行列Hの各列の全ての枝に対応するチェックノードメッセージujの積算値から、バリアブルノードメッセージviを求めたい枝からのチェックノードメッセージujを減算する減算処理が行われるが、図17の復号装置では、チェックノードメッセージujが枝用メモリ413に記憶されており、その枝用メモリ413から、準チェックノード計算器412に対して、バリアブルノードメッセージviを求めたい枝からのチェックノードメッセージuj(メッセージD411)が供給されるようになっている。

0186

従って、図17の復号装置では、バリアブルノードメッセージviを求めたい枝からのチェックノードメッセージujを、検査行列Hの各列の枝に対応するチェックノードメッセージujの積算が終了するまで遅延するFIFOメモリ155が必要ない。よって、図17の符号長量は、FIFOメモリ155の分だけ、図13の復号装置よりも小型に構成することができる。

0187

次に、図17の準チェックノード計算器412で行われる準チェックノード演算と、準バリアブルノード計算器415で行われる準バリアブルノード演算について、式を用いて説明する。

0188

準チェックノード計算器412は、次の式(8)の演算(バリアブルノード演算の一部)と、上述した式(7)の演算(チェックノード演算)とを、準チェックノード演算として行い、その準チェックノード演算の結果であるチェックノードメッセージujを、枝用メモリ413に供給して格納(記憶)させる。また、準バリアブルノード計算器415は、上述した式(5)の演算(バリアブルノード演算の他の一部)を、準バリアブルノード演算として行い、そのバリアブルノード演算の結果である復号途中結果vを、復号途中結果格納用メモリ410に供給して格納させる。

0189

・・・(8)

0190

なお、式(8)のudvは、バリアブルノード演算によって、検査行列Hのi列のバリアブルノードメッセージviを求めようとする枝からのチェックノード演算の結果を表している。即ち、udvは、バリアブルノード演算によってバリアブルノードメッセージviを求めたい枝に対応するチェックノードメッセージuj(枝からのチェックノードメッセージuj)である。

0191

ここで、上述した式(5)の演算の結果得られる復号途中結果vは、受信データu0iと検査行列Hのi列の各行の1に対応するすべての枝からのチェックノード演算の結果得られたチェックノードメッセージujとを加算したものであるので、式(8)にしたがい、そのような復号途中結果vから、検査行列Hのi列の、各行の1に対応する枝からのチェックノード演算によって求められたチェックノードメッセージujのうち、バリアブルノードメッセージviを求めようとする枝からのチェックノードメッセージudvを減算することにより、各枝のバリアブルノードメッセージviを求めることができる。

0192

従って、バリアブルノードメッセージviを求める式(1)のバリアブルノード演算は、式(5)の演算と、式(8)の演算とに分けることができる。

0193

一方、チェックノードメッセージujを求めるチェックノード演算は、式(7)で表される。

0194

従って、式(1)のバリアブルノード演算と、式(7)のチェックノード演算との処理は、式(5)の演算と、式(8)および式(7)の演算との処理に等価である。

0195

そこで、図17の復号装置では、準チェックノード計算器412において、式(8)および式(7)の演算(準チェックノード演算)を行うとともに、準バリアブルノード計算器415において、式(5)の演算(準バリアブルノード演算)を行い、LDPC符号の復号が行われる。

0196

なお、式(5)の準バリアブルノード演算によって求められる復号途中結果vは、式(1)のバリアブルノード演算の結果得られる各枝のバリアブルノードメッセージviに対して、そのバリアブルノードメッセージviに対応する枝からのチェックノードメッセージujを加算したものであるから、検査行列Hの1列(1つのバリアブルノード)に対して、1つだけ求められる。従って、符号長分の受信データu0iに対しては、符号長分(検査行列Hの列数)の復号途中結果vが求められる。

0197

図17の復号装置では、準チェックノード計算器412が、準バリアブルノード計算器415による準バリアブルノード演算の結果である検査行列Hの各列に対応する復号途中結果vを用いて、準チェックノード演算を行い、その準チェックノード演算の結果得られるチェックノードメッセージ(各チェックノードが各枝に出力するチェックノードメッセージ)ujを、枝用メモリ413に格納する。

0198

従って、枝用メモリ413に必要な記憶容量は、チェックノード演算の結果を格納する図13の枝用メモリ102と同様に、検査行列Hの1の数(全枝数)とチェックノードメッセージujの量子化ビット数(本実施の形態では、通常量子化値のビット数)とを乗算した値となる。

0199

一方、準バリアブルノード計算器415は、準チェックノード計算器412による準チェックノード演算の結果である検査行列Hのi列の、各行の“1”に対応するチェックノードメッセージujと受信データu0iを用いて、準バリアブルノード演算を行い、その準バリアブルノード演算の結果得られるi列に対応する復号途中結果vを、復号途中結果格納用メモリ410に格納する。

0200

従って、復号途中結果格納用メモリ410に必要な記憶容量は、検査行列Hの“1”の数より少ない検査行列Hの列数、即ち、LDPC符号の符号長と、復号途中結果vの量子化ビット数(本実施の形態では、通常量子化値のビット数)とを乗算した値となる。

0201

以上から、検査行列Hにおける1が疎らなLDPC符号を復号する図17の復号装置では、図13の枝用メモリ100に比べて、復号途中結果格納用メモリ410の記憶容量を削減することができ、これにより、図17の復号装置の装置規模を小さくすることができる。

0202

さらに、図17の復号装置において、準バリアブルノード計算器415が行う式(5)の準バリアブルノード演算は、チェックノード演算とバリアブルノード演算とを交互に繰り返すことにより、LDPC符号の繰り返し復号を行うにあたって、そのLDPC符号の最終的な復号結果を求める演算であり、従って、図17の復号装置には、図13の復号装置のように、LDPC符号の最終的な復号結果を求める式(5)の演算を行う不図示のブロックを有する必要がない。従って、そのようなブロックが不要な分だけ、図13の復号装置に比べて、図17の復号装置の装置規模を小さくすることができる。

0203

次に、図17の復号装置の各部について詳細に説明する。

0204

復号途中結果格納用メモリ410には、準バリアブルノード計算器415から、検査行列Hの列ごとの、式(5)の準バリアブルノード演算の結果得られる復号途中結果D415(式(5)のv)が供給され、復号途中結果格納用メモリ410は、準バリアブルノード計算器415から供給される復号途中結果D415を、順次記憶する。復号途中結果格納用メモリ410に記憶された、検査行列Hの列ごとの復号途中結果D415は、そこから順次読み出され、スイッチ411に供給される。

0205

スイッチ411には、復号途中結果格納用メモリ410から復号途中結果D415が供給される他、受信用メモリ416から、受信データD417(u0i)が供給される。スイッチ411は、制御部417から供給される制御信号D421にしたがって、復号途中結果格納用メモリ410から供給される復号途中結果D415、または受信用メモリ416から供給される受信データD417のうちのいずれか一方を選択し、復号途中結果D411として、準チェックノード計算器412に供給する。

0206

即ち、受信用メモリ416に、受信データD417が記憶された直後(受信データD417が記憶された後、その受信データD417を用いた最初の準バリアブルノード演算が行われる前)は、その受信データD417に対する復調途中結果D415が、復号途中結果格納用メモリ410に記憶されていないため、その復調途中結果D415を用いた準チェックノード演算を行うことができない。そこで、受信用メモリ416に、受信データD417が記憶された直後においては、制御部417は、受信データD417の選択を指示する制御信号D421を、スイッチ411に供給する。これにより、スイッチ411では、受信用メモリ416から供給される受信データD417が選択され、復号途中結果D411として、準チェックノード計算器412に供給される。従って、この場合、準チェックノード計算器412では、受信データD417を、式(8)の復号途中結果vとして用いて、準チェックノード演算が行われる。なお、準チェックノード演算には、枝用メモリ413に記憶されたチェックノードメッセージujが使用されるが、枝用メモリ413のチェックノードメッセージujは、新たな受信データD417が、受信用メモリ416に記憶されたときに、0に初期化される。

0207

一方、受信用メモリ416に、受信データD417が記憶され、その受信データD417を用いた最初の準バリアブルノード演算が行われた後(、その受信データD417に対する最終的な復号結果が出力されるまで)は、その受信データD417に対する復調途中結果D415が、復号途中結果格納用メモリ410に記憶されているので、制御部417は、復号途中結果D415の選択を指示する制御信号D421を、スイッチ411に供給する。これにより、スイッチ411では、復号途中結果格納用メモリ410から供給される復号途中結果D415が選択され、復号途中結果D411として、準チェックノード計算器412に供給される。従って、この場合、準チェックノード計算器412では、復号途中結果D415を、式(8)の復号途中結果vとして、準チェックノード演算が行われる。

0208

準チェックノード計算器412には、スイッチ411から、式(8)の復号途中結果vとしての復号途中結果D411が供給される他、枝用メモリ413から、準チェックノード計算器412による前回の準チェックノード演算の結果得られたチェックノードメッセージujが、メッセージD413として供給される。また、準チェックノード計算器412には、制御部417から制御信号D420が供給される。

0209

準チェックノード計算器412は、スイッチ411からの復号途中結果D411(式(8)のv)と、メッセージD413(前回のチェックノードメッセージuj)を用いて、準チェックノード演算を行い、即ち、式(8)の演算を行い、その後、さらに、式(7)の演算を行い、これにより、式(7)のチェックノードメッセージujを、検査行列Hの枝(値が1になっている要素)ごとに求める。そして、準チェックノード計算器412は、式(8)の準チェックノード演算の結果得られる、各枝のチェックノードメッセージujを、メッセージD412として、枝用メモリ413に供給する。

0210

枝用メモリ413は、準チェックノード計算器412から供給される各枝のメッセージD412を、順次記憶する。枝用メモリ413に記憶された各枝のメッセージD412(uj)は、次の準チェックノード演算と、次の準バリアブルノード演算のために、そこから順次読み出され、メッセージD413として、準チェックノード計算器412と、準バリアブルノード演算器415に供給される。

0211

準バリアブルノード計算器415には、枝用メモリ413から、各枝のメッセージD413(チェックノードメッセージuj)が供給される。また、準バリアブルノード計算器415には、受信用メモリ416からLDPC符号の受信データD417(式(5)のu0i)が供給される。さらに、準バリアブルノード計算器415には、制御部417から制御信号D422が供給される。

0212

準バリアブルノード計算器415は、枝用メモリ413から、各枝のメッセージD413(uj)と、受信用メモリ416からの受信データD417(u0i)とを用いて、式(5)の準バリアブルノード演算を、検査行列Hの列ごとに行い、これにより、復号途中結果vを、検査行列Hの列ごとに求める。そして、準バリアブルノード計算器415は、式(5)の準バリアブルノード演算の結果得られる復号途中結果vを、復号途中結果D415として、復号途中結果格納用メモリ410に供給する。

0213

ここで、上述したように、復号途中結果格納用メモリ410では、準バリアブルノード計算器415から供給される復号途中結果D415が、順次記憶され、さらに、その記憶された復号途中結果D415は、そこから順次読み出され、スイッチ411に供給される。

0214

但し、準バリアブルノード計算器415において、最後の準バリアブルノード演算が行われた場合、即ち、例えば、受信用メモリ416に記憶された受信データD417について、あらかじめ決められた回数だけ、準チェックノード演算と準バリアブルノード演算とが繰り返し行われた場合、復号途中結果格納用メモリ410は、最後に行われた準バリアブルノード演算の結果としての復号途中結果D415を、受信用メモリ416に記憶された受信データD417(LDPC符号)の最終的な復号結果として出力する。

0215

受信用メモリ416は、通信路を通して受信した受信信号D416から計算されたLDPC符号の各ビットの0らしさの値である、符号長分の受信LLR(対数尤度比)を、受信データD417として記憶し、スイッチ411と準バリアブルノード計算器415に供給する。

0216

制御部417は、制御信号D420を準チェックノード計算器412に、制御信号D421をスイッチ411に、制御信号D422を準バリアブルノード計算器415に、それぞれ供給することにより、それぞれを制御する。

0217

以上のように構成される図17の復号装置では、復号途中結果格納用メモリ410、準チェックノード計算器412、枝用メモリ413、準バリアブルノード計算器415の順で、データが一巡することで、1回の復号(繰り返し復号の1回分の処理(チェックノード演算とバリアブルノード演算))が行われる。図17の復号装置では、所定の回数だけ繰り返して復号が行われた後、準バリアブルノード計算器415による準バリアブルノード演算の結果である復号途中結果D415が、最終的な復号結果として出力される。

0218

次に、図17の準チェックノード計算器412と準バリアブルノード計算器415について、さらに詳述する。

0219

まず、図19は、図17の準チェックノード計算器412の構成例を示している。

0220

準チェックノード計算器412には、スイッチ411(図17)から、式(8)の復号途中結果vとしての復号途中結果D411が供給されるとともに、枝用メモリ413(図17)から、準チェックノード計算器412による前回の準チェックノード演算の結果得られたチェックノードメッセージujのうちの、いま式(8)によってバリアブルノードメッセージviを求めようとしている枝からのチェックノードメッセージudvが、メッセージD413として供給される。さらに、準チェックノード計算器412には、制御部417(図17)から制御信号D420が供給される。

0221

ここで、図17の復号装置では、準チェックノード演算と準バリアブルノード演算とが繰り返し行われることにより、等価的に、図13の復号装置と同様に、チェックノード演算とバリアブルノード演算とが繰り返し行われる。

0222

そして、図13の復号装置では、チェックノード演算によって得られるメッセージujと、バリアブルノード演算によって得られるメッセージviとが、いずれも、符号ビットを含めて6ビットの通常量子化値で表されることとしたが、図17の復号装置でも、メッセージujとメッセージviとは、いずれも、符号ビットを含めて6ビットの通常量子化値で表されることとする。また、図17の復号装置において、受信用メモリ416に記憶される受信データD417も、図13の復号長量と同様に、符号ビットを含めて6ビットの通常量子化値で表されることとする。

0223

この場合、枝用メモリ413(図17)から準チェックノード計算器412に供給されるメッセージD413(チェックノードメッセージudv)は、6ビットの通常量子化値で表される。また、スイッチ411(図17)から準チェックノード計算器412に供給される復号途中結果D411(v)は、後述するように、9ビットの通常量子化値で表される。

0224

枝用メモリ413(図17)から準チェックノード計算器412に供給された6ビットの通常量子化値によるメッセージD413(前回の準チェックノード演算の結果得られたチェックノードメッセージujのうちの、いま式(8)によってバリアブルノードメッセージviを求めようとしている枝からのチェックノードメッセージudv)と、スイッチ411(図17)から準チェックノード計算器412に供給された9ビットの通常量子化値による復号途中結果D411(v)とは、いずれも、ブロックB’の演算器431に供給される。

0225

また、制御部417(図17)から準チェックノード計算器412に供給された制御信号D420は、セレクタ435とセレクタ442に供給される。

0226

演算器431は、式(8)の演算、即ち、そこに供給される9ビットの復号途中結果D411(v)から、同じくそこに供給される6ビットの復号途中結果D413(udv)を減算し、これにより、6ビットのバリアブルノードメッセージviを求め、6ビットの通常量子化値によるメッセージD431(vi)として出力する。

0227

なお、演算器431は、前述した図12のバリアブルノード計算器103を構成する演算器156と同様に、式(8)の演算結果が、6ビットの通常量子化値によって表される数値範囲外である場合には、その演算結果をクリッピングし、6ビットの通常量子化値によるメッセージD431(vi)として出力する。

0228

演算器431が出力した6ビットのメッセージD431(vi)は、ブロックA’に供給される。ブロックA’では、演算器431からの6ビットのメッセージD431(バリアブルノードメッセージvi)のうち、最上位ビットの正負を示す符号ビットD432(sign(vi))がEXOR回路440およびFIFOメモリ444に供給され、下位5ビットの絶対値D433(|vi|)がLUT432に供給される。

0229

上述したように、ブロックA’は、図14に示したチェックノード計算器171のブロックAに対応しており、従って、ブロックAと同様の処理を行う。

0230

即ち、ブロックA’において、LUT432、演算器433、レジスタ434、セレクタ435、レジスタ436、演算器437、FIFOメモリ438、LUT439、EXOR回路440、レジスタ441、セレクタ442、レジスタ443、FIFOメモリ444、EXOR回路445は、図14のブロックAのLUT1121、演算器1122、レジスタ1123、セレクタ1124、レジスタ1125、演算器1126、FIFOメモリ1127、LUT1128、EXOR回路129、レジスタ130、セレクタ131、レジスタ132、FIFOメモリ133、EXOR回路134とそれぞれ同様に構成されている。

0231

さらに、ブロックA’においては、図14のブロックAと同様に、図19において太線で示す部分のビット数が、高精度量子化値と通常量子化値とのビット数の差である4ビットだけ多くなっている。

0232

そして、ブロックA’において、LUT432は、5ビットの絶対値D433(|vi|)に対して、式(7)における非線形関数φ(|vi|)の演算結果D434(φ(|vi|))を対応付けて記憶している。さらに、LUT432では、絶対値D433(|vi|)は、通常量子化値で表されているのに対して、非線形関数φ(|vi|)の演算結果D434(φ(|vi|))は、高精度量子化値で表されている。即ち、LUT432は、通常量子化値で表される5ビットの絶対値D433(|vi|)に対して、例えば、高精度量子化値で表される9ビットの、非線形関数φ(|vi|)の演算結果D434(φ(|vi|))を対応付けて記憶している。

0233

LUT432は、通常量子化値で表される5ビットの絶対値(5ビットの通常量子化値による絶対値)D433(|vi|)を入力として、それに対応付けられている、高精度量子化値で表される9ビットの、非線形関数φ(|vi|)の演算結果D434(φ(|vi|))を読み出し、演算器433とFIFOメモリ438に出力する。

0234

従って、LUT432は、式(7)における非線形関数φ(|vi|)を演算する処理、および通常量子化値を高精度量子化値に変換する処理を、等価的に行い、以降は、後述するLUT439において、高精度量子化値を通常量子化値に変換する処理が行われるまで、高精度量子化値を使用して処理が行われる。

0235

演算器433は、9ビットの演算結果D434(φ(|vi|))とレジスタ434に格納されている13ビットの値D435とを加算することにより、演算結果D434を積算し、その結果得られる13ビットの積算値D435をレジスタ434に再格納する。なお、検査行列Hの1行に亘る全ての枝からのメッセージD431(バリアブルノードメッセージvi)の絶対値D433(|vi|)に対する演算結果が積算された場合、レジスタ434はリセットされる。

0236

ここで、演算器433が出力する積算値D435が13ビットであり、LUT432から演算器433に入力されて積算の対象となる演算結果D434(φ(|vi|))が9ビットであるのは、図14において、演算器1122の出力が、演算器1122に入力される、LUT432からの9ビットの演算結果D434(φ(|vi|))よりも4ビットだけ多い13ビットになっているのと同様の理由による。

0237

検査行列Hの1行に亘るメッセージD431(バリアブルノードメッセージvi)が1つずつ読み込まれ、レジスタ434に1行分の演算結果D434が積算された積算値が格納された場合、制御部417(図17)から供給される制御信号D420は、0から1に変化する。例えば、検査行列Hの行の重み(row weight)が「9」である場合、制御信号D420は、8個目の演算結果D434が積算されるまでは、「0」となり、9個目の演算結果D434が積算されると「1」となる。

0238

制御信号D420が「1」の場合、セレクタ435は、レジスタ434に格納されている値、即ち、検査行列Hの1行に亘る全ての枝からのメッセージD431(バリアブルノードメッセージvi)から求められたφ(|vi|)が積算された13ビットの値D435(i=1からi=dcまでのΣφ(|vi|))を選択し、13ビットの値D436として、レジスタ436に出力して格納させる。レジスタ436は、格納している値D436を、13ビットの値D437として、セレクタ435と演算器437に供給する。制御信号D420が「0」の場合、セレクタ435は、レジスタ436から供給された値D437を選択し、レジスタ436に出力して再格納させる。即ち、検査行列Hの1行に亘る全ての枝からのメッセージD431(バリアブルノードメッセージvi)から求められたφ(|vi|)が積算されるまで、レジスタ436は、前回積算されたφ(|vi|)を、セレクタ435と演算器437に供給する。

0239

一方、FIFOメモリ438は、レジスタ436から新たな値D437(i=1からi=dcまでのΣφ(|vi|))が出力されるまでの間、LUT432が出力した9ビットの演算結果D434(φ(|vi|))を遅延し、9ビットのD438として演算器437に供給する。演算器437は、レジスタ436から供給された13ビットの値D437から、FIFOメモリ438から供給された9ビットのD438を減算し、その減算結果を、9ビットの減算値D439としてLUT439に供給する。即ち、演算器437は、検査行列Hの1行に亘る全ての枝からのメッセージD431(バリアブルノードメッセージvi)から求められたφ(|vi|)の積算値から、チェックノードメッセージujを求めたい枝からのメッセージD431(バリアブルノードメッセージvi)から求められたφ(|vi|)を減算して、その減算値(i=1からi=dc−1までのΣφ(|vi|))を減算値D439としてLUT439に供給する。

0240

なお、レジスタ436から供給される13ビットの値D437から、FIFOメモリ438から供給される9ビットのD438を減算した減算結果としての量子化値(高精度量子化値)が、9ビットの減算値D439で表すことができる最大値を越える場合には、演算器437は、減算結果としての高精度量子化値を、9ビットの高精度量子化値で表すことができる最大値にクリッピングし、9ビットの減算値D439を出力する。

0241

LUT439は、減算値D439(i=1からi=dc−1までのΣφ(|vi|))に対して、式(7)における逆関数φ-1(Σφ(|vi|))の演算を行った演算結果D440(φ-1(Σφ(|vi|)))を対応付けて記憶している。さらに、LUT439では、減算値D439(i=1からi=dc−1までのΣφ(|vi|))は、高精度量子化値で表されているのに対して、逆関数φ-1(Σφ(|vi|))の演算結果D440(φ-1(Σφ(|vi|)))は、通常量子化値で表されている。即ち、LUT439は、高精度量子化値で表される9ビットの減算値D439(i=1からi=dc−1までのΣφ(|vi|))に対して、通常量子化値で表される5ビットの、逆関数φ-1(Σφ(|vi|))の演算結果D440(φ-1(Σφ(|vi|)))を対応付けて記憶している。

0242

LUT439は、高精度量子化値で表される9ビットの減算値D439(i=1からi=dc−1までのΣφ(|vi|))を入力として、それに対応付けられている、通常量子化値で表される5ビットの、逆関数φ-1(Σφ(|vi|))の演算結果D440(φ-1(Σφ(|vi|)))を読み出して出力する。

0243

従って、LUT439は、式(7)における逆関数φ-1(Σφ(|vi|))を演算する処理、および高精度量子化値を通常量子化値に変換する処理を、等価的に行い、以降は、上述したLUT432において、通常量子化値を高精度量子化値に変換する処理が行われるまで、通常量子化値を使用して処理が行われる。

0244

以上の処理と並行して、EXOR回路440は、レジスタ441に格納されている1ビットの値D442と符号ビットD432との排他的論理和を演算することにより、符号ビットどうしの乗算を行い、1ビットの乗算結果D441をレジスタ441に再格納する。なお、検査行列の1行に亘る全ての1に対応する復号途中結果D411から求められたバリアブルノードメッセージvi(D431)の符号ビットD432が乗算された場合、レジスタ441はリセットされる。

0245

検査行列の1行に亘る全ての1に対応する復号途中結果D411から求められたバリアブルノードメッセージvi(D431)の符号ビットD432が乗算された乗算結果D441(i=1からdcまでのΠsign(vi))がレジスタ441に格納された場合、制御部417から供給される制御信号D420は、「0」から「1」に変化する。

0246

制御信号D420が「1」の場合、セレクタ442は、レジスタ441に格納されている値、即ち、検査行列の1行に亘る全ての1に対応する復号途中結果D411から求められた符号ビットD432が乗算された値D442(i=1からi=dcまでのΠsign(vi))を選択し、1ビットの値D443としてレジスタ443に出力して格納させる。レジスタ443は、格納している値D443を、1ビットの値D444としてセレクタ442とEXOR回路445に供給する。制御信号D420が「0」の場合、セレクタ442は、レジスタ443から供給された値D444を選択し、レジスタ443に出力して再格納させる。即ち、検査行列の1行に亘る全ての1に対応する復号途中結果D411(復号途中結果v)から求められたバリアブルノードメッセージvi(D431)の符号ビットD432が乗算されるまで、レジスタ443は、前回格納した値を、セレクタ442とEXOR回路445に供給する。

0247

一方、FIFOメモリ444は、レジスタ443から新たな値D444(i=1からi=dcまでのΠsign(vi))がEXOR回路445に供給されるまでの間、符号ビットD432を遅延し、1ビットの値D445としてEXOR回路445に供給する。EXOR回路445は、レジスタ443から供給された値D444と、FIFOメモリ444から供給された値D445との排他的論理和を演算することにより、値D444を、値D445で除算し、1ビットの除算結果を除算値D446として出力する。即ち、EXOR回路445は、検査行列の1行に亘る全ての1に対応する復号途中結果D411から求められたバリアブルノードメッセージvi(D431)の符号ビットD432(sign(vi))の乗算値を、チェックノードメッセージujを求めようとする枝からのバリアブルノードメッセージvi(D431)の符号ビットD432(sign(vi))で除算して、その除算値(i=1からi=dc−1までのΠsign(vi))を除算値D446として出力する。

0248

そして、準チェックノード計算器412では、LUT439から出力された通常量子化値の5ビットの演算結果D440を下位5ビットとするとともに、EXOR回路445から出力された1ビットの除算値D446を最上位ビット(符号ビット)とする合計6ビットの通常量子化値で表されるメッセージD412(チェックノードメッセージuj)が出力される。

0249

以上のように、準チェックノード計算器412では、式(7)と式(8)の演算が行われ、チェックノード演算の結果である、6ビットの通常量子化値によるチェックノードメッセージujが求められる。このチェックノードメッセージujは、準チェックノード計算器412から枝用メモリ413(図17)に供給されて記憶される。

0250

なお、図9の検査行列の行の重みの最大は9であるため、準チェックノード計算器412は、9個の復号途中結果D411から求められる9個の演算結果D434(φ(|vi|))を遅延させるFIFOメモリ438と、9個の符号ビットD432を遅延させるFIFOメモリ444を有している。行の重みが9未満の行のチェックノードメッセージujを計算するときには、FIFOメモリ438とFIFOメモリ444における遅延量が、その行の重みの値に減らされる。

0251

次に、図20は、図17の準バリアブルノード計算器415の構成例を示している。

0252

準バリアブルノード計算器415は、ブロックC’で構成される。ブロックC’は、上述したように、図18に示したバリアブルノード計算器103のブロックCに対応しており、従って、ブロックCと同様の処理を行う。

0253

即ち、ブロックC’において、演算器471、レジスタ472、セレクタ473、レジスタ474、演算器475は、図18のブロックCの演算器151、レジスタ152、セレクタ153、レジスタ154、演算器1561とそれぞれ同様に構成されている。

0254

準バリアブルノード計算器415には、枝用メモリ413(図17)から、チェックノード演算の結果であるメッセージD413(チェックノードメッセージuj)が供給され、そのメッセージD413は、演算器471に供給される。また、準バリアブルノード計算器415には、受信用メモリ416(図17)から受信データD417(u0i)が供給され、その受信データD417は、演算器475に供給される。さらに、準バリアブルノード計算器415には、制御部417(図17)から制御信号D422が供給され、その制御信号D422は、セレクタ473に供給される。

0255

ここで、準バリアブルノード計算器415に対して、枝用メモリ413(図17)から供給されるメッセージD413(チェックノードメッセージuj)と、受信用メモリ416(図17)から供給される受信データD417(u0i)とは、上述したように、いずれも、6ビットの通常量子化値で表されている。

0256

演算器471は、メッセージD413とレジスタ472に格納されている9ビットの値D471とを加算することにより、メッセージD413ujを積算し、その結果得られる9ビットの積算値を、レジスタ472に再格納する。なお、検査行列の1列に亘る全ての1に対応するメッセージD413(チェックノードメッセージuj)が積算された場合、レジスタ472はリセットされる。

0257

ここで、演算器471が出力する積算値が9ビットであり、演算器433に入力されて積算されるメッセージD413(uj)が6ビットであるのは、図12において、演算器151の出力が、演算器151に入力される6ビットのメッセージD103よりも3ビットだけ多い9ビットになっているのと同様の理由による。

0258

レジスタ472に1列分のメッセージD413が積算された値が格納された場合、制御部417(図17)から供給される制御信号D422は、「0」から「1」に変化する。例えば、列の重みが「5」である場合、制御信号D422は、4番目のメッセージD413が積算されるまでは「0」となり、5番目のメッセージD413が積算されると「1」となる。

0259

制御信号D422が「1」の場合、セレクタ473は、レジスタ472に格納されている値、即ち、検査行列Hの1列に亘る全ての枝からのメッセージD413(チェックノードメッセージuj)が積算された9ビットの積算値D471(j=1からdVまでのΣuj)を選択し、レジスタ474に出力して格納させる。レジスタ474は、格納している積算値D471を、9ビットの値D472として、セレクタ471と演算器475に供給する。制御信号D422が「0」の場合、セレクタ473は、レジスタ474から供給された9ビットの値D472を選択し、レジスタ474に出力し再格納させる。即ち、検査行列の1列に亘る全ての枝からのメッセージD413(チェックノードメッセージuj)が積算されるまで、レジスタ474は、前回の積算値D472を、セレクタ473と演算器475に供給する。

0260

演算器475は、9ビットの積算値D472と、受信用メモリ416(図17)から供給された6ビットの受信データD417とを加算して、その結果得られる9ビットの値を復号途中結果D415(復号途中結果v)として出力する。

0261

以上のように、準バリアブルノード計算器415では、通常量子化値を高精度量子化値に変換せずに、即ち、通常量子化値を使用したまま、式(5)の演算が行われ、9ビットの復号途中結果vが求められる。この復号途中結果vは、準バリアブルノード計算器415から復号途中結果格納用メモリ410(図17)に供給されて記憶される。

0262

なお、復号途中結果格納用メモリ410には、9ビットの通常量子化値で表された復号途中結果vが記憶され、この9ビットの復号途中結果vが、上述したように、スイッチ411(図17)を介して、準チェックノード計算器412に供給される。

0263

図17の復号装置でも、図13の復号装置と同様に、準チェックノード計算器412のLUT432において、通常量子化値を高精度量子化値に変換するとともに、LUT439において、高精度量子化値を通常量子化値に変換することにより、チェックノード演算およびバリアブルノード演算として行う処理のうちの、非線形関数φ(x)の演算後からその逆関数φ-1(x)の演算までの処理では、高精度量子化値を使用し、他の処理では、通常量子化値を使用するので、LDPC符号の復号を、復号装置の大規模化を抑えつつ精度良く行うことができる。

0264

さらに、図17の復号装置では、準チェックノード計算器412において、チェックノード演算と、バリアブルノード演算の一部とを行い、準バリアブルノード計算器415において、バリアブルノード演算の他の一部を行うので、図13の復号装置よりも、装置の規模を小さくすることができる。

0265

即ち、図17の復号装置において、枝用メモリ413は、図13の枝用メモリ102に対応し、復号途中結果格納用メモリ410は、図13の枝用メモリ100に対応し、受信用メモリ416は、図13の受信用メモリ104に対応する。

0266

そして、図17の枝用メモリ413と、対応する図13の枝用メモリ102とは、いずれも、6ビットのチェックノードメッセージujを、全枝数分だけ記憶する必要があるので、全枝数の6ビット倍の記憶容量を必要とする。また、図17の受信用メモリ416と、対応する図13の受信用メモリ104も、いずれも、6ビットの受信データu0iを、符号長分だけ記憶する必要があるので、符号長の6ビット倍の記憶容量を必要とする。

0267

さらに、図13の枝用メモリ100は、図13の枝用メモリ102と同様に、6ビットのバリアブルノードメッセージviを、全枝数分だけ記憶する必要があるので、全枝数の6ビット倍の記憶容量を必要とする。

0268

これに対して、図13の枝用メモリ100に対応する図17の復号途中結果格納用メモリ410は、準バリアブルノード計算器415が出力する復号途中結果v(D415)を、符号長分だけ記憶する必要がある。復号途中結果vは、図20で説明したように、9ビット(の通常量子化値)であるから、復号途中結果格納用メモリ410は、符号長の9ビット倍の記憶容量を必要とする。

0269

従って、復号途中結果格納用メモリ410と、対応する図13の枝用メモリ100とについては、全枝数が、符号長の3/2(=9ビット/6ビット)倍であれば、同一の記憶容量が必要となる。

0270

しかしながら、LDPC符号の検査行列Hは疎らではあるが、全枝数(検査行列Hにおいて1になっている要素の総数)は、一般に、符号長(検査行列Hの列数)の3/2倍よりも大であり、例えば、図9の検査行列Hでも、全枝数(323個)は、符号長(108)の約3(≒323/108)倍になっている。

0271

従って、復号途中結果格納用メモリ410の記憶容量は、対応する図13の枝用メモリ100よりも少ない記憶容量とすることができる。

0272

その結果、図17の復号装置は、復号途中結果格納用メモリ410の記憶容量を、対応する図13の枝用メモリ100の記憶容量よりも少なくすることができる分だけ、図13の復号装置よりも、装置の規模を小さくすることができる。

0273

また、図17の復号装置は、上述したように、(準バリアブルノード計算器415とは別に)式(5)を演算するブロックを設ける必要がなく、図18図12)のFIFOメモリ155を設ける必要もないので、図13の復号装置よりも、さらに小型に構成することができる。

0274

ここで、式(7)で表されるチェックノード演算と、式(1)で表されるバリアブルノード演算とを繰り返し行うことによってLDPC符号を復号する第1の復号方法と、式(8)および式(7)で表される準チェックノード演算と、式(5)で表される準バリアブルノード演算を繰り返し行うことによってLDPC符号を復号する第2の復号方法とは、等価である。

0275

そして、第1および第2の復号方法のいずれにおいても、式(7)の演算が行われるが、この式(7)は、式(9)、式(10)、および式(11)の3つの式に分解することができる。

0276

・・・(9)

0277

・・・(10)

0278

・・・(11)

0279

式(9)乃至式(11)を、その順番で演算することにより、式(7)の演算、つまりチェックノード演算を行うことができる。

0280

いま、式(9)乃至式(11)を、その順番で演算する場合に、その演算の過程を、式(9)で演算される非線形関数φ(|vi|)から、式(11)で演算される逆関数φ(W)までの「内側」と「外側」とに分けると、式(9)乃至式(11)の演算において、変数(メッセージ)viとujは、「外側」のみで使用され、変数ViとWとは、「内側」でのみ使用される。

0281

従って、「外側」のみで使用される変数viおよびujを表す量子化値と、「内側」でのみ使用される変数ViおよびWを表す量子化値とには、別個の数値を割り当てることができる。

0282

そこで、図13および図17の復号装置では、変数viおよびujを表す量子化値として、ある量子化幅Qで、あるダイナミックレンジDyの数値を表す通常量子化値を採用するとともに、変数ViおよびWを表す量子化値として、量子化幅Qよりも小さい量子化幅で、ダイナミックレンジDyよりも広いダイナミックレンジの数値を表す高精度量子化値を採用し、即ち、チェックノード演算およびバリアブルノード演算として行う処理のうちの、非線形関数φ(x)の演算後からその逆関数φ-1(x)の演算までの処理(「内側」)では、高精度量子化値を使用するとともに、他の処理(「外側」)では、通常量子化値を使用する。

0283

これにより、復号装置の大規模化を抑えつつ、LDPC符号の復号の高精度化を実現することができる。換言すれば、ある精度(性能)のLDPC符号の復号を実現するにあたって、復号装置の規模を大幅に削減することができる。

0284

即ち、図21は、各種の復号装置についてのBER/FERシミュレーション結果を示している。

0285

なお、図21において、横軸は、1ビットあたりの信号電力雑音電力比Eb/N0を表し、縦軸は、BER(Bit Error Rate)またはFER(Frame Error Rate)を表している。また、図21では、BERは実線で、FERは点線で、それぞれ示してある。

0286

図21において×印は、図10の復号装置において、メッセージuj,vi、および受信データu0iを6ビットの通常量子化値で表して、LDPC符号の復号を行った場合のBERとFERを表している。

0287

また、図21において、△印は、図10の復号装置において、メッセージuj,vi、および受信データu0iを10ビットの高精度量子化値で表して、LDPC符号の復号を行った場合のBERとFERを表している。

0288

×印で示すBERおよびFERと、△印で示すBERおよびFERとを比較して分かるように、メッセージuj,vi、および受信データu0iを10ビットの高精度量子化値で表した場合には、メッセージuj,vi、および受信データu0iを6ビットの通常量子化値で表した場合よりも、BERおよびFERが飛躍的に向上する。逆に言えば、メッセージuj,vi、および受信データu0iを6ビットの通常量子化値で表した場合には、メッセージuj,vi、および受信データu0iを10ビットの高精度量子化値で表した場合よりも、BERおよびFERが大きく劣化する。

0289

しかしながら、メッセージuj,vi、および受信データu0iを6ビットの通常量子化値で表した場合には、それらを10ビットの高精度量子化値で表した場合よりも、装置規模を、メッセージuj,vi、および受信データu0iを記憶させるメモリについてだけで40%削減することができる。メッセージuj,vi、および受信データu0iを記憶させるメモリの記憶容量は、メッセージuj,vi、および受信データu0iの量子化ビット数に比例するからである。

0290

一方、図21において、○印は、図13の復号装置において、メッセージuj,vi、および受信データu0iを6ビットの通常量子化値で表し、LUT1121(図14)において、6ビットの通常量子化値を10ビットの高精度量子化値に変換するとともに、LUT1128(図14)において、10ビットの高精度量子化値を6ビットの通常量子化値に変換して、LDPC符号の復号を行った場合のBERとFERを表している。

0291

図13の復号装置によれば、メッセージuj,vi、および受信データu0iを10ビットの高精度量子化値で表した場合とほぼ同等の性能(精度)が得られることが分かる。

0292

さらに、図13の復号装置では、メッセージuj,vi、および受信データu0iが6ビットの通常量子化値で表されるので、装置規模を、メッセージuj,vi、および受信データu0iを6ビットの通常量子化値で表す図10の復号装置とほぼ同等とすることができる。

0293

即ち、図13の復号装置によれば、メッセージuj,vi、および受信データu0iを6ビットの通常量子化値で表す図10の復号装置と比較すれば、その復号装置と同等の規模で、より高精度の復号を行うことができる。

0294

また、図13の復号装置によれば、メッセージuj,vi、および受信データu0iを10ビットの高精度量子化値で表す図10の復号装置と比較すれば、その復号装置と同等の性能を、小さな装置規模で、即ち、上述したように、受信データu0i等を記憶するメモリを40%削減して実現することができる。

0295

ここで、LDPC符号の符号長が長くなると、復号装置全体の規模については、受信データu0i等を記憶するメモリの規模が支配的になり、場合によっては、復号装置の規模の80%以上を、受信データu0i等を記憶するメモリが占めることがある。従って、受信データu0i等を記憶するメモリの削減の効果は、極めて大きい。

0296

なお、本実施の形態では、各ノードの演算を一つずつ順次行うフルシリアデコード(full serial decoding)のアーキテクチャを有する復号装置を採用したが、復号装置のアーキテクチャは、特に限定されるものではない。即ち、本発明は、フルシリアルデコードのアーキテクチャを有する復号装置の他、例えば、全ノードの演算を同時に行うフルパラレルデコード(full parallel decoding)のアーキテクチャを有する復号装置や、一つでも全てでもない、ある数のノードの演算を同時に行う一部パラレルデコード(partly parallel decoding)のアーキテクチャを有する復号装置にも適用可能である。

0297

さらに、検査行列Hは、図9に示したものに限定されるものではない。

0298

また、通常量子化値や高精度量子化値で表すデータ(例えば、メッセージuj,viや、受信データu0i、復号途中結果vなど)のビット数(量子化ビット数)も、上述した値に限定されるものではない。

0299

さらに、図13の枝用メモリ100および102、受信用メモリ104や、図17の復号途中結果格納用メモリ410、枝用メモリ413、受信用メモリ416としては、例えば、RAM(Read Only Memory)を使用することができる。ここで、これらの枝用メモリ100等として使用するRAMの1ワードあたりのビット数(ビット幅)や、RAMが記憶することができるワード数は、特に限定されるものではない。また、RAMのビット幅やワード数によっては、複数のRAMに対して、同様の制御信号(例えば、チップセレクト信号アドレス信号)を与えることにより、その複数のRAMを論理的に1つのRAMとみなして、枝用メモリ100等として使用することができる。即ち、例えば、物理的に1つのRAMのビット幅が、受信データu0i等の量子化ビット数に足りない場合には、複数のRAMを論理的に1つのRAMとみなして、受信データu0i等を記憶させることができる。

0300

また、本実施の形態では、LUT1121(図14)やLUT432(図19)、またはLUT1128(図14)やLUT439(図19)といったLUTによって、通常量子化値を高精度量子化値に変換し、または高精度量子化値を通常量子化値に変換するようにしたが、通常量子化値と高精度量子化値とのうちの一方から他方への変換は、LUTとは別に変換回路を設けて、その変換回路によって行うことが可能である。この場合、例えば、図14において、通常量子化値を高精度量子化値に変換する変換回路は、LUT1121の入力の直前に設けられ、高精度量子化値を通常量子化値に変換する変換回路は、LUT1128の出力の直後に設けられる。

0301

但し、通常量子化値と高精度量子化値とのうちの一方から他方への変換は、LUTによって行うことにより、LUTとは別に、変換回路を設ける必要がないため、装置規模を小型化することができる。

0302

さらに、本実施の形態では、非線形関数φ(x)、またはその逆関数φ-1(x)の演算を、LUT1121(図14)やLUT432(図19)、またはLUT1128(図14)やLUT439(図19)といったLUTによって行うようにしたが、非線形関数φ(x)やその逆関数φ-1(x)の演算は、例えば、CPU(Central Processing Unit)や論理回路によって行うことが可能である。

0303

なお、上述したLDPC符号を復号する復号装置は、例えば、(ディジタル衛星放送を受信するチューナなどに適用することができる。

図面の簡単な説明

0304

LDPC符号の検査行列Hを説明する図である。
パリティ部が下三角行列になっている検査行列Hを示す図である。
LDPC符号の復号手順を説明するフローチャートである。
メッセージの流れを説明する図である。
LDPC符号の検査行列Hの例を示す図である。
検査行列Hのタナーグラフを示す図である。
バリアブルノードを示す図である。
チェックノードを示す図である。
LDPC符号の検査行列Hの例を示す図である。
ノード演算を一つずつ行うLDPC符号の復号装置の構成例を示すブロック図である。
メッセージを一つずつ計算するチェックノード計算器101の構成例を示すブロック図である。
メッセージを一つずつ計算するバリアブルノード計算器103の構成例を示すブロック図である。
本発明の一実施の形態の復号装置の第1構成例を示すブロック図である。
チェックノード計算器171の構成例を示すブロック図である。
チェックノード計算器171の処理を説明するためのフローチャートである。
非線形関数φ(x)と、その逆関数φ-1(y)とを示す図である。
本発明の一実施の形態の復号装置の第2構成例を示すブロック図である。
バリアブルノード計算器103の構成例を示すブロック図である。
準チェックノード計算器412の構成例を示すブロック図である。
準バリアブルノード計算器415の構成例を示すブロック図である。
BER/FERを示す図である。

符号の説明

0305

100,102枝用メモリ, 103バリアブルノード計算器, 104受信用メモリ, 105 制御部, 129EXOR回路, 130レジスタ, 131セレクタ, 132 レジスタ, 133FIFOメモリ, 134 EXOR回路, 171チェックノード計算器, 410復号途中結果格納用メモリ, 411 スイッチ, 412 準チェックノード計算器, 413 枝用メモリ, 415 準バリアブルノード計算器, 416 受信用メモリ, 417 制御部, 431演算器, 432 LUT, 433 演算器, 434 レジスタ, 435 セレクタ, 436 レジスタ, 437 演算器, 438 FIFOメモリ, 439 LUT, 440 EXOR回路, 441 レジスタ, 442 セレクタ, 443 レジスタ, 444 FIFOメモリ, 445 EXOR回路, 471 演算器, 472 レジスタ, 473 セレクタ, 474 レジスタ, 475 演算器, 1211 LUT, 1122 演算器, 1123 レジスタ, 1124 セレクタ, 1125 レジスタ, 1126 演算器, 1127 FIFOメモリ, 1128 LUT

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ