Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

thanks for your help...

share|improve this question
    
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
show 2 more comments

1 Answer

up vote 2 down vote accepted

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$.

share|improve this answer
    
i am a new member for this site azimut.i did not know how to vote how to accept the answers that i received.thanks for your useful teach. –  ötarcan Apr 12 '13 at 11:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.