用一次N点的DFT实现2N点序列的DFT

理论分析如下： 依题意，对于序列)192cos(21)72cos(][n N

n N n x ?+?=ππ，只能进行一次N 点的DFT ，以得到x[n]的2N 点的DFT ：N n x DFT k X 2)]([)(=

，考虑序列的长度2N=128是2的7次幂，采用基-2FFT 算法中的按时间抽取的FFT 算法，具体分析如下：

将长度为N 的序列x[n]，将x[n]分解为偶数点和奇数点：

G[n]=x[2r],r=0,1,…,N-1;

H[n]=x[2r+1],r=0,1,…,N-1;

因此可以得到

1,...1,0],[2][][2][22]12[222]2[)(10101010-=+=+=++=∑∑∑∑-=-=-=-=N k k H N

k W k G N

kr W r h N k W N kr W r g N kr W r x N k W N kr W r x k X N r N r N r N r 由G[k],H[k]的周期为N/2和N k W N N k W

22-=+，可得： 前半部：1,...1,0],[2][][-=+=N k k H N

k W k G k X ；○1 后半部：1,...1,0],[2][][2][][-=-=++++=+N k k H N k W k G N k H N

N k W

N k G N k X ○

2 因此，我们考虑建立一个新的序列y[n]=g[n]+j*h[n]，通过对y[n]进行N 点的DFT ，从而得到G[k]和H[k]，以用以上的蝶形运算计算出X[k]。

以下是对于对y[n]进行N 点的DTF ，从而得到G[k]和H[k]的分析：

由y[n]=g[n]+j*h[n]，

有

Y[k]=DFT{y[n]}=DFT{g[n]+j*h[n]}=DFT{g[n]}+DFT{j*

h[n]}=G[k]+j*H[k]={ReG[k]-ImH[k]}+j*{ImG[k]+ReH[

k]}

由DFT 的共轭对称性可知，序列实部的DFT 对应原序列DFT 的周期共轭对称分量，则

G[k]=(1/2)*{Y[k]+Y *

[N-k]},○3

同理，序列虚部的DFT 对应原序列DFT 的周期共轭反对称分量，即有 H[k]=-j*(1/2)*{Y[k]-Y *

[N-k]}，○4

因此，只要对新序列y[n]=g[n]+j*h[n]进行N 点的DFT ，即可通过○3○4，得到G[k]和H[k]，进行蝶形运算○1○2即可得到对应的原序列的2N 点得DFT ：N n x DFT k X 2)]([)(