🔬 2D Parity Matrix Virtual Laboratory

OSI Layer 2: Error Detection and Correction

ECE 422-Data Communication & Computer Networks

1. Introduction to 2D Parity Check

Two-dimensional (2D) parity checking, also known as Longitudinal Redundancy Check (LRC) combined with Vertical Redundancy Check (VRC), is an error detection and correction technique used in digital communications and data storage systems.

Key Concept: 2D parity extends the simple 1D parity check by organizing data into a matrix and calculating parity bits for both rows and columns, enabling the detection and correction of single-bit errors.

2. Mathematical Foundation

2.1 Parity Bit Calculation

For a data matrix with m rows and n columns:

Row Parity: Prow,i = di,1 ⊕ di,2 ⊕ ... ⊕ di,n   (for i = 1 to m)
Column Parity: Pcol,j = d1,j ⊕ d2,j ⊕ ... ⊕ dm,j   (for j = 1 to n)
Corner Parity: Pcorner = (⊕ all row parities) = (⊕ all column parities)

2.2 Error Detection Capability

  • Single-bit errors: Detected and Corrected ✓
  • Two-bit errors: Detected but not corrected ✓
  • Three-bit errors: Detected (in most cases) ✓
  • Four-bit errors (rectangle): Undetected ✗

3. 2D Parity Matrix Structure

Example: 4×4 Data Matrix with Parity

Data Bits | Parity
-------------------
1 0 1 1 | 1 (Row 1 parity: 1⊕0⊕1⊕1 = 1)
0 1 0 0 | 1 (Row 2 parity: 0⊕1⊕0⊕0 = 1)
1 1 1 0 | 1 (Row 3 parity: 1⊕1⊕1⊕0 = 1)
0 0 1 1 | 0 (Row 4 parity: 0⊕0⊕1⊕1 = 0)
-------------------
0 0 1 0 | 0 (Column parities + Corner)

Advantages

  • Can correct single-bit errors
  • Detects all 1, 2, and 3-bit errors
  • Simple implementation
  • Low computational overhead
  • Burst error detection capability

Limitations

  • Cannot correct multiple-bit errors
  • Even number of errors may cancel out
  • Redundancy overhead: (m+n+1)/(m×n)
  • Rectangle pattern errors undetected

4. Applications in Communication Systems

  • Data Link Layer: Used in ARQ (Automatic Repeat Request) protocols
  • Memory Systems: DRAM error correction
  • Storage Systems: RAID arrays
  • Satellite Communication: Where retransmission is costly
  • Embedded Systems: Critical data integrity checking

5. Efficiency Analysis

Redundancy ratio for an m×n matrix:

Efficiency η = (m × n) / [(m+1) × (n+1)] × 100%
89% 8×8
80% 4×4
64% 2×2
94% 16×16

Data Efficiency vs Matrix Size

Interactive 2D Parity Matrix Simulator

Experiment with 2D parity matrices. Click on data cells to flip bits and observe error detection and correction capabilities.

Data Bits
Parity Bits
Corner Parity
Error Detected

Manual Error Injection

Click on any data cell in the matrix above to inject an error (flip the bit). Then use "Check & Correct" to detect and fix it.

💡 Click "Generate New Matrix" to start the simulation

Simulation Results

Simulation results will appear here...

Experimental Procedure

Step 1: Understanding the Setup

Familiarize yourself with the 2D parity matrix structure. Understand that:

  • Data bits form the main matrix (m × n)
  • Row parity bits are appended to each row
  • Column parity bits are appended to each column
  • The corner bit ensures overall parity consistency

Step 2: Matrix Generation

  1. Select desired matrix size (4×4 recommended for initial experiments)
  2. Choose parity type (Even or Odd)
  3. Click "Generate New Matrix" to create a random data matrix
  4. Observe how parity bits are calculated and positioned
  5. Manually verify at least one row and one column parity calculation

Step 3: Single Error Injection and Detection

  1. Inject a single-bit error by clicking on any data cell
  2. Note the position of the error (row i, column j)
  3. Click "Check & Correct" to run the error detection algorithm
  4. Observe how the system identifies the error location
  5. Verify that the error is corrected automatically
  6. Record the row and column parity mismatch indicators

Step 4: Multiple Error Analysis

  1. Generate a fresh matrix
  2. Inject two errors in different rows and columns
  3. Attempt detection and correction
  4. Record whether the errors are detected
  5. Note: 2D parity can detect but NOT correct double errors
  6. Repeat with three errors and four errors (rectangular pattern)

Step 5: Burst Error Simulation

  1. Create a matrix with adjacent errors (burst)
  2. Test detection capability
  3. Vary the burst length from 2 to n bits
  4. Analyze detection probability vs burst length

Step 6: Efficiency Calculation

  1. For each matrix size tested, calculate:
    Overhead = (m + n + 1) / [(m+1)(n+1)] × 100%
  2. Plot efficiency vs matrix size
  3. Determine optimal matrix size for your application

Step 7: Comparative Analysis

  1. Compare even vs odd parity performance
  2. Test with all-zeros and all-ones data patterns
  3. Analyze worst-case scenarios
  4. Document limitations observed

Data Recording Table

Use this template to record your experimental data:

Exp # Matrix Size Errors Injected Error Pattern Detected? Corrected? Comments
1 4×4 1 Single bit Yes/No Yes/No
2 4×4 2 Different rows/cols Yes/No N/A
3 4×4 2 Same row Yes/No N/A
4 4×4 4 Rectangle pattern Yes/No N/A

Lab Report Guidelines

1. Title Page

  • Experiment Title: 2D Parity Matrix Error Detection and Correction
  • Course Name and Code
  • Student Name and ID
  • Date of Experiment
  • Instructor Name

2. Abstract (150-200 words)

Briefly summarize:

  • Objective of the experiment
  • Methodology used (2D parity checking)
  • Key findings (error detection/correction capabilities)
  • Conclusions about efficiency and limitations

3. Introduction and Theory

  • Explain the need for error detection in digital communications
  • Describe 1D parity vs 2D parity
  • Mathematical formulation of parity calculation
  • Hamming distance concept (dmin = 4 for 2D parity)
  • Applications in real-world systems

4. Experimental Setup

  • Description of the virtual laboratory tool
  • Matrix sizes tested
  • Parity schemes used (even/odd)
  • Error injection methods
  • Parameters varied during experiments

5. Results and Analysis

Include the following:

  • Tables of experimental data (minimum 10 trials)
  • Sample matrices showing before/after error correction
  • Detection rate vs number of errors (graph)
  • Correction capability analysis
  • Undetected error patterns identified
  • Efficiency calculations for different matrix sizes

6. Discussion

Address these points:

  • Why can 2D parity correct single errors but not double errors?
  • Explain the rectangle pattern undetected error phenomenon
  • Compare theoretical vs observed detection rates
  • Trade-off between matrix size and overhead
  • Practical limitations in high-speed communication

7. Conclusion

  • Summary of findings
  • Effectiveness of 2D parity for error control
  • Recommendations for suitable applications
  • Suggested improvements or alternative methods

8. References

Cite textbooks and papers on error control coding, such as:

  • Tanenbaum, A.S. & Wetherall, D.J. (2011). Computer Networks (5th Ed.)
  • Stallings, W. (2013). Data and Computer Communications
  • Lin, S. & Costello, D.J. (2004). Error Control Coding

9. Appendices (if needed)

  • Source code of custom calculations
  • Additional matrix examples
  • Raw experimental data

Grading Rubric

Component Weight Criteria
Theory Understanding 20% Clear explanation of 2D parity mechanism
Experimental Data 25% Completeness, accuracy, organization
Analysis 25% Depth of insight, error pattern analysis
Presentation 15% Clarity, formatting, diagrams
Conclusions 15% Validity, relation to theory

2D Parity Calculator

Calculate parity bits for your own data matrix.

Efficiency Calculator

Error Probability Calculator