索引
单独视角: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ΔTf(t)e−j2πutdt=0+∫0NΔTf(t)e−j2πutdt=∫0NΔTf(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)=N1n=0∑N−1f⌢(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)=N1n=0∑N−1f⌢(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)=2N1u=0∑N−1F⌢(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)=2N1u=0∑N−1F⌢(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−1f(n)e−jN2πun,u=0,1,⋯,N−1f(n)=du=0∑N−1F(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=Aff=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)⋅0e−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)⋅0ejN2π⋅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=Aff=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−1ejN2π(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−1f(n)e−jN2πun,u=0,1,⋯,N−1f(n)=du=0∑N−1F(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−1e−jN4πk⋅i=c21−e−jN4πk1−e−jN4πk⋅N=0∀k1=k2,c2i=0∑N−1(e−jN2π⋅i⋅k1)(e−jN2π⋅i⋅k2)=c2i=0∑N−1e−jN2π(k1+k2)⋅i=c21−e−jN2π(k1+k2)1−e−jN2π(k1+k2)⋅N=0⇒AAT=ON×N