(57)【特許請求の範囲】
【請求項１】
複数の部分行列を有するパリティ検査行列に基づくＬＤＰＣ符号の復号器であって、前記複数の部分行列の各行および各列は、単一の非ゼロ項目を有し、
１つ又は複数の誤り訂正符号を復号する前記部分行列のそれぞれに関連する少なくとも１つのノードであって、各ノードは、複数のメモリ要素を有するメモリ・デバイスを含み、前記メモリ要素のうちの１つまたは複数は、選択的にディスエーブルされるように構成される、少なくとも１つのノード
を含む復号器。
【請求項２】
前記複数のメモリ要素は、ｍｍａｘ個のメモリ要素を含み、ｍｍａｘ・ｍｍａｘまでの部分行列次元を有する符号は、実現されることができる、請求項１に記載の復号器。
【請求項３】
複数の部分行列を有するパリティ検査行列に基づくＬＤＰＣ符号の復号器であって、前記複数の部分行列の各行および各列は、単一の非ゼロ項目を有し、
１つ又は複数の誤り訂正符号を復号する前記部分行列のそれぞれに関連する少なくとも１つのノードであって、少なくとも１つのノードは、選択的にディスエーブルされるように構成される、少なくとも１つのノード
を含む復号器。
【請求項４】
ノードの１行又は１列は、選択的にディスエーブルされるように構成される、請求項３に記載の復号器。
【請求項５】
複数の部分行列を有するパリティ検査行列に基づくＬＤＰＣ符号の復号器であって、前記複数の部分行列の各行および各列は、単一の非ゼロ項目を有し、
１つ又は複数の誤り訂正符号を復号する前記部分行列のそれぞれに関連する少なくとも１つのノードであって、少なくとも１つのノードは、実行時に選択的にディスエーブルされるように構成され、前記少なくとも１つのノードは、さらに、マルチプレクサを含む、少なくとも１つのノード
を含む復号器。
【請求項６】
複数の部分行列を有するパリティ検査行列に基づいてＬＤＰＣ符号を復号する方法であって、前記複数の部分行列の各行および各列は、単一の非ゼロ項目を有し、前記部分行列のそれぞれは、少なくとも１つの関連するノードを有し、各ノードは、複数のメモリ要素を有するメモリ・デバイスを含み、
前記メモリ要素のうちの１つまたは複数を選択的にディスエーブルするステップ
を含む方法。
【請求項７】
前記メモリ要素のうちの１つまたは複数を選択的にディスエーブルする前記ステップは、スイッチによって実行される、請求項６に記載の方法。
【請求項８】
複数の部分行列を有するパリティ検査行列に基づいてＬＤＰＣ符号を復号する方法であって、前記複数の部分行列の各行および各列は、単一の非ゼロ項目を有し、前記部分行列のそれぞれは、少なくとも１つの関連するノードを有し、
前記少なくとも１つのノードを選択的にディスエーブルするステップ
を含む方法。
【請求項９】
少なくとも１つのノードを選択的にディスエーブルする前記ステップは、ノードの１行又は１列を選択的にディスエーブルするステップから成る、請求項８に記載の方法。
【請求項１０】
少なくとも１つのノードを選択的にディスエーブルする前記工程は、前記ノードに関連するメモリに０をセットするステップからなる、請求項８に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、低密度パリティ検査（ＬＤＰＣ）符号を復号する技法に関し、より具体的には、準巡回（ｑｕａｓｉ−ｃｙｃｌｉｃ）低密度パリティ検査（ＬＤＰＣ）符号を復号する構成可能な技法に関する。
【背景技術】
【０００２】
情報が送信器と受信器との間で伝送される時に、誤りが発生する可能性がある。低密度パリティ検査（ＬＤＰＣ）符号などの誤り訂正符号が、しばしば、そのような誤りを検出し、訂正するのに使用される。ＬＤＰＣ符号は、パリティ検査行列Ｈに基づくブロック符号である。たとえば、Ｒ．Ｇ．Ｇａｌｌａｇｅｒ、「Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ−Ｃｈｅｃｋ  Ｃｏｄｅ」、ＩＲＥ  Ｔｒａｎｓ．Ｉｎｆｏｒｍ．  Ｔｈｅｏｒｙ、ｖｏｌ．ＩＴ−８、２１〜２８頁（１９６２年１月）を参照されたい。ＬＤＰＣ符号は、衛星通信、無線伝送、光ファイバなどのさまざまな伝送システム、ならびにハード・ディスク・ドライブ、光ディスク、および磁気バンドを含むさまざまな記憶媒体での使用について提案され、または提唱されている。
【０００３】
所与のＬＤＰＣ符号は、パリティ検査行列Ｈによって定義される。パリティ検査行列の非ゼロ項目は、受信された符号語内の誤りを検出し、訂正するのに使用されるパリティ検査を定義する。ＬＤＰＣパリティ検査行列は、疎であると言われる。言い換えると、この行列には、行列の大きさに対して相対的に少数の非ゼロ項目がある。パリティ検査行列Ｈが次元（ｎ−ｋ，ｎ）を有する場合に、符号語は、ｋ個の情報ビットおよびｎ−ｋ個のパリティ検査ビットを伴うｎビット長であると言われる。（ｎ，ｋ）符号に関するパリティ検査行列は、ｎ列ｎ−ｋ行を有する。
【０００４】
準巡回ＬＤＰＣ符号は、ランダム符号構成および構造化符号構成の利点の一部を組み合わせたものである。ランダムＬＤＰＣ符号の符号化は、通常、「オーダーｎ２」（Ｏ（ｎ２））演算である。準巡回ＬＤＰＣ符号によって、良い誤り率性能と単純化された符号化および復号の機会とが組み合わされる。その結果、準巡回ＬＤＰＣ符号が、ＩＥＥＥ  ８０２．１６ｅ標準規格について提案されてきた。
【非特許文献１】Ｒ．Ｇ．Ｇａｌｌａｇｅｒ、「Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ−Ｃｈｅｃｋ  Ｃｏｄｅ」、ＩＲＥ  Ｔｒａｎｓ．Ｉｎｆｏｒｍ．Ｔｈｅｏｒｙ、ｖｏｌ．ＩＴ−８、２１〜２８頁（１９６２年１月）
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ＬＤＰＣ復号器は、伝統的に特定のパリティ検査行列Ｈについて設計されてきた。したがって、この復号器が処理するブロック長および符号のレートは、特定のアーキテクチャについて固定されている。したがって、複数の符号ブロック長および符号レートをサポートできるＬＤＰＣ復号器の必要が存在する。可変パリティ検査行列をサポートできるＬＤＰＣ復号器に関するさらなる必要が存在する。
【課題を解決するための手段】
【０００６】
一般に、ＬＤＰＣ符号のブロックおよびレートに独立な復号の方法および装置を開示する。開示されるＬＤＰＣ復号器は、複数の符号ブロック長および符号レートならびに可変パリティ検査行列をサポートする。開示されるＬＤＰＣ復号器は、複数の部分行列を有するパリティ検査行列に基づくＬＤＰＣ符号を復号し、この複数の部分行列の各行および各列は、単一の非ゼロ項目を有する。たとえば、複数の部分行列のそれぞれ
【数１】
0005483875.tif 000002
は、ｌだけ循環シフトされたｍ×ｍ恒等行列である。
【０００７】
本発明の一態様によれば、部分行列のそれぞれは、少なくとも１つの関連するファイ・ノードを有し、各ファイ・ノードは、複数のメモリ要素を有するメモリ・デバイスを含み、メモリ要素のうちの１つまたは複数は、選択的にディスエーブルされることができる。一実施態様で、複数のメモリ要素は、ｍｍａｘ個のメモリ要素を含み、ｍｍａｘ・ｍｍａｘまでの部分行列次元を有する符号は、実現されることができる。
【０００８】
本発明のもう１つの態様によれば、ファイ・ノードを選択的にディスエーブルすることができる。たとえば、ファイ・ノードの１つまたは複数の行または列を、選択的にディスエーブルすることができる。一実施態様で、ファイ・ノードは、ファイ・ノードに関連するメモリに０をセットすることによって選択的にディスエーブルされる。
【０００９】
本発明のもう１つの態様によれば、ファイ・ノードは、実行時に選択的にディスエーブルされることができ、少なくとも１つのファイ・ノードは、さらに、マルチプレクサを含む。この形で、可変パリティ検査行列がもたらされる。やはり、ファイ・ノードは、たとえば、ファイ・ノードに関連するメモリに０をセットすることによって選択的にディスエーブルされることができる。複数のファイ・ノードは、行サマーに接続され、マルチプレクサは、少なくとも１つのファイ・ノードが接続される列を選択する１対多マルチプレクサである。
本発明ならびに本発明のさらなる特徴および利益のより完全な理解は、次の詳細な説明および図面を参照することによって得られるであろう。
【発明を実施するための最良の形態】
【００１０】
本発明は、複数の符号ブロック長および符号レートをサポートできるＬＤＰＣ復号器を提供する。本発明のもう１つの態様によれば、可変パリティ検査行列をサポートできるＬＤＰＣ復号器が提供される。
【００１１】
ＬＤＰＣ符号
図１に、例示的なＬＤＰＣ符号のパリティ検査行列１００を示す。図２に、図１のパリティ検査行列１００から構成されるタナー・グラフ２００を示す。図２に示されているように、タナー・グラフ２００は、複数の変数ノード２２０および検査ノード２１０から構成される。検査ノード２１０は、パリティ検査行列の行に対応する。第ｉ検査ノードは、パリティ検査行列Ｈの第ｉ行に対応する。同様に、変数ノードは、Ｈの列に対応する。所与の検査ノード２１０−ｋと所与の変数ノード２２０−ｋとの間の接続は、パリティ検査行列１００に１が存在する場合に行われる。
【００１２】
図１のパリティ検査行列１００は、平均値が０．５なので低密度行列すなわち疎行列ではないが、本明細書で例示のために使用されることに留意されたい。図２のタナー・グラフ２００は、二部グラフすなわち、頂点の集合を、同一集合内のどの２つの要素も単一の辺によって接続されない２つの別個の集合に分割できるグラフである。ガース（ｇｉｒｔｈ）すなわち最小サイクル長を符号の性能に関係付ける多数の理論がある。大きいガースを有する符号が、一般に好ましく、より小さいガースを有する符号よりよい性能をもたらすことを示すことができる。
【００１３】
ＬＤＰＣ符号を、複数の形で分類することができる。パリティ検査行列は、各行（または列）が、ラップアラウンドを伴って１位置横（または下）にシフトされた前の行（または列）である場合に、巡回行列である。さらに、パリティ検査行列を、準巡回構造を有すると言うことができる。
【００１４】
図３に、図１のパリティ検査行列１００の拡張である、例示的なＬＤＰＣ符号のパリティ検査行列３００を示す。図３に示されているように、パリティ検査行列３００は、巡回部分行列
【数２】
0005483875.tif 000003
からなり、各部分行列
【数３】
0005483875.tif 000004
は、ｌ位置だけ循環シフトされたｍ×ｍ恒等行列である。本発明の一態様によれば、１つのファイ・ノードが、これらの部分行列のそれぞれについて割り当てられる。下で図９に関して述べるように、これらのファイ・ノードは、復号動作に必要な「行」和および「列」和を計算できる他のブロックに接続される。したがって、復号器には、パリティ検査行列内の部分行列と同一の個数のファイ・ノードがある。
【００１５】
パリティ検査行列３００は、レート１／２符号を記述する（Ｈは、次元（ｎ−ｋ，ｎ）およびレート＝ｋ／ｎを有する）。ｍが１と等しい場合には、パリティ検査行列３００は
【数４】
0005483875.tif 000005
になり、（６，３）符号と等しい（ｎ，ｋ）がもたらされる。しかし、ｍが３と等しい場合の、結果のパリティ検査行列４００を図４に示す。結果のパリティ検査行列４００は、（ｎ，ｋ）＝（１８，９）符号に対応する。ｍ＝１およびｍ＝３について、同一の個数のファイ・ノードがあるが、各ファイ・ノードは、後者の場合に３倍の量のデータを有する。言い換えると、特定のＨ行列について、「１」の各位置は、本アーキテクチャにおけるアクティブ・ファイ・ノードの位置を表す。各ファイ・ノードは、ｍ個の入力に基づいてｍ個の出力を作る。
【００１６】
すべてのファイ・ノードが、並列に横並びで（ｉｎ  ｌｏｃｋ−ｓｔｅｐ）動作し、ｍ個の入力のめいめいのリストを順次処理する。したがって、本発明は、符号長を２倍にすることが処理時間を２倍にするのみであるアーキテクチャを提供する。これは、所与のスループットについて、クロック速度が符号長と独立であり、したがって非常に長い符号長を、スループット・コストなしで使用できることをも意味する。
【００１７】
ＬＤＰＣ符号の復号
受信された符号語を復号する際に、送信された可能性が最も高いメッセージが判定される。図５に、加法性白色ガウス雑音（ＡＷＧＮ）チャネルを介して送信された準巡回ＬＤＰＣ符号の例示的な復号アルゴリズム５００を示す。図５の表記は、次のように定義される。
・ｙｉは、符号語の位置ｉの受信されたサンプルである。
・σ２は、受信されたサンプルの雑音成分の分散である。
・ｐｉ＝Ｐｒ（ｍｉ＝１｜ｙｉ）は、観察ｙｉを与えられて、メッセージのビットｉが１と等しくなる確率である。
・ｑｉｊ（χ）は、第ｉ変数ノードから第ｊ検査ノードに渡されるメッセージであり、メッセージのビットｉすなわちｍｉがχと等しくなる確率である。
・ｒｊｉ（χ）は、第ｊ変数ノードから第ｉ検査ノードに渡されるメッセージであり、メッセージのビットｉすなわちｍｉがχと等しい場合に第ｊパリティ検査式が満足される確率である。
・Ｒｊは、パリティ検査行列内の、第ｊ行に「１」の項目を有する列の集合である。
・Ｃｉは、パリティ検査行列内の、第ｉ列に「１」の項目を有する行の集合である。
・Ｒｊ＼ｉは、要素ｉを除去された集合Ｒｊである。
・Ｃｉ＼ｊは、要素ｊを除去された集合Ｃｉである。
図５の復号アルゴリズムは、次のように進行する。
・初期化  変数ノードが、５００−１を使用して、各ビットのチャネル事後確率ｐｉおよび（１−ｐｉ）を計算することによって初期化される。
・パリティ検査式が満足されるか、反復の最大回数に達するまで、次を繰り返す。
○変数ノードから検査ノードにメッセージｑｉｊ（０）およびｑｉｊ（１）を送る。
○式５００−２および５００−３を使用して、各検査ノードで受け取られた情報を組み合わせることによって、メッセージｒｊｉ（０）およびｒｊｉ（１）を計算する。
○検査ノードから変数ノードにメッセージｒｊｉ（０）およびｒｊｉ（１）を送る。
○式５００−４および５００−５を使用して、各変数ノードで受け取られた情報を組み合わせることによって、メッセージｑｉｊ（０）およびｑｉｊ（１）を計算する。
【００１８】
図５の例示的な復号アルゴリズム５００は、高価な演算である乗算をかなりの回数だけ用いる。したがって、図６に、対数（ｌｏｇ）領域で演算することによって乗算演算を加算に変換する、準巡回ＬＤＰＣ符号の代替の復号アルゴリズム６００を示す。一般に、図６の復号アルゴリズム６００は、すべてのｒｊｉ（０）値、ｒｊｉ（１）値、および類似する値を対数尤度比
【数５】
0005483875.tif 000006
に置換する。対数領域では、「和」をとる時に、６００−２によって示されるように、符号の積が、乗算を正しく実行するのに使用される。
図６の復号アルゴリズムは、図５の復号アルゴリズムに似た形で進行する。
・初期化  変数ノードが、６００−１を使用して、受信されたサンプルに基づいて各ビットの対数尤度比Ｌｉを計算することによって初期化される。Ｌｉを使用してメッセージｌｏｇ  ｑｉｊを初期化する。
・有効な符号語に達する（Ｑｉから硬判定を行い、パリティ検査式をテストすることによって判定される）か、反復の最大回数に達するまで、次を繰り返す。
○変数ノードから検査ノードにメッセージｌｏｇ  ｑｉｊを送る。
○式６００−２を使用して、各検査ノードで受け取られた情報を組み合わせることによって、メッセージｌｏｇ  ｒｊｉを計算する。
○検査ノードから変数ノードにメッセージｌｏｇ  ｒｊｉを送る。
○６００−４を使用して、Ｌｉを各変数ノードで受け取られた情報と組み合わせることによってビット対数尤度比を計算する。
○式６００−３を使用して、Ｌｉを各変数ノードで受け取られた情報と組み合わせることによって、新しいメッセージｌｏｇ  ｑｉｊを計算する。
図６の復号アルゴリズム６００が、図７に示された関数Φ（ｘ）を利用し、ここで、
【数６】
0005483875.tif 000007
であることに留意されたい。図７に示されているように、関数Φ（ｘ）は、それ自体の逆関数である。
【００１９】
準巡回ＬＤＰＣ符号用の構成可能な復号器アーキテクチャ
図８に、例示的なＬＤＰＣ符号のパリティ検査行列８００を示す。図８に示されているように、パリティ検査行列８００は、やはり、巡回部分行列
【数７】
0005483875.tif 000008
からなり、各部分行列
【数８】
0005483875.tif 000009
は、ｌだけ循環シフトされたｍ×ｍ恒等行列である。図９は、本発明の特徴を組み込んだ、対応する例示的な復号器アーキテクチャ９００のブロック図である。１つのファイ・ノード９１０が、パリティ検査行列８００内の部分行列のそれぞれについて復号器アーキテクチャ９００内で割り当てられ、パリティ検査行列８００内の行ごとおよび列ごとに、１つの行サマー（ｓｕｍｍｅｒ）９３０および１つの列サマー９４０がある。各ファイ・ノードは、適当な行サマー９３０および列サマー９４０に接続される。
各部分行列は、次元ｍ×ｍを有する。したがって、各部分行列には、ｍ個の１だけが存在する。計算は、パリティ検査行列内に１がある位置だけについて実行される。したがって、各ファイ・ノードは、ｍ個の符号付き数の責任を負う。同様に、各行サマーおよび各列サマーは、ｍ個の要素を操作する。
【００２０】
図１０は、復号器アーキテクチャ９００の諸態様をさらに詳細に示すブロック図１０００である。具体的に言うと、ブロック図１０００は、図９の復号器アーキテクチャ９００内の所与のファイ・ノード９１０−１が、データ接続９２０−ｚによってファイ・ノード９１０−２などの他のファイ・ノードならびに行サマー９３０−ｚおよび列サマー９４０−ｚにどのように相互接続されるかを示す。
【００２１】
図１０に示されているように、ファイ・ノード９１０−１などの各ファイ・ノード９１０−ｚは、浮動小数点減算器１０１０−１、Φ（ｘ）関数計算ユニット１０２０−１、そのファイ・ノードが責任を負うｍ個の要素を格納するレジスタ１０３０−１、および各計算の行入力または列入力を選択するマルチプレクサ１０４０−１を含む。ファイ・ノードの間のデータ経路９２０は、範囲を減らされた浮動小数点数（たとえば、符号ビット、４ビットの仮数部＋５ビット指数部、仮数部に暗黙の「１」を伴う）である。各ファイ・ノードは、対応する行サマー９３０および列サマー９４０に接続される。この例示的実施形態では、サマー９３０および９４０は、７個までの浮動小数点数を加算することができる。ダイナミック・レンジが狭い実施態様では、Φ（ｘ）関数計算ユニット１０２０−１が、組合せ論理ルックアップ・テーブルを介して浮動小数点入力から直接にΦ（ｘ）を計算することができる。
【００２２】
行サマー９３０および列サマー９４０は、データの転送を最小にする圧縮ルーチン（インデックス→浮動小数点および浮動小数点→インデックス）、すべての入力を加算するのに十分な加算器、および初期ファイ・ノード値から減算する減算器からなる。
【００２３】
ファイ・ノード９１０内の回路網を、必要な数のレベルの並列性をサポートするために複製することができる。たとえば、データ経路の幅を広げ、その結果、複数の数を１クロック・サイクルで転送できるようにすることによって、より高い並列性をアーキテクチャ９００内で達成することができる。これは、行／列サマー９３０、９４０、およびΦ（ｘ）計算ユニットの適当な複製を必要とする。
【００２４】
実際のパリティ検査行列は、数千×数千の次元を有する場合があるが、パリティ検査行列を、多数の部分行列からなる、はるかに小さい行列に分割することができる。図９のアーキテクチャ９００を使用して、図６の復号アルゴリズム６００を、たとえば次のように実施することができる。各ファイ・ノードは、ｘｉと表されるメモリ要素の集合を有し、ｉは、｛０，…，ｍ−１｝からの値をとることができる。さらに、この例のアーキテクチャは、後チャネル対数尤度比（ＬＬＲ）Ｌｊを記憶する、列サマー内のメモリを含む。次のステップでは、ｒｉおよびｃｉは、それぞれ行サマーおよび列サマー内の累積された結果を表す。ＲｊおよびＣｊは、それぞれファイ・ノードから行サマーおよび列サマーへの接続の集合を表す。
【００２５】
１．受信されたデータから対数尤度比（ＬＬＲ）Ｌｊを計算し、列サマー９４０に格納する。Ｌｊ値の大きさをファイ・ノード９１０内の適当なｘｉメモリにコピーする、すなわちｘｉ＝｜Ｌｊ｜。
２．各ファイ・ノード９１０が、ｘｉ←Φ（ｘｉ）を計算する（すなわち、結果をｘｉに書き戻す）。
３．行サマー９３０が、適当な行のｘｉを合計し、すなわち
【数９】
0005483875.tif 000010
、ｒｊのパリティ（符号）も計算する。
４．合計および符合（結果）を、ファイ・ノードに返し、ファイ・ノード値を減算する、すなわち、ｘｉ←ｒｉ−ｘｉ。
５．各ファイ・ノードが、ｘｉ←Φ（ｘｉ）をもう一度計算する。ファイ・ノードは、現在、式６００−２の結果を含む。
６．列サマー９４０が、適当な列を合計し、初期ＬＬＲを加算する
【数１０】
0005483875.tif 000011
。符号ビットは、最尤符号語ビットを形成するのに使用される。これは、式６００−４の結果に対応する。
７．合計および符号を、ファイ・ノードに返し、ファイ・ノードに格納された値を減算する、すなわち、ｘｉ←ｃｊ−ｘｉ。これは、式６００−３の結果である。
【００２６】
ステップ２から５は、図６の「反復ステップ１」に対応する。ステップ６および７は、図６の「反復ステップ２」に対応する。ステップ２〜７は、すべてのｉ値｛０，…，ｍ−１｝について実行され、したがって、１回の反復と、最尤符号語の今までで最良の推定値の計算とを完了する。ステップ６の結果を使用して、有効な符号語に達したかどうかを判定し、したがって、このアルゴリズムの終了を可能にすることができる。
【００２７】
ｉの値ごとのステップ２〜７の反復は、有効な符号語に達し、このアルゴリズムが打ち切られるか、反復の最大回数を完了するかのいずれかになるまで継続される。
並列性要因を高めることによって、｛０，…，ｍ−１｝のうちの複数が、一時に操作される。
【００２８】
アーキテクチャ９００が、パリティ検査を実行することに留意されたい。ｃｊの符号ビットは、符号語を形成するのに使用され、次のステップで、これらが、ファイ・ノードに戻ってロードされる（符号が保存される）。Φ（ｘ）の計算も、符号を保存し、次の行の演算が実行される時に、符号ビットが、一緒に乗算される。積が０の場合に、これは、その行がパリティ式を満足することを意味する。その後、すべての行が０であるかどうかを調べて、それが有効な符号語であるかどうかを調べるテストを実行する。
【００２９】
可変ブロック長
本発明の一態様によれば、アーキテクチャ９００は、ファイ・ノードに、部分行列の値ｍに従って異なる量のデータの責任を負わせることによって、可変ブロック長を可能にする。したがって、１つの例示的実施態様では、各ファイ・ノード９１０のレジスタ１０３０は、たとえば９６個の要素を格納するのに十分なメモリｍｍａｘを有する。実際に使用されるメモリ要素は、たとえばスイッチによって制御することができる。本明細書で使用される「スイッチ」に、メモリ要素を選択的にイネーブルすることができる、すべてのハードウェアまたはソフトウェア・デバイスを含めることができることに留意されたい。ｍｍａｘ・ｍｍａｘまでの部分行列次元を有するすべての符号を、実現することができる。
【００３０】
可変レート
本発明のもう１つの態様によれば、アーキテクチャ９００は、余分なファイ・ノードを「オフにする」能力を有することによって（たとえば、メモリ１０３０に０をセットすることによって）可変レート符号復号器を提供する。この形で、行全体および列全体をオフにすることができる。たとえば、
【数１１】
0005483875.tif 000012
によって指定される（６，３）符号を、１つの列のすべてのファイ・ノードをオフにすることによって、（５，３）符号に変換することができる。
【００３１】
可変パリティ検査行列
本発明のさらなる態様によれば、パリティ検査行列は、任意選択で、ファイ・ノードをオフにし、各ファイ・ノードに列セレクタまたはマルチプレクサを追加することによって、実行時に構成可能とすることができる。ファイ・ノードは、たとえば、パリティ検査行列内のすべての可能なスロットにデータが取り込まれる時すなわち、パリティ検査行列によって指定されるｎ＊（ｎ−ｋ）個のスペースのそれぞれにデータが取り込まれる時に、オフにすることができる。しかし、これは、より多くのゲートを必要とする。各ファイ・ノードの列セレクタまたはマルチプレクサは、たとえば、８つのファイ・ノードを各行サマーにハードワイヤ接続し、次に、ファイ・ノードが４つの列のうちのどれに接続されるかを選択するために各ファイ・ノードに１−４マルチプレクサを追加することによって、実施することができる。たとえば、第１ファイ・ノード（各行の）を列１から４に写像させ、第２ファイ・ノードを列３から６に写像させ、以下同様にすることによって、多数の異なるパリティ検査行列を具体化することができる。
【００３２】
図１１に、ファイ・ノード１１１０を列サマー１１３０に接続するのにマルチプレクサ（Ｍｕｘ）要素１１２０を使用する、例の構成１１００を示す。次の表に、この構成を用いて実現できるＨのすべての可能な行を列挙する。
【数１２】
0005483875.tif 000013
【００３３】
パリティ検査行列は、低密度（疎）である。したがって、この２つの方法の組合せは、多数の異なるパリティ検査行列を実施できるという点で非常に効率的である。この方法を可変レート法と共に使用して、異なるレートの符号をも作成することができる。
【００３４】
複数の同一のダイが、通常、ウェハの表面上で繰り返されるパターン内に形成される。各ダイは、本明細書に記載のデバイスを含み、他の構造または回路を含むことができる。個々のダイは、ウェハから切断されまたはダイシングされ、その後、集積回路としてパッケージ化される。当業者は、ウェハをダイシングし、ダイをパッケージングして集積回路を作る方法を知っているはずである。そのように製造された集積回路は、本発明の一部と考えられる。
【００３５】
図示され本明細書で説明された実施形態が、単に本発明の原理の例示であることと、さまざまな変形形態を、本発明の趣旨および範囲から逸脱せずに当業者が実施できることとを理解されたい。
【図面の簡単な説明】
【００３６】
【図１】例示的なＬＤＰＣ符号のパリティ検査行列を示す図である。
【図２】図１のパリティ検査行列から構成されるタナー・グラフを示す図である。
【図３】図１のパリティ検査行列の拡張である、例示的なＬＤＰＣ符号のパリティ検査行列を示す図である。
【図４】ｍが３と等しいときの図３の例示的なＬＤＰＣ符号のパリティ検査行列を示す図である。
【図５】準巡回ＬＤＰＣ符号の例示的な復号アルゴリズムを示す図である。
【図６】対数領域で演算することによって乗算演算を加算に変換する、準巡回ＬＤＰＣ符号の代替の復号アルゴリズムを示す図である。
【図７】図６の復号アルゴリズムによって使用される関数Φ（ｘ）を示す図である。
【図８】例示的なＬＤＰＣ符号のパリティ検査行列を示す図である。
【図９】図８のパリティ検査行列に対応する、本発明の特徴を組み込んだ例示的な復号器アーキテクチャを示すブロック図である。
【図１０】復号器アーキテクチャの諸態様をさらに詳細に示すブロック図である。
【図１１】ファイ・ノードを列サマーに接続するのにマルチプレクサ（Ｍｕｘ）要素を使用する、例の構成を示す図である。
【図１】
0005483875.tif 000014
【図２】
0005483875.tif 000015
【図３】
0005483875.tif 000016
【図４】
0005483875.tif 000017
【図５】
0005483875.tif 000018
【図６】
0005483875.tif 000019
【図７】
0005483875.tif 000020
【図８】
0005483875.tif 000021
【図１１】
0005483875.tif 000022
【図９】
0005483875.tif 000023
【図１０】
0005483875.tif 000024