如何通俗地解釋什麼是離散傅里葉變換？

12-27

在學離散傅里葉變換(Discrete Fourier Transform)，但是對其不能理解。
能否通俗的講解一下？書上的講解DFT公式是怎麼來的，為什麼會這樣，都看不懂。
非常希望有人可以用一個例子給我講一下，比如在DFT之前我們收集的是什麼什麼樣本，為什麼要用DFT去變換這些樣本，變換完得到的新數據是用來幹什麼的。。
謝謝！

先說結論，不想看長答案的可以直接看:DTFT是給人用的，DFT是給機器用的，DFT是對DTFT的頻域採樣。

—————————————————————————

說DFT之前，我們先回憶一下以往的幾種傅里葉變換。

1、連續時間周期信號:處理時間連續並且具有周期性的信號，其頻域上離散，非周期。

2、連續時間非周期信號:處理時間連續但是不具有周期性的信號，其頻域上連續，非周期。

3、離散時間非周期信號:處理時間離散，不具有周期性的信號，其頻域上連續，有周期性。

4、離散時間周期信號:處理時間離散，具有周期性的信號，其頻域上離散，有周期性。

從理論上來說，這四種變換已經囊括了我們能遇到的信號種類了，那麼為什麼要額外引入DFT？從形式上看，DFT與離散時間周期信號的變換非常類似，有何原因？

首先，我們注意到在數字信號處理裡面，我們接觸的都是離散時間的信號，所以前兩種連續時間的傅里葉變換在我們這兒用不到。另外，數字信號處理的一個要點就是討論對數字信號的處理方式和演算法設計，這裡所說的處理方式不僅僅是人工的、解析的處理方式，更是機器能用的處理方式。

機器的局限性在哪呢？機器不能表達一個無限長的序列，也不能表達連續的頻域特徵。對於一般的離散時間信號而言，直接用DTFT確實很好，非常便於我們分析信號的頻域特徵，但問題是這一套機器是用不了的。因此我們才需要DFT，也就是說DTFT是給人用的，而DFT是給機器用的。

所謂DFT的引入，我認為主要可以分為兩點，一點是截斷，另一點是(頻域)採樣。需要截斷，是因為機器無法表示無限長的序列，只能處理有限長序列，這一點比較好理解。關於採樣，是理解DFT的重點。我們前面提到離散非周期序列的傅里葉變換(DTFT)在頻域上是連續的，這連續的頻域特徵機器是無法表達的，因此我們需要對它進行採樣。又由於頻域上具有周期性，只需要對2pi長度的區間採樣即可。那麼應該采多少個點呢？類似於Nyquist採樣定理的做法，我們得出採樣的點數M≥N即可(N表示該序列的長度)，為了方便起見只需取M=N。由此，DFT的兩個引入動機就清楚了:它是對無限長序列截斷成有限長序列，進行DTFT以後再在頻域採樣。

那麼為何DFT的形式和離散時間周期信號的傅里葉變換形式類似呢？注意到，有限長序列經過周期延拓即可變為周期信號，因此他們之間的相似性也不言而喻了。不過需要注意的是DFT對有限長序列均可以用，但離散時間周期信號的傅里葉變換隻能處理周期信號，這是本質的不同。

DFT可以這樣推導：
1.標準正交基
向量空間 $V$ （ $mathbb{R}^N$ 或 $mathbb{C}^N$ ）的標準正交基 $left{b_k ight}_{k=0}^{N-1}$ 滿足以下兩個條件：
$left<b_k,b_l ight>=0,k<br /> e l$
$|b_k|_2=1$
我們可以得到一個 $N imes N$ 的標準正交基矩陣：
$mathbf{B}=left[b_0|b_1|cdots|b_{N-1} ight]$
再把每一個標準正交基對應的係數 $alpha_k$ 寫成一個列向量：
$a=left[egin{array}{c} alpha_0 \ alpha_1 \ vdots \ alpha_{N-1} end{array} ight]$
則信號 $x$ 的標準正交基表示：
$x=alpha_0b_0+alpha_1b_1+cdots+alpha_{N-1}b_{N-1}=sum_{k=0}^{N-1}{alpha_kb_k} =left[b_0|b_1|cdots|b_{N-1} ight]left[egin{array}{c} alpha_0 \ alpha_1 \ vdots \ alpha_{N-1} end{array} ight]=mathbf{B}a$
那麼 $a=mathbf{B}^{-1}x=mathbf{B}^{H}x$ （這裡， $mathbf{B}^H$ 是指 $mathbf{B}$ 的共軛轉置矩陣，不難證明 $mathbf{B}^{-1}=mathbf{B}^H$ ）

關鍵結論：
對於一組標準正交基 $left{b_k ight}_{k=0}^{N-1}$ 和標準正交基矩陣 $mathbf{B}$ ，對於任意的信號 $x$ ，我們有以下的表達：

綜合式： $x=mathbf{B}a=sum_{k=0}^{N-1}{alpha_kb_k}$

分析式： $a=mathbf{B}^Hx$ 或 $alpha_k=left<x, b_k ight>$

綜合式表明信號 $x$ 可以表示成標準正交基的線性組合。
分析式給出了計算標準正交基對應係數 $alpha_k$ 的方法， $alpha_k$ 的大小表徵了信號 $x$ 與標準正交基向量 $b_k$
之間的相似度。

2.特徵向量與特徵值
結論：LTI系統的特徵向量是復正弦諧波（證明略）：
$s_kleft[n ight]=frac{e^{j{frac{2pi}{N}kn}}}{sqrt[]{N}},0le n,kle N-1$
可以看出復正弦諧波是一組標準正交基。

3.標準化的DFT（Normalized DFT）
對於標準正交基 $left{s_k ight}_{k=0}^{N-1}$ 和標準正交基矩陣 $mathbf{S}$ ，我們定義長度為 $N$ 的有限長信號 $x$ 的標準化DFT為：
綜合式(IDFT)： $x=mathbf{S}X$

$xleft[n ight]=sum_{k=0}^{N-1}{Xleft[k ight]frac{e^{j{frac{2pi}{N}kn}}}{sqrt[]{N}}}$

分析式(DFT)： $X=mathbf{S}^Hx$

$Xleft[k ight]=left<x,s_k ight>=sum_{n=0}^{N-1}{xleft[n<br /> ight]frac{e^{-j{frac{2pi}{N}kn}}}{sqrt[]{N}}}$
通過標準正交基得到的DFT一種表達，也是比較容易被人理解的一種形式。但這並不是我們通常能夠見到的DFT表達。

4.未標準化的DFT（Unnormalized DFT）
未標準化的DFT是通過正交基而非標準正交基得到的一種DFT表達，這也是我們常見的一種形式。這種形式可以避免計算上的複雜性，對於計算機來說，這是一種比較優雅的形式。由於傳統，在書本、文獻中一般統一採用這種DFT表達。
綜合式(IDFT)：

$xleft[n ight]=frac{1}{N}sum_{k=0}^{N-1}{X_uleft[k ight]e^{j{frac{2pi}{N}kn}}}$

分析式(DFT)：

$X_uleft[k ight]=sum_{n=0}^{N-1}{xleft[n ight]e^{-j{frac{2pi}{N}}kn}}$

簡單來說，DFT就是有限長信號的一種基變換，以復正弦諧波作為變換域的基是因為復正弦諧波是LTI系統的特徵函數。這樣，對於有限長信號，DFT就很自然成為分析LTI系統的工具了。
我的理解就是這樣了，好像也不是很通俗。

不妨試著從不太嚴謹的線性代數的角度來理解離散傅里葉變換。

1)
首先理解一個線性代數里最簡單的概念：正交基。考慮如下的向量表達式：

$[left( {egin{array}{*{20}{c}} {23}\ { - 11}\ 6 end{array}} ight) = 6 cdot left( {egin{array}{*{20}{c}} 0\ 0\ 1 end{array}} ight) + left( { - 11} ight) cdot left( {egin{array}{*{20}{c}} 0\ 1\ 0 end{array}} ight) + 23 cdot left( {egin{array}{*{20}{c}} 1\ 0\ 0 end{array}} ight)]$

一個簡單的向量被分解成了3個向量的線性和。特別的，在這個例子中，注意到，分解開的三個向量兩兩之間互相的內積等於零，於是這三個向量就是一組簡單的正交基。至於正交和內積為零，不妨這麼理解，內積指的是兩個向量互相之間的投影乘上個向量模那麼大小的係數，如果內積為零，意思是互相之間沒有投影，具體到上面例子就是想像一個三維空間中，三個坐標軸是互相垂直。具體到上面的例子，每個正交基向量前的係數正是原始向量在每個向量方向上的投影。

那麼正交基是不是唯一的呢，並不是，比如下面的表達式：

$[left( {egin{array}{*{20}{c}} {23}\ { - 11}\ 6 end{array}} ight) = 7 cdot left( {egin{array}{*{20}{c}} {frac{2}{7}}\ {frac{3}{7}}\ {frac{6}{7}} end{array}} ight) + 14 cdot left( {egin{array}{*{20}{c}} {frac{6}{7}}\ {frac{2}{7}}\ { - frac{3}{7}} end{array}} ight) + 21 cdot left( {egin{array}{*{20}{c}} {frac{3}{7}}\ { - frac{6}{7}}\ {frac{2}{7}} end{array}} ight)]$

一般來說，一個向量都可以表達成如下的形式：

$v=a_{1}v_{1}+a_{2}v_{2}+...+a_{k}v_{k}$

其中 $v in R^{k}, (v_{1}, v_{2}, ..., v_{k})$ 是一組正交基。

2)
理解了正交基之後，我們試著做下面一件事，求正交基向量對應的係數，還是以第一個表達式為例：

$[left( {egin{array}{{c}} {23}\ { - 11}\ 6 end{array}} ight) = a cdot left( {egin{array}{*{20}{c}} 0\ 0\ 1 end{array}} ight) + b cdot left( {egin{array}{{c}} 0\ 1\ 0 end{array}} ight) + c cdot left( {egin{array}{*{20}{c}} 1\ 0\ 0 end{array}} ight)]$

比如我們想求b的值是多少，回憶前面說的係數就是投影乘以向量的模，也就是內積，於是求係數就變得非常簡單：

$[b=leftlangle left( egin{matrix} 23 \ -11 \ 6 \ end{matrix} ight),left( egin{matrix} 0 \ 1 \ 0 \ end{matrix} ight) ight angle =23 imes 0+left( -11 ight) imes 1+6 imes 0=-11]$

對第二個表達式也可以做類似的事情：

$[leftlangle left( egin{matrix} 23 \ -11 \ 6 \ end{matrix} ight),left( egin{matrix} frac{6}{7} \ frac{2}{7} \ -frac{3}{7} \ end{matrix} ight) ight angle =23 imes frac{6}{7}+left( -11 ight) imes frac{2}{7}+6 imes left( -frac{3}{7} ight)=frac{138}{7}-frac{22}{7}-frac{18}{7}=14]$

3)
回到1)中的公式：

$v=a_{1}v_{1}+a_{2}v_{2}+...+a_{k}v_{k}$

如果我們想像一段離散地、有限的時間信號，假設採樣點有k個，我們不妨把這段時間信號看做是一個大小為k的向量，於是這段時間信號應該也可以用如上的表達式表達出來，其中v(t)就是在第t個時間點(第t維)的值，於是有如下：

$v(t)=a_{1}v_{1}(t)+a_{2}v_{2}(t)+...+a_{k}v_{k}(t)$

再做點簡單修改，設想有個向量

$[f=v+frac{1}{2}{{a}_{0}}left( egin{matrix} 1 \ vdots \ 1 \ end{matrix} ight)]$

其中 $f, v in R^{2k}$ ，那麼f(t)可以表達如下

$f(t)=frac{1}{2}a_{0}+a_{1}v_{1}(t)+a_{2}v_{2}(t)+...+a_{k}v_{k}(t)+b_{1}w_{1}(t)+b_{2}w_{2}(t)+...+b_{k}w_{k}(t)$

有沒有覺得很眼熟？把 $v_{n}(t)$ 換成cos(nx)， $w_{n}(t)$ 換成sin(nx)，也就是在頻域按頻率的分解，得到如下(為什麼是正交基就略過不展開了…)：

$f(t)=frac{1}{2}a_{0}+ sum_{n=1}^k a_{n}cos(nt) + sum_{n=1}^k b_{n}sin(nt)$

很不嚴謹地推廣到 $k ightarrow infty$ ，得到如下：

$f(t)=frac{1}{2}a_{0}+ sum_{n=1}^{infty} a_{n}cos(nt) + sum_{n=1}^{infty} b_{n}sin(nt)$

這正是傅里葉級數，其實正交基是信號相關理論中包含傅里葉級數在內的各種奇怪展開的基礎。至於為什麼每一項前的係數的計算方法是信號本身和基的積分由2)中關於點積的解釋也就很明白了。

明白了以上，從傅里葉級數到傅里葉變換，復振幅的表示的推廣在此就略過吧。

傅里葉變換是將函數的時域（紅色）與頻域（藍色）相關聯。
頻譜中的不同成分頻率在頻域中以峰值形式表示

①時域的原函數f

②傅里葉變換 $f=a_{0}+sum_{n=1}^{infty} a_{n} cos(nx)+b_{n} sin(nx)$

③ $f_{i} =a_{i} cos(ix)+b_{i} sin(ix)$

④ $ar{f_{i} } =amplitude of f_{i}$

⑤時域f與頻域 $ar{f}$ 對應

參考：
維基百科，自由的百科全書傅里葉變換

　本書以輕鬆有趣、通俗易懂的漫畫及故事的方式將抽象、複雜的傅里葉知識融會其中，讓人們在看故事的過程中就能完成對數學相關知識的「掃盲」。這是一本實用性很強的圖書，與我們傳統的教科書比較起來，具有幾大突出的特點，一漫畫的形式更易於讓人接受，二邊讀故事邊學知識，輕鬆且易於記憶，三更能讓讀者明白並記住傅里葉解析問題在現實生活中的應用。
　　
本書既可以作為人們日常生活中了解數學知識的讀本，也可以作為數學及相關專業學生的參考用書，更可以是文科專業學生理性認識和學習數學知識的工具書及相關專業的參考用書。

電驢地址《漫畫傅里葉解析》掃描版[PDF]

百度地址：[漫畫傅里葉解析].涉穀道雄.掃描版.pdf_免費高速下載

樓主問的是，什麼是離散傅里葉變換，怎麼都在講傅里葉變換。

其實如果理解什麼是連續傅里葉變換的話，從連續退到離散還是很容易的事情。但是我們不妨先回答一下，什麼是連續，什麼是離散？
我們從小到大學習的數學，一般來說，是從離散推廣到連續的，我們先學的1、2、3、4這些自然數就是『離散』，而後面的小數就把我們從這一個個孤立的點連接成了一條完整的數軸，這就是連續。
說了這麼多，大家肯定覺得，這些簡單的東西大家都明白啊，是的，所以這個時候我們要拋出另一個問題，離散和連續是絕對的嗎？這個問題很深奧，作為窮苦學生黨我也不能進行深入闡釋。但是我的理解下能夠說的就是，傅里葉變化，就是在離散和連續，時域和頻域里來回穿行，從無限到有限，在數學上讓很多很難計算為問題大大簡化。很多的傅里葉變換鑽了這樣一個空子：時域上連續的很多東西，在頻域上是離散的。
這個時候就要祭出維基百科上那張經典的圖了：https://en.wikipedia.org/wiki/File:Fourier_series_and_transform.gif

一個時間坐標軸上面連續的函數，分解成頻率不同的正弦函數，把這些正弦函數往後拖，從側面也就是頻域上看過去，可以看到得到的圖像是離散的！
這個時候我們在進一步，時域分解得到的正弦函數的頻率ω1，ω2，ω3們，我們取他們的最大公約數，（這個地方說最大公約數似乎有些不合適，就是表示選取的數能把ω1們整除）然後把它命名為ω0，它就是我們給這個頻域圖像選取的『基』，通俗地講就是所謂的「單位一」，有了這個基，我們就可以吧頻域上的刻度寫成1,2,3,4······
但是如果有些時候我們分解的正弦函數越來越複雜，使得得到的這個ω0越來越小，直觀的視覺效果就是在頻域坐標上我們看到的刻度密度越來越密，越來越密，最後，我們就從離散一股腦扎進了連續。
同樣的道理，頻域上連續的東西，到了時域上用同樣的分析方法，也可能是離散的。這裡面就像很多漫威DC的電影電視劇裡面常用的一個平行宇宙的假設一樣，想想有一個世界，和我們佔有同一條時間線，但是我們兩個世界卻佔有者不同的頻率段，所以我們這兩個世界在頻域上是離散而不相交的。。。。
個人的一點小觀點，請多指教/(ㄒoㄒ)/~~

離散信號的DTFT（離散時間傅里葉變換）在頻域上是連續且周期性的，omega的周期為2pi，但是連續信號在機器中並不好儲存，DFT（離散傅里葉變換）最好理解的方法就是當作它是在頻域上對DTFT的採樣，每隔2pi/N的頻率採樣一次，這樣把連續的頻率變成了離散的頻率。

但是在寫法上和DTFT有所不同，一般情況下分析DTFT的時候都會選取-pi~pi這個區間進行畫圖和分析，但是在DFT上我們應該選取0&<=k&<=N-1的區間，對應的頻率也就是0~2pi這個區間。因為DTFT是周期性而且周期是2pi，所以-pi~0這個區間其實就是pi~2pi這個區間。

不覺得沒有一個人真正回答了問題嗎？我最近做項目卡在這了，關鍵是那個離散傅里葉變化的公式啊！。。。怎麼跟連續時的公式對應起來呢？如果能對應起來我就直接拿連續情形下的公式編代碼了！不就是個積分嗎？！可是那個奇葩離散公式看不懂，不敢編啊！求解答離散傅里葉變換的公式！！

如果看了此文你還不懂傅里葉變換，那就過來掐死我吧【完整版】

傅里葉變換中有一個離散傅里葉變換是現代數字系統經常用的變換，甚至比連續傅里葉變換的應用場合還要多，畢竟我們目前處在一個數字化的世界中，那麼離散傅里葉變換要怎樣理解呢？就像題目所說的：離散傅里葉變換本質是周期信號求傅里葉級數！

具體來看，

有了以上推導，我們便可以將離散傅里葉變換用周期信號求傅里葉級數來統一起來了。在實際應用中，我們可以取一段時間的離散函數點x(n)，然後將其進行周期性延拓，從而可以利用離散傅里葉變換，得到X(k)，當然頻域周期性延拓得到周期信號。

從另一個角度說，我們知道針對傅里葉變換，時域周期，頻域肯定是離散的，同理，頻域周期，時域對應離散。而離散傅里葉變換中，時域和頻域均為離散，那麼時域和頻域肯定是周期信號。和離散傅里葉變換是相符合的。

一個問題從多個角度理解都能得到統一結論，如果我們學習一個知識，善於總結，將所學到的知識觸類旁通，每個人都能建立自己的知識庫，這也是學習的有效方法。

如果覺得對你有用，請給予支持！

根據尺度變換，假如頻域集中，則時域將無限分布，而shannon採樣定理表示對具有一定帶寬的信號，在時域將進行無限次採樣，並用sinc函數內插，才能恢復到原來的信號，這裡對採樣函數的頻率和sinc函數有所要求。對於連續信號，假設對時域和頻域都設定一段長度，先對時域採樣得到一系列離散點，再進行連續傅立葉變換，可知該傅立葉變換函數仍然為連續頻率密度函數，對頻域再次進行採樣得到頻域的離散點，這些點的黎曼和表示該信號的離散傅立葉變換。提出原信號的離散點向量，則得到離散傅立葉變換n的平方階矩陣，n表示採樣點的個數，這是一個對角正交矩陣，分解成幾個矩陣相乘，不斷遞歸，最終達到減少計算次數的目的，也就是fft的核心思想。上面提到的一個信號在時域和頻域上都有一定帶寬，這不可能存在，所以對應的離散傅立葉變換會存在誤差。

首次回答，純手打。

只要定義了一個空間上的測度，就可以有可測函數，就可以有積分，就可以有傅里葉變換。而離散傅里葉變換就是數列組成的空間上的傅里葉變換，測度是計數測度。
提一個不那麼靠譜的建議，數學好的可以去看看調和分析，我想可能會對這些東西理解得比較深刻(不過你需要學實分析，泛函分析，時間成本比較高)。

可以看成是把一個時域連續信號經過DAC進行採樣，得到的sample經過傅立葉變換變成頻域sample。簡單的說，DFT可以看成是FFT工程上的實現方式。。

現在知乎上很多人都是拿最基本的東西說的天花亂墜，然後故作高深，唉，不解決問題啊，你說一堆最基本的線性代數知識有什麼用呢？況且離散傅里葉變換矩陣並不是酉矩陣！！！ $F^{-1} = frac{1}{n} ext{conj}(F), ext{if} F in Re^{n imes n}$

可以看成，不同的一組頻率點上的帶通矩形濾波器組，這是我認為最通俗的解釋。