//?快速傅里?葉變換FFT的C語言算法徹底研究
?????????//?LED音樂頻譜顯示的核心算法就是快速傅里葉變換，FFT的理解和編程還是比較難的，特地撰寫此文分享一下研究成果。
//?一、徹底理解傅里葉變換	
//?快速傅里葉變換（Fast?Fourier?Transform）是離散傅里葉變換的一種快速算法，簡稱FFT，通過FFT可以將一個信號從時域變換到頻域。
//?模擬信號經過A/D轉換變為數字信號的過程稱為采樣。為保證采樣后信號的頻譜形狀不失真，采樣頻率必須大于信號中最高頻率成分的2倍，這稱之為采樣定理。
//?假設采樣頻率為fs，采樣點數為N，那么FFT結果就是一個N點的復數，每一個點就對應著一個頻率點，某一點n（n從1開始）表示的頻率為：fn=（n-1）*fs/N。
//?舉例說明：用1kHz的采樣頻率采樣128點，則FFT結果的128個數據即對應的頻率點分別是0，1k/128，2k/128，3k/128，…，127k/128?Hz。
//?這個頻率點的幅值為：該點復數的模值除以N/2（n=1時是直流分量，其幅值是該點的模值除以N）。
//?二、傅里葉變換的C語言編程
//?1、對于快速傅里葉變換FFT，第一個要解決的問題就是碼位倒序。
????//?假設一個N點的輸入序列，那么它的序號二進制數位數就是t=log2N.
????//?碼位倒序要解決兩個問題：①將t位二進制數倒序；②將倒序后的兩個存儲單元進行交換。
?
//?①將t=3位二進制數倒序
?
//?②將倒序后的兩個存儲單元進行交換
????//?如果輸入序列的自然順序號i用二進制數表示，例如若最大序號為15，即用4位就可表示n3n2n1n0，則其倒序后j對應的二進制數就是n0n1n2n3，那么怎樣才能實現倒序呢？利用C語言的移位功能！
//?程序如下，我不多說，看不懂者智商一定在180以下！
//?復數類型定義及其運算
#define?N?64??????//64點
#define?log2N?6???//log2N=6
/*復數類型*/
typedef?struct
{
?float?real;
?float?img;
}complex;
complex?xdata?x[N];?//輸入序列
/*復數加法*/
complex?add（complex?acomplex?b）
{
?complex?c;
?c.real=a.real+b.real;
?c.img=a.img+b.img;
?return?c;
}
/*復數減法*/
complex?sub（complex?acomplex?b）
{
?complex?c;
?c.real=a.real-b.real;
?c.img=a.img-b.img;
?return?c;
}
/*復數乘法*/
complex?mul（complex?acomplex?b）
{
?complex?c;
?c.real=a.real*b.real?-?a.img*b.img;
?c.img=a.real*b.img?+?a.img*b.real;
?return?c;
}
/***碼位倒序函數***/
void?Reverse（void）
{
?unsigned?int?ijk;
?unsigned?int?t;
?complex?temp;//臨時交換變量
?for（i=0;i?{
??k=i;//當前第i個序號
??j=0;//存儲倒序后的序號，先初始化為0
??for（t=0;t??{
???j<<=1;
???j|=（k&1）;//j左移一位然后加上k的最低位
???k>>=1;//k右移一位，次低位變為最低位
??}
??if（j>i）//如果倒序后大于原序數，就將兩個存儲單元進行交換（判斷j>i是為了防止重復交換）
??{
???temp=x[i];
???x[i]=x[j];
???x[j]=temp;
??}
?}
}
2、第二個要解決的問題就是蝶形運算
??
①第1級（第1列）每個蝶形的兩節點“距離”為1，第2級每個蝶形的兩節點“距離”為2，第3級每個蝶形的兩節點“距離”為4，第4級每個蝶形的兩節點“距離”為8。由此推得，
?第m級蝶形運算，每個蝶形的兩節點“距離”L=2m-1。
②對于16點的FFT，第1級有16組蝶形，每組有1個蝶形；第2級有4組蝶形，每組有2個蝶形；第3級有2組蝶形，每組有4個蝶形；第4級有1組蝶形，每組有8個蝶形。由此可推出，
對于N點的FFT，第m級有N/2L組蝶形，每組有L=2m-1個蝶形。
③旋轉因子?的確定
以16點FFT為例，第m級第k個旋轉因子為?，其中k=0～2m-1-1，即第m級共有2m-1個旋轉因子，根據旋轉因子的可約性，?，所以第m級第k個旋轉因子為?，其中k=0～2m-1-1。
為提高FFT的運算速度，我們可以事先建立一個旋轉因子數組，然后通過查表法來實現。
complex?code?WN[N]=//旋轉因子數組
{?//為節省CPU計算時間，旋轉因子采用查表處理
??//★根據實際FFT的點數N，該表數據需自行修改
??//以下結果通過Excel自動生成
??//??WN[k].real=cos（2*PI/N*k）;
??//??WN[k].img=-sin（2*PI/N*k）;
??{1.000000.00000}{0.99518-0.09802}{0.98079-0.19509}{0.95694-0.29028}
??{0.92388-0.38268}{0.88192-0.47140}{0.83147-0.55557}{0.77301-0.63439}
??{0.70711-0.70711}{0.63439-0.77301}{0.55557-0.83147}{0.47140-0.88192}
??{0.38268-0.92388}{0.29028-0.95694}{0.19509-0.98079}{0.09802-0.99518}
??{0.00000-1.00000}{-0.09802-0.99518}{-0.19509-0.98079}{-0.29028-0.95694}
??{-0.38268-0.92388}{-0.47140-0.88192}{-0.55557-0.83147}{-0.63439-0.77301}
??{-0.70711-0.70711}{-0.77301-0.63439}{-0.83147-0.55557}{-0.88192-0.47140}
??{-0.92388-0.38268}{-0.95694-0.29028}{-0.98079-0

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件??????17273??2010-06-07?10:25??DISPLAY\CORE\core_cm3.c

?????文件??????85714??2011-02-09?14:59??DISPLAY\CORE\core_cm3.h

?????文件??????15503??2011-03-10?10:52??DISPLAY\CORE\startup_stm32f10x_hd.s

?????文件??????12765??2011-03-10?10:52??DISPLAY\CORE\startup_stm32f10x_md.s

?????文件???????4743??2014-07-29?17:29??DISPLAY\HARDWARE\ADC\adc.c

?????文件????????312??2014-07-26?11:40??DISPLAY\HARDWARE\ADC\adc.h

?????文件??????23599??2014-08-01?15:02??DISPLAY\HARDWARE\ADC\fon.h

?????文件???????5188??2014-07-30?10:15??DISPLAY\HARDWARE\ADXL345\adxl345.c

?????文件???????2237??2014-07-30?10:09??DISPLAY\HARDWARE\ADXL345\adxl345.h

?????文件??????12320??2014-08-01?14:44??DISPLAY\HARDWARE\DM163\dm163.C

?????文件???????4494??2014-08-01?14:44??DISPLAY\HARDWARE\DM163\dm163.h

?????文件??????16475??2014-07-22?20:01??DISPLAY\HARDWARE\DM163\fon.h

?????文件???????1448??2014-07-29?21:43??DISPLAY\HARDWARE\EXTI\exti.c

?????文件????????132??2014-07-29?14:51??DISPLAY\HARDWARE\EXTI\exti.h

?????文件???????4172??2014-05-09?19:39??DISPLAY\HARDWARE\FFT\fft.c

?????文件?????????86??2014-05-09?15:49??DISPLAY\HARDWARE\FFT\fft.h

?????文件???????2555??2014-07-30?09:47??DISPLAY\HARDWARE\IIC\myiic.c

?????文件????????872??2014-07-29?20:42??DISPLAY\HARDWARE\IIC\myiic.h

?????文件????????525??2014-07-29?21:43??DISPLAY\HARDWARE\KEY\key.c

?????文件????????177??2014-07-29?21:43??DISPLAY\HARDWARE\KEY\key.h

?????文件????????534??2014-07-29?21:07??DISPLAY\HARDWARE\LED\led.c

?????文件????????139??2014-07-31?08:44??DISPLAY\HARDWARE\LED\led.h

?????文件????????399??2011-04-23?10:24??DISPLAY\keilkilll.bat

?????文件?????433932??2014-08-01?15:04??DISPLAY\OBJ\ADC.axf

?????文件?????295596??2014-07-31?11:10??DISPLAY\OBJ\adc.crf

?????文件????????808??2014-07-31?11:10??DISPLAY\OBJ\adc.d

?????文件??????77697??2014-08-01?15:04??DISPLAY\OBJ\ADC.hex

?????文件?????121937??2014-08-01?15:04??DISPLAY\OBJ\ADC.htm

?????文件????????800??2014-08-01?15:04??DISPLAY\OBJ\ADC.lnp

?????文件?????314856??2014-07-31?11:10??DISPLAY\OBJ\adc.o

............此處省略229個文件信息