(57)【要約】【課題】本発明は、簡単な符号化およびデコードプロセスを使用し、複雑性を導入せずに高データレートをサポートするために使用されるＬＤＰＣコードをデコードする方法およびシステムを提供することを目的とする。【解決手段】本願発明のデコード方法は、受信された雑音シンボル点とＬＤＰＣコードに関係する信号コンステレーションのシンボル点との間の距離に関係する距離ベクトル情報に基づいて事前確率情報を受信し、事前確率情報に基づいた事後確率情報を送信し、ＬＤＰＣコードに関係するパリティチェックの式が事前確率情報および事後確率情報にしたがって満足されるか否かを決定し、決定ステップに基づいて信号コンステレーションビットメトリックを選択的に再生成し、再生成された信号コンステレーションビットメトリックに基づいてデコードされたメッセージを出力することを特徴とする。【選択図】　　図１３
2004080753.tif 000002
【特許請求の範囲】
【請求項１】
低密度パリティチェック（ＬＤＰＣ）コードをデコードする方法において、
受信された雑音シンボル点とＬＤＰＣコードに関係する信号コンステレーションのシンボル点との間の距離に関係する距離ベクトル情報に基づいて事前確率情報を受信し、
事前確率情報に基づいた事後確率情報を送信し、
ＬＤＰＣコードに関係するパリティチェックの式が事前確率情報および事後確率情報にしたがって満足されるか否かを決定し、
決定ステップに基づいて信号コンステレーションビットメトリックを選択的に再生成し、
再生成された信号コンステレーションビットメトリックに基づいてデコードされたメッセージを出力するステップを有する低密度パリティチェックコードのデコード方法。
【請求項２】
さらに、事後確率情報および事前確率情報に基づいて外部情報を決定し、
外部情報にしたがって信号コンステレーションに関係するシンボル確率を出力するステップを含んでいる請求項１記載の方法。
【請求項３】
信号コンステレーションのシンボルはグレーコード化され、それによりグレーコード化された信号コンステレーションの弱いビットがグレーコード化されたシンボルのコンステレーションの弱さの少ないビットと少なくとも同じパリティチェックを割当てられる請求項１記載の方法。
【請求項４】
さらに、ＬＤＰＣコードのビットノードおよびチェックノードに関する情報を連続した物理的メモリ位置に記憶する請求項１記載の方法。
【請求項５】
ＬＤＰＣコードはパリティチェックマトリックスのサブマトリックスに制限を与える構成されたパリティチェックマトリックスを使用してコード化される請求項１記載の方法。
【請求項６】
信号コンステレーションは、８−ＰＳＫ（位相シフトキーイング）、１６ＱＡＭ（直交振幅変調）およびＱＰＳＫ（直交位相シフトキーイング）の１つを含んでいる請求項１記載の方法。
【請求項７】
低密度パリティチェック（ＬＤＰＣ）コードをデコードするための命令を保持し、前記命令は実行において請求項１記載の方法を１以上のプロセッサに行わせるように構成されているコンピュータ読取り可能な媒体。
【請求項８】
低密度パリティチェック（ＬＤＰＣ）コードをデコードするシステムにおいて、
受信された雑音シンボル点とＬＤＰＣコードに関係する信号コンステレーションのシンボル点との間の距離に関係する距離ベクトル情報に基づいて事前確率情報を受信する手段と、
事前確率情報に基づいて事後確率情報を送信する手段と、
ＬＤＰＣコードに関係するパリティチェックの式が事前確率情報と事後確率情報とにしたがって満足されるか否かを決定する手段と、
その決定に基づいて信号コンステレーションビットメトリックを選択的に再生成する手段と、
再生成された信号コンステレーションビットメトリックに基づいてデコードされたメッセージを出力する手段とを具備している低密度パリティチェックコードのデコードシステム。
【請求項９】
さらに、事後確率情報と事前確率情報とに基づいて外部情報を決定する手段と、
外部情報にしたがって信号コンステレーションに関係するシンボル確率を出力する手段とを含んでいる請求項８記載のシステム。
【請求項１０】
信号コンステレーションのシンボルはグレーコード化され、それによりグレーコード化されたシンボルコンステレーションの弱いビットがグレーコード化されたシンボルコンステレーションの弱さの少ないビットと少なくとも同じパリティを割当てられる請求項８記載のシステム。
【請求項１１】
さらに、ＬＤＰＣコードのビットノードおよびチェックノードに関する情報を連続する物理的位置に記憶する請求項８記載のシステム。
【請求項１２】
ＬＤＰＣコードはパリティチェックマトリックスのサブマトリックスに制限を与える構成されたパリティチェックマトリックスを使用してコード化される請求項８記載のシステム。
【請求項１３】
信号コンステレーションは、８−ＰＳＫ（位相シフトキーイング）、１６ＱＡＭ（直交振幅変調）およびＱＰＳＫ（直交位相シフトキーイング）の１つを含んでいる請求項１記載のシステム。
【請求項１４】
低密度パリティチェック（ＬＤＰＣ）コードをデコードする受信機において、
受信された雑音シンボル点とＬＤＰＣコードに関係する信号コンステレーションのシンボル点との間の距離に関係する距離ベクトル情報に基づいて事前確率情報を生成するように構成されているビットメトリック発生器と、
ビットメトリック発生器から受信された事前確率情報に基づいて事後確率情報を出力するように構成されたデコーダとを具備し、
デコーダはさらにＬＤＰＣコードに関係するパリティチェックの式が事前確率情報と事後確率情報とにしたがって満足されるか否かを決定するように構成され、
デコーダはパリティチェックの式が満足されない場合には再生成された信号コンステレーションビットメトリックに基づいてデコードされたメッセージを出力するように構成されている受信機。
【請求項１５】
さらに、ビットメトリック発生器は、事後確率情報と事前確率情報とに基づいて外部情報を決定し、外部情報にしたがった信号コンステレーションに関係するシンボル確率を出力するように構成されている請求項１４記載の受信機。
【請求項１６】
信号コンステレーションのシンボルはグレーコード化され、それによりグレーコード化されたシンボルコンステレーションの弱いビットがグレーコード化されたシンボルコンステレーションの弱さの少ないビットと少なくとも同じパリティを割当てられる請求項１４記載の受信機。
【請求項１７】
さらに、ＬＤＰＣコードのビットノードおよびチェックノードに関する情報を連続して記憶するように構成されているメモリを備えている請求項１４記載の受信機。
【請求項１８】
ＬＤＰＣコードはパリティチェックマトリックスのサブマトリックスに制限を与える構成されたパリティチェックマトリックスを使用してコード化されている請求項１４記載の受信機。
【請求項１９】
信号コンステレーションは、８−ＰＳＫ（位相シフトキーイング）、１６ＱＡＭ（直交振幅変調）およびＱＰＳＫ（直交位相シフトキーイング）の１つを含んでいる請求項１４記載の受信機。
【請求項２０】
低密度パリティチェック（ＬＤＰＣ）コードを使用しているメッセージを送信する方法において、
ＬＤＰＣコードを発生するためにパリティチェックマトリックスのサブマトリックスに制限を与える構成されたパリティチェックマトリックスにしたがって入力メッセージをコード化し、
無線通信システムによりＬＤＰＣコードを送信し、
無線通信システムにより通信している受信機はＬＤＰＣコードに関係する信号のコンステレーションにしたがって受信されたＬＤＰＣコードを反復的にデコードするように構成され、受信機は１以上のデコードの反復後に信号コンステレーションビットメトリックを反復的に再生成するように構成されている送信方法。
【請求項２１】
送信ステップにおいて、受信機は、受信された雑音シンボル点とＬＤＰＣコードと関連する信号コンステレーションのシンボル点との間の距離に関する距離ベクトル情報に基づいてビットメトリック発生器によって生成される事前確率情報に基づいて事後確率情報を送信するように構成されたＬＤＰＣデコーダを含み、
そのデコーダは、ＬＤＰＣコードに関係するパリティチェックの式が事前確率情報と事後確率情報とにしたがって満足されるか否かを決定する請求項２０記載の方法。
【請求項２２】
信号コンステレーションは、８−ＰＳＫ（位相シフトキーイング）、１６ＱＡＭ（直交振幅変調）およびＱＰＳＫ（直交位相シフトキーイング）の１つを含んでいる請求項２０記載の方法。
【請求項２３】
無線通信システムはＬＤＰＣコードの送信をサポートする衛星を含んでいる請求項２０記載の方法。
【請求項２４】
低密度パリティチェック（ＬＤＰＣ）コードを使用してメッセージを送信するための命令を保持しているコンピュータ読取り可能な媒体において、
前記命令は、実行されるとき、請求項２０記載の方法を１以上のプロセッサに行わせるように構成されているコンピュータの読取り可能な媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は通信システム、特にコードシステムシステムに関する。
【０００２】
【従来の技術】
通信システムは雑音のある通信チャンネルを横切って信頼性のある通信を行うためにコード化を使用する。これらの通信チャンネルは所定の信号対雑音比（ＳＮＲ）におけるシンボル当りのビットに関して表されることができる固定した容量を示し、論理的な上限（シャノン限界として知られている）を規定する。結果として、コード化設計はこのシャノン限界に接近するレートを実現することを目的とする。シャノン限界に接近する１つのこのようなクラスのコードは低密度パリティチェック（ＬＤＰＣ）コードである。
【０００３】
伝統的に、ＬＤＰＣコードは多くの欠点のために広く配備されていない。１つの欠点はＬＤＰＣ符号化技術が非常に複雑であることである。その発生器マトリックスを使用するＬＤＰＣコードの符号化は非常に大きい疎でないマトリックスの記憶を必要とする。さらにＬＤＰＣコードは効率的であるように大きいブロックを必要とし、結果的に、ＬＤＰＣコードのパリティチェックマトリックスが疎であったとしても、これらのマトリックスの記憶は問題である。
【０００４】
構成の観点から、多くの挑戦が行われている、例えば記憶はＬＤＰＣコードが実際に広く普及していない重要な理由である。またＬＤＰＣコード構成の重要な挑戦はデコーダ中の幾つかの処理エンジン（ノード）間に接続ネットワークを実現する方法である。さらにデコードプロセスの計算負荷、特にチェックノード動作は問題を有する。
【０００５】
【発明が解決しようとする課題】
それ故、簡単な符号化およびデコードプロセスを使用するＬＤＰＣ通信システムが必要とされる。より大きな複雑性を導入せずに高データレートをサポートするために効率的にＬＤＰＣコードを使用する必要もある。これはまたＬＤＰＣエンコーダおよびデコーダの改良された性能を必要とする。また、ＬＤＰＣコード化を行うためのメモリの要求を最小にすることが必要である。さらに、ＬＤＰＣデコーダで処理ノード間の通信を簡単にする方式も必要である。
【０００６】
【課題を解決するための手段】
これらおよび他の必要性は本発明により解決され、構成された低密度パリティチェック（ＬＤＰＣ）コードをデコードする方法が与えられる。ＬＤＰＣコードの構造はパリティチェックマトリックスの部分を低い三角へ限定し、および／またはデコーダの処理ノード間の通信が非常に簡単になるような他の要求を満足させることにより与えられる。またこの方法は高次の変調コンステレーション（８−ＰＳＫ（位相シフトキーイング）等）のさらに弱いビットへ余分のエラー保護を与えるために送信されたビットにＬＤＰＣコードの等しくないエラー保護容量を有効に使用することができる。デコードプロセスは各デコーダの反復後または幾つかのデコーダの反復後にＬＤＰＣデコーダへの信号コンピュータステレーションビットメトリックを反復的に再生成することを含んでいる。前述の装置はＬＤＰＣコードのデコードについての計算上効率的な方法を与える。
【０００７】
本発明の１実施形態の１特徴によると、低密度パリティチェック（ＬＤＰＣ）コードをデコードする方法が提供される。この方法は、受信された雑音シンボル点とＬＤＰＣコードに関係する信号コンステレーションのシンボル点との間の距離に関係する距離ベクトル情報に基づいて事前確率情報を受信することを含んでいる。この方法はさらに事前確率情報に基づいた事後確率情報の送信を含んでいる。この方法はＬＤＰＣコードに関係するパリティチェックの式が事前確率情報および事後確率情報にしたがって満足されるか否かを決定することを含んでいる。さらにこの方法は決定ステップに基づいて信号コンステレーションビットメトリックを選択的に再生成することを含んでいる。さらにこの方法は再生成された信号コンステレーションビットメトリックに基づいてデコードされたメッセージを出力することを含んでいる。
【０００８】
本発明の１実施形態の別の特徴によれば、低密度パリティチェック（ＬＤＰＣ）コードをデコードするシステムが提供される。このシステムは受信された雑音シンボル点とＬＤＰＣコードに関係する信号コンステレーションのシンボル点との間の距離に関係する距離ベクトル情報に基づいて事前確率情報を受信する手段を含んでいる。システムはまた、事前確率情報に基づいて事後確率情報を送信する手段を含んでいる。さらにシステムはＬＤＰＣコードに関係するパリティチェックの式が事前確率情報と事後確率情報とにしたがって満足されるか否かを決定する手段を含んでいる。システムはその決定に基づいて信号コンステレーションビットメトリックを選択的に再生成する手段を含んでいる。さらにシステムは再生成された信号コンステレーションビットメトリックに基づいてデコードされたメッセージを出力する手段を具備している。
【０００９】
本発明の１実施形態の別の特徴によると、低密度パリティチェック（ＬＤＰＣ）コードをデコードする受信機が提供される。受信機は、受信された雑音シンボル点とＬＤＰＣコードに関係する信号コンステレーションのシンボル点との間の距離に関係する距離ベクトル情報に基づいて事前確率情報を生成するように構成されているビットメトリック発生器を含んでいる。受信機はまたビットメトリック発生器から受信された事前確率情報に基づいて事後確率情報を出力するように構成されたデコーダを具備し、このデコーダはさらにＬＤＰＣコードに関係するパリティチェックの式が事前確率情報と事後確率情報とにしたがって満足されるか否かを決定するように構成されている。デコーダはパリティチェックの式が満足されない場合には再生成された信号コンステレーションビットメトリックに基づいてデコードされたメッセージを出力する。
【００１０】
本発明の１実施形態の別の特徴によると、低密度パリティチェック（ＬＤＰＣ）コードを使用しているメッセージを送信する方法が提供される。この方法はＬＤＰＣコードを発生するためにパリティチェックマトリックスのサブマトリックスに制限を与える構成されたパリティチェックマトリックスにしたがって入力メッセージをコード化することを含んでいる。この方法はまた無線通信システムによりＬＤＰＣコードを送信することを含んでおり、無線通信システムにより通信している受信機はＬＤＰＣコードに関係する信号のコンステレーションにしたがって受信されたＬＤＰＣコードを反復的にデコードするように構成されている。受信機は１以上のデコードの反復後に信号コンステレーションビットメトリックを反復的に再生成するように構成されている。
【００１１】
本発明のその他の特徴、特性、利点は、本発明を実施するために考慮された最良のモードを含む多くの特定の実施形態および構成を単に例示として示した以下の詳細な説明から容易に明白になるであろう。また、本発明は本発明の技術的範囲を逸脱せずに他のおよび異なる実施形態が可能であり、その幾つかの詳細が種々の明白な点に関して変形されることができる。したがって、図面および説明は発明を限定するものではなく例示として考慮される。
【００１２】
【発明の実施の形態】
本発明を限定ではない例示として説明する。添付図面では、同一の参照符号は類似の素子を表している。
構成された低密度パリティチェック（ＬＤＰＣ）コードを効率よく生成するシステム、方法、ソフトウェアを説明する。以下の説明では、説明の目的で、複数の特別な詳細を本発明を徹底的に理解するために説明する。しかしながら、当業者には本発明がこれらの特別な詳細な構成なしにまたは、等価の装置により実施されてもよいことが明白である。他の例では、よく知られた構造および装置を本発明を不必要に不明確にすることを避けるためブロック図の形態で示している。
【００１３】
図１は本発明の１実施形態にしたがった低密度パリティチェック（ＬＤＰＣ）コードを使用するように構成された通信システムのブロック図である。デジタル通信システム１００　は信号波形を発生し、通信チャンネル１０３　を横切って受信機１０５　へ送る送信機１０１　を含んでいる。このディスクリートな通信システム１００　では、送信機１０１　は可能なメッセージのディスクリートなセットを発生するメッセージソースを有し、各可能なメッセージは対応する信号波形を有する。これらの信号波形は通信チャンネル１０３　により減衰されるか、そうでなければ変更される。
雑音チャンネル１０３　に対抗するために、ＬＤＰＣコードが使用される。
【００１４】
送信機１０１　により発生されるＬＤＰＣコードは何等性能損失を招かずに高速度の実行を可能にする。送信機１０１　から出力されたこれらの構成されたＬＤＰＣコードは変調方式（例えば８−ＰＳＫ）によりチャンネルエラーに対して既に脆弱であるビットノードへ少数のチェックノードを割当てることを避ける。
【００１５】
このようなＬＤＰＣコードは（ターボコードと異なる）平行化が可能なデコードアルゴリズムを有し、これは加算、比較、テーブルの検索等の簡単な演算を有効に含んでいる。さらに、慎重に設計されたＬＤＰＣコードは任意のエラーフロアのサインを示さない。
【００１６】
本発明の１実施形態によると、送信機１０１　は比較的簡単な符号化技術を使用して、受信機１０５　と通信するために（デコード中に効率的なメモリアクセスを容易にする）パリティチェックマトリックスに基づいてＬＤＰＣコードを発生する。
送信機１０１　はブロック長が十分に大きいならば、連結したターボ＋ＲＳ（リード−ソロモン）コードより優れたＬＤＰＣコードを使用する。
【００１７】
図２は図１のシステムの例示的な送信機のブロック図である。送信機２００　には情報ソース２０１　から入力を受取り、受信機１０５　でのエラー補正処理に適している高い冗長度のコード化されたストリームを出力するＬＤＰＣエンコーダ２０３　が備えられている。情報ソース２０１　はディスクリートなアルファベットＸからｋ信号を発生し、ＬＤＰＣコードはパリティチェックマトリックスによって特定される。他方で、ＬＤＰＣコードのコード化は通常発生器マトリックスを特定することを必要とする。ガウスの消去法を使用してパリティチェックマトリックスから発生器マトリックスを獲得することが可能であるが、結果的なマトリックスはもはや疎ではなく、大きい発生器マトリックスの記憶は複雑である。
【００１８】
エンコーダ２０３　は構造をパリティチェックマトリックスに付加することによりパリティチェックマトリックスだけを使用する簡単なコード化技術を使用してアルファベットＹから変調器２０５　への信号を発生する。特に、マトリックスのある部分を三角形であるように制限することによりパリティチェックマトリックスに限定が置かれる。このようなパリティチェックマトリックス構造を以下図６でさらに十分に説明する。このような限定により無視できる程度の性能損失が生じ、それ故、魅力的なトレードオフを構成する。
【００１９】
変調器２０５　はコード化されたメッセージをエンコーダ２０３　から送信アンテナ２０７　へ送信される信号波形へマップし、この送信アンテナは通信チャンネル１０３　によってこれらの波形を放射する。したがって、コード化されたメッセージは変調され、送信アンテナ２０７　へ分配される。送信アンテナ２０７　からの送信は以下説明するように、受信機に伝播する。
【００２０】
図３は図１のＡのシステムの例示的な受信機のブロック図である。受信側では、受信機３００　は送信機２００　からの受信された信号の復調を行う復調器３０１　を含んでいる。これらの信号は復調のために受信アンテナ３０３　で受信される。復調後、受信された信号はデコーダ３０５　へ転送され、これはビットメトリック発生器３０７　と共にメッセージＸ’　を発生することによってもとのソースメッセージを再構成しようとする。グレーではないマッピングにより、ビットメトリック発生器３０７　はデコードプロセス中、確率情報をデコーダ３０５　と前後に（反復して）交換し、これは図１０に詳細に示されている。代わりに、（本発明の１実施形態により）グレーマッピングが使用されるならば、ビットメトリック発生器の１つの通過が十分であり、ここでは各ＬＤＰＣデコーダの反復後にさらにビットメトリック発生を試みることは性能の改良を制限する傾向があり、この方法は図１１に関してさらに十分に説明する。本発明により与えられる利点を認識するために、図４で説明されているように、ＬＤＰＣコードがどのように発生されるかを検査することが有効である。
【００２１】
図４は本発明の１実施形態による疎パリティチェックマトリックスの説明図である。ＬＤＰＣコードは疎パリティチェックマトリックスＨ（ｎ−ｋ）ｘｎ　を有する長い線形のブロックコードである。典型的に、ブロック長ｎは数千から数万ビットの範囲である。例えば、長さｎ＝８でレート１／２のＬＤＰＣコードのパリティチェックマトリックスが図４に示されている。同一のコードは図５によって２部分グラフにより同等に表されることができる。
【００２２】
図５は図４のマトリックスのＬＤＰＣコードの２部分グラフの図である。パリティチェックの式は各チェックノードで、全ての隣接するビットノードの（ＧＦ（ガロア域）（２）にわたる）合計がゼロに等しいことを示唆している。図面で見られるように、ビットノードはグラフの左側を占め、予め定められた関係にしたがって１以上のチェックノードに関連されている。例えばチェックノードｍ１　に対応して、以下の式はビットのノードに関してｎ１　＋ｎ４　＋ｎ５　＋ｎ８　＝０が存在する。
【００２３】
受信機３０３　に戻ると、ＬＤＰＣデコーダ３０５　はメッセージ通過デコーダと考えられ、それによってデコーダ３０５　はビットノードの値を発見することを目的とする。このタスクを実現するためにビットノードとチェックノードは相互に反復して通信する。この通信の特性を以下説明する。
【００２４】
チェックノードからビットノードへ、各チェックノードは他の隣接するビットノードから来る情報に基づいてビットノードの値に関する評価（“意見”）を隣接ビットノードへ提供する。例えば、先の例では、ｎ４　＋ｎ５　＋ｎ８　の合計が０からｍ１　（のように見える）ならば、（ｎ１　＋ｎ４　＋ｎ５　＋ｎ８　＝０なので）ｍ１　はｎ１　にｎ１　の値が０であると考えられていることを示し、そうでなければｍ１　はｎ１　にｎ１　の値が１であると考えられていることを指示する。さらに、ソフト決定デコードでは、信頼性の尺度が付加される。
【００２５】
ビットノードからチェックノードへ、各ビットノードは他の隣接チェックノードから来るフィードバックに基づいてその自己の値についての評価を隣接チェックノードへ中継する。先の例では、ｎ１　はただ２つの隣接チェックノードｍ１　とｍ３　を有する。ｍ３　からｎ１　へ来るフィードバックが、値ｎ１　が恐らく０であることを示したならば、ｎ１　はｍ１　にｎ１　の自己値の評価が０であることを通知する。ビットノードが２よりも多数の隣接チェックノードを有する場合、通信しているチェックノードへの決定を報告する前に他の隣接チェックノードから来るフィードバックにおいてビットノードは大多数の投票（ソフト決定）を実行する。
先のプロセスは全てのビットノードが正しいと考慮されるまで（即ち全てのパリティチェックの式が満足されるまで）、または予め定められた最大数の反復に到達するまで反復され、それによってデコードの故障が宣言される。
【００２６】
図６は疎パリティチェックマトリックスのサブマトリックスの図であり、サブマトリックスは本発明の１実施形態にしたがって低い三角形領域に限定されるパリティチェック値を含んでいる。前述したように、（図２の）エンコーダ２０３　はパリティチェックマトリックスの低い三角形領域の値を制限することにより簡単なエンコード技術を使用できる。本発明の１実施形態によれば、パリティチェックマトリックスに与えられる制限は以下の形態である。
Ｈ（ｎ−ｋ）ｘｎ　＝［Ａ（ｎ−ｋ）ｘｋ　Ｂ（ｎ−ｋ）ｘ（ｎ−ｋ）　］
ここでＢは低い三角形である。
【００２７】
任意の情報ブロックｉ＝（ｉ０　，ｉ１　，…，ｉｋ−１　）はＨｃＴ　＝０を使用してコードワードｃ＝（ｉ０　，ｉ１　，…，ｉｋ−１　，ｐ０　，ｐ１　，…，ｐｎ−ｋ−１　）にコード化され、帰納的にパリティビットを解く。例えば、
ａ００ｉ０　＋ａ０１ｉ１　＋…＋ａ０，ｋ−１　ｉｋ−１　＋ｐ０　＝０→ｐ０　を解く
ａ１０ｉ０　＋ａ１１ｉ１　＋…＋ａ１，ｋ−１　ｉｋ−１　＋ｂ１０ｐ０　＋ｐ１　＝０→ｐ１　を解く
ｐ２　、ｐ３　、…ｐｎ−ｋ−１　でも同様である。
【００２８】
図７は限定されていないパリティチェックマトリックス（Ｈマトリックス）対図６の限定されたＨマトリックスとの性能を示したグラフである。グラフは２つのＬＤＰＣコード間の性能比較を示しており、その一方は通常のパリティチェックマトリックスを有し、他方はコード化を簡単にするために低い三角形に限定されているパリティチェックマトリックスを有している。このシミュレーションの変調方式は８ＰＳＫである。性能損失は０．１ｄＢ以内である。それ故、性能損失は低い三角形Ｈマトリックスの限定に基づいて無視できる程度であり、エンコード技術の簡明さの利点は重要である。したがって、低い三角形または行および／または列の交換下の高い三角形に等しいパリティチェックマトリックスは同じ目的で使用されることができる。
【００２９】
図８のＡとＢはそれぞれグレーではない８−ＰＳＫ変調方式とグレーの８−ＰＳＫ変調の説明図であり、それぞれ図１のＡのシステムで使用されることができる。図８のＡのグレーではない８−ＰＳＫ変調方式は非常に低いフレーム消去レート（ＦＥＲ）を必要とするシステムを提供するために図３の受信機で利用されることができる。この要求はまた図８のＢで示されているように、ビーシーエッチ（Ｂｏｓｅ、Ｃｈａｕｄｈｕｒｉ　、Ｈｏｃｑｕｅｎｇｈｅｍ　（ＢＣＨ））、ハミングまたはリード−ソロモン（ＲＳ）コードのような外部コードを使用してグレーの８−ＰＳＫ変調方式を使用して満足される。
【００３０】
この方式下では、ＬＤＰＣデコーダ３０５　（図３）とビットメトリック発生器３０７　との間で反復する必要はない。これは８−ＰＳＫ変調を使用してもよい。外部コードがないと、グレーのラベリングを使用するＬＤＰＣデコーダ３０５　は以下の図９で示されているように早期のエラーフロアを示す。
【００３１】
図９は図８のＡとＢのグレーのラベリング対グレーではないラベリングを使用するコード間の性能を示したグラフである。エラーフロアはＬＤＰＣデコーダ３０５　からの正確なフィードバックを仮定して、既知の２ビットを有する２つの８−ＰＳＫ符号がさらにグレーではないラベリングで離れているために８−ＰＳＫビットメトリックの再生がグレーではないラベリングでさらに正確であるという事実から生じる。これは同様に高い信号対雑音比（ＳＮＲ）で動作するように見える。それ故、グレーまたはグレーではないラベリングを使用する同一のＬＤＰＣコードのエラー漸近線は同一の勾配を有しても（即ち相互に平行）、グレーではないラベリングを有するコードは任意のＳＮＲで低いＦＥＲを通過する。
【００３２】
他方で、非常に低いＧＥＲを必要としないシステムでは、ＬＤＰＣデコーダ３０５　と８−ＰＳＫビットメトリック発生器３０７　との間で反復しないグレーラベリングは、それぞれのＬＤＰＣデコーダ反復前に８−ＰＳＫビットメトリックの再生が複雑性を付加するのでさらに適切である。さらに、グレーラベリングが使用されるとき、それぞれのＬＤＰＣデコーダ反復前の８−ＰＳＫビットメトリックの再生は非常に僅かな性能改良だけを生じる。先に説明したように、反復のないグレーラベリングは外部コードが構成されるならば、非常に低いＦＥＲを必要とするシステムで使用されてもよい。
【００３３】
グレーラベリングとグレーではないラベリング間の選択はＬＤＰＣコード特性にも依存する。高い度合いのノードではＬＤＰＣデコーダ３０５　から８−ＰＳＫ（または類似の高次の変調）ビットメトリック発生器３０７　への初期のフィードバックがグレーではないラベリングによりさらに劣化するので、典型的にビットまたはチェックノードの程度が高い程、グレーラベリングには良好である。
【００３４】
８−ＰＳＫ（または類似の高次の）変調が２進デコーダで利用されるとき、符号の３（以上の）ビットが“等しい雑音で”受信されないことが認識される。例えばグレーの８−ＰＳＫラベリングでは、シンボルの第３のビットは他の２つのビットよりもデコードに対して雑音があると考慮される。それ故、ＬＤＰＣコード設計は８−ＰＳＫシンボルの“さらに雑音のある”第３のビットにより表されるこれらのビットノードに少数のエッジを割当てず、それによってこれらのビットは２度のペナルティを受けない。
【００３５】
図１０は本発明の１実施形態によるグレーではないマッピングを使用するＬＤＰＣデコーダの動作のフローチャートである。この方法では、ＬＤＰＣデコーダとビットメトリック発生器は次々に反復する。この例では、８−ＰＳＫ変調が使用されるが、同一の原理は他の高い変調方式にも適用される。このシナリオでは、変調器３０１　は距離ベクトルｄを出力し、受信された雑音シンボル点と８−ＰＳＫシンボル点とビットメトリック発生器３０７　との間の距離を示し、それによってベクトル成分は以下のようになることが想定される。
ｄｉ　＝−（ＥＳ　／Ｎ０　）｛（ｒｘ　−ｓｉ，ｘ　）２　＋（ｒｙ　−ｓｉ，ｙ　）２　｝
ｉ＝０，１，…７
８−ＰＳＫビットメトリック発生器３０７　は演繹的確率情報と経験的確率情報を交換するためにＬＤＰＣデコーダ３０５　と通信し、これはそれぞれｕとａで表される。即ちベクトルｕとａはそれぞれコード化されたビットのログ尤度比の演繹的および経験的確率を表す。
【００３６】
８−ＰＳＫビットメトリック発生器３０７　は以下のように３ビットの各グループの演繹的尤度比を発生する。最初に、コード化されたビットの外因的な情報が得られる。
【００３７】
ｅｊ　＝ａｊ　−ｕｊ　　　ｊ＝０，１，２
次に、８−ＰＳＫシンボル確率ｐｉ　　ｉ＝０，１，…，７が決定される。
＊　ｙｊ　＝−ｆ（０，ｅｊ　）　ｊ＝０，１，２
ここでｆ（ａ，ｂ）＝ｍａｘ（ａ，ｂ）＋ＬＵＴｆ　（ａ，ｂ）であり、
ＬＵＴｆ　（ａ，ｂ）＝ｌｎ（１＋ｅ　−｜ａ−ｂ　｜）である。
＊　ｘｊ　＝ｙｊ　＋ｅｊ　　　ｊ＝０，１，２
＊　ｐ０　＝ｘ０　＋ｘ１　＋ｘ２　　　ｐ４　＝ｙ０　＋ｘ１　＋ｘ２　
ｐ１　＝ｘ０　＋ｘ１　＋ｙ２　　　ｐ５　＝ｙ０　＋ｘ１　＋ｙ２　
ｐ２　＝ｘ０　＋ｙ１　＋ｘ２　　　ｐ６　＝ｙ０　＋ｙ１　＋ｘ２　
ｐ３　＝ｘ０　＋ｙ１　＋ｙ２　　　ｐ７　＝ｙ０　＋ｙ１　＋ｙ２　
次に、ビットメトリック発生器３０７　は以下のようにＬＤＰＣデコーダ３０５　への入力として、コード化されたビットの演繹的なログ尤度比を決定する。
【数１】
2004080753.tif 000003
２つよりも多数の変数が帰納的に評価されることができることに注意し、例えば、
ｆ（ａ，ｂ，ｃ）＝ｆ（ｆ（ａ，ｂ），ｃ）
グレーではないマッピングを使用するＬＤＰＣデコーダ３０５　の動作を説明する。ステップ１００１では、ＬＤＰＣデコーダ３０５　は次式にしたがって（および図１２のＡに示されているように）第１の反復前にコード化されたビットのログ尤度比ｖを初期化する。
ｖ　ｎ→ｋｉ＝ｕｎ　、ｎ＝０，１，…，Ｎ−１、ｉ＝１，２，…，ｄｅｇ（ビットノードｎ）
ここでｖ　ｎ→ｋｉはビットノードｎからその隣接するチェックノードｋｉ　へ送られるメッセージを示し、ｕｎ　はビットｎの復調器出力を示し、Ｎはコードワードのサイズである。
【００３８】
ステップ１００３では、チェックノードｋは更新され、それによって入力ｖは出力ｗを生成する。図１２のＢに示されるように、ｄｃ　の隣接するビットノードからチェックノードｋへ入来するメッセージはｖｎ１→ｋ　，ｖｎ２→ｋ　，…ｖ　ｎｄｃ→ｋ　により示される。目的はチェックノードｋからｄｃ　の隣接するビットノードへの出力メッセージを計算することである。これらのメッセージはｗ　ｋ→ｎ１，ｗ　ｋ→ｎ２，…，ｗ　ｋ→ｎｄｃ　により示され、ここで、
ｗ　ｋ→ｎｉ＝ｇ（ｖｎ１→ｋ　，ｖｎ２→ｋ　，…，ｖｎｉ−１→ｋ　，ｖｎｉ＋１→ｋ　，…，ｖｎｄｃ　→ｋ　）
関数ｇ（　）は以下のように規定される。
ｇ（ａ，ｂ）＝ｓｉｇｎ（ａ）×ｓｉｇｎ（ｂ）×｛ｍｉｎ（｜ａ｜，｜ｂ｜）｝＋ＬＵＴｇ　（ａ，ｂ）
ここで、
ＬＵＴｇ　（ａ，ｂ）＝ｌｎ（１＋ｅ　−｜ａ＋ｂ　｜）−ｌｎ（１＋ｅ　−｜ａ−ｂ　｜）
である。関数ｆと類似して、２よりも多数の変数を有する関数ｇは帰納的に評価されることができる。
【００３９】
次に、デコーダ３０５　はステップ１２０５で経験的確率情報（図１２のＣ）を出力し、それによって、
【数２】
2004080753.tif 000004
ステップ１００７で、全てのパリティチェックの式が満足されるか否かが決定される。これらのパリティチェックの式が満足されないならば、デコーダ３０５　はステップ１０１１のように、８−ＰＳＫビットメトリックとチャンネル入力ｕｎ　を再度導出する。次に、ステップ１０１３のようにビットノードが更新される。図１６に示されているように、チェックノードに隣接するｄｖ　からビットノードｎへ入来するメッセージはｗｋ１→ｋ　、ｗｋ２→ｋ　、…ｗ　ｋｄｖ→ｋ　により示される。ビットノードｎからの出力メッセージはｄｖ　の隣接するチェックノードへ計算して戻され、このようなメッセージはｖ　ｎ→ｋ１、ｖ　ｎ→ｋ２、ｖ　ｎ→ｋｄｖ　により示され、以下のように計算される。
【００４０】
【数３】
2004080753.tif 000005
ステップ１００９では（全てのパリティチェックの式が満足される場合）デコーダ３０５　はハード決定を出力する。
【数４】
2004080753.tif 000006
前述の方法はグレーではないラベリングが使用されるときに適切である。しかしながら、グレーラベリングが実行されるとき、図１１のプロセスが実行される。
【００４１】
図１１は、本発明の１実施形態にしたがってグレーのマッピングを使用している図３のＬＤＰＣデコーダの動作のフローチャートである。グレーラベリングが使用されるとき、それぞれのＬＤＰＣデコーダ反復後に再生されたビットメトリックが公称上の性能改良をもたらすので、ビットメトリックはＬＤＰＣデコーダ前に一度だけ発生されることが有効である。図１０のステップ１００１および１００３のように、ステップ１１０１および１１０３でコード化されたビットのログ尤度比ｖの初期化が実行され、チェックノードが更新される。次に、ビットノードｎはステップ１１０５のように更新される。その後、デコーダはアポステリオリ確率情報を出力する（ステップ１１０７）。ステップ１１０９では、全てのパリティチェックの式が満足されるか否かの決定が行われ、イエスならば、デコーダはハード決定を出力する（ステップ１１１１）。ノーであるならば、ステップ１１０３−１１０７が反復される。
【００４２】
図１３のＡは本発明の１実施形態にしたがって前方−後方方法を使用してチェックノードとビットノードとの間の出力メッセージを計算するフローチャートである。エッジに隣接するｄｃ　を有するチェックノードでは、ｄｃ　（ｄｃ　−１）の計算と複数のｇ（．，．）関数が実行される。しかしながら、前方−後方方法は計算の複雑性を３（ｄｃ　−２）に減少し、ｄｃ　−１変数が記憶される。
【００４３】
図１２のＢを参照すると、チェックノードｋへ隣接するビットノードｄｃ　への入来メッセージはｖｎ１→ｋ　，ｎ２→ｋ　，…，ｎｄｃ　→ｋ　により示される。出力メッセージはチェックノードｋからｄｃ　隣接ビットノードへ計算され、これらの出力メッセージはｗｋ　→ｎ１，ｗｋ　→ｎ２，…，ｗｋ　→ｎｄｃ　により示されることが望ましい。
【００４４】
これらの出力メッセージを計算するための前方−後方方法では、前方変数ｆ１　，ｆ２　，…，ｆｄｃは以下のように規定される。
ｆ１　＝ｖ１　→ｋ　
ｆ２　＝ｇ（ｆ１　，ｖ２　→ｋ　）
ｆ３　＝ｇ（ｆ２　，ｖ３　→ｋ　）
・　・　・
・　・　・
ｆｄｃ＝ｇ（ｆｄｃ−１，ｖｄｃ→ｋ　）
ステップ１３０１ではこれらの前方変数が計算され、ステップ１３０３で記憶される。
【００４５】
同様に、後方変数ｂ１　，ｂ２　，…，ｂｄｃは以下のように規定される。
ｂｄｃ＝ｖｄｃ→ｋ　
ｂｄｃ−１＝ｇ（ｂｄｃ，ｖｄｃ−１→ｋ　）
・　・　・
・　・　・
ｂ１　＝ｇ（ｂ２　，ｖ１　→ｋ　）
ステップ１３０５では、これらの後方変数が計算される。その後、ステップ１３０７のように、記憶された前方変数と計算された後方変数とに基づいて出力メッセージが計算される。出力メッセージは以下のように計算される。
ｗｋ　→１　＝ｂ２　
ｗｋ　→ｉ　＝ｇ（ｆｉ−１　，ｂｉ＋１　）　ｉ＝２，３，…，ｄｃ　−１
ｗｋ　→ｄｃ＝ｆｄｃ−１
この方法では前方変数ｆ２　，ｆ３　，…，ｆｄｃは記憶されることが必要である。後方変数ｂｉ　が計算されるので、出力メッセージｗｋ　→ｉ　は同時に計算され、それによって後方変数の記憶の必要性をなくす。
【００４６】
次に説明するように、計算負荷はさらに並列方法により強化される。
【００４７】
図１３のＢは本発明の１実施形態にしたがって並列方法を使用してチェックノードとビットノードとの間の出力メッセージを計算するプロセスのフローチャートである。ｄｃ　の隣接するビットノードからの入力ｖｎ１→ｋ　，ｎ２→ｋ　，…，ｎｄｃ　→ｋ　を有するチェックノードｋでは、ステップ１３１１として以下のパラメータが計算される。
γｋ　＝ｇ（ｖｎ１→ｋ　，ｎ２→ｋ　，…，ｎｄｃ　→ｋ　）
ｇ（，…，）関数も以下のように表されることができることに注意する。
ｇ（ａ，ｂ）＝ｌｎ（（１＋ｅａ＋ｂ　）／（ｅａ　＋ｅｂ　））
ｇ（，…，）関数の帰納特性を使用して、以下の式が得られる。
【数５】
2004080753.tif 000007
したがって、ｗｋ　→ｎｊは以下の方法で解かれる。
【数６】
2004080753.tif 000008
先の式のｌｎ（．）は関数ｌｎ｜ｅｘ　−１｜を表している検索テーブルＬＵＴＸ　を使用して得られる（ステップ１３１３）。他の検索テーブルＬＵＴｆ　またはＬＵＴｇ　とは異なって、テーブルＬＵＴｘ　は量子化レベルと同数のエントリを必要とする可能性がある。一度γｋ　が得られると、ステップ１３１５で全てのｎｉ　に対するｗｋ　→ｎｉの計算が上記の式を使用して並列して行われる。
【００４８】
γｋ　の計算の待ち時間は有効にｌｏｇ２　（ｄｃ　）である。
【００４９】
図１４乃至１６は本発明の種々の実施形態にしたがって発生されたＬＤＰＣコードのシミュレーション結果を示したグラフである。特に、図１４乃至１５は高次の変調と、３／４（ＱＰＳＫ、１．４８５ビット／シンボル）、２／３（８−ＰＳＫ、１．９８０ビット／シンボル）、５／６（８−ＰＳＫ、２．４７４ビット／シンボル）のコードレートにおけるＬＤＰＣコードの特性を示している。
【００５０】
２つの通常の方法がチェックノードとビットノードとの間の相互接続を実現するために存在し、それぞれ（１）全体的な並列方法、（２）部分的な並列方法である。全体的な並列アーキテクチャでは、全てのノードとそれらの相互接続が物理的に構成される。このアーキテクチャの利点は速度である。
【００５１】
しかしながら、全体的な並列アーキテクチャは全てのノードとそれらの接続を実現するのに大きな複雑性を含む。それ故、全体的な並列アーキテクチャでは、より小さいブロックサイズが複雑性を減少するために必要とされる。その場合、同じクロック周波数では、スループットの減少と幾らかのＦＥＲの劣化対Ｅｓ／Ｎｏ性能の比例的な減少が結果として生じる。
【００５２】
ＬＤＰＣコードを構成する第２の方法は、ノードの総数のサブセットだけを物理的に実現し、コードの全ての“機能的”ノードを処理するために限定された数の“物理的”ノードだけを使用することである。ＬＤＰＣデコーダの動作は非常に簡単に行われることができ、並列に動作されることができるが、設計上のさらなる挑戦は、通信が“ランダムに”分配されたビットノードとチェックノード間で設定される方法の開発である。図３のデコーダ３０５　は、本発明の１実施形態によれば、この問題を表面的にランダムコードを実現するために構成された方法でメモリをアクセスすることにより解決する。この方法を図１７および１８に関して説明する。
【００５３】
図１７および１８は、本発明の１実施形態にしたがって、ＬＤＰＣコード化のランダム性を実現するために構成されたアクセスをサポートするように組織されているメモリの上部および下部エッジをそれぞれ示している。構成されたアクセスはパリティチェックマトリックスの発生に焦点を合わせることにより正確なランダムコードの性能に妥協せずに実現されることができる。通常、パリティチェックマトリックスはチェックノードとビットノードとの接続により特定されることができる。例えば、ビットノードは３９２のグループに分割される（３９２は例示の目的で与えられている）。さらに、例えば程度３の第１のビットノードに接続されるチェックノードがａ、ｂ、ｃの符号を付けられると仮定すると、第２のビットノードに接続されるチェックノードはａ＋ｐ、ｂ＋ｐ、ｃ＋ｐの符号を付けられ、第３のビットノードに接続されるチェックノードはａ＋２ｐ、ｂ＋２ｐ、ｃ＋２ｐの符号を付けられる。３９２のビットノードの次のグループでは、第１のビットノードに接続されるチェックノードはａ、ｂ、ｃとは異なり、そのためｐの適切な選択では、全てのチェックノードは同一の程度を有する。ランダムな検索がフリー定数（ｆｒｅｅ　ｃｏｎｓｔａｎｔ　）にわたって行われ、それによって結果的なＬＤＰＣコードはサイクル−４およびサイクル−６フリーである。
【００５４】
前述の構成はチェックノードおよびビットノード処理中にメモリアクセスを容易にする。２部分グラフのエッジの値はランダムアクセスメモリ（ＲＡＭ）のような記憶媒体に記憶されることができる。チェックノードおよびビットノード処理中の正確なランダムＬＤＰＣコードに対して、エッジの値はランダムな方法で１つずつアクセスされる必要があることに注意する。しかしながら、このようなアクセス方式は高いデータレートのアプリケーションでは非常に遅くなる。図１７および１８のＲＡＭは１つの方法によって１クロックサイクルの関連するエッジの大きいグループで組織され、したがってこれらの値は“共に”メモリに位置付けられる。実際には、正確なランダムコードでさえも、チェックノードのグループ（およびそれぞれのビットノード）では、関連するエッジはＲＡＭ中で相互に隣接して位置されることができるが、ビットノードのグループ（それぞれのチェックノード）に隣接する関連するエッジはＲＡＭ中にランダムに分散されることが観察される。それ故、本発明では“トゲザネス”（ｔｏｇｅｔｈｅｒｎｅｓｓ）はパリティチェックマトリックス自体の設計から生じる。即ち、チェックマトリックス設計はビットノードとチェックノードのグループの関連するエッジがＲＡＭ中で共に同時に位置されることを確実にする。
【００５５】
図１７および１８で見られるように、各ボックスはエッジの値を含んでおり、これは多数のビット（例えば６）である。エッジＲＡＭは本発明の１実施形態にしたがって２つの部分、即ち上部エッジＲＡＭ（図１７）と下部エッジＲＡＭ（図１８）に分割される。下部エッジＲＡＭは例えば程度２のビットノードとチェックノードとの間にエッジを含んでいる。上部エッジＲＡＭは２よりも大きい程度のビットノードとチェックノードとの間にエッジを含んでいる。それ故、チェックノード２毎に、隣接エッジは下部ＲＡＭに記憶され、残りのエッジは上部エッジＲＡＭに記憶される。
【００５６】
前述の例の説明を継続すると、３９２ビットノードと３９２チェックノードのグループは一度の処理で選択される。３９２チェックノード処理では、ｑの連続的な行が上部エッジＲＡＭからアクセスされ、２の連続的な行が下部エッジＲＡＭから選択される。この例では、ｑ＋２は各チェックノードの程度である。ビットノード処理では、３９２ビットノードのグループが程度２を有するならば、それらのエッジは下部エッジＲＡＭの２の連続的な行に位置される。ビットノードが程度ｄ＞２を有するならば、それらのエッジは上部エッジＲＡＭの幾つかのｄ行に位置される。これらのｄ行のアドレスは読取専用メモリ（ＲＯＭ）のような不揮発性メモリに記憶されることができる。１つの行のエッジは３９２ビットのノードの第１のエッジに対応し、別の行のエッジは３９２ビットのノードの第２のエッジに対応する。さらに各行では、３９２のグループの第１のビットノードに属すエッジの列インデックスもまたＲＯＭに記憶されることができる。第２、第３等のビットノードに対応するエッジは“ラップアラウンド”方法で開始列インデックスにしたがう。例えば行のｊ番目のエッジが第１のビットノードに属すならば、（ｊ＋１）番目のエッジは第２のビットノードに属し、（ｊ＋２）番目のエッジは第３のビットノードに属し、（ｊ−１）番目のエッジは第３９２のビットノードに属する。
【００５７】
（図１７および１８に示されている）前述の組織により、メモリアクセスの速度はＬＤＰＣコード化中に非常に強化される。
【００５８】
図１９は本発明にしたがって実施形態が構成されることができるコンピュータシステム１６００を示している。このコンピュータシステム１６００は情報を通信するためのバス１６０１またはその他の通信機構と、情報処理のためにバス１６０１に結合されたプロセッサ１６０３とを含んでいる。コンピュータシステム１６００はまたランダムアクセスメモリ（ＲＡＭ）等の主メモリ１６０５、またはプロセッサ１６０３により実行される情報および命令を記憶するためにバス１６０１に結合されている他のダイナミック記憶装置も含んでいる。主メモリ１６０５はまたプロセッサ１６０３により実行される命令を実行するときに一時的に変数または他の中間情報を記憶するために使用されることもできる。コンピュータシステム１６００はさらにプロセッサ１６０３の静止情報および命令を記憶するためにバス１６０１に結合される読取専用メモリ（ＲＯＭ）１６０７またはその他の静止記憶装置を含んでいる。磁気ディスクまたは光ディスク等の記憶装置１６０９はさらに情報および命令を記憶するためにバス１６０１へ結合される。
【００５９】
コンピュータシステム１６００は情報をコンピュータユーザへ表示するためにバス１６０１により、陰極線管（ＣＲＴ）、液晶ディスプレイ、アクチブマトリックスディスプレイ、またはプラズマディスプレイ等のディスプレイ１６１１へ結合されてもよい。文字数字および他のキーを含んでいるキーボードのような入力装置１６１３はプロセッサ１６０３へ情報およびコマンド選択を通信するためにバス１６０１へ結合されている。別のタイプのユーザ入力装置は指令情報およびコマンド選択をプロセッサ１６０３へ通信し、ディスプレイ１６１１上のカーソル移動を制御するためにマウス、トラックボール、またはカーソル指令キー等のカーソル制御装置１６１５である。
【００６０】
本発明の１実施形態にしたがって、ＬＤＰＣコードの発生は主メモリ１６０５中に含まれている命令の構成を実行するプロセッサ１６０３に応答してコンピュータシステム１６００により行われる。このような命令は別のコンピュータの読取可能な媒体から記憶装置１６０９のような主メモリ１６０５に読取られることができる。主メモリ１６０５中に含まれる命令の構成の実行はプロセッサ１６０３にここで説明されているプロセスステップを実行させる。多処理構成において１以上のプロセッサは主メモリ１６０５中に含まれている命令の実行に使用されてもよい。別の実施形態では、ハードワイヤ回路が本発明の実施形態を実行するためにソフトウェア命令の代わりにまたはそれと組合わせて使用されてもよい。したがって、本発明の実施形態はハードウェア回路のとソフトウェアの任意の特定の組合わせに限定されない。
【００６１】
コンピュータシステム１６００はバス１６０１に結合された通信インターフェース１６１７も含んでいる。通信インターフェース１６１７はローカルネットワーク１６２１に接続されるネットワークリンク１６１９に結合して２方向データ通信を行う。例えば通信インターフェース１６１７はデジタル加入者ライン（ＤＳＬ）カードまたはモデム、統合サービスデジタル網（ＩＳＤＮ）カード、ケーブルモデムまたはデータ通信接続を対応するタイプの電話線に行う電話機のモデムであってもよい。別の例として、通信インターフェース１６１７は互換性のあるＬＡＮに対してデータ通信接続を行うために（例えばイーサネット（商標名）または非同期転送モデル（ＡＴＭ）ネットワーク用の）構内ネットワーク（ＬＡＮ）カードであってもよい。無線リンクもまた構成されることができる。任意のこのような構成では、通信インターフェース１６１７は種々のタイプの情報を表すデジタルデータストリームを伝送する電気的、電磁的または光信号を送信し、受信する。さらに、通信インターフェース１６１７はユニバーサルシリアルバス（ＵＳＢ）インターフェース、ＰＣＭＣＩＡ（パーソナルコンピュータメモリカード国際協会）インターフェース等のような周辺インターフェース装置を含むことができる。
【００６２】
ネットワークリンク１６１９は典型的に１以上のネットワークを通してデータ通信を他のデータ装置へ提供する。例えばネットワークリンク１６１９はローカルネットワーク１６２１を通してホストコンピュータ１６２３への接続を行い、これはネットワーク１６２５（例えば広域網（ＷＡＮ）または“インターネット”として共通して呼ばれているグローバルパケットデータ通信ネットワーク）またはサービスプロバイダにより動作されるデータ装置への接続を行う。構内ネットワーク１６２１およびネットワーク１６２５の両者は情報および命令を伝播するために電気的、電磁的または光信号を使用する。種々のネットワークを通る信号およびネットワークリンク１６１９上および通信インターフェース１６１７を通る信号はデジタルデータをコンピュータシステム１６００により通信し、情報および命令を伝播する例示としては搬送波の形態である。
【００６３】
コンピュータシステム１６００は、ネットワーク、ネットワークリンク１６１９、通信インターフェース１６１７を通してメッセージを送信し、プログラムコードを含むデータを受信することができる。インターネットの例では、サーバ（図示せず）はネットワーク１６２５、構内ネットワーク１６２１、通信インターフェース１６１７を通して本発明の１実施形態を実行するためのアプリケーションプログラムに属すリクエストされたコードを送信する。プロセッサ１６０３は受信しながら送信されたコードを実行および／または後に実行するために記憶装置１６９　または他の不揮発性記憶装置に記憶する。この方法では、コンピュータシステム１６００は搬送波の形態のアプリケーションコードを獲得する。
【００６４】
用語“コンピュータの読取可能な媒体”はここで使用されるとき実行のためプロセッサ１６０３へ命令を与えることに関係する任意の媒体を示している。このような媒体は多くの形態を取り、不揮発性媒体、揮発性媒体、伝送媒体を含むがそれに限定されない。不揮発性媒体は、例えば記憶装置１６０９のような光学または磁気ディスクを含んでいる。揮発性媒体は主メモリ１６０５のようなダイナミックメモリを含んでいる。伝送媒体はバス１６０１を構成するワイヤを含めて、同軸ケーブル、銅線、または光ファイバを含んでいる。伝送媒体は無線周波数（ＲＦ）および赤外線（ＩＲ）データ通信中に発生されるような音響、光または電磁波の形態を取ることができる。コンピュータの読取可能な媒体の通常の形態は、例えばフロッピーディスク、フレキシブルディスク、ハードディスク、磁気テープ、任意の他の磁気媒体、ＣＤ−ＲＯＭ、ＣＤＲＷ、ＤＶＤ、任意の他の光媒体、パンチカード、ペーパーテープ、光マークシート、穴のパターンまたは他の光学的に認識可能な指標を有する任意の他の物理的媒体、ＲＡＭ、ＰＲＯＭ、ＥＰＲＯＭ、ＦＬＡＳＨ−ＥＰＲＯＭ、任意の他のメモリチップまたはカートリッジ、搬送波またはコンピュータが読取可能な任意の他の媒体を含んでいる。
【００６５】
コンピュータの読取可能な媒体の種々の形態は実行するための命令をプロセッサに与えることを含んでいる。例えば、本発明の最小部分を実行するための命令は最初は遠隔コンピュータの磁気ディスクに位置されてもよい。このようなシナリオでは、遠隔コンピュータは命令を主メモリにロードし、モデムを使用して電話線によって命令を送信する。ローカルコンピュータシステムのモデムは電話線でデータを受信し、赤外線送信機を使用してそのデータを赤外線信号に変換し、その赤外線信号をパーソナルデジタルアシスタンス（ＰＤＡ）およびラップトップのようなポータブルコンピュータ装置へ送信する。ポータブルコンピュータ装置の赤外線検出器は赤外線信号により伝送された情報および命令を受信し、そのデータをバスに供給する。バスはそのデータを主メモリに伝送し、そこからプロセッサは命令を検索し実行する。主メモリにより受信された命令はプロセッサによる実行される前または後に随意選択的に記憶装置に記憶される。
【００６６】
さらに、本発明の種々の実施形態はエンコーダおよびデコーダを簡単にするために構成された低密度パリティチェック（ＬＤＰＣ）コードを発生する方法を提供する。ＬＤＰＣコードの構造はパリティチェックマトリックスを低い三角形であるように限定することにより与えられる。また、（８−ＰＳＫ（位相シフトキーイング）のような）高次の変調コンステレーションのさらに脆弱なビットに対して特別のエラー保護を行うために、送信されたビットにＬＤＰＣコードの不均一なエラー保護能力を有効に使用することができる。復号プロセスは各デコーダ反復後または幾つかのデコーダ反復後にＬＤＰＣデコーダへ信号コンステレーションビットメトリックを反復的に再生することを含んでいる。前述の方法は性能を犠牲にせずに複雑性を有効に減少させる。
【００６７】
本発明を多くの実施形態および構成と共に説明したが、本発明はそれに限定されるものではなく、種々の明白な変形および均等な構成は特許請求の範囲に記載された本発明の技術的範囲内に含まれるべきものである。
【図面の簡単な説明】
【図１】低密度パリティチェック（ＬＤＰＣ）コードを使用するように構成された本発明の１実施形態の通信システムの図。
【図２】図１のシステムの例示的な送信機のブロック図。
【図３】図１のシステムの例示的な受信機のブロック図。
【図４】本発明の実施形態にしたがって疎であるパリティチェックマトリックスの概略図。
【図５】図４のマトリックスのＬＤＰＣコードの２部分グラフ。
【図６】本発明の１実施形態にしたがってサブマトリックスが低い三角形領域に限定されたパリティチェック値を含んでいる、疎であるパリティチェックマトリックスのサブマトリックスの概略図。
【図７】限定されていないパリティチェックマトリックス（Ｈマトリックス）と図６のサブマトリックスを有する限定されたＨマトリックスを使用するコードとの性能を示したグラフ。
【図８】それぞれ図１のシステムで使用されることができるグレーではない８−ＰＳＫ変調方式と、グレーの８−ＰＳＫ変調の説明図。
【図９】グレーのラベリング対グレーではないラベリングを使用するコード間の性能を示したグラフ。
【図１０】本発明の１実施形態にしたがってグレーではないマッピングを使用しているＬＤＰＣデコーダの動作のフローチャート。
【図１１】本発明の１実施形態にしたがってグレーのマッピングを使用している図３のＬＤＰＣデコーダの動作のフローチャート。
【図１２】本発明の１実施形態にしたがった復号プロセスにおけるチェックノードとビットノード間の相互動作の図。
【図１３】本発明の種々の実施形態にしたがって、それぞれ前方−後方方法と並列方法を使用してチェックノードとビットノード間の出力されたメッセージを計算するプロセスのフローチャート。
【図１４】本発明の種々の実施形態にしたがって発生されたＬＤＰＣコードのシミュレーション結果を示したグラフ。
【図１５】本発明の種々の実施形態にしたがって発生されたＬＤＰＣコードのシミュレーション結果を示したグラフ。
【図１６】本発明の種々の実施形態にしたがって発生されたＬＤＰＣコードのシミュレーション結果を示したグラフ。
【図１７】本発明の１実施形態にしたがって、ＬＤＰＣコード化のランダム性を実現するために構成されたアクセスをサポートするように組織されているメモリの上部エッジの図。
【図１８】本発明の１実施形態にしたがって、ＬＤＰＣコード化のランダム性を実現するために構成されたアクセスをサポートするように組織されているメモリの下部エッジの図。
【図１９】本発明の１実施形態にしたがって、ＬＤＰＣコードの符号化と復号化のプロセスを実行できるコンピュータシステムのブロック図。
【図１】
2004080753.tif 000009
【図２】
2004080753.tif 000010
【図３】
2004080753.tif 000011
【図４】
2004080753.tif 000012
【図５】
2004080753.tif 000013
【図６】
2004080753.tif 000014
【図７】
2004080753.tif 000015
【図８】
2004080753.tif 000016
【図９】
2004080753.tif 000017
【図１０】
2004080753.tif 000018
【図１１】
2004080753.tif 000019
【図１２】
2004080753.tif 000020
【図１３】
2004080753.tif 000021
【図１４】
2004080753.tif 000022
【図１５】
2004080753.tif 000023
【図１６】
2004080753.tif 000024
【図１７】
2004080753.tif 000025
【図１８】
2004080753.tif 000026
【図１９】
2004080753.tif 000027