第六讲离散Fourier变换续与快速Fourier变换

1、第六讲 离散Fourier变换续与快速Fourier变换目录一、离散Fourier变换（DFT）1二、线性卷积与圆周卷积22.1 线性卷积22.2 圆周卷积22.3 时域卷积定理3三、离散Fourier变换的应用3四、考察离散Fourier变换的计算量3五、快速Fourier变换3六、FBP的频域滤波实现问题3一、离散Fourier变换（DFT）对序列，其离散Fourier变换定义为离散Fourier逆变换由下式给出 令 式写成矩阵形式注：有教材将离散Fouerier变换定义在周期序列上，为序列和的周期。这样定义对后面圆周卷积的处理是方便的。二、线性卷积与圆周卷积2.1 线性卷积离散时间信号与

2、的卷积定义为常记为注1：卷积就是加权求和注2：公式求和的范围是到，若序列和均为有限长序列，则当指标使得和没有定义时，可令其值为0；注3：看个视频的例子注4：序列和均为有限长序列，长度分别为和，请考虑两序列卷积的结果的长度。注5：一个练习。，2.2 圆周卷积对周期为的信号和，其圆周卷积定义为 常记为注1：上述圆周卷积定义在周期信号上注2：两信号的周期要相同注3：若考虑两长度为的信号和，可将其圆周卷积定义如下 上式中表示对关于求余所得的余数， 注4：视频注5：一个练习。，注6：可以将式写成矩阵形式2.3 时域卷积定理以表示的离散Fourier变换，则 证明： 考虑 再看右端恰为的IDFT。两端做离

3、散Fourier变换即得式。三、离散Fourier变换的应用离散Fourier变换的一个重要应用就是计算线性卷积。然而离散Fourier变换的卷积性质是跟圆周卷积相关的。考虑，如何利用离散Fourier变换计算线性卷积。四、考察离散Fourier变换的计算量考虑离散Fourier变换 注意，上式是个方程的计算，每计算一个需要进行次复数乘法和次复数加法。因此要完成全部运算共需次复数乘法和复数加法。随着增大，运算工作量将迅速增加，例如需要100次复数乘法运算，而当时，就需要一百多万次复数乘法运算。按照这种规律，如果较大的情况下，要求对信号进行实时处理，所需的运算速度就难以实现。幸运的是我们有FFT

4、，它能够将DFT的计算复杂度将为。五、快速Fourier变换快速Fourier（Fast Fourier Transform，FFT）是计算离散Fourier变换的一种特殊方法。FFT通过充分挖掘中矩阵的性质，来简化计算。以下仅考虑的情形。矩阵 其中，下面我们就考察和的性质。 取某些值时，的表达是简单的 对称性 周期性 矩阵中，关于的最高次幂是。利用上述两个性质， 中最多有多少个不同的数？注意到在矩阵中的某些数是非常简单的。例如，实际上无需做乘法运算，在较大的情况下，这一因素可使运算工作略有减少；再考虑到系数的周期性和对称性，合理安排重复出现的相乘运算，将使计算工作量显著减少。 （3）把点DF

5、T运算分解为两组点的DFT运算，然后求和下面证明这种分解是正确的，而且可以减少运算工作量对序列取点DFT。把运算分为奇数和偶数两部分 其中分别为的奇数部分和偶数部分构成的子列的DFT。也就是说，一个点的DFT被分解为两个点的DFT。由周期性可知， 又 将，代入有 或者伪代码考察算法的计算量例， 蝶形运算单元每个蝶形运算单元需要一次复数乘法和两次复数加法。由和获得的过程中，共包含个蝶形运算。因此需次复数乘法和次复数加法。对于的情况，需要把这种奇偶分解逐级进行下去。当时，全部DFT运算可分解为级流程图，其中每级都包含次复数乘法和次复数加法，FFT的全部计算量为复数乘法运算：复数加法运算：而直接DFT的计算量为复数乘法运算： 复数加法运算：下图为直接DFT和FFT算法中复数乘法次数与序列长度的关系曲线。以上是对序列长度是时的快速Fourier变换。当序列不是时，也有相应的快速Fourier算法。请有兴趣同学自己查阅相关文献。FFTW是一个开源的FFT库，号称是世界上最快的FFT库。网址是/六、FBP的频域滤波实现问题考虑滤波反投影重建问题I）若投影数据长度为，卷积核应该多长？II