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.

I am studying a construction of the binary Golay code using the extended binary Golay code $\mathcal{G}$. It is well known that the extended Golay code is a $[24,2^{12},8]_2$-code and can be constructed from the generating matrix $$ {I} \choose {A} $$ where $I$ is the $12 \times 12$ identity matrix and $A$ is the matrix of anti-adjacency of the set of vertices of an icosahedron. I studied some usual results about the extended binary Golay code. For instance: $A$ is orthogonal, or $\forall \; x \in \mathcal{G}: w(x) \in \{0,8,12,16,24\}$ where $w(x)$ denotes the weight of $x$, ...

Now it is stated that it is possible to construct a perfect $[23,2^{12},7]_2$-code with the following construction: consider the extended Golay code $\mathcal{G}$, pick $i \in \{1, \ldots, 24\}$ and set $$\mathcal{G}_i := \{x_1 \ldots \hat{x}_i \ldots x_{24} \mid x_1 \ldots x_{24} \in \mathcal{G} \}$$ Then $\mathcal{G}_i$ is a perfect $[23,2^{12},7]_2$-code.

Okay, now checking the perfection is not a problem since it suffices to check the Hamming bound (if we assume that $\mathcal{G}_i$ is indeed a $[23,2^{12},7]_2$-code). However why isn't it possible to choose $i \in \{1, \ldots , 24\}$ in such a clever way that $\mathcal{G}_i$ has minimal distance 8 instead of 7? I know from all the informations on the internet about Golay code that it is not possible, however I would like to see a direct proof of that, i.e. that does not involves uniqueness of the Golay code for instance. If I rephrase my question, it becomes: if we select two words at distance $8$, we can choose $i \in \{1, \ldots, 24\}$ such that the $i^{th}$ letter differs and delete it in every word so that minimal distance becomes indeed 7. Why is it always the case?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

The reason why this doesn't work is the following. There are 759 words of weight 8 in the Golay code. Between them they cover all 24 bit positions (the choice of the index i) many times over. (Transitivity of the automorphism group implies that all the positions are covered equally often, so we can say more precisely that each position has a '1' in 253 words of weight 8 and a '0' in 506 words of weight 8). Therefore, no matter which position you drop, you will turn some of the weight 8 words into weight 7 words. As the all zero word is also there, the Hamming distance then cannot be $>7$ either.

To give a fully convincing solution I would need to exhibit a set of words of weight 8 that cover all the 24 positions. As I don't know the precise ordering of the bit positions in your construction, I cannot do that reliably. If you post the generator matrix fully, then we should be able to do this quickly.

share|improve this answer
    
I am convinced by the argument of transitivity. This is the kind of "cyclicity" argument I was looking for. Morevover I don't really want to write a $12 \times 24$ matrix at the moment ;) –  Thomas Connor Jun 13 '11 at 9:59
    
@Thomas: I quite understand! If this is convincing enough, then everything is ok. –  Jyrki Lahtonen Jun 13 '11 at 10:03

Here is the most simple argument I have finally found. Recall that the Hamming bound.

Theorem Let $C$ be a $[n,M,d]_q$-code. Then $q^n \geq M ~ \sum_{i=1}^t{{n}\choose{i}}(q-1)^i$ where $t$ is the biggest integer suh that $d\geq 2t+1$.

A $[23,2^{12},8]_2$-code would violate the Hamming bound, hence it cannot exist and the minimal distance has to diminish (by at most 1).

share|improve this answer

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.