fft倒序演算法

1. 16點DFT的FFT演算法

FFT（快速傅里葉變換）是DFT的一種特殊情況，就是當運算點的個數是2的整數次冪的時候進行的運算（不夠用0補齊）。

FFT計算原理及流程圖：

原理：FFT的計算要求點數必須為2的整數次冪，如果點數不夠用0補齊。例如計算{2，3，5，8，4}的16點FFT，需要補11個0後進行計算。FFT計算運用蝶形運算，在蝶形運算中變化規律由W(N, p)推導，其中N為FFT計算點數，J為下角標的值。

L = 1時，W(N, p) = W(N, J) = W(2^L, J)，其中J = 0;

L = 2時，W(N, p) = W(N, J) = W(2^L, J)，其中J = 0, 1;

L = 3時，W(N, p) = W(N, J) = W(2^L, J)，其中J = 0, 1, 2, 3;

所以，W(N, p) = W(2^L, J)，其中J = 0, 1, ..., 2^(L-1)-1

又因為2^L = 2^M*2^(L-M) = N*2^(L-M)，這里N為2的整數次冪，即N=2^M，

W(N, p) = W(2^L, J) = W(N*2^(L-M), J) = W(N, J*2^(M-L))

所以，p = J*2^(M-L)，此處J = 0, 1, ..., 2^(L-1)-1，當J遍歷結束但計算點數不夠N時，J=J+2^L，後繼續遍歷，直到計算點數為N時不再循環。

流程圖：

/*======================================================================
*方法名：fft
*方法功能：計算數組的FFT，運用蝶形運算
*
*變數名稱：
*yVector-原始數據
*length-原始數據長度
*N-FFT計算點數
*fftYreal-FFT後的實部
*fftYImg-FFT後的虛部
*
*返回值：是否成功的標志，若成功返回true，否則返回false
*=====================================================================*/

+(BOOL)fft:(floatfloat*)yVectorandOriginalLength:(NSInteger)lengthandFFTCount:(NSInteger)NandFFTReal:(floatfloat*)fftYRealandFFTYImg:(floatfloat*)fftYImg
{
//確保計算時時2的整數冪點數計算
NSIntegerN1=[selfnextNumOfPow2:N];

//定義FFT運算是否成功的標志
BOOLisFFTOK=false;

//判斷計算點數是否為2的整數次冪
if(N!=N1)
{
//不是2的整數次冪，直接計算DFT
isFFTOK=[selfdft:yVectorandOriginalLength:lengthandFFTCount:NandFFTReal:fftYRealandFFTYImg:fftYImg];

//返回成功標志
returnisFFTOK;
}


//如果計算點數位2的整數次冪，用FFT計算，如下
//定義變數
floatyVectorN[N1];//N點運算的原始數據
NSIntegerpowOfN=log2(N1);//N=2^powOfN，用於標記最大運算級數(公式中表示為：M)
NSIntegerlevel=1;//運算級數（第幾次運算），最大為powOfN，初值為第一級運算(公式中表示為：L)
NSIntegerlineNum;//行號，倒序排列後的蝶形運算行號(公式中表示為：k)
floatinverseOrderY[N1];//yVector倒序x
NSIntegerdistanceLine=1;//行間距，第level級運算每個蝶形的兩個節點距離為distanceLine=2^(L-1)(公式中表示為：B)
NSIntegerp;//旋轉因子的階數，旋轉因子表示為W(N,p)，p=J*2^(M-L)
NSIntegerJ;//旋轉因子的階數，旋轉因子表示為W(2^L,J)，J=0,1,2,...,2^(L-1)-1=distanceLine-1
floatrealTemp,imgTemp,twiddleReal,twiddleImg,twiddleTheta,twiddleTemp=PI_x_2/N1;
NSIntegerN_4=N1/4;

//判斷點數是否夠FFT運算點數
if(length<=N1)
{
//如果N至少為length，先把yVector全部賦值
for(NSIntegeri=0;i<length;i++)
{
yVectorN[i]=yVector[i];
}

if(length<N1)
{
//如果N>length後面補零
for(NSIntegeri=length;i<N1;i++)
{
yVectorN[i]=0.0;
}
}
}
else
{
//如果N<length截取相應長度的數據進行運算
for(NSIntegeri=0;i<N1;i++)
{
yVectorN[i]=yVector[i];
}
}

//調用倒序方法
[selfinverseOrder:yVectorNandN:N1andInverseOrderVector:inverseOrderY];

//初始值
for(NSIntegeri=0;i<N1;i++)
{
fftYReal[i]=inverseOrderY[i];
fftYImg[i]=0.0;
}

//三層循環
//第三層（最里）：完成相同旋轉因子的蝶形運算
//第二層（中間）：完成旋轉因子的變化，步進為2^level
//第一層（最外）：完成M次迭代過程，即計算出x(k)=A0(k),A1(k),...,Am(k)=X(k)

//第一層循環
while(level<=powOfN)
{
distanceLine=powf(2,level-1);//初始條件distanceLine=2^(level-1)
J=0;
NSIntegerpow2_Level=distanceLine*2;//2^level
NSIntegerpow2_NSubL=N1/pow2_Level;//2^(M-L)

//第二層循環
while(J<distanceLine)
{
p=J*pow2_NSubL;
lineNum=J;
NSIntegerstepCount=0;//J運算的步進計數

//求旋轉因子
if(p==0)
{
twiddleReal=1.0;
twiddleImg=0.0;
}
elseif(p==N_4)
{
twiddleReal=0.0;
twiddleImg=-1.0;
}
else
{
//計算尤拉公式中的θ
twiddleTheta=twiddleTemp*p;

//計算復數的實部與虛部
twiddleReal=cos(twiddleTheta);
twiddleImg=-11*sin(twiddleTheta);
}

//第三層循環
while(lineNum<N1)
{
//計算下角標
NSIntegerfootNum=lineNum+distanceLine;

/*---------------------------------------
*用復數運算計算每級中各行的蝶形運算結果
*X(k)=X(k)+X(k+B)*W(N,p)
*X(k+B)=X(k)-X(k+B)*W(N,p)
*---------------------------------------*/
realTemp=fftYReal[footNum]*twiddleReal-fftYImg[footNum]*twiddleImg;
imgTemp=fftYReal[footNum]*twiddleImg+fftYImg[footNum]*twiddleReal;

//將計算後的實部和虛部分別存放在返回數組中
fftYReal[footNum]=fftYReal[lineNum]-realTemp;
fftYImg[footNum]=fftYImg[lineNum]-imgTemp;
fftYReal[lineNum]=fftYReal[lineNum]+realTemp;
fftYImg[lineNum]=fftYImg[lineNum]+imgTemp;

stepCount+=pow2_Level;

//行號改變
lineNum=J+stepCount;
}

//旋轉因子的階數變換，達到旋轉因子改變的效果
J++;
}

//運算級數加一
level++;
}

isFFTOK=true;
returnisFFTOK;
}

2. 如何實現128點的基2-FFT演算法,並與MATLAB的fft演算法作對比分析.

我只能給你一個fft演算法，流程圖說起來有點復雜，可以matlab裡面的函數tic（開啟時鍾）t=toc（關閉時鍾）t就是運算過程的時間
當然tic放程序開始，toc放結尾，來分析之即可
function d=lxfft(x)
n=length(x);
if n>2
for i=0:n/2-1
x1(i+1)=x(2*i+1);
x2(i+1)=x(2*i+2);
end
X1=lxfft(x1);
X2=lxfft(x2);
for i=0:n/2-1
X2(i+1)= X2(i+1)*exp(-j*2*pi/n*i);//旋轉因子
d(i+1)=X1(i+1)+X2(i+1);
d(i+n/2+1)=X1(i+1)-X2(i+1);
end
else
d(1)=x(1)+x(2);
d(2)=x(1)-x(2);
end
end

3. 求用C++實現的FFT演算法

很早以前的，如果管用別忘了給我加分呀
/*
This computes an in-place complex-to-complex FFT
x and y are the real and imaginary arrays of 2^m points.
dir = 1 gives forward transform
dir = -1 gives reverse transform
*/
short FFT(short int dir,long m,double *x,double *y)
{
long n,i,i1,j,k,i2,l,l1,l2;
double c1,c2,tx,ty,t1,t2,u1,u2,z;

/* Calculate the number of points */
n = 1;
for (i=0;i<m;i++)
n *= 2;

/* Do the bit reversal */
i2 = n >> 1;
j = 0;
for (i=0;i<n-1;i++) {
if (i < j) {
tx = x[i];
ty = y[i];
x[i] = x[j];
y[i] = y[j];
x[j] = tx;
y[j] = ty;
}
k = i2;
while (k <= j) {
j -= k;
k >>= 1;
}
j += k;
}

/* Compute the FFT */
c1 = -1.0;
c2 = 0.0;
l2 = 1;
for (l=0;l<m;l++) {
l1 = l2;
l2 <<= 1;
u1 = 1.0;
u2 = 0.0;
for (j=0;j<l1;j++) {
for (i=j;i<n;i+=l2) {
i1 = i + l1;
t1 = u1 * x[i1] - u2 * y[i1];
t2 = u1 * y[i1] + u2 * x[i1];
x[i1] = x[i] - t1;
y[i1] = y[i] - t2;
x[i] += t1;
y[i] += t2;
}
z = u1 * c1 - u2 * c2;
u2 = u1 * c2 + u2 * c1;
u1 = z;
}
c2 = sqrt((1.0 - c1) / 2.0);
if (dir == 1)
c2 = -c2;
c1 = sqrt((1.0 + c1) / 2.0);
}

/* Scaling for forward transform */
if (dir == 1) {
for (i=0;i<n;i++) {
x[i] /= n;
y[i] /= n;
}
}

return(TRUE);
}

---------------------------------------------------------------------------------
/*****************fft programe*********************/
#include "typedef.h"
#include "math.h"

struct compx EE(struct compx b1,struct compx b2)
{
struct compx b3;
b3.real=b1.real*b2.real-b1.imag*b2.imag;
b3.imag=b1.real*b2.imag+b1.imag*b2.real;
return(b3);
}

void FFT(struct compx *xin,int N)
{
int f,m,nv2,nm1,i,k,j=1,l;
/*int f,m,nv2,nm1,i,k,j=N/2,l;*/
struct compx v,w,t;
nv2=N/2;
f=N;
for(m=1;(f=f/2)!=1;m++){;}
nm1=N-1;

/*變址運算*/
for(i=1;i <=nm1;i++)
{
if(i <j){t=xin[j];xin[j]=xin[i];xin[i]=t;}
k=nv2;
while(k <j){j=j-k;k=k/2;}
j=j+k;
}

{
int le,lei,ip;
float pi;
for(l=1;l <=m;l++)
{ le=pow(2,l);// 這里用的是L而不是1 !!!!
lei =le/2;
pi=3.14159;
v.real=1.0;
v.imag=0.0;
w.real=cos(pi/lei);
w.imag=-sin(pi/lei);
for(j=1;j <=lei;j++)
{
/*double p=pow(2,m-l)*j;
double ps=2*pi/N*p;
w.real=cos(ps);
w.imag=-sin(ps);*/
for(i=j;i <=N;i=i+le)
{ /* w.real=cos(ps);
w.imag=-sin(ps);*/
ip=i+lei;
t=EE(xin[ip],v);
xin[ip].real=xin[i].real-t.real;
xin[ip].imag=xin[i].imag-t.imag;
xin[i].real=xin[i].real+t.real;
xin[i].imag=xin[i].imag+t.imag;
}
v=EE(v,w);
}
}
}
return;
}

/*****************main programe********************/

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include "typedef.h"

float result[257];
struct compx s[257];
int Num=256;
const float pp=3.14159;

main()
{

int i=1;
for(;i <0x101;i++)
{
s[i].real=sin(pp*i/32);
s[i].imag=0;
}

FFT(s,Num);

for(i=1;i <0x101;i++)
{
result[i]=sqrt(pow(s[i].real,2)+pow(s[i].imag,2));
}

}

-----------------------------------------------------------------------------------
FFT變換 C源代碼

FFT C source code (Simple radix-2)

void fft_float (
unsigned NumSamples,
int InverseTransform,
float *RealIn,
float *ImagIn,
float *RealOut,
float *ImagOut )
{
unsigned NumBits; /* Number of bits needed to store indices */
unsigned i, j, k, n;
unsigned BlockSize, BlockEnd;
double angle_numerator = 2.0 * DDC_PI;
double tr, ti; /* temp real, temp imaginary */
if ( !IsPowerOfTwo(NumSamples) )
{
fprintf (
stderr,
"Error in fft(): NumSamples=%u is not power of two\n",
NumSamples );
exit(1);
}
if ( InverseTransform )
angle_numerator = -angle_numerator;
CHECKPOINTER ( RealIn );
CHECKPOINTER ( RealOut );
CHECKPOINTER ( ImagOut );
NumBits = NumberOfBitsNeeded ( NumSamples );
/*
** Do simultaneous data and bit-reversal ordering into outputs...
*/
for ( i=0; i < NumSamples; i++ )
{
j = ReverseBits ( i, NumBits );
RealOut[j] = RealIn;
ImagOut[j] = (ImagIn == NULL) ? 0.0 : ImagIn;
}
/*
** Do the FFT itself...
*/
BlockEnd = 1;
for ( BlockSize = 2; BlockSize <= NumSamples; BlockSize <<= 1 )
{
double delta_angle = angle_numerator / (double)BlockSize;
double sm2 = sin ( -2 * delta_angle );
double sm1 = sin ( -delta_angle );
double cm2 = cos ( -2 * delta_angle );
double cm1 = cos ( -delta_angle );
double w = 2 * cm1;
double ar[3], ai[3];
double temp;
for ( i=0; i < NumSamples; i += BlockSize )
{
ar[2] = cm2;
ar[1] = cm1;
ai[2] = sm2;
ai[1] = sm1;
for ( j=i, n=0; n < BlockEnd; j++, n++ )
{
ar[0] = w*ar[1] - ar[2];
ar[2] = ar[1];
ar[1] = ar[0];
ai[0] = w*ai[1] - ai[2];
ai[2] = ai[1];
ai[1] = ai[0];
k = j + BlockEnd;
tr = ar[0]*RealOut[k] - ai[0]*ImagOut[k];
ti = ar[0]*ImagOut[k] + ai[0]*RealOut[k];
RealOut[k] = RealOut[j] - tr;
ImagOut[k] = ImagOut[j] - ti;
RealOut[j] += tr;
ImagOut[j] += ti;
}
}
BlockEnd = BlockSize;
}
/*
** Need to normalize if inverse transform...
*/
if ( InverseTransform )
{
double denom = (double)NumSamples;
for ( i=0; i < NumSamples; i++ )
{
RealOut /= denom;
ImagOut /= denom;
}
}
}

int IsPowerOfTwo ( unsigned x )
{
if ( x < 2 )
return FALSE;
if ( x & (x-1) ) // Thanks to 'byang' for this cute trick!
return FALSE;
return TRUE;
}

unsigned NumberOfBitsNeeded ( unsigned PowerOfTwo )
{
unsigned i;
if ( PowerOfTwo < 2 )
{
fprintf (
stderr,
">>> Error in fftmisc.c: argument %d to NumberOfBitsNeeded is too small.\n",
PowerOfTwo );
exit(1);
}
for ( i=0; ; i++ )
{
if ( PowerOfTwo & (1 << i) )
return i;
}
}

unsigned ReverseBits ( unsigned index, unsigned NumBits )
{
unsigned i, rev;
for ( i=rev=0; i < NumBits; i++ )
{
rev = (rev << 1) | (index & 1);
index >>= 1;
}
return rev;
}

double Index_to_frequency ( unsigned NumSamples, unsigned Index )
{
if ( Index >= NumSamples )
return 0.0;
else if ( Index <= NumSamples/2 )
return (double)Index / (double)NumSamples;
return -(double)(NumSamples-Index) / (double)NumSamples;
}

4. 求傅里葉變化 詳細過程 謝謝 又追加懸賞

盡管最初傅立葉分析是作為熱過程的解析分析的工具，但是其思想方法仍然具有典型的還原論和分析主義的特徵。"任意"的函數通過一定的分解，都能夠表示為正弦函數的線性組合的形式，而正弦函數在物理上是被充分研究而相對簡單的函數類，這一想法跟化學上的原子論想法何其相似！奇妙的是,現代數學發現傅立葉變換具有非常好的性質,使得它如此的好用和有用,讓人不晌緩得不感嘆造物的神奇: 1. 傅立葉變換是線性運算元,若賦予適當的范數,它還是酉運算元; 2. 傅立葉變換的逆變換容易求出,而且形式與正變換非常類似; 3. 正弦基函數是微分運算的本徵函數,從而使得線性微分方程的求解可以轉化為常系數的代數方程的求解.在線性時不變的物理系統內,頻率是個不變的性質,從而系統對於復雜激勵的響應可以通過組合其對不同頻率正弦信號的響應來獲取; 4. 著名的卷積定理指出:傅立葉變換可以化復雜的卷積運算為簡單的乘積運算,從而提供了計算卷積的一種簡單手段; 5. 離散形式的傅立葉變換可以利用數字計算機快速的算出(其演算法稱山滑為快速傅立葉變換演算法(FFT)). 正是由於上述的良好性質,傅里葉變換在物理學、數論、組合數學、信號處理、概率、統計、密碼學、聲學、光學等領域都有著廣泛的應用。 有関傅立葉變換的FPGA實現 傅立葉變換是數字信號處理中的基本操作，廣泛應用於表述及分析離散時域信號領域。但由於其運算量與變換點數N的平方成正比關系，因此，在N較大時，直接應用DFT演算法進行譜變換是不切合實際的。然而，快速傅立葉變換技術的出現使情況發生了根本性的變化。本文主要描述了採用FPGA來實現2k/4k/8k點FFT的設計方法。
整體結構
一般情況下，N點的傅立葉變換對為： 其中，WN=exp(－2pi/N)。X(k)和x(n)都為復數。與之相對的快速傅立葉變換有很多種,如DIT(時域抽取法)、DIF（頻域抽取法）、Cooley－Tukey和Winograd等。對於2n傅立葉變換，Cooley－Tukey演算法可導出DIT和DIF演算法。本文運用的基本思想是Cooley－Tukey演算法，即將高點數的傅立葉變換通過多重低點數傅立葉變換來實現。雖然DIT與DIF有差別，但由於它們在本質上都是一種基於標號分解的演算法，故在運算量和演算法復雜性等方面完全一樣，而沒有性能上的優劣之分，所以可以根據需要任取其中一種，本文主要以DIT方法為對象來討論。 N=8192點DFT的運算表達式為： 式中，m=(4n1+n2)(2048k1+k2)(n=4n1+n2，k=2048k1+k2)其中n1和k2可取0,1,．．．,2047,k1和n2可取0,1,2,3。 由式（3）可知，8k傅立葉變換可由4×2k的傅立葉變換構成。同理，4k傅立葉變換可由2×2k的傅立葉變換構成。而2k傅立葉變換可由128×16的傅立葉變換構成。128的傅立葉變換可進一步由16×8的傅立葉變換構成，歸根結底，整個傅立葉變換可由基2、基4的傅立葉變換構成。2k的FFT可以通過5個基4和1個基2變換來實現；4k的FFT變換可通過6個基4變換來實現；8k的FFT可以通過6個基4和1個基2變換來實現。也就是說：FFT的基本結構可由基2/4模塊、復數乘法器、存儲單元和存儲器控制模塊構成，其整體結構如圖1所示。 圖1中，RAM用來存儲輸入數據、運算過程中的中間結果以及運算完成後的數據，ROM用來存儲旋轉因子表。蝶形運算單元即為基2/4模塊，控逗謹臘制模塊可用於產生控制時序及地址信號，以控制中間運算過程及最後輸出結果。
蝶形運算器的實現
基4和基2的信號流如圖2所示。圖中，若A=r0+j*i0，B=r1+j*i1，C=r2+j*i2，D=r3+j*i3是要進行變換的信號，Wk0=c0+j*s0=1，Wk1=c1+j*s1，Wk2=c2+j*s2，Wk3=c3+j*s3為旋轉因子，將其分別代入圖2中的基4蝶形運算單元，則有： A′=[r0+(r1×c1－i1×s1)+(r2×c2－i2×s2)+(r3×c3－i3×s3)]+j[i0+(i1×c1+r1×s1)+(i2×c2+r2×s2)+(i3×c3+r3×s3)]? （4） B′=[r0+(i1×c1+r1×s1)－(r2×c2－i2×s2)－(i3×c3+r3×s3)]+j[i0－(r1×c1－i1×s1)－(i2×c2+r2×s2)+(r3×c3－i3×s3)] (5） C′=[r0－(r1×c1－i1×s1)+(r2×c2－i2×s2)－(r3×c3－i3×s3)]+j[i0－(i1×c1+r1×s1)+(i2×c2+r2×s2)－(i3×c3+r3×s3)] （6） D′=[r0－(i1×c1+r1×s1)－(r2×c2－i2×s2)+(i3×c3+r3×s3)]+j[i0+(r1×c1－i1×s1)－(i2×c2+r2×s2)－(r3×c3－i3×s3)]? （7） 而在基2蝶形中，Wk0和Wk2的值均為1，這樣，將A，B，C和D的表達式代入圖2中的基2運算的四個等式中，則有： A′=r0+(r1×c1－i1×s1)+j[i0+(i1×c1+r1×s1)]? （8） B′=r0－ (r1×c1－i1×s1)+j[i0－(i1×c1+r1×s1)] （9） C′=r2+(r3×c3－i3×s3)+j[i0+(i3×c3+r3×s3)]? （10） D′=r2－(r3×c3－i3×s3)+j[i0－(i3×c3+r3×s3)]? （11） 在上述式（4）～（11）中有很多類同項，如i1×c1+r1×s1和r1×c1－i1×s1等，它們僅僅是加減號的不同，其結構和運算均類似，這就為簡化電路提供了可能。同時，在蝶形運算中，復數乘法可以由實數乘法以一定的格式來表示，這也為設計復數乘法器提供了一種實現的途徑。 以基4為例，在其運算單元中，實際上只需做三個復數乘法運算，即只須計算BWk1、CWk2和DWk3的值即可，這樣在一個基4蝶形單元裡面，最多隻需要3個復數乘法器就可以了。在實際過程中，在不提高時鍾頻率下，只要將時序控制好?便可利用流水線（Pipeline）技術並只用一個復數乘法器就可完成這三個復數乘法，大大節省了硬體資源。 圖2 基2和基4蝶形演算法的信號流圖
FFT的地址
FFT變換後輸出的結果通常為一特定的倒序,因此，幾級變換後對地址的控制必須准確無誤。 倒序的規律是和分解的方式密切相關的，以基8為例，其基本倒序規則如下： 基8可以用2×2×2三級基2變換來表示，則其輸入順序則可用二進制序列（n1 n2 n3）來表示，變換結束後，其順序將變為（n3 n2 n1），如：X?011→ x?110，即輸入順序為3，輸出時順序變為6。 更進一步，對於基16的變換，可由2×2×2×2，4×4，4×2×2等形式來構成，相對於不同的分解形式，往往會有不同的倒序方式。以4×4為例，其輸入順序可以用二進制序列（n1 n2 n3n4）來表示變換結束後，其順序可變為（（n3 n4）（n1 n2）），如： X?0111→ x?1101。即輸入順序為7，輸出時順序變為13。 在2k/4k/8k的傅立葉變換中，由於要經過多次的基4和基2運算，因此，從每次運算完成後到進入下一次運算前，應對運算的結果進行倒序，以保證運算的正確性。
旋轉因子
N點傅立葉變換的旋轉因子有著明顯的周期性和對稱性。其周期性表現為： FFT之所以可使運算效率得到提高，就是利用了對稱性和周期性把長序列的DFT逐級分解成幾個序列的DFT，並最終以短點數變換來實現長點數變換。 根據旋轉因子的對稱性和周期性，在利用ROM存儲旋轉因子時，可以只存儲旋轉因子表的一部分，而在讀出時增加讀出地址及符號的控制，這樣可以正確實現FFT。因此,充分利用旋轉因子的性質，可節省70%以上存儲單元。 實際上，由於旋轉因子可分解為正、餘弦函數的組合，故ROM中存的值為正、餘弦函數值的組合。對2k/4k/8k的傅立葉變換來說，只是對一個周期進行不同的分割。由於8k變換的旋轉因子包括了2k/4k的所有因子，因此，實現時只要對讀ROM的地址進行控制，即可實現2k/4k/8k變換的通用。
存儲器的控制
因FFT是為時序電路而設計的，因此，控制信號要包括時序的控制信號及存儲器的讀寫地址，並產生各種輔助的指示信號。同時在計算模塊的內部，為保證高速，所有的乘法器都須始終保持較高的利用率。這意味著在每一個時鍾來臨時都要向這些單元輸入新的操作數，而這一切都需要控制信號的緊密配合。 為了實現FFT的流形運算，在運算的同時，存儲器也要接收數據。這可以採用乒乓RAM的方法來完成。這種方式決定了實現FFT運算的最大時間。對於4k操作，其接收時間為4096個數據周期，這樣?FFT的最大運算時間就是4096個數據周期。另外，由於輸入數據是以一定的時鍾為周期依次輸入的，故在進行內部運算時，可以用較高的內部時鍾進行運算，然後再存入RAM依次輸出。 為節省資源，可對存儲數據RAM採用原址讀出原址寫入的方法，即在進行下一級變換的同時，首先應將結果回寫到讀出數據的RAM存貯器中；而對於ROM，則應採用與運算的數據相對應的方法來讀出存儲器中旋轉因子的值。 在2k/4k/8k傅立葉變換中，要實現通用性，控制器是最主要的模塊。2k、4k、8k變換具有不同的內部運算時間和存儲器地址，在設計中，針對不同的點數應設計不同的存儲器存取地址，同時，在完成變換後，還要對開始輸出有用信號的時刻進行指示。
硬體的選擇
本設計的硬體實現選用的是現場可編程門陣列(FPGA)來滿足較高速度的需要。本系統在設計時選用的是ALTERA公司的STRATIX晶元，該晶元中包含有DSP單元，可以完成較為耗費資源的乘法器單元。同時，該器件也包含有大量存儲單元，從而可保證旋轉因子的精度。 除了一些專用引腳外，FPGA上幾乎所有的引腳均可供用戶使用，這使得FPGA信號處理方案具有非常好的I/O帶寬。大量的I/O引腳和多塊存儲器可使設計獲得優越的並行處理性能。其獨立的存儲塊可作為輸入/工作存儲區和結果的緩存區，這使得I/O可與FFT計算同時進行。在實現的時間方面，該設計能在4096個時鍾周期內完成一個4096點的FFT。若採用10MHz的輸入時鍾，其變換時間在200μs左右。而由於最新的FPGA使用了MultiTrack互連技術，故可在250MHz以下頻率穩定地工作，同時，FFT的實現時間也可以大大縮小。 FFT運算結果的精度與輸入數據的位數及運算過程中的位數有關，同時和數據的表示形式也有很大關系。一般來說，浮點方式比定點方式精度高。而在定點計算中，存儲器數據的位數越大，運算精度越高，使用的存儲單元和邏輯單元也越多。在實際應用中，應根據實際情況折衷選擇精度和資源。本設計通過MATLAB進行模擬證明：其實現的變換結果與MATLAB工具箱中的FFT函數相比，信噪比可以達到65db以上，完全可以滿足一般工程的實際應用要求。