Two-Dimensional Parity Check: Error Detection (with Worked Example)

A parity check detects certain transmission errors by appending extra bits that describe whether the data has even/odd parity. In a two-dimensional parity check, we write the data into a grid and compute parity across both directions—rows and columns—so the receiver can detect inconsistencies and often localize where corruption occurred.

Mechanically:

• If parity is computed as even parity, then each row and each column is required to have an even number of 1s.
• After transmission, the receiver recomputes all row and column parities.
• If a row parity and a column parity disagree with the expected values simultaneously, the intersection points to a likely corrupted bit location (localization).

A key concept is the Hamming distance: adding row/column parity constraints creates a structured code that has nonzero minimum distance for many error patterns, allowing detection of various single-bit (and some multi-bit) errors. However, like any parity-based method, it cannot guarantee detection of every possible multi-bit corruption. (Specifically, parity checks detect all odd-weight errors within the checked structure, while some even-weight patterns can “cancel out”.)

The core structure can be visualized as:

Key learning terms (used throughout)

• parity
• row parity
• column parity
• detection

Worked Example: Data = 1100101100110000110100101101

We are given the bitstring:

$$1100101100110000110100101101$$

Let’s apply a 2D parity check. The length is $28$ bits, which is perfect for arranging into an $R\times C$ matrix as $4\\times 7$ (since $4\\cdot 7=28$).

We will use even parity for both row and column parity bits. (If your course uses odd parity, the procedure is identical—only the parity-bit values change.)

Step 1: Arrange bits into a $4\\times 7$ matrix

Write the bits row-wise (left to right within a row):

Row 1: 1100101
Row 2: 1001100
Row 3: 0011010
Row 4: 0101101

So the matrix $M$ is:

Row parity bits (even parity)

Count 1s in each row:

• Row 1: 1100101 has $4$ ones → even → row parity $r_1=0$
• Row 2: 1001100 has $3$ ones → odd → row parity $r_2=1$
• Row 3: 0011010 has $3$ ones → odd → row parity $r_3=1$
• Row 4: 0101101 has $4$ ones → even → row parity $r_4=0$

So row parity vector is:

$$[r_1,r_2,r_3,r_4] = [0,1,1,0]$$

Column parity bits (even parity)

Now for each column (from the matrix):

• Col 1: bits = $[1,1,0,0]$ → $2$ ones → even → $c_1=0$
• Col 2: bits = $[1,0,0,1]$ → $2$ ones → even → $c_2=0$
• Col 3: bits = $[0,0,1,0]$ → $1$ one → odd → $c_3=1$
• Col 4: bits = $[0,1,1,1]$ → $3$ ones → odd → $c_4=1$
• Col 5: bits = $[1,1,0,1]$ → $3$ ones → odd → $c_5=1$
• Col 6: bits = $[0,0,1,0]$ → $1$ one → odd → $c_6=1$
• Col 7: bits = $[1,0,0,1]$ → $2$ ones → even → $c_7=0$

So column parity vector is:

$$[c_1,c_2,c_3,c_4,c_5,c_6,c_7] = [0,0,1,1,1,1,0]$$

How detection works (the key logic)

Consider what happens if exactly one bit flips during transmission (a $1\\leftrightarrow 0$ error):

• That flip changes the 1-count of its row by $\\pm 1$ (toggling parity).
• It also changes the 1-count of its column by $\\pm 1$ (toggling parity).
• Therefore, the parity check will fail for both the corresponding row and corresponding column.

So a single-bit error produces:

• at least two mismatches (one row, one column),
• and the intersection of the mismatching row and column identifies the bit’s location.

Concrete detection scenario (illustrative)

Suppose during transmission, the bit at Row 2, Column 4 flips.

From the matrix, Row 2 is 1 0 0 1 1 0 0, so Column 4 currently is 1. A flip makes it 0.

Effect on parities

• Row 2: number of 1s decreases by 1 → row parity toggles
  So receiver’s recomputed parity for Row 2 will not match the transmitted $r_2=1$.
• Column 4: Column 4 currently has bits $[0,1,1,1]$ (3 ones). After flip at Row 2, it becomes $[0,0,1,1]$ (2 ones). Parity toggles again.
  So receiver’s recomputed parity for Column 4 will not match $c_4=1$.

Thus, the receiver detects an error by finding:

• row mismatch at Row 2
• column mismatch at Column 4

Their intersection uniquely points to cell $(2,4)$ in this single-bit-error case.

Summary of what to transmit

For a $4\\times 7$ matrix:

• transmit the $28$ data bits,
• plus $4$ row parity bits and $7$ column parity bits:

$$\\text{Total transmitted bits} = 28 + 4 + 7 = 39$$

Parity bits to append:

• Row parity: $[0,1,1,0]$
• Column parity: $[0,0,1,1,1,1,0]$