Parity CheckDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/