Two-dimensional Parity — Parity Check | OneNoughtOne

0/240

Computer NetworksError Detection & Correction

Parity Check

LevelBeginner

Duration60 mins

TopicError Detection & Correction

3 / 5

Two-dimensional Parity

From Detection to Correction: The Power of a Second Dimension

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.

What You Will Learn

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.

Concept and Construction

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 \times n columns. The total data bits = m \times 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\timesn data + m row parity + n column parity + 1 corner = m\timesn + m + n + 1

Constructing a 4×4 Two-Dimensional Parity Block

Let's build a complete 2D parity structure with 16 data bits.

1
Step 1
$Data bits (16): 1011 0110 1100 0101$
2
Step 2
$Arrange in 4\times4 grid:$

Step 3

1 0 1 1 | ? 0 1 1 0 | ? 1 1 0 0 | ? 0 1 0 1 | ? --------- ? ? ? ? | ?

4
Step 4
$Calculate row parity (even): Row 1: 1+0+1+1=3 (odd) \to parity=1 Row 2: 0+1+1+0=2 (even) \to parity=0 Row 3: 1+1+0+0=2 (even) \to parity=0 Row 4: 0+1+0+1=2 (even) \to parity=0$
5
Step 5
$Calculate column parity (even): Col 1: 1+0+1+0=2 \to parity=0 Col 2: 0+1+1+1=3 \to parity=1 Col 3: 1+1+0+0=2 \to parity=0 Col 4: 1+0+0+1=2 \to parity=0$
6
Step 6
$Calculate corner parity: 0+1+0+0=1 \to parity=1$

Step 7

Complete block: 1 0 1 1 | 1 0 1 1 0 | 0 1 1 0 0 | 0 0 1 0 1 | 0 --------- 0 1 0 0 | 1

Single-bit Error Correction

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: Exactly one row \to that row's parity fails Exactly one column \to that column's parity fails 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 \leftarrow 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 \leftarrow Corrected! 1 1 0 0 | 0 0 1 0 1 | 0 --------- 0 1 0 0 | 1 All parities now check. Data recovered!

Errors in Parity Bits

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.

Multi-bit Error Detection

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 Row parity may pass (if the two bits are 0\to1 and 1\to0) Two column parities fail Pattern: 0 rows fail, 2 columns fail \to Detected as 2 errors (but not correctable) Case B: Errors in same column, different rows Two row parities fail Column parity may pass Pattern: 2 rows fail, 0 columns fail \to Detected Case C: Errors in different rows and columns (rectangular pattern possible) If errors form rectangle corners (4 bits), ALL parities might pass! Otherwise, detected 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 \to parity OK Each col has 2 errors \to parity OK ⚠ Completely undetected!

2D Parity Detection and Correction Capabilities
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

The Rectangular Pattern Vulnerability

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.

Implementation in Code

Let's implement a complete 2D parity encoder/decoder with error correction.

two_d_parity.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
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("
Original data with 2D parity:")
    print_grid(encoded, parity.rows, parity.cols)
    
    # Scenario 1: No error
    print("
--- Scenario 1: No error ---")
    corrected, status = parity.check_and_correct(encoded)
    print(f"Status: {status}")
    
    # Scenario 2: Single-bit error
    print("
--- 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("
--- 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("
--- 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()

Overhead Analysis

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: Data bits: m × n Row parity bits: m Column parity bits: n Corner parity bit: 1 Total parity bits: m + n + 1 Total transmitted: m × n + m + n + 1 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}$$

2D Parity Overhead for Various Grid Sizes
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: Overhead = 1/(n+1) For 64 bits: overhead = 1.5% 2D parity for 8\times8 = 64 bits adds 17 parity bits: Overhead = 17/81 = 21% The tradeoff: 2D parity uses ~14\times 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: Retransmission is expensive or impossible (one-way links, broadcast) Error rates make detection insufficient Latency requirements preclude request/retransmit cycles Storage systems where re-reading is costly

Optimal Grid Shape

For fixed data size n = m \times c, overhead is minimized when the grid is square (m = c = \sqrtn). However, practical constraints like byte boundaries often dictate rectangular grids.

Interleaving: Protecting Against Burst Errors

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 Example with 4-bit Burst

Demonstrating how interleaving protects against a burst error.

1
Step 1
$Setup: 4 codewords, each 4\times4 grid = 25 bits with parity$
2
Step 2
$Interleaving depth: 4 (transmit 1 bit from each codeword in turn)$
3
Step 3
$Transmission order: CW1[0], CW2[0], CW3[0], CW4[0], CW1[1], CW2[1], ...$
4
Step 4
$Burst error: 4 consecutive transmitted bits corrupted$
5
Step 5
$Effect without interleaving: 4 bits in same codeword \to uncorrectable$
6
Step 6
$Effect with interleaving: 1 bit in each of 4 codewords \to 4 separate single-bit errors$
7
Step 7
$Result: Each codeword has exactly 1 error \to all 4 errors corrected!$

Interleaving Adds Latency

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.

Historical and Practical 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: Each track = one column Parity track = column parity Record blocks with row parity CRC added for additional protection 2. Character Transmission Early communication systems transmitted characters with: 7 bits of ASCII data 1 horizontal parity bit per character Occasional vertical parity character (LRC - Longitudinal Redundancy Check) 3. RAID Storage (simplified view) The concept extends to RAID arrays: Data striped across multiple disks (columns) Parity disk stores column parity Single disk failure = single "column" error = recoverable 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.

Evolution from 2D Parity to Modern 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

Legacy of 2D Parity

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.

Computer NetworksError Detection & Correction

Parity Check

LevelBeginner

Duration60 mins

TopicError Detection & Correction

3 / 5

Two-dimensional Parity

From Detection to Correction: The Power of a Second Dimension

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.

What You Will Learn

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.

Concept and Construction

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 \times n columns. The total data bits = m \times 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\timesn data + m row parity + n column parity + 1 corner = m\timesn + m + n + 1

Constructing a 4×4 Two-Dimensional Parity Block

Let's build a complete 2D parity structure with 16 data bits.

1
Step 1
$Data bits (16): 1011 0110 1100 0101$
2
Step 2
$Arrange in 4\times4 grid:$

Step 3

1 0 1 1 | ? 0 1 1 0 | ? 1 1 0 0 | ? 0 1 0 1 | ? --------- ? ? ? ? | ?

4
Step 4
$Calculate row parity (even): Row 1: 1+0+1+1=3 (odd) \to parity=1 Row 2: 0+1+1+0=2 (even) \to parity=0 Row 3: 1+1+0+0=2 (even) \to parity=0 Row 4: 0+1+0+1=2 (even) \to parity=0$
5
Step 5
$Calculate column parity (even): Col 1: 1+0+1+0=2 \to parity=0 Col 2: 0+1+1+1=3 \to parity=1 Col 3: 1+1+0+0=2 \to parity=0 Col 4: 1+0+0+1=2 \to parity=0$
6
Step 6
$Calculate corner parity: 0+1+0+0=1 \to parity=1$

Step 7

Complete block: 1 0 1 1 | 1 0 1 1 0 | 0 1 1 0 0 | 0 0 1 0 1 | 0 --------- 0 1 0 0 | 1

Single-bit Error Correction

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: Exactly one row \to that row's parity fails Exactly one column \to that column's parity fails 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 \leftarrow 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 \leftarrow Corrected! 1 1 0 0 | 0 0 1 0 1 | 0 --------- 0 1 0 0 | 1 All parities now check. Data recovered!

Errors in Parity Bits

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.

Multi-bit Error Detection

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 Row parity may pass (if the two bits are 0\to1 and 1\to0) Two column parities fail Pattern: 0 rows fail, 2 columns fail \to Detected as 2 errors (but not correctable) Case B: Errors in same column, different rows Two row parities fail Column parity may pass Pattern: 2 rows fail, 0 columns fail \to Detected Case C: Errors in different rows and columns (rectangular pattern possible) If errors form rectangle corners (4 bits), ALL parities might pass! Otherwise, detected 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 \to parity OK Each col has 2 errors \to parity OK ⚠ Completely undetected!

2D Parity Detection and Correction Capabilities
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

The Rectangular Pattern Vulnerability

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.

Implementation in Code

Let's implement a complete 2D parity encoder/decoder with error correction.

two_d_parity.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
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("
Original data with 2D parity:")
    print_grid(encoded, parity.rows, parity.cols)
    
    # Scenario 1: No error
    print("
--- Scenario 1: No error ---")
    corrected, status = parity.check_and_correct(encoded)
    print(f"Status: {status}")
    
    # Scenario 2: Single-bit error
    print("
--- 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("
--- 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("
--- 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()

Overhead Analysis

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: Data bits: m × n Row parity bits: m Column parity bits: n Corner parity bit: 1 Total parity bits: m + n + 1 Total transmitted: m × n + m + n + 1 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}$$

2D Parity Overhead for Various Grid Sizes
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: Overhead = 1/(n+1) For 64 bits: overhead = 1.5% 2D parity for 8\times8 = 64 bits adds 17 parity bits: Overhead = 17/81 = 21% The tradeoff: 2D parity uses ~14\times 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: Retransmission is expensive or impossible (one-way links, broadcast) Error rates make detection insufficient Latency requirements preclude request/retransmit cycles Storage systems where re-reading is costly

Optimal Grid Shape

For fixed data size n = m \times c, overhead is minimized when the grid is square (m = c = \sqrtn). However, practical constraints like byte boundaries often dictate rectangular grids.

Interleaving: Protecting Against Burst Errors

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 Example with 4-bit Burst

Demonstrating how interleaving protects against a burst error.

1
Step 1
$Setup: 4 codewords, each 4\times4 grid = 25 bits with parity$
2
Step 2
$Interleaving depth: 4 (transmit 1 bit from each codeword in turn)$
3
Step 3
$Transmission order: CW1[0], CW2[0], CW3[0], CW4[0], CW1[1], CW2[1], ...$
4
Step 4
$Burst error: 4 consecutive transmitted bits corrupted$
5
Step 5
$Effect without interleaving: 4 bits in same codeword \to uncorrectable$
6
Step 6
$Effect with interleaving: 1 bit in each of 4 codewords \to 4 separate single-bit errors$
7
Step 7
$Result: Each codeword has exactly 1 error \to all 4 errors corrected!$

Interleaving Adds Latency

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.

Historical and Practical 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: Each track = one column Parity track = column parity Record blocks with row parity CRC added for additional protection 2. Character Transmission Early communication systems transmitted characters with: 7 bits of ASCII data 1 horizontal parity bit per character Occasional vertical parity character (LRC - Longitudinal Redundancy Check) 3. RAID Storage (simplified view) The concept extends to RAID arrays: Data striped across multiple disks (columns) Parity disk stores column parity Single disk failure = single "column" error = recoverable 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.

Evolution from 2D Parity to Modern 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

Legacy of 2D Parity

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.

Two-dimensional Parity

From Detection to Correction: The Power of a Second Dimension

Concept and Construction

Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

Step 7

Single-bit Error Correction

Multi-bit Error Detection

Implementation in Code

Overhead Analysis

Interleaving: Protecting Against Burst Errors

Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

Step 7

Historical and Practical Applications

There’s more to understand.

Two-dimensional Parity

From Detection to Correction: The Power of a Second Dimension

Concept and Construction

Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

Step 7

Single-bit Error Correction

Multi-bit Error Detection

Implementation in Code

Overhead Analysis

Interleaving: Protecting Against Burst Errors

Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

Step 7

Historical and Practical Applications

There’s more to understand.