(57)【特許請求の範囲】
【請求項１】
データ要素のブロックを順序変更する方法であり、
前記ブロックを複数のコ・セットに分割することと、
各コ・セットを順序変更することと、
前記順序変更されたコ・セットの要素を予め定められた順序で結合することによって順序変更されたブロックを作ること、を含み、
前記各コ・セットを順序変更するステップが、
Ｎ１ｘＮ２はＮ／ｎに等しく、Ｎは前記ブロックにおけるエレメント数であり、ｎはコ・セット数であるものとして、各コ・セットを行毎にＮ１行とＮ２列を持つアレイに読み込むことと、
素数Ｐ１＜Ｎ１、およびＰ２＜Ｎ２を選ぶことと、
Ｐ１およびＰ２の根としてα１およびα２を決定することと、
β１およびβ２の値を選択することと、
α１およびβ１の関数として前記アレイの行索引を順序変更することと、
α２およびβ２の関数として前記アレイの列索引を順序変更することと、
前記アレイをβ１行循環移動することと、
前記アレイをβ２列循環移動することと、
前記アレイから各コ・セットを列毎に読み出すこと、
を含む方法。
【請求項２】
Ｎは１よりも大きい正の整数であり、１よりも大きい正の整数ｎで割り切れる数であるとして、前記ブロックがＮ個のデータ要素を含み、前記ブロックをコ・セットに分割するステップがｎ個のコ・セットの各々に、前記ブロックにおける相対位置が共通の（Ｎ  ｍｏｄｕｌｏ（ｎ））の値を持つ要素を割り当てることを含む、請求項１に記載の方法。
【請求項３】
ｎの値が２であり、それによって第１のコ・セットは前記ブロックの全ての奇数番号の要素を含み、第２のコ・セットは前記ブロックの全ての偶数番号の要素を含む、請求項２に記載の方法。
【請求項４】
前記各コ・セットを順序変更するステップが各コ・セットにしたがってｍ−シーケンスを生成することを含む請求項１に記載の方法。
【請求項５】
システム要素のストリームからターボ符号を作成する方法であり、
第１の符号化器において前記システム要素を符号化して第１のターボ要素のストリームを作成することと、
システム要素の前記ストリームを複数のコ・セットに分割することと、
各コ・セットを順序変更することと、
前記順序変更されたコ・セットを予め定められた順序で結合することによって順序変更されたシステム要素のストリームを作ることと、
第２の符号化器において前記順序変更されたシステム要素のストリームを符号化して第２のターボ要素のストリームを作成することと、
前記第１と第２のターボ要素のストリームを予め定められた順序で結合すること、を含み、
前記各コ・セットを順序変更するステップが、
Ｎ１ｘＮ２はＮ／ｎに等しく、Ｎは前記ブロックにおけるエレメント数であり、ｎはコ・セット数であるものとして、各コ・セットを行毎にＮ１行とＮ２列を持つアレイに読み込むことと、
素数Ｐ１＜Ｎ１、およびＰ２＜Ｎ２を選ぶことと、
Ｐ１およびＰ２の根としてα１およびα２を決定することと、
β１およびβ２の値を選択することと、
α１およびβ１の関数として前記アレイの行索引を順序変更することと、
α２およびβ２の関数として前記アレイの列索引を順序変更することと、
前記アレイをβ１行循環移動することと、
前記アレイをβ２列循環移動することと、
前記アレイから各コ・セットを列毎に読み出すことと、
を含む方法。
【請求項６】
Ｎは前記システム要素のストリーム内の要素の数であるとして、前記システム要素のストリームをコ・セットに分割する前記ステップが、ｎ個のコ・セットの各々に、システム要素の前記ストリームにおける相対位置が共通の（Ｎ  ｍｏｄｕｌｏ（ｎ））の値を持つ要素を割り当てることを含む、請求項５に記載の方法。
【請求項７】
Ｎ個のターボ要素の前記第１と第２のストリームの前記結合が、システム要素のターボ要素に対する予め定められた比率を維持するために、ターボ要素の前記第１と第２のストリームの間引きを行うことを含む、請求項５に記載の方法。
【請求項８】
前記予め定められた比率が１／２であり、かつｎの値が２であり、それによって前記ターボ符号が各システム要素に対応する要素を少なくとも一つ含む、請求項７に記載の方法。
【請求項９】
データ要素のブロックを順序変更する装置であり、
前記ブロックを複数のコ・セットに分割する手段と、
各コ・セットを順序変更する手段と、
前記順序変更されたコ・セットの要素を予め定められた順序で結合することによって順序変更されたブロックを作る手段と、
を含み、
前記各コ・セットを順序変更する前記手段が、
Ｎ１ｘＮ２はＮ／ｎに等しく、Ｎは前記ブロックにおけるエレメント数であり、ｎはコ・セット数であるものとして、各コ・セットを行毎にＮ１行とＮ２列を持つアレイに読み込む手段と、
素数Ｐ１＜Ｎ１、およびＰ２＜Ｎ２を選ぶ手段と、
Ｐ１およびＰ２の根としてα１およびα２を決定する手段と、
β１およびβ２の値を選択する手段と、
α１およびβ１の関数として前記アレイの行索引を順序変更する手段と、
α２およびβ２の関数として前記アレイの列索引を順序変更する手段と、
前記アレイをβ１行循環移動する手段と、
前記アレイをβ２列循環移動する手段と、
前記アレイから各コ・セットを列毎に読み出す手段と、
を含む装置。
【請求項１０】
Ｎは１よりも大きい正の整数であり、１よりも大きい正の整数ｎで割り切れる数であるとして、前記ブロックがＮ個のデータ要素を含み、前記ブロックをコ・セットに分割する手段によってｎ個のコ・セットの各々に、前記ブロックにおける相対位置が共通の（Ｎ  ｍｏｄｕｌｏ（ｎ））の値を持つ要素が割り当てられる、請求項９に記載の装置。
【請求項１１】
ｎの値が２であり、それによって第１のコ・セットは前記ブロックの全ての奇数番号の要素を含み、第２のコ・セットは前記ブロックの全ての偶数番号の要素を含む、請求項１０に記載の装置。
【請求項１２】
各コ・セットを順序変更する手段が各コ・セットにしたがってｍ−シーケンスを生成する手段を含む請求項９に記載の装置。
【請求項１３】
システム要素のストリームからターボ符号を作成する装置であり、
前記システム要素を符号化して第１のターボ要素のストリームを作成する手段と、
システム要素の前記ストリームを複数のコ・セットに分割する手段と、
各コ・セットを順序変更する手段と、
前記順序変更されたコ・セットを予め定められた順序で結合することによって順序変更されたシステム要素のストリームを作る手段と、
前記順序変更されたシステム要素を符号化して第２のターボ要素のストリームを作成する手段と、
前記第１と第２のターボ要素のストリームを予め定められた順序で結合する手段と、を含み、
前記各コ・セットを順序変更する前記手段が、
Ｎ１ｘＮ２はＮ／ｎに等しく、Ｎは前記ブロックにおけるエレメント数であり、ｎはコ・セット数であるものとして、各コ・セットを行毎にＮ１行とＮ２列を持つアレイに読み込む手段と、
素数Ｐ１＜Ｎ１、およびＰ２＜Ｎ２を選ぶ手段と、
Ｐ１およびＰ２の根としてα１およびα２を決定する手段と、
β１およびβ２の値を選択する手段と、
α１およびβ１の関数として前記アレイの行索引を順序変更する手段と、
α２およびβ２の関数として前記アレイの列索引を順序変更する手段と、
前記アレイをβ１行循環移動する手段と、
前記アレイをβ２列循環移動する手段と、
前記アレイから各コ・セットを列毎に読み出す手段と、
を含む装置。
【請求項１４】
Ｎは前記システム要素のストリーム内の要素の数であるとして、前記システム要素のストリームをコ・セットに分割する前記手段が、ｎ個のコ・セットの各々に、システム要素の前記ストリームにおける相対位置が共通の（Ｎ  ｍｏｄｕｌｏ（ｎ））の値を持つ要素を割り当てることを含む、請求項１３に記載の装置。
【請求項１５】
Ｎ個のターボ要素の前記第１と第２のストリームを結合する前記手段が、システム要素のターボ要素に対する予め定められた比率を維持するために、ターボ要素の前記第１と第２のストリームの間引きを行う、請求項１３に記載の装置。
【請求項１６】
前記予め定められた比率が１／２でありかつｎの値が２であり、それによって前記ターボ符号が各システム要素に対応する要素を少なくとも一つ含む、請求項１５に記載の装置。
【請求項１７】
データ要素のブロックを順序変更するシステムであり、
前記ブロックを複数のコ・セットに分割するための分割ロジック（logic）と、
それぞれのコ・セットを順序変更するための順序変更ロジックと、
前記順序変更されたコ・セットの要素を予め定められた順序で結合することによって順序変更されたブロックを作るための結合ロジックと、を含み、
前記順序変更ロジックが、
Ｎ１ｘＮ２はＮ／ｎに等しく、Ｎは前記ブロックにおけるエレメント数であり、ｎはコ・セット数であるものとして、各コ・セットを行毎にＮ１行とＮ２列を持つアレイに格納する読み込みロジックと、
素数Ｐ１＜Ｎ１、およびＰ２＜Ｎ２を選び、
Ｐ１およびＰ２の根としてα１およびα２の決定を行い、
β１およびβ２の値の選択を行う、
よう設計された算術ロジックと、
α１およびβ１の関数として前記アレイの行索引の順序変更を行い、
α２およびβ２の関数として前記アレイの列索引の順序変更を行い、
前記アレイのβ１行循環移動を行い、
前記アレイのβ２列循環移動を行い、
前記アレイから各コ・セットを列毎に読み出す、
よう設計されたデータ操作ロジックと、
を含むシステム。
【請求項１８】
Ｎは１よりも大きい正の整数であり、１よりも大きい正の整数ｎで割り切れる数であるとして、前記ブロックがＮ個のデータ要素を含み、前記分割ロジックがｎ個のコ・セットの各々に、前記ブロックにおける相対位置が共通の（Ｎ  ｍｏｄｕｌｏ（ｎ））の値を持つ要素を割り当てる、請求項１７に記載のシステム。
【請求項１９】
ｎの値が２であり、それによって第１のコ・セットは前記ブロックの全ての奇数番号の要素を含み、第２のコ・セットは前記ブロックの全ての偶数番号の要素を含む、請求項１８に記載のシステム。
【請求項２０】
前記順序変更ロジックが、各コ・セットにしたがってｍ−シーケンスを生成することを含む請求項１７に記載のシステム。
【請求項２１】
システム要素のストリームからターボ符号を作成するためのシステムであり、
前記システム要素を符号化して第１のターボ要素のストリームを作成するための第１の符号化器と、
システム要素の前記ストリームを複数のコ・セットに分割するように設計された分割ロジックと、
各コ・セットを順序変更するように設計された順序変更ロジックと、
前記順序変更されたコ・セットを予め定められた順序で結合することによって順序変更されたシステム要素のストリームを作る、第１の結合ロジックと、
前記順序変更されたシステム要素を符号化して第２のターボ要素のストリームを作成する第２の符号化器と、
前記第１と第２のターボ要素のストリームを予め定められた順序で結合する第２の結合ロジックとを含み、
前記順序変更ロジックが、
Ｎ１ｘＮ２はＮ／ｎに等しく、Ｎは前記ブロックにおけるエレメント数であり、ｎはコ・セット数であるものとして、各コ・セットを行毎にＮ１行とＮ２列を持つアレイに格納する読み込みロジックと、
素数Ｐ１＜Ｎ１、およびＰ２＜Ｎ２を選び、
Ｐ１およびＰ２の根としてα１およびα２の決定を行い、
β１およびβ２の値の選択を行う
よう設計された算術ロジックと、
α１およびβ１の関数として前記アレイの行索引の順序変更を行い、
α２およびβ２の関数として前記アレイの列索引の順序変更を行い、
前記アレイのβ１行循環移動を行い、
前記アレイのβ２列循環移動を行い、
前記アレイから各コ・セットを列毎に読み出す、
よう設計されたデータ操作ロジックと、
を含むシステム。
【請求項２２】
Ｎは前記システム要素のストリーム内の要素の数であるとして、前記分割ロジックが、ｎ個のコ・セットの各々に、システム要素の前記ストリームにおける相対位置が共通の（Ｎ  ｍｏｄｕｌｏ（ｎ））の値を持つ要素を割り当てる、請求項２１に記載のシステム。
【請求項２３】
前記第２の結合ロジックが、システム要素のターボ要素に対する予め定められた比率を維持するために、ターボ要素の前記第１と第２のストリームの間引きを行う、請求項２１に記載のシステム。
【請求項２４】
前記予め定められた比率が１／２でありかつｎの値が２であり、それによって前記ターボ符号が各システム要素に対応する要素を少なくとも一つ含む、請求項２３に記載のシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は通信システムに関し、とくに、コード変調を行うインタリーバに関する。
【０００２】
【従来の技術】
通信路の符号化、すなわち符号化変調によって、モデムおよび無線通信システムのような電子的通信システムのビット誤り率（BER）が改善されることが知られている。ターボ符号化変調は、加法的ガウシアンホワイトノイズ（additive Gaussian white noise, AWGN）、あるいはフェージング（fading）で特徴づけられる「確率的誤差」通信路（random-error  channels）に対して、実用的であり、電力効率がよく、かつ帯域幅効率のよい方法であることが証明されている。例えば、これらの確率的誤差通信路は、符号分割多重アクセス（Code Division Multiple Access, CDMA）環境に見ることができる。
【０００３】
ターボ符号における重要な技術革新は、第２の符号化器への入力前に元のデータフレームの順序変更を行う、インタリーバである。従来の並行連結ターボ符号化器（parallel concatenated Turbo Encoder）が図１に示されている。ターボ符号化器には、２つの構成要素の符号化器１０２と１０４、および１台のインタリーバ１０６が含まれる。スイッチ１０８は、所望の比率（ratio）（例えば、Ｒ＝１／２）を保つために、符号化器１０２および１０４の各々からのビットを一つおきに間引く（puncture）ことができる。構成要素の符号化器の構造と動作、および比率の選択についてはよく知られていることであるので、本明細書においてはさらに詳しくは解説されない。しかしながら、とくに小ブロック・サイズのターボ符号に対して、インタリーバの構造は未解決の問題である。
【０００４】
現在は、もしＣＤＭＡ通信路のような加法的ガウシアン・ホワイトノイズ通信路において、データフレームサイズが無限大になるならば、従来の「ランダム・インタリーバ（random interleaver）」が最善であると考えられている。しかしながら、有限サイズのデータフレーム（すなわちターボ符号）用の最善のインタリーバはまだ決定されていない。
【０００５】
【発明が解決しようとする課題】
したがって、有限サイズのデータフレーム（すなわちターボ符号）用のインタリーバを設計する必要性が存在する。それ故、有限サイズのデータフレーム用のインタリーバを提供することは、本発明の一つの利点である。また、予め定められたサイズのフレーム用に最適化されたインタリーバを提供することは、本発明のもう一つの利点である。
【０００６】
【課題を解決するための手段】
本発明の一形態によると、Ｎ個のデータ要素を含んだブロックを順序変更する方法が提供される。ここで、Ｎは１よりも大きい正の整数ｎで割り切れる１よりも大きい正の整数である。この方法は、ブロックをそれぞれＮ／ｎのサイズをもつｎ個のコ・セット（co-sets）に分割すること、各コ・セットを順序変更すること、および順序変更されたコ・セットの要素を予め定められた順序で結合することによって順序変更されたブロックを作り出すこと、を含む。
【０００７】
本発明の一形態によると、前記ブロックにおける相対的位置が共通の（Ｎ  ｍｏｄｕｌｏ（ｎ））の値を持つ要素をｎ個のコ・セットの各々に割り当てることによって、前記ブロックをｎ個のコ・セットに分割するためのシステムと方法が提供される。
【０００８】
本発明は、一形態において、各々のコ・セットを代数的インタリーバ（algebraic interleaver）において順序変更し、コ・セットのサイズに適合されたブロックを作ること、およびコ・セット分割を行うこと、およびインタリーブを数回行うことを提供する。本発明は、一形態において、コ・セットに従ってｍ−シーケンスを生成することによって各コ・セットを順序変更することを提供する。
【０００９】
本発明のまたもう一つの形態によると、Ｎ個のシステム・ビット（system bits）から成るストリームからターボ符号を生成するシステムおよび方法が提供される。ここで、Ｎは１よりも大きい正の整数ｎで割り切れる１よりも大きい正の整数である。この方法は、第１の符号化器においてＮ個のシステム・ビットを符号化しＮ個のターボ・ビット（Turbo bits）から成る第１のストリームを生成すること、Ｎ個のシステム・ビットから成るストリームをそれぞれＮ／ｎのサイズを持ったｎ個のコ・セットに分割すること、各コ・セットを順序変更すること、順序変更された前記コ・セットを予め定められた順序で結合することにより、Ｎ個のシステム・ビットから成る、順序変更されたストリームを作ること、第２の符号化器においてＮ個の順序変更されたシステム・ビットを符号化し、Ｎ個のターボ・ビットから成る第２のストリームを生成すること、および、Ｎ個のターボ・ビットから成る第１のストリームと第２のストリームを予め定められた順序で結合すること、を含む。
【００１０】
本発明は、一形態において、前記ブロックにおける相対的位置が共通の（Ｎ  ｍｏｄｕｌｏ（ｎ））の値を持つ要素をｎ個のコ・セットの各々に割り当てることによって、Ｎ個のシステム・ビットから成るストリームをｎ個のコ・セットに分割すること、およびコ・セット分割とインタリービングを数回適用することを提供する。
【００１１】
本発明は、一形態において、システム・ビットのストリームからターボ・ビットのストリームを二つ生成すること、および、システム・ビットのターボ・ビットに対する予め定められた比率を保つために、Ｎ個のターボ・ビットからなる二つのストリームの間引きを行う（puncture）ことを提供する。
【００１２】
次に、本発明の代表的な実施形態を説明する。しかし、当業者には、様々な部分修正、追加、削除が、本請求項の意図あるいは範囲から逸脱することなくなされ得ることは、明らかであろう。
【００１３】
【発明の実施の形態】
本発明は、従来のターボ符号のパフォーマンスを改善するインタリーバを開示する。本発明の一つの実施形態は、集合分割による写像の概念を利用することによって、より小さなサイズのインタリーバを基にした任意のサイズの代数的インタリーバを構築するためのアルゴリズムを採用する。この技術は、代数的インタリーバのパラメータ表示（parameterization）、および選択された基準に基づくインタリーバの最適化を可能にする。
【００１４】
上記の実施形態は、並列連結ターボ符号の間引きによって生じるパリティ・ビットの損失を補償する。コ・セット分割された代数的インタリーバを採用することによって、間引きされたターボ符号（とくにＲ＝１／２に対して）のパフォーマンスは改善される。本発明は、ソフトウェア、あるいはハードウェア（すなわち特定用途向けＩＣ（ＡＳＩＣ）、プログラム可能論理アレイ（ＰＬＡ）、あるいは適する他のすべての論理装置）の形で実現可能である。
【００１５】
本明細書では、インタリーバの一実施形態が、ターボ符号、およびｃｄｍａ２０００に関して解説されるが、当業者は、これらのインタリーバはまた、今日のＣＤＭＡのような他のシステムにおいても使用でき、かつ他の符号を用いても使用できることを理解するであろう。
【００１６】
コ・セット分割に基づく代数的インタリーバの構築
本インタリーバの仕組みは決定性代数構造に基づいている。それは、ブロックをより小さなコ・セット・サブ・ブロックに分割し、より小サイズの代数的インタリーバを用いてコ・セットをインタリーブすることよって、任意のサイズのブロックをインタリーブすることのできる代数的インタリーバを設計するために、コ・セット分割のアイデアを採用している。次に、インタリーブされたコ・セットからの要素は、元のブロックのインタリーブド・バージョンを作るために、あらかじめ定められた順序で結合される。
【００１７】
本実施形態においては、コ・セット分割は、ｎ個のコ・セットの各々に、法ｎの計算（a modulo-n calculation）の同じ剰余を共有するブロックの要素を割り当てることによって、達成される。
【００１８】
例えば、表１のように識別される１２個の要素を含むブロックは、表２を含む２個のコ・セット、あるいは、表３を含む３個のコ・セット、あるいは、表４を含む４個のコ・セットに分割することができる。（ブロックはまた、それぞれ２個の要素をもつ６個のコ・セットに分割することもできるが、２個の要素をもつコ・セットを順序変更してもおそらく実際上役に立たないであろう。）
【００１９】
【表１】
0004422906.tif 000002
【表２】
0004422906.tif 000003
【表３】
0004422906.tif 000004
【表４】
0004422906.tif 000005
【００２０】
これより、要素１から４８として識別される４８個のデータ要素をもつブロックのインタリービングの一例について詳しく考察される。ブロックは、一方は要素１から４８のうち法２の剰余（modulo-2 residue）が０であるもの（すなわち、２４個の「偶数番号の」要素２、４、６、．．．４８）を含み、もう一方は要素１から４８のうち法２の剰余が１であるもの（すなわち、２４個の「奇数番号の」要素１、３、５、．．．４７）を含むような、２個のコ・セットに分割される。この解説では、これらの２個のブロックは、偶数ブロックおよび奇数ブロックと呼ばれる。当業者は、コ・セットの数を２に選んだことは例示のためであり、限定的なものではないことを理解するであろう。２個のブロックはそれぞれ、行毎に、かつ列毎に順序変更される。
【００２１】
２４個の要素をもったブロックはそれぞれ、４行６列のアレイ―すなわち、Ｎ１を４と選び、したがってＮ２を６と選んだ、Ｎ１ｘＮ２のアレイ―として扱われる。当業者は、これらの数は例示のためのものであり、他の数が選ばれ得ることを理解するであろう。次に、素数Ｐ１およびＰ２が選ばれる。Ｐ１はＮ１よりも大きい素数である。Ｐ１はＮ１よりも大きい素数で最も小さいものであることが望ましい。しかし、もしそれよりも大きな素数が選ばれても本方法は機能を果たす。したがって、Ｐ１に対して５の値が選ばれる。なぜなら、５が４（Ｎ１の値）よりも大きくて最も小さい素数であるからである。同様に、Ｐ２に対して７の値が選ばれる。なぜなら、７が６（Ｎ２の値）よりも大きくて最も小さい素数であるからである。次に、α１、α２、β１およびβ２の値が選ばれる。α１およびα２の値はそれぞれ、従来の方法で得られるＰ１およびＰ２の初期根（initial roots）である。β１およびβ２は、表５の範囲より最善の結果の得られる値が選ばれる。本例では、α１＝２、α２＝３、β１＝１およびβ２＝３である。
【００２２】
【表５】
0004422906.tif 000006
【００２３】
インタリーブされるブロックは行ごとにＮ１行Ｎ２列のアレイに読み込まれる。したがって、偶数ブロックは、表６のように読み込まれる。
【００２４】
【表６】
0004422906.tif 000007
【００２５】
次に、行索引Irow(n)が次の表の規則に従って順序変更される。
【表７】
0004422906.tif 000008
【００２６】
したがって、本例の行１、２、３および４に対して、Irowの値は次の表のようになる。
【表８】
0004422906.tif 000009
【００２７】
すると、元の行１は行４に、元の行２は行３に、などとなり、次の表のアレイを生成する。
【表９】
0004422906.tif 000010
【００２８】
次に、列索引Icol(n)は次の表の規則に従って順序変更される。
【表１０】
0004422906.tif 000011
【００２９】
したがって、本例の列１、２、３、４、５および６に対して、Icolの値は次の表のようになる。
【表１１】
0004422906.tif 000012
【００３０】
すると、先の列１は列４に、先の列２は列５に、などとなり、次の表のアレイを生成する。
【表１２】
0004422906.tif 000013
【００３１】
次に、β１行（１行）だけ行の循環移動が行われ、次の表のアレイを得る。
【表１３】
0004422906.tif 000014
【００３２】
次に、β２列（３列）だけ列の循環移動が行われ、次の表のアレイを得る。
【表１４】
0004422906.tif 000015
【００３３】
インタリーブされた偶数ブロックを列毎に読み出すと、次のインタリーバ出力索引（output index）が生成される。
38, 14, 02, 26, 40, 16, 04, 28, 48, 24, 12, 36, 42, 18, 06, 30, 46, 22, 10, 34, 44, 20, 08, 32
【００３４】
類似の処理が、奇数ブロック（考察中の４８個の要素から成るブロックの２４個の奇数要素）をインタリーブするために行われる。インタリーブされたコ・セットは予め定められた順序に従って再結合される。扱うのが数学的に便利でないサイズのブロックは、順序変更を行うために便利なサイズに埋められる場合がある。埋めた個所は順序変更後に捨てられる。例えば、４５個の要素から成るブロックは、本例におけるように順序変更を受ける前に、余分の要素４６、４７および４８を加えられ、順序変更後は要素４６、４７および４８は捨てられる場合がある。
【００３５】
このように、特有のサイズ（ここでは２４）を持つ基本的な代数的インタリーバ組み立てブロックにパラメータが与えられる。パラメータはπ｛α１，α２，β１，β２｝のように表される場合がある。ここで、πはインタリーバ・ブロックを意味しており、根｛α１，α２｝、およびシフト｛β１，β２｝は、代数的インタリーバに指定されている異なる最適化規準に逆らって選択され、組み立てブロックサイズに対する最適値に変更されることができる。
【００３６】
このようなコ・セット・インタリーバを用いたターボ符号化器の一例が図２に示されている。この例においては、入力シーケンスは、一方は入力シーケンスの偶数番号のビットから成り、もう一方は奇数番号のビットから成る、２個のコ・セットに分けられる。要素２０４および２０６は、それらに送られてくる要素を一つおきに通す分別器（decimator）である。分別器２０４および２０６の一方のみへの経路上にある単位遅延器２０２と連動すると、これは、奇数のシステム・ビットのシーケンス（１、３、．．．）から成るコ・セットをインタリーバ組み立てブロック２１０に通し、偶数のシステム・ビットのシーケンスから成るコ・セットをインタリーバ組み立てブロック２０８に通す結果となる。当業者には、他のビット通過制御の方法を用いることもできることが明らかである。
【００３７】
スイッチ１０８および２１２の開始位置は図２において示される位置に初期化されている。次に、それらは図２のターボ符号化器を通るビットの流れに同期して切り替わる（toggle）。したがって、スイッチ２１２は符号化器１０４への入力のために、インタリーバ２１０から出力される第１の要素、インタリーバ２０８から出力される第１の要素、インタリーバ２１０から出力される第２の要素、などの要素から成る単一のブロックを再構成する。もしスイッチ１０８がなければ、図２の機器構成は比率Ｒ＝１／３をもつビット・ストリーム（１個のシステム・ビット入力毎に１個のシステム・ビットと２個のターボ・ビットの出力）を出力する。スイッチ１０８は、出力が比率Ｒ＝１／２を持つように、符号化器１０２および１０４の各々からのターボ・ビットを一つ置きに間引く。
【００３８】
代数的インタリーバ組み立てブロック（コ・セット）はＮ０＝Ｎ／２のサイズを持つように選ばれている。ここで、Ｎはインタリーブされるブロックのサイズである。Ｎ０の値にＮ／２を用いる選択は設計上の選択である。当業者には、他の組み立てブロックサイズも可能であることが明らかである。次に、各々のブロックに、Ｎ１ ｘＮ２＝Ｎ０なる行数Ｎ１、および列数Ｎ２が割り当てられる。第１の組み立てブロックのために選ばれるパラメータは｛α１，α２，０，０｝であり、第２の組み立てブロックのために選ばれるパラメータは｛α３，α４，β１，β２｝である。パラメータ表示された（parameterized）インタリーバは、ターボ符号パフォーマンスに関して適切な値でもって最適化することができる。テーブル１は、ｃｄｍａ２０００において指定されたターボ符号用に決定された最適化パラメータセットを示している。
【００３９】
【表１５】
0004422906.tif 000016
【００４０】
本発明の代替実施例においては、コ・セット分割が２回以上行われる。上記の例では、偶数コ・セットの列１，２，３，４，５および６は列４，５，１，３，２および６に順序変更されたが、それからさらにコ・セット分割を行うことが可能である。つまり、新しい第１、第３および第５の列を１個のコ・セットとして、そして新しい第２、第４および第６の列をもう１個のコ・セットとして捉え、それによって次の表に示す２個のコ・セットを生成する。
【００４１】
【表１６】
0004422906.tif 000017
【００４２】
次に、これらはそれぞれ上の例と同様に行と列の循環移動を受ける。本発明の他の実施例においては、行と列の移動数が各々異なる値を用いる場合がある。すなわち、βの値は行と独立（row-independent）であるか、あるいは列と独立（column-independent）であるか、あるいはその両方であってもよい。
【００４３】
ターボ符号ビットの損失のない間引きされたターボ符号
本発明のコ・セット数を２としてコ・セット分割を行うことから得られる付加的利点は、特定の比率Ｒを得るために（図２のスイッチ１０８により）間引きを行うことによって、個々のシステム・ビットに対応したターボ・ビットを両方とも削除してしまうことがないことである。図３は、図１の従来のターボ符号化器について、Ｓ１からＳ５で示される５個のシステム・ビットを示し、システム・ビットＳ２を例に取ると、それに対応するターボ符号ビットＴ１２およびＴ２２は、間引きによって両方とも失われることを示している（仮定されたインタリーブド・ビットの順序の場合）。それらのビット・ストリームの一方は他方に対してインタリーブされているので、このようなことが起きないとは保証できない。目的地において復号化するときに、システム・ビット２が正確に翻訳される可能性が減少する。
【００４４】
入力シーケンスが偶数シーケンスと奇数シーケンスに分割され、インタリービングがそれぞれのシーケンス上で別々に行われ、その後にシーケンスが再結合される本発明にしたがうと、各システム・ビットは、間引きの後もそれに対応するターボ符号ビットを保持する。
【００４５】
さらに、単一の擬似ランダムシーケンス発生器（例えば、ｍ−シーケンス、 Ｍ−シーケンス, ＧＯＬＤシーケンス、Ｋａｓａｍｉシーケンス等）がインタリーバ組み立てブロックとして用いることができる。すなわち、図４において示されるように、２個のｍ−シーケンス発生器４０８および４１０がコ・セット分割のためのインタリーバを成すように組み合わされる。
【００４６】
このように、本発明は、有限サイズのフレームを符号化するためのターボ符号化器における使用のために有利なインタリービングを提供することが理解されるであろう。当業者は、図２および４に示される機器構成がコ・セット分割を持つターボ符号化器を提供することを理解するであろう。
【００４７】
上記の構成および前述の動作のシーケンスにおいて、本発明の範囲から逸脱することなく、変更が加え得ることは理解されるであろう。したがって、上記の記述、および添付図に含まれる事項はすべて、限定的な意味のものではなく、例証として解釈されるべきものであると意図されている。
【図面の簡単な説明】
【図１】従来の並行連結ターボ符号化器のブロック図。
【図２】本発明による代数的コ・セット・インタリーバを用いた並行連結ターボ符号化器のブロック図。
【図３】図１の従来のターボ符号化器における間引きのために生じるデータ損失を示す図。
【図４】本発明によるコ・セット・インタリーバとしてｍ−シーケンスを用いた並行連結ターボ符号化器のブロック図。
【符号の説明】
１０２  符号化器
１０４  符号化器
１０６  インタリーバ
２０２  単位遅延器
２０４  分別器
２０６  分別器
２０８  インタリーバ
２１０  インタリーバ
４０８  ｍ−シーケンス発生器
４１０  ｍ−シーケンス発生器
【図１】
0004422906.tif 000018
【図２】
0004422906.tif 000019
【図３】
0004422906.tif 000020
【図４】
0004422906.tif 000021