(57)【要約】低密度パリティチェック（ＬＤＰＣ）コード化された信号を復号するためのアプローチが提供される。ＬＤＰＣコード化された信号を生成するために使用された構成されたパリティチェックマトリックスに関連付けられたエッジ値はメモリ1501,1503から検索される。エッジ値は、ビットノードとチェックノードとの関係を特定し、エッジ値のセットの並行検索を可能にする予め定められた方式にしたがってメモリ内に記憶される。ＬＤＰＣコード化された信号に対応する復号された信号は検索されたエッジ値に基づいて出力される。
2005520467.tif 000002
【特許請求の範囲】
【請求項１】
低密度パリティチェック（ＬＤＰＣ）コード化された信号を生成するために使用された構成されたパリティチェックマトリックスに関連付けられたエッジ値を検索し、エッジ値はビットノードとチェックノードとの関係を特定し、エッジ値のセットの同時検索を可能にする予め定められた方式にしたがってメモリ内に記憶され、
検索されたエッジ値に基づいてＬＤＰＣコード化された信号に対応した復号された信号を出力するステップを含んでいるＬＤＰＣコード化された信号の復号方法。
【請求項２】
エッジ値は検索するステップにおいて予め定められた方式にしたがってメモリ(1501,1503)中に記憶され、予め定められた方式はそのエッジ値のセットに対する隣接した物理的メモリ位置を特定する請求項１記載の方法。
【請求項３】
メモリ(1501,1503)は、ビットノードの度数にしたがって区分されている請求項２記載の方法。
【請求項４】
ｎ度のビットノードを有するエッジ値はメモリ(1501,1503)の第１の部分に記憶され、ｎより大きい度数のビットノードを有するエッジ値はメモリ(1501,1503)の第２の部分に記憶される請求項３記載の方法。
【請求項５】
メモリ(1501,1503)のアドレスは、読出し専用メモリ（ＲＯＭ）中に記憶されている請求項２記載の方法。
【請求項６】
エッジ値のセットは、メモリ(1501,1503)に接続されたプロセッサの単一のクロックサイクルで検索され、ＭのビットノードまたはＭのチェックノードのグループに隣接しており、ここでＭは並列処理エンジンの数である請求項２記載の方法。
【請求項７】
エッジの隣接した配置は、パリティチェックマトリックスに制限を与える請求項２記載の方法。
【請求項８】
ＬＤＰＣコード化された信号は、８−ＰＳＫ（位相シフトキーイング）、１６−ＱＡＭ（直交振幅変調）、１６−ＡＰＳＫ（振幅位相シフトキーイング）、３２−ＡＰＳＫおよびＱＰＳＫ（直交位相シフトキーイング）の１つを含む信号コンステレーションにしたがって変調される請求項１記載の方法。
【請求項９】
検索するステップにおけるエッジ値のセットは、固定されたサイズのものである請求項１記載の方法。
【請求項１０】
低密度パリティチェック（ＬＤＰＣ）コード化された信号を復号する命令が実行されたときに、それが１以上のプロセッサに請求項１記載の方法を行わせるように構成されている命令を有しているコンピュータ読出し可能な媒体。
【請求項１１】
低密度パリティチェック（ＬＤＰＣ）コード化された信号を生成するために使用された構成されたパリティチェックマトリックスに関連付けられたエッジ値を検索する手段と、
ビットノードとチェックノードとの関係を特定するエッジ値のセットの同時検索を可能にする予め定められた方式にしたがってエッジ値を記憶するメモリ(1501,1503)と、
検索されたエッジ値に基づいてＬＤＰＣコード化された信号に対応した復号された信号を出力する手段とを備えているＬＤＰＣコード化された信号を復号するデコーダ。
【請求項１２】
予め定められた方式はそのエッジ値のセットに対する隣接した物理的メモリ位置を特定する請求項１１記載のデコーダ。
【請求項１３】
メモリ(1501,1503)は、ビットノードの度数にしたがって区分されている請求項１１記載のデコーダ。
【請求項１４】
ｎ度のビットノードに接続されたエッジ値はメモリ(1501,1503)の第１の部分に記憶され、ｎより大きい度数のビットノードに接続されたエッジ値はメモリ(1501,1503)の第２の部分に記憶される請求項１１記載のデコーダ。
【請求項１５】
構成されたパリティチェックマトリックスは、パリティチェックマトリックスのサブマトリックスに制限を与える請求項１１記載のデコーダ。
【請求項１６】
ＬＤＰＣコード化された信号は、８−ＰＳＫ（位相シフトキーイング）、１６−ＱＡＭ（直交振幅変調）、１６−ＡＰＳＫ（振幅位相シフトキーイング）、３２−ＡＰＳＫおよびＱＰＳＫ（直交位相シフトキーイング）の１つを含む信号コンステレーションにしたがって変調される請求項１１記載のデコーダ。
【請求項１７】
さらに、メモリ(1501,1503)のアドレスを記憶する読出し専用メモリを備えている請求項１１記載のデコーダ。
【請求項１８】
さらに、メモリ(1501,1503)に接続されたプロセッサを備えており、エッジ値のセットはこのプロセッサの単一のクロックサイクルで検索され、ＭのビットノードまたはＭのチェックノードのグループに隣接しており、ここでＭは並列処理エンジンの数である請求項１１記載のデコーダ。
【請求項１９】
ｎ度のビットノードに接続されており、ＬＤＰＣコード化された信号を生成するために使用された構成されたパリティチェックマトリックスに関連付けられたエッジ値の第１のグループを記憶する第１の部分と、
ｎより大きい度数のビットノードに接続されており、（ＬＤＰＣ）コード化された信号を生成するために使用された構成されたパリティチェックマトリックスに関連付けられたエッジ値の第２のグループを記憶する第２の部分とを備えており、
復号された信号を出力するために第１のグループまたは第２のグループからのエッジ値のセットが検索されるＬＤＰＣコード化された信号を復号するＬＤＰＣデコーダによりアクセス可能なメモリ。
【請求項２０】
予め定められた方式は隣接した物理的メモリ位置を特定する請求項１９記載のメモリ。
【請求項２１】
エッジの隣接した配置は、パリティチェックマトリックスに制限を与える請求項２０記載のメモリ。
【請求項２２】
ＬＤＰＣコード化された信号は、８−ＰＳＫ（位相シフトキーイング）、１６−ＱＡＭ（直交振幅変調）、１６−ＡＰＳＫ（振幅位相シフトキーイング）、３２−ＡＰＳＫおよびＱＰＳＫ（直交位相シフトキーイング）の１つを含む信号コンステレーションにしたがって変調される請求項１９記載のメモリ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は通信システムに関し、とくに、コード化されたシステムに関する。
【背景技術】
【０００２】
本出願は以下の暫定的な特許出願明細書に関連しており、３５  Ｕ．Ｓ．Ｃ§１１９（ｅ）の下にそれらの権利を有している：米国特許出願第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からの送信は、以下に説明するように受信機に伝播する。
【００２１】
図３は、図１のシステム内の例示的な受信機の概略図である。受信側において、受信機300は、送信機200から受信された信号の復調を行う復調装置301を備えている。これらの信号は、復調のために受信アンテナ303で受信される。受信された信号は復調後にデコーダ305に転送され、このデコーダ305はビット計量発生装置307と協力してメッセージＸ’を発生することにより元のソースメッセージの再構成を試みる。非グレーマッピングに関して、ビット計量発生装置307は復号プロセス中にデコーダ305と確率情報を前後に（反復的に）交換する。これは図１０に詳細に示されている。その代りに、グレーマッピングが使用された（本発明の１実施形態にしたがって）場合、ビット計量発生装置307の１つのパスで十分であり、このとき各ＬＤＰＣデコーダ反復の後におけるビット計量発生の別の試みにより、限られたパフォーマンス改良が得られる可能性が高い。このアプローチは、図１１に関してさらに詳細に説明される。本発明によって提供される利点を認識するために、図４において説明されるように、ＬＤＰＣコードがどのようにして発生されるかを示すことが有益である。
【００２２】
図４は、本発明の１実施形態によるスパースパリティチェックマトリックスの概略図である。ＬＤＰＣコードは、スパースパリティチェックマトリックスＨ(n-k)xnを有する長い線形ブロックコードである。典型的に、ブロック長ｎの範囲は何千乃至何万のビットである。図４には、たとえば、長さｎ＝８およびレート１／２のＬＤＰＣコードに対するパリティチェックマトリックスが示されている。同じコードは図５における２部分グラフにより等価に表されることができる。
【００２３】
図５は、図４のマトリックスのＬＤＰＣコードの２部分グラフの概略図である。パリティチェック方程式は、各チェックノードに対して、全ての隣接したビットノードの和（ＧＦ（ガロア域）（２）にわたる）がゼロに等しいことを示すものである。図面に示されているように、ビットノードはグラフの左側を占め、予め定められた関係にしたがって１以上のチェックノードと関連している。たとえば、チェックノードｍ1に対応して、式：ｎ1＋ｎ4＋ｎ5＋ｎ8＝０がビットノードに関して存在する。
【００２４】
受信機303に戻ると、ＬＤＰＣデコーダ305はメッセージパッシングデコーダとみなされ、それによってデコーダ305はビットノードの値を見出すことをめざしている。このタスクを行うために、ビットノードおよびチェックノードは互いに反復的に通信する。以下、この通信の特性を以下説明する。
【００２５】
チェックノードからビットノードへは、各チェックノードは隣接したビットノードに別の隣接したビットノードからの情報に基づいてそのビットノードの値に関する推定値（“オピニオン”）を提供する。たとえば、上記の例において、ｎ4，ｎ5およびｎ8の和がｍ1に０“のように見えた”場合、ｍ1は、ｎ1の値が０であると考えられる（ｎ1＋ｎ4＋ｎ5＋ｎ8＝０であるため）ことをｎ1に示す；その他の場合には、ｍ1は、ｎ1の値が１であると考えられることをｎ1に示す。さらに、ソフト決定復号のために、信頼性尺度が追加される。
【００２６】
ビットノードからチェックノードへは、各ビットノードは隣接したチェックノードに対してそれの別の隣接したチェックノードからのフィードバックに基づいてそれ自身の値に関する推定値を中継する。上記の例において、ｎ1は２つの隣接したチェックノードｍ1およびｍ3だけを有している。ｍ3からｍ1へのフィードバックがｎ1の値がおそらく０であることを示した場合、ｎ1はｎ1自身の値の推定値が０であることをｍ1に知らせる。ビットノードが３以上の隣接したチェックノードを有している場合に対しては、ビットノードは、それが通信するチェックノードにその決定を報告する前に、それの別の隣接したチェックノードからのフィードバックに関する多数決投票（ｍａｊｏｒｉｔｙ  ｖｏｔｅ）（ソフト決定）を行う。上記のプロセスは、全てのビットノードが正しいとみなされる（すなわち、全てのパリティチェック方程式が満足される）まで、あるいは予め定められた最大反復数に達し、それによって復号の失敗が宣言されるまで繰返される。
【００２７】
図６は、サブマトリックスが下方三角領域に制限されたパリティチェック値を含んでいる、本発明の１実施形態によるスパースパリティチェックマトリックスのサブマトリックスの概略図である。上述されたように、エンコーダ203（図２の）は、パリティチェックマトリックスの下方の三角領域に値を制限することにより単純な符号化技術を使用することができる。本発明の１実施形態によると、パリティチェックマトリックスに課せられる制限は、
Ｈ(n-k)xn＝［Ａ(n-k)xkＢ(n-k)x(n-k)］
の形式のものであり、ここで、Ｂは下方の三角である。
【００２８】
任意の情報ブロックｉ＝（ｉ0，ｉ1，…，ｉk-1）は、ＨｃT＝０を使用して、パリティビットについて反復的に解くことによりコードワードｃ＝（ｉ0，ｉ1，…，ｉk-1，ｐ0，ｐ1，…ｐn-k-1）に符号化される。たとえば、
【数１】
2005520467.tif 000003
【００２９】
ｐ2，ｐ3，…，ｐn-k-1に対しても同様である。
【００３０】
図７は、制限されていないパリティチェックマトリックス（Ｈマトリックス）を使用したコードと図６の制限されたＨマトリックスを使用したコードとの間のパフォーマンスを示すグラフである。このグラフは、一方が一般的なパリティチェックマトリックスによるものであり、他方が符号化を簡単化するために下方の三角に制限されたパリティチェックマトリックスによるものである２つのＬＤＰＣコードの間のパフォーマンス比較を示している。変調方式は、このシミュレーションにおいて８−ＰＳＫである。パフォーマンス損失は０．１ｄＢ以内である。したがって、パフォーマンス損失は下方の三角Ｈマトリックスの制限に基づいて無視できる程小さく、一方符号化技術の簡単化による利得は大きい。したがって、行および、または列置換（ｐｅｒｍｕｔａｔｉｏｎ）状態において下方の三角または上方の三角に等価であるパリティチェックマトリックスが同じ目的のために使用されることができる。
【００３１】
図８Ａおよび８Ｂはそれぞれ、図１のシステムにおいてそれぞれ使用されることのできる非グレー８−ＰＳＫ変調方式およびグレー８−ＰＳＫ変調方式の概略図である。図８Ａの非グレー８−ＰＳＫ方式は図３の受信機において使用され、非常に低いフレーム消去レート（ＦＥＲ）を必要とするシステムを提供することができる。この要求はまた、Ｂｏｓｅ，Ｃｈａｕｄｈｕｒｉ，およびＨｏｃｑｕｅｎｇｈｅｍ（ＢＣＨ）、ハミング、またはリード・ソロモン（ＲＳ）コードのような外部コードと共同して図８Ｂに示されているグレー８−ＰＳＫ方式を使用することにより満足されることができる。
【００３２】
この方式の下では、８−ＰＳＫ変調を使用することのできるＬＤＰＣデコーダ305（図３）とビット計量発生装置307との間で繰返しを行う必要はない。外部コードが存在しないとき、グレーラベル付けを使用するＬＤＰＣデコーダ305は、以下において図９で示されるように早期のフロアエラーを示す。
【００３３】
図９は、図８Ａのグレーラベル付けを使用したコードと図８Ｂの非グレーラベル付けを使用したコードとの間のパフォーマンスを示すグラフである。エラーフロアは、ＬＤＰＣデコーダ305からの正しいフィードバックを仮定すると、既知の２ビットによる２つの８−ＰＳＫシンボルは非グレーラベル付けによるほうがいっそう遠くに離れているため、非グレーラベル付けによる８−ＰＳＫビット計量の再生のほうが正確であることに由来する。これは同様に、高い信号対雑音比（ＳＮＲ）での動作として見られる。したがって、グレーまたは非グレーラベル付けを使用した同じＬＤＰＣコードのエラー漸近線が同じ傾斜を有していても（すなわち、互いに平行であっても）、非グレーラベル付けによるものは任意のＳＮＲで低いＦＥＲを通過する。
【００３４】
他方において、それ程低いＦＥＲを必要としないシステムに対しては、ＬＤＰＣデコーダ305と８−ＰＳＫビット計量発生装置307との間の反復を伴なわないグレーラベル付けのほうが適切かもしれない。これは、全ての各ＬＤＰＣデコーダ反復の前に８−ＰＳＫビット計量を再生することにより、追加の複雑さが生じるためである。さらに、グレーラル付けが使用されたとき、全ての各ＬＤＰＣデコーダ反復の前に８−ＰＳＫビット計量を再生しても、ごくわずかなパフォーマンス改善しか得られない。上述したように、反復を伴なわないグレーラベル付けは、外部コードが構成される場合、非常に低いＦＥＲを必要とするシステムに対して使用されることができる。
【００３５】
グレーラベル付けと非グレーラベル付けとの間の選択はまた、ＬＤＰＣコードの特性にも依存する。典型的に、ビットまたはチェックノード度が高くなると、それだけいっそうグレーラベル付けが適切になる。これは、高いノード度に関しては、非グレーラベル付けによるほうが、ＬＤＰＣデコーダ305から８−ＰＳＫ（または類似の高次の変調）ビット計量発生装置307への最初のフィードバックが低下するためである。
【００３６】
８−ＰＳＫ（または類似の高次の）変調が２進デコーダにより使用されたとき、シンボルの３（以上の）ビットは“等しい雑音で”受取られないことが認識される。たとえば、グレー８−ＰＳＫラベル付けに関して、あるシンボルの第３のビットはデコーダに対する雑音が他の２ビットより多いと考えられる。したがって、ＬＤＰＣコード設計では、８−ＰＳＫシンボルの“雑音が多い”第３のビットにより表されるこれらのビットノードは、これらのビットが２度とペナルティーを科せられないように、少数のエッジを割当てられない。
【００３７】
図１０は、本発明の１実施形態による非グレーマッピングを使用するＬＤＰＣデコーダの動作のフローチャートである。このアプローチの下では、ＬＤＰＣデコーダおよびビット計量発生装置は、次々に反復する。この例においては、８−ＰＳＫ変調が使用されている。しかしながら、同じ原理は他の高次変調方式にも適用される。このシナリオにおいて、復調装置301は、受取られた雑音の多いシンボル地点と８−ＰＳＫシンボル地点との間の距離を表す距離ベクトルｄをビット計量発生装置307に出力することを仮定すると、ベクトルコンポーネントは次のようになる：
【数２】
2005520467.tif 000004
【００３８】
８−ＰＳＫビット計量発生装置307は、ｕおよびａとしてそれぞれ表される演繹的確率情報および経験的確率情報を交換するためにＬＤＰＣデコーダ305と通信する。すなわち、ベクトルはｕおよびａはそれぞれコードビットの対数尤度比の演繹的確率情報および経験的確率情報を表す。
【００３９】
８−ＰＳＫビット計量発生装置307は、次のように３ビットの各グループに対する演繹的尤度比を生成する。最初に、コード化されたビットに関する非本質的情報が得られる：
ｅｊ＝ａｊ−ｕｊ      ｊ＝０，１，２
次に、８−ＰＳＫシンボル確率：ｐi      （ｉ＝０，１，…，７）が決定される。
【数３】
2005520467.tif 000005
【００４０】
次に、ビット計量発生装置307は以下のように、ＬＤＰＣデコーダ305への入力としてコード化されたビットの演繹的対数尤度比を決定する：
【数４】
2005520467.tif 000006
【００４１】
３以上の変数を有する関数ｆ（．）は、たとえば、ｆ（ａ，ｂ，ｃ）＝ｆ（ｆ（ａ，ｂ），ｃ）のように反復的に推定されることが可能なことが認識される。
【００４２】
以下、非グレーマッピングを使用するＬＤＰＣデコーダ305の動作を説明する。ステップ1001において、ＬＤＰＣデコーダ305は以下にしたがった（および図１２Ａに示されているように）最初の反復の前に、コード化されたビットｖの対数尤度比を初期化する：
【数５】
2005520467.tif 000007
【００４３】
ステップ1003において、チェックノードｋが更新され、それによって入力ｖにより出力ｗが得られる。図１２Ｂに見られるように、チェックノードｋに対してそのｄcの隣接ビットノードから入ってきたメッセージは、
【数６】
2005520467.tif 000008
【００４４】
によって示される。目的は、ｄcの隣接ビットノードに戻ってチェックノードｋから出ていくメッセージを計算することである。これらのメッセージは、次のように示される：
【数７】
2005520467.tif 000009
【００４５】
この関数ｇ（）は以下のように規定される：
【数８】
2005520467.tif 000010
【００４６】
関数ｆに類似して、３以上の変数を有する関数ｇは、反復的に推定されることができる。
【００４７】
次に、ステップ1005において、デコーダ305は、以下の関係が成立するように経験的確率情報を出力する（図１２のＣ）：
【数９】
2005520467.tif 000011
【００４８】
ステップ1007において、全てのパリティチェック式が満足されたか否かが決定される。これらのパリティチェック式が満足されていない場合、デコーダ305はステップ1011に示されているように、８−ＰＳＫビット計量およびチャンネル入力ｕnを再度求める。次に、ビットノードはステップ1013に示されているように更新される。図１４Ｃに示されているように、ビットノードｎに対してそれのｄvの隣接チェックノードから入ってきたメッセージは、
【数１０】
2005520467.tif 000012
【００４９】
によって示される。ビットノードｎから出ていくメッセージはｄvの隣接ビットノードに戻って計算される；このようなメッセージは、
【数１１】
2005520467.tif 000013
【００５０】
によって示され、次のように計算される：
【数１２】
2005520467.tif 000014
【００５１】
ステップ1013において、デコーダ305はハード決定を出力する（全てのパリティチェック式が満足される場合に）：
【数１３】
2005520467.tif 000015
【００５２】
上記のアプローチは、非グレーラベル付けが使用されたときに適切である。しかしながら、グレーラベル付けが実施されたとき、図１１のプロセスが実行される。
【００５３】
図１１は、本発明の１実施形態によるグレーマッピングを使用する図３のＬＤＰＣデコーダの動作のフローチャートである。グレーラベル付けが使用されたとき、全ての各ＬＤＰＣデコーダ反復の後にビット計量を再生することにより公称パフォーマンス改善が得られる可能性があるため、ビット計量は都合よくＬＤＰＣデコーダの前に一度だけ生成されることが有効である。図１０のステップ1001および1003に関するように、ステップ1101においてコードビッドｖの対数尤度比の初期化が行われ、ステップ1103においてチェックノードが更新される。次にステップ1105に示されているように、ビットノードｎが更新される。その後、デコーダは経験的確率情報を出力する（ステップ1107）。ステップ1109において、全てのパリティチェック式が満足されているか否かが決定される：そうであるならば、デコーダはハード決定を出力する（ステップ1111）。そうでない場合には、ステップ1103-1107が繰返される。
【００５４】
図１３のＡは、順方向・逆方向アプローチを使用してチェックノードとビットノードとの間の出ていくメッセージを計算する本発明の１実施形態によるプロセスのフローチャートである。ｄcの隣接エッジを有するチェックノードに対して、ｄc（ｄc−１）および多数のｇ（．，．）関数の計算が行われる。しかしながら、順方向・逆方向アプローチは計算の複雑さを３（ｄc−２）に軽減し、この場合ｄc−１の変数が記憶される。
【００５５】
図１２のＢに戻ると、チェックノードｋに対してそのｄcの隣接ビットノードから入ってきたメッセージは次のように示される：
【数１４】
2005520467.tif 000016
【００５６】
出ていくメッセージは、チェックノードｋからｄcの隣接ビットノードに戻って計算されることが望ましい；これらの出ていくメッセージは次のように示されている：
【数１５】
2005520467.tif 000017
【００５７】
出ていくメッセージの計算に対する順方向・逆方向アプローチの下では、順方向変数ｆ1，ｆ2，…，ｆdcは以下のように規定される：
【数１６】
2005520467.tif 000018
【００５８】
これらの順方向変数はステップ1301において計算され、ステップ1303で記憶される。
【００５９】
同様に、逆方向変数ｂ1，ｂ2，…，ｂdcは以下のように規定される：
【数１７】
2005520467.tif 000019
【００６０】
それから、これらの順方向変数はステップ1305において計算される。その後、ステップ1307において、記憶された順方向変数および計算された逆方向変数に基づいて出ていくメッセージが計算される。この出ていくメッセージは次のように計算される：
【数１８】
2005520467.tif 000020
【００６１】
このアプローチの下において、順方向変数ｆ2，ｆ3，…，ｆdcだけが記憶される必要がある。逆方向変数ｂiは計算されているので、出ていくメッセージ：
【数１９】
2005520467.tif 000021
【００６２】
は同時に計算され、それによって逆方向変数を記憶する必要性をなくする。
【００６３】
次に説明するように、計算負荷は並列アプローチによってさらに増強されることができる。
【００６４】
図１３のＢは、並列アプローチを使用してチェックノードとビットノードとの間の出ていくメッセージを計算する本発明の１実施形態によるプロセスのフローチャートである。ｄcの隣接ビットノードからの入力：
【数２０】
2005520467.tif 000022
【００６５】
を有するチェックノードｋに対して、ステップ1311に示されているように、以下のパラメータが計算される：
【数２１】
2005520467.tif 000023
【００６６】
ｇ（．，．）関数はまた、次のように表されることができることが認識される：
【数２２】
2005520467.tif 000024
【００６７】
ｇ（．，．）関数の反復特性を利用することにより、結果的に次式が得られる：
【数２３】
2005520467.tif 000025
【００６８】
したがって、
【数２４】
2005520467.tif 000026
【００６９】
は以下のように解かれることができる：
【数２５】
2005520467.tif 000027
【００７０】
上記の式のｌｎ（．）の項は、関数ｌｎ｜ｅx−１｜を表すルックアップテーブルＬＵＴxを使用して得られる（ステップ1313）。他のルックアップテーブルＬＵＴfまたはＬＵＴgとは異なり、このＬＵＴxはおそらく、量子化レベルの数と同じ数のエントリを必要とする。γkが得られると、ステップ1315に示されているように、全てのｎiに対する
【数２６】
2005520467.tif 000028
【００７１】
の計算は、上記の方程式を使用して並列に行われることができる。
【００７２】
γkの計算の待ち時間は、都合よく、ｌｏｇ2（ｄc）である。
【００７３】
図１４Ａ乃至図１４Ｃは、本発明の種々の実施形態にしたがって発生されたＬＤＰＣコードのシミュレーション結果を示すグラフである。とくに、図１４Ａ乃至図１４Ｃは、高次の変調と３／４（ＱＰＳＫ、１．４８５ビット／シンボル）、２／３（８−ＰＳＫ、１．９８０ビット／シンボル）、および５／６（８−ＰＳＫ、２．４７４ビット／シンボル）のコードレートを有するＬＤＰＣコードのパフォーマンスを示している。
【００７４】
チェックノードとビットノードとの間の相互接続を実現するための２つの一般的なアプローチ、すなわち：（１）完全並列アプローチ、および（２）部分的並列アプローチが存在する。完全並列アーキテクチャにおいて、ノードおよびそれらの相互接続の全てが物理的に構成される。このアーキテクチャの利点は速度である。
【００７５】
しかしながら、完全並列アーキテクチャは全てのノードおよびそれらの相互接続を行うときにかなりの複雑さを伴う可能性がある。したがって、完全並列アーキテクチャでは、複雑さを減少させるために小さいブロックサイズが必要とされる可能性がある。その場合には、結果的に、同じクロック周波数に対して、スループットが比例して減少すると共に、ＦＥＲ対Ｅｓ／Ｎｏパフォーマンスにおいて若干の低下が生じる可能性がある。
【００７６】
ＬＤＰＣコードの構成に対する第２のアプローチは、ノードの総数の部分集合だけを物理的に実現し、これらの限られた数の“物理的”ノードを使用して、そのコードの“機能的”ノードを全て処理することである。ＬＤＰＣデコーダの動作が非常に単純なものにされることが可能であり、並列に行われることが可能でも、設計における別の難題は、“ランダムに”分布されたビットノードとチェックノードとの間において通信がどのようにして設定されるかである。本発明の１実施形態によるデコーダ305（図３の）は見かけ上ランダムなコードを実現するようにある構成方式でメモリにアクセスすることによってこの問題を解決する。図１５Ａおよび図１５Ｂに関して、このアプローチを説明する。
【００７７】
図１５Ａおよび図１５Ｂはそれぞれ、ＬＤＰＣコード化のときにランダム化を達成するために構成されたアクセスをサポートするように編成された本発明の１実施形態によるメモリの上方エッジおよび下方エッジの概略図である。構成されたアクセスは、パリティチェックマトリックスの発生に集中することにより、真にランダムなコードのパフォーマンスに妥協せずに行われることができる。一般に、パリティチェックマトリックスは、チェックノードとビットノードとの接続により特定されることができる。たとえば、ビットノードは、例示のために３９２である固定されたサイズのグループに分割されることができる。さらに、度数３の第１のビットノードに接続されるチェックノードは、たとえば、ａ，ｂおよびｃの番号を付けられることを仮定すると、第２のビットノードに接続されるチェックノードはａ＋ｐ，ｂ＋ｐおよびｃ＋ｐの番号を付けられ、第３のビットノードに接続されるチェックノードはａ＋２ｐ，ｂ＋２ｐおよびｃ＋２ｐ等の番号を付けられ、ここでｐ＝（チェックノードの数）／３９２である。３９２ビットノードの次のグループに対しては、ｐの適切な選択により全てのチェックノードが同じ度数を有するように、第１のビットノードに接続されるチェックノードはａ，ｂ，ｃとは異なっている。結果的に得られるＬＤＰＣコードがサイクル４およびサイクル６フリーであるように、ランダムサーチが自由定数に対して行われる。本発明のパリティチェックマトリックスの構造上の特徴のために、エッジ情報は復号中に関連したエッジ値のグループへの並行アクセスを可能にするように記億されることができる。
【００７８】
換言すると、本発明のアプローチは、チェックノードおよびビットノード処理中のメモリアクセスを容易にする。２部分グラフにおけるエッジの値は、ランダムアクセスメモリ（ＲＡＭ）のような記憶媒体中に記憶されることができる。チェックノードおよびビットノードの処理中、真にランダムなＬＤＰＣコードに対してエッジの値はランダムな方式で１つづつアクセスされる必要があることが認識される。しかしながら、このような通常のアクセス方式は、高いデータレートのアプリケーションには遅過ぎる。図１５Ａおよび図１５ＢのＲＡＭは、関連したエッジの大きいグループが１クロックサイクルで取り出されることができる方式で編成されている；したがって、これらの値は予め定められた方式または配列にしたがってメモリ中に“一緒に”配置されている。実際には、真にランダムなコードでさえ、チェックノード（およびそれぞれにビットノード）のグループに対しては、関連エッジはＲＡＭ中に隣接して配置されることが可能であるが、しかしビットノード（それぞれにチェックノード）のグループに隣接した関連エッジはＲＡＭ中においてランダムに分散されることが認識される。したがって、本発明における“一緒”はパリティチェックマトリックス自身の設計に由来する。すなわち、このチェックマトリックス設計は、ビットノードとチェックノードのグループに対する関連エッジがＲＡＭ中に同時に一緒に配置されることを保証する。
【００７９】
図１５Ａおよび図１５Ｂに見られるように、各ボックスは、多くのビット（たとえば、６）であるエッジの値を含んでいる。本発明の１実施形態によるエッジＲＡＭは、上方エッジＲＡＭ1501(図１５Ａ)および下方エッジＲＡＭ1503(図１５Ｂ)の２つの部分に分割されている。下方エッジＲＡＭ1503は、たとえば、度数２のビットノードとチェックノードとの間のエッジを含んでいる。上方エッジＲＡＭ1501は、２より大きい度数のビットノードとチェックノードとの間のエッジを含んでいる。したがって、あらゆるチェックノードに対して、２つの隣接したエッジが下方エッジＲＡＭ1503中に記憶され、そのエッジの残りのものは上方エッジＲＡＭ1501中に記憶される。たとえば、種々のコードレートに対する上方エッジＲＡＭ1501および下方エッジＲＡＭ1503のサイズは表１に示されている：
【表１】
2005520467.tif 000029
【００８０】
この表１に基づいて、サイズが５７６×３９２のエッジＲＡＭは、１／２、２／３、３／４および５／６の全てのコードレートに対するエッジマトリックスを記憶するのに十分である。
【００８１】
認識されるように、この例示的なシナリオ下では、一度で処理するために３９２のビットノードと３９２のチェックノードのグループが選択される。３９２のチェックノード処理については、（ｑ＝ｄc−２）個の連続した行が上方エッジＲＡＭ1501からアクセスされ、２つの連続した行が下方エッジＲＡＭ1503からアクセスされる。ｄcの値は特定のコードに依存し、たとえば、上記のコードについてはレート１／２に対してｄc＝７、レート２／３に対してｄc＝１０、レート３／４に対してｄc＝１６、およびレート５／６に対してｄc＝２２である。当然ながら、別のコードに対するｄcの別の値が可能である。この例において、ｑ＋２は各チェックノードの度数である。
【００８２】
ビットノード処理について、３９２のビットノードのグループが度数２を有している場合、それらのエッジは下方エッジＲＡＭ1503の２つの連続した行中に配置される。ビットノードが度数ｄ＞２を有している場合、それらのエッジは上方エッジＲＡＭ1501のあるｄの行の中に配置される。これらのｄ行のアドレスは、読出し専用メモリ（ＲＯＭ）のような不揮発性メモリ中に記憶されることができる。その行の１つの中のエッジは３９２のビットノードの第１のエッジに対応し、別の行中のエッジは３９２のビットノードの第２のエッジに対応する等々である。さらに、各行に対して、３９２のグループ中の第１のビットノードに属するエッジの列インデックスもまたＲＯＭ中に記憶されることができる。第２、第３等の他のビットノードに対応したエッジは“ラップアラウンド”方式で開始時の列インデックスに続く。たとえば、行の中のｊ番目のエッジが第１のビットノードに属している場合、（ｊ＋１）番目のエッジは第２のビットノードに属し、（ｊ＋２）番目のエッジは第３のビットノードに属し、・・・、（ｊ−１）番目のエッジは第３９２のビットノードに属する。
【００８３】
表２乃至５において、上方エッジＲＡＭ1501の行インデックスおよび開始時の列インデックスが２／３、５／６、１／２および３／４の各コードレートについて度数３以上の３９２のビットノードの全ての各グループに対して特定される。表２乃至５の中の各行は、３９２のビットノードのある１つのグループを表している。第１の数は行インデックスを示し、第２の数は開始時の列インデックスを示している。たとえば表２では、第１の行は度数１３の３９２のビットノードの第１のグループに対する隣接したエッジのアドレスを完全に決定する。とくに、エントリ０／０は、３９２のビットノードの全てに対する第１の隣接したエッジが行番号０中に記憶されることを示している。さらにその行においては、０のインデックスを付けられた列は第１のビットノードの第１の隣接したエッジに対する情報を保持し、１のインデックスを付けられた列は第２のビットノードの第１の隣接したエッジに対する情報を保持する等々であり、最後に３９１のインデックスを付けられた列は第３９２のビットノードの第１の隣接したエッジに対する情報を保持している。
【００８４】
同様に、エントリ４３３／３２３は、３９２のビットノードの全てに対する第２の隣接したエッジが行番号４３３の中に記憶されることを特定する。さらにその行において、３２３のインデックスを付けられた列は第１のビットノードの第２の隣接したエッジに対する情報を保持し、３２４のインデックスを付けられた列は第２のビットノードの第２の隣接したエッジに対する情報を保持する等々である。３２２のインデックスを付けられた列は第３９２のビットノードの第２の隣接したエッジに対する情報を保持している。
【００８５】
同様に、表２の第１の行の中の別のエントリは、３９２のビットノードの第１のグループに対する残りの隣接したエッジのアドレスを決定する。同様に、表２の第２の行の中のエントリは、３９２のビットノードの第２のグループに対する残りの隣接したエッジのアドレスを決定する等々である。
【表２】
2005520467.tif 000030
【表３】
2005520467.tif 000031
【表４】
2005520467.tif 000032
【表５】
2005520467.tif 000033
【表６】
2005520467.tif 000034
【表７】
2005520467.tif 000035
【表８】
2005520467.tif 000036
【表９】
2005520467.tif 000037
【００８６】
図１５Ａおよび１５Ｂに示されている編成により、メモリアクセスの速度はＬＤＰＣコード化中に大幅に増加される。
【００８７】
図１６は、本発明による実施形態が実施されることのできるコンピュータシステムを示している。コンピュータシステム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を構成するワイヤを備えた同軸ケーブル、銅線および光ファイバが含まれる。伝送媒体はまた、無線周波数（ＲＦ）および赤外線（ＩＲ）データ通信中に生成されたもののような音波、光または電磁波の形態をとることができる。一般的な形態のコンピュータ読出し可能な媒体には、たとえば、フロッピー（Ｒ）ディスク、フレキシブルディスク、ハードディスク、磁気テープ、任意の他の磁気媒体、ＣＤ−ＲＯＭ、ＣＤＲＷ、ＤＶＤ、任意の他の光学媒体、パンチカード、紙テープ、光学式マークシート、孔のパターンまたは光学的に認識可能なしるしを有する任意の他の物理的媒体、ＲＡＭ、ＰＲＯＭ、およびＥＰＲＯＭ、ＦＬＡＳＨ−ＥＰＲＯＭ、任意の他のメモリチップまたはカートリッジ、搬送波、あるいはコンピュータが読出すことのできる任意の他の媒体が含まれる。
【００９４】
種々の形態のコンピュータ読出し可能な媒体が、命令をその実行のためにプロセッサに与えるために使用されることができる。たとえば、本発明の少なくとも一部を実行する命令は最初に、遠隔コンピュータの磁気ディスク上で生成されてもよい。このようなシナリオでは、遠隔コンピュータは命令を主メモリ中にロードし、その命令をモデムを使用して電話線で送信する。ローカルコンピュータシステムのモデムは電話線上のデータを受信し、赤外線送信機を使用してそのデータを赤外線信号に変換し、その赤外線信号をパーソナルデジタルアシスタント（ＰＤＡ）およびラップトップのような可搬計算装置に送信する。この可搬計算装置上の赤外線検出器は、赤外線信号から生成された情報および命令を受取ってそのデータをバスに供給する。バスはデータを主メモリに送り、この主メモリからプロセッサが命令を検索し、実行する。主メモリにより受取られた命令は、プロセッサによる実行の前または後に随意に記憶装置上に記憶されることができる。
【００９５】
したがって、本発明の種々の実施形態は、エンコーダおよびデコーダを簡単化するように、構成された低密度パリティチェック（ＬＤＰＣ）コードを生成する方法を提供する。ＬＤＰＣコードの構造は、パリティチェックマトリックスの一部分を下方の三角となるように制限することによって与えられる。また、この方法の利点は送信されたビットに関するＬＤＰＣコードの一様でないエラー保護機能を利用して、高次の変調コンステレーション（８−ＰＳＫ（位相シフトキーイング）のような）の弱点のあるビットに対して追加のエラー保護を提供することにある。復号プロセスは、デコーダが１回または数回反復した後にＬＤＰＣデコーダ中に信号コンステレーションビット計量を反復的に再生することを必然的に伴なう。上述したアプローチには、パフォーマンスを犠牲にせずに複雑さを軽減するという利点がある。
【００９６】
本発明はいくつかの実施形態および構成との関連して説明されたが、本発明はそれにより限定されるものではなく、添付されている請求の範囲の技術的範囲内にある種々の明らかな修正および等価な構成を包含するものである。
【図面の簡単な説明】
【００９７】
【図１】本発明の１実施形態にしたがって低密度パリティチェック（ＬＤＰＣ）コードを使用するように構成された通信システムの概略図。
【図２】図１のシステム内の送信機の例示的な送信機の概略図。
【図３】図１のシステム内の例示的な受信機の概略図。
【図４】本発明の１実施形態によるスパースパリティチェックマトリックスの概略図。
【図５】図４のマトリックスのＬＤＰＣコードの２部グラフの概略図。
【図６】サブマトリックスが下方三角領域に制限されたパリティチェック値を含んでいる、本発明の１実施形態によるスパースパリティチェックマトリックスのサブマトリックスの概略図。
【図７】制限されていないパリティチェックマトリックス（Ｈマトリックス）を使用したコードと図６に示されているようなサブマトリックスを有する制限されたＨマトリックスを使用したコードとの間のパフォーマンスを示すグラフ。
【図８Ａ】図１のシステムにおいて使用されることのできる非グレー８−ＰＳＫ変調方式の概略図。
【図８Ｂ】図１のシステムにおいて使用されることのできるグレー８−ＰＳＫ変調方式の概略図。
【図９】グレーラベル付けを使用したコードと非グレーラベル付けを使用したコードとの間のパフォーマンスを示すグラフ。
【図１０】本発明の１実施形態による非グレーマッピングを使用するＬＤＰＣデコーダの動作のフローチャート。
【図１１】本発明の１実施形態によるグレーマッピングを使用する図３のＬＤＰＣデコーダの動作のフローチャート。
【図１２】本発明の１実施形態による復号プロセスにおけるチェックノードとビットノードとの間の相互作用の概略図。
【図１３】順方向・逆方向アプローチおよび並列アプローチをそれぞれ使用してチェックノードとビットノードとの間の出ていくメッセージを計算する本発明の種々の実施形態によるプロセスのフローチャート。
【図１４Ａ】本発明の種々の実施形態にしたがって発生されたＬＤＰＣコードのシミュレーション結果を示すグラフ。
【図１４Ｂ】本発明の種々の実施形態にしたがって発生されたＬＤＰＣコードのシミュレーション結果を示すグラフ。
【図１４Ｃ】本発明の種々の実施形態にしたがって発生されたＬＤＰＣコードのシミュレーション結果を示すグラフ。
【図１５Ａ】ＬＤＰＣコード化のときにランダム化を達成するように構成されたアクセスをサポートするように編成されたメモリの上方エッジの概略図。
【図１５Ｂ】ＬＤＰＣコード化のときにランダム化を達成するように構成されたアクセスをサポートするように編成されたメモリの下方エッジの概略図。
【図１６】本発明の実施形態にしたがってＬＤＰＣコードを符号化し、復号するプロセスを行うことのできるコンピュータシステムの概略図。
【図１】
2005520467.tif 000038
【図２】
2005520467.tif 000039
【図３】
2005520467.tif 000040
【図４】
2005520467.tif 000041
【図５】
2005520467.tif 000042
【図６】
2005520467.tif 000043
【図７】
2005520467.tif 000044
【図８Ａ】
2005520467.tif 000045
【図８Ｂ】
2005520467.tif 000046
【図９】
2005520467.tif 000047
【図１０】
2005520467.tif 000048
【図１１】
2005520467.tif 000049
【図１２】
2005520467.tif 000050
【図１３】
2005520467.tif 000051
【図１４Ａ】
2005520467.tif 000052
【図１４Ｂ】
2005520467.tif 000053
【図１４Ｃ】
2005520467.tif 000054
【図１５Ａ】
2005520467.tif 000055
【図１５Ｂ】
2005520467.tif 000056
【図１６】
2005520467.tif 000057
【国際調査報告】
2005520467.tif 000058
2005520467.tif 000059
2005520467.tif 000060