Construction of cyclic codes over \(\mathrm{GF}(4)\) for DNA computing (Q2455456)

The paper investigates a class of linear and additive cyclic codes of odd length over \(\mathrm{GF}(4)=\{0,1,\omega ,\omega ^{2}\}\) (where \(\omega ^{2}+\omega +1=0\)) that arise in DNA\ computing. The constraints imposed by DNA computing suggest that a suitable code \(C\) should be \textit{reversible }(for any codeword \(~u=u_{0}u_{1}\dots u_{n-1}\in C\), \(u^{r}=u_{n-1}u_{n-2}\dots u_{0}\) is also in \(C\)) and \textit{complement }(for any codeword \( u=u_{0}u_{1}\dots u_{n-1}\in C\), \(u^{c}=u_{0}^{c}u_{1}^{c}\dots u_{n-1}^{c}\) is also in \(C\), where \(x^{c}=1+x,\) for any \(x\in \mathrm{GF}(4))\). The main results (Theorems 11 and 12) give a classification of such codes over \(\mathrm{GF}(4)\). It is proved that any additive reversible complement cyclic code \(C\) of odd length \(n\) over \(\mathrm{GF}(4)\) falls in one of the following types: (i) \(C=(\omega p(x),r(x))\) or \(C=(\omega ^{2}p(x),r(x))\), where \(p(x)\), \(r(x)\) are self-reciprocal binary polynomials that divide \(x^{n}-1\pmod 2\) and \(x-1\) does not divide \(r(x)\). (ii) \(C=(\omega p(x)+q(x),r(x))\), where \(p(x),r(x)\) are self-reciprocal binary polynomials that divide \(x^n-1\pmod 2\), \(r(x)\) divides \( q(x)(x^n-1)/p(x)\pmod 2\) and \(x-1\) does not divide \(r(x)\). Moreover, (1) if \(\deg (q)=\deg (p),\) then \(q(x)\) is self-reciprocal, (2) if \(\deg (q)<\deg (p),\) then \(r(x)\) divides \(x^{\deg (p)-\deg (q)}q^{\ast }(x)+q(x),\) (3) if \(\deg (q)>\deg (p),\) then \(r(x)\) divides \(x^{\deg (q)-\deg (p)}q(x)+q^{\ast }(x).\) This classification enables the authors to list explicitly the linear reversible complement cyclic codes over \(\mathrm{GF}(4)\) of lengths \(7, 9, 11\), and \(13\). For the additive case, two tables are given. Table 1 concerns the additive reversible complement cyclic codes \(C\) of length \(n~\)with minimum distance \(d \) \ that satisfy the RC (``reverse complement'') constraint for \(d\): for any \(u,v\in C\), \(H(u^c,v^r)\geq d\). (\(H\) denotes the Hamming distance). For \(n\in \{7,9,11,13\}\) and \(3\leq d\leq 11\), the number of codewords of the best code among these codes is given (if it exists). For example, there exists such a code of length 7 with minimum distance 3 with 256 codewords (the previously known best code of length 7 with minimum distance 3 had 180 codewords). Table 2 gives the best such codes that have fixed GC-content. No details of the computations necessary to obtain these tables are given.