Short Communication An Efficient Residue to Binary Converter for the New Two-Level Moduli Set {22n {2n ,2n+1 -1},2n -1, 2n +1} Safi Seyyed Mohammad1, Rashno Meysam1, Abedi Parvin2, Kaboli Mina1 and Safi Fatemeh Sadat1 1Department of Computer Engineering, Ahvaz branch, Islamic Azad University, Ahvaz, IRAN 2Department of Computer Engineering, Ahvaz branch, Islamic Azad University, Shoushtar, IRAN Available online at: www.isca.in Received 9th May 2012, revised 12th May 2012, accepted 19th June 2012 Abstract In this paper a new two-level four moduli set {22n {2n, 2n+1-1}, 2n -1, 2n +1} is introduced and an efficient residue to binary converter is proposed for it. This moduli set contains the moduli set {22n, 2n -1, 2n +1} in its first-level and the moduli set {2n, 2n+1 -1} in its second-level for the modulo 22n.The reverse converter for this moduli set is implemented in two-level structure, which is designed based on Chinese remainder theorem (CRT) and the new CRT-1 methods. The proposed residue to binary converter for this moduli set improves the hardware cost and delay significantly in comparison to the similar previously presented moduli sets. Keywords: Reverse converter, residue arithmetic, VLSI architecture. Introduction The residue number system (RNS) is a carry-free number system, which can be used as a method for high-speed and low-power implementation of digital signal processing (DSP) computation algorithms1. The residue to binary conversion is very important and complex part of an RNS system. The complexity of the residue to binary converter is mainly based on moduli set. Up to now, many moduli sets have been presented with various dynamic ranges (DR) such as {2n+1 -1, 2n, 2n -1}2, {22n, 2n -1, 2n+1 -1}3 and {2n, 22n -1, 22n +1}4, which have dynamic ranges equal to 3n, 4n and 5n-bits respectively. Some applications require large dynamic ranges with high parallelism. Therefore, four-moduli sets {2n -1, 2n, 2n +1, 2n+1 -1}5 and {2n -3, 2n -1, 2n+1, 2n+3}6 have been presented. Since moduli set {2n -1, 2n, 2n +1, 2n+1 -1} has appropriate moduli, it has a more efficient RNS arithmetic unit compared to moduli set {2n -3, 2n -1, 2n+1, 2n+3}. Hosseinzadeh et al have decreased the delay of reverse converter for moduli set {2n -1, 2n, 2n +1, 2n+1 -1}7. However, a little more hardware has been applied. In this paper, an improved residue to binary converter is proposed for moduli set {2n -1, 2n, 2n +1, 2n+1 -1} by converting it into a two-level moduli set in the form of {22n {2n, 2n+1 -1}, 2n -1, 2n +1} such that its residue to binary converter has lower delay and hardware cost in comparison to the proposed converters for {2n -1, 2n, 2n +1, 2n+1 -1}5 and {2n -1, 2n, 2n +1, 2n+1 -1}7 . Material and Methods The RNS1 is based on a moduli set {m1, m2,..., mn} which consists of pairwise relatively prime numbers. The dynamic range is defined as M = m1m2...mn. Each weighted number X < M has a unique representation in RNS as (x1, x2,..., xn) where: mod = , (1) By using CRT, the RNS number (x1, x2,..., xn) can be converted into its equivalent weighted number as (2) Where: , , , and . By using CRT-1, the reverse conversion can be done as (3) Where: , . In two-level RNS for each desired modulo at the first-level a moduli set at the second-level must be chosen in such a way that its dynamic range be equal or greater than the desired modulo at the first-level. In two-level RNS, arithmetic operations are performed on the residues of second-level moduli. Afterward, for converting from RNS to binary system, the residues of the second-level are converted to corresponding residues at the first-level. Then, recently obtained residues are converted to binary system. Residue to binary converter for the two-level moduli set {22n {2n, 2n+1-1}, 2n -1, 2n +1}: the CRT-1 for these two moduli requires only one multiplicative inverse as (4) The T =(x11, x12) can be obtained by substituting the value of k, and moduli m11 = 2n, m12 = 2n+1 in (3) as shown below (5) To calculate x1 which is the corresponding residue of m1 = 22n, since the value of x1 is in 0 = x1 < m1 span and the value of T is in 0 = T < m11× m12 span and with respect to this reality that m1 = m11× m12 , therefore below equation is used. (6) The simplification of (5) can be performed with considering the point that, by expressing xi in k bits, and are equivalent to p bits circular left shifting of xi, and one's complement of xi, respectively1. The residues can be represented at bit-level by: x11 = (x11,n-1,..., x11,1, x11,0) and x12 = (x12,n,..., x12,1, x12,0). Therefore, (5) can be rewritten as (7) (8) (9) (10) By substituting (9) and (10) in (8), H is obtained as a (n+1)-bits number. For calculating T, it is sufficient to concatenate x11 to H. (11) According to (11) equations (12) and (13) are concluded. With respect to (12) and (6) is obtained as follow (14) For the values greater than m1 = 22n and based on (11) and (13), T is equal to (15) The binary representation of m1 = 22n can be shown as (16) By substituting (15) and (16) in (6), x1 is obtained as (17) Since x1 has the same value for 0 = T < m1 and m1 = T < m11× m12, the most significant bit of x1 can be ignored as shown below (18) By calculating x1 and using residues x2 and x3, the residue to binary converter for the first-level moduli set {22n, 2n -1, 2n +1} is designed. Residue to Binary converter for the moduli set {22n, 2n -1, 2n +1} based on CRT: according to (2) and by assuming m1 = 22n, m2 = 2n -1 and m3 = 2n +1 we have , , and (19) Considering (19) the required multiplication reverses for (2) are computed as follows (20) (21) (22) The binary vectors x1, x2 and x3 can be represented in bit-level as x1 = (Hn -1,..., H1, H0, x11,n -1,..., x11,1, x11,0) , x2 = ( x2,n -1,..., x2,1, x2,0) and x3 = ( x3,n ,..., x3,1, x3,0). Now, (2) can be rewritten as (23) Where: l is an integer number and depends on the value of X. By replacing (25)-(22) in (23) we have (24) By dividing both sides of (24) by 22n we have (25) and calculating the floor values in modulo (22n -1) results in the following (26) In this case, the number X can be computed by the following (27) Eq. (26) can be rewritten as (28) = (29) = (30) (31) (32) The hardware implementation of residue to binary converter for the two-level moduli set {22n {2n, 2n+1 -1}, 2n -1, 2n +1} is illustrated in Figure-1. The required hardware consists of n NOT gates in operand preparation unit 1 (opu1) which are used for calculating equation (9). To implement (8), a modulo (2n+1 -1) adder is required. In this paper a (n+1)-bits carry propagate adder (CPA) with end around carry (EAC) is used to satisfy it. Opu2 contains (3n+1) NOT gates to calculate equations (29) and (32). Equation (28) is implemented by applying two 2n-bits carry-save adders (CSA) with EAC and one 2n-bits CPA with EAC. Some of the used full adders (FA) in CSA1 and CSA2 are reduced with pair of XOR/AND and XNOR/OR gates, because equations (31) and (32) have some bits with constant values 0 or 1. Equation (27) is computed by concatenating x1 with without any extra hardware. Results and Discussions In Table-1 the performance of the proposed residue to binary converter for the moduli set {22n {2n, 2n+1 -1}, 2n -1, 2n +1} has been compared with converters for {2n -1, 2n, 2n +1, 2n+1 -1}5 and {2n -1, 2n, 2n +1, 2n+1 -1}7 from both hardware cost and delay viewpoints. As shown in figure-1, the delay of opu1 and opu2 are equal to one NOT gate and CSA 1 and CSA2 have the delay of one full adder. In addition, the delay of CPA1 and CPA2 is equal to (2n+2)tFA and (4n)tFA respectively, where tFA denotes the delay of a full adder (FA). For a better comparison, the unit gate model is considered to obtain total area and delay estimations. Based on this model, each two-input monotonic gate counts as one gate in area and delay, an XOR/XNOR gate counts as two gates in area and delay, and an FA has area of seven gates and delay of four gates. The corresponding total unit gate area and delay are presented in table-1. According to the results of table-1, our proposed residue to binary converter has significant reduction in both delay and hardware cost in comparison to the converters presented for {2n -1, 2n, 2n +1, 2n+1 -1}5 and {2n -1, 2n, 2n +1, 2n+1 -1}7 moduli sets. Acknowledgement This paper has been derived from Seyyed Mohammad Safi research plan in Islamic Azad university Ahvaz branch. Conclusion This paper presents an efficient two-level design of reverse converter for the new two-level moduli set {22n {2n, 2n+1 -1}, 2n -1, 2n +1} based on combination of CRT and New CRT-1. Comparison with the similar four-moduli residue to binary converters show that the proposed design is faster and requires less hardware area. References 1. Omondi A. and Premkumar B., Residue Number Systems: Theory and Implementations, Imperial College Press, London (2007) 2. Mohan P.V.A., RNS-To-Binary Converter for a New Three-moduli Set {2n+1 -1,2n ,2n -1} , IEEE trans. Circuits Syst., 54(9), 775-779 (2007) 3. Sabbagh A., Dadkhah C.H., Navi K. and Eshghi M., Efficient MRC-Based Residue to Binary Converters for the New Moduli Sets {22n,2n -1,2n+1 -1} and {22n,2n -1,2n-1 -1}, IEICE TRANS. INF. & SYST., 92(9), 42-51 (2009) 4. Hariri A., Navi K. and Restegar R., A new high dynamic range moduli set with efficient reverse converter, Elsevier J. com and Math, 55(4), 660-668 (2008) 5. Mohan P.V.A. and Premkumar A.B., RNS-to-Binary Converters for Two Four-Moduli Set {2n -1,2n ,2n +1,2n+1-1} and {2n -1,2n,2n +1,2n+1+1}, IEEE Trans. Circuits syst. I, 54(6), 1245-1254 (2007) 6. Mohan P. V. A., New reverse converters for the moduli set {2n -3,2n -1,2n+1 ,2n+3}, Elsevier J. Electron. Commun., 62(9), 643-658 (2008) 7. Hosseinzadeh M., Sabbagh A. and Navi K., An improved reverse converter for the moduli set {2n -1, 2n, 2n +1, 2n+1 -1}, IEICE Elect. Exp, 5(17), 672-677 (2008) 8. Mewada Shivlal and Singh Umesh Kumar, Performance Analysis of Secure Wireless Mesh Networks, Researh J. Recent Sci., 1(3), 80-85 (2012) 9. Molahosseini A., Navi K., Hashemipour O. and A. Jalali, An efficient architecture for designing reverse converters based on a general three moduli set, Elsevier J. Systems Architecture, 54(10), 929-934 (2008) 10. Wang W., Swamy M. N. S., Ahmad M. O. and Wang Y., A Study of the Residue-to-Binary Converters for the Three-Moduli Sets, IEEE Trans. Circuits and Syst-II, 40(2), 235-243 (2003) 11. Piestrak S.J., A high speed realization of a residue to binary converter, IEEE Trans. Circuits and Syst-II, 42(10), 661-663 (1995) 1. Figure- 1 The proposed residue to binary converter: (a) second-level (b) first-level Table-1 Performance Comparison ConverterAreaUnit Gate AreaDelayUnit Gate Delay[5]-CI(9n+5+k*)AFA+(2n)AXNOR +(2n)AOR+(6n+1)ANOT(129n+7n2)/2 +4((23n+12)/2)tFA46n[7](10n+6+k*)AFA+(6n+2)AXNOR +(6n+2)AOR+(7n+2)ANOT +(n+3)AMUX21+(2n+1)AMUX3-1(193n+7n2)/2 +50((15n+22)/2)tFA30nProposed (5n+3)AFA+(n+1)AXOR +(n+1)AAND+(n+1)AXNOR +(n+1)AOR+(4n+1)ANOT(47n+30)(6n+4)tFA+2tNOT24n * k= (n-4)*(n+2)/2 Research Journal of Chemical Sciences _______________________________________________________ ISSN 2231-606X Vol. 1(5), 1-7, Aug. (2011) Res.J.Chem.Sci. International Science Congress Association 8 Research Journal of Recent Sciences _________________________________________________ ISSN 2277-2502 Vol. 1(7), 83-86, July (2012) Res.J.Recent Sci. International Science Congress Association 83 Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502 Vol. 1(7), 83-86, July (2012) Res. J. Recent Sci. International Science Congress Association 84 Research Journal of Chemical Sciences________________________________________________ ISSN 2231-606X Vol. 1(5), 1-7, Aug. (2011) Res.J.Chem.Sci International Science Congress Association 5