The bit-reverse operation used in FFT algorithm is a permutation operation. The following table shows the bit-reverse operation used in an eight-point FFT computation. Find a permutation matrix P such that: y(binary) = Px(binary)
| x Decimal |
x Binary |
y Bit-reverse |
y Decimal |
| 0 |
000 |
000 |
0 |
| 1 |
001 |
100 |
4 |
| 2 |
010 |
010 |
2 |
| 3 |
011 |
110 |
6 |
| 4 |
100 |
001 |
1 |
| 5 |
101 |
101 |
5 |
| 6 |
110 |
011 |
3 |
| 7 |
111 |
111 |
7 |