FFT 码位倒序(Bit-Reversal)可视化证明
通过递归地按奇偶分组,元素的最终位置由其分组路径决定。该路径恰好是其原始索引的二进制倒序。
蓝色箭头 (左)
: 偶数位分组 (路径记为 '0')
橙色箭头 (右)
: 奇数位分组 (路径记为 '1')
0
1
2
3
4
5
6
7
0
2
4
6
1
3
5
7
0
4
2
6
1
5
3
7
0
倒序: 000
正序: 000
4
倒序: 001
正序: 100
2
倒序: 010
正序: 010
6
倒序: 011
正序: 110
1
倒序: 100
正序: 001
5
倒序: 101
正序: 101
3
倒序: 110
正序: 011
7
倒序: 111
正序: 111