1 Introduction↩︎

An \((n,R)_q\)-covering code \({\cal C}\) is a set of words of length \(n\) over a given alphabet \(\Sigma_q\), of size \(q\), such that each word of length \(n\) over \(\Sigma_q\) is within Hamming distance \(R\) from at least one codeword in \({\cal C}\). In other words, for each \(x \in \Sigma_q^n\), there exists \(c \in {\cal C}\) such that \(d(x,c) \leq R\), where \(d(y,z)\), \(y,z \in \Sigma_q^n\), denotes the Hamming distance between \(y\) and \(z\). Covering codes were always of interest, but the interest increased due to the following three seminal papers [1]–[3]. The interest was also increased partially because of the connection of covering codes to data compression. An excellent book that covers all aspects of such codes is [4]. One of the main goals is to find for given \(n\), \(R\), and \(q\), the \((n,R)_q\)-covering code of the smallest size. Lot of work was done in this direction, see the excellent book [4] and references therein.

An \((n,R)_q\)-covering sequence (an \((n,R)_q\)-CS for short) is a cyclic sequence whose consecutive \(n\)-tuple form an \((n,R)_q\)-covering code. The target is to find for given \(n\), \(R\), and \(q\), the \((n,R)_q\)-CS of the shortest length. These sequences were considered first by Chung and Cooper [5] who called such a structure a de Bruijn covering code. The reason for the name was that the \(n\)-tuples of a cyclic sequence are considered, and this sequence forms a cycle in the de Bruijn graph. Moreover, if \(R=0\) then the shortest such sequence is a de Bruijn sequence [6]–[8].

The simple lower bound on the size of \({\cal C}\) is \[\left|{\cal C}\right| \geq \frac{q^n}{V_q (n,R)},\] where \[V_q(n,R) = \sum_{i=0}^{R} \binom{n}{i} (q-1)^i ~.\] This bound is the sphere-covering bound. There exists a covering code that approaches this bound up to a factor roughly \(eR \log R\) [9]. The proof method for this bound is probabilistic. A similar bound for an \((n,R)_q\)-CS over a prime power alphabet was presented in [5]. This bound was generalized to any alphabet by Vu [10]. The bound states that for fixed \(R\) there exists an \((n,R)_q\)-CS, over \(\Sigma_q\), whose length is at most \(\mathcal{O}\left(\frac{q^n}{V_q(n,R)}\log n \right)\).

For small \(R\), there are some \((n,R)_q\)-covering codes that attain the sphere-covering bound with equality, such as the Hamming codes of length \(n=2^r-1\) and radius one. Other codes are very close to the upper bound, such as the ones for \(R=2\) which are perfect asymptotically [11],[12],[13], or other similar codes [12], [14]. Similarly, such sparse covering codes were also considered for \(R=3\) [12], [14]. The main goal of the research on \((n,R)_q\)-CSs is to obtain sequences whose length is as close as possible to the upper bounds obtained for covering codes. For small \(n\), lower and upper bounds on the sizes of \((n,R)_2\)-CSs were obtained in [5]. Several constructions that yield upper bounds on the size of such binary sequences for small and large \(n\) were obtained in [15], [16]. Using heuristic search, some bounds for small \(n\) and \(R\) were found by [17]. Two of the constructions presented in [15], [16] yield sequences whose length is within a small constant factor of optimality. These sequences were obtained only for length \(n=2^r\) and \(n=2^r-1\) and the radius of the code is only \(1\).

Finally, the exposition in [16] suggested a new type of covering codes. An \((n,m,R)_q\)-CS code (an \((n,m,R)_q\)-CSC for short) \({\cal C}\) is a set of cyclic sequences, which are the codewords, of length \(m\) such that each word of length \(n\) is within distance \(R\) from at least one \(n\)-tuple of a codeword of \({\cal C}\), i.e., the consecutive \(n\)-tuples of all the codewords of \({\cal C}\) form an \((n,R)_q\)-covering code. Any cyclic code \({\cal C}\) of length \(n\) and covering radius \(R\) can be used as an \((n,n,R)_q\)-CSC \({\cal C}'\), where from the codewords that have the same cyclic shifts (which will be referred to later as an orbit, when only one representative is taken). An \((n,R)_q\)-CS of length \(\ell\) is an \((n,\ell,R)_q\)-CSC and hence the covering-sequences codes are the link between cyclic covering codes and covering sequences. This also can be the measure to evaluate the efficiency of a covering sequences code. A code that yields a shorter covering sequence is a better code.

There are four goals for this paper. The first one is to have some exposition for \((n,R)_q\)-CSs and \((n,m,R)_q\)-CSCs for \(q>2\) as [16] considered only binary sequences. The second is to find new \((n,R)_q\)-CSs that are within a small constant factor from optimality. The third is to put a strong emphasis on \((n,m,R)_q\)-CSCs and to find new \((n,m,R)_q\)-CSCs, especially codes for which \(m> n\). We believe that this should be a main focus in future research on covering codes. where the total length of the codewords is within a constant factor from optimality. The fourth is to look on the structure of orbits associated with the codes generated in the current paper.

The rest of the paper is organized as follows. Section 2 describes the main construction of a \((n,R)_q\)-CS from an \((n,m,R)_q\)-CSC. Section 3 reviews the constructions of the sequences for \(n=2^r\) and \(n=2^r-1\). It also emphasizes the connection of these constructions and \((n,m,R)_q\)-CSCs. Self-dual sequences play an important and surprising role in the construction of \(n=2^r\). They can present a nearly perfect covering code as a negacyclic code. All of these concepts will be discussed in this section. Section 4 shifts the discussion towards non-binary sequences over any finite field \(\mathbb{F}_q\). The optimal constructions in the binary case are generalized for \(\mathbb{F}_q\). In particular, constacyclic codes take the role of self-dual sequences in one of the constructions. The sequences obtained in the constructions are analyzed, and it is shown that the lengths of the obtained sequences are within a small constant factor of optimality. In particular, a factor of \(\frac{q}{q-1}\) from optimality is obtained for sequences over \(\mathbb{F}_q\). Section 5 is devoted to a construction of \((n,R)_q\)-CSs and \((n,m,R)_q\)-CSCs from codes obtained by interleaving. Interleaving has been presented in the past for constructions of \((n,R)_q\)-CSs, but in this section, interleaving is not performed directly on the sequences, but on the parity-check matrices of codes used to construct the \((n,R)_q\)-CSs. The sequences have a larger radius than the ones from which they were interleaved. Conclusions and a list of open problems are suggested in Section 6.

2 A Construction from Cyclic CSC↩︎

This section is devoted for the basic idea of the main construction presented in this work and implemented later for various parameters on various codes. Although the construction in [16] was defined for a binary alphabet, generalization for the construction to a non-binary alphabet is straightforward. The construction starts with an \((n,m,R)_q\)-CSC \({\cal C}\) with \(M\) codewords of length \(m\). A sequence \({\cal S}\) is degenerated if it can be represented as \({\cal S}= [X,X,\ldots,X]\), where the length of \(X\) is smaller than the length of \({\cal S}\). If \(X\) is the shortest string in such representation, then the length of \(X\) is the period of the sequence. The period of \(X\) is always a divisor of \(m\). If the shortest such string has length \(m\), then the sequence has full-period. If two sequences \({\cal S}_1\) and \({\cal S}_2\) are cyclic shifts of each other, then the sequences are called equivalent and denoted by \({\cal S}_1 \simeq {\cal S}_2\). For each codeword \({\mathbf{c}}\) (a cyclic sequence), we have to choose a starting point and let such a codeword \({\mathbf{c}}=(c_1,c_2,\ldots,c_m)\) be extended to \({\mathbf{c}}'=(c_1,c_2,\ldots,c_m,c_1,c_2,\ldots,c_{n-1})\). If \({\mathbf{c}}=(c_1,c_2,\ldots,c_m)\) is a degenerated codeword of period \(\ell\) that divides \(m\), then its extended codeword is \({\mathbf{c}}'=(c_1,c_2,\ldots,c_\ell,c_1,c_2,\ldots,c_{n-1})\). The extended codewords should be ordered in a list \({\mathbf{c}}_0'\), \({\mathbf{c}}_1'\), \({\mathbf{c}}_2'\),…,\({\mathbf{c}}_{M-1}'\), in a way that \({\mathbf{c}}_i'\) and \({\mathbf{c}}_{i+1}'\), for \(0 \leq i \leq M-1\), have a common string \(X_i\) of length \(t_i\), which is suffix of \({\mathbf{c}}_i'\) and a prefix of \({\mathbf{c}}_{i+1}'\), \(0 \leq i \leq M-1\), where indices are taken modulo \(M\). In other words, \({\mathbf{c}}_i' = (X_{i-1}, Z_i)=(Y_i X_i)\) and \({\mathbf{c}}_{i+1}'=(X_i,Z_{i+1})=(Y_{i+1},X_{i+1})\). Now, we can concatenate all the codewords in the list \({\mathbf{c}}_0'\), \({\mathbf{c}}_1'\), \({\mathbf{c}}_2'\),…,\({\mathbf{c}}_{M-1}'\) omitting the shared parts \(X_0\), \(X_1\),…,\(X_{M-1}\) to one cyclic sequence as follows: \[{\cal S}= [Y_0,Y_1,Y_2,\ldots,Y_{M-1}]~.\]

The construction uses merging of cycles and hence it will be referred to as Construction MC (merging cycles).

3 Binary Covering-Sequences Codes↩︎

After the description of Construction MC based on cyclic covering-sequences codes, we are going to describe implementations of the construction. Two such implementations were considered in [16]. The first one is based on the cyclic Hamming code, and the second one is based on self-dual sequences that form a nearly perfect covering code. The review of these two implementations will help to explain the constructions in Sections 4 and 5 as well as to shed some new light on the implementation with self-dual sequences.

3.1 \((2^r-1,1)\)-CS based on the Hamming code↩︎

Let \([n,k]_q\) denote a linear code of length \(n\) and dimension \(k\) over the finite field with \(q\) elements, \(\mathbb{F}_q\). The \([2^r-1,2^r-1-r]_2\) Hamming code, \({\cal H}_2(r)\), is a cyclic code, with radius \(1\), whose parity-check matrix can be represented as \[[ \alpha^0 ~ \alpha^1 ~ \alpha^2 ~ \cdots ~ \alpha^{2^r-2} ],\] where \(\alpha\) is a primitive element in \(\mathbb{F}_{2^r}\). It is well-known that the number of degenerated orbits in the code is much less than \(2^{2^{k-1}}\) [7], [16]. Therefore, for the construction of an \((2^r-1,1)\)-CS we are using less than \(2^{2^r -2r-1} + 2^{2^{k-1}}\) orbits (full-period and degenerated) that yield a \((2^r-1,1)_2\)-CS whose length is less than \(2^{2^r -r} + 2^{2^{r-1} +r+1}\). Thus, the sequence is within a factor of less than \(2 + \frac{1}{2^{2^r-2k-2}}\) from optimality.

It is interesting to note that all the binary degenerated sequences of length \(2^r-1\) are codewords in the Hamming code and hence they had to be taken into account in the computations.

3.2 \((2^r,1)\)-CS based on self-dual sequences↩︎

The implementation of Construction MC using self-dual sequences is of a special interest for a few different reasons. A binary cyclic sequence \({\cal S}= [s_0,s_1,\ldots,s_{k-1}]\) is called self-dual sequence if it is invariant under completion. We will refer only to self-dual sequences with full-period, i.e., not degenerated. Such a sequence \(S\) can be represented as \({\cal S}=[ X , \bar{X}]\), where \(X\) is a sequence whose length is \(k/2\) and \(\bar{X}\) is the binary complement of \(X\). In [16] there is a construction for a set of \(2^{2^r -2r-1}\) such sequences of length \(2^{r+1}\). This set of sequences form a \((2^r,2^{r+1},1)_2\)-CSC \({\cal C}\). By applying Construction MC on these sequences of \({\cal C}\) we obtain a \((2^r,1)_2\)-CS of length smaller than \(2^{2^r-2k-2}(2^{r+2}+2^r-1)\). An \((2^r,1)_2\)-covering code of the smallest size has \(2^{2^r-r}\) codewords. Thus, the \((2^r,1)_2\)-CS obtained by Construction MC on the code \({\cal C}\) has size within factor of \(1.25\) from optimality.

Moreover, the \(n\)-tuples of the CSC \({\cal C}\) form what is called a nearly perfect 1-covering code [18]. This specific code has some more interesting properties [18] that can be also obtained from a union of an extended Hamming code and its coset. We will refer to this code again in the next section.

4 Optimal Non-Binary Covering-Sequences Codes↩︎

The idea behind the two constructions of the \((n,1)_2\)-CSs in Section 3 is to use concatenation of codewords from a cyclic codes or, more precisely \((n,m,R)_q\)-CSCs. In Section 3 such binary codes were considered. In Section 3.1 the used code is \({\cal H}_2(r)\), i.e., \(n=m\), while in Section 3.2 the code used consists of a set of self-dual sequences and \(m >n\). In the non-binary case there are two types of \((n,m,R)_q\)-CSCs too, one for which \(m=n\) and one for which \(m>n\). But, in both cases \({\cal H}_q(r)\) is used. As in the binary case cyclic codes are used, but instead of self-dual sequences another type of code is used.

Cyclic codes have been extensively studied in the literature. The same is true for negacyclic codes, e.g. [19], [20] and constacyclic codes, e.g. [21], [22]. In some wide sense the code obtained from self-dual sequences can be said to be negacyclic if the alphabet \(\{ 0,1 \}\) will be changed to \(\{ -1 , +1\}\). For non-binary sequences and codes, \({\cal H}_q(r)\) will be represented as a constacyclic code.

For a Hamming code over \(\mathbb{F}_q\), \(q\) a prime power, with redundancy \(r\), \({\cal H}_q(r)\), the parity-check matrix is represented by \(n=\frac{q^r-1}{q-1}\) linearly independent column vectors of length \(r\). These \(n\) columns can be chosen in a few different ways. For example, we can take all column vectors of length \(r\) whose first nonzero entry is an one. We will choose a different representation which resembles the choice for \({\cal H}_2 (r)\). Let \(\alpha\) be a primitive element in \(\mathbb{F}_{q^r}\) and let \(H\) the \(\frac{q^r-1}{q-1} \times r\) matrix whose \(i\)-th column is the vector representing \(\alpha^i\), \(0 \leq i < n\).

While \({\cal H}_2(r)\) is always a cyclic code with radius 1. \({\cal H}_q(r)\) is a cyclic code if and only if \({\gcd (r,q-1)=1}\)[23].[24]. Construction MC can be applied to \({\cal H}_q(r)\) when \(\gcd (r,q-1)=1\) and yields similar results, while, Lemma 2 does not have a straightforward generalization for \(\mathbb{F}_q\).

We do not have a construction with self-dual sequences for the non-binary case. Moreover, these sequences form a topic for further research [25], [26]. Instead, we use the fact that the Hamming code over \(\mathbb{F}_q\) can be always represented as a constacyclic code as follows. The element \(\gamma = \alpha^n\) is a primitive element in \(\mathbb{F}_q\). The parity-check matrix of \({\cal H}_q(r)\) is \[[ h_0 ~ h_1 ~ \cdots ~ h_{n-1} ],\] where \(h_i\) is the \(q\)-ary representation of \(\alpha^i\).

If \((c_0,c_1,\ldots,c_{n-2},c_{n-1})\) is a codeword then \(\sum_{i=0}^{n-1} c_i \alpha^i = {\boldsymbol{0}}\). This implies that \(\sum_{i=0}^{n-1} c_i \alpha^{i+1} = {\boldsymbol{0}}\) or \((c_{n-1} \gamma) \alpha^0 + \sum_{i=1}^{n-1} c_{i-1} \alpha^i ={\boldsymbol{0}}\). As a consequence we have that \((\gamma a_{n-1},c_0,c_1,\ldots,c_{n-2})\) is a codeword in \({\cal H}_q(r)\). With the same process we have that \((\gamma a_{n-2},\gamma a_{n-1},c_0,c_1,\ldots,c_{n-3})\) is a codeword and so on, so \((\gamma c_0, \gamma c_1,\ldots, \gamma c_{n-2}, \gamma c_{n-1})\) is a codeword, \((\gamma^2 c_0, \gamma^2 c_1,\ldots, \gamma^2 c_{n-2}, \gamma^2 c_{n-1})\) is a codeword, and finally \((\gamma^{q-2} c_0, \gamma^{q-2} c_1,\ldots, \gamma^{q-2} c_{t-2}, \gamma^{q-2} c_{n-1})\) is a codeword. In this process we have that \[(c_1,\ldots, c_{n-2}, c_{n-1},\gamma^{q-2} c_0)=(c_1,\ldots, c_{n-2}, c_{n-1},\gamma^{-1} c_0)\] is a codeword (note that \(\gamma^{-1}\) is also a primitive element in \(\mathbb{F}_q\)). Hence we have the following results, which can now be easily verified.

Not all degenerated words of length \((q-1)n\) over \(\mathbb{F}_q\) are codewords since not all the required conditions in the proof of Lemma 2 are satisfied. This will be further discussed in the full version of this paper.

Of special interest are those codes whose length of codeword of \({\cal H}_q(r)\) is a repunit prime. A prime of the form \(n=\frac{q^r-1}{q-1}\) is called a repunit prime. When \(q=2\) this prime is a well-known Mersenne prime. If \(n\) is a prime, then all the codewords of the related \((n,q^r -1,1)_q\)-CSC are on orbits of full-period except for \(q\) codewords, the all-zero codeword and the \(q-1\) codewords whose orbit is \([c_0,c_1,\ldots,c_{q-1}]\), where \(c_i = \gamma^i\) and \(\gamma\) is a primitive element in \(\mathbb{F}_q\). Since all orbit except for these two are of full-period it follows that the size of the code is \[\frac{q^{n-r} -q}{n(q-1)} +2 = q \frac{q^{n-r-1}-1}{q^r -1} +2 .\] Each orbit is extended with \(n-1\) bits and using concatenation, we find that the length of the associated \((n,1)_q\)-CS is not more than \[q \frac{q^{n-r-1}-1}{q^r -1} (q^r -1 +n-1) +q+2(n-1) \leq q^{n-r} -q +(q^{n-r-1}-1) \frac{q}{q-1} \leq q^{n-r} \frac{q}{q-1}\] and since the size of optimal \((n,1)_q\)-covering code is \(q^{n-r}\), it follows that the constructed CSC and CS are within a factor of \(\frac{q}{q-1}\) from optimality. Slightly more complicated analysis achieves the same result when \(n\) is not a prime.

5 Interleaving of parity-Check matrices↩︎

Interleaving two covering sequences, in an appropriate way, yields a new covering sequence with a larger radius and relatively short length [16]. In this section, we show that interleaving the parity-check matrix of a cyclic covering code with the same parity-check matrix yields a better covering sequence whose length can be within a smaller factor from optimality. The following lemma can be verified from the definition of a cyclic linear covering code.

Lemma 4 can be implemented on \({\cal H}_q(r)\) to obtain \((n,2)_q\)-CSs whose length is within a constant factor of optimality.

Similarly to Example 1 we can give \((n,2)_q\)-CSs whose length is within a small factor of the lower bound for \((n,2)_q\) when the sequence is over \(\mathbb{F}_q\), where \(q > 2\). This can be done with the non-binary cyclic codes and the non-binary constacyclic codes presented in Section 4.

There are a few interesting families of codes obtained by interleaving of parity-check matrices. These codes are described in the following two examples.

6 Conclusions and Open Problems for Future Research↩︎

We have considered binary and non-binary covering sequences and covering-sequences codes. More details on some of the claims and some of the constructed codes will be presented in the full version of this paper. Our brief exposition raises several interesting problems for future research.

1. The same techniques used in the paper can be further used to obtain \((n,R)_q\)-CS sequences with larger radii, but the codes obtained will start to be within a larger optimality factor. Can the method be improved to obtain sequences of shorter length? Such an improvement or a new construction for shorter sequences is interesting when \(R\) is small and large.

2. The number of cyclic sequences obtained from the codewords in \({\cal H}_2(r)\) can be calculated based on the formula for the number of necklaces of order \(n\) for each length [7]. But the formula is quite complicated. Can these computations be simplified for exact computation of the sizes of the derived \((n,n,1)_q\)-CSCs. The situation is even more complicated for the \((n,q^r -1,1)_q\)-CSCs based on the representation of \({\cal H}_q(r)\) as a constacyclic code. Some of these computations will be considered in the full version of this paper.

3. The exact computation for the number of codewords in a \((\frac{q^r-1}{q-1} R,(q^r -1)R,R)_q\)-CSC is also of some interest. When \(\frac{q^r-1}{q-1}\) is a repunit prime, this computation is relatively easier and will be discussed in the full version of this paper.

4. In the context of the previous problems, it is interesting to consider the possible periods of the orbits in an \((n,q^r -1,1)_q\)-CSC which depend on the divisors of \(q^r -1\), but as was mentioned, when \(\frac{q^r-1}{q-1}\) is not a prime, not for all divisors of \(q^r-1\) there are orbits with the associated divisor as a codeword. Moreover, not all degenerated necklaces are codewords for periods where there are codewords, in contrary to the case of \({\cal H}_2(r)\) as proved in Lemma 2. This poses many questions, some of which will be discussed in the full version.

5. Some more analysis will be provided in the full version, but this is far from a complete analysis as was also pointed out in the previous problems.

References↩︎