feng

started from 11.28.2025

首页·个人博客

DFT

我们之前学过离散时间傅里叶变换(DTFT),它针对的是我们的数据据本身是离散时间的

\[\begin{gather}X(e^{jw})=\sum_{n=-\infty}^{\infty}x[n]e^{-jwn}\\x[n]=\frac{1}{2\pi}\int_{-\pi}^{\pi}X(e^{jw})e^{jwn}dw\end{gather}\]

对于DTFT,应用到现实中是有问题的.首先,它的求和是从\(-\infty\)到\(\infty\),这在现实中是不存在的.其次,DTFT做的信号频率还是连续的.一段离散的信号输入一个数字器件,输出必然是离散的.即输出的信号时间是有限的,频率是离散的.于是就出现了离散傅里叶变换(DFT)

\[X(k)=\sum_{n=0}^{N-1}x[n]e^{-j\frac{2\pi}{N}kn}\]

对比DTFT,首先是求和的上下限变成有界的了,其次是原来的\(w\)变成了\(\frac{2\pi}{N}k\),也就是说我们的频率也被离散化了,这样就解决了我们提到的问题.现在我们的频率已经离散化了,而逆变换原本是对频率积分,离散化后就变成求和了

\[x[n]=\frac{1}{N}\sum_{k=0}^{N-1}X(k)e^{j\frac{2\pi}{N}kn}\]

进行上面的离散化后,我们的有效数据缩小到了只有N个,当k=N的时候,\(j\frac{2\pi}{N}kn=j2\pi n\),也就是说相当于旋转了一周,加上了\(2\pi\)的整数倍,即输出是周期的,只是多了个\(\frac{1}{N}\)的线性变换所以令

\[\begin{gather}x=(x[0],x[1]…x[N-1])^T\\X=(X(0),X(1)…X(N-1))^T\end{gather}\]

于是我们可以得到下式

\[X=Fx\]

其中\(F\)是NxN的矩阵,且满足

\[F_{n,k}=e^{-j\frac{2\pi}{N}kn}\]

而反变换就可以写成

\[x=\frac{1}{N}F^HX\]

我们还要考虑傅里叶变换的基本特性.如果傅里叶变换是传统的离散时间傅里叶变换,那么其平移特性满足

\[x(t-t_0)\xleftrightarrow{F}X(e^{jw})e^{-jwt_0}\]

即多出了一个相位因子.现在我们考虑离散傅里叶变换的平移,但是我们发现由于序列只有有限长,进行平移后就移出去了,超出了我\(0\sim N-1\)的范围,那么移出去以后该怎么处理?
离散傅里叶变换的时域和频域不是完全对等的.

\[\begin{gather}X(k)=\sum_{n=0}^{N-1}x[n]e^{-j\frac{2\pi}{N}kn}\\x[n]=\frac{1}{N}\sum_{k=0}^{N-1}X(k)e^{j\frac{2\pi}{N}kn}\end{gather}\]

对于时域信号来说,他只有N的长度(我们把信号截断,只保留了一个周期);但是对于频域来说,它虽然只有k的长度,但它是周期的,这样得到的结果是不对等的.所以我们现在构造

\[\tilde{x}[n]=\sum_{r=-\infty}^{\infty}x[n-rN]\]

相当于在对\(x[n]\)进行周期延拓,即

\[x[n]=\tilde{x}[n],0<n<N-1\Leftrightarrow \tilde{x}[n]=x[n~mod~N]\]

也将\(x[n~mod~N]\)记为\(x[((n))_N]\).
基于\(\tilde{x}[n]\),我们构造一个连续时间的信号\(x_c(t)\),满足

\[x_c(t)=\sum_{n=-\infty}^{\infty}\tilde{x}[n]\delta(t-n)\]

这样处理后,我们就把离散数据和连续数据建立起了关联.而且可以得到

\[x_c(t+N)=\sum_{n=-\infty}^{\infty}\tilde{x}[n]\delta[t+N-n]\xrightarrow{n-N=n’}\sum_{n=-\infty}^{\infty}\tilde{x}[n’+N]\delta[t-n’]=\sum_{n=-\infty}^{\infty}\tilde{x}[n’]\delta[t-n’]x_c(t)\]

也就是说\(x_c(t)\)也以N为周期.一个连续函数有了周期性,就可以分解为傅里叶级数了周期信号的傅里叶表示,代入傅里叶级数的公式得到

\[x_c(t)=\sum_{k=-\infty}^{\infty}a_ke^{jw_0kt}=\sum_{k=-\infty}^{\infty}\alpha_ke^{j\frac{2\pi}{N}kt}\]

而\(w_0=\frac{2\pi}{T}\),对于\(x_c(t)\),其周期为N,因此\(w_0=\frac{2\pi}{N}\).其中

\[\begin{aligned} a_n&=\frac{1}{T}\int_{0}^{T}x_c(t)e^{-jw_0kt}dt=\frac{1}{N}\int_{0}^{N}x_c(t)e^{-j\frac{2\pi}{N}kt}dt \\&=\frac{1}{N}\int_{0}^{N}(\sum_{n=-\infty}^{\infty}\tilde{x}[n]\delta(t-n))e^{-j\frac{2\pi}{N}kt}dt \\&=\frac{1}{N}\int_{-\epsilon}^{N-\epsilon}(\sum_{n=-\infty}^{\infty}\tilde{x}[n]\delta(t-n))e^{-j\frac{2\pi}{N}kt}dt\ \\&=\frac{1}{N}\sum_{n=0}^{N-1}\int_{-\epsilon}^{N-\epsilon}\tilde{x}[n]\delta(t-n))e^{-j\frac{2\pi}{N}kt}dt \end{aligned}\]

而对于该积分来说,只有当t=n时才有值,所以

\[a_n=\frac{1}{N}\sum_{n=0}^{N-1}\tilde{x}[n]e^{-j\frac{2\pi}{N}nk}\]

在\(0\sim N-1\)上,有\(\tilde{x}[n]=x[n]\)于是

\[a_n=\frac{1}{N}\sum_{n=0}^{N-1}\tilde{x}[n]e^{-j\frac{2\pi}{N}nk}=\frac{1}{N}\sum_{n=0}^{N-1}x[n]e^{-j\frac{2\pi}{N}nk}=\frac{1}{N}X[k]\]

解释一下为什么要对积分限做调整,如果按照0到N去积分,刚好踩在了我的求和的点上.这样就会涉及到一个问题,该不该取.但是由于\(x_c(t)\)是周期的,所以我可以把积分限稍作平移,这样就取下不取上了,一定程度上简化了我们的处理.
现在,我们就把频域和时域对应起来了.

\[x_c(t)=\sum_{k=-\infty}^{\infty}\alpha_ke^{j\frac{2\pi}{N}kt}=\frac{1}{N}\sum_{k=-\infty}^{\infty}X[k]e^{j\frac{2\pi}{N}kt}\]

也就是说和频域真正对应的函数应该是\(x_c(t)\).现在回到平移的问题,我构造函数

\[x_c^m(t)=\sum_{n=-\infty}^{\infty}\tilde{x}(n-m)\delta(t-n)\Leftrightarrow \sum_{n=-\infty}^{\infty}\tilde{x}(n’)\delta(t-m-n’)\]

\(x_c\)是对\(\tilde{x}(n)\)做间隔为n的取样,\(x_c^m\)是对\(\tilde{x}(n-m)\)做间隔为n的取样,所以可以理解为,\(x_c^m\)是将\(x_c\)向右平移m个单位
然后接着重复上面的步骤:

\[x_c^m(t)=\sum_{k=-\infty}^{\infty}a_ke^{jw_0kt}=\sum_{k=-\infty}^{\infty}\alpha_ke^{j\frac{2\pi}{N}kt}\]

然后计算\(a_k\),

\[\begin{aligned}a_n&=\frac{1}{T}\int_{0}^{T}x_c(t)e^{-jw_0kt}dt=\frac{1}{N}\int_{0}^{N}x_c(t)e^{-j\frac{2\pi}{N}kt}dt\\&=\frac{1}{N}\int_{0}^{N}(\sum_{n=-\infty}^{\infty}\tilde{x}(n’)\delta(t-m-n’))e^{-j\frac{2\pi}{N}kt}dt\\&=\frac{1}{N}\sum_{n=-\infty}^{\infty}\int_{-\epsilon}^{N-\epsilon}\tilde{x}(n’)\delta(t-m-n’))e^{-j\frac{2\pi}{N}kt}dt\\&=\frac{1}{N}\sum_{n=-\infty}^{\infty}\tilde{x}(n’)e^{-j\frac{2\pi}{N}k(m+n’)}\\&=X(k)e^{-j\frac{2\pi}{N}km}\end{aligned}\]

所以

\[x_c^m(t)=\sum_{k=-\infty}^{\infty}(X(k)e^{-j\frac{2\pi}{N}km})e^{j\frac{2\pi}{N}kt}\]

所以

\[x_c\xleftrightarrow{F}X(k),x_c^m\xleftrightarrow{F}X(k)e^{-j\frac{2\pi}{N}km}\]

可以发现,得到的结果实际上与连续情况一致.由于现在我们的信号已经经过周期延拓了,所以就不存在移出去怎么办的问题了.
回顾上面的过程,我的从一开始的\(x[n]\)经过周期延拓变为\(\tilde{x}[n]\),这样信号就可以写成离散傅里叶级数的形式(DFS),再经过重建为连续信号变为\(x_c(t)\),最后又建立起\(x_c(t)\)和\(X(k)\)的关系.而既然频谱关系已经能够和\(x_c(t)\)产生联系,那么也就能关联起我最开始的离散信号\(x[n]\).而中间从\(x[n]\)到\(x_c(t)\)的过程,本质上来说是解决了时域上移出去的部分怎么处理的问题.而我们的处理方式是,对\(x[n]\)进行周期延拓.即把移出去的部分重新再补到开头,这也就是信号搬移的本质
现在我们从另一个角度考虑这个问题,我们刚才把离散数据周期延拓,然后重建为连续函数,再做连续时间傅里叶变换得到频域关系.
假设我现在有两组数据\(x=(x[0],x[1]…x[n])\),\(y=(y[0],y[1],y[2]…y[n])\)对其做离散傅里叶变换得

\[X(k)=\sum_{n=0}^{N-1}x[n]e^{-j\frac{2\pi}{N}nk},Y(k)=\sum_{l=0}^{N-1}y[n]e^{-j\frac{2\pi}{N}lk}\]

现在计算\(X(k)Y(k)\),得到的结果还是卷积吗?假设

\[Z(k)=X(k)Y(k)\]

做DFT的逆变换得到的数据就是N-1个,但是两个长度为N的数据卷积起来得到的信号长度为2N-1,数据长度对不上了.现在我们来计算

\[\begin{aligned}Z(k)&=\sum_{n=0}^{N-1}x[n]e^{-j\frac{2\pi}{N}nk}\sum_{l=0}^{N-1}y[l]e^{-j\frac{2\pi}{N}lk}\\&=\sum_{n=0}^{N-1}\sum_{l=0}^{N-1}x[n]y[l]e^{-j\frac{2\pi}{N}(l+n)k}\end{aligned}\]

其中\(l\)是\(0\sim N-1\),\(n\)是\(0\sim N-1\),那么\(l+n\)就是\(0\sim 2N-1\),而我们的DFT的\(k\)只有\(0\sim N-1\)所以多出来的部分就被移出去了,而DFT频谱是以N为周期的,于是

\[\begin{aligned}Z(k)&=\sum_{n=0}^{N-1}\sum_{l=0}^{N-1}x[n]y[l]e^{-j\frac{2\pi}{N}(l+n)k}=\sum_{n=0}^{N-1}\sum_{l=0}^{N-1}x[n]y[l]e^{-j\frac{2\pi}{N}((l+n) mod N)k}\\\end{aligned}\]

令\((l+n) mod N=l’\),则\(l=(l’-n)modN\),于是可得

\[\begin{aligned}Z(k) &=\sum_{n=0}^{N-1}\sum_{l’=0}^{N-1}x[n]y[(l’-n)modN]e^{-j\frac{2\pi}{N}l’k}=\sum_{l’=0}^{N-1}(\sum_{n=0}^{N-1}x[n]y[(l’-n)modN])e^{-j\frac{2\pi}{N}l’k}\end{aligned}\]

而这个式子

\[\sum_{n=0}^{N-1}x[n]y[(l’-n)modN]=\sum_{n=0}^{N-1}x[n]y[((l’-n))_N]\]

长的很像卷积,但是和常规线性卷积不同,卷到大于N的时候会卷回去,这样的卷积我们称为循环卷积(圆周卷积),记为\(x\enclose{circle}{*}y\),于是最终得到频域相乘对应时域做循环卷积.

\[X(k)Y(k)=\sum_{l’=0}^{N-1}(x\enclose{circle}{*}y)e^{-j\frac{2\pi}{N}l’k}\]

现在,假设我们有一个线性时不变的滤波器\(\{h(k)\}\),我有一组数据\(\{x[n]\}\),现在我想求出我的输出,实际上就是在求\(h(k)*x[n]\),但是一般来说,滤波器的长度和数据长度往往会差很远.如果要从头卷到尾,运算量非常的大.假设\(h\)的长度是n,\(x\)的长度是N,这样的复杂度是\(O(nN)\).但是我们可以优化,

\[\{h(k)\}\xrightarrow{DFT}H(k),\{x(k)\}\xrightarrow{DFT}X(k)\Rightarrow Z(k)=X(k)H(k)\xRightarrow{IDFT}z(k)=x(k)\enclose{circle}{*}h(k)\]

而\(DFT\)有更快的方法去进行,复杂度只有\(O(nlogn)\).

Pasted image 20251111192318.png

但是现在的问题是,频域上做滤波得到的东西实际上是循环卷积,这和我们想要的线性卷积不是一回事,因此我们需要再做处理.我们需要将信号做分段,然后每一段分别取做卷积关于卷积.
我们在分段的序列后面补上滤波器长度-1的0,然后一路卷积,完成每一段的卷积后直接进行相加,由于在序列后方补了0,而循环卷积等价于将序列进行周期延拓后做线性卷积,再取主值区间.补上0以后我们取的主值区间是序列长度+滤波器长度-1,

5e9253d1c7c661ce0821a09be900a40a.jpg

这样做以后,循环卷积得到的结果和线性卷积就相同了.得到的结果就是线性卷积的结果.
得到每一段的卷积的结果后,再把前一段的后M-1个和后一段的前M-1个进行相加就可以得到完整的卷积的结果.这个方法叫做重叠相加法.

Pasted image 20251111205915.png

如\(x[n]=\{1,2,3,4,5,6,7,8,9\}\),\(h[n]=\{1,2\}\)
直接卷积得到的结果为\(y[n]=\{1,4,7,10,13,16,19,22,25,18\}\)
把\(x[n]\)拆分为\(x_1[n]=\{1,2,3\}\),\(x_2[n]=\{4,5,6\}\),\(x_3[n]=\{7,8,9\}\)
得到的\(y_1[n]=\{1,4,7,6\}\),\(y_2[n]=\{4,13,16,12\}\),\(y_3[n]=\{7,22,25,18\}\)
能这样做的原因是:对于每一块我切割好的输入信号,我直接去对其进行卷积,这样造成的问题是:我的最后m-1位的卷积结果是有缺失的,而缺失的信息恰好可以由第二次卷积的前几位进行补齐.
但是这个方法会导致我们的序列变长,因此我们还有另外一个思路.我DFT得到的是循环卷积,假设滤波器长度为M,我们把后一段数据的前M-1个数据补到前一段数据的末尾.由于是循环卷积,前M-1个数据导致数据会来自该段数据的末位,最终导致重叠;而下一段的前M-1个由于上一段已经算过了,因此对于我来说数据也是多余的,因此也扔去,以此类推.

Pasted image 20251111205846.png

如\(x[n]=\{1,2,3,4,5,6,7,8,9\}\),\(h[n]=\{1,2\}\)
直接卷积得到的结果为\(y[n]=\{1,4,7,10,13,16,19,22,25,18\}\)
把\(x[n]\)拆分为\(x_1[n]=\{0,1,2,3\}\),\(x_2[n]=\{3,4,5,6\}\),\(x_3[n]=\{6,7,8,9\}\),\(x_4[n]=\{9,0,0,0\}\)
分别做周期卷积得到\(y_1[n]=\{6,1,4,7\}\),\(y_2[n]=\{15,10,13,16\}\),\(y_3[n]=\{24,19,22,25\}\)\(y_4[n]=\{9,18,0,0\}\)
这样处理的原因是:既然我后m-1位的信息缺失了,那我就先提前拿过来补上,让我的卷积得到的结果是完整的,然后再把和下一次卷积重复的部分删去.这个方法叫做重叠保留法

← 上一篇:
下一篇: →