Research Journal of Recent Sciences _________________________________________________ ISSN 2277-2502 Vol. 1(7), 83-86, July (2012) Res.J.Recent Sci. International Science Congress Association 83 Short Communication An Efficient Residue to Binary Converter for the New Two-Level Moduli Set {22n {2 ,2n+1 -1},2 -1, 2 +1}Safi Seyyed Mohammad, Rashno MeysamAbedi ParvinKaboli Mina and Safi Fatemeh Sadat1 Department of Computer Engineering, Ahvaz branch, Islamic Azad University, Ahvaz, IRAN Department 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 2012Abstract In this paper a new two-level four moduli set {22n {2, 2n+1–1}, 2 –1, 2 +1} is introduced and an efficient residue to binary converter is proposed for it. This moduli set contains the moduli set {22n, 2 –1, 2 +1} in its first-level and the moduli set {2, n+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 algorithms. 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, 2, 2 –1}, {22n, 2 –1, 2n+1 –1} and {2, 22n –1, 22n +1}, 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 {2 –1, 2, 2 +1, 2n+1 –1} and {2 –3, 2 –1, 2+1, 2+3}6 have been presented. Since moduli set {2–1, 2, 2 +1, 2n+1 –1} has appropriate moduli, it has a more efficient RNS arithmetic unit compared to moduli set {2 –3, 2–1, 2+1, 2+3}. Hosseinzadeh et al have decreased the delay of reverse converter for moduli set {2 –1, 2, 2 +1, 2n+1 –1}. However, a little more hardware has been applied. In this paper, an improved residue to binary converter is proposed for moduli set {2 –1, 2, 2 +1, 2n+1 –1} by converting it into a two-level moduli set in the form of {22n {2, 2n+1 –1}, 2–1, 2 +1} such that its residue to binary converter has lower delay and hardware cost in comparison to the proposed converters for {2 –1, 2, 2 +1, 2n+1 –1} and {2 –1, 2, 2 +1, n+1 –1} . Material and MethodsThe RNS is based on a moduli set { m,…, m} which consists of pairwise relatively prime numbers. The dynamic range is defined as M m. Each weighted number X has a unique representation in RNS as ( x,…, x) where: = mod = , ฃ (1) By using CRT, the RNS number ( x,…, x) can be converted into its equivalent weighted number as (2)Where: , , and . By using CRT-1, the reverse conversion can be done as 2311121223212311()()() n nnnn mmm Xxmkxxkmxxkmmmxx---=+-+-++- (3) Where: , 1 ,1. 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, Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502Vol. 1(7), 83-86, July (2012) Res. J. Recent Sci. International Science Congress Association 84 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 {2{2, 2+1–1}, 2 –1, 2 +1}: the CRT-1 for these two moduli requires only one multiplicative inverse as (4) The T =(11 x12) can be obtained by substituting the value of , and moduli 11 = 2 m12 = 2+1 in (3) as shown below 121111111211(2 (5) To calculate which is the corresponding residue of = 22n, since the value of is in 0 m span and the value of is in 0 m11 m12 span and with respect to this reality that m m11 m12 , therefore below equation is used. ifif 1211 (6) The simplification of (5) can be performed with considering the point that, by expressing in bits, 21 2kpix - and 21 kix - are equivalent to bits circular left shifting of , and one’s complement of , respectively. The residues can be represented at bit-level by: 11 = (11,-1,…, 11,1, 11,0) and 12 = (12,n,…, 12,1, 12,0). Therefore, (5) can be rewritten as 11 (7) (8) 11 11111,111,111,011,111,111,0 2121 22(0)1 nnnnsxxxxxxx--=-=-=  (9) 11 21212,12,112,012,112,112,012, 21112122() nnn nnsxxxxxxxx++===  (10) By substituting (9) and (10) in (8), is obtained as a (n+1)-bits number. For calculating , it is sufficient to concatenate 11 to . 0,111,1111 = (11) According to (11) equations (12) and (13) are concluded. 1211 ifif = (12) (13) With respect to (12) and (6) is obtained as follow 0,111,1111 = (14) For the values greater than = 22n and based on (11) and (13), is equal to 0,111,1111 = (15) The binary representation of = 22n can be shown as 00000000 (16) By substituting (15) and (16) in (6), is obtained as 0,111,1111 = (17) Since has the same value for 0 m and m1112, the most significant bit of can be ignored as shown below 0,111,1111 = (18) By calculating and using residues x and , the residue to binary converter for the first-level moduli set {2, 2 –1, 2 +1} is designed. Residue to Binary converter for the moduli set {22n, 2 –1, 2+1} based on CRT: according to (2) and by assuming m = 22n, = 2 –1 and m = 2 +1 we have )12(, )12(, )12( and )12( (19) Considering (19) the required multiplication reverses for (2) are computed as follows )12( (20) 1 221 2(21)12 n nnn kk - ด+=ฎ= (21) )12( (22) The binary vectors x, x and x can be represented in bit-level as x = (Hn –1,…, H, H, x11n –1,…, x11, x11) , = ( xn –1,…, x, x) and x = ( x ,…, x, x). Now, (2) can be rewritten as (23) Where: is an integer number and depends on the value of X. By replacing (25)-(22) in (23) we have )12()12()12()1)12( (24) By dividing both sides of (24) by 22n we have Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502Vol. 1(7), 83-86, July (2012) Res. J. Recent Sci. International Science Congress Association 85 ( ) l )12()12()12( 2 (25) and calculating the floor values in modulo (22n –1) results in the following )12()12()12()12()12()12( (26) In this case, the number X can be computed by the following (27) Eq. (26) can be rewritten as )12(5251 (28) 0,111,1111)12( = 0,111,1111 (29) 0,21,2,20000(2(2(1,2,20,21,2,20,2 (30) 0,31,3,3510000(1,3,30,30000 (31) 0,31,3,3520000( 0,31,3,31111 (32) The hardware implementation of residue to binary converter for the two-level moduli set {2 {2, 2+1 –1}, 2 –1, 2 +1} is illustrated in Figure-1. The required hardware consists of NOT gates in operand preparation unit 1 (opu1) which are used for calculating equation (9). To implement (8), a modulo (2+1 –1) adder is required. In this paper a (+1)-bits carry propagate adder (CPA) with end around carry (EAC) is used to satisfy it. Opu2 contains (3+1) NOT gates to calculate equations (29) and (32). Equation (28) is implemented by applying two 2-bits carry-save adders (CSA) with EAC and one 2-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 with 22n X \r \r  without any extra hardware. Results and DiscussionsIn Table-1 the performance of the proposed residue to binary converter for the moduli set {22n {2, 2n+1 –1}, 2 –1, 2 +1} has been compared with converters for {2 –1, 2, 2 +1, 2n+1 –1}and {2 –1, 2, 2 +1, 2n+1 –1} 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 tFAdenotes 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 {2 –1, 2, 2 +1, 2n+1–1} and {2 –1, 2, 2 +1, 2n+1 –1} moduli sets. AcknowledgementThis paper has been derived from Seyyed Mohammad Safi research plan in Islamic Azad university Ahvaz branch. ConclusionThis paper presents an efficient two-level design of reverse converter for the new two-level moduli set {2 {2, 2+1 –1}, 2–1, 2 +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. References1.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 ,2 –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,2 –1,2n+1 –1} and {22n,2 –1,2n–1 –1}, IEICE TRANS. INF. & SYST., 92(9), 42-51 (2009) Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502Vol. 1(7), 83-86, July (2012) Res. J. Recent Sci. International Science Congress Association 86 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 {2 –1,2n ,2 +1,2n+11} and {2 –1,2,2 +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 {2 –3,2 –1,2+1 ,2+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 {2 –1, 2, 2 +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) 3 X 2 X 1 X 12 X 11 X 1 X   X 2 n 2 n 2 n 2 n 2 n 1 n + 1 n + 1 n + 1 n + n n n 2 n Operand proparation Unit 1 Operand proparation Unit 2 2n-bit CSA1 with EAC 2n-bit CSA2 with EAC 2n 2n-bit CPA2 with EAC (Modulo (21)Adder) n+1 (n+1)-bit CPA1 with EAC (Modulo (21)Adder) - () b () a Figure- 1 The proposed residue to binary converter: (a) second-level (b) first-level Table-1 Performance Comparison Converter Area Unit Gate Area Delay Unit Gate Delay [5]-CI (9n+5+k*)AFA+(2n)AXNOR+(2n)A OR +(6n+1)A NOT (129n+7n 2 )/2 +4((23n+12)/2)tFA46n [7](10n+6+k*)AFA+(6n+2)AXNOR+(6n+2)AOR+(7n+2)ANOT+(n+3)A MUX21 +(2n+1)A MUX3 - 1 (193n+7n)/2 +50 ((15n+22)/2)tFA 30n Proposed (5n+3)AFA+(n+1)AXOR+(n+1)AAND+(n+1)AXNOR+(n+1)AOR+(4n+1)ANOT(47n+30) (6n+4)tFA+2tNOT 24n * k= (n-4)*(n+2)/2