第4章快速傅里叶变换〔FFT〕09–10–1.ppt

学习目标 理解按时间抽取的基-2FFT算法的原理、运算流图、所需计算量和算法特点； 理解按频率抽取的基-2FFT算法的原理、运算流图、所需计算量和算法特点； 理解IFFT算法； 运算量 二、 改进的途径 x(n) 长序列————短序列 WNkn 对一个连续时间信号xa(t)采样1秒得到一个4096个采样点的序列，若计算采样信号的4096点DFT。 假定仅对200≤f≤300Hz频率范围所对应的DFT采样点感兴趣。 （1）若直接用DFT，要计算这些值需要多少次复乘？ MN=101×4096=413696 （2）若用基2的DIT-FFT计算，则需要多少次复乘？ N/2log2N=4096/2log24096=24576 N点x(n)序列，构造新序列 y(n)=x(n/2),n为偶数时， y(n)=0，n为奇数时， n=0,1,2,…2N-1， 求：Y(K)与X(K)的关系，K=0,1,2,…. 2N-1 已知x(n)长度为N（N为偶数）。定义两个长度为N/2的序列如下: 其中，G(k)=DFT[g(n)], H(k)=DFT[h(n)],分别为N/2长。 试利用G(k)和H(k)表示出X(k)=DFT[x(n)]，k=0,1,……N-1。 N点x(n)序列，构造新序列 y(n)=x((n))NR2N(n), 试求：Y(k)与X(k)的关系，k=0,1,2,…. 2N-1 2、蝶形运算 基2的DIF-FFT，输入为自然顺序，输出为位倒序； 两节点“距离”为2M-m=2M/2m=N/2m; 第m级运算： §4. 5 IDFT的高效算法 直接调用FFT子程序计算IFFT，则可用下面的方法： 进一步减少运算量的措施： 多类蝶形单元运算 利用旋转因子的特殊值 旋转因子的生成 预先计算出旋转因子的数值存为表格，程序执行中直接查表得到所需旋转因子 实序列的FFT算法 利用DFT的共轭对称性 设x(n)是2N点实数序列， 试用一次N点DFT来计算x(n)的 2N点DFT：X(k), k=0,1,……2N-1。 （2） MN L=M+N-1≈M DIT-FFT(入口奇偶抽) （时域序列奇偶抽取） DIF-FFT (出口奇偶抽) （频域序列奇偶抽取） DIT-IFFT (出口奇偶抽) （时域序列奇偶抽取） DIF-IFFT (入口奇偶抽) （频域序列奇偶抽取） 时域序列在入口 频域序列在出口 时域序列在出口 频域序列在入口 DIF-FFT信号流图 DIT-IFFT信号流图 DIT―IFFT运算流图(防止溢出) 对上式两边同时取共轭，得 例 题 根据DIT―FFT的思想可得到 由于x(n)为实序列，所以X(k)具有共轭对称性，X(k)的另外N点的值为 §4.6 FFT的应用 线性卷积的FFT算法——快速卷积 1. FFT的快速卷积法 有限长单位脉冲响应h(n)与有限长输入信号x(n)的离散线性卷积。 设x(n)为M点，h(n)为N点， 输出为 y(n) =yc(n) =yl (n) L≥M+N-1 讨论：  （1）M ≈ N，则L≈2M-1≈2M，则 99.9 53.9 29.24 16 8.82 5.92 2.78 1.6 0.941 0.572 Km 4096 2048 1024 512 256 128 64 32 16 8 M=N 当M=512 时，运算速度可快16倍； 当M=4096 时， 约快100倍； M越长， 好处越明显。 短序列补很多零，长序列需全部输入后才能计算 存储容量大 运算时间长，处理延时很大，难于实时处理 怎么解决？——块卷积（重叠相加和重叠保留法） m表示第m级迭代，k, j为数据所在行数； 某一级的两个节点k和j的节点变量进行蝶形运算后，得到结果为下一级k, j两节点的节点变量，即每个蝶形的输入、输出数据节点同在一条水平线上； 与其他节点变量无关，即蝶形的两个输出值仍放回蝶形的两个输入所在的存储器中； 每级的N/2 个蝶形运算全部完成后，再开始下一级的蝶形运算； 这样经过M级运算后，原存放输入数据的N个存储单元中依次存放输出的N个值； 这种利用同一存储单元存放蝶形计算输入、输出数据的方法称为原位运算。可以节省存储单元,降低设备成本。 2. 倒位序规律 基2的DIT-FFT的输出X(k)按正常顺序排列在存储单元中，即按X(0)，X(1)，…，X(7)的顺序排列； 输入x(n)却不是按自然顺序存储的，而是按x(0)，x(4)， …， x(7)的顺序存入存储单元，看起来好像是“混乱无序”的； 实际上是有规律的，我们称