目錄

• • 【1】回顧DIT
  • 【2】算法原理
  • 【3】運算特點

【1】回顧DIT

https://blog.csdn.net/qq_42604176/article/details/105559756

【2】算法原理

設序列點數：N=2^M,M為正整數。將輸入序列按照前一半、后一半分開。（并非按照奇偶分）

由于，所以化簡為：

按照k奇數偶數進行分類討論：

注意，此時X(2r)：前半輸入與后半輸入之和的N/2點DFT
X(2r+1)：前半輸入與后半輸入之差的與WN^n之積的N/2點DFT；
將括號內的式子寫作整體：

基本的蝶形運算單元：

以N=8為例，展示出1級，2級，3級分解層次：
1、第一次分解

2、第二次分解：

3、第三次分解：

由于N=2^M,N/2仍然為偶數，將N/2點DFT輸出再次分解，一直進行到第M次，第M次做兩點DFT。

【3】運算特點

1、通過(N/2)*M個蝶形運算完成。（N/2:行數的一半，M：列數，運算的級數）
都有這樣的迭代運算：


2、DIT與DIF方法異同點：
【1】：DIF：輸入自然序列，輸出倒位序列。
DIT：輸入倒位序列，輸出自然序列。
（本質上都是重新排序）
【2】：基本蝶形運算單元不同：
DIF:復數乘積只出現在減法運算之后
DIT:先做復數乘法運算，再做加減法
【3】：運算量相同
【4】：都需要進行變址運算，且轉換的方法是一樣的
【5】：DIT、DIF的基本蝶形互為轉置

轉置：流圖中所有支路方向都反向，并且交換輸入輸出。節點變量值不做變換。

—————————————————————————————————————————————————————————————
參考資料：

《數字信號處理第三版.劉順蘭版》

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的快速傅里叶变换（FFT）——按频率抽取DIF的基的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。