① 單片機實現傅立葉變換
用FPGA這種單片機
在對FFT（快速傅立葉變換）演算法進行研究的基礎上，描述了用FPGA實現FFT的方法，並對其中的整體結構、蝶形單元及性能等進行了分析。
關鍵詞：
FPGA FFT
傅立葉變換是數字信號處理中的基本操作，廣泛應用於表述及分析離散時域信號領域。但由於其運算量與變換點數N的平方成正比關系，因此，在N較大時，直接應用DFT演算法進行譜變換是不切合實際的。然而，快速傅立葉變換技術的出現使情況發生了根本性的變化。本文主要描述了採用FPGA來實現2k／4k／8k點FFT的設計方法。
1 整體結構
一般情況下，N點的傅立葉變換對為：
其中，WN＝exp(－2 pi／N)。X(k)和x(n)都為復數。與之相對的快速傅立葉變換有很多種,如DIT(時域抽取法)、DIF（頻域抽取法）、Cooley－Tukey和Winograd等。對於2n傅立葉變換，Cooley－Tukey演算法可導出DIT和DIF演算法。本文運用的基本思想是Cooley－Tukey演算法，即將高點數的傅立葉變換通過多重低點數傅立葉變換來實現。雖然DIT與DIF有差別，但由於它們在本質上都是一種基於標號分解的演算法，故在運算量和演算法復雜性等方面完全一樣，而沒有性能上的優劣之分，所以可以根據需要任取其中一種，本文主要以DIT方法為對象來討論。
N＝8192點DFT的運算表達式為：
式中，m＝(4n1＋n2)(2048k1＋k2)(n＝4n1＋n2，k＝2048k1＋k2)其中n1和k2可取0,1,．．．,2047,k1和n2可取0,1,2,3。
由式（3）可知，8k傅立葉變換可由4×2k的傅立葉變換構成。同理，4k傅立葉變換可由2×2k的傅立葉變換構成。而2k傅立葉變換可由128×16的傅立葉變換構成。128的傅立葉變換可進一步由16×8的傅立葉變換構成，歸根結底，整個傅立葉變換可由基2、基4的傅立葉變換構成。2k的FFT可以通過5個基4和1個基2變換來實現；4k的FFT變換可通過6個基4變換來實現；8k的FFT可以通過6個基4和1個基2變換來實現。也就是說：FFT的基本結構可由基2／4模塊、復數乘法器、存儲單元和存儲器控制模塊構成，其整體結構如圖1所示。
圖1中，RAM用來存儲輸入數據、運算過程中的中間結果以及運算完成後的數據，ROM用來存儲旋轉因子表。蝶形運算單元即為基2／4模塊，控制模塊可用於產生控制時序及地址信號，以控制中間運算過程及最後輸出結果。
2 蝶形運算器的實現
基4和基2的信號流如圖2所示。圖中，若A＝r0＋j＊i0，B＝r1＋j＊i1，C＝r2＋j＊i2，D＝r3＋j＊i3是要進行變換的信號，Wk0＝c0＋j＊s0＝1，Wk1＝c1＋j＊s1，Wk2＝c2＋j＊s2，Wk3＝c3＋j＊s3為旋轉因子，將其分別代入圖2中的基4蝶形運算單元，則有：
A′＝[r0＋(r1×c1－i1×s1)＋(r2×c2－i2×s2)＋(r3×c3－i3×s3)]＋j[i0＋(i1×c1＋r1×s1)＋(i2×c2＋r2×s2)＋(i3×c3＋r3×s3)]� （4）
B′＝[r0＋(i1×c1＋r1×s1)－(r2×c2－i2×s2)－(i3×c3＋r3×s3)]＋j[i0－(r1×c1－i1×s1)－(
i2×c2＋r2×s2)＋(r3×c3－i3×s3)] (5）
C′＝[r0－(r1×c1－i1×s1)＋(r2×c2－i2×s2)－(r3×c3－i3×s3)]＋j[i0－(i1×c1＋r1×s1)＋(i2×c2＋r2×s2)－(i3×c3＋r3×s3)] （6）
D′＝[r0－(i1×c1＋r1×s1)－(r2×c2－i2×s2)＋(i3×c3＋r3×s3)]＋j[i0＋(r1×c1－i1×s1)－(i2×c2＋r2×s2)－(r3×c3－i3×s3)]� （7）
看明白了嗎？
② 傅里葉變換
離散傅里葉變換(discrete Fourier transform) 傅里葉分析方法是信號分析的最基本方法，傅里葉變換是傅里葉分析的核心，通過它把信號從時間域變換到頻率域，進而研究信號的頻譜結構和變化規律。但是它的致命缺點是： 計算量太大，時間復雜度太高，當采樣點數太高的時候，計算緩慢， 由此出現羨梁了DFT的快速實現，即下面的快速傅里葉變換FFT。
這里原始信號的三個正弦波的頻率分別為，200Hz、400Hz、600Hz,最大頻率為600赫茲。根據采樣定理，fs至少是600赫茲的2倍，這里選擇1400赫茲，即在一秒內選擇1400個點。
1400
[-4.18864943e-12+0.j 9.66210986e-05-0.04305756j 3.86508070e-04-0.08611996j
8.69732036e-04-0.12919206j 1.54641157e-03-0.17227871j]
換之後的結果數據長度和原始采樣信號是一樣的
每一個變換之後的值是一個復數，為a+bj的形式下標為0和 N /2的兩個復數的虛數部分為0，下標為i和 N - i 的兩個復數共輒，也就是其虛部數值相同、符號相反。再用ifft()從頻域轉回時域之後，出現了由誤差引起的很小的虛部，用np.real()取其實部即可．
由於一半是另一半的共軛，因此只需要關心一半數據．fft轉換後下標為0的春派巧實數表示時域信號中的直流成分（不隨時間變化）
振幅譜的縱坐標很大，而且具有對稱性
Y=A1+A2 cos(2πω2+φ2）+A3 cos(2πω3+φ3）+A4*cos(2πω4+φ4）
經過FFT之後，得到的「振幅圖」中，
第一個峰值（頻率位置）的模是A1的N倍，N為采樣點，本例中為N=1400，此例中沒有，因為信號沒有常數項A1
第二個峰值（頻率位置）的模是A2的N/2倍，N為采樣點，
第三個峰值（頻率位置）的模是A3的N/2倍，N為采樣點，
第四個峰值（頻率位置）的模是A4的N/2倍，N為采樣點，
STFT短時傅里葉變換，實際上是對一系列加窗數據做FFT。有的地方也會提到DCT（離散傅里葉變換），而DCT跟FFT的關系就是：FFT是實現DCT的一種快速演算法。
FFT有個參數N，表示對多少個點做FFT，如果一幀裡面的點的個數小於N就會zero-padding到N的長度。每個點對應一個頻率點，某一點n（n從1開始）表示的頻率為:
第一個點（n=1，Fn等於0）表示直流信號，最後一個點N的下一個點（實際上這個點是不存在的）表示采樣頻率Fs。
FFT後我們可以得到N個頻點，比如，采樣頻率為16000，N為1600，那麼FFT後就會得到1600個點扒鍵，FFT得到的1600個值的模可以表示1600個頻點對應的振幅。因為FFT具有對稱性，當N為偶數時取N/2+1個點，當N為奇數時，取(N+1)/2個點，比如N為512時最後會得到257個值。
scipy.signal.stft（x，fs = 1.0，window =『hann』，nperseg = 256，noverlap = None，nfft = None，detrend = False，return_oneside = True，boundary =『zeros』，padded = True，axis = -1 ）