----------------------------------------------
|          TECHNICAL REPORT ECE-95-2           |
|                  April 1995                  |
| Dept. of Electrical and Computer Engineering |
|           University of Victoria             |
 ----------------------------------------------

TITLE:   VLSI Design Methodologies for computing $X \bmod m$

AUTHORS: R. Sivakumar and N. J. Dimopoulos

ABSTRACT

The feasibility of implementing Residue Number System (RNS) 
based arithmetic processors has been motivated by the recent 
developments in microelectronics. In this report, new VLSI 
architectures are proposed for computing the integer modulo 
operation $X \bmod m$ when $m$ is restricted to the values 
$2^k,2^{k}\pm 1$ and composite numbers whose mutually prime 
factors fall in the above category. Two different design 
methodologies, namely, the recursive and partition methods 
are presented and their respective VLSI computational 
complexities are analyzed. A VLSI chip that computes 
$X \bmod m$ where $X$ is a $16$-bit number and $m=3,5,6,7,9$ 
and $10$ has been implemented using the proposed schemes in 
$3 \mu m$ CMOS technology and typical measurements have 
yielded a propagation delay of less than 109ns.