!pr3
Cyclic Redundancy Check Subroutine.........Bob Sander-Cederlof

In the May 1983 AAL I wrote about checksums and parity, two ways to guarantee the integrity of data.  In the world of microprocessors, you may encounter checksums at the end of data records on tape or disk, and parity bits on characters sent via a modem between computers.  Tacking on parity bits and checksums to data helps in checking whether the data has been changed.  However, there are more secure methods.

The best method I have ever heard of is commonly called Cyclic Redundancy Check, or CRC for short.  Since it appears a lot more complicated than parity or checksum, it stands to reason it should have a more complex name.  Right?  But programmers have a way of reducing all complexity to three capital letters, so we will call it CRC.

First, a little review.  The kind of parity I most frequently see adds an 8th bit on the left of a 7-bit value.  The parity bit is chosen so that the total number of one-bits in the 8-bit byte is odd.  For example, the seven bit number 1011010 (which might stand for an ASCII "Z") becomes 11011010, or $DA.  If we run into the value 01011010 ($5A), we know there has been an error somewhere.  Of course we don't know which bit is wrong, but we know at least one is because the total number of one-bits is even.

Checksums I run into are normally 8-bit or 16-bit "sums" of a large number of bytes or double bytes.  I put "sums" in quotation marks because the checksum may be formed by the exclusive-or operation rather than true addition.  In fact, it usually is.  Eight-bit checksums formed with exclusive-or are in reality a kind of lengthwise parity.  Each bit of the checksum is a parity bit for the column of bits in that position in the block of data.

In the old days, when dinosaurs first began to associate with herds of wildly spinning tape drives, you heard the words "vertical parity" and "longitudinal parity".  Vertical parity was in those days a seventh bit for each six-bit character written on the tape, and longitudinal parity was a 7-bit character tacked on the end of each tape record, just like a checksum.

Enough review.

CRC is a much better scheme.  A typical CRC implementation would add a 16-bit code to the end of a 256-byte block of data.  A simple checksum would warn you of all single-bit errors, and some errors involving more than one bit.  But CRC could detect all single and double bit errors, all errors with an odd number of error bits, all bursts of errors up to 16-bits in a row, and nearly all bursts of 17 or 18 bits in a row.  Wow!

Also, you can even use CRC codes to CORRECT single-bit errors, if you trade off against some detection of longer error bursts.
!np
You will run into CRC if you look into hard disks, or well- written modem software.

I like to write well-written programs, so I have been trying to understand CRC for some time now.  A long time ago I had access to a book called "Error Correcting Codes", which is a classic.  But I can't locate a copy now.  I have seen numerous articles on the topic, especially in Computer Design.  There was even one in Byte, Sept. 83, page 438.  But I couldn't make the program in Byte work the way CRC's are supposed to, and I don't save my old Computer Design magazines.

Bobby Deen to the rescue.  Bobby had a copy of a public domain routine by Paul Hansknecht, of Carpenter Associates, Box 451, Bloomfield Hills, MI 48013.  Actually four little subroutines, to:

     * clear the CRC code value
     * cycle the eight bits of a data byte
       through the CRC algorithm
     * finish the CRC calculation for an outbound message
     * check the CRC bytes of a received message.

What is the basic idea of CRC?  You perform an algorithm on each bit of a block of data, and get a CRC value.  You append the CRC value to the data, and transmit both data and CRC.  The receiver performs the same algorithm on the total record, both the data and the CRC code; when finished, the result of the receiver's CRC algorithm should be zero.  If not zero, there was an error.

I am speaking in terms of sending and receiving, as in transmitting data with a modem.  It all applies equally to writing and reading records on a disk, or even in adding check codes to a ROM.  The programs I wrote and will list here merely operate on a buffer in RAM, so that I can see what is happening.  You can extend them to practical uses from this base.

Which brings us to algorithms.  The one Bobby gave me works like this:







The 16-bit value is initialized to zero.  Then each bit in the data buffer is presented one at a time where the input arrow is.  The bits in the 16-bit value are all shifted left one position, and the new data bit comes in the right end to become the new bit 0.  The bit which shifts out the left end is Exclusive-ORed with the bits now found in bits 12, 5, and 0.  That is, if the bit shifted out was a zero, nothing happens.  If the bit shifted out was a one, exclusive or the 16 bit value with $1021.

If you understand the math of cyclic polynomials (I don't), this is supposed to be equivalent to X^16 + X^12 + X^5 + 1.  An organization known to me only as CCITT recommends this polynomial.  Another good one is reputed to be X^16 + X^15 +X^2 + 1, which is implemented by changing the exclusive or value from $1021 to $8005.

After all the bits of the data have been processed through the algorithm, 16 more zero bits are shifted through.  After the zeroes, the value in the CRC register is the CRC code we append to the data.

The "receiver" processes the data the same way, starting by zeroing the CRC register.  But instead of ending by shifting in 16 more zeroes, the receiver ends by shifting in the CRC code received.

I wanted to see if it really could find all those kinds of errors mentioned above.  I wrote a program which would compute the CRC value and append it to a data block.  Then I wrote another program which would "receive" the block and print out the resulting CRC value.  Then I modified it to one-by-one toggle each bit position in the entire block, simulating a single bit error in each bit position in the whole buffer.  My buffer is 256 bytes long, so that means 8*256 or 2048, different error positions.  Actually 2064, because of the two bytes of CRC.

This way I experimentally "discovered" that the value produced by the CRC computation on the received message is dependent on the error bit position.  It doesn't matter what the data was.  Therefore, if I had a lookup table of 2064 16-bit entries, I could search through it and find out which bit position was wrong.  There must be an easier way to figure out which bit position is wrong, but that is one of the things I still need to learn.

Okay.  CRC.BYTE (lines 2890-3060) is a subroutine to process the eight bits of one byte through the CRC algorithm.  CRC.BYTE needs to be called once for each byte of data in the buffer, plus either two zero bytes for a SEND routine or two CRC bytes for a RECV routine.

CRC.BUFFER (lines 2700-2850) is a little subroutine which calls CRC.BYTE once for each byte in the extended buffer.  I assume it is called with PNTR pointing at the first byte in the buffer, and LIMIT is equated to the byte just beyond the end.  The extended buffer includes either two zeroes on the end, or the two CRC bytes.

SETUP (lines 2610-2690) is a subroutine to initialize the CRC value register to zeroes, and to set PNTR to point at the beginning of the buffer.

The SEND and RECV routines at lines 1160-1380 simulate "sending" and "receiving" the buffer.  Note that both SEND and RECV finish by displaying the calculated CRC value.  SEND also stores the calculated CRC value into the end of the extended buffer.  RECV should end up with a CRC value of $0000, unless there have been bits changed between calls to SEND and RECV.

TEST.SINGLE.BIT.ERRORS (lines 1390-1800) is the testing subroutine which I described above.  It calls CRC.BUFFER 2064 times.  Each time a different bit is changed.  I print out the resulting CRC code each time, eight to a line, with the address of the byte containing the error bit leading the line.  Before running TEST.SINGLE.BIT.ERRORS, you should run SEND to be sure a valid CRC code is installed in the extended test buffer.

I wrote another test routine which tests all two-bit errors.  See TEST.DOUBLE.BIT.ERRORS, lines 1810-2410.  The only trouble is it would take about 72 hours to run, so I haven't let it go all the way.  I designed it to step through every bit position in two nested loops.  If both loops happen to be at the same bit position, the bit will be toggled twice resulting in no error.  I designed the program to print the address of the current byte whenever there was no error.

You might experiment with error bursts of various lengths, which should take no longer than TEST.SINGLE.BIT.ERRORS to run.

I would really be interested in finding out how to go backwards from a non-zero received CRC value to correct single-bit errors.  Is there some easy way, without either a huge table or a long computation?  If any of you know how, or have an article that tells how, pass it along.

1
