[工程科技]清华的信号处理原理电子教案2.ppt

☆ DFT的定义是针对任意的离散序列x(nTs)中的有限个离散抽样(0?nN)的，它并不要求该序列具有周期性。 ☆ 由DFT求出的周期离散谱 ☆ 由IDFT重建的信号是离散的周期函数 DFT总结 谱函数的周期为 fs = 1/Ts = N/NTs = N/T0 = Nf0 谱函数关于变元k的周期为 N 谱函数的离散间隔为 f0 = 1/T0 = 1/NTs = fs/N 重建信号的周期为 T0 = 1/f0 = N/Nf0 = N/fs = NTs 对应离散谱的离散间隔的倒数 重建信号的离散间隔为 Ts = 1/fs = 1/Nf0 = T0/N 对应离散谱的周期的倒数 To = NTs fs = Nfo ☆ 实序列的离散谱关于原点和 N/2（如果N是偶数）是共轭对称和幅度对称的。因此，真正有用的频谱信息可以从0?N/2-1范围获得。 ☆ 在时域和频域0?N范围内的N点分别是各自的主值区间或主值周期。 ☆ IDFT重建信号的基频就是频域的离散间隔（或时域周期的倒数），为 f0 = 1/T0 = 1/NTs DFT的性质 线性性 对任意常数am(1?m?M)，有 奇偶虚实性 DFT的反褶与平移（新解释）： 先把有限长序列周期延拓，再作相应反褶或平移，最后取主值区间的序列作为最终结果。 为了便于研究有限长序列的位移特性，需建立“圆周移位”的概念。 m N-1 m N-1+m x(n) x(n) n n O O 若将上述两个序列分别取DFT，则它们的级数取和范围出现差异。前者从0到N-1，后者从m到N-1+m。当时移位数不同时，DFT取和范围要随这改变。这种现象给位移序列DFT之研究带来了不便。 时移性 序列的时移不影响DFT离散谱的幅度 频移性 对称性 把离散谱序列当成时域序列进行DFT，结果是原时域序列反褶的N倍。 如果原序列具有偶对称性，则DFT结果是原时域序列的N倍。 反褶和共轭性 圆卷积 周期均为N的序列x(n)与y(n)之间的圆卷积定义为 仍是n的序列，周期为N 非周期序列之间只可能存在线卷积，不存在圆卷积；周期序列之间存在圆卷积，但不存在线卷积。 时域离散圆卷积定理 频域离散圆卷积定理 时域离散圆相关定理 圆相关 周期均为N的序列x(n)与y(n)之间的圆卷积定义为 仍是n的序列，周期为N 帕斯瓦尔定理 9FFT算法 直接计算DFT的复杂度为O(N2) 计算DFT的计算量： 每算一个H(k)，需要N次复数乘法，N-1次加法。因此，N点DFT需要N*N次复数乘法，N(N-1)次复数加法。 尽管预先算好并保存旋转因子 可以节省部分运算， 但按定义求DFT的运算量仍然很大。 FFT的原理 1 W具有周期性 2 W具有对称性 N点DFT运算可以分解为两组N/2点DFT运算，然后再取和。 经过周期性与对称性简化之后,容易发现DFT运算中存在着不必要的重复计算,避免这种重复,是简化运算的关键. DFT的复杂度与点数N有关！ FFT是DFT的快速算法，不是新的变换方法。其算法基础是：W的两个性质。 其中，k的取值范围是 0~N-1 而He(k)和Ho(k)是N/2点的DFT，其周期是N/2 因此，H(k)DFT的前N/2点和后N/2点都可以用He(k)和Ho(k)来表示 于是，N点H(k)用N/2点的He(k)和Ho(k)来计算的公式为： 0 4 2 6 1 5 3 7 0 4 2 6 1 5 3 7 0 4 2 6 1 5 3 7 0 4 2 6 1 5 3 7 0 4 2 6 1 5 3 7 0 4 2 6 1 5 3 7 0 4 2 6 1 5 3 7 0 4 2 6 1 5 3 7 0 4 2 6 1 5 3 7 0 4 2 6 1 5 3 7 0 4 2 6 1 5 3 7 0 4 2 6 1 5 3 7 0 4 2 6 1 5 3 7 0 4 2 6 1 5 3 7 X(k) x(n) N/4点DFT N/4点DFT N/4点DFT N/2点 DFT N/4点DFT N/2点 DFT N 点 组 合 相 加 第一级 第二级 第三级 FFT逐级分解 FFT运算流程图 第一级 第二级 第三级 蝶形运算单元 群 FFT蝶形运算单元 一个蝶形单元只需一次复数乘法和两次复数加法 可以共享 FFT算法流程说明 ☆ 全部计算分解为M级，或称为M次迭代。 ☆ 输入序列x(n)按码位倒读顺序排列，输出序列X(k)按自然顺序排列。 ☆ 每级都包含N/2个蝶形单元。 ☆ 每级的若干蝶形单元组成“群”。第1级群数为N/2，第2级群数为N/4，……第i级群数为N/2i，最后一级的群数为1。 ☆ 每个蝶形单元都包含乘Wnk与-Wnk的运算（可简化为乘Wnk与加、减法各一次）。 ☆ 同一级中