当前课程知识点：测试与检测技术基础 > Week5 测试信号分析与处理（4） (Signal processing IV) > 快速傅里叶变换 (Fast Fourier transform) > 快速傅里叶变换 (Fast Fourier transform)
我们接下来介绍
快速傅里叶变换
我们经常说FFT
实际上它
就是快速傅里叶变换
快速傅里叶变换实际上
在1965年首先由美国的数学家
J.W.Cooley
和J.W.Tukey提出来的
FFT实际上是基于复数的
离散傅里叶变换
它是一般离散傅里叶变换的
一种变形
FFT实际上
是能够有效的减少
我们计算离散傅里叶变换
所需要的乘法的次数的
同样
对于快速傅里叶变换当中
被变换的抽样点数
N如果越多
那么快速傅里叶算法
它的计算量的节省
就越显著
因此说FFT
也就是快速傅里叶变换
在数字信号处理当中
在计算大的整数乘法当中
以及求偏微分方程
等各个领域中
都是有非常广泛的应用
下面我们看一下
快速傅里叶变换
提出的一个基本思想
库利—图基
快速傅里叶变换的算法
是最常见的快速傅里叶算法
这个方法
是分治法作为策略
递归的将长度为N
等于N1×N2的DFT
也就是离散傅里叶分解为
长度分别为N1和N2的
两个较短序列的
离散傅里叶变换
以及与旋转因子的
复数的乘法
是这样的一个过程
这个过程
其实它的基本思想
在1965年的时候
由库利和图基
合作发表的一篇论文当中
就已经开始为很多人所了解
其中库利—图基的
快速傅里叶算法
应该说是最著名的一个应用
它是将序列长为N的
离散傅里叶变换
分割为两个长为N/2的
子序列的DFT
也就是离散傅里叶变换
因此这个应用只适用于
序列长度为2的
幂的离散傅里叶计算
也就是所谓的“基2—FFT”
实际上如同高斯和
库利与图基都指出的那样
所谓的库利—图基的算法
也可以用于
序列的长度N
为任意的因数分解形式的
离散傅里叶变换
也称之为
混合基的快速傅里叶变换
还可以应用于其他的
比方说像
分裂基快速傅里叶变换等等
变种的方法
我们请各位同学记住
所谓的库利—图基算法
它的基本思路就是
采用递归的方法进行计算的
实际上递归是它的一个基本的策略
库利—图基的算法就是把
离散傅里叶变换
分解为较小长度的
多个离散傅里叶变换
因此这种算法
可以同任意其他的
离散傅里叶算法
进行联合的使用
我们可以看到
下面这个2.224式和2.225式
分别是离散傅里叶变换
计算公式
离散傅里叶变换
和逆离散傅里叶变换
前面我们已经谈到过
对于N个点的X（k）
我们需要做N方次的
复数的乘法
和N（N-1）次复数的加法
也就是做一次复数乘法
需要做4次的实数相乘
和2次的实数相加
另外还要做1次的加法
我们就需要做2次的实数的相加
比方说N=1024的时候
就需要总共
这么多次复数的乘法
做这么多次数的
实数的乘法
接下来我们看一看
对于快速傅里叶变换
它的算法的本质
就是充分利用了因子WN的周期性
和对称性
对于对称性和周期性而言
我们可以看到
2.226式和2.227式
在前面我们已经介绍过了
从这个当中可以看到
因子WN 中的
N的平方个元素
只有N个独立的值
其中N/2个值
与其余的N/2个值
的数值是相等的
但是它的符号是相反的
对于快速傅里叶的算法
它的基本思想是
尽量避免运算当中重复的运算
把长序列的
离散傅里叶变换
分割为短序列的
离散傅里叶变换的
线性的组合
从而达到整体降低运算量的目的
当然它的效果
也就可以显现出来了
它的效果就是使
原来的N点的离散傅里叶变换的
乘法计算量
从N的平方次
降低为N/2乘以log2N次
如N=1024
那么它的计算量就为5120次
仅为原来计算量的4.88%
可以看到
应该说计算效率提高了很多
计算量也降低了很多
下面我们看一看
实数的离散傅里叶变换数据
与复数的离散傅里叶变换数据
表达形式我们可以做一个比较
在右边的图当中
上面是实数的离散傅里叶变换
下面是复数的离散傅里叶变换
对于实数的离散傅里叶变换
是将N个点时域信号
在频域表示为两组的N/2+1个点的
频域的信号
对于复数的DFT
也就是离散傅里叶变换
它是将两组的N点时域信号
转换成两组的N点的频域的信号
这个时候两组的时域信号
就被称为实部和虚部
实数的离散傅里叶变换
转换为复数的离散傅里叶变换
这个过程实际上就是将
N个点的实数的信号
转入复数离散傅里叶变换的
时域的实部
将虚部用0去进行填充
我们看一下
快速傅里叶变换的工作原理
首先是将
一个包含有N点的时域信号
分解成N个时域的信号
其中每个信号
只包含一个点
然后我们就计算出
这N个时域信号相对应的N个频谱
最后我们将N个频谱
合成为一个频谱
我们就得到了
原信号的傅里叶变换
可以看到
这就是快速傅里叶变换
它的工作原理
实际上就分这三个主要的步骤
具体而言
我们对于快速傅里叶变换
时域信号进行分解
可以看一下
实际上就是
对于一个信号点数
N为2的整数次幂的时候
我们对于每次信号进行分解
都是采用所谓的
交叉分解这种方法
就是将信号一分为二
首先我们将
16点信号分为两个八个点的信号
第二步我们将数据分解为
4个4点的信号
直到我们把信号分解为
N个1点的信号为止
实际上
信号的分解所需要的步数
就是以2为底的对数的N
下面这张图
就是快速傅里叶变换分解的图
可以看一下
一个16点的信号
怎么变成2个8点的信号
和4个4点的信号
以及8个2点的信号
最后是16个1个点的信号
接下来我们看看
经过那样的分解之后
实际上信号每一次
都被分解成为
偶数的抽样点
和奇数的抽样点
分解过程是对
信号抽样点重新的排序
原始信号的点
它的序号
与重新排列的信号点的序号
在二进制数表示当中
存在反转的关系
右边这张图
就是我们刚刚叙述的
这样的一个过程
FFT位是反转排序的
是这样一个过程
接下来我们看看
对于快速傅里叶变换
它的时域信号分解
我们利用的是一种
未反转分类的算法来实现的
也就是通过把N个时域信号
抽样点序号的二进制数值
从左到右反转来去实现的
这就是所谓的
未反转的分类算法
下面我们看一下
对于快速傅里叶变换
它的频谱是如何合成的
它的频谱的合成过程是
每次只能返回一步的合成
比方说对于一个16点的信号
第一步
它的频谱合成
只能将16个单点信号
合成为8个2点的频谱
第二步
将8个2点的频谱
合成为4个4点的这样的频谱
依此类推
当然最后就合成一个16点的频谱
实际上频谱合成的过程
它是与时域信号交叉分解过程的
一个逆的过程
下面举个例子
用两个4点的频谱
合成1个8点的频谱合成的过程
我们可以看到
用0分别填充4点信号
使它成为8点的信号
并相加得到8点的信号
填充的过程当中
是采用不同的策略的
其中第一个信号
偶数点填0
第二个奇数点填0
实际上对于奇数点填0的信号
我们通常可以认为是
经过时移抽样点得到的
它的频谱
需要与一个正弦的曲线相乘
我们知道
时域信号当中
它的移位等于采样移位Δ函数
对信号进行卷积
它的频谱
应对应乘以正弦曲线
右边这张图
分别在时域和频域
FFT合成的这样一个过程
下面就是8点的频谱合成的
蝶形运算的示意图
我们可以看到
奇数序列的4点的频谱
和偶数序列的4点的频谱
合成的过程
这个合成的过程
就是一个蝶形运算
最后我们看一下
对于快速傅里叶变换
它是如何实现的基本流程
是什么样子
对于快速傅里叶变换而言
首先我们要对它进行时域的分解
是采用未反转的排序的算法
把N点信号分解成N个单点的信号
接下来就要进行频域的合成
计算单点信号的频谱
采用蝶形运算
来分布合成多点的频谱
最后是蝶形运算循环次数
为log2 N
右边这个图是
快速傅里叶程序的流程图
也就是我们前面
叙述的这样一个过程
接下来我们看看
如何对快速傅里叶变换
计算的速度进行优化
通常我们是采用
置换计算这种方式
所谓的置换计算是指
同一个数组
被用于数据的输入
以及中间值存储
和数据的输出
置换计算能够很高效的利用
硬件的存储的资源
这种方式就可以提高
快速傅里叶计算的速度
对它进行优化的一个过程
小结一下
对于数字信号处理而言
通常是利用计算机或专用设备
对它进行数字信号处理的
以数值计算的方法
对信号作采集、变换、综合、估值
与识别等处理
对于连续的信号
我们要做离散的傅里叶变换的
三个基本步骤是
时域的采样
时域的截断
和频域的采样
如果采样率过低的话
系列的离散时间序列
就不能够反映
原始信号的波形的特征
频域处理的时候
就会出现频域的混淆
下面我们看看采样定理
采样定理就是
为避免混叠的产生
采样频率fS
必须高于信号频率成分当中
最高频率fmax的两倍
只有低于奈奎斯特频率的频率成分
才能够被精确的采样
这样的过程就是为了避免
频率的混淆
应该使被分析信号的最高频率fmax
低于奈奎斯特频率
信号的时域截断产生泄露
抑制或减小泄露效应的方法
是什么呢
是选择性能更好的
特殊的窗来替代矩形窗
也就是进行加窗的处理
为了避免栅栏效应
我们要对信号做一个整周期的采样
这个结论请大家一定要记住
下面我们给出的小结是
对于快速傅里叶变换而言的
对于快速傅里叶变换
它的基本思想
我们应该掌握的是
首先是为了避免运算当中的重复运算
把长序列的离散傅里叶变换
分割为短序列的
离散傅里叶变换的线性的组合
同时充分利用因子WN 的
周期性和它的对称性
从而达到整体降低运算量的目的
它的运算过程中
每两个等式的运算过程
可以用一个蝶形运算的流程图来表示
我们称这种运算基本单元
叫做蝶形运算单元
对于快速傅里叶变换而言
它的奇偶分解序列
我们是采用的码位倒置的整序
从而达到输入和输出
均按照整序列来进行排序的
好同学们
这一课的内容
我们就讲授到这里
我们下节课再见
-测试技术发展与研究内容 (The development of measurement technology)
-测量的本质与基本前提 (The precondition and foundation of measurement)
-标准及其单位 (Standards and Units)
--标准及其单位
-本章小结 (Chapter summary)
--本章小结
-测试信号分析与处理基础知识 (Basic knowledge of signal processing)
-周期信号的频域描述 (Fourier series)
-非周期信号的频域描述 (Fourier transform)
--非周期信号的频域描述 (Fourier transform)
-Class Exercise1
-Homework1
-傅里叶变换的性质 (The property of Fourier transform)
--傅里叶变换的性质 (The property of Fourier transform)
-功率信号的傅里叶变换 (Fourier transform of power signal)
--功率信号的傅里叶变换 (Fourier transform of power signal)
-本章小结 (Chapter summary)
-Class Exercise2
-Homework2
-随机信号的描述 (Description of random signal)
--随机信号的描述 (Description of random signal)
-随机过程主要特征参数 (Characteristic parameters of stochastic process)
--随机过程主要特征参数 (Characteristic parameters of stochastic process)
-相关分析 (Correlation analysis)
-功率谱分析与巴塞伐尔定理 (Power spectral analysis and Parseval’s theorem)
--功率谱分析与巴塞伐尔定理 (Power spectral analysis and Parseval’s theorem)
-Class Exercise3
-Homework3
-数字信号处理概述 (Outline of digital signal processing)
--数字信号处理概述 (Outline of digital signal processing)
-离散傅里叶变换 (Discrete Fourier transform)
--离散傅里叶变换 (Discrete Fourier transform)
-离散傅里叶变换的性质 (The property of discrete Fourier transform)
--离散傅里叶变换的性质 (The property of discrete Fourier transform)
-采样定理 (Sampling theorem)
-泄漏与加窗 (Spectral leakage and windowing)
--泄漏与加窗 (Spectral leakage and windowing)
-栅栏效应 (Picket fence effect)
-快速傅里叶变换 (Fast Fourier transform)
--快速傅里叶变换 (Fast Fourier transform)
-Class Exercise4
-Homework4
-测试系统概述 (Outline of the measurement system)
--测试系统概述 (Outline of the measurement system)
-测量误差 (Measurement error)
-测试系统的静态特性 (Static characteristics)
--测试系统的静态特性 (Static characteristics)
-测试系统的动态特性 (Dynamic characteristics)
--测试系统的动态特性 (Dynamic characteristics)
-Class Exercise5
-Homework5
-伯德图与奈奎斯特图 (Bode plot and Nyquist plot)
--伯德图与奈奎斯特图 (Bode plot and Nyquist plot)
-一阶惯性系统 (First-order system)
-二阶惯性系统 (second-order system)
--二阶惯性系统 (second-order system)
-测试系统对典型激励的响应函数 (The response function of typical signal stimulus)
--测试系统对典型激励的响应函数 (The response function of typical signal stimulus)
-测试系统实现精确测量的条件 (The preconditions of accurate measurement)
--测试系统实现精确测量的条件 (The preconditions of accurate measurement)
-测试系统的负载效应 (Loading effect)
-Class Exercise6
-Homework6
-被测量获取的基本概念 (Outline of sensors)
--被测量获取的基本概念 (Outline of sensors)
-传感器的分类 (The category of sensors)
--传感器的分类 (The category of sensors)
-电阻式传感器 (Resistive sensors)
-Class Exercise7
-Homework7
-电感式传感器 (Inductive sensors)
-电容式传感器 (Capacitive Sensors)
-压电传感器 (Piezoelectric sensors)
--压电传感器 (Piezoelectric sensors)
-磁电式传感器 (Magnetic sensors)
-Class Exercise8
-Homework8
-霍尔传感器 (Hall sensors)
-图像传感器 (CCD image sensor)
-光纤传感器 (Fiber optic sensor)
-传感器选用原则 (Selection principles of sensors)
--传感器选用原则 (Selection principles of sensors)
-Class Exercise9
-Homework9
-测试信号转换绪论 (The introduction of signal conditioning)
--测试信号转换绪论 (The introduction of signal conditioning)
-电桥 (Bridge circuit)
-调制与解调 (Modulation and demodulation)
--调制与解调 (Modulation and demodulation)
-Class Exercise10
-Homework10
-滤波器概述 (Outline of filter)
-滤波器的一般特性 (The characteristics of filter)
--滤波器的一般特性 (The characteristics of filter)
-滤波器的类型介绍 (The category of filter)
--滤波器的类型介绍 (The category of filter)
-滤波器的综合运用与MATLAB实现 (The application of filter and MATLAB realization)
--滤波器的综合运用与MATLAB实现 (The application of filter and MATLAB realization)
-Class Exercise11
-Homework11
-虚拟仪器技术概述
--虚拟仪器技术概述
-Class Exercise12
-Homework12
