A unified fast recursive algorithm for data shuffling in various orders

Data shuffling in a particular order is frequently required in signal processing applications. The authors present fast recursive algorithms, of order O(N), for shuffling a data sequence in various orders, e.g. bit reversed, Gray code, and other related orders, under a unified framework. These algorithms are computationally efficient in that every permutation index is essentially computed by a single logical or arithmetic operation between a previous index and a proper offset. The proposed algorithms can be used for the fast Fourier transform, fast Hartley transform, and mutual conversion among three typical forms of the Walsh transform