1 離散傅里葉變換(DFT)的推導
時域抽樣：

 

目的：解決信號的離散化問題。

效果：連續(xù)信號離散化使得信號的頻譜被周期延拓。

時域截斷：

原因：工程上無法處理時間無限信號。

方法：通過窗函數(shù)(一般用矩形窗)對信號進行逐段截取。

結(jié)果：時域乘以矩形脈沖信號，頻域相當于和抽樣函數(shù)卷積。

時域周期延拓：

目的：要使頻率離散，就要使時域變成周期信號。

方法：周期延拓中的搬移通過與 的卷積來實現(xiàn)。

表示：延拓后的波形在數(shù)學上可表示為原始波形與沖激串序列的卷積。

結(jié)果：周期延拓后的周期函數(shù)具有離散譜。

經(jīng)抽樣、截斷和延拓后，信號時域和頻域都是離散、周期的。過程見圖1。

 

 

處理后信號的連續(xù)時間傅里葉變換：
是離散函數(shù)，僅在離散頻率點 處存在沖激，強度為 ，其余各點為0。

是周期函數(shù)，周期為 ，每個周期內(nèi)有 個不同的幅值。

時域的離散時間間隔(或周期)與頻域的周期(或離散間隔)互為倒數(shù)。

2 DFT及IDFT的定義
DFT定義：設 是連續(xù)函數(shù) 的 個抽樣值 ，這N個點的寬度為N的DFT為：
IDFT定義：設 是連續(xù)頻率函數(shù) 的 個抽樣值 ， 這N個點的寬度為N的IDFT為：

稱為N點DFT的變換核函數(shù)， 稱為N點IDFT的變換核函數(shù)。它們互為共軛。

同樣的信號，寬度不同的DFT會有不同的結(jié)果。DFT正逆變換的對應關系是唯一的，或者說它們是互逆的。

引入
用途：

正逆變換的核函數(shù)分別可以表示為 和 。

 

核函數(shù)的正交性可以表示為：

DFT可以表示為：
IDFT可以表示為：
性質(zhì)：周期性和對稱性：

 

 

 

3 離散譜的性質(zhì)
離散譜定義：稱 為離散序列 的DFT離散譜，簡稱離散譜。

性質(zhì)：

周期性：序列的N點的DFT離散譜是周期為N的序列。

共扼對稱性：如果 為實序列，則其N點的DFT關于原點和N/2都具有共軛對稱性。即 ； ；
幅度對稱性：如果 為實序列，則其N點的DFT關于原點和N/2都具有幅度對稱性。即 ； ；
改寫：

簡記 為
簡記 為
DFT對簡記為： 或

4 DFT總結(jié)
DFT的定義是針對任意的離散序列 中的有限個離散抽樣 的，它并不要求該序列具有周期性。

由DFT求出的離散譜 是離散的周期函數(shù)，周期為 、離散間隔為 。離散譜關于變元k的周期為N。

如果稱離散譜經(jīng)過IDFT所得到的序列為重建信號， ，則重建信號是離散的周期函數(shù)，周期為 (對應離散譜的離散間隔的倒數(shù))、離散間隔為 (對應離散譜周期的倒數(shù))。

經(jīng)IDFT重建信號的基頻就是頻域的離散間隔，或時域周期的倒數(shù)，為 。

實序列的離散譜關于原點和 (如果N是偶數(shù))是共軛對稱和幅度對稱的。因此，真正有用的頻譜信息可以從0~ 范圍獲得，從低頻到高頻。

在時域和頻域 范圍內(nèi)的N點分別是各自的主值區(qū)間或主值周期。

 

5 DFT性質(zhì)
線性性：對任意常數(shù) ( )，有
奇偶虛實性：

DFT的反褶、平移：先把有限長序列周期延拓，再作相應反褶或平移，最后取主值區(qū)間的序列作為最終結(jié)果。

DFT有如下的奇偶虛實特性：

奇 奇；偶 偶；實偶 實偶；實奇 虛奇；

實 (實偶) + j(實奇)；實 (實偶)·EXP(實奇)。

反褶和共軛性：

時域
頻域

反褶
反褶

共軛
共軛＋反褶

共軛＋反褶
共軛

對偶性：
把離散譜序列當成時域序列進行DFT，結(jié)果是原時域序列反褶的N倍；

如果原序列具有偶對稱性，則DFT結(jié)果是原時域序列的N倍。

時移性： 。序列的時移不影響DFT離散譜的幅度。

頻移性：
時域離散圓卷積定理：
圓卷積：周期均為N的序列 與 之間的圓卷積為

仍是n的序列，周期為N。

非周期序列之間只可能存在線卷積，不存在圓卷積；周期序列之間存在圓卷積，但不存在線卷積。

頻域離散圓卷積定理：
時域離散圓相關定理：
周期為N的序列 和 的圓相關：
是n的序列，周期為N。

。其中 表示按k進行DFT運算。

帕斯瓦爾定理：
6 快速傅里葉變換FFT
(1) FFT不是一種新的變換，而是DFT的快速算法。

(2) 直接DFT計算的復雜度：
計算DFT需要： 次復數(shù)乘法； 次復數(shù)加法。

(3) FFT算法推導：

(i) 第L次迭代中對偶結(jié)點值的計算公式為：

， 是循環(huán)控制變量。

整序：經(jīng)過r次迭代后，得到結(jié)果 ，實際結(jié)果應是 ，所以流程的最后一步是按下標的正常二進制順序?qū)Y(jié)果進行整序。

(4) FFT算法特點：( )

(i) 共需 次迭代；

(ii) 第 次迭代對偶結(jié)點的偶距為 ，因此一組結(jié)點覆蓋的序號個數(shù)是 。

(iii) 第 次迭代結(jié)點的組數(shù)為 。

(iv) 可以預先計算好，而且 的變化范圍是 。

(5) FFT算法流程：( )

(i) 初始化： ；

(ii) 第 次迭代：

(a) 下標控制變量初始化 ；

(b) “結(jié)點對”的個數(shù)初始化 ;

(c)
Ø 按對偶結(jié)點對的計算公式進行置位運算，得到 和 的值；

Ø ； ；

Ø 跳過已經(jīng)計算過的結(jié)點(即上面 所對應的那些結(jié)點)： ；

Ø 如果 ，轉(zhuǎn)到b)繼續(xù)計算下一組結(jié)點；否則結(jié)束本次迭代。

(iii) 當 次迭代全部完成后，對結(jié)果 按下標二進制位進行整序，從而得到結(jié)果