Using redundant number representations for efficient VLSI implementation of modular arithmetic

The VLSI implementation of multiplication is usually achieved as an addition of partial products. Recent research has proposed the use of redundant number representations (RNR) to limit the carry propagation inherent within these additions, enabling high-speed multiplier designs. Multiplication over a modulus is often accomplished by interleaving the partial product additions with a modular adjustment to prevent word growth. However, for moduli other than 2^N or 2^N±1, this modular adjustment complicates the multiplier structure, requiring asymmetrical feedback or extra additions. This complication arises because the binary data is represented using consecutive powers of 2 (canonical basis). In this paper, an initial basis conversion of the data is proposed. Conventional binary logic is retained but consecutive bits now represent consecutive powers of β (a β-basis)