实数FFT算法的设计及其C语言实现
目前国内有关数字信号处理的教材在讲解快速傅里叶变换(FFT)时，都是以复数FFT为重点，实数FFT算法都是一笔带过，书中给出的具体实现程序多为BASIC或FORTRAN程序并且多数不能真正运行。鉴于目前在许多嵌入式系统中要用到FFT运算，如以DSP为核心的交流采样系统、频谱分析、相关分析等。本人结合自己的实际开发经验，研究了实数的FFT算法并给出具体的C语言函数，读者可以直接应用于自己的系统中。
首先分析实数FFT算法的推导过程，然后给出一种具体实现FFT算法的C语言程序，可以直接应用于需要FFT运算的单片机或DSP等嵌入式系统中。
1 倒位序算法分析
按时间抽取(DIT)的FFT算法通常将原始数据倒位序存储，最后按正常顺序输出结果X(0)，X(1)，...，X(k)，...。假设一开始，数据在数组float dataR[128]中，我们将下标i表示为(b6b5b4b3b2b1b0)b，倒位序存放就是将原来第i个位置的元素存放到第(b0b1b2b3b4b5b6)b 的位置上去.由于C语言的位操作能力很强，可以分别提取出b6、b5、b4、b3、b2、b1、b0，再重新组合成b0、b1、b2、b3、b4、b5、b6，即是倒位序的位置。程序段如下(假设128点FFT)：
/* i为原始存放位置，最后得invert_pos为倒位序存放位置*/
int b0=b1=b2=b3=b4=b5=6=0;
b0=i0x01; b1=(i/2)0x01; b2=(i/4)0x01;
b3=(i/8)0x01; b4=(i/16)0x01; b5=(i/32)0x01;
b6=(i/64)0x01; /*以上语句提取各比特的0、1值*/
invert_pos=x0*64+x1*32+x2*16+x3*8+x4*4+x5*2+x6;
大家可以对比教科书上的倒位序程序，会发现这种算法充分利用了C语言的位操作能力，非常容易理解而且位操作的速度很快。
2 实数蝶形运算算法的推导
我们首先看一下图1所示的蝶形图。
FFT算法的DSP实现 对于离散傅里叶变换(DFT)的数字计算，FFT是一种有效的方法。一般假定输入序列是复数。当实际输入是实数时，利用对称性质可以使计算DFT非常有效。 一个优化的实数FFT算法是一个组合以后的算法。原始的2N个点的实输入序列组合成一个N点的复序列，之后对复序列进行N点的FFT运算，最后再由N点的复数输出拆散成2N点的复数序列，这2 N点的复数序列与原始的2N点的实数输入序列的DFT输出一致。 使用这种方法，在组合输入和拆散输出的操作中，FFT运算量减半。这样利用实数FFT 算法来计算实输入序列的DFT的速度几乎是一般FFT算法的两倍。下面用这种方法来实现一个256点实数FFT（2N=256）运算。 1.实数FFT运算序列的存储分配 如何利用有限的DSP系统资源，合理的安排好算法使用的存储器是一个比较重要的问题。本文中，程序代码安排在0x3000开始的存储器中，其中0x3000~0x3080存放中断向量表，FFT程序使用的正弦表和余弦表数据(.data段)安排在0xc00开始的地方，变量(.bss段定义) 存放在0x80开始的地址中。另外，本文中256点实数FFT程序的数据缓冲位0x2300~0x23ff , FFT变换后功率谱的计算结果存放在0x2200~0x22ff中。连续定位.cmd文件程序如下： MEMORY { PAGE 0: IPROG: origin = 0x3080,len=0x1F80 VECT: lorigin=0x3000,len=0x80 EPROG: origin=0x38000,len=0x8000 PAGE 1: USERREGS: origin=0x60,len=0x1c BIOSREGS: origin=0x7c,len=0x4 IDA TA: origin=0x80,len=0xB80 EDA TA: origin=0xC00,len=0x1400 } SECTIONS { .vectors: { } > VECT PAGE 0 .sysregs: { } > BIOSREGS PAGE 1 .trcinit: { } > IPROG PAGE 0 .gblinit: { } > IPROG PAGE 0 .bios: { } > IPROG PAGE 0 frt: { } > IPROG PAGE 0 .text: { } > IPROG PAGE 0 .cinit: { } > IPROG PAGE 0 .pinit: { } > IPROG PAGE 0 .sysinit: { } > IPROG PAGE 0 .data: { } > EDATA PAGE 1 .bss: { } > IDATA PAGE 1 .far: { } > IDATA PAGE 1 .const: { } > IDATA PAGE 1 .switch: { } > IDATA PAGE 1
《DSP原理及其应用》实验设计报告 实验题目：FFT算法及滤波器的设计
摘要 随着信息科学的迅猛发展，数据采集与处理是计算机应用的一门关键技术，它主要研究信息数据的采集、存储和处理。而数字信号处理器(DSP)芯片的出现为实现数字信号处理算法提供了可能。数字信号处理器（DSP）以其特有的硬件体系结构和指令体系成为快速精确实现数字信号处理的首选工具。DSP芯片采用了哈佛结构，以其强大的数据处理功能在通信和信号处理等领域得到了广泛应用，并成为研究的热点。 本文主要研究基于TI的DSP芯片TMS320c54x的FFT算法、FIR滤波器和IIR滤波器的实现。首先大概介绍了DSP和TMS320c54x的结构和特点并详细分析了本系统的FFT变换和滤波器的实现方法。 关键词：DSP、TMS320c54x、FFT、FIR、IIR
Abstract With the rapid development of information science, data acquisition and processing is a key technology of computer applications, the main research of it is collection, storage and processing of information data. The emergence of the digital signal processor (DSP) chip offers the potential for the realization of the digital signal processing algorithm. Digital signal processor (DSP), with its unique hardware system structure and instruction system become the first tool of quickly and accurately realize the digital signal processing.DSP chip adopted harvard structure, with its powerful data processing functions in the communication and signal processing, and other fields has been widely applied, and become the research hot spot. This paper mainly studies the FFT algorithm based on TMS320c54x DSP chip of TI, the realization of FIR filter and IIR filter. First introduced the DSP and TMS320c54x briefly, then analyzed in detail the structure and characteristics of the system of the realization of FFT transform and filter method. Keyword: DSP、TMS320c54x、FFT、FIR、IIR
实数FFT算法的设计及其C语言实现 目前国内有关数字信号处理的教材在讲解快速傅里叶变换(FFT)时，都是以复数FFT为重点，实数FFT算法都是一笔带过，书中给出的具体实现程序多为BASIC或FORTRAN程序并且多数不能真正运行。鉴于目前在许多嵌入式系统中要用到FFT运算，如以DSP为核心的交流采样系统、频谱分析、相关分析等。本人结合自己的实际开发经验，研究了实数的FFT算法并给出具体的C语言函数，读者可以直接应用于自己的系统中。 首先分析实数FFT算法的推导过程，然后给出一种具体实现FFT算法的C语言程序，可以直接应用于需要FFT运算的单片机或DSP等嵌入式系统中。 1 倒位序算法分析 按时间抽取(DIT)的FFT算法通常将原始数据倒位序存储，最后按正常顺序输出结果X(0)，X(1)，...，X(k)，...。假设一开始，数据在数组float dataR[128]中，我们将下标i表示为(b6b5b4b3b2b1b0)b，倒位序存放就是将原来第i个位置的元素存放到第(b0b1b2b3b4b5b6)b 的位置上去.由于C语言的位操作能力很强，可以分别提取出b6、b5、b4、b3、b2、b1、b0，再重新组合成b0、b1、b2、b3、b4、b5、b6，即是倒位序的位置。程序段如下(假设128点FFT)： /* i为原始存放位置，最后得invert_pos为倒位序存放位置*/ int b0=b1=b2=b3=b4=b5=6=0; b0=i0x01; b1=(i/2)0x01; b2=(i/4)0x01; b3=(i/8)0x01; b4=(i/16)0x01; b5=(i/32)0x01; b6=(i/64)0x01; /*以上语句提取各比特的0、1值*/ invert_pos=x0*64+x1*32+x2*16+x3*8+x4*4+x5*2+x6; 大家可以对比教科书上的倒位序程序，会发现这种算法充分利用了C语言的位操作能力，非常容易理解而且位操作的速度很快。 2 实数蝶形运算算法的推导 我们首先看一下图1所示的蝶形图。
数字通信课程设计报告书 课题名称 基于matlab 的FFT 算法程序设计 姓 名 学 号 院 系 物理与电信工程系 专 业 电子信息工程 指导教师 2010年 01 月15日 ※※※※※※※※※ ※ ※ ※※ ※※ ※※ ※※※※※ ※※ 2007级数字通信 课程设计
基于matlab的FFT算法程序设计 0712401-36 李晔 （湖南城市学院物理与电信工程系通信工程专业,益阳,413000） 一、设计目的 1.通过该设计，进一步了解MATLAB软件。 2.通过该设计，进一步熟悉MATLAB的语法规则和编辑方式。 3.通过该设计，掌握傅里叶变换的含义和方法。 二、设计的主要要求 掌握Fourier变换，解了关于MATLAB软件在数字信号处理方面的应用，熟悉MATLAB的语法规则和编程。用MATLAB实现快速Fourier变换。 三、整体设计方案 对信号x=sin(2*pi*f0*t)进行频谱分析，用MATLAB仿真。选取抽样频率为fs=100Hz,依照下列条件用MATLAB软件对信号xt进行傅里叶变换y=fft(xt,N)并绘制频谱图，观察所产生的六幅频谱图进行对比，并进行分析。 四、程序设计 fs=100;%设定采样频率 N=128; n=0:N-1; t=n/fs; f0=10;%设定正弦信号频率
%生成正弦信号 x=sin(2*pi*f0*t); figure(1); subplot(321); plot(t,x);%作正弦信号的时域波形 xlabel('t'); ylabel('y'); title('正弦信号y=2*pi*10t时域波形'); grid; %进行FFT变换并做频谱图 y=fft(x,N);%进行fft变换 mag=abs(y);%求幅值 m=length(y); f=(0:m/2-1)'*fs/m;%进行对应的频率转换 figure(1); subplot(322); plot(f,mag(1:m/2));%做频谱图 axis([0,100,0,80]); xlabel('频率(Hz)'); ylabel('幅值'); title('正弦信号y=2*pi*10t幅频谱图N=128'); grid; %求均方根谱 sq=abs(y); figure(1); subplot(323); plot(f,sq(1:m/2)); xlabel('频率(Hz)'); ylabel('均方根谱');
毕业设计 [论文] 题目：FFT算法研究及基2-FFT算法的C语言实现学院：电气与信息工程学院 专业：电气工程及其自动化 姓名：XXX 学号：XXXXXX 指导老师：XXX 完成时间：2015年06月01日
摘要 离散傅立叶变换（DFT）常常用于计算信号处理。DFT算法可以得到信号的频域特性，因为该算法在计算上是密集的，长时间的使用时，计算机不能实时进行信号处理。所以DFT被发现之后的相当长时间内是没被应用到实际的项目。到了二十世纪六十年代中期一种新的计算方法被研究者发现出来，它就是FFT。FFT 并不是一种新的获取频域特征的方式，而是离散傅里叶变换的一种快速实现算法。 数字信号处理在当今科技发展中发展很迅速，不但是在传统的通信领域，其他方面也经常用到。利用快速傅里叶变换，实现了信号频域的变换处理。对于信号的处理，往往会和数学中的算法联系到一起。如果处理得当，将会对气象，地理信息等的发展，起到举足轻重的作用，同时对世界其他领域的发展有很大的促进作用。 关键词: FFT算法，C语言，编译实现
Abstract Discrete Fourier Transform (DFT) is often used to calculate the signal processing to obtain frequency domain signals. DFT algorithm can get the frequency domain characteristics of the signal, because the algorithm is computationally intensive, long-time use, the computer is not conducive to real-time signal processing. So DFT since it was discovered in a relatively long period of time is not to be applied to the actual projects until a new fast discrete Fourier calculation method --FFT is found in discrete Fourier transform was able to actually project has been widely used. FFT is not a new way to get the frequency domain, but the discrete Fourier transform of a fast algorithm. Fast Fourier Transform (FFT) is a digital signal processing important tool that the time domain signal into a frequency-domain signal processing. matched filtering has important applications. FFT is a discrete Fourier transform (DFT) is a fast algorithm, it can be a signal from the time domain to the frequency domain. Some signals in the time domain is not easy to observe the characteristics of what is, but then if you change the signal from the time domain to the frequency domain, it is easy to see out of. This design is required to be familiar with the basic principles of FFT algorithm, based on the preparation of C language program to achieve FFT algorithm real number sequence. Keywords: FFT algorithm, C language compiler to achieve
实验二快速傅立叶变换（FFT）算法实验 一．实验目的 1．加深对DFT算法原理和基本性质的理解； 2．熟悉FFT算法原理和FFT子程序的应用； 3．学习用FFT对连续信号和时域信号进行谱分析的方法，了解可能出现的分析误差及其原因，以便在实际中正确应用FFT。 二．实验设备 计算机，CCS 2.0 版软件，实验箱，DSP仿真器，短接块，导线。 三．基本原理 1．离散傅立叶变换DFT的定义：将时域的采样变换成频域的周期性离散函数，频域的采样也可以变换成时域的周期性离散函数，这样的变换称为离散傅立叶变换，简称DFT。 2．FFT是DFT的一种快速算法，将DFT的N2步运算减少为（N/2）log2N步，极大的提高了运算的速度。 3．旋转因子的变化规律。 4．蝶形运算规律。 5．基2FFT算法。 四．实验步骤 1．复习DFT的定义、性质和用DFT作谱分析的有关内容； 2．复习FFT算法原理与编程思想，并对照DIT-FFT运算流程图和程序框图，了解本实验提供的FFT子程序； 3．阅读本实验所提供的样例子程序； 4．运行CCS软件，对样例程序进行跟踪，分析结果；记录必要的参数。 5．填写实验报告。 6．提供样例程序实验操作说明 1）实验前的准备 “语音处理单元”的拨码开关设置：
在信号源单元中，设置左路信号源产生低频正弦波信号，右路产生高频正弦波信号。实验箱上电，用示波器分别观测OUT1和OUT2输出的模拟信号，并调节电位器直至低频正弦波信号为100Hz/1V左右；高频正弦波信号为6KHz/1V左右；将S3中的拨码开关2打到ON，用示波器观测OUT1输出的混叠信号波形。 用导线连接“信号源单元”中2号孔接口OUT1和语音处理单元中的2号孔接口“IN”； 正确完成计算机、DSP仿真器和实验箱的连接后，系统上电. 2）实验过程 启动CCS 2.0，用Project/Open打开“ExpFFT01.pjt”工程文件；双击“ExpFFT01.pjt”及“Source”可查看各源程序；加载“ExpFFT01.out”； 在主程序中，k++处设置断点；单击“Run”运行程序，或按F5运行程序；程序将运行
实验2 基2时域抽选的FFT 程序设计与调试 一、实验目的 掌握信号处理，尤其是数字信号处理的基本原理和方法。要求能通过实验熟练掌握基2时域抽选的快速傅立叶变换算法（FFT ）的基本原理，了解二维及多维快速傅立叶变换算法。 二、实验原理 1．复数类型 对于FFT 算法涉及的复数运算，使用自定义的COMPLEX 来定义复数类型，其使用方法与常规类型（如int,float,double ）相似。 typedef struct { float real, imag; } COMPLEX; 2．FFT 基本原理 FFT 改进了DFT 的算法，减少了运算量，主要是利用了旋转因子W 的两个性质： （a ）W 的周期性：W = W （b) W 的对称性：W =-W FFT 把N 点DFT 运算分解为两组N/2点的DFT 运算，然后求和： )()()(21k X W k X k X k N += 1,,1,0 ),()()2 (2 21-=-=+ N k N k k X W k X N k X 其中， ∑∑∑∑-=-=-=-=+== = = 1 1 2 21 1 112 2 2 2 2 2 2 2 )12()()()2()()(N N N N N N N N r rk r rk r rk r rk W r x W r x k X W r x W r x k X 在计算X 1(k)与X 2(k)时，仍利用上述公式，把它们看成是新的X(k)。如此递归下去，便是FFT 算法。 3．蝶形运算 从基2时域抽选FFT 运算流图可知： ① 蝶形两节点的距离为2m-1，其中，m 表示第m 列，且m =1,… ,L 。 例如N=8=23， 第一级(列)距离为21-1=1， 第二级(列)距离为22-1=2， 第三级(列)距离为23-1=4。 ② 考虑蝶形运算两节点的距离为2m-1，蝶形运算可表为： X m (k)=X m-1(k)+X m-1(k+2m-1) W N r X m (k+2m-1)= X m-1(k)-X m-1(k+2m-1) W N r 由于N 为已知，所以将r 的值确定即可确定W N r 。为此，令k=(n 2n 1n 0)2 ,再将k 左移(L-m)位，右边位置补零，就可得到(r)2 的值，即(r)2 =(k)22L-m 。 例如 N=8=23
128点FFT 算法设计方法 X(k)=127 n 0x n =∑（）w nk 128, X （k ）=63n 0x n =∑（2）w 1282nk +63n 0x n =∑（2+1） w 128(2n+1)k =63n 0x n =∑（2）w 64nk +(63n 0x n =∑（2+1） w 64nk )w 1281k =H(k)+G(k) w 1281k , H(k)= 63 n 0h n =∑（）w 64nk ,h(n)=x(2n) G(k)= 63 n 0g n =∑（） w 64nk ,g(n)=x(2n+1) H(k) = 63n 0h n =∑（） w 64nk =7a 0=∑(7b 0h a b =∑（+8）)w 64(a+8b)k H(k)=H(k 0+8k 1)= 7a 0=∑(7b 0 h a b =∑（+8）)w 64(a+8b)(k0+8k1) =7a 0=∑(7b 0 h a b =∑（+8）w 648bk0)w 64a(k0+8k1)w 6464bk1 =7a 0 =∑(7b 0h a b =∑（+8）w 648bk0)w 64a(k0+8k1) =7a 0 =∑(7b 0h a b =∑（+8）w 8bk0)w 64a(k0+8k1), [w 6464bk1=1] =7a 0 =∑(7b 0f b =∑（）w 8bk0)w 64a(k0+8k1) =7a 0=∑(7b 0 f b =∑（）w 8bk0w 64ak0 )w 648ak1)
=7a 0=∑(7 b 0f b =∑（）w 8bk0w 64ak0 )w 8ak1) w 8bk0旋转因子是1、-1、 等，可以用加减等运算实现，只有w 64ak0要乘旋转因子。 7b 0f b =∑（） w 8bk0用一个蝶8运算。 F(k0)= 7 b 0f b =∑（）w 8bk0,f(b)=h(a+2b), 红色旋转因子还未找到处理方法，使第二级也变为pe8运算 18W =134689222222 ------＝＋＋＋＋＋
DFT 算法原理 快速傅氏变换（FFT ）是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。 设x(n)为N 项的复数序列，由DFT 变换，任一X （m ）的计算都需要N 次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），那么求出N 项复数序列的X （m ）,即N 点DFT 变换大约就需要N2次运算。当N=1024点甚至更多的时候，需要N2=1048576次运算，在FFT 中，利用WN 的周期性和对称性，把一个N 项序列（设N=2k,k 为正整数），分为两个N/2项的子序列，每个N/2点DFT 变换需要（N/2）2次运算，再用N 次运算把两个N/2点的DFT 变换组合成一个N 点的DFT 变换。这样变换以后，总的运算次数就变成N+2（N/2）2=N+N2/2。继续上面的例子，N=1024时，总的运算次数就变成了525312次，节省了大约50%的运算量。而如果我们将这种“一分为二”的思想不断进行下去，直到分成两两一组的DFT 运算单元，那么N 点的DFT 变换就只需要Nlog2N 次的运算，N 在1024点时，运算量仅有10240次，是先前的直接算法的1%，点数越多，运算量的节约就越大，这就是FFT 的优越性。 、FFT 的算法原理 FFT 算法的输出X(K)为自然顺序，但为了适应原位计算，其输入序列不是按x(n)的自然顺序排序，这种经过M-1次奇偶抽选后的排序为序列的倒序。因此，在运算之前应先对序列x(n)进行倒序。倒序的规律就是把顺序数的二进制位倒置，即可得到倒序值。倒序数是在M 位二进制数最高位加一，逢2向右进位。对于 ，M 位二进制数最高位的权值为N/2，且从左到右二进制位的权值依次为 你N/4，N/8，···，2，1。因此，最高位加一相当于十进制运算J+N/2。（J 表示当前倒序数的十进制数值） 实验原理与方法FIR 滤波器 FIR 滤波器的设计问题在于寻求一系统函数)(z H ，使其频率响应)(ω j e H 逼近滤波器 要求的理想频率响应)(ω j d e H ，其对应的单位脉冲响应)(n h d 。 1．用窗函数设计FIR 滤波器的基本方法 设计思想：从时域从发，设计)(n h 逼近理想)(n h d 。设理想滤波器)(ω j d e H 的单位脉 冲响应为)(n h d 。以低通线性相位FIR 数字滤波器为例。
数字信号处理期末大作业FFT的发展史、现状及典型算法 班级 学号： 姓名：
FFT的发展史、现状及典型算法 傅里叶分析已有200多年的历史，目前FFT及其校正算法在工程实际中仍在广泛应用，展现了其不竭的生命力。本次作业我们论述FFT的现状，发展史以及一些算法，去详细了解、扩展这一算法，巩固所学知识。 一．FFT的简介 傅里叶变换是一种将信号从时域变换到频域的变换形式，然而当N很大的时候，求一个N点的DFT要完成N*N次复数乘法和N*（N-1）次复数加法，计算量非常大，所以人们开始探索一种简便的算法对于一个较大的N进行傅里叶变换。在20世纪60年代由Cooley和Tukey提出了快速傅里叶变换算法，它是快速计算DFT的一种简单高效的方法。 关于何为FFT，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。举个例子，设x(n)为N项的复数序列，由DFT 变换，任一X（m）的计算都需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），那么求出N项复数序列的X（m）,即N点DFT变换大约就需要N^2次运算。当N=1024点甚至更多的时候，需要N2=1048576次运算，在FFT中，利用WN的周期性和对称性，把一个N项序列（设N=2k,k为正整数），分为两个N/2项的子序列，每个N/2点DFT变换需要（N/2）2次运算，再用N次运算把两个N/2点的DFT变换组合成一个N点的DFT变换。这样变换以后，总的运算次数就变成N+2*（N/2)^2=N+（N^2）/2。继续上面的例子，N=1024时，总的运算次数就变成了525312次，节省了大约50%的运算量。而如果我们将这种“一分为二”的思想不断进行下去，直到分成两两一组的DFT运算单元，那么N点的DFT变换就只需要Nlog2N次的运算，N在1024点时，运算量仅有10240次，是先前的直接算法的1%，点数越多，运算量的节约就越大，这就是FFT的优越性。 所以使用FFT算法，可以大大提高傅里叶变换的运算速度，运算时间缩短一到两个数量级，从而使DFT变换应用迅速普及，不仅在频谱分析，而且在线性卷积、线性相关等方面得到广泛应用。
目录 1前言 (1) 2FFT算法的基本原理 (2) 2.1系统总体流程图 (2) 2.2 FFT运算规律及编程思想 (2) 2.2.1对图片的选择 (2) 2.2.2 FFT算法的基本原理 (3) 2.2.3 FFT算法的运算规律及编程思想 (4) 3 软件简介 (5) 3.1 Matlab简介 (5) 3.1.1 Matlab软件概况 (5) 3.1.2 Matlab的特点 (5) 3.2 GUI简介 (6) 3.2.1界面设计 (6) 3.3对比结果与分析 (8) 4心得体会 (10) 参考文献 (11) 附录ⅠMatlab源程序 (12) 附录ⅡGUI源程序 (16)
1前言 随着信息时代，数字时代的到来，数字信号处理已经成为一门极其重要的学科和技术领域。以DSP为核心芯片的处理系统日益变成了数字信号处理系统的主流。它广泛用于电子信息、通信、图像处理、语音处理、生物医学、自动控制、地质探测等领域，受到工程设计和使用人员的青睐。 MATLAB，它是美国Math Works公司推出的一种面向工程和科学计算的交互式计算软件。它以矩阵运算为基础，把计算、可视化、程序设计融合在一个简单易用的交互式工作环境中，是一款数据分析和处理功能都非常强大的工程适用软件。通过本次课设我们学会了分析和处理音频信号，首先要对图片信息进行采集，MATLAB的数据采集工具箱提供了一整套命令和函数，通过调用这些函数和命令，可直接控制图像进行数据采集。Window自带的程序也可驱动采集图片信息，并能保存该文件，供MATLAB相关函数直接读取写入。 MATLAB语言是一种数据分析和处理功能十分强大的计算机应用软件，它可以将图像文件变换位离散的数据文件，然后利用其强大的矩阵运算能力处理数据，如数据滤波、傅立叶变换、时域和频域分析、声音回放以及各种图的呈现等，它的信号处理与分析工具箱位语音信号分析提供了十分丰富的功能函数，利用这些功能函数可以快捷而又方便的完成图像信号的处理和分析以及信号的可视化，是人机交互更加便捷。信号处理是MATLAB重要应用的领域之一。 对于有限长序列x(n),若要求其N点的傅里叶变换DFT需要经过2N次复数乘法运算和N*(N-1)次复数加法运算。随着N的增加，运算量将急剧增加，而在实际问题中，N往往是较大的，如当N=1024时，完成复数乘法和复数加法的次数分别为百万以上，无论是用通用计算机还是用DSP芯片，都需要消耗大量的时间和机器内存，不能满足实时的要求。因此，DFT的这种运算只能进行理论上的计算，不适合对实时处理要求高的场合。因此，研究作为DSP的快速算法的FFT是相当必要的，快速傅里叶变换FFT是为提高DFT运算速度而采用的一种算法，快速算法的种类很多，而且目前仍在改进和提高，它是根据离散傅里叶变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。基于本学期所学的DIT-FFT的运算规律和编程思想以及Matlab的学习和使用，本课设要求在Matlab环境下编写基2 DIT-FFT算法实现对离散信号的快速傅里叶变换，再与Matlab软件自带的FFT函数实现对离散信号的傅里叶变换进行比较，如果得到的频谱相同，那么我们编写的程序就是正确的。用GUI界面完成人机交互方便使用的。本课程设计主要是对数字信号的分析。
1前言 (1) 2 FFT算法设计原理 (2) 3基于MATLAB的FFT算法实现与分析 (4) 3.1 MATLAB简介 (4) 3.2 MATLAB中FFT算法实现程序 (6) 3.2.1原图程序及分析 (6) 3.2.2灰度图程序及分析 (7) 3.2.3自建的FFT程序及分析 (8) 3.2.4自建的IFFT程序及分析 (9) 3.2.5内置的FFT程序及分析 (10) 3.2.6内置的IFFT程序及分析 (10) 3.3自建FFT与内置FFT图形及比较 (11) 3.4 IFFT结果与原灰度图形及比较 (12) 4 FFT算法用GUI的实现与分析 (13) 4.1 GUI简介 (13) 4.2 GUI实现FFT算法 (14) 4.2.1界面设计 (15) 4.2.2运行调试 (16) 4.3运行结果分析比较 (17) 5总结体会 (18) 参考文献 (19) 附录I (20) 附录II (24)
数字信号处理(Digital Signal Processing,DSP)是一门涉及许多学科而又广泛应用于许多领域的新兴学科。20世纪60年代以来，随着计算机和信息技术的飞速发展，数字信号处理技术应运而生并得到迅速的发展。数字信号处理是一种通过使用数学技巧执行转换或提取信息，来处理现实信号的方法，这些信号由数字序列表示。在过去的二十多年时间里，数字信号处理已经应用及渗透到许多重要科学和技术领域中，尤其在通信等领域得到极为广泛的应用。 傅里叶变换在信号处理中具有十分重要的作用，但是基于离散时间的傅里叶变换具有很大的时间复杂度，根据傅里叶变换理论，对一个有限长度且长度为的离散信号，做傅里叶变换的时间复杂度为，当很大时，其实现的时间是相当惊人的比如当为时，其完成时间为（为计算机的时钟周期），故其实现难度是相当大的，同时也严重制约了DFT 在信号分析中的应用，故需要提出一种快速的且有效的算法来实现。 正是鉴于DFT 极其复杂的时间复杂度，1965 年和巧妙地利用因子的周期性和对称性，提出了一个DFT 的快速算法，即快速傅里叶变换(FFT)，从而使得DFT 在信号处理中才得到真正的广泛应用。 本文基于时间抽选奇偶分解，利用MATLAB 软件实现快速傅里叶变换。基于所编的FFT 源程序应用的一个实例，本文对有限长度离散时间和连续时间信号进行频谱分析。 DFT是一种应用广泛的数学变换工具，MATLAB是一款功能强大的科学计算语言。MATLAB提供的fft函数解决了DFT的快速计算问题，但由于它是内建函数而不能了解到软件实现的过程。文章以按时间抽取的基2FFT算法为例，根据快速傅里叶变换的原理和规律，绘出了算法实现的程序框图，列出了MATLAB环境下软件实现的程序，建立了从算法理论到程序实现的完整概念。 在信号处理中，DFT（离散傅里叶变换）的计算具有举足轻重的地位。但是基于其复杂的计算，直接应用起来十分麻烦，基于此，本文利用MATLAB 软件对有限长度信号的DFT 进行改进，提出FFT（快速傅里叶变换），并利用FFT 对所给连续时间和离散时间信号做了频谱分析。
分类号TP000.0 学号 U D C 密级公开 工程硕士学位论文 面向多核向量处理器的FFT算法设计与实现 硕士生姓名 工程领域软件工程 研究方向 指导教师 研究生院 二〇〇一四年三月
论文书脊 （此页只是书脊样式，学位论文不需要印刷本页。） 面 向 多 核 处 理 器 的 FFT 算 法 设 计 与 实 现
Design and Implementation of FFT Based on MultiCore Vector Processor Candidate：Xiang Hongwei Advisor：Associate Researcher Wu Jiazhu A thesis Submitted in partial fulfillment of the requirements for the professional degree of Master of Engineering in Software Engineering Graduate School of National University of Defense Technology Changsha，Hunan，P.R.China （March，2014）
（此页放置《独创性声明》和《学位论文版权使用授权书》复印件，其原件存放在学位申请材料中。）
目录 摘要 (i) ABSTRACT ......................................................................................................... i i 第一章绪论 (1) 1.1 论文研究背景及意义 (1) 1.1.1 FFT应用背景 (1) 1.1.2 多核处理器 (2) 1.1.3 FFT相关研究 (4) 1.2 X-DSP体系结构 (7) 1.2.1 多核结构 (7) 1.2.2 单核结构 (7) 1.2.3 影响算法性能因素 (9) 1.3 汇编程序优化 (10) 1.4 本文研究内容 (11) 1.5 论文组织结构 (12) 第二章基2 FFT算法设计与实现 (13) 2.1 DIT基2 FFT (13) 2.1.1 算法基本原理 (13) 2.1.2 算法分析及优化 (14) 2.1.3 单精度浮点算法映射 (15) 2.1.4 双精度浮点算法映射 (20) 2.2 DIF基2 FFT (22) 2.2.1 算法基本原理 (22) 2.2.2 算法分析及优化 (23) 2.2.3 单精度浮点算法映射 (24) 2.2.4 双精度浮点算法映射 (26) 2.3 测试结果及分析 (29) 2.4 本章小结 (32) 第三章基4 FFT算法设计与实现 (33) 3.1 DIT基4 FFT (33) 3.1.1 算法基本原理 (33) 3.1.2 算法分析及优化 (34)
目录 1引言 (1) 2课程设计内容及要求 (2) 2.1课程设计内容 (2) 2.2课程设计要求 (2) 2.3课程设计目的 (2) 2.3课程设计平台 (2) 3基于MATLAB的FFT算法设计原理 (3) 3.1总体设计流程图 (3) 3.2语音信号的采集 (3) 3.3语音信号的时频分析 (3) 3.4快速傅里叶变换 (6) 3.4.1FFT的运算规律 (8) 3.4.2基于MATLAB的FFT所编写程序的框图 (12) 3.5自编算法与机带算法仿真波形比较 (13) 4设计总结 (16) 参考文献 (17) 附录 (18)
1 引言 随着信息时代，数字时代的到来，数字信号处理已经成为一门极其重要的学科和技术领域。以DSP为核心芯片的处理系统日益变成了数字信号处理系统的主流。它广泛用于电子信息、通信、图像处理、语音处理、生物医学、自动控制、地质探测等领域，受到工程设计和使用人员的青睐。 MATLAB，它是美国Math Works公司推出的一种面向工程和科学计算的交互式计算软件。它以矩阵运算为基础，把计算、可视化、程序设计融合在一个简单易用的交互式工作环境中，是一款数据分析和处理功能都非常强大的工程适用软件。通过本次实习我们学会了分析和处理音频信号，首先要对声音信号进行采集，MATLAB的数据采集工具箱提供了一整套命令和函数，通过调用这些函数和命令，可直接控制声卡进行数据采集。Window自带的录音机程序也可驱动声卡来采集语音信号，并能保存为WA V格式文件，供MATLAB相关函数直接读取、写入或播放。 MATLAB语言是一种数据分析和处理功能十分强大的计算机应用软件，它可以将声音文件变换位离散的数据文件，然后利用其强大的矩阵运算能力处理数据，如数据滤波、傅立叶变换、时域和频域分析、声音回放以及各种图的呈现等，它的信号处理与分析工具箱位语音信号分析提供了十分丰富的功能函数，利用这些功能函数可以快捷而又方便的完成语音信号的处理和分析以及信号的可视化，是人机交互更加便捷。信号处理是MATLAB重要应用的领域之一。 语音信号处理是研究用数字信号处理技术和语音学知识对语音信号进行处理的新兴的学科，是目前发展最为迅速的信息科学研究领域的核心技术之一。通过语音传递信息是人类最重要、最有效、最常用和最方便的交换信息形式。 语音信号的处理与滤波的设计主要是用MATLAB作为工具平台，设计中涉及到声音的录制、播放、存储和读取，语音信号的抽样、频谱分析，滤波器的设计及语音信号的滤波，通过数字信号处理课程的理论知识的综合运用。从实践上初步实现对数字信号的处理。
※※※※※※※※※ ※※ ※※ ※※※※※※※※※ 课题名称基于matlab的FFT算法程序设计 姓名 学号 学院 专业 指导教师
基于matlab 的FFT 算法程序设计 1 设计目的 （1）掌握FFT 算法程序的matlab 的实现。 （2）了解matlab 中对信号做频谱分析时如何设置参数。 （3）了解FFT 算法的原理。 （4）熟悉信号的各种频谱分析图。 2 设计思路 利用matlab 编程实现 （1） 利用原理分析出该信号的取样频率以及取样点数大概为多少才合适。 （2） 对未进行加噪声的信号进行幅频分析，然后恢复信号。 （3） 将原始信号加进噪声并进行幅频分析，然后恢复信号。 （4） 比对加噪声前后信号的幅频图，看有何区别再进行总结。 3 设计过程 3.1 设计原理 （1） FFT 变换原理 N 点序列的DFT 和IDFT 变换定义式如下： 1 [][]N kn N k x k x n W -==∑ （1） 1 10 1 [][]N kn N k x n X k W N --== ∑ （2） 利用旋转因子 2N j nk kn N W e π-= （3） 具有周期性，可以得到快速算法（FFT ）。 在MATLAB 中，可以用函数 (,)X fft x N = （4） 和
(,)x ifft X N = （5） 计算N 点序列的DFT 正、反变换。 （2） FFT 中选择频率以及采样点的标准 一个模拟信号，经过ADC 采样之后，就变成了数字信号。采样定理告诉我们，采样频率要大于信号频率的两倍，采样得到的数字信号，就可以做FFT （快速傅里叶变换）了。N 个采样点，经过FFT 之后，就可以得到N 个点的FFT 结果。为了方便进行FFT 运算，通常N 取2的整数次方。 假设采样频率为F s ，信号频率F ，采样点数为N 。那么FFT 之后结果就是一个为N 点的复数。每一个点就对应着一个频率点。这个点的模值，就是该频率值下的幅度特性。具体跟原始信号的幅度有什么关系呢？假设原始信号的峰值为A ，那么FFT 的结果的每个点（除了第一个点直流分量之外）的模值就是A 的N/2倍。而第一个点就是直流分量，它的模值就是直流分量的N 倍。而每个点的相位呢，就是在该频率下的信号的相位。第一个点表示直流分量（即0Hz ），而最后一个点N 的再下一个点（实际上这个点是不存在的，这里是假设的第N+1个点，也可以看做是将第一个点分做两半分，另一半移到最后）则表示采样频率F s ，这中间被N-1个点平均分成N 等份，每个点的频率依次增加。例如某点n 所表示的频率为： n F (1)/s n F N =-* （6） 由公式（2-6）可以看出，F n 所能分辨到频率为为F s /N ，如果采样频率F s 为1024Hz ，采样点数为1024点，则可以分辨到1Hz 。1024Hz 的采样率采样1024点，刚好是1秒，也就是说，采样1秒时间的信号并做FFT ，则结果可以分析到1Hz ，如果采样2秒时间的信号并做FFT ，则结果可以分析到0.5Hz 。如果要提高频率分辨力，则必须增加采样点数，也即采样时间。频率分辨率和采样时间是倒数关系。 假设FFT 之后某点n 用复数a+b*i 表示，那么这个复数的模就是A n =根号a*a+b*b ，相位就是： tan 2(,)P a b a = （7） 根据以上的结果，就可以计算出n 点（n≠1，且n<=N/2）对应的信号的表达式为：