#include?
#include?“fft_int.h“

//此代碼來源《數字信號處理C語言程序集》殷福亮、宋愛軍，沈陽：遼寧科學技術出版社，1997.7
//數組x存儲時域序列的實部，數組y存儲時域序列的虛部
//n代表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;
}

//計算蝶形圖的輸入下標（碼位倒讀）
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;
}

//計算每一級的輸出，l為某一級，i為同一級的不同群，使用同一內存（即位運算）
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????