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've been reading about Golay codes, and I found an interested property that I am having trouble showing. The property says:

If the $[24, 12, 8]$ binary Golay code $\mathcal{G}$ is punctured in any coordinate and the resulting code is extended in the same position, then the exact same code $\mathcal{G}$ is obtained.

Can anyone offer any suggestions? Thanks in advance!

EDIT

Puncturing and extending are defined as follows:

If $\mathcal{C}$ is an $[n,k,d]$ code over $\mathbb{F}_{q}$, then $\mathcal{C}$ is punctured by deleting the same coordinate $i$ in each codeword. If $G$ is a generator matrix for $\mathcal{C}$, then a generator matrix for the punctured code is obtained by $G$ by deleting column $i$ and omitting a zero or duplicate row that may occur.

The extended code $\mathcal{C}_{ext}$ is the code: $$ \mathcal{C}_{ext} = \{ x_1 x_2 \dots x_{n+1} \in \mathbb{F}_{q}^{n+1} : x_1x_2\dots x_n \in \mathcal{C} \mbox{ with } x_1 + x_2 + \dots + x_{n+1} = 0 \}.$$ The generator matrix for the extended code is obtained from $G$ by adding an extra column to $G$ so that the sum of the coordinates of each row is 0

share|improve this question
    
Common meanings of puncturing and extending mean deleting a parity check symbol and adding a parity check symbol respectively, though at least the first edition (though I believe not the second edition) of a well-known textbook uses different names for these operations. Also, extending very often, though not always, means adding an overall parity check. So, could you tell us what you (or whatever book or journal article you are reading) mean by puncturing? –  Dilip Sarwate Sep 17 '12 at 1:44
    
Sorry about the confusion Dilip. I added the definitions that are used with the property in question. –  josh Sep 17 '12 at 2:01

1 Answer 1

up vote 3 down vote accepted

No codeword in the Golay code $\mathcal C$ has Hamming weight $1$: in fact all the weights are even. Thus, no row of the generator matrix $\mathcal G$ can have a single $1$ in it, and puncturing the code by deleting the $i$-th coordinate does not produce any all-zeroes rows in $\mathcal G$ that might need to be discarded. The punctured code is thus a $[23, 12, 7]$ code $\mathcal C^*$.

Now, extend the punctured code $\mathcal C^*$by putting the overall parity check between the $(i-1)$-th and $i$-th coordinates instead of at the end as in your description of extension. Remember that the the $(i-1)$-th coordinate in $\mathcal C^*$ is the same as the $(i-1)$-th coordinate in $\mathcal C$ while the $i$-th coordinate in $\mathcal C^*$ is the $(1+1)$-th coordinate in $\mathcal C$ that got moved leftward by one position when the puncturing occurred.

An overall parity check bit is $0$ if the codeword being extended has even weight and is $1$ if the codeword being extended has odd weight.

(If you do not know this already, you can deduce it as follows. (i) After extension, each row of the new generator matrix is an even-weight codeword of the extended code, and so all the codewords of the extended code (being sums of rows of the generator matrix) have even weight, (ii) If a codeword in the original code had even weight, the extension bit must necessarily be a $0$ while if the codeword had odd weight the extension bit must necessarily be a $1$ to satisfy the condition that all codewords in the extended code have even weight.)

Now, suppose $c \in \mathcal C$ got punctured to $c^* \in \mathcal C^*$ by deletion of a $0$ bit. Then, $\text{wt}(c^*) = \text{wt}(c)\equiv 0 \mod 2$, and so the overall parity check being inserted will be a $0$. On the other hand, if a $1$ bit was deleted in the puncturing process, then $\text{wt}(c^*) = (\text{wt}(c) - 1)\equiv 1 \mod 2$ and so the overall parity check bit that will be inserted is a $1$. Thus, the insertion of an overall parity check bit to extend $\mathcal C^*$ simply puts back into each $c^*$ the bit that was deleted during the puncturing process to get the punctured codeword $c^*$.

Exercise: Figure out where in the above proof we used any specific property of Golay codes.

share|improve this answer
    
In the Golay code, every row has an ever weight, thus $wt(c) \equiv 0 $ mod 2. –  josh Sep 19 '12 at 1:03
    
@josh Yes indeed, but this property is hardly unique to the Golay code. Every binary code whose codewords all have even Hamming weight has a generator matrix with even-weight rows. In other words, the title of your question "A property of Golay codes" is a little misleading: it ought to be something like "A property of even-weight codes". –  Dilip Sarwate Sep 19 '12 at 1:16

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.