Projection Decoding of Some Binary Optimal Linear Codes of Lengths 36 and 40

Abstract

Practically good error-correcting codes should have good parameters and efficient decoding algorithms. Some algebraically defined good codes, such as cyclic codes, Reed–Solomon codes, and Reed–Muller codes, have nice decoding algorithms. However, many optimal linear codes do not have an efficient decoding algorithm except for the general syndrome decoding which requires a lot of memory. Therefore, a natural question to ask is which optimal linear codes have an efficient decoding. We show that two binary optimal $[36,19,8]$ linear codes and two binary optimal $[40,22,8]$ codes have an efficient decoding algorithm. There was no known efficient decoding algorithm for the binary optimal $[36,19,8]$ and $[40,22,8]$ codes. We project them onto the much shorter length linear $[9,5,4]$ and $[10,6,4]$ codes over $GF\left(4\right)$, respectively. This decoding algorithm, called projection decoding, can correct errors of weight up to 3. These $[36,19,8]$ and $[40,22,8]$ codes respectively have more codewords than any optimal self-dual $[36,18,8]$ and $[40,20,8]$ codes for given length and minimum weight, implying that these codes are more practical.

1. Introduction

Coding theory or the theory of error-correcting codes requires a lot of mathematical concepts but has wide applications in data storage, satellite communication, smart phone, and High Definition TV. The well known classes of (linear) codes include Reed-Solomon codes, Reed-Muller codes, turbo codes, LDPC codes, Polar codes, network codes, quantum codes, and DNA codes. One of the most important reasons why these codes are useful is that they have fast and efficient decoding algorithms.

A linear $[n,k]$ code C over $GF\left(q\right)$ or ${\mathbb{F}}_q$ is a k-dimensional subspace of ${\mathbb{F}}_q^n$. The dual of C is $C^{\perp }=\{x\in {\mathbb{F}}_q^n|x·c=0 \mathrm{for} \mathrm{any} c\in C\}$, where the dot product is either a usual inner product or a Hermitian inner product. A linear code C is called self-dual if $C=C^{\perp }$. If $q=2$, then C is called binary. A binary self-dual code is called doubly-even if all codewordshave weight $\equiv 0(mod4)$ and singly-even if some codewords have a weight $\equiv 2(mod4)$. If $q=4$, let $GF\left(4\right)=\{0,1,\omega ,\overline{\omega }\}$, where $\overline{\omega }={\omega }^2=\omega +1$. It is more natural to consider the Hermitian inner product $〈,〉$ on $GF{\left(4\right)}^n$: for $x=(x_1,x_2,\dots ,x_n)$ and $y=(y_1,y_2,\dots ,y_n)$ in $GF{\left(4\right)}^n$, $〈x,y〉={\sum }_{i=1}^n{x}_i\overline{y_i}$, where $\overline{a}=a^2$.

Researchers have tried to find an efficient decoding algorithms for some optimal linear codes. Some well known methods to decode linear codes are permutation decoding [1,2,3] for codes with large groups of automorphisms, decoding based on error locator polynomials in cyclic or AG codes [3], message passing algorithm for LDPC codes [4,5], and Successive Cancellation Decoding for polar codes [6].

Projection decoding was used for self-dual codes. For example, Pless [7] showed an efficient decoding of the $[24,12,8]$ extended binary self-dual Golay code by projecting it onto the $[6,3,4]$ hexacode over $GF\left(4\right)$. Later, Gaborit, Kim, and Pless [8,9] showed that a similar projection can be done for some singly even and doubly-even self-dual binary $[32,16,8]$ codes including the binary Reed Muller code. Recently, Kim and Lee [10] gave two algorithms for the projection decoding of a binary extremal self-dual code of length 40. The idea was to use the projection of the said code onto a Hermitian self-dual code over $GF\left(4\right)$. One of the two algorithms called syndrome decoding uses the syndrome decoding of the shorter code over $GF\left(4\right)$. Most examples for the projection decoding were extremal self-dual codes. Therefore it is natural to ask whether such a projection decoding can be done for a non-self-dual code which has larger dimensions than a self-dual code with the same length and minimum distance. In this paper, we show that this is possible.

The purpose of this paper is to show how to decode efficiently a binary optimal $[36,19,8]$ linear code and a binary optimal $[40,22,8]$ code by projecting them onto the much shorter length linear $[9,5,4]$ and $[10,6,4]$ codes over $GF\left(4\right)$, respectively. This decoding algorithm, which we will call projection decoding can correct errors of weight up to $\lfloor \frac{(8-1)}{2}\rfloor =3$. It can be seen that the decoding algorithm presented in this paper is a generalization of the syndrome projection decoding in [10] since this algorithm can be used to decode any linear code with a projection into an additive or a linear code over $GF\left(4\right)$ for errors of weight at most 3. Our decoding is the first time to decode those two optimal $[36,19,8]$ and $[40,22,8]$ codes, whose parameters are better than any optimal self-dual $[36,18,8]$ and $[40,20,8]$ codes.

This paper is organized as follows. In Section 2, we introduce a way to project a binary code of length $4n$ into an additive code of length n over $GF\left(4\right)$. We also mention some properties of this projection as given in [11,12]. In Section 3, we show explicitly how to construct $[36,19,8]$ and $[40,22,8]$ binary optimal codes with projections onto additive codes over $GF\left(4\right)$. Using this projection, we give a handy decoding algorithm to decode the said binary optimal codes in Section 4. This decoding algorithm exploits the properties of codes with projection onto an additive code over $GF\left(4\right)$ to locate the errors in the noisy codewords, assuming not more than 3 errors occurred. This algorithm has low complexity and can be done with hand. In Section 5, we conclude by showing working examples of how the decoding is carried out.

2. Projection of Binary Linear Codes

Let $v\in GF{\left(2\right)}^{4m}$. We associate to v a rectangular array $\mathbf{v}$ of zeros and ones. If we label the rows of the array with the elements of $GF\left(4\right)$, then the inner product of a column of the array with the row labels is an element of $GF\left(4\right)$. Thus, we obtain a corresponding element of $GF{\left(4\right)}^m$, which we call the projection of v, denoted Proj$\left(\mathbf{v}\right)$. We show this by the following example. Let $v=\left(100001000010000101101110010101111111\right)\in GF{\left(2\right)}^{36}$. Then we write v column-wisely as follows.

$$\mathbf{v}=\begin{array}{cccccccccc}& 1& 2& 3& 4& 5& 6& 7& 8& 9\\ 0& 1& 0& 0& 0& 0& 1& 0& 0& 1\\ 1& 0& 1& 0& 0& 1& 1& 1& 1& 1\\ \omega & 0& 0& 1& 0& 1& 1& 0& 1& 1\\ \overline{\omega }& 0& 0& 0& 1& 0& 0& 1& 1& 1\\ & \mathbf{0}& \mathbf{1}& \omega & \omega & \overline{\omega }& \overline{\omega }& \omega & \mathbf{0}& \mathbf{0}\end{array}$$

We define the parity of the column to be even (or odd) if an even (or odd) number of ones exists in the column, and the parity of the first row is defined similarly.

We call $C_4\subset GF{\left(4\right)}^n$ an additive code of length n over $GF\left(4\right)$ if it is closed under addition. Therefore, a linear code over $GF\left(4\right)$ is automatically additive, but not the converse.

Definition 1.

Let S be a subset of $GF{\left(2\right)}^{4m}$ and $C_4$ an additive code over $GF\left(4\right)$ of length m. Then S is said to have a projection O onto $C_4$ if for any $v\in S$,

(i) 

Proj$\left(\mathbf{v}\right)\in C_4$.

(ii) 

the columns of $\mathbf{v}$ are of the same parity, i.e., the columns are either all even or all odd.

(iii) 

the parity of the first row of $\mathbf{v}$ is the same as the parity of the columns.

The main advantage of this projection is that we can decode the long binary code by decoding its projection, thus generally decreasing the complexity of the decoding process. Several authors exhibited this fact [7,8,10].

Another similar projection is defined in [12], called projection E.

Definition 2.

Using the same notation as in Definition 1, S is said to have a projection E onto $C_4$ if conditions $\left(i\right)$ and $\left(ii\right)$ are satisfied together with the additional condition:

(iii) 

the parity of the first row of $\mathbf{v}$ is always even.

Let $C_4$ be an additive code of length m over $GF\left(4\right)$. Consider the map $\varphi :GF\left(4\right)\to GF{\left(2\right)}^4$ such that $\varphi \left(0\right)=0000$, $\varphi \left(1\right)=0011$, $\varphi \left(\omega \right)=0101$, and $\varphi \left(\overline{\omega }\right)=0110$. Define

$$\varphi \left(C_4\right)=\{(\varphi \left(c_1\right),\varphi \left(c_2\right),\dots ,\varphi \left(c_m\right)):(c_1,c_2,\dots ,c_m)\in C_4\}.$$

Let d be the code consisting of all even sums of weight 4 vectors whose ones appear in the same column in the projection, together with one additional vector $d_1=(10001000\dots 1000)$ if m is odd and $d_2=(10001000\dots 0111)$ if m is even. In [12], the following constructions were given:

• Construction O: ${\rho }_O\left(C_4\right)=\varphi \left(C_4\right)+d$,
• Construction E: ${\rho }_E\left(C_4\right)=\varphi \left(C_4\right)+d^{\prime }$,

where $d^{\prime }$ is the code consisting of $d_1$ if m is even and $d_2$ if m is odd.

The following result also was also given in [12].

Theorem 1.

Let $C_4$ be an additive $(m,2^r)$ code over $GF\left(4\right)$. Then

1. 

${\rho }_O\left(C_4\right)$ and ${\rho }_E\left(C_4\right)$ are binary linear $[4m,m+r]$ codes with projection O and E, respectively, onto $C_4$.

2. 

any binary linear code with projection O or E onto $C_4$ can be constructed in this way.

3. Construction of Binary Optimal $[36,19,8]$ and $[40,22,8]$ Codes

In this section, we apply the constructions given in the previous section to construct binary optimal codes of lengths 36 and 40. We were able to obtain two inequivalent codes for each length.

Let $C_4^9$ be a $(9,2^{10})$ additive code over $GF\left(4\right)$ with the following generator matrix

$$G\left(C_4^9\right)=\left[\begin{array}{ccccccccc}1& 0& 0& 0& 0& \overline{\omega }& 1& 1& 1\\ \omega & 0& 0& 0& 0& 1& \omega & \omega & \omega \\ 0& 1& 0& 0& 0& 1& \omega & \overline{\omega }& 0\\ 0& \omega & 0& 0& 0& \omega & \overline{\omega }& 1& 0\\ 0& 0& 1& 0& 0& 0& 1& \omega & \overline{\omega }\\ 0& 0& \omega & 0& 0& 0& \omega & \overline{\omega }& 1\\ 0& 0& 0& 1& 0& \overline{\omega }& \overline{\omega }& 0& 1\\ 0& 0& 0& \omega & 0& 1& 1& 0& \omega \\ 0& 0& 0& 0& 1& 1& \omega & 1& 1\\ 0& 0& 0& 0& \omega & \omega & \overline{\omega }& \omega & \omega \end{array}\right].$$

In fact the rows consisting of the odd indexed rows of $G\left(C_4^9\right)$ form a $[9,5,4]$-linear code over $GF\left(4\right)$ which can be found in MAGMA with the name of $BKLC\left(GF\right(4),9,5)$. The code $C_4^9$ has weight distribution $A_4=51,A_5=135,A_6=210,A_7=318,A_8=234,A_9=75$.

Let $C_4^{10}$ be the $(10,2^{12})$ additive code over $GF\left(4\right)$ generated by the following matrix

$$G\left(C_4^{10}\right)=\left[\begin{array}{cccccccccc}1& 0& 0& 0& 0& 0& \omega & 0& \omega & \overline{\omega }\\ \omega & 0& 0& 0& 0& 0& \overline{\omega }& 0& \overline{\omega }& 1\\ 0& 1& 0& 0& 0& 0& \overline{\omega }& 1& 1& 1\\ 0& w& 0& 0& 0& 0& 1& \omega & \omega & \omega \\ 0& 0& 1& 0& 0& 0& 1& \omega & \overline{\omega }& 0\\ 0& 0& \omega & 0& 0& 0& \omega & \overline{\omega }& 1& 0\\ 0& 0& 0& 1& 0& 0& 0& 1& \omega & \overline{\omega }\\ 0& 0& 0& \omega & 0& 0& 0& \omega & \overline{\omega }& 1\\ 0& 0& 0& 0& 1& 0& \overline{\omega }& \overline{\omega }& 0& 1\\ 0& 0& 0& 0& \omega & 0& 1& 1& 0& \omega \\ 0& 0& 0& 0& 0& 1& 1& \omega & 1& 1\\ 0& 0& 0& 0& 0& \omega & \omega & \overline{\omega }& \omega & \omega \end{array}\right].$$

The minimum distance of both of these codes is 4.

The rows consisting of the odd indexed rows of $G\left(C_4^{10}\right)$ form a $[10,6,4]$-linear code over $GF\left(4\right)$ which can be found in (Computational Algebra System) MAGMA with the name of (Best Known Linear Code) $BKLC\left(GF\right(4),10,6)$. The code $C_4^9$ has weight distribution $A_4=87,A_5=258,$$A_6=555,A_7=1020,A_8=1200,A_9=738,A_{10}=237$.

Denote by ${\mathcal{C}}_O^{36}$ and ${\mathcal{C}}_O^{40}$ the binary linear codes obtained from the additive codes $C_4^9$ and $C_4^{10}$, respectively, over $GF\left(4\right)$ by construction O. That is, ${\mathcal{C}}_O^{36}={\rho }_O\left(C_4^9\right)$ and ${\mathcal{C}}_O^{40}={\rho }_O\left(C_4^{10}\right)$. Their generator matrices are given below. These two codes constructed are inequivalent and both have projection O on to $C_4^9$ and $C_4^{10}$, respectively.

$$G\left({\mathcal{C}}_O^{36}\right)=\left[\begin{array}{c}100000010001000100010010010001110010\\ 010000010001000100010100011101001110\\ 001000010001000100010001000100101000\\ 000100010001000100010111001000011011\\ 000010010000000000000110001101011111\\ 000001010000000000000101011000110000\\ 000000110000000000000011010101100000\\ 000000001001000000000000011000111010\\ 000000000101000000000000010101100011\\ 000000000011000000000000001101010110\\ 000000000000100100000101010100001001\\ 000000000000010100000011001100000101\\ 000000000000001100000110011000000011\\ 000000000000000010010110001101101001\\ 000000000000000001010101011001010101\\ 000000000000000000110011010100110011\\ 000000000000000000001111000000001111\\ 000000000000000000000000111100001111\\ 000000000000000000000000000011111111\end{array}\right],$$

$$G\left({\mathcal{C}}_O^{40}\right)=\left[\begin{array}{c}1000000100010001000100010111001000010100\\ 0100000100010001000100010010001001001101\\ 0010000100010001000100010001001001111000\\ 0001000100010001000100010100001000101110\\ 0000100100000000000000000101011001101001\\ 0000010100000000000000000011010101010101\\ 0000001100000000000000000110001100110011\\ 0000000010010000000000000110001101011111\\ 0000000001010000000000000101011000110000\\ 0000000000110000000000000011010101100000\\ 0000000000001001000000000000011000111010\\ 0000000000000101000000000000010101100011\\ 0000000000000011000000000000001101010110\\ 0000000000000000100100000101010100001001\\ 0000000000000000010100000011001100000101\\ 0000000000000000001100000110011000000011\\ 0000000000000000000010010110001101101001\\ 0000000000000000000001010101011001010101\\ 0000000000000000000000110011010100110011\\ 0000000000000000000000001111000000001111\\ 0000000000000000000000000000111100001111\\ 0000000000000000000000000000000011111111\end{array}\right].$$

Similarly, we apply construction E on the codes $C_4^9$ and $C_4^{10}$. We obtain two inequivalent codes ${\mathcal{C}}_E^{36}={\rho }_E\left(C_4^9\right)$ and ${\mathcal{C}}_E^{40}={\rho }_E\left(C_4^{10}\right)$ with projection E on to $C_4^9$ and $C_4^{10}$, respectively. Their generator matrices are as follows.

$$G\left({\mathcal{C}}_E^{36}\right)=\left[\begin{array}{c}100000010001000100010010010001111101\\ 010000010001000100010100011101000001\\ 001000010001000100010001000100100111\\ 000100010001000100010111001000010100\\ 000010010000000000000110001101011111\\ 000001010000000000000101011000110000\\ 000000110000000000000011010101100000\\ 000000001001000000000000011000111010\\ 000000000101000000000000010101100011\\ 000000000011000000000000001101010110\\ 000000000000100100000101010100001001\\ 000000000000010100000011001100000101\\ 000000000000001100000110011000000011\\ 000000000000000010010110001101101001\\ 000000000000000001010101011001010101\\ 000000000000000000110011010100110011\\ 000000000000000000001111000000001111\\ 000000000000000000000000111100001111\\ 000000000000000000000000000011111111\end{array}\right],$$

$$G\left({\mathcal{C}}_E^{40}\right)=\left[\begin{array}{c}1000000100010001000100010111001000011011\\ 0100000100010001000100010010001001000010\\ 0010000100010001000100010001001001110111\\ 0001000100010001000100010100001000100001\\ 0000100100000000000000000101011001101001\\ 0000010100000000000000000011010101010101\\ 0000001100000000000000000110001100110011\\ 0000000010010000000000000110001101011111\\ 0000000001010000000000000101011000110000\\ 0000000000110000000000000011010101100000\\ 0000000000001001000000000000011000111010\\ 0000000000000101000000000000010101100011\\ 0000000000000011000000000000001101010110\\ 0000000000000000100100000101010100001001\\ 0000000000000000010100000011001100000101\\ 0000000000000000001100000110011000000011\\ 0000000000000000000010010110001101101001\\ 0000000000000000000001010101011001010101\\ 0000000000000000000000110011010100110011\\ 0000000000000000000000001111000000001111\\ 0000000000000000000000000000111100001111\\ 0000000000000000000000000000000011111111\end{array}\right].$$

Proposition 1.

The codes ${\mathcal{C}}_O^{36}$ and ${\mathcal{C}}_E^{36}$ are inequivalent binary optimal $[36,19,8]$ linear codes.

Proof. 

Since $C_4^9$ is an additive $(9,2^{10})$ code over $GF\left(4\right)$, it follows from Theorem 1 that ${\mathcal{C}}_O^{36}={\rho }_O\left(C_4^9\right)$ and ${\mathcal{C}}_E^{36}={\rho }_E\left(C_4^9\right)$ are binary $[36,19]$ linear codes. It remains to show that the minimum distance is 8. It is known that codes of these parameters are optimal [13].

Please note that any codeword $\mathbf{c}\in {\mathcal{C}}_O^{36}$ can be written as $\mathbf{c}=\mathbf{a}+\mathbf{b}+\mathbf{d}$ where $\mathbf{a}\in \varphi \left(C_4^9\right)$, $\mathbf{b}$ is an even sum of weight 4 vectors whose ones appear in the same column in the projection and $\mathbf{d}$ is equal to either $d_1=(1000\dots 1000)$ or the zero vector. Since the minimum distance of $C_4^9$ is 4 and thus $\varphi \left(C_4^9\right)$ is of minimum distance 8, $wt\left(\mathbf{a}\right)\ge 8$. By the definition of $\mathbf{b}$, it is clear that $wt\left(\mathbf{b}\right)\le 8$. Thus, the minimum distance of ${\mathcal{C}}_O^{36}$ is at most 8. Now partition $\mathbf{c}$ into blocks of length 4 and call the ith block ${\mathbf{c}}_i$ (which corresponds to the ith column in the projection). For each $i=1,\dots ,9$, write ${\mathbf{c}}_i={\mathbf{a}}_i+{\mathbf{b}}_i+{\mathbf{c}}_i$. From the construction, it can be seen that ${\mathbf{c}}_i=0000$ if and only if ${\mathbf{a}}_i={\mathbf{b}}_i={\mathbf{d}}_i=0000$. If $\mathbf{d}$ is the zero vector, i.e., ${\mathbf{d}}_i=0000$ for all i, then $wt({\mathbf{a}}_i+{\mathbf{c}}_i)\in \{2,4\}$. Thus, $wt\left(\mathbf{c}\right)=wt({\mathbf{a}}_i+{\mathbf{b}}_i)\ge 8$. Suppose ${\mathbf{d}}_i=1000$ for all i. If ${\mathbf{b}}_i=0000$, then $wt\left({\mathbf{c}}_i\right)=wt({\mathbf{a}}_i+{\mathbf{d}}_i)=3$. If ${\mathbf{b}}_i=1111$, then $wt({\mathbf{a}}_i+{\mathbf{b}}_i+{\mathbf{d}}_i)\in \{1,3\}$. Since at least 4 blocks ${\mathbf{c}}_i$ are nonzero, we conclude that $wt\left(\mathbf{c}\right)\ge 8$. Hence the minimum distance of this code is 8.

The case of ${\mathcal{C}}_E^{36}$ is proved similarly.

Finally, the codes ${\mathcal{C}}_O^{36}$ and ${\mathcal{C}}_E^{36}$ have different weight distributions given in

Table 1. Weight distribution of $C_O^{36}$.

$A_0=1$	$A_8=444$	$A_9=496$	$A_{10}=2160$	$A_{11}=4752$
$A_{12}=8760$	$A_{13}=$ 17,856	$A_{14}=$ 28,992	$A_{15}=$ 44,352	$A_{16}=$ 54,318
$A_{17}=$ 62,496	$A_{18}=$ 72,864	$A_{19}=$ 66,528	$A_{20}=$ 54,192	$A_{21}=$ 41,664
$A_{22}=$ 28,992	$A_{23}=$ 19,008	$A_{24}=8844$	$A_{25}=4464$	$A_{26}=2160$
$A_{27}=528$	$A_{28}=408$	$A_{32}=9$

and

Table 2. Weight distribution of $C_E^{36}$.

$A_0=1$	$A_8=444$	$A_9=528$	$A_{10}=2160$	$A_{11}=4464$
$A_{12}=8760$	$A_{13}=$ 19,008	$A_{14}=$ 28,992	$A_{15}=$ 41,664	$A_{16}=$ 54,318
$A_{17}=$ 66,528	$A_{18}=$ 72,864	$A_{19}=$ 62,496	$A_{20}=$ 54,192	$A_{21}=$ 44,352
$A_{22}=$ 28,992	$A_{23}=$ 17,856	$A_{24}=8844$	$A_{25}=4752$	$A_{26}=2160$
$A_{27}=496$	$A_{28}=408$	$A_{32}=9$

which was computed by MAGMA. Therefore they are inequivalent. Furthermore, we checked by MAGMA that these two codes are not equivalent to the currently known optimal $[36,19,8]$ code denoted by $BKLC\left(GF\right(2),36,19)$ in the MAGMA database because $BKLC\left(GF\right(2),36,19)$ has $A_8=1033$. Please note that the codes ${\mathcal{C}}_O^{36}$ and ${\mathcal{C}}_E^{36}$ have the automorphism groups of order 6, while $BKLC\left(GF\right(2),36,19)$ has a trivial automorphism. □

For length 40, we have a similar result as in Proposition 2. We display the weight distributions of $C_O^{40}$ and $C_E^{40}$ in

Table 3. Weight distribution of $C_O^{40}$.

$A_0=1$	$A_8=741$	$A_{10}=6144$	$A_{12}=$ 42,736	$A_{14}=$ 176,640
$A_{16}=$ 484,890	$A_{18}=$ 849,408	$A_{20}=$ 1,073,184	$A_{22}=$ 849,408	$A_{24}=$ 484,890
$A_{26}=$ 176,640	$A_{28}=$ 42,736	$A_{30}=6144$	$A_{32}=741$	$A_{40}=1$

and

Table 4. Weight distribution of $C_E^{40}$.

$A_0=1$	$A_8=741$	$A_{10}=6208$	$A_{12}=$ 42,096	$A_{14}=$ 179,520
$A_{16}=$ 477,210	$A_{18}=$ 862,848	$A_{20}=$ 1,057,056	$A_{22}=$ 862,848	$A_{24}=$ 477,210
$A_{26}=$ 179,520	$A_{28}=$ 42,096	$A_{30}=6208$	$A_{32}=741$	$A_{40}=1$

. Furthermore, we checked by MAGMA that these two codes are not equivalent to the currently known optimal $[40,22,8]$ code denoted by $BKLC\left(GF\right(2),40,22)$ in the MAGMA database because $BKLC\left(GF\right(2),40,22)$ has $A_8=1412$.

Proposition 2.

The codes ${\mathcal{C}}_O^{40}$ and ${\mathcal{C}}_E^{40}$ are inequivalent binary optimal $[40,22,8]$ linear codes.

4. Projection Decoding

Let $v\in GF{\left(2\right)}^{4m}$ and $\mathbf{v}$ its associated array, defined in Section 2. From this, we can partition the elements of $GF{\left(2\right)}^4$ with respect to its inner product with the row labels, as follows:

From Definitions 1 and 2, we know that if $v\in \mathcal{C}$, where $\mathcal{C}$ is a code with projection O on to $C_4$, then the columns of $\mathbf{v}$, as well as the first row have the same parity. Before we give the decoding algorithm, we first take note of the following observations regarding the error positions in the array $\mathbf{v}$.

Remark 1. 

1. 

An error on the first row of $\mathbf{v}$ preserves Proj$\left(\mathbf{v}\right)$.

2. 

An error on the coordinate that is not in the first row definitely changes Proj$\left(\mathbf{v}\right)$.

3. 

Two errors in the same column definitely changes Proj$\left(\mathbf{v}\right)$.

4. 

Three errors in the same column preserves Proj$\left(\mathbf{v}\right)$ if and only if the first entry is not changed.

We now present a simple decoding algorithm, which we will call the projection decoding, that can be used for any binary linear code with projection O or projection E onto some additive code $C_4$ over $GF\left(4\right)$. This decoding algorithm can correct errors of weight up to three. The idea is to use syndrome decoding in $C_4$, which has shorter length to locate errors in the binary codeword. The decoding is then completed by changing the columns in the array corresponding to the corrected entry in the projection, by using

Table 5. Projection of $GF{\left(2\right)}^4$ onto $GF\left(4\right)$.

$0\leftarrow \begin{array}{c}0\\ 0\\ 0\\ 0\end{array},\begin{array}{c}1\\ 1\\ 1\\ 1\end{array},\begin{array}{c}1\\ 0\\ 0\\ 0\end{array},\begin{array}{c}0\\ 1\\ 1\\ 1\end{array}$	$1\leftarrow \begin{array}{c}1\\ 1\\ 0\\ 0\end{array},\begin{array}{c}0\\ 0\\ 1\\ 1\end{array},\begin{array}{c}0\\ 1\\ 0\\ 0\end{array},\begin{array}{c}1\\ 0\\ 1\\ 1\end{array}$
$\omega \leftarrow \begin{array}{c}1\\ 0\\ 1\\ 0\end{array},\begin{array}{c}0\\ 1\\ 0\\ 1\end{array},\begin{array}{c}0\\ 0\\ 1\\ 0\end{array},\begin{array}{c}1\\ 1\\ 0\\ 1\end{array}$	$\overline{\omega }\leftarrow \begin{array}{c}1\\ 0\\ 0\\ 1\end{array},\begin{array}{c}0\\ 1\\ 1\\ 0\end{array},\begin{array}{c}0\\ 0\\ 0\\ 1\end{array},\begin{array}{c}1\\ 1\\ 1\\ 0\end{array}$

.

Let $\mathcal{C}$ be a binary linear code of length $4n$ with projection O or projection E onto $C_4$, an additive code over $GF\left(4\right)$. Let y be the received vector and assume that y is a noisy codeword of $\mathcal{C}$ with at most 3 errors. Let $\mathbf{y}$ be the associated array and $\overline{\mathbf{y}}=\mathrm{Proj}\left(\mathbf{y}\right)$. Denote by ${\mathbf{y}}_i$ the ith column of $\mathbf{y}$ and by ${\overline{\mathbf{y}}}_i$ the ith entry of $\overline{\mathbf{y}}$. Let H be the parity-check matrix of $C_4$ and denote the ith column of H by $H_i$. The projection decoding of $\mathcal{C}$ is carried out as follows.

Projection decoding algorithm

• Check the parity of the columns and the first row of $\mathbf{y}$.
• Let $y^o$, $y^e$ be the number of columns of $\mathbf{y}$ with odd or even parity, resp., and let $p=min(y^o,y^e)$.
• Depending on p, perform the following:

  (a)

  If $p=0$, compute the syndrome $\mathbf{s}=\overline{\mathbf{y}}{H}^T$.

  i.

  If $\mathbf{s}=\mathbf{0}$, then we say that no error occurred.

  ii.

  If $\mathbf{s}\ne \mathbf{0}$, the syndrome is a scalar multiple of one of the columns of H, say $\mathbf{s}=e_i{H}_i$ for some $e_i\in GF\left(4\right)$. Hence, the two errors occurred on the ith column of $\mathbf{y}$. Replace the ith coordinate of $\overline{\mathbf{y}}$ by $\overline{{\mathbf{y}}_i}+e_i\in GF\left(4\right)$ and replace the ith column of $\mathbf{y}$ with the vector corresponding to $\overline{{\mathbf{y}}_i}+e_i$ (see Table 5) such that the parity conditions are satisfied.

  (b)

  If $p=1$, let ${\mathbf{y}}_i$ be the column with the different parity. Compute the syndrome $\mathbf{s}=\overline{\mathbf{y}}{H}^T$.

  i.

  If $\mathbf{s}=\mathbf{0}$, check the parity of the first row.

  • If the parity of the first row is the same as the parity of ${\mathbf{y}}_{\mathbf{i}}$, then one error occurred on the first entry of ${\mathbf{y}}_i$. Change this entry to decode y.
  • If the parity of the first row is different from the parity of ${\mathbf{y}}_{\mathbf{i}}$, then three errors occurred on the 2nd to 4th entries of ${\mathbf{y}}_{\mathbf{i}}$. Change these entries to decode y.

  ii.

  If $\mathbf{0}\ne \mathbf{s}=e_i{H}_i$, then one or three errors occurred in the ith column of $\mathbf{y}$. Replace the ith coordinate of $\overline{\mathbf{y}}$ by $\overline{{\mathbf{y}}_i}+e_i\in GF\left(4\right)$ and replace the ith column of $\mathbf{y}$ with the vector corresponding to $\overline{{\mathbf{y}}_i}+e_i$ such that the parity conditions are satisfied.

  iii.

  If $\mathbf{s}=e_j{H}_j$ for some $j\ne i$, then two errors occurred in column j and one error in the first entry of column i. Replace the $jth$ coordinate of $\overline{\mathbf{y}}$ by $\overline{{\mathbf{y}}_j}+e_j\in GF\left(4\right)$ and replace the $jth$ column of $\mathbf{y}$ with the vector corresponding to $\overline{{\mathbf{y}}_j}+e_j$ with the same parity as ${\mathbf{y}}_j$ and of distance 2 from ${\mathbf{y}}_j$. Finally, replace the first entry of ${\mathbf{y}}_{\mathbf{i}}$ and check that the parity conditions are satisfied.

  (c)

  If $p=2$, let ${\mathbf{y}}_i,{\mathbf{y}}_j$ be the columns with the different parity. Compute the syndrome $\mathbf{s}=\overline{\mathbf{y}}{H}^T$. We know that $\mathbf{s}=e_i{H}_i+e_j{H}_j$.

  i.

  If $\mathbf{s}=0$, then the two errors occurred on the first coordinates of ${\mathbf{y}}_i$ and ${\mathbf{y}}_j$. Replace both coordinates and check if the parity conditions are satisfied.

  ii.

  If $e_i\ne 0$ and $e_j=0$, then errors occurred in the ith column of $\mathbf{y}$ and the first coordinate of $y_j$. Replace the first coordinate of $y_j$. Then replace the ith coordinate of $\overline{\mathbf{y}}$ by $\overline{{\mathbf{y}}_i}+e_i\in GF\left(4\right)$ and replace the ith column of $\mathbf{y}$ with the vector corresponding to $\overline{{\mathbf{y}}_i}+e_i$ such that the parity conditions are satisfied.

  iii.

  If $e_i,e_j\ne 0$, then errors occurred in the ith and jth columns of $\mathbf{y}$. Replace the ith coordinate of $\overline{\mathbf{y}}$ by $\overline{{\mathbf{y}}_i}+e_i\in GF\left(4\right)$ and the jth coordinate by $\overline{{\mathbf{y}}_j}+e_j\in GF\left(4\right)$ then replace the ith and jth columns of $\mathbf{y}$ with the corresponding vectors such that the parity conditions are satisfied.

  (d)

  If $p=3$, let ${\mathbf{y}}_i,{\mathbf{y}}_j$ and ${\mathbf{y}}_k$ be the columns with different parity. Then there are one error each on these columns. Compute the syndrome $\mathbf{s}=\overline{\mathbf{y}}{H}^T$. We know that $\mathbf{s}=e_i{H}_i+e_j{H}_j+e_k{H}_k$

  i.

  If $\mathbf{s}=\mathbf{0}$, then the three errors occurred on the first coordinates of ${\mathbf{y}}_i,{\mathbf{y}}_j$ and ${\mathbf{y}}_k$. Replace the first coordinates in these columns and check if the parity conditions are satisfied.

  ii.

  If $e_i\ne 0$ and $e_j,e_k=0$, then one error occurred in the ith column of $\mathbf{y}$ and one error each on the first coordinates of ${\mathbf{y}}_j$ and ${\mathbf{y}}_k$. Replace the first coordinates of ${\mathbf{y}}_j$ and ${\mathbf{y}}_k$. Then replace the ith coordinate of $\overline{\mathbf{y}}$ by $\overline{{\mathbf{y}}_i}+e_i\in GF\left(4\right)$ and replace the ith column of $\mathbf{y}$ with the vector corresponding to $\overline{{\mathbf{y}}_i}+e_i$ such that the parity conditions are satisfied.

  iii.

  If $e_i\ne 0,e_j\ne 0$ and $e_k=0$, then one error each occurred in the ith and jth column of $\mathbf{y}$ and the first coordinate of ${\mathbf{y}}_k$. Replace the first coordinate of ${\mathbf{y}}_k$. Then replace the ith coordinate of $\overline{\mathbf{y}}$ by $\overline{{\mathbf{y}}_i}+e_i\in GF\left(4\right)$ and the jth coordinate by $\overline{{\mathbf{y}}_j}+e_j\in GF\left(4\right)$ then replace the ith and jth columns of $\mathbf{y}$ with the corresponding vectors such that the parity conditions are satisfied.

  iv.

  If $e_i,e_j,e_k\ne 0$, then let ${\mathbf{y}}^{\prime }=\overline{\mathbf{y}}+\mathbf{e}$ where $\mathbf{e}$ is the vector of length 9 with $e_i,e_j$ and $e_k$ on the $i,j$ and kth coordinate and zero elsewhere. Replace one coordinate each in the $i,j,k$th columns of $\mathbf{y}$ so that it becomes ${\mathbf{y}}^{\prime }$ and the parity conditions are satisfied.

Remark 2.

We remark that our algorithm for codes ${\mathcal{C}}_O^{36}$, ${\mathcal{C}}_E^{36}$, ${\mathcal{C}}_O^{40}$, and ${\mathcal{O}}_E^{40}$ is complete and ending because we considered all possible number of column parities $p=min(y^o,y^e)\le 3$ and adjusted at most three errors according to the top row parity so that Propositions 1 and 2 are satisfied.

5. Examples

In this section, we provide examples to illustrate how the given decoding algorithm works. Even though these are samples, most remaining cases are done similarly.

The following two examples illustrate how to decode ${\mathcal{C}}_O^{36}$ by hand. As a linear code over $GF\left(4\right)$, $C_4^9$ has the following parity check matrix.

$$H\left(C_4^9\right)=\left[\begin{array}{ccccccccc}1& 0& 0& 0& 1& 1& \overline{\omega }& 0& 1\\ 0& 1& 0& 0& 1& 0& \omega & \overline{\omega }& 1\\ 0& 0& 1& 0& \omega & \overline{\omega }& 1& \omega & 1\\ 0& 0& 0& 1& 1& \overline{\omega }& 0& 1& \overline{\omega }\end{array}\right]$$

Example 1.

In this example, we illustrate the projection decoding of ${\mathcal{C}}_O^{36}$. Let $y\in GF{\left(2\right)}^{36}$ be a codeword in ${\mathcal{C}}_O^{36}$ with some error of weight up to three. Consider the following projection of y.

$$\mathbf{y}=\begin{array}{cccccccccc}& 1& 2& 3& 4& 5& 6& 7& 8& 9\\ 0& 0& 1& 0& 1& 0& 1& 0& 1& 0\\ 1& 0& 1& 1& 0& 1& 0& 0& 1& 1\\ \omega & 1& 1& 0& 0& 0& 1& 1& 0& 0\\ \overline{\omega }& 0& 0& 0& 0& 1& 0& 0& 1& 0\\ \overline{\mathbf{y}}=& \omega & \overline{\omega }& 1& 0& \omega & \omega & \omega & \omega & 1\end{array}$$

All the columns have odd parity except for the 5th and 6th columns, and hence $p=2$. Then we have the syndrome

$$\mathbf{s}=\overline{\mathbf{y}}H{\left(C_4^9\right)}^T=\left[\begin{array}{c}\omega \\ \omega \\ \overline{\omega }\\ \omega \end{array}\right]=\omega \left[\begin{array}{c}1\\ 1\\ \omega \\ 1\end{array}\right]=\omega H{\left(C_4^9\right)}_5.$$

Therefore we proceed to ii of Step 3(c) with $e_5=\omega$ and $e_6=0$. We replace ${\overline{\mathbf{y}}}_5=\omega$ by ${\overline{\mathbf{y}}}_5+e_5=\omega +\omega =0$ and then replace ${\mathbf{y}}_5=\left[\begin{array}{c}0\\ 1\\ 0\\ 1\end{array}\right]$ by a vector in Table 5 corresponding to 0 closest to it. Finally, we replace the first entry of ${\mathbf{y}}_6$. So there are two errors in y. Therefore, we decoded y as

$$\mathbf{y}=\begin{array}{cccccccccc}& 1& 2& 3& 4& 5& 6& 7& 8& 9\\ 0& 0& 1& 0& 1& \mathbf{0}& \mathbf{0}& 0& 1& 0\\ 1& 0& 1& 1& 0& \mathbf{1}& 0& 0& 1& 1\\ \omega & 1& 1& 0& 0& \mathbf{1}& 1& 1& 0& 0\\ \overline{\omega }& 0& 0& 0& 0& \mathbf{1}& 0& 0& 1& 0\\ & \omega & \overline{\omega }& 1& 0& \mathbf{0}& \omega & \omega & \omega & 1\end{array}$$

Example 2.

Let $y\in GF{\left(2\right)}^{36}$ be a codeword of ${\mathcal{C}}_E^{36}$ with some error of weight up to three and have the following projection

$$\mathbf{y}=\begin{array}{cccccccccc}& 1& 2& 3& 4& 5& 6& 7& 8& 9\\ 0& 0& 1& 0& 0& 0& 1& 0& 1& 0\\ 1& 0& 1& 1& 0& 0& 0& 0& 0& 1\\ \omega & 1& 0& 1& 0& 0& 1& 0& 0& 0\\ \overline{\omega }& 0& 1& 1& 1& 1& 1& 1& 1& 0\\ \overline{\mathbf{y}}=& \omega & \omega & 0& \overline{\omega }& \overline{\omega }& 1& \overline{\omega }& \overline{\omega }& 1\end{array}$$

Please note that $p=1$ and the parity of the 8th column differs from the rest of the column, i.e., $i=8$ in Step 3(b). We then compute the syndrome:

$$\mathbf{s}=\overline{\mathbf{y}}H{\left(C_4^9\right)}^T=\left[\begin{array}{c}\overline{\omega }\\ \overline{\omega }\\ 1\\ \overline{\omega }\end{array}\right]=\overline{\omega }\left[\begin{array}{c}1\\ 1\\ \omega \\ 1\end{array}\right]=\overline{\omega }H{\left(C_4^9\right)}_5.$$

So we have $j=5\ne i$ and $e_5=\overline{\omega }$. Proceeding with iii of Step 3(b), we replace ${\overline{\mathbf{y}}}_5=\overline{\omega }$ by ${\overline{\mathbf{y}}}_5+e_5=\overline{\omega }+\overline{\omega }=0$ and replace the fifth column ${\mathbf{y}}_5=\left[\begin{array}{c}0\\ 0\\ 0\\ 1\end{array}\right]$ by a vector in Table 5 corresponding to 0 which is of the same parity and distance 2 from ${\mathbf{y}}_5$. Then we change the first entry of ${\mathbf{y}}_8$. There are three errors in y. We decoded y as

$$\mathbf{y}=\begin{array}{cccccccccc}& 1& 2& 3& 4& 5& 6& 7& 8& 9\\ 0& 0& 1& 0& 0& \mathbf{0}& 1& 0& \mathbf{0}& 0\\ 1& 0& 1& 1& 0& \mathbf{1}& 0& 0& 0& 1\\ \omega & 1& 0& 1& 0& \mathbf{1}& 1& 0& 0& 0\\ \overline{\omega }& 0& 1& 1& 1& \mathbf{1}& 1& 1& 1& 0\\ & \omega & \omega & 0& \overline{\omega }& \mathbf{0}& 1& \overline{\omega }& \overline{\omega }& 1\end{array}$$

Next we show examples of projection decoding of ${\mathcal{C}}_O^{40}$ and ${\mathcal{C}}_E^{40}$. We use the following parity check matrix for $C_4^{10}$.

$$H\left(C_4^{10}\right)=\left[\begin{array}{cccccccccc}1& 0& 0& 0& 1& 1& \overline{\omega }& 0& 1& \overline{\omega }\\ 0& 1& 0& 0& 1& 0& \omega & \overline{\omega }& 1& \omega \\ 0& 0& 1& 0& \omega & \overline{\omega }& 1& \omega & 1& 0\\ 0& 0& 0& 1& 1& \overline{\omega }& 0& 1& \overline{\omega }& w\end{array}\right]$$

Example 3.

Assume $y\in GF{\left(2\right)}^{40}$ is a codeword of ${\mathcal{C}}_O^{40}$ with error of weight up to three and with the following projection

$$\mathbf{y}=\begin{array}{ccccccccccc}& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10\\ 0& 1& 0& 1& 0& 0& 0& 0& 1& 1& 1\\ 1& 0& 0& 1& 0& 1& 1& 1& 0& 0& 1\\ \omega & 0& 0& 1& 0& 1& 0& 1& 0& 0& 0\\ \overline{\omega }& 0& 1& 0& 1& 1& 0& 1& 0& 0& 1\\ \overline{\mathbf{y}}=& 0& \overline{\omega }& \overline{\omega }& \overline{\omega }& 0& 1& 0& 0& 0& \omega \end{array}$$

All the columns and the first row are of odd parity, so $p=0$. Computing the syndrome, we have

$$\mathbf{s}=\overline{\mathbf{y}}H{\left(C_4^{10}\right)}^T=\left[\begin{array}{c}0\\ 0\\ 0\\ \overline{\omega }\end{array}\right]=\overline{\omega }\left[\begin{array}{c}0\\ 0\\ 0\\ 1\end{array}\right]=\overline{\omega }H{\left(C_4^{10}\right)}_4.$$

Since $\mathbf{s}\ne \mathbf{0}$, by ii of Step 3(a) with $e_4=\overline{\omega }$, two errors occurred on the 4th column of $\mathbf{y}$. We replace ${\overline{\mathbf{y}}}_4=\overline{\omega }$ by ${\overline{\mathbf{y}}}_4+e_4=\overline{\omega }+\overline{\omega }=0$ and replace the fourth column ${\mathbf{y}}_4$ by the vector in Table 5 corresponding to 0 and of distance 2 from ${\mathbf{y}}_4=\left[\begin{array}{c}0\\ 0\\ 0\\ 1\end{array}\right]$. There are two errors in y. Therefore, y is decoded as

$${\mathbf{y}}^{\prime }=\begin{array}{ccccccccccc}& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10\\ 0& 1& 0& 1& \mathbf{0}& 0& 0& 0& 1& 1& 1\\ 1& 0& 0& 1& \mathbf{1}& 1& 1& 1& 0& 0& 1\\ \omega & 0& 0& 1& \mathbf{1}& 1& 0& 1& 0& 0& 0\\ \overline{\omega }& 0& 1& 0& \mathbf{1}& 1& 0& 1& 0& 0& 1\\ & 0& \overline{\omega }& \overline{\omega }& \mathbf{0}& 0& 1& 0& 0& 0& \omega \end{array}.$$

Example 4.

Assume $y\in GF{\left(2\right)}^{40}$ is a codeword of ${\mathcal{C}}_E^{40}$ with some error of weight up to 3. Let y have the following projection

$$\mathbf{y}=\begin{array}{ccccccccccc}& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10\\ 0& 0& 0& 1& 0& 1& 0& 0& 1& 0& 0\\ 1& 1& 0& 0& 0& 0& 0& 1& 1& 1& 0\\ \omega & 0& 1& 1& 1& 0& 1& 0& 1& 0& 1\\ \overline{\omega }& 1& 1& 1& 1& 1& 1& 1& 0& 1& 0\\ \overline{\mathbf{y}}=& \omega & 1& 1& 1& \overline{\omega }& 1& \omega & \overline{\omega }& \omega & \omega \end{array}$$

All the columns except columns 3, 8 and 10 are even so $p=3$. The syndrome is

$$\mathbf{s}=\overline{\mathbf{y}}H{\left(C_4^{10}\right)}^T=\left[\begin{array}{c}\omega \\ \omega \\ \omega \\ 0\end{array}\right]=H{\left(C_4^{10}\right)}_8+\overline{\omega }H{\left(C_4^{10}\right)}_{10}$$

Hence, from iii of Step 3(d), we have $e_8=1$, $e_{10}=\overline{\omega }$ and $e_3=0$. So we replace ${\overline{\mathbf{y}}}_8$ by ${\overline{\mathbf{y}}}_8+e_8=\overline{\omega }+1=\omega$ and ${\mathbf{y}}_8$ by the vector corresponding to ω in Table 5 closest to$\left[\begin{array}{c}1\\ 1\\ 1\\ 0\end{array}\right]$. We also replace ${\overline{\mathbf{y}}}_{10}$ by ${\overline{\mathbf{y}}}_{10}+e_{10}=\omega +\overline{\omega }=1$ and ${\mathbf{y}}_{10}=\left[\begin{array}{c}0\\ 0\\ 1\\ 0\end{array}\right]$ by the vector closest to it corresponding to 1 in Table 5. Finally we replace the first entry of column 3. There are three errors in y. Therefore, y is decoded as

$$\mathbf{y}=\begin{array}{ccccccccccc}& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10\\ 0& 0& 0& \mathbf{0}& 0& 1& 0& 0& \mathbf{1}& 0& \mathbf{0}\\ 1& 1& 0& 0& 0& 0& 0& 1& \mathbf{0}& 1& \mathbf{0}\\ \omega & 0& 1& 1& 1& 0& 1& 0& \mathbf{1}& 0& \mathbf{1}\\ \overline{\omega }& 1& 1& 1& 1& 1& 1& 1& \mathbf{0}& 1& \mathbf{1}\\ & \omega & 1& 1& 1& \overline{\omega }& 1& \omega & \omega & \omega & \mathbf{1}\end{array}$$

Remark 3.

The most time consuming part (or the dominating complexity part of the algorithm) is to decode the projected vector $\overline{\mathbf{y}}$ in the linear code ${\mathcal{C}}_4^9$ or ${\mathcal{C}}_4^{10}$ using the syndrome decoding. However, since we know which positions (or columns) have errors, this syndrome decoding can be done in at most $3\times 3\times 3=27$ possible ways because there are scalar multiples in the syndrome equation involving three nonzero scalars in Step (d) of the algorithm.

6. Conclusions

In this paper, we described how to decode binary optimal $[36,19,8]$ and $[40,22,8]$ codes by projecting them onto the linear $[9,5,4]$ and $[10,6,4]$ codes over $GF\left(4\right)$. Even though there were similar decoding for self-dual codes of lengths 24, 32, 40, there was no known efficient decoding algorithm for these non-self-dual optimal codes. Actually our algorithm works for any linear code with a projection onto a linear or additive code over $GF\left(4\right)$ for errors of weight at most 3.