JP2008219528A - Ｌｄｐｃ符号検出装置及びプログラム - Google Patents

Abstract

【課題】誤り率特性をほとんど劣化させずに、サムプロダクト・アルゴリズムの演算量を大幅に少なくすることができるＬＤＰＣ符号検出装置及びプログラムを提供すること
【解決手段】ビットノードの信頼度βが所定の閾値θより小さいビットノードについては、行処理演算及び列処理演算を行って更新するが、ビットノードの信頼度βが所定の閾値θ以上であるビットノードについては、前回の信頼度βをそのまま次回にも使うことにして信頼度βを更新しないことにより演算量を少なくする。
【選択図】図１

Description

本発明は、ＬＤＰＣ（low density parity check：低密度パリティ検査）符号を用いた符号を復号する符号検出技術に関する。

近年、理論限界に迫る優れた特性を達成する誤り訂正符号としてＬＤＰＣ符号が、通信・放送・記録系で注目されている。ＬＤＰＣ符号は、繰返演算であるサムプロダクト・アルゴリズムを用いることで達成する（例えば、特許文献１参照。）。
特開２００６−２７９３９６号公報

しかし、サムプロダクト・アルゴリズムには非線型関数の演算が含まれ演算量が多く、そのまま実装することは難しい。

本発明は、上記問題点に鑑み、誤り率特性をほとんど劣化させずに、サムプロダクト・アルゴリズムの演算量を大幅に少なくすることができるＬＤＰＣ符号検出装置及びプログラムを提供することを目的とする。

本発明のＬＤＰＣ符号検出装置は、(1).低密度パリティ検査（以下「ＬＤＰＣ」という。）符号のパリティ検査行列のタナーグラフに対応して設定された複数のチェックノードから当該チェックノードに接続されている複数のビットノードに向け信頼度αを伝搬し、(2).該複数のビットノードから該複数のチェックノードに向け信頼度βを伝搬する、(1)、(2)を繰り返す、その過程において信頼度βから算出される事後値の硬判定値をパリティ検査行列でパリティ検査することにより収束判定し送信符号の推定値を決定するサムプロダクト・アルゴリズムを用いて、受信値からの符号検出を行うＬＤＰＣ符号検出装置において、ビットノードの信頼度βが所定の閾値θより小さいビットノードを選択するビットノード選択手段と、該ビットノード選択手段が選択した前記ビットノードに接続されている各前記チェックノードについて、当該チェックノードに接続されている前記ビットノードから当該チェックノードに向け伝搬される前記信頼度βに基づき、当該チェックノードから前記ビットノード選択手段が選択した前記ビットノードに向け伝搬する信頼度αを算出し、伝搬する行処理演算手段と、前記ビットノード選択手段が選択した前記各ビットノードについて、当該ビットノードに接続されている前記各チェックノードから伝搬される信頼度αに基づき、当該ビットノードから前記各チェックノードに向け伝搬する信頼度βを算出して更新し、前記ビットノード選択手段が選択しなかった前記各ビットノードについて、繰返しの前回の事後値を次回の事後値とする列処理演算及びビットノード更新手段と、を備えることを特徴とする。

また、前記繰返しの数をカウントする復号繰返数カウント手段をさらに備え、該復号繰返数が所定値を超えてもなお収束しない場合には、前記ビットノード選択手段はすべてのビットノードを選択することで、通信環境が悪い場合にも復号を達成することができる。

また、本発明は、コンピュータを、上記ＬＤＰＣ符号検出装置として機能させるためのプログラムである。

本発明によれば復号演算量が大幅に少なくなるため、実装が容易になり、消費電力が小さくなり、処理を高速にすることができる。

以下、添付図面を参照しながら本発明を実施するための最良の形態について詳細に説明する。

図１は、本発明の一実施例によるＬＤＰＣ符号検出装置の構成を示す図である。本実施例のＬＤＰＣ符号検出装置は、初期尤度演算手段１０、更新処理削減ビットノード選択手段１１、未更新ビットノード情報記憶手段１２、行処理演算手段１３、列処理演算及びビットノード更新手段１４、硬判定手段１５、パリティ判定手段１６、復号繰返数カウント手段１７、復号処理切替手段１８からなる。

図２は、ＬＤＰＣ符号を説明する図である。ここでまず、ＬＤＰＣ符号を説明する。ＬＤＰＣ符号は、非常に疎な検査行列、すなわち、行列内の非零要素の数が非常に少ない検査行列により定義される線形符号であると同時に、タナーグラフで定義される符号である。そして、局所的に推論した結果をタナーグラフ上でやりとりして更新していくことで、優れた誤り率特性を達成する。図２は、（６,２）ＬＤＰＣ符号の場合について行重みｄc＝３、列重みｄv＝２の検査行列Ｈの例を示す。検査行列Ｈは図に示すようにタナーグラフによっても示すことができる。チェックノードは行に対応し、ビットノードは列に対応し、その間を接続するエッジは行列内の要素１に対応する。例えば、検査行列Ｈの第２行第５列の○を付けた１は、タナーグラフの太線で示すエッジに対応する。

ＳＰＡ（サムプロダクト・アルゴリズム）はチェックノードとビットノード間で情報を受け渡し、各ノードの情報を更新しながら繰返復号を行う復号アルゴリズムである。

まず、従来のＳＰＡについて説明する。検査行列Ｈにおいてｍ行目に“１”を持つ列のインデックスの集合をＮ（ｍ）＝｛ｎ：Ｈm,n＝１｝、ｎ列目に“１”を持つ行のインデックスの集合をＭ（ｎ）＝｛ｍ：Ｈm,n＝１｝と表す。ｌ回目の各ノードの更新処理を以下に示す。初期値β(0)mnは初期尤度β(0)mn＝λn＝（２／σ²）ｒnｙnである。ここで、σ²は雑音分散、ｒnは受信電力、ｙnは受信シンボルを示す。
（１）チェックノードの更新：ｍ番目チェックノードから各ｎ番目のビットノードへ渡すＬＬＲ（対数尤度比）値αmnの更新を下式のように表す。

ここで、ｎ'∈Ｎ(ｍ)＼ｎは、ｍに接続するビットノードｎ'の内ｎ番目のビットノードを含まない集合を表す。また、sign(・)は(・)の符号を返す関数である。

集合Ａの要素ａ,ｂに関して、演算（＋を○で囲う記号）を以下のように定義する。

（２）ビットノードの更新：ｎ番目ビットノードから、各ｍ番目チェックノードへ渡すＬＬＲ値βmnの更新を以下のように表す。

ここで、ｍ'∈Ｍ(ｎ)＼ｍは、ｎに接続するチェックノードｍ'の内ｍ番目のチェックノードを含まない集合を表す。各ビットの事後ＬＬＲを次式で更新する。

（３）硬判定とパリティチェック
（ａ）硬判定により復号系列を推定する。

（ｂ）Ｈω＾＝０もしくは最大繰返数ｌ＝ｌmaxに達したときは、復号結果としてω＾を出力。Ｈω＾≠０の場合、ｌ＝ｌ＋１として再び各ノードの更新処理を行う。

つぎに、δ−ｍｉｎ復号アルゴリズムについて説明する。式（３）に示したチェックノードの更新式は、非線形関数であるため実装が困難である。式（３）を簡易化した復号アルゴリズムとしてδ−ｍｉｎ復号アルゴリズムが提案されている。δ−ｍｉｎ復号アルゴリズムは、ＳＰＡと比べブロック誤り率（ＢＬＥＲ）特性の劣化が小さい（約０．０５ｄＢ）とされている。δ−ｍｉｎ復号アルゴリズムは、密度発展法による補正因子が不要であるため，本発明との併用が容易である。

式（３）を線形近似するために，対数関数ln(１＋exp(−ｘ))に関してTayler級数展開を行う。

実装を考慮すると演算量の小さい１次項までを用い，定数項はｘ＞０の領域で関数ln(１＋exp(−ｘ))との誤差を補正した値（＝０．９）を用いる。関数ln(１＋exp(−ｘ))の線形近似式を以下に示す。

本発明は，ＳＰＡや低演算量アルゴリズム（δ−ｍｉｎ復号アルゴリズム）と併用することでＬＤＰＣ符号の復号に必要なメモリー量及び消費電力を削減する。本発明は，２種類の閾値（ＬＬＲ閾値θLLR，繰返閾値θiter）を用いて更新処理を削減し，従来の復号アルゴリズムとほぼ等しい誤り率特性を達成する。本発明アルゴリズムは，ｌ−１回目の繰返処理のｎ番目のビットに対応するビットノードの事後ＬＬＲβ^{（ｌ−１）}nがＬＬＲの閾値θLLRより大きい場合（β^{（ｌ−１）}n≧θLLR），ｌ回目の更新処理を行わないことによって更新処理数を削減する。繰返閾値θiterは，ある回数θiter［回］以上繰返復号を行っても復号処理が終了しない場合，すべてのノードに対して更新処理を行うための閾値である。

本発明のアルゴリズムを以下に示す。
（１）ＬＬＲ閾値θLLRとビットノードのＬＬＲβnの比較：
（ａ）繰返数ｌ−１＜θiter：ｌ−１回目のビットノードの事後ＬＬＲβ^{（ｌ−１）}nとＬＬＲ閾値θLLRを比較する。
・｜β^{（ｌ−１）}n｜≧θLLRなるビットｎのインデックスの集合をＮ＿＝｛ｎ：｜β^{（ｌ−１）}n｜≧θLLR｝と表す。
・｜β^{（ｌ−１）}n｜＜θLLRなるビットｎに関してｍ行目に“１”を持つ列のインデックスの集合をＮ￣（ｍ）＝｛ｎ：Ｈm,n＝１∩｜β^{（ｌ−１）}n｜＜θLLR｝，ｎ列目に“１”を持つ行のインデックスの集合をＭ￣（ｎ）＝｛ｍ：Ｈm,n＝１∩｜β^{（ｌ−１）}n｜＜θLLR｝と表す。
（ｂ）繰返数ｌ−１≧θiter：全ての更新処理を行う。
（２）チェックノードの更新：ｍ番目チェックノードから各ｎ番目のビットノードへ渡すＬＬＲ値αmnの更新は，各ｎ番目のビットノードが｜β^{（ｌ−１）}n｜＜θLLRである場合，下式のように表される。

一方、ビットノードの事後ＬＬＲ値が｜β^{（ｌ−１）}n｜≧θLLRである各ビットノードに渡すＬＬＲ値αmnの更新、すなわち、行処理演算は行わない。
（３）ビットノードの更新：ｎ番目ビットノードから，各ｍ番目チェックノードに渡すＬＬＲ値βmnの更新を以下のように表す。
（ａ）｜β^{（ｌ−１）}n｜＜θLLRの場合。

｜β^{（ｌ−１）}n｜＜θLLRのビットの事後ＬＬＲを次式で更新する。

（ｂ）｜β^{（ｌ−１）}n｜≧θLLRの場合。ｌ−１回目のビットノードの事後ＬＬＲ値β^{（ｌ−１）}nをｌ回目のビットノードの事後ＬＬＲ値β^（ｌ）nとする。

（４）硬判定とパリティチェック
従来ＳＰＡと同様。

つぎに、図１に戻って、本実施例を実現する具体的な構成を説明する。まず、初期尤度演算手段１０は、受信信号を受信して、初期尤度β(0)mn＝λn＝（２／σ²）ｒnｙnを演算し、各ビットノードの初期尤度として設定する。つぎに、更新処理削減ビットノード選択手段１１は、ＬＬＲ閾値θLLRとビットノードのＬＬＲβnを比較して、｜β^{（ｌ−１）}n｜≧θLLRとなるビットノードについては更新のための演算を行わず前回の事後ＬＬＲをそのまま使う（式１２）。｜β^{（ｌ−１）}n｜＜θLLRとなるビットノードについては更新するため、接続されているチェックノードから当該ビットノードに渡す行処理演算を行う。未更新ビットノード情報記憶手段１２は、更新しないビットノードの事後ＬＬＲ値を次回にそのまま使うので、未更新ビットノード情報として記憶する。行処理演算手段１３は、更新するビットノードに接続されているチェックノードから当該ビットノードに渡す行処理演算をして更新する（式９）。列処理演算及びビットノード更新手段１４は、更新するビットノードについて列処理演算して更新する。硬判定手段１５は、各ビットノードの事後ＬＬＲ値に基づいて硬判定して一時推定値を求める（式６）。パリティ判定手段１６は、硬判定の結果の一時推定値と検査行列Ｈとから一時推定値のパリティを計算して、パリティが０か１かを判定する。パリティが０であれば、一時推定値を復号語として出力して動作を終了する。パリティが１の場合、復号繰返数カウント手段１７は、繰返数ｌをカウントして、復号処理切替手段１８は、ｌ−１を所定の閾値θiterと比較して、ｌ−１＜θiterの場合には、更新するビットノードと更新しないビットノードとを選択し、ｌ−１≧θiterの場合にはすべてのビットノードを更新するように信号処理を切り替える。

図３は、本発明と従来例の誤り率を比較する図である。図３は、符号化率Ｒ＝１／２、（３,６）レギュラーＬＤＰＣなどの各種ＬＤＰＣ符号について、本発明ＳＰＡと従来ＳＰＡのＡＷＧＮ（Additive White Gaussian Noise）通信路、ＢＰＳＫ（Bi-Phase Shift Keying）変調におけるＥb／Ｎo（信号雑音比）に対するＢＥＲ（Bit Error Rate）特性を示す。本発明においてＢＥＲがほとんど劣化していないことが分かる。

図４は、本発明と従来例のブロック誤り率を比較する図である。図４は、各種ＬＤＰＣ符号について、本発明ＳＰＡと従来ＳＰＡのＡＷＧＮ通信路、ＢＰＳＫ変調におけるＥb／Ｎoに対するＢＬＥＲ（BLock Error Rate）特性を示す。本発明においてＢＬＥＲがほとんど劣化していないことが分かる。

図５は、本発明と従来例の演算量を比較する図である。図５は、各種ＬＤＰＣ符号について、本発明ＳＰＡと従来ＳＰＡのＥb／Ｎoに対する演算量を示す。本発明の演算量は従来に比べて、約８０〜１０％と少なくなっていることが分かる。環境が良ければ演算量は従来に比べて約１／１０に減らすことができる。

なお、本発明は上記実施例に限定されるものではない。

δ−ｍｉｎ復号アルゴリズムを用いなくても、本発明は十分に演算量を少なくする効果を奏する。

ＬＬＲは、チェックノード又はビットノードの信頼度を表すパラメータであれば良く、ＬＬＲに限られない。

また、本発明のＬＤＰＣ符号検出装置は、コンピュータを本ＬＤＰＣ符号検出装置として機能させるためのプログラムでも実現される。このプログラムは、コンピュータで読み取り可能な記録媒体に格納されていてもよい。

このプログラムを記録した記録媒体は、図１に示されるＬＤＰＣ符号検出装置のＲＯＭそのものであってもよいし、また、外部記憶装置としてＣＤ−ＲＯＭドライブ等のプログラム読取装置が設けられ、そこに記録媒体を挿入することで読み取り可能なＣＤ−ＲＯＭ等であってもよい。

また、上記記録媒体は、磁気テープ、カセットテープ、フレキシブルディスク、ハードディスク、ＭＯ／ＭＤ／ＤＶＤ等、又は半導体メモリであってもよい。

本発明の一実施例によるＬＤＰＣ符号検出装置の構成を示す図である。 ＬＤＰＣ符号を説明する図である。 本発明と従来例の誤り率を比較する図である。 本発明と従来例のブロック誤り率を比較する図である。 本発明と従来例の演算量を比較する図である。

符号の説明

１０ 初期尤度演算手段
１１ 更新処理削減ビットノード選択手段
１２ 未更新ビットノード情報記憶手段
１３ 行処理演算手段
１４ 列処理演算及びビットノード更新手段
１５ 硬判定手段
１６ パリティ判定手段
１７ 復号繰返数カウント手段
１８ 復号処理切替手段

Claims (3)

1. (1).低密度パリティ検査（以下「ＬＤＰＣ」という。）符号のパリティ検査行列のタナーグラフに対応して設定された複数のチェックノードから当該チェックノードに接続されている複数のビットノードに向け信頼度αを伝搬し、
   (2).該複数のビットノードから該複数のチェックノードに向け信頼度βを伝搬する、
   (1)、(2)を繰り返す、その過程において信頼度βから算出される事後値の硬判定値をパリティ検査行列でパリティ検査することにより収束判定し送信符号の推定値を決定するサムプロダクト・アルゴリズムを用いて、受信値からの符号検出を行うＬＤＰＣ符号検出装置において、
   ビットノードの信頼度βが所定の閾値θより小さいビットノードを選択するビットノード選択手段と、
   該ビットノード選択手段が選択した前記ビットノードに接続されている各前記チェックノードについて、当該チェックノードに接続されている前記ビットノードから当該チェックノードに向け伝搬される前記信頼度βに基づき、当該チェックノードから前記ビットノード選択手段が選択した前記ビットノードに向け伝搬する信頼度αを算出し、伝搬する行処理演算手段と、
   前記ビットノード選択手段が選択した前記各ビットノードについて、当該ビットノードに接続されている前記各チェックノードから伝搬される信頼度αに基づき、当該ビットノードから前記各チェックノードに向け伝搬する信頼度βを算出して更新し、前記ビットノード選択手段が選択しなかった前記各ビットノードについて、繰返しの前回の事後値を次回の事後値とする列処理演算及びビットノード更新手段と、
   を備えることを特徴とするＬＤＰＣ符号検出装置。
2. 前記繰返しの数をカウントする復号繰返数カウント手段をさらに備え、該復号繰返数が所定値を超えてもなお収束しない場合には、前記ビットノード選択手段はすべてのビットノードを選択することを特徴とするＬＤＰＣ符号検出装置。
3. コンピュータを、請求項１又は２記載のＬＤＰＣ符号検出装置として機能させるためのプログラム。
   

Images