(57)【要約】  データ符号化の方法が開示されている。通信デバイスは、コードワード（ｃ）に符号化されるべき情報ビットのセットを受信し、それは、情報ビットのセットおよびパリティビットのセットを含む。第１のビット値は、パリティビットのセットにおける第１のパリティビットに割り当てられる。残りのパリティビットはその後、第１のパリティビットに割り当てられた第１のビット値に少なくとも部分的に基づいて符号化される。デバイスは、低密度パリティ検査（ＬＤＰＣ）符号のためのパリティ検査行列（Ｈ）および情報ビットのセットを使用して、残りのパリティビットを符号化することができる。デバイスはまた、パリティ検査行列Ｈの線形独立行に基づいて新たなパリティ検査行列（Ｈ０）を生成し得、式：Ｈ０ｃ＝０に基づいて残りのパリティビットの各々の値を反復して求めることができる。デバイスはその後、符号化されたコードワードｃが、ＬＤＰＣ符号を考慮した場合に有効なコードワードであるかどうかを決定することができ、ｃが有効なコードワードでない場合、コードワードの１つまたは複数のビット値を変更することができる。
2016521064.tif 000002
【特許請求の範囲】
【請求項１】
データ符号化の方法であって、
コードワード（ｃ）に符号化されるべき情報ビットのセットを受信することと、ここにおいて、前記コードワードは、前記情報ビットのセットおよびパリティビットのセットを含む、
前記パリティビットのセットにおける第１のパリティビットに第１のビット値を割り当てることと、
前記第１のパリティビットに割り当てられた前記第１のビット値に少なくとも部分的に基づいて、前記パリティビットのセットにおける残りのパリティビットを符号化することと、
を備える、データ符号化の方法。
【請求項２】
前記残りのパリティビットは、低密度パリティ検査（ＬＤＰＣ）符号のためのパリティ検査行列（Ｈ）および前記情報ビットのセットを使用して符号化される、請求項１に記載の方法。
【請求項３】
前記パリティ検査行列の線形独立行を使用して、新たなパリティ検査行列（Ｈ０）を生成すること、
をさらに備える、請求項２に記載の方法。
【請求項４】
前記残りのパリティビットを符号化することは、
式：Ｈ０ｃ＝０を使用して、前記残りのパリティビットの各々の値を反復して求めること、
を備える、請求項３に記載の方法。
【請求項５】
前記残りのパリティビットの各々の値を反復して求めることは、
反復毎に、最大でも１つの未知のパリティビットを含む１つまたは複数のベクトル方程式を解くことと、
を備える、請求項４に記載の方法。
【請求項６】
前記残りのパリティビットを符号化することは、
前記コードワードが所与のＬＤＰＣ符号に関して有効なコードワードであるかどうかを決定することと、
前記コードワードが有効なコードワードでない場合、前記コードワードの１つまたは複数のビット値を変更することと、
を備える、請求項１に記載の方法。
【請求項７】
前記コードワードの前記１つまたは複数のビット値を変更することは、
前記第１のパリティビットに第２のビット値を割り当てることと、ここにおいて、前記第２のビット値は前記第１のビット値とは異なる、
前記第２のビット値に少なくとも部分的に基づいて、前記残りのパリティビットの１つまたは複数のビット値を変更することと、
を備える、請求項６に記載の方法。
【請求項８】
前記残りのパリティビットの前記１つまたは複数のビット値を変更することは、
前記第１のパリティビットによって影響を受ける１つまたは複数の残りのパリティビットを識別することと、
前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットの各々のそれぞれのビット値を変更することと、
を備える、請求項７に記載の方法。
【請求項９】
前記所与のＬＤＰＣ符号に関連付けられる第２のパリティ検査行列の線形独立行を使用して第１のパリティ検査行列を生成することと、ここにおいて、前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットを識別することは、前記第１のパリティ検査行列に少なくとも部分的に基づいて、前記１つまたは複数の残りのパリティビットを識別することを含む、
をさらに備える、請求項８に記載の方法。
【請求項１０】
前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットを識別することは、
ルックアップテーブルにおいて前記１つまたは複数の残りのパリティビットを検索すること、
を備える、請求項９に記載の方法。
【請求項１１】
プログラム命令を含むコンピュータ可読記憶媒体であって、前記命令は、通信デバイス内で提供されるプロセッサによって実行されるとき、前記デバイスに、
コードワード（ｃ）に符号化されるべき情報ビットのセットを受信することと、ここにおいて、前記コードワードは、前記情報ビットのセットおよびパリティビットのセットを含む、
前記パリティビットのセットにおける第１のパリティビットに第１のビット値を割り当てることと、
前記第１のパリティビットに割り当てられた前記第１のビット値に少なくとも部分的に基づいて、前記パリティビットのセットにおける残りのパリティビットを符号化することと、
を行わせる、コンピュータ可読記憶媒体。
【請求項１２】
前記残りのパリティビットは、低密度パリティ検査（ＬＤＰＣ）符号のためのパリティ検査行列（Ｈ）および前記情報ビットのセットを使用して符号化される、請求項１１に記載のコンピュータ可読記憶媒体。
【請求項１３】
前記パリティ検査行列の線形独立行を使用して、新たなパリティ検査行列（Ｈ０）を生成すること、
を前記デバイスに行わせるプログラム命令をさらに備える、請求項１２に記載のコンピュータ可読記憶媒体。
【請求項１４】
前記残りのパリティビットを符号化するための前記プログラム命令の実行は、
式：Ｈ０ｃ＝０を使用して、前記残りのパリティビットの各々の値を反復して求めること、
を前記デバイスに行わせる、請求項１３に記載のコンピュータ可読記憶媒体。
【請求項１５】
前記残りのパリティビットの各々の値を反復して求めるための前記プログラム命令の実行は、
反復毎に、最大でも１つの未知のパリティビットを含む１つまたは複数のベクトル方程式を解くことと、
を前記デバイスに行わせる、請求項１４に記載のコンピュータ可読記憶媒体。
【請求項１６】
前記残りのパリティビットを符号化するための前記プログラム命令の実行は、
前記コードワードが所与のＬＤＰＣ符号に関して有効なコードワードであるかどうかを決定することと、
前記コードワードが有効なコードワードでない場合、前記コードワードの１つまたは複数のビット値を変更することと、
を前記デバイスに行わせる、請求項１１に記載のコンピュータ可読記憶媒体。
【請求項１７】
前記コードワードの前記１つまたは複数のビット値を変更するための前記プログラム命令の実行は、
前記第１のパリティビットに第２のビット値を割り当てることと、ここにおいて、前記第２のビット値は前記第１のビット値とは異なる、
前記第２のビット値に少なくとも部分的に基づいて、前記残りのパリティビットの１つまたは複数のビット値を変更することと、
を前記デバイスに行わせる、請求項１６に記載のコンピュータ可読記憶媒体。
【請求項１８】
前記残りのパリティビットの前記１つまたは複数のビット値を変更するための前記プログラム命令の実行は、
前記第１のパリティビットによって影響を受ける１つまたは複数の残りのパリティビットを識別することと、
前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットの各々のそれぞれのビット値を変更することと、
を前記デバイスに行わせる、請求項１７に記載のコンピュータ可読記憶媒体。
【請求項１９】
前記所与のＬＤＰＣ符号に関連付けられる第２のパリティ検査行列の線形独立行を使用して第１のパリティ検査行列を生成すること、ここにおいて、前記１つまたは複数の残りのパリティビットを識別するための前記プログラム命令は、前記第１のパリティ検査行列に少なくとも部分的に基づいて、前記１つまたは複数の残りのパリティビットを識別するための命令を含む、
を前記デバイスに行わせるプログラム命令をさらに備える、請求項１８に記載のコンピュータ可読記憶媒体。
【請求項２０】
前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットを識別するための前記プログラム命令の実行は、
ルックアップテーブルにおいて前記１つまたは複数の残りのパリティビットを検索すること、
を前記デバイスに行わせる、請求項１９に記載のコンピュータ可読記憶媒体。
【請求項２１】
通信デバイスであって、
コードワード（ｃ）に符号化されるべき情報ビットのセットを記憶するためのメモリ要素と、ここにおいて、前記コードワードは、前記情報ビットのセットおよびパリティビットのセットを含む、
前記パリティビットのセットにおける第１のパリティビットに第１のビット値を割り当てることと、
前記第１のパリティビットに割り当てられた前記第１のビット値に少なくとも部分的に基づいて、前記パリティビットのセットにおける残りのパリティビットを符号化することと、
を行うための１つまたは複数のプロセッサと、
を備える、通信デバイス。
【請求項２２】
前記残りのパリティビットは、低密度パリティ検査（ＬＤＰＣ）符号のためのパリティ検査行列（Ｈ）および前記情報ビットのセットを使用して符号化される、請求項２１に記載のデバイス。
【請求項２３】
前記１つまたは複数のプロセッサはさらに、
前記パリティ検査行列の線形独立行を使用して、新たなパリティ検査行列（Ｈ０）を生成すること、
のためのものである、請求項２２に記載のデバイス。
【請求項２４】
前記１つまたは複数のプロセッサは、
式：Ｈ０ｃ＝０を使用して、前記残りのパリティビットの各々の値を反復して求めること、
によって前記残りのパリティビットを復号するためのものである、請求項２３に記載のデバイス。
【請求項２５】
前記１つまたは複数のプロセッサは、
反復毎に、最大でも１つの未知のパリティビットを含む１つまたは複数のベクトル方程式を解くこと、
によって前記残りのパリティビットの各々の値を反復して求めるためのものである、請求項２４に記載のデバイス。
【請求項２６】
前記１つまたは複数のプロセッサは、
前記コードワードが所与のＬＤＰＣ符号に関して有効なコードワードであるかどうかを決定することと、
前記コードワードが有効なコードワードでない場合、前記コードワードの１つまたは複数のビット値を変更することと、
によって前記残りのパリティビットを符号化するためのものである、請求項２１に記載のデバイス。
【請求項２７】
前記１つまたは複数のプロセッサは、
前記第１のパリティビットに第２のビット値を割り当てることと、ここにおいて、前記第２のビット値は前記第１のビット値とは異なる、
前記第２のビット値に少なくとも部分的に基づいて、前記残りのパリティビットの１つまたは複数のビット値を変更することと、
によって前記コードワードの前記１つまたは複数のビット値を変更するためのものである、請求項２６に記載のデバイス。
【請求項２８】
前記１つまたは複数のプロセッサは、
前記第１のパリティビットによって影響を受ける１つまたは複数の残りのパリティビットを識別することと、
前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットの各々のそれぞれのビット値を変更することと、
によって前記残りのパリティビットの前記１つまたは複数のビット値を変更するためのものである、請求項２７に記載のデバイス。
【請求項２９】
前記１つまたは複数のプロセッサはさらに、
前記所与のＬＤＰＣ符号に関連付けられる第２のパリティ検査行列の線形独立行を使用して第１のパリティ検査行列を生成することと、
前記第１のパリティ検査行列に少なくとも部分的に基づいて、前記１つまたは複数の残りのパリティビットを識別することによって、前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットを識別することと、
のためのものである、請求項２８に記載のデバイス。
【請求項３０】
前記１つまたは複数のプロセッサは、
ルックアップテーブルにおいて前記１つまたは複数の残りのパリティビットを検索すること、
によって、前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットを識別するためのものである、請求項２９に記載のデバイス。
【請求項３１】
前記デバイスは、１０ＧＢＡＳＥ−Ｔイーサネットシステムの一部である、請求項２１に記載のデバイス。
【請求項３２】
通信デバイスであって、
コードワード（ｃ）に符号化されるべき情報ビットのセットを受信するための手段と、ここにおいて、前記コードワードは、前記情報ビットのセットおよびパリティビットのセットを含む、
前記パリティビットのセットにおける第１のパリティビットに第１のビット値を割り当てるための手段と、
前記第１のパリティビットに割り当てられた前記第１のビット値に少なくとも部分的に基づいて、前記パリティビットのセットにおける残りのパリティビットを符号化するための手段と、
を備える、通信デバイス。
【請求項３３】
前記残りのパリティビットは、低密度パリティ検査（ＬＤＰＣ）符号のためのパリティ検査行列（Ｈ）および前記情報ビットのセットを使用して符号化される、請求項３２に記載のデバイス。
【請求項３４】
前記パリティ検査行列Ｈの線形独立行を使用して、新たなパリティ検査行列（Ｈ０）を生成するための手段、
をさらに備える、請求項３３に記載のデバイス。
【請求項３５】
前記残りのパリティビットを符号化するための手段は、
式：Ｈ０ｃ＝０を使用して、前記残りのパリティビットの各々の値を反復して求めること、
のためのものである、請求項３４に記載のデバイス。
【請求項３６】
前記残りのパリティビットの各々の値を反復して求めるための手段は、
反復毎に、最大でも１つの未知のパリティビットを含む１つまたは複数のベクトル方程式を解くこと、
のためのものである、請求項３５に記載のデバイス。
【請求項３７】
前記残りのパリティビットを符号化するための手段は、
前記コードワードが所与のＬＤＰＣ符号に関して有効なコードワードであるかどうかを決定することと、
前記コードワードが有効なコードワードでない場合、前記コードワードの１つまたは複数のビット値を変更することと、
のためのものである、請求項３２に記載のデバイス。
【請求項３８】
前記残りのパリティビットを符号化するための手段はさらに、
前記第１のパリティビットに第２のビット値を割り当てることと、ここにおいて、前記第２のビット値は前記第１のビット値とは異なる、
前記第２のビット値に少なくとも部分的に基づいて、前記残りのパリティビットの１つまたは複数のビット値を変更することと、
のためのものである、請求項３７に記載のデバイス。
【請求項３９】
前記残りのパリティビットを符号化するための手段はさらに、
前記第１のパリティビットによって影響を受ける１つまたは複数の残りのパリティビットを識別することと、
前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットの各々のそれぞれのビット値を変更することと、
のためのものである、請求項３８に記載のデバイス。
【請求項４０】
前記所与のＬＤＰＣ符号に関連付けられる第２のパリティ検査行列の線形独立行を使用して第１のパリティ検査行列を生成するための手段と、ここにおいて、前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットを識別するための手段は、前記第１のパリティ検査行列に少なくとも部分的に基づいて、前記１つまたは複数の残りのパリティビットを識別するための手段を含む、
をさらに備える、請求項３９に記載のデバイス。
【請求項４１】
前記デバイスは、１０ＧＢＡＳＥ−Ｔイーサネットシステムの一部である、請求項３２に記載のデバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
[0001]本実施形態は概して、データ通信における誤り検出に関し、特に、低密度パリティ検査（ＬＤＰＣ）符号化に基づいて、誤り検出および／または訂正に関する。
【背景技術】
【０００２】
[0002]多くの通信システムが誤り訂正符号を使用する。特に、誤り訂正符号は、データストリームに冗長性を導入することによって、これらのシステムにおける情報転送の内在する信頼性の欠如を補うことができる。低密度パリティ検査（ＬＤＰＣ）符号は、反復コード化システムを使用する、ある特定のタイプの誤り訂正符号である。ＬＤＰＣ符号は、二部グラフ（「タナーグラフ」と度々称される）によって表されることができ、ここにおいて、変数ノードのセットは、コードワードの情報ビットに対応し、チェックノードのセットは、符号を定義するパリティ検査制約条件を表す。変数ノードおよびチェックノードは、それらがグラフのエッジで接続されている場合、「近隣」と考えられる。変数ノードシーケンスとの１対１のアソシエーションを有するビットシーケンスは、チェックノード毎に、すべての近隣変数ノードに関連付けられたビットがゼロのモジュロ２に合計してなる（すなわち、それらは偶数個の１を含む）ときかつそのときに限り（if and if only）、有効なコードワードである。
【０００３】
[0003]例えば、図１Ａは、例示的なＬＤＰＣ符号を表す二部グラフ１００を図示している。二部グラフ１００は、（四角で表されている）４つのチェックノード１２０に接続された（円で表されている）５つの変数ノード１１０のセットを含む。グラフ１００におけるエッジは、チェックノード１２０に変数ノード１１０を接続する。図１Ｂは、二部グラフ１００の行列表現１５０を図示している。行列表現１５０は、パリティ検査行列Ｈおよびコードワードベクトルｘを含み、ここにおいて、ｘ１−ｘ５は、コードワードｘのビットを表す。より具体的には、コードワードベクトルｘは、Ｈｘ＝０であるときかつそのときに限り、有効なコードワードを表す。
【０００４】
[0004]受信されたＬＤＰＣコードワードは、元のコードワードの再構築されたバージョンを作り出すために復号されうる。誤りが無い場合、または訂正可能な誤りのケースでは、復号は、符号化された元のデータ単位（data unit）を復元するために使用されうる。例えば、ＬＤＰＣデコーダは、エッジに沿って二部グラフ１００内でメッセージを交換すること、および、入ってくる（incoming）メッセージに基づいてノードにおいて計算を行うことでこれらのメッセージを更新すること、によって演算しうる。グラフ１００における各変数ノード１１０は最初に、通信チャネルからの観測によって決定されるような関連付けられたビットの値の推定値を示す「ソフトビット」（例えば、コードワードの受信されたビットを表す）を提供されうる。ＬＤＰＣデコーダはソフトビットを、対応するＬＤＰＣ符号のパリティ検査制約条件に基づいて、メモリからそれらを反復して読み取ること、およびメモリにそれらを戻すように（back）書き込むことによって更新することができる。
【０００５】
[0005]ＬＤＰＣコードワードを復号するために使用されるパリティ検査行列Ｈは、「疎（sparse）」（すなわち行列Ｈは、０のものよりも著しく少ない１を含む）である。例えば、ＩＥＥＥ８０２．３ａｎイーサネット（登録商標）規格によって採用されるＬＤＰＣ符号は、３２の行の重みおよび６の列の重みを持つ３８４×２０４８行列である。言い換えると、Ｈの各行は、３２つの１を有し、Ｈの各列は、６つの１を有する。Ｈが疎であること（sparseness）は、受信されたコードワードの効率的な復号を可能にする。反対に、ＬＤＰＣコードワードを符号化するために通常使用される生成行列（Ｇ）は、疎でない（例えば、ＧＨＴ＝０）。したがって、このような高い符号化の複雑性に起因して、生成行列Ｇを実装するＬＤＰＣエンコーダは、度々非常に複雑および／または非能率である。
【発明の概要】
【０００６】
[0006]本発明の概要は、発明を実施するための形態（Detailed Description）において以下にさらに説明される概念のセレクションを簡略化された形態で紹介するために提供されている。本発明の概要は、本願の主題の重要な特徴または本質的な特徴を特定するように意図されておらず、本願の主題の範囲を限定するようにも意図されていない。
【０００７】
[0007]別のデバイスに送信されるべきデータの符号化を支援しうる演算のデバイスおよび方法が開示されている。いくつかの実施形態では、デバイスは、コードワード（ｃ）に符号化されるべき情報のセットを記憶するためのメモリ要素と、ここにおいて、該コードワードは、情報ビットのセットおよびパリティビットのセットを含み、（ｉ）該パリティビットのセットにおける第１のパリティビットに第１のビット値を割り当て、（ｉｉ）該第１のパリティビットに割り当てられた該第１のビット値に少なくとも部分的に基づいて、該パリティビットのセットにおける残りのパリティビットを符号化する、ための１つまたは複数のプロセッサと、を含む。該１つまたは複数のプロセッサは、低密度パリティ検査（ＬＤＰＣ）符号のためのパリティ検査行列（Ｈ）および情報ビットのセットを使用して、該残りのパリティビットを符号化することができる。該１つまたは複数のプロセッサはまた、該符号化されたコードワードが、該ＬＤＰＣ符号を考慮した場合に有効なコードワードであるかどうかを決定することができ、それが有効なコードワードでない場合、該コードワードの１つまたは複数のビットを変更することができる。
【０００８】
[0008]いくつかの実施形態では、新たなパリティ検査行列（Ｈ０）が、パリティ検査行列Ｈの線形独立行に基づいて生成されうる。該残りのパリティビットの各々はその後、式：Ｈ０ｃ＝０に基づいて反復して値が求められうる（evaluate）。特に、該残りのパリティビットは、１つまたは複数のベクトル方程式を反復して解くことによって値を求められうる。
【０００９】
[0009]いくつかの実施形態では、該第１のパリティビットは、該コードワードが有効なコードワードでない場合に第２のビット値を割り当てられうる。該１つまたは複数のプロセッサはその後、もしあれば、該残りのパリティビットのどれが該第１のパリティビットによって影響を受けるかを決定し、該影響を受けたパリティビットのビット値を変更することができる。例えば、該１つまたは複数のプロセッサは、ルックアップテーブルにおいて該影響を受けたパリティビットを検索することができる。
【００１０】
[0010]（例えば、むしろ生成行列Ｇよりも）該パリティ検査行列Ｈを使用してＬＤＰＣコードワードを符号化することは、Ｈが疎であることに起因して符号化演算の複雑性を実質的に低減する。さらに、該第１のパリティビットのためのビット値を前提とすること、およびその前提に基づいて該残りのパリティビットの値を反復して求めることは、該ＬＤＰＣ符号化演算が、実質的に線形の方法で即座に行われることを可能にする。さらに、有限数の残りのパリティビットのみが、該第１のパリティビットの値に関する正しくない（incorrect）前提によって影響を受けうるので、正しくない前提に基づいて生成されるコードワードは、単一のステップで（例えば該影響を受けたパリティビットのビット値を変更することによって）実質的に訂正されうる。
【００１１】
[0011]本実施形態は、例として例示されており、添付図面の図によって制限されるようには意図されていない。
【図面の簡単な説明】
【００１２】
【図１Ａ】例示的なＬＤＰＣ符号の図式的および行列表現を図示している。
【図１Ｂ】例示的なＬＤＰＣ符号の図式的および行列表現を図示している。
【図２】いくつかの実施形態にしたがった通信システムを図示している。
【図３】いくつかの実施形態にしたがったデータ符号化演算を描写している実例的なフローチャートである。
【図４】いくつかの実施形態にしたがったＬＤＰＣ処理デバイスのブロック図である。
【図５】いくつかの実施形態にしたがってコードワードのパリティビットの値を求める方法を描写している実例的なフローチャートである。
【図６】いくつかの実施形態にしたがった別のデータ符号化演算を描写している実例的なフロー図である。
【図７】いくつかの実施形態にしたがったエンコーダのブロック図である。
【発明を実施するための形態】
【００１３】
[0019]以下の説明では、本開示の完全な理解を提供するために、特定のコンポーネント、回路、およびプロセスの例のような、多数の特定の詳細が述べられる。本明細書で使用される場合、「結合された」という用語は、直接接続されること、または、１つまたは複数の介在するコンポーネントまたは回路を通じて接続されることを意味する。また、以下の説明では、説明の目的で、本実施形態の完全な理解を提供するために特定の専門用語が述べられる。しかしながら、本実施形態を実施するためにこれらの特定の詳細が要求されない場合もあることは、当業者には明らかであろう。他の事例では、周知の回路およびデバイスが、本開示を不明確にすることを避けるために、ブロック図の形態で図示されている。本明細書に説明されている様々なバスによって提供される信号はいずれも、他の信号と時間多重され、１つまたは複数のコモンバスをわたって提供されうる。さらに、回路要素またはソフトウェアブロック間の相互接続は、バスまたは単一の信号線として図示されうる。バスの各々は、代わりとして単一の信号線であることができ、単一の信号線の各々は、代わりとしてバスであることができ、単一の線またはバスは、コンポーネント間の通信のための無数の物理的または論理的なメカニズムのうちの任意の１つまたは複数を表すことができる。本実施形態は、本明細書で説明されている特定の例に限定されるようには解釈されるものではなく、添付の特許請求の範囲によって定義されるすべての実施形態をその範囲内に含むものである。
【００１４】
[0020]図２は、いくつかの実施形態にしたがって通信システム２００を図示している。送信機２１０は、チャネル２２０上に信号を送信し、受信機２３０は、チャネル２２０からその信号を受信する。送信機２１０および受信機２３０は、例えば、コンピュータ、スイッチ、ルータ、ハブ、ゲートウェイ、および／または同様のデバイスでありうる。いくつかの実施形態では、通信システムは、ＩＥＥＥ８０２．３ａｎイーサネット規格に基づいた１０ＧＢＡＳＥ−Ｔイーサネットシステムである（例えば、チャネル２２０は有線リンクである）が、他の有線通信規格がシステム２００によって用いられうる。他の実施形態では、チャネル２２０は、ワイヤレスでありうる。
【００１５】
[0021]通信システム２００における様々なコンポーネントの不完全さは、信号の機能障害（signal impairment）のもととなり得、それにより信号減衰を引き起こしうる。例えば、チャネル２２０における不完全さは、チャネルの歪みを引き起こし得、これは、線形の歪み、マルチパスエフェクト、および／また加法性白色ガウス雑音（ＡＷＧＮ）を含みうる。潜在的な信号減衰に対抗するために、送信機２１０および受信機２３０は、ＬＤＰＣエンコーダおよびデコーダをそれぞれ含むことができる。特に、送信機２１０は、元のデータを復元するために（例えば、ＬＤＰＣ復号演算を通じて）受信機２３０によって実質的に復号されうるコードワードを作り出すために、出ていく（outgoing）データに対してＬＤＰＣ符号化を行うことができる。いくつかの実施形態では、送信機２１０は、送信機２１０および受信機２３０の両方によって使用されるＬＤＰＣ符号に関連付けられたパリティ検査行列（Ｈ）に基づいてコードワードを生成することができる。さらにいくつかの実施形態では、送信機２１０は、第１のパリティビットのための最初のビット値を前提とすること、およびその第１のパリティビットの最初のビット値に基づいて残りのパリティビットの値を反復して求めることによって、コードワードのためのパリティビットのセットを生成することができる。
【００１６】
[0022]図３は、いくつかの実施形態にしたがったデータ符号化演算３００を描写している実例的なフローチャートである。例えば図２を参照すると、送信機２１０は第１に、符号化および送信されるべき情報ビットのセットを受信する（３１０）。いくつかの実施形態では、情報ビットは、送信機２１０と受信機２３０との間で共有されるＬＤＰＣ符号に基づいて、ＬＤＰＣコードワード（ｃ）に符号化されうる。各コードワードｃは、元の情報ビット（ｃｓ）に加えてパリティビット（ｃｐ）のセットを含むことができ、それは、元の情報ビットｃｓに対してパリティ検査を行う、および／または元の情報ビットｃｓを復元するために使用されうる。いくつかの実施形態では、ＬＤＰＣ符号は、８０２．３ａｎイーサネット規格（例えば、１０ＧＢＡＳＥ−Ｔ）に基づくと、（２０４８、１７２３）正則ＬＤＰＣ符号に対応しうる。特に、８０２．３ａｎイーサネット規格の下で、１７２３情報ビットは、２０４８ビットコードワードを形成するために３２５パリティビットと組み合わせられる。
【００１７】
[0023]送信機２１０はその後、コードワードｃの第１のパリティビット（ｃｐ［０］）に最初のビット値（ｂ０）を割り当てる（３２０）。以下でより具体的に説明されることになるように、最初のビット値ｂ０は、第１のパリティビットｃｐ［０］の実際のビット値に関する「前提（assumption）」である。したがっていくつかの実施形態では、最初のビット値ｂ０は、前提が正しくないと実質的に決定される場合に、変更または訂正されうる任意の値（例えば０または１のどちらか）でありうる。本実施形態では、簡略化のためだけに、「第１の」パリティビット（すなわちｃｐ［０］）に対して前提がなされていることは、留意されるべきである。他の実施形態では、最初のビット値ｂ０は、パリティビットｃｐ［０］−ｃｐ［ｎ］のいずれかに対して前提とされうる。
【００１８】
[0024]最後に、送信機２１０は、第１のパリティビットｃｐ［０］に割り当てられた最初のビット値ｂ０に部分的に基づいて、残りのパリティビット（ｃｐ［１］−ｃｐ［ｎ］）を符号化する（３３０）。いくつかの実施形態では、残りのパリティビットｃｐ［１］−ｃｐ［ｎ］は、例えば、Ｈｃ＝０（ｍｏｄ２）を解くことによって、パリティ検査行列Ｈに基づいて、値が求められうる。さらにいくつかの実施形態では、送信機２１０は、例えば、最後のコードワードｃが、所与のＬＤＰＣ符号に関して有効なコードワードであるかどうかを決定することによって、パリティビットｃｐ［０］−ｃｐ［ｎ］が適切に符号化されうるかどうかを証明することができる。コードワードｃが有効なＬＤＰＣコードワードを表さない場合、送信機２１０は、第１のパリティビットｃｐ［０］、および最初のビット値ｂ０に基づいて不正確に符号化されてしまっていることがあるあらゆる残りのパリティビットｃｐ［１］−ｃｐ［ｎ］、のビット値を「反転（flip）」または変更することができる。
【００１９】
[0025]図４は、いくつかの実施形態にしたがったＬＤＰＣ処理デバイス４００のブロック図である。ＬＤＰＣ処理デバイス４００は、エンコーダ４１０、デコーダ４２０、および、通信チャネル（例えば、図２のチャネル２２０）を介してＬＤＰＣ符号化されたコードワードを送信および／または受信するトランシーバ４３０を含む。いくつかの実施形態では、通信チャネルは、１０ＧＢＡＳＥ−Ｔイーサネットチャネルに対応しうる（しかしながら他の通信媒体が使用されうる）。いくつかの実施形態では、ＬＤＰＣ符号は、８０２．３ａｎイーサネット規格（例えば、１０ＧＢＡＳＥ−Ｔ）に基づくと、正則（２０４８、１７２３）ＬＤＰＣ符号でありうる。したがって、各ＬＤＰＣコードワードは、長さが２０４８ビットであり得、それは１７２３情報ビットおよび３２５パリティビットを含む。
【００２０】
[0026]エンコーダ４１０は、メモリ４１２、ＬＤＰＣエンコーダ４１４、およびコードワード証明および訂正（ＣＶＣ）プロセッサ４１６を含む。特に、メモリ４１２は、ＬＤＰＣエンコーダ４１４によって符号化されるべき情報ビットを記憶することができる。ＬＤＰＣエンコーダ４１４は、別のデバイスに送信されるべきコードワードｃを、ＬＤＰＣ符号に基づいて生成することによって、メモリ４１２に記憶された情報ビットを処理する。いくつかの実施形態では、ＬＤＰＣエンコーダ４１４は、例えば、第１のパリティビットｃｐ［０］のための最初のビット値ｂ０を前提とすること、および式：Ｈｃ＝０に基づいて残りのパリティビットｃｐ［１］−ｃｐ［ｎ］の値を求めることによって、ＬＤＰＣ符号に関連付けられたパリティ検査行列Ｈに基づいて、コードワードｃを生成することができる。ＣＶＣプロセッサ４１６は、ＬＤＰＣエンコーダ４１４によって生成されたコードワードｃが、ＬＤＰＣ符号を考慮した場合に有効なコードワードを表すかどうかを決定する。いくつかの実施形態では、ＣＶＣプロセッサ４１６は、Ｈｃ＝０を証明することによって、コードワードｃの有効性を決定することができる。ｃが有効なコードワードでない場合、ＣＶＣプロセッサ４１６は、第１のパリティビットｃｐ［０］、および第１のパリティビットｃｐ［０］のビット値によって影響を受けるあらゆる残りのパリティビットｃｐ［１］−ｃｐ［ｎ］、のビット値を反転することで、コードワードｃを修正することができる。
【００２１】
[0027]デコーダ４２０は、メモリ４２２およびＬＤＰＣデコーダ４２４を含む。メモリ４２２は、トランシーバ４３０を介して受信される、ＬＤＰＣデコーダ４２４によって復号されるべきコードワードを記憶することができる。ＬＤＰＣデコーダ４２４は、ＬＤＰＣ符号に基づいてパリティ検査演算を行うことによって、メモリ４２２に記憶されるコードワードを処理する（ＬＤＰＣデコーダ４２４が、コードワードｃを生成するためにＬＤＰＣエンコーダ４１４によって使用されるものと同じパリティ検査行列Ｈを使用してパリティ検査演算を行うことができることに留意されたい）。より具体的には、ＬＤＰＣデコーダ４２４は、受信されたコードワードにおけるビットの有効性を証明すること、および／または誤って受信されてしまったあらゆるビットを、パリティ検査演算を通じて訂正するように試みることができる。例えば、各パリティ検査演算は、メモリ４２２から対応するソフトビット値を読み取ることと、そのソフトビット値を、特定のチェックノード（例えば、パリティ検査制約条件）に関連付けられた他のソフトビット値と組み合わせることと、結果としてチェックノード演算から生じるビット値をメモリ４２２に戻すように書き込むことと、を伴うことができる。いくつかの実施形態では、ＬＤＰＣデコーダ４２４は、パリティ検査演算を並行して行うために、複数の処理要素を含むことができる。ＬＤＰＣデコーダ４２４は、受信されたコードワードにおける１つまたは複数のビット誤りを訂正することができない（これにより結果として復号誤りをもたらす）場合、デコーダ４２４は、復号誤りメッセージを作り出すことができる。
【００２２】
[0028]生成行列Ｇの代わりにパリティ検査行列Ｈを使用することによって、エンコーダ４１０は、（例えば、Ｈが疎であることに起因して）比較的低い複雑性を持つ符号化演算を行うことによって、ＬＤＰＣコードワードを生成することができる。さらに、第１のパリティビットｃｐ［０］のためのビット値を前提とすること、およびその前提に基づいて残りのパリティビットｃｐ［１］−ｃｐ［ｎ］の値を反復して求めることは、エンコーダ４１０が、迅速に、かつ実質的に線形の方法でコードワードを生成することを可能にする。
【００２３】
[0029]図５は、いくつかの実施形態にしたがってコードワードのパリティビットの値を求める方法５００を描写している実例的なフローチャートである。新たなパリティ検査行列Ｈ０が、パリティ検査行列Ｈの線形独立行から構成される（５１０）。例えば、８０２．３ａｎイーサネット規格のＬＤＰＣ符号のためのパリティ検査行列Ｈは、ランク３２５を持つ３８４×２０４８行列である。したがって、Ｈの３８４行のうち、３２５のみが線形独立である（すなわち、他の行の線形結合として表現されることができない）。特に、３２５の線形独立行は、
【００２４】
【表１】
2016521064.tif 000003
【００２５】
である。８０２．３ａｎイーサネット規格のＬＤＰＣ符号のための、結果として生じる新たなパリティ検査行列Ｈ０は、元のパリティ検査行列Ｈの３２５の独立行（上記でリストアップされている）を備える３２５×２０４８行列である。
【００２６】
[0030]新たなパリティ検査行列Ｈ０はその後、２つのサブ行列ＨｓおよびＨｐにさらに分割される（５２０）。特に、Ｎ×Ｍパリティ検査行列Ｈ０は、
【００２７】
【数１】
2016521064.tif 000004
【００２８】
として表現されることができ、ここにおいて、Ｈｓは、Ｎ×Ｋサブ行列（Ｋは、各コードワードにおける情報ビットの数に対応する）であり、Ｈｐは、Ｎ×（Ｍ−Ｋ）サブ行列（Ｍ−Ｋは、各コードワードにおけるパリティビットの数に対応する）である。上記で説明されたように、８０２．３ａｎイーサネット規格は、１７２３情報ビット（すなわちＫ＝１７２３）および３２５パリティビットを備える２０４８ビットのＬＤＰＣコードワードを指定する。したがって、３２５×２０４８パリティ検査行列Ｈ０は、３２５×１７２３サブ行列Ｈｓおよび３２５×３２５サブ行列Ｈｐの観点から表現されることができる。
【００２９】
[0031]１×Ｍベクトルとして表現されるコードワードｃは、構成要素ベクトルｃｓおよびｃｐにさらに分割される（５３０）。より具体的には、Ｍビットコードワードｃは、
【００３０】
【数２】
2016521064.tif 000005
【００３１】
として表現されることができ、ここにおいて、ｃｓは、符号化されるべきＫ情報ビットを表し、ｃｐは、Ｍ−Ｋパリティビットを表す。例えば、８０２．３ａｎイーサネット規格に関して、２０４８ビットのコードワードｃは、１７２３情報ビットｃｓおよび３２５パリティビットｃｐの観点から表現されうる。
【００３２】
[0032]最後に、パリティビットｃｐは、ベクトル方程式：Ｈｓｃｓ＝Ｈｐｃｐを解くことによって値が求められうる（５４０）。例えば上記で説明されたように、任意の有効なコードワードｃに関してＨｃ＝０であるように、パリティ検査行列Ｈは定義される。Ｈ０がＨの独立行を含むので、任意の有効なコードワードｃに関してＨ０ｃ＝０であるという結果になる。Ｈ０の代わりにＨＳおよびＨｐを、ｃの代わりにｃｓおよびｃｐを用いることは、以下の式をもたらす。
【００３３】
【数３】
2016521064.tif 000006
【００３４】
バイナリフィールド符号化では、上記の式は
【００３５】
【数４】
2016521064.tif 000007
【００３６】
として書き換えられることができ、ここにおいて、ｓは、パリティ検査サブ行列Ｈｓと情報ビットｃｓを乗ずることによって得られる解ベクトルを表す。より具体的には、情報ビットｃｓは知られており（すなわち、それらは、符号化されるべき実際のデータビットである）、サブ行列Ｈｓの要素もまた知られている（すなわち、それらは、パリティ検査行列Ｈの要素に対応する）ので、Ｈｓｃｓの積は、解ベクトルｓによって表されることができる。したがって、パリティビットｃｐは、ベクトル方程式：
【００３７】
【数５】
2016521064.tif 000008
【００３８】
から決定されうる。
【００３９】
[0033]ｃｐが未知のビット値の実質的な数を備えることができる（例えば、８０２．３ａｎイーサネット規格の下ではコードワード毎に３２５パリティビットが存在する）ことは留意されるべきである。したがって、無理に（by brute force）上記式を解くことは、高レベルの符号化の複雑性を伴いうる。しかしながら、パリティビットのうちの１つのためのビット値を最初に前提とすることによって、残りのパリティビットが、実質的に線形の方法で即座に決定されうる。
【００４０】
[0034]生成行列Ｇの代わりにパリティ検査行列Ｈを使用してＬＤＰＣコードワードを符号化するによって、方法５００は、Ｈが疎であることに起因して符号化演算の複雑性を実質的に低減することができる。方法５００はさらに、符号化のために、元のパリティ検査行列Ｈの線形独立行のみを含む、新たなパリティ検査行列Ｈ０を使用することによって符号化の複雑性を低減する。
【００４１】
[0035]図６は、いくつかの実施形態にしたがった別のデータ符号化演算６００を描写している実例的なフローチャートである。上記で説明されたように、本実施形態は、パリティ検査行列Ｈ（またはＨ０）に基づいて、およびパリティビットｃｐの少なくとも１つのための最初のビット値を前提とすることによって、ＬＤＰＣコードワードｃを生成することができる。図４も参照すると、演算６００において、ＬＤＰＣ処理デバイス４００は最初に、符号化されるべき情報ビットｃｓのセットを受信する（６１０）。例えば、情報ビットｃｓは、ＬＤＰＣ処理デバイス４００もまた内在する通信デバイスの中央処理ユニット（ＣＰＵ）から受信されうる。
【００４２】
[0036]ＬＤＰＣ処理デバイス４００は、符号化されるべき情報ビットｃｓのセット毎にパリティビットｃｐのセットを決定することによって、ＬＤＰＣコードワードｃを生成する（例えば、ここにおいて、c = [cs cp]である）。図５を参照して上記で説明されたように、パリティビットｃｐは、式：Ｈｐｃｐ＝Ｈｓｃｓ＝ｓに基づいて値が求められうる。いくつかの実施形態では、ＬＤＰＣコードワードｃは、ＬＤＰＣ処理デバイス４００のエンコーダ４１０によって生成される。
【００４３】
[0037]ＬＤＰＣエンコーダ４１４は、コードワードｃの第１のパリティビットｃｐ［０］をゼロに設定する（６２０）。上記で説明されたように、第１のパリティビットｃｐ［０］に割り当てられたゼロビット値は、実際のビット値のための前提である。例えば、この前提により、残りのパリティビットｃｐ［１］−ｃｐ［ｎ］が、比較的低い符号化の複雑性で、実質的に線形の方法で値を求められることができるようになる。
【００４４】
[0038]ＬＤＰＣエンコーダ４１４はその後、第１のパリティビットｃｐ［０］に基づいて、残りのパリティビットｃｐ［１］−ｃｐ［ｎ］の値を反復して求める（６３０）。いくつかの実施形態では、反復毎に、既知のパリティビット値が、最大でも１つの未知のパリティビットを伴う（例えば、Ｈ０ｃ＝０から生じる）１つまたは複数のベクトル方程式に代入されうる。例えば、第１の反復中、第１のパリティビットｃｐ［０］は、最大でも１つの追加の未知のパリティビット（例えば、ｃｐ［１］）を伴う任意のベクトル方程式（複数も含む）において、その前提とされた値（例えば、ｃｐ［０］＝０）に代わって用いられうる。特定のベクトル方程式における唯一の未知のパリティビットとして、ｃｐ［１］の値は容易に決定されうる。次の反復において、２つの既知のパリティビットｃｐ［０］およびｃｐ［１］が、最大でも１つの追加の未知のパリティビット（例えば、ｃｐ［２］）を伴う１つまたは複数の他のベクトル方程式において代入されうる。このプロセスは、残りのパリティビット（例えば、ｃｐ［３］−ｃｐ［ｎ］）のすべての値が求められてしまうまで繰り返されうる。
【００４５】
[0039]パリティビットｃｐ［０］−ｃｐ［ｎ］のすべてがビット値を割り当てられた後、ＣＶＣプロセッサ４１６は、コードワードｃの有効性を検査する（６４０）。例えば、有効なコードワードｃは、式：Ｈｃ＝０および／またはＨ０ｃ＝０を満たすべきである。ベクトル積が０をもたらす場合、ｃは、有効なコードワードであり、ベクトル積が１をもたらす場合、ｃは有効なコードワードでない。ＣＶＣプロセッサ４１６が、ｃが有効なコードワードであるかどうかを決定するために、Ｈｃ（またはＨ０ｃ）のすべての行−積（row-product）の値を求める必要はないことは留意されるべきである。いくつかの実施形態において、ＣＶＣプロセッサ４１６は、単にコードワードｃが無効であるときはいつでも、１をもたらすと知られているパリティ検査行列Ｈ０の行をコードワードｃに乗じることによって、コードワードｃの有効性を証明することができる。例えば、８０２．３ａｎイーサネット規格の下で、ＣＶＣプロセッサ４１６は、パリティ検査行列Ｈ０の最後の行（例えば、８０２．３ａｎ規格のＬＤＰＣ符号のための行列Ｈの行３７１に対応する、行列Ｈ０の行３２５）をコードワードｃに乗ずることによって、この方法で生成されるコードワードの有効性を証明することができる。
【００４６】
[0040]ｃが有効なコードワードであるとＣＶＣプロセッサ４１６が決定する（６４０）場合、それは、最後の「符号化された」コードワードとしてコードワードｃを出力することによって進む（６７０）。例えば、コードワードｃはトランシーバ４３０に転送されることができ、トランシーバ４３０はその後、ネットワークにおいて別のデバイスにコードワードｃを送信することができる。しかしながら、ｃが有効なコードワードでないとＣＶＣプロセッサ４１６が決定する（６４０）場合、それは、第１のパリティビットｃｐ［０］に関する前提が正しくなかった（例えば、ｃｐ［０］≠０）ためである。
【００４７】
[0041]したがって、ｃが有効なコードワードでない（６４０）場合、ＣＶＣプロセッサ４１６は、第１のパリティビットｃｐ［０］を１に設定することができる（６５０）。ｃｐ［０］が最初に０であることが前提とされ（６２０）、残りのパリティビットｃｐ［１］−ｃｐ［ｎ］がその前提に基づいて値を求められたことを思い出されたい。第１のパリティビットｃｐ［０］に関する前提が正しくない場合、その正しくない前提に依存するあらゆる残りのパリティビットもまた、結果として誤ったビット値を有することになる。したがってＣＶＣプロセッサ４１６は、第１のパリティビットｃｐ［０］に割り当てられた最初のビット値によって影響を受けてしまっているいずれのそのような残りのパリティビットｃｐ［１］−ｃｐ［ｎ］のビット値も反転しうる。いくつかの実施形態では、ＬＤＰＣエンコーダ４１４は、第１のパリティビットｃｐ［０］に割り当てられた最初のビット値に基づいて、他のパリティビットｃｐ［１］−ｃｐ［ｎ］の値を再び求めることができる。
【００４８】
[0042]残りのパリティビットｃｐ［１］−ｃｐ［ｎ］のすべてが、ｃｐ［０］に割り当てられたビット値によって影響を受けうるわけではないことは留意されたい。言い換えると、いくつかのパリティビットは、ｃｐ［０］＝０または１であるかどうかに関わらず、同じビット値に評価されうる。さらに、影響を受けたパリティビットは、パリティ検査行列Ｈ０（またはＨ）にのみ依存し、それにより符号化より前に決定されうる。したがって、いくつかの実施形態では、第１のパリティビットｃｐ［０］のビット値を変更した（６５０）後、ＣＶＣプロセッサ４１６は、残りのパリティビットｃｐ［１］−ｃｐ［ｎ］間のあらゆる影響を受けたパリティビットのビット値を単に反転するだけでありうる（６６０）。
【００４９】
[0043]例えば、８０２．３ａｎ規格のＬＤＰＣ符号を参照すると、第１のパリティビットｃｐ［０］のビット値に依存する（またはそれに影響を受ける）ぴったり５５のパリティビットｃｐが存在する。これらの５５のパリティビットは、
【００５０】
【表２】
2016521064.tif 000009
【００５１】
である。上記の例では、ｃが有効なコードワードでない場合（例えば、ｃｐ［０］＝０という前提の下において）、ＣＶＣプロセッサ４１６は、ｃｐ［０］＝１を設定し（６５０）、上記でリストアップされた残りの５５のパリティビットのビット値を（例えば、０のものを１のものに変更すること、およびその逆を行うことによって）反転することができる。
【００５２】
[0044]第１のパリティビットｃｐ［０］、および残りのパリティビットｃｐ［１］−ｃｐ［ｎ］間のあらゆる影響を受けたパリティビットが反転された（６５０−６６０）後、結果としてもたらされるコードワードｃは有効なコードワードになる。したがって、ＣＶＣプロセッサ４１６は、最後の符号化されたコードワードとしてこの「訂正された」コードワードｃを出力することができる（６７０）。
【００５３】
[0045]第１のパリティビットｃｐ［０］のためのビット値を前提とすること、およびその前提に基づいて残りのパリティビットｃｐ［１］−ｃｐ［ｎ］の値を反復して求めることは、データ符号化演算６００が、迅速に、かつ実質的に線形の方法で実行されることを可能にする。パリティビットの固定セットのみが、第１のパリティビットｃｐ［０］のビット値によって影響を受けるので、ならびに、影響を受けたパリティビットは予め決定されうるので、正しくない前提（例えば、ｃｐ［０］≠０）に基づいて生成されるコードワードｃは、（例えば、影響を受けたパリティビットを反転することによって）単一のステップで訂正されうる。
【００５４】
[0046]図７は、いくつかの実施形態にしたがったエンコーダ７００のブロック図である。エンコーダ７００は、エンコーダインターフェース７１０、プロセッサ７２０、およびメモリ７３９含む。エンコーダインターフェース７１０は、エンコーダ７００に、および／またはエンコーダ７００からデータを通信するために使用されうる。例えば、エンコーダインターフェース７１０は、１つまたは複数のコードワードに符号化されるべき情報ビットを（例えば、ＣＰＵから）受信することができる。エンコーダインターフェース７１０はまた、エンコーダ７００によって生成されるコードワードを（例えば、トランシーバに）出力することもできる。
【００５５】
[0047]メモリ７３０は、受信された情報ビットを記憶するためにローカルキャッシュとして使用されうる情報ビットデータベース７３１、および１つまたは複数の影響を受けたパリティビットを識別する情報を記憶するために使用されうるビット訂正ルックアップテーブル７３２を含むことができる。上記で説明されているように、影響を受けたパリティビットは、第１のパリティビット（例えば、ｃｐ［０］）のビット値によって影響を受けうるコードワードｃの１つまたは複数のパリティビットｃｐに対応する。
【００５６】
[0048]さらに、メモリ７３０はまた、下記のソフトウェアモジュールの１つまたは複数を記憶することができる非一時的なコンピュータ可読記憶媒体（例えば、ＥＰＲＯＭ、ＥＥＰＲＯＭ（登録商標）、フラッシュメモリ、ハードドライブ、等のような１つまたは複数の不揮発性のメモリ要素）を含むことができる。  
・各コードワードの第１のパリティビットに最初のビット値を割り当てることによって、ＬＤＰＣ符号に関連付けられたパリティ検査行列Ｈを使用してＬＤＰＣコードワードを生成するための反復符号化モジュール７３３  
・反復符号化モジュール７３３によって生成された各コードワードが所与のＬＤＰＣ符号に関して有効なコードワードを表すかどうかを証明するためのコードワード（ＣＷ）証明モジュール７３４  
・無効であると決定されたコードワードの１つまたは複数のパリティビットを反転（すなわち、変更）するためのＣＷ訂正モジュール７３５  
各ソフトウェアモジュールは、プロセッサ７２０によって実行されるとき、エンコーダ７００に、対応する関数を実行させる命令を含むことができる。したがって、メモリ７３０の非一時的なコンピュータ可読記憶媒体は、図５−６に関して説明された演算のすべてまたは一部を行うための命令を含むことができる。
【００５７】
[0049]エンコーダインターフェース７１０とメモリ７３０との間で結合される、プロセッサ７２０は、（例えば、メモリ７３０内の）デコーダ７００に記憶される１つまたは複数のソフトウェアプログラムの命令のスクリプトを実行する能力がある、あらゆる適したプロセッサであることができる。例えば、プロセッサ７２０は、反復符号化モジュール７３３、ＣＷ証明モジュール７３４、および／またはＣＷ訂正モジュール７３５を実行することができる。
【００５８】
[0050]反復符号化モジュール７３３は、ＬＤＰＣコードワードｃを生成することによって情報ビットデータベース７３１に記憶された情報ビットを処理するために、プロセッサ７２０によって実行されうる。例えば、反復符号化モジュール７３３は、プロセッサ７２０によって実行されるとき、符号化されるべき情報ビットｃｓおよびＬＤＰＣ符号に関連付けられたパリティ検査行列Ｈに基づいて、コードワードｃのためのパリティビットｃｐのセットを決定することができる。いくつかの実施形態では、プロセッサ７２０は、（例えば、図５−６を参照して上記で説明されたように）コードワードｃの第１のパリティビットｃｐ［０］のための最初のビット値ｂ０を前提とし、式：Ｈｐｃｐ＝Ｈｓｃｓに基づいて残りのパリティビットｃｐ［１］−ｃｐ［ｎ］の値を反復して求めることによって、コードワードｃを生成することができる。
【００５９】
[0051]ＣＷ証明モジュール７３４は、反復符号化モジュール７３３によって生成されたコードワードｃが所与のＬＤＰＣ符号に関して有効なコードワードを表すかどうかを決定するために、プロセッサ７２０によって実行されうる。例えば、プロセッサ７２０によって実行されるとき、ＣＷ証明モジュール７３４は、Ｈｃ＝０を証明することによって、コードワードｃの有効性を決定することができる。いくつかの実施形態では、ＣＷ証明モジュール７３４を実行する際にプロセッサ７２０は、（例えば、図５を参照して上記で説明されたように）コードワードｃが無効であるときはいつでも、１をもたらすと知られているパリティ検査行列Ｈの単一の行をコードワードｃに乗ずることによって、コードワードｃの有効性を証明することができる。ｃが有効なコードワードである場合、プロセッサ７２０は、例えばトランシーバに出力されるべきコードワードｃをエンコーダインターフェース７１０に転送することができる。しかしながらｃが有効なコードワードでない場合、プロセッサ７２０はその代わりに、ＣＷ訂正モジュール７３５を実行することができる。
【００６０】
[0052]プロセッサ７２０によって実行されるとき、ＣＷ訂正モジュール７３５は、ＣＷ証明モジュール７３４によって無効であると決定されるコードワードｃを訂正または変更することができる。例えば、ＣＷ訂正モジュール７３５を実行する際にプロセッサ７２０は、第１のパリティビットｃｐ［０］のために前提とされた最初のビット値によって影響を受ける１つまたは複数のパリティビットｃｐ［１］−ｃｐ［ｎ］のためのビット値を反転することができる。いくつかの実施形態では、プロセッサ７２０は、第１のパリティビットｃｐ［０］の値を反転し、後続して残りのパリティビットｃｐ［１］−ｃｐ［ｎ］の値を再び求めることによって、コードワードｃを訂正することができる。他の実施形態では、プロセッサ７２０は、ビット訂正ルックアップテーブル７３２において影響を受けたパリティビットを検索し、（例えば、第１のパリティビットｃｐ［０］、および第１のパリティビットｃｐ［０］によって影響を受けるあらゆる他のパリティビットｃｐ［１］−ｃｐ［ｎ］を含む）影響を受けたパリティビットのみのビット値を反転することによって、コードワードｃを訂正することができる。
【００６１】
[0053]前の詳述では、本実施形態は、その特定の例示的な実施形態を参照して説明されてきた。しかしながら、添付の特許請求の範囲で述べられている開示のより広い範囲から逸脱することなく、様々な修正および変更がそれになされることは明らかであろう。したがって、明細書および図面は、限定的な意味というよりむしろ実例的な意味の中で考慮されるものとする。例えば、図３、５、および６のフロー図において描写された方法のステップは他の適切な順序で実行され得、複数のステップは単一のステップに結合され得、および／またはいくつかのステップは省略されうる。
【図１Ａ】
2016521064.tif 000010
【図１Ｂ】
2016521064.tif 000011
【図２】
2016521064.tif 000012
【図３】
2016521064.tif 000013
【図４】
2016521064.tif 000014
【図５】
2016521064.tif 000015
【図６】
2016521064.tif 000016
【図７】
2016521064.tif 000017
【手続補正書】
【提出日】平成27年12月25日(2015.12.25)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データ符号化の方法であって、
コードワード（ｃ）に符号化されるべき情報ビットのセットを受信することと、ここにおいて、前記コードワードは、前記情報ビットのセットおよびパリティビットのセットを含む、
前記パリティビットのセットにおける第１のパリティビットに第１のビット値を割り当てることと、
前記第１のパリティビットに割り当てられた前記第１のビット値に少なくとも部分的に基づいて、前記パリティビットのセットにおける残りのパリティビットを符号化することと、
を備え、前記残りのパリティビットを符号化することは、
前記コードワードが所与のＬＤＰＣ符号に関して有効なコードワードであるかどうかを決定することと、
前記コードワードが有効なコードワードでない場合、前記コードワードの１つまたは複数のビット値を変更することと、
を備える、データ符号化の方法。
【請求項２】
前記残りのパリティビットは、低密度パリティ検査（ＬＤＰＣ）符号のためのパリティ検査行列（Ｈ）および前記情報ビットのセットを使用して符号化される、請求項１に記載の方法。
【請求項３】
前記パリティ検査行列の線形独立行を使用して、新たなパリティ検査行列（Ｈ０）を生成すること、
をさらに備える、請求項２に記載の方法。
【請求項４】
前記残りのパリティビットを符号化することは、
式：Ｈ０ｃ＝０を使用して、前記残りのパリティビットの各々の値を反復して求めること、
を備える、請求項３に記載の方法。
【請求項５】
前記残りのパリティビットの各々の値を反復して求めることは、
反復毎に、最大でも１つの未知のパリティビットを含む１つまたは複数のベクトル方程式を解くことと、
を備える、請求項４に記載の方法。
【請求項６】
前記コードワードの前記１つまたは複数のビット値を変更することは、
前記第１のパリティビットに第２のビット値を割り当てることと、ここにおいて、前記第２のビット値は前記第１のビット値とは異なる、
前記第２のビット値に少なくとも部分的に基づいて、前記残りのパリティビットの１つまたは複数のビット値を変更することと、
を備える、請求項１に記載の方法。
【請求項７】
前記残りのパリティビットの前記１つまたは複数のビット値を変更することは、
前記第１のパリティビットによって影響を受ける１つまたは複数の残りのパリティビットを識別することと、
前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットの各々のそれぞれのビット値を変更することと、
を備える、請求項６に記載の方法。
【請求項８】
前記所与のＬＤＰＣ符号に関連付けられる第２のパリティ検査行列の線形独立行を使用して第１のパリティ検査行列を生成することと、ここにおいて、前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットを識別することは、前記第１のパリティ検査行列に少なくとも部分的に基づいて、前記１つまたは複数の残りのパリティビットを識別することを含む、
をさらに備える、請求項７に記載の方法。
【請求項９】
前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットを識別することは、
ルックアップテーブルにおいて前記１つまたは複数の残りのパリティビットを検索すること、
を備える、請求項８に記載の方法。
【請求項１０】
プログラム命令を含むコンピュータ可読記憶媒体であって、前記命令は、通信デバイス内で提供されるプロセッサによって実行されるとき、前記デバイスに、
コードワード（ｃ）に符号化されるべき情報ビットのセットを受信することと、ここにおいて、前記コードワードは、前記情報ビットのセットおよびパリティビットのセットを含む、
前記パリティビットのセットにおける第１のパリティビットに第１のビット値を割り当てることと、
前記第１のパリティビットに割り当てられた前記第１のビット値に少なくとも部分的に基づいて、前記パリティビットのセットにおける残りのパリティビットを符号化することと、
を行わせ、前記残りのパリティビットを符号化するための前記プログラム命令の実行は、
前記コードワードが所与のＬＤＰＣ符号に関して有効なコードワードであるかどうかを決定することと、
前記コードワードが有効なコードワードでない場合、前記コードワードの１つまたは複数のビット値を変更することと、
を前記デバイスに行わせる、コンピュータ可読記憶媒体。
【請求項１１】
前記残りのパリティビットは、低密度パリティ検査（ＬＤＰＣ）符号のためのパリティ検査行列（Ｈ）および前記情報ビットのセットを使用して符号化される、請求項１０に記載のコンピュータ可読記憶媒体。
【請求項１２】
前記パリティ検査行列の線形独立行を使用して、新たなパリティ検査行列（Ｈ０）を生成すること、
を前記デバイスに行わせるプログラム命令をさらに備える、請求項１１に記載のコンピュータ可読記憶媒体。
【請求項１３】
前記残りのパリティビットを符号化するための前記プログラム命令の実行は、
式：Ｈ０ｃ＝０を使用して、前記残りのパリティビットの各々の値を反復して求めること、
を前記デバイスに行わせる、請求項１２に記載のコンピュータ可読記憶媒体。
【請求項１４】
前記残りのパリティビットの各々の値を反復して求めるための前記プログラム命令の実行は、
反復毎に、最大でも１つの未知のパリティビットを含む１つまたは複数のベクトル方程式を解くことと、
を前記デバイスに行わせる、請求項１３に記載のコンピュータ可読記憶媒体。
【請求項１５】
前記コードワードの前記１つまたは複数のビット値を変更するための前記プログラム命令の実行は、
前記第１のパリティビットに第２のビット値を割り当てることと、ここにおいて、前記第２のビット値は前記第１のビット値とは異なる、
前記第２のビット値に少なくとも部分的に基づいて、前記残りのパリティビットの１つまたは複数のビット値を変更することと、
を前記デバイスに行わせる、請求項１０に記載のコンピュータ可読記憶媒体。
【請求項１６】
前記残りのパリティビットの前記１つまたは複数のビット値を変更するための前記プログラム命令の実行は、
前記第１のパリティビットによって影響を受ける１つまたは複数の残りのパリティビットを識別することと、
前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットの各々のそれぞれのビット値を変更することと、
を前記デバイスに行わせる、請求項１５に記載のコンピュータ可読記憶媒体。
【請求項１７】
前記所与のＬＤＰＣ符号に関連付けられる第２のパリティ検査行列の線形独立行を使用して第１のパリティ検査行列を生成すること、ここにおいて、前記１つまたは複数の残りのパリティビットを識別するための前記プログラム命令は、前記第１のパリティ検査行列に少なくとも部分的に基づいて、前記１つまたは複数の残りのパリティビットを識別するための命令を含む、
を前記デバイスに行わせるプログラム命令をさらに備える、請求項１６に記載のコンピュータ可読記憶媒体。
【請求項１８】
前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットを識別するための前記プログラム命令の実行は、
ルックアップテーブルにおいて前記１つまたは複数の残りのパリティビットを検索すること、
を前記デバイスに行わせる、請求項１７に記載のコンピュータ可読記憶媒体。
【請求項１９】
通信デバイスであって、
コードワード（ｃ）に符号化されるべき情報ビットのセットを記憶するためのメモリ要素と、ここにおいて、前記コードワードは、前記情報ビットのセットおよびパリティビットのセットを含む、
前記パリティビットのセットにおける第１のパリティビットに第１のビット値を割り当てることと、
前記第１のパリティビットに割り当てられた前記第１のビット値に少なくとも部分的に基づいて、前記パリティビットのセットにおける残りのパリティビットを符号化することと、
を行うための１つまたは複数のプロセッサと、
を備え、前記１つまたは複数のプロセッサは、
前記コードワードが所与のＬＤＰＣ符号に関して有効なコードワードであるかどうかを決定することと、
前記コードワードが有効なコードワードでない場合、前記コードワードの１つまたは複数のビット値を変更することと、
によって前記残りのパリティビットを符号化するためのものである、通信デバイス。
【請求項２０】
前記残りのパリティビットは、低密度パリティ検査（ＬＤＰＣ）符号のためのパリティ検査行列（Ｈ）および前記情報ビットのセットを使用して符号化される、請求項１９に記載のデバイス。
【請求項２１】
前記１つまたは複数のプロセッサはさらに、
前記パリティ検査行列の線形独立行を使用して、新たなパリティ検査行列（Ｈ０）を生成すること、
のためのものである、請求項２０に記載のデバイス。
【請求項２２】
前記１つまたは複数のプロセッサは、
式：Ｈ０ｃ＝０を使用して、前記残りのパリティビットの各々の値を反復して求めること、
によって前記残りのパリティビットを符号化するためのものである、請求項２１に記載のデバイス。
【請求項２３】
前記１つまたは複数のプロセッサは、
反復毎に、最大でも１つの未知のパリティビットを含む１つまたは複数のベクトル方程式を解くこと、
によって前記残りのパリティビットの各々の値を反復して求めるためのものである、請求項２２に記載のデバイス。
【請求項２４】
前記１つまたは複数のプロセッサは、
前記第１のパリティビットに第２のビット値を割り当てることと、ここにおいて、前記第２のビット値は前記第１のビット値とは異なる、
前記第２のビット値に少なくとも部分的に基づいて、前記残りのパリティビットの１つまたは複数のビット値を変更することと、
によって前記コードワードの前記１つまたは複数のビット値を変更するためのものである、請求項１９に記載のデバイス。
【請求項２５】
前記１つまたは複数のプロセッサは、
前記第１のパリティビットによって影響を受ける１つまたは複数の残りのパリティビットを識別することと、
前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットの各々のそれぞれのビット値を変更することと、
によって前記残りのパリティビットの前記１つまたは複数のビット値を変更するためのものである、請求項２４に記載のデバイス。
【請求項２６】
前記１つまたは複数のプロセッサはさらに、
前記所与のＬＤＰＣ符号に関連付けられる第２のパリティ検査行列の線形独立行を使用して第１のパリティ検査行列を生成することと、
前記第１のパリティ検査行列に少なくとも部分的に基づいて、前記１つまたは複数の残りのパリティビットを識別することによって、前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットを識別することと、
のためのものである、請求項２５に記載のデバイス。
【請求項２７】
前記１つまたは複数のプロセッサは、
ルックアップテーブルにおいて前記１つまたは複数の残りのパリティビットを検索すること、
によって、前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットを識別するためのものである、請求項２６に記載のデバイス。
【請求項２８】
前記デバイスは、１０ＧＢＡＳＥ−Ｔイーサネットシステムの一部である、請求項１９に記載のデバイス。
【請求項２９】
通信デバイスであって、
コードワード（ｃ）に符号化されるべき情報ビットのセットを受信するための手段と、ここにおいて、前記コードワードは、前記情報ビットのセットおよびパリティビットのセットを含む、
前記パリティビットのセットにおける第１のパリティビットに第１のビット値を割り当てるための手段と、
前記第１のパリティビットに割り当てられた前記第１のビット値に少なくとも部分的に基づいて、前記パリティビットのセットにおける残りのパリティビットを符号化するための手段と、
を備え、前記残りのパリティビットを符号化するための手段は、
前記コードワードが所与のＬＤＰＣ符号に関して有効なコードワードであるかどうかを決定することと、
前記コードワードが有効なコードワードでない場合、前記コードワードの１つまたは複数のビット値を変更することと、
のためのものである、通信デバイス。
【請求項３０】
前記残りのパリティビットは、低密度パリティ検査（ＬＤＰＣ）符号のためのパリティ検査行列（Ｈ）および前記情報ビットのセットを使用して符号化される、請求項２９に記載のデバイス。
【請求項３１】
前記パリティ検査行列Ｈの線形独立行を使用して、新たなパリティ検査行列（Ｈ０）を生成するための手段、
をさらに備える、請求項３０に記載のデバイス。
【請求項３２】
前記残りのパリティビットを符号化するための手段は、
式：Ｈ０ｃ＝０を使用して、前記残りのパリティビットの各々の値を反復して求めること、
のためのものである、請求項３１に記載のデバイス。
【請求項３３】
前記残りのパリティビットの各々の値を反復して求めるための手段は、
反復毎に、最大でも１つの未知のパリティビットを含む１つまたは複数のベクトル方程式を解くこと、
のためのものである、請求項３２に記載のデバイス。
【請求項３４】
前記残りのパリティビットを符号化するための手段はさらに、
前記第１のパリティビットに第２のビット値を割り当てることと、ここにおいて、前記第２のビット値は前記第１のビット値とは異なる、
前記第２のビット値に少なくとも部分的に基づいて、前記残りのパリティビットの１つまたは複数のビット値を変更することと、
のためのものである、請求項２９に記載のデバイス。
【請求項３５】
前記残りのパリティビットを符号化するための手段はさらに、
前記第１のパリティビットによって影響を受ける１つまたは複数の残りのパリティビットを識別することと、
前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットの各々のそれぞれのビット値を変更することと、
のためのものである、請求項３４に記載のデバイス。
【請求項３６】
前記所与のＬＤＰＣ符号に関連付けられる第２のパリティ検査行列の線形独立行を使用して第１のパリティ検査行列を生成するための手段と、ここにおいて、前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットを識別するための手段は、前記第１のパリティ検査行列に少なくとも部分的に基づいて、前記１つまたは複数の残りのパリティビットを識別するための手段を含む、
をさらに備える、請求項３５に記載のデバイス。
【請求項３７】
前記デバイスは、１０ＧＢＡＳＥ−Ｔイーサネットシステムの一部である、請求項２９に記載のデバイス。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００６１
【補正方法】変更
【補正の内容】
【００６１】
[0053]前の詳述では、本実施形態は、その特定の例示的な実施形態を参照して説明されてきた。しかしながら、添付の特許請求の範囲で述べられている開示のより広い範囲から逸脱することなく、様々な修正および変更がそれになされることは明らかであろう。したがって、明細書および図面は、限定的な意味というよりむしろ実例的な意味の中で考慮されるものとする。例えば、図３、５、および６のフロー図において描写された方法のステップは他の適切な順序で実行され得、複数のステップは単一のステップに結合され得、および／またはいくつかのステップは省略されうる。
以下に本願発明の当初の特許請求の範囲に記載された発明を付記する。
［Ｃ１］
データ符号化の方法であって、
コードワード（Ｃ）に符号化されるべき情報ビットのセットを受信することと、ここにおいて、前記コードワードは、前記情報ビットのセットおよびパリティビットのセットを含む、
前記パリティビットのセットにおける第１のパリティビットに第１のビット値を割り当てることと、
前記第１のパリティビットに割り当てられた前記第１のビット値に少なくとも部分的に基づいて、前記パリティビットのセットにおける残りのパリティビットを符号化することと、
を備える、データ符号化の方法。
［Ｃ２］
前記残りのパリティビットは、低密度パリティ検査（ＬＤＰＣ）符号のためのパリティ検査行列（Ｈ）および前記情報ビットのセットを使用して符号化される、Ｃ１に記載の方法。
［Ｃ３］
前記パリティ検査行列の線形独立行を使用して、新たなパリティ検査行列（Ｈ０）を生成すること、
をさらに備える、Ｃ２に記載の方法。
［Ｃ４］
前記残りのパリティビットを符号化することは、
式：Ｈ０Ｃ＝０を使用して、前記残りのパリティビットの各々の値を反復して求めること、
を備える、Ｃ３に記載の方法。
［Ｃ５］
前記残りのパリティビットの各々の値を反復して求めることは、
反復毎に、最大でも１つの未知のパリティビットを含む１つまたは複数のベクトル方程式を解くことと、
を備える、Ｃ４に記載の方法。
［Ｃ６］
前記残りのパリティビットを符号化することは、
前記コードワードが所与のＬＤＰＣ符号に関して有効なコードワードであるかどうかを決定することと、
前記コードワードが有効なコードワードでない場合、前記コードワードの１つまたは複数のビット値を変更することと、
を備える、Ｃ１に記載の方法。
［Ｃ７］
前記コードワードの前記１つまたは複数のビット値を変更することは、
前記第１のパリティビットに第２のビット値を割り当てることと、ここにおいて、前記第２のビット値は前記第１のビット値とは異なる、
前記第２のビット値に少なくとも部分的に基づいて、前記残りのパリティビットの１つまたは複数のビット値を変更することと、
を備える、Ｃ６に記載の方法。
［Ｃ８］
前記残りのパリティビットの前記１つまたは複数のビット値を変更することは、
前記第１のパリティビットによって影響を受ける１つまたは複数の残りのパリティビットを識別することと、
前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットの各々のそれぞれのビット値を変更することと、
を備える、Ｃ７に記載の方法。
［Ｃ９］
前記所与のＬＤＰＣ符号に関連付けられる第２のパリティ検査行列の線形独立行を使用して第１のパリティ検査行列を生成することと、ここにおいて、前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットを識別することは、前記第１のパリティ検査行列に少なくとも部分的に基づいて、前記１つまたは複数の残りのパリティビットを識別することを含む、
をさらに備える、Ｃ８に記載の方法。
［Ｃ１０］
前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットを識別することは、
ルックアップテーブルにおいて前記１つまたは複数の残りのパリティビットを検索すること、
を備える、Ｃ９に記載の方法。
［Ｃ１１］
プログラム命令を含むコンピュータ可読記憶媒体であって、前記命令は、通信デバイス内で提供されるプロセッサによって実行されるとき、前記デバイスに、
コードワード（Ｃ）に符号化されるべき情報ビットのセットを受信することと、ここにおいて、前記コードワードは、前記情報ビットのセットおよびパリティビットのセットを含む、
前記パリティビットのセットにおける第１のパリティビットに第１のビット値を割り当てることと、
前記第１のパリティビットに割り当てられた前記第１のビット値に少なくとも部分的に基づいて、前記パリティビットのセットにおける残りのパリティビットを符号化することと、
を行わせる、コンピュータ可読記憶媒体。
［Ｃ１２］
前記残りのパリティビットは、低密度パリティ検査（ＬＤＰＣ）符号のためのパリティ検査行列（Ｈ）および前記情報ビットのセットを使用して符号化される、Ｃ１１に記載のコンピュータ可読記憶媒体。
［Ｃ１３］
前記パリティ検査行列の線形独立行を使用して、新たなパリティ検査行列（Ｈ０）を生成すること、
を前記デバイスに行わせるプログラム命令をさらに備える、Ｃ１２に記載のコンピュータ可読記憶媒体。
［Ｃ１４］
前記残りのパリティビットを符号化するための前記プログラム命令の実行は、
式：Ｈ０Ｃ＝０を使用して、前記残りのパリティビットの各々の値を反復して求めること、
を前記デバイスに行わせる、Ｃ１３に記載のコンピュータ可読記憶媒体。
［Ｃ１５］
前記残りのパリティビットの各々の値を反復して求めるための前記プログラム命令の実行は、
反復毎に、最大でも１つの未知のパリティビットを含む１つまたは複数のベクトル方程式を解くことと、
を前記デバイスに行わせる、Ｃ１４に記載のコンピュータ可読記憶媒体。
［Ｃ１６］
前記残りのパリティビットを符号化するための前記プログラム命令の実行は、
前記コードワードが所与のＬＤＰＣ符号に関して有効なコードワードであるかどうかを決定することと、
前記コードワードが有効なコードワードでない場合、前記コードワードの１つまたは複数のビット値を変更することと、
を前記デバイスに行わせる、Ｃ１１に記載のコンピュータ可読記憶媒体。
［Ｃ１７］
前記コードワードの前記１つまたは複数のビット値を変更するための前記プログラム命令の実行は、
前記第１のパリティビットに第２のビット値を割り当てることと、ここにおいて、前記第２のビット値は前記第１のビット値とは異なる、
前記第２のビット値に少なくとも部分的に基づいて、前記残りのパリティビットの１つまたは複数のビット値を変更することと、
を前記デバイスに行わせる、Ｃ１６に記載のコンピュータ可読記憶媒体。
［Ｃ１８］
前記残りのパリティビットの前記１つまたは複数のビット値を変更するための前記プログラム命令の実行は、
前記第１のパリティビットによって影響を受ける１つまたは複数の残りのパリティビットを識別することと、
前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットの各々のそれぞれのビット値を変更することと、
を前記デバイスに行わせる、Ｃ１７に記載のコンピュータ可読記憶媒体。
［Ｃ１９］
前記所与のＬＤＰＣ符号に関連付けられる第２のパリティ検査行列の線形独立行を使用して第１のパリティ検査行列を生成すること、ここにおいて、前記１つまたは複数の残りのパリティビットを識別するための前記プログラム命令は、前記第１のパリティ検査行列に少なくとも部分的に基づいて、前記１つまたは複数の残りのパリティビットを識別するための命令を含む、
を前記デバイスに行わせるプログラム命令をさらに備える、Ｃ１８に記載のコンピュータ可読記憶媒体。
［Ｃ２０］
前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットを識別するための前記プログラム命令の実行は、
ルックアップテーブルにおいて前記１つまたは複数の残りのパリティビットを検索すること、
を前記デバイスに行わせる、Ｃ１９に記載のコンピュータ可読記憶媒体。
［Ｃ２１］
通信デバイスであって、
コードワード（Ｃ）に符号化されるべき情報ビットのセットを記憶するためのメモリ要素と、ここにおいて、前記コードワードは、前記情報ビットのセットおよびパリティビットのセットを含む、
前記パリティビットのセットにおける第１のパリティビットに第１のビット値を割り当てることと、
前記第１のパリティビットに割り当てられた前記第１のビット値に少なくとも部分的に基づいて、前記パリティビットのセットにおける残りのパリティビットを符号化することと、
を行うための１つまたは複数のプロセッサと、
を備える、通信デバイス。
［Ｃ２２］
前記残りのパリティビットは、低密度パリティ検査（ＬＤＰＣ）符号のためのパリティ検査行列（Ｈ）および前記情報ビットのセットを使用して符号化される、Ｃ２１に記載のデバイス。
［Ｃ２３］
前記１つまたは複数のプロセッサはさらに、
前記パリティ検査行列の線形独立行を使用して、新たなパリティ検査行列（Ｈ０）を生成すること、
のためのものである、Ｃ２２に記載のデバイス。
［Ｃ２４］
前記１つまたは複数のプロセッサは、
式：Ｈ０Ｃ＝０を使用して、前記残りのパリティビットの各々の値を反復して求めること、
によって前記残りのパリティビットを復号するためのものである、Ｃ２３に記載のデバイス。
［Ｃ２５］
前記１つまたは複数のプロセッサは、
反復毎に、最大でも１つの未知のパリティビットを含む１つまたは複数のベクトル方程式を解くこと、
によって前記残りのパリティビットの各々の値を反復して求めるためのものである、Ｃ２４に記載のデバイス。
［Ｃ２６］
前記１つまたは複数のプロセッサは、
前記コードワードが所与のＬＤＰＣ符号に関して有効なコードワードであるかどうかを決定することと、
前記コードワードが有効なコードワードでない場合、前記コードワードの１つまたは複数のビット値を変更することと、
によって前記残りのパリティビットを符号化するためのものである、Ｃ２１に記載のデバイス。
［Ｃ２７］
前記１つまたは複数のプロセッサは、
前記第１のパリティビットに第２のビット値を割り当てることと、ここにおいて、前記第２のビット値は前記第１のビット値とは異なる、
前記第２のビット値に少なくとも部分的に基づいて、前記残りのパリティビットの１つまたは複数のビット値を変更することと、
によって前記コードワードの前記１つまたは複数のビット値を変更するためのものである、Ｃ２６に記載のデバイス。
［Ｃ２８］
前記１つまたは複数のプロセッサは、
前記第１のパリティビットによって影響を受ける１つまたは複数の残りのパリティビットを識別することと、
前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットの各々のそれぞれのビット値を変更することと、
によって前記残りのパリティビットの前記１つまたは複数のビット値を変更するためのものである、Ｃ２７に記載のデバイス。
［Ｃ２９］
前記１つまたは複数のプロセッサはさらに、
前記所与のＬＤＰＣ符号に関連付けられる第２のパリティ検査行列の線形独立行を使用して第１のパリティ検査行列を生成することと、
前記第１のパリティ検査行列に少なくとも部分的に基づいて、前記１つまたは複数の残りのパリティビットを識別することによって、前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットを識別することと、
のためのものである、Ｃ２８に記載のデバイス。
［Ｃ３０］
前記１つまたは複数のプロセッサは、
ルックアップテーブルにおいて前記１つまたは複数の残りのパリティビットを検索すること、
によって、前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットを識別するためのものである、Ｃ２９に記載のデバイス。
［Ｃ３１］
前記デバイスは、１０ＧＢＡＳＥ−Ｔイーサネットシステムの一部である、Ｃ２１に記載のデバイス。
［Ｃ３２］
通信デバイスであって、
コードワード（Ｃ）に符号化されるべき情報ビットのセットを受信するための手段と、ここにおいて、前記コードワードは、前記情報ビットのセットおよびパリティビットのセットを含む、
前記パリティビットのセットにおける第１のパリティビットに第１のビット値を割り当てるための手段と、
前記第１のパリティビットに割り当てられた前記第１のビット値に少なくとも部分的に基づいて、前記パリティビットのセットにおける残りのパリティビットを符号化するための手段と、
を備える、通信デバイス。
［Ｃ３３］
前記残りのパリティビットは、低密度パリティ検査（ＬＤＰＣ）符号のためのパリティ検査行列（Ｈ）および前記情報ビットのセットを使用して符号化される、Ｃ３２に記載のデバイス。
［Ｃ３４］
前記パリティ検査行列Ｈの線形独立行を使用して、新たなパリティ検査行列（Ｈ０）を生成するための手段、
をさらに備える、Ｃ３３に記載のデバイス。
［Ｃ３５］
前記残りのパリティビットを符号化するための手段は、
式：Ｈ０Ｃ＝０を使用して、前記残りのパリティビットの各々の値を反復して求めること、
のためのものである、Ｃ３４に記載のデバイス。
［Ｃ３６］
前記残りのパリティビットの各々の値を反復して求めるための手段は、
反復毎に、最大でも１つの未知のパリティビットを含む１つまたは複数のベクトル方程式を解くこと、
のためのものである、Ｃ３５に記載のデバイス。
［Ｃ３７］
前記残りのパリティビットを符号化するための手段は、
前記コードワードが所与のＬＤＰＣ符号に関して有効なコードワードであるかどうかを決定することと、
前記コードワードが有効なコードワードでない場合、前記コードワードの１つまたは複数のビット値を変更することと、
のためのものである、Ｃ３２に記載のデバイス。
［Ｃ３８］
前記残りのパリティビットを符号化するための手段はさらに、
前記第１のパリティビットに第２のビット値を割り当てることと、ここにおいて、前記第２のビット値は前記第１のビット値とは異なる、
前記第２のビット値に少なくとも部分的に基づいて、前記残りのパリティビットの１つまたは複数のビット値を変更することと、
のためのものである、Ｃ３７に記載のデバイス。
［Ｃ３９］
前記残りのパリティビットを符号化するための手段はさらに、
前記第１のパリティビットによって影響を受ける１つまたは複数の残りのパリティビットを識別することと、
前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットの各々のそれぞれのビット値を変更することと、
のためのものである、Ｃ３８に記載のデバイス。
［Ｃ４０］
前記所与のＬＤＰＣ符号に関連付けられる第２のパリティ検査行列の線形独立行を使用して第１のパリティ検査行列を生成するための手段と、ここにおいて、前記第１のパリティビットによって影響を受ける前記１つまたは複数の残りのパリティビットを識別するための手段は、前記第１のパリティ検査行列に少なくとも部分的に基づいて、前記１つまたは複数の残りのパリティビットを識別するための手段を含む、
をさらに備える、Ｃ３９に記載のデバイス。
［Ｃ４１］
前記デバイスは、１０ＧＢＡＳＥ−Ｔイーサネットシステムの一部である、Ｃ３２に記載のデバイス。
【国際調査報告】
2016521064.tif 000018
2016521064.tif 000019