ベクトル化されたターボ復号器のためのデータ・インターリーブ回路および方法
【課題】複数のプロセッサを用いた並列復号化におけるメモリ・アクセスの効率を向上する。
【解決手段】Ｍ個のＷ値ウィンドウを含むデータ・ブロックをインターリーブするためのデータ・インターリーブ回路（３０６）および方法が、ウィンドウ内インデックスｗとＭ個の要素を有するウィンドウ間置換ベクトルｍとを生成するためのインデックス生成器（５００）と、ウィンドウ内インデックスｗを有するＭ個のデータ値をメモリから受信するように動作可能であり、さらに、ウィンドウ間置換ベクトルｍに従ってＭ個のデータ値を並べ直して、並べ直したデータ値を出力するように動作可能なウィンドウ間置換回路（５０４）とを備える。インデックス生成器は、置換多項式に従ってウィンドウ内インデックスｗとウィンドウ間置換ベクトルｍとを生成する再帰回路を含む。１つの応用例では、並べ直したデータ値をターボ復号器のＭ個の並列プロセッサに送る。
【解決手段】Ｍ個のＷ値ウィンドウを含むデータ・ブロックをインターリーブするためのデータ・インターリーブ回路（３０６）および方法が、ウィンドウ内インデックスｗとＭ個の要素を有するウィンドウ間置換ベクトルｍとを生成するためのインデックス生成器（５００）と、ウィンドウ内インデックスｗを有するＭ個のデータ値をメモリから受信するように動作可能であり、さらに、ウィンドウ間置換ベクトルｍに従ってＭ個のデータ値を並べ直して、並べ直したデータ値を出力するように動作可能なウィンドウ間置換回路（５０４）とを備える。インデックス生成器は、置換多項式に従ってウィンドウ内インデックスｗとウィンドウ間置換ベクトルｍとを生成する再帰回路を含む。１つの応用例では、並べ直したデータ値をターボ復号器のＭ個の並列プロセッサに送る。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的にデータ処理回路に関し、特に「ターボ符号」を用いる通信システム用のデータ処理回路に関する。
【背景技術】
【０００２】
通信システムにおいて、送信信号（たとえば無線による）は、フェージング、ジャミング、および他の、信号内にエラーを導入させ得る要素の影響を受けやすいことがある。送信前に信号を符号化することは、送信中に導入されたエラーを、受信部において信号を復号化したときに検出および補正できるようにすることによって、チャンネル・ノイズ、フェージング、およびジャミングの影響を抑えることに役立つ。
【０００３】
「ターボ符号」は、符号化方式におけるブレイクスルーであると認められており、送信中に生じるエラーに対する強力な抵抗を実現するものである。それらは、並列連結畳込み符号（ｐａｒａｌｌｅｌ ｃｏｎｃａｔｅｎａｔｅｄ ｃｏｎｖｏｌｕｔｉｏｎａｌ ｃｏｄｅｓ：ＰＣＣＣ）または直列連結畳込み符号（ｓｅｒｉａｌ ｃｏｎｃａｔｅｎａｔｅｄ ｃｏｎｖｏｌｕｔｉｏｎａｌ ｃｏｄｅｓ：ＳＣＣＣ）として実施することができる。ターボ符号によって、符号化利得が高くなり、ビット・エラー率が１０−７と低くなる。ターボ符号は、エラー補正が優れているため、信号対雑音比（ＳＮＲ）が一般的に低い応用例（たとえば、無線通信）において非常に有用である。
【０００４】
図１に、従来のターボ符号器の例を示す。ターボ符号器１００が受信した信号１０２は、第１の再帰的組織畳み込み（ｒｅｃｕｒｓｉｖｅ ｓｙｓｔｅｍａｔｉｃ ｃｏｎｖｏｌｕｔｉｏｎａｌ：ＲＳＣ）符号器１０４に送られるとともに、インターリーバ１０６を介して第２の畳み込み符号器１０８に送られる。２つの畳み込み符号器によってターボ符号の成分符号が得られる。インターリーバ１０６は、データ・ストリームの順序を、データ・ストリームを第２の畳み込み符号器に入力する前に変える。また一方のデータ・ストリームをインターリーブするので、結果として生じる符号は、ターボ符号器から得られる高い符号化利得を提供する時間変化特性を有するものとなる。符号化された信号１１０は、変調されて、通信チャネル上で送信される。
【０００５】
図２に、従来のターボ復号器の例を示す。ターボ復号器２００は、復調信号２０２を通信チャネルから受信する。信号２０２は、第１の軟入力、軟出力（ｓｏｆｔ−ｉｎｐｕｔ，ｓｏｆｔ ｏｕｔｐｕｔ：ＳＩＳＯ）復号器２０４に送られるとともに、インターリーバ２０６を介して第２のＳＩＳＯ復号器２０８に送られる。第２のＳＩＳＯ復号器２０８は信号２０２の成分も受信する。第１のＳＩＳＯ復号器２０４の出力を、インターリーバ２１０を介して第２のＳＩＳＯ復号器２０８に送り、第２のＳＩＳＯ復号器の出力を、デ・インターリーバ２１２を介して第１のＳＩＳＯ復号器２０４に送ることによって、反復復号を可能にする。動作時には、受信したデータ・ブロック（データ・フレームとも言う）を一度処理した後に、複数回再循環して、所望の符号化利得を達成する。ターボ符号は、エラーに対する高い抵抗を示すが、多くの実際の応用にとって理想的に適しているわけではない。なぜならば、ターボ符号器がインターリーバ（遅延を導入する）を用いる結果、待ち時間が極端に長くなり、またターボ復号器の反復アルゴリズムがコンピュータ的に複雑であるからである。ターボ符号は通常、大きなブロック・サイズ（たとえば、＞５０００ビット）を伴って動作する。反復復号を容易にするために、ブロック全体に対する軟入力をメモリに格納しなければならない。言い換えれば、各復号化段階において、軟入力を繰り返して用いて更新する。その結果、ターボ復号器はメモリ集約的（ｍｅｍｏｒｙ ｉｎｔｅｎｓｉｖｅ）となるため、ターボ復号器は、実用的でないかまたは応用例によっては高価すぎることになる。
【０００６】
一般的に、連続したターボ復号器の待ち時間は、特別にデザインされた高速のハードウェアを用いてターボ復号器を実現することによって、わずかに改善される場合がある。しかし、費用が増加し、デバイスが複雑になり、加えて消費電力が増加する（多くの低電力無線デバイスにおいては容認できない場合がある）という犠牲を払って得られるのは、待ち時間が漸進的に改善されるということのみである。
【０００７】
ターボ復号化の長い待ち時間に対処する代替的なアプローチは、並列復号化アーキテクチャを用いることである。並列復号化によって、スループットおよび待ち時間を大きく改善することができる。２つの基本的な並列化方式を利用することができる。並列処理は、複数の受信信号を同時に復号化することか、または受信信号ブロックをサブ・ブロックに分割して、サブ・ブロックを複数の並列プロセッサによって並列に復号化することによって、実現される場合がある。スループットおよび待ち時間は、並列復号化を用いて小さくなる場合があるが、大容量メモリの要求はそうはならない。加えて、ハードウェアもより複雑になり、コストも増加する。したがって、メモリ効率が良くてハードウェア（または面積）効率の良い並列化方式が、ターボ符号を実際に具体化するためには必要である。
【０００８】
並列処理に伴う問題の１つはメモリ・アクセスの問題である。特に、インターリーバの存在は、複数の並列プロセッサによってメモリが順序が狂ったアドレス指定をされざるを得ないことを意味する。２つ以上のプロセッサが、読み出しまたは書き込みアクセスを同じメモリに対して同じクロック周期で行なう必要があるときに、メモリ競合が生じる。ある種類の無競合（ｃｏｎｔｅｎｔｉｏｎ ｆｒｅｅ：ＣＦ）インターリーバの場合、メモリ競合はない。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
二次置換多項式（ｑｕａｄｒａｔｉｃ ｐｅｒｍｕｔａｔｉｏｎ ｐｏｌｙｎｏｍｉａｌ：ＱＰＰ）ターボ・インターリーバ（ロング・ターム・エボリューション（Ｌｏｎｇ Ｔｅｒｍ Ｅｖｏｌｕｔｉｏｎ：ＬＴＥ）規格において採用されている）は、ＣＦインターリーバである。ＬＴＥシステムでは高データ・レートが要求されるため、ターボ復号器は、複数のプロセッサを用いた並列復号化を利用する必要がある。したがって、ＱＰＰをマルチ・プロセッサ・ターボ復号器に適用することが求められている。
【図面の簡単な説明】
【００１０】
【図１】典型的な従来のターボ符号器のブロック図である。
【図２】典型的な従来のターボ復号器のブロック図である。
【図３】本発明のいくつかの実施形態による復号器回路の一部のブロック図である。
【図４】本発明のいくつかの実施形態による典型的なデータ置換を示す図である。
【図５】本発明のいくつかの実施形態による典型的なインターリーバのブロック図である。
【図６】本発明のいくつかの実施形態による典型的な多項式再帰回路のブロック図である。
【図７】本発明のいくつかの実施形態による典型的な再規格化可能な加算器のブロック図である。
【図８】本発明のいくつかの実施形態による基数４のターボ復号器に対する典型的なインターリーバのブロック図である。
【図９】本発明のいくつかの実施形態による単一の置換回路を用いた典型的なターボ復号器回路のブロック図である。
【図１０】本発明のいくつかの実施形態による典型的なメモリ割り当てを示す図である。
【図１１】本発明のいくつかの実施形態による典型的なメモリ割り当てを示す図である。
【図１２】本発明のいくつかの実施形態による２つの置換回路を用いた典型的なターボ復号器回路のブロック図である。
【図１３】本発明のいくつかの実施形態による典型的な基数Ｗの加算器のブロック図である。
【図１４】本発明のいくつかの実施形態による典型的な基数Ｗの多項式再帰回路のブロック図である。
【図１５】本発明のいくつかの実施形態による基数Ｗの多項式再帰回路を用いた直接型インデックス生成器のブロック図である。
【図１６】本発明のいくつかの実施形態による基数Ｗの多項式再帰回路を用いた間接型インデックス生成器のブロック図である。
【図１７】本発明のいくつかの実施形態によるインターリーブ後順序でデータ値にアクセスするための方法のフロー・チャートである。
【発明を実施するための形態】
【００１１】
添付の図では、個々の図の全体に渡って、同様の参照数字は同一のまたは機能的に同様の要素を指している。また添付の図は、以下の詳細な説明とともに本明細書に取り入れられて本明細書の一部を構成するとともに、さらに種々の実施形態を例示し、本発明にすべて従う種々の原理および優位性を説明する働きをする。
【００１２】
当業者であれば分かるように、図における要素は、簡潔および明瞭を目的として例示されており、必ずしも一定の比率で描かれているわけではない。たとえば、本発明の種々の実施形態の理解の向上を助けるために、図中のいくつかの要素の寸法は他の要素に対して誇張されている場合がある。
【００１３】
本発明による実施形態を詳細に説明する前に、以下のことに注意されたい。すなわち、実施形態は主に、ターボ復号器におけるインターリーバに関係する方法工程および装置構成要素の組み合わせにあるということである。したがって、装置構成要素よび方法工程は、適切であれば図面中で従来の符号を用いて表して、本発明の実施形態を理解するのに適切な特定の詳細のみを示すようにしている。これは、本明細書の説明の利益を受ける当業者には容易に明らかである詳細によって、開示が不明瞭になることがないようにするためである。
【００１４】
この文献において、関係語たとえば第１および第２、最上部および最下部などは単に、ある存在または行為を別の存在または行為と区別するために用いる場合があり、その場合、このような存在間または行為間のこのような関係または順序の実際のものを必ずしも必要としないし意味することもない。用語「含む」、「含んでいる」またはこれらの他のどんな変形も、包括的に含めることに及んでいることが意図されている。すなわち、要素のリストを含むプロセス、方法、物品、または装置には、これらの要素が含まれているだけでなく、明白にはリストにされていない他の要素、またはこのようなプロセス、方法、物品、もしくは装置に固有の他の要素が、含まれていても良い。要素が「含む」の後にきた場合、これは、要素を含むプロセス、方法、物品、または装置に、同じ要素がさらに存在することを排除するものではないことを、さらなる制約を伴うことなく行なうものである。
【００１５】
本明細書に記載した本発明の実施形態は、プログラマブル論理回路たとえばフィールド・プログラマブル・ゲート・アレイ（ｆｉｅｌｄ ｐｒｏｇｒａｍｍａｂｌｅ ｇａｔｅ ａｒｒａｙ：ＦＰＧＡ）または従来のプロセッサに、前記回路またはプロセッサを制御する一意の格納されたプログラム命令であって、本明細書に記載したインターリービングの機能の一部、ほとんど、またはすべて実現するプログラム命令を伴うものを含む場合があることが理解される。あるいは、一部または全部の機能を、格納されたプログラム命令を持たない状態機械によって実施することができるか、または各機能もしくはいくつかの機能のある組み合わせをカスタム・ロジックとして実施する１つもしくは複数の特定用途向け集積回路（ａｐｐｌｉｃａｔｉｏｎ ｓｐｅｃｉｆｉｃ ｉｎｔｅｇｒａｔｅｄ ｃｉｒｃｕｉｔ：ＡＳＩＣ）において実施することができる。当然のことながら、これらのアプローチの組み合わせを用いることができる。このようにして、これらの機能を得るための方法および手段について本明細書において説明している。さらに、以下のことが予想される。すなわち、おそらくかなりの努力および多くのデザイン選択が、たとえば、利用できる時間、最近の技術、および経済的考慮によって誘導されるにもかかわらず、本明細書で開示される考え方および原理によって導かれれば、当業者は、このようなソフトウェア命令およびプログラムおよびＩＣを最小限の実験で容易に作成することができるということである。
【００１６】
本発明の実施形態は、並列またはベクトル化されたターボ復号器におけるメモリ・アクセスに関する。したがって、本発明の実施形態は一般的にデータ処理回路に関し、特に「ターボ符号」を用いる通信システム用のデータ処理回路に関する。
【００１７】
図３は、本発明のいくつかの実施形態による復号器回路３００の一部のブロック図である。図３を参照して、回路３００はデータ・メモリ３０２を備える。データ・メモリ３０２は、復号器３０４のためのデータ格納を行なう。インターリーバ回路３０６が、メモリ３０２からのデータを復号器３０４へ転送するように動作可能である。インターリーバ回路３０６は、インデックスの順序列によって規定される置換に従ってデータのシーケンスを置換するデバイスである。典型的な応用例（たとえばターボ復号化）では、インターリーバは、メモリ内のデータへのランダム・アクセスを行なうためのアドレス３０８を生成して、対応するデータ３１０をメモリから受信する。生成されたアドレスは通常、インデックスの順序列に対応するため、この文献では、用語「インデックス」と「アドレス」とを交換可能に用いる。データ３１２は、自然順序またはインターリーブ後順序（ｉｎｔｅｒｌｅａｖｅｄ ｏｒｄｅｒ）で、復号器３０４に送られる。
【００１８】
復号器３０４は、データを復号化するために並列に動作する多くの処理要素３１４を備える並列プロセッサまたはベクトル化されたプロセッサである。各処理要素は、受信したデータ・ブロックのサブ・セクション、サブ・ブロック、または「ウィンドウ」上で動作する。インターリーバは、メモリからのデータをウィンドウ間で置換するように動作する。用語「ベクトル化される（ｖｅｃｔｏｒｉｚｅｄ）」を用いるのは、インターリーバによってデータの格納およびフェッチがベクトルとして（すなわち、別個のグループとして）できる場合である。復号器から出力されたデータ３１６は、メモリ３０２内に格納しても良いし、他の処理モジュールへ出力しても良い。
【００１９】
インターリーバ３０６を、種々のベクトル化されたターボ復号器アーキテクチャにおいて具体化しても良く、ウィンドウ間置換のシーケンスを生成するための論理回路を単純にする設計基準について開示する。
【００２０】
本発明の一実施形態においては、インターリーバは、ベクトル化されたターボ復号器における二次置換多項式（ＱＰＰ）インターリーバである。この実施形態においては、インターリーバによって、より高次の置換多項式を正または逆の順序で再帰的に生成することが行なわれる。一実施形態においては、インターリーバを論理回路として実施して、アドレスπ（ｘ）＝ｍｘＷ＋ｗｘをそのｍｘおよびｗｘ成分に自動的に分解する。加えて、インターリーバを用いて、ベクトル化されたターボ復号化を行なうために必要な「ウィンドウ内」アドレスと「ウィンドウ間」置換とを生成しても良い。
【００２１】
インターリーバを、第３世代（３Ｇ）無線アクセス技術のロング・ターム・エボリューション（ＬＴＥ）（以後、「ＬＴＥ」と言う）に対して提案されるターボ復号器ハードウェアにおいて用いても良い。
【００２２】
ＱＰＰ置換は、多項式によって生成される置換の二次の場合である。最初に、置換多項式の導入処理について説明する。処理は一般的である。なぜならば、ターボ復号器は、形式上は多項式であるが必ずしも二次ではない逆置換を効果的に用いることができるからである。次に、典型的なベクトル化されたターボ復号化アーキテクチャについて説明する。このアーキテクチャからインターリーバの機能上の要求が推論される。インターリーバの機能の１つは、置換を「ウィンドウ内」アドレスと「ウィンドウ間」置換とに分解することである。ウィンドウ間置換のシーケンスの生成を単純化できる設計基準についても説明する。
【００２３】
ｎ次の置換多項式は以下の形式である。
【００２４】
【数１】
ここで、ｘおよびｆｉは整数である。ｘを０からＫ−１まで増加させると、多項式Ｐｎ（ｘ）によって置換が生成される。多項式Ｐｎ（ｘ）は通常、置換されたシーケンスの位置ｘにおける数量の置換前位置として解釈される。ｆｉに対していくつか制約（ここでは扱わない）を設けることによって、Ｐｎ（ｘ）によって置換が生成されることを確実にする。ＬＴＥの場合、ターボ・インターリーバは二次多項式（すなわちｎ＝２）を用いる。簡単にするために、この文献の残りの部分では一般に、ｍｏｄ Ｋの表記法を省き、すべての量が、特に断らない限り、モジュロＫで換算されていると暗黙的に仮定する。
【００２５】
逆置換Ｐｍ−１（ｘ）、ここで、
【００２６】
【数２】
も、以下の多項式の形である。
【００２７】
【数３】
一般的に、ｎ≠ｍである。ＱＰＰの場合、ｆ２は、Ｋのすべての素因数（ｐｒｉｍｅ ｆａｃｔｏｒ）をある次数（ｏｒｄｅｒ）まで含まなければならない。その結果、ｍは、ｆ２のすべての素因数の最大次数（ｌａｒｇｅｓｔ ｏｒｄｅｒ）より大きくなることはない。
【００２８】
復号器スループットは、ベクトル化を通して増加させることができる。ベクトル化された復号器では、長さＫのデータ・ブロックを、Ｍ個の通常は非オーバーラッピングの長さＷの「ウィンドウ」に分割する（Ｋ＝ＭＷ）。これらを、Ｍ個のプロセッサによって同期して処理する。
【００２９】
図４に、本発明のいくつかの実施形態による典型的なデータ置換を示す。図４に示すのは、長さＫ＝４０のデータ・ブロック４０２である。ブロック４０２を、Ｍ＝４で長さ１０のウィンドウ４０４に分割してある。データを４個のプロセッサ４０６によって処理する。ｉ番目のプロセッサ（０≦ｉ≦３）によって、データ・ブロック４０２内での位置１０ｉ〜１０ｉ＋９におけるデータを処理する。
【００３０】
反復処理であるので、ターボ復号器は、順次的（または「自然（ｎａｔｕｒａｌ）」）順序および置換後順序（ｐｅｒｍｕｔｅｄ ｏｒｄｅｒ）の両方で、データを処理できなければならない。図４では、アレイ４０２は、データのシーケンスを自然順序で示し、アレイ４０８は、シーケンスを置換後またはインターリーブ後順序で示す。図４では、プロセッサ０が、データ位置０、１、２、…、９におけるデータ、および位置０、１７、３４、１１、２８、５、２２、３９、１６、３３におけるデータを、順次に処理できなければならないということを示している。同様に、プロセッサ１が、位置１０、１１、１２、…、１９におけるデータ、および位置１０、２７、４、２１、３８、１５、３２、９、２６、３におけるデータを、順次に処理できなければならない。
【００３１】
ベクトル化と置換後順序処理との組み合わせによって、メモリ管理の問題が持ち込まれる。なぜならば、複数のプロセッサが、メモリからのデータを、メモリ・アクセスに対して互いに干渉することも競合することもなく、置換後順序で同時にフェッチしなければならないからである。
【００３２】
図４の「インターリーブ後データ」列における置換アドレスは、実際には、ＱＰＰ３７ｘ＋２Ｏｘ２ ｍｏｄ ４０によって生成される。図４において、各自然順序および各置換アドレスは、形式ｍ１０＋ｗに分解されている。ここで、ｗは「ウィンドウ内アドレス」列の中にあり、ｍは「ウィンドウ番号」列の中にある。以後、アドレスは一般的に形式ｍＷ＋ｗであると考え、ｍおよびｗを、それぞれアドレスのｍおよびｗ成分であると言う。置換アドレスに対して、ｍ成分は、データが由来する置換前のシーケンスにおけるウィンドウを示し、ｗ成分は、データが由来するウィンドウ内での相対位置を示す。
【００３３】
図４の置換アドレス列４０８は、任意のステップにおいて、すべてのプロセッサが同じウィンドウ内アドレス（列４１０）におけるデータを処理することを示している。たとえば、置換後順序処理の場合、第１のステップにおいて、すべてのプロセッサはウィンドウ内アドレス０におけるデータを処理する。第２のステップにおいて、すべてのプロセッサはウィンドウ内アドレス７におけるデータを処理する。さらに、置換後順序処理の場合に、各ステップにおいてウィンドウ間置換があることに注意されたい（列４１２）。ｍｉ＝（ｍ０，ｍ１，ｍ２，ｍ３）ｉ（０≦ｍ０，ｍ１，ｍ２，ｍ３≦３）が、ｉ番目の処理ステップ（０≦ｉ≦９）におけるプロセッサ０、１、２、および３に対する置換されたアドレスのｍ成分をそれぞれ示すものとする。各ｍｉは、ステップｉに対するウィンドウ間置換である。表１に、これらのウィンドウ間置換をｉの関数として列挙する。ちなみに、各ｍｉ（１≦ｉ≦９）はｍ０の循環シフトであることに注意されたい。これは一般的に置換多項式に当てはまるわけではないが、特性が保たれる条件を以下に導き出す。
【００３４】
【表１】
結果として、この例におけるデータは１０×４Ｂのメモリに格納することができる。ここでＢはデータ幅（ビット）である。
【００３５】
図５は、本発明のいくつかの実施形態による典型的なインターリーバのブロック図である。図５を参照して、インターリーバは、インデックス生成器５００、メモリ５０２、およびウィンドウ間置換回路５０４を備える。１０×４Ｂのメモリ５０２は、４０個のデータ・サンプルのブロックを収容している。メモリの各行は、同じウィンドウ内インデックスｗのデータ要素を収容し、一方で、各列は、同じウィンドウ・インデックスｍのデータ要素を収容している。自然順序でデータを処理するとき、プロセッサ０はデータ値の第１の列を処理する。インターリーブ後順序でデータを処理するとき、プロセッサ０は、下線を引いた数字を伴うデータ値をウィンドウ内順序｛０，７，４，１，８，５，２，９，６，３｝で処理する。動作時には、インデックス生成器５００が、ウィンドウ内インデックス５０６（ｗ）を生成し、これをメモリ・アクセス・コントローラ５０８に送る。この例では、メモリ・アクセス・コントローラ５０８は、メモリ５０２の対応する行における４つのデータ要素をウィンドウ間置換回路５０４に送る行セレクタを備える。またインデックス生成器５００は、４要素の置換ベクトル５１０（ｍ）を生成し、これをウィンドウ間置換回路５０４に送る。ウィンドウ間置換回路５０４では、４つのデータ要素の順序を置換ベクトルに従って置換して、置換後順序のデータを復号器の処理要素に出力する。
【００３６】
データを順次的順序でベクトルとして処理するためには、インデックス生成器から順次的なウィンドウ内アドレス｛０，１，２，…，９｝を出して、単位元（ｉｄｅｎｔｉｔｙ）（すなわち、通過（ｐａｓｓ ｔｈｒｏｕｇｈ））ウィンドウ間置換｛０，１，２，３｝を適用する。データを置換後順序でベクトル処理するためには、インデックス生成器からアドレス０，７，４，１，８，５，２，９，６，３を出して、表１におけるウィンドウ間置換を適用する。
【００３７】
以前の例では、置換後順序処理に対してデータ・ベクトルをフェッチする場合には、各ステップにおいてすべてのプロセッサがデータを同じウィンドウ内アドレスで処理することが必要であることを示した。したがって、数学的には、置換π（ｘ）に対するベクトル化基準は以下のようになる。
【００３８】
【数４】
これは、すべての１≦ｕ≦Ｍ−１および０≦ｖ≦Ｗ−１に対してである。等式（４）を満たす置換を、ここではベクトル化可能な置換と言う。
【００３９】
ＷによってＫが割り切れると仮定すると、以下のようにＰｎ（ｘ）がベクトル化可能であることを示すのは簡単である。
【００４０】
【数５】
等式（５）では、関係ｔ ｍｏｄ Ｋ ｍｏｄ Ｗ＝ｔ ｍｏｄ Ｗを、ＷによってＫが割り切れるときに、任意の整数ｔに対して用いている。等式（５）の５つの等式のうち第４の等式における二重総和（ｄｏｕｂｌｅ ｓｕｍｍａｔｉｏｎ）はゼロである。なぜならば、総和における各項には、Ｗの因数が少なくとも１つは含まれているからである。
【００４１】
Ｐｍ−１（ｘ）は、Ｐｎ（ｘ）と同様に形式が多項式であるので、以下のようにベクトル化基準を満足しなければならない。
【００４２】
【数６】
これは、すべての１≦ｕ≦Ｍ−１および０≦ｖ≦Ｗ−１に対してである。Ｐｎ（ｘ）およびＰｍ−１（ｘ）は両方ともベクトル化可能であるため、データをベクトル的に格納およびフェッチすることが、自然順序においてまたはインターリーブ後順序において可能である。後述するように、このことは、ベクトル化されたターボ復号器に対して重要な単純化の効果がある。
【００４３】
等式（６）は、Ｐｍ−１（ｘ）の多項式の形式に基づいて、ベクトル化可能性を示しているが、置換π（ｘ）がベクトル化可能であるならば、その逆置換π−１（ｘ）もベクトル化可能であるということは一般的に正しい。π（ｘ）がベクトル化可能であるため、以下でなければならない。
【００４４】
【数７】
ここで、０≦ｕ，ｍｕ≦Ｍ−１、ｘ≠ｙ時にｍｘ≠ｍｙ、および０≠ｖ，ｗｖ≦Ｗ−１である。
【００４５】
等式（７）を逆にすると以下のようになる。
【００４６】
【数８】
等式（８）が与えられたとすると、π−１（ｘ）は明らかに等式（４）のベクトル化基準を満たしている。
【００４７】
工学の文献では、長さＫ＝ＭＷの置換π（ｘ）に対する無競合の基準（ｃｏｎｔｅｎｔｉｏｎ−ｆｒｅｅ ｃｒｉｔｅｒｉｏｎ）について以下のように述べている。
【００４８】
【数９】
これは、すべての０≦ｐ，ｑ≦Ｍ−１（ただしｐ≠ｑ）に対してである。Ｐｎ（ｘ）は等式（４）のベクトル化基準を満足するので、以下でなければならない。
【００４９】
【数１０】
ここで、０≦ｍｕ≦Ｍ−１（ｘ≠ｙ時にｍｘ≠ｍｙ）および０≦ｗｖ≦Ｗ−１（ｘ≠ｙ時にｗｘ≠ｗｙ）である。
【００５０】
等式（９）の床演算（ｆｌｏｏｒ ｏｐｅｒａｔｉｏｎ）によってｍｕが取り出されるため、Ｐｎ（ｘ）は、したがって不等式（９）を満足しなければならない。同一の論法によって、等式（６）が満足されるためＰｍ−１（ｘ）も不等式（９）を満足しなければならないということが決まる。
【００５１】
しかし、以下の形式の置換について考えてみる。
【００５２】
【数１１】
ここで、０≦ｍｕ≦Ｍ−１（ｘ≠ｙ時にｍｘ≠ｍｙ）および０≦ｗｕ，ｖ≦Ｗ−１である。ここでは、ｗ成分は、ｕおよびｖの両方に依存し、等式（１０）の場合のようにｖ単独に依存してはいない。その結果、不等式（９）は満足されるが、ベクトル化基準は必ずしも満足されないであろう。したがって、ベクトル化されたターボ復号化に対しては、ベクトル化基準の方が強い基準である。無競合のメモリ・アクセスを保証することに加えて、データをベクトルとして格納およびフェッチすることも、所望のウィンドウ内アドレスを出すことによって可能である。
【００５３】
ハードウェアのターボ復号化では、Ｐｎ（ｘ）を再帰的に生成する手段が必要である。Ｐｎ（ｘ＋１）を以下のように展開することによって再帰的関係を導き出すことができる。
【００５４】
【数１２】
ここで、Ｐｎ−１ｎ（ｘ）は次数ｎ−１の多項式である。
【００５５】
【数１３】
ここで係数は以下の通りである。
【００５６】
【数１４】
Ｐｎ−１ｎ（ｘ）自体が多項式であるため、以下が得られる。
【００５７】
【数１５】
したがって等式（１２）の再帰的関係を、以下のように０次項まで回帰させる（ｒｅｇｒｅｓｓｅｄ ｂａｃｋ）ことができる。
【００５８】
【数１６】
等式（１６）は、ハードウェアの具体化が簡単である。図６にその例をｎ＝５に対して示す。図６では、再帰回路６００は、レジスタ６０２、６０４、６０６、６０８、および６１０と、加算器６１２、６１４、６１６、６１８、および６２０とを備える。入力信号Ｐ０１（ｘ）（６２２）は一定であり、各Ｐｉ−１ｉ（ｘ）レジスタ（１≦ｉ≦５）の初期値は、等式（１３）の定数項ｈｉ−１，０である。初期値ｈｉ−１，０の決定を、たとえば、初期値をリアル・タイムで算出するかまたは値を事前計算して読み出し専用メモリに格納することによって、行なっても良い。出力６２４は多項式の値Ｐｎ（ｘ）である。また図６のハードウェアは、Ｐｎ（ｘ）を任意のｎ＜５に対して算出することが可能であり、これはＰｉ−１ｉ（ｘ）を０に、１≦ｉ≦５−ｎに対して初期化することによって行なわれる。
【００５９】
図６のハードウェア・モデルは、実際に行なわれる信号のモジュロＫの換算を省略することによって単純化している。これは、図７に示す再規格化可能な加算器７００を、図６の各加算器の代わりに用いることによって行なうことができる。図７を参照して、再規格化可能な加算器７００は、入力信号７０２（ｘ）および７０４（ｙ）、モジュロＫを加算するように動作可能である。入力信号ｘおよびｙを加算器７０６において加算して、信号７０８を生成する。加算器７１０では、値Ｋ（７１２）を信号７０８から差し引いて、信号７１４を生成する。信号７１４が正の場合、それを出力として用いなければならない。信号７１４が負の場合、信号７０８を出力として用いなければならない。この例では、データを２の補足形式で格納することで、信号７１４の最上位ビット（ｍｏｓｔ ｓｉｇｎｉｆｉｃａｎｔ ｂｉｔ：ＭＳＢ）を７１６において選択して、信号セレクタ７１８を制御するために利用できるようにしている。加算の結果（モジュロＫ）を、信号７２０として出力する。
【００６０】
図６のハードウェアが生成するＰｎ（ｘ）は、ｘ＝０で開始して、ｘ＝Ｋ−１まで増加する。しかしターボ復号器は、Ｐｎ（ｘ）を逆の順序で生成する必要もある。すなわち、ｘ＝Ｋ−１で開始して、ｘ＝０まで減少するのである。Ｐｎ（ｘ−１）を以下のように展開することによって、再帰的関係を導き出すことができる。
【００６１】
【数１７】
ここで、Ｑｎ−１ｎ（ｘ）は次数ｎ−１の多項式である。
【００６２】
【数１８】
ここで係数は以下の通りである。
【００６３】
【数１９】
Ｑｎ−１ｎ（ｘ）自体が多項式であるため、以下が得られる。
【００６４】
【数２０】
したがって等式（２０）の再帰的関係を、以下のように０次項まで回帰させることができる。
【００６５】
【数２１】
Ｐｉ−１ｉ（ｘ）レジスタ（１≦ｉ≦５）の値を初期化して定数項ｋｉ−１，０にすることによって、図６のハードウェアを用いて等式（２１）の再帰を算出することができる。正順序での生成に対するレジスタ初期化の場合と同様に、初期値ｋｉ−１，０の決定を、たとえば初期値をリアル・タイムで算出するかまたは値を事前計算して読み出し専用メモリに格納することによって、行なっても良い。
【００６６】
考え方の一例として、以下の置換多項式について考えてみる。
【００６７】
【数２２】
上記等式を用いて、以下が得られる。
【００６８】
【数２３】
【００６９】
【数２４】
【００７０】
【数２５】
前述したように、図６のハードウェアを用いてＰ３（ｘ）を正の順序で算出するために、レジスタを以下のように初期化する。
（１）レジスタＰ５（ｘ）を初期化して０にする。
（２）レジスタＰ４５（ｘ）を初期化して２７にする（Ｐ２３（ｘ）多項式の定数項）。（３）レジスタＰ３４（ｘ）を初期化して２０にする（Ｐ１２（ｘ）多項式の定数項）。（４）レジスタＰ２３（ｘ）を初期化して２０にする（定数項Ｐ０１（ｘ））。
（５）レジスタＰ１２（ｘ）およびＰ０１（ｘ）を初期化して０にする。
【００７１】
初期化の後、レジスタを３９回クロックして、シーケンスにおける４０個のアドレスすべてを生成する。表２に、レジスタの内容を、多項式Ｐ３（ｘ）＝３７ｘ＋２０ｘ２＋１０ｘ３ ｍｏｄ ４０に対する周期数ｘの関数として、正の順序で列挙する。表のＰ５（ｘ）列におけるアドレスのシーケンスは、等式（２２）を直接算出したときに生成されたであろうシーケンスと同じものであることを確認することができる。
【００７２】
逆順序の再帰に対する初期レジスタ値が、Ｑｉ−１ｉ（ｘ）から以下のように求まる。
【００７３】
【数２６】
【００７４】
【数２７】
【００７５】
【数２８】
したがって、図６のハードウェアを用いてＰ３（ｘ）を逆の順序で算出するために、レジスタを以下のように初期化する。
（１）レジスタＰ５（ｘ）を初期化して０にする。
（２）レジスタＰ４５（ｘ）を初期化して１３にする（Ｑ２３（ｘ）多項式の定数項）。（３）レジスタＰ３４（ｘ）を初期化して２０にする（Ｑ１２（ｘ）多項式の定数項）。（４）レジスタＰ２３（ｘ）を初期化して２０にする（定数項Ｑ０１（ｘ））。
（５）レジスタＰ１２（ｘ）およびＰ０１（ｘ）を初期化して０にする。
【００７６】
初期化の後、レジスタを４０回クロックして、シーケンスにおける４０個のアドレスすべてを生成する。表３に、レジスタの内容を、多項式Ｐ３（ｘ）＝３７ｘ＋２０ｘ２＋１０ｘ３ ｍｏｄ ４０に対する周期数ｘの関数として、逆の順序で列挙する。目視による検査によって、表３におけるシーケンスが表２の逆のシーケンスであることが明らかである。
【００７７】
【表２】
【００７８】
【表３】
前述の考え方は、主に基数（ｒａｄｉｘ）２の復号器に適用される。これは、クロック周期当たり１つのベクトルを処理する。符号トレリス記述（ｃｏｄｅ ｔｒｅｌｌｉｓ ｄｅｓｃｒｉｐｔｉｏｎ）では、基数２のマルチ・プロセッサ復号器の各プロセッサは、クロック周期当たり１つのトレリス・ステップを処理する。基数４の復号化は、復号器のスループットを増加させるための良く知られた技術である。符号トレリス記述では、基数４のマルチ・プロセッサ復号器の各プロセッサは、クロック周期当たり２つのトレリス・ステップを処理する。したがって基数４のベクトル化された復号器は、クロック周期当たり２つのベクトルを処理する。一方のベクトルは偶数のトレリス・ステップに対応し、他方は奇数のトレリス・ステップに対応する。
【００７９】
図８は、本発明のいくつかの実施形態による基数４の復号器に対する典型的なインターリーバ回路（たとえばインターリーバ回路３０６）のブロック図である。図８を参照して、インターリーバ回路は、偶数インデックス生成器８００、奇数インデックス生成器８０２、偶数ウィンドウ間置換回路８０４、および奇数ウィンドウ間置換回路８０６を備える。１０×４Ｂのメモリ５０２は、４０個のデータ・サンプルのブロックを収容している。動作時には、偶数インデックス生成器８００は偶数ウィンドウ内インデックス８０８を生成して、メモリ・アクセス・コントローラに送り、その結果、メモリ５０２の対応する行における４つのデータ要素が偶数ウィンドウ間置換回路８０４に送られる。同様に、奇数インデックス生成器８０２は奇数ウィンドウ内インデックス８１０を生成して、メモリ・アクセス・コントローラに送り、その結果、メモリ５０２の対応する行における４つのデータ要素が偶数ウィンドウ間置換回路８０６に送られる。またインデックス発生器８００、８０２は、４要素の置換ベクトルｍｅｖｅｎ８１２と４要素の置換ベクトルｍｏｄｄ８１４とを生成する。これらは、偶数ウィンドウ間置換回路８０４と奇数ウィンドウ間置換回路８０６とにそれぞれ送られる。偶数および奇数置換回路８０４および８０６はそれぞれ、置換ベクトルｍｅｖｅｎおよびｍｏｄｄにそれぞれ従って、４つのデータ要素の順序を置換して、データを置換後順序で復号器の処理要素に出力する。
【００８０】
基数４の動作を行なうために、インデックス発生器８００および８０２は、各クロック周期上で２ステップだけ進まなければならない。なお、等式（１２）〜（１６）は、クロック周期ごとに行なうインデックス発生器の１ステップの正の進みに対する帰納式を示している。等式（１７）〜（２１）は、クロック周期ごとに行なう１ステップの逆の進みに対する帰納式を与えている。これらの式は基数２の処理に適している。
【００８１】
基数４の処理に対して、これらの式は以下のように一般化される。ステップｘからｄステップだけ離れた再帰多項式の値は以下の通りである。
【００８２】
【数２９】
ここで、Ｓｎ−１ｎ（ｘ）は次数ｎ−１の多項式である。
【００８３】
【数３０】
ここで係数は以下の通りである。
【００８４】
【数３１】
Ｓｎ−１ｎ（ｘ）自体が多項式であるため、以下が得られる。
【００８５】
【数３２】
したがって等式（３２）の再帰的関係を、以下のように０次項まで回帰させることができる。
【００８６】
【数３３】
等式（２９）〜（３３）は、等式（１２）〜（１６）および（１７）〜（２１）の一般化である。基数２の正の進み（ｆｏｒｗａｒｄ ａｄｖａｎｃｅｍｅｎｔ）に対してｄ＝１であり、一方で、基数２の逆の進み（ｂａｃｋｗａｒｄ ａｄｖａｎｃｅｍｅｎｔ）に対してｄ＝−１である。同様に、基数４の正の進みに対してｄ＝２であり、一方で、基数４の逆の進みに対してｄ＝−２である。
【００８７】
図９は、典型的なベクトル化されたターボ復号器アーキテクチャのブロック図である。ログ・マップ復号器（たとえば、復号器３０４）は、複数のＭ個のログ・マップ・プロセッサ、たとえばプロセッサ３１４（「ＰＲＯＣ０」〜「ＰＲＯＣＭ−１」と標示される）からなる。ログ・マップ（ｌｏｇ−ＭＡＰ）復号器３０４は、復号器１モード（自然順序処理）と復号器２モード（置換後順序処理）とを交互に行なう。また外部データ格納用の２つのメモリ（たとえばメモリ５０２および別のメモリ５０２’）と置換回路（たとえば置換回路５０４）とが存在する。メモリ・セレクタ９０２は、ログ・マップ復号器３０４が復号器１モードなのか復号器２モードなのかに応じて、２つのメモリ５０２および５０２’間で選択する。いずれのモードにおいても、インターリーバ（インデックス生成器たとえばインデックス生成器５００と置換回路５０４とを備える）は、メモリの行からデータ・ベクトルを取り出すためのウィンドウ内アドレスと、ウィンドウ間でデータ・ベクトルを置換するためのウィンドウ間置換ベクトルとを生成する。なお、このアーキテクチャによって基数４の処理も可能である。この場合、インデックス生成器は、メモリの２つの行から２つのデータ・ベクトルを取り出すための２つのアドレス（偶数および奇数）に加えて、ウィンドウ間でこれらのデータ・ベクトルを置換するための２つのウィンドウ間置換ベクトルを生成する。
【００８８】
図１０および１１に、長さＫのブロック（Ｋ＝ＭＷ）に対する外部メモリの格納配置を例示する。外部メモリはＷの格納域深さであり、各格納域は、Ｂビット量の長さＭのベクトルを格納する。図１０および１１の略図における各小さいボックスには、収容されるデータのインデックスが示されている。インターリーバ置換をπ（ｘ）（０≦ｘ≦ＭＷ−１）によって示す。図１０は、外部メモリ１（５０２’）がデータを置換後順序で格納することを示している。図１１は、外部メモリ２（５０２）がデータを自然順序で格納することを示している。
【００８９】
このアーキテクチャにおけるデータの流れは以下の通りである。復号器２モード（置換後順序処理）では、ウィンドウ内置換アドレスをウィンドウ間置換ベクトルとともに出して置換回路を制御することによって、外部（ｅｘｔｒｉｎｓｉｃｓ）は外部メモリ２（自然順序メモリ）からベクトル的にフェッチされる。ログ・マップ・プロセッサが、更新された外部を生成すると、復号器２がそれらを（ベクトルとして）外部メモリ１内に順次に格納する。復号器２が、更新された外部を置換後順序で生成するが、それらを順次に格納するので、外部は最後には外部メモリ１内で置換後順序になることは、図１０に示す通りである。
【００９０】
復号器１モード（自然順序処理）では、外部は外部メモリ１（置換後順序メモリ）からベクトル的にフェッチされる。データはメモリ内では置換後順序であるが、復号器１は自然順序で処理するため、外部を、それらをフェッチするときに脱置換（ｄｅｐｅｒｍｕｔａｔｉｏｎ）しなれければならない。前述したように、逆のＱＰＰ置換はベクトル化可能である。したがって、復号器２が自然順序の外部を置換して置換後順序の外部にするのと同じ方法で、復号器１は置換後順序の外部を脱置換して自然順序の外部にする。したがって、復号器１は、ウィンドウ間脱置換アドレスをウィンドウ間脱置換とともに出して、置換回路を制御する。
【００９１】
図９の復号器アーキテクチャにおける置換回路は、任意の置換が可能でなければならない。そのため、Ｂビット値に対するＭ×Ｍクロスバー・スイッチを用いなければならない。ＬＴＥの場合、スループット要求から３２という大きいＭ値を決めても良く、Ｂはほぼ８ビットである。８ビット値に対する３２ｘ３２クロスバー・スイッチは、８１９２個の２入力マルチプレクサを用いて実現することができる。したがって、置換回路は復号器の重要な態様である。図９の復号器アーキテクチャにおいて単一の置換回路は可能である。なぜならば、インターリーバ置換およびその逆置換の両方をベクトル化しても良いからである。
【００９２】
置換をベクトル化することができる場合、その逆もベクトル化することができる（これについては前述した）。しかし無競合の置換には、無競合の逆置換という意味は含まれていない。置換π（ｘ）（０≦ｘ≦７）とその逆のπ−１（ｘ）について考えてみる。これらを表４に示す。置換π（ｘ）は明らかに、Ｍ＝２（すなわち、Ｗ＝４）に対して無競合である。しかし、逆のπ−１（ｘ）はＭ＝２に対して無競合ではないことも明らかである。たとえば、以下の通りである。
【００９３】
【数３４】
および
【００９４】
【数３５】
実際には、この場合、あらゆるステップにおいて競合が存在する。
【００９５】
【表４】
インターリーバ逆置換が無競合ではない場合、復号器は、外部を自然順序で両方の外部メモリに格納しなければならず、図１２に示すアーキテクチャが必要となる。図１２に示すのは、インターリーバ逆置換が無競合ではない場合の典型的なターボ復号器アーキテクチャである。このアーキテクチャには２つの置換回路５０４および１２０２がある。置換回路５０４はフェッチ時に外部を置換し、置換回路１２０２は格納時に外部を脱置換する。加えて、インバータ１２０４が、ウィンドウ間置換を反転させて置換回路１２０２を駆動するのに必要である。そのため、図９に示す復号器の方が図１２に示す復号器よりも単純である。前述したように、ＱＰＰと同様にベクトル化可能なインターリーバ置換を用いるときには、単一の置換ネットワークのみが必要であり、ハードウェアがウィンドウ間置換を反転する必要はない。
【００９６】
図９のより単純な復号器アーキテクチャに対するインターリーバ・モジュールに対して以下の能力が推論される。
（１）インターリーバ・モジュールは、置換およびその逆の両方を生成できなければならない。さらに、モジュールは、これらの置換を正の順序および逆の順序の両方で生成できなければならない。これには、置換多項式を再帰的に算出する一般的な論理回路が必要である。論理回路は、何らかの最高次数（ＬＴＥの場合は４または５）に対してデザインする必要がある。
【００９７】
（２）インターリーバ・モジュールは、Ｍ個のアドレスをウィンドウ内アドレスとウィンドウ間置換とに、クロック周期当たり１つのレートで分解できなければならない。論理回路は、何らかの最大数のウィンドウＭｍａｘと何らかの最大のウィンドウ寸法Ｗｍａｘとに適応するようにデザインする必要がある。ＬＴＥの場合、Ｍｍａｘ＝１６またはＭｍａｘ＝３２であり、Ｗｍａｘ＝３８４またはＷｍａｘ＝１９２である。
【００９８】
長さＷのウィンドウ上で動作するＭ個の並列プロセッサを伴うベクトル化されたターボ復号器について考えてみる。置換後順序処理の場合、ｉ番目のステップ（０≦ｉ≦Ｗ−１）では、以下のアドレスにおけるデータ、
【００９９】
【数３６】
を、フェッチしなければならない。数量ｗｉ（０≦ｗｉ≦Ｗ−１）はウィンドウ内アドレスであり、以下の値、
【０１００】
【数３７】
（ここで、０≦ｍｉ≦Ｍ−１）は、ウィンドウ間置換である。
【０１０１】
等式（３６）は、ハードウェアによってアドレスπ（ｘ）＝ｍｘＷ＋ｗｘをその成分ｍｘおよびｗｘに分解しなければならないことを示している。これらの成分は以下の通りである。
【０１０２】
【数３８】
および
【０１０３】
【数３９】
この問題に対するアプローチの１つは、π（ｘ）を算出した後に、ハードウェアによって等式（３８）および（３９）を力任せに算出することである。しかしながら、このアプローチは、Ｍが増えるにつれて高価になる。
【０１０４】
より良い解決方法は、π（ｘ）の決定に関与するすべての算出を「基数Ｗ（ｂａｓｅ−Ｗ）」ドメインにおいて行なうことである。この解決方法を用いれば、π（ｘ）の算出に関与する各数量ｖ＝ｍｖＷ＋ｗｖは、ｖではなく対（ｍｖ，ｗｖ）として示される。すべての動作は対で行なわれ、結果は対で示される。図６に示す再帰的アドレス生成ハードウェアの場合、図７の再規格化可能な加算器の代わりに、図１３に示す対ベースの（ｐａｉｒ−ｂａｓｅｄ）加算器を用いる。図１３に、図６の再帰的アドレス生成ハードウェアに対する典型的な対ベースの加算器１３００を示す。図１３を参照して、対ベースの加算器１３００は、信号対（ｍｘ、ｗｘ）（７０２および７０２’）を信号対（ｍｙ、ｗｙ）（７０４および７０４’）に加算して、その結果、信号対（ｍｚ，ｗｚ）（７２０および７２０’）を生じる。なお結果を、０≦ｍｚ≦Ｍ−１および０≦ｗｚ≦Ｗ−１となるように再規格化する。加算器７０６、加算器７１０、ＭＳＢセレクタ７１６、および信号セレクタ７１８によって、図７を参照して前述したように、ｗｘおよびｗｙモジュロＬ（ここでＬ＝Ｗ）を加算する第１の再規格化可能な加算器が形成される。同様に、第２の再規格化可能な加算器は、加算器１３０８に結合された加算器７０６’と、加算器１３０８に結合された加算器７１０’と、加算器７１０’に結合されたＭＳＢセレクタ７１６’と、ＭＳＢセレクタ７１６’に結合された信号セレクタ７１８’とを備えており、加算器７０６’および７１０’は、ｍｘ、ｍｙ、および「桁上げ」信号１３０６モジュロＬ（ここでＬ＝Ｍ）を加算する。ｗｘ＋ｗｙ−Ｗが負の場合に、信号１３０２がＭＳＢセレクタ７１６によって出力される。この信号は、ｗｘ＋ｗｙが≧Ｗの場合に設定される「桁上げ」信号１３０６を生成するために、インバータ１３０４を通過する。桁上げ信号１３０６は、加算器７０６’の出力に、加算器１３０８において加算される。このようにして、すべての算出をモジュロＫではなくモジュロＷで行なっても良い。図６の再帰回路において対ベースの加算器を用いる場合、力任せの技術でアドレスを算出した後にアドレスをそのｗおよびｍ成分に分解する算出を行なうのではなくて、ウィンドウ内アドレスとウィンドウ間置換ベクトル要素とを直接算出する。
【０１０５】
この解決方法を用いれば、アドレスπ（ｘ）を算出したときに、結果が自動的に、その分解された形式（ｍｘ、ｗｘ）で現れる。
【０１０６】
【数４０】
図１４に、基数Ｗの加算器を伴うＰｎ（ｘ）に対する多項式再帰回路１４００を示す。Ｐｎ（ｘ）に対する回路１４００は、基数Ｗの加算器を用いて構成されている。回路は、初期化パラメータ１４０２の組を受け入れて（前述したレジスタを初期化し）、等式（４０）において規定される成分対（ｍｘ、ｗｘ）（出力１４０６および１４０４に対応する）を生成する。
【０１０７】
前述のセクションでは、Ｐｎ（ｘ）に対する多項式再帰回路を、各アドレスがそのｍおよびｗ成分に自動的に分解されるように、どのように変更できるかについて説明した。ベクトル化されたターボ復号器は実際には、等式（２４）の場合と同様にＭ個のウィンドウに対するＭ個の同時分解を必要とする。なお、ベクトル化可能な置換を用いれば、すべてのＭ個のウィンドウに対してｗ成分は同一であり、一方で、ｍ成分を集めることによってウィンドウ間置換が形成される。
【０１０８】
Ｍ個の同時分解に対する間接アプローチにおいて、図１５に示すように、Ｍ個の同一のＰｎ（ｘ）回路を例示する。図１５に、インターリーバをウィンドウ内アドレスとウィンドウ間置換とに分解するための間接アプローチの例を示す。再帰回路１４００を、シーケンスの全体に渡ってウィンドウ寸法Ｗの間隔で場所をずらして開始するように初期化する。具体的には、ｕ番目の回路（０≦ｕ≦Ｍ−１）を、Ｐｎ（ｕＷ）から開始するように初期化する。このアプローチでは、Ｐｎ（ｘ）の自動分解形式を用いて、ｕ番目の回路がＰｎ（ｕＷ＋ｖ） ｍｏｄ Ｗとｆｌｏｏｒ（Ｐｎ（ｕＷ＋ｖ）／Ｗ）＝ｍｕ（ｖ）との両方を生成するようにする。Ｐｎ（ｕＷ＋ｖ） ｍｏｄ Ｗがすべての回路に対して同一であるので、実際にはこれらの出力のうちの１つのみを用いる。ｍｕ（ｖ）の組を集めてウィンドウ間置換を形成する。
【０１０９】
間接アプローチとは対照的に、直接アプローチでは、以下のようにウィンドウ間置換を直接算出するための再帰を導き出す。ｕ番目のプロセッサのアドレス（０≦ｕ≦Ｍ−１）のｖ番目のステップ（０≦ｖ≦Ｗ−１）でのｍ成分ｍｕ（ｖ）は、以下のように単純化することができる。
【０１１０】
【数４１】
ここで、Ｒｕ（ｖ）は次数ｎ−１の多項式である。
【０１１１】
【数４２】
ここで係数は以下の通りである。
【０１１２】
【数４３】
なお、Ｒｕ（ｖ）は多項式であるので、図６に示す再帰的な構造を用いて再帰的に算出することができる。図６に示す構造を用いてＲｕ（ｖ）を再帰的に算出する場合、算出をモジュロＭで換算することができる。したがって、この場合、図７の再規格化可能な加算器を、Ｋの代わりにＭを用いて、利用することができる。
【０１１３】
等式（４１）の５つの等式のうち最後の等式は、図１６に示す簡単なハードウェア解釈である。図１６に、Ｐｎ（ｖ）に対する自動分解再帰回路の単一インスタンス１４００（置換シーケンスの始まりから開始するように初期化されている）を用いて、ウィンドウ内アドレスとウィンドウ間置換のｍ０（ｖ）項とを取り出す場合を示す。Ｒｕ（ｖ）（１≦ｕ≦Ｍ−１、０≦ｖ≦Ｗ−１）を算出する回路のＭ−１個のインスタンス（１６０２、１６０２’、および１６０２”）も存在する。等式（４１）における方法に従って、ｍ０（ｖ）を、加算器１６０４、１６０４’、および１６０４”において各出力Ｒｕ（ｖ）に加算して、ｍｕ（ｖ）を得る。出力５１０は、自動分解再帰回路１４００の出力１４０６、１４０４のうち第１の出力１４０６と、加算器１６０４、１６０４’、および１６０４”の出力とを含むとともに、出力５１０は、ウィンドウ間置換ベクトルｍ（ｖ）＝（ｍ０（ｖ），ｍ１（ｖ），…，ｍＭ−１（ｖ））であり、出力５０６（ウィンドウ内インデックスｗである）は、回路１４００の出力１４０６、１４０４のうち第２の出力１４０４を含む。
【０１１４】
ウィンドウ間置換生成を、循環シフトを用いて単純化しても良い。特定の条件の下では、ｍ（ｖ）はすべてのｖ（０≦ｖ≦Ｗ−１）に対してｍ（０）の循環シフトである。このことは、潜在的に、置換（たとえば図４に示すもの）を実現するハードウェアを単純化するのに役立つであろう。どのようにこれが行なわれるかを理解するために、置換ｍ（ｖ）について考えてみる。ｍ０（ｖ）はｍ（ｖ）のすべての要素に対して共通であるので、以下のようになる。
【０１１５】
【数４４】
特に関心が持たれるのは、ベクトルＲ（ｖ）が一定でｖに依存しない場合、すなわち以下の場合である。
【０１１６】
【数４５】
これは、したがって以下を意味する。
【０１１７】
【数４６】
これは各ｕ（０≦ｕ≦Ｍ−１）に対してである。これが成り立つ場合、ｍ（ｖ）は、ｍ０（ｖ）の位置だけＲ（０）の循環シフトである。
【０１１８】
等式（４２）から導き出されるように、等式（４６）における条件が、すべてのｕおよびＷに対して成り立つべき場合には、以下でなければならない。
【０１１９】
【数４７】
これは、すべての１≦ｉ≦ｎ−１およびｉ＋１≦ｊ≦ｎに対してである。ｊの各値に対してｉの可能性が複数存在するため、以下でなければならない。
【０１２０】
【数４８】
これは２≦ｊ≦ｎに対してであり、ＬＣＤｉ［ｘｉ］は、すべての数ｘｉの最小公約数を表わしている。
【０１２１】
本発明の一態様によれば、単一の論理回路（適切に初期化されている）は、ベクトル化されたターボ復号器においてＱＰＰインターリーバを実現する働きをする。回路は、ＱＰＰ置換インデックスのシーケンスまたは逆置換インデックスのシーケンスを生成することが可能であっても良い。回路は、これらのシーケンスの算出を、正の順序で行なっても良いし逆の順序で行なっても良い。回路は、基数２の処理に対してクロック周期当たり１ステップ進む単一の回路を備えていても良い。さらに回路は、それぞれ基数４の処理に対してクロック周期当たり２ステップ進む２つの回路（偶数および奇数）を備えていても良い。
【０１２２】
以上、ベクトル化された置換と、ベクトル化されたターボ復号化アーキテクチャとについて説明してきた。一実施形態においては、置換およびその逆が両方ともベクトル化可能（ＱＰＰ置換の場合と同様）であるときに、単一の置換回路復号器アーキテクチャを用いる。ベクトル化されたターボ復号器インターリーバがウィンドウ内アドレスとウィンドウ間置換とを生成することを求める要求について説明し、この問題に対する２つの解決方法を示した。１つの（間接的な）解決方法（図１５に示す）では、場所をずらした多くの完全インターリーバを例示する一方で、他の（直接的な）解決方法（図１６に示す）では、ウィンドウ間置換のシーケンスを直接算出する再帰に基づく。インターリーバ設計段階（等式（４８））で利用できた基準として、ウィンドウ間置換シーケンスの生成を循環シフトのシーケンスに変えるものを導き出した。
【０１２３】
ここで導き出した技術はすべて、レジスタの組を適切に初期化することに基づいている。これらの初期値（等式（１４）、（１９）、および（４２）の定数項）を、事前算出して読み出し専用メモリに格納しても良いし、リアル・タイムで算出しても良い。
【０１２４】
図１７は、本発明のある態様に一致するインターリーブ後データのベクトル化された処理を行なうための方法のフロー・チャートである。図１７の開始ブロック１７０２の後で、ブロック１７０４において再帰回路のレジスタを初期化する。ブロック１７０６において、再帰回路をクロックして、ウィンドウ内インデックスｗとウィンドウ間置換ベクトルｍとを生成する。ブロック１７０８において、ウィンドウ内インデックスｗを用いて、データ行をメモリから取り出す。ブロック１７１０において、これらのデータ値を置換して並列プロセッサに送る。並列プロセッサは、ターボ復号器のプロセッサであっても良いし、インターリーブ後または置換後データを用いる何らかの他のプロセスを行なっても良い。ブロック１７１２においてデータを処理し、ブロック１７１４において処理結果をメモリに格納しても良いし出力しても良い。現在のデータ・ブロックにおいて処理すべきデータ値がもっと存在する場合（判定ブロック１７１６からの肯定の分岐によって示すように）、フローはブロック１７０６に戻って、次のウィンドウ内インデックスと置換ベクトルとを計算する。現在のデータ・ブロックにおいて処理すべきデータ値がもうない場合（判定ブロック１７１６からの否定の分岐によって示すように）、現在のブロックは処理されていて、ブロック１７１８において方法を終了する。
【０１２５】
上記の明細書では、本発明の特定の実施形態について説明してきた。しかし当業者であれば理解するように、添付の請求項で述べる本発明の範囲から逸脱することなく、種々の変更および変形を行なうことができる。したがって、明細書および図は限定的な意味ではなく例示的な意味で考慮すべきであり、このような変更はすべて、本発明の範囲に含まれることが意図されている。優位性、または問題の解決方法、および何らかの利益、優位性、解決方法を生じさせ得るかまたはより明白にし得るどんな要素も、いずれかまたは全ての請求項の重要であるか、必要であるか、または不可欠である特徴または要素として解釈してはならない。現時点で請求する発明は、添付の請求項によって規定され、本出願の係属中になされる任意の補正、および付与される請求項の均等物すべてを含む。
【技術分野】
【０００１】
本発明は、一般的にデータ処理回路に関し、特に「ターボ符号」を用いる通信システム用のデータ処理回路に関する。
【背景技術】
【０００２】
通信システムにおいて、送信信号（たとえば無線による）は、フェージング、ジャミング、および他の、信号内にエラーを導入させ得る要素の影響を受けやすいことがある。送信前に信号を符号化することは、送信中に導入されたエラーを、受信部において信号を復号化したときに検出および補正できるようにすることによって、チャンネル・ノイズ、フェージング、およびジャミングの影響を抑えることに役立つ。
【０００３】
「ターボ符号」は、符号化方式におけるブレイクスルーであると認められており、送信中に生じるエラーに対する強力な抵抗を実現するものである。それらは、並列連結畳込み符号（ｐａｒａｌｌｅｌ ｃｏｎｃａｔｅｎａｔｅｄ ｃｏｎｖｏｌｕｔｉｏｎａｌ ｃｏｄｅｓ：ＰＣＣＣ）または直列連結畳込み符号（ｓｅｒｉａｌ ｃｏｎｃａｔｅｎａｔｅｄ ｃｏｎｖｏｌｕｔｉｏｎａｌ ｃｏｄｅｓ：ＳＣＣＣ）として実施することができる。ターボ符号によって、符号化利得が高くなり、ビット・エラー率が１０−７と低くなる。ターボ符号は、エラー補正が優れているため、信号対雑音比（ＳＮＲ）が一般的に低い応用例（たとえば、無線通信）において非常に有用である。
【０００４】
図１に、従来のターボ符号器の例を示す。ターボ符号器１００が受信した信号１０２は、第１の再帰的組織畳み込み（ｒｅｃｕｒｓｉｖｅ ｓｙｓｔｅｍａｔｉｃ ｃｏｎｖｏｌｕｔｉｏｎａｌ：ＲＳＣ）符号器１０４に送られるとともに、インターリーバ１０６を介して第２の畳み込み符号器１０８に送られる。２つの畳み込み符号器によってターボ符号の成分符号が得られる。インターリーバ１０６は、データ・ストリームの順序を、データ・ストリームを第２の畳み込み符号器に入力する前に変える。また一方のデータ・ストリームをインターリーブするので、結果として生じる符号は、ターボ符号器から得られる高い符号化利得を提供する時間変化特性を有するものとなる。符号化された信号１１０は、変調されて、通信チャネル上で送信される。
【０００５】
図２に、従来のターボ復号器の例を示す。ターボ復号器２００は、復調信号２０２を通信チャネルから受信する。信号２０２は、第１の軟入力、軟出力（ｓｏｆｔ−ｉｎｐｕｔ，ｓｏｆｔ ｏｕｔｐｕｔ：ＳＩＳＯ）復号器２０４に送られるとともに、インターリーバ２０６を介して第２のＳＩＳＯ復号器２０８に送られる。第２のＳＩＳＯ復号器２０８は信号２０２の成分も受信する。第１のＳＩＳＯ復号器２０４の出力を、インターリーバ２１０を介して第２のＳＩＳＯ復号器２０８に送り、第２のＳＩＳＯ復号器の出力を、デ・インターリーバ２１２を介して第１のＳＩＳＯ復号器２０４に送ることによって、反復復号を可能にする。動作時には、受信したデータ・ブロック（データ・フレームとも言う）を一度処理した後に、複数回再循環して、所望の符号化利得を達成する。ターボ符号は、エラーに対する高い抵抗を示すが、多くの実際の応用にとって理想的に適しているわけではない。なぜならば、ターボ符号器がインターリーバ（遅延を導入する）を用いる結果、待ち時間が極端に長くなり、またターボ復号器の反復アルゴリズムがコンピュータ的に複雑であるからである。ターボ符号は通常、大きなブロック・サイズ（たとえば、＞５０００ビット）を伴って動作する。反復復号を容易にするために、ブロック全体に対する軟入力をメモリに格納しなければならない。言い換えれば、各復号化段階において、軟入力を繰り返して用いて更新する。その結果、ターボ復号器はメモリ集約的（ｍｅｍｏｒｙ ｉｎｔｅｎｓｉｖｅ）となるため、ターボ復号器は、実用的でないかまたは応用例によっては高価すぎることになる。
【０００６】
一般的に、連続したターボ復号器の待ち時間は、特別にデザインされた高速のハードウェアを用いてターボ復号器を実現することによって、わずかに改善される場合がある。しかし、費用が増加し、デバイスが複雑になり、加えて消費電力が増加する（多くの低電力無線デバイスにおいては容認できない場合がある）という犠牲を払って得られるのは、待ち時間が漸進的に改善されるということのみである。
【０００７】
ターボ復号化の長い待ち時間に対処する代替的なアプローチは、並列復号化アーキテクチャを用いることである。並列復号化によって、スループットおよび待ち時間を大きく改善することができる。２つの基本的な並列化方式を利用することができる。並列処理は、複数の受信信号を同時に復号化することか、または受信信号ブロックをサブ・ブロックに分割して、サブ・ブロックを複数の並列プロセッサによって並列に復号化することによって、実現される場合がある。スループットおよび待ち時間は、並列復号化を用いて小さくなる場合があるが、大容量メモリの要求はそうはならない。加えて、ハードウェアもより複雑になり、コストも増加する。したがって、メモリ効率が良くてハードウェア（または面積）効率の良い並列化方式が、ターボ符号を実際に具体化するためには必要である。
【０００８】
並列処理に伴う問題の１つはメモリ・アクセスの問題である。特に、インターリーバの存在は、複数の並列プロセッサによってメモリが順序が狂ったアドレス指定をされざるを得ないことを意味する。２つ以上のプロセッサが、読み出しまたは書き込みアクセスを同じメモリに対して同じクロック周期で行なう必要があるときに、メモリ競合が生じる。ある種類の無競合（ｃｏｎｔｅｎｔｉｏｎ ｆｒｅｅ：ＣＦ）インターリーバの場合、メモリ競合はない。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
二次置換多項式（ｑｕａｄｒａｔｉｃ ｐｅｒｍｕｔａｔｉｏｎ ｐｏｌｙｎｏｍｉａｌ：ＱＰＰ）ターボ・インターリーバ（ロング・ターム・エボリューション（Ｌｏｎｇ Ｔｅｒｍ Ｅｖｏｌｕｔｉｏｎ：ＬＴＥ）規格において採用されている）は、ＣＦインターリーバである。ＬＴＥシステムでは高データ・レートが要求されるため、ターボ復号器は、複数のプロセッサを用いた並列復号化を利用する必要がある。したがって、ＱＰＰをマルチ・プロセッサ・ターボ復号器に適用することが求められている。
【図面の簡単な説明】
【００１０】
【図１】典型的な従来のターボ符号器のブロック図である。
【図２】典型的な従来のターボ復号器のブロック図である。
【図３】本発明のいくつかの実施形態による復号器回路の一部のブロック図である。
【図４】本発明のいくつかの実施形態による典型的なデータ置換を示す図である。
【図５】本発明のいくつかの実施形態による典型的なインターリーバのブロック図である。
【図６】本発明のいくつかの実施形態による典型的な多項式再帰回路のブロック図である。
【図７】本発明のいくつかの実施形態による典型的な再規格化可能な加算器のブロック図である。
【図８】本発明のいくつかの実施形態による基数４のターボ復号器に対する典型的なインターリーバのブロック図である。
【図９】本発明のいくつかの実施形態による単一の置換回路を用いた典型的なターボ復号器回路のブロック図である。
【図１０】本発明のいくつかの実施形態による典型的なメモリ割り当てを示す図である。
【図１１】本発明のいくつかの実施形態による典型的なメモリ割り当てを示す図である。
【図１２】本発明のいくつかの実施形態による２つの置換回路を用いた典型的なターボ復号器回路のブロック図である。
【図１３】本発明のいくつかの実施形態による典型的な基数Ｗの加算器のブロック図である。
【図１４】本発明のいくつかの実施形態による典型的な基数Ｗの多項式再帰回路のブロック図である。
【図１５】本発明のいくつかの実施形態による基数Ｗの多項式再帰回路を用いた直接型インデックス生成器のブロック図である。
【図１６】本発明のいくつかの実施形態による基数Ｗの多項式再帰回路を用いた間接型インデックス生成器のブロック図である。
【図１７】本発明のいくつかの実施形態によるインターリーブ後順序でデータ値にアクセスするための方法のフロー・チャートである。
【発明を実施するための形態】
【００１１】
添付の図では、個々の図の全体に渡って、同様の参照数字は同一のまたは機能的に同様の要素を指している。また添付の図は、以下の詳細な説明とともに本明細書に取り入れられて本明細書の一部を構成するとともに、さらに種々の実施形態を例示し、本発明にすべて従う種々の原理および優位性を説明する働きをする。
【００１２】
当業者であれば分かるように、図における要素は、簡潔および明瞭を目的として例示されており、必ずしも一定の比率で描かれているわけではない。たとえば、本発明の種々の実施形態の理解の向上を助けるために、図中のいくつかの要素の寸法は他の要素に対して誇張されている場合がある。
【００１３】
本発明による実施形態を詳細に説明する前に、以下のことに注意されたい。すなわち、実施形態は主に、ターボ復号器におけるインターリーバに関係する方法工程および装置構成要素の組み合わせにあるということである。したがって、装置構成要素よび方法工程は、適切であれば図面中で従来の符号を用いて表して、本発明の実施形態を理解するのに適切な特定の詳細のみを示すようにしている。これは、本明細書の説明の利益を受ける当業者には容易に明らかである詳細によって、開示が不明瞭になることがないようにするためである。
【００１４】
この文献において、関係語たとえば第１および第２、最上部および最下部などは単に、ある存在または行為を別の存在または行為と区別するために用いる場合があり、その場合、このような存在間または行為間のこのような関係または順序の実際のものを必ずしも必要としないし意味することもない。用語「含む」、「含んでいる」またはこれらの他のどんな変形も、包括的に含めることに及んでいることが意図されている。すなわち、要素のリストを含むプロセス、方法、物品、または装置には、これらの要素が含まれているだけでなく、明白にはリストにされていない他の要素、またはこのようなプロセス、方法、物品、もしくは装置に固有の他の要素が、含まれていても良い。要素が「含む」の後にきた場合、これは、要素を含むプロセス、方法、物品、または装置に、同じ要素がさらに存在することを排除するものではないことを、さらなる制約を伴うことなく行なうものである。
【００１５】
本明細書に記載した本発明の実施形態は、プログラマブル論理回路たとえばフィールド・プログラマブル・ゲート・アレイ（ｆｉｅｌｄ ｐｒｏｇｒａｍｍａｂｌｅ ｇａｔｅ ａｒｒａｙ：ＦＰＧＡ）または従来のプロセッサに、前記回路またはプロセッサを制御する一意の格納されたプログラム命令であって、本明細書に記載したインターリービングの機能の一部、ほとんど、またはすべて実現するプログラム命令を伴うものを含む場合があることが理解される。あるいは、一部または全部の機能を、格納されたプログラム命令を持たない状態機械によって実施することができるか、または各機能もしくはいくつかの機能のある組み合わせをカスタム・ロジックとして実施する１つもしくは複数の特定用途向け集積回路（ａｐｐｌｉｃａｔｉｏｎ ｓｐｅｃｉｆｉｃ ｉｎｔｅｇｒａｔｅｄ ｃｉｒｃｕｉｔ：ＡＳＩＣ）において実施することができる。当然のことながら、これらのアプローチの組み合わせを用いることができる。このようにして、これらの機能を得るための方法および手段について本明細書において説明している。さらに、以下のことが予想される。すなわち、おそらくかなりの努力および多くのデザイン選択が、たとえば、利用できる時間、最近の技術、および経済的考慮によって誘導されるにもかかわらず、本明細書で開示される考え方および原理によって導かれれば、当業者は、このようなソフトウェア命令およびプログラムおよびＩＣを最小限の実験で容易に作成することができるということである。
【００１６】
本発明の実施形態は、並列またはベクトル化されたターボ復号器におけるメモリ・アクセスに関する。したがって、本発明の実施形態は一般的にデータ処理回路に関し、特に「ターボ符号」を用いる通信システム用のデータ処理回路に関する。
【００１７】
図３は、本発明のいくつかの実施形態による復号器回路３００の一部のブロック図である。図３を参照して、回路３００はデータ・メモリ３０２を備える。データ・メモリ３０２は、復号器３０４のためのデータ格納を行なう。インターリーバ回路３０６が、メモリ３０２からのデータを復号器３０４へ転送するように動作可能である。インターリーバ回路３０６は、インデックスの順序列によって規定される置換に従ってデータのシーケンスを置換するデバイスである。典型的な応用例（たとえばターボ復号化）では、インターリーバは、メモリ内のデータへのランダム・アクセスを行なうためのアドレス３０８を生成して、対応するデータ３１０をメモリから受信する。生成されたアドレスは通常、インデックスの順序列に対応するため、この文献では、用語「インデックス」と「アドレス」とを交換可能に用いる。データ３１２は、自然順序またはインターリーブ後順序（ｉｎｔｅｒｌｅａｖｅｄ ｏｒｄｅｒ）で、復号器３０４に送られる。
【００１８】
復号器３０４は、データを復号化するために並列に動作する多くの処理要素３１４を備える並列プロセッサまたはベクトル化されたプロセッサである。各処理要素は、受信したデータ・ブロックのサブ・セクション、サブ・ブロック、または「ウィンドウ」上で動作する。インターリーバは、メモリからのデータをウィンドウ間で置換するように動作する。用語「ベクトル化される（ｖｅｃｔｏｒｉｚｅｄ）」を用いるのは、インターリーバによってデータの格納およびフェッチがベクトルとして（すなわち、別個のグループとして）できる場合である。復号器から出力されたデータ３１６は、メモリ３０２内に格納しても良いし、他の処理モジュールへ出力しても良い。
【００１９】
インターリーバ３０６を、種々のベクトル化されたターボ復号器アーキテクチャにおいて具体化しても良く、ウィンドウ間置換のシーケンスを生成するための論理回路を単純にする設計基準について開示する。
【００２０】
本発明の一実施形態においては、インターリーバは、ベクトル化されたターボ復号器における二次置換多項式（ＱＰＰ）インターリーバである。この実施形態においては、インターリーバによって、より高次の置換多項式を正または逆の順序で再帰的に生成することが行なわれる。一実施形態においては、インターリーバを論理回路として実施して、アドレスπ（ｘ）＝ｍｘＷ＋ｗｘをそのｍｘおよびｗｘ成分に自動的に分解する。加えて、インターリーバを用いて、ベクトル化されたターボ復号化を行なうために必要な「ウィンドウ内」アドレスと「ウィンドウ間」置換とを生成しても良い。
【００２１】
インターリーバを、第３世代（３Ｇ）無線アクセス技術のロング・ターム・エボリューション（ＬＴＥ）（以後、「ＬＴＥ」と言う）に対して提案されるターボ復号器ハードウェアにおいて用いても良い。
【００２２】
ＱＰＰ置換は、多項式によって生成される置換の二次の場合である。最初に、置換多項式の導入処理について説明する。処理は一般的である。なぜならば、ターボ復号器は、形式上は多項式であるが必ずしも二次ではない逆置換を効果的に用いることができるからである。次に、典型的なベクトル化されたターボ復号化アーキテクチャについて説明する。このアーキテクチャからインターリーバの機能上の要求が推論される。インターリーバの機能の１つは、置換を「ウィンドウ内」アドレスと「ウィンドウ間」置換とに分解することである。ウィンドウ間置換のシーケンスの生成を単純化できる設計基準についても説明する。
【００２３】
ｎ次の置換多項式は以下の形式である。
【００２４】
【数１】
ここで、ｘおよびｆｉは整数である。ｘを０からＫ−１まで増加させると、多項式Ｐｎ（ｘ）によって置換が生成される。多項式Ｐｎ（ｘ）は通常、置換されたシーケンスの位置ｘにおける数量の置換前位置として解釈される。ｆｉに対していくつか制約（ここでは扱わない）を設けることによって、Ｐｎ（ｘ）によって置換が生成されることを確実にする。ＬＴＥの場合、ターボ・インターリーバは二次多項式（すなわちｎ＝２）を用いる。簡単にするために、この文献の残りの部分では一般に、ｍｏｄ Ｋの表記法を省き、すべての量が、特に断らない限り、モジュロＫで換算されていると暗黙的に仮定する。
【００２５】
逆置換Ｐｍ−１（ｘ）、ここで、
【００２６】
【数２】
も、以下の多項式の形である。
【００２７】
【数３】
一般的に、ｎ≠ｍである。ＱＰＰの場合、ｆ２は、Ｋのすべての素因数（ｐｒｉｍｅ ｆａｃｔｏｒ）をある次数（ｏｒｄｅｒ）まで含まなければならない。その結果、ｍは、ｆ２のすべての素因数の最大次数（ｌａｒｇｅｓｔ ｏｒｄｅｒ）より大きくなることはない。
【００２８】
復号器スループットは、ベクトル化を通して増加させることができる。ベクトル化された復号器では、長さＫのデータ・ブロックを、Ｍ個の通常は非オーバーラッピングの長さＷの「ウィンドウ」に分割する（Ｋ＝ＭＷ）。これらを、Ｍ個のプロセッサによって同期して処理する。
【００２９】
図４に、本発明のいくつかの実施形態による典型的なデータ置換を示す。図４に示すのは、長さＫ＝４０のデータ・ブロック４０２である。ブロック４０２を、Ｍ＝４で長さ１０のウィンドウ４０４に分割してある。データを４個のプロセッサ４０６によって処理する。ｉ番目のプロセッサ（０≦ｉ≦３）によって、データ・ブロック４０２内での位置１０ｉ〜１０ｉ＋９におけるデータを処理する。
【００３０】
反復処理であるので、ターボ復号器は、順次的（または「自然（ｎａｔｕｒａｌ）」）順序および置換後順序（ｐｅｒｍｕｔｅｄ ｏｒｄｅｒ）の両方で、データを処理できなければならない。図４では、アレイ４０２は、データのシーケンスを自然順序で示し、アレイ４０８は、シーケンスを置換後またはインターリーブ後順序で示す。図４では、プロセッサ０が、データ位置０、１、２、…、９におけるデータ、および位置０、１７、３４、１１、２８、５、２２、３９、１６、３３におけるデータを、順次に処理できなければならないということを示している。同様に、プロセッサ１が、位置１０、１１、１２、…、１９におけるデータ、および位置１０、２７、４、２１、３８、１５、３２、９、２６、３におけるデータを、順次に処理できなければならない。
【００３１】
ベクトル化と置換後順序処理との組み合わせによって、メモリ管理の問題が持ち込まれる。なぜならば、複数のプロセッサが、メモリからのデータを、メモリ・アクセスに対して互いに干渉することも競合することもなく、置換後順序で同時にフェッチしなければならないからである。
【００３２】
図４の「インターリーブ後データ」列における置換アドレスは、実際には、ＱＰＰ３７ｘ＋２Ｏｘ２ ｍｏｄ ４０によって生成される。図４において、各自然順序および各置換アドレスは、形式ｍ１０＋ｗに分解されている。ここで、ｗは「ウィンドウ内アドレス」列の中にあり、ｍは「ウィンドウ番号」列の中にある。以後、アドレスは一般的に形式ｍＷ＋ｗであると考え、ｍおよびｗを、それぞれアドレスのｍおよびｗ成分であると言う。置換アドレスに対して、ｍ成分は、データが由来する置換前のシーケンスにおけるウィンドウを示し、ｗ成分は、データが由来するウィンドウ内での相対位置を示す。
【００３３】
図４の置換アドレス列４０８は、任意のステップにおいて、すべてのプロセッサが同じウィンドウ内アドレス（列４１０）におけるデータを処理することを示している。たとえば、置換後順序処理の場合、第１のステップにおいて、すべてのプロセッサはウィンドウ内アドレス０におけるデータを処理する。第２のステップにおいて、すべてのプロセッサはウィンドウ内アドレス７におけるデータを処理する。さらに、置換後順序処理の場合に、各ステップにおいてウィンドウ間置換があることに注意されたい（列４１２）。ｍｉ＝（ｍ０，ｍ１，ｍ２，ｍ３）ｉ（０≦ｍ０，ｍ１，ｍ２，ｍ３≦３）が、ｉ番目の処理ステップ（０≦ｉ≦９）におけるプロセッサ０、１、２、および３に対する置換されたアドレスのｍ成分をそれぞれ示すものとする。各ｍｉは、ステップｉに対するウィンドウ間置換である。表１に、これらのウィンドウ間置換をｉの関数として列挙する。ちなみに、各ｍｉ（１≦ｉ≦９）はｍ０の循環シフトであることに注意されたい。これは一般的に置換多項式に当てはまるわけではないが、特性が保たれる条件を以下に導き出す。
【００３４】
【表１】
結果として、この例におけるデータは１０×４Ｂのメモリに格納することができる。ここでＢはデータ幅（ビット）である。
【００３５】
図５は、本発明のいくつかの実施形態による典型的なインターリーバのブロック図である。図５を参照して、インターリーバは、インデックス生成器５００、メモリ５０２、およびウィンドウ間置換回路５０４を備える。１０×４Ｂのメモリ５０２は、４０個のデータ・サンプルのブロックを収容している。メモリの各行は、同じウィンドウ内インデックスｗのデータ要素を収容し、一方で、各列は、同じウィンドウ・インデックスｍのデータ要素を収容している。自然順序でデータを処理するとき、プロセッサ０はデータ値の第１の列を処理する。インターリーブ後順序でデータを処理するとき、プロセッサ０は、下線を引いた数字を伴うデータ値をウィンドウ内順序｛０，７，４，１，８，５，２，９，６，３｝で処理する。動作時には、インデックス生成器５００が、ウィンドウ内インデックス５０６（ｗ）を生成し、これをメモリ・アクセス・コントローラ５０８に送る。この例では、メモリ・アクセス・コントローラ５０８は、メモリ５０２の対応する行における４つのデータ要素をウィンドウ間置換回路５０４に送る行セレクタを備える。またインデックス生成器５００は、４要素の置換ベクトル５１０（ｍ）を生成し、これをウィンドウ間置換回路５０４に送る。ウィンドウ間置換回路５０４では、４つのデータ要素の順序を置換ベクトルに従って置換して、置換後順序のデータを復号器の処理要素に出力する。
【００３６】
データを順次的順序でベクトルとして処理するためには、インデックス生成器から順次的なウィンドウ内アドレス｛０，１，２，…，９｝を出して、単位元（ｉｄｅｎｔｉｔｙ）（すなわち、通過（ｐａｓｓ ｔｈｒｏｕｇｈ））ウィンドウ間置換｛０，１，２，３｝を適用する。データを置換後順序でベクトル処理するためには、インデックス生成器からアドレス０，７，４，１，８，５，２，９，６，３を出して、表１におけるウィンドウ間置換を適用する。
【００３７】
以前の例では、置換後順序処理に対してデータ・ベクトルをフェッチする場合には、各ステップにおいてすべてのプロセッサがデータを同じウィンドウ内アドレスで処理することが必要であることを示した。したがって、数学的には、置換π（ｘ）に対するベクトル化基準は以下のようになる。
【００３８】
【数４】
これは、すべての１≦ｕ≦Ｍ−１および０≦ｖ≦Ｗ−１に対してである。等式（４）を満たす置換を、ここではベクトル化可能な置換と言う。
【００３９】
ＷによってＫが割り切れると仮定すると、以下のようにＰｎ（ｘ）がベクトル化可能であることを示すのは簡単である。
【００４０】
【数５】
等式（５）では、関係ｔ ｍｏｄ Ｋ ｍｏｄ Ｗ＝ｔ ｍｏｄ Ｗを、ＷによってＫが割り切れるときに、任意の整数ｔに対して用いている。等式（５）の５つの等式のうち第４の等式における二重総和（ｄｏｕｂｌｅ ｓｕｍｍａｔｉｏｎ）はゼロである。なぜならば、総和における各項には、Ｗの因数が少なくとも１つは含まれているからである。
【００４１】
Ｐｍ−１（ｘ）は、Ｐｎ（ｘ）と同様に形式が多項式であるので、以下のようにベクトル化基準を満足しなければならない。
【００４２】
【数６】
これは、すべての１≦ｕ≦Ｍ−１および０≦ｖ≦Ｗ−１に対してである。Ｐｎ（ｘ）およびＰｍ−１（ｘ）は両方ともベクトル化可能であるため、データをベクトル的に格納およびフェッチすることが、自然順序においてまたはインターリーブ後順序において可能である。後述するように、このことは、ベクトル化されたターボ復号器に対して重要な単純化の効果がある。
【００４３】
等式（６）は、Ｐｍ−１（ｘ）の多項式の形式に基づいて、ベクトル化可能性を示しているが、置換π（ｘ）がベクトル化可能であるならば、その逆置換π−１（ｘ）もベクトル化可能であるということは一般的に正しい。π（ｘ）がベクトル化可能であるため、以下でなければならない。
【００４４】
【数７】
ここで、０≦ｕ，ｍｕ≦Ｍ−１、ｘ≠ｙ時にｍｘ≠ｍｙ、および０≠ｖ，ｗｖ≦Ｗ−１である。
【００４５】
等式（７）を逆にすると以下のようになる。
【００４６】
【数８】
等式（８）が与えられたとすると、π−１（ｘ）は明らかに等式（４）のベクトル化基準を満たしている。
【００４７】
工学の文献では、長さＫ＝ＭＷの置換π（ｘ）に対する無競合の基準（ｃｏｎｔｅｎｔｉｏｎ−ｆｒｅｅ ｃｒｉｔｅｒｉｏｎ）について以下のように述べている。
【００４８】
【数９】
これは、すべての０≦ｐ，ｑ≦Ｍ−１（ただしｐ≠ｑ）に対してである。Ｐｎ（ｘ）は等式（４）のベクトル化基準を満足するので、以下でなければならない。
【００４９】
【数１０】
ここで、０≦ｍｕ≦Ｍ−１（ｘ≠ｙ時にｍｘ≠ｍｙ）および０≦ｗｖ≦Ｗ−１（ｘ≠ｙ時にｗｘ≠ｗｙ）である。
【００５０】
等式（９）の床演算（ｆｌｏｏｒ ｏｐｅｒａｔｉｏｎ）によってｍｕが取り出されるため、Ｐｎ（ｘ）は、したがって不等式（９）を満足しなければならない。同一の論法によって、等式（６）が満足されるためＰｍ−１（ｘ）も不等式（９）を満足しなければならないということが決まる。
【００５１】
しかし、以下の形式の置換について考えてみる。
【００５２】
【数１１】
ここで、０≦ｍｕ≦Ｍ−１（ｘ≠ｙ時にｍｘ≠ｍｙ）および０≦ｗｕ，ｖ≦Ｗ−１である。ここでは、ｗ成分は、ｕおよびｖの両方に依存し、等式（１０）の場合のようにｖ単独に依存してはいない。その結果、不等式（９）は満足されるが、ベクトル化基準は必ずしも満足されないであろう。したがって、ベクトル化されたターボ復号化に対しては、ベクトル化基準の方が強い基準である。無競合のメモリ・アクセスを保証することに加えて、データをベクトルとして格納およびフェッチすることも、所望のウィンドウ内アドレスを出すことによって可能である。
【００５３】
ハードウェアのターボ復号化では、Ｐｎ（ｘ）を再帰的に生成する手段が必要である。Ｐｎ（ｘ＋１）を以下のように展開することによって再帰的関係を導き出すことができる。
【００５４】
【数１２】
ここで、Ｐｎ−１ｎ（ｘ）は次数ｎ−１の多項式である。
【００５５】
【数１３】
ここで係数は以下の通りである。
【００５６】
【数１４】
Ｐｎ−１ｎ（ｘ）自体が多項式であるため、以下が得られる。
【００５７】
【数１５】
したがって等式（１２）の再帰的関係を、以下のように０次項まで回帰させる（ｒｅｇｒｅｓｓｅｄ ｂａｃｋ）ことができる。
【００５８】
【数１６】
等式（１６）は、ハードウェアの具体化が簡単である。図６にその例をｎ＝５に対して示す。図６では、再帰回路６００は、レジスタ６０２、６０４、６０６、６０８、および６１０と、加算器６１２、６１４、６１６、６１８、および６２０とを備える。入力信号Ｐ０１（ｘ）（６２２）は一定であり、各Ｐｉ−１ｉ（ｘ）レジスタ（１≦ｉ≦５）の初期値は、等式（１３）の定数項ｈｉ−１，０である。初期値ｈｉ−１，０の決定を、たとえば、初期値をリアル・タイムで算出するかまたは値を事前計算して読み出し専用メモリに格納することによって、行なっても良い。出力６２４は多項式の値Ｐｎ（ｘ）である。また図６のハードウェアは、Ｐｎ（ｘ）を任意のｎ＜５に対して算出することが可能であり、これはＰｉ−１ｉ（ｘ）を０に、１≦ｉ≦５−ｎに対して初期化することによって行なわれる。
【００５９】
図６のハードウェア・モデルは、実際に行なわれる信号のモジュロＫの換算を省略することによって単純化している。これは、図７に示す再規格化可能な加算器７００を、図６の各加算器の代わりに用いることによって行なうことができる。図７を参照して、再規格化可能な加算器７００は、入力信号７０２（ｘ）および７０４（ｙ）、モジュロＫを加算するように動作可能である。入力信号ｘおよびｙを加算器７０６において加算して、信号７０８を生成する。加算器７１０では、値Ｋ（７１２）を信号７０８から差し引いて、信号７１４を生成する。信号７１４が正の場合、それを出力として用いなければならない。信号７１４が負の場合、信号７０８を出力として用いなければならない。この例では、データを２の補足形式で格納することで、信号７１４の最上位ビット（ｍｏｓｔ ｓｉｇｎｉｆｉｃａｎｔ ｂｉｔ：ＭＳＢ）を７１６において選択して、信号セレクタ７１８を制御するために利用できるようにしている。加算の結果（モジュロＫ）を、信号７２０として出力する。
【００６０】
図６のハードウェアが生成するＰｎ（ｘ）は、ｘ＝０で開始して、ｘ＝Ｋ−１まで増加する。しかしターボ復号器は、Ｐｎ（ｘ）を逆の順序で生成する必要もある。すなわち、ｘ＝Ｋ−１で開始して、ｘ＝０まで減少するのである。Ｐｎ（ｘ−１）を以下のように展開することによって、再帰的関係を導き出すことができる。
【００６１】
【数１７】
ここで、Ｑｎ−１ｎ（ｘ）は次数ｎ−１の多項式である。
【００６２】
【数１８】
ここで係数は以下の通りである。
【００６３】
【数１９】
Ｑｎ−１ｎ（ｘ）自体が多項式であるため、以下が得られる。
【００６４】
【数２０】
したがって等式（２０）の再帰的関係を、以下のように０次項まで回帰させることができる。
【００６５】
【数２１】
Ｐｉ−１ｉ（ｘ）レジスタ（１≦ｉ≦５）の値を初期化して定数項ｋｉ−１，０にすることによって、図６のハードウェアを用いて等式（２１）の再帰を算出することができる。正順序での生成に対するレジスタ初期化の場合と同様に、初期値ｋｉ−１，０の決定を、たとえば初期値をリアル・タイムで算出するかまたは値を事前計算して読み出し専用メモリに格納することによって、行なっても良い。
【００６６】
考え方の一例として、以下の置換多項式について考えてみる。
【００６７】
【数２２】
上記等式を用いて、以下が得られる。
【００６８】
【数２３】
【００６９】
【数２４】
【００７０】
【数２５】
前述したように、図６のハードウェアを用いてＰ３（ｘ）を正の順序で算出するために、レジスタを以下のように初期化する。
（１）レジスタＰ５（ｘ）を初期化して０にする。
（２）レジスタＰ４５（ｘ）を初期化して２７にする（Ｐ２３（ｘ）多項式の定数項）。（３）レジスタＰ３４（ｘ）を初期化して２０にする（Ｐ１２（ｘ）多項式の定数項）。（４）レジスタＰ２３（ｘ）を初期化して２０にする（定数項Ｐ０１（ｘ））。
（５）レジスタＰ１２（ｘ）およびＰ０１（ｘ）を初期化して０にする。
【００７１】
初期化の後、レジスタを３９回クロックして、シーケンスにおける４０個のアドレスすべてを生成する。表２に、レジスタの内容を、多項式Ｐ３（ｘ）＝３７ｘ＋２０ｘ２＋１０ｘ３ ｍｏｄ ４０に対する周期数ｘの関数として、正の順序で列挙する。表のＰ５（ｘ）列におけるアドレスのシーケンスは、等式（２２）を直接算出したときに生成されたであろうシーケンスと同じものであることを確認することができる。
【００７２】
逆順序の再帰に対する初期レジスタ値が、Ｑｉ−１ｉ（ｘ）から以下のように求まる。
【００７３】
【数２６】
【００７４】
【数２７】
【００７５】
【数２８】
したがって、図６のハードウェアを用いてＰ３（ｘ）を逆の順序で算出するために、レジスタを以下のように初期化する。
（１）レジスタＰ５（ｘ）を初期化して０にする。
（２）レジスタＰ４５（ｘ）を初期化して１３にする（Ｑ２３（ｘ）多項式の定数項）。（３）レジスタＰ３４（ｘ）を初期化して２０にする（Ｑ１２（ｘ）多項式の定数項）。（４）レジスタＰ２３（ｘ）を初期化して２０にする（定数項Ｑ０１（ｘ））。
（５）レジスタＰ１２（ｘ）およびＰ０１（ｘ）を初期化して０にする。
【００７６】
初期化の後、レジスタを４０回クロックして、シーケンスにおける４０個のアドレスすべてを生成する。表３に、レジスタの内容を、多項式Ｐ３（ｘ）＝３７ｘ＋２０ｘ２＋１０ｘ３ ｍｏｄ ４０に対する周期数ｘの関数として、逆の順序で列挙する。目視による検査によって、表３におけるシーケンスが表２の逆のシーケンスであることが明らかである。
【００７７】
【表２】
【００７８】
【表３】
前述の考え方は、主に基数（ｒａｄｉｘ）２の復号器に適用される。これは、クロック周期当たり１つのベクトルを処理する。符号トレリス記述（ｃｏｄｅ ｔｒｅｌｌｉｓ ｄｅｓｃｒｉｐｔｉｏｎ）では、基数２のマルチ・プロセッサ復号器の各プロセッサは、クロック周期当たり１つのトレリス・ステップを処理する。基数４の復号化は、復号器のスループットを増加させるための良く知られた技術である。符号トレリス記述では、基数４のマルチ・プロセッサ復号器の各プロセッサは、クロック周期当たり２つのトレリス・ステップを処理する。したがって基数４のベクトル化された復号器は、クロック周期当たり２つのベクトルを処理する。一方のベクトルは偶数のトレリス・ステップに対応し、他方は奇数のトレリス・ステップに対応する。
【００７９】
図８は、本発明のいくつかの実施形態による基数４の復号器に対する典型的なインターリーバ回路（たとえばインターリーバ回路３０６）のブロック図である。図８を参照して、インターリーバ回路は、偶数インデックス生成器８００、奇数インデックス生成器８０２、偶数ウィンドウ間置換回路８０４、および奇数ウィンドウ間置換回路８０６を備える。１０×４Ｂのメモリ５０２は、４０個のデータ・サンプルのブロックを収容している。動作時には、偶数インデックス生成器８００は偶数ウィンドウ内インデックス８０８を生成して、メモリ・アクセス・コントローラに送り、その結果、メモリ５０２の対応する行における４つのデータ要素が偶数ウィンドウ間置換回路８０４に送られる。同様に、奇数インデックス生成器８０２は奇数ウィンドウ内インデックス８１０を生成して、メモリ・アクセス・コントローラに送り、その結果、メモリ５０２の対応する行における４つのデータ要素が偶数ウィンドウ間置換回路８０６に送られる。またインデックス発生器８００、８０２は、４要素の置換ベクトルｍｅｖｅｎ８１２と４要素の置換ベクトルｍｏｄｄ８１４とを生成する。これらは、偶数ウィンドウ間置換回路８０４と奇数ウィンドウ間置換回路８０６とにそれぞれ送られる。偶数および奇数置換回路８０４および８０６はそれぞれ、置換ベクトルｍｅｖｅｎおよびｍｏｄｄにそれぞれ従って、４つのデータ要素の順序を置換して、データを置換後順序で復号器の処理要素に出力する。
【００８０】
基数４の動作を行なうために、インデックス発生器８００および８０２は、各クロック周期上で２ステップだけ進まなければならない。なお、等式（１２）〜（１６）は、クロック周期ごとに行なうインデックス発生器の１ステップの正の進みに対する帰納式を示している。等式（１７）〜（２１）は、クロック周期ごとに行なう１ステップの逆の進みに対する帰納式を与えている。これらの式は基数２の処理に適している。
【００８１】
基数４の処理に対して、これらの式は以下のように一般化される。ステップｘからｄステップだけ離れた再帰多項式の値は以下の通りである。
【００８２】
【数２９】
ここで、Ｓｎ−１ｎ（ｘ）は次数ｎ−１の多項式である。
【００８３】
【数３０】
ここで係数は以下の通りである。
【００８４】
【数３１】
Ｓｎ−１ｎ（ｘ）自体が多項式であるため、以下が得られる。
【００８５】
【数３２】
したがって等式（３２）の再帰的関係を、以下のように０次項まで回帰させることができる。
【００８６】
【数３３】
等式（２９）〜（３３）は、等式（１２）〜（１６）および（１７）〜（２１）の一般化である。基数２の正の進み（ｆｏｒｗａｒｄ ａｄｖａｎｃｅｍｅｎｔ）に対してｄ＝１であり、一方で、基数２の逆の進み（ｂａｃｋｗａｒｄ ａｄｖａｎｃｅｍｅｎｔ）に対してｄ＝−１である。同様に、基数４の正の進みに対してｄ＝２であり、一方で、基数４の逆の進みに対してｄ＝−２である。
【００８７】
図９は、典型的なベクトル化されたターボ復号器アーキテクチャのブロック図である。ログ・マップ復号器（たとえば、復号器３０４）は、複数のＭ個のログ・マップ・プロセッサ、たとえばプロセッサ３１４（「ＰＲＯＣ０」〜「ＰＲＯＣＭ−１」と標示される）からなる。ログ・マップ（ｌｏｇ−ＭＡＰ）復号器３０４は、復号器１モード（自然順序処理）と復号器２モード（置換後順序処理）とを交互に行なう。また外部データ格納用の２つのメモリ（たとえばメモリ５０２および別のメモリ５０２’）と置換回路（たとえば置換回路５０４）とが存在する。メモリ・セレクタ９０２は、ログ・マップ復号器３０４が復号器１モードなのか復号器２モードなのかに応じて、２つのメモリ５０２および５０２’間で選択する。いずれのモードにおいても、インターリーバ（インデックス生成器たとえばインデックス生成器５００と置換回路５０４とを備える）は、メモリの行からデータ・ベクトルを取り出すためのウィンドウ内アドレスと、ウィンドウ間でデータ・ベクトルを置換するためのウィンドウ間置換ベクトルとを生成する。なお、このアーキテクチャによって基数４の処理も可能である。この場合、インデックス生成器は、メモリの２つの行から２つのデータ・ベクトルを取り出すための２つのアドレス（偶数および奇数）に加えて、ウィンドウ間でこれらのデータ・ベクトルを置換するための２つのウィンドウ間置換ベクトルを生成する。
【００８８】
図１０および１１に、長さＫのブロック（Ｋ＝ＭＷ）に対する外部メモリの格納配置を例示する。外部メモリはＷの格納域深さであり、各格納域は、Ｂビット量の長さＭのベクトルを格納する。図１０および１１の略図における各小さいボックスには、収容されるデータのインデックスが示されている。インターリーバ置換をπ（ｘ）（０≦ｘ≦ＭＷ−１）によって示す。図１０は、外部メモリ１（５０２’）がデータを置換後順序で格納することを示している。図１１は、外部メモリ２（５０２）がデータを自然順序で格納することを示している。
【００８９】
このアーキテクチャにおけるデータの流れは以下の通りである。復号器２モード（置換後順序処理）では、ウィンドウ内置換アドレスをウィンドウ間置換ベクトルとともに出して置換回路を制御することによって、外部（ｅｘｔｒｉｎｓｉｃｓ）は外部メモリ２（自然順序メモリ）からベクトル的にフェッチされる。ログ・マップ・プロセッサが、更新された外部を生成すると、復号器２がそれらを（ベクトルとして）外部メモリ１内に順次に格納する。復号器２が、更新された外部を置換後順序で生成するが、それらを順次に格納するので、外部は最後には外部メモリ１内で置換後順序になることは、図１０に示す通りである。
【００９０】
復号器１モード（自然順序処理）では、外部は外部メモリ１（置換後順序メモリ）からベクトル的にフェッチされる。データはメモリ内では置換後順序であるが、復号器１は自然順序で処理するため、外部を、それらをフェッチするときに脱置換（ｄｅｐｅｒｍｕｔａｔｉｏｎ）しなれければならない。前述したように、逆のＱＰＰ置換はベクトル化可能である。したがって、復号器２が自然順序の外部を置換して置換後順序の外部にするのと同じ方法で、復号器１は置換後順序の外部を脱置換して自然順序の外部にする。したがって、復号器１は、ウィンドウ間脱置換アドレスをウィンドウ間脱置換とともに出して、置換回路を制御する。
【００９１】
図９の復号器アーキテクチャにおける置換回路は、任意の置換が可能でなければならない。そのため、Ｂビット値に対するＭ×Ｍクロスバー・スイッチを用いなければならない。ＬＴＥの場合、スループット要求から３２という大きいＭ値を決めても良く、Ｂはほぼ８ビットである。８ビット値に対する３２ｘ３２クロスバー・スイッチは、８１９２個の２入力マルチプレクサを用いて実現することができる。したがって、置換回路は復号器の重要な態様である。図９の復号器アーキテクチャにおいて単一の置換回路は可能である。なぜならば、インターリーバ置換およびその逆置換の両方をベクトル化しても良いからである。
【００９２】
置換をベクトル化することができる場合、その逆もベクトル化することができる（これについては前述した）。しかし無競合の置換には、無競合の逆置換という意味は含まれていない。置換π（ｘ）（０≦ｘ≦７）とその逆のπ−１（ｘ）について考えてみる。これらを表４に示す。置換π（ｘ）は明らかに、Ｍ＝２（すなわち、Ｗ＝４）に対して無競合である。しかし、逆のπ−１（ｘ）はＭ＝２に対して無競合ではないことも明らかである。たとえば、以下の通りである。
【００９３】
【数３４】
および
【００９４】
【数３５】
実際には、この場合、あらゆるステップにおいて競合が存在する。
【００９５】
【表４】
インターリーバ逆置換が無競合ではない場合、復号器は、外部を自然順序で両方の外部メモリに格納しなければならず、図１２に示すアーキテクチャが必要となる。図１２に示すのは、インターリーバ逆置換が無競合ではない場合の典型的なターボ復号器アーキテクチャである。このアーキテクチャには２つの置換回路５０４および１２０２がある。置換回路５０４はフェッチ時に外部を置換し、置換回路１２０２は格納時に外部を脱置換する。加えて、インバータ１２０４が、ウィンドウ間置換を反転させて置換回路１２０２を駆動するのに必要である。そのため、図９に示す復号器の方が図１２に示す復号器よりも単純である。前述したように、ＱＰＰと同様にベクトル化可能なインターリーバ置換を用いるときには、単一の置換ネットワークのみが必要であり、ハードウェアがウィンドウ間置換を反転する必要はない。
【００９６】
図９のより単純な復号器アーキテクチャに対するインターリーバ・モジュールに対して以下の能力が推論される。
（１）インターリーバ・モジュールは、置換およびその逆の両方を生成できなければならない。さらに、モジュールは、これらの置換を正の順序および逆の順序の両方で生成できなければならない。これには、置換多項式を再帰的に算出する一般的な論理回路が必要である。論理回路は、何らかの最高次数（ＬＴＥの場合は４または５）に対してデザインする必要がある。
【００９７】
（２）インターリーバ・モジュールは、Ｍ個のアドレスをウィンドウ内アドレスとウィンドウ間置換とに、クロック周期当たり１つのレートで分解できなければならない。論理回路は、何らかの最大数のウィンドウＭｍａｘと何らかの最大のウィンドウ寸法Ｗｍａｘとに適応するようにデザインする必要がある。ＬＴＥの場合、Ｍｍａｘ＝１６またはＭｍａｘ＝３２であり、Ｗｍａｘ＝３８４またはＷｍａｘ＝１９２である。
【００９８】
長さＷのウィンドウ上で動作するＭ個の並列プロセッサを伴うベクトル化されたターボ復号器について考えてみる。置換後順序処理の場合、ｉ番目のステップ（０≦ｉ≦Ｗ−１）では、以下のアドレスにおけるデータ、
【００９９】
【数３６】
を、フェッチしなければならない。数量ｗｉ（０≦ｗｉ≦Ｗ−１）はウィンドウ内アドレスであり、以下の値、
【０１００】
【数３７】
（ここで、０≦ｍｉ≦Ｍ−１）は、ウィンドウ間置換である。
【０１０１】
等式（３６）は、ハードウェアによってアドレスπ（ｘ）＝ｍｘＷ＋ｗｘをその成分ｍｘおよびｗｘに分解しなければならないことを示している。これらの成分は以下の通りである。
【０１０２】
【数３８】
および
【０１０３】
【数３９】
この問題に対するアプローチの１つは、π（ｘ）を算出した後に、ハードウェアによって等式（３８）および（３９）を力任せに算出することである。しかしながら、このアプローチは、Ｍが増えるにつれて高価になる。
【０１０４】
より良い解決方法は、π（ｘ）の決定に関与するすべての算出を「基数Ｗ（ｂａｓｅ−Ｗ）」ドメインにおいて行なうことである。この解決方法を用いれば、π（ｘ）の算出に関与する各数量ｖ＝ｍｖＷ＋ｗｖは、ｖではなく対（ｍｖ，ｗｖ）として示される。すべての動作は対で行なわれ、結果は対で示される。図６に示す再帰的アドレス生成ハードウェアの場合、図７の再規格化可能な加算器の代わりに、図１３に示す対ベースの（ｐａｉｒ−ｂａｓｅｄ）加算器を用いる。図１３に、図６の再帰的アドレス生成ハードウェアに対する典型的な対ベースの加算器１３００を示す。図１３を参照して、対ベースの加算器１３００は、信号対（ｍｘ、ｗｘ）（７０２および７０２’）を信号対（ｍｙ、ｗｙ）（７０４および７０４’）に加算して、その結果、信号対（ｍｚ，ｗｚ）（７２０および７２０’）を生じる。なお結果を、０≦ｍｚ≦Ｍ−１および０≦ｗｚ≦Ｗ−１となるように再規格化する。加算器７０６、加算器７１０、ＭＳＢセレクタ７１６、および信号セレクタ７１８によって、図７を参照して前述したように、ｗｘおよびｗｙモジュロＬ（ここでＬ＝Ｗ）を加算する第１の再規格化可能な加算器が形成される。同様に、第２の再規格化可能な加算器は、加算器１３０８に結合された加算器７０６’と、加算器１３０８に結合された加算器７１０’と、加算器７１０’に結合されたＭＳＢセレクタ７１６’と、ＭＳＢセレクタ７１６’に結合された信号セレクタ７１８’とを備えており、加算器７０６’および７１０’は、ｍｘ、ｍｙ、および「桁上げ」信号１３０６モジュロＬ（ここでＬ＝Ｍ）を加算する。ｗｘ＋ｗｙ−Ｗが負の場合に、信号１３０２がＭＳＢセレクタ７１６によって出力される。この信号は、ｗｘ＋ｗｙが≧Ｗの場合に設定される「桁上げ」信号１３０６を生成するために、インバータ１３０４を通過する。桁上げ信号１３０６は、加算器７０６’の出力に、加算器１３０８において加算される。このようにして、すべての算出をモジュロＫではなくモジュロＷで行なっても良い。図６の再帰回路において対ベースの加算器を用いる場合、力任せの技術でアドレスを算出した後にアドレスをそのｗおよびｍ成分に分解する算出を行なうのではなくて、ウィンドウ内アドレスとウィンドウ間置換ベクトル要素とを直接算出する。
【０１０５】
この解決方法を用いれば、アドレスπ（ｘ）を算出したときに、結果が自動的に、その分解された形式（ｍｘ、ｗｘ）で現れる。
【０１０６】
【数４０】
図１４に、基数Ｗの加算器を伴うＰｎ（ｘ）に対する多項式再帰回路１４００を示す。Ｐｎ（ｘ）に対する回路１４００は、基数Ｗの加算器を用いて構成されている。回路は、初期化パラメータ１４０２の組を受け入れて（前述したレジスタを初期化し）、等式（４０）において規定される成分対（ｍｘ、ｗｘ）（出力１４０６および１４０４に対応する）を生成する。
【０１０７】
前述のセクションでは、Ｐｎ（ｘ）に対する多項式再帰回路を、各アドレスがそのｍおよびｗ成分に自動的に分解されるように、どのように変更できるかについて説明した。ベクトル化されたターボ復号器は実際には、等式（２４）の場合と同様にＭ個のウィンドウに対するＭ個の同時分解を必要とする。なお、ベクトル化可能な置換を用いれば、すべてのＭ個のウィンドウに対してｗ成分は同一であり、一方で、ｍ成分を集めることによってウィンドウ間置換が形成される。
【０１０８】
Ｍ個の同時分解に対する間接アプローチにおいて、図１５に示すように、Ｍ個の同一のＰｎ（ｘ）回路を例示する。図１５に、インターリーバをウィンドウ内アドレスとウィンドウ間置換とに分解するための間接アプローチの例を示す。再帰回路１４００を、シーケンスの全体に渡ってウィンドウ寸法Ｗの間隔で場所をずらして開始するように初期化する。具体的には、ｕ番目の回路（０≦ｕ≦Ｍ−１）を、Ｐｎ（ｕＷ）から開始するように初期化する。このアプローチでは、Ｐｎ（ｘ）の自動分解形式を用いて、ｕ番目の回路がＰｎ（ｕＷ＋ｖ） ｍｏｄ Ｗとｆｌｏｏｒ（Ｐｎ（ｕＷ＋ｖ）／Ｗ）＝ｍｕ（ｖ）との両方を生成するようにする。Ｐｎ（ｕＷ＋ｖ） ｍｏｄ Ｗがすべての回路に対して同一であるので、実際にはこれらの出力のうちの１つのみを用いる。ｍｕ（ｖ）の組を集めてウィンドウ間置換を形成する。
【０１０９】
間接アプローチとは対照的に、直接アプローチでは、以下のようにウィンドウ間置換を直接算出するための再帰を導き出す。ｕ番目のプロセッサのアドレス（０≦ｕ≦Ｍ−１）のｖ番目のステップ（０≦ｖ≦Ｗ−１）でのｍ成分ｍｕ（ｖ）は、以下のように単純化することができる。
【０１１０】
【数４１】
ここで、Ｒｕ（ｖ）は次数ｎ−１の多項式である。
【０１１１】
【数４２】
ここで係数は以下の通りである。
【０１１２】
【数４３】
なお、Ｒｕ（ｖ）は多項式であるので、図６に示す再帰的な構造を用いて再帰的に算出することができる。図６に示す構造を用いてＲｕ（ｖ）を再帰的に算出する場合、算出をモジュロＭで換算することができる。したがって、この場合、図７の再規格化可能な加算器を、Ｋの代わりにＭを用いて、利用することができる。
【０１１３】
等式（４１）の５つの等式のうち最後の等式は、図１６に示す簡単なハードウェア解釈である。図１６に、Ｐｎ（ｖ）に対する自動分解再帰回路の単一インスタンス１４００（置換シーケンスの始まりから開始するように初期化されている）を用いて、ウィンドウ内アドレスとウィンドウ間置換のｍ０（ｖ）項とを取り出す場合を示す。Ｒｕ（ｖ）（１≦ｕ≦Ｍ−１、０≦ｖ≦Ｗ−１）を算出する回路のＭ−１個のインスタンス（１６０２、１６０２’、および１６０２”）も存在する。等式（４１）における方法に従って、ｍ０（ｖ）を、加算器１６０４、１６０４’、および１６０４”において各出力Ｒｕ（ｖ）に加算して、ｍｕ（ｖ）を得る。出力５１０は、自動分解再帰回路１４００の出力１４０６、１４０４のうち第１の出力１４０６と、加算器１６０４、１６０４’、および１６０４”の出力とを含むとともに、出力５１０は、ウィンドウ間置換ベクトルｍ（ｖ）＝（ｍ０（ｖ），ｍ１（ｖ），…，ｍＭ−１（ｖ））であり、出力５０６（ウィンドウ内インデックスｗである）は、回路１４００の出力１４０６、１４０４のうち第２の出力１４０４を含む。
【０１１４】
ウィンドウ間置換生成を、循環シフトを用いて単純化しても良い。特定の条件の下では、ｍ（ｖ）はすべてのｖ（０≦ｖ≦Ｗ−１）に対してｍ（０）の循環シフトである。このことは、潜在的に、置換（たとえば図４に示すもの）を実現するハードウェアを単純化するのに役立つであろう。どのようにこれが行なわれるかを理解するために、置換ｍ（ｖ）について考えてみる。ｍ０（ｖ）はｍ（ｖ）のすべての要素に対して共通であるので、以下のようになる。
【０１１５】
【数４４】
特に関心が持たれるのは、ベクトルＲ（ｖ）が一定でｖに依存しない場合、すなわち以下の場合である。
【０１１６】
【数４５】
これは、したがって以下を意味する。
【０１１７】
【数４６】
これは各ｕ（０≦ｕ≦Ｍ−１）に対してである。これが成り立つ場合、ｍ（ｖ）は、ｍ０（ｖ）の位置だけＲ（０）の循環シフトである。
【０１１８】
等式（４２）から導き出されるように、等式（４６）における条件が、すべてのｕおよびＷに対して成り立つべき場合には、以下でなければならない。
【０１１９】
【数４７】
これは、すべての１≦ｉ≦ｎ−１およびｉ＋１≦ｊ≦ｎに対してである。ｊの各値に対してｉの可能性が複数存在するため、以下でなければならない。
【０１２０】
【数４８】
これは２≦ｊ≦ｎに対してであり、ＬＣＤｉ［ｘｉ］は、すべての数ｘｉの最小公約数を表わしている。
【０１２１】
本発明の一態様によれば、単一の論理回路（適切に初期化されている）は、ベクトル化されたターボ復号器においてＱＰＰインターリーバを実現する働きをする。回路は、ＱＰＰ置換インデックスのシーケンスまたは逆置換インデックスのシーケンスを生成することが可能であっても良い。回路は、これらのシーケンスの算出を、正の順序で行なっても良いし逆の順序で行なっても良い。回路は、基数２の処理に対してクロック周期当たり１ステップ進む単一の回路を備えていても良い。さらに回路は、それぞれ基数４の処理に対してクロック周期当たり２ステップ進む２つの回路（偶数および奇数）を備えていても良い。
【０１２２】
以上、ベクトル化された置換と、ベクトル化されたターボ復号化アーキテクチャとについて説明してきた。一実施形態においては、置換およびその逆が両方ともベクトル化可能（ＱＰＰ置換の場合と同様）であるときに、単一の置換回路復号器アーキテクチャを用いる。ベクトル化されたターボ復号器インターリーバがウィンドウ内アドレスとウィンドウ間置換とを生成することを求める要求について説明し、この問題に対する２つの解決方法を示した。１つの（間接的な）解決方法（図１５に示す）では、場所をずらした多くの完全インターリーバを例示する一方で、他の（直接的な）解決方法（図１６に示す）では、ウィンドウ間置換のシーケンスを直接算出する再帰に基づく。インターリーバ設計段階（等式（４８））で利用できた基準として、ウィンドウ間置換シーケンスの生成を循環シフトのシーケンスに変えるものを導き出した。
【０１２３】
ここで導き出した技術はすべて、レジスタの組を適切に初期化することに基づいている。これらの初期値（等式（１４）、（１９）、および（４２）の定数項）を、事前算出して読み出し専用メモリに格納しても良いし、リアル・タイムで算出しても良い。
【０１２４】
図１７は、本発明のある態様に一致するインターリーブ後データのベクトル化された処理を行なうための方法のフロー・チャートである。図１７の開始ブロック１７０２の後で、ブロック１７０４において再帰回路のレジスタを初期化する。ブロック１７０６において、再帰回路をクロックして、ウィンドウ内インデックスｗとウィンドウ間置換ベクトルｍとを生成する。ブロック１７０８において、ウィンドウ内インデックスｗを用いて、データ行をメモリから取り出す。ブロック１７１０において、これらのデータ値を置換して並列プロセッサに送る。並列プロセッサは、ターボ復号器のプロセッサであっても良いし、インターリーブ後または置換後データを用いる何らかの他のプロセスを行なっても良い。ブロック１７１２においてデータを処理し、ブロック１７１４において処理結果をメモリに格納しても良いし出力しても良い。現在のデータ・ブロックにおいて処理すべきデータ値がもっと存在する場合（判定ブロック１７１６からの肯定の分岐によって示すように）、フローはブロック１７０６に戻って、次のウィンドウ内インデックスと置換ベクトルとを計算する。現在のデータ・ブロックにおいて処理すべきデータ値がもうない場合（判定ブロック１７１６からの否定の分岐によって示すように）、現在のブロックは処理されていて、ブロック１７１８において方法を終了する。
【０１２５】
上記の明細書では、本発明の特定の実施形態について説明してきた。しかし当業者であれば理解するように、添付の請求項で述べる本発明の範囲から逸脱することなく、種々の変更および変形を行なうことができる。したがって、明細書および図は限定的な意味ではなく例示的な意味で考慮すべきであり、このような変更はすべて、本発明の範囲に含まれることが意図されている。優位性、または問題の解決方法、および何らかの利益、優位性、解決方法を生じさせ得るかまたはより明白にし得るどんな要素も、いずれかまたは全ての請求項の重要であるか、必要であるか、または不可欠である特徴または要素として解釈してはならない。現時点で請求する発明は、添付の請求項によって規定され、本出願の係属中になされる任意の補正、および付与される請求項の均等物すべてを含む。
【特許請求の範囲】
【請求項１】
Ｋ個の要素を有するデータ・ブロックを符号化するためのターボ符号器であって、
次数ｎの置換多項式、
【数１】
に従って、データ・ブロックをインターリーブするように動作可能なターボ・インターリーバであって、独立変数ｘと多項式係数ｆｉとは整数であり、係数ｆｉは、
【数２】
を、２≦ｊ≦ｎに対して満たし、ＬＣＤｉ［ｘｉ］は、すべての数ｘｉの最小公約数を示す、前記ターボ・インターリーバを備えるターボ符号器。
【請求項２】
Ｋ個の要素を有するデータ・ブロックを復号化するためのターボ復号器であって、
次数ｎの置換多項式、
【数３】
に従ってインターリーブされたデータ・ブロックを、デ・インターリーブするように動作可能なターボ・デ・インターリーバであって、独立変数ｘと多項式の係数ｆｉとは整数であり、係数ｆｉは、
【数４】
を、２≦ｊ≦ｎに対して満たし、ＬＣＤｉ［ｘｉ］は、すべての数ｘｉの最小公約数を示す、前記ターボ・デ・インターリーバを備えるターボ復号器。
【請求項１】
Ｋ個の要素を有するデータ・ブロックを符号化するためのターボ符号器であって、
次数ｎの置換多項式、
【数１】
に従って、データ・ブロックをインターリーブするように動作可能なターボ・インターリーバであって、独立変数ｘと多項式係数ｆｉとは整数であり、係数ｆｉは、
【数２】
を、２≦ｊ≦ｎに対して満たし、ＬＣＤｉ［ｘｉ］は、すべての数ｘｉの最小公約数を示す、前記ターボ・インターリーバを備えるターボ符号器。
【請求項２】
Ｋ個の要素を有するデータ・ブロックを復号化するためのターボ復号器であって、
次数ｎの置換多項式、
【数３】
に従ってインターリーブされたデータ・ブロックを、デ・インターリーブするように動作可能なターボ・デ・インターリーバであって、独立変数ｘと多項式の係数ｆｉとは整数であり、係数ｆｉは、
【数４】
を、２≦ｊ≦ｎに対して満たし、ＬＣＤｉ［ｘｉ］は、すべての数ｘｉの最小公約数を示す、前記ターボ・デ・インターリーバを備えるターボ復号器。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２０１３−５５６８８（Ｐ２０１３−５５６８８Ａ）
【公開日】平成２５年３月２１日（２０１３．３．２１）
【国際特許分類】
【出願番号】特願２０１２−２５１２８４（Ｐ２０１２−２５１２８４）
【出願日】平成２４年１１月１５日（２０１２．１１．１５）
【分割の表示】特願２０１０−５３５００３（Ｐ２０１０−５３５００３）の分割
【原出願日】平成２０年１１月１１日（２００８．１１．１１）
【出願人】（５１０２８４０７１）モトローラ モビリティ エルエルシー (50)
【氏名又は名称原語表記】ＭＯＴＯＲＯＬＡ ＭＯＢＩＬＩＴＹ ＬＬＣ
【Ｆターム（参考）】
【公開日】平成２５年３月２１日（２０１３．３．２１）
【国際特許分類】
【出願日】平成２４年１１月１５日（２０１２．１１．１５）
【分割の表示】特願２０１０−５３５００３（Ｐ２０１０−５３５００３）の分割
【原出願日】平成２０年１１月１１日（２００８．１１．１１）
【出願人】（５１０２８４０７１）モトローラ モビリティ エルエルシー (50)
【氏名又は名称原語表記】ＭＯＴＯＲＯＬＡ ＭＯＢＩＬＩＴＹ ＬＬＣ
【Ｆターム（参考）】
[ Back to top ]