当前位置:文档之家› 快速傅里叶变换(FFT)的DSP实现

快速傅里叶变换(FFT)的DSP实现

快速傅里叶变换(FFT)的DSP实现
快速傅里叶变换(FFT)的DSP实现

目录

一、前言

二、设计题目

三、设计要求

3.1 设计目的

3.2 设计要求

四、设计内容

五、设计原理

5.2 离散傅里叶变换DFT

5.3 快速傅里叶变换FFT

六、总体方案设计

6.1 设计有关程序流程图

6.2 在CCS环境下加载、调试源程序

七、主要参数

八、实验结果分析

九、设计总结

一、前言

随着数字电子技术的发展,数字信号处理的理论和技术广泛的应用于通讯、语音处理、计算机和多媒体等领域。快速傅里叶变换(FFT)使离散傅里叶变换的时间缩短了几个数量级。在数字信号处理领域被广泛的应用。FFT已经成为现代化信号处理的重要手段之一。

本次课程设计主要运用CCS这一工具。CCS(Code Composer Studio)是一种针对TM320系列DSP的集成开发环境,在Windows操作系统下,采用图形接口界面,提供环境配置、源文件编辑、程序调试、跟踪和分析等工具,可以帮助用户在一个软件环境下完成编辑、编译、链接、调试和数据分析等工作。

CCS有两种工作模式,即软件仿真器和硬件在线编程。软件仿真器工作模式可以脱离DSP芯片,在PC上模拟DSP的指令集和工作机制,主要用于前期算法实现和调试。硬件在线编程可以实时运行在DSP芯片上,与硬件开发板相结合进行在线编程和调试应用程序。二、设计题目

快速傅里叶变换(FFT)的DSP实现

三、设计要求

3.1设计目的

⑴加深对DFT算法原理和基本性质的理解;

⑵熟悉FFT的算法原理和FFT子程序的算法流程和应用;

⑶学习用FFT对连续信号和时域信号进行频谱分析的方法;

⑷学习DSP中FFT的设计和编程思想;

⑸学习使用CCS 的波形观察器观察波形和频谱情况; 3.2 基本要求

⑴研究FFT 原理以及利用DSP 实现的方法; ⑵编写FFT 程序; ⑶调试程序,观察结果。 四、 设计内容

⑴用DSP 汇编语言及C 语言进行编程; ⑵实现FFT 运算、对输入信号进行频谱分析。 五、 设计原理 快速傅里叶变换FFT

快速傅里叶变换(FFT )是一种高效实现离散傅里叶变换(DFT )的快速算法,是数字信号处理中最为重要的工具之一,它在声学,语音,电信和信号处理等领域有着广泛的应用。

5.1. 离散傅里叶变换DFT

对于长度为N 的有限长序列x(n),它的离散傅里叶变换(DFT )为

(1)

式中,

,称为旋转因子或蝶形因子。

从DFT 的定义可以看出,在x(n)为复数序列的情况下,对某个k 值,直接按(1)式计算X(k) 只需要N 次复数乘法和(N-1)次复数加法。因此,对所有N 个k 值,共需要N2次复数乘法和N(N-1)次复数加法。对于一些相当大有N 值(如1024点)来说,直接计算它的DFT 所需要的计算量是很大的,因此DFT 运算的应用受到了很大

1

,1,0,)()(1

-==

∑-=N k W

n x k X n n nk N

N

j N e

W /2π-=

的限制。

5.2.快速傅里叶变换FFT

旋转因子WN 有如下的特性。 对称性:

周期性:

利用这些特性,既可以使DFT 中有些项合并,减少了乘法积项,又可以将长序列的DFT 分解成几个短序列的DFT 。FFT 就是利用了旋转因子的对称性和周期性来减少运算量的。

FFT 的算法是将长序列的DFT 分解成短序列的DFT 。例如:N 为偶数时,先将N 点的DFT 分解为两个N/2点的DFT ,使复数乘法减少一半:再将每个N/2点的DFT 分解成N/4点的DFT ,使复数乘又减少一半,继续进行分解可以大大减少计算量。最小变换的点数称为基数,对于基数为2的FFT 算法,它的最小变换是2点DFT 。

一般而言,FFT 算法分为按时间抽取的FFT (DIT FFT)和按频率抽取的FFT(DIF FFT )两大类。DIF FFT 算法是在时域内将每一级输入序列依次按奇/偶分成2个短序列进行计算。而DIF FFT 算法是在频域内将每一级输入序列依次奇/偶分成2个短序列进行计算。两者的区别是旋转因子出现的位置不同,得算法是一样的。在DIF FFT 算法中,旋转因子 出现在输入端,而在DIF FFT 算法中

它出现在输入端。

假定序列x(n)的点数N 是2的幂,按照DIF FFT 算法可将其分为偶序列和奇序列。

2

/N k N

k N W W +-=N

k N

k

N

W W +=k

N

W

偶序列:

奇序列:

则x(n)的DFT 表示为

由于 ,则(3)式

可表示为

式中, 和分别为和的N/2的DFT 。

由于对称性,

则。因此,N

点可分为两部分: 前半部分: (4)

后半部分:

(5)

从式(4)和式(5)可以看出,只要求出0~N/2-1区间和的值,就可求出0~N-1区间的N 点值。

12/,1,0),2(2),-(N (4),(2),(0),1-==N r r x x x x x x 即12/,1,0),12(1),-(N (5),(3),(1),2-=+=N r r x x x x x x 即)

2()()()12()2()()()(1

2/0

221

2/0

211

2/0)12(1

2/0

21

1

-=-=-=+-=-=-=+=

++

=+

=

N r rk

N

k N

N r rk N

N r k

r N

N r rk N

N n nk

N

N n nk N

W r x W

W

r x W r x W r x n n W n x W

n x k X 为奇数

为偶数

[

][]

2

/)

2//(22

)/2(2N N j N j N

W e

e

W ===--ππ)

3(1

2/,1,0)

()()()()(211

2/0

2

/212/0

2/1-=+=+=

-=-=N k k X W k X W r x W

W

r x k X k

N N r rk

N k N

N r rk N )(1k X )(2k X )(1n x )(2n x ,

2

/K

N N k N

W W -=+)

()()2/(21k X W k X N k

X k

N -=+)(k X 1

2/,1,0)

()()(21-=+=N k k X W k X k X k

N 1

2/,1,0)

()()2/(21-=-=+N k k X W k X N k X k

N )(1k X )(2k X )(k X

以同样的方式进行抽取,可以求得N/4点的DFT ,重复抽取过程,就可以使N 点的DFT 用上组2点的 DFT 来计算,这样就可以大减少运算量。

基 2 DIF FFT 的蝶形运算如图(a)所示。设蝶形输入为和

,输出为和,则有

(6) (7)

在基数为2的FFT 中,设N=2M ,共有M 级运算,每级有N/2个2点FFT 蝶形运算,因此,N 点FFT 总共有个蝶形运算。

图(a) 基2 DIF FFT 的蝶形运算

例如:基数为2的FFT ,当N=8时,共需要3级,12个基2 DIT FFT 的蝶形运算。其信号流程如图(b)所示。

)(1p x m -)

(1q x m -)(p x m )(q x m k

N m m m W q x p x p x )()()(11--+=k

N

m m m W q x p x q x )()()(11---=N N 2log )2/()

(1q x m -)(p x m )

(1q x m -)(q x m

图(b) 8点基2 DIF FFT 蝶形运算

从图(b)可以看出,输入是经过比特反转的倒位序列,称为位码倒置,其排列顺序为。输出是按自然顺序排列,其顺序为。 六、 总体方案设计 6.1 设计程序流程图

)7(),3(),5(),1(),6(),2(),4(),0(x x x x x x x x )7(),6(,),1(),0(x x x x

6.2在CCS环境下加载、调试源程序

(1)起动CCS,在CCS中建立一个工程文件project\new\FFT,往工程文件里添加程序file\new\sourcefile.建立C源文件和一个命令文件,并将这两个文件添加到工程,再编译并装载程序:

阅读Dsp原理及应用中fft 用dsp实现的有关程序。

双击,启动CCS的仿真平台的配着选项。选择C5510 Simulator。Add加到my system ,按下save

(2)启动c5510后打开文件FFT.pjt.将编写好的源程序,和命令文件加载到文件FFT.pjt\Source.

(3)按下project\build调试程序,看其中是否有错误。

(4)无错后,Debug\run运行FFT.out程序。

(5)通过graph property dialog窗口,改变N点的值,得到不同的结果。

七.主要参数

进行N点FFT运算,分别实现N=256,N=512得到不同的功率谱图六.源程序:

Cmd源文件代码:

-f 0

-w

-stack 500

-sysstack 500

-l rts55.lib

MEMORY

{

DARAM: o=0x100, l=0x7f00

VECT:o=0x8000, l=0x100

DARAM2:o=0x8100,l=0x7f00

SARAM: o=0x10000,l=0x30000

SDRAM:o=0x40000,l=0x3e0000 }

SECTIONS

{

.text: {}>DARAM

.vectors: {}>VECT

.trcinit:{}>DARAM

.gblinit:{}>DARAM

.frt:{}>DARAM

.cinit:{}>DARAM

.pinit:{}>DARAM

.sysinit:{}>DARAM2

.far:{}>DARAM2

.const:{}>DARAM2

.switch:{}>DARAM2

.sysmem:{}>DARAM2

.cio:{}>DARAM2

.MEM$obj:{}>DARAM2

.sysheap:{}>DARAM2

.sysstack:{}>DARAM2

.stack:{}>DARAM2

.input:{}>DARAM2

.fftcode:{}>DARAM2

}

C文件源码:

#include "math.h"

#define sample_1 256

#define signal_1_f 60

#define signal_2_f 200

#define signal_sample_f 512

#define pi 3.1415926

int input[sample_1];

float fwaver[sample_1],fwavei[sample_1],w[sample_1]; float sin_tab[sample_1];

float cos_tab[sample_1];

void init_fft_tab();

void input_data();

void fft(float datar[sample_1],float datai[sample_1]); void main()

{

int i;

init_fft_tab();

input_data();

f or (i=0;i

{

fwaver[i]=input[i];

fwavei[i]=0.0f;

w[i]=0.0f;

}

fft(fwaver,fwavei);

while(1);

}

void init_fft_tab()

{

float wt1;

float wt2;

int i;

for (i=0;i

{

wt1=2*pi*i*signal_1_f;

wt1=wt1/signal_sample_f;

wt2=2*pi*i*signal_2_f;

wt2=wt2/signal_sample_f;

input[i]=(cos(wt1)+cos(wt2))/2*32768;

}

}

void input_data()

{

int i;

for(i=0;i

{

sin_tab[i]=sin(2*pi*i/sample_1);

cos_tab[i]=cos(2*pi*i/sample_1);

}

}

void fft(float datar[sample_1],float datai[sample_1]) {

int x0,x1,x2,x3,x4,x5,x6,x7,xx;

int i,j,k,b,p,L;

float TR,TI,temp;

for(i=0;i

{

x0=x1=x2=x3=x4=x5=x6=0;

x0=i&0x01;x1=(i/2)&0x01;x2=(i/4)&0x01;x3=(i/8)&0x01;

x4=(i/16)&0x01;x5=(i/32)&0x01;x6=(i/64)&0x01;x7=(i/128)&0x01;

xx=x0*128+x1*64+x2*32+x3*16+x4*8+x5*4+x6*2+x7;

datai[xx]=datar[i];

}

for(i=0;i

{

datar[i]=datai[i];datai[i]=0;

}

for(L=1;L<=8;L++)

{

b=1;i=L-1;

while(i>0)

{

b=b*2;i--;

}

for(j=0;j<=b-1;j++)

{

p=1;i=8-L;

while(i>0)

{

p=p*2;i--;

}

p=p*j;

for(k=j;k<256;k=k+2*b)

{

TR=datar[k];TI=datai[k];temp=datar[k+b];

datar[k]=datar[k]+datar[k+b]*cos_tab[p]+datai[k+b]*sin_tab[p];

datai[k]=datai[k]-datar[k+b]*sin_tab[p]+datai[k+b]*cos_tab[p];

datar[k+b]=TR-datar[k+b]*cos_tab[p]-datai[k+b]*sin_tab[p];

datai[k+b]=TI+temp*sin_tab[p]-datai[k+b]*cos_tab[p];

}

}

}

for(i=0;i

{

w[i]=sqrt(datar[i]*datar[i]+datai[i]*datai[i]);

}

}

八、实验结果及分析

作图,得到输入信号的功率图谱。

2)FFT变换结果图

3)改变信号的频率可以再做次实验。

FFT 算法特点:()

共需次迭代; 第

次迭代对偶结点的偶距为

,因此一组结

点覆盖的序号个数是。

次迭代结点的组数为。

可以预先计算好,而且的变化范围是

r

N 2

=r )

1(r L L ≤≤L

L

r L L N K K 2

/2

==--1

2

)(2-=

-L L L N K K )

1(r L L ≤≤[

]

1

2

)(2/-=-L L L K K N L

P

N W L

P 1

2~

0-N

因此N越大,运算越多。

九、设计总结

通过这次课程设计,我获得了很多。一开始对DSP这个概念很陌生,对于其中的内容更是一知半解。我只知道这门学科应该很有用,但是不知道该如何去把握它,认识它。这次课程设计,让我对DSP有了更进一步的了解。对FFT算法有了新的认识,对其原理和基本性质做了回顾,为以后深入的学习奠定了基础。这次课程设计,我觉得最有意义的就是掌握了一定的DSP系统的软件设计能力。而且还了解了CCS的组成与基本功能。掌握了它的安装、配置、基本操作、工程项目的建立和调试等。希望在以后的应用中能学到更多的知识,并将它们运用到实践中去。

FFT超全快速傅里叶

快速傅里叶变换 FFT是离散傅立叶变换的快速算法,可以将一个信号变换到频域。有些信号在时域上是很难看出什么特征的,但是如果变换到频域之后,就很容易看出特征了。这就是很多信号分析采用FFT变换的原因。另外,FFT可以将一个信号的频谱提取出来,这在频谱分析方面也是经常用的。 虽然很多人都知道FFT是什么,可以用来做什么,怎么去做,但是却不知道FFT之后的结果是什意思、如何决定要使用多少点来做FFT。 现在圈圈就根据实际经验来说说FFT结果的具体物理意义。一个模拟信号,经过ADC采样之后,就变成了数字信号。采样定理告诉我们,采样频率要大于信号频率的两倍,这些我就不在此罗嗦了。 采样得到的数字信号,就可以做FFT变换了。N个采样点,经过FFT之后,就可以得到N个点的FFT结果。为了方便进行FFT运算,通常N取2的整数次方。 假设采样频率为Fs,信号频率F,采样点数为N。那么FFT之后结果就是一个为N点的复数。每一个点就对应着一个频率点。这个点的模值,就是该频率值下的幅度特性。具体跟原始信号的幅度有什么关系呢?假设原始信号的峰值为A,那么FFT的结果的每个点(除了第一个点直流分量之外)的模值就是A的N/2倍。而第一个点就是直流分量,它的模值就是直流分量的N倍。而每个点的相位呢,就是在该频率下的信号的相位。第一个表示直流分量(即0Hz),而最后一个点N的再下一个点(实际上这个点是不存在的,这里是假设的第N+1个点,也可以看做是将第一个点分做两半分,另一半移到最后)则表示 采样频率Fs,这中间被N-1个点平均分成N等份,每个点的频率依次增加。例如某点n所表示的频率为:Fn=(n-1)*Fs/N。由上面的公式可以看出,Fn所能分辨到频率为为Fs/N,如果采样频率Fs为1024Hz,采样点数为1024点,则可以分辨到1Hz。1024Hz的采样率采样1024点,刚好是1秒,也就是说,采样1秒时间的信号并做FFT,则结果可以分析到1Hz,如果采样2秒时间的信号并做FFT,则结果可以分析到0.5Hz。如果要提高

快速傅里叶变换(FFT)课程设计

快速傅里叶变换(FFT)的DSP 实现 (马灿明 计算机学院 计算机应用技术 2110605410) 摘要:本文对快速傅里叶变换(FFT)原理进行简单介绍后,然后介绍FFT 在TMS320C55xx 定 点DSP 上的实现,FFT 算法采用C 语言和汇编混合编程来实现,算法程序利用了CCS 对其结果进行了仿真。 关键字:FFT ,DSP ,比特反转 1.引言 傅里叶变换是将信号从时域变换到频域的一种变换形式,是信号处理领域中一种重要的分析工具。离散傅里叶变换(DFT )是连续傅里叶变换在离散系统中的表现形式。由于DFT 的计算量很大,因此在很长一段时间内使其应用受到很大的限制。 20世纪60年代由Cooley 和Tukey 提出了快速傅里叶变换(FFT )算法,它是快速计算DFT 的一种高效方法,可以明显地降低运算量,大大地提高DFT 的运算速度,从而使DFT 在实际中得到了广泛的应用,已成为数字信号处理最为重要的工具之一。 DSP 芯片的出现使FFT 的实现变得更加方便。由于多数的DSP 芯片都能在单指令周期内完成乘法—累加运算,而且还提供了专门的FFT 指令(如实现FFT 算法所必需的比特反转等),使得FFT 算法在DSP 芯片上实现的速度更快。本节首先简要介绍FFT 算法的基本原理,然后介绍FFT 算法的DSP 实现。 2.FFT 算法的简介 快速傅里叶变换(FFT )是一种高效实现离散傅里叶变换(DFT )的快速算法,是数字信号处理中最为重要的工具之一,它在声学,语音,电信和信号处理等领域有着广泛的应用。 2.1离散傅里叶变换DFT 对于长度为N 的有限长序列x(n),它的离散傅里叶变换(DFT )为 1,1,0, )()(1 0-==∑-=N k W n x k X n n nk N (1) 式中, N j N e W /2π-= ,称为旋转因子或蝶形因子。 从DFT 的定义可以看出,在x(n)为复数序列的情况下,对某个k 值,直接按(1) 式计算X(k) 只需要N 次复数乘法和(N-1)次复数加法。因此,对所有N 个k 值,共需要N 2 次复数乘法和N(N-1)次复数加法。对于一些相当大有N 值(如1024点)来说,直接计算它的DFT 所需要的计算量是很大的,因此DFT 运算的应用受到了很大的限制。 2.2快速傅里叶变换FFT 旋转因子W N 有如下的特性。 。对称性: 2/N k N k N W W +-= 。周期性: N k N k N W W += 利用这些特性,既可以使DFT 中有些项合并,减少了乘法积项,又可以将长序列的DFT

详解FFT(快速傅里叶变换FFT.

kn N W N N 第四章 快速傅里叶变换 有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长 序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换 (FFT). 1965 年,Cooley 和 Tukey 提出了计算离散傅里叶变换(DFT )的快 速算法,将 DFT 的运算量减少了几个数量级。从此,对快速傅里叶变换(FFT ) 算法的研究便不断深入,数字信号处理这门新兴学科也随 FFT 的出现和发 展而迅速发展。根据对序列分解与选取方法的不同而产生了 FFT 的多种算 法,基本算法是基2DIT 和基2DIF 。FFT 在离散傅里叶反变换、线性卷积 和线性相关等方面也有重要应用。 快速傅里叶变换(FFT )是计算离散傅里叶变换(DFT )的快速算法。 DFT 的定义式为 N ?1 X (k ) = ∑ x (n )W N R N (k ) n =0 在所有复指数值 W kn 的值全部已算好的情况下,要计算一个 X (k ) 需要 N 次复数乘法和 N -1 次复数加法。算出全部 N 点 X (k ) 共需 N 2 次复数乘法 和 N ( N ? 1) 次复数加法。即计算量是与 N 2 成正比的。 FFT 的基本思想:将大点数的 DFT 分解为若干个小点数 DFT 的组合, 从而减少运算量。 W N 因子具有以下两个特性,可使 DFT 运算量尽量分解为小点数的 DFT 运算: (1) 周期性: ( k + N ) n N = W kn = W ( n + N ) k (2) 对称性:W ( k + N / 2 ) = ?W k N N 利用这两个性质,可以使 DFT 运算中有些项合并,以减少乘法次数。例子: 求当 N =4 时,X(2)的值

fft快速傅里叶变换 c语言实现

#include #include #include #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:\n"); scanf("%d",&size_x); printf("Please input the data in x[N]:\n"); for(i=0;i

实验四 快速傅里叶变换(FFT)

实验四 快速傅里叶变换(FFT ) 4.1实验目的 1)加深对快速傅里叶变换(FFT )基本理论的理解; 2)了解使用快速傅里叶变换(FFT )计算有限长序列和无限长序列信号频谱的方法; 3)掌握用MATLAB 语言进行快速傅里叶变换时常用的子函数。 4.2实验原理 1)用MATLAB 提供的子函数进行快速傅里叶变换 从理论学习可知,DFT 是唯一在时域和频域均为离散序列的变换方法,它适用于有限长序列。尽管这种变换方法是可以用于数值计算的,但如果只是简单的按照定义进行数据处理,当序列长度很大时,则将占用很大的内存空间,运算时间将很长。 快速傅里叶变换是用于DFT 运算的高效运算方法的统称,FFT 只是其中的一种。FFT 主要有时域抽取算法和频域抽取算法,基本思想是将一个长度为N 的序列分解成多个短序列,如基2算法、基4算法等,大大缩短了运算的时间。 MATLAB 中提供了进行快速傅里叶变换(FFT )的子函数,用fft 计算DFT ,用ifft 计算IDFT 。 2)用FFT 计算有限长序列的频谱 基本概念: 一个序号从1n 到2n 的时域有限长序列()x n ,它的频谱()j X e ω定义为它的离散时间傅里叶变换,且在奈奎斯特(Nyquist )频率范围内有界并连续。序列的长度为N ,则211N n n =?+。计算()x n 的离散傅里叶变换(DFT )得到的是()j X e ω的N 个样本点()k j X e ω。其中数字频率为 k 2πω()d ωk k N == 式中:d ω为数字频率的分辨率;k 取对应-(N -1)/2到(N -1)/2区间的整数。 在实际使用中,往往要求计算出信号以模拟频率为横坐标的频谱,此时对应的模拟频率为 s s 2π2π?ω/T ()()T k k k k kD N L ==== 式中:D 为模拟频率的分辨率或频率间隔;T s 为采样信号的周期,Ts =1/Fs ;定义信号时域长度L =N T s 。

快速傅里叶变换(FFT)试题

第一章 快速傅里叶变换(FFT ) 4.1 填空题 (1)如果序列)(n x 是一长度为64点的有限长序列)630(≤≤n ,序列)(n h 是一长度为128点 的有限长序列)1270 (≤≤n ,记)()()(n h n x n y *=(线性卷积),则)(n y 为 点的序列,如果 采用基FFT 2算法以快速卷积的方式实现线性卷积,则FFT 的点数至少为 点。 解:64+128-1=191点; 256 (2)如果一台通用机算计的速度为:平均每次复乘需100s μ,每次复加需20s μ,今用来计算N=1024点的DFT )]([n x 。问直接运算需( )时间,用FFT 运算需要( )时间。 解:①直接运算:需复数乘法2 N 次,复数加法) (1-N N 次。 直接运算所用计算时间1T 为 s s N N N T 80864.12512580864020110021==?-+?=μ)( ② 基2FFT 运算:需复数乘法 N N 2log 2 次,复数加法N N 2log 次。 用FFT 计算1024点DTF 所需计算时间2T 为 s s N N N N T 7168.071680020log 100log 2 222==?+?=μ。 (3)快速傅里叶变换是基于对离散傅里叶变换 和利用旋转因子k N j e π2-的 来减少计算量,其特点是 _______、_________和__________。 解:长度逐次变短;周期性;蝶形计算、原位计算、码位倒置 (4)N 点的FFT 的运算量为复乘 、复加 。 解:N N L N mF 2log 2 2== ;N N NL aF 2log == 4.2 选择题 1.在基2DIT —FFT 运算中通过不断地将长序列的DFT 分解成短序列的DFT ,最后达到2点DFT 来降低运算量。若有一个64点的序列进行基2DIT —FFT 运算,需要分解 次,方能完成运算。 A.32 B.6 C.16 D. 8 解:B 2.在基2 DIT —FFT 运算时,需要对输入序列进行倒序,若进行计算的序列点数N=16,倒序前信号点序号为8,则倒序后该信号点的序号为 。 A. 8 B. 16 C. 1 D. 4 解:C 3.在时域抽取FFT 运算中,要对输入信号x(n)的排列顺序进行“扰乱”。在16点FFT 中,原来x(9)

快速傅里叶变换(FFT)的原理及公式

快速傅里叶变换(FFT)的原理及公式 原理及公式 非周期性连续时间信号x(t)的傅里叶变换可以表示为 式中计算出来的是信号x(t)的连续频谱。但是,在实际的控制系统中能够得到的是连续信号x(t)的离散采样值x(nT)。因此需要利用离散信号x(nT)来计算信号x(t)的频谱。 有限长离散信号x(n),n=0,1,…,N-1的DFT定义为: 可以看出,DFT需要计算大约N2次乘法和N2次加法。当N较大时,这个计算量是很大的。利用WN的对称性和周期性,将N点DFT分解为两个N/2点 的DFT,这样两个N/2点DFT总的计算量只是原来的一半,即(N/2)2+(N/2)2=N2/2,这样可以继续分解下去,将N/2再分解为N/4点DFT等。对于N=2m点的DFT都可以分解为2点的DFT,这样其计算量可以减少为(N/2)log2N 次乘法和Nlog2N次加法。图1为FFT与DFT-所需运算量与计算点数的关系曲线。由图可以明显看出FFT算法的优越性。 将x(n)分解为偶数与奇数的两个序列之和,即

x1(n)和x2(n)的长度都是N/2,x1(n)是偶数序列,x2(n)是奇数序列,则 其中X1(k)和X2(k)分别为x1(n)和x2(n)的N/2点DFT。由于X1(k)和X2(k)均以N/2为周期,且WN k+N/2=-WN k,所以X(k)又可表示为: 上式的运算可以用图2表示,根据其形状称之为蝶形运算。依此类推,经过m-1次分解,最后将N点DFT分解为N/2个两点DFT。图3为8点FFT的分解流程。 FFT算法的原理是通过许多小的更加容易进行的变换去实现大规模的变换,降低了运算要求,提高了与运算速度。FFT不是DFT的近似运算,它们完全是等效的。 关于FFT精度的说明: 因为这个变换采用了浮点运算,因此需要足够的精度,以使在出现舍入误差时,结果中的每个组成部分的准确整数值仍是可辨认的。为了FFT的舍入误差,应该允许增加几倍log2(log2N)位的二进制。以256为基数、长度为N字节的数

快速傅里叶变换FFT原理与实现

FFT原理与实现 2010-10-07 21:10:09| 分类:数字信号处理 | 标签:fft dft |举报|字号订阅 在数字信号处理中常常需要用到离散傅立叶变换(DFT),以获取信号的频域特征。尽管传统的DFT算法能够获取信号频域特征,但是算法计算量大,耗时长,不利于计算机实时对信号进行处理。因此至DFT被发现以来,在很长的一段时间内都不能被应用到实际的工程项目中,直到一种快速的离散傅立叶计算方法——FFT,被发现,离散傅立叶变换才在实际的工程中得到广泛应用。需要强调的是,FFT并不是一种新的频域特征获取方式,而是DFT的一种快速实现算法。本文就FFT的原理以及具体实现过程进行详尽讲解。 DFT计算公式 本文不加推导地直接给出DFT的计算公式: 其中x(n)表示输入的离散数字信号序列,WN为旋转因子,X(k)为输入序列x(n)对应的N个离散频率点的相对幅度。一般情况下,假设x(n)来自于低通采样,采样频率为fs,那么X(k)表示了从-fs/2率开始,频率间隔为fs/N,到fs/2-fs/N截至的N个频率点的相对幅度。因为DFT计算得到的一组离散频率幅度值实际上是在频率轴上从成周期变化的,即X(k+N)=X(k)。因此任意取连续的N个点均可以表示DFT的计算效果,负频率成分比较抽象,难于理解,根据X(k)的周期特性,于是我们又可以认为X(k)表示了从零频率开始,频率间隔为fs/N,到fs-fs/N 截至的N个频率点的相对幅度。 N点DFT的计算量

根据(1)式给出的DFT计算公式,我们可以知道每计算一个频率点X(k)均需要进行N次复数乘法和N-1次复数加法,计算N各点的X(k)共需要N^2次复数乘法和N*(N-1)次复数加法。当x(n)为实数的情况下,计算N点的DFT需要2*N^2次实数乘法,2*N*(N-1)次实数加法。 旋转因子WN的特性 1.WN的对称性 2.WN的周期性 3.WN的可约性 根据以上这些性质,我们可以得到式(5)的一系列有用结果 基-2 FFT算法推导 假设采样序列点数为N=2^L,L为整数,如果不满足这个条件可以人为地添加若干个0以使采样序列点数满足这一要求。首先我们将序列x(n)按照奇偶分为两组如下: 于是根据DFT计算公式(1)有:

详解FFT(快速傅里叶变换FFT

kn N W N N 第四章 快速傅里叶变换 有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长 序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换 (FFT). 1965 年,Cooley 和 Tukey 提出了计算离散傅里叶变换(DFT )的快 速算法,将 DFT 的运算量减少了几个数量级。从此,对快速傅里叶变换(FFT ) 算法的研究便不断深入,数字信号处理这门新兴学科也随 FFT 的出现和发 展而迅速发展。根据对序列分解与选取方法的不同而产生了 FFT 的多种算 法,基本算法是基2DIT 和基2DIF 。FFT 在离散傅里叶反变换、线性卷积 和线性相关等方面也有重要应用。 快速傅里叶变换(FFT )是计算离散傅里叶变换(DFT )的快速算法。 DFT 的定义式为 N ?1 X (k ) = ∑ x (n )W N R N (k ) n =0 在所有复指数值 W kn 的值全部已算好的情况下,要计算一个 X (k ) 需要 N 次复数乘法和 N -1 次复数加法。算出全部 N 点 X (k ) 共需 N 2 次复数乘法 和 N ( N ? 1) 次复数加法。即计算量是与 N 2 成正比的。 FFT 的基本思想:将大点数的 DFT 分解为若干个小点数 DFT 的组合, 从而减少运算量。 W N 因子具有以下两个特性,可使 DFT 运算量尽量分解为小点数的 DFT 运算: (1) 周期性: ( k + N ) n N = W kn = W ( n + N ) k (2) 对称性:W ( k + N / 2 ) = ?W k N N 利用这两个性质,可以使 DFT 运算中有些项合并,以减少乘法次数。例子: 求当 N =4 时,X(2)的值

快速傅里叶变换的原理及其应用

快速傅里叶变换的原理及其应用 摘要: 快速傅氏变换(FFT),是离散傅氏变换的快速算法,它是根据离散傅氏变换的奇、偶、虚、实等特性,对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现,但是对于在计算机系统或者说数字系统中应用离散傅立叶变换,可以说是进了一大步。傅里叶变换的理论与方法在“数理方程”、“线性系统分析”、“信号处理、仿真”等很多学科领域都有着广泛应用,由于计算机只能处理有限长度的离散的序列,所以真正在计算机上运算的是一种离散傅里叶变换. 虽然傅里叶运算在各方面计算中有着 重要的作用,但是它的计算过于复杂,大量的计算对于系统的运算负担过于庞大,使得一些对于耗电量少,运算速度慢的系统对其敬而远之,然而,快速傅里叶变换的产生,使得傅里叶变换大为简化,在不牺牲耗电量的条件下提高了系统的运算速度,增强了系统的综合能力,提高了运算速度,因此快速傅里叶变换在生产和生活中都有着非常重要的作用,对于学习掌握都有着非常大的意义。 关键词:快速傅氏变换;图像处理;matlab 前言: 傅里叶变换在信号处理中具有十分重要的作用,但是基于离散时间的傅里叶变换具有很大的时间复杂度,根据傅里叶变换理论,对一个有限长度且 长度为N的离散信号,做傅里叶变换的时间复杂度为) O,当N很大时τ, (2 N 其实现的时间是相当惊人的(比如当N为4 10 10时,其完成时间为τ8 (τ为计算机的时钟周期)),故其实现难度是相当大的,同时也严重制约了DFT在信号分析中的应用,故需要提出一种快速的且有效的算法来实 现。正是鉴于DFT极其复杂的时间复杂度,1965年..JWCooley 和..JWTukey巧妙地利用 NW因子的周期性和对称性,提出了一个DFT的快速算法,即快速傅里叶变换(FFT),从而使得DFT在信号处理中才得到真正的广泛应用。 傅立叶变化的原理; (1)原理

快速傅里叶变换(FFT)原理及源程序

《测试信号分析及处理》课程作业 快速傅里叶变换 一、程序设计思路 快速傅里叶变换的目的是减少运算量,其用到的方法是分级进行运算。全部计算分解为M 级,其中N M 2log =;在输入序列()i x 中是按码位倒序排列的,输出序列()k X 是按顺序排列;每级包含2N 个蝶形单元,第i 级有i N 2 个群,每个群有12-i 个蝶形单元; 每个蝶形单元都包含乘r N W 和r N W -系数的运算,每个蝶形 单元数据的间隔为12-i ,i 为第i 级; 同一级中各个群的系数W 分布规律完全相同。 将输入序列()i x 按码位倒序排列时,用到的是倒序算法——雷德算法。 自然序排列的二进制数,其下面一个数总比上面的数大1,而倒序二进制数的下面一个数是上面一个数在最高位加1并由高位向低位仅为而得到的。 若已知某数的倒序数是J ,求下一个倒序数,应先判断J 的最高位是否为0,与2 N k =进行比较即可得到结果。如果J k >,说明最高位为0,应把其变成1,即2 N J +,这样就得到倒序数了。如果J k ≤,即J 的最高位为1,将最高位化为0,即2N J -,再判断次高位;与4N k =进行比较,若为0,将其变位1,即4 N J +,即得到倒序数,如果次高位为1,将其化为0,再判断下一位……即从高位到低位依次判断其是否为1,为1将其变位0,若这一位为0,将其变位1,即可得到倒序数。若倒序数小于顺序数,进行换位,否则不变,防治重复交换,变回原数。 注:因为0的倒序数为0,所以可从1开始进行求解。 二、程序设计框图 (1)倒序算法——雷德算法流程图

(2)FFT算法流程

快速傅里叶变换fft变换

快速傅里叶变换FFT的C语言算法彻底研究LED音乐频谱显示的核心算法就是快速傅里叶变换,FFT的理解和编程还是比较难的,特地撰写此文分享一下研究成果。 一、彻底理解傅里叶变换 快速傅里叶变换(Fast Fourier Transform)是离散傅里叶变换的一种快速算法,简称FFT,通过FFT可以将一个信号从时域变换到频域。模拟信号经过A/D转换变为数字信号的过程称为采样。为保证采样后信号的频谱形状不失真,采样频率必须大于信号中最高频率成分的2倍,这称之为采样定理。假设采样频率为fs,采样点数为N,那么FFT结果就是一个N点的复数,每一个点就对应着一个频率点,某一点n(n 从1开始)表示的频率为:fn=(n-1)*fs/N。举例说明:用1kHz的采样频率采样128点,则FFT结果的128个数据即对应的频率点分别是0,1k/128,2k/128,3k/128,…,127k/128 Hz。这个频率点的幅值为:该点复数的模值除以N/2(n=1时是直流分量,其幅值是该点的模值除以N)。 二、傅里叶变换的C语言编程 1、对于快速傅里叶变换FFT,第一个要解决的问题就是码位倒序。假设一个N 点的输入序列,那么它的序号二进制数位数就是t=log2N.码位倒序要解决两个问题:①将t位二进制数倒序;②将倒序后的两个存储单元进行交换。如果输入序列的自然顺序号i用二进制数表示,例如若最大序号为15,即用4位就可表示n3n2n1n0,则其倒序后j对应的二进制数就是n0n1n2n3,那么怎样才能实现倒序呢?利用C语言的移位功能! 程序如下,我不多说,看不懂者智商一定在180以下!复数类型定义及其运算#define N 64 //64点 #define log2N 6 //log2N=6 /*复数类型*/ typedef struct { float real; float img; }complex; complex xdata x[N]; //输入序列 /*复数加法*/ complex add(complex a,complex b) { complex c; c.real=a.real+b.real; c.img=a.img+b.img; return c; } /*复数减法*/ complex sub(complex a,complex b) { complex c; c.real=a.real-b.real;

相关主题
文本预览
相关文档 最新文档