I am a bit confused on whether a binary (5,3,4)-code exists.
As far as I am aware, this code exists if and only if a binary (4,3,3)-code exists according to Theorem 2.7 in Raymond Hill's book "A first course in coding theory".
I tried to check the sphere packing bound and found that when M is 3, it does indeed satisfy the inequality of the sphere packing bound. However, when I try to construct either of these above codes, I cannot find a code that satisfies a length of 5, and a distance of at least 4.
Am I missing something?
Best Answer
The sphere-packing bound is an upper bound on the maximum size $M$ of a code of given length $n$ and minimum Hamming distance $d$. That this upper bound is a bit above $3$ for $n=4$ and $M=3$,
$$M\le\frac{2^4}{\binom40+\binom41}=3.2\;,$$
doesn’t imply that there is a code of size $3$; only that there can’t be a code of size greater than $3$. Indeed, there is no such code of size $3$, since if $a$ and $b$ differ in $3$ places, then $c$ must coincide with one of them in $2$ of those places, and can thus only differ from it in $4-2=2$ places.