This paper explores an architecture for parallel independent computations of inner products over the direct product ring /spl Rfr//sub 257/spl times/17/. The structure is based on the polynomial mapping of the Modulus Replication RNS for calculations over dynamic ranges much larger than the product of the computational moduli. We show that the computational ring is optimal for our purposes, and introduce basic cells for the efficient calculation of all elements of the polynomial ring computations.

Presents a new multivariate mapping strategy for the recently introduced Modulus Replication Residue Number System (MRRNS). This mapping allows computation over a large dynamic range using replications of extremely small rings. The technique maintains the useful features of the MRRNS, namely: ease of input coding; absence of a Chinese Remainder Theorem inverse mapping across the full dynamic range; replication of identical rings; and natural integration of complex data processing. The concepts are illustrated by a specific example of complex inner product processing associated with a radix-4 decimation in time fast Fourier transform algorithm. A complete quantization analysis is performed and an efficient scaling strategy chosen based on the analysis. The example processor uses replications of three rings: modulo-3, -5, and -7; the effective dynamic range is in excess of 32 b. The paper also includes very-large-scale-integration implementation strategies for the processor architecture that consists of arrays of massively parallel linear bit-level pipelines.>

A finite polynomial ring structure for mapping inner product computations to parallel independent ring computations over 3-b moduli has been introduced by N.M. Wigley et al. (1992). The main algorithmic computation architecture can be implemented using well-established systolic array mapping principles, and a project to construct a Polynomial Ring Engine (PRE) is underway to exploit the VLSI implementation properties of such computations. A semi-systolic architecture for the input and output conversion mappings that are required in the engine is introduced here. It is shown that the entire mappings procedure can be carried out with pipelined six-input logic blocks and small, fast, binary adders. CMOS implementation techniques for the pipelined blocks are discussed, and the design procedure is illustrated with results from a recently completed module generator.>

The authors describe mapping, scaling, and conversion processes using a new mapping strategy for the modulus replication residue number system (MRRNS). The strategy allows direct mapping of bits of either a purely real or multiplexed bit coded complex number to a set of independent rings, defined by moduli 3, 5, and 7. The MRRNS technique is superior to a large QRNS system operating with a computational dynamic range of over 27 b. A classical radix-4 implementation of a 1024 FFT is used for the comparison. The scaling and conversion procedure is shown to be a set of finite ring calculations followed by an array of ordinary binary adders. The VLSI implementation of the most complex finite ring circuit required (a Mod 7 multiplier) is shown to be easily implemented using the switching tree approach, and mask extracted simulations at 50 MHz demonstrate the embedding of the switching trees in a dynamic pipeline/evaluate circuit with restoring latch.>

The disadvantage of computations using finite rings is the need to compute over many different rings in order to produce useful dynamic ranges of computation. By mapping integers into polynomial rings, one can replace the different rings by the replication of the same ring with considerable computational advantages. The authors present the methodology of such a mapping strategy, and discuss the application of the features of the technique to dense fabrication strategies such as WSI and ULSI, where redundancy is an integral part of the architecture. It is shown that all of the operations can be performed by the recently introduced bit-steered ROM technique, with attendant advantages of easy testability and fault detection. The polynomial mapping strategy allows the extra advantage of low-overhead redundancy when general computational blocks are employed.>

A technique is presented for coding weighted magnitude components (e.g. bits) of numbers directly into polynomial residue rings, such that repeated use may be made of the same set of moduli to effectively increase the dynamic range of the computation. This effectively limits the requirement for large sets of relatively prime moduli, For practical computations over quadratic residue rings, at least 6-bit moduli have to be considered. It is shown that 5-bit moduli can be effectively used for large dynamic range computations.>