(57)【要約】【課題】擬似巡回LDPC符号のMP復号において、ブロック内並列度を固定した場合でも多様なZに対しても効率よく対応可能な復号器構成を与えること【解決手段】ブロックの先頭S個以下の受信値データを保持し、ブロックの大きさＺがSの倍数でない場合は該ブロックの先頭から（Ｓ−（Ｚ  ｍｏｄ  Ｓ））個のデータをブロックの受信値データの末尾に付加してSの倍数になるようにした上で受信値メモリに書き込む受信値整列手段６０１と、列処理モジュールもしくは行処理モジュールとメッセージメモリの間でブロックのオフセット値に対応した巡回置換をレコード単位で行い、ＺがＳの倍数でない場合には該ブロックの出力の先頭から（Ｓ−（Ｚ  ｍｏｄ  Ｓ））個のメッセージを該ブロックの出力メッセージの末尾に付加してSの倍数になるようにした上でメッセージメモリに出力するメッセージ整列手段６０４、６０７を備えた復号装置６。【選択図】図６
2008069231.tif 000002
【特許請求の範囲】
【請求項１】
同一サイズの巡回置換行列もしくは零行列をブロックとするパリティ検査行列を持つ擬似巡回低密度パリティ検査符号をブロック内における復号並列処理度Ｓで復号するメッセージ・パッシング復号装置において、
ブロックの先頭S個以下の通信路から受信した受信値データを保持し、該ブロックの大きさＺがSの倍数でない場合は該ブロックの先頭から（Ｓ−（Ｚ  ｍｏｄ  Ｓ））個のデータを該ブロックの受信値データの末尾に付加してSの倍数になるようにした上で受信値メモリに書き込む受信値整列手段と、
前記メッセージ・パッシング復号の列処理を行いメッセージを生成するＳ個の列処理手段からなる列処理モジュールと、
前記メッセージ・パッシング復号の行処理を行いメッセージを生成するＳ個の行処理手段からなる行処理モジュールと、
メッセージを格納し、Ｓ個のメッセージを１レコードとして入出力するメッセージメモリと、
前記列処理モジュールもしくは行処理モジュールと前記メッセージメモリの間で前記ブロックのオフセット値に対応した巡回置換を前記レコード単位で行い、ＺがＳの倍数でない場合には該ブロックの出力の先頭から（Ｓ−（Ｚ  ｍｏｄ  Ｓ））個のメッセージを該ブロックの出力メッセージの末尾に付加してSの倍数になるようにした上で前記メッセージメモリに出力するメッセージ整列手段、
を備えたことを特徴とする復号装置。
【請求項２】
請求項１に記載の復号装置において、
前記受信値メモリおよび前記メッセージメモリはそれぞれ複数のメモリデバイスにより構成されることを特徴とする復号装置。
【請求項３】
請求項１に記載の復号装置において、
前記受信値メモリ、前記メッセージメモリ、前記列処理モジュール、前記行処理モジュール、前記メッセージ整列手段を複数のブロックの並列処理に対応してそれぞれ複数個備えたことを特徴とする復号装置。
【請求項４】
請求項１に記載の復号装置において、
前記メッセージ整列手段は連続する２個のレコードからS個のメッセージを選択するメッセージ抽出手段と前記メッセージ抽出手段への入力を制御する複数のレジスタを備えたことを特徴とする復号装置。
【請求項５】
請求項１に記載の復号装置において、
前記巡回置換行列のブロックのサイズＺに応じて前記ブロック内における復号処理並列度Sを決定する並列度決定手段を備えたことを特徴とする復号装置。
【請求項６】
請求項5に記載の復号装置において、
前記並列度決定手段は前記巡回置換行列のサイズＳの1/2以下で、予め決められた復号処理並列度の候補の中で最大の値に復号処理並列度を設定することを特徴とする復号装置。
【請求項７】
請求項4記載の復号装置において、
前記メッセージ抽出手段は、２個の入力レコードに対してそれぞれ独立に動作させることが可能な2個のシフト手段と、前記シフト手段の出力の値を選択するセレクタ群を備えたことを特徴とする復号装置。
【請求項８】
同一サイズの巡回置換行列もしくは零行列をブロックとするパリティ検査行列を持つ擬似巡回低密度パリティ検査符号をブロック内における復号並列処理度Ｓで復号するメッセージ・パッシング復号方法において、
ブロックの先頭S個以下の通信路から受信した受信値データを保持し、該ブロックの大きさＺがSの倍数でない場合は該ブロックの先頭から（Ｓ−（Ｚ  ｍｏｄ  Ｓ））個のデータを該ブロックの受信値データの末尾に付加してSの倍数になるようにした上で受信値メモリに書き込む工程と、
列処理または行処理により生成されたメッセージに対して前記ブロックのオフセット値に対応した巡回置換をＳ個のメッセージから成るレコード単位で行い、ＺがＳの倍数でない場合には該ブロックの出力の先頭から（Ｓ−（Ｚ  ｍｏｄ  Ｓ））個のメッセージを該ブロックの出力メッセージの末尾に付加してSの倍数になるようにした上でメッセージメモリに出力する工程を備えたことを特徴とした復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は誤り訂正符号化および復号処理に関し、特に低密度パリティ検査符号（Low-Density  Parity-Check  Code,  以下、LDPC符号と略す）に対する復号装置に関する。
【背景技術】
【０００２】
誤り訂正符号は符号化、復号という処理によってデータ伝送時に混入するノイズの影響を低減する技術である。符号化は送信するデータに冗長を付加する処理であり、符号化されたデータを符号語と呼ぶ。通信路に送出された符号語はノイズの影響を受けて受信時には符号語の一部のビットが反転するといったエラーが起こる。復号はこのエラーの影響を受けた受信語から冗長を利用してデータを復元する処理である。【０００３】
LDPC符号は１９６０年代に提案された誤り訂正符号であるが、ターボ符号との関連が指摘され、１９９０年代後半になって注目を集めるようになった（例えば、非特許文献１参照）。
誤り訂正符号は推定処理である復号処理が符号化処理に比べて複雑となる。特に、訂正能力の高い大きな符号長の符号で最尤復号、もしくはそれに近い復号性能を得ようとすると一般には非常に複雑度が高い処理となる。
LDPC符号は疎、かつタナーグラフで表現したときに小さなloopの個数が小さいパリティ検査行列を持つ、ということで特徴付けられ、この性質から比較的効率の良い高性能復号法が存在する。この復号方法はメッセージ・パッシング復号（Message-Passing  decoding,  以下、MP復号と略す）と呼ばれている。【０００４】
以下、LDPC符号のMP復号について説明を行う。尚、簡単のために符号はバイナリであり、変調方式はBPSK（Binary  Phase  Shift  Keying）でノイズが0の場合は符号語のビット0に対しては＋１、ビット１には−１という軟判定値が受信値に対応するとする。
LDPC符号のＭＰ復号法はパリティ検査行列の成分’1’に割り当てられた“メッセージ”と呼ばれる量をパリティ検査行列の列に対応する列処理および行に対応する行処理によって反復的に更新することで実行される。メッセージは行処理から列処理へと、列処理から行処理への２種類存在し、それぞれCVメッセージ、VCメッセージと呼ぶ場合もある。【０００５】
図１はLDPC符号のＭＰ復号の模式図である。以下、図１を参照してメッセージ・パッシング復号を説明する。
列iに対応する符号語ビットの受信値をｒ(i)とする。r(i)は対数尤度比で表されているとする。列処理はr(i)とこの列で成分が’1’である行からのCVメッセージを用いて実行される。ここでは列iにおける1の個数（次数と呼ぶ）を3として、成分が1である行をi(0),i(1),i(2)とし、列iへのメッセージをcv(i(0),i)，cv(i(1),i),…,cv(i(2),i)と表す。列iにおける列処理において行i(0)へのメッセージvc(i,i(0))は[式１]で表すことができる。
[式１]  vc(i,i(0))←  r(i)+  cv(i(1),i)+cv(i(2),i)
vc(i,i(1)),vc(i,i(2))についても同様である。【０００６】
一方、行j(次数4とする)において成分が’1’である列をj(0),j(1),j(2),j(3)として、列処理からの行jへのメッセージをvc(j(0),j),…,  vc(j(3),j)としたとき、行jは列j(1)に対して[式２]で表されるcv(j,j(1))を送出する。
[式２]  c(j,j(1))←  F(vc(j(0),j),vc(j(2),j),vc(j(3),j))
ここでFは行処理を表す関数で、sum-productアルゴリズム,  min-sumアルゴリズムといった方式が知られている。min-sumアルゴリズムを[式3]に表す。
[式3]  c(j,j(1))←sgn(vc(j(0),j))sgn(vc(j(2),j))sgn(vc(j(3),j))・min{|vc(j(0),j)|,|vc(j(2),j)|,|vc(j(3),j)|}
ここでsgn(a)はaの正負の符号(+1または-1),  |a|はaの絶対値、minは最小値を選択する関数である。cv(j,j(0)),cv(j,j(2)),cv(j,j(3))についても同様に算出する。
LDPC符号では大きな符号長であっても行、列の次数が小さいため、[式１]、[式２]の処理の複雑度は小さくて済む。【０００７】
すべての列、行に対して一通り[式１]及び[式２]を実行する処理の単位を１  iteration処理と呼ぶことにする。LDPC符号ではこの繰り返し回数は通常１０から１００回程度である。
最終的な０，１の判定（硬判定）は各符号語ビットにおいて、[式４]  の正負を判定することによって行われる。
[式４]  r(i)+cv(i(0),i)+cv(i(1),i)+  cv(i(2),i)
この硬判定結果がすべてのチェックノードを満たした時点、もしくはあらかじめ決められた回数のiterationを終了した後、MP復号は終了する。【０００８】
パリティ検査行列のすべての行、列に対応する行処理、列処理を同時に行うように装置化できれば高速化が期待できるが、LDPC符号は通常長い符号長（1000以上）も使用するため、これは困難となる。そこで、メッセージをメモリに格納し、回路を共有して一部の行、列を並列に動作させて装置複雑度とスループットの調節を図る部分的並列復号が考えられる。LDPC符号の部分的並列復号器実装ではこのメモリへのアクセスが課題となる。【０００９】
高スループット実現のためには、最初からメモリアクセスの容易性が期待できるパリティ検査行列を持つ符号を採用することが望ましい。そのような構造を持つLDPC符号として擬似巡回(quasi-cyclic)LDPC符号が知られている。
擬似巡回LDPC符号の典型的な構成法は同一サイズの巡回置換行列または零行列をブロックとしてパリティ検査行列を構成する方法である。このような構成法から擬似巡回LDPC符号はブロックの大きさを変えることによって同一符号構造で多様な符号長を実現することが可能であり、符号長の柔軟さが求められるモバイルなどのアプリケーションには適している。擬似巡回LDPC符号のパリティ検査行列において巡回置換行列のブロックに対して’1’,零行列に対して’0’を割り当てることで生成される行列をbase  matrixと呼ぶ。Base  matrixのサイズをJ×K,巡回置換行列のブロックのサイズをZとするとパリティ検査行列はJZ×KZの行列となる。図２はJ=2,  K=3,  Z=5の擬似巡回LDPC符号のパリティ検査行列の例である。I(j)はサイズZの単位行列の各行を右にjだけシフトした行列を表す。このjをオフセット値と呼ぶ。【００１０】
オフセット値はMP復号において列処理モジュールと行処理モジュールの間のメッセージの順序の入れ替えを指定する。例えば図２のパリティ検査行列Ｈ(Z  =  5)における上段の中のブロックに対応するVCメッセージがa(0),  a(1),  a(2),  a(3),  a(4)であったとする。このときブロックのオフセット値1に基づいてa(1),  a(2),  a(3),  a(4),  a(0)と順序を入れ替えることでこれらのメッセージを行ブロックにおける先頭の行から順に対応させることができる。【００１１】
擬似巡回LDPC符号の部分的復号処理ではパリティ検査行列の巡回置換行列のブロックを列処理および行処理において何個並列に処理するかという“列ブロック並列度”および”行ブロック並列度”と、ブロックにおいて同時に処理をする列処理または行処理の個数である“ブロック内並列度”の積が全体の並列度の指標となる。本発明で注目するのは後者のブロック内並列度である。図３はパリティ検査行列におけるブロックのサイズZとブロック内並列度Sの関係を示している。巡回置換行列に対応するブロックにはZ個のメッセージが対応しており、ブロック内並列度Sを実現するためにはZ個のメッセージの入出力をS個単位のレコードで行う必要がある。つまり、VCメッセージa(0),a(1),..,a(Z-1)に対して、オフセット値jであったらa(j),  a(j+1),..,a(Z-1),a(0),...,a(j-1)の順序への変更をS個単位の入出力で効率よく行わなければならない。【００１２】
最も簡明な場合はS  =  Zのときで、これは特許文献１に記されている。
図４は特許文献１の方式を示す。図４(a)はパリティ検査行列を、図４(b)はS=Z=6の場合のメモリフォーマットを、図４(c)は復号装置構成を表している。図４(b)でa(0),..,a(5)が一つのブロックに対応する受信値もしくはCVメッセージのフォーマットを表していて、一つのレコードを成している。図４(c)で受信値メモリ400、VCメッセージメモリ403,  CVメッセージメモリ405はともにサイズZのレコード単位で入出力を行う。1列ブロックまたは1行ブロックに対して列処理または行処理を行うプロセッサもそれぞれZ個用意し、列処理モジュール401および行処理モジュール406を構成する。vcメッセージメモリ403と列処理モジュール401の間には巡回置換手段404を設けオフセット値に基づいて巡回置換を行い、列方向の順序であるメッセージを行方向の順序に並び替える。このオフセット値は検査行列ROM407および制御手段408で設定される。巡回置換手段404は巡回置換手段402の逆変換を行う。【００１３】
特許文献１の方式は非常に直接的な方式であるが、ブロック内並列度SがブロックサイズZに一致する場合のみ動作する方式である。ZがSよりも大きくかつSの倍数という条件の下では特許文献２および非特許文献2に記載されている方式が自然に適用できる。図５(a)はパリティ検査行列を、図5(b)はZ=18,  S=6に対するメモリフォーマットを、図５(c)は列処理モジュールとVCメッセージメモリの間でメッセージの順序を入れ替えるメッセージ整列手段の構成図を表している。この方式は連続する2レコードから1レコードを切り出すことでレコード単位の入出力で大きさZの巡回置換処理を実現する。レジスタ501には1時点前に入力されたレコードを格納し、シフト手段503で現在の入力レコードと連結、シフトして先頭のS個のデータ（レコード）を取り出す。オフセット値jに対してj  mod  Sがシフト値に対応する。レジスタ500はブロックにおける最初の入力レコードを格納しておき、ブロックの最後の入力レコードと併せて最終出力のレコードを完成させる。【００１４】
【特許文献１】特表2004-531972号公報
【特許文献２】米国特許出願公開第2004/0034828号明細書
【非特許文献１】D.J.C.Macky  及び  R.M.Neal、“Good  error  correcting  codes  based  on  very  sparse  matrices”、米国、IEEE  Transactions  on  Information  Theory、45巻、２号、pp.399-431、１９９９年３月
【非特許文献２】Y.  Chen  及びD.  Hocevar、“A  FPGA  and  ASIC  Implementation  of  Rate  1/2,  8088b  Irregular  Low  Density  Parity  Check  Decoder”、米国、IEEE、Globecom2003、pp.113-117、２００３年
【発明の開示】
【発明が解決しようとする課題】
【００１５】
モバイル通信などの用途では符号長の自由度が求められ、非常に多くのブロックサイズZに対応する必要がある。ここでZがSの倍数でない場合にはブロックの最終レコードは完備にはならない。たとえば図5(c)でZ=16の場合はブロックの最終レコードのデータはa(12)  a(13)  a(14)  a(15)までで残りのa(16),  a(17)のスペースは不定となる。非特許文献2ではこのときこの残りの部分にはダミーデータを設定し、この最終レコードの前後で制御を注意深く行えば対応可能と述べている。しかし、例えばa(11),a(12),a(13),a(14),a(15),a(0)というレコードを取り出す場合、連続する2個のレコード(a(6),…,a(11))と(a(12),a(13),a(14),a(15),?,?)からこのレコードを生成することができないため、図5の(c)の装置では対応することができない。もちろん3個のレコードから出力を生成することは可能であるが、これは装置の複雑度増大につながる。また、モバイル適用時などZが可変であり、2Sより小さいZが設定された場合にはZ/2のブロック内並列度で処理を行うことが考えられるが、図5(c)のシフト手段ではこれに対応することができない。【００１６】
本発明の目的は擬似巡回LDPC符号のMP復号において、ブロック内並列度を固定した場合でも多様なZに対しても効率よく対応可能な復号器構成を与えることである。
【課題を解決するための手段】
【００１７】
本発明の復号装置は、同一サイズの巡回置換行列もしくは零行列をブロックとするパリティ検査行列を持つ擬似巡回低密度パリティ検査符号をブロック内における復号並列処理度Ｓで復号するメッセージ・パッシング復号装置であり、ブロックの先頭S個以下の通信路から受信した受信値データを保持し、該ブロックの大きさＺがSの倍数でない場合は該ブロックの先頭から（Ｓ−（Ｚ  ｍｏｄ  Ｓ））個のデータを該ブロックの受信値データの末尾に付加してSの倍数になるようにした上で受信値メモリに書き込む受信値整列手段と、メッセージ・パッシング復号の列処理を行いメッセージを生成するＳ個の列処理手段からなる列処理モジュールと、メッセージ・パッシング復号の行処理を行いメッセージを生成するＳ個の行処理手段からなる行処理モジュールと、メッセージを格納し、Ｓ個のメッセージを１レコードとして入出力するメッセージメモリと、列処理モジュールもしくは行処理モジュールとメッセージメモリの間でブロックのオフセット値に対応した巡回置換をレコード単位で行い、ＺがＳの倍数でない場合には該ブロックの出力の先頭から（Ｓ−（Ｚ  ｍｏｄ  Ｓ））個のメッセージを該ブロックの出力メッセージの末尾に付加してSの倍数になるようにした上でメッセージメモリに出力するメッセージ整列手段を備えている（請求項１ないし請求項７）。【００１８】
上記復号装置によれば、受信値整列手段とメッセージ整列手段は、パリティ検査行列のブロックのサイズZがブロック内の並列処理度Sの倍数でない場合でも巡回的に先頭メッセージを付加してレコードを生成するために常に連続する2個のレコードから出力レコードを生成することができる。
そのため、巡回置換行列のブロックの大きさZがブロック内並列度Sの倍数でない場合でも、列処理と行処理のモジュール間でのメッセージの順序の変更が効率よく行うことができる。【００１９】
上記復号装置において、受信値メモリおよびメッセージメモリはそれぞれ複数のメモリデバイスにより構成されるようにしてもよい（請求項２）。【００２０】
上記復号装置において、受信値メモリ、メッセージメモリ、列処理モジュール、行処理モジュール、メッセージ整列手段を複数のブロックの並列処理に対応してそれぞれ複数個備えるようにしてもよい（請求項３）。【００２１】
上記復号装置において、メッセージ整列手段は連続する２個のレコードからS個のメッセージを選択するメッセージ抽出手段とメッセージ抽出手段への入力を制御する複数のレジスタを備えるようにしてもよい（請求項４）。【００２２】
上記復号装置において、巡回置換行列のブロックのサイズＺに応じてブロック内における復号処理並列度Sを決定する並列度決定手段を備えるようにしてもよい（請求項５）。【００２３】
上記復号装置において、並列度決定手段は巡回置換行列のサイズＳの1/2以下で、予め決められた復号処理並列度の候補の中で最大の値に復号処理並列度を設定するようにしてもよい（請求項６）。【００２４】
上記復号装置において、メッセージ抽出手段は２個の入力レコードに対してそれぞれ独立に動作させることが可能な2個のシフト手段と、シフト手段の出力の値を選択するセレクタ群を備えるようにしてもよい（請求項７）。【００２５】
本発明の復号方法は、同一サイズの巡回置換行列もしくは零行列をブロックとするパリティ検査行列を持つ擬似巡回低密度パリティ検査符号をブロック内における復号並列処理度Ｓで復号するメッセージ・パッシング復号方法であり、ブロックの先頭S個以下の通信路から受信した受信値データを保持し、該ブロックの大きさＺがSの倍数でない場合は該ブロックの先頭から（Ｓ−（Ｚ  ｍｏｄ  Ｓ））個のデータを該ブロックの受信値データの末尾に付加してSの倍数になるようにした上で受信値メモリに書き込む工程と、列処理または行処理により生成されたメッセージに対してブロックのオフセット値に対応した巡回置換をＳ個のメッセージから成るレコード単位で行い、ＺがＳの倍数でない場合には該ブロックの出力の先頭から（Ｓ−（Ｚ  ｍｏｄ  Ｓ））個のメッセージを該ブロックの出力メッセージの末尾に付加してSの倍数になるようにした上でメッセージメモリに出力する工程を備えている（請求項８）。【００２６】
上記復号方法によれば、パリティ検査行列のブロックのサイズZがブロック内の並列処理度Sの倍数でない場合でも受信値データとメッセージに巡回的に先頭メッセージを付加してレコードを生成するために常に連続する2個のレコードから出力レコードを生成することができる。
そのため、巡回置換行列のブロックの大きさZがブロック内並列度Sの倍数でない場合でも、列処理と行処理のモジュール間でのメッセージの順序の変更が効率よく行うことができる。
【発明の効果】
【００２７】
本発明の効果は巡回置換行列のブロックの大きさZがブロック内並列度Sの倍数でない場合でも、列処理と行処理のモジュール間でのメッセージの順序の変更を効率よく行うことができることである。これはZがSの倍数でない場合でも巡回的に先頭メッセージを付加してレコードを生成するために常に連続する2個のレコードから出力レコードを生成可能なことに起因する。
【発明を実施するための最良の形態】
【００２８】
以下、図を参照しながら本発明の一実施形態である復号装置6の構成と動作について説明する。
図６は復号装置6のブロック図である。図６において、検査行列ROM600は擬似巡回LDPC符号のパリティ検査行列のブロックである巡回置換行列のオフセット値情報を保持している。【００２９】
制御手段610は検査行列ROM600に格納されているオフセット値をメッセージ整列手段604,607に設定する。パリティ検査行列のすべてのブロックをパラレルに処理する列ブロック並列度、行ブロック並列度の場合には、検査行列ROM600および制御手段610からの情報は予め各モジュールに設定されているため、検査行列ROM600およびオフセット値のメッセージ整列手段604,607への設定処理は、必要ない場合もある。【００３０】
受信値整列手段601は受信データをブロック毎にS個のレコード単位にして受信値メモリ602に書き込む。ZがSの倍数ではない場合には、最終レコードに巡回的にブロックの先頭データを付加して大きさSのレコードを生成する。【００３１】
受信値メモリ602は、列ブロック並列度に対応した個数のメモリブロックで構成され、受信値メモリ602には、それぞれSの大きさの単位のレコードで入出力が行われる。Sが大きい場合は、複数のメモリデバイスを用いて1ブロックに対する受信値メモリ602が構成されることもある。【００３２】
列処理モジュール603はMP復号の複数の列処理手段から成り、各ブロックの処理では、受信値メモリ602,  CVメッセージメモリ608からS個単位のレコードで順にデータを読み込み、行処理へのメッセージをS個単位のレコードとして生成する。1列ブロックに対してS個の列処理手段を1つの処理単位として、これを復号器における列ブロック並列度に応じた個数分用意する。【００３３】
メッセージ整列手段604はVCメッセージを巡回置換行列のブロックのオフセット値の列番号から始まる順序に並び替える処理をS個単位のレコードでの入出力で行う。このブロックの並び替え後の最終レコードは先頭メッセージを巡回的に付加して大きさSのレコードを生成して出力する。メッセージ整列手段604は同時にメッセージが更新されるブロックの個数分用意する。【００３４】
VCメッセージメモリ605は、パリティ検査行列の巡回置換行列のブロック単位でVCメッセージを保持する。VCメッセージメモリ605もS個のデータを1レコードとして入出力を行う。ZがSの倍数でないときには、最終レコードはブロックの先頭データを付加して大きさSのレコードとして保持する。VCメッセージメモリ605は、メッセージ整列手段604の個数と同一のメモリブロックで構成される。VCメッセージメモリ605は、受信値メモリ602と同様に複数のメモリデバイスで構成されることがある。【００３５】
行処理モジュール606はVCメッセージメモリからデータを読み込み、CVメッセージを生成する。行処理モジュール606は1行ブロックに対してS個の列処理手段を単位として、これを行ブロック並列度分用意する。【００３６】
メッセージ整列手段607はメッセージ整列手段604の逆変換を行う回路であり、行方向のメッセージの順序を列方向の順序に並び替える処理を行う。メッセージ整列手段607は、このブロックの並び替え後の最終レコードとして先頭メッセージを巡回的に付加して大きさSのレコードを生成して出力する。メッセージ整列手段607は同時にメッセージが更新されるブロックの個数分用意する。【００３７】
CVメッセージメモリ608はCVメッセージを保持する。CVメッセージメモリ608は、S個のデータを1レコードとして入出力を行い、ZがSの倍数でないときには最終レコードはブロックの先頭データを付加して大きさSのレコードとして保持する。CVメッセージメモリ608は、メッセージ整列手段607の個数と同一のメモリブロックで構成される。CVメッセージメモリ605は、受信値メモリ602と同様に複数のメモリデバイスで構成されることがある。【００３８】
出力メモリ609は[式３]に基づき判定した硬判定値を保持し、出力を行う。【００３９】
図７は本発明の受信値整列手段601の構成を表している。パリティ検査行列の巡回置換行列のブロックの大きさZがSの倍数でない場合には、ブロックの先頭の(S−(Z  Mod  S)個（ここでZ  Mod  SはZのSを法とした値で、1以上S以下の代表系でとる）のデータを一時格納手段700に保持しておき、これを最後に付加してブロックの最終レコードとする。これに付随する遅延が発生するため、一時格納手段701,セレクタ703,レジスタ705と二重化して装置を構成し、スイッチ706,セレクタ707で切り替えることでこれに対処する。【００４０】
メッセージ整列手段604における処理は2個の連続するレコードから1個のレコードを取り出すメッセージ抽出処理と、この連続する2個のレコードを生成する処理およびこれらの制御をオフセット値に基づいて行うメッセージ供給処理に大きく分けられる。
またメッセージ整列手段604はMP復号の行処理、列処理のスケジューリングによっても構成が異なる場合があり、大きく次の２種類に分けられる：
(A)  1ブロックの列処理、メッセージ整列処理がすべて終了した後、そのブロックの行処理を開始する。
(B)  S個ずつの行処理を逐次行えるように列処理、行処理を実行する。
(B)は行処理で更新したメッセージをそのiteration内で即時に利用するシリアル復号処理もしくはレイヤード復号処理と呼ばれる方式で必要となる。このようなスケジューリングはメッセージの更新速度を高め、繰り返し復号の収束の高速化を図ることができるが、制御が複雑になるという欠点がある。【００４１】
図８は前記処理(A)を実現するためのメッセージ整列手段604,607の構成を表している。制御手段800はオフセット値に基づきレジスタ802,803,804およびセレクタ807,808,809を制御してメッセージ抽出手段801に連続する2レコードを供給する。レジスタ804はブロックにおける先頭の入力データを格納しておき、ブロックにおける最後の出力レコード生成に利用する。メッセージ抽出手段801は制御手段800の指示に基づき2レコード、つまり2S個のメッセージからS個のメッセージを取り出し、出力する。制御手段800は出力されたレコードを書き込むCVメッセージメモリ605またはVCメッセージメモリ608のアドレス（＝レコード番号（ブロック内相対値））も出力する。【００４２】
図９は前記処理(B)を実現するためのメッセージ整列手段604,607の構成を表している。前記処理(A)との相違点はオフセット値に合わせて入力データの順序も調節するため、ブロック内の処理の途中においても、順序が連続とならない、より正確にはメッセージの重複が存在する最終レコードと先頭レコードが入力レコードとなることである。このようなメッセージの並びのギャップがあっても連続的に出力を生成できるようにするため、レジスタ902,  903にはそれぞれ2時点前、1時点前の入力レコードを保持しておき、最初はこの連続する2レコードを用いてメッセージ抽出手段901は出力を生成する。また、レジスタ904,905にはブロックの先頭の2個の入力レコードを保持しておく。図9のメッセージ整列手段では図8と比較して出力が開始されるのが1時点遅くなるが、このような注意深い制御を行うことで任意のオフセット値に対してメッセージ抽出手段に出力生成可能な連続的に入力レコードを設定し、出力レコードを生成することが可能になる。【００４３】
図10は本発明の実施形態においてブロックサイズZが可変で、ブロック内並列度SをZに応じて適応的に変更することを可能にする並列度適応設定手段1003である。ブロックサイズＺが可変である場合には、図６の検査行列ROM600,制御手段610に代わって図10の並列度適応設定手段1003を設ける。
並列度決定手段1000はブロックサイズZに応じてブロック内並列度Sを決定する。制御手段1001は検査行列ROM1002とZからブロックサイズZに対するオフセット値を決定する。制御手段1001はこのZ,  Sおよびオフセット値によって受信値整列手段601およびメッセージ整列手段604,607を制御し、復号処理を実行する。
【実施形態１】
【００４４】
以下、復号装置６について、具体例を用いて説明する。図１１は本発明の実施形態１における受信値メモリ602のフォーマット例である。図１１(a)はZ  =  15,  S  =  6の場合であり、ブロックの受信値データをa(0),  a(1),  …,  a(14)と表している。このとき受信値整列手段601はブロックにおける最終レコードを（a(12),  a(13),  a(14),  a(0),  a(1),  a(2)）と先頭部分を付加してSの倍数となるようにして書き込む。CVメッセージメモリ608も同様のフォーマットとなる。
図１１(b)は図１１(a)に対して、オフセット値j=9の場合のVCメッセージメモリ605におけるメッセージのフォーマットである。最終レコードは巡回的にa(9),  a(10),  a(11)を付加した形となる。
【００４５】
並列度決定手段1000は並列度SとブロックサイズZに応じてブロック内並列度を決定する。この際、典型的にはZ/2,もしくはそれ以下で予め決められた値の中での最大値に設定する。図11(c)はZ=7でS=3（S max＝６）の場合の受信値メモリ602のフォーマットである。実装的にはSは2の冪にすることが簡易化のためには効果的である。
【００４６】
次に、復号装置６の動作について具体例（S=5,  Z=12）を用いて説明する。
図7の受信値整列手段601で、ある列ブロックに対する受信データがa(0),…,a(11)であるとする。受信データはレジスタ704にS  =  5個のデータを保持する毎に受信値メモリ602に書き込まれる。一時格納手段700は(S  -  (Z  Mod  S)  )  =  3個の先頭データ  a(0),  a(1),  a(2)を保持する。ここで、Mod  SはSを法とした値で1からSまでの値を表す。最終レコードではレジスタ704にはa(10),  a(11)のデータが保持されるが、一時格納手段700のa(0),  a(1),  a(2)を付加した後に受信値メモリ602に書き込む。その間の次の列ブロックに対応する入力データはレジスタ705および一時格納手段701に格納し、これらを交互に利用することで巡回的にデータを補充した形でのS個単位のレコードを実現する。
【００４７】
次に図8のメッセージ整列手段604の具体的な動作例を説明する。
列処理モジュール603ではブロックに対するVCメッセージはZ=12,  S=5では
R_0  =  (0,  1,  2,  3,  4)    R_1  =  (5,  6,  7,  8,  9)    R_2  =  (10,  11,  0,  1,  2)
の順序で生成される(数字はメッセージのブロック内での列方向のインデックスを示す)。この入力に対してメッセージ整列手段604ではj  =  3の場合ならば
T_0  =  (3,  4,  5,  6,  7)    T_1  =  (8,  9,  10,  11,  0)    T_2  =  (1,  2,  3,  4,  5)
という3個のレコードを生成、出力する（出力順序は問わず）。図12(a)は図8の回路を用いてこれを実現するときのタイムチャートを示している。
【００４８】
1ブロックにおけるレコード数をeとする(e  =  [(Z  +  S−1)/S],  Z  は2S以上,  [x]はxの整数部分を表す)。レジスタ802は一時点前の入力レコードR_(t-1)を保持しており、これと現在の入力レコードR_tの2個のレコードから出力を生成する。ただしZ,  Sおよびjが条件
[式５]    (Z  Mod  S)  <  (j  mod  S)
を満たし、かつt-1=[j/S]の場合には出力側の最終レコードT_(e-1)とjから始まる先頭のレコードT_0はともにR_(t-1)とR_tから生成される。そこで、メッセージ抽出手段801でT_(e-1)を取り出した後、レジスタ802はホールド、レジスタ803はR_tを保持し、メッセージ抽出手段801は次のサイクルでR_(t-1)とR_tからT_0を生成するように制御する。このときレジスタ802にはレジスタ803の値が格納され、レジスタ803には入力レコードが格納される。[式５]をギャップ発生条件、この処理をギャップ処理と呼ぶことにする。図１２(a)は、メッセージ整列手段タイムチャート（ｊ=3）であって、サイクル1,  2はギャップ処理の具体例である。図１２(a)のサイクル3での処理からわかるように、(10,  11,  0,  1,  2)と最終レコードに巡回的にデータを付加しておくことで連続する2レコードのみから出力レコードを生成することが可能となる。
【００４９】
ギャップ処理が発生しない場合（つまり(Z  Mod  S)が(j  mod  S)以上の場合）、最終レコードR_(e-1)が入力された時点でレジスタ804の先頭レコードR_0をレジスタ803に移動する。次のステップでレジスタ802のR_(e-1)とレジスタ803のR_0をメッセージ抽出手段801の入力とし、最終の出力レコードを生成する。図12(b)は、メッセージ整列手段タイムチャート（ｊ=11）であって、サイクル3はこの処理の具体例である。Z  Mod  SがS(ZはSの倍数)もしくはS-1の場合には[式５]は成り立たず、従来の処理と同様になる。
図８のメッセージ整列手段において、制御手段800で生成される出力データのアドレスの初期値は
[式６]    (e−[(j  +  (S  −  Z  Mod  S))/  S])  mod  e  
で与えることができ、それ以降のアドレスはeを法として1インクリメントすることで得ることができる。
【００５０】
図13は図9のメッセージ整列手段601におけるタイムチャートの例である。図8のメッセージ整列手段601との相違点はT_0,  T_1,  …の順序でレコードを生成することであり、列処理モジュールで生成するメッセージの順序もそれに合わせる必要がある。この際、列処理モジュールではオフセット値jに対してi  =  [j  /  S]のレコードR_iから順にR_(i+1),..,R_(e-1),R_0,..,R_(i-1)とメッセージを生成し、メッセージ整列手段604に供給する。
【００５１】
レジスタ902,  903には現在の入力レコードR_tに対してそれぞれ2時点前の入力レコードR_(t-2)と1時点前の入力レコードR_(t-1)を保持している。メッセージ抽出手段901はR_(t-2)とR_(t-1)から出力レコードを取り出す。ただし、[式4]のギャップ発生条件が成り立つZ,  S,  ｊの設定で、入力レコードがR_0,  レジスタ902,  903がR_(e-2),  R_(e-1)の場合には次の出力はR_(e-1)とR_0の2レコードではなく、R_0とR_1から生成する必要がある。図9の構成では出力までに1時点分余計に遅延を持たせているためこれに対応が可能で、このときレジスタ902には入力レコードR_0を書き込み、これ以降、レジスタ902は1時点前の入力レコードを保持し、現在の入力レコードと併せてメッセージ抽出手段901の入力となるよう制御を変更する。この処理を図８の場合と同様ギャップ処理と呼ぶ。列処理モジュールからの最終レコードの入力後はレジスタ904,  905で格納しておいたブロックの先頭レコードを入力レコードとして扱う。
【００５２】
図9におけるギャップ処理を図13(a)の具体例を用いて説明する。図13(a)はZ  =  12,  S  =  5,  j  =  9であり[式５]のギャップ条件が成り立つ。[j/S]=1のためメッセージ整列手段へはR_1,  R_2,  R_0の順でメッセージのレコードが供給される。レジスタ904,905へはR_1,  R_2が順に格納される。サイクル2の時点ではレジスタ902,  903にはR_1,  R_2が格納されており、入力レコードがR_0である（e  =  3）。このとき出力レコードはT_0  =  (9,  10,  11,  0,  1,  2)であるが、次の出力T_1  =  (3,  4,  5,  6,7)はR_2とR_0ではなく、R_0とR_1から生成することが可能となる。上記の説明した図9の動作では、このときレジスタ902には入力レコードであるR_0を保持するため、サイクル3でのメッセージ抽出手段901へ供給されるデータはこのR_0とレジスタ904に格納されているR_1となり、メッセージ抽出手段901ではT_1を取り出すことが可能になる。また、サイクル2での処理からわかるように、(10,  11,  0,  1,  2)と最終レコードに巡回的に先頭データを付加しておくことで連続する2レコードのみから出力レコードを生成することがここでも可能となっている。
【００５３】
図13(b)は[式５]のギャップ条件が成り立たない場合（Z=12,  S=5,  j=11）の図9のメッセージ整列手段のタイムチャートの具体例を示している。特にZ  Mod  SがSもしくはS-1の場合には任意のjに対して常にギャップ条件は成り立たないため、遅延を1時点減らすことが可能となる。
【００５４】
図１４は図8、図9のメッセージ抽出手段801,901の構成例で、左シフト手段1400,  右シフト手段1401およびセレクタ群1402で構成される。制御手段800,  900は左シフト手段1400,右シフト手段1401それぞれのシフト値およびセレクタ群1402の選択パターンを逐次変更することで所望のメッセージ抽出を行う。
【００５５】
図１２を用いて図１４のメッセージ抽出手段801,901の動作の具体例を説明する。図１２(a)のサイクル2において左シフト手段1400への入力レコードは(0,  1,  2,  3,  4),  右シフト手段1401への入力レコードは(5,  6,  7,  8,  9)である。このとき左シフト手段1400は1シフト、右シフト手段14001は4シフトを行い、セレクタ群1402は左から[0,0,0,0,1]というパターンで選択を行う（'0’は左シフト手段1400からの入力を選択することを表し、’1’は右シフト手段1401からの入力を選択することを表す）。これによって(1,  2,  3,  4,  5)のレコードを抽出することができる。ギャップ処理があった場合には制御の変更が生じて図１２(a)でサイクル3以降では左シフト手段1400,  右シフト手段1401のシフト値はそれぞれ3,  2,  セレクタ群1402の選択パターンは[0,0,1,1,1,]となる。
【００５６】
Zが2Sより小さいときは図１０の並列度選択手段で決定されたブロック内並列度S_0が設定される。大きさSのレコードのうちの先頭のS_0個のみにメッセージは格納される状態になる。図１４のメッセージ抽出手段は入力となる2レコードに対して個別にシフト処理を行い、それぞれの同一ポジションの出力に対して選択処理を行っているため、このようにS_0  <  Sの場合でも処理の変更なく対応可能である。
【００５７】
復号装置6によれば、受信値整列手段601とメッセージ整列手段604、607は、パリティ検査行列のブロックのサイズZがブロック内の並列処理度Sの倍数でない場合でも巡回的に先頭メッセージを付加してレコードを生成するために常に連続する2個のレコードから出力レコードを生成することができる。
そのため、巡回置換行列のZがSの倍数でない場合でも、列処理モジュール603と行処理モジュール606間でのメッセージの順序の変更を効率よく行うことができる。この付加部分に関しては列処理および行処理を二重に行うことになるが、ZがSに比して大きければそのオーバーヘッドは小さい。
【００５８】
以上、実施形態（及び実施例）を参照して本願発明を説明したが、本願発明は上記実施形態（及び実施例）に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【００５９】
この出願は２００６年１２月７日に出願された日本出願特願２００６−３３０９２４を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【００６０】
本発明によって高い符号長自由度の要求されるモバイル通信などへのLDPC符号適用が可能となる。
【図面の簡単な説明】
【００６１】
【図１】ＬＤＰＣ符号の復号処理を説明する図である。
【図２】ＬＤＰＣ符号におけるパリティ検査行列を説明する図である。
【図３】ブロックのサイズとブロックない並列度の関係を示す図である。
【図４】図４（ａ）は、パリティ検査行列の一例を示す図である。図４（ｂ）は、メモリフォーマットの一例を示す図である。図４（ｃ）は、従来の復号装置の構成図である。
【図５】図５（ａ）は、パリティ検査行列の一例を示す図である。図５（ｂ）は、メモリフォーマットの一例を示す図である。図５（ｃ）は、従来のメッセージ整列手段の構成図である。
【図６】本発明の一実施形態である復号装置の構成図である。
【図７】受信値整列手段の構成図である。
【図８】メッセージ整列手段の構成図である。
【図９】メッセージ整列手段の構成図である。
【図１０】並列度適応設定手段の構成図である。
【図１１】図１１（ａ）、図１１（ｂ）、図１１（ｃ）は、受信値メモリのフォーマット例を示す図である。
【図１２】図１２（ａ）、図１２（ｂ）は、メッセージ整列手段のタイムチャートを示す図である。
【図１３】図１３（ａ）、図１３（ｂ）は、メッセージ整列手段のタイムチャートを示す図である。
【図１４】メッセージ抽出手段の構成図である。
【符号の説明】
【００６２】
６  復号装置
６００  検査行列ＲＯＭ
６０１  受信値整列手段
６０２  受信値メモリ
６０３  列処理モジュール
６０４、６０７  メッセージ整列手段
６０５  ＶＣメッセージメモリ
６０６  行処理モジュール
６０８  ＣＶメッセージメモリ
６０９  出力メモリ
６１０  制御手段
７００、７０１  一時格納手段
７０４、７０５  レジスタ
８００  制御手段
８０１  メッセージ抽出手段
８０７、８０８、８０９  レジスタ
９００  制御手段
９０１  メッセージ抽出手段
９０３、９０４、９０５、９０７、９０８  レジスタ
１０００  並列度決定回路
１００１  制御手段
１００２  検査行列ＲＯＭ
【図１】
2008069231.tif 000003
【図２】
2008069231.tif 000004
【図３】
2008069231.tif 000005
【図４】
2008069231.tif 000006
【図５】
2008069231.tif 000007
【図６】
2008069231.tif 000008
【図７】
2008069231.tif 000009
【図８】
2008069231.tif 000010
【図９】
2008069231.tif 000011
【図１０】
2008069231.tif 000012
【図１１】
2008069231.tif 000013
【図１２】
2008069231.tif 000014
【図１３】
2008069231.tif 000015
【図１４】
2008069231.tif 000016
【国際調査報告】
2008069231.tif 000017
2008069231.tif 000018