【導(dǎo)讀】介紹DFT的運(yùn)算特點,再具體討論高效算法。FIRDF的實現(xiàn)、線性卷積等。一個重要的原因是DFT有。nx有限長序列的DFT為。次復(fù)乘,有總的計算量有次復(fù)加。當(dāng)N較大時,所需的運(yùn)算量是很大的。如果要求實時處理,對運(yùn)算速度的要求將是十分苛刻的。N例如,當(dāng),則。這么大量的復(fù)乘對運(yùn)算時間的要求就很高。特點及減少運(yùn)算量,提高運(yùn)算效率的方法。所以,每一次復(fù)乘實際是作了四次實乘,兩次實加。在定義時我們強(qiáng)調(diào)其隱含周期性,實質(zhì)是系。nkNW此外,除了具有周期性外,還具有對稱性。由以上推倒看到,利用周期性使原有7個系數(shù),兩個系數(shù),不難想象4點的DFT可以利用兩點DFT實現(xiàn)。事實正是如此,1965年,庫利-圖基首次提。逐次分解為較短序列的DFT運(yùn)算。次分解時間序列得到的,所以叫時間抽取法。因為N是2的M次方,所以稱“基2”。