Computing parity involves counting the number of ones in the unit of data, and adding a zero or one to make the count odd or even (it depends on weather we're using "odd parity" or "even parity" ).
For example, for the 4 bit item 1001, there are two one bits. For even parity, a zero is added to the stream, maintaining an even number of one bits. For odd parity, a one is added to make the number of ones odd. Following are the results:
The exclusive OR (XOR) operator (^)is fundamental to the computation of parity.
Computing parity that is even involves XORing the bits of the data stream together, while computing odd parity XORs the bits and negates the result equivalent to XNOR operator (~).This is demonstrated in the following example using the previous table:
1^0^0^1 = 0 (Computing Even Parity)
~(1^0^0^1) = 1 (Computing Odd Parity)
This mechanism enables the detection of single bit errors, because if one bit gets flipped due to line noise, there will be an incorrect number of ones in the received data. Consider the following assuming even parity:
A sends 10010 B receives 11010
B computes the parity:
1^1^0^1 = 1
The parity bits do not match (even parity the XOR result should be 0), indicating an error. Rather than computing parity on the data bits and comparing them to the parity bit, the receiver will actually XOR the data bits and the parity bit. If the result is zero, the check passed, a non zero result indicates an error. If P is the parity generation function, then :
P(d1,d2,d3,....dn) = P
and:
P(d1,d2,d3,....dn,P) = 0
if no error has occurred. Any incorrect bit results in the same outcome, but there is no information regarding which bit flipped, and therefore no possibility of correcting it. Also, if two bits flip, no errors are indicated:
A sends 10010 B receives 11000
B computes the parity:
1^1^0^0^0 = 0
and shows that the data is valid when it's not, therefore when using this method you must assume that the probability for two errors is very low.
There are some other methods that can detect two errors, or detect and correct one error such as parallel parity, Hamming codes, etc.