home *** CD-ROM | disk | FTP | other *** search
/ Programmer's ROM - The Computer Language Library / programmersrom.iso / ada / general / crc.doc < prev    next >
Encoding:
Text File  |  1988-05-03  |  4.9 KB  |  128 lines
  1.     
  2.  
  3.               8080 ROUTINE GENERATES CRC CHARACTER
  4.                          by Fred Gutman
  5.  
  6.             California Microwave, Inc., Sunnyvale, CA
  7.     
  8.  
  9.         Communications  and  magnetic-storage  controllers  often  use
  10. cyclic  redundancy  checking  (CRC)   to   enhance   data-transmission
  11. accuracy;  this  method's  popularity  is  due,  in  part, to its easy
  12. implementa- tion with shift registers  and  exclusive-OR  gates  (EDN,
  13. Sept 5, 1978, pgs 119-123).
  14.  
  15.         Many software methods can emulate this hardware mechanization.
  16. The  more natural software method discussed here directly executes the
  17. division of  a  message  by  a  generating  polynomial.   An  example,
  18. programmed on the 8080, appears in the figure.
  19.  
  20.         CRC divides a message M(x)  of  any  length  by  a  generating
  21. polynomial  P(x)  to  form  a  quotient  Q(x)  and  a  remainder R(x):
  22. M(x)/P(x)=Q(x)+R(x).  R(x) is appended to the message and  checked  at
  23. the  receiving  end of the communication channel or upon read- back of
  24. magnetic-storage information.
  25.  
  26.         In  these  operations,  addition and division are based on the
  27. exclusive-OR function without carry; only bit-by-bit  differences  are
  28. important,  not  their  arithmetic  sum.   Thus,  while  this  process
  29. resembles nonrestoring binary division, its mechanization is  somewhat
  30. simpler.   Note  that  you  don't  have  to  store  the quotient - the
  31. remainder is the only useful  part.   This  versatile  method  accepts
  32. different  generating polynomials (table); you simply insert them into
  33. the routine in the figure.  In each case, an R-bit remainder  is  left
  34. in  location REM for transmission or checking.  (R is the order of the
  35. generating polynomial.)
  36.  
  37.  
  38.     
  39.                             TABLE
  40.  
  41.          POLYNOMIAL                MASK         HEX FORM
  42.  
  43. CR16:  x16+x15+x2+1                H=128          8005
  44. SDLC:  x16+x12+x5+1                H=128          1021
  45. CCITT: x16+x15+x10+x6+x5+1         H=128          8461
  46.        x16+x15+x13+x7+x4+x2+x+1    H=128          A097
  47. HDLC:  x14+x2+x+1                  H=128          4007
  48.        x8+x7+x2+1                  L=128          0185
  49. CR12:  x12+x11+x3+x2+x+1           H=8            180F
  50. BCC:   x8+1                        L=128          0101
  51. CR16 REVERSE: x15+x14+x+1          H=128          4003
  52. CCIT REVERSE: x16+x11+x4+1         H=128          0811
  53.               x8+x7+x5+x4+1        L=128          01B1
  54.  
  55.  
  56.     
  57.  
  58.  
  59. --------------------------------------------------------------------
  60.  
  61. NOTES FOR REPOSITORY USERS ON SIMTEL20
  62.  
  63.         CRCs  provide  a convenient way to verify that a file received
  64. from a repository is an exact duplicate of the file on the repository.
  65. A  standard  CRC  polynomial  has been selected, and several different
  66. programs have been created which analyze files and compute  the  value
  67. of  this  CRC polynomial when the data in the file is provided as data
  68. for the polynomial.  The following list may prove to be useful:
  69.  
  70.     
  71. Program Name    Implementation        Comments
  72. ------------    --------------        --------
  73.   NCRC        TOPS-20            MICRO:<CPM.TOPS20>
  74.                       NCRC.MID (written in Midas)
  75.   CRC        UNIX            PD:<UNIX.CPM>
  76.                       CRCK2.C (generic C)
  77.   CRC        CP/M            MICRO:<CPM.DIRUTL>
  78.                       CRCKxx.ASM (8080 asm)
  79.                       xx=version number
  80.   CRC        ZCPR3            MICRO:<CPM.ZCPR3>
  81.                       CRC.MAC (8080 asm)
  82.     
  83.  
  84.         Source code is provided for all of the routines listed above.
  85.  
  86.         The repositories on SIMTEL20 contain CRCLST  files,  generated
  87. by NCRC for TOPS-20, which contain the CRCs for the files contained in
  88. them.  The <ADA> repository's CRCLST file is:
  89.  
  90.     
  91.         PD:<ADA>ADA.CRCLST
  92.     
  93.  
  94.         Previous  versions  of  the  CRCLST  are  often  retained  for
  95. historical purposes.  Only the  last  N  versions  of  ADA.CRCLST  are
  96. retained,  where  N  is  indeterminant.   By  using the file reference
  97. specified above, the latest version is always retrieved.
  98.  
  99.  
  100. SAMPLE ADA.CRCLST
  101.  
  102.     
  103. Filename            Type     Bytes     Sectors     CRC
  104.  
  105. Directory PD:<ADA.COMPONENTS>
  106. LIMPRIOR.ADA.2            ASCII      7374   58 =  3AH  364CH
  107. LIMPRIOR.PRO.2            ASCII      3461   28 =  1CH  813DH
  108. LIST.ADA.2            ASCII     17483  137 =  89H  4B17H
  109. LIST.PRO.2            ASCII      3397   27 =  1BH  7780H
  110. PRIOR.ADA.2            ASCII      6398   50 =  32H  A562H
  111. PRIOR.PRO.2            ASCII      3582   28 =  1CH  5060H
  112. SAFEIO.ADA.2            ASCII      9730   77 =  4DH  7E5BH
  113. SAFEIO.PRO.2            ASCII      3661   29 =  1DH  BB29H
  114.  
  115. Directory PD:<ADA.GENERAL>
  116. 00READ.ME.2            ASCII      1578   13 =   DH  84D1H
  117. ADAREPOS.TXT.2            ASCII      3681   29 =  1DH  9B3EH
  118. COPYRITE.DOC.1            ASCII      4434   35 =  23H  206EH
  119. COPYRITE.INF.1            ASCII      5777   46 =  2EH  AEBCH
  120. COPYRITE.TXT.1            ASCII     11313   89 =  59H  9916H
  121. FTP.DOC.1            ASCII     17412  137 =  89H  B0E3H
  122. LBR.DOC.2            ASCII       955    8 =   8H  E967H
  123. MLIST.DOC.1            ASCII       807    7 =   7H  45FBH
  124. PROLOGUE.ADA.1            ASCII      2513   20 =  14H  3CB9H
  125. SAMPLE.PRO.1            ASCII      3461   28 =  1CH  813DH
  126. UUCP-BIT.DOC.1            ASCII      4649   37 =  25H  CCBCH
  127.     
  128.