Loading learning content...
Simple parity can tell us that an error occurred, but not where. This limitation seems fundamental—after all, a single bit can only convey one bit of information. But what if we could apply parity in two dimensions?
Two-dimensional parity arranges data in a rectangular grid and computes parity for each row AND each column. When a single bit is corrupted, both its row parity and column parity will fail, and the intersection of the failing row and column pinpoints the exact error location.
With the error located, correction is trivial: simply flip the bit.
This elegant technique transforms parity from a mere detection mechanism into a genuine error-correcting code, using nothing more sophisticated than multiple applications of the same XOR operation we already understand.
By the end of this page, you will understand how to construct a two-dimensional parity scheme, how to detect and correct single-bit errors, the expanded detection capabilities for multi-bit errors, the overhead analysis and efficiency considerations, and the limitations that led to more sophisticated codes.
Two-dimensional parity organizes data bits into a rectangular array and adds redundancy in both dimensions.
Construction Steps:
Step 1: Arrange data in a grid Organize the data bits into m rows × n columns. The total data bits = m × n.
Step 2: Compute row parity For each row, compute a parity bit that makes the row have even (or odd) parity.
Step 3: Compute column parity For each column, compute a parity bit that makes the column have even (or odd) parity.
Step 4: Compute corner parity Compute a final parity bit for the row of parity bits (or equivalently, the column of parity bits—they should agree if everything is consistent).
Resulting Structure:
Data Columns (n) │ Row
┌─────────────────────────┐ │ Parity
R │ d₁₁ d₁₂ d₁₃ ... d₁ₙ │ │ r₁
o │ d₂₁ d₂₂ d₂₃ ... d₂ₙ │ │ r₂
w │ d₃₁ d₃₂ d₃₃ ... d₃ₙ │ │ r₃
s │ ⋮ ⋮ ⋮ ⋮ │ │ ⋮
(m) │ dₘ₁ dₘ₂ dₘ₃ ... dₘₙ │ │ rₘ
└─────────────────────────┘ │
───────────────────────────────────────
Col c₁ c₂ c₃ ... cₙ │ P
Parity │ (corner)
Total bits transmitted: m×n data + m row parity + n column parity + 1 corner = m×n + m + n + 1
The remarkable power of 2D parity is its ability to not just detect but correct single-bit errors.
The Correction Algorithm:
Step 1: Check all row parities Compute parity for each received row (including the row parity bit). Record which rows have parity errors.
Step 2: Check all column parities Compute parity for each received column (including the column parity bit). Record which columns have parity errors.
Step 3: Locate the error If exactly one row and one column fail parity, the error is at their intersection.
Step 4: Correct the error Flip the bit at the identified location.
Why This Works:
A single-bit error affects:
The failing row and column "point" to the corrupted bit like coordinates on a map.
Detailed Example: Correcting a Single-bit Error
Original transmitted block: Received block (error at position 2,3):
1 0 1 1 | 1 1 0 1 1 | 1
0 1 1 0 | 0 0 1 0 0 | 0 ← Row 2 parity fails!
1 1 0 0 | 0 1 1 0 0 | 0
0 1 0 1 | 0 0 1 0 1 | 0
--------- ---------
0 1 0 0 | 1 0 1 0 0 | 1
↑
Column 3 parity fails!
Verification at receiver:
| Check | Calculation | Result |
|---|---|---|
| Row 1 | 1⊕0⊕1⊕1⊕1 = 0 | ✓ Even |
| Row 2 | 0⊕1⊕0⊕0⊕0 = 1 | ✗ Odd (Error!) |
| Row 3 | 1⊕1⊕0⊕0⊕0 = 0 | ✓ Even |
| Row 4 | 0⊕1⊕0⊕1⊕0 = 0 | ✓ Even |
| Col 1 | 1⊕0⊕1⊕0⊕0 = 0 | ✓ Even |
| Col 2 | 0⊕1⊕1⊕1⊕1 = 0 | ✓ Even |
| Col 3 | 1⊕0⊕0⊕0⊕0 = 1 | ✗ Odd (Error!) |
| Col 4 | 1⊕0⊕0⊕1⊕0 = 0 | ✓ Even |
Conclusion: Error at Row 2, Column 3. Flip bit (2,3) from 0 to 1.
After correction:
1 0 1 1 | 1
0 1 1 0 | 0 ← Corrected!
1 1 0 0 | 0
0 1 0 1 | 0
---------
0 1 0 0 | 1
All parities now check. Data recovered!
The same technique handles errors in the parity bits themselves. If a row parity bit is corrupted, only that row fails the parity check, but no column fails. If the corner parity bit is corrupted, only the last row and last column fail. The algorithm handles all cases uniformly.
While 2D parity can correct single-bit errors, its detection capabilities extend further.
Two-bit Errors:
With simple 1D parity, two-bit errors are invisible. In 2D parity, the situation depends on the error pattern:
Case A: Errors in same row, different columns
Case B: Errors in same column, different rows
Case C: Errors in different rows and columns (rectangular pattern possible)
The Rectangular Blind Spot:
Corner pattern (undetectable): Other patterns (detectable):
X . . X Errors at X . . . Errors at
. . . . (1,1), (1,4), . X . . (1,1), (2,2),
. . . . (4,1), (4,4) X . . . (3,1)
X . . X . . . . 3 errors detected!
Each row has 2 errors → parity OK
Each col has 2 errors → parity OK
⚠ Completely undetected!
| Error Pattern | Rows Failing | Cols Failing | Outcome |
|---|---|---|---|
| No errors | 0 | 0 | Correct acceptance |
| 1 error (data) | 1 | 1 | Corrected ✓ |
| 1 error (row parity) | 1 | 0 | Corrected ✓ |
| 1 error (col parity) | 0 | 1 | Corrected ✓ |
| 1 error (corner) | 1 | 1 | Corrected ✓ |
| 2 errors (same row) | 0 | 2 | Detected, not correctable |
| 2 errors (same col) | 2 | 0 | Detected, not correctable |
| 2 errors (diagonal) | 2 | 2 | Detected, not correctable |
| 4 errors (rectangle) | 0 | 0 | ⚠ UNDETECTED |
| 3 errors | 1 or 3 | 1 or 3 | Detected, not correctable |
If exactly four bits are corrupted at the corners of a rectangle within the data grid, the errors cancel perfectly in both dimensions so all parities pass. This is the fundamental limitation of 2D parity that makes it unsuitable for high-error-rate environments.
Let's implement a complete 2D parity encoder/decoder with error correction.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190
from typing import List, Tuple, Optional class TwoDimensionalParity: """ Implementation of Two-Dimensional Parity for error detection and correction. This implementation uses even parity for both rows and columns. """ def __init__(self, rows: int, cols: int): """ Initialize with grid dimensions. Args: rows: Number of data rows cols: Number of data columns """ self.rows = rows self.cols = cols def encode(self, data: List[List[int]]) -> List[List[int]]: """ Encode data with 2D parity. Args: data: 2D list of bits (rows × cols) Returns: Extended grid with row/column parity and corner bit """ # Create encoded grid with space for parity encoded = [[0] * (self.cols + 1) for _ in range(self.rows + 1)] # Copy data for i in range(self.rows): for j in range(self.cols): encoded[i][j] = data[i][j] # Calculate row parity (rightmost column) for i in range(self.rows): row_xor = 0 for j in range(self.cols): row_xor ^= encoded[i][j] encoded[i][self.cols] = row_xor # Calculate column parity (bottom row) for j in range(self.cols): col_xor = 0 for i in range(self.rows): col_xor ^= encoded[i][j] encoded[self.rows][j] = col_xor # Calculate corner parity corner_xor = 0 for i in range(self.rows): corner_xor ^= encoded[i][self.cols] encoded[self.rows][self.cols] = corner_xor return encoded def check_and_correct(self, received: List[List[int]]) -> Tuple[List[List[int]], str]: """ Check received block and correct single-bit errors if possible. Args: received: Received grid including parity bits Returns: Tuple of (corrected_grid, status_message) """ # Check row parities row_errors = [] for i in range(self.rows + 1): row_xor = 0 for j in range(self.cols + 1): row_xor ^= received[i][j] if row_xor != 0: row_errors.append(i) # Check column parities col_errors = [] for j in range(self.cols + 1): col_xor = 0 for i in range(self.rows + 1): col_xor ^= received[i][j] if col_xor != 0: col_errors.append(j) # Analyze results if len(row_errors) == 0 and len(col_errors) == 0: return received, "No errors detected" elif len(row_errors) == 1 and len(col_errors) == 1: # Single-bit error - can correct! error_row = row_errors[0] error_col = col_errors[0] # Create corrected copy corrected = [row.copy() for row in received] corrected[error_row][error_col] ^= 1 # Flip the bit return corrected, f"Single-bit error corrected at ({error_row}, {error_col})" else: # Multiple errors detected but not correctable return received, f"Multiple errors detected: {len(row_errors)} row(s), {len(col_errors)} column(s) failing" def extract_data(self, grid: List[List[int]]) -> List[List[int]]: """Extract original data from encoded grid.""" return [[grid[i][j] for j in range(self.cols)] for i in range(self.rows)] def demo_2d_parity(): """Demonstrate 2D parity encoding and error correction.""" # Create encoder for 4x4 data grid parity = TwoDimensionalParity(4, 4) # Original data data = [ [1, 0, 1, 1], [0, 1, 1, 0], [1, 1, 0, 0], [0, 1, 0, 1] ] print("Two-Dimensional Parity Demonstration") print("=" * 50) # Encode encoded = parity.encode(data) print("\nOriginal data with 2D parity:") print_grid(encoded, parity.rows, parity.cols) # Scenario 1: No error print("\n--- Scenario 1: No error ---") corrected, status = parity.check_and_correct(encoded) print(f"Status: {status}") # Scenario 2: Single-bit error print("\n--- Scenario 2: Single-bit error at (1,2) ---") corrupted = [row.copy() for row in encoded] corrupted[1][2] ^= 1 # Flip bit print("Received (corrupted):") print_grid(corrupted, parity.rows, parity.cols) corrected, status = parity.check_and_correct(corrupted) print(f"Status: {status}") print("After correction:") print_grid(corrected, parity.rows, parity.cols) # Scenario 3: Two-bit error (same row) print("\n--- Scenario 3: Two-bit error in same row ---") corrupted = [row.copy() for row in encoded] corrupted[0][0] ^= 1 corrupted[0][2] ^= 1 print("Received (corrupted):") print_grid(corrupted, parity.rows, parity.cols) _, status = parity.check_and_correct(corrupted) print(f"Status: {status}") # Scenario 4: Rectangular pattern (undetectable!) print("\n--- Scenario 4: Rectangular pattern (corners) ---") corrupted = [row.copy() for row in encoded] corrupted[0][0] ^= 1 corrupted[0][3] ^= 1 corrupted[3][0] ^= 1 corrupted[3][3] ^= 1 print("Received (corrupted at corners):") print_grid(corrupted, parity.rows, parity.cols) _, status = parity.check_and_correct(corrupted) print(f"Status: {status}") print("⚠ WARNING: Data is corrupted but error was not detected!") def print_grid(grid: List[List[int]], data_rows: int, data_cols: int): """Pretty-print a 2D parity grid.""" for i, row in enumerate(grid): line = " ".join(str(b) for b in row[:data_cols]) line += " | " + str(row[data_cols]) print(" " + line) if i == data_rows - 1: print(" " + "-" * (data_cols * 2 + 4)) if __name__ == "__main__": demo_2d_parity()The error correction capability of 2D parity comes at the cost of additional overhead. Let's analyze.
Overhead Calculation:
For an m × n data grid:
Overhead ratio:
$$\text{Overhead} = \frac{m + n + 1}{m \times n + m + n + 1}$$
Efficiency (code rate):
$$R = \frac{m \times n}{m \times n + m + n + 1}$$
| Grid Size | Data Bits | Parity Bits | Total | Overhead % | Code Rate |
|---|---|---|---|---|---|
| 4 × 4 | 16 | 9 | 25 | 36.0% | 0.640 |
| 8 × 8 | 64 | 17 | 81 | 21.0% | 0.790 |
| 16 × 16 | 256 | 33 | 289 | 11.4% | 0.886 |
| 32 × 32 | 1024 | 65 | 1089 | 6.0% | 0.940 |
| 7 × 4 (ASCII) | 28 | 12 | 40 | 30.0% | 0.700 |
| 8 × 11 (typical) | 88 | 20 | 108 | 18.5% | 0.815 |
Comparison with Simple Parity:
Simple (1D) parity for n bits adds exactly 1 parity bit:
2D parity for 8×8 = 64 bits adds 17 parity bits:
The tradeoff: 2D parity uses ~14× more overhead than 1D parity for the same data size, but gains the ability to correct single-bit errors rather than merely detect them.
When is this worthwhile?
The overhead is justified when:
For fixed data size n = m × c, overhead is minimized when the grid is square (m = c = √n). However, practical constraints like byte boundaries often dictate rectangular grids.
Real communication channels often exhibit burst errors—where multiple consecutive bits are corrupted together. This poses a problem because 2D parity can only correct single-bit errors within its block.
The Solution: Interleaving
Interleaving spreads logically adjacent bits across multiple 2D parity blocks, so a burst error becomes distributed as single-bit errors in several blocks.
How Interleaving Works:
Suppose we have 4 blocks of 16 bits each to transmit:
Without interleaving: With interleaving:
Block 1: B1₁ B1₂ B1₃ ... B1₁₆ Position 1: B1₁ B2₁ B3₁ B4₁
Block 2: B2₁ B2₂ B2₃ ... B2₁₆ Position 2: B1₂ B2₂ B3₂ B4₂
Block 3: B3₁ B3₂ B3₃ ... B3₁₆ Position 3: B1₃ B2₃ B3₃ B4₃
Block 4: B4₁ B4₂ B4₃ ... B4₁₆ ... ... ... ... ...
↓ Transmit block by block ↓ Transmit column by column
A 4-bit burst damages 4 bits A 4-bit burst damages 1 bit
all in Block 1. UNCORRECTABLE! in each of 4 blocks. CORRECTABLE!
Interleaving transforms burst errors into distributed single-bit errors.
Interleaving requires buffering multiple codewords before transmission and de-interleaving at the receiver. For n-way interleaving, latency increases by factor of n. This is acceptable for storage and some communication but may be problematic for real-time applications.
Two-dimensional parity has been used in numerous real-world systems, though many have been superseded by more powerful codes.
Historical Applications:
1. Magnetic Tape Storage (1950s-1980s)
Early magnetic tape systems recorded data across multiple parallel tracks. 2D parity was natural:
2. Character Transmission
Early communication systems transmitted characters with:
3. RAID Storage (simplified view)
The concept extends to RAID arrays:
4. Memory with SEC-DED
The 2D parity concept influenced Single Error Correction, Double Error Detection (SEC-DED) codes used in ECC memory, though actual implementations use Hamming codes.
| Application | Original Method | Modern Replacement | Reason for Change |
|---|---|---|---|
| Magnetic Tape | 2D Parity + CRC | Reed-Solomon | Better burst error handling |
| Serial Comm. | Character + LRC | CRC-16/32 | Better random error detection |
| Memory | Byte parity | ECC (Hamming) | Error correction needed |
| Disk Arrays | XOR parity (RAID5) | RAID6, erasure codes | Multiple failure tolerance |
While 2D parity itself is rarely used in modern high-performance systems, its conceptual contribution is profound: it demonstrated that adding redundancy in multiple dimensions can enable error correction, not just detection. This insight underlies modern LDPC codes, turbo codes, and other advanced techniques.
Understanding 2D parity in terms of Hamming distance provides deep insight into its capabilities.
Hamming Distance Basics:
The Hamming distance between two codewords is the number of bit positions in which they differ.
Minimum distance of a code is the smallest Hamming distance between any two valid codewords.
Key relationships:
Simple Parity:
2D Parity:
Why minimum distance = 4?
To create a valid codeword from another valid codeword by flipping bits, you must maintain all row and column parities. The minimum number of flips that preserves all parities is 4 (a rectangular pattern). Hence, minimum distance = 4.
Proof of Minimum Distance = 4:
Claim: The minimum Hamming distance of 2D even parity code is 4.
Proof:
We show that:
Distance ≠ 1: A single bit flip changes one row parity and one column parity. The codeword becomes invalid. ✓
Distance ≠ 2: Two bit flips in the same row change that row's parity (making it invalid) unless the row parity bit is also flipped (but that's a third flip). Two flips in different rows also fail column parity unless they're in the same column (but then column parity fails unless column parity bit flipped). Any 2-flip pattern leaves at least one parity violated. ✓
Distance ≠ 3: Three flips: at least one row has exactly 1 flip (by pigeonhole). That row's parity fails unless a second flip is in the same row. But then some column has exactly 1 flip, which fails. Cannot avoid a parity violation with 3 flips. ✓
Distance = 4 is achievable: Flip four bits at corners of a rectangle. Each row has 2 flips (parity OK). Each column has 2 flips (parity OK). Valid codeword. ✓
Therefore, minimum distance = 4. ∎
We have thoroughly explored two-dimensional parity, a technique that extends simple parity into the realm of error correction. Let's consolidate the key insights:
What's Next:
In the next page, we'll examine the limitations of parity checking in depth—exploring the error patterns it misses, the conditions under which it fails, and why more sophisticated techniques like CRC and Hamming codes were developed to address these shortcomings.
You now understand two-dimensional parity, a technique that achieves single-bit error correction using only XOR operations. This foundation prepares you for understanding Hamming codes and other error-correcting codes that build upon these same principles.