(57)【要約】重みが２の列を制御性良く分布させる決定論的構造をパリティ検査行列Ｈに関して提案する。このパリティ検査行列Ｈは、ランダムに構成されるパリティ検査行列に比べて、検出されないフレーム誤りの発生を減らし、かつコード機能を著しく向上させるように作用する。Ｈは非決定論的セクションＨ１及び決定論的セクションＨ２を含み、Ｈ２は２よりも大きい奇数の重みを有する列ｈを含む第１部分と、行ｉ、列ｊに関して、ｉ＝ｊの場合に１、ｉ＝ｊ＋１の場合に１、ｉ，ｊが上記関係以外の場合に０、に等しい行列要素を含む第２部分と、を含む。
2007511139.tif 000002
【特許請求の範囲】
【請求項１】
パリティ検査ビット（ｐ０，．．．，ｐｍ−１）を現在のシンボル集合ｓ＝（ｓ０，．．．，ｓｋ−１）に基づいて生成する送信機を動作させる方法であって、
前記現在のシンボル集合ｓ＝（ｓ０，．．．，ｓｋ−１）を受信するステップと、
行列Ｈを使用して前記パリティ検査ビットを求めるステップであって、Ｈが非決定論的セクションＨ１及び決定論的セクションＨ２を含み、Ｈ２が２よりも大きい奇数の重みを有する列ｈを含む第１部分と、行ｉ、列ｊに関して、
ｉ＝ｊの場合に１、
ｉ＝ｊ＋１の場合に１、
ｉ，ｊが上記関係以外の場合に０、
に等しい行列要素を含む第２部分と、を含む、前記パリティ検査ビットを求めるステップと、
前記パリティ検査ビットを前記現在のシンボル集合と共に送信するステップと、
を備える方法。
【請求項２】
請求項１に記載の方法において、
【数１】
2007511139.tif 000020
が成立する、方法。
【請求項３】
請求項１に記載の方法において、前記行列Ｈを使用して前記パリティ検査ビット（ｐ０，ｐ１，．．．，ｐｍ−１）を求めるステップは、次式によりｐ０を求めるステップを含み、
【数２】
2007511139.tif 000021
上式において、
【数３】
2007511139.tif 000022
は、Ｈ１の全ての行を合計した後の行ベクトルを表わす、方法。
【請求項４】
請求項１に記載の方法において、前記行列Ｈを使用して前記パリティ検査ビット（ｐ０，ｐ１，．．．，ｐｍ−１）を求めるステップは、
次式によりｐ０を求めるステップであって、
【数４】
2007511139.tif 000023
上式において、
【数５】
2007511139.tif 000024
は、Ｈ１の全ての行を合計した後の行ベクトルを表わす、ｐ０を求めるステップと、
ｐ１，．．．，ｐｍ−１を再帰的に次式を用いて求めるステップであって、
【数６】
2007511139.tif 000025
上式において、ｖ＝［ｖ０，ｖ１，．．．，ｖｍ−１］Ｔ＝Ｈ１ｓＴである、ｐ１，．．．，ｐｍ−１を再帰的に求めるステップと、
を含む、方法。
【請求項５】
請求項１に記載の方法において、前記行列Ｈを使用して前記パリティ検査ビット（ｐ０，ｐ１，．．．，ｐｍ−１）を求めるステップは、
次式によりｐ０を求めるステップであって、
【数７】
2007511139.tif 000026
上式において、
【数８】
2007511139.tif 000027
は、Ｈ１の全ての行を合計した後の行ベクトルを表す、ｐ０を求めるステップと、
ｐ１，．．．，ｐｍ−１を再帰的に求めるステップと、
を含む、方法。
【請求項６】
請求項１に記載の方法であって、更に、
追加のパリティ検査ビットを送信する必要があると判断するステップと、
前記追加のパリティ検査ビット（ｐｍ，．．．，ｐｍ２−１）を、前記現在のシンボル集合ｓ＝（ｓ０，．．．，ｓｋ−１）及び（ｐ０，．．．，ｐｍ−１）に基づいて送信するステップと、
を備える方法。
【請求項７】
現在のシンボル集合ｓ＝（ｓ０，．．．，ｓｋ−１）を推定する受信機を動作させる方法であって、
受信信号ベクトルｙ＝（ｙ０，．．．，ｙｎ−１）を受信するステップと、
行列Ｈを使用して前記現在のシンボル集合（ｓ０，．．．，ｓｋ−１）を推定するステップであって、Ｈが非決定論的セクションＨ１及び決定論的セクションＨ２を含み、Ｈ２が２よりも大きい奇数の重みを有する列ｈを含む第１部分と、行ｉ、列ｊに関して、
ｉ＝ｊの場合に１、
ｉ＝ｊ＋１の場合に１、
ｉ，ｊが上記関係以外の場合に０、
に等しい行列要素を含む第２部分と、を含む、前記現在のシンボル集合（ｓ０，．．．，ｓｋ−１）を推定するステップと、
を備える方法。
【請求項８】
請求項７に記載の方法において、
【数９】
2007511139.tif 000028
が成立する、方法。
【請求項９】
請求項７に記載の方法であって、更に、
追加のパリティ検査ビットを受信すると判断するステップと、
前記受信した追加のパリティ検査ビットを使用して、前記現在のシンボル集合（ｓ０，．．．，ｓｋ−１）を推定するステップと、
を備える方法。
【請求項１０】
請求項７に記載の方法であって、更に、
行列Ｈ（２）を使用して前記現在のシンボル集合（ｓ０，．．．，ｓｋ−１）を求めるステップを備え、Ｈ（２）はＨに基づく、方法。
【請求項１１】
装置であって、
行列Ｈを記憶する記憶手段と、
行列Ｈを使用してパリティ検査ビットを求めるマイクロプロセッサであって、Ｈが非決定論的セクションＨ１及び決定論的セクションＨ２を含み、Ｈ２が２よりも大きい奇数の重みを有する列ｈを含む第１部分と、行ｉ、列ｊに関して、
ｉ＝ｊの場合に１、
ｉ＝ｊ＋１の場合に１、
ｉ，ｊが上記関係以外の場合に０、
に等しい行列要素を含む第２部分と、を含む、マイクロプロセッサと、
前記パリティ検査ビットを送信する送信機と、
を備える装置。
【請求項１２】
装置であって、
行列Ｈを記憶する記憶手段と、
信号ベクトルｙ＝（ｙ０，．．．，ｙｎ−１）を受信する受信機と、
行列Ｈを使用して現在のシンボル集合（ｓ０，．．．，ｓｋ−１）を求めるマイクロプロセッサであって、Ｈが非決定論的セクションＨ１及び決定論的セクションＨ２を含み、Ｈ２が２よりも大きい奇数の重みを有する列ｈを含む第１部分と、行ｉ、列ｊに関して、
ｉ＝ｊの場合に１、
ｉ＝ｊ＋１の場合に１、
ｉ，ｊが上記関係以外の場合に０、
に等しい行列要素を含む第２部分と、を含む、マイクロプロセッサと、
を備える装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータのエンコード及びデコードに関する。より詳細には、データを低密度パリティ検査（ＬＤＰＣ：low-density parity-check）コードを利用してエンコード及びデコードする方法及び装置に関する。
【背景技術】
【０００２】
ＬＤＰＣコードはパリティ検査行列Ｈにより指定される線形ブロック・コードである。一般的に、ＬＤＰＣコードはｑ≧２の場合にガロア体ＧＦ（ｑ）上で定義される。ｑ＝２の場合、コードは２進コードである。全ての線形ブロック・コードの場合のように、ｋビット情報ブロックｓ１×ｋは通常、符号生成行列Ｇｋ×ｎによりエンコードされてｎビットのコードワードｘ１×ｎになり、コード・レートはｒ＝ｋ／ｎとなる。コードワードｘは雑音の大きいチャネルを介して転送され、受信信号ベクトルｙはデコーダに渡されて情報ブロックｓ１×ｋが推定される。
【０００３】
ｎ次元空間を仮定すると、行列Ｇの行はｋ次元のコードワード部分空間Ｃを張り、パリティ検査行列Ｈｍ×ｎの行はｍ次元の双対空間Ｃ⊥を張り、この場合、ｍ＝ｎ−ｋである。ｘ＝ｓＧかつＧＨＴ＝０であるので、ｘＨＴ＝０が部分空間Ｃの全てのコードワードに対して成り立ち、この場合、“Ｔ”は行列の転置を表す。ＬＤＰＣコードに関する説明では、このことは一般的に次式のように表される。
【０００４】
【数１】
2007511139.tif 000003
上式において、０は全てがゼロの行ベクトルであり、コードワードｘ＝［ｓ  ｐ］＝［ｓ０，ｓ１，．．．，ｓｋ−１，ｐ０，ｐ１，．．．，ｐｍ−１］であり、この場合ｐ０，．．．ｐｍ−１はパリティ検査ビットであり、ｓ０，．．．，ｓｋ−１は組織（systematic）ビットであり、情報ブロック内の情報ビットに等しい。
【０００５】
良好な誤り訂正機能を備えるＬＤＰＣコードを使用するために、適切な低密度パリティ検査行列Ｈを定義する必要がある。最も不規則なＬＤＰＣコードの場合、Ｈの列のほとんどの部分の重みを２にして（すなわち、一列において２つの１及び全てのゼロ）、全体を低密度に維持する（すなわち、行列全体をスパース行列にする）必要がある。非常に多くの数の重みが２の列によって、Ｈの列の平均重みを低く維持しながら、高い重み（例えば３０）を幾つかの列に割り当てることができる（ここで、行の重みは普通、範囲が限定されており、かつ非常に小さいことに留意されたい）。
【０００６】
パリティ検査行列を種々の行重み及び列重みを用いて構成する操作は、誤り性能を考慮に入れると複雑になる。例えば、行列は、行重み及び列重みの制約を満たしつつ、一連のランダムに生成される列により構成可能であるが、重みが２の列が行列に多くの割合で含まれる場合には、ランダムに生成される重みが２の列は容易に欠損構造（bad structure ）を含むことができ、この構造によって検出できない誤りイベント及び小さな最小距離が生じる。一般的に、Ｎｕｄビットの検出できない誤りイベントは、パリティ検査行列のＮｕｄ個の列の合計（２を法とする）が、全てがゼロの列になる場合に生じ得る。全てがゼロの列が生じるような合計は、パリティ検査行列がサイズが小さく、かつ重みが２の列を含む場合に、より高い頻度で生じる。検出できない誤りイベントは、（Ｎｕｄ）の最小値に等しいコードの最小距離に直接関連付けられる。その結果、ランダムに生成されるパリティ検査行列は小さな最小距離を有することができ、最小距離が小さいことによって、検出できない誤り及び信号対雑音比が高い状態での誤りフロアが発生する確率が高くなる。更に、重みが２の列に関連するコード・ビット（ｘの要素群）は、重みが２よりも大きい列に関連するコード・ビットよりも遥かに誤りになり易いので、検出できないフレーム誤りの多くが、重みが２の列を含むと予測される。（ａ）長さが４のサイクルを回避する、かつ（ｂ）可能な場合は重みが２の列の間の重なりを回避するような方法が幾つかの先行技術によるコード設定ガイドラインとして文献に引用されている、あるいは暗示されているが、これらのガイドラインは良好な誤り性能コードには十分とはなり得ない。従って、検出できないフレーム誤りの発生が減少して、ランダムに設定されるパリティ検査行列に比べてコード品質が著しく改善されるような、重みが２の列の決定論的分布が必要となる。
【０００７】
上記の問題があるにも拘らず、ＬＤＰＣコードの別の問題は、コードを定義するＨ行列に対応する生成行列Ｇを使用する直接的な方法においてエンコード操作の複雑さが増すことである。組織的なＬＤＰＣエンコーダの場合、パリティ検査ビットｐｉ，ｉ＝０，．．．，ｍ−１は通常、所与の情報ビットｓ０，．．．，ｓｋ−１，ｍ＝ｎ−ｋから計算される。コードワードをｘ＝［ｓ  ｐ］＝［ｓ０，ｓ１，．．．，ｓｋ−１，ｐ０，ｐ１，．．．，ｐｍ−１］とすると、パリティ検査ビットは式（１）のパリティ検査方程式を満たす。従来のエンコード方法では、パリティ検査行列Ｈを、組織型行列Ｈｓｙｓ＝［Ｉｍ×ｍ，ＰＴ］に、ガウス消去及び列再配置を使用して変換し、該当する符号生成行列がＧ＝［Ｐｋ×ｍ，Ｉｋ×ｋ］になるようにする。従って、従来のエンコーダはパリティ検査ビットを、［ｐ０，．．．，ｐｍ−１］＝［ｓ０，．．．，ｓｋ−１］Ｐを使用して計算する。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
この直接的な方法によって実施局面における問題が、特にコードワード・サイズｎが大きい場合に生じる。第１に、Ｈは低密度（すなわち、行列に数個の１が含まれ、かつ行当たりの１の数がｎと共に大きくなることがない）であるが、Ｐ従ってＧは通常、高密度になる（すなわち、行列に多くの１が含まれ、かつ行当たりの１の数がｎと共に大きくなる）。従来のエンコーダを用いると、Ｐにおける１の位置を記憶するために大量のメモリが必要となる。第２に、Ｐが高密度であるため、２進数の加算の数（Ｐの要素が「１」の場合は単に項の数をカウントする）はｎ２のオーダーとなり、これはエンコード操作の複雑さがｎの２乗で増大することを意味する。従って、不規則ＬＤＰＣコードのエンコーダであって、高性能の不規則ＬＤＰＣコードの構造の利点を生かして前処理を最小化し、かつ単純なエンコード・プログラムを受け入れる高効率なエンコーダが必要になる。
【課題を解決するための手段】
【０００９】
上記の要求に対処するために、データをエンコードして、デコードする方法及び装置を本明細書において提供する。特に、検出されないフレーム誤りの発生を減少させ、かつコード機能を、ランダムに構成されるパリティ検査行列に比べて著しく向上させるパリティ検査行列Ｈを使用して生成されるパリティ検査ビットを提供する。Ｈは非決定論的セクションＨ１及び決定論的セクションＨ２を含み、Ｈ２は、２よりも大きい奇数の重みを有する列ｈを含む第１部分と、行ｉ、列ｊに関して、ｉ＝ｊの場合に１、ｉ＝ｊ＋１の場合に１、ｉ，ｊが上記関係以外の場合に０に等しくなる行列要素を含む第２部分と、を含む。
【００１０】
本発明は、パリティ検査ビット（ｐ０，．．．，ｐｍ−１）を現在のシンボル集合ｓ＝（ｓ０，．．．，ｓｋ−１）に基づいて生成する送信機を動作させる方法を含む。本方法は、現在のシンボル集合ｓ＝（ｓ０，．．．，ｓｋ−１）を受信するステップと、行列Ｈを使用してパリティ検査ビットを求めるステップと、を含む。Ｈは非決定論的セクションＨ１及び決定論的セクションＨ２を含み、Ｈ２は、２よりも大きい奇数の重みを有する列ｈを含む第１部分と、行ｉ、列ｊに関して、ｉ＝ｊの場合に１、ｉ＝ｊ＋１の場合に１、ｉ，ｊが上記関係以外の場合に０に等しくなる行列要素を含む第２部分と、を含む。
【００１１】
本発明は更に、現在のシンボル集合ｓ＝（ｓ０，．．．，ｓｋ−１）を推定する受信機を動作させる方法を含む。本方法は、受信信号ベクトルｙ＝（ｙ０，．．．，ｙｎ−１）を受信するステップと、行列Ｈを使用して現在のシンボル集合ｓ＝（ｓ０，．．．，ｓｋ−１）を推定するステップと、を含む。
【００１２】
本発明は更に、行列Ｈを記憶する記憶手段と、行列Ｈを使用してパリティ検査ビットを求めるマイクロプロセッサと、を備える装置を含む。
本発明は更に、行列Ｈを記憶する記憶手段と、信号ベクトルｙ＝（ｙ０，．．．，ｙｎ−１）を受信する受信機と、行列Ｈを使用して現在のシンボル集合ｓ＝（ｓ０，．．．，ｓｋ−１）を求めるマイクロプロセッサと、を備える装置を含む。
【発明を実施するための最良の形態】
【００１３】
次に、図面を参照すると（図面では、同様の参照番号が同様の構成部品を表す）、図１は、本発明の第１の実施形態によるエンコーダ１００のブロック図である。図示のように、エンコーダ１００はマイクロプロセッサ１０１と、ルックアップ・テーブル１０３と、を備える。本発明の第１の実施形態では、マイクロプロセッサ１０１は、ＭＳＣ８１００のＤＳＰ及びＤＳＰ５６３００のＤＳＰのようなデジタル信号プロセッサ（ＤＳＰ：digital signal processor）を含む（但し、これらに限定される訳ではない）。更に、ルックアップ・テーブル１０３は、行列を記憶する記憶手段として機能し、かつリードオンリー・メモリを備えるが、この技術分野の当業者であれば、他の形式のメモリ（例えば、ランダムアクセス・メモリ、磁気記憶メモリなど）も利用できることが分かるであろう。第２の実施形態では、マイクロプロセッサ１０１及びルックアップ・テーブル１０３の機能を、特定用途向け集積回路（ＡＳＩＣ：application specific integrated circuit ）またはフィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ：field programmable gate array ）に組み込むことができる。特に、ルックアップ・テーブル１０３は、信号経路が回路中に存在するか、あるいは存在しない構成に対応する所定の形式のメモリにおいて具体化可能である。
【００１４】
上述したように、エンコード・データは通常、組織ビットに加わる形の複数のパリティ検査ビットとして出力され、この場合、パリティ検査ビット及び組織ビットは一緒になって方程式ＨｘＴ＝０Ｔの解となる。本発明の第１の実施形態では、パリティ検査行列Ｈはルックアップ・テーブル１０３に記憶され、マイクロプロセッサ１０１がこの行列Ｈにアクセスして上式を解く。特に、マイクロプロセッサ１０１はパリティ検査ビット（ｐ０，．．．，ｐｍ−１）の適切な値を、現在のシンボル集合ｓ＝（ｓ０，．．．，ｓｋ−１）及びパリティ検査行列Ｈに基づいて求める。次に、パリティ検査ビット及びシンボル集合を送信機に渡して、受信機に送信する。Ｈは非決定論的セクションＨ１（すなわち、各項目の値が特定の構造を持つように定義されることもなければ、決定されることもないので、この値は、特定の構成制約が満たされる限りランダムとすることができる）と、決定論的セクションＨ２（すなわち、各項目の値が特定の構造を持つように定義されるか、あるいは決定される）と、を含む。
【００１５】
決定論的セクションＨ２は更に２つの部分から構成される。詳細には、第１部分は２よりも大きい奇数の重みを有する第１列ｈを含み、第２部分Ｈ２' は、０≦ｉ≦ｍ−１，０≦ｊ≦ｍ−２の場合のＨ２' の行ｉ、列ｊに関して、ｉ＝ｊの場合に１、ｉ＝ｊ＋１の場合に１、ｉ，ｊが上記関係以外の場合には０に等しくなる行列要素を含む。従って、全体としてのパリティ検査行列Ｈは次式により表わすことができ、
【００１６】
【数２】
2007511139.tif 000004
更に決定論的セクションＨ２は、
【００１７】
【数３】
2007511139.tif 000005
により表わすことができる。
【００１８】
本発明の好適な実施形態では、Ｈ１はサイズがｍ行ｋ列の任意のバイナリ行列とすることができる（別の表現をすれば、Ｈ１を規則的な構造とするか、あるいは不規則な構造とするか、あるいは任意の所望の重み分布を有するようにすることができる）。Ｈ２は下三角行列ではないが簡単な構造を有する。Ｈ２の第１列（ｈで示す）は、奇数個の１（３個以上の１）を有し、残りの列（ｍ行（ｍ−１）列の行列Ｈ２' により示される）は重みが２であり、最大１個の１が互いに重複する（Ｈ２' のプライムは、転置行列ではなく部分行列であることを示す）。
【００１９】
決定論的部分行列Ｈ２は必ず重みが２の列を（ｍ−１）個だけ有するが、行列Ｈ２がコード機能に影響を与えるとは考えられない。何故なら、重みが２の列の間には繰り返しがなく、かつ文献において報告されている最適な重み分布は通常、多くの重みが２の列を含むからである。Ｈ１の部分行列及びｈ列は、全体の行列Ｈが良好な誤り訂正機能を有するように構成されると考えられる。例えば、Ｈ１は通常、重みが２よりも大きい列により構成される。
【００２０】
先行技術とは異なり、Ｈ２行列は、重みが１の列が絶対に生じないように選択される。重みが１の列は機能を低下させる。何故なら、重みが１の列に対応するビットは、繰り返しデコードを行なっている間のソフト情報を更新しないように作用するからである。決定論的部分行列Ｈ２は組織ビットではなく、パリティ検査ビットに対応するように構成されるので、組織ビットはＨ１の相対的に大きい列の重みに起因して良好に保護される。
【００２１】
エンコード方法
上に例示したＨ２構造によって、エンコード操作の複雑さは、コード・サイズに対して２乗の割合で変化するのではなく線形的になる。エンコード操作は、生成行列を求めるか、あるいは計算することなく行なうことができる。
【００２２】
情報ビットｓのブロックが与えられれば必ず、ｍ個のパリティ検査ビットを、次式により定義される方程式を解くことにより求めることができる。
【００２３】
【数４】
2007511139.tif 000006
ｈの列重みが奇数であり、かつＨ２' が（ｍ−１）個の重みが２の列を含むので、式（４）における全ての方程式を合計すると次式が得られる。
【００２４】
【数５】
2007511139.tif 000007
上式において、ΣｒｏｗＨ１はＨ１の全ての行を合計した後の行ベクトルを表わす。ここで、合計操作は等価的に、中間列ベクトルｖ＝［ｖ０，ｖ１，．．．，ｖｍ−１］Ｔ＝Ｈ１ｓＴに対して実行することができるが、Ｈ１の行に対する合計操作は事前に行なうことができ、かつ合計操作によってｐ０を計算するための操作が少なくて済む。
【００２５】
ｐ０を求めると、残りのパリティ検査ビットｐ１からｐｍ−１を再帰的に求めることができる。例えば、
【００２６】
【数６】
2007511139.tif 000008
上式において、［ｈ０，ｈ１，．．．，ｈｍ−２，ｈｍ−１］Ｔは、式（３）の列ｈである。式（６）では全ての変数が２進数であるので、エンコード操作の複雑さは非常に低い。更に、実施形態を簡単にするために、ベクトルｗ＝［ｗ０，ｗ１，．．．，ｗｍ−２，ｗｍ−１］＝［ｈ０ｐ０＋ｖ０，ｈ１ｐ０＋ｖ１，．．．，ｈｍ−２ｐ０＋ｖｍ−２，ｈｍ−１ｐ０＋ｖｍ−１］を記憶してパリティ検査ビットをｐ１＝ｗ０，ｐｉ＝ｐｉ−１＋ｗｉ−１，ｉ＝２，３，．．．ｍ−１により求めることができるようにする。
【００２７】
パリティ検査方程式を、ｐｍ−１からｐ１の順番で再帰的に解くこともできる。この場合、パリティ検査ビットは、ｐｍ−１＝ｗｍ−１，ｐｉ＝ｐｉ＋１＋ｗｉ，ｉ＝ｍ−２，．．．，２，１により求められる。
【００２８】
ｈの更に別の構造を使用してエンコード操作の複雑さを更に低減することができる。例えば、式（３）において、ｈのほとんどの項目はゼロが後に続く構成（trailing zeros）とすることができる（例えば、ｈ＝［１００１００１０．．．０］Ｔ）。ｚ≦ｉ≦ｍ−１の場合のｈｉの全ての値が０であることが判明すると、パリティ検査ビットを式（６）におけるように再帰的に求めるステップを簡単にして、再帰的エンコード構造を変えることができる。一つの例では、ｚ≦ｉ≦ｍ−１においてｗｉ＝ｖｉ，従ってｚ≦ｉ≦ｍ−１におけるｐｉは、ｐ０を求める前に求めることができる。この場合、ｐ０からｐｚ−１はｓ及びｐｚに基づいて求めることができる。
【００２９】
デコード方法
図２は本発明の一つの実施形態によるデコーダ２００のブロック図である。図示のように、デコーダ２００はマイクロプロセッサ２０１と、ルックアップ・テーブル２０３と、を備える。本発明の第１の実施形態では、マイクロプロセッサ２０１は、ＭＳＣ８１００のＤＳＰ及びＤＳＰ５６３００のＤＳＰのようなデジタル信号プロセッサ（ＤＳＰ）を含む（但し、これらに限定される訳ではない）。更に、ルックアップ・テーブル２０３は、行列Ｈを記憶する記憶手段として機能し、かつリードオンリー・メモリを備える。しかしながら、この技術分野の当業者であれば、他の形式のメモリ（例えば、ランダムアクセス・メモリ、磁気記憶メモリなど）も利用できることが分かるであろう。第２の実施形態では、マイクロプロセッサ２０１及びルックアップ・テーブル２０３の機能を、特定用途向け集積回路（ＡＳＩＣ）またはフィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）に組み込むことができる。特に、ルックアップ・テーブル２０３は、信号経路が回路中に存在するか、あるいは存在しない構成に対応する形式のメモリにおいて具体化可能である。
【００３０】
受信信号ベクトル（受信機を通して受信する）ｙ＝（ｙ０，．．．，ｙｎ−１）は、雑音の大きいチャネルを介して伝送されるコードワードｘに対応し、この場合、エンコード・データｘは上述したように、方程式ＨｘＴ＝０Ｔの解である。本発明の第１の実施形態では、パリティ検査行列Ｈはルックアップ・テーブル２０３に記憶され、マイクロプロセッサ２０１がこの行列Ｈにアクセスしてｙをデコードし、情報ブロックｓ（すなわち、現在のシンボル集合ｓ＝（ｓ０，．．．，ｓｋ−１））を推定する。特に、マイクロプロセッサ２０１は現在のシンボル集合ｓ＝（ｓ０，．．．，ｓｋ−１）を、受信信号ベクトルｙ＝（ｙ０，．．．，ｙｎ−１）及びパリティ検査行列Ｈに基づいて推定する。上述したように、Ｈは非決定論的セクションＨ１（すなわち、各項目の値が特定の構造を持つように定義されることもなければ、決定されることもないので、この値は、特定の構成制約が満たされる限りランダムとすることができる）と、決定論的セクションＨ２（すなわち、各項目の値が特定の構造を持つように定義されるか、あるいは決定される）と、を含む。
【００３１】
この技術分野では公知のように、デコーダ２００はパリティ検査行列Ｈをマイクロプロセッサ２０１において使用してデコードを実行することができる。一つのこのような方法では、ベクトル行列乗算をＨを使用して行なって、生じ得る誤りパターンを求める。別のこのような方法では、Ｈを使用して、グラフのエッジがＨの１に対応する２部グラフ（bipartite graph ）を構築し、更に２部グラフのｙを繰り返し処理する。
【００３２】
コード変更
多くの場合、新規コード（新規の、あるいは異なるパリティ検査行列）は、既存コード（既存のパリティ検査行列）を変更することにより生成することが望ましい。新規コードは通常、既存コードとは異なる数の情報ビットまたはパリティ検査ビットを有する。変更が適切であれば、新規コードは元のコードと同様の手順を通してエンコード及びデコードすることができる。パリティ検査ビットを付加するか、あるいは取り除く変更は、ＬＤＰＣコードに関しては特に難しい。何故なら、結果として得られるコードは、元のコードが良好な特性を有していた場合でも、エンコードまたはデコードに関して良好な特性を有することができないからである。次のサブセクションでは、コードの良好な特性を維持しながらコードを変更する２つの方法について説明する。
【００３３】
簡易変更
上述したＨ２構造の場合、Ｈ行列は、Ｈ２構造を変えることなく、任意の数のパリティ検査ビットだけ拡張または縮小することができる。各拡張コードまたは縮小コードは、上に例示した同じエンコード手順を使用し、かつ当該コードのＨ１部分行列が注意深く構築される場合に良好な機能を維持する。
【００３４】
例えば、ｇ個のパリティ検査ビットを削除して高いレート（ｎ−ｇ，ｋ）のコードを得ようとする場合は、Ｈ行列は、ｇ個の最も右側の列及びｇ個の最も下側の行を削除することにより変更される。別の構成として、Ｈ行列はｇ個のパリティ検査ビットだけ拡張して低いレート（ｎ＋ｇ，ｋ）のコードを得ることができ、この操作は、ｇ個の列を右側に付加し、かつｇ個の行を下側に付加してＨ２において対角線上に２つの１が配置される構成の２の重みを有する列構造を維持することにより行なわれる。
【００３５】
削除を行なう際に不所望の第１列（例えば、重みが３未満の、あるいは重みが偶数の列）がＨ２に含まれるのを避けるために、ｈの１が上側に分布する構造が好ましい。例えば、ｈ＝［１００１００１０．．．０］Ｔの構成の式（３）では、ｈの３つの項目のみが１であり、かつｈの上側に位置する。
【００３６】
簡易変更によって元のコードのエンコード操作の容易さを維持することができ、かつ行列を記憶する記憶容量を減らし易くなるが、簡易変更により生成される複数のコードは、高いレートのコードのパリティ検査ビットが低いレートのコードのパリティ検査ビットの部分集合であるという意味において関係する訳ではない。同じ情報シンボル集合が与えられた場合において、高いレートのコードのパリティ検査ビットが低いレートのコードのパリティ検査ビットの部分集合である関係は、レート互換（rate compatibility）と呼ばれる。
【００３７】
レート互換コード変更
上に定義したＨ行列を変更してレート互換ＬＤＰＣコードをＨ２と同様な連結部分により生成することができる。例えば、添え字がコード１、コード２、及びコード３をそれぞれ示す構成の３個のコードについて考察する。コード１のパリティ検査ビットは、コード２のパリティ検査ビットの部分集合であり（すなわち、コード１のパリティ検査ビットをコード２のパリティ検査ビットの内部で入れ子にする）、かつコード２のパリティ検査ビットは、コード３のパリティ検査ビットの部分集合である（すなわち、コード２のパリティ検査ビットをコード３のパリティ検査ビットの内部で入れ子にし、そして今度は、コード１のパリティ検査ビットをコード３のパリティ検査ビットの内部で入れ子にする）。コード１は、次式により定義されるパリティ検査行列Ｈ（１）を有する。
【００３８】
【数７】
2007511139.tif 000009
上式において、Ｈ１（１）はｍ１行ｋ列の行列であり、Ｈ２（１）はｍ１行ｍ１列の行列であり、この行列の構造は式（３）に従い、かつこの構造によってパリティ検査ビットｐ０，ｐ１，．．．，ｐｍ１−１が生成される。ここで、式（７）は式（２）と等価であり、かつ添え字「（１）」は単に、第１コード（すなわち、Ｈ（１）＝Ｈ，ｍ１＝ｍ）を強調するために使用していることに留意されたい。
【００３９】
コード２は、次式により定義されるパリティ検査行列Ｈ（２）を有する。
【００４０】
【数８】
2007511139.tif 000010
上式において、Ｈ１（２）は（ｍ２−ｍ１）行（ｋ＋ｍ１）列の行列であり、Ｈ２（２）は（ｍ２−ｍ１）行（ｍ２−ｍ１）列の行列であり、この行列の構造は式（３）に示される構造に従い、かつコード２によってパリティ検査ビットｐ０，ｐ１，．．．，ｐｍ２−１が生成される。（ｍ２−ｍ１）行（ｍ２−ｍ１）列の行列の構造が式（３）に示される構造に従うので、決定論的セクションＨ２（２）は２よりも大きい奇数の重みを有する第１列ｈ（２）と、０≦ｉ≦ｍ−１，０≦ｊ≦ｍ−２の場合の行ｉ、列ｊに関して、ｉ＝ｊの場合に１、ｉ＝ｊ＋１の場合に１、ｉ，ｊが上記関係以外の場合には０に等しくなる第２部分と、を含む。第１列ｈ（２）はｈ（１）と同じサイズまたは同じ成分を有する必要はなく、ｈ（１）はコード１の列ｈである。入れ子構造に起因して、パリティ検査ビットｐｍ１，．．．，ｐｍ２−１は、Ｈ１（２），Ｈ２（２）、組織ビットｓ、及び前に計算されたパリティ検査ビットｐ０，ｐ１，．．．，ｐｍ１−１から、式（５）及び（６）に表わされるエンコード方法を使用して得ることができる。
【００４１】
コード３は、次式により定義されるパリティ検査行列Ｈ（３）を有する。
【００４２】
【数９】
2007511139.tif 000011
上式において、Ｈ１（３）は（ｍ３−ｍ２）行（ｋ＋ｍ２）列の行列であり、Ｈ２（３）は（ｍ３−ｍ２）行（ｍ３−ｍ２）列の行列であり、この行列の構造は式（３）に従い、コード３によってパリティ検査ビットｐ０，ｐ１，．．．，ｐｍ３−１が生成される。入れ子構造に起因して、パリティ検査ビットｐｍ２，．．．，ｐｍ３−１は、Ｈ１（３），Ｈ２（３）、組織ビットｓ、及び前に計算されたパリティ検査ビットｐ０，ｐ１，．．．，ｐｍ２−１から、式（５）及び（６）に表わされるエンコード方法を使用して得ることができる。ここで、Ｈと同様、Ｈ（２）及びＨ（３）は共に、式（３）に示すように、２よりも大きい奇数の重みを有する第１列と、０≦ｉ≦ｍ−１，０≦ｊ≦ｍ−２の場合の行ｉ、列ｊに関して、ｉ＝ｊの場合に１、ｉ＝ｊ＋１の場合に１、ｉ，ｊが上記関係以外の場合には０に等しくなる構成の残りの全ての行と、を有する決定論的セクションを含む。
【００４３】
式（９）において定義される「マザーコード」によって、３つの異なるレートｋ／（ｋ＋ｍ１），ｋ／（ｋ＋ｍ２），及びｋ／（ｋ＋ｍ３）のコードを効果的に定義することができる。次に３セット（［ｓ，ｐ０，ｐ１，．．．，ｐｍ１−１］，［ｓ，ｐ０，ｐ１，．．．，ｐｍ２−１］，及び［ｓ，ｐ０，ｐ１，．．．，ｐｍ３−１］）を異なる送信／受信コード・レートに関して使用し、更にこれらのセットはレート互換であるので、増加的冗長性（ＩＲ：incremental redundancy）に使用することができる。ＩＲでは、第１送信において［ｓ，ｐ０，ｐ１，．．．，ｐｍ１−１］を送信し、第２送信において，［ｐｍ１，．．．，ｐｍ２−１］を送信し、第３送信において［ｐｍ２，．．．，ｐｍ３−１］を送信することができる。第１送信よりも後の送信は、早い方の送信が失敗した場合（受信されなかったか、あるいは正しくデコードされなかった場合）、またはプロトコルによって複数の送信が指定される場合に行なわれ得る。上述の説明では、コード２，コード３，．．．，などの追加のパリティ・ビットの送信を仮定したが、この技術分野の当業者であれば、他のモードの送信を使用することができることが理解できるであろう。例えば、第１送信が失敗すると、第２送信によりコード２及びコード３両方の追加のパリティ・ビット［ｐｍ１，．．．，ｐｍ３−１］を送信することができる。
【００４４】
次の記述では、どのようにしてコード２の新規のパリティ検査ビットをコード１の情報ビット及びパリティ検査ビットから生成することができるのかについて示すための例を示す。この特性を例示するために、ｋ＝９，ｍ１＝９，ｍ２＝１３として、次式により表されるｍ１行（ｋ＋ｍ１）列の行列、
【００４５】
【数１０】
2007511139.tif 000012
および次式により表されるｍ２行（ｋ＋ｍ２）列の行列を定義する。
【００４６】
【数１１】
2007511139.tif 000013
パリティ検査ビットｐ０からｐｍ１−１（＝ｐ８）が既に計算されていると仮定する。ｐｍ１，．．．，ｐｍ２−１の計算では、式（５）及び（６）に表わされるエンコード方法を次のようにして使用することができる。
次式を計算する。
【００４７】
【数１２】
2007511139.tif 000014
次に、次式を計算する。
【００４８】
【数１３】
2007511139.tif 000015
【００４９】
【数１４】
2007511139.tif 000016
【００５０】
【数１５】
2007511139.tif 000017
【００５１】
【数１６】
2007511139.tif 000018
上式において、関数ｒｏｗｉ（Ｈ）は行列Ｈのｉ番目の行を選択する。ｐｍ１を求めるための好適な方法が上に提示されているが、他の同様な方法を使用することができる。例えば、ｐｍ１は次式により求めることもできる。
【００５２】
【数１７】
2007511139.tif 000019
上に示すように、一旦、第１コードの行列Ｈの第１パリティ検査ビットが送信され、かつ第１送信が失敗したと判断されると、追加のパリティ検査ビット（ｐｍ，．．．，ｐｍ２−１）を、現在のシンボル集合ｓ＝（ｓ０，．．．，ｓｋ−１）及び第１パリティ検査ビット（ｐ０，ｐ１，．．．ｐｍ−１）に基づいて計算して送信することができる。行列Ｈ（２）を使用して追加のパリティ検査ビットを求めるが、この場合、Ｈ（２）は式（８）に示すＨに基づく。このプロセスは無限に続く。従って、動作期間中、マイクロプロセッサ１０１はＨの構造を利用してｍ個のパリティ検査ビットを式（５）及び（６）に基づいて計算する。追加のパリティ検査ビットが必要となると、これらのパリティ検査ビットは、式（８）及び（９）を参照しながら上に定義される行列を使用して計算される。ここで再び、Ｈ（１）＝Ｈかつｍ１＝ｍであることを思い出されたい。
【００５３】
図３はエンコーダ１００、特にマイクロプロセッサ１０１の動作を示すフロー・チャートである。論理フローはステップ３０１から始まり、このステップでは、現在のシンボル集合ｓ＝（ｓ０，．．．，ｓｋ−１）を受信する。ステップ３０３では、第１パリティ検査ビットの値をＨに基づいて求める。詳細には、第１パリティ検査ビット（ｐ０，．．．ｐｍ−１）を式（５）及び（６）について上述したようにして求める。ステップ３０５では、現在のシンボル集合及び第１パリティ検査ビットを送信する。ステップ３０７では、追加のパリティ検査ビットのいずれかを送信する必要があるのかについての判断を行なう。この判断は、例えば第１送信が失敗した場合（受信されなかったか、あるいは正しくデコードされなかった場合）、または送信プロトコルによって必ず第２送信が指定される場合に行なわれ得る。ステップ３０７において、追加のパリティ検査ビットを送信する必要があると判断されると、論理フローはステップ３０９に進み、このステップにおいて、追加のパリティ検査ビットを適切なＨ（２），Ｈ（３），．．．，などに基づいて求める。Ｈ（２），Ｈ（３），．．．，などのパリティ検査ビットを送信するという選択は、例えば送信プロトコル、品質指標などに基づいて行なうことができる。ステップ３１１では、追加のパリティ検査ビットを送信し、論理フローはステップ３０７に戻る。ステップ３０７において、追加のパリティ検査ビットを送信する必要がないと判断されると、論理フローはステップ３１３で終了する。
【００５４】
図４はデコーダ２００、特にマイクロプロセッサ２０１の動作を示すフロー・チャートである。論理フローはステップ４０１から始まり、このステップでは、受信信号ベクトルｙ＝（ｙ０，．．．，ｙｎ−１）を受信する。ステップ４０３では、情報ブロックｓ（すなわち、現在のシンボル集合（ｓ０，．．．，ｓｋ−１））の推定値をＨに基づいて求める。この技術分野では公知のように、デコーダ２００が、パリティ検査行列Ｈをマイクロプロセッサ２０１において使用してデコードを実行するためには多くの方法がある。一つのこのような方法では、ベクトル行列乗算をＨを使用して行なって、生じ得る誤りパターンを求める。別のこのような方法では、Ｈを使用して、グラフのエッジがＨの１に対応するグラフを構築し、更にｙをグラフ上で繰り返し処理する。ステップ４０７では、追加のパリティ検査ビットを受信するか否かについての判断を行ない、この場合の追加のパリティ検査ビットは、雑音の大きいチャネルを介して伝送される追加のパリティ検査ビットの追加受信信号ベクトルの形式で受信される。この判断は、例えば第１送信が失敗した場合（受信されなかったか、あるいは正しくデコードされなかった場合）、または送信プロトコルによって必ず追加の送信が指定される場合に行なわれ得る。ステップ４０７において、追加のパリティ検査ビットを受信すると判断されると、論理フローはステップ４０９に進み、このステップにおいて、情報ブロックｓ（すなわち、現在のシンボル集合（ｓ０，．．．，ｓｋ−１））の推定値を適切なＨ（２），Ｈ（３），．．．，などと、受信した追加のパリティ検査ビットとに基づいて求める。次に論理フローはステップ４０７に戻る。ステップ４０７において、追加のパリティ検査ビットを受信しないと判断されると、論理フローはステップ４１３で終了する。
【００５５】
本発明について特定の実施形態を参照しながら特定の形で示し、説明してきたが、この技術分野の当業者であれば、形式及び詳細に関する種々の変更を本明細書において、本発明の技術思想及び技術範囲から逸脱しない範囲で加え得ることが理解できるであろう。例えば、本発明について、ｓｉ及びｐｉの順番がｘの内部で定義されるものとして示したが、この技術分野の当業者であれば、コードワード・ビットをどのような順番でも、Ｈの列がその順番に従って順序入れ替えされる限り、収集することができるので、ｘの内部においてビットの他の順番が生じ得ることが分かるであろう。更に、上記説明は、バイナリー・コード（すなわち、ガロア体ＧＦ（２）上で定義されるコード）を参照しながら特定の形で示され、かつ為されてきたが、この技術分野の当業者であれば、任意のガロア体ＧＦを利用することもできることが分かるであろう。上に提示した例は一つの形式で示しているが、同様なエンコード操作及びコード変更手順が可能になる他の形式を使用することができる。例えば、列ｈは単純に第１列とするのではなく、Ｈ２の任意の列に配置することができる。別の例では、ｘのビットの順番を入れ替えてＨの列の順序入れ替えが必要となるようにすることができる。更に別の例では、Ｈの行の順序入れ替えを、パリティ検査ビットの値に影響を及ぼすことなく行なうことができる。行列Ｈはまた、パリティ検査行列を利用する任意のタイプのデコーダにも使用することができる。このような変更は次の請求項における技術範囲に含まれるものである。
【００５６】
尚、国際出願の英文明細書中にＪＩＳコードで表記できない箇所があったため、本翻訳文では代替表記を使用した。具体的には、ベクトル、行列を表す記号が、国際出願の英文明細書ではボールド体（太字）で表現されていたが、本翻訳文の本文中では通常の字体で表現されている。また、［数１］〜［数１７］の数式中では、英文明細書と同様のボールド体で表現されていることに留意されたい。
【図面の簡単な説明】
【００５７】
【図１】本発明の好適な実施形態によるエンコーダのブロック図。
【図２】本発明の好適な実施形態によるデコーダのブロック図。
【図３】本発明の好適な実施形態による、図１のエンコーダの動作を示すフロー・チャート。
【図４】本発明の好適な実施形態による、図２のデコーダの動作を示すフロー・チャート。
【図１】
2007511139.tif 000029
【図２】
2007511139.tif 000030
【図３】
2007511139.tif 000031
【図４】
2007511139.tif 000032
【国際調査報告】
2007511139.tif 000033
2007511139.tif 000034
2007511139.tif 000035