Existence of codes

1.5k Views Asked by At

I am looking at the following exercise:

enter image description here

At $(a)$ and $(b)$ I have supposed that there is such a code. Then the Hamming bound has to be satisfied, i.e. $M \leq \frac{q^n}{\sum_{i=0}^{\lfloor \frac{d-1}{2}\rfloor} \binom{n}{i}(q-1)^i} $ .But this leads to a contradiction.

For $(d)$ I have thought that it holds that $ 2^{57}=\frac{2^{63}}{\sum_{i=0}^1 \binom{63}{i}} $. But from this we cannot deduce that there is a perfect binary linear code with parameters $(63, 2^{57},3)$, right?

At $(c)$ and $(d)$ the Hamming bound is satisfied. From this we cannot deduce that such codes exist. How can we determine whether the stated codes exist or not?

1

There are 1 best solutions below

3
On BEST ANSWER

You are right, Hamming bound gives only a necessary condition for existence; if it's satisfied, we cannot deduce anything.

A bound that gives a sufficient condition is the Gilbert–Varshamov bound. You can try to apply it to problems c) and d)

Regarding e), recall that the Hamming codes are perfect codes. Check if the parameters given allow the construction of a Hamming code (they do).