Tom, Dick, and Mary Discover the DFT 阅读记录

Tom, Dick, and Mary Discover the DFT 阅读记录"/>

Tom, Dick, and Mary Discover the DFT 阅读记录

本文描述了三个善于思考的学生：Tom，Dick和Mary，从学到的傅里叶变换（FT）出发，基于"想采用计算机计算FT"这一想法，逐步推导出了离散傅里叶变换（DFT）的故事。

出于"懒"的想法，TDM三人（以下均如此称呼）想使用计算机进行傅里叶分析计算，考虑到傅里叶变换的表达式为：
X ( f ) = ∫ − ∞ ∞ x ( t ) e − 2 π f t d t (1) X(f)=\int_{-\infty}^{\infty}x(t)e^{-2\pi ft}dt \tag{1} X(f)=∫−∞∞​x(t)e−2πftdt(1)

但是 t t t和 f f f均为连续变量，TDM三人想在频域上获得离散谱，于是想到了傅里叶级数（FS），为了能应用FS，将 x ( t ) x(t) x(t)采用周期重复的办法得到了一个和 x ( t ) x(t) x(t)高度相关的新函数 y ( t ) y(t) y(t).

y ( t ) = ∑ k = − ∞ ∞ x ( t − k T y ) (2) y(t)=\sum_{k=-\infty}^{\infty}x(t-kT_y) \tag{2} y(t)=k=−∞∑∞​x(t−kTy​)(2)

从而对于周期函数 y ( t ) y(t) y(t)，能使用FS得到如下级数表达式：

y ( t ) = ∑ m = − ∞ ∞ α m e j 2 π m f y t , f y = 1 T y (3) y(t)=\sum_{m=-\infty}^{\infty}\alpha_me^{j2\pi mf_yt},f_y=\frac{1}{T_y} \tag{3} y(t)=m=−∞∑∞​αm​ej2πmfy​t,fy​=Ty​1​(3)

其中：

α m = 1 T y ∫ − T y / 2 T y / 2 y ( t ) e − j 2 π m f y t d t (4) \alpha_m=\frac{1}{T_y}\int_{-T_y/2}^{T_y/2}y(t)e^{-j2\pi mf_yt}dt \tag{4} αm​=Ty​1​∫−Ty​/2Ty​/2​y(t)e−j2πmfy​tdt(4)

用 x ( t ) x(t) x(t)代换有： α m = 1 T y ∫ − T y / 2 T y / 2 x ( t ) e − j 2 π m f y t d t = 1 T y ∫ − T / 2 T / 2 x ( t ) e − j 2 π m f y t d t = 1 T y X ( m f y ) (5) \begin{aligned} \alpha_m&=\frac{1}{T_y}\int_{-T_y/2}^{T_y/2}x(t)e^{-j2\pi mf_yt}dt \\ &=\frac{1}{T_y}\int_{-T/2}^{T/2}x(t)e^{-j2\pi mf_yt}dt \\ &=\frac{1}{T_y}X(mf_y) \end{aligned} \tag{5} αm​​=Ty​1​∫−Ty​/2Ty​/2​x(t)e−j2πmfy​tdt=Ty​1​∫−T/2T/2​x(t)e−j2πmfy​tdt=Ty​1​X(mfy​)​(5)

可以看到，当 T ≤ T y T\leq T_y T≤Ty​时，上述过程才成立。即 x ( t ) x(t) x(t)需要是时域受限的，否则不同周期间会产生交叠干扰。

TDM三人想对（3）式中的 y ( t ) y(t) y(t)进行FT，但是他们不确定（3）中的 y ( t ) y(t) y(t)和（2）中的 y ( t ) y(t) y(t)是否一致，于是TDM把FS变换后的 y ( t ) y(t) y(t)信号记为 y ′ ( t ) y'(t) y′(t).

y ′ ( t ) = ∑ m = − ∞ ∞ 1 T y X ( m f y ) e j 2 π m f y t (6) y'(t)=\sum_{m=-\infty}^{\infty}\frac{1}{T_y}X(mf_y)e^{j2\pi mf_yt} \tag{6} y′(t)=m=−∞∑∞​Ty​1​X(mfy​)ej2πmfy​t(6)

则有可以得到其傅里叶变换为：

Y ′ ( t ) = ∫ − ∞ ∞ y ′ ( t ) e − 2 π f t d t = ∫ − ∞ ∞ ∑ m = − ∞ ∞ 1 T y X ( m f y ) e j 2 π m f y t e − j 2 π f t d t = X ( f ) ∑ m = − ∞ ∞ 1 T y δ ( f − m f y ) (7) \begin{aligned} Y'(t)&=\int_{-\infty}^{\infty}y'(t)e^{-2\pi ft}dt \\ &=\int_{-\infty}^{\infty}\sum_{m=-\infty}^{\infty}\frac{1}{T_y}X(mf_y)e^{j2\pi mf_yt}e^{-j2\pi ft}dt \\ &=X(f)\sum_{m=-\infty}^{\infty}\frac{1}{T_y}\delta(f-mf_y) \end{aligned} \tag{7} Y′(t)​=∫−∞∞​y′(t)e−2πftdt=∫−∞∞​m=−∞∑∞​Ty​1​X(mfy​)ej2πmfy​te−j2πftdt=X(f)m=−∞∑∞​Ty​1​δ(f−mfy​)​(7)

然后对 Y ′ ( t ) Y'(t) Y′(t)进行傅里叶逆变换可得:

y ′ ( t ) = x ( t ) ∗ ∫ − ∞ ∞ ∑ m = − ∞ ∞ 1 T y δ ( f − m f y ) e j 2 π f t d t = x ( t ) ∗ ∑ m = − ∞ ∞ δ ( t − m T y ) = y ( t ) (8) \begin{aligned} y'(t)&=x(t)*\int_{-\infty}^{\infty}\sum_{m=-\infty}^{\infty}\frac{1}{T_y}\delta(f-mf_y)e^{j2\pi ft}dt \\ &=x(t)*\sum_{m=-\infty}^{\infty}\delta(t-mT_y)=y(t) \end{aligned} \tag{8} y′(t)​=x(t)∗∫−∞∞​m=−∞∑∞​Ty​1​δ(f−mfy​)ej2πftdt=x(t)∗m=−∞∑∞​δ(t−mTy​)=y(t)​(8)

这说明：把 x ( t ) x(t) x(t)周期延拓后再进行FS,得到的频域离散采样，能够复原 x ( t ) x(t) x(t)。只要 x ( t ) x(t) x(t)的时域宽度小于延拓周期 T y T_y Ty​.

这时，Tom敏锐地洞察到了这一重要信息，考虑到时域和频域的相互对应。Tom认为，如果我们能构建时域的周期延拓，得到离散频域采样，从而复原得到时域信息，那么反过来，构建频域的周期延拓，得到离散时域采样，也能复原得到频域信息。从而建立起了一种从离散抽样复原连续信号的对应关系。

说干就干，TDM三人开始尝试构建频域的周期延拓：

Y ( f ) = ∑ n = − ∞ ∞ X ( f − n f s ) (9) Y(f)=\sum_{n=-\infty}^{\infty}X(f-nf_s) \tag{9} Y(f)=n=−∞∑∞​X(f−nfs​)(9)

其中 X ( f ) X(f) X(f)为 x ( t ) x(t) x(t)的傅里叶变换。同样，对于周期的 Y ( t ) Y(t) Y(t)，采用和（3）式相似的方法，写出其傅里叶级数表示：

Y ( f ) = ∑ n = − ∞ ∞ β n e j 2 π n T s f , T s = 1 / f s (10) Y(f)=\sum_{n=-\infty}^{\infty}\beta_ne^{j2\pi nTsf},T_s=1/f_s \tag{10} Y(f)=n=−∞∑∞​βn​ej2πnTsf,Ts​=1/fs​(10)

其中：

β n = 1 f s ∫ − f s / 2 f s / 2 Y ( f ) e − j 2 π n T s f d f = 1 f s ∫ − f / 2 f / 2 Y ( f ) e − j 2 π n T s f d f = 1 f s x ( − n T s ) (11) \begin{aligned} \beta_n&=\frac{1}{f_s}\int_{-f_s/2}^{f_s/2}Y(f)e^{-j2\pi nT_sf}df \\ &=\frac{1}{f_s}\int_{-f/2}^{f/2}Y(f)e^{-j2\pi nT_sf}df \\ &=\frac{1}{f_s}x(-nT_s) \end{aligned} \tag{11} βn​​=fs​1​∫−fs​/2fs​/2​Y(f)e−j2πnTs​fdf=fs​1​∫−f/2f/2​Y(f)e−j2πnTs​fdf=fs​1​x(−nTs​)​(11)

同理，当 f ≤ f y f\leq f_y f≤fy​时，上述过程才成立。即 X ( f ) X(f) X(f)需要是频域受限的（虽然，一个信号不可能同时是频域时域都受限的，但是正是TDM三人对此的忽略，他们才能继续深入研究）

则可以得到， Y ( f ) Y(f) Y(f)的"FS"为：

Y ( f ) = 1 f s ∑ n = − ∞ ∞ x ( − n T s ) e j 2 π n T s f = 1 f s ∑ n = − ∞ ∞ x ( n T s ) e − j 2 π n T s f (12) \begin{aligned} Y(f)&=\frac{1}{f_s}\sum_{n=-\infty}^{\infty}x(-nTs)e^{j2\pi nT_sf} \\ &=\frac{1}{f_s}\sum_{n=-\infty}^{\infty}x(nTs)e^{-j2\pi nT_sf} \end{aligned} \tag{12} Y(f)​=fs​1​n=−∞∑∞​x(−nTs)ej2πnTs​f=fs​1​n=−∞∑∞​x(nTs)e−j2πnTs​f​(12)

自然的，采用相同的思想，通过对频域进行解析延拓，得到了时域的离散采样值，这份采样值能够表征频域的信息。假设 x ( t ) x(t) x(t)的最高频带为 f b f_b fb​,则为了保证重建后的频带不混叠，则 f = 2 f b ≤ f y f=2f_b\leq f_y f=2fb​≤fy​.自然得到了"奈奎斯特采样定理"： f y ≥ 2 f b f_y\geq 2f_b fy​≥2fb​

其实（12）式已经极其接近离散时间序列的傅里叶变换（DTFT）了，只是相差一个系数，DTFT的形式如下

Y ( f ) = ∑ n = − ∞ ∞ x ( n T s ) e − j 2 π n T s f (13) Y(f)=\sum_{n=-\infty}^{\infty}x(nTs)e^{-j2\pi nT_sf} \tag{13} Y(f)=n=−∞∑∞​x(nTs)e−j2πnTs​f(13)

也就是说，TDM三人从傅里叶变换（FT）和傅里叶级数（FS）出发，已经独立推理出了DTFT的形式。DTFT并不是什么独立的"新变换方式"，而是出于应用需要，基于FT和FS的一种自然而然的扩展。DTFT告诉我们，只需要在时域上记录有限个离散采样点，我们就能复原出其完整的连续频域，这在现实应用中意义重大。

目前为止，TDM三人已经能做到这些事：连续非周期时域到连续非周期频域的变换（FT）、连续周期时域到离散非周期时域的变换（FS）、离散非周期时域到连续周期频域的变换（DTFT）。

还是为了做作业这个初衷，他们想用刚推出来的DTFT来复原信号。但是在无穷时间内采样无穷个是不显示了，为此，他们只能采用有限个时域抽样点来复原信号的频域图谱，尽管这只会得到一个近似的频率谱。

但是很快，TDM三人碰到了困难：他们并不知道原信号 x 3 ( t ) x_3(t) x3​(t)的带宽是多大。既然不知道那就先摸索，于是他们按照 t = n T s t=nT_s t=nTs​，其中 n = 0 , 1 , . . . , N − 1 n=0,1,...,N-1 n=0,1,...,N−1，一共抽取了 N N N个点，得到的不是 X ( f ) X(f) X(f)而是其周期延拓版本 Y ( f ) Y(f) Y(f)：

Y ( f ) = 1 f s ∑ n = 0 N x 3 ( n T s ) e − j 2 π n T s f (14) Y(f)=\frac{1}{f_s}\sum_{n=0}^Nx_3(nTs)e^{-j2\pi nT_sf} \tag{14} Y(f)=fs​1​n=0∑N​x3​(nTs)e−j2πnTs​f(14)

这时，Mary想到了第一次分析时对 x ( t ) x(t) x(t)做周期延拓的方法，于是她把它写了下来：

y ( n T s ) = ∑ k = − ∞ ∞ x 3 ( n T s − k N T s ) (15) y(nT_s)=\sum_{k=-\infty}^{\infty}x_3(nT_s-kNT_s) \tag{15} y(nTs​)=k=−∞∑∞​x3​(nTs​−kNTs​)(15)

然后他们画了画 y ( n T S ) y(nT_S) y(nTS​)的图像，发现从前 n n n个点恰好是序列 x 3 ( n T s ) , n = 0 , 1 , . . . , N − 1 x_3(nT_s),n=0,1,...,N-1 x3​(nTs​),n=0,1,...,N−1

但是他们现在还是没有 X 3 ( f ) X_3(f) X3​(f)的样本，只有一个由 X 3 ( f ) X_3(f) X3​(f)的周期延拓的样本 y ( n T s ) y(nT_s) y(nTs​)

此时Mary提出了一个关键性的视角：对于一个时域有限的信号，如果我们将其周期延拓，就能得到其离散的频域信号。同样，对于一个信号的频域 Y ( f ) ) Y(f)) Y(f))，我们如果认为它是频域有限的并对其周期延拓，同样能够得到其离散的时域信号。于是对于 Y ( f ) ) Y(f)) Y(f))，假设其频带受限，即最大频带为 f s / 2 f_s/2 fs​/2

Y 3 ( f ) = { Y ( f ) , − f s 2 ≤ f ≤ f s 2 0 , o t h e r w i s e (16) Y_3(f)=\left\{ \begin{aligned} &Y(f),\frac{-f_s}{2}\leq f \leq \frac{f_s}{2} \\ &0,otherwise \end{aligned} \right. \tag{16} Y3​(f)=⎩ ⎨ ⎧​​Y(f),2−fs​​≤f≤2fs​​0,otherwise​(16)

然后再对 y 3 ( f ) y_3(f) y3​(f)进行周期延拓，得到 w ( t ) w(t) w(t)

w ( t ) = ∑ i = − ∞ ∞ y 3 ( t − i T w ) (17) w(t)=\sum_{i=-\infty}^{\infty}y_3(t-iT_w) \tag{17} w(t)=i=−∞∑∞​y3​(t−iTw​)(17)

为了抽样的一致， T w T_w Tw​应当为 T s T_s Ts​的整数倍：

y T w = M T s , f w = f s M (18) y T_w=MT_s,f_w=\frac{f_s}{M} \tag{18} yTw​=MTs​,fw​=Mfs​​(18)

从而可以得到 w ( t ) w(t) w(t)的FS:

w ( t ) = ∑ k = − ∞ ∞ γ k e j 2 π k f w t (19) w(t)=\sum_{k=-\infty}^{\infty}\gamma_ke^{j2\pi kf_wt} \tag{19} w(t)=k=−∞∑∞​γk​ej2πkfw​t(19)

其中：

γ k = 1 T w ∫ − T w / 2 T w / 2 w ( t ) e − j 2 π k f w t d t = 1 T w Y 3 ( k f w ) (20) \gamma_k=\frac{1}{T_w}\int_{-T_w/2}^{T_w/2} w(t)e^{-j2\pi kf_wt}dt =\frac{1}{T_w}Y_3(kf_w) \tag{20} γk​=Tw​1​∫−Tw​/2Tw​/2​w(t)e−j2πkfw​tdt=Tw​1​Y3​(kfw​)(20)

则有：

w ( t ) = 1 T w ∑ k = − ∞ ∞ Y 3 ( k f w ) e j 2 π k f w t (21) w(t)=\frac{1}{T_w}\sum_{k=-\infty}^{\infty}Y_3(kf_w)e^{j2\pi kf_wt} \tag{21} w(t)=Tw​1​k=−∞∑∞​Y3​(kfw​)ej2πkfw​t(21)

为了用 Y ( f ) Y(f) Y(f)代替 Y 3 ( f ) Y_3(f) Y3​(f),限制 − f s 2 ≤ k f w ≤ f s 2 \frac{-f_s}{2}\leq kf_w \leq \frac{f_s}{2} 2−fs​​≤kfw​≤2fs​​则有：

w ( t ) = 1 T w ∑ k Y ( k f w ) e j 2 π k f w t (22) w(t)=\frac{1}{T_w}\sum_{k}Y(kf_w)e^{j2\pi kf_wt} \tag{22} w(t)=Tw​1​k∑​Y(kfw​)ej2πkfw​t(22)

现在TDM三人可以用离散频域值计算时域的值了，他们很关注采样点 ( t = n T s , n = 0 , 1 , . . . , N − 1 ) (t=nT_s,n=0,1,...,N-1) (t=nTs​,n=0,1,...,N−1)上的值：

w ( n T s ) = 1 T w ∑ k Y ( k f w ) e j 2 π k f w n T s (23) w(nT_s)=\frac{1}{T_w}\sum_{k}Y(kf_w)e^{j2\pi kf_wnTs} \tag{23} w(nTs​)=Tw​1​k∑​Y(kfw​)ej2πkfw​nTs(23)

Dick觉得只是计算出了一些无意义的值，但是Mary指出去研究 y 3 ( t ) y_3(t) y3​(t)和原始时间样本 x 3 ( t ) x_3(t) x3​(t)的关系，他们发现这一步他们之前已经做过：

y 3 ( n T s ) = ∫ − f s / 2 f s / 2 Y 3 ( f ) e j 2 π f n T s d f = ∫ − f s / 2 f s / 2 Y ( f ) e j 2 π f n T s d f = ∫ − f s / 2 f s / 2 ( 1 f s ∑ n = 0 N x 3 ( n T s ) e − j 2 π n T s f ) e j 2 π f n T s d f = x 3 ( n T s ) . (24) \begin{aligned} y_3(nT_s)&=\int_{-f_s/2}^{f_s/2}Y_3(f)e^{j2\pi fnT_s}df=\int_{-f_s/2}^{f_s/2}Y(f)e^{j2\pi fnT_s}df \\ &=\int_{-f_s/2}^{f_s/2}(\frac{1}{f_s}\sum_{n=0}^Nx_3(nTs)e^{-j2\pi nT_sf})e^{j2\pi fnT_s}df \\ &=x_3(nT_s). \end{aligned} \tag{24} y3​(nTs​)​=∫−fs​/2fs​/2​Y3​(f)ej2πfnTs​df=∫−fs​/2fs​/2​Y(f)ej2πfnTs​df=∫−fs​/2fs​/2​(fs​1​n=0∑N​x3​(nTs)e−j2πnTs​f)ej2πfnTs​df=x3​(nTs​).​(24)

则 w ( n T s ) w(nT_s) w(nTs​)可以写成：

w ( n T s ) = ∑ i = − ∞ ∞ x 3 ( n T s − i T w ) (25) w(nT_s)=\sum_{i=-\infty}^{\infty}x_3(nT_s-iT_w) \tag{25} w(nTs​)=i=−∞∑∞​x3​(nTs​−iTw​)(25)

考虑到 T w = M T s T_w=MT_s Tw​=MTs​:

w ( n T s ) = ∑ i = − ∞ ∞ x 3 ( ( n − i M ) T s ) (26) w(nT_s)=\sum_{i=-\infty}^{\infty}x_3((n-iM)T_s) \tag{26} w(nTs​)=i=−∞∑∞​x3​((n−iM)Ts​)(26)

注意， x 3 ( n T s ) x_3(nTs) x3​(nTs)只在 n = 0 , 1 , . . . , N − 1 n=0,1,...,N-1 n=0,1,...,N−1有非0值（因为 x 3 ( t ) x_3(t) x3​(t)是一个时域有限的信号）特别的，我们只要取 M ≥ N M \geq N M≥N，就必然能够取到 w ( 0 ) , w ( T s ) , . . . , w ( ( N − 1 ) T s ) w(0),w(T_s),...,w((N-1)T_s) w(0),w(Ts​),...,w((N−1)Ts​)。如果取 M = N M=N M=N，则:

w ( n T s ) = ∑ i = − ∞ ∞ x 3 ( ( n − i N ) T s ) = x 3 ( n T s ) (27) w(nT_s)=\sum_{i=-\infty}^{\infty}x_3((n-iN)T_s)=x_3(nT_s) \tag{27} w(nTs​)=i=−∞∑∞​x3​((n−iN)Ts​)=x3​(nTs​)(27)

联系此前做的 w ( t ) w(t) w(t) FS变换，参考（22）式子，则有：

x 3 ( n T s ) = 1 T w ∑ k Y ( k f w ) e j 2 π k f w n T s = 1 N T s ∑ k Y ( k f w ) e j 2 π k n / N (28) \begin{aligned} x_3(nT_s)&=\frac{1}{T_w}\sum_{k}Y(kf_w)e^{j2\pi kf_wnT_s} \\ &=\frac{1}{NT_s}\sum_{k}Y(kf_w)e^{j2\pi kn/N} \end{aligned} \tag{28} x3​(nTs​)​=Tw​1​k∑​Y(kfw​)ej2πkfw​nTs​=NTs​1​k∑​Y(kfw​)ej2πkn/N​(28)

其中 − f S 2 ≤ k f s N ≤ f s 2 \frac{-f_S}{2} \leq \frac{kf_s}{N} \leq \frac{f_s}{2} 2−fS​​≤Nkfs​​≤2fs​​， n = 0 , 1 , . . . , N − 1 n=0,1,...,N-1 n=0,1,...,N−1

得到了一个方向的变换，反向的变换很容易得到，由（12）式有：

Y ( k f s N ) = 1 f s ∑ n = 0 N − 1 x 3 ( n T s ) e − j 2 π n k / N (29) Y(\frac{kf_s}{N})=\frac{1}{f_s}\sum_{n=0}^{N-1}x_3(nT_s)e^{-j2\pi nk/N} \tag{29} Y(Nkfs​​)=fs​1​n=0∑N−1​x3​(nTs​)e−j2πnk/N(29)

限制条件一样，也是 − f s 2 ≤ k f s N ≤ f s 2 \frac{-f_s}{2} \leq \frac{kf_s}{N} \leq \frac{f_s}{2} 2−fs​​≤Nkfs​​≤2fs​​， n = 0 , 1 , . . . , N − 1 n=0,1,...,N-1 n=0,1,...,N−1

其实这已经是得到了初步的DFT了。再考虑到 Y D T F T ( f ) = f s Y ( f ) Y_{DTFT}(f)=f_sY(f) YDTFT​(f)=fs​Y(f),则：

Y D T F T ( k f s N ) = ∑ n = 0 N − 1 x 3 ( n T s ) e − j 2 π n k / N (30) Y_{DTFT}(\frac{kf_s}{N})=\sum_{n=0}^{N-1}x_3(nT_s)e^{-j2\pi nk/N} \tag{30} YDTFT​(Nkfs​​)=n=0∑N−1​x3​(nTs​)e−j2πnk/N(30)

对应：

x 3 ( n T s ) = 1 N ∑ k Y D T F T ( k f w ) e j 2 π k n / N (31) x_3(nT_s)=\frac{1}{N}\sum_{k}Y_{DTFT}(kf_w)e^{j2\pi kn/N} \tag{31} x3​(nTs​)=N1​k∑​YDTFT​(kfw​)ej2πkn/N(31)

首先考虑 k k k的取值，首先无论是 N N N为奇数还是偶数，在 − f s 2 ≤ k f s N ≤ f s 2 \frac{-f_s}{2} \leq \frac{kf_s}{N} \leq \frac{f_s}{2} 2−fs​​≤Nkfs​​≤2fs​​条件约束下，k总有N个连续取值

再考虑到 Y D T F T ( k f w ) = Y D T F T ( k f s / N ) Y_{DTFT}(kf_w)=Y_{DTFT}(kf_s/N) YDTFT​(kfw​)=YDTFT​(kfs​/N)是 X 3 ( f ) X_3(f) X3​(f)的周期为 f s f_s fs​的周期延拓，即 Y D T F T ( k f w ) = Y D T F T ( ( k + N ) f w ) Y_{DTFT}(kf_w)=Y_{DTFT}((k+N)f_w) YDTFT​(kfw​)=YDTFT​((k+N)fw​)
，并且 e j 2 π k n / N e^{j2\pi kn/N} ej2πkn/N也以N为周期。

既然k总有N个取值，并且取k和k+N时值总是相等，为何不取 k = 0 , 1 , . . . , N − 1 k=0,1,...,N-1 k=0,1,...,N−1？则有（31）可简化为：

x 3 ( n T s ) = 1 N ∑ k = 0 N − 1 Y D T F T ( k f w ) e j 2 π k n / N (32) x_3(nT_s)=\frac{1}{N}\sum_{k=0}^{N-1}Y_{DTFT}(kf_w)e^{j2\pi kn/N} \tag{32} x3​(nTs​)=N1​k=0∑N−1​YDTFT​(kfw​)ej2πkn/N(32)

至此，从（30）（32）已经得到了DFT： X ( k ) = ∑ n = 0 N − 1 x ( n ) e − j 2 π n k / N x ( n ) = 1 N ∑ k = 0 N − 1 X ( k ) e j 2 π k n / N (33) \begin{aligned} &X(k)=\sum_{n=0}^{N-1}x(n)e^{-j2\pi nk/N}\\ &x(n)=\frac{1}{N}\sum_{k=0}^{N-1}X(k)e^{j2\pi kn/N} \end{aligned} \tag{33} ​X(k)=n=0∑N−1​x(n)e−j2πnk/Nx(n)=N1​k=0∑N−1​X(k)ej2πkn/N​(33)

纵观TDM三人"发现DFT"的思想过程，可以发现DFT的出现是极其自然的，起源于"采用计算机计算傅里叶变换"这一初始目的，采用FT和FS这两个基本工具，一步一步推导出了DTFT，最后得到DFT。正如文中所言"DFT是什么新的理论吗？"，DFT是连续时域频域的FT在离散时域频域上的自然延申。并且可以看到，奈奎斯特采样定律其实是在推导DFT中为了保持有限的带宽不混叠，自然而然产生的约束条件。

推导过程中，最为重要的就是时域和频域的对应的思想。在推导DTFT时，Tom指出既然时域的周期延拓导出离散的频域，则同样的频域的周期延拓也能导出离散的时域；在推导DFT的过程中，Mary也指出了既然能够把时域看作周期的，则频域也能看作周期的。可以看出TDM三人对FT中时域频域转换有相当良好的基础。深度理解FT的本质，才能更好运用它。

作者J.R.Deller在文章开头说了这样一句话：“Education is the process of
telling smaller and smaller lies.”，即：教育是一个说越来越小谎言的过程。我们得到的DFT，其实只是一个"谎言"，我们虽然能使用它，但是我们却不知晓它为何是如此形式。TDM三人的探索，正是完善这个"谎言"的过程，从而对DFT有了更深刻全面的理解，DFT再也不是"天外来客"，而是"土生土长"于FT的。“说越来越小谎言"的意思，也就是"追求越来越接近真理”。

总结：

1，DFT是FT在离散域的自然延拓，采样定理是推导过程中自然产生的限制条件

2，学基础知识要扎实

3，学习过程中要有求知欲

文章原文pdf连接：Tom, Dick, and Mary Discover the DFT