Multidimensional parity-check code

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

Overview

In an MDPC code, information bits are organized into an ${\displaystyle N}$-dimensional structure, where each bit is protected by ${\displaystyle N}$ parity bits. Each parity bit is calculated along a different dimensional axis. The code can be characterized by its dimension vector${\displaystyle r=[r_{1},r_{2},\cdots ,r_{n}]}$, where ${\displaystyle r_{i}}$ defines the size of the block or multi-block in the ${\displaystyle i}$th dimension. The code length ${\displaystyle c}$ can be expressed as

${\displaystyle c=\prod _{n=1}^{N}r_{n}}$

while the number of information bits ${\displaystyle d}$ is given by

${\displaystyle d=\prod _{n=1}^{N}(r_{n}-1)}$. ^[2]

Reduced generator matrices

Reduced generator matrices eliminate redundant parity bits while maintaining error correction capabilities. This modification increases the code rate without significantly degrading performance. The code rate ${\displaystyle R}$ for a reduced MDPC is given by

${\displaystyle 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 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 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 systems and memory protection schemes. They offer several advantages over other error-correcting codes, including positive code gain at low signal-to-noise ratios 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. pp. 360–363.
2. J. M. Shea, T. F. Wong (2003). "Multidimensional Codes". Encyclopedia of Telecommunications. Wiley.
3. Ludek Dudácek, Ivo Vertat (2016). Multidimensional Parity Check codes with short block lengths. 24th Telecommunications Forum TELFOR. pp. 1–4.
4. 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. pp. 46–49.

See also

• Error detection and correction
• Forward error correction
• Low-density parity-check code