OVERFLOW DETECTION AND CORRECTION TECHNIQUES IN RNS ARITHMETIC COMPUTATIONS

Abstract

There is speed limitation on hardware built on Weighted Number Systems (WNS) due to carry propagation. In recent years, attempts have been made to circumvent the speed limitation imposed on WNS in arithmetic operations by investigating into number systems such as Residue Number System (RNS) which has special carry characteristics for parallel computations. RNS is carry-free in nature and is able to support parallel and high speed arithmetic such as addition and multiplication. Overflow detection is one of the difficult operations of RNS; but overflow can lead to the representation of incorrect values in the RNS system ifnot detected. Schemes that will be able to detect and correct overflow during arithmetic operations will boost research in the RNS. This thesis presents three schemes for detecting and correcting overflow in RNS arithmetic computations such addition: Two efficient algorithms for RNS overflow detection and correction for a generalised moduli set {2an - 1,2an, 2an + 1}, a = 1,2, ... is presented. By taking a = 1, the algorithms are applied to the popular moduli set {2n - 1, 2n, 2n + 1} for implementation and comparison. This is done by first devising a novel technique based on the Chinese Remainder Theorem (CRT) and another based on the Mixed Radix Conversion (MRC) method by performing partial RNS-binary conversion. The other technique also based on the MRC for the reverse conversion is applied on the moduli set {22n+1 - 1,2n + 1,2n 1} with a redundant modulus 2, which assists in detecting overflow during addition operations in the given moduli set. All the proposed schemes are able to prevent the representation of illegitimate numbers in the RNS system as if they were legitimate numbers thus correcting overflow. The schemes are demonstrated theoretically to be more efficient than similar state-of-the art schemes.