Efficient Address Generation for Prime Factor Algorithms

Kar Lik Wong, Raymond Chan, Pak Kong Lun, Wan Chi Siu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

6 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)1518-1528
Number of pages11
JournalIEEE Transactions on Acoustics, Speech, and Signal Processing
Volume38
Issue number9
DOIs
Publication statusPublished - 1 Jan 1990

ASJC Scopus subject areas

  • Signal Processing

Cite this