How Reed-Muller Codes Correct Multidimensional Errors

Reed-Muller (RM) codes are a foundational class of linear error-correcting codes that model information as multivariate polynomials evaluated over a binary hypercube. By mapping binary data to geometric coordinates across multiple dimensions, these codes structure redundancy so that errors localized or dispersed across multidimensional binary patterns can be detected and systematically resolved. Through fast majority-logic decoding, Reed-Muller codes isolate and eliminate corrupted bits level by level across affine subspaces, restoring the original binary transmission.

Binary Representation via Multivariate Polynomials

A classic binary Reed-Muller code, denoted as \(\text{RM}(r, m)\), is defined by two integer parameters: the order \(r\) and the dimension \(m\), where \(0 \le r \le m\). The code length is \(n = 2^m\), representing the total number of vertices in an \(m\)-dimensional binary vector space \(\mathbb{F}_2^m\).

  1. Coordinate Mapping: Every position in a codeword corresponds to a binary vector \((v_1, v_2, \dots, v_m) \in \{0, 1\}^m\).
  2. Boolean Polynomials: A message is encoded as the evaluation of a multivariate Boolean polynomial \(f(x_1, x_2, \dots, x_m)\) of degree at most \(r\) over \(\mathbb{F}_2\).
  3. Codeword Construction: The general polynomial takes the form: \[f(x_1, \dots, x_m) = a_0 + \sum_{i=1}^m a_i x_i + \sum_{i < j} a_{ij} x_i x_j + \dots + \sum_{i_1 < \dots < i_r} a_{i_1 \dots i_r} x_{i_1} \dots x_{i_r}\] where all coefficients \(a\) and variables \(x\) belong to \(\{0, 1\}\). Evaluating \(f\) across all \(2^m\) binary coordinate combinations produces the \(2^m\)-bit codeword.

Because the variables represent orthogonal axes in an \(m\)-dimensional space, the binary codeword inherently arranges message bits across a geometric hypercube.

Modeling Multidimensional Error Patterns

When a codeword is transmitted through a noisy channel, bit flips alter values at specific coordinates within the \(m\)-dimensional hypercube. The received vector \(R\) is expressed as \(R = C \oplus E\), where \(C\) is the transmitted codeword, \(E\) is the binary error vector, and \(\oplus\) denotes bitwise modulo-2 addition.

In the binary hypercube framework: * An error pattern \(E\) corresponds to an indicator function that takes the value \(1\) at corrupted coordinates and \(0\) elsewhere. * Errors may manifest as isolated coordinate flips, dense clusters along particular sub-dimensions (lines or planes), or distributed patterns spanning multiple orthogonal directions. * The minimum Hamming distance of an \(\text{RM}(r, m)\) code is \(d_{\min} = 2^{m-r}\), which guarantees the correction of any arbitrary error pattern containing up to: \[t = \left\lfloor \frac{2^{m-r} - 1}{2} \right\rfloor\] erroneous bits, regardless of how they are distributed across the multidimensional grid.

Error Correction via Majority-Logic Decoding

Reed-Muller codes correct errors using Reed’s majority-logic decoding, an algorithm that leverages the geometric properties of affine subspaces within \(\mathbb{F}_2^m\). The decoder works iteratively from the highest-degree terms down to the constant term.

1. Isolating Higher-Degree Coefficients

To determine the coefficient of a degree-\(k\) monomial (such as \(a_{1,2,\dots,k}\) for \(x_1 x_2 \dots x_k\)), the algorithm selects an affine subspace of dimension \(m-k\) where the remaining variables \((x_{k+1}, \dots, x_m)\) vary over all \(2^{m-k}\) possible states while the target variables are held fixed.

Summing the received values over this subspace yields a parity check. Because lower-degree polynomials evaluate to an even number of ones across complete affine subspaces, their contributions cancel out under modulo-2 arithmetic. Consequently, each parity check isolates the specific target coefficient plus a combination of channel errors.

2. Majority Voting

For each coefficient of degree \(k\), there exist \(2^{m-k}\) parallel, non-overlapping affine subspaces that yield independent estimates of that coefficient.

The decoder computes the binary parity sum for each subspace and applies a majority vote: * If the majority of the parity checks evaluate to \(1\), the coefficient is decided as \(1\). * If the majority evaluate to \(0\), the coefficient is decided as \(0\).

Because the error budget \(t < 2^{m-r-1}\) is smaller than half the number of independent checks (\(2^{m-k-1}\) for \(k \le r\)), corruptions cannot flip the outcome of the majority vote.

3. Successive Cancellation of Errors

Once all coefficients of degree \(r\) are determined: 1. Their corresponding polynomial evaluations are generated and subtracted (via modulo-2 addition) from the received vector. 2. This removes the higher-order component from the corrupted word, effectively reducing the decoding problem to an \(\text{RM}(r-1, m)\) code. 3. The process repeats recursively for degrees \(r-1, r-2, \dots, 0\).

After the constant term \(a_0\) is evaluated and subtracted, all errors in the received word are fully rectified, reconstructing the exact original binary message.