home *** CD-ROM | disk | FTP | other *** search
/ CP/M / CPM_CDROM.iso / cpm / gendoc / crcart.dqc / CRCART.DOC
Encoding:
Text File  |  1985-02-09  |  3.5 KB  |  82 lines
  1.            From "EDN" magazine, June 5, 1979, page 84
  2.            ------------------------------------------
  3.  
  4.               8080 ROUTINE GENERATES CRC CHARACTER
  5.                          by Fred Gutman
  6.             California Microwave, Inc., Sunnyvale, CA
  7.  
  8. Communications  and magnetic-storage controllers often use cyclic 
  9. redundancy checking (CRC) to enhance data-transmission  accuracy; 
  10. this method's popularity is due, in part, to its easy implementa-
  11. tion  with shift registers and exclusive-OR gates (EDN,  Sept  5, 
  12. 1978, pgs 119-123).
  13.  
  14.   Many  software methods can emulate this hardware mechanization.  
  15. The more natural software method discussed here directly executes 
  16. the division of a message by a generating polynomial. An example, 
  17. programmed on the 8080, appears in the figure.
  18.  
  19.   CRC  divides  a  message M(x) of any  length  by  a  generating 
  20. polynomial  P(x)  to form a quotient Q(x) and a  remainder  R(x): 
  21. M(x)/P(x)=Q(x)+R(x).  R(x) is appended to the message and checked 
  22. at  the receiving end of the communication channel or upon  read-
  23. back of magnetic-storage information.
  24.  
  25.   In  these operations,  addition and division are based  on  the 
  26. exclusive-OR function without carry;  only bit-by-bit differences 
  27. are  important,  not  their arithmetic  sum.   Thus,  while  this 
  28. process resembles nonrestoring binary division, its mechanization 
  29. is  somewhat  simpler.   Note  that you don't have to  store  the 
  30. quotient - the remainder is the only useful part.  This versatile 
  31. method  accepts  different generating  polynomials  (table);  you 
  32. simply insert them into the routine in the figure.  In each case, 
  33. an  R-bit remainder is left in location REM for  transmission  or 
  34. checking.  (R is the order of the generating polynomial.)
  35.  
  36.  
  37.                             TABLE
  38.  
  39.          POLYNOMIAL                MASK         HEX FORM
  40.  
  41. CR16:  x16+x15+x2+1                H=128          8005
  42. SDLC:  x16+x12+x5+1                H=128          1021
  43. CCITT: x16+x15+x10+x6+x5+1         H=128          8461
  44.        x16+x15+x13+x7+x4+x2+x+1    H=128          A097
  45. HDLC:  x14+x2+x+1                  H=128          4007
  46.        x8+x7+x2+1                  L=128          0185
  47. CR12:  x12+x11+x3+x2+x+1           H=8            180F
  48. BCC:   x8+1                        L=128          0101
  49. CR16 REVERSE: x15+x14+x+1          H=128          4003
  50. CCIT REVERSE: x16+x11+x4+1         H=128          0811
  51.               x8+x7+x5+x4+1        L=128          01B1
  52.  
  53.  
  54.                          FIGURE
  55.  
  56. 011F         MESS    DS    1
  57. 0120 0000    REM     DW    0
  58. 0122         DIVP    LHLD  REM   ;REMAINDER
  59. 0125 7C              MOV   A,H
  60. 0126 E680            ANI   128   ;Q-BIT MASK SEE TABLE
  61. 0128 F5              PUSH  PSW   ;SAVE STATUS
  62. 0129 29              DAD   H     ;2 X R(X)
  63. 012A 3A1F01          LDA   MESS  ;MESSAGE BIT IN LSB
  64. 012D 85              ADD   L
  65. 012E 6F              MOV   L,A
  66. 012F F1              POP   PSW
  67. 0130 CA3B01          JZ    $+11  ;IF Q-BIT IS ZERO
  68. 0133 7C      QB      MOV   A,H
  69. 0134 EE10            XRI   10H   ;MS HALF OF GEN. POLY
  70. 0136 67              MOV   H,A
  71. 0137 7D              MOV   A,L
  72. 0138 EE21            XRI   21H   ;LS HALF
  73. 013A 6F              MOV   L,A
  74. 013B 222001          SHLD  REM
  75. 013E C9              RET
  76. 013F                 END   100H
  77.  
  78. An   8080  routine  for  generating   a   cyclic-redundancy-check 
  79. character leaves that character in location REM.
  80.  
  81. END
  82.