DSP

FFT及其框图实现

2019-07-13 16:57发布

站内文章 / DSP
14521 0 1431
class="markdown_views prism-github-gist"> FFTFFT及其框图实现   基22时域抽取
  基22频域抽取   FFTFFT的全称为快速傅里叶变换，但是FFTFFT并不是一种变换，而是实现DFTDFT的一种快速算法。当NN比较大时，使用FFTFFT可大大减少进行DFTDFT变换的计算量。   NN点的DFTDFT所需的计算量为:
X[k]=∑n=0N−1x[n]WNknX[k]=sum_{n=0}^{N-1}x[n]W_N^{kn}
乘法:N2N^2次，加法:N(N−1)N(N-1)次。每当NN提高一倍，计算量增大四倍。

基22时域抽取

  假设有一长度为2N2N的有限长序列x[n]x[n]，现对其进行DFTDFT变换，现有一算法可以将2N2N点的DFTDFT计算降为NN的DFTDFT计算，如下:
  记g[n]g[n]为x[n]x[n]的下标为偶数时的序列，即g[n]=x[2n],0≤n≤N−1g[n]=x[2n],0leq n leq N-1,记v[n]v[n]为x[n]x[n]的下标为奇数时的序列，即v[n]=x[2n+1],0≤n≤N−1v[n]=x[2n+1],0leq n leq N-1,则
X[k]=∑n=02N−1x[n]W2Nkn=∑n=0N−1x[2n]W2Nk2n+∑n=0N−1x[2n+1]W2Nk(2n+1)=∑n=0N−1g[n]WNkn+W2Nk∑n=0N−1v[n]WNkn=G[<k>N]+W2NkV[<k>N],0≤k≤2N−1 egin{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}^ksum_{n=0}^{N-1}v[n]W_N^{kn} \ &=G[<k>_N]+W_{2N}^{k}V[<k>_N], 0leq k leq 2N-1 end{aligned}
当0≤k≤N−10 leq k leq N-1时
X[k]=G[k]+W2NkV[k]X[k]=G[k]+W_{2N}^kV[k]
当N≤k≤2N−1N leq k leq 2N-1时
X[k]=G[<k>N]+W2NkV[<k>N]→k=m+NG[m]−W2NmV[m],0≤m≤N−1X[k]=G[<k>_N]+W_{2N}^{k}V[<k>_N]xrightarrow{k=m+N}G[m]-W_{2N}^{m}V[m], 0leq m leq N-1
其中g[n]g[n]和v[n]v[n]的DFTDFT都是NN点的。   两个NN点的DFTDFT的运算量(以乘法为例)为2N22N^2,而一个2N2N点的DFT

热门文章