目錄
- 【1】回顧DIT
- 【2】算法原理
- 【3】運算特點
【1】回顧DIT
【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的基本蝶形互為轉置
轉置：流圖中所有支路方向都反向，并且交換輸入輸出。節點變量值不做變換。
—————————————————————————————————————————————————————————————
參考資料：