I nte rna t io na l J o urna l o f   E lect rica l a nd   Co m p ute r  E ng in ee ring   ( I J E CE )   Vo l.   7 ,   No .   1 ,  Feb r u ar y   201 7 ,   p p .   5 2 1 ~ 5 2 5   I SS N:  2088 - 8708 ,  DOI : 1 0 . 1 1 5 9 1 / i j ec e . v 7 i 1 . pp 521 - 5 2 5           521       J o ur na l ho m ep a g e :  h ttp : //ia e s jo u r n a l.c o m/o n lin e/in d ex . p h p /I JE C E   New  H euristic M o del f o r  O pti m a l  CRC  Poly no m ia l       Ah m ed  Sa li h K hirbeet ,   Ra v ie  Cha nd re n M un iy a nd i   Re se a rc h   Ce n ter f o r  S o f t w a re   T e c h n o lo g y   a n d   M a n a g e m e n t,   F a c u lt y   o f   Tec h n o lo g y   a n d   In f o rm a ti o n   S c ien c e ,   Un iv e rsity   Ke b a n g sa a n   M a la y sia ,   M a la y sia       Art icle  I nfo     AB ST RAC T   A r ticle  his to r y:   R ec eiv ed   Oct  2 3 ,   2 0 1 6   R ev i s ed   Dec   1 4 ,   2 0 1 6   A cc ep ted   Dec   3 0 ,   2 0 1 6       C y c li c   Re d u n d a n c y   Co d e s  (CRCs )  a re   im p o rtan t  f o r  m a in tain in g   i n teg rit y   in   d a ta  tran sm issio n s.  CRC  p e rf o rm a n c e   is  m a in l y   a ff e c ted   b y   th e   p o ly n o m ial   c h o se n .   Re c e n t  in c re a se s  in   d a ta  th ro u g h p u t  re q u ire  a   f o ra y   in to   d e ter m in in g   o p ti m a l  p o ly n o m ials   th ro u g h   so f t w a r e   o r  h a rd w a r e   i m p le m e n tati o n s.  M o st   CRC  im p le m e n tatio n s  i n   u se ,   o ff e r  les s  th a n   o p ti m a l  p e rf o r m a n c e   o r  a re   in f e rio r  to   th e ir   n e w e r  p u b li sh e d   c o u n terp a rts.   Clas sic a l  a p p r o a c h e s  to   d e term in in g   o p ti m a l  p o ly n o m i a ls  in v o lv e   b ru te  f o rc e   b a se d   se a rc h in g   a   p o p u lati o n   se t  o f   a ll   p o ss ib le  p o ly n o m ials  in   th a t  se t.   T h is  p a p e r  e v a lu a tes   p e rf o r m a n c e   o f   CRC - p o l y n o m ial s g e n e ra ted   w it h   G e n e ti c   A lg o rit h m s.  It  th e n   c o m p a re s  th e   re su lt a n t  p o ly n o m ial s,  b o t h   w it h   a n d   w it h o u t  e n c r y p ti o n   h e a d e rs ag a in st a b e n c h m a rk   p o ly n o m ial.   K ey w o r d :   C y cl ic  r ed u n d an c y   co d es   Data   au t h en t icatio n   Data   in te g r it y     Gen etic  al g o r ith m s   Op ti m izatio n   Co p y rig h t  ©   2 0 1 7   In stit u te o f  A d v a n c e d   E n g i n e e rin g   a n d   S c ien c e .    Al l  rig h ts  re se rv e d .   C o r r e s p o nd ing   A uth o r :   Ah m ed   Salih   Kh ir b ee t ,   R esear ch   C en ter   f o r   So f t w ar e  T ec h n o lo g y   a n d   Ma n ag e m e n t,   Facu lt y   o f   T ec h n o lo g y   a n d   I n f o r m at io n   Scie n ce ,     Un i v er s it y   Keb an g s aa n   Ma la y s ia ,  Ma la y s ia .   E m ail:  a h m ed . s a lih 8 9 @ s i s w a. u k m . ed u . m y       1.   I NT RO D UCT I O N   C y cl ic  R ed u n d an c y   C h ec k   ( C R C )   co d es  ar e  a  h ig h l y   r ec o g n ized   d ata  in teg r it y   m ec h a n is m   in   d ig ital   co m m u n icatio n s   f o r   i n d u s tr ia l  u s e.   T h e y   ac t  a s   a   f ir s t  lin e   o f   d e f en s e  i n   d etec tin g   d ata  p ac k et  co r r u p tio n   b et w ee n   t w o   n o d es  i n   a  c o m m u n icatio n   lin k   [ 1 ] .   Var io u s   C R C   i m p le m e n tatio n s   ex is t  in   d i f f er en t   ap p licatio n s ,   e. g .   f r o m   e m b e d d ed   n et w o r k   ap p licatio n s   [ 1 ]   to   w ir ele s s   n et w o r k s   [ 2 ] ,   to   co m m u n icat io n   p r o to co ls   s u ch   as  USB   3   [ 3 ] .   T h eir   w id e  ac ce p tan ce   is   d u e  to   th eir   s i m p lic it y ,   g o o d   en co d in g   a n d   d ec o d in g   p er f o r m a n ce ,   an d   g o o d   lev el s   o f   er r o r   d etec tio n   [ 4 ] .   A s   d ata  th r o u g h p u t  i n cr ea s e s ,   h o w e v er ,   it  b ec o m e s   i m p o r tan t to   u t ilize  o p ti m ized   C R C   i m p le m e n tatio n s .   C R C   o p ti m izat io n   h as  b ee n   at te m p ted   f r o m   t w o   a n g les,  n a m el y ,   p o l y n o m ial  s elec tio n ,   a n d   h ar d w ar e   i m p le m en ta tio n .   T h e  lat ter   is   d u e  to   t h e  co n s tr ai n ts   o f   tr ad it io n al  C R C   i m p le m en tatio n s   c au s ed   b y   i n cr ea s i n g   d ata  r ates.  Dif f er e n t  h ar d w ar e  i m p le m en ta tio n s   h a v e  b ee n   att e m p ted   to   co p e  w it h   t h is .   An   atte m p t  f o r   b etter   p o ly n o m ial  s elec tio n   f r o m   a  h ar d w ar e  p er s p ec tiv e  w as  d escr ib ed   b y   [ 5 ] .   T h ey   d ev elo p ed   a  p ip elin ed   i m p le m en tatio n   o f   p o l y n o m ia l  d iv i s io n   w h ic h   h elp ed   f o r m   t h e  b asis   o f   a n   e f f ec ti v e   C R C .   I t  i m p r o v ed   s p ee d ,   w h i le  allo w i n g   f o r   d ata  r ates  f r o m   1   Gb its /s   to   4   Gb its /s   o n   f ield - p r o g r a m m ab le   g ate  ar r a y   ( FP G A )   i m p le m e n tatio n s   w i th   r esp e ct  to   t h e  p ar alleliza tio n   le v el  ( f r o m   8   to   3 2   b its ) .   Ho w e v er ,   f aster   d ata  r ates,  i.e .   5   Gb its /s ,   w er e  ac h ie v ed   b y   a n   8 - b it  p ar allel  C R C - 3 2   p r o p o s ed   b y   [ 3 ]   to   m atc h   th e  h ig h   th r o u g h p u t  o f   U SB   3 . 0 .   I t  also   p r o v ed   th at  an   8 - b it  p a r allel  C R C - 3 2   w a s   m u c h   f a s ter   th a n   it s   s er ial   co u n ter p ar t.  Desp i te  t h e  i m p r o v e m e n t,  it  is   o v er s h ad o w ed   b y   r esear ch   d o n e   b y   [ 6 ]   w h o   p r o p o s e  a  C R C   cir cu it u s ab le  f o r   1 0 Gb p ,   u tili zin g   t h e  s tate - s p ac e  tr an s f o r m atio n   m et h o d .   I m p r o v in g   C R C   i m p le m en tati o n   f r o m   a  s o f t w ar e  p er s p ec tiv e  r eq u ir es  in cr ea s in g   o p ti m i za tio n   o f   a   p o p u latio n   o f   p o l y n o m ia ls   o r   f in d i n g   o t h er   w a y s   s u c h   a s   r ed u cin g   t h e  i n itial  s ea r ch   p o p u latio n   s et  o f   p o ly n o m ia ls .   C h o o s in g   d if f er en t  p o l y n o m ial s   f o r   ce r tain   d ata  w o r d   len g t h s   an d   b it  len g th s   o f f er   d if f er en t   lev els   o f   o p ti m izatio n .   A   p o l y n o m ial   s elec tio n   p r o ce s s   f o r   em b ed d ed   n et w o r k   ap p licatio n s   a n d   a  s et  o f   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I J E C E   Vo l.  7 ,   No .   1 ,  Feb r u ar y   201 7   :  5 2 1   –   525   522   "g o o d "   g en er al - p u r p o s e  p o l y n o m ials   h a s   b ee n   d escr ib ed   b y   [ 1 ] .   A   co llec tio n   o f   3 5   n e w   p o ly n o m ia ls   a lo n g   w it h   1 3   p r ev io u s l y   p u b lis h ed   p o ly n o m ia ls   t h at  p r o v id e  g o o d   p er f o r m a n ce   f o r   C R C s   b et w e en   3 -   a n d   1 6 - b it f o r   d ata  w o r d   len g t h s   u p   to   2 0 4 8   b its   w er e  lis ted .   I t  also   d is cu s s es  a  co u p le  o f   co m p ar is o n   ca s e  s tu d ies  b et w ee n   a   s et  o f   c u r r en t  p r o to co ls   n a m e l y   USB   w it h   I T U  ( f o r   5 - b it  C R C s )   a n d   d if f er en t  8 - b it  p o ly n o m ial s .   T h e  ca s e  s tu d ie s   ar e  u s ed   to   p r o v e  h o w   u s i n g   d if f er en t  p o l y n o m ial s   a f f ec t  t h e  p er f o r m a n ce   o f   er r o r   d etec tio n   an d   h o w   h ig h er   le v el s   o f   o p ti m izatio n   m a y   b e  ac h iev ed   b y   u s in g   n e w er   p u b lis h ed   C R C   p o l y n o m i als.  T h e  p ap er   th e n   p r o v id es  an   ex h au s ti v e  s u r v e y   o f   C R C   p o l y n o m ials   f r o m   3 -   to   1 5 - b it  alo n g   w ith   a  d is cu s s io n   o f   1 6 - b it  p o ly n o m ia ls .   T h e  p ap er   also   d ef in e s   " g o o d "   p o ly n o m ia l s   as  th o s e  ac h ie v i n g   t h e  m ax i m u m   Ha m m i n g   Dis ta n ce   f o r   th e  lo n g est  d ata  w o r d   alo n g   w it h   o th er   co n s id er atio n s .   Desp ite  th e  co m p r e h en s i v e  n at u r e  o f   th is   r esear ch ,   C R C   co d es  b e y o n d   1 6   p ar ity   b its   w er e  av o id ed   d u e  to   t h e  lar g e  n u m b er   o f   p o s s ib ilit ies   th a t  h ad   to   b e  in v est ig ated .   Ho w ev er ,   ce r tain   clas s es  o f   2 4 -   an d   3 2 - b it  C R C   co d es  w er e  in v es tig a ted   b y   [ 7 ] ,   w h er ea s   a   co m p r e h en s iv e  s ea r ch   f o r   C R C   co d es  w i th   3 2   p ar it y   b its   w a s   u n d er tak en   b y   [ 8 ] .   Si m i lar   to   [ 1 ] ,   an   an al y s is   o f   C R C   co d e  s tan d ar d s ,   n a m el y ,   C R C - 1 2 ,   A NSI   a n d   C C I 7 T   X. 2 5 ,   p r o v ed   th at  th e   s ta n d ar d s   w er e  n o t  o n   p ar   w ith   t h e  b est   p o s s ib le  C R C   i m p le m en ta tio n s   a n d   t h at  t h e  s it u atio n   s ee m ed   u n l ik el y   to   ch a n g e  d u e  to   ec o n o m ic  co n ce r n s   [ 4 ] .   T h is   co u p led   w it h   t h e  u s e  o f   C R C s   in   h i g h - t h r o u g h p u t  ap p licatio n s   s u ch   a s   USB   3   [ 3 ] ,   h as  m ad e  p ar allel  C R C   cir c u itr y   d esi g n ,   an   i m p o r tan t a r ea   o f   r esear ch   [ 9 ] .   P er f o r m a n ce   o f   C R C   i m p le m en tatio n s   cr ea ted   b y   p o l y n o m ials   w it h   a  d eg r ee   o f   1 6   an d   ab o v e  f o r   er r o r   d etec tio n   in   co m m u n ic atio n   s y s te m s   w as  e v al u ated   b y   [ 4 ] .   T h e  p r o p er ties   o f   m i n i m u m   d is tan ce ,   " p r o p er n ess "   an d   u n d etec ted   er r o r   p r o b a b ilit y   f o r   b in ar y   s y m m etr ic   ch a n n els   ( B SC )   ar e  ca lcu lated   a n d   co m p ar ed   w it h   ex i s ti n g   s tan d a r d s .   T h e  co r e   o f   C R C   i m p le m en ta tio n s   d ep en d s   o n   th e  p o l y n o m ial  ch o s en .   Desp ite  t h eir   i m p o r tan ce   in   en s u r in g   d ata  in te g r it y ,   a  co m p r eh en s i v e  r esear ch   d is c lo s ed   th at  m o s t  p u b lis h ed   C R C   p o l y n o m ial s   ar e  eith er   o p tim a l  w h en   l i m ited   to   ce r tain   m ess a g e  le n g th s   o r   in f er io r   t o   alter n ativ e s .   T h e  latter   is   s u p p o r ted   b y   t h e  f ac t   th at  m a n y   ap p licatio n s   u ti lize  C R C s   th at   o f f er   m u c h   le s s   er r o r   d etec tio n   ca p ab ilit y   t h a n   p o s s ib le  f o r   a  ce r tain   C R C   b it  v al u e.   T h is   m a y   also   b e  s u p p o r ted   b y   th e   lack   o f   " to o ls   an d   d ata  tab les"   f o r   m ea s u r i n g   p o l y n o m ial   p er f o r m a n ce   [ 1 ] .   W ith   r eg ar d s   to   p o l y n o m ial  s elec tio n ,   t h e  c u r r en t  la n d s ca p e  s u f f er s   f r o m   th r ee   i s s u es :  ( 1 )   lacu n ae   ex is t   i n   t h e   cu r r en t  p u b li s h e d   p o ly n o m ials   s et   ( 2 )   n o   s p ec if ic   g u id an ce   ex is t s   o n   t h e  v iab ilit y   o f   ce r tai n   p o ly n o m ia ls   in   ce r tai n   co n tex t s ,   an d   ( 3 )   lacu n ae   w it h   r esp ec t  to   p u b lis h ed   q u an titati v e  an al y s e s   [ 1 ] .   R esear ch   h as  s h o w n   th a t  v ar y in g   p o l y n o m ial s   w it h i n   a  ce r tain   s ize   as  w e ll  as  v ar y i n g   th e  s ize,   p r o d u ce s   d if f er en t  r esu lt s   w it h   r es p ec t to   er r o r   d e tectin g   p er f o r m a n ce   [ 4 ] .       2.   M E T H O D O L O G Y   W ith   r eg ar d s   to   e m b ed d ed   n et w o r k s ,   an   attr ib u te  o f   co n ce r n   w it h   C R C   i m p le m e n ta tio n   is   t h e   Ha m m i n g   D is ta n ce   ( HD)   [ 1 ] .   HD  is   th e  lea s t  b it  in v er s io n s   t h at  h a v e  to   b e  in te g r ated   in to   a  m es s a g e  to   g en er ate  a n   er r o r   th at  i s   " u n d etec tab le  b y   t h at  m ess a g e ' s   C R C - b ased   Fra m e  C h e ck   Seq u e n ce " .   T h e  p r o b a b ilit y   o f   s u c h   a  d ata  co r r u p tio n   o cc u r r in g   i s   s m all  b u t  n o n et h eles s ,   th e  lea s t  n u m b er   o f   b it  in v er s io n s   i n   o r d er   to   ac h iev e   th e   a f o r e m e n tio n ed   u n d etec tab le  er r o r s   i s   c r u cial  i n   C R C   p o l y n o m ial   d es ig n   [ 1 ] ;  s ize   o f   b its   an d   d ata  w o r d s   ar e  also   to   b e  co n s id er ed   s in ce   t h e y   a f f ec t e r r o r - d etec tio n   p er f o r m an ce   [ 4 ] .   C o n n ec ted   w it h   HD  is   th e  at t r ib u te,   Ha m m i n g   W eig h t  ( H W ) .   Fo r   a  HW   o f   N,   N  is   t h e   n u m b er   o f   u n d etec ted   er r o r   p r o b a b ilit ies  b y   a  C R C   i m p le m en tatio n   w i th   r esp ec t  to   a  s p ec i f ic  p o l y n o m ial.   A   co llectio n   o f   HW s   ca p t u r es   p er f o r m a n ce   f o r   d i f f er e n t  n u m b er s   o f   b it s   co r r u p ted   in   a  m e s s a g e  at   a  p ar ticu lar   d ata  w o r d   len g th .   T h e  f ir s t n o n - ze r o   Ha m m in g   w ei g h t d eter m i n es a   c o d e’ s   HD.   T h e  g o al  o f   f i n d in g   a  g o o d   C R C   p o l y n o m ial  is   to   e n s u r e  o p ti m izatio n ,   i.e . ,   to   m ax i m ize   th e  HD  a n d   m i n i m ize  th e  HW .   T h e  class ical  w a y   to   f i n d   s u c h   p o l y n o m i als  is   to   tr y   all  p o s s ib le  ca s es  o f   p o ly n o m ia ls   an d   d ata  b it  er r o r s   ( 1 - ,   2 - ,   3 - ,   m es s ag e  len g t h   er r o r s ) ,   an d   th en   s elec t  th e  o p ti m al  o n e.   T h is   m e th o d   is   s u itab le  f o r   s m al l  v alu e s   o f   d ata  w o r d   l en g t h s   a n d   p o l y n o m ial   d eg r ee .   Ho w e v er ,   f o r   lar g er   v al u es,  co m p u tat io n al   co m p le x it y   i n cr ea s es a n d   th u s   m ak e s   s o l u tio n s   i m p o s s ib le  o n   to d ay ' s   co m p u ter s .   W e  p r o p o s e  s o lv in g   t h e  is s u e  o f   r ed u cin g   co m p u tatio n al  co m p lex i t y   b y   u s i n g   t h e  co n ce p t   o f   Gen etic   A l g o r ith m s   ( G A ) ,   th u s   tr ea ti n g   t h e  p r o b le m   as  an   o p ti m izatio n   p r o b lem .   G A   i s   a  t y p e  o f   ev o lu tio n ar y   co m p u tatio n   m et h o d ,   b u t  h a s   n o   ag r ee d   u p o n   d ef i n itio n   w h ich   d i f f er en tiate s   it  f r o m   o th er   ev o l u tio n - co m p u tatio n   m et h o d s .   Ho w e v er ,   t h er e  ar e  s o m e  f ea t u r es   w h i c h   co n s is te n tl y   p r ese n t  th e m s el v es   i n   G A  m et h o d s :  “ p o p u latio n s   o f   ch r o m o s o m e s ,   s elec tio n   ac co r d in g   to   f itn e s s ,   cr o s s o v er   to   p r o d u ce   n e w   o f f s p r i n g ,   an d   r an d o m   m u tatio n   o f   n e w   o f f s p r in g . ” [ 1 0 ] .   A ls o ,   g e n etic  al g o r ith m s   h av e  b ee n   ap p lied   in   v ar io u s   ap p licatio n s   in   co m m u n icatio n   [ 1 1 ] ,   [ 12] .    GAs  h elp   r ed u ce   t h e  p o p u lati o n   o f   a  ce r tain   p r o b le m   s et  b y   p er f o r m i n g   a  d ir ec ted   s ea r ch   [ 1 3 ] .   T h is   is   i n   co n tr ast  to   th e   clas s ical   m et h o d ,   w h ic h   i s   r a n d o m   i n   n atu r e  a n d   r eq u ir es  g o i n g   t h r o u g h   a ll  m e m b er s   o f   th e  p r o b lem   s et ' s   p o p u latio n .   Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I SS N:  2088 - 8708     N ew He u r i s tic  Mo d el  fo r   Op ti ma l CRC   P o lyn o mia l   ( A h med   S a lih   K h ir b ee t )   523   GA   al lo w s   m o v e m en t  f r o m   o n e  s et  o f   d ata  r ep r esen ted   i n   b in ar y   ( " ch r o m o s o m es" )   in   th e  s ea r c h   s p ac e  to   a  n e w   o n e  b y   p er f o r m i n g   a  t y p e  o f   " n atu r al   s elec t io n " ,   as  is   p r esen t   in   n a tu r e.   I t  u t ilizes   g e n etic s - in s p ir e d   o p er ato r s :  c r o s s o v er ,   m u tatio n ,   an d   in v er s io n .   Si m i l ar   to   th e  n atu r al  in s p ir atio n   it  w a s   d er iv ed   f r o m ,   ea ch   " ch r o m o s o m e"   co n s is t s   o f   " g en es" .   " Gen es"   in   t u r n   r ep r esen t  a n   i n s ta n ce   o f   a  ce r t ain   " allele" ,   i.e . ,   0     o r   1 .   " C h r o m o s o m es"   ar e  s elec ted   o n   th eir   f itn e s s   to   r ep r o d u ce ;  f itter   ch r o m o s o m e s   o n   av er ag e  p r o d u ce   m o r e   o f f s p r in g .   T h e  Op er ato r s   th e n   d ef i n e  h o w   n e w   " ch r o m o s o m es"   ar e  to   b e  s elec ted   u n til   an   o p tim a l  s o l u tio n   i s   r ea ch ed   [ 1 0 ] .   I n   r elatio n   to   th e   ca s e  a t  h an d ,   th e  h ig h es t  p o s s ib le  d e g r ee   f o r   an y   p o l y n o m ial  i s   n .   T h er ef o r e,   th e   len g th   o f   ea c h   ch r o m o s o m e  is   n   an d   ea ch   ch r o m o s o m e  is   p ad d ed   w it h   “ 1 ”s  w h ic h   r ep r esen t  th e  co n s ta n t  i n   th e  p o l y n o m ial.   HD  h as  b ee n   u s ed   as  a  co n s tr ain t,  s o   ea ch   c h r o m o s o m e   th at  d o es  n o t  s atis f y   th e  co n s tr ai n t  is   r ej ec ted .   B ef o r e  s tar tin g   a  s e ar ch   p r o ce s s ,   th e  u s er   m u s t  d eter m i n e  b it  er r o r   ca s es  ( f r o m   1   to   th e  r eq u ir ed   v alu e  o f   b it  er r o r s ) ,   th e  m a x i m u m   n u m b er   o f   co m b in a tio n s   f o r   ea ch   ca s e,   an d   th e  m ess ag e  len g t h .   B ec au s e  b in ar y   r ep r esen tatio n   h a s   b ee n   u s ed ,   t h e  v alu e s '   lo w er   b o u n d   is   ze r o   ( 0 )   w h ile  t h e  h i g h e r   b o u n d   is   o n e  ( 1 ) .   T h e  v alu e s   ar e  al w a y s   in teg er s   ( GF( 2 ) ) .   T h e  tar g et  o f   t h e  o p ti m izatio n   p r o ce s s   i s   to   m i n i m ize  t h e  f o llo w i n g   f u n ctio n :          ∑                                                                    T h e  Fit n ess   Val u e  ( FV)   eq u at io n   clar if ies  t h at  in cr ea s in g   t h e  n u m b er   o f   u s ed   co m b in atio n s   m ak e s   th e  r esu ltan t so lu tio n   n ea r er   to   th e  b est s o lu tio n ,   b u t  n o t  w it h o u t in cr ea s i n g   th e  co m p u tat io n al  co m p le x it y .   Data   i n teg r it y   o f   t h e  d ata   p ac k ets   tr an s f er r ed   ca n   b e  e n s u r ed   b y   u s in g   e n cr y p t io n .   O n e   o f   s ec u r e   cip h er   o p er atio n 's  p r in cip le s   is   d if f u s io n .   I t  is   s atis f ied   w h e n ,   if   a   s i n g le  b it  o f   t h e  p lai n   te x t   is   c h an g ed ,   e v er y   b it  o f   th e  cip h er   tex t  ch an g es  w it h   a  p r o b ab ilit y   o f   0 . 5   an d   v ice  v er s a.   T h is   is   u s e f u l  f o r   th e  s ce n ar io   at  h an d   as  an y   er r o r   th at  o cc u r s   in   t h e  m es s a g e  d u r in g   tr an s m i s s io n   w i ll  ca u s e  a  lar g e  n u m b er   o f   er r o r s   in   th e  m es s ag e  a f ter   d ec r y p tio n   w h ich   i n   tu r n   h elp s   t h e  n e x t  s tag e  ( C R C   d etec to r )   to   r e d u ce   th e  n u m b er   o f   u n d etec ted   er r o r s .   T h e  n u m b er   o f   u n d etec ted   er r o r s   ca n   b e  f u r th er   r ed u ce d   b y   en s u r i n g   ea c h   d ata  p ac k et   co n tain s   a  h ea d er   w h ich   is   k n o w n   to   b o th   th e  s en d er   an d   r e ce iv er .   T h u s ,   if   th e  er r o r   is   u n d etec ted   u s in g   FC S,   it c an   b e  d etec ted   b y   ch ec k i n g   f o r   ch an g es i n   t h e  h ea d er   af te r   d ec r y p tio n .   T h e  A d v a n ce d   E n cr y p tio n   S tan d ar d   ( A E S)  s p ec if ica tio n   w il l  b e  u s ed   f o r   e n cr y p tio n   f u n ct io n s   r elatin g   to   h ea d er s .   T h e  s p ec i f icatio n   [ 1 4 ]   d ef in es  i t  as  a  b lo ck   cip h er   w h ic h   ca n   b e  u s ed   b o th   w a y s ,   i.e . ,   to   en cr y p t  i n f o r m atio n   i n to   cip h er tex t  a n d   also   to   d ec r y p t  t h e  r esu lta n t  cip h er tex t  b ac k   in to   its   o r ig in al   f o r m .   I t  is   a  s y m m etr ic - k e y   al g o r ith m ,   w h ic h   m ea n s   t h at  t h e  s a m e   k e y   i s   u s ed   f o r   b o th   en cr y p t io n   a n d   d ec r y p tio n   f u n ctio n s .   I t   ca n   en cr y p t  a n d   d ec r y p t   d ata  i n   1 2 8 - b it  b lo c k s   b y   u s in g   1 2 8 ,   1 9 2 ,   an d   2 5 6 - b it  cr y p to g r ap h ic   k e y s .   W e  w il l b e  u s i n g   a  1 2 8 - b it c r y p to g r ap h ic  k e y   f o r   o u r   a p p licatio n .       3.   RE SU L T S  A ND  D I SS CUSS I O N   T o   v alid ate  th e  p r o p o s ed   m et h o d ,   w e  co n d u cted   e x p er i m e n ts   u s i n g   t h e  M A T L A B   en v ir o n m en t  w it h   its   b u ilt - i n   G A   to o lb o x .   T h e  f ir s t  e x p er i m e n t  co n s is ted   o f   d ata  p ac k ets  o f   4 8   b its ,   an d   w h er e  th e  h ig h es t  d eg r ee   o f   th e  g en er ato r   p o ly n o m ial  w as  1 6 .   B i t  er r o r   ca s es  r an g ed   f r o m   1   to   6f   b its ,   an d   f o r   ea ch   ca s e,   1 0 , 0 0 0   co m b i n atio n s   w er e  test ed   at  m o s t.   T h e  HD  w a s   ch o s e n   to   b e  a t  m in i m u m ,   6 .   T h e  b en ch m a r k   ch o s en   f o r   th is   ex p er i m en t  w as  t h e   p o ly n o m ia l  f o u n d   b y   [ 4 ] ,   w it h   a  h ex   v al u e  o f   0 x C 8 6 C .   A n   a n al y s i s   b y   [ 1 ]   f o u n d   it  to   th e  b est  a m o n g s t  m an y   o th er s   f o r   a  d ata  w o r d   s ize  o f   4 8   b its .   R esu lt s   ar e  s h o w n   in   T ab le  1 .       T ab le  1 .   R esu lta n t P o ly n o m ial   Vs  [ 4 ] ,   T ested   W ith   1 0 , 0 0 0   C o m b i n atio n s   HD   P o l y n o mi a l   1   b i t   2   b i t s   3   b i t s   4   b i t s   5   b i t s   6   b i t s   N o .   o f   U n d e t e c t e d   Er r o r s   R e su l t a n t   0 x 8 4 1 1   5   0   0   0   0   1 8 3   1 2 6 7   1 4 5 0   [ 4 ]   0 x C 8 6 C   6   0   0   0   0   0   2 1 9 1   2 1 9 1       A lt h o u g h   t h e   r esu ltan t  p o l y n o m ial   h a s   a   lo w er   HD   th a n   [ 4 ] ,   th e  s u m   o f   u n d etec ted   er r o r s   in   5 - b i t   an d   6 - b it  ca s e s   is   lo w er   t h an   u n d etec ted   er r o r s   in   [ 4 ]   f o r   6   b its .   As  p r ev io u s l y   m e n tio n ed ,   in cr ea s i n g   th e   m ax i m u m   n u m b er   o f   co m b i n atio n s   m a k es  t h e  s o l u tio n   n ea r er   to   th e  b est  s o lu t io n .   T h er ef o r e ,   an o th er   ex p er i m e n t  w a s   co n d u cted ;  t h is   ti m e,   m ak in g   t h e  m a x i m u m   n u m b er   o f   co m b in a tio n s ,   3 0 0 , 0 0 0 .   T h e  r esu lt s   ar e  s u m m ar ized   i n   T ab le  2 .   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I J E C E   Vo l.  7 ,   No .   1 ,  Feb r u ar y   201 7   :  5 2 1   –   525   524       T ab le  2 .  R esu lta n t P o ly n o m ial   Vs  [ 4 ] ,   T ested   W ith   3 0 0 , 0 0 0   C o m b i n atio n s   HD   P o l y n o mi a l   1   b i t   2   b i t s   3   b i t s   4   b i t s   5   b i t s   6   b i t s   N o .   o f   U n d e t e c t e d   Er r o r s   R e su l t a n t   0 x 9 9 4 7   5   0   0   0   0   57   1 1 6 3   1 2 2 0   [ 4 ]   0 x C 8 6 C   6   0   0   0   0   0   2 1 9 1   2 1 9 1       I t  is   clea r   th at   t h e  n e w   r es u lta n t  p o l y n o m ial  i s   ab le  to   d etec t  m o r e  er r o r   ca s es  th a n   t h e   p r ev io u s   o n e ,   an d   th u s   [ 4 ] ' s   a s   w ell.   T h e  n u m b er   o f   u n d etec ted   er r o r   p r o b ab ilit ies  h as  d ec r ea s ed   s ig n i f ican tl y   f r o m   th e   p r ev io u s   ex p er i m en t,  r es u lti n g   in   5 7   co m p ar ed   w it h   1 8 3   f r o m   th e  p r ev io u s   e x p er i m e n t,  f o r   5 - b its .   T h e  i m p r o v e m en t i n   6 - b it s   w as  n o t sig n i f ican t b u t n o n et h eles s   s ti ll b etter   b y   1 0 4   u n d etec ted   er r o r   p r o b ab ilit ies.   I n   o r d er   to   v alid ate  th e  ef f ec t   o f   en cr y p tio n   in   lo w er in g   th e  n u m b er   o f   u n d etec ted   er r o r s ,   an o th er   ex p er i m e n t  w as  co n d u cted .   T h is   t i m e,   a  d ata  w o r d   s ize  o f   1 1 2   w as  u s ed   an d   t h e  h ig h es t  p o s s ib le  p o l y n o m ial   d eg r ee   w a s   1 6 .   B it  er r o r   ca s e s   r an g ed   f r o m   1   to   6   b its ,   an d   4 0 0 , 0 0 0   c o m b i n atio n s   at  m o s t,  w er e  te s ted   f o r   ea ch   ca s e.   T h e  HD  co n s tr ai n t  w a s   lef t a s   is ,   w it h   a  m in i m u m   v alu e  o f   6 .   T ab le   3   s h o w s   th e  r es u lta n t  p o ly n o m ial,   th e  n u m b er   o f   u n d etec ted   er r o r s ,   th e  n u m b er   o f   u n d etec ted   er r o r s   w ith   e n cr y p tio n ,   an d   t h e  n u m b er   o f   u n d etec ted   er r o r s   w it h   e n cr y p tio n   alo n g   w it h   a  h ea d er   o f   o n e - b y te   s ize,   w h er e  4   m illi o n   co m b i n a tio n s   o f   6 - b it  er r o r s   h av e  b ee n   r an d o m l y   ch o s e n   an d   test ed .   T h e  d ata  w o r d   s ize  w a s   1 1 2   b it.  T h e  b en ef it  o f   ad d in g   en cr y p tio n   as  w e ll  as   a  h ea d er   ca n   b e  clea r ly   s ee n .   T h e  n u m b er   o f   u n d etec ted   er r o r   p r o b ab ilit ies  w it h o u t  en cr y p tio n   a n d   a  h ea d er   w as  1 4 1 .   A d d i n g   e n cr y p ti o n   r ed u ce d   it  to   6 0   an d   ad d in g   a  h ea d er   alo n g   w i th   en cr y p tio n   d ec r ea s ed   it  ev en   f u r th er ,   en ab li n g   t h e  C R C   i m p le m e n tatio n   to   ca tch   all  p o s s ib le  er r o r s .       T ab le  3 .   No .   Of   Un d etec ted   E r r o r   P r o b ab ilit ies f o r   t h e  P o ly n o m ial  0 x 8 9 4 8   P o l y n o mi a l   C R C   C R C   a n d   E n c r y p t i o n   C R C   a n d   E n c r y p t i o n   w i t h   H e a d e r   0 x 8 9 4 8   1 4 1   60   0       4.   CO NCLU SI O N   AND  F U T U RE   WO RK   Ou r   w o r k   s h o w ed   h o w   u s in g   a  GA   ap p r o ac h   d ec r ea s ed   th e  n u m b er   o f   p o s s ib le  s o lu t io n   ca n d id ates   f o r   f i n d in g   a n   o p ti m al  p o l y n o m ial  f o r   u s e  in   a  C R C   i m p le m en tatio n .   W e  co m p ar ed   th e  r e s u lta n t  p o l y n o m ials   ag ain s t  a   b en c h m ar k   [ 4 ]   f o r   a   d ata  w o r d   le n g t h   o f   4 8   b its .   W e  also   ev al u ated   t h e  e f f ec t  o f   e n cr y p tio n   o n   d ata   h ea d er s   in   a  C R C   i m p le m en tatio n ;  w e  f o u n d   th at   en cr y p tio n   i m p r o v es  p er f o r m a n ce   o f   a  C R C   i m p le m en ta tio n .   Ou r   ev al u atio n ,   h o w ev er ,   is   n o t  co m p r eh en s i v e  w h ic h   l ea v es  r o o m   f o r   f u t u r e  w o r k .   A   m o r e   th o r o u g h   e v al u atio n   o f   u s i n g   GA  f o r   d i f f er e n t  d ata  w o r d   le n g t h s   a n d   C R C   b it   len g t h   w o u ld   ad d   s tr en g t h   to   th e  p r o p o s al  at  h a n d .   Si m i lar ly ,   a  t h o r o u g h   b e n ch m ar k   an a l y s i s   o f   r es u lta n t  p o l y n o m ials   u s in g   G A  f o r   th e   v ar io u s   d ata  w o r d   le n g th s   a n d   C R C   b it le n g th   w o u ld   p r o v e  t h e  v alid it y   o f   o u r   m e th o d   ac r o s s   a  w id er   s co p e  o f   C R C   i m p le m e n tatio n s .       ACK NO WL E D G E M E NT S   T h e  r esear ch er s   w is h   to   t h an k   Un i v er s iti   Keb an g s aa n   Ma la y s ia  ( UK M)   f o r   s u p p o r tin g   t h is   w o r k   b y   r esear ch   g r an ts : D a n a  I m p a k   P er d an a  ( DI P - 2 0 1 4 - 0 3 7 ) .       RE F E R E NC E S   [1 ]   P .   Ko o p m a n   a n d   T .   Ch a k ra v a rty ,   “ C y c li c   Re d u n d a n c y   Co d e   (CRC)  P o ly n o m ial  S e l e c ti o n   F o r  Em b e d d e d   Ne tw o rk s” ,   In t.   Co n f.   De p e n d a b l e   S y st.  Ne two rk s ,   2 0 0 4 ,   p p .   1 – 1 1 ,   2 0 0 4 .   [2 ]   V .   Ch e a ,   M . V.  M a rti n ,   a n d   R.   L i sc a n o ,   “ Ha m m in g   d istan c e   a s  a   m e tri c   f o r  th e   d e tec ti o n   o f   c rc - b a se d   sid e - c h a n n e l   c o m m u n ica ti o n s  in   8 0 2 . 1 1   w irele ss   n e tw o rk s” ,   in   IEE E  c o n fer e n c e   o n   c o mm u n ica ti o n s  a n d   n e two rk   s e c u rity  ( c n s) ,  2 0 1 5 ,   p p .   2 1 8 – 2 2 6 .   [3 ]   Y.  W u   a n d   Y.  Qiu ,   “ T h e   8 - b it   p a ra ll e l  c rc - 3 2   re se a r c h   a n d   im p le m e n tatio n   i n   u sb   3 . 0 ” ,   in   I n ter n a t io n a l  c o n fer e n c e   o n   C o mp u ter   sc ien c e   se rv ice   s y st e m ( c ss s) ,   2 0 1 2 ,   p p .   1 0 7 9 – 1 0 8 2 .   [4 ]   T .   Ba ich e v a ,   S .   Do d u n e k o v ,   a n d   P .   Ka z a k o v ,   “ Un d e tec ted   e rro r  p ro b a b il it y   p e rf o r m a n c e   o f  c y c li c   re d u n d a n c y - c h e c k   c o d e s o f   1 6 - b it   re d u n d a n c y ” ,   in   IE E  Pro c e e d i n g s  -   C o mm u n i c a ti o n s ,   v o l.   1 4 7 ,   n o .   5 ,   p p .   2 5 3 – 2 5 6 .   [5 ]   F .   M o n teiro ,   A .   Da n d a c h e ,   A .   M ’S ir,   a n d   B.   L e p ley ,   “ A   p o l y n o m ial  d iv isio n   p i p e li n e d   a rc h it e c tu re   f o r  c rc   e rro r  d e tec ti n g   c o d e s” ,   in   T h e   1 3 th   i n te rn a ti o n a l  c o n fer e n c e   o n   M icr o e lec tro n ics ,   2 0 0 1 ,   v o l .   1 3 ,   p p .   1 3 3 – 1 3 6 .   Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I SS N:  2088 - 8708     N ew He u r i s tic  Mo d el  fo r   Op ti ma l CRC   P o lyn o mia l   ( A h med   S a lih   K h ir b ee t )   525   [6 ]   J.S .   L in ,   C. K.  L e e ,   M . D.   S h ieh ,   a n d   J.H.   Ch e n ,   “ Hig h - sp e e d   c rc   d e sig n   f o r  1 0   g b p s  a p p li c a ti o n s” ,   i n   I EE E   in ter n a t io n a l   sy mp o siu m  o n   c irc u it s a n d   sy ste ms ,   2 0 0 6 ,   p .   4 .   [7 ]   G .   Ca sta g n o li ,   S .   Bra u e r,   a n d   M .   He rr m a n n ,   “ Op ti m iza ti o n   o f   c y c li c   re d u n d a n c y - c h e c k   c o d e s  w it h   2 4   a n d   3 2   p a rit y   b it s ” ,   IEE E   T ra n s.  C o mm u n . ,   v o l.   4 1 ,   n o .   6 ,   p p .   8 8 3 – 8 9 2 ,   1 9 9 3 .   [8 ]   P .   Ko o p m a n ,   “ 3 2 - b it   c y c li c   r e d u n d a n c y   c o d e s  f o r  in tern e t  a p p li c a ti o n s” ,   in   I n ter n a t io n a l  c o n fer e n c e   o n   d e p e n d a b le  sy ste ms   a n d   n e tw o rk s ,   2 0 0 2 ,   p p .   4 5 9 – 4 6 8 .   [9 ]   K.  W it z k e   a n d   C.   L e u n g ,   “ A  c o m p a riso n   o f   so m e   e rro r  d e tec ti n g   c rc   c o d e   sta n d a rd s” ,   IEE E  T ra n s .   Co mm u n . ,   v o l.   3 3 ,   n o .   9 ,   p p .   9 9 6 – 9 9 8 ,   1 9 8 5 .   [1 0 ]   M .   M it c h e l l,   A n   i n tro d u c ti o n   to   g e n e ti c   a lg o rith ms .   Bra d f o rd   B o o k s,  1 9 9 8 .   [1 1 ]   J.  M o h a m m e d ,   “ Co m p a ra ti v e   P e rf o r m a n c e   In v e stig a ti o n s  o f   S to c h a stic  a n d   G e n e ti c   A lg o rit h m s  Un d e r  F a st   D y n a m ica ll y   Ch a n g in g   En v iro n m e n t  in   S m a rt  A n ten n a s” ,   In t.   J .   El e c tr.   Co mp u t.   En g . ,   v o l .   2 ,   n o .   1 ,   p p .   9 8 – 1 0 5 ,   2 0 1 2 .   [1 2 ]   N.  Jia n g ,   S .   Jin ,   Y.  G u o ,   a n d   Y.  He ,   “ L o c a li z a ti o n   o f   W irele ss   S e n so r  Ne tw o rk   B a se d   o n   Ge n e ti c   A l g o rit h m ” ,   In t.   J .   Co mp u t.   C o mm u n .   Co n tro l ,   v o l .   8 ,   n o .   6 ,   p .   8 2 5 ,   2 0 1 3 .   [1 3 ]   S .   S iv a n a n d a m   a n d   S .   De e p a ,   In tro d u c t io n   to   g e n e ti c   a l g o rit h ms .   S p rin g e r  Be rli n   He i d e lb e rg ,   2 0 0 7 .   [1 4 ]   “ S p e c if ica ti o n   f o r  th e   a d v a n c e d   e n c ry p ti o n   sta n d a r d   (A ES ), ”   Fed .   I n f.   Pr o c e ss .   S ta n d .   P u b l. ,   2 0 0 1 .       B I O G RAP H I E S   O F   AUTH O RS       Ahm e d   S a li h   K h irbee t   Re se a rc h   Ce n ter f o r  S o f t w a re   T e c h n o lo g y   a n d   M a n a g e m e n t  (S OFT A M )    F a c u lt y   o f   T e c h n o lo g y   a n d   In f o rm a ti o n   S c ien c e     Un iv e rsit y   Ke b a n g sa a n   M a la y si a   a h m e d . sa li h 8 9 @s isw a . u k m . e d u . m y         Ra v ie C h a n d r e n   M u n iy a n d i   Re se a rc h   Ce n ter f o r  S o f t w a re   T e c h n o lo g y   a n d   M a n a g e m e n t  (S OFT A M )    F a c u lt y   o f   T e c h n o lo g y   a n d   In f o rm a ti o n   S c ien c e     Un iv e rsit y   Ke b a n g sa a n   M a la y si a .   ra v ie@ u k m . e d u . m y       Evaluation Warning : The document was created with Spire.PDF for Python.