Efficiency of the Residue Number System for Computing Discrete Fourier Transforms
Abstract
In this thesis the residue number, or RNS, is analyzed in detail and compared against a conventional two's complement system for the problem of computing Discrete Fourier Transforms (DFTs) via the Winograd Fourier Transform Algorithm (WFTA). The analysis shows that in a side-by-side comparison, the size and speed advantages of RNS cannot compensate for the high overhead required for conversion and scaling. The residue number system, or RNS, is a system of representing integers by their remainders, or residues, after division by a predetermined set of relatively prime integers. Operations such as addition, subtraction, and multiplication can be performed with modular arithmetic on these residues in independent channels, such that it is a carry-free system. RNS can exploit efficient ROM layouts by building arithmetic units out of ROMs. The main disadvantage of RNS is that scaling and conversion back to RNS require a lengthy series of operations. The WFTA is found to be the best algorithm for doing DFTs in RNS because it reduces the need for scaling by nesting the necessary multiplications into one layer, such that there is only one layer of coefficients that increase the range of the output data. (kr)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1990
- Accession Number
- ADA227685
Entities
People
- Thomas P. Dennedy
Organizations
- Air Force Institute of Technology