关于FFT ButterFly做完之后为什么是bitreversal order的

关于ButterFly做完之后为什么是bitreversal order的

FFT的算法是将多项式拆为两半,偶数和奇数部分,分别记为 P e , P o P_e,P_o Pe​,Po​。
butterfly的计算过程为 P e + P o , w ( P e − P o ) P_e +P_o, w(P_e-P_o) Pe​+Po​,w(Pe​−Po​),而这个过程又是递归的。所以考虑这样的过程:
0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 order by even and odd 0 , 2 , 4 , 6 , 1 , 3 , 5 , 7 order by even and odd 0 , 4 , 2 , 6 , 1 , 5 , 3 , 7 \begin{aligned} 0,1,2,3,4,5,6,7\\ \text{order by even and odd}\\ 0,2,4,6,1,3,5,7\\ \text{order by even and odd}\\ 0,4,2,6,1,5,3,7 \end{aligned} 0,1,2,3,4,5,6,7order by even and odd0,2,4,6,1,3,5,7order by even and odd0,4,2,6,1,5,3,7​
所以最后的结果会是一个bit reversal的结果。

上一篇:MATALB断点颜色变灰色


下一篇:CF1291A Even But Not Even 题解