JP3575606B2 - データの低密度パリティ検査符号化方法および装置 - Google Patents
データの低密度パリティ検査符号化方法および装置 Download PDFInfo
- Publication number
- JP3575606B2 JP3575606B2 JP2002199657A JP2002199657A JP3575606B2 JP 3575606 B2 JP3575606 B2 JP 3575606B2 JP 2002199657 A JP2002199657 A JP 2002199657A JP 2002199657 A JP2002199657 A JP 2002199657A JP 3575606 B2 JP3575606 B2 JP 3575606B2
- Authority
- JP
- Japan
- Prior art keywords
- parity check
- matrix
- check matrix
- data
- ldpc
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L1/00—Arrangements for detecting or preventing errors in the information received
- H04L1/004—Arrangements for detecting or preventing errors in the information received by using forward error control
- H04L1/0056—Systems characterized by the type of code used
- H04L1/0057—Block codes
- H04L1/0058—Block-coded modulation
-
- G—PHYSICS
- G11—INFORMATION STORAGE
- G11B—INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER
- G11B20/00—Signal processing not specific to the method of recording or reproducing; Circuits therefor
- G11B20/10—Digital recording or reproducing
- G11B20/18—Error detection or correction; Testing, e.g. of drop-outs
- G11B20/1833—Error detection or correction; Testing, e.g. of drop-outs by adding special lists or symbols to the coded information
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
- H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
- H03M13/1148—Structural properties of the code parity-check or generator matrix
- H03M13/116—Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices
- H03M13/1162—Array based LDPC codes, e.g. array codes
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
- H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
- H03M13/1148—Structural properties of the code parity-check or generator matrix
- H03M13/118—Parity check matrix structured for simplifying encoding, e.g. by having a triangular or an approximate triangular structure
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/25—Error detection or forward error correction by signal space coding, i.e. adding redundancy in the signal constellation, e.g. Trellis Coded Modulation [TCM]
- H03M13/255—Error detection or forward error correction by signal space coding, i.e. adding redundancy in the signal constellation, e.g. Trellis Coded Modulation [TCM] with Low Density Parity Check [LDPC] codes
Landscapes
- Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Mathematical Physics (AREA)
- Probability & Statistics with Applications (AREA)
- Theoretical Computer Science (AREA)
- Signal Processing (AREA)
- Computer Networks & Wireless Communication (AREA)
- Error Detection And Correction (AREA)
- Detection And Prevention Of Errors In Transmission (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明は、全般的には、データの低密度パリティ検査（ＬＤＰＣ）符号化の方法および装置に関し、具体的には、データ通信および記憶システムのバイナリ変調およびマルチレベル変調のためのＬＤＰＣ符号語へのデータのマッピングのためのパリティ検査行列に基づくデータのブロック符号化に関する。
【０００２】
【従来の技術】
「Ｌｏｗ−ｄｅｎｓｉｔｙ ｐａｒｉｔｙ−ｃｈｅｃｋ ｃｏｄｅｓ（ギャラガ（Ｇａｌｌａｇｅｒ）著／ＭＩＴ Ｐｒｅｓｓ／米国マサチューセッツ州ケンブリッジ／１９６３年）」に、メッセージパッシング・デコーダに基づいて、バイナリ入力加法性白色ガウス雑音チャネル（ＡＷＧＮ）のチャネル容量に極めて近づくことができることが示された。それから、ＬＤＰＣ符号を多数の実用的な通信チャネルおよび記録チャネル上で容量に非常に近づけることができることが示された。したがって、ＬＤＰＣ符号は、ターボ符号の代替技術と考えられている。特に、ＬＤＰＣ符号は、ターボ符号よりすぐれた漸近性能を示し、エラー・フロアの影響が少なく、デコーダの複雑さと性能の間のさまざまなトレードオフを提供する。ＬＤＰＣ符号の長所は、その復号に使用されるｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムの実装があまり複雑でないことである。ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムの簡略化バージョン版では、完全なｓｕｍ−ｐｒｏｄｕｃｔ復号と比較して無視できる程度の復号性能の低下と引き換えに、複雑さが減らされる。
【０００３】
ハード・ディスクまたはテープ・システムなどの磁気記憶アプリケーションの多くでは、情報がバイナリ形式で記憶される。これらのアプリケーションでは、リード・ソロモン（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ）外符号に連接（ｃｏｎｃａｔｅｎａｔｅ）された変調内符号が、書き込まれた情報の信頼性の高い抽出のために使用される。ターボ符号およびＬＤＰＣ符号は、磁気記憶システムの面密度を、現在の使用可能な磁気コンポーネントの限界まで押し上げることができる。ハード・ディスクの現在のセクタ・サイズの制約が符号のブロック長を制限し、高い符号化率を要求しているにもかかわらず、単純な反復復号方式によって理論限界の約１．５ｄＢ以内に性能を高めることができることが示された。これは、既存のシステムと比較して重大な利得を表している。高効率ＬＤＰＣ符号は、磁気記憶システムの外符号として使用される時に、畳み込み符号またはターボ符号を超える利点を有すると思われる。たとえば、ＬＤＰＣ符号は、１０−８のエラー率でエラー・フロアの影響を受けないと思われる。さらに、ＬＤＰＣ符号のパリティ検査行列のまばらさ（ｓｐａｒｓｅｎｅｓｓ）によって、畳み込み外符号と直列に連接されたシステムと比較してより複雑でない復号アルゴリズムがもたらされる。また、インターリービングがＬＤＰＣ符号に潜在的に組み込まれているので、ＬＤＰＣエンコーダとチャネルの間のインターリーバは不要である。磁気記憶チャネルに関する従来のリード・ソロモン符号に対するＬＤＰＣ符号の潜在的な利益は、「Ｒｅｄｕｃｅｄ−Ｃｏｍｐｌｅｘｉｔｙ Ｉｔｅｒａｔｉｖｅ Ｄｅｃｏｄｉｎｇ ｏｆ Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ Ｃｏｄｅｓ ｆｏｒ Ｇｅｎｅｒａｌｉｚｅｄ Ｐａｒｔｉａｌ Ｒｅｓｐｏｎｓｅ Ｃｈａｎｎｅｌｓ（ミッテルホルツァ（Ｔ． Ｍｉｔｔｅｌｈｏｌｚｅｒ）、ドラキア（Ａ． Ｄｈｏｌａｋｉａ）、およびエレフテリオウ（Ｅ． Ｅｌｅｆｔｈｅｒｉｏｕ）共著／ＩＥＥＥ Ｔｒａｎｓ． Ｍａｇｎ．， ３７（２）， ｐｐ． ７２１−７２８／２００１年３月）」に記載されている。ＬＤＰＣ符号によって、磁気記憶システムでは、面密度がその究極の限界まで押し上げられると期待される。
【０００４】
有線伝送システムおよび無線伝送システムを含む多くの通信システムには、伝送信号帯域幅に対する厳格な制限がある。そのような制限によって、２より多数のレベルを有する信号変調の必要が生じる。多くの従来のシステムでは、そのようなアプリケーションでトレリス符号化変調（ＴＣＭ）が使用される。しかし、ＴＣＭに関連する問題は、それが反復復号に適さないことである。したがって、許容可能な複雑さでの信号品質のさらなる改善は、達成が困難である。
【０００５】
「Ａ ｔｕｒｂｏ ＴＣＭ ｓｃｈｅｍｅ ｗｉｔｈ ｌｏｗ ｄｅｃｏｄｉｎｇ ｃｏｍｐｌｅｘｉｔｙ （Ｃａｔｅｎａ Ｎｅｔｗｏｒｋｓ Ｉｎｃ．／Ｔｅｍｐｏｒａｒｙ Ｄｏｃｕｍｅｎｔ ＢＩ−０９０， ＩＴＵ−Ｔ Ｓｔｕｄｙ Ｇｒｏｕｐ １５， Ｑｕｅｓｔｉｏｎ ４／インド／ゴア／２０００年１０月２３から２７日）」、「Ｐｒｏｐｏｓａｌ ｏｆ ｄｅｃｉｓｉｏｎ ｍａｋｉｎｇ ｆｏｒ ｔｕｒｂｏ ｃｏｄｉｎｇ ａｎｄ ｒｅｐｏｒｔ ｏｆ ｐｅｒｆｏｒｍａｎｃｅ ｅｖａｌｕａｔｉｏｎ ｏｆ ｐｒｏｐｏｓｅｄ ＴＴＣＭ（ＰＣＣＣ） ｗｉｔｈ Ｒ−Ｓ ｃｏｄｅ ａｎｄ ｗｉｔｈｏｕｔ Ｒ−Ｓ ｃｏｄｅ （Ｍｉｔｓｕｂｉｓｈｉ Ｅｌｅｃｔｒｉｃ Ｃｏｒｐ．／Ｔｅｍｐｏｒａｒｙ Ｄｏｃｕｍｅｎｔ ＢＩ−００３， ＩＴＵ−Ｔ Ｓｔｕｄｙ Ｇｒｏｕｐ １５／インド、ゴア／２０００年１０月２３から２７日）」および「Ｒｅｓｕｌｔｓ ｏｆ ｔｈｅ ｒｅｑｕｉｒｅｍｅｎｔｓ ｒｅｑｕｅｓｔｅｄ ｉｎ ｔｈｅ ｃｏｄｉｎｇ ａｄ ｈｏｃ ｒｅｐｏｒｔ（Ｖｏｃａｌ Ｔｅｃｈｎｏｌｏｇｉｅｓ Ｉｎｃ．／Ｔｅｍｐｏｒａｒｙ Ｄｏｃｕｍｅｎｔ ＨＣ−０７３， ＩＴＵ−Ｔ Ｓｔｕｄｙ Ｇｒｏｕｐ １５， Ｑｕｅｓｔｉｏｎ ４／カナダ、ハンツビル／２０００年６月３１日から８月４日」に、マルチレベルＡＤＳＬ伝送およびマルチレベルＶＤＳＬ伝送のターボ符号化方式が記載されている。これらのターボ符号化技法では、再帰的な規則正しい形での畳み込みエンコーダの並列連接（ｐａｒａｌｌｅｌ ｃｏｎｃａｔｉｎａｔｉｏｎ）による情報ビットの符号化と、複数の可能なターボ復号技法の１つによる反復復号が用いられる。「Ｂｌｏｃｋ ｐｒｏｄｕｃｔ ｔｕｒｂｏ ｃｏｄｅｓ ｆｏｒ Ｇ．ｄｍｔ．ｂｉｓ ａｎｄ Ｇ．ｌｉｔｅ．ｂｉｓ（Ｇｌｏｂｅｓｐａｎ Ｉｎｃ．／Ｔｅｍｐｏｒａｒｙ Ｄｏｃｕｍｅｎｔ ＢＡ−０６３， ＩＴＵ−Ｔ Ｓｔｕｄｙ Ｇｒｏｕｐ １５， Ｑｕｅｓｔｉｏｎ ４／ベルギー、アントワープ／２０００年６月１９から２３日）」に、コンポーネントＢｏｓｅ−Ｃｈａｕｄｈｕｒｉ−Ｈｏｅｑｕｅｎｇｈｅｍ（ＢＣＨ）符号を使用するブロック・プロダクト・コードおよびＣｈａｓｅアルゴリズムに基づくそのソフト反復復号のアプリケーションが記載されている。さらなる複雑さが生じるものの、これらの技法はトレリス符号化に対するある程度の性能強化を提供する。
【０００６】
「Ｌｏｗ−ｄｅｎｓｉｔｙ ｐａｒｉｔｙ−ｃｈｅｃｋ ｃｏｄｅｓ（ギャラガ（Ｒ． Ｇ． Ｇａｌｌａｇｅｒ）著／ＩＲＥ Ｔｒａｎｓ． Ｉｎｆｏ． Ｔｈｅｏｒｙ， ｖｏｌ． ＩＴ−８， ｐｐ． ２１−２８／１９６２年１月）」、「Ｎｅａｒ Ｓｈａｎｎｏｎ ｌｉｍｉｔ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｌｏｗ ｄｅｎｓｉｔｙ ｐａｒｉｔｙ ｃｈｅｃｋ ｃｏｄｅｓ（マッケイ（Ｄ． Ｊ． Ｃ． ＭａｃＫａｙ）およびニール（Ｒ． Ｍ． Ｎｅａｌ）共著／Ｅｌｅｃｔｒｏｎ． Ｌｅｔｔ．， ｖｏｌ． ３２， ｎｏ． １８， ｐｐ． １６４５−１６４６／１９９６年８月）」、「Ｇｏｏｄ ｅｒｒｏｒ−ｃｏｒｒｅｃｔｉｎｇ ｃｏｄｅｓ ｂａｓｅｄ ｏｎ ｖｅｒｙ ｓｐａｒｓｅ ｍａｔｒｉｃｅｓ（マッケイ（Ｄ． Ｊ． Ｃ． ＭａｃＫａｙ）著／ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｉｎｆｏｒｍ． Ｔｈｅｏｒｙ， ｖｏｌ． ４５， Ｎｏ． ２， ｐｐ． ３９９−４３１／１９９９年３月）」および「Ｒｅｄｕｃｅｄ ｃｏｍｐｌｅｘｉｔｙ ｉｔｅｒａｔｉｖｅ ｄｅｃｏｄｉｎｇ ｏｆ ｌｏｗ ｄｅｎｓｉｔｙ ｐａｒｉｔｙ ｃｈｅｃｋ ｃｏｄｅｓ ｂａｓｅｄ ｏｎ ｂｅｌｉｅｆ ｐｒｏｐａｇａｔｉｏｎ（フォッソリア（ＦＯＳＳＯＲＩＥＲ， Ｍ． Ｐ． Ｃ．）、ミハルジェビック（ＭＩＨＡＬＪＥＶＩＣ， Ｍ．）およびイマイ（ＩＭＡＩ， Ｈ．）共著／ＩＥＥＥ Ｔｒａｎｓ． Ｃｏｍｍｕｎ．， １９９９， ４７， （５）， ｐｐ． ６７３−６８０）」に記載されている、ＬＤＰＣ符号の代替の符号化技法に関するアプリケーション開発は、これまで無線システムまたはディジタル磁気記録などのバイナリ変調を必要とするアプリケーションに焦点を合わせてきた。しかし、ＬＤＰＣ符号はマルチレベル伝送にも適用することができる。
【０００７】
「Ｂａｎｄｗｉｄｔｈ ｅｆｆｉｃｉｅｎｔ ｌｏｗ ｄｅｎｓｉｔｙ ｐａｒｉｔｙ ｃｈｅｃｋ ｃｏｄｉｎｇ ｕｓｉｎｇ ｍｕｌｔｉｌｅｖｅｌ ｃｏｄｉｎｇ ａｎｄ ｉｎｔｅｒａｔｉｖｅ ｍｕｌｔｉｓｔａｇｅ ｄｅｃｏｄｉｎｇ（ナラヤナン（Ｋ． Ｒ． Ｎａｒａｙａｎａｎ）およびリー（Ｊ． Ｌｉ）共著／Ｐｒｏｃ． Ｉｎｔ． Ｓｙｍｐ． ｏｎ Ｔｕｒｂｏ−Ｃｏｄｅｓ、ｐｐ． １６５−１６８／フランス、ブレスト／２０００年９月）」に、バイナリＬＤＰＣブロック符号に基づくマルチレベル符号化技法が記載されている。この技法では、ビット・インターリーブ式変調または反復マルチステージ復号を伴うマルチレベル符号化に、ＬＤＰＣブロック符号が使用される。この技法によるビット・インターリーブ式ＬＤＰＣ変調の場合、マルチレベル・シンボルの選択に使用されるビットのすべてが、ＬＤＰＣ符号ビットである。マルチレベル符号化に関して、複数のＬＤＰＣブロック符号が、マルチレベル方式のコンポーネント・コードとして使用される。この技法は、複数のＬＤＰＣエンコーダ／デコーダを必要とし、特に長いコードまたは大きいコンステレーション・サイズの場合にかなり実装が複雑となるという短所を有する。
【０００８】
「Ｌｏｗ ｄｅｎｓｉｔｙ ｐａｒｉｔｙ ｃｈｅｃｋ ｃｏｄｅｄ ｍｏｄｕｌａｔｉｏｎ ｆｏｒ ＡＤＳＬ（Ａｗａｒｅ Ｉｎｃ．／Ｔｅｍｐｏｒａｒｙ Ｄｏｃｕｍｅｎｔ ＢＩ−０８１， ＩＴＵ−Ｔ Ｓｔｕｄｙ Ｇｒｏｕｐ １５， Ｑｕｅｓｔｉｏｎ ４／インド、ゴア／２０００年１０月２３から２７日）」にも、バイナリＬＤＰＣブロック符号に基づくマルチレベル符号化技法が記載されている。この技法は、ＴＣＭに類似するが、畳み込み符号化の代わりにＬＤＰＣ符号化が使用されることが異なる。具体的に言うと、ｓｅｔ ｐａｒｔｉｔｉｏｎｉｎｇが、ＴＣＭで使用されるものと同一の原理に従う。この技法は、追加のＢｏｓｅ−Ｃｈａｕｄｈｕｒｉ−Ｈｏｅｇｕｅｎｇｈｅｍ（ＢＣＨ）符号を必要とし、これによってシステムの複雑になるという短所を有する。また、ＴＣＭおよび類似の方式で必要なｓｅｔ ｐａｒｔｉｔｉｏｎｉｎｇは、軟（ソフト）判定ベースの復号技法について劣悪な性能につながる。
【０００９】
「Ｔｅｍｐｏｒａｒｙ Ｄｏｃｕｍｅｎｔ ＲＮ−２５ （ＩＴＵ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｓｔａｎｄａｒｄｉｚａｔｉｏｎ Ｓｅｃｔｏｒ， Ｓｔｕｄｙ Ｇｒｏｕｐ １５／米国ニュー・ジャージー／２００１年５月２１から２５日）」に、決定的（ｄｅｔｅｒｍｉｎｉｓｔｉｃ）ＬＤＰＣ方法と、ＡＤＳＬ伝送およびＡＤＳＬ Ｌｉｔｅ伝送へのそのアプリケーションが記載されている。ここで提案された方法は、例えば、ガウス消去法を使用する、生成行列の事前の計算を必要とする。符号化には、Ｏ（Ｎ２）個の演算が必要となる。
【００１０】
送信される情報ビットの組を第１のグループおよび第２のグループに分割するステップと、ブロック符号を生成するために第１のグループを符号化するステップと、グレイコード化されたマッピング関数（Ｇｒａｙ−ｃｏｄｅｄ ｍａｐｐｉｎｇ ｆｕｎｃｔｉｏｎ）に従ってブロック・コードに依存するシンボルのコンステレーション内のシンボルのサブセットを選択するステップと、グレイコード化されたマッピング関数に従って第２のグループに依存するサブセット内のシンボルを選択するステップと、選択されたシンボルを送信するステップとを含むマルチレベル・データ通信の方法が存在する。この方法は、達成可能な符号化利得に関して優れた性能を提供する。符号化利得が生じるのは、ブロック符号化方式を反復的に復号することができ、これによって、トレリス符号化変調と比較してかなりの性能利得がもたらされるからである。この方法の特に好ましい実施形態には、インターリーブを必要としない、単純なｓｕｍ−ｐｒｏｄｕｃｔアルゴリズム（ＳＰＡ）またはその複雑さの低い派生技術を介して復号することができるＬＤＰＣ符号またはシンプル・プロダクト・コードに基づくマルチレベル符号化方式が含まれる。
【００１１】
ＬＤＰＣ符号に関連する不利益は、比較的高い符号化の複雑さが必要になることである。ＬＤＰＣ符号語が情報ブロックに符号の生成行列（ｇｅｎｅｒａｔｏｒ ｍａｔｒｉｘ ｏｆ ｔｈｅ ｃｏｄｅ）をかけることによって得られる場合、符号化には、Ｏ（Ｎ２）個の演算が必要である（Ｎは符号長を表す）。そのような符号化の手順は「時間的に線形（ｌｉｎｅａｒ ｉｎ ｔｉｍｅ）」ではない。さらに、指定されたＬＤＰＣパリティ検査行列から符号の生成行列を計算するために、前処理ステップが必要である。生成行列の計算には、ガウス消去法が含まれ、これは、Ｏ（Ｎ３）個の演算を必要とする。前処理は、特定のＬＤＰＣ検査行列について１回実行され、オフラインで実行され得るが、パリティ検査行列の系列（ｆａｍｉｌｙ）の１つの選択を必要とするアプリケーションに関する復号の時に、計算コストが極端に高くなる可能性がある。このことは、例えば、符号が接続ごとに選択されるｘＤＳＬの場合が該当する。ＬＤＰＣ符号の効率的な符号化に関する話題は、「Ｌｏｗ ｄｅｎｓｉｔｙ ｐａｒｉｔｙ ｃｈｅｃｋ ｃｏｄｅｓ ｗｉｔｈ ｓｅｍｉ−ｒａｎｄｏｍ ｐａｒｉｔｙ ｃｈｅｃｋ ｍａｔｒｉｘ（ピン（Ｌ． Ｐｉｎｇ）、レウン（Ｗ． Ｋ． Ｌｅｕｎｇ）、およびファムド（Ｎ． Ｐｈａｍｄｏ）共著／Ｅｌｅｃｔｒｏｎ． Ｌｅｔｔｅｒｓ， Ｖｏｌ． ３５， Ｎｏ． １， ｐｐ． ３８−３９／１９９９年１月７日）」、「Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｃｏｎｓｔｒｕｃｔｉｏｎｓ ｏｆ ｉｒｒｅｇｕｌａｒ Ｇａｌｌａｇｅｒ ｃｏｄｅｓ（マッケイ（Ｄ． Ｊ． Ｃ． ＭａｃＫａｙ）、ウィルソン（Ｓ． Ｔ． Ｗｉｌｓｏｎ）、およびダベイ（Ｍ． Ｃ． Ｄａｖｅｙ）共著／ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｖｏｌ． ４７， Ｎｏ． １０， ｐｐ． １４４９−１４５４／１９９９年１０月）」および「Ｅｆｆｉｃｉｅｎｔ ｅｎｃｏｄｉｎｇ ｏｆ ｌｏｗ−ｄｅｎｓｉｔｙ ｐａｒｉｔｙ−ｃｈｅｃｋ ｃｏｄｅｓ（リチャードソン（Ｒ． Ｒｉｃｈａｒｄｓｏｎ）およびウルバンケ（Ｒ． Ｌ． Ｕｒｂａｎｋｅ）共著／ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ， Ｖｏｌ． ４７．， Ｎｏ． ２， ｐｐ． ６３８−６５６／２００１年２月）」に示されている。
【００１２】
「Ｌｏｗ ｄｅｎｓｉｔｙ ｐａｒｉｔｙ ｃｈｅｃｋ ｃｏｄｅｓ ｗｉｔｈ ｓｅｍｉ−ｒａｎｄｏｍ ｐａｒｉｔｙ ｃｈｅｃｋ ｍａｔｒｉｘ（ピン（Ｌ． Ｐｉｎｇ）、レウン（Ｗ． Ｋ． Ｌｅｕｎｇ）およびファムド（Ｎ． Ｐｈａｍｄｏ）共著／Ｅｌｅｃｔｒｏｎ． Ｌｅｔｔｅｒｓ， Ｖｏｌ． ３５， Ｎｏ． １， ｐｐ． ３８−３９／１９９９年１月７日）」では、ＬＤＰＣ符号のパリティ検査行列が、決定的部分（ｄｅｔｅｒｍｉｎｉｓｔｉｃ ｐａｒｔ）とランダム部分（ｒａｎｄｏｍ ｐａｒｔ）を含むという意味で「セミランダム」である。決定的部分は、効率的な符号化を可能にするために、帯状対角線すなわち「ジグザグ」形（ｂａｎｄ−ｄｉａｇｏｎａｌ ｏｒ ”ｚｉｇ−ｚａｇ” ｆｏｒｍ）である。パリティ検査行列の残りは、４サイクルを避けてランダムに作成される。「Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｃｏｎｓｔｒｕｃｔｉｏｎｓ ｏｆ ｉｒｒｅｇｕｌａｒ Ｇａｌｌａｇｅｒ ｃｏｄｅｓ（マッケイ（Ｄ． Ｊ． Ｃ． ＭａｃＫａｙ）、ウィルソン（Ｓ． Ｔ． Ｗｉｌｓｏｎ）およびダベイ（Ｍ． Ｃ． Ｄａｖｅｙ）共著／ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｖｏｌ． ４７， Ｎｏ． １０， ｐｐ． １４４９−１４５４／１９９９年１０月）」および「Ｅｆｆｉｃｉｅｎｔ ｅｎｃｏｄｉｎｇ ｏｆ ｌｏｗ−ｄｅｎｓｉｔｙ ｐａｒｉｔｙ−ｃｈｅｃｋ ｃｏｄｅｓ（リチャードソン（Ｒ． Ｒｉｃｈａｒｄｓｏｎ）およびウルバンケ（Ｒ． Ｌ． Ｕｒｂａｎｋｅ）共著／ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ， Ｖｏｌ． ４７．， Ｎｏ． ２， ｐｐ．６３８−６５６／２００１年２月）」では、パリティ検査行列が、やはりランダム構成によって生成され、三角行列（ｔｒｉａｎｇｕｌａｒ）または「ほぼ三角行列（ａｐｐｒｏｘｉｍａｔｅ ｔｒｉａｎｇｕｌａｒ）」であることが、効率的な符号化を可能にするために課せられる。これらの構成はそれぞれ、線形時間で符号化可能なＬＤＰＣ符号につながる。しかし、これには、下記を含む複数の短所がある。
（ａ）ランダムに構成されたパリティ検査符号は、少数のパラメータを介して指定することができない。言い換えると、パリティ検査行列の０でない要素のすべての位置を、個別に与えなければならない。
（ｂ）パリティ検査行列を三角行列またはほぼ三角行列にするために、しばしば前処理が必要になる。
（ｃ）得られる符号が、ランダムに構成されたＬＤＰＣ符号と比較して低い性能をもたらす。
【００１３】
【発明が解決しようとする課題】
線形時間の符号化の複雑さを有するＬＤＰＣ符号につながるパリティ検査行列を提供することが望ましい。また、完全に決定的（ｄｅｔｅｒｍｉｎｉｓｔｉｃ）であり、少数のパラメータを介して指定できるパリティ検査行列を提供することが望ましい。また、最小量の前処理を必要とするか前処理が不要なパリティ検査行列を提供することが望ましい。
【００１４】
【課題を解決するための手段】
本発明によれば、データの低密度パリティ検査（ＬＤＰＣ）符号化の方法であって、第１のＭ×Ｎパリティ検査行列を定義するステップと、第１のＭ×Ｎパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成するステップと、第２のパリティ検査行列に基づいてデータをＬＤＰＣ符号語にマッピングするステップとを含む方法が提供される。
【００１５】
この方法には、さらに、第２のパリティ検査行列から４サイクルを除去するステップを含めることができる。代替案では、パリティ検査行列の定義に、最初から４サイクルを除去するために、第１のパリティ検査行列の行のサイクリック・シフトを含めることができる。本発明の好ましい実施形態には、Ｍ×Ｍ部分行列の主対角線に沿った要素に同一の値をセットするステップが含まれる。
【００１６】
もう１つの態様から本発明を見ると、第１のＭ×Ｎパリティ検査行列を定義する手段と、第１のＭ×Ｎパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手段と、第２のパリティ検査行列に基づいてデータをＬＤＰＣ符号語にマッピングする手段とを含む、データの低密度パリティ検査（ＬＤＰＣ）符号化装置が提供される。
【００１７】
もう１つの態様から本発明を見ると、データの低密度パリティ検査（ＬＤＰＣ）符号化プログラムであって、前記符号化プログラムが、コンピュータ・システムに、第１のＭ×Ｎパリティ検査行列を定義する手順と、第１のＭ×Ｎパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手順と、第２のパリティ検査行列に基づいて、データをＬＤＰＣ符号語にマッピングする手順とを実行させるプログラムが提供される。また、そのようなプログラムを格納したコンピュータ読み取り可能な記憶媒体が提供可能であることは勿論である。
【００１８】
本発明は、通信チャネルを介して情報源から受信したデータを送信し、前記データを低密度パリティ検査（ＬＤＰＣ）符号語に符号化するデータ送信装置であって、第１のＭ×Ｎパリティ検査行列を定義する手段と、第１のＭ×Ｎパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手段と、第２のパリティ検査行列に基づいて、データをＬＤＰＣ符号語にマッピングする手段とを含む、データ送信装置にも拡張され得る。
【００１９】
本発明は、さらに、データ・ストレージ・チャネル内の情報源から受信したデータを記憶し、前記データが低密度パリティ検査（ＬＤＰＣ）符号語に符号化され、第１のＭ×Ｎパリティ検査行列を定義する手段と、第１のＭ×Ｎパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手段と、第２のパリティ検査行列に基づいて、データをＬＤＰＣ符号語にマッピングする手段とを含む、データ記憶装置に拡張され得る。
【００２０】
したがって、提供されるパリティ検査行列は、線形時間の符号化複雑さを有するＬＤＰＣ符号につながる。そのような行列は、完全に決定的であり、少数のパラメータを介して指定することができる。また、そのような行列は、最小量の前処理を必要とするか前処理が不要である。得られるコードの性能は、ランダムに構成されるＬＤＰＣ符号と同等またはそれ以上である。
【００２１】
これから説明する本発明の好ましい実施形態は、いわゆる「アレイ・コード」についてパリティ検査行列の構成を使用する。アレイ・コードは、「Ａｒｒａｙ ｃｏｄｅｓ（ブラウム（Ｍ． Ｂｌａｕｍ）、ファレル（Ｐ． Ｆａｒｒｅｌｌ）およびティルボーグ（Ｈ． ｖａｎ Ｔｉｌｂｏｒｇ）共著／Ｈａｎｄｂｏｏｋ ｏｆ Ｃｏｄｉｎｇ Ｔｈｅｏｒｙ， Ｖ． Ｓ． Ｐｌｅｓｓ ａｎｄ Ｗ． Ｃ． Ｈｕｆｆｍａｎ Ｅｄｓ．， Ｅｌｓｅｖｉｅｒ／１９９８年）」に記載されている。ＬＤＰＣパリティ検査行列を得るためのアレイ・コードの構成の直接の適用は、「Ａｒｒａｙ ｃｏｄｅｓ ａｓ ｌｏｗ−ｄｅｎｓｉｔｙ ｐａｒｉｔｙ−ｃｈｅｃｋ ｃｏｄｅｓ（ファン（Ｊ． Ｌ． Ｆａｎ）／Ｐｒｏｃ． Ｉｎｔ． Ｓｙｍｐ． ｏｎ Ｔｕｒｂｏ Ｃｏｄｅｓ、ｐｐ． ５４３−５４６／フランス、ブレスト／２０００年９月）」および「ＬＤＰＣ ｃｏｄｅｓ ｆｏｒ Ｇ．ｄｍｔ．ｂｉｓ ａｎｄ Ｇ．ｌｉｔｅ．ｂｉｓ（エルフテリオウ（Ｅ． Ｅｌｅｆｔｈｅｒｉｏｕ）およびエルセール（Ｓ． Ｏｅｌｃｅｒ）共著／Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ Ｕｎｉｏｎ， ＩＴＵ−Ｔ， Ｓｔｕｄｙ Ｇｒｏｕｐ １５ ／ Ｑｕｅｓｔｉｏｎ ４， Ｔｅｍｐｏｒａｒｙ Ｄｏｃｕｍｅｎｔ ＣＦ−０６０／米国フロリダ州クリアウォーター／２００１年１月８から１２日）」に記載されている。最後に述べた２つの参考文献の符号は、少数のパラメータを介して指定されるが、線形時間で符号化することはできない。
【００２２】
【発明の実施の形態】
以下に、例示のみを目的として、添付図面を参照して本発明の好ましい実施形態を説明する。
【００２３】
以下では、
【数１】
を「チルダＨ」と呼称する。
【００２４】
まず図１を参照すると、本発明の好ましい実施形態には、ディジタル加入者線（ＤＳＬ）通信チャネルなどの通信チャネル２０を介して受信機（図示せず）に接続される送信装置１０が含まれる。動作中に、送信装置１０は、コンピュータ・システム、携帯電話、固定回線電話、または類似するデータ通信端点などの情報源４０から情報ビット３０のシーケンスを受信する。送信装置１０は、通信チャネル２０を介して受信機に送信するために、情報ビット３０をシンボル５０に変換する。
【００２５】
図２を参照すると、本発明の特に好ましい実施形態では、送信装置１０に、分割器１００、分割器１００に接続されたブロック・エンコーダであるエンコーダ１１０、およびエンコーダ１１０と分割器１００に接続されたシンボル・マッパー１２０が含まれる。パリティ検査行列の行列ジェネレータ１６０が、エンコーダ１１０に接続される。動作中、分割器１００は、各変調の時に、情報源４０から通信される情報ビット３０の組を、第１のグループ１３０および第２のグループ１４０に分割する。エンコーダ１１０は、第２のグループ１４０を符号化して、行列ジェネレータによって供給されるパリティ検査行列に基づいてブロック符号１５０を生成する。パリティ検査行列は、コード・パラメータ１７０に基づいて行列ジェネレータによって生成される。シンボル・マッパー１２０は、グレイコード化されたマッピング関数に従って、ブロック符号１５０に依存するシンボルのコンステレーション内のシンボルのサブセットを選択する。シンボル・マッパー１２０は、グレイコード化されたマッピング関数に従って、第１のグループ１３０に依存する、サブセット内のシンボルも選択する。選択されたシンボル５０が、通信チャネル２０を介して受信機に通信される。分割器１００は、シフト・レジスタまたは類似する論理機能によって実施することができる。送信装置１０を、（１）ハードワイヤード・ロジック（結線論理）によって、（２）コンピュータ・プログラム・コードを用いてプログラムされた汎用プロセッサ／専用ディジタル信号プロセッサによって、または（３）ハードワイヤード・ロジックとコンピュータ・プログラム・コードの組み合わせによって、実施できることに留意されたい。
【００２６】
図３を参照すると、図２に関して既に本明細書で説明した送信装置１０の変更形態では、分割器１００が省略され、エンコーダ１１０が、情報源４０から受信した情報ビット３０のすべてを符号化して、ブロック符号１５０を生成する。シンボル・マッパー１２０が、グレイコード化されたマッピング関数に従って、ブロック符号１５０に依存するシンボルのコンステレーション内のシンボルを選択する。選択されたシンボル５０が、通信チャネル２０を介して受信機に通信される。
【００２７】
図４を参照すると、本発明の好ましい実施形態では、行列ジェネレータ１６０に、三角行列ジェネレータ３１０に接続された行列定義ロジック３００が含まれる。図５を参照すると、ステップ３５０で、動作中、行列定義ロジック３００が、入力のコード・パラメータ１７０に基づいて第１のＭ×Ｎパリティ検査行列３２０を定義する。ステップ３６０で、三角行列ジェネレータ３１０が、第１の行列に基づいて第２の行列を生成する。第２の行列は、Ｍ×Ｍの三角行列である部分行列を有する。ステップ３７０で、第２の行列が、行列ジェネレータ１６０からエンコーダ１１０に供給される。エンコーダ１１０へのデータ入力が、第２の行列に基づいてＬＤＰＣ符号語にマッピングされる。本発明の好ましい実施形態でのパリティ検査行列の定義および三角行列の生成の２つの手法を、図６および図７に関してこれから説明する。
【００２８】
図６を参照すると、本発明の好ましい実施形態では、行列生成に、３つのステップ、１、２、および３が含まれる。ステップ１では、行列Ｈを、アレイ・コードに関するパリティ検査行列（ｐａｒｉｔｙ−ｃｈｅｃｋ ｍａｔｒｉｃｅｓ ｆｏｒ ａｒｒａｙ ｃｏｄｅｓ）の定義に従って定義する。ステップ２は、上三角構造（ｕｐｐｅｒ−ｔｒｉａｎｇｕｌａｒ ｓｔｒｕｃｔｕｒｅ）を実現するために行列Ｈを決定的に修正する三角化（ｔｒｉａｎｇｕｌａｒｉｚａｔｉｏｎ）ステップである。ステップ３には、第２のステップで導入された可能性がある４サイクルを除去する単純な手順が含まれる。
【００２９】
＜ステップ１：Ｈの定義（Ｄｅｆｉｎｉｔｉｏｎ ｏｆ Ｈ）＞
アレイ・コード風のＬＤＰＣパリティ検査行列Ｈは、３つのパラメータすなわち、素数ｐと２つの整数ｋ，ｊ（ｋ，ｊ≦ｐ）によって定義される。行列Ｈは、次元ｊｐ×ｋｐを有し、次式によって与えられる。
【数２】
ここで、Ｉは、ｐ×ｐ単位行列であり、ａは、シングル・レフト（またはライト）・サイクリック・シフトを表すｐ×ｐ置換行列であり、例えば、
【数３】
である。パラメータｊ，ｋは、それぞれＨの列数および行数を提供する。構成により、行列Ｈは、４サイクル・フリー（４サイクルなしの状態）である。言い換えるならば、複数の位置にオーバーラップする１を有する行はない。
【００３０】
Ｈは、符号語長Ｎ＝ｋｐとパリティ検査数Ｍ＝ｊｐを有するＬＤＰＣ符号の系列のパリティ検査行列を表す。符号語長Ｎ’（＜Ｎ）またはパリティ検査数Ｍ’（＜Ｍ）を有するＬＤＰＣ符号は、Ｈの右端の（Ｎ−Ｎ’）列および下端の（Ｍ−Ｍ’）行を破棄することによって簡単に得られる。結果として得られるＭ’×Ｎ’行列が、使用される行列のサイズの明白な修正と共に、ステップ２および３でＨの代わりに使用される。
【００３１】
＜ステップ２：Ｈの三角化（Ｔｒｉａｎｇｕｌａｒｉｚａｔｉｏｎ ｏｆ Ｈ）＞
Ｈが、ブロック行列形式
Ｈ＝［Ｈ１｜Ｈ２］
で表され、Ｈ１が、次元ｊｐ×ｊｐを有し、Ｈ２が、次元ｊｐ×（ｋ−ｊ）ｐを有するものとする。Ｕが、Ｈ１の主対角線（ｍａｉｎ ｄｉａｇｏｎａｌ）上の各要素を１に置換し、主対角線の下のすべての要素に０をセットすることによってＨ１から得られるｊｐ×ｊｐの上三角行列であるものとする。ｊｐ×ｋｐの行列
ＨＵ＝［Ｕ｜Ｈ２］
によって、線形時間で符号化可能なＬＤＰＣ符号のパリティ検査行列が定義される。
【００３２】
行列Ｈが、構成によって４サイクルがないが、ＨＵが、上三角行列Ｕを導入したことに起因して、４サイクル・フリーではない場合があることに留意されたい。しかし、４サイクルは、次のステップで示されるように、簡単に検出され、除去される。
【００３３】
＜ステップ３：４サイクルの除去（Ｅｌｉｍｉｎａｔｉｏｎ ｏｆ ４−ｃｙｃｌｅｓ）＞
Ａ＝ＨＵ・ＨＵ Ｔであるものとする。ただし、Ｔは行列転置を表す。Ａの対角要素ａｍ，ｍ，ｍ＝１，…，ｊｐによって、行ｍのハミング重さ、すなわち、行列ＨＵのパリティ検査ｍによって検査されるシンボルの数が与えられる。非対角要素ａｍ，ｎ、ｍ，ｎ＝１，…，ｊｐ、ｍ≠ｎによって、パリティ検査ｍおよびパリティ検査ｎの両方によって検査されるシンボルの数が与えられる。４サイクルなしでは、ａｍ，ｎ≦１である。
【００３４】
したがって、パリティ検査行列が４サイクル・フリーであることを保証するためには、（ａ）Ａ＝ＨＵ・ＨＵ Ｔの下三角部分（ｌｏｗｅｒ−ｔｒｉａｎｇｕｌａｒ ｐａｒｔ）を計算し、（ｂ）ａｍ，ｎ＞１、（ｍ，ｎ＝１，…，ｊｐ；ｍ＜ｎ）の場合に、ＨＵの第（ｎ，ｍ）要素に０をセットする。
【００３５】
チルダＨＵによって、ステップ３の最後に得られる行列を表す。チルダＨＵによって定義されるＬＤＰＣ符号は、符号語長Ｎ＝ｋｐ、パリティ検査数Ｍ＝ｊｐ、および情報ブロック長Ｋ＝（ｋ−ｊ）ｐを有する。チルダＨＵを使用することによる線形時間符号化の可能性を、次に示す。
【００３６】
効率的な符号化は、符号の生成行列を計算する必要なしに、パリティ検査行列チルダＨＵから直接に達成される。ＬＤＰＣ符号が線形ブロック符号なので、Ｎタプル（Ｎ−ｔｕｐｌｅ）ｘは、ＯがＭ×１の零ベクトルであるものとして、チルダＨＵ・ｘ＝０の場合に限ってＬＤＰＣ符号語になる。このベクトルｘは、次の形で表すことができる。
【数４】
ここで、ｊｐ×１のベクトルｐが、符号語ｘのパリティ部分、（ｋ−ｊ）ｐ×１のベクトルｓが、符号語ｘの組織的部分を表す。ｐのｊｐ個のパリティ・ビットは、
【数５】
を使用し、チルダＨＵの上三角形式を使用することによって、再帰的な形で得られる。これを示すために、ベクトルｐおよびｓの両方が、ｐ×１の部分ベクトルに分割されるものとする。
【数６】
ここで、ｐｉ＝｛ｐｉ，ｎ；ｎ＝１，２，…，ｐ｝、ｉ＝１，２，…，ｊであり、ｓｉ＝｛ｓｉ，ｎ；ｎ＝１，２，…，ｐ｝、ｉ＝１，２，…，ｋ−ｊである。すると、ｐｍの要素が、下記の再帰の組によって、ｍ＝ｊ、ｊ−１、…、１について得られる。
【数７】
ここで、第２の添字、ｐｌ、…およびｓｌ、…は、行列ａのべきによって割り当てられる特定の値に依存するが、表記が長くならないように省略されたものである。括弧内に示された項は、やはり行列ａのべきの特定の値に依存して、実際には存在しない場合がある。
【００３７】
したがって、上の符号化処理は、パリティ検査行列チルダＨＵの三角形構造（ｔｒｉａｎｇｕｌａｒ ｓｔｒｕｃｔｕｒｅ）およびそのまばらさ（ｓｐａｒｓｉｔｙ）を利用している。ｒが符号化率であるものとして、符号化が約
【数８】
回のＸＯＲ演算を必要とすることを示すことができる。
【００３８】
図７を参照すると、図６に関して既に説明した手法の変更形態に、２つのステップ１’および２’が含まれる。ステップ１’および２’を、これから詳細に説明する。
【００３９】
＜ステップ１’：ＨＳの定義（Ｄｅｆｉｎｉｔｉｏｎ ｏｆ ＨＳ）＞
行列ＨＳは、ブロック単位の形で、行列Ｈの行をサイクリック・シフトすることによって定義される。各ブロック−行のサイクリック・シフトの量は、ＨＳの左端のｊｐ×ｊｐ個のサブ・ブロックに、その対角線に沿って単位行列Ｉが含まれるようになる量である。
【数９】
ＨＳは、サイクリック・シフトのみを介してＨから得られたので、それぞれｊおよびｋによって与えられる列および行の重さを有し、４サイクルフリーである。
【００４０】
＜ステップ２’：ＨＳの三角化（Ｔｒｉａｎｇｕｌａｒｉｚａｔｉｏｎ ｏｆ ＨＳ）＞
行列ＨＳは、左端のｊｐ×ｊｐ個のサブ・ブロックの下三角要素を０に置換することによって三角化される。その結果、下記の行列ＨＵ Ｓが得られる。
【数１０】
ここで、Ｏは、ｐ×ｐの零行列である。
【００４１】
ＨＵ Ｓによって定義されるＬＤＰＣ符号は、符号語長Ｎ＝ｋｐ、パリティ検査数Ｍ＝ｊｐ、および情報ブロック長Ｋ＝（ｋ−ｊ）ｐを有する。また、ＨＵ Ｓは、４サイクル・フリーである。明らかに、ＨＵ Ｓによって定義されるＬＤＰＣ符号は、線形時間での符号化が可能である。
【００４２】
符号語長Ｎ’（＜Ｎ）またはパリティ検査数Ｍ’（＜Ｍ）を有するＬＤＰＣ符号は、ＨＵ Ｓの右端の（Ｎ−Ｎ’）列および下端の（Ｍ−Ｍ’）行を破棄することによって、簡単に得られる。
【００４３】
効率的な符号化は、図６に関して前に説明した手法に関して前に説明したものと同一の形で達成される。ｒが符号化率であるものとして、
【数１１】
回のＸＯＲ演算が必要であることを示すことができる。
【００４４】
図６および７に関して本明細書で前に説明した本発明の実施形態で得られるパリティ検査行列は、三角行列を有する。「Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｃｏｎｓｔｒｕｃｔｉｏｎｓ ｏｆ ｉｒｒｅｇｕｌａｒ Ｇａｌｌａｇｅｒ ｃｏｄｅｓ（マッケイ（Ｄ． Ｊ． Ｃ． ＭａｃＫａｙ）、ウィルソン（Ｓ． Ｔ． Ｗｉｌｓｏｎ）およびダベイ（Ｍ． Ｃ． Ｄａｖｅｙ）共著／ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｖｏｌ． ４７， Ｎｏ． １０， ｐｐ． １４４９−１４５４／１９９９年１０月）」と、「Ｅｆｆｉｃｉｅｎｔ ｅｎｃｏｄｉｎｇ ｏｆ ｌｏｗ−ｄｅｎｓｉｔｙ ｐａｒｉｔｙ−ｃｈｅｃｋ ｃｏｄｅｓ／リチャードソン（Ｒ． Ｒｉｃｈａｒｄｓｏｎ）およびウルバンケ（Ｒ． Ｌ． Ｕｒｂａｎｋｅ）共著／ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ， Ｖｏｌ． ４７．， Ｎｏ． ２， ｐｐ．６３８−６５６／２００１年２月）」に、「ほぼ三角形」の形
【数１２】
（Ｃ、Ｄ、Ｅ、およびＴは適当な次元の行列であり、Ｔ行列が上三角行列である。）のパリティ検査行列を有するＬＤＰＣ符号についても、高速な符号化が可能であることが示されている。そのような形は、図６および７に関して本明細書で前に説明した手法を一般化することによって、効率的に得ることができる。
【００４５】
たとえば、図６に関して本明細書で前に説明した手法に従う場合には、ほぼ三角行列を生成するために、ステップ１は同一のままであるが、行列Ｈを、ブロック行列形式で
【数１３】
として同等に記述することができる。ここで、Ｈ５は、ｔｐ×ｔｐの行列であり、整数ｔ≦ｊであり、行列Ｈ３、Ｈ４、およびＨ６は、適当な次元を有する。ステップ２に類似する三角化ステップを、Ｈ５に適用する。Ｕ５が、Ｈ５の主対角線の各要素を１に置換し、主対角線の下のすべての要素に０をセットすることによってＨ５から得られるｔｐ×ｔｐ上三角行列であるものとする。
【００４６】
ｊｐ×ｋｐの行列
【数１４】
は、ほぼ三角行列であり、したがって、これによって、前述の「Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｃｏｎｓｔｒｕｃｔｉｏｎｓ ｏｆ ｉｒｒｅｇｕｌａｒ Ｇａｌｌａｇｅｒ ｃｏｄｅｓ（マッケイ（Ｄ． Ｊ． Ｃ． ＭａｃＫａｙ）、ウィルソン（Ｓ． Ｔ． Ｗｉｌｓｏｎ）およびダベイ（Ｍ． Ｃ． Ｄａｖｅｙ）共著／ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｖｏｌ． ４７， Ｎｏ． １０， ｐｐ． １４４９−１４５４／１９９９年１０月）」と、「Ｅｆｆｉｃｉｅｎｔ ｅｎｃｏｄｉｎｇ ｏｆ ｌｏｗ−ｄｅｎｓｉｔｙ ｐａｒｉｔｙ−ｃｈｅｃｋ ｃｏｄｅｓ（リチャードソン（Ｒ． Ｒｉｃｈａｒｄｓｏｎ）およびウルバンケ（Ｒ． Ｌ． Ｕｒｂａｎｋｅ）共著／ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ， Ｖｏｌ． ４７．， Ｎｏ． ２， ｐｐ．６３８−６５６／２００１年２月）」による高速な符号化が可能なＬＤＰＣ符号のパリティ検査行列が定義される。その後、ステップ３をこのほぼ三角形の行列に適用して、４サイクルを除去する。
【００４７】
明らかに、ステップ１の行列Ｈを、行方向および列方向に切り詰めて、符号語長およびパリティ検査数の特定の値を実現することができる。
【００４８】
前に示したように、図７に関して本明細書で前に説明した手法も、ほぼ三角形のパリティ検査行列を得るのに使用することができる。この目的のためには、行列ＨＳのｔ−１個の下側ブロック行を右にサイクリック・シフトすることによって、ステップ１’を変更する。すなわち、最も下のブロック行が、ｔ−１位置だけシフトされ、次に上のブロック行が、ｔ−２位置だけシフトされる。その後、ステップ２’を、そのようにして得られた行列の左下のｔｐ×ｔｐ部分行列だけに適用して、ほぼ三角形の新しい行列をもたらす。行列全体が、ほぼ三角行列であり、４サイクルがなく、「Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｃｏｎｓｔｒｕｃｔｉｏｎｓ ｏｆ ｉｒｒｅｇｕｌａｒ Ｇａｌｌａｇｅｒ ｃｏｄｅｓ（マッケイ（Ｄ． Ｊ． Ｃ． ＭａｃＫａｙ）、ウィルソン（Ｓ． Ｔ． Ｗｉｌｓｏｎ）、およびダベイ（Ｍ． Ｃ． Ｄａｖｅｙ）共著／ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｖｏｌ． ４７， Ｎｏ． １０， ｐｐ． １４４９−１４５４／１９９９年１０月）」と、「Ｅｆｆｉｃｉｅｎｔ ｅｎｃｏｄｉｎｇ ｏｆ ｌｏｗ−ｄｅｎｓｉｔｙ ｐａｒｉｔｙ−ｃｈｅｃｋ ｃｏｄｅｓ（リチャードソン（Ｒ． Ｒｉｃｈａｒｄｓｏｎ）およびウルバンケ（Ｒ． Ｌ． Ｕｒｂａｎｋｅ）共著／ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ， Ｖｏｌ． ４７．， Ｎｏ． ２， ｐｐ．６３８−６５６／２００１年２月）」に従う高速ＬＤＰＣ符号化に直接に使用することができる。
【００４９】
やはり、ステップ２’の終りに得られる行列を、行方向および列方向に切り詰めて、符号語長およびパリティ検査数の特定の値を達成することができる。
【００５０】
本発明のいくつかの実施形態では、パリティ検査行列を、通信チャネル２０を介する受信機への送信装置１０の接続の際に、行列定義ロジック３００によって定義することができる。たとえば、行列を、通信チャネル２０の端点間で折衝された次元に基づいて、接続時に行列定義ロジック３００によって作成することができる。具体的に言うと、パリティ検査行列を、受信機から送信装置１０へのコード・パラメータ１７０の供給に基づいて決定することができる。本発明の他の実施形態では、パリティ検査行列を、接続が確立される前に、行列定義ロジック３００によって定義することができる。たとえば、１つまたは複数のパリティ検査行列を、行列定義ロジック３００内で事前設定することができ、各事前設定された行列が、事前設定されたコード長（列数）および事前設定されたパリティ検査数（行数）を有する。複数の事前設定された行列を有する実施形態では、接続の確立時に、適当な行列が、行列定義ロジック３００に対して選択される。そのような選択は、たとえば、前に説明したように通信チャネル２０の端点間の折衝に基づいて実行することができる。
【００５１】
本発明の好ましい実施形態を、これまでは通信システムに関して説明した。しかし、本発明は、そのようなシステムへの適用に制限されない。たとえば、図８を参照すると、前に説明したエンコーダ１１０の実施形態を、情報源４０からのデータをハード・ディスク・ストレージ・チャネルなどのストレージ・チャネルに記憶するデータ記憶システム２１０で使用することもできる。
【００５２】
本明細書で前に説明した送信装置１０、エンコーダ１１０、および行列ジェネレータ１６０のそれぞれを、（１）ハードワイヤード・ロジックによって、（２）コンピュータ・プログラム・コードを用いてプログラムされた汎用プロセッサ／専用ディジタル信号プロセッサによって、または（３）ハードワイヤード・ロジックとコンピュータ・プログラム・コードの組み合わせによって、実施できることを諒解されたい。たとえば、図９を参照すると、前に図２に関して説明したデータ通信システムで、送信装置１０に、メモリ４１０に接続されたプログラマブル・ディジタル信号プロセッサ（ＤＳＰ）４００を含めることができ、メモリ４１０にコンピュータ・プログラム・コード４２０が記憶され、コンピュータ・プログラム・コード４２０が、ＤＳＰ４００によって実行される時に、図５に関して前に説明した方法のステップを実行するようにＤＳＰ４００を構成する。
【００５３】
本明細書で好ましい実施形態に関して本発明を説明したが、当業者は、本発明の範囲から逸脱せずに、形態および詳細におけるさまざまな変更を行うことができることを諒解するであろう。
【００５４】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００５５】
（１）データの低密度パリティ検査（ＬＤＰＣ）符号化の方法であって、
第１のＭ×Ｎパリティ検査行列を定義するステップと、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成するステップと、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングするステップと、
を含む方法。
（２）前記第２のパリティ検査行列から４サイクルを除去するステップをさらに含む、上記（１）に記載の方法。
（３）前記第１のパリティ検査行列の前記定義が、前記第１のパリティ検査行列の行のサイクリック・シフトを含む、上記（１）に記載の方法。
（４）前記Ｍ×Ｍ部分行列の主対角線に沿った要素に同一の値をセットするステップを含む、上記（１）に記載の方法。
（５）データの低密度パリティ検査（ＬＤＰＣ）符号化装置であって、
第１のＭ×Ｎパリティ検査行列を定義する手段と、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手段と、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングする手段と、
を含む装置。
（６）前記第２のパリティ検査行列を生成する手段が、前記第２のパリティ検査行列から４サイクルを除去する手段をさらに含む、上記（５）に記載の装置。
（７）前記第１のパリティ検査行列を定義する手段が、前記第１のパリティ検査行列の行をサイクリック・シフトする、上記（５）に記載の装置。
（８）前記第１のパリティ検査行列を定義する手段が、前記Ｍ×Ｍ部分行列の主対角線に沿った要素に同一の値をセットする、上記（５）に記載の装置。
（９）データの低密度パリティ検査（ＬＤＰＣ）符号化プログラムであって、前記符号化プログラムが、コンピュータ・システムに、
第１のＭ×Ｎパリティ検査行列を定義する手順と、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手順と、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングする手順と、
を実行させるプログラム。
（１０）前記第２のパリティ検査行列から４サイクルを除去する手順をさらにコンピュータ・システムに実行させる、上記（９）に記載のプログラム。
（１１）前記第１のパリティ検査行列の定義が、前記第１のパリティ検査行列のサイクリック・シフトを含む、上記（９）に記載のプログラム。
（１２）データの低密度パリティ検査（ＬＤＰＣ）符号化プログラムを格納したコンピュータ読み取り可能な記憶媒体であって、前記符号化プログラムが、コンピュータ・システムに、
第１のＭ×Ｎパリティ検査行列を定義する手順と、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手順と、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングする手順と、
を実行させるプログラムを格納したコンピュータ読み取り可能な記憶媒体。
（１３）通信チャネルを介して情報源から受信したデータを送信し、前記データを低密度パリティ検査（ＬＤＰＣ）符号語に符号化するデータ通信装置であって、
第１のＭ×Ｎパリティ検査行列を定義する手段と、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手段と、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングする手段と、
を含むデータ通信装置。
（１４）データ・ストレージ・チャネル内の情報源から受信したデータを記憶し、前記データを低密度パリティ検査（ＬＤＰＣ）符号語に符号化するデータ記憶装置であって、
第１のＭ×Ｎパリティ検査行列を定義する手段と、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手段と、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングする手段と、
を含むデータ記憶装置。
【図面の簡単な説明】
【図１】通信システムのブロック図である。
【図２】通信システムの送信装置のブロック図である。
【図３】通信システムのもう１つの送信装置のブロック図である。
【図４】送信装置の行列ジェネレータのブロック図である。
【図５】送信装置のエンコーダ機能に対応する流れ図である。
【図６】行列ジェネレータに対応する流れ図である。
【図７】行列ジェネレータに対応するもう１つの流れ図である。
【図８】データ記憶システムのブロック図である。
【図９】通信システムの送信装置のもう１つの例のブロック図である。
【符号の説明】
１０ 送信装置
２０ 通信チャネル
３０ 情報ビット
４０ 情報源
５０ シンボル
１００ 分割器
１１０ エンコーダ
１２０ シンボル・マッパー
１３０ 第１のグループ
１４０ 第２のグループ
１５０ ブロック・コード
１６０ 行列ジェネレータ
１７０ コード・パラメータ
２１０ データ記憶システム
３００ 行列定義ロジック
３１０ 三角行列ジェネレータ
３２０ 第１のＭ×Ｎパリティ検査行列
４００ プログラマブル・ディジタル信号プロセッサ（ＤＳＰ）
４１０ メモリ
４２０ コンピュータ・プログラム・コード
【発明の属する技術分野】
本発明は、全般的には、データの低密度パリティ検査（ＬＤＰＣ）符号化の方法および装置に関し、具体的には、データ通信および記憶システムのバイナリ変調およびマルチレベル変調のためのＬＤＰＣ符号語へのデータのマッピングのためのパリティ検査行列に基づくデータのブロック符号化に関する。
【０００２】
【従来の技術】
「Ｌｏｗ−ｄｅｎｓｉｔｙ ｐａｒｉｔｙ−ｃｈｅｃｋ ｃｏｄｅｓ（ギャラガ（Ｇａｌｌａｇｅｒ）著／ＭＩＴ Ｐｒｅｓｓ／米国マサチューセッツ州ケンブリッジ／１９６３年）」に、メッセージパッシング・デコーダに基づいて、バイナリ入力加法性白色ガウス雑音チャネル（ＡＷＧＮ）のチャネル容量に極めて近づくことができることが示された。それから、ＬＤＰＣ符号を多数の実用的な通信チャネルおよび記録チャネル上で容量に非常に近づけることができることが示された。したがって、ＬＤＰＣ符号は、ターボ符号の代替技術と考えられている。特に、ＬＤＰＣ符号は、ターボ符号よりすぐれた漸近性能を示し、エラー・フロアの影響が少なく、デコーダの複雑さと性能の間のさまざまなトレードオフを提供する。ＬＤＰＣ符号の長所は、その復号に使用されるｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムの実装があまり複雑でないことである。ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムの簡略化バージョン版では、完全なｓｕｍ−ｐｒｏｄｕｃｔ復号と比較して無視できる程度の復号性能の低下と引き換えに、複雑さが減らされる。
【０００３】
ハード・ディスクまたはテープ・システムなどの磁気記憶アプリケーションの多くでは、情報がバイナリ形式で記憶される。これらのアプリケーションでは、リード・ソロモン（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ）外符号に連接（ｃｏｎｃａｔｅｎａｔｅ）された変調内符号が、書き込まれた情報の信頼性の高い抽出のために使用される。ターボ符号およびＬＤＰＣ符号は、磁気記憶システムの面密度を、現在の使用可能な磁気コンポーネントの限界まで押し上げることができる。ハード・ディスクの現在のセクタ・サイズの制約が符号のブロック長を制限し、高い符号化率を要求しているにもかかわらず、単純な反復復号方式によって理論限界の約１．５ｄＢ以内に性能を高めることができることが示された。これは、既存のシステムと比較して重大な利得を表している。高効率ＬＤＰＣ符号は、磁気記憶システムの外符号として使用される時に、畳み込み符号またはターボ符号を超える利点を有すると思われる。たとえば、ＬＤＰＣ符号は、１０−８のエラー率でエラー・フロアの影響を受けないと思われる。さらに、ＬＤＰＣ符号のパリティ検査行列のまばらさ（ｓｐａｒｓｅｎｅｓｓ）によって、畳み込み外符号と直列に連接されたシステムと比較してより複雑でない復号アルゴリズムがもたらされる。また、インターリービングがＬＤＰＣ符号に潜在的に組み込まれているので、ＬＤＰＣエンコーダとチャネルの間のインターリーバは不要である。磁気記憶チャネルに関する従来のリード・ソロモン符号に対するＬＤＰＣ符号の潜在的な利益は、「Ｒｅｄｕｃｅｄ−Ｃｏｍｐｌｅｘｉｔｙ Ｉｔｅｒａｔｉｖｅ Ｄｅｃｏｄｉｎｇ ｏｆ Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ Ｃｏｄｅｓ ｆｏｒ Ｇｅｎｅｒａｌｉｚｅｄ Ｐａｒｔｉａｌ Ｒｅｓｐｏｎｓｅ Ｃｈａｎｎｅｌｓ（ミッテルホルツァ（Ｔ． Ｍｉｔｔｅｌｈｏｌｚｅｒ）、ドラキア（Ａ． Ｄｈｏｌａｋｉａ）、およびエレフテリオウ（Ｅ． Ｅｌｅｆｔｈｅｒｉｏｕ）共著／ＩＥＥＥ Ｔｒａｎｓ． Ｍａｇｎ．， ３７（２）， ｐｐ． ７２１−７２８／２００１年３月）」に記載されている。ＬＤＰＣ符号によって、磁気記憶システムでは、面密度がその究極の限界まで押し上げられると期待される。
【０００４】
有線伝送システムおよび無線伝送システムを含む多くの通信システムには、伝送信号帯域幅に対する厳格な制限がある。そのような制限によって、２より多数のレベルを有する信号変調の必要が生じる。多くの従来のシステムでは、そのようなアプリケーションでトレリス符号化変調（ＴＣＭ）が使用される。しかし、ＴＣＭに関連する問題は、それが反復復号に適さないことである。したがって、許容可能な複雑さでの信号品質のさらなる改善は、達成が困難である。
【０００５】
「Ａ ｔｕｒｂｏ ＴＣＭ ｓｃｈｅｍｅ ｗｉｔｈ ｌｏｗ ｄｅｃｏｄｉｎｇ ｃｏｍｐｌｅｘｉｔｙ （Ｃａｔｅｎａ Ｎｅｔｗｏｒｋｓ Ｉｎｃ．／Ｔｅｍｐｏｒａｒｙ Ｄｏｃｕｍｅｎｔ ＢＩ−０９０， ＩＴＵ−Ｔ Ｓｔｕｄｙ Ｇｒｏｕｐ １５， Ｑｕｅｓｔｉｏｎ ４／インド／ゴア／２０００年１０月２３から２７日）」、「Ｐｒｏｐｏｓａｌ ｏｆ ｄｅｃｉｓｉｏｎ ｍａｋｉｎｇ ｆｏｒ ｔｕｒｂｏ ｃｏｄｉｎｇ ａｎｄ ｒｅｐｏｒｔ ｏｆ ｐｅｒｆｏｒｍａｎｃｅ ｅｖａｌｕａｔｉｏｎ ｏｆ ｐｒｏｐｏｓｅｄ ＴＴＣＭ（ＰＣＣＣ） ｗｉｔｈ Ｒ−Ｓ ｃｏｄｅ ａｎｄ ｗｉｔｈｏｕｔ Ｒ−Ｓ ｃｏｄｅ （Ｍｉｔｓｕｂｉｓｈｉ Ｅｌｅｃｔｒｉｃ Ｃｏｒｐ．／Ｔｅｍｐｏｒａｒｙ Ｄｏｃｕｍｅｎｔ ＢＩ−００３， ＩＴＵ−Ｔ Ｓｔｕｄｙ Ｇｒｏｕｐ １５／インド、ゴア／２０００年１０月２３から２７日）」および「Ｒｅｓｕｌｔｓ ｏｆ ｔｈｅ ｒｅｑｕｉｒｅｍｅｎｔｓ ｒｅｑｕｅｓｔｅｄ ｉｎ ｔｈｅ ｃｏｄｉｎｇ ａｄ ｈｏｃ ｒｅｐｏｒｔ（Ｖｏｃａｌ Ｔｅｃｈｎｏｌｏｇｉｅｓ Ｉｎｃ．／Ｔｅｍｐｏｒａｒｙ Ｄｏｃｕｍｅｎｔ ＨＣ−０７３， ＩＴＵ−Ｔ Ｓｔｕｄｙ Ｇｒｏｕｐ １５， Ｑｕｅｓｔｉｏｎ ４／カナダ、ハンツビル／２０００年６月３１日から８月４日」に、マルチレベルＡＤＳＬ伝送およびマルチレベルＶＤＳＬ伝送のターボ符号化方式が記載されている。これらのターボ符号化技法では、再帰的な規則正しい形での畳み込みエンコーダの並列連接（ｐａｒａｌｌｅｌ ｃｏｎｃａｔｉｎａｔｉｏｎ）による情報ビットの符号化と、複数の可能なターボ復号技法の１つによる反復復号が用いられる。「Ｂｌｏｃｋ ｐｒｏｄｕｃｔ ｔｕｒｂｏ ｃｏｄｅｓ ｆｏｒ Ｇ．ｄｍｔ．ｂｉｓ ａｎｄ Ｇ．ｌｉｔｅ．ｂｉｓ（Ｇｌｏｂｅｓｐａｎ Ｉｎｃ．／Ｔｅｍｐｏｒａｒｙ Ｄｏｃｕｍｅｎｔ ＢＡ−０６３， ＩＴＵ−Ｔ Ｓｔｕｄｙ Ｇｒｏｕｐ １５， Ｑｕｅｓｔｉｏｎ ４／ベルギー、アントワープ／２０００年６月１９から２３日）」に、コンポーネントＢｏｓｅ−Ｃｈａｕｄｈｕｒｉ−Ｈｏｅｑｕｅｎｇｈｅｍ（ＢＣＨ）符号を使用するブロック・プロダクト・コードおよびＣｈａｓｅアルゴリズムに基づくそのソフト反復復号のアプリケーションが記載されている。さらなる複雑さが生じるものの、これらの技法はトレリス符号化に対するある程度の性能強化を提供する。
【０００６】
「Ｌｏｗ−ｄｅｎｓｉｔｙ ｐａｒｉｔｙ−ｃｈｅｃｋ ｃｏｄｅｓ（ギャラガ（Ｒ． Ｇ． Ｇａｌｌａｇｅｒ）著／ＩＲＥ Ｔｒａｎｓ． Ｉｎｆｏ． Ｔｈｅｏｒｙ， ｖｏｌ． ＩＴ−８， ｐｐ． ２１−２８／１９６２年１月）」、「Ｎｅａｒ Ｓｈａｎｎｏｎ ｌｉｍｉｔ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｌｏｗ ｄｅｎｓｉｔｙ ｐａｒｉｔｙ ｃｈｅｃｋ ｃｏｄｅｓ（マッケイ（Ｄ． Ｊ． Ｃ． ＭａｃＫａｙ）およびニール（Ｒ． Ｍ． Ｎｅａｌ）共著／Ｅｌｅｃｔｒｏｎ． Ｌｅｔｔ．， ｖｏｌ． ３２， ｎｏ． １８， ｐｐ． １６４５−１６４６／１９９６年８月）」、「Ｇｏｏｄ ｅｒｒｏｒ−ｃｏｒｒｅｃｔｉｎｇ ｃｏｄｅｓ ｂａｓｅｄ ｏｎ ｖｅｒｙ ｓｐａｒｓｅ ｍａｔｒｉｃｅｓ（マッケイ（Ｄ． Ｊ． Ｃ． ＭａｃＫａｙ）著／ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｉｎｆｏｒｍ． Ｔｈｅｏｒｙ， ｖｏｌ． ４５， Ｎｏ． ２， ｐｐ． ３９９−４３１／１９９９年３月）」および「Ｒｅｄｕｃｅｄ ｃｏｍｐｌｅｘｉｔｙ ｉｔｅｒａｔｉｖｅ ｄｅｃｏｄｉｎｇ ｏｆ ｌｏｗ ｄｅｎｓｉｔｙ ｐａｒｉｔｙ ｃｈｅｃｋ ｃｏｄｅｓ ｂａｓｅｄ ｏｎ ｂｅｌｉｅｆ ｐｒｏｐａｇａｔｉｏｎ（フォッソリア（ＦＯＳＳＯＲＩＥＲ， Ｍ． Ｐ． Ｃ．）、ミハルジェビック（ＭＩＨＡＬＪＥＶＩＣ， Ｍ．）およびイマイ（ＩＭＡＩ， Ｈ．）共著／ＩＥＥＥ Ｔｒａｎｓ． Ｃｏｍｍｕｎ．， １９９９， ４７， （５）， ｐｐ． ６７３−６８０）」に記載されている、ＬＤＰＣ符号の代替の符号化技法に関するアプリケーション開発は、これまで無線システムまたはディジタル磁気記録などのバイナリ変調を必要とするアプリケーションに焦点を合わせてきた。しかし、ＬＤＰＣ符号はマルチレベル伝送にも適用することができる。
【０００７】
「Ｂａｎｄｗｉｄｔｈ ｅｆｆｉｃｉｅｎｔ ｌｏｗ ｄｅｎｓｉｔｙ ｐａｒｉｔｙ ｃｈｅｃｋ ｃｏｄｉｎｇ ｕｓｉｎｇ ｍｕｌｔｉｌｅｖｅｌ ｃｏｄｉｎｇ ａｎｄ ｉｎｔｅｒａｔｉｖｅ ｍｕｌｔｉｓｔａｇｅ ｄｅｃｏｄｉｎｇ（ナラヤナン（Ｋ． Ｒ． Ｎａｒａｙａｎａｎ）およびリー（Ｊ． Ｌｉ）共著／Ｐｒｏｃ． Ｉｎｔ． Ｓｙｍｐ． ｏｎ Ｔｕｒｂｏ−Ｃｏｄｅｓ、ｐｐ． １６５−１６８／フランス、ブレスト／２０００年９月）」に、バイナリＬＤＰＣブロック符号に基づくマルチレベル符号化技法が記載されている。この技法では、ビット・インターリーブ式変調または反復マルチステージ復号を伴うマルチレベル符号化に、ＬＤＰＣブロック符号が使用される。この技法によるビット・インターリーブ式ＬＤＰＣ変調の場合、マルチレベル・シンボルの選択に使用されるビットのすべてが、ＬＤＰＣ符号ビットである。マルチレベル符号化に関して、複数のＬＤＰＣブロック符号が、マルチレベル方式のコンポーネント・コードとして使用される。この技法は、複数のＬＤＰＣエンコーダ／デコーダを必要とし、特に長いコードまたは大きいコンステレーション・サイズの場合にかなり実装が複雑となるという短所を有する。
【０００８】
「Ｌｏｗ ｄｅｎｓｉｔｙ ｐａｒｉｔｙ ｃｈｅｃｋ ｃｏｄｅｄ ｍｏｄｕｌａｔｉｏｎ ｆｏｒ ＡＤＳＬ（Ａｗａｒｅ Ｉｎｃ．／Ｔｅｍｐｏｒａｒｙ Ｄｏｃｕｍｅｎｔ ＢＩ−０８１， ＩＴＵ−Ｔ Ｓｔｕｄｙ Ｇｒｏｕｐ １５， Ｑｕｅｓｔｉｏｎ ４／インド、ゴア／２０００年１０月２３から２７日）」にも、バイナリＬＤＰＣブロック符号に基づくマルチレベル符号化技法が記載されている。この技法は、ＴＣＭに類似するが、畳み込み符号化の代わりにＬＤＰＣ符号化が使用されることが異なる。具体的に言うと、ｓｅｔ ｐａｒｔｉｔｉｏｎｉｎｇが、ＴＣＭで使用されるものと同一の原理に従う。この技法は、追加のＢｏｓｅ−Ｃｈａｕｄｈｕｒｉ−Ｈｏｅｇｕｅｎｇｈｅｍ（ＢＣＨ）符号を必要とし、これによってシステムの複雑になるという短所を有する。また、ＴＣＭおよび類似の方式で必要なｓｅｔ ｐａｒｔｉｔｉｏｎｉｎｇは、軟（ソフト）判定ベースの復号技法について劣悪な性能につながる。
【０００９】
「Ｔｅｍｐｏｒａｒｙ Ｄｏｃｕｍｅｎｔ ＲＮ−２５ （ＩＴＵ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｓｔａｎｄａｒｄｉｚａｔｉｏｎ Ｓｅｃｔｏｒ， Ｓｔｕｄｙ Ｇｒｏｕｐ １５／米国ニュー・ジャージー／２００１年５月２１から２５日）」に、決定的（ｄｅｔｅｒｍｉｎｉｓｔｉｃ）ＬＤＰＣ方法と、ＡＤＳＬ伝送およびＡＤＳＬ Ｌｉｔｅ伝送へのそのアプリケーションが記載されている。ここで提案された方法は、例えば、ガウス消去法を使用する、生成行列の事前の計算を必要とする。符号化には、Ｏ（Ｎ２）個の演算が必要となる。
【００１０】
送信される情報ビットの組を第１のグループおよび第２のグループに分割するステップと、ブロック符号を生成するために第１のグループを符号化するステップと、グレイコード化されたマッピング関数（Ｇｒａｙ−ｃｏｄｅｄ ｍａｐｐｉｎｇ ｆｕｎｃｔｉｏｎ）に従ってブロック・コードに依存するシンボルのコンステレーション内のシンボルのサブセットを選択するステップと、グレイコード化されたマッピング関数に従って第２のグループに依存するサブセット内のシンボルを選択するステップと、選択されたシンボルを送信するステップとを含むマルチレベル・データ通信の方法が存在する。この方法は、達成可能な符号化利得に関して優れた性能を提供する。符号化利得が生じるのは、ブロック符号化方式を反復的に復号することができ、これによって、トレリス符号化変調と比較してかなりの性能利得がもたらされるからである。この方法の特に好ましい実施形態には、インターリーブを必要としない、単純なｓｕｍ−ｐｒｏｄｕｃｔアルゴリズム（ＳＰＡ）またはその複雑さの低い派生技術を介して復号することができるＬＤＰＣ符号またはシンプル・プロダクト・コードに基づくマルチレベル符号化方式が含まれる。
【００１１】
ＬＤＰＣ符号に関連する不利益は、比較的高い符号化の複雑さが必要になることである。ＬＤＰＣ符号語が情報ブロックに符号の生成行列（ｇｅｎｅｒａｔｏｒ ｍａｔｒｉｘ ｏｆ ｔｈｅ ｃｏｄｅ）をかけることによって得られる場合、符号化には、Ｏ（Ｎ２）個の演算が必要である（Ｎは符号長を表す）。そのような符号化の手順は「時間的に線形（ｌｉｎｅａｒ ｉｎ ｔｉｍｅ）」ではない。さらに、指定されたＬＤＰＣパリティ検査行列から符号の生成行列を計算するために、前処理ステップが必要である。生成行列の計算には、ガウス消去法が含まれ、これは、Ｏ（Ｎ３）個の演算を必要とする。前処理は、特定のＬＤＰＣ検査行列について１回実行され、オフラインで実行され得るが、パリティ検査行列の系列（ｆａｍｉｌｙ）の１つの選択を必要とするアプリケーションに関する復号の時に、計算コストが極端に高くなる可能性がある。このことは、例えば、符号が接続ごとに選択されるｘＤＳＬの場合が該当する。ＬＤＰＣ符号の効率的な符号化に関する話題は、「Ｌｏｗ ｄｅｎｓｉｔｙ ｐａｒｉｔｙ ｃｈｅｃｋ ｃｏｄｅｓ ｗｉｔｈ ｓｅｍｉ−ｒａｎｄｏｍ ｐａｒｉｔｙ ｃｈｅｃｋ ｍａｔｒｉｘ（ピン（Ｌ． Ｐｉｎｇ）、レウン（Ｗ． Ｋ． Ｌｅｕｎｇ）、およびファムド（Ｎ． Ｐｈａｍｄｏ）共著／Ｅｌｅｃｔｒｏｎ． Ｌｅｔｔｅｒｓ， Ｖｏｌ． ３５， Ｎｏ． １， ｐｐ． ３８−３９／１９９９年１月７日）」、「Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｃｏｎｓｔｒｕｃｔｉｏｎｓ ｏｆ ｉｒｒｅｇｕｌａｒ Ｇａｌｌａｇｅｒ ｃｏｄｅｓ（マッケイ（Ｄ． Ｊ． Ｃ． ＭａｃＫａｙ）、ウィルソン（Ｓ． Ｔ． Ｗｉｌｓｏｎ）、およびダベイ（Ｍ． Ｃ． Ｄａｖｅｙ）共著／ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｖｏｌ． ４７， Ｎｏ． １０， ｐｐ． １４４９−１４５４／１９９９年１０月）」および「Ｅｆｆｉｃｉｅｎｔ ｅｎｃｏｄｉｎｇ ｏｆ ｌｏｗ−ｄｅｎｓｉｔｙ ｐａｒｉｔｙ−ｃｈｅｃｋ ｃｏｄｅｓ（リチャードソン（Ｒ． Ｒｉｃｈａｒｄｓｏｎ）およびウルバンケ（Ｒ． Ｌ． Ｕｒｂａｎｋｅ）共著／ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ， Ｖｏｌ． ４７．， Ｎｏ． ２， ｐｐ． ６３８−６５６／２００１年２月）」に示されている。
【００１２】
「Ｌｏｗ ｄｅｎｓｉｔｙ ｐａｒｉｔｙ ｃｈｅｃｋ ｃｏｄｅｓ ｗｉｔｈ ｓｅｍｉ−ｒａｎｄｏｍ ｐａｒｉｔｙ ｃｈｅｃｋ ｍａｔｒｉｘ（ピン（Ｌ． Ｐｉｎｇ）、レウン（Ｗ． Ｋ． Ｌｅｕｎｇ）およびファムド（Ｎ． Ｐｈａｍｄｏ）共著／Ｅｌｅｃｔｒｏｎ． Ｌｅｔｔｅｒｓ， Ｖｏｌ． ３５， Ｎｏ． １， ｐｐ． ３８−３９／１９９９年１月７日）」では、ＬＤＰＣ符号のパリティ検査行列が、決定的部分（ｄｅｔｅｒｍｉｎｉｓｔｉｃ ｐａｒｔ）とランダム部分（ｒａｎｄｏｍ ｐａｒｔ）を含むという意味で「セミランダム」である。決定的部分は、効率的な符号化を可能にするために、帯状対角線すなわち「ジグザグ」形（ｂａｎｄ−ｄｉａｇｏｎａｌ ｏｒ ”ｚｉｇ−ｚａｇ” ｆｏｒｍ）である。パリティ検査行列の残りは、４サイクルを避けてランダムに作成される。「Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｃｏｎｓｔｒｕｃｔｉｏｎｓ ｏｆ ｉｒｒｅｇｕｌａｒ Ｇａｌｌａｇｅｒ ｃｏｄｅｓ（マッケイ（Ｄ． Ｊ． Ｃ． ＭａｃＫａｙ）、ウィルソン（Ｓ． Ｔ． Ｗｉｌｓｏｎ）およびダベイ（Ｍ． Ｃ． Ｄａｖｅｙ）共著／ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｖｏｌ． ４７， Ｎｏ． １０， ｐｐ． １４４９−１４５４／１９９９年１０月）」および「Ｅｆｆｉｃｉｅｎｔ ｅｎｃｏｄｉｎｇ ｏｆ ｌｏｗ−ｄｅｎｓｉｔｙ ｐａｒｉｔｙ−ｃｈｅｃｋ ｃｏｄｅｓ（リチャードソン（Ｒ． Ｒｉｃｈａｒｄｓｏｎ）およびウルバンケ（Ｒ． Ｌ． Ｕｒｂａｎｋｅ）共著／ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ， Ｖｏｌ． ４７．， Ｎｏ． ２， ｐｐ．６３８−６５６／２００１年２月）」では、パリティ検査行列が、やはりランダム構成によって生成され、三角行列（ｔｒｉａｎｇｕｌａｒ）または「ほぼ三角行列（ａｐｐｒｏｘｉｍａｔｅ ｔｒｉａｎｇｕｌａｒ）」であることが、効率的な符号化を可能にするために課せられる。これらの構成はそれぞれ、線形時間で符号化可能なＬＤＰＣ符号につながる。しかし、これには、下記を含む複数の短所がある。
（ａ）ランダムに構成されたパリティ検査符号は、少数のパラメータを介して指定することができない。言い換えると、パリティ検査行列の０でない要素のすべての位置を、個別に与えなければならない。
（ｂ）パリティ検査行列を三角行列またはほぼ三角行列にするために、しばしば前処理が必要になる。
（ｃ）得られる符号が、ランダムに構成されたＬＤＰＣ符号と比較して低い性能をもたらす。
【００１３】
【発明が解決しようとする課題】
線形時間の符号化の複雑さを有するＬＤＰＣ符号につながるパリティ検査行列を提供することが望ましい。また、完全に決定的（ｄｅｔｅｒｍｉｎｉｓｔｉｃ）であり、少数のパラメータを介して指定できるパリティ検査行列を提供することが望ましい。また、最小量の前処理を必要とするか前処理が不要なパリティ検査行列を提供することが望ましい。
【００１４】
【課題を解決するための手段】
本発明によれば、データの低密度パリティ検査（ＬＤＰＣ）符号化の方法であって、第１のＭ×Ｎパリティ検査行列を定義するステップと、第１のＭ×Ｎパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成するステップと、第２のパリティ検査行列に基づいてデータをＬＤＰＣ符号語にマッピングするステップとを含む方法が提供される。
【００１５】
この方法には、さらに、第２のパリティ検査行列から４サイクルを除去するステップを含めることができる。代替案では、パリティ検査行列の定義に、最初から４サイクルを除去するために、第１のパリティ検査行列の行のサイクリック・シフトを含めることができる。本発明の好ましい実施形態には、Ｍ×Ｍ部分行列の主対角線に沿った要素に同一の値をセットするステップが含まれる。
【００１６】
もう１つの態様から本発明を見ると、第１のＭ×Ｎパリティ検査行列を定義する手段と、第１のＭ×Ｎパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手段と、第２のパリティ検査行列に基づいてデータをＬＤＰＣ符号語にマッピングする手段とを含む、データの低密度パリティ検査（ＬＤＰＣ）符号化装置が提供される。
【００１７】
もう１つの態様から本発明を見ると、データの低密度パリティ検査（ＬＤＰＣ）符号化プログラムであって、前記符号化プログラムが、コンピュータ・システムに、第１のＭ×Ｎパリティ検査行列を定義する手順と、第１のＭ×Ｎパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手順と、第２のパリティ検査行列に基づいて、データをＬＤＰＣ符号語にマッピングする手順とを実行させるプログラムが提供される。また、そのようなプログラムを格納したコンピュータ読み取り可能な記憶媒体が提供可能であることは勿論である。
【００１８】
本発明は、通信チャネルを介して情報源から受信したデータを送信し、前記データを低密度パリティ検査（ＬＤＰＣ）符号語に符号化するデータ送信装置であって、第１のＭ×Ｎパリティ検査行列を定義する手段と、第１のＭ×Ｎパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手段と、第２のパリティ検査行列に基づいて、データをＬＤＰＣ符号語にマッピングする手段とを含む、データ送信装置にも拡張され得る。
【００１９】
本発明は、さらに、データ・ストレージ・チャネル内の情報源から受信したデータを記憶し、前記データが低密度パリティ検査（ＬＤＰＣ）符号語に符号化され、第１のＭ×Ｎパリティ検査行列を定義する手段と、第１のＭ×Ｎパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手段と、第２のパリティ検査行列に基づいて、データをＬＤＰＣ符号語にマッピングする手段とを含む、データ記憶装置に拡張され得る。
【００２０】
したがって、提供されるパリティ検査行列は、線形時間の符号化複雑さを有するＬＤＰＣ符号につながる。そのような行列は、完全に決定的であり、少数のパラメータを介して指定することができる。また、そのような行列は、最小量の前処理を必要とするか前処理が不要である。得られるコードの性能は、ランダムに構成されるＬＤＰＣ符号と同等またはそれ以上である。
【００２１】
これから説明する本発明の好ましい実施形態は、いわゆる「アレイ・コード」についてパリティ検査行列の構成を使用する。アレイ・コードは、「Ａｒｒａｙ ｃｏｄｅｓ（ブラウム（Ｍ． Ｂｌａｕｍ）、ファレル（Ｐ． Ｆａｒｒｅｌｌ）およびティルボーグ（Ｈ． ｖａｎ Ｔｉｌｂｏｒｇ）共著／Ｈａｎｄｂｏｏｋ ｏｆ Ｃｏｄｉｎｇ Ｔｈｅｏｒｙ， Ｖ． Ｓ． Ｐｌｅｓｓ ａｎｄ Ｗ． Ｃ． Ｈｕｆｆｍａｎ Ｅｄｓ．， Ｅｌｓｅｖｉｅｒ／１９９８年）」に記載されている。ＬＤＰＣパリティ検査行列を得るためのアレイ・コードの構成の直接の適用は、「Ａｒｒａｙ ｃｏｄｅｓ ａｓ ｌｏｗ−ｄｅｎｓｉｔｙ ｐａｒｉｔｙ−ｃｈｅｃｋ ｃｏｄｅｓ（ファン（Ｊ． Ｌ． Ｆａｎ）／Ｐｒｏｃ． Ｉｎｔ． Ｓｙｍｐ． ｏｎ Ｔｕｒｂｏ Ｃｏｄｅｓ、ｐｐ． ５４３−５４６／フランス、ブレスト／２０００年９月）」および「ＬＤＰＣ ｃｏｄｅｓ ｆｏｒ Ｇ．ｄｍｔ．ｂｉｓ ａｎｄ Ｇ．ｌｉｔｅ．ｂｉｓ（エルフテリオウ（Ｅ． Ｅｌｅｆｔｈｅｒｉｏｕ）およびエルセール（Ｓ． Ｏｅｌｃｅｒ）共著／Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ Ｕｎｉｏｎ， ＩＴＵ−Ｔ， Ｓｔｕｄｙ Ｇｒｏｕｐ １５ ／ Ｑｕｅｓｔｉｏｎ ４， Ｔｅｍｐｏｒａｒｙ Ｄｏｃｕｍｅｎｔ ＣＦ−０６０／米国フロリダ州クリアウォーター／２００１年１月８から１２日）」に記載されている。最後に述べた２つの参考文献の符号は、少数のパラメータを介して指定されるが、線形時間で符号化することはできない。
【００２２】
【発明の実施の形態】
以下に、例示のみを目的として、添付図面を参照して本発明の好ましい実施形態を説明する。
【００２３】
以下では、
【数１】
【００２４】
まず図１を参照すると、本発明の好ましい実施形態には、ディジタル加入者線（ＤＳＬ）通信チャネルなどの通信チャネル２０を介して受信機（図示せず）に接続される送信装置１０が含まれる。動作中に、送信装置１０は、コンピュータ・システム、携帯電話、固定回線電話、または類似するデータ通信端点などの情報源４０から情報ビット３０のシーケンスを受信する。送信装置１０は、通信チャネル２０を介して受信機に送信するために、情報ビット３０をシンボル５０に変換する。
【００２５】
図２を参照すると、本発明の特に好ましい実施形態では、送信装置１０に、分割器１００、分割器１００に接続されたブロック・エンコーダであるエンコーダ１１０、およびエンコーダ１１０と分割器１００に接続されたシンボル・マッパー１２０が含まれる。パリティ検査行列の行列ジェネレータ１６０が、エンコーダ１１０に接続される。動作中、分割器１００は、各変調の時に、情報源４０から通信される情報ビット３０の組を、第１のグループ１３０および第２のグループ１４０に分割する。エンコーダ１１０は、第２のグループ１４０を符号化して、行列ジェネレータによって供給されるパリティ検査行列に基づいてブロック符号１５０を生成する。パリティ検査行列は、コード・パラメータ１７０に基づいて行列ジェネレータによって生成される。シンボル・マッパー１２０は、グレイコード化されたマッピング関数に従って、ブロック符号１５０に依存するシンボルのコンステレーション内のシンボルのサブセットを選択する。シンボル・マッパー１２０は、グレイコード化されたマッピング関数に従って、第１のグループ１３０に依存する、サブセット内のシンボルも選択する。選択されたシンボル５０が、通信チャネル２０を介して受信機に通信される。分割器１００は、シフト・レジスタまたは類似する論理機能によって実施することができる。送信装置１０を、（１）ハードワイヤード・ロジック（結線論理）によって、（２）コンピュータ・プログラム・コードを用いてプログラムされた汎用プロセッサ／専用ディジタル信号プロセッサによって、または（３）ハードワイヤード・ロジックとコンピュータ・プログラム・コードの組み合わせによって、実施できることに留意されたい。
【００２６】
図３を参照すると、図２に関して既に本明細書で説明した送信装置１０の変更形態では、分割器１００が省略され、エンコーダ１１０が、情報源４０から受信した情報ビット３０のすべてを符号化して、ブロック符号１５０を生成する。シンボル・マッパー１２０が、グレイコード化されたマッピング関数に従って、ブロック符号１５０に依存するシンボルのコンステレーション内のシンボルを選択する。選択されたシンボル５０が、通信チャネル２０を介して受信機に通信される。
【００２７】
図４を参照すると、本発明の好ましい実施形態では、行列ジェネレータ１６０に、三角行列ジェネレータ３１０に接続された行列定義ロジック３００が含まれる。図５を参照すると、ステップ３５０で、動作中、行列定義ロジック３００が、入力のコード・パラメータ１７０に基づいて第１のＭ×Ｎパリティ検査行列３２０を定義する。ステップ３６０で、三角行列ジェネレータ３１０が、第１の行列に基づいて第２の行列を生成する。第２の行列は、Ｍ×Ｍの三角行列である部分行列を有する。ステップ３７０で、第２の行列が、行列ジェネレータ１６０からエンコーダ１１０に供給される。エンコーダ１１０へのデータ入力が、第２の行列に基づいてＬＤＰＣ符号語にマッピングされる。本発明の好ましい実施形態でのパリティ検査行列の定義および三角行列の生成の２つの手法を、図６および図７に関してこれから説明する。
【００２８】
図６を参照すると、本発明の好ましい実施形態では、行列生成に、３つのステップ、１、２、および３が含まれる。ステップ１では、行列Ｈを、アレイ・コードに関するパリティ検査行列（ｐａｒｉｔｙ−ｃｈｅｃｋ ｍａｔｒｉｃｅｓ ｆｏｒ ａｒｒａｙ ｃｏｄｅｓ）の定義に従って定義する。ステップ２は、上三角構造（ｕｐｐｅｒ−ｔｒｉａｎｇｕｌａｒ ｓｔｒｕｃｔｕｒｅ）を実現するために行列Ｈを決定的に修正する三角化（ｔｒｉａｎｇｕｌａｒｉｚａｔｉｏｎ）ステップである。ステップ３には、第２のステップで導入された可能性がある４サイクルを除去する単純な手順が含まれる。
【００２９】
＜ステップ１：Ｈの定義（Ｄｅｆｉｎｉｔｉｏｎ ｏｆ Ｈ）＞
アレイ・コード風のＬＤＰＣパリティ検査行列Ｈは、３つのパラメータすなわち、素数ｐと２つの整数ｋ，ｊ（ｋ，ｊ≦ｐ）によって定義される。行列Ｈは、次元ｊｐ×ｋｐを有し、次式によって与えられる。
【数２】
【数３】
【００３０】
Ｈは、符号語長Ｎ＝ｋｐとパリティ検査数Ｍ＝ｊｐを有するＬＤＰＣ符号の系列のパリティ検査行列を表す。符号語長Ｎ’（＜Ｎ）またはパリティ検査数Ｍ’（＜Ｍ）を有するＬＤＰＣ符号は、Ｈの右端の（Ｎ−Ｎ’）列および下端の（Ｍ−Ｍ’）行を破棄することによって簡単に得られる。結果として得られるＭ’×Ｎ’行列が、使用される行列のサイズの明白な修正と共に、ステップ２および３でＨの代わりに使用される。
【００３１】
＜ステップ２：Ｈの三角化（Ｔｒｉａｎｇｕｌａｒｉｚａｔｉｏｎ ｏｆ Ｈ）＞
Ｈが、ブロック行列形式
Ｈ＝［Ｈ１｜Ｈ２］
で表され、Ｈ１が、次元ｊｐ×ｊｐを有し、Ｈ２が、次元ｊｐ×（ｋ−ｊ）ｐを有するものとする。Ｕが、Ｈ１の主対角線（ｍａｉｎ ｄｉａｇｏｎａｌ）上の各要素を１に置換し、主対角線の下のすべての要素に０をセットすることによってＨ１から得られるｊｐ×ｊｐの上三角行列であるものとする。ｊｐ×ｋｐの行列
ＨＵ＝［Ｕ｜Ｈ２］
によって、線形時間で符号化可能なＬＤＰＣ符号のパリティ検査行列が定義される。
【００３２】
行列Ｈが、構成によって４サイクルがないが、ＨＵが、上三角行列Ｕを導入したことに起因して、４サイクル・フリーではない場合があることに留意されたい。しかし、４サイクルは、次のステップで示されるように、簡単に検出され、除去される。
【００３３】
＜ステップ３：４サイクルの除去（Ｅｌｉｍｉｎａｔｉｏｎ ｏｆ ４−ｃｙｃｌｅｓ）＞
Ａ＝ＨＵ・ＨＵ Ｔであるものとする。ただし、Ｔは行列転置を表す。Ａの対角要素ａｍ，ｍ，ｍ＝１，…，ｊｐによって、行ｍのハミング重さ、すなわち、行列ＨＵのパリティ検査ｍによって検査されるシンボルの数が与えられる。非対角要素ａｍ，ｎ、ｍ，ｎ＝１，…，ｊｐ、ｍ≠ｎによって、パリティ検査ｍおよびパリティ検査ｎの両方によって検査されるシンボルの数が与えられる。４サイクルなしでは、ａｍ，ｎ≦１である。
【００３４】
したがって、パリティ検査行列が４サイクル・フリーであることを保証するためには、（ａ）Ａ＝ＨＵ・ＨＵ Ｔの下三角部分（ｌｏｗｅｒ−ｔｒｉａｎｇｕｌａｒ ｐａｒｔ）を計算し、（ｂ）ａｍ，ｎ＞１、（ｍ，ｎ＝１，…，ｊｐ；ｍ＜ｎ）の場合に、ＨＵの第（ｎ，ｍ）要素に０をセットする。
【００３５】
チルダＨＵによって、ステップ３の最後に得られる行列を表す。チルダＨＵによって定義されるＬＤＰＣ符号は、符号語長Ｎ＝ｋｐ、パリティ検査数Ｍ＝ｊｐ、および情報ブロック長Ｋ＝（ｋ−ｊ）ｐを有する。チルダＨＵを使用することによる線形時間符号化の可能性を、次に示す。
【００３６】
効率的な符号化は、符号の生成行列を計算する必要なしに、パリティ検査行列チルダＨＵから直接に達成される。ＬＤＰＣ符号が線形ブロック符号なので、Ｎタプル（Ｎ−ｔｕｐｌｅ）ｘは、ＯがＭ×１の零ベクトルであるものとして、チルダＨＵ・ｘ＝０の場合に限ってＬＤＰＣ符号語になる。このベクトルｘは、次の形で表すことができる。
【数４】
【数５】
【数６】
【数７】
【００３７】
したがって、上の符号化処理は、パリティ検査行列チルダＨＵの三角形構造（ｔｒｉａｎｇｕｌａｒ ｓｔｒｕｃｔｕｒｅ）およびそのまばらさ（ｓｐａｒｓｉｔｙ）を利用している。ｒが符号化率であるものとして、符号化が約
【数８】
【００３８】
図７を参照すると、図６に関して既に説明した手法の変更形態に、２つのステップ１’および２’が含まれる。ステップ１’および２’を、これから詳細に説明する。
【００３９】
＜ステップ１’：ＨＳの定義（Ｄｅｆｉｎｉｔｉｏｎ ｏｆ ＨＳ）＞
行列ＨＳは、ブロック単位の形で、行列Ｈの行をサイクリック・シフトすることによって定義される。各ブロック−行のサイクリック・シフトの量は、ＨＳの左端のｊｐ×ｊｐ個のサブ・ブロックに、その対角線に沿って単位行列Ｉが含まれるようになる量である。
【数９】
【００４０】
＜ステップ２’：ＨＳの三角化（Ｔｒｉａｎｇｕｌａｒｉｚａｔｉｏｎ ｏｆ ＨＳ）＞
行列ＨＳは、左端のｊｐ×ｊｐ個のサブ・ブロックの下三角要素を０に置換することによって三角化される。その結果、下記の行列ＨＵ Ｓが得られる。
【数１０】
【００４１】
ＨＵ Ｓによって定義されるＬＤＰＣ符号は、符号語長Ｎ＝ｋｐ、パリティ検査数Ｍ＝ｊｐ、および情報ブロック長Ｋ＝（ｋ−ｊ）ｐを有する。また、ＨＵ Ｓは、４サイクル・フリーである。明らかに、ＨＵ Ｓによって定義されるＬＤＰＣ符号は、線形時間での符号化が可能である。
【００４２】
符号語長Ｎ’（＜Ｎ）またはパリティ検査数Ｍ’（＜Ｍ）を有するＬＤＰＣ符号は、ＨＵ Ｓの右端の（Ｎ−Ｎ’）列および下端の（Ｍ−Ｍ’）行を破棄することによって、簡単に得られる。
【００４３】
効率的な符号化は、図６に関して前に説明した手法に関して前に説明したものと同一の形で達成される。ｒが符号化率であるものとして、
【数１１】
【００４４】
図６および７に関して本明細書で前に説明した本発明の実施形態で得られるパリティ検査行列は、三角行列を有する。「Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｃｏｎｓｔｒｕｃｔｉｏｎｓ ｏｆ ｉｒｒｅｇｕｌａｒ Ｇａｌｌａｇｅｒ ｃｏｄｅｓ（マッケイ（Ｄ． Ｊ． Ｃ． ＭａｃＫａｙ）、ウィルソン（Ｓ． Ｔ． Ｗｉｌｓｏｎ）およびダベイ（Ｍ． Ｃ． Ｄａｖｅｙ）共著／ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｖｏｌ． ４７， Ｎｏ． １０， ｐｐ． １４４９−１４５４／１９９９年１０月）」と、「Ｅｆｆｉｃｉｅｎｔ ｅｎｃｏｄｉｎｇ ｏｆ ｌｏｗ−ｄｅｎｓｉｔｙ ｐａｒｉｔｙ−ｃｈｅｃｋ ｃｏｄｅｓ／リチャードソン（Ｒ． Ｒｉｃｈａｒｄｓｏｎ）およびウルバンケ（Ｒ． Ｌ． Ｕｒｂａｎｋｅ）共著／ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ， Ｖｏｌ． ４７．， Ｎｏ． ２， ｐｐ．６３８−６５６／２００１年２月）」に、「ほぼ三角形」の形
【数１２】
【００４５】
たとえば、図６に関して本明細書で前に説明した手法に従う場合には、ほぼ三角行列を生成するために、ステップ１は同一のままであるが、行列Ｈを、ブロック行列形式で
【数１３】
【００４６】
ｊｐ×ｋｐの行列
【数１４】
【００４７】
明らかに、ステップ１の行列Ｈを、行方向および列方向に切り詰めて、符号語長およびパリティ検査数の特定の値を実現することができる。
【００４８】
前に示したように、図７に関して本明細書で前に説明した手法も、ほぼ三角形のパリティ検査行列を得るのに使用することができる。この目的のためには、行列ＨＳのｔ−１個の下側ブロック行を右にサイクリック・シフトすることによって、ステップ１’を変更する。すなわち、最も下のブロック行が、ｔ−１位置だけシフトされ、次に上のブロック行が、ｔ−２位置だけシフトされる。その後、ステップ２’を、そのようにして得られた行列の左下のｔｐ×ｔｐ部分行列だけに適用して、ほぼ三角形の新しい行列をもたらす。行列全体が、ほぼ三角行列であり、４サイクルがなく、「Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｃｏｎｓｔｒｕｃｔｉｏｎｓ ｏｆ ｉｒｒｅｇｕｌａｒ Ｇａｌｌａｇｅｒ ｃｏｄｅｓ（マッケイ（Ｄ． Ｊ． Ｃ． ＭａｃＫａｙ）、ウィルソン（Ｓ． Ｔ． Ｗｉｌｓｏｎ）、およびダベイ（Ｍ． Ｃ． Ｄａｖｅｙ）共著／ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｖｏｌ． ４７， Ｎｏ． １０， ｐｐ． １４４９−１４５４／１９９９年１０月）」と、「Ｅｆｆｉｃｉｅｎｔ ｅｎｃｏｄｉｎｇ ｏｆ ｌｏｗ−ｄｅｎｓｉｔｙ ｐａｒｉｔｙ−ｃｈｅｃｋ ｃｏｄｅｓ（リチャードソン（Ｒ． Ｒｉｃｈａｒｄｓｏｎ）およびウルバンケ（Ｒ． Ｌ． Ｕｒｂａｎｋｅ）共著／ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ， Ｖｏｌ． ４７．， Ｎｏ． ２， ｐｐ．６３８−６５６／２００１年２月）」に従う高速ＬＤＰＣ符号化に直接に使用することができる。
【００４９】
やはり、ステップ２’の終りに得られる行列を、行方向および列方向に切り詰めて、符号語長およびパリティ検査数の特定の値を達成することができる。
【００５０】
本発明のいくつかの実施形態では、パリティ検査行列を、通信チャネル２０を介する受信機への送信装置１０の接続の際に、行列定義ロジック３００によって定義することができる。たとえば、行列を、通信チャネル２０の端点間で折衝された次元に基づいて、接続時に行列定義ロジック３００によって作成することができる。具体的に言うと、パリティ検査行列を、受信機から送信装置１０へのコード・パラメータ１７０の供給に基づいて決定することができる。本発明の他の実施形態では、パリティ検査行列を、接続が確立される前に、行列定義ロジック３００によって定義することができる。たとえば、１つまたは複数のパリティ検査行列を、行列定義ロジック３００内で事前設定することができ、各事前設定された行列が、事前設定されたコード長（列数）および事前設定されたパリティ検査数（行数）を有する。複数の事前設定された行列を有する実施形態では、接続の確立時に、適当な行列が、行列定義ロジック３００に対して選択される。そのような選択は、たとえば、前に説明したように通信チャネル２０の端点間の折衝に基づいて実行することができる。
【００５１】
本発明の好ましい実施形態を、これまでは通信システムに関して説明した。しかし、本発明は、そのようなシステムへの適用に制限されない。たとえば、図８を参照すると、前に説明したエンコーダ１１０の実施形態を、情報源４０からのデータをハード・ディスク・ストレージ・チャネルなどのストレージ・チャネルに記憶するデータ記憶システム２１０で使用することもできる。
【００５２】
本明細書で前に説明した送信装置１０、エンコーダ１１０、および行列ジェネレータ１６０のそれぞれを、（１）ハードワイヤード・ロジックによって、（２）コンピュータ・プログラム・コードを用いてプログラムされた汎用プロセッサ／専用ディジタル信号プロセッサによって、または（３）ハードワイヤード・ロジックとコンピュータ・プログラム・コードの組み合わせによって、実施できることを諒解されたい。たとえば、図９を参照すると、前に図２に関して説明したデータ通信システムで、送信装置１０に、メモリ４１０に接続されたプログラマブル・ディジタル信号プロセッサ（ＤＳＰ）４００を含めることができ、メモリ４１０にコンピュータ・プログラム・コード４２０が記憶され、コンピュータ・プログラム・コード４２０が、ＤＳＰ４００によって実行される時に、図５に関して前に説明した方法のステップを実行するようにＤＳＰ４００を構成する。
【００５３】
本明細書で好ましい実施形態に関して本発明を説明したが、当業者は、本発明の範囲から逸脱せずに、形態および詳細におけるさまざまな変更を行うことができることを諒解するであろう。
【００５４】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００５５】
（１）データの低密度パリティ検査（ＬＤＰＣ）符号化の方法であって、
第１のＭ×Ｎパリティ検査行列を定義するステップと、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成するステップと、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングするステップと、
を含む方法。
（２）前記第２のパリティ検査行列から４サイクルを除去するステップをさらに含む、上記（１）に記載の方法。
（３）前記第１のパリティ検査行列の前記定義が、前記第１のパリティ検査行列の行のサイクリック・シフトを含む、上記（１）に記載の方法。
（４）前記Ｍ×Ｍ部分行列の主対角線に沿った要素に同一の値をセットするステップを含む、上記（１）に記載の方法。
（５）データの低密度パリティ検査（ＬＤＰＣ）符号化装置であって、
第１のＭ×Ｎパリティ検査行列を定義する手段と、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手段と、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングする手段と、
を含む装置。
（６）前記第２のパリティ検査行列を生成する手段が、前記第２のパリティ検査行列から４サイクルを除去する手段をさらに含む、上記（５）に記載の装置。
（７）前記第１のパリティ検査行列を定義する手段が、前記第１のパリティ検査行列の行をサイクリック・シフトする、上記（５）に記載の装置。
（８）前記第１のパリティ検査行列を定義する手段が、前記Ｍ×Ｍ部分行列の主対角線に沿った要素に同一の値をセットする、上記（５）に記載の装置。
（９）データの低密度パリティ検査（ＬＤＰＣ）符号化プログラムであって、前記符号化プログラムが、コンピュータ・システムに、
第１のＭ×Ｎパリティ検査行列を定義する手順と、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手順と、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングする手順と、
を実行させるプログラム。
（１０）前記第２のパリティ検査行列から４サイクルを除去する手順をさらにコンピュータ・システムに実行させる、上記（９）に記載のプログラム。
（１１）前記第１のパリティ検査行列の定義が、前記第１のパリティ検査行列のサイクリック・シフトを含む、上記（９）に記載のプログラム。
（１２）データの低密度パリティ検査（ＬＤＰＣ）符号化プログラムを格納したコンピュータ読み取り可能な記憶媒体であって、前記符号化プログラムが、コンピュータ・システムに、
第１のＭ×Ｎパリティ検査行列を定義する手順と、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手順と、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングする手順と、
を実行させるプログラムを格納したコンピュータ読み取り可能な記憶媒体。
（１３）通信チャネルを介して情報源から受信したデータを送信し、前記データを低密度パリティ検査（ＬＤＰＣ）符号語に符号化するデータ通信装置であって、
第１のＭ×Ｎパリティ検査行列を定義する手段と、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手段と、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングする手段と、
を含むデータ通信装置。
（１４）データ・ストレージ・チャネル内の情報源から受信したデータを記憶し、前記データを低密度パリティ検査（ＬＤＰＣ）符号語に符号化するデータ記憶装置であって、
第１のＭ×Ｎパリティ検査行列を定義する手段と、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手段と、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングする手段と、
を含むデータ記憶装置。
【図面の簡単な説明】
【図１】通信システムのブロック図である。
【図２】通信システムの送信装置のブロック図である。
【図３】通信システムのもう１つの送信装置のブロック図である。
【図４】送信装置の行列ジェネレータのブロック図である。
【図５】送信装置のエンコーダ機能に対応する流れ図である。
【図６】行列ジェネレータに対応する流れ図である。
【図７】行列ジェネレータに対応するもう１つの流れ図である。
【図８】データ記憶システムのブロック図である。
【図９】通信システムの送信装置のもう１つの例のブロック図である。
【符号の説明】
１０ 送信装置
２０ 通信チャネル
３０ 情報ビット
４０ 情報源
５０ シンボル
１００ 分割器
１１０ エンコーダ
１２０ シンボル・マッパー
１３０ 第１のグループ
１４０ 第２のグループ
１５０ ブロック・コード
１６０ 行列ジェネレータ
１７０ コード・パラメータ
２１０ データ記憶システム
３００ 行列定義ロジック
３１０ 三角行列ジェネレータ
３２０ 第１のＭ×Ｎパリティ検査行列
４００ プログラマブル・ディジタル信号プロセッサ（ＤＳＰ）
４１０ メモリ
４２０ コンピュータ・プログラム・コード
Claims (14)
- 装置をしてデータの低密度パリティ検査（ＬＤＰＣ）符号化を実行させるための方法であって、前記装置に対して、
第１のＭ×Ｎパリティ検査行列を定義するステップと、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成するステップと、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングするステップと、
を実行させる方法。 - 前記第２のパリティ検査行列から４サイクルを除去するステップをさらに含む、請求項１に記載の方法。
- 前記第１のパリティ検査行列の前記定義が、前記第１のパリティ検査行列の行のサイクリック・シフトを含む、請求項１に記載の方法。
- 前記Ｍ×Ｍ部分行列の主対角線に沿った要素に同一の値をセットするステップを含む、請求項１に記載の方法。
- データの低密度パリティ検査（ＬＤＰＣ）符号化装置であって、
第１のＭ×Ｎパリティ検査行列を定義する手段と、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手段と、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングする手段と、
を含む装置。 - 前記第２のパリティ検査行列を生成する手段が、前記第２のパリティ検査行列から４サイクルを除去する手段をさらに含む、請求項５に記載の装置。
- 前記第１のパリティ検査行列を定義する手段が、前記第１のパリティ検査行列の行をサイクリック・シフトする、請求項５に記載の装置。
- 前記第１のパリティ検査行列を定義する手段が、前記Ｍ×Ｍ部分行列の主対角線に沿った要素に同一の値をセットする、請求項５に記載の装置。
- データの低密度パリティ検査（ＬＤＰＣ）符号化プログラムであって、前記符号化プログラムが、コンピュータ・システムに、
第１のＭ×Ｎパリティ検査行列を定義する手順と、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手順と、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングする手順と、
を実行させるプログラム。 - 前記第２のパリティ検査行列から４サイクルを除去する手順をさらにコンピュータ・システムに実行させる、請求項９に記載のプログラム。
- 前記第１のパリティ検査行列の定義が、前記第１のパリティ検査行列のサイクリック・シフトを含む、請求項９に記載のプログラム。
- データの低密度パリティ検査（ＬＤＰＣ）符号化プログラムを格納したコンピュータ読み取り可能な記憶媒体であって、前記符号化プログラムが、コンピュータ・システムに、
第１のＭ×Ｎパリティ検査行列を定義する手順と、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手順と、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングする手順と、
を実行させるプログラムを格納したコンピュータ読み取り可能な記憶媒体。 - 通信チャネルを介して情報源から受信したデータを送信し、前記データを低密度パリティ検査（ＬＤＰＣ）符号語に符号化するデータ通信装置であって、
第１のＭ×Ｎパリティ検査行列を定義する手段と、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手段と、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングする手段と、
を含むデータ通信装置。 - データ・ストレージ・チャネル内の情報源から受信したデータを記憶し、前記データを低密度パリティ検査（ＬＤＰＣ）符号語に符号化するデータ記憶装置であって、
第１のＭ×Ｎパリティ検査行列を定義する手段と、
前記第１のパリティ検査行列に基づいて、三角行列であるＭ×Ｍ部分行列を有する第２のパリティ検査行列を生成する手段と、
前記第２のパリティ検査行列に基づいて、前記データをＬＤＰＣ符号語にマッピングする手段と、
を含むデータ記憶装置。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US09/902859 | 2001-07-11 | ||
| US09/902,859 US6895547B2 (en) | 2001-07-11 | 2001-07-11 | Method and apparatus for low density parity check encoding of data |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2003115768A JP2003115768A (ja) | 2003-04-18 |
| JP3575606B2 true JP3575606B2 (ja) | 2004-10-13 |
Family
ID=25416512
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2002199657A Expired - Fee Related JP3575606B2 (ja) | 2001-07-11 | 2002-07-09 | データの低密度パリティ検査符号化方法および装置 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US6895547B2 (ja) |
| JP (1) | JP3575606B2 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7337385B2 (en) | 2004-06-23 | 2008-02-26 | Kabushiki Kaisha Toshiba | Decoding apparatus and method for decoding the data encoded with an LDPC code |
Families Citing this family (242)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6307487B1 (en) | 1998-09-23 | 2001-10-23 | Digital Fountain, Inc. | Information additive code generator and decoder for communication systems |
| US7068729B2 (en) * | 2001-12-21 | 2006-06-27 | Digital Fountain, Inc. | Multi-stage code generator and decoder for communication systems |
| WO2003021440A1 (en) * | 2001-09-01 | 2003-03-13 | Bermai, Inc. | Decoding architecture for low density parity check codes |
| JP3833545B2 (ja) | 2002-02-13 | 2006-10-11 | 三菱電機株式会社 | 通信システム、受信機、送信機および通信方法 |
| JP4042841B2 (ja) * | 2002-03-29 | 2008-02-06 | 富士通株式会社 | 行列演算処理装置 |
| US6920601B1 (en) | 2002-04-08 | 2005-07-19 | Sanera Systems Inc. | Error correction for data communication |
| US6968491B1 (en) * | 2002-04-08 | 2005-11-22 | Sanera Systems Inc. | Generating a check matrix for error correction |
| EP1359672A1 (en) * | 2002-05-03 | 2003-11-05 | Siemens Aktiengesellschaft | Method for improving the performance of concatenated codes |
| JP3946087B2 (ja) * | 2002-05-23 | 2007-07-18 | 三菱電機株式会社 | 通信システム、受信機および通信方法 |
| JP4224022B2 (ja) * | 2002-06-11 | 2009-02-12 | デジタル ファウンテン， インコーポレイテッド | イナクティブ化によって連鎖反応符号を復号化するためのシステムおよび処理 |
| US9240810B2 (en) * | 2002-06-11 | 2016-01-19 | Digital Fountain, Inc. | Systems and processes for decoding chain reaction codes through inactivation |
| EP1518328B1 (en) * | 2002-07-03 | 2007-04-18 | The DIRECTV Group, Inc. | Encoding of low-density parity check (ldpc) codes using a structured parity check matrix |
| US7020829B2 (en) * | 2002-07-03 | 2006-03-28 | Hughes Electronics Corporation | Method and system for decoding low density parity check (LDPC) codes |
| US6829308B2 (en) * | 2002-07-03 | 2004-12-07 | Hughes Electronics Corporation | Satellite communication system utilizing low density parity check codes |
| US7577207B2 (en) | 2002-07-03 | 2009-08-18 | Dtvg Licensing, Inc. | Bit labeling for amplitude phase shift constellation used with low density parity check (LDPC) codes |
| US7266750B1 (en) | 2002-07-10 | 2007-09-04 | Maxtor Corporation | Error recovery strategies for iterative decoders |
| US7864869B2 (en) * | 2002-07-26 | 2011-01-04 | Dtvg Licensing, Inc. | Satellite communication system utilizing low density parity check codes |
| US20040019845A1 (en) * | 2002-07-26 | 2004-01-29 | Hughes Electronics | Method and system for generating low density parity check codes |
| US7350130B2 (en) * | 2002-08-15 | 2008-03-25 | Broadcom Corporation | Decoding LDPC (low density parity check) code with new operators based on min* operator |
| US7178080B2 (en) * | 2002-08-15 | 2007-02-13 | Texas Instruments Incorporated | Hardware-efficient low density parity check code for digital communications |
| US6909383B2 (en) | 2002-10-05 | 2005-06-21 | Digital Fountain, Inc. | Systematic encoding and decoding of chain reaction codes |
| KR20040033554A (ko) | 2002-10-15 | 2004-04-28 | 삼성전자주식회사 | 에러 정정 부호화 장치 및 그 방법 |
| US7702986B2 (en) * | 2002-11-18 | 2010-04-20 | Qualcomm Incorporated | Rate-compatible LDPC codes |
| KR100936022B1 (ko) * | 2002-12-21 | 2010-01-11 | 삼성전자주식회사 | 에러 정정을 위한 부가정보 생성 방법 및 그 장치 |
| US20040157626A1 (en) * | 2003-02-10 | 2004-08-12 | Vincent Park | Paging methods and apparatus |
| JP4163023B2 (ja) * | 2003-02-28 | 2008-10-08 | 三菱電機株式会社 | 検査行列生成方法および検査行列生成装置 |
| US8196000B2 (en) * | 2003-04-02 | 2012-06-05 | Qualcomm Incorporated | Methods and apparatus for interleaving in a block-coherent communication system |
| KR100996029B1 (ko) | 2003-04-29 | 2010-11-22 | 삼성전자주식회사 | 저밀도 패리티 검사 코드의 부호화 장치 및 방법 |
| DE602004030869D1 (de) * | 2003-05-30 | 2011-02-17 | Sony Corp | Dekodierverfahren, dekodiervorrichtung, programm, aufzeichnungs-/wiedergabevorrichtung und -verfahren, und wiedergabevorrichtung und -verfahren |
| US7814392B2 (en) * | 2003-06-20 | 2010-10-12 | Intel Corporation | System, apparatus and methods of dynamically determined error correction codes in communication systems |
| US8140931B2 (en) * | 2003-07-03 | 2012-03-20 | Dtvg Licensing, Inc. | Method and system for generating parallel decodable low density parity check (LDPC) codes |
| US7213197B2 (en) * | 2003-08-08 | 2007-05-01 | Intel Corporation | Adaptive bit loading with low density parity check forward error correction |
| KR100809619B1 (ko) | 2003-08-26 | 2008-03-05 | 삼성전자주식회사 | 이동 통신 시스템에서 블록 저밀도 패러티 검사 부호부호화/복호 장치 및 방법 |
| US7237174B2 (en) * | 2003-09-04 | 2007-06-26 | The Directv Group, Inc. | Method and system for providing short block length low density parity check (LDPC) codes in support of broadband satellite applications |
| US7334181B2 (en) * | 2003-09-04 | 2008-02-19 | The Directv Group, Inc. | Method and system for providing short block length low density parity check (LDPC) codes |
| US6771197B1 (en) * | 2003-09-26 | 2004-08-03 | Mitsubishi Electric Research Laboratories, Inc. | Quantizing signals using sparse generator factor graph codes |
| CN1954501B (zh) | 2003-10-06 | 2010-06-16 | 数字方敦股份有限公司 | 通过通信信道接收从源发射的数据的方法 |
| US7234098B2 (en) * | 2003-10-27 | 2007-06-19 | The Directv Group, Inc. | Method and apparatus for providing reduced memory low density parity check (LDPC) codes |
| US7376883B2 (en) * | 2003-10-27 | 2008-05-20 | The Directv Group, Inc. | Method and system for providing long and short block length low density parity check (LDPC) codes |
| KR20050044963A (ko) * | 2003-11-08 | 2005-05-16 | 삼성전자주식회사 | ｑ차 제곱 잉여류를 이용한 준순환 저밀도 패러티 검사부호 생성 방법 |
| WO2005050885A1 (ja) | 2003-11-21 | 2005-06-02 | Matsushita Electric Industrial Co., Ltd. | マルチアンテナ受信装置、マルチアンテナ受信方法、マルチアンテナ送信装置及びマルチアンテナ通信システム |
| US7406648B2 (en) * | 2003-12-24 | 2008-07-29 | Electronics And Telecommunications Research Institute | Methods for coding and decoding LDPC codes, and method for forming LDPC parity check matrix |
| KR100632268B1 (ko) * | 2003-12-24 | 2006-10-11 | 한국전자통신연구원 | Ｌｄｐｃ 부호 부호화 및 복호화 방법, 및 ｌｄｐｃ패러티 검사 행렬 형성 방법. |
| KR100538281B1 (ko) * | 2003-12-26 | 2005-12-22 | 한국전자통신연구원 | 채널 신뢰도 값의 비균일 양자화를 이용한 복호 전처리장치 및 그를 이용한 저밀도패리티검사 복호 시스템 |
| US7395495B2 (en) * | 2004-01-12 | 2008-07-01 | Intel Corporation | Method and apparatus for decoding forward error correction codes |
| US7802162B2 (en) | 2004-01-20 | 2010-09-21 | Nec Corporation | Parity check matrix generation method, data transmission system, encoding device, decoding device, and a parity check matrix generation program |
| US20050193320A1 (en) * | 2004-02-09 | 2005-09-01 | President And Fellows Of Harvard College | Methods and apparatus for improving performance of information coding schemes |
| US7260763B2 (en) * | 2004-03-11 | 2007-08-21 | Nortel Networks Limited | Algebraic low-density parity check code design for variable block sizes and code rates |
| KR100540663B1 (ko) * | 2004-04-19 | 2006-01-10 | 삼성전자주식회사 | 저밀도 패리티 체크 코딩의 패리티 체크 행렬 변환 방법 |
| CA2559818C (en) * | 2004-04-28 | 2011-11-29 | Samsung Electronics Co., Ltd. | Apparatus and method for coding/decoding block low density parity check code with variable block length |
| JP4971144B2 (ja) | 2004-05-07 | 2012-07-11 | デジタル ファウンテン， インコーポレイテッド | ファイルダウンロードおよびストリーミングのシステム |
| KR20050118056A (ko) * | 2004-05-12 | 2005-12-15 | 삼성전자주식회사 | 다양한 부호율을 갖는 Ｂｌｏｃｋ ＬＤＰＣ 부호를 이용한이동 통신 시스템에서의 채널부호화 복호화 방법 및 장치 |
| KR100762619B1 (ko) | 2004-05-21 | 2007-10-01 | 삼성전자주식회사 | 저밀도 패리티 검사 코드를 이용한 복호화 장치 및 방법 |
| US7526717B2 (en) | 2004-06-16 | 2009-04-28 | Samsung Electronics Co., Ltd. | Apparatus and method for coding and decoding semi-systematic block low density parity check codes |
| US20050283707A1 (en) * | 2004-06-22 | 2005-12-22 | Eran Sharon | LDPC decoder for decoding a low-density parity check (LDPC) codewords |
| KR20050123336A (ko) * | 2004-06-24 | 2005-12-29 | 엘지전자 주식회사 | Ｌｄｐｃ 코드를 이용한 가변 코드 레이트 적응 부호화 방법 |
| US7581157B2 (en) * | 2004-06-24 | 2009-08-25 | Lg Electronics Inc. | Method and apparatus of encoding and decoding data using low density parity check code in a wireless communication system |
| JP4282558B2 (ja) | 2004-06-30 | 2009-06-24 | 株式会社東芝 | 低密度パリティチェック符号復号器及び方法 |
| US7395490B2 (en) * | 2004-07-21 | 2008-07-01 | Qualcomm Incorporated | LDPC decoding methods and apparatus |
| KR101073907B1 (ko) | 2004-07-27 | 2011-10-17 | 엘지전자 주식회사 | Ｌｄｐｃ 코드를 이용한 부호화 방법 및 부호화를 위한컴퓨터로 읽을 수 있는 기록 매체 |
| KR100739684B1 (ko) * | 2004-08-05 | 2007-07-13 | 삼성전자주식회사 | 저밀도 패리티 체크 행렬 생성 장치 및 방법 |
| US7600174B2 (en) | 2004-08-10 | 2009-10-06 | Samsung Electronics Co., Ltd | Apparatus and method for encoding and decoding a block low density parity check code |
| US7203897B2 (en) * | 2004-08-12 | 2007-04-10 | Motorola, Inc. | Method and apparatus for encoding and decoding data |
| US7188297B2 (en) * | 2004-08-12 | 2007-03-06 | Motorola, Inc. | Method and apparatus for encoding and decoding data |
| CN101341659B (zh) * | 2004-08-13 | 2012-12-12 | Dtvg许可公司 | 用于多输入多输出通道的低密度奇偶校验码的码设计与实现的改进 |
| KR100886075B1 (ko) * | 2004-08-13 | 2009-02-26 | 더 디렉티브 그룹, 인크. | 방송 시스템에서 복수의 정보 비트를 포함한 데이터를인코딩하는데 이용되는 저밀도 패리티 검사 코드를설계하기 위한 방법 및 시스템 |
| AU2005273169B2 (en) * | 2004-08-16 | 2008-09-11 | Nokia Technologies Oy | Apparatus and method for coding/decoding block low density parity check code with variable block length |
| FI121431B (fi) * | 2004-09-13 | 2010-11-15 | Tamfelt Pmc Oy | Paperikoneessa käytettävä kudosrakenne ja menetelmä sen valmistamiseksi |
| US7562280B2 (en) * | 2004-09-10 | 2009-07-14 | The Directv Group, Inc. | Code design and implementation improvements for low density parity check codes for wireless routers using 802.11N protocol |
| US7543212B2 (en) * | 2004-09-13 | 2009-06-02 | Idaho Research Foundation, Inc. | Low-density parity-check (LDPC) encoder |
| EP1800405B1 (en) * | 2004-09-17 | 2014-03-12 | LG Electronics Inc. | Encoding and decoding of ldpc codes using structured parity check matrices |
| KR101065693B1 (ko) * | 2004-09-17 | 2011-09-19 | 엘지전자 주식회사 | Ｌｄｐｃ 코드를 이용한 부호화, 복호화 방법 및 부호화또는 복호화를 위한 ｌｄｐｃ 코드 생성 방법 |
| KR20060032807A (ko) * | 2004-10-13 | 2006-04-18 | 삼성전자주식회사 | 저밀도 패리티 체크 행렬 생성 방법 및 장치 |
| US7516389B2 (en) * | 2004-11-04 | 2009-04-07 | Agere Systems Inc. | Concatenated iterative and algebraic coding |
| CN100550655C (zh) * | 2004-11-04 | 2009-10-14 | 中兴通讯股份有限公司 | 一种低密度奇偶校验码的编码器/译码器及其生成方法 |
| US7581159B2 (en) * | 2004-11-23 | 2009-08-25 | Texas Instruments Incorporated | Simplified decoding using structured and punctured LDPC codes |
| KR100669152B1 (ko) | 2004-11-25 | 2007-01-15 | 한국전자통신연구원 | 저밀도 패리티 검사 코드의 부호화 장치 및 방법 |
| KR100641052B1 (ko) | 2004-12-08 | 2006-11-02 | 한국전자통신연구원 | Ｌｄｐｃ 부호기 및 복호기, 및 ｌｄｐｃ 부호화 방법 및복호화 방법 |
| US7555696B2 (en) * | 2004-12-09 | 2009-06-30 | General Instrument Corporation | Method and apparatus for forward error correction in a content distribution system |
| RU2373641C2 (ru) | 2004-12-15 | 2009-11-20 | Нек Корпорейшн | Устройство кодирования с исправлением ошибок и способ кодирования с исправлением ошибок, используемый в нем |
| KR100678521B1 (ko) | 2004-12-20 | 2007-02-02 | 한국전자통신연구원 | 비균일 저밀도 패리티 검사 부호의 부호화 장치 및 방법 |
| KR101216075B1 (ko) * | 2004-12-22 | 2012-12-26 | 엘지전자 주식회사 | 채널 코드를 이용한 복호화 및 복호화 장치 |
| US8438459B2 (en) | 2004-12-22 | 2013-05-07 | Lg Electronics Inc. | Apparatus and method for decoding using channel code |
| EP1832002A1 (en) * | 2004-12-29 | 2007-09-12 | Intel Corporation | Multilevel low density parity-check |
| JP2008526164A (ja) * | 2004-12-29 | 2008-07-17 | インテル・コーポレーション | ３ストライプ・ギルバート低密度パリティ検査符号 |
| US7617439B2 (en) * | 2005-01-10 | 2009-11-10 | Broadcom Corporation | Algebraic construction of LDPC (Low Density Parity Check) codes with corresponding parity check matrix having CSI (Cyclic Shifted Identity) sub-matrices |
| US8675176B2 (en) * | 2005-02-25 | 2014-03-18 | Asml Netherlands B.V. | Parameter control in a lithographic apparatus using polarization |
| US20060195761A1 (en) * | 2005-02-26 | 2006-08-31 | Samsung Electronics Co., Ltd. | Method of generating low-density parity check matrix and method of generating parity information using the low-density parity check matrix |
| US7653867B2 (en) * | 2005-03-01 | 2010-01-26 | The Texas A&M University System | Multi-source data encoding, transmission and decoding using Slepian-Wolf codes based on channel code partitioning |
| US7779326B2 (en) * | 2005-03-01 | 2010-08-17 | The Texas A&M University System | Multi-source data encoding, transmission and decoding using Slepian-Wolf codes based on channel code partitioning |
| US7634710B2 (en) | 2005-03-25 | 2009-12-15 | Teranetics, Inc. | Efficient decoding |
| US7461328B2 (en) | 2005-03-25 | 2008-12-02 | Teranetics, Inc. | Efficient decoding |
| WO2006106841A1 (ja) * | 2005-03-31 | 2006-10-12 | Mitsubishi Denki Kabushiki Kaisha | 誤り訂正符号化装置 |
| JP4494276B2 (ja) * | 2005-03-31 | 2010-06-30 | Ｋｄｄｉ株式会社 | 適応変調装置および適応変調方法 |
| US8010870B2 (en) * | 2005-04-25 | 2011-08-30 | Sony Corporation | Coding apparatus and coding method |
| KR101157246B1 (ko) * | 2005-05-16 | 2012-06-15 | 삼성전자주식회사 | 저밀도 패리티 검사 부호의 패딩 및 천공 방법 |
| US7571372B1 (en) | 2005-06-23 | 2009-08-04 | Marvell International Ltd. | Methods and algorithms for joint channel-code decoding of linear block codes |
| US7523375B2 (en) * | 2005-09-21 | 2009-04-21 | Distribution Control Systems | Set of irregular LDPC codes with random structure and low encoding complexity |
| JP2007087530A (ja) | 2005-09-22 | 2007-04-05 | Rohm Co Ltd | 信号復号方法、信号復号装置および信号記憶システム |
| US7398453B2 (en) * | 2005-10-03 | 2008-07-08 | Motorola, Inc. | Method and apparatus for a low-density parity-check decoder |
| US20070162816A1 (en) * | 2005-10-17 | 2007-07-12 | Samsung Electronics Co., Ltd. | Method for constructing a parity check matrix of an irregular low density parity check code |
| KR100809616B1 (ko) * | 2005-10-19 | 2008-03-05 | 삼성전자주식회사 | 가변 블록 길이를 가지는 블록 저밀도 패리티 검사 부호부호화/복호 장치 및 방법 |
| US7661037B2 (en) | 2005-10-27 | 2010-02-09 | Samsung Electronics Co., Ltd. | LDPC concatenation rules for IEEE 802.11n systems |
| US7489538B2 (en) * | 2005-11-14 | 2009-02-10 | University Of Idaho | Radiation tolerant combinational logic cell |
| US7797611B2 (en) * | 2005-11-14 | 2010-09-14 | International Business Machines Corporation | Creating an error correction coding scheme and reducing data loss |
| US7707479B2 (en) * | 2005-12-13 | 2010-04-27 | Samsung Electronics Co., Ltd. | Method of generating structured irregular low density parity checkcodes for wireless systems |
| JP4558638B2 (ja) * | 2005-12-15 | 2010-10-06 | 富士通株式会社 | 符号器および復号器 |
| US7584406B2 (en) | 2005-12-20 | 2009-09-01 | Samsung Electronics Co., Ltd. | LDPC concatenation rules for IEEE 802.11n system with packets length specific in octets |
| US7620880B2 (en) * | 2005-12-20 | 2009-11-17 | Samsung Electronics Co., Ltd. | LDPC concatenation rules for IEEE 802.11n system with packets length specified in OFDM symbols |
| US20070180344A1 (en) * | 2006-01-31 | 2007-08-02 | Jacobsen Eric A | Techniques for low density parity check for forward error correction in high-data rate transmission |
| US7925965B2 (en) * | 2006-02-02 | 2011-04-12 | Samsung Electronics Co., Ltd | Method for transmitting/receiving signals in a communications system and an apparatus therefor |
| US20070198905A1 (en) * | 2006-02-03 | 2007-08-23 | Nokia Corporation | Transmitter for a communications network |
| JP5550834B2 (ja) | 2006-02-13 | 2014-07-16 | デジタル ファウンテン， インコーポレイテッド | 可変ｆｅｃオーバヘッド及び保護期間を利用したストリーミング及びバッファリング |
| US9270414B2 (en) | 2006-02-21 | 2016-02-23 | Digital Fountain, Inc. | Multiple-field based code generator and decoder for communications systems |
| KR101221897B1 (ko) * | 2006-04-21 | 2013-01-15 | 엘지전자 주식회사 | Ｌｄｐｃ 부호화 장치 |
| US7934143B1 (en) | 2006-04-24 | 2011-04-26 | Marvell International Ltd. | Parity insertion for inner architecture |
| US7657821B1 (en) * | 2006-05-09 | 2010-02-02 | Cisco Technology, Inc. | Error detecting code for multi-character, multi-lane, multi-level physical transmission |
| US7971129B2 (en) | 2006-05-10 | 2011-06-28 | Digital Fountain, Inc. | Code generator and decoder for communications systems operating using hybrid codes to allow for multiple efficient users of the communications systems |
| US8028216B1 (en) | 2006-06-02 | 2011-09-27 | Marvell International Ltd. | Embedded parity coding for data storage |
| US9386064B2 (en) | 2006-06-09 | 2016-07-05 | Qualcomm Incorporated | Enhanced block-request streaming using URL templates and construction rules |
| US9419749B2 (en) | 2009-08-19 | 2016-08-16 | Qualcomm Incorporated | Methods and apparatus employing FEC codes with permanent inactivation of symbols for encoding and decoding processes |
| US9380096B2 (en) | 2006-06-09 | 2016-06-28 | Qualcomm Incorporated | Enhanced block-request streaming system for handling low-latency streaming |
| US9178535B2 (en) * | 2006-06-09 | 2015-11-03 | Digital Fountain, Inc. | Dynamic stream interleaving and sub-stream based delivery |
| US9209934B2 (en) | 2006-06-09 | 2015-12-08 | Qualcomm Incorporated | Enhanced block-request streaming using cooperative parallel HTTP and forward error correction |
| US9432433B2 (en) | 2006-06-09 | 2016-08-30 | Qualcomm Incorporated | Enhanced block-request streaming system using signaling or block creation |
| CN100423454C (zh) * | 2006-06-14 | 2008-10-01 | 北京新岸线移动多媒体技术有限公司 | 一类低密度奇偶校验码的实现方法 |
| CN101355402B (zh) * | 2006-06-14 | 2011-08-03 | 广东新岸线计算机系统芯片有限公司 | 一类低密度奇偶校验码的实现方法及装置 |
| US7576562B1 (en) | 2006-06-19 | 2009-08-18 | The United States Of America As Represented By The United States National Aeronautics And Space Administration | Diagnosable structured logic array |
| JP5215537B2 (ja) * | 2006-06-28 | 2013-06-19 | 三星電子株式会社 | 情報符号化装置、情報復号装置、情報符号化方法、および情報復号方法 |
| KR101154995B1 (ko) * | 2006-07-14 | 2012-06-15 | 엘지전자 주식회사 | Ｌｄｐｃ 부호화를 수행하는 방법 |
| US7831895B2 (en) * | 2006-07-25 | 2010-11-09 | Communications Coding Corporation | Universal error control coding system for digital communication and data storage systems |
| US7752529B2 (en) * | 2006-07-26 | 2010-07-06 | Broadcom Corporation | Combined LDPC (low density parity check) encoder and syndrome checker |
| JP2008065969A (ja) * | 2006-08-09 | 2008-03-21 | Fujitsu Ltd | 符号化装置、復号化装置、符号化方法、復号化方法および記憶装置 |
| JP4856605B2 (ja) * | 2006-08-31 | 2012-01-18 | パナソニック株式会社 | 符号化方法、符号化装置、及び送信装置 |
| US8464120B2 (en) * | 2006-10-18 | 2013-06-11 | Panasonic Corporation | Method and system for data transmission in a multiple input multiple output (MIMO) system including unbalanced lifting of a parity check matrix prior to encoding input data streams |
| US7827464B2 (en) * | 2006-11-15 | 2010-11-02 | Seagate Technology Llc | Iterative read channel architectures with coded modulation |
| US20080155372A1 (en) * | 2006-12-21 | 2008-06-26 | Radiospire Networks, Inc. | Methods and apparatus for improving error indication performance in systems with low-density parity check codes |
| TWI332205B (en) * | 2007-03-01 | 2010-10-21 | Lite On It Corp | Data modulation/encryption method used in holographic stotage system |
| US8261155B2 (en) | 2007-03-09 | 2012-09-04 | Qualcomm Incorporated | Methods and apparatus for encoding and decoding low density parity check (LDPC) codes |
| US7949932B2 (en) * | 2007-03-20 | 2011-05-24 | Quantum Corporation | Strengthening parity check bit protection for array-like LDPC codes |
| US8619974B2 (en) * | 2007-03-27 | 2013-12-31 | Hughes Network Systems, Llc | Method and system for providing spread scrambled coded multiple access (SSCMA) |
| US20100122143A1 (en) | 2007-03-27 | 2010-05-13 | Hughes Network Systems, Llc | Method and system for providing low density parity check (ldpc) coding for scrambled coded multiple access (scma) |
| US8140946B2 (en) * | 2007-03-27 | 2012-03-20 | Hughes Network Systems, Llc | Method and apparatus for generating low rate turbo codes |
| US10630512B2 (en) * | 2007-03-27 | 2020-04-21 | Hughes Network Systems, Llc | Optimal forward error correction for non-orthogonal multiple access (NOMA) communications systems |
| US9461765B2 (en) | 2007-03-27 | 2016-10-04 | Hughes Networks Systems, Llc | Method and system for providing scrambled coded multiple access (SCMA) |
| KR100975696B1 (ko) * | 2007-04-05 | 2010-08-12 | 삼성전자주식회사 | 통신 시스템에서 부호화 장치 및 방법 |
| KR101119302B1 (ko) * | 2007-04-20 | 2012-03-19 | 재단법인서울대학교산학협력재단 | 통신 시스템에서 저밀도 패리티 검사 부호 부호화 장치 및방법 |
| US7945842B2 (en) * | 2007-06-19 | 2011-05-17 | International Business Machines Corporation | Method and apparatus for rateless source coding with/without decoder side information |
| US7958429B2 (en) * | 2007-07-02 | 2011-06-07 | Broadcom Corporation | Distributed processing LDPC (low density parity check) decoder |
| KR101129260B1 (ko) * | 2007-09-12 | 2012-03-27 | 디지털 파운튼, 인크. | 신뢰성 있는 통신들을 가능하게 하는 소스 식별 정보 생성 및 통신 |
| US8181081B1 (en) | 2007-11-30 | 2012-05-15 | Marvell International Ltd. | System and method for decoding correlated data |
| CN100589359C (zh) * | 2008-04-23 | 2010-02-10 | 中兴通讯股份有限公司 | 一种里德索罗蒙码的译码方法及装置 |
| US8509081B2 (en) * | 2008-05-01 | 2013-08-13 | Saudi Arabian Oil Company | Adaptive hybrid wireless and wired process control system and method |
| CN102067673B (zh) * | 2008-05-01 | 2014-01-01 | 法赫德国王石油矿产大学 | 自适应无线过程控制系统和方法 |
| JP5009418B2 (ja) * | 2008-06-09 | 2012-08-22 | パイオニア株式会社 | 検査行列の生成方法及び検査行列、並びに復号装置及び復号方法 |
| US8103931B2 (en) * | 2008-08-27 | 2012-01-24 | Mitsubishi Electric Research Laboratories, Inc. | Method for constructing large-girth quasi-cyclic low-density parity-check codes |
| EP2178213A1 (en) | 2008-10-16 | 2010-04-21 | Thomson Licensing | Methods and apparatuses for error correction coding |
| US8612823B2 (en) * | 2008-10-17 | 2013-12-17 | Intel Corporation | Encoding of LDPC codes using sub-matrices of a low density parity check matrix |
| US8266497B1 (en) * | 2008-10-17 | 2012-09-11 | Link—A—Media Devices Corporation | Manufacturing testing for LDPC codes |
| JP5051109B2 (ja) * | 2008-12-01 | 2012-10-17 | 富士通株式会社 | 行列変換方法、行列変換装置および送受信システム |
| US9281847B2 (en) | 2009-02-27 | 2016-03-08 | Qualcomm Incorporated | Mobile reception of digital video broadcasting—terrestrial services |
| US8341509B2 (en) * | 2009-03-17 | 2012-12-25 | Broadcom Corporation | Forward error correction (FEC) scheme for communications |
| US8464123B2 (en) * | 2009-05-07 | 2013-06-11 | Ramot At Tel Aviv University Ltd. | Matrix structure for block encoding |
| US9288010B2 (en) | 2009-08-19 | 2016-03-15 | Qualcomm Incorporated | Universal file delivery methods for providing unequal error protection and bundled file delivery services |
| GB0916001D0 (en) * | 2009-09-11 | 2009-10-28 | Univ Edinburgh | Inter-carrier modulation |
| US20110096828A1 (en) * | 2009-09-22 | 2011-04-28 | Qualcomm Incorporated | Enhanced block-request streaming using scalable encoding |
| US9917874B2 (en) | 2009-09-22 | 2018-03-13 | Qualcomm Incorporated | Enhanced block-request streaming using block partitioning or request controls for improved client-side handling |
| KR101644656B1 (ko) * | 2009-11-02 | 2016-08-10 | 삼성전자주식회사 | 선형 블록 부호를 사용하는 통신 시스템에서 패리티 검사 행렬을 생성하는 방법과 이를 이용한 채널 부호화/복호화 장치 및 방법 |
| WO2011056833A1 (en) * | 2009-11-04 | 2011-05-12 | Saudi Arabian Oil Company | Adaptive hybrid wireless and wired process control system and method |
| EP2503698B1 (en) | 2009-11-17 | 2018-02-14 | Mitsubishi Electric Corporation | Error correction method and device, and communication system using the same |
| US8081010B1 (en) | 2009-11-24 | 2011-12-20 | Ics, Llc | Self restoring logic |
| US8782489B2 (en) | 2010-02-18 | 2014-07-15 | Hughes Network Systems, Llc | Method and system for providing Low Density Parity Check (LDPC) encoding and decoding |
| US8914709B1 (en) * | 2010-03-04 | 2014-12-16 | Sk Hynix Memory Solutions Inc. | Manufacturing testing for LDPC codes |
| US9225961B2 (en) | 2010-05-13 | 2015-12-29 | Qualcomm Incorporated | Frame packing for asymmetric stereo video |
| US9596447B2 (en) | 2010-07-21 | 2017-03-14 | Qualcomm Incorporated | Providing frame packing type information for video coding |
| US9319448B2 (en) | 2010-08-10 | 2016-04-19 | Qualcomm Incorporated | Trick modes for network streaming of coded multimedia data |
| JP5434890B2 (ja) * | 2010-11-18 | 2014-03-05 | 株式会社Ｊｖｃケンウッド | 符号化装置、符号化方法、プログラム |
| US8958375B2 (en) | 2011-02-11 | 2015-02-17 | Qualcomm Incorporated | Framing for an improved radio link protocol including FEC |
| US9270299B2 (en) | 2011-02-11 | 2016-02-23 | Qualcomm Incorporated | Encoding and decoding using elastic codes with flexible source block mapping |
| US8788922B2 (en) * | 2011-02-28 | 2014-07-22 | Apple Inc | Error correction codes for incremental redundancy |
| US8839069B2 (en) | 2011-04-08 | 2014-09-16 | Micron Technology, Inc. | Encoding and decoding techniques using low-density parity check codes |
| EP2525495A1 (en) | 2011-05-18 | 2012-11-21 | Panasonic Corporation | Bit-interleaved coding and modulation (BICM) with quasi-cyclic LDPC codes |
| CN102868483A (zh) * | 2011-07-06 | 2013-01-09 | 北京新岸线无线技术有限公司 | 一种用于数据传输的方法及装置 |
| US9253233B2 (en) | 2011-08-31 | 2016-02-02 | Qualcomm Incorporated | Switch signaling methods providing improved switching between representations for adaptive HTTP streaming |
| US8756478B2 (en) * | 2011-09-07 | 2014-06-17 | Lsi Corporation | Multi-level LDPC layer decoder |
| CN103023603B (zh) * | 2011-09-20 | 2015-07-08 | 澜起科技（上海）有限公司 | 基于ldpc校验矩阵的比特交织编码调制的实现方法 |
| US9843844B2 (en) | 2011-10-05 | 2017-12-12 | Qualcomm Incorporated | Network streaming of media data |
| US9203434B1 (en) | 2012-03-09 | 2015-12-01 | Western Digital Technologies, Inc. | Systems and methods for improved encoding of data in data storage devices |
| US9294226B2 (en) | 2012-03-26 | 2016-03-22 | Qualcomm Incorporated | Universal object delivery and template-based file delivery |
| US8854759B2 (en) | 2012-04-24 | 2014-10-07 | International Business Machines Corporation | Combined soft detection/soft decoding in tape drive storage channels |
| US8605383B1 (en) | 2012-05-21 | 2013-12-10 | Western Digital Technologies, Inc. | Methods, devices and systems for characterizing polarities of piezoelectric (PZT) elements of a two PZT element microactuator |
| US9178534B2 (en) | 2012-05-29 | 2015-11-03 | International Business Machines Corporation | Methods for partial reverse concatenation for data storage devices using composite codes |
| US9558782B2 (en) | 2012-05-29 | 2017-01-31 | International Business Machines Corporation | Partial reverse concatenation for data storage devices using composite codes |
| US9190076B2 (en) | 2012-05-29 | 2015-11-17 | International Business Machines Corporation | Data format using an efficient reverse concatenated modulation code for magnetic tape recording |
| US8856615B1 (en) | 2012-06-11 | 2014-10-07 | Western Digital Technologies, Inc. | Data storage device tracking log-likelihood ratio for a decoder based on past performance |
| US8972834B2 (en) | 2012-08-28 | 2015-03-03 | Hughes Network Systems, Llc | System and method for communicating with low density parity check codes |
| US8972826B2 (en) | 2012-10-24 | 2015-03-03 | Western Digital Technologies, Inc. | Adaptive error correction codes for data storage systems |
| US9021339B2 (en) | 2012-11-29 | 2015-04-28 | Western Digital Technologies, Inc. | Data reliability schemes for data storage systems |
| US9059736B2 (en) | 2012-12-03 | 2015-06-16 | Western Digital Technologies, Inc. | Methods, solid state drive controllers and data storage devices having a runtime variable raid protection scheme |
| US9619317B1 (en) | 2012-12-18 | 2017-04-11 | Western Digital Technologies, Inc. | Decoder having early decoding termination detection |
| US8966339B1 (en) | 2012-12-18 | 2015-02-24 | Western Digital Technologies, Inc. | Decoder supporting multiple code rates and code lengths for data storage systems |
| US9122625B1 (en) | 2012-12-18 | 2015-09-01 | Western Digital Technologies, Inc. | Error correcting code encoder supporting multiple code rates and throughput speeds for data storage systems |
| US9214963B1 (en) | 2012-12-21 | 2015-12-15 | Western Digital Technologies, Inc. | Method and system for monitoring data channel to enable use of dynamically adjustable LDPC coding parameters in a data storage system |
| US8797664B1 (en) | 2012-12-22 | 2014-08-05 | Western Digital Technologies, Inc. | Polarity detection of piezoelectric actuator in disk drive |
| US9092353B1 (en) | 2013-01-29 | 2015-07-28 | Pmc-Sierra Us, Inc. | Apparatus and method based on LDPC codes for adjusting a correctable raw bit error rate limit in a memory system |
| US9246634B2 (en) | 2013-02-10 | 2016-01-26 | Hughes Network Systems, Llc | Apparatus and method for improved modulation and coding schemes for broadband satellite communications systems |
| US9294131B2 (en) | 2013-02-10 | 2016-03-22 | Hughes Network Systems, Llc | Apparatus and method for improved modulation and coding schemes for broadband satellite communications systems |
| US8887024B2 (en) | 2013-02-10 | 2014-11-11 | Hughes Network Systems, Llc | Apparatus and method for improved modulation and coding schemes for broadband satellite communications systems |
| US9813080B1 (en) | 2013-03-05 | 2017-11-07 | Microsemi Solutions (U.S.), Inc. | Layer specific LDPC decoder |
| US8990661B1 (en) * | 2013-03-05 | 2015-03-24 | Pmc-Sierra Us, Inc. | Layer specific attenuation factor LDPC decoder |
| US10230396B1 (en) * | 2013-03-05 | 2019-03-12 | Microsemi Solutions (Us), Inc. | Method and apparatus for layer-specific LDPC decoding |
| US9397701B1 (en) | 2013-03-11 | 2016-07-19 | Microsemi Storage Solutions (Us), Inc. | System and method for lifetime specific LDPC decoding |
| US9203431B2 (en) | 2013-03-15 | 2015-12-01 | Hughes Networks Systems, Llc | Low density parity check (LDPC) encoding and decoding for small terminal applications |
| US9590656B2 (en) | 2013-03-15 | 2017-03-07 | Microsemi Storage Solutions (Us), Inc. | System and method for higher quality log likelihood ratios in LDPC decoding |
| US9450610B1 (en) | 2013-03-15 | 2016-09-20 | Microsemi Storage Solutions (Us), Inc. | High quality log likelihood ratios determined using two-index look-up table |
| US9454414B2 (en) | 2013-03-15 | 2016-09-27 | Microsemi Storage Solutions (Us), Inc. | System and method for accumulating soft information in LDPC decoding |
| KR20150005853A (ko) | 2013-07-05 | 2015-01-15 | 삼성전자주식회사 | 송신 장치 및 그의 신호 처리 방법 |
| KR102002559B1 (ko) | 2013-07-05 | 2019-07-22 | 삼성전자주식회사 | 송신 장치 및 그의 신호 처리 방법 |
| US9685980B2 (en) * | 2014-03-19 | 2017-06-20 | Samsung Electronics Co., Ltd. | Transmitting apparatus and interleaving method thereof |
| US9417804B2 (en) | 2014-07-07 | 2016-08-16 | Microsemi Storage Solutions (Us), Inc. | System and method for memory block pool wear leveling |
| US9153283B1 (en) | 2014-09-30 | 2015-10-06 | Western Digital Technologies, Inc. | Data storage device compensating for hysteretic response of microactuator |
| US10332613B1 (en) | 2015-05-18 | 2019-06-25 | Microsemi Solutions (Us), Inc. | Nonvolatile memory system with retention monitor |
| US9680505B2 (en) * | 2015-05-19 | 2017-06-13 | Samsung Electronics Co., Ltd. | Transmitting apparatus and interleaving method thereof |
| US9692453B2 (en) * | 2015-05-19 | 2017-06-27 | Samsung Electronics Co., Ltd. | Transmitting apparatus and interleaving method thereof |
| US9705530B2 (en) * | 2015-05-19 | 2017-07-11 | Samsung Electronics Co., Ltd. | Transmitting apparatus and interleaving method thereof |
| US9716516B2 (en) * | 2015-05-19 | 2017-07-25 | Samsung Electronics Co., Ltd. | Transmitting apparatus and interleaving method thereof |
| US9595978B2 (en) * | 2015-05-19 | 2017-03-14 | Samsung Electronics Co., Ltd. | Transmitting apparatus and interleaving method thereof |
| US9847794B2 (en) | 2015-05-19 | 2017-12-19 | Samsung Electronics Co., Ltd. | Transmitting apparatus and interleaving method thereof |
| US9634692B2 (en) * | 2015-05-19 | 2017-04-25 | Samsung Electronics Co., Ltd. | Transmitting apparatus and interleaving method thereof |
| US9799405B1 (en) | 2015-07-29 | 2017-10-24 | Ip Gem Group, Llc | Nonvolatile memory system with read circuit for performing reads using threshold voltage shift read instruction |
| US9886214B2 (en) | 2015-12-11 | 2018-02-06 | Ip Gem Group, Llc | Nonvolatile memory system with erase suspend circuit and method for erase suspend management |
| US9892794B2 (en) | 2016-01-04 | 2018-02-13 | Ip Gem Group, Llc | Method and apparatus with program suspend using test mode |
| WO2017126733A1 (ko) * | 2016-01-19 | 2017-07-27 | 연세대학교 산학협력단 | 고신뢰도 및 저지연 통신에 적합한 ldpc 부호화를 위한 장치 및 방법 |
| US9899092B2 (en) | 2016-01-27 | 2018-02-20 | Ip Gem Group, Llc | Nonvolatile memory system with program step manager and method for program step management |
| US10320421B2 (en) * | 2016-05-13 | 2019-06-11 | Hyperstone Gmbh | Method and device for error correction coding based on high-rate generalized concatenated codes |
| CN106209115B (zh) * | 2016-06-29 | 2019-09-20 | 深圳忆联信息系统有限公司 | 一种数据处理方法及电子设备 |
| US10318389B2 (en) * | 2016-07-15 | 2019-06-11 | Quantum Corporation | Joint de-duplication-erasure coded distributed storage |
| US10157677B2 (en) | 2016-07-28 | 2018-12-18 | Ip Gem Group, Llc | Background reference positioning and local reference positioning using threshold voltage shift read |
| US10291263B2 (en) | 2016-07-28 | 2019-05-14 | Ip Gem Group, Llc | Auto-learning log likelihood ratio |
| US10236915B2 (en) | 2016-07-29 | 2019-03-19 | Microsemi Solutions (U.S.), Inc. | Variable T BCH encoding |
| RU2667772C1 (ru) * | 2017-05-05 | 2018-09-24 | Хуавэй Текнолоджиз Ко., Лтд. | Способ и устройство обработки информации и устройство связи |
| CN109951250B (zh) * | 2017-12-21 | 2021-01-08 | 华为技术有限公司 | 通信信号的ldpc编码方法和装置 |
-
2001
- 2001-07-11 US US09/902,859 patent/US6895547B2/en not_active Expired - Lifetime
-
2002
- 2002-07-09 JP JP2002199657A patent/JP3575606B2/ja not_active Expired - Fee Related
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7337385B2 (en) | 2004-06-23 | 2008-02-26 | Kabushiki Kaisha Toshiba | Decoding apparatus and method for decoding the data encoded with an LDPC code |
Also Published As
| Publication number | Publication date |
|---|---|
| US20030037298A1 (en) | 2003-02-20 |
| US6895547B2 (en) | 2005-05-17 |
| JP2003115768A (ja) | 2003-04-18 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3575606B2 (ja) | データの低密度パリティ検査符号化方法および装置 | |
| US7069492B2 (en) | Method of interleaving a binary sequence | |
| EP1965498B1 (en) | Encoding of LDPC codes with an irregular parity check matrix obtained by masking | |
| US8261152B2 (en) | Apparatus and method for channel encoding/decoding in communication system using variable-length LDPC codes | |
| CN101073205B (zh) | 低密度奇偶校验编码器和解码器以及低密度奇偶校验编码和解码方法 | |
| US8069390B2 (en) | Universal error control coding scheme for digital communication and data storage systems | |
| US7058873B2 (en) | Encoding method using a low density parity check code with a column weight of two | |
| CN103152055B (zh) | 编码和解码通信系统中的信道的设备和方法 | |
| US7774689B2 (en) | Encoding and decoding methods and systems | |
| US8386880B2 (en) | Method for transmitting non-binary codes and decoding the same | |
| JP4392924B2 (ja) | 符号化装置及び方法、記憶媒体 | |
| US8495459B2 (en) | Channel-encoding/decoding apparatus and method using low-density parity-check codes | |
| TW200939639A (en) | Data-processing device, data-processing method, encoding device and encoding method | |
| CA2409179A1 (en) | Systems and methods for ldpc coded modulation | |
| JP2004266463A (ja) | 検査行列生成方法および検査行列生成装置 | |
| US9294130B1 (en) | Quasi-cyclic low-density parity-check (QC-LDPC) encoder | |
| Ye et al. | Optimized rate-adaptive protograph-based LDPC codes for source coding with side information | |
| Jang et al. | Design of LDPC coded BICM in DVB broadcasting systems with block permutations | |
| EP2211470A1 (en) | Generating an exponent table for coding and decoding LDPC codewords of different lengths | |
| Xiao et al. | Systematic binary deterministic rateless codes | |
| Limpaphayom et al. | Power-and bandwidth-efficient communications using LDPC codes | |
| Andreadou et al. | Quasi-Cyclic Low-Density Parity-Check (QC-LDPC) codes for deep space and high data rate applications | |
| Xie et al. | Design of rate-compatible protograph-based LDPC codes with mixed circulants | |
| Hu et al. | A new coding scheme for the noisy-channel Slepian-Wolf problem: Separate design and joint decoding | |
| Qiu et al. | Concatenated Reed-Solomon/Spatially Coupled LDPC Codes |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20040615 |
|
| RD14 | Notification of resignation of power of sub attorney |
Free format text: JAPANESE INTERMEDIATE CODE: A7434 Effective date: 20040615 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20040630 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| LAPS | Cancellation because of no payment of annual fees |