Efficient Address Generation for Prime Factor Algorithms

The prime factor algorithms (PFA’s) are a class of fast algorithms for important digital signal processing operations such as discrete Fourier transform (DFT), number theoretic transform (NTT), and discrete Hartley transform (DHT). Address generation schemes used in PFA’s may take up more than 60% of their total computation time. In this paper, we try to explain as clearly as possible the problem of address generation and how the prime factor mapping (PFM) technique is used in this class of algorithms. Two novel address generation schemes are then proposed to improve efficiency. The first scheme reduces the computation required for unscrambling data in an in-place realization of PFA by reducing the number of variables used to calculate the data addresses. The second scheme is to be used in an inplace in-order realization of the PFA. It achieves high efficiency by replacing complicated modulo operations of conventional approaches by simple indirect addressing techniques. Making use of this new scheme, software packages have been written for the computation of DFT’s, using a high level language and two low level languages (80286/ 287 assembly language and TMS320C25 assembly language). Results of these realizations show that a reduction of 50% in address generation time is achievable and this gives a saving of 30% in total computation time. A hardware address generator is also developed. This generator may provide clues to improving digital signal processor architectures in the future.