Virtual Labs

ML Decoding of First-Order Reed-Muller Codes

For a first-order Reed-Muller code

RM(1, m)

, what are the code length

n

and dimension

k

in terms of

m

n = 2^m, \quad k = 2^m

Explanation

n = 2^m, \quad k = m + 1

Explanation

n = m, \quad k = m + 1

Explanation

n = 2^{m+1}, \quad k = m

Explanation

Which mapping is used to convert binary bits from

\mathbb{F}_2

to real values for transmission over the AWGN channel in this module?

0 \mapsto 0, \quad 1 \mapsto 1

Explanation

0 \mapsto -1, \quad 1 \mapsto +1

Explanation

0 \mapsto +1, \quad 1 \mapsto -1

Explanation

0 \mapsto 1, \quad 1 \mapsto 0

Explanation

In the recursive construction of the Sylvester-type Hadamard matrix

H_{2^m}

, which sub-block is negated?

a: The top-left block Explanation

Explanation

b: The top-right block Explanation

Explanation

c: The bottom-left block Explanation

Explanation

d: The bottom-right block Explanation

Explanation

What is the computational complexity of the Fast Hadamard Transform (FHT) for a vector of length

n=2^m

O(n^2)

O((2^m)^2)

Explanation

O(m 2^m)

O(n \log n)

Explanation

O(n)

O(2^m)

Explanation

O(m^2)

Explanation

In the decoding algorithm, what does the index

j

of the maximum absolute component of the Hadamard transform

\mathbf{Z}

determine?

a: The constant term

a_0

of the message polynomial. Explanation

Explanation

b: The linear coefficients

a_1, \dots, a_m

of the message polynomial. Explanation

Explanation

c: The noise vector

\mathbf{N}

. Explanation

Explanation

d: The magnitude of the error. Explanation

Explanation

If the component of the Hadamard transform with the largest magnitude,

Z_j

, is **negative**, what is the value of the constant term

\hat{a}_0

\hat{a}_0 = 0

Explanation

\hat{a}_0 = 1

Explanation

c: It cannot be determined. Explanation

Explanation

\hat{a}_0 = -1

Explanation

What does the Maximum Likelihood (ML) decoding rule simplify to for the AWGN channel?

a: Minimizing the Hamming distance. Explanation

Explanation

b: Maximizing the inner product (correlation) with the received vector. Explanation

Explanation

c: Solving a system of linear equations. Explanation

Explanation

d: Finding the codeword with the minimum weight. Explanation

Explanation

In the

RM(1,4)

example provided, the winning index was

j=11

(binary

1011

). What was the corresponding linear polynomial?

X_1 + X_3 + X_4

Explanation

X_1 + X_2 + X_4

Explanation

X_2 + X_3 + X_4

Explanation

X_1 + X_2 + X_3

Explanation

Why is the Hadamard Transform

\mathbf{Z} = \mathbf{Y} H_{2^m}

used in this decoding process?

a: It converts the noise into a binary error pattern. Explanation

Explanation

b: It computes the correlations between the received vector and all possible linear basis codewords simultaneously. Explanation

Explanation

c: It reduces the dimension of the code from

n

k

. Explanation

Explanation

d: It performs majority logic voting for each bit. Explanation

Explanation