16点DFT的FFT算法 DFT与FFT运算时间对比！急求~~如果给出结果，追加100...
\u79bb\u6563\u5085\u7acb\u53f6\u53d8\u6362\uff08DFT\uff09\u548c\u5feb\u901f\u7b97\u6cd5\uff08FFT\uff09\u7684\u533a\u522b\u662f\u4ec0\u4e48\uff1f\u7528matlab\uff1f\u8fd9\u4e2a\u505a\u5b9e\u9a8c\u65f6\u5019\u5c31\u7b97\u554a \u6211\u6709\u8ba1\u7b97fft\u7684 DFT\u7684\u5c31\u7b97\u4e86 \u90a3\u4e2a\u6709\u5f88\u591a \u4f46\u662f\u90fd\u8fd9\u4e48\u957f\u65f6\u95f4\u4e86 \u4f60\u8fd8\u8981\u5417
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;
}
参考8点按时间抽取FFT算法，扩展一下就行了，采样输入序列要按序号进行二进制逆序排序（就是将序号的二进制码颠倒，再排序，比如x[1]的序号7的二进制码是001，颠倒一下是100，所以放在第4位，而x[0]的序号0的二进制码是000，排序后还是放在第0位）。8点里面上图中的N就是8，16点改成16，W右上角的系数观察上图，就可以看了规律了。建议看下书吧 ，分析一下拆分方法和递推公式，很简单的
绛旓細鏃犻檺闀跨殑搴忓垪涔熷線寰鍙互鐢ㄦ湁闄愰暱搴忓垪鏉ラ艰繎銆傚浜庢湁闄愰暱鐨勫簭鍒楁垜浠彲浠ヤ娇鐢ㄧ鏁ｅ倕绔嬪彾鍙樻崲锛DFT锛(鍏紡娌℃硶杈撳叆锛屼笉濂芥剰鎬)銆侱FT鏄搴忓垪鍌呯珛鍙跺彉鎹㈢殑绛夎窛閲囨牱銆傛槸搴忓垪鍌呯珛鍙跺彉鎹㈢殑绛夎窛閲囨牱銆傚揩閫熷倕绔嬪彾鍙樻崲FFT骞朵笉鏄笌DFT涓嶇浉鍚岀殑鍙︿竴绉嶅彉鎹紝鑰屾槸涓轰簡鍑忓皯DFT杩愮畻娆℃暟鐨勪竴绉嶅揩閫绠楁硶銆傚畠鏄DFT鍙樻崲寮...
绛旓細渚嬮涓殑 f 闄や簡512锛屽洜涓哄仛鐨512涓偣鐨刦ft銆傚鏋滄敼鎴愬叾瀹冪殑鐐规暟鐨刦ft锛岄偅涔堟í鍧愭爣闂撮殧涔熼渶瑕佹敼銆傛讳箣锛岀粨鏋滈櫎浜唂ft甯︽潵鐨勮宸紝搴旇鏄樊涓嶅鐨勩傜旱鍧愭爣娌℃湁澶鐨勬剰涔夛紝鍥犱负鍌呴噷鍙跺彉鎹㈠墠搴旇鏈夌郴鏁扮殑锛宮atlab鐪佺暐浜嗙郴鏁帮紝瀵艰嚧瀹為檯澶у皬娌℃湁澶鎰忎箟锛屼絾鏄袱涓鐜囧搴旂殑骞呭兼瘮鍊艰〃绀鸿繖涓や釜棰戠巼鎴愬垎鐨勫崰...
绛旓細澶ф暟鎹噺鐨勮瘽锛屽綋鐒舵槸fft浜嗐傚叾瀹FFT灏辨槸DFT鐨蹇绠楁硶锛屼袱鑰呮槸涓鏍风殑銆傚彧涓嶈繃FFT杩愮畻閫熷害鏇村揩
绛旓細N涓洪噰鏍风偣锛 STFT鐭椂鍌呴噷鍙跺彉鎹紝瀹為檯涓婃槸瀵逛竴绯诲垪鍔犵獥鏁版嵁鍋FFT銆傛湁鐨勫湴鏂逛篃浼氭彁鍒癉CT锛堢鏁ｅ倕閲屽彾鍙樻崲锛夛紝鑰孌CT璺烣FT鐨勫叧绯诲氨鏄鏁ｅ倕閲屽彾鍙樻崲锛欶FT鏄疄鐜癉CT鐨勪竴绉嶅揩閫绠楁硶銆 FFT鏈変釜鍙傛暟N锛岃〃绀哄澶氬皯涓偣鍋欶FT锛屽鏋滀竴甯ч噷闈㈢殑鐐圭殑涓暟灏忎簬N灏变細zero-padding鍒癗鐨勯暱搴︺傛瘡涓偣瀵瑰簲涓涓鐜...
绛旓細FFT琛ラ浂: N鐐笵FT鐨棰戣氨鍒嗚鲸鐜囨槸2蟺 /N銆傛爡鏍忔晥搴斾竴鑺傛寚鍑哄彲浠ラ氳繃琛ラ浂瑙傚療鍒版洿澶氱殑棰戠偣(瑙併婃暟瀛椾俊鍙峰鐞嗐嬭鏈148椤),浣嗘槸杩欏苟涓嶆剰鍛崇潃琛ラ浂鑳藉鎻愰珮鐪熸鐨勯璋卞垎杈ㄧ巼銆傝繖鏄洜涓簒[n]瀹為檯涓婃槸x(t) 閲囨牱鐨勪富鍊煎簭鍒,鑰屽皢x[n]琛ラ浂寰楀埌鐨剎鈥橻n] 鍛ㄦ湡寤舵嫇涔嬪悗涓庡師鏉ョ殑搴忓垪骞朵笉鐩稿悓,涔熶笉鏄痻(t)鐨勯噰鏍枫傚洜姝...
绛旓細2DIT-FFT鐨勮繍绠楅噺113.3DIT-FFT绠楁硶鐨勭壒鐐123.4N=16鏃剁殑DIT-FFT绠楁硶144MATLAB绋嬪簭浠ｇ爜154.1N=8鐐笵IT-FFT浠ｇ爜154.2N=16鐐DIT-FFT浠ｇ爜165MATLAB浠跨湡缁撴灉鍙婇獙璇175.1DIT-FFT鍑芥暟璋冭瘯175.2DIT-FFT鍑芥暟杩愯缁撴灉185.3璋冪敤绯荤粺鍑芥暟楠岃瘉196蹇冨緱浣撲細21鍙傝冩枃鐚22鎽樿姝ゆ璇捐鐩殑鏄埄鐢∕ATLAB瀹炵幇8鐐瑰熀浜嶥IT鐨...
绛旓細DFT鐨鍙樻崲涓庡弽鍙樻崲鍏紡锛氳繖閲屼笉鍋氳缁嗘帹瀵硷紝缃戜笂鏈夊緢澶氭帹瀵艰繃绋嬨備絾鏄綋n寰堝ぇ鏃讹紝璁＄畻閲忓緢澶э紝杩欏氨寮曞叆浜咶FT銆1965骞,搴撳埄(cooley)鍜屽浘鍩(Tukey)棣栧厛鎻愬嚭FFT绠楁硶.瀵逛簬N鐐笵FT,浠呴渶(N/2)log2N 娆″鏁颁箻娉曡繍绠.渚嬪N=1024=2鐨10娆″箓鏃讹紝闇瑕(1024/2)log2 2鐨10娆″箓 =512*10=5120娆°5120/1048576...
绛旓細DFT锛欴FT闇瑕佽繘琛1400娆″鏁板姞娉曞拰1400娆″鏁颁箻娉曘FFT锛欶FT闇瑕佽繘琛宭og2(1400)娆″鏁板姞娉曞拰1400娆″鏁颁箻娉
绛旓細fft(x,n)鏄竴缁村揩閫熷倕閲屽彾鍙樻崲锛寈鐩稿綋浜庝俊鍙凤紝n鏄彉鎹㈢偣鏁般傜鏁ｅ倕閲屽彾鍙樻崲DFT鐨蹇绠楁硶灏辨槸FFT銆
绛旓細鑰屽鏋滄垜浠皢杩欑鈥滀竴鍒嗕负浜屸濈殑鎬濇兂涓嶆柇杩涜涓嬪幓锛岀洿鍒板垎鎴愪袱涓や竴缁勭殑DFT杩愮畻鍗曞厓锛岄偅涔圢鐐圭殑 DFT鍙樻崲灏卞彧闇瑕丯log2N娆＄殑杩愮畻锛孨鍦1024鐐规椂锛岃繍绠楅噺浠呮湁10240娆★紝鏄厛鍓嶇殑鐩存帴绠楁硶鐨1%锛岀偣鏁拌秺澶氾紝杩愮畻閲忕殑鑺傜害灏辫秺澶э紝杩欏氨鏄 FFT鐨勪紭瓒婃.鍌呴噷鍙跺彉鎹紙Transform茅e de Fourier锛夋槸涓绉嶇Н鍒嗗彉鎹...
