豆豉
[拼音]:N dian youxian changxulie de lisan Fuliy bianhuan
[英文]:discrete Fourier transformation of finite length sequences
時域N點序列χ(n)的離散傅立葉變換(DFT)以X(k)表示,定義為
(1)
式中K=0,1,…,N-1。式(1)稱為DFT的正變換。從式(1)可以匯出
(2)
式中n=0,1,…,N-1。式(2)稱為DFT的逆變換。式(1)和式(2)合起來稱為離散傅立葉變換對。
由於在科學技術工作中人們所得到的離散時間訊號大多是有限長的N點序列,所以對N點序列進行時域和頻域之間的變換是常用的變換,另外 DFT有它的快速演算法,使變換可以在很短的時間內完成,所以DFT是數字訊號處理中最為重要的工具之一。
DFT的原理
是以給定的時域N點序列χ(n)作為主值週期進行週期延拓(即使之週期化)得到以 N點為週期的離散週期序列χ((n))N,再求χ((n))N的離散傅立葉級數(DFS)表示(見離散時間週期序列的離散傅立葉級數表示),得頻域的N點離散週期序列X((k))N,最後從X((k))N中取出其主值週期,即得X(k)。同理,與此相似,如果已知X(k)求χ(n),則是從X(k)得X((k))N,再從X((k))N得χ((n))N,取出主值週期即得χ(n)。這個概念很重要,DFT的性質大都與此有關。至於從χ(n)求X(k),或已知X(k)求χ(n)則是用(1)式或(2)式直接進行的,並不需要通過χ((n))N和X((k))N。
DFT的主要性質
共有5點,如下表中所列。表中a、b為常數, χ((m))N為以N點為週期的週期序列,χ((n+m))N為χ((n))N序列整體左移m點後的結果
其他符號如X((k+l))N,X((l))N,Y((k-l))N及y((n-m))N等可類推其含義,不一一列出。
DFT的快速演算法
又稱為快速傅立葉變換(FFT)。當序列的長度N為2的整數次冪(即N=2
,λ為整數)時,演算法的指導思想是將一個N 點序列的DFT分成兩個N/2點序列的DFT,再分成四個N/4點序列的DFT,如此下去,直到變成N/2個兩點序列的DFT。這種快速演算法的計算工作量與DFT的直接計算的計算工作量之比約為log2N/(2N),以N=1024為例FFT的計算工作量僅約為DFT直接計算的1/200。