(57)【特許請求の範囲】
【請求項１】
基数４のバタフライ演算を、下記式
Ｘ０＝（ｘ０＋ｘ２）＋（ｘ１＋ｘ３）
Ｘ１＝（ｘ０−ｘ２）＋ｊ（ｘ１−ｘ３）
Ｘ２＝（ｘ０＋ｘ２）−（ｘ１＋ｘ３）
Ｘ３＝（ｘ０−ｘ２）−ｊ（ｘ１−ｘ３）
（ただし、ｘ０，ｘ１，ｘ２，ｘ３はバタフライ入力、Ｘ０，Ｘ１，Ｘ２，Ｘ３は演算結果データ）
に従ってパイプライン処理によって行うバタフライ演算器であって、
入力されたバタフライ入力を順に格納する第１のデータバッファと、
少なくとも前記第１のデータバッファに格納されたバタフライ入力を基にして、中間データとしてｘ０＋ｘ２、ｘ１＋ｘ３、ｘ０−ｘ２、ｊ（ｘ１−ｘ３）をサイクル毎に演算する第１の演算部と、
前記第１の演算部によって演算された中間データを順に格納する第２のデータバッファと、
少なくとも前記第２のデータバッファに格納された中間データを基にして、演算結果データをサイクル毎に演算する第２の演算部とを備え、
前記第１の演算部は、前記第２のデータバッファに格納された中間データを用いて演算を行うものである
ことを特徴とするバタフライ演算器。
【請求項２】
請求項１記載のバタフライ演算器において、
前記第１のデータバッファは、バタフライ入力をサイクル毎に順にシフトする，直列接続された２個のレジスタを備え、
前記第２のデータバッファは、中間データをサイクル毎に順にシフトする，直列接続された２個のレジスタを備え、
前記第１の演算部は、
当該バタフライ演算器に入力されたバタフライ入力および前記第２のデータバッファの第２段レジスタに格納された中間データのいずれか一方を選択出力する第１の選択回路と、
前記第１のデータバッファの第２段レジスタに格納されたバタフライ入力およびこのバタフライ入力に２を乗じたもののいずれか一方を選択出力する第４の選択回路と、
前記第１の選択回路の出力データに対して、前記第４の選択回路の出力データの加算または減算を行う第１の加減算器と、
前記第１の加減算器の出力データおよびこの出力データに虚数ｊを乗じたもののいずれか一方を、中間データとして選択出力する第２の選択回路とを備えたものであり、
前記第２の演算部は、
前記第１の演算部から出力された中間データおよび前記第２のデータバッファの第２段レジスタに格納された中間データのいずれか一方を選択出力する第３の選択回路と、
前記第３の選択回路の出力データに対して、前記第２のデータバッファの第１段レジスタに格納されたバタフライ入力の加算または減算を行い、加算または減算結果を演算結果データとして出力する第２の加減算器とを備えたものである
ことを特徴とするバタフライ演算器。
【請求項３】
基数４のバタフライ演算を行う場合には、下記式
Ｘ０＝（ｘ０＋ｘ２）＋（ｘ１＋ｘ３）
Ｘ１＝（ｘ０−ｘ２）＋ｊ（ｘ１−ｘ３）
Ｘ２＝（ｘ０＋ｘ２）−（ｘ１＋ｘ３）
Ｘ３＝（ｘ０−ｘ２）−ｊ（ｘ１−ｘ３）
（ただし、ｘ０，ｘ１，ｘ２，ｘ３はバタフライ入力、Ｘ０，Ｘ１，Ｘ２，Ｘ３は演算結果データ）
に従ってパイプライン処理によって行うバタフライ演算器であって、
入力されたバタフライ入力を格納する第１のデータバッファと、
少なくとも前記第１のデータバッファに格納されたバタフライ入力を基にして、中間データとしてｘ０＋ｘ２、ｘ１＋ｘ３、ｘ０−ｘ２、ｊ（ｘ１−ｘ３）をサイクル毎に演算する第１の演算部と、
前記第１の演算部によって演算された中間データを格納する第２のデータバッファと、
少なくとも前記第２のデータバッファに格納された中間データを基にして、演算結果データをサイクル毎に演算する第２の演算部とを備え、
基数２のバタフライ演算を行う場合には、前記第１の演算部は、中間データとしてｘ０＋ｘ２、ｘ１＋ｘ３、ｘ０−ｘ２、ｘ１−ｘ３をサイクル毎に演算可能であり、
前記第２の演算部は、０を加算することにより、入力した中間データと同じ値を演算結果データとして出力することにより、
当該バタフライ演算器は、２つの基数２のバタフライ演算を、下記式
Ｘ０＝ｘ０＋ｘ２
Ｘ１＝ｘ１＋ｘ３
Ｘ２＝ｘ０−ｘ２
Ｘ３＝ｘ１−ｘ３
に従って実行する
ことを特徴とするバタフライ演算器。
【請求項４】
請求項３記載のバタフライ演算器において、
前記第１のデータバッファは、バタフライ入力をサイクル毎に順にシフトする，直列接続された４個のレジスタを備え、
前記第２のデータバッファは、中間データをサイクル毎に順にシフトする，直列接続された２個のレジスタを備え、
前記第１の演算部は、
当該バタフライ演算器に入力されたバタフライ入力および前記第１のデータバッファの第４段レジスタに格納されたバタフライ入力のいずれか一方を選択出力する第１の選択回路と、
前記第１の選択回路の出力データに対して、前記第１のデータバッファの第２段レジスタに格納されたバタフライ入力の加算または減算を行う第１の加減算器と、
前記第１の加減算器の出力データおよびこの出力データに虚数ｊを乗じたもののいずれか一方を、中間データとして選択出力する第２の選択回路とを備えたものであり、
前記第２の演算部は、
前記第１の演算部から出力された中間データ、前記第２のデータバッファの第２段レジスタに格納された中間データ、および論理値“０”のいずれか１つを選択出力する第３の選択回路と、
前記第３の選択回路の出力データに対して、前記第２のデータバッファの第１段レジスタに格納されたバタフライ入力の加算または減算を行い、加算または減算結果を演算結果データとして出力する第２の加減算器とを備えたものである
ことを特徴とするバタフライ演算器。
【請求項５】
請求項３記載のバタフライ演算器において、
前記第１のデータバッファは、バタフライ入力をサイクル毎に順にシフトする，直列接続された２個のレジスタを備え、
前記第２のデータバッファは、中間データをサイクル毎に順にシフトする，直列接続された２個のレジスタを備え、
前記第１の演算部は、
当該バタフライ演算器に入力されたバタフライ入力および前記第２のデータバッファの第２段レジスタに格納された中間データのいずれか一方を選択出力する第１の選択回路と、
前記第１のデータバッファの第２段レジスタに格納されたバタフライ入力およびこのバタフライ入力に２を乗じたもののいずれか一方を選択出力する第４の選択回路と、
前記第１の選択回路の出力データに対して、前記第４の選択回路の出力データの加算または減算を行う第１の加減算器と、
前記第１の加減算器の出力データおよびこの出力データに虚数ｊを乗じたもののいずれか一方を、中間データとして選択出力する第２の選択回路とを備えたものであり、
前記第２の演算部は、
前記第１の演算部から出力された中間データ、前記第２のデータバッファの第２段レジスタに格納された中間データ、および論理値“０”のいずれか１つを選択出力する第３の選択回路と、
前記第３の選択回路の出力データに対して、前記第２のデータバッファの第１段レジスタに格納されたバタフライ入力の加算または減算を行い、加算または減算結果を演算結果データとして出力する第２の加減算器とを備えたものである
ことを特徴とするバタフライ演算器。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、高速フーリエ変換等で用いるバタフライ演算装置を構成するバタフライ演算器に関する。
【０００２】
【従来の技術】
近年、ディジタル通信技術と半導体集積技術の進歩に伴い、テレビ、ラジオ放送のディジタル化が進められている。地上波を用いたディジタル放送では、多くの場合、変復調方式にＯＦＤＭ（Orthogonal Frequency Division Multiplex ：直交周波数分割多重）が採用されている。ＯＦＤＭはいくつもの情報を限られた周波数帯域の中で効率よく伝送する方式であり、マルチパスの妨害に強いという地上波放送向けの特徴を持つ。しかし、ＯＦＤＭでは数千サンプルの大規模な高速フーリエ変換を行う必要があり、その実用化のためには高速フーリエ変換装置の低コスト化が重要な課題となっている。
【０００３】
高速フーリエ変換では、バタフライ演算と呼ばれる基本演算と演算データに回転子データを乗じる回転子乗算とを複数回行うことによって、演算を行う。そこで、高速フーリエ変換装置は、バタフライ演算と回転子乗算を行うバタフライ演算装置を備え、このバタフライ演算装置を繰り返し用いて高速フーリエ変換を行う。バタフライ演算として最も一般的なものとして、基数２のバタフライ演算がある。基数２のバタフライ演算を用いてサンプル数Ｎ＝２＾ｎ（ｎは正の整数、＾はべき乗を表す）の高速フーリエ変換を行う場合には、基数２のバタフライ演算をｎ・２＾（ｎ−１）回行う。
【０００４】
一方、大規模な高速フーリエ変換では、膨大な演算量を削減するため、基数４などの高基数のバタフライ演算を用いる場合が多い。高基数のバタフライ演算を用いた従来の高速フーリエ変換装置の一例として、基数４のバタフライ演算を用いて高速フーリエ変換を行うものが、A.Delaruelle et al. "A Channel Demodulator IC for Digital Audio Broadcasting"(In IEEE Custom Integrated Circuit Conference, May 1994 )に記載されている。
【０００５】
【発明が解決しようとする課題】
しかしながら、従来では、基数４のバタフライ演算を高速フーリエ変換に用いた場合には、高速フーリエ変換装置の回路規模が増大してしまうという問題があった。
【０００６】
まず、基数４のバタフライ演算は基数２のバタフライ演算に比べて演算が複雑であるので、その分、バタフライ演算器の回路規模が増大してしまう。
【０００７】
また、基数４のバタフライ演算を用いてサンプル数Ｎ＝２＾ｎの高速フーリエ変換を行う場合には、ｎの値によっては基数２のバタフライ演算を併せて行う必要が生じる。すなわち、ｎが偶数のときはｎ・２＾（ｎ−３）回の基数４のバタフライ演算を行えばよいが、ｎが奇数のときは（ｎ−１）・２＾（ｎ−３）回の基数４のバタフライ演算と２＾（ｎ−１）回の基数２のバタフライ演算とを行う必要がある。このような動作を実現するためには、バタフライ演算器は基数４と基数２のバタフライ演算の両方を行う機能を備える必要がある。このことは、バタフライ演算器の回路規模の増大につながり、ひいては高速フーリエ変換装置の回路規模の増大を招くことになる。
【０００８】
しかも、基数４と基数２のバタフライ演算では演算回数も演算結果データ数も異なるため、単に両方の演算機能を備えただけでは、高速フーリエ変換のための繰り返し演算において、基数４と基数２のバタフライ演算で演算結果が得られるタイミングが異なることになり、このことは、高速フーリエ変換の制御が複雑になるという問題を引き起こす。
【０００９】
前記の問題に鑑み、本発明は、基数４のバタフライ演算を行う，回路規模の小さなバタフライ演算器を提供することを目的とする。また、基数４と基数２のバタフライ演算を同じタイミングで実行可能であり、かつ、回路規模が小さなバタフライ演算器を提供することを目的とする。
【００１０】
【課題を解決するための手段】
前記の課題を解決するため、本発明は、パイプライン処理によって基数４のバタフライ演算を時分割して行い、演算部の回路規模を削減したものである。また、パイプライン処理における中間データを演算に再帰的に利用することによって、保持する必要があるバタフライ入力の個数を減らして、データバッファのレジスタを削減したものである。さらに、本発明は、１つの基数４バタフライ演算と２つの基数２バタフライ演算とを、共通の演算器を用いて、同一のタイミングで演算結果が得られるように構成したものである。
【００１１】
具体的に、請求項１の発明が講じた手段は、基数４のバタフライ演算を下記式
Ｘ０＝（ｘ０＋ｘ２）＋（ｘ１＋ｘ３）
Ｘ１＝（ｘ０−ｘ２）＋ｊ（ｘ１−ｘ３）
Ｘ２＝（ｘ０＋ｘ２）−（ｘ１＋ｘ３）
Ｘ３＝（ｘ０−ｘ２）−ｊ（ｘ１−ｘ３）
（ただし、ｘ０，ｘ１，ｘ２，ｘ３はバタフライ入力、Ｘ０，Ｘ１，Ｘ２，Ｘ３は演算結果データ）
に従ってパイプライン処理によって行うバタフライ演算器として、入力されたバタフライ入力を順に格納する第１のデータバッファと、少なくとも前記第１のデータバッファに格納されたバタフライ入力を基にして、中間データとしてｘ０＋ｘ２、ｘ１＋ｘ３、ｘ０−ｘ２、ｊ（ｘ１−ｘ３）をサイクル毎に演算する第１の演算部と、前記第１の演算部によって演算された中間データを順に格納する第２のデータバッファと、少なくとも前記第２のデータバッファに格納された中間データを基にして、演算結果データをサイクル毎に演算する第２の演算部とを備え、前記第１の演算部は、前記第２のデータバッファに格納された中間データを用いて演算を行うものものである。
【００１２】
請求項１の発明によると、第１の演算部は少なくとも第１のデータバッファに格納されたバタフライ入力を基にして、サイクル毎に中間データの演算を行い、第２の演算部は少なくとも第２のデータバッファに格納された中間データを基にして、サイクル毎に演算結果データの演算を行う。すなわち、バタフライ演算を時分割してサイクル毎に行うので、演算部の回路規模が削減される。また、第１の演算部は第２のデータバッファに格納された中間データを用いて演算を行うため、バタフライ入力に基づきすでに演算された中間データが新たな中間データの演算に再帰的に利用されることになる。このため、第１のデータバッファに保持する必要のあるバタフライ入力の個数が少なくなり、これにより、第１のデータバッファの回路規模を縮小することができる。
【００１３】
そして、請求項２の発明では、前記請求項１のバタフライ演算器において、前記第１のデータバッファはバタフライ入力をサイクル毎に順にシフトする，直列接続された２個のレジスタを備え、前記第２のデータバッファは中間データをサイクル毎に順にシフトする，直列接続された２個のレジスタを備え、前記第１の演算部は、当該バタフライ演算器に入力されたバタフライ入力および前記第２のデータバッファの第２段レジスタに格納された中間データのいずれか一方を選択出力する第１の選択回路と、前記第１のデータバッファの第２段レジスタに格納されたバタフライ入力およびこのバタフライ入力に２を乗じたもののいずれか一方を選択出力する第４の選択回路と、前記第１の選択回路の出力データに対して、前記第４の選択回路の出力データの加算または減算を行う第１の加減算器と、前記第１の加減算器の出力データおよびこの出力データに虚数ｊを乗じたもののいずれか一方を、中間データとして選択出力する第２の選択回路とを備えたものとし、前記第２の演算部は、前記第１の演算部から出力された中間データおよび前記第２のデータバッファの第２段レジスタに格納された中間データのいずれか一方を選択出力する第３の選択回路と、前記第３の選択回路の出力データに対して、前記第２のデータバッファの第１段レジスタに格納されたバタフライ入力の加算または減算を行い、加算または減算結果を演算結果データとして出力する第２の加減算器とを備えたものとする。
【００１４】
請求項２の発明は、請求項１の発明の構成において、第１の演算部に、第１のデータバッファの第２段レジスタに格納されたバタフライ入力およびこのバタフライ入力に２を乗じたもののいずれか一方を選択出力する第４の選択回路を設けるとともに、第１のデータバッファの第４段レジスタに格納されたバタフライ入力の代わりに、第２のデータバッファの第２段レジスタに格納された中間データを第１の選択回路の選択対象データとしたものである。
【００１５】
すなわち、請求項２の発明によると、バタフライ入力がｘ０，ｘ１，ｘ２，ｘ３の順に入力されたとき、第１の演算部はバタフライ入力の入力から２サイクル遅れて４サイクルにわたって演算を行う。前半の２サイクルにおいては、第１の選択回路は当該バタフライ演算器に入力されたバタフライ入力を選択し、第４の選択回路は第１のデータバッファの第２段レジスタに格納されたバタフライ入力を選択し、かつ、第１の加減算器は加算を行い、後半の２サイクルにおいては、第１の選択回路は第２のデータバッファの第２段レジスタに格納された中間データを選択し、第４の選択回路は第１のデータバッファの第２段レジスタに格納されたバタフライ入力に２を乗じたものを選択し、第１の加減算器は減算を行う。また、第２の選択回路は、第１〜第３のサイクルにおいては第１の加減算器の出力データを選択出力する一方、最終サイクルにおいては第１の加減算器の出力データに虚数ｊを乗じたものを選択出力する。このような動作によって、第１の演算部から、請求項２の発明と同様にｘ０＋ｘ２、ｘ１＋ｘ３、ｘ０−ｘ２、ｊ（ｘ１−ｘ３）の順に中間データが出力される。したがって、第１のデータバッファを構成するのに要するレジスタの個数を２に削減することができる。
【００１６】
また、請求項３の発明が講じた解決手段は、基数４のバタフライ演算を行う場合には、下記式
Ｘ０＝（ｘ０＋ｘ２）＋（ｘ１＋ｘ３）
Ｘ１＝（ｘ０−ｘ２）＋ｊ（ｘ１−ｘ３）
Ｘ２＝（ｘ０＋ｘ２）−（ｘ１＋ｘ３）
Ｘ３＝（ｘ０−ｘ２）−ｊ（ｘ１−ｘ３）
（ただし、ｘ０，ｘ１，ｘ２，ｘ３はバタフライ入力、Ｘ０，Ｘ１，Ｘ２，Ｘ３は演算結果データ）
に従ってパイプライン処理によって行うバタフライ演算器として、入力されたバタフライ入力を格納する第１のデータバッファと、少なくとも前記第１のデータバッファに格納されたバタフライ入力を基にして、中間データとしてｘ０＋ｘ２、ｘ１＋ｘ３、ｘ０−ｘ２、ｊ（ｘ１−ｘ３）をサイクル毎に演算する第１の演算部と、前記第１の演算部によって演算された中間データを格納する第２のデータバッファと、少なくとも前記第２のデータバッファに格納された中間データを基にして、演算結果データをサイクル毎に演算する第２の演算部とを備え、基数２のバタフライ演算を行う場合には、前記第１の演算部は、中間データとしてｘ０＋ｘ２、ｘ１＋ｘ３、ｘ０−ｘ２、ｘ１−ｘ３をサイクル毎に演算可能であり、前記第２の演算部は、０を加算することにより、入力した中間データと同じ値を演算結果データとして出力することにより、当該バタフライ演算器は、２つの基数２のバタフライ演算を、下記式
Ｘ０＝ｘ０＋ｘ２
Ｘ１＝ｘ１＋ｘ３
Ｘ２＝ｘ０−ｘ２
Ｘ３＝ｘ１−ｘ３
に従って実行するものである。
【００１７】
請求項３の発明によると、１つの基数４バタフライ演算および２つの基数２バタフライ演算を、ともに第１および第２の演算部を用いて行うことができ、しかも、基数４と基数２のバタフライ演算の演算タイミングおよび演算結果データの個数を合わせることができる。また、基数２のバタフライ演算では、第１の演算部はｊ（ｘ１−ｘ３）の代わりにｘ１−ｘ３を演算すればよく、第２の演算部は入力データをそのまま出力するだけでよいので、基数２のバタフライ演算を実行可能にするための第１および第２の演算部の構成の変更はごくわずかである。
【００１８】
そして、請求項４の発明では、前記請求項３のバタフライ演算器において、前記第１のデータバッファはバタフライ入力をサイクル毎に順にシフトする，直列接続された４個のレジスタを備え、前記第２のデータバッファは中間データをサイクル毎に順にシフトする，直列接続された２個のレジスタを備え、前記第１の演算部は、当該バタフライ演算器に入力されたバタフライ入力および前記第１のデータバッファの第４段レジスタに格納されたバタフライ入力のいずれか一方を選択出力する第１の選択回路と、前記第１の選択回路の出力データに対して、前記第１のデータバッファの第２段レジスタに格納されたバタフライ入力の加算または減算を行う第１の加減算器と、前記第１の加減算器の出力データおよびこの出力データに虚数ｊを乗じたもののいずれか一方を、中間データとして選択出力する第２の選択回路とを備えたものとし、前記第２の演算部は、前記第１の演算部から出力された中間データ、前記第２のデータバッファの第２段レジスタに格納された中間データ、および論理値“０”のいずれか１つを選択出力する第３の選択回路と、前記第３の選択回路の出力データに対して、前記第２のデータバッファの第１段レジスタに格納されたバタフライ入力の加算または減算を行い、加算または減算結果を演算結果データとして出力する第２の加減算器とを備えたものとする。
【００１９】
また、請求項５の発明では、前記請求項３のバタフライ演算器において、前記第１のデータバッファはバタフライ入力をサイクル毎に順にシフトする，直列接続された２個のレジスタを備え、前記第２のデータバッファは中間データをサイクル毎に順にシフトする，直列接続された２個のレジスタを備え、前記第１の演算部は、当該バタフライ演算器に入力されたバタフライ入力および前記第２のデータバッファの第２段レジスタに格納された中間データのいずれか一方を選択出力する第１の選択回路と、前記第１のデータバッファの第２段レジスタに格納されたバタフライ入力およびこのバタフライ入力に２を乗じたもののいずれか一方を選択出力する第４の選択回路と、前記第１の選択回路の出力データに対して、前記第４の選択回路の出力データの加算または減算を行う第１の加減算器と、前記第１の加減算器の出力データおよびこの出力データに虚数ｊを乗じたもののいずれか一方を、中間データとして選択出力する第２の選択回路とを備えたものとし、前記第２の演算部は、前記第１の演算部から出力された中間データ、前記第２のデータバッファの第２段レジスタに格納された中間データ、および論理値“０”のいずれか１つを選択出力する第３の選択回路と、前記第３の選択回路の出力データに対して、前記第２のデータバッファの第１段レジスタに格納されたバタフライ入力の加算または減算を行い、加算または減算結果を演算結果データとして出力する第２の加減算器とを備えたものとする。
【００２０】
請求項４および５の発明によると、基数２のバタフライ演算において、第３の選択回路に論理値“０”を選択させることによって、第２の演算部から、入力した中間データをそのまま演算結果データとして出力させることができる。また、第２の選択回路に第１の加減算器の出力データを選択させることによって、第１の演算部から、ｊ（ｘ１−ｘ３）の代わりにｘ１−ｘ３を出力させることができる。
【００２１】
【発明の実施の形態】
以下、本発明の実施形態について、図面を参照しながら説明する。
【００２２】
（第１の実施形態）
図１は本発明の第１の実施形態に係るバタフライ演算器を含むバタフライ演算装置の構成図である。図１に示すバタフライ演算装置は、図１０（ａ）に示すような回転子乗算および基数４バタフライ演算を行うものである。すなわち、図１０（ａ）に示すように、データＤ０〜Ｄ３と回転子データとの回転子乗算を行い、データｘ０〜ｘ３を算出し、データｘ０〜ｘ３をバタフライ入力として、次のような式に基づきバタフライ演算を行い、データＸ０〜Ｘ３を算出する。
Ｘ０＝（ｘ０＋ｘ２）＋（ｘ１＋ｘ３）
Ｘ１＝（ｘ０−ｘ２）＋ｊ（ｘ１−ｘ３）
Ｘ２＝（ｘ０＋ｘ２）−（ｘ１＋ｘ３）
Ｘ３＝（ｘ０−ｘ２）−ｊ（ｘ１−ｘ３）
【００２３】
図１において、１はデータｘ０〜ｘ３をバタフライ入力としてバタフライ演算を行い、演算結果データＸ０〜Ｘ３を出力するバタフライ演算器、５は入力データＤ０〜Ｄ３と回転子データＷｉとの乗算を行い、データｘ０〜ｘ３を出力する回転子乗算器、７は回転子乗算器５の出力データｘ０〜ｘ３を格納するレジスタである。バタフライ演算器１の構成要素として、１０はバタフライ入力ｘ０〜ｘ３を順に格納する第１のデータバッファ、２０はバタフライ演算器１に入力されたバタフライ入力および第１のデータバッファ１０に格納されたバタフライ入力を基にして、中間データの演算を行う第１の演算部、３０は第１の演算部２０から出力された中間データを順に格納する第２のデータバッファ、４０は第１の演算部２０から出力された中間データおよび第２のデータバッファ３０に格納された中間データを基にして、演算結果データＸ０〜Ｘ３の演算を行う第２の演算部である。
【００２４】
第１の演算部２０は構成要素として、制御信号ＳＡ０に従い加算または減算を行う第１の加減算器２１、虚数ｊ（ｊ２＝−１）を乗じる乗算器２２、および制御信号ＳＡ０、ＳＳ０によりそれぞれ制御される第１および第２の選択回路２３，２４を備えている。また、第２の演算部４０は構成要素として、制御信号ＳＡ１に従い加算または減算を行う第２の加減算器４１、および制御信号ＳＡ１により制御される第３の選択回路４２を備えている。また、１１〜１４および３１，３２はパイプライン処理におけるサイクルごとに値を更新するレジスタであり、第１のデータバッファ１０は直列に接続されたレジスタ１１〜１４からなり、第２のデータバッファ３０は直列に接続されたレジスタ３１，３２からなる。
【００２５】
図２は選択信号の値に応じた各選択回路の出力を示す図である。同図中、（ａ）は選択信号ＳＡ０の値に応じた第１の選択回路２３の出力を、（ｂ）は選択信号ＳＳ０の値に応じた第２の選択回路２４の出力を、（ｃ）は選択信号ＳＡ１の値に応じた第３の選択回路４２の出力を、それぞれ示している。第１の選択回路２３は、図２（ａ）に示すように、バタフライ演算器１に入力されたバタフライ入力および第１のデータバッファ１０のレジスタ１４に格納されたバタフライ入力のうち、選択信号ＳＡ０が“０”のときはバタフライ演算器１に入力されたバタフライ入力を、選択信号ＳＡ０が“１”のときはレジスタ１４に格納されたバタフライ入力を、選択出力する。第２の選択回路２４は、図２（ｂ）に示すように、第１の加減算器２１の出力データおよび乗算器２２の出力データ（第１の加減算器２１の出力データに虚数ｊを乗じたもの）のうち、選択信号ＳＳ０が“０”のときは第１の加減算器２１の出力データを、選択信号ＳＳ０が“１”のときは乗算器２２の出力データを、選択出力する。第３の選択回路４２は、図２（ｃ）に示すように、第２の選択回路２４の出力データ（第１の演算部２０から出力された中間データ）および第２のデータバッファ３０のレジスタ３２に格納された中間データのうち、選択信号ＳＡ１が“０”のときは第２の選択回路２４の出力データを、選択信号ＳＡ１が“１”のときはレジスタ３２に格納された中間データを、選択出力する。
【００２６】
また、第１の加減算器２１は選択信号ＳＡ０に従って動作し、選択信号ＳＡ０が“０”のときは加算を行う一方、“１”のときは減算を行う。第２の加減算器４１は選択信号ＳＡ１に従って動作し、選択信号ＳＡ１が“０”のときは加算を行う一方、“１”のときは減算を行う。
【００２７】
ここで、入力データＤ０〜Ｄ３、バタフライ入力ｘ０〜ｘ３、演算結果データＸ０〜Ｘ３、および第１の演算部２０が出力する中間データは、それぞれ複素データである。
【００２８】
図３は図１に示すバタフライ演算装置の処理タイミングを示す図である。図３に示すように、図１に示すバタフライ演算装置は、入力データＤ０〜Ｄ３をサイクルごとに入力し、入力データＤ３の入力サイクルの次のサイクルから演算結果データＸ０〜Ｘ３をサイクルごとに出力する。図１に示すバタフライ演算装置における各処理はパイプライン処理であり、演算結果データＸ０〜Ｘ３の出力と次の入力データＤ０〜Ｄ３の入力とをオーバーラップさせて処理することが可能である。図３において、レジスタ出力とあるのは、各レジスタに格納されたデータを示す。
【００２９】
入力データＤ０〜Ｄ３は、回転子乗算器５によって回転子データＷｉを乗じられ、データｘ０〜ｘ３としてレジスタ７に格納される。レジスタ７の出力データｘ０〜ｘ３は、バタフライ入力として、第１のデータバッファ１０のレジスタ１１〜１４に順に格納される。
【００３０】
第１の演算部２０による中間データの演算は、バタフライ入力ｘ０〜ｘ３の入力の開始から２サイクル遅れて開始される。第１の演算部２０は、レジスタ７の出力データ（バタフライ演算器１に入力されたバタフライ入力）並びに第１のデータバッファ１０の第２段レジスタ１２および第４段レジスタ１４の出力データを入力として、第１の加減算器２１および乗算器２２によって、中間データの演算を行う。第１の加減算器２１は、レジスタ７の出力データおよび第１のデータバッファ１０の第４段レジスタ１４の出力データのうち第１の選択回路２３によって選択されたものに対して、第１のデータバッファ１０の第２段レジスタ１２の出力データの加算または減算を行う。乗算器２２は第１の加減算器２１の出力データに虚数ｊを乗じ、第２の選択回路２４は第１の加減算器２１の出力データおよび乗算器２２の出力データのいずれか一方を選択し、中間データとして出力する。
【００３１】
第１の演算部２０による中間データの演算において、選択信号ＳＡ０は、前半の２サイクルは“０”になり、後半の２サイクルは“１”になる。したがって、前半の２サイクルでは、第１の選択回路２３はバタフライ演算器１に入力されたバタフライ入力を選択出力し、第１の加減算器２１は加算を行う一方、後半の２サイクルでは、第１の選択回路２３は第１のデータバッファ１０の第４段レジスタ１４に格納されたバタフライ入力を選択出力し、第１の加減算器２１は減算を行う。この結果、第１の加減算器２１の各サイクルの出力データは、（ｘ０＋ｘ２），（ｘ１＋ｘ３），（ｘ０−ｘ２），（ｘ１−ｘ３）となる。
【００３２】
また、選択信号ＳＳ０は、前半の３サイクルは“０”になり、最終のサイクルのみ“１”になる。したがって、第２の選択回路２４は、前半の３サイクルでは第１の加減算器２１の出力データを選択出力する一方、最終サイクルでは乗算器２２の出力データ（第１の加減算器２１の出力データに虚数ｊを乗じたもの）を選択出力する。この結果、第１の演算部２０から中間データとして、（ｘ０＋ｘ２），（ｘ１＋ｘ３），（ｘ０−ｘ２），ｊ（ｘ１−ｘ３）が順に出力される。第１の演算部２０から出力された中間データは、第２のデータバッファ３０内のレジスタ３１，３２に順に格納される。
【００３３】
第２の演算部４０による演算結果データの演算は、第１の演算部２０による中間データの演算から１サイクル遅れて、すなわちバタフライ入力ｘ０〜ｘ３の入力の開始から３サイクル遅れて開始される。第２の演算部４０は、第１の演算部２０から出力された中間データ並びに第２のデータバッファ３０の第１段レジスタ３１および第２段レジスタ３２に格納された中間データを入力として、第２の加減算器４１によって、演算結果データの演算を行う。第２の加減算器４１は、第２の選択回路２４の出力データおよび第２のデータバッファ３０の第２段レジスタ３２の出力データのうち第３の選択回路４２によって選択されたものに対して、第２のデータバッファ３０の第１段レジスタ３１の出力データの加算または減算を行う。
【００３４】
第２の演算部４０による演算結果データの演算において、選択信号ＳＡ１は、最初および３番目のサイクルは“０”になり、２番目および最終のサイクルは“１”になる。したがって、最初および３番目のサイクルでは、第３の選択回路４２は第２の選択回路２４の出力データを選択出力し、第２の加減算器４１は加算を行う一方、２番目および最終のサイクルでは、第３の選択回路４２は第２のデータバッファ３０の第２段レジスタ３２の出力データを選択出力し、第２の加減算器４１は減算を行う。この結果、第２の演算部４０から演算結果データとして、（ｘ０＋ｘ２）＋（ｘ１＋ｘ３）（＝Ｘ０），（ｘ０＋ｘ２）−（ｘ１＋ｘ３）（＝Ｘ１），（ｘ０−ｘ２）＋ｊ（ｘ１−ｘ３）（＝Ｘ２），（ｘ０−ｘ２）−ｊ（ｘ１−ｘ３）（＝Ｘ３）が出力される。
【００３５】
すなわち、入力データがＤ０，Ｄ１，Ｄ２，Ｄ３の順に入力されるのに対して、演算結果データはＸ０，Ｘ２，Ｘ１，Ｘ３の順に出力される。演算結果データの出力の順序を、データ入力の順序に合わせるべく、Ｘ０，Ｘ１，Ｘ２，Ｘ３とする場合には、演算結果データを格納するアドレスの順序を入れ換えればよい。
【００３６】
以上のような処理によって、図１に示すバタフライ演算装置は、入力データＤ０〜Ｄ３に対し、回転子乗算および基数４バタフライ演算を行い、演算結果データＸ０〜Ｘ３を算出する。
【００３７】
以上のように、本実施形態によると、バタフライ入力を格納する第１のデータバッファ１０と中間データを格納する第２のデータバッファ２０とを設け、第１の演算部２０および第２の演算部４０をパイプライン処理によって１サイクルごとに時分割して用いることによって、基数４のバタフライ演算を行うバタフライ演算器の演算部の回路規模を縮小することができる。
【００３８】
（第２の実施形態）
以下、本発明の第２の実施形態について図面を参照しながら説明する。
【００３９】
図４は本発明の第２の実施形態に係るバタフライ演算器を含むバタフライ演算装置の構成図である。図４に示すバタフライ演算装置は、第１の実施形態と同様に、図１０（ａ）に示すような回転子乗算および基数４バタフライ演算を行うものである。
【００４０】
図４において、２はバタフライ入力ｘ０〜ｘ３を基にしてバタフライ演算を行い、演算結果データＸ０〜Ｘ３を出力するバタフライ演算器である。バタフライ演算器２の構成要素として、１０Ａはバタフライ入力ｘ０〜ｘ３を順に格納する第１のデータバッファ、２０Ａはバタフライ演算器２に入力されたバタフライ入力および第１のデータバッファ１０Ａに格納されたバタフライ入力を基にして、中間データの演算を行う第１の演算部、３０は第１の演算部２０Ａから出力された中間データを順に格納する第２のデータバッファ、４０は第１の演算部２０Ａから出力された中間データおよび第２のデータバッファ３０に格納された中間データを基にして、演算結果データＸ０〜Ｘ３の演算を行う第２の演算部である。図４において、図１と同一の機能を有するものには同一の符号を付しており、本実施形態ではその詳細な説明を省略する。
【００４１】
図４に示すバタフライ演算器２が図１に示すバタフライ演算器１と異なるのは、図１に示すバタフライ演算器１の第１のデータバッファ１０が４段のレジスタから構成されていたのに対し、図４に示すバタフライ演算器２の第１のデータバッファ１０Ａは２段のレジスタから構成されている点である。
【００４２】
図４に示すバタフライ演算器２の第１の演算部２０Ａは、図１に示すバタフライ演算器１の第１の演算部２０の各構成要素以外に、入力データに２を乗じる乗算器２５および制御信号ＳＢ０により制御される第４の選択回路２６を備えている。すなわち、第１のデータバッファ１０Ａを２段のレジスタで構成するため、バタフライ演算器２に入力されたバタフライ入力および第２のデータバッファ３０の第２段レジスタ３２に格納された中間データのうち第１の選択回路２３によって選択出力されたものと、第１のデータバッファ１０Ａの第２段レジスタ１２に格納されたバタフライ入力および乗算器２５の出力データ（レジスタ１２に格納されたバタフライ入力に２を乗じたもの）のうち第４の選択回路２６によって選択されたものとを、第１の加減算器２１の入力としている。
【００４３】
図５は選択信号の値に応じた各選択回路の出力を示す図である。同図中、（ａ）は選択信号ＳＡ０の値に応じた第１の選択回路２３の出力を、（ｂ）は選択信号ＳＢ０の値に応じた第４の選択回路２６の出力を、それぞれ示している。第１の選択回路２３は、図５（ａ）に示すように、バタフライ演算器２に入力されたバタフライ入力および第２のデータバッファ３０のレジスタ３２に格納された中間データのうち、選択信号ＳＡ０が“０”のときはバタフライ演算器２に入力されたバタフライ入力を、選択信号ＳＡ０が“１”のときはレジスタ３２に格納された中間データを、選択出力する。第４の選択回路２６は、図５（ｂ）に示すように、第１のデータバッファ１０Ａの第２段レジスタ１２に格納されたバタフライ入力および乗算器２５の出力データのうち、選択信号ＳＢ０が“０”のときはレジスタ１２に格納されたバタフライ入力を、選択信号ＳＢ０が“１”のときは乗算器２５の出力データを、選択出力する。
【００４４】
図６は図４に示すバタフライ演算装置の処理タイミングを示す図である。第１の実施形態と同様に、入力データＤ０〜Ｄ３をサイクルごとに入力し、入力データＤ３の入力サイクルの次のサイクルから演算結果データＸ０〜Ｘ３をサイクルごとに出力する。各処理はパイプライン処理であり、演算結果データＸ０〜Ｘ３の出力と次の入力データＤ０〜Ｄ３の入力とをオーバーラップさせて処理することが可能である。また、第１の実施形態と同様に、第１の演算部２０Ａによる中間データの演算は、バタフライ入力ｘ０〜ｘ３の入力の開始から２サイクル遅れて開始され、第２の演算部４０による演算結果データの演算は、第１の演算部２０Ａによる中間データの演算から１サイクル遅れて、すなわちバタフライ入力ｘ０〜ｘ３の入力の開始から３サイクル遅れて開始される。
【００４５】
バタフライ入力ｘ０〜ｘ３は、第１のデータバッファ１０Ａのレジスタ１１，１２に順に格納される。第１の演算部２０Ａは、バタフライ演算器２に入力されたバタフライ入力、第１のデータバッファ１０Ａの第２段レジスタ１２に格納されたバタフライ入力および第２のデータバッファ３０の第２段レジスタ３２に格納された中間データを入力として、第１の加減算器２１および乗算器２２，２５によって、中間データの演算を行う。第１の加減算器２１は、バタフライ演算器２に入力されたバタフライ入力およびレジスタ３２に格納された中間データのうち第１の選択回路２３によって選択されたものに対し、レジスタ１２に格納されたバタフライ入力および乗算器２５の出力データのうち第４の選択回路２６によって選択されたものの加算または減算を行う。乗算器２２および第２の選択回路２４の動作は第１の実施形態と同様である。
【００４６】
第１の演算部２０Ａによる中間データの演算において、選択信号ＳＡ０は、前半の２サイクルは“０”になり、後半の２サイクルは“１”になる。したがって、前半の２サイクルでは、第１の選択回路２３はバタフライ演算器２に入力されたバタフライ入力を選択出力し、第１の加減算器２１は加算を行う一方、後半の２サイクルでは、第１の選択回路２３はレジスタ３２に格納された中間データを選択出力し、第１の加減算器２１は減算を行う。また、選択信号ＳＢ０は、前半の２サイクルは“０”になり、後半の２サイクルは“１”になる。したがって、第４の選択回路２６は、前半の２サイクルではレジスタ１２に格納されたバタフライ入力を選択出力する一方、後半の２サイクルでは乗算器２５の出力データを選択出力する。
【００４７】
この結果、第１の加減算器２１には、各サイクルにおいて、入力Ａとしてｘ２，ｘ３，（ｘ０＋ｘ２），（ｘ１＋ｘ３）が、入力Ｂとしてｘ０，ｘ１，ｘ２・２，ｘ３・２が入力される。したがって、第１の加減算器２１の出力データは（ｘ０＋ｘ２），（ｘ１＋ｘ３），（ｘ０−ｘ２），（ｘ１−ｘ３）となる。
【００４８】
第２のデータバッファ３０、第２の演算部４０の処理は、第１の実施形態と同様である。この結果、第２の演算部４０から演算結果データとして、（ｘ０＋ｘ２）＋（ｘ１＋ｘ３）（＝Ｘ０），（ｘ０＋ｘ２）−（ｘ１＋ｘ３）（＝Ｘ２），（ｘ０−ｘ２）＋ｊ（ｘ１−ｘ３）（＝Ｘ１），（ｘ０−ｘ２）−ｊ（ｘ１−ｘ３）（＝Ｘ３）が出力される。
【００４９】
ここで、第１の加減算器２１に着目すると、図３および図６に示すように、本実施形態と第１の実施形態とでは同一のデータが出力される。第１の実施形態では、第１の加減算器２１は後半の２サイクルにおける出力データ（ｘ０−ｘ２），（ｘ１−ｘ３）を、第１のデータバッファ１０の第２段および第４段レジスタ１２，１４に格納されたバタフライ入力から算出していた。このため、図１０（ａ）に示すバタフライ演算の第１段目の加減算で用いるデータの間隔の２倍に等しい段数のレジスタが、第１のデータバッファ１０には必要であった。例えば、（ｘ０−ｘ２）は０番目と２番目のデータを用いた演算であり、データ間隔は２である。また（ｘ１−ｘ３）は１番目と３番目のデータを用いた演算であり、データ間隔は２である。したがって、第１の実施形態では、第１のデータバッファ１０に４段のレジスタを必要とする。
【００５０】
一方、本実施形態では、第１の加減算器２１は後半の２サイクルにおける出力データ（ｘ０−ｘ２），（ｘ１−ｘ３）を、第１のデータバッファ１０Ａの第２段レジスタ１２に格納されたバタフライ入力および第２のデータバッファ３０の第２段レジスタ３２に格納された中間データから算出する。すなわち、すでに算出した前半の２サイクルにおける中間データ（ｘ０＋ｘ２），（ｘ１＋ｘ３）が第２のデータバッファ３０のレジスタ３１，３２に格納されることを利用し、それぞれｘ２，ｘ３に２を乗じた値を減算することによって、後半の２サイクルにおける出力データ（ｘ０−ｘ２），（ｘ１−ｘ３）を算出する。これにより、後半の２サイクルにおける中間データの演算にはバタフライ入力ｘ０，ｘ１は不要になるので、第１のデータバッファ１０Ａを２段のレジスタのみで構成することが可能になる。
【００５１】
以上のように本実施形態によれば、第１の演算部２０Ａに２を乗じる乗算器２５を設け、第２のデータバッファ３０に格納された中間データを用いて第１の演算部２０Ａで演算を行うことにより、第１のデータバッファ１０Ａのレジスタ段数を削減することができる。
【００５２】
（第３の実施形態）
以下、本発明の第３の実施形態について図面を参照しながら説明する。
【００５３】
図７は本発明の第３の実施形態に係るバタフライ演算器を含むバタフライ演算装置の構成図である。図７に示すバタフライ演算装置は、図１０（ａ）に示すような回転子乗算および基数４バタフライ演算と、図１０（ｂ）に示すような回転子乗算および基数２バタフライ演算とを行うものである。
【００５４】
基数２バタフライ演算時には２つのバタフライ演算を行う。すなわち、図１０（ｂ）に示すように、データＤ０〜Ｄ３と回転子データとの回転子乗算を行い、データｘ０〜ｘ３を算出し、データｘ０〜ｘ３をバタフライ入力として、次のような式に基づきバタフライ演算を行い、データＸ０〜Ｘ３を算出する。
＜第１の基数２バタフライ演算＞
Ｘ０＝ｘ０＋ｘ２、Ｘ２＝ｘ０−ｘ２
＜第２の基数２バタフライ演算＞
Ｘ１＝ｘ１＋ｘ３、Ｘ３＝ｘ１−ｘ３
【００５５】
図７において、３はバタフライ入力ｘ０〜ｘ３を基にして基数４または基数２のバタフライ演算を行い、演算結果データＸ０〜Ｘ３を出力するバタフライ演算器である。バタフライ演算器３の構成要素として、１０Ａはバタフライ入力ｘ０〜ｘ３を順に格納する第１のデータバッファ、２０Ａはバタフライ演算器３に入力されたバタフライ入力および第１のデータバッファ１０Ａに格納されたバタフライ入力を基にして、中間データの演算を行う第１の演算部、３０は第１の演算部２０Ａから出力された中間データを順に格納する第２のデータバッファ、４０Ａは第１の演算部２０Ａから出力された中間データおよび第２のデータバッファ３０に格納された中間データを基にして、演算結果データＸ０〜Ｘ３の演算を行う第２の演算部である。図７において、図４と同一の機能を有するものには同一の符号を付しており、本実施形態ではその詳細な説明を省略する。
【００５６】
図７に示すバタフライ演算器３が図４に示すバタフライ演算器２と異なるのは、基数２バタフライ演算を行うために、第２の演算部４０Ａが、図４に示すバタフライ演算器２の第２の演算部４０における第３の選択回路４２の代わりに、選択信号ＳＣ０に従って動作する第３の選択回路４３を備えている点である。
【００５７】
第３の選択回路４３は選択対象のデータとして論理値“０”が追加されており、図８に示すように、第２の選択回路２４の出力データ（第１の演算部２０Ａから出力された中間データ）、第２のデータバッファ３０のレジスタ３２に格納された中間データ、および論理値“０”のうち、選択信号ＳＣ０が“０”のときは第２の選択回路２４の出力データを、選択信号ＳＣ０が“１”のときはレジスタ３２に格納された中間データを、そして選択信号ＳＣ０が“２”のときは論理値“０”を選択出力する。また、第２の加減算器４１は、選択信号ＳＣ０が“０”または“２”のときは加算を行う一方、“１”のときは減算を行う。
【００５８】
バタフライ演算器３が基数４バタフライ演算を行うときは、第２の演算部４０Ａの第３の選択回路４３は論理値“０”を選択せず、第１および第２の実施形態に係る第２の演算部４０の第３の選択回路４２と同様の動作を行う。一方、基数２バタフライ演算を行うときは、第２の演算部４０Ａの第３の選択回路４３は常に論理値“０”を選択出力する。
【００５９】
図９は図７に示すバタフライ演算装置が基数２バタフライ演算を行うときの処理タイミングを示す図である。第１および第２の実施形態と同様に、入力データＤ０〜Ｄ３をサイクルごとに入力し、入力データＤ３の入力サイクルの次のサイクルから演算結果データＸ０〜Ｘ３をサイクルごとに出力する。各処理はパイプライン処理であり、演算結果データＸ０〜Ｘ３の出力と次の入力データＤ０〜Ｄ３の入力とをオーバーラップさせて処理することが可能である。また、第１および第２の実施形態と同様に、第１の演算部２０Ａによる中間データの演算は、バタフライ入力ｘ０〜ｘ３の入力の開始から２サイクル遅れて開始され、第２の演算部４０Ａによる演算結果データの演算は、第１の演算部２０Ａによる中間データの演算から１サイクル遅れて、すなわちバタフライ入力ｘ０〜ｘ３の入力の開始から３サイクル遅れて開始される。
【００６０】
第１のデータバッファ１０Ａ、第１の演算部２０Ａおよび第２のデータバッファ３０は、第２の実施形態と同様に動作する。ただし、選択信号ＳＳ０は基数２のバタフライ演算において常に“０”に設定され、これにより、第１の演算部２０Ａから中間データとして第１の加減算器２１の出力データに虚数ｊが乗じられたものが出力されることはなく、第１の演算部２０Ａは最終サイクルにおいて、中間データとして（ｘ１−ｘ３）を出力する。
【００６１】
第２の演算部４０Ａによる演算結果データの演算において、選択信号ＳＣ０は基数２のバタフライ演算において常に“２”になるので、第３の選択回路４３は論理値“０”を選択出力するとともに、第２の加減算器４１は加算を行う。これにより、第２の演算部４０Ａから、演算結果データとして、第２のデータバッファ３０の第１段レジスタ３１に格納された中間データと同じ値が出力される。すなわち、第２の演算部４０Ａから演算結果データとして、ｘ０＋ｘ２（＝Ｘ０），ｘ１＋ｘ３（＝Ｘ１），ｘ０−ｘ２（＝Ｘ２），ｘ１−ｘ３（＝Ｘ３）が出力される。
【００６２】
なお、基数４バタフライ演算を行うときは、第２の演算部４０Ａの第３の選択回路４３は第１および第２の実施形態に係る第２の演算部４０の第３の選択回路４２と同様の動作を行うので、図６と同様の処理タイミングになる。
【００６３】
図９に示すように、入力データがＤ０，Ｄ１，Ｄ２，Ｄ３の順に入力されるのに対して、演算結果データはＸ０，Ｘ１，Ｘ２，Ｘ３の順に出力される。一方、基数４バタフライ演算では、図６に示すように、演算結果データはＸ０，Ｘ２，Ｘ１，Ｘ３の順に出力される。演算結果データの出力の順序を基数４バタフライ演算と基数２バタフライ演算とで合わせる場合には、演算結果データを格納するアドレスの順序を入れ換えればよい。
【００６４】
以上のような処理によって、図７に示すバタフライ演算装置は、入力データＤ０〜Ｄ３に対し、回転子乗算および１つの基数４バタフライ演算、または回転子乗算および２つの基数２バタフライ演算を行い、演算結果データＸ０〜Ｘ３を算出する。
【００６５】
以上のように、本実施形態によれば、第２の演算部４０Ａ内の第３の選択回路４３に論理値０を選択する機能を設けることによって、１つの基数４バタフライ演算、または２つの基数２バタフライ演算をデータ出力タイミングを合わせて行うことができる。すなわち、基数４バタフライ演算および基数２バタフライ演算の両方を同一タイミングで実行可能なバタフライ演算器を簡易な構成によって実現することができ、しかもその切替は単純な制御によって行うことができる。
【００６６】
なお、第１、第２、第３の実施形態において、各レジスタは複素データを格納するレジスタであり、各演算器は複素データに対する演算器であるものとしたが、各レジスタを実数部レジスタと虚数部レジスタとに分けて従属接続し、各演算器において実数部演算および虚数部演算を時分割して行ってもよい。この場合には、第１のデータバッファ１０，１０Ａおよび第２のデータバッファ３０のレジスタ段数は前述した実施形態における段数の倍の段数となり、各演算器は前述した実施形態における回路規模の半分の回路規模となる。
【００６７】
また、第２および第３の実施形態において、第１の演算部２０Ａ内に２を乗じる乗算器２５を設けたが、この乗算器２５の代わりに入力データを上位側に１ビットシフトする１ビットシフタを設けてもよい。
【００６８】
【発明の効果】
以上のように本発明によると、基数４バタフライ演算をパイプライン処理によって行い、演算器を時分割して用いるので、演算器の回路規模が削減される。また、すでに演算された中間データを用いて新たな中間データの演算を行うので、バタフライ入力を保持する第１のデータバッファのレジスタ段数が削減される。さらに、基数４と基数２のバタフライ演算を共通の演算器で実行可能なので、演算器の回路規模の増大が抑制される。したがって、回路規模の小さなバタフライ演算器を実現することができる。
【００６９】
また、１つの基数４バタフライ演算および２つの基数２バタフライ演算の演算結果データの出力タイミングを合わせることができるので、本発明に係るバタフライ演算器を用いることによって、高速フーリエ変換装置におけるバタフライ演算の繰り返し演算の制御が容易になる。
【図面の簡単な説明】
【図１】  本発明の第１の実施形態に係るバタフライ演算器を含むバタフライ演算装置の構成図である。
【図２】  （ａ）〜（ｃ）は本発明の第１の実施形態における選択回路の動作を示す図である。
【図３】  本発明の第１の実施形態におけるバタフライ演算装置の処理タイミングを示す図である。
【図４】  本発明の第２の実施形態に係るバタフライ演算器を含むバタフライ演算装置の構成図である。
【図５】  （ａ），（ｂ）は本発明の第２の実施形態における選択回路の動作を示す図である。
【図６】  本発明の第２の実施形態におけるバタフライ演算装置の処理タイミングを示す図である。
【図７】  本発明の第３の実施形態に係るバタフライ演算器を含むバタフライ演算装置の構成図である。
【図８】  本発明の第３の実施形態における選択回路の動作を示す図である。
【図９】  本発明の第３の実施形態におけるバタフライ演算装置の処理タイミングを示す図である。
【図１０】  （ａ），（ｂ）はバタフライ演算装置が実行するバタフライ演算を示す図である。
【符号の説明】
１，２，３  バタフライ演算器
１０，１０Ａ  第１のデータバッファ
１１，１２，１３，１４  レジスタ
２０，２０Ａ  第１の演算部
２１  第１の加減算器
２３  第１の選択回路
２４  第２の選択回路
２６  第４の選択回路
３０  第２のデータバッファ
３１，３２  レジスタ
４０，４０Ａ  第２の演算部
４１  第２の加減算器
４２，４３  第３の選択回路
【図１】
0003865469.tif 000002
【図２】
0003865469.tif 000003
【図３】
0003865469.tif 000004
【図４】
0003865469.tif 000005
【図５】
0003865469.tif 000006
【図６】
0003865469.tif 000007
【図７】
0003865469.tif 000008
【図８】
0003865469.tif 000009
【図９】
0003865469.tif 000010
【図１０】
0003865469.tif 000011