Vector Radix Fast Fourier Transform,
MASSACHUSETTS INST OF TECH CAMBRIDGE RESEARCH LAB OF ELECTRONICS
Pagination or Media Count:
A new radix-2 two-dimensional direct FFT is generalized in this paper to include arbitrary radices and non-square arrays. It is shown that the radix-4 version of this algorithm may require significantly fewer computations than conventional row-column transform methods. Also, the new algorithm eliminates the matrix transpose operation normally required when the array must reside on a bulk storage device. It requires the same number of passes over the array on bulk storage as efficient matrix transpose routines, but produces the transform in bit-reversed order. An additional pass over the data is necessary to sort the array if normal ordering is desired.
- Theoretical Mathematics
- Computer Programming and Software