FFT 码位倒序(Bit-Reversal)可视化证明

通过递归地按奇偶分组,元素的最终位置由其分组路径决定。该路径恰好是其原始索引的二进制倒序。

蓝色箭头 (左): 偶数位分组 (路径记为 '0') 橙色箭头 (右): 奇数位分组 (路径记为 '1')
01234567
0246
1357
04
26
15
37
0
倒序: 000
正序: 000
4
倒序: 001
正序: 100
2
倒序: 010
正序: 010
6
倒序: 011
正序: 110
1
倒序: 100
正序: 001
5
倒序: 101
正序: 101
3
倒序: 110
正序: 011
7
倒序: 111
正序: 111