Covering Sequences for $\ell$-tuples

The binary de Bruijn graph of order $\ell$, $G_{\ell}$, was introduced in 1946 by de Bruijn [6]. His target in introducing this graph was to find a recursive method to enumerate the number of cyclic binary sequences of length $2^{\ell}$ such that each $\ell$-tuple appears as a window exactly once in each sequence. These sequences were later called de Bruijn sequences. These results were later generalized in [22] for any alphabet of finite size $q$, using a $q$-ary generalization of the de Bruijn graph of order $\ell$, $G_{q,\ell}$.

The vertices of $G_{q,\ell}$ are the $q$-ary $(\ell-1)$-tuples, and its edges correspond to the $q$-ary $\ell$-tuples. There is an edge ${u\rightarrow v}$ if $v$ can be obtained from $u$ by shifting one entry left and appending a symbol. Eulerian cycles in de Bruijn graphs, i.e., cycles that visit all the edges of $G_{q,\ell}$ exactly once, are called de Bruijn cycles. It was proved that the number of de Bruijn cycles in $G_{q,\ell}$ is $(q!)^{q^{\ell-1}}/{q^{\ell}}$ [22].

Each de Bruijn cycle induces a single (cyclic) de Bruijn sequence of length $q^{\ell}$, by picking any edge in the cycle as a starting point, considering its first entry and appending the first entry of each consecutive edge in the cycle. All sequences that can be generated in this way are considered as the same sequence. Contrary to this, each de Bruijn cycle induces $q^{\ell}$ distinct acyclic de Bruijn sequences, i.e., sequences of length $q^{\ell}+\ell-1$ that contain each $\ell$-tuple as a window exactly once, using a similar method with the exception of appending the ($\ell-1$)-suffix of the last edge as well; each sequence corresponds to a choice of different starting edge from $G_{q,\ell}$. Hence, the number of such acyclic de Bruijn sequences is $(q!)^{q^{\ell-1}}$ and their asymptotic rate is $\log_{q}(q!)/q$ (equals $1/2$ for $q=2$). One of the first applications of the de Bruijn graph was in the introduction of shift-register sequences and linear feedback shift registers [11]. Throughout the years, an extensive number of papers have studied the de Bruijn sequences and their applications, several of those include [2, 4, 8, 9, 13, 17, 19]. Most recently, DNA storage has brought fresh interest to this family of sequences; for more information on such applications the reader is referred to [1, 12, 21].

This paper studies a novel generalization of de Bruijn sequences (for the rest of this paper we refer only to acyclic sequences). We say that a sequence is an $\ell$-tuples covering sequence if it contains each $q$-ary $\ell$-tuple as a window at least once. This work follows recent generalizations of de Bruijn sequences that proposed unique variations regarding the appearances of $\ell$-tuples in the sequence: $\ell$-repeat free sequences [7, 10] require each $\ell$-tuple to appear at most once, ($b,\ell$)-locally-constrained de Bruijn sequences [3] require each $\ell$-tuple to appear at most once in every window of length $b$, and $(\ell,\mu)$-balanced de Bruijn sequences [16] require each ${\ell\text{-tuple}}$ to appear exactly $\mu$ times in the sequence.

Notice that for sequences of length $q^{\ell}+\ell-1$, all $\ell$-tuples covering sequences are simply the de Bruijn sequences deduced from the de Bruijn graph $G_{q,\ell}$; as a result, their asymptotic rate is $\log_{q}(q!)/q$. Our main goal is to efficiently construct codes of $\ell$-tuples covering sequences with higher rates (specifically larger than $1/2$ for binary sequences) and fixed number of redundancy symbols. We study the cardinality for the set of $\ell$-tuples covering sequences and present lower bounds on its asymptotic rate for various values of $\ell$. Additionally, we present an upper bound on $\ell$ such that the redundancy of the set of all $\ell$-tuples covering sequences is at most one symbol. Later, we present an encoding algorithm for the set of binary $\ell$-tuples covering sequences that uses a single redundancy bit and meets this bound on $\ell$. Finally, we use a generalization of the de Bruijn graph to develop an upper bound for the cardinality of this set of sequences.

Another interesting family of sequences is introduced as a building block to our analysis of $\ell$-tuples covering sequences. For some $\ell$-tuple ${\boldsymbol{v}}$, we say that a sequence is a ${\boldsymbol{v}}$-avoiding sequence if it does not contain ${\boldsymbol{v}}$ as a window. Note that if ${\boldsymbol{v}}$ is the all-zero $\ell$-tuple, then this family of sequences is known as RLL sequences and was studied before, for example in [14, 20]. We study this family of sequences for any $\ell$-tuple ${\boldsymbol{v}}$.

The rest of this paper is organized as follows. In Section II we formally define the families of sequences studied in this paper and review several previous results. In Section III, we study the family of ${\boldsymbol{v}}$-avoiding sequences for any $\ell$-tuple ${\boldsymbol{v}}$. Based on these results, in Section IV we analyze the cardinality of $\ell$-tuples covering sequences and present an encoding scheme for $q=2$ which uses a single redundancy bit.

For two integers $i,k\in\mathbb{N}$ such that $i\leqslant k$ we denote by $[i,k]$ the set $\{i,\dots,k\}$ and use $[k]$ as a shorthand for $[0,k-1]$. We use the notation $\Sigma_{q}=\{0,1,\dots,q-1\}$ as the alphabet of finite size $q$. For simplicity, when $q=2$, we omit the parameter $q$ from this notation and similar ones.

Let $n\in\mathbb{N}$ and let ${\boldsymbol{w}}=(w_{0},\dots,w_{n-1})\in\Sigma_{q}^{n}$ denote a sequence of length $n$. For two positive integers $i$ and $k$ such that $i+k-1\leqslant n$, let ${\boldsymbol{w}}_{i,k}$ denote the substring $(w_{i},\dots,w_{i+k-1})$. Additionally, let Pref${}_{k}({\boldsymbol{w}})\triangleq{\boldsymbol{w}}_{0,k},$ Suff${}_{k}({\boldsymbol{w}})\triangleq{\boldsymbol{w}}_{n-k,k}$ denote the $k$-prefix, $k$-suffix of ${\boldsymbol{w}}$, respectively. The notation ${\boldsymbol{w}}\circ{\boldsymbol{v}}$ is the concatenation of ${\boldsymbol{w}}$ and another sequence ${\boldsymbol{v}}$, and ${\boldsymbol{w}}^{i}$ denotes the concatenation of ${\boldsymbol{w}}$ $i$ times, i.e., ${{\boldsymbol{w}}^{i}={\boldsymbol{w}}\circ{\boldsymbol{w}}^{i-1}}$. Let $W,V$ denote two sets of vectors over $\Sigma_{q}$. We denote the set $WV=\{{\boldsymbol{w}}\circ{\boldsymbol{v}}\mid{\boldsymbol{w}}\in W,{\boldsymbol{v}}\in V\}$ and the set $W^{i}$ to be $i$ concatenations of the set $W$. Finally, the redundancy of a set $A\subseteq\Sigma_{q}^{n}$ is defined as $\text{red}({A})\triangleq n-\log_{q}|A|$.

Note that the edges of $G_{q,\ell}$ correspond to the set of $q$-ary ${\ell\text{-tuples}}$, $\Sigma_{q}^{\ell}$.

Let ${\cal S}_{q}(\ell)$ denote the set of $q$-ary de Bruijn sequences of order $\ell$. The connection between Eulerian cycles in $G_{q,\ell}$ to de Bruijn sequences is as follows. In order to generate a sequence from a cycle, we pick any edge in the cycle and set its first entry as the start of the sequence. Then, we append to the sequence the first entry of each consecutive edge in the cycle. Finally, we append the $(\ell-1)$-suffix of the last edge of the cycle to form the whole sequence. Note that since each edge of $G_{q,\ell}$ can be picked as the first edge of the Eulerian cycle, a single cycle generates $q^{\ell}$ unique de Bruijn sequences.

Recall that the number of de Bruijn cycles in $G_{q,\ell}$ is $(q!)^{q^{\ell-1}}/{q^{\ell}}$. Since each de Bruijn cycle generates $q^{\ell}$ unique de Bruijn sequences of length $q^{\ell}+\ell-1$, it follows that $|{\cal S}_{q}(\ell)|=(q!)^{q^{\ell-1}}$. Therefore, the asymptotic rate of ${\cal S}_{q}(\ell)$ is

Note that when $q=2$, this asymptotic rate equals $1/2$. However, for $q\rightarrow\infty$, it approaches $1$.

Next, we introduce the main family of sequences that is discussed in this paper.

We denote the set of all $q$-ary $\ell$-tuples covering sequence over $\Sigma_{q}^{n}$ by ${\cal R}_{q}(n,\ell)$ and notate the size of such code by $r_{q}(n,\ell)\triangleq|{\cal R}_{q}(n,\ell)|$. For a window length that is a function of $n$, that is $\ell=f(n)$, we denote the asymptotic rate of ${\cal R}_{q}(n,f(n))$ by

Note the following connection between $\ell$-tuples covering sequences and de Bruijn sequences; if $n=q^{\ell}+\ell-1$, then the set ${\cal R}_{q}(n,\ell)$ is exactly the set of de Bruijn sequences ${\cal S}_{q}(\ell)$. Therefore, $\mathbb{R}_{q}(\ell)={\log_{q}(q!)}/{q}$ in this case. In Section IV we study the cardinality of ${\cal R}_{q}(n,\ell)$ for various sizes of $\ell$, i.e., for various functions $f(n)$. Moreover, we present an encoding algorithm for $q=2$ that uses a single redundancy bit.

In this section, we present the auxiliary family of ${\boldsymbol{v}}$-avoiding sequences that is used later in our analysis of $\ell$-tuples covering sequences in Section IV.

For a given $\ell$-tuple ${\boldsymbol{v}}$, we notate the size of this code by $a_{q}(n,{\boldsymbol{v}})\triangleq|{\cal A}_{q}(n,{\boldsymbol{v}})|$. Note that for ${\boldsymbol{v}}=0^{\ell}$, this family of sequences is the family of $(0,\ell-1)$-RLL sequences [20] (for integers $d,k$, a $(d,k)$-RLL sequence satisfies that the number of zeros between two consecutive ones is in the range $[d,k]$). These sequences were studied extensively in [14] for different functions $\ell=f(n)$.

We are motivated to study this family of sequences due to the following connection to the family of $\ell$-tuples covering sequences; a sequence ${\boldsymbol{s}}$ is an $\ell$-tuples covering sequence if and only if for every ${\boldsymbol{v}}\in\Sigma_{q}^{\ell}$, ${\boldsymbol{s}}$ is not a ${\boldsymbol{v}}$-avoiding sequence. This connection will be utilized later in order to encode and analyze the cardinality of ${\cal R}_{q}(n,\ell)$.

In this section, we focus on the main family of sequences discussed in this paper, $\ell$-tuples covering sequences. We study the cardinality of this set of sequences and present a lower bound on its asymptotic rate for various values of $\ell$. Then, we present an upper bound for $\ell$ such that the redundancy of the set of $\ell$-tuples covering sequences is at most one symbol. Later, we present an encoding algorithm for binary $\ell$-tuples covering sequences that uses a single redundancy bit that meets this bound on $\ell$. Finally, we use a generalization of the de Bruijn graph to develop an upper bound for the cardinality of this set of sequences.