第六章_和DFT有关的几个问题.ppt

* * * * * 2. 利用 DFT 进行频谱分析 f/(Hz) f/(Hz) f/(Hz) f/(Hz) |X(ejω)| |X(ejω)| |X(ejω)| |X(ejω)| 参数选择的步骤与方法： 如果已知信号 x(t) 的最高频率 fm，为了防止混叠，选定抽样频率 fs 满足 fs ≥ 2fm；如果不知道信号 x(t) 的最高频率 fm，抽样频率可依照具体的应用要求或采集设备的能力选定，然后采用抗混叠滤波器防止混叠现象发生。 根据实际需要选定频率分辨率 Δf，然后即可确定做 DFT所需的点数 N= fs /Δf 。 fs 和 N 确定以后，即可确定所需信号 x(t) 的长度 T= N / fs = NTs。 2. 利用 DFT 进行频谱分析 DFT及IDFT 表达式： 令 3. 快速傅里叶变换 改写为矩阵形式： 3. 快速傅里叶变换 DFT 的计算量： 为了计算 N 点 DFT 需要 N2 次复数乘法和 N(N-1) 次复数加法，而每次复数乘法需要四次实数乘法和两次实数加法，每次复数加法需要两次实数加法，因此实现 N 点 DFT总共需要 4N2 次实数乘法和 2N(N-1)+2N2 次实数加法。 当N=1024 时，将需要 400 多万次的实数乘法和实数加法运算！ 3. 快速傅里叶变换 1965年，库利（Cooley）和图基（Tukey）首先提出后来被称为快速傅里叶变换（fast Fourier transform, FFT）的DFT快速算法。 FFT 算法的原理和依据主要有两点，第一点是充分利用 WN 因子的性质： ①周期性 ②对称性 如果 N 为偶数，则有 ③可约性 3. 快速傅里叶变换 单位圆 ※ ※ ※ ※ ※ ※ ※ ※ 利用上述 WN 因子的性质，4 点 DFT 矩阵可逐步简化如下： 周期性 对称性 由此可见， DFT 矩阵可约简化成为大部分元素都是 1 或 -1的矩阵，且非 1 或 -1的元素有重复。随着 N 的增大，矩阵中 1 或 -1元素的比例近于指数的增长，因此将大大减小 DFT 的 计算量。 3. 快速傅里叶变换 FFT 算法原理和依据的第二点是：N 点 DFT 运算可分解为两组N/2 点 DFT 运算。 令 N=2M，M 为整数，把 N 点序列 x(n) 按照 n 为偶数和奇数分为两个 N/2 点序列 x(2r) 和 x(2r+1),而 r=0,1,…,N-1/2,于是有 令 3. 快速傅里叶变换 则有 A(k) 和 B(k)都是 N/2 点的 DFT,而 X(k) 是 N 点 DFT，因此用上式表示 X(k) 并不完全，但是因为 因此用A(k) 和 B(k)能够完全的表示 X(k)。 按照上述方法继续分下去，直到两点 DFT 为止： 以上算法是将时间n按照奇偶分开，故称为时间抽取算法（decimation in time, DIT） 3. 快速傅里叶变换 8 点 FFT 时间抽取算法信号流图： 3. 快速傅里叶变换 x0(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) x(0) x0(1) x0(2) x0(3) x0(4) x0(5) x0(6) x0(7) -1 -1 -1 -1 x1(0) x1(1) x1(2) x1(3) x1(4) x1(5) x1(6) x1(7) x2(0) x2(1) x2(2) x2(3) x2(4) x2(5) x2(6) x2(7) x3(0) x3(1) x3(2) x3(3) x3(4) x3(5) x3(6) x3(7) X(1) X(2) X(3) X(4) X(5) X(6) X(7) X(0) -1 -1 -1 -1 -1 -1 -1 -1 “级”的概念： 因为 M=log2N, 所以N 点 DFT可分为 M 级。 3. 快速傅里叶变换 x0(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) x(0) x0(1) x0(2) x0(3) x0(4) x0(5) x0(6) x0(7) -1 -1 -1 -1 x1(0) x1(1) x1(2) x1(3) x1(4) x1(5) x1(6) x1(7) x2(0) x2(1) x2(2) x2(3) x2(4) x2(5) x2(6) x2(7) x3(0) x3(1) x3(2) x3(3) x3(4) x3(5) x3(6) x