Premium
A new superfast bit reversal algorithm
Author(s) -
Rubio M.,
Gómez P.,
Drouiche K.
Publication year - 2002
Publication title -
international journal of adaptive control and signal processing
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.73
H-Index - 66
eISSN - 1099-1115
pISSN - 0890-6327
DOI - 10.1002/acs.718
Subject(s) - bit (key) , fast fourier transform , algorithm , property (philosophy) , surprise , computer science , constant (computer programming) , homomorphism , arithmetic , mathematics , discrete mathematics , psychology , social psychology , philosophy , computer security , epistemology , programming language
In this paper we present a new bit reversal algorithm which outperforms the existing ones. The bit reversal technique is involved in the fast Fourier transform technique (FFT), which is widely used in computer‐based numerical techniques for solving numerous problems. The new approach for computing the bit reversal is based upon a pseudo‐semi‐group homomorphism property. The surprise is that this property is almost trivial to prove but at the same time it also leads to a very efficient algorithm which we believe to be the best with only ( N ) operations and optimal constant, i.e. unity. Copyright © 2002 John Wiley & Sons, Ltd.