(57)【要約】      （修正有）【課題】低密度パリティチェック（ＬＤＰＣ）コード化信号のブロードキャスト送信をサポートするアプローチを提供する。【解決手段】受信機にはＬＤＰＣ信号をデコードしてデコード化信号を出力するデコーダ（１０１）が含まれている。デコーダ（１０１）はエンコーダとして動作し、干渉相殺するためにデコード化信号を再エンコードする。【選択図】図１
2005051756.tif 000002
【特許請求の範囲】
【請求項１】
低密度パリティチェック（ＬＤＰＣ）コード化信号の複数の受信機へのブロードキャスト送信をサポートする方法において、
受信機の１つにより入力信号を受信し、前記１つの受信機はＬＤＰＣデコーダを含み、
前記デコーダにより前記入力信号をエンコードしてエンコード化信号を出力することを含む方法。
【請求項２】
ＬＤＰＣコード化信号を受信し、
前記ＬＤＰＣデコーダにより前記ＬＤＰＣ信号をデコードしてデコード化信号を出力することをさらに含む請求項１記載の方法。
【請求項３】
前記入力信号が前記デコード化信号であり、前記エンコード化信号が前記受信ＬＤＰＣ信号との干渉相殺に対して使用される請求項２に記載の方法。
【請求項４】
デコードおよびエンコードのステップは同時に実行される請求項２記載の方法。
【請求項５】
前記デコード化信号の最初のｋ個の情報ビットに基づいて受信ベクトルを組み立て、
前記受信ベクトルで前記デコーダを初期化することをさらに含む請求項２記載の方法。
【請求項６】
前記受信ベクトルはｎの長さを有し、ｎ−ｋビットが論理０値に関係するチャネルビットの最尤比の最大値にしたがって初期化される請求項５記載の方法。
【請求項７】
前記受信ベクトルはｎの長さを有し、ｎ−ｋビットがヌル値に関係するチャネルビットの最尤比の最大値にしたがって初期化される請求項５記載の方法。
【請求項８】
前記ＬＤＰＣ信号は衛星リンクを通して受信される請求項１記載の方法。
【請求項９】
前記ＬＤＰＣコード化信号は、８−ＰＳＫ（位相シフトキーイング）、１６−ＱＡＭ（直角位相振幅変調）、１６−ＡＰＳＫ（振幅位相シフトキーイング）、３２−ＡＰＳＫおよびＱＰＳＫ（直角位相シフトキーイング）のうちの１つを含む信号配列にしたがって変調される請求項１記載の方法。
【請求項１０】
低密度パリティチェック（ＬＤＰＣ）コード化信号の複数の受信機へのブロードキャスト送信をサポートする命令が記録されているコンピュータ読み取り可能な媒体において、
前記命令は実行時に、１つ以上のプロセッサに請求項１記載の方法を実行させるように配列されている媒体。
【請求項１１】
低密度パリティチェック（ＬＤＰＣ）コード化信号のブロードキャスト送信を受信する受信機装置において、
受信機の１つにより入力信号を受信する手段と、
前記入力信号をエンコードして、エンコード化信号を出力するように構成されたデコーダとを具備し、
前記１つの受信機はＬＤＰＣデコーダを含む装置。
【請求項１２】
ＬＤＰＣコード化信号を受信する手段をさらに具備し、
前記デコーダは前記ＬＤＰＣ信号をデコードして、デコード化信号を出力する請求項１１記載の装置。
【請求項１３】
前記入力信号が前記デコード化信号であり、前記エンコード化信号が前記受信ＬＤＰＣ信号との干渉相殺に対して使用される請求項１２記載の装置。
【請求項１４】
前記デコーダはデコードとエンコードを同時に実行する請求項１２記載の装置。
【請求項１５】
前記デコーダは、前記デコード化信号の最初のｋ個の情報ビットに基づいて受信ベクトルを組み立て、前記受信ベクトルで前記デコーダを初期化するようにさらに構成されている請求項１２記載の装置。
【請求項１６】
前記受信ベクトルはｎの長さを有し、ｎ−ｋビットが論理０値に関係するチャネルビットの最尤比の最大値にしたがって初期化される請求項１５記載の装置。
【請求項１７】
前記受信ベクトルはｎの長さを有し、ｎ−ｋビットがヌル値に関係するチャネルビットの最尤比の最大値にしたがって初期化される請求項１５記載の装置。
【請求項１８】
前記ＬＤＰＣ信号は衛星リンクを通して受信される請求項１１記載の装置。
【請求項１９】
前記ＬＤＰＣコード化信号は、８−ＰＳＫ（位相シフトキーイング）、１６−ＱＡＭ（直角位相振幅変調）、１６−ＡＰＳＫ（振幅位相シフトキーイング）、３２−ＡＰＳＫおよびＱＰＳＫ（直角位相シフトキーイング）のうちの１つを含む信号配列にしたがって変調される請求項１１記載の装置。
【請求項２０】
低密度パリティチェック（ＬＤＰＣ）コードを発生させるデコーダにおいて、
受信されたＬＤＰＣエンコード化信号をデコードするように構成されたプロセッサを具備し、
前記プロセッサは、前記受信ＬＤＰＣエンコード化信号に関係する干渉相殺のために前記デコード化信号をエンコードするようにさらに構成されているデコーダ。
【発明の詳細な説明】
【関連出願】
【０００１】
本願は“デコーダによるＬＤＰＣコードのファミリーの効率的なエンコーディング”と題する、２００３年７月３日に出願された米国仮特許出願番号第６０／４８４，９８８号に関係し、３５Ｕ．Ｓ．Ｃセクション１１９（ｅ）の下でより早い出願日の利益を主張し、この米国仮特許出願の全体は参照によりここに組み込まれている。
【技術分野】
【０００２】
本発明は通信システムに関し、特にコード化システムに関する。
【背景技術】
【０００３】
通信システムはコーディングを使用して、雑音のある通信チャネルにおいて信頼性のある通信を確実に行う。これらの通信チャネルは固定容量を示し、ある信号対雑音比（ＳＮＲ）におけるシンボル当たりのビットに関して表現することができ、（シャノン限界として知られている）理論的な上限を規定する。結果として、コーディング設計はこのシャノン限界に近づくレートを達成することを目的としている。シャノン限界に近づくこのようなクラスのコードの１つは低密度パリティチェック（ＬＤＰＣ）コードである。
【０００４】
従来、ＬＤＰＣコードは多くの欠点があることから、幅広く採用されていなかった。１つの欠点はＬＤＰＣエンコーディング技術は非常に複雑であることである。その生成行列を使用してＬＤＰＣコードをエンコードには、非常に大きな非希薄行列を記憶することが必要である。さらに、ＬＤＰＣコードは大きなブロックが有効であることを必要とし、結果的に、ＬＤＰＣコードのパリティチェック行例が希薄であっても、これらの行列の記憶が問題である。
【０００５】
実現の将来的な見通しから、多数の難題に直面する。例えば、記憶装置はＬＤＰＣコードが実際には広まっていない重要な理由である。また、ＬＤＰＣコード実現における主な難題はデコーダ中のいくつかの処理エンジン（ノード）間で接続ネットワークをどのように達成するかである。さらに、デコーディングプロセス、特にチェックノード動作における計算負荷は問題を生じる。
【０００６】
例えば、ブロードキャストアプリケーションでは、驚くべき数の利用受信機のために、ＬＤＰＣデコーダを含む、受信機ハードウェアから生じる費用の影響は大きく拡大する。
【０００７】
一方、衛星ブロードキャストアプリケーションのようなアプリケーションの中には、必要とされる送信機の数は比較的少ないものもある。これは受信機よりも送信機の費用がかなり高くなることにつながる。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
したがって、エンコーディング動作を実行する標準受信機を構成する必要性がある。この方法では、送信機は受信機の経済的利益を利用することができる。
【課題を解決するための手段】
【０００９】
これらのおよび他の必要性は本発明により取り扱われる。本発明ではデコーダの構成部品を使用して低密度パリティチェック（ＬＤＰＣ）エンコーディングを実行するアプローチが提供される。１つの実施形態では、ｎ−ｋビットは論理０値に関係するチャネルビットの最尤比の最大値にしたがって初期化される。先のアプローチは既存のデコーダハードウェアを共有することによりエンコーディング能力を有効に提供し、それにより最小費用で受信機の機能性を向上させる。ＬＤＰＣデコーダは多数の並列処理エンジンを使用できることから、デコーダはこれらのリソースを利用して、高速かつ効率的なエンコーディングを提供することができる。また、先の構成は受信機内のエンコーダに対して専用ハードウェアを作る必要性もなくす効果がある。これは衛星ブロードキャストアプリケーションにおいて大きな費用節約をもたらし、多数の受信機の採用を伴うことができる。
【００１０】
本発明の実施形態の１つの観点にしたがうと、複数の受信機への低密度パリティチェック（ＬＤＰＣ）コード化信号のブロードキャスト送信をサポートする方法が開示される。この方法は、受信機の１つにより入力信号を受信することを含み、この１つの受信機はＬＤＰＣデコーダを含む。また、この方法はデコーダにより、入力信号をエンコードして、エンコード化信号を出力することを含む。
【００１１】
本発明の実施形態の他の観点にしたがうと、低密度パリティチェック（ＬＤＰＣ）コード化信号のブロードキャスト送信を受信する装置が開示される。この装置は、受信機の１つにより入力信号を受信する手段を含み、この１つの受信機はＬＤＰＣデコーダを含む。この装置はまた入力信号をエンコードして、エンコード化信号を出力するように構成されたデコーダも含む。
【００１２】
本発明の実施形態のさらに別の観点にしたがうと、低密度パリティチェック（ＬＤＰＣ）コードを発生させるデコーダが開示される。このデコーダは受信ＬＤＰＣエンコード化信号をデコードするように構成されたプロセッサを含む。プロセッサは受信ＬＤＰＣエンコード化信号に関して干渉相殺するためにデコード化信号をエンコードするようにさらに構成されている。
【００１３】
本発明のさらに別の観点、特徴および効果は、多数の特定の実施形態および構成を単に示すことにより、以下の詳細な説明から容易に明らかになり、多数の特定の実施形態および構成には本発明を実行するために企図されているベストモードが含まれる。本発明は他のおよび異なる実施形態も可能であり、そのいくつかの詳細は本発明の精神および範囲をまったく逸脱することなく、さまざまな明らかな観点で修正することができる。したがって、図面および説明は本質的に例示として考えるべきであり、制限的なものとして考えるべきではない。
【００１４】
本発明は添付図面において例のつもりで示され、限定のつもりで示されているものではなく、添付図面では同じ参照番号は同様な構成要素に言及している。
【発明を実施するための最良の形態】
【００１５】
低密度パリティチェック（ＬＤＰＣ）コードを効率的にエンコーディングするシステム、方法およびソフトウェアを説明する。以下の記述では、説明の目的のために、本発明の完全な理解をもたらすように多くの特定な詳細を記述する。しかしながら、これらの特定な詳細がなく、あるいは均等な構成で、本発明を実施してもよいことは当業者に明らかである。他の例では、よく知られた構造およびデバイスは本発明を不必要性に曖昧にすることを避けるためにブロック図で示されている。
【００１６】
図１は本発明の実施形態にしたがった、ＬＤＰＣエンコーディングを実行できる低密度パリティチェック（ＬＤＰＣ）デコーダの図である。一般的に、ＬＤＰＣエンコーディングプロセスは情報源からの入力を受け入れ、受信機におけるエラー訂正処理に適したより高い冗長性を持つコード化ストリームを出力することを伴う。例として、情報源は離散アルファベットＸからｋ個の信号を発生させる。ＬＤＰＣコードはパリティチェック行列により特定される。一方、ＬＤＰＣコードをエンコーディングすることは一般的に生成行列を特定することを必要とする。ガウス消去法を使用してパリティチェック行列から生成行列を得ることは可能であるけれども、結果として得られる行列はもはや希薄ではなく、大きな生成行列を記憶させることは複雑になることがある。
【００１７】
ＬＤＰＣエンコーディングプロセスは簡単なエンコーディング技術を使用してアルファベットＹから変調器に対する信号を発生させ、この簡単なエンコーディング技術はパリティチェック行列に構造を強いることにより、パリティチェック行列のみを使用する。特に、行列のある部分を三角行列に制約することにより、パリティチェック行列に制限をおく。このようなパリティチェック行列の制約は以下の図４においてさらに完全に説明する。このように制限すると性能損失が無視可能となり、したがって、魅力あるトレードオフを構成する。
【００１８】
示されているように、デコーダ１０１によるＬＤＰＣエンコーディングプロセスをサポートする機能構成部品には、受信ベクトル構成モジュール１０３、デコーダ初期化モジュール１０５およびチェックノード処理モジュール１０７が含まれる。チェックノード処理モジュール１０７は加算器１１１に出力し、加算器１１１はレジスタ１０９に記憶されている以前の出力を合計する。これらモジュール１０３、１０５、１０７は関連して動作し、新しい情報をエンコードし、あるいは（干渉相殺アプリケーションにおいて）受信データストリームを再エンコードする。このプロセスは図５および図６に関してさらに完全に説明する。
【００１９】
本発明により提供される効果を理解するために、以下で説明するように、どのようにしてＬＤＰＣコードが発生されるかをさらに綿密に調べることが有益である。
【００２０】
図２は本発明の実施形態にしたがった、希薄パリティチェック行列の図である。ＬＤＰＣコードは希薄パリティチェック行列Ｈ(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に対して同様である。
【００２８】
ＬＤＰＣデコーダ１０１は高度並列システムとして実現できることから、デコーディング用ハードウェアを使用して適切に設計されたエンコーダは処理時間に関してかなり効率的にすることができる。したがって、エンコーディングプロセスはデコーディングの通常動作に影響を与えることなく、クロックサイクルを“こっそり入手”することができる。ハードウェア費用に関して、デコーダハードウェアを活用することによるエンコーディングはデコーダ１０１に対してほとんど費用を追加しないか、あるいはまったく追加しない効果がある。
【００２９】
本発明のアプローチは他のＬＤＰＣコードに適用することができるが、説明のために、（図４に説明されているような）ＬＤＰＣコードの１つの特定ファミリーに着目する。その１組のコードに関して説明を続けると、行列演算に関し、パリティビットの計算は以下のように表すことができる。
【００３０】
ｐ￣＝Ｂ-1Ａｉ￣
エンコーディングは先の行列乗算を実行することにより達成することができる。このエンコーディングプロセスはＬＤＰＣデコーダ１０１に対して適用することができる。説明のために、ＬＤＰＣは信頼伝搬（belief propagation）によりデコードされることを仮定する。
【００３１】
２つのケースを考える。第１のケースはデコーダ１０１のハードウェアを使用して一般的に任意の情報をエンコードすることを伴い（図５および図６）、第２のケースは同じハードウェアによりデコードされているデータを再エンコードすることに関する。原則として、第２のケースは第１のケースの特殊なケースであり、結果として、第１のケースとまったく同じように取り扱われる。代替では、単に前者のアプローチの特定なケースとしてこのケースを見るのではなく、異なるものとして見て、いくつかの効果が第２のケースの処理に伴う。
【００３２】
図５は本発明の実施形態にしたがった、データをエンコードするように使用される図１のＬＤＰＣデコーダの動作のフローチャートである。任意のハードウェア構成が有限精度（finite precision）を使用しなければならないことが認識される。したがって、以下のことが規定される。ＰＯＳＩＮＦおよびＮＥＧＩＮＦは、それぞれ１または−１（それぞれ論理０または１）をとるために、特定のチャネルビットに対する最尤比の最大値とする。第１のケースに対するエンコーディングアルゴリズムは次の通りである。
【００３３】
ステップ５０１において、モジュール１０３によって、デコーダ１０１は、最初のｋ個の受信値がｋ個の情報ビットからマッピングされ、論理０がＰＯＳＩＮＦにマッピングされ、論理１がＮＥＧＩＮＦにマッピングされるように、エンコードされるべきｋ個の情報ビットから“受信ベクトル”を組み立てる。最後のｎ−ｋ個の受信値はＰＯＳＩＮＦとして初期化される。次に、デコーダ１０１はステップ５０３において、デコーダ１０１の通常初期化を実行することにより、組み立てられたベクトル（すべてエッジ値）でモジュール１０５により初期化される。
【００３４】
ステップ５０５において、ｉ番目のチェックノードに対して、チェックノード処理エンジン１０７は以下の計算を行う。
【００３５】
ｄi＝ｇ（ｅ1,i，ｅ2,i，……，ｅνi-1）
ここで、νiはｉ番目のチェックノードに接続されたエッジ数である。一般性を失うことなく、ｅνiは非情報ビット（パリティチェックビット）に対応するビットノードに接続されたエッジであることを仮定する。
【００３６】
次に、デコーダ１０１はステップ５０７において、バイナリベクトルｂ￣＝（ｂ0，…，ｂn-k-1）への硬判定ｄ￣＝（ｄ0，…，ｄn-k-1）を実行する。最後のパリティチェックｐ￣は次のように計算される（ステップ５０９）。
【００３７】
【数１】
2005051756.tif 000003
先のプロセスから、デコーダ１０１の１反復の計算時間で、エンコーディングプロセスもデコーダ１０１により実行することができることが認められる。ＬＤＰＣデコーダ１０１が一般的に大半のコードのデコーディングのために少なくとも数１０反復を反復する必要がある事実を仮定すると、エンコーディングを実行する時間は一般的なＬＤＰＣフレームをデコードする時間の比較的わずかな部分である。
【００３８】
図６は本発明の実施形態にしたがった、データをエンコードするのに使用される図１のＬＤＰＣデコーダの修正された動作のフローチャートである。この修正されたプロセスは図５のものよりも小さいが、ステップ６０１において、最後のｎ−ｋ個の受信値はＰＯＳＩＮＦの代わりに“何もしない（ＤＯＮ‘Ｔ  ＣＡＲＥ）”（すなわちヌル値）として初期化される。ステップ６０３−６０９はステップ５０３−５０９に対応し、したがって説明しない。
【００３９】
図７は本発明にしたがった実施形態を実現することができるコンピュータシステムを図示している。コンピュータシステム７００は、バス７０１または情報を通信する他の通信メカニズムと、バス７０１に結合され、情報を処理するプロセッサ７０３とを含む。コンピュータシステム７００は、バス７０１に結合され、情報およびプロセッサ７０３により実行されるべき命令を記憶する、ランダムアクセスメモリ（ＲＡＭ）または他の動的記憶デバイスのような、メインメモリ７０５も含む。メインメモリ７０５は、プロセッサ７０３により実行されるべき命令を実行中に、一時的な変数や他の中間的な情報を記憶するのにも使用することができる。コンピュータシステム７００は、バス７０１に結合され、プロセッサ７０３のために静的情報および命令を記憶するリードオンリーメモリ（ＲＯＭ）７０７や他の静的記憶デバイスをさらに含む。磁気ディスクや光学ディスクのような記憶デバイス７０９は、情報および命令を記憶するためにバス７０１に付加的に結合される。
【００４０】
コンピュータシステム７００は、情報をコンピュータユーザに表示するために、陰極線管（ＣＲＴ）、液晶ディスプレイ、アクティブマトリクスディスプレイ、またはプラズマディスプレイのような、ディスプレイ７１１にバス７０１を介して結合されてもよい。英数字および他のキーを含むキーボードのような入力デバイス７１３は情報およびコマンド選択をプロセッサ７０３に通信するためにバス７０１に結合される。他のタイプのユーザ入力デバイスは、方向情報およびコマンド選択をプロセッサ７０３に通信し、ディスプレイ７１１上のカーソルの動きを制御するための、マウス、トラックボール、またはカーソル方向キーのようなカーソル制御７１５である。
【００４１】
本発明の１つの実施形態にしたがうと、ＬＤＰＣコードの発生はメインメモリ７０５に含まれている命令の配列を実行するプロセッサ７０３に応答して、コンピュータシステム７００により提供される。このような命令は、記憶デバイス７０９のような他のコンピュータ読み取り可能な媒体からメインメモリ７０５に読み込むことができる。メインメモリ７０５に含まれている命令の配列の実行はプロセッサ７０３にここで説明するプロセスステップを実行させる。マルチ処理構成の１つ以上のプロセッサを使用して、メインメモリ７０５に含まれている命令を実行してもよい。代替実施形態では、ソフトウェア命令の代わりにあるいはソフトウェア命令と組み合わせてハードワイヤード回路を使用して、本発明の実施形態を実現してもよい。したがって、本発明の実施形態はハードウェア回路およびソフトウェアの何らかの特定な組み合わせに限定されるものではない。
【００４２】
コンピュータシステム７００はバス７０１に結合された通信インターフェイス７１７も含む。通信インターフェイス７１７はローカルネットワーク７２１に接続されたネットワークリンク７１９に結合している２方向データ通信を提供する。例えば、通信インターフェイス７１７はデジタル加入者線（ＤＳＬ）カードまたはモデム、統合サービスデジタルネットワーク（ＩＳＤＮ）カード、ケーブルモデム、または電話モデムであって、対応するタイプの電話回線に対してデータ通信接続を提供してもよい。他の例として、通信インターフェイス７１７はローカルエリアネットワーク（ＬＡＮ）カード（例えば、イーサーネット（登録商標）や非同期転送モード（ＡＴＭ）ネットワーク）であって、互換性ＬＡＮへのデータ通信接続を提供してもよい。ワイヤレスリンクを実現することもできる。このような任意の構成において、通信インターフェイス７１７は、電気、電磁気または光の信号を送受信し、これらの信号はさまざまなタイプの情報を表すデジタルデータストリームを伝える。さらに、通信インターフェイス７１７は、ユニバーサルシリアルバス（ＵＳＢ）インターフェイス、ＰＣＭＣＩＡ（パーソナルコンピュータメモリカード国際協会）インターフェイスなどのような、周辺機器インターフェイスデバイスを含むことができる。
【００４３】
ネットワークリンク７１９は一般的に１つ以上のネットワークを通して他のデータデバイスに対してデータ通信を提供する。例えば、ネットワークリンク７１９はローカルネットワーク７２１を通してホストコンピュータ７２３への接続を提供し、ローカルネットワーク７２１はネットワーク７２５（例えば、ワイドエリアネットワーク（ＷＡＮ）または“インターネット”として現在一般的に言及されているグローバルパケットデータ通信ネットワーク）への接続性、またはサービスプロバイダにより運営されるデータ装置への接続性を有する。ローカルネットワーク７２１およびネットワーク７２５はともに電気、電磁気または光の信号を使用して、情報および命令を伝える。さまざまなネットワークを通る信号およびネットワークリンク７１９上の信号で通信インターフェイス７１７を通る信号は、情報および命令を伝達する搬送波の例示的な形態である。通信インターフェイス７１７はコンピュータシステム７００とデジタルデータを通信する。
【００４４】
コンピュータシステム７００はネットワーク、ネットワークリンク７１９および通信インターフェイス７１７を通して、メッセージを送信し、プログラムを含むデータを受信することができる。インターネットの例では、（示されていない）サーバは、ネットワーク７２５、ローカルネットワーク７２１および通信インターフェイス７１７を通して、本発明の実施形態を実現するアプリケーションプログラムに属する要求されたコードを送信してもよい。プロセッサ７０３は受信している間に送信されたコードを実行し、および／またはコードを後での実行のために記憶デバイス７０９または他の不揮発性記憶装置に記憶させてもよい。この方法では、コンピュータシステム７００は搬送波の形態でアプリケーションコードを得てもよい。
【００４５】
ここで使用されているような用語“コンピュータ読み取り可能な媒体”は、実行のためにプロセッサ７０３に命令を提供することに関係する任意の媒体に関係する。このような媒体は多くの形態をとることができ、これらに限定されないが、不揮発性媒体、揮発性媒体および送信媒体が含まれる。不揮発性媒体は、例えば記憶デバイス７０９のような光または磁気ディスクが含まれる。揮発性媒体はメインメモリ７０５のような動的メモリが含まれる。送信媒体は、バス７０１を構成するワイヤを含む、同軸ケーブル、銅線および光ファイバを含む。送信媒体は、無線周波数（ＲＦ）および赤外線（ＩＲ）データ通信中に発生されるもののような、音響、光または電磁気の波の形態もとることができる。コンピュータ読み取り可能な媒体の一般的な形態は、例えばフロッピ（登録商標）ディスク、フレキシブルディスク、ハードディスク、磁気テープ、他の任意の磁気媒体、ＣＤ−ＲＯＭ、ＣＤＲＷ、ＤＶＤ、他の任意の光媒体、パンチカード、紙テープ、光マークシート、穴や他の光学認識可能な表示のパターンを有する他の任意の物理媒体、ＲＡＭ、ＰＲＯＭ、ＥＰＲＯＭ、ＦＬＡＳＨ−ＥＰＲＯＭ、他の任意のメモリチップまたはカートリッジ、搬送波、あるいはコンピュータが読み取ることができる他の任意の媒体を含む。
【００４６】
さまざまな形態のコンピュータ読み取り可能な媒体は実行するためにプロセッサに命令を提供することに関係してもよい。例えば、本発明の少なくとも一部を実行する命令は遠隔コンピュータの磁気ディスク上に最初に記憶されてもよい。このようなシナリオでは、遠隔コンピュータは命令をメインメモリにロードして、その命令をモデムを使用して電話回線を通して送信する。ローカルコンピュータシステムのモデムは電話回線上でデータを受信し、赤外線送信機を使用して、データを赤外線信号に変換し、その赤外線信号を、パーソナルデジタルアシスタンス（ＰＤＡ）およびラップトップのようなポータブルコンピューテングデバイスに送信する。ポータブルコンピューテングデバイス上の赤外線検出器は赤外線信号により運ばれる情報および命令を受信し、データをバス上に置く。バスはそのデータをメインメモリに伝え、このメインメモリからプロセッサは命令を取り出して実行する。メインメモリにより受信される命令は、オプション的に、プロセッサにより実行される前または後に記憶デバイス上に記憶されてもよい。
【００４７】
したがって、本発明のさまざまな実施形態は複数の受信機への低密度パリティチェック（ＬＤＰＣ）コード化信号のブロードキャスト送信をサポートするアプローチを提供する。受信機はＬＤＰＣデコーダを含み、ＬＤＰＣデコーダはＬＤＰＣ信号をデコードして、デコード化信号を出力するとともに、入力信号をエンコードする。入力信号はデコード化信号とすることができ、これにより干渉相殺のために再エンコード化信号を使用する。上記アプローチは受信機中に独立した専用エンコーダを採用することを避ける効果がある。
【００４８】
本発明は多数の実施形態および構成とともに説明したが、本発明はそのように制限されるものではなく、さまざまな変形および均等構成をカバーし、これらも特許請求の範囲の範囲に入る。
【図面の簡単な説明】
【００４９】
【図１】図１は、本発明の実施形態にしたがった、ＬＤＰＣエンコーディングを実行することができるＬＤＰＣデコーダの図である。
【図２】図２は、本発明の実施形態にしたがった、希薄パリティチェック行列の図である。
【図３】図３は、図２の行列のＬＤＰＣコードの２部グラフの図である。
【図４】図４は、本発明の実施形態にしたがった、希薄パリティチェック行列の部分行列の図であり、部分行列は低位三角領域に制限されたパリティチェック値を含む。
【図５】図５は本発明の実施形態にしたがった、データをエンコードするのに使用される図１のＬＤＰＣデコーダの動作のフローチャートである。
【図６】図６は本発明の実施形態にしたがった、データをエンコードするのに使用される図１のＬＤＰＣデコーダの修正された動作のフローチャートである。
【図７】図７は本発明の実施形態にしたがった、ＬＤＰＣコードをエンコーディングおよびデコーディングするプロセスを実行することができるコンピュータシステムの図である。
【図１】
2005051756.tif 000004
【図２】
2005051756.tif 000005
【図３】
2005051756.tif 000006
【図４】
2005051756.tif 000007
【図５】
2005051756.tif 000008
【図６】
2005051756.tif 000009
【図７】
2005051756.tif 000010
【外国語明細書】
2005051756000001.pdf