FFT（快速傅裏葉變換）是DFT的壹種特殊情況，就是當運算點的個數是2的整數次冪的時候進行的運算（不夠用0補齊）。
FFT計算原理及流程圖：
原理：FFT的計算要求點數必須為2的整數次冪，如果點數不夠用0補齊。例如計算{2，3，5，8，4}的16點FFT，需要補11個0後進行計算。FFT計算運用蝶形運算，在蝶形運算中變化規律由W(N, p)推導，其中N為FFT計算點數，J為下角標的值。
L = 1時，W(N, p) = W(N, J) = W(2^L, J)，其中J = 0;
L = 2時，W(N, p) = W(N, J) = W(2^L, J)，其中J = 0, 1;
L = 3時，W(N, p) = W(N, J) = W(2^L, J)，其中J = 0, 1, 2, 3;
所以，W(N, p) = W(2^L, J)，其中J = 0, 1, ..., 2^(L-1)-1
又因為2^L = 2^M*2^(L-M) = N*2^(L-M)，這裏N為2的整數次冪，即N=2^M，
W(N, p) = W(2^L, J) = W(N*2^(L-M), J) = W(N, J*2^(M-L))
所以，p = J*2^(M-L)，此處J = 0, 1, ..., 2^(L-1)-1，當J遍歷結束但計算點數不夠N時，J=J+2^L，後繼續遍歷，直到計算點數為N時不再循環。
流程圖：
實現代碼：
/*======================================================================? *?方法名：fft? *?方法功能：計算數組的FFT，運用蝶形運算? *? *?變量名稱：? *yVector?-?原始數據? *length-?原始數據長度? *N?-?FFT計算點數? *fftYreal-?FFT後的實部? *fftYImg?-?FFT後的虛部? *? *?返回值：是否成功的標誌，若成功返回true，否則返回false? *=====================================================================*/+?(BOOL)fft:(floatfloat?*)yVector?andOriginalLength:(NSInteger)length?andFFTCount:(NSInteger)N?andFFTReal:(floatfloat?*)fftYReal?andFFTYImg:(floatfloat?*)fftYImg
{
//?確保計算時時2的整數冪點數計算
NSInteger?N1?=?[self?nextNumOfPow2:N];
//?定義FFT運算是否成功的標誌
BOOL?isFFTOK?=?false;
//?判斷計算點數是否為2的整數次冪
if?(N?!=?N1)
{
//?不是2的整數次冪，直接計算DFT
isFFTOK?=?[self?dft:yVector?andOriginalLength:length?andFFTCount:N?andFFTReal:fftYReal?andFFTYImg:fftYImg];
//?返回成功標誌
return?isFFTOK;
}
//?如果計算點數位2的整數次冪，用FFT計算，如下
//?定義變量
float?yVectorN[N1];?//?N點運算的原始數據
NSInteger?powOfN?=?log2(N1);//?N?=?2^powOfN，用於標記最大運算級數(公式中表示為：M)
NSInteger?level?=?1;//?運算級數（第幾次運算），最大為powOfN，初值為第壹級運算(公式中表示為：L)
NSInteger?lineNum;//?行號，倒序排列後的蝶形運算行號(公式中表示為：k)
float?inverseOrderY[N1];//?yVector倒序x
NSInteger?distanceLine?=?1;?//?行間距，第level級運算每個蝶形的兩個節點距離為distanceLine?=?2^(L-1)(公式中表示為：B)
NSInteger?p;//?旋轉因子的階數，旋轉因子表示為?W(N,?p)，p?=?J*2^(M-L)
NSInteger?J;//?旋轉因子的階數，旋轉因子表示為?W(2^L,?J)，J?=?0,?1,?2,...,?2^(L-1)?-?1?=?distanceLine?-?1
float?realTemp,?imgTemp,?twiddleReal,?twiddleImg,?twiddleTheta,?twiddleTemp?=?PI_x_2/N1;
NSInteger?N_4?=?N1/4;
//?判斷點數是否夠FFT運算點數
if?(length?<=?N1)
{
//?如果N至少為length，先把yVector全部賦值
for?(NSInteger?i?=?0;?i?<?length;?i++)
{
yVectorN[i]?=?yVector[i];
}
if?(length?<?N1)
{
//?如果?N?>?length?後面補零
for?(NSInteger?i?=?length;?i?<?N1;?i++)
{
yVectorN[i]?=?0.0;
}
}
}
else
{
//?如果?N?<?length?截取相應長度的數據進行運算
for?(NSInteger?i?=?0;?i?<?N1;?i++)
{
yVectorN[i]?=?yVector[i];
}
}
//?調用倒序方法
[self?inverseOrder:yVectorN?andN:N1?andInverseOrderVector:inverseOrderY];
//?初始值
for?(NSInteger?i?=?0;?i?<?N1;?i++)
{
fftYReal[i]?=?inverseOrderY[i];
fftYImg[i]?=?0.0;
}
//?三層循環
//?第三層（最裏）：完成相同旋轉因子的蝶形運算
//?第二層（中間）：完成旋轉因子的變化，步進為2^level
//?第壹層（最外）：完成M次叠代過程，即計算出x(k)?=?A0(k),?A1(k),...,Am(k)?=?X(k)
//?第壹層循環
while?(level?<=?powOfN)
{
distanceLine?=?powf(2,?level?-?1);?//?初始條件?distanceLine?=?2^(level-1)
J?=?0;
NSInteger?pow2_Level?=?distanceLine?*?2;?//?2^level
NSInteger?pow2_NSubL?=?N1/pow2_Level;//?2^(M-L)
//?第二層循環
while?(J?<?distanceLine)
{
p?=?J?*?pow2_NSubL;
lineNum?=?J;
NSInteger?stepCount?=?0;?//?J運算的步進計數
//?求旋轉因子
if?(p==0)
{
twiddleReal?=?1.0;
twiddleImg?=?0.0;
}
else?if?(p?==?N_4)
{
twiddleReal?=?0.0;
twiddleImg?=?-1.0;
}
else
{
//?計算尤拉公式中的θ
twiddleTheta?=?twiddleTemp?*?p;
//?計算復數的實部與虛部
twiddleReal?=?cos(twiddleTheta);
twiddleImg?=?-11?*?sin(twiddleTheta);
}
//?第三層循環
while?(lineNum?<?N1)
{
//?計算下角標
NSInteger?footNum?=?lineNum?+?distanceLine;
/*---------------------------------------?
*?用復數運算計算每級中各行的蝶形運算結果? *?X(k)?=?X(k)?+?X(k+B)*W(N,p)? *?X(k+B)?=?X(k)?-?X(k+B)*W(N,p)? *---------------------------------------*/realTemp?=?fftYReal[footNum]?*?twiddleReal?-?fftYImg[footNum]?*?twiddleImg;
imgTemp=?fftYReal[footNum]?*?twiddleImg?+?fftYImg[footNum]?*?twiddleReal;
//?將計算後的實部和虛部分別存放在返回數組中
fftYReal[footNum]?=?fftYReal[lineNum]?-?realTemp;
fftYImg[footNum]=?fftYImg[lineNum]?-?imgTemp;
fftYReal[lineNum]?=?fftYReal[lineNum]?+?realTemp;
fftYImg[lineNum]=?fftYImg[lineNum]?+?imgTemp;
stepCount?+=?pow2_Level;
//?行號改變
lineNum?=?J?+?stepCount;
}
//?旋轉因子的階數變換，達到旋轉因子改變的效果
J++;
}
//?運算級數加壹
level++;
}
isFFTOK?=?true;
return?isFFTOK;
}