Understanding Discrete Fourier Transform (DFT)
discrete Fourier transform (DFT)是一個能夠解析訊號的頻率成分 (frequency components)的演算法， 也就是大家常說的時域訊號轉頻譜 (spectrum)。在說明DFT怎麼做到 這件事之前，我們先來談訊號間的相似性 (similarity)。
Similarity
當你在照鏡子的時候，你會說鏡中的人跟你的相似性很高，因為你往左他就往左，你往右他 就往右。我們也可以給予訊號一樣的解釋，當兩個訊號的變化很同步的時候，我們就可以說它們 的相似性很高。
或許你曾經看過以下這個數學式:
`similarity = \sum_{n=0}^{N-1} x(n)y(n)`
這個式子告訴我們，假如x跟y的相似性很高，那麼當x(n)是正數的時候y(n)就會是正數， 而當x(n)是負數的時候y(n)也會是負數，此時把x(n)乘上y(n)我們會得到一個正數。反之， 如果x跟y的相似性很低，那麼當x(n)是正數的時候y(n)就會是負數，而當x(n)是負數的時候y(n) 反而變成是正數，此時把x(n)乘上y(n)會得到一個負數。
Discrete Fourier Transform
相似性跟DFT怎麼扯上關係呢? 讓我們來看看DFT的公式
`X(k) = \sum_{n=0}^{N-1} x(n)e^{-2\pikn/N}`
又是exponential又是虛數的看起來很複雜，我們先把後面那陀`e^{-2\pikn/N}`用y(n)來表示
`X(k) = \sum_{n=0}^{N-1} x(n)y(n)`
喔喔，這不就恰好是前面所講的similarity的數學式嗎! 原來DFT是在算x(n)跟`e^{-2\pikn/N}` 之間的相似性啊。那那那，`e^{-2\pikn/N}`又是什麼東西呢?
數學上，我們可以把exponential拆解成sin跟cos的組合
`e^{-i\theta}=cos\theta-isin\theta`
如果讓 `\theta=2\pikn/N`，那我們就可以得到
`e^{-2\pikn/N}=cos(2\pikn/N)-isin(2\pikn/N)`
現在我們可以把DFT的公式做個改寫
`X(k) = \sum_{n=0}^{N-1} x(n)e^{-2\pikn/N}`
`\qquad\qquad = \sum_{n=0}^{N-1} x(n)[cos(2\pikn/N)-isin(2\pikn/N)]`
`\qquad\qquad = \sum_{n=0}^{N-1} x(n)cos(2\pikn/N) - i\sum_{n=0}^{N-1} x(n)sin(2\pikn/N)`
實數跟複數，河水不犯井水，讓我們專心解析實數的部分
`X(0) = \sum_{n=0}^{N-1} x(n)cos(2\pi\*0\*n/N)`
`X(1) = \sum_{n=0}^{N-1} x(n)cos(2\pi\*1\*n/N)`
`\*\*\*`
`X(k) = \sum_{n=0}^{N-1} x(n)cos(2\pi\*k\*n/N)`
現在所謂頻率成分在我們的眼中看來就是在計算x(n)跟各種的cos週期波之間的相似性。 我們來看看不同的k值的cos會怎麼變化，將k試著代入不同的值，我們可以發現，k越大， 頻率越快
Great! DFT現在可以看成是在計算x(n)跟各種頻率的cos週期波之間的相似性。 如果想把k值轉換到真實頻率的話，我們就需要知道x的取樣頻率，轉換公式如下:
`f=(k\*fs)/N`
fs是取樣頻率，N則是取樣點的個數。現在我們知道了DFT的背後的原理是什麼了， 接下來我們實際用Matlab做一組訊號來試看看DFT， 訊號由5Hz跟12Hz兩個頻率所組成並帶有一些雜訊，其中12Hz的震幅要大於5Hz。
看起來很不錯，在5Hz跟12Hz的頻率成分都成功地解析出來，而且還分辨得出12Hz的訊號要強於5Hz。