The Implementation of Fast Radix 2 Transforms on Array Processors
- 1 January 1980
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-29 (1) , 20-27
- https://doi.org/10.1109/tc.1980.1675452
Abstract
Methods of implementing fast radix 2 transforms on array processors are considered. The complexity of arithmetic and data routing operations is analyzed for the methods given. It is shown that all methods give an O(P) speed-up in the arithmetic operations for a P processor array. However the methods incur an overhead in data organization. Theorems are presented that prove one method to be superior in minimizing this overhead for transforms of length N > P.Keywords
This publication has 6 references indexed in Scilit:
- Some Results Concerning Data Routing in Array ProcessorsIEEE Transactions on Computers, 1980
- The solution of elliptic partial differential equations using number theoretic transforms with application to narrow or limited computer hardwareComputer Physics Communications, 1977
- Number theoretic transforms to implement fast digital convolutionProceedings of the IEEE, 1975
- Fast Convolution using fermat number transforms with applications to digital filteringIEEE Transactions on Acoustics, Speech, and Signal Processing, 1974
- ILLIAC IV Software and Application ProgrammingIEEE Transactions on Computers, 1968
- An Algorithm for the Machine Calculation of Complex Fourier SeriesMathematics of Computation, 1965