Effective reverse conversion in residue number system processors
Kazeem Alagbe Gbolagade · Data Archiving and Networked Services (DANS) · 2010
I n this dissertation, we propose effective Residue Number System (RNS) to Weighted Number System conversion techniques.This research follows the two traditional conversion methods: the Mixed Radix Conversion (MRC) and the Chinese Remainder Theorem (CRT).In the first line of research, we investigate two MRC based techniques with k being the number of moduli.First, we introduce an RNS to MRC technique, which addresses the computation of Mixed Radix Digits in such away that enables the MRC parallelization.This scheme results in an RNS to MRC with an asymptotic complexity, in terms of arithmetic operations, in the order of O(k).Second, we generalize a previously proposed technique that was restricted to 5-moduli set such that it can be utilized in conjunction with any RNS with the set of relatively prime integer moduli {m 1 , m 2 , m 3 , ..., m k }.Just like the first scheme, this second technique also results in an RNS to MRC with an asymptotic complexity, in terms of arithmetic operations, in the order of O(k).In the second line of research, we propose a number of efficient converters based on the simplification of the traditional CRT.First, we assume a general {m 1 , m 2 , m 3 , ..., m k } moduli set, where m 1 > m 2 > m 3 > ... > m k , with the dynamic range M = k i=1 m i and introduce a modified CRT that requires mod-m k instead of mod-M calculations.Subsequently, we further simplify the conversion process by focusing on moduli sets with common factors, i.e., {2n + 2, 2n + 1, 2n} and {2n + 3, 2n + 2, 2n + 1, 2n}.Additionally, for the moduli set {2n + 2, 2n + 1, 2n}, we propose further simplifications which result in a scheme that does not even require explicit modulo operation computation.Second, for the {2n + 1, 2n, 2n -1} moduli set, we propose a novel converter, which also doesn't require explicit modulo operation computation during the conversion processes.Third, we propose two efficient memoryless reverse converters for the {2 n+1 -1, 2 n , 2 n -1} moduli set.Fourth, we propose two efficient adder based reverse converters for the {2 2n+1 -1, 2 n , 2 n -1} moduli set.Finally, two CRT and one MRC based reverse converters are proposed for the moduli set {2 2n+1 -1, 2 2n , 2 n -1}.Experimental results indicate that our proposals substantially outperform state of the art equivalent converters in terms of area, delay, and power consumption.