Parity Check

Date: 11/12/2000 at 11:55:33
From: hf2186
Subject: The Parity Check

What is a parity check, and how does it work?

Date: 11/14/2000 at 11:28:32
From: Doctor TWE
Subject: Re: The Parity Check

Hi - thanks for writing to Dr. Math.

Parity is a means of detecting errors in binary transmission streams. 
It is based on sending redundant data to verify the integrity of the 
received data. It is not foolproof.

To use a parity check, at the transmission end the data are divided 
into groups of bits (typically 7 or 8 bits per group). For each group 
a parity bit is generated and sent along with the data group. At the 
receiving end, another parity bit is generated based on the received 
data and compared with the parity bit sent by the transmitter. If the 
parity bits match, the data are considered (probably) valid, but if 
the parity bits do not match, an error has occurred during 
transmission.

There are two "types" of parity checks that can be used; even parity 
and odd parity. The transmitter and receiver must use the same method 
for the check to work properly.

With even parity, the total number of 1's in the data plus parity bit 
must be an even number. Thus, if there are already an even number of 
1's in the data itself the parity bit generated is 0, but if there are 
an odd number of 1's in the data itself, the parity bit generated is 1 
to make the total even. For example (using 7 data bits, P is the 
parity bit generated):

                        EVEN PARITY
     Data      #1's in data   P   Total # 1's (data and P)
     -------   ------------   -   --------------------
     0110110     4 (Even)     0    4 (Even)
     0011111     5 (Odd)      1    6 (Even)
     0000000     0 (Even)     0    0 (Even)
     1010100     3 (Odd)      1    4 (Even)
     1111111     7 (Odd)      1    8 (Even)

With odd parity, the total number of 1's in the data plus parity bit 
must be an odd number. Thus, if there are already an odd number of 1's 
in the data itself the parity bit generated is 0, but if there are an 
even number of 1's in the data itself, the parity bit generated is 1 
to make the total odd. For example (using 7 data bits, P is the parity 
bit generated):

                         ODD PARITY
     Data      #1's in data   P   Total # 1's (data and P)
     -------   ------------   -   --------------------
     0110110     4 (Even)     1    5 (Odd)
     0011111     5 (Odd)      0    5 (Odd)
     0000000     0 (Even)     1    1 (Odd)
     1010100     3 (Odd)      0    3 (Odd)
     1111111     7 (Odd)      0    7 (Odd)

If a single bit is switched during transmission, a parity check will 
catch it, and we know the data are bad. We can't tell, however, which 
bit was switched. For example, suppose 0110110 is sent using odd 
parity, and the second bit from the left is switched:

    Data sent:     0110110
    #1's in data:  4 (Even)
    Parity bit:    1
    Tl. # 1's:     5 (Odd)

    Data received: 0010110   (Note the changed bit)
    #1's in data:  3 (Odd)
    Parity bit:    0
    Tl. # 1's:     3 (Odd)

Comparing the two parity bits, we can see that there was an error. 
However, we don't know which bit was switched. Any of the following 
data could have produced the received result with only a single bit 
change:

     1010110
     0110110
     0000110
     0011110
     0010010
     0010100
     0010111

We have no way of knowing which of the above were the original data.

As mentioned at the beginning, parity is not foolproof. For example, 
suppose 0110110 is sent using odd parity, and the second and fourth 
bits from the left are both switched:

    Data sent:     0110110
    #1's in data:  4 (Even)
    Parity bit:    1
    Tl. # 1's:     5 (Odd)

    Data received: 0011110   (Note the changed bits)
    #1's in data:  4 (Even)
    Parity bit:    1
    Tl. # 1's:     5 (Odd)

Here, the parity bit generated by the receiver matches the parity bit 
sent by the transmitter, so the data are assumed to be valid even 
though an error has occurred. In fact, any time two bits (or any even 
number of bits) are switched, the parity check is fooled.

There are other error detection (and even correction) schemes, many of 
which are more reliable than a simple parity check. Some examples are 
vertical parity, HVP (horizontal and vertical parity), checksums, and 
CRC (circular redundancy check.) Many of these, however, are built on 
the principles of parity.

I hope this helps. If you have any more questions, write back.

- Doctor TWE, The Math Forum
  http://mathforum.org/dr.math/