(57)【特許請求の範囲】
【請求項１】
高速フーリエ変換の計算を実行する少なくとも一つのバタフライ演算器を備えるデジタルデータ処理プロセッサであって、
前記バタフライ演算器は、複素乗算を行う第１のステージ（１２；１２’）と、前記第１のステージの出力データを入力として複素加算／減算を行う第２のステージ（２６）とを備え、
前記第１および第２のステージのそれぞれは、複数の加算／減算ハードウェアモジュールおよび前記複数の加算／減算ハードウェアモジュール間を接続し、データ転送を行う複数のリンクを備え、前記複数のリンクはマルチプレクサを含み、
前記第１のステージ（１２’）は、
４つの実数の加算／減算ハードウェアモジュール（１０４，１０８，１１０，１１４）と、前記４つの実数の加算／減算ハードウェアモジュール（１０４，１０８，１１０，１１４）の入力に接続されるマルチプレクサ（１０６，１１２，１１６）で構成され、入力データ（Ｒｅｆ，ａ，ｂ，ｃ，ｄ，ｅ／Ｐ０，ｆ／Ｐ１）に対して実数の加算／減算を行う第１のレベル（９８）、
３つの実数の乗算器（１１８，１２０，１２２）で構成され、前記第１のレベルの出力データに対して実数の乗算を行う第２のレベル（１００）、および
２つの実数の加算／減算ハードウェアモジュール（７６，８６）と、前記２つの実数の加算／減算ハードウェアモジュール（７６，８６）の入力に接続されるマルチプレクサ（１２４，１２６，１２８，１３０）で構成され、前記第１のレベルの出力データ及び／又は前記第２のレベルの出力データに対して実数の加算／減算を行う第３のレベル（７６，８６，１２４，１２６，１２８，１３０）、を備え、
前記第２のステージ（２６）は、４つの実数の加算／減算ハードウェアモジュール（７８，８２，８８，９２）と、前記４つの実数の加算／減算ハードウェアモジュール（７８，８２，８８，９２）の入力に接続されるマルチプレクサ（８０，８４，９０，９４）を備え、
前記バタフライ演算器は、前記第１のレベル（９８）の加算／減算ハードウェアモジュールのうちの２つの加算／減算ハードウェアモジュール（１０４，１１４）、前記第３のレベル（７６，８６，１２４，１２６，１２８，１３０）の加算／減算ハードウェアモジュールのうちの１つの加算／減算ハードウェアモジュール（８６）、および前記第１のステージ（１２’）と前記第２のステージ（２６）に含まれる全てのマルチプレクサ（１０６，１１２，１１６，１２４，１２６，１２８，１３０，８０，８４，９０，９４）をプログラム可能な少なくとも１つのパラメータ（β）に対応して再構成することによって、高速フーリエ変換の演算を実行する第１の構成と、ビタビアルゴリズムの、ブランチメトリック値、パスメトリック値、および生き残りパスの計算を実行する第２の構成との間で切り替えられることを特徴とするデジタルデータ処理プロセッサ（９６）。
【請求項２】
前記少なくとも１つのパラメータ（β）は単一の２進パラメータ（β）であり、前記第１のレベル（９８）の加算／減算ハードウェアモジュールのうちの２つの加算／減算ハードウェアモジュール（１０４，１１４）、および前記第３のレベル（７６，８６，１２４，１２６，１２８，１３０）の加算／減算ハードウェアモジュールのうちの１つの加算／減算ハードウェアモジュール（８６）は、それぞれのモジュールの加算器の構成と減算器の構成との間で前記単一の２進パラメータ（β）に対応して切り替えられ、前記単一の２進パラメータ（β）が２進値の一方を取る場合は前記バタフライ演算器による高速フーリエ変換の計算を行う前記第１の構成になり、前記単一の２進パラメータ（β）が２進値のもう一方を取る場合は前記バタフライ演算器によるブランチメトリック値とパスメトリック値と生き残りパスの計算を行う前記第２の構成になる、請求項１に記載のデジタルデータ処理プロセッサ（９６）。
【請求項３】
前記全てのマルチプレクサ（１０６，１１２，１１６，１２４，１２６，１２８，１３０，８０，８４，９０，９４）は、２つの入力および１つの出力を備え、前記単一の２進パラメータ（β）に対応して前記２つの入力の一方を選択する、請求項２に記載のデジタルデータ処理プロセッサ（９６）。
【請求項４】
前記デジタルデータ処理プロセッサ（９６）は、複数の前記バタフライ演算器を備え、前記バタフライ演算器のそれぞれは、高速フーリエ変換の計算を実行する前記第１の構成と、ブランチメトリック値とパスメトリック値とビタビアルゴリズム実装の生き残りパスの計算を実行する前記第２の構成との間で切り替え可能なバタフライ演算器であって、前記デジタルデータ処理プロセッサ（９６）は、複数の前記バタフライ演算器を組み合わせることによって、Ｒａｄｉｘ−２タイプのトレリス構造のＣｏｏｌｅｙ−Ｔｕｋｅｙ型アルゴリズム法による高速フーリエ変換の計算と、４つの基準シンボルを持つトレリス構造のビタビアルゴリズムの計算を実行可能であることを特徴とする、請求項１〜３のうちいずれか一項に記載のデジタルデータ処理プロセッサ（９６）。
【請求項５】
送信／受信信号をマルチキャリア変調／復調し、畳み込み符号で処理した信号を復号化する移動通信端末であって、請求項１〜４のうちいずれか一項に記載のデジタルデータ処理プロセッサ（９６）を少なくとも１つ有し、少なくとも一つの前記デジタルデータ処理プロセッサ（９６）が畳み込み符号で処理した信号の復号化に用いられることを特徴とする移動通信端末（１３６）。
【請求項６】
ＯＦＤＭタイプの変調および復調を行う、請求項５に記載の移動通信端末（１３６）。
【請求項７】
マルチ規格タイプの移動通信端末（１３６）であって、実装したそれぞれの規格と互換性のあるＯＦＤＭ変調および復調を行う少なくとも１つの変調器／復調器と、実装したそれぞれの規格と互換性のある畳み込み符号で符号化した信号を復号化する少なくとも１つの復号化器とを有する、請求項６に記載の移動通信端末（１３６）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、高速フーリエ変換、すなわちＦＦＴ（英語の「Ｆａｓｔ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ」）または逆高速フーリエ変換、すなわちＩＦＦＴ（英語の「Ｉｎｖｅｒｓｅ  Ｆａｓｔ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ」）の計算を実行するためのデジタルデータの処理プロセッサに関する。本発明はまた、このようなプロセッサを少なくとも１つ備える移動通信端末にも係る。
【背景技術】
【０００２】
このようなプロセッサは、数多くの通信用途で使用法が見出され、とりわけ送信／受信した信号をマルチキャリア変調／復調する端末で使用される。実際この種の端末では、この変調／復調がとりわけソフトウェア無線または再構成可能な無線ＳＤＲ（英語の「Ｓｏｆｔｗａｒｅ  Ｄｅｆｉｎｅｄ  Ｒａｄｉｏ」）の枠組でＦＦＴ／ＩＦＦＴのデジタル計算を起こすことが一般に有利である。
【０００３】
ＳＤＲタイプの送信／受信端末とは、デジタル−アナログ変換をアンテナの最も近くで行う端末のことであり、こうすることによって端末が実行する変調／復調および符号化／復号化の処理がデジタル信号で行われる。このデジタル信号は実際に、再構成可能な処理に最適であり、つまりはさまざまな規格またはさまざまな進化に適応可能なものである。
【０００４】
例えば現在は、多数の無線通信規格が存在する。規格がこのように急速に増加した結果、異なる規格を管理できる端末の需要が増大している。計算能力には限度があり、プログラム可能な信号処理プロセッサは過度に電力を消費するため、これらの装置をこの需要に完全に対応するように適合させる対策は困難になっている。その結果、純粋にソフトウェアのみの対策は考えられず、ハードウェア演算器を使用せざるを得ない。
【０００５】
複数の規格を管理する第１の対策は、対象規格のさまざまな処理チェーンでそれぞれがハードウェア演算器を有するものを同じ端末内に並列させる方法である。この対策は実装が容易だが、使用するシリコン面積の点で効率的ではないという最大の欠点がある。
【０００６】
もう１つの対策は、さまざまな処理チェーンを設計し、これらの処理チェーンが機能モジュールの一部およびハードウェア演算器を共用化するようにする方法である。この第２の対策では、端末をパラメータ化し、該当するそれぞれの処理チェーンを実行するための再構成がパラメータ値の変更を１回しか必要としないようにする。とりわけ、ハードウェア演算器を共用化する技術が、Ｌ．Ａｌａｕｓらによる「Ｐｒｏｍｉｓｉｎｇ  ｔｅｃｈｎｉｑｕｅ  ｏｆ  ｐａｒａｍｅｔｒｉｚａｔｉｏｎ  ｆｏｒ  ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  ｒａｄｉｏ、ｔｈｅ  Ｃｏｍｍｏｎ  Ｏｐｅｒａｔｏｒｓ  Ｔｅｃｈｎｉｑｕｅ：ｆｕｎｄａｍｅｎｔａｌｓ  ａｎｄ  ｅｘａｍｐｌｅｓ（再構成可能な無線の有望なパラメータ化、共用演算器の技術：基礎および例）」と題した文献（Ｊｏｕｒｎａｌ ｏｆ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍｓ、ＤＯＩ１０．１００７／ｓ１１２６５−００９−０３５３−０４、２００９年３月１４日発行）に記載されている（非特許文献１）。
【０００７】
この文献は例として、ＦＦＴ／ＩＦＦＴ計算を行うハードウェア演算器は大多数の規格で必要なため、共用化できることが有利であると指摘している。実際、現在の通信規格または開発途中の通信規格のほとんどは、ＯＦＤＭ（英語の「Ｏｒｔｈｏｇｏｎａｌ Ｆｒｅｑｕｅｎｃｙ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅｘｉｎｇ：直交周波数分割多重」）タイプの変調に基づくものである。ＯＦＤＭ変調は、直交周波数に分割することによってデジタル信号を符号化する方法である。ＯＦＤＭ変調の原理は、独立周波数で同時に送信されるサブチャネルに分割して通信を多重化することにある。ＯＦＤＭ変調のまさに中核がＦＦＴ計算を有する。
【０００８】
ＦＦＴ演算器は、より一般には周波数領域で信号を受信する機能の基本演算器として働く。例えばＦＦＴ演算器は、イコライゼーションによるチャネル推定の周波数領域での実装、マルチキャリア方式の変調／復調、およびいわゆる「ｃａｎａｌｉｓａｔｉｏｎ（チャネル管理）」（すなわちチャネルの選択）の機能のフィルタバンクでの実行に使用される。したがってこの演算器は、処理チェーンのさまざまなレベルでさまざまな規格の枠組で使用できる。この演算器によって、ＦＦＴ計算を行う限定数のハードウェア演算器を備える再構成可能な端末を得ることを検討することができる。
【０００９】
本発明は、さらに正確には、少なくとも１つのバタフライ演算器を備え、Ｒａｄｉｘ２タイプの再分割を行ういわゆるＣｏｏｌｅｙ−Ｔｕｋｅｙ型アルゴリズムの手法によってＦＦＴ演算器の機能を果たすプロセッサに関する。このようなプロセッサが、例えば欧州特許第１５８３５３３号に記載されている（特許文献１）。一般に、このようなプロセッサをバタフライ演算器に実装する際には、それぞれのバタフライ演算器が、複素乗算を行う第１のステージと、この第１のステージの出力データを入力で受信して複素加算／減算を行う第２のステージとを備え、この２つのそれぞれのステージは加算／減算およびこの２つのモジュール間でデータ転送を行う複数の接続を備える。複素乗算を行う第１のステージはさらに、乗算を行うハードウェアモジュールを有する。
【００１０】
これらのハードウェアモジュールは、前述したＦＦＴ演算器の実装に独自のものである。とりわけ、ＦＦＴ演算器は、移動体通信における送信／受信端末の変調／復調以外のもう１つの重要機能であるチャネルの符号化／復号化には使用されないため、その他のハードウェアモジュールを追加してチャネルの符号化を実施する必要がある。
【００１１】
そのため、ほとんどの規格では、転送データの信頼性を確保するためにチャネルの符号化プロセスを必要とする。実際、チャネルの符号化は、転送するメッセージを、例えばこのメッセージを畳み込み符号化器で符号化して強化したメッセージに代替することで、転送チャネルがもたらす妨害に対抗するのに役立つ。よってビタビアルゴリズムは、畳み込み符号で処理した信号の復号化に広く使用される技術である。
【００１２】
この技術をＳＤＲタイプの送信／受信端末に実装するには、特殊なハードウェアモジュールおよびプロセッサが必要になるためやや複雑性が増す。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】欧州特許第１５８３５３３号
【非特許文献】
【００１４】
【非特許文献１】Ｌ．Ａｌａｕｓら著、「Ｐｒｏｍｉｓｉｎｇ  ｔｅｃｈｎｉｑｕｅ  ｏｆ  ｐａｒａｍｅｔｒｉｚａｔｉｏｎ  ｆｏｒ  ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  ｒａｄｉｏ、ｔｈｅ  Ｃｏｍｍｏｎ  Ｏｐｅｒａｔｏｒｓ  Ｔｅｃｈｎｉｑｕｅ：ｆｕｎｄａｍｅｎｔａｌｓ  ａｎｄ  ｅｘａｍｐｌｅｓ（再構成可能な無線の有望なパラメータ化、共用演算器の技術：基礎および例）」、Ｊｏｕｒｎａｌ ｏｆ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍｓ出版、ＤＯＩ１０．１００７／ｓ１１２６５−００９−０３５３−０４、２００９年３月１４日発行
【発明の概要】
【発明が解決しようとする課題】
【００１５】
したがって、前述の問題および制約を少なくとも部分的に解決でき、かつ／または端末の再構成可能性を向上できるデータ処理プロセッサを備えることが望まれる。
【課題を解決するための手段】
【００１６】
したがって本発明は、高速フーリエ変換の計算を実行する少なくとも１つのバタフライ演算器を備えるデジタルデータ処理プロセッサであって、このバタフライ演算器は、複素乗算を行う第１のステージと、この第１のステージの出力データを入力で受信して複素加算／減算を行う第２のステージとを備え、この２つのそれぞれのステージは、複数の加算／減算ハードウェアモジュールおよびこの２つのモジュール間でデータ転送を行う複数の接続を備えるプロセッサにおいて、バタフライ演算器の各ステージの加算／減算モジュールの少なくとも一部、およびこれらのモジュール同士の接続の少なくとも一部は、バタフライ演算器が前記高速フーリエ変換の演算を実行する第１の構成と、バタフライ演算器がブランチメトリック値とパスメトリック値とビタビアルゴリズム実装の生き残りパスの計算を実行する第２の構成との間でプログラム可能な少なくとも１つのパラメータを用いて構成可能であるプロセッサを目的とする。
【００１７】
本発明が利用した元の構想は、ＦＦＴ計算を行うバタフライ演算器による実装が、ブランチメトリック値とパスメトリック値とビタビアルゴリズムの生き残りパスの計算で考えられる実装と似ていることを確認したことに由来している。このようにビタビアルゴリズムをバタフライ構造で実装することで、バタフライ演算器を有するＦＦＴ計算プロセッサが行う複素乗算ならびに複素加算および複素減算のステージで使用する複数の加算／減算ハードウェアモジュールの共用化が可能であることが明らかになる。そのため、これらの加算／減算モジュールおよびこのモジュール間の接続をパラメータ化すると、パラメータ化に応じてｒａｄｉｘ２のバタフライ演算器を有するＦＦＴ計算、およびブランチメトリック値とパスメトリック値とビタビアルゴリズム実装の生き残りパスの計算を実行することができる唯一のデジタルデータ処理プロセッサの設計を検討できるようになる。チャネルを変調／復調および符号化／復号化する機能は、共用のハードウェア演算器に基づく同じ端末で果たすことができ、この端末内に搭載するハードウェア素子の数量もサイズも抑えられる。
【００１８】
さらに、ＦＦＴ計算は複素数データに対して演算されるため、ＦＦＴ計算と、ブランチメトリック値とパスメトリック値とビタビアルゴリズム実装の生き残りパスの計算との間で構成可能なプロセッサは、入力データを硬データ（２進）か（複数ビットに符号化した）軟データに処理してビタビ復号を実行することができる。
【００１９】
選択的に、複素乗算を行う第１のステージは、入力データの実数の加算／減算を行う第１のレベルと、第１のレベルが供給するデータを基に実行される実数乗算を行う第２のレベルと、第２のレベルが供給するデータを基に実行される実数加算および実数減算を行う第３のレベルと、複素乗算を行う第１のステージの第１のレベルにある加算／減算モジュールの少なくとも一部と、複素乗算を行う第１のステージの第１のレベルが、第２のレベルで実行する実数乗算数を制限するために組織された事前の加算および／または減算の演算を実行する第１の構成と、ビタビアルゴリズムの実装のブランチメトリック値の計算を実行する第２の構成との間で少なくとも１つのプログラム可能なパラメータを用いて構成可能なこれらのモジュールへの接続またはこれらのモジュールからの接続の少なくとも一部とを有する。
【００２０】
この構成は、一方でＦＦＴ／ＩＦＦＴ、もう一方でビタビの２つの計算に対して共用化することができるハードウェアモジュール数を最適化する。
【００２１】
同じく選択的に、複素乗算を行う第１のステージの第１のレベルは、４つの加算および／または減算ハードウェアモジュールを有し、複素乗算を行う第１のステージの第２のレベルは、３つの実数乗算ハードウェアモジュールを有する。
【００２２】
同じく選択的に、構成可能な加算／減算モジュールは、加算器の構成と減算器の構成との間で単一の２進パラメータを用いることで構成可能になる。
【００２３】
同じく選択的に、構成可能な接続は、２つの入力および１つの出力を備えて前記単一の２進パラメータを用いて２つの入力の一方を選択するマルチプレクサを有する。
【００２４】
同じく選択的に、本発明によるデジタルデータ処理プロセッサは、
−  第１の演算器であって、この第１の演算器が高速フーリエ変換の計算に含まれる係数の実部の計算を実行する第１の構成と、この第１の演算器がパスメトリック値とビタビアルゴリズム実装の生き残りパスの第１の計算を実行する第２の構成との間で少なくとも１つのプログラム可能なパラメータを用いて構成可能な加算／減算を組み合わせた３つのモジュールを有する第１の演算器と、
−  第１の演算器とは異なる第２の演算器であって、この第２の演算器が高速フーリエ変換の計算に含まれる係数の虚部の計算を実行する第１の構成と、パスメトリック値とビタビアルゴリズム実装の生き残りパスの第２の計算を実行する第２の構成との間で少なくとも１つのプログラム可能なパラメータを用いて構成可能な加算／減算を組み合わせた３つのモジュールを有する第２の演算器と
を有する。
【００２５】
同じく選択的に、本発明によるデジタルデータ処理プロセッサは、それぞれのバタフライ演算器が前記高速フーリエ変換の計算を実行する前記第１の構成と、それぞれのバタフライ演算器がブランチメトリック値とパスメトリック値とビタビアルゴリズム実装の生き残りパスの計算を実行する前記第２の構成との間で構成可能な複数のバタフライ演算器であって、Ｒａｄｉｘ−２タイプのトレリス構造のＣｏｏｌｅｙ−Ｔｕｋｅｙ型アルゴリズム法による高速フーリエ変換の計算を行い、４つの基準シンボルを持つトレリス構造のビタビアルゴリズムを実装するように両演算器の間で構造化されるバタフライ演算器を有する。
【００２６】
本発明はまた、送信／受信信号をマルチキャリア変調／復調し、畳み込み符号で処理した信号を復号化する移動通信端末であって、前述したようなデジタルデータ処理プロセッサを少なくとも１つ有する移動通信端末も目的とする。
【００２７】
選択的に、本発明による移動通信端末は、ＯＦＤＭタイプの変調および復調を行う。
【００２８】
同じく選択的に、本発明による移動通信端末は、マルチ規格タイプのものであり、実装したそれぞれの規格と互換性のあるＯＦＤＭ変調および復調を行う少なくとも１つの変調器／復調器と、実装したそれぞれの規格と互換性のある畳み込み符号で符号化した信号を復号化する少なくとも１つの復号化器とを有する。
【００２９】
本発明は、添付の図を参照しながら例のみを目的として挙げた以下の説明文を読めばよりよく理解できるであろう。
【図面の簡単な説明】
【００３０】
【図１】Ｒａｄｉｘ２タイプの再分割を行うＣｏｏｌｅｙ−Ｔｕｋｅｙ型アルゴリズム法によってＦＦＴ／ＩＦＦＴ計算を実装するトレリス構造のデータ処理ネットワークの全体構造を示す概略図である
【図２】図１のデータ処理ネットワークで使用するバタフライ演算器の構造の概略図である。
【図３】図２のバタフライ演算器の加算／減算および乗算モジュールにおける可能な実装を示す概略図である。
【図４】ビタビアルゴリズムを実装するデータ処理チェーンの全体構造の概略図である。
【図５】図４のデータ処理チェーンの一部で使用するバタフライ演算器の構造を示す概略図である。
【図６】図５のバタフライ演算器の加算／減算モジュールにおける可能な実装を示す概略図である。
【図７Ａ】図３および６に示した実装の加算／減算モジュールの一部を構成可能なように共用化した様子を示す図である。
【図７Ｂ】図３および６に示した実装の加算／減算モジュールの一部を構成可能なように共用化した様子を示す図である。
【図８】本発明の一実施形態によるバタフライ演算器を有するプロセッサの全体構造の概略図である。
【図９】本発明の一実施形態による移動通信端末の全体構造の概略図である。
【発明を実施するための形態】
【００３１】
高速フーリエ変換ＦＦＴは、離散フーリエ変換を計算するアルゴリズムである。このアルゴリズムは、信号をデジタル処理し、時間または空間領域の離散データを周波数領域で変換するのに使用する。
【００３２】
つまり、例えば信号ｘのＮ値の離散時間値ｘ［０］、．．．、ｘ［Ｎ−１］である。フーリエ変換ＸのＮ個の周波数値は次式で規定される。
【００３３】
【数１】
0006008194.tif 000002
【００３４】
（ｋ＝０，．．．，Ｎ−１、式中
0006008194.tif 000003
）
【００３５】
逆離散フーリエ変換は、符号および因子１／Ｎを除いて離散フーリエ変換と同じであるため、逆高速フーリエ変換ＩＦＦＴは、この逆離散フーリエ変換を計算するためのＦＦＴと同じアルゴリズムに基づくものである。したがって、高速フーリエ変換ＦＦＴの計算を実行するように構成されたあらゆるデジタルデータ処理プロセッサも同じく逆高速フーリエ変換ＩＦＦＴの計算ができる。
【００３６】
ＦＦＴ計算のうち特に単純でよく用いられる実装が、Ｒａｄｉｘ２タイプの再分割によるＣｏｏｌｅｙ−Ｔｕｋｅｙ型アルゴリズム法である。この実装では、変換したサンプル数Ｎが２の累乗であると仮定し、ｎ個のサンプル処理を規模の小さいｎ／２のサイズである同じ処理２回に再帰的に分割する。実際、第１の規模は以下のようになる。
【００３７】
【数２】
0006008194.tif 000004
【００３８】
帰納的に、所定規模のＦＦＴ計算を規模の小さい２つのＦＦＴ計算で実行し、所定規模の信号のうち１つは偶数のサンプルに対して係り、もう１つは奇数のサンプルに対して係る。
【００３９】
よく知られているさらに単純な方法を用いると、連続ステップを含む複数の規模（またはレベル）のある図１に示したようなトレリス構造の処理が得られ、この図ではＮ＝８で３つのステップＳｔ１、Ｓｔ２およびＳｔ３が含まれている。
【００４０】
各ステップではバタフライ演算をＮ／２回行い、合計すると図２に示した計算のようにＮ／２×ｌｏｇ２（Ｎ）回のバタフライ演算を行う。このバタフライ演算では、２つのデータｙｋ［０］およびｙｋ［１］をクロス計算する必要があり、一方のデータｙｋ［１］の複素数に因子Ｗを乗算して中間値を供給したのち、ｙｋ［０］とこの中間値との間で複素加算および複素減算を行って２つのデータｙｋ＋１［０］およびｙｋ＋１［１］を供給する。図１に示した例では、因子Ｗの値は、規模／ステップＳｔ１ではｗ０、規模／ステップＳｔ２ではｗ０またはｗ２、規模／ステップＳｔ３ではｗ０、ｗ１、ｗ２またはｗ３になる。
【００４１】
ｙｋ＋１［０］およびｙｋ＋１［１］をｙｋ［０］およびｙｋ［１］に結びつける２つの関係は次式になる。
ｙｋ＋１［０］＝ｙｋ［０］＋Ｗ．ｙｋ［１］
ｙｋ＋１［１］＝ｙｋ［０］−Ｗ．ｙｋ［１］
【００４２】
実際には、バタフライ演算は、複素乗算を行う第１のステージと、第１のステージの出力データを入力で受信して複素加算および複素減算を行う第２のステージとで構成した演算器で実行する。この複素乗算を実行するため、第１のステージは、実数乗算を行うハードウェアモジュールと、実数加算／減算を行うハードウェアモジュールと、これらのモジュール間でデータを転送する接続とを有する。この複素加算および複素減算を実行するため、第２のステージは、実数加算／減算を行うハードウェアモジュールと、これらのモジュールにデータを転送する接続とを有する。
【００４３】
さらに正確には、
ｙｋ［１］＝ａ＋ｉｂ、
Ｗ＝ｃ＋ｉｄ、
ｙｋ［０］＝ｅ＋ｉｆ、
であることがわかり、式中ａ、ｂ、ｃ、ｄ、ｅおよびｆは実数値であり、次式の実数乗算、実数加算および実数減算を行うハードウェアモジュールが必要であることがわかる。
ｙｋ＋１［０］＝（ａｃ−ｂｄ＋ｅ）＋ｉ（ｂｃ＋ａｄ＋ｆ）
ｙｋ＋１［１］＝（−ａｃ＋ｂｄ＋ｅ）＋ｉ（−ｂｃ−ａｄ＋ｆ）
【００４４】
この単純な式では、バタフライ演算器が実行する計算には、実数乗算を行うハードウェアモジュール４つ、実数加算を行うハードウェアモジュール３つ、実数減算を行うハードウェアモジュール３つを必要とし、これは図３の左部分に示したとおりである。
【００４５】
さらに正確には、図３の左部分に示したバタフライ演算器１０が複素乗算を行う符号１２を付した第１のステージは、それぞれが積ａｄ、ｂｃ、ｂｄおよびａｃを実行する４つの乗算モジュール１４、１６、１８および２０と、モジュール１４および１６からの出力データを受信して加算ａｄ＋ｂｃを実行する加算モジュール２２と、モジュール１８および２０からの出力データを受信して減算ａｃ−ｂｄを実行する減算モジュール２４とを有する。
【００４６】
バタフライ演算器が複素加算および複素減算を行う符号２６を付した第２のステージは、
−  モジュール２２からの出力データおよび変数ｆを受信して演算ａｄ＋ｂｃ＋ｆを実行し、ｙｋ＋１［０］からＦＦｔ−Ｉｍ０と表記した虚部を供給する加算モジュール２８と、
−  モジュール２４からの出力データおよび変数ｅを受信して演算ａｃ−ｂｄ＋ｅを実行し、ｙｋ＋１［０］からＦＦｔ−Ｒｅ０と表記した実部を供給する加算モジュール３０と、
−  モジュール２２からの出力データおよび変数ｆを受信して演算−ａｄ−ｂｃ＋ｆを実行し、ｙｋ＋１［１］からＦＦｔ−Ｉｍ１と表記した虚部を供給する減算モジュール３２と、
−  モジュール２４からの出力データおよび変数ｅを受信して演算ｂｄ−ａｃ＋ｅを実行し、ｙｋ＋１［１］からＦＦｔ−Ｒｅ１と表記した実部を供給する減算モジュール３４と
を有する。
【００４７】
さらに長い式では、次式からさらに巧妙であることがわかるように、バタフライ演算器が実行する計算は、実数乗算を行うハードウェアモジュールを３つしか必要としないことがあるが、この場合は図３の右部分に示したように、実数加算を行うハードウェアモジュール５つおよび実数減算を行うハードウェアモジュール４つを使用する。このさらに長い式は、ｙｋ＋１［０］およびｙｋ＋１［１］を同じように次式で表される。
ｙｋ＋１［０］＝［ｃ（ａ＋ｂ）−ｂ（ｄ＋ｃ）＋ｅ］＋ｉ［ｃ（ａ＋ｂ）＋ａ（ｄ−ｃ）＋ｆ］
ｙｋ＋１［１］＝［−ｃ（ａ＋ｂ）＋ｂ（ｄ＋ｃ）＋ｅ］＋ｉ［−ｃ（ａ＋ｂ）−ａ（ｄ−ｃ）＋ｆ］
【００４８】
さらに正確には、図３の右部分に示したバタフライ演算器１０’が複素乗算を行う第１のステージ１２’は、まず連続する第１のレベルに、
−  演算ｄ−ｃを実行する減算モジュール３６と、
−  演算ａ＋ｂを実行する加算モジュール３８と、
−  演算ｄ＋ｃを実行する加算モジュール４０と
を有する。
【００４９】
次に、連続する第２のレベルには、
−  モジュール３６からの出力データおよび変数ａを受信して演算ａ（ｄ−ｃ）を実行する乗算モジュール４２と
−  モジュール３８からの出力データおよび変数ｃを受信して演算ｃ（ａ＋ｂ）を実行する乗算モジュール４４と、
−  モジュール４０からの出力データおよび変数ｂを受信して演算ｂ（ｄ＋ｃ）を実行する乗算モジュール４６と
を有する。
【００５０】
最後に、連続する第３のレベルには、
−  モジュール４２および４４からの出力データを受信して演算ａ（ｄ−ｃ）＋ｃ（ａ＋ｂ）＝ａｄ＋ｂｃを実行するモジュール２２などの加算モジュールと、
−  モジュール４４および４６からの出力データを受信して演算ｃ（ａ＋ｂ）−ｂ（ｄ＋ｃ）＝ａｃ−ｂｄを実行するモジュール２４などの減算モジュールと
を有する。
【００５１】
バタフライ演算器が複素加算および複素減算を行う第２のステージ２６は変化せず、モジュール２８、３０、３２および３４のそれぞれの出力で値ＦＦＴ−Ｉｍ０、ＦＦＴ−Ｒｅ０、ＦＦＴ−Ｉｍ１およびＦＦＴ−Ｒｅ１を供給する。
【００５２】
したがって、図３に示したバタフライ演算器１０および１０’の２つの構造は、ＦＦＴ計算を実行するために実施する計算という意味では同じであることが明らかになる。
【００５３】
ビタビアルゴリズムを実装するためのデータ処理チェーンの全体構造は、図４に示すとおりである。
【００５４】
このアルゴリズムは、畳み込み符号化器、すなわち各入力ビットがレジスタ内でシフトを生成し、出力で結果を生成するシフトレジスタを有する符号化器で符号化した信号の場合に［Ｘ０，．．．，ＸＮ−１］を測定する系列を生成する最も確からしい状態の系列を帰納法により発見することを目的とする。
【００５５】
このアルゴリズムの原理は、受信したそれぞれの値をシフトレジスタから出力され得るあらゆる値と比較し、最も確からしいこのレジスタのどのシフトから受信値が生じたのかを判定する。このシフトを認識することによって、このシフトを発生させた値がわかり、その結果、受信メッセージの生成値がわかる。
【００５６】
受信メッセージの各値に対して、縦座標がシフトレジスタの取り得る状態の集合であり、横座標が可能な遷移の集合であるトレリス構造が得られ、このトレリスのパターンは、符号化器に新たな入力があるごとに時間的に変化することなく反復される。符号化器の出力では、特定の２進系列のみが可能である。この系列はトレリス線図に存在する異なるパスと対応する。
【００５７】
ビタビアルゴリズムの適用は、トレリスの中から受信系列に最も近い２進系列を検索することで成り立つ。実際には、このアルゴリズムの実行には、それぞれの時点でトレリスのそれぞれの状態に対して、以下の３つの演算を行う。
【００５８】
−  ブロック４８が実行するブランチメトリック値の計算であって、（効率１／Ｎに対して）Ｎ個のシンボルを受信した場合に、受信したシンボルの２Ｎ個のシンボルに対する尤度を表す値を計算することからなる計算。この２Ｎ個の値はブランチメトリックと呼ばれ、Ｎ＝２の場合はＢｍ００、Ｂｍ０１、Ｂｍ１０およびＢｍ１１と表記する。
【００５９】
−  ブロック５０が実行するパスメトリック値および生き残りパスの計算であって、シフトレジスタの最も確からしい状態を判定することからなる計算。トレリスの各ノードに対して、送信系列の一部となるこのノードに累積した確からしさを表すパスメトリックが、前の周期で計算されたパスメトリックおよび現在のブランチメトリック値を考慮して更新される。この更新は、２つのパスメトリックの計算および最も弱いパス（生き残りパス）の選択を含む。
【００６０】
−  ブロック５２が実行する判定によるビットの記憶であって、生き残りパスをトレースバックする技術によってフレームの最後で復号した信号を復元するための記憶。
【００６１】
具体的には、ブロック４８は受信値とシフトレジスタが出力し得る値との差を計算する。
【００６２】
ブロック５０は、一般にＡＣＳ（加算比較選択）（「Ａｄｄｉｔｉｏｎ，  Ｃｏｍｐａｒｉｓｏｎ  ａｎｄ  Ｓｅｌｅｃｔｉｏｎ」）ブロックと呼ばれるもので、トレリスの各ノードで２つのパスメトリックとブランチメトリックとの加算、得られた２つのパスメトリックの比較、および最も弱いパスの選択を実行する。
【００６３】
そのため、ブロック４８が計算した４つの可能なブランチメトリックＢｍ００、Ｂｍ０１、Ｂｍ１０およびＢｍ１１に基づく計算の場合、図５に示したようなバタフライ演算器で次の２つのパスメトリックの計算をすることがわかる。
Ｐｍｋ［ｔ＋ｌ］＝Ｖｉｔ０＝Ｍｉｎ（Ｐｍｋ［ｔ］＋Ｂｍ００、Ｐｍｋ＋１［ｔ］＋Ｂｍ１０）
Ｐｍｋ＋Ｎ／２［ｔ＋１］＝Ｖｉｔ１＝Ｍｉｎ（Ｐｍｋ［ｔ］＋Ｂｍ０１、Ｐｍｋ＋１［ｔ］＋Ｂｍ１１）
【００６４】
２つの値の比較による最小値の検出は、マルチプレクサに接続する減算器を用いて実行できることを考えると、ブロック４８および５０の計算、つまりブランチメトリック値とパスメトリック値とビタビアルゴリズム実装の生き残りパスの計算を実行するために、このバタフライ演算器は、
−  パスメトリック値および生き残りパスの２つの計算それぞれに対し、加算ハードウェアモジュール２つおよび減算ハードウェアモジュール１つ、
−  ４つのブランチメトリック値Ｂｍ００、Ｂｍ０１、Ｂｍ１０およびＢｍ１１を計算する追加の減算ハードウェアモジュール４つ
を必要とすることがわかる。
【００６５】
総合すると、図６に示すように、１０個の加算／減算ハードウェアモジュールがこのバタフライ演算器に使用される。前の周期で計算した２つのパスメトリックをＰ０およびＰ１、受信値をＲｅｆ、４つの可能な出力値をａ、ｂ、ｃ、ｄと表示すると、図６に示すバタフライ演算器５４は連続する第１のレベルで、
−  演算Ｒｅｆ−ｂ＝Ｂｍ０１、Ｒｅｆ−ｄ＝Ｂｍ１１、Ｒｅｆ−ｃ＝Ｂｍ１０およびＲｅｆ−ａ＝Ｂｍ００を実行する４つの減算モジュール５６、５８、６０および６２を有し、
連続する第２のレベルで、
−  モジュール６２からの出力データおよび変数Ｐ０を受信して演算Ｐ０＋Ｂｍ００を実行する加算モジュール６４と、
−  モジュール６０からの出力データおよび変数Ｐ１を受信して演算Ｐ１＋Ｂｍ１０を実行する加算モジュール６６と、
−  モジュール５６からの出力データおよび変数Ｐ０を受信して演算Ｐ０＋Ｂｍ０１を実行する加算モジュール６８と、
−  モジュール５８からの出力データおよび変数Ｐ１を受信して演算Ｐ１＋Ｂｍ１１を実行する加算モジュール７０とを有し、
連続する第３のレベルで、
−  モジュール６４および６６からの出力データを受信してＰ０＋Ｂｍ００とＰ１＋Ｂｍ１０とを比較し、そこからＶｉｔ０の値を導く減算モジュール７２と、
−  モジュール６８および７０からの出力データを受信してＰ０＋Ｂｍ０１とＰ１＋Ｂｍ１１とを比較し、そこからＶｉｔ１の値を導く減算モジュール７４とを有する。
【００６６】
したがって、ＦＦＴを行うバタフライ演算器１０および１０’のバタフライ構造は、ビタビ演算器５４を含む一方で、特定の加算／減算モジュールおよび例えばマルチプレクサを介した接続をパラメータ化することによって加算／減算ハードウェアモジュールの一部とこれらのモジュール間の接続との共用を検討することができるハードウェア構成も含むことがわかる。
【００６７】
特に、複素加算および複素減算を行う第２のステージに関連する複素乗算を行う第１のステージ（モジュール２２および２４）の第３のレベルからなる装置は、ＦＦＴを行うバタフライ演算器１０および１０’を共用し、３つの加算／減算ハードウェアモジュールからなる２つのグループ（第１のグループにはモジュール２２、２８および３２、第２のグループにはモジュール２４、３０および３４）を備え、いずれもビタビ演算器５４の第２および第３のレベル（第１のグループにはモジュール６４、６６および７２、第２のグループにはモジュール６８、７０および７４）からなる装置のようになる。
【００６８】
さらに一層巧妙な方法では、ＦＦＴを行うバタフライ演算器１０’が複素乗算を行う第１のステージの第１のレベル（モジュール３６、３８および４０）は、ビタビ演算器５４の第１のレベル（モジュール５６、５８、６０および６２）にパラメータ化によって使用できる３つの加算／減算ハードウェアモジュールを有する。
【００６９】
最初に、図７Ａは、一方ではモジュール２２、２８および３２で可能な共用化を示し、もう一方ではモジュール６４、６６および７２で可能な共用化を示す。このハードウェアの共用化は、対象とする３つのモジュールからなる２つの装置のそれぞれの入力および出力の共通の数学的表現を介していることがわかる。
【００７０】
したがって、ビタビ演算器５４のモジュール６４、６６および７２を考える場合、加算モジュール６６の２つの入力をＥ１（Ｒｅｆ−ｃ）およびＥ２（Ｐ１）、加算モジュール６４の２つの入力をＥ３（Ｒｅｆ−ａ）およびＥ４（Ｐ０）、加算モジュール６４の出力をＳ１（Ｐ０＋Ｂｍ００）、減算モジュール７２の出力をＳ２（Ｐ０＋Ｂｍ００−（Ｐ１＋Ｂｍ１０））、加算モジュール６６の出力をＳ３（Ｐ１＋Ｂｍ１０）と表記すると、以下の一連の式が得られる。
【００７１】
【数３】
0006008194.tif 000005
【００７２】
次に、ＦＦＴを行うバタフライ演算器１０または１０’のモジュール２２、２８および３２を考える場合、加算モジュール２２の２つの入力をＥ１（演算器１０に対してｂｃ、または演算器１０’に対してｃ（ａ＋ｂ））およびＥ２（演算器１０に対してａｄ、または演算器１０’に対してａ（ｄ−ｃ））、加算モジュール２８（または減算モジュール３２）の２つの入力の一方をＥ４（ｆ）、もう一方はモジュール２２の出力、加算モジュール２８の出力をＳ１（ＦＦＴ−Ｉｍ０）、減算モジュール３２の出力をＳ２（ＦＦＴ−Ｉｍ１）、加算モジュール２２の出力をＳ３とすると、以下の一連の式が得られる。
【００７３】
【数４】
0006008194.tif 000006
【００７４】
この２つの一連の式から、ＦＦＴ計算とビタビ演算の２ｔの演算器にパラメータβを除いて共通する以下の第３の式を導くことができる。
【００７５】
【数５】
0006008194.tif 000007
【００７６】
この第３の一連の式から、図７Ａに示す共用演算器７５を導く。この演算器は、Ｅ１およびＥ２を受信してＳ３（第３の関係）を供給する加算ハードウェアモジュール７６を有する。この演算器はさらに、加算ハードウェアモジュール７８を有し、このモジュールは、Ｅ４とパラメータβの値に応じて制御されるマルチプレクサ８０の出力とを受信し、Ｓ３（β＝１）またはＥ３（β＝０）を供給する。この加算ハードウェアモジュール７８は、Ｓ１（第１の関係）を供給する。また、この演算器は減算ハードウェアモジュール８２を有し、このモジュールは、Ｓ３とパラメータβの値に応じて制御されるマルチプレクサ８４の出力とを受信し、Ｅ４（β＝１）またはＳ１（β＝０）を供給する。この減算ハードウェアモジュール８２は、Ｓ２（第２の関係）を供給する。
【００７７】
共用演算器７５の加算モジュール７６は、β＝１のときはモジュール２２の機能を果たし、β＝０のときはモジュール６６の機能を果たし、共用演算器７５の加算モジュール７８は、β＝１のときはモジュール２８の機能を果たし、β＝０のときはモジュール６４の機能を果たし、共用演算器７５の減算モジュール８２は、β＝１のときはモジュール３２の機能を果たし、β＝０のときはモジュール７２の機能を果たすことがわかる。
【００７８】
同じように、図７Ｂは、一方ではモジュール２４、３０および３４で可能な共用化を示し、もう一方ではモジュール６８、７０および７４で可能な共用化を示す。このハードウェアの共用化は、対象とする３つのモジュールからなる２つの装置のそれぞれの入力および出力の共通の数学的表現を介していることがわかる。
【００７９】
したがって、ビタビ演算器５４のモジュール６８、７０および７４を考える場合、加算モジュール７０の２つの入力をＥ１（Ｒｅｆ−ｄ）およびＥ２（Ｐ１）、加算モジュール６８の２つの入力をＥ３（Ｒｅｆ−ｂ）およびＥ４（Ｐ０）、加算モジュール６８の出力をＳ１（Ｐ０＋Ｂｍ０１）、減算モジュール７４の出力をＳ２（Ｐ０＋Ｂｍ００−（Ｐ１＋Ｂｍ１１））、加算モジュール７０の出力をＳ３（Ｐ１＋Ｂｍ１１）と表記すると、以下の一連の式が得られる。  
【００８０】
【数６】
0006008194.tif 000008
【００８１】
次に、ＦＦＴを行うバタフライ演算器１０または１０’のモジュール２４、３０および３４を考える場合、減算モジュール２４の２つの入力をＥ１（演算器１０に対してｂｄ、または演算器１０’に対してｂ（ｄ＋ｃ））およびＥ２（演算器１０に対してａｃ、または演算器１０’に対してｃ（ａ＋ｂ））、加算モジュール３０（または減算モジュール３４）の２つの入力の一方をＥ４（ｅ）、もう一方はモジュール２４の出力、加算モジュール３０の出力をＳ１（ＦＦＴ−Ｒｅ０）、減算モジュール３４の出力をＳ２（ＦＦＴ−Ｒｅ１）、減算モジュール２４の出力をＳ３とすると、以下の一連の式が得られる。  
【００８２】
【数７】
0006008194.tif 000009
【００８３】
この２つの一連の式から、ＦＦＴ計算とビタビ演算の２ｔの演算器にパラメータβを除いて共通する以下の第３の式を導くことができる。  
【００８４】
【数８】
0006008194.tif 000010
【００８５】
この第３の一連の式から、図７Ｂに示す共用演算器８５を導く。この演算器は、Ｅ１およびＥ２を受信してＳ３（第３の関係）を供給するパラメータ化可能な加算／減算ハードウェアモジュール８６を有する。さらに正確には、このパラメータ化可能なモジュール８６は、β＝０のときは加算器（Ｅ１＋Ｅ２）として機能し、β＝１のときは減算器（Ｅ２−Ｅ１）として機能するように設計する。この演算器はさらに、加算ハードウェアモジュール８８を有し、このモジュールは、Ｅ４とパラメータβの値に応じて制御されるマルチプレクサ９０の出力とを受信し、Ｓ３（β＝１）またはＥ３（β＝０）を供給する。この加算ハードウェアモジュール８８は、Ｓ１（第１の関係）を供給する。また、この演算器は減算ハードウェアモジュール９２を有し、このモジュールは、Ｓ３とパラメータβの値に応じて制御されるマルチプレクサ９４の出力とを受信し、Ｅ４（β＝１）またはＳ１（β＝０）を供給する。この減算ハードウェアモジュール９２は、Ｓ２（第２の関係）を供給する。
【００８６】
共用演算器８５のパラメータ化可能な加算／減算モジュール８６は、β＝１のときはモジュール２４の機能を果たし、β＝０のときはモジュール７０の機能を果たし、共用演算器８５の加算モジュール８８は、β＝１のときはモジュール３０の機能を果たし、β＝０のときはモジュール６８の機能を果たし、共用演算器８５の減算モジュール９２は、β＝１のときはモジュール３４の機能を果たし、β＝０のときはモジュール７４の機能を果たすことがわかる。
【００８７】
図７Ａおよび７Ｂに示す共用演算器から、（パラメータβのみを用いて）パラメータ化可能な少なくとも１つのバタフライ共用演算器であって、第１の構成（β＝１）で高速フーリエ変換の計算を実行でき、第２の構成（β＝０）でブランチメトリック値とパスメトリック値とビタビアルゴリズム実装の生き残りパスの計算を実行できるバタフライ共用演算器を有するデータ処理プロセッサを設計することができる。
【００８８】
さらに、ＦＦＴを行うバタフライ演算器１０’の巧妙な構造に基づいて、図７Ａおよび７Ｂに示す加算／減算モジュールだけでなく、ＦＦＴを行うバタフライ演算器１０’が複素乗算を行う第１のステージ（モジュール３６、３８および４０）の第１のレベルにある加算／減算モジュール、およびビタビ演算器５４の第１のレベルにある加算／減算モジュール（モジュール５６、５８、６０および６２）も共用化することができる。
【００８９】
したがって、例えば図８に概略的に示したデータ処理プロセッサ９６が得られる。
【００９０】
このデータ処理プロセッサ９６は、乗算または加算／減算を行うハードウェアモジュールがある連続する３つのレベルを有する。
【００９１】
第１のレベル９８では、このデータ処理プロセッサは独立した４つの加算／減算ハードウェアモジュールを有する。この第１のレベルは、ビタビ演算器５４の（ブロック４８の機能を実行する）第１のレベルおよびＦＦＴを行うバタフライ演算器１０が複素乗算を行う第１のステージの第１のレベルに共通のものである。この第１のレベル９８の加算／減算ハードウェアモジュールのうちの３つは、ＦＦＴ計算およびビタビ演算に共通のものであり、１つはビタビ演算のみを対象とするものである。
【００９２】
第２のレベル１００では、このデータ処理プロセッサは、ＦＦＴ計算のみを対象とする３つの乗算ハードウェアモジュールを有する。
【００９３】
第３のレベル１０２では、このデータ処理プロセッサは、図７Ａおよび７Ｂに示した２つの演算器を有する。この第３のレベルは、ビタビ演算器５４の（ブロック５０の機能を実行する）第２および第３のレベル、および複素乗算を行う第１のステージの第３のレベルとＦＦＴを行うバタフライ演算器１０’が複素加算および複素減算を行う第２のステージとの組み合わせに共通のものである。
【００９４】
さらに正確には、第１のレベル９８は、値ａおよびパラメータβの値に応じて制御されるマルチプレクサ１０６の出力を受信し、ｂ（β＝１）またはＲｅｆ（β＝０）を供給するパラメータ化可能な加算／減算ハードウェアモジュール１０４を有する。さらに正確には、このパラメータ化可能なモジュール１０４は、β＝１のときは加算器として機能し、β＝０のときは減算器として機能するように設計する。したがって、このモジュールは、β＝１のときはａ＋ｂを供給し、β＝０のときはＲｅｆ−ａを供給する。
【００９５】
第１のレベル９８はさらに、ｂおよびＲｅｆを受信してＲｅｆ−ｂを供給する減算ハードウェアモジュール１０８を有する。
【００９６】
第１のレベル９８はさらに、値ｃおよびパラメータβの値に応じて制御されるマルチプレクサ１１２の出力を受信してｄ（β＝１）またはＲｅｆ（β＝０）を供給する減算ハードウェアモジュール１１０を有する。したがってこのモジュール１１０は、β＝１のときはｄ−ｃを供給し、β＝０のときはＲｅｆ−ｃを供給する。
【００９７】
最後に、第１のレベル９８は、値ｄおよびパラメータβの値に応じて制御されるマルチプレクサ１１６の出力を受信してｃ（β＝１）またはＲｅｆ（β＝０）を供給するパラメータ化可能な加算／減算ハードウェアモジュール１１４を有する。さらに正確にはこのパラメータ化可能なモジュール１１４は、β＝１のときは加算器として機能し、β＝０のときは減算器として機能するように設計する。したがって、このモジュールは、β＝１のときはｃ＋ｄを供給し、β＝０のときはＲｅｆ−ｄを供給する。
【００９８】
ＦＦＴ計算（β＝１）のみに必要とされる第２のレベル１００は、
−  値ａおよび減算モジュール１１０の出力を受信し、β＝１のときに値ａ（ｄ−ｃ）を供給する第１の乗算ハードウェアモジュール１１８と、
−  値ｂおよびパラメータ化可能な加算／減算モジュール１１４の出力を受信し、β＝１のときに値ｂ（ｄ＋ｃ）を供給する第２の乗算ハードウェアモジュール１２０と、
−  値ｃおよびパラメータ化可能な加算／減算モジュール１０４の出力を受信し、β＝１のときに値ｃ（ａ＋ｂ）を供給する第３の乗算ハードウェアモジュール１２２と
を有する。
【００９９】
第３のレベル１０２の加算モジュール７６は、パラメータβの値に応じて制御されるマルチプレクサ１２４の出力を受信して乗算モジュール１１８の出力ａ（ｄ−ｃ）（β＝１）またはＰ０（β＝０）を供給し、パラメータβの値に応じて制御されるマルチプレクサ１２６の出力を受信して乗算モジュール１２２の出力ｃ（ａ＋ｂ）（β＝１）またはパラメータ化可能な加算／減算モジュール１０４の出力Ｒｅｆ−ａ（β＝０）を供給する。
【０１００】
第３のレベル１０２のパラメータ化可能な加算／減算モジュール８６は、パラメータβの値に応じて制御されるマルチプレクサ１２８の出力を受信して乗算モジュール１２０の出力ｂ（ｄ＋ｃ）（β＝１）または減算モジュール１０８の出力Ｒｅｆ−ｂ（β＝０）を供給し、パラメータβの値に応じて制御されるマルチプレクサ１３０の出力を受信して乗算モジュール１２２の出力ｃ（ａ＋ｂ）（β＝１）またはＰ１（β＝０）を供給する。
【０１０１】
最後に、マルチプレクサ８０は、（β＝１のときに出力に供給する）モジュール７６の出力を受信するとともに、（β＝０のときにモジュール７８の出力に供給する）減算モジュール１１０の出力も受信し、一方マルチプレクサ９０は、（β＝１のときに出力に供給する）モジュール８６の出力を受信するとともに、（β＝０のときにモジュール８８の出力に供給する）パラメータ化可能な加算／減算モジュール１１４の出力も受信する。
【０１０２】
第３のレベル１０２の出力では、減算モジュール８２の出力に制御される第１のマルチプレクサ１３２が、モジュール７６および７８が供給する２つの値の小さい方をビタビ演算用に選択し（値Ｖｉｔ０を取得）、減算モジュール９２の出力に制御される第２のマルチプレクサ１３４が、モジュール８６および８８が供給する２つの値の小さい方をビタビ演算用に選択する（値Ｖｉｔ１を取得）。
【０１０３】
前述のデータ処理プロセッサは、β＝１のときは入力値ａ、ｂ、ｃ、ｄ、ｅ、ｆを用いてＦＦＴ計算を実行し、β＝０のときは入力値Ｒｅｆ、ａ、ｂ、ｃ、ｄ、Ｐ０、Ｐ１を用いてブランチメトリック値とパスメトリック値とビタビアルゴリズム実装の生き残りパスの計算を実行するために、単純な２進パラメータβを用いて構成できることが明らかになる。図８に示した図のグレ−の素子（８０、８４、８６、９０、９４、１０４、１０６、１１２、１１４、１１６、１２４、１２６、１２８、１３０）は、βを用いてパラメータ化可能な素子である。
【０１０４】
ＦＦＴアルゴリズムとビタビアルゴリズムとは、処理するデータにおいても実行する関数においても異なるものだが、減算および／または加算ハードウェアモジュールの共用化および共用構造の概念は、この２つのアルゴリズムを実行するバタフライ演算器の動作が元々似ていることが明らかであったために実現可能なものである。
【０１０５】
ＦＦＴ計算のみを実行するバタフライ演算器を備えるデータ処理プロセッサに対して、減算モジュール１０８とＦＦＴモードからビタビモードへ切り替えることができるあらゆるマルチプレクサとを追加する必要があるだけである。したがって、ＦＦＴ計算を行う演算器およびブランチメトリック値とパスメトリック値とビタビアルゴリズム実装の生き残りパスの計算を行う演算器を、前述の演算器と比較すると、加算および／または減算を行う演算器の必要性が約半分に減少する。
【０１０６】
ＦＦＴ計算およびビタビ演算は通常同時に実行されないため、その分利得が重要になる。
【０１０７】
しかしながら、２つの処理に必要な総合資源は異なるため（現在の規格を見ると、ＦＦＴのサイズは６４〜２０４８と幅があるためトレリスのステップごとに３２〜１０２４個のバタフライ演算器が必要になるが、畳み込み符号の生成多項式の次数は４〜８に及ぶため、８〜１２８個のバタフライ演算器が必要になる）、ＦＦＴのバタフライ演算器を前述の方法で半分のみ実装すると仮定すると、加算／減算ハードウェアモジュール数に対して利得１３％でビタビ演算を実行するのに十分なバタフライ演算器を備えていることになる。並列処理をさらに全体にビタビ演算のバタフライ演算器のレベルまで増加すると、利得約５０％を達成できる余地がある。
【０１０８】
この共用構造のもう１つの利点が、ＦＦＴモードで処理したデータは複素数になるはずであり、その実部および虚部は一般に整数であることから、ビタビモードの場合に利益を引き出すことができるという点である。そのためビタビモードでは、処理プロセッサは、硬入力データ（２進）とも軟入力データ（整数）とも動作することができる。
【０１０９】
最後に、マイクロエレクトロニクス技術の性能には変動があることを考慮すると、基礎が可能なかぎり規則的なプロセッサを提供することが有利である。実際には、このようなプロセッサを超過数設置し、それを性能またはこれらのプロセッサのそれぞれに起こり得る故障に応じて後験的に構成するように検討することができる。
【０１１０】
その結果、前述したようなデータ処理プロセッサ９６は、送信／受信信号をマルチキャリア変調／復調し、図９に示すように畳み込み符号で処理した信号を復号化する移動通信端末１３６に搭載することが有利である。
【０１１１】
ＦＦＴおよびビタビの２つの動作モードを有するこの処理プロセッサの用途は多数あり、単一規格の端末または多数の規格に対応する端末に適用される。実際、多くの規格は、例えばＯＦＤＭ変調（ＦＦＴ計算）を実行し、畳み込み符号の復号化（ビタビアルゴリズム）を必要とし、以下の規格がある。
【０１１２】
−  地上波デジタルラジオ放送ＤＡＢ、
−  地上波デジタルテレビジョン放送（ＤＶＢ−Ｔ、ＤＶＢ−Ｈ）、
−  地上波デジタルラジオ放送Ｔ−ＤＭＢ、
−  デジタルラジオ放送ＤＲＭ、
−  有線接続：ＡＤＳＬ、ＶＤＳＬ、電力線モデム（Ｈｏｍｅｐｌｕｇ）、ケーブルモデム（Ｄｏｃｓｉｓ規格）、
−８０２．１１ａ、８０２．１１ｇ（Ｗｉ−Ｆｉ）、８０２．１６（ＷｉＭＡＸ）およびＨｉｐｅｒＮの規格に基づく無線ネットワーク
−  次世代モバイルネットワーク（４Ｇ）。
【０１１３】
当然ながら、現在の規格または研究途中の規格のほぼすべてはＯＦＤＭ変調および／またはビタビ復号を利用するため、このリストは網羅的なものではない。
【０１１４】
さらに、最近の研究から、ＦＦＴは単純な変調よりもさらに多様な演算に適用できることがわかった。とりわけＦＦＴは、相関関係の計算、ＦＩＲタイプのフィルタ生成、チャネルの推定、または複数のユーザの検出に使用できる。同じように、ビタビアルゴリズムは、過去の研究ではターボ符号の復号化にも及んだ。
【０１１５】
したがって、本発明が提供するＦＦＴとビタビの共用アーキテクチャは、移動通信端末のほとんどの機能で使用でき、チャネルの復号化および変調／復調を行う単一のブロックに限定されるものではない。
【０１１６】
最後に、本発明は、本明細書で検討した実施形態に限定されるものではないことがわかるであろう。ここに開示した教示に照らし合わせて、上に記載した実施形態にさまざまな修正を加えてもよいことは当業者には明らかであろう。以下の特許請求の範囲では、使用した用語が請求項を本明細書で明らかにした実施形態に限定するものと解釈してはならず、本文の記載およびそこから予見される内容は、ここに開示した教示の実装に一般知識を応用することによって当業者が到達しうる範囲内であることから、請求項が範囲に含めると想定するあらゆる同等のものも含まれると解釈すべきである。
【図１】
0006008194.tif 000011
【図２】
0006008194.tif 000012
【図３】
0006008194.tif 000013
【図４】
0006008194.tif 000014
【図５】
0006008194.tif 000015
【図６】
0006008194.tif 000016
【図７Ａ】
0006008194.tif 000017
【図７Ｂ】
0006008194.tif 000018
【図８】
0006008194.tif 000019
【図９】
0006008194.tif 000020