TELKOM NIKA , Vol.11, No .11, Novemb er 201 3, pp. 6577 ~6 583   e-ISSN: 2087 -278X           6577      Re cei v ed Ap ril 23, 2013; Revi sed  Jun e  20, 2013; Accepted July 2 1 ,  2013   An Efficient Reverse C onverter for The New High  Dynamic Range 5-Moduli Set      Xiaolan L v *,  Ming Xiao  Coll eg e of Co mputer an d Ele c tronic Informa tion, G uan gdo ng Un iversit y  o f  Petrochemica l  T e chnolog y,  Maomin g 52 50 00, Guan gdo n g ,   Chin a   *Corres p o ndi n g  author, e-ma i l : 2909 01 37@ q q .com       A b st r a ct   In this  pa per,  an  efficie n t re sidu e to  bi nar y conv erter  de sign  for th e  n e w  hig h   dyn a m ic  ra ng e   mo du li set {2 n -1 ,2 n +1 ,2 2n ,2 2n +1, 2 2n- 1 -1} is pr esente d . T he r e verse c onver sion i n  the fo u r-mo dul i set {2 2n ,  2 2n +1 , 2 n +1 , 2 n -1} has b een  p r opos ed i n  liter ature. Henc e, t he conv erters  are bas ed o n  the new  mod u li  set  {2 2n- 1 -1, (2 n -1)(2 n +1)(2 2n +1 )2 2n } and pr op ose i t s residue to  bi nary conv erter  usin g New  Chi nese R e ma ind e r   T heore m   2 (  N e w  CRT  2). T h e n e w  modu li  set are  pro pos ed w i th  a dy na mic  ran ge  8n- 1  bits a n d  has  th e   same fe atures  of the  po pul ar  on e. W hen  c o mpar ed to  th e co mmo n  fiv e  modu li r e vers e co nverters, t h is  enh anc ed  mod u li set has  mor e  dyna mic ran ge, and  it us eful for hig h  perf o rmanc e co mp uting.     Ke y w ords : reverse conv erte r ， residue n u m ber system (R NS), new  Chinese re main de r theore m s (n ew   CRT).     Copy right  ©  2013 Un ive r sita s Ah mad  Dah l an . All rig h t s r ese rved .       1. Introduc tion  The conve n tional weig hte d   num be r system  has  ca rry p r op agati on am ong  a r ithmetic  operation s , resultin g in pe rforma nce de grad ati on  in hard w a r e co mputing syst ems.  The re sidue   numbe r  sy ste m  (R NS) i s   a n  effi cient alt e rnative n u m ber  system  which  ha s be e n  an im porta nt  resea r ch field  in compute r   arithmeti c  for  many  de ca de s. On e of the  key adva n tag e s of  RNS is  a   carry-free nu mber  sy stem ,  whi c h ca n repre s e n t  nu mber in  a n o n -weighte d  f o rm.  High  sp eed   and le ss ha rd ware  compl e xity could be  achi ev ed by  decompo sin g  a large bi nary numbe r int o  a  set of small e r resi due s [1-3]. RNS ha s dra w n wi de sprea d  attention for in cre a s ing p e rfo r m ance  of com m uni cation sy stem,  Digital Sig n a l Pro c e ssi n g  such  a s  F ourie r tran sfo r m (FFT),  di gita l   filter, and ima ge pro c e s sin g .   The b a si c b u ilding bl ocks  for a  RNS  ne eded  re sidu e  arithmeti c  u n it, binary-to -redid u e   conve r ters, a nd re sid ue-to -bina r y co nverters [4 , 5]. Choi ce of t he mod u li set that inclu des  relatively pri m e intege rs  and de sig n s  of the  reverse co nverte r are imp o rta n t becau se th ese   issue s  have  basic effe cts on reve rse conv e r ter’ s perform an ce, they have long been  the   perfo rman ce  bottlene ck f o r RNS [8-1 5]. Another  i m porta nt arit hmetic p r obl em is  conve r ting  resi due to bi nary num ber,  which is the  cru c ial fo r  a RNS ap plication. The tradit i onal alg o rith ms  of reverse converte r are  Chine s e Re mainde r The o rem (CRT) and Mixed-radix co nversion   (MRC). Howe ver, the use of CRT is un profitable  sin c e it is involve a large mo dulo M ope ra tion,  whe r e M is th e prod uct of all moduli [6]. The MRC i s  a sequ ential  pro c e ss  whi c h requi re s times   [7]. Rece ntly, Wan g  ha s p r opo sed  Ne w  Chin ese Rem a inde r Th eorem 1 (Ne w   CRT I) a nd  Ne w   Chin ese Re m a inde r Th eorem 2 (Ne w  CRT II), whi c h  are b a sed o n  CRT  and  M RC [8]. The  Ne w  CRT s  algo rithm elimin ate s  the d r a w b a cks  of tr adit i onal  CRT  a nd M RC, resulting in n o ta ble  improvem ent in hard w a r e.    By far, many  different m o d u li sets  have  been  propo se d, whi c h  hav e different p r opertie s ,   whi c n acco rdi ng to dynami c  ran ge (DR),  arithmet ic op eration s  an d hard w a r e imp l ementation. In  some high -p erform an ce comp utation system s,  the y  demand  more p a rall e lism with la rger   dynamic  ran g e . A few of five-mo duli set  have bee n re ported, Sk avantzo s propo sed a  fi ve-m o duli  set  {2 n -1,2 n ,2 n +1, 2 n +2 (n+1)/2 +1, 2 n -2 (n+1)/2 +1} [9],  Math ew et al. al so pro p o s ed  a  fi ve-mod uli  set  {2 3n -1,2 3n ,2 n +1,2 3n +2 (3n+1)/2 +1, 2 3n -2 (3n+1)/2 +1} [10], they have the sa me  disa dvant age s that all the  moduli a r e  no t in the form  of 2 n  or 2 n ±1 ,  the multiplicative inverses  are in  poo r fo rmats,  re sulti n g   in the sp eed  of the arith m etic unit i s  re st ricte d . Skavant zo s an d Stouraiti s prop osed a  fi ve- Evaluation Warning : The document was created with Spire.PDF for Python.
                               e-ISSN: 2 087-278X   TELKOM NIKA  Vol. 11, No . 11, Novemb er 201 3:  657 7 – 6583   6578 moduli set  { 2 n+1 , 2 n -1, 2 n +1, 2 n+1 -1,2 n+1 +1}  [11], Ca o  et al. al so p r opo se d a  rel a tively balan ced  fi ve- m oduli set { 2 n -1,2 n , 2 n +1,  2 n+1 -1,2 n-1 -1} [12], though all the moduli are in the form of 2 n  or  2 n ±1 with thi s  two mod u li sets, they are  only co -pri me  for even val ues of  n  and dynamic ran g e   are only  5 n  bits , la rg er dyn a mic  rang e mo dul i  set s  are  necessa ry fo r large  num ber  comp utation s . A few of larger dyn a mic  rang e mo d u li  sets h a ve propo sed, which com p ri se s  non  c o -prime moduli [13].  In this paper,  we propo se a  resid ue to binary co nverte r desi gn ba se d on Ne w CRT I and  New CRT II  with our new  moduli  s e t {2 n -1,2 n +1, 2 2n ,2 2n +1, 2 2n-1 -1},  whi c h i s  valid  any value  of n.  These involvi ng mod u li of this mo duli  se t are in the fo rm of 2 n  or  2 n ±1, this  makes  the  c onverter  desi gn i n  le ss h a rdware   complexity. Th e p r op osed  moduli  set is de rived f r om  the m oduli   set  {2 2n , 2 2n +1,  2 n +1,  2 n -1 }  [14],  while  the dynamic ran ge has rai s ed  to 8 n -1  bits. A two-l e vel de si gn   of reverse converte r for the prop osed  m oduli set based on co mbination of  New Chine s e  Remai nde r T heorem 1  (New  CRT I)  an d Ne w  Ch i n e s e  Rem a ind e r  Th eorem 2   (Ne w   CRT II) is   pre s ente d .  The rest of  the pap er i s  org anized  as fo llo ws: In se ction  2, we p r ovid e  a bri e f  introdu ction  f o r th e  RNS s  and  Ne w CRTs. In  sectio n  3, the  ne w 5 - mod u li  set  is  propo se d,  and   an  efficient re verse co nvert e r  alg o rithm s  for  the  ne w fi ve-mod uli set  that base d  o n  Ne w CRT s   is   provide d . Ha rdwa re impl e m entation is  pre s ente d   in se ction 4. Evaluating the p r opo se d reve rse   conve r ter a n d  com pare th e re sult in te rms of  conve r sio n  del ay and ha rd ware co st with oth e r  simila r reve rse conve r ters i n  se ction 5. T he pap er is  concl ude d in section 6       2. Backg rou nd  In a re sid u e  numb e r  system (RNS),  an integ e r  X  can  be  defi ned by  a m oduli  set  { m 1 ,m 2 , ... ,m n }, which is  co nsi s ted of a  set of pairwise   relatively pri m e intege r n u mbe r s, i.e., gcd   ( m i , m j )=1 for  i ≠ j. The dyn a mic  rang e (DR) M is th e  prod uct of the mod u li, 1 n i i M m , A   weig hted re prese n tation  X  can b e  rep r e s ented a s   X =( x 1 , x 2 ,..., x n ), where:     mo d 1 , 2 , 0 i ii i i m x XX m i n x m                                (1)    Then integ e r  X  has a uniq u e  n-tuple  rep r ese n tion:  12 ,, 0 RN S n Xx x x X M   .                 Ne w Chin ese   Rem a ind e r  Theo rem 1 ( N e w  CRT   I)  [ 8 ]:  For a  m o duli set  { m 1 , m 2 , ... , m n },  the weighte d  number X can be co nverted  from its a set of resi due num ber  ( x 1 , x 2 ,..., x n ), it is   pre s ente d  usi ng Ne w CRT  I as:    23 1 12 1 2 2 3 2 11 12 3 1 1 () ( ) () nn nn n n mm m m kx x k m x x Xx m km m m x x            ( 2 )     Whe r e 23 1 3 1 3 1 11 2 1 2 2 1 2 1, 1 , , 1 nn nn nn m m mm m m m m mm km k m m k mm                 Ne w  Chin es e R e mai nde r  The o re m 2 ( Ne w  CR T II)  [8]: For  a  2 - mod u li  set  { m 1 ,m 2 },  whe r e  m 1 < m 2  . the weig hte d  numb e r  X   can be  co nvert ed from it s re sidu e re prese n tation ( x 1 ,x 2 ),  it can be re prese n ted by New CRT II as  follows:    1 22 0 1 2 () m Xx m k x x                                                                                                             (3)    1 02 1 m km                                                                                                                                              (4)    Whe r e,  k i  is t he multiplicative inverse.         Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   e-ISSN:  2087 -278X       An Efficient Reve rse Co nverter fo r The  Ne w  Hig h  Dynam ic Ran g e  5-Mod u li Set (Xiaolan L v )  6579 3. Rev e rse Conv erter to 5 - Moduli Set { 2 n -1,2 n +1,2 2n ,2 2n +1, 2 2n-1 -1}   In this sectio n, we apple t he Ne w CRT-I and the Ne w CRT- Ⅱ  to the prop osed  supe rset  {2 n -1,2 n +1, 2 2n ,2 2n +1, 2 2n-1 -1}   to achieve a high-perfo rmance re si d ue to binary  converte r, its  dynamic  ra ng e is 8 n -1  bits. We de note  the re sidu es  corre s p ondin g  to this mo d u li set ( m 1 ,  m 2 ,   m 3 ,  m 4 ,  m 5 ) as ( x 1 ,  x 2 ,  x 3 ,  x 4 ,  x 5 ).   A two-level  conversion  alg o rithm for th e  resi due to  bi nary conve r si on is  pre s e n ted. The  moduli  set  S={2 n -1,2 n +1,2 2n ,2 2n +1, 2 2n-1 -1} i s   de comp ose d  into  two  su bsets. i.e.,  S 1 ={2 2n , 2 2n +1,   2 n +1,  2 n -1} a nd  S 2 ={ 2 2n-1 -1,2 2n (2 n -1 )( 2 n +1) ( 2 2n +1)}.  From [14], the moduli set S 1 ={2 2n , 2 2n +1,   2 n +1,  2 n -1} a r e pai rwise p r ime  whe n   n  is valid for  any value. T her efo r e, it is necessa ry that  prove the all  moduli of S 1  are all pai rwise prime to the  moduli of 2 2n-1 -1 for any value of  n .   Theo rem 1:  The num be r of 2 n -1,2 n +1, 2 2n ,2 2n +1,and  2 2n-1 -1 are pairwi se  relativ e ly prime  for any value of  n .  Proof:  Acco rding to the Euclid’ s  The o rem gcd  ( a , b )= gc d( b , a  mod  b ), it is  easy to find.                         21 1 1 21 1 1 21 2 2 22 1 2 1 g c d 2 1, 2 1 g c d 2 1, 2 1 g c d 2 1, 1 1 2 1 , 2 1 2 1 , ( 2 1) ( 2 1) , 2 1 21 , 2 2 , 1 1 21 , 2 1 , 2 1 , 3 1 nn n n n nn n n n nn n nn n gc d g c d g c d gc d g c d gc d g c d                      (5)    It can  be  see n  that  all the   greate s t  com m on  di viso rs  are  eq ual to   1, therefore  t he fou r   numbe rs 2 n -1 ,2 n +1, 2 2n ,and 2 2n +1 are rela tively prime to the modulo  2 2n-1 -1.  At the beginn ing, we assu me that an integer  X 1   is re pre s ente d  as ( x 1 ,  x 2 ,  x 3 ,  x 4 ) based on th e  four-m oduli set  S 1 ={2 2n , 2 2n +1,  2 n +1,  2 n -1}. The  fi nal w e ig h t ed   X  can b e  calculated fro m  the  resi due s ( X 1 , x 5 ) corre s po n d  to the seco nd moduli  set  S 2 ={2 2n-1 -1, ( 2 n -1) ( 2 n +1) ( 2 2n +1) 2 2n }.  In the firs t level of the converter, A c c o rding  to th e  conve r si on  al gorithm  of [1 4], the  weigh t ed  X 1 =( x 1 ,  x 2 ,  x 3 ,  x 4 ) ca n be o b tained by:     2 11 2 n X xZ                                                                                                                        (6)    Z  is th e o u tpu t  of modu o 2 4n -1 ad de r, the r efore Z i s   a  4 n -bit i n tege r, then X 1  ha s  6 n  bit s .  In the se co n d  level of the  reverse  co n v erter, by ap plying (3 ) to  the moduli  set S 2 , S 2  can be  rewritten as :    2 2 21 2 4 21 2 2 ( 2 1 ) ( 2 1 )( 2 1 ), 2 1 ( 2 ( 2 1 ) , 2 1 ) n n nn n n nn S      (7)     X  can be  calculated by Ne w CRT- Ⅱ .    21 24 10 5 1 21 2( 2 1 ) ( ) n nn XX k x X                                                              (8)    L e mma   1 : Th e multiplicativ e inverse of the numb e r 2 2n (2 4n -1) m odu lo 2 2n-1 -1 is  k 0.     21 2 2 0 1 2( 2 1 ) 1 2 3 nn k                                                                                              (9)    Proof : Ac cording to (4), we have 21 24 0 21 2( 2 1 ) 1 n nn k  。                                                                                                    Then, (8 ) can  be rewritten  as:     21 24 2 1 2 2 1 51 21 1 2( 2 1 ) 2 ( 2 1 ) 1 2 ( ) 3 n nn n n XX x X        (10 )     Its origin al form of  k 0  is n o t amena ble to  hard w a r e d e s ign, the n  it is expa nded i n to geom etri cal  seri es.   Evaluation Warning : The document was created with Spire.PDF for Python.
                               e-ISSN: 2 087-278X   TELKOM NIKA  Vol. 11, No . 11, Novemb er 201 3:  657 7 – 6583   6580 2 1 0 246 2 2 1 [2(2 1 ) 1 ) ] 2 2 2 2 2 3 nn                                             (11)    Finally, the weighted X ca n  be rep r e s ent ed as follo w:       21 2 4 0 246 2 2 2 2 1 51 21 2 ( 2 1 ) ( 2 222 2 ) 2 ( ) n nn n n XX x X    (12 )       4. Hard w a re  Realization  of Rev e rse Conv erter  Hardware fra m e of the propo sed 5 - mo duli set S = {2 n -1,2 n +1, 2 2n ,2 2n +1, 2 2n-1 -1} r e v e rs e   conve r ter i s  shown Figu re  1.        Figure 1. Fra m e of the Pro posed  5-mod u li Set Reverse Converte r      Hardware implementatio n for intege r  X 1   from the re si due s ( x 1 ,  x 2 ,  x 3 ,  x 4 ) correspond to   the four-mod uli set S 1 ={2 2n , 2 2n +1,  2 n +1 ,  2 n -1} h a s  co mpleted by   [1 4]. The aim o f  this se ction  is  to implement  the hardware  architectu re o f   X  from the resid u e s  ( X 1 , x 5 ) corre s po n d  to the se co nd  moduli set S 2 ={2 2n-1 -1, (2 n -1) ( 2 n +1 )( 2 2n +1) 2 2n }. Figure  2 shows the architectu re o f  the residue  to   binary conve r ter for the 2-moduli set S 2 .          Figure 2. Architecture of Reverse Co nverter fo r the 2 - mod u li set S 2  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   e-ISSN:  2087 -278X       An Efficient Reve rse Co nverter fo r The  Ne w  Hig h  Dynam ic Ran g e  5-Mod u li Set (Xiaolan L v )  6581 The (1 2)  can  be re written a s :     24 1 2( 2 1 ) nn X XR                                                                                                    (13)    Whe r e:     21 21 21 21 0 2 22 22 0 2 22 51 1 2 21 2 1 22 22 15 2 1 21 2 1 (2 2 2 ) 2 ( ) (2 2 2 ) ( ) 2, 2 ( ) n n nn nn n nn Rx X r r rx r X            (14 )     No w, we  co nsid er Equ a tion (1 3) a nd  (14 ) , and  si mplify them for efficie n t hard w a r e  implement. Firs t, we  s h ow  two  L e mma s ,  they ca n b e   use d  to impl e m ent mod u lo  2 n -1 add er by  s i mply c i rcular s h ift.  L e mma   2 :  21 2 m n x is equivalent to  circula r  lef shi ft a  m -bits bin a ry  namb e r  x  by  n  bits  [12].  L e mma   3 :  21 2 m n x is equivalent  to circula r   lef  sh ift  a  m -bits binary na mbe r   x  by  n  bits , t hen     compl e me nt of result [12].   L e mma   4 :  21 2 m ms i  is equivalent to  21 2 m i   Whe r e,  n  and   m  are any natural num bers.  Since  X 1  is a 6 n -bits n u m ber an d  x 5  is a (2 n -1 )-bits numbe r, they are rep r e s ented in  their binary forms  as  follows :      1 1 ,6 1 1 ,6 2 1 , 1 1 , 0 6 nn n X XX X X                   5 5 ,2 2 5 ,2 3 5 , 1 5 , 0 21 nn n x xx x x                                                                        Whe r e,  x i,j   de note the  jth  of  x i . Th en,  r 1  an d  r 2   can  be  furthe rmo r e  si mply by lem m a 2  an d   lemma 3.     21 22 15 5 , 0 5 , 2 2 5 , 2 3 5 , 1 21 21 2 n n nn n rx x x x x                                                                 (15)  21 21 22 21 21 6 3 6 1 62 42 64 6 5 4 1 24 22 1 2 1 4 3 44 2 0 22 2 3 1 21 2 1 21 2( ) 11 11 n n n n n n nnn n n n nn n n n n nn rX XX X X X X X XX X X X X X X                   21 22 23 2 （） + （） r rrr （） （） 21 21 n 4    (16 )     Whe r e,  i x  is the complem e nt of  i x , and  r 21 ,  r 22 ,  r 23 ,  r 24  can  be rep r esent ed in th eir bin a ry form s .   By substitutin g  (15 )  and (1 6) in to (1 4), R can be  cal c ul ated by:    21 024 2 2 12 12 2 2 3 2 4 21 (2 2 2 2 ) ( ) n n Rr r r r r                                      (17)  By applying  Le mma   2, Le mm a   3  and  Le mm a   4  in Equation (15), (16) a nd (1 7),  they can  be sim p lified  to decrea s e  the hardwa r e comp lexit y . The Ope r and Prepa rat i on Unit  (OP U )   inclu d e s   simp ly manipul ating the  routin g of th e  bit s   and i n verte r s of the  re sid u e s th at p r ep a r es  the ope ran d s for mod u lo  adde r. The i m pleme n tatio n  of R  requi res a  5 n -ope rand carry  sa ve   adde r (CSA)  with en d-a r o und  carry (E AC) [15] tre e  followe d by a modul o 2 2n-1 -1 add er th a t  is  one (5 n , 2 2n-1 -1) M u lti-O p e r and  Modul ar Adder  (MO M A). In the p aper,  we  con s ide r ed  mod u lar  adde r that i s   the ca rry p r o pagate  add er (CPA)  wi th e nd aroun d ca rry (EA C ) [16 ]. Furtherm o re,  (13 )  ca n be rewritten a s :     24 6 2 2 11 2( 2 1 ) X 2 2 2 nn n n n XX R R R Y R        ( 1 8 )     Evaluation Warning : The document was created with Spire.PDF for Python.
                               e-ISSN: 2 087-278X   TELKOM NIKA  Vol. 11, No . 11, Novemb er 201 3:  657 7 – 6583   6582  Whe r e:     6 1 2 2 2 3 1 0 1 ,6 1 1 ,6 2 1 , 1 1 , 0 21 6 2 n nn n n n n YX R R R R R X X X X                   (19)    It should  be  noted, b e cause  X 1  is a  6 n -bits nu mber, (19 )  can be reali z ed by  sim p le   con c ate natio n without ad d i tional  hardware an d co mp utation co st.   Finally, by s ubs tituting (19) in (18), we have:    2 11 2 2 2 3 1 0 42 21 21 1 1 1 1 1 1 1 1 n nn nn n XY V Y V V V V                              (20)    Reali z ation  o f   X   relie s on a  (8 n -1)-bits binary su btra cter, whi c h can  b e   impl e m ented rely on  a   (8n - 1)-bit s re gular  CPA with ‘1’ carry-in  and (2 n -1 ) NOT gate s .  Example 1 ： Fo r  n =8 ， the pro p o s e d  5-m oduli  set is S = (6 5536,6 553 7,2 55,257,  3276 7 ）， th e weig hted  numbe r  X  can be  calcul ated fro m  its RNS  representat ion   (121,1 65,27 4 1 ,1056,3 012 5 ) , the re si d u e s  have  bina ry rep r e s entati on  x 1 =(0000 1 0101 0110 101 ),  x 2 =(00 0000 1 0000 1000 00 ),  x 3 =(0 111 10 01),  x 4 =(010 1001 01) and   x 5 =(111 010 1101 0110 1).  For  the first level   of the propo sed reverse  co nverter, the  4 - mod u li set S 1 =(6 5536,6 5 5 37,255,2 57), i t s  equivalent weighted  n u m ber  X 1 =(11 9 4449 7348 884 ) 10  that we  can obtain ed  by (6). Fo r t h e   se con d  l e vel of  the  prop osed  reve rse  co nverte r, the  2-m oduli  S 2 =(32 767,2 5 5 ×2 57 ×65 5 3 6 ×6 553 7), a c cordi ng to  (14 ) -(19 ),  we h a ve R=(3 080 4)  10  and  Y 1 =(86 706 74 6275 6853 624 5)  10  , finally,  X =(8 670 674 6 2554 9765 301 )  10  can be o b tained by (2 0).       5. Performan ce Ev aluation  In this sectio n ,  the area an d delay of  pro posed reve rse conve r ter fo r the new  fi ve -mod uli  sup e rset a r e  evaluated. According to  Fi gure  1  an d Fi gure  2, the p r opo sed  5-m o duli re sid ue-t o - binary   co nve r ter co nsi s ts of  one   fou r -moduli set   converte r,  on e   (5 n , 2 2n-1 -1) MOMA for t he  cal c ulatio n of R, one (8 n -1)-bit bina ry subtracte r  an d som e  inverters. Th e esti mated ha rd ware   co sts a c cordi ng to full add er (FA ) , and  modula r  ad d e r (m od ad d), subtra ctor  (sub ) an d so me   logic gate s . F u ll ad ders (F A’s)  with  co n s tant bit s   of 1 ’ s o r   0’s a r e  redu ced  to p a i r s of XO R/AND  or XNOR/O R gates. T he t o tal co nversi on del ay  and  hard w a r e  co sts are the  su m of the resi due- to-binary converter for the 4-moduli  s e t  S 1  and 2-m oduli  set S 2 . Table 1  sh o w s th e ha rd ware   co sts a nd co nversi on d e la ys of the pro pos ed 5 - mod u li set reverse co nverte rs,  whe r e  t FA  den ote   the delay of an FA and L   d enote the nu mber of level s  in an CSA tree, re sp ectiv e ly.      Table 1. Ha rd ware Ch aract e rization of Each  Pa rt of the Propo se d Reverse Co nvere r    Mod set  part   FA  NOT   XOR/AND   XNOR/ O R   Dela y  S 1   OP U  -  6 n +3 -  -  t not   CSA1 2 n +1 -  2 n -1  -  t FA  CSA2 2 n +2 -  2 n -2  -  t FA   CSA3 2 n +3 -  -  2 n -3  t FA   CPA 4 n  -  -  -  (8 n )t FA   Area   (10 n +6)A FA +(4 n -3 ) A xo r +(4 n -3 )A an d +(2 n -3 )A x nor +(2 n -3 ) A or   +(6n+3)A no t   Dela y (8 n +3)t F A +t not   S 2   OP U1  -  6 n  -  -  t NOT   CSA 10 n 2 -9 n + 2  -  -  --   L 1  CPA 2 n -1  -  -  -  (4 n -2 )t FA   OP U2    2 n -1  -  -  t NOT   8n-1 bit sub   8 n -1  -  -  -  (8 n -1 )t FA   Area  (10 n 2 + n )A F A +(8 n -1 ) A not   Dela y  L 1 +2 t NOT +(12 n -3 )t FA   S  Area  (10 n 2 +11 n +6) t FA +(4 n -3 ) t xo r +(4 n -3 ) t an d +(2 n -2 )  t x nor +( 2 n -2 ) t or +(14 n +2 )t not   Dela y 3t NOT +20 n t F A +  L 1     The dynami c   rang e of the  prop osed 5 - moduli  set ha s 8 n -1 bits .  Up to now, it is dif fi c u lt to find  a   existing m o d u li set s  that  has th e  sam e  dynami c   ra nge a s  th e p r opo se d 5 - m oduli  set. Mo duli  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   e-ISSN:  2087 -278X       An Efficient Reve rse Co nverter fo r The  Ne w  Hig h  Dynam ic Ran g e  5-Mod u li Set (Xiaolan L v )  6583 sets of [10] a nd [12] have t he same  nu mbers of ch a nnel s as o u r  prop osed mo duli set, but h a ve   different dyn a m ic  ran ge.  We compa r e  o u r m oduli  set  with [1 0] an d [12]. Fo r a   fair comp ari s on ,  n -bit CPA s  with EAC are   con s id ere d  for the im ple m entation of  the modul o 2 n -1 ad der fo r all  conve r ters. Table 2 sh ows the  hardware co sts and  conv ersion d e l a ys of the propo sed 5 - mo duli  set  reverse   conve r ters, [ 10] an d [12].  It is  cl ea r from the  table  that p r opo sed 5 - mo duli  set  reverse co nverters  h a s a  signifi cant su perio rity  in hi gh dynami c  range m oduli  set with  effici ent  reverse  conv erter.  L 1  a nd  L 2  a r e  num ber  of the l e vels of th e  CSA tree  wit h  (5 n) inp u t  and   ((n/2)+1) input res p ec tively.      Table 2. Ha rd ware Co mple xity and Conversi on Delay Comp ari s o n   converter  DR   n  area  Dela y   [10]  15n  odd  >(  36n 2 +144 n )   A F A  >(27 n +9)  t FA    [12]( n =6k)  5n  even  1 6 (5 n 2 +145 n － 12)  A FA   n=6k   (18 n +  L 2 +7 )  t FA   Proposed  8n-1   an y  (10 n 2 +11 n +6)   A FA  +(4 n -3)A xo r +  (4 n -3 )A an d +(2 n -2) A x nor   +(2 n -2 )A or + （ 14 n +2 ） A not (3t NOT +20 n t FA +  L 1 )  t FA       6. Conclusio n   This pa per i n trodu ce d th e ne w high  dynami c   ra nge  5-m odul i set  {2 n -1,2 n +1, 2 2n ,  2 2n +1, 2 2n-1 -1},  whe r e  n  i s  a n y positive in teger. Th e efficient  reverse  conve r ter fo r the moduli  set  is presented t hat is ba sed  on the NE W CRT s a nd  th e conve r se al gorithm fo r the four-moduli  set  {2 n -1,2 n +1, 2 2n ,2 2n +1}. The  overall  spe e d  of the arith m et ic unit of  RNS  syste m s ba se d on  the  moduli set S 1  and S is re stricted to the  2 2n +1 chann e l , but the pro posed 5-mod u li set reve rse   conve r ter that  its dynamic range h a s raised to 8 n -1 bit s .      Referen ces   [1]  HL  Garn er .  T h e Resi due N u mber S y stem.  IRE T r ansactio n s on Electro n i c Co mput ers . 195 9; 8(6):  140- 147.   [2]  NS Szab o, RJ   T anaka. R e sid ue  Arithmetic  a nd  its  Ap plic ati ons to C o mp uter  T e chnolo g y .  Ne w   Y o rk :   McGra w - Hil l.1 967; 1-2 0 .  [3]  MA  Soderstran d . Resid ue nu mber s y stem a r ithmetic:  mod e rn ap plic ation s  in digita l sign al process i n g .   Califor ni a: IEEE Press. 1986:  1-32.   [4]  B Parhami. Co mputer  Arithme t ic:  Algorithms and H a rd w a re  Desig n .  Oxford, U.K.:  Oxford  Univ .  20 00.   [5]  PV A  Mohan. R e sid ue Num ber  S y stems:  Algo rith ms and  Arc h itectures. Nor w e ll, MA: Klu w er , 2002.   [6]  G Dimauro, S Impdedovo, G Pirlo.  A  new  t e chn i q ue for fast number comparison i n  the residu e   number s y stems.  IEEE T r ans.  Com p ut. , 1993; 42: 60 8–6 1 2 .  [7]  M Lu, J Chia n g .  A  novel div i sion a l g o rithm  for the resid u e  numb e r s y stem.  IEEE T r ans. Comput.,   199 2; 41: 102 6 –10 32.   [8] Y   W ang.  New   Chin ese re ma i nder theor e m s.  Proc. 32th  Asil omar Conf. Si gnals, S y stems, Comp uters,   199 8; 1: 165– 1 71.   [9] A   Skavantzos.  An ef fi cient res i due to weighted conv er ter for  a new residue  num b er system . Proc. 8th  Great Lakes S y mp. VLSI, Ne w   Orle ans, LA.  1998; 9: 18 5– 191.   [10]  J Mathe w , D R adh akrish na n,  T  Srikanthan.  F a st residue-to -bin ary convert e r architectur e s . Proc. 4nd   Mid w est S y mp.  Circuits S y st. 199 9; 2: 1090 – 109 3.  [11]    A  Skavantzos,  T  Stouraitis.  Groupe d- mod u li resid ue nu mber systems for fast signal process i ng .  Proc. Int. Sy m p . Circuits S y st . 1999; 3: 478 – 483.   [12]  B Cao, CH C h ang,  T   Srikant han.  A  resid u e - to-bin ar y  c onv erter for ne w   fi ve-moduli set.  IEEE  T r ans.  Circuits System s I.  2007; 54( 5): 1041 –1 049.   [13]  A  Skavantzos, M  Abda lla h. Impl em entatio n is sues of t he t w o-lev e l resid u e  number s y st e m   w i th pa irs  of conju gate m odu li.  IEEE T r ans. Signal Proc ess . 1999; 4 7 ( 3 ): 826– 83 8.  [14]  AS Mola hoss e i n i, K N a vi, O H a shem ipo u r ,  et al. Ef ficie n t re verse co nverte r for the N e w   4 -modul i set s   {2 n − 1, 2 n , 2 n +1,  2 2n+ 1 − 1} and {2 n − 1, 2 n +1 , 2 2n , 2 2n + 1 } b a sed on the  Ne w   CR T s .  IEEE T r ans. on  Circuits and Sy stem s I . 2010;  57(4): 82 3-8 3 5   [15]  SJ Piestrak.  A   hig h - spee d re alisati on  of res i du e to bin a r y   s y stem conv er sion.  IEEE T r ans. Circuits   Syst. II,  Analog  Digit. Sign al P r ocess . 199 5; 42(6): 66 1– 663 ,    [16]  Patel RA, Ben a issa M, Bouss a kta S. F a st  paralle l-prefi x  arc h itectures for modu lo 2 n − 1 A dditi on  w i th  a   singl e repr ese n tation of zer o .  IEEE T r ansactions on Com puters.  2007; 56( 1 1 ): 148 4-14 92 .  Evaluation Warning : The document was created with Spire.PDF for Python.