CS412 Networking and Telecommunications Project Part I

CRC-8 Checksum Calculation

Description
Write a function (or method if you prefer) in JAVA that takes a message stored as a bit pattern in a byte array and returns a byte of CRC checksum computed by using the CRC-8 polynomial.  The input is a byte array with an extra 8 0's already appended for CRC calculation.  The returned value is an 8-bit checksum, i.e., a byte. 

Algorithm
The following sketch of an algorithm might be useful.  It needs a little refinement.

1. Initialize a short sixteenBitWord with the first two bytes in message.
2. Initialize a short crcPattern with the CRC pattern shifted all the way left in this 16-bit short.
3. Initialize a short bitMask with a 1 in the leftmost bit and 0's elsewhere, i.e., "short bitMask = (short) 0x8000".
4. While bitMask does not cross into the lower byte, i.e., while (bitMask != 0x80)
       If a 1 appears in sixteenBitWord in the same position as the 1 bit in bitMask then
           subtract crcPattern from sixteenBitWord.
       Shift crcPattern rightward one bit. (Use logical shift right operator ">>>".)
       Shift bitMask rightward one bit. (Use logical shift right operator ">>>".) 
5. Shift the lower byte of sixteenBitWord to the upper byte, and copy in next byte of the message into the lower byte of sixteenBitWord.  The algorithm terminates when there is no more byte in the message to be copied.
6. Goto 2.

In many places you will need to cast the data to short or byte. 

Please trace the algorithm (trace is not to be turned in) to make sure you understand how it works if you want to implement it.  Write a driver to test your function.  Check up on your Java operators, there are many available for bit manipulation that you may not have used before.

This function is a really short one (20 lines of code at most) if your code is nicely crafted.

CRC-16 can be calculated by changing byte to short and short to long in the algorithm.  Similarly, CRC-32 can be calculated by changing byte to int and short to long.  Java also have a standard CRC32 class and you are encouraged to explore it. 

Two programs CRC16.java and CRC32.java can also be found at http://www.cs.princeton.edu/introcs/51data/CRC16.java and http://www.cs.princeton.edu/introcs/51data/CRC32.java, respectively.  BTW, I'd like to recommend Professors Robert Sedgewick and Kevin Wayne's Introduction to CS Web site http://www.cs.princeton.edu/introcs/home/ to every CS students as it is a very good learning and reference Web site.  You can also find many interesting problems to work on.