What about $[n,k,7]$ binary perfect code? (Exercise from the book Fundamentals of Error Correcting Codes)

coding-theory

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}$
OK

2) $(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(*)$$

  • Equation $(*)$ tells us that $n+1$ is a factor of the integer $3\cdot 2^{n-k+1}$. By the uniqueness of integer factorization it follows that $n+1=3^\epsilon\cdot 2^b$ with $\epsilon\in\{0,1\},0\le b\le n-k+1$. This settles part (b).
  • Assume that $b\ge4$. It follows that both $(n+1)^2$ and $-3(n+1)$ are divisible by $2^4$. A key observation is that the third term, $+8$, in square brackets is not. This means that the quantity in square brackets is divisible by $8$ but is not divisible by $16$. Let's take advantage by writing $(n+1)=16m$, $m$ a positive integer. Then $$[(n+1)^2-3(n+1)+8]=256m^2-48m+8=8(32m^2-6m+1).$$ Here the factor $32m^2-6m+1$ is an odd integer $\ge27$. But the integer $3\cdot2^{n-k+1}$ has no odd factors larger than $3$, so this contradicts $(*)$. Therefore $b\in\{0,1,2,3\}$.
  • If $b=0$ or $b=1$ then $n+1=3^\epsilon\cdot2^b<7$ making it obvious that a code of length $n$ cannot have minimum distance $7$. If $b=2$ then $n+1=4\cdot3^{\epsilon}$ is either $4$ or $12$. The former is similarly impossible. If $n+1=12$ then $(n+1)^2-3(n+1)+8=116=2^2\cdot29$ violating $(*)$. Therefore the only possibility is $b=3$, when either $n+1=2^3=8$ or $n+1=3\cdot2^3=24$.
  • It is possible that $n+1=8$ for the repetition code of length $7$ is perfect. Similarly, $n+1=24$ is possible, as the binary Golay code of length $23$ is a perfect code with minimum distance $7$.
Related Question