Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 3 / 3K / a

Table of contents
- Solution a

Solution

The Reed-Muller code is spanned by the evaluation vectors of the square-free monomials

\prod_{i \in I} x_{i}, ∣ I ∣ \leq r,

form a basis: every Boolean function has a unique algebraic normal form, so the monomials remain independent after evaluation on

F_{2}^{d}

. Thus

dim RM (d, r) = \sum_{j = 0}^{r} (j d) .

Induction using the decomposition

(u, u + v)

, with

u \in RM (d - 1, r)

and

v \in RM (d - 1, r - 1)

, gives the lower bound

2^{d - r}

for every nonzero weight. The monomial

x_{1} \dots x_{r}

attains it, so the minimum distance is

d_{m i n} = 2^{d - r} .

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version