离散傅立叶变换的运算特点.ppt

快速傅立叶变换 2 2 17-1 离散傅立叶变换的运算特点 27-2 按时间抽取的FFT算法 37-3 按频率抽取的FFT算法 47-4 几种特殊的FFT算法 * * 引言 有限长序列通过离散傅里叶变换(DFT)将其频域 离散化成有限长序列。但其计算量太大，很难实时 地处理问题，因此引出了快速傅里叶变换(FFT)。 FFT 并不是一种新的变换形式，它只是DFT 的一种 快速算法。并且根据对序列分解与选取方法的不同 而产生了FFT 的多种算法。 FFT: Fast Fourier Transform 1965年，Cooley, Turkey 机器计算傅里叶级数的一种算法 3 3 * * 直接计算DFT的问题及改进途径 离散傅立叶变换（DFT）的定义为： 4 4 k0，1，2，N1 n0，1，2，N1 * * DFT运算量 * * 5 5 复数乘法复数加法 一个X(k)N N 1 N个X(k) （N点DFT） N2N (N 1) 实数乘法实数加法 一次复乘42 一次复加2 一次X (k)4N2N+2 (N 1)=2(2N 1) N个X (k) (N点DFT) 4N 22N (2N 1) 由此看出：直接计算DFT时，乘法次数与加法次数都是 和N的平方成比例的。当N很大时，所需工作量非常可观。 当N=1024点时，直接计DFT需要： 次，即四百多万次的实数乘法运算。这对实时性很强的信号处理 (如雷达信号处理)来讲，它对计算速度有十分苛刻的要求。 可利用DFT运算的系数 的固有对称性和周期性，改善 DFT的运算效率 * * 6 * * 7 8 8 * * 9 9 * * FFTFFT算法分类算法分类 : : 时间抽选法 DIT: Decimation-In-Time 频率抽选法 DIF: Decimation-In-Frequency 7-2 按时间抽取的FFT算法 一、按时间抽取的算法原理 二、按时间抽取的算法特点 三、按时间抽取FFT算法的其他形式 11 11 * * 一、按时间抽取的算法原理 设序列点数 N = 2L，L 为整数。 若不满足，则补零 N为2的整数幂的FFT算法称基-2FFT算法。 将序列x(n)按n的奇偶分成两组： 1212 * * 1313 则x(n)的DFT: * * 1414 再利用周期性求X(k)的后半部分 * * 1515 一个“蝶形运算”包含1次乘法，2次加法 * * 1616 * * 复数乘法复数加法 一个N / 2点DFT(N / 2)2N / 2 (N / 2 1) 两个N / 2点DFTN 2 / 2N (N / 2 1) 一个蝶形12 N / 2个蝶形N / 2N 总计 1717 分解后的运算量： 运算量减少了近一半 * * N / 2仍为偶数，进一步分解：N / 2 N / 4 1818 * * 19 1919 同理： 其中： 这样逐级分解，直到2点DFT 2020 N=2xk=x0, x1 * * 2121 x0 x2 x1 x3 X10 X11 X20 X21 2点DFT 2点DFT -1 -1 -1 -1 X 0 X 1 X 2 X 3 * * 2222 * * 2323 4点DFT 4点DFT x0 x2 x4 x6 x1 x3 x5 x7 X10 X11 X12 X13 X20 X21 X22 X23 X 0 X 1 X 2 X 3 X 4 X 5 X 6 X 7 -1 -1 -1 -1 * * 2424 4点DFT 4点DFT x0 x2 x4 x6 x1 x3 x5 x7 X10 X11 X12 X13 X20 X21 X22 X23 X 0 X 1 X 2 X 3 X 4 X 5 X 6 X 7 -1 -1 -1 -1 8点基2时间抽取FFT算法流图 * * 2525 第一级 第二级第三级 * * 2626 1.计算速度 当N = 2L时，共有L级蝶形，每级N / 2个蝶形，每 个蝶形有1次复数乘法2次复数加法。 复数乘法： 复数加法： 比较DFT * * 2727 * * 2828 复乘次数 N N 2 * * 例 .如果一台通用计算机的速度为平均每次复乘 ， 每次复加 ，用它来计算512点的 ，问 直接计算需要多少时间，用 运算需要多少时间。 解：(1)直接利用 计算： 复乘次数为 ，复加次数为 。 复乘所需时间 复加所需时间 所以直接利用DFT 计算所需时间： * * 2929 复乘所需时间 复加所需时间 所以用 FFT 计算所需时间 (2) 利用 计算： 复乘次数为 ，复加次数为 。 * * 3030 2.倒序排列 n0n1n2 000 1 10 1 100 1 10 1 倒位序 自然序 00000000 10041001 01022010 11063011 00114100 10155101 01136110 11177111 3131 3232 倒序 k 0 k 1 k 2 xk 2 k1k0 x00 0 x10 0 x01 0 0 1 0 1 1 12 xk k 0xk 2 k1 0 1 x11 0 x001 x101 x01 1 x111 0 1 0 1 0 1 0 1 * * 3.同址运算 在同一级蝶形运算中，两信号只参与一次运算。 4.蝶距规律 3333 三、按时间抽取FFT算法的其它形式 3434 * * 3535 * * 3636 * * 3737 * * 一、按频率抽取的算法原理 二、按频率抽取的算法特点 三、与按时间抽取算法的对称性 3838 一、按频率抽取的算法原理 设序列点数 N = 2L，L 为整数。 若不满足，则补零 将X(k)按k的奇偶分组前，先将输入x(n)按n的顺序 分成前后两半 3939 4040 则x(n)的DFT: 4141 按k的奇偶将X(k)分成两部分： 令 4242 则X(2r)和X(2r+1)分别是x1(n)和x2(n)的 N / 2点DFT，记为X1(k)和 X2(k) 4343 x1(0) x1(1) -1 x1(2) x1(3) -1 x2(0) x2(1) -1 x2(2) x2(3) -1 N/2点 DFT N/2点 DFT x(0) x(7) x(1) x(2) x(3) x(4) x(5) x(6) X1(0)=X(0) X2(0)=X(1) X1(1)=X(2) X1(2)=X(4) X1(3)=X(6) X2(1)=X(3) X2(2)=X(5) X2(3)=X(7) N /2仍为偶数，进一步分解：N /2 N /4 4444 4545 x3(0) x3(1) -1 -1 x4(0) x4(1) N/4点 DFT N/4点 DFT x1(0) x1(1) x1(2) x1(3) X3(0)=X1(0)=X(0) X4(0)=X1(1)=X(2) X3(1)=X1(2)=X(4) X4(1)=X1(3)=X(6) 逐级分解，直到2点DFT 4646 同理： 其中： 3 N W -1 2 N W -1 1 N W -1 0 N W -1 x0 x4 x1 x5 x2 x6 x3 x7 4点 DFT X0 X6 X2 X4 4点 DFT X1 X3 X5 X7 4848 X0 X6 X4 X2 X1 X5 X3 X7 0 N W 1 N W 2 N W 3 N W -1 -1 -1 -1 x0 x3 x1 x2 x4 x5 x6 x7 0 N W 2 N W 2点 DFT -1 -1 2 N W 0 N W -1 -1 2点 DFT 2点 DFT 2点 DFT 4949 0 N W 1 N W 2 N W 3 N W -1 -1 -1 -1 x0 x3 x1 x2 x4 x5 x6 x7 0 N W 2 N W 2 N W 0 N W X0 X6 X4 X2 X1 X5 X3 X7 0 N W 0 N W 0 N W 0 N W -1 -1 -1 -1 -1 -1 -1 -1 时间抽取和频率 抽取FFT算法： 5050 1.计算速度 当N = 2L时，共有L级蝶形，每级N / 2个蝶形 ，每个蝶形有1次复数乘法2次复数加法。 复数乘法： 复数加法： 无论从流图结构，还是从计算速度来看，按时间抽取算法和按频率无论从流图结构，还是从计算速度来看，按时间抽取算法和按频率 抽取算法这两种抽取算法这两种FFTFFT算法是完全等价的。算法是完全等价的。 2.排序规则 输入序列x（n）是自然顺序的，输出序列X（k是倒 置顺序的。 其整序规则与按时间抽取算法是完全一致的。 5151 3.同址运算 该算法和按时间抽取算法一样也是进行同址运算的。 4.蝶距规律 其蝶形系数的分布规律与按时间抽取算法是完全对称的 。 5252 三、与按时间抽取算法的对称性 二者具有完全对称的蝶距规律 蝶形结构和运算流图也都是完全对称的 需要的复乘和复加次数也相同 频率抽取法运算流图是时间抽取法运算流图的转置， 若知道其中一个，应用转置关系就可以得到另一个。 5353 一、按频率抽取的算法原理 二、按频率抽取的算法特点 三、与按时间抽取算法的对称性 5454 一、按频率抽取的算法原理 设序列点数 N = 2L，L 为整数。 若不满足，则补零 将X(k)按k的奇偶分组前，先将输入x(n)按n的顺序 分成前后两半 5555 5656 则x(n)的DFT: 5757 按k的奇偶将X(k)分成两部分： 令 5858 则X(2r)和X(2r+1)分别是x1(n)和x2(n)的 N / 2点DFT，记为X1(k)和 X2(k) 5959 x1(0) x1(1) -1 x1(2) x1(3) -1 x2(0) x2(1) -1 x2(2) x2(3) -1 N/2点 DFT N/2点 DFT x(0) x(7) x(1) x(2) x(3) x(4) x(5) x(6) X1(0)=X(0) X2(0)=X(1) X1(1)=X(2) X1(2)=X(4) X1(3)=X(6) X2(1)=X(3) X2(2)=X(5) X2(3)=X(7) N /2仍为偶数，进一步分解：N /2 N /4 6060 6161 x3(0) x3(1) -1 -1 x4(0) x4(1) N/4点 DFT N/4点 DFT x1(0) x1(1) x1(2) x1(3) X3(0)=X1(0)=X(0) X4(0)=X1(1)=X(2) X3(1)=X1(2)=X(4) X4(1)=X1(3)=X(6) 逐级分解，直到2点DFT 6262 同理： 其中： 3 N W -1 2 N W -1 1 N W -1 0 N W -1 x0 x4 x1 x5 x2 x6 x3 x7 4点 DFT X0 X6 X2 X4 4点 DFT X1 X3 X5 X7 6464 X0 X6 X4 X2 X1 X5 X3 X7 0 N W 1 N W 2 N W 3 N W -1 -1 -1 -1 x0 x3 x1 x2 x4 x5 x6 x7 0 N W 2 N W 2点 DFT -1 -1 2 N W 0 N W -1 -1 2点 DFT 2点 DFT 2点 DFT 6565 0 N W 1 N W 2 N W 3 N W -1 -1 -1 -1 x0 x3 x1 x2 x4 x5 x6 x7 0 N W 2 N W 2 N W 0 N W X0 X6 X4 X2 X1 X5 X3 X7 0 N W 0 N W 0 N W 0 N W -1 -1 -1 -1 -1 -1 -1 -1 时间抽取和频率 抽取FFT算法： 6666 1.计算速度 当N = 2L时，共有L级蝶形，每级N / 2个蝶形 ，每个蝶形有1次复数乘法2次复数加法。 复数乘法： 复数加法： 无论从流图结构，还是从计算速度来看，按时间抽取算法和按频率无论从流图结构，还是从计算速度来看，按时间抽取算法和按频率 抽取算法这两种抽取算法这两种FFTFFT算法是完全