離散信號的傅立葉各式轉換:DFT、IDFT、FFT(Fast DFT)

■信號的各種傅立葉變換分析

■離散傅立葉轉換 Discrete Fourier Transform (DFT)與逆離散傅立葉轉換

Inverse Fourier Transform (IDFT)

【視頻】Introduction to the DT Fourier Transform

■ DFT 矩陣表示法

DFT 可用矩陣的方式表示

逆離散傅立葉轉換 IDFT 的矩陣表示為

逆傅立葉轉換則是依逆時針方向旋轉。

【例】如取樣值N=4 ( 即Twiddle Factor=4)

■快速傅立葉轉換 Fast Discrete Fourier Transforms (Fast DFT)

FFT就是FDFT的簡稱

依據定義，DFT計算的時間複雜度N^2 ，FFT的複雜度是 Nlog2N。

（FFT是基數2的，就是说N必须是2的幂次）

實際使用時，N 值很大，導致 DFT 計算量龐大。

因此J. W. Cooley, John Turkey 修改 DFT 演算法，改用

divide-and-conquer 方法提出快速傅立葉轉換(FFT)。

且 FFT 可得到與 DFT 相同的結果

【視頻】最偉大的演算法之一，快速傅立葉轉換

【視頻】TI Precision Labs – ADCs: Fast Fourier Transforms (FFTs) and Windowing

【例】DFT 具有可逆性之舉例如下

【視頻】The FFT Algorithm - Simple Step by Step

■傅立葉（Joseph Fourier，1768 -1830）

https://www.tunghua.com.tw/portal_b10_cnt_page.php?button_num=b10&folder_id=696&cnt_id=8391