(57)【特許請求の範囲】
【請求項１】
0004713039.tif 000036
に応じたシリアルターボ符号化ブロック表現から、並列ターボ符号化を行う方法であって、
a) 並列度ｎにおいて、
0004713039.tif 000037
に対応する第１の内部状態について時間インデックス置換を行う工程と、
ｂ）
Ｘi(t-1)＝Ｘi-1(t-2)                 （2.xi.1）
・
・
・
Ｘi(t(n-1))＝Ｘi-1(t-n)              （2.xi.n-1）
に応じた残りの内部状態（i=2,...,N）について時間インデックス置換を行う工程と、
ｃ）
0004713039.tif 000038
に応じた出力信号について、
Ｑj(t)＝      Ｑj0(p)
Ｑj(t-1)＝    Ｑj1(p)
・
・
・
Ｑj(t-(n-1))＝Ｑjn-1(p)
jε[1,...,M]
の並列出力ベクトルを導出するために時間インデックス置換を行う工程と、
ｄ）  内部状態xk(t）(k=1,...,N)のそれぞれについて内部状態置換処理を行う工程であって、
ｄ１）  最大時間インデックス要素を前記内部状態xk(t)についてtmax=t-1に設定する工程と、
ｄ２）  前記最大時間インデックスｔmaxを有する内部状態について、前記内部状態xk(t)表現をスキャンする工程と、
ｄ３）  式（２）を利用する状態変数置換工程を通して、前記内部状態xk(t)の表現においてｔmaxからｔmax-1へ後方時間インデックス遷移を実行する工程と、
ｄ４）  ｔmaxを１だけ減ずると共に、ｔmaxがt-nよりも大きい間において前記ステップｄ２）からｄ４）を繰り返す工程とを備える工程と、
ｅ）内部状態置換処理を、各並列出力ベクトルＱj(t)(j=i,...,M)の各要素Ｑj(t-1)(i=0,...,n-2)について実行する工程であって、
ｅ１）  前記最大時間インデックス要素を、考慮された並列出力ベクトルＱj(t)におけるベクトル要素Ｑj(t-1)について、ｔmax＝t-i-1に設定する工程と、
ｅ２）  前記最大時間インデックスを有する内部状態について、前記ベクトル要素Ｑj(t-i)の表現をスキャンする工程と、
ｅ３）  式（２）を利用する状態変数置換工程を通して、前記ベクトル要素Ｑj(t-i)の表現においてｔmaxからｔmax-1へ後方時間インデックス遷移を実行する工程と、
ｅ４）  ｔmaxを１だけ減ずると共に、ｔmaxがt-nよりも大きい間において前記ステップｅ２）からｅ４）を繰り返す工程とを備える工程とを
備えることを特徴とする方法。
【請求項２】
並列度ｎの並列ターボ符号化ブロックであって、
ａ）  入力信号Ｉ(t)のｎサンプル（Ｉ(t-1),...,Ｉ(t-n)）を、前記並列ターボ符号化ブロックに格納するための手段（Ｉ0,...,Ｉ7）と、
ｂ）前記並列ターボ符号化ブロックの少なくとも１の出力信号Ｑj(t)のｎサンプル（Ｑj(t),...,Ｑj(t-(n-1)）)を格納するための、少なくとも１の手段（Ｑ0,...,Ｑ7）と、
ｃ）  遅延ユニット（Ｘ１,...,ＸＮ）の列を備え、並列処理に適応され、前記列の少なくとも２つの遅延ユニットＸ１、・・・、ＸＮが、前記入力信号Ｉ(ｔ)のｎ個のサンプルI(t-1),...,I(t-n)のサブセットを直接受け、前記並列化ターボ符号化ブロックの少なくとも１つの遅延ユニットＸ１、・・・、ＸＮの出力信号が、前記並列化ターボ符号化ブロックの少なくとも２つの遅延ユニットへ供給されるように、前記入力信号Ｉ（ｔ）のｎ個のサンプルの並列処理に適応されたターボ符号化手段とを備え、
0004713039.tif 000039
に対応するシリアルターボ符号化ブロックから導出可能な構造を、前記ターボ符号化手段が請求項１に記載の並列化されたターボ符号化を行なう際に有することを特徴とする並列ターボ符号化ブロック。
【請求項３】
前記並列度が２であり、Ｎ＝３，Ｍ＝１、α＝［0，1，1］、β＝［1，1，0，1］である場合に、前記ターボ符号化手段の構造が
0004713039.tif 000040
であることを特徴とする請求項２に記載の並列ターボ符号化ブロック。
【請求項４】
前記並列度が４であり、Ｎ＝３，Ｍ＝１、α＝［0，1，1］、β＝［1，1，0，1］である場合に、前記ターボ符号化手段の構造が
0004713039.tif 000041
0004713039.tif 000042
であることを特徴とする請求項２に記載の並列ターボ符号化ブロック。
【請求項５】
前記並列度が８であり、Ｎ＝３，Ｍ＝１、α＝［0，1，1］、β＝［1，1，0，1］である場合に、前記ターボ符号化手段の構造が
0004713039.tif 000043
0004713039.tif 000044
であることを特徴とする請求項２に記載の並列ターボ符号化ブロック。
【請求項６】
コンピュータの内部メモリに直接にロード可能なコンピュータプログラムであって、
前記コンピュータプログラムがコンピュータ上で実行される場合に、請求項１に記載の方法を実行するためのソフトウェアコード部を備えることを特徴とするコンピュータプログラム。
【請求項７】
前記ソフトウェアコード部が、ＶＨＤＬ形式であることを特徴とする請求項６に記載のコンピュータプログラム。
【請求項８】
前記ソフトウェアコード部が、
0004713039.tif 000045
0004713039.tif 000046
0004713039.tif 000047
0004713039.tif 000048
0004713039.tif 000049
0004713039.tif 000050
END rtl;
のように定義されることを特徴とする請求項７に記載のコンピュータプログラム。
【発明の詳細な説明】
【０００１】
［発明の属する技術分野］
本発明は、ターボ符号器の実装に関連する。より詳細には、本発明はターボ符号器の実装の並列化に関連する。
【０００２】
［従来の技術］
電気通信システムの送信機のベースバンド部は大抵の場合、送信ビットの汎用エンコーダを他のパーツと共に含むものである。エンコーダは、冗長な情報を到来したビットサイズｋのデータストリームに追加するものである。これにより、ビット数は符号化レートｒに基づき係数１／ｒ倍で増加する。現在、符号化レート１／２及び１／３が公に利用されているが、他のレートも同様に利用することができる。従って、符号化されていないＫビットの各ブロックについて、上記エンコーダはＫ／ｒ符号化ビットのブロックを出力する。
【０００３】
電気通信システムにおけるデータストリームの受信側では、いくつかのビットがエアインタフェースでの送信において破壊されている場合でも、オリジナルデータストリームが受信機の符号化されたデータブロックから再計算される。
【０００４】
最近は、通信データの送信におけるエラー制御のためにターボ符号器が導入されている。一般には、ターボ符号化は、送信に先立ち同一情報シーケンスの異なるインタリーブバージョンに２以上のコンポーネント符号を適用することを含む。公知技術としてのターボ符号化には、たとえば、Berrou等の”Turbo-codes（ターボ符号）”IEEE International Communication Conference,pp.1064-1070,May 1993やSklarの"A Primer on Turbo Code Concepts（ターボ符号概念入門）",IEEE Communications Magazine,pp.94-102,December 1997,があり、ここで与えられるであろうさらなる詳細や、上記文献はここにおいて引用により記載に代えるものである。
【０００５】
図８はターボ符号器の一例を示す。図８に示すように、ターボ符号器は、同一構成の２つのターボ符号器ブロックＴＣＢ１とＴＣＢ２から構成される。２つのターボ符号器ブロックの相違は、一方が入力ブロックのビットを順序不変で受信し、他方がインタリーブされた順序で入力ビットを受信することである。各入力ビットについて、出力０，１，２のそれぞれにおいて３出力ビットが生成される。
【０００６】
図８に示すように、ターボ符号器ブロックＴＣＢ１は第１のＸＯＲゲート１００を入力段に備え、第２のＸＯＲゲート１０２を出力段に備える。その間において、３つの遅延ユニット１０４から１０８が存在し、各入力ビットを遅延させる。同様に、ターボ符号器ブロックＴＣＢ２は、第３のＸＯＲゲート１１０を入力段に、第４のＸＯＲゲート１１２を出力段に備える。その間において、３つの遅延ユニット１１４から１１８が存在し、各入力ビットを遅延させる。
【０００７】
さらに図８に示されるように、ターボ符号器への入力信号は、ターボ符号器ブロック１へ直接供給され、その一方で、入力信号はインタリーバ１２０を介して、第２のターボ符号器ブロックＴＣＢ２へ供給される。出力０については、入力信号がそのまま何の修正もされずに転送される。
【０００８】
図８に示すターボ符号器のためのパラメータは、各ターボ符号器ブロックにおける遅延ユニットの番号であり、さらに、異なるＸＯＲゲート１００，１０２，１１０及び１１２への入力信号の供給を示すものである。
【０００９】
図８に示すターボ符号器を端的に実現するには、入力及び出力レジスタ（図８には不図示）と同様に、ターボ符号化がビットワイズ手法（bitwise manner）で実行されるように、遅延ユニットを利用することになる。ここでは、遅延ユニットの出力がそれ以前のクロックサイクルにおける入力を表すように、すべての遅延ユニットが同一システムクロックで動作する。
【００１０】
遅延ユニットをシリアルに利用してターボ符号器を端的に実現することにより、多くのレジスタやＸＯＲゲートを必要としない一方で、その主な不利益は、ターボ符号化がシリアルに実行されることにある。このことは、システムクロックの１サイクルで１ビットしか符号化されないことを意味する。結果として、高ビットレートを必要とする場合には、システムクロック周波数は非常に高いものとなってしまう。
【００１１】
もし、たとえば１２００チャネルが符号化されるとして、それぞれが１ミリ秒に１００ビットを有する音声チャネルに関連するならば、必要なシステムクロック周波数は１２０Ｍｈｚである。
【００１２】
このように、たとえばＡＳＩＣやＦＰＧＡ技術を利用して上述のターボ符号器を実現することは非常に困難である。
【００１３】
専用ターボ符号器を各チャネルに備えることは一つの解決策である一方で、異なるチャネルは依然として並列に符号化されなければならないので、入力及び出力のビットストリームの複雑なハンドリングが要求される。このためには、正しい入力を正しい時間に正しいターボ符号器に供給するための非常に複雑な制御ロジックが導入されることになる。さらに、異なるターボ符号器の出力の扱いもまた、同様に複雑になるであろう。
【００１４】
［発明の概要］
上記の観点から、本発明の目的はターボ符号器ブロックの処理速度を向上させることにある。
【００１５】
本発明によれば、この目的はターボ符号器の並列化（parallel realization）によって達成される。
【００１６】
これまで、ターボ符号器ブロックの構造は、ターボ符号器ブロックの並列化のための基礎をなす汎用形式の表現で記載されていた。
【００１７】
特に、ターボ符号器ブロックへの入力サンプルは、並列度を表すnを用いて、n次元の並列入力ベクトルの要素として変換される。
【００１８】
ターボ符号器ブロックの汎用形式の表現は、この並列入力ベクトルの、少なくとも１の並列出力ベクトルへのマッピングを導くために利用される。
【００１９】
より詳細には、内部状態変数置換処理（internal state variable substitution process）が、汎用形式表現における各内部状態変数に適用される。ここで、内部状態変数の表現は、それ以前に決定された時間インデックスが置換された内部状態変数の表現を利用した後方時間インデックス遷移の実行を通して置換された最大時間インデックス要素についてスキャンされる。これらの置換ステップは、各内部状態変数の表現が入力ベクトル要素及び並列化の度合いにより遅延するターボ符号器の内部状態変数の値にのみ依存するまで繰り返される。
【００２０】
さらに、置換処理は各並列出力ベクトルの各要素について同様に実行される。再度、各出力ベクトル内の各ベクトル要素の表現は、最大時間インデックスを有する内部状態変数についてスキャンされ、ベクトル要素の表現における後方時間インデックス遷移の決定が、各ベクトル要素の表現が入力ベクトル要素及び並列化の度合いにより遅延するターボ符号器の内部状態変数の値にのみ依存するまで再帰的行われる。
【００２１】
それゆえに、本発明は、処理速度を向上させるために、多くのシリアルターボ符号器の代わりに唯一の並列化ターボ符号器ブロックのみを必要とするような、ターボ符号器ブロックの並列化を提案する。これは、複数のターボ符号器ブロックに必要な複雑な入力及び出力制御を不要とする決定的な利益をもたらすものである。
【００２２】
たとえば、４ビット並列ターボ符号器ブロックでは、上記の例におけるシステムクロック周波数は３０Ｍｈｚの範囲になるので、ＦＰＧＡやＡＳＩＣ技術を利用して簡単に実現することができる。ゆえに、並列化されたターボ符号器ブロック及びそこから導き出されるターボ符号器は、ＦＰＧＡ又はＡＳＩＣ技術ベースの実装を利用するための所定のスペックに見合う並列度に応じて、シリアルターボ符号器を越える高速度化を達成できる。このように、並列化されたターボ符号器ブロックは、異なるチャネルを同時に複雑にハンドリングする必要もなく、ベースバンド部における低処理遅延を実現する複雑な電気通信システムの基礎を形成するものである。
【００２３】
さらに、並列化されたターボ符号器ブロック及び上記ターボ符号器は、シリアルターボ符号器と比較して、論理ゲート及びレジスタの追加余剰が最小限ですむ。
【００２４】
また、ターボ符号器の前及びその後に続く処理ブロックもまた並列処理手法をサポートする場合は、シリアルターボ符号器及び（パラレルツーシリアル又はその逆の）付加的コンバータを備えるエンコーダブロックに比べて、エンコーダブロック全体として完全な符号化ブロックが必要とするロジック及びレジスタはより少なくなる。
【００２５】
本発明の好適な実施形態によれば、コンピュータ上で走らせる場合に、本発明の並列化方法に対応するステップを実行するソフトウェアコード部を備えるコンピュータの内部メモリに直接ロード可能なコンピュータプログラム製品をも提供される。より好ましくは、ソフトウェアコード部は、ＶＨＤＬタイプのものである。
【００２６】
それゆえに、開発サイクルが少なく、デザインをたとえばＡＳＩＣやＦＰＧＡなどの異なるハードウェア技術にマッピングする場合の高い柔軟性を有する並列ターボ符号器設計の高速な開発及び修正の基礎を実現するものである。
【００２７】
［好適な実施形態の説明］
以下において、本発明の好適な実施形態が図１乃至図７を参照して記載される。
【００２８】
特に、図１及び図２に示すようなターボ符号器ブロックの形式的な記載は、本発明に対応した並列化方法の記載の基礎として与えられるであろう。
【００２９】
図３を参照して、データ入力のタイムシーケンシャルストリームが、並列化されたターボ符号器ブロックにおいて扱われるために、どのように並列入力ベクトルにマッピングされるかが記載されてもよい。また、この並列化されたターボ符号器ブロックの並列出力ベクトルがデータ出力のタイムシーケンシャルストリームにマッピングされるかが記載されてもよい。
【００３０】
これに続いて、本発明に対応した並列化方法を利用するターボ符号器ブロックの並列化を実現するための異なる例は、図４から図７を参照して記載される。
【００３１】
［１．シリアル型のターボ符号器ブロック、汎用記載］
図１は、シリアル型のターボ符号器ブロックのブロック線図である。
【００３２】
図１に示すように、ターボ符号器ブロックは、Ｎ個の遅延ユニット、Ｘ１，Ｘ２，・・・ＸＮを、たとえばフリップフロップ等で備える。遅延ユニットＸ１，Ｘ２，・・・ＸＮの出力信号は、それぞれＸ１(t)，Ｘ２(t)，・・・ＸＮ(t)とし、ここでｔは、正数の時間を表す指数である。第１の遅延ユニットＸ１の入力には、入力ＸＯＲゲート１２が提供され、最後の遅延ユニットＸＮの出力には、出力ＸＯＲゲート１４が提供される。
【００３３】
図１に示すように、入力信号Ｉ(t)は入力遅延ユニット１６を介して供給され、出力ＸＯＲゲート１４の出力信号は、出力遅延ユニット１８を介して転送される。
【００３４】
また、図１を参照すると、出力信号Ｘ１(t)，Ｘ２(t)，・・・ＸＮ(t)は、接続α１、α２，・・・、αＮを介して入力ＸＯＲゲート１２に提供される。また、遅延ユニットに対する入力信号は、接続β０、β１，・・・、βＮ−１を介して出力ＸＯＲゲート１４へ提供される。さらに、遅延ユニットＸＮの出力は、接続βＮを介して出力ＸＯＲゲート１４へ供給される。
【００３５】
形式的に０又は１の値を、接続α１、α２，・・・、αＮのそれぞれ、さらに接続β０、β１，・・・、βＮ−１のそれぞれに割り当てると、Ｎ個の遅延ユニットを有するどんなシリアルターボ符号器ブロックも、以下の式に従って記載することができる。
【００３６】
0004713039.tif 000002
0004713039.tif 000003
0004713039.tif 000004
【００３７】
図２に示すように、単一出力を有するターボ符号器ブロックについて上記のように与えられる一般的な表現は、シリアル型で複数の出力を有するターボ符号器ブロックについて一般化されてもよい。
【００３８】
図１のように、図２もまた、遅延ユニットＸ１，Ｘ２，・・・ＸＮについて、その出力が、それぞれＸ１(t)，Ｘ２(t)，・・・ＸＮ(t)である。遅延ユニットＸ１，Ｘ２，・・・ＸＮのそれぞれの出力信号Ｘ１(t)，Ｘ２(t)，・・・ＸＮ(t)は、図１においてすでに記載されているように、接続α１、α２，・・・、αＮを介して入力ＸＯＲゲート１２に提供される。また、入力データストリームは、入力遅延ユニット１６を介して入力ＸＯＲゲート１２に提供される。
【００３９】
図２に記載のシリアルターボ符号器ブロックは、複数の出力Ｑ１(t)，・・・、ＱＭ(t)が与えられる点で、上記のターボ符号器ブロックとは異なる。図２に示されるように、各出力について、関連する出力ＸＯＲゲート１４−１、・・・・、１４−Ｍが存在する。そのような出力ＸＯＲゲート１４−１、・・・・、１４−Ｍのそれぞれにおいて、関連する出力遅延ユニット１８−１、・・・・、１８−Ｍが接続されている。
【００４０】
図２にさらに示されているように、遅延ユニットＸ１，Ｘ２，・・・ＸＮへの各入力は、第１の出力ＸＯＲゲート１４−１へ、接続β1,0、β1,1，・・・、β1,N-1を介して供給され、さらに、第２の出力ＸＯＲゲート１４−２へも、接続β2,0、β2,1，・・・、β2,N-1を介して供給され、以下同様に続く。さらに、最終の遅延ユニットＸＮの出力は、接続β1,Nを介して、第１の出力ＸＯＲゲート１４−１へ供給され、接続β1,Nを介して、第１の出力ＸＯＲゲート１４−１へ供給され、接続β2,Nを介して、第２の出力ＸＯＲゲート１４−２へ供給され、以下同様に続く。最後に、各出力ＸＯＲゲートの出力信号が、ターボ符号器ブロック出力信号Ｑ１(t)，・・・、ＱＭ(t)を導くために遅延される。
【００４１】
図２のターボ符号器ブロックの形式的な表現は、複数の出力Ｑ１(t)，・・・、ＱＭ(t)について関連する出力表現が以下のように一般化される点で、上記のターボ符号器ブロックとは異なる。
【００４２】
0004713039.tif 000005
【００４３】
上記の１以上の出力を有するシリアル型のターボ符号器ブロックの形式表現は、本発明に対応する並列化方法の表現の基礎となるであろう。
【００４４】
しかしながら、以下に本発明に対応する並列化方法を記載する前に、まず、シリアルデータ入力ストリームの並列入力ベクトルへのマッピングと、並列出力ベクトルをシリアルデータ出力ストリームへマッピングし直すことについて、図３を参照して説明する。
【００４５】
[２．ｎ次の並列型ターボ符号器ブロック]
図３の左側上部において、シリアルデータ入力ストリームに対応するタイムシーケンスが示されている。同様に、図３の右側上部には、シリアル出力ストリームに対応する時間シーケンスが示されている。
【００４６】
図３に示すように、並列入力ベクトルＩ0,Ｉ1,Ｉn-1は、データ入力値Ｉ(t-1)、Ｉ(t-2)、・・・、Ｉ(t-n)の系列から以下のように導き出されてもよい。
【００４７】
Ｉ(t-1)＝Ｉ0(p-1)
Ｉ(t-2)＝Ｉ1(p-1)
・
・
・
・
Ｉ(t-n)＝Ｉn-1(p-1)
シリアルデータ入力ストリームから導き出された図３に示す並列入力ベクトルが、以下に記載する並列ターボ符号器ブロックにおいて処理されるとすると、あるものは並列出力ベクトルＱj0、・・・、Ｑjn-1に到達する。
【００４８】
図３に示すように、この並列出力ベクトルは、シリアルデータ出力ストリームＱj(t)，・・・、Ｑj(t-(n-1))へマッピングし直されてもよい。
【００４９】
Ｑj(t)＝      Ｑj0(p)
Ｑj(t-1)＝    Ｑj1(p)
・
・
・
Ｑj(t-(n-1))＝Ｑjn-1(p)
jε[1,...,M]
【００５０】
［２．１  並列化の一般的なアウトライン］
本発明によれば、異なる時間スケールがシリアルドメイン及びパラレルドメインにおいて利用される。言い換えれば、シリアルタイムドメインにおけるｎ個のシリアルデータ入力のセットが、並列タイムドメインｐにおける１クロックサイクルで並列に処理される並列入力ベクトルに対応する。
【００５１】
故に、結果としての並列システムクロックは、同量のデータを処理する場合に想定されるシリアルシステムクロックよりもｎ倍遅くなる。それゆえに、シリアル時間表現（ｔ−１）は、並列時間表現（ｐ−１）と置き換えられてもよく、ｎ個のシリアル時間入力のシーケンスは、１並列クロックサイクル前の（ｐ−１）、単一並列入力ベクトルとして書き換えられる。同様に、出力の系列も現在の並列サイクル（ｐ）についての並列出力ベクトルとして書き換えられる。
【００５２】
図１及び図２に応じたターボ符号器ブロックの一般的表現及び、さらに、シリアルデータ入力ストリームの並列入力ベクトルへのマッピング、及び並列出力ベクトルのシリアル出力データストリームへの逆マッピングを利用するので、本発明のアプローチは、ｎ個のシリアルデータ入力アイテムを有する並列入力ベクトルの、並列化されたターボ符号器ブロックへの供給、及び、それぞれがｎ個の出力データアイテムを備えるＭ個の出力ベクトルの計算に依拠する。
【００５３】
出力ベクトルのｎ個の要素は、シリアルターボ符号器ブロックのｎシステムクロック前における（並列化されたターボ符号器ブロックにおける１サイクルに対応する）内部遅延ユニットＸ１，・・・ＸＮの値と、さらには、並列入力ベクトルにおいてこのｎサイクルにおいて加算されたすべての入力データアイテムにのみ依存する。
【００５４】
以下に記載するように、本発明のアプローチは、並列出力ベクトルの出力要素と、並列ターボ符号器ブロックの内部遅延ユニットの次の並列サイクルについての、並列ターボ符号器ブロックの内部遅延ユニットの出力値と以前の並列サイクルの並列入力ベクトルに依存した出力値を表す等式の決定に依存している。
【００５５】
シリアル表現（たとえば、式(1.Q)）を参照すると、時間ｔにおけるシリアル型のターボ符号器ブロックの各出力値は、遅延ユニットＸ１，・・・、ＸＮの時間ｔ−１における出力値及び時間ｔ−１における入力データアイテムから計算される。
【００５６】
内部遅延ユニットのすべての出力値を、シリアル実装における１システムクロックサイクル前における値で置換し、この置換ステップをｎシリアルシステムクロックサイクル前の出力値のみが残るまで繰り返すことにより、ｎシリアルサイクル又は同等な１並列サイクルについての出力結果の並列計算式が導出される。
【００５７】
言い換えれば、これらの等式は、ｎシリアルクロックサイクルが１パラレルクロックサイクルを表すので、並列化されたターボ符号器ブロックの基礎を形成する。
【００５８】
［２．２  第１の内部状態についての後方時間インデックス置換］
上述の再帰的置換処理の準備において、第１の遅延ユニットＸ１の出力を以下のように表現することができる。
【００５９】
0004713039.tif 000006
【００６０】
これは、シリアルクロックサイクルｔ−１，・・・、ｔ−（ｎ−１）の内部状態を表現するために、以下において第１の内部状態と呼ばれる。
【００６１】
0004713039.tif 000007
【００６２】
［２．３  更なる内部状態（i=2,...,N）についての後方時間インデックス置換］
付随する遅延ユニットＸ２，・・・、ＸＮの出力（式（1.x2）,...,（1.xN）参照）を以下のように表現することができる。
Ｘi(t)＝Ｘi-1(t-1)
シリアルクロックサイクルｔ−１，・・・、ｔ−（ｎ−１）の内部状態を表現するために、これは更なる内部状態と呼ばれる。
Ｘi(t-1)＝Ｘi-1(t-2)                 （2.xi.1）
・
・
・
Ｘi(t(n-1))＝Ｘi-1(t-n)              （2.xi.n-1）
【００６３】
［２．４  出力ベクトル要素についての後方時間インデックス置換］
さらに、ターボ符号器ブロックの少なくとも１の出力（式(1.Q)参照）についての表現は、
0004713039.tif 000008
シリアルクロックサイクルｔ−１，・・・、ｔ−（ｎ−１）についての、以下の出力を表現するために利用されてもよい。
0004713039.tif 000009
0004713039.tif 000010
【００６４】
［２．５  再帰的後方時間インデックス遷移ステップによる並列化］
［２．５．１  目的］
すでに上記において述べた本発明に対応する並列化処理の目的は、各並列出力ベクトル（図２に示す出力１、・・・、Ｍごとに一つ）の要素を、ｎシリアルデータ入力アイテム及び現在の並列サイクルよりも１並列サイクル（ｎシリアルサイクルに相当）前の内部状態の関数として表現することである。
【００６５】
0004713039.tif 000011
【００６６】
［２．５．２  再帰的時間インデックス遷移ステップ］
まず、この目的を実現するためにすべての内部状態が並列化される。すべての内部状態Ｘ１(t)，Ｘ２(t)，・・・ＸＮ(t)について、この内部状態の表現において使用される最大時間インデックスが、まず動作のシリアル表現に対応するｔ−１にセットされる。
【００６７】
全ての内部状態の表現が考慮され、上記の式（２）のうちの一つを利用して、この現在の最大時間インデックスに先立つ時間インデックスに依存する同一の内部状態を表現する形式により、それぞれが現在の最大時間インデックスに依存する内部状態変数を置換するように再帰的にスキャンされる。
【００６８】
それゆえに、考慮された内部状態の表現は、現在の最大時間インデックスから、これに先行する時間インデックスへの遷移を行なうことで修正される。この遷移を以下では後方時間インデックス遷移と呼ぶ。後方時間インデックス遷移が、現在の最大時間インデックスに依存する全ての内部状態変数実行されると、現在の最大時間インデックスは１減少する。
【００６９】
この処理の再帰的反復は、最大時間インデックスが、t-nになるまで継続される。この理由は、この点において、サイクルｔ（ｐ）における考慮される内部状態は、時間ｔ−ｎ（ｐ−１）における内部状態及びシリアル入力データアイテムＩ（ｔ−１）、・・・、Ｉ（ｔ−ｎ）にのみ依存して記載されるからである。
【００７０】
つぎに、再度、上述の後方時間インデックス遷移を内部状態について再帰的に実行することにより、各出力ベクトルの全ての要素が並列化される。
【００７１】
さらに、再帰的時間インデックス遷移ステップの途中段階における、現在の最大時間インデックスの修正では、内部状態のそれぞれの表現及び出力ベクトルの要素を、（a XOR a XOR b = b）の関係を利用することにより単純化することができる。言い換えれば、重複するターム（a XOR a）は、それぞれの表現においてキャンセルされる。
【００７２】
図２に示すようなもっとも一般的な形式におけるシリアルターボ符号器ブロックの再帰的並列化は、以下のようにまとめることができる。
【００７３】
procedure recursive_parallelization(n)
0004713039.tif 000012
0004713039.tif 000013
0004713039.tif 000014
【００７４】
以下において、上記の並列化アプローチの適用について説明するために、この並列化処理はより詳細に特定の例と関連して説明される。
【００７５】
以下に示すように、各並列化ターボ符号器ブロックは、例えば、フリップフロップI0,...,I7の第1のグループのような、入力信号Ｉ(ｔ)のｎ個のサンプルI(t-1),...,I(t-n)を並列化ターボ符号器ブロックにさらに供給するための格納部と、例えば、フリップフロップQ0,...,Q7の第2のグループのような、並列化ターボ符号器ブロックの少なくとも１つの出力信号Qj(ｔ),j=1,...,Mのｎ個のサンプルQj(t),...,Qj(t-(n-1))を格納する少なくとも１つの格納部を備える。
【００７６】
さらに、並列化ターボ符号器ブロックは、ｎ個の遅延ユニットＸ１、・・・、ＸＮの列（bank）を備え、当該列の少なくとも２つの遅延ユニットＸ１、・・・、ＸＮが、入力信号Ｉ(ｔ)のｎ個のサンプルI(t-1),...,I(t-n)のサブセットを直接受け、並列化ターボ符号器ブロックの少なくとも１つの遅延ユニットＸ１、・・・、ＸＮの出力信号が、並列化ターボ符号器ブロックの少なくとも２つの遅延ユニットへ供給されるように、入力信号Ｉ（ｔ）のｎ個のサンプルの並列処理に適応されている。
【００７７】
図４は、図８に示すターボ符号化において利用される、シリアル型の特定のターボ符号器ブロックのブロック線図である。
【００７８】
ここで、入力遅延ユニット１６及び出力遅延ユニット１８の提供は、シリアル実装する場合の前提条件ではないが、並列化された場合に、図３に示すような入力ベクトル及び出力ベクトルの要素を訂正するために必要である。
【００７９】
図４に示すシリアルターボ符号器ブロックは、上記の式（１）に従い形式的表現を利用してＮ＝３，Ｍ＝１、α＝［α１，α２，α３］＝［0，1，1］、β＝［β１，β２，β３，β４］＝［1，1，0，1］とすることにより簡単化してもよい。以下においては、いかにしてこのシリアルターボ符号器ブロックが、ｎ＝２，４及び８ビットの並列ターボ符号器ブロックに並列化されるかを説明する。
【００８０】
［３．１  例：Ｎ＝３，Ｍ＝１、α＝［0，1，1］、β＝［1，1，0，1］の場合の２ビット並列ターボ符号化］
式（１）より、図４に示されるターボ符号器ブロックについての表現として、以下を得ることができる。
【００８１】
0004713039.tif 000015
【００８２】
２シリアル時間サイクルについての後方時間インデックス遷移が必要である。
【００８３】
0004713039.tif 000016
0004713039.tif 000017
【００８４】
図５は、この並列化処理の結果を示す。すなわち、図４に示すターボ符号器ブロックを２ビット並列化した場合のブロック線図である。
【００８５】
［３．２  例：Ｎ＝３，Ｍ＝１、α＝［0，1，1］、β＝［1，1，0，1］の場合の４ビット並列ターボ符号化］
式（１）より、図４に示されるターボ符号器ブロックについての表現として、以下を得ることができる。
【００８６】
0004713039.tif 000018
【００８７】
４シリアル時間サイクルについての後方時間インデックス遷移が必要である。
【００８８】
0004713039.tif 000019
0004713039.tif 000020
0004713039.tif 000021
【００８９】
図６は、この並列化処理の結果を示す。すなわち、図４に示すターボ符号器ブロックを４ビット並列化した場合のブロック線図である。
【００９０】
［３．３  例：Ｎ＝３，Ｍ＝１、α＝［0，1，1］、β＝［1，1，0，1］の場合の８ビット並列ターボ符号化］
式（１）より、図４に示されるターボ符号器ブロックについての表現として、以下を得ることができる。
【００９１】
0004713039.tif 000022
0004713039.tif 000023
【００９２】
８シリアル時間サイクルについての後方時間インデックス遷移が必要である。
【００９３】
0004713039.tif 000024
0004713039.tif 000025
0004713039.tif 000026
0004713039.tif 000027
0004713039.tif 000028
0004713039.tif 000029
【００９４】
図７Ａ及び図７Ｂは、この並列化処理の結果を示す。すなわち、図４に示すターボ符号器ブロックを８ビット並列化した場合のブロック線図である。
【００９５】
［４．ＶＨＤＬコード］
上記のステップ・バイ・ステップの再帰的並列化は、異なる代替デザインを比較するために論理合成ツールとともに利用することもできる。いかなる特定のシステムにも制限することなく、ここでは、論理合成ツールを利用した論理回路の設計例として、超高速ハードウェア記述言語ＶＨＤＬを典型的な例として引用する。
【００９６】
ＶＨＤＬコードを利用して、ターボ符号器ブロックを並列化を実現することの利点は、ＡＳＩＣやＦＰＧＡのような特定の技術に拘束されることなく、非常に短時間で設計内容を認識できることである。
【００９７】
このように、実際の技術はターボ符号器ブロック並列化結果を通して規定されないが、符号化のために論理合成ツールにより扱われるパラメータとして設定され、また、異なる設計オプションを比較するために簡単に変更することができる。
【００９８】
以下において、ＶＨＤＬコードは、図５、図６及び図７に示す２、４及び８ビット並列化ターボ符号器ブロックについてリストされる。ＶＨＤＬコード言語の使用は、技術として公然知られたものであり、上記の並列化結果との関係は自明であるから、詳細についての説明はここでは行わない。
【００９９】
0004713039.tif 000030
0004713039.tif 000031
0004713039.tif 000032
0004713039.tif 000033
0004713039.tif 000034
0004713039.tif 000035
END rtl;
【０１００】
［５．ターボ符号化の実現］
本発明の背景となる技術についての上記記載は図８と関連して行われた一方で、図８はまた、以下に記載するように本発明にも関連する。
【０１０１】
これまで記載した本発明のように、Ｍ個の出力を有するターボ符号器ブロックの並列化について述べる。しかしながら、本発明によれば、完全なターボ符号化の構成は、図８に示されるような並列化された２つのターボ符号器ブロックの例示を必要とする（ここでは、両方のブロックにおいてＭ＝１が想定される。）。
【０１０２】
あるターボ符号器ブロックは、図８における出力１を導くノーマルな入力データストリームに関連し、他方は、出力２を導くインタリーブされた入力データストリームに関連する。入力データストリームは、出力０へも直接に転送されるので、ターボ符号化の３出力が、パラレルクロックサイクルについて３ｎビットの幅を有する。ここで、ｎは並列度である。
【図面の簡単な説明】
【図１】  １出力を備えるターボ符号器ブロックのブロック線図である。
【図２】  複数出力を備えるターボ符号器ブロックのブロック線図である。
【図３】  並列入力ベクトルへのデータ入力の時間系列ストリームのマッピングを表す図である。
【図４】  シリアル型の特定のターボ符号器ブロックのブロック線図である。
【図５】  図４に示すターボ符号器ブロックを２ビット並列化した場合のブロック線図である。
【図６】  図４に示すターボ符号器ブロックを４ビット並列化した場合のブロック線図である。
【図７Ａ】  図４に示すターボ符号器ブロックを、入力部を８ビット並列化した場合のブロック線図である。
【図７Ｂ】  図４に示すターボ符号器ブロックの出力部を並列化した場合のブロック線図である。
【図８】  ターボ符号器ブロックＴＣＢ１及びＴＣＢ２と同様にインタリーバを備えるターボ符号器の構成図である。
【図１】
0004713039.tif 000051
【図２】
0004713039.tif 000052
【図３】
0004713039.tif 000053
【図４】
0004713039.tif 000054
【図５】
0004713039.tif 000055
【図６】
0004713039.tif 000056
【図７Ａ】
0004713039.tif 000057
【図７Ｂ】
0004713039.tif 000058
【図８】
0004713039.tif 000059