(57)【要約】構成された低密度パリティチェック（ＬＤＰＣ）コードを符号化する方法が提供される。低密度パリティチェック（ＬＤＰＣ）コードの構成されたパリティチェックマトリックスを表す情報を記憶するメモリ1605,1607は符号化プロセス中にアクセスされる。情報は表形式で編成され、各行はパリティチェックマトリックスの列のグループの第１の列内における１の値の発生を表す。行はパリティチェックマトリックスの列のグループに対応し、各グループ内の後続する列は予め定められた演算にしたがって導出される。ＬＤＰＣコード化された信号は、パリティチェックマトリックスを表す記憶された情報に基づいて出力される。
2005520468.tif 000002
【特許請求の範囲】
【請求項１】
低密度パリティチェック（ＬＤＰＣ）コードの構成されたパリティチェックマトリックスを表す情報を記憶したメモリにアクセスし、その情報は表形式で編成され、各行はパリティチェックマトリックスの列のグループの第１の列内における１の値の発生を表し、行はパリティチェックマトリックスの列のグループに対応し、各グループ内の後続する列は予め定められた演算にしたがって導出され、
パリティチェックマトリックスを表す記憶された情報に基づいてＬＤＰＣコード化された信号を出力するステップを含んでいる符号化方法。
【請求項２】
予め定められた演算は、
各グループの第１の列に関して循環シフトを行い、
ＬＤＰＣコードのコードレートに依存するある定数を各グループの第１の列に加算するステップの１つを特定する請求項１記載の方法。
【請求項３】
パリティビットは順次決定され、
パリティチェックマトリックスのｉ番目の行の中のｊ番目のエントリが１である場合に、（ｉ−１）番目のパリティビットおよびｊ番目の情報ビットを追加することによりｉ番目のパリティビットを決定するステップをさらに含んでいる請求項１記載の方法。
【請求項４】
パリティビット累算装置をゼロに初期化し、
パリティチェックマトリックスの（ｊＭ）番目の列の中のｉ番目のエントリが１である場合、ｉ番目のパリティビット累算装置の中のＭの情報ビットのｊ番目のグループの中の第１の情報ビットを累算し、ここでｊ＝０，１，２，３，…ｋldpc／Ｍ−１であり、
パリティビット累算装置の中のｊ番目のグループの残りの（Ｍ−１）の情報ビットｍ＝ｊＭ＋１，ｊＭ＋２，ｊＭ＋３，…，（ｊ＋１）Ｍ−１を｛ｘ＋ｍ  ｍｏｄ  Ｍ×ｑ｝ｍｏｄ（ｎldpc−ｋldpc）にしたがって累算し、ｘはそのグループの中の第１のビットｊＭに対応したパリティビット累算装置のアドレスを示し、ｑはコードレート依存定数であり、
全ての情報ビットが使い尽くされた後、
【数１】
2005520468.tif 000072
にしたがって演算をｉ＝１からスタートして行うステップをさらに含んでおり、ｐi，ｉ＝０，１，…，ｎldpc−ｋldpc−１の最終的な内容はパリティビットｐiに等しい請求項１記載の方法。
【請求項５】
Ｍ＝３６０である請求項４記載の方法。
【請求項６】
コード依存定数ｑは、コードレート２／３，５／６，１／２，３／４，４／５，３／５，８／９および９／１０に対してそれぞれ６０，３０，９０，４５，３６，７２，２０および１８である請求項４記載の方法。
【請求項７】
８−ＰＳＫ（位相シフトキーイング）、１６−ＱＡＭ（直交振幅変調）、ＱＰＳＫ（直交位相シフトキーイング）、１６−ＡＰＳＫ（振幅位相シフトキーイング）および３２−ＡＰＳＫの１つを含む信号コンステレーションにしたがってＬＤＰＣコード化された信号を変調するステップをさらに含んでいる請求項１記載の方法。
【請求項８】
Ｂｏｓｅ  Ｃｈａｕｄｈｕｒｉ  Ｈｏｃｑｕｅｎｇｈｅｍ（ＢＣＨ）コードにしたがって入力信号を符号化するステップをさらに含んでおり、入力信号に対応した出力ＬＤＰＣコード化された信号は、外部ＢＣＨコードおよび内部ＬＤＰＣコードを有するコードを表している請求項１記載の方法。
【請求項９】
冗長ＢＣＨビットの数はｎBCH−ｋBCH＝１６＊ｔであり、ここでｔはＢＣＨコードのエラー補正能力を表している請求項８記載の方法。
【請求項１０】
ＢＣＨコードのエラー補正能力は、レート１／２、３／４、４／５、３／５のＬＤＰＣコードと連結して使用されたときには１２ビットであり、レート２／３および５／６のＬＤＰＣコードと連結して使用されたときには１０ビットであり、レート８／９および９／１０のＬＤＰＣコードと連結して使用されたときには８ビットである請求項８記載の方法。
【請求項１１】
パリティチェックマトリックスの列インデックスｊ＊３６０（ｊ＝０，１，２，３，…，ｋldpc／３６０−１）中の１の行インデックスは、以下の表Ａ乃至Ｈの１つにしたがってｊ番目の行において与えられる：
【表１】
2005520468.tif 000073
【表２】
2005520468.tif 000074
【表３】
2005520468.tif 000075
【表４】
2005520468.tif 000076
【表５】
2005520468.tif 000077
【表６】
2005520468.tif 000078
【表７】
2005520468.tif 000079
【表８】
2005520468.tif 000080
【表９】
2005520468.tif 000081
【表１０】
2005520468.tif 000082
【表１１】
2005520468.tif 000083
【表１２】
2005520468.tif 000084
【表１３】
2005520468.tif 000085
【表１４】
2005520468.tif 000086
【表１５】
2005520468.tif 000087
【表１６】
2005520468.tif 000088
【表１７】
2005520468.tif 000089
【表１８】
2005520468.tif 000090
【表１９】
2005520468.tif 000091
【表２０】
2005520468.tif 000092
【表２１】
2005520468.tif 000093
【表２２】
2005520468.tif 000094
【表２３】
2005520468.tif 000095
請求項１記載の方法。
【請求項１２】
パリティチェックマトリックスのその他の列インデックスｍ（ｍモジュロ３６０≠０およびｍ＜ｋldpc）中の１の行インデックスは｛ｘ＋ｍ  ｍｏｄ３６０×ｑ｝ｍｏｄ（ｎldpc−ｋldpc）によって与えられ、ここでレート２／３のＬＤＰＣコードに対してはｑ＝６０であり、レート５／６のＬＤＰＣコードに対してはｑ＝３０であり、レート１／２のＬＤＰＣコードに対してはｑ＝９０であり、レート３／４のＬＤＰＣコードに対してはｑ＝４５であり、レート４／５のＬＤＰＣコードに対してはｑ＝３６であり、レート３／５のＬＤＰＣコードに対してはｑ＝７２であり、レート８／９のＬＤＰＣコードに対してはｑ＝２０であり、レート９／１０のＬＤＰＣコードに対してはｑ＝１８であり、ｘは表Ａ乃至Ｇのｊ番目の行におけるエントリを示し、ここでｊ＝ｉｎｔ｛ｍ／３６０｝であり、ｉｎｔ｛．｝は整数関数を示し、列インデックスｍ＝ｋldpc＋ｊ（ｊ＝０，１，２，…，ｎldpc−ｋldpc−２）中の１の行インデックスはｊおよびｊ＋１によって与えられ、パリティチェックマトリックスの列インデックスｎldpc−１中の１の行インデックスはｎldpc−ｋldpc−１によって与えられる請求項１１記載の方法。
【請求項１３】
符号化命令が実行されたときに、それが１以上のプロセッサに請求項１記載の方法を行わせるように構成されている命令を有しているコンピュータ読出し可能な媒体。
【請求項１４】
低密度パリティチェック（ＬＤＰＣ）コードの構成されたパリティチェックマトリックスを表す情報を記憶したメモリ(1605,1607)を備えており、その情報は表形式で編成され、各行はパリティチェックマトリックスの列のグループの第１の列内における１の値の発生を表し、行はパリティチェックマトリックスの列のグループに対応し、各グループ内の後続する列は予め定められた演算にしたがって導出され、
ＬＤＰＣコード化された信号を出力するためにパリティチェックマトリックスを表す記憶された情報を検索する手段を備えているＬＤＰＣコードを生成するエンコーダ。
【請求項１５】
予め定められた演算は、各グループの第１の列に関する循環シフトおよび各グループの第１の列へのある定数の加算の１つを特定し、定数はＬＤＰＣコードのコードレートに依存している請求項１４記載のエンコーダ。
【請求項１６】
ｉ番目のパリティビットは、パリティチェックマトリックスのｉ番目の行の中のｊ番目のエントリが１である場合、（ｉ−１）番目のパリティビットおよびｊ番目の情報ビットを追加することにより決定される請求項１４記載のエンコーダ。
【請求項１７】
パリティビット累算装置はゼロに初期化され、Ｍの情報ビットのｊ番目のグループの中の第１の情報ビットは、パリティチェックマトリックスの（ｊＭ）番目の列の中のｉ番目のエントリが１である場合に累算され、ここでｊ＝０，１，２，３，…ｋldpc／Ｍ−１であり、ｊ番目のグループの残りの（Ｍ−１）の情報ビットｍ＝ｊＭ＋１，ｊＭ＋２，ｊＭ＋３，…，（ｊ＋１）Ｍ−１は、パリティチェック累算装置において｛ｘ＋ｍ  ｍｏｄ  Ｍ×ｑ｝ｍｏｄ（ｎldpc−ｋldpc）にしたがって累算され、ｘはそのグループの中の第１のビットｊＭに対応したパリティビット累算装置のアドレスを示し、ｑはコードレート依存定数であり、全ての情報ビットが使い尽くされた後、ｉ＝１からスタートする演算が
【数２】
2005520468.tif 000096
にしたがって行われ、ｐi，ｉ＝０，１，…，ｎldpc−ｋldpc−１の最終的な内容はパリティビットｐiに等しい請求項１４記載のエンコーダ。
【請求項１８】
Ｍ＝３６０である請求項１７記載のエンコーダ。
【請求項１９】
コード依存定数ｑは、コードレート２／３，５／６，１／２，３／４，４／５，３／５，８／９および９／１０に対してそれぞれ６０，３０，９０，４５，３６，７２，２０および１８である請求項１４記載のエンコーダ。
【請求項２０】
ＬＤＰＣコード化された信号は、８−ＰＳＫ（位相シフトキーイング）、１６−ＱＡＭ（直交振幅変調）、ＱＰＳＫ（直交位相シフトキーイング）、１６−ＡＰＳＫ（振幅位相シフトキーイング）および３２−ＡＰＳＫの１つを含む信号コンステレーションにしたがって変調される請求項１１記載のエンコーダ。
【請求項２１】
さらに、Ｂｏｓｅ  Ｃｈａｕｄｈｕｒｉ  Ｈｏｃｑｕｅｎｇｈｅｍ（ＢＣＨ）コードにしたがって入力信号を符号化するように構成されたＢＣＨエンコーダを備えており、入力信号に対応した出力ＬＤＰＣコード化された信号は、外部ＢＣＨコードおよび内部ＬＤＰＣコードを有するコードを表している請求項１４記載のエンコーダ。
【請求項２２】
冗長ＢＣＨビットの数はｎBCH−ｋBCH＝１６＊ｔであり、ここでｔはＢＣＨコードのエラー補正能力を表している請求項２１記載のエンコーダ。
【請求項２３】
ＢＣＨコードのエラー補正能力は、レート１／２、３／４、４／５、３／５のＬＤＰＣコードと連結して使用されたときには１２ビットであり、レート２／３および５／６のＬＤＰＣコードと連結して使用されたときには１０ビットであり、レート８／９および９／１０のＬＤＰＣコードと連結して使用されたときには８ビットである請求項２１記載のエンコーダ。
【請求項２４】
低密度パリティチェック（ＬＤＰＣ）コードの構成されたパリティチェックマトリックスを表す情報を記憶したメモリ(1605,1607)を備えており、その情報は表形式で編成され、各行はパリティチェックマトリックスの列のグループの第１の列内における１の値の発生を表し、行はパリティチェックマトリックスの列のグループに対応し、各グループ内の後続する列は予め定められた演算にしたがって導出され、
メモリ(1605,1607)中に記憶された情報にアクセスしてＬＤＰＣコード化された信号を出力するように構成されたＬＤＰＣエンコーダ(203)を備えているＬＤＰＣコード化を使用する送信機。
【請求項２５】
予め定められた演算は、各グループの第１の列に関する循環シフトおよび各グループの第１の列へのある定数の加算の１つを特定し、定数はＬＤＰＣコードのコードレートに依存している請求項２４記載の送信機。
【請求項２６】
ｉ番目のパリティビットは、パリティチェックマトリックスのｉ番目の行の中のｊ番目のエントリが１である場合、（ｉ−１）番目のパリティビットおよびｊ番目の情報ビットを追加することにより決定される請求項２４記載の送信機。
【請求項２７】
パリティビット累算装置はゼロに初期化され、Ｍの情報ビットのｊ番目のグループの中の第１の情報ビットは、パリティチェックマトリックスの（ｊＭ）番目の列の中のｉ番目のエントリが１である場合に累算され、ここでｊ＝０，１，２，３，…ｋldpc／Ｍ−１であり、ｊ番目のグループの残りの（Ｍ−１）の情報ビットｍ＝ｊＭ＋１，ｊＭ＋２，ｊＭ＋３，…，（ｊ＋１）Ｍ−１は、パリティチェック累算装置において｛ｘ＋ｍ  ｍｏｄ  Ｍ×ｑ｝ｍｏｄ（ｎldpc−ｋldpc）にしたがって累算され、ｘはそのグループの中の第１のビットｊＭに対応したパリティビット累算装置のアドレスを示し、ｑはコードレート依存定数であり、全ての情報ビットが使い尽くされた後、ｉ＝１からスタートする演算が
【数３】
2005520468.tif 000097
にしたがって行われ、ｐi，ｉ＝０，１，…，ｎldpc−ｋldpc−１の最終的な内容はパリティビットｐiに等しい請求項２４記載の送信機。
【請求項２８】
Ｍ＝３６０である請求項２７記載の送信機。
【請求項２９】
コード依存定数ｑは、コードレート２／３，５／６，１／２，３／４，４／５，３／５，８／９および９／１０に対してそれぞれ６０，３０，９０，４５，３６，７２，２０および１８である請求項２４記載の送信機。
【請求項３０】
ＬＤＰＣコード化された信号は、８−ＰＳＫ（位相シフトキーイング）、１６−ＱＡＭ（直交振幅変調）、ＱＰＳＫ（直交位相シフトキーイング）、１６−ＡＰＳＫ（振幅位相シフトキーイング）および３２−ＡＰＳＫの１つを含む信号コンステレーションにしたがって変調される請求項２４記載の送信機。
【請求項３１】
さらに、Ｂｏｓｅ  Ｃｈａｕｄｈｕｒｉ  Ｈｏｃｑｕｅｎｇｈｅｍ（ＢＣＨ）コードにしたがって入力信号を符号化するように構成されたＢＣＨ送信機を備えており、入力信号に対応した出力ＬＤＰＣコード化された信号は、外部ＢＣＨコードおよび内部ＬＤＰＣコードを有するコードを表している請求項２４記載の送信機。
【請求項３２】
冗長ＢＣＨビットの数はｎBCH−ｋBCH＝１６＊ｔであり、ここでｔはＢＣＨコードのエラー補正能力を表している請求項３１記載の送信機。
【請求項３３】
ＢＣＨコードのエラー補正能力は、レート１／２、３／４、４／５、３／５のＬＤＰＣコードと連結して使用されたときには１２ビットであり、レート２／３および５／６のＬＤＰＣコードと連結して使用されたときには１０ビットであり、レート８／９および９／１０のＬＤＰＣコードと連結して使用されたときには８ビットである請求項３１記載の送信機。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は通信システムに関し、とくに、コード化されたシステムに関する。
【背景技術】
【０００２】
本出願は以下の暫定的な特許出願明細書に関連しており、３５  Ｕ．Ｓ．Ｃ§１１９（ｅ）の下にそれらの権利を有している：米国特許出願第60/393,457号明細書（２００２年７月３日出願）、米国特許出願第60/398,760号明細書（２００２年７月２６日出願）、米国特許出願第60/403,812号明細書（２００２年８月１５日出願）、米国特許出願第60/421,505号明細書（２００２年１０月２５日出願）、米国特許出願第60/421,999号明細書（２００２年１０月２９日出願）、米国特許出願第60/423,710号明細書（２００２年１１月４日出願）、米国特許出願第60/440,199号明細書（２００３年１月１５日出願）、米国特許出願第60/447,641号明細書（２００３年２月１４日出願）、米国特許出願第60/456,220号明細書（２００３年３月２０日出願）、２００３年５月９日に出願された米国特許出願明細書（“Description LDPC and BCH Encoders,”）、２００３年６月２４日に出願された米国特許出願明細書（“Description LDPC and BCH Encoders,”）（Attorney Docket:PD-203044）、２００３年６月２４日に出願された米国特許出願明細書（“Description LDPC and BCH Encoders,”）（Attorney Docket:PD-203059）。なお、これらは全てこの明細書において参考文献とされている。
【０００３】
通信システムは、雑音の多い通信チャンネルによる通信の信頼性の高さを保証するためにコード化を使用する。これらの通信チャンネルは、ある信号対雑音比（ＳＮＲ）におけるシンボル当りのビットで表されることのできる固定された容量を示し、理論上の上限（シャノン限界として知られている）を規定する。その結果、コード化設計は、このシャノン限界に近いレートの達成をめざしている。シャノン限界に近いコードのこのような１つのクラスは、低密度パリティチェック（ＬＤＰＣ）コードである。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
伝統的に、ＬＤＰＣコードは、そのいくつかの欠点のためにそれ程広くは配備されてきていない。１つの欠点は、ＬＤＰＣコード化技術が非常に複雑なことである。ＬＤＰＣコードをそのジェネレータマトリックスを使用して符号化するには、非常に大きい非スパースマトリックスを記憶する必要がある。さらに、ＬＤＰＣコードは、効率的である大きいブロックを必要とし、その結果、ＬＤＰＣコードのパリティチェックマトリックスがスパースでも、これらのマトリックスの記憶には問題がある。
【０００５】
構成の観点からは、いくつかの難題に直面する。たとえば、記憶は、ＬＤＰＣコードが実際に広く普及していない重要な理由である。また、ＬＤＰＣコード構成における主要な問題は、デコーダ中のいくつかの処理エンジン（ノード）の間における接続ネットワークをどのようにして達成するかである。さらに、復号プロセスにおける計算負荷、とくに、チェックノード動作には問題がある。
【０００６】
したがって、簡単な符号化および復号プロセスを使用するＬＤＰＣ通信システムが必要とされている。高度な複雑さを伴なわずにＬＤＰＣコードを使用して高いデータレートを効率的にサポートすることもまた必要とされている。ＬＤＰＣエンコーダおよびデコーダの性能を改善する必要もある。ＬＤＰＣコード化を実施するために記憶要求を最小にすることもまた必要とされている。さらに、ＬＤＰＣデコーダ内の処理ノードの間の通信を簡単化する方式もまた必要とされている。
【課題を解決するための手段】
【０００７】
これらおよびその他の必要性は、構成された低密度パリティチェック（ＬＤＰＣ）コードを符号化する方法が提供される本発明によって解決される。ＬＤＰＣコードの構造は、パリティチェックマトリックスの一部分を下方の三角となるように制限し、および、またはデコーダのビットノードとチェックノードとの間の通信が簡単化されるように別の要求を満足することによって提供される。構成されたパリティチェックマトリックスを表す情報を記憶するメモリがアクセスされる。その情報は表形式で編成され、各行はパリティチェックマトリックスの列のグループの第１の列内における１の値の発生を表す。行はパリティチェックマトリックスの列のグループに対応し、各グループ内の後続する列は予め定められた演算（たとえば、論理桁送り、加法等）にしたがって導出される。ＬＤＰＣコード化された信号は、パリティチェックマトリックスを表す記憶された情報に基づいて出力される。本発明の１実施形態によると、Ｂｏｓｅ  Ｃｈａｕｄｈｕｒｉ  Ｈｏｃｑｕｅｎｇｈｅｍ（ＢＣＨ）エンコーダは、ＢＣＨコードを使用して入力信号を符号化するために送信機によって使用され、入力信号に対応した出力ＬＤＰＣコード化された信号は、外部ＢＣＨコードおよび内部ＬＤＰＣコードを有するコードを表している。さらに、周期的冗長検査（ＣＲＣ）コードにしたがって入力信号を符号化するためにＣＲＣエンコーダが提供される。この方法の利点は、ＬＤＰＣコードの適切な符号化および復号を行うことにある。
【０００８】
本発明の１実施形態の１つの特徴によると、ある１つの符号化方法が開示されている。この方法は、低密度パリティチェック（ＬＤＰＣ）コードの構成されたパリティチェックマトリックスを表す情報を記憶したメモリにアクセスするステップを含んでいる。その情報は表形式で編成され、各行はパリティチェックマトリックスの列のグループの第１の列内における１の値の発生を表している。行はパリティチェックマトリックスの列のグループに対応し、各グループ内の後続する列は予め定められた演算にしたがって導出される。この方法はまた、パリティチェックマトリックスを表す記憶された情報に基づいてＬＤＰＣコード化された信号を出力するステップを含んでいる。
【０００９】
本発明の１実施形態の別の特徴によると、低密度パリティチェック（ＬＤＰＣ）コードを生成するエンコーダが開示されている。このエンコーダは、ＬＤＰＣコードの構成されたパリティチェックマトリックスを表す情報を記憶したメモリを備えている。この情報は表形式で編成され、各行はパリティチェックマトリックスの列のグループの第１の列内における１の値の発生を表している  。行はパリティチェックマトリックスの列のグループに対応し、各グループ内の後続する列は予め定められた演算にしたがって導出される。このエンコーダはまた、ＬＤＰＣコード化された信号を出力するためにパリティチェックマトリックスを表す記憶された情報を検索する手段を備えている。
【００１０】
本発明の１実施形態の別の特徴によると、低密度パリティチェック（ＬＤＰＣ）コード化を使用する送信機が開示されている。この送信機は、ＬＤＰＣコードの構成されたパリティチェックマトリックスを表す情報を記憶したメモリを備え、その情報は表形式で編成され、各行はパリティチェックマトリックスの列のグループの第１の列内における１の値の発生を表す。行はパリティチェックマトリックスの列のグループに対応し、各グループ内の後続する列は予め定められた演算にしたがって導出される。この送信機はまた、メモリからの記憶された情報にアクセスしてＬＤＰＣコード化された信号を出力するように構成されたＬＤＰＣエンコーダを備えている。
【００１１】
本発明のさらに別のアスペクト、特徴および利点は、本発明を実施するために考えられた最良のモードを含む多数の特定の実施形態および構成を単に例示することにより以下の詳細な説明から容易に明らかになるであろう。本発明はまた別の異なった実施形態が可能であり、そのいくつかの詳細は種々の明白な点において本発明の技術的範囲を逸脱することなく修正されることができる。したがって、その図面および説明は何等発明の技術的範囲に制限を課すものではなく、本質的に例示とみなされるものである。
【発明を実施するための最良の形態】
【００１２】
本発明は、添付図面の図において発明の技術的範囲を制限するものではなく単なる例示として示されている。なお、図面において、同じ参照符号は類似した構成要素を示している。  
低密度パリティチェック（ＬＤＰＣ）コードを効率的に復号するためのシステム、方法およびソフトウェアを説明する。以下の説明において、多くの特定の詳細は本発明を完全に理解するために説明の目的で記載されている。しかしながら、本発明はこれらの特定の詳細なしで、あるいは等価の構成により実現可能であることは当業者に明らかである。他の例において、よく知られている構造および装置は、本発明をいたずらに不明瞭にすることを避けるためにブロック図の形態で示されている。
【００１３】
図１は、低密度パリティチェック（ＬＤＰＣ）コードを使用するように構成された本発明の１実施形態による通信システムの概略図である。デジタル通信システム100は、受信機105に対して通信チャンネル103を横切って信号波形を発生する送信機101を備えている。このディスクリートな通信システム100において、送信機101は可能なメッセージの離散セットを生成するメッセージソースを有しており、その可能なメッセージのそれぞれが対応した信号波形を有している。これらの信号波形は通信チャンネル103により減衰され、あるいはそうでなければ変更される。雑音チャンネル103に関するこの問題を克服するためにＬＤＰＣコードが使用される。
【００１４】
送信機101により発生されたＬＤＰＣコードは、パフォーマンス損失を招くことなく高速構成を可能にする。送信機101から出力されたこれらの構成されたＬＤＰＣコードは、変調方式（たとえば、８−ＰＳＫ）のためにすでにチャンネルエラーを受け易くなっているビットノードに対して少数のチェックノードを割当てることを避ける。
【００１５】
このようなＬＤＰＣコードは対応可能な復号アルゴリズム（ターボコードとは異なり）を有しており、それは加算、比較およびテーブルルックアップのような単純な動作を都合よく含んでいる。さらに、注意深く設計されたＬＤＰＣコードは、エラーフロアの兆候を示さない。
【００１６】
本発明の１実施形態によると、送信機101は受信機105と通信するために、比較的簡単な符号化技術を使用してパリティチェックマトリックス（復号中効率的なメモリアクセスを容易にする）に基づいてＬＤＰＣコードを発生する。送信機101は、ブロック長が十分に大きければ、連結されたターボ＋ＲＳ（リード・ソロモン）コードをしのぐことができるＬＤＰＣコードを使用する。
【００１７】
図２Ａおよび２Ｂは、図１の送信機内に配備された例示的なＬＤＰＣエンコーダの概略図である。図２Ａに見られるように、送信機200は、情報ソース201からの入力を受取って、受信機105におけるエラー補正処理に適した高度に冗長なコード化されたストリームを出力するＬＤＰＣエンコーダ203を備えている。情報ソース201は、デイスクリートなアルファベットＸからｋ個の信号を発生する。ＬＤＰＣコードはパリティチェックマトリックスにより特定される。他方において、ＬＤＰＣコードを符号化するには、一般に、ジェネレータマトリックスを特定する必要がある。たとえ、ガウスの消去法を使用してパリティチェックマトリックスからジェネレータマトリックスを得ることが可能であっても、結果的に得られるマトリックスはもはやスパースではなく、大きいジェネレータマトリックスを記憶することは複雑である可能性が高い。
【００１８】
エンコーダ203は、構造がパリティチェックマトリックスになるようにすることによってパリティチェックマトリックスだけを利用する簡単な符号化技術を使用してアルファベットＹから変調装置205に信号を発生する。とくに、パリティチェックマトリックスには、このマトリックスのある部分を三角であるように制約することによりある制限が課せられる。このようなパリティチェックマトリックスの構成は、以下図６においてさらに詳細に説明される。このような制限の結果、パフォーマンス損失は無視できる程度のものとなり、したがってこれは魅力的なトレードオフである。
【００１９】
変調装置205はエンコーダ203からの符号化されたメッセージを、送信アンテナ207に送られる信号波形にマップし、この送信アンテナ207は通信チャンネル103によりこれらの波形を放射する。送信アンテナ207からの送信は、以下に説明するように受信機に伝播する。
【００２０】
図２ＢはＢｏｓｅ  Ｃｈａｕｄｈｕｒｉ  Ｈｏｃｑｕｅｎｇｈｅｍ（ＢＣＨ）エンコーダおよび周期的冗長検査（ＣＲＣ）エンコーダにより使用される本発明の１実施形態によるＬＤＰＣエンコーダを示している。このシナリオでは、ＣＲＣエンコーダ209およびＢＣＨエンコーダ211と共にＬＤＰＣエンコーダ203により発生されたコードは、連結された外部ＢＣＨコードおよび内部低密度パリティチェック（ＬＤＰＣ）コードを有する。さらに、周期的冗長検査（ＣＲＣ）コードを使用してエラー検出が行われる。例示的な実施形態において、ＣＲＣエンコーダ209はジェネレータ多項式（ｘ5＋ｘ4＋ｘ3＋ｘ2＋１）（ｘ2＋ｘ＋１）（ｘ＋１）により８ビットＣＲＣコードを使用して符号化する。
【００２１】
ＬＤＰＣエンコーダ203は、
【数４】
2005520468.tif 000003
【００２２】
のサイズの情報ブロックを、
【数５】
2005520468.tif 000004
【００２３】
のサイズのコードワードに系統的に符号化する。コードワードの送信は所定の順序でｉ0からスタートし、
【数６】
2005520468.tif 000005
【００２４】
で終了する。以下の表１には、ＬＤＰＣコードパラメータ（ｎldpc，ｋldpc）が示されている。
【表２４】
2005520468.tif 000006
【００２５】
ＬＤＰＣエンコーダ203のタスクは、ｋldpcの情報ビット： 
【数７】
2005520468.tif 000007
【００２６】
のあらゆるブロックに対するｎldpc−ｋldpcのパリティビット：
【数８】
2005520468.tif 000008
【００２７】
を決定することである。その手順は次のとおりである。最初に、パリティビットが初期化される；
【数９】
2005520468.tif 000009
【００２８】
表３乃至１０の第１の行において指定されたパリティビットアドレスで第１の情報ビットｉ0が累算される。たとえば、レート２／３（表３）に対する結果は次のようになる：
【数１０】
2005520468.tif 000010
【００２９】
（全ての加算はＧＦ（２）内のものである。）
【００３０】
その後、次の３５９個の情報ビットｉm，ｍ＝１，２，…，３５９については、これらのビットはパリティビットアドレス｛ｘ＋ｍ  ｍｏｄ３６０×ｑ｝ｍｏｄ（ｎldpc−ｋldpc）で累算され、ここでｘは第１のビットｉ0に対応したパリティビット累算装置のアドレスを示し、ｑは表２において特定されたコードレート依存定数を示している。この例を続けると、レート２／３に対してｑ＝６０である。例示すると、情報ビットｉ1に対して、以下の演算が行われる：
【数１１】
2005520468.tif 000011
【００３１】
３６１番目の情報ビットｉ360に関しては、パリティビット累算装置のアドレスは表３乃至１０の第２の行中に与えられる。同様に、後続する３５９個の情報ビットｉm，ｍ＝３６１，３６２，…，７１９に対するパリティビット累算装置のアドレスは公式｛ｘ＋ｍ  ｍｏｄ３６０×ｑ｝ｍｏｄ（ｎldpc−ｋldpc）を使用して得られ、ここでｘは情報ビットｉ360、すなわち、表３乃至１０の第２の行の中のエントリに対応したパリティビット累算装置のアドレスを示している。同様に、３６０の新しい情報ビットのグループ毎に、パリティビット累算装置のアドレスを見出すために表３乃至１０からの新しい行が使用される。
【００３２】
全ての情報ビットが使い尽くされた後、最後のパリティビットは次のように得られる。最初に、以下の演算がｉ＝１からスタートして行われる：
【数１２】
2005520468.tif 000012
【００３３】
ｐi，ｉ＝０，１，…，ｎldpc−ｋldpc−１の最後の内容はパリティビットｐiに等しい。
【表２５】
2005520468.tif 000013
【表２６】
2005520468.tif 000014
【表２７】
2005520468.tif 000015
【表２８】
2005520468.tif 000016
【表２９】
2005520468.tif 000017
【表３０】
2005520468.tif 000018
【表３１】
2005520468.tif 000019
【表３２】
2005520468.tif 000020
【表３３】
2005520468.tif 000021
【表３４】
2005520468.tif 000022
【表３５】
2005520468.tif 000023
【表３６】
2005520468.tif 000024
【表３７】
2005520468.tif 000025
【表３８】
2005520468.tif 000026
【表３９】
2005520468.tif 000027
【表４０】
2005520468.tif 000028
【表４１】
2005520468.tif 000029
【表４２】
2005520468.tif 000030
【表４３】
2005520468.tif 000031
【表４４】
2005520468.tif 000032
【表４５】
2005520468.tif 000033
【表４６】
2005520468.tif 000034
【表４７】
2005520468.tif 000035
【００３４】
ＢＣＨエンコーダ211に関して、ＢＣＨコードパラメータは表１１に列挙されている。
【表４８】
2005520468.tif 000036
【００３５】
上記の表において、ｎbch＝ｋldpcであることが認識される。
【００３６】
ｔエラー補正ＢＣＨエンコーダ211のジェネレータ多項式は、以下の表１２のリスト中の最初のｔ個の多項式を乗算することにより得られる：
【表４９】
2005520468.tif 000037
【００３７】
コードワード：
【数１３】
2005520468.tif 000038
【００３８】
への情報ビット：
【数１４】
2005520468.tif 000039
【００３９】
のＢＣＨ符号化は、次のように行われる。メッセージ多項式：
【数１５】
2005520468.tif 000040
【００４０】
は、
【数１６】
2005520468.tif 000041
【００４１】
により乗算される。次に、
【数１７】
2005520468.tif 000042
【００４２】
がｇ（ｘ）により除算される。
【数１８】
2005520468.tif 000043
【００４３】
を剰余とすると、コードワード多項式は次のように定められる：
【数１９】
2005520468.tif 000044
【００４４】
上記のＬＤＰＣコードは、例示的な実施形態において、ＭＰＥＧ（モーション・ピクチャ・エキスパート・グループ）パケット伝送のような種々のデジタルビデオアプリケーションに使用されることができる。
【００４５】
図３は、図１のシステム内の例示的な受信機の概略図である。受信側において、受信機300は、送信機200から受信された信号の復調を行う復調装置301を備えている。これらの信号は、復調のために受信アンテナ303で受信される。受信された信号は復調後にデコーダ305に転送され、このデコーダ305はビット計量発生装置307と協力してメッセージＸ’を発生することにより元のソースメッセージの再構成を試みる。非グレーマッピングに関して、ビット計量発生装置307は復号プロセス中にデコーダ305と確率情報を前後に（反復的に）交換する。これは図１０に詳細に示されている。その代りに、グレーマッピングが使用された（本発明の１実施形態にしたがって）場合、ビット計量発生装置307の１つのパスで十分であり、このとき各ＬＤＰＣデコーダ反復の後におけるビット計量発生の別の試みにより、限られたパフォーマンス改良が得られる可能性が高い。このアプローチは、図１１に関してさらに詳細に説明される。本発明によって提供される利点を認識するために、図４において説明されるように、ＬＤＰＣコードがどのようにして発生されるかを示すことが有益である。
【００４６】
図４は、本発明の１実施形態によるスパースパリティチェックマトリックスの概略図である。ＬＤＰＣコードは、スパースパリティチェックマトリックスＨ(n-k)xnを有する長い線形ブロックコードである。典型的に、ブロック長ｎの範囲は何千乃至何万のビットである。図４には、たとえば、長さｎ＝８およびレート１／２のＬＤＰＣコードに対するパリティチェックマトリックスが示されている。同じコードは図５における２部分グラフにより等価に表されることができる。
【００４７】
図５は、図４のマトリックスのＬＤＰＣコードの２部分グラフの概略図である。パリティチェック方程式は、各チェックノードに対して、全ての隣接したビットノードの和（ＧＦ（ガロア域）（２）にわたる）がゼロに等しいことを示すものである。図面に示されているように、ビットノードはグラフの左側を占め、予め定められた関係にしたがって１以上のチェックノードと関連している。たとえば、チェックノードｍ1に対応して、式：ｎ1＋ｎ4＋ｎ5＋ｎ8＝０がビットノードに関して存在する。
【００４８】
受信機303に戻ると、ＬＤＰＣデコーダ305はメッセージパッシングデコーダとみなされ、それによってデコーダ305はビットノードの値を見出すことをめざしている。このタスクを行うために、ビットノードおよびチェックノードは互いに反復的に通信する。以下、この通信の特性を以下説明する。
【００４９】
チェックノードからビットノードへは、各チェックノードは隣接したビットノードに別の隣接したビットノードからの情報に基づいてそのビットノードの値に関する推定値（“オピニオン”）を提供する。たとえば、上記の例において、ｎ4，ｎ5およびｎ8の和がｍ1に０“のように見えた”場合、ｍ1は、ｎ1の値が０であると考えられる（ｎ1＋ｎ4＋ｎ5＋ｎ8＝０であるため）ことをｎ1に示す；その他の場合には、ｍ1は、ｎ1の値が１であると考えられることをｎ1に示す。さらに、ソフト決定復号のために、信頼性尺度が追加される。
【００５０】
ビットノードからチェックノードへは、各ビットノードは隣接したチェックノードに対してそれの別の隣接したチェックノードからのフィードバックに基づいてそれ自身の値に関する推定値を中継する。上記の例において、ｎ1は２つの隣接したチェックノードｍ1およびｍ3だけを有している。ｍ3からｍ1へのフィードバックがｎ1の値がおそらく０であることを示した場合、ｎ1はｎ1自身の値の推定値が０であることをｍ1に知らせる。ビットノードが３以上の隣接したチェックノードを有している場合に対しては、ビットノードは、それが通信するチェックノードにその決定を報告する前に、それの別の隣接したチェックノードからのフィードバックに関する多数決投票（ｍａｊｏｒｉｔｙ  ｖｏｔｅ）（ソフト決定）を行う。上記のプロセスは、全てのビットノードが正しいとみなされる（すなわち、全てのパリティチェック方程式が満足される）まで、あるいは予め定められた最大反復数に達し、それによって復号の失敗が宣言されるまで繰返される。
【００５１】
図６は、サブマトリックスが下方三角領域に制限されたパリティチェック値を含んでいる、本発明の１実施形態によるスパースパリティチェックマトリックスのサブマトリックスの概略図である。上述されたように、エンコーダ203（図２Ａおよび２Ｂの）は、パリティチェックマトリックスの下方の三角領域に値を制限することにより単純な符号化技術を使用することができる。本発明の１実施形態によると、パリティチェックマトリックスに課せられる制限は、
Ｈ(n-k)xn＝［Ａ(n-k)xkＢ(n-k)x(n-k)］
の形式のものであり、ここで、Ｂは下方の三角である。
【００５２】
任意の情報ブロックｉ＝（ｉ0，ｉ1，…，ｉk-1）は、ＨｃT＝０を使用して、パリティビットについて反復的に解くことによりコードワードｃ＝（ｉ0，ｉ1，…，ｉk-1，ｐ0，ｐ1，…ｐn-k-1）に符号化される。たとえば、
【数２０】
2005520468.tif 000045
【００５３】
ｐ2，ｐ3，…，ｐn-k-1に対しても同様である。
【００５４】
図７は、制限されていないパリティチェックマトリックス（Ｈマトリックス）を使用したコードと図６の制限されたＨマトリックスを使用したコードとの間のパフォーマンスを示すグラフである。このグラフは、一方が一般的なパリティチェックマトリックスによるものであり、他方が符号化を簡単化するために下方の三角に制限されたパリティチェックマトリックスによるものである２つのＬＤＰＣコードの間のパフォーマンス比較を示している。変調方式は、このシミュレーションにおいて８−ＰＳＫである。パフォーマンス損失は０．１ｄＢ以内である。したがって、パフォーマンス損失は下方の三角Ｈマトリックスの制限に基づいて無視できる程小さく、一方符号化技術の簡単化による利得は大きい。したがって、行および、または列置換（ｐｅｒｍｕｔａｔｉｏｎ）状態において下方の三角または上方の三角に等価であるパリティチェックマトリックスが同じ目的のために使用されることができる。
【００５５】
図８Ａおよび８Ｂはそれぞれ、図１のシステムにおいてそれぞれ使用されることのできる非グレー８−ＰＳＫ変調方式およびグレー８−ＰＳＫ変調方式の概略図である。図８Ａの非グレー８−ＰＳＫ方式は図３の受信機において使用され、非常に低いフレーム消去レート（ＦＥＲ）を必要とするシステムを提供することができる。この要求はまた、Ｂｏｓｅ，Ｃｈａｕｄｈｕｒｉ，およびＨｏｃｑｕｅｎｇｈｅｍ（ＢＣＨ）、ハミング、またはリード・ソロモン（ＲＳ）コードのような外部コードと共同して図８Ｂに示されているグレー８−ＰＳＫ方式を使用することにより満足されることができる。
【００５６】
この方式の下では、８−ＰＳＫ変調を使用することのできるＬＤＰＣデコーダ305（図３）とビット計量発生装置307との間で繰返しを行う必要はない。外部コードが存在しないとき、グレーラベル付けを使用するＬＤＰＣデコーダ305は、以下において図９で示されるように早期のフロアエラーを示す。
【００５７】
図９は、図８Ａのグレーラベル付けを使用したコードと図８Ｂの非グレーラベル付けを使用したコードとの間のパフォーマンスを示すグラフである。エラーフロアは、ＬＤＰＣデコーダ305からの正しいフィードバックを仮定すると、既知の２ビットによる２つの８−ＰＳＫシンボルは非グレーラベル付けによるほうがいっそう遠くに離れているため、非グレーラベル付けによる８−ＰＳＫビット計量の再生のほうが正確であることに由来する。これは同様に、高い信号対雑音比（ＳＮＲ）での動作として見られる。したがって、グレーまたは非グレーラベル付けを使用した同じＬＤＰＣコードのエラー漸近線が同じ傾斜を有していても（すなわち、互いに平行であっても）、非グレーラベル付けによるものは任意のＳＮＲで低いＦＥＲを通過する。
【００５８】
他方において、それ程低いＦＥＲを必要としないシステムに対しては、ＬＤＰＣデコーダ305と８−ＰＳＫビット計量発生装置307との間の反復を伴なわないグレーラベル付けのほうが適切かもしれない。これは、全ての各ＬＤＰＣデコーダ反復の前に８−ＰＳＫビット計量を再生することにより、追加の複雑さが生じるためである。さらに、グレーラル付けが使用されたとき、全ての各ＬＤＰＣデコーダ反復の前に８−ＰＳＫビット計量を再生しても、ごくわずかなパフォーマンス改善しか得られない。上述したように、反復を伴なわないグレーラベル付けは、外部コードが構成される場合、非常に低いＦＥＲを必要とするシステムに対して使用されることができる。
【００５９】
グレーラベル付けと非グレーラベル付けとの間の選択はまた、ＬＤＰＣコードの特性にも依存する。典型的に、ビットまたはチェックノード度が高くなると、それだけいっそうグレーラベル付けが適切になる。これは、高いノード度に関しては、非グレーラベル付けによるほうが、ＬＤＰＣデコーダ305から８−ＰＳＫ（または類似の高次の変調）ビット計量発生装置307への最初のフィードバックが低下するためである。
【００６０】
８−ＰＳＫ（または類似の高次の）変調が２進デコーダにより使用されたとき、シンボルの３（以上の）ビットは“等しい雑音で”受取られないことが認識される。たとえば、グレー８−ＰＳＫラベル付けに関して、あるシンボルの第３のビットはデコーダに対する雑音が他の２ビットより多いと考えられる。したがって、ＬＤＰＣコード設計では、８−ＰＳＫシンボルの“雑音が多い”第３のビットにより表されるこれらのビットノードは、これらのビットが２度とペナルティーを科せられないように、少数のエッジを割当てられない。
【００６１】
図１０は、本発明の１実施形態による非グレーマッピングを使用するＬＤＰＣデコーダの動作のフローチャートである。このアプローチの下では、ＬＤＰＣデコーダおよびビット計量発生装置は、次々に反復する。この例においては、８−ＰＳＫ変調が使用されている。しかしながら、同じ原理は他の高次変調方式にも適用される。このシナリオにおいて、復調装置301は、受取られた雑音の多いシンボル地点と８−ＰＳＫシンボル地点との間の距離を表す距離ベクトルｄをビット計量発生装置307に出力することを仮定すると、ベクトルコンポーネントは次のようになる：
【数２１】
2005520468.tif 000046
【００６２】
８−ＰＳＫビット計量発生装置307は、ｕおよびａとしてそれぞれ表される演繹的確率情報および経験的確率情報を交換するためにＬＤＰＣデコーダ305と通信する。すなわち、ベクトルはｕおよびａはそれぞれコードビットの対数尤度比の演繹的確率情報および経験的確率情報を表す。
【００６３】
８−ＰＳＫビット計量発生装置307は、次のように３ビットの各グループに対する演繹的尤度比を生成する。最初に、コード化されたビットに関する非本質的情報が得られる：
ｅｊ＝ａｊ−ｕｊ      ｊ＝０，１，２
次に、８−ＰＳＫシンボル確率：ｐi      （ｉ＝０，１，…，７）が決定される。
【数２２】
2005520468.tif 000047
【００６４】
次に、ビット計量発生装置307は以下のように、ＬＤＰＣデコーダ305への入力としてコード化されたビットの演繹的対数尤度比を決定する：
【数２３】
2005520468.tif 000048
【００６５】
３以上の変数を有する関数ｆ（．）は、たとえば、ｆ（ａ，ｂ，ｃ）＝ｆ（ｆ（ａ，ｂ），ｃ）のように反復的に推定されることが可能なことが認識される。
【００６６】
以下、非グレーマッピングを使用するＬＤＰＣデコーダ305の動作を説明する。ステップ1001において、ＬＤＰＣデコーダ305は以下にしたがった（および図１２Ａに示されているように）最初の反復の前に、コード化されたビットｖの対数尤度比を初期化する：
【数２４】
2005520468.tif 000049
【００６７】
ステップ1003において、チェックノードｋが更新され、それによって入力ｖにより出力ｗが得られる。図１２Ｂに見られるように、チェックノードｋに対してそのｄcの隣接ビットノードから入ってきたメッセージは、
【数２５】
2005520468.tif 000050
【００６８】
によって示される。目的は、ｄcの隣接ビットノードに戻ってチェックノードｋから出ていくメッセージを計算することである。これらのメッセージは、次のように示される：
【数２６】
2005520468.tif 000051
【００６９】
この関数ｇ（）は以下のように規定される：
【数２７】
2005520468.tif 000052
【００７０】
関数ｆに類似して、３以上の変数を有する関数ｇは、反復的に推定されることができる。
【００７１】
次に、ステップ1005において、デコーダ305は、以下の関係が成立するように経験的確率情報を出力する（図１２のＣ）：
【数２８】
2005520468.tif 000053
【００７２】
ステップ1007において、全てのパリティチェック式が満足されたか否かが決定される。これらのパリティチェック式が満足されていない場合、デコーダ305はステップ1011に示されているように、８−ＰＳＫビット計量およびチャンネル入力ｕnを再度求める。次に、ビットノードはステップ1013に示されているように更新される。図１４Ｃに示されているように、ビットノードｎに対してそれのｄvの隣接チェックノードから入ってきたメッセージは、
【数２９】
2005520468.tif 000054
【００７３】
によって示される。ビットノードｎから出ていくメッセージはｄvの隣接ビットノードに戻って計算される；このようなメッセージは、
【数３０】
2005520468.tif 000055
【００７４】
によって示され、次のように計算される：
【数３１】
2005520468.tif 000056
【００７５】
ステップ1013において、デコーダ305はハード決定を出力する（全てのパリティチェック式が満足される場合に）：
【数３２】
2005520468.tif 000057
【００７６】
上記のアプローチは、非グレーラベル付けが使用されたときに適切である。しかしながら、グレーラベル付けが実施されたとき、図１１のプロセスが実行される。
【００７７】
図１１は、本発明の１実施形態によるグレーマッピングを使用する図３のＬＤＰＣデコーダの動作のフローチャートである。グレーラベル付けが使用されたとき、全ての各ＬＤＰＣデコーダ反復の後にビット計量を再生することにより公称パフォーマンス改善が得られる可能性があるため、ビット計量は都合よくＬＤＰＣデコーダの前に一度だけ生成されることが有効である。図１０のステップ1001および1003に関するように、ステップ1101においてコードビッドｖの対数尤度比の初期化が行われ、ステップ1103においてチェックノードが更新される。次にステップ1105に示されているように、ビットノードｎが更新される。その後、デコーダは経験的確率情報を出力する（ステップ1107）。ステップ1109において、全てのパリティチェック式が満足されているか否かが決定される：そうであるならば、デコーダはハード決定を出力する（ステップ1111）。そうでない場合には、ステップ1103-1107が繰返される。
【００７８】
図１３のＡは、順方向・逆方向アプローチを使用してチェックノードとビットノードとの間の出ていくメッセージを計算する本発明の１実施形態によるプロセスのフローチャートである。ｄcの隣接エッジを有するチェックノードに対して、ｄc（ｄc−１）および多数のｇ（．，．）関数の計算が行われる。しかしながら、順方向・逆方向アプローチは計算の複雑さを３（ｄc−２）に軽減し、この場合ｄc−１の変数が記憶される。
【００７９】
図１２のＢに戻ると、チェックノードｋに対してそのｄcの隣接ビットノードから入ってきたメッセージは次のように示される：
【数３３】
2005520468.tif 000058
【００８０】
出ていくメッセージは、チェックノードｋからｄcの隣接ビットノードに戻って計算されることが望ましい；これらの出ていくメッセージは次のように示されている：
【数３４】
2005520468.tif 000059
【００８１】
出ていくメッセージの計算に対する順方向・逆方向アプローチの下では、順方向変数ｆ1，ｆ2，…，ｆdcは以下のように規定される：
【数３５】
2005520468.tif 000060
【００８２】
これらの順方向変数はステップ1301において計算され、ステップ1303で記憶される。
【００８３】
同様に、逆方向変数ｂ1，ｂ2，…，ｂdcは以下のように規定される：
【数３６】
2005520468.tif 000061
【００８４】
それから、これらの順方向変数はステップ1305において計算される。その後、ステップ1307において、記憶された順方向変数および計算された逆方向変数に基づいて出ていくメッセージが計算される。この出ていくメッセージは次のように計算される：
【数３７】
2005520468.tif 000062
【００８５】
このアプローチの下において、順方向変数ｆ2，ｆ3，…，ｆdcだけが記憶される必要がある。逆方向変数ｂiは計算されているので、出ていくメッセージ：
【数３８】
2005520468.tif 000063
【００８６】
は同時に計算され、それによって逆方向変数を記憶する必要性をなくする。
【００８７】
次に説明するように、計算負荷は並列アプローチによってさらに増強されることができる。
【００８８】
図１３のＢは、並列アプローチを使用してチェックノードとビットノードとの間の出ていくメッセージを計算する本発明の１実施形態によるプロセスのフローチャートである。ｄcの隣接ビットノードからの入力：
【数３９】
2005520468.tif 000064
【００８９】
を有するチェックノードｋに対して、ステップ1311に示されているように、以下のパラメータが計算される：
【数４０】
2005520468.tif 000065
【００９０】
ｇ（．，．）関数はまた、次のように表されることができることが認識される：
【数４１】
2005520468.tif 000066
【００９１】
ｇ（．，．）関数の反復特性を利用することにより、結果的に次式が得られる：
【数４２】
2005520468.tif 000067
【００９２】
したがって、
【数４３】
2005520468.tif 000068
【００９３】
は以下のように解かれることができる：
【数４４】
2005520468.tif 000069
【００９４】
上記の式のｌｎ（．）の項は、関数ｌｎ｜ｅx−１｜を表すルックアップテーブルＬＵＴxを使用して得られる（ステップ1313）。他のルックアップテーブルＬＵＴfまたはＬＵＴgとは異なり、このＬＵＴxはおそらく、量子化レベルの数と同じ数のエントリを必要とする。γkが得られると、ステップ1315に示されているように、全てのｎiに対する
【数４５】
2005520468.tif 000070
【００９５】
の計算は、上記の方程式を使用して並列に行われることができる。
【００９６】
γkの計算の待ち時間は、都合よく、ｌｏｇ2（ｄc）である。
【００９７】
図１４Ａ乃至図１４Ｃは、本発明の種々の実施形態にしたがって発生されたＬＤＰＣコードのシミュレーション結果を示すグラフである。とくに、図１４Ａ乃至図１４Ｃは、高次の変調と３／４（ＱＰＳＫ、１．４８５ビット／シンボル）、２／３（８−ＰＳＫ、１．９８０ビット／シンボル）、および５／６（８−ＰＳＫ、２．４７４ビット／シンボル）のコードレートを有するＬＤＰＣコードのパフォーマンスを示している。
【００９８】
チェックノードとビットノードとの間の相互接続を実現するための２つの一般的なアプローチ、すなわち：（１）完全並列アプローチ、および（２）部分的並列アプローチが存在する。完全並列アーキテクチャにおいて、ノードおよびそれらの相互接続の全てが物理的に構成される。このアーキテクチャの利点は速度である。
【００９９】
しかしながら、完全並列アーキテクチャは全てのノードおよびそれらの相互接続を行うときにかなりの複雑さを伴う可能性がある。したがって、完全並列アーキテクチャでは、複雑さを減少させるために小さいブロックサイズが必要とされる可能性がある。その場合には、結果的に、同じクロック周波数に対して、スループットが比例して減少すると共に、ＦＥＲ対Ｅｓ／Ｎｏパフォーマンスにおいて若干の低下が生じる可能性がある。
【０１００】
ＬＤＰＣコードの構成に対する第２のアプローチは、ノードの総数の部分集合だけを物理的に実現し、これらの限られた数の“物理的”ノードを使用して、そのコードの“機能的”ノードを全て処理することである。ＬＤＰＣデコーダの動作が非常に単純なものにされることが可能であり、並列に行われることが可能でも、設計における別の難題は、“ランダムに”分布されたビットノードとチェックノードとの間において通信がどのようにして設定されるかである。本発明の１実施形態によるデコーダ305（図３の）は見かけ上ランダムなコードを実現するようにある構成方式でメモリにアクセスすることによってこの問題を解決する。図１５Ａおよび図１５Ｂに関して、このアプローチを説明する。
【０１０１】
図１５Ａおよび図１５Ｂはそれぞれ、ＬＤＰＣコード化のときにランダム化を達成するために構成されたアクセスをサポートするように編成された本発明の１実施形態によるメモリの上方エッジおよび下方エッジの概略図である。構成されたアクセスは、パリティチェックマトリックスの発生に集中することにより、真にランダムなコードのパフォーマンスに妥協せずに行われることができる。一般に、パリティチェックマトリックスは、チェックノードとビットノードとの接続により特定されることができる。たとえば、ビットノードは、例示のために３９２である固定されたサイズのグループに分割されることができる。さらに、度数３の第１のビットノードに接続されるチェックノードは、たとえば、ａ，ｂおよびｃの番号を付けられることを仮定すると、第２のビットノードに接続されるチェックノードはａ＋ｐ，ｂ＋ｐおよびｃ＋ｐの番号を付けられ、第３のビットノードに接続されるチェックノードはａ＋２ｐ，ｂ＋２ｐおよびｃ＋２ｐ等の番号を付けられ、ここでｐ＝（チェックノードの数）／３９２である。３９２ビットノードの次のグループに対しては、ｐの適切な選択により全てのチェックノードが同じ度数を有するように、第１のビットノードに接続されるチェックノードはａ，ｂ，ｃとは異なっている。結果的に得られるＬＤＰＣコードがサイクル４およびサイクル６フリーであるように、ランダムサーチが自由定数に対して行われる。本発明のパリティチェックマトリックスの構造上の特徴のために、エッジ情報は復号中に関連したエッジ値のグループへの並行アクセスを可能にするように記億されることができる。
【０１０２】
換言すると、本発明のアプローチは、チェックノードおよびビットノード処理中のメモリアクセスを容易にする。２部分グラフにおけるエッジの値は、ランダムアクセスメモリ（ＲＡＭ）のような記憶媒体中に記憶されることができる。チェックノードおよびビットノードの処理中、真にランダムなＬＤＰＣコードに対してエッジの値はランダムな方式で１つづつアクセスされる必要があることが認識される。しかしながら、このような通常のアクセス方式は、高いデータレートのアプリケーションには遅過ぎる。図１５Ａおよび図１５ＢのＲＡＭは、関連したエッジの大きいグループが１クロックサイクルで取り出されることができる方式で編成されている；したがって、これらの値は予め定められた方式または配列にしたがってメモリ中に“一緒に”配置されている。実際には、真にランダムなコードでさえ、チェックノード（およびそれぞれにビットノード）のグループに対しては、関連エッジはＲＡＭ中に隣接して配置されることが可能であるが、しかしビットノード（それぞれにチェックノード）のグループに隣接した関連エッジはＲＡＭ中においてランダムに分散されることが認識される。したがって、本発明における“一緒”はパリティチェックマトリックス自身の設計に由来する。すなわち、このチェックマトリックス設計は、ビットノードとチェックノードのグループに対する関連エッジがＲＡＭ中に同時に一緒に配置されることを保証する。
【０１０３】
図１５Ａおよび図１５Ｂに見られるように、各ボックスは、多くのビット（たとえば、６）であるエッジの値を含んでいる。本発明の１実施形態によるエッジＲＡＭは、上方エッジＲＡＭ1501(図１５Ａ)および下方エッジＲＡＭ1503(図１５Ｂ)の２つの部分に分割されている。下方エッジＲＡＭ1503は、たとえば、度数２のビットノードとチェックノードとの間のエッジを含んでいる。上方エッジＲＡＭは、２より大きい度数のビットノードとチェックノードとの間のエッジを含んでいる。したがって、あらゆるチェックノードに対して、２つの隣接したエッジが下方エッジＲＡＭ1503中に記憶され、そのエッジの残りのものは上方エッジＲＡＭ1501中に記憶される。たとえば、種々のコードレートに対する上方エッジＲＡＭ1501および下方エッジＲＡＭ1503のサイズは表１４に示されている：
【表５０】
2005520468.tif 000071
【０１０４】
この表１４に基づいて、サイズが５７６×３９２のエッジＲＡＭは、１／２、２／３、３／４および５／６の全てのコードレートに対するエッジマトリックスを記憶するのに十分である。
【０１０５】
認識されるように、この例示的なシナリオ下では、一度で処理するために３９２のビットノードと３９２のチェックノードのグループが選択される。３９２のチェックノード処理については、（ｑ＝ｄc−２）個の連続した行が上方エッジＲＡＭ1501からアクセスされ、２つの連続した行が下方エッジＲＡＭ1503からアクセスされる。ｄcの値は特定のコードに依存し、たとえば、上記のコードについてはレート１／２に対してｄc＝７、レート２／３に対してｄc＝１０、レート３／４に対してｄc＝１６、およびレート５／６に対してｄc＝２２である。当然ながら、別のコードに対するｄcの別の値が可能である。この例において、ｑ＋２は各チェックノードの度数である。
【０１０６】
ビットノード処理について、３９２のビットノードのグループが度数２を有している場合、それらのエッジは下方エッジＲＡＭ1503の２つの連続した行中に配置される。ビットノードが度数ｄ＞２を有している場合、それらのエッジは上方エッジＲＡＭ1501のあるｄの行の中に配置される。これらのｄ行のアドレスは、読出し専用メモリ（ＲＯＭ）のような不揮発性メモリ中に記憶されることができる。その行の１つの中のエッジは３９２のビットノードの第１のエッジに対応し、別の行中のエッジは３９２のビットノードの第２のエッジに対応する等々である。さらに、各行に対して、３９２のグループ中の第１のビットノードに属するエッジの列インデックスもまたＲＯＭ中に記憶されることができる。第２、第３等の他のビットノードに対応したエッジは“ラップアラウンド”方式で開始時の列インデックスに続く。たとえば、行の中のｊ番目のエッジが第１のビットノードに属している場合、（ｊ＋１）番目のエッジは第２のビットノードに属し、（ｊ＋２）番目のエッジは第３のビットノードに属し、・・・、（ｊ−１）番目のエッジは第３９２のビットノードに属する。
【０１０７】
図１５Ａおよび１５Ｂに示されている編成により、メモリアクセスの速度はＬＤＰＣコード化中に大幅に増加される。
【０１０８】
図１６は、本発明による実施形態が実施されることのできるコンピュータシステムを示している。コンピュータシステム1600はバス1601または情報を伝達する別の通信メカニズムと、バス1601に接続された情報を処理するプロセッサ1603とを備えている。コンピュータシステム1600はまた、バス1601に接続されてプロセッサ1603により実行されるべき命令および情報を記憶するランダムアクセスメモリ（ＲＡＭ）または別の動的装置のような主メモリ1605を備えている。この主メモリ1605はまた、命令がプロセッサ1603により実行されている期間中に一時的な変数またはその他の中間的な情報を記憶するために使用されることができる。コンピュータシステム1600はさらに、静的情報およびプロセッサ1603に対する命令を記憶する読出し専用メモリ（ＲＯＭ）1607または別の静的記憶装置を備え、それはバス1601に接続されている。さらにバス1601には、情報および命令を記憶する磁気ディスクまたは光学ディスクのような記憶装置1609が接続されている。
【０１０９】
コンピュータシステム1600は、情報をコンピュータユーザに表示する陰極線管（ＣＲＴ）、液晶ディスプレイ、アクティブマトリックスディスプレイ、またはプラズマディスプレイのような表示装置1611に対してバス1601を介して結合されてもよい。バス1601には、情報およびコマンド選択をプロセッサ1603に伝達する英数字その他のキーを含むキーボードのような入力装置1613が結合されている。別のタイプのユーザ入力装置は、方向情報およびコマンド選択をプロセッサ1603に伝達すると共に表示装置1611上のカーソルの移動を制御するマウス、トラックボール、またはカーソル方向キーのようなカーソル制御装置1615である。
【０１１０】
本発明の１実施形態によると、ＬＤＰＣコードの発生は、主メモリ1605中に含まれている命令のアレンジメントを実行するプロセッサ1603に応答してコンピュータシステム1600により行われる。このような命令は、記憶装置1609のような別のコンピュータ読出し可能な媒体から主メモリ1605中に読出されることができる。プロセッサ1603は、主メモリ1605中に含まれている命令のアレンジメントを実行することによりこの明細書に記載されている処理ステップを行う。多重処理構成された１以上のプロセッサもまた、主メモリ1605中に含まれている命令を実行するために使用されてもよい。別の実施形態において、本発明の実施形態を実施するソフトウェア命令の代りに、またはそれと共にハードワイヤード回路が使用されてもよい。したがって、本発明の実施形態はハードウェア回路およびソフトウェアの特定の組合せに限定されない。
【０１１１】
コンピュータシステム1600はまた、バス1601に接続された通信インターフェース1617を備えている。この通信インターフェース1617は、ローカルネットワーク1621に接続されたネットワークリンク1619に結合された両方向データ通信を提供する。たとえば、通信インターフェース1617は、デジタル加入者ライン（ＤＳＬ）カードまたはモデム、統合サービスデジタル網（ＩＳＤＮ）カード、ケーブルモデム、あるいは対応したタイプの電話線に対するデータ通信接続を提供するための電話モデムであってもよい。別の例として、通信インターフェース1617は、適合するＬＡＮへのデータ通信接続を行う他のローカルエリアネットワーク（ＬＡＮ）カード（たとえば、イーサネット（登録商標）または非同期転送モデル（ＡＴＭ）ネットワーク用の）であってもよい。無線リンクもまた構成されることができる。任意のこのような構成において、通信インターフェース1617は、種々のタイプの情報を表すデジタルデータストリームを伝送する電気信号、電磁信号または光信号を送受信する。さらに、通信インターフェース1617は、ユニバーサルシリアルバス（ＵＳＢ）インターフェース、ＰＣＭＣＩＡ（パーソナルコンピュータメモリカードインターナショナルアソシエーション）インターフェース等のような周辺インターフェース装置を備えていることができる。
【０１１２】
ネットワークリンク1619は典型的に、１以上のネットワークによる別のデータサービスへのデータ通信を提供する。たとえば、ネットワークリンク1619は、ネットワーク1625（たとえば、広域ネットワーク（ＷＡＮ）または今は“インターネット”と呼ばれているグローバルパケットデータ通信ネットワーク）への、あるいはサービスプロバイダにより動作されるデータ装置への接続を有するホストコンピュータ1623へローカルネットワーク1621を通って接続を提供することができる。ローカルネットワーク1621およびネットワーク1625は共に電気信号、電磁信号または光信号を使用して情報および命令を伝達する。種々のネットワークを通る信号、ネットワークリンク1619上の信号、およびコンピュータシステム1600とデジタルデータを通信する通信インターフェース1617からの信号は、情報および命令を伝送する例示的な形態の搬送波である。
【０１１３】
コンピュータシステム1600は、ネットワーク、ネットワークリンク1619および通信インターフェース1617を通ってメッセージを送り、プログラムコードを含むデータを受信することができる。インターネットの例では、サーバ（示されていない）は、本発明の１実施形態を実施するアプリケーションプログラムに属するリクエストされたコードをネットワーク1625、ローカルネットワーク1621および通信インターフェース1617を通って送信する。プロセッサ1603は、その送信されたコードが受信され、および、または後に実行されるために記憶装置1609または別の不揮発性記憶装置中に記憶されているあいだにこれを実行することができる。このようにして、コンピュータシステム1600はアプリケーションコードを搬送波の形態で得ることができる。
【０１１４】
この明細書において使用されている“コンピュータ読出し可能な媒体”という用語は、命令をその実行のためにプロセッサ1603に与えることに関係する任意の媒体を示している。このような媒体は、不揮発性媒体、揮発性媒体および伝送媒体を含むが、それに限定されない多くの形態をとることができる。不揮発性媒体には、たとえば、記憶装置1609のような光学または磁気ディスクが含まれる。揮発性媒体には、主メモリ1605のような動的記憶装置が含まれる。伝送媒体には、バス1601を構成するワイヤを備えた同軸ケーブル、銅線および光ファイバが含まれる。伝送媒体はまた、無線周波数（ＲＦ）および赤外線（ＩＲ）データ通信中に生成されたもののような音波、光または電磁波の形態をとることができる。一般的な形態のコンピュータ読出し可能な媒体には、たとえば、フロッピー（Ｒ）ディスク、フレキシブルディスク、ハードディスク、磁気テープ、任意の他の磁気媒体、ＣＤ−ＲＯＭ、ＣＤＲＷ、ＤＶＤ、任意の他の光学媒体、パンチカード、紙テープ、光学式マークシート、孔のパターンまたは光学的に認識可能なしるしを有する任意の他の物理的媒体、ＲＡＭ、ＰＲＯＭ、およびＥＰＲＯＭ、ＦＬＡＳＨ−ＥＰＲＯＭ、任意の他のメモリチップまたはカートリッジ、搬送波、あるいはコンピュータが読出すことのできる任意の他の媒体が含まれる。
【０１１５】
種々の形態のコンピュータ読出し可能な媒体が、命令をその実行のためにプロセッサに与えるために使用されることができる。たとえば、本発明の少なくとも一部を実行する命令は最初に、遠隔コンピュータの磁気ディスク上で生成されてもよい。このようなシナリオでは、遠隔コンピュータは命令を主メモリ中にロードし、その命令をモデムを使用して電話線で送信する。ローカルコンピュータシステムのモデムは電話線上のデータを受信し、赤外線送信機を使用してそのデータを赤外線信号に変換し、その赤外線信号をパーソナルデジタルアシスタント（ＰＤＡ）およびラップトップのような可搬計算装置に送信する。この可搬計算装置上の赤外線検出器は、赤外線信号から生成された情報および命令を受取ってそのデータをバスに供給する。バスはデータを主メモリに送り、この主メモリからプロセッサが命令を検索し、実行する。主メモリにより受取られた命令は、プロセッサによる実行の前または後に随意に記憶装置上に記憶されることができる。
【０１１６】
このように、本発明の種々の実施形態は、構成された低密度パリティチェック（ＬＤＰＣ）コードを符号化する方法を提供する。ＬＤＰＣコードの構造は、パリティチェックマトリックスの一部分を下方の三角となるように制限し、および、またはデコーダのビットノードとチェックノードとの間の通信が簡単化されるように別の要求を満足することによって提供される。構成されたパリティチェックマトリックスを表す情報を記憶するメモリがアクセスされる。その情報は表形式で編成され、各行はパリティチェックマトリックスの列のグループの第１の列内における１の値の発生を表す。行はパリティチェックマトリックスの列のグループに対応し、各グループ内の後続する列は予め定められた演算（たとえば、論理桁送り、加法等）にしたがって導出される。ＬＤＰＣコード化された信号は、パリティチェックマトリックスを表す記憶された情報に基づいて出力される。本発明の１実施形態によると、Ｂｏｓｅ  Ｃｈａｕｄｈｕｒｉ  Ｈｏｃｑｕｅｎｇｈｅｍ（ＢＣＨ）エンコーダは、ＢＣＨコードを使用して入力信号を符号化するために送信機によって使用され、入力信号に対応した出力ＬＤＰＣコード化された信号は、外部ＢＣＨコードおよび内部ＬＤＰＣコードを有するコードを表している。さらに、周期的冗長検査（ＣＲＣ）コードにしたがって入力信号を符号化するためにＣＲＣエンコーダが提供される。上記の方法の利点は、性能を犠牲にすることなく複雑さを軽減することにある。
【０１１７】
本発明はいくつかの実施形態および構成との関連して説明されたが、本発明はそれにより限定されるものではなく、添付されている請求の範囲の技術的範囲内にある種々の明らかな修正および等価な構成を包含するものである。
【図面の簡単な説明】
【０１１８】
【図１】本発明の１実施形態にしたがって低密度パリティチェック（ＬＤＰＣ）コードを使用するように構成された通信システムの概略図。
【図２Ａ】図１の送信機内に配備された例示的なＬＤＰＣエンコーダの概略図。
【図２Ｂ】図１の送信機内に配備された例示的なＬＤＰＣエンコーダの概略図。
【図３】図１のシステム内の例示的な受信機の概略図。
【図４】本発明の１実施形態によるスパースパリティチェックマトリックスの概略図。
【図５】図４のマトリックスのＬＤＰＣコードの２部グラフの概略図。
【図６】サブマトリックスが下方三角領域に制限されたパリティチェック値を含んでいる、本発明の１実施形態によるスパースパリティチェックマトリックスのサブマトリックスの概略図。
【図７】制限されていないパリティチェックマトリックス（Ｈマトリックス）を使用したコードと図６に示されているようなサブマトリックスを有する制限されたＨマトリックスを使用したコードとの間のパフォーマンスを示すグラフ。
【図８Ａ】図１のシステムにおいて使用されることのできる非グレー８−ＰＳＫ変調方式の概略図。
【図８Ｂ】図１のシステムにおいて使用されることのできるグレー８−ＰＳＫ変調方式の概略図。
【図９】グレーラベル付けを使用したコードと非グレーラベル付けを使用したコードとの間のパフォーマンスを示すグラフ。
【図１０】本発明の１実施形態による非グレーマッピングを使用するＬＤＰＣデコーダの動作のフローチャート。
【図１１】本発明の１実施形態によるグレーマッピングを使用する図３のＬＤＰＣデコーダの動作のフローチャート。
【図１２】本発明の１実施形態による復号プロセスにおけるチェックノードとビットノードとの間の相互作用の概略図。
【図１３】順方向・逆方向アプローチおよび並列アプローチをそれぞれ使用してチェックノードとビットノードとの間の出ていくメッセージを計算する本発明の種々の実施形態によるプロセスのフローチャート。
【図１４Ａ】本発明の種々の実施形態にしたがって発生されたＬＤＰＣコードのシミュレーション結果を示すグラフ。
【図１４Ｂ】本発明の種々の実施形態にしたがって発生されたＬＤＰＣコードのシミュレーション結果を示すグラフ。
【図１４Ｃ】本発明の種々の実施形態にしたがって発生されたＬＤＰＣコードのシミュレーション結果を示すグラフ。
【図１５Ａ】ＬＤＰＣコード化のときにランダム化を達成するように構成されたアクセスをサポートするように編成されたメモリの上方エッジの概略図。
【図１５Ｂ】ＬＤＰＣコード化のときにランダム化を達成するように構成されたアクセスをサポートするように編成されたメモリの下方エッジの概略図。
【図１６】本発明の実施形態にしたがってＬＤＰＣコードを符号化し、復号するプロセスを行うことのできるコンピュータシステムの概略図。
【図１】
2005520468.tif 000098
【図２Ａ】
2005520468.tif 000099
【図２Ｂ】
2005520468.tif 000100
【図３】
2005520468.tif 000101
【図４】
2005520468.tif 000102
【図５】
2005520468.tif 000103
【図６】
2005520468.tif 000104
【図７】
2005520468.tif 000105
【図８Ａ】
2005520468.tif 000106
【図８Ｂ】
2005520468.tif 000107
【図９】
2005520468.tif 000108
【図１０】
2005520468.tif 000109
【図１１】
2005520468.tif 000110
【図１２】
2005520468.tif 000111
【図１３】
2005520468.tif 000112
【図１４Ａ】
2005520468.tif 000113
【図１４Ｂ】
2005520468.tif 000114
【図１４Ｃ】
2005520468.tif 000115
【図１５Ａ】
2005520468.tif 000116
【図１５Ｂ】
2005520468.tif 000117
【図１６】
2005520468.tif 000118
【国際調査報告】
2005520468.tif 000119
2005520468.tif 000120
2005520468.tif 000121
2005520468.tif 000122