(57)【特許請求の範囲】
【請求項１】
１組の情報ビットを受信することと、
マッチトリフトＬＤＰＣ符号に基づいてコードワードを生成するために、低密度パリティ検査（ＬＤＰＣ）符号化演算を前記１組の情報ビットに実行することと、ここにおいて、マッチトリフティングが可換リフティング群に基づく、ここにおいて、前記ＬＤＰＣ符号が、いくつかのパリティビットと、前記パリティビットの値を決定するための副行列とを含む、ここにおいて、
前記リフティング群の位数（Ｚ）が前記リフティングのサイズに対応し、
前記副行列の行列式が、ｇａ＋（ｇ０＋ｇＬ）Ｐの形式の多項式であり、ここで、
ｇ０は前記群の単位元であり、
【数１】
0005976960.tif 000056
であり、
正整数ｋおよびＬに対して、Ｚ＝２ｋ×Ｌであり、
非負のｌ＜ｋに対して、ａ＝２ｌ×Ｌであり、
Ｐは、前記リフティング群に関連付けられた２値群環の任意の非ゼロ元である、を備えるデータ符号化の方法。
【請求項２】
前記リフティング群が巡回群であり、ここにおいて、
ｇｉはｘｉと同一に扱うことができ、
前記副行列の前記行列式が、ｘａ＋（１＋ｘＬ）Ｐ（ｘ）の形式を取り、ここで、Ｐ（ｘ）は少なくとも２つの項を有し、２ｋＬ＝０モジュロＺである、請求項１に記載の方法。
【請求項３】
前記副行列が、その行および列の置換を除いて、上三角である、請求項１に記載の方法。
【請求項４】
前記副行列の第１の副対角線より下の元が０に等しい、請求項３に記載の方法。
【請求項５】
プログラム命令を備える非一時的コンピュータ可読記憶媒体であって、前記プログラム命令が、通信デバイス内に設けられたプロセッサによって実行されたとき、前記プログラム命令により、前記デバイスが、
１組の情報ビットを受信し、
マッチトリフトＬＤＰＣ符号に基づいてコードワードを生成するために、ＬＤＰＣ符号化演算を前記１組の情報ビットに実行する、ここにおいて、マッチトリフティングが可換リフティング群に基づく、ここにおいて、前記ＬＤＰＣ符号が、いくつかのパリティビットと、前記パリティビットの値を決定するための副行列とを含む、ここにおいて、
前記リフティング群の位数（Ｚ）が前記リフティングのサイズに対応し、
前記副行列の行列式が、ｇａ＋（ｇ０＋ｇＬ）Ｐの形式の多項式であり、ここで、
ｇ０は前記群の単位元であり、
【数２】
0005976960.tif 000057
であり、
正整数ｋおよびＬに対して、Ｚ＝２ｋ×Ｌであり、
非負のｌ＜ｋに対して、ａ＝２ｌ×Ｌであり、
Ｐは、前記リフティング群に関連付けられた２値群環の任意の非ゼロ元である、非一時的コンピュータ可読記憶媒体。
【請求項６】
前記リフティング群が巡回群であり、ここにおいて、
ｇｉはｘｉと同一に扱うことができ、
前記副行列の前記行列式が、ｘａ＋（１＋ｘＬ）Ｐ（ｘ）の形式を取り、ここで、Ｐ（ｘ）は少なくとも２つの項を有し、２ｋＬ＝０モジュロＺである、請求項５に記載の非一時的コンピュータ可読記憶媒体。
【請求項７】
前記副行列が、その行および列の置換を除いて、上三角である、請求項５に記載の非一時的コンピュータ可読記憶媒体。
【請求項８】
前記副行列の第１の副対角線より下の元が０に等しい、請求項７に記載の非一時的コンピュータ可読記憶媒体。
【請求項９】
１組の情報ビットを記憶するメモリと、
符号器と、ここにおいて、前記符号器が、
マッチトリフトＬＤＰＣ符号に基づいてコードワードを生成するために、ＬＤＰＣ符号化演算を前記１組の情報ビットに実行する、ここにおいて、マッチトリフティングが可換リフティング群に基づく、ここにおいて、前記ＬＤＰＣ符号が、いくつかのパリティビットと、前記パリティビットの値を決定するための副行列とを含む、ここにおいて、
前記リフティング群の位数（Ｚ）が前記リフティングのサイズに対応し、
前記副行列の行列式が、ｇａ＋（ｇ０＋ｇＬ）Ｐの形式の多項式であり、ここで、
ｇ０は前記群の単位元であり、
【数３】
0005976960.tif 000058
であり、
正整数ｋおよびＬに対して、Ｚ＝２ｋ×Ｌであり、
非負のｌ＜ｋに対して、ａ＝２ｌ×Ｌであり、
Ｐは、前記リフティング群に関連付けられた２値群環の任意の非ゼロ元である、を備える通信デバイス。
【請求項１０】
前記リフティング群が巡回群であり、ここにおいて、
ｇｉはｘｉと同一に扱うことができ、
前記副行列の前記行列式が、ｘａ＋（１＋ｘＬ）Ｐ（ｘ）の形式を取り、ここで、Ｐ（ｘ）は少なくとも２つの項を有し、２ｋＬ＝０モジュロＺである、請求項９に記載のデバイス。
【請求項１１】
前記副行列が、その行および列の置換を除いて、上三角である、請求項９に記載のデバイス。
【請求項１２】
前記副行列の第１の副対角線より下の元が０に等しい、請求項１１に記載のデバイス。
【請求項１３】
１組の情報ビットを受信するための手段と、
マッチトリフトＬＤＰＣ符号に基づいてコードワードを生成するために、ＬＤＰＣ符号化演算を前記１組の情報ビットに実行するための手段と、ここにおいて、マッチトリフティングが可換リフティング群に基づく、ここにおいて、前記ＬＤＰＣ符号が、いくつかのパリティビットと、前記パリティビットの値を決定するための副行列とを含む、ここにおいて、
前記リフティング群の位数（Ｚ）が前記リフティングのサイズに対応し、
前記副行列の行列式が、ｇａ＋（ｇ０＋ｇＬ）Ｐの形式の多項式であり、ここで、
ｇ０は前記群の単位元であり、
【数４】
0005976960.tif 000059
であり、
正整数ｋおよびＬに対して、Ｚ＝２ｋ×Ｌであり、
非負のｌ＜ｋに対して、ａ＝２ｌ×Ｌであり、
Ｐは、前記リフティング群に関連付けられた２値群環の任意の非ゼロ元である、を備える符号器。
【発明の詳細な説明】
【技術分野】
【０００１】
[0001]本実施形態は、一般に、通信およびデータ記憶システムに関し、詳細には、ＬＤＰＣ符号を使用する通信およびデータ記憶システムに関する。
【背景技術】
【０００２】
[0002]多くの通信システムは誤り訂正符号を使用する。詳細には、誤り訂正符号は、データストリームに冗長性を導入することによってこれらのシステムへの情報転送の本質的な不信頼性を補償する。低密度パリティ検査（ＬＤＰＣ）符号は、反復コーディング方式を使用する特定のタイプの誤り訂正符号である。ＬＤＰＣ符号は、二部グラフ（しばしば「タナーグラフ」と呼ばれる）によって表すことができ、１組の変数ノードが、コードワードのビットに対応し、１組の検査ノードが、符号を定義する１組のパリティ検査制約に対応する。変数ノードおよび検査ノードがグラフのエッジで接続される場合、それらは「隣接しているもの」と見なされる。検査ノードごとに、すべての隣接する変数ノードに関連するビットが合計されて、０モジュロ２になる（すなわち、それらは偶数個の１を含む）ときおよびそのときに限って、変数ノードシーケンスと１対１に関連付けられたビットシーケンスは、有効なコードワードである。
【０００３】
[0003]たとえば、図１Ａは、例示的なＬＤＰＣ符号を表す二部グラフ１００を示す。二部グラフ１００は、４つの検査ノード１２０（正方形で表された）に接続された１組の５つの変数ノード１１０（円で表された）を含む。グラフ１００のエッジは、変数ノード１１０を検査ノード１２０に接続する。図１Ｂは、二部グラフ１００の行列表現１５０を示す。行列表現１５０は、パリティ検査行列Ｈおよびコードワードベクトルｘを含み、ここで、ｘ１〜ｘ５はコードワードｘのビットを表す。より詳細には、コードワードベクトルｘは、Ｈｘ＝０のときおよびそのときに限って、有効なコードワードを表す。図２は、たとえば、本願の譲受人が所有する米国特許第７，５５２，０９７号に説明されているように、図１Ａのグラフの３つのコピーを作る効果をグラフ式に示す。３つのコピーは、コピーの間の同様なエッジを置換することによって相互接続され得る。置換が巡回置換に制限される場合、結果として生じるグラフは、リフティングＺ＝３による擬似巡回ＬＤＰＣに対応する。３つのコピーが作られたオリジナルのグラフは、本明細書では基礎グラフ（base graph）と呼ばれる。
【０００４】
[0004]受信されたＬＤＰＣコードワードは、オリジナルのコードワードの再構築されたバージョンを生成するために復号され得る。誤りがない場合、または訂正可能な誤りの場合には、復号化は、符号化されたオリジナルのデータユニットを回復するために使用され得る。ＬＤＰＣ復号器は、一般に、エッジに沿って、二部グラフ１００内でメッセージを交換し、入来メッセージに基づいてノードで計算を実行することによりこれらのメッセージを更新することによって動作する。たとえば、グラフ１００の各変数ノード１１０は、最初に、通信チャネルからの観察によって決定されるような関連するビット値の推定を示す「ソフトビット」（たとえば、コードワードの受信されたビットを表す）が供給され得る。これらのソフトビットを使用して、ＬＤＰＣ復号器は、メモリからメッセージまたはその一部分を反復して読み出し、更新されたメッセージまたはその一部分をメモリに戻して書き込むことによってメッセージを更新することができる。更新演算は、一般に、対応するＬＤＰＣ符号のパリティ検査制約に基づく。リフトされたＬＤＰＣ符号のための実施態様では、同様のエッジ上のメッセージは、多くの場合、並列に処理される。
【０００５】
[0005]多くの実用的なＬＤＰＣ符号設計は、符号化および復号化演算で高並列性をサポートするために、大きいリフティングファクタ（lifting factor）および比較的小さい基礎グラフをもつ擬似巡回構成を使用する。多くのＬＤＰＣ符号は、さらに、その構成に次数２の変数ノードのチェーンを使用する。時々蓄積構造（accumulate structure）と呼ばれるそのような次数２の変数ノードチェーンは、簡単な符号化および良好な性能をもたらす。巡回リフティングに基づくＬＤＰＣ符号設計は、多項式モジュロの環の上の符号として解釈することができ、２値多項式モジュロＸZ−１とすることができ、ここで、Ｚはリフティングサイズ（たとえば、擬似巡回符号における巡回のサイズ）である。それにより、そのような符号の符号化は、多くの場合、この環における代数演算として解釈され得る。
【発明の概要】
【０００６】
[0006]本概要は、発明を実施するための形態において以下でさらに説明する概念の選択を簡略化された形で紹介するために与えるものである。本概要は、請求する主題の主要な特徴または本質的特徴を識別するものではなく、請求する主題の範囲を限定するものでもない。
【０００７】
[0007]多くのＬＤＰＣ符号設計は、並列性をサポートするために巡回リフティングを使用する。加えて、多くのＬＤＰＣ設計は、簡単な符号化をサポートするために次数２の変数ノードの蓄積構造を使用したが、その理由は、それらが良好な性能をもつ符号をもたらすからである。しかしながら、非常に低い誤り率を目標とするコーディング方式では、大きい蓄積構造は高いエラーフロアをもたらすという点で問題となることがある。したがって、いくつかのコーディング方式の性能目標は、蓄積構造を使用する巡回リフト設計を用いて達成することが困難である。エラーフロアは、累積チェーン中の変数ノードのうちのいくつかの次数を増加させるか、または、一般に、グラフ中の変数ノードの次数を増加させることによって低下され、それは、改善された性能を与えることができる。しかしながら、そのようにすることは、一般に、符号化プロセスを複雑にする。それにより、より高い次数の変数ノードをサポートしながら、符号化の簡単さを保持する、蓄積構造を変更する方法を見いだすことが望ましい。
【０００８】
[0008]巡回リフティングに基づくＬＤＰＣ符号設計は、多項式モジュロｘZ−１の環の上の符号として解釈することができ、ここで、Ｚはリフティングサイズ（たとえば、擬似巡回符号における巡回のサイズ）である。そのような符号の符号化は、多くの場合、この環の行列方程式を解くことに還元する。蓄積構造の簡単な符号化は、符号化式に含まれる符号化行列の簡単な可逆性となって現れる。追加として、略上三角（または下三角）である符号化行列により、パリティビットの多くが、後退代入（back substitution）によって決定され得る。後退代入プロセスを開始することは、いくつかの初期ビットについて解くことを含む。この初期のステップの困難さは、符号化行列の可逆性に密接に関係付けられる。通常使用される蓄積構造は、主として符号化行列の対角線および副対角線にのみ非ゼロエントリを有する、略二重対角線である行列をもたらす。累積チェーンを使用するいくつかの符号化構造では、より高い次数、典型的には次数３である行列の１つの列が存在する。しかしながら、非常に低い誤り率を目標とするコーディング方式では、大きい蓄積構造は高いエラーフロアをもたらすという点で問題となることがある。エラーフロアは、累積チェーン中の変数ノードのうちのいくつかの次数を増加させるか、または、一般に、グラフ中の変数ノードの次数を増加させることによって低下され、それは、改善された性能を与えることができる。しかしながら、そのようにすることは、一般に、符号化プロセスを複雑にする。
【０００９】
[0009]それにより、より高い次数の変数ノードをサポートしながら、符号化の簡単さを保持するように、蓄積構造を変更することが望ましい。本明細書の実施形態は、簡単な符号化を与える変更された符号化構造を提供する。いくつかの実施形態は、変更された累積チェーンと見なされ得る構造を有し、チェーン中のいくつかの変数ノードは、追加のエッジを有し、したがって、２よりも高い次数のものである。それにより、これらの符号のための符号化行列は二重対角線構造を有するが、対角線より上に追加の非ゼロ元が存在し得る。その結果として、次数が少なくとも３である追加の列が存在し得る巡回リフティング値を注意深く選択することによって、追加のエッジのうちのいくつかは、符号の基礎をなすグラフィック表示の大きいガース（girth）を維持し、それによって、低いエラーフロア性能をサポートしながら、符号化演算を簡単にするように選ばれる。説明された二重対角線および略上三角構造は、行列の列および行の適切な配列によってのみ明確に観察され、構造は、それが目に見えるようには明白でない他の配列の場合でさえ存在することが当業者によって理解されるだろう。
【００１０】
[0010]本実施形態は例として示されており、添付図面の図によって限定されるものではない。
【図面の簡単な説明】
【００１１】
【図１Ａ】[0011]例示のＬＤＰＣ符号のグラフ表示の図。
【図１Ｂ】例示のＬＤＰＣ符号の行列表示の図。
【図２】[0012]図１Ａのグラフの３つのコピーを作る効果をグラフ式に示す図。
【図３】[0013]いくつかの実施形態による通信システムを示す図。
【図４】[0014]いくつかの実施形態による通信デバイスのブロック図。
【図５】[0015]例示の擬似巡回ＬＤＰＣ符号のリフトされたパリティ検査行列表示のパリティビット部分を示す図。
【図６】[0016]別の例示の擬似巡回ＬＤＰＣ符号のリフトされたパリティ検査行列表示のパリティビット部分を示す図。
【図７】[0017]図１０に与えられたレートｒ＝２７／３０をもつ例示的なＬＤＰＣ符号のリフトされたパリティ検査行列表現のパリティビット部分を示す図。
【図８】[0018]図１１に与えられたレートｒ＝１３／１５をもつ例示的なＬＤＰＣ符号のリフトされたパリティ検査行列表現のパリティビット部分を示す図。
【図９】[0019]図１２に与えられたレートｒ＝２１／２８をもつ例示的なＬＤＰＣ符号のリフトされたパリティ検査行列表現のパリティビット部分を示す図。
【図１０】[0020]レートｒ＝２７／３０をもつＬＤＰＣ符号に関連する例示のパリティ検査行列を示す図。
【図１１】[0021]レートｒ＝１３／１５をもつＬＤＰＣ符号に関連する例示のパリティ検査行列を示す図。
【図１２】[0022]レートｒ＝２１／２８をもつＬＤＰＣ符号に関連する例示のパリティ検査行列を示す図。
【図１３】[0023]いくつかの実施形態による通信デバイスのブロック図。
【発明を実施するための形態】
【００１２】
[0024]以下の説明では、本開示の十分な理解を提供するために、特定の構成要素、回路、およびプロセスの例などの多数の特定の細部が記載されている。本明細書で使用する「結合された」という用語は、直接接続されていること、または１つまたは複数の介在する構成要素もしくは回路を通して接続されていることを意味する。さらに、以下の記述においておよび説明のために、特定の命名法が、本実施形態の十分な理解を提供するために記載されている。しかしながら、これらの特定の細部は本実施形態を実践するのに必要とされないことがあることが当業者には明白であろう。他の場合には、よく知られている回路およびデバイスは、本開示を不明瞭にしないためにブロック図の形式で示される。本明細書で説明する様々なバスにより供給される信号のいずれも他の信号と時分割多重され、１つまたは複数の共通バスにより供給され得る。追加として、回路要素間またはソフトウェアブロック間の相互接続は、バスとして、または単一の信号ラインとして示されることがある。バスの各々は、代替として、単一の信号ラインとすることができ、単一の信号ラインの各々は、代替として、バスとすることができ、単一のラインまたはバスは、構成要素間の通信のための無数の物理的または論理的機構のうちの任意の１つまたは複数を表すことができる。本実施形態は、本明細書に記載された具体的な例に限定されると見なされるものではなく、むしろ、添付された特許請求の範囲によって定義されたすべての実施形態を、それらの範囲内に含むものである。
【００１３】
[0025]図３は、いくつかの実施形態による通信システム３００を示す。送信機３１０はチャネル３２０に信号を送信し、受信機３３０はチャネル３２０から信号を受信する。送信機３１０および受信機３３０は、たとえば、コンピュータ、スイッチ、ルータ、ハブ、ゲートウェイ、および／または同様のデバイスであり得る。ある実施形態では、チャネル３２０はワイヤレスである。他の実施形態では、チャネル３２０は、有線リンク（たとえば、同軸ケーブルまたは他の物理的接続）である。
【００１４】
[0026]通信システム３００の様々な構成要素の欠陥は、信号障害の原因になり、それにより、信号劣化を引き起こすことがある。たとえば、チャネル３２０の欠陥はチャネル歪みを導入することがあり、チャネル歪みは、直線歪み、マルチパス効果、および／または付加白色ガウス雑音（ＡＷＧＮ）を含むことがある。潜在的な信号劣化と戦うために、送信機３１０および受信機３３０は、ＬＤＰＣ符号器および復号器を含むことができる。詳細には、送信機３１０は送出データにＬＤＰＣ符号化を実行して、オリジナルのデータの回復するために受信機３３０で後に復号され得る（たとえば、ＬＤＰＣ復号化演算によって）コードワードを生成することができる。いくつかの実施形態では、送信機３１０は、１つまたは複数の「パンクチャされた」ビットをもつＬＤＰＣ符号化コードワードを、たとえば、１つまたは複数のパンクチャされた変数ノードをもつＬＤＰＣ符号に基づいて、送信することができる。
【００１５】
[0027]リフティングは、より小さい基礎符号の多数のコピーから比較的大きいＬＤＰＣ符号を発生させるための技法である。たとえば、リフティングは、更新された基礎グラフのいくつか（Ｚ個）の並列コピーを生成し、次いで、基礎グラフの各コピーのエッジクラスタの置換により並列コピーを相互接続することによって、リフトされたＬＤＰＣ符号発生させることができる。エッジのクラスタは、基礎グラフのＺ並列コピーにおける基礎グラフ中の単一エッジのＺコピーの組を参照する。リフティングにより、ＬＤＰＣ符号は、並列符号化および／または復号化実施を使用するとともに、さらに、大きいＬＤＰＣ符号に一般に関連する記述の複雑さを低減して、実施され得るようになる。リフトされたＬＤＰＣ符号のより詳細な説明は、たとえば、２００８年３月１７日に出版された、Ｔｏｍ  ＲｉｃｈａｒｄｓｏｎおよびＲｕｅｄｉｇｅｒ  Ｕｒｂａｎｋｅによる「Ｍｏｄｅｒｎ  Ｃｏｄｉｎｇ  Ｔｈｅｏｒｙ」という書名の書籍で見いだすことができ、その全体が参照により明細書に組み込まれる。
【００１６】
[0028]リフティングサイズＺをもつコードワードを処理する場合、ＬＤＰＣ復号器は、リフトされたグラフのすべてのＺ個のエッジに対してパリティ検査演算または変数ノード演算を同時に実行するために、Ｚ個の処理要素を利用することができる。いくつかの実施形態では、Ｚの約数が使用され得る。詳細には、各パリティ検査演算は、対応するソフトビット値をメモリから読み出すことと、ソフトビット値を検査ノードに関連した他のソフトビット値と組み合わせることと、検査ノード演算に由来するソフトビットをメモリに戻して書き込むこととを含む。
【００１７】
[0029]図４は、いくつかの実施形態による通信デバイス４００のブロック図である。通信デバイス４００は、符号器４１０、復号器４２０、および通信チャネルを介してＬＤＰＣ符号化コードワードを送信および／または受信するトランシーバ４３０を含む。符号器４１０は、メモリ４１２とＬＤＰＣ符号器４１４とを含む。メモリ４１２は、ＬＤＰＣ符号器４１４で符号化されるべきデータ（すなわち、情報ビット）を記憶するのに使用され得る。ＬＤＰＣ符号器４１４は、別のデバイスに送信されるべき、ＬＤＰＣ符号に基づく、コードワードを発生させることによって、メモリ４１２に記憶された情報ビットを処理する。いくつかの実施形態では、ＬＤＰＣ符号は、リフトされたＬＤＰＣ符号とすることができる。
【００１８】
[0030]復号器４２０は、メモリ４２２とＬＤＰＣ復号器４２４とを含む。メモリ４２２は、トランシーバ４３０を介して受信された、ＬＤＰＣ復号器４２４によって復号されるべきコードワードを記憶する。ＬＤＰＣ復号器４２４は、メモリ４２４に記憶されたコードワードを、ＬＤＰＣ符号を使用してパリティ検査演算を反復して実行し、誤りが発生している状態で受信されたいかなるビットも訂正を試みることによって処理する。いくつかの実施形態では、ＬＤＰＣ符号は、リフトされたＬＤＰＣ符号とすることができる。いくつかの実施形態では、ＬＤＰＣ復号器４２４は、パリティ検査または変数ノード演算を並列に実行するために複数の処理要素を含むことができる。たとえば、リフティングサイズＺをもつコードワードを処理する場合、ＬＤＰＣ復号器４２４は、リフトされたグラフのすべてのＺ個のエッジに対してパリティ検査演算を同時に実行するために、いくつか（Ｚ個）の処理要素を利用することができる。いくつかの実施形態では、Ｚの約数が使用され得る。
【００１９】
[0031]いくつかの実施形態では、符号擬似巡回２値ＬＤＰＣ符号を考えることができる。たとえば、巡回リフティングのサイズを表すためにプロトグラフ／基礎グラフパースペクティブおよびＺを使用することができる。数学的には、巡回的にリフトされたＬＤＰＣ符号は、２値多項式モジュロｘZ−１の群多元環の上の符号と見なすことができる。この解釈の下で、２値ベクトル（ｂ0，ｂ1，…，ｂZ-1）は、次の多項式として解釈される
【数１】
0005976960.tif 000002
【００２０】
次いで、ｘaを乗算して、
【数２】
0005976960.tif 000003
【００２１】
が与えられ、これは、（ｂ0，ｂ1，…，ｂZ-1）を、ａだけ右に巡回的にシフトすることによって得られた２値ベクトルに対応する。
【数３】
0005976960.tif 000004
【００２２】
[0032]リフトされたパリティ検査行列表示において、多重エッジがないと仮定すると、リフトされたパリティ検査行列Ｈの非空エントリは、整数モジュロＺと見なすことができる。コードワードＣ（ｘ）＝［Ｃ1（ｘ），Ｃ2（ｘ），…Ｃn（ｘ）］Tは、次のものを満たすｎ個の２進多項式モジュロＸZ−１（ｎは、基礎グラフ中の変数ノードの数である）のベクトルと見なすことができ、
【数４】
0005976960.tif 000005
【００２３】
ここで、ｉごとに、ここで、Ｎiは、Ｈの行ｉの非空エントリの集合を表す。
【００２４】
リフトされたパリティ検査行列Ｈでは、２値多項式モジュロＸZ−１に対する行列を表すためにＨ（ｘ）を使用し、ここで、Ｈi,jが非空である場合、
【数５】
0005976960.tif 000006
【００２５】
であり、Ｈi,jが空である場合、Ｈi,j（ｘ）＝０である。多重エッジの場合には、Ｈの対応するエントリは、取られることによって、１組の整数モジュロＺとなるように取られ得る。たとえば、二重エッジＨij＝ａ，ｂは、Ｈi,j（ｘ）＝ｘa＋ｘbとして分解され得る。後続の例では、多重エッジが生じてないと仮定する。明示された多元環に精通している人々は、多重エッジを含むように記述を一般化する方法を容易に理解するであろう。
【００２６】
[0033]符号化は、情報ビットからＣ（ｘ）を決定することを含む。Ｈの列のサブセットは、情報列Ｉとして指定され得る。Ｈが次元ｍ×ｎを有する場合、ｎ−ｍの情報列（すなわち、｜Ｉ｜＝ｎ−ｍ）がある。いくつかの実施形態では、Ｉは、集合Ｉ＝｛ｎ−ｍ＋１，ｎ−ｍ＋２，…，ｎ｝に対応することができる。［１，ｎ］におけるＩの補数は、パリティ列Ｐと呼ばれる。いくつかの実施形態では、Ｐは、集合Ｐ＝｛１，２，…，ｍ｝に対応することができる。いくつかの実施形態では、ＬＤＰＣ符号がパンクチャされた列を含む。これらの列は、送信されるコードワードの一部ではない。復号器において、これらのノードに関連する対数尤度比（ＬＬＲ）が、０に初期化される。基礎送信ブロック長はｎ−ｐであり、ここで、ｐはパンクチャされた列の数であり、レートは（ｎ−ｍ）／（ｎ−ｐ）である。２値情報ブロックサイズは、（ｎ−ｍ）×Ｚであり、送信ブロックサイズは（ｎ−ｐ）×Ｚである。
【００２７】
[0034]そのようなＬＤＰＣ符号の符号化を実行するために、情報ビットは、すべてのｉ∈Ｉに対してＣi（ｘ）を設定するのに使用される。符号化プロセスは、Ｈ（ｘ）Ｃ（ｘ）＝０であるようにｉ∈Ｐに対してＣi（ｘ）を解く。いくつかのＬＤＰＣ符号において、Ｐの元に関連付けられたＨの列のうちのいくつかは、次数１とすることができる。これらの列に関連付けられたビットは、他のビットの簡単なパリティである。多くの場合、そのようなビットは、符号中のパリティビットであり、他のビットが決定された後、容易に決定される。発明者等は、概して、次数２以上であるパリティビットの符号化に焦点を当てる。表記の便宜上、そのような次数１の変数ノードは存在しないと仮定する。
【００２８】
[0035]多くの場合、符号化プロセスの最初のステップは、
【数６】
0005976960.tif 000007
【００２９】
を計算することであり、ここで、Ｎiは、Ｈにおいて行ｉに非空エントリをもつ列の集合を表す。Ｄ（ｘ）＝（Ｄ1（ｘ），…，Ｄm（ｘ））Tを仮定し、およびｉ∈Ｐに対してＣi（ｘ）＝０を一時的に設定すると、Ｄ（ｘ）は、Ｄ（ｘ）＝Ｈ（ｘ）Ｃ（ｘ）と書き直され得る。Ｍは、Ｐから列を取ることによって形成されたＨの正方副行列を表すとしよう。さらに、ＣP（ｘ）は、パリティ要素のみからなるＣ（ｘ）のサブベクトルを表すとしよう。次いで、符号化プロセスは、次の式を、ＣP（ｘ）に対して解く。
【数７】
0005976960.tif 000008
【００３０】
[0036]符号化プロセスの複雑さは、この式を解くことの複雑さに主として依存することに気付かれるであろう。したがって、行列Ｍの構造の選択は、符号化の複雑さを決定する際にかなり重要である。通常使用される符号化構造は、次のものなどの二重対角線タイプ構造である。
【数８】
0005976960.tif 000009
【００３１】
二重対角線構造は、この行列において明白である。二重対角線および略上三角構造は、簡単なガウス消去法手順が適用され得ることを意味する。上述の例では、各行が、それ自体と上の行との和によって取り替えられる場合、結果として生じる行列は上三角となる。次いで、符号化システムは容易に解くことができる。
【００３２】
[0037]この方法を一般化した符号化手法は、以下の通りである。最初に、多項式ベクトルｐ（ｘ）＝（ｐ1（ｘ），…，ｐm（ｘ））が、次のものを決定するように確立される。
【数９】
0005976960.tif 000010
【００３３】
多くの場合、ｐiの各々は低い重みを有することになる。この演算は、ベクトルＤ（ｘ）にバレルシフトを実行し、一緒にしてその結果の排他的論理和をとることによって実行されて、Ｅ（ｘ）を得ることができることに留意されたい。ベクトルｐ（ｘ）は、ｐ（ｘ）Ｍ（ｘ）＝（０，…，０，ｑ（ｘ））であるように選ばれ、それにより、次のものがもたらされる。
【数１０】
0005976960.tif 000011
【００３４】
以前の例では、ｐ（ｘ）の対応する選択は、すべてが１のベクトルである。符号化プロセスの次のステップは、
【数１１】
0005976960.tif 000012
【００３５】
を計算することであり、ここで、ｑ-1（ｘ）ｑ（ｘ）＝１である。本実施形態では、パリティ検査行列は、ｑ-1（ｘ）が低い重みの多項式の積として低複雑性を実現するように構成される。最後に、後退代入ステップが、残りのＣj（ｘ）を決定するために実行され得る。
【００３６】
[0038]本明細書で使用する表記を示すために、サイズ３×５およびＺ＝６の基礎行列を含む例が以下に提供される。
【数１２】
0005976960.tif 000013
【００３７】
コードワードＣ（ｘ）＝（Ｃ1（ｘ），…，Ｃ5（ｘ））があり、ここで、Ｃi（ｘ）は、２値ベクトル（ｂ0，…，ｂ5）に対応して、
【数１３】
0005976960.tif 000014
【００３８】
の形式を取る。この例では、情報列はＣ4（ｘ）およびＣ5（ｘ）である。これらを、Ｃ4（ｘ）＝１＋ｘ＋ｘ3およびＣ5（ｘ）＝ｘ4＋ｘ5であるようにそれぞれ２値ベクトル（１，１，０，１，０，０）および（０，０，０，０，１，１）で与えるとしよう。
【００３９】
[0039]Ｄ（ｘ）を計算すると、
【数１４】
0005976960.tif 000015
【００４０】
が得られ、２値ベクトルの表現では次の通りである。
【数１５】
0005976960.tif 000016
【００４１】
[0040]次に、
【数１６】
0005976960.tif 000017
【００４２】
が得られ、（ＣP（ｘ）＝［Ｃ1（ｘ），Ｃ2（ｘ），Ｃ3（ｘ）］T）に対して次のものを解く必要がある。
【数１７】
0005976960.tif 000018
【００４３】
[0041]Ｍ（ｘ）は二重対角線構造であり、３番目の列のみが２を超える次数であることに気付かれるであろう。ガウス消去法手法に従って、ｐ（ｘ）＝（１，１，１）を左から乗算し、
【数１８】
0005976960.tif 000019
【００４４】
であることに留意すると、そこで、
【数１９】
0005976960.tif 000020
【００４５】
が得られ、したがって、ｑ（ｘ）＝（１＋ｘ3＋ｘ4）である。次に、ｑ（ｘ）2＝ｑ（ｘ2）＝１＋ｘ6＋ｘ8＝ｘ8＝ｘ2であり、そこで、ｑ-1（ｘ）＝ｘ4ｑ（ｘ）が得られ、それは、
【数２０】
0005976960.tif 000021
【００４６】
になり、それは（０，１，０，１，０，１）と等価である。多項式ｑ（ｘ）は項（１＋ｘ3）を含み、それは、２乗されると、（１＋ｘ6）＝０を与えることに気付かれるであろう。本実施形態は、ｑ（ｘ）＝ｘa＋（１＋ｘL）Ｐ（ｘ）であるようにＭ（ｘ）を選ぶことになり、ここで、ある正整数ｋに対して２kＬ＝Ｚであり、Ｐ（ｘ）は任意の非ゼロ多項式である。例は既知であり、そのとき、Ｐ（ｘ）は単項式である。本実施形態は、Ｐ（ｘ）が単に単項式でない場合、この一般形式のｑ（ｘ）を有することになる。
【００４７】
[0042]最後に、例の符号化を完了するために、Ｃ2（ｘ）およびＣ1（ｘ）について解くのに後退代入を使用する。Ｃ2（ｘ）＝Ｃ3（ｘ）＋Ｄ3（ｘ）＝１＋ｘ＋ｘ2＋ｘ3＋ｘ4＋ｘ5およびＣ1（ｘ）＝ｘ3Ｃ3（ｘ）＋Ｄ1（ｘ）＝１＋ｘ＋ｘ2＋ｘ3である。それにより、結果として生じるコードワードは次の通りである。
【数２１】
0005976960.tif 000022
【００４８】
[0043]図５は、例示の擬似巡回ＬＤＰＣ符号のリフトされたパリティ検査行列表示５００のパリティビット部分を示す。行列表示５００は８×８行列Ｍ（ｘ）を含む。これは、行および列の順序を逆転した状態での初期の６×６の例に類似している。したがって、この例では、二重対角線構造が対角線および夕食対角線として現れ、行列は上三角ではなく略下三角である。左端の列は、この場合、次数３を有する。符号化は、最初にＭ（ｘ）の行を合計することによって実行され、次のものが得られる。
【数２２】
0005976960.tif 000023
【００４９】
次のものが決定され得る。
【数２３】
0005976960.tif 000024
【００５０】
残りのＣi（ｘ）は、後退代入によって容易に得られ得る。この例では、第２列から第８列の二重対角線構造に累積チェーンを観察することができる。累積チェーンにわたって合計すると、この特に簡単な例がもたらされる。
【００５１】
[0044]この例では、行列Ｍ（ｘ）がさらに示すところによれば、対応する二部グラフは、各々がｍ−１個の次数２の変数ノードと単一の次数３の変数ノードとを含むＺループを含む。ｍが小さい場合、この構造は、不十分な性能、遅い収束、および高いエラーフロアをもたらすことがある。
【００５２】
[0045]図６は、別の例示の擬似巡回ＬＤＰＣ符号のリフトされたパリティ検査行列表示６００のパリティビット部分を示す。行列表示６００は８×８行列Ｍ（ｘ）を含み、ここで、０、ａ、およびｂはすべて相異なるモジュロＺである。この場合、Ｍ（ｘ）の行を合計すると、次のものが生成される。
【数２４】
0005976960.tif 000025
【００５３】
これにより、式［１］に基づいて、次のものが決定され得る。
【数２５】
0005976960.tif 000026
【００５４】
Ｃ1（ｘ）を解くには、（１＋ｘa＋ｘb）が、最初に、逆転されなければならない。低い複雑さのためには、逆数は低い重みを有することが好ましいことがある。それにより、それ結果、これを容易にするように、ａおよびｂは選ばれ得る。より詳細には、ａおよびｂを選ぶのに役立つ２つの知見がある。第１の知見は、次の一般的な関係である。
【数２６】
0005976960.tif 000027
【００５５】
第２の知見は、ａおよびｂは両方がＺを除算する（たとえば、ｄ＞１が最大公約数であると仮定する）場合、問題は、２値多項式モジュロＸZ/d−１の環において（１＋ｘa/d＋ｘb/d）を逆転することと等価である。しかしながら、これが生じる場合、行列Ｍはｄディスジョイント（ｄｉｓｊｏｉｎｔ）サブグラフを表すことに留意されたい。
【００５６】
[0046]次に、Ｚ＝２kＬを仮定する。これは、次式の
【数２７】
0005976960.tif 000028
【００５７】
をもたらし、またはより一般的には、ｌ∈｛１，２，…，ｋ｝に対して、
【数２８】
0005976960.tif 000029
【００５８】
をもたらす。これにより、ａ＝２lＬ、またはｂ＝２lＬ、またはａ−ｂ＝２lＬである場合、（１＋ｘa＋ｘb）は容易に逆転され得る。たとえば、ｋ＝３およびａ＝Ｌである場合、式は次のものになる。
【数２９】
0005976960.tif 000030
【００５９】
ここから、（１＋ｘa＋ｘb）の逆数は、最初の３つの約数を右側から乗算し、次いで、その結果を巡回的にシフトすることを含む簡単な手順を使用して得られ得ることが分る。
【００６０】
[0047]その結果、符号化演算の主要な困難は、Ｍ（ｘ）の行列式を逆転することに還元され得る。一般に、２値多項式は、その重みが奇数である場合のみ逆転可能である。これは、Ｍ（ｘ）の可能な構造を制限する。上述の手順は、次の形式の任意の多項式を逆転するのに使用され得ることに留意されたい。
【数３０】
0005976960.tif 000031
【００６１】
ここで、Ｐ（ｘ）は任意の非ゼロ多項式であり、ａは任意であり、ある正整数ｋに対して２kＬ＝０モジュロＺである。次いで、
【数３１】
0005976960.tif 000032
【００６２】
である。
【数３２】
0005976960.tif 000033
【００６３】
であるので、ｑ（ｘ）の逆数は、次のものとして得られる。
【数３３】
0005976960.tif 000034
【００６４】
二重対角線の略上三角または下三角形式を有する行列では、上述の演算によって得られるｑ（ｘ）は、単項因子を除いて、Ｍ（ｘ）の行列式である。それにより、いくつかの実施形態では、行列Ｍ（ｘ）はｄｅｔ  Ｍ（ｘ）が式［２］の形式を取るように構成され得る。
【００６５】
[0048]図７は、図１０に与えられたレートｒ＝２７／３０をもつ例示的なＬＤＰＣ符号のリフトされたパリティ検査行列表現７００のパリティビット部分を示す。符号化演算が、最初に、ｐ（ｘ）＝（１，１，（１＋ｘ135），（１＋ｘ113＋ｘ135））を設定することによって実行されて、次のものを生成することができる。
【数３４】
0005976960.tif 000035
【００６６】
次いで、ｑ（ｘ）＝（１＋ｘ13＋ｘ58＋ｘ90＋ｘ135＋ｘ203＋ｘ225）を検証することができ、それにより、
【数３５】
0005976960.tif 000036
【００６７】
ｑ（ｘ）＝＝ｘ203＋（１＋ｘ45）（ｘ13＋（１＋ｘ45）（１＋ｘ135））＝ｘ203＋（１＋ｘ45）Ｐ（ｘ）が得られ、ここで、Ｐ（ｘ）＝ｘ13＋（１＋ｘ45）（１＋ｘ135）＝１＋ｘ13＋ｘ45＋ｘ135＋ｘ180であり、そこで、Ｃ4（ｘ）について次のように解くことができる。
【数３６】
0005976960.tif 000037
【００６８】
ある簡単化がこの例では行われており、実際、上述の積の中間因子（middle factor）は、Ｐ（ｘ）の内部に生じる追加の項のうちのいくつかの形式のために、さらに簡単化され得ることに留意されたい。最後に、符号化を完了するために、後退代入によって解いて、次のものが得られる。
【数３７】
0005976960.tif 000038
【００６９】
[0049]図８は、図１１に与えられたレートｒ＝１３／１５をもつ例示的なＬＤＰＣ符号のリフトされたパリティ検査行列表現８００のパリティビット部分を示す。符号化演算が、最初に、ｐ（ｘ）＝（１，１，１，１）を設定することによって実行されて、次のものを生成することができる。
【数３８】
0005976960.tif 000039
【００７０】
次いで、ｑ（ｘ）＝（１＋ｘ45＋ｘ119）を検証することができ、それにより、次の通りである。
【数３９】
0005976960.tif 000040
【００７１】
Ｃ4（ｘ）について解くと、次のものがもたらされる。
【数４０】
0005976960.tif 000041
【００７２】
最後に、Ｃ1（ｘ）、…、Ｃ3（ｘ）が、後退代入によって得られ得る。
【００７３】
[0050]図９は、図１２に与えられたレートｒ＝２１／２８をもつ例示的なＬＤＰＣ符号のリフトされたパリティ検査行列表現９００のパリティビット部分を示す。符号化演算が、最初に、ｐ（ｘ）＝（１，１，１，１，ｘ2＋ｘ47，ｘ2＋ｘ47，ｘ2＋ｘ47，ｘ2＋ｘ47）を設定することによって実行されて、次のものを生成することができる。
【数４１】
0005976960.tif 000042
【００７４】
次いで、ｑ（ｘ）＝（ｘ2＋ｘ92＋ｘ261）を検証することができ、それにより、次の通りである。
【数４２】
0005976960.tif 000043
【００７５】
Ｃ8（ｘ）について解くと、次のものがもたらされる。
【数４３】
0005976960.tif 000044
【００７６】
最後に、Ｃ1（ｘ）、…、Ｃ7（ｘ）が、後退代入によって得られ得る。
【００７７】
[0051]提示されたすべての例において、巡回リフティングを仮定している。提示された概念は、マッチトリフティング（matched lifting）のクラスに一般化され得る。一般的なマッチトリフティングは、位数がリフティングのサイズと同じである群のリフティングを使用する。巡回リフティングの場合には、群は巡回群である。マッチトリフティングの他の例は、巡回群または任意の有限群の積を使用することができる。この一般化された設定では、群Ｇは、Ｚ個の元ｇ0、ｇ1、…、ｇZ-1からなり、乗法定理ｇiｇj＝ｇkは群のよく知られた定義を満たす。すべての群は単位元を有し、それをｇ0であると見なす。Ｇ上のマッチトリフト２値ＬＤＰＣ符号は、次の形式の元からなる群環の上の符号として解釈され得る。
【数４４】
0005976960.tif 000045
【００７８】
環における加算は、次のもののような対応する係数の加算に対応する。
【数４５】
0005976960.tif 000046
【００７９】
乗算は、
【数４６】
0005976960.tif 000047
【００８０】
のような群乗算に基づき、ここで、次の通りである。
【数４７】
0005976960.tif 000048
【００８１】
巡回リフティングの場合には、単にｇiをｘiと同一に扱うことができ、群環における乗算は多項式乗算モジュロＸZ−１である。群Ｇが可換である（それはすべてのｉ，ｊについてｇiｇj＝ｇjｇiを意味する）場合、恒等式（identity）ｑ（ｘ2）＝ｑ（ｘ）2が、一般に、一般化された群環において当てはまる。より詳細には、それは、次のものを保持する。
【数４８】
0005976960.tif 000049
【００８２】
したがって、簡単な符号化のための上述の構成は、任意の可換マッチトリフティングの場合に帰納する。簡単化する条件は、符号化行列Ｍの行列式が形式ｇa＋（ｇ0＋ｇL）Ｐを取ることであり、ここで、Ｐは群環の任意の元であり、ｇLは、ある正整数ｋに対して、
【数４９】
0005976960.tif 000050
【００８３】
の性質を有することである。
【００８４】
[0052]上述の例では、符号化副行列は、置換または行および／または列を除いて、略上三角（または下三角）であった。言い換えれば、Ｍにおける副対角線より下の元はすべて０である。そのような構成は、少なくとも１つの変数ノードがＭにおいて次数２であることを含む。非常に深いエラーフロアを必要とするいくつかの用途では、最小次数が２よりも大きいことが望ましいことがある。この場合、Ｍの逆転は、一般に、上述で提示された例よりも多く関与させられる。しかしながら、主要な符号化問題はＭの逆転に関連しており、これは、Ｍの行列式が所望の形式、すなわち、擬似巡回リフティングの場合にはｘa＋（１＋ｘL）Ｐ（ｘ）を、任意の可換群マッチトリフティングの場合には形式ｇa＋（ｇ0＋ｇL）Ｐを有するのを保証することによって、簡単にされ得ることに気付かれるであろう。
【００８５】
[0053]本実施形態では、リフトされたＬＤＰＣ符号のコードワードは、サイズＺ×ｎの２次元２値アレイと見なすことができ、ここで、ｎは基礎（送信）ブロック長である。いくつかの実施形態では、提案されるダウンストリーム符号は、Ｚ＝３６０のように定義される．コンステレーションごとに、ｋビットが、一度に次元当たり取られ得る（たとえば、１０２４ＱＡＭでは、ｋ＝５）。さらに、ｋは３６０の約数であり、ｋビットが一度に列方向に取られ、それにより、３６０／ｋ次元、または列当たり１８０／ｋシンボルを発生させることができる。それにより、注目する場合において、集合ｋ∈｛１，２，３，４，５，６｝では、ｋは６０の約数であることに留意されたい。
【００８６】
[0054]図１０、図１１、および図１２は、いくつかの実施形態による、それぞれ、例示のパリティ検査行列１０００、１１００、および１２００を示す。パリティ検査行列１０００、１１００、および１２００の各々において一番上の行は、Ｈの列を指し示す。２番目の行は、情報（１）およびパリティ（０）列を示す。３番目の行は、送信された列（１）およびパンクチャされた列（０）を示す。
【００８７】
[0055]それぞれ、レートｒ＝２７／３０およびｒ＝１３／１５をもつＬＤＰＣ符号に関連するパリティ検査行列１０００および１１００は、システマティックであることに留意されたい。しかしながら、レートｒ＝２１／２８をもつＬＤＰＣ符号に関連するパリティ検査行列１２００は、パンクチャされた情報列を有しており、したがって、完全にはシステマティックでない。
【００８８】
[0056]図１３は、いくつかの実施形態による通信デバイス１３００のブロック図である。通信デバイス１３００は、トランシーバ１３１０と、プロセッサ１３２０と、メモリ１３３０とを含む。トランシーバ１３１０は、通信デバイス１３００へのおよび／または通信デバイス１３００からのデータの通信のために使用され得る。たとえば、トランシーバ１３１０は、通信デバイス１３００とＣＰＵとの間で情報ビットを受信および／または送信することができる。符号器インターフェース１３１０は、通信デバイス１３００とネットワーク中の別の通信デバイスとの間でＬＤＰＣコードワードを出力および／または受信することもできる。
【００８９】
[0057]メモリ１３３０は、受信された情報ビットおよび／またはコードワードを記憶するためにローカルキャッシュとして使用され得るデータストア１３３２を含むことができる。さらに、メモリ１３３０は、以下のソフトウェアモジュールを記憶することができる非一時的コンピュータ可読記憶媒体（たとえば、ＥＰＲＯＭ、ＥＥＰＲＯＭ（登録商標）、フラッシュメモリ、ハードドライブなどのような１つまたは複数の不揮発性メモリ要素）をさらに含むことができる。
【００９０】
・コードワードを生成するために、ＬＤＰＣ符号を使用して、１組の情報ビットを符号化するためのＬＤＰＣ符号化モジュール１３３４、および
・ＬＤＰＣ符号を使用してＬＤＰＣコードワードを復号するためのＬＤＰＣ復号化モジュール１３３６。
【００９１】
各ソフトウェアモジュールには、プロセッサ１３２０によって実行されると、対応する機能を符号器１３００に実行させることができる命令が含まれ得る。それにより、メモリ１３３０の非一時的コンピュータ可読記憶媒体は、ＬＤＰＣ符号化演算を実行する（たとえば、図５〜図１２に関して上述されたような）ための命令を含むことができる。モジュール１３３４〜１３３６がメモリ１３３０中にソフトウェアとして示されているが、モジュールのいずれも、ハードウェア、ソフトウェア、ファームウェア、または前述のものの組合せで実装され得ることに留意されたい。
【００９２】
[0058]  符号器インターフェース１５１０とメモリ１５３０との間に結合されるプロセッサ１５２０は、復号器１５００に（たとえば、メモリ１５３０内に）記憶された１つまたは複数のソフトウェアプログラムの命令のスクリプトを実行することができる任意の好適なプロセッサとすることができる。たとえば、プロセッサ１５２０は、ＬＤＰＣ符号化モジュール１５３４、ＣＷパンクチャリングモジュール１５３６、および／またはＬＤＰＣ復号化モジュール１５３８を実行することができる。
【００９３】
[0059]符号器インターフェース１３１０とメモリ１３３０との間に結合されるプロセッサ１３２０は、復号器１３００に（たとえば、メモリ１３３０内に）記憶された１つまたは複数のソフトウェアプログラムの命令のスクリプトを実行することができる任意の好適なプロセッサとすることができる。たとえば、プロセッサ１３２０は、ＬＤＰＣ符号化モジュール１３３４および／またはＬＤＰＣ復号化モジュール１３３６を実行することができる。
【００９４】
[0060]ＬＤＰＣ符号化モジュール１３３４は、プロセッサ１３２０によって実行されて、ＬＤＰＣ符号の使用により情報ビットを符号化して、コードワードを生成することができる。たとえば、プロセッサ１３２０は、ＬＤＰＣ符号化モジュール１３３４を実行する際に、ＬＤＰＣ符号化モジュール１３３４と、対応する受信デバイスの復号化モジュールとによって共有されるＬＤＰＣ符号に基づいて、情報ビットにＬＤＰＣ符号化演算を実行することができる。各コードワードは、オリジナルの情報ビット、ならびにオリジナル情報ビットにパリティ検査を実行するおよび／またはオリジナルの情報ビットを回復するために使用され得る１組のパリティビットを含むことができる。
【００９５】
[0061]いくつかの実施形態では、ＬＤＰＣ符号は、符号化複雑さを低減するおよび／または最小化するために、擬似巡回リフティングに基づくリフトされたＬＤＰＣ符号とすることができる（たとえば、図５〜図１２に関して上述されたように）。たとえば、ＬＤＰＣ符号は、いくつかのパリティビットと、パリティビットの値を決定するための副行列とを含むことができる。詳細には、ＬＤＰＣ符号は、位数Ｚ（すなわち、リフティングのサイズに対応する）のマッチトリフトＬＤＰＣ符号とすることができる。副行列の行列式は、ｇa＋（ｇ0＋ｇL）Ｐの形式の多項式とすることができ、ここで、ｇ0は群の単位元であり、
【数５０】
0005976960.tif 000051
【００９６】
であり、Ｐはリフティング群に関連付けられた２値群環の任意の非ゼロ元である。いくつかの実施形態では、リフティング群は巡回群とすることができ、ここで、ｇiはｘiと同一に扱われ得る。その結果、副行列の行列式は、ｘa＋（１＋ｘL）Ｐ（ｘ）とすることができ、ここで、Ｐ（ｘ）は少なくとも２つの項を有し、２kＬ＝０モジュロＺである。
【００９７】
[0062]ＬＤＰＣ復号化モジュール１３３６は、ＬＤＰＣ符号を使用してＬＤＰＣコードワードを復号するためにプロセッサ１３２０によって実行され得る。上述されたように、ＬＤＰＣ符号は、リフトされたＬＤＰＣ符号とすることができる（たとえば、擬似巡回リフティングに基づいて）。
【００９８】
[0063]前述の明細書において、本実施形態は、本発明の特定の例示の実施形態を参照して説明された。しかしながら、添付の特許請求の範囲に記載された本開示のより広い範囲から逸脱することなく、様々な改変および変更がそれに行われ得ることは明らかであろう。
以下に、本願出願の当初の特許請求の範囲に記載された発明を付記する。
［Ｃ１］
１組の情報ビットを受信することと、
マッチトリフトＬＤＰＣ符号に基づいてコードワードを生成するために、低密度パリティ検査（ＬＤＰＣ）符号化演算を前記１組の情報ビットに実行することと、ここにおいて、マッチトリフティングが可換リフティング群に基づく、ここにおいて、前記ＬＤＰＣ符号が、いくつかのパリティビットと、前記パリティビットの値を決定するための副行列とを含む、ここにおいて、
前記リフティング群の位数（Ｚ）が前記リフティングのサイズに対応し、
前記副行列の行列式が、ｇa＋（ｇ0＋ｇL）Ｐの形式の多項式であり、ここで、
ｇ0は前記群の単位元であり、
【数５１】
0005976960.tif 000052
であり、
Ｐは、前記リフティング群に関連付けられた２値群環の任意の非ゼロ元である、
を備えるデータ符号化の方法。
［Ｃ２］
前記リフティング群が巡回群であり、ここにおいて、
ｇiはｘiと同一に扱うことができ、
前記副行列の前記行列式が、ｘa＋（１＋ｘL）Ｐ（ｘ）の形式を取り、ここで、Ｐ（ｘ）は少なくとも２つの項を有し、２kＬ＝０モジュロＺである、Ｃ１に記載の方法。
［Ｃ３］
前記副行列が、その行および列の置換を除いて、上三角である、Ｃ１に記載の方法。
［Ｃ４］
前記副行列の第１の副対角線より下の元が０に等しい、Ｃ３に記載の方法。
［Ｃ５］
プログラム命令を備えるコンピュータ可読記憶媒体であって、前記プログラム命令が、通信デバイス内に設けられたプロセッサによって実行されたとき、前記プログラム命令により、前記デバイスが、
１組の情報ビットを受信し、
マッチトリフトＬＤＰＣ符号に基づいてコードワードを生成するために、ＬＤＰＣ符号化演算を前記１組の情報ビットに実行する、ここにおいて、マッチトリフティングが可換リフティング群に基づく、ここにおいて、前記ＬＤＰＣ符号が、いくつかのパリティビットと、前記パリティビットの値を決定するための副行列とを含む、ここにおいて、
前記リフティング群の位数（Ｚ）が前記リフティングのサイズに対応し、
前記副行列の行列式が、ｇa＋（ｇ0＋ｇL）Ｐの形式の多項式であり、ここで、
ｇ0は前記群の単位元であり、
【数５２】
0005976960.tif 000053
であり、
Ｐは、前記リフティング群に関連付けられた２値群環の任意の非ゼロ元である、コンピュータ可読記憶媒体。
［Ｃ６］
前記リフティング群が巡回群であり、ここにおいて、
ｇiはｘiと同一に扱うことができ、
前記副行列の前記行列式が、ｘa＋（１＋ｘL）Ｐ（ｘ）の形式を取り、ここで、Ｐ（ｘ）は少なくとも２つの項を有し、２kＬ＝０モジュロＺである、Ｃ５に記載のコンピュータ可読記憶媒体。
［Ｃ７］
前記副行列が、その行および列の置換を除いて、上三角である、Ｃ５に記載のコンピュータ可読記憶媒体。
［Ｃ８］
前記副行列の第１の副対角線より下の元が０に等しい、Ｃ７に記載のコンピュータ可読記憶媒体。
［Ｃ９］
１組の情報ビットを記憶するメモリと、
符号器と、ここにおいて、前記符号器が、
マッチトリフトＬＤＰＣ符号に基づいてコードワードを生成するために、ＬＤＰＣ符号化演算を前記１組の情報ビットに実行する、ここにおいて、マッチトリフティングが可換リフティング群に基づく、ここにおいて、前記ＬＤＰＣ符号が、いくつかのパリティビットと、前記パリティビットの値を決定するための副行列とを含む、ここにおいて、
前記リフティング群の位数（Ｚ）が前記リフティングのサイズに対応し、
前記副行列の行列式が、ｇa＋（ｇ0＋ｇL）Ｐの形式の多項式であり、ここで、
ｇ0は前記群の単位元であり、
【数５３】
0005976960.tif 000054
であり、
Ｐは、前記リフティング群に関連付けられた２値群環の任意の非ゼロ元である、
を備える通信デバイス。
［Ｃ１０］
前記リフティング群が巡回群であり、ここにおいて、
ｇiはｘiと同一に扱うことができ、
前記副行列の前記行列式が、ｘa＋（１＋ｘL）Ｐ（ｘ）の形式を取り、ここで、Ｐ（ｘ）は少なくとも２つの項を有し、２kＬ＝０モジュロＺである、Ｃ９に記載のデバイス。
［Ｃ１１］
前記副行列が、その行および列の置換を除いて、上三角である、Ｃ９に記載のデバイス。
［Ｃ１２］
前記副行列の第１の副対角線より下の元が０に等しい、Ｃ１１に記載のデバイス。
［Ｃ１３］
１組の情報ビットを受信するための手段と、
マッチトリフトＬＤＰＣ符号に基づいてコードワードを生成するために、ＬＤＰＣ符号化演算を前記１組の情報ビットに実行するための手段と、ここにおいて、マッチトリフティングが可換リフティング群に基づく、ここにおいて、前記ＬＤＰＣ符号が、いくつかのパリティビットと、前記パリティビットの値を決定するための副行列とを含む、ここにおいて、
前記リフティング群の位数（Ｚ）が前記リフティングのサイズに対応し、
前記副行列の行列式が、ｇa＋（ｇ0＋ｇL）Ｐの形式の多項式であり、ここで、
ｇ0は前記群の単位元であり、
【数５４】
0005976960.tif 000055
であり、
Ｐは、前記リフティング群に関連付けられた２値群環の任意の非ゼロ元である、
を備える符号器。
【図１Ａ】
0005976960.tif 000060
【図１Ｂ】
0005976960.tif 000061
【図２】
0005976960.tif 000062
【図３】
0005976960.tif 000063
【図４】
0005976960.tif 000064
【図５】
0005976960.tif 000065
【図６】
0005976960.tif 000066
【図７】
0005976960.tif 000067
【図８】
0005976960.tif 000068
【図９】
0005976960.tif 000069
【図１０】
0005976960.tif 000070
【図１１】
0005976960.tif 000071
【図１２】
0005976960.tif 000072
【図１３】
0005976960.tif 000073