HP Labs Technical Reports

Click here for full text: Postscript PDF

Bit Reversal on Uniprocessors

Karp, Alan H.



Abstract: Many versions of the Fast Fourier Transform require a reordering of either the input or the output data that corresponds to reversing the order of the bits in the array index. There has been a surprisingly large number of papers on this subject in the recent literature. This paper collects 30 methods for bit reversing an array. Each method was recoded into a uniform style in Fortran and its performance measured on several different machines, each with a different memory system. This paper includes a description of how the memories of the machines operate to motivate two new algorithms that perform substantially better than the others.

Back to Index

[Research] [News] [Tech Reports] [Palo Alto] [Bristol] [Japan] [Israel] [Site Map] [Home] [Hewlett-Packard]