(57)【要約】【課題】低密度パリティチェック（ＬＤＰＣ）コードを発生させるアプローチを提供する。【解決手段】ＬＤＰＣエンコーダ（２０３）がアウタBose Chaudhuri Hocqenghem（ＢＣＨ）コードを有するＬＤＰＣコードを発生させる。１／３レートに対して、関連パラメータは次の通りである。ｑ＝１２０、ｎldpc＝６４８００、ｋldpc＝ｎBCH＝２１６００、ｋBCH＝２１４０８（１２ビットエラー訂正ＢＣＨ）。１／４レートに対して、ＬＤＰＣコードは以下の関連パラメータを持つ。ｑ＝１３５、ｎldpc＝６４８００、ｋldpc＝ｎBCH＝１６２００、ｋBCH＝１６００８（１２ビットエラー訂正ＢＣＨ）。２／５レートに対して、以下のパラメータが存在する。ｑ＝１０８、ｎldpc＝６４８００、ｋldpc＝ｎBCH＝２５９２０、ｋBCH＝２５７２８（１２ビットエラー訂正ＢＣＨ）。上記アプローチは衛星を通してのデジタルビデオブロードキャストサービスに特定のアプリケーションを有する。【選択図】      図１
2005136989.tif 000002
【特許請求の範囲】
【請求項１】
エンコーディングするための方法において、
情報ビットを受信し、
それぞれパリティビットアキュムレータのアドレスを特定する各テーブル
【表１】
2005136989.tif 000015
2005136989.tif 000016
【表２】
2005136989.tif 000017
【表３】
2005136989.tif 000018
に関係する１／３のコードレート、１／４のコードレートまたは２／５のコードレートのうちの１つにしたがって、情報ビットに基づき、低密度パリティチェック（ＬＤＰＣ）コードのパリティビットを発生させることを含む方法。
【請求項２】
ＬＤＰＣコード化信号を変調し、
変調信号を送信することをさらに含む請求項１記載の方法。
【請求項３】
変調信号はブロードバンド衛星アプリケーションのサポートで衛星リンク（１０３）を通して送信される請求項２記載の方法。
【請求項４】
変調ステップは、８−ＰＳＫ（位相偏移変調）、１６−ＱＡＭ（直交振幅変調）、ＱＰＳＫ（４相位相偏移変調）、１６−ＡＰＳＫ（振幅位相偏移変調）および３２−ＡＰＳＫのうちの１つを含む信号配列にしたがって実行される請求項２記載の方法。
【請求項５】
エンコーディングするための命令を記憶しているコンピュータ読み取り可能な媒体において、
前記命令は、実行時に１つ以上のプロセッサに請求項１記載の方法を実行させるように構成されている媒体。
【請求項６】
エンコーダ（２０３）において、
情報ビットを受信する手段と、
パリティビットアキュムレータのアドレスをそれぞれ特定する各テーブル
【表４】
2005136989.tif 000019
2005136989.tif 000020
【表５】
2005136989.tif 000021
【表６】
2005136989.tif 000022
に関係する複数のコードレートの１つにしたがって、情報ビットに基づき、ＬＤＰＣコード化信号として送信するために、アウタBose Chaudhuri Hocqenghem（ＢＣＨ）コードを有する低密度パリティチェック（ＬＤＰＣ）コードを発生させる手段とを具備するエンコーダ。
【請求項７】
ＬＤＰＣコード化信号が変調されて送信される請求項６記載のエンコーダ（２０３）。
【請求項８】
変調信号はブロードバンド衛星アプリケーションのサポートで送信される請求項７記載のエンコーダ（２０３）。
【請求項９】
変調は、８−ＰＳＫ（位相偏移変調）、１６−ＱＡＭ（直交振幅変調）、ＱＰＳＫ（４相位相偏移変調）、１６−ＡＰＳＫ（振幅位相偏移変調）および３２−ＡＰＳＫのうちの１つを含む信号配列にしたがって実行される請求項７記載のエンコーダ（２０３）。
【請求項１０】
低密度パリティチェック（ＬＤＰＣ）コード化信号の送信をサポートする送信機（２００）において、
受信情報ビットに基づいて、ＬＤＰＣコードを出力するように構成された低密度パリティチェック（ＬＤＰＣ）エンコーダ（２０３）と、
ＬＤＰＣエンコーダ（２０３）に結合され、ＬＤＰＣコードに対するアウタコードを提供するように構成されたBose Chaudhuri Hocqenghem（ＢＣＨ）エンコーダ（２１１）とを具備し、
ＬＤＰＣコードは、それぞれパリティビットアキュムレータのアドレスを特定する各テーブル
【表７】
2005136989.tif 000023
2005136989.tif 000024
【表８】
2005136989.tif 000025
【表９】
2005136989.tif 000026
に関係する１／３のコードレート、１／４のコードレートまたは２／５のコードレートのうちの１つにしたがって発生される送信機。
【請求項１１】
ＬＤＰＣコード化信号を変調するように構成された変調器（２０５）をさらに具備する請求項１０記載の送信機（２００）。
【請求項１２】
変調信号はブロードバンド衛星アプリケーションのサポートで衛星リンク（１０３）を通して送信される請求項１１記載の送信機（２００）。
【請求項１３】
変調は８−ＰＳＫ（位相偏移変調）、１６−ＱＡＭ（直交振幅変調）、ＱＰＳＫ（４相位相偏移変調）、１６−ＡＰＳＫ（振幅位相偏移変調）および３２−ＡＰＳＫのうちの１つを含む信号配列にしたがって実行される請求項１１記載の送信機（２００）。
【発明の詳細な説明】
【関連出願】
【０００１】
本願は２００３年１０月２７日に出願され、“レート１／３および１／４ＬＤＰＣコード”と題する米国仮出願第６０／５１４，６８３号および２００３年１１月７日に出願され、“レート１／３、１／４および２／５ＬＤＰＣコード”と題する米国仮出願第６０／５１８，１９９号に関係し、３５Ｕ．Ｓ．Ｃ．１１９条（ｅ）のもとで、これらの米国仮出願の先の出願日の利益を主張する。
【発明の分野】
【０００２】
本発明は通信システムに関し、特に、コード化システムに関する。
【発明の背景】
【０００３】
通信システムはコーディングを使用して雑音のある通信チャネルに渡る信頼性ある通信を確実に行う。例えば、衛星ネットワークのようなワイヤレス（または無線）システムでは、地理的および環境的要因からの雑音源が多い。これらの通信チャネルは固定容量を表し、これはある信号対雑音比（ＳＮＲ）におけるシンボル当たりのビットに関して表すことができ、（シャノン限界として知られる）理論的上限を規定する。結果として、コーディング設計はこのシャノン限界に近づくレートを達成することを目的としている。この目的は、帯域幅制約衛星システムに対して特に密接な関係がある。シャノン限界に近づくこのようなクラスのコードの１つは低密度パリティチェック（ＬＤＰＣ）コードである。
【０００４】
従来、ＬＤＰＣコードは多くの欠点があることから、幅広く採用されていなかった。１つの欠点はＬＤＰＣエンコーディング技術が非常に複雑であることである。その生成行列を使用してＬＤＰＣコードをエンコードするには、非常に大きな非希薄行列を記憶することが必要である。さらに、ＬＤＰＣコードは大きなブロックが効率的であることを必要とし、結果的に、ＬＤＰＣコードのパリティチェック行例が希薄であっても、これらの行列の記憶が問題である。
【０００５】
実現の将来的な見通しから、多数の難題に直面する。例えば、記憶装置はＬＤＰＣコードが実際には広まっていない重要な理由である。したがって、長いＬＤＰＣコードはより大きな記憶空間を要求する。また、ＬＤＰＣコード実現における主な難題はデコーダ中のいくつかの処理エンジン（ノード）間で接続ネットワークをどのように達成するかである。さらに、デコーディングプロセス、特にチェックノード動作における計算負荷は問題を生じる。
【０００６】
したがって、簡単なエンコーディングおよびデコーディングプロセスを使用するＬＤＰＣ通信システムに対する必要性がある。より複雑さを持ち込むことなく、ＬＤＰＣコードを使用して高データレートを効率的にサポートする必要性がある。ＬＤＰＣエンコーダおよびデコーダの性能を向上させる必要性もある。ＬＤＰＣコーディングを実現するための記憶要求を最小にする必要性もある。
【発明の開示】
【発明の概要】
【０００７】
これらおよび他の必要性は本発明により取り扱われる。ここで、低密度パリティチェック（ＬＤＰＣ）コードをエンコーディングするアプローチが提供される。エンコーダは、ＬＤＰＣコード化信号として送信するために、テーブル１−６の１つにしたがって、アウタBose Chaudhuri Hocqenghem（ＢＣＨ）コードを有するＬＤＰＣコードを発生させる。テーブル１−６のそれぞれはパリティビットアキュムレータのアドレスを特定する。このアプローチはＬＤＰＣコードの好都合なエンコーディングとともにデコーディングを有効に提供する一方で、記憶および処理リソースを最小にする。
【０００８】
本発明の実施形態の他の観点にしたがうと、ＬＤＰＣコードは、８−ＰＳＫ（位相偏移変調）、１６−ＱＡＭ（直交振幅変調）、ＱＰＳＫ（４相位相偏移変調）、１６−ＡＰＳＫ（振幅位相偏移変調）および３２−ＡＰＳＫのうちの１つを含む信号配列にしたがって変調される信号により表される。
【０００９】
本発明の実施形態のさらに別の観点にしたがうと、変調されたＬＤＰＣコード化信号はブロードバンド衛星アプリケーションのサポートで衛星リンクを通して送信される。
【００１０】
本発明のさらに他の観点、特徴および利点は、本発明を実施するために意図される最良の態様を含む、数多くの特定の実施形態および実施を単に例示することにより、以下の詳細の説明から容易に明らかになる。本発明は他のおよび異なる実施形態を行うこともでき、そのいくつかの詳細はすべて本発明の精神および範囲を逸脱することなく、さまざまな明白な点で修正できる。したがって、図面および説明は本質的に例証であると見なされるべきであり、限定的と見なされてはならない。
【００１１】
本発明は添付図面の図中に制限としてではなく例証として描かれ、図面において同じ参照番号は類似するエレメントに関係する。
【好ましい実施形態の説明】
【００１２】
ショートフレーム長の低密度パリティチェック（ＬＤＰＣ）コードを効率的にエンコーディングするシステム、方法およびソフトウェアを説明する。以下の説明においては、説明の目的のために、本発明の完全な理解を提供するため、多数の特定な詳細が述べられている。しかしながら、本発明がこれらの特定な詳細なしに、あるいは均等な構成で実現されてもよいことは当業者にとっては明らかである。他の例では、周知の構造およびデバイスは本発明を不必要に曖昧にするのを避けるためにブロック図で示されている。
【００１３】
図１は本発明の実施形態にしたがった、低密度パリティチェック（ＬＤＰＣ）コードを利用するように構成された通信システムの図である。デジタル通信システム１００は送信機１０１を含み、この送信機１０１は通信チャネル１０３を通して受信機１０５に向かう信号波形を発生させる。このディスクリート通信システム１００では、送信機１０１はディスクリートセットの可能性あるメッセージを生成するメッセージ源を有し、それぞれの可能性あるメッセージは対応する信号波形を持つ。これらの信号波形は通信チャネル１０３により、減衰され、そうでなければ変更される。チャネル１０３における雑音と戦うためにＬＤＰＣコードが利用される。
【００１４】
例として、チャネル１０３はブロードバンド衛星アプリケーションのサポートで衛星ターミナル（例えば非常に小型の開口ターミナル（ＶＳＡＴ））の役に立つ衛星リンクである。このようなアプリケーションには衛星ブロードキャスティングおよびインターラクティブサービス（およびデジタルビデオブロードキャスト（ＤＶＢ）−Ｓ２標準規格に準拠する）が含まれる。衛星を通してのデジタルビデオブロードキャスティング（ＤＶＢ−Ｓ）標準規格は世界中で幅広く採用されており、例えばデジタル衛星テレビ番組を提供している。
【００１５】
送信機１０１により発生されるＬＤＰＣコードは何らかの性能損失を生じさせることなく高速な構成を可能にする。送信機１０１から出力されるこのように構成されたＬＤＰＣコードは、変調スキーム（例えば８−ＰＳＫ）によりチャネルエラーに既に弱いビットノードに対してわずかな数のチェックノードを割り当てることを避ける。
【００１６】
このようなＬＤＰＣコードは（ターボコードと異なり）並列可能なデコーディングアルゴリズムを持ち、これは加算、比較およびテーブルルックアップのような簡単な動作を伴う効果がある。さらに、慎重に設計されたＬＤＰＣコードはエラーフロアーの兆候を何ら示さない。
【００１７】
本発明の１つの実施形態にしたがうと、送信機１０１は比較的に簡単なエンコーディング技術を使用して、（デコーディング中に効率的なメモリアクセスを促進する）パリティチェック行列に基づいてＬＤＰＣコードを発生させ、受信機１０５と通信する。送信機１０１はＬＤＰＣコードを使用し、ブロック長が十分に長ければ、ＬＤＰＣコードは連結ターボ＋ＲＳ（リードソロモン）コードより性能が優れる場合がある。
【００１８】
図２Ａおよび図２Ｂは図１の送信機に配置される例示的なＬＤＰＣエンコーダの図である。図２Ａに見られるように、送信機２００にはＬＤＰＣエンコーダ２０３が設けられ、ＬＤＰＣエンコーダ２０３は情報源２０１からの入力を受け入れ、受信機１０５におけるエラー訂正処理に適切なより高い冗長性のコード化ストリームを出力する。情報源２０１は、離散アルファベットＸからｋ個の信号を発生させる。ＬＤＰＣコードはパリティチェック行列で特定される。他方、ＬＤＰＣコードをエンコーディングするには、一般的には生成行列を特定することが必要になる。ガウス消去法を使用してパリティチェック行列から生成行列を得ることが可能であるが、結果として得られる行列はもはや希薄でなく、大きな生成行列を記憶することは複雑となる可能性がある。
【００１９】
エンコーダ２０３は、簡単なエンコーディング技術を使用して、変調器２０５に対する信号をアルファベットＹから発生させ、この簡単なエンコーディング技術は構造をパリティチェック行列に課すことによりパリティチェック行列のみ使用する。特に、行列のある部分を三角形に制約することによりパリティチェック行列に制限がおかれる。このようなパリティチェック行列の構造は図６で以下にさらに完全に説明する。このような制限は無視しうる性能損失となり、したがって魅力的なトレードオフとなる。
【００２０】
変調器２０５はエンコーダ２０３からのエンコード化メッセージを信号波形にマッピングし、この信号波形は送信アンテナ２０７に送られ、送信アンテナ２０７はこれらの波形を送信チャネル１０３を通して放射する。したがって、エンコード化メッセージは変調され、送信アンテナ２０７に配信される。以下で説明するように、送信アンテナ２０７からの送信は（図３に示されている）受信機に伝搬する。
【００２１】
図２Ｂは、本発明の１つの実施形態にしたがった、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＝０。例として、ｋldpcビットはシステマティックにエンコードされ、ｎldpcビットが発生される。第１の情報ビットｉ0はテーブル１−３の第１行で特定されるパリティビットアドレスにおいて累積される。テーブル１の１／３レートコードに対して、関連パラメータは次の通りである。ｑ＝１２０、ｎldpc＝６４８００、ｋldpc＝ｎBCH＝２１６００、ｋBCH＝２１４０８（１２ビットエラー訂正ＢＣＨ）。１／４レートに対して、ＬＤＰＣコードは以下の関連パラメータを持つ。ｑ＝１３５、ｎldpc＝６４８００、ｋldpc＝ｎBCH＝１６２００、ｋBCH＝１６００８（１２ビットエラー訂正ＢＣＨ）。ロング２／５ＬＤＰＣコードに対して、以下のパラメータが存在する。ｑ＝１０８、ｎldpc＝６４８００、ｋldpc＝ｎBCH＝２５９２０、ｋBCH＝２５７２８（１２ビットエラー訂正ＢＣＨ）。
【００２５】
例えば、レート１／３（テーブル１）に対し、ｉ0について以下の結果となる。
【００２６】
【数１】
2005136989.tif 000003
上記の式において、加算はＧＦ（２）におけるものである。
【００２７】
その後、次の３５９情報ビットｉm、ｍ＝１，２，…，３５９に対して、これらのビットはパリティビットアドレス｛ｘ＋ｍ  ｍｏｄ３６０×ｑ｝ｍｏｄ（ｎldpc−ｋldpc）において累積される。ここでｘは第１ビットｉ0に対応するパリティビットアキュムレータのアドレスを示し、ｑはコードレート依存定数である。レート１／３に対するｑ＝１２０で例を続けると、情報ビットｉ1に対して、以下の演算が実行される。
【００２８】
【数２】
2005136989.tif 000004
【００２９】
第３６１の情報ビットｉ360に対して、パリティビットアキュムレータのアドレスはテーブル１−３の第２行に与えられている。同様な方法で、後続する３５９情報ビットｉm、ｍ＝３６１，３６２，…，７１９に対して、パリティビットアキュムレータのアドレスは式｛ｘ＋ｍ  ｍｏｄ３６０×ｑ｝ｍｏｄ（ｎldpc−ｋldpc）を使用して得られる。ここでｘは情報ビットｉ360に対応するパリティビットアキュムレータのアドレス、すなわちテーブル１−３の第２行におけるエントリを示す。同様に、３６０の新しい情報ビットの各グループに対して、テーブル１−３からの新しい行が使用されて、パリティビットアキュムレータのアドレスが発見される。
【００３０】
【表１０】
2005136989.tif 000005
2005136989.tif 000006
【００３１】
【表１１】
2005136989.tif 000007
【００３２】
【表１２】
2005136989.tif 000008
2005136989.tif 000009
【００３３】
すべての情報ビットが使い尽くされた後に、最終パリティビットは次の通りに得られる。最初に、ｉ＝１で開始して、以下の演算が実行される。
【００３４】
【数３】
2005136989.tif 000010
【００３５】
ｐi，ｉ＝０，１，…，ｎldpc−ｋldpc−１の最終内容はパリティビットｐiに等しい。
【００３６】
すべての情報ビットが使い尽くされた後に、最終パリティビットは次の通りに得られる。最初に、ｉ＝１で開始して、以下の演算が実行される。
【００３７】
【数４】
2005136989.tif 000011
【００３８】
ｐi，ｉ＝０，１，…，ｎldpc−ｋldpc−１の最終内容はパリティビットｐiに等しい。
【００３９】
本発明の１つの実施形態にしたがった、ＢＣＨエンコーディングに関して、ＢＣＨエンコーダ２１１により利用されるＢＣＨコードの生成多項式は次の通りである。
【００４０】
ｇ（ｘ）＝（１＋ｘ＋ｘ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ｍ（ｘ）＋ｄ（ｘ）。
【００４２】
上述したように、ｋldpcビットはシステマティックにエンコードされ、ｎldpcビットが発生される。本発明の１つの実施形態にしたがうと、ｎldpcは１６２００ビットであり、これはショートブロック長である。比較的短い長さのこのようなコードの場合、約１６２００ビット以下の長さを有するＬＤＰＣコードは“ショート”ブロック長コードと考えられる。
【００４３】
本発明の実施形態にしたがうと、ショートブロックコードのいくつか（例えばテーブル５のレート１／５）はブロックサイズｎm＞１６２００のわずかに長い（ｋm，ｎm）“マザー”コードのバージョンを短くすることにより発生される。図２Ｄに示されているように、ＢＣＨエンコード化ビットのｋldpcはｋm−ｋldpcダミー０により先行される（ステップ２５１）。ステップ２５３において、結果として得られるｋmビットはシステマティックにエンコードされ、ｎmビットが発生される。ステップ２５５において、最初のｋm−ｋldpcダミー０は削除され、結果として得られるｎldpc＝１６２００ビットが送信される（ステップ２５７）。ｋm−ｋldpc＝ｎm−ｎldpcであることに留意すべきである。テーブル４−６は他の例示的なショートコードレート１／３、１／５および２／５（１６２００ビットのｎldpc）を提供する。
【００４４】
【表１３】
2005136989.tif 000012
【００４５】
【表１４】
2005136989.tif 000013
【００４６】
【表１５】
2005136989.tif 000014
【００４７】
テーブル１−６に提供されているＬＤＰＣコードを設計する先のアプローチは、メモリ（例えばランダムアクセスメモリ（ＲＡＭ））内の隣接するメモリ位置に常に配置されるべき、ビットノードおよびチェックノードの区分されたグループに関する関連情報の記憶および検索を効果的に可能にする。結果的に、異なるデコーダを使用することなく、複数のコードレートをサポートすることができる。さらに、この設計は単一ＲＡＭバンクの使用を可能にし、それにより集積回路のサイズを最小にする。先に言及したように、例示的な実施形態では、ＭＰＥＧ（モーションピクチャエキスパートグループ）パケット送信のような、さまざまなデジタルビデオアプリケーションに対して、先のＬＤＰＣコードを使用することができる。
【００４８】
図３は図１のシステムにおける例示的な受信機の図である。受信側では、受信機３００には復調器３０１が含まれ、復調器３０１は送信機２００からの受信信号の復調を行う。これらの信号は復調のために受信アンテナ３０３において受信される。復調後、受信信号はＬＤＰＣデコーダ３０５に転送され、デコーダ３０５はビットメトリック発生器３０７とともに、メッセージＸ’を発生させることによりオリジナルソースメッセージを再構成しようと試行する。ビットメトリック発生器３０７は、デコーディングプロセス中にデコーダ３０５と行ったり来たり（反復的に）情報を交換してもよい。これらのデコーディングアプローチは２００３年７月３日に出願された“低密度パリティチェック（ＬＤＰＣ）デコーダにおけるルーティングのための方法およびシステム”と題する同時継続中の出願（シリアル番号１０／６１３，８２４号；代理人ドケットＰＤ−２０３００９）でさらに完全に説明されている。テーブル１−６に関して構成されるＬＤＰＣコードは共通のデコーディングアーキテクチャを使用して複数のコードレート（結果的に、複数のデータレート）をサポートすることができることに留意すべきである。これに対して、例えば畳み込みコードは中間レートを達成するためにパンクチャ技術を必要とする。
【００４９】
本発明により提供される利点をさらに理解するために、図４で説明されているように、どのようにしてＬＤＰＣコードが発生されるかを調べることが有効である。
【００５０】
図４は本発明の実施形態にしたがった、希薄パリティチェック行列の図である。ＬＤＰＣコードは希薄パリティチェック行列Ｈ(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（ＢＣＨ）コードを有するＬＤＰＣコードを発生させる。テーブル１−６のそれぞれはパリティビットアキュムレータのアドレスを特定する。先のアプローチは性能を犠牲にすることなく減少された複雑さを生み出す。
【００６９】
本発明は多数の実施形態および構成とともに説明したが、本発明はそのように制限されるものではなく、さまざまな変形および均等構成をカバーし、これらも特許請求の範囲の範囲に入る。
【図面の簡単な説明】
【００７０】
【図１】図１は本発明の実施形態にしたがった、低密度パリティチェック（ＬＤＰＣ）コードを利用するように構成された通信システムの図である。
【図２Ａ】図２Ａは図１の送信機に配置された例示的なＬＤＰＣエンコーダの図である。
【図２Ｂ】図２Ｂは図１の送信機に配置された例示的なＬＤＰＣエンコーダの図である。
【図２Ｃ】図２Ｃは本発明の実施形態にしたがった、ロングフレーム長コードおよびショートフレーム長ＬＤＰＣコードをそれぞれ発生させるための図２ＢのＬＤＰＣエンコーダのエンコーディングプロセスのフローチャートである。
【図２Ｄ】図２Ｄは本発明の実施形態にしたがった、ロングフレーム長コードおよびショートフレーム長ＬＤＰＣコードをそれぞれ発生させるための図２ＢのＬＤＰＣエンコーダのエンコーディングプロセスのフローチャートである。
【図３】図３は図１のシステムにおける例示的な受信機の図である。
【図４】図４は本発明の実施形態にしたがった、希薄パリティチェック行列の図である。
【図５】図５は図４の行列のＬＤＰＣコードの２部グラフの図である。
【図６】図６は本発明の実施形態にしたがった、希薄パリティチェック行列の部分行列の図であり、部分行列は低位三角領域に制限されたパリティチェック値を含む。
【図７】図７は反復コードに対するレート１／３および１／４におけるＬＤＰＣコードの性能のグラフである。
【図８】図８は図２Ａの送信機によりサポートされるさまざまなコードレートおよび変調スキームにおけるＬＤＰＣコードの性能のグラフである。
【図９】図９は本発明の実施形態にしたがった、ＬＤＰＣエンコーディングプロセスを実行することができるコンピューテングシステムの図である。
【図１】
2005136989.tif 000027
【図２Ａ】
2005136989.tif 000028
【図２Ｂ】
2005136989.tif 000029
【図２Ｃ】
2005136989.tif 000030
【図２Ｄ】
2005136989.tif 000031
【図３】
2005136989.tif 000032
【図４】
2005136989.tif 000033
【図５】
2005136989.tif 000034
【図６】
2005136989.tif 000035
【図７】
2005136989.tif 000036
【図８】
2005136989.tif 000037
【図９】
2005136989.tif 000038
【外国語明細書】
2005136989000001.pdf