Virtual Labs

Reed-Muller Codes : Generator and Parity Check Matrices and the Minimum Distance

1. The Reed-Muller code

RM(r, m)

is defined by evaluating a set of polynomials. What is the length

n

of all codewords in

RM(r, m)

2^r

Explanation

2^m

Explanation

\binom{m}{r}

Explanation

m+r

Explanation

2. Which of the following polynomials would be evaluated to create a codeword in

RM(2, 4)

? (Variables are

X_4, X_3, X_2, X_1

)

P(X_4, X_3, X_2, X_1) = X_4X_3X_2 + X_1

Explanation

P(X_4, X_3, X_2, X_1) = X_3X_1 + X_2 + 1

Explanation

P(X_4, X_3, X_2, X_1) = X_4X_3X_2X_1

Explanation

P(X_4, X_3, X_2, X_1) = X_1X_2X_3X_4 + X_2

Explanation

3. When defining the polynomial basis for

RM(r, m)

, why do we typically only use multilinear monomials (e.g.,

X_3X_1

) and not terms like

X_1^2

X_2^3

a: Because

X_i^k = X_i

for any

k \ge 1

when evaluating at any point

x_i \in \{0, 1\}

. Explanation

Explanation

b: Because polynomials with higher powers are too difficult to evaluate. Explanation

Explanation

c: Because the degree

r

is always less than 2. Explanation

Explanation

d: Because

X_i^k = 0

F_2

, so these terms vanish. Explanation

Explanation

4. Which codewords are present in the

RM(0, m)

code?

a: The all-zero vector and the all-one vector. Explanation

Explanation

b: Every vector with even weight and length

2^m

. Explanation

Explanation

c: There are

m

codewords, one for each variable. Explanation

Explanation

d: Only the all-zero vector. Explanation

Explanation

5. What is the dimension

k

of the Reed-Muller code

RM(1, 4)

a: 16 Explanation

Explanation

b: 4 Explanation

Explanation

c: 5 Explanation

Explanation

d: 8 Explanation

Explanation

6. What is the minimum distance

d

of the

RM(r, m)

code?

2^{r+m}

Explanation

2^r

Explanation

2^{m-r}

Explanation

2^{r-m}

Explanation

7. Which specific code is

RM(m, m)

equivalent to?

a: The repetition code

RM(0, m)

. Explanation

Explanation

b: The single-parity-check code

RM(m-1, m)

. Explanation

Explanation

c: The entire space

\mathbb{F}_2^n

, where

n=2^m

. Explanation

Explanation

d: The empty code containing only the zero vector. Explanation

Explanation

8. Let

C_1 = RM(r, m)

and

C_2 = RM(r+1, m)

. What is the relationship between these two codes?

C_1

is a subcode of

C_2

(

C_1 \subseteq C_2

). Explanation

Explanation

C_2

is a subcode of

C_1

(

C_2 \subseteq C_1

). Explanation

Explanation

C_1

and

C_2

are disjoint (except for the zero vector). Explanation

Explanation

C_1

is the dual code of

C_2

(

C_1 = C_2^\perp

). Explanation

Explanation