(57)【要約】多数の異なるタイプのアルゴリズムを行う方法およびシステムによれば、これらのアルゴリズムのすべてに対して同じ乗算器を使用することができる単一の数学エンジン（３０）が利用される。この数学エンジンには、選択的に制御される並列出力レジスタ（３３）と、少なくとも１つの選択的に制御されるメモリ（３１）と、複数のＰＥ（processing element）（４０）とが含まれる。この出力レジスタと、メモリと、ＰＥとは、パフォームされるアルゴリズムに応じて、選択的に制御される。
2006500684.tif 000002
【特許請求の範囲】
【請求項１】
処理すべきデータを受け取る並列出力シフトレジスタと、該並列出力シフトレジスタの出力を受け取り、データ出力を供給する複数のＡＬＵ（arithmetic logic unit）回路を使用する加算器ツリーを含むプロセッサと、を備え、前記シフトレジスタは、前記プロセッサの能力に基づいて前記処理すべきデータを選択的に出力するための選択可能な初期ポジションを含むことを特徴とする数学エンジン。
【請求項２】
請求項１において、前記並列出力シフトレジスタから出力を受け取り、該並列出力シフトレジスタからのデータを前記プロセッサに提供するマルチプレクサをさらに備えることを特徴とする数学エンジン。
【請求項３】
請求項２において、前記シフトレジスタからの出力を選択的にイネーブルにする少なくとも１つのイネーブル回路を備えたことを特徴とする数学エンジン。
【請求項４】
請求項１において、前記データは、実数部及び虚数部を含むことを特徴とする数学エンジン。
【請求項５】
複数の異なるタイプの計算を行う計算ユニットであって、
並列出力シフトレジスタと、
該並列出力シフトレジスタから出力を受け取り、複数のＡＬＵ（arithmetic logic unit）を備える加算器ツリーに出力を提供するマルチプレクサと、
前記並列出力シフトレジスタを選択的にイネーブルにする選択回路と
を備え、
前記マルチプレクサは、前記加算器ツリーに前記入力データのある特定の部分を供給して異なる計算を行うことを特徴とする計算ユニット。
【請求項６】
請求項５において、少なくとも前記加算器ツリーのデータ幅の倍数であるデータ幅を有する少なくとも１つの選択可能なメモリをさらに備えたことを特徴とする計算ユニット。
【請求項７】
計算を行う数学エンジンであって、
入力データを記憶する少なくとも１つの入力メモリと、
該少なくとも１つの入力メモリから前記入力データを受け取り、複数のフォールドを介して選択可能な出力を提供する選択可能なメモリであって、前記フォールドが、それぞれ、本選択可能なメモリ内に少なくとも１つのポジションを含む選択可能なメモリと、
前記選択可能なメモリから出力を受け取り、選択的に出力を供給する複数のプロセッサを有するプロセッサアレイと
を含むことを特徴とする数学エンジン。
【請求項８】
請求項７において、所望の数学計算に応じて、前記少なくとも１つの入力メモリおよび前記選択可能なメモリを選択的に制御するイネーブル回路をさらに備えたことを特徴とする数学エンジン。
【請求項９】
請求項８において、前記プロセッサアレイから出力を受け取り、前記出力を処理する複数のＡＬＵ（arithmetic logic unit）を有する加算器ツリーと、
該加算器ツリーからの各出力を受け取り蓄積するアキュムレーション回路と
をさらに含み、
前記イネーブル回路は、さらに、前記加算器ツリーの少なくとも一部を制御し、前記所望の数学計算をサポートする
ことを特徴とする数学エンジン。
【請求項１０】
複素関数を解くコンピュテーション回路であって、
複素解用の入力データを受け取るメモリと、
前記複素関数用の演算因子を記憶する記憶領域と、
前記メモリからの入力と前記演算因子とを受け取るマルチプレクサと、
前記メモリによって記憶された多くのビット位置に従って処理する処理アレイ回路であって、前記マルチプレクサからの出力と前記入力データの少なくとも一部とを含む処理アレイ回路と、
前記プロセッサアレイから出力を受け取り、加算出力を供給する複素加算器ツリーと、
該加算器ツリーから出力を受け取り、蓄積された複素出力を供給するアキュムレータ回路と
を備えたことを特徴とするコンピュテーション回路。
【請求項１１】
請求項１０において、前記メモリは、選択可能な初期ポジションを有する並列出力シフトレジスタを含むことを特徴とするコンピュテーション回路。
【請求項１２】
請求項１０において、本コンピュテーション回路は、ＤＦＴ（discrete Fourier transform）を行うため回転因子を演算因子として供給し、前記マルチプレクサは、その入力を前記メモリおよび前記演算因子から受け取ることを特徴とするコンピュテーション回路。
【請求項１３】
複素関数を解くコンピュテーション回路であって、
解用の複素入力データを受け取るメモリと、
回転因子を記憶するための記憶領域と、
前記メモリからの前記複素入力データと、前記記憶領域からの前記回転因子とを受け取るマルチプレクサと、
前記マルチプレクサからの出力および前記入力データの少なくとも一部を含み、前記メモリによって記憶された多くのビット位置に従ってデータを処理する処理アレイ回路と、
前記プロセッサアレイから出力を受け取り、加算出力を供給する複素加算器ツリーと、
前記加算出力を計数するアキュムレータと
を備えたことを特徴とするコンピュテーション回路。
【請求項１４】
請求項１３において、前記メモリは、選択可能な初期ポジションを有する並列出力シフトレジスタを含むことを特徴とするコンピュテーション回路。
【請求項１５】
複素関数を電子的に解く方法であって、
第１メモリから複素解用の入力データを供給するステップと、
第２メモリから前記複素関数用の演算因子を供給し、前記演算因子と、前記第１メモリからのデータとをマルチプレクシングして得られたデータを供給するステップと、
前記マルチプレクシングされたデータの選択部分を、並列出力として処理アレイに供給するステップであって、前記選択部分が、前記複素関数に依存するステップと
を備えたことを特徴とする方法。
【請求項１６】
請求項１５において、前記処理アレイは、複数の加算器を含むことを特徴とする方法。
【請求項１７】
請求項１５において、
ＤＦＴ（discrete Fourier transform）を行うため、回転因子を前記演算因子として供給するステップと、
前記処理アレイの少なくとも一部を選択的に関与させ、前記プロセッサアレイによって処理されるデータサイズを制御するステップと
を備えたことを特徴とする方法。
【請求項１８】
請求項１５において、前記プロセッサアレイからのデータ出力を蓄積するステップをさらに備えたことを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複素乗算器アレイの出力を計算するために数学エンジンを利用することに関する。特に、本発明は、複数の数学計算を行うためにアクセス可能な計算量的に効率的な（computationally efficient）数学エンジンである。
【背景技術】
【０００２】
最新のワイヤレス通信システムは、一般に、信号処理を行うのに膨大な量の数学計算を必要とする。このような計算は、一般に、プロセッサおよびＡＳＩＣ（application specific integrated circuit）によって行われる。
【０００３】
受信機用の標準のＡＳＩＣ設計では、多数のアルゴリズムをインプリメントし計算する必要があり、これらのアルゴリズムが、割り当てられた時間中に計算を完了するために、多数の並列乗算を必要とすることがしばしばある。これらのアルゴリズムは、典型的には、多数のマトリクス−マトリクス乗算およびマトリクス−ベクトル乗算と、多数のＤＦＴ（discrete Fourier transform）計算およびＦＦＴ（fast Fourier transform）計算とからなる。乗算器は、ＡＳＩＣ上で大きなスペースを占めるので、いくつかのアルゴリズムに対して同じ乗算器を適用できる解決策を考案することが望ましい。
【０００４】
様々な現在のワイヤレス技術、例えば、ＷＣＤＭＡ、ＷＴＴ、ＣＤＭＡ２０００、８０２．１Ｘ、ＴＤＳＣＤＭＡ、ＦＤＤ、ＴＤＤをサポートするため、また、現時点では企図されていない他の将来のシステムアーキテクチャをサポートするため、ある共通の計算を用いることができる。共通に行われる１つのこのようなタイプの計算としては、内積乗算がある。内積計算は２つのマトリクスを演算する標準の機能である。例えば、内積計算は、チャネル推定およびデータ推定を行うのに必要となる。広帯域ＴＤＤシステムにおいては、このような計算として、素因数ＦＦＴの計算と、マトリクスとマトリクスとの乗算と、マトリクスとその複素共役転置マトリクスとの乗算と、マトリクスとベクトルとの乗算とを含めることができる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
一般に、いくつかの内積計算は、単一の通信装置によって行わなければならず、したがって、この通信装置は、必要とされる計算に対応できるだけの処理能力を有しなければならない。現在、それぞれのアルゴリズムは、そのアルゴリズム自体の数学的な機能をインプリメントするため、専用のハードウェアを使用している。ハードウェアを繰り返し使用して演算効率を最大にできるシステムを開発することが有利になろう。演算効率には、処理時間と、処理を行うためのシリコンチップの面積と、このシリコンチップが処理において必要とする電力とが含まれるが、これらに限定されるものではない。
【課題を解決するための手段】
【０００６】
本発明によれば、ハードウェアを効率的に利用するため、複数のタイプの数学計算を行う数学エンジンが提供される。本発明は、並列出力を有するメモリを含む。この並列出力を使用して、論理的に隣接した値を並列に選択的に出力される１つまたは複数の値を記憶する。この記憶された値の長さ、例えばベクトルの長さが、計算区域（computational section）の容量よりも大きい場合、このメモリは、全ベクトルに対する数学的な実行を完了できる論理シーケンスにおいて、このベクトルの一部（フォールド（fold）という。）を提供できるように、アドレスされる。
【０００７】
数学エンジンのオペレーションを制御するため、データを転送し、かつ適正な数学計算を行うことができるイネーブル信号を選択的に使用することによって、異なるアルゴリズムの結果が生成される。こうすると、異なるタイプの計算を行う数学エンジンの柔軟性が高まるという利点が得られ、かつ、信号プロセッサを設計する際に必要とされる半導体のスペースが小さくなる経済的なプロセッサ回路も得られる。
【発明を実施するための最良の形態】
【０００８】
次に、図面を参照して本発明を説明する。これらの図面において、同じ参照符号は同一要素を示す。
【０００９】
本発明は、複数の異なる別々のアルゴリズムを処理する単一の数学エンジンに関する。この数学エンジンでは、これらすべてのアルゴリズムに対して同じハードウェアを使用することができる。乗算器は、ＡＳＩＣ上でかなりのスペースを必要とするが、本発明によれば、ＡＳＩＣに必要とされるスペースが小さくなる。本発明に係る数学エンジンは、ハードウェアの時間稼働率を高めることによって、必須の計算を行う上で極めて効率的でもある。この数学エンジンの効率は、入力マトリクスのサイズおよびＰＥの数によって決まる。
【００１０】
この数学エンジンは、一般に、少なくとも２つの入力と１つの出力とを有する。これらの入力は、直列入力および並列入力を含み、この並列入力の幅は、ＰＥ（processing element）の数と同じである。ＰＥの数は、ベクトル全体、ベクトルの一部、またはマトリクスのベクトルになるように最適化することができる。これら並列入力および直列入力は、ともに、シフトレジスタまたは別のタイプの直列アクセスレジスタにロードして、異なるタイプの演算を行うことができる。この並列出力シフトレジスタは、並列出力を有し、かつ記憶したデータを迅速に出力できるメモリである。このシフトレジスタの並列出力は、ＰＥの数によって幅が決まる論理的に隣接した値が、直列アクセスレジスタの機能を実施できるか、選択可能な出力を有する並列出力シフトレジスタの機能を実施できるか、あるいは、２次並列入力にアクセスできるようにマルチプレクシングされる。１次並列入力と、シフトレジスタの並列入力をマルチプレクシングしたものと、２次並列入力とは、複素乗算器および加算器ツリーへの入力となる。この加算器ツリーにより、この数学エンジンによって行われる計算の効率が高まる。こうすると、各演算ごとに、データをレジスタ内にできるだけ迅速に移動させることができ、かつ、この演算の内部ステップが効率よく行われるように、データを再構築することができる。
【００１１】
好ましい実施形態では、並列出力シフトレジスタは、論理的に隣接したデータ値からデータを出力し、この出力を使用して、選択的に並列出力する値が計算区域に記憶される。この記憶されるベクトルの長さが、計算区域の容量よりも大きい場合、並列出力シフトレジスタは、全ベクトルに対する数学的な実行を完了できるシーケンスにおいて、このベクトルの一部が提供されるようにアドレスされる。その結果、ほとんどすべてのクロックが、演算を行うためのデータを準備する複数のステップに費やされずに、計算に用いられる。この並列出力シフトレジスタを所与の長さの出力回路と結合させると、並列出力ｎ−フォールドシフトレジスタになる。すなわち、このメモリの記憶領域（store）が、計算区域のデータ幅（すなわち、ＰＥの数）のｎ倍になる。
【００１２】
加算器ツリーは、値をアキュムレータに供給し、このアキュムレータにより、多数の異なるマトリクス−マトリクス乗算およびマトリクス−ベクトル乗算を行うことができ、かつ、ＡＨＡおよびＡＨｒのような計算を効率よく行うことができる。
【００１３】
本発明によれば、この数学エンジンによって行われる内積計算には、チャネル推定およびデータ推定に必須の複数の異なるタイプの乗算、例えば、素因数ＦＦＴと、マトリクスとマトリクスとの乗算と、マトリクスと複素共役転置マトリクスとの乗算と、マトリクスとベクトルの乗算とが含まれるが、これらに限定されるものではない。
【００１４】
図１は、本発明に従って作製される数学エンジン３０の概略ブロック図を示す。数学エンジン３０には、ＰＰＤＩＳ（primary parallel data input source、１次並列データ入力源）３１と、デマルチプレクサ３２と、ｎ−フォールドシフトレジスタ３３と、ＳＤＩＳ（serial data input source、直列データ入力源）３４と、マルチプレクサ３５と、ＳＰＤＩＳ（secondary parallel data input source、２次並列データ入力源）３６と、が含まれる。また、複数のアレイ要素（図に示す４１〜４４）からなる複素乗算器ＰＥアレイ４０と、複素加算器ツリー５５と、複素アキュムレータ５６も含まれる。複素アキュムレータ５６には、初期条件入力マルチプレクサ５８と、サマー（summer）５７と、サマー出力レジスタ５９とが含まれる。サマー出力レジスタ５９から、蓄積された出力が得られる。ＰＥアレイ４０は、内積出力を含めて、並列複素乗算機能を提供する。
【００１５】
演算時において、ＰＰＤＩＳ  ３１の出力は、Ｑ個のロケーションを含む。ＳＤＩＳ  ３４は、シフトレジスタ３３に複素受信チップシーケンス（complex received chip sequence）を提供する。ＳＤＩＳ  ３４からのこの出力を用いて、シフトレジスタ３３を直列ロードする。シフトレジスタ３３は、ｎ個のフォールドを有し、各フォールドは、それぞれ複素値を含むＱ個のロケーションを有する。さらに、シフトレジスタ３３は、任意のフォールドに、ＰＰＤＩＳ  ３１からのＱ個のロケーションからの値をロードし、また、クロックごとに、Ｘ個のゼロのロケーションをシフトインすることができる。マルチプレクサ３５は、シフトレジスタ３３からの出力およびＳＰＤＩＳ  ３６からのＱ個のロケーションの複素値を受け取る。
【００１６】
マルチプレクサ３５からの出力は、複素乗算器アレイ４０に提供される。複素乗算器アレイ４０を使用して、複素加算器ツリー５５に、対応する入力を提供する。複素加算器ツリー５５は、Ｑ入力複素加算器ツリーである。
【００１７】
加算器ツリー５５は、その出力をアキュムレータ５６に提供する。アキュムレータ５６には、サマー５７のところで、マルチプレクサ５８を介して供給される初期条件が提供される。サマー５７の出力結果は、出力レジスタ５９にストアされる。
【００１８】
図１に示す本発明に係る数学エンジン３０は、いくつかの異なるタイプの計算を行うことができるので、別々のプロセッサが不要になり、その結果、このような数学計算に必要とされるＡＳＩＣの実装面積が大幅に小さくなる。以下、ＷＴＤＤ通信システムにおける好ましい実施形態の３つの異なる応用例、１）自己相関マトリクス（ＡＨＡ）の生成と、２）白色化整合フィルタリング（ＡＨｒ）と、３）Steinerアルゴリズムと、によって行われるチャネル推定を説明するが、応用例はこれらに限定されるものではない。ただし、本発明の趣旨および範囲から逸脱しない限り、他のアルゴリズムを実施できることは、当業者にとって当然のことである。
【００１９】
図２Ａ〜図２Ｃおよび図３Ａ〜図３Ｇを参照して、ＡＨＡ関数をインプリメントした本発明の実施形態を説明する。この実施形態では、本発明に係る図１の数学エンジンを利用してＡＨＡ関数をインプリメントするプロセスを説明する。ＡＨＡ関数は、数学エンジンによって計算される関数の中で最も複雑なものの１つである。というのは、ＡＨＡ関数は、部分的に記憶されたマトリクスと、この同じ部分的に記憶されたマトリクスであって部分的に計算された結果のみで異なるやり方でアクセスされたマトリクスと、から計算されるからである。演算の順序は、これらのマトリクスの論理的な数列に基づくのではなく、これらのマトリクスが、数学エンジンの既存の機能にどの程度適合しているかに基づく。
【００２０】
図２Ａは、マトリクスＡＨと、マトリクスＡと、マトリクスＡＨＡとを、簡単なフィールドマトリクス（field matrix）で表現したものである。ＡＨ行ブロックのみをメモリに記憶させ、そして、マトリクスＡＨ全体およびマトリクスＡ全体は、記憶された行ブロックをアドレスするアドレシング関数として表される。この関数はデータにアクセスできる能力を有する。このデータをＡマトリクスにおけるように使用するため、このデータの虚部が反転されている。得られたマトリクスＡＨＡは、圧縮して記憶され、マトリクスＡＨおよびマトリクスＡから構築されたもののように見える。
【００２１】
このＡＨサブブロックは、単一のアクセスメモリ（図１のＰＰＤＩＳ  ３２）にしか記憶されないので、第１ステップは、このＡＨメモリの内容を、シフトレジスタ３３にコピーすることであり、また、そこで、第２および第３の行ブロックを表すようにこの内容を操作して、これらのブロックがこの計算で用いるデータウィンドウによってしか見えないようにすることができる。マトリクスＡＨの幅は、ＳＦ（拡散率）＋Ｗ（チャネル応答長）−１であり、２０個のＰＥしかないので、各ＡＨのワードには２０個の値がある。フォールドと呼ぶ２０個の値のチャンク（chunk）内にデータを移動させる（この場合には、例えば、ＳＦ＋Ｗ−１＝４４であり、そのため、３つのフォールドがある）。図３Ａ、図３Ｂ、および図３Ｃは、ＡＨの最初の行をシフトレジスタにロードするところを示す最初の３つのクロックサイクルを示す。
【００２２】
図３Ａでは、ＡＨのブロックの第１行の第１フォールドを、シフトレジスタの第１フォールド記憶領域にロードする。図３Ｂでは、ＡＨ行ブロックの第１行の第２フォールドを、シフトレジスタの第２フォールド記憶領域にロードする。図３Ｃでは、ＡＨ行ブロックの第１行の第３フォールドを、シフトレジスタの第３フォールド記憶領域にロードする。
【００２３】
図２Ｂは、このマトリクスの計算される部分を強調して表示する。行全体を強調して表示しているが、計算では、このマトリクスの破線の内側の部分しか使用しない。図２Ｂは、マトリクスＡＨの第１行と、マトリクスＡの第１列とを乗算して、マトリクスＡＨＡの第１の値が得られるところを示す。
【００２４】
マトリクスＡＨとマトリクスＡとの行および列のブロックは、ＰＥの数よりも大きいので（この実施形態では、行および列のサイズは４４）、この計算は、一度に１フォールドずつ行われる（すなわち、３クロックで３フォールドが行われる）。行全体が終了するまで、フォールドの各部分が乗算され、（図１に示す）蓄積レジスタ５９に蓄積される。終了した時点で、結果が数学エンジンの外部に記憶される。マトリクスＡＨは、シフトレジスタの値によって表され、マトリクスＡの値は、ＡＨメモリにおいて、虚数値の逆関数で表される。これは、（図１に示す）複素乗算器アレイ４０内で、これら虚数値の共役をとることによって行われる。
【００２５】
図３Ｄに、マトリクスＡＨの第１行の第１フォールドと、マトリクスＡの第１列の第１フォールドとの乗算を示す。この乗算の結果は、蓄積レジスタ５９に記憶される。図３Ｅに、マトリクスＡＨの第１行の第２フォールドと、マトリクスＡの第１列の第２フォールドとの乗算を示す。この乗算の蓄積結果は、前の蓄積値に加算され、蓄積レジスタ５９に記憶される。図３Ｆに、マトリクスＡＨの第１行の第３フォールドと、マトリクスＡの第１列の第３フォールドとの乗算を示す。この乗算の蓄積結果は、前の蓄積値に加算され、蓄積レジスタ５９に記憶される。蓄積レジスタ５９に記憶された値は、マトリクスＡＨＡの第１ロケーションを表し、さらなる処理のために外部に記憶される。この乗算には、各フォールドごとに１クロックで、合計３クロックかかるが、マトリクスＡＨの第１行の第１フォールドと、マトリクスＡの第２の有効な列の第１フォールドと、の乗算を示す図３Ｇには、第１クロックしか示していない。この乗算の結果は、蓄積レジスタ５９に記憶される。このプロセスは３クロックの間続き、最終的に、蓄積された結果は、さらに処理するため、外部に記憶される。
【００２６】
図２Ｃからは、１６個のゼロがどのようにシフトレジスタ３３の左側からシフトインされ、その結果、マトリクスＡＨの第２行ブロックが、この計算ウィンドウで用いられる入力ウィンドウを通して見られる、ことが分かる。このプロセスには１クロックしかかからず、残りの計算と並行して実行することができ、それによってかなりの時間が節約される。マトリクスＡＨのサブブロックの第１行をこのようにシフトしたものには、計算ウィンドウで用いられる値の、ＡＨのサブブロックのシフトされたサブブロックごとに、マトリクスＡのサブブロックのすべての有効な列を乗算しなければならない。
【００２７】
ＡＨの第１の有効な行のすべてのフォールドに、計算に用いられる入力ウィンドウに含まれるマトリクスＡのサブブロックのすべての有効な列を乗算した後で、他の有効な行ごとに、この同じプロセス全体を実行する。このように順番が狂ったプロセスが実行されるので、ＡＨのサブブロックのシフトされたサブブロック用にＡＨの行をロードし直す必要がない。
【００２８】
次に、第２実施形態として、図４Ａ〜図４Ｄおよび図５Ａ〜図５Ｉを参照して、図１の数学エンジンによって行われるＡＨｒ関数を説明する。ＡＨｒ関数は、マトリクスＡＨ全体と、受信したベクトル（ｒ）との乗算である。マトリクスＡＨは、全体として記憶されておらず、ＡＨ行ブロックと呼ぶ比較的小さい部分しか実際に記憶されていない。実際には、マトリクスＡＨ中の他のすべての値は、ＡＨ行ブロックの繰り返しか、またはゼロである。したがって、ＡＨは、ＡＨ行ブロックの複素アドレシング方式として記憶することができる。
【００２９】
例えば、広帯域ＴＤＤの３Ｇ（third generation）データバーストタイプ１または３の中には、全部で６１個のＡＨ行ブロックがあり、バーストタイプ２のタイムスロットには全部で６９個のＡＨ行ブロックがある。実際には、２つのベクトルｒがあり、一方はデータフィールド１用のものであり、他方はデータフィールド２用のものである。簡単にするために、１つのベクトルｒについてこの関数を説明する。ついで、第２のデータのセットのベクトルについてこのプロセスを繰り返す。
【００３０】
図４Ａは、ＡＨｒのマトリクス乗算を示す図である。ＡＨ行ブロックは、マトリクスＡＨ全体を通して繰り返され、残りはすべてゼロである。ＡＨ行ブロックの行の、４つの行のうち２つは前の処理によって無効になっている。
【００３１】
ＡＨｒ関数を計算する第１ステップは、数学エンジンのシフトレジスタ３３全体に、ベクトルｒの値をあらかじめロードすることである。（図１に示す）シフトレジスタ３３は、ＳＤＩＳ  ３４によって直列ロードされる。マトリクスＡＨは、ＰＰＤＩＳ  ３１で提供される。
【００３２】
ＡＨｒの計算のステップ的なプロセスを開始するために、図４Ｂに、マトリクスＡＨの第１行とベクトルｒとの計算を示す。
【００３３】
ベクトルＡＨの第１のＳＦ＋Ｗ−１の値だけがゼロでない値を含むので、この行の積の第１部分のみを計算する。ＰＥは２０個しかないので、複数のステップ（例えば、フォールド）で乗算を実行しなければならない。この実施形態では、Ｗが２９なので、ＳＦ＋Ｗ−１は４４になる。ＳＦ＋Ｗ−１をＰＥの数（２０）で除算し、それを切り上げると、ＡＨの行の有効な部分と、ベクトルｒの有効な部分との全内積計算を行うには、全部で３つのフォールドまたは３つのクロックの乗算および蓄積を行う。図５Ａ、図５Ｂ、および図５Ｃに示す最初の３つのクロックに、このマトリクスの行とベクトルの内積の最初の値を計算する段階的なプロセスを示す。
【００３４】
図５Ａは、ＡＨの第１行の第１フォールドに、ベクトルｒの第１フォールドを乗算し、その結果を蓄積レジスタ５９に記憶するところを示す。図５Ｂに、ＡＨの第１行の第２フォールドに、ベクトルｒの第２フォールドを乗算し、その結果を、現時点で蓄積レジスタ５９内にある結果に加算するところを示す。図５Ｃに、ＡＨの第１行の第３フォールドに、ベクトルｒの第３フォールドを乗算し、その結果を、現時点で蓄積レジスタ５９内にある結果に加算するところを示す。この時点で、得られた蓄積値は、第１のＡＨｒ計算ポイントとして記憶される。
【００３５】
次のステップは、現時点で計算された記号（シンボル）を用いて、このＡＨ行ブロックの次の有効な行の計算を行うステップである。これは、図４Ｃに示すように、ベクトルｒの同じ部分にＡＨの新しい行を乗算するというものである。このベクトルｒは、同一にできるが、ＡＨメモリでは、ＡＨの異なる行にアクセスする。図５Ｄ、図５Ｅ、および図５Ｆに、この場合も、３つのクロックを示す。これらの図は、３つのすべてのフォールドの乗算／蓄積を示している。図５Ｄは、ＡＨの第３行の第１フォールドに、ベクトルｒの第１フォールドを乗算し、その結果を蓄積レジスタ５９に記憶する例を示す。図５Ｅは、ＡＨの第３行の第２フォールドに、ベクトルｒの第２フォールドを乗算し、その結果を、現時点で蓄積レジスタ５９内にある結果に加算する例を示す。図５Ｆは、ＡＨの第３行の第３フォールドに、ベクトルｒの第３フォールドを乗算し、その結果を、現時点で蓄積レジスタ５９にある結果に加算する例を示す。この時点で、得られた蓄積値は、第２のＡＨｒ計算ポイントとして記憶される。
【００３６】
次のステップは、このベクトルｒを用いて、ＡＨの第２行ブロックの計算を開始するステップである。このステップでは、ＡＨの第２行サブブロックの有効な各行にベクトルｒが乗算される。ＡＨのサブブロックが乗算されるベクトルｒは、異なる。というのは、次の行には、後側から、１６個の値のみがシフトインされているからである。図４Ｄに、計算に関与する部分を強調して表示する。
【００３７】
記憶されたＡＨ行ブロックは移動しないので、このベクトルｒのうち、新しいＡＨ行ブロックの行が乗算される部分を、アラインし直す（re-align）ため、このベクトルｒをシフトしなければならない。これは、シフトレジスタ３３に、１６個のクロックで１６個の新しい値をシフトインし、ベクトルｒの最初の複数の値を切り捨てる、ことにより行われる。このプロセスにおける最初の２つのクロックを、図５Ｇおよび図５Ｈに示すが、残りのクロックについては推測できるであろう。その後、第１のＡＨ行ブロックについて用いたのと同じプロセスを開始するが、この繰り返しオペレーションの最初のクロックを、第１のＡＨ行ブロックの最初のクロックと比較して示す。
【００３８】
図５Ｇは、シフトレジスタにおいて、ベクトルｒの第１の値が右側からシフトインされ、このシフトレジスタに入れられた１番目の値が失われる例を示す。図５Ｈは、ベクトルｒの第２の値がこのシフトレジスタにシフトインされ、このレジスタに入れられた２番目の値が失われる例を示す。図５Ｉは、ＡＨｒの第１行ブロックの第１の計算の場合とまったく同様に、ＡＨの第１行に、新たにシフトインされたベクトルｒの第１フォールドが乗算され、その結果が蓄積レジスタ５９に記憶される例を示す。このプロセスは、ＡＨの各行ブロックごとに、ＡＨの各行ブロックの有効行のフォールドについて、継続する。
【００３９】
第３の実施形態を説明する。図１の数学エンジンによって行われるSteinerアルゴリズムを、図６Ａ〜図６Ｄを参照して説明する。これらの図は、この数学エンジンを使用して、４５６ポイントSteinerについて３ポイントＤＦＴを行うプロセスを示す。図６Ａ〜図６Ｃは第１のＤＦＴを計算する例を示すが、各図においてクロックは異なる。図に示すように、このＤＦＴのうちの最初の３つのアドレスは、既にメモリに直列にロードされており、そのため、これら３つのアドレスには、ＰＰＤＩＳ  ３１（図１）を介して同時に並列にアクセスすることができる。このＤＦＴのために用いられる回転因子（Twiddle Factors）は、ＳＰＤＩＳ  ３６（図１）を介して入力される。
【００４０】
これら３つのクロックでは、それぞれ、アドレス０、アドレス１５２、およびアドレス３０４における第１のＤＦＴ入力には、ＤＦＴのこのポイントに固有な回転因子の３つのセットの１つが、乗算される。これら３つの計算結果は、図１の数学エンジン外に送られる。
【００４１】
図６Ａにおいて、回転因子セット１の３つのポイントに、ＤＦＴ  １の３つのポイントが乗算され、その結果が外部に記憶される。第２のＤＦＴの第１ポイントがメモリの次の行にロードされる。図６Ｂにおいては、回転因子セット２の３つのポイントに、ＤＦＴ  １の３つのポイントを乗算し、この乗算結果を外部に記憶する。第２のＤＦＴの第２ポイントをメモリの次の行にロードする。図６Ｃにおいては、回転因子セット３の３つのポイントに、ＤＦＴ  １の３つのポイントを乗算し、この乗算結果を外部に記憶する。第２のＤＦＴの第３ポイントをこのメモリの次の行にロードする。
【００４２】
図６Ｄは、次のＤＦＴの第１ポイントが、回転因子セット１と計算され、回転因子セット２及び３との計算が後続のクロックにおいて行われる例を示す。６４ポイントＤＦＴについての計算は、わずかに異なる方法で行われる。すなわち、この方法においては、ＤＦＴセットと回転因子セットとの乗算が、連続した４つのクロックにおいて行われ、この乗算結果が蓄積され、その後、記憶される。
【００４３】
図６Ｄにおいては、回転因子セット１の３つのポイントに、ＤＦＴ  ２の３つのポイントが乗算され、この乗算結果が外部に記憶される。第３のＤＦＴの第１ポイントがメモリの次の行にロードされる。この乗算が、３ポイントＤＦＴについて、それぞれ、３つの回転因子セットすべてについて、継続される。他のＤＦＴについても同様である。すなわち、８ポイントＤＦＴは８つの回転因子セットについて行われ、１９ポイントＤＦＴが１９個の回転因子セットについて行われ、６４ポイントＤＦＴが６４個の回転因子セットについて行われる。
【００４４】
図７Ａ〜図７Ｃを参照すると、本発明に係る数学エンジンの入力を選択的にイネーブルにすると、この数学エンジンが、ＡＨＡ、ＡＨｒ、および、Steiner関数をパフォームできることができる、ことが分かる。図７Ａに示すように、ＡＨＡ関数については、ＡＨＡ演算において、システム応答マトリクス（ＡＨ）を提供するため、ＰＰＤＩＳ入力のみが使用され、このシステム応答マトリクスに、その複素共役転置マトリクスの値が乗算される。このシフトレジスタの並列ロード機能を用いると、この複素乗算器アレイにはその入力の１つの共役をとる能力があるので、必須のフォールドの個数によって、ｘ個のクロックサイクルにおいて（ただし、１≦ｘ≦ｎ、ｎはフォールドの最大個数）各ポイントが計算される。
【００４５】
図７Ｂを参照すると、ＡＨｒ関数については、ＰＰＤＩＳにより、システム応答マトリクス（ＡＨ）が提供される。さらに、直列入力を利用して、受信したベクトル（ｒ）のデータフィールドがＡＨｒ演算に提供される。あるタイムスロットについて、このシステム応答マトリクス（ＡＨ）に、受信したベクトルｒのデータフィールドが乗算される。このシフトレジスタの直列ロード機能を用いて、このデータフィールドがシフトレジスタにロードされ、システム応答マトリクスが１次並列入力に提供される。得られるベクトルの各要素は、必須のフォールドの個数によって、ｘ個のクロックサイクルにおいて（ただし、１≦ｘ≦ｎ、ｎはフォールドの最大個数）計算される。
【００４６】
図７Ｃに示すように、Steinerオペレーション（ＦＦＴ）については、ＰＰＤＩＳにより、ＦＦＴ入力データセットが提供され、ＳＰＤＩＳにより、ＦＦＴ回転因子が提供される。ｍポイントＦＦＴにおけるＦＦＴオペレーションにおいて、ＰＰＤＩＳによってこのデータセットの適正なｍ個のポイントが複素乗算器アレイに供給され、ＳＰＤＩＳによって適正なＦＦＴ回転因子が供給される。
【図面の簡単な説明】
【００４７】
【図１】本発明に係る数学エンジンを示すブロック図である。
【図２Ａ】システム応答マトリクス（ＡＨ）とその複素共役転置マトリクス（Ａ）とを乗算して、自己相関マトリクス（ＡＨＡ）を計算する説明図である。
【図２Ｂ】システム応答マトリクス（ＡＨ）とその複素共役転置マトリクス（Ａ）とを乗算して、自己相関マトリクス（ＡＨＡ）を計算する説明図である。
【図２Ｃ】システム応答マトリクス（ＡＨ）とその複素共役転置マトリクス（Ａ）とを乗算して、自己相関マトリクス（ＡＨＡ）を計算する説明図である。
【図３Ａ】ＡＨＡ関数に必須の計算を行う図１の数学エンジンを示す図である。
【図３Ｂ】ＡＨＡ関数に必須の計算を行う図１の数学エンジンを示す図である。
【図３Ｃ】ＡＨＡ関数に必須の計算を行う図１の数学エンジンを示す図である。
【図３Ｄ】ＡＨＡ関数に必須の計算を行う図１の数学エンジンを示す図である。
【図３Ｅ】ＡＨＡ関数に必須の計算を行う図１の数学エンジンを示す図である。
【図３Ｆ】ＡＨＡ関数に必須の計算を行う図１の数学エンジンを示す図である。
【図３Ｇ】ＡＨＡ関数に必須の計算を行う図１の数学エンジンを示す図である。
【図４Ａ】マトリクスＡＨと受信信号ベクトル（ｒ）との乗算を示す図である。
【図４Ｂ】マトリクスＡＨと受信信号ベクトル（ｒ）との乗算を示す図である。
【図４Ｃ】マトリクスＡＨと受信信号ベクトル（ｒ）との乗算を示す図である。
【図４Ｄ】マトリクスＡＨと受信信号ベクトル（ｒ）との乗算を示す図である。
【図５Ａ】ＡＨｒ関数に必須の計算を行う図１の数学エンジンを示す図である。
【図５Ｂ】ＡＨｒ関数に必須の計算を行う図１の数学エンジンを示す図である。
【図５Ｃ】ＡＨｒ関数に必須の計算を行う図１の数学エンジンを示す図である。
【図５Ｄ】ＡＨｒ関数に必須の計算を行う図１の数学エンジンを示す図である。
【図５Ｅ】ＡＨｒ関数に必須の計算を行う図１の数学エンジンを示す図である。
【図５Ｆ】ＡＨｒ関数に必須の計算を行う図１の数学エンジンを示す図である。
【図５Ｇ】ＡＨｒ関数に必須の計算を行う図１の数学エンジンを示す図である。
【図５Ｈ】ＡＨｒ関数に必須の計算を行う図１の数学エンジンを示す図である。
【図５Ｉ】ＡＨｒ関数に必須の計算を行う図１の数学エンジンを示す図である。
【図６Ａ】ＤＦＴに必須の計算を行う図１の数学エンジンを示す図である。
【図６Ｂ】ＤＦＴに必須の計算を行う図１の数学エンジンを示す図である。
【図６Ｃ】ＤＦＴに必須の計算を行う図１の数学エンジンを示す図である。
【図６Ｄ】ＤＦＴに必須の計算を行う図１の数学エンジンを示す図である。
【図７Ａ】入力源の選択的使用を示す図である。
【図７Ｂ】入力源の選択的使用を示す図である。
【図７Ｃ】入力源の選択的使用を示す図である。
【図１】
2006500684.tif 000003
【図２Ａ】
2006500684.tif 000004
【図２Ｂ】
2006500684.tif 000005
【図２Ｃ】
2006500684.tif 000006
【図３Ａ】
2006500684.tif 000007
【図３Ｂ】
2006500684.tif 000008
【図３Ｃ】
2006500684.tif 000009
【図３Ｄ】
2006500684.tif 000010
【図３Ｅ】
2006500684.tif 000011
【図３Ｆ】
2006500684.tif 000012
【図３Ｇ】
2006500684.tif 000013
【図４Ａ】
2006500684.tif 000014
【図４Ｂ】
2006500684.tif 000015
【図４Ｃ】
2006500684.tif 000016
【図４Ｄ】
2006500684.tif 000017
【図５Ａ】
2006500684.tif 000018
【図５Ｂ】
2006500684.tif 000019
【図５Ｃ】
2006500684.tif 000020
【図５Ｄ】
2006500684.tif 000021
【図５Ｅ】
2006500684.tif 000022
【図５Ｆ】
2006500684.tif 000023
【図５Ｇ】
2006500684.tif 000024
【図５Ｈ】
2006500684.tif 000025
【図５Ｉ】
2006500684.tif 000026
【図６Ａ】
2006500684.tif 000027
【図６Ｂ】
2006500684.tif 000028
【図６Ｃ】
2006500684.tif 000029
【図６Ｄ】
2006500684.tif 000030
【図７Ａ】
2006500684.tif 000031
【図７Ｂ】
2006500684.tif 000032
【図７Ｃ】
2006500684.tif 000033
【国際調査報告】
2006500684.tif 000034
2006500684.tif 000035