快速傅里叶变换FourierSeries

JeanBaptisteJosephFourier(French)(1763~1830)DiscreteFourierTransform在處理信號時，常藉由離散傅立葉轉換(DiscreteFourierTransform,DFT)來取得信號所對應的頻譜；再由頻譜來讀取信號的參數。但由於離散傅立葉所做的計算量過於龐大，當處理大量的資料時，需要快速計算的演算法。FastFourierTransformFFT(FastFourierTransform)，大幅提高頻譜的計算速度FFT使用條件：信號必須是週期性的。取樣週期必須為信號週期的整數倍。取樣速率(Samplingrate)必須高於信號最高頻率的2倍以上。取樣點數N必須為2k個資料。FourierSeries任一週期(periodic)函數可以分解成許多不同振幅(amplitude)，不同頻率(frequency)的正弦(sinusoidal)諧波(harmonic)與餘弦(cosinusoidal)諧波(harmonic)的合成(composition)FourierSeries傅立葉級數(FourierSeries)的基本觀念即是以弦波函數來組成信號空間，每個週期函數都可利用弦波函數來組成。一個信號x(t)可以表為傅立葉級數如下：方形波三種諧波(harmonic)三個諧波的合成Addingharmonics頻譜比較FourierSeries•尤拉公式:eiφ=cosφ+isinφ其概念與複數平面之極式相通FourierSeries以複數型式表示傅立葉級數，將更為簡潔DiscreteFourierTransform(DFT)在處理信號時，常藉由離散傅立葉轉換(DiscreteFourierTransform,DFT)來取得信號所對應的頻譜；再由頻譜來讀取信號的參數。但由於離散傅立葉所做的計算量過於龐大，當處理大量的資料時，需要快速計算的演算法。DiscreteFourierTransform(DFT)以數位方式對連續信號取樣，週期時間T之內，可取樣N個取樣點的數位信號DFT可表為DiscreteFourierTransform(DFT)式中m為頻域上的第m個刻度，n為時域上的第n個刻度X(m)為頻域上第m個刻度向量，x(n)為時域上第n個刻度純量FastFourierTransformFFT(FastFourierTransform)，大幅提高頻譜的計算速度FFT使用條件：信號必須是週期性的。取樣週期必須為信號週期的整數倍。取樣速率(Samplingrate)必須高於信號最高頻率的2倍以上。取樣點數N必須為2k個資料。快速傅利葉轉換原理Acomplexnthrootofunityisacomplexnumberzsuchthatzn=1.n=e2i/n=principalnthrootofunity.eit=cost+isint.i2=-1.Thereareexactlynrootsofunity:nk,k=0,1,...,n-1.0=112=i34=-156=-i7快速傅利葉轉換原理n2=n/2nn+k=nk