Bit Reversal on Uniprocessors
作者： Alan H. Karp
DOI: 10.1137/1038001
关键词: Reversing 、 Bit (horse) 、 Computer data storage 、 Hierarchical control system 、 Parallel computing 、 Fast Fourier transform 、 Algorithm 、 Computer science 、 Vector processor 、 Array data structure 、 Fortran 、 Theoretical computer science 、 Applied mathematics 、 Computational mathematics
摘要: Many versions of the fast Fourier transform require a reordering either input or output data that corresponds to reversing order bits in array index. There has been surprisingly large number papers on this subject recent literature.This paper collects 30 methods for bit an array. Each method was recoded into uniform style Fortran and its performance measured several different machines, each with memory system. This includes description how memories machines operate motivate two new algorithms perform substantially better than others.
core.ac.uk
sci-hub.se 参考文章(23)
J.J. Rodriguez, An improved bit-reversal algorithm for the fast Fourier transform international conference on acoustics speech and signal processing. pp. 1407- 1410 ,(1988) , 10.1109/ICASSP.1988.196862
Thomas J. Watson IBM Research Center, On Estimating and Enhancing Cache Effectiveness languages and compilers for parallel computing. pp. 328- 343 ,(1991) , 10.1007/BFB0038674
H. H. Wang, On vectorizing the fast fourier transform Bit Numerical Mathematics. ,vol. 20, pp. 233- 243 ,(1980) , 10.1007/BF01933196
Oscar Buneman, Conversion of FFT’s to Fast Hartley Transforms SIAM Journal on Scientific and Statistical Computing. ,vol. 7, pp. 624- 638 ,(1986) , 10.1137/0907042
R. Singleton, A method for computing the fast Fourier transform with auxiliary memory and limited high-speed storage IEEE Transactions on Audio and Electroacoustics. ,vol. 15, pp. 91- 98 ,(1967) , 10.1109/TAU.1967.1161906
Alan Edelman, Optimal matrix transposition of bit reversal on hypercubes: all-to-personalized communication Journal of Parallel and Distributed Computing. ,vol. 11, pp. 328- 331 ,(1991) , 10.1016/0743-7315(91)90039-C
David G. Korn, Jules J. Lambiotte, Computing the Fast Fourier Transform on a vector computer Mathematics of Computation. ,vol. 33, pp. 977- 992 ,(1979) , 10.1090/S0025-5718-1979-0528051-4
Donald Fraser, Bit reversal and generalized sorting of multidimensional arrays Signal Processing. ,vol. 9, pp. 163- 176 ,(1985) , 10.1016/0165-1684(85)90143-4
P. Duhamel, A connection between bit reversal and matrix transposition: hardware and software consequences IEEE Transactions on Acoustics, Speech, and Signal Processing. ,vol. 38, pp. 1893- 1896 ,(1990) , 10.1109/29.103090
David H. Bailey, FFTs in external or hierarchical memory The Journal of Supercomputing. ,vol. 4, pp. 23- 35 ,(1990) , 10.1007/BF00162341