離散時間信號的FFT 演算法及晶片化
【視頻】How to find 8 point DFT using Direct method
●Twiddle Factor 旋轉因子
旋轉因子 W 描述了一個“旋轉向量”，它根據樣本數量 N 遞增旋轉。
下圖是 N = 2、4 和 8 個樣本的圖示。
例如，W 的N=4 時，則n = 2 與n=6 與n=10、… 都相同。
W 的 N=8 時，則n = 3 與n=11與n=19、 …都相同。
【視頻】 Find 6 point DFT using matrix method
█FFT (Fast Fourier Transform)快速傅立葉變換
為快速計算DFT, 通常採用蝶形演算法(Butterfly Algorithm)
它可簡少運算次數,因此可快速求解
●BF (Butterfly) 碟形
●Stage 及Radix
●FFT 轉換有DIT FFT 與 DIF FFT 兩種方式
分時FFT（Decimation-in-time FFT）: DFT式中的序列在時域上的蝶形演算
分頻FFT（Decimation-in-frequency FFT）: DFT式中的序列在頻域上的蝶形
演算
【視頻】FFT 碟形演算法原理推導
【視頻】8-point FFT 蝶形計算示範
●FFT 計算降冪效率
■ FFT 計算晶片化的演算法
●BF 蝶形計算: Complex Butterfly calculation
【例】 Radix-2 FFT 蝶形單元概述和 8-bin Radix-2 FFT 示例
●複數乘法器（CM）
●常數乘法器的移位加法
常數乘法器的設計, 例如乘以常數 0.7071 可以表示為
■N-Point FFT 方塊圖
●8-Point FFT 方塊圖
●256-Point FFT方塊圖
對於較大的N，將N點 FFT 分解為更小的V -FFT 更為有效，其中 256 點 FFT 被分解為 16 點 FFT，因此， X(k)中的計算可以計算為
●N-Point 的Reconfigurable FFT 方塊圖
參考 :
■FFT 的 FPGA IP 方案
FFT IP Cores，基於串行處理，一般只有一個Radix-4（或Radix-2）節點，每一個旋轉因子都會重複使用這樣一個節點，以克服邏輯面積消耗的缺點；當今市場上可用的此類 FFT IP 核的示例如圖
●Twiddel Factor 為10bit的Xilinx Spartan-6 FPGA
【視頻】FFT design using MATLAB-VIVADO
【視頻】DFT with FFT Algorithm using TMS320C67XX DSP Processor
參考資料:
1. 離散傅立葉變換DFT
2. 離散傅立葉變換矩陣
https://zh.wikipedia.org/wiki/離散傅立葉變換矩陣
3. Discrete Fourier Transform (離散傅立葉轉換)
4. 從傅立葉級數到快速傅立葉轉換
5.台灣國立交通大學 林毅慧 碩士論文
分享至
成為作者繼續創作的動力吧！
