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/