New algorithms and VLSI architectures for efficient RNS computations

• Main Author: Tay, Thian Fatt
• Other Authors: Chang Chip Hong
• Format: Theses and Dissertations
• Language: English
• Published: 2016
• Subjects: DRNTU::Engineering::Electrical and electronic engineering::Electronic circuits
• Online Access: https://hdl.handle.net/10356/66937
• Institution: Nanyang Technological University

Residue Number System (RNS) is a non-weighted number system emerging as a promising substitute of two's complement number system for data representation in high-speed and low-power digital signal processing. In RNS, arithmetic operations, such as addition, subtraction and multiplication, can be carried out at a faster speed due to the avoidance of carry propagation. Nonetheless, the arithmetic operations such as sign detection, scaling, base transformation and error decoding, are generally more difficult to be implemented in RNS. This thesis aims to tackle these difficult RNS operations by designing simple and efficient algorithms and architectures. In this thesis, a fast and area efficient 2^n signed integer RNS scaler for the moduli set {2^n−1, 2^n, 2^n+1} is proposed. The complex sign detection circuit has been obviated and replaced by simple logic manipulation of some bit-level information of intermediate magnitude scaling results. As a result, the proposed architecture achieves at least 21.6% of area saving, 28.8% of speedup and 32.5% of total power reduction compared to the state-of-art designs. In addition, a new concept of base transformation is introduced to reduce the overall arithmetic processing costs of multi-base RNS. The exploration into this new concept is motivated by the overkill of arithmetic operator sizes in RNS-based digital signal processors (DSPs) due to the choice of moduli set to accommodate for the occasional high precision operations. A new algorithm is proposed to directly map the residues of signed integers from one modulo-arithmetic friendly base S1 ≡ {2^n-1, 2^(n+k), 2^n+1} to another S2 ≡ {2^(n-α)-1, 2^(n+k-α), 2^(n-α)+1}, to reduce the word lengths of residue arithmetic operators by α bits. The proposed algorithm utilizes range quantization approach to avoid the complex reverse conversion and sign detection operations. The synthesis results show that its VLSI implementation efficiency, in terms of area-delay product and energy consumption, outperforms the best possible improvised solution. Furthermore, two new algorithms for the correction of single and multiple residue digit errors in Redundant Residue Number System (RRNS) are presented in this thesis. These algorithms involve a fixed number of syndrome computations of to locate the erroneous residue digits. They compare favourably against existing residue digit correction algorithms involving iterative computations as their required computation times are more predictable and thus, they are amenable to hardware implementation.