有限长离散变换Finite-LengthdiscreteTransforms.PPT

第五章有限长离散变换 Finite-Length discrete Transforms 本章主要内容 离散傅立叶变换定义 离散傅立叶变换性质 （与DTFT的关系，圆周移位和圆周卷积，DFT的对称性，DFT定理） DFT的应用（实序列的DFT计算，用DFT计算线性卷积） 离散余弦变换 5.1 正交变换 5.2 离散傅里叶变换Discrete Fourier Transform (DFT) DTFT是离散时间信号的傅里叶变换，时域离散，频域连续，周期为2?。 由于计算机只能处理数字信号，而不能处理连续信号，所以必须把信号连续的频谱离散化。 时域 频域 连续，非周期 ? FT ? 连续，非周期 连续，周期 ? FST ? 离散，非周期 离散，非周期 ? DTFT ? 周期，连续 离散周期? DFS ? 离散周期 例 - 5_3.m 同样 5.10用DFT实现线性卷积Linear Convolution Using the DFT 令g[n] 和 h[n] 为长度为 N 和 M的有限长序列 其中 L=N+M-1 定义两个长度为L 的序列： 5.10用DFT实现线性卷积Linear Convolution Using the DFT 因此，yL[n]=g[n]*h[n]=yC[n]=ge[n]*he[n] 图示如下： 5.10.2有限长序列和无限长序列的线性卷积Linear Convolution of a Finite-Length Sequence with an Infinite-Length Sequence 建立一种基于DFT的方法： 重叠相加法Overlap-Add Method 因此，通过 x[n]和h[n]的线性卷积得到的期望序列y[n] ： 由于短线性卷积的结果重叠，且需要将重叠部分加起来得到正确的最后结果，所以上面的实现过程称为重叠相加法 M文件fftfilt可以用来实现上面的方法。 按时间抽取FFT算法Decimation-in-Time FFT Algorithm 方块图所示： 按时间抽取FFT算法Decimation-in-Time FFT Algorithm N=8时按时间抽取FFT算法的完整流图 按时间抽取FFT算法Decimation-in-Time FFT Algorithm 上述改进的FFT算法的另一个吸引人的特性是存储要求。 这种类型的存储位置共享特性通常称之为同址计算，结果明显节省了整个算法的存储要求。 按时间抽取FFT算法Decimation-in-Time FFT Algorithm 当DFT样本X[k]在输出端顺序排列时，输入时域样本x[n] 则以一个不同的顺序排列。 按时间抽取FFT算法Decimation-in-Time FFT Algorithm 因此, 在开始用上面描述的FFT算法运算以前，必须重新排列顺序结构输入的x[n] 用二进制形式表示输入样本点x[n] 和它们顺序重新排列后的样本点，则可得到m和n之间有如下关系： 按时间抽取FFT算法Decimation-in-Time FFT Algorithm m: 000 001 010 011 100 101 110 111 n: 000 100 010 110 001 101 011 111 设 ( b2b1b0 )代表输入序列 x[n]于二进制的序号n。 则在开始进行DFT计算之前，样本 x[b2b1b0 ] 在位置 m= b0b1b2 输出是原输入序列的倒序列。 IDFT 算法Inverse DFT Computation 作业 阅读教材 p.234 to 264 习题 5.8, 5.11, 5.20, 5.21, 5.26, 5.28, 5.41 M3.2, M3.8, M3.9 这些性质可用来进一步降低计算的复杂度。 在得出该总数的过程中, 考虑: 和 的相乘也为复数 对称性 按时间抽取FFT算法Decimation-in-Time FFT Algorithm 改进的蝶形，减少复数乘 改进的按时间抽取FFT算法流图（书 图11.24） 当 时，可分解为M级蝶形，每级都有N/2个蝶形运算。 每一级 N / 2次复数乘； N 次复数加。 则 M级 次复数乘 次复数加 与直接计算DFT的运算量之比 DIT-FFT算法运算量 DIT-FFT算法运算量 长度是 N+M-1， 叠加区间 N ≤ n ≤ N + M