函数正交变换与离散傅里叶变换.ppt

第二章 函数正交变换与离散傅里叶变换 2.1 函数的正交展开 2.2 离散系统与连续系统的等效性 2.3 离散傅里叶变换及性质 2.4 圆周卷积与线性卷积 2.5 快速傅里叶变换 2.6 其他离散变换及特点 2.1函数的正交展开 2.1函数的正交展开 2.1函数的正交展开 2.1函数的正交展开 2.1函数的正交展开 2.1函数的正交展开 2.1函数的正交展开 2.1函数的正交展开 2.1函数的正交展开 2.1函数的正交展开 2.1函数的正交展开 2.1函数的正交展开 2.2离散系统和连续系统的等效性 2.2离散系统和连续系统的等效性 2.2离散系统和连续系统的等效性 2.2离散系统和连续系统的等效性 2.2离散系统和连续系统的等效性 2.2离散系统和连续系统的等效性 2.2离散系统和连续系统的等效性 2.2离散系统和连续系统的等效性 2.2离散系统和连续系统的等效性 2.2离散系统和连续系统的等效性 2.2离散系统和连续系统的等效性 2.2离散系统和连续系统的等效性 2.2离散系统和连续系统的等效性 2.2离散系统和连续系统的等效性 2.2离散系统和连续系统的等效性 2.2离散系统和连续系统的等效性 2.2离散系统和连续系统的等效性 2.3离散傅里叶变换及性质 2.3离散傅里叶变换及性质 2.3离散傅里叶变换及性质 2.3离散傅里叶变换及性质 2.3离散傅里叶变换及性质 2.3离散傅里叶变换及性质 2.3离散傅里叶变换及性质 2.3离散傅里叶变换及性质 2.3离散傅里叶变换及性质 2.3离散傅里叶变换及性质 2.3离散傅里叶变换及性质 2.3离散傅里叶变换及性质 2.3离散傅里叶变换及性质 2.3离散傅里叶变换及性质 2.3离散傅里叶变换及性质 2.3离散傅里叶变换及性质 2.3离散傅里叶变换及性质 2.3离散傅里叶变换及性质 2.4 圆周卷积与线性卷积 2.4 圆周卷积与线性卷积 2.4 圆周卷积与线性卷积 2.4圆周卷积与线性卷积 2.4圆周卷积与线性卷积 2.4圆周卷积与线性卷积 2.4圆周卷积与线性卷积 2.4圆周卷积与线性卷积 2.4圆周卷积与线性卷积 2.5快速傅里叶变换FFT 2.5快速傅里叶变换FFT 时域抽取基－2FFT算法（DIT-FFT） 典 型 例 题 运算量 FFT算法的特点 DIT-FFT算法其他形式的流图 N=8 时输入是正序、输出是倒码的DIT-FFT运算流图 频域抽取基－2FFT算法（DIF-FFT） 算法的推导 DIF-FFT的蝶式运算流图 DIF-FFT的一次分解运算流图 DIF-FFT的二次分解运算流图 有关说明 逆DFT的快速算法（IFFT） IFFT算法的推导 FFT（IFFT）算法的实现 3、Chirp-z变换 3、Chirp-z变换 3、Chirp-z变换 3、Chirp-z变换 3、Chirp-z变换 3、Chirp-z变换 3、Chirp-z变换 计算步骤： 离散傅立叶变换 DCT 时域抽取基－2FFT算法（DIT-FFT） 例如N=8时的DFT,可以分解为两个N/2=4点DFT, 如下图： 时域抽取基－2FFT算法（DIT-FFT） 同理： , ∴N/2仍可能是偶数,可以进一步把每个N/2点的序列再按其奇偶部分分解为两个N/4的子序列。 时域抽取基－2FFT算法（DIT-FFT） 其中 对 也可进行同样的分解： 时域抽取基－2FFT算法（DIT-FFT） 依次类推：经过M-1次分解后，可将N点DFT分解成N/2个两点DFT。 这样又一次的分解得到4个N/4点DFT，见下图。 例： 试画出N=8时的完整的基-2 DIT-FFT运算流图。 时域抽取基－2FFT算法（DIT-FFT） 由有关算法的讨论知：当 时，总共应有M级分解，每级有N/2个“蝶式运算”。每个“蝶式运算”需一次复数乘、两次复数加运算，这样M级总共需要的运算量为： 如：若N＝1024，直接计算DFT与采用FFT运算量之比约为205，“快速”得以充分体现。 若N足够大，通过直接计算DFT与采用FFT计算其运算量之比为： 时域抽取基－2FFT算法（DIT-FFT） ① 倒码 观察完整的FFT流图能发现有两个特点：倒码和原位运算 倒码即码位倒置：是指将原二进制数的码位倒过来 按从低位到高位排列。 顺序与倒码顺序对照表 0 4 2 6 1 5 3 7 000 100 010 110 001 101 011 000 0