豆豉

[拼音]：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。