所有考试总算考完了,于是我被LAJi学校坑去生产线QAQ
趁着脑袋还记得先马一下(距离遗忘DSP所有内容还有30min
已知X[m]=∑k=0N−1x[k]WNkm,m=0,1,...N−1
那么
X[m]=k=0∑N−1[k==2r]x[k]WNkm+k=0∑N−1[k==2r+1]x[k]WNkm
X[m]=r=0∑N/2−1x[2r]WN2rm+r=0∑N/2−1x[2r+1]WN(2r+1)m
=r=0∑N/2−1x[2r]WN2rm+WNmr=0∑N/2−1x[2r+1]WN2rm
=r=0∑N/2−1x1[r]WN2rm+WNmr=0∑N/2−1x2[r]WN2rm
由可约,
=r=0∑N/2−1x1[r]WN/2rm+WNmr=0∑N/2−1x2[r]WN/2rm
X[m]=X1[m]+X2[m]
由周期,
X1[m+N/2]=X1[m]
X2[m+N/2]=X2[m]
由对称,
WNm+N/2=−WNm
可得到另一边
X[m+N/2]=X1[m+N/2]+WNm+N/2X2[m+N/2]=X1[m]−WNmX2[m]
对比一下
X[m]=X1[m]+WNmX2[m]
X[m+N/2]=X1[m]−WNmX2[m]
复杂度
T(n)=2T(n/2)+O(n)
FFT流程图要点
1.过程我觉得按照自底向上的写法比较好
2.原输入顺序是通过二进制的翻转(不是反)来确认的
本来考试前画了一张挺漂亮的图但找不到了..
换了一张灵魂作图
