(57)【要約】  受信した情報（４０１）に対しパリティ検査ビットが計算される（４０３）。各符号化率の最大の符号長さに対する基本モデル行列（４０３）が定義される。基本モデル行列（４０３）におけるシフトの組｛ｐ（ｉ，ｊ）｝は、同じ符号化率の他の全ての符号長さに対するシフトサイズを決定するために用いられる。拡張係数ｚｆに相当する符号サイズに対するシフトサイズ｛ｐ（ｆ，ｉ，ｊ）｝は、ｐ（ｉ，ｊ）を比例的にスケーリングすることによって、｛ｐ（ｉ，ｊ）｝から導かれ、｛ｐ（ｆ，ｉ，ｊ）｝によるモデル行列は、第ｆ番目の符号に対するパリティ検査ビット（４０３）を決定するために用いられる。
2008510379.tif 000002
【特許請求の範囲】
【請求項１】
情報ブロックに基づきパリティ検査ビットを生成する送信機を動作させる方法であって、
最大の符号長さに対する１組のシフトサイズｐ（ｉ，ｊ）を有する基本モデル行列を定義する工程と、
１組のシフトサイズｐ（ｉ，ｊ）に基づき他の全ての符号長さに対するシフトサイズｐ（ｆ，ｉ，ｊ）を決定する工程と、
［ここで、ｆは符号長さの指標であり、ｐ（ｆ，ｉ，ｊ）＝Ｆ（ｐ（ｉ，ｊ），ｚ０／ｚｆ）であり、ｚ０は最大の符号長さの拡張係数であり、ｚｆは第ｆ番目の符号長さの拡張係数である］
情報ブロックｓ＝（ｓ０，．．．，ｓｋｆ−１）を受信する工程と、
ｐ（ｆ，ｉ，ｊ）によって定義されるモデル行列を用いてパリティ検査ビットを決定する工程と、
情報ブロックに加えてパリティ検査ビットを送信する工程と、からなる方法。
［ここで｛ｐ（ｉ，ｊ）｝は次の通りである］
【表１】
2008510379.tif 000019
【請求項２】
ｐ（ｆ，ｉ，ｊ）は次式の通りである請求項１に記載の方法。
【数１】
2008510379.tif 000020
［ここで、└ｘ┘は床関数を表す］
【請求項３】
ｐ（ｆ，ｉ，ｊ）は次式の通りである請求項１に記載の方法。
【数２】
2008510379.tif 000021
［ここで、［ｘ］は丸め関数を表す］
【請求項４】
ｐ（ｆ，ｉ，ｊ）は次式の通りである請求項１に記載の方法。
【数３】
2008510379.tif 000022
［ここで、┌ｘ┐は天井関数を表す］
【請求項５】
拡張係数ｚｆを有するｐ（ｆ，ｉ，ｊ）によって定義されるモデル行列Ｈｂｍ（ｆ）から拡張されるパリティ検査行列Ｈ（ｆ）に基づきパリティ検査ビットが見出される請求項１に記載の方法。
【請求項６】
最大の符号長さに対する１組のシフトサイズｐ（ｉ，ｊ）を有する基本モデル行列を記憶するための記憶手段と、
情報ブロックｓ＝（ｓ０，．．．，ｓｋｆ−１）及び基本モデル行列を受信し、１組のシフトサイズｐ（ｉ，ｊ）に基づき他の全ての符号長さに対するシフトサイズｐ（ｆ，ｉ，ｊ）を決定するマイクロプロセッサと、
［ここで、ｆは符号長さの指標であり、ｐ（ｆ，ｉ，ｊ）＝Ｆ（ｐ（ｉ，ｊ），ｚ０／ｚｆ）であり、ｚ０は最大の符号長さの拡張係数であり、ｚｆは第ｆ番目の符号長さの拡張係数である］
マイクロプロセッサはｐ（ｆ，ｉ，ｊ）によって定義されるモデル行列に基づくパリティ検査ビットと、情報ブロックｓ＝（ｓ０，．．．，ｓｋｆ−１）とを出力することと、からなる装置。
［ここで｛ｐ（ｉ，ｊ）｝は次の通りである］
【表２】
2008510379.tif 000023
【請求項７】
ｐ（ｆ，ｉ，ｊ）は次式の通りである請求項６に記載の装置。
【数４】
2008510379.tif 000024
［ここで、└ｘ┘は床関数を表す］
【請求項８】
ｐ（ｆ，ｉ，ｊ）＝Ｆ（ｐ（ｉ，ｊ），ｚ０／ｚｆ）の値を有するリードオンリメモリを含む請求項６に記載の装置。
【請求項９】
ｚ０／ｚｆの値を有するリードオンリメモリを含む請求項６に記載の装置。
【請求項１０】
情報ブロックｓ＝（ｓ０，．．．，ｓｋｆ−１）を推定する受信機を動作させる方法であって、
信号ベクトルを受信する工程と、
最大の符号長さに対する１組のシフトサイズｐ（ｉ，ｊ）を有する基本モデル行列を定義する工程と、
１組のシフトサイズｐ（ｉ，ｊ）に基づき他の全ての符号長さに対するシフトサイズｐ（ｆ，ｉ，ｊ）を決定する工程と、
［ここで、ｆは符号長さの指標であり、ｐ（ｆ，ｉ，ｊ）＝Ｆ（ｐ（ｉ，ｊ），ｚ０／ｚｆ）であり、ｚ０は最大の符号長さの拡張係数であり、ｚｆは第ｆ番目の符号長さの拡張係数である］
ｐ（ｆ，ｉ，ｊ）によって定義されるモデル行列と受信した信号ベクトルとに基づき、情報ブロックｓ＝（ｓ０，．．．，ｓｋｆ−１）を推定する工程と、からなる方法。
［ここで｛ｐ（ｉ，ｊ）｝は次の通りである］
【表３】
2008510379.tif 000025
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータのエンコード及びデコードに関する。より詳細には、本発明は低密度パリティ検査（ＬＤＰＣ）符号を利用するデータのエンコード及びデコードのための方法並びに装置に関する。
【背景技術】
【０００２】
低密度パリティ検査（ＬＤＰＣ）符号は、パリティ検査行列Ｈによって指定される線形ブロック符号である。一般に、ＬＤＰＣ符号は、ｑ≧２のガロア域ＧＦ（ｑ）によって定義される。ｑ＝２の場合、符号は二値符号である。全ての線形ブロック符号は、ｋビットの情報ベクトルｓ１×ｋと符号生成行列Ｇｋ×ｎとの積として記述可能であり、ｎビットの符号語ｘ１×ｎを生成する。ここで符号化率は、ｒ＝ｋ／ｎである。符号語ｘはノイズを有するチャネルを通じて送信され、受信信号ベクトルｙは情報ベクトルｓ１×ｋを推定するためにデコーダへ渡される。
【０００３】
ｎ次元空間が与えられると、Ｇの行はｋ次元の符号語部分空間Ｃを張り、パリティ検査行列Ｈｍ×ｎの行は、ｍ次元の双対空間Ｃ⊥を張る。ここで、ｍ＝ｎ−ｋである。ｘ＝ｓＧ、かつ、ＧＨＴ＝０ならば、部分空間Ｃにおける全ての符号語に対し、ｘＨＴ＝０となる。ここで、“Ｔ”（又は斜体の“Ｔ”）は行列の転置を表す。ＬＤＰＣ符号の説明では、これは一般に次のように記述される。
【０００４】
【数１】
2008510379.tif 000003
ここで、０は全てゼロの行ベクトルであり、符号語ｘ＝［ｓ  ｐ］＝［ｓ０，ｓ１，．．．，ｓｋ−１，ｐ０，ｐ１，．．．，ｐｍ−１］である。ここで、ｐ０，．．．，ｐｍ−１はパリティ検査ビットである。また、ｓ０，．．．，ｓｋ−１はシステマティックビットであり、情報ブロック内の情報ビットと等しい。
【０００５】
ＬＤＰＣ符号においては、Ｈにおける非ゼロのエントリの密度は低く、即ち、Ｈにはわずかな割合の１しか存在せず、密なＨを用いるよりも優れた誤り訂正性能と、簡単なデコードとが可能となる。また、パリティ検査行列は二分グラフによっても記述可能である。二分グラフは、符号のグラフ記述であるのみならず、デコーダのモデルでもある。二分グラフでは、符号語ビット（即ち、Ｈの各列）は左側の変数ノードによって表現され、各パリティ検査方程式（即ち、Ｈの各行）は右側の検査ノードによって表現される。各変数ノードはＨの列に相当し、各検査ノードはＨの行に相当するので、交換可能に「変数ノード」及びＨの「列」と呼ばれ、交換可能に「検査ノード」及びＨの「行」と呼ばれる。変数ノードは検査ノードにのみ接続されており、検査ノードは変数ノードにのみ接続されている。ｎ個の符号語ビット及びｍ個のパリティビットを有する符号では、符号語ビットｊが検査方程式ｉに参加する場合、エッジにて変数ノードｖｊが検査ノードｃｉへ接続される（ｉ＝０，１，．．．，ｍ−１、ｊ＝０，１，．．．，ｎ−１）。換言すると、パリティ検査行列Ｈのエントリｈｉｊが１である場合、変数ノードｊが検査ノードｉへ接続される。方程式（１）を反映すると、全ての検査ノードが偶パリティを有する場合、変数ノードは有効な符号語を表現する。
【０００６】
パリティ検査行列、パリティ検査方程式及び二分グラフの間の関係を示すため、一例を以下に示す。ｎ＝１２とすると、符号化率１／２の符号は次式によって定義される。
【０００７】
【数２】
2008510379.tif 000004
左側部分はｋ（＝６）個の情報ビットｓに相当し、右側部分はｍ（＝６）個のパリティビットｐに相当する。式（１）を適用すると、式（２）におけるＨによって次の６個のパリティ検査方程式が定義される。また、Ｈの対応する二分グラフを図１に示す。
【０００８】
【数３】
2008510379.tif 000005
充分な有限長さのＬＤＰＣ符号の二分グラフは、必然的にサイクルを有する。長さ２ｄのサイクル（サイクル−２ｄのように表記される）は、ｄ個の変数ノード及びｄ個の検査ノードを通過し、いずれのエッジも繰り返すことなく各ノードをそのノード自体へ接続する、２ｄ個のエッジからなる経路である。短いサイクル、特にサイクル−４は、反復的デコーダ（ｉｔｅｒａｔｉｖｅ  ｄｅｃｏｄｅｒ）の性能を低下させるので、通常、符号設計においては回避される。
【０００９】
符号サイズが大きくなると、無作為に構成されているＬＤＰＣ符号のエンコード及びデコードは困難になる。構造化ＬＤＰＣ設計では、大きなｍ×ｎ擬似乱数Ｈ行列を直接的に構築する代わりに、小さなｍｂ×ｎｂの基本行列Ｈｂから開始し、ｚ個のＨｂの複製を作成して、そのｚ個の複製を相互に連結して大きなｍ×ｎのＨ行列を形成する。ここで、ｍ＝ｍｂ×ｚ，ｎ＝ｎｂ×ｚである。行列表現を用いると、ＨｂからＨを構築するには、Ｈｂの各１はｚ×ｚ置換部分行列によって置き換えられ、Ｈｂの各０はｚ×ｚ全ゼロ部分行列によって置き換えられる。この置換は非常に簡単であり、性能を損なわないことが示されている。例えば、単位行列の列を所与の量だけ巡回右シフトすることによって置換部分行列が得られる簡単な巡回右シフトは、デコード性能を低下させることなく用いられ得る。（ｘ  ｍｏｄ  ｚ）回の巡回左シフトは（（ｚ−ｘ）  ｍｏｄ  ｚ）回の巡回右シフトと等しいので、本明細書では、巡回右シフトのみを説明し、簡単のため巡回シフトと呼ぶ。この制約を用いると、ｚ×ｚの全ゼロ行列を表すようにＨｂの各ｈｉｊ＝０をｐ（ｉ，ｊ）＝−１によって置き換え、Ｈｂの各ｈｉｊ＝１をｐ（ｉ，ｊ）≧０の巡回シフトサイズに置き換えることによって得られるｍｂ×ｎｂのモデル行列Ｈｂｍにより、各行列Ｈをユニークに表現することが可能である。
【００１０】
したがって、拡張した行列Ｈを用いる代わりに、モデル行列Ｈｂｍによって、符号がユニークに定義される。充分に小さなｍｂ×ｎｂのＨｂｍと、各々サイズｚを有するビットのベクトルとに基づき、エンコード及びデコードの両方が実行され得る。
【００１１】
この手順では、本質的には、Ｈｂの各エッジはＨのサイズｚのベクトルエッジ（Ｈｂｍのｐ（ｉ，ｊ）によって表現される）に対しマッピングされ、Ｈｂの各変数ノードはＨの長さｚのベクトル変数ノード（Ｈｂｍの列に相当）に対しマッピングされ、Ｈｂの各検査ノードはＨの長さｚのベクトル検査ノード（Ｈｂｍの行に相当）に対しマッピングされる。構造化設計では、次の２つの段階を通じてＨに無作為性が構築される：（ａ）偽似乱数基本行列Ｈｂ、（ｂ）各ベクトルエッジ内のエッジの偽似乱数シフト。無作為化に関する両段階は非常に簡単であるため、構造化設計の記憶及び処理の複雑性は低い。
【００１２】
多くの場合、ＩＥＥＥ  ８０２．１６標準規格において定義されているシステムなどのシステムでは、サイズ（ｎｆ，ｋｆ）の符号のファミリに対する誤り訂正符号を提供することが必要である。ここで、ファミリ内の符号は全て、同じ符号化率Ｒ＝ｋｆ／ｎｆを有し、符号サイズは、ｎｆ＝ｚｆ×ｎｂ，ｋｆ＝ｚｆ×ｋｂ（ｆ＝０，１，．．．，ｆｍａｘ）のように、基本サイズからスケーリングされている。ここで、符号ファミリにおけるメンバの総数は（ｆｍａｘ＋１）であり、ｚｆはファミリにおける第ｆ番目の符号に対する拡張係数である。これらのシステムでは、１つの基本行列Ｈｂ及び１組の適切なｚｆから、全ての（ｎｆ，ｋｆ）に対する符号を導くことが可能である。ｐ（ｆ，ｉ，ｊ）を、拡張係数ｚｆの第ｆ番目のモデル行列Ｈｂｍ（ｆ）内の位置（ｉ，ｊ）に位置するベクトルエッジのシフトサイズとする。したがって、交換可能に１組のシフトサイズ｛ｐ（ｆ，ｉ，ｊ）｝及びモデル行列Ｈｂｍ（ｆ）と呼ばれる。
【００１３】
しかしながら、各Ｈｂｍ（ｆ）に対してシフトサイズｐ（ｆ，ｉ，ｊ）を如何に定義するかは明らかでない。符号のファミリを定義するための一手法は、全ての所与のｆに対して独立に、基本行列Ｈｂ及びｐ（ｆ，ｉ，ｊ）（０≦ｉ≦ｍ−１，０≦ｊ≦ｎ−１）のうちの一方又は両方をサーチすることである。しかしながら、この手法では、全てのｆについて、Ｈｂ及びｐ（ｆ，ｉ，ｊ）（０≦ｉ≦ｍ−１，０≦ｊ≦ｎ−１）のうちの一方又は両方が指定され、記憶される必要がある。
【００１４】
ＨｂによってＬＤＰＣデコーダの基本構造及びメッセージの相互連結が定義されるため、ファミリの全ての符号に対しＨｂを再利用することが好適であろう。ファミリの全ての符号によって同じＨｂが共有されると、
・Ｈｂのエントリ（ｉ，ｊ）が０であるとき、シフトサイズｐ（ｆ，ｉ，ｊ）＝−１である。シフトサイズｐ（ｆ，ｉ，ｊ）＝−１は、二値パリティ検査行列Ｈ（ｆ）への拡張の際にモデル行列Ｈｂｍ（ｆ）のエントリ（ｉ，ｊ）を置き換えるために用いられる、ｚｆ×ｚｆの全ゼロ部分行列を表すために用いられる。Ｈｂのエントリ（ｉ，ｊ）が０である場合、任意のｆに対するｐ（ｆ，ｉ，ｊ）は同じである。即ち、ｐ（ｆ，ｉ，ｊ）≡−１である。なお、“−１”は全ゼロ部分行列のラベルでしかなく、例えば、“−２”又は“∞”など、負でない整数以外の任意の他のラベルが同等に用いられ得る。
・Ｈｂのエントリ（ｉ，ｊ）が１であるとき、シフトサイズｐ（ｆ，ｉ，ｊ）≧０である。シフトサイズｐ（ｆ，ｉ，ｊ）≧０は、ｐ（ｆ，ｉ，ｊ）列だけ巡回右シフトされたｚｆ×ｚｆ単位部分行列を表すために用いられる。この部分行列は、二値パリティ検査行列Ｈ（ｆ）への拡張の際にモデル行列Ｈｂｍ（ｆ）のエントリ（ｉ，ｊ）を置き換えるために用いられる。異なるｆに対するｐ（ｆ，ｉ，ｊ）の値は異なる場合がある。即ち、異なるｆに対するＨｂｍ（ｆ）のエントリ（ｉ，ｊ）は異なる場合がある。
【００１５】
負でないｐ（ｆ，ｉ，ｊ）の値に関しては、任意のｚｆに対し、ｐ（ｆ，ｉ，ｊ）＝ｐ（ｉ，ｊ）  ｍｏｄ  ｚｆを用いることが提案されている。ここで、シフトサイズの組｛ｐ（ｉ，ｊ）｝は全てのｚｆに対して同じである。したがって、｛ｐ（ｉ，ｊ）｝の１つの組しか指定される必要がなく、異なるｚｆの符号を実装することの複雑性は潜在的に減少される。しかしながら、モジュロ演算の影響のため、１組の｛ｐ（ｉ，ｊ）｝が１つのｚｆに対する不良なサイクルパターンを回避するように設計されることによって、別のｚｆに対するサイクルの数は大きく、符号語の重みは低くなり、一部の（ｎｆ，ｋｆ）に対する誤り訂正性能は低下する。
【発明の開示】
【発明が解決しようとする課題】
【００１６】
したがって、全ての符号サイズ（ｎｆ，ｋｆ）に対して所望の符号特性を維持しつつ、１組の｛ｐ（ｉ，ｊ）｝からシフトサイズ｛ｐ（ｆ，ｉ，ｊ）｝を導く方法の必要が存在する。
【課題を解決するための手段】
【００１７】
上述の必要に対処するために、各符号化率のうちの最大の符号長さに対し、基本モデル行列が定義される。基本モデル行列におけるシフトの組｛ｐ（ｉ，ｊ）｝は、同じ符号化率の他の全ての符号長さに対するシフトサイズを決定するために用いられる。拡張係数ｚｆに相当する符号サイズに対するシフトサイズ｛ｐ（ｆ，ｉ，ｊ）｝は、ｐ（ｉ，ｊ）を比例的にスケーリングすることによって｛ｐ（ｉ，ｊ）｝から導かれ、｛ｐ（ｆ，ｉ，ｊ）｝によって定義されるモデル行列は、第ｆ番目の符号に対するパリティ検査ビットを決定するために用いられる。
【００１８】
本発明は、情報ブロックに基づきパリティ検査ビットを生成する送信機を動作させるための方法に関する。この方法は、最大の符号長さに対する１組のシフトサイズｐ（ｉ，ｊ）を有する基本モデル行列を定義する工程と、１組のシフトサイズｐ（ｉ，ｊ）に基づき他の全ての符号長さに対するシフトサイズｐ（ｆ，ｉ，ｊ）を決定する工程と、を含む。ここで、ｆは符号長さの指標であり、ｐ（ｆ，ｉ，ｊ）＝Ｆ（ｐ（ｉ，ｊ），ｚ０／ｚｆ）であり、ｚ０は最大の符号長さの拡張係数であり、ｚｆは第ｆ番目の符号長さの拡張係数である。情報ブロックが受信され、モデル行列を用いてパリティ検査ビットが決定される。モデル行列はｐ（ｆ，ｉ，ｊ）によって定義される。
【００１９】
また、本発明は、最大の符号長さに対する１組のシフトサイズｐ（ｉ，ｊ）を有する基本モデル行列を記憶するための記憶手段を備える装置に関する。この装置は、これに加えて、情報ブロックｓ＝（ｓ０，．．．，ｓｋｆ−１）及び基本モデル行列を受信するマイクロプロセッサを備える。マイクロプロセッサは、１組のシフトサイズｐ（ｉ，ｊ）に基づき他の全ての符号長さに対するシフトサイズｐ（ｆ，ｉ，ｊ）を決定する。ここで、ｆは符号長さの指標であり、ｐ（ｆ，ｉ，ｊ）＝Ｆ（ｐ（ｉ，ｊ），ｚ０／ｚｆ）であり、ｚ０は最大の符号長さの拡張係数であり、ｚｆは第ｆ番目の符号長さの拡張係数である。マイクロプロセッサはｐ（ｆ，ｉ，ｊ）によって定義されるモデル行列に基づくパリティ検査ビットと、情報ブロックｓ＝（ｓ０，．．．，ｓｋｆ−１）とを出力する。
【００２０】
また、本発明は、情報ブロックｓ＝（ｓ０，．．．，ｓｋｆ−１）を推定する受信機を動作させるための方法に関する。この方法は、信号ベクトルを受信する工程と、最大の符号長さに対する１組のシフトサイズｐ（ｉ，ｊ）を有する基本モデル行列を定義する工程と、１組のシフトサイズｐ（ｉ，ｊ）に基づき他の全ての符号長さに対するシフトサイズｐ（ｆ，ｉ，ｊ）を決定する工程と、を含む。ここで、ｆは符号長さの指標であり、ｐ（ｆ，ｉ，ｊ）＝Ｆ（ｐ（ｉ，ｊ），ｚ０／ｚｆ）であり、ｚ０は最大の符号長さの拡張係数であり、ｚｆは第ｆ番目の符号長さの拡張係数である。ｐ（ｆ，ｉ，ｊ）によって定義されるモデル行列と受信した信号ベクトルとに基づき、情報ブロックｓ＝（ｓ０，．．．，ｓｋｆ−１）が推定される。
【００２１】
最後に、本発明は、最大の符号長さに対する１組のシフトサイズｐ（ｉ，ｊ）を有する基本モデル行列を記憶するための記憶手段を備える装置に関する。この装置は、これに加えて、信号ベクトルを受信し、１組のシフトサイズｐ（ｉ，ｊ）に基づき他の全ての符号長さに対するシフトサイズｐ（ｆ，ｉ，ｊ）を決定するデコーダを備える。ここで、ｆは符号長さの指標であり、ｐ（ｆ，ｉ，ｊ）＝Ｆ（ｐ（ｉ，ｊ），ｚ０／ｚｆ）であり、ｚ０は最大の符号長さの拡張係数であり、ｚｆは第ｆ番目の符号長さの拡張係数である。デコーダはｐ（ｆ，ｉ，ｊ）によって定義されるモデル行列と受信した信号ベクトルとに基づく情報ブロックｓ＝（ｓ０，．．．，ｓｋｆ−１）に対する推定値を出力する。
【発明を実施するための最良の形態】
【００２２】
拡張した行列Ｈの特性は、基本行列Ｈｂの特性及びシフトサイズｐ（ｉ，ｊ）に密接に関連することが示されている。符号設計の疑似巡回性のため、一定の所望されないシフトサイズｐ（ｉ，ｊ）のパターンによってＨｂのサイクル及び符号語のパターンが保存され、拡張した行列Ｈにおいて複数回繰り返されることによって、誤り訂正性能は許容不能なものとなる。
【００２３】
低い重みの符号語は短いサイクルを含むため、Ｈｂに重み−１列が存在しない場合、充分なデコード性能を得るには、対象の符号サイズ（ｎｆ，ｋｆ）の全てに対し短いサイクルが壊れていることを確認することで充分である。
【００２４】
次の条件が満たされる場合、拡張した行列においてＨｂのサイクルが複製されることが分かっている。
基本行列Ｈｂにおいて２ｃ個のエッジが長さ２ｃのサイクルを形成する場合、拡張した行列Ｈにおいて、対応する２ｃ個のベクトルエッジは、次式であるとき、かつそのときに限り、長さ２ｃのｚ個のサイクルを形成する。
【００２５】
【数４】
2008510379.tif 000006
ここで、ｚは拡張係数であり、ｐ（ｉ）はモデル行列Ｈｂｍにおけるエッジｉの巡回シフトサイズであり、エッジ０，１，２，．．．，２ｃ−１は（この順序で）Ｈｂにおいてサイクルを形成する。
【００２６】
１つのｚｆ値に対して方程式（４）を満たすことを回避する固定組のシフトサイズ｛ｐ（ｉ，ｊ）｝が、別のｚｆ値に対する方程式（４）を満たす場合が実際にあるが、｛ｐ（ｉ，ｊ）｝をｚｆに比例してスケーリングする場合、方程式（４）の線形性により、全てのｚｆに対して方程式（４）を満たすことは回避されることが示される。
【００２７】
２つの拡張係数ｚ０，ｚ１に対し、１組のシフトサイズ｛ｐ（ｉ，ｊ）｝を用いて所与の基本行列Ｈｂを拡張することが想定される。ここで、α＝ｚ０／ｚ１＞１である。シフトサイズの組｛ｐ（ｉ，ｊ）｝≡｛ｐ（０，ｉ，ｊ）｝によって、拡張係数ｚ０に対する長さ２ｃのサイクルが回避されると仮定すると、
【００２８】
【数５】
2008510379.tif 000007
ここで、ｐ（ｉ）はモデル行列Ｈｂｍ（０）におけるエッジｉの巡回シフトサイズであり、エッジ０，１，２，．．．，２ｃ−１は（この順序で）Ｈｂにおいてサイクルを形成する。スケーリングされたシフトサイズ｛ｐ（ｉ，ｊ）／α｝の組が拡張係数ｚ１に対し用いられる場合、ｚ１から拡張されたＨ行列によって長さ２ｃのサイクルも回避されることが、方程式（６）によって示される。２ｃは任意のサイクル長さであり得るので、スケーリングされたシフトサイズ｛ｐ（ｉ，ｊ）／α｝を用いることにより、ｚ０に対する｛ｐ（ｉ，ｊ）｝の組によって回避される、ｚ１に対する全てのサイクルタイプが回避される。
【００２９】
上述の説明では、スケーリングの後のシフトサイズが整数である必要があるという制限を無視した。整数を得るために、全てのｐ（ｉ，ｊ）／αに対し、例えば、床関数└ｘ┘（ｘ以下の最大の整数）、天井関数┌ｘ┐（ｘ以上の最小の整数）又は丸め関数［ｘ］（ｘとの差が最小の整数）、が実行される必要がある。一般に、ｚ０に対するシフトサイズｐ（ｉ，ｊ）≡ｐ（０，ｉ，ｊ）が与えられると、ｚ１に対するシフトサイズはｐ（ｉ，ｊ）及びαの関数Ｆ（．）として導かれ得る。
【００３０】
【数６】
2008510379.tif 000008
例えば、式（６）のトップに対し丸め関数が用いられ、ｚ０に対して設計されたシフトサイズがｐ（ｉ，ｊ）である場合、ｚ１に適用されるシフトサイズの組は次式となる。
【００３１】
【数７】
2008510379.tif 000009
通常では全ての正のｐ（ｉ，ｊ）がスケーリングされるが、式（８）のようなスケーリングは｛ｐ（ｉ，ｊ）｝のサブセットに対してのみ適用される場合がある。例えば、存在する場合にはＨｂの重み−１列のエッジなど、任意のサイクルに含まれるものがスケーリングされる必要がない。負でない全てのｐ（ｉ，ｊ）に対してスケーリングが適用される場合には、関数Ｆ（．）の定義に応じて、Ｈｂｍ（０），Ｈｂｍ（１）の基本行列が同じであってもよく、同じでなくてもよい。
【００３２】
システムに２より多くの拡張係数が必要である場合、ｐ（ｆ，ｉ，ｊ）の発見に対して上述の解析が容易に適用される。この場合、最大の符号長さに対する１組のシフトサイズｐ（０，ｉ，ｊ）を有する母モデル行列（基本モデル行列とも呼ぶ）Ｈｂｍ（０）が定義され、この行列から、第ｆ番目の符号ファミリのメンバに対するシフトサイズｐ（ｆ，ｉ，ｊ）を有するモデル行列Ｈｂｍ（ｆ）が導かれる（ｆ＝１，．．．，ｆｍａｘ）。ｚ０＝ｍａｘ（ｚｆ）、かつ、ｐ（０，ｉ，ｊ）＝ｐ（ｉ，ｊ）と仮定すると、ｚｆの全範囲に対して同じサイクルの基本行列が回避されるように、ｐ（ｉ，ｊ）からｐ（ｆ，ｉ，ｊ）を導く際、式（８）のような拡張においてαｆ＝ｚ０／ｚｆが用いられる。詳細には、全てのｐ（ｉ，ｊ）が発見されると仮定すると、一般に、次式を用いてｐ（ｉ，ｊ）からｐ（ｆ，ｉ，ｊ）が導かれる。
【００３３】
【数８】
2008510379.tif 000010
さらに、一例として、ｚ０＝ｍａｘ（ｚｆ）と仮定し、丸め関数を用いると、式（８）に対応して関数Ｆ（．）は次のように定義され得る。
【００３４】
【数９】
2008510379.tif 000011
同様に、丸め関数［ｘ］の代わりに床関数└ｘ┘又は天井関数┌ｘ┐を用いることが可能である。
【００３５】
なお、上述の設計手順は任意のタイプの基本行列Ｈｂに対し適用される。例えば、次のように２つの部分からなるＨｂに対し適用され得る。
【００３６】
【数１０】
2008510379.tif 000012
さらに、行列式部分Ｈｂ２は次のように２つの区分へ分割され得る。ここで、ベクトルｈｂは奇数の重みｗｈ＞２を有し、Ｈ’ｂ２は行列式の階段構造を有する。
【００３７】
【数１１】
2008510379.tif 000013
換言すると、Ｈ’ｂ２の第ｉ行、第ｊ列の行列要素は、次式と等しい。
【００３８】
【数１２】
2008510379.tif 000014
［符号のファミリに対するエンコーダ実装］
上述の設計によるファミリのメンバは全て母モデル行列Ｈｂｍ≡Ｈｂｍ（０）から導かれ、したがって全て同じ構造を有するため、ファミリの各メンバに対するエンコード処理は同様である。モデル行列の一部分又は全体が記憶され、グループ化された情報シーケンスの巡回シフトを実行するためのバレルシフタに対する命令として解釈され得る。
【００３９】
ファミリのメンバは全て母モデル行列Ｈｂｍ≡Ｈｂｍ（０）から導かれるため、ファミリのエンコーダの実装に必要なのは、母行列が記憶されることのみである。丸め関数［ｘ］が用いられると仮定すると、ファミリの第ｆ番目のメンバでは、全てのｐ（ｉ，ｊ）＞０に対し、母モデル行列の巡回シフトｐ（ｉ，ｊ）が巡回シフト［ｐ（ｉ，ｊ）／（ｚ０／ｚｆ）］に置き換えられる。ここで、ｚｆは、エンコードされるファミリの第ｆ番目のメンバの拡張係数を示す。この直接的な実装は、ファミリの各メンバに対するαｆ−１＝（ｚ０／ｚｆ）−１（又は、αｆ＝（ｚ０／ｚｆ））の値をリードオンリメモリに記憶し、実行時に乗算器を用いて［ｐ（ｉ，ｊ）／（ｚ０／ｚｆ）］の値（ｐ（ｉ，ｊ）＞０）を計算することである。これに代えて、ファミリの各メンバに対するシフトサイズの組｛ｐ（ｆ，ｉ，ｊ）｝（ｆ＝０，１，．．．，ｆｍａｘ）は予め式（８）（又は、一般的には式（７））を用いて計算され、リードオンリメモリに記憶されてもよい。
【００４０】
バレルシフタはファミリのメンバに相当する全ての語サイズｚｆに巡回シフトを提供するように修正され得る。バレルシフタを修正することによってバレルシフタの論理は複雑となり、より低速のクロック速度が必要となるが、余分な論理資源を必要とする一代替案では、各語サイズｚｆに対して異なるバレルシフタがインスタンス化される。
【００４１】
図２は、エンコーダ２００のブロック図である。示すように、エンコーダ２００は、拡張係数ｚｆを決定するために、マイクロプロセッサ２０１、参照テーブル２０３及び論理回路２０５を備える。互いの外部に存在するように示したが、論理回路２０５の機能がマイクロプロセッサ２０１内に実装されてもよいことが、当業者には認識される。マイクロプロセッサ２０１は、好適には、デジタル信号プロセッサ（ＤＳＰ）を含む。デジタル信号プロセッサには、ＭＳＣ８３００及びＤＳＰ５６３００のＤＳＰなどがあるが、それらに限定されない。これに加えて、参照テーブル２０３は行列を記憶するための記憶手段として作用し、リードオンリメモリを含む。しかしながら、他の形態のメモリ（例えば、ランダムアクセスメモリ、磁気記憶メモリなど）が同様に利用されてよいことが、当業者には認識される。第２の実施形態では、マイクロプロセッサ２０１、参照テーブル２０３及び論理回路２０５の機能は、特定用途向け集積回路（ＡＳＩＣ）又はフィールドプログラマブルゲートアレイ（ＦＰＧＡ）へ組み込まれ得る。詳細には、参照テーブル２０３は、回路における信号経路の存在又は非存在に対応するメモリの形態で実装され得る。
【００４２】
上述のように、一般に、エンコードされたデータはシステマティックビットに加えて複数のパリティ検査ビットの形態を取り、パリティ検査ビット及びシステマティックビットが共に符号語ｘを形成する。本発明の第１の実施形態では、基本モデル行列Ｈｂｍは参照テーブル２０３に記憶され、パリティ検査ビットを発見するためにマイクロプロセッサ２０１によってアクセスされる。詳細には、マイクロプロセッサ２０１は、情報ブロックｓ＝（ｓ０，．．．，ｓｋｆ−１）、拡張係数ｚｆ及び基本モデル行列Ｈｂｍに基づき、パリティ検査ビットｐ＝（ｐ０，．．．，ｐｍｆ−１）に対する適切な値を決定する。拡張係数ｚｆは、ｚｆ＝ｋｆ／ｋｂ＝ｎｆ／ｎｂを用いて論理２０５によって決定され、長さｚｆのベクトルや発見したαｆ＝ｚ０／ｚｆへとビットをグループ化するために用いられる。パリティ検査ビットが発見された後、パリティ検査ビット及びシステマティックビットは送信機へ渡され、受信機へ送信される。
【００４３】
図３は、本発明の一実施形態によるデコーダ３００のブロック図である。示すように、デコーダ３００は、拡張係数ｚｆを決定するために、マイクロプロセッサ３０１、参照テーブル３０３及び論理回路３０５を備える。本発明の第１の実施形態では、マイクロプロセッサ３０１は、デジタル信号プロセッサ（ＤＳＰ）を含む。デジタル信号プロセッサには、ＭＳＣ８３００及びＤＳＰ５６３００のＤＳＰなどがあるが、それらに限定されない。これに加えて、参照テーブル３０３は基本モデル行列Ｈｂｍを記憶するための記憶手段として作用し、リードオンリメモリを含む。しかしながら、他の形態のメモリ（例えば、ランダムアクセスメモリ、磁気記憶メモリなど）が同様に利用されてよいことが、当業者には認識される。第２の実施形態では、マイクロプロセッサ３０１及び参照テーブル３０３の機能は、特定用途向け集積回路（ＡＳＩＣ）又はフィールドプログラマブルゲートアレイ（ＦＰＧＡ）へ組み込まれ得る。詳細には、参照テーブル３０３は、回路における信号経路の存在又は非存在に対応するメモリの形態で実装され得る。
【００４４】
受信信号ベクトル（受信機を介して受信される）ｙ＝（ｙ０，．．．，ｙｎｆ−１）は、ノイズを有するチャネルを通じて送信される符号語ｘに相当する。ここで、上述のように、エンコードされたデータｘは、符号ファミリの第ｆ番目の符号語ベクトルである。本発明の第１の実施形態では、基本モデル行列Ｈｂｍは参照テーブル３０３に記憶され、ｙをデコードして情報ブロックｓ＝（ｓ０，．．．，ｓｋｆ−１）を推定するために、マイクロプロセッサ３０１によってアクセスされる。詳細には、マイクロプロセッサ３０１は、受信信号ベクトルｙ＝（ｙ０，．．．，ｙｎｆ−１）及び基本モデル行列Ｈｂｍに基づき、情報ブロックｓ＝（ｓ０，．．．，ｓｋｆ−１）を推定する。拡張係数ｚｆは、ｚｆ＝ｋｆ／ｋｂ＝ｎｆ／ｎｂを用いて論理３０５によって決定され、長さｚｆのベクトルや発見したαｆ＝ｚ０／ｚｆへと受信信号及びビットをグループ化するために用いられる。
【００４５】
図４は、エンコーダ２００の、詳細には、マイクロプロセッサ２０１の動作を示すフローチャートである。論理フローは工程４０１にて開始し、情報ブロック（ｓ０，．．．，ｓｋｆ−１）がマイクロプロセッサ２０１によって受信される。工程４０３にて、情報ブロック及びＨｂｍ（ｆ）に基づきパリティ検査ビットの値が決定される。ここで、Ｈｂｍ（ｆ）によって｛ｐ（ｆ，ｉ，ｊ）｝がユニークに定義される。詳細には、基本モデル行列Ｈｂｍのシフトサイズの組｛ｐ（ｉ，ｊ）｝がメモリから読み出される。マイクロプロセッサは｛ｐ（ｉ，ｊ）｝及びαｆを利用して、｛ｐ（ｆ，ｉ，ｊ）｝を決定する。パリティ検査ビット（ｐ０，．．．，ｐｍｆ−１）は、方程式（１）を解くことによって決定される。工程４０５にて、情報ブロック及びパリティ検査ビットがチャネルを通じて送信される。
【００４６】
図５は、デコーダ３００の、詳細には、マイクロプロセッサ３０１の動作を示すフローチャートである。論理フローは工程５０１にて開始し、受信信号ベクトルｙ＝（ｙ０，．．．，ｙｎｆ−１）が受信される。工程５０３にて、Ｈｂｍ（ｆ）に基づき情報ブロックｓ＝（ｓ０，．．．，ｓｋｆ−１）の推定値が決定される。ここで、Ｈｂｍ（ｆ）は｛ｐ（ｆ，ｉ，ｊ）｝によってユニークに定義される。詳細には、基本モデル行列Ｈｂｍのシフトサイズの組｛ｐ（ｉ，ｊ）｝がメモリから読み出される。マイクロプロセッサは｛ｐ（ｉ，ｊ）｝及びαｆを利用して、｛ｐ（ｆ，ｉ，ｊ）｝を決定する。説明したように、マイクロプロセッサは、シフトサイズ｛ｐ（ｆ，ｉ，ｊ）｝（又は同等に、Ｈｂｍ（ｆ））によって受信信号ベクトルを処理し、情報ブロックの推定値を得る。好適な一実施形態では、マイクロプロセッサは、符号の二分グラフを用いるメッセージ通過アルゴリズムによって、処理を実行する。
【００４７】
［実施例］
一例として、５７６〜２３０４ビットの範囲にある１９の符号サイズのｎｆに対する符号設計を記載する。各基本モデル行列は、シフトサイズｚ０＝９６に対して設計されている。１組のシフトサイズ｛ｐ（ｉ，ｊ）｝は基本モデル行列に対して定義されており、同じ符号化率の他の符号サイズに対して用いられる。他の符号サイズでは、シフトサイズは基本モデル行列から次のように導かれる。
【００４８】
拡張係数ｚｆに相当する符号サイズに対しては、そのシフトサイズ｛ｐ（ｆ，ｉ，ｊ）｝は、次式のように、ｐ（ｉ，ｊ）を比例的にスケーリングすることによって｛ｐ（ｉ，ｊ）｝から導かれる。
【００４９】
【数１３】
2008510379.tif 000015
なお、αｆ＝ｚ０／ｚｆであり、└ｘ┘は、−∞の方向の最も近い整数を与える床関数を表す。
【００５０】
１／２，２／３，３／４の３つの符号化率について、基本モデル行列を以下に示す。ここで、ｆは所与の符号化率における符号長さの指標であり、ｆ＝０，１，２，．．．，１８である。
【００５１】
［符号化率１／２］：
基本モデル行列のサイズはｎｂ＝２４，ｍｂ＝１２であり、拡張係数ｚ０＝９６（即ち、ｎ０＝２４×９６＝２３０４）である。他の符号サイズｎｆを得るため、拡張係数ｚｆはｎｆ／２４と等しい。
【００５２】
【表１】
2008510379.tif 000016
［符号化率２／３］：
基本モデル行列のサイズはｎｂ＝２４，ｍｂ＝８であり、拡張係数ｚ０＝９６（即ち、ｎ０＝２４×９６＝２３０４）である。他の符号サイズｎｆを得るため、拡張係数ｚｆはｎｆ／２４と等しい。
【００５３】
【表２】
2008510379.tif 000017
［符号化率３／４］：
基本モデル行列のサイズはｎｂ＝２４，ｍｂ＝６であり、拡張係数ｚ０＝９６（即ち、ｎ０＝２４×９６＝２３０４）である。他の符号サイズｎｆを得るため、拡張係数ｚｆはｎｆ／２４と等しい。
【００５４】
【表３】
2008510379.tif 000018
本発明は特定の実施形態に関連して詳細に示され、説明されているが、本発明の精神及び範囲から逸脱することなく、形態及び詳細における種々の変更が行なわれ得ることが、当業者には理解される。例えば、符号サイズの範囲が非常に大きいとき、例えば、αがｚ／２に近付くときには、適正なシフトサイズの組｛ｐ（ｉ，ｊ）｝を発見することは非常に困難となる。したがって、符号範囲が大き過ぎる場合、即ち、αが大きい場合、符号ファミリにおいて一定の範囲のｚｆを各々覆う、｛ｐ（ｉ，ｊ）｝の複数の組が用いられてよい。別の例として、説明では、第０番目の符号ファミリに対し、母モデル行列Ｈｂｍ（０）、ｚ０＝ｍａｘ（ｚｆ）及びｐ（０，ｉ，ｊ）＝ｐ（ｉ，ｊ）が用いられると仮定したが、符号ファミリに存在しないが対象の符号ファミリに対するシフトサイズｐ（ｆ，ｉ，ｊ）を導くために用いられる符号サイズに対してＨｂｍ（０），ｚ０，ｐ（ｉ，ｊ）が定義されてもよいことが、当業者には理解される。別の例として、説明では、ｚ０＝ｍａｘ（ｚｆ）であると仮定したが、シフトサイズ導出においてｍａｘ（ｚｆ）と等しくないｚ０の値が用いられてよいことが、当業者には理解される。かかる変更は添付の特許請求の範囲内にあることが意図される。
【図面の簡単な説明】
【００５５】
【図１】（１２，６）のＨ行列の二分グラフ。
【図２】エンコーダのブロック図。
【図３】デコーダのブロック図。
【図４】図２のエンコーダの動作を示すフローチャート。
【図５】図３のデコーダの動作を示すフローチャート。
【図１】
2008510379.tif 000026
【図２】
2008510379.tif 000027
【図３】
2008510379.tif 000028
【図４】
2008510379.tif 000029
【図５】
2008510379.tif 000030
【国際調査報告】
2008510379.tif 000031