(57)【要約】【課題】LDPCの復号回路において転送速度を上げるためには、推定事後確率データを格納するメモリを並列して多量に保有しなくてはならい。【解決手段】メモリAおよびメモリBは検査行列の符号部分の内の連続して１が存在している列901に対応するメモリであり、常にアクセスを受けるため高速なメモリもしくはフリップフロップで構成する。メモリCは符号部分の内のランダムに１が存在している列902に対応したメモリ、メモリDは階段状に１が存在しているパリティ部分1003に対応したメモリであり、いずれも通常なメモリで構成する。このように、検査行列の特徴を考えて推定事後確率データの格納方法を工夫することにより使用するメモリの個数を減らした。【選択図】図９
2010268179.tif 000002
【特許請求の範囲】
【請求項１】
低密度パリティコード（LDPC）の情報を検査行列に従いシリアル処理して復号するLDPC復号回路において、
推定事後確率データを記憶するメモリは、前記検査行列のパターンに基づいてブロック化された前記検査行列の符号部分の内で“１”を有するブロックが列に多く存在する箇所に対して高速メモリもしくはフリップフロップメモリで構成し、前記検査行列の符号部分のそれ以外の箇所に対して少なくとも１つのランダムメモリにより構成し、前記検査行列のパリティ符号部に対して他の１つのランダムメモリで構成することを特徴とするLDPC復号回路。
【請求項２】
前記ブロック化は、前記検査行列のQuasi-Cyclic 符号とRepeat Accumulate符号により行なわれることを特徴とする請求項１に記載のLDPC復号回路。
【請求項３】
前記パリティ符号部のパターンが、当該ランダムメモリを一度読み出したデータが次の行に対する処理で必ず使用されるようなものであるときは、前に読み出したデータを保持しておくことを特徴とする請求項１もしくは２に記載のLDPC復号回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はLDPC復号回路に関する。
【背景技術】
【０００２】
LDPC(Low Density Parity Check Code)とは、通信などにおいて雑音によって情報が誤ってしまう時に、その誤りを訂正する目的で情報に付加される冗長な符号であり、訂正能力が非常に高いことが特徴である。冗長な符号を付加する装置を符号化装置といい、誤りを訂正する装置を復号化装置という。
【０００３】
LDPCは、1960年代に提案されたが、そのアルゴリズムを実現するためには、当時としては、大量の記憶境域を持たなくてはならず、あまり実用的ではないとされていた。しかしながら、近年の高集積化や強力な誤り訂正の需要により、注目され始めている。
【０００４】
先ず、LDPCの符号化について説明する。nビットの情報符号の集合をCとし、mビットの検査符号の集合をMとする。通信路に送出する情報をX=(C,M)と定義し、m行，(m+n)列を有する検査行列をHとしたとき、X・H＝０となるような集合Mを見つけ出すことができる。Xを算出することを符号化と呼ぶ。
【０００５】
次に、LDPCの復号化について説明する。通信路において、Xを変調した集合をFとした時、雑音などにより、データが壊れて、Fを復調した結果がYとなってしまった場合、その値から誤りを推測して、訂正した後の集合をyとすると、H・y＝０となる筈であり、このようなyを見つけることを復号化と呼ぶ。このとき、Y、yは復調後のデータであるため軟判定符号となっている。但し、H・y＝０を計算するときには、yは硬判定後の情報で行なう。
【０００６】
LDPCの復号化は、推定事後確率データZRを初期値（復調結果Y）から検査行列H（m，m+n）に従って順次に更新していくことにより行なう。この更新の過程において、全要素の値を初期値０とし更新されていく検査行列H（m,m+n）と同サイズの行列Ｌ（m,m+n）を使用する。検査行列H（m，m+n）の要素が１に関連する要素について全処理が終了すると、H・y＝０のチェックが行なわれ、NGの場合は処理が繰り返される。このようなLDPC符号の復号を回路化する場合は、一般的に、図１６に示すような回路構成が採用される。
【０００７】
推定事後確率データZRは、非常に大きいデータであり、また連続したデータであるため、メモリに格納することができる。この推定事後確率データZRを格納するメモリをZRメモリといい、一般的には１つのアドレスに１つのデータを記憶する。メモリのビット幅は、推定事後確率データZRの量子化ビット数により、１つのアドレスに１つのデータであれば、メモリのビット幅とデータの量子化ビット幅は等価となる。推定事後確率データZRは、１つずつシリアルに読み出すことも理論上は可能であるが、計算速度が非常に低下するため、一般的には、いくつかのデータを一度に読み出す必要が生じる。また、Lの値も同様でLメモリに値を記憶するが、Lメモリは本発明とは直接関係しないので詳細な説明は省略する。
【０００８】
ZRメモリは推定事後確率データZRを検査行列H（m,m+n）の列毎に記憶し、Lメモリは行列L（m,m+n）の各要素の値を記憶する。上記処理の過程で、ZRメモリおよびLメモリを読み出して計算し、その結果を再びZRメモリおよびLメモリに格納することを繰り返す。この時、推定事後確率データZRは検査行列の要素の内で１の存在している列の要素を取り出す必要がある。
【０００９】
ところで、検査行列H（m,m+n）が膨大な場合、ZRメモリおよびLメモリの記憶容量も膨大となり、全ての情報を１つのメモリに保存すると、その情報の読出し及び書込み処理をシリアルに行うこととなるため処理性能が落ちてしまう。この種の問題に関し、推定事後確率データを複数のメモリに分割して格納するとした従来技術が知られている。
【００１０】
しかし、この技術では単に複数のメモリに分割するとしただけであるため、後述のようにブロック化した検査行列H（m,m+n）において、ランダムに“１”が存在しアクセスを受けないメモリはともかく、連続して“１”が存在し常にアクセスを受けるメモリでは低速な読み書きとなるので、それだけ処理性能が劣化することは避けられないという問題点がある。一方、読み書き速度を向上させようとして、単純に全てのメモリを高速メモリもしくはフリップフロップで構成したり、並列して読み書きできるメモリの数を増やすとコストが嵩むことになる。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開2008−278184
【発明の開示】
【発明が解決しようとする課題】
【００１２】
解決しようとする問題点は、常にアクセスを受ける推定事後確率データを記憶するメモリの読み書き速度が遅いということである。
【課題を解決するための手段】
【００１３】
本発明は、推定事後確率データを記憶するメモリの速度の向上を図るため、検査符号の特性に合わせて記憶方式を工夫したことを最も主要な特徴とする。
【発明の効果】
【００１４】
本発明のLDPC復号回路は、高い転送性能を持たせるためにLDPC復号アルゴリズムの回路化を少数のメモリで実現できるという利点がある。その理由は、検査行列の特徴に従って推定事後確率データをメモリに格納する構成としたからである。即ち、検査行列の行単位に処理を行う場合に、その時に必要なデータがメモリから読み易い構成とした。
【図面の簡単な説明】
【００１５】
【図１】LDPCの一般的な復号アルゴリズム（メイン部）を示すフローチャート
【図２】LDPCの一般的な復号アルゴリズム（Z計算部）を示すフローチャート
【図３】LDPCの一般的な復号アルゴリズムフロー（L計算部）を示すフローチャート
【図４】一般的な検査行列を例示する図
【図５】検査符号（Quasi-Cyclic LDPC符号）のブロック化を例示する図
【図６】ブロック化された検査符号の表示を例示する図
【図７】ブロック表示された一般的な検査符号を例示する図
【図８】本発明のLDPC復号回路を示す図
【図９】検査行列とZRメモリを構成するメモリとの対応関係を示す図
【図１０】メモリAと推定事後確率データZRと行列の対応イメージを示す図
【図１１】メモリCと推定事後確率データZRと行列の対応イメージを示す図
【図１２】図８をより具体的に示した図
【図１３】本発明のLDPC復号回路の動作例を示すタイミングチャート
【図１４】他の検査行列とZRメモリを構成するメモリとの対応関係を示す図
【図１５】図14に対応するLDPC復号回路の動作例を示すタイミングチャート
【図１６】一般的な復号器の回路構成図
【発明を実施するための最良の形態】
【００１６】
推定事後確率データを記憶するメモリの読み書き速度を向上するという目的を、コストを抑えつつ実現した。
【実施例】
【００１７】
先ず、LDPCの復号化の一般的なアルゴリズムについて、図１〜図３により簡単に説明する。このアルゴリズムを実現するための回路構成は、基本的には図１６に示したとおりである。検査行列Hはm行、（m+n）列、初期値として、Z(i)=Y(i）、L(j,i)=0とする。但し、j=0〜(m-1)、i=0〜(m+n-1)である（図１のステップS1）。なお、tはトライ回数を表す。
【００１８】
j=0として検査行列Hの１行目を指定し（ステップS2）、make Z（ステップS3）、次いでをmake L（ステップS4）起動する。これをj=(m-1)まで繰り返し（ステップS5）、H・y=0を確認する（ステップS6）。最終のZRがyである。H・y=0でなく、かつtをカウントアップ（ステップS7）してもトライ回数が最大回数に達していない場合（ステップS8）はステップS2へ戻る。
【００１９】
図２はmake Zの詳細を示す。i=0として検査行列Hの１列目を指定し（ステップS3-1）、検査行列H(j,i)=1なら（ステップS3-2）、Z(i)=ZR(i)-L(j.i)（ステップS3-3）、検査行列H(j,i)=1でないなら（ステップS3-2）、Z(i)=0（ステップS3-4）という処理をi=(m+n-1)まで繰り返す（ステップS3-5,ステップS3-6）。
【００２０】
図３はmake Lの詳細を示す。i=0として検査行列Hの１列目を指定し（ステップS4-1）、検査行列H(j,i)=1なら（ステップS4-2）、L(j,i)=f(Z,i)およびZR(i)=Z(i)+L(j,i)（ステップS4-3）、検査行列H(j,i)=1でないなら（ステップS4-2）、L=0（ステップS4-4）という処理をi=(m+n-1)まで繰り返す（ステップS4-5,ステップS4-6）。
【００２１】
ここで、Z(0)〜Z(i-1)およびZ(i+1)〜Z(m+n-1)の絶対値の内の最小値をa、Z(0)〜Z(i-1)およびZ(i+1)〜Z(m+n-1)の符合の掛け算結果をbとした場合、f(Z,i)=a・bである。
【００２２】
さて、符号化および復号化の時に使用される検査行列Hの例を図４に示す。図４は説明を単純化するために小規模としているが、検査行列Hの行と列は、とても大きいことがあり、図４のように０と１のみで表現するのは、非常に困難となる。そこで、図５のようにブロック化し、図６のように、その１が存在する位置を示す数字をブロックに割り当てることがある。ZRメモリは推定事後確率データを基本的には検査行列Hの列単位に記憶するが、図５のようにブロック化した場合にはブロック単位に記憶する。
【００２３】
図６において、左上隅から右下隅にかけて斜めに規則的に１が並ぶブロックは０、オール０のブロックは−１、その他のブロックは１が割り当てられている。ブロック内の１は規則的に巡回する必要がある。このように表現できる符号をQuasi-Cyclic符号と呼ぶ。また、検査行列の右半分が、図４に示すように、斜めに規則的に１が並ぶ符号をRepeat Accumulate符号と呼び、符号化において有利になるため、一般的に用いられることが多い。
【００２４】
LDPCの復号は、その計算量の多さから、回路への実装はとても難しいとされている。最大の問題点は、図３のステップS4-3におけるZRおよびLの情報を全て記憶する必要があり、この記憶のために多くのメモリを利用しなくてはならないということにある。この多くのメモリとは、多くの個数のメモリを使用するということである。その理由は、ZRおよびLが大量であるためである。例えば、一つの数値の要素を8bit、LDPC(2000,1000)において、1が一行辺り10個存在すると、Lは1000×10×8 = 80000bitのデータを記憶しなくてはならず、これを全てフリップフロップで設計してしまうと、回路規模が膨大となる。
【００２５】
次に、このデータを全て一つのメモリに記憶するとしても、メモリは、１回のアクセスで、データ幅分のデータしかやりとりできない。しかし、図１〜図３までに記したシリアルアルゴリズムのLDPCでは、ステップS4-3において10個のデータをほぼ同時に必要とするため、並列に読み出せるようにメモリを分割する必要がある。
【００２６】
Quasi-Cyclic符号により、ブロック化された場合に列で見ると、最低でもそのブロック分だけメモリが必要となる。もし、例に挙げたLDPC(2000,1000)の符号において、20bit単位でブロック化されたとしても、必要となるメモリは、2000/20=100で100個となり、ASICなどへの実装の妨げとなる。従って、メモリの分割を行わないで、全ての情報を１つのメモリに保存すると、その情報の読出し及び書込み処理をシリアルに行うため処理性能が落ちてしまう。
【００２７】
本発明のLDPC復号回路は、図１６に示したように、ZRメモリに大量のメモリを使用するのではなく、検査行列の特徴から連続してアクセスされない領域を持った列は統合して、図８に示すように、ZRメモリ1-1を構成するメモリの数を減らす。具体的には、図７に示すようなブロック表示の検査行列であった場合、符号部分の列701には常に１があり、パリティ部分702には階段状に１があるので、列701のそれぞれにはメモリもしくはフリップフロップに割り当て、パリティ部分702には１つのメモリを割り当て、符号部分の他の列は全てで他の１つのメモリを割り当てる。なお、図８における「１２」等の数字は、大規模な検査行列に対応して、図６における「−１」等の数字に代わるものであって、20x20の行列のパターンを一意に示している。
【００２８】
本発明により、本来、図７に示すような検査行列では、１２列のため最低でも１２個のメモリが必要となるところを、２個（列701をフリップフロップに割り当てた場合）もしくは４個に減らすことができて、かつ性能を落とすこともない。
【００２９】
図９を参照すると、検査行列とZRメモリ1-1を構成するメモリA〜Dとの対応関係が示されている。図９において、メモリAおよびメモリBは符号部分の内の連続して１が存在している列901に対応するメモリであり、常にアクセスを受けるため高速なメモリもしくはフリップフロップで構成する。メモリCは符号部分の内のランダムに１が存在している列902に対応したメモリ、メモリDは階段状に１が存在しているパリティ部分1003に対応したメモリであり、いずれも通常のメモリで構成する。
【００３０】
図１０，図１１は、図９を詳細化し、メモリA、メモリCと推定事後確率データZRと行列の対応を示している。図１０における単位行列1001は図９における列901を拡大したものである。単位行列1001に対応した推定事後確率データZRは図９に示したイメージのようにメモリAに格納される。同様に、図１１における単位行列1101,1102は図９における列902を拡大したものである。単位行列1101,1102に対応した推定事後確率ZRは、図９に示したイメージのようにメモリCに格納される。このように、メモリCには、複数の列の推定事後確率データZRが格納される。よって、単位行列1101と単位行列1102は読出しが排他的となるように構成されていることが肝要である。
【００３１】
図１２は図９を図１６に対応する形態で示す。メモリCとメモリDは、常に同じ列を実行するわけではなく、制御回路５により指定された列を実行する。メモリDは、階段状の行列部分のデータを割り当てる部分であるが、図９からも分るとおり、一度読み出した推定事後確率データZRは、次の（行に対する）処理で必ず使用されるため、バッファリングしておくことで、メモリアクセスを減らすことができる。Lメモリ２は、メモリA〜メモリDに対応したLの情報を格納する。制御回路５は各ブロック1-1，２〜４を全て制御する。計算回路３は図１〜図３に示した処理を実行する。
【００３２】
図１２により動作について説明する。メモリA〜メモリDには、Yの値が推定事後確率データZRの初期値として格納されている。制御回路５がメモリA〜メモリDおよびLメモリ２に対して、最初の行を読み出す。前述のとおり、これらのメモリに配置されている推定事後確率データZRは、一度のアクセスにより１行分が読み出せるようになっている。また、Lメモリ２に関しては、１行分の情報を一度のアクセスで読み出せるようにデータが配置されているとする。
【００３３】
バッファ４は、前回読み出したメモリDからの推定事後確率データZRを保持するもので、この存在により、メモリDへのアクセスを減らすことが可能となる。横の行を読み出した後、計算回路３により、新しい推定事後確率データZRとLの情報が作成され、再び各メモリに格納される。これを繰り返すことにより、行列の行を最後まで実行し、全ての行の実行が完了した時点で１回の訂正とする。この訂正を数回繰り返すことにより、誤りの訂正を行うことができる。図１３は、４行分の実行により１回の訂正をすることを２回繰り返した場合をタイミングチャートで示している。
【００３４】
なお、その基本的構成は上記の通りであるが、図１４に示すように、図９とは異なる検査行列に対応するタイミングチャートを図１５に示す。図１４において、符号部分の内のランダムに１が存在している列1402において、メモリCは、一度に２個の列の推定事後確率データZRをアクセスされる必要が発生する。このため、図１５において、メモリCの２回の読出しが完了するまで、他のメモリの読出しを待たせる構成としている。
【符号の説明】
【００３５】
１    ZRメモリ
２    Lメモリ
３    計算回路
４    バッファ
５    制御回路
2-1   ZRメモリ
701   符号部分の列
702   パリティ部分
901   符号部分の列
902   符号部分の列
903   パリティ部分
1001  単位行列
1101  単位行列
1102  単位行列
1401  符号部分の列
1402  符号部分の列
1403  単位行列
【図１】
2010268179.tif 000003
【図２】
2010268179.tif 000004
【図３】
2010268179.tif 000005
【図４】
2010268179.tif 000006
【図５】
2010268179.tif 000007
【図６】
2010268179.tif 000008
【図７】
2010268179.tif 000009
【図８】
2010268179.tif 000010
【図９】
2010268179.tif 000011
【図１０】
2010268179.tif 000012
【図１１】
2010268179.tif 000013
【図１２】
2010268179.tif 000014
【図１３】
2010268179.tif 000015
【図１４】
2010268179.tif 000016
【図１５】
2010268179.tif 000017
【図１６】
2010268179.tif 000018