Virtual Labs

ML Decoding of First-Order Reed-Muller Codes

1. Which of the following statements correctly defines the Reed-Muller code

RM(r, m)

in terms of Boolean polynomials?

a: The set of all Boolean polynomials in

m

variables with degree exactly equal to

r

. Explanation

Explanation

b: The set of all Boolean polynomials in

m

variables with degree at most

r

. Explanation

Explanation

c: The set of all Boolean polynomials in

r

variables with degree at most

m

. Explanation

Explanation

d: The set of all homogenous Boolean polynomials of degree

r

. Explanation

Explanation

2. Using the

(u | u + v)

construction (Plotkin construction), how can the Reed-Muller code

RM(r, m)

be decomposed?

RM(r, m) = \{(u, u+v) \mid u \in RM(r-1, m-1), v \in RM(r, m-1)\}

Explanation

RM(r, m) = \{(u, u+v) \mid u \in RM(r, m-1), v \in RM(r-1, m-1)\}

Explanation

RM(r, m) = \{(u, v) \mid u \in RM(r, m-1), v \in RM(r-1, m-1)\}

Explanation

RM(r, m) = \{(u+v, v) \mid u \in RM(r-1, m-1), v \in RM(r, m-1)\}

Explanation

3. What is the minimum Hamming distance

d

of the Reed-Muller code

RM(r, m)

2^{m-r}

Explanation

2^{r}

Explanation

2^{m-1}

Explanation

2^{m-r-1}

Explanation

4. Which duality relationship holds for Reed-Muller codes?

RM(r, m)^\perp = RM(r, m)

Explanation

RM(r, m)^\perp = RM(m-r, m)

Explanation

RM(r, m)^\perp = RM(m-r-1, m)

Explanation

RM(r, m)^\perp = RM(r-1, m)

Explanation

5. In Majority Logic Decoding for

RM(r, m)

, what is the primary mechanism for determining the coefficient of a highest-degree monomial?

a: Solving a system of linear equations using Gaussian elimination. Explanation

Explanation

b: Taking a vote based on the parity sums of disjoint subsets of the received vector. Explanation

Explanation

c: Iteratively flipping bits until the syndrome weight is minimized. Explanation

Explanation

d: Calculating the Fourier transform of the received vector. Explanation

Explanation