JP3836859B2 - 構成されたパリティチェックマトリックスを使用する低密度パリティチェック（ｌｄｐｃ）コードの符号化 - Google Patents

Description

本発明は通信システムに関し、とくに、コード化されたシステムに関する。

本出願は以下の暫定的な特許出願明細書に関連しており、３５ Ｕ．Ｓ．Ｃ§１１９（ｅ）の下にそれらの権利を有している：米国特許出願第60/393,457号明細書（２００２年７月３日出願）、米国特許出願第60/398,760号明細書（２００２年７月２６日出願）、米国特許出願第60/403,812号明細書（２００２年８月１５日出願）、米国特許出願第60/421,505号明細書（２００２年１０月２５日出願）、米国特許出願第60/421,999号明細書（２００２年１０月２９日出願）、米国特許出願第60/423,710号明細書（２００２年１１月４日出願）、米国特許出願第60/440,199号明細書（２００３年１月１５日出願）、米国特許出願第60/447,641号明細書（２００３年２月１４日出願）、米国特許出願第60/456,220号明細書（２００３年３月２０日出願）、２００３年５月９日に出願された米国特許出願明細書（“Description LDPC and BCH Encoders,”）、２００３年６月２４日に出願された米国特許出願明細書（“Description LDPC and BCH Encoders,”）（Attorney Docket:PD-203044）、２００３年６月２４日に出願された米国特許出願明細書（“Description LDPC and BCH Encoders,”）（Attorney Docket:PD-203059）。なお、これらは全てこの明細書において参考文献とされている。

通信システムは、雑音の多い通信チャンネルによる通信の信頼性の高さを保証するためにコード化を使用する。これらの通信チャンネルは、ある信号対雑音比（ＳＮＲ）におけるシンボル当りのビットで表されることのできる固定された容量を示し、理論上の上限（シャノン限界として知られている）を規定する。その結果、コード化設計は、このシャノン限界に近いレートの達成をめざしている。シャノン限界に近いコードのこのような１つのクラスは、低密度パリティチェック（ＬＤＰＣ）コードである。

伝統的に、ＬＤＰＣコードは、そのいくつかの欠点のためにそれ程広くは配備されてきていない。１つの欠点は、ＬＤＰＣコード化技術が非常に複雑なことである。ＬＤＰＣコードをそのジェネレータマトリックスを使用して符号化するには、非常に大きい非スパースマトリックスを記憶する必要がある。さらに、ＬＤＰＣコードは、効率的である大きいブロックを必要とし、その結果、ＬＤＰＣコードのパリティチェックマトリックスがスパースでも、これらのマトリックスの記憶には問題がある。

構成の観点からは、いくつかの難題に直面する。たとえば、記憶は、ＬＤＰＣコードが実際に広く普及していない重要な理由である。また、ＬＤＰＣコード構成における主要な問題は、デコーダ中のいくつかの処理エンジン（ノード）の間における接続ネットワークをどのようにして達成するかである。さらに、復号プロセスにおける計算負荷、とくに、チェックノード動作には問題がある。

したがって、簡単な符号化および復号プロセスを使用するＬＤＰＣ通信システムが必要とされている。高度な複雑さを伴なわずにＬＤＰＣコードを使用して高いデータレートを効率的にサポートすることもまた必要とされている。ＬＤＰＣエンコーダおよびデコーダの性能を改善する必要もある。ＬＤＰＣコード化を実施するために記憶要求を最小にすることもまた必要とされている。さらに、ＬＤＰＣデコーダ内の処理ノードの間の通信を簡単化する方式もまた必要とされている。

これらおよびその他の必要性は、構成された低密度パリティチェック（ＬＤＰＣ）コードを符号化する方法が提供される本発明によって解決される。ＬＤＰＣコードの構造は、パリティチェックマトリックスの一部分を下方の三角となるように制限し、および、またはデコーダのビットノードとチェックノードとの間の通信が簡単化されるように別の要求を満足することによって提供される。構成されたパリティチェックマトリックスを表す情報を記憶するメモリがアクセスされる。その情報は表形式で編成され、各行はパリティチェックマトリックスの列のグループの第１の列内における１の値の発生を表す。行はパリティチェックマトリックスの列のグループに対応し、各グループ内の後続する列は予め定められた演算（たとえば、論理桁送り、加法等）にしたがって導出される。ＬＤＰＣコード化された信号は、パリティチェックマトリックスを表す記憶された情報に基づいて出力される。本発明の１実施形態によると、Ｂｏｓｅ Ｃｈａｕｄｈｕｒｉ Ｈｏｃｑｕｅｎｇｈｅｍ（ＢＣＨ）エンコーダは、ＢＣＨコードを使用して入力信号を符号化するために送信機によって使用され、入力信号に対応した出力ＬＤＰＣコード化された信号は、外部ＢＣＨコードおよび内部ＬＤＰＣコードを有するコードを表している。さらに、周期的冗長検査（ＣＲＣ）コードにしたがって入力信号を符号化するためにＣＲＣエンコーダが提供される。この方法の利点は、ＬＤＰＣコードの適切な符号化および復号を行うことにある。

本発明の１実施形態の１つの特徴によると、ある１つの符号化方法が開示されている。この方法は、低密度パリティチェック（ＬＤＰＣ）コードの構成されたパリティチェックマトリックスを表す情報を記憶したメモリにアクセスするステップを含んでいる。その情報は表形式で編成され、各行はパリティチェックマトリックスの列のグループの第１の列内における１の値の発生を表している。行はパリティチェックマトリックスの列のグループに対応し、各グループ内の後続する列は予め定められた演算にしたがって導出される。この方法はまた、パリティチェックマトリックスを表す記憶された情報に基づいてＬＤＰＣコード化された信号を出力するステップを含んでいる。

本発明の１実施形態の別の特徴によると、低密度パリティチェック（ＬＤＰＣ）コードを生成するエンコーダが開示されている。このエンコーダは、ＬＤＰＣコードの構成されたパリティチェックマトリックスを表す情報を記憶したメモリを備えている。この情報は表形式で編成され、各行はパリティチェックマトリックスの列のグループの第１の列内における１の値の発生を表している 。行はパリティチェックマトリックスの列のグループに対応し、各グループ内の後続する列は予め定められた演算にしたがって導出される。このエンコーダはまた、ＬＤＰＣコード化された信号を出力するためにパリティチェックマトリックスを表す記憶された情報を検索する手段を備えている。

本発明の１実施形態の別の特徴によると、低密度パリティチェック（ＬＤＰＣ）コード化を使用する送信機が開示されている。この送信機は、ＬＤＰＣコードの構成されたパリティチェックマトリックスを表す情報を記憶したメモリを備え、その情報は表形式で編成され、各行はパリティチェックマトリックスの列のグループの第１の列内における１の値の発生を表す。行はパリティチェックマトリックスの列のグループに対応し、各グループ内の後続する列は予め定められた演算にしたがって導出される。この送信機はまた、メモリからの記憶された情報にアクセスしてＬＤＰＣコード化された信号を出力するように構成されたＬＤＰＣエンコーダを備えている。

本発明のさらに別のアスペクト、特徴および利点は、本発明を実施するために考えられた最良のモードを含む多数の特定の実施形態および構成を単に例示することにより以下の詳細な説明から容易に明らかになるであろう。本発明はまた別の異なった実施形態が可能であり、そのいくつかの詳細は種々の明白な点において本発明の技術的範囲を逸脱することなく修正されることができる。したがって、その図面および説明は何等発明の技術的範囲に制限を課すものではなく、本質的に例示とみなされるものである。

本発明は、添付図面の図において発明の技術的範囲を制限するものではなく単なる例示として示されている。なお、図面において、同じ参照符号は類似した構成要素を示している。
低密度パリティチェック（ＬＤＰＣ）コードを効率的に復号するためのシステム、方法およびソフトウェアを説明する。以下の説明において、多くの特定の詳細は本発明を完全に理解するために説明の目的で記載されている。しかしながら、本発明はこれらの特定の詳細なしで、あるいは等価の構成により実現可能であることは当業者に明らかである。他の例において、よく知られている構造および装置は、本発明をいたずらに不明瞭にすることを避けるためにブロック図の形態で示されている。

図１は、低密度パリティチェック（ＬＤＰＣ）コードを使用するように構成された本発明の１実施形態による通信システムの概略図である。デジタル通信システム100は、受信機105に対して通信チャンネル103を横切って信号波形を発生する送信機101を備えている。このディスクリートな通信システム100において、送信機101は可能なメッセージの離散セットを生成するメッセージソースを有しており、その可能なメッセージのそれぞれが対応した信号波形を有している。これらの信号波形は通信チャンネル103により減衰され、あるいはそうでなければ変更される。雑音チャンネル103に関するこの問題を克服するためにＬＤＰＣコードが使用される。

送信機101により発生されたＬＤＰＣコードは、パフォーマンス損失を招くことなく高速構成を可能にする。送信機101から出力されたこれらの構成されたＬＤＰＣコードは、変調方式（たとえば、８−ＰＳＫ）のためにすでにチャンネルエラーを受け易くなっているビットノードに対して少数のチェックノードを割当てることを避ける。

このようなＬＤＰＣコードは対応可能な復号アルゴリズム（ターボコードとは異なり）を有しており、それは加算、比較およびテーブルルックアップのような単純な動作を都合よく含んでいる。さらに、注意深く設計されたＬＤＰＣコードは、エラーフロアの兆候を示さない。

本発明の１実施形態によると、送信機101は受信機105と通信するために、比較的簡単な符号化技術を使用してパリティチェックマトリックス（復号中効率的なメモリアクセスを容易にする）に基づいてＬＤＰＣコードを発生する。送信機101は、ブロック長が十分に大きければ、連結されたターボ＋ＲＳ（リード・ソロモン）コードをしのぐことができるＬＤＰＣコードを使用する。

図２Ａおよび２Ｂは、図１の送信機内に配備された例示的なＬＤＰＣエンコーダの概略図である。図２Ａに見られるように、送信機200は、情報ソース201からの入力を受取って、受信機105におけるエラー補正処理に適した高度に冗長なコード化されたストリームを出力するＬＤＰＣエンコーダ203を備えている。情報ソース201は、デイスクリートなアルファベットＸからｋ個の信号を発生する。ＬＤＰＣコードはパリティチェックマトリックスにより特定される。他方において、ＬＤＰＣコードを符号化するには、一般に、ジェネレータマトリックスを特定する必要がある。たとえ、ガウスの消去法を使用してパリティチェックマトリックスからジェネレータマトリックスを得ることが可能であっても、結果的に得られるマトリックスはもはやスパースではなく、大きいジェネレータマトリックスを記憶することは複雑である可能性が高い。

エンコーダ203は、構造がパリティチェックマトリックスになるようにすることによってパリティチェックマトリックスだけを利用する簡単な符号化技術を使用してアルファベットＹから変調装置205に信号を発生する。とくに、パリティチェックマトリックスには、このマトリックスのある部分を三角であるように制約することによりある制限が課せられる。このようなパリティチェックマトリックスの構成は、以下図６においてさらに詳細に説明される。このような制限の結果、パフォーマンス損失は無視できる程度のものとなり、したがってこれは魅力的なトレードオフである。

変調装置205はエンコーダ203からの符号化されたメッセージを、送信アンテナ207に送られる信号波形にマップし、この送信アンテナ207は通信チャンネル103によりこれらの波形を放射する。送信アンテナ207からの送信は、以下に説明するように受信機に伝播する。

図２ＢはＢｏｓｅ Ｃｈａｕｄｈｕｒｉ Ｈｏｃｑｕｅｎｇｈｅｍ（ＢＣＨ）エンコーダおよび周期的冗長検査（ＣＲＣ）エンコーダにより使用される本発明の１実施形態によるＬＤＰＣエンコーダを示している。このシナリオでは、ＣＲＣエンコーダ209およびＢＣＨエンコーダ211と共にＬＤＰＣエンコーダ203により発生されたコードは、連結された外部ＢＣＨコードおよび内部低密度パリティチェック（ＬＤＰＣ）コードを有する。さらに、周期的冗長検査（ＣＲＣ）コードを使用してエラー検出が行われる。例示的な実施形態において、ＣＲＣエンコーダ209はジェネレータ多項式（ｘ⁵＋ｘ⁴＋ｘ³＋ｘ²＋１）（ｘ²＋ｘ＋１）（ｘ＋１）により８ビットＣＲＣコードを使用して符号化する。

ＬＤＰＣエンコーダ203は、

のサイズの情報ブロックを、

のサイズのコードワードに系統的に符号化する。コードワードの送信は所定の順序でｉ₀からスタートし、

で終了する。以下の表１には、ＬＤＰＣコードパラメータ（ｎ_ldpc，ｋ_ldpc）が示されている。

ＬＤＰＣエンコーダ203のタスクは、ｋ_ldpcの情報ビット：

のあらゆるブロックに対するｎ_ldpc−ｋ_ldpcのパリティビット：

を決定することである。その手順は次のとおりである。最初に、パリティビットが初期化される；

表３乃至１０の第１の行において指定されたパリティビットアドレスで第１の情報ビットｉ₀が累算される。たとえば、レート２／３（表３）に対する結果は次のようになる：

（全ての加算はＧＦ（２）内のものである。）

その後、次の３５９個の情報ビットｉ_m，ｍ＝１，２，…，３５９については、これらのビットはパリティビットアドレス｛ｘ＋ｍ ｍｏｄ３６０×ｑ｝ｍｏｄ（ｎ_ldpc−ｋ_ldpc）で累算され、ここでｘは第１のビットｉ₀に対応したパリティビット累算装置のアドレスを示し、ｑは表２において特定されたコードレート依存定数を示している。この例を続けると、レート２／３に対してｑ＝６０である。例示すると、情報ビットｉ₁に対して、以下の演算が行われる：

３６１番目の情報ビットｉ₃₆₀に関しては、パリティビット累算装置のアドレスは表３乃至１０の第２の行中に与えられる。同様に、後続する３５９個の情報ビットｉ_m，ｍ＝３６１，３６２，…，７１９に対するパリティビット累算装置のアドレスは公式｛ｘ＋ｍ ｍｏｄ３６０×ｑ｝ｍｏｄ（ｎ_ldpc−ｋ_ldpc）を使用して得られ、ここでｘは情報ビットｉ₃₆₀、すなわち、表３乃至１０の第２の行の中のエントリに対応したパリティビット累算装置のアドレスを示している。同様に、３６０の新しい情報ビットのグループ毎に、パリティビット累算装置のアドレスを見出すために表３乃至１０からの新しい行が使用される。

全ての情報ビットが使い尽くされた後、最後のパリティビットは次のように得られる。最初に、以下の演算がｉ＝１からスタートして行われる：

ｐ_i，ｉ＝０，１，…，ｎ_ldpc−ｋ_ldpc−１の最後の内容はパリティビットｐ_iに等しい。

ＢＣＨエンコーダ211に関して、ＢＣＨコードパラメータは表１１に列挙されている。

上記の表において、ｎ_bch＝ｋ_ldpcであることが認識される。

ｔエラー補正ＢＣＨエンコーダ211のジェネレータ多項式は、以下の表１２のリスト中の最初のｔ個の多項式を乗算することにより得られる：

コードワード：

への情報ビット：

のＢＣＨ符号化は、次のように行われる。メッセージ多項式：

は、

により乗算される。次に、

がｇ（ｘ）により除算される。

を剰余とすると、コードワード多項式は次のように定められる：

上記のＬＤＰＣコードは、例示的な実施形態において、ＭＰＥＧ（モーション・ピクチャ・エキスパート・グループ）パケット伝送のような種々のデジタルビデオアプリケーションに使用されることができる。

図３は、図１のシステム内の例示的な受信機の概略図である。受信側において、受信機300は、送信機200から受信された信号の復調を行う復調装置301を備えている。これらの信号は、復調のために受信アンテナ303で受信される。受信された信号は復調後にデコーダ305に転送され、このデコーダ305はビット計量発生装置307と協力してメッセージＸ’を発生することにより元のソースメッセージの再構成を試みる。非グレーマッピングに関して、ビット計量発生装置307は復号プロセス中にデコーダ305と確率情報を前後に（反復的に）交換する。これは図１０に詳細に示されている。その代りに、グレーマッピングが使用された（本発明の１実施形態にしたがって）場合、ビット計量発生装置307の１つのパスで十分であり、このとき各ＬＤＰＣデコーダ反復の後におけるビット計量発生の別の試みにより、限られたパフォーマンス改良が得られる可能性が高い。このアプローチは、図１１に関してさらに詳細に説明される。本発明によって提供される利点を認識するために、図４において説明されるように、ＬＤＰＣコードがどのようにして発生されるかを示すことが有益である。

図４は、本発明の１実施形態によるスパースパリティチェックマトリックスの概略図である。ＬＤＰＣコードは、スパースパリティチェックマトリックスＨ_(n-k)xnを有する長い線形ブロックコードである。典型的に、ブロック長ｎの範囲は何千乃至何万のビットである。図４には、たとえば、長さｎ＝８およびレート１／２のＬＤＰＣコードに対するパリティチェックマトリックスが示されている。同じコードは図５における２部分グラフにより等価に表されることができる。

図５は、図４のマトリックスのＬＤＰＣコードの２部分グラフの概略図である。パリティチェック方程式は、各チェックノードに対して、全ての隣接したビットノードの和（ＧＦ（ガロア域）（２）にわたる）がゼロに等しいことを示すものである。図面に示されているように、ビットノードはグラフの左側を占め、予め定められた関係にしたがって１以上のチェックノードと関連している。たとえば、チェックノードｍ₁に対応して、式：ｎ₁＋ｎ₄＋ｎ₅＋ｎ₈＝０がビットノードに関して存在する。

受信機303に戻ると、ＬＤＰＣデコーダ305はメッセージパッシングデコーダとみなされ、それによってデコーダ305はビットノードの値を見出すことをめざしている。このタスクを行うために、ビットノードおよびチェックノードは互いに反復的に通信する。以下、この通信の特性を以下説明する。

チェックノードからビットノードへは、各チェックノードは隣接したビットノードに別の隣接したビットノードからの情報に基づいてそのビットノードの値に関する推定値（“オピニオン”）を提供する。たとえば、上記の例において、ｎ₄，ｎ₅およびｎ₈の和がｍ₁に０“のように見えた”場合、ｍ₁は、ｎ₁の値が０であると考えられる（ｎ₁＋ｎ₄＋ｎ₅＋ｎ₈＝０であるため）ことをｎ₁に示す；その他の場合には、ｍ₁は、ｎ₁の値が１であると考えられることをｎ₁に示す。さらに、ソフト決定復号のために、信頼性尺度が追加される。

ビットノードからチェックノードへは、各ビットノードは隣接したチェックノードに対してそれの別の隣接したチェックノードからのフィードバックに基づいてそれ自身の値に関する推定値を中継する。上記の例において、ｎ₁は２つの隣接したチェックノードｍ₁およびｍ₃だけを有している。ｍ₃からｍ₁へのフィードバックがｎ₁の値がおそらく０であることを示した場合、ｎ₁はｎ₁自身の値の推定値が０であることをｍ₁に知らせる。ビットノードが３以上の隣接したチェックノードを有している場合に対しては、ビットノードは、それが通信するチェックノードにその決定を報告する前に、それの別の隣接したチェックノードからのフィードバックに関する多数決投票（ｍａｊｏｒｉｔｙ ｖｏｔｅ）（ソフト決定）を行う。上記のプロセスは、全てのビットノードが正しいとみなされる（すなわち、全てのパリティチェック方程式が満足される）まで、あるいは予め定められた最大反復数に達し、それによって復号の失敗が宣言されるまで繰返される。

図６は、サブマトリックスが下方三角領域に制限されたパリティチェック値を含んでいる、本発明の１実施形態によるスパースパリティチェックマトリックスのサブマトリックスの概略図である。上述されたように、エンコーダ203（図２Ａおよび２Ｂの）は、パリティチェックマトリックスの下方の三角領域に値を制限することにより単純な符号化技術を使用することができる。本発明の１実施形態によると、パリティチェックマトリックスに課せられる制限は、
Ｈ_(n-k)xn＝［Ａ_(n-k)xkＢ_(n-k)x(n-k)］
の形式のものであり、ここで、Ｂは下方の三角である。

任意の情報ブロックｉ＝（ｉ₀，ｉ₁，…，ｉ_k-1）は、Ｈｃ^T＝０を使用して、パリティビットについて反復的に解くことによりコードワードｃ＝（ｉ₀，ｉ₁，…，ｉ_k-1，ｐ₀，ｐ₁，…ｐ_n-k-1）に符号化される。たとえば、

ｐ₂，ｐ₃，…，ｐ_n-k-1に対しても同様である。

図７は、制限されていないパリティチェックマトリックス（Ｈマトリックス）を使用したコードと図６の制限されたＨマトリックスを使用したコードとの間のパフォーマンスを示すグラフである。このグラフは、一方が一般的なパリティチェックマトリックスによるものであり、他方が符号化を簡単化するために下方の三角に制限されたパリティチェックマトリックスによるものである２つのＬＤＰＣコードの間のパフォーマンス比較を示している。変調方式は、このシミュレーションにおいて８−ＰＳＫである。パフォーマンス損失は０．１ｄＢ以内である。したがって、パフォーマンス損失は下方の三角Ｈマトリックスの制限に基づいて無視できる程小さく、一方符号化技術の簡単化による利得は大きい。したがって、行および、または列置換（ｐｅｒｍｕｔａｔｉｏｎ）状態において下方の三角または上方の三角に等価であるパリティチェックマトリックスが同じ目的のために使用されることができる。

図８Ａおよび８Ｂはそれぞれ、図１のシステムにおいてそれぞれ使用されることのできる非グレー８−ＰＳＫ変調方式およびグレー８−ＰＳＫ変調方式の概略図である。図８Ａの非グレー８−ＰＳＫ方式は図３の受信機において使用され、非常に低いフレーム消去レート（ＦＥＲ）を必要とするシステムを提供することができる。この要求はまた、Ｂｏｓｅ，Ｃｈａｕｄｈｕｒｉ，およびＨｏｃｑｕｅｎｇｈｅｍ（ＢＣＨ）、ハミング、またはリード・ソロモン（ＲＳ）コードのような外部コードと共同して図８Ｂに示されているグレー８−ＰＳＫ方式を使用することにより満足されることができる。

この方式の下では、８−ＰＳＫ変調を使用することのできるＬＤＰＣデコーダ305（図３）とビット計量発生装置307との間で繰返しを行う必要はない。外部コードが存在しないとき、グレーラベル付けを使用するＬＤＰＣデコーダ305は、以下において図９で示されるように早期のフロアエラーを示す。

図９は、図８Ａのグレーラベル付けを使用したコードと図８Ｂの非グレーラベル付けを使用したコードとの間のパフォーマンスを示すグラフである。エラーフロアは、ＬＤＰＣデコーダ305からの正しいフィードバックを仮定すると、既知の２ビットによる２つの８−ＰＳＫシンボルは非グレーラベル付けによるほうがいっそう遠くに離れているため、非グレーラベル付けによる８−ＰＳＫビット計量の再生のほうが正確であることに由来する。これは同様に、高い信号対雑音比（ＳＮＲ）での動作として見られる。したがって、グレーまたは非グレーラベル付けを使用した同じＬＤＰＣコードのエラー漸近線が同じ傾斜を有していても（すなわち、互いに平行であっても）、非グレーラベル付けによるものは任意のＳＮＲで低いＦＥＲを通過する。

他方において、それ程低いＦＥＲを必要としないシステムに対しては、ＬＤＰＣデコーダ305と８−ＰＳＫビット計量発生装置307との間の反復を伴なわないグレーラベル付けのほうが適切かもしれない。これは、全ての各ＬＤＰＣデコーダ反復の前に８−ＰＳＫビット計量を再生することにより、追加の複雑さが生じるためである。さらに、グレーラル付けが使用されたとき、全ての各ＬＤＰＣデコーダ反復の前に８−ＰＳＫビット計量を再生しても、ごくわずかなパフォーマンス改善しか得られない。上述したように、反復を伴なわないグレーラベル付けは、外部コードが構成される場合、非常に低いＦＥＲを必要とするシステムに対して使用されることができる。

グレーラベル付けと非グレーラベル付けとの間の選択はまた、ＬＤＰＣコードの特性にも依存する。典型的に、ビットまたはチェックノード度が高くなると、それだけいっそうグレーラベル付けが適切になる。これは、高いノード度に関しては、非グレーラベル付けによるほうが、ＬＤＰＣデコーダ305から８−ＰＳＫ（または類似の高次の変調）ビット計量発生装置307への最初のフィードバックが低下するためである。

８−ＰＳＫ（または類似の高次の）変調が２進デコーダにより使用されたとき、シンボルの３（以上の）ビットは“等しい雑音で”受取られないことが認識される。たとえば、グレー８−ＰＳＫラベル付けに関して、あるシンボルの第３のビットはデコーダに対する雑音が他の２ビットより多いと考えられる。したがって、ＬＤＰＣコード設計では、８−ＰＳＫシンボルの“雑音が多い”第３のビットにより表されるこれらのビットノードは、これらのビットが２度とペナルティーを科せられないように、少数のエッジを割当てられない。

図１０は、本発明の１実施形態による非グレーマッピングを使用するＬＤＰＣデコーダの動作のフローチャートである。このアプローチの下では、ＬＤＰＣデコーダおよびビット計量発生装置は、次々に反復する。この例においては、８−ＰＳＫ変調が使用されている。しかしながら、同じ原理は他の高次変調方式にも適用される。このシナリオにおいて、復調装置301は、受取られた雑音の多いシンボル地点と８−ＰＳＫシンボル地点との間の距離を表す距離ベクトルｄをビット計量発生装置307に出力することを仮定すると、ベクトルコンポーネントは次のようになる：

８−ＰＳＫビット計量発生装置307は、ｕおよびａとしてそれぞれ表される演繹的確率情報および経験的確率情報を交換するためにＬＤＰＣデコーダ305と通信する。すなわち、ベクトルはｕおよびａはそれぞれコードビットの対数尤度比の演繹的確率情報および経験的確率情報を表す。

８−ＰＳＫビット計量発生装置307は、次のように３ビットの各グループに対する演繹的尤度比を生成する。最初に、コード化されたビットに関する非本質的情報が得られる：
ｅ_ｊ＝ａ_ｊ−ｕ_ｊ ｊ＝０，１，２
次に、８−ＰＳＫシンボル確率：ｐ_i （ｉ＝０，１，…，７）が決定される。

次に、ビット計量発生装置307は以下のように、ＬＤＰＣデコーダ305への入力としてコード化されたビットの演繹的対数尤度比を決定する：

３以上の変数を有する関数ｆ（．）は、たとえば、ｆ（ａ，ｂ，ｃ）＝ｆ（ｆ（ａ，ｂ），ｃ）のように反復的に推定されることが可能なことが認識される。

以下、非グレーマッピングを使用するＬＤＰＣデコーダ305の動作を説明する。ステップ1001において、ＬＤＰＣデコーダ305は以下にしたがった（および図１２Ａに示されているように）最初の反復の前に、コード化されたビットｖの対数尤度比を初期化する：

ステップ1003において、チェックノードｋが更新され、それによって入力ｖにより出力ｗが得られる。図１２Ｂに見られるように、チェックノードｋに対してそのｄ_cの隣接ビットノードから入ってきたメッセージは、

によって示される。目的は、ｄ_cの隣接ビットノードに戻ってチェックノードｋから出ていくメッセージを計算することである。これらのメッセージは、次のように示される：

この関数ｇ（）は以下のように規定される：

関数ｆに類似して、３以上の変数を有する関数ｇは、反復的に推定されることができる。

次に、ステップ1005において、デコーダ305は、以下の関係が成立するように経験的確率情報を出力する（図１２のＣ）：

ステップ1007において、全てのパリティチェック式が満足されたか否かが決定される。これらのパリティチェック式が満足されていない場合、デコーダ305はステップ1011に示されているように、８−ＰＳＫビット計量およびチャンネル入力ｕ_nを再度求める。次に、ビットノードはステップ1013に示されているように更新される。図１４Ｃに示されているように、ビットノードｎに対してそれのｄ_vの隣接チェックノードから入ってきたメッセージは、

によって示される。ビットノードｎから出ていくメッセージはｄ_vの隣接ビットノードに戻って計算される；このようなメッセージは、

によって示され、次のように計算される：

ステップ1013において、デコーダ305はハード決定を出力する（全てのパリティチェック式が満足される場合に）：

上記のアプローチは、非グレーラベル付けが使用されたときに適切である。しかしながら、グレーラベル付けが実施されたとき、図１１のプロセスが実行される。

図１１は、本発明の１実施形態によるグレーマッピングを使用する図３のＬＤＰＣデコーダの動作のフローチャートである。グレーラベル付けが使用されたとき、全ての各ＬＤＰＣデコーダ反復の後にビット計量を再生することにより公称パフォーマンス改善が得られる可能性があるため、ビット計量は都合よくＬＤＰＣデコーダの前に一度だけ生成されることが有効である。図１０のステップ1001および1003に関するように、ステップ1101においてコードビッドｖの対数尤度比の初期化が行われ、ステップ1103においてチェックノードが更新される。次にステップ1105に示されているように、ビットノードｎが更新される。その後、デコーダは経験的確率情報を出力する（ステップ1107）。ステップ1109において、全てのパリティチェック式が満足されているか否かが決定される：そうであるならば、デコーダはハード決定を出力する（ステップ1111）。そうでない場合には、ステップ1103-1107が繰返される。

図１３のＡは、順方向・逆方向アプローチを使用してチェックノードとビットノードとの間の出ていくメッセージを計算する本発明の１実施形態によるプロセスのフローチャートである。ｄ_cの隣接エッジを有するチェックノードに対して、ｄ_c（ｄ_c−１）および多数のｇ（．，．）関数の計算が行われる。しかしながら、順方向・逆方向アプローチは計算の複雑さを３（ｄ_c−２）に軽減し、この場合ｄ_c−１の変数が記憶される。

図１２のＢに戻ると、チェックノードｋに対してそのｄ_cの隣接ビットノードから入ってきたメッセージは次のように示される：

出ていくメッセージは、チェックノードｋからｄ_cの隣接ビットノードに戻って計算されることが望ましい；これらの出ていくメッセージは次のように示されている：

出ていくメッセージの計算に対する順方向・逆方向アプローチの下では、順方向変数ｆ₁，ｆ₂，…，ｆ_dcは以下のように規定される：

これらの順方向変数はステップ1301において計算され、ステップ1303で記憶される。

同様に、逆方向変数ｂ₁，ｂ₂，…，ｂ_dcは以下のように規定される：

それから、これらの順方向変数はステップ1305において計算される。その後、ステップ1307において、記憶された順方向変数および計算された逆方向変数に基づいて出ていくメッセージが計算される。この出ていくメッセージは次のように計算される：

このアプローチの下において、順方向変数ｆ₂，ｆ₃，…，ｆ_dcだけが記憶される必要がある。逆方向変数ｂ_iは計算されているので、出ていくメッセージ：

は同時に計算され、それによって逆方向変数を記憶する必要性をなくする。

次に説明するように、計算負荷は並列アプローチによってさらに増強されることができる。

図１３のＢは、並列アプローチを使用してチェックノードとビットノードとの間の出ていくメッセージを計算する本発明の１実施形態によるプロセスのフローチャートである。ｄ_cの隣接ビットノードからの入力：

を有するチェックノードｋに対して、ステップ1311に示されているように、以下のパラメータが計算される：

ｇ（．，．）関数はまた、次のように表されることができることが認識される：

ｇ（．，．）関数の反復特性を利用することにより、結果的に次式が得られる：

したがって、

は以下のように解かれることができる：

上記の式のｌｎ（．）の項は、関数ｌｎ｜ｅ^x−１｜を表すルックアップテーブルＬＵＴ_xを使用して得られる（ステップ1313）。他のルックアップテーブルＬＵＴ_fまたはＬＵＴ_gとは異なり、このＬＵＴ_xはおそらく、量子化レベルの数と同じ数のエントリを必要とする。γ_kが得られると、ステップ1315に示されているように、全てのｎ_iに対する

の計算は、上記の方程式を使用して並列に行われることができる。

γ_kの計算の待ち時間は、都合よく、ｌｏｇ₂（ｄ_c）である。

図１４Ａ乃至図１４Ｃは、本発明の種々の実施形態にしたがって発生されたＬＤＰＣコードのシミュレーション結果を示すグラフである。とくに、図１４Ａ乃至図１４Ｃは、高次の変調と３／４（ＱＰＳＫ、１．４８５ビット／シンボル）、２／３（８−ＰＳＫ、１．９８０ビット／シンボル）、および５／６（８−ＰＳＫ、２．４７４ビット／シンボル）のコードレートを有するＬＤＰＣコードのパフォーマンスを示している。

チェックノードとビットノードとの間の相互接続を実現するための２つの一般的なアプローチ、すなわち：（１）完全並列アプローチ、および（２）部分的並列アプローチが存在する。完全並列アーキテクチャにおいて、ノードおよびそれらの相互接続の全てが物理的に構成される。このアーキテクチャの利点は速度である。

しかしながら、完全並列アーキテクチャは全てのノードおよびそれらの相互接続を行うときにかなりの複雑さを伴う可能性がある。したがって、完全並列アーキテクチャでは、複雑さを減少させるために小さいブロックサイズが必要とされる可能性がある。その場合には、結果的に、同じクロック周波数に対して、スループットが比例して減少すると共に、ＦＥＲ対Ｅｓ／Ｎｏパフォーマンスにおいて若干の低下が生じる可能性がある。

ＬＤＰＣコードの構成に対する第２のアプローチは、ノードの総数の部分集合だけを物理的に実現し、これらの限られた数の“物理的”ノードを使用して、そのコードの“機能的”ノードを全て処理することである。ＬＤＰＣデコーダの動作が非常に単純なものにされることが可能であり、並列に行われることが可能でも、設計における別の難題は、“ランダムに”分布されたビットノードとチェックノードとの間において通信がどのようにして設定されるかである。本発明の１実施形態によるデコーダ305（図３の）は見かけ上ランダムなコードを実現するようにある構成方式でメモリにアクセスすることによってこの問題を解決する。図１５Ａおよび図１５Ｂに関して、このアプローチを説明する。

図１５Ａおよび図１５Ｂはそれぞれ、ＬＤＰＣコード化のときにランダム化を達成するために構成されたアクセスをサポートするように編成された本発明の１実施形態によるメモリの上方エッジおよび下方エッジの概略図である。構成されたアクセスは、パリティチェックマトリックスの発生に集中することにより、真にランダムなコードのパフォーマンスに妥協せずに行われることができる。一般に、パリティチェックマトリックスは、チェックノードとビットノードとの接続により特定されることができる。たとえば、ビットノードは、例示のために３９２である固定されたサイズのグループに分割されることができる。さらに、度数３の第１のビットノードに接続されるチェックノードは、たとえば、ａ，ｂおよびｃの番号を付けられることを仮定すると、第２のビットノードに接続されるチェックノードはａ＋ｐ，ｂ＋ｐおよびｃ＋ｐの番号を付けられ、第３のビットノードに接続されるチェックノードはａ＋２ｐ，ｂ＋２ｐおよびｃ＋２ｐ等の番号を付けられ、ここでｐ＝（チェックノードの数）／３９２である。３９２ビットノードの次のグループに対しては、ｐの適切な選択により全てのチェックノードが同じ度数を有するように、第１のビットノードに接続されるチェックノードはａ，ｂ，ｃとは異なっている。結果的に得られるＬＤＰＣコードがサイクル４およびサイクル６フリーであるように、ランダムサーチが自由定数に対して行われる。本発明のパリティチェックマトリックスの構造上の特徴のために、エッジ情報は復号中に関連したエッジ値のグループへの並行アクセスを可能にするように記億されることができる。

換言すると、本発明のアプローチは、チェックノードおよびビットノード処理中のメモリアクセスを容易にする。２部分グラフにおけるエッジの値は、ランダムアクセスメモリ（ＲＡＭ）のような記憶媒体中に記憶されることができる。チェックノードおよびビットノードの処理中、真にランダムなＬＤＰＣコードに対してエッジの値はランダムな方式で１つづつアクセスされる必要があることが認識される。しかしながら、このような通常のアクセス方式は、高いデータレートのアプリケーションには遅過ぎる。図１５Ａおよび図１５ＢのＲＡＭは、関連したエッジの大きいグループが１クロックサイクルで取り出されることができる方式で編成されている；したがって、これらの値は予め定められた方式または配列にしたがってメモリ中に“一緒に”配置されている。実際には、真にランダムなコードでさえ、チェックノード（およびそれぞれにビットノード）のグループに対しては、関連エッジはＲＡＭ中に隣接して配置されることが可能であるが、しかしビットノード（それぞれにチェックノード）のグループに隣接した関連エッジはＲＡＭ中においてランダムに分散されることが認識される。したがって、本発明における“一緒”はパリティチェックマトリックス自身の設計に由来する。すなわち、このチェックマトリックス設計は、ビットノードとチェックノードのグループに対する関連エッジがＲＡＭ中に同時に一緒に配置されることを保証する。

図１５Ａおよび図１５Ｂに見られるように、各ボックスは、多くのビット（たとえば、６）であるエッジの値を含んでいる。本発明の１実施形態によるエッジＲＡＭは、上方エッジＲＡＭ1501(図１５Ａ)および下方エッジＲＡＭ1503(図１５Ｂ)の２つの部分に分割されている。下方エッジＲＡＭ1503は、たとえば、度数２のビットノードとチェックノードとの間のエッジを含んでいる。上方エッジＲＡＭは、２より大きい度数のビットノードとチェックノードとの間のエッジを含んでいる。したがって、あらゆるチェックノードに対して、２つの隣接したエッジが下方エッジＲＡＭ1503中に記憶され、そのエッジの残りのものは上方エッジＲＡＭ1501中に記憶される。たとえば、種々のコードレートに対する上方エッジＲＡＭ1501および下方エッジＲＡＭ1503のサイズは表１４に示されている：

この表１４に基づいて、サイズが５７６×３９２のエッジＲＡＭは、１／２、２／３、３／４および５／６の全てのコードレートに対するエッジマトリックスを記憶するのに十分である。

認識されるように、この例示的なシナリオ下では、一度で処理するために３９２のビットノードと３９２のチェックノードのグループが選択される。３９２のチェックノード処理については、（ｑ＝ｄ_c−２）個の連続した行が上方エッジＲＡＭ1501からアクセスされ、２つの連続した行が下方エッジＲＡＭ1503からアクセスされる。ｄ_cの値は特定のコードに依存し、たとえば、上記のコードについてはレート１／２に対してｄ_c＝７、レート２／３に対してｄ_c＝１０、レート３／４に対してｄ_c＝１６、およびレート５／６に対してｄ_c＝２２である。当然ながら、別のコードに対するｄ_cの別の値が可能である。この例において、ｑ＋２は各チェックノードの度数である。

ビットノード処理について、３９２のビットノードのグループが度数２を有している場合、それらのエッジは下方エッジＲＡＭ1503の２つの連続した行中に配置される。ビットノードが度数ｄ＞２を有している場合、それらのエッジは上方エッジＲＡＭ1501のあるｄの行の中に配置される。これらのｄ行のアドレスは、読出し専用メモリ（ＲＯＭ）のような不揮発性メモリ中に記憶されることができる。その行の１つの中のエッジは３９２のビットノードの第１のエッジに対応し、別の行中のエッジは３９２のビットノードの第２のエッジに対応する等々である。さらに、各行に対して、３９２のグループ中の第１のビットノードに属するエッジの列インデックスもまたＲＯＭ中に記憶されることができる。第２、第３等の他のビットノードに対応したエッジは“ラップアラウンド”方式で開始時の列インデックスに続く。たとえば、行の中のｊ番目のエッジが第１のビットノードに属している場合、（ｊ＋１）番目のエッジは第２のビットノードに属し、（ｊ＋２）番目のエッジは第３のビットノードに属し、・・・、（ｊ−１）番目のエッジは第３９２のビットノードに属する。

図１５Ａおよび１５Ｂに示されている編成により、メモリアクセスの速度はＬＤＰＣコード化中に大幅に増加される。

図１６は、本発明による実施形態が実施されることのできるコンピュータシステムを示している。コンピュータシステム1600はバス1601または情報を伝達する別の通信メカニズムと、バス1601に接続された情報を処理するプロセッサ1603とを備えている。コンピュータシステム1600はまた、バス1601に接続されてプロセッサ1603により実行されるべき命令および情報を記憶するランダムアクセスメモリ（ＲＡＭ）または別の動的装置のような主メモリ1605を備えている。この主メモリ1605はまた、命令がプロセッサ1603により実行されている期間中に一時的な変数またはその他の中間的な情報を記憶するために使用されることができる。コンピュータシステム1600はさらに、静的情報およびプロセッサ1603に対する命令を記憶する読出し専用メモリ（ＲＯＭ）1607または別の静的記憶装置を備え、それはバス1601に接続されている。さらにバス1601には、情報および命令を記憶する磁気ディスクまたは光学ディスクのような記憶装置1609が接続されている。

コンピュータシステム1600は、情報をコンピュータユーザに表示する陰極線管（ＣＲＴ）、液晶ディスプレイ、アクティブマトリックスディスプレイ、またはプラズマディスプレイのような表示装置1611に対してバス1601を介して結合されてもよい。バス1601には、情報およびコマンド選択をプロセッサ1603に伝達する英数字その他のキーを含むキーボードのような入力装置1613が結合されている。別のタイプのユーザ入力装置は、方向情報およびコマンド選択をプロセッサ1603に伝達すると共に表示装置1611上のカーソルの移動を制御するマウス、トラックボール、またはカーソル方向キーのようなカーソル制御装置1615である。

本発明の１実施形態によると、ＬＤＰＣコードの発生は、主メモリ1605中に含まれている命令のアレンジメントを実行するプロセッサ1603に応答してコンピュータシステム1600により行われる。このような命令は、記憶装置1609のような別のコンピュータ読出し可能な媒体から主メモリ1605中に読出されることができる。プロセッサ1603は、主メモリ1605中に含まれている命令のアレンジメントを実行することによりこの明細書に記載されている処理ステップを行う。多重処理構成された１以上のプロセッサもまた、主メモリ1605中に含まれている命令を実行するために使用されてもよい。別の実施形態において、本発明の実施形態を実施するソフトウェア命令の代りに、またはそれと共にハードワイヤード回路が使用されてもよい。したがって、本発明の実施形態はハードウェア回路およびソフトウェアの特定の組合せに限定されない。

コンピュータシステム1600はまた、バス1601に接続された通信インターフェース1617を備えている。この通信インターフェース1617は、ローカルネットワーク1621に接続されたネットワークリンク1619に結合された両方向データ通信を提供する。たとえば、通信インターフェース1617は、デジタル加入者ライン（ＤＳＬ）カードまたはモデム、統合サービスデジタル網（ＩＳＤＮ）カード、ケーブルモデム、あるいは対応したタイプの電話線に対するデータ通信接続を提供するための電話モデムであってもよい。別の例として、通信インターフェース1617は、適合するＬＡＮへのデータ通信接続を行う他のローカルエリアネットワーク（ＬＡＮ）カード（たとえば、イーサネット（登録商標）または非同期転送モデル（ＡＴＭ）ネットワーク用の）であってもよい。無線リンクもまた構成されることができる。任意のこのような構成において、通信インターフェース1617は、種々のタイプの情報を表すデジタルデータストリームを伝送する電気信号、電磁信号または光信号を送受信する。さらに、通信インターフェース1617は、ユニバーサルシリアルバス（ＵＳＢ）インターフェース、ＰＣＭＣＩＡ（パーソナルコンピュータメモリカードインターナショナルアソシエーション）インターフェース等のような周辺インターフェース装置を備えていることができる。

ネットワークリンク1619は典型的に、１以上のネットワークによる別のデータサービスへのデータ通信を提供する。たとえば、ネットワークリンク1619は、ネットワーク1625（たとえば、広域ネットワーク（ＷＡＮ）または今は“インターネット”と呼ばれているグローバルパケットデータ通信ネットワーク）への、あるいはサービスプロバイダにより動作されるデータ装置への接続を有するホストコンピュータ1623へローカルネットワーク1621を通って接続を提供することができる。ローカルネットワーク1621およびネットワーク1625は共に電気信号、電磁信号または光信号を使用して情報および命令を伝達する。種々のネットワークを通る信号、ネットワークリンク1619上の信号、およびコンピュータシステム1600とデジタルデータを通信する通信インターフェース1617からの信号は、情報および命令を伝送する例示的な形態の搬送波である。

コンピュータシステム1600は、ネットワーク、ネットワークリンク1619および通信インターフェース1617を通ってメッセージを送り、プログラムコードを含むデータを受信することができる。インターネットの例では、サーバ（示されていない）は、本発明の１実施形態を実施するアプリケーションプログラムに属するリクエストされたコードをネットワーク1625、ローカルネットワーク1621および通信インターフェース1617を通って送信する。プロセッサ1603は、その送信されたコードが受信され、および、または後に実行されるために記憶装置1609または別の不揮発性記憶装置中に記憶されているあいだにこれを実行することができる。このようにして、コンピュータシステム1600はアプリケーションコードを搬送波の形態で得ることができる。

この明細書において使用されている“コンピュータ読出し可能な媒体”という用語は、命令をその実行のためにプロセッサ1603に与えることに関係する任意の媒体を示している。このような媒体は、不揮発性媒体、揮発性媒体および伝送媒体を含むが、それに限定されない多くの形態をとることができる。不揮発性媒体には、たとえば、記憶装置1609のような光学または磁気ディスクが含まれる。揮発性媒体には、主メモリ1605のような動的記憶装置が含まれる。伝送媒体には、バス1601を構成するワイヤを備えた同軸ケーブル、銅線および光ファイバが含まれる。伝送媒体はまた、無線周波数（ＲＦ）および赤外線（ＩＲ）データ通信中に生成されたもののような音波、光または電磁波の形態をとることができる。一般的な形態のコンピュータ読出し可能な媒体には、たとえば、フロッピー（Ｒ）ディスク、フレキシブルディスク、ハードディスク、磁気テープ、任意の他の磁気媒体、ＣＤ−ＲＯＭ、ＣＤＲＷ、ＤＶＤ、任意の他の光学媒体、パンチカード、紙テープ、光学式マークシート、孔のパターンまたは光学的に認識可能なしるしを有する任意の他の物理的媒体、ＲＡＭ、ＰＲＯＭ、およびＥＰＲＯＭ、ＦＬＡＳＨ−ＥＰＲＯＭ、任意の他のメモリチップまたはカートリッジ、搬送波、あるいはコンピュータが読出すことのできる任意の他の媒体が含まれる。

種々の形態のコンピュータ読出し可能な媒体が、命令をその実行のためにプロセッサに与えるために使用されることができる。たとえば、本発明の少なくとも一部を実行する命令は最初に、遠隔コンピュータの磁気ディスク上で生成されてもよい。このようなシナリオでは、遠隔コンピュータは命令を主メモリ中にロードし、その命令をモデムを使用して電話線で送信する。ローカルコンピュータシステムのモデムは電話線上のデータを受信し、赤外線送信機を使用してそのデータを赤外線信号に変換し、その赤外線信号をパーソナルデジタルアシスタント（ＰＤＡ）およびラップトップのような可搬計算装置に送信する。この可搬計算装置上の赤外線検出器は、赤外線信号から生成された情報および命令を受取ってそのデータをバスに供給する。バスはデータを主メモリに送り、この主メモリからプロセッサが命令を検索し、実行する。主メモリにより受取られた命令は、プロセッサによる実行の前または後に随意に記憶装置上に記憶されることができる。

このように、本発明の種々の実施形態は、構成された低密度パリティチェック（ＬＤＰＣ）コードを符号化する方法を提供する。ＬＤＰＣコードの構造は、パリティチェックマトリックスの一部分を下方の三角となるように制限し、および、またはデコーダのビットノードとチェックノードとの間の通信が簡単化されるように別の要求を満足することによって提供される。構成されたパリティチェックマトリックスを表す情報を記憶するメモリがアクセスされる。その情報は表形式で編成され、各行はパリティチェックマトリックスの列のグループの第１の列内における１の値の発生を表す。行はパリティチェックマトリックスの列のグループに対応し、各グループ内の後続する列は予め定められた演算（たとえば、論理桁送り、加法等）にしたがって導出される。ＬＤＰＣコード化された信号は、パリティチェックマトリックスを表す記憶された情報に基づいて出力される。本発明の１実施形態によると、Ｂｏｓｅ Ｃｈａｕｄｈｕｒｉ Ｈｏｃｑｕｅｎｇｈｅｍ（ＢＣＨ）エンコーダは、ＢＣＨコードを使用して入力信号を符号化するために送信機によって使用され、入力信号に対応した出力ＬＤＰＣコード化された信号は、外部ＢＣＨコードおよび内部ＬＤＰＣコードを有するコードを表している。さらに、周期的冗長検査（ＣＲＣ）コードにしたがって入力信号を符号化するためにＣＲＣエンコーダが提供される。上記の方法の利点は、性能を犠牲にすることなく複雑さを軽減することにある。

本発明はいくつかの実施形態および構成との関連して説明されたが、本発明はそれにより限定されるものではなく、添付されている請求の範囲の技術的範囲内にある種々の明らかな修正および等価な構成を包含するものである。

本発明の１実施形態にしたがって低密度パリティチェック（ＬＤＰＣ）コードを使用するように構成された通信システムの概略図。 図１の送信機内に配備された例示的なＬＤＰＣエンコーダの概略図。 図１の送信機内に配備された例示的なＬＤＰＣエンコーダの概略図。 図１のシステム内の例示的な受信機の概略図。 本発明の１実施形態によるスパースパリティチェックマトリックスの概略図。 図４のマトリックスのＬＤＰＣコードの２部グラフの概略図。 サブマトリックスが下方三角領域に制限されたパリティチェック値を含んでいる、本発明の１実施形態によるスパースパリティチェックマトリックスのサブマトリックスの概略図。 制限されていないパリティチェックマトリックス（Ｈマトリックス）を使用したコードと図６に示されているようなサブマトリックスを有する制限されたＨマトリックスを使用したコードとの間のパフォーマンスを示すグラフ。 図１のシステムにおいて使用されることのできる非グレー８−ＰＳＫ変調方式の概略図。 図１のシステムにおいて使用されることのできるグレー８−ＰＳＫ変調方式の概略図。 グレーラベル付けを使用したコードと非グレーラベル付けを使用したコードとの間のパフォーマンスを示すグラフ。 本発明の１実施形態による非グレーマッピングを使用するＬＤＰＣデコーダの動作のフローチャート。 本発明の１実施形態によるグレーマッピングを使用する図３のＬＤＰＣデコーダの動作のフローチャート。 本発明の１実施形態による復号プロセスにおけるチェックノードとビットノードとの間の相互作用の概略図。 順方向・逆方向アプローチおよび並列アプローチをそれぞれ使用してチェックノードとビットノードとの間の出ていくメッセージを計算する本発明の種々の実施形態によるプロセスのフローチャート。 本発明の種々の実施形態にしたがって発生されたＬＤＰＣコードのシミュレーション結果を示すグラフ。 本発明の種々の実施形態にしたがって発生されたＬＤＰＣコードのシミュレーション結果を示すグラフ。 本発明の種々の実施形態にしたがって発生されたＬＤＰＣコードのシミュレーション結果を示すグラフ。 ＬＤＰＣコード化のときにランダム化を達成するように構成されたアクセスをサポートするように編成されたメモリの上方エッジの概略図。 ＬＤＰＣコード化のときにランダム化を達成するように構成されたアクセスをサポートするように編成されたメモリの下方エッジの概略図。 本発明の実施形態にしたがってＬＤＰＣコードを符号化し、復号するプロセスを行うことのできるコンピュータシステムの概略図。

Claims (33)

1. 低密度パリティチェック（ＬＤＰＣ）コードの構成されたパリティチェックマトリックスを表す情報を記憶したメモリにアクセスし、その情報は表形式で編成され、各行はパリティチェックマトリックスの列のグループの第１の列内における１の値の発生を表し、行はパリティチェックマトリックスの列のグループに対応し、各グループ内の後続する列は予め定められた演算にしたがって導出され、
   パリティチェックマトリックスを表す記憶された情報に基づいてＬＤＰＣコード化された信号を出力するステップを含んでいる符号化方法。
2. 予め定められた演算は、
   各グループの第１の列に関して循環シフトを行い、
   ＬＤＰＣコードのコードレートに依存するある定数を各グループの第１の列に加算するステップの１つを特定する請求項１記載の方法。
3. パリティビットは順次決定され、
   パリティチェックマトリックスのｉ番目の行の中のｊ番目のエントリが１である場合に、（ｉ−１）番目のパリティビットおよびｊ番目の情報ビットを追加することによりｉ番目のパリティビットを決定するステップをさらに含んでいる請求項１記載の方法。
4. パリティビット累算装置をゼロに初期化し、
   パリティチェックマトリックスの（ｊＭ）番目の列の中のｉ番目のエントリが１である場合、ｉ番目のパリティビット累算装置の中のＭの情報ビットのｊ番目のグループの中の第１の情報ビットを累算し、ここでｊ＝０，１，２，３，…ｋ_ldpc／Ｍ−１であり、
   パリティビット累算装置の中のｊ番目のグループの残りの（Ｍ−１）の情報ビットｍ＝ｊＭ＋１，ｊＭ＋２，ｊＭ＋３，…，（ｊ＋１）Ｍ−１を｛ｘ＋ｍ ｍｏｄ Ｍ×ｑ｝ｍｏｄ（ｎ_ldpc−ｋ_ldpc）にしたがって累算し、ｘはそのグループの中の第１のビットｊＭに対応したパリティビット累算装置のアドレスを示し、ｑはコードレート依存定数であり、
   全ての情報ビットが使い尽くされた後、
   

   

   にしたがって演算をｉ＝１からスタートして行うステップをさらに含んでおり、ｐ_i，ｉ＝０，１，…，ｎ_ldpc−ｋ_ldpc−１の最終的な内容はパリティビットｐ_iに等しい請求項１記載の方法。
5. Ｍ＝３６０である請求項４記載の方法。
6. コード依存定数ｑは、コードレート２／３，５／６，１／２，３／４，４／５，３／５，８／９および９／１０に対してそれぞれ６０，３０，９０，４５，３６，７２，２０および１８である請求項４記載の方法。
7. ８−ＰＳＫ（位相シフトキーイング）、１６−ＱＡＭ（直交振幅変調）、ＱＰＳＫ（直交位相シフトキーイング）、１６−ＡＰＳＫ（振幅位相シフトキーイング）および３２−ＡＰＳＫの１つを含む信号コンステレーションにしたがってＬＤＰＣコード化された信号を変調するステップをさらに含んでいる請求項１記載の方法。
8. Ｂｏｓｅ Ｃｈａｕｄｈｕｒｉ Ｈｏｃｑｕｅｎｇｈｅｍ（ＢＣＨ）コードにしたがって入力信号を符号化するステップをさらに含んでおり、入力信号に対応した出力ＬＤＰＣコード化された信号は、外部ＢＣＨコードおよび内部ＬＤＰＣコードを有するコードを表している請求項１記載の方法。
9. 冗長ＢＣＨビットの数はｎ_BCH−ｋ_BCH＝１６＊ｔであり、ここでｔはＢＣＨコードのエラー補正能力を表している請求項８記載の方法。
10. ＢＣＨコードのエラー補正能力は、レート１／２、３／４、４／５、３／５のＬＤＰＣコードと連結して使用されたときには１２ビットであり、レート２／３および５／６のＬＤＰＣコードと連結して使用されたときには１０ビットであり、レート８／９および９／１０のＬＤＰＣコードと連結して使用されたときには８ビットである請求項８記載の方法。
11. パリティチェックマトリックスの列インデックスｊ＊３６０（ｊ＝０，１，２，３，…，ｋ_ldpc／３６０−１）中の１の行インデックスは、以下の表Ａ乃至Ｈの１つにしたがってｊ番目の行において与えられる：
    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    請求項１記載の方法。
12. パリティチェックマトリックスのその他の列インデックスｍ（ｍモジュロ３６０≠０およびｍ＜ｋ_ldpc）中の１の行インデックスは｛ｘ＋ｍ ｍｏｄ３６０×ｑ｝ｍｏｄ（ｎ_ldpc−ｋ_ldpc）によって与えられ、ここでレート２／３のＬＤＰＣコードに対してはｑ＝６０であり、レート５／６のＬＤＰＣコードに対してはｑ＝３０であり、レート１／２のＬＤＰＣコードに対してはｑ＝９０であり、レート３／４のＬＤＰＣコードに対してはｑ＝４５であり、レート４／５のＬＤＰＣコードに対してはｑ＝３６であり、レート３／５のＬＤＰＣコードに対してはｑ＝７２であり、レート８／９のＬＤＰＣコードに対してはｑ＝２０であり、レート９／１０のＬＤＰＣコードに対してはｑ＝１８であり、ｘは表Ａ乃至Ｇのｊ番目の行におけるエントリを示し、ここでｊ＝ｉｎｔ｛ｍ／３６０｝であり、ｉｎｔ｛．｝は整数関数を示し、列インデックスｍ＝ｋ_ldpc＋ｊ（ｊ＝０，１，２，…，ｎ_ldpc−ｋ_ldpc−２）中の１の行インデックスはｊおよびｊ＋１によって与えられ、パリティチェックマトリックスの列インデックスｎ_ldpc−１中の１の行インデックスはｎ_ldpc−ｋ_ldpc−１によって与えられる請求項１１記載の方法。
13. 符号化命令が実行されたときに、それが１以上のプロセッサに請求項１記載の方法を行わせるように構成されている命令を有しているコンピュータ読出し可能な媒体。
14. 低密度パリティチェック（ＬＤＰＣ）コードの構成されたパリティチェックマトリックスを表す情報を記憶したメモリ(1605,1607)を備えており、その情報は表形式で編成され、各行はパリティチェックマトリックスの列のグループの第１の列内における１の値の発生を表し、行はパリティチェックマトリックスの列のグループに対応し、各グループ内の後続する列は予め定められた演算にしたがって導出され、
    ＬＤＰＣコード化された信号を出力するためにパリティチェックマトリックスを表す記憶された情報を検索する手段を備えているＬＤＰＣコードを生成するエンコーダ。
15. 予め定められた演算は、各グループの第１の列に関する循環シフトおよび各グループの第１の列へのある定数の加算の１つを特定し、定数はＬＤＰＣコードのコードレートに依存している請求項１４記載のエンコーダ。
16. ｉ番目のパリティビットは、パリティチェックマトリックスのｉ番目の行の中のｊ番目のエントリが１である場合、（ｉ−１）番目のパリティビットおよびｊ番目の情報ビットを追加することにより決定される請求項１４記載のエンコーダ。
17. パリティビット累算装置はゼロに初期化され、Ｍの情報ビットのｊ番目のグループの中の第１の情報ビットは、パリティチェックマトリックスの（ｊＭ）番目の列の中のｉ番目のエントリが１である場合に累算され、ここでｊ＝０，１，２，３，…ｋ_ldpc／Ｍ−１であり、ｊ番目のグループの残りの（Ｍ−１）の情報ビットｍ＝ｊＭ＋１，ｊＭ＋２，ｊＭ＋３，…，（ｊ＋１）Ｍ−１は、パリティチェック累算装置において｛ｘ＋ｍ ｍｏｄ Ｍ×ｑ｝ｍｏｄ（ｎ_ldpc−ｋ_ldpc）にしたがって累算され、ｘはそのグループの中の第１のビットｊＭに対応したパリティビット累算装置のアドレスを示し、ｑはコードレート依存定数であり、全ての情報ビットが使い尽くされた後、ｉ＝１からスタートする演算が
    

    

    にしたがって行われ、ｐ_i，ｉ＝０，１，…，ｎ_ldpc−ｋ_ldpc−１の最終的な内容はパリティビットｐ_iに等しい請求項１４記載のエンコーダ。
18. Ｍ＝３６０である請求項１７記載のエンコーダ。
19. コード依存定数ｑは、コードレート２／３，５／６，１／２，３／４，４／５，３／５，８／９および９／１０に対してそれぞれ６０，３０，９０，４５，３６，７２，２０および１８である請求項１４記載のエンコーダ。
20. ＬＤＰＣコード化された信号は、８−ＰＳＫ（位相シフトキーイング）、１６−ＱＡＭ（直交振幅変調）、ＱＰＳＫ（直交位相シフトキーイング）、１６−ＡＰＳＫ（振幅位相シフトキーイング）および３２−ＡＰＳＫの１つを含む信号コンステレーションにしたがって変調される請求項１１記載のエンコーダ。
21. さらに、Ｂｏｓｅ Ｃｈａｕｄｈｕｒｉ Ｈｏｃｑｕｅｎｇｈｅｍ（ＢＣＨ）コードにしたがって入力信号を符号化するように構成されたＢＣＨエンコーダを備えており、入力信号に対応した出力ＬＤＰＣコード化された信号は、外部ＢＣＨコードおよび内部ＬＤＰＣコードを有するコードを表している請求項１４記載のエンコーダ。
22. 冗長ＢＣＨビットの数はｎ_BCH−ｋ_BCH＝１６＊ｔであり、ここでｔはＢＣＨコードのエラー補正能力を表している請求項２１記載のエンコーダ。
23. ＢＣＨコードのエラー補正能力は、レート１／２、３／４、４／５、３／５のＬＤＰＣコードと連結して使用されたときには１２ビットであり、レート２／３および５／６のＬＤＰＣコードと連結して使用されたときには１０ビットであり、レート８／９および９／１０のＬＤＰＣコードと連結して使用されたときには８ビットである請求項２１記載のエンコーダ。
24. 低密度パリティチェック（ＬＤＰＣ）コードの構成されたパリティチェックマトリックスを表す情報を記憶したメモリ(1605,1607)を備えており、その情報は表形式で編成され、各行はパリティチェックマトリックスの列のグループの第１の列内における１の値の発生を表し、行はパリティチェックマトリックスの列のグループに対応し、各グループ内の後続する列は予め定められた演算にしたがって導出され、
    メモリ(1605,1607)中に記憶された情報にアクセスしてＬＤＰＣコード化された信号を出力するように構成されたＬＤＰＣエンコーダ(203)を備えているＬＤＰＣコード化を使用する送信機。
25. 予め定められた演算は、各グループの第１の列に関する循環シフトおよび各グループの第１の列へのある定数の加算の１つを特定し、定数はＬＤＰＣコードのコードレートに依存している請求項２４記載の送信機。
26. ｉ番目のパリティビットは、パリティチェックマトリックスのｉ番目の行の中のｊ番目のエントリが１である場合、（ｉ−１）番目のパリティビットおよびｊ番目の情報ビットを追加することにより決定される請求項２４記載の送信機。
27. パリティビット累算装置はゼロに初期化され、Ｍの情報ビットのｊ番目のグループの中の第１の情報ビットは、パリティチェックマトリックスの（ｊＭ）番目の列の中のｉ番目のエントリが１である場合に累算され、ここでｊ＝０，１，２，３，…ｋ_ldpc／Ｍ−１であり、ｊ番目のグループの残りの（Ｍ−１）の情報ビットｍ＝ｊＭ＋１，ｊＭ＋２，ｊＭ＋３，…，（ｊ＋１）Ｍ−１は、パリティチェック累算装置において｛ｘ＋ｍ ｍｏｄ Ｍ×ｑ｝ｍｏｄ（ｎ_ldpc−ｋ_ldpc）にしたがって累算され、ｘはそのグループの中の第１のビットｊＭに対応したパリティビット累算装置のアドレスを示し、ｑはコードレート依存定数であり、全ての情報ビットが使い尽くされた後、ｉ＝１からスタートする演算が
    

    

    にしたがって行われ、ｐ_i，ｉ＝０，１，…，ｎ_ldpc−ｋ_ldpc−１の最終的な内容はパリティビットｐ_iに等しい請求項２４記載の送信機。
28. Ｍ＝３６０である請求項２７記載の送信機。
29. コード依存定数ｑは、コードレート２／３，５／６，１／２，３／４，４／５，３／５，８／９および９／１０に対してそれぞれ６０，３０，９０，４５，３６，７２，２０および１８である請求項２４記載の送信機。
30. ＬＤＰＣコード化された信号は、８−ＰＳＫ（位相シフトキーイング）、１６−ＱＡＭ（直交振幅変調）、ＱＰＳＫ（直交位相シフトキーイング）、１６−ＡＰＳＫ（振幅位相シフトキーイング）および３２−ＡＰＳＫの１つを含む信号コンステレーションにしたがって変調される請求項２４記載の送信機。
31. さらに、Ｂｏｓｅ Ｃｈａｕｄｈｕｒｉ Ｈｏｃｑｕｅｎｇｈｅｍ（ＢＣＨ）コードにしたがって入力信号を符号化するように構成されたＢＣＨ送信機を備えており、入力信号に対応した出力ＬＤＰＣコード化された信号は、外部ＢＣＨコードおよび内部ＬＤＰＣコードを有するコードを表している請求項２４記載の送信機。
32. 冗長ＢＣＨビットの数はｎ_BCH−ｋ_BCH＝１６＊ｔであり、ここでｔはＢＣＨコードのエラー補正能力を表している請求項３１記載の送信機。
33. ＢＣＨコードのエラー補正能力は、レート１／２、３／４、４／５、３／５のＬＤＰＣコードと連結して使用されたときには１２ビットであり、レート２／３および５／６のＬＤＰＣコードと連結して使用されたときには１０ビットであり、レート８／９および９／１０のＬＤＰＣコードと連結して使用されたときには８ビットである請求項３１記載の送信機。

Images