FFT（fast Fourier transformation）即快速傅里葉變換，是離散傅里葉變換的一種快速算法。它是根據(jù)離散傅里葉變換的奇、偶、虛、實(shí)特性，對(duì)離散傅里葉變換的算法進(jìn)行改進(jìn)而得到的。在

FFT（fast Fourier transformation）即快速傅里葉變換，是離散傅里葉變換的一種快速算法。它是根據(jù)離散傅里葉變換的奇、偶、虛、實(shí)特性，對(duì)離散傅里葉變換的算法進(jìn)行改進(jìn)而得到的。在傅里葉變換理論上沒有新的發(fā)現(xiàn)，但在計(jì)算機(jī)系統(tǒng)或數(shù)字系統(tǒng)中應(yīng)用離散傅里葉變換是向前邁出的一大步。

在FFT中，利用WN的周期性和對(duì)稱性，將N項(xiàng)序列（設(shè)N=2K，K為正整數(shù)）劃分為兩個(gè)N/2項(xiàng)子序列。每個(gè)n/2點(diǎn)DFT變換需要（n/2）兩次運(yùn)算，然后用n次運(yùn)算將兩個(gè)n/2點(diǎn)DFT變換組合成一個(gè)n點(diǎn)DFT變換。經(jīng)過此轉(zhuǎn)換后，操作總數(shù)變?yōu)閚2*（N/2）^2=n2^2/2。

FFT提高了運(yùn)算速度，但也限制了采樣數(shù)，即2^n點(diǎn)。DFT沒有這樣的限制。

小結(jié)：FFT速度快，DFT靈活，各有優(yōu)點(diǎn)，如果滿足分析要求，兩者的精度是一樣的。

快速傅里葉變換和離散傅里葉變換的主要區(qū)別是什么？哪個(gè)準(zhǔn)確？

離散時(shí)間傅里葉變換有時(shí)稱為順序傅里葉變換。離散時(shí)間傅里葉變換本質(zhì)上是單位圓上的（雙邊）Z變換。當(dāng)時(shí)域信號(hào)為連續(xù)信號(hào)時(shí)，采用連續(xù)時(shí)間傅里葉變換；當(dāng)時(shí)域信號(hào)為離散信號(hào)時(shí)，采用離散時(shí)間傅里葉變換。

離散時(shí)間傅里葉變換（DTFT）使我們能夠在頻域（數(shù)字頻域）分析離散時(shí)間信號(hào)的頻譜和離散時(shí)間系統(tǒng)的頻率響應(yīng)特性。但有兩個(gè)實(shí)際問題。

1. 數(shù)字頻率是一個(gè)模擬量。為了今后用數(shù)字方法對(duì)其進(jìn)行分析和處理，在時(shí)域?qū)r(shí)間變量t進(jìn)行離散是不夠的，在頻域?qū)?shù)字頻率進(jìn)行離散也是不夠的。

2. 大多數(shù)實(shí)數(shù)序列是無限長(zhǎng)的。為了便于分析和處理，必須對(duì)無限序列進(jìn)行截?cái)嗷蚍侄危⑵滢D(zhuǎn)化為有限序列。

DTFT是對(duì)任意序列的傅里葉分析，其頻譜是連續(xù)函數(shù)；DFT是將有限長(zhǎng)序列作為周期序列，對(duì)有限長(zhǎng)序列的傅里葉分析，DFT的特點(diǎn)是在時(shí)域和頻域都是有限長(zhǎng)序列。

DFT提供了一種用計(jì)算機(jī)分析信號(hào)和系統(tǒng)的方法，特別是FFT，它是DFT的一種快速算法。它已廣泛應(yīng)用于許多科學(xué)技術(shù)領(lǐng)域，推動(dòng)了數(shù)字信號(hào)處理技術(shù)的快速發(fā)展。