数字电路zw4 - 图文

第四章 快速傅里叶变换(FFT)

4.1引言

4.2直接计算DFT的问题及改进的途径

4.3按时间抽选(DIT)的基-2 FFT算法(库利-图基算法)

一、 算法原理

图4-1时间抽选法蝶形运算流图符号

图4-2按时间抽选，将一个N点DFT分解为两个N/2点DFT

图4-3由两个N/4点DFT组合成一个N/2点DFT

图4-4按时间抽选，将一个N点DFT分解为四个N/4点DFT(N=8)

图4-5 N=8按时间抽选法FFT运算流图

二、 运算量

图4-6直接计算DFT与FFT算法所需乘法

2

数字信号处理教程（第三版）

三、 按时间抽选的FFT算法的特点

图4-7按时间抽选蝶形运算结构 图4-8描述倒位序的树状图

图4-9倒位序的变址处理

图4-10按时间抽选，输入自然顺序、输出倒位序的FFT流图 图4-11按时间抽选，输入输出皆为自然顺序的FFT流图

图4-12按时间抽选，各级具有相同几何形状，输入倒位序、输出自然顺序的FFT流图 图4-13按时间抽选，各级具有相同几何形状，输入自然顺序、输出倒位序的FFT流图

4.4按频率抽选(DIF)的基-2 FFT算法(桑德-图基算法)

一、 算法原理

图4-14按频率抽选蝶形运算流图符号

图4-15按频率抽选，将N点DFT分解为两个N/2点DFT的组合(N=8) 图4-16按频率抽选，将一个N点DFT分解为4个N/4点DFT(N=8)

图4-17按频率抽选FFT流图(N=8)

二、 原位运算

图4-18按频率抽选蝶形运算结构

三、 蝶形运算两节点间的“距离” 四、 WrN的计算

五、 按频率抽选法与按时间抽选法的异同

数字信号处理教程（第三版）

3

4.5离散傅里叶反变换(IDFT)的快速计算方法

图4-19 IFFT流图(N=8)

4

数字信号处理教程（第三版）

4.6 N为复合数的FFT算法——混合基算法

一、 整数的多基多进制表示形式 二、 N=r1r2的快速算法

图4-20 N=4×2=8的FFT运算流图(只画了一部分)

4.7基-4 FFT算法

图4-21一个基-4 FFT基本运算的信号流图

图4-22按时间抽选基-4 FFT流图

4.8分裂基FFT算法

图4-23分裂基FFT算法(时间抽选)的第一级流图 图4-24分裂基FFT算法的一个基本蝶形运算 图4-25 N=24=16点的分裂基FFT的示意图 图4-26 N=24=16分裂基FFT算法(按时间抽选)的流图

数字信号处理教程（第三版）

5

4.9线性调频z变换(Chirp-z变换)算法

一、 算法的基本原理

图4-27 (a) 线性调频z变换在z平面的螺线抽样； (b) Chirp-z变换运算流程

二、 Chirp-z变换(CZT)的实现步骤

图4-28 Chirp-z变换的圆周卷积图

三、 运算量的估算

4.10线性卷积与线性相关的FFT算法

一、 线性卷积的FFT算法

图4-29重叠相加法图形

2. 重叠保留法

图4-30重叠保留法示意图

图4-31用保留信号代替补零后的局部混叠现象

二、 线性相关的FFT算法 4.11FFT的软件实现

图4-32 FFT数据倒位序流程图 图4-33基-2 按时间抽选FFT流程图 图4-34基-2 FFT算法的C++程序

图4-35按时间抽选、输入自然顺序、输出倒位序FFT流程图(见表4-3)

本文来源：https://www.bwwdw.com/article/cqtw.html