Last time I talked about different methods to make checksums a bit (no pun intended) more robust than just simply adding bytes in a message together. Of course, there are other ways to safeguard against accidental corruption of data, ranging from the very simple to the monstrously complex.
On the simple side is parity. Parity is simple. You add a bit to the word to ensure that it has either an odd or even number of 1 bits. One short cut to counting the number of bits is to realize that you really only care about bit 0. An even number will always have bit 0=0 and an odd number will always have bit 1=1. Consider this C code:
unsigned char byte=0x70; /* byte to compute parity for */ unsigned char working; /* temporary working copy */ unsigned paritybit=0; /* assume even number of 1s */ /* this loop starts with byte and then shifts until all the 1's are gone */ for (working=byte;working!=0; working>>=1) paritybit^=(working&1);
This won’t take more than 8 loops (and less if possible). The loop starts working out with the same value as byte. The loop body XORs the existing parity bit with bit 0 of the working copy. This flips paritybit from 0 to 1 (or, later, from 1 to 0) every time working has a 1 in the bit 0 position. Each loop iteration shifts working over one place to the right until there are no more 1 bits.
It is probably not slow enough to require optimization, but you could shift working to the left instead of the right and then look at the top bit instead of the bottom bit. But the effort to figure out the best shift direction probably wipes out any possible gain, especially on a byte. If you really need faster, consider a look up table (click here for an example).
Since the code sets paritybit to be the same as bit 0 of the sum of the 1 bits in byte, the resulting bit is an even parity bit. That is, if byte has an odd number of bits, the parity bit will be a 1, making the total number of bits even. If the byte already has an even number of bits, the parity bit will be 0. If you wanted odd parity, you can simply start paritybit as 1 (this makes sense if you think of the initialization of paritybit as the parity of a word with all zeros, which is an even number of 1s, sort of).
Parity is used in some memory systems, busses, and many communication systems. Some RAID disk drives also use parity to help reconstruct data. The problem is it isn’t very useful, even though it is easy to compute. The only thing an error can do is flip a 1 to a 0 or vice versa. Any error that changes a 1 to a 1 or a 0 to a 0 isn’t really an error, right? If one bit is in error, the parity check will catch that error (even if the wrong bit is the parity bit itself). But what happens if two bits are in error? Ugh. If two 1 bits change to 0 bits or two 0 bits change to 1 bits, the parity doesn’t change. That is, three 1 bits and a single 1 bit both have an odd count of 1 bits. The same goes for taking away a 1 and adding a 1 somewhere else.
By the same logic, though, 3 bits in error will show up as a bad parity check. If you think about it a bit, parity always catches odd numbers of bit errors, and misses even numbers of bit errors.
One interesting use of parity bits is cross parity (or longitudinal redundancy check, if you prefer expensive words). Suppose you want to detect errors in 8 bytes of data. If you imagine each byte stacked one on top the other, you could compute the parity of the bits in each column of data. Then you could compute all the rows as usual. This would result in two parity bytes, one horizontal and one vertical (see the figure below).
What’s interesting about this is that if a single error occurs, you will get a bad parity bit in both parity bytes. By noting where the bad bits intersect, you can deduce which bit is in error. And since the bit must be in the opposite state, you can repair the error. For example, suppose you later retrieve the block of data and find that bit 6 of the vertical parity shows an error and so does bit 1 of the horizontal parity. The latter tells you that the error is in byte 1. The former indicates the error is in bit 6. Since the bit is in error, it must be set to a 1, and thus you could correct it by flipping it to a 0.
The problem still remains: Multiple errors may go undetected, depending on how they occur in the data pattern. To fight this, more sophisticated codes are typically used, including Hamming codes (like Richard Hamming, not like ham radio) and the Cyclic Redundancy Check (CRC). Actually, parity is a special case of CRC, just not a very good case. I’ll save those until next time. There have also been attempts to extend cross parity to be more robust. I remembered reading an article years ago about orchard parity, but I have never seen it actually used. Google search being amazing turned up this patent from 1984: http://www.google.com/patents?id=Bu00AAAAEBAJ,which proves, if nothing else, that my personal memory hasn’t started needing error detection quite yet.