(57)【要約】典型的な順方向誤り訂正法は、トレリスコード変調を用いている。畳み込み符号（ｃｏｎｖｏｌｕｔｉｏｎ ｃｏｄｅ）に代えて、変調およびコーディング手順の一部として低密度パリティーチェックコードを用いることにより、低密度パリティーチェックコーディングおよび変調を実行することが出来る。低密度パリティーチェックコードは、エラーフロアを有しておらず、サイクルもなく、情報ビットおよびパリティービットと同じビットエラーレートを有するとともに、可変コードワードサイズを有するパリティーチェックマトリクスおよび生成マトリクスの両方において、時宜を得た構成を得ることができる。【選択図】図３
2004503979.tif 000002
【特許請求の範囲】
【請求項１】
通信チャネルを介した通信用のデータビット信号の複合変調および順方向誤り訂正（ＦＥＣ）コーディング法であって、
ＦＥＣコード化ビット信号を生成するため、ＬＤＰＣコードを用いてデータビット信号のサブセットをＦＥＣコーディングするステップ、
一以上のビット信号を含む少なくとも一のコンステレーションを用いて、前記データビット信号およびＦＥＣコード化ビット信号を変調するステップ、および　前記ＦＥＣコード化ビット信号を用いて、少なくとも一のコンステレーションのコセット（ｃｏｓｅｔ）を指定するステップ、を備えたこと、
を特徴とするもの。
【請求項２】
請求項１の方法において、前記変調は、シングルキャリア又はマルチキャリア変調であること、
を特徴とするもの。
【請求項３】
請求項１の方法において、前記ＬＤＰＣコードは、一以上の情報ビットおよび一以上のパリティービットと同じＢＥＲを有していること、
を特徴とするもの。
【請求項４】
請求項１の方法において、ＬＤＰＣコードパリティーチェックマトリクスは、初期化又は設定段階（ｃｏｎｆｉｇｕｒａｔｉｏｎ ｐｈａｓｅ）中に決定されること、
を特徴とするもの。
【請求項５】
請求項１の方法において、ＬＤＰＣコードジェネレーターマトリクスは、初期化又は設定段階中に決定されること、
を特徴とするもの。
【請求項６】
請求項１の方法において、ＬＤＰＣコードパリティーチェックマトリクスは、待ち時間（ｌａｔｅｎｃｙ）およびデータレートが特定された後に決定されること、
を特徴とするもの。
【請求項７】
請求項１の方法において、ＬＤＰＣコードジェネレーターマトリクスは、待ち時間およびデータレートが特定された後に決定されること、
を特徴とするもの。
【請求項８】
請求項１の方法において、前記ＬＤＰＣコードは、可変のコードワード長を有すること、
を特徴とするもの。
【請求項９】
請求項８の方法において、前記コードワード長は、データレートおよび待ち時間の一つ以上に基づいて変化すること、
を特徴とするもの。
【請求項１０】
請求項１の方法において、前記ＬＤＰＣコードは、サイクルを全く有していないこと、
を特徴とするもの。
【請求項１１】
請求項１の方法において、前記ＬＤＰＣコードのパリティーチェックマトリクスは、少なくとも一の情報ビットと少なくとも一のパリティーノードを有する少なくとも一のパリティービットとを接続する、同じ数の枝を有すること、
を特徴とするもの。
【請求項１２】
請求項１の方法において、パリティーチェックマトリクスは、同じ数の情報ビットおよびパリティービットに接続された少なくとも一のパリティーノード、を含むこと、
を特徴とするもの。
【請求項１３】
ＬＤＰＣコードを用いたデータビットの信号の順方向誤り訂正コーディング法であって、
データレートおよび待ち時間の少なくとも一つを決定するステップ、および
データビット信号をエンコードするＬＤＰＣ生成マトリクスを決定するステップ、を備えたこと、
を特徴とするもの。
【請求項１４】
請求項１３の方法において、前記データレートおよび待ち時間の少なくとも一つは、初期化又は設定段階中に決定されること、
を特徴とするもの。
【請求項１５】
請求項１３の方法において、前記ＬＤＰＣコードジェネレーターマトリクスは、前記データレートおよび前記待ち時間が特定された後に決定されること、
を特徴とするもの。
【請求項１６】
請求項１３の方法において、前記ＬＤＰＣコードは、可変のコードワード長を有すること、
を特徴とするもの。
【請求項１７】
請求項１６の方法において、前記コードワード長は、データレートおよび待ち時間のいずれか一つ以上に基づいて変化すること、
を特徴とするもの。
【請求項１８】
請求項１３の方法において、前記ＬＤＰＣコードは、サイクルを全く有していないこと、
を特徴とするもの。
【請求項１９】
ＬＤＰＣコードを用いたデータビット信号の順方向誤り訂正デコーディング法であって、
データレートおよび待ち時間の少なくとも一つを決定するステップ、および
コード化されたビット信号をデコードするＬＤＰＣパリティーチェックマトリクスを決定するステップ、を備えたこと、
を特徴とするもの。
【請求項２０】
請求項１９の方法において、前記前記データレートおよび待ち時間の少なくとも一つは、初期化又は設定段階中に決定されること、
を特徴とするもの。
【請求項２１】
請求項１９の方法において、ＬＤＰＣパリティーチェックマトリクスは、データレートおよび待ち時間が特定された後に決定されること、
を特徴とするもの。
【請求項２２】
請求項１９の方法において、前記ＬＤＰＣコードは、可変のコードワード長を有すること、
を特徴とするもの。
【請求項２３】
請求項２２の方法において、前記コードワード長は、データレートおよび待ち時間のいずれか一つ以上に基づいて変化すること、
を特徴とするもの。
【請求項２４】
請求項１９の方法において、前記ＬＤＰＣコードは、サイクルを全く有していないこと、
を特徴とするもの。
【請求項２５】
ＬＤＰＣコードを用いてデータビット信号の順方向誤り訂正コーディングを実行する情報を記憶した情報記憶媒体であって、
データレートおよび待ち時間の少なくとも一つを決定する情報、および
データビット信号をエンコードするＬＤＰＣジェネレーターマトリクスを決定する情報、を備えたこと、
を特徴とするもの。
【請求項２６】
請求項２５の媒体において、前記データレートおよび待ち時間の少なくとも一つは、初期化又は設定段階中に決定されること、
を特徴とするもの。
【請求項２７】
請求項２５の媒体において、前記ＬＤＰＣコードジェネレーターマトリクスは、前記データレートおよび前記待ち時間が特定された後に決定されること、
を特徴とするもの。
【請求項２８】
請求項２５の媒体において、前記ＬＤＰＣコードは、可変のコードワード長を有すること、
を特徴とするもの。
【請求項２９】
請求項２８の媒体において、前記コードワード長は、データレートおよび待ち時間のいずれか一つ以上に基づいて変化すること、
を特徴とするもの。
【請求項３０】
請求項２５の媒体において、前記ＬＤＰＣコードは、サイクルを全く有していないこと、
を特徴とするもの。
【請求項３１】
ＬＤＰＣコードを用いてデータビット信号の順方向誤り訂正デコーディングを実行する情報を記憶した情報記憶媒体であって、
データレートおよび待ち時間の少なくとも一つを決定する情報、および
前記データビット信号をデコードするＬＤＰＣパリティーチェックマトリクスを決定する情報、を備えたこと、
を特徴とするもの。
【請求項３２】
請求項３１の媒体において、前記データレートおよび待ち時間の少なくとも一つは、初期化又は設定段階中に決定されること、
を特徴とするもの。
【請求項３３】
請求項３１の媒体において、ＬＤＰＣパリティーチェックマトリクスは、データレートおよび待ち時間が特定された後に決定されること、
を特徴とするもの。
【請求項３４】
請求項３１の媒体において、前記ＬＤＰＣコードは、可変のコードワード長を有すること、
を特徴とするもの。
【請求項３５】
請求項３４の媒体において、前記コードワード長は、データレートおよび待ち時間のいずれか一つ以上に基づいて変化すること、
を特徴とするもの。
【請求項３６】
請求項３１の媒体において、前記ＬＤＰＣコードは、サイクルを全く有していないこと、
を特徴とするもの。
【発明の詳細な説明】
【０００１】
【関連出願に関するデータ】
本出願は、これらの全体が参照のため本明細書に取り込まれる、２０００年６月１６日出願の”ＬＤＰＣコード化変調”と題する米国仮特許出願番号６０／２１２、２３３、および、２０００年１０月１８日出願の”ＡＤＳＬ用の低密度パリティーチェック（ＬＤＰＣ）コード化変調”と題する米国仮特許出願番号６０／２４１、４６８、の利益を主張する。
【０００２】
【発明の分野】
本発明は、通信のコーディングに関する。具体的には、本発明は、マルチキャリア環境用の順方向誤り訂正コーディング法に関する。
【０００３】
【関連技術の説明】
従来の通信システムにおいては、ＤＳＬシステムの性能を向上させるため、トレリスコード化変調（ＴＣＭ）と呼ばれる復号変調およびコーディング手順が頻繁に用いられている。１９７６年にウンガーベオック（Ｕｎｇｅｒｂｅｏｃｋ）がＴＣＭを最初に発表し、かかる技術は、それ以来、いくつかの電気通信規格に用いられている。具体的には、トレリスコードは、情報ビットのストリームのサブセットをエンコードするとともに、信号コンステレーションをサブセット、すなわち、コセット（ｃｏｓｅｔ）に分割し、次に、情報ビットを前記コセットにマップするため、畳み込みコード（ｃｏｎｖｏｌｕｔｉｏｎ ｃｏｄｅ）を用いる。標準的なＡＤＳＬシステムは、参照のため本明細書に取り込まれるＩＴＵ規格Ｇ９９２．１で詳述されているＴＣＭを用いる。
【０００４】
低密度パリティーチェック（ＬＤＰＣ）コードは、従来の通信システムにも用いられている。従来のコードと比較すると、ＬＤＰＣコードによれば、性能が向上しているのが判る。ＬＤＰＣコードは、例えば、その全体が参照のために本明細書に取り込まれる、１９９９年のＩＥＥＥでのＤ．Ｊ．Ｃ．マッケイ氏による”良いエラー　−　ごくわずかなマトリクスに基づき、コードを訂正する”と題する通信理論に関する論文、において説明されている。従来のＬＤＰＣコード化通信システムにおいては、ＬＤＰＣコードは、リードソロモンコード又はハミングコ−ドと同様に、従来から用いられているブロックコードとして使用されている。
【０００５】
【発明の概要】
しかし、ＬＤＰＣコードは、従来のＬＤＰＣコード化システムにおいて、例えばトレリスコード化変調として行われる複合変調およびコーディング手順の一部としては、用いられていなかった。このことから、本発明のシステムおよび方法実施形態は、低密度パリティーチェックコードに基づいた通信用の順方向誤り訂正コーディング法を提供する。具体的には、本発明の一の実施形態は、畳み込みコードに代えて、複合変調およびコーディング手順の一部としてＬＤＰＣコードを用いている。この新たなエンコード方法は、ＬＤＰＣコード化変調と呼ばれる（ＬＤＰＣＣＭ）。
【０００６】
本発明のある実施形態において、ＬＤＰＣＣＭは、従来のＡＤＳＬシステムの性能を向上させるために用いられている。従来から、ＡＤＳＬシステムはＴＣＭを採用してきた。しかしながら、本発明の一実施形態においては、コーディング利得を向上させるため、ＴＣＭに代えてＬＤＰＣＣＭが用いられている。しかし、上述のように、ＡＤＳＬシステムにおいてＬＤＰＣＣＭを用いるためには、ＬＤＰＣＣＭコードがいくつかの条件を満たさなければならない。かかる条件には、エラーフロアがなく、しかも、サイクルのないコード、という条件を含ませることができる。また、かかるコードは、情報ビットおよびパリティービットと同じビットエラーレート（ＢＥＲ）を有するとともに、可変なコードワードサイズを有するパリティーチェックマトリクス、および生成マトリクスの構造を比較的早く決定する能力を有していなければならない。
【０００７】
第一実施形態の、エラーフロアがなく、しかも、サイクルがないという条件を満たす設計は、例えば、その全体が参照のために本明細書に取り込まれる、２０００年のＩＥＥＥでのＤ．Ｊ．Ｃ．マッケイ氏による”ＬＤＰＣ”と題した通信理論に関する論文、において説明されている。そこで開示されているＬＤＰＣコードは、サイクルのない９９７９のコードワードサイズを有しているので、エラーフロアもない。しかし、例えば、その構造を、他のコードワードに適用することができず、例えば、コードワードを短くも長くもできない。
【０００８】
従って、本発明の一実施例によれば、順方向誤り訂正（ＦＥＣ）コード化ビット信号は、ＬＤＰＣコードを用いてデータビット信号のサブセットをＦＥＣコーディングすることによって生成される。
【０００９】
本発明の他の特徴は、マルチキャリア環境においてＬＤＰＣコードを使用すること、に関する。
【００１０】
また、本発明の他の特徴は、ＤＳＬシステムの性能を向上させること、に関する。
【００１１】
また、本発明の他の特徴は、低密度パリティーチェックコードに基づき、ＡＤＳＬシステムを介した通信をコーディングする方法を提供すること、に関する。
【００１２】
また、本発明の他の特徴は、畳み込みコードの代わりに、ＡＤＳＬ環境における複合変調およびコーディング手順の一部として用いられる低密度パリティーチェックコードを提供すること、に関する。
【００１３】
また、本発明他の特徴は、初期又は設定段階中にＬＤＰＣパリティーチェックマトリクスを構築すること、に関する。
【００１４】
また、本発明の他の特徴は、初期又は設定段階中にＬＤＰＣジェネレーターマトリクスを構築すること、に関する。
【００１５】
また、本発明の他の特徴は、通信システムの待ち時間およびデータレート条件が決定された後にＬＤＰＣパリティーチェックマトリクスを構築すること、に関する。
【００１６】
また、本発明の他の特徴は、通信システムの待ち時間およびデータレート条件が決定された後にＬＤＰＣジェネレーターマトリクスを構築すること、に関する。
【００１７】
本発明の上記およびその他の特徴、ならびに効果は、以下で述べる実施形態の詳細な説明において説明され、または、それによって明らかである。
【００１８】
【詳細な説明】
エラーフロアがなく、サイクルもないＬＤＰＣコードの第一の条件については、ビデオ情報等のビットエラーに弱い情報が搬送されることが多いので、ＡＤＳＬシステムは、非常に低いビットエラーレート（ＢＥＲ）で動作しなければならない。かかる理由から、ＡＤＳＬシステムは、ＢＥＲが１Ｅ−７未満で動作するよう指定される。したがって、ＬＤＰＣＣＭにはエラーフロアがあってはならない。順方向誤り訂正（ＦＥＣ）コードのエラーフロアは、非常に高い信号比において非ゼロＢＥＲ（ｎｏｎ−ｚｅｒｏ ＢＥＲ）であると定義される。多くのコードは、エラーフロアを有しない。例えば、チャネルの信号比（ＳＮＲ）が高くなる（無限に近付く）と、ＢＥＲは、下がり続ける（ゼロに近付く）。ターボコード（ｔｕｒｂｏ ｃｏｄｅ）は、エラーフロアが必ず存在するコーディング法の、例である。このことは、非常に高い信号比においても、ターボコードのＢＥＲは変化しないことを意味する。したがって、本発明の特徴によると、ＬＤＰＣコードは、コード内にサイクルが確実に存在しないようにすることで、エラーフロアなしに構築される。
【００１９】
情報ビットおよびパリティービットと同じビットエラレート（ＢＥＲ）を有するコードの第二の条件について、従来のＬＤＰＣコード化システムでは、ＬＤＰＣコードは、簡単なブロックコードとして用いられていた。これらのシステムにおいて、パリティービットは、コードワードの一部として、情報ビットとともにチャネルを介して送信される。受信側では、パリティービットは、情報ビットのエラー訂正のデコーディング用に使用される。当該デコーディングプロセス完了後、パリティービットは廃棄される。このことから、従来のＬＤＰＣコード化システムにおいてはコード化システムは、しばしば、パリティービットおよび情報ビットに関し、異なるＢＥＲを有するコードを用いている。
【００２０】
本発明のある実施形態においては、エンコードされたビット、すなわち、情報およびパリティービット、はコンステレーションコセット（ｃｏｎｓｔｅｌｌａｔｉｏｎ ｃｏｓｅｔ）を指定するために用いられる。したがって、パリティーおよび情報ビットは、どのコセットをデコーディングに用いるかを決定するのに使用されるので、エンコードされた全てのビットが同じＢＥＲを有していることが重要である。具体的には、ＬＤＰＣコードは、少なくとも確実に、ＬＤＰＣパリティーチェックマトリクスが情報ビットおよびパリティービットをパリティーノードに接続するのと同じ数の枝を有するとともに、パリティーノードが同じ数の情報ビットおよびパリティービットに接続させることにより、情報ビットおよびパリティービット上に、同じＢＥＲで構築される。
【００２１】
ＡＤＳＬシステムは、レートが可変で、しかも、待ち時間も可変なシステムである。このことは、どのようなデータレートにおいてもＡＤＳＬトランシーバーを構成することができること、を意味している。例えば、ＩＴＵ規格Ｇ９９２．１は、ＡＤＳＬトランシーバーが、３２Ｋｂｐｓきざみで、６４Ｋｂｐｓから６Ｍｂｐｓまでのレートで動作可能であること、を要求する。また、ＡＤＳＬシステムは、待ち時間が可変なシステムでもある。このことは、ＡＤＳＬトランシーバーは、多数の異なる待ち時間、すなわち、遅延、レベルで動作可能でなければならないこと、を意味する。例えば、ＩＴＵ規格Ｇ９９２．１は、ＡＤＳＬトランシーバーが、１．５ミリセカンド（１．５ ｍｓｅｃｓ）から２０ミリセカンドのレベルで動作可能であること、を要求する。
【００２２】
例えば、システムは、特定のデータレートについて異なる様々な待ち時間をサポートしなければならないので、ＡＤＳＬの可変レートおよび可変の待ち時間に関する要件は、使用可能なＦＥＣコーディングの種類に関し、異なる設計上の制約を課すことになる。例えば、データレートが、例えば６４ｋｂｐｓと低く、要求される待ち時間が、例えば１．５ミリセカンドと低い場合、待ち時間の短いＦＥＣコードを用いなければならない。
【００２３】
待ち時間が短いＦＥＣブロックコードは、短いコードワード長を用いることによって設計される。一般に、コードワードが長ければ長いほど、ＦＥＣコードのコードゲインが大きくなる。しかし、コードワードが長くなると、待ち時間も長くなってしまう。うまく設計されたＡＤＳＬ用のＦＥＣコードは、待ち時間ならびにデータレート要件に基づいてコードワード長を調整可能でなければならないことになる。これにより、ＦＥＣコードは、待ち時間ならびにデータレート要件に基づき、最大限のコードゲインを提供することができる。
【００２４】
したがって、本発明の実施形態の例において、ＬＤＰＣコードは、可変のコードワード長を有するよう構成してもよい。かかる可変コードワード長のＬＤＰＣコード、すなわち、パリティーチェックマトリクスは、データレートおよび待ち時間が特定された後に決定される。これにより、例えば、異なるコードワード長を有する多数のＬＤＰＣコードを記憶することなく、一連で多数のデータレートおよび待ち時間のレベル用に一のトランシーバーを構成することが可能となる。このように、一旦、データレートおよび待ち時間の要件が特定されると、ＬＤＰＣコード構成は、データレートおよび待ち時間の要件を満たすとともに、コードゲインを最大にするコードワード長を決定する。例えば、ＡＤＳＬトランシーバーは、レートが可変で、しかも、待ち時間も可変なシステムである。このことは、例えば、サービスのレベル（サービスプロバイダーが提供する）、アプリケーション、電話線の質等、に基づき、異なるデータレートおよび待ち時間を用いて、これらを動作させるよう構成することができること、を意味している。例えば、消費者がサービスプロバイダーからＡＤＳＬサービスを購入した場合、消費者は、データレート能力で特定可能なサービスのレベルを購入することになる。例えば、消費者は、電話局から消費者の家まで３８４から１５３６ｋｂｐｓのデータレートが保証されたＡＤＳＬサービスを購入することができる。電話線の状況および電話局からの距離により、消費者は、約３８４から１５３６ｋｂｐｓの範囲のデータレートを得る。また、消費者には、サービスのレベルに基づき、ある程度の待ち時間、例えば、５ミリセカンド、が保証される。したがって、ＡＤＳＬトランシーバーがインストールされた後に、上述の要素に基づいてデータレートが決定される。このデータレートおよびサービスの待ち時間の要件に基づき、コードゲイン、すなわち、このデータレートおよび待ち時間用のコードワードサイズを最大にするＬＤＰＣコードが構築される。具体的には、ＡＤＳＬトランシーバーは、最初に、例えば、初期段階又は訓練段階（ｔｒａｉｎｉｎｇ ｐｈａｓｅ）の間、電話線のデータレート能力を測定し、次に、ＡＤＳＬトランシーバーは、ＡＤＳＬサービスによって許容されたデータレートに基づいて動作データレートを決定する。動作データレートを決定した後、ＡＤＳＬトランシーバーは、サービスの待ち時間要件に基づき、ＬＤＰＣコードを構築する。
【００２５】
これに代えて、ＡＤＳＬ接続上で動作すると予想されるアプリケーション、例えば、ビデオ、に基づいて、待ち時間および／又はデータレート要件を設定することができ、さらに、この場合、アプリケーションに対する要件がデータレートおよび待ち時間を決定するのに寄与した後に、ＬＤＰＣコードが構築される。
【００２６】
パリティーチェックマトリクスを適切なタイミングで構築するため、例えば、トランシーバーの初期段階又は設定段階中に構築を完了させるためだけに決定を行うべきである。例えば、ＡＤＳＬトランシーバーにおいては、初期化中のチャネル、すなわち、電話線の信号対ノイズ比（ＳＮ比）を測定し、当該ＳＮ比に基づいて動作データレートを生成する。また、上述のように、ＡＤＳＬサービスレベルおよびアプリケーションを、データレートを決定するための要素としてもよい。待ち時間は、初期化段階の間又はトランシーバーの設定段階、すなわち、ＡＤＳＬサービスが最初にインストールされた際、のいずれかの間にも決定される。データレートおよび待ち時間が特定された後に、ＬＤＰＣコードが構成される。
【００２７】
ジェネレーターマトリクスの構築に関しては、ＬＤＰＣエンコーダーでＬＤＰＣコードワードを生成するため、ＬＤＰＣコードのジェネレーターマトリクスが用いられる。かかるジェネレーターマトリクスは、通常、パリティーチェックマトリクスに対してガウス消去法（Ｇａｕｓｓｉａｎ ｅｌｉｍｉｎａｔｉｏｎ ）を実行することによるパリティーチェックによって得られる。上述のように、ＡＤＳＬシステムにおける可変のコードワードサイズを用いたパリティーチェックマトリクスの決定に関しては、コードワードサイズを可変とするため、適切なタイミングでＬＤＰＣコードを生成しなければならない。したがって、生成マトリクスも、その場で（ｏｎ−ｔｈｅ−ｆｌｙ）、又はデータレートおよび待ち時間の要件が特定された後等の、適時に生成される。
【００２８】
コードのパリティーチェックマトリクスは、いずれのコードワードと掛けた場合に（ｍｕｌｔｉｐｌｅｘｅｄ ｂｙ）、全てがゼロベクトル（ａｌｌ−ｚｅｒｏ　ｖｅｃｔｏｒ）となるマトリクスである。これは、数学的に以下のように表すことができる：
Ｈを、コードのパリティーチェックマトリクスとし、ｃを、コードＣ中のいずれかのコードワードとすると：
【数１】
2004503979.tif 000003
コードのジェネレーターマトリクスは、入力ベクトルと掛けた場合に、コードワードとなるマトリクスである。これは、数学的に以下のように表すことができる：
Ｇを、コードのパリティチェックマトリクスとし、ａを、いずれかのデータベクトルとすると：
【数２】
2004503979.tif 000004
ここで、Ｃは、全てのコードワードの組み合わせである。例えば、パリティーチェックマトリクスを示すと：
Ｈ＝
【表１】
2004503979.tif 000005
【００２９】
また、生成マトリクスは：
Ｇ＝
【表２】
2004503979.tif 000006
【００３０】
次に、移入力ベクトルにａ＝｛０、１、０，０｝とすると、結果としてのコードワードは：
【数３】
2004503979.tif 000007
これにより、必要に応じ、以下が導き出される；
【数４】
2004503979.tif 000008
この例においては、パリティーチェックマトリクスおよびジェネレーターマトリクスの双方が、体系的であること、すなわち、マトリクスのどこかにアイデンティティーマトリクスが存在すること、に注意すべきである：
【数５】
2004503979.tif 000009
この場合、下式に注意すべきである。
【００３１】
【数６】
2004503979.tif 000010
ＬＤＰＣコード用のパリティーチェックは、パリティーチェックマトリクスにおいて、ランダムに１つづつ列状に配する（ａｓｓｉｇｎｉｎｇ ｏｎｅｓ ｔｏ ｔｈｅ ｒｏｗｓ）ことによって（上の例ではＨ）、生成される。列の数は、情報ビット数Ｋ、プラス、パリティービット数（Ｐ）、に等しい。また、行の数は、パリティービット数に等しい。
【００３２】
図１は、円が情報ビット１００を表わし、正方形がパリティービット１１０を示すパリティーチェックマトリクスの例、を示している。情報ビットとパリティービットを接続する複数の線１１５は、パリティーチェックマトリクス内の１をを表わすとともに、コードワードによって満たされるべきパリティーチェックの式を表わしている。正方形１２０の下の列を見ると、下列に沿って正方形と接続する全てのビットの合計（モジュロ２）は、コードワードについてゼロと等しくなければならない。
【００３３】
図２は、ランダムパリティーチェックコード１３０の例を示している。この例においては、三つの情報ビット１００および三つのパリティーチェックビット１１０がある。また、上列に沿った各ビットから下列に沿ってチェックノード１２０に至る接続１１５が二つある。チェックノード１２０が三つしかないので、各チェックノードは、情報ビットおよびパリティービットに対し、四つの接続を有している。また、パリティーチェックコード１３０用のパリティーチェックマトリクスＨ　１４０も示されている。パリティーチェックマトリクス１４０の各行は、１を二つ有し（ｔｗｏ ｏｎｅｓ）、各列は１を四つ有していること（ｆｏｕｒ ｏｎｅｓ）、に注意すべきである。これは、パリティーチェックコード１３０の図解例と同じである。
【００３４】
図１および図２の両方は、各列に同じ数が存在することを表す通常のパリティーチェックマトリクス、ならびに、各行に同じ数が存在するパリティーチェックマトリクス、を示している。また、図２は、各パリティーチェックノード１２０が同数の情報ビットおよびパリティービットに接続している場合を示している。
【００３５】
ここで説明するジェネレーターマトリクスを見つけるための最後のポイントは、ＬＤＰＣコードの構築を考慮した場合に重要である。具体的には、一般的なパリティーチェックマトリクスによって説明されるコード用のジェネレーターマトリクスを得るため、パリティーチェックマトリクスにガウス消去法を実行することにより、体系的なパリティーチェックマトリクスを形成し、その後、マトリクスＨを置き換えることによってジェネレーターマトリクスを得る。しかし、ランダムに構成されたＨマトリクスは、”フルランク”でなくてもよく、したがって、パリティーチェックマトリクスから長さＮのコードを形成できなくてもよい。実際には、コードワード長は、Ｎより短いことが多く、通常、三ビット以内である。
【００３６】
図３は、本発明に係るＬＤＰＣコーダーの例を示している。ＡＤＳＬトランシーバーの構造は広く知られており、ＩＴＵ規格Ｇ９９２．１等で示されているので、ＡＤＳＬ通信に必要な残りのハードウエアおよびソフトウエアについては、ここでは説明を行わない。ＬＤＰＣコーダー３００は、ＬＤＰＣエンコーダーモジュール３１０、コセットマップ決定モジュール３２０、ＱＡＭエンコーダー３３０、および、変調器３４０を備えている。入力パスＢＭは、入力された非コード化情報ビットを表している。入力情報ストリームＢ’Ｍ　は、入力された被コード化情報ビットを示している。ストリームＣＮ内の情報は、ＬＤＰＣコード化ビットを示している。また、ＬＤＰＣコーダー３００と関連するのは、ジェネレーターマトリクスモジュール４００である。
【００３７】
コードレートは、以下のように表すことが出来る：
【数７】
2004503979.tif 000011
ＬＤＰＣＣＭ受信機は、ＬＤＰＣパリティーチェックマトリクスを用いて実行されるＬＤＰＣデコーディングと一体となって図３と逆の機能を備えている。かかるパリティーチェックマトリクスは、当該受信機内にあるパリティーチェック構成モジュールを用いて構築される。
【００３８】
上述のように、ＬＤＰＣパリティーマトリクスは、初期化又は設定段階中にデータレートおよび待ち時間の要件が特定された後に構築される。ＬＤＰＣパリティーチェックマトリクスの構築は、受信機で行われ、コードレートおよび各情報および各パリティービットから各パリティーノードへの枝の数を選択するレートおよびブランチ決定モジュール（図示せず）によって開始される。これらの枝数は、（ｔ）によって示される。これらの枝は、疑似ー乱数シフトレジスター（ＰＲＢＳ）等の乱数モジュール（図示せず）内で決定された乱数に基づき、サイクルのｔの数に基づいて各ビットから情報およびパリティービットを介してパリティーノードへと、ランダムに割り当てられる。これにより、各情報およびパリティービットからｔ個の枝が存在することが確実となる。繰り返しになるが（ａｓ ｉｎ ｅａｒｌｉｅｒ ｉｔｅｒａｔｉｏｎ）、同じビットから同じパリティーノードに枝が割り当てられている場合、新しい乱数が選択されるとともに、新たな枝が選ばれる。
【００３９】
全てのノードを完全に占める（ｆｕｌｌｙ ｐｏｐｕｌａｔｅｄ）には二つの選択肢がある。具体的には、システムは、全てのパリティーノードから同じ枝数、又は、その代わりに、全てのパリティーノードからパリティービットおよび情報ビットの両方への同じ数の接続、を決定することが可能である。全てのパリティーノードにおける同じ数の枝用に、各パリティーノードにカウンター（図示せず）が割り当てられると共に、そのノードに枝が接続されるたびにカウントが増やされる。カウンターが、一旦２ｔに達すると、当該ノードに対してそれ以上接続することができなくなる。ランダムに生成された枝が”フル”ノードを選択した場合、乱数は廃棄され、新しい枝が選ばれる。これを行う効率的な方法としては、１−（Ｎ−ｋ−ｆ）の範囲、ここでｆは、”フル”ノードの数、で乱数を選ぶことである。しかし、枝数が最後にまで達していると、枝の重複（ｄｕｐｌｉｃａｔｅ）を回避することが困難となり、プロセスを再スタートするか、ｔ個の枝よりも少ない数ビットを選択するか、のいずれかを選択することができる。
【００４０】
パリティーノードからパリティービットおよび情報ビットの両方への接続と同じ数の接続のため、 各パリティーノードに対し、パリティービットと情報ビットの枝数を個別にカウントするため、二つのカウンターが割り当てられる。次に、どのノードも自身に割り当てられた情報ビット又はパリティービットに対する接続の数を超えないように、枝数が選ばれる。同じ数の枝が全てのパリティーノードに存在するという、上述の実施形態と同じ方法によってこれを達成することが可能である。しかし、この例におけるシナリオでは、”フル”ノードを有する代わりに、”フル情報”ノードおよび”フルパリティー”ノードが存在する。
【００４１】
次に、パリティーチェックマトリクスを全部照会することにより、どのような長さにでも形成可能なサイクルを削除することができ、また、他の枝を用いてサイクルを形成する枝を再度割り当てるようにしても、サイクルが除去される。枝の再割り当ては、上述のルーピングステップ（ｌｏｏｐｉｎｇ ｓｔｅｐ）と同じ方法で行われるが、演算が複雑となるおそれがあるので、単にサイクルから枝を取り除くとともに、システムの性能に支障をきたすことがなければ、ノードの一部と前記のビットとが異なる接続数を有するようにしてもよい。
【００４２】
送信機においては、初期化又は設定段階中にデータレートおよび待ち時間が特定された後、ジェネレーターマトリクスモジュール４００によってジェネレーターマトリクスが決定される。具体的には、ガウス消去法を用いて、体系的なパリティーチェックマトリクスが生成される。かかる体系的なマトリクスからは、上述のように、ジェネレーターマトリクスが生成される。かかるパリティーチェックマトリクスが、所定の長さよりコードワードが短いことを表す、”フルランク”でない場合、二つの選択肢がある。第一の選択肢としては、上述のルーピングを再度実行する。また、それに代えて、所望のコードレート用に必要とされるよりも多くの情報ビットを選択し、残りのステップを順に行ってもよい。しかし、これによりパリティーノード用の枝は、異なる数となってしまう。
【００４３】
マトリクスがフルランクでない場合、必要に応じ、一以上の行を削除することが可能である。こうしてできたコードが余分な情報ビットを有している場合、これらが送信に必要とされることはないが、エンコーディングおよびデコーディングの目的に関し、かかる余剰ビットをゼロと見なすことができる。
【００４４】
なお、ＬＤＰＣコードを生成する第二の方法は、全体的なコード構造の特徴の多くを犠牲にすることで、上述の方法よりも高速となる。本方法によるＬＤＰＣの生成方法との主な相違点は、マトリクスのパリティービットセクションを形成する列が、下三角構造（ｌｏｗｅｒ ｔｒｉａｎｇｕｌａｒ ｉｎ ｓｔｒｕｃｔｕｒｅ）となるようパリティーチェックマトリクスに制限が課されていることである。下三角部分がアィデンティテイーマトリクスである場合には、比較的容易にジェネレーターマトリクスを決定することができることが知られている。結局、パリティービットセクションは、本質的に下三角構造であるということが判る。
【００４５】
図４は、かかる構造のパリティーチェックマトリクスの構成を示している。下三角は、正方形のマトリクスに適用されており、かかる正方形のマトリクスは、いずかの又は全てのゼロでない項目（ｎｏｎ−ｚｅｒｏ ｔｅｒｍ）が、１、１からＮ、Ｎ、すなわち、それを超える全てがゼロとなるような主なダイアゴナルと同じか、又はそれ未満である。この例の場合、パリティービット用のパリティーチェックマトリクスの一部であって、最後のＮ−Ｋ列が、サイズＮ−Ｋ×Ｎ−Ｋの正方形のマトリクスを形成する。これが、下三角に必要とされる部分である。情報ビット用のセクションについては、制約がない。したがって、アィデンティティーマトリクスと呼ばれる（通常の場合に）セクションは、サイズＮ−Ｋ×Ｎ−Ｋのアィデンティティーマトリクスを形成するパリティービットセクションである。したがって、かかるアィデンティティーマトリクス（又はいずれかのダイアゴナルマトリクス）は、下三角マトリクスのサブセットである。
【００４６】
以下に説明する乱数発生と組み合わせた場合の本構造の利点は、パリティーチェックマトリクスおよび生成マトリクスのいずれをも記憶する必要がないことである。エンコーディング又はデコーディングのいずれかの間の適切な時に、いずれかのポイントにおいて必要な枝は、必要に応じてＰＲＢＳから決定することができる。これにより、コードワードサイズが大きくなるにつれ、マトリクスのサイズが大きくなるという利点お生じさせることが判る。また、ガウス消去法を用いた通常のＬＤＰＣコード生成法は、非過疎（ｎｏｎ−ｓｐａｒｓｅ）でありエンコーダー用に大量の記憶容量を必要とするジェネレーターマトリクスを生じさせる。
【００４７】
かかる方法をエンコーダーの利益になるよう用いる方法の一つは、全てのパリティーノードをゼロと等しく設定することである。情報ビットが到着すると、例えば、ＰＲＢＳを用いてパリティーノードの接続が決定され、パリティーノードを用いてかかる情報ビットが排他的論理和される（ＸＯＲｅｄ）。次に、最初のパリティービットが最初のパリティーノードと同じ値に設定され、この値は、最初のパリティービットに接続された他のパリティーノードを用いて排他的論理和される。これらの接続は、ＰＲＢＳ等によって、再び決定される。
【００４８】
図５は、本発明にかかるＬＤＰＣコードを決定する方法の第一の実施形態を示している。具体的には、制御は、ステップＳ１００で開始され、ステップＳ１１０へと続く。ステップＳ１１０においては、コードレートが決定される。次に、ステップＳ１２０において、枝数（ｔ）が決定される。その後、ステップＳ１３０へと続く。
【００４９】
ステップＳ１３０においては、情報又はパリティービットが選択される。次に、ステップＳ１４０において、乱数が決定される。次に、ステップＳ１５０では、選択された情報又はパリティービットから枝が選択される。その後、ステップＳ１６０へと続く。
【００５０】
ステップＳ１６０においては、決定された枝が重複しているか否かの判断がなされる。枝が重複している場合、ステップＳ１４０にジャンプする。そうでない場合は、ステップＳ１７０へと続く。
【００５１】
ステップＳ１７０においては、パリティーノードに枝が割り当てられる。次に、ステップＳ１８０において、選ばれたビット用にｔが指数化（ｉｎｄｅｘｅｄ）される。次に、ステップＳ１９０では、割り当てられた枝数が全ての情報およびパリティービット用のｔと等しいどうかの判断がなされる。情報およびパリティービットがｔ個の枝を有していない場合は、ステップＳ２００へと続く。等しい枝を有する場合は、ステップＳ２１０へジャンプする。
【００５２】
ステップＳ２００においては、次の情報又はパリティービットが選ばれる。次に、制御はステップＳ１４０へと戻る。
【００５３】
ステップＳ２１０においては、サイクルが削除される。次に、ステップＳ２２０において、ジェネレーターマトリクスが決定される。次に、Ｓ２３０において、パリティーチェックマトリクスがフルランクであるかどうかの判断がなされる。パリティーチェックマトリクスがフルランクでない場合、ステップＳ２４０へと続く。フルランクの場合は、制御が終了するステップＳ２５０へとジャンプする。
【００５４】
ステップＳ２４０においては、必要とされる以上の情報ビットが選ばれ、ステップＳ１２０にジャンプする。
【００５５】
図６は、本発明にかかるＬＤＰＣコードを決定する方法の第二の実施形態を示している。具体的には、制御は、ステップＳ３００で開始され、ステップＳ３１０へと続く。ステップＳ３１０においては、コードレートが決定される。次に、ステップＳ３２０において、枝数（ｔ）が決定される。その後、ステップＳ３３０において、情報および／またはパリティービットが選択される。次に、ステップＳ３４０へと続く。
【００５６】
ステップＳ３４０においては、乱数が決定される。次に、ステップＳ３５０では、選択された情報又はパリティービットとパリティーノード間の枝が決定される。次に、ステップＳ３６０においては、前記の枝が重複しているか否かの判断がなされる。枝が重複している場合、ステップＳ３４０に戻る。そうでない場合は、ステップＳ３７０へと続く。ステップＳ３７０においては、パリティーノードがフルであるか否かの判断がなされる。パリティーノードがフルの場合、ステップＳ３４０に戻る。フルでない場合は、ステップＳ３８０へと続く。
【００５７】
ステップＳ３８０においては、枝がパリティーノードに割り当てられる。次に、ステップＳ３９０では、選ばれた情報又はパリティービット用にｔが指数化（ｉｎｄｅｘｅｄ）される。その後、ステップＳ４００において、全ての情報およびパリテオービットにｔ個の枝が割り当てられたか否かの判断がなされる。全ての情報およびパリティービットにｔ個の枝が割り当てられていない場合は、ステップＳ４００へと続く。割り当てられている場合は、制御が終了するステップＳ４２０へジャンプする。
【００５８】
ステップＳ４００において、次の情報又はパリティービットが選択される。次に、ステップＳ３３０に戻る。
【００５９】
図７は、ステップＳ１４０およびＳ３４０で示した乱数決定方法の例を示している。具体的には、ステップＳ５００で制御が開始され、ステップＳ５１０へと続く。ステップＳ５１０においては、例えば、長い非反復シーケンス（ｌｏｎｇ ｎｏｎ−ｒｅｐｅａｔｉｎｇ ｓｅｑｕｅｎｃｅ）を有する疑似乱数シフトレジスタ（ＰＲＢＳ）から乱数が選択される。次に、ステップＳ５２０において、Ｎが選択される。その後、ステップＳ５３０で、ＰＲＢＳがシフトされる。次に、ステップＳ５４０へと続く。
【００６０】
ステップＳ５４０においては、レジスターモジュロ演算（ｒｅｇｉｓｔｅｒｓ ｍｏｄｕｌｏ）（Ｎ−Ｋ）の値が取得される。次に、ステップＳ５５０では、乱数が出力される。その後、制御シ−ケンスが終了するステップＳ５６０へと続く。
【００６１】
図３に示すように、ＬＤＰＣコード化システムにおいて、コード決定システムおよび関連する部品は、ＶＤＳＬモデム等のＤＳＬモデム上、又は、通信装置を有する別のプログラム済みの汎用コンピュータによって実行することができる。 しかし、かかるＬＤＰＣコード決定システムは、特殊な用途のコンピュータ、プログラム済みのマイクロプロセッサー、又は、マイクロコントローラー兼周辺集積回路素子、ＡＳＩＣ又は他の集積回路、デジタル信号プロセッサー、個別素子（ｄｉｓｃｒｅｔｅ ｅｌｅｍｅｎｔ），ＰＬＤ、ＰＬＡ、ＦＰＧＡ、ＰＡＬ等及び関連する通信機器等のプログラマブルロジック装置等のプログラム組み込み済みハードウエア（ｈａｒｄｗｉｒｅｄ）又は電子ロジック回路によっても実行可能である。一般に、図５から図７に示すフローチャートを連続して実行可能な有限状態機械（ｆｉｎｉｔｅ ｓｔａｔｅ ｍａｃｈｉｎｅ）を実現することができる装置であれば、どのような装置でも本発明にかかるＬＤＰＣコード決定システムに使用することが出来る。なお、ここで用いられているモジュールという用語は、どのようなハードウエア又はソフトウエア、あるいは、その組み合わせ、を含む概念である。
【００６２】
ＬＤＰＣＣＭ法は、どのような無線、有線又は、従来の通信システムを介して改良されたコーディングを提供するので有れば、一般に、どのような通信システムにも用いることが出来る。ＬＤＰＣＣＭ法は、マルチキャリア又はシングルキャリア変調を用いるどのような通信システムにも使用可能である。また、このＬＤＰＣＣＭ法は、データレートおよび待ち時間の条件が可変で、データレートおよび待ち時間の条件が初期化又は設定段階中に決定される、いずれの通信システムにも用いることができる。
【００６３】
また、開示された方法は、様々なコンピュータ、ワークステーション、又はモデムハードウエア、および／又は、ソフトウエアプラットフォーム上で使用可能なポータブルソースコードを提供するオブジェクト又はオブジェクト指向のソフトウエア開発環境により直ちに実現することができる。それに代えて、開示されたモデムは、その一部又は全部を、標準的なロジック回路又はＶＬＳＩデザインを用いたプログラム組み込み済みハードウエア（ｈａｒｄｗｉｒｅｄ）により実現しても良い。本発明にかかるシステムを実現するため、当該システムの速度、および／又は、効率についての要求事項、特定の機能、特定のソフトウエア、および／又は、ハードウエアシステム、又はマイクロプロセッサー、すなわち、用いられるマイクロコンピュータシステムによっては、他のソフトウエア又はハードウエアを用いても良い。しかし、ここで示されているＬＤＰＣコード決定システムは、ここで記載された機能の説明およびコンピュータならびに通信技術の一般的な知識を用いることにより、適用可能な技術の当業者によって、既知の、以後開発されるシステム又は構成、装置、および／又は、ソフトウエアを用いたハードウエア、および／又は、ソフトウエアを用いて、直ちに実現することが出来る。
【００６４】
さらに、開示された方法は、プログラムされた汎用コンピュータ、特殊な用途のコンピュータ、マイクロプロセッサおよび関連する通信機器、ＤＳＬモデム等のモデム、上で実行されるソフトウエアとして直ちに実現することが出来る。このような場合、本発明の方法およびシステムは、ＤＳＬモデム等のモデムに組み込まれたプログラムとして実現することが出来る。かかるＬＤＰＣコード決定システムは、当該システムおよび当該方法を、ＡＤＳＬモデム、ＶＤＳＬモデム、ネットワークインターフェースカード等のモデムのハードウエアおよびソフトウエアシステム、等のソフトウエア、および／又は、ハードウエアシステム内に物理的に組み込む、によっても実現可能である。
【００６５】
したがって、本発明によれば、ＬＤＰＣコード決定方法およびシステムが提供されることは、明かである。本発明は、いくつかの実施形態に関して説明がなされているが、適用可能な技術の当業者にとっては、多くの代替手段、変更例があることは、明らかに理解できる。したがって、出願人は、本発明の精神およびその範囲中にある、かかる代替手段、変更例、均等物を含むことを意図するものである。
【図面の簡単な説明】
本発明の実施形態は、以下の図面を参照しつつ説明した。
【図１】
図１は、ＬＤＰＣコード化変調システムの例を示す機能ブロックである。
【図２】
図２は、パリティーチェックマトリクスの図解例である。
【図３】
図３は、乱数パリティーチェックマトリクスの例を示す。
【図４】
図４は、パリティーチェックマトリクスの構成の例を示している。
【図５】
図５は、ＬＤＰＣコードを決定する実施形態の概要フローチャートである。
【図６】
図６は、ＬＤＰＣコードを決定する第二の実施形態を示すフローチャートである。
【図７】
図７は、乱数を決定する方法の一例を示すフローチャートである。
【図１】
2004503979.tif 000012
【図２】
2004503979.tif 000013
【図３】
2004503979.tif 000014
【図４】
2004503979.tif 000015
【図５】
2004503979.tif 000016
【図６】
2004503979.tif 000017
【図７】
2004503979.tif 000018
【国際公開パンフレット】
2004503979.tif 000019
2004503979.tif 000020
2004503979.tif 000021
2004503979.tif 000022
2004503979.tif 000023
2004503979.tif 000024
2004503979.tif 000025
2004503979.tif 000026
2004503979.tif 000027
2004503979.tif 000028
2004503979.tif 000029
2004503979.tif 000030
2004503979.tif 000031
2004503979.tif 000032
2004503979.tif 000033
2004503979.tif 000034
2004503979.tif 000035
2004503979.tif 000036
2004503979.tif 000037
2004503979.tif 000038
2004503979.tif 000039
2004503979.tif 000040
2004503979.tif 000041
2004503979.tif 000042
2004503979.tif 000043
2004503979.tif 000044
2004503979.tif 000045
2004503979.tif 000046
2004503979.tif 000047
【国際調査報告】
2004503979.tif 000048
2004503979.tif 000049