演算部

演算部は，Input strモジュール，Radix4モジュール，Nextモジュールで構成されてい る．Input strモジュールは1段のステージで構成されている．Input strステージは，Mem ステージから外部から入力されたデータを格納したアドレスを受け取る．Memステージか らバタフライ演算可能となるアドレスを受け取ると，アドレッシング部にcolorを付加して BAを出力する．それ以外のアドレスが入力されたときは，転送制御回路の転送信号を削除 することで，パケットの消去を行っている. この時，BAの発行回数は外部から入力される colormaxによって制限される．colorはBAに付加されるたびにインクリメントされて次の BAに付加される．colorがcolormaxを超えた場合，無条件でパケットの消去を行うため，

回路を流れるストリーム数をcolor_maxで制限することができる．

図3.3 Radix4モジュールのステージ構成

Radix4モジュールは，complexステージ，sync ステージ，additionステージの三つの

3.3 基本回路構成

ステージに分かれている．ステージの構成を図3.3に示す．complexステージは，回転因子 とデータを乗算するステージである．sync ステージは，バタフライ演算を行うために必要 なデータの同期を取っている．パケットが持つデータの数は一つであるため，基数個のデー タによってバタフライ演算を行うには，データの同期を取る必要がある．今回構成した回 路は，基数4のバタフライ演算なので，4つのデータの同期を取っている．stream genモ ジュールでアドレスを生成する際に，indexが付与される．このindexはバタフライ演算の データの入力順を保つためにある．なので，syncステージでは，indexの値によって，デマ ルチプレクサで出力先を選択している．出力先はそれぞれ，異なる数のデータラッチを構え ている．バタフライ演算のデータを持っている先頭パケットから最後尾のパケットまでは，

最後尾のパケットが入力されるまでの待機する回数が異なる．その待機の回数をデータラッ チの数で調整している．後段のadditionステージには，同期を取った4つのデータをまと めて出力している．additionステージは，バタフライ演算の加算を行うステージである．バ タフライ演算の加算処理の途中で，虚数を乗算する処理が発生する．虚数の乗算は実数成分 のデータ部と虚数成分のデータ部を入れ替え，実数成分に-1を乗算している．additionス テージでは，加算結果を最後に4で除算処理を行っている．FFT長がNであるFFTの演 算結果は，入力データが1から-1までの値域であれば，最大値Nから最小値-Nの値域にな る．これは，固定小数点演算を行うには，整数を表現するbit幅が大きくなる．しかし，こ の除算処理を入れることで，FFTの中間データの値域が常に1から-1となり，出力結果も 1から-1となり，整数部のbit幅を少なくすることができる．

Nextモジュールは，SelectStepステージ，SameStepステージ，NextStepステージの 三つのステージで構成している．Next モジュールは，FFT の終了判定および次に行う バタフライ演算の BA の生成を行っている．SelectStepステージの構成を図 3.4 に示す．

SelectStepステージは，FFT内のバタフライ演算の段数であるstepの更新を行うステージ である．stepの値を保持するためにregisterを構えている．処理を行ったバタフライ演算の BAの値によって，更新するかを判断する．stepが切り替わった時の最初のバタフライ演算 のBAは常に0になる．そのため，BA=0が入力された時，registerはインクリメントされ

3.3 基本回路構成

図3.4 SelectStepステージの構成

たstepを書き込む．書き込みタイミングは，次ステージであるSameStepステージのC素 子から出力されるcp信号で行っている．

SameStepステージは，処理されたバタフライ演算と同じstep内のバタフライ演算のBA

の更新と，Stream genモジュールでバタフライ演算に必要なデータのアドレスを生成する 際に必要になるskipの生成を行っている．SameStepステージの構成を図3.5に示す．同ス テップ内のBAは，インクリメントされることで新たな BAとして更新することができる．

しかし，colormax分並列に処理を行っているので，ここでは，colormaxを加算することで BAを更新している．また，stepが更新される毎に，バタフライ演算によってデータが収束 していく．そのため，R^stepに組み分けされる．この組が切り替わり目は，_R^Nstep で求めるこ とができる．そのため，組が切り替わった時は，組の最初のバタフライ演算の BAに _R^Nstep

を加算することでBAを更新することができる．

NextStepステージは，処理されたバタフライ演算と異なる step内のバタフライ演算の

3.3 基本回路構成

図3.5 SameStepステージの構成

BA の更新，更新された step による skip の生成，FFT の終了判定を行っている．また 前段のSameStepステージで生成された BAとskip と自ステージで生成したBAとskip のどちらを出力するのかの選択もこのステージで行っている．NextStep ステージのBA は，SelectStepステージで生成されたrenewStepに基づいてBA，skipを生成する．また，

renewStepが最終ステップを超えた場合，全てのバタフライ演算が処理されたとみなし，終

了フラグを立てて，oprをreorder処理の命令に書き換える．