FFT及其框圖實現

\(FFT\)的全稱為快速傅里葉變換，但是\(FFT\)并不是一種變換，而是實現\(DFT\)的一種快速算法。當\(N\)比較大時，使用\(FFT\)可大大減少進行\(DFT\)變換的計算量。

\(N\)點的\(DFT\)所需的計算量為:
\[ X[k]=\sum_{n=0}^{N-1}x[n]W_N^{kn} \]
乘法:\(N^2\)次，加法:\(N(N-1)\)次。每當\(N\)提高一倍，計算量增大四倍。

基\(2\)時域抽取

假設有一長度為\(2N\)的有限長序列\(x[n]\)，現對其進行\(DFT\)變換，現有一算法可以將\(2N\)點的\(DFT\)計算降為\(N\)的\(DFT\)計算，記\(g[n]\)為\(x[n]\)的下標為偶數時的序列，即\(g[n]=x[2n],0\leq n \leq N-1\),記\(v[n]\)為\(x[n]\)的下標為奇數時的序列，即\(v[n]=x[2n+1],0\leq n \leq N-1\),則
\[ \begin{aligned} X[k]&=\sum_{n=0}^{2N-1}x[n]W_{2N}^{kn}\\ &=\sum_{n=0}^{N-1}x[2n]W_{2N}^{k2n}+\sum_{n=0}^{N-1}x[2n+1]W_{2N}^{k(2n+1)} \\ &=\sum_{n=0}^{N-1}g[n]W_N^{kn}+W_{2N}^k\sum_{n=0}^{N-1}v[n]W_N^{kn} \\ &=G[<k>_N]+W_{2N}^{k}V[<k>_N], 0\leq k \leq 2N-1 \end{aligned} \]
當\(0 \leq k \leq N-1\)時
\[ X[k]=G[k]+W_{2N}^kV[k] \]
當\(N \leq k \leq 2N-1\)時
\[ X[k]=G[<k>_N]+W_{2N}^{k}V[<k>_N]\xrightarrow{k=m+N}G[m]-W_{2N}^{m}V[m], 0\leq m \leq N-1 \]
其中\(g[n]\)和\(v[n]\)的\(DFT\)都是\(N\)點的。

兩個\(N\)點的\(DFT\)的運算量(以乘法為例)為\(2N^2\),而一個\(2N\)點的\(DFT\)運算量為\(4N^2\),計算量減少了一半!如果\(N=2^r\),則可以一直降下去，從而大大的減少了計算量。通過計算，可以知道此時的計算量為:乘法:\(\dfrac{N}{2}log_2N\),加法:\(Nlog_2N\)。

下面以8點的\(DFT\)為例,其實現框圖為:

基\(2\)頻域抽取

依然對于\(2N\)點的序列\(x[n]\)進行\(DFT\)計算，這次將\(x[n]\)分為前后兩部分，即\(g[n]\)為\(x[n]\)的前\(N\)個點,即\(g[n]=x[n],0 \leq n \leq N-1\),\(v[n]\)為\(x[n]\)的后\(N\)個點，即\(v[n]=x[n+N],0\leq n\leq N-1\),則:
\[ \begin{aligned} X[k]&=\sum_{n=0}^{2N-1}x[n]W_{2N}^{kn}\\ &=\sum_{n=0}^{N-1}x[n]W_{2N}^{kn}+\sum_{n=N}^{2N-1}x[n]W_{2N}^{kn} \\ &=\sum_{n=0}^{N-1}x[n]W_{2N}^{kn}+\sum_{m=0}^{N-1}x[m+N]W_{2N}^{k(m+N)}\\ &=\sum_{n=0}^{N-1}g[n]W_{2N}^{kn}+(-1)^k\sum_{n=0}^{N-1}v[n]W_{2N}^{kn} \end{aligned} \]
對其進行頻域抽取
\[ X[2r]=\sum_{n=0}^{N-1}g[n]W_{2N}^{2rn}+\sum_{n=0}^{N-1}v[n]W_{2N}^{2rn}=G[k]+V[k],0\leq r \leq N-1 \]
\[ X[2r+1]=\sum_{n=0}^{N-1}g[n]W_{2N}^{(2r+1)n}-\sum_{n=0}^{N-1}v[n]W_{2N}^{(2r+1)n}=W_{2N}^{n}(G[k]-V[k]) \]
該算法也將\(2N\)點的\(DFT\)降為了2個\(N\)點的\(DFT\)。

將上面時域抽取的實現框圖中所有的\(x[n]\)換成\(X[k]\),然后所有箭頭反向，即輸入變輸出，輸出變輸入，得到的框圖就是頻域抽取實現的框圖。

轉載于:https://www.cnblogs.com/LastKnight/p/10958076.html

總結

以上是生活随笔為你收集整理的15 FFT及其框图实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。