# Multidimensional parity-check code

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Multidimensional_parity-check_code
> Markdown URL: https://mediated.wiki/source/Multidimensional_parity-check_code.md
> Source: https://en.wikipedia.org/wiki/Multidimensional_parity-check_code
> Source revision: 1274264320
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

A **multidimensional parity-check code (MDPC)** is a type of [error-correcting code](/source/Error-correcting_code) that generalizes two-dimensional [parity checks](/source/Parity_check) to higher dimensions. It was developed as an extension of simple parity check methods used in [magnetic recording systems](/source/Magnetic_tape) and [radiation-hardened](/source/Radiation_hardening) [memory designs](/source/Memory_architecture).[1]

## Overview

In an MDPC code, information bits are organized into an N-dimensional structure, where each [bit](/source/Bit) is protected by N [parity bits](/source/Parity_bit). Each parity bit is calculated along a different dimensional axis. The code can be characterized by its *dimension vector* r = [r_1, r_2, \cdots, r_n ], where r_i defines the size of the block or multi-block in the ith dimension. The code length c can be expressed as

- c = \prod_{n=1}^{N} r_n

while the number of information bits d is given by

- d = \prod_{n=1}^{N} (r_n - 1).[2]

### Reduced generator matrices

*Reduced generator matrices* eliminate redundant [parity bits](/source/Parity_bits) while maintaining error correction capabilities. This modification increases the code rate without significantly degrading performance. The code rate R for a reduced MDPC is given by

- R = \frac{d}{c} = \frac{\prod_{n=1}^{N} (r_n - 1)}{\prod_{n=1}^{N} r_n}.

The reduced generator matrix can be created using systematic construction methods, resulting in more efficient encoding processes compared to traditional parity check codes.

The following [pseudocode](/source/Pseudocode) shows how to generate a reduced generator matrix:[3]

**function** function_name **is** *// Initialize G with identity matrix augmented with ones column* G ← [I_{r1-1} | 1_{(r1-1)×1}] **for** n ← 2 to N **do** *// Update G with Kronecker product* G ← I_{r_n-1} ⊗ G *// Calculate product of previous dimensions* x ← Πi=1n-1(ri - 1) *// Create temporary matrix with ones column and identity* G_tmp ← 1_{(r_n-1)×1} ⊗ I_x *// Augment G with temporary matrix* G ← [G | G_tmp] **return** G **end function**

### Decoding algorithms

Decoding in MDPC systems typically employs an [iterative algorithm](/source/Iterative_algorithm) based on *Failed Dimension Markers (FDM)*, which indicate the number of parity check failures associated with each information bit. The FDM-based decoding process works by identifying bits with the highest probability of error and iteratively attempting corrections until either all errors are resolved or a maximum iteration limit is reached.[3]

## Applications

MDPC codes have applications in scenarios where short block lengths are required, such as [real-time communications](/source/Real-time_communication) systems and [memory protection](/source/Memory_protection) schemes. They offer several advantages over other [error-correcting codes](/source/Error-correcting_codes), including positive code gain at low [signal-to-noise ratios](/source/Signal-to-noise_ratio) and simpler implementation complexity compared to LDPC codes. The level of error protection can be adjusted by modifying the number of dimensions or the size of each dimension, allowing for flexibility in design trade-offs between code rate and error correction capability.[4]

## References

1. Q. L. Rao, C. He (2009). "A new 2-D parity checking architecture for radiation-hardened by design SRAM". *Asia Pacific Conference on Postgraduate Research in Microelectronics & Electronics*

1. J. M. Shea, T. F. Wong (2003). "Multidimensional Codes". *Encyclopedia of Telecommunications*. Wiley.

1. Ludek Dudácek, Ivo Vertat (2016). "Multidimensional Parity Check codes with short block lengths". *24th Telecommunications Forum TELFOR*

1. A. Vadinala, G. K. Kumar (2013). "Multi Dimensional Parity Based Hamming Codes For Correcting The SRAM Memory Faults Under High EMI Conditions". *IACEECE International Conference*

## See also

- [Error detection and correction](/source/Error_detection_and_correction)
- [Forward error correction](/source/Forward_error_correction)
- [Low-density parity-check code](/source/Low-density_parity-check_code)

---
Adapted from the Wikipedia article [Multidimensional parity-check code](https://en.wikipedia.org/wiki/Multidimensional_parity-check_code) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Multidimensional_parity-check_code?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.