(57)【特許請求の範囲】
【請求項１】
多数の検査ノードが各々の変数ノードからＬＬＲ（Ｌｏｇ−Ｌｉｋｅｌｉｈｏｏｄ  Ｒａｔｉｏ）メッセージを受信するステップと、
前記各検査ノードに対して前記ＬＬＲメッセージを直列に構成するステップと、
前記ＬＬＲメッセージに基づき、指数関数または指数関数の和で近似させたｇ’（ｘ）関数を含む関数を通じて前記検査ノードの更新を行うステップとを含み、
前記ｇ’（ｘ）関数は、第１ターム（１ｓｔ  Ｔｅｒｍ）、第２ターム（２ｎｄ  Ｔｅｒｍ）、及び第３ターム（３ｒｄ  Ｔｅｒｍ）の和で構成される以下の数式（１）であることを特徴とする低密度パリティ検査（ＬＤＰＣ：Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ）復号器における検査ノード更新方法。
【数１】
0004651600.tif 000013
この時、αは、４｜ｘ｜＋２である。
【請求項２】
前記指数関数は、２の指数関数からなることを特徴とする請求項１に記載の低密度パリティ検査復号器における検査ノード更新方法。
【請求項３】
前記２の指数関数は、以下の数式（２）であることを特徴とする請求項２に記載の低密度パリティ検査復号器における検査ノード更新方法。
【数２】
0004651600.tif 000014
この時、α値は、４｜ｘ｜＋２である。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は低密度パリティ検査復号器における検査ノード更新方法に関し、より詳細には高速のデータを伝送するデジタル通信システムの確率伝播（Ｂｅｌｉｅｆ  Ｐｒｏｐａｇａｔｉｏｎ  以下、「ＢＰ」という。）アルゴリズムを使う低密度パリティ検査（Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ  以下、ＬＤＰＣ）符号復号器において、検査ノード更新規則（Ｃｈｅｃｋ  ｎｏｄｅ  ｕｐｄａｔｅ  ｒｕｌｅ）を指数関数の和で近似させ、演算の複雑度を下げると共にＢＰアルゴリズムの性能と等しくなるようにする低密度パリティ検査復号器における検査  ノード更新方法に関する。
【背景技術】
【０００２】
一般的に、ＬＰＤＣ符号とは、図１Ａに示すように符号（Ｃｏｄｅ）を定義するパリティ検査行列（Ｐａｒｉｔｙ  Ｃｈｅｃｋ  Ｍａｔｒｉｘ）の各行と列に「１」の数が少ない符号であって、検査ノード（Ｃｈｅｃｋ  Ｎｏｄｅ）と変数ノード（Ｖａｒｉａｂｌｅ  Ｎｏｄｅ）、そしてそれを連結するエッジ（Ｅｄｇｅ）で構成されたファクターグラフ（Ｆａｃｔｏｒ  Ｇｒａｐｈ）によってその構造が定義される符号である（例えば、特許文献１及び２参照）。
【０００３】
また、ＬＤＰＣ符号はＢＰアルゴリズムを使って復号できるが、該ＢＰアルゴリズムを使うと非常に大きい符号語も実用的かつ正確に復号することができ、完全並列処理が可能なので処理速度も上げることができる。このＢＰアルゴリズムを使う復号器はチャネルからの尤度（Ｌｉｋｅｌｉｈｏｏｄ）を利用することができる軟判定復号器で、限界距離復号器（Ｂｏｕｎｄｅｄ  Ｄｉｓｔａｎｃｅ  Ｄｅｃｏｄｅｒ）より優れた性能を持つ（例えば、非特許文献１参照）。このように優れた復号器が存在するため、符号長を長くすることができ、ブロックサイズを大きくするとシャノンのチャネル容量の限界に迫る性能が得られる。また、ブロックサイズを大きくすると、最小距離（ｍｉｎｉｍｕｍ  ｄｉｓｔａｎｃｅ）が増加することになり、最小距離の小さいターボ符号よりも誤り率特性がよくなる。
【０００４】
一方、ＢＰアルゴリズムは、ファクターグラフ上で互いに連結されている各ノードの間のエッジを介して伝達されたメッセージ値が、各々のノーで新しい値に反復的に更新（ｕｐｄａｔｅ）される過程を通じて行われる。ここで一回の反復（ｉｔｅｒａｔｉｏｎ）過程とは、各々のノードにおける値が全部更新されたときを定義する。２進（Ｂｉｎａｒｙ）通信システムである場合、メッセージは一般的に対数尤度比（ＬＬＲ：Ｌｏｇ−Ｌｉｋｅｌｉｈｏｏｄ  Ｒａｔｉｏ）を用いて表現され、下記の式（３）の通りである。
【０００５】
【数３】
0004651600.tif 000002
【０００６】
この場合、ＢＰアルゴリズムの変数ノードでの更新規則は和のみからなっていて容易に具現できるが、検査ノードでの更新規則は双曲正接（Ｈｙｐｅｒｂｏｌｉｃ  Ｔａｎｇｅｎｔ）及び多くの乗算が存在する。従って、ＢＰアルゴリズムは、Ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムとも呼ばれる。
【０００７】
下記の式（４）は、任意の検査ノードＣｉにおいて、Ｃｉにエッジで連結されているｄｃ個の変数ノード（Ｖ０，Ｖ１，〜Ｖｄ−２，Ｖｄ−１）のうちＶｊへのメッセージ、ＬＬＲ（λｃ→ｖ）を更新する規則であり、その更新過程を図１Ｂに示す。
【０００８】
【数４】
0004651600.tif 000003
【０００９】
図１Ｂにおいて、検査ノードＣｉとｄｃ個の変数ノード（Ｖ０，Ｖ１，〜Ｖｄ−２，Ｖｄ−１）を繋ぐエッジ上のメッセージを全部更新しなければならないので、式（６）をｄｃ回行うべきであり、これは一つの検査ノード当たりｄｃ×（ｄｃ−１）回の乗算が求められるのと同様である。
【００１０】
それとは異なり、検査ノードＣｉとｄｃ個の変数ノード（Ｖ０，Ｖ１，〜Ｖｄ−２，Ｖｄ−１）を繋ぐエッジ上のメッセージを図１Ｃに示すように式（５）の数式を使用する検査ノードを直列に構成して更新することもできる。これは前者の方式より少ない乗算で更新を行うことができる。ｆｊ−１は、Ｖ０，Ｖ１，〜Ｖｄ−２，Ｖｄ−１のうちのＶｊを示し、順次チェックノードを更新する過程においてＶ０から始まることを示しています。ｂｊ−１は、Ｖ０，Ｖ１，〜Ｖｄ−２，Ｖｄ−１のうちのＶｊを示し、順次チェックノードを更新する過程においてＶｄｃ−１から始まることを示しています。
【００１１】
【数５】
0004651600.tif 000004
【００１２】
図１Ｃでの各検査ノードの更新値は、式（５）に示されたＳｉｇｎ・Ｍｉｎ関数と、式（５）の（Ａ）と（Ｂ）に示された関数ｇ（ｘ）との和で示すことができる。この時、関数ｇ（ｘ）は下記の式（６）の通りである。
【００１３】
【数６】
0004651600.tif 000005
【００１４】
一方、式（５）を用いた図１Ｃのような検査ノード更新方法は、式（４）を用いるＢＰアルゴリズムに比べ少ない演算を求めるが、相変わらず具現しにくい関数ｇ（ｘ）の計算を含んでいる。
【００１５】
従って、ｇ（ｘ）を容易に具現するための様々な方法が研究されてきた。式（５）の計算を容易にするために、ｇ（ｘ）を「０」にして置き、両入力値の符号と最小値のみ取るＳｉｇｎ−Ｍｉｎ方式（ＵＭＰ−ＢＰという）、Ｓｉｇｎ−Ｍｉｎ方式を補正するために１より大きい所定の値で割るＮｏｒｍａｌｉｚｅ−ＢＰアルゴリズムもあるが、既存のアルゴリズムに比べ性能の劣化が大きいという問題点がある。
【００１６】
一方、ｇ（ｘ）を容易に具現するためのｇ（ｘ）を近似させる方法として、量子（Ｑｕａｎｔｉｚａｔｉｏｎ）方式、線形近似（Ｌｉｎｅａｒ  Ａｐｐｒｏｘｉｍａｔｉｏｎ）、及び区分（Ｐｉｅｃｅｗｉｓｅ）線形近似方式などがある。この中で区分線形近似方式は、既存の方法に比べ性能が優れＢＰアルゴリズムに等しい性能を持つが、区間毎に異なる関数を使い且つルックアップ（Ｌｏｏｋ−ｕｐ）テーブルが必要であるという問題点がある。
【特許文献１】韓国公開特許第２００４−０５６９７２
【特許文献２】米国公開特許第２００４−０３４８２７
【非特許文献１】計算を簡素化するためにｓｕｂ−Ｍｉｎ−Ｓｕｍデコーディングを使ってＬＬＲメッセージであるλのｔａｎ項を指数形態に変えて近似化させるＬＤＰＣデコーディングアルゴリズム  Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ａｌｂｅｒｔａ  ｆｏｒ  ｔｈｅ  ３ｒｄ  Ａｎｎｕａｌ  Ａｎａｌｏｇ  Ｄｅｃｏｄｉｎｇ  Ｗｏｒｋｓｈｏｐ出版、２００４年６月８日出版、Ｓｈｅｒｙｌ  Ｈｏｗａｒｄ，  Ｔｏｎｙ  Ｒａｐｌｅｙ，及びＣｈｒｉｓｔｉａｎ  Ｓｃｈｌｅｇｅｌ  ａｎｄ  Ｖｉｎｃｅｎｔ  Ｇａｕｄｅｔ著
【発明の開示】
【発明が解決しようとする課題】
【００１７】
本発明は、前述の問題点を解決するために提出されたもので、本発明の目的は、高速のデータを伝送するデジタル通信システムの確率伝播（ＢＰ）アルゴリズムを使う低密度パリティ検査（ＬＤＰＣ）符号復号器において、検査ノード更新規則を指数関数の和で近似させ、演算の複雑度を下げると共にＢＰアルゴリズムと性能が等しくなるようにする低密度パリティ検査復号器における検査ノード更新方法を提供することにある。
【課題を解決するための手段】
【００１８】
上記目的を達成するために、本発明に係る低密度パリティ検査（ＬＤＰＣ：Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ）復号器における検査ノード更新方法は、多数の検査ノードが各々の変数ノードからＬＬＲ（Ｌｏｇ−Ｌｉｋｅｌｉｈｏｏｄ  Ｒａｔｉｏ）メッセージを受信するステップと、前記各検査ノードに対して前記ＬＬＲメッセージを直列に構成するステップと、前記ＬＬＲメッセージに基づき、指数関数または指数関数の和で近似させたｇ’（ｘ）関数を含む関数を通じて前記検査ノードの更新を行うステップとを含み、前記ｇ’（ｘ）関数は、第１ターム（１ｓｔ  Ｔｅｒｍ）、第２ターム（２ｎｄ  Ｔｅｒｍ）、及び第３ターム（３ｒｄ  Ｔｅｒｍ）の和で構成される以下の数式（１）であることを特徴とする低密度パリティ検査（ＬＤＰＣ：Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ）復号器における検査ノード更新方法。
【数７】
0004651600.tif 000006
この時、αは、４｜ｘ｜＋２である。
【００１９】
前記指数関数は、２の指数関数からなることが好ましい。
前記２の指数関数は、式（８）であることが好ましい。
【数８】
0004651600.tif 000007
この時、αは、４｜ｘ｜＋２である。
【００２０】
式（７）の前記αは、４｜ｘ｜＋２であることが好ましい。
式（８）の前記αは、４｜ｘ｜＋２であることが好ましい。
【発明の効果】
【００２１】
本発明によると、検査ノード更新時に使う規則が指数関数の和でのみに構成され、加算器とシフト・レジスタで容易に具現することができ、すべての区間に対して一つの式のみ利用するので、ルックアップテーブル（ｌｏｏｋ−Ｕｐ  ｔａｂｌｅ）が別に必要ではなく、既存のＢＰアルゴリズムを使う場合に比べ性能劣化の発生を抑えることができる。
【発明を実施するための最良の形態】
【００２２】
以下、添付の図面に基づいて本発明の好適な実施形態を詳述する。
まず、各図面の構成要素に参照符号を付するにおいて、同一構成要素に対しては他の図面上に表示されるとしてもできる限り同一符号を有するようにすることに留意しなければならない。
また、関連する公知の構成または機能に対する具体的な説明は適宜省略する。
【００２３】
図２は、本発明を説明するための低密度パリティ検査復号器の機能ブロックを示す機能ブロック図である。
同図に示すように、ＬＤＰＣ復号器２００は、Ｃ  Ｔｏ  Ｖエッジメッセージメモリ（Ｃｈｅｃｋ  Ｎｏｄｅ  Ｔｏ  Ｖａｒｉａｂｌｅ  Ｎｏｄｅ  Ｅｄｇｅ  Ｍｅｓｓａｇｅ  Ｍｅｍｏｒｙ）２１０、変数ノード処理部（Ｖａｒｉａｂｌｅ  Ｎｏｄｅ  Ｐｒｏｃｅｓｓｏｒ）２２０、出力バッファ（Ｏｕｔｐｕｔ  Ｂｕｆｆｅｒ）２３０、復号制御部（Ｄｅｃｏｄｅｒ  Ｃｏｎｔｒｏｌ  Ｍｏｄｕｌｅ）２４０、検査ノード処理部（Ｃｈｅｃｋ  Ｎｏｄｅ  Ｐｒｏｃｅｓｓｏｒ）２５０、及びＶ  Ｔｏ  Ｃエッジメッセージメモリ（Ｖａｒｉａｂｌｅ  Ｎｏｄｅ  Ｔｏ  Ｃｈｅｃｋ  Ｎｏｄｅ  Ｅｄｇｅ  Ｍｅｓｓａｇｅ  Ｍｅｍｏｒｙ）２６０を含む。
【００２４】
つまり、ＬＤＰＣ復号器２００は、各エッジを介して受信された符号語の各ビットに対し、該当ビットが「０」又は「１」である確率を計算する。ＬＤＰＣ復号器２００が計算した確率情報を「メッセージ」と呼び、パリティ検査行列で定義された各パリティを介してメッセージの品質を検査することができる。
【００２５】
この時、Ｃ  Ｔｏ  Ｖエッジメッセージメモリ２１０は、検査ノードからエッジを介して変数ノードへ伝達されるメッセージを保存し、Ｖ  Ｔｏ  Ｃエッジメッセージメモリ２６０は、変数ノードからエッジを介して検査ノードへ伝達されるメッセージを保存する。
【００２６】
一方、各変数ノードは、入力された符号化シンボルのＬＬＲ値を受信し、変数ノード処理部２２０は各変数ノードを介して受信されたＬＬＲ値を変数ノード更新規則に従って更新して検査ノードに伝達する。これに対し、検査ノード処理部２５０は各変数ノードから受信した符号化シンボルを本発明に係る検査ノード更新を行うために、図１Ｃに示すように各検査ノードに対して直列に構成した後、式（５）の計算の中の関数ｇ（ｘ）を指数関数の和で近似させたｇ’（ｘ）に代替して演算した結果を再び変数ノードに伝送する。
【００２７】
出力バッファ２３０は、変数ノードの各符号化シンボルを臨時保存する。
そして、復号制御部２４０は、変数ノード処理部２２０と検査ノード処理部２５０とを含む各処理部を制御してメッセージ反復更新が行われるようにする。
【００２８】
本発明の実施形態に係る検査ノード更新に用いられる関数は、式（６）のように展開されるログ形態のｇ（ｘ）関数をテイラー（Ｔａｙｌｏｒ）定理に従って式（９）のように指数形態の関数に置き換え、式（９）において第３ターム（Ｔｅｒｍ）部分（Ａ）を式（１０）のように２−α（Ｂ）に近似させ３つのタームからなる関数を得る。次に、式（１０）のように示された関数において、αを「４｜ｘ｜＋２」に置き換えて整理すると、式（１１）に示された２の指数関数で表示することができる。これはシフト・レジスタのみで値が得られ便利である。従って、本発明の更新に係る関数は、式（５）の関数ｇ（ｘ）を幾何級数的（Ｅｘｐｏｎｅｎｔｉａｌ）指数関数に近似させたものであり、式（９）、式（１０）、式（１１）に示されたように指数関数の和のみからなる関数である。
【００２９】
【数９】
0004651600.tif 000008
【００３０】
【数１０】
0004651600.tif 000009
【００３１】
【数１１】
0004651600.tif 000010
【００３２】
従って、ＬＤＰＣ復号器２００における検査ノードは各変数ノードからＬＬＲメッセージを受信し、各メッセージに基づいて演算を行う。つまり、ＬＤＰＣ復号器２００は図１Ｃに示すように各検査ノードに対して直列に構成した後、式（５）の計算の中で関数ｇ（ｘ）を式（９）、式（１０）、式（１１）に示された指数関数の和で近似させたｇ’（ｘ）関数に従って更新を行う。この時、ｇ’（ｘ）関数は、式（１０）に示されたように第１ターム、第２ターム及び第３タームからなり、式（１１）のように２の指数関数に示すことができる。また、ｇ’（ｘ）関数において、第１タームは常に使い、第２タームと第３タームは必要に応じて使う。
【００３３】
図３は、本発明の実施形態に従って検査ノード更新に適用されたｇ’（ｘ）関数の試験結果グラフを示したもので、本発明に係る指数形態の関数で第１ターム、第２ターム及び第３タームに対する関数の結果値が本来のｇ（ｘ）関数に近似していることを示す。
【００３４】
図４は、本発明に係る更新アルゴリズムと他のアルゴリズムのフレーム誤り率（ＦＥＲ）グラフを示したものであり、図６は本発明に係る更新アルゴリズムと他のアルゴリズムのビット誤り率（ＢＥＲ）グラフを示したものである。
【００３５】
図４及び図５は、ＩＥＥＥ８０２．１１ｎ技術グループのＴＧｎ  Ｓｙｎｃ行列を利用し（１１−０４−０８８９−０５−０００ｎ−ｔｇｎｓｙｎｃ−ｐｒｏｐｏｓａｌ−Ｔｅｃｈｎｉｃａｌ−ｓｐｅｃｉｆｉｃａｔｉｏｎ．ｄｏｃ）、符号率（Ｃｏｄｅ  Ｒａｔｅ）Ｒは１／２、コードワードサイズ（Ｃｏｒｄｗｏｒｄ  Ｓｉｚｅ）は１７８、ブロックサイズ（Ｂｌｏｃｋ  Ｓｉｚｅ）は７２に設定し、加法性白色ガウス雑音（ＡＷＧＮ：Ａｄｄｉｔｉｖｅ  Ｗｈｉｔｅ  Ｇａｕｓｓｉａｎ  Ｎｏｉｓｅ）とＢＰＳＫ（Ｂｉｎａｒｙ  Ｐｈａｓｅ  Ｓｈｉｆｔ  Ｋｅｙ）などを仮定して得られた試験結果である。また、図５は、ＢＰ、Ｐｉｅｃｅｗｉｓｅ−ｌｉｎｅａｒ近似、本発明に係る更新関数の第１ターム、第２ターム、第３タームの近似、Ｎｏｒｍａｌｉｚｅｄ  ＢＰ、及びＵＭＰ−ＢＰの対するフレーム誤り率（Ｆｒａｍｅ  Ｅｒｒｏｒ  Ｒａｔｅ：ＦＥＲ）を示したもので、本発明の更新関数に係る第１ターム乃至第３タームに対する結果値がＢＰアルゴリズムによる性能結果値にほぼ一致していることが分かる。
【００３６】
そして、図６に示されたビット誤り率（Ｂｉｔ  Ｅｒｒｏｒ  Ｒａｔｅ）も同じく、図３に示された本発明の更新関数に係る第１ターム乃至第３タームまでに対する結果値がＢＰアルゴリズムによる性能結果値にほぼ一致していることが分かる。
【００３７】
以上から、本発明によると、高速のデータを伝送するデジタル通信システムの確率伝播（ＢＰ）アルゴリズムを使う低密度パリティ検査（ＬＤＰＣ）符号復号器において、検査ノード更新規則を指数関数の和で近似させ、演算の複雑度を下げると共にＢＰアルゴリズムと性能が等しくなるようにする低密度パリティ検査復号器における検査ノード更新方法を実現することができる。
なお、第１タームのみからなるもの、第１ターム及び第２タームからなるもの、すなわち、以下の式（１２）または式（１３）を式（１０）の代わりに用いても良い。
【００３８】
【数１２】
0004651600.tif 000011
【００３９】
【数１３】
0004651600.tif 000012
【００４０】
以上、本発明の好適な実施形態を図示及び説明してきたが、本発明の技術的範囲は前述の実施形態に限定するものではなく、特許請求の範囲に基づいて定められ、特許請求の範囲において請求する本発明の要旨から外れることなく当該発明が属する技術分野において通常の知識を有する者であれば誰もが多様な変形実施が可能であることは勿論のことであり、該変更した技術は特許請求の範囲に記載された発明の技術的範囲に属するものである。
【図面の簡単な説明】
【００４１】
【図１Ａ】パリティ検査行列及びファクターグラフの構造を示す図面である。
【図１Ｂ】ＢＰアルゴリズムにおいて検査ノードのメッセージ更新過程を示す図面である。
【図１Ｃ】検査ノードの直列式更新過程を示す図面である。
【図２】本発明を説明するための低密度パリティ検査復号器の機能ブロックを示す機能ブロック図である。
【図３】本発明の実施形態に従って検査ノードの更新に適用された関数の試験結果とグラフを示す図面である。
【図４】本発明に係る更新アルゴリズムと他のアルゴリズムのフレーム誤り率（ＦＥＲ）グラフを示す図面である。
【図５】本発明に係る更新アルゴリズムと他のアルゴリズムのビット誤り率（ＢＥＲ）グラフを示す図面である。
【符号の説明】
【００４２】
２００    低密度パリティ検査復号器
２１０    Ｃ  Ｔｏ  Ｖエッジメッセージメモリ
２２０    変数ノード処理部
２３０    出力バッファ
２４０    復号制御部
２５０    検査ノード処理部
２６０    Ｖ  Ｔｏ  Ｃエッジメッセージメモリ
【図１Ａ】
0004651600.tif 000015
【図１Ｂ】
0004651600.tif 000016
【図１Ｃ】
0004651600.tif 000017
【図２】
0004651600.tif 000018
【図３】
0004651600.tif 000019
【図４】
0004651600.tif 000020
【図５】
0004651600.tif 000021