Intern ati o n a Journ a l of  Re con f igur able  and Embe dded  Sys t ems  (I JRES)  V o l.  4, N o . 1 ,  Mar c h  20 15 pp . 6 ~ 1 2   I S SN : 208 9-4 8 6 4              Jo urn a l  h o me pa ge : h ttp ://iaesjo u r na l.com/ o n lin e/ind e x.ph p / IJRES  An Effi cient VLS I  Archit ectu r e f o r Nonbinary L D PC Decoder  with Ad aptive Message Control        R. V a ra th ar aj an   Department o f  ECE, Sri  Lakshmi Ammal Engineering  College, Ch ennai, Ind i     Article Info    A B STRAC T Article histo r y:  Received Sep 26, 2014  Rev i sed  No 13 , 20 14  Accepte d Dec 2, 2014      A new decoder   architecture fo nonbinar y  low-d e nsity  par i ty   check (LDPC)  codes is prese n ted in  this p a per  to  reduce the h a rdware operational  complexity  and  power consumption. Ad aptiv e m e ssage control ( A MC) is to  achi e ve the low  decoding com p lexit y  th at d y na m i call y  tr im s  the m e s s a ge   length of b e li ef  inform ation to r e duce  the  am ount of m e m o r y  a ccesses an d   arithmetic oper a tions. A new horiz ontal  nonbinar y  LD PC decoder   archi t ec ture  is develop e d to  i m p le m e nt AMC. Ke y com p o n ents in th archi t ec ture  hav e  be en d e s i gned  with  the  consid eration of  variab le message  lengths to  lev e r a ge th e ben e fit  of  the proposed  AMC. Simulation results   demonstrate  that the proposed  nonbinar y  LDP C  decod e r ar chitecture  can   significantly  r e duce hardware opera tions an d power consumption as  compared with existing work with negligible p e rf ormance d e grad ation .     Keyword:  Ada p t i v e m e ssage c ont rol   Decoding  E x t e n d ed   mi n - s u No n bi nary  l o w- de nsi t y  pari t y - check (L DPC )   code s   VLSI a r chitecture   Copyright ©  201 5 Institut e  o f   Ad vanced  Engin eer ing and S c i e nce.  All rights re se rve d Co rresp ond i ng  Autho r R.  V a r a th ar a j an  Pro f ess o r  &  H ead  Depa rt m e nt  of  EC E,  Sri  L a ks hm i  A m m a l En gi nee r i n g C o l l e ge, C h e nna i ,  I nda   Em a il: v a rath u2 1@yahoo .com      1.   INTRODUCTION  Lo w- den s i t y  pari t y -chec k  (L DPC )  co des  [ 1 ] ,  [ 2 ]  are c o nsi d e r ed  as  o n of t h e m o st  po we rf ul   capacity-approaching c o des.  LDPC c o des  can   b e  co nstructed  in   bo th b i nary do m a in  and   Galo is  field s  (i.e.,  GF( 2 m ), w h e r m  >1). B i nary  L D PC  c ode s ha ve  be en st u d i e d e x t e nsi v el y  an d  ado p t e d i n   m a n y   com m uni cat i on p r ot ocol s ,  su ch as D V B - T2 ,   W i M a x, et c.  I n  ge neral ,  a ve ry  l o n g  co de l e ngt h i s  necessa ry  fo bi na ry  LDPC  code s t o  a p p r oac h  t h e c h a nnel  ca paci t y . Lo w- Den s i t y  Pari t y -C hec k  (LD P C )  c o d e s ha ve  recently received a lot of attention  b eca use of their a d m i ra ble perform a nce  and ha ve bee n  widely consi d ere d   as a pr om i s i ng candi dat e  er ro r-c or rect i ng c o di n g  sc hem e  f o r m a ny  real  appl i cat i o ns i n  t e l ecom m uni cati o n s   and m a gnet i c  s t ora g e.  No n b i n ary  LDPC  c o d e s co nst r uct e i n  Gal o i s   fi el d s  of fer i m pro v e d pe rf o r m a nce at  a  m oderat e  code  l e ngt h. I n  a d d i t i on,  no n b i n ar y  LDPC  c odes  can  be com b i n ed  wi t h   hi g h   or der m o d u l a t i ons  t o   increase t h bandwidt h e ffic i ency. Due t o   these feat ures ,  desi g n  a n d i m pl em ent a t i on of  n o nbi nary   LDPC   code have  bec o m e  cri t i cal  for m a ny  em ergi ng  ap pl i cat i ons  suc h  as  u n d er wat e r ac o u st i c   com m uni cat i ons.   key  chal l e n g e i n  t h e a p pl i cat i on  of  n o n b i nary  L D PC  c ode s i s  t h ei r hi gh  dec o di n g  c o m p l e xi t y , as   each sym bol in the c ode word is dec o ded  using a l o ng m e ssage.  A lot  of researc h  effort aim s  at reducing the   deco di n g  com p l e xi t y  of n o n b i n a r y  LDPC  code s at  t h alg o rith m   lev e l. To  d eal with  th e p r ob lem th at  co m p u t atio n a co m p lex ity in creases ex pon en tially with , the extended Mi n-Sum  (EMS)  was propose d   in [3 whe r o n l y  t h e m o st  si gni fi c a nt   n ent r i e i n  a m e ssage  were  us ed  i n  t h dec odi ng dec odi ng  t echni qu e   devel ope d i n  [ 4 ]  con d u ct ed t h e EM with   a redu ced  co mp lex ity o f  o(n m   lo g n m ) wi t h  m i nor  per f o r m a nce   d e grad atio n. It sh ou ld   b e   n o t ed  th at these alg o r ith m - lev e l tech n i q u es do  no t exp licitly co n s ider the  com p l e xi t y  i n  t h e i m pl em ent a t i on  of  n o nbi na ry  LD PC   deco ders .   Diffe re nt fr om  these existing  wo rk s targetin g ha rd wa re imp l em en tatio n  co st, th e fo cus o f  th is p a p e is to  redu ce the h a rdware operatio n a l co m p lex ity in   nonbi n ary L D PC  de code r a r chitect ures . T h is e n a b les  Evaluation Warning : The document was created with Spire.PDF for Python.
                        I S SN 2 089 -48 64  I J RES  Vo l.  4 ,   N o 1 ,  Mar c h 20 15  :   6 – 12  effi ci ent   deco d i ng s u i t a bl fo r  em ergi ng a ppl i cat i ons s u ch  a s  u nde r w at er a c ou st i c  sens or  net w or ks  [5]  t h at  are   un de r t h e se ve re res o urce  (e. g ., e n e r gy )  co nst r ai nt s .   It  was reported that  m e m o ry ac cesses and a r ithm e tic  o p e ration s  are  th e two  m a j o co n t ribu to rs to th op eratin cost in L D PC  decode rs. As  the am ount of  me m o ry   accesses and a r ithm e tic operations is largely determ ined  by the m e ssage length, re duc i ng m e ssage lengt h is   deem ed as an effective  way for ef ficien t d ecod i ng Differen t  fro m  th e  EMS wh ich   main tain s a con s tan t   messag e  len g t h  fo r ev ery sy m b o l; th e p r op o s ed   AMC ad ju sts th e m e ssag e  leng th  adap tiv ely, wh ich  can  reduce t h e m e ssage le ngt h at t h require d   perform a nce.  In t h i s  pa per ,  a  ho ri zo nt al  seq u ent i a l  VL SI a r ch itecture for  the nonbi nary  LDPC  deco de r   em pl oy i n g   t h e AM C  i s  devel o ped .  The  desi g n  o f  t h e  key  com pone nt s i n  t h i s  arc h i t ect ure, s u c h  as vari abl e  n ode a n d   ch eck   no d e   u p d a te un its, is op ti m i zed  b y  ex p l o itin g  th variab le leng th   so rters, wh ich  can  b e   d y n a m i cally   con f i g ure d  i n   di ffe re nt  fu nct i onal   uni t s  t o  a ccom m odat e  vari abl e  m e ssage l e ngt h s . T h AM C  i s  im pl em ent e by  a l o w-c o m p l e xi t y  app r o x i m a ti on m e t h o d  t o  avoi d ha rd ware  ove rhe a ds an d per f o rm ance im pact . A  m a ppi n g  t a bl e base d ap pr oac h  i s  pr op ose d  t o  co nd uct  sear chi n g o p erat i o ns wi t h  l o w co m p l e xi ty . W e   appl y   AM C  t o  EM t o  ad dres s t h m e m o ry  and t h r o ug h put  i ssu es cause d by  t h e w o r s t  case m e ssage l e ngt h.  Not e   t h at  AM C  ca n   al so  be em pl oy ed i n   ot he dec odi ng   up dat e   r u l e s s u c h  as  t h e M i n-M a x al g o ri t h m .  I n  a ddi t i on,  t h e pr o pose d   AM C  can be  gene ral l y  appl i e d t o   m o st  exi s t i ng  deco de r archi t ect u r es  (seq uent i a l ,  p a rt i a p a rallel and   fu lly p a rallel).      2.   R E V I EW OF  N O N B INARY  LDPC COD E A no nb in ary LDPC cod e  is defin e d  b y  its p a rity ch eck  m a trix  (PCM)  = [h ij ],  wh ich  is an  M × N  sp arse m a trix  with  low  d e n s ity o f   n o n z ero  en tries. Th e non zero   en tries of  t a ke  val u e s  fr om  a Gal o i s  fi el d   GF( 2 m ). A leng th-N vecto r   with  en tries hav i ng  v a lu es fro m  GF(2 m ) i s   a code wo r d  i f  and  onl y  i f   Hx  0 Each entry in t h e codeword is  calle d a sym b ol . A n  LDPC  c ode  wi t h  PC M   can  b e  rep r esen ted   b y  a b i partite   gra p h cal l e T a nne gra p h ,   whi c h c o n s i s t s  o f  t w o cat e g o r i e s of  n o d es;  t h at  i s vari a b l e  n o d es  vi 1    i   N  and M chec node s cj ,   j   M .   A va ri abl e  n ode  vi  i s  c o nnect e d   wi t h  a  chec k n o d e c j  i f  an onl y  i f   hji  i n   th e PCM  i s  no nze r o .   The  dec odi ng  pr ocess  o f   n o n b i n a r y  L D P C  co des  ope r a t e s o n  t h e  m e ssages t h at  r e prese n t  t h e   p r ob ab ility d i stribu tio n   o f  sy m b o l s. A  m e ssag e  is a len g t h-2 m  vector recordi ng the  2 m  bel i e f i n fo rm at ion  of a  sym bol subj ect  to channel noi se, whe r e each belief inform a tion indicates the probability  of this noisy sym bol  to  b e   on e of  the 2 m  ele m ents  in GF(2 m ). Th e dec odi ng  pr o cess i s  essent i a l l y  i t e rat i v m e ssage e x c h an ge a n d   up dat e   bet w ee n t h e  chec n o d es a n d  va ri abl e  n odes  i n  t h Tan n er  g r ap r e prese n t a t i o n.  The m e ssages  on  t h e   Tan n er g r a ph  excha n ge an d up dat e  i n  t w di rect i o ns. Va r i abl e  no de m e ssages ( V NM s ) , de n o t e d by   q , pass   fr om   t h e vari abl e  no des t o  t h e check n o d e s;  and chec k n o d e m e ssages (C NM s), de n o t e d by   r , pass f r om  t h ch eck nod es t o  th v a riab le no d e s.  VNMs are in itialized   with  ch ann e messag e s,  wh ich  are th e inpu t to  t h decode r. T h en, VNMs are se nt to the  check  nodes to  updat e  the CNMs. T h ne w CNMs  are then se nt back to   t h e vari a b l e  n ode s an d use d  t oget h e r  wi t h  t h e chan n e messag e s to  up d a te th VNMs. Th is pro c ed ure is  k now n as t h belief  p r op agatio n.  There a r e m a inl y  t w o t y pes  of  dec odi ng al go ri t h m s  – su m - prod uct  al g o ri t h m  (SPA and m i n-sum   (MS),  of  which the latter one  is a  m a the m atical appr oxim a tion of SPA where the s u m  of product is replaced  b y  th e m a x i mu m  p r o d u c t term . Du e to  its relativ ely si mp le op eration ,   MS is o f ten  ch o s en   for practical   ap p lication s . Fu rt h e r redu ction  in  th e co m p lex ity o f  MS is d e sirab l e; on e su ch  ap pro ach is th e ex ten d e d  MS  (EM S )  alg o rith m .       3.   M I N- SUM  WITH ADA PTIV M E SSA G E C O N T ROL  In t h i s  sect i o n ,  an ada p t i v e m e ssage co nt r o l  m e t hod t h at  dy nam i call y  adju st s t h m e ssage l e ngt h o f  a  sym bol  du ri n g  t h e decodi n g  i t e rat i on was  devel o pe d. A  t r uncat i o n sc hem e   i s  prop o s ed f o r t h e p r op ose d   AMC-EMS al go rith m .     A.   A d a p tive   Mess age  C o n t rol ( A MC )   In t u itiv ely, when  th e d i stributio n  o f   b e lief in fo rm atio n  is  m o re co n c en t r ated , a m e ssa g e  with  a  sm aller num ber of e n tries m i ght be s u fficie n t to retain  the  sam e  am ount of the  be lief inform ation. E x ploiting  t h i s  fact , we  p r o p o se t o  a d ap t i v el y  cont r o l  t h e m e ssage l e ngt h d u ri ng t h e deco di n g  i t e r a t i on.  Ou r ap p r oac h   leads to t w o major a d vanta g e s . First, due t o   the casual  nat u re o f  c h a nnel   n o i s e, c h a nnel   m e ssages f o r  d i ffere nt   sym bol s m a y   have  di f f ere n t  st at i s t i c s. In com p ari s on  wi t h  t h e EM S w h i c h m a i n t a i n s a fi xed  num ber o f   en tries fo r all ch ann e l m e ssa g e s, th p r op osed  AMC can   lo wer th e av erag e m e ssag e  l e n g t h  wh ile retain ing  the sam e  a m o unt of belief  inform ation. Second, as  the  decoding proceeds, th e belief inform atio n will   gra d ually conc entrate around  the correct element in th e case of c o nve r ge nce. T h us, fe wer entries are  neede d   Evaluation Warning : The document was created with Spire.PDF for Python.
I J RES   I S SN 208 8-8 7 0 8     An  Efficien t  VLS I  Arch itecture fo r N o n b i n a ry LDPC Decod e r with   Adap tive …   ( R . Var a t har aj a n )   8 i n  t h e m e ssage of a sy m bol i . e., t h e m e ssage can  be  truncated eve n  m o re. T h ese feat ures are es senti a l for  red u ci n g  t h e c o m put at i onal  c o m p l e xi t y  of  d ecodi ng  n o nbi nary  L D PC  co des.   The m a jor  dec odi ng ope r ation at a  chec k node is t o   refi ne t h e estim ated  message  of a  sym bol based  on t h e m e ssages of  ot he r sy m bol s t h at   are correlated by t h e PCM H.  The el e m entary  check node ope r ation  i n   the Min-Sum  (MS)  decodi ng  algorithm  [3], [4] can be  expre ssed as     r=q 1 q 2           ( 1 )     Whe r e q 1  and q 2  are  t h e l e ngt 2 vari ab l e  no de m e ssages, a n d t h basi c o p e r at i o n i s   defi ne d a s  r α   max ( q1 β +q2 γ ), whe r e r α , q1 β ,q2 γ    are th e en t r ies in  m e ssag e r,  q1 ,q 2 corresp ond ing  to  α , β , γ  res p ectively.  On  t h e o t her  h a nd , each   v a riab le nod e im p r o v e s th fid e lity o f  b e lief in fo rm atio n b a sed   on  th receive d m e ssa ges from   m u ltiple chec node s connecte d   by  the PCM. T h e  ele m entary operation at a  va riable   no de ca be e x press e d  as  [3] ,   [4]     q   =   r 1 +   r 2           ( 2 )      Wh ich  su m s  u p  th b e lief in fo rm atio n   asso ciated   wi t h  the  sam e  finite field ele m ent. The  ha rd ware   co m p lex ity in  i m p l e m en tin g  (1 ) an d  (2 ) is determin ed  b y  th e len g t h s  of variab le no d e  messag e s (VNMs) and  ch eck   no d e  m e ssag e (CNMs). In t u itiv ely, wh en  t h e d i stri bu tio n   o f   b e lief  in fo rm atio n  is m o re co n c en trated , a   sh orter m e ssag e  mig h t  b e  su fficien t to  retain  m o st o f  th b e l i ef in form at io n.  The ba sic idea  of AMC is to keep as few e n trie s in a m e s s age as possi bl e with ou t in curring  m u ch  i n f o rm at i on l o ss. It  has bee n  dem onst r at e d  t h at   m e ssage t r uncat i o n can be i m pl ement e d by  fi n d i ng t h e   min i m a l n  th at satisfies      q( n+ 1)   q( 1 )  +  l n (1- ζ )/ ζ          ( 3 )     Whe r ζ  is the confi d ence  factor that determines  the tradeoff  bet w een  performance and ope r ational   com p l e xi t y , and  q( k)  i n di cat es t h kt h e n t r y  i n  t h e  l o do m a i n  rep r ese n t a t i on  of t h e m e ssage  q t h at  i s  so rt e d   in  ord e r.  In th is case, the trun cation  criteria can   b e   recast as     q( n+ 1)     ln  (1- ζ )/ ζ          ( 4 )     whe r e t h e thres hol d  is  use d  t o  truncate m e ssages.  Th op er ation   o f  A M C i n  a  no nb in ar y LD PC  dec ode r ca be s u m m ari zed as f o l l o ws.     Initia liza t io • Channel m e s s age truncation:  =AMC(f j ) whe r e f j  is the  receive d c h annel  m e ssage.  • V a r i ab le  no de m e ssag e :  q ij j , where q ij  i s  t h vari a b l e  n ode  m e ssage fr om  t h e vari abl e  n ode  v j  to  th e c h eck  no de c i   Iterations    Per m ut at i on q ij α   q ij α *hij , where  h ij  is th n o n z ero  PCM ele m en t, an d  th e m u lt ip licati o n  is con d u c ted  i n   GF( 2 m ).   • Check node  update     r ij j i M k \ ) (   q ij           ( 5 )     wh ere M ( i)\j    is th e set  of  n e ig hbo uring   v a ri ab le nod es  o f  th check node c i   e x cluding  the variable node v j  Inve rse  perm ut at i on r ij α   r ij α /hij , whe r e h ij   i s  t h e no nze r o  PC M  el em ent, an d t h e di vi s i on i s  co n duct e d i n   GF( 2 m ).   • V a r i ab le node up d a te    q ij =AMC ( j + ) \ ) ( kj r amc i j N k         ( 6 )   Evaluation Warning : The document was created with Spire.PDF for Python.
                        I S SN 2 089 -48 64  I J RES  Vo l.  4 ,   N o 1 ,  Mar c h 20 15  :   6 – 12    wh ere N(j ) \i is th e set o f   n e ig hbo ri n g  ch eck  nod es of th e v a riab le  n o d e   v  e x cluding the chec node  c i , and  AMC   m ean s that th e AMC is  ap p lied to   all th e in term ed iat e  resu lts.   Tent at i v dec odi ng   c j =Max ( j + ) ) ( kj r j N k          ( 7 )       4.   VLSI  A R C H I TECTURE  F O SEQ U EN TIAL A M C-B A SED  DE CO DER   In th is section ,  a seq u e n tial n onb in ary LDPC  dec ode arc h itecture for  the propos e d AMC  is   prese n t e d .   We  fi rst   di scuss t h e t o p l e vel  a r chi t ect ure a n t h en  det a i l  t h e  desi g n   of  sev e ral  key  c o m pone nt su ch  as th e v a riab le len g t h  sor t er v a r i ab le no d e  upd ate un it ( V N U ) ,  and  ch eck nod e update u n ite ( C N U ) .  Th pr o pose d   AM C  can be a ppl i e d t o   di ffe re nt  no bi na ry  LD PC  dec odi ng s c hed u l e s, s u c h   as seq u ent i a l ,   part i a l l y   p a rallel and   fu lly p a rallel architectu r es.    A.   Horiz o ntal Nonbinar y   L D P C  Decoder Ar chitecture   The desi g n  of  ho ri zo nt al  no n b i n a r y  LDPC   deco de r em pl oy i ng wi t h   AM C  i s  show n i n   fi g u re 1 .  I n   t h i s  ab ove a r c h i t ect ure c onsi s t s  of  vari a b l e  no de  up dat e   uni t ,  c h eck  n o d e u p d at e u n i t ,  chec k s u m   uni t ,   tentative dec oding  unit, pe rmutation,  invers e pe rm utation and RAM. Ran dom  access m e m o ry is used t o  store   t h e dat a . I n  t h i s  archi t ect ure  R A M   m e m o ry  i s  di vi ded i n t o  fou r  di vi si o n s.  R A M b  i s  used  t o  st ore t h e ch annel   messag e s; RAMa is to  sto r so m e  b its, wh i c h  are  g i v e n  to th e RAMd  t o   g e n e rate th e interm ed iate ch e c k  nod m e ssages .pe r m u t a t i on i s  used t o  rear ra ng e t h e or der o f  i nput s ,  w h i c h  are com i ng fr om   t h e vari abl e  no de   up dat e   u n i t .  I n verse  pe rm ut ati on i s  u s ed  t o   arra nge  t h e  o r der  o f   bi t s wh i c h are  f r om  t h e chec n ode   up dat e   uni t .  Te nt at i v e  dec odi ng i s   u s ed t o  d o  t h e   i t e rat i on  pr oce ss. C h ec k s u m  u n i t  i s  use d  t o  c h eck t h e c h an nel   messag e with   th e v a l u es i n  that u n it.      Fi gu re  1.  B l oc di ag ram  of h o ri z ont al   no n b i n ary  L D PC  de code r em pl oy i n g  wi t h  AM C       At  t h e be gi n n i ng  of t h dec odi ng , t h e t r u n cat ed  ch ann e m e ssag e s are lo ad ed  in to   th m e m o ry  R A M b . Te nt at i v e dec odi ng i s  con duct e d wi t h  t h e cha n nel  m e ssages an d t h e res u l t s  are s t ore d  i n  t h e m e m o ry  RAMc. If tenta tive decoding s u ceeds,  decodi ng te rm inates  and R A Mc out puts the final  result. Ot herwis e, the   d ecod e r in itializes th e i n termed iate ch eck   no d e  m e ssag e s (ICNMs) i n   the m e m o ry RAMd  with th e ch ann e l   messag e s.  After th e in itializatio n ,  t h e ch eck   n o d e   u p d a te un it (CNU)  read s IC NMs from RAMd  to  perfo r m   the check  node update. The  CNMs fr om   the CNU are inversely perm uted,  an d t h e n  pa ssed t o  t h e va r i abl e   no de  u pdat e  u n i t  al o n g  wi t h   t h e ass o ci at ed  chan nel  m e ssage t o   per f o r m   vari a b l e  n o d up dat e .  The  va ri abl e   RAMb  RAMa   perm   I nvperm   RAMd  CNU  VNU   CSU              R A M TDU I npu Out put   Evaluation Warning : The document was created with Spire.PDF for Python.
I J RES   I S SN 208 8-8 7 0 8     An  Efficien t  VLS I  Arch itecture fo r N o n b i n a ry LDPC Decod e r with   Adap tive …   ( R . Var a t har aj a n )   10 no de  up dat e  u n i t  (V NU ) al s o  ge ne rat e s t h m e ssages f o r t h e t e nt at i v e  deco di n g   uni t  (TD U ) t o  c o nd uct   tentative decoding. If tentative d ecoding doe s  not succee d,  the VNMs fro m  VNU are then pe rm uted and se nt  back to the C NU to update  the corresponding IC NMs, which are the n   sto r ed  in  th e RAMd After this, th d ecod e r pro ceed s  to  an o t h e variab le nod e. Th is pro cess con tin u e s un til th e ch eck  su m  u n it (CSU) d eci d e s t o   terminate beca use  of either  successful dec o ding or  reach i n the lim it of iterations.    B.   Vari able No d e   Up da te Unit         Fi gu re 2.   Im pl em ent a t i on of  t h e VN U u n i t       The desi gn o f  VN U i s  sho w n  i n  fi gure  2. T h e fu nct i o n o f  VN U i s  t o  com put e t w m e ssages,  whe r e   the belief i n form ation ass o ciated with t h sam e  Ga lo is field  ele m en t in  th e t w o m e ssag e s is su mmed .   Vari a b l e  no de  up dat e  u n i t  i s   use d  t o  t r u n cat e t h m e ssage l e ngt h .  I n  t h i s  uni t  re gi st er ar ray ,  m a ppi ng t a bl e,   m u l tip lex e r, sorter, co m p arato r  are  presen ted .  Th e m a p p i ng  tab l e is u tilized  to  su m  u p  th e en t r ies associated  with  th e sam e   fin ite filed  elemen t. Th fin a l resu lts are  sen t  to  t h e v a riab le leng th  sorter with th e asso ciated  Galo is field   ele m en ts an d   AMC is th en  app lied  to  t h outp u t o f  th sorter, starting  from th e larg est en try in  th e sorter,  wh en  th e en try is smaller th an  th e th resh o l d ,  t h following e n tri e s are  discarde d. T h is re duce s the   har d ware  o p er at i ons i n  t h e  V N U .     C.   Check  N o de   Upd a te  U n it   Th e CNU pro d u ces th e larg est ele m en ts a m o n g  all th e com b in atio n s  from two  in pu t messag e s. The  pr o pose d  desi g n  of C N U i s  sho w n i n  fi g u re  3. Fi g u re sh o w s t h at  t h e co m p l e xi ty  of C NU ca n be re d u ced t o   additions and insertion ope r ations if  the two input m e ssages are sorte d  in  the descending orde r. He re  adopt   t h i s  m e t hod i n   t h e C N desi g n The  com p l e xi t y  of  t h e C N depe n d o n  t w o  fact ors .             Fi gu re  3.   Im pl em ent a t i on  of t h e C NU  u n i t       The fi rst  fact o r  i s  t h num ber o f  o u t put s,  whi c h det e rm ines  ho w m a ny  i n sert i o n o p e rat i ons  ar e   neede d The se cond  factor is t h e le ng th   o f  t h e so rter,  wh ich d e term in es h o w m a n y  co m p arison s an d  sh i f tin Evaluation Warning : The document was created with Spire.PDF for Python.
                        I S SN 2 089 -48 64  I J RES  Vo l.  4 ,   N o 1 ,  Mar c h 20 15  :   6 – 12  11 ope rations are  invol ved i n  each inse rti on  ope ration. Em ploying the pr opose d  AMC,  the  m e ssage lengt decrease s  thus  becom e s s m aller during the  iteration.  Th is redu ces th n u m b er o f  arithmetic o p e ratio n s  and  in sertion s . To  ad dress th e seco nd  fact o r , th so rter is  co nfigu r ed  to  b e  th sam e  len g t h  o f  th e sh orter m e ssage  th ereb y redu cin g  th e co m p lex ity o f  each  insertio o p e ra tio n. Th e CNU  also   p e rform s  ad d ition s  i n  t h e Gal o is  field.  Howe ver, additions i n  the Gal o is field are esse n tially  b it-wise  XOR  o p e ration s , t h u s  th e co m p lex ity is  m u ch  lo wer than  th e real  num b e r ad d ition s  of  b e lief informatio n .     D.   V a ria b le Lengt h  So rt er  Sort i ng i s   an i m port a nt  o p era t i on i n  t h e C N U a nd  V N U .  I n  t h e C N U, t h e so rt er c h o o se s n u m b er o f   ele m en ts with   th e larg est  b e lief inform atio n  as requ ir e d   for c h eck node  update. In the   VNU, truncati o n is   carried out and it discards t h sm a ller ele m en ts and t h e re m a ining  elem ents  are s o rted  i n   or d e r  as th e i npu t of   CNU.   The basic sorting  ope ration is to  insert a new ele m ent into a vect or according to its  m a g n itude . The   p r op o s ed  v a riab le len g t h  so rt er is illu strate d  in  figu re 4, wh ere on ly th e d a ta p a th  o f  b e lief in formatio n  is  sh own  as it d e termin es th e sh ifting   o p e ratio n. Th e sorter   consists of  num b er of  stages  to acc omm odate the   longest m e ssa ge length.  Eac h  stage c ontai ns a com p arat or a nd a  re gi st er. Eac h  t i m e   new  bel i e f i n f o rm at i on  co m e s in , it is  co m p ared  wit h  all th e b e lief in fo rm atio n  in  th e activ e stag es in  p a rallel. Th e con t en o f  t h e first  stag e h a v i n g   l a rg er b e lief  i n fo rm atio n  will  b e  rep l aced b y  t h n e in pu t,  wh ereas its orig in al   b e lief  in fo rm atio n  will b e  sh ifted  to   th e righ t stag an d  so   o n . Sort er is an  im p o r tan t  op eration  in  ch eck  nod e up d a t e   uni t  an vari a b l e  n ode  u p d a t e uni t .  S o rt e r   con s i s t s  of  de code r,  regi st e r ,  com p arat or m u lt i p l e xer,  x o gat e The  ope rat i on  i s  paral l e l  pr oc ess. Em pl oy i ng AM C ,  t h e m e ssage l e n g t h   r e duce s  g r ad ual l y .  Thus  o n l y  t h e l a st   st ages are  ena b l e d.  Thi s  i s  c ont rol l e by  t h e l o n g er  o n o f  t h e t w o m e ssages i n  t h e c h eck  no de  up da t e  uni t   ( C NU )  or  v a r i ab le  nod e u p d a t e   un it  (V NU ).         Fig u re  4 .  Variab le leng th   sort er      Th e m a j o r op eratio n s  in  th e so rt er a r e com p arisons and shi f tings . The num ber of these ope rations is  m a i n l y  det e r m ined  by  t h e l e n g t h   of t h e m e ssage t o  be  pr oce ssed. T h pr op ose d  AM C  dy n a m i cal ly  adjust s t h e   messag e  leng th du ri n g  th e iteratio n ,  t h ereb red u c i n g th com p lex i t y  o f  sortin g .     E.   Searching  Searc h i n g i s  a not her  m a jor  o p erat i o n i n  t h e   check  n o d up dat e  u n i t  (C N U an vari a b l e  n ode  u p d at e   u n it (VNU).  In th e VNU, th b e lief inform at io n  i n  on e m e ssage  need s t o  s earch  f o r i t s  c o unt e r pa rt  i n  a n ot he m e ssage t o   su m s  up t h bel i e f i n fo rm at i on. The  o u t p ut   of  th e so rter is co n s i d ered   v a li d  if and   on ly if the  cor r es po n d i n g  Gal o i s   fi el el em ent  has n o t  bee n   gen e r a t e d p r evi o usl y . A sea r chi n ope rat i o n  ha s t o   be   con d u ct ed  o n  t h e c u r r e n t   out put  t o  c o m p are i t  wi t h  t h pre v i o us  o u t p ut of  t h e s o rt e r .T he  m a ppi ng   in fo rm atio n  b e tween  th Gal o is field  elem e n ts and  th eir i n d e x e s in  a m e ssag e  is m a in tain ed  b y  a map p i n g   t a bl e of   w o r d s wi t h   wo rd l e ngt h o f   bi t s . I n  t h e C N U ,  n u m b er of  di f f e r ent  el em ent s  need t o   be ge nerat e d   according to varia b le node   m e ssages. The output of th e sorter is considere d  val i d if and onl y  if the  cor r es po n d i n g  Gal o i s   fi el el em ent  has n o t  bee n   gen e r a t e d p r evi o usl y . A sea r chi n ope rat i o n  ha s t o   be   conducted  on t h e c u rrent  out put  t o  com p are it with the  prev i ous  o u t p ut s of  t h e s o rt er.     Mapp ing  tab l e is to   records th e statu s  of Gal o is field  ele m en ts;  it is referre d  to as statu s  tab l e in  th e CNU.  Th e ex isten ce  o f  t h el em ent  needs  t o  be det e rm i n ed;  a  m a ppi n g   t a bl e wi t h  o n l y  num ber o f  bi t s  can be c onst r uct e d. T h pr o pos ed  Evaluation Warning : The document was created with Spire.PDF for Python.
I J RES   I S SN 208 8-8 7 0 8     An  Efficien t  VLS I  Arch itecture fo r N o n b i n a ry LDPC Decod e r with   Adap tive …   ( R . Var a t har aj a n )   12 map p i ng -b ased search i n g  sche m e  is n a tu rally lo w co m p le x ity in  co m p a r ison  with   d i rect search ing   o f  the  m e ssage, es pec i al l y  when t h m e ssage i s   ver y  l o n g .       5.   RESULT AND DIS C USSI ON          Fi gu re 5.   H o ri z ont al  no n b i n a r y   LDPC  dec o d e em pl oy i ng wi t h  AM C       Tab l 1 .  C o m p arisio n Resu lt  Fo r Variou s Meth od Para m e ter   MS  EMS  AMC-EMS  M e m o ry   Size    3232 32   2143 68   1604 76   Power     1   0. 7   56 m W         6.   CO NCL USI O N   A n e n onb inary lo d e n s ity p a rity ch eck (LDPC)  decoding  arc h itecture  is p r op osed to  r e d u ce  h a rdw a r e   op eratio n  an p o wer  co n s u m p tio n .   A   ho r i zo n t al sequ en tial VLSI  ar ch itectu r e for  th e nonb in ar y   LDPC  dec o der  em pl oy s t h e AM C .  The d e s i gn o f  t h e key  com ponent s i n  t h i s  archi t ect ure ,  suc h  as v a ri abl e   n o d e  and  ch eck   n o d e  upd ate un its, is  op timized  b y  ex p l o itin g th v a riab le leng th sorters, wh ich can   b e   dy nam i cal ly  con f i g ure d  i n   di ffe rent   fu nct i o nal  u n i t s  t o  ac com m odat e  va ri abl e  m e ssage l e ngt hs.  T h AM C  i s   im pl em ent e d by  a l o w-c o m p l e xi t y  app r o x i m a ti on m e t hod t o  av oi d ha r d wa re o v er hea d s an d pe rf or m a nce  im pact . Her e   Ada p t i v e  M e s s age C o nt rol   m e t hod  i s   us ed  t o   r e du ce t h e m e ssag e  leng th . Th us th messag e   l e ngt h  i s  re d u c e by  ap pl y i ng  ada p t i v e m e ssage c ont rol  t o   t h e va ri abl e   n o d up dat e   uni t ,  t h en  t h e t r u n c a t i on  i s  achi e ve d.  Si m u l a t i on re sul t s an d sy nt hesi s  re po rt s are  ana l y zed.      REFERE NC ES   [1]   R. G.  Gallager.  Low-Density  Parity-Check Codes Ca mbri dge , MA:   MI T Press. 19 63.    [2]   D.J . C. M acKa y   and R. Neal. “ Good codes based on very sparse  matrices ”. In Proc. Cr y p tograph y  Coding, 5th I M Conf. 1995 , pp   100–111.  [3]   D. Declercq an d M. Fossorier. “Decoding alg o rithms for nonbinar y  LDPC codes over GF(q)”.  IE EE T r ans.   Commun.  vol. 5 5 , no . 4 ,  pp     63 3–643, Apr. 200 7.  [4]   A.Voicil a, D.  Decer cq, F .  V e rdi e r, M .  F o s s o rier,  and P .  Urard. “ Low compleix ty,  low memory E M S algorithm fo non-binary LDPC codes ”. In  Pro c . ICC .  2007 , pp . 671–676 [5]   J. Huang, S .  Zh ou, and  P. Will et. “Nonbinar y   L D PC  coding for  m u lticarr i er und erwater  acoustic com m unication IEEE  J .  S e l.  Are a s Commun.  vol. 26, no. 9, pp. 16 84–1696, Sep .  2 008.  [6]   W. Tang, J. Huang, L.  Wang,  and S. Zhou. “ Nonbinary LDPC decoding by Min-Sum with adaptive message   control ”. In  Proc. Int. Conf  Aco u st. Speech , Sig n al Process. (IC ASSP). 2011, pp . 3164–31     Evaluation Warning : The document was created with Spire.PDF for Python.