0984

Error Detection

Data Transmission · 4 question types

Practise

A parity block combines a horizontal parity bit (one per byte) with a vertical parity byte (one bit per column), so that the row AND column of any single-bit error can be identified.

Two-dimensional parity block: four data bytes stacked as rows of a bit grid, with a redundant parity byte (LRC) calculated down each column shown beneath, and the transmitted frame of the four data bytes followed by the appended column-parity byte 01001111 sent to the receiver.
Source: LRC by GeeksforGeeks

The structure:

  • A block of (say) nine 8-bit bytes, arranged as 9 rows × 8 columns.
  • Each row has its own parity bit, calculated across the row's data bits.
  • A 10th row, called the parity byte, holds one parity bit per column, calculated down the column.

When the block is received, the receiver re-calculates every row parity and every column parity. The intersection of the mismatched row and the mismatched column pinpoints the exact bit that flipped, which can then be corrected automatically.

Worked example

Completing the parity byte of a parity block

Four bytes, each a parity bit followed by the data bits b7 to b1, are transmitted as a parity block using even parity. The parity bit of each byte has already been set. Complete the parity byte.

parity bitb7b6b5b4b3b2b1
byte A01100101
byte B11010100
byte C00100111
byte D10111000
parity byte

Solution:

  • Treat each column like a row: count its 1s and, for even parity, write 1 if the count is odd and 0 if it is already even.
  • Counting the 1s down the columns, parity bit first: 2, 2, 3, 2, 1, 3, 1, 2.
  • The b6, b4, b3 and b2 columns are odd, so they get a 1 and the rest get a 0.
  • Parity byte: parity bit 0, then 0 1 0 1 1 1 0 for b7 down to b1.
  • Check: the parity byte holds four 1s, an even number, as it must when every row and column is even.

A single flipped bit then fails its row and its column, and the bit where they cross is the error. In the paper that set this, two right bits earned one mark, five earned two and all eight earned three, so fill every cell.

What parity blocks detect

  • Single-bit error: detected AND located.
  • Two errors in the same row: row parity passes, but two columns mismatch (still detected, harder to locate).
  • Even number of errors in the same row AND same columns: undetectable.

Parity blocks are far stronger than a single parity bit, at the cost of one extra byte per block.