Cheap and Secure Web Hosting Provider : See Now

[Solved]: Existence of Hamming code

, , No Comments
Problem Detail: 

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?

Asked By : Evinda

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54667

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback