用法：
//?函數名:?快速傅立葉變換（來源《C常用算法集》）
//?本函數測試OK可以在TC2.0VC++6.0Keil?C51測試通過。
//?如果你的MCS51系統有足夠的RAM時可以驗證一下用單片機處理FFT有多么的慢。
//
//?入口參數：?
//?l:?l?=?0?傅立葉變換;?l?=?1?逆傅立葉變換
//?il:?il?=?0不計算傅立葉變換或逆變換模和幅角；il?=?1計算模和幅角
//?n:?輸入的點數，為偶數，一般為32，64，128，...1024等
//?k:?滿足n=2^k（k>0）實質上k是n個采樣數據可以分解為偶次冪和奇次冪的次數
//?pr[]:?l=0時，存放N點采樣數據的實部
//?l=1時?存放傅立葉變換的N個實部
//?pi[]:?l=0時，存放N點采樣數據的虛部?
//?l=1時?存放傅立葉變換的N個虛部
//
//?出口參數：
//?fr[]:?l=0?返回傅立葉變換的實部
//?l=1?返回逆傅立葉變換的實部
//?fi[]:?l=0?返回傅立葉變換的虛部
//?l=1?返回逆傅立葉變換的虛部
//?pr[]:?il?=?1i?=?0?時，返回傅立葉變換的模
//?il?=?1i?=?1?時，返回逆傅立葉變換的模
//?pi[]:?il?=?1i?=?0?時，返回傅立葉變換的輻角
//?il?=?1i?=?1?時，返回逆傅立葉變換的輻角
//?data:?2005.8.15Mend?Xin?Dong

程序代碼：
#include
#include

#define?N?8

void?kkfft（double?pr[]?double?pi[]?int?n?int?k?double?fr[]?double?fi[]?int?l?int?il）;
void?main（）
{
?????double?xr[N]xi[N]Yr[N]Yi[N]l=0il=0;
?????int?ijn=Nk=3;
?????for（i=0;i?????{
?????????xr[i]=i;
?????????xi[i]=0;
?????}
?????printf（“------FFT------\n“）;
?????l=0;
?????kkfft（xrxinkYrYilil）;
?????for（i=0;i?????{
?????????printf（“%-11lf?+?j*?%-11lf\n“Yr[i]Yi[i]）;
?????}

?????printf（“-----DFFT-------\n“）;
?????l=1;
?????kkfft（YrYinkxrxilil）;
?????for（i=0;i?????{
?????????printf（“%-11lf?+?j*?%-11lf\n“xr[i]xi[i]）;
?????}
?????getch（）;
}


void?kkfft（double?pr[]?double?pi[]?int?n?int?k?double?fr[]?double?fi[]?int?l?int?il）
{
?????int?itmisijnvl0;
?????double?pqsvrvipoddrpoddi;
?????for?（it=0;?it<=n-1;?it++）
?????{
???????m?=?it;
????????is?=?0;
????????for（i=0;?i<=k-1;?i++）
????????{
????????j?=?m/2;
????????is?=?2*is+（m-2*j）;
????????m?=?j;
????????}
????????fr[it]?=?pr[is];
????????fi[it]?=?pi[is];
?????}


?????pr[0]