Tools

ML Decoding of First-Order Reed-Muller Codes

Decoding RM(1,m) Codes on the AWGN Channel

While majority logic decoding is highly effective for Reed-Muller codes on binary channels, an even more efficient algorithm exists for decoding first-order Reed-Muller codes, RM(1,m)RM(1,m), on the Additive White Gaussian Noise (AWGN) channel. This method, based on the Fast Hadamard Transform (FHT), performs Maximum Likelihood (ML) decoding with remarkable speed.

1. Preliminaries: ML Decoding for the AWGN Channel

First, let's establish the model. An RM(1,m)RM(1,m) code is a linear code of length n=2mn=2^m and dimension k=m+1k=m+1. Its basis functions are the constant monomial 11 and the mm linear monomials {X1,X2,…,Xm}\{X_1, X_2, \dots, X_m\}.

To transmit a binary codeword C∈RM(1,m)\mathbf{C} \in RM(1,m) over an AWGN channel, we must first map its bits to real values. We use the standard bipolar mapping:

  • 0∈F2↦+1∈R0 \in \mathbb{F}_2 \mapsto +1 \in \mathbb{R}
  • 1∈F2↦−1∈R1 \in \mathbb{F}_2 \mapsto -1 \in \mathbb{R}

This converts the binary codeword C\mathbf{C} into a bipolar vector Cbip\mathbf{C}_{bip}. The channel then adds a noise vector N\mathbf{N}, whose components are independent, identically distributed Gaussian random variables. The received vector Y\mathbf{Y} is: Y=Cbip+N \mathbf{Y} = \mathbf{C}_{bip} + \mathbf{N} The goal of the decoder is to find the most likely transmitted codeword given the received vector Y\mathbf{Y}. For the AWGN channel, the Maximum Likelihood (ML) decoding rule simplifies to finding the codeword that maximizes the inner product (or correlation) with the received vector: C^bip=arg⁡max⁡∗c∈C∗bip⟨Y,c⟩ \hat{\mathbf{C}}_{bip} = \arg\max*{\mathbf{c} \in \mathcal{C}*{bip}} \langle \mathbf{Y}, \mathbf{c} \rangle where Cbip\mathcal{C}_{bip} is the set of all 2m+12^{m+1} bipolar codewords of the RM(1,m)RM(1,m) code. A brute-force search is computationally expensive.

2. The Hadamard Matrix

The key to efficient decoding lies in the structure of the Sylvester-type Hadamard matrices, which are defined recursively for orders N=2mN=2^m:

  • Base Case (m=1m=1): H2=(111−1)H_2 = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}
  • Recursive Step: H2m=(H2m−1H2m−1H2m−1−H2m−1)H_{2^m} = \begin{pmatrix} H_{2^{m-1}} & H_{2^{m-1}} \\ H_{2^{m-1}} & -H_{2^{m-1}} \end{pmatrix}

2.1 Step-by-Step Construction

The recursive definition provides a clear method for building larger Hadamard matrices.

  • Constructing H2H_2 (Base Case): The construction starts with the 2×22 \times 2 base matrix: H2=(111−1) H_2 = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}

  • Constructing H4H_4: We construct H4H_4 by arranging four copies of H2H_2 in a block structure, negating the bottom-right block: H4=(H2H2H2−H2)=(11111−11−111−1−11−1−11) H_4 = \begin{pmatrix} H_2 & H_2 \\ H_2 & -H_2 \end{pmatrix} = \left( \begin{array}{cc|cc} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ \hline 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{array} \right) This yields the final 4×44 \times 4 matrix: H4=(11111−11−111−1−11−1−11) H_4 = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{pmatrix}

  • Constructing H8H_8: Similarly, H8H_8 is constructed from four blocks of the H4H_4 matrix: H8=(H4H4H4−H4) H_8 = \begin{pmatrix} H_4 & H_4 \\ H_4 & -H_4 \end{pmatrix} Substituting the matrix for H4H_4 results in the final 8×88 \times 8 matrix: H8=(111111111−11−11−11−111−1−111−1−11−1−111−1−111111−1−1−1−11−11−1−11−1111−1−1−1−1111−1−11−111−1) H_8 = \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 & 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 & 1 & -1 & -1 & 1 \\ 1 & 1 & 1 & 1 & -1 & -1 & -1 & -1 \\ 1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 \\ 1 & 1 & -1 & -1 & -1 & -1 & 1 & 1 \\ 1 & -1 & -1 & 1 & -1 & 1 & 1 & -1 \end{pmatrix}

2.2 The Crucial Connection: Codewords as Hadamard Rows

The set of all 1616 bipolar codewords of the RM(1,3)RM(1,3) code is precisely the set of the 8 rows of H8H_8 and their negatives. We denote the rows of H8H_8 as h0,h1,…,h7\mathbf{h}_0, \mathbf{h}_1, \dots, \mathbf{h}_7.

A codeword is generated by a polynomial f(X)=a0+a1X1+a2X2+a3X3f(\mathbf{X}) = a_0 + a_1 X_1 + a_2 X_2 + a_3 X_3. The linear part, a1X1+a2X2+a3X3a_1 X_1 + a_2 X_2 + a_3 X_3, corresponds to a specific row of H8H_8, while the constant term, a0a_0, determines its sign. The bipolar codeword for the linear part is hj\mathbf{h}_j, where jj is the integer whose binary representation is (a1a2a3)(a_1 a_2 a_3).

The following table explicitly shows all 16 codewords of RM(1,3)RM(1,3) and their relationship to the rows of H8H_8.

Message Polynomial f(X)f(\mathbf{X}) Index jj Binary Rep. (a1a2a3)(a_1a_2a_3) Binary Codeword C\mathbf{C} Corresponding Hadamard Row
00 0 000 (0,0,0,0,0,0,0,0)(0,0,0,0,0,0,0,0) h0\mathbf{h}_0
11 0 000 (1,1,1,1,1,1,1,1)(1,1,1,1,1,1,1,1) −h0-\mathbf{h}_0
X3X_3 1 001 (0,1,0,1,0,1,0,1)(0,1,0,1,0,1,0,1) h1\mathbf{h}_1
1+X31+X_3 1 001 (1,0,1,0,1,0,1,0)(1,0,1,0,1,0,1,0) −h1-\mathbf{h}_1
X2X_2 2 010 (0,0,1,1,0,0,1,1)(0,0,1,1,0,0,1,1) h2\mathbf{h}_2
1+X21+X_2 2 010 (1,1,0,0,1,1,0,0)(1,1,0,0,1,1,0,0) −h2-\mathbf{h}_2
X2+X3X_2+X_3 3 011 (0,1,1,0,0,1,1,0)(0,1,1,0,0,1,1,0) h3\mathbf{h}_3
1+X2+X31+X_2+X_3 3 011 (1,0,0,1,1,0,0,1)(1,0,0,1,1,0,0,1) −h3-\mathbf{h}_3
X1X_1 4 100 (0,0,0,0,1,1,1,1)(0,0,0,0,1,1,1,1) h4\mathbf{h}_4
1+X11+X_1 4 100 (1,1,1,1,0,0,0,0)(1,1,1,1,0,0,0,0) −h4-\mathbf{h}_4
X1+X3X_1+X_3 5 101 (0,1,0,1,1,0,1,0)(0,1,0,1,1,0,1,0) h5\mathbf{h}_5
1+X1+X31+X_1+X_3 5 101 (1,0,1,0,0,1,0,1)(1,0,1,0,0,1,0,1) −h5-\mathbf{h}_5
X1+X2X_1+X_2 6 110 (0,0,1,1,1,1,0,0)(0,0,1,1,1,1,0,0) h6\mathbf{h}_6
1+X1+X21+X_1+X_2 6 110 (1,1,0,0,0,0,1,1)(1,1,0,0,0,0,1,1) −h6-\mathbf{h}_6
X1+X2+X3X_1+X_2+X_3 7 111 (0,1,1,0,1,0,0,1)(0,1,1,0,1,0,0,1) h7\mathbf{h}_7
1+X1+X2+X31+X_1+X_2+X_3 7 111 (1,0,0,1,0,1,1,0)(1,0,0,1,0,1,1,0) −h7-\mathbf{h}_7

3. ML Decoding via the Hadamard Transform

The Hadamard Transform of a vector Y\mathbf{Y} is the matrix-vector product Z=YH2m\mathbf{Z} = \mathbf{Y} H_{2^m}. The jj-th component of Z\mathbf{Z} is the inner product ⟨Y,hj⟩\langle \mathbf{Y}, \mathbf{h}_j \rangle. This single operation computes the correlations with all candidate codewords simultaneously.

The Algorithm: Input: A received vector Y\mathbf{Y} of length n=2mn=2^m. Output: The decoded message polynomial f^(X)\hat{f}(\mathbf{X}).

  1. Transform: Compute the Hadamard Transform of the received vector: Z=YH_2m \mathbf{Z} = \mathbf{Y} H\_{2^m}
  2. Search: Find the index jj corresponding to the component of Z\mathbf{Z} with the largest absolute value over all 2m2^m possible indices: j=arg⁡max⁡_i∈{0,…,2m−1}∣Zi∣ j = \arg\max\_{i \in \{0, \dots, 2^m-1\}} |Z_i|
  3. Decode: Let the binary representation of jj be (b1b2…bm)(b_1 b_2 \dots b_m). a. The linear part of the polynomial is a^1X1+⋯+a^mXm\hat{a}_1 X_1 + \dots + \hat{a}_m X_m, where a^i=bi\hat{a}_i = b_i. b. The constant term a^0\hat{a}_0 is determined by the sign of ZjZ_j. If Zj<0Z_j < 0, then a^0=1\hat{a}_0 = 1. If Zj>0Z_j > 0, then a^0=0\hat{a}_0 = 0.

4. The Fast Hadamard Transform (FHT)

A direct matrix-vector multiplication takes O((2m)2)O((2^m)^2) operations. The FHT is an efficient algorithm that reduces this complexity to O(m2m)O(m 2^m) by exploiting the recursive structure of the Hadamard matrix.

5. Detailed Decoding Example 1: RM(1,3)

  • Parameters: m=3,r=1,n=8,k=4m=3, r=1, n=8, k=4.

Step 1: Transmitted Codeword

  • Message Polynomial: f(X)=1+X1+X3f(\mathbf{X}) = 1 + X_1 + X_3.
  • Binary Codeword C=Eval(1)⊕Eval(X1)⊕Eval(X3)=(1,0,1,0,0,1,0,1)\mathbf{C} = \text{Eval}(1) \oplus \text{Eval}(X_1) \oplus \text{Eval}(X_3) = (1,0,1,0,0,1,0,1).
  • Bipolar Codeword Cbip=(−1,+1,−1,+1,+1,−1,+1,−1)\mathbf{C}_{bip} = (-1, +1, -1, +1, +1, -1, +1, -1). This corresponds to −h5-\mathbf{h}_5.

Step 2: Received Vector

  • Noise Vector N=(0.1,−0.2,0.2,0.1,−0.3,0.1,−0.1,0.2)\mathbf{N} = (0.1, -0.2, 0.2, 0.1, -0.3, 0.1, -0.1, 0.2).
  • Received Vector Y=Cbip+N=(−0.9,0.8,−0.8,1.1,0.7,−0.9,0.9,−0.8)\mathbf{Y} = \mathbf{C}_{bip} + \mathbf{N} = (-0.9, 0.8, -0.8, 1.1, 0.7, -0.9, 0.9, -0.8).

Step 3: Hadamard Transform

  • Compute Z=YH8\mathbf{Z} = \mathbf{Y} H_8. The resulting vector is: Z=(0.1,3.7,2.3,3.1,−2.5,−1.9,−0.5,−8.3) \mathbf{Z} = (0.1, 3.7, 2.3, 3.1, -2.5, -1.9, -0.5, -8.3)

Step 4: Search and Decode

  • Search: By inspection, the component with the largest absolute value is Z7=−8.3Z_7 = -8.3. The winning index is j=7j=7.
  • Decode: a. The binary representation of j=7j=7 is (111)2(111)_2. With ordering (X1,X2,X3X_1,X_2,X_3), this gives a^1=1,a^2=1,a^3=1\hat{a}_1=1, \hat{a}_2=1, \hat{a}_3=1. The linear part is X1+X2+X3X_1+X_2+X_3. b. The sign of Z7Z_7 is negative, so the constant term is a^0=1\hat{a}_0=1.
  • Final Result: The decoded polynomial is f^(X)=1+X1+X2+X3\hat{f}(\mathbf{X}) = 1 + X_1 + X_2 + X_3. The decoding is successful.

6. Detailed Decoding Example 2: RM(1,4)

  • Parameters: m=4,r=1,n=16,k=5m=4, r=1, n=16, k=5.

Step 1: Transmitted Codeword

  • Message Polynomial: f(X)=X1+X3+X4f(\mathbf{X}) = X_1 + X_3 + X_4.
  • The linear part corresponds to index jj with binary rep (a1a2a3a4)=(1011)2=11(a_1a_2a_3a_4)=(1011)_2 = 11.
  • Binary Codeword is C=Eval(X1+X3+X4)=(0,1,0,1,1,0,1,0,1,0,1,0,0,1,0,1)\mathbf{C} = \text{Eval}(X_1+X_3+X_4) = (0,1,0,1,1,0,1,0,1,0,1,0,0,1,0,1).
  • Bipolar Codeword Cbip=(+1,−1,+1,−1,−1,+1,−1,+1,−1,+1,−1,+1,+1,−1,+1,−1)\mathbf{C}_{bip} = (+1,-1,+1,-1,-1,+1,-1,+1,-1,+1,-1,+1,+1,-1,+1,-1). This corresponds to h11\mathbf{h}_{11} of H16H_{16}.

Step 2: Received Vector

  • A small random noise vector N\mathbf{N} is added, resulting in the received vector Y\mathbf{Y}: Y=(0.9,−1.2,1.1,−0.8,−1.1,0.9,−0.8,1.2,−0.9,0.8,−1.2,1.1,1.2,−0.9,0.8,−1.1) \mathbf{Y} = (0.9, -1.2, 1.1, -0.8, -1.1, 0.9, -0.8, 1.2, -0.9, 0.8, -1.2, 1.1, 1.2, -0.9, 0.8, -1.1)

Step 3: Hadamard Transform

  • We compute the transform Z=YH16\mathbf{Z} = \mathbf{Y} H_{16}. We expect the component Z11Z_{11} to have the largest magnitude.
  • The calculation of the full transform yields a vector where ∣Z11∣|Z_{11}| is the maximum value. For instance, Z11=⟨Y,h11⟩Z_{11} = \langle \mathbf{Y}, \mathbf{h}_{11} \rangle. Since Y\mathbf{Y} is a noisy version of h11\mathbf{h}_{11}, this inner product will be a large positive number. A full FHT calculation would show Z11≈15.0Z_{11} \approx 15.0, while all other components are significantly smaller.

Step 4: Search and Decode

  • Search: The component with the largest absolute value is found to be Z11≈15.0Z_{11} \approx 15.0. The winning index is j=11j=11.
  • Decode: a. The binary representation of j=11j=11 is (1011)2(1011)_2. With ordering (X1,X2,X3,X4X_1,X_2,X_3,X_4), this gives a^1=1,a^2=0,a^3=1,a^4=1\hat{a}_1=1, \hat{a}_2=0, \hat{a}_3=1, \hat{a}_4=1. The linear part is X1+X3+X4X_1+X_3+X_4. b. The sign of Z11Z_{11} is positive, so the constant term is a^0=0\hat{a}_0=0.
  • Final Result: The decoded polynomial is f^(X)=X1+X3+X4\hat{f}(\mathbf{X}) = X_1 + X_3 + X_4. The decoding is successful.