Hacker News new | ask | show | jobs
by RodgerTheGreat 4707 days ago
A common approach for performing a Fast Fourier Transform involves reversing the bits in time-domain samples.
2 comments

Expanding slightly, there’s a permutation that needs to happen in order to efficiently perform a DFT in-place (and the same approach is often used even when the transform is out-of-place). For power of two sizes (one of the most common cases), that permutation is precisely the same as a bit reversal of the indices.
Reversing the bits in the index to the samples :-)