(57)【要約】【課題】処理速度の早い復号装置１００を提供する【解決手段】多元ＬＤＰＣ符号を用いて符号化されたデータを復号処理する復号装置１００であって、対数フーリエ変換処理部１０１と、変数ノード処理部１０４と、エッジ係数処理部１０６と、検査ノード処理部１０７と、を具備し、対数フーリエ変換処理部１０１が、符号化フレームデータのシンボルの確率ベクトルに対してフーリエ変換処理および対数値化処理を施し、対数フーリエ領域確率ベクトルの初期値を出力し、変数ノード処理部１０４と、エッジ係数処理部１０６と、検査ノード処理部１０７と、が対数フーリエ領域確率ベクトルを用いて、イタレーション処理を行う。【選択図】図３
2011119857.tif 000002
【特許請求の範囲】
【請求項１】
多元低密度パリティ検査符号を用いて符号化された符号化フレームデータを復号処理する復号装置であって、
前記符号化フレームデータのシンボルの確率ベクトルに対して、フーリエ変換処理および対数値化処理を施し、対数フーリエ領域確率ベクトルの初期値を出力する対数フーリエ変換処理部と、
前記対数フーリエ領域確率ベクトルの初期値とエッジ係数処理部から出力される第４のメッセージとを用いた畳み込み演算による変数ノード処理を実行し、第１のメッセージを算出するとともに対数フーリエ領域確率ベクトルを更新し、出力する変数ノード処理部と、
前記第１のメッセージに対してエッジ係数処理を実行し、第２のメッセージを算出するとともに、検査ノード処理部から入力される第３のメッセージに対してエッジ逆係数処理を実行し前記第４のメッセージを算出する前記エッジ係数処理部と、
前記第２のメッセージに対して加算演算による検査ノード処理を実行し、前記第３のメッセージを算出する前記検査ノード処理部と、
を備えたことを特徴とする復号装置。
【請求項２】
前記対数フーリエ領域確率ベクトルの基底ベクトルの符号判定により硬判定を行う硬判定部を、さらに具備することを特徴とする請求項１に記載の復号装置。
【請求項３】
前記第３のメッセージの総和ベクトルの基底ベクトルの符号判定を行うことでパリティ検査を行うパリティ検査部、を有することを特徴とする請求項１または請求項２に記載の復号装置。
【請求項４】
多元低密度パリティ検査符号を用いて符号化された符号化フレームデータを復号処理する復号方法であって、
対数フーリエ変換処理工程と、変数ノード処理工程と、エッジ係数処理工程と、検査ノード処理工程と、を具備し、
前記対数フーリエ変換処理工程が、前記符号化フレームデータのシンボルの確率ベクトルに対して、フーリエ変換処理および対数化処理を施し、対数フーリエ領域確率ベクトルの初期値を算出する処理工程であり、
前記変数ノード処理工程が、前記対数フーリエ領域確率ベクトルと前記検査ノード処理部から出力される第４のメッセージとを用いた畳み込み演算による変数ノード処理を実行し、第１のメッセージを算出するとともに前記対数フーリエ領域確率ベクトルを更新する処理工程であり、
前記エッジ係数処理工程が、前記第１のメッセージに対してエッジ係数処理を実行し、第２のメッセージを算出するとともに、第３のメッセージに対してエッジ逆係数処理を実行し前記第４のメッセージを算出する処理工程であり、
前記検査ノード処理工程が、前記第２のメッセージに対して、加算演算による検査ノード処理を実行し、前記第３のメッセージを算出する処理工程であることを特徴とする復号方法。
【請求項５】
前記対数フーリエ領域確率ベクトルの基底ベクトルの符号判定により硬判定を行う硬判定工程をさらに具備することを特徴とする請求項４に記載の復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、誤り訂正符号により符号化されたデータを復号する復号装置および復号方法に関し、特に、多元ＬＤＰＣ符号により符号化されたデータを復号する復号装置および復号方法に関する。
【背景技術】
【０００２】
近年、誤り訂正符号として、符号性能の理論的限界であるシャノン限界に迫る優れた性能が報告されているＬＤＰＣ符号(Low Density Parity Check codes）が、携帯電話および無線ＬＡＮ等に使用されている。携帯電話等に使用されているＬＤＰＣは２元ＬＤＰＣ符号であるが、ガロア拡大体上で構成した多元ＬＤＰＣ符号は、数百ビットから数千ビットといった１万ビット以下の短い符号長に対して２元ＬＤＰＣ符号をしのぐ高い復号性能を持つことが知られている。特に、多元ＬＤＰＣ符号化データは、並列計算が可能なＳＵＭ−ＰＲＯＤＵＣＴアルゴリズム（ＳＰＡ）を用いることにより効率的に復号処理が可能である。
【０００３】
ＳＰＡ復号処理では変数ノード（variable node）における乗算処理と検査ノード（check node）における畳み込み（convolution）演算処理とを繰り返す。しかし、多元ＬＤＰＣ符号のＳＰＡ復号処理では、変数ノードよりも次数が高い検査ノードにおいて複雑な畳み込み演算処理を行う必要があるため、処理速度が低下するという問題があった。
【０００４】
このため、非特許文献１には、ＦＦＴ(高速フーリエ変換)を用い畳み込み演算を高速に行うアルゴリズムが提案されているが、このアルゴリズムの実行には高い演算精度が必要であった。また非特許文献２には、検査ノードにおける畳み込み演算処理を近似して単純化するアルゴリズムが開示されている。しかし、このアルゴリズムを用いたとしても、依然として検査ノードにおける畳み込み演算処理は時間を要する処理であり、処理速度を上げることは容易ではなかった。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】マッカイ、デイビイ（MacKay and.Davey）著、「短ブロック長高速レートのＬＤＰＣ符号の評価（Evaluation of Gallager codes for short block length and high rate applications）」、アイエムエイ  符号ワークショップ予稿集（in Proc. IMA Workshop Codes、 Syst. ） 113-130ページ、グラフィカルモデルズ（Graphical Models）、米国、１９９９年。
【非特許文献２】メルシュ、ステンダム、モエネクライ（Wymeersch、Steendam、 and Moeneclaey）著、「ＧＦ（ｑ）のＬＤＰＣ符号の対数領域復号（Log-domain decoding of LDPC codes over ＧＦ(ｑ)）」、アイトリプルイー通信国際会議予稿集（IEEE International Conference on Communications） 772-776ページ、米国、２００４年。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記事情に鑑みて、本発明はなされたものであり、処理速度の早い復号装置および復号方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本願発明の一態様の復号装置は、多元低密度パリティ検査符号を用いて符号化された符号化フレームデータを復号処理する復号装置であって、符号化フレームデータのシンボルの確率ベクトルに対して、フーリエ変換処理および対数値化処理を施し、対数フーリエ領域確率ベクトルの初期値を出力する対数フーリエ変換処理部と、対数フーリエ領域確率ベクトルの初期値とエッジ係数処理部から出力される第４のメッセージとを用いた畳み込み演算による変数ノード処理を実行し第１のメッセージを算出するとともに対数フーリエ領域確率ベクトルを更新し、出力する変数ノード処理部と、第１のメッセージに対してエッジ係数処理を実行し、第２のメッセージを算出するとともに、検査ノード処理部から入力される第３のメッセージに対してエッジ逆係数処理を実行し第４のメッセージを算出するエッジ係数処理部と、第２のメッセージに対して加算演算による検査ノード処理を実行し、第３のメッセージを算出する検査ノード処理部と、を備えたことを特徴とする。
【０００８】
本発明の別の一態様の復号方法は、多元低密度パリティ検査符号を用いて符号化された符号化フレームデータを復号処理する復号方法であって、対数フーリエ変換処理と、変数ノード処理と、エッジ係数処理と、検査ノード処理と、を具備し、対数フーリエ変換処理が、符号化フレームデータのシンボルの確率ベクトルに対して、フーリエ変換処理および対数化処理を施し、対数フーリエ領域確率ベクトルの初期値を算出する処理であり、変数ノード処理が、対数フーリエ領域確率ベクトルと検査ノード処理部から出力される第４のメッセージとを用いた畳み込み演算による変数ノード処理を実行し、第１のメッセージを算出するとともに対数フーリエ領域確率ベクトルを更新する処理であり、エッジ係数処理が、第１のメッセージに対してエッジ係数処理を実行し、第２のメッセージを算出するとともに、第３のメッセージに対してエッジ逆係数処理を実行し第４のメッセージを算出する処理であり、検査ノード処理が、第２のメッセージに対して、加算演算による検査ノード処理を実行し、第３のメッセージを算出する処理である。
【発明の効果】
【０００９】
本発明によれば処理速度の早い復号装置および復号方法を提供することができる。
【図面の簡単な説明】
【００１０】
【図１】多元ＬＤＰＣ符号を説明するための説明図である。
【図２】多元ＬＤＰＣ符号のパリティ検査行列をグラフ表現したタナーグラフである。
【図３】第１の実施の形態の復号装置の構成図である。
【図４】基底ベクトルを説明するための説明図である。
【図５】第２の実施の形態の復号装置の構成図である。
【発明を実施するための形態】
【００１１】
＜多元ＬＤＰＣ符号＞
最初に、多元ＬＤＰＣ符号について簡単に説明する。図１は、ガロア拡大体ＧＦ（４）、すなわちサイズ４のときの多元ＬＤＰＣ符号の２行３列のパリティ検査行列(Parity Check Matrix)を示している。多元ＬＤＰＣ符号では、複数のビットからなるシンボル単位で処理を行う。例えば、ＧＦ（４）の多元ＬＤＰＣ符号では、バイナリ表現の（００）、（１０）、（０１）、（１１）を、それぞれ、０、α、１、α２の４つのシンボルとして復号処理する。検査行列は各行がパリティ検査式を表しており、図１に示すように、データフレームは検査式の積和が０になるように構成されている。このため、復号されたデータフレームに誤りが生じていた場合には、この検査式の拘束を使って訂正処理が行われる。なお、復号装置１００においては、ＧＦ（６４）、ＧＦ（１２８）、またはＧＦ（２５６）のようなガロア拡大体を用いることが好ましい。
【００１２】
次に、図２は図１に示したパリティ検査行列をグラフ表現したタナーグラフを示す。ＳＰＡではタナーグラフで示すように、変数ノードと検査ノードとの間で、エッジ係数処理を行いながら、メッセージのやりとりを繰り返すイタレーション処理により、復号処理を行う。
【００１３】
＜第１の実施の形態＞
次に、図３を用いて本発明の第１の実施の形態の復号装置１００の概略構成を説明する。図３に示すように本実施の形態の復号装置１００は、対数フーリエ変換処理部１０１、通信路値メモリ１０２、スケジューラ１０３、変数ノード処理部１０４、エッジ係数処理部１０６、検査ノード処理部１０７、パリティ検査部１０８、硬判定部１０９、および出力バッファ１１０を有する。
【００１４】
ここで、ＬＦＤＶは対数フーリエ領域確率ベクトル( Log-Fourier Domain  Probability Vector  )を表している。変数ノード処理部１０４がエッジ係数処理部１０６に出力するメッセージが第１のメッセージＭ１であるＶＣメッセージであり、エッジ係数処理部１０６が検査ノード処理部１０７に出力するメッセージが第２のメッセージＭ２である係数処理後のＶＣメッセージである。また検査ノード処理部１０７がエッジ係数処理部１０６に出力するメッセージが第３のメッセージＭ３であるＣＶメッセージであり、エッジ係数処理部１０６が変数ノード処理部１０４に出力するメッセージが第４のメッセージＭ４である係数処理後のＣＶメッセージである。なお、それぞれのメッセージの具体的な算出方法については後に詳述する。またＬＦＤＶおよびメッセージは処理回数に応じて変化するため、必要に応じて、末尾に括弧付きで処理回数（ｌ）を示す。例えばＬＦＤＶ（０）は対数フーリエ領域確率ベクトルの初期値を意味する。
【００１５】
復号装置１００を構成する上記構成要素は、電気回路等であり、物理的に独立した構成要素である必要はなく、例えば１チップにパッケージされていてもよい。また汎用のＣＰＵで実行されるＦＷ（Firm Ware）により上記構成要素の機能を実現してもよい。さらに、復号装置１００は、変数ノード処理部１０４とエッジ係数処理部１０６との間のメッセージを一時的に記憶する第１のメッセージメモリ、検査ノード処理部１０７４とエッジ係数処理部１０６との間のメッセージを一時的に記憶する第２のメッセージメモリ等の記憶部を有していることが好ましい。
【００１６】
スケジューラ１０３は、復号装置１００全体の制御を行う。具体的には変数ノード処理部１０４、エッジ係数処理部１０６、および検査ノード処理部１０７へ処理の実行を通知し、通信路値メモリ１０２へ変数ノード処理部１０４の処理のタイミングにあわせて必要なデータを出力するよう通知する。また、パリティ検査部１０８から入力されるパリティ検査結果、または復号繰り返し回数（イタレーション回数）から復号処理の終了を判断し、復号処理が終了した際には出力バッファ１１０へ復号結果を図示しない後段の信号処理部へ出力するよう通知する。
【００１７】
通信路値メモリ１０２は、一時記憶部であり、対数フーリエ変換処理部１０１から入力された、ＬＦＤＶの初期値、ＬＦＤＶ（０）を、イタレーション処理を行う間、保持する。通信路値メモリ１０２が保持しているＬＦＤＶ（０）は、変数ノード処理部１０４の処理に応じて、少なくとも１回以上出力される。
【００１８】
硬判定部１０９は、変数ノード処理部１０４から入力される符号データフレーム分のＬＦＤＶ（ｌ）におけるビット毎の基底ベクトル（base vector）を指すインデックスの値を正負判定し、正のときは０、負のときは１と判定して、硬判定データを出力する。ここで図４に示すように基底ベクトルとはバイナリにおいて「１」が１個だけのベクトルである。硬判定結果はパリティ検査部１０８と出力バッファ１１０とへ出力される。出力バッファ１１０は硬判定データを一時的に記憶し、スケジューラ１０３の通知に応じて復号結果である、硬判定データを出力する。
【００１９】
パリティ検査部１０８は、硬判定部１０９から入力される硬判定データが、多元ＬＤＰＣ符号のパリティ検査式を満たすかどうかパリティ検査を行い、その結果をスケジューラ１０３へ出力する。
【００２０】
対数フーリエ変換処理部１０１には図示しない信号処理部から、符号データフレームに含まれる各シンボルの確率ベクトル、「ｐ_v（ｘ）」、が入力される。対数フーリエ変換処理部１０１は入力された確率ベクトル、「ｐ_v（ｘ）」に対し、フーリエ変換処理を施し、さらに対数値化処理（底は自然対数）を施して、対数フーリエ領域確率ベクトル（ＬＦＤＶ）、「ｌｎ（Ｐ_ｖ（ｚ））」の初期値（ＬＦＤＶ（０））を、通信路値メモリ１０２へ出力する。
【００２１】
すなわち、対数フーリエ変換処理部１０１は、符号化フレームデータのシンボルの確率ベクトル、「ｐ_v（ｘ）」、に対して、フーリエ変換処理および対数化処理を施し、対数フーリエ領域確率ベクトルの初期値ＬＦＤＶ（０）を出力する。
【００２２】
ここで、通常、フーリエ変換処理は複素数に対して行われるが、多元ＬＤＰＣ符号のシンボルはガロア体のため、対数フーリエ変換処理部１０１が行うフーリエ変換処理は加算と減算のみによって実行される。以下にその変換式である式１を示す。
【００２３】
（式１）
【数１】
2011119857.tif 000003
【００２４】
上記の式１において、「ｐ_v（ｘ）」はシンボルｖの確率ベクトルを表し、この確率ベクトルの長さはガロア体ＧＦ（ｑ）の要素数と等しい「ｑ」となる。また、「ｘ・ｚ」はインデックス番号を２元展開したバイナリベクトル同士の内積を表す。ガロア体のサイズが２のべき乗の場合には、フーリエ変換処理は再帰的に実行することができるため、バタフライ演算で知られる高速フーリエ変換アルゴリズムを用いることができる。またフーリエ変換後の値は負となることがあるため、対数変換式は以下の式で与えられる複素数に拡張したものを用いる。
【００２５】
（式２）
【数２】
2011119857.tif 000004
【００２６】
（式３）
【数３】
2011119857.tif 000005
【００２７】
変数ノード処理部１０４は、スケジューラ１０３から入力される変数ノード処理の実行通知に従い、通信路値メモリ１０２から入力されるＬＦＤＶ（０）、「ｌｎＰｖ（ｚ）」と、エッジ係数処理部１０６から入力される逆係数処理後のＣＶメッセージＭ４（ｌ）、「Λ＾（ｌ）＿ｃｖ」とを用いて、パリティ検査行列の指定された列インデックスのパリティ検査式に従う変数ノード処理を実行し、第１のメッセージＭ１（ｌ）であるＶＣメッセージ、「Λ＾（ｌ）＿ｖｃ」と、ＬＦＤＶ（ｌ）、「Λ＾（ｌ）＿ｖ」と、を計算する。
【００２８】
すなわち、変数ノード処理部１０４は、対数フーリエ領域確率ベクトルＬＦＤＶ（０）と第４のメッセージＭ４（ｌ）とを用いた畳み込み演算による変数ノード処理を実行し、第１のメッセージＭ１を算出するとともに、対数フーリエ領域確率ベクトルＬＦＤＶ（ｌ）を算出する。言い換えれば変数ノード処理部１０４は、対数フーリエ領域確率ベクトルＬＦＤＶ（ｌ）を、対数フーリエ領域確率ベクトルＬＦＤＶ（０）と第４のメッセージＭ４（ｌ）とを用いて更新する。
【００２９】
以下に、ＶＣメッセージ、「Λ＾（ｌ）＿ｖｃ」を算出する式４を示す。
（式４）
【数４】
2011119857.tif 000006
【００３０】
ここで、「Λ＾（ｌ）＿ｃ‘ｖ」、は、エッジ係数処理部１０６から入力される逆係数処理後のＣＶメッセージＭ４（ｌ）を表す。「Ｖ＿ｃ＼ｃ」は、集合「Ｖ＿ｃ」のうち、「ｃ」を除いた行インデックスの部分集合を表し、「ｌ」は、繰り返し回数を表す。なお、復号開始時の「Λ＾（０）＿ｖｃ」は「ｌｎＰｖ（ｚ）」とする。
【００３１】
また、
【数５】
2011119857.tif 000007
は、以下の式６で定義される畳み込み演算を表す。
【００３２】
（式６）
【数６】
2011119857.tif 000008
【００３３】
さらに、ＬＦＤＶ（ｌ）、「Λ＾（ｌ）＿ｖ」は、以下の式７により計算される。
（式７）
【数７】
2011119857.tif 000009
【００３４】
エッジ係数処理部１０６は、変数ノード処理部１０４から入力されるＶＣメッセージＭ１（ｌ）に対し、エッジ係数（Edge ｃｏｅｆｆｉｃｉｅｎｔ ）、「α＿ｖｃ」、で係数処理を行い、係数処理後のＶＣメッセージＭ２（ｌ）を算出し、検査ノード処理部１０７へ出力する。また、エッジ係数処理部１０６は、検査ノード処理部１０７から入力されるＣＶメッセージＭ３（ｌ）に対し、エッジ係数「α＿ｖｃ」で逆係数処理を行い、逆係数処理後のＣＶメッセージＭ４（ｌ）を変数ノード処理部１０４へ出力する。
【００３５】
すなわち、エッジ係数処理部１０６は、第１のメッセージＭ１に対してエッジ係数処理を実行し第２のメッセージＭ２を算出するとともに、第３のメッセージＭ３に対してエッジ逆係数処理を実行し第４のメッセージＭ４を算出する。
【００３６】
まず、係数処理後のＶＣメッセージＭ２（ｌ）を算出する式８を以下に示す。
（式８）
【数８】
2011119857.tif 000010
【００３７】
なお、Ａ（α）は、係数αに対応するバイナリ行列で、以下の式９により与えられる。
【００３８】
（式９）
【数９】
2011119857.tif 000011
【００３９】
また、「ｅ＿ｉ」は、ｉビット目のみが１であるバイナリ基底ベクトルである。 
【００４０】
次に、逆係数処理後のＣＶメッセージＭ４（ｌ）を算出する逆係数処理を以下に示す。
（式１０）
【数１０】
2011119857.tif 000012
【００４１】
対数フーリエ変換処理による確率ベクトルの処理を行わない公知の多元ＬＤＰＣ符号の復号処理では、係数処理の単純な逆操作により逆係数処理を行うことができる。しかし、本発明のアルゴリズムを用いた復号方法では、（式１０）の算出処理を実行する必要がある。なお、符号化時の係数を転置した係数行列にすることで、逆係数処理を従来の処理と同等の単純な逆操作処理に置き換えることも可能である。
【００４２】
検査ノード処理部１０７は、エッジ係数処理部１０６から入力された係数処理後のＶＣメッセージＭ２（ｌ）を用いて、ＣＶメッセージＭ３（ｌ＋１）を算出する。すなわち、検査ノード処理部１０７は、第２のメッセージＭ２に対して加算演算による検査ノード処理を実行し、第３のメッセージＭ３を算出する
【００４３】
具体的には、検査ノード処理部１０７は、以下の式１１で示す加算演算を行う。
（式１１）
【数１１】
2011119857.tif 000013
【００４４】
以上の説明のように、本実施の形態の復号装置１００および復号方法では検査ノード処理の負荷が小さいため、処理速度が速い。
【００４５】
すなわち、従来の多元ＬＤＰＣ符号の復号装置では、次数（項数）が多い検査ノード処理において、（式５）に示したような畳み込み演算を行うため、検査ノード処理の負荷が大きかった。これに対して、本実施の形態の復号装置１００および復号方法では、検査ノード処理が畳み込み演算ではなく加算演算であるため、検査ノード処理の負荷は小さく、処理速度が速い。
【００４６】
なお、硬判定部１０９の硬判定方法としては、上述した方法だけでなく、従来の多元ＬＤＰＣ符号の復号処理で用いられている確率ベクトル領域での硬判定を行うことも、もちろん可能である。確率ベクトル領域で硬判定を行う場合には、ＬＦＤＶ（ｌ）に対して逆対数フーリエ変換処理を施し、事後確率ベクトルを算出し、その事後確率ベクトルが最大となるシンボルへ硬判定する。
【００４７】
次に、本実施の形態の復号装置１００の動作について処理の流れに沿って説明する。
＜確率ベクトル入力処理工程＞
図示しない前段の信号処理部より、符号データフレームの各シンボルの確率ベクトル「ｐ_v（ｘ）」が復号装置１００に入力される。
【００４８】
＜対数フーリエ変換処理工程＞
復号装置１００に入力された符号化フレームデータの各シンボルの確率ベクトル「ｐ_v（ｘ）」は逐次、対数フーリエ変換処理部１０１で対数フーリエ変換（フーリエ変換および対数化）され、通信路値メモリ１０２へ格納される。なお対数フーリエ変換された確率ベクトルの初期値、ＬＦＦＶ（０）、「ｌｎ（Ｐ_v（ｚ））」は復号処理が行われる間、通信路値メモリ１０２で保持される。
【００４９】
符号データフレームのすべてのＬＦＦＶ（０）が通信路値メモリ１０２に入力されたら、スケジューラ１０３の指示により復号処理が開始され、ＬＦＦＶ（０）が変数ノード処理部１０４に出力される。
【００５０】
＜初期化処理工程＞
変数ノード処理部１０４において、ＶＣメッセージＭ１が、ＬＦＦＶ（０）を用いて初期化される。なお、以下の説明では、イタレーション回数（ｌ）の場合を例に説明する。
【００５１】
＜係数処理工程＞
変数ノード処理部１０４から出力されたＶＣメッセージＭ１（ｌ）が、エッジ係数処理部１０６で係数処理され、係数処理後のＶＣメッセージＭ２（ｌ）が算出される。
【００５２】
＜検査ノード処理工程＞
検査ノード処理部１０７は、エッジ係数処理部１０６から出力されたＶＣメッセージＭ２（ｌ）を用いて、（式９）で示した検査ノード処理を行いＣＶメッセージＭ３（ｌ＋１）を算出する。このとき、検査ノード処理部１０７が各検査ノードの処理を逐次的に行ってもよいが、複数の検査ノード処理を並列処理することが好ましい。並列処理により、処理速度がより速くなる。さらに検査ノード処理部１０７がすべての検査ノードの処理を同時に並列処理することが、より好ましい。
【００５３】
＜逆係数処理工程＞
検査ノード処理部１０７から出力されたＣＶメッセージＭ３（ｌ＋１）が、エッジ係数処理部１０６で逆係数処理され、逆係数処理後のＣＶメッセージＭ４（ｌ＋１）が算出される。
【００５４】
＜変数ノード処理工程＞
変数ノード処理部１０４にて（式４）、（式７）に示した変数ノード処理が行われ、ＬＦＤＶ（ｌ＋１）が算出される。
【００５５】
＜硬判定処理工程＞
変数ノード処理部１０４から出力された、ＬＦＤＶ（ｌ＋１）に対し、硬判定部１０９にて硬判定が行われ、硬判定結果、すなわち硬判定データが算出され、パリティ検査部１０８と出力バッファ１１０に出力される。
【００５６】
＜パリティ検査処理工程＞
硬判定データをもとにパリティ検査部１０８がパリティ検査を行う。
【００５７】
＜復号処理終了？＞
パリティ検査において、すべてのパリティ検査式を満たした場合には、誤りなく復号処理が完了したことを意味する。すると、スケジューラ１０３は復号処理を終了し、出力バッファ１１０へ硬判定データを出力するよう指示する
【００５８】
パリティ検査において、パリティ検査式を満たさない場合には、（式４）で得られたＶＣメッセージＭ１（ｌ＋１）をもとに、上記の一連の処理であるイタレーション処理が、繰り返し行われる。
【００５９】
イタレーション処理の繰り返し回数（イタレーション回数）については、あらかじめ最大数Ｌｍａｘが決められており、最大数Ｌｍａｘを超えた場合にはパリティ検査においてパリティ検査式が満足しなくても、スケジューラ１０３は復号処理を停止し、出力バッファ１１０の硬判定結果を後段の信号処理部へ出力する。または、スケジューラ１０３はエラー信号を出力する。
【００６０】
なお、復号処理完了までに必要な繰り返し回数が多いことが処理開始前に判明している場合には、パリティ検査部１０８はパリティ検査をイタレーション処理毎に行わないで、所定のイタレーション回数の場合にのみ、または所定のイタレーション回数おきに、実施してもよい。
【００６１】
以上のように本実施の形態の復号方法では、多元ＬＤＰＣ符号の並列復号計算において従来の確率領域ＳＰＡと等価なフーリエ領域ＳＰＡを用いる。このため確率領域ＳＰＡによる復号処理でボトルネックとなっていた検査ノード処理における畳み込み演算を、メッセージが集中していない変数ノードに任せることにより処理遅延の問題を解決している。
【００６２】
すなわち、本実施の形態の復号方法では、入力された確率ベクトルを対数フーリエ変換し、復号処理を対数フーリエ領域で実施することにより、従来の復号装置で問題となっていた検査ノード処理における畳み込み演算を加算処理に入れ替えて、ＳＰＡによる処理を行うことができるために、復号処理の処理速度を早くすることができる。
【００６３】
＜第２の実施の形態＞
次に、本発明の第２の実施の形態の復号装置１００Ａおよび復号方法について説明する。本実施の形態の復号装置１００Ａおよび復号方法は、第１の実施の形態の復号装置１００および復号方法と類似しているため、同じ構成要素には同じ符号を付し説明は省略する。
【００６４】
図５に示すように、本実施の形態の復号装置１００Ａは検査ノード処理部２０７とパリティ検査部２０８とが、第１の実施の形態の復号装置１００と異なる。
【００６５】
検査ノード処理部２０７は、（式１０）で示した検査ノード処理と同時に以下の（式１２）で示す第３のメッセージＭ３の総和ベクトルＭ５の算出処理を行う。そしてパリティ検査部２０８は（式１２）で得られた第３のメッセージＭ３の総和ベクトルＭ５の基底ベクトルの硬判定を行うことで、パリティ検査を行う。
【００６６】
（式１２）
【数１２】
2011119857.tif 000014
【００６７】
すなわち、本実施の形態の復号装置１００Ａおよび復号方法では、パリティ検査部２０８は、検査ノード処理部２０７が出力する第３のメッセージＭ３の総和ベクトルＭ５の基底ベクトルの符号判定を行うことでパリティ検査を行う。
【００６８】
ここで、（式１０）の算出は、最初に総和ベクトルＭ５を算出し、総和ベクトルＭ５から１つの変数ノード「ｃ」へのメッセージを除くことにより行うことができる。このため（式１０）の算出過程で算出された総和ベクトルＭ５を用いることにより、復号装置１００Ａでは新たに（式１２）の算出を行うことなく、パリティ検査を行うことができる。
【００６９】
本実施の形態の復号装置１００Ａおよび復号方法は、第１の実施の形態の復号装置１００および復号方法と同じ効果を有し、さらに処理速度の早い復号装置および復号方法である。
【００７０】
なお、本発明は多元ＬＤＰＣ符号を用いるシステムであれば、いかなるシステムに対しても応用可能である。例えば通信システム、放送システムをはじめ、磁気記録システム、光ディスクシステム、さらには半導体メモリ等、様々なストレージシステムでも用いることが可能である。
【００７１】
また、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【符号の説明】
【００７２】
１００、１００Ａ…復号装置
１０１…対数フーリエ変換処理部
１０２…通信路値メモリ
１０３…スケジューラ
１０４…変数ノード処理部
１０６…エッジ係数処理部
１０７…検査ノード処理部
１０８…パリティ検査部
１０９…硬判定部
１１０…出力バッファ
２０７…検査ノード処理部
２０８…パリティ検査部
【図１】
2011119857.tif 000015
【図２】
2011119857.tif 000016
【図３】
2011119857.tif 000017
【図４】
2011119857.tif 000018
【図５】
2011119857.tif 000019