GoalExplain what a parity check can and cannot detect, and use a parity block to find a single wrong bit.
New words
corrupted data · data that has been changed by an error on its waylimitation · something a method cannot doparity block · a grid of bytes with a parity bit in every row and an extra parity byte, so that a single wrong bit can be locatedparity byte · the last row of a parity block, which holds a parity bit for each column
Explanation
A parity check has limits. If one bit changes, the number of 1s changes by one, so the byte fails and the error is noticed, but the receiver does not know which bit is wrong. If two bits change, the number of 1s can change by two, or stay the same, so the byte still passes and the error is missed. A parity block solves part of this. The sender sends several bytes together, followed by a parity byte that holds a parity bit for every column. The receiver checks every row and every column, and a single wrong bit makes exactly one row and one column fail. The wrong bit sits where they cross, so the receiver can turn it back. If two or more bits are wrong, the block cannot reliably show which they are.
Situation
Parity check result
Error found?
1 bit changes
fails
yes, but we do not know which bit
2 bits change (1 → 0 and 0 → 1, or two 0 → 1)
passes
no
1 wrong bit in a parity block
one row and one column fail
yes, and the bit is located
Worked examples
Byte sent
Byte received
What happened
1s in received
Parity check
Data correct?
01100101
01000101
one bit flipped
3
fail
no
01100101
01111101
two bits flipped
6
pass
no
01100101
00100111
one 1 became 0 and one 0 became 1
4
pass
no
What parity cannot see. The even-parity byte 01100101 is sent, and its data bits are worth 101. Three different things can happen to it. When only one bit changes, the byte fails. When two bits change, the byte still has an even number of 1s and passes, although its data is now wrong: the data bits of 01111101 are worth 125 and those of 00100111 are worth 39.
Parity bit
Bit 7
Bit 6
Bit 5
Bit 4
Bit 3
Bit 2
Bit 1
Row check
Byte 1
0
1
0
1
0
0
1
1
pass
Byte 2
0
0
1
1
1
1
1
0
fail
Byte 3
1
1
0
0
1
1
0
0
pass
Byte 4
0
0
0
1
1
1
0
1
pass
Parity byte
1
0
1
1
0
1
0
0
pass
Column check
pass
pass
pass
pass
fail
pass
pass
pass
A parity block, found out. Four data bytes and a parity byte were sent with even parity. After the journey, the receiver checks every row and column. Only Byte 2 fails its row check, and only the Bit 4 column fails its column check. The wrong bit is where Byte 2 and Bit 4 cross.
Parity bit
Bit 7
Bit 6
Bit 5
Bit 4
Bit 3
Bit 2
Bit 1
Row check
Byte 1
0
1
0
1
0
0
1
1
pass
Byte 2
0
0
1
1
0
1
1
0
pass
Byte 3
1
1
0
0
1
1
0
0
pass
Byte 4
0
0
0
1
1
1
0
1
pass
Parity byte
1
0
1
1
0
1
0
0
pass
Column check
pass
pass
pass
pass
pass
pass
pass
pass
Fixing the bit. The wrong bit is in Byte 2, Bit 4, and it reads 1. Turning it into 0 gives Byte 2 = 00110110, and now every row and column passes again. This is how a block can correct a single error and not only notice it.
Class activity
Find the flipped card (no computer). Make a block of five rows of eight cards (four rows of data with parity bits and one parity row, using even parity). Partner A closes their eyes while Partner B turns over exactly one card. Partner A counts the 1s in each row and column, names the row and the column that fail, and finds the card. Then try turning over two cards in different rows and columns. What do the row and column checks show now, and can you be sure which cards were turned?
Practice
1
The sender used even parity. For each pair, say whether the byte received passes the parity check, and whether the data really arrived correctly.
Byte sent
Byte received
Pass or fail?
Data correct?
11011011
11001011
?
?
00100111
01100011
?
?
01110010
01110010
?
?
Byte 1: received 11001011 has 5 ones, so it fails; the data is wrong. Byte 2: received 01100011 has 4 ones, so it passes; the data is wrong. Byte 3: received 01110010 has 4 ones, so it passes; the data is correct.
2
A learner says: ‘If a byte passes the parity check, it must be correct.’ Explain why this is not true, with an example.
A byte can pass even though it is wrong when two bits change. For example, with even parity 10110100 becomes 10011100 (one 1 became 0 and one 0 became 1). It still has four 1s, an even number, so it passes, but the data is different.
3
This parity block was sent with even parity and one bit is wrong. Work out the row check and column check results, and name the byte and the bit that is wrong.
Parity bit
Bit 7
Bit 6
Bit 5
Bit 4
Bit 3
Bit 2
Bit 1
Row check
Byte 1
0
0
1
0
1
1
0
1
?
Byte 2
0
1
1
1
0
0
0
1
?
Byte 3
1
0
0
1
0
1
0
0
?
Byte 4
0
1
1
0
0
0
1
1
?
Parity byte
1
0
1
0
1
0
0
1
?
Column check
?
?
?
?
?
?
?
?
Byte 3 fails its row check and the Bit 2 column fails its column check, so the wrong bit is in Byte 3, Bit 2. It is a 0 and should be a 1.
4
Give one limitation of a parity check, and say how a parity block improves on it.
A parity check cannot say which bit is wrong (and it misses two changed bits). A parity block checks the columns too, so one wrong bit makes a row and a column fail, and the bit where they cross can be found and corrected.