#include?
#include?“fft_int.h“

//此代碼來(lái)源《數(shù)字信號(hào)處理C語(yǔ)言程序集》殷福亮、宋愛(ài)軍，沈陽(yáng)：遼寧科學(xué)技術(shù)出版社，1997.7
//數(shù)組x存儲(chǔ)時(shí)域序列的實(shí)部，數(shù)組y存儲(chǔ)時(shí)域序列的虛部
//n代表N點(diǎn)FFT，sign=1為FFT，sign=-1為IFFT
extern??int?x[32];
extern??int?y[32];
void?FFT（?int?x[]?int?y[]int?nint?sign）
{
int?ijklmn1n2;
double?cc1ess1ttrti;

//unsigned?char?cc1ess1ttrti;
//unsigned?char?ijklmn1n2;
//Calculate?i?=?log2N
for（j?=?1i?=?1;?i<32;?i++）
{
?????m?=?i;
?????j?=?2*j;
?????if（j?==?n）
?????????break;
}

//計(jì)算蝶形圖的輸入下標(biāo)（碼位倒讀）
n1?=?n?-?1;
for（j=0i=0;?i{
????if（i????{
?????????tr?=?x[j];
?????????ti?=?y[j];
?????????x[j]?=?x[i];
?????????y[j]?=?y[i];?
?????????x[i]?=?tr;
?????????y[i]?=?ti;?????????????????
????}
????k?=?n/2;
????while（k<（j+1））
????{
????????j?=?j?-?k;
????????k?=?k/2;??????????????
????}
????j?=?j?+?k;
}

//計(jì)算每一級(jí)的輸出，l為某一級(jí)，i為同一級(jí)的不同群，使用同一內(nèi)存（即位運(yùn)算）
n1?=?1;
for（l=1;?l<=m;?l++）
{
????n1?=?2*n1;
????n2?=?n1/2;
????e?=?3.1415926/n2;
????c?=?1.0;
????s?=?0.0;
????c1?=?cos（e）;
????s1?=?-sign*sin（e）;
????for（j=0;?j????{
????????for（i=j;?i????