A new approach to fixed-coefficient inner product computation over finite rings

摘要

Inherently parallel arithmetic based on the residue number system (RNS) lends itself very well to implementation of high-speed digital signal processing (DSP) hardware. In most cases, DSP computations can be decomposed to the inner product form Y=/spl Sigma//sub i=0//sup N-1/C/sub i/X/sub i/. Therefore, implementation of the inner product computation over finite rings is of paramount importance for RNS-based DSP hardware. Recently, periodic properties of residues of powers of 2 have been found useful in designing residue arithmetic circuits. This paper presents a deeper insight to the periodicity concepts by applying abstract algebra and number theory methods. Advantage is taken of the fact that the set Z/sub m//sup +/={1, 2, ..., m-1} splits completely, with respect to some g/spl isin/Z/sub m//sup +/, into sets which are closed under multiplication by g modulo m. Properties of such a decomposition of Z/sub m//sup +/ are investigated and the theory is applied to develop new fixed-coefficient inner product circuits for finite-ring arithmetic. The new designs are almost exclusively composed of full adders and they can easily be pipelined to achieve very high throughput. A VLSI implementation study of the new inner product circuits is presented. It shows that, compared with the best method known to date, both smaller area requirements and higher throughput are achieved.