实验八 利用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)
傅里叶变换在信号处理中的应用 姓名董柱班级电气工程及其自动化学号1109141013 摘要: 傅里叶变换是一种特殊的积分变换。通过傅里叶变换把信号的从时域变换到频域研究,采用频域法较之经典时域的方法有很多突出的优点,虽然傅里叶分析不是信息科学与技术领域中唯一的变换域方法,但是不得不承认,在此领域中,傅里叶变换分析始终有着广泛的应用,通过傅里叶变换实现信号的滤波,调制,抽样是傅里叶变换在信号处理中最主要的作用。通过对信号的调制可以将信号的低频成分调制到高频,实现频谱搬移,减少马间串扰,提高抗噪声新能,有利于信号的远距离传输,另外,对信号采样可以使连续信号离散化,有利于用计算机对信号进行处理,总之,傅里叶变换在信号处理中有着非常重要的作用。傅里叶变换是学习其他频域变换的基础。 关键词: 傅里叶变换,时域,频域,信号处理,信息科学与技术,滤波,调制,抽样。 一傅里叶变换 1.定义 f(t)是t的函数,如果t满足狄里赫莱条件:具有有限个间断点;具有有限个极值点;绝对可积。则有下图①式成立。称为积分运算f(t)的傅立叶变换, ②式的积分运算叫做F(ω)的傅立叶逆变换。F(ω)叫做f(t)的像函数,f(t)叫做 F(ω)的像原函数。F(ω)是f(t)的像。f(t)是F(ω)原像。 ① 傅里叶变换 傅里叶逆变换 2.分类 连续傅立叶变换:一般情况下,若“傅立叶变换”一词的前面未加任何限定语,则指的是“连续傅立叶变换”。“连续傅立叶变换”将平方可积的函数f(t) 表示成复指数函数的积分或级数形式。 f(t) = \mathcal^[F(ω)] = \frac{\sqrt{2π}} \int\limits_{-\infty}^\infty F(ω)e^{iωt}\,dω.
第2章信号分析 本章提要 信号分类 周期信号分析--傅里叶级数 非周期信号分析--傅里叶变换 脉冲函数及其性质 信号:反映研究对象状态和运动特征的物理量信号分析:从信号中提取有用信息的方法 和手段 §2-1 信号的分类 两大类:确定性信号,非确定性信号 确定性信号:给定条件下取值是确定的。 进一步分为:周期信号, 非周期信号。
质量M 弹簧 刚度K t x (t ) o x 0 质量-弹簧系统的力学模型 x (t ) ? ?? ? ??+=0cos )(?t m k A t x 非确定性信号(随机信号):给定条件下取值是不确定的 按取值情况分类:模拟信号,离散信号 数字信号:属于离散信号,幅值离散,并用二进制表示。 信号描述方法 时域描述 如简谐信号
频域描述 以信号的频率结构来描述信号的方法:将信号看成许多谐波(简谐信号)之和,每一个谐波称作该信号的一个频率成分,考察信号含有那些频率的谐波,以及各谐波的幅值和相角。
?- = 2 2 0)(1T T dt t x T a ?- = 2 2 0cos )(2T T n tdt n t x T a ω ? - = 2 2 0sin )(2T T n tdt n t x T b ω 式中 T--周期;0--基频, 0=2 /T 。 三角函数展开式的另一种形式: ) cos()(1 00∑∞ =++=n n n t n A a t x ?ωN 次谐波 N 次谐波的相角 N 次谐波的频率 N 次谐波的幅值 信号的均值,直流分量
C语言实现FFT(快速傅里叶变换) 函数原型:空快速傅立叶变换(Struct Compx *xin,Intn) 函数函数:对输入复数组执行快速傅立叶变换(FFT)输入参数:*xin复结构组的第一个地址指针。结构输出参数:no * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *结构compx u,w,t。 nv2 =快速傅立叶变换_ N/2;nm1 =快速傅立叶变换_ N-1;(I = 0;i
快速傅里叶变换FFT的FPGA设计与实现 学生姓名郭衡 班级电科1704 学号17419002064 指导教师谭会生 成绩 2020年5 月20 日
快速傅里叶变换FFT 的设计与实现 一、研究项目概述 非周期性连续时间信号x(t)的傅里叶变换可以表示为:= )(?X dt t j e t x ? ∞ ∞ --1 )(?,式中计算出来的是信号x(t)的连续频谱。但是,在实际的控制系统中能够式中计算出来的是信号x(t)的连续频谱。但是,在实际的控制系统中能够算信号x(t)的频谱。 有限长离散信号x(n),n=0,1,…,N-1的DFT 定义为: ∑-=-=-==1 02,1.....10)()(N n N j N kn N e W N k W n x K X π、、。 可以看出,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 算法的优越性。 图1 FFT 与DFT 所需乘法次数比 较
X[1] 将x(n)分解为偶数与奇数的两个序列之和,即x(n)=x1(n)+x2(n)。 x1(n)和x2(n)的长度都是N /2,x1(n)是偶数序列,x2(n)是奇数序列,则 ∑∑=--=-=+2 )12(120 2)1.....,0()(2)(1)(N n k n N N n km N N k W n x W n x K X 所以)1...,0()(2)(1)(12 22120 -=+=∑∑-=-=N k W n x W W n x K X N n km N k N km N N n 由于km N N j km N j km N W e e W 2/2 /2222===--ππ ,则 )1.....,0)((2)(1)(2)(1)(12 2/120 2/-=+=+=∑∑-=-=N k k X W k X W n x W W n x K X k N N n km N k N N n kn N 其中X1(k)和X2(k)分别为x1(n)和x2(n)的N /2点DFT 。由于X1(k)和X2(k)均以N /2为周期,且WNk+N/2=-WNk ,所以X(k)又可表示为: )12/....,1,0)((2)(1)(-=+=N k k X W k X K X k N )12/....,1,0)((2)(1)2/(-=-=+N k k X W k X N K X k N
乐山师范学院学生实验报告 实验课程名称: matlab 与信号系统实验 实验日期:2014年 月 日 姓名 学号 同组人 班级 系(院) 专业 级 班 指导老师 一、实验项目名称 连续时间信号傅里叶变换及调制定理 二、实验目的 1.学会用MA TLAB 求符号运算法的傅立叶正反变换; 2. 理解调制对信号频谱的影响 三、实验主要仪器设备仪器、器材、软件等 PC 机与matlab 软件 四、实验原理 见指导书 五、实验内容、步骤 1.求信号)()(t e t f t ε-=的频谱函数,并分别作出原函数与频谱函数的波形。 2.求信号2 )1(2)(ωω ωj j F += 的原函数,并分别作出原函数与频谱函数的波形。 3.设信号)100sin()(t t f π=,载波)(t y 为频率为400Hz 的余弦信号。试用MATLAB 实现调幅信号)(t y ,并观察)(t y 的频谱和)(t f 的频谱,以及两者在频域上的关系。 4.设),10cos( )()(),1()1()(1t t f t f t u t u t f π=--+=,试用MATLAB 画出)(),(1t f t f 的时域波形及其频谱,并观察傅里叶变换的频移特性。 六、实验记录(数据、现象、报表、软件、图象等) 1、 syms t w; f=exp(-1*t).*heaviside(t); y=fourier(f);
y=simplify(y); subplot(121); ezplot(f,[-3,3]); subplot(122); ezplot(w,y,[-2,2]); -2 02 0.10.20.30.40.50.60.70.80.9t exp(-t) heaviside(t) -2 -1 01 2 -3-2 -101 2 34 x y x = w, y = 1/(1+i w) 2、 syms t w ; ft=ifourier((2*w/(1+i*w)^2),t); y=ifourier(ft); y=simplify(y); subplot(121); ezplot(real(ft)); subplot(122); ezplot(imag(ft)); -5 05 -1 -0.8-0.6-0.4-0.200.20.40.60.81 t i exp(-t) heaviside(t) (t-1)-i conj(exp(-t) heaviside(t) (t-1))0 2 4 6 -0.6 -0.5-0.4-0.3-0.2-0.100.10.20.3 t -1/2 i (2 i exp(-t) heaviside(t) (t-1)+2 i conj(exp(-t) heaviside(t) (t-1)))
(4) 2 T 2 T f (t)dt 傅里叶(Fourier )级数的指数形式与傅里叶变换 专题摘要:根据欧拉(Euler )公式,将傅里叶级数三角表示转化为指数表示,进而得到傅 里叶积分定理,在此基础上给出傅里叶变换的定义和数学表达式。 在通信与信息系统、交通信息与控制工程、信号与信息处理等学科中,都需要对各种 信号与系统进行分析。 通过对描述实际对象数学模型的数学分析、 求解,对所得结果给以物 理解释、赋予其物理意义,是解决实际问题的关键。这种数学分析方法主要针对确定性信号 的时域和频域分析,线性时不变系统的描述以及信号通过线性时不变系统的时域分析与变换 域分析。所有这些分析方法都离不开傅里叶变换、拉普拉斯变换和离散时间系统的 z 变换。 而傅里叶变换的理论基础是傅里叶积分定理。 傅里叶积分定理的数学表达式就是傅里叶级数 的指数形式。 不但傅里叶变换依赖于傅里叶级数,就是纯数学分支的调和分析也来源于函数的傅里 叶级数。因此,傅里叶级数无论在理论研究还是在实际应用中都占有非常重要的地位。 我们 承认满足狄里克莱(Dirichlet )条件下傅里叶级数的收敛性结果,不去讨论和深究傅里叶展 式的唯一性问题。 傅里叶级数的指数形式 一个以T 为周期的函数f (t ),在[-T ,T ]上满足狄里克莱条件:1o f (t )连续或只有 2 2 数。在连续点处 有限个第一类间断点; 2。 只有有限个极值点。 那么f (t )在nT,T ]上就可以展成傅里叶级 f(t) a 0 ,. (a n cosn ?t b n sin n ?t) (1) 其中 a n T 2 f (t) cosn tdt, (n 二 0,1,2,), _2 根据欧拉(Euler )公式: b n ;认)州艸(n=1,2,3,), (3) e" - cos : j si , (1)式化为 f(t)二色二 a 2 J e jn e" n jn ? £ j jn ? t +b e —e M n 2j 若令 a n - j b n 一 2 jn ;.-:t . a n jb n ?弓曲 2 」,
#include
傅里叶变换能将满足一定条件的某个函数表示成三角函数(正弦和/或余弦函数)或者它们的积分的线性组合。在不同的研究领域,傅里叶变换具有多种不同的变体形式,如连续傅里叶变换和离散傅里叶变换。最初傅里叶分析是作为热过程的解析分析的工具被提出的。 傅里叶变换属于谐波分析。 傅里叶变换的逆变换容易求出,而且形式与正变换非常类似; 正弦基函数是微分运算的本征函数,从而使得线性微分方程的求解可以转化为常系数的代数方程的求解.在线性时不变的物理系统内,频率是个不变的性质,从而系统对于复杂激励的响应可以通过组合其对不同频率正弦信号的响应来获取; 卷积定理指出:傅里叶变换可以化复杂的卷积运算为简单的乘积运算,从而提供了计算卷积的一种简单手段; 离散形式的傅里叶变换可以利用数字计算机快速的算出(其算法称为快速傅里叶变换算法(FFT)). 1、为什么要进行傅里叶变换,其物理意义是什么? 傅立叶变换是数字信号处理领域一种很重要的算法。要知道傅立叶变换算法的意义,首先要了解傅立叶原理的意义。傅立叶原理表明:任何连续测量的时序或信号,都可以表示为不同频率的正弦波信号的无限叠加。而根据该原理创立的傅立叶变换算法利用直接测量到的原始信号,以累加方式来计算该信号中不同正弦波信号的频率、振幅和相位。 和傅立叶变换算法对应的是反傅立叶变换算法。该反变换从本质上说也是一种累加处理,这样就可以将单独改变的正弦波信号转换成一个信号。 因此,可以说,傅立叶变换将原来难以处理的时域信号转换成了易于分析的频域信号(信号的频谱),可以利用一些工具对这些频域信号进行处理、加工。最后还可以利用傅立叶反变换将这些频域信号转换成时域信号。 从现代数学的眼光来看,傅里叶变换是一种特殊的积分变换。它能将满足一定条件的某个函数表示成正弦基函数的线性组合或者积分。在不同的研究领域,傅里叶变换具有多种不同的变体形式,如连续傅里叶变换和离散傅里叶变换。 在数学领域,尽管最初傅立叶分析是作为热过程的解析分析的工具,但是其思想方法仍然具有典型的还原论和分析主义的特征。"任意"的函数通过一定的分解,都能够表示为正弦函数的线性组合的形式,而正弦函数在物理上是被充分研究而相对简单的函数类:1. 傅立叶变换是线性算子,若赋予适当的范数,它还是酉算子;2. 傅立叶变换的逆变换容易求出,而且形式与正变换非常类似;3. 正弦基函数是微分运算的本征函数,从而使得线性微分方程的求解可以转化为常系数的代数方程的求解.在线性时不变杂的卷积运算为简单的乘积运算,从而提供了计算卷积的一种简单手段;5. 离散形式的傅立叶的物理系统内,频率是个不变的性质,从而系统对于复杂激励的响应可以通过组合其对不同频率正弦信号的响应来获取;4. 著名的卷积定理指出:傅立叶变换可以化复变换可以利用数字计算机快速的算出(其算法称为快速傅立叶变换算法(FFT))。 正是由于上述的良好性质,傅里叶变换在物理学、数论、组合数学、信号处理、概率、统计、密码学、声学、光学等领域都有着广泛的应用。 2、图像傅立叶变换的物理意义 图像的频率是表征图像中灰度变化剧烈程度的指标,是灰度在平面空间上的梯度。如:大面积的沙漠在图像中是一片灰度变化缓慢的区域,对应的频率值很低;而对于地表属性变换剧烈的边缘区域在图像中是一片灰度变化剧烈的区
#include 2 奇偶信号的FS: (i) 偶信号的FS: 2 a n f (t)cosn T] T 1 Fn 弘 1tdt ; bn 2 T1 f (t)sin n 1tdt c n d n a n (ii ) jbn an 2 2 偶的周期信号的 奇信号的FS: F n ( Fn 实, 偶对称);n FS 系数只有直流项和余弦项。 2 T f(t)sinn 1tdt ; 5 dn T| 11 1 Fn F n jbn ( Fn 纯虚,奇对称); a a n 0 ; b n b n 2jFn 第二章连续时间傅里叶变换 1周期信号的频谱分析 一一傅里叶级数FS (1) 狄义赫利条件:在同一个周期 T1内,间断点的个数有限;极大值和极小值的数目有限;信号绝 为T i ,角频率为 ,2 f ,—。 Ti (3)任何满足狄义赫利条件周期函数都可展成傅里叶级数。 ⑷三角形式的FS: (i) 展开式:f(t) a 0 (ancon it bn sin n ,t) n 1 (ii) 系数计算公式: (a) 直流分量: ao f (t)dt T 1 T 1 (b) n 次谐波余弦分量: a n - f (t) cosn 1tdt, n N T1 T 1 2 (c) n 次谐波的正弦分量: bn — f (t)sinn 1tdt, n N T1 T 1 (iii) 系数an 和bn 统称为三角形式的傅里叶级数系数,简称傅里叶系数。 (iv) 称f1 1/T1为信号的基波、基频; nf1为信号的n 次谐波。 (V) 合并同频率的正余弦项得: n 和n 分别对应合并后 门次谐波的余弦项和正弦项的初相位。 (vi) 傅里叶系数之间的关系: (5)复指数形式的FS: (i) 展开式:f (t) Fne jn 1t n (ii) 系数计算:Fn 丄 f(t)e jn 1t dt, n Z T] T 1 (iii) 系数之间的关系: (iv) Fn 关于 n 是共扼对称的,即它们关于原点互为共轭。 (v) 正负n (n 非零)处的Fn 的幅度和等于Cn 或dn 的幅度。 对可积 丁 f(t)dt 。 (2)傅里叶级数:正交函数线性组合。 正交函数集可以是三角函数集 {1,cosn *,sinn 1t :n N}或复指数函数集 {e jn 术:n Z},函数周期 (1)f(t)=u(t+6)-u(t-6) (2)f1(t)=f(-2t) (3)f2(t)=f(t-2) (4)f3(t)=f(t)· 以上四个式子的Matlab编程求其傅里叶变换与幅频特性,相频特性图 dt=0.001 t=-15:dt:15; f=(t>=-6)-(t>=6); k=-600:600; w1=2*pi*k/600; F=f*exp(-j*t'*w1)*dt; subplot(4,3,1); plot(t,f); axis([-15,15,-0.1,1.1]);grid; subplot(4,3,2); plot(w1,abs(F)); axis([-7,7,-1,13]);grid; subplot(4,3,3); plot(w1,angle(F)); axis([-10,10,-5,5]);grid; dt=0.001 t=-15:dt:15; f=(t<=6)-(t<=-3); k=-600:600; w1=2*pi*k/600; F=f*exp(-j*t'*w1)*dt; subplot(4,3,4); plot(t,f); axis([-15,15,-0.1,1.1]);grid; subplot(4,3,5); plot(w1,abs(F)); axis([-7,7,-1,10]);grid; subplot(4,3,6); plot(w1,angle(F)); axis([-10,10,-5,5]);grid; dt=0.001 t=-15:dt:15; f=(t>=-4)-(t>=8); k=-600:600; w1=2*pi*k/600; F=f*exp(-j*t'*w1)*dt; subplot(4,3,7); plot(t,f); axis([-15,15,-0.1,1.1]);grid; subplot(4,3,8); plot(w1,abs(F)); axis([-7,7,-1,13]);grid; subplot(4,3,9); plot(w1,angle(F)); axis([-8,8,-5,5]);grid; dt=0.001; t=-15:dt:15; f=((t>=-6)-(t>=6)).*exp(-j*5*t); k=-600:600; w1=2*pi*k/600; F=f*exp(-j*t'*w1)*dt; subplot(4,3,10); plot(t,f); axis([-10,10,-1.2,1.2]);grid; subplot(4,3,11); plot(w1,abs(F)); axis([-7,7,-1,13]);grid; subplot(4,3,12); plot(w1,angle(F)); axis([-8,8,-5,5]);grid; §2.4 快速傅里叶变换 (FFT) 实现 一、实验目的 1. 掌握FFT 算法的基本原理; 2. 掌握用C 语言编写DSP 程序的方法。 二、实验设备 1. 一台装有CCS3.3软件的计算机; 2. DSP 实验箱的TMS320F2812主控板; 3. DSP 硬件仿真器。 三、实验原理 傅里叶变换是一种将信号从时域变换到频域的变换形式,是信号处理的重要分析工具。离散傅里叶变换(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/ 第四章快速傅里叶变换 有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换(FFT). 1965年,Cooley和Tukey提出了计算离散傅里叶变换(DFT)的快速算法,将DFT的运算量减少了几个数量级。从此,对快速傅里叶变换(FFT)算法的研究便不断深入,数字信号处理这门新兴学科也随FFT的出现和发展而迅速发展。根据对序列分解与选取方法的不同而产生了FFT的多种算法,基本算法是基2DIT和基2DIF。FFT在离散傅里叶反变换、线性卷积和线性相关等方面也有重要应用。 快速傅里叶变换(FFT)是计算离散傅里叶变换(DFT)的快速算法。 DFT的定义式为 )(k X =)()(1 k R W n x N N n kn N ∑-= 在所有复指数值kn N W 的值全部已算好的情况 下,要计算一个)(k X 需要N 次复数乘法和N -1次复数加法。算出全部N 点)(k X 共需2 N 次 复数乘法和)1(-N N 次复数加法。即计算量是与2 N 成正比的。 FFT 的基本思想:将大点数的DFT 分解为若干个小点数DFT 的组合,从而减少运算量。 N W 因子具有以下两个特性,可使 DFT 运算 量尽量分解为小点数的DFT 运算: (1) 周期性:k N n N kn N n N k N W W W )()(++== (2) 对称性:k N N k N W W -=+)2/( 利用这两个性质,可以使DFT 运算中有些项合并,以减少乘法次数。例子:求当N =4时,X(2)的值 通过合并,使乘法次数由4次减少到1次,运算量减少。 FFT 的算法形式有很多种,但基本上可以 华中科技大学 信号与系统课程设论文 快速傅里叶变换(FFT)的计算机实现 学院: 班级: 学号: 姓名: 指导老师: 二〇一三年八月 摘要 用C语言编程完成对输入波形的时域采样的FFT变换以及频域分析,同时用DFT 变换来验证FFT变换结果的正确性。时域信号的输入有两种方式:一种是依次输入时域信号(仅支持多个正弦及余弦信号之和的形式)各谐波分量的幅值和角频率值,另一种是直接输入时域信号的采样值。然后进行DFT变换和FFT变换,两者结果应该是一样的。DFT变换的实现直接脱胎于定义,FFT变换采用的是基2时间抽取算法,用倒位序算法和蝶形算法实现。 关键词:傅里叶变换;DFT; FFT;倒位序 1背景知识 1.1 为什么要进行傅里叶变换 在进行科学研究的过程中,很重要的一点就是为一个系列的问题找到一个通法,从而为实际的应用打下基础。 在信号分析这个方向,如果直接对时域信号进行分析,那么我们将发现,很难找到一种固定的方法来进行分析,这是因为信号对时间t的函数形式存在无数种,我们是无法将这些函数以及这些函数的各种形式的组合都统一起来进行研究的。而进行傅里叶变换之后,我们就能很好达到这个目的——用一种方法来研究所有的信号(这些信号也需要满足一定的条件,但范围是非常广的)。 那么为什么傅里叶变换可以达到这样的目的呢?对于一个时域信号,我们习惯从时间的角度进行理解,也就是以时间为自变量,以信号值为因变量,一个信号是该信号在所有的时间点的值的叠加,每个信号分量在时间域上只占据了一个点,要想得到这个信号的所有信息,我们需要知道这个信号在时间轴上每一点的值,缺一不可。傅里叶变换之后,依然是一个叠加的问题,只不过由时间角度的叠加变成了频率角度的叠加,这时每一个信号分量都覆盖了一个时间域上的整个区间,并且每一个信号分量都是周期性的(三角函数的周期性),这样,只需要知道每个信号分量的幅值、频率、相位就能在时间轴上得到它的所有信息,而所有信号分量的叠加就得到了原来的信号。并且我们并非需要将所有信号分量都叠加起来,这是因为傅里叶变换之后,随着信号分量频率值的上升,信号分量幅值呈一个较快的下降趋势,在精度允许的范围内,我们并不需要去考虑频率值超出某个范围的那部分信号分量,我们所考虑的那个频率区间的信号分量的叠加已经能够很好的还原出原信号,而这个频率区间只占据了频率轴很少的部分,从而简化了后面的分析过程。同时,若原信号是周期性的,那该信号在频率轴上将只占据有限个点,分析难度更是大大减小。 1.2傅里叶级数 1.2.1频率分量与频率成分 对于时域信号来说,频率含量就是信号被分成的正弦波簇所确定的所有频率分量。例如,有 (1-1) 式中,N rad/s 正弦波的相位。 根据式(1-1)其 1-1)定义的信号完全由 频率,振幅和相信的相位所确定。 由式(1-1)定义的信号特征,可以通过对组成该信号的正弦频率,振幅,相位来研究。 1.2.2周期信号的三角傅里叶级数 式: 目录 一、前言 二、设计题目 三、设计要求 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π-= 连续时间周期信号傅里叶级数:?= T dt t x T a )(1 ??--= = T t T jk T t jk k dt e t x T dt e t x T a π ω2)(1 )(1 离散时间周期信号傅里叶级数:[][]()∑∑= - =-= = N n n N jk N n n jkw k e n x N e n x N a /21 1 0π 连续时间非周期信号的傅里叶变换:()? ∞∞ --=dt e t x jw X jwt )( 连续时间非周期信号的傅里叶反变换:()dw e jw X t x jwt ? ∞ ∞ -=π 21 )( 连续时间周期信号傅里叶变换:∑+∞ -∞ =??? ? ? ? -=k k k w a jw X T 22)(πδπ 连续时间周期信号傅里叶反变换:()dw e w w t x jwt ? ∞ ∞ --=0221 )( πδπ 离散时间非周期信号傅里叶变换:∑∞ -∞ =-= n n j e n x e X ωω j ][)( 离散时间非周期信号傅里叶反变换:? = π 2d e )(e π 21][ωωωn j j X n x 离散时间周期信号傅里叶变换:∑+∞ -∞ =-= k k k a X )(π2)e (0 j ωωδω 离散时间周期信号傅里叶反变换:[]ωω ωδωd e n n j ?--=π 20 πl)2(π2π 21][x 拉普拉斯变换:()dt e t s X st -∞ ∞ -? =)(x 拉普拉斯反变换:()()s j 21 t x j j d e s X st ?∞ +∞ -= σσ π Z 变换:∑∞ -∞ =-=n n z n x X ][)z ( Z 反变换: ??-== z z z X r z X n x n n d )(πj 21d )e ()(π21][1j π2ωω 实验六 傅里叶变换及其反变换 6.1实验目的 1.学会运用MATLAB 求连续时间信号的傅里叶变换; 2.学会运用MATLAB 求连续时间信号的傅里叶反变换; 3.学会运用MATLAB 求连续时间信号的频谱图。 6.2实验原理及实例分析 1.连续时间信号傅里叶变换----CTFT 傅里叶变换在信号分析中具有非常重要的意义,它主要是用来进行信号的频谱分析的。傅里叶变换和其逆变换定义如下: ?∞ ∞--= dt e t x j X t j ωω)()( 6.1 ?∞∞-=ωωπωd e j X t x t j )(21)( 6.2 连续时间傅里叶变换主要用来描述连续时间非周期信号的频谱。按照教材中的说法,任意非周期信号,如果满足狄里克利条件,那么,它可以被看作是由无穷多个不同频率(这些频率都是非常的接近)的周期复指数信号e j ωt 的线性组合构成的,每个频率所对应的周期复指数信号e j ωt 称为频率分量(frequency component ),其相对幅度为对应频率的|X(j ω)|之值,其相位为对应频率的X(j ω)的相位。 X(j ω)通常为关于的复函数,可以按照复数的极坐标表示方法表示为: X(j ω)=| X(j ω)|e j ∠ X(j ω) 其中,| X(j ω)|称为x(t)的幅度谱,而∠X(j ω)则称为x(t)的相位谱。 给定一个连续时间非周期信号x(t),它的频谱也是连续且非周期的。对于连续时间周期信号,也可以用傅里变换来表示其频谱,其特点是,连续时间周期信号的傅里叶变换时有冲激序列构成的,是离散的——这是连续时间周期信号的傅里叶变换的基本特征。 2.用MATLAB 实现CTFT 的计算 MATLAB 进行傅里叶变换有两种方法,一种利用符号运算的方法计算,另一种是数值计算。 1) MATLAB 符号运算求解法 MATLAB 符号数学工具箱提供了直接求解傅里叶变换与傅里叶反变换的函数fourier( )及ifourier( )。常用的是:F=fourier(f) 默认返回值是关于ω的函数。 f=fourier(F,t) 返回值是关于t 的函数 例:利用MATLAB 求单边指数信号f(t) = e -2t u(t)的傅里叶变换,画出f(t)及其幅度谱和相位谱图。 syms t v w x phase im re ; %定义符号变量 f = exp(-2*t)*sym('Heaviside(t)'); %f(t)=exp(-2*t)*u(t) Fw = fourier(f); %求傅里叶变换 subplot(311); ezplot(f); %绘制f(t)的时域波形 axis([-1 2.5 0 1.1]); subplot(312); ezplot(abs(Fw)); %绘制幅度谱 im = imag(Fw); %计算F(w)的虚部连续时间傅里叶变换
连续信号的傅里叶变换及matlab显示
快速傅里叶变换 (FFT) 实现
快速傅里叶变换
快速傅里叶变换(FFT)的计算机实现信号与系统课程设计Word
快速傅里叶变换(FFT)的DSP实现
傅里叶变换公式
实验六傅里叶变换及其反变换