(57)【要約】構造化パリティチェック行列Ｈを提案する。Ｈは基底行列Ｈｂの展開であり、Ｈｂ２は２より大きい奇数の重みを有する列ｈｂからなる第一の部分と、行ｉと列ｊが、ｉ＝ｊについては１に等しく、ｉ＝ｊ＋１については１に等しく、他の位置については０に等しい行列要素を備える第二の部分とを備える。基底行列Ｈｂの展開は、前記第二の部分Ｈ’ｂ２の各列における１については同一部分行列を用い、この展開はｈｂにおける偶数個の１については対になった部分行列を用いる。
2008509635.tif 000002
【特許請求の範囲】
【請求項１】
現在の記号セットｓ＝（ｓ０，…，ｓｋ−１）に基づいてパリティチェックビットｐ＝（ｐ０，…，ｐｍ−１）を生成する送信機を動作させる方法であって、
前記現在の記号セットｓ＝（ｓ０，…，ｓｋ−１）を受信する工程と、
行列Ｈを用いて前記パリティチェックビットを決定する工程と、
前記現在の記号セットと共に前記パリティチェックビットを送信する工程とを備え、
Ｈは基底行列Ｈｂの展開であり、ＨｂはセクションＨｂ１およびセクションＨｂ２を備え、Ｈｂ２は２より大きい奇数の重みを有する列ｈｂを有する第一の部分と、行ｉと列ｊが、ｉ＝ｊについては１に等しく、ｉ＝ｊ＋１については１に等しく、他の位置については０に等しい行列要素を備える第二の部分Ｈ’ｂ２とを備え、前記基底行列Ｈｂの展開は、前記第二の部分Ｈ’ｂ２の各列における１については同一部分行列を用い、ｈｂの偶数個の１については対になった部分行列を用いる前記方法。
【請求項２】
Ｈｂは、Ｈｂの各エントリをサイズｚ×ｚの部分行列で置換することによって展開されてＨを生成することを特徴とする請求項１に記載の方法。
【請求項３】
Ｈｂは、Ｈｂの各ゼロ要素をサイズｚ×ｚのゼロ部分行列で置換することによって展開されてＨを生成することを特徴とする請求項１に記載の方法。
【請求項４】
Ｈｂは、Ｈｂの各非ゼロ要素を非ゼロ部分行列で置換することによって展開されてＨを生成することを特徴とする請求項１に記載の方法。
【請求項５】
ＨｂはＨｂの各非ゼロ要素を非ゼロ順列部分行列で置換することによって展開されてＨを生成することを特徴とする請求項１に記載の方法。
【請求項６】
【数１】
2008509635.tif 000026
が成り立ち、ベクトルｈｂが奇数の重みｗｈ＞＝３を有することを特徴とする請求項１に記載の方法。
【請求項７】
行列Ｈを記憶する記憶手段と、
行列Ｈを用いてパリティチェックビットを決定するマイクロプロセッサと、
前記パリティチェックビットを送信する送信機とを備え、
Ｈは基底行列Ｈｂの展開であり、ＨｂはセクションＨｂ１およびセクションＨｂ２を備え、Ｈｂ２は２より大きい奇数の重みを有する列ｈｂを有する第一の部分と、行ｉと列ｊが、ｉ＝ｊについては１に等しく、ｉ＝ｊ＋１については１に等しく、他の位置については０に等しい行列要素を備える第二の部分Ｈ’ｂ２とを備え、
二つの同一部分行列がＨ’ｂ２のすべての列における１を展開させるのに用いられ、対になった部分行列がｈｂにおける偶数個の１を展開するのに用いられることを特徴とする装置。
【請求項８】
【数２】
2008509635.tif 000027
が成り立ち、ベクトルｈｂが奇数の重みｗｈ＞＝３を有することを特徴とする請求項７に記載の装置。
【請求項９】
行列Ｈを記憶する記憶手段と、
信号ベクトルｙ＝（ｙ０…Ｙｎ−１）を受信する受信機と、
行列Ｈを用いて現在の記号セット（ｓ０，…，ｓｋ−１）を決定するマイクロプロセッサとを備え、
Ｈは基底行列Ｈｂの展開であり、ＨｂはセクションＨｂ１およびセクションＨｂ２を備え、Ｈｂ２は２より大きい奇数の重みを有する列ｈｂを有する第一の部分と、行ｉと列ｊが、ｉ＝ｊについては１に等しく、ｉ＝ｊ＋１については１に等しく、他の位置については０に等しい行列要素を備える第二の部分Ｈ’ｂ２とを備え、
二つの同一部分行列がＨ’ｂ２のすべての列における１を展開させるのに用いられ、対になった部分行列がｈｂにおける偶数個の１を展開するのに用いられることを特徴とする装置。
【請求項１０】
【数３】
2008509635.tif 000028
が成り立ち、ベクトルｈｂが奇数の重みｗｈ＞＝３を有することを特徴とする請求項９に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般的にデータのエンコードおよびデコードに関し、特に、低密度パリティチェック（ＬＤＰＣ）コードを用いるデータのエンコードおよびデコード方法および装置に関する。
【背景技術】
【０００２】
参照によってここに組み入れられた米国特許出願番号１０／８３９９９５に記載されているように、低密度パリティチェック（ＬＤＰＣ）符号は、パリティチェック行列Ｈによって指定される線形ブロック符号である。一般的には、ＬＤＰＣ符号はガロア域ＧＦ（ｑ），ｑ≧２上に定義される。ｑ＝２であれば、その符号は２進符号である。すべての線形ブロック符号は、ｎビットの符号語Ｘ１×ｎを生成する、ｋビットの情報ベクトルｓ１×ｋと符号発生器行列Ｇｋ×ｎとの積として表現することができ、符号レートはｒ＝ｋ／ｎである。符号語ｘはノイズ通信路を通して送信され、受信信号ベクトルｙは情報ベクトルＳ１×ｋを推定すべくデコーダに渡される。
【０００３】
ｎ次元空間と、Ｇの行がｋ次元の符号語の部分空間Ｃに渡り、パリティチェック行列Ｈｍ×ｎの行がｍ次元の相対空間Ｃ⊥に渡り、ｍ＝ｎ−ｋであると仮定する。ｘ＝ｓＧおよびＧＨＴ＝０であるため、部分空間Ｃにおいてすべての符号語についてｘＨＴ＝０という結果になる。「Ｔ」（あるいは斜体「Ｔ」）は行列転置を表している。ＬＤＰＣ符号を議論するとき、これは一般的に以下の式（１）ように書かれる。
【０００４】
【数４】
2008509635.tif 000003
ここで０は全ゼロの行ベクトルであり、符号語ｘ＝［ｓ  ｐ］＝［ｓ０，ｓ１，…，ｓｋ−１，Ｐ０，ｐ１，…ｐｍ−１］、ｐ０，…，ｐｍ−１はパリティチェックビットであり、ｓ０，…，ｓｋ−１は、情報ベクトル内の情報ビットと等しいシステムビットである。
【０００５】
ＬＤＰＣ符号については、Ｈにおける非ゼロエントリの密度は低い、すなわち、Ｈが１の比率は低いため、濃密なＨを用いるよりも、より良いエラー訂正性能および簡易なデコードが可能になる。パリティチェック行列も二部グラフによって表記することができる。この二部グラフは符号のグラフ表記ばかりでなく、デコーダのモデルでもある。この二部グラフでは、符号語ビット（従ってＨの各列）は左側の変数ノードによって表現され、各パリティチェック方程式（従ってＨの各行）は右側のチェックノードによって表現される。各変数ノードはＨの各列に対応し、各チェックノードはＨの行に対応し、Ｈの「変数ノード」および「列」はＨの「チェックノード」および「列」として交換可能に参照される。変数ノードはチェックノードにのみ接続され、チェックノードは変数ノードにのみ接続される。ｎ符号語ビットおよびｍパリティビットを有する符号については、符号語ビットｉがチェック方程式ｊに参加していれば（ｉ＝０，１…，ｎ−１，ｊ＝０，１，…，ｍ−１）、変数ノードｖｉはエッジによってチェック符号ｃｊに接続される。換言すれば、パリティチェック行列Ｈのエントリｈｊｉが１であれば、変数ノードｉはチェックノードｊに接続される。式（１）をミラーリングして、すべてのチェックノードが偶数パリティを有している場合、変数ノードは正当な符号語を表現している。
【０００６】
パリティチェック行列とパリティチェック方程式と二部グラフとの関係を示す例を以下に示す。ｎ＝１２、レート−１／２の符号は下記のように定義され、
【０００７】
【数５】
2008509635.tif 000004
ここで左側部分はｋ（＝６）情報ビットｓに対応し、右側部分はｍ（＝６）パリティビットｐに対応する。式（１）を適用すると、式（２）のＨは以下のように、６パリティチェック方程式を定義する。
【０００８】
【数６】
2008509635.tif 000005
Ｈは図１に示した対応二部グラフも有する。
【０００９】
上述したように、受信機は送信された符号語ｘの汚染バージョンｙを取得する。ｙをデコードし元の情報シーケンスｓを決定するために、確率伝播のような反復復号化アルゴリズムが二部グラフに基づいて適用される。符号語ビットの対数尤度比（ＬＬＲｓ）のフォーマットのソフト情報は、変数ノードのバンクとチェックノードのバンクとの間で渡される。反復は、すべてのチェック方程式が満たされたとき、あるいは最大許可反復限度に到達したときのいずれかの場合に停止する。
【００１０】
構造化ＬＤＰＣ符号設計は小さいｍｂ×ｎｂの基底行列（ｂａｓｅ  ｍａｔｒｉｘ）Ｈｂを用いて開始され、Ｈｂのｚ個のコピーを作成し、そのｚ個のコピーを相互接続して大きなｍ×ｎのＨ行列を形成する（ｍ＝ｍｂ×ｚ、ｎ＝ｎｂ×ｚ）。ＨｂからＨを構築するためにこの行列表現を用いることにより、Ｈｂにおける各１がｚ×ｚの順列部分行列によって置換され、Ｈｂにおける各０がｚ×ｚの全ゼロの部分行列で置換される。この手順は本質的に、Ｈｂの各エッジをＨにおける長さｚのベクトルエッジにマッピングし、Ｈｂの各変数ノードをＨにおける長さｚのベクトル変数ノードにマッピングし、Ｈｂの各チェックノードをＨにおける長さｚのベクトルチェックノードにマッピングする。小さな行列Ｈｂをベクトル化して大きな行列Ｈを構築することの利点は以下の通りである。
１．異なるｚの値を用いることによって、比ｋｂ／ｎｂの符号（ｋｂ＝ｎｂ−ｍｂ）を、単一の基底行列Ｈｂから多くの異なる情報シーケンスサイズｋ＝ｚ×ｋｂについて設計することができる。
２．必要メモリがかなり減少する。構造化ＬＤＰＣ設計によって、記憶する必要があるのは基底行列Ｈｂおよびその１についての順列のみであり、これに必要なメモリはかなり少ない。なぜならＨｂは典型的にＨよりかなり小さく、順列は非常に単純だからである。
３．エンコードおよびデコードは、単一のビット毎にではなくビットのグループに対して実行することができる。例えば、ｚ個のメッセージからなる一グループがメモリから取り出され、順序変更されて、ベクトル変数ノードとベクトルチェックノードとの間で渡されるようになる。
【００１１】
構造化ＬＤＰＣ設計の考え方は実施の複雑さを大きく減少させるが、基底行列を設計し、与えられた対象Ｈサイズ用の順列行列を割り当てて、良好なエラー訂正性能を有し効率よくエンコードおよびデコードすることのできるＬＤＰＣ符号を得るような技術は存在しない。従って構造化Ｈを設計する方法および装置と、構造化Ｈ行列を用いてデータをエンコードおよびデコードするための方法および装置が望まれている。
【発明を実施するための最良の形態】
【００１２】
上述した要望に対処するために構造化パリティチェック行列Ｈを提案する。Ｈは基底行列Ｈｂの展開であり、ＨｂはセクションＨｂ１およびセクションＨｂ２を備え、Ｈｂ２は２より大きい奇数の重み（ｏｄｄ  ｗｅｉｇｈｔ）を有する列ｈｂを備える第一の部分と、行ｉと列ｊが、ｉ＝ｊとｉ＝ｊ＋１については１に等しく、他の位置については０に等しい行列要素を備える第二の部分とを備える。基底行列Ｈｂの展開は、第二の部分Ｈ’ｂ２の各列における１については同一部分行列を用い、ｈｂの偶数個の１については対になった部分行列を用いる。
【００１３】
本発明は、現在の記号セットｓ＝（ｓ０，…，ｓｋ−１）に基づいてパリティチェックビットｐ＝（ｐ０，…，ｐｍ−１）を生成する送信機を動作させる方法を包含する。その方法は、現在の記号セットｓ＝（ｓ０，…，ｓｋ−１）を受信する工程と、行列Ｈを用いてパリティチェックビットを決定する工程とを備える。現在の記号セットと共にパリティチェックビットが送信される。Ｈは基底行列Ｈｂの展開であり、ＨｂはセクションＨｂ１およびセクションＨｂ２を備える。Ｈｂ２は２より大きい奇数の重みを有する列ｈｂを有する第一の部分と、行ｉと列ｊが、ｉ＝ｊについては１に等しく、ｉ＝ｊ＋１については１に等しく、他の位置については０に等しい行列要素を備える第二の部分Ｈ’ｂ２とを備える。基底行列Ｈｂの展開は、第二の部分Ｈ’ｂ２の各列における１については同一部分行列を用い、この展開はｈｂにおける偶数個の１については対になった部分行列を用いる。
【００１４】
本発明は付加的に、現在の記号セットＳ＝（ｓ０，…，ｓｋ−１）を推測する受信機を動作させる方法を包含する。この方法は受信信号ベクトルｙ＝（ｙｏ，…，ｙｎ−１）を受信する工程と、行列Ｈを用いて現在の記号セットＳ＝（ｓ０，…，ｓｋ−１）を推測する工程とを備える。行列Ｈは基底行列Ｈｂの展開であり、ＨｂはセクションＨｂ１およびセクションＨｂ２を備え、Ｈｂ２は２より大きい奇数の重みを有する列ｈｂを備える第一の部分と、行ｉと列ｊが、ｉ＝ｊとｉ＝ｊ＋１については１に等しく、他の位置については０に等しい行列要素を備える第二の部分Ｈ’ｂ２とを備える。基底行列Ｈｂの展開は第二の部分Ｈ’ｂ２の各列における１については同一部分行列を用い、ｈｂにおける偶数個の１については対をなす部分行列を用いる。
【００１５】
本発明は付加的に、行列Ｈを記憶する記憶手段を備える装置と、行列Ｈを用いてパリティチェックビットを決定するマイクロプロセッサとを備える装置を包含し、Ｈは基底行列Ｈｂの展開であり、ＨｂはセクションＨｂ１およびセクションＨｂ２を備え、Ｈｂ２は２より大きい奇数の重みを有する列ｈｂを備える第一の部分と、行ｉと列ｊが、ｉ＝ｊについては１に等しく、ｉ＝ｊ＋１については１に等しく、他の位置については０に等しい行列要素を備える第二の部分Ｈ’ｂ２とを備える。基底行列Ｈｂの展開は第二の部分Ｈ’ｂ２の各列における１については同一部分行列を用い、ｈｂにおける偶数個の１については対をなす部分行列を用いる。
【００１６】
本発明は、行列Ｈを記憶する記憶手段と、信号ベクトルｙ＝（ｙｏ…ｙｎ−１）を受信する受信機と、マトリックスＨを用いて現在の記号セット（ｓ０，…，ｓｋ−１）を決定するマイクロプロセッサとを備える装置を包含する。マトリックスＨは基底行列Ｈｂの展開であり、ＨｂはセクションＨｂ１およびセクションＨｂ２を備え、Ｈｂ２は２より大きい奇数の重みを有する列ｈｂを有する第一の部分を備える。第二の部分Ｈ’ｂ２は、行ｉと列ｊが、ｉ＝ｊについては１に等しく、ｉ＝ｊ＋１については１に等しく、他の位置については０に等しい行列要素を備える。二つの同一部分行列がＨ’ｂ２のすべての列における１を展開するのに用いられ、対になった部分行列がｈｂにおける偶数個の１を展開するのに用いられる。
【００１７】
同様の要素に同様の部材番号を付した図面を参照すると、図３は本発明の第１実施形態に関するエンコーダ３００のブロック図である。図示したように、エンコーダ３００はマイクロプロセッサ３０１とルックアップテーブル３０３とを備える。本発明の第１実施形態のマイクロプロセッサ３０１は、ＭＳＣ８３００およびＤＳＰ５６３００ＤＳＰなどのデジタル信号プロセッサ（ＤＳＰ）を備えるが、これらに限定はされない。ルックアップテーブル３０３は行列を格納する格納手段として作用し、リードオンリーメモリを備えるが、当業者であれば他の形式のメモリ（例えば、ランダムアクセスメモリ、磁気記憶メモリなど）もまた同様に使用できることを認識できる。第２実施形態では、マイクロプロセッサ３０１とルックアップテーブル３０３の機能は、特定用途向け集積回路（ＡＳＩＣ）や、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）に組み込むことができる。特にルックアップテーブル３０３は、回路内の信号経路の有無に対応するメモリの形式で実施することができる。
【００１８】
上述したように、符号化されたデータは一般に、システムビットに加え、複数のパリティチェックビットとして出力され、パリティチェックとシステムビットは符号語ｘを形成する。本発明の第１実施形態において、パリティチェック行列Ｈはルックアップテーブル３０３に記憶され、式（１）を解くためにマイクロプロセッサ３０１によってアクセス可能である。特にマイクロプロセッサ３０１は、現在の記号セットｓ＝（ｓ０，…，ｓｋ−１）とパリティチェック行列Ｈに基づいてパリティチェックビットｐ＝（ｐ０，…，ｐｍ−１）にとって適切な値を決定する。その後、パリティチェックビットおよび記号セットは送信機に渡されて、受信機に送信される。
【００１９】
図４は本発明の一実施形態に関するデコーダ４００のブロック図である。図示したように、デコーダ４００はマイクロプロセッサ４０１とルックアップテーブル４０３とを備える。本発明の第１実施形態において、マイクロプロセッサ４０１は、ＭＳＣ８３００およびＤＳＰ５６３００ＤＳＰなどのデジタル信号プロセッサ（ＤＳＰ）を備えるが、これらに限定はされない。ルックアップテーブル４０３は行列Ｈを格納する格納手段として作用し、リードオンリーメモリを備えるが、当業者であれば他の形式のメモリ（例えば、ランダムアクセスメモリ、磁気記憶メモリなど）もまた同様に使用できることを認識できる。第２実施形態において、マイクロプロセッサ４０１とルックアップテーブル４０３の機能は、特定用途向け集積回路やフィールドプログラマブルゲートアレイ（ＦＰＧＡ）に組み込むことができる。特にルックアップテーブル４０３は回路内の信号経路の有無に対応するメモリの形式で実施することができる。
【００２０】
（受信機を介して受信された）受信信号ベクトルｙ＝（ｙ０，…，ｙｎ−１）は、ノイズ通信路を介して送信された符号語ｘに対応し、符号化されたデータｘは上述したように符号語ベクトルである。本発明の第１実施形態において、パリティチェック行列Ｈはルックアップテーブル４０３に記憶されており、ｙをデコードして、現在の記号セットｓ（すなわち、現在の記号セット（ｓ０，…，ｓｋ−１））を推定するのにマイクロプロセッサ４０１によってアクセスされる。特にマイクロプロセッサ４０１は、受信信号ベクトルｙ＝（ｙ０，…，ｙｎ−１）およびパリティチェック行列Ｈに基づいて、現在の記号セット（ｓ０，…，ｓｋ−１）を推定する。
【００２１】
この技術分野においてよく知られているように、エンコーダ４００が、マイクロプロセッサ４０１においてデコードするために、パリティチェック行列Ｈを用いる多くの方法がある。一つの方法は、Ｈを用いたベクトル行列乗算を実行して、起こり得るエラーパターンを決定するものである。別の方法は、グラフ内のエッジがＨにおける１に対応している二部グラフを構成し、二部グラフ上で反復してｙを処理するのにＨを用いる。
【００２２】
構造化ＬＤＰＣについて、ｚ×ｚの部分行列は順列行列や、順列行列の和や、あるいは任意の２値行列であってもよい。順列行列Ｐは各行に単一の１を有し、各列に単一の１を有しているため、その順列部分行列が用いられた場合、展開された行列Ｈの重み分布は基底行列Ｈｂのものと同様である。従ってＨｂの重み分布は所望の最終重み分布にできるだけ近いように選択される。以下の説明は、Ｈｂのエントリが順列行列によって置換される例であるが、任意の行列を用いてもよい。もしベクトルエッジの順列部分行列Ｐｚ×ｚが１を（行、列）エントリ（ｐ（ｉ）、ｉ）に有するならば、ベクトルエッジ内のｉ番目のエッジは、ベクトルエッジがベクトルチェックノードに接続される前に、ｐ（ｉ）番目の位置に順序変更される。言い換えると、この順序変更は、関連するベクトル変数ノード内のｉ番目の変数ノードを、関連するベクトル変数ノード内のｐ（ｉ）番目のチェックノードに連結させる。
【００２３】
Ｈからなる順列は、単純な循環シフトやビット逆転等のように、性能を損なうことなく非常に単純であり得る。例えば、単純な循環右シフトを用いることができる。この制限によって、各Ｈ行列は、ｍｂ×ｎｂモデル行列Ｈｂｍによって一意的に表現することができ、以下によって取得することができる。
・ｚ×ｚの全ゼロ部分行列表すべく、Ｈｂにおける各０を−１で置換し、そして、
・Ｈｂにおける各ｈｉｊ＝１を循環シフトサイズｐ（ｉ，ｊ）で置換する（ｐ（ｉ，ｊ）は負ではない）。
【００２４】
循環左シフト（ｘ  ｍｏｄ  ｚ）回数は循環右シフト（（ｚ−ｘ）  ｍｏｄ  ｚ）回数と等価であるため、循環右シフトを説明して、それを循環シフトの説明とすることは簡略化の点で適切である。先に述べたように、ＨとＨｂｍとの間には一対一のマッピングがある。従ってＨｂｍは、ｚが与えられた場合のＨの手短な表現である。表記上では、モデル行列は、添え字「ｂｍ」によって基底行列とは区別され、展開行列は、添え字「ｂｍ」を除去することによって区別される。これら３つの行列間の関係は図２に示される。この構造を用いることによって、符号はｍ×ｎのサイズのランダムなＨと類似したエラー訂正性能を有し、一方でエンコードおよびデコードはより小さいＨｂｍに基づいて実行される。
【００２５】
例えば、式（２）の行列は、以下のように、モデル行列Ｈｂｍを構築するための基底行列Ｈｂとして用いられてもよい。
【００２６】
【数７】
2008509635.tif 000006
ｚ＝３の場合、Ｈｂｍは、各−１を３×３の全ゼロ部分行列で置換し、各１を部分行列Ｐｉ（ｉ＝０，１，２）で置換することによって、（ｍｂ×ｚ）×（ｎｂ×ｚ）行列Ｈに変換される。ここで
【００２７】
【数８】
2008509635.tif 000007
Ｐ０は単位行列（ｉｄｅｎｔｉｔｙ  ｍａｔｒｉｘ）であり、Ｐｉ、ｉ＞０の列は、ｉ回数循環右シフトされたＰ０の列である。
【００２８】
ベクトルｑ＝［ｑ０，ｑ１，ｑ２］、ｑＰ０＝［ｑ０，ｑ１，ｑ２］、ｑＰ１＝［ｑ２，ｑ０，ｑ１］、ｑＰ２＝［ｑ１，ｑ２，ｑ０］であると仮定する。言い換えると、ｑＰ１はベクトルｑの循環右シフトとなる。一方、ＰｉｑＴはｑＴの循環上シフト、あるいはｑの等価循環左シフトとなる。ｚ×ｚの行列Ｑが用いられるときにも同様の規則が当てはまり、ＱＰｉはＱの列の循環右シフトとなり、ＰｉＱはＱの行の循環上シフトとなる。
【００２９】
＜基底行列Ｈ＞
ベクトル化しないＬＤＰＣ符号については、Ｈのパリティ部用の改良された階段構造を有するＨ行列は、性能を損なうことなく、有効なエンコードをもたらす。一般には、ｘ＝［ｓ  ｐ］＝［ｓ０，ｓ１，…，ｓｋ−１，ｐ０，ｐ１，…ｐｍ−１］であると仮定すると、ｍ×ｎのＨ行列は二つの部分行列、すなわち、
【００３０】
【数９】
2008509635.tif 000008
に分割することができる。ここでＨ２は改良された階段構造であり、Ｈ１はｍ×ｋのサイズの任意の二値行列であり得る。この同じ構造は、構造化ＬＤＰＣ設計に基底行列Ｈｂを構築するために用いることができる。同様に、改良された階段構造を用いることによって、Ｈｂを二つのセクションに分割することができる。Ｈｂ１はシステムビットｓに対応し、Ｈｂ２はパリティチェックビットｐに対応する。
【００３１】
【数１０】
2008509635.tif 000009
セクションＨｂ２はさらに二つのセクションに分割可能である。ベクトルｈｂは奇数の重みｗｈを有し、Ｈ’ｂ２は階段構造を有する。
【００３２】
【数１１】
2008509635.tif 000010
セクションＨｂ１は、ランダムに構築することができる。好ましくは、行列Ｈｂの全体は、所望の最終重み分布にできるだけ近づくような重み分布を有する。
【００３３】
＜シフトサイズ＞
基底行列Ｈｂをｍｂ×ｎｂモデル行列Ｈｂｍ（これはＨまで展開する）に変換するために、循環シフトサイズｐ（ｉ，ｊ）はＨｂの各１について決定される必要がある。シフトサイズはまずＨ２について特定されることができる。Ｈ２セクションについてのシフトサイズが決定された後に、Ｈ１セクションのシフトサイズは、Ｈの全体の良好な性能を達成するように決定することができる。基底行列のＨ１部および基底行列のＨ１部（セクションＨｂｍｉ）のシフトサイズは多くの異なる方法に割り当てることができる。例えば、シフトサイズについてのランダム値を選択することができ、シフトサイズが性能の顕著な低下を起こさなければ、それを受け入れることができる。過剰数の短周期循環あるいは低重みの符号語を導入した結果によって性能の低下が引き起こることがある。ＬＤＰＣ技術において利用可能な他の技術を用いてもよい。
【００３４】
与えられた対象Ｈサイズ用の循環シフトサイズｐ（ｉ，ｊ）は、デコード性能を損なうことなく、効率的なエンコードを可能にするように特定される。デコードを促進するためには、シフトは、互いに加算する場合には、ｈｂにおける１に対応するシフト行列の一つを除く全部が取り消されるように割り当てられてもよく、合計する場合には、Ｈ’ｂ２のすべてのベクトル行が取り消されるように割り当てられてもよい。これは、シフトサイズを一つのエントリを除いて対でｈｂに割り当てるように、また同じシフトサイズをＨ’ｂ２の各列における両方の１に割り当てるように変換する。例えば、ｈｂ＝［１  ０  ０  １  ０  ０  １］Ｔであれば、ｈｂｍ＝［３  −１  −１  ３−１  −１  ４］Ｔをモデル行列内の対応列とすることを受け入れることができる。というのはシフトサイズ３が対で割り当てられるためである。各列Ｈ’ｂ２の全ての非ゼロエントリ（両方とも１）には同じシフトサイズが割り当てられるので、任意のシフトサイズの選択肢は、シフトサイズ０（すなわち、単位部分行列）＋ベクトル列内のビットの順列に対応する。このように、Ｈ’ｂ２のすべてのシフトサイズは便宜上０に割り当てることができ、すなわち、Ｈ’ｂ２の各１は、Ｈに展開するとき、ｚ×ｚの単位部分行列で置換される。
【００３５】
循環の存在によって、ｈｂｍのシフトサイズは慎重に割り当てられなければならない。短い循環あるいは低重みの符号語の形成を回避するための規則を適用してもよい。循環を回避するために用いることが可能な一特性は：
もし２ｃエッジが長さ２ｃの一つの循環を基底行列Ｈｂに形成するならば、対応する２ｃベクトルエッジは、展開した行列Ｈにおける長さ２ｃのｚ循環を形成する。それは以下の場合において、および以下の場合に限ってである。
【００３６】
【数１２】
2008509635.tif 000011
ここでｚは展開係数（ｅｘｐａｎｓｉｏｎ  ｆａｃｔｏｒ）であり、ｐ（ｉ）はモデル行列Ｈｂｍにおけるエッジｉの循環シフトサイズであり、エッジ０，１，２、…、２ｃ−１（この順番で）はＨｂに循環を形成する。
【００３７】
Ｈｂ２の構造によって、ｈｂとＨ’ｂ２との間に循環が存在する。従ってｈｂｍにおける任意の二つの同一シフトサイズは、上記特性に従い、展開した行列Ｈ内で巡回のｚ回の繰り返しをもたらす。しかしながら、もしこれらの二つのシフトが遠く離間して存在するのであれば、循環は長い長さを有し、反復復号化に対してわずかの影響しか持たない。従って好ましい実施形態において、基底行列のｈｂが三個の１を有する場合、循環の長さを最大限にするために、同じシフトサイズが割り当てられる二つの１はｈｂｍの最上位値および底位置に配置され（できるだけ離間するように）、その一方でｈｂの中央に、対になっていないシフトサイズの一つの１を残す。例えば、ｈｂｍ＝［３  −１  ３  −１  −１  −１  ４］ＴはｈとＨ’２との間で長さ６のｚ循環となり、一方、ｈｂｍ＝［３  −１  ４  −１  −１  −１  ３］ＴはｈとＨ’２との間で長さ１４のｚ循環となる。ｈとＨ’２はｈｂとＨ’ｂ２から展開されている。
【００３８】
つまり、Ｈｂ２はモデル行列
【００３９】
【数１３】
2008509635.tif 000012
にマッピングされ、ｋｂ＝ｎｂ−ｍｂであり、ｈｂｍにおいてｗｈ個（奇数、ｗｈ＞＝３）の負ではないエントリが存在し、Ｈ’ｂｍ２において−１個のエントリは略して左側のブランクとなる。すべてのｐ（ｉ、ｋｂ）値は、任意のゼロでない部分行列にマッピングされ得る１回を除いてｈｂｍにおいて偶数回出現する。従って、ｗｈが奇数であるために、すべてのｗｈシフトに同じ値（例えば、０）を与えることが可能となる。Ｈ’ｂｍ２については、ｐ（ｉ，ｊ）＝ｐ（ｉ＋１，ｊ）、ｊ＝ｋｂ＋１、ｋｂ＋２、…、ｎｂ−１、ｉ＝ｊ−ｋｂ−１。好ましい実施形態において、ｗｈ＝３であると仮定すると、一実施形態は、ｈｂｍ＝［０  −１…−１  ｐｈ−１…−１…０］Ｔ、ｐｈ  ｍｏｄ  ｚ1０、およびｐ（ｉ，ｊ）＝ｐ（ｉ＋１，ｊ）＝０、ｊ＝ｋｂ＋１、ｋｂ＋２、…、ｎｂ−１、ｉ＝ｊ−ｋｂ−１をＨ’ｂｍ２部に有する。
【００４０】
上記説明は単位行列の循環シフトである部分行列を用いることに焦点を当てたが、一般には、任意の他の部分行列が用いられてもよい（またベースモデル行列の等価物で表現されてもよい）。エンコードを促進するための制限は：
１.Ｈ’ｂｍ２のすべての列において、二つのゼロでない部分行列が同一である。
２.ｈｂｍのｗｈ個（奇数、ｗｈ＞＝３）のゼロでない部分行列は、任意のゼロでない行列であり得る一つの部分行列を除いて対になっている（すなわち、一つの部分行列は他の部分行列と等しい）。
【００４１】
＜エンコード＞
エンコードとは、情報シーケンスｓを与えられたパリティシーケンスｐを決定する処理である。構造化ＬＤＰＣ符号をエンコードするために、各動作は単一のビットの代わりにｚビットのグループに対して行われる。あるいは、ベクトル演算は用いられなくてもよく、下記の式は等価なスカラー形式で実行される。エンコードするために、ｓはｚビットのｋｂ＝ｎｂ−ｍｂ個のグループに分割される。このグループ化されたｓをｕで表現することにする。
【００４２】
【数１４】
2008509635.tif 000013
ここでｕの各要素は以下の列ベクトルである。
【００４３】
【数１５】
2008509635.tif 000014
モデル行列Ｈｂｍを使用して、パリティシーケンスｐはｚ個のグループに決定される。グループ化されたｐをｖで表現することにする。
【００４４】
【数１６】
2008509635.tif 000015
ここでｖの各要素は以下の列ベクトルである。
【００４５】
【数１７】
2008509635.tif 000016
エンコードは２ステップで進む、すなわち、ｖ（０）を決定する初期化工程（ａ）と、ｖ（ｉ）からＶ（ｉ＋１）（ただし、０≦ｉ≦ｍｂ−２）を決定する反復工程（ｒｅｃｕｒｓｉｏｎ）（ｂ）である。
【００４６】
ｖ（０）の式は、式（１）の行を合計することによって導出され、以下のように得られる。
【００４７】
【数１８】
2008509635.tif 000017
ここでｘはｈｂｍの行インデックスであり、エントリは負ではなく、また、奇数の回数を用いる。好ましい実施形態において、ｈｂｍの最上位値と底位置のエントリは対になり、従って、１≦ｘ≦ｍｂ−２となる。式（１４）は、両側からＰ−１ｐ（ｘ、ｋｂ）を乗算することによって、ｖ（０）について解ける。ここで検討する特別の場合では、ｐ（ｘ，ｋｂ）が循環シフトを表し、Ｐ−１ｐ（ｘ、ｋｂ）＝Ｐｚ−ｐ（ｘ、ｋｂ）である。言い換えれば、ｖ（０）は以下の式によって得られる。
【００４８】
【数１９】
2008509635.tif 000018
一般には、式（１６）と（１７）において表現される反復はＨ’ｂ２の構造を考慮することによって、導き出すことができる。
【００４９】
【数２０】
2008509635.tif 000019
及び
【００５０】
【数２１】
2008509635.tif 000020
ただし
【００５１】
【数２２】
2008509635.tif 000021
従って、ｖ（０）にないすべてのパリティビットは、０≦ｉ≦ｍｂ−２について式（１６）および（１７）を反復して評価することによって決定される。
Ｈ’ｂ２における１のシフトサイズが全ゼロである好ましい実施形態において、式（１６）および（１７）は式（１９）および（２０）として簡略化される。
【００５２】
【数２３】
2008509635.tif 000022
及び
【００５３】
【数２４】
2008509635.tif 000023
従って、一般的な場合のように、ｖ（０）にないすべてのパリティビットは、０≦ｉ≦ｍｂ−２についての式（１９）および（２０）を反復して評価することによって決定される。
【００５４】
式（１４）、（１９）、および（２０）はエンコードアルゴリズムを表している。これらの式もまた、標準デジタル論理アーキテクチャの観点から直接的解釈を有する。まず、Ｈｂｍの負ではない要素ｐ（ｉ，ｊ）がベクトルの循環シフトサイズを表現しているため、Ｐｐ（ｉ，ｊ）ｕ（ｊ）の形式のすべての積はサイズｚのバレルシフタによって実現できる。ゼロの循環シフトサイズはバレルシフトされる必要はない。すべての可能な循環シフトを実行するバレルシフタは各入力ビットからすべての出力ビットに接続を供給しなくてはならないために、それが起動する速度はｚに依存する。与えられたｚについて、すべての可能な循環シフトの適切な部分集合のみを許可することによって複雑性を減少させ、また、速度を増加させることができる。例えば、Ｈｂｍは偶数の循環シフトサイズのみによって構築されることができる。式（１４）、（１９）、および（２０）における合計は、ｐ（ｉ，ｊ）＝−１であるときに開閉される（すなわち、更新しない）ベクトル的ＸＯＲ（排他的ＯＲ）演算を表現する。
【００５５】
式（１４）、（１９）、および（２０）において合計を実施するために、Ｈｂｍのエントリｐ（ｉ，ｊ）（０≦ｉ≦ｋｂ、０≦ｊ≦ｍｂ−１）は、［ｌｏｇ２ｚ］＋１ビットの幅のリードオンリーメモリ（ＲＯＭ）に記憶され得る。グループ化情報シーケンスはサイズｚメモリに記憶されて、起こった順番に読み出され得る。各情報ベクトルｕ（ｊ）が読み出されるとき、必要な循環シフトのバレルシフタを指示するＨｂｍのＲＯＭから対応するエントリが読み出され得る。循環シフトの後、部分的な合計を含むレジスタが更新される。式（１４）について、各内部の和が完了した後、その結果は外部の合計を含む他のレジスタを更新することに使用することができる。外部の合計が完了したとき、それはｚ−ｐ（ｘ、ｋｂ）によって循環的にシフトされ得る。
【００５６】
バレルシフトが単一のクロック周期で実施可能であると仮定すると、エンコードはほぼ（ｋｂ＋１）ｍｂクロック周期で実施可能である。この数字は、ｍｂ−１個の余分なｚ幅のレジスタの費用で、式（１４）が計算されているときに利用可能となる結果を利用して式（１９）および（２０）の合計を計算して記憶させることによって、減少させることができる。
【００５７】
＜行列の拡張＞
符号拡張手順は、低いレートの符号に到達するために構造化符号に適用することができる。徐々に低くなるレート符号を、増加的冗長（ＩＲ）手順の連続送信において用いることができる。具体的には１番目の送信のモデル行列は下記の式で表せる。
【００５８】
【数２５】
2008509635.tif 000024
そして、２番目の送信についてのモデル行列は以下の式
【００５９】
【数２６】
2008509635.tif 000025
等を用いてもよい。各送信ｉについて、部分行列Ｈ（ｉ）ｂｍ２は（９）の形式と、ｍ（ｉ）ｂ×ｍ（ｉ）ｂのサイズとを有している。１番目の送信はｎ（１）ｂ＝ｋｂ＋ｍ（１）ｂグループのビットすなわち［ｕ（０）、ｕ（１）、…、ｕ（ｋｂ−１）、ｖ（１）（０）、ｖ（１）（１）、…、ｖ（１）（ｍ（１）ｂ−１）］を送信してもよい。尚、各グループのサイズはｚである。１番目の送信の後のデコードは受信信号すなわち［ｕ（０）、ｕ（１）、…、ｕ（ｋｂ−１）、ｖ（１）（０）、ｖ（１）（１）、…、ｖ（１）（ｍ（１）ｂ−１）］と、式（２１）とを用いて実行される。２番目の送信はサイズｚのビットからなる他のｍ（２）ｂグループのビットすなわち［ｖ（２）（０）、ｖ（２）（１）、…、ｖ（２）（ｍ（２）ｂ−１）］を送信してもよい。尚、ｍ２＝ｍ（２）ｂｚであり、１番目と２番目の送信のビットすなわち［ｕ（０）、ｕ（１）、…、ｕ（ｋｂ−１）、ｖ（１）（０）、ｖ（１）（１）、…、ｖ（１）（ｍ（１）ｂ−１）、ｖ（２）（０）、ｖ（２）（１）、…、ｖ（２）（ｍ（２）ｂ−１）］は式（２２）に対応する符号語である。従って、２番目の送信の後のデコードは、式（２２）と、１番目の送信と２番目の送信からの結合受信信号とに基づいて実行される。この手順はより多くの送信について繰り返されてもよい。２番目の送信後のデコードは、１番目の送信の比より低い比ｋｂ／ｎｂ（２）＝ｋｂ／（ｎｂ（１）＋ｍｂ（２））の符号に基づいている。この手順は多くの送信について繰り返され、付加的な送信の各々はより強い、より低い比の符号に寄与する。
【００６０】
図５はエンコーダ３００、特に、マイクロプロセッサ３０１の動作を示すフローチャートである。論理フローは現在の記号セット（ｓ０，…，ｓｋ−１）がマイクロプロセッサ３０１によって受信されるステップ５０１において始まる。ステップ５０３において、パリティチェックビットの値は現在の記号セットおよびＨに基づいて決定される。特に、パリティチェックビット（ｐ０，…，ｐｍ−１）は上述したように決定される。Ｈは基底行列Ｈｂの展開である。説明したとおり、ＨｂはセクションＨｂ１とセクションＨｂ２を備える。Ｈｂ２は２より大きい奇数の重みを有する列ｈｂからなる第一の部分と、行ｉと列ｊが、ｉ＝ｊについては１に等しく、ｉ＝ｊ＋１については１に等しく、他の位置については０に等しい行列要素を備える第２の部分とを備える。加えて、（Ｈを生成する）基底行列Ｈｂの展開は第二の部分Ｈ’ｂ２の各列の１については同一部分行列を用い、ｈｂにおける偶数個の１については対をなす部分行列を用いる。ステップ５０５において、現在の記号セットおよびパリティチェックビットは、無線送信によって送信される。
【００６１】
図６はデコーダ４００、特に、マイクロプロセッサ４０１の動作を示すフローチャートである。論理フローは、受信信号ベクトルｙ＝（ｙ０，…，ｙｎ−１）が受信されるステップ６０１において始まる。ステップ６０３において、現在の記号セットｓ（すなわち、現在の記号セット（ｓ０，…，ｓｋ−１））の推定値はＨに基づいて決定される。説明したとおり、Ｈは基底行列Ｈｂの展開であり、ＨｂはセクションＨｂ１およびセクションＨｂ２を備え、Ｈｂ２は２より大きい奇数の重みを有する列ｈｂからなる第一の部分と、行ｉと列ｊが、ｉ＝ｊについては１に等しく、ｉ＝ｊ＋１については１に等しく、他の位置については０に等しい行列要素を備える第２の部分とを備える。
【００６２】
本発明は特定の実施形態について特に図示され記載されてはいるが、本発明の精神と範囲を超えることなく、形式と詳細において種々の変化がなされることは当業者によって理解されよう。例えば、本発明の図示において、ｘ内におけるｓｉおよびｐｉの順序付けが定義されているが、Ｈの列が再順序付けされる限りは、符号語ビットを任意の順序で収集することができるため、当業者であれば符号語ビットがＨの列ｘ内におけるビットの他の順序付けを発生しうることを認識するであろう。従って、上記の記載は二値符号（すなわち、ガロア域ＧＦ（２）上に定義された符号）を特に図示し説明したものであるが、当業者は任意のＧＦも同様に用いることができることを認識するである。上述の例は一つの形式で示されているものの、同様のエンコードおよび符号訂正手順を可能にする他の形式も可能である。例えば、Ｈの行はパリティチェックビットの値に影響を与えることなく、その順序を変えてもよい。他の例において、改良された階段構造は、パリティチェックビットのサブセットのために用いられてもよい。さらに他の例において、基底行列を展開行列に展開するときに、付加的ステップが実行されてもよい。行列Ｈも、パリティチェック行列に依存する任意のタイプのデコーダにおいて用いられてもよい。本発明は、このような変化が以下の請求の範囲内で起きることを目的とする。
【図面の簡単な説明】
【００６３】
【図１】（１２，６）のＨ行列の二部グラフを示す。
【図２】基底行列Ｈｂとモデル行列Ｈｂｍと最終の展開行列Ｈとの関係を示す。
【図３】エンコーダのブロック図。
【図４】デコーダのブロック図。
【図５】図３のエンコーダの動作を示すフローチャート。
【図６】図４のエンコーダの動作を示すフローチャート。
【図１】
2008509635.tif 000029
【図２】
2008509635.tif 000030
【図３】
2008509635.tif 000031
【図４】
2008509635.tif 000032
【図５】
2008509635.tif 000033
【図６】
2008509635.tif 000034
【国際調査報告】
2008509635.tif 000035