下载文档原格式
信号分析与处理课后习题答案第五章 快速傅里叶变换1.如果一台通用计算机的速度为平均每次复乘需要50us ，每次复加需要10us ，用来就散N=1024点的DFT ，问：（1）直接计算需要多少时间？用FFT 计算呢？（2）照这样计算，用FFT 计算快速卷积对信号进行处理是，估计可实现实时处理的信号最高频率？ 解：分析：直接利用DFT 计算：复乘次数为N 2，复加次数为N(N-1)；利用FFT 计算：复乘次数为20.5log N N ，复加次数为2log N N ；（1） 直接DFT 计算：复乘所需时间2215010245052.4288T N us us s =⨯=⨯=复加所需时间2(1)101024(10241)1010.47552T N N us us s =-⨯=-⨯= 所以总时间1262.90432DFT T T T s =+=FFT 计算：复乘所需时间3220.5log 500.51024log 1024500.256T N N us us s =⨯=⨯⨯⨯= 复加所需时间422log 101024log 1024100.1024T N N us us s =⨯=⨯⨯= 所以总时间为340.3584FFT T T T s =+= （2） 假设计算两个N 长序列1()x n 和2()x n 的卷积计算过程为如下：第一步：求1()X k ，2()X k ；所需时间为2FFT T ⨯第二步：计算12()()()X k X k X k =•，共需要N 次复乘运算所需时间为501024500.0512To N us us s =⨯=⨯=第三步：计算(())IFFT X k ，所需时间为FFT T所以总时间为230.35840.0512 1.1264FFT T T To s s s =⨯+=⨯+= 容许计算信号频率为N/T=911.3Hz2.设x(n)是长度为2N 的有限长实序列，()X k 为x(n)的2N 点得DFT 。
快速傅⾥叶变换快速傅⾥叶变换快速傅⾥叶变换（FFT ）是根据计算量的最⼩化原理来设计和实施离散傅⾥叶变换(DFT)计算的⽅法。
1965年，库利（T.W.Cooley ）和图基（J.W.tukey ）发表了著名的《计算机计算傅⾥叶级数的⼀种算法》论⽂。
从此掀起了快速傅⾥叶变换计算⽅法研究的热潮。
快速傅⾥叶变换（FFT ）的出现，实现了快速、⾼效的信号分析和信号处理，为离散傅⾥叶变换(DFT)的⼴泛应⽤奠定了基础。
1.1离散傅⾥叶变换(DFT)的计算设x(n)是⼀个长度为M 的有限长序列，则定义x(n)的N 点离散傅⾥叶变换为∑-===10)()]([)(N n kn NW n x n x DFT k X 其中由于计算⼀个X(k)值需要N 次复乘法和(N-1)次复数加法，因⽽计算N 个X(k)值，共需N2次复乘法和N(N-1)次复加法。
每次复乘法包括4次实数乘法和2次实数加法，每次复加法包括2次实数加法，因此计算N 点的DFT 共需要4N2次实数乘法和(2N2+2N ·(N-1))次实数加法。
当N 很⼤时，这是⼀个⾮常⼤的计算量。
1.2减少DFT 计算量的⽅法减少DFT 的计算量的主要途径是利⽤k N W 的性质和计算表达式的组合使⽤，其本质是减少DFT 计算的点数N 以便减少DFT 的计算量。
k N W 的性质：（1）对称性： (2)周期性： (3) 可约性： (4) 特殊点：选择其中⼀个证明N N j k N j N k N j N k N e e e W 222)2(22πππ--+-+==ππj k N j e e --=2k N j e π2--=k N W -=FFT 算法是基于可以将⼀个长度为N 的序列的离散傅⾥叶变换逐次分解为较短的离散傅⾥叶变换来计算这⼀基本原理的。
这⼀原理产⽣了许多不同的算法，但它们在计算速度上均取得了⼤致相当的改善。
0,1,,1k N =-()*nk nk N N W W -=()()nk N n k n N k N N NW W W ++==nk mnk N mN W W =//nk nk m N N mW W =01N W =/21N N W =-(/2)k N k N NW W +=-在这⾥讨论两类基本的FFT 算法。
第五章离散傅里叶变换及其快速算法 1离散傅里叶变换(DFT)的推导(1) 时域抽样：目的：解决信号的离散化问题。
效果：连续信号离散化使得信号的频谱被周期延拓。
⑵时域截断： 原因：工程上无法处理时间无限信号。
方法：通过窗函数(一般用矩形窗)对信号进行逐段截取。
结果：时域乘以矩形脉冲信号，频域相当于和抽样函数卷积。
(3)时域周期延拓：目的：要使频率离散，就要使时域变成周期信号。
方法：周期延拓中的搬移通过与 、：(t _nT s )的卷积来实现。
表示：延拓后的波形在数学上可表示为原始波形与冲激串序列的卷积。
结果：周期延拓后的周期函数具有离散谱。
经抽样、截断和延拓后，信号时域和频域都是离散、周期的。
过程见图抽样后0 fJif-用于截断原函数J L<Z 用于抽样i4LJI Ji WWtin1 f=1 ----------> --------------t-------------- ►fVtt截断后有卷积波纹i------------- ►t0 I------------------ rfJL 」L延拓后7角ii t飞7Vtfft \ \ t \ f定义DFT用于延拓「ITf处理后信号的连续时间傅里叶变换:I'U N *|nT sr 0 N图1 DFT 推导过程示意图〜 oo "N 4l ~(f)=£ IS h(nTs)ek =^O「j2 飞n/Nn=0-kf o )(i) l~(f)是离散函数，仅在离散频率点f二kf o k—处存在冲激，强度为a k,其T o NT s余各点为0。
〜N N 1(ii) H(f)是周期函数，周期为Nf o == 工，每个周期内有N个不同的幅值。
T o NT s T s(iii) 时域的离散时间间隔(或周期)与频域的周期(或离散间隔)互为倒数。
2 DFT及IDFT的定义DFT定义：设hnT s是连续函数h(t)的N个抽样值n=0,1,…,N J，这N个点的宽度为N 的DFT 为：DFT N h(nT s)]=^ h(nT s)e」2邢/N =H —— J (k =0,1,…，N _1)7 l NT s 丿IDFT定义：设H 上是连续频率函数H(f)的N个抽样值k =0,1，…，N J，这N个点(NT s 丿的宽度为N的IDFT为：DFT N1 H k丄7 H L e」2「nk/N厶nTs , (k =0,1,…，N —1)|L Ns N k 卫NT se^Rk/N称为N点DFT的变换核函数，e j2 flk/N称为N点IDFT的变换核函数。
FFT 快速傅里叶变换(Fast Fourier Transform) 是一种用于快速计算傅里叶变换的算法，是在傅里叶变换的基础上发展而来的。
FFT 算法被广泛应用于数字信号处理、图像处理、声音处理、卷积操作、解析几何等领域，它的高效性和实时性使得它成为了当今计算机科学领域不可或缺的一部分。
一、傅里叶变换简介傅里叶变换是将一个时域信号转换为频域信号的过程，其公式如下：$F(\omega)=\int_{-\infty}^{\infty}f(t)e^{-i\omega t}dt$其中，$f(t)$ 表示时域信号，$F(\omega)$ 表示频域信号，$\omega$ 表示角频率。
傅里叶变换可以分为连续傅里叶变换和离散傅里叶变换两种。
连续傅里叶变换仅适用于连续信号，而离散傅里叶变换适用于离散信号。
二、离散傅里叶变换离散傅里叶变换是一种将离散信号变换为频域信号的方法，其公式如下：$X_k=\sum_{n=0}^{N-1}x_n e^{-\frac{2\pi i}{N}kn},k=0,1,...,N-1$其中，$x_n(n=0,1,...,N-1)$ 表示原始离散信号，$X_k(k=0,1,...,N-1)$ 表示变换后的频域信号。
但是，使用该公式直接计算离散傅里叶变换的时间复杂度为$O(N^2)$，计算效率低下。
三、FFT 快速傅里叶变换FFT 快速傅里叶变换是一种基于DFT 离散傅里叶变换的高效算法，它的时间复杂度可以达到$O(NlogN)$，较之直接计算DFT 的时间复杂度要低得多。
FFT 算法的基本思想是将 DFT 分治成多个较小的 DFT，并利用其重复性降低运算次数。
1.蝴蝶运算蝴蝶运算是 FFT 算法的基本运算，通过它可以将 DFT 的计算复杂度降低为 $O(N)$。
蝴蝶运算的实质是将两个相邻点之间的信号进行乘法和加法运算，其公式如下：$X_k=X_{k1}+W_{N}^kX_{k2},X_{k+N/2}=X_{k1}-W_{N}^kX_{k2}$其中，$X_{k1}$ 表示 $X_k$ 中偶数项，$X_{k2}$ 表示 $X_k$ 中奇数项，$W_N$ 是DFT 的核函数。
