Abstract

In this study, we investigate Residue Number System (RNS) to binary conversion, which is an important issue concerning the utilization of RNS numbers in Digital Signal Processing (DSP) applications. We present a Mixed Radix Conversion (MRC) technique for efficient RNS to binary conversion. First, we show that the computation of the required multiplicative inverses can be eliminated. Next, we propose an adder based RNS to binary converter, which requires mod-(2ⁿ-1) or mod-(2^n-1-1) instead of mod-(2ⁿ) (2^n-1-1) required by other state of the art Chinese Remainder Theorem (CRT) based equivalent converters. The proposed converter outperforms CRT based equivalent state of the art converters in terms of both speed and area. Consequently, due to the fact that our scheme operates on smaller magnitude operands, it results in less complex adders, which potentially results in faster implementation.

---

INTRODUCTION

There is no ordering significance between the digits in Residue Number System (RNS). The result of any operation such as addition, subtraction or multiplication depends solely on the corresponding digits of its operands. This parallel property accounts for the inherent carry free property of the RNS, which makes RNS to be very useful in addition and multiplication dominated Digital Signal Processing (DSP) applications such as digital filtering, correlation, convolution, fast fourier transform and image processing. However, the following are the disadvantages of RNS: magnitude comparison, overflow detection, sign detection, moduli selection and data conversion. For RNS advantages not to be nullified by its disadvantages, an effective data converter is required. The research on residue to binary conversion is based on either the Chinese Remainder Theorem (CRT), (Van Vu, 1985; Elleithy and Bayoumi, 1992; Ahmad and Hoda, 1998; Wang, 1998; Ahmad et al., 2003; Amir and Keivan, 2007; Gbolagade and Cotofana, 2008) or Mixed Radix Conversion (MRC) (Huang, 1983; Chakraborti et al., 1986; Yassine, 1991, 1999; Yassine and Moore, 1991). CRT is desirable because the computation can be parallelized while MRC is by its very nature a sequential process. However, many RNS-Binary converters are based on MRC due to the complex and slow modulo-M operation (M being the system dynamic range thus a rather large constant) required by CRT. The major problem with the MRC is that the computations of the MR digits is done in a serial manner and requires a large number of arithmetic operations. In this study, we present a memoryless reverse converter. First, we show that the computation of the multiplicative inverses can be eliminated. Next, we employ shifting property to eliminate the involved multipliers. The proposed converter outperforms equivalent CRT based reverse converter in terms of both area and speed.

MATERIALS AND METHODS

RNS is defined in terms of a set of relatively prime integers (m_i)_{i = 1, n} such that gcd (m_i, m_j) = 1 for i≠j, where gcd means greatest common divisor of m_i and m_j. For such a system

is the dynamic range and any integer X ε (0, M-1) can be uniquely represented as X = (x₁, x₂, x₃, …, x_n), where, x_i = |X|m_i, 0≤x_i<m_i. We note here in this study, that we use x_i = |X|_mi to denote the X mod m_i operation and the operator ⊗ to represent the operation of addition, subtraction and multiplication. Given any 2 integer numbers K and L RNS represented by K = (k₁, k2, k3, …, k_n) and L = (l₁, l₂, l₃,…, l_n), respectively. W = K ⊗ L,

can be calculated as W = (w₁, w₂, w₃, …, w_n), where, w_i = |k_i ⊗ l_i|_mi, for i = 1 to n. This actually means that the complexity of the calculation of the ⊗ operation is determined by the number of bits required to represent the residues and not by the one required to represent the input operands. Using MRC, the reverse conversion can be formulated as follows (Szabo and Tanaka, 1967). Suppose that an n-digit RNS number X = (x₁, x₂, x₃, …, x_n) with the set of relatively prime integer moduli set (m₁, m₂, m₃, …, m_n), determine the Mixed Radix Digits (MRD) (a₁, a₂, a₃, …, a_n) such that the Eq. 1 holds true:

X = a1 + a2m1 + a3m1m2 + … + anm1m2m3…mn-1

(1)

The MRD can be computed as follows Yassine and Moore (1991):

(2)

Apart from parallelizing the MRC technique, the usage of special moduli sets such as (2ⁿ + 1, 2ⁿ, 2ⁿ - 1), (2ⁿ, 2ⁿ - 1, 2^n-1 - 1), (2n + 1, 2n, 2n - 1) etc., results in a further simplification of the MRC technique. In the following study, we simplify the MRC technique using the moduli set (2ⁿ, 2ⁿ - 12^n-1 - 1).

PROPOSED ALGORITHM

Given the RNS number (x₁, x₂, x₃) with respect to the moduli set (m₁, m₂, m₃) in the form (2ⁿ, 2ⁿ-1, 2^n-1-1), the proposed algorithm computes the binary equivalent of this RNS number using MRC technique. First, we demonstrate that the computation of the multiplicative inverses can be eliminated for this moduli set. Next, we present a memory less MRC technique.

Theorem I: Given the moduli set (2ⁿ, 2ⁿ-12^n-1-1) with m₁ = 2ⁿ, m₂ = 2ⁿ-1, m₃ = 2^n-1-1, the following hold true:

(3)

(4)

(5)

Proof: If it can be demonstrated that |m₁X₁|_m2 = 1, then 1 is the multiplicative inverse of m₁ with respect to m₂.

thus, Eq. 3 holds true.

In the same way, if it can be shown that |m₂X₁|_m3 = 1, then 1 is the multiplicative inverse of m₂ with respect to m₃. |(2ⁿ - 1)X1|₂^n-1_-1 putting y = 2ⁿ, we obtain

thus, Eq. 4 holds true.

Again, if it can be proved that |m₁X2^n-2|_m2 = 1, then 2^n-2 is the multiplicative inverse of m₁ with respect to m₃. |2ⁿ(2^n-2)|₂^n-1_-1, putting y = 2ⁿ, we obtain

thus, Eq. 5 holds true.

Next, we assume a moduli set of length 3 for Eq. 2 and by substituting Eq. 3-5, we obtain the following expressions:

(6)

where:

(7)

In order to clarify this algorithm, let us convert (7, 1, 0)_{RNS (8|7|3)} to decimal.

Hence,

X = 7+1X8 +0X8X7 = 15

as it should.

In order to further reduce the hardware complexity, we use the following properties Amir and Keivan (2007):

•	Modulo (2p-1) multiplication of a residue number by 2q, where, p and q are positive integers, is equivalent to q bit circular left shifting

•	Modulo (2p-1) of a negative number is accomplished by subtracting this number from (2p-1). This is equivalent to taking one’s compliment of the number

If the residues x₁, x₂ and x₃ have binary representations as Eq. 8-10:

x1 = (x1, n-1x1, n-2…x1, 1x1, 0)

(8)

x2 = (x2, n-2x2, n-3…x2, 1x2, 0)

(9)

x3 = (x3, n-3x3, n-4…x3, 1x3, 0)

(10)

The multiplier in a₃ in Eq. 7 and of course all the multipliers in Eq. 6 can be eliminated by using the above properties. We start by showing the binary representation of a₁ and a₂.

a1 = (x1, n-1x1, n-2…x1, 1x1, 0) a2 = |u1 + u2|2n-1

where:

u1 = (x2, n-2x2, n-3…x2, 1x2, 0) u2 = - (x1, n-1x1, n-2…x1, 1x1, 0)

Also, a₃ in Eq. 7 can be written as:

a3 = |u3 + u4|2n-1

Using the properties stated above, we have

Also,

Hardware implementation of the proposed residue to binary converter for the moduli set (2ⁿ+1, 2ⁿ, 2^n-1-1) is based on the computation of u₁, u₂, u₃ and u₄. It is made up of 3n-bit full adders together with modulo (2ⁿ-1) and (2^n-1-1) adders which can be implemented using different methods. Using n-bit and (n-2)-bit one’s compliment adders, the performance of the proposed converter can be significantly improved but this is left as a subject of future investigation.

RESULTS AND DISCUSSION

The proposed converter is a novel converter, which is dedicated to the moduli set (2ⁿ, 2ⁿ-1, 2^n-1-1). A converter, which is better than equivalent existing converters has been presented by Ahmad and Hoda (1998). Thus, we compare our proposal with this best state of the art equivalent converter. The converter presented by Ahmad and Hoda (1998) requires 1 adder, 3 subtractors and 1 comparator, whereas our proposal requires only three adders. In terms of area, our proposal is better than the best state of the art converter. Delay wise, the proposed converter requires (t_n + t_n-1) whereas the converter given by Ahmad and Hoda (1998) requires (2t_n-1 + t_2n-1). This implies that the proposal is faster than the best state of the art converter. Figure 1 depicts the implementation, the converter in Ahmad and Hoda (1998), while Fig. 2 shows the implementation of the proposed converter. Table 1 and 2, respectively, show the hardware requirements and performance comparison of this proposal and the one in Ahmad and Hoda (1998). Clearly, it can be seen that this proposal is better in terms of area and delay than the known best state of the art equivalent converter.

 

Fig. 1:	Hardware implementation of Ahmad and Hoda (1998)

 

 

Fig. 2:	Hardware implementation of the proposed converter

 

 

Table 1:	Comparison of hardware requirements

 

 

Table 2:	Comparison of delay

 

CONCLUSION

In this study, we investigated RNS to binary conversion, which is an important issue concerning the utilization of RNS numbers in DSP applications. We presented an MRC technique for efficient RNS to binary conversion. First, we demonstrated that the computation of the required multiplicative inverses can be eliminated. Next, we proposed an adder based RNS to binary converter, which requires only 3, 2-1 adders and mod- (2ⁿ-1) and mod-(2^n-1-1) instead of mod- (2ⁿ) (2^n-1-1) required by other state of the art CRT based equivalent converters. Also, in terms of delay, this proposal requires (t_n + t_n-1). The proposed converter outperforms CRT based equivalent state of the art converters in terms of both speed and area. Consequently, due to the fact that our scheme operates on smaller magnitude operands, it results in less complex adders, which potentially results in faster implementation. The performance of the proposed converter can be significantly improved using n-bit and (n-2)-bit one’s compliment adders but this is left as a subject of future investigation.

How to cite this article:

Kazeem Alagbe Gbolagade . A Memoryless MRC Technique for RNS-to-Binary Conversion Using The Moduli Set (2ⁿ, 2ⁿ-1, 2^n-1-1).
DOI: https://doi.org/10.36478/ijscomp.2009.127.130
URL: https://www.makhillpublications.co/view-article/1816-9503/ijscomp.2009.127.130