Man and History: Discrete Fourier Transform

Discrete Fourier Transform

2022/03/15

-----

https://pixabay.com/zh/photos/nature-landscape-lava-lava-pit-3348406/

-----

◎ 說明：

-----

Fig. 1. Discrete Fourier Transform 數學公式 [12]。

-----

Q1：離散傅立葉變換公式中的除法是什麼意思？

A1：參考圖一的公式一。

一般除法的意思就是幾倍。比方說，六除以二等於三，六就是二的三倍。那麼在傅立葉變換的公式裡面，它的除法是什麼意思呢？也是幾倍的意思。

我們先看一下圖一下方的矩陣乘法，也就是公式三，它把一個取樣後的訊號，透過傅立葉矩陣，變成了一連串的頻率，裡面的值是振幅。這是什麼意思呢？其實就是把原始訊號除以不同頻率的波，看看它是每一個波的幾倍。

等等，矩陣乘法怎麼又變成除法呢？我們可以回過頭看一下公式一。原本的除法，是除以一個逆時針旋轉的波，這是等價於乘以原來的波（但是由逆時針改成順時針），數學符號不同，物理意義是一樣的。

如果這樣還是不大能理解，那可以把圖一下方的傅立葉矩陣換成《DFT Matrix》的圖三 [13]，應該就比較容易懂了。那張圖就是把要分析的訊號除以不同頻率的弦波。

如果你對於「波」不是很瞭解，那可以先看一下《Wave - 演算法筆記》[12]。

-----

Q2：離散傅立葉變換與離散傅立葉逆變換有何不同？

A2：我們剛剛在問題一中提到的離散傅立葉變換是波的分解，逆變換其實就是波的合成。乘法在這邊就是很直觀的使用了。與其用很多文字解釋公式，不如看一下《Discrete Fourier Transform in Python》的圖二 [14]，你就知道公式三跟公式四在做什麼事了。

-----

Q3：離散傅立葉變換矩陣是什麼？

A3：

-----

Q4：離散傅立葉變換公式中的 N 分之一是什麼意思？

A4：

-----

Fig. 2. Discrete Fourier Series [3].

-----

Fig. 3. Discrete Fourier Transform [3].

-----

◎ 參考資料：

-----

1. 傅立葉矩陣與逆矩陣

「F4 的列向量的模長是 2，為了使矩陣更完美，可以把它除以 2，於是矩陣的各列就變成了標準正交向量。對於標準正交的實矩陣來說，矩陣的逆等於矩陣的轉置，傅立葉矩陣可化簡為標準正交的複矩陣，具有同樣的性質，F4 的逆矩陣就是它共軛的轉置。由於 F4 的逆矩陣就是 F4 共軛的轉置，所以 F4 的逆矩陣和 F4 具有同樣的性質。」[6]。

-----

2. 模長

「直觀上，向量通常被標示為一個帶箭頭的有向線段。線段的長度表示向量的大小（或稱模長），向量的方向即箭頭所指的方向。」[7]。

-----

3. 正交

[8]。

-----

4. 標準正交

[9]。

-----

5. 共軛轉置

[10]。

-----

6. 歸一化因子（1/N) ^ (1/2）

「The normalization factor multiplying the DFT and IDFT (here 1 and 1/N and the signs of the exponents are merely conventions, and differ in some treatments. The only requirements of these conventions are that the DFT and IDFT have opposite-sign exponents and that the product of their normalization factors be 1/N. A normalization of (1/N)^(1/2) for both the DFT and IDFT, for instance, makes the transforms unitary.」[1]。

翻譯：

「乘以 DFT 和 IDFT 的歸一化因子（這裡 1 和 1/N 以及指數的符號只是約定，在某些處理上有所不同。這些約定的唯一要求是 DFT 和 IDFT 具有相反符號的指數和它們的歸一化因子的乘積為 1/N。例如，對於 DFT 和 IDFT 的 (1/N) ^ (1/2) 歸一化可以使變換成為么正變換。」

# DFT 和 IDFT 具有相反符號的指數

# DFT 和 IDFT的歸一化因子的乘積為 1/N

-----

7. Unitary Transformation（么正變換）

[10]。

-----

8. 加速

「為了加快計算速度，正向傅立葉轉換經常改成不除以 √N ，逆向傅立葉轉換經常改成多除以 √N 。」[11]。

-----

References

[1] Discrete Fourier transform - Wikipedia

https://en.wikipedia.org/wiki/Discrete_Fourier_transform