快速傅立叶变换(FFT)算法实验

实验四 快速傅立叶变换（FFT ）算法实验

一、实验目的

1．进一步熟悉DSP 的DSP/BIOS 系统 2．掌握FFT 算法的基本原理

3．掌握FFT 算法在DSP 中的基本实现方法

二、实验设备

1．具有USB 接口的PC 机一台 2．USB 仿真器一台

3．ARM/DSP/FPGA 实验箱一台

三、实验原理

本实验是在我们已经掌握DSP/BIOS 开发平台以及如何正确操作AIC23的基础上，进一步学习FFT 算法在DSP 中的实现方法，并通过实验系统中产生的模拟波形，查看FFT 以后的波形图。

傅里叶变换是一种将信号从时域变换到频域的变换形式，是信号处理的重要分析工具。离散傅里叶变换（DFT ）是傅里叶变换在离散系统中的表示形式。但是DFT 的计算量非常大， FFT 就是DFT 的一种快速算法, FFT 将DFT 的N 2 步运算减少至 ( N/2 )log 2N 步。

离散信号x(n)的傅里叶变换可以表示为

∑=-=1

0][)(N N nk N W n x k X ， N

j N e W /2π-=

式中的W N 称为蝶形因子，利用它的对称性和周期性可以减少运算量。一般而言，

FFT 算法分为时间抽取（DIT ）和频率抽取（DIF ）两大类。两者的区别是蝶形因子出现的位置不同，前者中蝶形因子出现在输入端，后者中出现在输出端。本实验以时间抽取方法为例。

时间抽取FFT 是将N 点输入序列x(n) 按照偶数项和奇数项分解为偶序列和奇序列。偶序列为：x(0), x(2), x(4),…, x(N-2)；奇序列为：x(1), x(3), x(5),…, x(N-1)。这样x(n) 的N 点DFT 可写成：

()()∑++∑=-=+-=1

2/0

)12(1

2/0

2122)(N n k

n N N n nk N

W n x W

n x k X 考虑到W N 的性质，即

2/)2//(22/)2(2][N N j N j N W e e W ===--ππ

因此有：

()()∑++∑=-=-=1

2/0

2/1

2/0

2

/122)(N n nk

N k N

N n nk

N W n x W

W

n x k X 或者写成：

()()k Z W k Y k X k

N +=)(

由于Y(k) 与Z(k) 的周期为N/2，并且利用W N 的对称性和周期性，即：

k

N N k N W W -=+2/

可得：

()()k Z W k Y N k X k

N -=+)2/(

对Y(k) 与Z(k) 继续以同样的方式分解下去，就可以使一个N 点的DFT 最终用

一组2点的DFT 来计算。在基数为2的FFT 中，总共有log 2(N) 级运算，每级中有N/2 个2点FFT 蝶形运算。

单个蝶形运算示意图如图4.10.1

所示。

图4-1 单个蝶形运算示意图

以N ＝8为例，时间抽取FFT 的信号流图如图4.10.2所示。

W 0

W 0

W

2

W 0

W

2

W 0W 1W 2W 3

x(0)

x(4)

x(2)

x(6)x(1)

x(5)

x(3)

x(7)

X(7)

X(6)X(5)X(4)X(3)X(2)

X(1)X(0)W 0

W 0

W 0

图4-2 8点FFT 信号流图

从上图可以看出，输出序列是按自然顺序排列的，而输入序列的顺序则是“比特反转”方式排列的。也就是说，将序号用二进制表示，然后将二进制数以相反方向排列，再以这个数作为序号。如011变成110，那么第3个输入值和第六个输入值就要交换位置了。本实验中采用了一种比较常用有效的方法完成这一步工作——雷德算法。

四、实验内容 五、实验步骤

第一步骤：新建项目FFT.pjt及编写定时中断文件（ FFT.c ，FFTcfg.cmd），在对各个文件进行编译及运行，其文件分别如下。

/**********************************************/

/* Title: FFT.c */

/* Author: ZZH */

/* Data: 2010-12-5 */

/**********************************************/

#include "FFTcfg.h"

#include "FPGA.h"

#include

#define N 128

#define LOGN 7

#define LR_PATH 1 //0:左声道 1：右声道

#define pi 3.14159

/***********************************************/

void Delay(Int32 num1,Int32 num2);

void AIC23_Init(void);

/***********************************************/

float Data_Buff[N];

float Dr[N], Di[N];

float Result_Buff[N];

float Temp;

float Wr, Wi; /* 蝶形因子 */

float Tr, Ti, Vr, Vi; /* 临时变量 */

unsigned short Save_Index;

unsigned short FFT_Enable;

unsigned short i,j,k;

unsigned short n,m,a,b,c;

/***********************************************/

void main()

{

HWI_disable();

Save_Index = 0;

FFT_Enable = FALSE;

FPGA_RST = 1; //复位FPGA内部所有寄存器

MCBSP1_SREG = 2; //将AIC23的数据接口映射到McBSP1

AIC23_SREG = 2; //将McBSP1映射到AIC23的控制接口

AIC23_Init();

C54_enableIMR(0x0400);

HWI_enable();

while(1);

}

/***********************************************/

void Delay(Int32 num1,Int32 num2)

{

Int32 i,j;

for(i=0; i

for(j=0; j

}

void AIC23_Init(void)

{

MCBSP_start(hMcbsp0, MCBSP_XMIT_START|

MCBSP_SRGR_START|

MCBSP_SRGR_FRAMESYNC,

0x200); //允许串口1发送数据

//初始化AIC23

while(!MCBSP_xrdy(hMcbsp0));

MCBSP_write16(hMcbsp0, 0x1e00); //AIC23复位

Delay(100,100);

while(!MCBSP_xrdy(hMcbsp0));

MCBSP_write16(hMcbsp0, 0x0c00); //Line In，POWER、CLOCK、OSC、OUT、DAC、ADC，MIC全部打开

while(!MCBSP_xrdy(hMcbsp0));

MCBSP_write16(hMcbsp0, 0x0017); //Left line input channel volume control

while(!MCBSP_xrdy(hMcbsp0));

MCBSP_write16(hMcbsp0, 0x0217); //Right line input channel volume control

while(!MCBSP_xrdy(hMcbsp0));

MCBSP_write16(hMcbsp0, 0x0479); //Left Channel Headphone Volume Control

while(!MCBSP_xrdy(hMcbsp0));

MCBSP_write16(hMcbsp0, 0x0679); //Right Channel Headphone Volume Control

while(!MCBSP_xrdy(hMcbsp0));

MCBSP_write16(hMcbsp0, 0x0810); //Analog Audio Path Control

while(!MCBSP_xrdy(hMcbsp0));

MCBSP_write16(hMcbsp0, 0x0a00); //Digital Audio Path Control

while(!MCBSP_xrdy(hMcbsp0));

MCBSP_write16(hMcbsp0, 0x0e53); //Digital Audio Interface Format while(!MCBSP_xrdy(hMcbsp0));

MCBSP_write16(hMcbsp0, 0x100c); //Sample Rate Control:USB Mode,8KSPS

while(!MCBSP_xrdy(hMcbsp0));

MCBSP_write16(hMcbsp0, 0x1201); //Digital Interface Activation MCBSP_start(hMcbsp1, MCBSP_XMIT_START |

MCBSP_RCV_START |

MCBSP_SRGR_START |

MCBSP_SRGR_FRAMESYNC,

0x200); //允许串口1发送数据}

void Mcbsp1_ISR(void)

{

Int32 DTemp;

short DTemp2;

DTemp = MCBSP_read32(hMcbsp1); //Read ADC Data

MCBSP_write32(hMcbsp1, DTemp); //Write Data to DAC DTemp2 = LR_PATH ? (DTemp & 0xffff):(DTemp >> 16); if(!FFT_Enable)

{

Data_Buff[Save_Index%N] = DTemp2;

Save_Index ++;

if(Save_Index >= N)

FFT_Enable = 1;

}

else

{

Save_Index = 0;

for(i=0; i

{

Dr[i] = Data_Buff[i];

Di[i] = 0;

}

// 用雷德算法对输入信号序列进行倒序重排

j=0;

for(i=0;i

{

if(i

{

Temp = Dr[j];

Dr[j] = Dr[i];

Dr[i] = Temp;

}

k=N/2;

while((k<=j) && (k>0))

{

j=j-k;

k=k/2;

}

j=j+k;

}

// FFT Start

m = 7; //m = log2(N)

for(n=1; n<=m; n++)

{

a = 1; // a=2的n次方

for(i=0;i

a=a*2;

b=a/2;

Vr = 1.0; // 蝶形因子

Vi = 0.0;

Wr = cos(pi/b);

Wi = -sin(pi/b);

for(j=0;j

{

for(i=j;i

{

c=i+b;

Tr = Dr[c]*Vr - Di[c]*Vi;

Ti = Dr[c]*Vi + Di[c]*Vr;

Dr[c] = Dr[i] - Tr;

Di[c] = Di[i] - Ti;

Dr[i] = Dr[i] + Tr;

Di[i] = Di[i] + Ti;

}

Tr = Vr*Wr - Vi*Wi;

Ti = Vr*Wi + Vi*Wr;

Vr = Tr;

Vi = Ti;

}

}

for(n=0; n<300; n++)

Result_Buff[n] = sqrt((Dr[n]*Dr[n])+(Di[n]*Di[n]));

// FFT End

FFT_Enable = 0;

Save_Index = 0;

}

}

/* Do *not* directly modify this file. It was */

/* generated by the Configuration Tool; any */

/* changes risk being overwritten. */

/* INPUT FFT.cdb */

/* MODULE PARAMETERS */

GBL_USERINITFXN = _FXN_F_nop;

MEM_SEGZERO = IDATA;

MEM_MALLOCSEG = IDATA;

CLK_TIMEFXN = FXN_F_zero; CLK_HOOKFXN = CLK_F_rete; PRD_THOOKFXN = KNL_tick_stub; RTDX_DATAMEMSEG = IDATA;

HST_DSMBUFSEG = IDATA;

SWI_EHOOKFXN = GBL_NULL;

SWI_IHOOKFXN = GBL_NULL;

SWI_EXECFXN = SWI_F_exec; SWI_RUNFXN = SWI_F_run;

TSK_STACKSEG = IDATA;

TSK_VCREATEFXN = _FXN_F_nop; TSK_VDELETEFXN = _FXN_F_nop; TSK_VEXITFXN = _FXN_F_nop; IDL_CALIBRFXN = GBL_NULL; SYS_ABORTFXN = _UTL_doAbort; SYS_ERRORFXN = _UTL_doError; SYS_EXITFXN = _UTL_halt;

SYS_PUTCFXN = _UTL_doPutc; GIO_CREATEFXN = _FXN_F_nop; GIO_DELETEFXN = _FXN_F_nop; GIO_PENDFXN = _FXN_F_nop; GIO_POSTFXN = _FXN_F_nop;

/* OBJECT ALIASES */

_USERREGS = USERREGS;

_BIOSREGS = BIOSREGS;

_CSLREGS = CSLREGS;

_VECT = VECT;

_IDATA = IDATA;

_IPROG = IPROG;

_HWI_RS = HWI_RS;

_HWI_NMI = HWI_NMI;

_HWI_SINT17 = HWI_SINT17;

_HWI_SINT18 = HWI_SINT18;

_HWI_SINT19 = HWI_SINT19;

_HWI_SINT20 = HWI_SINT20;

_HWI_SINT21 = HWI_SINT21;

_HWI_SINT22 = HWI_SINT22;

_HWI_SINT23 = HWI_SINT23;

_HWI_SINT24 = HWI_SINT24;

_HWI_SINT25 = HWI_SINT25;

_HWI_SINT26 = HWI_SINT26;

_HWI_SINT27 = HWI_SINT27;

_HWI_SINT28 = HWI_SINT28;

_HWI_SINT29 = HWI_SINT29;

_HWI_SINT30 = HWI_SINT30;

_HWI_INT0 = HWI_INT0;

_HWI_INT1 = HWI_INT1;

_HWI_INT2 = HWI_INT2;

_HWI_TINT = HWI_TINT;

_HWI_SINT4 = HWI_SINT4;

_HWI_SINT5 = HWI_SINT5;

_HWI_SINT6 = HWI_SINT6;

_HWI_SINT7 = HWI_SINT7;

_HWI_SINT8 = HWI_SINT8;

_HWI_SINT9 = HWI_SINT9;

_HWI_SINT10 = HWI_SINT10;

_HWI_SINT11 = HWI_SINT11;

_HWI_SINT12 = HWI_SINT12;

_HWI_SINT13 = HWI_SINT13;

_HWI_SINT14 = HWI_SINT14;

_HWI_SINT15 = HWI_SINT15;

_KNL_swi = KNL_swi;

_TSK_idle = TSK_idle;

_RTDX_dataPump = RTDX_dataPump;

_LOG_system = LOG_system;

/* MODULE GBL */

SECTIONS {

.vers (COPY): {} /* version information */

}

-priority

-llnkrtdx.a54

-ldrivers.a54 /* device drivers support */

-lsioboth.a54 /* supports both SIO models */

-lbios.a54 /* DSP/BIOS support */

-lrtdx.lib /* RTDX support */

-lcsl5410.lib

-lrts.lib /* C and C++ run-time library support */ /* MODULE MEM */

-stack 0x100

MEMORY {

PAGE 1: USERREGS: origin = 0x60, len = 0x1a

PAGE 1: BIOSREGS: origin = 0x7c, len = 0x4

PAGE 1: CSLREGS: origin = 0x7a, len = 0x2

PAGE 0: VECT: origin = 0x7f80, len = 0x80

PAGE 1: IDATA: origin = 0x80, len = 0x3f80 PAGE 0: IPROG: origin = 0x4000, len = 0x3f80 }

/* MODULE CLK */

SECTIONS {

.clk: {

_CLK_start = FXN_F_nop;

CLK_F_isr = CLK_F_isr54x;

CLK_F_gethtime = FXN_F_zero;

CLK_A_TABBEG = .;

/* no CLK objs */

CLK_A_TABEND = .;

CLK_A_TABLEN = (. - CLK_A_TABBEG) / 1; } > IDATA PAGE 1

}

_CLK_PRD = CLK_PRD;

_CLK_COUNTSPMS = CLK_COUNTSPMS;

_CLK_REGS = CLK_REGS;

_CLK_USETIMER = CLK_USETIMER;

_CLK_TIMERNUM = CLK_TIMERNUM;

_CLK_TCR = CLK_TCR;

_CLK_TDDR = CLK_TDDR;

/* MODULE PRD */

SECTIONS {

.prd: {

PRD_A_TABBEG = .;

/* no PRD objects */

PRD_A_TABEND = .;

PRD_A_TABLEN = (. - PRD_A_TABBEG) / 8; } > IDATA PAGE 1

}

/* MODULE RTDX */

_RTDX_interrupt_mask = 0x0;

/* MODULE HWI */

SECTIONS {

.hwi_vec: {

GBL_F_chip = GBL_F_chip54x;

} > VECT PAGE 0

.hwi: {

/* no HWI stubs are necessary */

} > IPROG PAGE 0

}

/* MODULE SWI */

SECTIONS {

.swi: {

SWI_A_TABBEG = .;

*(.swi)

SWI_A_TABEND = .;

SWI_A_TABLEN = (. - SWI_A_TABBEG) / 11;

} > IDATA PAGE 1

}

/* MODULE IDL */

SECTIONS {

.idl: {

IDL_A_TABBEG = .;

*(.idl)

IDL_A_TABEND = .;

IDL_A_TABLEN = (. - IDL_A_TABBEG) / 2;

IDL_A_CALBEG = .;

*(.idlcal)

IDL_A_CALEND = .;

IDL_A_CALLEN = (. - IDL_A_CALBEG) / 2;

} > IDATA PAGE 1

}

SECTIONS {

.sysregs: {} > BIOSREGS PAGE 1

.bss: {} > IDATA PAGE 1

.far: {} > IDATA PAGE 1

.sysdata: align = 128 {

GBL_A_SYSPAGE = .;

GBL_A_SYSDP = GBL_A_SYSPAGE >> 7;

} > IDATA PAGE 1

.mem: {} > IDATA PAGE 1

.sts: {

STS_A_TABBEG = .;

_STS_A_TABBEG = .;

/* no STS objects */

STS_A_TABEND = .;

_STS_A_TABEND = .;

STS_A_TABLEN = (. - _STS_A_TABBEG) / 8; _STS_A_TABLEN = (. - _STS_A_TABBEG) / 8; } > IDATA PAGE 1

.args: fill=0 {

*(.args)

. += 0x4;

} > IDATA PAGE 1

.sys: {} > IDATA PAGE 1

.trace: fill = 0x0 {

_SYS_PUTCBEG = .;

. += 0x200;

_SYS_PUTCEND = . - 1;

} > IDATA PAGE 1

.csldata: {

*(.csldata)

} > IDATA PAGE 1

.pip: {

PIP_A_TABBEG = .;

_PIP_A_TABBEG = .;

/* no PIP objects */

PIP_A_TABEND = .;

_PIP_A_TABEND = .;

PIP_A_TABLEN = (. - _PIP_A_TABBEG) / 25;

_PIP_A_TABLEN = (. - _PIP_A_TABBEG) / 25;

} > IDATA PAGE 1

/* LOG_system buffer */

.LOG_system$buf: align = 0x40 fill = 0xffff {} > IDATA PAGE 1 .data: {} > IDATA PAGE 1

.const: {} > IDATA PAGE 1

.printf (COPY): {} > IDATA PAGE 1

.cio: {} > IDATA PAGE 1

.log: {

LOG_A_TABBEG = .;

_LOG_A_TABBEG = .;

*(.log)

LOG_A_TABEND = .;

_LOG_A_TABEND = .;

LOG_A_TABLEN = (. - _LOG_A_TABBEG) / 6;

_LOG_A_TABLEN = (. - _LOG_A_TABBEG) / 6;

} > IDATA PAGE 1

.gio: {} > IDATA PAGE 1

.TSK_idle$stk: {

*(.TSK_idle$stk)

} > IDATA PAGE 1

.stack: fill=0xbeef {

GBL_stackbeg = .;

*(.stack)

GBL_stackend = ((GBL_stackbeg + 0x100 - 1) & 0xfffe) ; _HWI_STKBOTTOM = GBL_stackend;

_HWI_STKTOP = GBL_stackbeg;

} > IDATA PAGE 1

.tsk: {

*(.tsk)

} > IDATA PAGE 1

.rtdx_data: {} > IDATA PAGE 1

.dsm: {} > IDATA PAGE 1

.hst: {

HST_A_TABBEG = .;

_HST_A_TABBEG = .;

/* no HST objects */

HST_A_TABEND = .;

_HST_A_TABEND = .;

HST_A_TABLEN = (. - _HST_A_TABBEG) / 5;

_HST_A_TABLEN = (. - _HST_A_TABBEG) / 5;

} > IDATA PAGE 1

.IDATA$heap: {

IDATA$B = .;

_IDATA_base = .;

IDATA$L = 0x400;

_IDATA_length = 0x400;

. += 0x400;

} > IDATA PAGE 1

.rtdx_text: {} > IPROG PAGE 0

.bios: {} > IPROG PAGE 0

.text: {} > IPROG PAGE 0

.switch: {} > IPROG PAGE 0

.pinit: {} > IPROG PAGE 0

.cinit: {} > IPROG PAGE 0

.sysinit: {} > IPROG PAGE 0

.gblinit: {} > IPROG PAGE 0

.trcdata: {} > IPROG PAGE 0

frt: {} > IPROG PAGE 0

}

}

第二步骤：连接好硬件及示波器(示波器接模拟输出)。

1．将DSP的USB仿真器连接到实验系统的DSP模块上的JTAG接口；将“音频Code模块”的接口类型跳线连接至SPI端；将“信源选择”连接到中间，也就是选择NC，即不给AIC23输入板上的任何波形。

2．跳线选择无误后，给系统上电，并将USB仿真器的USB连接线插入到计算器的USB接口

第三步骤：打开CCS软件，并打开已建好的FFT.pjt工程，并编译。

第四步骤：编译通过后，下载代码到DSP

第五步骤：设置对话框和断点

首先点击View\Graph\Time/Frequency…，会弹出一个设置对话框，对其作如图4-3所示的设置后，点击【OK】即可。

图4-3 对话框的设置

再打开FFT工程下面的FFT.c，在程序尾部如图4-4所示的位置设置断点。

图4-4 断点设置

第五步骤：

将“音频Codec模块”的信源选择跳线连接值R端（如要连接到L端，请将DFT.c顶端的宏定义LR_PATH置为0即可）。

全部设置好后，点击CCS软件左侧全速运行按钮，即。

第六步骤：待程序运行后，通过调节模拟信源端的波形

?当模拟输出信源端波形选择为00时：

示波器上输出的是余弦函数波形

图4-5 正弦波与其FFT后的波形

?当模拟输出信源端波形选择为01时：

示波器上输出的是方波波形

图4-6 方波与其FFT后的波形

?当模拟输出信源端波形选择为10时：

示波器上输出的时三角波形

图4-7 三角波与其FFT后的波形 当模拟输出信源端波形选择为11时：

示波器上输出的时锯齿波波形

图4-8 锯齿波与其FFT后的波形六、实验小结

实验八 利用快速傅里叶变换(FFT)实现快速卷积(精选、)

实验八 利用FFT 实现快速卷积 一、 实验目的 （1） 通过这一实验，加深理解FFT 在实现数字滤波（或快速卷积）中的重要作用，更好的利用FFT 进行数字信号处理。 （2） 进一步掌握循环卷积和线性卷积两者之间的关系。 二、 实验原理与方法 数字滤波器根据系统的单位脉冲响应h(n)是有限长还是无限长可分为有限长单位脉冲响应（Finite Impulse Response ）系统（简记为FIR 系统）和无限长单位脉冲响应（Infinite Impulse Response ）系统（简记为IIR 系统）。 对于FIR 滤波器来说，除了可以通过数字网络来实现外，也可以通过FFT 的变换来实现。 一个信号序列x(n)通过FIR 滤波器时，其输出应该是x(n)与h(n)的卷积： ∑+∞ -∞ =-= =m m n h m x n h n x n y )()()(*)()( 或 ∑+∞ -∞ =-= =m m n x m h n x n h n y ) ()()(*)()( 当h(n)是一个有限长序列，即h(n)是FIR 滤波器，且10-≤≤N n 时 ∑-=-=1 0) ()()(N m m n x m h n y 在数字网络（见图6.1）类的FIR 滤波器中，普遍使用的横截型结构（见下图6.2 图6.1 滤波器的数字网络实现方法 图6.2 FIR 滤波器横截型结构 y(n) y(n) -1-1-1-1

应用FFT 实现数字滤波器实际上就是用FFT 来快速计算有限长度列间的线性卷积。 粗略地说，这种方法就是先将输入信号x(n)通过FFT 变换为它的频谱采样 值X(k)，然后再和FIR 滤波器的频响采样值H(k)相乘，H(k)可事先存放在存储器中，最后再将乘积H(k)X(k)通过快速傅里叶变换（简称IFFT ）还原为时域序列，即得到输出y(n)如图6.3所示。 图6.3 数字滤波器的快速傅里叶变换实现方法 现以FFT 求有限长序列间的卷积及求有限长度列与较长序列间的卷积为例来讨论FFT 的快速卷积方法。 （1） 序列)(n x 和)(n h 的列长差不多。设)(n x 的列长为1N ，)(n h 的列长为2N ，要求 )()(n x n y =N ∑-=-==1 ) ()()(*)()(N r r n h r x n h n x n h 用FFT 完成这一卷积的具体步骤如下： i. 为使两有限长序列的线性卷积可用其循环卷积代替而不发生混叠，必须选择循环卷积长度121-+≥N N N ，若采用基2-FFT 完成卷积运 算，要求m N 2=（m 为整数）。 ii. 用补零方法使)(n x ，)(n h 变成列长为N 的序列。 ?? ?-≤≤-≤≤=10 10)()(11N n N N n n x n x ?? ?-≤≤-≤≤=10 1 0)()(22N n N N n n h n h iii. 用FFT 计算)(),(n h n x 的N 点离散傅里叶变换 )()(k X n x FFT ??→? )()(k H n h FFT ??→? iv. 做)(k X 和)(k H 乘积，)()()(k H k X k Y ?= v. 用FFT 计算)(k Y 的离散傅里叶反变换得 y(n)

实验二 参考 快速傅立叶变换(FFT)及其应用

实验二快速傅立叶变换（FFT ）及其应用 一、实验目的 1.在理论学习的基础上，通过本实验，加深对FFT 的理解，熟悉FFT 子程序。 2.熟悉应用FFT 对典型信号进行频谱分析的方法 3.了解应用FFT 进行信号频谱分析过程中可能出现的问题以便在实际中正确应用FFT 。 二、实验原理 在各种信号序列中，有限长序列信号处理占有很重要地位，对有限长序列，我们可以使用离散Fouier 变换(DFT)。这一变换不但可以很好的反映序列的频谱特性，而且易于用快速 算法在计算机上实现，当序列x(n)的长度为N 时，它的DFT 定义为： 1 0()()N kn N n X k x n W -==∑， 2n j N N W e -=反换为：10 1()()N kn N k x n X k W N --==∑有限长序列的DFT 是其Z 变换在单位圆上的 等距采样，或者是序列Fourier 变换的等距采样，因此可以用于序列的谱分析。 FFT 并不是与DFT 不同的另一种变换，而是为了减少DFT 运算次数的一种快速算法。它是对变换式进行一次次分解，使其成为若干小点数的组合，从而减少运算量。常用的FFT 是以2为基数的，其长度 N=2L ，它的效率高，程序简单使用非常方便，当要变换的序列长度不等于2的整数次方时，为了使用以2为基数的FFT ，可以用末位补零的方法，使其长度延长至2的整数次方。 在运用DFT 进行频谱分析的过程中可能产生几种问题： (1) 混叠 序列的频谱时被采样信号的周期延拓，当采样速率不满足Nyquist 定理时，就会发生频谱混叠，使得采样后的信号序列频谱不能真实的反映原信号的频谱。 避免混叠现象的唯一方法是保证采样速率足够高，使频谱混叠现象不致出现，即在确定采样频率之前，必须对频谱的性质有所了解，在一般情况下，为了保证高于折叠频率的分量不会出现，在采样前，先用低通模拟滤波器对信号进行滤波。 (2) 泄漏 实际中我们往往用截短的序列来近似很长的甚至是无限长的序列，这样可以使用较短的DFT 来对信号进行频谱分析，这种截短等价于给原信号序列乘以一个矩形窗函数，也相当于在频域将信号的频谱和矩形窗函数的频谱卷积，所得的频谱是原序列频谱的扩展。 泄漏不能与混叠完全分开，因为泄漏导致频谱的扩展，从而造成混叠。为了减少泄漏的影响，可以选择适当的窗函数使频谱的扩散减至最小。 DFT 是对单位圆上Z 变换的均匀采样，所以它不可能将频谱视为一个连续函数，就一定意义上看，用DFT 来观察频谱就好像通过一个栅栏来观看一个图景一样，只能在离散点上看到真实的频谱，这样就有可能发生一些频谱的峰点或谷点被“尖桩的栅栏”所拦住，不能别我们观察到。 减小栅栏效应的一个方法就是借助于在原序列的末端填补一些零值，从而变动DFT 的点数，这一方法实际上是人为地改变了对真实频谱采样的点数和位置，相当于搬动了每一根“尖桩栅栏”的位置，从而使得频谱的峰点或谷点暴露出来。 用FFT 可以实现两个序列的圆周卷积。在一定的条件下，可以使圆周卷积等于线性卷积。一般情况，设两个序列的长度分别为N1和N2，要使圆周卷积等于线性卷积的充要条件是

实验一快速傅里叶变换

实验一 快速傅里叶变换之报告 一 、实验目的 1、在理论学习的基础上，通过本实验加深对快速傅立叶变换的理解； 2、熟悉并掌握按时间抽取FFT 算法的程序； 3、了解应用FFT 进行信号频谱分析过程中可能出现的问题，例如混淆、泄漏、 栅栏效应等，以便在实际中正确应用FFT 。 二 实验内容 a ） 信号频率F ＝50Hz ，采样点数N=32,采样间隔T= matlab 程序代码为： F=50; T=; N=32; n=0:N-1; t=n*T; A=sin(2*pi*F*t); figure; Y = fft(A,N); h = (abs(Y)); h=h/max(h(1:N)); for n=1:N; string1=strcat('X(',num2str(n-1), ')=',num2str(h(n))); disp(string1); f=(n/T)/N; end stem([0:N-1]/N/T,h); xlabel('?μ?ê/HZ'); ylabel('??·ùX￡¨ejw￡?'); title('·ù?μì?D?'); 上述代码命令中，将FFT 变换后的数字变量K ，在画图时转换成频域中的频率f 。这主 要是根据数字频率与模拟域频率之间的关系： T Ω=ω 其中ω、Ω分别为数字和模拟域中的频率，且N k πω2= f π2=Ω 于是有： NT k f = 运算结果： X(1)=1 X(2)= X(3)= X(4)=

X(5)= X(6)= X(7)= X(8)= X(9)= X(10)= X(11)= X(12)= X(13)= X(14)= X(15)= X(16)= X(17)= X(18)= X(19)= X(20)= X(21)= X(22)= X(23)= X(24)= X(25)= X(26)= X(27)= X(28)= X(29)= X(30)= X(31)=1 b）信号频率F＝50Hz，采样点数N=32,采样间隔T= 同理可将a）中F、N、T，参数改成要求值（以下均是如此），即可得，X(0)= X(1)= X(2)= X(3)= X(4)= X(5)= X(6)= X(7)= X(8)=1 X(9)= X(10)= X(11)= X(12)= X(13)= X(14)= X(15)= X(16)= X(17)= X(18)= X(19)= X(20)= X(21)= X(22)= X(23)= X(24)=1 X(25)= X(26)= X(27)= X(28)= X(29)= X(30)= X(31)=

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)算法_DSP实验

快速傅立叶变换(FFT)算法实验 摘要：FFT（Fast Fourier Transformation），即为快速傅里叶变换，是离散傅里叶变换的快速算法，它是根据离散傅里叶变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。这种算法大大减少了变换中的运算量，使得其在数字信号处理中有了广泛的运用。本实验主要要求掌握在CCS环境下用窗函数法设计FFT快速傅里叶的原理和方法；并且熟悉FFT快速傅里叶特性；以及通过本次试验了解各种窗函数对快速傅里叶特性的影响等。 引言： 快速傅里叶变换FFT是离散傅里叶变换DFT的一种快速算法。起初DFT的计算在数字信号处理中就非常有用，但由于计算量太大，即使采用计算机也很难对问题进行实时处理，所以并没有得到真正的运用。1965年J.W.库利和T.W.图基提出快速傅里叶变换，采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少,特别是被变换的抽样点数N越多,FFT算法计算量的节省就越显著。从此，对快速傅里叶变换（FFT）算法的研究便不断深入，数字信号处理这门新兴学科也随FFT的出现和发展而迅速发展。根据对序列分解与选取方法的不同而产生了FFT的多种算法，基本算法是基2DIT和基2DIF。FFT 的出现，使信号分析从时域分析向频域分析成为可能，极大地推动了信号分析在各领域的实际应用。FFT在离散傅里叶反变换、线性卷积和线性相关等方面也有重要应用。

一、 实验原理： FFT 并不是一种新的变换，它是离散傅立叶变换（DFT ）的一种快速算法。由于我们在计算DFT 时一次复数乘法需用四次实数乘法和二次实数加法；一次复数加法则需二次实数加法。每运算一个X （k ）需要4N 次复数乘法及2N+2（N-1）=2（2N-1）次实数加法。所以整个DFT 运算总共需要4N^2次实数乘法和N*2(2N-1)=2N(2N-1)次实数加法。如此一来，计算时乘法次数和加法次数都是和N^2成正比的，当N 很大时，运算量是可观的，因而需要改进对DFT 的算法减少运算速度。 根据傅立叶变换的对称性和周期性，我们可以将DFT 运算中有些项合并。我们先设序列长度为N=2^L ，L 为整数。将N=2^L 的序列x(n)(n=0,1,……，N-1)，按N 的奇偶分成两组，也就是说我们将一个N 点的DFT 分解成两个N/2点的DFT ，他们又从新组合成一个如下式所表达的N 点DFT ： ∑∑∑∑∑-=+-=-=++ = + =-≤≤= =1 )12(1 20 2为奇 为偶 10 )12()2()()(10, )()]([)(N r k r N N r rk N n nk N n nk N N n nk N W r x W r x W n x W n x N k W n x n x DFT k X

DSP-快速傅立叶变换(FFT)算法实验

中南大学 DSP技术实验报告 实验名称：快速傅立叶变换(FFT)算法实验专业班级：信息0602 学生姓名：张倩曦（学号：24） 指导老师：陈宁 完成日期： 2009年12月2日 中南大学·信息科学与工程学院

快速傅立叶变换(FFT)算法实验一．实验目的 1．掌握用窗函数法设计FFT 快速傅里叶的原理和方法； 2．熟悉FFT 快速傅里叶特性； 3．了解各种窗函数对快速傅里叶特性的影响。 二．实验设备 PC 兼容机一台，操作系统为Windows2000(或Windows98，WindowsXP，以下默认为Windows2000)，安装Code Composer Studio 软件。 三．实验原理 1．FFT 的原理和参数生成公式： 公式（1）FFT 运算公式 FFT 并不是一种新的变换，它是离散傅立叶变换（DFT）的一种快速算法。由于我们在计算DFT 时一次复数乘法需用四次实数乘法和二次实数加法；一次复数加法则需二次实数加法。 每运算一个X（k）需要4N 次复数乘法及2N+2（N-1）=2（2N-1）次实数加法。所以整个DFT运算总共需要4N^2 次实数乘法和N*2(2N-1)=2N(2N-1)次实数加法。如此一来，计算时乘法次数和加法次数都是和N^2 成正比的，当N 很大时，运算量是可观的，因而需要改进对DFT 的算法减少运算速度。 根据傅立叶变换的对称性和周期性，我们可以将DFT 运算中有些项合并。我们先设序列长度为N=2^L，L 为整数。将N=2^L 的序列x(n)(n=0,1,……，N-1)，

按N的奇偶分成两组，也就是说我们将一个N 点的DFT 分解成两个N/2 点的DFT，他们又重新组合成一个如下式所表达的N 点DFT： 一般来说，输入被假定为连续的。当输入为纯粹的实数的时候，我们就可以利用左右对称的特性更好的计算DFT。 我们称这样的RFFT 优化算法是包装算法：首先2N 点实数的连续输入称为“进包”。其次N 点的FFT 被连续运行。最后作为结果产生的N 点的合成输出是“打开”成为最初的与DFT 相符合的2N 点输入。使用这一思想，我们可以划分FFT 的大小，它有一半花费在包装输入O（N）的操作和打开输出上。这样的RFFT 算法和一般的FFT 算法同样迅速，计算速度几乎都达到了两次DFT的连续输入。下列一部分将描述更多的在TMS320C55x 上算法和运行的细节。 5．程序流程图：

快速傅里叶变换(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

快速傅里叶变换实验报告..

快速傅里叶变换实验报告 班级： 姓名： 学号:

快速傅里叶变换 一．实验目的 1.在理论学习的基础上，通过本实验加深对快速傅立叶变换的理解； 2.熟悉并掌握按时间抽取FFT 算法的程序； 3.了解应用FFT 进行信号频谱分析过程中可能出现的问题，例如混淆、泄漏、栅栏效应等，以便在实际中正确应用FFT 。 二．实验内容 1.仔细分析教材第六章‘时间抽取法FFT ’的算法结构，编制出相应的用FFT 进行信号分析的C 语言（或MATLAB 语言）程序； 2.用FFT 程序分析正弦信号 ()sin(2)[()(*)],(0)1y t f t u t u t N T t u π=---∞<<+∞=设 分别在以下情况进行分析并讨论所得的结果： a ） 信号频率f ＝50Hz ，采样点数N=32,采样间隔T=0.000625s b ） 信号频率f ＝50Hz ，采样点数N=32,采样间隔T=0.005s c ） 信号频率f ＝50Hz ，采样点数N=32,采样间隔T=0.0046875s d ） 信号频率f ＝50Hz ，采样点数N=32,采样间隔T=0.004s e ） 信号频率 f ＝50Hz ，采样点数N=64,采样间隔T=0.000625s f ） 信号频率f ＝250Hz ，采样点数N=32,采样间隔T=0.005s g ） 将c ） 信号后补32个0，做64点FFT 三．实验要求 1.记录下实验内容中各种情况下的X (k)值，做出频谱图并深入讨论结果，说明参数的变化对信号频谱产生哪些影响。频谱只做模特性，模的最大值＝1，全部归一化；

2.打印出用C 语言（或MATLAB 语言）编写的FFT 源程序，并且在每一小段处加上详细的注释说明； 3.用C 语言（或MATLAB 语言）编写FFT 程序时，要求采用人机界面形式： N , T , f 变量均由键盘输入，补零或不补零要求设置一开关来选择。 四．实验分析 对于本实验进行快速傅里叶变换，依次需要对信号进行采样，补零（要求补零时），码位倒置，蝶形运算，归一化处理并作图。 此外，本实验要求采用人机界面形式，N,T,F 变量由键盘输入，补零或不补零设置一开关来选择。 1.采样 本实验进行FFT 运算，给出的是正弦信号，需要先对信号进行采样，得到有限 长序列()n x ， N n ...... 2,1,0= Matlab 实现： t=0:T:T*(N-1); x=sin(2*pi*f*t); 2.补零 根据实验要求确定补零与否，可以用if 语句做判断，若为1，再输入补零个数， 并将补的零放到采样得到的序列的后面组成新的序列，此时新的序列的元素个数等于原采样点个数加上补零个数，并将新的序列个数赋值给N 。 Matlab 实现： a=input('是否增加零点? 是请输入1 否请输入0\n'); if (a) ZeroNum=input('请输入增加零点的个数:\n'); else ZeroNum=0; end if (a) x=[x zeros(1, ZeroNum)];%%指令zeros(a,b)生成a 行b 列全0矩阵，在单行矩阵x 后补充0 end N=N+ZeroNum; 3.码位倒置 本实验做FFT 变换的级数为M ，N M 2log =

快速傅里叶变换FFT.

————第四章———— 快速傅里叶变换FFT 所谓的快速算法，就是根据原始变换定义算法的运算规律及其中的某些算子的特殊性质，找出减少乘法和加法运算次数的有效途径，实现原始变换的各种高效算法。一种好的快速算法可使变换速度提高几个数量级。 由于快速算法很多，而且还在不断研究和发展。较成熟的算法都有现成的程序。所以，通过教材中介绍的四种快速算法，主要学习研究快速算法的基本思想和减少运算量的途径，熟悉各种快速算法的特点、运算效率和适用情况。为今后研究新的快速算法和合理选用快速算法打好基础。 4.1 学 习 要 点 4.1.1 直接计算N 点DFT 的运算量 对于 ()(),1 0∑-==N n kn N W n x k X 1,,1,0-=N k 复数乘法次数： 2 N M c = 复数加法次数： ()1-=N N A c 当1>>N 时，复数乘法和加法次数都接近为2 N 次，随着N 增大非线性增大。 4.1.2 减少运算量的基本途径 DFT 定义式中只有两种运算：()n x 与kn N W 的乘法相加。所以，kn N W 的特性对乘法运算 量必有影响。 （1）根据的对称性、周期性和特殊值减少乘法运算次数。 ①对称性：k N N k N W W -=+ 2 ，()k k N N W 12-=，()k N k N N W W =* - ②周期性：k N lN k N W W =+。 ③kn N W 的特殊值(无关紧要旋转因子)： 1;;124 -===±N N N N N W j W W 。对这些因子不能进行乘法运算。 （2）将较大数N 点DFT 分解为若干个小数点DFT 的组合，减少运算量。这正是FFT 能大量节省运算量的关键。 4.1.3 四种快速算法的基本思想及特点 根据上述减少运算量的途径，巧妙地在时域或频域进行不同的抽取分解与组合，得到不

快速傅里叶变换实验报告

快速傅里叶变换实验报告 快速傅里叶变换实验报告 机械34班刘攀 2019010558 一、基本信号（函数）的FFT变换 1. x(t)=sin(ω0t+)+sin2ω0t+cos3ω0t 6 1) 采样频率fs=8f0，截断长度N=16； 取ω0=2πrad/s，则f0=1Hz，fs=8Hz，频率分辨率?f=?f=fs=0.5Hz。 Nπ最高频率fc=3f0=3Hz，fs>2fc，故满足采样定理，不会发生混叠现象。截断长度T=2T0，整周期截取，不会发生栅栏效应。理论上有一定的泄漏，但在整周期截取的情况下，旁瓣上的采样都约为 0，泄漏现象没有体现出来。 频谱图如下： 幅值误差?A=0，相位误差??=0。 2) 采样频率fs=8f0，截断长度N=32； 取ω0=2πrad/s，则f0=1Hz，fs=8Hz，频率分辨率?f=?f=fs=0.25Hz。 N最高频率fc=3f0=3Hz，fs>2fc，故满足采样定理，不会发生混叠现象。截断长度T=4T0，整周期截取，不会发生栅栏效应。理论上有一定的泄漏，但在整周期截取的情况下，旁瓣上的采样都约为 0，泄漏现象没有体现出来。 频谱图如下： 幅值误差?A=0，相位误差??=0。 2. x(t)=sin(ω0t+π 6)+sin11ω0t 1) 采样频率fs=8f0，截断长度N=16； 取ω0=2πrad/s，则f0=1Hz，fs=8Hz，频率分辨率?f=?f=fs=0.5Hz。 N最高频率 fc=11f0=11Hz，fs 漏，但在整周期截取的情况下，旁瓣上的采样都约为 0，泄漏现象没有体现出来。 频谱图：

由上图可以看出，并未体现出11f0的成分，说明波形出现混叠失真。为了消除混叠 现象，应加大采样频率，使之大于等于 22Hz。 f0处的幅值误差?A=0，11f0处由于出现 了混叠现象，幅值误差没有意义；相位误差??=0。 2) 采样频率fs=32f0，截断长度N=32； 取ω0=2πrad/s，则f0=1Hz，fs=32Hz，频率分辨率?f=?f=fs=1Hz。 N最高频率 fc=11f0=11Hz，fs>2fc，故满足采样定理，不会发生混叠现象。 漏，但在整周期截取的情况下，旁瓣上的采样都约为 0，泄漏现象没有体现出来。 频谱图： 该频谱图体现出了f0和11f0的成分，说明未失真，且幅值均为1,。幅值误差?A=0，相位误差??=0。 3. x(t)=0t 1) 采样频率fs=8f0，截断长度N=16； 取ω0=2πrad/s，则f0=1Hz，fs=8Hz，频率分辨率?f=?f=fs=0.5Hz。 N最高频率f cf 0Hz，fs>2fc，故满足采样定理，不会发生混叠现象。 频谱图： 在忽略旁瓣信号的情况下，可近似认为： x(t)≈0.9098cos(3ω0t+56.9520?) 故幅值误差?A=0.9096-1=-0.0904，相位误差??=56.9520?。 2) 采样频率fs=32f0，截断长度N=32； 取ω0=2πrad/s，则f0=1Hz，fs=32Hz，频率分辨率?f=?f=fs=1Hz。N最高频率f cf 0Hz，fs>2fc，故满足采样定理，不会发生混叠现象。 频谱图： 在忽略旁瓣信号的情况下，可近似认为：

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

快速傅里叶变换的原理及其应用 摘要 快速傅氏变换（FFT），是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。傅里叶变换的理论与方法在“数理方程”、“线性系统分析”、“信号处理、仿真”等很多学科领域都有着广泛应用,由于计算机只能处理有限长度的离散的序列,所以真正在计算机上运算的是一种离散傅里叶变换. 虽然傅里叶运算在各方面计算中有着重要的作用，但是它的计算过于复杂，大量的计算对于系统的运算负担过于庞大，使得一些对于耗电量少，运算速度慢的系统对其敬而远之，然而，快速傅里叶变换的产生，使得傅里叶变换大为简化，在不牺牲耗电量的条件下提高了系统的运算速度，增强了系统的综合能力，提高了运算速度，因此快速傅里叶变换在生产和生活中都有着非常重要的作用，对于学习掌握都有着非常大的意义。 关键词快速傅氏变换；快速算法；简化；广泛应用

Abstract Fast Fourier Transform (FFT), is a discrete fast Fourier transform algorithm, which is based on the Discrete Fourier Transform of odd and even, false, false, and other characteristics of the Discrete Fourier Transform algorithms improvements obtained. Its Fourier transform theory has not found a new, but in the computer system or the application of digital systems Discrete Fourier Transform can be said to be a big step into. Fourier transform theory and methods in the "mathematical equation" and "linear systems analysis" and "signal processing, simulation," and many other areas have a wide range of applications, as the computer can only handle a limited length of the sequence of discrete, so true On the computer's operation is a discrete Fourier transform. Fourier Although all aspects of computing in the calculation has an important role, but its calculation was too complicated, a lot of computing system for calculating the burden is too large for some Less power consumption, the slow speed of operation of its system at arm's length, however, have the fast Fourier transform, Fourier transform greatly simplifying the making, not in power at the expense of the conditions to increase the speed of computing systems, and enhance the system The comprehensive ability to improve the speed of operation, the Fast Fourier Transform in the production and life have a very important role in learning to master all have great significance. Key words Fast Fourier Transform; fast algorithm; simplified; widely used

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

kn N W N N 第四章 快速傅里叶变换 有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长 序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换 (FFT). 1965 年，Cooley 和 Tukey 提出了计算离散傅里叶变换（DFT ）的快 速算法，将 DFT 的运算量减少了几个数量级。从此，对快速傅里叶变换（FFT ） 算法的研究便不断深入，数字信号处理这门新兴学科也随 FFT 的出现和发 展而迅速发展。根据对序列分解与选取方法的不同而产生了 FFT 的多种算 法，基本算法是基２DIT 和基２DIF 。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)的值

快速傅里叶变换实验报告

快速傅里叶变换实验报告 机械34班 攀 2013010558 一、 基本信号（函数）的FFT 变换 1. 000()sin()sin 2cos36 x t t t t πωωω=+++ 1) 采样频率08s f f =，截断长度N=16； 取02ωπ=rad/s ，则0f =1Hz ，s f =8Hz ，频率分辨率f ?=s f f N ?==0.5Hz 。 最高频率c f =30f =3Hz ，s f >2c f ，故满足采样定理，不会发生混叠现象。 截断长度02T T =，整周期截取，不会发生栅栏效应。理论上有一定的泄漏，但在整周期 截取的情况下，旁瓣上的采样都约为 0，泄漏现象没有体现出来。 频谱图如下：

幅值误差0A ?=，相位误差0??=。 2) 采样频率08s f f =，截断长度N=32； 取02ωπ=rad/s ，则0f =1Hz ，s f =8Hz ，频率分辨率f ?=s f f N ?==0.25Hz 。 最高频率c f =30f =3Hz ，s f >2c f ，故满足采样定理，不会发生混叠现象。 截断长度04T T =，整周期截取，不会发生栅栏效应。理论上有一定的泄漏，但在整周期 截取的情况下，旁瓣上的采样都约为 0，泄漏现象没有体现出来。 频谱图如下：

幅值误差0A ?=，相位误差0??=。 2. 00()sin()sin116 x t t t πωω=++ 1) 采样频率08s f f =，截断长度N=16； 取02ωπ=rad/s ，则0f =1Hz ，s f =8Hz ，频率分辨率f ?=s f f N ?==0.5Hz 。 最高频率c f =110f =11Hz ，s f <2c f ，故不满足采样定理，会发生混叠现象。 截断长度02T T =，整周期截取，不会发生栅栏效应。理论上有一定的泄漏，但在整周期 截取的情况下，旁瓣上的采样都约为 0，泄漏现象没有体现出来。 频谱图：

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

快速傅里叶变换实验

快速傅里叶变换实验

————————————————————————————————作者：————————————————————————————————日期： ?

实验七快速傅里叶变换实验 20１1０１0５４1?机１4 林志杭 一、实验目的 1.加深对几个特殊概念的理解：“采样”……“混叠”;“窗函数”（截断）……“泄漏”；“非整周期截取”……“栅栏”。 ２．加深理解如何才能避免“混叠”，减少“泄漏”，防止“栅栏”的方法和措施以及估计这些因素对频谱的影响。 3．对利用通用微型计算机及相应的FFＴ软件，实现频谱分析有一个初步的了解。 二、实验原理 为了实现信号的数字化处理，利用计算机进行频谱分析――计算信号的频谱。由于计算机只能进行有限的离散计算(即ＤFT)，因此就要对连续的模拟信号进行采样和截断。而这两个处理过程可能引起信号频谱的畸变，从而使DFT的计算结果与信号的实际频谱有误差。有时由于采样和截断的处理不当，使计算出来的频谱完全失真。因此在时域处理信号时要格外小心。 时域采样频率过低，将引起频域的“混叠”。为了避免产生“混叠”,要求时域采样时必须满足采样定理,即:采样频率fｓ必须大于信号中最高频率fc的2倍（ｆｓ＞2fc)。因此在信号数字处理中，为避免混叠，依不同的信号选择合适的采样频率将是十分重要的。 频域的“泄漏”是由时域的截断引起的。时域的截断使频域中本来集中的能量向它的邻域扩散(如由一个δ(f）变成一个siｎc(f），而泄漏的旁瓣将影响其它谱线的数值。时域截断还会引起“栅栏效应”,对周期信号而言，它是由于截断长度不等于周期信号的周期的整数倍而引起的。因此避免“栅栏”效应的办法就是整周期截断。 综上所述,在信号数字化处理中应十分注意以下几点： 1．为了避免“混叠”,要求在采样时必须满足采样定理。 为了减少“泄漏”，应适当增加截断长度和选择合适的窗 对信号进行整周期截取,则能消除“栅栏数应”。 增加截断长度，则可提高频率分辨率。 三、预习内容 熟悉Mａtlab语言、函数和使用方法；利用Ｍatｌab所提供的ＦFT函数编写程序。 四、实验内容及步骤 调通所编写的程序,对下列信号〔函数〕进行离散FFT变换,根据题目的要求……FFT变换点数〔截断长度〕及采样频率,计算各点的傅里叶变换值,画出频谱图,对典型的谱线标出其幅值及相角。 （-)内容: 1． t t t t x 3 cos 2 sin ) 6 sin( )(ω ω π ω+ + + = 代码： N=ｉnput(＇N='); n=input（'ｎ=')；ｔ=1：1：Ｎ；

实验四 快速傅里叶变换(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 。