EE261 Lecture 22

课程主页:https://see.stanford.edu/Course/EE261

这次回顾第二十二讲,这一讲介绍了DFT的性质以及快速傅里叶变换。

DFT的性质

Parseval恒等式

证明:

特别的,取$\mathrm{f}=\mathrm{g}$,那么

平移和平移定理

定义

那么

因此

modulation定理

考虑

由定义可得

第$m$个分量为

对$\underline{\mathcal{F}}\left({\omega}^{n} \mathrm{f}\right)$平移$n$个单位可得

上式右边第$m$个分量为

我们得到

卷积

定义

在上述定义下,我们有

利用卷积,我们可得

证明:

那么

所以

因此

平移和卷积

类似连续情形,我们有

所以

$\delta $的更多性质

考虑$\delta $的乘法

对于卷积

类似的,我们有

考虑特殊情形,$f$也为$\delta $函数:

FFT算法

我们知道计算DFT需要$O(n^2)$的计算量,当$n$很大时显然不够高效,有没有方法可以减少计算量呢?FFT就是起到这样作用的算法,其计算量为$O(n\log n)$,下面简单介绍该算法的思想。

一些记号

定义

那么

更一般的,我们有

对于第二项为奇数的情形,我们有

最后考虑一种特殊情形

划分求和

为了简化讨论,这里假设$N$为偶数,那么

利用之前的内容对上式分别处理得到

于是我们得到下式

对于$N-1 \ge m\ge N/2$的情形,我们考虑$m + N/2, m=0,\ldots, N/2-1$即可,注意到

对于奇数项,需要处理$\omega[N,-(m+N / 2)]$

所以

总结

将上述内容总结,我们得到FFT算法

其中$m=0,1, \ldots, N / 2$

本文标题:EE261 Lecture 22

文章作者:Doraemonzzz

发布时间:2019年07月30日 - 10:09:00

最后更新:2019年07月30日 - 10:29:05

原始链接:http://doraemonzzz.com/2019/07/30/EE261 Lecture 22/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。