(57)【要約】  回路はデータブロックの符号化及び復号のための行列生成を行毎に実行する。この回路は、広範囲の誤り訂正コーディング及び復号（ＥＣＣ）の用途に使用するのに適した高性能低密度パリティ検査（ＬＤＰＣ）行列の高速代数的生成を実行する。回路の動作は、ユーザ定義の性能条件に基づいて、初期パラメーターの単純集合からあらゆるサイズの行列を生成できるようにする数学的巡回環方法に基づいている。パリティ検査行列（Ｈ）を生成する主なステップは、ＲＧ行列構造の選択、群環要素の選択、行充填スキームによるＲＧ行列の部分行列を生成すること、部分行列の巡回配置によりＲＧ行列を生成すること、及びＲＧ行列から適当に選択した列を削除することによりパリティ検査行列を生成して所望の性能を達成しかつ次に行列を転置することである。回路は、先に生成したパリティ検査行列Ｈの行ベクトルから計算した初期ベクトルを受信し、該ベクトルを巡回シフトしてパリティ検査行列Ｈの所望の出力行を生成し、ＲＧ行列構造及び選択した行によってベクトルの処理順序を変更し、符号化すべき情報のベクトルを処理することによりデータの符号化又は復号を実行する。【選択図】図１
2010532129.tif 000002
【特許請求の範囲】
【請求項１】
誤り訂正コーディングのために群環パリティ検査行列Ｈの生成のための電子回路又は光回路のデータ処理装置により実行される方法であって、
（ａ）部分行列を含む適当な群環行列構造を選択するステップ、
（ｂ）適当な環要素及び適当な群要素を選択することにより前記部分行列のそれぞれについて初期ベクトルを与えるステップ、
（ｃ）行充填スキームに従って前記各ベクトルから前記部分行列を充填するステップ、
（ｄ）前記部分行列から前記群環行列構造を充填して群環行列ＲＧを与えるステップ、
（ｅ）前記ＲＧ行列を転置して前記パリティ行列Ｈを作成するステップ
からなり、更に、前記行列ＲＧから列を削除するステップ（ｆ）を有し、削除される列の数を、入力データの出力データに対する目標比率であるレートに関する所望の値により決定する方法。
【請求項２】
前記ステップ（ａ）において、前記ＲＧ行列が各行及び列にＮ個の正方部分行列を有し、Ｎが整数である請求項１に記載の方法。
【請求項３】
Ｎが２の累乗である請求項２に記載の方法。
【請求項４】
前記ステップ（ａ）において、前記ＲＧ行列構造が、前記ＲＧ行列のサイズを符号語長と等しくするようにしたものである請求項１乃至３のいずれかに記載の方法。
【請求項５】
前記ステップ（ｂ）において全部の前記部分行列における要素の数が、低密度パリティ検査（ＬＤＰＣ）行列を与える請求項１乃至４のいずれかに記載の方法。
【請求項６】
前記ステップ（ｂ）において、要素間の差分を、単一のベクトル内又はベクトル間のいずれにおいても全く繰り返さない請求項１乃至５のいずれかに記載の方法。
【請求項７】
前記ステップ（ｂ）において、ベクトルｎの長さ引く差分により定義される要素間の巡回間隔を、単一のベクトル内又はベクトル間のいずれにおいても全く繰り返さない請求項１乃至６のいずれかに記載の方法。
【請求項８】
前記ステップ（ｂ）において、ベクトルの数が、部分行列の数で割った符号語長に等しい請求項１乃至７のいずれかに記載の方法。
【請求項９】
前記ステップ（ｂ）において、前記ベクトルを構成する群環要素の選択を擬似ランダム式に実行する請求項１乃至８のいずれかに記載の方法。
【請求項１０】
前記ステップ（ｂ）において、ｎがＮで割った符号サイズとして定義される場合に、前記ベクトルの要素を０からｎ−１までの所定の部分行列の指数の範囲内で選択する請求項１乃至９のいずれかに記載の方法。
【請求項１１】
前記ステップ（ｂ）が、各要素がｎ要素の行ベクトルにおける１の位置を定義するバイナリー形式に前記ベクトルを変換することを含む請求項１乃至１０のいずれかに記載の方法。
【請求項１２】
前記ステップ（ｃ）が、線形巡回動作の使用により前記部分行列を充填することを含み、部分行列の各行を先の行から、整数で順方向又は逆方向に巡回した位置で充填する請求項１乃至１１のいずれかに記載の方法。
【請求項１３】
前記ステップ（ｃ）が、前記部分行列を充填することを含み、部分行列の各行を先の行から、等式により動的に決定される整数値で順方向又は逆方向に巡回した位置で充填する請求項１乃至１１のいずれかに記載の方法。
【請求項１４】
前記ステップ（ｆ）が、前記ＲＧ行列に共に重み０の列又は行がなくかつ低い列重み値の周りに偶発的に高い重み値がある重み分布からなる目標の列重み分布が達成されることを確実にすることによって良好な距離を達成するために前記ステップ（ａ）、（ｂ）、（ｃ）及び（ｄ）と組み合わせて実行される請求項１乃至１３のいずれかに記載の方法。
【請求項１５】
前記ステップ（ｄ）が、前記部分行列の巡回配置を行うことを含む請求項１乃至１４のいずれかに記載の方法。
【請求項１６】
前記ステップ（ｆ）において削除する列の選択が、ベクトルの作成に用いる規則と一致する代数的パターンによって決定される請求項１乃至１５のいずれかに記載の方法。
【請求項１７】
前記ステップ（ｆ）が、前記ＲＧ行列が可逆的でありかつ前記パリティ検査行列に重み０の列又は行がないことを確実にするために前記ステップ（ａ）、（ｂ）、（ｃ）、（ｄ）及び（ｅ）と組み合わせて実行される請求項１６に記載の方法。
【請求項１８】
前記ステップ（ｆ）を実行して、６サイクルのループ及び８サイクルのループのような短サイクルに関連するパリティ及びデータビットを取り除く又は最小にする請求項１乃至１７のいずれかに記載の方法。
【請求項１９】
前記ステップ（ｆ）が以下の各サブステップ、
（ｉ）群要素の差分集合を非０サポートを有するものと決定して群環符号を検査し、
（ii）前記差分集合が繰り返し要素を含まないように、前記検査符号の前記群要素を選択し、
（iii）非０サポートを有する群要素で、繰り返し（群）要素を有しない差分集合を有する該群要素を有する前記群環要素を用い、
（iv）前記群環要素に対応する前記行列のどの行を削除すべきかを決定することにより前記レートを選択すること
を含む請求項１６乃至１８のいずれかに記載の方法。
【請求項２０】
（ａ）部分行列を含む適当な群環行列構造を選択するステップ、
（ｂ）適当な環要素及び適当な群要素を選択することにより前記部分行列のそれぞれについて初期ベクトルを与えるステップ、
（ｃ）行充填スキームに従って前記各ベクトルから前記部分行列を充填するステップ、
（ｄ）前記部分行列から前記群環行列構造を充填して群環行列ＲＧを与えるステップ、
（ｅ）前記ＲＧ行列を転置して前記パリティ行列Ｈを作成するステップ
からなり、更に、前記行列ＲＧから列を削除するステップ（ｆ）を有し、削除される列の数を、入力データの出力データに対する目標比率であるレートに関する所望の値により決定する方法において、誤り訂正コーディングのためにパリティ検査行列Ｈを生成するように適合させた電子又は光回路。
【請求項２１】
前記回路が、前記ステップ（ｃ）についてバイナリーベクトルの連続的な巡回シフトのためのシフトレジスターと、前記シフトレジスターの動作を制御するカウンターとを備える請求項２０に記載の回路。
【請求項２２】
前記回路が、バイナリーベクトルの非０要素の位置の追跡を維持するカウンターを有し、かつ前記処理装置が前記カウンターを増分して次の各行を作成するように適合される請求項２０又は２１に記載の回路。
【請求項２３】
前記回路が非線形に前記カウンターを増分するように適合される請求項２２に記載の回路。
【請求項２４】
前記回路が前記カウンターを減分するように適合される請求項２３に記載の回路。
【請求項２５】
前記行列Ｈが２の累乗までの整数Ｎのサイズを有し、かつ前記カウンターが類似のビットサイズを有する請求項２２乃至２４のいずれかに記載の回路。
【請求項２６】
前記回路が、要素間の差分を単一のベクトル内又はベクトル間のいずれにおいても全く繰り返さないように前記ステップ（ｂ）を実行するように適合される請求項２０乃至２５のいずれかに記載の回路。
【請求項２７】
前記回路が、ベクトルｎの長さ引く差分で定義される要素間の巡回間隔を単一のベクトル内又はベクトル間のいずれにおいても全く繰り返さないように前記ステップ（ｂ）を実行するように適合される請求項２０乃至２６のいずれかに記載の回路。
【請求項２８】
データの符号化又は復号のための方法であって、以下の各ステップ、
（ｉ）請求項１乃至１９のいずれかに記載の方法により生成されるパリティ検査行列Ｈの行ベクトルから計算される初期ベクトルを受信し、
（ii）前記ベクトルを巡回シフトして前記パリティ検査行列Ｈの所望の出力行を生成し、
（iii）前記ＲＧ行列構造及び選択した前記行によって前記ベクトルの処理順序を変更し、
（iv）符号化すべき情報の前記ベクトルを処理し、
（ｖ）前記パリティ検査行列Ｈの次の行についてステップ（ii）乃至（iv）を繰り返す
ことからなる方法。
【請求項２９】
前記ステップ（ii）について、前記回路が、削除した列に到達する毎に追加の巡回シフトを追加し、次の削除していない列に基づいて行を作成する請求項２８に記載の方法。
【請求項３０】
前記ステップ（ｉ）及び（ii）について、それぞれにベクトルの要素の位置を格納するカウンターにベクトルを変換する請求項２８又は２９に記載の方法。
【請求項３１】
カウンターが１の各位置を直接追跡し、前記カウンターのブロックサイズが２の整数累乗で、バイナリー式の前記カウンターが各サイクルの最後に自動的にリセットする請求項３０に記載の方法。
【請求項３２】
前記カウンターが、次の所望の行に対応する所望のシフトによって増分し又は減分する請求項３０又は３１に記載の方法。
【請求項３３】
前記ステップ（ii）がシフトレジスターによって実行される請求項２８又は２９に記載の方法。
【請求項３４】
符号化又は復号のための電子又は光回路であって、前記回路が以下のステップ、
（ｉ）請求項１乃至１９のいずれかに記載の方法により生成されるパリティ検査行列Ｈの行ベクトルから計算される初期ベクトルを受信し、
（ii）前記ベクトルを巡回シフトして前記パリティ検査行列Ｈの所望の出力行を生成し、
（iii）前記ＲＧ行列構造及び選択した前記行によって前記ベクトルの処理順序を変更し、
（iv）符号化すべき情報の前記ベクトルを処理し、
（ｖ）前記パリティ検査行列Ｈの次の行についてステップ（ii）乃至（iv）を繰り返す
を実行するように適合された回路。
【請求項３５】
前記ステップ（ii）について、前記回路が、削除した列に到達する毎に追加の巡回シフトを追加し、次の削除していない列に基づいて行を作成するように適合された請求項３４に記載の回路。
【請求項３６】
前記回路がカウンターを有し、かつ、それぞれにベクトルの要素の位置を格納するカウンター値にベクトルを変換することにより前記ステップ（ｉ）及び（ii）を実行するように適合された請求項３４又は３５に記載の回路。
【請求項３７】
前記回路が、１の各位置を直接追跡し、前記カウンターのブロックサイズが２の整数累乗で、バイナリー式の前記カウンターが各サイクルの最後に自動的にリセットするように適合されたカウンターを有する請求項３６に記載の回路。
【請求項３８】
前記カウンターが、次の所望の行に対応する所望のシフトによって増分し又は減分する請求項３６又は３７に記載の回路。
【請求項３９】
前記回路がシフトレジスターを有し、かつ前記ステップ（ii）が前記シフトレジスターにより実行される請求項３４又は３５に記載の回路。
【請求項４０】
前進誤り訂正データストリームを生成するための通信機器であって、前記機器が符号化又は復号するために請求項２０乃至２７、又は３４乃至３９のいずれかに記載の回路を有する通信機器。
【請求項４１】
ＬＤＰＣ群環パリティ検査行列を用いて、データを符号化又は復号し、メモリ記憶の複雑さを低減する方法であって、先の行の巡回シフトであるプロトグラフ入力の対角行列要素が、隣接するメモリアドレス内に格納されて、可変ノード及び検査ノードの処理が少ない数の大きいメモリにアクセスできるようにした方法。
【請求項４２】
請求項４１の方法を実行するように適合されたＬＤＰＣエンコーダー又はデコーダー逐次ベクトルアーキテクチャ回路。
【請求項４３】
請求項４１の方法を実行するように適合されたＬＤＰＣエンコーダー又はデコーダー並列アーキテクチャ回路であって、各サイクルで行又は列のプロトグラフ入力全体を処理する回路。
【請求項４４】
請求項４１に記載の方法を実行するように適合されたＬＤＰＣエンコーダー又はデコーダー並列アーキテクチャ回路であって、各サイクルで多数の行又は列のプロトグラフ入力全体を処理する回路。
【請求項４５】
前記行列のリング巡回性を用いてレイヤーを定義し、又は拡張行列の行を前記レイヤー上にマッピングし、かつ次に或るレイヤーからの検査／可変更新を次のレイヤー上で用い、デコーダーの収束時間の向上を達成することにより、階層型確率伝搬を用いるように適合された請求項４３又は４４に記載の回路。
【請求項４６】
デジタル処理装置上で実行する際に請求項１乃至１９、２８乃至３３又は４４のいずれかの方法を実行するためのプログラムを格納するのに使用されるコンピュータ読み出し可能なメモリ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、誤り訂正コーディングのための群環式の低密度パリティ検査（ＬＤＰＣ）行列の生成に関する。
【背景技術】
【０００２】
誤り訂正符号は、雑音の多いチャネルでの通信やデータ記憶媒体への記憶の際に発生するエラーからデータを保護するのに用いられる。近年、「ターボ符号」や「低密度パリティ検査（ＬＤＰＣ）」符号のような繰り返し復号される符号は、十分に大きいデータのブロックについて動作する際に、「シャノン限界」と呼ばれる信頼性のある通信の基本的な限界の非常に近くまで動作し得ることが分かっている。しかしながら、これらの符号、特にＬＤＰＣ符号をより広く配置することは、それらの符号化及び復号の複雑さが比較的大きいことによって妨げられる。更に、最も効率的なＬＤＰＣ符号は、擬似ランダム法を用いて生成される大きな行列によって表される。このような行列は、代数的に作り直すことができず、それらを格納するのに大容量のメモリが必要である。従って、十分に決定論的な行列生成方法を用いて、ＬＤＰＣコーディングの複雑さを減らし、より小さいデータのブロック（ワイヤレス通信に適応可能）について符号の性能を向上させることが必要である。
【０００３】
大きな擬似ランダム行列は、処理電力及びメモリ条件がバッテリー電力及びコストに大きな影響を与える、携帯機器のような低出力機器には実用的でない場合が多い。そこで、このような機器のための方法は、例えば電気通信の基準ＧＳＭ及び３Ｇにおける畳み込み符号を、それらは必要な処理電力が少なくかつＤＳＰを必要とする場合とは反対にＡＳＩＣ上で実行し得ることから、符号化に用いている。
【０００４】
国際公開ＷＯ２００６／１１７７６９には、群及び環の選択がある符号行列を生成し、群環ＲＧを形成し、前記ＲＧから要素を選択し、かつ符号化及び復号行列を生成するという方法が記載されている。問題は、群環が行列の無限集合であり、それから適当な要素を選択しなければならないことである。その目的とする用途に適した特性を有する要素をどのように選択するかという指針は与えられていない。
【０００５】
また、米国出願公開第２００７／００３３４８０号公報及び国際公開ＷＯ２００４／０１９２６８に記載されているように、非群環方法が、ＬＤＰＣパリティ検査行列の生成に用いられている。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明は、ＬＤＰＣパリティ検査行列の生成のために性能及びメモリ構成の改善を達成することを目的としている。
【課題を解決するための手段】
【０００７】
本発明によれば、誤り訂正コーディングのために群環パリティ検査行列Ｈの生成のための電子回路又は光回路のデータ処理装置により実行される方法であって、
（ａ）部分行列を含む適当な群環行列構造を選択するステップ、
（ｂ）適当な環要素及び適当な群要素を選択することにより前記部分行列のそれぞれについて初期ベクトルを与えるステップ、
（ｃ）行充填スキームに従って前記各ベクトルから前記部分行列を充填するステップ、
（ｄ）前記部分行列から前記群環行列構造を充填して群環行列ＲＧを与えるステップ、
（ｅ）前記ＲＧ行列を転置して前記パリティ行列Ｈを作成するステップ
からなり、更に、前記行列ＲＧから列を削除するステップ（ｆ）を有し、削除される列の数を、入力データの出力データに対する目標比率であるレートに関する所望の値により決定する方法が提供される。
【０００８】
好ましくは、前記ステップ（ａ）において、前記ＲＧ行列が各行及び列にＮ個の正方部分行列を有し、ここでＮが整数であり、好ましくは、Ｎが２の累乗である。
【０００９】
好ましくは、前記ステップ（ａ）において、前記ＲＧ行列構造が、前記ＲＧ行列のサイズを符号語長と等しくするようにしたものである。また、前記ステップ（ｂ）において全部の前記部分行列における要素の数が、好ましくは低密度パリティ検査（ＬＤＰＣ）行列を与える。
【００１０】
ある実施例では、前記ステップ（ｂ）において、要素間の差分を、単一のベクトル内又はベクトル間のいずれにおいても全く繰り返さない。好ましくは、前記ステップ（ｂ）において、ベクトルｎの長さ引く差分により定義される要素間の巡回間隔を、単一のベクトル内又はベクトル間のいずれにおいても全く繰り返さない。
【００１１】
ある実施例では、前記ステップ（ｂ）において、ベクトルの数が、部分行列の数で割った符号語長に等しく、かつ、前記ステップ（ｂ）において、前記ベクトルを構成する群環要素の選択を擬似ランダム式に実行する。
【００１２】
ある実施例では、前記ステップ（ｂ）において、ｎがＮで割った符号サイズとして定義される場合に、前記ベクトルの要素を０からｎ−１までの所定の部分行列の指数の範囲内で選択する。
【００１３】
ある実施例では、前記ステップ（ｂ）が、各要素がｎ要素の行ベクトルにおける１の位置を定義するバイナリー形式に前記ベクトルを変換することを含む。
【００１４】
好ましくは、前記ステップ（ｃ）が、線形巡回動作の使用により前記部分行列を充填することを含み、部分行列の各行を先の行から、整数で順方向又は逆方向に巡回した位置で充填する。また、好ましくは、前記ステップ（ｃ）が、前記部分行列を充填することを含み、部分行列の各行を先の行から、等式により動的に決定される整数値で順方向又は逆方向に巡回した位置で充填する。
【００１５】
ある実施例では、前記ステップ（ｆ）が、前記ＲＧ行列に共に重み０の列又は行がなくかつ低い列重み値の周りに偶発的に高い重み値がある重み分布からなる目標の列重み分布が達成されることを確実にすることによって良好な距離を達成するために前記ステップ（ａ）、（ｂ）、（ｃ）及び（ｄ）と組み合わせて実行される。
【００１６】
好ましくは、前記ステップ（ｄ）が前記部分行列の巡回配置を行い、かつ、前記ステップ（ｆ）において削除する列の選択が、ベクトルの作成に用いる規則と一致する代数的パターンによって決定される。
【００１７】
ある実施例では、前記ステップ（ｆ）が、前記ＲＧ行列が可逆的でありかつ前記パリティ検査行列に重み０の列又は行がないことを確実にするために前記ステップ（ａ）、（ｂ）、（ｃ）、（ｄ）及び（ｅ）と組み合わせて実行される。好ましくは、前記ステップ（ｆ）を実行して、６サイクルのループ及び８サイクルのループのような短サイクルに関連するパリティ及びデータビットを取り除く又は最小にする。
【００１８】
ある実施例では、前記ステップ（ｆ）が以下の各サブステップ、
（ｉ）群要素の差分集合を非０サポートを有するものと決定して群環符号を検査し、
（ii）前記差分集合が繰り返し要素を含まないように、前記検査符号の前記群要素を選択し、
（iii）非０サポートを有する群要素で、繰り返し（群）要素を有しない差分集合を有する該群要素を有する前記群環要素を用い、
（iv）前記群環要素に対応する前記行列のどの行を削除すべきかを決定することにより前記レートを選択すること
を含む。
【００１９】
本発明の別の側面によれば、上述したいずれかの方法において誤り訂正コーディングのためにパリティ検査行列Ｈを生成するように適合された電子又は光回路が提供される。
【００２０】
本発明の更に別の側面によれば、データの符号化又は復号のための方法であって、以下の各ステップ、
（ｉ）上述したいずれかの方法により生成されるパリティ検査行列Ｈの行ベクトルから計算される初期ベクトルを受信し、
（ii）前記ベクトルを巡回シフトして前記パリティ検査行列Ｈの所望の出力行を生成し、
（iii）前記ＲＧ行列構造及び選択した前記行によって前記ベクトルの処理順序を変更し、
（iv）符号化すべき情報の前記ベクトルを処理し、
（ｖ）前記パリティ検査行列Ｈの次の行についてステップ（ii）乃至（iv）を繰り返す
ことからなる方法が提供される。
【００２１】
ある実施例では、前記ステップ（ii）について、前記回路が、削除した列に到達する毎に追加の巡回シフトを追加し、次の削除していない列に基づいて行を作成する。別の実施例では、前記ステップ（ｉ）及び（ii）について、それぞれにベクトルの要素の位置を格納するカウンターにベクトルを変換する。
【００２２】
ある実施例では、カウンターが１の各位置を直接追跡し、前記カウンターのブロックサイズが２の整数累乗で、バイナリー式の前記カウンターが各サイクルの最後に自動的にリセットする。別の実施例では、前記カウンターが、次の所望の行に対応する所望のシフトによって増分し又は減分する。
【００２３】
ある実施例では、前記ステップ（ii）がシフトレジスターによって実行される。
【００２４】
本発明の別の側面によれば、パリティ検査行列の行ベクトルを形成する初期ベクトルを受信した後に、上述したいずれかの方法のステップを実行するように適合された、符号化又は復号のための電子又は光回路が提供される。
【００２５】
また、本発明によれば、上述したいずれかの回路を備え、前進誤り訂正データストリームを生成するための通信機器が提供される。
【００２６】
本発明の更に別の側面によれば、ＬＤＰＣ群環パリティ検査行列を用いて、データを符号化又は復号し、メモリ記憶の複雑さを低減する方法であって、先の行の巡回シフトであるプロトグラフ入力の対角行列要素が、隣接するメモリアドレス内に格納されて、可変ノード及び検査ノードの処理が少ない数の大きいメモリにアクセスできるようにした方法が提供される。ある実施例では、ＤＰＣエンコーダー又はデコーダー逐次ベクトルアーキテクチャ回路が、この方法を実行するように適合される。
【００２７】
別の側面によれば、並列アーキテクチャ回路が、各サイクルにおいて行又は列のプロトグラフ入力全体で動作し、かつ好ましくは、前記回路が前記方法を実行するように適合され、各サイクルにおいて多数の行又は列のプロトグラフ入力全体で動作する。別の側面では、前記回路が、前記行列のリング巡回性を用いてレイヤーを定義し、又は拡張行列の行を前記レイヤー上にマッピングし、かつ次に或るレイヤーからの検査／可変更新を次のレイヤー上で用い、デコーダーの収束時間の向上を達成することにより、階層型確率伝搬を用いるように適合されている。
【００２８】
また、本発明によれば、デジタル処理装置上で実行する際に上述したいずれかの方法を実行するためのプログラムを記憶するのに使用されるコンピュータ読み取り可能な記憶装置が提供される。
【図面の簡単な説明】
【００２９】
【図１】本発明の符号化及び復号回路の動作を示す図である。
【図２】（ａ）図は４つの群環（ＲＧ）要素ベクトルを示す図であり、（ｂ）図は前記ベクトルからのＲＧ行列の生成を示すフロー図である。
【図３】ＲＧ行列のパリティ検査行列への変換を示す図である。
【図４】同じ初期ベクトルから生成した２つの異なるＲＧ行列を示す図である。
【図５】性能比較を表すプロットの集合を示す図である。
【図６】２つのＲＧ行列と対応するパリティ検査行列を示す図である。
【図７】性能比較を表すプロットの集合を示す図である。
【図８】行充填パターンを示す図である。
【図９】行列の特性を示すヒストグラムである。
【図１０】性能比較のプロットの集合を示す図である。
【図１１】２つの異なる行充填パターンを示す図である。
【図１２】ＲＧ行列及び３つの対応するパリティ検査行列を示す図である。
【図１３】行列の特性を示すヒストグラムである。
【図１４】性能比較を表すプロットの集合を示す図である。
【図１５】別の行充填パターンを示す図である。
【図１６】インラインＬＤＰＣ行列生成の際のＲＧ行列を示す図である。
【図１７】インラインＬＤＰＣ行列生成の際のＲＧ行列を示す図である。
【図１８】インライン行列生成のためのハードウエア回路のブロック図である。
【図１９】ハードウエアの別のシフトレジスターの構成を示すブロック図である。
【図２０】本発明の実施例の回路のハードウエア構成を示す図である。
【図２１】本発明の実施例の回路のハードウエア構成を示す図である。
【図２２】本発明の実施例の回路のハードウエア構成を示す図である。
【図２３】本発明の実施例の回路のハードウエア構成を示す図である。
【図２４】本発明によって得られる利点を示す図である。
【図２５】本発明によって得られる利点を示す図である。
【図２６】本発明によって得られる利点を示す図である。
【図２７】本発明によって得られる利点を示す図である。
【発明を実施するための形態】
【００３０】
図１を参照すると、本発明の回路は、変調前にデータブロックを符号化するために行毎に行列の生成を実行する。本発明の別の回路は受信機に設けられて、復号のために行毎の行列の生成を実行する。
【００３１】
前記回路は、広範囲の誤り訂正コーディング及び復号（ＥＣＣ）の用途での使用に適した高性能な低密度パリティ検査（ＬＤＰＣ）行列の代数的生成を高速で実行する。回路の動作は、ユーザ定義の性能条件に基づいて、初期パラメーターの簡単な集合からあらゆるサイズの行列を生成できるようにする数学的巡回環方法に基づいて行われる。
【００３２】
パリティ検査行列を事前に生成しかつ記憶させる必要がない。図１に示すように、初期パラメーターを与えることを必要とするだけである。前記回路動作は群環数学に基づいており、従ってシリアル、パイプライン型シリアル、逐次ベクトル及び部分並列を含む広範囲の実現可能なアーキテクチャに適している。これらのアーキテクチャの中で、この技術は逐次ベクトル及び部分並列の実施に特に利益がある。
【００３３】
データの符号化及び復号に使用し得るパリティ検査行列を生成するプロセスには、５つの主要なステップがある。
−ＲＧマトリックス構造の選択−所望の性能を生み出し得る適当な構造を選択する
−群環要素の選択−適当な環（ガロア体２（２進数）のような）を選択しかつスキームに従って選択した適当な群要素を選択する。
−部分行列の生成−幾つかの適当な行充填スキームを通してＲＧ行列の部分行列を生成する。このような行充填スキームは好ましくは線形かつ巡回的である。
−ＲＧ行列の生成−部分行列の巡回配置によりＲＧ行列を生成する。
−パリティ検査行列の生成−適当に選択した列をＲＧ行列から削除することによりパリティ検査行列を生成して所望の性能を達成し、かつ次に前記行列を転置する。
【００３４】
パリティ検査行列Ｈ（対応する生成／符号化行列に変換）を用いてデータを符号化するとき、符号化したデータ（メッセージビット及びパリティ検査ビットから構成される）は、伝送又は格納の際におけるエラーに抵抗し得ることが望ましい。このようなエラーのレベルは、通常所定の信号対雑音比におけるビット誤り率（ＢＥＲ）として表現される。符号化行列が良いほど、所定の信号対雑音比に対するＢＥＲが良くなり、かつ同じＢＥＲを達成するのに使用し得る信号対雑音比が低くなる。大部分の用途では、最小のＢＥＲが要求され、例えばワイヤレス電気通信の用途では１０-6である。
【００３５】
ＬＤＰＣ符号は、あらゆる線形ブロック符号として、所謂「ビットノード」（ＬＤＰＣ行列の列に対応）と「検査ノード」（ＬＤＰＣ行列の行に対応）との相互関係を示すタナーグラフにより表すことができる。
【００３６】
低いＢＥＲを達成するには、エラーが訂正され得るように、パリティ検査ビットとデータ（例えば、メッセージ）ビットとの間に良好な「相互リンク」があることが望ましい。これは、各パリティ検査ノードを多数のビットノードに接続すべきで、エラーの影響を受けたデータビット上に情報を含む多数のパリティビットによりエラーを訂正できるようにすることを意味する。同様に、パリティビット内のエラーは、多数のデータビットとのリンクを介して訂正することができる。短ループ、例えば「４サイクル」は、検査ノード及びビットノードが小さいサイクルでのみ一体にリンクされ、エラーを訂正できない可能性が高くなる場合に発生する。このようなタナーグラフ上でパリティ検査ノードとビットノードとを近い間隔でリンクする短ループは最小にすべきであり、これは群環要素を選択するための本発明の機構によって達成されている。実際、本発明において群環要素を注意深く選択することによって、４サイクルループ（２つの検査ノードと２つのビットノードのみを一体にリンクするループ）を完全に回避することができる。更に、適当な列の削除は、これらのループを含む列の組み合わせを取り除くことによって、６サイクルループ及び８サイクルループを最小にし又は取り除くことができる。
【００３７】
多数のエラーを訂正する符号の能力は、符号の距離として測る場合が多い。この距離は、２つの符号語が異なるというための最小数の位置（ビット）の尺度である。その間で２つの符号語が異なることになる位置が多いほど、エラーが単一の符号語に訂正され得るだけのメッセージをそのまま残すことになる可能性が増す。発生するエラーが多すぎる場合又は短い距離が存在する場合には、エラーを訂正することが不可能な場合がある。
【００３８】
パターンや列重み及び行重みの分布（パリティ行列のあらゆる所定の列又は行における非０要素の数）の無い不規則な行列は、距離がより大きくなる虞がある。このような不規則な行列は、より複雑な充填パターンを部分行列に用いると生成することができる。
【００３９】
このプロセスは、列の削除と注意深く結合させる必要があり、群環要素の選択は、得られるパリティ検査行列が重み０の列又は行を含まないことを確実にし、かつＲＧ行列が可逆的であることを確実にするように処理する。更に、各部分行列に異なる行充填パターンが存在し得る。
【００４０】
本発明を用いて作成されるパリティ検査行列は十分に決定論的であり、非常に少ない初期パラメーターに基づいて線順（line-by-line）に高速で生成することができる。更に、所謂「階段状構造」で用いたとき、線形時間での高速かつ単純な符号化に容易に用いることができる。「階段状」と結合させた行列の代数的特性が、符号化率の選択の柔軟性と結び付いた高速のコーディング及び復号速度、並びにランダムパリティ検査行列を維持するのに必要な指標付けメモリの相当な減少となる。これらの改善は、復号性能をランダムパリティ検査行列を用いることにより達成されるそれに近いものに維持しつつ、達成される。このような行列は、携帯可能なバッテリー駆動式ワイヤレス機器や、低複雑性誤り訂正と共に符号化率の微妙な選択及びシャノン限界に近い動作が望ましい他の機器について、特に有用であることが分かるであろう。
【００４１】
実施例
図１及び図２を参照すると、２０４の符号サイズで、サイズ４のＲＧ行列構造が選択されている。次に、４つのベクトル：Ｖ１，Ｖ２，Ｖ３及びＶ４で表される群環要素を選択する。
ＲＧ  行列サイズ：Ｎ＝４
符号（符号語）サイズ：ｎc＝２０４；部分行列サイズ：ｎ＝ｎc／Ｎ＝２０４／４＝５１；
Ｖ１＝［３］  Ｖ２＝［１６，２１］  Ｖ３＝［３３］  Ｖ４＝［０，１８，４０］
次にＶ1乃至ＶNのベクトルを次の一連の動作を通じて変形する。
ａ）ベクトル毎に０をｎで置き換える（ifＶ(i)＝０→Ｖ(i)＝ｎ）
ｂ）各ベクトルをｎから引く（Ｖ＝ｎ−Ｖ；）
次のように計算する。
ｎ＝５１；
Ｖ１＝５１−Ｖ１＝５１−［３］＝［４８］；
Ｖ２＝５１−［１６，２１］＝［３５，３０］；
Ｖ３＝５１−Ｖ３＝５１−［３３］＝［１８］；
Ｖ４＝５１−Ｖ４＝５１−［５１，１８，４０］＝［０，３３，１１］；
／／Ｖ４において、０は５１で置換えられている（減算前に）
【００４２】
指標付けを１から開始する（例えば、ＭＡＴＬＡＢにおけるように）場合、１の値を前記要素のそれぞれに加えるべきである。
【００４３】
このような場合：Ｖ1＝［49］,  Ｖ2＝［36,31］,  Ｖ3＝［19］,  Ｖ4＝［1,34,12］
上記動作は、群環論を用いた表記法に生成プロセスを一致させることになっている。
【００４４】
次に、特に図１を参照すると、前記ベクトルはバイナリー形式に変換される。ここで、Ｖ1乃至ＶNにおける各要素が、以下の動作を通じて、Ｖ1_binary,Ｖ2_binary…それぞれにおけるｎ個の要素の行ベクトルにおける「１」の位置を定義する。
ａ）全ベクトルをｎ個の０を含む行として開始する。（Ｖ_binary＝zeros（1,ｎ）；）
ｂ）Ｖ1乃至ＶNの要素により定義される位置に１を入力する。（Ｖ_binary（Ｖ(i)）＝1；）
特に図２を参照すると、４つのベクトルＶ１〜Ｖ４（概括的な参照番号１を付与）を用いて、関連するベクトルの巡回シフトにより、Ｎ個の正方巡回部分行列２：Ａ、Ｂ、Ｃ及びＤを生成する。
【００４５】
次に、このシステムは、上記部分行列、例えば
【数１】
2010532129.tif 000003
の巡回配置によりＲＧ行列３を作成する。
【００４６】
特に図３を参照すると、次に前記システムが、以下の動作を通じて、列の削除４及び転置５によりＲＧ行列３に基づいて、パリティ検査行列Ｈ，６を生成する。
【００４７】
ａ）行列ＲＧが可逆的であるかを検査−そうでない場合、初期ベクトルの別の組み合わせを選択
ｂ）ＲＧから適当な列を除去（選択）して所望の符号化率を達成
ｃ）前記行列を転置
前記パリティ検査行列のサイズは、ｎc−符号語サイズ、ｋ−メッセージサイズ（レート＝ｋ／ｎc）の場合に、（ｎc−ｋ）割るｎcである。
【００４８】
レート＝１／２の場合、ｋ＝ｎc／２であり、従ってＲＧからの列の半分を削除しなければならない。ここで、列を（最初のものから開始して）１つ置きに削除し、次に前記行列を転置する。
【００４９】
要約すると、前記システムは、
１）ＲＧ行列構造及び群環要素の選択で開始
２）対応するバイナリー行列を作成
３）それらのベクトルから正方部分行列を生成
４）前記部分行列の適当な配置により行列ＲＧを作成
５）ＲＧから列を除去
６）前記行列を転置する。
【００５０】
上記実施例に続いて、以下に本発明をより一般的な用語で説明する。
【００５１】
前記ＲＧ行列の最も簡単な構造は、次のように２つの異なる正方行列Ａ及びＢから構成される２×２である。
【数２】
2010532129.tif 000004
【００５２】
前記ＲＧ行列のサイズ（行又は列の長さ）は符号語長ｎcに等しい。従って、２×２ＲＧ行列構造の場合、部分行列Ａ及びＢはｎc／２のサイズを有することになる。
【００５３】
擬似ランダム初期ベクトル生成のプロセスについては、ＲＧ行列全体についてより均一にビットを展開するために４×４構造又はそれより大きいものを用いることが有利な場合が多い。基本的に、バイナリー符号については、ＲＧ行列の行（列）における部分行列の数が２の整数累乗である。従って、次の構造、２×２、４×４、８×８、１６×１６等が可能である。それぞれの場合、部分行列は巡回式に配置されることになる。一般に、前記方法はより高いガロア体について符号を用いることができる。前記ＲＧ行列において異なる数の部分行列及び異なる部分行列の配置も可能である。デコーダーにおけるハードウエア並列性の面から、Ｌ＞＞２の場合に、２×２行列をＬ×Ｌ行列に拡大し得ることは、Ｌ×Ｌ行列を２×２行列まで縮小することよりも重要である。
【００５４】
次の実施例は、４×４及び８×８ＲＧ行列の構造を示している。
【数３】
2010532129.tif 000005
【００５５】
基本的に、あらゆるＲＧ行列構造は通常、性能を損なうことなく、２×２構造に縮小することができる。例えば、サイズ９６の４×４構造の次のベクトル
Ｖ1＝（9,15,19）  Ｖ2＝（3,20）  Ｖ3＝（22）  Ｖ4＝（12）  （ＲＧ４×４）
により記述される符号は、２つのベクトル、
Ｖ1＝（3,20,33,39,43）  Ｖ2＝（12,46）  （ＲＧ２×２）
で表される２×２構造に縮小することができる。
【００５６】
ＲＧ４×４とＲＧ２×２の最初の行は同一である−前記行列間の差は、図４に示すように、以下の行に充填する方法にある。図５は、ＲＧ４×４行列及びＲＧ２×２行列に基づいて作成されたサイズ＝９６及びレート＝１／２の符号について性能比較（ガウシアンチャネル、ＢＰＳＫ変調）を示している。
【００５７】
バイナリー符号（ガロア体２）の場合、初期ベクトルが、ＲＧ行列に含まれる各部分行列の最初の行における「１」の値を有するビットの位置を定義する。次に、各部分行列の次に続く行を、巡回シフト（右側又は左側への逐次１ビットのシフト）又は最初の行の代替処理により作成する。同様の原則は、より高いガロア体内の符号にも適用される。
【００５８】
前記ベクトルを構成する群環要素の選択は、以下の制約条件で擬似ランダム式に実行される。
−ｎをＮで割った符号サイズとして定義した場合に、０からｎ−１までの所定の部分行列の指数の範囲内で要素を選択する。
−各ブロック（部分行列）における要素間の差分（間隔）及び巡回差分（ｎ引く間隔）は決して繰り返さない。
−或るブロックにおける要素間の差分及び巡回差分は別のブロックにおいて決して繰り返さない。
−あるベクトル及びそれに続くベクトルにおける要素間の差分及び巡回差分は決して繰り返さない。
−パリティ検査行列を疎（低密度）にするために要素の合計数を小さく維持する。
【００５９】
要素間における差分の繰り返しを回避することは、対応する符号における４サイクルを回避することに直接関連する。次の例は、これが符号の性能にどのように影響し得るかを示している。
【００６０】
ベクトル
Ｖ1＝（9,15,19）  Ｖ2＝（3,20）  Ｖ3＝（22）  Ｖ4＝（12）  （コード１）
で表される、先に説明したものと同じ符号を考える。コード１は、先に列挙した制約条件に従って設計されている。
【００６１】
対照的に、非常に似た符号（Ｖ1の１要素及びＶ2の１要素を変更することにより構成される）
Ｖ1＝（9,15,21）  Ｖ2＝（14,20）  Ｖ3＝（22）  Ｖ4＝（12）  （コード２）
は、要素間の差分の繰り返し、即ち
１５−９＝６（Ｖ1において）及び２１−１５＝６（Ｖ1において）及び２１−１４＝６（Ｖ2において）
を含む。
【００６２】
これらの繰り返しは、重要な性能の低下を生じる。
【００６３】
図６は、ＲＧ行列の構造を示し、それらの符号を、対応するパリティ検査行列Ｈ（Ｈ−ＲＧから列を１つおきに削除すること−符号化率＝１／２の場合、及びそれに続く行列の転置により作成）と共に表しており、図７は、それらのＢＰＳＫ変調を用いたガウシアンチャネルにおける性能を示している。
【００６４】
パリティ検査行列ＨはＲＧ行列から、ＲＧから多数の列を除去（選択）すること及びそれに続く行列の転置により作成される。符号化率は、ＲＧから削除（選択）した列の数で決定されるパリティ検査行列の形状によって定義される。一般に、Ｈ行列は、ｎCを符号語長（ＲＧのサイズに対応）としかつｋをメッセージ（データブロック）長さとした場合に、（ｎc−ｋ）÷ｎcのサイズを有する。従って、Ｈを得るためにＲＧから除去すべき列の数は、メッセージビットの数に等しい。符号化率は、ｋ／ｎCとして定義される。このように、符号化率が１／２の場合、ＲＧから列の半分を除去しなければならず、同様に符号化率が１／３の場合、列の３分の１を除去しなければならない等である。いずれの場合にも、このような行列は、削除が完了した後に転置しなければならない。
【００６５】
パリティ検査行列を作成するためにＲＧからどの列を削除すべきかという選択は、普通はパターンによって定義される。例えば、１／２の符号化率を有する符号の場合、列の半分を削除しなければならない。ここで、最も簡単かつ最も明確なパターンは、１列おきに削除することである。これによって、一様な行重み分布を有しかつ２つの列重みが交互に現れる行列Ｈが作成される。異なるパターンを選択することによって、列重み分布をより多様なものとし、かつ符号性能を改善することができる。性能は一般に、０又は１の重みを全く含まず、重み２の出現があったとしても僅かである列重み分布を生成する削除パターンによって、向上することになる。また、重み分布は、階段状パターンのような、符号化で採用されるあらゆる別の構造を考慮する必要がある。また、分布パターンは、符号の距離を最大にする幾分高い重み値を含む必要がある。良い分布パターンは、低い値の周囲に高い重み数が僅かにある重い分布を含んでいる。また、最大の列重みは、ハードウエアの実現に影響を与え、性能と実施とのバランスをもたらすことになる。
【００６６】
ここで、初期ベクトルの選択の場合のように、削除パターンもまた、ＬＤＰＣ符号において短サイクルを回避することに関係する場合がある。ベクトルの選択プロセスにおいて全ての４サイクルが排除されていると仮定すると、符号は、列削除パターンの適当な選択を介して６サイクル、８サイクルなどを除去することによって更に最適化することができる。別の方法は、ＲＧ行列を論理的に分析し、短サイクルの位置を計算し、これらの列を削除しかつ所望の符号化率が得られるまで繰り返し、削除した列をパターンに変換することである。列の削除が、最初にベクトルを選択した規則を破ることにならないように注意しなければならない。一般に、初期ベクトルの選択及び列削除パターンの選択の双方は、並行して最適化するべきである。１つの符号の性能に肯定的な強い影響を有するパターンが別の符号において性能を低下させる虞がある。０に等しい列重みを生じるパターンは、有効な符号を形成しないので、回避しなければならない。
【００６７】
図８は、上述したコード１に基づいて作成した２つのパリティ検査行列の構造を示している。コード１ａは、図６に示すコード１と同一であり、標準的な手法で−ＲＧから列を最初のものから開始して１つおきに削除することにより（削除した列の順序：１、３、５、７、９、１１、１３、１５、１７、…、９５）作成した。対照的に、コード１ｂは、異なる列削除パターンを用いて、最初の３つの隣接する列をＲＧに残し、かつ次の３つの隣接する列を削除する（例えば、４、５、６、１０、１１、１２、１６、１７、１８、…、９６）ようにして作成した。いずれの場合も、削除後に行列を転置した。図９は、これらの行列について計算した列重み分布と行重み分布とを比較している。コード１ｂがより多様な列重み分布を有し、ガウシアンチャネルにおいてより良い性能を発揮することは明らかである（図１０）。行重みは、コード１ａ及びパリティ検査行列生成方法の直接的な結果であるコード１ｂの双方について一定である。行重み分布を多様化する１つの方法は、後述するように、ＲＧにおける行充填パターンを変更することによるものである。
【００６８】
ＲＧにおいて行充填パターンを変更することは、行列をより不規則なものにすることによって、符号の性能を更に改善することができる。標準的な巡回行充填は常に規則的な行重みを有する行列を作成するが、列重みは列削除パターンによって変化し得る。また、行重み分布に不規則性を導入するために、行充填パターンは標準巡回パターンから異なるものでなければならない。
【００６９】
例えば、１より大きい増分を用いる巡回パターンが可能であり、良い行分布パターンを生成することができる。４×４ＲＧ行列における他のこのように非標準的な行充填は、図１１に示すように、部分行列Ａにおいて１番目の行から、部分行列Ｂにおいて２番目の行から、部分行列Ｃにおいて３番目の行から、及び部分行列Ｄにおいて４番目の行から始めて、３つおきの行毎に「１」の代わりに「０」を入力することによって達成することができる。
【００７０】
多くの様々な行充填パターンが可能である。一般に、０に等しい列重み又は行重みとなるパターンは、そのような行がそれに続く列削除段階において削除される場合以外は、非可逆的ＲＧ行列を作成する他のパターンと同様に、回避すべきである。行充填パターンは、初期ベクトルの選択及び列削除のパターンと並行して最適化すべきである。例えば、前述したコード１は、パターン１を用いたとき、非可逆的ＲＧ行列を生じることになるので、有効な符号を形成しない。従って、有効な符号を作成するためには、異なるベクトルの集合、例えば、
コード３；パターン１を使用：
Ｖ1＝（19）  Ｖ2＝（10,15）  Ｖ3＝（3,5,12,13）  Ｖ4＝（4,8）
を選択しなければならない。
【００７１】
コード３及びパターン１に基づいて形成されるＲＧ行列が、符号化率＝１／２の３つの符号を表す対応パリティ検査行列と共に、図１２に示されている。コード３ａは、ＲＧから１つおきに列を削除することにより（前述したコード１ａにおけるように）形成し、コード３ｂはコード１ｂについて先に用いたものと同等の列削除パターンを用いて（最初の３つの隣接する列をＲＧに残し、次の３つの隣接する列を削除するなど）作成したのに対し、コード３ｃは、次の列：１、３、４、８、…など（８つの列毎に繰り返す）を削除することによって作成した。図１３は、コード３ａ、コード３ｂ及びコード３ｃについて計算した列重み分布及び行重み分布を示している。パターン１は、標準的な列削除パターン（コード３ａ）の場合でさえ、不規則な列重み分布及び行重み分布を生じることが明らかである。予想されるように、非標準的に行充填パターンを非標準的列削除パターンと組み合わせることによって、重み分布（コード３ｂ及びコード３ｃ）がより多様なものになる。ここで、しかしながら、コード３ｃの性能がコード３ａの性能より良いにも拘わらず、コード３ｂ（コード１ｂについて先に用いたものと同一の列削除パターンを有する）は、コード３ａよりも性能が悪い。これは、コード１ａ及びコード１ｂついて先に説明した場合と対照的であり、更に、ビット誤り率を最小にするためには、全パラメータ（初期ベクトル、列削除パターン及び行充填パターン）を同時に最適化しなければならないことを証明している。この場合、コード３ｃは、図１４に示すように最高の性能に最適化されている。
【００７２】
実際には、ＲＧ行列を作成するのに使用できる非常に様々な異なる行充填パターンがあり、図１５には幾つかの変形例が示されている。これらのパターンは、各部分行列において同じ又は異なるものであり得る−主な制約条件は、ＲＧ行列がＧＦ（２）において可逆的でなければならいこと、及びパリティ検査行列Ｈが０の重みを有する列又は行を有しないことである。これは、行充填パターンという意味で柔軟性があるが、列削除後のパリティ検査行列が適当な初期ベクトルの選択での規則及び列重み分布での規則を確実に破らないことを条件としている。
【００７３】
数学的根拠
以下に、本発明の利点の数学的根拠を説明する。
【００７４】
短サイクルを回避すること
この部分は、検査行列のグラフにおいて短サイクルをどのように回避するかについての方法を説明する。数学的証明を示す。
【００７５】
特に、群環要素ｕについて、それが群要素の点から、その対応する行列Ｕがそのグラフで短サイクルを有しないようにその式に現れる必要かつ十分な条件を説明する。また、これらの条件が、ｕから構成される群環行列Ｕに短サイクルがいつ及びどこで発生し得るかを決定し、これらの短サイクルを、Ｕから符号を構成する際に回避することが可能である。
【００７６】
符号を構成するための単位導出法が群環ＲＧのどのモジュールＷを選択すべきかについて完全な自由を有することに注意すべきである。この部分は、短サイクルが一般に起こり得る場合を決定し、従ってこれらの短サイクルを回避するように、モジュールＷを選択することができる。モジュールＷの選択によって、生成行列及び検査行列が決定される。
【００７７】
一般
ＲＧを、環Ｒについて群Ｇの群環を表すこととする。ｕ∈ＲＧを、符号を生成する又は検査することとする。ＧをＧ＝｛ｇ1、ｇ2、…、ｇn｝によりリストすることとする。ＲＧにおいて、
【数４】
2010532129.tif 000006
とする。
【００７８】
非０係数を有するｕで発生する各（異なる）対のｇi，ｇjについて、（群）差分ｇiｇj-1，ｇjｇi-1を形成する。すると、ｕの差分集合ＤＳ（ｕ）が、このような全ての差分で構成される。よって、
【数５】
2010532129.tif 000007
ｕの差分集合が群要素からなることに注意する。
【００７９】
定理１．１  行列Ｕは、ＤＳ（ｕ）が繰り返し（群）要素を有しないときに限り、そのグラフに短サイクルを有しない。
【００８０】
証明：
Ｕの行は順にｕｇi、ｉ＝１，…，ｎ，に対応する。
すると、Ｕは４サイクルを有する。
⇔
幾つかのｉ≠ｊ及び幾つかのｋ≠ｌについて、ｕｇi及びｕｇjにおけるｇm，ｇlの係数は非０である。
⇔
【数６】
2010532129.tif 000008
かつ
【数７】
2010532129.tif 000009
⇔
【数８】
2010532129.tif 000010
かつ
【数９】
2010532129.tif 000011
⇔
ＤＳ（ｕ）は、gkgi-1gigl-1=gkgl-1及びgkgj-1gl-1=gkgl-1の双方を含む。これは、ＤＳ（ｕ）が繰り返し要素を有するときに限り起こる。
【００８１】
繰り返し要素
ここでｕを、ＣＤ（ｕ）が繰り返し要素を有するようなものとする。
【００８２】
よって、表示されるαiが非０である場合に、u=…+αmgm+αrgr+αpgp+αqgq+…であり、従ってgmgr-1=gpgq-1となる。短サイクルを生じる要素が表示され、要素ｇm、ｇr、ｇp、ｇqが必ずしもＧのリスティングの順序でなくて良いことに注意する。
【００８３】
要素のグラフ及び従って非０の係数に関心が有るので、非０係数を係数１で置き換える。よって、u=…+gm+gr+gp+gq+…と書くことにより、gmgr-1=gpgq-1となる。
【００８４】
あるｐ，ｑがｍ，ｒの１つとなり得る場合でそれをｕの等式にリストすべきでない場合を組み込む。
【００８５】
すると、
【数１０】
2010532129.tif 000012
かつ、
【数１１】
2010532129.tif 000013
となる（ugm-1gp=ugr-1gq及びugp-1gm=ugq-1grに注意する）。
【００８６】
よって、短サイクルを回避するには、最初の行を用いる場合には、Ｕにおいてｇm-1ｇp又はｇp-1ｇm行により決定される行を用いず、又は一般に、ｇi行が発生する場合、ｇiｇm-1ｇp行及びｇiｇp-1ｇm行が発生してはならない。
【００８７】
同様に、ＣＤ（ｕ）が繰り返し要素を有するとき、Ｕにおける或る列を回避することによって、短サイクルなしで行列を完了することが可能である。
【００８８】
特別な場合
Ｓ＝｛ｉ1，ｉ2，…，ｉr｝を非負不等整数の集合とし、かつｎをｊ＝１，２，…，ｒの全てについてｎ＞ｉjの整数とする。
【００８９】
すると、Ｓｍｏｄ  ｎの巡回差分集合が、DS(n)={ij-ik mod n|1≦j,k≦r,j≠k}によって定義される。これは、おそらくは繰り返し要素を有する集合である。
【００９０】
例えば、Ｓ＝｛１，３，７｝及びｎ＝１２の場合、ＤＳ（１２）＝｛２，６，４，１０，６，８｝となる。
【００９１】
｜Ｓ｜＝ｒの場合、｜ＤＳ（ｎ）｜＝ｒ（ｒ−１）となる。
【００９２】
Ｃnがｇにより生成される場合の群環ＲＣnを考える。αij≠０で、u=αi1gi1+αi2gi2+…+αirgir∈RCnとする。Ｓ＝｛ｉ1，ｉ2，…，ｉr｝に設定し、かつｕの巡回差分集合ｍｏｄ  ｎ、ＣＤ（ｕ）を、ＣＤ（ｕ）＝ＤＳ（ｎ）ということにより定義する。
【００９３】
この差分集合が、上記「一般」の部分で定義した差分集合における群環要素の指数の集合（等式を非負の形で書いたとき）である。
【００９４】
ＵをｕのＲＧ行列とする。ＵはＣnの要素のリスティングに依存し、ここではナチュラルリスティングを選択する。
【００９５】
定理１．２  Ｕは、ＣＤ（ｕ）が繰り返し要素を有しないときに限り、そのグラフに４サイクルを有しない。
【００９６】
証明：この証明は、定理１．１から続くものである。
Ｇ＝Ｃn×Ｃmを、ｇ，ｈによりそれぞれ生成される巡回群Ｃn，Ｃmの直積とする。
Ｇの要素を1,g,g2,…,gn-1,h,hg,hg2,…,hgn-1,…,hm-1,hm-1g,…,hm-1gn-1によりリストする。
このリスティングを用いてＲＧの要素を書き出し、従ってu=a0+h(a1)+…+hm-1am-1を、各ａiがａi-1∈Ｃnの場合のＲＧにあるものとする。
Ｓをａ0，ａ1，…，ａm-1において発生する全ての指数からなる集合に設定し、かつＣＤ（ｕ）＝ＤＳ（ｎ）と定義する。
【００９７】
すると、定理１．１を用いて以下を証明することができる。
【００９８】
定理１．３  Ｕは、ＣＤ（ｕ）が繰り返し要素を有しないときに限り４サイクルを有しない。
【００９９】
繰り返し要素（特別な場合）：
ＣＤ（ｕ）が繰り返し要素を有する系を得ることができる。
【０１００】
u=…+gm+gr+gp+gq+…とすることにより、ｍ−ｒ＝ｐ−ｑ  ｍｏｄｎとなる。一般性を失うが、ｐ＞ｍと仮定する。
或るｐ，ｑがｍ，ｎの１つであり得るような場合でｕの等式にリストすべきでない場合を組み込む。
すると、ｐ＞ｍの場合に、
【数１２】
2010532129.tif 000014
であり、かつｎ＞ｎ＋ｍ−ｐ＞０について、
【数１３】
2010532129.tif 000015
となる。
（ｍ−ｐ＝ｒ−ｑ  ｍｏｄ  ｎであることにより、ugp-m=ugq-r=ugn+q-rかつugn+m-p=ugn+r-q=ugr-qであることに注意する。）
【０１０１】
よって、短サイクルを回避するには、最初の行を用いる場合にはＵにおいてｐ−ｍ行又はｎ＋ｍ−ｐ行を使用せず、又は一般に、ｉ行が発生する場合には、ｉ＋ｐ−ｍ行又はｉ＋ｎ＋ｐ−ｍ行が発生してはならない。
【０１０２】
距離を改善する
次に、ｕｖ＝０かつrankｕ＋rankｖ＝ｎであるように、２つの要素ｕ、ｖ∈Ｚ2Ｃnを考える。Ｕ、Ｖをそれぞれｕ、ｖに対応する対応ｎ×ｎ行列とする。
【０１０３】
よって、符号は
【数１４】
2010532129.tif 000016
であり、かつｙｖ＝０のときに限り、ｙ∈Ｃである。
【０１０４】
ここで、y=ΣαigiがＣにおける一般的要素であるとする。ｙがどのくらい短かくなり得るかということに関心がある。より詳細にいえば、ｓｕｐｐ（ｙ）は非０αi∈ｙの数である。よって、Ｃの距離は、
【数１５】
2010532129.tif 000017
である。
【０１０５】
ｖが、
【数１６】
2010532129.tif 000018
の形をとる。Ｚ2を精査しているので、各係数は０又は１のいずれかである。
【０１０６】
すると、ｙｖ＝０のときに限り、ｙ∈Ｃとなる。よって、ｙｖにおいてｇk，ｋ＝０，１，…，ｎ−１の係数を考えることにより、次の等式が維持されるときに限り、ｙ∈Ｃを得る。
【数１７】
2010532129.tif 000019
【０１０７】
ここで、添え字はｍｏｄ  ｎと解される。これの非０の解に関心がある。予想通り得られた行列は巡回行列である。これは次のように簡単に書ける。
【数１８】
2010532129.tif 000020
【０１０８】
この配列／行列においてあらゆる非０要素が同じ回数発生することに注意する。
【０１０９】
最初の列にｓの非０がある場合には、全ての列にｓの非０がある。
【０１１０】
最短の距離について考える際、最短の非０語において係数α0が０でないと仮定することができる。
【０１１１】
ここで、群環ＲＧにおいてｕｖ＝１の場合に、単位導出符号Ｃが得られるとする。Ｇ＝ｇ1，ｇ2，…，ｇnとし、かつＷがS={gi1,gi2,…,gir}によりモジュールとして生成されるとする。ｙｖにおいて¬（ｇk∈Ｓ）である各ｇkの係数が全て０であるときに限り、ｙ∈Ｃである。
【０１１２】
次に、ｙを一般系でα1ｇ1＋α2ｇ2＋…＋αnｇnと書き、ｙｖを考える。ｙｖにおけるＳにないＧにおける各要素の係数が全て０であるという事実から、変数αiにおけるｒの同次式の系が得られる。
【０１１３】
従って、Ｇ−Ｓにおける各要素に対応して、等式が得られる。
【０１１４】
各同次式は、ｙｖにおける各ｇik∈Ｓの係数を考えることから導出される。
【０１１５】
符号の距離は、この方程式系の最短の非０の解である。
【０１１６】
次に、最短の距離がｓで、{ali1,αi2,…,αis}が非０でありかつ他の全てのαjが０であるときに発生するとする。
【０１１７】
これらの非０係数は前記方程式系で発生する。
【０１１８】
これら非０の解が起こる等式を見て、注意深く選択することによりＳから幾つかのｇkを削除する。式が１つ多い新しい方程式系が得られる。この新しい系は、前の系を含むので、この新しい系の全ての解が前の系の解であることにより、新しい系の距離は少なくとも前の系の距離と同じ大きさである。
【０１１９】
次に、前の等式を再考しかつ{ali1,αi2,…,αis}が起こる場合を知ることができる。これらのいずれもが発生しない全ての式を取り除くことができ、この結果余分な要素をＳに追加することになる。
【０１２０】
インライン（行毎の）ＬＤＰＣ行列生成
ＬＤＰＣ行列生成の代数的方法の重要な利点の１つは、そのＬＤＰＣ行列をオンデマンドで即ち要求が有り次第に、又は特定の行又は列でさえオンデマンドで生成する能力である。従来の符号化動作では、符号化すべき情報の正しいサイズのブロックを符号化行列に掛けて、得られたデータを伝送し又は格納する。このような行列動作は線順に実施することができ、従って必要とするメモリ又はデータレジスターの量が大幅に減少する。本発明は、以下に記載するように、そのような線順の実施に適用することができる。
【０１２１】
符号化処理において、生成／符号化行列（ｎc−符号語サイズ、ｋ−データブロックサイズの場合に、サイズｎc×ｋを有する）が、ガウスの消去法のような適当な行列変換により、対応するＬＤＰＣ／パリティ検査行列（（ｎc−ｋ）×ｎのサイズを有する）から最初に得られる。次に、符号化すべきデータのブロックのそれぞれを生成行列に掛け、その結果データビット及びパリティ検査ビッドを含む符号語を得る。行列積処理において、生成行列の各列に順に、（ｎc−ｋ）2に比例する処理コストでデータブロックを掛ける。この計算コストは、いわゆる「階段状構造」（D.J.C MacKay、“Information theory, inference and learning algorithms”, Cambridge University
Press 2003に記載されるような）を用いることにより低減することができる。このような場合、次数（ｎc−ｋ）のコストでデータを符号化するためにＬＤＰＣ行列を直接用いることができるので、行列変換の必要がない。標準的な符号化技術及び「階段状」手法を用いた方法のいずれにおいても、パリティ検査（又は生成）行列をライン毎に（line-by-line）生成することは、常に行列全体をメモリに格納する必要がなくなるので、有利である。この「階段状」手法によって、高速（線形時間での）符号化及び処理を実行するのに必要な処理電力が少ないという更なる利点が得られる。このように、高速でメモリ効率が良くかつ電力効率の高い誤り訂正コーディングに適したライン毎のＬＤＰＣ行列生成処理のためのハードウェア実装を以下に説明する。
【０１２２】
パリティ検査行列Ｈの行は、ＲＧ行列から列を選択することに等しい。従って、適当なＬＤＰＣ行列を生成するのに選択したパラメータを用いて、ＲＧ行列の所望の列及び従ってパリティ検査行列の所望の行を生成する必要がある。
【０１２３】
図１６及び図１７を参照して、サイズ４８×４８のＲＧマトリックスが次のパラメータを用いて生成される簡単な実施例を考える。
４×４部分行列形式
行の巡回充填
列の削除なし（簡単のため）
ベクトル：Ｖ1＝［４，９］；  Ｖ2＝［５］；  Ｖ3＝［１，７］；  Ｖ4＝［１１］；
ＲＧの列において１の位置を定義する新たな４つのベクトルＶA、ＶB、ＶC、ＶDを簡単に見つけることができる（Ｈにおける行に相当）。
【数１９】
2010532129.tif 000021
【０１２４】
従って、
【数２０】
2010532129.tif 000022
【０１２５】
ここで、以下の新たに定義されるベクトルからインライン行列生成処理を開始することができる。
ＶA＝［5,10］；  ＶB＝［9］；  ＶC＝［1,7］；  ＶD＝［3］；
これらは、パリティ検査行列Ｈの行における１の位置を定義している。
【０１２６】
まず、前記ベクトルをそのバイナリー形式に変換する。ここで、
【数２１】
2010532129.tif 000023
【０１２７】
ＬＤＰＣパリティ検査行列の最初の行（ＲＧ行列における最初の列に相当）は、従って次のように与えられる。
【数２２】
2010532129.tif 000024
【０１２８】
パリティ検査行列の次の行を、各ブロック内のベクトルの定義された行シフトにより形成する。この実施例では、巡回シフトにより次のようになる。
【数２３】
2010532129.tif 000025
次に、
【数２４】
2010532129.tif 000026
等々となる。
【０１２９】
巡回シフトは、部分行列ブロックの最後に至るまで続ける。次に、選択した構造によって、ベクトルの配置を変更する必要がある。この実施例では、次のように変更される。
【数２５】
2010532129.tif 000027
【０１３０】
それに続く各行をこの原則に基づいて、行列全体が使用されるまで生成し、かつ次に全部を繰り返す。
【０１３１】
全ての場合において、ＲＧ行列からの幾つかの列を、転置する前に削除して、所望の符号化率及び性能を達成する。どの列を削除するべきかを選択するために用いたのと同じ等式又は方法をインライン実装に適用することができる。これを達成する有効な方法は、削除した列に到達する毎に追加の巡回シフト（又はどの行充填方法を用いたにせよ）を追加し、次の削除していない列に基づいて行を作成することである。
【０１３２】
ハードウエア
パリティ検査行列Ｈを生成することにより、行列を記憶させ又は生成することなく符号化及び／又は復号を実行するハードウエア回路により使用するために最適な初期ベクトルを選択することができる。前記行列は前記回路により生成する必要がなく、先に生成しかつ試験した行列に基づいて、製造時又は初期化時にプログラムすることができる。
【０１３３】
図１８は、４つのシフトレジスターを用いて１の位置を記憶させる回路を示している。この回路の構成要素は次の通りである。
１１、カウンターにより制御され、バイナリーベクトルの連続的な巡回シフトを実行するシフトレジスター。
１２、符号サイズ及び符号化率に関する情報を前記カウンターに入力する。
１３、前記カウンターがブロックの配置を制御する（符号サイズ及び現在の行番号に基づく）。
１４、出力はパリティ検査行列Ｈの現在の行である。
【０１３４】
この実装は、利用可能なあらゆるＬＤＰＣ生成パラメーターと互換性がある。
【０１３５】
別の実施例では、より小型の回路が１のそれぞれの位置を直接追跡する単一のビットカウンターを有する。これは、ＬＤＰＣ行列の疎特性によって、シフトレジスターを用いるよりも、必要とするメモリ及び処理電力が大幅に少ない。特に、ブロックサイズが２の整数累乗である場合、バイナリカウンターが各サイクルの最後に自動的にリセットするので好都合である。
【０１３６】
別の方法は、部分行列ブロック長さに等しい単一のシフトレジスター（又は単一のブロックにおいて１を追跡するカウンター）を用いて各ブロックについて系を巡回することである。この方法は、追加のレジスター（カウンター）を含んで列又は行番号の追跡を維持し、かつ図１９に示すようにブロック毎に所望の行を生成することになる。
【０１３７】
ＬＤＰＣハードウエア実装
メモリ構成
従来のＬＤＰＣの符号化及び復号において、問題は、検査ノード及び可変ノードの処理のためにメモリアドレッシングの複雑さが要求されることである。
【０１３８】
また、単一のクロックサイクル内で多数の行及び列の処理を同時に実行することが知られている。
【０１３９】
図２０及び図２１は、このような並列ハードウェアアーキテクチャに関する現在の技術状態を示している。図２０の構成は、行又は列全体について同時に動作する。図２１のそれは、プロトグラフの多数の行及び多数の列について同時に動作する。これによって、シリアル実装と比較して、実質的なスループットの増加又はレイテンシーの減少が得られる。しかしながら、これは非常に複雑なメモリのアドレッシングの対価として得られるものである。本発明では、この複雑さが実質的に低減される。
【０１４０】
本発明のパリティ検査行列は、従来の方法よりも大きい構造を有する。これは、プロトグラフの行ｍが行ｍ−１の巡回シフトであるという追加の特性を有する。これは、複雑さの低いデコーダーアーキテクチャを得る上で重要なことを暗示している。非リング型（non-ring）アーキテクチャでは、主要な問題の１つが、ＶＮＵ及びＣＮＵプロセッサーによる並列読み取り及び書き込みが別個のメモリに確実に向けられるようにすることである。これは、リング型プロトグラフの普通の特性である。実際、これは、図２１に示すアーキテクチャのメモリ構成がＭ／Ｒ×Ｎ／Ｒの別個のメモリのアレイからＮ／Ｒのアレイへと縮小することを意味している。これは、（ａ）ＡＳＩＣルーティングの輻輳を大幅に低減すること、（ｂ）多くの小さいメモリよりも少ない数の大きなメモリがより面積効率的であるという２つの効果を有する。
【０１４１】
以下の３×３の例を考える。
【数２６】
2010532129.tif 000028
【０１４２】
多数の行及び列で同時に動作する従来の並列アーキテクチャは、上述したようにかつ図２２に示すように、Ｎ×Ｍまでのメモリを有することになる。これは、全てのＡXXが同じアドレスでアクセスされるという事実を利用しておらず、集合｛Ａ’，Ｂ’，Ｃ’｝は各ＶＮＵ及び各ＣＮＵによってアドレスされる。メモリの断片化は、全てのＡ、Ｂ及びＣを一緒に広いメモリに格納し、かつ本発明の並列アーキテクチャについて以下に示すように配線によって元のメモリアレイの位置に分配することによって低減することができる。
【０１４３】
図２２は、群環並列アーキテクチャのメモリ構成を示しており、１つの検査ノードプロセッサー／可変ノードプロセッサーが、１サイクル内でプロトグラフからの行又は列の全体に動作する。
【０１４４】
図２３は、群環並列アーキテクチャのメモリ構成を示しており、Ｍ／Ｒ検査ノードプロセッサー及びＮ／Ｒ可変ノードプロセッサーが、１サイクル内でプロトグラフからの多数の行又は列全体に同時に動作する。
【０１４５】
例えば図２３に示すアーキテクチャは、３つの物理的メモリを用いて、９つの語のベクトルを読み取りかつ書き込みする。例えば、Ａ00、Ａ11及びＡ22が同じアドレスに記憶され、かつ３つの語の幅のデータバスを形成する。これによって、３つの物理的メモリによりサイクル毎に９つのメッセージを供給できる。これによって、このようなアーキテクチャメモリ構成のメモリ複雑さは、より簡単な逐次ベクトルアーキテクチャと同様のレベルになる。
【０１４６】
リング型構造を逐次ベクトルアーキテクチャに適用することは、Ｒ、拡張サイズの整数倍での更なる並列性を可能にする。実際、メモリ幅はｋ×Ｒメッセージに増加し、ｋの対角プロトグラフ入力を同時に処理できるようにする。ｋ→Ｎの限界で、完全な対角線を単一のサイクルで処理する。
【０１４７】
８０２．１１ｎプロトグラフがリング循環型でないにも拘わらず、そうであると仮定した場合、２つのリングエンハンスメントのメモリ構造を見つけることができる。図２３のアーキテクチャについては、２つの対角線を構成する階段状に区分けすることができ、残りが１２の対角線を有する１２×１２のプロトグラフとなることに注意する。これらは、１つにすると８つまでの列入力が提供される。以下の表では、従来方法の性能が最初の２列に示され、本発明の性能が第３列及び第４列に示されている。
【０１４８】
【表１】
2010532129.tif 000029
【０１４９】
階層型確率伝搬
階層型確率伝搬（ＬＢＰ）の適用について考えると、これの本質は、パリティ行列がレイヤーからなり、かつ或るレイヤーでの検査／可変更新が次のそれに使用されることである。このようにして、繰り返しによるよりも、外部情報によって全てのレイヤーが改善される。多くのレイヤーを有する行列については、収束時間が劇的に改善される。群環行列はナチュラルレイヤー化を有し、各群の行が１つのレイヤーである。群環逐次ベクトルアーキテクチャは、クロックサイクル毎に幾つかのレイヤーを部分処理することに依存するので、ＬＢＰを完全には利用していない。図２２の群環アーキテクチャは、レイヤー内の展開行列の行を処理することにより、ＬＢＰを完全に利用する。図２３の群環アーキテクチャは、展開行列においてレイヤーを行とするように再定義することによってのみであるが、ＬＢＰ上にマップすることができる。
【０１５０】
本発明のメモリ構成及びメモリアドレッシングの利益は、ハードウェアで容易に実行することができ、ＡＳＩＣのルーティングの輻輳を減らす上で実質的な利点を有する。これは特に、大きなブロックサイズ又は非常に高いスループットを必要とするシステムに関連する。また、この技術は、適応コーディング技術として適しており、可変な符号化率及びブロックサイズを可能にする。
【０１５１】
簡単化したメモリアドレッシングによって、エンコーダー／デコーダーに必要なシリコン面積が実質的に低減する（ルーティングの輻輳の低減による）。シリコン面積への影響の大きさは、主にブロックサイズによるものであり、８０２．１１ｎについての２０〜５０％から大きなブロックサイズのシステムについての８０〜９５％まで変化し得る。これは、それ自体アーキテクチャのレイテンシー又はスループットを向上させるものではないが、非常に高いスループットのシステムについて大きな利益を得ることができる。
【０１５２】
前記アーキテクチャのレイテンシー及びスループットは、主として復号に必要な繰り返しの数によって決定され、本発明は、以下に示すように、現在の８０２．１１ｎ及び８０２．１６ｅ標準に対して１０〜２０％の向上が得られる。これは、２０％高いスループット及び２０％低いレイテンシーに直接変換され、又は所望の性能に必要なシリコン面積が更に減少する。
【０１５３】
シミュレーションのベンチマーク
図２４及び図２５は以下の通り、本発明を用いて高速で生成されかつＭＡＴＬＡＢに基づいたシミュレーションにより試験した２つのＬＤＰＣ符号のビット誤り率性能を示している。エンコーダーは、ＭＡＴＬＡＢ電気通信ツールボックスからの標準的ＬＤＰＣエンコーダーであり、かつデコーダーは、ＭＡＴＬＡＢ電気通信ツールボックスからの標準的繰り返しＬＤＰＣデコーダー（メッセージパッシングアルゴリズム）である。最後の１８９（８０２.１１ｎ）及び３３６（８０２．１６ｅ）列は、ＩＥＥＥ行列におけるものと同一の「階段状」構造を含む。残余の部分は、１５の（８０２．１１ｎ）初期パラメーター及び１７の（８０２．１６ｅ）初期パラメーターを入力に取り、行列を線順に、構造全体をメモリに記憶させることを必要とせずに再作成し得る代数的アリゴリズムを用いて生成した。図２６及び図２７は、最新の標準に対して、本発明により生成した符号を用いて８０２．１１ｎの場合及び８０２．１６ｅの場合双方について繰り返し回数対雑音レベルを示している。
【０１５４】
小ブロックのＬＤＰＣによる性能向上
大きなブロックのＬＤＰＣによるＥＣＣ性能はシャノン限界に近いものが得られるのに対し、小さいブロックサイズのＬＤＰＣは同様の性能を発揮しない。しかしながら、本発明は、小さいブロックサイズについて現在のＬＤＰＣの実装に対して実質的にＢＥＲ性能の向上が得られる（ベンチマークで１ｄＢまで観測）。
【０１５５】
達成される性能向上を用いて、以下の利益を実現することができる。
−送信電力を１ｄＢ減少させかつバッテリー寿命を長くしながらも同じリンク性能及びレンジを達成し、約２５％の改善が得られる。
−繰り返し回数を同じに維持し、かつより長いレンジ及びより頑強な短いレンジを達成する。
−繰り返し回数を減らして、既存の解と同じＢＥＲグラフを達成する。この新しいアーキテクチャは、全体により高いスループットが可能である。
−繰り返し回数を減らしかつ並列性を幾分除去（ゲートを少なく）するので、クロックサイクルにおける全復号時間が既存の解と同じである。この新しいアーキテクチャはシリコン面積及びコストが小さくなる。
【０１５６】
本発明によって、ＬＤＰＣ  ＥＣＣを利用した用途で、次のような設計上の実質的な利益が得られることが分かる。
−公知の８０２.１１ｎ及び８０２．１６ｅ標準と比較して優れたＬＤＰＣ  ＢＥＲ性能。
−事前定義した特性：符号サイズ、符号化率及び目標のビット誤り率（ＢＥＲ）性能に対して高速設計しかつ高性能ＬＤＰＣ行列を生成する能力。
−既存の巡回ＬＤＰＣ利用方法と比較して、メモリアドレッシングの必要性及びルーティングの複雑さを低減しつつ、シリアル、逐次ベクトル又は部分並列アーキテクチャにおいてハードウェア実装を可能にし、広範な用途について技術を適合させ得ること。
−動的かつ適応コーディングを、符号化率又は符号語長のいずれかのみ又は潜在的に完全に適応的なものを可能にする。
−階層的確率伝搬によるＬＤＰＣ行列構造利用可能な復号。低い繰り返し条件による低い符号化レイテンシー及び高いスループット。
【０１５７】
ＬＤＰＣ行列生成技術の設計上の利益によって、次のような重要な商業上の利益が得られる。
−適当な高性能ハードウェアＬＤＰＣの解を高速開発できることによる市場化への時間低減。
−公知のＬＤＰＣの解と比較してより効率的なメモリ記憶、ルーティングの複雑さ、処理及び電力バジェット。
−潜在的に完全な適応型符号化システムとして特定の用途の条件に対するＥＣＣの解の微調整。
−僅かなコストでかつ現在までのＬＤＰＣの域を越えた用途におけるＬＤＰＣの動作を可能にすること。
【０１５８】
本発明は、通信（受信機及び送信機の双方）及び記憶装置並びに設備に組み込むことができ、恐らくは符号化及び複号回路に組み込むことができる。このような機器又はシステムに本発明を組み込む可能性のある方法には、メモリ又はソフトウェアに基づいた実装に加えて、とりわけ、用途特定集積回路（ＡＳＩＣ）、フィールドプログラマブルゲードアレイ（ＦＧＰＡ）、デジタル信号プロセッサ（ＤＳＰ）のようなプロセッサ利用方法が含まれる。
【０１５９】
多くの用途について、本発明から次のような利益を得ることができる（但し、限定するものではない）。
（ａ）ブルートゥースのようなパーソナルエリアネットワーク、Ｗｉ−Ｆｉのようなローカルエリアネットワーク、Ｗｉ−Ｍａｘのようなメトロポリタンエリアネットワーク、路側ネットワーク、デジタル無線ネットワーク、衛星ネットワークを含むワイヤレスネットワーク。
（ｂ）ギガビットイーサネットのような高速度有線ネットワーク。
（ｃ）磁気記憶装置及び光記憶装置。
【０１６０】
本発明は、上述した実施例又は用途に限定されるものではなく、その構成及び詳細において様々に変化させることができる。例えば、別の実施例では、幾つかの先行する処理の数学的方法が転置を必要としない場合には、転置を実行しない。本発明は、符号化において階段状構造を使用する場合のようなより大きな行列のブロックを生成するのに適用することができる。本発明を実施する回路は、専用のハードウェア又はメモリを用いた方法を実施するようにプログラムされた汎用プロセッサとすることができる。また、本発明はホログラフィック記憶装置に適用することができる。
【図１】
2010532129.tif 000030
【図２】
2010532129.tif 000031
【図３】
2010532129.tif 000032
【図４】
2010532129.tif 000033
【図５】
2010532129.tif 000034
【図６】
2010532129.tif 000035
【図７】
2010532129.tif 000036
【図８】
2010532129.tif 000037
【図９】
2010532129.tif 000038
【図１０】
2010532129.tif 000039
【図１１】
2010532129.tif 000040
【図１２】
2010532129.tif 000041
【図１３】
2010532129.tif 000042
【図１４】
2010532129.tif 000043
【図１５】
2010532129.tif 000044
【図１６】
2010532129.tif 000045
【図１７】
2010532129.tif 000046
【図１８】
2010532129.tif 000047
【図１９】
2010532129.tif 000048
【図２０】
2010532129.tif 000049
【図２１】
2010532129.tif 000050
【図２２】
2010532129.tif 000051
【図２４】
2010532129.tif 000052
【図２５】
2010532129.tif 000053
【図２６】
2010532129.tif 000054
【図２７】
2010532129.tif 000055
【国際調査報告】
2010532129.tif 000056
2010532129.tif 000057
2010532129.tif 000058
2010532129.tif 000059
2010532129.tif 000060