數字信號處理一

注：本文并非所有原創，有部分參考并參考了網上的文章和圖片，若侵必刪！

從各個名詞的說起

FS，FT，LT、ZT、DTFT、DFS、DFT、FFT

先看這個一文弄懂DFT、DTFT、DFS的關系

另參考有道云筆記中的“從傅里葉級數到傅里葉變換”

先從圖直觀來看

x(t)及其傅里葉變換X(jw)

F ( j w ) = ∫ ? ∞ + ∞ f ( t ) e ? j ω t d t ( 1 ) f ( t ) = 1 2 π ∫ ? ∞ + ∞ F ( j w ) e j ω t d ω ( 2 ) F(jw)=\int_{-\infin}^{+\infin}f(t)e^{-j{\omega}t}d_t{\qquad}(1)\\ f(t)=\frac{1}{2\pi}\int_{-\infin}^{+\infin}F(jw)e^{j{\omega}t}d_{\omega}{\qquad}(2) F(jw)=∫?∞+∞?f(t)e?jωtdt?(1)f(t)=2π1?∫?∞+∞?F(jw)ejωtdω?(2)

• (1)頻域某個點（把 ω \omega ω視為常數），由時域各個時間點的疊加組成，因為時域是連續的，所以頻域某個頻率成分（頻率點）等于時域各個時間點的積分，
• (2)時域某個點（把 t t t視為常數），由頻域各個頻率成分的疊加組成，因為頻域是連續的，所以時域某個時間點等于頻域各個頻率成分（頻率點）的積分，

對時域采樣進行離散化

記住：周期沖激序列的傅里葉變換仍是周期沖激序列，強度和周期都是 2 π / T 2{\pi}/T 2π/T，時域相乘，等于頻域卷積，得到離散的 x ( n ) x(n) x(n)和連續的 X ( e j ω ) X(e^{j\omega}) X(ejω)，
δ T ( t ) = ∑ n = ? ∞ + ∞ δ ( t ? n T ) ? ω 0 δ ω 0 ( ω ) = ∑ n = ? ∞ + ∞ ω 0 δ ( ω ? n ω 0 ) ω 0 = 2 π T \delta_T(t)=\sum_{n=-\infin}^{+\infin}{\delta(t-nT)}{\Longleftrightarrow}{\omega_0}\delta_{\omega_0}(\omega)=\sum_{n=-\infin}^{+\infin}{{\omega_0}\delta({\omega}-n\omega_0)}\\ \omega_0=\frac{2\pi}{T} δT?(t)=n=?∞∑+∞?δ(t?nT)?ω0?δω0??(ω)=n=?∞∑+∞?ω0?δ(ω?nω0?)ω0?=T2π?

從結果可以發現，雖然時域被采樣離散化了，但頻域還是連續的，不利于計算機處理，所以我們對頻域進行采樣離散化(還有一種方法：在時域中選取N點，說白了就是對時域連續信號 x ( t ) x(t) x(t)進行N點采樣，然后將N點采樣信號進行周期延拓，虛擬成周期離散的信號并將其進行離散傅里葉變換，得到的頻譜圖即為周期離散的)，注意：從圖5到圖6就是DTFT，

同樣，頻域相乘等于時域卷積，從連續的 X ( e j ω ) X(e^{j\omega}) X(ejω)得到離散的 X ( k ) X(k) X(k)，注意：從 x ( n ) x(n) x(n)到 X ( k ) X(k) X(k)就是DFT，即從圖5到圖10，

從圖6到圖10經過了離散化，所以橫坐表也從 ω \omega ω變為了k，k也可以認為是頻率，

各個變換的關系-圖示

• 非周期序列x(n)的N點DFT就是X(k)（即圖10），但是k需滿足 0 ≤ k ≤ N ? 1 0{\le}k{\le}N-1 0≤k≤N?1，即將k的取值限制在主值區間，這隱含X(k)是周期函式，
• 對x(n)周期化后，再求其DFS，結果其實就是DFT，只不過DFS的結果中對k沒有要求，
• DFT的結果與選取的點數N有關，N越大，結果越精確，
• 可見，DFT只是為了計算機處理方便，在頻率域對DTFT進行的采樣并截取主值而已，有人可能疑惑，對圖(10)進行IDFT，回到時域即圖(9)，它與原離散信號圖(5)所示的x[n]不同呀，它是x[n]的周期性延拓！沒錯，因此你去查找一個IDFT的定義式，是不是對n的取值區間進行限制了呢？這一限制的含義就是，取該周期延拓序列的主值區間，即可還原x[n]！

一圖理解DFT

FS表示傅里葉級數

話說傅里葉大佬發現了任何一個周期函式都能用許多個正弦函式之和來表示，即
f T ( t ) = a 0 2 + ∑ n = 1 ∞ ( a n cos ? ( n ω 0 t ) + b n sin ? ( n ω 0 t ) ) n = 0 , 1 , 2 , . . . 其 中 a n = 2 T ∫ t 0 t 0 + T f T ( t ) cos ? ( n ω 0 t ) d t n = 0 , 1 , 2 , . . . b n = 2 T ∫ t 0 t 0 + T f T ( t ) sin ? ( n ω 0 t ) d t n = 0 , 1 , 2 , . . . f_T(t)=\frac{a_0}{2}+\sum_{n=1}^{\infin}(a_n{\cos}(n{\omega_0}t)+b_n{\sin}({n\omega_0}t)){\qquad}n=0,1,2,...\\ 其中\\ a_n=\frac{2}{T}\int_{t_0}^{t_0+T}f_T(t)\cos(n{\omega_0}t)d_t{\qquad}n=0,1,2,...\\ b_n=\frac{2}{T}\int_{t_0}^{t_0+T}f_T(t)\sin(n{\omega_0}t)d_t{\qquad}n=0,1,2,...\\ fT?(t)=2a0??+n=1∑∞?(an?cos(nω0?t)+bn?sin(nω0?t))n=0,1,2,...其中an?=T2?∫t0?t0?+T?fT?(t)cos(nω0?t)dt?n=0,1,2,...bn?=T2?∫t0?t0?+T?fT?(t)sin(nω0?t)dt?n=0,1,2,...
或者寫成指數形式：
f T ( t ) = ∑ n = ? ∞ + ∞ F n e j n ω 0 t ω 0 = 2 π T ( 1 ) F n = 1 T ∫ ? T 2 T 2 f T ( t ) e ? j n ω 0 t d t n = 0 , ± 1 , ± 2 , . . . ( 2 ) f_T(t)=\sum_{n=-\infin}^{+\infin}F_ne^{j{n\omega_0}t}{\qquad}\omega_0=\frac{2\pi}{T}{\qquad}(1)\\ F_n=\frac{1}{T}\int_{-\frac{T}{2}}^{\frac{T}{2}}f_T(t)e^{-jn{\omega_0}t}d_t{\qquad}n=0,\pm1,\pm2,...{\qquad}(2) fT?(t)=n=?∞∑+∞?Fn?ejnω0?tω0?=T2π?(1)Fn?=T1?∫?2T?2T??fT?(t)e?jnω0?tdt?n=0,±1,±2,...(2)
時頻域變換解釋：

• (1)時域某個時間點，由頻域各個頻率成分( n ω 0 n{\omega}_0 nω0?)的疊加組成，
• (2)頻域某個頻率成分的強度，由時域各個時間點的疊加組成（時域是連續的，所以是積分），

但是對于非周期函式卻不能展開成傅里葉級數，此時就演變出了傅里葉變換，

FT表示傅里葉變換

從FS到FT的推導就省略了，下面是結果：
f ( t ) = 1 2 π ∫ ? ∞ + ∞ ∫ ? ∞ + ∞ f ( t ) e ? j ω t d t e j ω t d ω F ( j w ) = ∫ ? ∞ + ∞ f ( t ) e ? j ω t d t ( 1 ) f ( t ) = 1 2 π ∫ ? ∞ + ∞ F ( j w ) e j ω t d ω ( 2 ) f(t)=\frac{1}{2\pi}\int_{-\infin}^{+\infin}\int_{-\infin}^{+\infin}f(t)e^{-j{\omega}t}d_te^{j{\omega}t}d_{\omega}\\ F(jw)=\int_{-\infin}^{+\infin}f(t)e^{-j{\omega}t}d_t{\qquad}(1)\\ f(t)=\frac{1}{2\pi}\int_{-\infin}^{+\infin}F(jw)e^{j{\omega}t}d_{\omega}{\qquad}(2) f(t)=2π1?∫?∞+∞?∫?∞+∞?f(t)e?jωtdt?ejωtdω?F(jw)=∫?∞+∞?f(t)e?jωtdt?(1)f(t)=2π1?∫?∞+∞?F(jw)ejωtdω?(2)
時頻域變換解釋：

• (2)時域某個時間點，由頻域各個頻率成分( ω {\omega} ω)的疊加組成（頻域是連續的，所以是積分），
• (1)頻域某個頻率成分，由時域各個時間點的疊加組成（時域是連續的，所以是積分），

FT能夠將信號從時域搬到頻域，便于分析；但還是不利于處理，因為計算機能夠處理的都是數字信號，即是離散的，因此可以通過抽樣在時域進行離散化，

上式運算式是有條件的，即 f ( t ) f(t) f(t)滿足絕對可積，然而連續周期信號并不滿足，但是它可以展開成傅里葉級數，引入沖激函式后也可表示其傅里葉變換，

周期信號的傅里葉變換

周期信號不滿足絕對可積的條件，但引入沖激函式后即可求得其傅里葉變換，

那么周期信號的FT是什么呢？

下面這個推導不是很好理解：

信號與系統書上的推導（比較好理解）：
∵ f T ( t ) = ∑ n = ? ∞ ∞ F n e j n ω 0 t , ω 0 = 2 π T ∴ F T ( j w ) = F [ f T ( t ) ] = F [ ∑ n = ? ∞ ∞ F n e j n ω 0 t ] = ∑ n = ? ∞ ∞ F n F [ e j n ω 0 t ] ∵ F [ e j n ω 0 t ] = 2 π δ ( ω ? n ω 0 ) ∴ F T ( j w ) = 2 π ∑ n = ? ∞ ∞ F n δ ( ω ? n ω 0 ) {\because}{\quad}f_T(t)=\sum_{n=-\infin}^{\infin}F_ne^{jn{\omega_0}t},{\quad}{\omega_0}=\frac{2\pi}{T}\\ {\therefore}{\quad}F_T(jw)={\mathscr{F}}[f_T(t)]={\mathscr{F}}[\sum_{n=-\infin}^{\infin}F_ne^{jn{\omega_0}t}]=\sum_{n=-\infin}^{\infin}F_n{\mathscr{F}}[e^{jn{\omega_0}t}]\\ {\because}{\quad}{\mathscr{F}}[e^{jn{\omega_0}t}]=2{\pi}{\delta}(\omega-n\omega_0)\\ {\therefore}{\quad}F_T(jw)=2{\pi}\sum_{n=-\infin}^{\infin}F_n{\delta}(\omega-n\omega_0) ∵fT?(t)=n=?∞∑∞?Fn?ejnω0?t,ω0?=T2π?∴FT?(jw)=F[fT?(t)]=F[n=?∞∑∞?Fn?ejnω0?t]=n=?∞∑∞?Fn?F[ejnω0?t]∵F[ejnω0?t]=2πδ(ω?nω0?)∴FT?(jw)=2πn=?∞∑∞?Fn?δ(ω?nω0?)
上式表明：周期信號的傅里葉變換由無窮多個出現在諧波頻率 n ω 0 n\omega_0 nω0?上的沖激函陣列成，每一沖激的強度為傅里葉系數 F n F_n Fn?乘上 2 π 2\pi 2π

單位周期沖激序列 δ T ( t ) \delta_T(t) δT?(t)的傅里葉變換是什么呢？

• 周期性沖激序列 δ T ( t ) \delta_T(t) δT?(t)的傅里葉系數 F n = 1 / T F_n=1/T Fn?=1/T，

已 知 δ T ( t ) = ∑ n = ? ∞ ∞ δ ( t ? n T ) , ω 0 = 2 π T ∵ f ( t ) = δ T ( t ) → F n = 1 T ∴ F [ δ T ( t ) ] = 2 π ∑ n = ? ∞ ∞ F n δ ( ω ? n ω 0 ) = 2 π T ∑ n = ? ∞ ∞ δ ( ω ? n ω 0 ) = ω 0 ∑ n = ? ∞ ∞ δ ( ω ? n ω 0 ) = ω 0 δ ω 0 ( ω ) 已知{\quad}\delta_T(t)=\sum_{n=-\infin}^{\infin}\delta(t-nT),{\quad}\omega_0=\frac{2\pi}{T}\\ {\because}{\quad}f(t)=\delta_T(t){\rightarrow}F_n=\frac{1}{T}\\ {\therefore}{\quad}{\mathscr{F}}[\delta_T(t)]=2{\pi}\sum_{n=-\infin}^{\infin}F_n\delta(\omega-n\omega_0)=\frac{2\pi}{T}\sum_{n=-\infin}^{\infin}\delta(\omega-n\omega_0)=\\ \omega_0\sum_{n=-\infin}^{\infin}\delta(\omega-n\omega_0)=\omega_0\delta_{\omega_0}(\omega)\\ 已知δT?(t)=n=?∞∑∞?δ(t?nT),ω0?=T2π?∵f(t)=δT?(t)→Fn?=T1?∴F[δT?(t)]=2πn=?∞∑∞?Fn?δ(ω?nω0?)=T2π?n=?∞∑∞?δ(ω?nω0?)=ω0?n=?∞∑∞?δ(ω?nω0?)=ω0?δω0??(ω)

結論：周期為T的沖激序列的傅里葉變換也是周期沖激序列，其強度是 ω 0 = 2 π T {\omega_0}=\frac{2\pi}{T} ω0?=T2π?，其周期也是 ω 0 \omega_0 ω0?，

DFTF表示離散時間傅里葉變換

重點是在于離散時間，即在時間域上是離散的，但其變換的結果在頻域上依然是連續的，

∵ x s ( t ) = x ( t ) δ T ( t ) = x ( t ) ∑ n = ? ∞ ∞ δ ( t ? n T ) ∴ X s ( j ω ) = F [ x s ( t ) ] = ∫ ? ∞ + ∞ x ( t ) ∑ n = ? ∞ ∞ δ ( t ? n T ) e ? j ω t d t = ∑ n = ? ∞ ∞ ∫ ? ∞ + ∞ x ( t ) δ ( t ? n T ) e ? j ω t d t = ∑ n = ? ∞ ∞ x ( n T ) e ? j ω n T ∫ ? ∞ + ∞ δ ( t ? n T ) d t = ∑ n = ? ∞ ∞ x ( n T ) e ? j ω n T {\because}{\quad}x_s(t)=x(t){\delta_T}(t)=x(t)\sum_{n=-\infin}^{\infin}{\delta}(t-nT)\\ {\therefore}{\quad}X_s(j\omega)={\mathscr{F}}[x_s(t)]=\int_{-\infin}^{+\infin}x(t)\sum_{n=-\infin}^{\infin}{\delta}(t-nT)e^{-j{\omega}t}d_t\\ =\sum_{n=-\infin}^{\infin}\int_{-\infin}^{+\infin}x(t)\delta(t-nT)e^{-j{\omega}t}d_t\\ =\sum_{n=-\infin}^{\infin}x(nT)e^{-j{\omega}nT}\int_{-\infin}^{+\infin}\delta(t-nT)d_t\\ =\sum_{n=-\infin}^{\infin}x(nT)e^{-j{\omega}nT} ∵xs?(t)=x(t)δT?(t)=x(t)n=?∞∑∞?δ(t?nT)∴Xs?(jω)=F[xs?(t)]=∫?∞+∞?x(t)n=?∞∑∞?δ(t?nT)e?jωtdt?=n=?∞∑∞?∫?∞+∞?x(t)δ(t?nT)e?jωtdt?=n=?∞∑∞?x(nT)e?jωnT∫?∞+∞?δ(t?nT)dt?=n=?∞∑∞?x(nT)e?jωnT
令T=1，則變為：
X s ( j ω ) = ∑ n = ? ∞ ∞ x ( n ) e ? j ω n 或 X ( e j ω ) = ∑ n = ? ∞ ∞ x ( n ) e ? j ω n X_s(j{\omega})=\sum_{n=-\infin}^{\infin}x(n)e^{-j{\omega}n}\\ 或{\quad} X(e^{j{\omega}})=\sum_{n=-\infin}^{\infin}x(n)e^{-j{\omega}n} Xs?(jω)=n=?∞∑∞?x(n)e?jωn或X(ejω)=n=?∞∑∞?x(n)e?jωn
不管是 j ω , e j ω j\omega,e^{j\omega} jω,ejω，還是 e j Ω e^{j\Omega} ejΩ，最終的自變數都是 ω \omega ω（ ω = Ω T {\omega}={\Omega}T ω=ΩT，T為采樣周期），

數字信號處理書上的定義：
X ( e j ω ) = F [ x ( n ) ] = ∑ n = ? ∞ ∞ x ( n ) e ? j ω n ( 1 ) x ( n ) = F ? [ X ( e j ω ) ] = 1 2 π ∫ ? π π X ( e j ω ) e j ω n d ω ( 2 ) X(e^{j\omega})={\mathscr{F}}[x(n)]=\sum_{n=-\infin}^{\infin}x(n)e^{-j{\omega}n}{\qquad}(1)\\ x(n)={\mathscr{F}^-}[X(e^{j\omega})]=\frac{1}{2\pi}\int_{-\pi}^{_\pi}X(e^{j\omega})e^{j{\omega}n}d_{\omega}{\qquad}(2) X(ejω)=F[x(n)]=n=?∞∑∞?x(n)e?jωn(1)x(n)=F?[X(ejω)]=2π1?∫?ππ??X(ejω)ejωndω?(2)
時頻域變換解釋：

• (1)頻域某個頻率成分，由時域各個序列點的疊加組成（時域是離散的，所以是求和），
• (2)時域某個序列點，由頻域各個頻率成分( ω {\omega} ω)的疊加組成（頻域是連續的，所以是積分），

上式運算式是有條件的，即 x ( n ) x(n) x(n)滿足絕對可和，然而離散周期信號并不滿足，但是它可以展開成離散傅里葉級數，如下，另外，可以發現DTFT的結果中 ω \omega ω仍然是連續的，不利于計算機處理，

DFS表示離散傅里葉級數

設 x ( n ) ~ \widetilde{x(n)} x(n) ?是以N為周期的周期序列，則其可以展開成離散傅里葉級數，

推導

我們知道 x ( n ) ~ \widetilde{x(n)} x(n) ?的基波成分為 e 1 ( n ) = a 1 e j 2 π N n e_1(n)=a_1e^{j\frac{2\pi}{N}n} e1?(n)=a1?ejN2π?n，k次諧波成分為 e k ( n ) = a k e j 2 π N k ? n e_k(n)=a_ke^{j\frac{2\pi}{N}k{\cdot}n} ek?(n)=ak?ejN2π?k?n，又因為 e j ( ( 2 π / N ) ( k + N ) n = e j ( ( 2 π / N ) k n e^{j((2\pi/N)(k+N)n}=e^{j((2\pi/N)kn} ej((2π/N)(k+N)n=ej((2π/N)kn，所以離散傅里葉級數中只有N個獨立的諧波成分，展開成傅里葉級數時，只能取 k = 0 → N ? 1 k=0{\rightarrow}N-1 k=0→N?1的N個獨立的諧波分量，k=0表示直流分量，因此， x ( n ) ~ \widetilde{x(n)} x(n) ?展開成離散傅里葉級數如下：
x ( n ) ~ = ∑ k = 0 N ? 1 a k e j 2 π N k n \widetilde{x(n)}=\sum_{k=0}^{N-1}a_ke^{j\frac{2\pi}{N}kn} x(n) ?=k=0∑N?1?ak?ejN2π?kn
為求系數 a k a_k ak?，將上式兩邊乘以 e ? j 2 π N m n e^{-j\frac{2\pi}{N}mn} e?jN2π?mn，并對n在一個周期N中求和，即：

定義

X ( k ) ~ = D F S [ x ( n ) ~ ] = ∑ n = 0 N ? 1 x ( n ) ~ e ? j 2 π N k n ( 1 ) x ( n ) ~ = I D F S [ X ( k ) ~ ] = 1 N ∑ k = 0 N ? 1 X ( k ) ~ e j 2 π N k n ( 2 ) \widetilde{X(k)}=DFS[\widetilde{x(n)}]=\sum_{n=0}^{N-1}\widetilde{x(n)}e^{-j{\frac{2\pi}{N}}kn}{\qquad}(1)\\ \widetilde{x(n)}=IDFS[\widetilde{X(k)}]=\frac{1}{N}\sum_{k=0}^{N-1}\widetilde{X(k)}e^{j{\frac{2\pi}{N}}kn}{\qquad}(2) X(k) ?=DFS[x(n) ?]=n=0∑N?1?x(n) ?e?jN2π?kn(1)x(n) ?=IDFS[X(k) ?]=N1?k=0∑N?1?X(k) ?ejN2π?kn(2)
時頻域變換解釋：

• (1)頻域某個頻率成分( ω = 2 π N k {\omega}=\frac{2\pi}{N}k ω=N2π?k)，由時域各個序列點的疊加組成（時域是離散的，所以是求和），
• (2)時域某個序列點，由頻域各個頻率成分( ω = 2 π N k {\omega}={\frac{2\pi}{N}k} ω=N2π?k)的疊加組成（頻域是離散的，所以是求和），
• 注意：
  • (1)的結果對k沒有限制，即k可以取從 ? ∞ -\infin ?∞到 + ∞ +\infin +∞的任何整數，對應的頻率就是 2 π N k \frac{2\pi}{N}k N2π?k；但是求和時只對n從0到N-1的序列點求和，
  • (2)的結果對n沒有限制，即n可以取從 ? ∞ -\infin ?∞到 + ∞ +\infin +∞的任何整數，對應的時間就是 n n n，但是求和時只對k從0到N-1的頻率成分求和，
  • 這是DFS與DFT最大的區別，也是聯系，

x ( n ) ~ \widetilde{x(n)} x(n) ?是以N為周期的周期序列，那為什么頻域的某個頻率成分只等于一個周期內( n = 0 → n = N ? 1 n=0{\rightarrow}n=N-1 n=0→n=N?1)的疊加呢？其它序列點不貢獻頻率成分嗎？詳看書上推導（主要原因是其獨立的頻率成分就只有N個），

和FS對比理解：
f T ( t ) = ∑ n = ? ∞ + ∞ F n e j n ω 0 t ( 1 ) F n = 1 T ∫ ? T 2 T 2 f T ( t ) e ? j n ω 0 t d t ( 2 ) f_T(t)=\sum_{n=-\infin}^{+\infin}F_ne^{j{n\omega_0}t}{\qquad}(1)\\ F_n=\frac{1}{T}\int_{-\frac{T}{2}}^{\frac{T}{2}}f_T(t)e^{-jn{\omega_0}t}d_t{\qquad}(2) fT?(t)=n=?∞∑+∞?Fn?ejnω0?t(1)Fn?=T1?∫?2T?2T??fT?(t)e?jnω0?tdt?(2)

DFT表示離散傅里葉變換

因為DTFT的結果在頻域上依然是連續的，不利于計算機處理，所以對頻域進行采樣離散化， x ( n ) x(n) x(n)是一個長度為M的有限長序列，則定義 x ( n ) x(n) x(n)的N點離散傅里葉變換為：

書上DFT的定義：
X ( k ) = D F T [ x ( n ) ] = ∑ n = 0 N ? 1 x ( n ) W N k n k = 0 , 1 , . . . , N ? 1 x ( n ) = I D F T [ X ( k ) ] = 1 N ∑ k = 0 N ? 1 X ( K ) W N ? k n n = 0 , 1 , . . . , N ? 1 W N = e ? j 2 π N X(k)=DFT[x(n)]=\sum_{n=0}^{N-1}x(n)W_N^{kn}{\quad}k=0,1,...,N-1\\ x(n)=IDFT[X(k)]=\frac{1}{N}\sum_{k=0}^{N-1}X(K)W_N^{-kn}{\quad}n=0,1,...,N-1\\ W_N=e^{-j\frac{2\pi}{N}}\\ X(k)=DFT[x(n)]=n=0∑N?1?x(n)WNkn?k=0,1,...,N?1x(n)=IDFT[X(k)]=N1?k=0∑N?1?X(K)WN?kn?n=0,1,...,N?1WN?=e?jN2π?
其實就是：
∵ W N = e ? j 2 π N ∴ X ( k ) = D F T [ x ( n ) ] = ∑ n = 0 N ? 1 x ( n ) e ? j 2 π N k n k = 0 , 1 , . . . , N ? 1 ( 1 ) x ( n ) = I D F T [ X ( k ) ] = ∑ k = 0 N ? 1 X ( K ) e j 2 π N k n n = 0 , 1 , . . . , N ? 1 ( 2 ) {\because}{\quad}W_N=e^{-j\frac{2\pi}{N}}\\ {\therefore}{\quad}X(k)=DFT[x(n)]=\sum_{n=0}^{N-1}x(n)e^{-j\frac{2\pi}{N}kn}{\quad}k=0,1,...,N-1{\qquad}(1)\\ x(n)=IDFT[X(k)]=\sum_{k=0}^{N-1}X(K)e^{j\frac{2\pi}{N}kn}{\quad}n=0,1,...,N-1{\qquad}(2)\\ ∵WN?=e?jN2π?∴X(k)=DFT[x(n)]=n=0∑N?1?x(n)e?jN2π?knk=0,1,...,N?1(1)x(n)=IDFT[X(k)]=k=0∑N?1?X(K)ejN2π?knn=0,1,...,N?1(2)
時頻域變換解釋：

• (1)頻域某個頻率成分( ω = 2 π N k {\omega}=\frac{2\pi}{N}k ω=N2π?k)，由時域各個序列點的疊加組成（時域是離散的，所以是求和），
• (2)時域某個序列點，由頻域各個頻率成分( ω = 2 π N k {\omega}={\frac{2\pi}{N}k} ω=N2π?k)的疊加組成（頻域是離散的，所以是求和），
• 注意：
  • (1)的結果對k有限制，即k只能取從0到N-1之間的整數，對應的頻率就是 2 π N k \frac{2\pi}{N}k N2π?k；求和時也是只對n從0到N-1的序列點求和，
  • (2)的結果對n有限制，即n只能取從0到N-1之間的整數，對應的時間/序列就是 n n n，求和時也是只對k從0到N-1的頻率成分求和，
  • 這是DFS與DFT最大的區別，也是聯系，

和DFS的區別：
X ( k ) ~ = D F S [ x ( n ) ~ ] = ∑ n = 0 N ? 1 x ( n ) ~ e ? j 2 π N k n x ( n ) ~ = I D F S [ X ( k ) ~ ] = 1 N ∑ n = 0 N ? 1 X ( k ) ~ e j 2 π N k n \widetilde{X(k)}=DFS[\widetilde{x(n)}]=\sum_{n=0}^{N-1}\widetilde{x(n)}e^{-j{\frac{2\pi}{N}}kn}\\ \widetilde{x(n)}=IDFS[\widetilde{X(k)}]=\frac{1}{N}\sum_{n=0}^{N-1}\widetilde{X(k)}e^{j{\frac{2\pi}{N}}kn} X(k) ?=DFS[x(n) ?]=n=0∑N?1?x(n) ?e?jN2π?knx(n) ?=IDFS[X(k) ?]=N1?n=0∑N?1?X(k) ?ejN2π?kn
不考慮其它的，DFS的運算式和DFT一模一樣，只是DFT對k和n的取值有限定，DFT中對k和n的限定其實就是使其在主值區間，看這，

周期序列的傅里葉變換運算式

先前說過，周期信號不滿足絕對可積，所以無法通過FT求得其傅里葉變換，但是引入沖激信號后可表示，周期序列也是一樣的，不滿足絕對可和，但通過展開成傅里葉級數，再引入沖激序列即可，如下：

還記得嗎？前面我們推導了周期信號的傅里葉變換是由一系列在諧波處的沖激函陣列成，其強度是傅里葉系數乘上 2 π 2\pi 2π；現在我們得到了復指數序列的傅里葉變換，其結果是在 ω 0 + 2 π r \omega_0+2{\pi}r ω0?+2πr(r為整數)處的單位沖激函式，強度為 2 π 2\pi 2π，周期序列的傅里葉變換是：
X ( e j ω ) = F [ x ( n ) ~ ] = ∑ k = 0 N ? 1 2 π X ( k ) ~ N ∑ r = ? ∞ ∞ δ ( ω ? 2 π N k ? 2 π r ) 式 中 , K = 0 , 1 , 2 , . . . , N ? 1 ， 如 果 讓 k 在 ? ∞ 到 ∞ 區 間 變 換 ， 上 式 可 簡 化 為 X ( e j ω ) = 2 π N ∑ k = ? ∞ ∞ X ( k ) ~ δ ( ω ? 2 π N k ) 式 中 X ( k ) ~ = ∑ n = 0 N ? 1 x ( n ) ~ e ? j 2 π N k n X(e^{j\omega})={\mathscr{F}}[\widetilde{x(n)}]=\sum_{k=0}^{N-1}\frac{2{\pi}{\widetilde{X(k)}}}{N}\sum_{r={-\infin}}^{\infin}\delta({\omega}-{\frac{2\pi}{N}k}-2{\pi}r)\\ 式中,K=0,1,2,...,N-1，如果讓k在-\infin到\infin區間變換，上式可簡化為\\ X(e^{j\omega})=\frac{2\pi}{N}\sum_{k={-\infin}}^{\infin}{\widetilde{X(k)}}\delta(\omega-\frac{2\pi}{N}k)\\ 式中{\qquad}{\widetilde{X(k)}}=\sum_{n=0}^{N-1}\widetilde{x(n)}e^{-j{\frac{2\pi}{N}}kn} X(ejω)=F[x(n) ?]=k=0∑N?1?N2πX(k) ??r=?∞∑∞?δ(ω?N2π?k?2πr)式中,K=0,1,2,...,N?1，如果讓k在?∞到∞區間變換，上式可簡化為X(ejω)=N2π?k=?∞∑∞?X(k) ?δ(ω?N2π?k)式中X(k) ?=n=0∑N?1?x(n) ?e?jN2π?kn

FFT表示快速傅里葉變換

FFT其實就是DFT，只不過是利用DFT的某些性質，使得計算更加快速，

DFT與FT,ZT的關系

設序列 x ( n ) x(n) x(n)的長度為M，

X ( z ) = Z T [ x ( n ) ] = ∑ n = 0 M ? 1 x ( n ) z ? n ( 1 ) X ( e j ω ) = D T F T [ x ( n ) ] = ∑ n = 0 M ? 1 x ( n ) e ? j ω n ( 2 ) X ( k ) = D F T [ x ( n ) ] N = ∑ n = 0 M ? 1 x ( n ) W N k n = ∑ n = 0 M ? 1 x ( n ) e ? j 2 π N n k k = 0 , 1 , . . . , N ? 1 ( 3 ) X(z)=ZT[x(n)]=\sum_{n=0}^{M-1}x(n)z^{-n}{\quad}(1)\\ X(e^{j\omega})=DTFT[x(n)]=\sum_{n=0}^{M-1}x(n)e^{-j{\omega}n}{\quad}(2)\\ X(k)=DFT[x(n)]_N=\sum_{n=0}^{M-1}x(n)W_N^{kn}\\ =\sum_{n=0}^{M-1}x(n)e^{-j\frac{2\pi}{N}nk}{\quad}k=0,1,...,N-1{\quad}(3)\\ X(z)=ZT[x(n)]=n=0∑M?1?x(n)z?n(1)X(ejω)=DTFT[x(n)]=n=0∑M?1?x(n)e?jωn(2)X(k)=DFT[x(n)]N?=n=0∑M?1?x(n)WNkn?=n=0∑M?1?x(n)e?jN2π?nkk=0,1,...,N?1(3)

• 序列 x ( n ) x(n) x(n)的N點DFT- X ( k ) X(k) X(k)是 x ( n ) x(n) x(n)的Z變換在單位圓上的N點等間隔采樣；
  X ( k ) = X ( z ) ∣ z = e j 2 π N k k = 0 , 1 , . . . , N ? 1 X(k)=X(z)\big|_{\color{blue}z=e^{j\frac{2\pi}{N}k}}{\quad}k=0,1,...,N-1 X(k)=X(z)∣∣?z=ejN2π?k?k=0,1,...,N?1
• X ( k ) X(k) X(k)是 x ( n ) x(n) x(n)的傅里葉變換 X ( e j ω ) X(e^{j\omega}) X(ejω)在區間 [ 0 , 2 π ] [0,\ 2\pi] [0, 2π]上的N點等間隔采樣；
  X ( k ) = X ( e j ω ) ∣ w = 2 π N k k = 0 , 1 , . . . , N ? 1 X(k)=X(e^{j\omega})\big|_{\color{blue}w=\frac{2\pi}{N}k}{\quad}k=0,1,...,N-1 X(k)=X(ejω)∣∣?w=N2π?k?k=0,1,...,N?1
  

FT與LT的關系

因為并不是所有的信號都能傅里葉變換（需要滿足絕對可積），所以可以乘上一個衰減因子 e ? δ t e^{-{\delta}t} e?δt，這樣能使新構造的信號滿足絕對可積，進而實作從時域變換到頻域（此時是復頻域），因為 e ? j ω t e ? δ t = e ? ( δ + j ω ) t = e ? s t e^{-j{\omega}t}e^{-{\delta}t}=e^{-{({\delta+j\omega})t}}=e^{-st} e?jωte?δt=e?(δ+jω)t=e?st， s = δ + j ω s=\delta+j\omega s=δ+jω即為復頻域，當δ為0時，即退化為傅里葉變換，

即LT變換是FT的推廣，從頻域推廣到復頻域，

各個變換的公式匯總

FS

f T ( t ) = ∑ n = ? ∞ + ∞ F n e j n ω 0 t ω 0 = 2 π T ( 1 ) F n = 1 T ∫ ? T 2 T 2 f T ( t ) e ? j n ω 0 t d t n = 0 , ± 1 , ± 2 , . . . ( 2 ) f_T(t)=\sum_{n=-\infin}^{+\infin}F_ne^{j{n\omega_0}t}{\qquad}\omega_0=\frac{2\pi}{T}{\qquad}(1)\\ F_n=\frac{1}{T}\int_{-\frac{T}{2}}^{\frac{T}{2}}f_T(t)e^{-jn{\omega_0}t}d_t{\qquad}n=0,\pm1,\pm2,...{\qquad}(2) fT?(t)=n=?∞∑+∞?Fn?ejnω0?tω0?=T2π?(1)Fn?=T1?∫?2T?2T??fT?(t)e?jnω0?tdt?n=0,±1,±2,...(2)

FT

f ( t ) = 1 2 π ∫ ? ∞ + ∞ ∫ ? ∞ + ∞ f ( t ) e ? j ω t d t e j ω t d ω F ( j w ) = ∫ ? ∞ + ∞ f ( t ) e ? j ω t d t ( 1 ) f ( t ) = 1 2 π ∫ ? ∞ + ∞ F ( j w ) e j ω t d ω ( 2 ) f(t)=\frac{1}{2\pi}\int_{-\infin}^{+\infin}\int_{-\infin}^{+\infin}f(t)e^{-j{\omega}t}d_te^{j{\omega}t}d_{\omega}\\ F(jw)=\int_{-\infin}^{+\infin}f(t)e^{-j{\omega}t}d_t{\qquad}(1)\\ f(t)=\frac{1}{2\pi}\int_{-\infin}^{+\infin}F(jw)e^{j{\omega}t}d_{\omega}{\qquad}(2) f(t)=2π1?∫?∞+∞?∫?∞+∞?f(t)e?jωtdt?ejωtdω?F(jw)=∫?∞+∞?f(t)e?jωtdt?(1)f(t)=2π1?∫?∞+∞?F(jw)ejωtdω?(2)

DTFT

X ( e j ω ) = F [ x ( n ) ] = ∑ n = ? ∞ ∞ x ( n ) e ? j ω n ( 1 ) x ( n ) = F ? [ X ( e j ω ) ] = 1 2 π ∫ ? π π X ( e j ω ) e j ω n d ω ( 2 ) X(e^{j\omega})={\mathscr{F}}[x(n)]=\sum_{n=-\infin}^{\infin}x(n)e^{-j{\omega}n}{\qquad}(1)\\ x(n)={\mathscr{F}^-}[X(e^{j\omega})]=\frac{1}{2\pi}\int_{-\pi}^{_\pi}X(e^{j\omega})e^{j{\omega}n}d_{\omega}{\qquad}(2) X(ejω)=F[x(n)]=n=?∞∑∞?x(n)e?jωn(1)x(n)=F?[X(ejω)]=2π1?∫?ππ??X(ejω)ejωndω?(2)

DFS

X ( k ) ~ = D F S [ x ( n ) ~ ] = ∑ n = 0 N ? 1 x ( n ) ~ e ? j 2 π N k n ( 1 ) x ( n ) ~ = I D F S [ X ( k ) ~ ] = 1 N ∑ k = 0 N ? 1 X ( k ) ~ e j 2 π N k n ( 2 ) \widetilde{X(k)}=DFS[\widetilde{x(n)}]=\sum_{n=0}^{N-1}\widetilde{x(n)}e^{-j{\frac{2\pi}{N}}kn}{\qquad}(1)\\ \widetilde{x(n)}=IDFS[\widetilde{X(k)}]=\frac{1}{N}\sum_{k=0}^{N-1}\widetilde{X(k)}e^{j{\frac{2\pi}{N}}kn}{\qquad}(2) X(k) ?=DFS[x(n) ?]=n=0∑N?1?x(n) ?e?jN2π?kn(1)x(n) ?=IDFS[X(k) ?]=N1?k=0∑N?1?X(k) ?ejN2π?kn(2)

DFT

X ( k ) = D F T [ x ( n ) ] = ∑ n = 0 N ? 1 x ( n ) W N k n k = 0 , 1 , . . . , N ? 1 = ∑ n = 0 N ? 1 x ( n ) e ? j 2 π N n k k = 0 , 1 , . . . , N ? 1 ( 1 ) x ( n ) = I D F T [ X ( k ) ] = 1 N ∑ k = 0 N ? 1 X ( K ) W N ? k n n = 0 , 1 , . . . , N ? 1 = ∑ n = 0 N ? 1 x ( n ) e j 2 π N k n k = 0 , 1 , . . . , N ? 1 ( 2 ) W N = e ? j 2 π N X(k)=DFT[x(n)]=\sum_{n=0}^{N-1}x(n)W_N^{kn}{\quad}k=0,1,...,N-1\\=\sum_{n=0}^{N-1}x(n)e^{-j\frac{2\pi}{N}nk}{\quad}k=0,1,...,N-1{\qquad}(1)\\x(n)=IDFT[X(k)]=\frac{1}{N}\sum_{k=0}^{N-1}X(K)W_N^{-kn}{\quad}n=0,1,...,N-1\\=\sum_{n=0}^{N-1}x(n)e^{j\frac{2\pi}{N}kn}{\quad}k=0,1,...,N-1{\qquad}(2)\\ {\color{blue}W_N=e^{-j\frac{2\pi}{N}}}\\ X(k)=DFT[x(n)]=n=0∑N?1?x(n)WNkn?k=0,1,...,N?1=n=0∑N?1?x(n)e?jN2π?nkk=0,1,...,N?1(1)x(n)=IDFT[X(k)]=N1?k=0∑N?1?X(K)WN?kn?n=0,1,...,N?1=n=0∑N?1?x(n)ejN2π?knk=0,1,...,N?1(2)WN?=e?jN2π?

總結

• FT的時域是連續的、即物件是 x ( t ) x(t) x(t)，而DFT的時域是離散的、即物件是 x ( n ) x(n) x(n)，但變換的結果在頻域都是連續的；

• DFT與DTFT都是對時域離散序列 x ( n ) x(n) x(n)進行頻域變換；

• DTFT的結果在頻域是連續的，但DFT的結果在頻域是離散的；

• FT/DTFT的頻率是 e j ω ? ω e^{j\omega}{\longrightarrow}\omega ejω?ω、即連續的，DFT的頻率是 e j 2 π N k n ? ω = 2 π N k e^{j\frac{2\pi}{N}kn}{\longrightarrow}\omega=\frac{2\pi}{N}k ejN2π?kn?ω=N2π?k，怎么理解 2 π N k \frac{2\pi}{N}k N2π?k是頻率呢？我們知道 x ( n ) x(n) x(n)是由 x ( t ) x(t) x(t)采樣而來的，假設采樣頻率為 f s f_s fs?且滿足奈奎斯特采樣定理，則采樣后的頻譜是周期的、未混疊的；
  
  ( 0 , π ) (0,\pi) (0,π)對應著 ( 0 , 0.5 f s ) (0,0.5f_s) (0,0.5fs?)，因為 ( 0 , ? π ) (0,-\pi) (0,?π)和 ( 0 , π ) (0,\pi) (0,π)是對稱的，所以就不用看了，現在就可以求得DFT的頻率了，即：
  ∵ 0.5 f s π = ω k 2 π N k ∴ ω k = 0.5 f s π 2 π N k k = 0 , 1 , . . . , N ? 1 \because{\quad}\frac{0.5f_s}{\pi}=\frac{\omega_k}{\frac{2\pi}{N}k}\\ \therefore{\quad}{\color{blue}\omega_k=\frac{0.5f_s}{\pi}\frac{2\pi}{N}k}\\ k=0,1,...,N-1 ∵π0.5fs??=N2π?kωk??∴ωk?=π0.5fs??N2π?kk=0,1,...,N?1
  

• x ( n ) x(n) x(n)是非周期的并且長度為N，我們對 x ( n ) x(n) x(n)進行周期延拓得到 x ( n ) ~ \widetilde{x(n)} x(n) ?， x ( n ) ~ \widetilde{x(n)} x(n) ?的DFS的結果 X ( k ) ~ \widetilde{X(k)} X(k) ?的主值序列等于 x ( n ) x(n) x(n)的DFT的結果 X ( k ) X(k) X(k)，