离散傅里叶变换快速算法

离散傅里叶变换快速算法

一、 实验目的

1. 掌握实现时间抽取快速福利也变化（FFT）的编程方法； 2. 掌握基于雷德算法的码位倒置程序；

二、 实验内容

1. 码位倒置程序

采用雷德（Rader）算法实现码位倒置。它的基本原理是采用二进制的“反向进位加法”依次产生对应某一字长的码位倒置排列序列。所谓“反向进位加法”是相对于一般加法而言的，并且主要完成加1操作，即将权值最高的数值与1相加，若有进位，就向较低一级权值进行围，即由左向右进位。

2. 蝶形运算程序

蝶形运算可以由外、中、内三层嵌套循环实现，其中外层循环由技术L公职，当循环体执行M次后，就完成了全部蝶形运算。中层循环油系数W控制，中层循环的循环体需要执行2L1次。内层循环由群书控制，内层循环体的循环次数为

N/2L。综上所述，外、中、内三层循环的循环体执行的次数分别为M次、2L1次和N/2L次，完成的基本蝶形运算数目恰好为MN/2次。

三、 实验结果

1. FFT快速傅里叶变化的C语言程序源代码： #include \"math.h\" #include \"stdio.h\"

void fft(float A[],float B[],unsigned M) {

unsigned long N,I,J,K,L,LE,LE1,P,Q,R;

float Wr,Wi,W1r,W1i,WTr,WTi,theta,Tr,Ti,T; N=1<for (I=0;II) { T=A[I]; A[I]=A[J]; A[J]=T; T=B[I];

1

信号分析与处理实验报告

B[I]=B[J]; B[J]=T; } K=N>>1; while (K >=2&&J>=K){ J-= K; K >>=1; } J+= K; }

for(L=1;L<=M;L++){ LE=1<theta=(-1)*3.1415926536/LE1; W1r=cos(theta); W1i=sin(theta); for(R=0;Rreturn; }

void main() { float R[32],I[32]; int i; for(i=0;i<32;i++) {

2

信号分析与处理实验报告

R[i]=1000219+i; I[i]=0; } fft(R,I,5); for(i=0;i<32;i++) { printf(\"%f+(%f*i)\\n\ } }

2. 程序验证  输入序列：

x(n){1000219.000000,1000220.000000,1000221.000000,1000222.000000,1000223.000000,1000224.000000,1000225.000000,1000226.000000,1000227.000000,1000228.000000,1000229.000000,1000230.000000,1000231.000000,1000232.000000,1000233.000000,1000234.000000,1000235.000000,1000236.000000,1000237.000000,1000238.000000,1000239.000000,1000240.000000,1000241.000000,1000242.000000,1000243.000000,1000244.000000,1000245.000000,1000246.000000,1000247.000000,1000248.000000,1000249.000000,1000250.000000}

 经FFT变换后的输出序列：

X(k){32007504.000000+0.000000i,-15.999994+162.450745i,-15.999998+80.437424i,-16.000002+52.744919i,-15.999995+38.627411i,-15.999995+29.933886i,-15.999991+23.945679i,-15.999992+19.496031i,-16.000000+15.999995i,-16.000002+13.130857i,-16.000002+10.690854i,-16.000000+8.552172i,-15.999999+6.627410i,-15.999998+4.853537i,-15.999996+3.182583i,-15.999991+1.575829i,-16.000000+0.000000i,-16.000002+-1.575859i,-16.000000+-3.182594i,-15.999999+-4.853544i,-15.999999+-6.627412i,-15.999997+-8.552172i,-15.999995+-10.690848i,-15.999983+-13.130850i,-16.000000+-15.999995i,-16.000002+-19.496054i,-16.000002+-23.945690i,-16.000000+-29.933889i,-16.000006+-38.627407i,-16.000010+-52.744919i,-16.000015+-80.437408i,-16.000031+-162.450684i}

3