傅里叶级数与傅里叶变换_Part6_离散傅里叶变换推导

0、Part4和Part5的复习

0.1、Part4复习

参考链接：傅里叶级数与傅里叶变换_Part4_傅里叶级数的复数形式

对于周期为$T$，即$f\left(t\right)=f\left(t+T\right)$的函数，它的傅里叶级数的复数展开形式如下：

$f\left(t\right)=\sum _{n=-\infty }^{\infty }{c}_n{e}^{in\omega t}$, 其中，$c_n=\frac{1}{T}{\int }_0^{T}f\left(t\right)e^{-in\omega t}dt$

重写一下
$f_T\left(t\right)=\sum _{n=-\infty }^{\infty }{c}_n{e}^{in{\omega }_{0}t}(1)$，${\omega }_0=\frac{2\pi }{T}$为角频率。

$c_n=\frac{1}{T}{\int }_0^T{f}_T\left(t\right)e^{-in{\omega }_{0}t}dt=\frac{1}{T}{\int }_{-\frac{T}{2}}^{\frac{T}{2}}{f}_T\left(t\right)e^{-in{\omega }_{0}t}dt(2)$

在上式中，$\sum _{n=-\infty }^{\infty }{e}^{in{\omega }_{0}t}$可以理解一种规则，而$c_n$呢，我们可以理解为它定义了函数，$c_n=a+bi$是一个复数。

0.2、Part5复习

参考链接：傅里叶级数与傅里叶变换_Part5_傅里叶级数推导傅里叶变换

$f\left(t\right)=\frac{1}{2\pi }{\int }_{-\infty }^{\infty }{\int }_{-\infty }^{\infty }f\left(t\right)e^{-i\omega t}dt{e}^{i\omega t}d\omega$

$F\left(\omega \right)\triangleq {\int }_{-\infty }^{\infty }f\left(t\right)e^{-i\omega t}dt$ ， 这就是傅里叶变换。

$f\left(t\right)=\frac{1}{2\pi }{\int }_{-\infty }^{\infty }F\left(\omega \right)e^{i\omega t}d\omega$， 这就是傅里叶逆变换。

这都是连续时间的傅里叶变换/逆变换，实际信号没法儿用。

1、离散傅里叶变换推导

我们现在存在一个离散的时间序列 $x\left(n\right)$，其中呢，$n=0,1,2,\cdots ,N-1$，采样间隔为 $T$。

下面，我们假设存在一个函数$f_{NT}\left(t\right)$，使得 $x\left(n\right)=f_{NT}\left(nT\right)$，并且$f_{NT}\left(t\right)$是一个周期函数，周期为 $NT$，即 $f_{NT}\left(t\right)=f_{NT}\left(t+NT\right)$。

下面根据Part4对于傅里叶级数的复数形式的推导结果，进行进一步的推导

$f_T\left(t\right)=\sum _{n=-\infty }^{\infty }{c}_n{e}^{in{\omega }_{0}t}=\sum _{n=-\infty }^{\infty }\left[\left(\frac{1}{T}{\int }_0^T{f}_T\left(t\right)e^{-in{\omega }_{0}t}dt\right)\cdot e^{in{\omega }_{0}t}\right]$

我们将周期为$NT$的函数$f_{NT}\left(t\right)=f_{NT}\left(t+NT\right)$带入到上式当中，可得

$f_{NT}\left(t\right)=\sum _{n=-\infty }^{\infty }\left[\left(\frac{1}{NT}{\int }_0^{NT}{f}_{NT}\left(t\right)e^{-in{\omega }_{0}t}dt\right)\cdot e^{in{\omega }_{0}t}\right]$

注意到Part4中原定定义是${\omega }_0=\frac{2\pi }{T}$，由于现在我们的周期是$NT$，注意：$NT$中的$T$是采样间隔的意思，$\frac{2\pi }{T}$中的$T$是周期的意思。

在所以此处${\omega }_0$应该为${\omega }_0=\frac{2\pi }{NT}$，将 ${\omega }_0=\frac{2\pi }{NT}$进一步带入到上式当中，可得

$f_{NT}\left(t\right)=\sum _{n=-\infty }^{\infty }\left[\left(\frac{1}{NT}{\int }_0^{NT}{f}_{NT}\left(t\right)e^{-in\frac{2\pi }{NT}t}dt\right)\cdot e^{in\frac{2\pi }{NT}t}\right]$

观察公式中的（）部分，其实它是等于$c_n=\frac{1}{NT}{\int }_0^{NT}{f}_{NT}\left(t\right)e^{-in\frac{2\pi }{NT}t}dt$

再观察Part5连续时间傅里叶变换的结果

$f\left(t\right)=\frac{1}{2\pi }{\int }_{-\infty }^{\infty }{\int }_{-\infty }^{\infty }f\left(t\right)e^{-i\omega t}dt{e}^{i\omega t}d\omega$

$F\left(\omega \right)\triangleq {\int }_{-\infty }^{\infty }f\left(t\right)e^{-i\omega t}dt$ ， 傅里叶变换。

$f\left(t\right)=\frac{1}{2\pi }{\int }_{-\infty }^{\infty }F\left(\omega \right)e^{i\omega t}d\omega$， 傅里叶逆变换。

两次积分的里面那一项，${\int }_{-\infty }^{\infty }f\left(t\right)e^{-i\omega t}dt$ 就是傅里叶变换$\triangleq F\left(\omega \right)$。

再观察$f_{NT}\left(t\right)$的傅里叶级数表达。

$f_{NT}\left(t\right)=\sum _{n=-\infty }^{\infty }\left[\left(\frac{1}{NT}{\int }_0^{NT}{f}_{NT}\left(t\right)e^{-in\frac{2\pi }{NT}t}dt\right)\cdot e^{in\frac{2\pi }{NT}t}\right]$

外层是$n$从$-\infty$到$+\infty$的累积和，内层也是一个积分。如果把累加和看成是一个积分，那么也是两次积分。

我们的目的是为了推导离散傅里叶变换

那么我们是不是可以把同样把 内层的积分$\frac{1}{NT}{\int }_0^{NT}{f}_{NT}\left(t\right)e^{-in\frac{2\pi }{NT}t}dt$ 定义成 周期为$NT$的函数的傅里叶变换$\triangleq F\left(\omega \right)$呢？ 答案是肯定的

进一步推导，定义：

$F\left(\omega \right)\triangleq \frac{1}{NT}{\int }_0^{NT}{f}_{NT}\left(t\right)e^{-in\frac{2\pi }{NT}t}dt$

我们都知道，定积分，是可以用面积法来近似的

${\int }_0^{NT}g\left(t\right)dt=\underset{T\to 0}{\lim }\sum _{k=0}^{N-1}g\left(kT\right)\cdot T$

我们令$g\left(t\right)=f_{NT}\left(t\right)e^{-in\frac{2\pi }{NT}t}$

那么

F ( ω ) = 1 N T ∫ 0 N T f N T ( t ) e − i n 2 π N T t d t = 1 N T lim ⁡ T → 0 ∑ k = 0 N − 1 g ( k T ) ⋅ T = 1 N T lim ⁡ T → 0 ∑ k = 0 N − 1 f N T ( k T ) e − i n 2 π N T k T ⋅ T = 1 N lim ⁡ T → 0 ∑ k = 0 N − 1 f N T ( k T ) e − i n 2 π k N = 1 N lim ⁡ T → 0 ∑ k = 0 N − 1 x ( k ) e − i n 2 π k N

F(ω)​=NT1​∫0NT​fNT​(t)e−inNT2π​tdt=NT1​T→0lim​k=0∑N−1​g(kT)⋅T=NT1​T→0lim​k=0∑N−1​fNT​(kT)e−inNT2π​kT⋅T=N1​T→0lim​k=0∑N−1​fNT​(kT)e−inN2πk​=N1​T→0lim​k=0∑N−1​x(k)e−inN2πk​​

即：

$F\left(\omega \right)=\frac{1}{N}\underset{T\to 0}{\lim }\sum _{k=0}^{N-1}x\left(k\right)e^{-in\frac{2\pi k}{N}}$

在Part5的推导中，我们知道$\omega =n{\omega }_0$，根据上面的推导，我们知道 ${\omega }_0=\frac{2\pi }{NT}$ 因此，$\omega =n\cdot \frac{2\pi }{NT}$

最终得到

$F\left(n\cdot \frac{2\pi }{NT}\right)=\frac{1}{N}\underset{T\to 0}{\lim }\sum _{k=0}^{N-1}x\left(k\right)e^{-in\frac{2\pi k}{N}}$

记 $X\left(n\right)=F\left(n\cdot \frac{2\pi }{NT}\right)$

就初步得到了 离散傅里叶变换的形式

$X\left(n\right)=\frac{1}{N}\sum _{k=0}^{N-1}x\left(k\right)e^{-in\frac{2\pi k}{N}},T\to 0$

2、离散傅里叶逆变换推导

根据傅里叶级数的定义， $n$是从$-\infty$到$+\infty$的整数，那么可以看出$n\cdot \frac{2\pi }{NT}$也是离散的一些点。所以我们可以认为$X\left(n\right)$就是离散傅里叶变换了。

那么对于离散的傅里叶逆变换，也能顺理成章的推导出。

注 : 使用$mT$来代替前文中的$nT$，是为了在后续推导中更便于理解。

f N T ( t ) = lim ⁡ T → 0 f N T ( m T ) = ∑ n = − ∞ ∞ [ ( 1 N T ∫ 0 N T f N T ( t ) e − i n 2 π N T t d t ) ⋅ e i n 2 π N T t ] , m ∈ [ − ∞ , + ∞ ] = ∑ n = − ∞ ∞ [ ( 1 N lim ⁡ T → 0 ∑ k = 0 N − 1 x ( k ) e − i n 2 π k N ) ⋅ e i n 2 π N T t ] , t = m T = ∑ n = − ∞ ∞ [ ( 1 N ∑ k = 0 N − 1 x ( k ) e − i n 2 π k N ) ⋅ e i n 2 π N T m T ] , T → 0 = ∑ n = − ∞ ∞ [ X ( n ) ⋅ e i n 2 π m N ] , T → 0

fNT​(t)​=T→0lim​fNT​(mT)=n=−∞∑∞​[(NT1​∫0NT​fNT​(t)e−inNT2π​tdt)⋅einNT2π​t],m∈[−∞,+∞]=n=−∞∑∞​[(N1​T→0lim​k=0∑N−1​x(k)e−inN2πk​)⋅einNT2π​t],t=mT=n=−∞∑∞​[(N1​k=0∑N−1​x(k)e−inN2πk​)⋅einNT2π​mT],T→0=n=−∞∑∞​[X(n)⋅einN2πm​],T→0​

注意：其中$t\in \left[-\infty ,+\infty \right]\Rightarrow m=\frac{t}{T}\in \left[-\infty ,+\infty \right]$的，而公式中的累加和 $n$的上下限为 $\left[-\infty ,+\infty \right]$，但$x\left(m\right)$的$m$不是$\left[-\infty ,+\infty \right]$，

根据前文的定义：

$x\left(m\right)=f_{NT}\left(mT\right),m=0,1,2,3,\cdots ,N-1$

t = lim ⁡ T → 0 m T ∈ { 0 , T , 2 T , 3 T , ⋯   , ( N − 1 ) T } ⇒ m = t T ∈ [ 0 , 1 , 2 , 3 , ⋯   , ( N − 1 ) ] t = \mathop {\lim }\limits_{T \to 0} mT \in \left\{ {0,T,2T,3T, \cdots ,\left( {N - 1} \right)T} \right\} \Rightarrow m = \frac{t}{T} \in \left[ {0,1,2,3, \cdots ,\left( {N - 1} \right)} \right] t=T→0lim​mT∈{0,T,2T,3T,⋯,(N−1)T}⇒m=Tt​∈[0,1,2,3,⋯,(N−1)]

因此离散傅里叶逆变换中的上下限应该为 $\left[0,N-1\right]$。 即

$x\left(m\right)=f_{NT}\left(mT\right)\triangleq \sum _{n=0}^{N-1}\left[X\left(n\right)\cdot e^{in\frac{2\pi m}{N}}\right]$

口说无凭，我给出证明。证明： F − 1 { F [ x ( m ) ] } = x ( m ) {F^{ - 1}}\left\{ {F\left[ {x\left( m \right)} \right]} \right\} = x\left( m \right) F−1{F[x(m)]}=x(m)

F − 1 { F [ f N T ( m T ) ] } = ∑ n = 0 N − 1 [ X ( n ) ⋅ e i n 2 π m N ] = ∑ n = 0 N − 1 ( 1 N ∑ k = 0 N − 1 x ( k ) e − i n 2 π k N ) ⋅ e i n 2 π m N = 1 N ∑ n = 0 N − 1 [ x ( 0 ) e − i n 2 π ⋅ 0 N + x ( 1 ) e − i n 2 π ⋅ 1 N + x ( 2 ) e − i n 2 π ⋅ 2 N + ⋯ + x ( a ) e − i n 2 π ⋅ a N + ⋯ x ( N − 1 ) e − i n 2 π ⋅ N − 1 N ] ⋅ e i n 2 π m N = 1 N × { ( x ( 0 ) e − i n 2 π ⋅ 0 N + x ( 1 ) e − i n 2 π ⋅ 1 N + x ( 2 ) e − i n 2 π ⋅ 2 N + ⋯ + x ( a ) e − i n 2 π ⋅ a N + ⋯ x ( N − 1 ) e − i n 2 π ⋅ N − 1 N ) e i 0 2 π m N + ( x ( 0 ) e − i n 2 π ⋅ 0 N + x ( 1 ) e − i n 2 π ⋅ 1 N + x ( 2 ) e − i n 2 π ⋅ 2 N + ⋯ + x ( a ) e − i n 2 π ⋅ a N + ⋯ x ( N − 1 ) e − i n 2 π ⋅ N − 1 N ) e i 1 2 π m N + ( x ( 0 ) e − i n 2 π ⋅ 0 N + x ( 1 ) e − i n 2 π ⋅ 1 N + x ( 2 ) e − i n 2 π ⋅ 2 N + ⋯ + x ( a ) e − i n 2 π ⋅ a N + ⋯ x ( N − 1 ) e − i n 2 π ⋅ N − 1 N ) e i 2 2 π m N + ⋯ + ( x ( 0 ) e − i n 2 π ⋅ 0 N + x ( 1 ) e − i n 2 π ⋅ 1 N + x ( 2 ) e − i n 2 π ⋅ 2 N + ⋯ + x ( a ) e − i n 2 π ⋅ a N + ⋯ x ( N − 1 ) e − i n 2 π ⋅ N − 1 N ) e i b 2 π m N + ⋯ + ( x ( 0 ) e − i n 2 π ⋅ 0 N + x ( 1 ) e − i n 2 π ⋅ 1 N + x ( 2 ) e − i n 2 π ⋅ 2 N + ⋯ + x ( a ) e − i n 2 π ⋅ a N + ⋯ x ( N − 1 ) e − i n 2 π ⋅ N − 1 N ) e i ( N − 1 ) 2 π m N }

\right\} \end{array} F−1{F[fNT​(mT)]}=n=0∑N−1​[X(n)⋅einN2πm​]=n=0∑N−1​(N1​k=0∑N−1​x(k)e−inN2πk​)⋅einN2πm​=N1​n=0∑N−1​[x(0)e−inN2π⋅0​+x(1)e−inN2π⋅1​+x(2)e−inN2π⋅2​+⋯+x(a)e−inN2π⋅a​+⋯x(N−1)e−inN2π⋅N−1​]⋅einN2πm​=N1​×⎩ ⎨ ⎧​(x(0)e−inN2π⋅0​+x(1)e−inN2π⋅1​+x(2)e−inN2π⋅2​+⋯+x(a)e−inN2π⋅a​+⋯x(N−1)e−inN2π⋅N−1​)ei0N2πm​+(x(0)e−inN2π⋅0​+x(1)e−inN2π⋅1​+x(2)e−inN2π⋅2​+⋯+x(a)e−inN2π⋅a​+⋯x(N−1)e−inN2π⋅N−1​)ei1N2πm​+(x(0)e−inN2π⋅0​+x(1)e−inN2π⋅1​+x(2)e−inN2π⋅2​+⋯+x(a)e−inN2π⋅a​+⋯x(N−1)e−inN2π⋅N−1​)ei2N2πm​+⋯+(x(0)e−inN2π⋅0​+x(1)e−inN2π⋅1​+x(2)e−inN2π⋅2​+⋯+x(a)e−inN2π⋅a​+⋯x(N−1)e−inN2π⋅N−1​)eibN2πm​+⋯+(x(0)e−inN2π⋅0​+x(1)e−inN2π⋅1​+x(2)e−inN2π⋅2​+⋯+x(a)e−inN2π⋅a​+⋯x(N−1)e−inN2π⋅N−1​)ei(N−1)N2πm​​⎭ ⎬ ⎫​​

注：1、里面的求和是$n$不变，所以展开里面的累积和时，$n$保持不动，k待入数值。 外层的求和是$m$不变。这时候要把$n$带入数值。

= 1 N × { ( x ( 0 ) e − i 0 2 π ⋅ 0 N e i 0 2 π m N + x ( 1 ) e − i 0 2 π ⋅ 1 N e i 0 2 π m N + ⋯ + x ( a ) e − i 0 2 π ⋅ a N e i 0 2 π m N + ⋯ x ( N − 1 ) e − i 0 2 π ⋅ N − 1 N e i 0 2 π m N ) + ( x ( 0 ) e − i 1 2 π ⋅ 0 N e i 1 2 π m N + x ( 1 ) e − i 1 2 π ⋅ 1 N e i 1 2 π m N + ⋯ + x ( a ) e − i 1 2 π ⋅ a N e i 1 2 π m N + ⋯ x ( N − 1 ) e − i 1 2 π ⋅ N − 1 N e i 1 2 π m N ) + ⋯ + ( x ( 0 ) e − i b 2 π ⋅ 0 N e i b 2 π m N + x ( 1 ) e − i b 2 π ⋅ 1 N e i b 2 π m N + ⋯ + x ( a ) e − i b 2 π ⋅ a N e i b 2 π m N + ⋯ x ( N − 1 ) e − i b 2 π ⋅ N − 1 N e i b 2 π m N ) + ⋯ + ( x ( 0 ) e − i ( N − 1 ) 2 π ⋅ 0 N e i ( N − 1 ) 2 π m N + x ( 1 ) e − i ( N − 1 ) 2 π ⋅ 1 N e i ( N − 1 ) 2 π m N + ⋯ + x ( a ) e − i ( N − 1 ) 2 π ⋅ a N e i ( N − 1 ) 2 π m N + ⋯ + x ( N − 1 ) e − i ( N − 1 ) 2 π ⋅ N − 1 N e i ( N − 1 ) 2 π m N ) } = \frac{1}{N} \times \left\{

\right) \end{array} \right\} =N1​×⎩ ⎨ ⎧​(x(0)e−i0N2π⋅0​ei0N2πm​+x(1)e−i0N2π⋅1​ei0N2πm​+⋯+x(a)e−i0N2π⋅a​ei0N2πm​+⋯x(N−1)e−i0N2π⋅N−1​ei0N2πm​)+(x(0)e−i1N2π⋅0​ei1N2πm​+x(1)e−i1N2π⋅1​ei1N2πm​+⋯+x(a)e−i1N2π⋅a​ei1N2πm​+⋯x(N−1)e−i1N2π⋅N−1​ei1N2πm​)+⋯+(x(0)e−ibN2π⋅0​eibN2πm​+x(1)e−ibN2π⋅1​eibN2πm​+⋯+x(a)e−ibN2π⋅a​eibN2πm​+⋯x(N−1)e−ibN2π⋅N−1​eibN2πm​)+⋯+⎝ ⎛​x(0)e−i(N−1)N2π⋅0​ei(N−1)N2πm​+x(1)e−i(N−1)N2π⋅1​ei(N−1)N2πm​+⋯+x(a)e−i(N−1)N2π⋅a​ei(N−1)N2πm​+⋯+x(N−1)e−i(N−1)N2π⋅N−1​ei(N−1)N2πm​​⎠ ⎞​​⎭ ⎬ ⎫​

注2：我们把普通项拿出来，看看：

$x\left(a\right)e^{-ib\frac{2\pi \cdot a}{N}}{e}^{ib\frac{2\pi m}{N}}=x\left(a\right)e^{-i\left(b\frac{2\pi \cdot a}{N}-b\frac{2\pi m}{N}\right)}=x\left(a\right)e^{i\frac{2\pi }{N}b\left(m-a\right)},a\in \left[0,N-1\right],b\in \left[0,N-1\right]$

将上式重新化简：

= 1 N × { x ( 0 ) ∑ b = 0 N − 1 e − i 2 π N b ( m − 0 ) + x ( 1 ) ∑ b = 0 N − 1 e − i 2 π N b ( m − 1 ) + ⋯ + x ( a ) ∑ b = 0 N − 1 e − i 2 π N b ( m − a ) + ⋯ + x ( N − 1 ) ∑ b = 0 N − 1 e − i 2 π N b ( m − ( N − 1 ) ) } = ∑ a = 0 N − 1 x ( a ) ∑ b = 0 N − 1 e − i 2 π N b ( m − a )

=N1​×{x(0)b=0∑N−1​e−iN2π​b(m−0)+x(1)b=0∑N−1​e−iN2π​b(m−1)+⋯+x(a)b=0∑N−1​e−iN2π​b(m−a)+⋯+x(N−1)b=0∑N−1​e−iN2π​b(m−(N−1))}=a=0∑N−1​x(a)b=0∑N−1​e−iN2π​b(m−a)​

注3：推导思路总结，先展到最开，然后先列相加，再行相加。

当$m=a$时， $\sum _{b=0}^{N-1}{e}^{-i\frac{2\pi }{N}b\left(m-a\right)}=\sum _{b=0}^{N-1}1=N$

当 $m\ne a$时， $\sum _{b=0}^{N-1}{e}^{-i\frac{2\pi }{N}b\left(m-a\right)}=0$，下面证明

证明:
{

假设存在一个公比为 $q=e^{-i\frac{2\pi }{N}\left(m-a\right)}$的等比数列。

$A_1=e^{-i\frac{2\pi }{N}0\left(m-a\right)}$, $A_2=e^{-i\frac{2\pi }{N}1\left(m-a\right)}$, $A_n=e^{-i\frac{2\pi }{N}\left(N-1\right)\left(m-a\right)}$

∑ b = 0 N − 1 e − i 2 π N b ( m − a ) = ∑ i = 1 n A i = A 1 − A n q 1 − q = 1 − e − i 2 π N ( N − 1 ) ( m − a ) e − i 2 π N ( m − a ) 1 − e − i 2 π N ( m − a ) = 1 − e − i 2 π N N ( m − a ) 1 − e − i 2 π N ( m − a ) = 1 − e − i 2 π ( m − a ) 1 − e − i 2 π N ( m − a )

b=0∑N−1​e−iN2π​b(m−a)​=i=1∑n​Ai​=1−qA1​−An​q​=1−e−iN2π​(m−a)1−e−iN2π​(N−1)(m−a)e−iN2π​(m−a)​=1−e−iN2π​(m−a)1−e−iN2π​N(m−a)​=1−e−iN2π​(m−a)1−e−i2π(m−a)​​

$m-a$ 为整数，$m\ne a$且$m-a\ne 0$ ，可得

$e^{-i2\pi \left(m-a\right)}=\cos \left(2\pi \left(m-a\right)\right)-\sin \left(2\pi \left(m-a\right)\right)j=1-0j=1\Rightarrow \sum _{b=0}^{N-1}{e}^{-i\frac{2\pi }{N}b\left(m-a\right)}=\frac{1-1}{1-e^{-i\frac{2\pi }{N}\left(m-a\right)}}=0$

证毕。
}

当$m=a$时， $\sum _{b=0}^{N-1}{e}^{-i\frac{2\pi }{N}b\left(m-a\right)}=\sum _{b=0}^{N-1}1=N$

当 $m\ne a$时， $\sum _{b=0}^{N-1}{e}^{-i\frac{2\pi }{N}b\left(m-a\right)}=0$。

那么外层求和就只剩 $x\left(m\right)$项了。

即：

F − 1 { F [ x ( m ) ] } = 1 N ∑ a = 0 N − 1 x ( a ) ∑ b = 0 N − 1 e − i 2 π N b ( m − a ) = 1 N x ( m ) ∑ b = 0 N − 1 1 = x ( m ) {F^{ - 1}}\left\{ {F\left[ {x\left( m \right)} \right]} \right\} = \frac{1}{N}\sum\limits_{a = 0}^{N - 1} {x\left( a \right)\sum\limits_{b = 0}^{N - 1} {{e^{ - i\frac{{2\pi }}{N}b\left( {m - a} \right)}}} } = \frac{1}{N}x\left( m \right)\sum\limits_{b = 0}^{N - 1} 1 = x\left( m \right) F−1{F[x(m)]}=N1​a=0∑N−1​x(a)b=0∑N−1​e−iN2π​b(m−a)=N1​x(m)b=0∑N−1​1=x(m) 证毕。

把上述的推导先进行一个总结：

$X\left(n\right)=\frac{1}{N}\sum _{k=0}^{N-1}x\left(k\right)e^{-in\frac{2\pi k}{N}}$

$x\left(m\right)=\sum _{n=0}^{N-1}\left[X\left(n\right)\cdot e^{in\frac{2\pi m}{N}}\right]$

注意到这个系数 $\frac{1}{N}$ 在非周期函数的连续时间傅里叶变换当中，也有一个系数 $\frac{1}{2\pi }$ ，它是放到了傅里叶逆变换的。

$f\left(t\right)=\frac{1}{2\pi }{\int }_{-\infty }^{\infty }{\int }_{-\infty }^{\infty }f\left(t\right)e^{-i\omega t}dt{e}^{i\omega t}d\omega$

$F\left(\omega \right)\triangleq {\int }_{-\infty }^{\infty }f\left(t\right)e^{-i\omega t}dt$ ， 傅里叶变换。

$f\left(t\right)=\frac{1}{2\pi }{\int }_{-\infty }^{\infty }F\left(\omega \right)e^{i\omega t}d\omega$， 傅里叶逆变换。

为了和连续时间的傅里叶变换契合，离散时间的傅里叶变换也把系数$\frac{1}{N}$放到逆变换中（本质上是等价的 F − 1 { F [ x ( m ) ] } {F^{ - 1}}\left\{ {F\left[ {x\left( m \right)} \right]} \right\} F−1{F[x(m)]}还是$=x\left(m\right)$ ）即

$X\left(n\right)=\sum _{k=0}^{N-1}x\left(k\right)e^{-in\frac{2\pi k}{N}}$

$x\left(m\right)=\frac{1}{N}\sum _{n=0}^{N-1}\left[X\left(n\right)\cdot e^{in\frac{2\pi m}{N}}\right]$

上述推导结果，除了用的符号不同，与书籍《快速傅里叶变换 算法与应用》中定义已经一模一样啦。

3、推导总结

最终离散傅里叶变换公式如下：

$X\left(n\right)=\sum _{k=0}^{N-1}x\left(k\right)e^{-in\frac{2\pi k}{N}}$

$x\left(m\right)=\frac{1}{N}\sum _{n=0}^{N-1}\left[X\left(n\right)\cdot e^{in\frac{2\pi m}{N}}\right]$

系列学习链接：欢迎大家点赞、收藏、留言讨论。

傅里叶级数与傅里叶变换_Part0_欧拉公式证明+三角函数和差公式证明

傅里叶级数与傅里叶变换_Part1_三角函数系的正交性

傅里叶级数与傅里叶变换_Part2_周期为2Π的函数展开为傅里叶级数

傅里叶级数与傅里叶变换_Part3_周期为2L的函数展开为傅里叶级数

傅里叶级数与傅里叶变换_Part4_傅里叶级数的复数形式

傅里叶级数与傅里叶变换_Part5_傅里叶级数推导傅里叶变换

傅里叶级数与傅里叶变换_Part6_离散傅里叶变换推导

傅里叶级数与傅里叶变换_Part7_离散傅里叶变换的性质