关于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的结果。