# perfect binary e-error correcting code

let C be a perfect binary e-error correcting code of length n.

assume 0 is a symbol and that 0 vector is a codeword.show that P={1,2,...,n}

together with supports of codewords of weight 2e+1form an STS(e+1,2e+1,n)

-
I give up: what is an STS? –  rschwieb Apr 10 '13 at 21:30
@rschwieb Probably STS stands for Steiner triple system which is a Steiner system with parameters $(2,3,n)$. Except for the Golay code, all perfect binary $e$- correcting codes have $e=1$ so that $(2e,2e+1,n) = (2,3,n)$. The result in question is Theorem 17, Chapter 2, of MacWilliams and Sloane's Theory of Error-Correcting Codes. –  Dilip Sarwate Apr 10 '13 at 22:11
@DilipSarwate I'm aware of the classification of perfect linear codes, but the fact this person makes an assumption that the zero vector is a codeword seems to suggest he might not be talking about linear codes. Is it possible that what I've been thinking of as the classification of linear codes goes beyond linearity too?? –  rschwieb Apr 11 '13 at 1:22
@rschwieb: For the question to make sense, I think STS just means "Steiner System". As pointed out by Dilip Sarwate, the Golay code doesn't give you a Steiner triple system. –  azimut Apr 11 '13 at 16:39
@azimut I was able to read Dilip's comment, but thanks for confirming. –  rschwieb Apr 11 '13 at 16:43

Let $d = 2e + 1$ be the minimum distance of $C$. For all $v\in\{0,1\}^n$, we have $w_{\text{Ham}}(v) = \left|\operatorname{supp}(v)\right|$ and $d_{\text{Ham}}(v,v') = \left|\operatorname{supp}(v) \triangle \operatorname{supp}(v')\right|$, where $\triangle$ denotes the symmetric difference of sets. In the following, we identify a vector $v\in \{0,1\}$ with its support $\operatorname{supp}(v)\subseteq P$.
We are going to show that the set of codewords of weight $d$ form a Steiner system $S(e+1,d,n)$. Thus, we have to show that for any subset $T$ of $P = \{1,\ldots,n\}$ of size $\left|T\right| = e+1$, there is a unique codeword $K$ of size $\left|K\right| = d$ containing $T$.
1. There is at most one such codeword: If there were two distinct codewords $K_1$, $K_2$ of weight $d$ such that $T \subset K_1$, $T \subset K_2$, then the Hamming distance of $K_1$ and $K_2$ was $$\left| K_1\triangle K_2\right| = \left| K_1\setminus (K_1 \cap K_2)\right| + \left| K_2\setminus (K_1 \cap K_2)\right|\\\leq 2(d - (e+1)) = 2d - (2e + 2) = d-1,$$ contradicting the minimum distance of the code.
2. There is at least one such codeword: Since $C$ is perfect, there is a codeword $K$ such that the Hamming ball with center $K$ and radius $e$ contains $T$. By the triangular inequality, $\left|K\right|\leq \left| T\right| + e = 2e + 1 = d$. On the other hand, since $C$ contains the zero word and its minimum distance is $d$, $\left|K\right| \geq d$. So $\left|K\right| = d = 2e + 1$, and the distance of $T$ and $K$ is at most $e$. By $\left|T\right| = e+1$, this implies that the distance is exactly $e$ and $T\subset K$.