I'm trying to solve an exercise from the book Fundamentals of Error Correcting Codes, can somebody help me?
The problem is the following:
Let $C$ be an $[n, k, 7]$ perfect binary code.
(a) Using equality in the Sphere Packing Bound, prove that
$$(n+1)[(n+1)^2 −3(n+1)+8]=3·2^{n−k+1}.$$
(b) Prove that $n+1$ is either $2^b$ or $3·2^b$ where, in either case,
$b≤n−k+1$.(c) Prove that $b < 4$.
(d) Prove that $n=23$ or $n=7$.
(e) Name two codes that are perfect $[n, k, 7]$ codes, one with $n = 7$
and the other with $n = 23$.
For part a) I could easily prove the claim 🙂
For part b) I answered in the following way:
From part a) we know $n+1=(3·2^{n−k+1})/(n^2-n+6)$, so since $n$ is a
natural number, then so is $n+1$ and thus we can consider three cases:
1) $(n^2-n+6)$ divides $3$ (it does not divide $2^{n-k+1}$) -> $n+1=2^{n-k+1}$
OK2) $(n^2-n+6)$ divides both $3$ and $2^{n-k+1}$ -> $n+1=2^b$ with $b<=n-k+1$ OK
3) $(n^2-n+6)$ divides $2^{n-k+1}$ (it does not divides $3$) -> $n+1=3·2^b$ with $b<=n-k+1$ OK
I'm really not sure if it's enough to prove the claim or if there is some "more mathematically" proof. any suggestion?
For part c) I'm completely lost. I cannot find a way to prove that $b<4$.
(I tried to use the information that $C$ is a perfect code. but I'm stuck!)
& also for part d) & e) I need any suggestions.
Best Answer
The starting point is the identity (your part a) gotten by having an equality in the sphere packing bound $$(n+1)[(n+1)^2 −3(n+1)+8]=3·2^{n−k+1}.\qquad(*)$$