表總結了dft最重要的一些屬性。許多屬性與傅立葉變換一致，例如：變換是惟一（雙射）的、重疊的使用，以及實部與虛部通過hilbert變換聯系在一起。

　　表 dft 定 理

　　前向和反向變換的相似性產生了一種可選的反演算法。利用dft的向量／矩陣表示式：

　　也就是可以利用刻度為1／n的嚴的dft計算離散傅立葉反變換。

　　1．實序列的dft

　　現在來研究一下當輸入序列是實數時，一些dft（和fft）計算的額外簡化計算。在這種情況下，我們有兩種選擇：一種是可以用一個n點dft計算兩個n點序列的dft；另一種是可以用一個n點dft計算一個長度為2n的實序列的dft。

　　如果利用表給出的hilbert屬性，也就是實序列具有偶對稱的實頻譜和奇對稱的虛頻譜，就可以將下面的算法合成起來^[124]。

　　因此，除了一個n點dft（或fft）之外的計算量就是來自旋轉因子±exp（jπk/n）次實數加法和乘法。

　　為了用一個長度為n的dft變換兩個長度為n的序列，我們可以運用實序列具有一個偶頻譜而純虛序列的頻譜為奇數這一事實（請參閱表）。這也是下面算法的基礎。

　　因此，除了一個n點dft（或fft）之外的計算量就是為了構成正確的2個n點dft而進行的2n次實數乘法。

　　2．利用dft計算快速卷積

　　最常用到dft（或fft）的一個領域就是計算卷積。如同傅立葉變換一樣，時域內的卷積就是將兩個變換的序列相乘：兩個時間序列在頻域內變換，計算一個（標量）逐點乘積，再將結果返回到時域中。與傅立葉變換相比，主要的區別是dft計算了一個循環的而不是線性的卷積。這一點在用fft實現快速卷積的時候必須加以考慮。也就產生了兩種方法，分別是“重疊節約”和“重疊增加”。在重疊節約方法中，我們只需要簡單地放棄在邊界被循環卷積破壞的采樣即可。在重疊增加方法中，通過在公共乘積流上直接加上部分序列的方法在濾波器和信號中填充0。

　　對于快速卷積而言，最常見的輸入序列都是實序列。因此，有效卷積可以用實變換來實現。我們還可以為hartley變換構造一個類似fft的算法，與復變換^[130]相比較，可以將性能提高兩倍。

　　如果要利用可行的fft程序，我們需要使用前面討論過的實序列算法6．2或算法6．3。圖給出了一個與算法6．2相似的可選方法，該方法用—個n點dft來實現兩個n點變換，不過在這種情況下，實部用作dft，虛部用作idft，根據卷積理論，在反變換的時候需要用到虛部。

　　圖 采用復數fft的實數卷積[56]

　　假設實數值濾波器（也就是f［k］＝f［－k］*）的dft已經被離線計算過，那么在頻域內就只需要n／2次乘法來計算x［k］f［k］。

　　歡迎轉載，信息來源維庫電子市場網（www.dzsc.com）