..《测试信号分析及处理》课程作业快速傅里叶变换一、程序设计思路快速傅里叶变换的目的是减少运算量，其用到的方法是分级进行运算。全部计算分解为 M 级，其中 M log2 N ；在输入序列 xi中是按码位倒序排列的，输出序列 Xk是按顺序排列；每级包含 NN个蝶形单元，第i 级有i 个群，每个22rr群有 2i1 个蝶形单元； 每个蝶形单元都包含乘WN 和WN 系数的运算，每个蝶形单元数据的间隔为 2i1 ，i 为第 i 级； 同一级中各个群的系数W 分布规律完全相同。将输入序列 xi按码位倒序排列时，用到的是倒序算法——雷德算法。 自然序排列的二进制数，其下面一个数总比上面的数大 1，而倒序二进制数的下面一个数是上面一个数在最高位加 1 并由高位向低位仅为而得到的。若已知某数的倒序数是 J ，求下一个倒序数，应先判断 J 的最高位是否为 0，N与 k 进行比较即可得到结果。如果 k J ，说明最高位为 0，应把其变成 1，2N即 J ，这样就得到倒序数了。如果 k J ，即J 的最高位为 1，将最高位化为2NNN0，即 J ，再判断次高位；与 k 进行比较，若为 0，将其变位 1，即 J ，244即得到倒序数，如果次高位为 1，将其化为 0，再判断下一位……即从高位到低位依次判断其是否为 1，为1 将其变位 0，若这一位为 0，将其变位1，即可得到倒序数。若倒序数小于顺序数，进行换位，否则不变，防治重复交换，变回原数。注：因为 0 的倒序数为 0，所以可从 1 开始进行求解。二、程序设计框图（1）倒序算法——雷德算法流程图word. ...(2)FFT 算法流程word. ...三、FFT 源程序void fft(x,n)int n;double x[];{int i,j,k,l,m,n1,n2;double c,c1,e,s,s1,t,tr;for(j=1,i=1;i
