Algebraic decoding of Golay(24,12)

A couple years ago, I implemented a Golay(24,12) decoder to be used in the GOMX-1 decoder in gr-satellites. The implementation can be seen here. I followed the algorithm in the book The Art of Error Correction Coding, Section 2.2.3, without taking much care to understand why the algorithm worked. Now I am doing some experiments with Golay(24,12) and Golay(23,12) codes, so I have needed to revisit that algorithm and understand it well to adapt it to my needs. Here I explain how this algebraic decoder works.

Recall that a Golay(24,12) is any 12-dimensional linear subspace of \(GF(2)^{24}\) such that the Hamming distances between its elements are at least 8. When used as a systematic code, a Golay(24,12) code is usually given in terms of its generator matrix\[G = \begin{pmatrix}I\\B\end{pmatrix},\]where \(I\) is the \(12 \times 12\) identity matrix and \(B\) is also \(12 \times 12\). The message \(x \in GF(2)^{12}\) is encoded as the codeword \(Gx\). Note that Golay codes and their generator matrix are not unique. Indeed, one can permute the rows and columns of \(B\) to obtain another systematic Golay code (however, this is the only freedom one has to construct different Golay codes).

Given a Golay code with generator matrix \(G\) as above, a parity check matrix can be easily constructed as\[H = \begin{pmatrix}B & I\end{pmatrix},\] since \(HG = 0\) and \(H\) has maximum rank. Note that this property is a general property of all systematic linear codes over a field of characteristic 2. We haven’t used any of the properties of Golay codes yet.

For certain Golay codes, the matrix \(B\) is symmetric. The algorithm given in The Art of Error Correction Coding makes use of this fact. For the codes I’m using, \(B\) is not symmetric, so I have needed to adapt the algorithm.

Let \(r \in GF(2)^{24}\) be the received word, \(\varepsilon_j\) the vector having a one in the \(j\)-th position and zeros elsewhere, and \(w(\cdot)\) denote the Hamming weight. The decoding procedure (for \(B\) not necessarily symmetric) goes as follows:

1. Compute the syndrome \(s = Hr\)
2. If \(w(s) \leq 3\), put \(e = (0, s)\) and go to step 8
3. If \(w(s + B\varepsilon_j) \leq 2\) for some \(1 \leq j \leq 12\), put \(e = (\varepsilon_j, s + B\varepsilon_j)\) and go to step 8
4. Compute \(q = B^Ts\)
5. If \(w(q) \leq 3\), put \(e = (q, 0)\) and go to step 8
6. If \(w(q + B^T\varepsilon_j) \leq 2\) for some \(1 \leq j \leq 12\), put \(e = (q + B^T \varepsilon_j, \varepsilon_j)\) and go to step 8
7. \(r\) is uncorrectable
8. The corrected codeword is \(c = r + e\)

To show that this algorithm works, we need the following lemma, which will be proved below.

Lemma 1. The matrix \(B\) is invertible and \(B^{-1} = B^T\).

Let us now prove that the algebraic decoding algorithm given above works. First we show that for all possible values of \(e\) given by the algorithm, we have \(Hc = 0\). To this end, we write \(r = (r_1,r_2)\) and \(e = (e_1,e_2)\), where \(r_1,r_2,e_1,e_2 \in GF(2)^{12}\). Then\[Hc = Br_1 + Be_1 + r_2 + e_2.\] Also,\[s = Br_1 + r_2.\] If \(e\) is as in step 2, we have \(e_1 = 0\), \(e_2 = s\), so we see that \(Hc = 0\). If \(e\) is as in step 3, we have \(e_1 = \varepsilon_j\) and \(e_2 = Br_1 + r_2 + B\varepsilon_j\), so we also have \(Hc = 0\). By Lemma 1, we have\[q = B^TBr_1 + B^Tr_2 = r_1 + B^Tr_2.\]If \(e\) is as in step 5, then \(e_1 = r_1 + B^Tr_2\) and \(e_2 = 0\). Applying Lemma 1 again, we see that \(Hc = 0\). Finally, if \(e\) is as in step 6, then \(e_1 = r_1 + B^T r_2 + B^T \varepsilon_j\) and \(e_2 = \varepsilon_j\), and using Lemma 1 we also see that \(Hc = 0\).

This means that if the decoder succeeds (meaning that it doesn’t reach step 7), then it produces a valid codeword \(c\). Also, note that \(e\) is always chosen so that \(w(e) \leq 3\). Since the minimum Hamming distance between different codewords is 8, this means that when the decoder succeeds, it produces the nearest valid codeword \(c\) to the received word \(r\). It remains to show that if the received codeword has at most 3 errors, then the decoder succeeds.

To show this, we assume that \(r = \widetilde{c} + \widetilde{e}\), where \(H\widetilde{c} = 0\) and \(w(\widetilde{e}) \leq 3\). We must show that the algorithm succeeds. We write \(\widetilde{e} = (\widetilde{e}_1, \widetilde{e}_2)\), with \(\widetilde{e}_1, \widetilde{e}_2 \in GF(2)^{12}\). Note that\[s = B\widetilde{e}_1 + \widetilde{e}_2,\]and\[q = \widetilde{e}_1 + B^T\widetilde{e}_2.\]Since \(w(\widetilde{e}) \leq 3\), then either \(\widetilde{e}_1\) or \(\widetilde{e}_2\) must be zero or equal to some \(\varepsilon_j\) for \(1\leq j \leq 12\). If \(\widetilde{e}_1 = 0\), then \(s = \widetilde{e}_2\), so \(w(s) \leq 3\) and step 2 of the algorithm succeeds. If \(\widetilde{e}_1 = \varepsilon_j\), then \(s + B\varepsilon_j = \widetilde{e}_2\), so \(w(s + B\varepsilon_j) \leq 2\) and step 3 succeeds. If \(\widetilde{e}_2 = 0\), then \(q = \widetilde{e}_1\), so \(w(q) \leq 3\) and step 5 succeeds. Finally, if \(\widetilde{e}_2 = \varepsilon_j\), then \(q + B^T \varepsilon_j = \widetilde{e}_2\), so \(w(q + B^T \varepsilon_j) \leq 2\) and step 6 succeeds. This finishes the proof.

It also follows from this proof that the algorithm must fail if \(r\) has exactly 4 errors, since when the algorithm succeeds, it always produces a valid codeword whose Hamming distance to \(r\) is at most 3, which is impossible in this case. Therefore, the algorithm is able to correct up to 3 errors and detect up to 4 errors.

Now we turn to the proof of the lemma.

Proof of Lemma 1: Since \(B\) is a square matrix, it is enough to prove that \(B^T B = I\), which amounts to showing that the product of any two columns of \(B\) is one if the columns are the same and zero if the columns are different (by product here we mean the scalar product of two column vectors). This is equivalent to showing that the product of any two columns of \(G\) is zero. It is known that the number of ones that any two codewords in a Golay code have in common is even. Therefore, the product of any two codewords in a Golay code is zero, so this is also true for the columns of the generator matrix \(G\).

The algorithm given above works well for a Golay(24,12) code. However it cannot be easily adapted to decode a Golay(23,12) code. The problem is that, for these codes, the matrix \(B\) is \(11 \times 12\), so \(B^T B\) is not invertible (however, \(B B^T = I_{11\times 11}\)). Since I also need a decoder for a Golay(23,12) code, I will have to think if there is some way to adapt this algorithm.