(57)【特許請求の範囲】
【請求項１】
LDPC(Low Density Parity Check)符号を復号する復号装置において、
前記LDPC符号が、
P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を第１の構成行列として、複数の前記第１の構成行列の組合せによる第１の構造の検査行列で元々表現されるか、または、元々の検査行列の行と列のうちの少なくとも1以上の置換により前記第１の構造の行列で表現される場合、
FをPの１以外の約数としたとき、
前記LDPC符号を受信した結果得られる受信値を復号するための演算として、F個のチェックノードの演算またはF個のバリアブルノードの演算を並列的に行い、各演算の結果得られるF個のメッセージを出力するメッセージ計算手段と、
前記メッセージ計算手段から出力されるF個の前記メッセージに対して、F×Fのサイクリックシフトを行って出力するシフト手段と、
前記シフト手段から出力されるF個の前記メッセージの書き込み、書き込まれたF個の前記メッセージの読み出し、または、F個の前記受信値の読み出し若しくは書き込みができる記憶手段と、
F×Fの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはF×Fの０行列を第２の構成行列として、複数の前記第２の構成行列の組合せによる第２の構造の行列を定義した場合に、前記第１の構造の検査行列で表現される前記受信値に対して少なくとも列置換処理を施すことで、前記メッセージ計算手段への前記受信値の提供の制御として、前記第２の構成行列に対応するF個の前記受信値を単位とする提供の制御を行う制御手段と
を備える復号装置。
【請求項２】
前記列置換処理として、
P＝F×Jとして、前記第１の構造の行列を構成する前記複数の第１の構成行列のP個の列に対して列番号0乃至P-1を付したとして、
前記第１の構成行列を処理単位として、
処理対象の前記第１の構成行列に対して列置換を施すことで、処理対象の前記第１の構成行列を、前記列番号をJで除算した余りが同一になる列同士で構成される複数の前記第２の構成行列によって区分する
処理を含んでいる
請求項１に記載の復号装置。
【請求項３】
前記LDPC符号を受信することにより得られる受信値をバッファリングするバッファ手段
をさらに備え、
前記制御手段は、
前記バッファ手段において、前記第１の構造の行列の形態で受信される前記受信値を並び替えて、前記第２の構造の行列の形態でバッファリングさせる制御を行い、
前記第２の構造の行列の形態でバッファリングされた前記受信値を、前記第２の構成行列に対応するF個の前記受信値を単位として、前記記憶手段を介して前記メッセージ計算手段に提供する制御を行う
請求項１に記載の復号装置。
【請求項４】
前記制御手段は、
前記第１の構造の行列の形態で受信される前記受信値の中から、前記第２の構造の行列に変化した場合に前記第２の構成行列に対応するF個の前記受信値を選択して、選択したF個の前記受信値を、前記記憶手段を介して前記メッセージ計算手段に提供する制御を行う
請求項１に記載の復号装置。
【請求項５】
LDPC(Low Density Parity Check)符号を復号する復号装置の復号方法において、
前記LDPC符号が、
P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を第１の構成行列として、複数の前記第１の構成行列の組合せによる第１の構造の検査行列で元々表現されるか、または、元々の検査行列の行と列のうちの少なくとも1以上の置換により前記第１の構造の行列で表現される場合に、
FをPの１以外の約数としたとき、
前記LDPC符号を受信した結果得られる受信値を復号するための演算として、F個のチェックノードの演算またはF個のバリアブルノードの演算を並列的に行い、各演算の結果得られるF個のメッセージを出力するメッセージ計算手段と、
前記メッセージ計算手段から出力されるF個の前記メッセージに対して、F×Fのサイクリックシフトを行って出力するシフト手段と、
前記シフト手段から出力されるF個の前記メッセージの書き込み、書き込まれたF個の前記メッセージの読み出し、または、F個の前記受信値の読み出し若しくは書き込みができる記憶手段とを備える前記復号装置が実行するステップとして、
F×Fの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはF×Fの０行列を第２の構成行列として、複数の前記第２の構成行列の組合せによる第２の構造の行列を定義した場合に、前記第１の構造の検査行列で表現される前記受信値に対して少なくとも列置換処理を施すことで、前記メッセージ計算手段への前記受信値の提供の制御として、前記第２の構成行列に対応するF個の前記受信値を単位とする提供の制御を行う
ステップを含む復号方法。
【請求項６】
LDPC(Low Density Parity Check)符号を復号する復号装置を制御するコンピュータであ
って、
前記LDPC符号が、
P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を第１の構成行列として、複数の前記第１の構成行列の組合せによる第１の構造の検査行列で元々表現されるか、または、元々の検査行列の行と列のうちの少なくとも1以上の置換により前記第１の構造の行列で表現される場合に、
FをPの１以外の約数としたとき、
前記LDPC符号を受信した結果得られる受信値を復号するための演算として、F個のチェックノードの演算またはF個のバリアブルノードの演算を並列的に行い、各演算の結果得られるF個のメッセージを出力するメッセージ計算手段と、
前記メッセージ計算手段から出力されるF個の前記メッセージに対して、F×Fのサイクリックシフトを行って出力するシフト手段と、
前記シフト手段から出力されるF個の前記メッセージの書き込み、書き込まれたF個の前記メッセージの読み出し、または、F個の前記受信値の読み出し若しくは書き込みができる記憶手段とを備える前記復号装置を制御する前記コンピュータに、
F×Fの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはF×Fの０行列を第２の構成行列として、複数の前記第２の構成行列の組合せによる第２の構造の行列を定義した場合に、前記第１の構造の検査行列で表現される前記受信値に対して少なくとも列置換処理を施すことで、前記メッセージ計算手段への前記受信値の提供の制御として、前記第２の構成行列に対応するF個の前記受信値を単位とする提供の制御を行う
ステップを実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、復号装置および方法並びにプログラムに関し、特に、構造の異なる複数のLDPC符号の復号ができ、かつ、回路規模縮小も図ることができる復号装置および方法並びにプログラムに関する。
【背景技術】
【０００２】
通信システムにおいては、コーディングを使用して雑音のある通信チャネルに渡る信頼性ある通信が行われている。例えば、衛星ネットワークのようなワイヤレス（または無線）システムでは、地理的および環境的要因からの雑音源が多い。これらの通信チャネルは固定容量を表し、ある信号対雑音比（ＳＮＲ）におけるシンボル当たりのビットに関して表すことができ、シャノン限界として知られる理論的上限を規定している。結果として、コーディング設計はこのシャノン限界に近づくレートを達成することを目的としている。この目的は、帯域幅制約衛星システムに対して特に密接な関係がある。
【０００３】
近年では、シャノン限界に近い性能を示す符号化方法として、例えば、並列連接畳み込み符号(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符号について具体的に説明する。なお、LDPC符号は、線形符号であり、必ずしも２元である必要はないが、ここでは、２元であるものとして説明する。
【０００７】
LDPC符号は、そのLDPC符号を定義する検査行列(parity check matrix)が疎なものであることを最大の特徴とするものである。ここで、疎な行列とは、行列のコンポーネントの"1"の個数が非常に少なく構成されるものであり、疎な検査行列をHで表すものとすると、そのような検査行列Hとしては、例えば、図１に示すように、各列のハミング重み（"1"の数）(weight)が"3"であり、且つ、各行のハミング重みが"6"であるもの等がある。
【０００８】
このように、各行及び各列のハミング重みが一定である検査行列Hによって定義されるLDPC符号は、レギュラーLDPC符号と称される。一方、各行及び各列のハミング重みが一定でない検査行列Hによって定義されるLDPC符号は、イレギュラーLDPC符号と称される。
【０００９】
このようなLDPC符号による符号化は、検査行列Hに基づいて生成行列Gを生成し、この生成行列Gを２元の情報メッセージに対して乗算することによって符号語を生成することで実現される。具体的には、LDPC符号による符号化を行う符号化装置は、まず、検査行列Hの転置行列HTとの間に、式GHT=0が成立する生成行列Gを算出する。ここで、生成行列Gが、k×n行列である場合には、符号化装置は、生成行列Gに対してkビットからなる情報メッセージ（ベクトルu）を乗算し、nビットからなる符号語ｃ（＝uＧ）を生成する。この符号化装置によって生成された符号語は、値が"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が、図２に示すように、情報部と、下三角行列のパリティ部とで構成され、パリティ部の下三角の部分の要素が、すべて1であるとすると、符号語cのパリティビットの１番目のビットは、情報メッセージuのうちの、検査行列Hの情報部の第１行において1になっている要素に対応するビットのEXOR（排他的論理和）を演算した値となる。
【００１２】
また、符号語cのパリティビットの２番目のビットは、情報メッセージuのうちの、検査行列Hの情報部の第２行において1になっている要素に対応するビットと、パリティビットの１番目のビットのEXORを演算した値となる。
【００１３】
さらに、符号語cのパリティビットの３番目のビットは、情報メッセージuのうちの、検査行列Hの情報部の第３行において1になっている要素に対応するビットと、パリティビットの１番目および２番目のビットのEXORを演算した値となる。
【００１４】
以下、同様にして、符号語cのパリティビットのi番目のビットは、情報メッセージuのうちの、検査行列Hの情報部の第i行において1になっている要素に対応するビットと、パリティビットの１乃至i-1番目のビットのEXORを演算した値となる。
【００１５】
以上のようにして、n-kビットのパリティビットを求め、kビットの情報メッセージuに続けて配置することにより、nビットの符号語cを得ることができる。
【００１６】
一方、LDPC符号の復号は、Gallagerが確率復号(Probabilistic Decoding)と称して提案したアルゴリズムであって、バリアブルノード(バリアブルノード（メッセージノード(message node)とも呼ばれる。）)と、チェックノード(チェックノード)とからなる、いわゆるタナーグラフ(Tanner graph)上での確率伝播(belief propagation)によるメッセージ・パッシング・アルゴリズムによって行うことが可能である。ここで、以下、適宜、バリアブルノードとチェックノードを、単に、ノードともいう。
【００１７】
しかしながら、確率復号においては、各ノード間で受け渡されるメッセージが実数値であることから、解析的に解くためには、連続した値をとるメッセージの確率分布そのもを追跡する必要があり、非常に困難を伴う解析を必要とすることになる。そこで、Gallagerは、LDPC符号の復号アルゴリズムとして、アルゴリズムＡ又はアルゴリズムＢを提案している。
【００１８】
LDPC符号の復号は、例えば、図３に示すような手順に従って行われる。なお、ここでは、符号長の長さのLDPC符号の受信データのi番目をU0(u0i)とし、チェックノードから出力されるj番目のメッセージ（チェックノードに接続しているj番目の枝から出力されるメッセージ）をujとし、バリアブルノードから出力されるi番目のメッセージ（バリアブルノードに接続しているi番目の枝から出力されるメッセージ）をviとする。また、ここでは、メッセージとは、値の"0"らしさを表す、いわゆる対数尤度比(log likelihood ratio)等を表現する実数値である。
【００１９】
まず、LDPC符号の復号においては、図３に示すように、ステップＳ１１において、受信データU0(u0i)が受信され、メッセージujが"0"に初期化されるとともに、繰り返し処理のカウンタとしての整数をとる変数kが"0"に初期化され、処理は、ステップＳ１２に進む。ステップＳ１２において、受信データU0(u0i)を用いて、式（１）に示すバリアブルノードの演算を行うことによってメッセージviが求められ、さらに、このメッセージviを用いて、式（２）に示すチェックノードの演算を行うことによってメッセージujが求められる。
【００２０】
【数１】
0004487213.tif 000002
・・・（１）
【００２１】
【数２】
0004487213.tif 000003
・・・（２）
【００２２】
ここで、式（１）と式（２）におけるdvとdcは、それぞれ、検査行列Hの縦方向（列）と横方向（行）の"1"の個数、つまり、列の重み（ハミング重み）と行の重みを示す任意に選択可能とされるパラメータであり、例えば、(3,6)符号の場合には、dv=3，dc=6となる。
【００２３】
なお、式（１）又は（２）の演算においては、それぞれ、メッセージを出力しようとする枝(edge)から入力されたメッセージを、和又は積演算の対象としては用いないことから、和又は積演算の範囲が、１ないしdv-1又は１ないしdc-1となっている。また、式（２）に示す演算は、２入力v1，v2に対して１が得られる式（３）に示す関数R(v1,v2)のテーブルを予め作成しておき、これを式（４）に示すように連続的（再帰的）に用いることによって行うことができる。
【００２４】
【数３】
0004487213.tif 000004
・・・（３）
【００２５】
【数４】
0004487213.tif 000005
・・・（４）
【００２６】
ステップＳ１２では、さらに、変数kが"1"だけインクリメントされ、処理は、ステップＳ１３に進む。ステップＳ１３では、変数kが所定の繰り返し復号回数N以上であるか否かが判定される。ステップＳ１３において、変数kがN以上ではないと判定された場合、処理は、ステップＳ１２に戻り、以下、同様の処理が繰り返される。
【００２７】
また、ステップＳ１３において、変数kがN以上であると判定された場合、処理は、ステップＳ１４に進み、式（５）に示す演算を行うことによって最終的に出力する復号結果としてのメッセージvが求められて出力され、LDPC符号の復号処理が終了する。
【００２８】
【数５】
0004487213.tif 000006
・・・（５）
【００２９】
ここで、式（５）の演算は、式（１）の演算とは異なり、バリアブルノードに接続している全ての枝からのメッセージujを用いて行われる。
【００３０】
このようなLDPC符号の復号では、例えば(3,6)符号の場合には、図４に示すように、各ノード間でメッセージの授受が行われる。なお、図４において"="（イコール）で示すノードは、バリアブルノードを表し、式（１）に示したバリアブルノードの演算が行われる。また、図４において"+"（プラス）で示すノードは、チェックノードを表し、式（２）に示したチェックノードの演算が行われる。特に、アルゴリズムＡにおいては、メッセージを２元化し、"+"で示すチェックノードにて、dc-1個の入力メッセージ（チェックノードに入力されるメッセージvi）の排他的論理和演算を行い、"="で示すバリアブルノードにて、受信データRに対して、dv-1個の入力メッセージ（バリアブルノードに入力されるメッセージuj）が全て異なるビット値であった場合には、符号を反転して出力する。
【００３１】
また、近年、LDPC符号の復号の実装法に関する研究も行われている。実装方法について述べる前に、まず、LDPC符号の復号を摸式化して説明する。
【００３２】
図５は、(3,6)符号のLDPC符号（符号化率1/2、符号長12）の検査行列(parity check matrix)Hの例である。LDPC符号の検査行列Hは、図６のように、タナーグラフを用いて書き表すことができる。ここで、図６において、"+"で表されるのが、チェックノードであり、"="で表されるのが、バリアブルノードである。チェックノードとバリアブルノードは、それぞれ、検査行列の行と列に対応する。チェックノードとバリアブルノードとの間の結線は、枝(edge)であり、検査行列Hの"1"に相当する。すなわち、検査行列の第ｊ行第ｉ列のコンポーネントが１である場合には、図６において、上からｉ番目のバリアブルノード（"="のノード）と、上からｊ番目のチェックノード（"+"のノード）とが、枝により接続される。枝は、バリアブルノードに対応するLDPC符号（の受信データ）のビットが、チェックノードに対応する拘束条件を持つことを表す。なお、図６は、図５の検査行列Hのタナーグラフとなっている。
【００３３】
LDPC符号の復号方法であるサムプロダクトアルゴリズム(Sum Product Algorithm)は、バリアブルノードの演算とチェックノードの演算とを繰り返し行う。
【００３４】
バリアブルノードでは、図７のように、式（１）のバリアブルノードの演算を行う。すなわち、図７において、バリアブルノードに接続している枝のうちのi番目の枝に対応するメッセージviは、バリアブルノードに接続している残りの枝からのメッセージu1及びu2と、受信データu0iとを用いて計算される。他の枝に対応するメッセージも同様に計算される。
【００３５】
チェックノードの演算について説明する前に、式（２）を、式a×b=exp{ln(|a|)+ln(|b|)}×sign(a)×sign(b)の関係を用いて、式（６）のように書き直す。但し、sign(x)は、x≧0のとき1（論理０）であり、x＜0のとき-1（論理１）である。
【００３６】
【数６】
0004487213.tif 000007
・・・（６）
【００３７】
さらに、x≧0において、非線形関数φ(x)=-ln(tanh(x/2))を定義すると、その逆関数φ-1(x)は、式φ-1(x)=2tanh-1(e-x)で表されるから、式（６）は、式（７）のように書くことができる。
【００３８】
【数７】
0004487213.tif 000008
・・・（７）
【００３９】
チェックノードでは、図８のように、式（７）のチェックノードの演算を行う。すなわち、図８において、チェックノードに接続している枝のうちのj番目の枝に対応するメッセージujは、チェックノードに繋がっている残りの枝からのメッセージv1,v2,v3,v4,v5を用いて計算される。他の枝に対応するメッセージも同様に計算される。
【００４０】
なお、関数φ(x)は、φ(x)=ln((ex+1)/(ex-1))とも表すことができ、x＞0において、φ(x)=φ-1(x)、すなわち、非線形関数φ(x)の演算結果と、その逆関数φ-1(x)の演算結果とは同一である。関数φ(x)及びφ-1(x)をハードウェアに実装する際には、LUT(Look Up Table)を用いて実装される場合があるが、両者は同一のLUTとなる。
【００４１】
また、式（１）のバリアブルノードの演算は、式（５）と、次の式（８）とに分けることができる。
【００４２】
【数８】
0004487213.tif 000009
・・・（８）
【００４３】
したがって、式（５）及び式（８）と、式（７）の演算を繰り返し行うことにより、式（１）のバリアブルノードの演算と、式（７）のチェックノードの演算を繰り返し行うことができる。この場合、式（５）及び式（８）のバリアブルノードの演算のうちの、式（５）の演算の結果を、そのまま、最終的な復号結果とすることができる。
【００４４】
サムプロダクトアルゴリズムをハードウェアに実装して、復号装置とする場合、式（１）（、又は式（５）及び式（８））で表されるバリアブルノード演算（バリアブルノードの演算）及び式（７）で表されるチェックノード演算（チェックノードの演算）を、適度な回路規模と動作周波数で繰り返し行うことが必要である。
【００４５】
以下、このような復号装置の実装の例について説明する。
【００４６】
LDPC符号の復号アルゴリズムは、その特徴として極めて高い並列処理復号装置の実装を可能とする。しかしながら、符号長が大きい符号の完全並列復号装置は回路規模が非常に大きくなり、実現が困難である。
【００４７】
そこで、近年、現実的な回路規模での復号装置の実装に適した構造を持つLDPC符号が提案され、DVB-S.2（ETSI EN302307）等の伝送方式に採用されている。よって、以下、かかるLDPC符号を、DVB-S.2のLDPC符号と称する。
【００４８】
DVB-S.2のLDPC符号は、検査行列に対して行／列置換を施すことにより、次のような構造を持つ行列により表すことができるようになっている。
【００４９】
即ち、P=360としたとき、P×Pの単位行列、その単位行列のコンポーネントである１のうち１個以上が０になった行列（以下、適宜、準単位行列という）、単位行列または準単位行列をサイクリックシフト(cyclic shift)した行列（以下、適宜、シフト行列という）、単位行列、準単位行列、またはシフト行列のうちの２以上(複数)の和（以下、適宜、和行列という）、P×Pの０行列を構成行列として、複数の構成行列の組合わせにより構成される検査行列によって、DVB-S.2のLDPC符号は表すことができるようになっている。なお、以下、かかる構造の検査行列を、P×Pの構造の検査行列と称する。そして、以下、P×Pの構造の検査行列で表されるLDPC符号を、「Pの符号」と称する。
【００５０】
このような「Pの符号」を用いることで、P個の受信値（Pビット）およびP個のメッセージ（Pビット）を同時に処理する復号装置が実装可能となっている。
【００５１】
ただし、以下では説明を容易なものとすべく、P=6として説明を行っていく。図９は、符号化率2/3、符号長108のLDPC符号を表す検査行列であって、6×6の構造の検査行列の一例を示している。なお、図９の例では、6×6の構造を明確なものとすべく、6×6の各構成行列の間には間隔が空けられている。また、図９の例では、見易さのため、「０」の代わりに「．」と記述されている。即ち、図９の例の検査行列は、6×6の単位行列、その単位行列の１のうち１個が０になった準単位行列、それらのシフト行列、それらの和行列、6×6の０行列といった構成行列の組合わせにより構成されている。
【００５２】
図１０は、このような「P=6のLDPC符号」を復号する復号装置の一例を示している。
【００５３】
図１０の例の復号装置は、受信値バッファ２００、受信値格納メモリ２０１、ノード演算部２０２、シフト部２０３、メッセージ格納メモリ２０４、および復号結果格納メモリ２０５を含むように構成されている。
【００５４】
受信値バッファ２００は、通信路を通して受信したデータD200を１符号分蓄え、データD201として受信値格納メモリ２０１に転送する。なお、受信値バッファ２００に採用されている伝送方式によっては、受信値バッファ２００において符号ビットの並び替えが行われる場合もある。
【００５５】
受信値格納メモリ２０１は、受信値データD201を図９の検査行列の列の順に6個（1個は6ビット）ずつを同時に読み出し、即ち、6×6の構成行列を単位として読み出し、それらを6個の受信データD202として、ノード演算部２０２に供給する。
【００５６】
ノード演算部２０２は、６つのノード演算器２１０−１乃至２１０−６を有している。６つのノード演算器２１０−１乃至２１０−６は、受信値格納メモリ２０１から供給される６個の受信データD202のうちの所定の１個と、メッセージ格納メモリ２０４から供給される６個のメッセージD205のうちの所定の1個とを用いて、図示せぬ制御部の指示に基づいて、チェックノード演算またはバリアブルノード演算をそれぞれ並行に行い、計算したメッセージD203をシフト部２０３にそれぞれ供給する。即ち、ノード演算器２１０−１乃至２１０−６によってそれぞれ同時演算された６個のメッセージD203が出力されて、シフト部２０３に供給される。また、バリアブルノード演算時には、ノード演算器２１０−１乃至２１０−６によってそれぞれ演算された６個の復号結果D206が同時に出力されて、復号結果格納メモリ２０５に供給される。
【００５７】
シフト部２０３には、ノード演算部２０２から６個のメッセージD203が供給される場合、それに対応する枝が図９の検査行列において元となる単位行列などを幾つサイクリックシフトしたものであるかの情報が図示せぬ制御部から提供される。そこで、シフト部２０３は、この情報に基づいて、６個のメッセージD203を並べ替えるサイクリックシフトを行い、その結果をメッセージD204として、メッセージ格納メモリ２０４に供給する。
【００５８】
メッセージ格納メモリ２０４は、シフト部２０３から供給された６個のメッセージD204を、図示せぬ制御部から指定されるアドレスに格納する。また、メッセージ格納メモリ２０４は、図示せぬ制御部から指定されるアドレスから読みだした6個のデータを６個のメッセージD205としてノード演算部２０２に供給する。
【００５９】
復号結果格納メモリ２０５は、ノード演算部２０２のノード演算器２１０−１乃至２１０−６から同時にそれぞれ供給される6ビット分の復号結果D206、即ち6個の復号結果D206を格納し、復号が完了した後に、復号結果D207として出力する。
【００６０】
なお、この図１０の復号装置は、各種メモリへの読み書きの順番やシフト量を適切に制御することで、単一の符号のみならず、同じ構造を持つ別の符号の復号を行なうこともできる。
【００６１】
図１１は、ノード演算部２０２の６つのノード演算器２１０−１乃至２１０−６のそれぞれの構成例を示している。なお、以下、６つのノード演算器２１０−１乃至２１０−６を個々に区別する必要がない場合、単に、ノード演算器２１０と称する。
【００６２】
図１１の例のノード演算器２１０は、式(１)に従ったバリアブルノード演算と、式(７)に従ったチェックノード演算とを相互に切り替えて行うことができる。
【００６３】
ノード演算器２１０は、外部からメッセージ（データ）が供給（入力）される入力ポートとして、２つの入力ポートP301,P302を有している。すなわち、入力ポートP301には、図１０の受信値格納メモリ２０１から読み出された受信データD202が供給される。入力ポートP302には、図１０のメッセージ格納メモリ２０４から読み出されたメッセージD205が供給される。
【００６４】
また、ノード演算器２１０は、図１０のシフト部２０３に対してメッセージD203を供給（出力）する出力ポートP303と、図１０の復号結果格納メモリ２０５に対して復号結果D206を供給（出力）する出力ポートP304を有している。
【００６５】
ノード演算器２１０は、セレクタ３０１,３１６,３１８を有している。これらのセレクタ３０１,３１６,３１８が“v”の側を選択した場合には、ノード演算器２１０はバリアブルノード演算を行うことになる。これに対して、セレクタ３０１,３１６,３１８が“c”の側を選択した場合には、ノード演算器２１０はチェックノード演算を行うことになる。
【００６６】
まず、バリアブルノード演算を行う場合の動作の観点から、ノード演算器２１０の説明をする。
【００６７】
メッセージ格納メモリ２０４から供給される１列分のチェックノードからのメッセージD205が入力ポートP302を介して、メッセージD301（メッセージuj）として一つずつ入力され、セレクタ３０１を通過してメッセージD306として加算器３０２に入力される。加算器３０２には、セレクタ３１７の出力データD323も入力される。即ち、メッセージD306に対して、セレクタ３１７の出力データD323が加算されて、その加算値がレジスタ３０３に格納される。
【００６８】
ここで、セレクタ３１７の入力がレジスタ３０３の出力データD307側に切り替えられている場合、加算器３０２において、メッセージD306に対して、レジスタ３０３に格納してあるデータD307が加算されて、その加算値がレジスタ３０３に再格納される。
【００６９】
一方、セレクタ３１７の入力がセレクタ３１８の出力データD322側に切り替えられている場合、加算器３０２において、メッセージD306に対して、セレクタ３１８の出力データD322が加算される。即ち、セレクタ３１８の出力データD322とは、入力ポートP301に受信データD300として受信された受信データD202(u0i)である。よって、加算器３０２において、メッセージD306に対して、受信データD202(u0i)が加算されて、その加算値がレジスタ３０３に格納される。
【００７０】
このような動作が１列分繰り返されると、レジスタ３０３には、ｊ＝１からdvまでのΣuj＋u0iに相当するデータが蓄積される。かかるデータD307（ｊ＝１からdvまでのΣuj＋u0i）は、セレクタ３０４を介してレジスタ３０５に格納される。
【００７１】
一方、遅延用FIFO３１０は、レジスタ３０５から新たなデータD308（ｊ＝１からdvまでのΣuj＋u0i）が出力されるまでの間、セレクタ３０１が出力したチェックノードからのメッセージD306を遅延し、遅延入力メッセージD315として減算器３１２に供給する。
【００７２】
遅延入力メッセージD315は、減算器３１２においてレジスタ３０５の出力データD308から減算されて、その減算値D316（ｊ＝１からdv-1までのΣuj＋u0i)がセレクタ３１６を通過して、メッセージD321となる。このメッセージD312が、出力メッセージD203として出力ポートP303から出力されて図１０のシフト部２０３に供給される。
【００７３】
以上の内容を換言すると、ノード演算器２１０は、バリアブルノードに繋がっている全てのチェックノードからのメッセージと受信データの和から、求めたいチェックノードからのメッセージを引いて、求めたい枝 (edge)へのメッセージを計算することで、式(１)の演算を実現している。
【００７４】
次に、チェックノード演算を行う場合の動作の観点から、ノード演算器２１０の説明をする。
【００７５】
図１０のメッセージ格納メモリ２０４から供給される１行分のバリアブルノードからのメッセージD205が入力ポートP302を介して、メッセージD301（メッセージvi）として一つずつ入力され、その絶対値D303(|vi|)がLUT３００に供給される。
【００７６】
LUT３００は、そこに入力される値を引数xとして、式（７）のチェックノード演算における非線形関数φ(x)の演算結果を出力するLUTであり、絶対値D303(|vi|)の供給に対して、非線形関数φ(|vi|)の演算を行った演算結果D305（φ(|vi|)）を読み出す。
【００７７】
この演算結果D305（φ(|vi|)）は、セレクタ３０１を通過してメッセージD306として加算器３０２に入力される。加算器３０２において、このメッセージD306に対して、セレクタ３１７の出力データD323が加算されて、即ち、レジスタ３０３に格納してあるデータD307が加算されて、その加算値がレジスタ３０３に再格納される。このように、データD307は、演算結果D305（φ(|vi|)）の積算値となる。
【００７８】
1行分のメッセージD301（メッセージvi）の各演算結果D305（φ(|vi|)）が積算されると、その積算値D307（i＝１からdcまでのΣφ(|vi|))はセレクタ３０４を通過して、レジスタ３０５に格納される。
【００７９】
一方、遅延用FIFO３１０は、レジスタ３０５から新たなデータD308（i＝１からdcまでのΣφ(|vi|))が出力されるまでの間、セレクタ３０１の出力データD306、即ち、LUT３００の演算結果D305を遅延し、遅延データD315として減算器３１２に供給する。
【００８０】
減算器３１２において、レジスタ３０５に格納されている積算メッセージD308から、遅延データD315が減算され、その減算値D316（i＝１からdc-1までのΣφ(|vi|))はLUT３１４に供給される。
【００８１】
LUT３１４は、そこに入力される値を引数xとして、式（７）のチェックノード演算における非線形関数φ(x)の逆関数φ-1(x)の演算結果を出力するLUTであり、減算器３１２からの減算値D316（ｉ＝１からdc-1までのΣφ(|vi|)）の供給に対して、逆関数φ-1（Σφ(|vi|)）の演算を行った演算結果D318（φ-1(Σφ(|vi|)))を出力する。
【００８２】
以上の処理と並行して、各メッセージD301の正負を表す符号ビット(sign bit)D304 (sign(vi))と、レジスタ３０７に格納されている値D310との排他的論理和がEXOR回路３０６において演算されることで、その演算結果D309がレジスタ３０７に再格納される。
【００８３】
レジスタ３０７において、1行分の符号ビットが積算されたところで、その積算値D310(ｉ＝１からdcまでのΠsign(vi)）がセレクタ３０８を通過して、レジスタ３０９に格納される。
【００８４】
一方、遅延用FIFO３１０は、レジスタ３０９から新たなデータD311(ｉ＝１からdcまでのΠsign(vi))が出力されるまでの間、積算に用いられた符号ビットD304(sign(vi))を遅延し、遅延符号ビットD313 としてEXOR回路３１５に供給する。
【００８５】
この遅延符号ビットD313と、レジスタ３０９の積算値D311との排他的論理和がEXOR回路３１５において演算されることで、その演算結果、即ちｉ＝１からdc-1までのΠsign(vi)が符号ビットD319として出力される。
【００８６】
最終的に、LUT３１４の演算結果D318（φ-1(Σφ(|vi|)))に対して、この符号ビットD319が付加された値D320が、セレクタ３１６を通過してメッセージD321となる。このメッセージD312が、出力メッセージD203として出力ポートP303から出力されて図１０のシフト部２０３に供給される。
【００８７】
以上の内容を換言すると、ノード演算器２１０は、チェックノードに繋がっている全てのバリアブルノードからのメッセージの和から、求めたいバリアブルノードからのメッセージを引くことで、式(７)の演算を実現している。
【００８８】
また、ノード演算器２１０は、復号の最終段（例えば、あらかじめ定められた繰り返し復号の回数Nだけ行われるバリアブルノード演算及びチェックノード演算のうちの最後に行われるバリアブルノード演算）において、式（１）のバリアブルノード演算の代わりに、式（５）の演算が行われ、その演算結果、即ち、レジスタ３０５からの出力データD308が、復号結果D206として出力ポートP304から出力されて図１０の復号結果格納メモリ２０５に供給される。
【００８９】
なお、図１０の例の復号装置は、「P=6の符号」の復号装置であるが、Pが6以外の「Pの符号」の復号装置も基本的に図１０の例と基本的に同様の構成を取ることができる。
【非特許文献１】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 parse 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
【発明の開示】
【発明が解決しようとする課題】
【００９０】
しかしながら、「Pの符号」の復号装置を、従来の技術で図１０の例と同様の構成で実現する場合、ノード演算器は６並列でなくP並列必要となる。また、シフト部も、６×６ではなくP×Pのサイクリックしフトを行う必要がある。さらにまた、各種メモリも、６個のデータではなくP個のデータを同時に読み書きできる必要がある。
【００９１】
よって、Pの値が大きい場合には、復号装置全体の回路規模が増大してしまうという問題が生ずる。
【００９２】
また、従来の復号装置では、「Pの符号」以外の例えば「Qの符号」の復号を行なうことができない。従って、ひとつの伝送システムに用いる符号はすべて、「Pの符号」であることが必要であった。そのため、例えば、伝送レートの高い固定受信機向けのサービス用に「Pの符号」、伝送レートは低いが消費電力制限の大きい携帯型受信機向けのサービス用には「Qの符号」を採用するような伝送システムでは、共用受信機を構成する場合に、「Pの符号」と「Qの符号」のそれぞれに対して専用の復号装置を別々に設ける必要がある、といった問題も生じてしまう。
【００９３】
本発明は、このような状況に鑑みてなされたものであり、構造の異なる複数のLDPC符号の復号ができ、回路規模縮小も図ることができる復号装置を提供することを目的とするものである。
【課題を解決するための手段】
【００９４】
本発明の一側面の復号装置は、LDPC(Low Density Parity Check)符号を復号する復号装置であって、前記LDPC符号が、P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を第１の構成行列として、複数の前記第１の構成行列の組合せによる第１の構造の検査行列で元々表現されるか、または、元々の検査行列の行と列のうちの少なくとも1以上の置換により前記第１の構造の行列で表現される場合、FをPの１以外の約数としたとき、前記LDPC符号を受信した結果得られる受信値を復号するための演算として、F個のチェックノードの演算またはF個のバリアブルノードの演算を並列的に行い、各演算の結果得られるF個のメッセージを出力するメッセージ計算手段と、前記メッセージ計算手段から出力されるF個の前記メッセージに対して、F×Fのサイクリックシフトを行って出力するシフト手段と、前記シフト手段から出力されるF個の前記メッセージの書き込み、書き込まれたF個の前記メッセージの読み出し、または、F個の前記受信値の読み出し若しくは書き込みができる記憶手段と、F×Fの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはF×Fの０行列を第２の構成行列として、複数の前記第２の構成行列の組合せによる第２の構造の行列を定義した場合に、前記第１の構造の検査行列で表現される前記受信値に対して少なくとも列置換処理を施すことで、前記メッセージ計算手段への前記受信値の提供の制御として、前記第２の構成行列に対応するF個の前記受信値を単位とする提供の制御を行う制御手段とを備える。
【００９５】
前記列置換処理として、P＝F×Jとして、前記第１の構造の行列を構成する前記複数の第１の構成行列のP個の列に対して列番号0乃至P-1を付したとして、前記第１の構成行列を処理単位として、処理対象の前記第１の構成行列に対して列置換を施すことで、処理対象の前記第１の構成行列を、前記列番号をJで除算した余りが同一になる列同士で構成される複数の前記第２の構成行列によって区分する処理を含んでいる。
【００９６】
前記LDPC符号を受信することにより得られる受信値をバッファリングするバッファ手段をさらに備え、前記制御手段は、前記バッファ手段において、前記第１の構造の行列の形態で受信される前記受信値を並び替えて、前記第２の構造の行列の形態でバッファリングさせる制御を行い、前記第２の構造の行列の形態でバッファリングされた前記受信値を、前記第２の構成行列に対応するF個の前記受信値を単位として、前記記憶手段を介して前記メッセージ計算手段に提供する制御を行う。
【００９７】
前記制御手段は、前記第１の構造の行列の形態で受信される前記受信値の中から、前記第２の構造の行列に変化した場合に前記第２の構成行列に対応するF個の前記受信値を選択して、選択したF個の前記受信値を、前記記憶手段を介して前記メッセージ計算手段に提供する制御を行う。
【００９８】
本発明の一側面の復号方法およびプログラムは、本発明の一側面の上述した復号装置に対応する方法およびプログラムである。
【００９９】
本発明の一側面の復号装置および方法並びにプログラムにおいては、LDPC(Low Density Parity Check)符号を復号する復号装置において、次のような処理がなされる。即ち、前記LDPC符号が、P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を第１の構成行列として、複数の前記第１の構成行列の組合せによる第１の構造の検査行列で元々表現されるか、または、元々の検査行列の行と列のうちの少なくとも1以上の置換により前記第１の構造の行列で表現される場合に、FをPの１以外の約数としたとき、前記LDPC符号を受信した結果得られる受信値を復号するための演算として、F個のチェックノードの演算またはF個のバリアブルノードの演算を並列的に行い、各演算の結果得られるF個のメッセージを出力するメッセージ計算処理が行われる。また、前記メッセージ計算処理の結果出力されるF個の前記メッセージに対して、F×Fのサイクリックシフトを行って出力するシフト処理が行われる。また、前記シフト処理の結果出力されるF個の前記メッセージの書き込み、書き込まれたF個の前記メッセージの読み出し、または、F個の前記受信値の読み出し若しくは書き込みがほぼ同時に行われる。そして、F×Fの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはF×Fの０行列を第２の構成行列として、複数の前記第２の構成行列の組合せによる第２の構造の行列を定義した場合に、前記第１の構造の検査行列で表現される前記受信値に対して少なくとも列置換処理を施すことで、前記メッセージ計算処理に対する前記受信値の提供の制御として、前記第２の構成行列に対応するF個の前記受信値を単位とする提供の制御が行われる。
【発明の効果】
【０１００】
本発明によれば、LDPC(Low Density Parity Check)符号を復号する復号装置を提供できる。特に、構造の異なる複数のLDPC符号の復号ができ、回路規模縮小も図ることができる。
【発明を実施するための最良の形態】
【０１０５】
次に、本発明の手法について説明する。
【０１０６】
本明細書でいう「Pの符号」とは、準巡回(QC（Quasi Cyclic)）符号の性質を持ったLDPC符号のひとつである。
【０１０７】
ここでQC符号とは、任意の符号語を、ある自然数の周期だけ巡回シフトした系列が、元の符号語以外の符号語となる符号のことをいう。
【０１０８】
QC符号の検査行列は、巡回行列（cyclic matrix）を用いて表すことができる。かかる巡回行列が、本明細書でいうシフト行列であり、全ての列がある任意の列、例えば最初の列の巡回シフト（サイクリックシフト）である行列として定義される。
【０１０９】
「Pの符号」に含まれるシフト行列は、上述したように、P×Pの単位行列または準単位行列がサイクリックシフトされて生成される。即ち、P×Pの単位行列または準単位行列に対して、サイクリックシフトを１列ずつ順次施していくことで、相異なる種類のシフト行列が順次生成されていくことになる。そして、P列分のサイクリックシフトが行われると、元の単位行列または準単位行列が再度得られることになる。即ち、このようなサイクリックシフトの単位がPとなっている。
【０１１０】
ここで、留意すべき点は、厳密には、「Pの符号」で用いられる「準単位行列」とそのシフト行列は、QC符号には含まれない点である。即ち、「Pの符号」を含むDVB-S2のLDPC符号には行／列置換後に、右上の１個所のみ、「準単位行列」が現れる。その意味で、厳密には、DVB-S2のLDPC符号は、QC符号ではない。ただし、DVB-S2のLDPC符号の復号器では、この欠けた部分に簡単な例外処理を施しているだけなので、復号器のアーキテクチャとしては、QCの場合と何等違いはない。以上のことから、「Pの符号」は、QC符号のひとつであると記述せずに、QC符号の性質を持ったと記述した次第である。
【０１１１】
換言すると、P×Pのシフト行列、その生成元となるP×Pの単位行列若しくはP×Pの準単位行列、これらの和であるP×Pの和行列、P×Pの０行列を構成行列として、各構成行列を規則的に配置させた行列が、P×Pの構造の検査行列である。「Pの符号」は、このような規則的な構造の検査行列として表すことができるゆえ、準巡回符号の性質を持っているのである。
【０１１２】
即ち、「Pの符号」とは、P×Pのシフト行列等のP×Pの構成行列を単位として構成されるという規則性を有している。よって、「Pの符号」の復号装置を、従来の技術で図１０の例と同様の構成で実現する場合、ノード演算器は６並列でなくP並列必要となっていた。また、シフト部も、６×６ではなくP×Pのサイクリックシフトを行う必要があった。さらにまた、各種メモリも、６個のデータではなくP個のデータを同時に読み書きできる必要があった。
【０１１３】
そこで、本発明人は、P×Pの構造の検査行列に対して、行や列の置換を行うことで、F×Fの構成行列（ただし、Fは１以外のPの約数）を規則的に配置させた行列に並び替える処理またはそれと等価な処理（以下、これらをまとめて並び替え処理と称する）を実行し、並び替え処理後の行列を用いて復号を行う、といった手法を発明した。ここで、F×Fの構成行列の種類としてはP×Pの構成行列と同種類の行列、即ち、F×Fの単位行列、F×Fの準単位行列、F×Fのシフト行列、および、F×Fの和行列、F×Fの０行列が存在する。
【０１１４】
なお、並び替える処理またはそれと等価な処理をまとめて並び替え処理と呼称することにしたのは、次の理由による。即ち、P×Pの構造の検査行列に対して行または列を実際に並び替えて行列の構造を変換させた状態でメモリに格納させた後に、復号する（ノード演算器側に提供する）ことは必須ではないからである。即ち、例えば、P×Pの構造のままで検査行列をメモリに格納させ、ノード演算器に提供する段階で、行または列を並び替える手法と等価な手法により、選択的にメモリから読み出してノード演算器に提供してもよいからである。即ち、ノード演算器からすると、検査行列の並び替えが行われた状態と等価な状態で、各受信データが提供されれば足りるからである。
【０１１５】
換言すると、本発明の手法とは、P×Pの構造の検査行列で表現される受信値に対して少なくとも列の置換をする処理若しくはそれと等価な処理を含む並び替え処理を施す手法であり、これにより、ノード演算器への受信値の提供の制御として、F×Fの構成行列に対応するF個の受信値を単位とした提供を実現する手法であるといえる。
【０１１６】
このような本発明の手法を適用することで、「Pの符号」を復号する場合でも、ノード演算器の並列数をP並列からF並列に削減することができる。また、シフト部も、P×PではなくF×Fのサイクリックシフトを行えば足りるようになる。さらにまた、各種メモリも、P個のデータではなくF個のデータを同時に読み書きできればよくなる。
【０１１７】
以上のように、本発明の手法を適用することで、復号装置全体として、従来の復号装置と比較して大幅に回路規模を削減できるようになる。ただし、詳細については後述するが、Pの約数は複数存在する場合があり、かかる場合に、最小値をFとする必要はなく、伝送レートや回路の動作周波数に応じた最適値をFとして採用すると好適である。
【０１１８】
さらにまた、詳細については後述するが、Pとは異なる値であって１（という値）以外のQが、Fを約数に持つ場合、即ち、FがPとQの公約数の場合、本発明の手法を適用することで、上述のF並列のノード演算器等を構成とする復号装置を用いて、「Pの符号」のみならず「Qの符号」も選択的に切り換えて復号することが可能になる。
【０１１９】
具体的には例えば、P=6に対してF=3とした場合には、本発明の手法を適用することで、復号装置は、図１２の構成を取ることができる。即ち、図１２は、本発明を適用した復号装置の構成例を示している。
【０１２０】
図１２の例の復号装置は、受信値バッファ５００、受信値格納メモリ５０１、ノード演算部５０２、シフト部５０３、メッセージ格納メモリ５０４、復号結果格納メモリ５０５、および制御部５０６を含むように構成されている。
【０１２１】
このように、図１２の例の復号装置は、全体の構成、即ち、各構成要素（ブロック）の繋がりや、復号装置全体からみた場合の各構成要素の役割（機能）は、制御部５０６を除き、上述の図１０の例の復号装置と基本的に同様である。しかしながら、各構成要素の視点からすると、次のような違いがある。
【０１２２】
即ち、図１０の例の受信値バッファ２００、受信値格納メモリ２０１、メッセージ格納メモリ２０４、および復号結果格納メモリ２０５は、P=６個のデータ（6ビット）を同時に読み書きできるメモリ構成をとっている。これに対して、受信値バッファ５００、受信値格納メモリ５０１、メッセージ格納メモリ５０４、復号結果格納メモリ５０５は、F=3個のデータ（3ビット）を同時に読み書きできるメモリ構成をとっている。
【０１２３】
また、図１０の例のシフト部２０３は、６×６（＝P×P）のサイクリックシフトを行う構成を有している。これに対して、図１２の例のシフト部５０３は、３×３（＝F×F）のサイクリックシフトを行う構成を有している。
【０１２４】
また、図１０の例のノード演算部２０２は、P=６個のノード演算器２１０−１乃至２１０−６を有している。これに対して、図１２の例のノード演算部５０２は、F=３個のノード演算器５１０−１乃至５１０−３を有している。
【０１２５】
よって、以上の各構成要素の違いがあることから、図１２の例の復号装置は全体として、図１０の例の従来の復号装置と比較して、回路規模が縮小された装置として構成することができる。
【０１２６】
なお、ノード演算器５１０−１乃至５１０−３は、図１１の構成のノード演算器２１０をそのまま採用することができる。もっとも、ノード演算器５１０−１乃至５１０−３自体は、図１１の構成以外の構成を採用した場合にも、本発明を適用できることは言うまでも無い。
【０１２７】
また、ノード演算器５１０−１乃至５１０−３の代わりに、３つのバリアブルノード演算器と３つのチェックノード演算器とが別々の回路として構成されている復号装置に対しても、本発明を適用できることも言うまでも無い。
【０１２８】
さらにまた、ノード演算器５１０−１乃至５１０−３を用いずにバリアブルノード演算を行う場合にも、本発明を適用できることも言うまでも無い。
【０１２９】
以下、図１２の例の復号装置の動作について説明する。
【０１３０】
なお、後述するように、図１２の例の復号装置は、Fを約数に持つ任意のPについて、「Pの符号」を復号することができる。ただし、動作の説明をする際には、図１０の例の従来の復号装置との比較を容易なものとすべく、復号対象は、図９の６×６の構造の検査行列で示される「P=6のLDPC符号」であるとする。
【０１３１】
受信値バッファ５００は、通信路を通して受信したデータD500を１符号分蓄え、受信値格納メモリ５０１に転送する。
【０１３２】
ここで、検査行列の列の並び替えは符号系列の並び替えに相当する。よって、制御部５０６の制御に基づいて、次のような並び替え処理が受信値バッファ５００において実行される。
【０１３３】
即ち、図９の検査行列は、６×６の構成行列の集合体として表されている。そこで、６×６の構成行列を並び替えの単位として、その６×６の構成行列を、所定規則に基づいて、３×３の構成行列の集合体となる行列に並び替えを行う、といった並び替え処理が実行される。ここで、所定規則としては、行番号または列番号を２で割った余りが同一になる行と列同士で構成される行列を、即ち、遇数または奇数でそれぞれ区分した行列を、３×３の構成行列とする、といった規則が採用されているとする。
【０１３４】
具体的には例えば、図１３は、図９の検査行列の構成行列の一例であって、６×６のシフト行列を示している。図１３において、○（丸印）内の数値は列番号を示しており、□（四角印）内の数値は行番号を示している。
【０１３５】
この図１３の６×６のシフト行列に対して、上述の規則に従った並び替え処理が施されると、図１４の行列が得られることとなる。図１４の行列は、図中点線で区分されているように、3×3の０行列、3×3の準単位行列、３×３のシフト行列といったように、３×３の構成行列（点線で区分されている４つの構成行列）で構成されていることがわかる。
【０１３６】
以上のような並び替え処理が、その他の６×６の各構成行列にもそれぞれ施される。その結果、図９の６×６の構造の検査行列は、図１５の構造の行列に並び替えられることになる。なお、図１５の例では、３×３の構成行列を単位として区分されていることを明確にすべく、3×3の各構成行列の間には間隔が空けられている。即ち、図１５の例の行列は、3×3の単位行列、3×3の準単位行列、3×3のシフト行列、3×3の和行列、3×3の０行列の組合わせにより構成されている。
【０１３７】
よって、図１２の受信値格納メモリ５０１の後段の動作は、6（＝P）が3(=F)に変化した以外は、図１０の受信値格納メモリ２０１の後段の動作と同様となる。換言すると、あたかも「P=3の符号」を復号するのと全く同様の動作が行われる。
【０１３８】
なお、伝送方式として、そもそも符号ビットの順番を入れ替えて通信路に送出する方式が採用されている場合は、その並び替えも、上述の並び替え処理とともにまたはその前後に、受信値バッファ５００において行われる。
【０１３９】
以上、Fとして、P=6の約数である3を採用した場合の例について説明した。当然ながら、P=6の別の約数（１を除く）、即ち2を採用することもできる。ただし、この場合、図９の６×６の構造の検査行列に施される並び替え処理において採用される所定規則とは、次のような規則となる。即ち、行番号または列番号を３で割った余りが同一になる行と列同士で構成される行列を、２×２の構成行列とする、といった規則が採用される。
【０１４０】
具体的には例えば、図１３の６×６のシフト行列に対して、かかる規則に従った並び替え処理が施されると、図１６の行列が得られる。図１６の行列は、図中点線で区分されているように、2×2の０行列、2×2の準単位行列、2×2のシフト行列といったように、2×2の構成行列（点線で区分されている９つの構成行列）で構成されていることがわかる。
【０１４１】
よって、この場合も、受信値格納メモリ５０１の後段の動作は、6（＝P）が2(=F)に変化した以外は、図１０の例の受信値格納メモリ２０１以降の後段の動作と同様になる。換言すると、あたかも「P=2のLDPC符号」を復号するのと全く同様の動作が行われる。
【０１４２】
即ち、F=2とした場合には、復号装置は、図１２の構成をとる必要はなく、2並列のノード演算器、2×2のサイクリックシフトを行うシフト部、および、2個のデータ（2bit）のデータを同時に読み書きできる各種メモリを有する構成を取れば足りる。
【０１４３】
さらに、以上においてはPが6である場合の例について説明したが、当然ながらPは6以外となる場合がある。例えば、検査行列の構造によっては、P=360となる場合がある。このように任意の値がPとなる場合でも、本発明の手法は適用可能である。そして、本発明の手法によれば、Pが決定した後は、１以外の任意の約数をFとして採用することも可能である。
【０１４４】
即ち、任意のPと、そのPの約数のうちの１を除く任意のFが採用された場合、P×Pの構造の検査行列（PのLDPC符号）に対して、次のような所定規則に従った並び替え処理を施すとで、F並列のノード演算器、F×Fのサイクリックシフトを行うシフト部、および、F個のデータ（Fビット）のデータを同時に読み書きできる各種メモリを有する構成で、復号装置を実装できるようになる。
【０１４５】
この場合の所定規則とは、P=F×Jとすると、行番号0乃至P-1または列番号0乃至P-1をJで割った余りが同一になる行と列同士で構成される行列を、F×Fの構成行列とする、といった規則となる。そして、かかる規則に従った並び替え処理が、P×Pの構造の検査行列を構成するP×Pの各種構成行列のそれぞれに施されることになる。
【０１４６】
なお、上述したように、ここでいう並べ替え処理とは、P×Pの構造の検査行列を並び替えた状態でメモリに記録することまでに限定する処理ではない。即ち、上述の例では、受信値バッファ５００において並び替え処理が実行され、並び替え後の行列がいったん格納されて、その並び替え後の行列が、受信値格納メモリ５０１を介してノード演算部５０２に提供されていた。しかしながら、ノード演算部５０２の前段のメモリでは、P×Pの構造の検査行列のまま格納させておき、かかるメモリからノード演算部５０２に対して提供する際に、上述の所定規則に従った並び替え処理を読み出しの処理として適用し、即ち、上述の所定規則に従って選択的にメモリからデータを読み出して、ノード演算部５０２に提供するようにしてもよい。即ち、ここでいう並べ替え処理とは、このような読み出し処理も含めた広義な概念の処理である。なお、読み出し処理の制御については、制御部（図１２の例では制御部５０６）に担当させれば容易に実現可能である。
【０１４７】
また、上述の例とは、符号長108，符号化率2/3の例であったが、これらの値は例示にしか過ぎないことは言うまでもない。即ち、例えば、P=6となり、エッジ総数が同じかそれ以下であれば、任意の符号長、任意の符号化率を採用しても、制御信号を変えることで、同一の復号装置を用いて復号することが可能である。さらに、Pが同じで符号長とエッジの総数がそれぞれ所定値以下であるという条件を満たす符号の復号装置は、同じ条件を満たし得る符号長、異なる符号化率の符号であっても復号することができる。
【０１４８】
以上の内容をまとめると、本発明を適用することで、Pの値に拘束されることなく、伝送レートや動作周波数に応じて、復号の並列性Fを可能な範囲内（Pの約数という範囲内）で任意に選択できる。これにより、回路規模の小さい復号装置を開発することが容易に可能になる。
【０１４９】
即ち、例えば、Pが例えば360のときには、 Fは360，180，120といった約数の中から任意のものを選択することができる。このFは、上述した如くノード演算器の並列数になっていることからもわかるように、本発明を採用した場合には復号の並列性を示す値であるといえる。そこで、復号装置の開発者等は、復号の並列性を考慮しつつ、伝送レートと回路の動作周波数に応じて最適な値をFとして選ぶことができるようになる。
【０１５０】
即ち、必要な伝送レートに対して、F として大きい値のPの約数を選択ときには、復号の並列性が必要以上に高いため、復号に必要な時間よりも長い間隔でしかデータが到来しない。そこで、データが到来する時間と復号に必要な時間が同程度になるように、Pの約数のうちの適当な値をFとして選ぶことで、復号の並列性を下げ、その結果、復号装置の回路規模を削減できる。また、将来的に回路が高速動作するようになれば、Fとして小さい値を採用したとしても、復号装置の並列性を下げても従来と同等の性能を達成することが可能になる。
【０１５１】
さらに、PとQ（ただし、P > Q）が公約数を持つとき、その公約数を復号の並列性Fとして採用した復号装置は、「Pの符号」と「Qの符号」の両者を復号することが可能である。
【０１５２】
従って、例えば、高い伝送レートを必要とするサービスには大きな「Pの符号」を用い、携帯型受信機用サービス（それゆえ伝送レートが低くてよいサービス）には小さな「Qの符号」を用いた場合でも、１つの復号装置で、どちらのサービスの符号も復号できる復号機能を備えた共通受信装置を実現することができる。
【０１５３】
即ち、共通受信装置を実現可能であることは、「Pの符号」と「Q の符号」の両方を伝送システムの中に共存させることを可能にする。
【０１５４】
例えば、DVB-S.2のLDPC符号を8PSK,30Msym/sで送信する場合には、符号ビットのビットレートは90Mbpsになる。検査行列の列重みの平均は概ね3.5程度であるため、符号1ビット当たりに必要な演算量は、復号回数を50回とすると、3.5×50×2=350程度になる。よって、クロック数としては、この演算量に、回路の効率性として仮に1.5を掛けた数が必要になる。そのクロック数を演算の並列性360で割ると、復号装置は90Mbps×350×1.5/360=131.25MHzで動作すればよいことになる。
【０１５５】
この場合、復号の並列性をP=360とした従来の復号装置では、360個のデータを同時に読み書きできるメモリを実現すべく、ビット数が大きく、ワード数の少ない面積効率の悪いRAMを採用する必要があった。また、かかる従来の復号装置では、ノード演算器も360個有する必要があった。このようなことから、従来の復号装置は、回路規模が非常に大きなものであった。
【０１５６】
ここで、仮に、DVB-S.2のLDPC符号を、上述の90Mbpsよりも低い伝送方式、例えば15Mbpsの伝送方式に応用する場合、復号の並列性をF=60としても、同じ動作周波数で同じ復号回数を実現すること、即ち同じ復号性能を達成することができる。
【０１５７】
復号の並列性をF=60とすることができれば、同時に読み書きすべきデータが60個で済む。よって、メモリを構成する場合には、上述の従来の面積効率の悪いRAMと比較してワード数が6倍のRAMであって、そのビット数を減らした同一総数のRAMを採用することができる。或いは、そのビット数自体は同一のRAMを採用した場合でも、RAMの総数を減らすことが可能になる。いずれにしても、同じビット数のデータを保存するための面積効率が格段に上がることになる。また、ノード演算器の数もF=60個になるため、論理回路の規模も減らすことができる。
【０１５８】
即ち、DVB-S.2のLDPC符号を、例えば地上波の放送に利用する場合、消費電力の問題で携帯型移動受信機での受信は難しくなる。そこで、例えば携帯型受信機向けには、Qを60としたより短い符号長の符号を用いてサービスを行う場合が想定できる。そのような場合であっても、本発明を適用することで、復号の並列性をF=60として符号長64800の符号まで復号できる復号装置であって、「P=360の符号」と「Q=60の符号」の両者を復号可能な復号装置を容易に実現することができる。よって、かかる復号装置を備えた受信装置は、固定受信用サービス（「P=360の符号」を用いるサービス）と、携帯型受信機用サービス（「Q=60の符号」を用いるサービス）の両方を受信することが可能になる。
【０１５９】
以上の内容をまとめると、本発明を適用することで、大きな値Pを持つLDPC符号の復号装置を、その約数Fに基づいて実装することが可能になる。即ち、ビットレートの低い伝送方式や、将来回路が高速化した場合には、従来と比較して回路規模の小さい復号装置を実現することが可能になる。
【０１６０】
また、本発明を適用することで、公約数Fを持つ整数に基づく符号は、全てFに基づく復号装置で復号することができるようになる。よって、伝送レートや受信形態の異なるサービスに応じて、適した大きさのLDPC符号をひとつの伝送システムに共存させることが可能になる。
【０１６１】
即ち、上述の例の伝送システムは、「Pの符号」と「Qの符号」の２種類のみが用いられたが、１以外の整数値Fの倍数となる相異なる複数の整数値のうちの、システムの設計者等により選択されたK個（Kは２以上の整数値）の整数値α（αは、選択されたK個の整数値を示す）のそれぞれに対応するK種類の「αの符号」を用いることが可能になる。
【０１６２】
ところで、上述した一覧表示処理も含む一連の処理は、ハードウェアにより実行させることもできるし、ソフトウエアにより実行させることもできる。
【０１６３】
上述した一連の処理をソフトウエアにより実行させる場合、本発明が適用される復号装置は、例えば、図１７に示されるコンピュータで構成することもできる。
【０１６４】
図１７において、CPU（Central Processing Unit）１００１は、ROM（Read Only Memory）１００２に記録されているプログラム、または記憶部１００８からRAM（Random Access Memory）１００３にロードされたプログラムに従って各種の処理を実行する。RAM１００３にはまた、CPU１００１が各種の処理を実行する上において必要なデータなども適宜記憶される。
【０１６５】
CPU１００１、ROM１００２、およびRAM１００３は、バス１００４を介して相互に接続されている。このバス１００４にはまた、入出力インターフェース１００５も接続されている。
【０１６６】
入出力インターフェース１００５には、キーボード、マウスなどよりなる入力部１００６、ディスプレイなどよりなる出力部１００７、ハードディスクなどより構成される記憶部１００８、および、モデム、ターミナルアダプタなどより構成される通信部１００９が接続されている。通信部１００９は、インターネットを含むネットワークを介して他の装置（図示せず）との間で行う通信を制御する。
【０１６７】
入出力インターフェース１００５にはまた、必要に応じてドライブ１０１０が接続され、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどよりなるリムーバブルメディア１０１１が適宜装着され、それらから読み出されたコンピュータプログラムが、必要に応じて記憶部１００８にインストールされる。
【０１６８】
一連の処理をソフトウエアにより実行させる場合には、そのソフトウエアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどに、ネットワークや記録媒体からインストールされる。
【０１６９】
このようなプログラムを含む記録媒体は、図１７に示されるように、装置本体とは別に、ユーザにプログラムを提供するために配布される、プログラムが記録されている磁気ディスク（フロッピディスクを含む）、光ディスク（CD-ROM(Compact Disk-Read Only Memory),DVD(Digital Versatile Disk)を含む）、光磁気ディスク（ＭＤ（Mini-Disk）を含む）、もしくは半導体メモリなどよりなるリムーバブルメディア（パッケージメディア）１２１１により構成されるだけでなく、装置本体に予め組み込まれた状態でユーザに提供される、プログラムが記録されているROM１００２や、記憶部１００８に含まれるハードディスクなどで構成される。
【０１７０】
なお、本明細書において、記録媒体に記録されるプログラムを記述するステップは、その順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０１７１】
また、本明細書において、システムとは、複数の装置や処理部により構成される装置全体を表すものである。
【図面の簡単な説明】
【０１７２】
【図１】LDPC 符号の検査行列の例を示す図である。
【図２】LDPC符号の下三角形な検査行列の例を示す図である。
【図３】LDPC符号を復号する際の一連の処理行程を説明するフローチャートである。
【図４】メッセージの流れの説明図である。
【図５】(3,6) LDPC 符号の 検査行列の例を示す図である。
【図６】図５の検査行列のタナーグラフを示す図である。
【図７】バリアブルノードでのメッセージ計算を説明する図である。
【図８】チェックノードでのメッセージ計算を説明する図である。
【図９】６×６の構造の検査行列の例を示す図である。
【図１０】LDPC 符号の従来の復号装置の構成例を示すブロック図である。
【図１１】ノード演算器の構成例を示すブロック図である。
【図１２】本発明が適用されるLDPC符号の構成例を示すブロック図である。
【図１３】６×６のシフト行列の一例を示す図である。
【図１４】図１３のシフト行列の行や列を並べることで、３×３の構成行列を生成する手法を説明する図である。
【図１５】図９の６×６の構造の検査行列に対して、図１４の手法の並び替え処理を施すことで得られる３×３の構造の行列を示す図である。
【図１６】図１３のシフト行列の行や列を並べることで、２×２の構成行列を生成する手法を説明する図である。
【図１７】本発明が適用される復号装置の他の実施形態としての、コンピュータの構成例を示すブロック図である。
【符号の説明】
【０１７３】
５００  受信値バッファ，  ５０１  受信値格納メモリ，  ５０２  ノード演算部，  ５０３  シフト部，  ５０４  復号結果格納メモリ，  ５０５  メッセージ格納メモリ，  １００１  CPU，  １００２  ROM，  １００３  RAM，  １００８  記憶部，  １０１０  リムーバブルメディア
【図１】
0004487213.tif 000010
【図２】
0004487213.tif 000011
【図３】
0004487213.tif 000012
【図４】
0004487213.tif 000013
【図５】
0004487213.tif 000014
【図６】
0004487213.tif 000015
【図７】
0004487213.tif 000016
【図８】
0004487213.tif 000017
【図９】
0004487213.tif 000018
【図１０】
0004487213.tif 000019
【図１１】
0004487213.tif 000020
【図１２】
0004487213.tif 000021
【図１３】
0004487213.tif 000022
【図１４】
0004487213.tif 000023
【図１５】
0004487213.tif 000024
【図１６】
0004487213.tif 000025
【図１７】
0004487213.tif 000026