AdvertisementYour brand could be hereYour brand hereOn every Darslab page · students, parents and teachersinfo@darslab.comAsk for pricesPricesinfo@darslab.com
☰ Year plan · Computing

Check the bits, guard the data

Week 23 · 3.3 Parity checks and network security · 3 lessons
2

When parity is not enough

Computing 9: Topic 3.3, pp. 284–298
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.

SituationParity check resultError found?
1 bit changesfailsyes, but we do not know which bit
2 bits change (1 → 0 and 0 → 1, or two 0 → 1)passesno
1 wrong bit in a parity blockone row and one column failyes, and the bit is located
Worked examples
Byte sentByte receivedWhat happened1s in receivedParity checkData correct?
0110010101000101one bit flipped3failno
0110010101111101two bits flipped6passno
0110010100100111one 1 became 0 and one 0 became 14passno
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 bitBit 7Bit 6Bit 5Bit 4Bit 3Bit 2Bit 1Row check
Byte 101010011pass
Byte 200111110fail
Byte 311001100pass
Byte 400011101pass
Parity byte10110100pass
Column checkpasspasspasspassfailpasspasspass
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 bitBit 7Bit 6Bit 5Bit 4Bit 3Bit 2Bit 1Row check
Byte 101010011pass
Byte 200110110pass
Byte 311001100pass
Byte 400011101pass
Parity byte10110100pass
Column checkpasspasspasspasspasspasspasspass
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 sentByte receivedPass or fail?Data correct?
1101101111001011??
0010011101100011??
0111001001110010??
2
A learner says: ‘If a byte passes the parity check, it must be correct.’ Explain why this is not true, with an example.
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 bitBit 7Bit 6Bit 5Bit 4Bit 3Bit 2Bit 1Row check
Byte 100101101?
Byte 201110001?
Byte 310010100?
Byte 401100011?
Parity byte10101001?
Column check????????
4
Give one limitation of a parity check, and say how a parity block improves on it.