# Error-Resilient Weakly Constrained Coding via Row-by-Row Coding

Prachi Mishra and Navin Kashyap  Department of Electrical Communication
Engineering
Indian Institute of Science, Bengaluru, Karnataka, India
Email: {prachimishra<EMAIL_ADDRESS>
###### Abstract

A weakly constrained code is a collection of finite-length strings over a
finite alphabet in which certain substrings or patterns occur according to
some prescribed frequencies. Buzaglo and Siegel (ITW 2017) gave a construction
of weakly constrained codes based on row-by-row coding, that achieved the
capacity of the weak constraint. In this paper, we propose a method to make
this row-by-row coding scheme resilient to errors.

##  I Introduction

In several applications where coding is required, it is necessary to prevent
or restrict the frequency of occurrence of specific patterns as substrings of
codewords. One such application area of much current interest is DNA-based
data storage systems [1],[2]. DNA has great potential as a data storage medium
because of its high density, physical compressibility, and stability over
extreme environmental conditions. A DNA molecule is a polymer formed by a long
chain of nucleotides. There are four types of nucleotides in such a chain,
which means that DNA strands can be viewed a long sequences over a 4-letter
alphabet. Repetitions of the same nucleotide, called the homopolymer run,
significantly increase the chance of synthesis and sequencing errors [3], [4].
Therefore, long homopolymer runs should be avoided in the design of DNA
molecules for storage purposes. Other applications where it is necessary to
restrict the frequencies of occurrence of certain patterns in codewords
include the suppression of patterning effect due to inter-symbol interference
[5],[6], and multi-level cell flash memory [7].

A constrained code is a set of finite-length sequences that completely forbid
certain unwanted patterns from appearing as substrings. A more relaxed notion
is that of a weakly constrained code, which imposes restrictions on the
frequencies of occurrence of certain patterns as substrings, without
necessarily forbdding them completely. Weak constraints can be more appealing
for applications such as DNA-based data storage, because strong constraints,
which entirely prohibit the occurrence of undesirable substrings, often incur
a significant rate penalty. There is a large body of literature on constrained
codes (see e.g., [8], [9], [10]), but weakly constrained codes — also called
semi-constrained codes — are relatively less explored [11],[12],[13],[14].

There is an extensive literature on making constrained codes error-resilient
by combining them with error-correcting codes — see [10, Chapter 9] for
references. However, to the best of our knowledge, there seems to be no prior
work on doing the same for weakly constrained codes. This paper attempts to
address this problem.

Specifically, we consider the weakly constrained coding scheme proposed by
Buzaglo and Siegel [14], which they have shown achieves the capacity of the
associated weak constraint. In their coding scheme, messages are first encoded
into a 2-dimensional array $W$ using row-by-row coding [15]. A weakly
constrained codeword $w$ is then formed by concatenating the columns of this
array in some order. The order of concatenation of columns is not _a priori_
fixed, but depends on the messages being encoded. At the time of decoding, the
decoder must first reconstruct the array $W$ from the codeword $w$. To do
this, it must infer from $w$ itself the order in which the columns of $W$ were
concatenated to form $w$. Errors affecting $w$ compromise the ability of the
decoder to correctly determine the order of concatenation of columns.

In this paper, we propose a modification to the coding scheme of [14]. Our
scheme uses row-by-row coding to encode messages into arrays whose columns can
always be concatenated in a _fixed_ order, while ensuring that the resulting
codeword $w$ respects the weak constraint. This removes the need for the
decoder to infer the order of concatenation from $w$, thus making the scheme
more resilient to errors. Our modified scheme also introduces less redundancy
than the original coding scheme of [14].

The remainder of this paper is structured as follows. We provide the necessary
definitions and notation in Section II. This section also contains a brief
description of the weakly constrained coding scheme of [14]. We present our
error-resilient weakly constrained coding scheme in Section III. Some of the
details of the coding scheme and its analysis are provided in appendices. We
make some concluding remarks in Section IV.

##  II Preliminaries

This section contains only the definitions and notations required for our
purposes. For details on how row-by-row coding schemes yield capacity-
achieving coding schemes for weakly constrained systems, we refer the reader
to the work of Buzaglo and Siegel [14].

A row-by-row coding scheme is associated with an $n$-integral Markov chain on
a primitive subgraph of a de Bruijn graph. We introduce these notions below.
For a positive integer $n$, we set $[n]:=\\{1,2,\ldots,n\\}$.

###  II-A Markov Chains

Let $G=(V,E,L)$ be a labelled directed graph, where $V$ and $E$ denote the
vertex and edge sets of $G$, respectively, and $L$ is the labelling function
defined over the edges $e\in E$. For an edge $e\in E$, we let $\sigma(e)$ and
$\tau(e)$ denote the initial and terminal vertex, respectively, of the edge. A
Markov chain $P$ on $G$ is a probability mass function over the edge set of
$G$, $P:E\rightarrow[0,1]$, such that $\sum_{e\in E}P(e)=1$. This induces a
probability mass function, $\pi$, on the vertex set $V$: for all $u\in V$,

$\pi(u):=\sum_{e\in E:\sigma(e)=u}P(e).$ (1)

A Markov chain is called _stationary_ if for all $u\in V$,

$\pi(u)=\sum_{e\in E:\tau(e)=u}P(e).$

Given a positive integer $n$, We call a stationary Markov chain _$n$
-integral_ if, for all edges $e\in E$, the number $P(e)n$ is an integer.

###  II-B de Bruijn Graphs

For integers $k\geq 1$ and $\mu\geq 2$, the $k^{\text{th}}$-order de Bruijn
graph $D_{k,\mu}$ is a labelled directed graph over an alphabet $\Sigma$ of
size $\mu$. Its vertex set $V_{k,\mu}$ is the set $\Sigma^{k}$. The edge set
$E_{k,\mu}$ is defined such that there exists a directed edge from vertex
$u=(u^{1},u^{2},\ldots,u^{k})$ to $v=(v^{1},v^{2},\ldots,v^{k})$ iff
$u^{i+1}=v^{i}$ for all $i\in[k-1]$. An edge $e$ from $u$ to $v$ gets the
label $L(e):=v^{k}$. Thus, the edge $e$ can be uniquely identified by a
$(k+1)$-tuple $e=(e^{1},e^{2},\ldots,e^{k+1})$, where $e^{i}=u^{i}$ for all
$i\in[k]$ and $e^{i+1}=v^{k}$. A first-order de Bruijn graph is shown in
Figure 1.

Figure 1: The de Bruijn graph $D_{1,2}$.

A directed graph $G$ is said to be _primitive_ if it satisfies the following
property for all sufficiently large integers $N$: for any ordered pair of
vertices $u$ and $v$ in $G$, there is a path of length $N$ from $u$ to $v$. As
an example, the primitive subgraphs of $D_{1,2}$ on the vertex set
$V_{1,2}=\\{0,1\\}$ are precisely those obtained from $D_{1,2}$ by deleting at
most one of the two self-loops.

###  II-C Row-By-Row Constrained Coding

Let $P$ be an $n$-integral stationary Markov chain on a primitive subgraph,
$G=(V,E,L)$, of $D_{k,\mu}$. We will assume that $P$ assigns positive
probabilities to all the edges of $G$. Each edge $e$ of $G$ can then be viewed
as having $P(e)n$ copies, which we call the _multiplicity_ of that edge.
Listing out the vertices of $G$ in some arbitrary (but fixed) order
$v_{1},v_{2},\ldots,v_{|V|}$, we define $n_{l}:=\pi(v_{l})n$ for all
$l\in[|V|]$, where $\pi(\cdot)$ is as defined in (1). Note that $n_{l}$ is an
integer for all $l$. We define a $k\times n$ matrix $U_{\pi}$ as follows: each
of the first $n_{1}$ columns is equal to the vertex $v_{1}$, each of the next
$n_{2}$ columns is equal to the vertex $v_{2}$, and so on, ending in the last
$n_{|V|}$ columns all being equal to the vertex $v_{|V|}$. Let $S(G)$ denote
the set of all finite-length sequences over the alphabet $\Sigma$ that can be
obtained by concatenating the labels of edges along (directed) paths in $G$.
In other words, $S(G)$ consists of all possible words of the form
$(L(e_{1}),L(e_{2}),\ldots,L(e_{t}))$, $t=1,2,3,\ldots$, where the sequence of
edges $e_{1},e_{2},\ldots,e_{t}$ forms a (directed) path in $G$.

For any $K\geq k+1$, a _$(G,P,n)$ -array_ is a $K\times n$ array $W$ having
the following properties:

  * (A1)

each column of $W$ is a sequence in $S(G)$;

  * (A2)

in any $(k+1)\times n$ sub-array $W^{\\#}$ formed by $k+1$ consecutive rows of
$W$, each edge $e$ of $G$ occurs as a column of $W^{\\#}$ exactly $P(e)n$
times.

Note that these properties imply that in any $k\times n$ sub-array
$W^{{\ddagger}}$ formed by $k$ consecutive rows of $W$, each vertex $v_{l}$ of
$G$ occurs as a column of $W^{{\ddagger}}$ exactly $n_{l}$ times.

A row-by-row constrained coding scheme is a means of encoding messages into a
$(G,P,n)$-array.

###  II-D Weakly Constrained Coding

For a positive integer $N$, a _$(G,P,N)$ -weakly constrained coding scheme_ is
a method of encoding messages into (and subsequently decoding them from)
length-$N$ words $w\in S(G)$ with the property that each edge $e$ in $G$
occurs in $w$ approximately $P(e)N$ number of times.

Buzaglo and Siegel [14] proposed such a weakly constrained coding scheme using
row-by-row coding. Their row-by-row coding scheme is an encoding of a sequence
of $m$ messages into a $(G,P,n)$-array $W$ of size $(k+b\log n+m+N_{G})\times
n$, having some additional properties:

  * (B1)

the first $k$ rows of $W$ constitute the fixed matrix $U_{\pi}$ defined above;

  * (B2)

the first $k+b\log n$ rows of $W$ (where $b$ is some constant) constitute a
fixed matrix $\hat{U}_{\pi}$ with all distinct columns;

  * (B3)

the next $m$ rows below $\hat{U}_{\pi}$ encode the $m$ messages, one message
per row;

  * (B4)

the last $N_{G}$ rows (where $N_{G}$ is a constant that depends only on the
graph $G$) are chosen so that the columns of $W$ can be stitched together in
some order, to form a long word in $S(G)$.

To satisfy Property (B3), the messages are first encoded into codewords of a
certain constant-composition code $C_{\text{rbr}}$, and each codeword is then
inserted in a prescribed manner into a row of the $(G,P,n)$-array $W$ — see
Appendix A.

Property (B4) requires further explanation. For two words
$w_{1}=(w_{1}^{1},w_{1}^{2},\ldots,w_{1}^{\ell_{1}})$ and
$w_{2}=(w_{2}^{1},w_{2}^{2},\ldots,w_{2}^{\ell_{2}})$ over $\Sigma$, of
lengths $\ell_{1},\ell_{2}\geq k$, we say that $w_{1}$ is _extendable_ by
$w_{2}$ if the last $k$ entries of $w_{1}$ are equal to the first $k$ entries
of $w_{2}$. The result of extending $w_{1}$ by $w_{2}$ is word of length
$\ell_{1}+\ell_{2}-k$:

$w_{1}||w_{2}:=(w_{1}^{1},w_{1}^{2},\ldots,w_{1}^{\ell_{1}},w_{2}^{k+1},w_{2}^{k+2},\ldots,w_{2}^{\ell_{2}})$
(2)

It can be readily verified that if two words $w_{1},w_{2}\in S(G)$ are such
that $w_{1}$ is extendable by $w_{2}$, then $w_{1}||w_{2}\in S(G)$. Moreover,
if an edge $e\in E$ occurs as a substring $t_{1}$ times in $w_{1}$ and $t_{2}$
times in $w_{2}$, then it occurs as a substring $t_{1}+t_{2}$ times in
$w_{1}||w_{2}$.

Now, let $W_{1},W_{2},\ldots,W_{n}$ be the $n$ columns of an $M\times n$
$(G,P,n)$-array $W$, listed in order from left to right. Suppose that there
exists a permutation $\rho:[n]\rightarrow[n]$, such that for all
$j\in[n-1],W_{\rho(j)}$ is extendable by $W_{\rho(j+1)}$. Then,

$w=W_{\rho(1)}||W_{\rho(2)}||\cdots||W_{\rho(n)}.$

is a word of length $N=nM-(n-1)k$ belonging to $S(G)$, in which each edge $e$
of $G$ occurs exactly $P(e)n(M-k)=P(e)(N-k)$ times.

Lemma 2 in [14] says that if for all $e\in E$, we have $P(e)n\geq|V|$, then it
is always possible to find some $N_{G}$ rows to satisfy Property (B4). More
precisely, the addition of these $N_{G}$ rows yields a permutation
$\rho:[n]\to[n]$ such that the $n$ columns of the resulting array $W$ can be
stitched together as in (2) to form a word of length $N=(b\log n+m+N_{G})n+k$
in which every pattern $e\in E$ occurs exactly $P(e)(N-k)$ times. We summarize
this in the form of a proposition.

######  Proposition 1 (Corollary 1 in [14]).

If for all $e\in E,P(e)n\geq|V|$ holds, then there exists a constant $b$ that
depends only on $G$ and the Markov chain $P$, such that one can encode $m$
messages from $C_{\mathrm{rbr}}$ into a length $N=(b\log n+m+N_{G})n+k$
codeword $w\in S(G)$, in which every pattern $e\in E$ occurs exactly
$P(e)(N-k)$ times.

This method of encoding $m$ messages into a length-$N$ codeword $w\in S(G)$ as
above constitutes the encoder of a weakly constrained coding scheme.

######  Example 1.

Let $G$ be the subgraph of $D_{1,2}$ shown in the figure below.

Consider the $n$-integral stationary Markov chain on $G$ given by
$P(00)=0.5,P(01)=P(10)=0.25$, and $n=8$. For this graph and Markov chain, we
give a $9\times 8$ array $W$ that encodes $m=2$ messages using the row-by-row
coding scheme of Buzaglo and Siegel [14]:

0 |  0 |  0 |  0 |  0 |  0 |  1 |  1
---|---|---|---|---|---|---|---
0 |  0 |  0 |  0 |  1 |  1 |  0 |  0
0 |  0 |  0 |  1 |  0 |  0 |  1 |  0
0 |  0 |  1 |  0 |  0 |  1 |  0 |  0
0 |  1 |  0 |  1 |  0 |  0 |  0 |  0
1 |  0 |  0 |  0 |  0 |  1 |  0 |  0
0 |  0 |  0 |  0 |  0 |  0 |  1 |  1
0 |  0 |  1 |  1 |  0 |  0 |  0 |  0
1 |  0 |  0 |  0 |  0 |  1 |  0 |  0

The first five rows of $W$ constitute $\hat{U}_{\pi}$ (of which the first row
is $U_{\pi}$), followed by two rows representing messages, and the final
$N_{G}=2$ rows needed to stitch together the columns. The columns can be
stitched together in the order shown below to form a length-$65$ codeword
$w\in S(G)$:

$w=W_{1}||W_{7}||W_{2}||W_{3}||W_{4}||W_{5}||W_{6}||W_{8}$.

The codeword $w$ is of length $N=65$, in which the pattern $00$ occurs exactly
$P(00)(N-k)=32$ times, and the patterns $01$ and $10$ each appear exactly
$P(01)(N-k)=P(10)(N-k)=16)=32$ times.

Decoding requires recreating the $m$ rows of the array $W$ that constitute the
_payload_ , i.e., the rows of $W$ that contain the messages. To do this, the
decoder needs to know the order in which the columns of $W$ are stitched
together to form the codeword $w$. It is able to infer this from the matrix
$\hat{U}_{\pi}$, which is static and known to both encoder and decoder. The
distinct columns of $\hat{U}_{\pi}$ act as unique identifiers for the columns
of $W$. But this feature has the drawback that errors affecting the rows of
$\hat{U}_{\pi}$ can potentially result in incorrect payload extraction by the
decoder — see Example 4 in Appendix B. On the other hand, any error in the
$N_{G}$ rows added after the payload leads to an incorrect reconstruction of
the $W$ matrix, but it does not affect the payload extraction. Therefore, if
there is a way to avoid or correct the errors in the rows of $\hat{U}_{\pi}$,
we can successfully extract the payload rows. Errors directly affecting the
payload rows can be corrected using known error-correction techniques for
constant-composition codes.

##  III Error-Resilient Weakly Constrained Coding

In this section, we propose a method to keep the order of concatenation of
columns of $W$ constant, i.e., independent of the payload. In this way, we do
not need the mechanism used in [14] of adding extra rows to create unique
identifiers for the columns of $W$. This approach makes the construction of
weakly constrained codes via row-by-row coding error-resilient. The number of
redundant rows added by the method of [14] is $N_{G}+O(\log n)$, while our
method adds only a fixed number of rows after the payload, independent of $n$.
Our proposed method also removes the additional condition of $P(e)n\geq|V|$
required by the scheme in [14]. However, at this stage, our results are
applicable only to primitive subgraphs $G$ of the first-order de Bruijn graph
$D_{1,2}$.

###  III-A Our Main Results

Let $G$ be a primitive subgraph of $D_{1,2}$, with vertex set $\\{0,1\\}$.
Thus, $G$ is a graph obtained by removing at most one of the two self-loops in
$D_{1,2}$. In particular, the edges $01$ and $10$ remain in $G$. Consider an
$n$-integral stationary Markov chain on $P$ that assigns positive probability
to all edges in $G$. Additionally, if $e$ is a self-loop of $D_{1,2}$ that is
not in $G$, we set $P(e)=0$. Stationarity of $P$ and primitivity of $G$ imply
that $0<P(01)=P(10)<0.5$, and $\max\bigl{(}P(00),P(11)\bigr{)}>0$.

As in the scheme of [14], we encode $m$ messages into a $(G,P,n)$-array $W$
using row-by-row coding. The first row of the array is the $1\times n$ matrix
$U_{\pi}$ which, as per its structure detailed in Section II-C, has vertex
$v_{1}:=0$ appearing $n_{1}$ times as a block, followed by vertex $v_{2}:=1$
appearing $n_{2}$ times. The next $m$ rows of $W$ constitute the payload of
$m$ messages encoded using the code $C_{\text{rbr}}$, as described in Appendix
A. At this stage, the $(m+1)$-th row of $W$ has the $n_{1}$ and $n_{2}$ copies
of the vertices $v_{1}$ and $v_{2}$, respectively, arranged in an arbitrary
order. Our goal is to transition from this arbitrary arrangement of vertices
to a “target” row at the bottom of $W$ having a pre-determined arrangement of
vertices, by adding only a fixed number of intermediate rows (see Figure 2).
The number, $Z$, of rows to be added (including the target row) solely depends
on the parameters of the Markov chain. The arrangement of vertices we would
like in the target row is $\sigma_{\text{left}}(U_{\pi})$, which is simply
$U_{\pi}$ cyclically shifted to the left by one position. With this as the
bottom row of the array $W$, we can stitch together the columns consecutively
in the order of their appearance in the array to form a codeword in $S(G)$ of
length $N=(m+Z)n+1$, in which each edge $e$ of $G$ appears exactly $P(e)(N-1)$
times. Our main results are the following theorem and its corollary.

######  Theorem 1.

With $G$ and $P$ as above, let $p=\max\bigl{(}P(00),P(11)\bigr{)}$ and
$q=\min\bigl{(}P(00),P(11)\bigr{)}$. Let $\mathbf{r}$ be any $n$-tuple
consisting of $n_{1}$ occurrences of $v_{1}$ and $n_{2}$ occurrences of
$v_{2}$ in some arbitrary order. We can construct a $(G,P,n)$-array with $Z+1$
rows in which the first row is $\mathbf{r}$ and the last row is
$\sigma_{\mathrm{left}}(U_{\pi})$, where

$Z=\max\Bigl{(}2\bigl{(}2+\bigl{\lceil}{\textstyle\frac{P(10)+q-p}{p}}\bigr{\rceil}\bigl{)},2\bigl{(}1+\bigl{\lceil}{\textstyle\frac{q}{2P(01)}}\bigr{\rceil}\bigl{)}\Bigl{)}.$

We remark that the statement of the theorem will hold for any choice of the
last row that has $n_{1}$ occurrences of $v_{1}$ and $n_{2}$ occurrences of
$v_{2}$.

######  Corollary 1.

Given an $n$-integral stationary Markov chain $P$ on a primitive subgraph,
$G$, of $D_{1,2}$, there exists a constant $Z$ that depends only on $P$, such
that one can injectively encode $m$ messages from $C_{\mathrm{rbr}}$ into a
length $N=(m+Z)n+1$ codeword $w\in S(G)$, in which every pattern $e\in E$
occurs exactly $P(e)(N-1)$ times.

Figure 2: A $(G,P,n)$-array of size $(1+m+Z)\times n$, with first row
$U_{\pi}$, $m$ rows of payload, and last row
$\sigma_{\mathrm{left}}(U_{\pi})$.

Since the corollary is a direct consequence of the discussion prior to the
statement of Theorem 1, we will devote the remainder of this section to a
proof of the theorem. Leveraging the symmetry of the graph $D_{1,2}$, we may
assume that $P(00)\geq P(11)$. Due to space constraints, we provide only a
sketch of the proof here, leaving the details to Appendix C.

###  III-B Proof Sketch for Theorem 1

Our problem is one of transitioning from a top row
$\mathbf{r}=(r^{j})_{j\in[n]}$ to a bottom row
$\sigma_{\mathrm{left}}(U_{\pi})=:\mathbf{s}=(s^{j})_{j\in[n]}$ in a fixed
number of steps. If $r^{j}=v_{l}$ and $s^{j}=v_{l^{\prime}}$ for some
$j\in[n]$ and $l,l^{\prime}\in\\{1,2\\}$, then the transition from $r^{j}$ to
$s^{j}$ must be made via a path from $v_{l}$ to $v_{l}^{\prime}$ in $G$. We
call such a transition a _$v_{l}$ –$v_{l^{\prime}}$ flow_ (see Figure 2), and
the number of $v_{l}$–$v_{l^{\prime}}$ flows needed to transition from
$\mathbf{r}$ to $\mathbf{s}$ is denoted by $M_{v_{l}v_{l^{\prime}}}$. Since
$M_{10}+M_{11}$ is the number of flows starting from a vertex $1$ (i.e.,
$v_{2}$) in $\mathbf{r}$, we must have $M_{10}+M_{11}=n_{2}$, which is the
number of occurrences of $v_{2}$ in $\mathbf{r}$. Similarly, considering that
flows must terminate in vertices in $\mathbf{s}$, we have
$M_{01}+M_{11}=n_{2}$. So, we have $M_{01}=M_{10}=n_{2}-M_{11}$. Also, the
equality $M_{00}+M_{01}=n_{1}$ yields $M_{00}=n_{1}-n_{2}+M_{11}$. Thus,
setting $M_{11}=M$, we can express all the other $M_{**}$ in terms of $M$.
This means that we can parametrize our problem by the number $M$.

We divide our problem into two cases: $M\geq P(11)n$ and $M<P(11)n$. For the
case $M\geq P(11)n$, our problem can be solved by adding a single intermediate
row, when $M$ satisfies a further lower bound (see Eq. (3)). Otherwise, when
$M$ does not meet the lower bound in (3), we propose a technique called
“$1$–$1$ boosting” to raise the number of $1$–$1$ flows to a value
$M^{\prime}>M$. We use this technique repeatedly till we achieve the lower
bound. When $M<P(11)n$, we perform $1$–$1$ boosting repeatedly to raise the
number of $1$–$1$ flows to a value $M^{\prime}\geq P(11)n$, so that we are
back to the previous case.

Before proceeding further, we introduce some convenient notation. Let
$n^{*}:=P(11)n$ denote the multiplicity of the $11$ edge. The multiplicities
of the other edges in $G$ can be expressed in terms of $n^{*}$ as follows:
$P(01)n=P(10)n=n_{2}-n^{*}$ and $P(00)n=n_{1}-(n_{2}-n^{*})$.

Case 1: $M\geq n^{*}$.

Flow |  $\\#$ occurrences of the flow | Path $\mathbf{1}$ |  $\\#$ times Path $\mathbf{1}$ is used | Path $\mathbf{2}$ |  $\\#$ times Path $\mathbf{2}$ is used
---|---|---|---|---|---
$0$–$0$ | $n_{1}-(n_{2}-M)$ | $0\rightarrow 0\rightarrow 0$ | $n_{1}-2n_{2}+M+n^{*}$ | $0\rightarrow 1\rightarrow 0$ | $n_{2}-n^{*}$
$1$–$0$ | $n_{2}-M$ | $1\rightarrow 0\rightarrow 0$ | $n_{2}-M$ | $1\rightarrow 1\rightarrow 0$ | Zero
$0$–$1$ | $n_{2}-M$ | $0\rightarrow 0\rightarrow 1$ | $n_{2}-M$ | $0\rightarrow 1\rightarrow 1$ | Zero
$1$–$1$ | $M$ | $1\rightarrow 1\rightarrow 1$ | $n^{*}$ | $1\rightarrow 0\rightarrow 1$ | $M-n^{*}$
Table I: Two-step transition

The basic idea here is a two-step transition that attempts to go from
$\mathbf{r}$ to $\mathbf{s}$ in two steps, i.e., via one intermediate row.
Recall that when the number of $1$–$1$ flows is $M$, the numbers of $0$–$0$,
$0$–$1$ and $1$–$0$ flows are $n_{1}-n_{2}+M$, $n_{2}-M$ and $n_{2}-M$,
respectively. (In particular, this means that $M\geq n_{2}-n_{1}$ must hold,
as the number of $0$–$0$ flows cannot be negative.)

####  III-B1 Two-step transition

The two-step transition method is summarized in Table I. For each type of
flow, Table I gives two paths of length $2$ that can realize that flow, along
with the number of times that each of these paths must be used. Thus, for
example, to realize the $n_{1}-(n_{2}-M)$ instances of the $0$–$0$ flow that
occur in the transition from $\mathbf{r}$ to $\mathbf{s}$, we must use Path 1
($0\to 0\to 0$) exactly $n_{1}-2n_{2}+M+n^{*}$ times, and Path 2 ($0\to 1\to
0$) exactly $n_{2}-n^{*}$ times. The middle vertices of these paths are the
vertices that fill up the intermediate row of the two-step transition. This
results in a $3\times n$ array $W^{\prime}$ with first row $\mathbf{r}$, last
row $\mathbf{s}$, and an intermediate row constructed via Paths 1 and 2 of the
flows, _provided that the expressions for the usage numbers for each path are
all non-negative and do not exceed the multiplicities of the edges that are in
that path_. In particular, we must have $n_{1}-2n_{2}+M+n^{*}\geq 0$ and
$n_{2}-M\leq P(00)n$. Both conditions reduce to the lower bound

$M\geq P(11)n+P(10)n-P(00)n,$ (3)

which gives a sufficient condition for the two-step transition method to work.
When this condition is met, the path usage numbers given in Table I ensure
that the resulting $3\times N$ array $W^{\prime}$ is a valid $(G,P,n)$-array.

####  III-B2 $1$–$1$ boosting

In problem instances where $M$ does not meet the lower bound in (3), we
implement a method of increasing $M$ by augmenting the overall number of steps
required for the $\mathbf{r}$-to-$\mathbf{s}$ transition. We call this process
of raising the number ($M$) of $1$–$1$ flows as “$1$–$1$ boosting”. This
technique involves creating an intermediate transition problem by introducing
a new row, $\mathbf{r}^{\prime}$, below the top row $\mathbf{r}$ and another
new row, $\mathbf{s}^{\prime}$, above the target bottom row $\mathbf{s}$. We
refer to adding one row below $\mathbf{r}$ as the “launch step” and one above
$\mathbf{s}$ as the “landing step”.

Our $1$–$1$ boosting technique is described by the three steps below. An
example illustrating this procedure is provided in Appendix C-A.

Step $1$: Start by filling the entries in $\mathbf{r}^{\prime}$ and
$\mathbf{s}^{\prime}$ corresponding to the $1$–$1$ flows in the
$\mathbf{r}$-to-$\mathbf{s}$ transition. Use the $11$ edge $n^{*}$ times in
the launch step and in the landing step; and use the $10$ edge (resp. $01$
edge) in the launch step (resp. landing step) $M-n^{*}$ times.

Step $2$: Next, fill the entries in $\mathbf{r}^{\prime}$ and
$\mathbf{s}^{\prime}$ corresponding to the $0$–$0$ flows. Use the $01$ edge
$P(01)n$ times in the launch step, and use the $10$ edge in the landing step
for the columns in which the $01$ edge is used in the launch step.

Step $3$: Fill the remaining vacant columns in the launch and landing steps,
exhausting all the remaining available edges at both steps.

Let $M^{\prime}$ be the number of times the $1$–$1$ flow occurs in the
intermediate $\mathbf{r}^{\prime}$-to-$\mathbf{s}^{\prime}$ transition
problem. A small calculation shows that

$M^{\prime}=M+P(00)n.$ (4)

Thus, if the $1$–$1$ boosting method is iteratively used $t$ times, then at
the end of the $t$ iterations, the number of times the $1$–$1$ flow occurs in
the intermediate transition problem is $M^{\prime}=M+tP(00)n$. We will use
this in Appendix C-C, where we compute the overall number of steps it takes to
solve the $\mathbf{r}$-to-$\mathbf{s}$ transition problem.

Case 2: $M<n^{*}$. We defer this case to Appendices C-B and C-C.

######  Example 2.

For the graph and the Markov chain from Example 1, we give a $7\times 8$ array
$W$ that encodes $m=2$ messages using our row-by-row coding scheme.

0 |  0 |  0 |  0 |  0 |  0 |  1 |  1
---|---|---|---|---|---|---|---
1 |  0 |  0 |  1 |  0 |  0 |  0 |  0
0 |  0 |  0 |  0 |  0 |  0 |  1 |  1
0 |  0 |  1 |  0 |  1 |  0 |  0 |  0
0 |  0 |  0 |  0 |  0 |  1 |  1 |  0
0 |  0 |  0 |  1 |  1 |  0 |  0 |  0
0 |  0 |  0 |  0 |  0 |  1 |  1 |  0

The first row of the array is $U_{\pi}$, followed by $m=2$ rows corresponding
to the payload, and $Z=4$ additional rows added to execute the transition from
the third row, $\mathbf{r}$, to the target row
$\mathbf{s}=\sigma_{\mathrm{left}}(U_{\pi})$. Note that, the target row
$\mathbf{s}$ is actually reached in two steps from $\mathbf{r}$, but the
decoder expects a fixed number ($Z=4$) of additional rows as per the coding
scheme summarized in Theorem 1. So, we take two more steps to transition from
$\mathbf{s}$ to itself. This transition is accomplished by the two-step method
described in Section III-B1.

The columns of $W$ can be concatenated in the order of their appearance, i.e.,

$w=W_{1}||W_{2}||W_{3}||W_{4}||W_{5}||W_{6}||W_{7}||W_{8}$.

The resulting $w$ is a codeword in $S(G)$ of length $N=(Z+m)n+1=49$ that does
not have $11$ as a substring, but in which $00$, $01$ and $10$ appear as a
substring exactly $24$, $12$ and $12$ times, respectively.

##  IV Concluding Remarks

In this paper, we proposed a modification of the weakly constrained coding
scheme of Buzaglo and Siegel [3]. We argued that our modified coding scheme is
more error-resilient, and also introduces less redundancy, than the original
scheme. However, our scheme can only be applied to weak constraints defined by
Markov chains on primitive subgraphs of the first-order de Bruijn graph
$D_{1,2}$. Work is in progress on extending our techniques so as to be
applicable to weak constraints defined on higher-order de Bruijn graphs.

## Acknowledgement

This work was supported in part by a Qualcomm Innovation Fellowship awarded to
the second author.

## References

  * [1] G. M. Church, Y. Gao, and S. Kosuri, “Next-generation digital information storage in DNA,” Science, vol. 337, no. 6102, pp. 1628–1628, 2012.
  * [2] N. Goldman, P. Bertone, S. Chen, C. Dessimoz, E. M. LeProust, B. Sipos, and E. Birney, “Towards practical, high-capacity, low-maintenance information storage in synthesized DNA,” Nature, vol. 494, no. 7435, pp. 77–80, 2013.
  * [3] J. Bornholt, R. Lopez, D. M. Carmean, L. Ceze, G. Seelig, and K. Strauss, “A DNA-based archival storage system,” in Proceedings of the Twenty-First International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 637–649, 2016.
  * [4] M. G. Ross, C. Russ, M. Costello, A. Hollinger, N. J. Lennon, R. Hegarty, C. Nusbaum, and D. B. Jaffe, “Characterizing and measuring bias in sequence data,” Genome biology, vol. 14, pp. 1–20, 2013.
  * [5] A. Shafarenko, A. Skidin, and S. K. Turitsyn, “Weakly-constrained codes for suppression of patterning effects in digital communications,” IEEE Transactions on Communications, vol. 58, no. 10, pp. 2845–2854, 2010.
  * [6] A. Shafarenko, K. S. Turitsyn, and S. Turitsyn, “Skewed coding for suppression of pattern-dependent errors,” in 2005 31st European Conference on Optical Communication, ECOC 2005, vol. 2, pp. 193–194, IET, 2005.
  * [7] Y. Liu and P. H. Siegel, “Shaping codes for structured data,” in 2016 IEEE Global Communications Conference (GLOBECOM), pp. 1–6, IEEE, 2016.
  * [8] B. Marcus, R. M. Roth, and P. H. Siegel, “Constrained systems and coding for recording channels,” in Handbook of Coding Theory (R. Brualdi, C. Huffman, and V. Pless, eds.), Elsevier, 1998.
  * [9] K. A. S. Immink, Codes for Mass Data Storage Systems.  Shannon Foundation Publisher, 2004.
  * [10] B. H. Marcus, R. M. Roth, and P. H. Siegel, “An introduction to coding for constrained systems.”  lecture notes.
  * [11] B. H. Marcus and R. M. Roth, “Improved Gilbert-Varshamov bound for constrained systems,” IEEE Transactions on Information Theory, vol. 38, no. 4, pp. 1213–1221, 1992.
  * [12] K. A. S. Immink, “Weakly constrained codes,” Electronics Letters, vol. 33, no. 23, pp. 1943–1943, 1997.
  * [13] O. Elishco, T. Meyerovitch, and M. Schwartz, “Semiconstrained systems,” IEEE Transactions on Information Theory, vol. 62, no. 4, pp. 1688–1702, 2016.
  * [14] S. Buzaglo and P. H. Siegel, “Weakly constrained codes via row-by-row coding,” in 2017 IEEE Information Theory Workshop (ITW), pp. 151–155, IEEE, 2017.
  * [15] I. Tal, T. Etzion, and R. M. Roth, “On row-by-row coding for 2-D constraints,” IEEE Transactions on Information Theory, vol. 55, no. 8, pp. 3565–3576, 2009.

##  Appendix A Row-By-Row Constrained Coding

The row–by–row encoding scheme encodes a sequence of $m$ messages
$M_{1},M_{2},\ldots,M_{m}$ into $m$ rows below the $k$ rows of the $U_{\pi}$
matrix defined in section II-C. This gives us a resultant $(G,P,n)$-array $W$
of order $(k+m)\times n$, with row index $i$ running from $-k+1\leq i\leq m$
and column index $j\in[n]$.
The messages are encoded into rows such that the following conditions are
satisfied:
(i) Every message $M_{i}:i\in[m]$ is encoded into a unique $n$ length vector,
which is stored in the row $W_{i}$.
(ii) For $i_{1},i_{2}\in[m]$, if $i_{1}\leq i_{2}$ then, $W_{i_{1}}$ will be
encoded before $W_{i_{2}}$ .
(iii) For every edge $e\in E$ and $\forall i\in[m]$, the edge $e$ appears as a
column of the rows $W_{i-k},W_{i-k+1},\ldots,w_{i}$ exactly $P(e)n$ times.

To implement the row-by-row coding, we encode the input messages using a
constant-weight code of the form,

$C_{\text{rbr}}=C_{1}\times C_{2}\times\ldots\times C_{|V|}$ (5)

where,

$C_{l}=\\{w\in\Sigma^{n_{l}}:\forall\alpha\in\Sigma,\alpha\text{ appears in
$w$ }P(v_{l}\alpha)n\text{ times}\\}$ (6)

If $M_{i}$ is encoded into a codeword $\mathbf{c}\in
C_{rbr}:\mathbf{c}=c_{1}c_{2}\ldots c_{|V|}$, where $c_{l}\in C_{l}:\forall
l\in[|V|]$, then $c_{l}$ is stored in $W_{i}$ ($i^{th}$ row of $W$), in the
$n_{l}$ positions of $j$ for which
$W_{i-k,j},W_{i-k+1,j},\ldots,W_{i-1,j}=v_{l}$. This implementation satisfies
the properties of the row-by-row weakly constrained coding scheme.

######  Example 3.

Let $G$ be the graph shown in Figure 3, representing the "no-$11$" constrained
system. $G$ is a primitive subgraph of $D_{1,2}$. Let the $n$-integral
stationary Markov chain on $G$ is $P(00)=0.5,P(01)=P(10)=0.25$ and $n=8$.
Hence, the state probability mass function is $\pi(0)=0.75,\pi(1)=0.25$, and
$n_{0}=6,n_{1}=2$.

Figure 3: The graph $G=(V,E,L)$

According to the description given by the row-by-row coding scheme,
$U_{\pi}=00000011$. The constant weight codeword, $C_{\text{rbr}}=C_{1}\times
C_{2}$

$C_{1}=x\in\\{0,1\\}^{6}:\begin{tabular}[]{l}\\\ $1$ appears in $x$ two
times\\\ $0$ appears in $x$ four times\end{tabular}$

$C_{2}=x\in\\{0,1\\}^{2}:\hskip 5.69046pt0$ appears in $x$ two times

The codewords $c=10010000,\hat{c}=00001100\in C_{rbr}$ are encoded into the
$W$ matrix.

0 |  0 |  0 |  0 |  0 |  0 |  1 |  1
---|---|---|---|---|---|---|---
1 |  0 |  0 |  1 |  0 |  0 |  0 |  0
0 |  0 |  0 |  0 |  0 |  0 |  1 |  1

The first row is $U_{\pi}$. In the second row, the first six entries of
codeword $c$ are encoded below zeroes in the row $W_{0}$, and the last two
entries of the codeword $c$ are encoded below ones in $W_{0}$. In the third
row, the first six entries of codeword $\hat{c}$ are encoded below zeroes in
the row $W_{1}$ and the last two entries of the codeword $\hat{c}$ are encoded
below ones in $W_{1}$. Every column belongs to the constrained code, i.e.,
every column follows the "no-11 constraint". Every edge $e\in E:\\{0,1\\}^{2}$
occurs as a column of two consecutive rows, exactly $P(e)n$ times.

##  Appendix B Incorrect Payload extraction

######  Example 4.

The $\hat{U}_{\pi}$ for the $9\times 8$ array $W$ obtained in Example 1 are
tabulated below.

Columns |  Markers
---|---
$B_{1}$ |  $00000$
$B_{2}$ |  $00001$
$B_{3}$ |  $00010$
$B_{4}$ |  $00101$
$B_{5}$ |  $01000$
$B_{6}$ |  $01010$
$B_{7}$ |  $10100$
$B_{8}$ |  $10000$

If $W_{4,5}$ and $W_{4,6}$ entries of the $W$ matrix are flipped, it results
in an exchange of the markers for columns $B_{5}$ and $B_{6}$, leading to an
erroneous extraction of the payload. Consequently,
$c^{\prime}=10100000,\hat{c}^{\prime}=00001100$ (see the correct codeword in
Example 3). If a single entry $W_{2,1}$ is flipped, the column markers for
$B_{1}$ and $B_{5}$ become identical, leading to two possible reconstructions
of the payload.

##  Appendix C Proof details

###  C-A Example of $1$–$1$ Boosting in the Case of $M\geq n^{*}$

######  Example 5.

Let $G$ be the first order de Bruijn graph shown in figure 1. Consider the
$n$-integral stationary Markov chain on $G$ given by
$P(10)=P(01)=0.4,P(00)=P(11)=0.1$. For $n=10$, we have $n_{1}=5\text{ and
}n_{2}=5,\text{ and }n^{*}=P(11)n=1$. The initial two-step problem instance is
shown in Table II. We have two $1$–$1$ flows in our initial two-step problem
instance. The transition method given in Table I will be valid only if
$M\geq\max(P(11)n,P(11)n+P(10)n-P(00)n)=4$. As $M\geq n^{*}$, we employ
$1$–$1$ boosting for this case. The intermediate transition problem after one
iteration of the $1$–$1$ boosting procedure is displayed in Table III. After
boosting, we obtain three $1$–$1$ flows in the intermediate transition
problem. We can repeat this process for one more iteration to raise the number
of $1$–$1$ flows to $4$.

$1$ | $1$ | $1$ | $0$ | $1$ | $1$ | $0$ | $0$ | $0$ | $0$
---|---|---|---|---|---|---|---|---|---
|  |  |  |  |  |  |  |  |
$0$ | $0$ | $0$ | $0$ | $1$ | $1$ | $1$ | $1$ | $1$ | $0$
Table II: Before $1$–$1$ boosting $1$ | $1$ | $1$ | $0$ | $1$ | $1$ | $0$ | $0$ | $0$ | $0$
---|---|---|---|---|---|---|---|---|---
$0$ | $0$ | $0$ | $1$ | $1$ | $0$ | $1$ | $1$ | $1$ | $1$
|  |  |  |  |  |  |  |  |
$1$ | $1$ | $1$ | $1$ | $1$ | $0$ | $0$ | $0$ | $0$ | $0$
$0$ | $0$ | $0$ | $0$ | $1$ | $1$ | $1$ | $1$ | $1$ | $0$
Table III: After one iteration of $1$–$1$ boosting

###  C-B $1$–$1$ Boosting in the Case of $M<n^{*}$

In the instances where $M<n^{*}$, we perform $1$–$1$ boosting to raise the
number of $1$–$1$ flows $M$, to a value $M^{\prime}\geq n^{*}$. This case is
handled in two ways.
When $P(11)n-M\geq P(10)n$, perform the following steps :
Step 1: Start by filling entries in $\mathbf{r}^{\prime}$ and
$\mathbf{s}^{\prime}$ corresponding to $1$–$1$ flow in $\mathbf{r}$ to
$\mathbf{s}$ transition. Use $11$ edge, $M$ times in the launch step and the
landing step.
Step 2: Next, fill the entries in $\mathbf{r}^{\prime}$ and
$\mathbf{s}^{\prime}$ corresponding to $1$–$0$ flow in $\mathbf{r}$ to
$\mathbf{s}$ transition with the remaining $11$ edges ($P(11)n-M$) the launch
step and use $10$ edge in the landing step.
Step 3: Fill the entries in $\mathbf{r}^{\prime}$ and $\mathbf{s}^{\prime}$
corresponding to $0$–$1$ flow in $\mathbf{r}$ to $\mathbf{s}$ transition with
$01$ edge in the launch step and the remaining $11$ edges ($P(11)n-M$) in the
landing step.
Let $M^{\prime}$ be the number of times $1$–$1$ flow occurs in the
intermediate $\mathbf{r}^{\prime}$ to $\mathbf{s}^{\prime}$ transition
problem. A small calculation shows that

$M^{\prime}=M+2P(10)n.$ (7)

If $1$–$1$ boosting method is iteratively used $t$ times, then at the end of
$t$ iterations, the number of $1$–$1$ flow occurs in the intermediate
transition problem will be $M^{\prime}=M+2tP(10)n$. We will use $1$–$1$
boosting for multiple iterations until we achieve $M^{\prime}\geq n^{*}$.

When $P(11)n-M<P(10)n$, perform step $1$ and $2$ in the above defined
procedure. The number of $1$–$1$ flows in the intermediate
$\mathbf{r}^{\prime}$ to $\mathbf{s}^{\prime}$ problem instance will be,

$M^{\prime}=M+(P(11)n-M)=P(11)n.$ (8)

Since we have already raised the number of $1$–$1$ flows in the intermediate
transition problem to $n^{*}$, we will use this procedure for a single
iteration and then use "$11$" boosting for the case $1$.

######  Example 6.

Let $G$ be the first order de Bruijn graph shown in figure 1. Consider the
$n$-integral stationary Markov chain on $G$ given by
$P(10)=P(01)=0.1,P(00)=P(11)=0.4$. For $n=10$, we have $n_{1}=5\text{ and
}n_{2}=5$ and $n^{*}=P(11)n=4$. The two-step transition method given in Table
I will be valid only if $M\geq\max(P(11)n,P(11)n+P(10)n-P(00)n)=4$. The
initial two-step problem instance is shown in Table IV. We have one $1$–$1$
flow in our initial two-step problem instance. As $M<n^{*}\text{ and
}P(11)n-M>P(10)n$, we employ $1$–$1$ boosting for the case $2$. The $W$ array
after one iteration of the $1$–$1$ boosting is displayed in Table V. After the
boosting, we obtain three $1$–$1$ flows. We can repeat this process for one
more iteration to raise the number of $1$–$1$ flows to $4$.

$0$ | $1$ | $1$ | $1$ | $1$ | $0$ | $0$ | $0$ | $0$ | $1$
---|---|---|---|---|---|---|---|---|---
|  |  |  |  |  |  |  |  |
$0$ | $0$ | $0$ | $0$ | $1$ | $1$ | $1$ | $1$ | $1$ | $0$
Table IV: Before $1$–$1$ boosting $0$ | $1$ | $1$ | $1$ | $1$ | $0$ | $0$ | $0$ | $0$ | $1$
---|---|---|---|---|---|---|---|---|---
$0$ | $0$ | $1$ | $1$ | $1$ | $1$ | $0$ | $0$ | $0$ | $1$
|  |  |  |  |  |  |  |  |
$0$ | $0$ | $0$ | $1$ | $1$ | $1$ | $0$ | $1$ | $1$ | $0$
$0$ | $0$ | $0$ | $0$ | $1$ | $1$ | $1$ | $1$ | $1$ | $0$
Table V: After one iteration of $1$–$1$ boosting

###  C-C Number of Steps Required to Reach the Target Row

As our problem is the one of transitioning from a top row
$\mathbf{r}=(r^{j})_{j\in[n]}$ to a bottom row
$\sigma_{\mathrm{left}}(U_{\pi})=:\mathbf{s}=(s^{j})_{j\in[n]}$ in a fixed
number of steps. In this section, initially, we compute the required number of
steps to solve $\mathbf{r}$ to $\mathbf{s}$ transition problem, for each
specified case. Subsequently, to ensure a fixed number of steps, $Z$, across
all cases, we determine the maximum steps required among all cases. If the
transition is achieved before the maximum number of steps, we maintain the
target row for the remaining steps. Maintaining the arrangement of vertices
after every two steps is possible by choosing $M=n_{2}$ in the two-step
transition method described in Table I. Since the maximum of steps needed for
each case is an even number, we can maintain the permutation in jumps of two.

$\mathbf{\textbf{Case }1:M\geq n^{*}}$

When $M<P(11)n+P(10)n-P(00)n$, let $t$ be the minimum number of iterations of
$1$–$1$ boosting needed to raise the number of $1$–$1$ flows in the
intermediate $\mathbf{r}^{\prime}$ to $\mathbf{s}^{\prime}$ transition problem
to a value $M^{\prime}$ greater than or equal to the further lower bound (see
Eq. (3)), then we have

$M^{\prime}\geq P(11)n+P(10)n-P(00)n,$

$M+tP(00)n\geq P(11)n+P(10)n-P(00)n,$

$t=\left\lceil\frac{P(11)n+P(10)n-P(00)n-M}{P(00)n}\right\rceil.$ (9)

Therefore, when the number of $1$–$1$ flows for $\mathbf{r}$ to $\mathbf{s}$
transition is greater than or equal to $n^{*}$ then, for any $n$-integral
stationary Markov chain on $G$, it is feasible to have $\mathbf{r}$ to
$\mathbf{s}$ transition, in at most $Z_{1}$ steps, where

$Z_{1}=2\left(1+\left\lceil\frac{P(11)+P(10)-P(00)}{P(00)}\right\rceil\right).$
(10)

Case 2 : $\mathbf{M<n^{*}}$

(i) $P(11)n-M\geq P(10)n:$

Let $t$ be the minimum number of iterations of $1$–$1$ boosting needed to
raise the number of $1$–$1$ flows in the intermediate $\mathbf{r}^{\prime}$ to
$\mathbf{s}^{\prime}$ transition problem, to a value $M^{\prime}\geq n^{*}$,
then we have

$M^{\prime}\geq P(11)n,$

$M+2tP(01)n\geq P(11)n,$

$t=\left\lceil\frac{P(11)-M}{2P(01)n}\right\rceil.$ (11)

Therefore, when the number of $1$–$1$ flows in $\mathbf{r}$ to $\mathbf{s}$
transition is less than $n^{*}$, then for any $n$-integral stationary Markov
chain on $G$ such that $P(11)n-M\geq P(10)n$, it is feasible to have
$\mathbf{r}$ to $\mathbf{s}$ transition, in at most $Z_{2}$ steps, where

$Z_{2}=2\left(1+\left\lceil\frac{P(11)}{2P(01)}\right\rceil\right).$ (12)

(ii) $P(11)n-M<P(10)n:$

We execute the transition from $\mathbf{r}$ to $\mathbf{s}$ in two stages. The
first stage is to use one iteration of $1$-$1$ boosting for case when
$M<n^{*}$. This increases the number of $1$–$1$ flows in the intermediate
$\mathbf{r}^{\prime}$ to $\mathbf{s}^{\prime}$ transition to
$M^{\prime}=n^{*}$. The second stage is to use $1$–$1$ boosting for the case
when $M\geq n^{*}$ and increase the number of $1$-$1$ flows above the further
lower bound, $M^{\prime}\geq P(11)n+P(10)n-P(00)n$.

The first stage can be completed in two steps. Let $t$ be the number of
iterations of $1$–$1$ boosting needed to complete the second stage, then we
have

$M^{\prime}+tP(00)n\geq P(11)n+P(10)n-P(00)n$,

$t=\left\lceil\frac{P(11)n+P(10)n-P(00)n-M^{\prime}}{P(00)n}\right\rceil$.

Therefore, when the number of $1$–$1$ flows in $\mathbf{r}$ to $\mathbf{s}$
transition is less than $n^{*}$, then for any $n$-integral stationary Markov
chain on $G$ such that $P(11)n-M<P(10)n$, it is feasible to have $\mathbf{r}$
to $\mathbf{s}$ transition, in at most $Z_{3}$ steps, where

$Z_{3}=2\left(2+\left\lceil\frac{P(11)+P(10)-P(00)}{P(00)}\right\rceil\right).$
(13)

Combining the cases $1\text{ and }2$, we conclude that for any $n$-integral
stationary Markov chain on $G$, it is feasible to have $\mathbf{r}$ to
$\mathbf{s}$ transition, in at most $Z$ steps, where
$Z=\max(Z_{1},Z_{2},Z_{3})$.

##  Appendix D Encoding and Decoding Algorithms

Algorithm 1 Encoding

We have a graph $G$ which is a primitive subgraph of $D_{1,2}$, and an
$n$-integral stationary Markov chain on $G$ that assigns positive probability
to all the edges in $G$.

1:Encode the $M$ messages into constant weight codewords, using Row-by-Row
coding.

2:Construct $1\times n$ array $U_{\pi}$, as described in section II-C.

3:Program $M$ rows below $U_{\pi}$ to obtain $W_{(1+m)\times n}$ array, as per
row-by-row coding scheme.

4:Add two vacant rows and set the bottom row as the target row, which is
$U_{\pi}$ cyclically shifted to the left by one position.

5:Compute $M$ the number of $1$–$1$ flows for the two-step transition
instance, the lower bound $LB=P(11)n+P(10)n-P(00)n$, and the number of steps
$Z$, from the expression given in the Theorem 1.

6:if $M\geq\max(P(11)n,LB$) then

  * i:

Use the transition method defined in Table I.

  * ii:

If the number of steps used is less than $Z$, maintain the target row for the
remaining steps by choosing $M=n_{2}$ in the transition method defined in
Table I.

7:end if

8:if $P(11)n\leq M\leq LB$ then

  * i

Use $1$-$1$ boosting for the case $M\geq P(11)n$, and raise the number of
$1$-$1$ flows in the intermediate transition instance to a value
$M^{{}^{\prime}}\geq LB$.

  * ii

Apply step $6$.

9:end if

10:if $M<P(11)n\text{ and }P(11)n-M<P(10)n$ then

  * i

Use the Step $1$ and $2$ of $1$–$1$ boosting for the case $M<P(11)n$ for one
iteration.

  * ii

Apply step $6$ or $8$.

11:end if

12:if $M<P(11)m\text{ and }P(11)n-M\geq P(10)n$ then

  * i

Use $1$–$1$ boosting for the case $M<P(11)n$ and raise the number of $1$-$1$
flows in the intermediate transition instance to a value $M^{\prime}\geq
n^{*}$.

  * ii

Apply step $6$ or $8$.

13:end if

14:Concatenate the columns of $W$ array in the order of their appearance to
get one long codeword of length $N$ in which every pattern $e\in E$ occurs
exactly $P(e)(N-1)$ times.

Algorithm 2 Decoding

1:Reconstruct $W$ array by stacking each batch of $Z$ symbols as a column in
the order of their appearance.

2:Use the row-by-row decoding method to extract the payload.