索引

单独视角：DFT公式的推导单独视角：IDFT公式的推导综合视角：DFT, IDFT公式组的系数修正

单独视角：DFT公式的推导

由博文一维连续傅里叶变换和逆变换公式的一种推导，设f(t)f\left( t \right)f(t)是一个连续的时间信号，其一维连续Fourier变换可取为

F(u)=∫−∞∞f(t)e−j2πutdtF\left( u \right)=\int_{-\infty }^{\infty }{f\left( t \right){{e}^{-j2\pi ut}}dt}F(u)=∫−∞∞​f(t)e−j2πutdt

步骤一

从某一时刻（记为000时刻）开始，每经过时间间隔ΔT\Delta TΔT就对连续函数f(t)f\left( t \right)f(t)采样一次，共采样NNN次。对连续函数f(t)f\left( t \right)f(t)等间隔采样就得到一个离散序列

f(ΔT),f(2ΔT),⋯,f(NΔT)f\left( \Delta T \right),f\left( 2\Delta T \right),\cdots ,f\left( N\Delta T \right)f(ΔT),f(2ΔT),⋯,f(NΔT)

记为

f⌢(0),f⌢(1),⋯,f⌢(N−1)\overset\frown{f}\left( 0 \right),\text{ }\overset\frown{f}\left( 1 \right),\text{ }\cdots ,\text{ }\overset\frown{f}\left( N-1 \right)f⌢​(0),f⌢​(1),⋯,f⌢​(N−1)

而对于其他没采样到的点，即∀t∉{ΔT,2ΔT,⋯NΔT}\forall t\notin \left\{ \Delta T,\text{ }2\Delta T,\cdots N\Delta T \right\}∀t∈/​{ΔT,2ΔT,⋯NΔT}，视该点处采样的函数值

f(t)=0f\left( t \right)=0f(t)=0

步骤二

将一维连续Fourier变换公式进行拆解

F(u)=∫−∞∞f(t)e−j2πutdt=∫−∞0+∫0NΔT+∫NΔT∞f(t)e−j2πutdt=∫−∞0+∫NΔT∞f(t)e−j2πutdt+∫0NΔTf(t)e−j2πutdt=0+∫0NΔTf(t)e−j2πutdt=∫0NΔTf(t)e−j2πutdt=F1(u)\begin{aligned} & F\left( u \right)=\int_{-\infty }^{\infty }{f\left( t \right){{e}^{-j2\pi ut}}dt} \\ & =\int_{-\infty }^{0}{+\int_{0}^{N\Delta T}{+\int_{N\Delta T}^{\infty }{f\left( t \right){{e}^{-j2\pi ut}}dt}}} \\ & =\int_{-\infty }^{0}{+\int_{N\Delta T}^{\infty }{f\left( t \right){{e}^{-j2\pi ut}}dt}}+\int_{0}^{N\Delta T}{f\left( t \right){{e}^{-j2\pi ut}}dt} \\ & =0+\int_{0}^{N\Delta T}{f\left( t \right){{e}^{-j2\pi ut}}dt} \\ & =\int_{0}^{N\Delta T}{f\left( t \right){{e}^{-j2\pi ut}}dt} \\ & ={{F}_{1}}\left( u \right) \\ \end{aligned}​F(u)=∫−∞∞​f(t)e−j2πutdt=∫−∞0​+∫0NΔT​+∫NΔT∞​f(t)e−j2πutdt=∫−∞0​+∫NΔT∞​f(t)e−j2πutdt+∫0NΔT​f(t)e−j2πutdt=0+∫0NΔT​f(t)e−j2πutdt=∫0NΔT​f(t)e−j2πutdt=F1​(u)​

步骤三

将F1(u){{F}_{1}}\left( u \right)F1​(u)转换为黎曼和形式F2(u){{F}_{2}}\left( u \right)F2​(u)，具体地说，把区间[0,NΔT]\left[ 0,N\Delta T \right][0,NΔT]等间隔分成NNN份，第iii个区间ki=[(i−1)ΔT,iΔT]{{k}_{i}}=\left[ \left( i-1 \right)\Delta T,i\Delta T \right]ki​=[(i−1)ΔT,iΔT]，i=1,2,⋯,Ni=1,2,\cdots ,Ni=1,2,⋯,N，每个区间长度为ΔT\Delta TΔT。在每个区间ki{{k}_{i}}ki​上取右端点的函数值f(iΔT)e−j2πu⋅(iΔT)f\left( i\Delta T \right){{e}^{-j2\pi u\centerdot \left( i\Delta T \right)}}f(iΔT)e−j2πu⋅(iΔT)。

F2(u)=∑i=1N[f(iΔT)e−j2πu⋅(iΔT)]⋅ΔT=∑n=0N−1[f((n+1)ΔT)e−j2πu⋅(n+1)ΔT]⋅ΔT=∑n=0N−1[f⌢(n)e−j2πu⋅(n+1)ΔT]⋅ΔT\begin{aligned} & {{F}_{2}}\left( u \right)=\sum\limits_{i=1}^{N}{\left[ f\left( i\Delta T \right){{e}^{-j2\pi u\centerdot \left( i\Delta T \right)}} \right]\centerdot \Delta T} \\ & =\sum\limits_{n=0}^{N-1}{\left[ f\left( \left( n+1 \right)\Delta T \right){{e}^{-j2\pi u\centerdot \left( n+1 \right)\Delta T}} \right]\centerdot \Delta T} \\ & =\sum\limits_{n=0}^{N-1}{\left[ \overset\frown{f}\left( n \right){{e}^{-j2\pi u\centerdot \left( n+1 \right)\Delta T}} \right]\centerdot \Delta T} \\ \end{aligned}​F2​(u)=i=1∑N​[f(iΔT)e−j2πu⋅(iΔT)]⋅ΔT=n=0∑N−1​[f((n+1)ΔT)e−j2πu⋅(n+1)ΔT]⋅ΔT=n=0∑N−1​[f⌢​(n)e−j2πu⋅(n+1)ΔT]⋅ΔT​

步骤四

若规定采样开始点和结束点之间的时长是1个单位时间，即

NΔT=1N\Delta T=1NΔT=1

则有

F2(u)=1N∑n=0N−1f⌢(n)e−j2πun+1N,u=0,1,⋯,N−1{{F}_{2}}\left( u \right)=\frac{1}{N}\sum\limits_{n=0}^{N-1}{\overset\frown{f}\left( n \right){{e}^{-j2\pi u\frac{n+1}{N}}}},\text{ }u=0,1,\cdots ,N-1F2​(u)=N1​n=0∑N−1​f⌢​(n)e−j2πuNn+1​,u=0,1,⋯,N−1

这就可定义为DFT的一条公式。

其他形式

在取相同的一维连续Fourier变换公式的基础上，更改步骤一如下。

步骤一

从某一时刻（记为0时刻）开始，采样，然后经过时间间隔ΔT\Delta TΔT才对f(t)f\left( t \right)f(t)采样一次，共采样NNN次。采样最后一次时再过时间ΔT\Delta TΔT才终止操作。对f(t)f\left( t \right)f(t)等间隔采样得到一个离散序列

f(0),f(ΔT),⋯,f((N−1)ΔT)f\left( 0 \right),\text{ }f\left( \Delta T \right),\text{ }\cdots ,\text{ }f\left( \left( N-1 \right)\Delta T \right)f(0),f(ΔT),⋯,f((N−1)ΔT)

记为

f⌢(0),f⌢(1),⋯,f⌢(N−1)\overset\frown{f}\left( 0 \right),\text{ }\overset\frown{f}\left( 1 \right),\text{ }\cdots ,\text{ }\overset\frown{f}\left( N-1 \right)f⌢​(0),f⌢​(1),⋯,f⌢​(N−1)

原步骤二无需变动。

原步骤三中只改动以下内容：在每个区间ki=[(i−1)ΔT,iΔT]{{k}_{i}}=\left[ \left( i-1 \right)\Delta T,\text{ }i\Delta T \right]ki​=[(i−1)ΔT,iΔT]上取左端点的函数值f((i−1)ΔT)e−j2πu⋅(i−1)ΔTf\left( \left( i-1 \right)\Delta T \right){{e}^{-j2\pi u\centerdot \left( i-1 \right)\Delta T}}f((i−1)ΔT)e−j2πu⋅(i−1)ΔT。

在NΔT=1N\Delta T=1NΔT=1的限制下，就可以得到另一条公式

F2(u)=1N∑n=0N−1f⌢(n)e−j2πunN,u=0,1,⋯,N−1{{F}_{2}}\left( u \right)=\frac{1}{N}\sum\limits_{n=0}^{N-1}{\overset\frown{f}\left( n \right){{e}^{-j2\pi u\frac{n}{N}}}},\text{ }u=0,1,\cdots ,N-1F2​(u)=N1​n=0∑N−1​f⌢​(n)e−j2πuNn​,u=0,1,⋯,N−1

单独视角：IDFT公式的推导

由博文一维连续傅里叶变换和逆变换公式的一种推导，设f(t)f\left( t \right)f(t)是一个连续的时间信号，其一维连续Fourier逆变换可取为

f(t)=12∫−∞∞F(u)ej2πutduf\left( t \right)=\frac{1}{2}\int_{-\infty }^{\infty }{F\left( u \right){{e}^{j2\pi ut}}du}f(t)=21​∫−∞∞​F(u)ej2πutdu

与DFT公式推导过程相似，可以得到IDFT的公式

f(n)=12N∑u=0N−1F⌢(u)ej2πnu+1N,n=0,1,⋯,N−1f\left( n \right)=\frac{1}{2N}\sum\limits_{u=0}^{N-1}{\overset\frown{F}\left( u \right){{e}^{j2\pi n\frac{u+1}{N}}}},\text{ }n=0,1,\cdots ,N-1f(n)=2N1​u=0∑N−1​F⌢(u)ej2πnNu+1​,n=0,1,⋯,N−1

或

f(n)=12N∑u=0N−1F⌢(u)ej2πnuN,n=0,1,⋯,N−1f\left( n \right)=\frac{1}{2N}\sum\limits_{u=0}^{N-1}{\overset\frown{F}\left( u \right){{e}^{j2\pi n\frac{u}{N}}}},\text{ }n=0,1,\cdots ,N-1f(n)=2N1​u=0∑N−1​F⌢(u)ej2πnNu​,n=0,1,⋯,N−1

综合视角：DFT, IDFT公式组的系数修正

为了实现对f(t)f\left( t \right)f(t)进行DFT，得到的结果进行IDFT还是得到f(t)f\left( t \right)f(t)，我们需要考虑DFT和IDFT公式的系数。令

F(u)=c∑n=0N−1f(n)e−j2πunN,u=0,1,⋯,N−1f(n)=d∑u=0N−1F(u)ej2πunN,n=0,1,⋯,N−1\begin{aligned} & F\left( u \right)=c\sum\limits_{n=0}^{N-1}{f\left( n \right){{e}^{-j\frac{2\pi un}{N}}}},\text{ }u=0,1,\cdots ,N-1 \\ & f\left( n \right)=d\sum\limits_{u=0}^{N-1}{F\left( u \right){{e}^{j\frac{2\pi un}{N}}}},\text{ }n=0,1,\cdots ,N-1 \\ \end{aligned}​F(u)=cn=0∑N−1​f(n)e−jN2πun​,u=0,1,⋯,N−1f(n)=du=0∑N−1​F(u)ejN2πun​,n=0,1,⋯,N−1​

设

F→=[F(0),F(1),⋯,F(n−1)]Tf→=[f(0),f(1),⋯,f(n−1)]T\begin{aligned} & \overrightarrow{F}={{\left[ F\left( 0 \right),\text{ }F\left( 1 \right),\text{ }\cdots ,\text{ }F\left( n-1 \right) \right]}^{T}} \\ & \overrightarrow{f}={{\left[ f\left( 0 \right),\text{ }f\left( 1 \right),\text{ }\cdots ,\text{ }f\left( n-1 \right) \right]}^{T}} \\ \end{aligned}​F=[F(0),F(1),⋯,F(n−1)]Tf​=[f(0),f(1),⋯,f(n−1)]T​

则有

F→=Af→f→=BF→\begin{aligned} & \overrightarrow{F}=A\overrightarrow{f} \\ & \overrightarrow{f}=B\overrightarrow{F} \\ \end{aligned}​F=Af​f​=BF​

其中

AN×N=c(e−j2πN⋅0⋅0e−j2πN⋅0⋅1⋯e−j2πN⋅0⋅(N−1)e−j2πN⋅1⋅0e−j2πN⋅1⋅1⋯e−j2πN⋅1⋅(N−1)⋮⋮⋱⋮e−j2πN⋅(N−1)⋅0e−j2πN⋅(N−1)⋅1⋯e−j2πN⋅(N−1)⋅(N−1))BN×N=d(ej2πN⋅0⋅0ej2πN⋅0⋅1⋯ej2πN⋅0⋅(N−1)ej2πN⋅1⋅0ej2πN⋅1⋅1⋯ej2πN⋅1⋅(N−1)⋮⋮⋱⋮ej2πN⋅(N−1)⋅0ej2πN⋅(N−1)⋅1⋯ej2πN⋅(N−1)⋅(N−1))\begin{aligned} & {{A}_{N\times N}}=c\left( \begin{matrix} {{e}^{-j\frac{2\pi }{N}\centerdot 0\centerdot 0}} & {{e}^{-j\frac{2\pi }{N}\centerdot 0\centerdot 1}} & \cdots & {{e}^{-j\frac{2\pi }{N}\centerdot 0\centerdot \left( N-1 \right)}} \\ {{e}^{-j\frac{2\pi }{N}\centerdot 1\centerdot 0}} & {{e}^{-j\frac{2\pi }{N}\centerdot 1\centerdot 1}} & \cdots & {{e}^{-j\frac{2\pi }{N}\centerdot 1\centerdot \left( N-1 \right)}} \\ \vdots & \vdots & \ddots & \vdots \\ {{e}^{-j\frac{2\pi }{N}\centerdot \left( N-1 \right)\centerdot 0}} & {{e}^{-j\frac{2\pi }{N}\centerdot \left( N-1 \right)\centerdot 1}} & \cdots & {{e}^{-j\frac{2\pi }{N}\centerdot \left( N-1 \right)\centerdot \left( N-1 \right)}} \\ \end{matrix} \right) \\ & {{B}_{N\times N}}=d\left( \begin{matrix} {{e}^{j\frac{2\pi }{N}\centerdot 0\centerdot 0}} & {{e}^{j\frac{2\pi }{N}\centerdot 0\centerdot 1}} & \cdots & {{e}^{j\frac{2\pi }{N}\centerdot 0\centerdot \left( N-1 \right)}} \\ {{e}^{j\frac{2\pi }{N}\centerdot 1\centerdot 0}} & {{e}^{j\frac{2\pi }{N}\centerdot 1\centerdot 1}} & \cdots & {{e}^{j\frac{2\pi }{N}\centerdot 1\centerdot \left( N-1 \right)}} \\ \vdots & \vdots & \ddots & \vdots \\ {{e}^{j\frac{2\pi }{N}\centerdot \left( N-1 \right)\centerdot 0}} & {{e}^{j\frac{2\pi }{N}\centerdot \left( N-1 \right)\centerdot 1}} & \cdots & {{e}^{j\frac{2\pi }{N}\centerdot \left( N-1 \right)\centerdot \left( N-1 \right)}} \\ \end{matrix} \right) \\ \end{aligned}​AN×N​=c⎝⎜⎜⎜⎛​e−jN2π​⋅0⋅0e−jN2π​⋅1⋅0⋮e−jN2π​⋅(N−1)⋅0​e−jN2π​⋅0⋅1e−jN2π​⋅1⋅1⋮e−jN2π​⋅(N−1)⋅1​⋯⋯⋱⋯​e−jN2π​⋅0⋅(N−1)e−jN2π​⋅1⋅(N−1)⋮e−jN2π​⋅(N−1)⋅(N−1)​⎠⎟⎟⎟⎞​BN×N​=d⎝⎜⎜⎜⎛​ejN2π​⋅0⋅0ejN2π​⋅1⋅0⋮ejN2π​⋅(N−1)⋅0​ejN2π​⋅0⋅1ejN2π​⋅1⋅1⋮ejN2π​⋅(N−1)⋅1​⋯⋯⋱⋯​ejN2π​⋅0⋅(N−1)ejN2π​⋅1⋅(N−1)⋮ejN2π​⋅(N−1)⋅(N−1)​⎠⎟⎟⎟⎞​​

显然有

F→=Af→f→=BF→}⇒F→=(AB)F→\left. \begin{aligned} & \overrightarrow{F}=A\overrightarrow{f} \\ & \overrightarrow{f}=B\overrightarrow{F} \\ \end{aligned} \right\}\text{ }\Rightarrow \text{ }\overrightarrow{F}=\left( AB \right)\overrightarrow{F}​F=Af​f​=BF​⎭⎬⎫​⇒F=(AB)F

于是自然地想要令

AB=IN×N⇔{∀k∈{0,1,⋯,N−1},cd∑i=0N−1(e−j2πN⋅i⋅k⋅ej2πN⋅i⋅k)=cdN=1∀k1≠k2,cd∑i=0N−1(e−j2πN⋅i⋅k1⋅ej2πN⋅i⋅k2)=cd∑i=0N−1ej2π(k2−k1)Ni=cd1−ej2π(k2−k1)N⋅N1−ej2π(k2−k1)N=0⇔cd=1N\begin{aligned} & \text{ }AB={{I}_{N\times N}} \\ & \Leftrightarrow \left\{ \begin{aligned} & \forall k\in \left\{ 0,1,\cdots ,N-1 \right\},\text{ }cd\sum\limits_{i=0}^{N-1}{\left( {{e}^{-j\frac{2\pi }{N}\centerdot i\centerdot k}}\centerdot {{e}^{j\frac{2\pi }{N}\centerdot i\centerdot k}} \right)}=cdN=1 \\ & \forall {{k}_{1}}\ne {{k}_{2}},\text{ }cd\sum\limits_{i=0}^{N-1}{\left( {{e}^{-j\frac{2\pi }{N}\centerdot i\centerdot {{k}_{1}}}}\centerdot {{e}^{j\frac{2\pi }{N}\centerdot i\centerdot {{k}_{2}}}} \right)}=cd\sum\limits_{i=0}^{N-1}{{{e}^{j\frac{2\pi \left( {{k}_{2}}-{{k}_{1}} \right)}{N}i}}}=cd\frac{1-{{e}^{j\frac{2\pi \left( {{k}_{2}}-{{k}_{1}} \right)}{N}\centerdot N}}}{1-{{e}^{j\frac{2\pi \left( {{k}_{2}}-{{k}_{1}} \right)}{N}}}}=0 \\ \end{aligned} \right. \\ & \Leftrightarrow cd=\frac{1}{N} \\ \end{aligned}​AB=IN×N​⇔⎩⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎧​​∀k∈{0,1,⋯,N−1},cdi=0∑N−1​(e−jN2π​⋅i⋅k⋅ejN2π​⋅i⋅k)=cdN=1∀k1​​=k2​,cdi=0∑N−1​(e−jN2π​⋅i⋅k1​⋅ejN2π​⋅i⋅k2​)=cdi=0∑N−1​ejN2π(k2​−k1​)​i=cd1−ejN2π(k2​−k1​)​1−ejN2π(k2​−k1​)​⋅N​=0​⇔cd=N1​​

因此最终我们得到DFT和IDFT的公式为

F(u)=c∑n=0N−1f(n)e−j2πunN,u=0,1,⋯,N−1f(n)=d∑u=0N−1F(u)ej2πunN,n=0,1,⋯,N−1cd=1N\begin{matrix} F\left( u \right)=c\sum\limits_{n=0}^{N-1}{f\left( n \right){{e}^{-j\frac{2\pi un}{N}}}},\text{ }u=0,1,\cdots ,N-1 \\ f\left( n \right)=d\sum\limits_{u=0}^{N-1}{F\left( u \right){{e}^{j\frac{2\pi un}{N}}}},\text{ }n=0,1,\cdots ,N-1 \\ cd=\frac{1}{N} \\ \end{matrix}F(u)=cn=0∑N−1​f(n)e−jN2πun​,u=0,1,⋯,N−1f(n)=du=0∑N−1​F(u)ejN2πun​,n=0,1,⋯,N−1cd=N1​​

此外，我们指出，对称阵A,BA,BA,B不可能为正交矩阵。事实上，有AAT=BBT=ON×N≠IN×NA{{A}^{T}}=B{{B}^{T}}={{O}_{N\times N}}\ne {{I}_{N\times N}}AAT=BBT=ON×N​​=IN×N​

以AAA为例子，计算AATA{{A}^{T}}AAT如下。

{∀k∈{0,1,⋯,N−1},c2∑i=0N−1(e−j2πN⋅i⋅k)2=c2∑i=0N−1e−j4πkN⋅i=c21−e−j4πkN⋅N1−e−j4πkN=0∀k1≠k2,c2∑i=0N−1(e−j2πN⋅i⋅k1)(e−j2πN⋅i⋅k2)=c2∑i=0N−1e−j2π(k1+k2)N⋅i=c21−e−j2π(k1+k2)N⋅N1−e−j2π(k1+k2)N=0⇒AAT=ON×N\begin{aligned} & \left\{ \begin{aligned} & \forall k\in \left\{ 0,1,\cdots ,N-1 \right\},\text{ }{{c}^{2}}\sum\limits_{i=0}^{N-1}{{{\left( {{e}^{-j\frac{2\pi }{N}\centerdot i\centerdot k}} \right)}^{2}}}={{c}^{2}}\sum\limits_{i=0}^{N-1}{{{e}^{-j\frac{4\pi k}{N}\centerdot i}}}={{c}^{2}}\frac{1-{{e}^{-j\frac{4\pi k}{N}\centerdot N}}}{1-{{e}^{-j\frac{4\pi k}{N}}}}=0 \\ & \forall {{k}_{1}}\ne {{k}_{2}},\text{ }{{c}^{2}}\sum\limits_{i=0}^{N-1}{\left( {{e}^{-j\frac{2\pi }{N}\centerdot i\centerdot {{k}_{1}}}} \right)\left( {{e}^{-j\frac{2\pi }{N}\centerdot i\centerdot {{k}_{2}}}} \right)}={{c}^{2}}\sum\limits_{i=0}^{N-1}{{{e}^{-j\frac{2\pi \left( {{k}_{1}}+{{k}_{2}} \right)}{N}\centerdot i}}}={{c}^{2}}\frac{1-{{e}^{-j\frac{2\pi \left( {{k}_{1}}+{{k}_{2}} \right)}{N}\centerdot N}}}{1-{{e}^{-j\frac{2\pi \left( {{k}_{1}}+{{k}_{2}} \right)}{N}}}}=0 \\ \end{aligned} \right. \\ & \\ & \Rightarrow \text{ }A{{A}^{T}}={{O}_{N\times N}} \\ \end{aligned}​⎩⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎧​​∀k∈{0,1,⋯,N−1},c2i=0∑N−1​(e−jN2π​⋅i⋅k)2=c2i=0∑N−1​e−jN4πk​⋅i=c21−e−jN4πk​1−e−jN4πk​⋅N​=0∀k1​​=k2​,c2i=0∑N−1​(e−jN2π​⋅i⋅k1​)(e−jN2π​⋅i⋅k2​)=c2i=0∑N−1​e−jN2π(k1​+k2​)​⋅i=c21−e−jN2π(k1​+k2​)​1−e−jN2π(k1​+k2​)​⋅N​=0​⇒AAT=ON×N​​