(57)【要約】【課題】ショートフレーム長の低密度パリティチェック（ＬＤＰＣ）コードをエンコーディングするアプローチを提供する。【解決手段】エンコーダ（２０３）がアウタBose Chaudhuri Hocqenghem（ＢＣＨ）コードを有するＬＤＰＣコードを発生させる。パリティチェック行列の一部を低位三角に制限することにより、および／または他の要求を満足させることにより、構造がＬＤＰＣコードに課され、これによりデコーダ（３０５）のビットノードとチェックノードとの間の通信が簡単化される。さらに、巡回冗長検査（ＣＲＣ）エンコーダ（２０９）が提供され、ＣＲＣコードにしたがって入力信号がエンコードされる。このアプローチは衛星を通してのデジタルビデオブロードキャストサービスに特に適用を有する。【選択図】      図２Ａ
2005086824.tif 000002
【特許請求の範囲】
【請求項１】
低密度パリティチェック（ＬＤＰＣ）コード化信号の送信をサポートする方法において、
情報ビットを受信し、
ＬＤＰＣコード化信号として送信するために、テーブル１−１０のうちの１つにしたがって、情報ビットに基づき、低密度パリティチェック（ＬＤＰＣ）コードを発生させることを含み、
【表１】
2005086824.tif 000016
【表２】
2005086824.tif 000017
【表３】
2005086824.tif 000018
【表４】
2005086824.tif 000019
【表５】
2005086824.tif 000020
【表６】
2005086824.tif 000021
【表７】
2005086824.tif 000022
【表８】
2005086824.tif 000023
【表９】
2005086824.tif 000024
【表１０】
2005086824.tif 000025
テーブル１−１０のそれぞれはパリティビットアキュムレータのアドレスを特定する方法。
【請求項２】
ｇ（ｘ）＝（１＋ｘ＋ｘ3＋ｘ5＋ｘ14）×（１＋ｘ6＋ｘ8＋ｘ11＋ｘ14）×（１＋ｘ＋ｘ2＋ｘ6＋ｘ9＋ｘ10＋ｘ14）×（１＋ｘ4＋ｘ7＋ｘ8＋ｘ10＋ｘ12＋ｘ14）×（１＋ｘ2＋ｘ4＋ｘ6＋ｘ8＋ｘ9＋ｘ11＋ｘ13＋ｘ14）×（１＋ｘ3＋ｘ7＋ｘ8＋ｘ9＋ｘ13＋ｘ14）×（１＋ｘ2＋ｘ5＋ｘ6＋ｘ7＋ｘ10＋ｘ11＋ｘ13＋ｘ14）×（１＋ｘ5＋ｘ8＋ｘ9＋ｘ10＋ｘ11＋ｘ14）×（１＋ｘ＋ｘ2＋ｘ3＋ｘ9＋ｘ10＋ｘ14）×（１＋ｘ3＋ｘ6＋ｘ9＋ｘ11＋ｘ12＋ｘ14）×（１＋ｘ4＋ｘ11＋ｘ12＋ｘ14）×（１＋ｘ＋ｘ2＋ｘ3＋ｘ5＋ｘ6＋ｘ7＋ｘ8＋ｘ10＋ｘ13＋ｘ14）の生成多項式に基づいて、Bose Chaudhuri Hocqenghem（ＢＣＨ）アウタコードが使用される請求項１記載の方法。
【請求項３】
ＬＤＰＣコード化信号を変調し、
変調信号を送信することをさらに含む請求項１記載の方法。
【請求項４】
変調信号はブロードバンド衛星アプリケーションのサポートで衛星リンク（１０３）を通して送信される請求項３記載の方法。
【請求項５】
変調ステップは、８−ＰＳＫ（位相偏移変調）、１６−ＱＡＭ（直交振幅変調）、ＱＰＳＫ（４相位相偏移変調）、１６−ＡＰＳＫ（振幅位相偏移変調）および３２−ＡＰＳＫのうちの１つを含む信号配列にしたがって実行される請求項３記載の方法。
【請求項６】
低密度パリティチェック（ＬＤＰＣ）コード化信号の送信をサポートするための命令を記憶しているコンピュータ読み取り可能な媒体において、
前記命令は、実行時に１つ以上のプロセッサに請求項１記載の方法を実行させるように構成されている媒体。
【請求項７】
低密度パリティチェック（ＬＤＰＣ）コード化信号の送信をサポートするエンコーダ（２０３）において、
情報ビットを受信する手段と、
ＬＤＰＣコード化信号として送信するために、テーブル１−１０のうちの１つにしたがって、情報ビットに基づき、低密度パリティチェック（ＬＤＰＣ）コードを発生させる手段とを具備し、
【表１１】
2005086824.tif 000026
【表１２】
2005086824.tif 000027
【表１３】
2005086824.tif 000028
【表１４】
2005086824.tif 000029
【表１５】
2005086824.tif 000030
【表１６】
2005086824.tif 000031
【表１７】
2005086824.tif 000032
【表１８】
2005086824.tif 000033
【表１９】
2005086824.tif 000034
【表２０】
2005086824.tif 000035
テーブル１−１０のそれぞれはパリティビットアキュムレータのアドレスを特定するエンコーダ。
【請求項８】
Bose Chaudhuri Hocqenghem（ＢＣＨ）アウタコードがｇ（ｘ）＝（１＋ｘ＋ｘ3＋ｘ5＋ｘ14）×（１＋ｘ6＋ｘ8＋ｘ11＋ｘ14）×（１＋ｘ＋ｘ2＋ｘ6＋ｘ9＋ｘ10＋ｘ14）×（１＋ｘ4＋ｘ7＋ｘ8＋ｘ10＋ｘ12＋ｘ14）×（１＋ｘ2＋ｘ4＋ｘ6＋ｘ8＋ｘ9＋ｘ11＋ｘ13＋ｘ14）×（１＋ｘ3＋ｘ7＋ｘ8＋ｘ9＋ｘ13＋ｘ14）×（１＋ｘ2＋ｘ5＋ｘ6＋ｘ7＋ｘ10＋ｘ11＋ｘ13＋ｘ14）×（１＋ｘ5＋ｘ8＋ｘ9＋ｘ10＋ｘ11＋ｘ14）×（１＋ｘ＋ｘ2＋ｘ3＋ｘ9＋ｘ10＋ｘ14）×（１＋ｘ3＋ｘ6＋ｘ9＋ｘ11＋ｘ12＋ｘ14）×（１＋ｘ4＋ｘ11＋ｘ12＋ｘ14）×（１＋ｘ＋ｘ2＋ｘ3＋ｘ5＋ｘ6＋ｘ7＋ｘ8＋ｘ10＋ｘ13＋ｘ14）の生成多項式に基づいている請求項７記載のエンコーダ（２０３，２１１）。
【請求項９】
ＬＤＰＣコード化信号を変調する手段と、
変調信号を送信する手段とをさらに具備する請求項７記載のエンコーダ（２０３，２１１）。
【請求項１０】
変調信号はブロードバンド衛星アプリケーションのサポートで衛星リンク（１０３）を通して送信される請求項９記載のエンコーダ（２０３，２１１）。
【請求項１１】
変調ステップは、８−ＰＳＫ（位相偏移変調）、１６−ＱＡＭ（直交振幅変調）、ＱＰＳＫ（４相位相偏移変調）、１６−ＡＰＳＫ（振幅位相偏移変調）および３２−ＡＰＳＫのうちの１つを含む信号配列にしたがって実行される請求項９記載のエンコーダ（２０３，２１１）。
【請求項１２】
低密度パリティチェック（ＬＤＰＣ）コード化信号の送信をサポートする送信機（２００）において、
情報ビットを受信するように構成されたBose Chaudhuri Hocqenghem（ＢＣＨ）エンコーダ（２１１）と、
ＢＣＨエンコーダ（２１１）に結合され、ＬＤＰＣコード化信号として送信するために、テーブル１−１０のうちの１つにしたがって、情報ビットに基づき、アウタＢＣＨコードを有する低密度パリティチェック（ＬＤＰＣ）コードを出力するＬＤＰＣエンコーダ（２０３）とを具備し、
【表２１】
2005086824.tif 000036
【表２２】
2005086824.tif 000037
【表２３】
2005086824.tif 000038
【表２４】
2005086824.tif 000039
【表２５】
2005086824.tif 000040
【表２６】
2005086824.tif 000041
【表２７】
2005086824.tif 000042
【表２８】
2005086824.tif 000043
【表２９】
2005086824.tif 000044
【表３０】
2005086824.tif 000045
テーブル１−１０のそれぞれはパリティビットアキュムレータのアドレスを特定する送信機。
【請求項１３】
ＢＣＨアウタコードがｇ（ｘ）＝（１＋ｘ＋ｘ3＋ｘ5＋ｘ14）×（１＋ｘ6＋ｘ8＋ｘ11＋ｘ14）×（１＋ｘ＋ｘ2＋ｘ6＋ｘ9＋ｘ10＋ｘ14）×（１＋ｘ4＋ｘ7＋ｘ8＋ｘ10＋ｘ12＋ｘ14）×（１＋ｘ2＋ｘ4＋ｘ6＋ｘ8＋ｘ9＋ｘ11＋ｘ13＋ｘ14）×（１＋ｘ3＋ｘ7＋ｘ8＋ｘ9＋ｘ13＋ｘ14）×（１＋ｘ2＋ｘ5＋ｘ6＋ｘ7＋ｘ10＋ｘ11＋ｘ13＋ｘ14）×（１＋ｘ5＋ｘ8＋ｘ9＋ｘ10＋ｘ11＋ｘ14）×（１＋ｘ＋ｘ2＋ｘ3＋ｘ9＋ｘ10＋ｘ14）×（１＋ｘ3＋ｘ6＋ｘ9＋ｘ11＋ｘ12＋ｘ14）×（１＋ｘ4＋ｘ11＋ｘ12＋ｘ14）×（１＋ｘ＋ｘ2＋ｘ3＋ｘ5＋ｘ6＋ｘ7＋ｘ8＋ｘ10＋ｘ13＋ｘ14）の生成多項式に基づいている請求項１２記載の送信機（２００）。
【請求項１４】
ＬＤＰＣコード化信号を変調するように構成された変調器（２０５）をさらに具備する請求項１２記載の送信機（２００）。
【請求項１５】
変調信号はブロードバンド衛星アプリケーションのサポートで衛星リンク（１０３）を通して送信される請求項１４記載の送信機（２００）。
【請求項１６】
変調ステップは、８−ＰＳＫ（位相偏移変調）、１６−ＱＡＭ（直交振幅変調）、ＱＰＳＫ（４相位相偏移変調）、１６−ＡＰＳＫ（振幅位相偏移変調）および３２−ＡＰＳＫのうちの１つを含む信号配列にしたがって実行される請求項１４記載の送信機（２００）。
【発明の詳細な説明】
【発明の分野】
【０００１】
本発明は通信システムに関し、特に、コード化システムに関する。
【発明の背景】
【０００２】
通信システムはコーディングを使用して雑音のある通信チャネルに渡る信頼性ある通信を確実に行う。例えば、衛星ネットワークのようなワイヤレス（または無線）システムでは、地理的および環境的要因からの雑音源が多い。これらの通信チャネルは固定容量を表し、これはある信号対雑音比（ＳＮＲ）におけるシンボル当たりのビットに関して表すことができ、（シャノン限界として知られる）理論的上限を規定する。結果として、コーディング設計はこのシャノン限界に近づくレートを達成することを目的としている。この目的は、帯域幅制約衛星システムに対して特に密接な関係がある。シャノン限界に近づくこのようなクラスのコードの１つは低密度パリティチェック（ＬＤＰＣ）コードである。
【０００３】
従来、ＬＤＰＣコードは多くの欠点があることから、幅広く採用されていなかった。１つの欠点はＬＤＰＣエンコーディング技術が非常に複雑であることである。その生成行列を使用してＬＤＰＣコードをエンコードするには、非常に大きな非希薄行列を記憶することが必要である。さらに、ＬＤＰＣコードは大きなブロックが効率的であることを必要とし、結果的に、ＬＤＰＣコードのパリティチェック行例が希薄であっても、これらの行列の記憶が問題である。
【０００４】
実現の将来的な見通しから、多数の難題に直面する。例えば、記憶装置はＬＤＰＣコードが実際には広まっていない重要な理由である。したがって、長いＬＤＰＣコードはより大きな記憶空間を要求する。また、ＬＤＰＣコード実現における主な難題はデコーダ中のいくつかの処理エンジン（ノード）間で接続ネットワークをどのように達成するかである。さらに、デコーディングプロセス、特にチェックノード動作における計算負荷は問題を生じる。
【０００５】
したがって、簡単なエンコーディングおよびデコーディングプロセスを使用するＬＤＰＣ通信システムに対する必要性がある。より複雑さを持ち込むことなく、ＬＤＰＣコードを使用して高データレートを効率的にサポートする必要性がある。ＬＤＰＣエンコーダおよびデコーダの性能を向上させる必要性もある。ＬＤＰＣコーディングを実現するための記憶要求を最小にする必要性もある。
【発明の開示】
【発明の概要】
【０００６】
これらおよび他の必要性は本発明により取り扱われる。ここで、ショートブロック長の低密度パリティチェック（ＬＤＰＣ）コードをエンコーディングするアプローチが提供される。エンコーダは、ＬＤＰＣコード化信号として送信するために、テーブル１−７の１つにしたがって、アウタBose Chaudhuri Hocqenghem（ＢＣＨ）コードを有するＬＤＰＣコードを発生させる。テーブル１−７のそれぞれはパリティビットアキュムレータのアドレスを特定する。パリティチェック行列の一部を低位三角に制限することにより、および／または他の要求を満足させることにより、構造がＬＤＰＣコードに課され、これによりデコーダのビットノードとチェックノードとの間の通信が簡単化される。さらに、巡回冗長検査（ＣＲＣ）エンコーダが提供され、ＣＲＣコードにしたがって入力信号がエンコードされる。このアプローチはＬＤＰＣコードの好都合なエンコーディングとともにデコーディングを有効に提供する一方で、記憶および処理リソースを最小にする。
【０００７】
本発明の実施形態の他の観点にしたがうと、ＬＤＰＣコードは、８−ＰＳＫ（位相偏移変調）、１６−ＱＡＭ（直交振幅変調）、ＱＰＳＫ（４相位相偏移変調）、１６−ＡＰＳＫ（振幅位相偏移変調）および３２−ＡＰＳＫのうちの１つを含む信号配列にしたがって変調される信号により表される。
【０００８】
本発明の実施形態の他の観点にしたがうと、変調されたＬＤＰＣコード化信号はブロードバンド衛星アプリケーションのサポートで衛星リンクを通して送信される。
【０００９】
本発明の実施形態のさらに別の観点にしたがうと、ＢＣＨアウタコードはｇ（ｘ）＝（１＋ｘ＋ｘ3＋ｘ5＋ｘ14）×（１＋ｘ6＋ｘ8＋ｘ11＋ｘ14）×（１＋ｘ＋ｘ2＋ｘ6＋ｘ9＋ｘ10＋ｘ14）×（１＋ｘ4＋ｘ7＋ｘ8＋ｘ10＋ｘ12＋ｘ14）×（１＋ｘ2＋ｘ4＋ｘ6＋ｘ8＋ｘ9＋ｘ11＋ｘ13＋ｘ14）×（１＋ｘ3＋ｘ7＋ｘ8＋ｘ9＋ｘ13＋ｘ14）×（１＋ｘ2＋ｘ5＋ｘ6＋ｘ7＋ｘ10＋ｘ11＋ｘ13＋ｘ14）×（１＋ｘ5＋ｘ8＋ｘ9＋ｘ10＋ｘ11＋ｘ14）×（１＋ｘ＋ｘ2＋ｘ3＋ｘ9＋ｘ10＋ｘ14）×（１＋ｘ3＋ｘ6＋ｘ9＋ｘ11＋ｘ12＋ｘ14）×（１＋ｘ4＋ｘ11＋ｘ12＋ｘ14）×（１＋ｘ＋ｘ2＋ｘ3＋ｘ5＋ｘ6＋ｘ7＋ｘ8＋ｘ10＋ｘ13＋ｘ14）の生成多項式に基づいている。
【００１０】
本発明のさらに他の観点、特徴および利点は、本発明を実施するために意図される最良の態様を含む、数多くの特定の実施形態および実施を単に例示することにより、以下の詳細の説明から容易に明らかになる。本発明は他のおよび異なる実施形態を行うこともでき、そのいくつかの詳細はすべて本発明の精神および範囲を逸脱することなく、さまざまな明白な点で修正できる。したがって、図面および説明は本質的に例証であると見なされるべきであり、限定的と見なされてはならない。
【００１１】
本発明は添付図面の図中に制限としてではなく例証として描かれ、図面において同じ参照番号は類似するエレメントに関係する。
【好ましい実施形態の説明】
【００１２】
ショートフレーム長の低密度パリティチェック（ＬＤＰＣ）コードを効率的にエンコーディングするシステム、方法およびソフトウェアを説明する。以下の説明においては、説明の目的のために、本発明の完全な理解を提供するため、多数の特定な詳細が述べられている。しかしながら、本発明がこれらの特定な詳細なしに、あるいは均等な構成で実現されてもよいことは当業者にとっては明らかである。他の例では、周知の構造およびデバイスは本発明を不必要に曖昧にするのを避けるためにブロック図で示されている。
【００１３】
図１は本発明の実施形態にしたがった、低密度パリティチェック（ＬＤＰＣ）コードを利用するように構成された通信システムの図である。デジタル通信システム１００は送信機１０１を含み、この送信機１０１は通信チャネル１０３を通して受信機１０５に向かう信号波形を発生させる。このディスクリート通信システム１００では、送信機１０１はディスクリートセットの可能性あるメッセージを生成するメッセージ源を有し、それぞれの可能性あるメッセージは対応する信号波形を持つ。これらの信号波形は通信チャネル１０３により、減衰され、そうでなければ変更される。雑音チャネル１０３と戦うためにＬＤＰＣコードが利用される。
【００１４】
例として、チャネル１０３はブロードバンド衛星アプリケーションのサポートで衛星ターミナル（例えば非常に小型の開口ターミナル（ＶＳＡＴ））の役に立つ衛星リンクである。このようなアプリケーションには衛星ブロードキャスティングおよびインターラクティブサービス（およびデジタルビデオブロードキャスト（ＤＶＢ）−Ｓ２標準規格に準拠する）が含まれる。衛星を通してのデジタルビデオブロードキャスティング（ＤＶＢ−Ｓ）標準規格は世界中で幅広く採用されており、例えばデジタル衛星テレビ番組を提供している。
【００１５】
送信機１０１により発生されるＬＤＰＣコードは何らかの性能損失を生じさせることなく高速な構成を可能にする。送信機１０１から出力されるこのように構成されたＬＤＰＣコードは、変調スキーム（例えば８−ＰＳＫ）によりチャネルエラーに既に弱いビットノードに対してわずかな数のチェックノードを割り当てることを避ける。
【００１６】
このようなＬＤＰＣコードは（ターボコードと異なり）並列可能なデコーディングアルゴリズムを持ち、これは加算、比較およびテーブルルックアップのような簡単な動作を伴う効果がある。さらに、慎重に設計されたＬＤＰＣコードはエラーフロアーの兆候を何ら示さない。
【００１７】
本発明の１つの実施形態にしたがうと、送信機１０１は比較的に簡単なエンコーディング技術を使用して、（デコーディング中に効率的なメモリアクセスを促進する）パリティチェック行列に基づいてＬＤＰＣコードを発生させ、受信機１０５と通信する。送信機１０１はＬＤＰＣコードを使用し、ブロック長が十分に長ければ、ＬＤＰＣコードは連結ターボ＋ＲＳ（リードソロモン）コードより性能が優れる場合がある。
【００１８】
図２Ａおよび図２Ｂは図１の送信機に配置される例示的なＬＤＰＣエンコーダの図である。図２Ａに見られるように、送信機２００にはＬＤＰＣエンコーダ２０３が設けられ、ＬＤＰＣエンコーダ２０３は情報源２０１からの入力を受け入れ、受信機１０５におけるエラー訂正処理に適切なより高い冗長性のコード化ストリームを出力する。情報源２０１は、離散アルファベットＸからｋ個の信号を発生させる。ＬＤＰＣコードはパリティチェック行列で特定される。他方、ＬＤＰＣコードをエンコーディングするには、一般的には生成行列を特定することが必要になる。ガウス消去法を使用してパリティチェック行列から生成行列を得ることが可能であるが、結果として得られる行列はもはや希薄でなく、大きな生成行列を記憶することは複雑となる可能性がある。
【００１９】
エンコーダ２０３は、簡単なエンコーディング技術を使用して、変調器２０５に対する信号をアルファベットＹから発生させ、この簡単なエンコーディング技術は構造をパリティチェック行列に課すことによりパリティチェック行列のみ使用する。特に、行列のある部分を三角形に制約することによりパリティチェック行列に制限がおかれる。このようなパリティチェック行列の構造は図６で以下にさらに完全に説明する。このような制限は無視しうる性能損失となり、したがって魅力的なトレードオフとなる。
【００２０】
変調器２０５はエンコーダ２０３からのエンコード化メッセージを信号波形にマッピングし、この信号波形は送信アンテナ２０７に送られ、送信アンテナ２０７はこれらの波形を送信チャネル１０３を通して放射する。したがって、エンコード化メッセージは変調され、送信アンテナ２０７に配信される。以下で説明するように、送信アンテナ２０７からの送信は（図３に示されている）受信機に伝搬する。
【００２１】
図２Ｂは、本発明の１つの実施形態にしたがった、Bose Chaudhuri Hocqenghem（ＢＣＨ）エンコーダと巡回冗長検査（ＣＲＣ）エンコーダとともに利用されるＬＤＰＣエンコーダを示している。このシナリオのもとでは、ＣＲＣエンコーダ２０９とＢＣＨエンコーダ２１１とともに、ＬＤＰＣエンコーダ２０３により発生されるコードは連結されたアウタＢＣＨコードおよびインナ低密度パリティチェック（ＬＤＰＣ）コードを有する。さらに、エラー検出は巡回冗長検査（ＣＲＣ）コードを使用して達成される。例示的な実施形態におけるＣＲＣエンコーダ２０９は、生成多項式（Ｘ5＋Ｘ4＋Ｘ3＋Ｘ2＋１）（Ｘ2＋Ｘ＋１）（Ｘ＋１）を有する８ビットＣＲＣコードを使用してエンコードする。ＣＲＣコードはＢＣＨエンコーダ２１１に出力される。
【００２２】
図２Ｃは、本発明の１つの実施形態にしたがった、ショートフレーム長ＬＤＰＣコードを発生させるための図２ＢのＬＤＰＣエンコーダのエンコーディングプロセスのフローチャートである。ステップ２１１において、情報ビットが受信され、エンコーダ２０９、２１１および２０３のチェーンにおいて処理される。結果的に、ステップ２２３において、ＬＤＰＣエンコーダ２０３は受信情報ビットに基づいてアウタＢＣＨコードを有するＬＤＰＣコードを発生させる。コードはＣＲＣコードも含む。次に、ＬＤＰＣコードは信号により表され、この信号はチャネル１０３を通しての送信のために、ステップ２２５により変調され、チャネル１０３は例示的な実施形態では、１つ以上の衛星ターミナルに対する衛星リンクである（ステップ２２７）。
【００２３】
ＬＤＰＣエンコーダ２０３はサイズｋldpc、ｉ＝（ｉ0，ｉ1，…，ｉKldpc-1）の情報ブロックをサイズｎldpc、ｃ＝（ｉ0，ｉ1，…，ｉKldpc-1，ｐ0，ｐ1，…，ｐnldpc-Kldpc-1）のコードワードにシステマティックにエンコードする。コードワードの送信は所定の順でｉ0から開始し、ｐnldpc-Kldpc-1で終了する。
【００２４】
ＬＤＰＣエンコーダ２０３のタスクはｋldpc情報ビットの各ブロック（ｉ0，ｉ1，…，ｉKldpc-1）に対して、ｎldpc−ｋldpcパリティビット（ｐ0，ｐ1，…，ｐnldpc-Kldpc-1）を決定することである。手順は次の通りである。最初に、パリティビットが初期化される。ｐ0＝ｐ1＝ｐ2＝…＝ｐnldpc-Kldpc-1＝０。第１の情報ビットｉ0はテーブル１−７の第１行で特定されるパリティビットアドレスにおいて累積される。例として、ｋldpcビットはシステマティックにエンコードされ、ｎldpcビットが発生される。本発明の１つの実施形態にしたがうと、ｎldpcは１６２００ビットであり、これはショートブロック長である。比較的短い長さのこのようなコードの場合、約１６２００ビット以下の長さを有するＬＤＰＣコードは“ショート”ブロック長コードと考えられる。本発明の１つの実施形態にしたがった、ショートフレーム長コードのパラメータがテーブル８に提供されている。
【００２５】
すべての情報ビットが使い尽くされた後に、最終パリティビットは次の通りに得られる。最初に、ｉ＝１で開始して、以下の演算が実行される。
【００２６】
【数１】
2005086824.tif 000003
【００２７】
ｐi，ｉ＝０，１，…，ｎldpc−ｋldpc−１の最終内容はパリティビットｐiに等しい。
【００２８】
【表３１】
2005086824.tif 000004
【００２９】
【表３２】
2005086824.tif 000005
【００３０】
【表３３】
2005086824.tif 000006
【００３１】
【表３４】
2005086824.tif 000007
【００３２】
【表３５】
2005086824.tif 000008
【００３３】
【表３６】
2005086824.tif 000009
【００３４】
【表３７】
2005086824.tif 000010
【００３５】
【表３８】
2005086824.tif 000011
【００３６】
【表３９】
2005086824.tif 000012
【００３７】
【表４０】
2005086824.tif 000013
【００３８】
すべての情報ビットが使い尽くされた後に、最終パリティビットは次の通りに得られる。最初に、ｉ＝１で開始して、以下の演算が実行される。
【００３９】
【数２】
2005086824.tif 000014
【００４０】
ｐi，ｉ＝０，１，…，ｎldpc−ｋldpc−１の最終内容はパリティビットｐiに等しい。
【００４１】
ＢＣＨエンコーダ２１１に関して、ＢＣＨコードパラメータはテーブル１１に列挙されており、ｎldpcは１６２００に等しい。
【００４２】
【表４１】
2005086824.tif 000015
【００４３】
ＢＣＨエンコーダ２１１により利用されるＢＣＨコードの生成多項式は次の通りである。
【００４４】
ｇ（ｘ）＝（１＋ｘ＋ｘ3＋ｘ5＋ｘ14）×（１＋ｘ6＋ｘ8＋ｘ11＋ｘ14）×（１＋ｘ＋ｘ2＋ｘ6＋ｘ9＋ｘ10＋ｘ14）×（１＋ｘ4＋ｘ7＋ｘ8＋ｘ10＋ｘ12＋ｘ14）×（１＋ｘ2＋ｘ4＋ｘ6＋ｘ8＋ｘ9＋ｘ11＋ｘ13＋ｘ14）×（１＋ｘ3＋ｘ7＋ｘ8＋ｘ9＋ｘ13＋ｘ14）×（１＋ｘ2＋ｘ5＋ｘ6＋ｘ7＋ｘ10＋ｘ11＋ｘ13＋ｘ14）×（１＋ｘ5＋ｘ8＋ｘ9＋ｘ10＋ｘ11＋ｘ14）×（１＋ｘ＋ｘ2＋ｘ3＋ｘ9＋ｘ10＋ｘ14）×（１＋ｘ3＋ｘ6＋ｘ9＋ｘ11＋ｘ12＋ｘ14）×（１＋ｘ4＋ｘ11＋ｘ12＋ｘ14）×（１＋ｘ＋ｘ2＋ｘ3＋ｘ5＋ｘ6＋ｘ7＋ｘ8＋ｘ10＋ｘ13＋ｘ14）。
【００４５】
情報ビットｍ＝（ｍkbch-1，ｍkbch-2，…，ｍ1，ｍ0）のコードワードｃ＝（ｍkbch-1，ｍkbch-2，…，ｍ1，ｍ0，ｄnbch-kbch-1，ｄnbch-kbch-2，…，ｄ1，ｄ0）へのＢＣＨエンコーディングは以下の通りに達成される。メッセージ多項式ｍ（ｘ）＝ｍkbch-1ｘkbch-1＋ｍkbch-2ｘkbch-2＋…＋ｍ1ｘ＋ｍ0はｘnbch-kbchにより乗算される。次に、ｘnbch-kbchｍ（ｘ）はｇ（ｘ）により除算される。剰余としてのｄ（ｘ）＝ｄnbch-kbch-1ｘnbch-kbch-1＋…＋d1ｘ＋d0により、コードワード多項式は以下の通りにセットされる。ｃ（ｘ）＝ｘnbch-kbchｍ（ｘ）＋ｄ（ｘ）。
【００４６】
先に言及したように、例示的な実施形態では、ＭＰＥＧ（モーションピクチャエキスパートグループ）パケット送信のような、さまざまなデジタルビデオアプリケーションに対して、先のＬＤＰＣコードを使用することができる。
【００４７】
図３は図１のシステムにおける例示的な受信機の図である。受信側では、受信機３００には復調器３０１が含まれ、復調器３０１は送信機２００からの受信信号の復調を行う。これらの信号は復調のために受信アンテナ３０３において受信される。復調後、受信信号はデコーダ３０５に転送され、デコーダ３０５はビットメトリック発生器３０７とともに、メッセージＸ’を発生させることによりオリジナルソースメッセージを再構成しようと試行する。ビットメトリック発生器３０７は、デコーディングプロセス中にデコーダ３０５と行ったり来たり（反復的に）情報を交換してもよい。これらのデコーディングアプローチは２００３年７月３日に出願された“低密度パリティチェック（ＬＤＰＣ）デコーダにおけるルーティングのための方法およびシステム”と題する同時継続中の出願（シリアル番号１０／６１３，８２４号；代理人ドケットＰＤ−２０３００９）でさらに完全に説明されており、この出願はここでその全体が組み込まれている。本発明により提供される利点を理解するために、図４で説明されているように、どのようにしてＬＤＰＣコードが発生されるかを調べることが有効である。
【００４８】
図４は本発明の実施形態にしたがった、希薄パリティチェック行列の図である。ＬＤＰＣコードは希薄パリティチェック行列Ｈ(n-k)xnを有する長い線形ブロックコードである。一般的に、ブロック長ｎは数千から数万ビットの範囲をとる。例えば、長さｎ＝８およびレート１／２のＬＤＰＣコードに対するパリティチェック行列が図４に示されている。同じコードは図５に関して２部グラフにより等価的に表すことができる。
【００４９】
図５は図４の行列のＬＤＰＣコードに対する２部グラフの図である。パリティチェック式は、各チェックノードについて、すべての隣接ビットノードの（ＧＦ（ガロア域）（２）に対する）合計が０に等しくなることを意味する。図に見られるように、ビットノードはグラフの左側を占め、予め定められた関係にしたがって、１つ以上のチェックノードと関係している。例えば、チェックノードｍ1に対応して、以下の表現ｎ1＋ｎ4＋ｎ5＋ｎ8＝０がビットノードに関して存在する。
【００５０】
受信機３０３に戻ると、ＬＤＰＣデコーダ３０５はメッセージ通過デコーダとして考えられ、それによりデコーダ３０５はビットノードの値を発見することを目的としている。このタスクを達成するために、ビットノードとチェックノードは互いに繰り返し通信する。この通信の性質を以下に説明する。
【００５１】
チェックノードからビットノードについては、各チェックノードは隣接ビットノードに対して、他の隣接ビットノードから来る情報に基づいてそのビットノードの値と考えられる推定値（“オピニオン”）を提供する。例えば、先の例において、ｎ4、ｎ5およびｎ8の合計がｍ1にとって０の“ように見える”場合には、ｍ1はｎ1に対してｎ1の値は０であると思うことを示し（なぜならｎ1＋ｎ4＋ｎ5＋ｎ8＝０）、そうでなければ、ｍ1はｎ1に対して、ｎ1の値は１であると思えることを示す。さらに、軟判定デコーディングに対して、信頼性の尺度が加えられる。
【００５２】
ビットノードからチェックノードについては、各ビットノードは隣接チェックノードに対して、それの他の隣接チェックノードから来るフィードバックに基づいてそれ自体の値についての推定値を中継する。先の例では、ｎ1は２つの隣接チェックノードｍ1およびｍ3のみを有する。ｍ3から来るｎ1へのフィードバックが、ｎ1の値がおそらく０であることを示す場合には、ｎ1はｎ1自体の値の推定値は０であることをｍ1に通知する。ビットノードが２つより多い隣接チェックノードを持つケースでは、ビットノードは、それと通信しているチェックノードに対して判定を報告する前に、それの他の隣接チェックノードから来るフィードバックにおいて多数決（軟判定）を実行する。先のプロセスはすべてのビットノードが正しい（すなわち、すべてのパリティチェック式が満たされる）と考えられるまで、あるいは予め定められた最大数の反復に達して、それによりデコーディングの失敗が宣言されるまで繰り返される。
【００５３】
図６は本発明の実施形態にしたがった、希薄パリティチェック行列の部分行列の図である。部分行列は低位三角領域に制限されたパリティチェック値を含む。先に説明したように、（図２Ａおよび図２Ｂの）エンコーダ２０３は、パリティチェック行列の低位三角領域の値を制限することにより、簡単なエンコーディング技術を使用することができる。本発明の実施形態にしたがうと、パリティチェック行列に課される制限は次の形態をとる。
【００５４】
Ｈ(n-k)xn＝［Ａ(n-k)xkＢ(n-k)x(n-k)］
ここで、Ｂは低位三角行列である。
【００５５】
任意の情報ブロックｉ＝（ｉ0，ｉ1，…，ｉk-1）がＨcT＝０を使用して、コードワードｃ＝（ｉ0，ｉ1，…，ｉk-1，ｐ0，ｐ1，…，ｐn-k-1）にエンコードされ、パリティビットに対して帰納的に解く。例えば、
ａ00ｉ0＋ａ01ｉ1＋…＋ａ0,k-1ｉk-1＋ｐ0＝０→ｐ0を解き、
ａ10ｉ0＋ａ11ｉ1＋…＋ａ1,k-1ｉk-1＋ｂ10ｐ0＋ｐ1＝０→ｐ1を解き、
ｐ2，ｐ3，…，ｐn-k-1に対して同様である。
【００５６】
図７は本発明にしたがった実施形態を実現することができるコンピュータシステムを図示している。コンピュータシステム７００は、バス７０１または情報を通信する他の通信メカニズムと、バス７０１に結合され、情報を処理するプロセッサ７０３とを含む。コンピュータシステム７００は、バス７０１に結合され、情報およびプロセッサ７０３により実行されるべき命令を記憶する、ランダムアクセスメモリ（ＲＡＭ）または他の動的記憶デバイスのような、メインメモリ７０５も含む。メインメモリ７０５は、プロセッサ７０３により実行されるべき命令を実行中に、一時的な変数や他の中間的な情報を記憶するのにも使用することができる。コンピュータシステム７００は、バス７０１に結合され、プロセッサ７０３のために静的情報および命令を記憶するリードオンリーメモリ（ＲＯＭ）７０７や他の静的記憶デバイスをさらに含む。磁気ディスクや光学ディスクのような記憶デバイス７０９は、情報および命令を記憶するためにバス７０１に付加的に結合される。
【００５７】
コンピュータシステム７００は、情報をコンピュータユーザに表示するために、陰極線管（ＣＲＴ）、液晶ディスプレイ、アクティブマトリクスディスプレイ、またはプラズマディスプレイのような、ディスプレイ７１１にバス７０１を介して結合されてもよい。英数字および他のキーを含むキーボードのような入力デバイス７１３は情報およびコマンド選択をプロセッサ７０３に通信するためにバス７０１に結合される。他のタイプのユーザ入力デバイスは、方向情報およびコマンド選択をプロセッサ７０３に通信し、ディスプレイ７１１上のカーソルの動きを制御するための、マウス、トラックボール、またはカーソル方向キーのようなカーソル制御７１５である。
【００５８】
本発明の１つの実施形態にしたがうと、ＬＤＰＣコードの発生はメインメモリ７０５に含まれている命令の配列を実行するプロセッサ７０３に応答して、コンピュータシステム７００により提供される。このような命令は、記憶デバイス７０９のような他のコンピュータ読み取り可能な媒体からメインメモリ７０５に読み込むことができる。メインメモリ７０５に含まれている命令の配列の実行はここで説明するプロセスステップをプロセッサ７０３に実行させる。マルチ処理構成の１つ以上のプロセッサを使用して、メインメモリ７０５に含まれている命令を実行してもよい。代替実施形態では、ソフトウェア命令の代わりにあるいはソフトウェア命令と組み合わせてハードワイヤード回路を使用して、本発明の実施形態を実現してもよい。したがって、本発明の実施形態はハードウェア回路およびソフトウェアの何らかの特定な組み合わせに限定されるものではない。
【００５９】
コンピュータシステム７００はバス７０１に結合された通信インターフェイス７１７も含む。通信インターフェイス７１７はローカルネットワーク７２１に接続されたネットワークリンク７１９に結合している２方向データ通信を提供する。例えば、通信インターフェイス７１７はデジタル加入者線（ＤＳＬ）カードまたはモデム、統合サービスデジタルネットワーク（ＩＳＤＮ）カード、ケーブルモデム、または電話モデムであって、対応するタイプの電話回線に対してデータ通信接続を提供してもよい。他の例として、通信インターフェイス７１７はローカルエリアネットワーク（ＬＡＮ）カード（例えば、イーサーネット（登録商標）や非同期転送モード（ＡＴＭ）ネットワーク）であって、互換性ＬＡＮへのデータ通信接続を提供してもよい。ワイヤレスリンクを実現することもできる。このような任意の構成において、通信インターフェイス７１７は、電気、電磁気または光の信号を送受信し、これらの信号はさまざまなタイプの情報を表すデジタルデータストリームを伝える。さらに、通信インターフェイス７１７は、ユニバーサルシリアルバス（ＵＳＢ）インターフェイス、ＰＣＭＣＩＡ（パーソナルコンピュータメモリカード国際協会）インターフェイスなどのような、周辺機器インターフェイスデバイスを含むことができる。
【００６０】
ネットワークリンク７１９は一般的に１つ以上のネットワークを通して他のデータデバイスに対してデータ通信を提供する。例えば、ネットワークリンク７１９はローカルネットワーク７２１を通してホストコンピュータ７２３への接続を提供し、ローカルネットワーク７２１はネットワーク７２５（例えば、ワイドエリアネットワーク（ＷＡＮ）または“インターネット”として現在一般的に言及されているグローバルパケットデータ通信ネットワーク）への接続性、またはサービスプロバイダにより運営されるデータ装置への接続性を有する。ローカルネットワーク７２１およびネットワーク７２５はともに電気、電磁気または光の信号を使用して、情報および命令を伝える。さまざまなネットワークを通る信号およびネットワークリンク７１９上の信号で通信インターフェイス７１７を通る信号は、情報および命令を伝達する搬送波の例示的な形態である。通信インターフェイス７１７はコンピュータシステム７００とデジタルデータを通信する。
【００６１】
コンピュータシステム７００はネットワーク、ネットワークリンク７１９および通信インターフェイス７１７を通して、メッセージを送信し、プログラムを含むデータを受信することができる。インターネットの例では、（示されていない）サーバは、ネットワーク７２５、ローカルネットワーク７２１および通信インターフェイス７１７を通して、本発明の実施形態を実現するアプリケーションプログラムに属する要求されたコードを送信してもよい。プロセッサ７０３は受信している間に送信されたコードを実行し、および／またはコードを後での実行のために記憶デバイス７０９または他の不揮発性記憶装置に記憶させてもよい。この方法では、コンピュータシステム７００は搬送波の形態でアプリケーションコードを得てもよい。
【００６２】
ここで使用されているような用語“コンピュータ読み取り可能な媒体”は、実行のためにプロセッサ７０３に命令を提供することに関係する任意の媒体に関係する。このような媒体は多くの形態をとることができ、これらに限定されないが、不揮発性媒体、揮発性媒体および送信媒体が含まれる。不揮発性媒体は、例えば記憶デバイス７０９のような光または磁気ディスクが含まれる。揮発性媒体はメインメモリ７０５のような動的メモリが含まれる。送信媒体は、バス７０１を構成するワイヤを含む、同軸ケーブル、銅線および光ファイバを含む。送信媒体は、無線周波数（ＲＦ）および赤外線（ＩＲ）データ通信中に発生されるもののような、音響、光または電磁気の波の形態もとることができる。コンピュータ読み取り可能な媒体の一般的な形態は、例えばフロッピ（登録商標）ディスク、フレキシブルディスク、ハードディスク、磁気テープ、他の任意の磁気媒体、ＣＤ−ＲＯＭ、ＣＤＲＷ、ＤＶＤ、他の任意の光媒体、パンチカード、紙テープ、光マークシート、穴や他の光学認識可能な表示のパターンを有する他の任意の物理媒体、ＲＡＭ、ＰＲＯＭ、ＥＰＲＯＭ、ＦＬＡＳＨ（登録商標）−ＥＰＲＯＭ、他の任意のメモリチップまたはカートリッジ、搬送波、あるいはコンピュータが読み取ることができる他の任意の媒体を含む。
【００６３】
さまざまな形態のコンピュータ読み取り可能な媒体は実行するためにプロセッサに命令を提供することに関係してもよい。例えば、本発明の少なくとも一部を実行する命令は遠隔コンピュータの磁気ディスク上に最初に記憶されてもよい。このようなシナリオでは、遠隔コンピュータは命令をメインメモリにロードして、その命令をモデムを使用して電話回線を通して送信する。ローカルコンピュータシステムのモデムは電話回線上でデータを受信し、赤外線送信機を使用して、データを赤外線信号に変換し、その赤外線信号を、パーソナルデジタルアシスタンス（ＰＤＡ）およびラップトップのようなポータブルコンピューテングデバイスに送信する。ポータブルコンピューテングデバイス上の赤外線検出器は赤外線信号により運ばれる情報および命令を受信し、データをバス上に置く。バスはそのデータをメインメモリに伝え、このメインメモリからプロセッサは命令を取り出して実行する。メインメモリにより受信される命令は、オプション的に、プロセッサにより実行される前または後に記憶デバイス上に記憶されてもよい。
【００６４】
したがって、本発明のさまざまな実施形態はショートブロック長の低密度パリティチェック（ＬＤＰＣ）コードをエンコーディングするアプローチを提供する。エンコーダはＬＤＰＣコード化信号として送信するために、テーブル１−１０の１つにしたがって、アウタBose Chaudhuri Hocqenghem（ＢＣＨ）コードを有するＬＤＰＣコードを発生させる。テーブル１−１０のそれぞれはパリティビットアキュムレータのアドレスを特定する。パリティチェック行列の一部を低位三角に制限することにより、および／または他の要求を満足させることにより、構造がＬＤＰＣコードに課され、これによりデコーダのビットノードとチェックノードとの間の通信が簡単化される。さらに、巡回冗長検査（ＣＲＣ）エンコーダが提供され、ＣＲＣコードにしたがって入力信号がエンコードされる。上記アプローチは性能を犠牲にすることなく減少された複雑さを生み出す。
【００６５】
本発明は多数の実施形態および構成とともに説明したが、本発明はそのように制限されるものではなく、さまざまな変形および均等構成をカバーし、これらも特許請求の範囲の範囲に入る。
【図面の簡単な説明】
【００６６】
【図１】図１は本発明の実施形態にしたがった、低密度パリティチェック（ＬＤＰＣ）コードを利用するように構成された通信システムの図である。
【図２Ａ】図２Ａは図１の送信機に配置された例示的なＬＤＰＣエンコーダの図である。
【図２Ｂ】図２Ｂは図１の送信機に配置された例示的なＬＤＰＣエンコーダの図である。
【図２Ｃ】図２Ｃは本発明の１つの実施形態にしたがった、ショートフレーム長ＬＤＰＣコードを発生させるための図２ＢのＬＤＰＣエンコーダのエンコーディングプロセスのフローチャートである。
【図３】図３は図１のシステムにおける例示的な受信機の図である。
【図４】図４は本発明の実施形態にしたがった、希薄パリティチェック行列の図である。
【図５】図５は図４の行列のＬＤＰＣコードの２部グラフの図である。
【図６】図６は本発明の実施形態にしたがった、希薄パリティチェック行列の部分行列の図であり、部分行列は低位三角領域に制限されたパリティチェック値を含む。
【図７】図７は本発明の実施形態にしたがった、ＬＤＰＣエンコーディングプロセスを実行することができるコンピュータシステムの図である。
【図１】
2005086824.tif 000046
【図２Ａ】
2005086824.tif 000047
【図２Ｂ】
2005086824.tif 000048
【図２Ｃ】
2005086824.tif 000049
【図３】
2005086824.tif 000050
【図４】
2005086824.tif 000051
【図５】
2005086824.tif 000052
【図６】
2005086824.tif 000053
【図７】
2005086824.tif 000054
【外国語明細書】
2005086824000001.pdf