Page 259 - Anatomy of a Robot

09_200256_CH09/Bergren 4/17/03 11:24 AM Page 244
244 CHAPTER NINE
www.relisoft.com/Science/CrcNaive.html
www.relisoft.com/Science/CrcOptim.html
www.relisoft.com/Science/source/Crc.zip
PARITY BITS
Let’s look at a simple checksum structure example. Parity bits, as part of a checksum
structure, can simply indicate how many ones are in a byte. Basically, take a byte and
count up the number of ones in the 8 bits. If we are using an even parity scheme, then
the number of ones in the bits (including the parity bit) must be even. For example, if an
even number of ones is in the data byte, then append a ninth parity bit containing a zero
to the byte to keep an even parity. If the number of ones in the byte is odd, then append
a one as the ninth parity bit to attain even parity. If we do this for every byte in the data
block, then single bit errors in any byte will “finger” that byte as bad. We will be able
to detect single bit errors in the data block at the expense of increasing the data by 1/8.
If we also compute the parity for each bit, over the entire data block we will get more
capability. We can, for example, compute the number of ones in the 0 bit position for
the entire data block and append a column parity byte at the end of the data block con-
taining a single 9-bit number. The column parity byte will contain the parity computed
for the 0th, first, second, ...eighth, and ninth columns of bits in the data block. Then,
if a single bit is corrupted in the data block, that byte’s parity bit will signal which byte
is erroneous, and the column parity byte will tell us which bit is wrong in that byte. This
will allow us to correct single bit errors in a data block by duplicating and expanding
the data block by about 1/8. It’s not a very strong code; better ones can be created.
It is easy to make up our own code, but we must be sure it matches the requirements
of the robot’s operating environment. The strength of the code should match the error
rates, the error distribution, and the tolerance the robot has for errors.

REED-SOLOMON CHECKSUMS

One of the most often used checksum calculations is the Reed-Solomon (RS) code. This
type of code is capable of correcting multiple errors in a block of data. The reason this
is useful will be outlined shortly. RS coding also expands the data block by appending
parity bytes.
One popular RS code is RS(255,233), which expands a 233-byte data block to 256
bytes by appending 32 bytes of parity checksums, an expansion of the data block by a
factor of about 14 percent. The RS(255,233) polynomial enables up to 16 different bytes
to be corrected at the same time.