Parity Data Link Error Detection / Correction Method

A parity bit is a bit that is appended to a bit stream to make the total number of "1" bits in a given set of bits always even or odd. Parity checks are the simplest error detecting system.

For example, if we send some specific sequence of ones and zeros, and then count the number of ones that we sent and send an extra 1 if that count is odd (making the total now even) or an extra 0 if that count is already even, a single bit error can be detected: The reciever can count up the number of 1 bits they recieved, perform the same calculation, and if the result is not even, they will know that an error occured.

Parity checks have serious limitations: The reciever has no way of knowing which bit was wrong, and if two bits were changed in value (e.g. a pair of 1's are both changed to 0's) then the errors would pass undetected.

There are two types of parity: even and odd. An even parity bit is set to 1 if the number of ones in a given set of bits is odd (making the total number of ones, including the parity bit, even). An odd parity bit is set to 1 if the number of ones in a given set of bits is even (making the total number of ones, including the parity bit, odd).

Even parity is actually a special case of a cyclic redundancy check (CRC), where the 1-bit CRC is generated by the polynomial x+1.

Parity calculated vertically, along the columns of many sets of bits, is called an LRC or Longitudinal Redundancy Check

The job of summing up the ones in a stream of bits is commonly performed by the XOR logic function. In this case, the XOR can be thought of as counting the ones, although what it really does is produce a 1, when it's inputs are different and a 0 when it's inputs are the same. It turns out the result is the same. For example, If we take the bits 1 0 1 1 and add them up, we get 3, which is odd, so even parity would be 1. If we take the first bit and XOR it with the second, we get 1, because they are different. Then we take that result, 1, and XOR it with the next bit of data, also a 1 to get a 0, because they are the same. Finally, the 0 and the last 1 are different and so we end up with a 1. You can try that with any example you like, the end result is the same: XOR is even parity.

Questions: