P. Duhamel, Implementation of "split-radix", FFT algorithms for complex, real, and real-symetric data, IEEE Trans. on ASSP, vol.34, issue.2, pp.803-816, 1984.

M. Vetterli and H. J. Nussbaumer, Simple FFT and DCT algorithms with reduced number of opérations, Signal Processing, vol.6, pp.267-278, 1984.

J. B. Martens, Recursive cyclotomic factorization : A new algorithm for calculating the DFT, SIAM CBMS-NSF séries, vol.32, pp.750-761, 1980.

P. Duhamel, Algorithms meeting the lower bounds on the multiplicative complexity of length-2n DFT's and their connection with practical algorithms, IEEE Trans. on ASSP, vol.38, pp.1504-1511, 1990.

M. T. Heideman and C. S. Burrus, On the number of multiplications necessary to compute a length-2n DFT, IEEE Trans ASSP, vol.34, pp.91-95, 1986.

C. Rader and N. Brenner, A new principle for Fast Fourier Transform, IEEE Trans. on ASSP, vol.24, pp.264-265, 1976.

C. H. Papadimitriou, Optimality of the Fast Fourier Transform, J. Ass

. Comput and . Mach, , vol.26, pp.95-102, 1979.

H. Sorensen, M. T. Heideman, and C. S. Burrus, On computing the splitradix FFT, IEEE Trans on ASSP, vol.34, issue.1, 1986.

C. S. Burrus, A Duhamel-Hollman split-radix DIF FFT (Ref : Electronics letters, 1984.

P. Duhamel, Un algorithme de transformation de Fourier rapide à double base, Annales des télécommunications, vol.40, 1985.

P. Duhamel and M. Vetterli, Improved Fourier and Hartley Transform

, Algorithms Application to Cyclic Convolution of Real Data, IEEE Trans on ASSP, vol.35, issue.6, 1987.

P. Duhamel, B. Piron, and J. M. Etcheto, On Computing the Inverse DFT, IEEE Trans on ASSP, vol.36, issue.2, pp.285-286, 1988.

A. A. Yong, A Better FFT Bit-Reversal Algorithm Without Tables, IEEE Trans on ASSP, vol.39, issue.10, pp.2365-2367, 1991.

J. W. Cooley and J. W. Tukey, An algorithm for machine computation of complex Fourier séries, Math Comput, vol.19, pp.297-301, 1965.

C. M. Rader and N. M. Brenner, A new principle for fast Fourier transformation, IEEE Trans. Acoust., Speech, Signal Processing, vol.24, pp.264-265, 1976.

K. M. Cho and G. C. Ternes, Real-factor FFT algorithms, Proc. IEEE ICASSP, pp.634-637, 1978.

R. D. Preuss, Very fast computation of the radix-2, discrète Fourier transform, IEEE Trans. Acoust., Speech, Signal Processing, vol.30, pp.595-607, 1982.

H. J. Nussbaumer, Fast Fourier Transform and Convolution Algorithm, 1981.

H. Johnson and C. S. Burrus, Twiddle factors in the radix-2 FFT, Proc. 1982 Asilomar Conf. Circuits Syst., Comput, pp.413-416, 1982.

S. Winograd, On the multiplicative complexity of the discrète Fourier transform, Adv. Math, vol.32, pp.83-117, 1979.

C. S. Burrus and P. W. Eschenbacher, An in-place, in-order prime factor FFT algorithm, IEEE Trans. Acoust., Speech, Signal Processing, vol.29, pp.806-817, 1981.

L. R. Morris, Automatic génération of time efficient digital signal processing software, IEEE Trans. Acoust., Speech, Signal Processing, vol.25, pp.74-79, 1977.

S. Winograd, On computing the discrète Fourier transform, Math. Comput, vol.32, pp.175-199, 1978.

P. Duhamel and H. Hollmann, Split-radix FFT algorithm, Electron. Lett, vol.20, pp.14-16, 1984.

R. Yavne, An economical method for calculating the discrète Fourier transform, AFIPS Proc, vol.33, pp.115-125, 1968.

M. Vetterli and H. J. Nussbaumer, Simple FFT and DCT algorithms with reduced number of opérations, Signal Processing, vol.6, pp.267-278, 1984.

Z. Wang, Fast algorithms for the discrète W transforms and the discrète Fourier transform, IEEE Trans. Acoust., Speech, Signal Processing, vol.32, pp.803-816, 1984.

J. B. Martens, Recursive cyclotomic factorization-A new algorithm for calculating the discrète Fourier transform, IEEE Trans

. Acoust, Discrète Fourier transform algorithms for reai valued sé-quences, Speech, Signal Processing, vol.32, pp.390-396, 1984.

G. D. Bergland, A fast Fourier transform algorithm for real-valued séries, Commun

, ACM, vol.11, pp.703-710, 1968.

H. Ziegler, A fast Fourier transform algorithm for symmetric realvalued series, IEEE Trans. Audio Electroacoust, vol.20, pp.353-356, 1972.

P. Duhamel and H. Hollmann, Existence ofa 2"-FFT algorithm with a number of multiplications lower than 2, Electron. Lett, vol.20, pp.690-692, 1984.

M. J. Narasimha and A. M. Peterson, On the computation of the discrète cosine transform, IEEE Trans. Commun, vol.26, pp.934-936, 1978.

L. R. Morris, Digital signal processing software, 1982.

M. Vetterli, FFT's of signais with symmetries and application to autocorrelation computation, 1985.

M. T. Heideman and C. S. Burrus, Multiply/add tradeoff in length-2" FFT algorithms, vol.85, pp.780-783, 1985.

P. Duhamel, Implementation of split-radix FFT algorithms for complex, real, and real-symmetric data, IEEE Trans. Acoust., Speech. Signal Processing, vol.24, issue.2, pp.285-295

L. R. Morris, Digital signal processing software, 1983.

M. Vetterli and P. Duhamel, Split-radix algorithms for length-p'" DFT's, IEEE Trans. Acoust.. Speech, Signal, Processing, vol.37, issue.1, pp.57-64, 1989.

D. M. Evans, An improved digit-reversal permutation algorithm for the fast Fourier transform and Hartley transform, IEEE Trans

. Acoust, Speech, Signal Processing, pp.1120-1125, 1987.

R. J. Polge, B. K. Bhaganan, and J. M. Carswell, Fast computational algorithms for bit reversal, IEEE Trans. Comput, pp.1-9, 1974.

J. O. Eklundh, A fast computer method for matrix transposing, IEEE Trans. Comput, pp.801-803, 1972.

C. S. Burrus and T. W. Parks, DFT/FFTand Convolution Algorithms, 1985.

Z. J. Mou and P. Duhamel, In-place butterfly style FFT of 2-D real séquences, IEEE Trans. Acoust.. Speech, Signal Processing, vol.36, issue.10, pp.1642-1650, 1988.

J. J. Johnson, R. Rodriquez, and . Tolimieri, A methodology for designing, modifying, and implementing Fourier transform algorithms on various architectures

, Pierre Duhamel (M'87-SM'87) was bom in France in 1953. He received the Ingenieur degree in electrical engineering from the National Institute for Applied Sciences (INSA), Rennes. France. in 1975. the Dr. Ing. degree in 1978, and the Doctorat es Sciences in 1986, both from Orsay UniFrom 1975 to 1980 he was with Thom

J. W. Cooley and J. W. Tukey, An algorithm for the machine calculation of complex Fourier séries, Math. Comput, vol.19, pp.297-301, 1965.

R. D. Preuss, Very fast computation of the radix 2 discrète Fourier transform, IEEE Trans. Acoust., Speech, Signal Processing, pp.595-607, 1982.

G. D. Bergland, A fast Fourier transform algorithm for real-valued series, Commun. ACM, vol.11, pp.703-710, 1968.

H. Ziegler, A fast Fourier transform algorithm for symmetric realvalued series, IEEE Trans. Audio Electroacoust, vol.20, pp.353-356, 1972.

J. B. Martens, Discrète Fourier transform algorithms for real-valued sequences, IEEE Trans. Acoust., Speech, Signal Processing, pp.390-396, 1984.

M. Vetterli and H. J. Nussbaumer, Simple FFT and DCT algorithms with reduced number of opérations, Signal Processing, vol.6, pp.267-278, 1984.

P. Duhamel, Implementation of split-radix FFT algorithms for complex, real, and real-symmetric data, IEEE Trans. Acoust., Speech, Signal Processing, vol.34, pp.285-295, 1986.

R. N. Bracewell, The fast Hartley transform, Proc. IEEE, vol.22, pp.1010-1018, 1984.

H. V. Sorensen, D. L. Jones, C. S. Burrus, and M. T. Heideman, On computing the discrète Hartley transform, IEEE Trans. Acoust., Speech. Signal Processing, issue.33, pp.1231-1238, 1985.

P. Duhamel, Un algorithme de transformation de Fourier rapide à double base, Ann. Télécommun, vol.40, pp.481-494, 1985.

M. Vetterli and H. J. Nussbaumer, Algorithmes de transformation de Fourier et en cosinus mono et bi-dimensionnels, Ann. Télécom-mun, vol.40, pp.466-476, 1985.

H. V. Sorensen, M. T. Heideman, and C. S. Burrus, On computing the split-radix FFT, IEEE Trans. Acoust., Speech, Signal Processing, vol.34, pp.152-156, 1986.

R. C. Agarwal and C. S. Burrus, Fast convolution using Fermât number transform with application to digital filtering, IEEE Trans

A. .. Speech, Signal Processing, pp.87-97, 1974.

R. Ansari, An extension of the discrète Fourier transform, IEEE Trans. Circuits Syst, pp.618-619, 1985.

S. Pei and J. Wu, Split-radix fast Hartley transform, Electron. Lett, vol.22, pp.26-27, 1986.

L. R. Morris, Automatic génération of time efficient digital signal processing software, IEEE Trans. Acoust., Speech, Signal Processing, vol.25, pp.74-79, 1977.

P. Duhamel, M'87) was bom in France in 1953. He received the Ingénieur degree in electrical engineering from the National Institute for Applied Sciences

. Ing, 1978, and the Doctorat es Sciences in 1986 from Orsay University, France. From 1975 to 1980 he was with Thomson-CSF

F. Paris, where his research interests were in circuit theory and signal processing. including digital filtering and automatic analog fault diagnosis, He is now working on fast convolution algorithms, including number theoretic transforms and fast Fourier transforms

M. Vetterli,

S. On-acoustics and . Signal-processing, , vol.36, p.285, 1988.

L. R. Rabiner and B. Gold, Theory and Application of Digital Signal Processing, 1975.

E. 0. Brigham, The Fasl Fourier Transform, 1974.

C. S. Burrus and T. W. Parks, DFT/FFT and Convolution Algorithms, 1985.

P. Duhamel, A Better FFT Bit-Reversal Aigorithm Without Tables Angelo A. Yong Abstract-The bit-reversai counteralgorithm of Gold and Rader bit reverses a continuous séquence of N numbers by running a loop N -1 times, IEEE Trans. Acoust., Speech, Signal Processing, pp.285-295, 1986.

, its author obtains a small improvement of the bit-reversal counteralgorithm (BRCA), Fig. 1, by reducing the upper limit of the counter from N -2 to N -1 ? square root (rN), where N = 2 and "r" equals 1 for an even E or 2 if E is odd; the relative savings reported for N = 128 is 8.5 %. In part II, a faster BRCA is proposed. The working storage of the BRCA does not dépend on N and it may become insignificant, The need for an efficient bit-reversal algorithm for the fast Fourierand Hartley transforms, using a radix

. Ii and . An, EFFICIENT Bit-Reversal PROCEDURE The initial step, to improve the algorithm, cornes from the observation that given a couple of numbers (/, J ), where / is an even Manuscript received August 11, 1990; revised April 17, 1991. The author is with the Department of Electronics, IEEE Log Number 9101869

B. Gold and C. M. Rader, Digital Processing of Signais, 1969.

R. J. Polge, B. K. Bhagavan, and J. M. Carswell, Fast computational algorithms for bit reversai, IEEE Trans. Comput, issue.1, pp.1-9, 1974.

D. M. Evans, An improved digit-reversal permutation algorithm for the fast Fourier and Hartley transforms, IEEE Trans. Acousl., Speech, Signal Processing, vol.35, pp.1120-1125, 1987.

J. J. Rodriguez, An improved FFT digit-reversal algorithm, IEEE Trans. Acoust., Speech, Signal Processing, vol.37, pp.1298-1300, 1989.

J. S. Walker, A new bit reversai algorithm, IEEE Trans. Acoust., Speech, Signal Processing, vol.38, pp.1472-1473, 1990.