Error Detection Methods
Parity check
- The parity checking protocol determines whether bits in a transmission have been corrupted
- Every byte transmitted has one of its bits allocated as a parity bit
- The sender and receiver must agree before transmission whether they are using odd or even parity
- If odd parity is used then there must be an odd number of 1’s in the byte, including the parity bit
- If even parity is used then there must be an even number of 1’s in the byte, including the parity bit
- The value of the parity bit is determined by counting the number of 1’s in the byte, including the parity bit
- If the number of 1’s does not match the agreed parity then an error has occurred
- Parity checks only check that an error has occurred, they do not reveal where the error(s) occurred
Even parity
- Below is an arbitrary binary string
EVEN |
Byte |
||||||
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
- If an even parity bit is used then all bits in the byte, including the parity bit, must add up to an even number
- There are four 1’s in the byte. This means the parity bit must be 0 otherwise the whole byte, including the parity bit, would add up to five which is an odd number
Odd parity
- Below is an arbitrary binary string
ODD |
Byte |
||||||
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
- If an odd parity bit is used then all bits in the byte, including the parity bit, must add up to an odd number
- There are four 1’s in the byte. This means the parity bit must be a 1 otherwise the whole byte, including the parity bit, would add up to four which is an even number
- The table below shows a number of examples of the agreed parity between a sender and receiver and the parity bit used for each byte
Example # |
Agreed parity |
Parity bit |
Main bit string |
Total number of 1’s |
||||||
#1 |
ODD |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
5 |
#2 |
EVEN |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
2 |
#3 |
EVEN |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
6 |
#4 |
ODD |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
5 |
#5 |
ODD |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
5 |
#6 |
EVEN |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
4 |
- Example #1: The agreed parity is odd. All of the 1’s in the main bit string are added (5). As this number is odd already the parity bit is set to 0 so the whole byte stays odd
- Example #2: The agreed parity is even. All of the 1’s in the main bit string are added (1). As this number is odd the parity bit is set to 1 to make the total number of 1’s even (2)
- Example #6: The agreed parity is even. All of the 1’s in the main bit string are added (4). As this number is even already the parity bit is set to 0 so the whole byte stays even
How do errors occur?
- When using parity bits, an error occurs when the number of total bits does not match the agreed parity
- Bits can be flipped or changed due to interference on a wire or wirelessly due to weather or other signals
Example # |
Agreed parity |
Parity bit |
Main bit string |
Total number of 1’s |
Error |
||||||
#1 |
ODD |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
6 |
Error |
#2 |
EVEN |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
2 |
No error |
#3 |
EVEN |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
7 |
Error |
#4 |
ODD |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
5 |
No error |
#5 |
ODD |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
6 |
Error |
#6 |
EVEN |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
3 |
Error |
- Example #1: The agreed parity is odd but the total number of 1’s is even (6). An error has occurred somewhere
- Example #2: The agreed parity is even and the total number of 1’s is even (2). No error has occurred here
- Example #3: The agreed parity is even but the total number of 1’s is odd (7). An error has occurred somewhere
- Parity checks are quick and easy to implement but fail to detect bit swaps that cause the parity to remain the same
- Below is an arbitrary binary string. The agreed parity is odd and the total number of 1’s is five (odd)
Agreed parity |
Parity bit |
Total number of 1’s |
Error |
|||||||
ODD |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
5 |
No error |
Agreed parity |
Parity bit |
Total number of 1’s |
Error |
|||||||
ODD |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
3 |
No error |
Parity bytes and parity blocks
- Parity checks do not pinpoint errors in data, only that an error has occurred
- Parity blocks and parity bytes can be used to check an error has occurred and where the error is located
- A parity block consists of a block of data with the number of 1’s totalled horizontally and vertically
- A parity byte is also sent with the data which contains the parity bits from the vertical parity calculation
- Below is a parity block with a parity byte at the bottom and a parity bit column in the second column
ODD |
Parity bit |
Bit 2 |
Bit 3 |
Bit 4 |
Bit 5 |
Bit 6 |
Bit 7 |
Bit 8 |
Byte 1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
Byte 2 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
Byte 3 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
Byte 4 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
Byte 5 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
Byte 6 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
Byte 7 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
Byte 8 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
Parity byte |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
- The above table uses odd parity
- Each byte row calculates the horizontal parity as a parity bit as normal
- Each bit column calculates the vertical parity for each row. This is the parity byte. It is calculated before transmission and sent with the parity block
- Each parity bit tracks if a flip error occurred in a byte while the parity byte calculates if an error occurred in a bit column
- By cross referencing both horizontal and vertical parity values the error can be pinpointed
- In the above example the byte 3 / bit 5 cell is the error and should be a 0 instead
- The error could be fixed automatically or a retransmission request could be sent to the sender
Exam Tip
- Remember, parity bits only track if an error occurred, not where it is located. The parity bit itself might be the error. Parity bytes are calculated before transmission so act as a check on the parity bits themselves