(57)【特許請求の範囲】
【請求項１】
装置をしてデータの低密度パリティ検査（ＬＤＰＣ）符号化を実行させるための方法であって、前記装置に対して、
第１のＭ×Ｎパリティ検査行列を定義するステップと、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成するステップと、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングするステップと、
を実行させる方法。
【請求項２】
前記第２のパリティ検査行列から４サイクルを除去するステップをさらに含む、請求項１に記載の方法。
【請求項３】
前記第１のパリティ検査行列の前記定義が、前記第１のパリティ検査行列の行のサイクリック・シフトを含む、請求項１に記載の方法。
【請求項４】
前記Ｍ×Ｍ部分行列の主対角線に沿った要素に同一の値をセットするステップを含む、請求項１に記載の方法。
【請求項５】
データの低密度パリティ検査（ＬＤＰＣ）符号化装置であって、
第１のＭ×Ｎパリティ検査行列を定義する手段と、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手段と、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングする手段と、
を含む装置。
【請求項６】
前記第２のパリティ検査行列を生成する手段が、前記第２のパリティ検査行列から４サイクルを除去する手段をさらに含む、請求項５に記載の装置。
【請求項７】
前記第１のパリティ検査行列を定義する手段が、前記第１のパリティ検査行列の行をサイクリック・シフトする、請求項５に記載の装置。
【請求項８】
前記第１のパリティ検査行列を定義する手段が、前記Ｍ×Ｍ部分行列の主対角線に沿った要素に同一の値をセットする、請求項５に記載の装置。
【請求項９】
データの低密度パリティ検査（ＬＤＰＣ）符号化プログラムであって、前記符号化プログラムが、コンピュータ・システムに、
第１のＭ×Ｎパリティ検査行列を定義する手順と、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手順と、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングする手順と、
を実行させるプログラム。
【請求項１０】
前記第２のパリティ検査行列から４サイクルを除去する手順をさらにコンピュータ・システムに実行させる、請求項９に記載のプログラム。
【請求項１１】
前記第１のパリティ検査行列の定義が、前記第１のパリティ検査行列のサイクリック・シフトを含む、請求項９に記載のプログラム。
【請求項１２】
データの低密度パリティ検査（ＬＤＰＣ）符号化プログラムを格納したコンピュータ読み取り可能な記憶媒体であって、前記符号化プログラムが、コンピュータ・システムに、
第１のＭ×Ｎパリティ検査行列を定義する手順と、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手順と、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングする手順と、
を実行させるプログラムを格納したコンピュータ読み取り可能な記憶媒体。
【請求項１３】
通信チャネルを介して情報源から受信したデータを送信し、前記データを低密度パリティ検査（ＬＤＰＣ）符号語に符号化するデータ通信装置であって、
第１のＭ×Ｎパリティ検査行列を定義する手段と、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手段と、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングする手段と、
を含むデータ通信装置。
【請求項１４】
データ・ストレージ・チャネル内の情報源から受信したデータを記憶し、前記データを低密度パリティ検査（ＬＤＰＣ）符号語に符号化するデータ記憶装置であって、
第１のＭ×Ｎパリティ検査行列を定義する手段と、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手段と、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングする手段と、
を含むデータ記憶装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、全般的には、データの低密度パリティ検査（ＬＤＰＣ）符号化の方法および装置に関し、具体的には、データ通信および記憶システムのバイナリ変調およびマルチレベル変調のためのＬＤＰＣ符号語へのデータのマッピングのためのパリティ検査行列に基づくデータのブロック符号化に関する。
【０００２】
【従来の技術】
「Ｌｏｗ−ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ−ｃｈｅｃｋ  ｃｏｄｅｓ（ギャラガ（Ｇａｌｌａｇｅｒ）著／ＭＩＴ  Ｐｒｅｓｓ／米国マサチューセッツ州ケンブリッジ／１９６３年）」に、メッセージパッシング・デコーダに基づいて、バイナリ入力加法性白色ガウス雑音チャネル（ＡＷＧＮ）のチャネル容量に極めて近づくことができることが示された。それから、ＬＤＰＣ符号を多数の実用的な通信チャネルおよび記録チャネル上で容量に非常に近づけることができることが示された。したがって、ＬＤＰＣ符号は、ターボ符号の代替技術と考えられている。特に、ＬＤＰＣ符号は、ターボ符号よりすぐれた漸近性能を示し、エラー・フロアの影響が少なく、デコーダの複雑さと性能の間のさまざまなトレードオフを提供する。ＬＤＰＣ符号の長所は、その復号に使用されるｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムの実装があまり複雑でないことである。ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムの簡略化バージョン版では、完全なｓｕｍ−ｐｒｏｄｕｃｔ復号と比較して無視できる程度の復号性能の低下と引き換えに、複雑さが減らされる。
【０００３】
ハード・ディスクまたはテープ・システムなどの磁気記憶アプリケーションの多くでは、情報がバイナリ形式で記憶される。これらのアプリケーションでは、リード・ソロモン（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ）外符号に連接（ｃｏｎｃａｔｅｎａｔｅ）された変調内符号が、書き込まれた情報の信頼性の高い抽出のために使用される。ターボ符号およびＬＤＰＣ符号は、磁気記憶システムの面密度を、現在の使用可能な磁気コンポーネントの限界まで押し上げることができる。ハード・ディスクの現在のセクタ・サイズの制約が符号のブロック長を制限し、高い符号化率を要求しているにもかかわらず、単純な反復復号方式によって理論限界の約１．５ｄＢ以内に性能を高めることができることが示された。これは、既存のシステムと比較して重大な利得を表している。高効率ＬＤＰＣ符号は、磁気記憶システムの外符号として使用される時に、畳み込み符号またはターボ符号を超える利点を有すると思われる。たとえば、ＬＤＰＣ符号は、１０−８のエラー率でエラー・フロアの影響を受けないと思われる。さらに、ＬＤＰＣ符号のパリティ検査行列のまばらさ（ｓｐａｒｓｅｎｅｓｓ）によって、畳み込み外符号と直列に連接されたシステムと比較してより複雑でない復号アルゴリズムがもたらされる。また、インターリービングがＬＤＰＣ符号に潜在的に組み込まれているので、ＬＤＰＣエンコーダとチャネルの間のインターリーバは不要である。磁気記憶チャネルに関する従来のリード・ソロモン符号に対するＬＤＰＣ符号の潜在的な利益は、「Ｒｅｄｕｃｅｄ−Ｃｏｍｐｌｅｘｉｔｙ  Ｉｔｅｒａｔｉｖｅ  Ｄｅｃｏｄｉｎｇ  ｏｆ  Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ  Ｃｏｄｅｓ  ｆｏｒ  Ｇｅｎｅｒａｌｉｚｅｄ  Ｐａｒｔｉａｌ  Ｒｅｓｐｏｎｓｅ  Ｃｈａｎｎｅｌｓ（ミッテルホルツァ（Ｔ．  Ｍｉｔｔｅｌｈｏｌｚｅｒ）、ドラキア（Ａ．  Ｄｈｏｌａｋｉａ）、およびエレフテリオウ（Ｅ．  Ｅｌｅｆｔｈｅｒｉｏｕ）共著／ＩＥＥＥ  Ｔｒａｎｓ．  Ｍａｇｎ．，  ３７（２），  ｐｐ．  ７２１−７２８／２００１年３月）」に記載されている。ＬＤＰＣ符号によって、磁気記憶システムでは、面密度がその究極の限界まで押し上げられると期待される。
【０００４】
有線伝送システムおよび無線伝送システムを含む多くの通信システムには、伝送信号帯域幅に対する厳格な制限がある。そのような制限によって、２より多数のレベルを有する信号変調の必要が生じる。多くの従来のシステムでは、そのようなアプリケーションでトレリス符号化変調（ＴＣＭ）が使用される。しかし、ＴＣＭに関連する問題は、それが反復復号に適さないことである。したがって、許容可能な複雑さでの信号品質のさらなる改善は、達成が困難である。
【０００５】
「Ａ  ｔｕｒｂｏ  ＴＣＭ  ｓｃｈｅｍｅ  ｗｉｔｈ  ｌｏｗ  ｄｅｃｏｄｉｎｇ  ｃｏｍｐｌｅｘｉｔｙ  （Ｃａｔｅｎａ  Ｎｅｔｗｏｒｋｓ  Ｉｎｃ．／Ｔｅｍｐｏｒａｒｙ  Ｄｏｃｕｍｅｎｔ  ＢＩ−０９０，  ＩＴＵ−Ｔ  Ｓｔｕｄｙ  Ｇｒｏｕｐ  １５，  Ｑｕｅｓｔｉｏｎ  ４／インド／ゴア／２０００年１０月２３から２７日）」、「Ｐｒｏｐｏｓａｌ  ｏｆ  ｄｅｃｉｓｉｏｎ  ｍａｋｉｎｇ  ｆｏｒ  ｔｕｒｂｏ  ｃｏｄｉｎｇ  ａｎｄ  ｒｅｐｏｒｔ  ｏｆ  ｐｅｒｆｏｒｍａｎｃｅ  ｅｖａｌｕａｔｉｏｎ  ｏｆ  ｐｒｏｐｏｓｅｄ  ＴＴＣＭ（ＰＣＣＣ）  ｗｉｔｈ  Ｒ−Ｓ  ｃｏｄｅ  ａｎｄ  ｗｉｔｈｏｕｔ  Ｒ−Ｓ  ｃｏｄｅ  （Ｍｉｔｓｕｂｉｓｈｉ  Ｅｌｅｃｔｒｉｃ  Ｃｏｒｐ．／Ｔｅｍｐｏｒａｒｙ  Ｄｏｃｕｍｅｎｔ  ＢＩ−００３，  ＩＴＵ−Ｔ  Ｓｔｕｄｙ  Ｇｒｏｕｐ  １５／インド、ゴア／２０００年１０月２３から２７日）」および「Ｒｅｓｕｌｔｓ  ｏｆ  ｔｈｅ  ｒｅｑｕｉｒｅｍｅｎｔｓ  ｒｅｑｕｅｓｔｅｄ  ｉｎ  ｔｈｅ  ｃｏｄｉｎｇ  ａｄ  ｈｏｃ  ｒｅｐｏｒｔ（Ｖｏｃａｌ  Ｔｅｃｈｎｏｌｏｇｉｅｓ  Ｉｎｃ．／Ｔｅｍｐｏｒａｒｙ  Ｄｏｃｕｍｅｎｔ  ＨＣ−０７３，  ＩＴＵ−Ｔ  Ｓｔｕｄｙ  Ｇｒｏｕｐ  １５，  Ｑｕｅｓｔｉｏｎ  ４／カナダ、ハンツビル／２０００年６月３１日から８月４日」に、マルチレベルＡＤＳＬ伝送およびマルチレベルＶＤＳＬ伝送のターボ符号化方式が記載されている。これらのターボ符号化技法では、再帰的な規則正しい形での畳み込みエンコーダの並列連接（ｐａｒａｌｌｅｌ  ｃｏｎｃａｔｉｎａｔｉｏｎ）による情報ビットの符号化と、複数の可能なターボ復号技法の１つによる反復復号が用いられる。「Ｂｌｏｃｋ  ｐｒｏｄｕｃｔ  ｔｕｒｂｏ  ｃｏｄｅｓ  ｆｏｒ  Ｇ．ｄｍｔ．ｂｉｓ  ａｎｄ  Ｇ．ｌｉｔｅ．ｂｉｓ（Ｇｌｏｂｅｓｐａｎ  Ｉｎｃ．／Ｔｅｍｐｏｒａｒｙ  Ｄｏｃｕｍｅｎｔ  ＢＡ−０６３，  ＩＴＵ−Ｔ  Ｓｔｕｄｙ  Ｇｒｏｕｐ  １５，  Ｑｕｅｓｔｉｏｎ  ４／ベルギー、アントワープ／２０００年６月１９から２３日）」に、コンポーネントＢｏｓｅ−Ｃｈａｕｄｈｕｒｉ−Ｈｏｅｑｕｅｎｇｈｅｍ（ＢＣＨ）符号を使用するブロック・プロダクト・コードおよびＣｈａｓｅアルゴリズムに基づくそのソフト反復復号のアプリケーションが記載されている。さらなる複雑さが生じるものの、これらの技法はトレリス符号化に対するある程度の性能強化を提供する。
【０００６】
「Ｌｏｗ−ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ−ｃｈｅｃｋ  ｃｏｄｅｓ（ギャラガ（Ｒ．  Ｇ．  Ｇａｌｌａｇｅｒ）著／ＩＲＥ  Ｔｒａｎｓ．  Ｉｎｆｏ．  Ｔｈｅｏｒｙ，  ｖｏｌ．  ＩＴ−８，  ｐｐ．  ２１−２８／１９６２年１月）」、「Ｎｅａｒ  Ｓｈａｎｎｏｎ  ｌｉｍｉｔ  ｐｅｒｆｏｒｍａｎｃｅ  ｏｆ  ｌｏｗ  ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ  ｃｈｅｃｋ  ｃｏｄｅｓ（マッケイ（Ｄ．  Ｊ．  Ｃ．  ＭａｃＫａｙ）およびニール（Ｒ．  Ｍ．  Ｎｅａｌ）共著／Ｅｌｅｃｔｒｏｎ．  Ｌｅｔｔ．，  ｖｏｌ．  ３２，  ｎｏ．  １８，  ｐｐ．  １６４５−１６４６／１９９６年８月）」、「Ｇｏｏｄ  ｅｒｒｏｒ−ｃｏｒｒｅｃｔｉｎｇ  ｃｏｄｅｓ  ｂａｓｅｄ  ｏｎ  ｖｅｒｙ  ｓｐａｒｓｅ  ｍａｔｒｉｃｅｓ（マッケイ（Ｄ．  Ｊ．  Ｃ．  ＭａｃＫａｙ）著／ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  Ｉｎｆｏｒｍ．  Ｔｈｅｏｒｙ，  ｖｏｌ．  ４５，  Ｎｏ．  ２，  ｐｐ．  ３９９−４３１／１９９９年３月）」および「Ｒｅｄｕｃｅｄ  ｃｏｍｐｌｅｘｉｔｙ  ｉｔｅｒａｔｉｖｅ  ｄｅｃｏｄｉｎｇ  ｏｆ  ｌｏｗ  ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ  ｃｈｅｃｋ  ｃｏｄｅｓ  ｂａｓｅｄ  ｏｎ  ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ（フォッソリア（ＦＯＳＳＯＲＩＥＲ，  Ｍ．  Ｐ．  Ｃ．）、ミハルジェビック（ＭＩＨＡＬＪＥＶＩＣ，  Ｍ．）およびイマイ（ＩＭＡＩ，  Ｈ．）共著／ＩＥＥＥ  Ｔｒａｎｓ．  Ｃｏｍｍｕｎ．，  １９９９，  ４７，  （５），  ｐｐ．  ６７３−６８０）」に記載されている、ＬＤＰＣ符号の代替の符号化技法に関するアプリケーション開発は、これまで無線システムまたはディジタル磁気記録などのバイナリ変調を必要とするアプリケーションに焦点を合わせてきた。しかし、ＬＤＰＣ符号はマルチレベル伝送にも適用することができる。
【０００７】
「Ｂａｎｄｗｉｄｔｈ  ｅｆｆｉｃｉｅｎｔ  ｌｏｗ  ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ  ｃｈｅｃｋ  ｃｏｄｉｎｇ  ｕｓｉｎｇ  ｍｕｌｔｉｌｅｖｅｌ  ｃｏｄｉｎｇ  ａｎｄ  ｉｎｔｅｒａｔｉｖｅ  ｍｕｌｔｉｓｔａｇｅ  ｄｅｃｏｄｉｎｇ（ナラヤナン（Ｋ．  Ｒ．  Ｎａｒａｙａｎａｎ）およびリー（Ｊ．  Ｌｉ）共著／Ｐｒｏｃ．  Ｉｎｔ．  Ｓｙｍｐ．  ｏｎ  Ｔｕｒｂｏ−Ｃｏｄｅｓ、ｐｐ．  １６５−１６８／フランス、ブレスト／２０００年９月）」に、バイナリＬＤＰＣブロック符号に基づくマルチレベル符号化技法が記載されている。この技法では、ビット・インターリーブ式変調または反復マルチステージ復号を伴うマルチレベル符号化に、ＬＤＰＣブロック符号が使用される。この技法によるビット・インターリーブ式ＬＤＰＣ変調の場合、マルチレベル・シンボルの選択に使用されるビットのすべてが、ＬＤＰＣ符号ビットである。マルチレベル符号化に関して、複数のＬＤＰＣブロック符号が、マルチレベル方式のコンポーネント・コードとして使用される。この技法は、複数のＬＤＰＣエンコーダ／デコーダを必要とし、特に長いコードまたは大きいコンステレーション・サイズの場合にかなり実装が複雑となるという短所を有する。
【０００８】
「Ｌｏｗ  ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ  ｃｈｅｃｋ  ｃｏｄｅｄ  ｍｏｄｕｌａｔｉｏｎ  ｆｏｒ  ＡＤＳＬ（Ａｗａｒｅ  Ｉｎｃ．／Ｔｅｍｐｏｒａｒｙ  Ｄｏｃｕｍｅｎｔ  ＢＩ−０８１，  ＩＴＵ−Ｔ  Ｓｔｕｄｙ  Ｇｒｏｕｐ  １５，  Ｑｕｅｓｔｉｏｎ  ４／インド、ゴア／２０００年１０月２３から２７日）」にも、バイナリＬＤＰＣブロック符号に基づくマルチレベル符号化技法が記載されている。この技法は、ＴＣＭに類似するが、畳み込み符号化の代わりにＬＤＰＣ符号化が使用されることが異なる。具体的に言うと、ｓｅｔ  ｐａｒｔｉｔｉｏｎｉｎｇが、ＴＣＭで使用されるものと同一の原理に従う。この技法は、追加のＢｏｓｅ−Ｃｈａｕｄｈｕｒｉ−Ｈｏｅｇｕｅｎｇｈｅｍ（ＢＣＨ）符号を必要とし、これによってシステムの複雑になるという短所を有する。また、ＴＣＭおよび類似の方式で必要なｓｅｔ  ｐａｒｔｉｔｉｏｎｉｎｇは、軟（ソフト）判定ベースの復号技法について劣悪な性能につながる。
【０００９】
「Ｔｅｍｐｏｒａｒｙ  Ｄｏｃｕｍｅｎｔ  ＲＮ−２５  （ＩＴＵ  Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｔａｎｄａｒｄｉｚａｔｉｏｎ  Ｓｅｃｔｏｒ，  Ｓｔｕｄｙ  Ｇｒｏｕｐ  １５／米国ニュー・ジャージー／２００１年５月２１から２５日）」に、決定的（ｄｅｔｅｒｍｉｎｉｓｔｉｃ）ＬＤＰＣ方法と、ＡＤＳＬ伝送およびＡＤＳＬ  Ｌｉｔｅ伝送へのそのアプリケーションが記載されている。ここで提案された方法は、例えば、ガウス消去法を使用する、生成行列の事前の計算を必要とする。符号化には、Ｏ（Ｎ２）個の演算が必要となる。
【００１０】
送信される情報ビットの組を第１のグループおよび第２のグループに分割するステップと、ブロック符号を生成するために第１のグループを符号化するステップと、グレイコード化されたマッピング関数（Ｇｒａｙ−ｃｏｄｅｄ  ｍａｐｐｉｎｇ  ｆｕｎｃｔｉｏｎ）に従ってブロック・コードに依存するシンボルのコンステレーション内のシンボルのサブセットを選択するステップと、グレイコード化されたマッピング関数に従って第２のグループに依存するサブセット内のシンボルを選択するステップと、選択されたシンボルを送信するステップとを含むマルチレベル・データ通信の方法が存在する。この方法は、達成可能な符号化利得に関して優れた性能を提供する。符号化利得が生じるのは、ブロック符号化方式を反復的に復号することができ、これによって、トレリス符号化変調と比較してかなりの性能利得がもたらされるからである。この方法の特に好ましい実施形態には、インターリーブを必要としない、単純なｓｕｍ−ｐｒｏｄｕｃｔアルゴリズム（ＳＰＡ）またはその複雑さの低い派生技術を介して復号することができるＬＤＰＣ符号またはシンプル・プロダクト・コードに基づくマルチレベル符号化方式が含まれる。
【００１１】
ＬＤＰＣ符号に関連する不利益は、比較的高い符号化の複雑さが必要になることである。ＬＤＰＣ符号語が情報ブロックに符号の生成行列（ｇｅｎｅｒａｔｏｒ  ｍａｔｒｉｘ  ｏｆ  ｔｈｅ  ｃｏｄｅ）をかけることによって得られる場合、符号化には、Ｏ（Ｎ２）個の演算が必要である（Ｎは符号長を表す）。そのような符号化の手順は「時間的に線形（ｌｉｎｅａｒ  ｉｎ  ｔｉｍｅ）」ではない。さらに、指定されたＬＤＰＣパリティ検査行列から符号の生成行列を計算するために、前処理ステップが必要である。生成行列の計算には、ガウス消去法が含まれ、これは、Ｏ（Ｎ３）個の演算を必要とする。前処理は、特定のＬＤＰＣ検査行列について１回実行され、オフラインで実行され得るが、パリティ検査行列の系列（ｆａｍｉｌｙ）の１つの選択を必要とするアプリケーションに関する復号の時に、計算コストが極端に高くなる可能性がある。このことは、例えば、符号が接続ごとに選択されるｘＤＳＬの場合が該当する。ＬＤＰＣ符号の効率的な符号化に関する話題は、「Ｌｏｗ  ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ  ｃｈｅｃｋ  ｃｏｄｅｓ  ｗｉｔｈ  ｓｅｍｉ−ｒａｎｄｏｍ  ｐａｒｉｔｙ  ｃｈｅｃｋ  ｍａｔｒｉｘ（ピン（Ｌ．  Ｐｉｎｇ）、レウン（Ｗ．  Ｋ．  Ｌｅｕｎｇ）、およびファムド（Ｎ．  Ｐｈａｍｄｏ）共著／Ｅｌｅｃｔｒｏｎ．  Ｌｅｔｔｅｒｓ，  Ｖｏｌ．  ３５，  Ｎｏ．  １，  ｐｐ．  ３８−３９／１９９９年１月７日）」、「Ｃｏｍｐａｒｉｓｏｎ  ｏｆ  ｃｏｎｓｔｒｕｃｔｉｏｎｓ  ｏｆ  ｉｒｒｅｇｕｌａｒ  Ｇａｌｌａｇｅｒ  ｃｏｄｅｓ（マッケイ（Ｄ．  Ｊ．  Ｃ．  ＭａｃＫａｙ）、ウィルソン（Ｓ．  Ｔ．  Ｗｉｌｓｏｎ）、およびダベイ（Ｍ．  Ｃ．  Ｄａｖｅｙ）共著／ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，  Ｖｏｌ．  ４７，  Ｎｏ．  １０，  ｐｐ．  １４４９−１４５４／１９９９年１０月）」および「Ｅｆｆｉｃｉｅｎｔ  ｅｎｃｏｄｉｎｇ  ｏｆ  ｌｏｗ−ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ−ｃｈｅｃｋ  ｃｏｄｅｓ（リチャードソン（Ｒ．  Ｒｉｃｈａｒｄｓｏｎ）およびウルバンケ（Ｒ．  Ｌ．  Ｕｒｂａｎｋｅ）共著／ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，  Ｖｏｌ．  ４７．，  Ｎｏ．  ２，  ｐｐ．  ６３８−６５６／２００１年２月）」に示されている。
【００１２】
「Ｌｏｗ  ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ  ｃｈｅｃｋ  ｃｏｄｅｓ  ｗｉｔｈ  ｓｅｍｉ−ｒａｎｄｏｍ  ｐａｒｉｔｙ  ｃｈｅｃｋ  ｍａｔｒｉｘ（ピン（Ｌ．  Ｐｉｎｇ）、レウン（Ｗ．  Ｋ．  Ｌｅｕｎｇ）およびファムド（Ｎ．  Ｐｈａｍｄｏ）共著／Ｅｌｅｃｔｒｏｎ．  Ｌｅｔｔｅｒｓ，  Ｖｏｌ．  ３５，  Ｎｏ．  １，  ｐｐ．  ３８−３９／１９９９年１月７日）」では、ＬＤＰＣ符号のパリティ検査行列が、決定的部分（ｄｅｔｅｒｍｉｎｉｓｔｉｃ  ｐａｒｔ）とランダム部分（ｒａｎｄｏｍ  ｐａｒｔ）を含むという意味で「セミランダム」である。決定的部分は、効率的な符号化を可能にするために、帯状対角線すなわち「ジグザグ」形（ｂａｎｄ−ｄｉａｇｏｎａｌ  ｏｒ  ”ｚｉｇ−ｚａｇ”  ｆｏｒｍ）である。パリティ検査行列の残りは、４サイクルを避けてランダムに作成される。「Ｃｏｍｐａｒｉｓｏｎ  ｏｆ  ｃｏｎｓｔｒｕｃｔｉｏｎｓ  ｏｆ  ｉｒｒｅｇｕｌａｒ  Ｇａｌｌａｇｅｒ  ｃｏｄｅｓ（マッケイ（Ｄ．  Ｊ．  Ｃ．  ＭａｃＫａｙ）、ウィルソン（Ｓ．  Ｔ．  Ｗｉｌｓｏｎ）およびダベイ（Ｍ．  Ｃ．  Ｄａｖｅｙ）共著／ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，  Ｖｏｌ．  ４７，  Ｎｏ．  １０，  ｐｐ．  １４４９−１４５４／１９９９年１０月）」および「Ｅｆｆｉｃｉｅｎｔ  ｅｎｃｏｄｉｎｇ  ｏｆ  ｌｏｗ−ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ−ｃｈｅｃｋ  ｃｏｄｅｓ（リチャードソン（Ｒ．  Ｒｉｃｈａｒｄｓｏｎ）およびウルバンケ（Ｒ．  Ｌ．  Ｕｒｂａｎｋｅ）共著／ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，  Ｖｏｌ．  ４７．，  Ｎｏ．  ２，  ｐｐ．６３８−６５６／２００１年２月）」では、パリティ検査行列が、やはりランダム構成によって生成され、三角行列（ｔｒｉａｎｇｕｌａｒ）または「ほぼ三角行列（ａｐｐｒｏｘｉｍａｔｅ  ｔｒｉａｎｇｕｌａｒ）」であることが、効率的な符号化を可能にするために課せられる。これらの構成はそれぞれ、線形時間で符号化可能なＬＤＰＣ符号につながる。しかし、これには、下記を含む複数の短所がある。
（ａ）ランダムに構成されたパリティ検査符号は、少数のパラメータを介して指定することができない。言い換えると、パリティ検査行列の０でない要素のすべての位置を、個別に与えなければならない。
（ｂ）パリティ検査行列を三角行列またはほぼ三角行列にするために、しばしば前処理が必要になる。
（ｃ）得られる符号が、ランダムに構成されたＬＤＰＣ符号と比較して低い性能をもたらす。
【００１３】
【発明が解決しようとする課題】
線形時間の符号化の複雑さを有するＬＤＰＣ符号につながるパリティ検査行列を提供することが望ましい。また、完全に決定的（ｄｅｔｅｒｍｉｎｉｓｔｉｃ）であり、少数のパラメータを介して指定できるパリティ検査行列を提供することが望ましい。また、最小量の前処理を必要とするか前処理が不要なパリティ検査行列を提供することが望ましい。
【００１４】
【課題を解決するための手段】
本発明によれば、データの低密度パリティ検査（ＬＤＰＣ）符号化の方法であって、第１のＭ×Ｎパリティ検査行列を定義するステップと、第１のＭ×Ｎパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成するステップと、第２のパリティ検査行列に基づいてデータをＬＤＰＣ符号語にマッピングするステップとを含む方法が提供される。
【００１５】
この方法には、さらに、第２のパリティ検査行列から４サイクルを除去するステップを含めることができる。代替案では、パリティ検査行列の定義に、最初から４サイクルを除去するために、第１のパリティ検査行列の行のサイクリック・シフトを含めることができる。本発明の好ましい実施形態には、Ｍ×Ｍ部分行列の主対角線に沿った要素に同一の値をセットするステップが含まれる。
【００１６】
もう１つの態様から本発明を見ると、第１のＭ×Ｎパリティ検査行列を定義する手段と、第１のＭ×Ｎパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手段と、第２のパリティ検査行列に基づいてデータをＬＤＰＣ符号語にマッピングする手段とを含む、データの低密度パリティ検査（ＬＤＰＣ）符号化装置が提供される。
【００１７】
もう１つの態様から本発明を見ると、データの低密度パリティ検査（ＬＤＰＣ）符号化プログラムであって、前記符号化プログラムが、コンピュータ・システムに、第１のＭ×Ｎパリティ検査行列を定義する手順と、第１のＭ×Ｎパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手順と、第２のパリティ検査行列に基づいて、データをＬＤＰＣ符号語にマッピングする手順とを実行させるプログラムが提供される。また、そのようなプログラムを格納したコンピュータ読み取り可能な記憶媒体が提供可能であることは勿論である。
【００１８】
本発明は、通信チャネルを介して情報源から受信したデータを送信し、前記データを低密度パリティ検査（ＬＤＰＣ）符号語に符号化するデータ送信装置であって、第１のＭ×Ｎパリティ検査行列を定義する手段と、第１のＭ×Ｎパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手段と、第２のパリティ検査行列に基づいて、データをＬＤＰＣ符号語にマッピングする手段とを含む、データ送信装置にも拡張され得る。
【００１９】
本発明は、さらに、データ・ストレージ・チャネル内の情報源から受信したデータを記憶し、前記データが低密度パリティ検査（ＬＤＰＣ）符号語に符号化され、第１のＭ×Ｎパリティ検査行列を定義する手段と、第１のＭ×Ｎパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手段と、第２のパリティ検査行列に基づいて、データをＬＤＰＣ符号語にマッピングする手段とを含む、データ記憶装置に拡張され得る。
【００２０】
したがって、提供されるパリティ検査行列は、線形時間の符号化複雑さを有するＬＤＰＣ符号につながる。そのような行列は、完全に決定的であり、少数のパラメータを介して指定することができる。また、そのような行列は、最小量の前処理を必要とするか前処理が不要である。得られるコードの性能は、ランダムに構成されるＬＤＰＣ符号と同等またはそれ以上である。
【００２１】
これから説明する本発明の好ましい実施形態は、いわゆる「アレイ・コード」についてパリティ検査行列の構成を使用する。アレイ・コードは、「Ａｒｒａｙ  ｃｏｄｅｓ（ブラウム（Ｍ．  Ｂｌａｕｍ）、ファレル（Ｐ．  Ｆａｒｒｅｌｌ）およびティルボーグ（Ｈ．  ｖａｎ  Ｔｉｌｂｏｒｇ）共著／Ｈａｎｄｂｏｏｋ  ｏｆ  Ｃｏｄｉｎｇ  Ｔｈｅｏｒｙ，  Ｖ．  Ｓ．  Ｐｌｅｓｓ  ａｎｄ  Ｗ．  Ｃ．  Ｈｕｆｆｍａｎ  Ｅｄｓ．，  Ｅｌｓｅｖｉｅｒ／１９９８年）」に記載されている。ＬＤＰＣパリティ検査行列を得るためのアレイ・コードの構成の直接の適用は、「Ａｒｒａｙ  ｃｏｄｅｓ  ａｓ  ｌｏｗ−ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ−ｃｈｅｃｋ  ｃｏｄｅｓ（ファン（Ｊ．  Ｌ．  Ｆａｎ）／Ｐｒｏｃ．  Ｉｎｔ．  Ｓｙｍｐ．  ｏｎ  Ｔｕｒｂｏ  Ｃｏｄｅｓ、ｐｐ．  ５４３−５４６／フランス、ブレスト／２０００年９月）」および「ＬＤＰＣ  ｃｏｄｅｓ  ｆｏｒ  Ｇ．ｄｍｔ．ｂｉｓ  ａｎｄ  Ｇ．ｌｉｔｅ．ｂｉｓ（エルフテリオウ（Ｅ．  Ｅｌｅｆｔｈｅｒｉｏｕ）およびエルセール（Ｓ．  Ｏｅｌｃｅｒ）共著／Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｕｎｉｏｎ，  ＩＴＵ−Ｔ，  Ｓｔｕｄｙ  Ｇｒｏｕｐ  １５  ／  Ｑｕｅｓｔｉｏｎ  ４，  Ｔｅｍｐｏｒａｒｙ  Ｄｏｃｕｍｅｎｔ  ＣＦ−０６０／米国フロリダ州クリアウォーター／２００１年１月８から１２日）」に記載されている。最後に述べた２つの参考文献の符号は、少数のパラメータを介して指定されるが、線形時間で符号化することはできない。
【００２２】
【発明の実施の形態】
以下に、例示のみを目的として、添付図面を参照して本発明の好ましい実施形態を説明する。
【００２３】
以下では、
【数１】
0003575606.tif 000002
を「チルダＨ」と呼称する。
【００２４】
まず図１を参照すると、本発明の好ましい実施形態には、ディジタル加入者線（ＤＳＬ）通信チャネルなどの通信チャネル２０を介して受信機（図示せず）に接続される送信装置１０が含まれる。動作中に、送信装置１０は、コンピュータ・システム、携帯電話、固定回線電話、または類似するデータ通信端点などの情報源４０から情報ビット３０のシーケンスを受信する。送信装置１０は、通信チャネル２０を介して受信機に送信するために、情報ビット３０をシンボル５０に変換する。
【００２５】
図２を参照すると、本発明の特に好ましい実施形態では、送信装置１０に、分割器１００、分割器１００に接続されたブロック・エンコーダであるエンコーダ１１０、およびエンコーダ１１０と分割器１００に接続されたシンボル・マッパー１２０が含まれる。パリティ検査行列の行列ジェネレータ１６０が、エンコーダ１１０に接続される。動作中、分割器１００は、各変調の時に、情報源４０から通信される情報ビット３０の組を、第１のグループ１３０および第２のグループ１４０に分割する。エンコーダ１１０は、第２のグループ１４０を符号化して、行列ジェネレータによって供給されるパリティ検査行列に基づいてブロック符号１５０を生成する。パリティ検査行列は、コード・パラメータ１７０に基づいて行列ジェネレータによって生成される。シンボル・マッパー１２０は、グレイコード化されたマッピング関数に従って、ブロック符号１５０に依存するシンボルのコンステレーション内のシンボルのサブセットを選択する。シンボル・マッパー１２０は、グレイコード化されたマッピング関数に従って、第１のグループ１３０に依存する、サブセット内のシンボルも選択する。選択されたシンボル５０が、通信チャネル２０を介して受信機に通信される。分割器１００は、シフト・レジスタまたは類似する論理機能によって実施することができる。送信装置１０を、（１）ハードワイヤード・ロジック（結線論理）によって、（２）コンピュータ・プログラム・コードを用いてプログラムされた汎用プロセッサ／専用ディジタル信号プロセッサによって、または（３）ハードワイヤード・ロジックとコンピュータ・プログラム・コードの組み合わせによって、実施できることに留意されたい。
【００２６】
図３を参照すると、図２に関して既に本明細書で説明した送信装置１０の変更形態では、分割器１００が省略され、エンコーダ１１０が、情報源４０から受信した情報ビット３０のすべてを符号化して、ブロック符号１５０を生成する。シンボル・マッパー１２０が、グレイコード化されたマッピング関数に従って、ブロック符号１５０に依存するシンボルのコンステレーション内のシンボルを選択する。選択されたシンボル５０が、通信チャネル２０を介して受信機に通信される。
【００２７】
図４を参照すると、本発明の好ましい実施形態では、行列ジェネレータ１６０に、三角行列ジェネレータ３１０に接続された行列定義ロジック３００が含まれる。図５を参照すると、ステップ３５０で、動作中、行列定義ロジック３００が、入力のコード・パラメータ１７０に基づいて第１のＭ×Ｎパリティ検査行列３２０を定義する。ステップ３６０で、三角行列ジェネレータ３１０が、第１の行列に基づいて第２の行列を生成する。第２の行列は、Ｍ×Ｍの三角行列である部分行列を有する。ステップ３７０で、第２の行列が、行列ジェネレータ１６０からエンコーダ１１０に供給される。エンコーダ１１０へのデータ入力が、第２の行列に基づいてＬＤＰＣ符号語にマッピングされる。本発明の好ましい実施形態でのパリティ検査行列の定義および三角行列の生成の２つの手法を、図６および図７に関してこれから説明する。
【００２８】
図６を参照すると、本発明の好ましい実施形態では、行列生成に、３つのステップ、１、２、および３が含まれる。ステップ１では、行列Ｈを、アレイ・コードに関するパリティ検査行列（ｐａｒｉｔｙ−ｃｈｅｃｋ  ｍａｔｒｉｃｅｓ  ｆｏｒ  ａｒｒａｙ  ｃｏｄｅｓ）の定義に従って定義する。ステップ２は、上三角構造（ｕｐｐｅｒ−ｔｒｉａｎｇｕｌａｒ  ｓｔｒｕｃｔｕｒｅ）を実現するために行列Ｈを決定的に修正する三角化（ｔｒｉａｎｇｕｌａｒｉｚａｔｉｏｎ）ステップである。ステップ３には、第２のステップで導入された可能性がある４サイクルを除去する単純な手順が含まれる。
【００２９】
＜ステップ１：Ｈの定義（Ｄｅｆｉｎｉｔｉｏｎ  ｏｆ  Ｈ）＞
アレイ・コード風のＬＤＰＣパリティ検査行列Ｈは、３つのパラメータすなわち、素数ｐと２つの整数ｋ，ｊ（ｋ，ｊ≦ｐ）によって定義される。行列Ｈは、次元ｊｐ×ｋｐを有し、次式によって与えられる。
【数２】
0003575606.tif 000003
ここで、Ｉは、ｐ×ｐ単位行列であり、ａは、シングル・レフト（またはライト）・サイクリック・シフトを表すｐ×ｐ置換行列であり、例えば、
【数３】
0003575606.tif 000004
である。パラメータｊ，ｋは、それぞれＨの列数および行数を提供する。構成により、行列Ｈは、４サイクル・フリー（４サイクルなしの状態）である。言い換えるならば、複数の位置にオーバーラップする１を有する行はない。
【００３０】
Ｈは、符号語長Ｎ＝ｋｐとパリティ検査数Ｍ＝ｊｐを有するＬＤＰＣ符号の系列のパリティ検査行列を表す。符号語長Ｎ’（＜Ｎ）またはパリティ検査数Ｍ’（＜Ｍ）を有するＬＤＰＣ符号は、Ｈの右端の（Ｎ−Ｎ’）列および下端の（Ｍ−Ｍ’）行を破棄することによって簡単に得られる。結果として得られるＭ’×Ｎ’行列が、使用される行列のサイズの明白な修正と共に、ステップ２および３でＨの代わりに使用される。
【００３１】
＜ステップ２：Ｈの三角化（Ｔｒｉａｎｇｕｌａｒｉｚａｔｉｏｎ  ｏｆ  Ｈ）＞
Ｈが、ブロック行列形式
Ｈ＝［Ｈ１｜Ｈ２］
で表され、Ｈ１が、次元ｊｐ×ｊｐを有し、Ｈ２が、次元ｊｐ×（ｋ−ｊ）ｐを有するものとする。Ｕが、Ｈ１の主対角線（ｍａｉｎ  ｄｉａｇｏｎａｌ）上の各要素を１に置換し、主対角線の下のすべての要素に０をセットすることによってＨ１から得られるｊｐ×ｊｐの上三角行列であるものとする。ｊｐ×ｋｐの行列
ＨＵ＝［Ｕ｜Ｈ２］
によって、線形時間で符号化可能なＬＤＰＣ符号のパリティ検査行列が定義される。
【００３２】
行列Ｈが、構成によって４サイクルがないが、ＨＵが、上三角行列Ｕを導入したことに起因して、４サイクル・フリーではない場合があることに留意されたい。しかし、４サイクルは、次のステップで示されるように、簡単に検出され、除去される。
【００３３】
＜ステップ３：４サイクルの除去（Ｅｌｉｍｉｎａｔｉｏｎ  ｏｆ  ４−ｃｙｃｌｅｓ）＞
Ａ＝ＨＵ・ＨＵＴであるものとする。ただし、Ｔは行列転置を表す。Ａの対角要素ａｍ，ｍ，ｍ＝１，…，ｊｐによって、行ｍのハミング重さ、すなわち、行列ＨＵのパリティ検査ｍによって検査されるシンボルの数が与えられる。非対角要素ａｍ，ｎ、ｍ，ｎ＝１，…，ｊｐ、ｍ≠ｎによって、パリティ検査ｍおよびパリティ検査ｎの両方によって検査されるシンボルの数が与えられる。４サイクルなしでは、ａｍ，ｎ≦１である。
【００３４】
したがって、パリティ検査行列が４サイクル・フリーであることを保証するためには、（ａ）Ａ＝ＨＵ・ＨＵＴの下三角部分（ｌｏｗｅｒ−ｔｒｉａｎｇｕｌａｒ  ｐａｒｔ）を計算し、（ｂ）ａｍ，ｎ＞１、（ｍ，ｎ＝１，…，ｊｐ；ｍ＜ｎ）の場合に、ＨＵの第（ｎ，ｍ）要素に０をセットする。
【００３５】
チルダＨＵによって、ステップ３の最後に得られる行列を表す。チルダＨＵによって定義されるＬＤＰＣ符号は、符号語長Ｎ＝ｋｐ、パリティ検査数Ｍ＝ｊｐ、および情報ブロック長Ｋ＝（ｋ−ｊ）ｐを有する。チルダＨＵを使用することによる線形時間符号化の可能性を、次に示す。
【００３６】
効率的な符号化は、符号の生成行列を計算する必要なしに、パリティ検査行列チルダＨＵから直接に達成される。ＬＤＰＣ符号が線形ブロック符号なので、Ｎタプル（Ｎ−ｔｕｐｌｅ）ｘは、ＯがＭ×１の零ベクトルであるものとして、チルダＨＵ・ｘ＝０の場合に限ってＬＤＰＣ符号語になる。このベクトルｘは、次の形で表すことができる。
【数４】
0003575606.tif 000005
ここで、ｊｐ×１のベクトルｐが、符号語ｘのパリティ部分、（ｋ−ｊ）ｐ×１のベクトルｓが、符号語ｘの組織的部分を表す。ｐのｊｐ個のパリティ・ビットは、
【数５】
0003575606.tif 000006
を使用し、チルダＨＵの上三角形式を使用することによって、再帰的な形で得られる。これを示すために、ベクトルｐおよびｓの両方が、ｐ×１の部分ベクトルに分割されるものとする。
【数６】
0003575606.tif 000007
ここで、ｐｉ＝｛ｐｉ，ｎ；ｎ＝１，２，…，ｐ｝、ｉ＝１，２，…，ｊであり、ｓｉ＝｛ｓｉ，ｎ；ｎ＝１，２，…，ｐ｝、ｉ＝１，２，…，ｋ−ｊである。すると、ｐｍの要素が、下記の再帰の組によって、ｍ＝ｊ、ｊ−１、…、１について得られる。
【数７】
0003575606.tif 000008
ここで、第２の添字、ｐｌ、…およびｓｌ、…は、行列ａのべきによって割り当てられる特定の値に依存するが、表記が長くならないように省略されたものである。括弧内に示された項は、やはり行列ａのべきの特定の値に依存して、実際には存在しない場合がある。
【００３７】
したがって、上の符号化処理は、パリティ検査行列チルダＨＵの三角形構造（ｔｒｉａｎｇｕｌａｒ  ｓｔｒｕｃｔｕｒｅ）およびそのまばらさ（ｓｐａｒｓｉｔｙ）を利用している。ｒが符号化率であるものとして、符号化が約
【数８】
0003575606.tif 000009
回のＸＯＲ演算を必要とすることを示すことができる。
【００３８】
図７を参照すると、図６に関して既に説明した手法の変更形態に、２つのステップ１’および２’が含まれる。ステップ１’および２’を、これから詳細に説明する。
【００３９】
＜ステップ１’：ＨＳの定義（Ｄｅｆｉｎｉｔｉｏｎ  ｏｆ  ＨＳ）＞
行列ＨＳは、ブロック単位の形で、行列Ｈの行をサイクリック・シフトすることによって定義される。各ブロック−行のサイクリック・シフトの量は、ＨＳの左端のｊｐ×ｊｐ個のサブ・ブロックに、その対角線に沿って単位行列Ｉが含まれるようになる量である。
【数９】
0003575606.tif 000010
ＨＳは、サイクリック・シフトのみを介してＨから得られたので、それぞれｊおよびｋによって与えられる列および行の重さを有し、４サイクルフリーである。
【００４０】
＜ステップ２’：ＨＳの三角化（Ｔｒｉａｎｇｕｌａｒｉｚａｔｉｏｎ  ｏｆ  ＨＳ）＞
行列ＨＳは、左端のｊｐ×ｊｐ個のサブ・ブロックの下三角要素を０に置換することによって三角化される。その結果、下記の行列ＨＵＳが得られる。
【数１０】
0003575606.tif 000011
ここで、Ｏは、ｐ×ｐの零行列である。
【００４１】
ＨＵＳによって定義されるＬＤＰＣ符号は、符号語長Ｎ＝ｋｐ、パリティ検査数Ｍ＝ｊｐ、および情報ブロック長Ｋ＝（ｋ−ｊ）ｐを有する。また、ＨＵＳは、４サイクル・フリーである。明らかに、ＨＵＳによって定義されるＬＤＰＣ符号は、線形時間での符号化が可能である。
【００４２】
符号語長Ｎ’（＜Ｎ）またはパリティ検査数Ｍ’（＜Ｍ）を有するＬＤＰＣ符号は、ＨＵＳの右端の（Ｎ−Ｎ’）列および下端の（Ｍ−Ｍ’）行を破棄することによって、簡単に得られる。
【００４３】
効率的な符号化は、図６に関して前に説明した手法に関して前に説明したものと同一の形で達成される。ｒが符号化率であるものとして、
【数１１】
0003575606.tif 000012
回のＸＯＲ演算が必要であることを示すことができる。
【００４４】
図６および７に関して本明細書で前に説明した本発明の実施形態で得られるパリティ検査行列は、三角行列を有する。「Ｃｏｍｐａｒｉｓｏｎ  ｏｆ  ｃｏｎｓｔｒｕｃｔｉｏｎｓ  ｏｆ  ｉｒｒｅｇｕｌａｒ  Ｇａｌｌａｇｅｒ  ｃｏｄｅｓ（マッケイ（Ｄ．  Ｊ．  Ｃ．  ＭａｃＫａｙ）、ウィルソン（Ｓ．  Ｔ．  Ｗｉｌｓｏｎ）およびダベイ（Ｍ．  Ｃ．  Ｄａｖｅｙ）共著／ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，  Ｖｏｌ．  ４７，  Ｎｏ．  １０，  ｐｐ．  １４４９−１４５４／１９９９年１０月）」と、「Ｅｆｆｉｃｉｅｎｔ  ｅｎｃｏｄｉｎｇ  ｏｆ  ｌｏｗ−ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ−ｃｈｅｃｋ  ｃｏｄｅｓ／リチャードソン（Ｒ．  Ｒｉｃｈａｒｄｓｏｎ）およびウルバンケ（Ｒ．  Ｌ．  Ｕｒｂａｎｋｅ）共著／ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，  Ｖｏｌ．  ４７．，  Ｎｏ．  ２，  ｐｐ．６３８−６５６／２００１年２月）」に、「ほぼ三角形」の形
【数１２】
0003575606.tif 000013
（Ｃ、Ｄ、Ｅ、およびＴは適当な次元の行列であり、Ｔ行列が上三角行列である。）のパリティ検査行列を有するＬＤＰＣ符号についても、高速な符号化が可能であることが示されている。そのような形は、図６および７に関して本明細書で前に説明した手法を一般化することによって、効率的に得ることができる。
【００４５】
たとえば、図６に関して本明細書で前に説明した手法に従う場合には、ほぼ三角行列を生成するために、ステップ１は同一のままであるが、行列Ｈを、ブロック行列形式で
【数１３】
0003575606.tif 000014
として同等に記述することができる。ここで、Ｈ５は、ｔｐ×ｔｐの行列であり、整数ｔ≦ｊであり、行列Ｈ３、Ｈ４、およびＨ６は、適当な次元を有する。ステップ２に類似する三角化ステップを、Ｈ５に適用する。Ｕ５が、Ｈ５の主対角線の各要素を１に置換し、主対角線の下のすべての要素に０をセットすることによってＨ５から得られるｔｐ×ｔｐ上三角行列であるものとする。
【００４６】
ｊｐ×ｋｐの行列
【数１４】
0003575606.tif 000015
は、ほぼ三角行列であり、したがって、これによって、前述の「Ｃｏｍｐａｒｉｓｏｎ  ｏｆ  ｃｏｎｓｔｒｕｃｔｉｏｎｓ  ｏｆ  ｉｒｒｅｇｕｌａｒ  Ｇａｌｌａｇｅｒ  ｃｏｄｅｓ（マッケイ（Ｄ．  Ｊ．  Ｃ．  ＭａｃＫａｙ）、ウィルソン（Ｓ．  Ｔ．  Ｗｉｌｓｏｎ）およびダベイ（Ｍ．  Ｃ．  Ｄａｖｅｙ）共著／ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，  Ｖｏｌ．  ４７，  Ｎｏ．  １０，  ｐｐ．  １４４９−１４５４／１９９９年１０月）」と、「Ｅｆｆｉｃｉｅｎｔ  ｅｎｃｏｄｉｎｇ  ｏｆ  ｌｏｗ−ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ−ｃｈｅｃｋ  ｃｏｄｅｓ（リチャードソン（Ｒ．  Ｒｉｃｈａｒｄｓｏｎ）およびウルバンケ（Ｒ．  Ｌ．  Ｕｒｂａｎｋｅ）共著／ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，  Ｖｏｌ．  ４７．，  Ｎｏ．  ２，  ｐｐ．６３８−６５６／２００１年２月）」による高速な符号化が可能なＬＤＰＣ符号のパリティ検査行列が定義される。その後、ステップ３をこのほぼ三角形の行列に適用して、４サイクルを除去する。
【００４７】
明らかに、ステップ１の行列Ｈを、行方向および列方向に切り詰めて、符号語長およびパリティ検査数の特定の値を実現することができる。
【００４８】
前に示したように、図７に関して本明細書で前に説明した手法も、ほぼ三角形のパリティ検査行列を得るのに使用することができる。この目的のためには、行列ＨＳのｔ−１個の下側ブロック行を右にサイクリック・シフトすることによって、ステップ１’を変更する。すなわち、最も下のブロック行が、ｔ−１位置だけシフトされ、次に上のブロック行が、ｔ−２位置だけシフトされる。その後、ステップ２’を、そのようにして得られた行列の左下のｔｐ×ｔｐ部分行列だけに適用して、ほぼ三角形の新しい行列をもたらす。行列全体が、ほぼ三角行列であり、４サイクルがなく、「Ｃｏｍｐａｒｉｓｏｎ  ｏｆ  ｃｏｎｓｔｒｕｃｔｉｏｎｓ  ｏｆ  ｉｒｒｅｇｕｌａｒ  Ｇａｌｌａｇｅｒ  ｃｏｄｅｓ（マッケイ（Ｄ．  Ｊ．  Ｃ．  ＭａｃＫａｙ）、ウィルソン（Ｓ．  Ｔ．  Ｗｉｌｓｏｎ）、およびダベイ（Ｍ．  Ｃ．  Ｄａｖｅｙ）共著／ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，  Ｖｏｌ．  ４７，  Ｎｏ．  １０，  ｐｐ．  １４４９−１４５４／１９９９年１０月）」と、「Ｅｆｆｉｃｉｅｎｔ  ｅｎｃｏｄｉｎｇ  ｏｆ  ｌｏｗ−ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ−ｃｈｅｃｋ  ｃｏｄｅｓ（リチャードソン（Ｒ．  Ｒｉｃｈａｒｄｓｏｎ）およびウルバンケ（Ｒ．  Ｌ．  Ｕｒｂａｎｋｅ）共著／ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，  Ｖｏｌ．  ４７．，  Ｎｏ．  ２，  ｐｐ．６３８−６５６／２００１年２月）」に従う高速ＬＤＰＣ符号化に直接に使用することができる。
【００４９】
やはり、ステップ２’の終りに得られる行列を、行方向および列方向に切り詰めて、符号語長およびパリティ検査数の特定の値を達成することができる。
【００５０】
本発明のいくつかの実施形態では、パリティ検査行列を、通信チャネル２０を介する受信機への送信装置１０の接続の際に、行列定義ロジック３００によって定義することができる。たとえば、行列を、通信チャネル２０の端点間で折衝された次元に基づいて、接続時に行列定義ロジック３００によって作成することができる。具体的に言うと、パリティ検査行列を、受信機から送信装置１０へのコード・パラメータ１７０の供給に基づいて決定することができる。本発明の他の実施形態では、パリティ検査行列を、接続が確立される前に、行列定義ロジック３００によって定義することができる。たとえば、１つまたは複数のパリティ検査行列を、行列定義ロジック３００内で事前設定することができ、各事前設定された行列が、事前設定されたコード長（列数）および事前設定されたパリティ検査数（行数）を有する。複数の事前設定された行列を有する実施形態では、接続の確立時に、適当な行列が、行列定義ロジック３００に対して選択される。そのような選択は、たとえば、前に説明したように通信チャネル２０の端点間の折衝に基づいて実行することができる。
【００５１】
本発明の好ましい実施形態を、これまでは通信システムに関して説明した。しかし、本発明は、そのようなシステムへの適用に制限されない。たとえば、図８を参照すると、前に説明したエンコーダ１１０の実施形態を、情報源４０からのデータをハード・ディスク・ストレージ・チャネルなどのストレージ・チャネルに記憶するデータ記憶システム２１０で使用することもできる。
【００５２】
本明細書で前に説明した送信装置１０、エンコーダ１１０、および行列ジェネレータ１６０のそれぞれを、（１）ハードワイヤード・ロジックによって、（２）コンピュータ・プログラム・コードを用いてプログラムされた汎用プロセッサ／専用ディジタル信号プロセッサによって、または（３）ハードワイヤード・ロジックとコンピュータ・プログラム・コードの組み合わせによって、実施できることを諒解されたい。たとえば、図９を参照すると、前に図２に関して説明したデータ通信システムで、送信装置１０に、メモリ４１０に接続されたプログラマブル・ディジタル信号プロセッサ（ＤＳＰ）４００を含めることができ、メモリ４１０にコンピュータ・プログラム・コード４２０が記憶され、コンピュータ・プログラム・コード４２０が、ＤＳＰ４００によって実行される時に、図５に関して前に説明した方法のステップを実行するようにＤＳＰ４００を構成する。
【００５３】
本明細書で好ましい実施形態に関して本発明を説明したが、当業者は、本発明の範囲から逸脱せずに、形態および詳細におけるさまざまな変更を行うことができることを諒解するであろう。
【００５４】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００５５】
（１）データの低密度パリティ検査（ＬＤＰＣ）符号化の方法であって、
第１のＭ×Ｎパリティ検査行列を定義するステップと、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成するステップと、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングするステップと、
を含む方法。
（２）前記第２のパリティ検査行列から４サイクルを除去するステップをさらに含む、上記（１）に記載の方法。
（３）前記第１のパリティ検査行列の前記定義が、前記第１のパリティ検査行列の行のサイクリック・シフトを含む、上記（１）に記載の方法。
（４）前記Ｍ×Ｍ部分行列の主対角線に沿った要素に同一の値をセットするステップを含む、上記（１）に記載の方法。
（５）データの低密度パリティ検査（ＬＤＰＣ）符号化装置であって、
第１のＭ×Ｎパリティ検査行列を定義する手段と、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手段と、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングする手段と、
を含む装置。
（６）前記第２のパリティ検査行列を生成する手段が、前記第２のパリティ検査行列から４サイクルを除去する手段をさらに含む、上記（５）に記載の装置。
（７）前記第１のパリティ検査行列を定義する手段が、前記第１のパリティ検査行列の行をサイクリック・シフトする、上記（５）に記載の装置。
（８）前記第１のパリティ検査行列を定義する手段が、前記Ｍ×Ｍ部分行列の主対角線に沿った要素に同一の値をセットする、上記（５）に記載の装置。
（９）データの低密度パリティ検査（ＬＤＰＣ）符号化プログラムであって、前記符号化プログラムが、コンピュータ・システムに、
第１のＭ×Ｎパリティ検査行列を定義する手順と、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手順と、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングする手順と、
を実行させるプログラム。
（１０）前記第２のパリティ検査行列から４サイクルを除去する手順をさらにコンピュータ・システムに実行させる、上記（９）に記載のプログラム。
（１１）前記第１のパリティ検査行列の定義が、前記第１のパリティ検査行列のサイクリック・シフトを含む、上記（９）に記載のプログラム。
（１２）データの低密度パリティ検査（ＬＤＰＣ）符号化プログラムを格納したコンピュータ読み取り可能な記憶媒体であって、前記符号化プログラムが、コンピュータ・システムに、
第１のＭ×Ｎパリティ検査行列を定義する手順と、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手順と、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングする手順と、
を実行させるプログラムを格納したコンピュータ読み取り可能な記憶媒体。
（１３）通信チャネルを介して情報源から受信したデータを送信し、前記データを低密度パリティ検査（ＬＤＰＣ）符号語に符号化するデータ通信装置であって、
第１のＭ×Ｎパリティ検査行列を定義する手段と、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手段と、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングする手段と、
を含むデータ通信装置。
（１４）データ・ストレージ・チャネル内の情報源から受信したデータを記憶し、前記データを低密度パリティ検査（ＬＤＰＣ）符号語に符号化するデータ記憶装置であって、
第１のＭ×Ｎパリティ検査行列を定義する手段と、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手段と、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングする手段と、
を含むデータ記憶装置。
【図面の簡単な説明】
【図１】通信システムのブロック図である。
【図２】通信システムの送信装置のブロック図である。
【図３】通信システムのもう１つの送信装置のブロック図である。
【図４】送信装置の行列ジェネレータのブロック図である。
【図５】送信装置のエンコーダ機能に対応する流れ図である。
【図６】行列ジェネレータに対応する流れ図である。
【図７】行列ジェネレータに対応するもう１つの流れ図である。
【図８】データ記憶システムのブロック図である。
【図９】通信システムの送信装置のもう１つの例のブロック図である。
【符号の説明】
１０  送信装置
２０  通信チャネル
３０  情報ビット
４０  情報源
５０  シンボル
１００  分割器
１１０  エンコーダ
１２０  シンボル・マッパー
１３０  第１のグループ
１４０  第２のグループ
１５０  ブロック・コード
１６０  行列ジェネレータ
１７０  コード・パラメータ
２１０  データ記憶システム
３００  行列定義ロジック
３１０  三角行列ジェネレータ
３２０  第１のＭ×Ｎパリティ検査行列
４００  プログラマブル・ディジタル信号プロセッサ（ＤＳＰ）
４１０  メモリ
４２０  コンピュータ・プログラム・コード
【図１】
0003575606.tif 000016
【図２】
0003575606.tif 000017
【図３】
0003575606.tif 000018
【図４】
0003575606.tif 000019
【図５】
0003575606.tif 000020
【図６】
0003575606.tif 000021
【図７】
0003575606.tif 000022
【図８】
0003575606.tif 000023
【図９】
0003575606.tif 000024