Bounds on linear code

68 Views Asked by At

My teacher taught us that according to hamming bound

(1) for a $[7,4]$ code $d_{min}\leq 3$,

(2) for a $[7,3]$ code $d_{min}\leq 4$.

But when I am applying hamming bound I get $d_{min}\leq 4$ for both the cases. Can someone explain it to me clearly with formula?

1

There are 1 best solutions below

0
On

The Hamming bound for a binary code with $n=7$ gives

$$ 2^{7-k} \ge \sum_{r=0}^t \binom{7}{r} =s(t) \tag{1}$$

with $s(0)=1$, $s(1)=8$, $s(2)=29 \dots$

Then, for $k=4$ we have $s(t)\ge 2^3 \implies t\le 1$

For $k=3$ we have $s(t)\ge 2^4 \implies t\le 1$

Now, $t=\lfloor (d-1)/2\rfloor$ , which gives $d \le 4$

In this sense, you are right: in principle, we could have a $(7,4)$ code with $d=4$ and the Hamming bound would not be violated.

But there's more. The thing is that the inequality in $(1)$ must be strict if the distance is even. If we had a $(7,4)$ code with $d=4$, then it would be "perfect" (the inequality $(1)$ turns an equality), so the union of the "balls" would cover all the space; but this is impossible if the distance is even. For more details, see this answer.