ＦＦＴ演算回路

トップ :: G 物理学 :: G06 計算;計数

【発明の名称】	ＦＦＴ演算回路
【発明者】	【氏名】澁谷洋志
【要約】	【課題】回路面積の有効利用を図りつつ、サンプルデータ数が大きい場合の効率的な処理と、利用できる対象データの拡大とを両立させる。【解決手段】本発明のＦＦＴ演算回路は、基数８のバタフライ演算結果のデータを第１の信号線群から出力するたすき掛け処理部１４に、当該バタフライ演算途中の中間データを取り出す第２及び第３の信号線群が設けられている。そして、基数２のバタフライ演算結果に相当する前記中間データが第１の信号線群から出力され、基数４のバタフライ演算結果に相当する前記中間データが第２の信号線群から出力される。

【特許請求の範囲】
【請求項１】２以上のただ一つの整数をα、１からα－１までの少なくとも一つの整数をβとすると、基数（２のα乗）のバタフライ演算回路の一部を利用して基数（２のβ乗）のバタフライ演算を行う、ことを特徴とするＦＦＴ演算回路。
【請求項２】基数（２のα乗）のバタフライ演算結果のデータを第αの信号線群から出力するたすき掛け処理部に、当該バタフライ演算途中の中間データを取り出す第βの信号線群が設けられ、基数（２のβ乗）のバタフライ演算結果に相当する前記中間データが前記第βの信号線群から出力される、請求項１記載のＦＦＴ演算回路。
【請求項３】前記αが３であり、前記βが１及び２である、請求項１記載のＦＦＴ演算回路。
【請求項４】前記αが３であり、前記βが１及び２である、請求項２記載のＦＦＴ演算回路。
【請求項５】前記たすき掛け処理部は、入力データの加減算を行う第１の加減算器群と、この第１の加減算器群の出力データについて加減算を行う第２の加減算器群と、この第２の加減算器群の出力データについて加減算を行う第３の加減算器群と、この第３の加減算器群の出力データの一部について乗算を行う乗算器群と、この乗算器群の出力データと前記加減算器群の出力データの一部とについて加減算を行う第４の加減算器群と、前記第１の加減算器群の出力データを取り出す前記第１の信号線群と、前記第２の加減算器群の出力データを取り出す前記第２の信号線群と、前記第３及び前記第４の加減算器群の出力データを取り出す前記第３の信号線群とを備えた、請求項４記載のＦＦＴ演算回路。
【請求項６】前記第１及び前記第２の加減算器群がそれぞれ８個の２入力１出力加算器及び８個の２入力１出力減算器からなり、前記第３の加減算器群が６個の２入力１出力加算器及び６個の２入力１出力減算器からなり、前記第４の加減算器群が４個の２入力１出力加算器及び４個の２入力１出力減算器からなる、請求項５記載のＦＦＴ演算回路。

【発明の詳細な説明】【０００１】
【発明の属する技術分野】本発明は、ディジタル信号処理に用いられるＦＦＴ（Fast Fourier Transform：高速フーリエ変換）演算回路に関する。なお、本明細書中において、例えば「2*8^n」とは、「２×（８のｎ乗）」を意味するものとする。
【０００２】
【従来の技術】ＦＦＴは、時間領域における一連のサンプルデータに潜む周波数成分を抽出するのに用いられる手法であり、多数のデータを短時間で処理できるという優れた特徴を有する。また、ＦＦＴをハードウェアにする際には、面積の小さい回路が必要とされる。
【０００３】同じデータ数の対象についてＦＦＴの演算を行う場合、バタフライ演算の基数の値が大きいほど高速に処理できる。ＦＦＴの対象となるデータの数をＮとすると、ＦＦＴの演算を終了するまでのバタフライ演算の回数は、基数２で(N/2)log2N、基数４で(N/4)log4N、基数８で(N/8)log8Nとなる。また、1バタフライあたりの乗算回数は、基数２で４、基数４で１２、基数８で３２となる。したがって、乗算回数は基数２で4*(N/2)log2N、基数４で12*(N/4)log4N、基数８で32*(N/8)log8Nとなり、単純計算でも基数２、基数４の乗算回数はそれぞれ基数８の乗算回数の1.5倍、1.125倍となる。
【０００４】一方、ＦＦＴで対象となるデータ数は、基数のべき乗個である。よって、基数２のバタフライ演算では256、512、1024、2048、4096…というデータ数を扱える。一方、基数８のバタフライ演算では、８のべき乗個すなわち512、4096…というデータ数しか扱えないので、利用できる対象が限定されてしまうという課題があった。
【０００５】
【発明が解決しようとする課題】この課題は基数４のバタフライ演算についても同様であるため、基数４のＦＦＴは対象データが４のべき乗に限定されてしまう。特開平10-307811号公報では、基数４のバタフライ演算回路において基数２のバタフライ演算を処理する回路を内蔵させることによって、この課題を解決している。しかし、データ数が大きい場合においても基数４のバタフライ演算に限定されてしまうので、演算効率は基数８のバタフライ演算に比べて低いものとなってしまう。
【０００６】また、基数の大きいバタフライ演算に基数の小さいバタフライ演算をつなげる手法が考えられる。例えば、基数８のバタフライ演算に基数２のバタフライ演算をつなげることによって、データ数2*8^nを処理するというものである。しかし、基数８のバタフライ演算をＮ段行ったのちに１段だけ基数２のバタフライ演算を行うことにより、基数８のバタフライ演算が処理されている間、基数２のバタフライ演算回路が活用されないので、回路面積を有効に利用できない。
【０００７】
【発明の目的】以上のように、基数８のバタフライ演算は、サンプルデータ数が大きい場合に効率的な処理を実現する一方、利用できるサンプルデータ数が限定されてしまうという課題があった。そこで、本発明の目的は、回路面積の有効利用を図りつつ、サンプルデータ数が大きい場合の効率的な処理と、利用できるサンプルデータ数の拡大とを両立可能とした、ＦＦＴ演算回路を提供することにある。
【０００８】
【課題を解決するための手段】本発明に係るＦＦＴ演算回路は、２以上のただ一つの整数をα、１からα－１までの少なくとも一つの整数をβとすると、基数２のα乗のバタフライ演算回路の一部を利用して基数２のβ乗のバタフライ演算を行うことを特徴とするものである（請求項１）。より具体的に言えば、基数２のα乗のバタフライ演算結果のデータを第αの信号線群から出力するたすき掛け処理部に、当該バタフライ演算途中の中間データを取り出す第βの信号線群が設けられ、基数２のβ乗のバタフライ演算結果に相当する前記中間データが前記第βの信号線群から出力される、ものである（請求項２）。
【０００９】例えば、前記αが３であり、前記βが１及び２である（請求項３、４）。このとき、前記たすき掛け処理部は、入力データの加減算を行う第１の加減算器群と、この第１の加減算器群の出力データについて加減算を行う第２の加減算器群と、この第２の加減算器群の出力データについて加減算を行う第３の加減算器群と、この第３の加減算器群の出力データの一部について乗算を行う乗算器群と、この乗算器群の出力データと前記加減算器群の出力データの一部とについて加減算を行う第４の加減算器群と、前記第１の加減算器群の出力データを取り出す前記第１の信号線群と、前記第２の加減算器群の出力データを取り出す前記第２の信号線群と、前記第３及び前記第４の加減算器群の出力データを取り出す前記第３の信号線群とを備えた、ものとしてもよい（請求項５）。
【００１０】更にこのとき、前記第１及び前記第２の加減算器群がそれぞれ８個の２入力１出力加算器及び８個の２入力１出力減算器からなり、前記第３の加減算器群が６個の２入力１出力加算器及び６個の２入力１出力減算器からなり、前記第４の加減算器群が４個の２入力１出力加算器及び４個の２入力１出力減算器からなる、としてもよい（請求項６）。
【００１１】以下、一例としてαが３であり、βが１及び２である場合について説明する。基数８のバタフライ演算は、サンプルデータ数が大きい場合に効率的な処理を実現する一方、利用できるサンプルデータ数が限定されてしまうという課題があった。本発明は、基数８のバタフライ演算回路において基数２及び基数４のバタフライ演算を処理することによって、この課題を解決しようとするものである。本発明に係るＦＦＴ演算回路では、演算データ数が8^n(=2^(3n))、2*8^n(=2^(3n+1))、4*8^n(=2^(3n+2))を対象とすることができるため、基数２のバタフライ演算回路で扱いうる対象をすべてカバーすることができる。また、基数８のバタフライ演算回路を利用して基数２及び基数４のバタフライ演算を行うため、回路面積を有効に利用できる。
【００１２】
【発明の実施の形態】図１は、本発明に係るＦＦＴ演算回路の一実施形態を示すブロック図である。図２は、図１のＦＦＴ演算回路における、たすき掛け処理部の内部構成、及びたすき掛け処理部とセレクタとの接続関係を示すブロック図である。以下、これらの図面に基づき説明する。
【００１３】本実施形態のＦＦＴ演算回路は、基数８のバタフライ演算回路の一部を用いて、基数２及び基数４のバタフライ演算をも行うものであり、データ格納部１１、ひねり係数格納部１２、ひねり係数乗算部１３、たすき掛け処理部１４、セレクタ１５、制御部１６等を備えている。本実施形態の特徴は、バタフライ演算の核をなすたすき掛け処理部１４、セレクタ１５及び制御部１６にある。
【００１４】たすき掛け処理部１４の信号線群sig3から基数８のバタフライ演算結果データを出力する。これに加え、信号線群sig1、信号線群sig2を設定し、これらから中間データを取り出すことによって、信号線群sig1から基数２のバタフライ演算の処理結果に相当するデータ、信号線群sig2から基数４のバタフライ演算の処理結果に相当するデータが得られる。したがって、基数８のバタフライ演算回路において基数２及び基数４のバタフライ演算をも行うため、回路規模を増やすことなく、2*8^n個や4*8^n個のデータに対しても処理することが可能である。
【００１５】データ格納部１１には、ＦＦＴ演算を開始する前に初期データを格納する。ＦＦＴ処理中には中間データが格納され、ＦＦＴ演算終了時には処理結果データが格納される。ひねり係数格納部１２にはひねり係数が格納される。ＦＦＴの対象となるデータの数がＮであるとき、格納されるひねり係数はｋを0、1、2、…、N-1とするとsin(2πk/N)、cos(2πk/N)である。ひねり係数乗算部１３は、データ格納部１１から出力されるデータとひねり係数格納部１２から出力されるひねり係数との乗算を行う。たすき掛け処理部１４は、ひねり係数格納部１２から出力されるデータに対してたすき掛け処理を行い、信号線群sig1からは基数２のバタフライ演算の処理結果に相当するデータ、信号線群sig2からは基数４のバタフライ演算の処理結果に相当するデータ、信号線群sig3からは基数８のバタフライ演算処理結果データを出力する。セレクタ１５は、制御部１６からの制御信号に基づいて、たすき掛け処理部１４の信号線群sig1、sig2、sig3から出力されるデータを選択し、データ格納部１１に出力する。
【００１６】たすき掛け処理部１４は、入力データの加減算を行う加減算器群as1、加減算器群as1の出力データについて加減算を行う加減算器群as2、加減算器群as2の出力データについて加減算を行う加減算器群as3、加減算器群as3の出力データの一部について乗算を行う乗算器群mul1、乗算器群mul1の出力データと加減算器群as3の出力データの一部とについて加減算を行う加減算器群as4、加減算器群as1の出力データを取り出す信号線群sig1、加減算器群as2の出力データを取り出す信号線群sig2、加減算器群as3、as4の出力データを取り出す信号線群sig3等を備えている。
【００１７】加減算器群as1、as2はそれぞれ８個の２入力１出力加算器及び８個の２入力１出力減算器からなり、加減算器群as3は６個の２入力１出力加算器及び６個の２入力１出力減算器からなり、加減算器群as4は４個の２入力１出力加算器及び４個の２入力１出力減算器からなる。セレクタ１５は、たすき掛け処理部１４の信号線群sig1、sig2、sig3のいずれかを、制御部１６からの制御信号に従って選択し、それぞれのデータを出力する。
【００１８】次に、本実施形態のＦＦＴ演算回路の動作について詳しく説明する。まず、基数８のバタフライ演算を説明した上で、基数２及び基数４のバタフライ演算を説明する。その上で、基数８のバタフライ演算における基数２のバタフライ演算及び基数４のバタフライ演算の実現方法について述べる。
【００１９】基数８のバタフライ演算では８点の離散フーリエ変換を行う。８点のバタフライ演算は式(1)のように表わされる。
Xn=Σ⁷_k=0 x_k*W^(n*k)----(1)n=0,1,2,…,7ただし、Ｗは式(2)で表される回転子である。ｊは以下虚数単位とする。
W=exp(-2πj/8)----(2)【００２０】式(1)を展開すると式(3)から式(10)のように表される。
X0=x0+x1+x2+x3+x4+x5+x6+x7----(3) X1=x0+t(1-j)*x1-j*x2+t(-1-j)*x3-x4-t(1-j)*x5+j*x6-t(-1-j)*x7----(4) X2=x0-j*x1-x2+j*x3+x4-j*x5-x6+j*x7----(5) X3=x0+t(-1-j)*x1+j*x2+t(1-j)*x3-x4-t(-1-j)*x5-j*x6-t(1-j)*x7----(6) X4=x0-x1+x2-x3+x4-x5+x6-x7----(7) X5=x0+t(-1+j)*x1-j*x2+t(1+j)*x3-x4+t(-1+j)*x5+j*x6-t(1+j)*x7----(8) X6=x0+j*x1-x2-j*x3+x4+j*x5-x6-j*x7----(9) X7=x0+t(1+j)*x1+j*x2+t(-1+j)*x3-x4-t(1+j)*x5-j*x6-t(-1+j)*x7----(10)ただし、tは定数1/√2である。
【００２１】ここで扱われるデータは複素データである。そこで、バタフライ演算入力データxiの実数部をai、虚数部をbi、出力データXiの実数部をAi、虚数部をBiとし、式(2)から式(9)を整理すると、式(11)から式(26)のように表される。また、式(11)から式(26)のようにa0、a1、…、a7、b0、b1、…、b7からA0、A1、…、A7、B0、B1、…、B7を算出する過程を図示したのが図３である。
A0=a0+a4+(a1+a5)+(a2+a6)+(a3+a7)----(11) A2=a0+a4+(b1+b5)-(a2+a6)-(b3+b7)----(12) A4=a0+a4-(a1+a5)+(a2+a6)-(a3+a7)----(13) A6=a0+a4-(b1+b5)-(a2+a6)+(b3+b7)----(14) A1=a0-a4+t(a1-a5)+t(b1-b5)+(b2-b6)-t(a3-a7)+t(b3-b7)----(15) A3=a0-a4-t(a1-a5)+t(b1-b5)-(b2-b6)+t(a3-a7)+t(b3-b7)----(16) A5=a0-a4-t(a1-a5)-t(b1-b5)+(b2-b6)+t(a3-a7)-t(b3-b7)----(17) A7=a0-a4+t(a1-a5)-t(b1-b5)-(b2-b6)-t(a3-a7)-t(b3-b7)----(18) B0=b0+b4+(b1+b5)+(b2+b6)+(b3+b7)----(19) B2=b0+b4-(a1+a5)-(b2+b6)+(a3+a7)----(20) B4=b0+b4-(b1+b5)+(b2+b6)-(b3+b7)----(21) B6=b0+b4+(a1+a5)-(b2+b6)-(a3+a7)----(22) B1=b0-b4+t(b1-b5)-t(a1-a5)-(a2-a6)-t(b3-b7)-t(a3-a7)----(23) B3=b0-b4-t(b1-b5)-t(a1-a5)+(a2-a6)+t(b3-b7)-t(a3-a7)----(24) B5=b0-b4-t(b1-b5)+t(a1-a5)-(a2-a6)+t(b3-b7)+t(a3-a7)----(25) B7=b0-b4+t(b1-b5)+t(a1-a5)+(a2-a6)-t(b3-b7)+t(a3-a7)----(26)【００２２】ここで、式(27)から式(42)のように変数ap0、am0、ap1、am1、ap3、am2、ap3、am3、bp0、bm0、bp1、bm1、bp2、bm2、bp3、bm3を設定する。これは図３における加減算器群as1の出力に相当する。
ap0=a0+a4----(27)am0=a0-a4----(28)ap1=a1+a5----(29)am1=a1-a5----(30)ap2=a2+a6----(31)am2=a2-a6----(32)ap3=a3+a7----(33)am3=a3-a7----(34)bp0=b0+b4----(35)bm0=b0-b4----(36)bp1=b1+b5----(37)bm1=b1-b5----(38)bp2=b2+b6----(39)bm2=b2-b6----(40)bp3=b3+b7----(41)bm3=b3-b7----(42)【００２３】更に、式(43)から式(58)のように変数aap0、apm0、app1、apm1、amp0、amm0、amp1、amm1、bpp0、bpm0、bpp1、bpm1、bmp0、bmm0、bmp1、bmm1を設定する。これは図３における加減算器群as2の出力に相当する。
app0=ap0+ap2----(43)apm0=ap0-ap2----(44)app1=ap1+ap3----(45)apm1=ap1-ap3----(46)amp0=am0+bm2----(47)amm0=am0-bm2----(48)amp1=am1+bm3----(49)amm1=am1-bm3----(50)bpp0=bp0+bp2----(51)bpm0=bp0-bp2----(52)bpp1=bp1+bp3----(53)bpm1=bp1-bp3----(54)bmp0=bm0+am2----(55)bmm0=bm0-am2----(56)bmp1=bm1+am3----(57)bmm1=bm1-am3----(58)【００２４】これらを用いて式(11)から式(26)を表わすと式(59)から式(74)のようになる。これは図３における加減算群as3、加減算器群as4及び乗算器群mul1の操作に相当する。
A0=app0+app1----(59)A4=app0-app1----(60)A2=apm0+bpm1----(61)A6=apm0-bpm1----(62)A1=amp0+t*(amp1+bmm1)----(63)A5=amp0-t*(amp1+bmm1)----(64)A3=amm0-t*(amm1-bmp1)----(65)A7=amm0+t*(amm1-bmp1)----(66)B0=bpp0+bpp1----(67)B4=bpp0-bpp1----(68)B2=bpm0-apm1----(69)B6=bpm0+apm1----(70)B1=bmm0-t*(amp1-bmm1)----(71)B5=bmm0+t*(amp1-bmm1)----(73)B3=bmp0-t*(amm1+bmp1)----(72)B7=bmp0+t*(amm1+bmp1)----(74)【００２５】次に、基数２のバタフライ演算について説明し、先に述べた基数８のバタフライ演算内における基数２のバタフライ演算の実現方法を述べる。
【００２６】基数２のバタフライ演算は式(75)で表わされる。
Xn=Σ¹_k=0 x_k*W^(n*k)----(75)n=0,1ここで、Ｗは式(76)で表わされるものである。
W=exp(-2πj/2)----(76)【００２７】よって、基数２のバタフライ演算を基数８のバタフライ演算における式(11)から式(26)のように表現すると、式(77)から式(80)のようになる。
A0=a0+a1----(77)A1=a0-a1----(78)B0=b0+b1----(79)B1=b0-b1----(80)【００２８】この式(77)、(78)、(79)、(80)の４項組は、式(27)、(28)、(35)、(36)の４項組、式(29)、(30)、(37)、(38)の４項組、式(31)、(32)、(39)、(40)の４項組、式(33)、(34)、(41)、(42)の４項組と対応がとれる。よって、基数２のバタフライ演算を行う２データ４入力を(a0、a4、b0、b4)又は(a2、a6、b2、b6)、(a1、a5、b1、b5)、(a3、a7、b3、b7)に対応させ、その加減算結果である(ap0、am0、bp0、bm0)又は(ap2、am2、bp2、bm2)、(ap1、am1、bp1、bm1)、(ap3、am3、bp3、bm3)を得ることによって、基数２のバタフライ演算結果を出力することができる。
【００２９】すなわち、図３に示すように基数８のバタフライ演算において、a0、a1、…、a7、b0、b1、…、b7に上述の組み合わせを鑑みた入力を行い、加減算器群as1の結果を信号線群sig1に取り出すことによって、基数２のバタフライ演算を４組並列に処理した結果を出力することができる。
【００３０】続いて、基数４のバタフライ演算について説明し、先に述べた基数８のバタフライ演算内における基数４のバタフライ演算の実現方法を述べる。
【００３１】基数４のバタフライ演算は式(81)で表わされる。
Xn=Σ³_k=0 x_k*W^(n*k)----(81)n=0,1,2,3ここで、Ｗは式(82)で表わされるものである。
W=exp(-2πj/4)----(82)【００３２】よって、基数４のバタフライ演算を基数８のバタフライ演算における式(11)から式(26)のように表現すると、式(83)から式(90)のようになる。
A0=a0+a2+(a1+a3)----(83)A2=a0+a2-(a1+a3)----(84)A1=a0-a2+(b1-b3)----(85)A3=a0-a2-(b1-b3)----(86)B0=b0+b2+(b1+b3)----(87)B2=b0+b2-(b1+b3)----(88)B1=b0-b2-(a1-a3)----(89)B3=b0-b2+(a1-a3)----(90)【００３３】この式(83)、(84)、(85)、(86)、(87)、(88)、(89)、(90)の８項組は式(43)、(44)、(47)、(48)、(51)、(52)、(56)、(55)の８項組、式(45)、(46)、(49)、(50)、(53)、(54)、(58)、(57)の８項組と対応がとれる。よって、基数４のバタフライ演算を行う４データ８入力を(a0、a4、a2、a6、b0、b4、b2、b6)又は(a1、a5、a3、a7、b1、b5、b3、b7)に対応させ、その加減算結果である(app0、apm0、amp0、amm0、bpp0、bpm0、bmm0、bmp0)又は(app1、apm1、amp1、amm1、bpp1、bpm1、bmm1、bmp1)を得ることによって、基数４のバタフライ演算結果を出力することができる。
【００３４】すなわち、図３に示すように基数８のバタフライ演算において、a0、a1、…、a7、b0、b1、…、b7に上述の組み合わせを鑑みた入力を行い、加減算器群as2の結果を信号線群sig2に取り出すことによって、基数４のバタフライ演算を２組並列に処理した結果を出力することができる。
【００３５】ここで、例としてデータ数2*8^nの対象について、ＦＦＴを行う際の処理について説明する。ただし、各格納部はメモリで実現したとする。
【００３６】制御部１６は、データ格納部１１に対して、基数８のバタフライ演算のアルゴリズムに則ったアドレスのデータを出力するように制御信号を送る。ひねり係数格納部１２に対しては、基数８のバタフライ演算のアルゴリズムに則ったひねり係数を出力するよう制御信号を送る。また、ひねり係数乗算部１３に対しては、データ格納部１１から出力されるデータとひねり係数格納部１２から出力されるひねり係数との乗算を、基数８のバタフライ演算のアルゴリズムに則って行うよう制御信号を送る。乗算されたデータはたすき掛け処理部１４に送られ、そこでたすき掛け処理が行われる。続いて、制御部１６は、セレクタ１５に対して、基数８のバタフライ演算結果を選択するように制御信号を送る。セレクタ１５は、たすき掛け処理部１４の信号線群の中から基数８のバタフライ演算結果である信号線群sig3を選択し、それらのデータをデータ格納部１１へ出力する。このループをｎ回実行する。
【００３７】その上で、制御部１６は、データ格納部に対して、基数２のバタフライ演算のアルゴリズムに則ったアドレスのデータを出力するように制御信号を送る。ひねり係数格納部１２に対しては、基数２のバタフライ演算のアルゴリズムに則ったひねり係数を出力するよう制御信号を送る。また、ひねり係数乗算部１３に対しては、データ格納部１１から出力されるデータとひねり係数格納部１２から出力されるひねり係数との乗算を、基数２のバタフライ演算のアルゴリズムに則って行うよう制御信号を送る。乗算されたデータはたすき掛け処理部１４に送られ、そこでたすき掛け処理が行われる。続いて、制御部１６は、セレクタ１５に対して、基数２のバタフライ演算結果を選択するように制御信号を送る。セレクタ１は、たすき掛け処理部１４の信号線群の中から基数２のバタフライ演算結果である信号線群sig1を選択し、それらのデータをデータ格納部１１へ出力する。このループを１回実行する。
【００３８】以上の処理の結果、データ格納部１１には2*8^nのＦＦＴ演算の結果が格納される。
【００３９】なお、本発明は、上記実施形態を発展させて、例えば「基数１６のバタフライ演算回路の一部を利用して基数２、４、８のバタフライ演算を行う」というように、上記実施形態における基数８の部分を１６、３２、・・・とすることができる。一例として、基数１６の場合について説明する。
【００４０】基数１６のバタフライ演算がX_n=Σ¹⁵_k=0 x_k*W^(n*k) n=0,…,15 ----(91)ただし、W=exp(-2πj/16) ：jは虚数単位を基本の形として動作するのは、基数２、４、８の場合と同様である。
【００４１】式(91)を展開すると、n=2m の場合 X_n={(x_0+x_8)+(x_4+x_12)*w4^n}+{(x_1+x_9)+(x_5+x_13)*w4^n}*W^n+{(x_2+x_10)+(x_6+x_14)*w4^n}*W^(2*n)+{(x_3+x_11)+(x_7+x_15)*w4^n}*W^(3*n)----(92)n=2m+1 の場合 X_n={(x_0-x_8)+(x_4-x_12)*w4^n}+{(x_1-x_9)+(x_5-x_13)*w4^n}*W^n+{(x_2-x_10)+(x_6-x_14)*w4^n}*W^(2*n)+{(x_3-x_11)+(x_7-x_15)*w4^n}*W^(3*n)----(93)となる。ただし、w4=exp(2πj/4)。
【００４２】(92)式はX_n={(x_0+x_8)+(x_2+x_10)*w8^n+(x_4+x_12)*w8^(2*n)+(x_6+x_14)*w8^(3*n)}+{(x_1+x_9)+(x_3+x_11)*w8^n+(x_5+x_13)*w8^(2*n)+(x_7+x_15)*w8^(3*n)}*W^n----(94)(93)式は X_n={(x_0-x_8)+(x_2-x_10)*w8^n+(x_4-x_12)*w8^(2*n)+(x_6-x_14)*w8^(3*n)}+{(x_1-x_9)+(x_3-x_11)*w8^n+(x_5-x_13)*w8^(2*n)+(x_7-x_15)*w8^(3*n)}*W^n----(95)と変形できる。ただし、w8=exp(2πj/8)。
【００４３】(92)、(93)式の括弧{}内が基数４のバタフライ演算に相当し、(94)、(95)式の括弧{}内が基数８のバタフライ演算に相当する。基数２についても同様に示すことができる。これは、更に基数の値が大きくなっても言えることである。
【００４４】
【発明の効果】本発明に係るＦＦＴ演算回路によれば、２以上のただ一つの整数をα、１からα－１までの少なくとも一つの整数をβとすると、基数（２のα乗）のバタフライ演算回路の一部を利用して基数（２のβ乗）のバタフライ演算を行うことにより、データ数が（２のα乗）^nだけでなく2*（２のα乗）^n、…についても、回路規模を増大することなくＦＦＴを行える。その理由は、基数（２のα乗）のバタフライ演算回路の一部をそのまま用いて基数（２のβ乗）のバタフライ演算を行うことにより、2*（２のα乗）^n、…というデータ数を扱う基数（２のβ乗）のバタフライ演算回路が不要になるためである。したがって、回路面積の有効利用を図りつつ、サンプルデータ数が大きい場合の効率的な処理と、利用できるサンプルデータ数の拡大とを両立させることができる。
【００４５】特に請求項３又は４記載のＦＦＴ演算回路によれば、データ数が8^nだけでなく2*8^nや4*8^nについても、回路規模を増大することなくＦＦＴを行える。その理由は、基数８のバタフライ演算回路の一部をそのまま用いて基数２のバタフライ演算及び基数４のバタフライ演算を行えることにより、2*8^nや4*8^nというデータ数を扱う基数２や基数４のバタフライ演算回路が不要になるためである。

【出願人】	【識別番号】０００００４２３７【氏名又は名称】日本電気株式会社
【出願日】	平成１２年１０月３０日（２０００．１０．３０）
【代理人】	【識別番号】１０００７９１６４【弁理士】【氏名又は名称】高橋勇
【公開番号】	特開２００２－１３２７４７（Ｐ２００２－１３２７４７Ａ）
【公開日】	平成１４年５月１０日（２００２．５．１０）
【出願番号】	特願２０００－３３０５２４（Ｐ２０００－３３０５２４）