(57)【要約】【課題】ｍｉｎ−ｓｕｍアルゴリズムの処理サイクル数を少なくすることのできる低密度パリティ検査符号の復号装置及び復号方法を提供する。【解決手段】本発明の実施形態によれば、行処理演算部３は、検査行列の行ごとに、列処理演算結果が書き込まれるβメモリ２から読み出された列処理演算結果に対して行処理演算を行う。列処理演算部４は、検査行列の列ごとに、行処理演算結果が書き込まれるαメモリ１から読み出された行処理演算結果に対して列処理演算を行う。制御手段５は、検査行列の要素が零ブロックであるか非零ブロックであるかに応じて、αメモリ１およびβメモリ２の読み出しおよび書き込み、ならびに行処理演算部３および列処理演算部４を制御し、前行の行処理演算結果に対する列処理演算と現在行の行処理演算を並行に実行する。【選択図】  図１
2011249980.tif 000002
【特許請求の範囲】
【請求項１】
行処理および列処理の並列処理数をブロックサイズとした基本ブロックを要素とする検査行列により定義される低密度パリティ検査符号を復号する復号装置であって、
行処理演算結果が書き込まれる行処理演算結果メモリ手段と、
列処理演算結果が書き込まれる列処理演算結果メモリ手段と、
前記検査行列の行ごとに、前記列処理演算結果メモリ手段から読み出された列処理演算結果に対して行処理演算を行う行処理演算手段と、
前記検査行列の列ごとに、前記行処理演算結果メモリ手段から読み出された行処理演算結果に対して列処理演算を行う列処理演算手段と、
前記検査行列の前記要素が零ブロックであるか非零ブロックであるかに応じて、前記行処理演算結果メモリ手段および前記列処理演算結果メモリ手段の読み出しおよび書き込み、ならびに前記行処理演算手段および前記列処理演算手段を制御する制御手段と
を備え、
前行の行処理演算結果に対する列処理演算と現在行の行処理演算を並行に実行する
ことを特徴とする低密度パリティ検査符号の復号装置。
【請求項２】
行処理対象の前記要素が零ブロックであるときは、
前記制御手段が、前記行処理演算手段における演算の省略を行う
ことを特徴とする請求項１に記載の低密度パリティ検査符号の復号装置。
【請求項３】
列処理対象の前記要素が零ブロックであるときは、
前記制御手段が、前記列処理演算手段における演算の省略を行う
ことを特徴とする請求項１または２に記載の低密度パリティ検査符号の復号装置。
【請求項４】
行処理および列処理の並列処理数をブロックサイズとした基本ブロックを要素とする検査行列により定義される低密度パリティ検査符号を復号する復号方法であって、
前記検査行列の行ごとに、行処理演算結果が書き込まれる列処理演算結果メモリ手段から読み出された列処理演算結果に対して行処理演算を行い、
前記検査行列の列ごとに、列処理演算結果が書き込まれる行処理演算結果メモリ手段から読み出された行処理演算結果に対して列処理演算を行い、
前記検査行列の前記要素が零ブロックであるか非零ブロックであるかに応じて、前記行処理演算結果メモリ手段および前記列処理演算結果メモリ手段の読み出しおよび書き込み、ならびに前記行処理演算および前記列処理演算の実行を制御し、
前行の行処理演算結果に対する列処理演算と現在行の行処理演算を並行に実行する
ことを特徴とする低密度パリティ検査符号の復号方法。
【請求項５】
行処理対象の前記要素が零ブロックであるときは、前記行処理演算における演算の省略を行う
ことを特徴とする請求項４に記載の低密度パリティ検査符号の復号方法。
【請求項６】
列処理対象の前記要素が零ブロックであるときは、前記列処理演算における演算の省略を行う
ことを特徴とする請求項４または５に記載の低密度パリティ検査符号の復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、  低密度パリティ検査符号の復号装置及び復号方法に関する。
【背景技術】
【０００２】
低密度パリティ検査（Low  Density  Parity  Check：ＬＤＰＣ）符号は、少数の非零成分を持つ疎なパリティ検査行列により定義される誤り訂正符号である。ＬＤＰＣ符号により符号化されたデータを復号する復号処理では、パリティ検査行列の行方向と列方向で情報の確からしさ（尤度）をやりとりし、更新を繰り返すアルゴリズムが用いられる。
【０００３】
その復号アルゴリズムの中でもハードウェア実装に適したｍｉｎ−ｓｕｍアルゴリズムを用いた場合、行方向の演算（行処理）では、列方向の演算（列処理）の結果βの正負の符号の積の計算と絶対値の最小値の探索を行い、列処理では、行処理の結果αの総和を計算する。
【０００４】
行処理および列処理の計算式は、次のとおりである。
【数１】
2011249980.tif 000003
【数２】
2011249980.tif 000004
【０００５】
ここで、
ｍ：行番号
ｎ：列番号
αｍｎ：ｍ行ｎ列目の行処理結果
βｍｎ：ｍ行ｎ列目の列処理結果
Ａ（ｍ）：ｍ行目に‘１’が立っている列番号の集合
Ｂ（ｎ）：ｎ列目に‘１’が立っている行番号の集合
Ａ（ｍ）＼ｎ：集合Ａ（ｍ）からｎを除いた集合
Ｂ（ｎ）＼ｍ：集合Ｂ（ｎ）からｍを除いた集合
ｓｉｇｎ（ｘ）：ｘの正負の集合（負の場合：−１、正の場合：１）
【０００６】
一般に、ｍｉｎ−ｓｕｍアルゴリズムを用いる復号装置では、複数の行処理、または、複数の列処理を並列に処理する。その検査行列としては、行処理および列処理の並列処理数をブロックサイズとした単位行列を基本ブロックとして、この基本ブロックを要素とする検査行列が用いられる。この検査行列では、基本ブロックに含まれる複数の行を「行」と称し、基本ブロックに含まれる複数の列を「列」と称する。
【０００７】
また、演算処理は、各行の行処理と列処理が交互に実行される。そのとき、１行分の行処理結果は行処理メモリに書き込まれて、その行の列処理に使用され、また、その列処理結果は列処理結果メモリに書き込まれて、次の行の行処理に使用される。
【０００８】
したがって、この演算処理に要する処理サイクル数Ｓは、パリティ検査行列の行数をｋ、各行の基本ブロック数をｂ、各ブロックの行処理および列処理に要するサイクル数をそれぞれｓ１、ｓ２とすると、
Ｓ＝ｋ・ｂ・（ｓ１＋ｓ２）
と表される。
【０００９】
このように、ｍｉｎ−ｓｕｍアルゴリズムを用いた従来のＬＤＰＣ符号の復号処理では、検査行列に配列された基本ブロックの総数（ｋ・ｂ）に比例して演算処理に要する処理サイクル数Ｓが増加する、という問題があった。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２００９−１００２２２号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
そこで、本発明の目的は、ｍｉｎ−ｓｕｍアルゴリズムの処理サイクル数を少なくすることのできる低密度パリティ検査符号の復号装置及び復号方法を提供することにある。
【課題を解決するための手段】
【００１２】
本発明の実施形態によれば、行処理演算手段は、検査行列の行ごとに、列処理演算結果が書き込まれる列処理演算結果メモリ手段から読み出された列処理演算結果に対して行処理演算を行う。列処理演算手段は、前記検査行列の列ごとに、行処理演算結果が書き込まれる行処理演算結果メモリ手段から読み出された行処理演算結果に対して列処理演算を行う。制御手段は、前記検査行列の前記要素が零ブロックであるか非零ブロックであるかに応じて、前記行処理演算結果メモリ手段および前記列処理演算結果メモリ手段の読み出しおよび書き込み、ならびに前記行処理演算手段および前記列処理演算手段を制御し、前行の行処理演算結果に対する列処理演算と現行の行処理演算を並行に実行する。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施例に係る低密度パリティ検査符号の復号装置の構成の例を示すブロック図。
【図２】本発明の実施例の復号装置の行処理と列処理の処理順序の説明図。
【図３】低密度パリティ検査符号の検査行列の例を示す図。
【図４】本発明の実施例の復号装置の行処理と列処理の演算手順の例を示す図。
【図５】本発明の実施例の復号装置の行処理と列処理の演算手順の例を示す図。
【図６】本発明の実施例の復号装置の行処理と列処理の演算手順の例を示す図。
【図７】本発明の実施例の復号装置の処理サイクル数の例を示す図。
【発明を実施するための形態】
【００１４】
以下、本発明の実施例について図面を参照して説明する。なお、図中、同一または相当部分には同一の符号を付して、その説明は繰り返さない。
【実施例】
【００１５】
図１は、本発明の実施例に係る低密度パリティ検査符号の復号装置の構成の例を示すブロック図である。本実施例では、行処理および列処理の並列処理数をブロックサイズとした基本ブロックを要素とする検査行列により定義される低密度パリティ検査符号を復号する復号装置の例を示す。
【００１６】
本実施例の復号装置は、行処理演算結果が書き込まれるαメモリ（行処理演算結果メモリ）１と、列処理演算結果が書き込まれるβメモリ（列処理演算結果メモリ）２と、検査行列の行ごとに、βメモリ２から読み出された列処理演算結果に対して行処理演算を行う行処理演算部３と、検査行列の列ごとに、αメモリ１から読み出された行処理演算結果に対して列処理演算を行う列処理演算部４と、検査行列の要素が零ブロックであるか非零ブロックであるかに応じて、αメモリ１およびβメモリ２の読み出しおよび書き込み、ならびに行処理演算部３および列処理演算部４を制御する制御部５と、を備える。
【００１７】
αメモリ１には、１つのアドレスに並列処理数と同数のαが行順に格納され、βメモリ２には、１つのアドレスに並列処理数と同数のβが列順に格納される。
【００１８】
初期状態では、αメモリ１には‘０’が格納され、βメモリ２には復号装置の入力である対数尤度比が格納されている。
【００１９】
行処理演算部３は、列→行変換回路３１と、α計算回路３２と、を有する。
【００２０】
列→行変換回路３１は、列処理演算部４から入力される、列順に並べられたβを、検査行列情報をもとに、行順に並べ替える。
【００２１】
α計算回路３２は、列→行変換回路３１から出力されたβに対して、正負の符号の積の計算と、絶対値の最小値の探索を行い、数１に示した計算式の計算を行う。
【００２２】
列処理演算部４は、行→列変換回路４１と、総和更新回路４２と、β計算回路４３と、を有する。
【００２３】
行→列変換回路４１は、αメモリ１から読み出された、行順に並べられたαを、検査行列情報をもとに、列順に並べ替える。
【００２４】
総和更新回路４２は、行→列変換回路４１から入力されたαと、βメモリ２から読みだされたβとから、総和Σαを、Σα＝β＋αとして算出する。
【００２５】
β計算回路４３は、総和更新回路４２から入力された総和Σαと、行→列変換回路４１から入力されたαとから、数２に示した式のβを、β＝Σα−αとして算出する。
【００２６】
制御部５は、検査行列情報をもとに、αメモリ１およびβメモリ２に対する、読み出しおよび書き込みのアドレスの制御を行う。
【００２７】
また、制御部５は、検査行列情報をもとに、行処理演算部３および列処理演算部４の処理の流れを制御する。このとき、制御部５は、列処理中の列処理演算部４の演算結果を行処理演算部３へ入力するように制御し、１つ前の行の列処理と、現在の行の行処理とが並行に実行されるようにする。
【００２８】
その際、制御部５は、処理対象の要素が零ブロックであるときは、行処理と列処理のいずれか、もしくは両方において演算の省略を行う。
【００２９】
図２に、本実施例における行処理と列処理の処理順序を示す。
【００３０】
まず、最初に、検査行列の１行目の行処理が実行される。次に、１行目の列処理と２行目の行処理が並行して実行される。続いて、２行目の列処理と３行目の行処理が並行して実行される。次に、３行目の列処理と４行目の行処理が並行して実行される。以下、１つ前の行の列処理と現在の行の行処理が並行に実行される。最後に、最終行の列処理が実行される。
【００３１】
このように、本実施例では、１行目と最終行を除いては、行処理と列処理が並行に実行される。そのとき、制御部５は、行処理対象の要素が零ブロックであるときは行処理の演算を省略し、列処理対象の要素が零ブロックであるときは列処理の演算を省略するよう、並列処理の実行を制御する。また、行処理対象の要素および列処理対象の要素がともに零ブロックであるときは、そのステップの処理全体を省略する。
【００３２】
次に、図３に示す検査行列を例にとって、本実施例の復号装置の行処理と列処理の具体的な演算手順を図４〜図６を用いて説明する。
【００３３】
図３（ａ）は、行処理および列処理の並列処理数をブロックサイズとした基本ブロックを要素とする、行ブロック数が４、列ブロック数が２４の検査行列である。図中の白抜きの四角は、複数の単位行列をシフトした非零行列を示し、図中のハッチングした四角は、零行列を示す。ここで、行ブロック数は垂直方向の基本ブロックの数を指し、列ブロック数は水平方向の基本ブロックの数を指す。また、各行を行ブロック番号０〜３で表し、各列を列ブロック番号０〜２３で表す。
【００３４】
図３（ｂ）は、基本ブロックの例である。この例の場合、行処理の並列処理数が４、列処理の並列処理数が４となる。
【００３５】
図３（ｂ）に示す例の場合、行処理の演算結果α０１、α１２、α２３、α３０が、αメモリ１の１つのアドレスに、行順（前述の順）に格納される。また、列処理の演算結果β３０、β０１、β１２、β２３が、βメモリ２の１つのアドレスに、列順（前述の順）に格納される。
【００３６】
図４は、行処理と列処理を並行に実行するときの基本的な手順である。この手順は、行処理対象のブロックおよび列処理対象のブロックがともに非零ブロックである場合に使用される。例えば、図３の行ブロック番号３の行処理と行ブロック番号２の列処理を並行に実行するときに、図４に示す手順が使用される。
【００３７】
ここでは、１ブロック目（行ブロック番号３、列ブロック番号０）の処理を例にとって図４に示した手順を説明する。なお、以降の説明では、行ブロック番号ｐ、列ブロック番号ｑの位置のブロックに対する、行処理結果をα（ｐ，ｑ）、列処理結果をβ（ｐ，ｑ）と表すものとする。また、本実施例では、それぞれの処理は、クロックに同期して制御される。そこで、クロックサイクルの順に、処理の流れを説明する。
【００３８】
１サイクル目：αメモリ１からα（２，０）をリードし、行→列変換回路４１へ入力する（Ｓ１１）。
【００３９】
２サイクル目：α（２，０）を行→列変換回路４１で列順に並び替え、総和更新回路４２へ入力する（Ｓ１２）。同時に、βメモリ２からβ（２，０）をリードし、総和更新回路４２へ入力する（Ｓ１３）。また、αメモリ１からα（３，０）をリードし、行→列変換回路４１へ入力する（Ｓ０１）。
【００４０】
３サイクル目：総和更新回路４２で、α（２，０）とβ（２，０）から、Σα（０）＝β（２，０）＋α（２，０）を計算し、β計算回路４３へ入力する（Ｓ１４）。同時に、α（３，０）を行→列変換回路４１で列順に並び替え、β計算回路４３へ入力する（Ｓ０２）。
【００４１】
４サイクル目：β計算回路４３で、α（３，０）とΣα（０）から、β（３，０）＝Σα（０）−α（３，０）を計算する（Ｓ０３）。
【００４２】
５サイクル目：β（３，０）をβメモリ２へライトする（Ｓ１５）。同時に、β（３，０）を列→行変換回路３１で行順に並べ替え、α計算回路３２へ入力する（Ｓ０４）。
【００４３】
６サイクル目：α計算回路３２で、β（３，０）から、新たなα（３，０）を計算する（Ｓ０５）。
【００４４】
７サイクル目：最後に、この新たなα（３，０）をαメモリ１へライトする（Ｓ０６）。
【００４５】
このように、本実施例では、列処理対象および行処理対象のブロックがともに非零ブロックの場合、７サイクルで列処理と行処理を並行に処理するが、列処理対象あるいは行処理対象のブロックのいずれかが零ブロックの場合、零ブロックに対する演算を省略して、所要サイクル数を削減する。
【００４６】
まず、列処理対象のブロックが零ブロック、行処理対象のブロックが非零ブロックの場合について説明する。
【００４７】
図５は、列処理対象のブロックが零ブロック、行処理対象のブロックが非零ブロックの場合の処理手順である。ここでは、図３の行ブロック番号２の行処理と行ブロック番号１の列処理について、１ブロック目（行ブロック番号２、列ブロック番号０）の処理を例にとって、クロックサイクル順に説明する。
【００４８】
１サイクル目：βメモリ２からβ（１，０）をリードし、総和更新回路４２へ入力する（Ｓ１３）。また、αメモリ１からα（２，０）をリードし、行→列変換回路４１へ入力する（Ｓ０１）。
【００４９】
２サイクル目：総和更新回路４２で、β（１，０）から、Σα（０）＝β（１，０）＋０を計算し、β計算回路４３へ入力する（Ｓ１４）。同時に、α（２，０）を行→列変換回路４１で列順に並び替え、β計算回路４３へ入力する（Ｓ０２）。
【００５０】
３サイクル目：β計算回路４３で、α（２，０）とΣα（０）から、β（２，０）＝Σα（０）−α（２，０）を計算する（Ｓ０３）。
【００５１】
４サイクル目：β（２，０）をβメモリ２へライトする（Ｓ１５）。同時に、β（２，０）を列→行変換回路３１で行順に並べ替え、α計算回路３２へ入力する（Ｓ０４）。
【００５２】
５サイクル目：α計算回路３２で、β（２，０）から、新たなα（２，０）を計算する（Ｓ０５）。
【００５３】
６サイクル目：最後に、この新たなα（２，０）をαメモリ１へライトする（Ｓ０６）。
【００５４】
このように、列処理対象のブロックが零ブロックの場合、列処理演算の一部（αメモリリード、行→列変換）を省略することにより、６サイクルで列処理と行処理を並行に処理することができる。
【００５５】
なお、図５に示す処理手順は、行処理のみが行われる、図３の行ブロック番号０の行処理にも使用される。
【００５６】
次に、列処理対象のブロックが非零ブロック、行処理対象のブロックが零ブロックの場合について説明する。
【００５７】
図６は、列処理対象のブロックが零ブロック、行処理対象のブロックが零ブロックの場合の処理手順である。ここでは、図３の行ブロック番号１の行処理と行ブロック番号０の列処理について、１ブロック目（行ブロック番号１、列ブロック番号０）の処理を例にとって、クロックサイクル順に説明する。
【００５８】
１サイクル目：αメモリ１からα（０，０）をリードし、行→列変換回路４１へ入力する（Ｓ１１）。
【００５９】
２サイクル目：α（０，０）を行→列変換回路４１で列順に並び替え、総和更新回路４２へ入力する（Ｓ１２）。同時に、βメモリ２からβ（０，０）をリードし、総和更新回路４２へ入力する（Ｓ１３）。
【００６０】
３サイクル目：総和更新回路４２で、α（０，０）とβ（０，０）から、Σα（０）＝β（０，０）＋α（０，０）を計算し、β計算回路４３へ入力する（Ｓ１４）。
【００６１】
４サイクル目：β計算回路４３で、Σα（０）から、β（１，０）＝Σα（０）−０を計算する（Ｓ０３）。
【００６２】
５サイクル目：β（１，０）をβメモリ２へライトする（Ｓ１５）。
【００６３】
このように、行処理対象のブロックが零ブロックの場合、行処理の演算を省略して、５サイクルで列処理のみを行う。
【００６４】
なお、図６に示す処理手順は、列処理のみが行われる、最終行（図３では、行ブロック番号３）の列処理にも使用される。
【００６５】
また、列処理対象および行処理対象のブロックがともに零ブロックの場合は、行処理、列処理ともに演算不要である。したがって、この場合、処理サイクル数は０となる。
【００６６】
上述したように、本実施例では、処理対象のブロックが零ブロックであるかどうかによって、処理手順および処理サイクル数が異なってくる。そこで、図３の行列全体での処理サイクル数を図７に示す。
【００６７】
図７では、並行処理を行う行ブロック番号ごとに、処理対象のブロックの零ブロック／非零ブロックの組み合わせごとのブロック数を算出し、それぞれのブロックの処理に要するサイクル数を掛け合わせて、全体の処理サイクル数を算出している。図３に示した行列の例では、行処理および列処理にようする全体の処理サイクル数は６８０サイクルである。
【００６８】
これに対して、従来の、各行の行処理と列処理を交互に実行する処理方法における処理サイクル数を求めると、次のようになる。
【００６９】
行処理のサイクル数ｓ１は、本実施例の図５に示す手順と同じく、ｓ１＝６、列処理のサイクル数ｓ２は、本実施例の図４に示す手順のうちの４サイクル目の処理が不要なので、ｓ２＝４となる。したがって、図３に示した行列の場合、行数ｋは、ｋ＝４、各行の基本ブロック数ｂは、ｂ＝２０であるので、行列全体の処理サイクル数Ｓは、
Ｓ＝ｋ・ｂ・（ｓ１＋ｓ２）＝４×２０×（６＋４）＝８００
となる。
【００７０】
このように、本実施例によれば、図３に示した行列の例に対しては、処理サイクル数を８００から６８０に減らす（削減率１５％）ことができる。
【符号の説明】
【００７１】
１  αメモリ
２  βメモリ
３  行処理演算部
４  列処理演算部
５  制御部
３１  列→行変換回路
３２  α計算回路
４１  行→列変換回路
４２  総和更新回路
４３  β計算回路
【図１】
2011249980.tif 000005
【図２】
2011249980.tif 000006
【図３】
2011249980.tif 000007
【図４】
2011249980.tif 000008
【図５】
2011249980.tif 000009
【図６】
2011249980.tif 000010
【図７】
2011249980.tif 000011