Virtual Labs

Majority Logic Decoding of Reed-Muller Codes

1. An

RM(r, m)

code has a minimum distance

d_{min} = 2^{m-r}

. What is its error correction capability

t

for majority logic decoding?

t = d_{min} - 1

Explanation

t = d_{min}

Explanation

t = 2^{m-r}

Explanation

t = \lfloor (d_{min}-1)/2 \rfloor

Explanation

2. What is the primary algebraic purpose of summing a polynomial's evaluations over a check set

\mathcal{V}_S(\mathbf{b})

a: To cancel the contribution of all monomials of degree less than

r = |S|

. Explanation

Explanation

b: To find the average value of the polynomial. Explanation

Explanation

c: To exclusively isolate the coefficient

a_S

, cancelling all other coefficients. Explanation

Explanation

d: To check the parity of the uninvolved variables

\mathbf{b}

. Explanation

Explanation

3. When decoding an

RM(3, 7)

code, how many disjoint check sets are used to vote for a single degree-3 coefficient (e.g.,

\hat{a}_{123}

a: 8 Explanation

Explanation

b: 16 Explanation

Explanation

c: 32 Explanation

Explanation

d: 4 Explanation

Explanation

4. In the iterative decoding algorithm, what is the purpose of the 'peel off' step (calculating

\mathbf{Y}_{i-1} = \mathbf{Y}_i + \mathbf{C}_i

a: To add the newly found coefficients

\hat{f}_i

to the final polynomial

\hat{f}

. Explanation

Explanation

b: To correct the errors in the working vector

\mathbf{Y}_i

before the next stage. Explanation

Explanation

c: To find the locations of the errors in the received vector. Explanation

Explanation

d: To remove the influence of the just-decoded degree-

i

terms, so they don't interfere with decoding the lower-degree terms. Explanation

Explanation

5. You are decoding an

RM(2, 4)

vector

\mathbf{Y}

(which has

t=1

). For the coefficient

\hat{a}_{34}

, the four check-sum estimates are

(1, 1, 0, 1)

. What is the decoded coefficient

\hat{a}_{34}

a: 0 Explanation

Explanation

b: 1 Explanation

Explanation

c: Failure (cannot be determined) Explanation

Explanation

d: 2 Explanation

Explanation