第3章节3函数逼近与快速Fourier变换3-53-6.ppt

* 于是 若 这就证明了（6.5）成立. 即 是正交的. 则 于是 因此， 在 个点 上的 最小二乘傅里叶逼近为 * （6.6） 其中 （6.7） 在（6.6）中， 若 ， 则 为 在点 上的插值函数， 于是由（6.6）得 即 （6.8） * （6.7）是由 求 的过程， 称为 的离散 而（6.8）是由 求 的过程，称为反变换. 傅里叶变换. 简称DFT， * 3.6.2 N点DFT 与快速傅氏变换（FFT） 不论是按（6.7）式由 求 ， 由 求 ， （6.9） 其中 (正变换) 或 (反变换)， 还是由（6.4）计算傅里叶逼近系数 都可归结为计算 是已知复数序列. 或是按（6.8） * 当 较大且处理数据很多时，就是用高速的电子计算 机，很多实际问题仍然无法计算， 如直接用（6.9）计算 ，需要 次复数乘法和 次 复数加法，称为 个操作，计算全部 共要 个操作. 1965年产生了FFT算法，大大提高了运算速度，从而使DFT得到广泛的应用. FFT算法的基本思想就是尽量减少乘法次数. * 用（6.9）计算全部 ， 表面看要做 个乘法， 实际上所有 中， 只有 个不 同的值 特别当 时，只有 个不同的值. 因此可把同一个 对应的 相加后再乘 ，这就 能大量减少乘法次数. * 设正整数 除以 后得商 及余数 ， 则 ， 称为 的 同余数，以 表示. 由于 因此计算 时可用 的 同余数 代替 ，从而推出 FFT算法. 以 为例. 说明FFT的计算方法. 由于 则（6.9）的和是 （6.10） 故有 * 将 用二进制表示为 其中 只能取0或1， 例如 根据 表示法，有 公式（6.10）可表示为 * （6.11） 若引入记号 （6.12） * 则（6.11）变成 它说明利用 同余数可把计算 分为 步，用公式 （6.12）计算. 每计算一个 只用2次复数乘法，计算一个 用 次复数乘法，计算全部 共用 次复数乘法. 若注意 公式（6.12）还可进一步 简化为 * 将这表达式中二进制表示还原为十进制表示： * （6.13） 同样（6.12）中的 也可简化为 即 即 得 * 把二进制表示还原为十进制表示，得 （6.14） 同理（6.12）中 可简化为 即 * 表示为十进制，有 （6.15） * 根据公式(6.13)，(6.14)，(6.15)，由 逐次计算到 见表3-5(略）. 上面推导的 的计算公式可类似地推广到 的情形. 根据公式(6.13)，(6.14)，(6.15)，一般情况的FFT 计算公式如下： * （6.16） 其中 从 出发， 由 到 算到 一组 占用 个复数单元，计算时需给出两组单元， 括号内的数代表它的位置，在计算机中代表存放数的地址. 即为所求. * 这个计算公式除了具有不倒地址的优点外，计算只有两 重循环， 计算过程中只要按地址号存放 则最后得到的 就是所求离散频谱的次序. 外循环 由 计算到 ，内循环 由 计算到 由 计算到 更重要的是整个计算过程省计算量. 由公式看到算一个 共做 次复数乘法， 而最后一步计算 时，由于 * （注意 时 故 ），因此，总共要算 次复数乘法，它比直接用（6.9）需 次乘法 当 时比值是 它比一般FFT的 计算量（ 次乘法）也快一倍. 快得多，计算量比值是 我们称（6.16）的计算公式为改进的FFT算法 .