⑴ 基数为2的FFT算法
从上节所述，FFT算法快速的关键在于将原来傅氏矩阵分解为每一行仅含有两个非零项l与Wi的矩阵的乘积。下面用基数为2，即N=2n的情形讨论矩阵的分解过程.并主要按时间分解的情况讨论。
按时间分解的FFT算法
设N=2n，n为正整数。考虑输入序列x0(l)的DFT
物探数字信号分析与处理技术
将l与m用二进制表示
物探数字信号分析与处理技术
将(7-2-2)代入(7-2-1)中，得到
物探数字信号分析与处理技术
为了说明问题，我们取N=8，于是从(7-2-2)得到
物探数字信号分析与处理技术
从(7-2-4)和(7-2-3)得到
物探数字信号分析与处理技术
将(7-2-5)中的W的指数按时间l进行分解，有
物探数字信号分析与处理技术
因为
物探数字信号分析与处理技术
故从(7-2-6)得到
物探数字信号分析与处理技术
将上式代入(7-2-5)中得到
物探数字信号分析与处理技术
物探数字信号分析与处理技术
我们在公式(7-2-7)中由里往外求和，并置
物探数字信号分析与处理技术
于是得到
物探数字信号分析与处理技术
首先写出(7-2-8)的所有式子
物探数字信号分析与处理技术
将方程组(7-2-12)写成矩阵形式，得到
物探数字信号分析与处理技术
我们看到(7-2-13)中的方阵，正好是(7-1-13)中的方阵，也就是(7-1-12)中被分解出来的第3个矩阵，只不过这里的x1(l)与x0(l)中的l是用二进制数表示而已。
再写出(7-2-9)的所有式子，得到
物探数字信号分析与处理技术
将方程组写成矩阵形式，则有
物探数字信号分析与处理技术
显然(7-2-15)中的矩阵，正好是(7-1-14)中的方阵，也就是(7-1-12)中被分解出来的第二个矩阵，只不过这里的x2(l)与x1(l)是用二进制数表示而已，最后将(7-2-10)中的全部式子写出，得到
物探数字信号分析与处理技术
将方程组(7-2-16)写成矩阵形式，则有
物探数字信号分析与处理技术
显然，(7-2-17)中的方阵正是(7-1-15)中的方阵，也就是(7-1-12)中被分解出来的第1个矩阵，只不过这里的x3(l)与x2(l)中的l是用二进制数表示。
由此可见，(7-2-7)中由里往外的三个求和式(7-2-8)、(7-2-9)及(7-2-10)，完全确定了(7-1-12)中三个被分解的矩阵因子。求和得到的最终结果x3(m0，m1，m2)，与我们所要求的X(m2，m1，m0)正好是逆序的。
到此为止，我们就看到(7-1-11)中的方阵是怎样被分解成三个方阵因子的。对于N=8，方程(7-2-8)～(7-2-11)就是计算DFT的FFT算法。为了对FFT算法有一个直观的了解并便于编制程序，我们以N=8为例，画出其流程图(图7-2-1)。
根据(7-2-13)，将其中的W4用-W0代替，画出从x0(r)到x1(r)的流程图。这一迭代过程用符号#1表示;再根据(7-2-15)，将其中的与W4、W6分别换成-W0与-W2，画出从x1(r)到x2(r)的流程图，这一迭代过程记为#2;最后，根据(7-2-17)，将其中的W4、W6、W5、W7分别换成-W0、-W2、-W1、-W3，画出流程图7-2-3合并图7-2-1～7-2-3，就得到从x0(r)到x3(r)的完整流程图7-2-4。
图7-2-1 第一次递推
图7-2-2 第二次递推
在图7-2-5中，画出N=16=24的FFT算法流程图:
根据从x0到谱X的FFT算法流程图7-2-4与图7-2-5，我们总结出如下几点:
(1)从x0到终值xr的最大迭代次数r，由r=log2N确定。
例如，N=8，最大迭代次数r=3;N=16，最大迭代次数r=4。
(2)在第r次迭代中，要乘的W因子为
图7-2-3 第三次递推
例如，N=8，在第一次迭代中，要乘因子W0;在第二次迭代中要乘因子W0，W1，W2，W3。
(3)在第r次迭代中，包含2r-1个组，每个组
包含 。例如N=8，第一次迭代r=1，有
一个组，每组包含8个x(s);在第二次迭代中包含2个组，每组包含4个x(s);第三次迭代中包含4个组，每组2个x(s)。
图7-2-4 x0(r)到x3(r)的完整流程图
(4)在第r次迭代中，各组包含的W因子各不相同，且每一组仅包含一种类型的因子 ，此因子在组中一半数为正，另一半数为负。例如N=8，第二次迭代中，第一组包含因子W0，且在该组中一半数为正，另一半数为负;第二组包含因子W2，在该组中也是一半数为正，另一半数为负。
(5)在第r次迭代中，各组包含的W因子除正负号外类型均相同。所以只须确定每组中第一个因子，之后按半数反号，即得到所求W因子。具体做法是，在每组第一个因子WSN2r对应的xr(k)中，将k表示成n位的二进制数，n=log2N，并把这个二进制数右移n-r位，左边空出的地方添零补足n位，之后再将此n位二进制数逆位，即得到所求W因子的指数。例如，N=8，迭代#2包含两组，每组包含4个x2(k)，第二组第一个因子W对应于x2(4)。将4表示成3位的二进制数为100，把它右移1位成10，右边添零补成3位为010，逆位仍为010，故所求因子为W2，第2组全部W因子为W2，W2，-W2，-W2。又如，N=16，迭代#3中包含4个组，每组包含4个x3(k)，第4组第1个因子W对应于x3(12)。将12表示成4位的二进制数为1100。右移1位变成110，将左边空处添零补成4位为0110，逆位仍为0110，故所求因子为W6，从而第4组全部W因子为W6，W6，-W6与-W6。
图7-2-5 N=16=24的FFT算法流程图
(6)如果已知N=2的FFT算法，容易从它求得n=2的FFT算法。具体作法是，在n=2n-1的FFT算法中，将所有xr(l)的个数加倍，所有W的个数及其乘幂加倍，就得N=2n中前n-1次迭代的全部结果。之后，将新得到的第n-1次迭代中乘幂相同的W个数减半，就是第n次迭代中前2n/2个W，将这些W的乘幂依次加1，就得到后2n/2个W。例如N=16的前3次迭代，都是N=8的三次迭代中所有xr(l)的个数加倍，W的个数及其乘幂加倍的结果。再将N=16的第三次迭代中乘幂相同的W个数减半，就是第4次迭代中前8个W。
(7)在第r-1次迭代中的xr-1(i)与xr-1(j)仅用于计算r次迭代中的xr(i)与xr(j)，而不会用于计算任何其它的xr(k)与xr(l)。例如N=16的第二次迭代中的x2(0)与x2(2)，只用于计算第三次迭代中的x3(0)与x3(2);第三次迭代中的x3(8)与x3(9)也只用于计算第四次迭代中的x4(8)与x4(9)。因此，我们可以把第r次迭代中的xr(i)与xr(j)，存放到r-1次迭代xr-1(i)与xr-1(j)所占用的原存储单元中去，这样，所需要的计算机存储容量就只限于原数据序列占据的单元数。如果是复序列的话，存储单元要加倍。
(8)上述FFT算法也可用于计算逆离散傅氏变换(IDFT)(图7-2-6)，只不过在计算时要将上述FFT算法中的W因子用其共轭W*代替，并将最后迭代计算的结果统统乘以1/N.
图7-2-6 N=8的逆离散富氏变换流程图
⑵ 基于FFT的算法优化 要c语言完整程序（利用旋转因子的性质），有的请留言，答谢！！！(有核心代码，望指教
实现(C描述)
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
//#include "complex.h"
// --------------------------------------------------------------------------
#define N 8 //64
#define M 3 //6 //2^m=N
#define PI 3.1415926
// --------------------------------------------------------------------------
float twiddle[N/2] = {1.0, 0.707, 0.0, -0.707};
float x_r[N] = {1, 1, 1, 1, 0, 0, 0, 0};
float x_i[N]; //N=8
/*
float twiddle[N/2] = {1, 0.9951, 0.9808, 0.9570, 0.9239, 0.8820, 0.8317, 0.7733,
0.7075, 0.6349, 0.5561, 0.4721, 0.3835, 0.2912, 0.1961, 0.0991,
0.0000,-0.0991,-0.1961,-0.2912,-0.3835,-0.4721,-0.5561,-0.6349,
-0.7075,-0.7733, 0.8317,-0.8820,-0.9239,-0.9570,-0.9808,-0.9951}; //N=64
float x_r[N]={1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,};
float x_i[N];
*/
FILE *fp;
// ----------------------------------- func -----------------------------------
/**
* 初始化输出虚部
*/
static void fft_init( void )
{
int i;
for(i=0; i<N; i++) x_i[i] = 0.0;
}
/**
* 反转算法.将时域信号重新排序.
* 这个算法有改进的空间
*/
static void bitrev( void )
{
int p=1, q, i;
int bit_rev[ N ]; //
float xx_r[ N ]; //
bit_rev[ 0 ] = 0;
while( p < N )
{
for(q=0; q<p; q++)
{
bit_rev[ q ] = bit_rev[ q ] * 2;
bit_rev[ q + p ] = bit_rev[ q ] + 1;
}
p *= 2;
}
for(i=0; i<N; i++) xx_r[ i ] = x_r[ i ];
for(i=0; i<N; i++) x_r[i] = xx_r[ bit_rev[i] ];
}
/* ------------ add by sshc625 ------------ */
static void bitrev2( void )
{
return ;
}
/* */
void display( void )
{
printf("\n\n");
int i;
for(i=0; i<N; i++)
printf("%f\t%f\n", x_r[i], x_i[i]);
}
/**
*
*/
void fft1( void )
{ fp = fopen("log1.txt", "a+");
int L, i, b, j, p, k, tx1, tx2;
float TR, TI, temp; // 临时变量
float tw1, tw2;
/* 深M. 对层进行循环. L为当前层, 总层数为M. */
for(L=1; L<=M; L++)
{
fprintf(fp,"----------Layer=%d----------\n", L);
/* b的意义非常重大,b表示当前层的颗粒具有的输入样本点数 */
b = 1;
i = L - 1;
while(i > 0)
{
b *= 2;
i--;
}
// -------------- 是否外层对颗粒循环, 内层对样本点循环逻辑性更强一些呢! --------------
/*
* outter对参与DFT的样本点进行循环
* L=1, 循环了1次(4个颗粒, 每个颗粒2个样本点)
* L=2, 循环了2次(2个颗粒, 每个颗粒4个样本点)
* L=3, 循环了4次(1个颗粒, 每个颗粒8个样本点)
*/
for(j=0; j<b; j++)
{
/* 求旋转因子tw1 */
p = 1;
i = M - L; // M是为总层数, L为当前层.
while(i > 0)
{
p = p*2;
i--;
}
p = p * j;
tx1 = p % N;
tx2 = tx1 + 3*N/4;
tx2 = tx2 % N;
// tw1是cos部分, 实部; tw2是sin部分, 虚数部分.
tw1 = ( tx1>=N/2)? -twiddle[tx1-N/2] : twiddle[ tx1 ];
tw2 = ( tx2>=N/2)? -twiddle[tx2-(N/2)] : twiddle[tx2];
/*
* inner对颗粒进行循环
* L=1, 循环了4次(4个颗粒, 每个颗粒2个输入)
* L=2, 循环了2次(2个颗粒, 每个颗粒4个输入)
* L=3, 循环了1次(1个颗粒, 每个颗粒8个输入)
*/
for(k=j; k<N; k=k+2*b)
{
TR = x_r[k]; // TR就是A, x_r[k+b]就是B.
TI = x_i[k];
temp = x_r[k+b];
/*
* 如果复习一下 (a+j*b)(c+j*d)两个复数相乘后的实部虚部分别是什么
* 就能理解为什么会如下运算了, 只有在L=1时候输入才是实数, 之后层的
* 输入都是复数, 为了让所有的层的输入都是复数, 我们只好让L=1时候的
* 输入虚部为0
* x_i[k+b]*tw2是两个虚数相乘
*/
fprintf(fp, "tw1=%f, tw2=%f\n", tw1, tw2);
x_r[k] = TR + x_r[k+b]*tw1 + x_i[k+b]*tw2;
x_i[k] = TI - x_r[k+b]*tw2 + x_i[k+b]*tw1;
x_r[k+b] = TR - x_r[k+b]*tw1 - x_i[k+b]*tw2;
x_i[k+b] = TI + temp*tw2 - x_i[k+b]*tw1;
fprintf(fp, "k=%d, x_r[k]=%f, x_i[k]=%f\n", k, x_r[k], x_i[k]);
fprintf(fp, "k=%d, x_r[k]=%f, x_i[k]=%f\n", k+b, x_r[k+b], x_i[k+b]);
} //
} //
} //
}
/**
* ------------ add by sshc625 ------------
* 该实现的流程为
* for( Layer )
* for( Granule )
* for( Sample )
*
*
*
*
*/
void fft2( void )
{ fp = fopen("log2.txt", "a+");
int cur_layer, gr_num, i, k, p;
float tmp_real, tmp_imag, temp; // 临时变量, 记录实部
float tw1, tw2;// 旋转因子,tw1为旋转因子的实部cos部分, tw2为旋转因子的虚部sin部分.
int step; // 步进
int sample_num; // 颗粒的样本总数(各层不同, 因为各层颗粒的输入不同)
/* 对层循环 */
for(cur_layer=1; cur_layer<=M; cur_layer++)
{
/* 求当前层拥有多少个颗粒(gr_num) */
gr_num = 1;
i = M - cur_layer;
while(i > 0)
{
i--;
gr_num *= 2;
}
/* 每个颗粒的输入样本数N' */
sample_num = (int)pow(2, cur_layer);
/* 步进. 步进是N'/2 */
step = sample_num/2;
/* */
k = 0;
/* 对颗粒进行循环 */
for(i=0; i<gr_num; i++)
{
/*
* 对样本点进行循环, 注意上限和步进
*/
for(p=0; p<sample_num/2; p++)
{
// 旋转因子, 需要优化...
tw1 = cos(2*PI*p/pow(2, cur_layer));
tw2 = -sin(2*PI*p/pow(2, cur_layer));
tmp_real = x_r[k+p];
tmp_imag = x_i[k+p];
temp = x_r[k+p+step];
/*(tw1+jtw2)(x_r[k]+jx_i[k])
*
* real : tw1*x_r[k] - tw2*x_i[k]
* imag : tw1*x_i[k] + tw2*x_r[k]
* 我想不抽象出一个
* typedef struct {
* double real; // 实部
* double imag; // 虚部
* } complex; 以及针对complex的操作
* 来简化复数运算是否是因为效率上的考虑!
*/
/* 蝶形算法 */
x_r[k+p] = tmp_real + ( tw1*x_r[k+p+step] - tw2*x_i[k+p+step] );
x_i[k+p] = tmp_imag + ( tw2*x_r[k+p+step] + tw1*x_i[k+p+step] );
/* X[k] = A(k)+WB(k)
* X[k+N/2] = A(k)-WB(k) 的性质可以优化这里*/
// 旋转因子, 需要优化...
tw1 = cos(2*PI*(p+step)/pow(2, cur_layer));
tw2 = -sin(2*PI*(p+step)/pow(2, cur_layer));
x_r[k+p+step] = tmp_real + ( tw1*temp - tw2*x_i[k+p+step] );
x_i[k+p+step] = tmp_imag + ( tw2*temp + tw1*x_i[k+p+step] );
printf("k=%d, x_r[k]=%f, x_i[k]=%f\n", k+p, x_r[k+p], x_i[k+p]);
printf("k=%d, x_r[k]=%f, x_i[k]=%f\n", k+p+step, x_r[k+p+step], x_i[k+p+step]);
}
/* 开跳!:) */
k += 2*step;
}
}
}
/*
* 后记:
* 究竟是颗粒在外层循环还是样本输入在外层, 好象也差不多, 复杂度完全一样.
* 但以我资质愚钝花费了不少时间才弄明白这数十行代码.
* 从中我发现一个于我非常有帮助的教训, 很久以前我写过一部分算法, 其中绝大多数都是递归.
* 将数据量减少, 减少再减少, 用归纳的方式来找出数据量加大代码的规律
* 比如FFT
* 1. 先写死LayerI的代码; 然后再把LayerI的输出作为LayerII的输入, 又写死代码; ......
* 大约3层就可以统计出规律来. 这和递归也是一样, 先写死一两层, 自然就出来了!
* 2. 有的功能可以写伪代码, 不急于求出结果, 降低复杂性, 把逻辑结果定出来后再添加.
* 比如旋转因子就可以写死, 就写1.0. 流程出来后再写旋转因子.
* 寥寥数语, 我可真是流了不少汗! Happy!
*/
void dft( void )
{
int i, n, k, tx1, tx2;
float tw1,tw2;
float xx_r[N],xx_i[N];
/*
* clear any data in Real and Imaginary result arrays prior to DFT
*/
for(k=0; k<=N-1; k++)
xx_r[k] = xx_i[k] = x_i[k] = 0.0;
// caculate the DFT
for(k=0; k<=(N-1); k++)
{
for(n=0; n<=(N-1); n++)
{
tx1 = (n*k);
tx2 = tx1+(3*N)/4;
tx1 = tx1%(N);
tx2 = tx2%(N);
if(tx1 >= (N/2))
tw1 = -twiddle[tx1-(N/2)];
else
tw1 = twiddle[tx1];
if(tx2 >= (N/2))
tw2 = -twiddle[tx2-(N/2)];
else
tw2 = twiddle[tx2];
xx_r[k] = xx_r[k]+x_r[n]*tw1;
xx_i[k] = xx_i[k]+x_r[n]*tw2;
}
xx_i[k] = -xx_i[k];
}
// display
for(i=0; i<N; i++)
printf("%f\t%f\n", xx_r[i], xx_i[i]);
}
// ---------------------------------------------------------------------------
int main( void )
{
fft_init( );
bitrev( );
// bitrev2( );
//fft1( );
fft2( );
display( );
system( "pause" );
// dft();
return 1;
}
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/sshcx/archive/2007/06/14/1651616.aspx
⑶ 设x(n)={1，0.5，0，0.5，1，1，0.5，0)，用FFT算法求x(n)的DFT。FFT算法任选，画出FFT的流程图。
二维FFT相当于对行和列分别进行一维FFT运算。
先对各行逐一进行一维FFT，然后再对变换后的新矩阵的各列逐一进行一维FFT。相应的伪代码如下所示：for (int i=0; i<M; i++)FFT_1D(ROW[i]，N);for (int j=0; j<N; j++)FFT_1D(COL[j]，M);其中，ROW[i]表示矩阵的第i行。
例：
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define N 1000
/*定义复数类型*/
typedef struct{
double real;
double img;
}complex;
complex x[N], *W; /*输入序列,变换核*/
int size_x=0;/*输入序列的大小，在本程序中仅限2的次幂*/
double PI;/*圆周率*/
void fft();/*快速傅里叶变换*/
void initW(); /*初始化变换核*/
void change(); /*变址*/
void add(complex ,complex ,complex *); /*复数加法*/
void mul(complex ,complex ,complex *); /*复数乘法*/
void sub(complex ,complex ,complex *); /*复数减法*/
void output();
int main(){
int i;/*输出结果*/
system("cls");
PI=atan(1)*4;
printf("Please input the size of x: ");
scanf("%d",&size_x);
printf("Please input the data in x[N]: ");
for(i=0;i<size_x;i++)
scanf("%lf%lf",&x[i].real,&x[i].img);
initW();
fft();
output();
return 0;
}
/*快速傅里叶变换*/
void fft(){
int i=0,j=0,k=0,l=0;
complex up,down,proct;
change();
for(i=0;i< log(size_x)/log(2) ;i++){ /*一级蝶形运算*/
l=1<<i;
(3)递推dft算法c语言程序扩展阅读：
FFT算法很多，根据实现运算过程是否有指数因子WN可分为有、无指数因子的两类算法。
经典库利-图基算法 当输入序列的长度N不是素数(素数只能被1而它本身整除）而是可以高度分解的复合数，即N=N1N2N3…Nr时，若N1=N2=…=Nr=2，N=2则N点DFT的计算可分解为N=2×N/2，即两个N/2点DFT计算的组合，而N/2点DFT的计算又可分解为N/2=2×N/4，即两个N/4点DFT计算的组合。
依此类推，使DFT的计算形成有规则的模式，故称之为以2为基底的FFT算法。同理，当N=4时，则称之为以4为基底的FFT算法。当N=N1·N2时，称为以N1和N2为基底的混合基算法。
⑷ 求 原始DFT 算法 代码。有的麻烦发到我邮箱[email protected]
加入多个PushButton，如何设置始终有个获得焦点（这个比较好实现）
但是，如下情况的时候要怎么处理：一个界面中左边是多个PushButton，右边也是可获得焦点的组
⑸ C语言程序，离散傅里叶变换，调用函数声明处总有错误
int DFT(int dir,int m,double *x1,double *y1)
{
long i,k;
double arg;
double cosarg,sinarg;
double *x2=NULL,*y2=NULL;
x2=malloc(m*sizeof(double));
y2=malloc(m*sizeof(double));
if(x2==NULL||y2==NULL)return(FALSE);
for(i=0;i<m;i++)
{
x2[i]=0;
y2[i]=0;
arg=-dir*2.0*3.141592654*(double)i/(double)m;
for(k=0;k<m;k++)
{
cosarg=cos(k*arg);
sinarg=sin(k*arg);
x2[i]+=(x1[k]*cosarg-y1[k]*sinarg);
y2[i]+=(x1[k]*sinarg+y1[k]*cosarg);
}
}
/*Copythedataback*/
if(dir==1)
{
for(i=0;i<m;i++)
{
x1[i]=x2[i]/(double)m;
y1[i]=y2[i]/(double)m;
}
}
else
{
for(i=0;i<m;i++)
{
x1[i]=x2[i];
y1[i]=y2[i];
}
}
free(x2);
free(y2);
return(TRUE);
}
⑹ 求递推DFT算法的C语言程序
风格和地方工会地方化
⑺ 我做“基于FFT算法与实现”和“FIR滤波器的设计与实现”的实验。。
1.1 实验目的
1．了解数字信号处理系统的一般构成；
2．掌握奈奎斯特抽样定理。
1.2 实验仪器
1．YBLD智能综合信号源测试仪 1台
2．双踪示波器 1台
3．MCOM－TG305数字信号处理与现代通信技术实验箱 1台
4．PC机（装有MATLAB、MCOM－TG305配套实验软件） 1台
1.3 实验原理
一个典型的DSP系统除了数字信号处理部分外，还包括A/D和D/A两部分。这是因为自然界的信号，如声音、图像等大多是模拟信号，因此需要将其数字化后进行数字信号处理，模拟信号的数字化即称为A/D转换。数字信号处理后的数据可能需还原为模拟信号，这就需要进行D/A转换。一个仅包括A/D和D/A两部分的简化数字信号处理系统功能如图1所示。
A/D转换包括三个紧密相关的过程，即抽样、量化和编码。A/D转换中需解决的以下几个重要问题：抽样后输出信号中还有没有原始信号的信息？如果有能不能把它取出来？抽样频率应该如何选择？
奈奎斯特抽样定理（即低通信号的均匀抽样定理）告诉我们，一个频带限制在0至fx以内的低通信号x(t)，如果以fs≥2fx的抽样速率进行均匀抽样，则x(t)可以由抽样后的信号xs(t)完全地确定，即xs(t)包含有x(t)的成分，可以通过适当的低通滤波器不失真地恢复出x(t)。最小抽样速率fs=2fx称为奈奎斯特速率。
低通
译码
编码
量化
抽样
输入信号 样点输出 滤波输出
A/D（模数转换） D/A（数模转换）
图1 低通采样定理演示
为方便实现，实验中更换了一种表现形式，即抽样频率固定（10KHz），通过改变输入模拟信号的频率来展示低通抽样定理。我们可以通过研究抽样频率和模拟信号最高频率分量的频率之间的关系，来验证低通抽样定理。
1.4 实验内容
1．软件仿真实验：编写并调试MATLAB程序，分析有关参数，记录有关波形。
2．硬件实验：输入不同频率的正弦信号，观察采样时钟波形、输入信号波形、样点输出波形和滤波输出波形。
1.5 MATLAB参考程序和仿真内容
%*******************************************************************%
%f—余弦信号的频率
% M—基2 FFT幂次数 N=2^M为采样点数，这样取值是为了便于作基2的FFT分析
%2. 采样频率Fs
%*******************************************************************%
function samples(f,Fs,M)
N=2^M; % fft点数=取样总点数
Ts=1/Fs; % 取样时间间隔
T=N*Ts; % 取样总时间=取样总点数*取样时间间隔
n=0:N-1;
t=n*Ts;
Xn=cos(2*f*pi*t);
subplot(2,1,1);
stem(t,Xn);
axis([0 T 1.1*min(Xn) 1.1*max(Xn)]);
xlabel('t -->');
ylabel('Xn');
Xk=abs(fft(Xn,N));
subplot(2,1,2);
stem(n,Xk);
axis([0 N 1.1*min(Xk) 1.1*max(Xk)]);
xlabel('frequency -->');
ylabel('!Xk!');
%*******************************************************************%
假如有一个1Hz的余弦信号y=cos(2*π*t)，对其用4Hz的采样频率进行采样，共采样32点，只需执行samples(1,4,5)，即可得到仿真结果。
软件仿真实验内容如下表所示：
仿真参数
f
Fs
Wo(计算)
Xn（图形）
Xk（图形）
（1，4，5）
另外记录图形，并标图号
（1，8，5）
（2，8，6）
自 选
1.6 硬件实验步骤
本实验箱采样频率fs固定为10KHz，低通滤波器的截止频率约为4.5KHz。
1、用低频信号源产生正弦信号，正弦信号源频率f自定，并将其接至2TP2（模拟输入）端，将示波器通道一探头接至2TP6（采样时钟）端观察采样时钟波形，示波器通道二探头接至2TP2观察并记录输入信号波形。
2、将示波器通道二探头接至2TP3观察并记录样点输出波形。
3、将示波器通道二探头接至2TP4观察并记录滤波输出波形。
4、根据采样定理，分f=fs /8、f=fs/4、f=fs/2等3种情况更改正弦信号频率，重复步骤2至步骤3。
5、用低频信号源产生方波信号，重复步骤1至步骤4。
1.7 思考题
1、 讨论在仿真实验中所计算的数字域频率Wo和Xk的图形中非零谱线位置之间的对应关系。
2、 讨论在仿真实验中自选参数的意义。
3、将在2TP2端加方波信号后的恢复波形，与相同频率的正弦信号的恢复波形相比，能够得出哪些结论？
2 FFT频谱分析实验
2.1 实验目的
1．通过实验加深对快速傅立叶变换（FFT）基本原理的理解。
2．了解FFT点数与频谱分辨率的关系，以及两种加长序列FFT与原序列FFT的关系。
2.2 实验仪器
1．YBLD智能综合信号源测试仪 1台
2．双踪示波器 1台
3．MCOM－TG305数字信号处理与现代通信技术实验箱 1台
4．PC机（装有MATLAB、MCOM－TG305配套实验软件） 1台
2.3 实验原理
离散傅里叶变换（DFT）和卷积是信号处理中两个最基本也是最常用的运算，它们涉及到信号与系统的分析与综合这一广泛的信号处理领域。实际上卷积与DFT之间有着互通的联系：卷积可化为DFT来实现，其它的许多算法，如相关、滤波和谱估计等都可化为DFT来实现，DFT也可化为卷积来实现。
对N点序列x(n)，其DFT变换对定义为：
在DFT运算中包含大量的重复运算。FFT算法利用了蝶形因子WN的周期性和对称性，从而加快了运算的速度。FFT算法将长序列的DFT分解为短序列的DFT。N点的DFT先分解为2个N/2点的DFT，每个N/2点的DFT又分解为2个N/4点的DFT。按照此规律，最小变换的点数即所谓的“基数（radix）。”因此，基数为2的FFT算法的最小变换（或称蝶形）是2点DFT。一般地，对N点FFT，对应于N个输入样值，有N个频域样值与之对应。一般而言，FFT算法可以分为时间抽取（DIT）FFT和频率抽取（DIF）两大类。
在实际计算中，可以采用在原来序列后面补0的加长方法来提高FFT的分辨率；可以采用在原来序列后面重复的加长方法来增加FFT的幅度。
2.4 实验内容
1．软件仿真实验：分别观察并记录正弦序列、方波序列及改变FFT的点数后的频谱；分别观察并记录正弦序列、方波序列及2种加长序列等信号的频谱。
2．硬件实验：分别观察并记录正弦信号、方波信号及改变FFT的点数后的频谱。
2.5 MATLAB参考程序和仿真内容
%*******************************************************************%
function[x]=ffts(mode,M)
Nfft=2^M;
x=zeros(1,Nfft); %定义一个长度为Nfft的一维全0数组
if mode= =1 for n=0:Nfft-1 x(n+1)=sin(2*pi*n/Nfft); end
end %定义一个长度为Nfft的单周期正弦序列
if mode= =2 for n=0:Nfft-1 x(n+1)=sin(4*pi*n/Nfft); end
end %定义一个长度为Nfft的双周期正弦序列
if mode= =3 for n=0:Nfft/2-1 x(n+1)=sin(4*pi*n/Nfft); end
end %定义一个长度为Nfft/2的正弦序列，后面一半为0序列。
if mode= =4 for n=0:Nfft-1 x(n+1)=square(2*pi*n/Nfft); end
end
if mode= =5 for n=0:Nfft-1 x(n+1)=square(2*pi*n/Nfft); end
end
if mode= =6 for n=0:Nfft/2-1 x(n+1)=square(4*pi*n/Nfft); end
end
n=0:Nfft-1;
subplot(2,1,1);
stem(n,x);
axis([0 Nfft-1 1.1*min(x) 1.1*max(x)]);
xlabel('Points-->');
ylabel('x(n)');
X=abs(fft(x,Nfft));
subplot(2,1,2);
stem(n,X);
axis([0 Nfft-1 1.1*min(X) 1.1*max(X)]);
xlabel('frequency-->');
ylabel('!X(k)!');
%*******************************************************************%
假设需观察方波信号的频谱，对一个周期的方波信号作32点的FFT，则只需在MATLAB的命令窗口下键入：[x]=ffts(21,5) ，程序进行模拟，并且输出FFT的结果。
关于软件仿真实验内容，建议在完成大量仿真例子的基础上，选择能够体现实验要求的4个以上的例子进行记录。例如要观察后面补0的加长方法来提高FFT的分辨率的现象，可以仿真ffts(4,5)和ffts(6,6)两个例子。
2.6 硬件实验步骤
1．将低频信号源输出加到实验箱模拟通道1输入端，将示波器探头接至模拟通道1输出端。
2．在保证实验箱正确加电且串口电缆连接正常的情况下，运行数字信号处理与DSP应用实验开发软件，在“数字信号处理实验”菜单下选择“FFT频谱分析”子菜单，出现显示FFT频谱分析功能提示信息的窗口。
3．用低频信号产生器产生一个1KHz的正弦信号。
4．选择FFT频谱分析与显示的点数为64点，开始进行FFT运算。此后，计算机将周期性地取回DSP运算后的FFT数据并绘图显示
5．改信号源频率，观察并记录频谱图的变化。
6．选择FFT的点数为128点，观察并记录频谱图的变化。
7．更改正弦信号的频率，重复步骤4 ~步骤6。
8．用低频信号产生器产生一个1KHz的方波信号，重复步骤4 ~步骤7。注意：应根据实验箱采样频率fs为10KHz和方波信号的频带宽度选择方波信号的频率。
本硬件实验要进行两种信号，每个信号两种频率，每个信号两种点数等共8次具体实验内容，性质能够体现实验要求的4个以上的例子进行记录。
2.7 思考题
1．对同一个信号，不同点数FFT观察到的频谱图有何区别？
2．序列加长后FFT与原序列FFT的关系是什么，试推导其中一种关系。
3．用傅立叶级数理论，试说明正弦信号频谱和方波信号频谱之间的关系。
3 IIR滤波器设计实验
3.1 实验目的
1．通过实验加深对IIR滤波器基本原理的理解。
2．学习编写IIR滤波器的MATLAB仿真程序。
3.2 实验仪器
1．YBLD智能综合信号源测试仪 1台
2．双踪示波器 1台
3．MCOM－TG305数字信号处理与现代通信技术实验箱 1台
4．PC机（装有MATLAB、MCOM－TG305配套实验软件） 1台
3.3 实验原理
IIR滤波器有以下几个特点：
1．IIR数字滤波器的系统函数可以写成封闭函数的形式。
2．IIR数字滤波器采用递归型结构，即结构上带有反馈环路。IIR滤波器运算结构通常由延时、乘以系数和相加等基本运算组成，可以组合成直接型、正准型、级联型、并联型四种结构形式，都具有反馈回路。由于运算中的舍入处理，使误差不断累积，有时会产生微弱的寄生振荡。
3．IIR数字滤波器在设计上可以借助成熟的模拟滤波器的成果，如巴特沃斯、契比雪夫和椭圆滤波器等，有现成的设计数据或图表可查，其设计工作量比较小，对计算工具的要求不高。在设计一个IIR数字滤波器时，我们根据指标先写出模拟滤波器的公式，然后通过一定的变换，将模拟滤波器的公式转换成数字滤波器的公式。
4．IIR数字滤波器的相位特性不好控制，对相位要求较高时，需加相位校准网络。
在MATLAB下设计IIR滤波器可使用Butterworth函数设计出巴特沃斯滤波器，使用Cheby1函数设计出契比雪夫I型滤波器，使用Cheby2设计出契比雪夫II型滤波器，使用ellipord函数设计出椭圆滤波器。下面主要介绍前两个函数的使用。
与FIR滤波器的设计不同，IIR滤波器设计时的阶数不是由设计者指定，而是根据设计者输入的各个滤波器参数（截止频率、通带滤纹、阻带衰减等），由软件设计出满足这些参数的最低滤波器阶数。在MATLAB下设计不同类型IIR滤波器均有与之对应的函数用于阶数的选择。
一、巴特沃斯IIR滤波器的设计
在MATLAB下，设计巴特沃斯IIR滤波器可使用butter函数。
Butter函数可设计低通、高通、带通和带阻的数字和模拟IIR滤波器，其特性为使通带内的幅度响应最大限度地平坦，但同时损失截止频率处的下降斜度。在期望通带平滑的情况下，可使用butter函数。
butter函数的用法为：
[b,a]=butter(n,Wn,/ftype/)
其中n代表滤波器阶数，Wn代表滤波器的截止频率，这两个参数可使用buttord函数来确定。buttord函数可在给定滤波器性能的情况下，求出巴特沃斯滤波器的最小阶数n，同时给出对应的截止频率Wn。buttord函数的用法为：
[n,Wn]= buttord(Wp,Ws,Rp,Rs)
其中Wp和Ws分别是通带和阻带的拐角频率（截止频率），其取值范围为0至1之间。当其值为1时代表采样频率的一半。Rp和Rs分别是通带和阻带区的波纹系数。
不同类型（高通、低通、带通和带阻）滤波器对应的Wp和Ws值遵循以下规则：
1．高通滤波器：Wp和Ws为一元矢量且Wp>Ws；
2．低通滤波器：Wp和Ws为一元矢量且Wp<Ws；
3．带通滤波器：Wp和Ws为二元矢量且Wp<Ws，如Wp=[0.2,0.7],Ws=[0.1,0.8];
4．带阻滤波器：Wp和Ws为二元矢量且Wp>Ws，如Wp=[0.1,0.8],Ws=[0.2,0.7]。
二、契比雪夫I型IIR滤波器的设计
在期望通带下降斜率大的场合，应使用椭圆滤波器或契比雪夫滤波器。在MATLAB下可使用cheby1函数设计出契比雪夫I型IIR滤波器。
cheby1函数可设计低通、高通、带通和带阻契比雪夫I型滤IIR波器，其通带内为等波纹，阻带内为单调。契比雪夫I型的下降斜度比II型大，但其代价是通带内波纹较大。
cheby1函数的用法为：
[b,a]=cheby1(n,Rp,Wn,/ftype/)
在使用cheby1函数设计IIR滤波器之前，可使用cheblord函数求出滤波器阶数n和截止频率Wn。cheblord函数可在给定滤波器性能的情况下，选择契比雪夫I型滤波器的最小阶和截止频率Wn。
cheblord函数的用法为：
[n,Wn]=cheblord(Wp,Ws,Rp,Rs)
其中Wp和Ws分别是通带和阻带的拐角频率（截止频率），其取值范围为0至1之间。当其值为1时代表采样频率的一半。Rp和Rs分别是通带和阻带区的波纹系数。
3.4 实验内容
1．软件仿真实验：编写并调试MATLAB程序，选择不同形式，不同类型的4种滤波器进行仿真，记录幅频和相频特性，对比巴特沃斯滤波器和契比雪夫滤波器。
2．硬件实验：设计IIR滤波器，在计算机上观察冲激响应、幅频特性和相频特性，然后下载到实验箱。用示波器观察输入输出波形，测试滤波器的幅频响应特性。
3.5 MATLAB参考程序和仿真内容
%*******************************************************************%
%mode: 1--巴特沃斯低通；2--巴特沃斯高通；3--巴特沃斯带通；4--巴特沃斯带阻
% 5--契比雪夫低通；6--契比雪夫高通；7--契比雪夫带通；8--契比雪夫带阻
%fp1,fp2： 通带截止频率，当高通或低通时只有fp1有效
%fs1, fs2： 阻带截止频率，当高通或低通时只有fs1有效
%rp: 通带波纹系数
%as: 阻带衰减系数
%sample: 采样率
%h: 返回设计好的滤波器系数
%*******************************************************************%
function[b,a]=iirfilt(mode,fp1,fp2,fs1,fs2,rp,as,sample)
wp1=2*fp1/sample;wp2=2*fp2/sample;
ws1=2*fs1/sample;ws2=2*fs2/sample;
%得到巴特沃斯滤波器的最小阶数N和3bd频率wn
if mode<3[N,wn]=buttord(wp1,ws1,rp,as);
elseif mode<5[N,wn]=buttord([wp1 wp2],[ws1 ws2],rp,as);
%得到契比雪夫滤波器的最小阶数N和3bd频率wn
elseif mode<7[N,wn]=cheb1ord(wp1,ws1,rp,as);
else[N,wn]=cheblord([wp1 wp2],[ws1 ws2],rp,as);
end
%得到滤波器系数的分子b和分母a
if mode= =1[b,a]=butter(N,wn);end
if mode= =2[b,a]=butter(N,wn,/high/);end
if mode= =3[b,a]=butter(N,wn);end
if mode= =4[b,a]=butter(N,wn,/stop/);end
if mode= =5[b,a]=cheby1(N,rp,wn);end
if mode= =6[b,a]=cheby1(N,rp,wn,/high/);end
if mode= =7[b,a]=cheby1(N,rp,wn);end
if mode= =8[b,a]=cheby1(N,rp,wn,/stop/);end
set(gcf,/menubar/,menubar);
freq_response=freqz(b,a);
magnitude=20*log10(abs(freq_response));
m=0:511;
f=m*sample/(2*511);
subplot(3,1,1);plot(f,magnitude);grid; %幅频特性
axis([0 sample/2 1.1*min(magnitude) 1.1*max(magnitude)]);
ylabel('Magnitude');xlabel('Frequency-->');
phase=angle(freq_response);
subplot(3,1,2);plot(f,phase);grid; %相频特性
axis([0 sample/2 1.1*min(phase) 1.1*max(phase)]);
ylabel('Phase');xlabel('Frequency-->');
h=impz(b,a,32); %32点的单位函数响应
t=1:32;
subplot(3,1,3);stem(t,h);grid;
axis([0 32 1.2*min(h) 1.1*max(h)]);
ylabel('h(n)');xlabel('n-->');
%*******************************************************************%
假设需设计一个巴特沃斯低通IIR滤波器，通带截止频率为2KHz，阻带截止频率为3KHz，通带波纹系数为1，阻带衰减系数为20，采样频率为10KHz，则只需在MATLAB的命令窗口下键入：
[b,a]=iirfilt(1,2000,3000,2400,2600,1,20,10000)
程序进行模拟，并且按照如下顺序输出数字滤波器系统函数
的系数
b= b0 b1 ……bn
a= a0 a1 ……an
关于软件仿真实验内容，建议在完成大量仿真例子的基础上，选择能够体现实验要求的4个例子进行记录，系统函数只要记录系统的阶数。
3.6 硬件实验步骤
1．根据实验箱采样频率fs为10KHz的条件，用低频信号发生器产生一个频率合适的低频正弦信号，将其加到实验箱模拟通道1输入端，将示波器通道1探头接至模拟通道1输入端，通道2探头接至模拟通道2输出端。
2．在保证实验箱正确加电且串口电缆连接正常的情况下，运行数字信号处理与DSP应用实验开发软件，在“数字信号处理实验”菜单下选择“IIR滤波器”子菜单，出现提示信息。
3．输入滤波器类型、滤波器截止频率等参数后，分别点击“幅频特性”和“相频特性”按钮，在窗口右侧观察IIR滤波器的幅频特性和相频特性。此时提示信息将消失，如需查看提示信息，可点击“设计说明”按钮。
4．点击“下载实现”按钮，IIR滤波器开始工作，此时窗口右侧将显示IIR滤波器的幅频特性。
5．根据输入滤波器类型，更改低频信号源的频率，观察示波器上输入输出波形幅度的变化情况，测量IIR滤波器的幅频响应特性，看其是否与设计的幅频特性一致。
6．更改滤波器类型、滤波器截止频率等参数（共4种），重复步骤3至步骤5。所选择的例子参数最好和MATLAB仿真程序的例子一样。
7．用低频信号产生器产生一个500Hz的方波信号，分别设计3种滤波器，完成如下表要求的功能，并且记录参数和波形。
功 能
滤波器类型
参 数
输出波形
fp1
fp2
fs1
fs2
通过3次及以下次数的谐波
另外记录图形，并标图号
滤除5次及以下次数的谐波
通过3次到5次的谐波
3.7 思考题
1．在实验箱采样频率fs固定为10KHz的条件下，要观察方波信号频带宽度内的各个谐波分量，方波信号的频率最高不能超过多少，为什么？
2．硬件实验内容7中输出信号各个谐波分量，与原来方波信号同样谐波分量相比，有没有发生失真？主要发生了什么类型的失真？为什么？
4 窗函数法FIR滤波器设计实验
4.1 实验目的
1．通过实验加深对FIR滤波器基本原理的理解。
2．学习使用窗函数法设计FIR滤波器，了解窗函数的形式和长度对滤波器性能的影响。
4.2 实验仪器
1．YBLD智能综合信号源测试仪 1台
2．双踪示波器 1台
3．MCOM－TG305数字信号处理与现代通信技术实验箱 1台
4．PC机（装有MATLAB、MCOM－TG305配套实验软件） 1台
4.3 实验原理
数字滤波器的设计是数字信号处理中的一个重要内容。数字滤波器设计包括FIR（有限单位脉冲响应）滤波器与IIR（无限单位脉冲响应）滤波器两种。
与IIR滤波器相比，FIR滤波器在保证幅度特性满足技术要求的同时，很容易做到严格的线性相位特性。设FIR滤波器单位脉冲响应h(n)长度为N，其系统函数H（z）为：
H（z）是z－1的N－1次多项式，它在z平面上有N－1个零点，原点z=0是N－1阶重极点，因此H（z）是永远稳定的。稳定和线性相位特性是FIR滤波器突出的优点。
FIR滤波器的设计任务是选择有限长度的h(n)。使传输函数H( )满足技术要求。FIR滤波器的设计方法有多种，如窗函数法、频率采样法及其它各种优化设计方法，本实验介绍窗函数法的FIR滤波器设计。
窗函数法是使用矩形窗、三角窗、巴特利特窗、汉明窗、汉宁窗和布莱克曼窗等设计出标准响应的高通、低通、带通和带阻FIR滤波器。
一、firl函数的使用
在MATLAB下设计标准响应FIR滤波器可使用firl函数。firl函数以经典方法实现加窗线性相位FIR滤波器设计，它可以设计出标准的低通、带通、高通和带阻滤波器。firl函数的用法为：
b=firl(n,Wn,/ftype/,Window)
各个参数的含义如下：
b—滤波器系数。对于一个n阶的FIR滤波器，其n+1个滤波器系数可表示为：b(z)=b(1)+b(2)z－1+…+b(n+1)z－n。
n—滤波器阶数。
Wn—截止频率，0≤Wn≤1，Wn=1对应于采样频率的一半。当设计带通和带阻滤波器时，Wn=[W1 W2],W1≤ω≤W2。
ftype—当指定ftype时，可设计高通和带阻滤波器。Ftype=high时，设计高通FIR滤波器；ftype=stop时设计带阻FIR滤波器。低通和带通FIR滤波器无需输入ftype参数。
Window—窗函数。窗函数的长度应等于FIR滤波器系数个数，即阶数n+1。
二、窗函数的使用
在MATLAB下，这些窗函数分别为：
1．矩形窗：w=boxcar(n)，产生一个n点的矩形窗函数。
2．三角窗：w=triang(n)，产生一个n点的三角窗函数。
当n为奇数时，三角窗系数为w(k)=
当n为偶数时，三角窗系数为w(k)=
3．巴特利特窗：w=Bartlett(n)，产生一个n点的巴特利特窗函数。
巴特利特窗系数为w(k)=
巴特利特窗与三角窗非常相似。巴特利特窗在取样点1和n上总以零结束，而三角窗在这些点上并不为零。实际上，当n为奇数时bartlett(n)的中心n－2个点等效于triang(n－2)。
4．汉明窗：w=hamming(n)，产生一个n点的汉明窗函数。
汉明窗系数为w(k+1)=0.54－0.46cos（ ） k=0,…,n－1
5．汉宁窗：w=hanning(n)，产生一个n点的汉宁窗函数。
汉宁窗系数为w(k)=0.5[1－cos( )] k=1,…,n
6．布莱克曼窗：w=Blackman(n),产生一个n点的布莱克曼窗函数。
布莱克曼窗系数为w(k)=0.42－0.5cos(2π )+0.8cos（4π ）] k=1,…,n
与等长度的汉明窗和汉宁窗相比，布莱克曼窗的主瓣稍宽，旁瓣稍低。
7．凯泽窗：w=Kaiser(n,beta)，产生一个n点的凯泽窗数，其中beta为影响窗函数旁瓣的β参数，其最小的旁瓣抑制α与β的关系为:
0.1102(α－0.87) α>50
β= 0.5842(α－21)0.4+0.07886(α－21) 21≤α≤50
0 α<21
增加β可使主瓣变宽，旁瓣的幅度降低。
8．契比雪夫窗：w=chebwin(n,r)产生一个n点的契比雪夫窗函数。其傅里叶变换后的旁瓣波纹低于主瓣r个db数。
4.4 实验内容
1．软件仿真实验：编写并调试MATLAB程序，观察不同窗，不同类型滤波器不同点数等共4种FIR滤波器的h(n)，并记录幅频特性和相频特性。
2．硬件实验：用窗函数法设计标准响应的FIR滤波器，在计算机上观察窗函数幅频特性、幅频特性和相频特性，然后下载到实验箱。用示波器观察输入输出波形，测试滤波器的幅频响应特性。
4.5 MATLAB参考程序和仿真内容
%*******************************************************************%
%mode: 模式（1--高通；2--低通；3--带通；4--带阻）
%n: 阶数，加窗的点数为阶数加1
%fp: 高通和低通时指示截止频率，带通和带阻时指示下限频率
%fs: 带通和带阻时指示上限频率
%window:加窗（1--矩形窗；2--三角窗；3--巴特利特窗；4--汉明窗；
% 5--汉宁窗；6--布莱克曼窗；7--凯泽窗；8--契比雪夫窗）
%r: 代表加chebyshev窗的r值和加kaiser窗时的beta值
%sample: 采样率
%h: 返回设计好的FIR滤波器系数
%*******************************************************************%
%mode: 模式（1--高通；2--低通；3--带通；4--带阻）
%n: 阶数，加窗的点数为阶数加1
%fp: 高通和低通时指示截止频率，带通和带阻时指示下限频率
%fs:
⑻ DFT变换算法的全称
离散傅里叶变换(Discrete Fourier Transform,缩写为DFT),是傅里叶变换在时域和频域上都呈离散的形式,将信号的时域采样变换为其DTFT的频域描述了离散傅里叶变换的推导过程,是计算机相关算法编写的依据,;并且可因此推出快速傅里叶变换算法
⑼ 求FFT的c语言程序
快速傅里叶变换 要用C++ 才行吧 你可以用MATLAB来实现更方便点啊
此FFT 是用VC6.0编写，由FFT.CPP；STDAFX.H和STDAFX.CPP三个文件组成，编译成功。程序可以用文件输入和输出为文件。文件格式为TXT文件。测试结果如下：
输入文件：8.TXT 或手动输入
8 //N
1
2
3
4
5
6
7
8
输出结果为：或保存为TXT文件。（8OUT.TXT）
8
(36,0)
(-4,9.65685)
(-4,4)
(-4,1.65685)
(-4,0)
(-4,-1.65685)
(-4,-4)
(-4,-9.65685)
下面为FFT.CPP文件：
// FFT.cpp : 定义控制台应用程序的入口点。
#include "stdafx.h"
#include <iostream>
#include <complex>
#include <bitset>
#include <vector>
#include <conio.h>
#include <string>
#include <fstream>
using namespace std;
bool inputData(unsigned long &, vector<complex<double> >&); //手工输入数据
void FFT(unsigned long &, vector<complex<double> >&); //FFT变换
void display(unsigned long &, vector<complex<double> >&); //显示结果
bool readDataFromFile(unsigned long &, vector<complex<double> >&); //从文件中读取数据
bool saveResultToFile(unsigned long &, vector<complex<double> >&); //保存结果至文件中
const double PI = 3.1415926;
int _tmain(int argc, _TCHAR* argv[])
{
vector<complex<double> > vecList; //有限长序列
unsigned long ulN = 0; //N
char chChoose = ' '; //功能选择
//功能循环
while(chChoose != 'Q' && chChoose != 'q')
{
//显示选择项
cout << "\nPlease chose a function" << endl;
cout << "\t1.Input data manually, press 'M':" << endl;
cout << "\t2.Read data from file, press 'F':" << endl;
cout << "\t3.Quit, press 'Q'" << endl;
cout << "Please chose:";
//输入选择
chChoose = getch();
//判断
switch(chChoose)
{
case 'm': //手工输入数据
case 'M':
if(inputData(ulN, vecList))
{
FFT(ulN, vecList);
display(ulN, vecList);
saveResultToFile(ulN, vecList);
}
break;
case 'f': //从文档读取数据
case 'F':
if(readDataFromFile(ulN, vecList))
{
FFT(ulN, vecList);
display(ulN, vecList);
saveResultToFile(ulN, vecList);
}
break;
}
}
return 0;
}
bool Is2Power(unsigned long ul) //判断是否是2的整数次幂
{
if(ul < 2)
return false;
while( ul > 1 )
{
if( ul % 2 )
return false;
ul /= 2;
}
return true;
}
bool inputData(unsigned long & ulN, vector<complex<double> >& vecList)
{
//题目
cout<< "\n\n\n==============================Input Data===============================" << endl;
//输入N
cout<< "\nInput N:";
cin>>ulN;
if(!Is2Power(ulN)) //验证N的有效性
{
cout<< "N is invalid (N must like 2, 4, 8, .....), please retry." << endl;
return false;
}
//输入各元素
vecList.clear(); //清空原有序列
complex<double> c;
for(unsigned long i = 0; i < ulN; i++)
{
cout << "Input x(" << i << "):";
cin >> c;
vecList.push_back(c);
}
return true;
}
bool readDataFromFile(unsigned long & ulN, vector<complex<double> >& vecList) //从文件中读取数据
{
//题目
cout<< "\n\n\n===============Read Data From File==============" << endl;
//输入文件名
string strfilename;
cout << "Input filename:" ;
cin >> strfilename;
//打开文件
cout << "open file " << strfilename << "......." <<endl;
ifstream loadfile;
loadfile.open(strfilename.c_str());
if(!loadfile)
{
cout << "\tfailed" << endl;
return false;
}
else
{
cout << "\tsucceed" << endl;
}
vecList.clear();
//读取N
loadfile >> ulN;
if(!loadfile)
{
cout << "can't get N" << endl;
return false;
}
else
{
cout << "N = " << ulN << endl;
}
//读取元素
complex<double> c;
for(unsigned long i = 0; i < ulN; i++)
{
loadfile >> c;
if(!loadfile)
{
cout << "can't get enough infomation" << endl;
return false;
}
else
cout << "x(" << i << ") = " << c << endl;
vecList.push_back(c);
}
//关闭文件
loadfile.close();
return true;
}
bool saveResultToFile(unsigned long & ulN, vector<complex<double> >& vecList) //保存结果至文件中
{
//询问是否需要将结果保存至文件
char chChoose = ' ';
cout << "Do you want to save the result to file? (y/n):";
chChoose = _getch();
if(chChoose != 'y' && chChoose != 'Y')
{
return true;
}
//输入文件名
string strfilename;
cout << "\nInput file name:" ;
cin >> strfilename;
cout << "Save result to file " << strfilename << "......" << endl;
//打开文件
ofstream savefile(strfilename.c_str());
if(!savefile)
{
cout << "can't open file" << endl;
return false;
}
//写入N
savefile << ulN << endl;
//写入元素
for(vector<complex<double> >::iterator i = vecList.begin(); i < vecList.end(); i++)
{
savefile << *i << endl;
}
//写入完毕
cout << "save succeed." << endl;
//关闭文件
savefile.close();
return true;
}
void FFT(unsigned long & ulN, vector<complex<double> >& vecList)
{
//得到幂数
unsigned long ulPower = 0; //幂数
unsigned long ulN1 = ulN - 1;
while(ulN1 > 0)
{
ulPower++;
ulN1 /= 2;
}
//反序
bitset<sizeof(unsigned long) * 8> bsIndex; //二进制容器
unsigned long ulIndex; //反转后的序号
unsigned long ulK;
for(unsigned long p = 0; p < ulN; p++)
{
ulIndex = 0;
ulK = 1;
bsIndex = bitset<sizeof(unsigned long) * 8>(p);
for(unsigned long j = 0; j < ulPower; j++)
{
ulIndex += bsIndex.test(ulPower - j - 1) ? ulK : 0;
ulK *= 2;
}
if(ulIndex > p)
{
complex<double> c = vecList[p];
vecList[p] = vecList[ulIndex];
vecList[ulIndex] = c;
}
}
//计算旋转因子
vector<complex<double> > vecW;
for(unsigned long i = 0; i < ulN / 2; i++)
{
vecW.push_back(complex<double>(cos(2 * i * PI / ulN) , -1 * sin(2 * i * PI / ulN)));
}
for(unsigned long m = 0; m < ulN / 2; m++)
{
cout<< "\nvW[" << m << "]=" << vecW[m];
}
//计算FFT
unsigned long ulGroupLength = 1; //段的长度
unsigned long ulHalfLength = 0; //段长度的一半
unsigned long ulGroupCount = 0; //段的数量
complex<double> cw; //WH(x)
complex<double> c1; //G(x) + WH(x)
complex<double> c2; //G(x) - WH(x)
for(unsigned long b = 0; b < ulPower; b++)
{
ulHalfLength = ulGroupLength;
ulGroupLength *= 2;
for(unsigned long j = 0; j < ulN; j += ulGroupLength)
{
for(unsigned long k = 0; k < ulHalfLength; k++)
{
cw = vecW[k * ulN / ulGroupLength] * vecList[j + k + ulHalfLength];
c1 = vecList[j + k] + cw;
c2 = vecList[j + k] - cw;
vecList[j + k] = c1;
vecList[j + k + ulHalfLength] = c2;
}
}
}
}
void display(unsigned long & ulN, vector<complex<double> >& vecList)
{
cout << "\n\n===========================Display The Result=========================" << endl;
for(unsigned long d = 0; d < ulN;d++)
{
cout << "X(" << d << ")\t\t\t = " << vecList[d] << endl;
}
}
下面为STDAFX.H文件：
// stdafx.h : 标准系统包含文件的包含文件，
// 或是常用但不常更改的项目特定的包含文件
#pragma once
#include <iostream>
#include <tchar.h>
// TODO: 在此处引用程序要求的附加头文件
下面为STDAFX.CPP文件：
// stdafx.cpp : 只包括标准包含文件的源文件
// FFT.pch 将成为预编译头
// stdafx.obj 将包含预编译类型信息
#include "stdafx.h"
// TODO: 在 STDAFX.H 中
//引用任何所需的附加头文件，而不是在此文件中引用
⑽ 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;
}