データを符号化および復号化する方法および装置
【課題】無競合インターリーバでターボ符号化する方法と装置が提供される。
【解決手段】動作中にサイズＫ’の入力ブロックが受信される。オリジナルの入力ブロックおよびインターリーブした入力ブロックは、符号語ブロックを得るために符号化される。オリジナルの入力ブロックは、サイズＫ’のインターリーバと置換π（ｉ）＝（ｆ１×ｉ＋ｆ２×ｉ２）ｍｏｄＫ’を用いてインターリーブされる。０≦ｉ≦Ｋ’−１はインターリービング後のシンボル位置の連続したインデックスであり、π（ｉ）は位置ｉに対応したインターリービング前のシンボル・インデックスであり、Ｋ’はシンボルにおけるインターリーバ・サイズであり、ｆ１とｆ２はインターリーバを定義する因数である。Ｋ’、ｆ１、ｆ２の値は、表のうちの少なくとも１つの列から得られる。符号語ブロックはチャネルを通じて送信される。
【解決手段】動作中にサイズＫ’の入力ブロックが受信される。オリジナルの入力ブロックおよびインターリーブした入力ブロックは、符号語ブロックを得るために符号化される。オリジナルの入力ブロックは、サイズＫ’のインターリーバと置換π（ｉ）＝（ｆ１×ｉ＋ｆ２×ｉ２）ｍｏｄＫ’を用いてインターリーブされる。０≦ｉ≦Ｋ’−１はインターリービング後のシンボル位置の連続したインデックスであり、π（ｉ）は位置ｉに対応したインターリービング前のシンボル・インデックスであり、Ｋ’はシンボルにおけるインターリーバ・サイズであり、ｆ１とｆ２はインターリーバを定義する因数である。Ｋ’、ｆ１、ｆ２の値は、表のうちの少なくとも１つの列から得られる。符号語ブロックはチャネルを通じて送信される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、データを符号化および復号化することに関し、特に、ターボ符号化および復号化する方法および装置に関する。
【背景技術】
【０００２】
有線および無線リンクを通じたデジタル・データ送信は、たとえば、リンクまたはチャネルにおける雑音によって、他の送信からの障害によって、または、他の環境要因によってそのデータが破損することがある。チャネルによって導入される誤りと格闘すべく、多くの通信システムが、通信を支援する誤り訂正技術を利用している。
【０００３】
誤り訂正に利用される１つの技術は、それがチャネルを通じて送信される前の情報ブロックのターボ符号化である。そのような技術を利用して、通信システムの送信器内の符号化器は、長さＫ’ビットの入力ブロック
ｕ（太字）は、Ｎビットの符号語ブロックｘ（太字）に符号化するであろう。その後、符号語ブロックは、ＩＥＥＥ８０２．１６ｅ仕様書に定義されるようにチャネル・インターリービングのようなさらなる処理の恐らく後で、チャネルを通じて送信される。受信器では、ターボ復号化器は、入力として長さＮの受信信号ベクトルｙ（太字）を得、ベクトルｕ（太字）の推定ｕ（太字、チルダ）を生成する。
【０００４】
典型的には、ターボ符号化器は、２つの構成要素畳み込み符号化器から構成されている。第１構成要素符号化器は、そのオリジナルの順序での入力として入力ブロックｕ（太字）を得、第２構成要素符号化器は、ｕ（太字）をターボ・インターリーバπに通過させた後で、そのインターリーブした順序で入力ブロックｕ（太字）を得る。ターボ符号化器出力ｘ（太字）は、系統的なビット（入力ブロックｕ（太字）に等しい）と、第１構成要素符号化器からのパリティ・ビットと、第２構成要素符号化器からのパリティ・ビットとから構成されている。
【０００５】
対応して、通信システムの受信器内のターボ復号化器は、２つの構成要素畳み込み復号化器から構成され、各々は、各構成要素符号用である。構成要素復号化器は、インターリーバπおよび対応するデインターリーバπ−１によって分離される。対数尤度比（ＬＬＲ）フォーマットのメッセージは、構成要素復号化器間で反復して渡される。決定ｕ（太字、チルダ）は、幾つかの反復の後になされる。
【０００６】
ターボ・インターリーバπは、ターボ符号設計における重要な構成要素である。それは、擬似ランダムな方法で入力ブロックｕ（太字）にスクランブルをかける原因となり、このように、良い重み分配を持った符号語ｘ（太字）を提供し、したがって、良い誤り訂正能力を提供する。
【非特許文献１】Release 6 interleaver，3GPP standard turbo code 25.212 V6.4.0，２００５年３月，Pages.16-20
【非特許文献２】Berrou C., Saouter Y., Douillard C., Kerouedan S., Jezequel M., 泥esigning good permutations for Turbo Codes: towards a single model・ in Proceedings of ICC 2004, IEEE Communications Society，２００４年６月，vol. 1, pages 341-345
【発明の開示】
【発明が解決しようとする課題】
【０００７】
復号化性能に加えて、ターボ・インターリーバπの定義は、受信器内のターボ復号化器の実施を非常に影響する。メモリ・アクセス競合のない高レベルな並行処理を可能にするために、ターボ・インターリーバπは、無競合特性を有する必要がある。
【０００８】
無競合インターリーバの前述の必要性に対処するために、無競合インターリーバでターボ符号化する方法および装置がここに提供されている。
【課題を解決するための手段】
【０００９】
動作中に、サイズＫ’の入力ブロックが受信される。オリジナルの入力ブロックおよびインターリーブした入力ブロックは、符号語ブロックを得るために符号化され、ここでは、オリジナルの入力ブロックは、サイズＫ’のインターリーバおよび置換π（ｉ）＝（ｆ１×ｉ＋ｆ２×ｉ２）ｍｏｄＫ’を使用してインターリーブされる。ここで、０≦ｉ≦Ｋ’−１は、インターリービング後のシンボル位置の連続したインデックスであり、π（ｉ）は、位置ｉに対応したインターリービング前のシンボル・インデックスであり、Ｋ’は、シンボルにおけるインターリーバ・サイズであり、ｆ１およびｆ２は、インターリーバを定義する因数である。Ｋ’、ｆ１、ｆ２の値は、テーブル２うちの少なくとも１つの列から得られる。符号語ブロックは、チャネルを通じて送信される。
【００１０】
本発明のさらに別の実施形態において、オリジナルの入力ブロックは、サイズＫ’のインターリーバおよび置換π（ｉ）＝（ｆ１×ｉ＋ｆ２×ｉ２）ｍｏｄＫ’を使用してインターリーブされる。ここで、０≦ｉ≦Ｋ’−１は、インターリービング後のシンボル位置の連続したインデックスであり、π（ｉ）は、位置ｉに対応したインターリービング前のシンボル・インデックスであり、Ｋ’は、シンボルにおけるインターリーバ・サイズであり、ｆ１およびｆ２は、インターリーバを定義する因数である。Ｋ’、ｆ１、ｆ２の値は、テーブル３のうちの少なくとも１つの列から得られる。
【００１１】
データを符号化および復号化することについて記述する前に、次の定義が、必要な背景を設定するために提供される。
・Ｋは、情報ブロック・サイズを表わしている。
【００１２】
・Ｋ’は、インターリーバ・サイズ（つまり、ターボ符号インターリーバが定義される入力ブロック・サイズ）を表わしている。
・Ｋｆｉｌｌｅｒは、情報ブロックに付加されたフィラー・ビットの数を表わしている。
【００１３】
・πは、ターボ符号内部インターリーバを表わしている。
・Ｆｌｏｏｒ演算
【００１４】
【数１】
は、ｘ以下の最大整数を表わし、Ｃｅｉｌ演算
【００１５】
【数２】
は、ｘ以上の最小整数を表わしている。
【００１６】
・ｕ（太字）は、入力ブロックを表わし、それは、Ｋ’の長さを有し、送信器でのターボ符号化器に送られる。ｕ（太字、チルダ）は、推定された入力ブロックを表わし、それは、Ｋ’の長さを有し、受信器でのターボ復号化器によって生成される。復号誤りがないときには、ｕ（太字、チルダ）＝ｕ（太字）であることを注記しておく。そうでなければｕ（太字、チルダ）≠ｕ（太字）である。
【発明を実施するための最良の形態】
【００１７】
さて、図面を参照して、ここでは、同様の参照符号は、同様の構成要素を指定しており、図１は、送信器１００のブロック図である。示されるように、送信器１００は、フィラー挿入回路１０９と、ターボ符号化器１０１と、インターリーバ・サイズ決定回路１０３と、インターリーバ・パラメータ・テーブル１０５と、送信器１０７とを備えている。符号化器１０１は、好ましくはレートが１／３の３ＧＰＰターボ符号化器であるが、符号化器１０１の動作についてここに記述される技術は、後部ビット（ｔａｉｌ ｂｉｔ）を持つ、または後部ビットを持たないターボ符号化を行なうターボ符号化器、後部ビットのバイナリ符号化器またはデュオ・バイナリ符号化器、様々なレート・マッチングおよびパンクチャリング技術を使用したターボ符号化器などを含む他の符号化器に適用されることが可能であるが、これらに限定されるものではない。回路１０３は、インターリーバ・サイズＫ’を決定し、Ｋ’は、１組のサイズからのものである。ここで、１組のサイズは、Ｋ’＝ａｐ×ｆ、Ｐｍｉｎ≦ｐ≦ｐｍａｘ、ｆｍｉｎ≦ｆ≦ｆｍａｘであり、ａは、整数であり、ｆは、ｆｍｉｎとｆｍａｘとの間の連続的な整数であり、ｐは、ｐｍｉｎとｐｍａｘとの間の整数値を取る（ａ＞１、ｐｍａｘ＞ｐｍｉｎ、ｐｍｉｎ＞１）。
【００１８】
送信器１００の動作中に、サイズＫの情報ブロックは、ターボ符号化器１０１によって符号化される必要がある。多数の様々なＫが使用される幾つかの通信システムについては、すべての情報ブロック・サイズＫに対する無競合（ＣＦ）インターリーバを定義することは効率的ではない（そして、多くの場合、不可能である）。それは、小さい組（Ｋ’）の良好に設計されたＣＦインターリーバがすべての情報ブロック・サイズをカバーすることができる場合には、望ましい。情報ブロック・サイズＫ’を与えられて、適切なインターリーバ・サイズＫ’は、利用可能なサイズの組（たとえば、テーブル１０５に列挙されたインターリーバ・サイズ）から回路１０３によって選択されることが可能である。その後、情報ブロックは、回路１０９によってサイズＫ’の入力ブロックにパディングし、入力としてターボ符号化器１０１に送られる。典型的な構成は、Ｋｆｉｌｌｅｒフィラー・ビットを持った情報ブロックを（フィラー挿入回路１０９を介して）パディングすることである。用語「サイズ」および「長さ」は、ブロックまたはベクトルにおける要素の数を示すために相互置換可能に使用されることを注記しておく。
【００１９】
一旦、Ｋ’が回路１０３によって選択されると、それは、ターボ符号化器１０１に与えられる。符号化中には、無競合インターリーバを使用することが可能である（図１には示されていない）。たとえば、インターリーバは、置換π（ｉ）＝（ｉＰ０＋Ａ＋ｄ（ｉ））ｍｏｄＫ’を使用することができ、ここでは、０≦ｉ≦Ｋ’−１は、インターリービング後のシンボル位置の連続したインデックスであり、π（ｉ）は、位置ｉに対応したインターリービング前のシンボル・インデックスであり、Ｋ’は、シンボルにおけるインターリーバ・サイズであり、Ｐ０は、Ｋ’の比較的重要な数であり、Ａは、定数であり、Ｃは、Ｋ’を分割する小さい数であり、ｄ（ｉ）は、形態ｄ（ｉ）＝β（ｉｍｏｄＣ）＋Ｐ０×α（ｉｍｏｄＣ）の「ディザ」ベクトルであり、α（・）およびβ（・）は、各々の長さがＣであるベクトルであり、０≦ｉ≦Ｋ’−１に対して周期的に適用される。別の例として、インターリーバは、置換π（ｉ）＝（ｆ１×ｉ＋ｆ２×ｉ２）ｍｏｄＫ’を使用することができ、ここで、０≦ｉ≦Ｋ’−１は、インターリービング後のシンボル位置の連続したインデックスであり、π（ｉ）は、位置ｉに対応したインターリービング前のシンボル・インデックスであり、Ｋ’は、シンボルにおけるインターリーバ・サイズであり、ｆ１およびｆ２は、インターリーバを定義する因数である。一般に、シンボルは、マルチ・ビットからなることが可能であり、インターリービングのステップは、シンボル内のビットの順序を変更する付加的なステップを使用することが可能である。一般性を失わずに、下の議論は、シンボルが１ビットのみからなる（このように、シンボル内のビットの順序を変更する必要はない）典型的な場合を考慮しており、用語「ビット」および「シンボル」は、相互置換可能に使用されることができる。
【００２０】
ターボ符号化器１０１の出力は、符号語ブロックｘ（太字）を含み、ｘ（太字）は、それがチャネルを通じて送信される場合に送信器１０７に送られる。送信器は、レート・マッチング、チャネル・インターリービング、変調などのような付加的な処理を、チャネルを通じて符号語ブロックｘ（太字）を送信する前に行なうことが可能である。
【００２１】
図２は、図１の符号化器１０１のブロック図である。示されるように、符号化器１０１は、インターリーバ２０１と、符号化回路２０２と、符号化回路２０３とを備えている。符号化器の一例は、３ＧＰＰ仕様書に定義されたターボ符号化器である。３ＧＰＰに定義されたターボ符号化器のマザー符号レートは、Ｒ＝１／３のネイティブ符号レートを有している。ターボ符号化器の出力では、３ビットは、入力ブロック内の各ビットに対して生成され、１つは、系統的ビットであり（入力ブロックにおけるビットに等しい）、１つは、構成要素符号化器１からのパリティ・ビットであり、１つは、構成要素符号化器２からのパリティ・ビットである。加えて、ターボ符号化器の出力は、ＮＴＢ後部ビットを含むことも可能であり、それは、構成要素符号のトレリスを終了するために使用される。たとえば、３ＧＰＰターボ符号に対して、ターボ符号化器の出力でのＮＴＢ＝１２ビット、構成要素符号当たり６後部ビット。一方、後部ビット構成要素畳み込み符号を使用することが可能であり、このように、ＮＴＢ＝０をなす。
【００２２】
インターリーバ２０１は、無競合インターリーバであることが可能である。インターリーバπ（ｉ）（０≦ｉ＜Ｋ’）は、それがΨ＝π（インターリーバ）およびΨ＝π−１（デインターリーバ）の両方に対して次の制約を満足する場合にのみ、ウィンドウ・サイズＷに対して無競合であると言われる。
【００２３】
【数３】
ここで、０≦ｊ＜Ｗ、０≦ｔ、ｖ＜Ｍ（＝Ｋ’／Ｗ）であり、ｔ≠ｖである。しかしながら、それは、効率的なターボ復号化器の設計に対して必ずしも必要だとは限らないが、典型的には、すべてのＭウィンドウはいっぱいであり、ここで、Ｋ’＝ＭＷである。（１）式における項は、反復復号化中に出力メモリ・バンクに外因値を書き込むときにＭプロセッサによって同時にアクセスされるメモリ・バンク・アドレスである。これらのメモリ・バンク・アドレスが、各々の読み取りおよび書き込み動作中にすべて固有である場合には、メモリ・アクセスには競合がなく、したがって、（デ）インターリービングの待ち時間を回避することができ、高速度復号化器の実施に結び付く。
【００２４】
ターボ符号化器の実施中に、長さＫ’ビットの入力ブロック１０１は、インターリーバ２０１および符号化回路２０２の両方に入る。インターリーバ２０１は、サイズＫ’の無競合インターリーバであることが可能である。
【００２５】
インターリーバ２０１は、入力ブロックをインターリーブし、インターリーブした順序で入力ブロックを符号化回路２０３に渡す。その後、符号化回路２０３は、インターリーブした入力ブロックを符号化する。同様の方法で、符号化回路２０２は、オリジナルの入力ブロックを符号化する。符号語ブロックｘ（太字）は、系統的ブロック（入力ブロックに等しい）と、符号化回路２０２の出力と、符号化回路２０３の出力とからなる。その後、符号語ブロックｘ（太字）は、送信器１０７に送られる。
【００２６】
無競合インターリーバの例としては、殆ど規則的な置換（ＡＲＰ）インターリーバは、次式から与えられる。
π（ｉ）＝（ｉＰ０＋Ａ＋ｄ（ｉ））ｍｏｄＫ’
ここで、０≦ｉ≦Ｋ’−１は、インターリービング後のビット位置の連続したインデックスであり、π（ｉ）は、位置ｉに対応したインターリービング前のビット・インデックスであり、Ｋ’は、インターリーバ・サイズであり、Ｐ０は、Ｋ’に比較的重要な数であり、Ａは、定数であり、Ｃは、Ｋ’を分割する小さい数であり、ｄ（ｉ）は、形態ｄ（ｉ）＝β（ｉｍｏｄＣ）＋Ｐ０×α（ｉｍｏｄＣ）のディザ・ベクトルであり、ここで、α（・）およびβ（・）は、長さＣの各々のベクトルであり、０≦ｉ≦Ｋ’−１に対して周期的に適用される。α（・）およびβ（・）の両方は、Ｃの倍数からなる。このように、全体的なインターリーバπ（・）は、期間Ｃを持った疑似周期的（つまり、周期的）特性を有して構築され、後部ビットターボ符号において使用されるときに、ターボ符号化自体は、擬似周期的になり、簡素化された符号設計手順に導く。
【００２７】
無競合インターリーバの別の例として、二次多項式置換（ＱＰＰ）インターリーバが、次式から与えられる。
π（ｉ）＝（ｆ１×ｉ＋ｆ２×ｉ２）ｍｏｄＫ’
ここで、０≦ｉ≦Ｋ’−１は、インターリービング後のシンボル位置の連続したインデックスであり、π（ｉ）は、位置ｉに対応したインターリービング前のシンボル・インデックスであり、Ｋ’は、シンボルにおけるインターリーバ・サイズであり、ｆ１およびｆ２は、インターリーバを定義する因数である。ＡＲＰのインターリーバと同様に、ターボ符号は、後部ビットである場合に疑似周期でもある。
【００２８】
インターリーバ２０１がＭの様々な値に対して（１）式を満足することができる場合には、復号化器は、様々な程度の並列処理を使用して実施されることができる（各Ｍに対して１つ）。このように、様々な因数を有したＫ’を選択することが望ましい。長さＫ’のＡＲＰのインターリーバに対して、任意のウィンドウ・サイズＷは、ＷがＣとＫ’の因数との倍数である場合には、メモリ・アクセス競合なしの高速復号化のために使用されることができる。並列ウィンドウの異なる定義により、並列ウィンドウの数としてＫ’の任意の因数を使用することが可能である。ＱＰＰインターリーバに対して、インターリーバ・サイズＫ’のすべての因数は、並列Ｍの可能性のあるレベルである。これは、並列因数Ｍの広い範囲を可能にするによって復号化器の設計における柔軟性および拡張性を提供する。このように、復号化速度と複雑さとの間の良い譲歩は、システム（またはユーザ要素のクラス）の必要条件に基づいてなされることができる。
【００２９】
［インターリーバ・サイズＫ’の選択］
上で議論したように、インターリーバ・サイズ決定回路１０３は、与えられたＫに対するインターリーバ・サイズＫ’を決定する必要がある。この項は、ターボ符号インターリーバが定義されることが可能である限られた数のサイズ（つまり、Ｋ’）を選択する方法について記述している。先に示したように、フィラー挿入回路（パンクチャリングまたはレート・マッチング方法と共に）は、任意の情報ブロック・サイズＫ’を扱うために使用されることが可能である。一般に、インターリーバ・サイズ選択は、フィラー・ビットによる復号化の負担および性能劣化を考慮に入れなければならない。
【００３０】
入力ブロックを形成するために情報ブロックにパディングされたフィラー・ビットＫｆｉｌｌｅｒの数は、情報ブロック・サイズＫ’の小さい割合（たとえば、約１０〜１３％）に限定されることが望ましい。これは、隣接したインターリーバ・サイズ（つまり、隣接したＫ’値）間の差を限定することによって達成される（すべての利用可能なＫ’値が昇順でソートされると仮定する）。フィラー・ビットの数は、Ｋ’≧Ｋのような利用可能な最小のＫ’を選択することによって最小化される。フィラー・ビットの数は、Ｋｆｉｌｌｅｒ＝Ｋ’−Ｋである。しかしながら、必要に応じて、Ｋ’≧Ｋの他の利用可能な値も選択されることが可能である。
【００３１】
ＫｍｉｎとＫｍａｘとの間の情報サイズをカバーするように定義された次のサイズの組を考慮する。
Ｋ’＝ａｐ×ｆ（ｐｍｉｎ≦ｐ≦ｐｍａｘ；ｆｍｉｎ≦ｆ≦ｆｍａｘ） …（２）
ここで、ａは、整数であり、ｆは、ｆｍｉｎとｆｍａｘとの間の連続的な整数であり、ｐは、ｐｍｉｎとｐｍａｘとの間の整数値を取る（ａ＞１、ｐｍａｘ＞ｐｍｉｎ、ｐｍｉｎ＞１）。必要ではないが、Ｋｍｉｎ＝ａｐｍｉｎ×ｆｍｉｎ、およびＫｍａｘ＝ａｐｍａｘ×ｆｍａｘのようなこれらのパラメータを選択することができる一方で、必要でないことがある任意のサイズを廃棄する。一連の情報ブロック・サイズをカバーするために限定されたサイズの組を選択するこの方法は、片対数スライスと呼ばれる。与えられたサイズＫの情報ブロックに対して、サイズＫ’は、利用可能なインターリーバ・サイズの組と、情報ブロック・サイズＫ’とに基づいて選択される。
【００３２】
片対数スライスは、大きいダイナミック・レンジの信号を圧縮するのに利用される圧伸操作と同様である（たとえば、音声コーデックにおいて使用されるＡ−Ｌａｗおよびｍｕ−Ｌａｗ圧伸器）。片対数スライスの規則は、広範囲の情報ブロック・サイズをカバーするための効率的な設計を可能にする。
【００３３】
パラメータを選択する幾つかの方法については、ｆｍｉｎおよびｆｍａｘ値を選択する１つの方法は、Ｋ’値が、互いに並んだ隣接したｐに起因させることである（つまりａｐ×（ｆｍａｘ＋１）＝ａｐ＋１×ｆｍｉｎ）、したがって、
ｆｍａｘ＝ａ×ｆｍｉｎ−１
である。与えられたｐの値に対して、２つの隣接したブロック・サイズＫ’間の分離は、ａｐによって与えられ、それは、情報ブロック・サイズＫがグループｐであり、インターリーバ・サイズがＫ’に等しい場合に、最大ａｐ−１フィラー・ビットが加えられることを意味している。このように、情報ブロック・サイズＫに対するフィラー・ビットＫｆｉｌｌｅｒの割合は、下に示されるように拘束され、それは、ブロック・サイズＫが（ｐ，ｆｍｉｎ）によって与えられるサイズよりも僅かに大きいときに生じ、Ｋ’を使用して（ｐ，ｆｍｉｎ＋１）によって次のものが与えられる。
【００３４】
【数４】
これに代えて、隣接したｐに起因するＫ’値は、ａｐ×ｆｍａｘ＝ａｐ＋１×（ｆｍｉｎ−１）を介して互いに並ぶことができ、ｆｍａｘ＝ａ×（ｆｍｉｎ−１）を生じる。これは、同様のＫｆｉｌｌｅｒ／Ｋ限界を与えるであろう。したがって、片対数スライスのためのパラメータは、サポートされるブロック・サイズの範囲によって、さらに、フィラー・ビットの許容可能な割合で調整されることができる。ｆｍｉｎの選択は、次の２つの必要条件間の平衡を必要とする。
【００３５】
・ｆｍｉｎは、フィラー・ビットの割合を低減するように大きくあるべきである。
・ｆｍｉｎは、各のｐに対して定義されたブロック・サイズの数が、ｆｍａｘ＝ａ×ｆｍｉｎ−１であると仮定して、ｆｍａｘ−ｆｍｉｎ＋１＝（ａ−１）×ｆｍｉｎであるので、インターリーバのテーブルのサイズを限定するように小さくあるべきである。
【００３６】
片対数スライス法は、任意のブロック・サイズに対して非常に簡素であり、使用されるインターリーバ・サイズＫ’は、（２）式から容易に決定されることが可能である。
［インターリーバ・サイズの選択例］
３ＧＰＰ ＬＴＥについては、４０〜６１４４ビット間の各ブロック・サイズのＣＦインターリーバを定義することが必須ではない。限定された、または小さい組の良好に設計されたＣＦインターリーバは、すべてのブロック・サイズをカバーするのに十分である。定義されていないブロック・サイズ（つまり、ＣＦインターリーバが定義されていない）については、零パディング（つまり、フィラー・ビットの添付）は、上で記述したように、効果的に使用されることができる。
【００３７】
第１例として、テーブル１０５における３ＧＰＰの長期的な発展（ＬＴＥ）のための情報ブロック・サイズをカバーするのに適した１組のインターリーバは、上で記述した片対数スライス法に基づいて定義される。特に、次式は、２６４〜４０９６のサイズをカバーしている。
Ｋ’＝２ｐ×ｆ（ｐ＝３，４，５，６；ｆ＝３３，３４，…６４） …（３）
４０ビット〜６１４４ビットの全範囲をカバーするために、（３）式で定義されたＫ’の組は、８（ビット）のステップ・サイズで２６４〜４０に延長され、６４（ビット）のステップ・サイズで４０９６〜６１４４に拡張されている。１８８のインターリーバ・サイズのすべての組は、下のテーブル１にも列挙されている。
（３）式で特定されるサイズは、ａ＝２、ｐｍｉｎ＝３、ｐｍａｘ＝６、ｆｍｉｎ＝３３、ｆｍａｘ＝６４、ｆｍａｘ＝ａ×（ｆｍｉｎ−１）を有しており、したがって、ａｐ×ｆｍａｘ＝ａｐ＋１×（ｆｍｉｎ−１）であることを注記しておく。
【００３８】
［テーブル１］３ＧＰＰ ＬＴＥ用に定義されたインターリーバ・サイズＫ’の組。
【００３９】
【表１】
一旦１０５のインターリーバ・サイズが決定されると、ＣＦインターリーバは、各々のインターリーバ・サイズに対して設計されることが可能である。任意の情報ブロック・サイズＫが与えられると、回路１０３は、Ｋ以上の１０５からのＫ’の最小値を選択することによってＫに使用されるインターリーバ・サイズＫを決定することができる。その後、サイズＫ’のインターリーバに関連したパラメータは、インターリーバ・パラメータ１０５の格納手段からルックアップされ、それは、通信装置用のメモリに通常格納されている。
【００４０】
テーブル１に示されるサイズは、最小４０ビットおよび最大６１４４ビットを持ったＫ’に対して定義された例のみであることを注記しておく。さらに、簡素性について、サイズは、後部のまたは後部ビット構成要素符号を使用したそれらの間の差を考慮していない。ターボ符号化器が後部ビットでなされる場合には、７の倍数であるＫ’は使用されることができない。これらは、削除または修正されるであろう。最後に、付加的なインターリーバ・サイズは、インターリーバ間の間隔を減少させるために上のものに加えられることが可能である。たとえば、余分なインターリーバは、テーブル１における間隔１６でインターリーバ間に定義されることが可能であり、その結果、インターリーバは、より小さいＫ’に対するすべてのバイト間隔に対して定義される。
【００４１】
［ＱＰＰインターリーバの例］
３ＧＰＰの長期的な発展（ＬＴＥ）用のテーブル１におけるインターリーバ・サイズをカバーするのに適した７１ ＣＦ ＱＰＰインターリーバの部分集合がテーブル２に示されている。これらのインターリーバは、二次方程式の逆多項式を有しており、その結果、デインターリーバもまた、ＱＰＰである。加えて、３ＧＰＰの長期的な発展（ＬＴＥ）用のテーブル１におけるインターリーバ・サイズをカバーするのに適した１０ ＣＦ ＱＰＰインターリーバの部分集合がテーブル３に示されており、ここで、インターリーバは、次数が３または４の置換多項式であるデインターリーバを有している。
【００４２】
テーブル１におけるすべてのインターリーバ・サイズＫ’について、Ｋ’は、４の倍数である（実際には、Ｋ’は８の倍数である）。そのようなサイズに対して、２次の多項式π（ｉ）＝（ｆ１×ｉ＋ｆ２×ｉ２）ｍｏｄＫ’は、ｆ２がＫ’のすべての素因数で除算可能であり、ｆ１がＫ’の如何なる素因数でも除算可能でない場合にのみ、有効なインターリーバである。テーブル２およびテーブル３におけるすべてのインターリーバ・パラメータがこの条件を満足していることを示すことができる。
【００４３】
ＱＰＰインターリーバは、置換多項式の形式で表現することができるデインターリーバを有することを保証される、つまり、
【００４４】
【数５】
であるが、デインターリーバπ−１（ｘ）の次数ｍは、ｆ２のすべての素因数の中で最も高い順位と比べ少しも大きくないということだけが保証される。パラメータ（ｆ１，ｆ２）は、低いｍが望まれる場合には、より厳格な条件を満足しなければならない。このように、良い誤り訂正能力を提供する一方で低い次数のデインターリーバを有したＱＰＰインターリーバを設計するのは困難であることがある。
【００４５】
ターボ符号化により、インターリーバおよびデインターリーバの両方の複雑さが重要となる。デインターリーバの次数ｍは、ターボ復号化器の実装の複雑さに直接的に影響することがある。低い次数のデインターリーバは、より高い次数のデインターリーバよりも実装することがそれほど複雑ではない。したがって、ＱＰＰインターリーバの探索においては、
・好ましくは、二次方程式のデインターリーバを備えたインターリーバ（つまり、ｍ＝２、デインターリーバはＱＰＰでもある）が使用されるべきである。たとえば、テーブル２におけるＱＰＰインターリーバの各々は、ターボ符号化性能を妥協することなく、二次方程式のデインターリーバを有している。
【００４６】
・もし、或るサイズ用場合Ｋ’に対して、誤り訂正性能が著しく妥協される場合であって、インターリーバが二次方程式のデインターリーバを有していなければならない場合には、僅かに高い次数（たとえば、ｍ＝３または４）のデインターリーバを備えたインターリーバが代わりに使用されることができる。たとえば、テーブル３におけるＱＰＰインターリーバの各々は、次数が３または４のデインターリーバを有しており、良いターボ符号化性能を提供する。
【００４７】
デインターリーバに制約がまったくない場合には、テーブル２における長さＫ’のＱＰＰは、９程度の次数のデインターリーバを有することができ、テーブル３におけるものは、７程度の次数のデインターリーバを有することができると指摘されるべきである。
【００４８】
インターリーバ・パラメータ１０５のための格納手段は、Ｋ’がテーブル２またはテーブル３に含まれる場合には、テーブル２またはテーブル３のうちの少なくとも１つの列から得られるＫ’、ｆ１、ｆ２の値を使用してＱＰＰインターリーバ・パラメータを格納することが可能である。インターリーバ２０１は、Ｋ’がテーブル２またはテーブル３に含まれる場合には、テーブル２またはテーブル３のうちの少なくとも１つの列から得られるＫ’ｆ１、ｆ２の値を持ったＱＰＰインターリーバを使用することが可能である。
［テーブル２］次数が２の置換多項式であるデインターリーバを備えたＬＴＥ用に定義されたＱＰＰインターリーバの部分集合用のパラメータ（つまり、逆二次方程式）。
【００４９】
【表２】
［テーブル３］次数が３または４の置換多項式であるデインターリーバを備えたＬＴＥ用に定義されたＱＰＰインターリーバの部分集合用パラメータ。
【００５０】
【表３】
図３は、受信器３００のブロック図である。入力では、フィラー処理回路３０２は、チャネルを通じて（たとえば、無線で）送信されてくることがある信号ベクトルを受信する。その後、回路３０６は、インターリーバ・サイズＫ’を決定し、それは、上で議論したのと同様の方法でなされることができる（たとえば、格納装置３０８から、または演算を介してテーブルのルックアップを行なうことによって）。したがって、情報ブロック・サイズＫを与えられて、復号化器３０４は、符号化器１０１によって使用されたのと同一のインターリーバ・サイズＫ’を使用する。フィラー処理回路３０２は、受信した信号ベクトルおよびフィラー・ビット位置を適切に処理するために使用される（たとえば、フィラー・ビット位置が既知である場合には、対応するＬＬＲ量は、復号化中に非常に高い量に設定されることができる。その後、ターボ復号化器３０４は、復号化を行ない、長さＫ’の入力ブロックの推定ｕ（太字、チルダ）を得る。最後に、情報ブロック抽出回路３１０は、ｕ（太字、チルダ）から推定された情報ブロックを抽出する。フィラー処理回路３０２は、説明の容易さのためにターボ復号化器の外部に示されているが、これら２つは、実装の際に組み合わせられることができる。
【００５１】
図４は、図３のターボ復号化器３０４のブロック図である。明白なように、インターリーバ４０２およびデインターリーバ４０１は、復号化回路４０３と復号化回路４０４との間に存在する。反復復号化は、本技術において公知なもののように行われるが、先行技術の復号化器とは異なり、インターリーバ・サイズＫ’は、１組のサイズからのものである。ここで、１組のサイズは、Ｋ’＝ａｐ×ｆ（ｐｍｉｎ≦ｐ≦ｐｍａｘ；ｆｍｉｎ≦ｆ≦ｆｍａｘ）を含んでおり、ａは、整数であり、ｆは、ｆｍｉｎとｆｍａｘとの間の連続的な整数であり、ｐは、ｐｍｉｎとｐｍａｘとの間の整数値を取る（ａ＞１、ｐｍａｘ＞ｐｍｉｎ、ｐｍｉｎ＞１）。パラメータＫｆｉｌｌｅｒは、ターボ復号化器３０４には必要であるか、または、必要ではないことがあり、したがって、図４においては破線でラベル付けされている。
【００５２】
インターリーバ４０２は、置換π（ｉ）＝（ｆ１×ｉ＋ｆ２×ｉ２）ｍｏｄＫ’を利用することが可能であり、ここで、０≦ｉ≦Ｋ’−１は、インターリービング後のシンボル位置の連続したインデックスであり、π（ｉ）は、位置ｉに対応したインターリービング前のシンボル・インデックスであり、Ｋ’は、シンボルにおけるインターリーバ・サイズであり、ｆ１およびｆ２は、インターリーバを定義する因数である。Ｋ’、ｆ１、ｆ２の値は、Ｋ’がテーブル２またはテーブル３に含まれる場合には、テーブル２またはテーブル３の１列から得られる。デインターリーバ４０１は、インターリーバ４０２の逆関数を行なう。
【００５３】
図５は、送信器１００の動作を示すフローチャートである。論理フローは、ステップ５０１で開始され、ここでは、回路１０３は、１組のサイズからのものであるインターリーバ・サイズＫ’を決定する。ここで、１組のサイズは、Ｋ’＝ａｐ×ｆ（ｐｍｉｎ≦ｐ≦ｐｍａｘ；ｆｍｉｎ≦ｆ≦ｆｍａｘ）を含み、ａは、整数であり、ｆは、ｆｍｉｎとｆｍａｘとの間の連続的な整数であり、ｐは、ｐｍｉｎとｐｍａｘとの間の整数値を取る（ａ＞１、ｐｍａｘ＞ｐｍｉｎ、ｐｍｉｎ＞１）。
【００５４】
ステップ５０３では、フィラー挿入回路１０９は、サイズＫの情報ブロックを受信し、サイズＫの情報ブロックをサイズＫ’の入力ブロックｕ（太字）にパディングし、入力ブロックｕ（太字）を出力する。その後、インターリーバ２０１は、サイズＫ’の入力ブロックを（好ましくは、無競合インターリーバを使用して）インターリーブし（ステップ５０７）、サイズＫ’のインターリーブしたブロックを符号化回路２０３に送る（ステップ５０９）。最後に、ステップ５１１で、オリジナルの入力ブロックおよびインターリーブした入力ブロックが符号化される。
【００５５】
上で議論したように、入力ブロックをインターリーブするステップは置換π（ｉ）＝（ｆ１×ｉ＋ｆ２×ｉ２）ｍｏｄＫ’を使用するステップを含むことが可能である。ここで、０≦ｉ≦Ｋ’−１は、インターリービング後のシンボル位置の連続したインデックスであり、π（ｉ）は、位置ｉに対応したインターリービング前のシンボル・インデックスであり、Ｋ’は、シンボルにおけるインターリーバ・サイズであり、ｆ１およびｆ２は、インターリーバを定義する因数である。Ｋ’、ｆ１、ｆ２の値は、Ｋ’がテーブル２またはテーブル３に含まれる場合には、テーブル２またはテーブル３の１列から得られる。
【００５６】
図６は、図３の受信器の動作を示すフローチャートである。論理フローは、ステップ６０１で開始され、ここでは、回路３０６は、インターリーバ・サイズＫ’を決定する。ステップ６０３では、回路３０２は、フィラー・ビット情報を受信した信号ベクトルに加え、たとえば、フィラー・ビットおよびフィラー・ビット位置が公知の回路３０２である場合には、ターボ復号化器の入力におけるそれらの位置の対数尤度比（ＬＬＲ）を高い量に設定することが可能である。ステップ６０７では、ターボ復号化器は、サイズＫ’のインターリーバおよびデインターリーバを使用して復号化器の入力ブロックを復号化し、長さＫ’の入力ブロックの推定ｕ（太字、チルダ）を出力する。ステップ６０９では、情報ブロック抽出回路３１０は、長さＫ’の情報ブロックの推定を得るためにフィラー・ビットを削除する。最後に、ステップ６１１では、推定された情報ブロックが出力される。
【００５７】
本発明が特定の実施形態に関して特に示され且つ記述される一方で、当業者には、形態および詳細における様々な変更が本発明の精神および範囲から逸脱することなしにそこになされることが可能であることが理解されるであろう。一例においては、インターリーバのテーブルは、次のものを含む特別な場合をさらに扱うために強化されることが可能である。（ａ）任意の特別なブロック・サイズをカバーするように定義されるインターリーバ・サイズの付加的な組を使用することが（たとえば、フィラー・ビットなしで、または、より小さいフィラー・ビット数で）扱われなければならない。（ｂ）インターリーバ・サイズは、片対数スライスのサイズからの小さい値を加算または減算することによって僅かに調整されることができる。別の例においては、本発明は、バイナリ入力ターボ符号化器を仮定して上に記述したが、同一の原理は、ターボ符号化器が入力としてシンボルを取るときには適用されることができる。たとえば、デュオ・バイナリ・ターボ符号は、一度に２バイナリ・ビットのシンボルを取り、ターボ・インターリーバは、シンボルの順序を変更する（シンボル内のビットを交互に入れ替えるようにさらにスクランブルをかける）。そのような場合には、入力ブロック・サイズは、シンボルにおいて測定され、インターリーバ・サイズは、入力ブロックにおけるシンボルの数に等しい。別の例においては、上の記述は、インターリーバ・サイズおよびインターリーバ・パラメータがルックアップ・テーブルに格納されるものと仮定しているが、それらは、代数演算のような他の手段を介して決定されることも可能である。さらに別の例においては、上の記述は、ターボ符号を仮定しているが、本方法は、他のＦＥＣ手法（たとえば、低密度パリティ・チェック（ＬＤＰＣ）符号、リード・ソロモン（ＲＳ）符号などを含む）に適用されることも可能である。そのような変更は、次の請求の範囲内にあると意図されている。
【図面の簡単な説明】
【００５８】
【図１】送信器のブロック図である。
【図２】図１のターボ符号化器のブロック図である。
【図３】受信器のブロック図である。
【図４】図３のターボ復号化器のブロック図である。
【図５】図１の送信器の動作を示すフローチャートである。
【図６】図３の受信器の動作を示すフローチャートである。
【符号の説明】
【００５９】
１００ 送信器
１０１ ターボ符号化器
１０３ インターリーバ・サイズ決定回路
１０５ インターリーバ・パラメータ・テーブル
１０７ 送信器
１０９ フィラー挿入回路
２０１ インターリーバ
２０２，２０３ 符号化回路
３００ 受信器
３０２ フィラー処理回路
３０４ ターボ復号化器
３０６ インターリーバ・サイズ決定回路
３０８ インターリーバ・パラメータ格納装置
３１０ 情報ブロック抽出回路
４０１ デインターリーバ
４０２ インターリーバ
４０３，４０４ 復号化回路
【技術分野】
【０００１】
本発明は、概して、データを符号化および復号化することに関し、特に、ターボ符号化および復号化する方法および装置に関する。
【背景技術】
【０００２】
有線および無線リンクを通じたデジタル・データ送信は、たとえば、リンクまたはチャネルにおける雑音によって、他の送信からの障害によって、または、他の環境要因によってそのデータが破損することがある。チャネルによって導入される誤りと格闘すべく、多くの通信システムが、通信を支援する誤り訂正技術を利用している。
【０００３】
誤り訂正に利用される１つの技術は、それがチャネルを通じて送信される前の情報ブロックのターボ符号化である。そのような技術を利用して、通信システムの送信器内の符号化器は、長さＫ’ビットの入力ブロック
ｕ（太字）は、Ｎビットの符号語ブロックｘ（太字）に符号化するであろう。その後、符号語ブロックは、ＩＥＥＥ８０２．１６ｅ仕様書に定義されるようにチャネル・インターリービングのようなさらなる処理の恐らく後で、チャネルを通じて送信される。受信器では、ターボ復号化器は、入力として長さＮの受信信号ベクトルｙ（太字）を得、ベクトルｕ（太字）の推定ｕ（太字、チルダ）を生成する。
【０００４】
典型的には、ターボ符号化器は、２つの構成要素畳み込み符号化器から構成されている。第１構成要素符号化器は、そのオリジナルの順序での入力として入力ブロックｕ（太字）を得、第２構成要素符号化器は、ｕ（太字）をターボ・インターリーバπに通過させた後で、そのインターリーブした順序で入力ブロックｕ（太字）を得る。ターボ符号化器出力ｘ（太字）は、系統的なビット（入力ブロックｕ（太字）に等しい）と、第１構成要素符号化器からのパリティ・ビットと、第２構成要素符号化器からのパリティ・ビットとから構成されている。
【０００５】
対応して、通信システムの受信器内のターボ復号化器は、２つの構成要素畳み込み復号化器から構成され、各々は、各構成要素符号用である。構成要素復号化器は、インターリーバπおよび対応するデインターリーバπ−１によって分離される。対数尤度比（ＬＬＲ）フォーマットのメッセージは、構成要素復号化器間で反復して渡される。決定ｕ（太字、チルダ）は、幾つかの反復の後になされる。
【０００６】
ターボ・インターリーバπは、ターボ符号設計における重要な構成要素である。それは、擬似ランダムな方法で入力ブロックｕ（太字）にスクランブルをかける原因となり、このように、良い重み分配を持った符号語ｘ（太字）を提供し、したがって、良い誤り訂正能力を提供する。
【非特許文献１】Release 6 interleaver，3GPP standard turbo code 25.212 V6.4.0，２００５年３月，Pages.16-20
【非特許文献２】Berrou C., Saouter Y., Douillard C., Kerouedan S., Jezequel M., 泥esigning good permutations for Turbo Codes: towards a single model・ in Proceedings of ICC 2004, IEEE Communications Society，２００４年６月，vol. 1, pages 341-345
【発明の開示】
【発明が解決しようとする課題】
【０００７】
復号化性能に加えて、ターボ・インターリーバπの定義は、受信器内のターボ復号化器の実施を非常に影響する。メモリ・アクセス競合のない高レベルな並行処理を可能にするために、ターボ・インターリーバπは、無競合特性を有する必要がある。
【０００８】
無競合インターリーバの前述の必要性に対処するために、無競合インターリーバでターボ符号化する方法および装置がここに提供されている。
【課題を解決するための手段】
【０００９】
動作中に、サイズＫ’の入力ブロックが受信される。オリジナルの入力ブロックおよびインターリーブした入力ブロックは、符号語ブロックを得るために符号化され、ここでは、オリジナルの入力ブロックは、サイズＫ’のインターリーバおよび置換π（ｉ）＝（ｆ１×ｉ＋ｆ２×ｉ２）ｍｏｄＫ’を使用してインターリーブされる。ここで、０≦ｉ≦Ｋ’−１は、インターリービング後のシンボル位置の連続したインデックスであり、π（ｉ）は、位置ｉに対応したインターリービング前のシンボル・インデックスであり、Ｋ’は、シンボルにおけるインターリーバ・サイズであり、ｆ１およびｆ２は、インターリーバを定義する因数である。Ｋ’、ｆ１、ｆ２の値は、テーブル２うちの少なくとも１つの列から得られる。符号語ブロックは、チャネルを通じて送信される。
【００１０】
本発明のさらに別の実施形態において、オリジナルの入力ブロックは、サイズＫ’のインターリーバおよび置換π（ｉ）＝（ｆ１×ｉ＋ｆ２×ｉ２）ｍｏｄＫ’を使用してインターリーブされる。ここで、０≦ｉ≦Ｋ’−１は、インターリービング後のシンボル位置の連続したインデックスであり、π（ｉ）は、位置ｉに対応したインターリービング前のシンボル・インデックスであり、Ｋ’は、シンボルにおけるインターリーバ・サイズであり、ｆ１およびｆ２は、インターリーバを定義する因数である。Ｋ’、ｆ１、ｆ２の値は、テーブル３のうちの少なくとも１つの列から得られる。
【００１１】
データを符号化および復号化することについて記述する前に、次の定義が、必要な背景を設定するために提供される。
・Ｋは、情報ブロック・サイズを表わしている。
【００１２】
・Ｋ’は、インターリーバ・サイズ（つまり、ターボ符号インターリーバが定義される入力ブロック・サイズ）を表わしている。
・Ｋｆｉｌｌｅｒは、情報ブロックに付加されたフィラー・ビットの数を表わしている。
【００１３】
・πは、ターボ符号内部インターリーバを表わしている。
・Ｆｌｏｏｒ演算
【００１４】
【数１】
は、ｘ以下の最大整数を表わし、Ｃｅｉｌ演算
【００１５】
【数２】
は、ｘ以上の最小整数を表わしている。
【００１６】
・ｕ（太字）は、入力ブロックを表わし、それは、Ｋ’の長さを有し、送信器でのターボ符号化器に送られる。ｕ（太字、チルダ）は、推定された入力ブロックを表わし、それは、Ｋ’の長さを有し、受信器でのターボ復号化器によって生成される。復号誤りがないときには、ｕ（太字、チルダ）＝ｕ（太字）であることを注記しておく。そうでなければｕ（太字、チルダ）≠ｕ（太字）である。
【発明を実施するための最良の形態】
【００１７】
さて、図面を参照して、ここでは、同様の参照符号は、同様の構成要素を指定しており、図１は、送信器１００のブロック図である。示されるように、送信器１００は、フィラー挿入回路１０９と、ターボ符号化器１０１と、インターリーバ・サイズ決定回路１０３と、インターリーバ・パラメータ・テーブル１０５と、送信器１０７とを備えている。符号化器１０１は、好ましくはレートが１／３の３ＧＰＰターボ符号化器であるが、符号化器１０１の動作についてここに記述される技術は、後部ビット（ｔａｉｌ ｂｉｔ）を持つ、または後部ビットを持たないターボ符号化を行なうターボ符号化器、後部ビットのバイナリ符号化器またはデュオ・バイナリ符号化器、様々なレート・マッチングおよびパンクチャリング技術を使用したターボ符号化器などを含む他の符号化器に適用されることが可能であるが、これらに限定されるものではない。回路１０３は、インターリーバ・サイズＫ’を決定し、Ｋ’は、１組のサイズからのものである。ここで、１組のサイズは、Ｋ’＝ａｐ×ｆ、Ｐｍｉｎ≦ｐ≦ｐｍａｘ、ｆｍｉｎ≦ｆ≦ｆｍａｘであり、ａは、整数であり、ｆは、ｆｍｉｎとｆｍａｘとの間の連続的な整数であり、ｐは、ｐｍｉｎとｐｍａｘとの間の整数値を取る（ａ＞１、ｐｍａｘ＞ｐｍｉｎ、ｐｍｉｎ＞１）。
【００１８】
送信器１００の動作中に、サイズＫの情報ブロックは、ターボ符号化器１０１によって符号化される必要がある。多数の様々なＫが使用される幾つかの通信システムについては、すべての情報ブロック・サイズＫに対する無競合（ＣＦ）インターリーバを定義することは効率的ではない（そして、多くの場合、不可能である）。それは、小さい組（Ｋ’）の良好に設計されたＣＦインターリーバがすべての情報ブロック・サイズをカバーすることができる場合には、望ましい。情報ブロック・サイズＫ’を与えられて、適切なインターリーバ・サイズＫ’は、利用可能なサイズの組（たとえば、テーブル１０５に列挙されたインターリーバ・サイズ）から回路１０３によって選択されることが可能である。その後、情報ブロックは、回路１０９によってサイズＫ’の入力ブロックにパディングし、入力としてターボ符号化器１０１に送られる。典型的な構成は、Ｋｆｉｌｌｅｒフィラー・ビットを持った情報ブロックを（フィラー挿入回路１０９を介して）パディングすることである。用語「サイズ」および「長さ」は、ブロックまたはベクトルにおける要素の数を示すために相互置換可能に使用されることを注記しておく。
【００１９】
一旦、Ｋ’が回路１０３によって選択されると、それは、ターボ符号化器１０１に与えられる。符号化中には、無競合インターリーバを使用することが可能である（図１には示されていない）。たとえば、インターリーバは、置換π（ｉ）＝（ｉＰ０＋Ａ＋ｄ（ｉ））ｍｏｄＫ’を使用することができ、ここでは、０≦ｉ≦Ｋ’−１は、インターリービング後のシンボル位置の連続したインデックスであり、π（ｉ）は、位置ｉに対応したインターリービング前のシンボル・インデックスであり、Ｋ’は、シンボルにおけるインターリーバ・サイズであり、Ｐ０は、Ｋ’の比較的重要な数であり、Ａは、定数であり、Ｃは、Ｋ’を分割する小さい数であり、ｄ（ｉ）は、形態ｄ（ｉ）＝β（ｉｍｏｄＣ）＋Ｐ０×α（ｉｍｏｄＣ）の「ディザ」ベクトルであり、α（・）およびβ（・）は、各々の長さがＣであるベクトルであり、０≦ｉ≦Ｋ’−１に対して周期的に適用される。別の例として、インターリーバは、置換π（ｉ）＝（ｆ１×ｉ＋ｆ２×ｉ２）ｍｏｄＫ’を使用することができ、ここで、０≦ｉ≦Ｋ’−１は、インターリービング後のシンボル位置の連続したインデックスであり、π（ｉ）は、位置ｉに対応したインターリービング前のシンボル・インデックスであり、Ｋ’は、シンボルにおけるインターリーバ・サイズであり、ｆ１およびｆ２は、インターリーバを定義する因数である。一般に、シンボルは、マルチ・ビットからなることが可能であり、インターリービングのステップは、シンボル内のビットの順序を変更する付加的なステップを使用することが可能である。一般性を失わずに、下の議論は、シンボルが１ビットのみからなる（このように、シンボル内のビットの順序を変更する必要はない）典型的な場合を考慮しており、用語「ビット」および「シンボル」は、相互置換可能に使用されることができる。
【００２０】
ターボ符号化器１０１の出力は、符号語ブロックｘ（太字）を含み、ｘ（太字）は、それがチャネルを通じて送信される場合に送信器１０７に送られる。送信器は、レート・マッチング、チャネル・インターリービング、変調などのような付加的な処理を、チャネルを通じて符号語ブロックｘ（太字）を送信する前に行なうことが可能である。
【００２１】
図２は、図１の符号化器１０１のブロック図である。示されるように、符号化器１０１は、インターリーバ２０１と、符号化回路２０２と、符号化回路２０３とを備えている。符号化器の一例は、３ＧＰＰ仕様書に定義されたターボ符号化器である。３ＧＰＰに定義されたターボ符号化器のマザー符号レートは、Ｒ＝１／３のネイティブ符号レートを有している。ターボ符号化器の出力では、３ビットは、入力ブロック内の各ビットに対して生成され、１つは、系統的ビットであり（入力ブロックにおけるビットに等しい）、１つは、構成要素符号化器１からのパリティ・ビットであり、１つは、構成要素符号化器２からのパリティ・ビットである。加えて、ターボ符号化器の出力は、ＮＴＢ後部ビットを含むことも可能であり、それは、構成要素符号のトレリスを終了するために使用される。たとえば、３ＧＰＰターボ符号に対して、ターボ符号化器の出力でのＮＴＢ＝１２ビット、構成要素符号当たり６後部ビット。一方、後部ビット構成要素畳み込み符号を使用することが可能であり、このように、ＮＴＢ＝０をなす。
【００２２】
インターリーバ２０１は、無競合インターリーバであることが可能である。インターリーバπ（ｉ）（０≦ｉ＜Ｋ’）は、それがΨ＝π（インターリーバ）およびΨ＝π−１（デインターリーバ）の両方に対して次の制約を満足する場合にのみ、ウィンドウ・サイズＷに対して無競合であると言われる。
【００２３】
【数３】
ここで、０≦ｊ＜Ｗ、０≦ｔ、ｖ＜Ｍ（＝Ｋ’／Ｗ）であり、ｔ≠ｖである。しかしながら、それは、効率的なターボ復号化器の設計に対して必ずしも必要だとは限らないが、典型的には、すべてのＭウィンドウはいっぱいであり、ここで、Ｋ’＝ＭＷである。（１）式における項は、反復復号化中に出力メモリ・バンクに外因値を書き込むときにＭプロセッサによって同時にアクセスされるメモリ・バンク・アドレスである。これらのメモリ・バンク・アドレスが、各々の読み取りおよび書き込み動作中にすべて固有である場合には、メモリ・アクセスには競合がなく、したがって、（デ）インターリービングの待ち時間を回避することができ、高速度復号化器の実施に結び付く。
【００２４】
ターボ符号化器の実施中に、長さＫ’ビットの入力ブロック１０１は、インターリーバ２０１および符号化回路２０２の両方に入る。インターリーバ２０１は、サイズＫ’の無競合インターリーバであることが可能である。
【００２５】
インターリーバ２０１は、入力ブロックをインターリーブし、インターリーブした順序で入力ブロックを符号化回路２０３に渡す。その後、符号化回路２０３は、インターリーブした入力ブロックを符号化する。同様の方法で、符号化回路２０２は、オリジナルの入力ブロックを符号化する。符号語ブロックｘ（太字）は、系統的ブロック（入力ブロックに等しい）と、符号化回路２０２の出力と、符号化回路２０３の出力とからなる。その後、符号語ブロックｘ（太字）は、送信器１０７に送られる。
【００２６】
無競合インターリーバの例としては、殆ど規則的な置換（ＡＲＰ）インターリーバは、次式から与えられる。
π（ｉ）＝（ｉＰ０＋Ａ＋ｄ（ｉ））ｍｏｄＫ’
ここで、０≦ｉ≦Ｋ’−１は、インターリービング後のビット位置の連続したインデックスであり、π（ｉ）は、位置ｉに対応したインターリービング前のビット・インデックスであり、Ｋ’は、インターリーバ・サイズであり、Ｐ０は、Ｋ’に比較的重要な数であり、Ａは、定数であり、Ｃは、Ｋ’を分割する小さい数であり、ｄ（ｉ）は、形態ｄ（ｉ）＝β（ｉｍｏｄＣ）＋Ｐ０×α（ｉｍｏｄＣ）のディザ・ベクトルであり、ここで、α（・）およびβ（・）は、長さＣの各々のベクトルであり、０≦ｉ≦Ｋ’−１に対して周期的に適用される。α（・）およびβ（・）の両方は、Ｃの倍数からなる。このように、全体的なインターリーバπ（・）は、期間Ｃを持った疑似周期的（つまり、周期的）特性を有して構築され、後部ビットターボ符号において使用されるときに、ターボ符号化自体は、擬似周期的になり、簡素化された符号設計手順に導く。
【００２７】
無競合インターリーバの別の例として、二次多項式置換（ＱＰＰ）インターリーバが、次式から与えられる。
π（ｉ）＝（ｆ１×ｉ＋ｆ２×ｉ２）ｍｏｄＫ’
ここで、０≦ｉ≦Ｋ’−１は、インターリービング後のシンボル位置の連続したインデックスであり、π（ｉ）は、位置ｉに対応したインターリービング前のシンボル・インデックスであり、Ｋ’は、シンボルにおけるインターリーバ・サイズであり、ｆ１およびｆ２は、インターリーバを定義する因数である。ＡＲＰのインターリーバと同様に、ターボ符号は、後部ビットである場合に疑似周期でもある。
【００２８】
インターリーバ２０１がＭの様々な値に対して（１）式を満足することができる場合には、復号化器は、様々な程度の並列処理を使用して実施されることができる（各Ｍに対して１つ）。このように、様々な因数を有したＫ’を選択することが望ましい。長さＫ’のＡＲＰのインターリーバに対して、任意のウィンドウ・サイズＷは、ＷがＣとＫ’の因数との倍数である場合には、メモリ・アクセス競合なしの高速復号化のために使用されることができる。並列ウィンドウの異なる定義により、並列ウィンドウの数としてＫ’の任意の因数を使用することが可能である。ＱＰＰインターリーバに対して、インターリーバ・サイズＫ’のすべての因数は、並列Ｍの可能性のあるレベルである。これは、並列因数Ｍの広い範囲を可能にするによって復号化器の設計における柔軟性および拡張性を提供する。このように、復号化速度と複雑さとの間の良い譲歩は、システム（またはユーザ要素のクラス）の必要条件に基づいてなされることができる。
【００２９】
［インターリーバ・サイズＫ’の選択］
上で議論したように、インターリーバ・サイズ決定回路１０３は、与えられたＫに対するインターリーバ・サイズＫ’を決定する必要がある。この項は、ターボ符号インターリーバが定義されることが可能である限られた数のサイズ（つまり、Ｋ’）を選択する方法について記述している。先に示したように、フィラー挿入回路（パンクチャリングまたはレート・マッチング方法と共に）は、任意の情報ブロック・サイズＫ’を扱うために使用されることが可能である。一般に、インターリーバ・サイズ選択は、フィラー・ビットによる復号化の負担および性能劣化を考慮に入れなければならない。
【００３０】
入力ブロックを形成するために情報ブロックにパディングされたフィラー・ビットＫｆｉｌｌｅｒの数は、情報ブロック・サイズＫ’の小さい割合（たとえば、約１０〜１３％）に限定されることが望ましい。これは、隣接したインターリーバ・サイズ（つまり、隣接したＫ’値）間の差を限定することによって達成される（すべての利用可能なＫ’値が昇順でソートされると仮定する）。フィラー・ビットの数は、Ｋ’≧Ｋのような利用可能な最小のＫ’を選択することによって最小化される。フィラー・ビットの数は、Ｋｆｉｌｌｅｒ＝Ｋ’−Ｋである。しかしながら、必要に応じて、Ｋ’≧Ｋの他の利用可能な値も選択されることが可能である。
【００３１】
ＫｍｉｎとＫｍａｘとの間の情報サイズをカバーするように定義された次のサイズの組を考慮する。
Ｋ’＝ａｐ×ｆ（ｐｍｉｎ≦ｐ≦ｐｍａｘ；ｆｍｉｎ≦ｆ≦ｆｍａｘ） …（２）
ここで、ａは、整数であり、ｆは、ｆｍｉｎとｆｍａｘとの間の連続的な整数であり、ｐは、ｐｍｉｎとｐｍａｘとの間の整数値を取る（ａ＞１、ｐｍａｘ＞ｐｍｉｎ、ｐｍｉｎ＞１）。必要ではないが、Ｋｍｉｎ＝ａｐｍｉｎ×ｆｍｉｎ、およびＫｍａｘ＝ａｐｍａｘ×ｆｍａｘのようなこれらのパラメータを選択することができる一方で、必要でないことがある任意のサイズを廃棄する。一連の情報ブロック・サイズをカバーするために限定されたサイズの組を選択するこの方法は、片対数スライスと呼ばれる。与えられたサイズＫの情報ブロックに対して、サイズＫ’は、利用可能なインターリーバ・サイズの組と、情報ブロック・サイズＫ’とに基づいて選択される。
【００３２】
片対数スライスは、大きいダイナミック・レンジの信号を圧縮するのに利用される圧伸操作と同様である（たとえば、音声コーデックにおいて使用されるＡ−Ｌａｗおよびｍｕ−Ｌａｗ圧伸器）。片対数スライスの規則は、広範囲の情報ブロック・サイズをカバーするための効率的な設計を可能にする。
【００３３】
パラメータを選択する幾つかの方法については、ｆｍｉｎおよびｆｍａｘ値を選択する１つの方法は、Ｋ’値が、互いに並んだ隣接したｐに起因させることである（つまりａｐ×（ｆｍａｘ＋１）＝ａｐ＋１×ｆｍｉｎ）、したがって、
ｆｍａｘ＝ａ×ｆｍｉｎ−１
である。与えられたｐの値に対して、２つの隣接したブロック・サイズＫ’間の分離は、ａｐによって与えられ、それは、情報ブロック・サイズＫがグループｐであり、インターリーバ・サイズがＫ’に等しい場合に、最大ａｐ−１フィラー・ビットが加えられることを意味している。このように、情報ブロック・サイズＫに対するフィラー・ビットＫｆｉｌｌｅｒの割合は、下に示されるように拘束され、それは、ブロック・サイズＫが（ｐ，ｆｍｉｎ）によって与えられるサイズよりも僅かに大きいときに生じ、Ｋ’を使用して（ｐ，ｆｍｉｎ＋１）によって次のものが与えられる。
【００３４】
【数４】
これに代えて、隣接したｐに起因するＫ’値は、ａｐ×ｆｍａｘ＝ａｐ＋１×（ｆｍｉｎ−１）を介して互いに並ぶことができ、ｆｍａｘ＝ａ×（ｆｍｉｎ−１）を生じる。これは、同様のＫｆｉｌｌｅｒ／Ｋ限界を与えるであろう。したがって、片対数スライスのためのパラメータは、サポートされるブロック・サイズの範囲によって、さらに、フィラー・ビットの許容可能な割合で調整されることができる。ｆｍｉｎの選択は、次の２つの必要条件間の平衡を必要とする。
【００３５】
・ｆｍｉｎは、フィラー・ビットの割合を低減するように大きくあるべきである。
・ｆｍｉｎは、各のｐに対して定義されたブロック・サイズの数が、ｆｍａｘ＝ａ×ｆｍｉｎ−１であると仮定して、ｆｍａｘ−ｆｍｉｎ＋１＝（ａ−１）×ｆｍｉｎであるので、インターリーバのテーブルのサイズを限定するように小さくあるべきである。
【００３６】
片対数スライス法は、任意のブロック・サイズに対して非常に簡素であり、使用されるインターリーバ・サイズＫ’は、（２）式から容易に決定されることが可能である。
［インターリーバ・サイズの選択例］
３ＧＰＰ ＬＴＥについては、４０〜６１４４ビット間の各ブロック・サイズのＣＦインターリーバを定義することが必須ではない。限定された、または小さい組の良好に設計されたＣＦインターリーバは、すべてのブロック・サイズをカバーするのに十分である。定義されていないブロック・サイズ（つまり、ＣＦインターリーバが定義されていない）については、零パディング（つまり、フィラー・ビットの添付）は、上で記述したように、効果的に使用されることができる。
【００３７】
第１例として、テーブル１０５における３ＧＰＰの長期的な発展（ＬＴＥ）のための情報ブロック・サイズをカバーするのに適した１組のインターリーバは、上で記述した片対数スライス法に基づいて定義される。特に、次式は、２６４〜４０９６のサイズをカバーしている。
Ｋ’＝２ｐ×ｆ（ｐ＝３，４，５，６；ｆ＝３３，３４，…６４） …（３）
４０ビット〜６１４４ビットの全範囲をカバーするために、（３）式で定義されたＫ’の組は、８（ビット）のステップ・サイズで２６４〜４０に延長され、６４（ビット）のステップ・サイズで４０９６〜６１４４に拡張されている。１８８のインターリーバ・サイズのすべての組は、下のテーブル１にも列挙されている。
（３）式で特定されるサイズは、ａ＝２、ｐｍｉｎ＝３、ｐｍａｘ＝６、ｆｍｉｎ＝３３、ｆｍａｘ＝６４、ｆｍａｘ＝ａ×（ｆｍｉｎ−１）を有しており、したがって、ａｐ×ｆｍａｘ＝ａｐ＋１×（ｆｍｉｎ−１）であることを注記しておく。
【００３８】
［テーブル１］３ＧＰＰ ＬＴＥ用に定義されたインターリーバ・サイズＫ’の組。
【００３９】
【表１】
一旦１０５のインターリーバ・サイズが決定されると、ＣＦインターリーバは、各々のインターリーバ・サイズに対して設計されることが可能である。任意の情報ブロック・サイズＫが与えられると、回路１０３は、Ｋ以上の１０５からのＫ’の最小値を選択することによってＫに使用されるインターリーバ・サイズＫを決定することができる。その後、サイズＫ’のインターリーバに関連したパラメータは、インターリーバ・パラメータ１０５の格納手段からルックアップされ、それは、通信装置用のメモリに通常格納されている。
【００４０】
テーブル１に示されるサイズは、最小４０ビットおよび最大６１４４ビットを持ったＫ’に対して定義された例のみであることを注記しておく。さらに、簡素性について、サイズは、後部のまたは後部ビット構成要素符号を使用したそれらの間の差を考慮していない。ターボ符号化器が後部ビットでなされる場合には、７の倍数であるＫ’は使用されることができない。これらは、削除または修正されるであろう。最後に、付加的なインターリーバ・サイズは、インターリーバ間の間隔を減少させるために上のものに加えられることが可能である。たとえば、余分なインターリーバは、テーブル１における間隔１６でインターリーバ間に定義されることが可能であり、その結果、インターリーバは、より小さいＫ’に対するすべてのバイト間隔に対して定義される。
【００４１】
［ＱＰＰインターリーバの例］
３ＧＰＰの長期的な発展（ＬＴＥ）用のテーブル１におけるインターリーバ・サイズをカバーするのに適した７１ ＣＦ ＱＰＰインターリーバの部分集合がテーブル２に示されている。これらのインターリーバは、二次方程式の逆多項式を有しており、その結果、デインターリーバもまた、ＱＰＰである。加えて、３ＧＰＰの長期的な発展（ＬＴＥ）用のテーブル１におけるインターリーバ・サイズをカバーするのに適した１０ ＣＦ ＱＰＰインターリーバの部分集合がテーブル３に示されており、ここで、インターリーバは、次数が３または４の置換多項式であるデインターリーバを有している。
【００４２】
テーブル１におけるすべてのインターリーバ・サイズＫ’について、Ｋ’は、４の倍数である（実際には、Ｋ’は８の倍数である）。そのようなサイズに対して、２次の多項式π（ｉ）＝（ｆ１×ｉ＋ｆ２×ｉ２）ｍｏｄＫ’は、ｆ２がＫ’のすべての素因数で除算可能であり、ｆ１がＫ’の如何なる素因数でも除算可能でない場合にのみ、有効なインターリーバである。テーブル２およびテーブル３におけるすべてのインターリーバ・パラメータがこの条件を満足していることを示すことができる。
【００４３】
ＱＰＰインターリーバは、置換多項式の形式で表現することができるデインターリーバを有することを保証される、つまり、
【００４４】
【数５】
であるが、デインターリーバπ−１（ｘ）の次数ｍは、ｆ２のすべての素因数の中で最も高い順位と比べ少しも大きくないということだけが保証される。パラメータ（ｆ１，ｆ２）は、低いｍが望まれる場合には、より厳格な条件を満足しなければならない。このように、良い誤り訂正能力を提供する一方で低い次数のデインターリーバを有したＱＰＰインターリーバを設計するのは困難であることがある。
【００４５】
ターボ符号化により、インターリーバおよびデインターリーバの両方の複雑さが重要となる。デインターリーバの次数ｍは、ターボ復号化器の実装の複雑さに直接的に影響することがある。低い次数のデインターリーバは、より高い次数のデインターリーバよりも実装することがそれほど複雑ではない。したがって、ＱＰＰインターリーバの探索においては、
・好ましくは、二次方程式のデインターリーバを備えたインターリーバ（つまり、ｍ＝２、デインターリーバはＱＰＰでもある）が使用されるべきである。たとえば、テーブル２におけるＱＰＰインターリーバの各々は、ターボ符号化性能を妥協することなく、二次方程式のデインターリーバを有している。
【００４６】
・もし、或るサイズ用場合Ｋ’に対して、誤り訂正性能が著しく妥協される場合であって、インターリーバが二次方程式のデインターリーバを有していなければならない場合には、僅かに高い次数（たとえば、ｍ＝３または４）のデインターリーバを備えたインターリーバが代わりに使用されることができる。たとえば、テーブル３におけるＱＰＰインターリーバの各々は、次数が３または４のデインターリーバを有しており、良いターボ符号化性能を提供する。
【００４７】
デインターリーバに制約がまったくない場合には、テーブル２における長さＫ’のＱＰＰは、９程度の次数のデインターリーバを有することができ、テーブル３におけるものは、７程度の次数のデインターリーバを有することができると指摘されるべきである。
【００４８】
インターリーバ・パラメータ１０５のための格納手段は、Ｋ’がテーブル２またはテーブル３に含まれる場合には、テーブル２またはテーブル３のうちの少なくとも１つの列から得られるＫ’、ｆ１、ｆ２の値を使用してＱＰＰインターリーバ・パラメータを格納することが可能である。インターリーバ２０１は、Ｋ’がテーブル２またはテーブル３に含まれる場合には、テーブル２またはテーブル３のうちの少なくとも１つの列から得られるＫ’ｆ１、ｆ２の値を持ったＱＰＰインターリーバを使用することが可能である。
［テーブル２］次数が２の置換多項式であるデインターリーバを備えたＬＴＥ用に定義されたＱＰＰインターリーバの部分集合用のパラメータ（つまり、逆二次方程式）。
【００４９】
【表２】
［テーブル３］次数が３または４の置換多項式であるデインターリーバを備えたＬＴＥ用に定義されたＱＰＰインターリーバの部分集合用パラメータ。
【００５０】
【表３】
図３は、受信器３００のブロック図である。入力では、フィラー処理回路３０２は、チャネルを通じて（たとえば、無線で）送信されてくることがある信号ベクトルを受信する。その後、回路３０６は、インターリーバ・サイズＫ’を決定し、それは、上で議論したのと同様の方法でなされることができる（たとえば、格納装置３０８から、または演算を介してテーブルのルックアップを行なうことによって）。したがって、情報ブロック・サイズＫを与えられて、復号化器３０４は、符号化器１０１によって使用されたのと同一のインターリーバ・サイズＫ’を使用する。フィラー処理回路３０２は、受信した信号ベクトルおよびフィラー・ビット位置を適切に処理するために使用される（たとえば、フィラー・ビット位置が既知である場合には、対応するＬＬＲ量は、復号化中に非常に高い量に設定されることができる。その後、ターボ復号化器３０４は、復号化を行ない、長さＫ’の入力ブロックの推定ｕ（太字、チルダ）を得る。最後に、情報ブロック抽出回路３１０は、ｕ（太字、チルダ）から推定された情報ブロックを抽出する。フィラー処理回路３０２は、説明の容易さのためにターボ復号化器の外部に示されているが、これら２つは、実装の際に組み合わせられることができる。
【００５１】
図４は、図３のターボ復号化器３０４のブロック図である。明白なように、インターリーバ４０２およびデインターリーバ４０１は、復号化回路４０３と復号化回路４０４との間に存在する。反復復号化は、本技術において公知なもののように行われるが、先行技術の復号化器とは異なり、インターリーバ・サイズＫ’は、１組のサイズからのものである。ここで、１組のサイズは、Ｋ’＝ａｐ×ｆ（ｐｍｉｎ≦ｐ≦ｐｍａｘ；ｆｍｉｎ≦ｆ≦ｆｍａｘ）を含んでおり、ａは、整数であり、ｆは、ｆｍｉｎとｆｍａｘとの間の連続的な整数であり、ｐは、ｐｍｉｎとｐｍａｘとの間の整数値を取る（ａ＞１、ｐｍａｘ＞ｐｍｉｎ、ｐｍｉｎ＞１）。パラメータＫｆｉｌｌｅｒは、ターボ復号化器３０４には必要であるか、または、必要ではないことがあり、したがって、図４においては破線でラベル付けされている。
【００５２】
インターリーバ４０２は、置換π（ｉ）＝（ｆ１×ｉ＋ｆ２×ｉ２）ｍｏｄＫ’を利用することが可能であり、ここで、０≦ｉ≦Ｋ’−１は、インターリービング後のシンボル位置の連続したインデックスであり、π（ｉ）は、位置ｉに対応したインターリービング前のシンボル・インデックスであり、Ｋ’は、シンボルにおけるインターリーバ・サイズであり、ｆ１およびｆ２は、インターリーバを定義する因数である。Ｋ’、ｆ１、ｆ２の値は、Ｋ’がテーブル２またはテーブル３に含まれる場合には、テーブル２またはテーブル３の１列から得られる。デインターリーバ４０１は、インターリーバ４０２の逆関数を行なう。
【００５３】
図５は、送信器１００の動作を示すフローチャートである。論理フローは、ステップ５０１で開始され、ここでは、回路１０３は、１組のサイズからのものであるインターリーバ・サイズＫ’を決定する。ここで、１組のサイズは、Ｋ’＝ａｐ×ｆ（ｐｍｉｎ≦ｐ≦ｐｍａｘ；ｆｍｉｎ≦ｆ≦ｆｍａｘ）を含み、ａは、整数であり、ｆは、ｆｍｉｎとｆｍａｘとの間の連続的な整数であり、ｐは、ｐｍｉｎとｐｍａｘとの間の整数値を取る（ａ＞１、ｐｍａｘ＞ｐｍｉｎ、ｐｍｉｎ＞１）。
【００５４】
ステップ５０３では、フィラー挿入回路１０９は、サイズＫの情報ブロックを受信し、サイズＫの情報ブロックをサイズＫ’の入力ブロックｕ（太字）にパディングし、入力ブロックｕ（太字）を出力する。その後、インターリーバ２０１は、サイズＫ’の入力ブロックを（好ましくは、無競合インターリーバを使用して）インターリーブし（ステップ５０７）、サイズＫ’のインターリーブしたブロックを符号化回路２０３に送る（ステップ５０９）。最後に、ステップ５１１で、オリジナルの入力ブロックおよびインターリーブした入力ブロックが符号化される。
【００５５】
上で議論したように、入力ブロックをインターリーブするステップは置換π（ｉ）＝（ｆ１×ｉ＋ｆ２×ｉ２）ｍｏｄＫ’を使用するステップを含むことが可能である。ここで、０≦ｉ≦Ｋ’−１は、インターリービング後のシンボル位置の連続したインデックスであり、π（ｉ）は、位置ｉに対応したインターリービング前のシンボル・インデックスであり、Ｋ’は、シンボルにおけるインターリーバ・サイズであり、ｆ１およびｆ２は、インターリーバを定義する因数である。Ｋ’、ｆ１、ｆ２の値は、Ｋ’がテーブル２またはテーブル３に含まれる場合には、テーブル２またはテーブル３の１列から得られる。
【００５６】
図６は、図３の受信器の動作を示すフローチャートである。論理フローは、ステップ６０１で開始され、ここでは、回路３０６は、インターリーバ・サイズＫ’を決定する。ステップ６０３では、回路３０２は、フィラー・ビット情報を受信した信号ベクトルに加え、たとえば、フィラー・ビットおよびフィラー・ビット位置が公知の回路３０２である場合には、ターボ復号化器の入力におけるそれらの位置の対数尤度比（ＬＬＲ）を高い量に設定することが可能である。ステップ６０７では、ターボ復号化器は、サイズＫ’のインターリーバおよびデインターリーバを使用して復号化器の入力ブロックを復号化し、長さＫ’の入力ブロックの推定ｕ（太字、チルダ）を出力する。ステップ６０９では、情報ブロック抽出回路３１０は、長さＫ’の情報ブロックの推定を得るためにフィラー・ビットを削除する。最後に、ステップ６１１では、推定された情報ブロックが出力される。
【００５７】
本発明が特定の実施形態に関して特に示され且つ記述される一方で、当業者には、形態および詳細における様々な変更が本発明の精神および範囲から逸脱することなしにそこになされることが可能であることが理解されるであろう。一例においては、インターリーバのテーブルは、次のものを含む特別な場合をさらに扱うために強化されることが可能である。（ａ）任意の特別なブロック・サイズをカバーするように定義されるインターリーバ・サイズの付加的な組を使用することが（たとえば、フィラー・ビットなしで、または、より小さいフィラー・ビット数で）扱われなければならない。（ｂ）インターリーバ・サイズは、片対数スライスのサイズからの小さい値を加算または減算することによって僅かに調整されることができる。別の例においては、本発明は、バイナリ入力ターボ符号化器を仮定して上に記述したが、同一の原理は、ターボ符号化器が入力としてシンボルを取るときには適用されることができる。たとえば、デュオ・バイナリ・ターボ符号は、一度に２バイナリ・ビットのシンボルを取り、ターボ・インターリーバは、シンボルの順序を変更する（シンボル内のビットを交互に入れ替えるようにさらにスクランブルをかける）。そのような場合には、入力ブロック・サイズは、シンボルにおいて測定され、インターリーバ・サイズは、入力ブロックにおけるシンボルの数に等しい。別の例においては、上の記述は、インターリーバ・サイズおよびインターリーバ・パラメータがルックアップ・テーブルに格納されるものと仮定しているが、それらは、代数演算のような他の手段を介して決定されることも可能である。さらに別の例においては、上の記述は、ターボ符号を仮定しているが、本方法は、他のＦＥＣ手法（たとえば、低密度パリティ・チェック（ＬＤＰＣ）符号、リード・ソロモン（ＲＳ）符号などを含む）に適用されることも可能である。そのような変更は、次の請求の範囲内にあると意図されている。
【図面の簡単な説明】
【００５８】
【図１】送信器のブロック図である。
【図２】図１のターボ符号化器のブロック図である。
【図３】受信器のブロック図である。
【図４】図３のターボ復号化器のブロック図である。
【図５】図１の送信器の動作を示すフローチャートである。
【図６】図３の受信器の動作を示すフローチャートである。
【符号の説明】
【００５９】
１００ 送信器
１０１ ターボ符号化器
１０３ インターリーバ・サイズ決定回路
１０５ インターリーバ・パラメータ・テーブル
１０７ 送信器
１０９ フィラー挿入回路
２０１ インターリーバ
２０２，２０３ 符号化回路
３００ 受信器
３０２ フィラー処理回路
３０４ ターボ復号化器
３０６ インターリーバ・サイズ決定回路
３０８ インターリーバ・パラメータ格納装置
３１０ 情報ブロック抽出回路
４０１ デインターリーバ
４０２ インターリーバ
４０３，４０４ 復号化回路
【特許請求の範囲】
【請求項１】
ターボ符号化器を動作させる方法であって、前記方法は、
サイズＫ’の入力ブロックを受信すること、および
符号語ブロックを得るために入力ブロックおよびインターリーブした入力ブロックを符号化することを含み、
前記入力ブロックは、サイズＫ’のインターリーバおよび置換π（ｉ）＝（ｆ１×ｉ＋ｆ２×ｉ２）ｍｏｄＫ’を使用してインターリーブされ、ここで、０≦ｉ≦Ｋ’−１は、インターリービング後のシンボル位置の連続したインデックスであり、π（ｉ）は、位置（ｉ）に対応したインターリービング前のシンボル・インデックスであり、Ｋ’は、シンボルにおけるインターリーバ・サイズであり、ｆ１およびｆ２は、前記インターリーバを定義する因数であり、Ｋ’、ｆ１、ｆ２の値は、次表のうちの少なくとも１つの列から得られる、方法。
【表１】
【請求項２】
チャネルを通じて符号語ブロックを送信することをさらに含む、請求項１記載の方法。
【請求項３】
前記インターリーバは、二次方程式のデインターリーバを含んでいる、請求項２記載の方法。
【請求項４】
ターボ符号化器を動作させる方法であって、前記方法は、
サイズＫ’の入力ブロックを受信すること、および
符号語ブロックを得るために入力ブロックおよびインターリーブした入力ブロックを符号化することを含み、
前記入力ブロックは、サイズＫ’のインターリーバおよび置換π（ｉ）＝（ｆ１×ｉ＋ｆ２×ｉ２）ｍｏｄＫ’を使用してインターリーブされ、ここで、０≦ｉ≦Ｋ’−１は、インターリービング後のシンボル位置の連続したインデックスであり、π（ｉ）は、位置ｉに対応したインターリービング前のシンボル・インデックスであり、Ｋ’は、シンボルにおけるインターリーバ・サイズであり、ｆ１およびｆ２は、前記インターリーバを定義する因数であり、Ｋ’、ｆ１、ｆ２の値は、次表のうちの少なくとも１つの列から得られる、方法。
【表２】
【請求項５】
前記インターリーバは、次数が３または４のデインターリーバを含んでいる、請求項４記載の方法。
【請求項６】
ターボ符号化器を動作させるための装置であって、前記装置は、
１組のサイズからインターリーバ・サイズＫ’を決定するインターリーバ・サイズ決定回路と、
サイズＫの入力ブロックを受信し、該サイズＫの入力ブロックをサイズＫ’の入力ブロックにパディングするフィラー挿入回路と、
前記サイズＫ’の入力ブロックをインターリーブするインターリーバと
を備え、
該インターリーバは、置換π（ｉ）＝（ｆ１×ｉ＋ｆ２×ｉ２）ｍｏｄＫ’を使用し、ここで、０≦ｉ≦Ｋ’−１は、インターリービング後のシンボル位置の連続したインデックスであり、π（ｉ）は、位置ｉに対応したインターリービング前のシンボル・インデックスであり、Ｋ’は、シンボルにおけるインターリーバ・サイズであり、ｆ１およびｆ２は、前記インターリーバを定義する因数であり、Ｋ’、ｆ１、ｆ２の値は、次表のうちの少なくとも１つの列から得られる、装置。
【表３】
【請求項７】
符号語ブロックを得るために、前記入力ブロックおよび前記インターリーブした入力ブロックを符号化する符号化器をさらに備える、請求項６記載の装置。
【請求項８】
ターボ符号化器を動作させるための装置であって、前記装置は、
１組のサイズからインターリーバ・サイズＫ’を決定するインターリーバ・サイズ決定回路と、
サイズＫの入力ブロックを受信し、該サイズＫの入力ブロックをサイズＫ’の入力ブロックにパディングするフィラー挿入回路と、
前記サイズＫ’の入力ブロックをインターリーブするインターリーバと
を備え、
該インターリーバは、置換π（ｉ）＝（ｆ１×ｉ＋ｆ２×ｉ２）ｍｏｄＫ’を使用し、ここで、０≦ｉ≦Ｋ’−１は、インターリービング後のシンボル位置の連続したインデックスであり、π（ｉ）は、位置ｉに対応したインターリービング前のシンボル・インデックスを含み、Ｋ’は、シンボルにおけるインターリーバ・サイズであり、ｆ１およびｆ２は、前記インターリーバを定義する因数であり、Ｋ’、ｆ１、ｆ２の値は、次表のうちの少なくとも１つの列から得られる、装置。
【表４】
【請求項９】
符号語ブロックを得るために、前記入力ブロックおよび前記インターリーブした入力ブロックを符号化する符号化器をさらに備える、請求項８記載の装置。
【請求項１０】
前記インターリーバは、次数が３または４のデインターリーバを有する、請求項９記載の装置。
【請求項１】
ターボ符号化器を動作させる方法であって、前記方法は、
サイズＫ’の入力ブロックを受信すること、および
符号語ブロックを得るために入力ブロックおよびインターリーブした入力ブロックを符号化することを含み、
前記入力ブロックは、サイズＫ’のインターリーバおよび置換π（ｉ）＝（ｆ１×ｉ＋ｆ２×ｉ２）ｍｏｄＫ’を使用してインターリーブされ、ここで、０≦ｉ≦Ｋ’−１は、インターリービング後のシンボル位置の連続したインデックスであり、π（ｉ）は、位置（ｉ）に対応したインターリービング前のシンボル・インデックスであり、Ｋ’は、シンボルにおけるインターリーバ・サイズであり、ｆ１およびｆ２は、前記インターリーバを定義する因数であり、Ｋ’、ｆ１、ｆ２の値は、次表のうちの少なくとも１つの列から得られる、方法。
【表１】
【請求項２】
チャネルを通じて符号語ブロックを送信することをさらに含む、請求項１記載の方法。
【請求項３】
前記インターリーバは、二次方程式のデインターリーバを含んでいる、請求項２記載の方法。
【請求項４】
ターボ符号化器を動作させる方法であって、前記方法は、
サイズＫ’の入力ブロックを受信すること、および
符号語ブロックを得るために入力ブロックおよびインターリーブした入力ブロックを符号化することを含み、
前記入力ブロックは、サイズＫ’のインターリーバおよび置換π（ｉ）＝（ｆ１×ｉ＋ｆ２×ｉ２）ｍｏｄＫ’を使用してインターリーブされ、ここで、０≦ｉ≦Ｋ’−１は、インターリービング後のシンボル位置の連続したインデックスであり、π（ｉ）は、位置ｉに対応したインターリービング前のシンボル・インデックスであり、Ｋ’は、シンボルにおけるインターリーバ・サイズであり、ｆ１およびｆ２は、前記インターリーバを定義する因数であり、Ｋ’、ｆ１、ｆ２の値は、次表のうちの少なくとも１つの列から得られる、方法。
【表２】
【請求項５】
前記インターリーバは、次数が３または４のデインターリーバを含んでいる、請求項４記載の方法。
【請求項６】
ターボ符号化器を動作させるための装置であって、前記装置は、
１組のサイズからインターリーバ・サイズＫ’を決定するインターリーバ・サイズ決定回路と、
サイズＫの入力ブロックを受信し、該サイズＫの入力ブロックをサイズＫ’の入力ブロックにパディングするフィラー挿入回路と、
前記サイズＫ’の入力ブロックをインターリーブするインターリーバと
を備え、
該インターリーバは、置換π（ｉ）＝（ｆ１×ｉ＋ｆ２×ｉ２）ｍｏｄＫ’を使用し、ここで、０≦ｉ≦Ｋ’−１は、インターリービング後のシンボル位置の連続したインデックスであり、π（ｉ）は、位置ｉに対応したインターリービング前のシンボル・インデックスであり、Ｋ’は、シンボルにおけるインターリーバ・サイズであり、ｆ１およびｆ２は、前記インターリーバを定義する因数であり、Ｋ’、ｆ１、ｆ２の値は、次表のうちの少なくとも１つの列から得られる、装置。
【表３】
【請求項７】
符号語ブロックを得るために、前記入力ブロックおよび前記インターリーブした入力ブロックを符号化する符号化器をさらに備える、請求項６記載の装置。
【請求項８】
ターボ符号化器を動作させるための装置であって、前記装置は、
１組のサイズからインターリーバ・サイズＫ’を決定するインターリーバ・サイズ決定回路と、
サイズＫの入力ブロックを受信し、該サイズＫの入力ブロックをサイズＫ’の入力ブロックにパディングするフィラー挿入回路と、
前記サイズＫ’の入力ブロックをインターリーブするインターリーバと
を備え、
該インターリーバは、置換π（ｉ）＝（ｆ１×ｉ＋ｆ２×ｉ２）ｍｏｄＫ’を使用し、ここで、０≦ｉ≦Ｋ’−１は、インターリービング後のシンボル位置の連続したインデックスであり、π（ｉ）は、位置ｉに対応したインターリービング前のシンボル・インデックスを含み、Ｋ’は、シンボルにおけるインターリーバ・サイズであり、ｆ１およびｆ２は、前記インターリーバを定義する因数であり、Ｋ’、ｆ１、ｆ２の値は、次表のうちの少なくとも１つの列から得られる、装置。
【表４】
【請求項９】
符号語ブロックを得るために、前記入力ブロックおよび前記インターリーブした入力ブロックを符号化する符号化器をさらに備える、請求項８記載の装置。
【請求項１０】
前記インターリーバは、次数が３または４のデインターリーバを有する、請求項９記載の装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２００８−２１９８９２（Ｐ２００８−２１９８９２Ａ）
【公開日】平成２０年９月１８日（２００８．９．１８）
【国際特許分類】
【出願番号】特願２００８−４７０３７（Ｐ２００８−４７０３７）
【出願日】平成２０年２月２８日（２００８．２．２８）
【出願人】（３９０００９５９７）モトローラ・インコーポレイテッド (649)
【氏名又は名称原語表記】ＭＯＴＯＲＯＬＡ ＩＮＣＯＲＰＯＲＡＴＥＤ
【Ｆターム（参考）】
【公開日】平成２０年９月１８日（２００８．９．１８）
【国際特許分類】
【出願日】平成２０年２月２８日（２００８．２．２８）
【出願人】（３９０００９５９７）モトローラ・インコーポレイテッド (649)
【氏名又は名称原語表記】ＭＯＴＯＲＯＬＡ ＩＮＣＯＲＰＯＲＡＴＥＤ
【Ｆターム（参考）】
[ Back to top ]