1
$\begingroup$

We are given a number $n \geq 3$ and we know that the Hamming bound is satisfied. Does this imply that there is a Hamming code with length $\frac{q^r-1}{q-1}$, dimension $\frac{q^r-1}{q-1}-r$ and Hamming-distance $3$ or do we have to construct such a code, given that the bound is satisfied?

$\endgroup$
  • 1
    $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Apr 9 '16 at 14:31
4
$\begingroup$

The Hamming bound is an upper bound on the size of codes. It's not a tight bound in general, though in some specific cases it is achievable. Codes achieving the Hamming bound are called perfect codes.

When the alphabet size is a prime power, all perfect codes are known: apart from some trivial cases (repetition codes, codes with one codeword, and codes containing all possible codewords), they share the same parameters as a Hamming code or a Golay code.

What this means is that if your alphabet size is a prime power and you have parameters satisfying the Hamming bound, then a code with these parameters actually exists only in the cases listed above. In any other case, the bound isn't tight.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.