第九章离散傅里叶变换选读.ppt

3 倒位序运算 FFT运算流程中，输出X(k)按正常顺序排 列在存储单元,而输入是按顺序: 这种顺序称作倒位序,即二进制数 倒位。 是由奇偶分组造成的,以N=8为例说明如下: 倒位序的实现 输入序列先按自然顺序存入存储单元,然后经变址运算来实现倒位序排列。 设输入序列的序号为n,二进制为 (n2 n1 n0 )2 ,倒位序顺序用 表示,其倒位序 二进制为(n0 n1 n2 )2 。 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 2 0 1 0 0 1 0 2 3 0 1 1 1 1 0 6 4 1 0 0 0 0 1 1 5 1 0 1 1 0 1 5 6 1 1 0 0 1 1 3 7 1 1 1 1 1 1 7 自然顺序n 二进制n n n 倒位序二进制n n n 倒位顺序n ^ 2 1 0 0 1 2 码位倒序（N=8） 码位倒序（N=16） A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8) x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7) x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) 倒位序的变址处理方法 存储单元 自然顺序 变址 倒位序 蝶距为1 蝶距为2 W N 0 W N 0 W N 0 W 0 N -1 -1 -1 -1 P(0) P(1) Q(0) Q(1) Y(0) Y(1) Z(0) Z(1) W N 0 W N 2 W N 0 W N 2 -1 -1 -1 -1 G(0) G(1) G(2) G(3) H(0) H(1) H(2) H(3) W W W W N 0 N 1 N 2 N 3 -1 -1 -1 -1 X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) 4.WNr 的分布规律 第1级： 第2级： …… 第i级: …… 第L级: 5.存储单元 存输入序列 (n),n=0,1, ,N-1, 计N 个单元; 存放系数 , r=0,1, ,N/2-1, 需N/2个存储单元； 共计(N+N/2)个存储单元。 三、FFT运算量 1． N=2 时，共有L=log N级蝶形运算；每一级有N/2个蝶形单元。 2．每一级有N个输入中间数据，且每级只用到本级的输入中间数据，适合于迭代运算。 3．计算量： 每级N/2次复乘法，N次复加。（每蝶形只乘一次，加减各一次）。共有L*N/2=N/2log2N 次复乘法；复加法L*N=Nlog2N 次。与直接DFT定义式运算量相比(倍数) N2/(Nlog2N) 。当 N大时，此倍数很大。 2 L §9-7 DFT的应用 一、利用FFT计算线卷积 1、时域圆周卷积定理 设 则 2、圆周卷积与线卷积的关系 补‘0’ 加长 3、方法 N点FFT N点FFT IFFT x x(n) h(n) y(n) 补“0” 补“0” M L 连续时间 非周期信号 1、时域的离散化与有限化 二、利用DFT逼近连续时间信号的频谱 2、频域的有限化与离散化 3、误差分析 1）.混叠现象 为避免混叠,由抽样定理可知，须满足 其中, 为抽样频率; 为信号的最高频率分量； 或者 其中,T为抽样间隔。 2）.频谱泄漏（截断误差） 在实际应用中，通常将所观测的信号 限制在一定的时间间隔内,也 就是说， 在时域对信号进行截断操作,或称作：加时 间窗,亦即用时间窗函数乘以信号,由卷积定 理可知，时域相乘,频域为卷积,这就造成拖 尾现象,称之为频谱泄漏. 0 n 0 n n 3）.栅栏效应