離散傅立葉變換

離散傅立葉變換，是傅立葉變換在時域和頻域上都呈離散的形式，將訊號的時域取樣變換為其DTFT的頻域取樣。在形式上，變換兩端的序列是有限長的，而實際上這兩組序列都應當被認為是離散週期訊號的主值序列。即使對有限長的離散訊號作DFT，也應當將其看作其週期延拓的變換。在實際應用中通常採用快速傅立葉變換計算DFT。定義.對於formula_1點序列formula_2，它的離散傅立葉變換為formula_3其中formula_4是自然對數的底數，formula_5是虛數單位。通常以符號formula_6表示這一變換，即formula_7離散傅立葉變換的逆變換為：formula_8可以記為：formula_9實際上，DFT和IDFT變換式中和式前面的歸一化係數並不重要。在上面的定義中，DFT和IDFT前的係數分別為formula_10和formula_11。有時會將這兩個係數都改成formula_12。從連續到離散.連續時間訊號formula_13以及對應的連續傅立葉變換formula_14都是連續函式。由於數位系統只能處理有限長的離散訊號，因此必須將formula_15和formula_16都離散化，並且建立對應的傅立葉變換。假設formula_13時限於formula_18，再透過時域取樣將formula_13離散化，就可以得到有限長離散訊號，記為formula_20。設取樣週期為formula_21，則時域取樣點數formula_22。formula_23它的傅立葉變換為formula_24這就是formula_13在時域取樣後的連續傅立葉變換，也就是離散時間傅立葉變換，它在頻域依然是連續的。下面將頻域訊號轉化為有限長離散訊號。與對時域訊號的處理類似，假設頻域訊號是帶限的，再經過離散化，即可得到有限長離散訊號。依據取樣定理，頻域取樣若要能完全重建原訊號，頻域訊號formula_14應當帶限於formula_27。由於時域訊號時限於formula_18，由取樣定理以及時頻對偶的關係，頻域的取樣間隔應為formula_29。故，頻域取樣點數為：formula_30即頻域取樣的點數和時域取樣同為formula_1，頻域取樣點為formula_32。而DTFT在頻域上取樣：formula_33令formula_34，將其歸一化，就得到前面定義的離散傅立葉變換。因此，DFT就是先將訊號在時域離散化，求其連續傅立葉變換後，再在頻域離散化的結果。DFT與CFT.下面考察離散傅立葉變換與連續傅立葉變換的關係。連續傅立葉變換formula_35的取樣為：formula_36將這個積分以黎曼和的形式近似，有：formula_37這一結論指出離散傅立葉變換確實是連續傅立葉變換在某種意義上的近似。不過必須注意以下兩點：為此，通常對連續訊號的時域取樣再做一次加窗處理，這樣就得到帶限的有限長離散訊號。DFT與DTFT.離散時間傅立葉變換的DTFT為：formula_39對formula_40在離散的頻點formula_41上取樣formula_42即為formula_15的DFT。由於DTFT在頻域是週期的，所以在DTFT頻域上的均勻取樣也應是週期的。formula_44實際上是這個週期序列的主值序列。柵欄效應.formula_1點序列的DFT只能在有限的formula_1個頻點上觀察頻譜，這相當於從柵欄的縫隙中觀察景色，對於瞭解訊號在整個頻域上的特性是不夠的。為了觀察到其他頻率的資訊，需要對原訊號formula_38做一些處理，以便在不同的頻點上取樣。將原來在DTFT頻域上的取樣點數增加到formula_48點，這樣取樣點位置變為formula_49。則對應的DFT成為formula_50若在序列formula_38之後補上M-N個零，設為formula_52，則上式變為formula_53因此將formula_38補零再做DFT就可以得到formula_38的DTFT在其他頻率上的值，相當於移動了柵欄，因而能夠從其他位置進行觀察。頻譜解析度.formula_1點DFT的頻譜解析度是formula_57。柵欄效應一節指出可以透過補零觀察到更多的頻點，但是這並不意味著補零能夠提高真正的頻譜解析度。這是因為formula_38實際上是formula_13取樣的主值序列，而將formula_38補零得到的formula_52週期延拓之後與原來的序列並不相同，也不是formula_13的取樣。因此formula_63與formula_16是不同離散訊號的頻譜。對於補零至formula_48點的formula_66的DFT，只能說它的解析度formula_67僅具有計算上的意義，formula_63並不是真正的、物理意義上的頻譜。頻譜解析度的提高只能在滿足取樣定理的條件下增加時域取樣長度來實現。從空間的角度分析.週期為N的離散訊號構成一個"N"維歐幾里得空間formula_69。在這一空間上兩個訊號"x"和"y"的內積定義為formula_70下面給出formula_69上的一組正交基：formula_72將訊號"x"在這組正交基上分解，得formula_73令formula_74此即為離散傅立葉變換。又formula_75則有formula_76此即為離散傅立葉變換的逆變換。由此可知，在正交分解的角度上說，離散週期訊號formula_15的離散傅立葉變換formula_16實質上是formula_15在正交基formula_80上的分量。而從線性變換的角度上說，formula_80是圓周卷積的特徵向量，formula_16則是對應的特徵值。DFT與圓周卷積.根據卷積定理，離散訊號x與y的圓周卷積對偶於頻域上x與y離散傅立葉變換的乘積。下面揭示DFT與圓周卷積的內在關係。對長為N的離散訊號formula_83與formula_84，如果要計算它們的卷積，就必須定義formula_85與formula_86在"0≤n deg("a"("x")) + deg("b"("x"))。然後作圓周卷積：formula_117其中c就是"c"("x")係數的向量。由於圓周卷積的DFT是乘積，有：formula_118則formula_119利用快速傅立葉變換，這一演算法的運算複雜度為formula_120。OFDM.OFDM，使得只要通道延時小於迴圈字首的長度，就能消除通道延時對傳輸的影響。特殊例子.數論轉換.數論轉換是離散傅利葉轉換(DFT)的一個特例 formula_121，此運算是根據模運算 而取得的，formula_122需要是質數 ，如此可以建構出有限域，並且存在 formula_123 個可以整除 formula_124 的實數根。如此可以得到formula_125，formula_126 為正整數。令 formula_127 為第 formula_124 個單位根，則第 formula_123 個單位根 formula_130 可以表示成 formula_131 。另外，再令formula_1 為 formula_130 次方 formula_122 模運算之迴圈個數。則數論矩陣為formula_135formula_136 與 formula_137 各為 Column 與 Row 的指數(index), 令 formula_138 與 formula_139 各代表Column 與 Row 的總數，則formula_140， formula_141.舉個例子來說，當 formula_142 則formula_143formula_144formula_145formula_146因為 formula_147 經 formula_148 的模運算為 formula_149 ，因此可以判定此情況為 formula_150 個次方一迴圈，所以 formula_151，formula_1可以整除 formula_124。則數論矩陣可以表示成formula_154在一些特殊的情況下，令 formula_155 ，而 formula_100 不是值數也是有意義的。像是 Fermat Number Transform 中formula_157，以及 Mersenne Number Transform 中 formula_158.