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=Σ_i=0^N-1 C_iX_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_m⁺={1, 2, ..., m-1} splits completely, with respect to some g∈Z_m⁺, into sets which are closed under multiplication by g modulo m. Properties of such a decomposition of Z_m⁺ 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