A multiplier-free fast transform with efficient VLSI implementation for polynomial RNS processors

The application of polynomial residue number systems (PRNSs) in complex multiplication offers very low complexity within the digital signal processing area. Isomorphic mappings between complex number and PRNS domains suffer from a nontrivial transform problem which eventually precludes the inherent advantages of the PRNS approach. a significant simplification in the mapping procedure is achieved by a FFT-like scheme and a sequence of primitive shift-then-add operations. These operations originate from an algebraic congruence and a residue reduction of a Fermat prime within finite fields. An efficient custom VLSI implementation of the FFT-type multiplier-free system confirms the advantages of the novel mapping algorithm. The prototype VLSI design of a 5 bit multiplier-free FFT-type PRNS processor has been implemented using the Magic IC layout tool. In terms of speed, cost, and simplicity, the innovative approach of this new design outperforms the conventional systems currently in use