will be determined by counting the number of 1s in the byte
that you want to send. For even parity, the goal is to have an
even number of 1s between the byte and its parity bit.
For example, in Figure 4, the first byte has four 1s in
it, so the parity bit is a 0 because there is already an even
number of 1s in the byte. Odd parity is just the opposite. In
odd parity, the goal is to end up with an odd number of 1s
between the byte and its parity bit. Using parity will detect if
an odd number of bits have been inverted, but misses cases
where an even number of bits have been inverted.
Another, slightly more complex, way to detect errors is
to use something called a checksum. This method of error
detection fits better with larger chunks of data than a single
byte, unlike the previous examples. There are many possible
ways to compute a checksum.
Here is a very basic example of how you could compute
one. We will have packets of six bytes. For each six bytes of
data, we will add a seventh byte of data that is the checksum
byte. To calculate the value of the seventh byte, you could
add together the six data bytes and discard any extra bits
that overflow. The sender would send this data packet. On
the receiving end, the six bytes would be added together
and the result would be compared to the checksum. If the
checksum and the computed result were the same, then the
data would be considered to be valid.
Checksums can get more complex than this example.
The next example demonstrates how to compute an Adler- 32
checksum. The Adler- 32 checksum is 32 bits long and is
computed as two 16-bit values. The first value is simply the
sum of all bytes in the packet plus 1. The second value is a
little more complex. Refer to Figure 5 for a better idea of how
to calculate the second value.
The second value is the sum of all of the intermediate
first value results. For each step of calculating the second
value, you will take the total of the previous step, plus the
running sum from the first value. After the first and second
values are calculated, there is one additional calculation that
must be done on them — a modulus operation.
To calculate modulus, you divide the first number by the
second number using integer division. The result is the
remainder. For example, 7 mod 2 is 1, since 7 divided by 2
has a quotient of 3 with a remainder of 1. In the case of the
Adler- 32 calculation, we are calculating each value mod
65521. To send this packet, first send the actual data,
followed by the first and second values of the checksum.
Cyclic Redundancy Check (CRC)
CRC error checking is the strongest type of error checking
of those presented here. It works with longer sequences of
data, but also takes more processor power than the previous
examples. Like any algorithm that is often used, CRC has
other, more highly optimized forms that can be somewhat
cryptic to follow.
Like the other error detection methods discussed here,
CRC sticks a small piece of data onto the end of each chunk
of data that is sent. The CRC algorithm works in a similar way
to binary division, which was discussed in May’s column.
There are three differences between binary division and
the CRC calculation. The first is that, instead of using
subtracts at each step of the calculation, CRC uses the XOR
operator. The second difference between binary division and
the CRC calculation is that, at each step of the solution, the
decision whether or not to do the XOR operation is made
contingent upon if the most significant bit of the partial
remainder is a 1 or a 0. If the most significant bit is a 1, then
the XOR operation is performed. The third difference
between binary division and the CRC calculation is that,
before the CRC calculation, a certain number of zeros is
appended to the end of the dividend. The number of zeros
appended is the number of bits in the divisor minus one.
Take a look at Figure 6 for a better understanding. The
important part of the CRC calculation is the remainder. This
is the part that is tacked onto the end of the CRC packet. In
Figure 6, the digits in green are the original message. The
blue zeros are added on to assist in the calculation. The
orange digits are the remainder that replaces the blue zeros
in the final packet that is transmitted. In Figure 6, the
message being sent would be 1010 1011 1101.
There is one more part of CRC that hasn’t been discussed
yet. This is the divisor that is used. The specific divisor used
has a big influence on how likely it is that the CRC calculation
on the receiver side will detect a given error. Figure 7 lists some
commonly used ones. This article will not go into why each
of these divisors is better than others, but rest assured that
some really smart
math people out there
have some good
reasons and statistics
to back them up!
Once all of this is
done, the packet is
Figure 4. Even and odd parity.
1 + 83 = 84
0 + 84 = 84
84 + 69 = 153
84 + 153 = 237
153 + 82 = 235
237 + 235 = 472
235 + 86 = 321
472 + 321 = 793
321 + 79 = 400
793 + 400 = 1,193
Figure 5. Calculating an Adler- 32 checksum.
SERVO 07.2004 41