(57)【要約】【課題】  訂正不可能なエラーが発生した場合であっても、その中に含まれる誤り率を平均的に減少させることができる低密度パリティチェック符号復号器及び方法を提供する。【解決手段】  ＣＰＵ１６は、復号としてパリティ検査行列と受信データとを掛けて得られたベクトルのうち、値が”１”である数をパリティエラー数として記憶し、かつ、このパリティエラー数に対応する硬判定結果情報を出力候補情報保存領域２６に記憶する。そして、この復号を所定回数行った後に、受信データの訂正が不能とＣＰＵ１６によって判別された場合は、出力候補情報保存領域２６に記憶されたパリティエラー数のうち、最小値であるパリティエラー数を判別し、このパリティエラー数に対応する硬判定結果情報を読み出し、復号結果として出力する。【選択図】      図１
2006135813.tif 000002
【特許請求の範囲】
【請求項１】
低密度パリティチェック符号復号器であって、
所定のパリティ検査行列を用いて受信データを復号する場合、前記パリティ検査行列と受信データとを掛けて得られたベクトルのうち、値が”非零”である数をパリティエラー数として記憶し、かつ前記パリティエラー数に対応する硬判定結果情報を記憶する記憶手段と、
前記復号を所定回数行った後に、前記受信データの訂正が不能と判別された場合は、前記記憶手段に記憶されたパリティエラー数のうち、最小値であるパリティエラー数に対応する硬判定結果情報を読み出し、復号結果として出力する出力手段と、
を含むことを特徴とする低密度パリティチェック符号復号器。
【請求項２】
低密度パリティチェック符号復号器であって、
所定のパリティ検査行列を用いて受信データを復号する場合、前記パリティ検査行列と受信データとを掛けて得られたベクトルのうち、値が”非零”である数をパリティエラー数とし、当該パリティエラー数が既に記憶されているパリティエラー数と比較して最小値であると判別された場合は、前記記憶されているパリティエラー数、及びこれに対応する硬判定結果情報に換えて、最小値である前記パリティエラー数及びこれに対応する硬判定結果情報を記憶する記憶手段と、
前記復号を所定回数行った後に、前記受信データの訂正が不能と判別された場合は、前記記憶手段に記憶された硬判定結果情報を読み出し、復号結果として出力する出力手段と、
を含むことを特徴とする低密度パリティチェック符号復号器。
【請求項３】
前記パリティ検査行列と受信データとを掛ける場合、前記パリティ検査行列の各行のうち、値が”１”である数が奇数個であるときは、前記ベクトルの値は”１”となり、前記パリティ検査行列の各行のうち、値が”１”である数が偶数個であるときは前記ベクトルの値は”０”とすることを特徴とする請求項１または請求項２に記載の低密度パリティチェック符号復号器。
【請求項４】
低密度パリティチェック符号復号器であって、
所定のパリティ検査行列を用いて受信データを復号する場合、前記パリティ検査行列と受信データとを掛けて得られたベクトルのうち、値が”零”である値を記憶する記憶手段と、
前記復号を所定回数行った後に、前記受信データの訂正が不能と判別された場合は、前記記憶手段に記憶された値のうち、最大値を読み出し、復号結果として出力する出力手段と、
を含むことを特徴とする低密度パリティチェック符号復号器。
【請求項５】
低密度パリティチェック符号復号方法であって、
所定のパリティ検査行列を用いて受信データを復号する場合、前記パリティ検行列と受信データとを掛けて得られたベクトルのうち、値が”非零”である数をパリティエラー数として記憶し、かつ前記パリティエラー数に対応する硬判定結果情報を記憶手段に記憶する記憶ステップと、
前記復号を所定回数行った後に、前記受信データの訂正が不能と判別された場合は、前記記憶手段に記憶されたパリティエラー数のうち、最小値であるパリティエラー数に対応する硬判定結果情報を読み出し、復号結果として出力する出力ステップと、
を有することを特徴とする低密度パリティチェック符号復号方法。
【請求項６】
低密度パリティチェック符号復号方法であって、
所定のパリティ検査行列を用いて受信データを復号する場合、前記パリティ検査行列と受信データとを掛けて得られたベクトルのうち、値が”非零”である数をパリティエラー数とし、当該パリティエラー数が既に記憶されているパリティエラー数と比較して最小値であると判別された場合は、前記記憶されているパリティエラー数、及びこれに対応する硬判定結果情報に換えて、最小値である前記パリティエラー数及びこれに対応する硬判定結果情報を記憶手段に記憶する記憶ステップと、
前記復号を所定回数行った後に、前記受信データの訂正が不能と判別された場合は、前記記憶手段に記憶された硬判定結果情報を読み出し、復号結果として出力する出力ステップと、
と有することを特徴とする低密度パリティチェック符号復号方法。
【請求項７】
前記パリティ検査行列と受信データとを掛ける場合、前記パリティ検査行列の各行のうち、値が”１”である数が奇数個であるときは、前記ベクトルの値は”１”となり、前記パリティ検査行列の各行のうち、値が”１”である数が偶数個であるときは前記ベクトルの値は”０”とすることを特徴とする請求項４または請求項５に記載の低密度パリティチェック符号復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、低密度パリティチェック（Low Density Parity Check）符号を復号するための低密度パリティチェック符号復号器及び方法に関する。
【背景技術】
【０００２】
最近、誤り検査訂正符号として、低密度パリティチェック符号（以下、ＬＤＰＣ符号と称する）が注目されている。ＬＤＰＣ符号を復号する技術として、メッセージパッシングアルゴリズム（Message-Passing Algorithm）が知られている（例えば、非特許文献１参照）。メッセージパッシングアルゴリズムでは、ＬＤＰＣ符号を復号するために、当該ＬＤＰＣ符号における検査行列（パリティ検査行列）の行毎のビット更新と、列毎のパリティ更新とが反復実行される。
【非特許文献１】アンドリュー・ジェイ・ブランクスビー(Andrew J. Blanksby），クリス・ジェイ・ホーランド(Chris J. Howland)，「A 690-mW 1-Gb/s 1024-b, rate-1/2 低密度パリティチェック符号復号器(A 690-mW 1-Gb/s 1024-b, Rate-1/2 Low-Density Parity-Check Code Decoder)」，IEEE Journal of Solid-State Circuits, Vol. 37, No. 3, March 2002 p.404-412」。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
上述したＬＤＰＣ符号は非常に強力な符号であるが、繰り返し復号を実行している間に、その時々の中間的な復号結果の中の誤りの数は増減することがある。特に訂正不可能なエラーが発生した場合には、このエラー数をグラフにすると、大きな振幅でエラー数が増減する場合がある。このような場合に、たとえば、あらかじめ決められた所定の繰り返し回数に達したことで訂正不能と判定されるケースでは、上述した振幅の高いところ、すなわち、誤り数が増えた状態での復号結果を出力してしまう可能性がある。
【０００４】
本発明は上記事情を考慮してなされたものでその目的は、訂正不可能なエラーが発生した場合であっても、その中に含まれる誤り率を平均的に減少させることができる低密度パリティチェック符号復号器及び方法を提供することである。
【課題を解決するための手段】
【０００５】
本発明の１つの観点によれば、低密度パリティチェック符号復号器であって、所定のパリティ検査行列を用いて受信データを復号する場合、前記パリティ検査行列と受信データとを掛けて得られたベクトルのうち、値が”非零”である数をパリティエラー数として記憶し、かつ前記パリティエラー数に対応する硬判定結果情報を記憶する記憶手段と、前記復号を所定回数行った後に、前記受信データの訂正が不能と判別された場合は、前記記憶手段に記憶されたパリティエラー数のうち、最小値であるパリティエラー数に対応する硬判定結果情報を読み出し、復号結果として出力する出力手段とを含むことを特徴とする。
【０００６】
このように、上記低密度パリティチェック符号復号器は、所定のパリティ検査行列を用いて受信データを復号する場合、パリティ検査行列と受信データとを掛けて得られたベクトルのうち、値が”１”である数をパリティエラー数として記憶し、かつ、このパリティエラー数に対応する硬判定結果情報を記憶する。そして、この復号を所定回数行った後に、受信データの訂正が不能と判別された場合は、記憶されたパリティエラー数のうち、最小値であるパリティエラー数を特定し、このパリティエラー数に対応する硬判定結果情報を読み出し、復号結果として出力する。このため、受信データの訂正が不能と判別された場合に、出力される復号結果をパリティエラー数が最小値である硬判定結果情報を得ることができる。
【発明の効果】
【０００７】
本発明によれば低密度パリティチェック符号復号時に、訂正不能エラーと判定される場合に、その時のビット判定結果を出力するのではなく、パリティエラーの数がもっとも小さかったときの判定結果を出力することにより、符号語内の誤りビットの数を平均的に減らすことができる。
【発明を実施するための最良の形態】
【０００８】
以下図面を参照して、本発明の実施形態を説明する。
【０００９】
（第１実施形態）
図１は、本発明の第１実施形態に係る低密度パリティチェック符号復号器を適用した低密度パリティチェック符号復号システムの構成を示すブロック図である。
【００１０】
低密度パリティチェック符号復号システムは、受信したアナログデータをデジタルデータに変換するＡ／Ｄ変換部１２と、Ａ／Ｄ変換部１２により変換されたデジタルデータを受信し、チャネル出力を行うデータ受信部１４と、受信したデータ等を記憶するメモリ部１８と、当該低密度パリティチェック符号復号システムの制御を行うコントローラであるＣＰＵ（中央処理装置）１６とから構成されている。また、メモリ部１８は、チャネル出力情報を記憶するチャネル出力記憶領域２０と、チャネル出力記憶領域２０に記憶された任意のデータをコピーして保存するｑメモリ記憶手段２２及びｐメモリ記憶手段２４と、パリティ検査行列と受信データとを掛けて得られたベクトルのうち、値が”１”である数をパリティエラー数として記憶し、かつパリティエラー数に対応する硬判定結果情報を記憶する出力候補情報保存領域２６とを備える。
【００１１】
次に、図２は、本発明の第１実施形態に係る低密度パリティチェック符号復号器を適用した低密度パリティチェック（ＬＤＰＣ）符号のパリティ検査行列Ｈの構成を示す模式図である。
【００１２】
このパリティ検査行列Ｈは、ＬＤＰＣ符号がＮ（＝ｓｍ）ビットである場合を前提としている。このＬＤＰＣ符号のｊ番目（ｊ＝１，２，…，Ｎ）のビットをｘjと表現する。パリティ検査行列Ｈの各行は、周知のように、それぞれ１つのパリティチェック方程式であると見なすことができる。パリティ検査行列Ｈの第ｉ行に対応するパリティチェック方程式は、第ｉパリティチェック方程式と呼ばれる。ＮビットのＬＤＰＣ符号は、パリティ検査行列Ｈ内の全てのパリティチェック方程式、つまり第１乃至第Ｍパリティチェック方程式を満足しなければならない。
【００１３】
また、メッセージパッシングアルゴリズムによりＬＤＰＣ符号を復号するには、一般にビット更新とパリティ更新とを反復する必要がある。
【００１４】
通常、ビット更新は次式で表現される。
【数１】
2006135813.tif 000003
【００１５】
ここで、ｒi,j，Ｍ(i)，Ｍ(i)＼ｊ，ｊ'∈M(i)＼ｊ，ｑi,j'，ｓｇｎ(ｑi,j'),Ψ( )は次の通りである。  
ｒi,jは、パリティノードからビットノードに、パリティ検査行列Ｈの第ｉ行の各ビット（但し、第ｉ行のｊ番目の位置のビットを除く）に対応するパリティ情報（信頼性情報）ｑi,j'を受け渡すことにより求められる。ｒi,jは、パリティ検査行列Ｈの第ｉ行内のｊ番目の位置に対応する符号ビットｘjに関する信頼性を表すビット情報（信頼性情報）である。ここでは、ｒi,jは、ビットｘjが０または１である確率それ自体ではなくて、その確率の対数値を表すものとする。ここで対数値を用いるのは、乗除算を加減算に置き換えることを可能とするためである。
【００１６】
Ｍ(i)は、パリティ検査行列Ｈの第ｉ行内で“１”となるビットの行位置の集合を表す。  
Ｍ(i)＼jは、ｊを除くＭ(i)を表す。  
ｊ'∈Ｍ(i)＼ｊは、ｊを除くＭ(i)に含まれている任意の行位置を表す。  
ｑi,j'は、パリティ検査行列Ｈの第ｉ行内のｊ番目の位置に対応する符号ビットｘj'に関する信頼性を表すパリティ情報（信頼性情報）である。ｑi,j'は、ビットｘj'が０または１である確率それ自体ではなくて、その確率の対数値を表すものとする。
【００１７】
ｓｇｎ(ｑi,j')は、ｑi,j'の符号を表す。ｑi,j'の符号は当該ｑi,j'の最上位ビットＭＳＢで示される。もし、ｑi,j'が負であるなら、ｓｇｎ(ｑi,j')＝−１となり、ＭＳＢ(ｑi,j')＝１である。また、ｑi,j'が負でないなら、つまり零または正であるなら、ｓｇｎ(ｑi,j')＝＋１となり、ＭＳＢ(ｑi,j')＝０である。
【００１８】
Ψ( )は、確率演算のための関数（以下、Ψ関数と称する）である。
【００１９】
また、パリティ更新は次式で表現される
【数２】
2006135813.tif 000004
【００２０】
ここで、ｑi,j，ｐj，Ｎ(j)，Ｎ(j)＼ｉ，ｉ'∈Ｎ(j)＼ｉ，ｒi',jは次の通りである。  
ｑi,jは、ビットノードからパリティノードに、パリティ検査行列Ｈの第ｊ行の各ビット（但し、第ｊ列のｉ番目の位置のビットを除く）に対応するビット情報（信頼性情報）ｒi',jを受け渡すことにより求められる。ｑi,jは、パリティ検査行列Ｈの第ｉ行内のｊ番目の位置のビットｘjに関する信頼性を表すパリティ情報（信頼性情報）である。このｑi,jが上記ｑi,j'として上記式（１）に従うビット更新に用いられる。
【００２１】
ｐjは、ＬＤＰＣ符号が通信チャネルを通って出力された際に、その出力から推定される当該符号中のｊ番目のビットｘjが１または０である確率（初期確率）の対数値を表す。パリティ検査行列Ｈにおいて値が“１”の各ビットに対応するｑi,jの初期値はｐjに一致する。
【００２２】
Ｎ(j)は、パリティ検査行列Ｈの第ｊ列で“１”となるビットの列位置の集合を表す。  
Ｎ(j)＼ｉは、ｉを除くＮ(j)を表す。  
ｉ'∈Ｎ(j)＼ｉは、ｉを除くＮ(j)に含まれている任意の列位置を表す。  
ｒi',jは、パリティ検査行列Ｈの第ｉ行内のｊ番目の位置のビットｘjに関する信頼性を表すビット情報（信頼性情報）である。このｒi',jには、上記式（１）に従う計算で更新されたｒi,jが用いられる。
【００２３】
次に、図３のフローチャートを参照して、第１実施形態に係る低密度パリティチェック符号復号方法について説明する。
【００２４】
例えば、パリティ検査行列Ｈは、次式で表される。
【数３】
2006135813.tif 000005
【００２５】
ＣＰＵ１６は、ステップＳ１で、受信データの復号処理を行う。
【００２６】
[数３]で示したパリティ検査行列Ｈに復号を行う受信データとして、例えば、
【数４】
2006135813.tif 000006
を掛けると、
【数５】
2006135813.tif 000007
となる。このとき、[数４]は、一番下の２つの要素が１であるので、パリティ検査行列Ｈである[数３]の右端の２行に対して掛けられる。すなわち、パリティ検査行列Ｈの各行のうち、値が”１”である数が奇数個であるときは、前記ベクトルの値は”１”となり、前記パリティ検査行列の各行のうち、値が”１”である数が偶数個であるときは前記ベクトルの値は”０”とすることにより、[数６]がベクトルとして出力される。出力されたベクトルは、ＣＰＵ１６によって、ステップＳ２で、値”１”の数をパリティエラー数として出力候補情報として、メモリ部１８の出力候補情報保存領域２６に記憶される。例えば、[数６]の場合であると、パリティエラー数は、値”１”が４つ存在するので、「４」として記憶される。また、このパリティエラー数に対応する硬判定結果情報（例えば、「０」と「１」からなるデータ等）も記憶する。
【００２７】
ＣＰＵ１６は、ステップＳ３で、復号が所定回数行われたか否かの判別を行う。ステップＳ３で、ＣＰＵ１６によって復号が所定回数行われていないと判別された場合は、上述した復号を所定回数繰り返す（このとき、パリティエラー数として、「４」、「１０」、「１４」、「２０」、「１７」、「４１」が記憶されるとする）。なお、復号の繰り返し回数情報は、出力候補情報保存領域２６等に記憶しておき、ＣＰＵ１６が必要に応じて参照する。
【００２８】
ステップＳ３で、ＣＰＵ１６によって、所定回数だけ復号が行われた後、復号が所定回数行われたと判別された場合は、ステップＳ４で、メモリ部１８の出力候補情報保存領域２６に記憶されているパリティエラー数のうち、最小値を判別する。例えば、パリティエラー数として、「４」、「１０」、「１４」、「２０」、「１７」、「４１」が記憶されているので、最小値は４となる。そして、最小値として判別されたパリティエラー数に対応する硬判定結果情報を読み出して、復号の結果データとして出力する。
【００２９】
以上より、低密度パリティチェック符号復号時において、復号が所定回数実施され、訂正不能エラーと判定される場合でも、その時のビット判定結果をそのまま出力するのではなく、パリティエラーの数がもっとも小さかったときの判定結果（硬判定結果情報）を出力することにより、符号語内の誤りビットの数を平均的に減らすことができる。すなわち、訂正不可能なエラーが発生した場合であっても、その中に含まれる誤り率を平均的に減少させることができる。したがって、映像や音声データなど、一定速度以上のデータ転送速度が必要なシステムにおいて、比較的誤りの少ないデータを転送し、ユーザに認知されうるようなエラーを減らすことができる。また、低密度パリティチェック復号器の外側に外符号が存在するような連接符号の構成をとるシステムにおいては、外符号での訂正確率を高めることができる。
【００３０】
なお、値が”非零”である”１”を記憶し、記憶された値の最小値を利用する場合に加え、”零”の値である”０”を記憶し、記憶された値の最大値を利用するようにしてもよい。
【００３１】
（第２実施形態）
図４は、本発明の第２実施形態に係る低密度パリティチェック符号復号器を適用した低密度パリティチェック符号復号システムの構成を示すブロック図である。
【００３２】
第２実施形態では、メモリ部１８が備える出力候補情報保存領域２６を出力情報保存領域２８としている。出力情報保存領域２８には、すべての結果データ（パリティエラー数と対応する硬判定結果情報）を記憶することはせずに、記憶する前にパリティエラー数が最小値であるか否かを判別し、最小値であった場合のみ、対応する硬判定結果情報とともに記憶する。このとき、古い結果データは、上書き等で消去する。
【００３３】
次に、図５のフローチャートを参照して、第２実施形態に係る低密度パリティチェック符号復号方法について説明する。
【００３４】
ＣＰＵ１６は、ステップＳ１０で、受信データの復号処理を行い、ステップＳ１１で、結果データであるパリティエラー数が最小値か否かを判別する。この判別には、メモリ部１８が備える出力情報保存領域２８に記憶されているパリティエラー数を参照し、結果データのパリティエラー数の方が小さな値であるかを判別する。ステップＳ１１で、パリティエラー数が最小値であると判別されると、ステップＳ１２で、記憶されている結果データに換えて、新しい結果データを記憶する。続いて、ＣＰＵ１６は、ステップＳ１３で、所定回数だけ復号が行われたか否かを判別する。ステップＳ１３で、ＣＰＵ１６によって、所定回数だけ復号が行われたと判別された場合は、出力情報保存領域２８に記憶されているパリティエラー数に対応する硬判定結果情報を読み出し、復号結果として出力する。
【００３５】
以上により、結果データをすべて記憶しておく必要がないため、メモリ部１８の記憶領域が小さくて済み、かつ復号結果の出力時間を短縮することができる。
【００３６】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【００３７】
【図１】本発明の第１実施形態に係る低密度パリティチェック符号復号器を適用した低密度パリティチェック符号復号システムの構成を示すブロック図。
【図２】本発明の第１実施形態に係る低密度パリティチェック符号復号器を適用した低密度パリティチェック符号のパリティ検査行列Ｈの構成を示す模式図。
【図３】本発明の第１実施形態に係る低密度パリティチェック符号復号方法について説明したフローチャート。
【図４】本発明の第２実施形態に係る低密度パリティチェック符号復号器を適用した低密度パリティチェック符号復号システムの構成を示すブロック図。
【図５】本発明の第２実施形態に係る低密度パリティチェック符号復号方法について説明したフローチャート。
【符号の説明】
【００３８】
１２…Ａ／Ｄ変換部、１４…データ受信部、１６…ＣＰＵ、１８…メモリ部、２０…チャネル出力記憶領域、２２…メモリ記憶手段、２４…メモリ記憶手段、２６…出力候補情報保存領域、２８…出力情報保存領域
【図１】
2006135813.tif 000008
【図２】
2006135813.tif 000009
【図３】
2006135813.tif 000010
【図４】
2006135813.tif 000011
【図５】
2006135813.tif 000012