6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Sep 17, 2012 at 1:44
  • $\begingroup$ Sorry about the confusion Dilip. I added the definitions that are used with the property in question. $\endgroup$
    – josh
    Sep 17, 2012 at 2:01

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ In the Golay code, every row has an ever weight, thus $wt(c) \equiv 0 $ mod 2. $\endgroup$
    – josh
    Sep 19, 2012 at 1:03
  • $\begingroup$ @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". $\endgroup$ Sep 19, 2012 at 1:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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