チェック・ノードでＢＣＪＲアルゴリズムを使用する高速収束ＬＤＰＣ復号方法。
ＤＶＢ−Ｓ２標準規格で使用されるＩＲＡ符号などのＬＤＰＣ符号を復号する方法であって、符号グラフは、第１変数ノード（システマティック）、次数２を有する第２変数ノード（パリティ）、およびジグザグ接続性によって第２変数ノードに接続されたチェック・ノードを含み、ａ）各グループのチェック・ノードは、内部変数ノードと呼ばれる変数ノードによって接続される、グループ化され、ｂ）グループ（ＧＲｊ）ごとに、ｂ１）２状態トレリスに対して事後最大（ＭＡＰ）タイプのアルゴリズムを使用することによって前記グループのすべてのチェック・ノードを合同で更新するサブステップ（７１）と、ｂ２）前記少なくとも１つの内部第２変数ノードを除く前記グループに接続されたすべての第１変数ノードおよびすべての第２変数ノード（ＰＮｉ−１，ｉ、ＰＮｉ，ｉ＋１）を更新するサブステップ（７２、７３）とを実行し、ｃ）ステップｂ）を反復して繰り返す。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ通信方法を対象とし、詳細には、ＬＤＰＣ（Ｌｏｗ−Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ−Ｃｈｅｃｋ）符号を用いて符号化された符号語の復号方法を対象とする。
【０００２】
本発明は、さらに詳細には、ＩＲＡ（Ｉｒｒｅｇｕｌａｒ Ｒｅｐｅａｔ Ａｃｃｕｍｕｌａｔｅ）符号を利用するデータ通信システムを対象とするがこれに限定されない。ＩＲＡ符号とは、たとえば、ｓｅｃｏｎｄ ｉｎｔｅｒｎａｔｉｏｎａｌ ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｔｕｒｂｏ Ｃｏｄｅｓ、フランス国ブレスト、２０００年９月で提示されたＨｕｉ Ｊｉｎ他の「Ｉｒｒｅｇｕｌａｒ Ｒｅｐｅａｔ−Ａｃｃｕｍｕｌａｔｅ Ｃｏｄｅｓ」と題する論文に記載されている。
【０００３】
本発明は、たとえばＤＶＢ−Ｓ２（Ｄｉｇｉｔａｌ Ｖｉｄｅｏ Ｂｒｏａｄｃａｓｔ）標準規格、ＷＬＡＮ ８０２．１１ｎ標準規格、またはＷＩＭＡＸ ８０２．１６ｅ標準規格で展開されたＬＤＰＣ符号複合方法も対象としている。
【背景技術】
【０００４】
Ｌｏｗ−Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ−Ｃｈｅｃｋ（ＬＤＰＣ）符号は、１９６２年にＧａｌｌａｇｅｒによって導入され、１９９６年にＭａｃＫａｙおよびＮｅａｌによって再発見された。ＬＤＰＣ符号は、計算および実装の複雑さに起因して、長い間、実用化には至らなかった。しかし、シミュレーション計算を扱うに足りるより高い計算能力を引き出したマイクロエレクトロニクスの進歩によって、現在は実装が可能となっている。その優れた誤り訂正性能に起因して、ＬＤＰＣ符号は、将来の遠隔通信の標準と期待されている。
【０００５】
ＬＤＰＣ符号は、その疎なＭ×Ｎパリティ検査行列Ｈによって定義される線形ブロック符号である。パリティ検査行列Ｈは、それぞれ列次数および行次数と呼ばれる、１列あたりｊ個の１、１行あたりｋ個の１を含む。（ｊ，ｋ）−ｒｅｇｕｌａｒ ＬＤＰＣ符号は、均一な重みの行次数および列次数を有し、そうでない場合には、この符号はｉｒｒｅｇｕｌａｒと呼ばれる。パリティ検査符号は、２部グラフによって表すことができる。Ｍ個のチェック・ノードは、パリティ制約に対応し、Ｎ個の変数ノードは、符号語のデータ記号を表す。グラフの辺は、パリティ検査行列内の１に対応する。
【０００６】
ＬＤＰＣ符号エンコーダ内では、サイズ（Ｎ−Ｍ）の符号化すべきパケットに、サイズ（Ｎ−Ｍ）×Ｎの生成行列Ｇが乗ぜられる。この乗算は、長さＮの符号化されたベクトルとなる。生成行列Ｇおよびパリティ検査行列Ｈは、関係ＧＨｔ＝０を満足し、ここで、０は、零行列である。
【０００７】
一般的に言って、ＬＤＰＣ符号復号器は、復号モジュールを含み、この復号モジュールは、長さＮの符号化されたベクトルを受け取り、パリティ検査行列Ｈを使用することによって長さＮの中間ベクトルを送達する。次に、デマッピング（ｄｅｍａｐｐｉｎｇ）モジュールが、長さ（Ｎ−Ｍ）の復号されたベクトルを前記中間ベクトルから抽出する。
【０００８】
より正確には、ＬＤＰＣ符号は、硬決定または軟決定のいずれかの形で、メッセージ受渡しアルゴリズムを使用して復号される。この復号は、反復処理であり、この反復処理は、変数ノードとチェック・ノードとの間でメッセージを交換する。通常は、Ｂｅｌｉｅｆ Ｐｒｏｐａｇａｔｉｏｎ（ＢＰ）アルゴリズムが使用され、このアルゴリズムは、変数ノードとチェック・ノードとの間でソフト情報を反復して交換する。符号性能は、主に、パリティ検査行列Ｈのランダムさ、符号語サイズＮ、および符号レートＲ＝（Ｎ−Ｍ）／Ｎに依存する。
【０００９】
チャネル符号化部分は、ＵＭＴＳ、ＷＬＡＮ、およびＷＰＡＮなどの無線通信システムにおける非常に重要な構成要素である。特にＷＬＡＮおよびＷＰＡＮの領域では、復号の待ち時間が、決定的に重要である。Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ符号は、近い将来のこの種のシステムに関する有望な候補と考えることができる。これらの符号は、ＤＶＢ−Ｓ２標準規格および一部の光ファイバ通信システムで展開されつつある。
【００１０】
この符号は、いくつかの非常に興味深い特性を有している。この特性によって、これらの符号が待ち時間のクリティカルな応用例に対して選択できる。
【００１１】
新しいＤＶＢ−Ｓ２標準規格は、強力な順方向誤り訂正（ＦＥＣ）システムを特徴とする。このＦＥＣは、理論的限界に近い伝送を可能にする。これは、ＬＤＰＣ符号を使用することによって可能にされ、このＬＤＰＣ符号は、ターボ符号の性能さえしのぐことができる。柔軟性を提供するために、Ｒ＝１／４からＲ＝９／１０までの範囲の１１個の異なる符号レート（Ｒ）が規定されている。符号語長は６４８００ビットまでである。この膨大な最大符号語長が、優れた通信性能の理由である。６４８００ビットの符号語長を説明する。
【００１２】
ＤＶＢ−Ｓ２符号について、６４８００個のいわゆる変数ノード（ＶＮ）および６４８００×（１−Ｒ）個のチェック・ノード（ＣＮ）が存在する。この２タイプのノードの接続性は、標準規格で規定される。変数ノードは、情報ノードおよびパリティ・ノードを含む。ＬＤＰＣ符号の復号に関して、この２タイプのノードの間で、ノード処理が複雑とはならない間に反復してメッセージが交換される。一般に、１回の反復中、まず変数ノード（ＶＮ）が処理され（更新され）、次にチェック・ノード（ＣＮ）が処理される（更新される）。
【００１３】
後記する「２フェーズＭＰ」と称するこの従来の２フェーズアルゴリズムまたはメッセージ受渡しの問題は、低い収束速度すなわち、固定された回数の反復の間に到達する通信性能にかかるものである。
【００１４】
Ｍａｎｓｏｕｒ他の論文、題名「Ｈｉｇｈ−Ｔｈｒｏｕｇｈｐｕｔ ＬＤＰＣ Ｄｅｃｏｄｅｒｓ」、ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ａ Ｖｅｒｙ Ｌａｒｇｅ Ｓｃａｌｅ Ｉｎｔｅｇｒａｔｉｏｎ Ｓｙｓｔｅｍｓ（ＶＬＳＩ）、ｖｏｌ．１１、ｎｏ ６、９７６〜９９６頁、２００３年１２月に、ノードの更新されたメッセージが他のノードに直接に渡されるときに収束速度を改善できることが示されている。より正確には、この論文によれば、チェック・ノードの部分集合が、別々に処理され、新たに計算されたメッセージが、対応する変数ノードに即座に渡される。変数ノードは、その発信メッセージを更新する。したがって、次のチェック・ノード部分集合は、新たに更新されたメッセージを受け取り、これによって収束速度が改善される。このスケジューリングは、この論文では「Ｔｕｒｂｏ Ｄｅｃｏｄｉｎｇ Ｍｅｓｓａｇｅ Ｐａｓｓｉｎｇ」と呼ばれ、その後、「ターボＭＰ」と呼ばれている。
【００１５】
Ｈｏｃｅｖａｒの論文、題名「Ａ ｒｅｄｕｃｅｄ ｃｏｍｐｌｅｘｉｔｙ ｄｅｃｏｄｅｒ ａｒｃｈｉｔｅｃｔｕｒｅ ｖｉａ ｌａｙｅｒｅｄ ｄｅｃｏｄｉｎｇ ｏｆ ＬＤＰＣ ｃｏｄｅｓ」、Ｐｒｏｃ．ＩＥＥＥ Ｗｏｒｋｓｈｏｐ ｏｎ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍｓ（ＳｉＰＳ ’０４），Ａｕｓｔｉｎ， ＵＳＡ、２００４年１０月、１０７〜１１２頁、ならびにＣｏｌａｖｏｌｐｅの論文、題名「Ｄｅｓｉｇｎ ａｎｄ Ｐｅｒｆｏｒｍａｎｃｅ ｏｆ Ｔｕｒｂｏ Ｇａｌｌａｇｅｒ Ｃｏｄｅｓ」、ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ、ｖｏｌ．５２、ｎｏ １１、１９０１〜１９０８頁、２００４年１１月に、Ｍａｎｓｏｕｒ他の論文の教示に類似する教示がある。
【発明の開示】
【発明が解決しようとする課題】
【００１６】
本発明は、従来技術の復号方法より高速の収束速度を有するＬＤＰＣ符号の新しい復号方法を提案することを１つの目的とする。
【課題を解決するための手段】
【００１７】
本発明による新しい復号方法は、具体的には、複数のチェック・ノードの同時最大事後（ＭＡＰ）確率を計算することによって、効率的に活用される穴をあけられた符号語として伝送された符号語を解釈する。各チェック・ノードは、基本的な２状態トレリスと考えられる。言い換えると、本発明の一態様によれば、本明細書で「内部パリティ・ノード」と呼ばれるパリティ・ノードを介して相互に接続されたチェック・ノードのグループ、あるいは、最終的に、このように単一のグループを形成するすべてのチェック・ノードが合同で更新され、すべての内部パリティ・ノードは更新されない。これは、各チェック・ノードを別々に更新し、例外なしにすべてのパリティ・ノードを更新する従来の復号方法とは異なる。
【００１８】
前記したように、あるノードの更新は、このノードから別のノードに放たれるすべてのメッセージが更新されることを意味する。
【００１９】
したがって、本発明の態様によれば、ＬＤＰＣ符号化された符号語を復号する方法であって、前記ＬＤＰＣ符号が、チェック・ノードと第１変数ノード、たとえば情報ノードおよびジグザグ接続性によってチェック・ノードに接続された次数２の第２変数ノード、たとえばパリティ・ノードを含む変数ノードとを含む２部グラフによって表される方法が提案されている。
【００２０】
本発明のこの態様の一般的な構成によれば、前記方法は、ａ）内部第２変数ノードと呼ばれる少なくとも１つの第２変数ノードを介して相互に接続されたチェック・ノードの少なくとも１つのグループをすべてのチェック・ノードから定義することと、ｂ）グループごとに、ｂ１）最大事後（ＭＡＰ）タイプのアルゴリズムを使用することによって前記グループのすべてのチェック・ノードを合同で更新するサブステップ（７１）と、ｂ２）前記少なくとも１つの内部第２変数ノードを除く前記グループに接続されたすべての第１変数ノードおよびすべての第２変数ノードを更新するサブステップ（７２、７３）と、を実行することと、ｃ）ステップｂ）を反復して繰り返すことと、を含む。
【００２１】
一実施形態によれば、すべてのチェック・ノードが、単一のグループを形成する時に、ステップｂ）は、ｂ１）最大事後（ＭＡＰ）タイプの前記アルゴリズムを使用することによってすべてのチェック・ノードを合同で更新することと、ｂ２）すべての前記第２変数ノードを除くすべての第１変数ノードを更新することと、を含む。
【００２２】
言い換えると、この実施形態によれば、すべての第２変数ノードは、いわゆる「内部第２変数ノード」となる。
【００２３】
しかし、本発明のこの実施形態は、特にＭＡＰアルゴリズムを使用することによるチェック・ノードの合同更新のゆえに、収束速度の改善を可能にするが、それでも全トレリス計算（チェック・ノードの更新）のフェーズと情報ノードを更新するフェーズという２つのフェーズが、使用されている。
【００２４】
全トレリスの小さい部分を復号し、情報ノードを介して情報を更新し、その後、トレリスの次のセクションを計算することがより効率的となる。
【００２５】
言い換えると、本発明の他の実施形態によれば、ステップａ）は、チェック・ノードを、少なくとも１つの内部第２変数ノードを介して相互に接続された少なくとも２つのチェック・ノードの少なくとも２つのグループに分割することを含み、各グループは、接続する第２変数ノードと呼ばれる１つの第２変数ノードによって隣接するグループに接続される。さらに、サブステップｂ２）は、前記グループのチェック・ノードに接続されたすべての第１変数ノードを更新することと、前記内部第２変数ノードを更新せずに前記グループに接続された各接続する第２変数ノードを更新することとを含む。
【００２６】
チェック・ノードは、グループごとに、前記グループのすべてのチェック・ノードが、それぞれ異なる第１変数ノードに接続されるように分割されることが好ましい。これは、この方法の収束速度をさらに改善する。
【００２７】
ＭＡＰタイプのアルゴリズムは、好ましくは、いわゆるＬｏｇＭＡＰアルゴリズムまたはいわゆるＭａｘＬｏｇＭＡＰアルゴリズムとすることができる。
【００２８】
本発明の一実施形態によれば、ＬＤＰＣ符号は、Ｉｒｒｅｇｕｌａｒ Ｒｅｐｅａｔ−Ａｃｃｕｍｕｌａｔｅ（ＩＲＡ）符号である。
【００２９】
ＬＤＰＣ符号は、たとえばＤＶＢ−Ｓ２ ＬＤＰＣ符号とすることができる。
【００３０】
ＬＤＰＣ符号は、ＷＬＡＮ ８０２．１１ｎ標準規格またはＷＩＭＡＸ ８０２．１６ｅ標準規格で展開された符号とすることもできる。
【００３１】
各符号化された符号語は、無線通信システムの無線媒体から受信することができる。
【００３２】
本発明の他の態様によれば、ＬＤＰＣ符号化された符号語を復号する復号器であって、前記ＬＤＰＣ符号が、チェック・ノードと第１変数ノードおよびジグザグ接続性によってチェック・ノードに接続された次数２の第２変数ノードを含む変数ノードとを含む２部グラフによって表され、前記復号器が、チェック・ノードを更新するように適合されたチェック・ノード処理手段および変数ノードを更新するように適合された変数処理手段を含む処理手段と、前記処理手段をアクティブ化するように適合された制御手段とを含む、復号器として構成してもよい。
【００３３】
本発明のこの態様の一般的な特徴によれば、すべてのチェック・ノードは、内部第２変数ノードと呼ばれる少なくとも１つの第２変数ノードを介して相互に接続されたチェック・ノードの少なくとも１つのグループを定義し、前記チェック・ノード処理手段は、最大事後（ＭＡＰ）タイプのアルゴリズムを実施し、グループのすべてのチェック・ノードを合同で更新するように適合され、前記制御手段は、前記処理手段を反復してアクティブ化するように適合され、各反復中に、前記グループのすべてのチェック・ノードを合同で更新するため、ならびに前記少なくとも１つの内部第２変数ノードを除く前記グループに接続されたすべての第１変数ノードおよびすべての第２変数ノードを更新するために、グループごとに前記チェック・ノード処理手段および前記変数ノード処理手段をアクティブ化するように適合される。
【００３４】
本発明の一実施形態によれば、すべてのチェック・ノードは単一のグループを形成し、前記チェック・ノード処理手段はすべてのチェック・ノードを合同で更新するように適合され、各反復中に、前記制御手段は、前記チェック・ノード処理手段を合同で更新するためおよびすべての前記第２変数ノードを除くすべての第１変数ノードを更新するために、前記チェック・ノード処理手段および前記変数ノード処理手段をアクティブ化するように適合される。
【００３５】
本発明の他の実施形態によれば、複数のチェック・ノードは、少なくとも１つの内部第２変数ノードを介して相互に接続された少なくとも２つのチェック・ノードの少なくとも２つのグループに分割される。各グループは、接続する第２変数ノードと呼ばれる１つの第２変数ノードによって隣接するグループに接続される。前記制御手段は、前記処理手段を反復してアクティブ化するように適合され、各反復中に、前記グループのすべてのチェック・ノードを合同で更新するため、前記グループのチェック・ノードに接続されたすべての第１変数ノードを更新するため、および前記内部第２変数ノードを更新せずに前記グループに接続された各接続する第２変数ノードを更新するために、グループごとに前記チェック・ノード処理手段および前記変数処理手段をアクティブ化するように適合される。
【００３６】
本発明のもう１つの態様によれば、上で定義された復号器を含む、無線通信システムの端末を備えてもよい。
【００３７】
本発明の他の利益および特徴は、後記する詳細な説明および図面によってさらに明らかになる。しかしながら、これらの記載および図面等に限定されるものではない。
【発明を実施するための最良の形態】
【００３８】
次の説明では、特に言及しない限り、ＬＤＰＣ符号は、ＤＶＢ−Ｓ２標準規格を定義する「ＥＴＳＩ ＥＮ ３０２ ３０７ ｖ１．１．１ （２００４−０６）」で定義されたＤＶＢ−Ｓ２ ＬＤＰＣ符号としている。しかしながら、本発明は、そのような符号に限定されず、たとえばＷＬＡＮ ８０２．１１ｎ標準規格またはＷＩＭＡＸ ８０２．１６ｅ標準規格で展開されたものなど、任意の他のＬＤＰＣ符号に使用することができる。
【００３９】
ＬＤＰＣ符号のパリティ検査行列Ｈは、疎な２進行列である。有効な符号語ｘの組は、Ｈｔｘ＝０を満足しなければならない。
【００４０】
Ｈの１列は、符号語の１ビットに関連し、１行は、パリティ検査に対応する。Ｈの行の非ゼロ要素は、対応するビットがこのパリティ検査に寄与することを意味する。この符号は、タナー・グラフと呼ばれる２部グラフによって最も良く記述される。タナー・グラフは、符号ビットとパリティ検査との間の関連のグラフ表現である。符号ビットは、変数ノードＶＮｉ（円）として示され、パリティ検査は、チェック・ノードＣＮｉ（正方形）として示され、辺でこれらが接続されている。各ノードの辺の数を、ノード次数と呼ぶ。ノード次数がすべての変数ノードについて同一の場合に、パリティ検査行列Ｈをｒｅｇｕｌａｒと呼び、そうでない場合に、パリティ検査行列Ｈをｉｒｒｅｇｕｌａｒと呼ぶ。
【００４１】
ＤＶＢ−Ｓ２パリティ検査行列は、２つの別個の部分すなわち、システマティック情報専用のランダム部分およびパリティ情報に属する固定部分からなる。
【００４２】
ＤＶＢ−Ｓ２符号のタナー・グラフを図１に示す。それぞれ符号語のシステマティック・ビットおよびパリティ・ビットに対応する２つのタイプの変数ノードすなわち、情報ノードＩＮｉと呼ばれる変数ノードの第１部分集合と、パリティ・ノードＰＮｉと呼ばれる変数ノードの第２部分集合とが存在する。
【００４３】
順列Πは、情報ノードＩＮｉとチェック・ノードＣＮｉとの間の接続性のランダム行列部分を表す。パリティ・ノードＰＮｉは、すべてが次数２を有し、固定されたジグザグ・パターンでチェック・ノードＣＮｉに接続される。
【００４４】
Ｎ個のチェック・ノードは、情報ノードから来る一定個数の付随する辺を有し、ここでは、チェック・ノード・グルーピングａと呼ばれる。
【００４５】
さらに、チェック・ノードの次数は、情報ノードおよびパリティ・ノードから来る付随する辺の個数に対応する。ここで、第１チェック・ノードＣＮ０は、次数４を有するが、他のすべてのチェック・ノードは、次数５を有する。
【００４６】
Ｋ個の情報ノードは、２つの部分集合ｆｊおよびｆ３から構成される。ｆｊおよびｆ３は、それぞれ、次数ｊおよび次数３の情報ノードの個数を指定する。
【００４７】
情報ノードおよびチェック・ノードの接続性は、次のＤＶＢ−Ｓ２符号化規則によって定義される。
【数１】
ここで、
ｐｊは、第ｊパリティ・ビットであり、
ｉｍは、第ｍ情報符号ビットであり、
ｘ、ｑ、およびｎは、ＤＶＢ−Ｓ２標準規格によって指定される符号レート依存のパラメータである。
【００４８】
この符号化規則が、パリティ検査行列の項目を決定する。第ｍ列は、各行ｊに非ゼロ要素を有し、したがって、順列Πは、すべてのチェック・ノードＣＮｍと情報ノードＩＮｊとの間に１つの辺を生成する。
【００４９】
パリティ・ノードＰＮｉとチェック・ノードＣＮｉとの間の固定されたジグザグ・パターン接続性は、次の符号化方式によって定義される。
【数２】
【００５０】
これは、単純なアキュムレータである。パリティ検査行列の対応する部分は、各列に２つの非ゼロ要素を有し、正方帯行列を形成する。
【００５１】
従来通りに、ＬＤＰＣ符号は、メッセージ受渡しアルゴリズム（「２フェーズＭＰ」）を使用して復号することができる。このアルゴリズムは、変数ノードとチェック・ノードとの間で反復してソフト情報を交換する。交換されるメッセージは、一般に、対数尤度比（ＬＬＲ）である。ＬＬＲ値は、伝送されるビットが「０」または「１」のどちらであるかを判断することを可能にする符号と、この判断の信頼度を表す大きさとを含む。次数ｉの各変数ノードは、次の関係に従ってメッセージｋの更新を計算する。
【数３】
ここで、λｋは、その変数ノードからの更新されるＬＬＲであり、λｃｈは、その変数ノードの対応するチャネルＬＬＲであり、λ１は、その変数ノードの付随する辺のＬＬＲである。
【００５２】
チェック・ノード・メッセージ更新は、一般に、メッセージｋについて、次の関係に従って計算される。
【数４】
ここで、λｋはチェック・ノードからの更新されるＬＬＲであり、λ１は、チェック・ノードの付随する辺のＬＬＲである。
【００５３】
ＤＶＢ−Ｓ２標準規格は、１／４と等しい符号レートＲから９／１０と等しい符号レートＲまでの範囲にわたるＬＤＰＣ符号をサポートする。ＤＶＢ−Ｓ２符号ごとに、チェック・ノードＣＮｉおよびパリティ・ノードＰＮｉは、ジグザグ・パターンで接続される。言い換えると、２つの連続するチェック・ノードは、次数２のパリティ・ノードによって接続される。
【００５４】
次数２の変数ノードは、対応するチャネル値を単純に加算された第１の付随する辺の入力が、第２の付随する辺の出力であり、逆も同様であるという特性を有する。
【００５５】
したがって、従来技術のように、ノードの更新は、カノニカル・スケジューリング（ｃａｎｏｎｉｃａｌ ｓｃｈｅｄｕｌｉｎｇ）で行うことができる。第１ステップでは、すべての変数ノードを更新しなければならず、第２ステップでは、すべてのチェック・ノードを更新しなければならない。
【００５６】
この２フェーズメッセージ受渡しアルゴリズム（「２フェーズＭＰ」）は、ＬＤＰＣ符号に関する最も一般的に適用される復号アルゴリズムである。しかし、この２フェーズ更新の問題は、その遅い収束速度である。
【００５７】
本発明では、より高速の収束速度を有する新しい復号方法が提案されている。
【００５８】
ＬＤＰＣ符号器は、次のように、実現される可能性がある。符号器は、その次数分布に対応する情報ビットを繰り返す繰返しユニットを含む。この展開されたシーケンスが、インターリーブされ（Π）、これに、Σａと表されるパリティ・グループ化が続く。このグループ化は、ビットのパリティ検査合計（ｍｏｄｕｌｏ ２）を計算する。その結果が、その後、２状態ＲＳＣ符号器によって累算される。結果のパリティ・シーケンス
【数５】
およびシステマティック情報
【数６】
が、伝送される。この符号器の結果のタナー・グラフは、パリティ・ノードの固定されたジグザグ接続性をもたらす。
【００５９】
その一方で、チェック・ノードは、終端された２状態トレリスと考えることができる。これは、図２において、次数ｊのチェック・ノードＣＮについて示されている。トレリスの終端するビットは、時間ステップｊ−１でのトレリス状態に対応し、これは、グループ化Σｊ−１にも対応する。
【００６０】
パリティ検査グループ化Σａおよび２状態ＲＳＣ符号器を用いる従来の線形符号化方式は、２状態ＲＳＣ符号器および穴をあけるユニットを用いる符号化方式と同等であることが観察された。
【００６１】
言い換えると、本発明による新しい復号方法は、伝送された符号語を、穴をあけられた符号語として解釈する。これは、同一グループのチェック・ノードに接続されたパリティ・ノード（「内部」パリティ・ノードと呼ぶ）を更新せずにチェック・ノードを合同で（すべてのチェック・ノードを一緒にまたはチェック・ノードのグループによってのいずれかで）更新することにつながる。もちろん、従来のＬＤＰＣ符号器の変更は、本発明の復号方法を実行するためには不要となる。
【００６２】
本発明の第１実施形態を、図３に示す。
【００６３】
この図では、すべてのチェック・ノードが、単一のグループを形成し、全トレリスＥＴＲによって表される。
【００６４】
したがって、すべてのパリティ・ノードＰＮｉが、内部パリティ・ノードであると考えられる。
【００６５】
この第１実施形態による方法の流れを、図４に概略的に示す。
【００６６】
より正確には、ステップ４０で、すべての情報ノードが、まず、対応するチャネルＬＬＲ値λｃｈ、実際にはこれらのチャネル値に含まれるシステマティック情報を用いて初期化される。
【００６７】
その後、初期化済みメッセージが、２状態トレリスＥＴＲに渡され、置換される。
【００６８】
ステップ４１で、複数のメッセージが、これまでに周知のＢＣＪＲアルゴリズムを適用することによって全２状態トレリスＥＴＣを介して計算される。当業者は、Ｌ．Ｂａｈｌ、Ｊ．Ｃｏｃｋｅ、Ｆ．Ｊｅｌｉｎｅｋ、およびＪ．Ｒａｖｉｖ、「Ｏｐｔｉｍａｌ Ｄｅｃｏｄｉｎｇ ｏｆ Ｌｉｎｅａｒ Ｃｏｄｅｓ ｆｏｒ Ｍｉｎｉｍｉｚｉｎｇ Ｓｙｍｂｏｌ Ｅｒｒｏｒ Ｒａｔｅ」、ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ、ｖｏｌ．ＩＴ−２０、２８４〜２８７頁、１９７４年３月において詳細を参照することができる。
【００６９】
また、パリティ・ノードＰＮｉを更新せずに、すべてのチェック・ノードが合同で更新される、すなわち、チェック・ノードから情報ノードへのすべてのメッセージが、合同で更新される。しかし、パリティ・ノードが更新されないので、受け取られるＬＬＲ値
【数７】
（入力メッセージ）に含まれるパリティ情報
【数８】
が、考慮に入れられる。
【００７０】
より正確には、ＢＣＪＲアルゴリズムは、各ビットが送信済みである最大事後（ＭＡＰ）確率をｕｋ＝０またはｕｋ＝１として計算する。Ｂａｈｌ論文でのオリジナルの確率ベース定式化は、多数の乗算を含んでいる。そして、Ｌｏｇ−ＭＡＰアルゴリズムになるように対数領域に移植される。Ｌｏｇ−ＭＡＰアルゴリズムも、これまでに当業者に周知な技術である。当業者は、たとえば、Ｐ．Ｒｏｂｅｒｔｓｏｎ、Ｐ．Ｈｏｅｈｅｒ、およびＥ．Ｖｉｌｌｅｂｒｕｎ、「Ｏｐｔｉｍａｌ ａｎｄ Ｓｕｂ−Ｏｐｔｉｍａｌ Ｍａｘｉｍｕｍ ａ Ｐｏｓｔｅｒｉｏｒｉ Ａｌｇｏｒｉｔｈｍｓ Ｓｕｉｔａｂｌｅ ｆｏｒ Ｔｕｒｂｏ Ｄｅｃｏｄｉｎｇ」、Ｅｕｒｏｐｅａｎ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ（ＥＴＴ）、ｖｏｌ．８、ｎｏ ２、１１９〜１２５頁、１９９７年３月〜４月を参照することができる。
【００７１】
入力ｋのＭＡＰ確率は、
【数９】
と計算される。
【００７２】
情報ノードのＬＬＲ
【数１０】
は、システマティック入力を表し、パリティ・ノード・メッセージ
【数１１】
は、パリティ情報を表す。式（４）は、３つの確率を使用して表すことができ、これらの確率は、符号器状態
【数１２】
、ｋ∈｛０ … Ｅ｝およびｍ，ｍ’∈｛１，２｝を表し、Ｅは、ＩＮメッセージの個数である［図３を参照されたい］。
【００７３】
分岐メトリックス
【数１３】
は、
【数１４】
と
【数１５】
との間で遷移が行われた確率である。これは、入力メッセージ
【数１６】
および
【数１７】
、符号構造、ならびにｕｋ＝０またはｕｋ＝１の仮定から導出される。詳細について、当業者は、前記したＲｏｂｅｒｔｓｏｎ他の文献を参照することができる。
【００７４】
これらの分岐メトリックスを使用することによって、確率
【数１８】
が取得されることができ、この確率は、初期状態ならびに受信シーケンス
【数１９】
および
【数２０】
を与えられて、符号器が状態
【数２１】
に達した確率を表している。これは、次のように計算される。
【数２２】
【００７５】
この計算は、順方向再帰（ｆｏｒｗａｒｄ ｒｅｃｕｒｓｉｏｎ）と呼ばれる。逆方向再帰（ｂａｃｋｗａｒｄ ｒｅｃｕｒｓｉｏｎ）を実行することによって、状態
【数２３】
および受信シーケンスの残り
【数２４】
を与えられて符号器が（既知の）最終状態に達した確率
【数２５】
がもたらされる。
【数２６】
αおよびβは、両方とも状態メトリックスと呼ばれる。式（４）は、次のように書き直される。
【数２７】
【００７６】
すべての事後値
【数２８】
が計算された時に、それ自体の古い情報の確認を避けるために適当な入力メッセージ
【数２９】
を引くことによって決定される外来情報
【数３０】
が、情報ノードに戻って渡される。したがって、
【数３１】
は、
【数３２】
と計算される。
【００７７】
言い換えると、
【数３３】
は、チェック・ノードによって合同で更新され、情報ノードに戻って渡されるすべてのメッセージのベクトルを表す。
【００７８】
ステップ４２で、すべての情報ノードが、アクティブであり、前記した式（３）に従って更新される。言い換えると、情報ノードからチェック・ノードへのすべてのメッセージが、前記した従来の式（３）に従って更新され、この式（３）では、λｃｈが、ＬＬＲチャネル値のシステマティック情報である。
【００７９】
すべての情報ノードがステップ４２で更新された後に、反復が終了し、新しい反復を開始することができる（ステップ４３）。
【００８０】
この反復復号処理は、従来の停止判断基準に達するまで継続される。
【００８１】
たとえば、停止判断基準は、指定された通信性能を得るのに必要な所定の反復回数とすることができる。
【００８２】
たとえば、復号可能なブロックまたは符号語については、付随する辺の対数尤度比のチェック・ノード合計を考慮に入れた停止判断基準が、非常によい停止判断基準となる。
【００８３】
本発明の復号器ＤＣＤの例を、図５に概略的に示す。
【００８４】
より正確には、復号器ＤＣＤは、変数ノード処理手段ＶＰＭ、チェック・ノード処理手段ＣＰＭ、ならびに変数ノード処理手段ＶＰＭおよびチェック・ノード処理手段ＣＰＭを制御する制御手段ＣＴＬＭを含む処理手段ＰＲＭを含む。
【００８５】
したがって、各ＬＤＰＣ符号化された符号語ＥＮＣＷは、復号器ＤＣＤによって受け取られ、この復号器は、対応する復号された符号語ＤＣＷを送達する。
【００８６】
変数ノード処理手段ＶＰＭは、上の式（３）に従って情報ノードを更新するためにソフトウェアによって実現されることができる。
【００８７】
変数ノード処理手段は、ハードウェアによって、たとえばアキュムレータを使用することによっても実現されることができる。
【００８８】
チェック・ノード処理手段は、従来のＭＡＰユニットによって、ハードウェアまたはマイクロプロセッサ内のソフトウェアのいずれかによって実現されることができる。
【００８９】
制御手段は、ハードウェアによってまたはマイクロプロセッサ内のソフトウェアによってのいずれかでも実現されることができる。
【００９０】
１つの単一を使用する実施形態では、制御手段は、前記処理手段ＰＲＭを反復してアクティブ化し、前記チェック・ノードを合同で更新するためおよびすべてのパリティ・ノードを除いてすべての情報ノードを更新するために、各反復中に前記チェック・ノード処理手段ＣＰＭおよび前記変数ノード処理手段ＶＰＭをアクティブ化するように適合される。
【００９１】
図４に示された実施形態によれば、全トレリスＥＴＲにわたって使用されるＬｏｇ−ＭＡＰアルゴリズムは、２フェーズが使用されている。一方のフェーズは、トレリス計算（チェック・ノードの合同更新）用であり、他方のフェーズは、情報ノードをアクティブ化し、更新するためのものである。
【００９２】
しかし、トレリスの小さいセクションを復号し、情報ノードを介して情報を更新し、その後、トレリスの次のセクションを計算することが、より効率的である。
【００９３】
そのような実施形態を、図６および７により具体的に示す。
【００９４】
全トレリスは、チェック・ノードのグループＧＲｉに対応するより小さいセクションＴＲＳｉに区分される。１つのトレリス・セクションに用いられる情報ノード辺の個数を、セクション・サイズＳと称する。
【００９５】
本実施例では、Ｓ＝６としている。言い換えると、各トレリス・セクションＴＲＳｉは、３と等しいグループ化を有する２つのチェック・ノードのグループＧＲｉに対応する。
【００９６】
図１に示されたオリジナルのタナー・グラフでは、２つの隣接するチェック・ノードが一つのパリティ・ノードを介して接続される。このパリティ・ノードを、本明細書では「内部」パリティ・ノードと称する。これは、たとえば第１グループＧＲ１のパリティ・ノードＰＮ１または図６の第１トレリス・セクションＴＲＳ１にあてはまる。
【００９７】
より一般的に、図６の例に示されているように、各グループＧＲｉ（トレリス・セクションＴＳｉ）は、２つの内部パリティ・ノードＰＮｎおよびＰＮｎ＋１に関連する最後のトレリス・セクションＴＲＳｎを除いて、１つの内部パリティ・ノードＴＮｉに関連する。
【００９８】
後記するように、本発明では、これらの内部パリティ・ノードのすべてが反復復号方法中に更新されない。
【００９９】
さらに、各トレリス・セクションＴＲＳｉまたはグループＧＲｉは、本明細書で「接続する」パリティ・ノードと呼ばれる１つのパリティ・ノードによって、隣接するグループに接続される。
【０１００】
本実施例では、グループＧＲ１は、接続するパリティ・ノードＰＮ１，２によってグループＧＲ２に接続されている。より一般的に言えば、グループＧＲｉは、接続するパリティ・ノードＰＮｉ−１，ｉを介してグループＧＲｉ−１に、接続するパリティ・ノードＰＮｉ，ｉ＋１を介してグループＧＲｉ＋１に接続されている。
【０１０１】
現在の例では、チェック・ノードは、２つのチェック・ノードのグループに分割されている。しかし、１つのグループまたは１つのトレリス・セクション内のチェック・ノードの個数は、異なるものとすることができ、グループごとに異なるものとすることができる。
【０１０２】
しかし、本復号方法は、各グループのすべてのチェック・ノードが、それぞれ異なる情報ノードに接続されるときに、より効率的となる。
【０１０３】
この実施形態による復号方法の流れが図７に示される。
【０１０４】
端的に言うと、情報ノードから始めて、対応するメッセージが、第１トレリス・セクションに渡される。Ｌｏｇ−ＭＡＰアルゴリズムを使用して、新しい外来情報が、計算され、参加する情報ノードすなわち、前記第１トレリス・セクションに接続された情報ノードに戻って渡される。参加する情報ノードの出力メッセージは、上の従来の式（３）に従って更新される。次に、次のトレリス・セクションが処理される。１つの反復は、すべてのトレリス・セクションがそのメッセージを更新した時に終了する。２つのトレリス・セクションの境界の間のメッセージ受渡しは、接続するパリティ・ノードを介して行われ、この接続するパリティ・ノードは、次数２の標準変数ノードであり、上の従来の式（３）に従って更新される。
【０１０５】
より正確には、図７を参照すると、第１ステップ７０は、ＬＬＲチャネル値λｃｈ（システマティック情報）を使用する情報ノード初期化である。この初期化ステップ７０は、図４の初期化ステップ４０に類似する。
【０１０６】
次に、反復１（ｉｔ＝１）が始まる。
【０１０７】
反復１は、第１トレリス・セクションＴＲＳｉまたはチェック・ノードの第１グループＧＲｉ（ｉ＝１）の処理から始まる。グループＧＲ１のすべてのチェック・ノードが、上で説明したＬｏｇ−ＭＡＰアルゴリズムを使用することによって合同で更新される。
【０１０８】
言い換えると、全トレリス内の１つのセクションだけが処理される。かかるトレリスのセクション処理は、「ウィンドウイング」と呼ばれ、当業者に知られている。境界での状態メトリックスは、それぞれ順方向再帰または逆方向再帰を伴う獲得フェーズによって従来通りに計算することができる。しかし、獲得フェーズを、ここでは避けることができる。すなわち、２状態ＲＳＴ符号器のパリティ・ビットが、次の時間ステップにトレリスを終了させるからである。したがって、この終了条件を使用して、パリティ・ノード情報が使用可能であるときには必ず、順方向再帰または逆方向再帰を開始することができる。
【０１０９】
グループＧＲ１のすべてのチェック・ノードが更新された（ステップ７１）後に、すべての参加する情報ノードＩＮｊを、上の従来の式（３）に従って更新する（ステップ７２）。いわゆる参加する情報ノードＩＮｊは、チェック・ノードの第１グループＧＲ１を表す第１トレリス・セクションＴＲＳ１に接続された情報ノードである。
【０１１０】
次に、当然のことながら、内部パリティ・ノードＰＮ１を除いて、この第１トレリス・セクションＴＲＳ１に接続されたパリティ・ノードを更新する。
【０１１１】
本実施例では、第１トレリス・セクションＴＲＳ１に接続されたパリティ・ノードは、接続するパリティ・ノードＰＮ１，２である。
【０１１２】
この接続するパリティ・ノードは、前記した式（３）に従って従来通りに更新される。ここで、λｃｈは、パリティ情報である（ステップ７３）。
【０１１３】
次に、第２トレリス・セクションＴＲＳ２が処理される。
【０１１４】
より正確には、このトレリス・セクションＴＲＳ２に対応するすべてのチェック・ノードが、合同で更新される（ステップ７１）。次に、すべての参加する情報ノードが更新され（ステップ７２）、その後、接続するパリティ・ノードＰＮ１，２およびＰＮ２，３が更新される。
【０１１５】
復号は、最後のトレリス・セクションＴＲＳｎに達するまで継続される。
【０１１６】
再度、この最後のトレリス・セクションＴＲＳｎに対応するチェック・ノードが、合同で更新されると（ステップ７１）、すべての参加する情報ノードが更新され（ステップ７２）、最後に、接続するパリティ・ノードＰＮｎ−１，ｎが、再び更新される（ステップ７３）。
【０１１７】
また、この最後のトレリス・セクションにおいては、内部パリティ・ノードＰＮｎおよびＰＮｎ＋１は、更新されない。
【０１１８】
この段階で、反復１が終了し、次の反復（ｉｔ＝ｉｔ＋１、ステップ７６）を開始することができる。
【０１１９】
復号処理は、既に前記した図４の説明のように、停止判断基準に達した時に停止する。
【０１２０】
本実施例では、トレリス・セクションは、各反復中に、最初のトレリス・セクションから最後のトレリス・セクションへと連続して処理されて終える。
【０１２１】
しかし、本発明によれば、各反復中に任意の順序でトレリス・セクションを連続して処理することも可能となる。
【０１２２】
セクション・サイズＳは、少なくとも２つのチェック・ノードの合同ＭＡＰ処理を保証するために、チェック・ノードのグループ化または次数の倍数になるように選択される。Ｓの適切な値は、Ｓ＝１０ａとすることができる（「ａ」は、チェック・ノードのグループ化または次数である）。
【０１２３】
本発明にかかる他の実施形態を実施することを可能にする復号器は、図５に示された復号器に類似するハードウェアとすることができる。もちろん、制御手段は、図７に示された異なるステップを実行するために実現され、またはプログラムされる。さらに、変数処理手段ＶＰＭは、情報ノードまたは接続するパリティ・ノードのいずれかを更新するのに使用される。
【０１２４】
本発明による復号方法の変換速度は、従来技術による従来の「２フェーズＭＰ」およびＭａｎｓｏｕｒ論文で開示されたいわゆる「ターボＭＰ」より高速であり、両方の従来技術の方法は、例外なしに、すべてのパリティ・ノードが更新されると共に、チェック・ノードが別々に更新される。
【０１２５】
本発明による復号方法は、高い符号レート柔軟性をサポートする。
【０１２６】
さらに、本発明による復号方法は、必要な反復の回数をかなり減らし、さらに、エラー・フロアをより低くする。
【０１２７】
一例として、図８に、異なるメッセージ受渡しアルゴリズムすなわち、従来の２フェーズ・メッセージ受渡し（「２フェーズＭＰ」）、いわゆるターボ・メッセージ受渡しアルゴリズム（「ターボＭＰ」）、および、ここでは「セクション化されたＭＰ」と呼ばれる本発明の第２実施形態による復号方法を使用するｉｒｒｅｇｕｌａｒ ＬＤＰＣ符号の通信性能を示す。
【０１２８】
図８の左側のフレーム誤り率（ＦＥＲ）曲線は１０回の反復を仮定し、図８の右側の曲線は２フェーズＭＰ、ターボＭＰ、およびセクション化されたＭＰについて、それぞれ４０回、４０回および３０回の反復を仮定する。
【０１２９】
Ｅｂはチャネル上のビット情報伝送の平均エネルギであり、Ｎ０は前記チャネルの雑音エネルギである。
【０１３０】
１００ｋのブロックは、ＡＷＧＮチャネル上でシミュレートされる。ＬＤＰＣ符号は、１６００ビットおよび（λ３＝０．５２，λ４＝０．２４，λ５＝０．０８，λ９＝０．０４，λ３１＝０．１２）のＩＮ次数分布を有するｉｒｒｅｇｕｌａｒ ＬＤＰＣ符号である。さらに、グループ化ａ（チェック・ノード次数）は、７と等しく、結果の符号レートは、Ｒ＝０．５である。
【０１３１】
セクション化されたＭＰは、Ｓ＝７０のセクション・サイズを使用し、このサイズは、符号レートＲ＝０．５の１０個のＣＮの合同処理に対応する。セクション化されたＭＰの収束速度は、必ずターボＭＰおよび２フェーズＭＰより速い。
【０１３２】
特に、低符号レートについて、収束速度の差は、注目すべきものとなる。一方、Ｒ＝０．１２５および１０回の反復について、ターボＭＰおよび２フェーズＭＰのＦＥＲは、収束を開始することすらしていなかった。
【０１３３】
さらに、２フェーズＭＰを使用するときには、セクション化されたＭＰの３０回の反復の後で得られる通信性能を達成するために、約２００回の反復が必要である。
【０１３４】
もう１つの重要な利益は、複数のＣＮｓの合同計算に起因して、エラー・フロアを下げることができることである。セクション化されたＭＰは、ターボＭＰより低いエラー・フロアを有し、ターボＭＰは、２フェーズＭＰより低いエラー・フロアを有する。
【０１３５】
ＬＤＰＣ復号器ＤＣＤを、無線通信システムの受信器ＴＰ（図９）、たとえば、衛星チャネルを介して符号化された符号語を受信する、たとえば復調器ＤＭＤとして他の従来の構成要素を含むＤＶＢ−Ｓ２受信器に組み込むことができる。
【０１３６】
この復号器は、基地局または任意の他のアクセス・ポイントに組み込むこともできる。
【０１３７】
しかし、本発明は、前記した応用例に限定されないことは言うまでもない。たとえば、ＬＤＰＣ符号化された符号語を、有線通信システム、たとえばｘＤＳＬシステムまたは光ファイバ・システムから受信することも可能である。また、復号器を、そのような有線通信システムの要素に組み込むことも可能である。
【図面の簡単な説明】
【０１３８】
【図１】ＤＶＢ−Ｓ２ ＬＤＰＣ符号の２部グラフを示す図である。
【図２】次数ｊのチェック・ノードと２状態トレリスとの間の対応を示す図である。
【図３】トレリス表現を用いて提示されたＬＤＰＣ符号のグラフ表現を示す図である。
【図４】本発明にかかる方法の第１実施形態に関係する流れ図を概略的に示す図である。
【図５】本発明にかかる復号器の実施形態を概略的に示す図である。
【図６】Ｓ＝６のセクション・サイズを有するトレリス・セクションと共に提示されたＬＤＰＣ符号の表現を概略的に示す図である。
【図７】本発明にかかる方法のもう１つの実施形態に関係する流れ図を概略的に示す図である。
【図８】フレーム誤り率（ＦＥＲ）に関係する曲線を示す図である。
【図９】本発明にかかる無線通信システムの端末を示す図である。
【技術分野】
【０００１】
本発明は、データ通信方法を対象とし、詳細には、ＬＤＰＣ（Ｌｏｗ−Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ−Ｃｈｅｃｋ）符号を用いて符号化された符号語の復号方法を対象とする。
【０００２】
本発明は、さらに詳細には、ＩＲＡ（Ｉｒｒｅｇｕｌａｒ Ｒｅｐｅａｔ Ａｃｃｕｍｕｌａｔｅ）符号を利用するデータ通信システムを対象とするがこれに限定されない。ＩＲＡ符号とは、たとえば、ｓｅｃｏｎｄ ｉｎｔｅｒｎａｔｉｏｎａｌ ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｔｕｒｂｏ Ｃｏｄｅｓ、フランス国ブレスト、２０００年９月で提示されたＨｕｉ Ｊｉｎ他の「Ｉｒｒｅｇｕｌａｒ Ｒｅｐｅａｔ−Ａｃｃｕｍｕｌａｔｅ Ｃｏｄｅｓ」と題する論文に記載されている。
【０００３】
本発明は、たとえばＤＶＢ−Ｓ２（Ｄｉｇｉｔａｌ Ｖｉｄｅｏ Ｂｒｏａｄｃａｓｔ）標準規格、ＷＬＡＮ ８０２．１１ｎ標準規格、またはＷＩＭＡＸ ８０２．１６ｅ標準規格で展開されたＬＤＰＣ符号複合方法も対象としている。
【背景技術】
【０００４】
Ｌｏｗ−Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ−Ｃｈｅｃｋ（ＬＤＰＣ）符号は、１９６２年にＧａｌｌａｇｅｒによって導入され、１９９６年にＭａｃＫａｙおよびＮｅａｌによって再発見された。ＬＤＰＣ符号は、計算および実装の複雑さに起因して、長い間、実用化には至らなかった。しかし、シミュレーション計算を扱うに足りるより高い計算能力を引き出したマイクロエレクトロニクスの進歩によって、現在は実装が可能となっている。その優れた誤り訂正性能に起因して、ＬＤＰＣ符号は、将来の遠隔通信の標準と期待されている。
【０００５】
ＬＤＰＣ符号は、その疎なＭ×Ｎパリティ検査行列Ｈによって定義される線形ブロック符号である。パリティ検査行列Ｈは、それぞれ列次数および行次数と呼ばれる、１列あたりｊ個の１、１行あたりｋ個の１を含む。（ｊ，ｋ）−ｒｅｇｕｌａｒ ＬＤＰＣ符号は、均一な重みの行次数および列次数を有し、そうでない場合には、この符号はｉｒｒｅｇｕｌａｒと呼ばれる。パリティ検査符号は、２部グラフによって表すことができる。Ｍ個のチェック・ノードは、パリティ制約に対応し、Ｎ個の変数ノードは、符号語のデータ記号を表す。グラフの辺は、パリティ検査行列内の１に対応する。
【０００６】
ＬＤＰＣ符号エンコーダ内では、サイズ（Ｎ−Ｍ）の符号化すべきパケットに、サイズ（Ｎ−Ｍ）×Ｎの生成行列Ｇが乗ぜられる。この乗算は、長さＮの符号化されたベクトルとなる。生成行列Ｇおよびパリティ検査行列Ｈは、関係ＧＨｔ＝０を満足し、ここで、０は、零行列である。
【０００７】
一般的に言って、ＬＤＰＣ符号復号器は、復号モジュールを含み、この復号モジュールは、長さＮの符号化されたベクトルを受け取り、パリティ検査行列Ｈを使用することによって長さＮの中間ベクトルを送達する。次に、デマッピング（ｄｅｍａｐｐｉｎｇ）モジュールが、長さ（Ｎ−Ｍ）の復号されたベクトルを前記中間ベクトルから抽出する。
【０００８】
より正確には、ＬＤＰＣ符号は、硬決定または軟決定のいずれかの形で、メッセージ受渡しアルゴリズムを使用して復号される。この復号は、反復処理であり、この反復処理は、変数ノードとチェック・ノードとの間でメッセージを交換する。通常は、Ｂｅｌｉｅｆ Ｐｒｏｐａｇａｔｉｏｎ（ＢＰ）アルゴリズムが使用され、このアルゴリズムは、変数ノードとチェック・ノードとの間でソフト情報を反復して交換する。符号性能は、主に、パリティ検査行列Ｈのランダムさ、符号語サイズＮ、および符号レートＲ＝（Ｎ−Ｍ）／Ｎに依存する。
【０００９】
チャネル符号化部分は、ＵＭＴＳ、ＷＬＡＮ、およびＷＰＡＮなどの無線通信システムにおける非常に重要な構成要素である。特にＷＬＡＮおよびＷＰＡＮの領域では、復号の待ち時間が、決定的に重要である。Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ符号は、近い将来のこの種のシステムに関する有望な候補と考えることができる。これらの符号は、ＤＶＢ−Ｓ２標準規格および一部の光ファイバ通信システムで展開されつつある。
【００１０】
この符号は、いくつかの非常に興味深い特性を有している。この特性によって、これらの符号が待ち時間のクリティカルな応用例に対して選択できる。
【００１１】
新しいＤＶＢ−Ｓ２標準規格は、強力な順方向誤り訂正（ＦＥＣ）システムを特徴とする。このＦＥＣは、理論的限界に近い伝送を可能にする。これは、ＬＤＰＣ符号を使用することによって可能にされ、このＬＤＰＣ符号は、ターボ符号の性能さえしのぐことができる。柔軟性を提供するために、Ｒ＝１／４からＲ＝９／１０までの範囲の１１個の異なる符号レート（Ｒ）が規定されている。符号語長は６４８００ビットまでである。この膨大な最大符号語長が、優れた通信性能の理由である。６４８００ビットの符号語長を説明する。
【００１２】
ＤＶＢ−Ｓ２符号について、６４８００個のいわゆる変数ノード（ＶＮ）および６４８００×（１−Ｒ）個のチェック・ノード（ＣＮ）が存在する。この２タイプのノードの接続性は、標準規格で規定される。変数ノードは、情報ノードおよびパリティ・ノードを含む。ＬＤＰＣ符号の復号に関して、この２タイプのノードの間で、ノード処理が複雑とはならない間に反復してメッセージが交換される。一般に、１回の反復中、まず変数ノード（ＶＮ）が処理され（更新され）、次にチェック・ノード（ＣＮ）が処理される（更新される）。
【００１３】
後記する「２フェーズＭＰ」と称するこの従来の２フェーズアルゴリズムまたはメッセージ受渡しの問題は、低い収束速度すなわち、固定された回数の反復の間に到達する通信性能にかかるものである。
【００１４】
Ｍａｎｓｏｕｒ他の論文、題名「Ｈｉｇｈ−Ｔｈｒｏｕｇｈｐｕｔ ＬＤＰＣ Ｄｅｃｏｄｅｒｓ」、ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ａ Ｖｅｒｙ Ｌａｒｇｅ Ｓｃａｌｅ Ｉｎｔｅｇｒａｔｉｏｎ Ｓｙｓｔｅｍｓ（ＶＬＳＩ）、ｖｏｌ．１１、ｎｏ ６、９７６〜９９６頁、２００３年１２月に、ノードの更新されたメッセージが他のノードに直接に渡されるときに収束速度を改善できることが示されている。より正確には、この論文によれば、チェック・ノードの部分集合が、別々に処理され、新たに計算されたメッセージが、対応する変数ノードに即座に渡される。変数ノードは、その発信メッセージを更新する。したがって、次のチェック・ノード部分集合は、新たに更新されたメッセージを受け取り、これによって収束速度が改善される。このスケジューリングは、この論文では「Ｔｕｒｂｏ Ｄｅｃｏｄｉｎｇ Ｍｅｓｓａｇｅ Ｐａｓｓｉｎｇ」と呼ばれ、その後、「ターボＭＰ」と呼ばれている。
【００１５】
Ｈｏｃｅｖａｒの論文、題名「Ａ ｒｅｄｕｃｅｄ ｃｏｍｐｌｅｘｉｔｙ ｄｅｃｏｄｅｒ ａｒｃｈｉｔｅｃｔｕｒｅ ｖｉａ ｌａｙｅｒｅｄ ｄｅｃｏｄｉｎｇ ｏｆ ＬＤＰＣ ｃｏｄｅｓ」、Ｐｒｏｃ．ＩＥＥＥ Ｗｏｒｋｓｈｏｐ ｏｎ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍｓ（ＳｉＰＳ ’０４），Ａｕｓｔｉｎ， ＵＳＡ、２００４年１０月、１０７〜１１２頁、ならびにＣｏｌａｖｏｌｐｅの論文、題名「Ｄｅｓｉｇｎ ａｎｄ Ｐｅｒｆｏｒｍａｎｃｅ ｏｆ Ｔｕｒｂｏ Ｇａｌｌａｇｅｒ Ｃｏｄｅｓ」、ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ、ｖｏｌ．５２、ｎｏ １１、１９０１〜１９０８頁、２００４年１１月に、Ｍａｎｓｏｕｒ他の論文の教示に類似する教示がある。
【発明の開示】
【発明が解決しようとする課題】
【００１６】
本発明は、従来技術の復号方法より高速の収束速度を有するＬＤＰＣ符号の新しい復号方法を提案することを１つの目的とする。
【課題を解決するための手段】
【００１７】
本発明による新しい復号方法は、具体的には、複数のチェック・ノードの同時最大事後（ＭＡＰ）確率を計算することによって、効率的に活用される穴をあけられた符号語として伝送された符号語を解釈する。各チェック・ノードは、基本的な２状態トレリスと考えられる。言い換えると、本発明の一態様によれば、本明細書で「内部パリティ・ノード」と呼ばれるパリティ・ノードを介して相互に接続されたチェック・ノードのグループ、あるいは、最終的に、このように単一のグループを形成するすべてのチェック・ノードが合同で更新され、すべての内部パリティ・ノードは更新されない。これは、各チェック・ノードを別々に更新し、例外なしにすべてのパリティ・ノードを更新する従来の復号方法とは異なる。
【００１８】
前記したように、あるノードの更新は、このノードから別のノードに放たれるすべてのメッセージが更新されることを意味する。
【００１９】
したがって、本発明の態様によれば、ＬＤＰＣ符号化された符号語を復号する方法であって、前記ＬＤＰＣ符号が、チェック・ノードと第１変数ノード、たとえば情報ノードおよびジグザグ接続性によってチェック・ノードに接続された次数２の第２変数ノード、たとえばパリティ・ノードを含む変数ノードとを含む２部グラフによって表される方法が提案されている。
【００２０】
本発明のこの態様の一般的な構成によれば、前記方法は、ａ）内部第２変数ノードと呼ばれる少なくとも１つの第２変数ノードを介して相互に接続されたチェック・ノードの少なくとも１つのグループをすべてのチェック・ノードから定義することと、ｂ）グループごとに、ｂ１）最大事後（ＭＡＰ）タイプのアルゴリズムを使用することによって前記グループのすべてのチェック・ノードを合同で更新するサブステップ（７１）と、ｂ２）前記少なくとも１つの内部第２変数ノードを除く前記グループに接続されたすべての第１変数ノードおよびすべての第２変数ノードを更新するサブステップ（７２、７３）と、を実行することと、ｃ）ステップｂ）を反復して繰り返すことと、を含む。
【００２１】
一実施形態によれば、すべてのチェック・ノードが、単一のグループを形成する時に、ステップｂ）は、ｂ１）最大事後（ＭＡＰ）タイプの前記アルゴリズムを使用することによってすべてのチェック・ノードを合同で更新することと、ｂ２）すべての前記第２変数ノードを除くすべての第１変数ノードを更新することと、を含む。
【００２２】
言い換えると、この実施形態によれば、すべての第２変数ノードは、いわゆる「内部第２変数ノード」となる。
【００２３】
しかし、本発明のこの実施形態は、特にＭＡＰアルゴリズムを使用することによるチェック・ノードの合同更新のゆえに、収束速度の改善を可能にするが、それでも全トレリス計算（チェック・ノードの更新）のフェーズと情報ノードを更新するフェーズという２つのフェーズが、使用されている。
【００２４】
全トレリスの小さい部分を復号し、情報ノードを介して情報を更新し、その後、トレリスの次のセクションを計算することがより効率的となる。
【００２５】
言い換えると、本発明の他の実施形態によれば、ステップａ）は、チェック・ノードを、少なくとも１つの内部第２変数ノードを介して相互に接続された少なくとも２つのチェック・ノードの少なくとも２つのグループに分割することを含み、各グループは、接続する第２変数ノードと呼ばれる１つの第２変数ノードによって隣接するグループに接続される。さらに、サブステップｂ２）は、前記グループのチェック・ノードに接続されたすべての第１変数ノードを更新することと、前記内部第２変数ノードを更新せずに前記グループに接続された各接続する第２変数ノードを更新することとを含む。
【００２６】
チェック・ノードは、グループごとに、前記グループのすべてのチェック・ノードが、それぞれ異なる第１変数ノードに接続されるように分割されることが好ましい。これは、この方法の収束速度をさらに改善する。
【００２７】
ＭＡＰタイプのアルゴリズムは、好ましくは、いわゆるＬｏｇＭＡＰアルゴリズムまたはいわゆるＭａｘＬｏｇＭＡＰアルゴリズムとすることができる。
【００２８】
本発明の一実施形態によれば、ＬＤＰＣ符号は、Ｉｒｒｅｇｕｌａｒ Ｒｅｐｅａｔ−Ａｃｃｕｍｕｌａｔｅ（ＩＲＡ）符号である。
【００２９】
ＬＤＰＣ符号は、たとえばＤＶＢ−Ｓ２ ＬＤＰＣ符号とすることができる。
【００３０】
ＬＤＰＣ符号は、ＷＬＡＮ ８０２．１１ｎ標準規格またはＷＩＭＡＸ ８０２．１６ｅ標準規格で展開された符号とすることもできる。
【００３１】
各符号化された符号語は、無線通信システムの無線媒体から受信することができる。
【００３２】
本発明の他の態様によれば、ＬＤＰＣ符号化された符号語を復号する復号器であって、前記ＬＤＰＣ符号が、チェック・ノードと第１変数ノードおよびジグザグ接続性によってチェック・ノードに接続された次数２の第２変数ノードを含む変数ノードとを含む２部グラフによって表され、前記復号器が、チェック・ノードを更新するように適合されたチェック・ノード処理手段および変数ノードを更新するように適合された変数処理手段を含む処理手段と、前記処理手段をアクティブ化するように適合された制御手段とを含む、復号器として構成してもよい。
【００３３】
本発明のこの態様の一般的な特徴によれば、すべてのチェック・ノードは、内部第２変数ノードと呼ばれる少なくとも１つの第２変数ノードを介して相互に接続されたチェック・ノードの少なくとも１つのグループを定義し、前記チェック・ノード処理手段は、最大事後（ＭＡＰ）タイプのアルゴリズムを実施し、グループのすべてのチェック・ノードを合同で更新するように適合され、前記制御手段は、前記処理手段を反復してアクティブ化するように適合され、各反復中に、前記グループのすべてのチェック・ノードを合同で更新するため、ならびに前記少なくとも１つの内部第２変数ノードを除く前記グループに接続されたすべての第１変数ノードおよびすべての第２変数ノードを更新するために、グループごとに前記チェック・ノード処理手段および前記変数ノード処理手段をアクティブ化するように適合される。
【００３４】
本発明の一実施形態によれば、すべてのチェック・ノードは単一のグループを形成し、前記チェック・ノード処理手段はすべてのチェック・ノードを合同で更新するように適合され、各反復中に、前記制御手段は、前記チェック・ノード処理手段を合同で更新するためおよびすべての前記第２変数ノードを除くすべての第１変数ノードを更新するために、前記チェック・ノード処理手段および前記変数ノード処理手段をアクティブ化するように適合される。
【００３５】
本発明の他の実施形態によれば、複数のチェック・ノードは、少なくとも１つの内部第２変数ノードを介して相互に接続された少なくとも２つのチェック・ノードの少なくとも２つのグループに分割される。各グループは、接続する第２変数ノードと呼ばれる１つの第２変数ノードによって隣接するグループに接続される。前記制御手段は、前記処理手段を反復してアクティブ化するように適合され、各反復中に、前記グループのすべてのチェック・ノードを合同で更新するため、前記グループのチェック・ノードに接続されたすべての第１変数ノードを更新するため、および前記内部第２変数ノードを更新せずに前記グループに接続された各接続する第２変数ノードを更新するために、グループごとに前記チェック・ノード処理手段および前記変数処理手段をアクティブ化するように適合される。
【００３６】
本発明のもう１つの態様によれば、上で定義された復号器を含む、無線通信システムの端末を備えてもよい。
【００３７】
本発明の他の利益および特徴は、後記する詳細な説明および図面によってさらに明らかになる。しかしながら、これらの記載および図面等に限定されるものではない。
【発明を実施するための最良の形態】
【００３８】
次の説明では、特に言及しない限り、ＬＤＰＣ符号は、ＤＶＢ−Ｓ２標準規格を定義する「ＥＴＳＩ ＥＮ ３０２ ３０７ ｖ１．１．１ （２００４−０６）」で定義されたＤＶＢ−Ｓ２ ＬＤＰＣ符号としている。しかしながら、本発明は、そのような符号に限定されず、たとえばＷＬＡＮ ８０２．１１ｎ標準規格またはＷＩＭＡＸ ８０２．１６ｅ標準規格で展開されたものなど、任意の他のＬＤＰＣ符号に使用することができる。
【００３９】
ＬＤＰＣ符号のパリティ検査行列Ｈは、疎な２進行列である。有効な符号語ｘの組は、Ｈｔｘ＝０を満足しなければならない。
【００４０】
Ｈの１列は、符号語の１ビットに関連し、１行は、パリティ検査に対応する。Ｈの行の非ゼロ要素は、対応するビットがこのパリティ検査に寄与することを意味する。この符号は、タナー・グラフと呼ばれる２部グラフによって最も良く記述される。タナー・グラフは、符号ビットとパリティ検査との間の関連のグラフ表現である。符号ビットは、変数ノードＶＮｉ（円）として示され、パリティ検査は、チェック・ノードＣＮｉ（正方形）として示され、辺でこれらが接続されている。各ノードの辺の数を、ノード次数と呼ぶ。ノード次数がすべての変数ノードについて同一の場合に、パリティ検査行列Ｈをｒｅｇｕｌａｒと呼び、そうでない場合に、パリティ検査行列Ｈをｉｒｒｅｇｕｌａｒと呼ぶ。
【００４１】
ＤＶＢ−Ｓ２パリティ検査行列は、２つの別個の部分すなわち、システマティック情報専用のランダム部分およびパリティ情報に属する固定部分からなる。
【００４２】
ＤＶＢ−Ｓ２符号のタナー・グラフを図１に示す。それぞれ符号語のシステマティック・ビットおよびパリティ・ビットに対応する２つのタイプの変数ノードすなわち、情報ノードＩＮｉと呼ばれる変数ノードの第１部分集合と、パリティ・ノードＰＮｉと呼ばれる変数ノードの第２部分集合とが存在する。
【００４３】
順列Πは、情報ノードＩＮｉとチェック・ノードＣＮｉとの間の接続性のランダム行列部分を表す。パリティ・ノードＰＮｉは、すべてが次数２を有し、固定されたジグザグ・パターンでチェック・ノードＣＮｉに接続される。
【００４４】
Ｎ個のチェック・ノードは、情報ノードから来る一定個数の付随する辺を有し、ここでは、チェック・ノード・グルーピングａと呼ばれる。
【００４５】
さらに、チェック・ノードの次数は、情報ノードおよびパリティ・ノードから来る付随する辺の個数に対応する。ここで、第１チェック・ノードＣＮ０は、次数４を有するが、他のすべてのチェック・ノードは、次数５を有する。
【００４６】
Ｋ個の情報ノードは、２つの部分集合ｆｊおよびｆ３から構成される。ｆｊおよびｆ３は、それぞれ、次数ｊおよび次数３の情報ノードの個数を指定する。
【００４７】
情報ノードおよびチェック・ノードの接続性は、次のＤＶＢ−Ｓ２符号化規則によって定義される。
【数１】
ここで、
ｐｊは、第ｊパリティ・ビットであり、
ｉｍは、第ｍ情報符号ビットであり、
ｘ、ｑ、およびｎは、ＤＶＢ−Ｓ２標準規格によって指定される符号レート依存のパラメータである。
【００４８】
この符号化規則が、パリティ検査行列の項目を決定する。第ｍ列は、各行ｊに非ゼロ要素を有し、したがって、順列Πは、すべてのチェック・ノードＣＮｍと情報ノードＩＮｊとの間に１つの辺を生成する。
【００４９】
パリティ・ノードＰＮｉとチェック・ノードＣＮｉとの間の固定されたジグザグ・パターン接続性は、次の符号化方式によって定義される。
【数２】
【００５０】
これは、単純なアキュムレータである。パリティ検査行列の対応する部分は、各列に２つの非ゼロ要素を有し、正方帯行列を形成する。
【００５１】
従来通りに、ＬＤＰＣ符号は、メッセージ受渡しアルゴリズム（「２フェーズＭＰ」）を使用して復号することができる。このアルゴリズムは、変数ノードとチェック・ノードとの間で反復してソフト情報を交換する。交換されるメッセージは、一般に、対数尤度比（ＬＬＲ）である。ＬＬＲ値は、伝送されるビットが「０」または「１」のどちらであるかを判断することを可能にする符号と、この判断の信頼度を表す大きさとを含む。次数ｉの各変数ノードは、次の関係に従ってメッセージｋの更新を計算する。
【数３】
ここで、λｋは、その変数ノードからの更新されるＬＬＲであり、λｃｈは、その変数ノードの対応するチャネルＬＬＲであり、λ１は、その変数ノードの付随する辺のＬＬＲである。
【００５２】
チェック・ノード・メッセージ更新は、一般に、メッセージｋについて、次の関係に従って計算される。
【数４】
ここで、λｋはチェック・ノードからの更新されるＬＬＲであり、λ１は、チェック・ノードの付随する辺のＬＬＲである。
【００５３】
ＤＶＢ−Ｓ２標準規格は、１／４と等しい符号レートＲから９／１０と等しい符号レートＲまでの範囲にわたるＬＤＰＣ符号をサポートする。ＤＶＢ−Ｓ２符号ごとに、チェック・ノードＣＮｉおよびパリティ・ノードＰＮｉは、ジグザグ・パターンで接続される。言い換えると、２つの連続するチェック・ノードは、次数２のパリティ・ノードによって接続される。
【００５４】
次数２の変数ノードは、対応するチャネル値を単純に加算された第１の付随する辺の入力が、第２の付随する辺の出力であり、逆も同様であるという特性を有する。
【００５５】
したがって、従来技術のように、ノードの更新は、カノニカル・スケジューリング（ｃａｎｏｎｉｃａｌ ｓｃｈｅｄｕｌｉｎｇ）で行うことができる。第１ステップでは、すべての変数ノードを更新しなければならず、第２ステップでは、すべてのチェック・ノードを更新しなければならない。
【００５６】
この２フェーズメッセージ受渡しアルゴリズム（「２フェーズＭＰ」）は、ＬＤＰＣ符号に関する最も一般的に適用される復号アルゴリズムである。しかし、この２フェーズ更新の問題は、その遅い収束速度である。
【００５７】
本発明では、より高速の収束速度を有する新しい復号方法が提案されている。
【００５８】
ＬＤＰＣ符号器は、次のように、実現される可能性がある。符号器は、その次数分布に対応する情報ビットを繰り返す繰返しユニットを含む。この展開されたシーケンスが、インターリーブされ（Π）、これに、Σａと表されるパリティ・グループ化が続く。このグループ化は、ビットのパリティ検査合計（ｍｏｄｕｌｏ ２）を計算する。その結果が、その後、２状態ＲＳＣ符号器によって累算される。結果のパリティ・シーケンス
【数５】
およびシステマティック情報
【数６】
が、伝送される。この符号器の結果のタナー・グラフは、パリティ・ノードの固定されたジグザグ接続性をもたらす。
【００５９】
その一方で、チェック・ノードは、終端された２状態トレリスと考えることができる。これは、図２において、次数ｊのチェック・ノードＣＮについて示されている。トレリスの終端するビットは、時間ステップｊ−１でのトレリス状態に対応し、これは、グループ化Σｊ−１にも対応する。
【００６０】
パリティ検査グループ化Σａおよび２状態ＲＳＣ符号器を用いる従来の線形符号化方式は、２状態ＲＳＣ符号器および穴をあけるユニットを用いる符号化方式と同等であることが観察された。
【００６１】
言い換えると、本発明による新しい復号方法は、伝送された符号語を、穴をあけられた符号語として解釈する。これは、同一グループのチェック・ノードに接続されたパリティ・ノード（「内部」パリティ・ノードと呼ぶ）を更新せずにチェック・ノードを合同で（すべてのチェック・ノードを一緒にまたはチェック・ノードのグループによってのいずれかで）更新することにつながる。もちろん、従来のＬＤＰＣ符号器の変更は、本発明の復号方法を実行するためには不要となる。
【００６２】
本発明の第１実施形態を、図３に示す。
【００６３】
この図では、すべてのチェック・ノードが、単一のグループを形成し、全トレリスＥＴＲによって表される。
【００６４】
したがって、すべてのパリティ・ノードＰＮｉが、内部パリティ・ノードであると考えられる。
【００６５】
この第１実施形態による方法の流れを、図４に概略的に示す。
【００６６】
より正確には、ステップ４０で、すべての情報ノードが、まず、対応するチャネルＬＬＲ値λｃｈ、実際にはこれらのチャネル値に含まれるシステマティック情報を用いて初期化される。
【００６７】
その後、初期化済みメッセージが、２状態トレリスＥＴＲに渡され、置換される。
【００６８】
ステップ４１で、複数のメッセージが、これまでに周知のＢＣＪＲアルゴリズムを適用することによって全２状態トレリスＥＴＣを介して計算される。当業者は、Ｌ．Ｂａｈｌ、Ｊ．Ｃｏｃｋｅ、Ｆ．Ｊｅｌｉｎｅｋ、およびＪ．Ｒａｖｉｖ、「Ｏｐｔｉｍａｌ Ｄｅｃｏｄｉｎｇ ｏｆ Ｌｉｎｅａｒ Ｃｏｄｅｓ ｆｏｒ Ｍｉｎｉｍｉｚｉｎｇ Ｓｙｍｂｏｌ Ｅｒｒｏｒ Ｒａｔｅ」、ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ、ｖｏｌ．ＩＴ−２０、２８４〜２８７頁、１９７４年３月において詳細を参照することができる。
【００６９】
また、パリティ・ノードＰＮｉを更新せずに、すべてのチェック・ノードが合同で更新される、すなわち、チェック・ノードから情報ノードへのすべてのメッセージが、合同で更新される。しかし、パリティ・ノードが更新されないので、受け取られるＬＬＲ値
【数７】
（入力メッセージ）に含まれるパリティ情報
【数８】
が、考慮に入れられる。
【００７０】
より正確には、ＢＣＪＲアルゴリズムは、各ビットが送信済みである最大事後（ＭＡＰ）確率をｕｋ＝０またはｕｋ＝１として計算する。Ｂａｈｌ論文でのオリジナルの確率ベース定式化は、多数の乗算を含んでいる。そして、Ｌｏｇ−ＭＡＰアルゴリズムになるように対数領域に移植される。Ｌｏｇ−ＭＡＰアルゴリズムも、これまでに当業者に周知な技術である。当業者は、たとえば、Ｐ．Ｒｏｂｅｒｔｓｏｎ、Ｐ．Ｈｏｅｈｅｒ、およびＥ．Ｖｉｌｌｅｂｒｕｎ、「Ｏｐｔｉｍａｌ ａｎｄ Ｓｕｂ−Ｏｐｔｉｍａｌ Ｍａｘｉｍｕｍ ａ Ｐｏｓｔｅｒｉｏｒｉ Ａｌｇｏｒｉｔｈｍｓ Ｓｕｉｔａｂｌｅ ｆｏｒ Ｔｕｒｂｏ Ｄｅｃｏｄｉｎｇ」、Ｅｕｒｏｐｅａｎ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ（ＥＴＴ）、ｖｏｌ．８、ｎｏ ２、１１９〜１２５頁、１９９７年３月〜４月を参照することができる。
【００７１】
入力ｋのＭＡＰ確率は、
【数９】
と計算される。
【００７２】
情報ノードのＬＬＲ
【数１０】
は、システマティック入力を表し、パリティ・ノード・メッセージ
【数１１】
は、パリティ情報を表す。式（４）は、３つの確率を使用して表すことができ、これらの確率は、符号器状態
【数１２】
、ｋ∈｛０ … Ｅ｝およびｍ，ｍ’∈｛１，２｝を表し、Ｅは、ＩＮメッセージの個数である［図３を参照されたい］。
【００７３】
分岐メトリックス
【数１３】
は、
【数１４】
と
【数１５】
との間で遷移が行われた確率である。これは、入力メッセージ
【数１６】
および
【数１７】
、符号構造、ならびにｕｋ＝０またはｕｋ＝１の仮定から導出される。詳細について、当業者は、前記したＲｏｂｅｒｔｓｏｎ他の文献を参照することができる。
【００７４】
これらの分岐メトリックスを使用することによって、確率
【数１８】
が取得されることができ、この確率は、初期状態ならびに受信シーケンス
【数１９】
および
【数２０】
を与えられて、符号器が状態
【数２１】
に達した確率を表している。これは、次のように計算される。
【数２２】
【００７５】
この計算は、順方向再帰（ｆｏｒｗａｒｄ ｒｅｃｕｒｓｉｏｎ）と呼ばれる。逆方向再帰（ｂａｃｋｗａｒｄ ｒｅｃｕｒｓｉｏｎ）を実行することによって、状態
【数２３】
および受信シーケンスの残り
【数２４】
を与えられて符号器が（既知の）最終状態に達した確率
【数２５】
がもたらされる。
【数２６】
αおよびβは、両方とも状態メトリックスと呼ばれる。式（４）は、次のように書き直される。
【数２７】
【００７６】
すべての事後値
【数２８】
が計算された時に、それ自体の古い情報の確認を避けるために適当な入力メッセージ
【数２９】
を引くことによって決定される外来情報
【数３０】
が、情報ノードに戻って渡される。したがって、
【数３１】
は、
【数３２】
と計算される。
【００７７】
言い換えると、
【数３３】
は、チェック・ノードによって合同で更新され、情報ノードに戻って渡されるすべてのメッセージのベクトルを表す。
【００７８】
ステップ４２で、すべての情報ノードが、アクティブであり、前記した式（３）に従って更新される。言い換えると、情報ノードからチェック・ノードへのすべてのメッセージが、前記した従来の式（３）に従って更新され、この式（３）では、λｃｈが、ＬＬＲチャネル値のシステマティック情報である。
【００７９】
すべての情報ノードがステップ４２で更新された後に、反復が終了し、新しい反復を開始することができる（ステップ４３）。
【００８０】
この反復復号処理は、従来の停止判断基準に達するまで継続される。
【００８１】
たとえば、停止判断基準は、指定された通信性能を得るのに必要な所定の反復回数とすることができる。
【００８２】
たとえば、復号可能なブロックまたは符号語については、付随する辺の対数尤度比のチェック・ノード合計を考慮に入れた停止判断基準が、非常によい停止判断基準となる。
【００８３】
本発明の復号器ＤＣＤの例を、図５に概略的に示す。
【００８４】
より正確には、復号器ＤＣＤは、変数ノード処理手段ＶＰＭ、チェック・ノード処理手段ＣＰＭ、ならびに変数ノード処理手段ＶＰＭおよびチェック・ノード処理手段ＣＰＭを制御する制御手段ＣＴＬＭを含む処理手段ＰＲＭを含む。
【００８５】
したがって、各ＬＤＰＣ符号化された符号語ＥＮＣＷは、復号器ＤＣＤによって受け取られ、この復号器は、対応する復号された符号語ＤＣＷを送達する。
【００８６】
変数ノード処理手段ＶＰＭは、上の式（３）に従って情報ノードを更新するためにソフトウェアによって実現されることができる。
【００８７】
変数ノード処理手段は、ハードウェアによって、たとえばアキュムレータを使用することによっても実現されることができる。
【００８８】
チェック・ノード処理手段は、従来のＭＡＰユニットによって、ハードウェアまたはマイクロプロセッサ内のソフトウェアのいずれかによって実現されることができる。
【００８９】
制御手段は、ハードウェアによってまたはマイクロプロセッサ内のソフトウェアによってのいずれかでも実現されることができる。
【００９０】
１つの単一を使用する実施形態では、制御手段は、前記処理手段ＰＲＭを反復してアクティブ化し、前記チェック・ノードを合同で更新するためおよびすべてのパリティ・ノードを除いてすべての情報ノードを更新するために、各反復中に前記チェック・ノード処理手段ＣＰＭおよび前記変数ノード処理手段ＶＰＭをアクティブ化するように適合される。
【００９１】
図４に示された実施形態によれば、全トレリスＥＴＲにわたって使用されるＬｏｇ−ＭＡＰアルゴリズムは、２フェーズが使用されている。一方のフェーズは、トレリス計算（チェック・ノードの合同更新）用であり、他方のフェーズは、情報ノードをアクティブ化し、更新するためのものである。
【００９２】
しかし、トレリスの小さいセクションを復号し、情報ノードを介して情報を更新し、その後、トレリスの次のセクションを計算することが、より効率的である。
【００９３】
そのような実施形態を、図６および７により具体的に示す。
【００９４】
全トレリスは、チェック・ノードのグループＧＲｉに対応するより小さいセクションＴＲＳｉに区分される。１つのトレリス・セクションに用いられる情報ノード辺の個数を、セクション・サイズＳと称する。
【００９５】
本実施例では、Ｓ＝６としている。言い換えると、各トレリス・セクションＴＲＳｉは、３と等しいグループ化を有する２つのチェック・ノードのグループＧＲｉに対応する。
【００９６】
図１に示されたオリジナルのタナー・グラフでは、２つの隣接するチェック・ノードが一つのパリティ・ノードを介して接続される。このパリティ・ノードを、本明細書では「内部」パリティ・ノードと称する。これは、たとえば第１グループＧＲ１のパリティ・ノードＰＮ１または図６の第１トレリス・セクションＴＲＳ１にあてはまる。
【００９７】
より一般的に、図６の例に示されているように、各グループＧＲｉ（トレリス・セクションＴＳｉ）は、２つの内部パリティ・ノードＰＮｎおよびＰＮｎ＋１に関連する最後のトレリス・セクションＴＲＳｎを除いて、１つの内部パリティ・ノードＴＮｉに関連する。
【００９８】
後記するように、本発明では、これらの内部パリティ・ノードのすべてが反復復号方法中に更新されない。
【００９９】
さらに、各トレリス・セクションＴＲＳｉまたはグループＧＲｉは、本明細書で「接続する」パリティ・ノードと呼ばれる１つのパリティ・ノードによって、隣接するグループに接続される。
【０１００】
本実施例では、グループＧＲ１は、接続するパリティ・ノードＰＮ１，２によってグループＧＲ２に接続されている。より一般的に言えば、グループＧＲｉは、接続するパリティ・ノードＰＮｉ−１，ｉを介してグループＧＲｉ−１に、接続するパリティ・ノードＰＮｉ，ｉ＋１を介してグループＧＲｉ＋１に接続されている。
【０１０１】
現在の例では、チェック・ノードは、２つのチェック・ノードのグループに分割されている。しかし、１つのグループまたは１つのトレリス・セクション内のチェック・ノードの個数は、異なるものとすることができ、グループごとに異なるものとすることができる。
【０１０２】
しかし、本復号方法は、各グループのすべてのチェック・ノードが、それぞれ異なる情報ノードに接続されるときに、より効率的となる。
【０１０３】
この実施形態による復号方法の流れが図７に示される。
【０１０４】
端的に言うと、情報ノードから始めて、対応するメッセージが、第１トレリス・セクションに渡される。Ｌｏｇ−ＭＡＰアルゴリズムを使用して、新しい外来情報が、計算され、参加する情報ノードすなわち、前記第１トレリス・セクションに接続された情報ノードに戻って渡される。参加する情報ノードの出力メッセージは、上の従来の式（３）に従って更新される。次に、次のトレリス・セクションが処理される。１つの反復は、すべてのトレリス・セクションがそのメッセージを更新した時に終了する。２つのトレリス・セクションの境界の間のメッセージ受渡しは、接続するパリティ・ノードを介して行われ、この接続するパリティ・ノードは、次数２の標準変数ノードであり、上の従来の式（３）に従って更新される。
【０１０５】
より正確には、図７を参照すると、第１ステップ７０は、ＬＬＲチャネル値λｃｈ（システマティック情報）を使用する情報ノード初期化である。この初期化ステップ７０は、図４の初期化ステップ４０に類似する。
【０１０６】
次に、反復１（ｉｔ＝１）が始まる。
【０１０７】
反復１は、第１トレリス・セクションＴＲＳｉまたはチェック・ノードの第１グループＧＲｉ（ｉ＝１）の処理から始まる。グループＧＲ１のすべてのチェック・ノードが、上で説明したＬｏｇ−ＭＡＰアルゴリズムを使用することによって合同で更新される。
【０１０８】
言い換えると、全トレリス内の１つのセクションだけが処理される。かかるトレリスのセクション処理は、「ウィンドウイング」と呼ばれ、当業者に知られている。境界での状態メトリックスは、それぞれ順方向再帰または逆方向再帰を伴う獲得フェーズによって従来通りに計算することができる。しかし、獲得フェーズを、ここでは避けることができる。すなわち、２状態ＲＳＴ符号器のパリティ・ビットが、次の時間ステップにトレリスを終了させるからである。したがって、この終了条件を使用して、パリティ・ノード情報が使用可能であるときには必ず、順方向再帰または逆方向再帰を開始することができる。
【０１０９】
グループＧＲ１のすべてのチェック・ノードが更新された（ステップ７１）後に、すべての参加する情報ノードＩＮｊを、上の従来の式（３）に従って更新する（ステップ７２）。いわゆる参加する情報ノードＩＮｊは、チェック・ノードの第１グループＧＲ１を表す第１トレリス・セクションＴＲＳ１に接続された情報ノードである。
【０１１０】
次に、当然のことながら、内部パリティ・ノードＰＮ１を除いて、この第１トレリス・セクションＴＲＳ１に接続されたパリティ・ノードを更新する。
【０１１１】
本実施例では、第１トレリス・セクションＴＲＳ１に接続されたパリティ・ノードは、接続するパリティ・ノードＰＮ１，２である。
【０１１２】
この接続するパリティ・ノードは、前記した式（３）に従って従来通りに更新される。ここで、λｃｈは、パリティ情報である（ステップ７３）。
【０１１３】
次に、第２トレリス・セクションＴＲＳ２が処理される。
【０１１４】
より正確には、このトレリス・セクションＴＲＳ２に対応するすべてのチェック・ノードが、合同で更新される（ステップ７１）。次に、すべての参加する情報ノードが更新され（ステップ７２）、その後、接続するパリティ・ノードＰＮ１，２およびＰＮ２，３が更新される。
【０１１５】
復号は、最後のトレリス・セクションＴＲＳｎに達するまで継続される。
【０１１６】
再度、この最後のトレリス・セクションＴＲＳｎに対応するチェック・ノードが、合同で更新されると（ステップ７１）、すべての参加する情報ノードが更新され（ステップ７２）、最後に、接続するパリティ・ノードＰＮｎ−１，ｎが、再び更新される（ステップ７３）。
【０１１７】
また、この最後のトレリス・セクションにおいては、内部パリティ・ノードＰＮｎおよびＰＮｎ＋１は、更新されない。
【０１１８】
この段階で、反復１が終了し、次の反復（ｉｔ＝ｉｔ＋１、ステップ７６）を開始することができる。
【０１１９】
復号処理は、既に前記した図４の説明のように、停止判断基準に達した時に停止する。
【０１２０】
本実施例では、トレリス・セクションは、各反復中に、最初のトレリス・セクションから最後のトレリス・セクションへと連続して処理されて終える。
【０１２１】
しかし、本発明によれば、各反復中に任意の順序でトレリス・セクションを連続して処理することも可能となる。
【０１２２】
セクション・サイズＳは、少なくとも２つのチェック・ノードの合同ＭＡＰ処理を保証するために、チェック・ノードのグループ化または次数の倍数になるように選択される。Ｓの適切な値は、Ｓ＝１０ａとすることができる（「ａ」は、チェック・ノードのグループ化または次数である）。
【０１２３】
本発明にかかる他の実施形態を実施することを可能にする復号器は、図５に示された復号器に類似するハードウェアとすることができる。もちろん、制御手段は、図７に示された異なるステップを実行するために実現され、またはプログラムされる。さらに、変数処理手段ＶＰＭは、情報ノードまたは接続するパリティ・ノードのいずれかを更新するのに使用される。
【０１２４】
本発明による復号方法の変換速度は、従来技術による従来の「２フェーズＭＰ」およびＭａｎｓｏｕｒ論文で開示されたいわゆる「ターボＭＰ」より高速であり、両方の従来技術の方法は、例外なしに、すべてのパリティ・ノードが更新されると共に、チェック・ノードが別々に更新される。
【０１２５】
本発明による復号方法は、高い符号レート柔軟性をサポートする。
【０１２６】
さらに、本発明による復号方法は、必要な反復の回数をかなり減らし、さらに、エラー・フロアをより低くする。
【０１２７】
一例として、図８に、異なるメッセージ受渡しアルゴリズムすなわち、従来の２フェーズ・メッセージ受渡し（「２フェーズＭＰ」）、いわゆるターボ・メッセージ受渡しアルゴリズム（「ターボＭＰ」）、および、ここでは「セクション化されたＭＰ」と呼ばれる本発明の第２実施形態による復号方法を使用するｉｒｒｅｇｕｌａｒ ＬＤＰＣ符号の通信性能を示す。
【０１２８】
図８の左側のフレーム誤り率（ＦＥＲ）曲線は１０回の反復を仮定し、図８の右側の曲線は２フェーズＭＰ、ターボＭＰ、およびセクション化されたＭＰについて、それぞれ４０回、４０回および３０回の反復を仮定する。
【０１２９】
Ｅｂはチャネル上のビット情報伝送の平均エネルギであり、Ｎ０は前記チャネルの雑音エネルギである。
【０１３０】
１００ｋのブロックは、ＡＷＧＮチャネル上でシミュレートされる。ＬＤＰＣ符号は、１６００ビットおよび（λ３＝０．５２，λ４＝０．２４，λ５＝０．０８，λ９＝０．０４，λ３１＝０．１２）のＩＮ次数分布を有するｉｒｒｅｇｕｌａｒ ＬＤＰＣ符号である。さらに、グループ化ａ（チェック・ノード次数）は、７と等しく、結果の符号レートは、Ｒ＝０．５である。
【０１３１】
セクション化されたＭＰは、Ｓ＝７０のセクション・サイズを使用し、このサイズは、符号レートＲ＝０．５の１０個のＣＮの合同処理に対応する。セクション化されたＭＰの収束速度は、必ずターボＭＰおよび２フェーズＭＰより速い。
【０１３２】
特に、低符号レートについて、収束速度の差は、注目すべきものとなる。一方、Ｒ＝０．１２５および１０回の反復について、ターボＭＰおよび２フェーズＭＰのＦＥＲは、収束を開始することすらしていなかった。
【０１３３】
さらに、２フェーズＭＰを使用するときには、セクション化されたＭＰの３０回の反復の後で得られる通信性能を達成するために、約２００回の反復が必要である。
【０１３４】
もう１つの重要な利益は、複数のＣＮｓの合同計算に起因して、エラー・フロアを下げることができることである。セクション化されたＭＰは、ターボＭＰより低いエラー・フロアを有し、ターボＭＰは、２フェーズＭＰより低いエラー・フロアを有する。
【０１３５】
ＬＤＰＣ復号器ＤＣＤを、無線通信システムの受信器ＴＰ（図９）、たとえば、衛星チャネルを介して符号化された符号語を受信する、たとえば復調器ＤＭＤとして他の従来の構成要素を含むＤＶＢ−Ｓ２受信器に組み込むことができる。
【０１３６】
この復号器は、基地局または任意の他のアクセス・ポイントに組み込むこともできる。
【０１３７】
しかし、本発明は、前記した応用例に限定されないことは言うまでもない。たとえば、ＬＤＰＣ符号化された符号語を、有線通信システム、たとえばｘＤＳＬシステムまたは光ファイバ・システムから受信することも可能である。また、復号器を、そのような有線通信システムの要素に組み込むことも可能である。
【図面の簡単な説明】
【０１３８】
【図１】ＤＶＢ−Ｓ２ ＬＤＰＣ符号の２部グラフを示す図である。
【図２】次数ｊのチェック・ノードと２状態トレリスとの間の対応を示す図である。
【図３】トレリス表現を用いて提示されたＬＤＰＣ符号のグラフ表現を示す図である。
【図４】本発明にかかる方法の第１実施形態に関係する流れ図を概略的に示す図である。
【図５】本発明にかかる復号器の実施形態を概略的に示す図である。
【図６】Ｓ＝６のセクション・サイズを有するトレリス・セクションと共に提示されたＬＤＰＣ符号の表現を概略的に示す図である。
【図７】本発明にかかる方法のもう１つの実施形態に関係する流れ図を概略的に示す図である。
【図８】フレーム誤り率（ＦＥＲ）に関係する曲線を示す図である。
【図９】本発明にかかる無線通信システムの端末を示す図である。
【特許請求の範囲】
【請求項１】
ＬＤＰＣ符号化された符号語を復号する方法であって、
前記ＬＤＣＰ符号は、２部グラフによって表され、
前記２部グラフは、チェック・ノードと変数ノードと、から構成されており、
前記変数ノードには、第１変数ノード（ＩＮｉ）およびジグザグ接続性によって前記チェック・ノード（ＣＮｉ）に接続された次数２の第２変数ノード（ＰＮｉ）が含まれており、
ａ）内部第２変数ノード（ＰＮｉ）と呼ばれる少なくとも１つの第２変数ノードを介して相互に接続されたチェック・ノードの少なくとも１つのグループ（ＧＲｉ）をすべての前記チェック・ノードから定義することと、
ｂ）グループ（ＧＲｉ）ごとに、ｂ１）最大事後（ＭＡＰ）タイプのアルゴリズムを使用することによって前記グループのすべての前記チェック・ノードを合同で更新するサブステップ（７１）と、ｂ２）前記少なくとも１つの内部第２変数ノードを除く前記グループに接続されたすべての前記第１変数ノードおよびすべての前記第２変数ノード（ＰＮｉ−１，ｉ、ＰＮｉ，ｉ＋１）を更新するサブステップ（７２、７３）と、を実行することと、
ｃ）ステップｂ）を反復して繰り返すことと、からなる方法。
【請求項２】
すべての前記チェック・ノードは、単一のグループが形成され、
ステップｂ）には、
ｂ１）前記最大事後（ＭＡＰ）タイプの前記アルゴリズムを使用することによってすべての前記チェック・ノードを合同で更新すること（４１）と、
ｂ２）すべての前記第２変数ノードを除くすべての前記第１変数ノードを更新すること（４２）と、が含まれる請求項１に記載の方法。
【請求項３】
ステップａ）には、前記チェック・ノードを、少なくとも１つの内部第２変数ノードを介して相互に接続された少なくとも２つのチェック・ノードの少なくとも２つのグループに分割することが含まれ、
各グループは、接続する第２変数ノードと呼ばれる１つの第２変数ノードによって隣接するグループに接続され、
サブステップｂ２）は、前記グループの前記チェック・ノードに接続されたすべての前記第１変数ノードを更新すること（７２）と、前記内部第２変数ノードを更新せずに前記グループに接続された各接続する第２変数ノードを更新すること（７３）と、が含まれる請求項１に記載の方法。
【請求項４】
前記グループのすべての前記チェック・ノードは、グループごとに、それぞれ異なる第１変数ノードに接続される、請求項３に記載の方法。
【請求項５】
前記ＭＡＰタイプの前記アルゴリズムは、いわゆるＬｏｇＭＡＰアルゴリズムまたはいわゆるＭａｘＬｏｇＭＡＰアルゴリズムである、請求項１ないし請求項４のいずれかに記載の方法。
【請求項６】
前記ＬＤＰＣ符号の前記２部グラフは、第１変数ノードとして情報ノード（ＩＮｉ）および第２変数ノードとしてパリティ・ノード（ＰＮｉ）を含んでいる、請求項１ないし請求項５のいずれかに記載の方法。
【請求項７】
前記ＬＤＰＣ符号は、Ｉｒｒｅｇｕｌａｒ Ｒｅｐｅａｔ−Ａｃｃｕｍｕｌａｔｅ（ＩＲＡ）符号である、請求項１ないし請求項６のいずれかに記載の方法。
【請求項８】
前記ＬＤＰＣ符号は、ＤＶＢ−Ｓ２ ＬＤＰＣ符号またはＷＬＡＮ ８０２．１１ｎ標準規格もしくはＷＩＭＡＸ ８０２．１６ｅ標準規格で展開された符号である、請求項１ないし請求項７のいずれかに記載の方法。
【請求項９】
各符号化された符号語は、無線通信システムの無線媒体からまたは有線通信システムから受信される、請求項１ないし請求項８のいずれかに記載の方法。
【請求項１０】
ＬＤＰＣ符号化された符号語を復号する復号器であって、
前記ＬＤＰＣ符号は、チェック・ノードと、第１変数ノード（ＩＮｉ）およびジグザグ接続性によって前記チェック・ノード（ＣＮｉ）に接続された次数２の第２変数ノード（ＰＮｉ）を含む変数ノードと、が含まれた２部グラフによって表され、
チェック・ノードを更新するように適合されたチェック・ノード処理手段（ＣＰＭ）および変数ノードを更新するように適合された変数処理手段（ＶＰＭ）を含む処理手段（ＰＲＭ）と、前記処理手段をアクティブ化するように適合された制御手段とを備え、
すべての前記チェック・ノードは、内部第２変数ノードと呼ばれる少なくとも１つの第２変数ノードを介して相互に接続されたチェック・ノードの少なくとも１つのグループを定義し、
前記チェック・ノード処理手段（ＣＰＭ）は、最大事後（ＭＡＰ）タイプのアルゴリズムを実施し、グループのすべての前記チェック・ノードを合同で更新するように適合され、
前記制御手段（ＣＴＬＭ）は、前記処理手段（ＰＲＭ）を反復してアクティブ化するように適合され、各反復（ｉｔ）中に、前記グループのすべての前記チェック・ノードを合同で更新するため、ならびに前記少なくとも１つの内部第２変数ノードを除く前記グループに接続されたすべての前記第１変数ノードおよびすべての前記第２変数ノードを更新するために、グループごとに前記チェック・ノード処理手段（ＣＰＭ）および前記変数ノード処理手段（ＶＰＭ）をアクティブ化するように適合される、復号器。
【請求項１１】
すべての前記チェック・ノードは、単一のグループを形成し、
前記チェック・ノード処理手段は、すべての前記チェック・ノードを合同で更新するように適合され、
前記制御手段（ＣＴＬＭ）は、各反復中に、前記チェック・ノードを合同で更新するためおよびすべての前記第２変数ノードを除くすべての前記第１変数ノードを更新するために、前記チェック・ノード処理手段および前記変数ノード処理手段をアクティブ化するように適合される、請求項１０に記載の復号器。
【請求項１２】
前記チェック・ノードは、少なくとも１つの内部第２変数ノードを介して相互に接続された少なくとも２つのチェック・ノードの少なくとも２つのグループに分割され、
各グループは、接続する第２変数ノードと呼ばれる１つの第２変数ノードによって隣接するグループに接続され、
前記制御手段（ＣＴＬＭ）は、前記処理手段を反復してアクティブ化するように適合され、各反復中に、前記グループのすべての前記チェック・ノードを合同で更新するため、前記グループの前記チェック・ノードに接続されたすべての前記第１変数ノードを更新するため、および前記内部第２変数ノードを更新せずに前記グループに接続された各接続する第２変数ノードを更新するために、グループごとに前記チェック・ノード処理手段および前記変数処理手段をアクティブ化するように適合される、請求項１０に記載の復号器。
【請求項１３】
前記グループのすべての前記チェック・ノードは、グループごとに、それぞれ異なる第１変数ノードに接続される、請求項１２に記載の復号器。
【請求項１４】
前記ＭＡＰタイプの前記アルゴリズムは、いわゆるＬｏｇＭＡＰアルゴリズムまたはいわゆるＭａｘＬｏｇＭＡＰアルゴリズムである、請求項１０ないし請求項１３のいずれかに記載の復号器。
【請求項１５】
前記メッセージは、対数尤度比（ＬＬＲ）である、請求項１０ないし請求項１４のいずれかに記載の復号器。
【請求項１６】
前記ＬＤＰＣ符号の前記２部グラフは、第１変数ノードとして情報ノード（ＩＮｉ）および第２変数ノードとしてパリティ・ノード（ＰＮｉ）を含む、請求項１０ないし請求項１５のいずれかに記載の復号器。
【請求項１７】
前記ＬＤＰＣ符号は、Ｉｒｒｅｇｕｌａｒ Ｒｅｐｅａｔ−Ａｃｃｕｍｕｌａｔｅ（ＩＲＡ）符号である、請求項１６に記載の復号器。
【請求項１８】
前記ＬＤＰＣ符号は、ＤＶＢ−Ｓ２ ＬＤＰＣ符号またはＷＬＡＮ ８０２．１１ｎ標準規格もしくはＷＩＭＡＸ ８０２．１６ｅ標準規格で展開された符号である、請求項１６に記載の復号器。
【請求項１９】
請求項１０ないし請求項１８のいずれかに記載の復号器を備える、無線通信システムまたは有線通信システム、たとえばｘＤＳＬシステムまたは光ファイバ・システムの要素。
【請求項２０】
無線通信システムの端末または基地局またはアクセス・ポイントを形成する、請求項１９に記載の要素。
【請求項１】
ＬＤＰＣ符号化された符号語を復号する方法であって、
前記ＬＤＣＰ符号は、２部グラフによって表され、
前記２部グラフは、チェック・ノードと変数ノードと、から構成されており、
前記変数ノードには、第１変数ノード（ＩＮｉ）およびジグザグ接続性によって前記チェック・ノード（ＣＮｉ）に接続された次数２の第２変数ノード（ＰＮｉ）が含まれており、
ａ）内部第２変数ノード（ＰＮｉ）と呼ばれる少なくとも１つの第２変数ノードを介して相互に接続されたチェック・ノードの少なくとも１つのグループ（ＧＲｉ）をすべての前記チェック・ノードから定義することと、
ｂ）グループ（ＧＲｉ）ごとに、ｂ１）最大事後（ＭＡＰ）タイプのアルゴリズムを使用することによって前記グループのすべての前記チェック・ノードを合同で更新するサブステップ（７１）と、ｂ２）前記少なくとも１つの内部第２変数ノードを除く前記グループに接続されたすべての前記第１変数ノードおよびすべての前記第２変数ノード（ＰＮｉ−１，ｉ、ＰＮｉ，ｉ＋１）を更新するサブステップ（７２、７３）と、を実行することと、
ｃ）ステップｂ）を反復して繰り返すことと、からなる方法。
【請求項２】
すべての前記チェック・ノードは、単一のグループが形成され、
ステップｂ）には、
ｂ１）前記最大事後（ＭＡＰ）タイプの前記アルゴリズムを使用することによってすべての前記チェック・ノードを合同で更新すること（４１）と、
ｂ２）すべての前記第２変数ノードを除くすべての前記第１変数ノードを更新すること（４２）と、が含まれる請求項１に記載の方法。
【請求項３】
ステップａ）には、前記チェック・ノードを、少なくとも１つの内部第２変数ノードを介して相互に接続された少なくとも２つのチェック・ノードの少なくとも２つのグループに分割することが含まれ、
各グループは、接続する第２変数ノードと呼ばれる１つの第２変数ノードによって隣接するグループに接続され、
サブステップｂ２）は、前記グループの前記チェック・ノードに接続されたすべての前記第１変数ノードを更新すること（７２）と、前記内部第２変数ノードを更新せずに前記グループに接続された各接続する第２変数ノードを更新すること（７３）と、が含まれる請求項１に記載の方法。
【請求項４】
前記グループのすべての前記チェック・ノードは、グループごとに、それぞれ異なる第１変数ノードに接続される、請求項３に記載の方法。
【請求項５】
前記ＭＡＰタイプの前記アルゴリズムは、いわゆるＬｏｇＭＡＰアルゴリズムまたはいわゆるＭａｘＬｏｇＭＡＰアルゴリズムである、請求項１ないし請求項４のいずれかに記載の方法。
【請求項６】
前記ＬＤＰＣ符号の前記２部グラフは、第１変数ノードとして情報ノード（ＩＮｉ）および第２変数ノードとしてパリティ・ノード（ＰＮｉ）を含んでいる、請求項１ないし請求項５のいずれかに記載の方法。
【請求項７】
前記ＬＤＰＣ符号は、Ｉｒｒｅｇｕｌａｒ Ｒｅｐｅａｔ−Ａｃｃｕｍｕｌａｔｅ（ＩＲＡ）符号である、請求項１ないし請求項６のいずれかに記載の方法。
【請求項８】
前記ＬＤＰＣ符号は、ＤＶＢ−Ｓ２ ＬＤＰＣ符号またはＷＬＡＮ ８０２．１１ｎ標準規格もしくはＷＩＭＡＸ ８０２．１６ｅ標準規格で展開された符号である、請求項１ないし請求項７のいずれかに記載の方法。
【請求項９】
各符号化された符号語は、無線通信システムの無線媒体からまたは有線通信システムから受信される、請求項１ないし請求項８のいずれかに記載の方法。
【請求項１０】
ＬＤＰＣ符号化された符号語を復号する復号器であって、
前記ＬＤＰＣ符号は、チェック・ノードと、第１変数ノード（ＩＮｉ）およびジグザグ接続性によって前記チェック・ノード（ＣＮｉ）に接続された次数２の第２変数ノード（ＰＮｉ）を含む変数ノードと、が含まれた２部グラフによって表され、
チェック・ノードを更新するように適合されたチェック・ノード処理手段（ＣＰＭ）および変数ノードを更新するように適合された変数処理手段（ＶＰＭ）を含む処理手段（ＰＲＭ）と、前記処理手段をアクティブ化するように適合された制御手段とを備え、
すべての前記チェック・ノードは、内部第２変数ノードと呼ばれる少なくとも１つの第２変数ノードを介して相互に接続されたチェック・ノードの少なくとも１つのグループを定義し、
前記チェック・ノード処理手段（ＣＰＭ）は、最大事後（ＭＡＰ）タイプのアルゴリズムを実施し、グループのすべての前記チェック・ノードを合同で更新するように適合され、
前記制御手段（ＣＴＬＭ）は、前記処理手段（ＰＲＭ）を反復してアクティブ化するように適合され、各反復（ｉｔ）中に、前記グループのすべての前記チェック・ノードを合同で更新するため、ならびに前記少なくとも１つの内部第２変数ノードを除く前記グループに接続されたすべての前記第１変数ノードおよびすべての前記第２変数ノードを更新するために、グループごとに前記チェック・ノード処理手段（ＣＰＭ）および前記変数ノード処理手段（ＶＰＭ）をアクティブ化するように適合される、復号器。
【請求項１１】
すべての前記チェック・ノードは、単一のグループを形成し、
前記チェック・ノード処理手段は、すべての前記チェック・ノードを合同で更新するように適合され、
前記制御手段（ＣＴＬＭ）は、各反復中に、前記チェック・ノードを合同で更新するためおよびすべての前記第２変数ノードを除くすべての前記第１変数ノードを更新するために、前記チェック・ノード処理手段および前記変数ノード処理手段をアクティブ化するように適合される、請求項１０に記載の復号器。
【請求項１２】
前記チェック・ノードは、少なくとも１つの内部第２変数ノードを介して相互に接続された少なくとも２つのチェック・ノードの少なくとも２つのグループに分割され、
各グループは、接続する第２変数ノードと呼ばれる１つの第２変数ノードによって隣接するグループに接続され、
前記制御手段（ＣＴＬＭ）は、前記処理手段を反復してアクティブ化するように適合され、各反復中に、前記グループのすべての前記チェック・ノードを合同で更新するため、前記グループの前記チェック・ノードに接続されたすべての前記第１変数ノードを更新するため、および前記内部第２変数ノードを更新せずに前記グループに接続された各接続する第２変数ノードを更新するために、グループごとに前記チェック・ノード処理手段および前記変数処理手段をアクティブ化するように適合される、請求項１０に記載の復号器。
【請求項１３】
前記グループのすべての前記チェック・ノードは、グループごとに、それぞれ異なる第１変数ノードに接続される、請求項１２に記載の復号器。
【請求項１４】
前記ＭＡＰタイプの前記アルゴリズムは、いわゆるＬｏｇＭＡＰアルゴリズムまたはいわゆるＭａｘＬｏｇＭＡＰアルゴリズムである、請求項１０ないし請求項１３のいずれかに記載の復号器。
【請求項１５】
前記メッセージは、対数尤度比（ＬＬＲ）である、請求項１０ないし請求項１４のいずれかに記載の復号器。
【請求項１６】
前記ＬＤＰＣ符号の前記２部グラフは、第１変数ノードとして情報ノード（ＩＮｉ）および第２変数ノードとしてパリティ・ノード（ＰＮｉ）を含む、請求項１０ないし請求項１５のいずれかに記載の復号器。
【請求項１７】
前記ＬＤＰＣ符号は、Ｉｒｒｅｇｕｌａｒ Ｒｅｐｅａｔ−Ａｃｃｕｍｕｌａｔｅ（ＩＲＡ）符号である、請求項１６に記載の復号器。
【請求項１８】
前記ＬＤＰＣ符号は、ＤＶＢ−Ｓ２ ＬＤＰＣ符号またはＷＬＡＮ ８０２．１１ｎ標準規格もしくはＷＩＭＡＸ ８０２．１６ｅ標準規格で展開された符号である、請求項１６に記載の復号器。
【請求項１９】
請求項１０ないし請求項１８のいずれかに記載の復号器を備える、無線通信システムまたは有線通信システム、たとえばｘＤＳＬシステムまたは光ファイバ・システムの要素。
【請求項２０】
無線通信システムの端末または基地局またはアクセス・ポイントを形成する、請求項１９に記載の要素。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公表番号】特表２００９−５３１８９７（Ｐ２００９−５３１８９７Ａ）
【公表日】平成２１年９月３日（２００９．９．３）
【国際特許分類】
【出願番号】特願２００９−５０２０８０（Ｐ２００９−５０２０８０）
【出願日】平成１９年３月２８日（２００７．３．２８）
【国際出願番号】ＰＣＴ／ＥＰ２００７／０５２９８６
【国際公開番号】ＷＯ２００７／１１０４３６
【国際公開日】平成１９年１０月４日（２００７．１０．４）
【出願人】（３０１０４０５７８）エスティマイクロエレクトロニクス エヌヴィ (5)
【Ｆターム（参考）】
【公表日】平成２１年９月３日（２００９．９．３）
【国際特許分類】
【出願日】平成１９年３月２８日（２００７．３．２８）
【国際出願番号】ＰＣＴ／ＥＰ２００７／０５２９８６
【国際公開番号】ＷＯ２００７／１１０４３６
【国際公開日】平成１９年１０月４日（２００７．１０．４）
【出願人】（３０１０４０５７８）エスティマイクロエレクトロニクス エヌヴィ (5)
【Ｆターム（参考）】
[ Back to top ]