# Coding Schemes Based on Reed-Muller Codes for $(d,\infty)$-RLL Input-
Constrained Channels

V. Arvind Rameshwar, and Navin Kashyap The work of V. A. Rameshwar was
supported by a Prime Minister’s Research Fellowship, from the Ministry of
Education, Govt. of India. A part of this work was presented at the 2022 IEEE
International Symposium on Information Theory (ISIT).The authors are with the
Department of Electrical Communication Engineering, Indian Institute of
Science, Bengaluru 560012, India (e-mail<EMAIL_ADDRESS>nkashyap@iisc.ac.in).

###### Abstract

The paper considers coding schemes derived from Reed-Muller (RM) codes, for
transmission over input-constrained memoryless channels. Our focus is on the
$(d,\infty)$-runlength limited (RLL) constraint, which mandates that any pair
of successive $1$s be separated by at least $d$ $0$s. In our study, we first
consider $(d,\infty)$-RLL subcodes of RM codes, taking the coordinates of the
RM codes to be in the standard lexicographic ordering. We show, via a simple
construction, that RM codes of rate $R$ have linear $(d,\infty)$-RLL subcodes
of rate $R\cdot{2^{-\left\lceil\log_{2}(d+1)\right\rceil}}$. We then show that
our construction is essentially rate-optimal, by deriving an upper bound on
the rates of linear $(d,\infty)$-RLL subcodes of RM codes of rate $R$. Next,
for the special case when $d=1$, we prove the existence of potentially non-
linear $(1,\infty)$-RLL subcodes that achieve a rate of
$\max\left(0,R-\frac{3}{8}\right)$. This, for $R>3/4$, beats the $R/2$ rate
obtainable from linear subcodes. We further derive upper bounds on the rates
of $(1,\infty)$-RLL subcodes, not necessarily linear, of a certain canonical
sequence of RM codes of rate $R$. We then shift our attention to settings
where the coordinates of the RM code are not ordered according to the
lexicographic ordering, and derive rate upper bounds for linear
$(d,\infty)$-RLL subcodes in these cases as well. Finally, we present a new
two-stage constrained coding scheme, again using RM codes of rate $R$, which
outperforms any linear coding scheme using $(d,\infty)$-RLL subcodes, for
values of $R$ close to $1$.

###### Index Terms:

Reed-Muller codes, runlength-limited constraints, BMS channels

##  I Introduction

Constrained coding is a method that helps alleviate error-prone sequences in
data recording and communication systems, by allowing the encoding of
arbitrary user data sequences into only those sequences that respect the
constraint (see, for example, [1] or [2]). In this work, we consider the
construction of constrained codes derived from the Reed-Muller (RM) family of
codes.

Our focus is on the $(d,\infty)$-runlength limited (RLL) input constraint,
which mandates that there be at least $d$ $0$s between every pair of
successive $1$s in the binary input sequence. For example, when $d=2$, the
sequence $100100010$ respects the $(2,\infty)$-RLL constraint, but the
sequence $10100010$, does not. It can also be checked that the
$(1,\infty)$-RLL constraint is the same as a “no-consecutive-ones” constraint.
The $(d,\infty)$-RLL constraint is a special case of the $(d,k)$-RLL
constraint, which admits only binary sequences in which successive $1$s are
separated by at least $d$ $0$s, and the length of any run of $0$s is at most
$k$. In a magnetic recording system, for example, the $(d,\infty)$-RLL
constraint on the data sequence (where the bit $1$ corresponds to a voltage
peak of high amplitude and the bit $0$ corresponds to no peak) ensures that
successive $1$s are spaced far enough apart, so that there is little inter-
symbol interference between the voltage responses corresponding to the
magnetic transitions. Reference [3] contains many examples of $(d,k)$-RLL
codes used in practice in magnetic storage and recording. More recently,
$(d,k)$-RLL input constrained sequences have also been investigated for joint
energy and information transfer performance [4].

We are interested in the transmission of $(d,\infty)$-RLL constrained codes
over an input-constrained, noisy binary-input memoryless symmetric (BMS)
channel, without feedback. BMS channels form a subclass of discrete memoryless
channels (DMCs). Examples of BMS channels include the binary erasure channel
(BEC) and binary symmetric channel (BSC), shown in Figures 1a and 1b. Figure 2
illustrates our system model of an input-constrained BMS channel, without
feedback. Input-constrained DMCs fall under the broad class of discrete
finite-state channels (DFSCs).

$\epsilon$$\epsilon$$1-\epsilon$$1-\epsilon$${\displaystyle 0}$$1$$1$$0$$-1$

(a)

$p$$p$$1-p$$1-p$${\displaystyle 0}$$1$$1$$-1$

(b)

Figure 1: (a) The binary erasure channel (BEC$(\epsilon)$) with erasure
probability $\epsilon$ and output alphabet $\mathscr{Y}=\\{-1,0,1\\}$. (b) The
binary symmetric channel (BSC$(p)$) with crossover probability $p$ and output
alphabet $\mathscr{Y}=\\{-1,1\\}$.

For the setting of _unconstrained_ DMCs without feedback, explicit codes
achieving the capacities, or whose rates are very close to the capacities,
have been derived in works such as [5, 6, 7, 8, 9]. However, to the best of
our knowledge, there are no explicit coding schemes with provable rate and
probability of error guarantees, for input-constrained DMCs without feedback.
We mention also that unlike the case of the unconstrained DMC, whose capacity
is characterized by Shannon’s single-letter formula,
$C_{\text{DMC}}=\sup_{P(x)}I(X;Y)$, the computation of the capacity of a DFSC,
given by the maximum mutual information rate between inputs and outputs, is a
much more difficult problem to tackle, and is open for many simple channels.
In fact, the computation of the mutual information rate even for the simple
case of Markov inputs, over input-constrained DMCs, reduces to the computation
of the entropy rate of a hidden Markov process—a well-known hard problem (see
[10, 11, 12, 13, 14, 15, 16]).

In this paper, we make progress on the construction of explicit codes over
$(d,\infty)$-RLL input-constrained DMCs. Our motivation for constructing
$(d,\infty)$-RLL constrained codes using RM codes, is the recent result of
Reeves and Pfister [17] that Reed-Muller (RM) codes achieve, under bit-MAP
decoding, any rate $R\in[0,C)$, over unconstrained BMS channels, where $C$ is
the capacity of the BMS channel. We note that for the specific setting of the
BEC, Kudekar et al. in [6] were the first to show that Reed-Muller (RM) codes
are capacity-achieving. These results then imply that the constrained coding
schemes we construct have bit-error probability going to $0$ (using the bit-
MAP decoder for the RM code), as the blocklength goes to infinity, if the
codes are used over $(d,\infty)$-RLL input-constrained BMS channels.

###  I-A Other Approaches From Prior Art

There is extensive literature on constrained code constructions that can
correct a fixed number of errors, under a combinatorial error model (see
Chapter 9 in [1] and the references therein). Another related line of work
that aims to limit error propagation during the decoding of constrained codes
can be found in [18, 19, 20, 21]. More recently, the work [22] proposed the
insertion of parity bits for error correction, into those positions of binary
constrained codewords that are unconstrained, i.e., whose bits can be flipped,
with the resultant codeword still respecting the constraint. However, such
works do not analyze the resilience of constrained codes to stochastic channel
noise—the standard noise model in information theory, which is taken up in our
paper.

To the best of our knowledge, the paper [23], on rates achievable by
$(d,k)$-RLL subcodes of cosets of a linear block code, was the first to
consider the problem of coding schemes over RLL input-constrained DMCs.
Specifically, from Corollary 1 of [23], we see that there exist cosets of
capacity-achieving (over the unconstrained BMS channel) codes, whose
$(d,k)$-RLL constrained subcodes have rate at least $C_{0}^{(d,k)}+C-1$, where
$C_{0}^{(d,k)}$ is the noiseless capacity of the $(d,k)$-RLL constraint.
However, the work in [23] does not identify _explicit_ codes over RLL input-
constrained channels.

In the context of designing coding schemes over (input-constrained) BMS
channels, it would be remiss to not comment on the rates achieved by polar
codes—another family of explicit codes that is capacity-achieving over a broad
class of channels (see, for example, [5, 24, 25], and references therein).
Following the work of Li and Tan in [26], it holds that the capacity without
feedback of the class of input-constrained DMCs can be approached arbitrarily
closely using stationary, ergodic Markov input distributions of finite order.
Moreover, from the results in [25], it follows that polar codes can achieve
the mutual information rate of any stationary, ergodic finite-state Markov
input process, over any DMC. In particular, this shows that polar codes
achieve the capacity of $(d,\infty)$-RLL input-constrained DMCs, which
includes the class of $(d,\infty)$-RLL input-constrained BMS channels.
However, this observation is not very helpful for the following reasons:

  * •

We do not possess knowledge of an optimal sequence of Markov input
distributions.

  * •

The polar code construction described above is not explicit, since the choice
of bit-channels to send information bits over is not explicitly known for an
arbitrary BMS channel.

  * •

It is hard to compute the rate achieved by such a coding scheme, since such a
computation reduces to the calculation of the mutual information rate of a
hidden Markov process.

$P_{Y|X}$$\hat{m}$$y^{n}$$x^{n}$DecoderConstrainedEncoderBMS${\displaystyle
m\in\left[2^{nR}\right]}$

Figure 2: System model of an input-constrained binary-input memoryless
symmetric (BMS) channel without feedback.

###  I-B Our Contributions

In this work, we propose explicit coding schemes using RM codes, with
computable rate lower bounds, over input-constrained BMS channels. In the
first part of the paper, we fix the ordering of the coordinates of the RM
codes we consider to be the standard lexicographic ordering. Suppose that $C$
is the capacity of the unconstrained BMS channel. Our first approach to
designing $(d,\infty)$-RLL constrained codes is simply to identify _linear_
$(d,\infty)$-RLL subcodes of RM codes of rate $R$. Our results identify
subcodes of rate $R\cdot{2^{-\left\lceil\log_{2}(d+1)\right\rceil}}$, in the
limit as the blocklength goes to infinity, thereby showing that a rate of
$C\cdot{2^{-\left\lceil\log_{2}(d+1)\right\rceil}}$ is achievable over
$(d,\infty)$-RLL input-constrained BMS channels, using linear RM subcodes.
Next, we present a lower bound on rates of _non-linear_ $(1,\infty)$-RLL
subcodes of RM codes. Our result shows that a rate of
$\max\left(0,C-\frac{3}{8}\right)$ is achievable, using this approach.

We then consider the question of obtaining upper bounds on the rates of
$(d,\infty)$-RLL subcodes of RM codes of rate $R$, under the lexicographic
coordinate ordering. First, we impose the additional restriction that the
subcodes be linear. We prove that any linear $(d,\infty)$-RLL subcode can have
rate at most $\frac{R}{d+1}$, in the limit as the blocklength goes to
infinity. This shows that the linear $(d,\infty)$-RLL subcodes we previously
identified are essentially rate-optimal. Next, we consider general (not
necessarily linear) constrained subcodes of RM codes, and derive an upper
bound on the rate of the largest $(1,\infty)$-RLL subcodes of a certain
canonical sequence of RM codes of rate $R$, which we had also used in our
lower bounds. Our novel method of analysis involves using an alternative
characterization of $(1,\infty)$-RLL codewords of RM codes, and employs
properties of the weight distribution of RM codes—a topic that has received
revived attention over the last decade (see, for example, the survey [27] and
the papers [28, 29, 30, 31]). Unfortunately, this method does not readily
extend to the $(d,\infty)$-RLL case, upper bounds for which remain an open
problem.

Since permutations of coordinates have the potential to convert a binary word
that does not respect the $(d,\infty)$-RLL constraint to one that does, we
then ask the question if under alternative coordinate orderings, we can obtain
_linear_ $(d,\infty)$-RLL subcodes of RM codes of rate $R$, of rate larger
than the upper bound of $\frac{R}{d+1}$ that we had derived for the case when
the coordinates follow the lexicographic ordering. We show that for RM codes
of large enough blocklength, under almost all coordinate permutations, linear
$(d,\infty)$-RLL subcodes must respect a rate upper bound of
$\frac{R}{d+1}+\delta$, where $\delta>0$ can be arbitrarily small.

As an improvement over the rates achievable using $(d,\infty)$-RLL subcodes,
we propose a new explicit two-stage (or concatenated) coding scheme using RM
codes. The rate achieved by this scheme is at least $\frac{C_{0}\cdot
C^{2}\cdot 2^{-\left\lceil\log_{2}(d+1)\right\rceil}}{C^{2}\cdot
2^{-\left\lceil\log_{2}(d+1)\right\rceil}+1-C+\epsilon}$, where $C_{0}$ is the
noiseless capacity of the input constraint, and $\epsilon>0$ can be taken to
be as small as needed. For example, when $d=1$, the rates achieved using this
two-stage scheme are better than those achieved by any scheme that uses linear
$(1,\infty)$-RLL subcodes of RM codes (under almost all coordinate orderings),
when $C\gtrapprox 0.7613$, and better than the rate achieved by our non-linear
subcodes for all $C\lessapprox 0.55$ and $C\gtrapprox 0.79$. Moreover, as the
capacity of the channel approaches $1$, i.e., as the channel noise approaches
$0$, the rate achieved by our two-stage coding scheme can be made arbitrarily
close to $C_{0}$, which is the largest rate achievable, at zero noise, given
the constraint.

The remainder of the paper is organized as follows: Section II introduces the
notation and provides some preliminary background. Section III states our main
results. The achievable rates using $(d,\infty)$-RLL subcodes of RM codes of
rate $R$, under the lexicographic coordinate ordering, are discussed in
Section IV. Section V-A then describes the derivation of upper bounds on the
rates of linear $(d,\infty)$-RLL subcodes of RM codes of rate $R$, and Section
V-B contains a derivation of upper bounds on the rates of general
$(1,\infty)$-RLL subcodes of a canonical sequence of RM codes of rate $R$, at
all times assuming the ordering of coordinates to be the lexicographic
ordering. Section V-C then discusses rate upper bounds for linear
$(d,\infty)$-RLL subcodes of RM codes of rate $R$, under other coordinate
orderings. Section VI then presents our construction of a two-stage or
concatenated $(d,\infty)$-RLL constrained coding scheme using RM codes.
Finally, Section VII contains concluding remarks and a discussion on possible
future work.

##  II Notation and Preliminaries

###  II-A Notation

We use calligraphic letters, e.g., $\mathscr{X}$, to denote sets. The notation
$[n]$ denotes the set, $\\{1,2,\ldots,n\\}$, of integers, and the notation
$[a:b]$, for $a<b$, denotes the set of integers $\\{a,a+1,\ldots,b\\}$.
Moreover, for a real number $x$, we use $\left\lceil x\right\rceil$ to denote
the smallest integer larger than or equal to $x$. For vectors $\mathbf{w}$ and
$\mathbf{v}$ of length $n$ and $m$, respectively, we denote their
concatenation by the $(m+n)$-length vector, $\mathbf{w}\mathbf{v}$. The
notation $x^{N}$ denotes the vector $(x_{1},\ldots,x_{N})$. We also use the
notation $\mathbf{e}_{i}^{(n)}$ to denote the standard basis vector of length
$n$, with a $1$ at position $i$, and $0$s elsewhere, for $i\in[n]$. When
$n=2^{m}$, for some $m$, we interchangeably index the coordinates of vectors
$\mathbf{v}\in\\{0,1\\}^{n}$ by integers $i\in[0:n-1]$ and by $m$-tuples
$\mathbf{b}=(b_{1},\ldots,b_{m})\in\\{0,1\\}^{m}$. We let B$(i)$ denote the
length-$m$ binary representation of $i$, for $0\leq i\leq 2^{m}-1$. We then
use the notation $\mathbf{e}_{\mathbf{b}}^{(n)}$ to denote the standard basis
vector of length $n$, with a $1$ at position $\mathbf{b}$, and $0$s elsewhere.
The superscript ‘$(n)$’ will be dropped when clear from context. For any
$n\in\mathbb{N}$, we denote by $S_{(d,\infty)}^{(n)}$, the set of all
$n$-length binary words that respect the $(d,\infty)$-RLL constraint, and we
set $S_{(d,\infty)}=\bigcup_{n\geq 1}S_{(d,\infty)}^{(n)}$.

Given a set $A$, we define the indicator function $\mathds{1}\\{x\in A\\}$ to
be $1$ when $x\in A$, and $0$, otherwise. The notation
$X\sim\mathcal{N}(\mu,\sigma^{2})$ refers to the fact that the random variable
$X$ is drawn according to the Gaussian distribution, with mean $\mu$ and
variance $\sigma^{2}>0$. Also, the notation
$h_{b}(p):=-p\log_{2}p-(1-p)\log_{2}(1-p)$ is the binary entropy function, for
$p\in[0,1]$. All through, the empty summation is defined to be $0$, and the
empty product is defined to be $1$. We write exp${}_{2}(z)$ for $2^{z}$, where
$z\in\mathbb{R}$, and the notation $\ln$ refers to the natural logarithm.
Throughout, we use the convenient notation $\binom{m}{\leq r}$ to denote the
summation $\sum\limits_{i=0}^{r}\binom{m}{i}$. For sequences $(a_{n})_{n\geq
1}$ and $(b_{n})_{n\geq 1}$ of positive reals, we say that $a_{n}=O(b_{n})$,
if there exists $n_{0}\in\mathbb{N}$ and a positive real $M$, such that
$a_{n}\leq M\cdot b_{n}$, for all $n\geq n_{0}$. Likewise, we say that
$a_{n}=o(b_{n})$, if $\lim_{n\to\infty}\frac{a_{n}}{b_{n}}=0$.

###  II-B Information Theoretic Preliminaries

####  II-B1 Block Codes and Constrained Codes

We recall the following definitions of block codes over $\mathbb{F}_{2}$ and
their rates (see, for example, Chapter 1 of [32]).

######  Definition II.1.

An $(n,M)$ block code $\mathcal{C}$ over $\mathbb{F}_{2}$ is a nonempty subset
of $\mathbb{F}_{2}^{n}$, with $|\mathcal{C}|=M$. The rate of the block code
$\mathcal{C}$ is given by

$\text{rate}(\mathcal{C}):=\frac{\log_{2}M}{n}.$

Moreover, given a sequence of codes $\\{\mathcal{C}^{(n)}\\}_{n\geq 1}$, if it
holds that rate$(\mathcal{C}^{(n)})\xrightarrow{n\to\infty}R$, for some
$R\in[0,1]$, then we say that $\\{\mathcal{C}^{(n)}\\}_{n\geq 1}$ is of rate
$R$.

Consider now the set $S_{(d,\infty)}^{(n)}$ of length-$n$ binary words that
satisfy the $(d,\infty)$-RLL constraint. We recall the following definition
(see, for example, Chapter 3 of [1]):

######  Definition II.2.

The noiseless capacity $C_{0}^{(d)}$ of the $(d,\infty)$-RLL constraint is
defined as

$C_{0}^{(d)}:=\lim_{n\to\infty}\frac{\log_{2}\left\lvert
S_{(d,\infty)}^{(n)}\right\rvert}{n}=\inf_{n}\frac{\log_{2}\left\lvert
S_{(d,\infty)}^{(n)}\right\rvert}{n},$

where the last equality follows from the subadditivity of the sequence
$\left(\log_{2}\left\lvert S_{(d,\infty)}^{(n)}\right\rvert\right)_{n\geq 1}$.

####  II-B2 Linear Codes Over BMS Channels

A binary-input channel $W$ is defined by the binary-input input alphabet
$\mathscr{X}=\\{0,1\\}$, the output alphabet
$\mathscr{Y}\subseteq{\mathbb{R}}$, and the transition probabilities
$\left(P(y|x):x\in\mathscr{X},y\in\mathscr{Y}\right)$, where $P(\cdot|x)$ is a
density function with respect to the counting measure, if $\mathscr{Y}$ is
discrete, and with respect to the Lebesgue measure, if
$\mathscr{Y}=\mathbb{R}$ and the output distribution is continuous. A binary-
input memoryless symmetric (BMS) channel obeys a memorylessness property,
i.e., $P(y_{i}|x^{i},y^{i-1})=P(y_{i}|x_{i})$, for all $i$. Further, the
channel is symmetric, in that $P(y|1)=P(-y|0)$, for all $y\in\mathscr{Y}$.
Every such channel can be expressed as a multiplicative noise channel, in the
following sense: if at any $i$ the input random symbol is $X_{i}\in\\{0,1\\}$,
then the corresponding output symbol $Y_{i}\in\mathscr{Y}$ is given by

$Y_{i}=(-1)^{X_{i}}\cdot Z_{i},$

where the noise random variables $Z^{n}$ are independent and identically
distributed, and the noise process $(Z_{i})_{i\geq 1}$ is independent of the
input process $(X_{i})_{i\geq 1}$. Common examples of such channels include
the binary erasure channel (BEC$(\epsilon)$), with $P(Z_{i}=1)=1-\epsilon$ and
$P(Z_{i}=0)=\epsilon$, the binary symmetric channel (BSC$(p)$), with
$P(Z_{i}=1)=1-p$ and $P(Z_{i}=-1)=p$, and the binary additive white Gaussian
noise (BI-AWGN) channel, where $Z_{i}\sim\mathcal{N}(1,\sigma^{2})$. Figures
1a and 1b depict the BEC and BSC, pictorially.

In this work, we are interested in designing codes over input-constrained BMS
channels. We refer the reader to [17] for definitions of the bit-MAP decoder
and bit-error probability $P_{b}^{(n)}$ (under bit-MAP decoding), indexed by
the blocklength $n$ of the code. We also refer the reader to standard texts on
information theory such as [33], [34] for definitions of blockwise maximum-a-
posteriori (block-MAP) decoding and block-error probability $P_{B}^{(n)}$.

Specifically, we shall be using constrained subcodes of linear codes
$\left\\{\mathcal{C}^{(n)}\right\\}_{n\geq 1}$ over BMS channels. At the
decoder end, we shall employ the bit-MAP decoders of
$\left\\{\mathcal{C}^{(n)}\right\\}_{n\geq 1}$. Since $\mathcal{C}^{(n)}$ is
linear, the average bit-error probability $P_{b}^{(n)}$ (resp. the average
block-error probability $P_{B}^{(n)}$), under bit-MAP decoding (resp. block-
MAP decoding) of $\mathcal{C}^{(n)}$ is the same as the average bit-error
probability (resp. the average block-error probability) when a subcode of
$\mathcal{C}^{(n)}$ is used (see [17] for a discussion).

We say that a rate $R$ is achieved by
$\left\\{\mathcal{C}^{(n)}\right\\}_{n\geq 1}$ over a BMS channel, under bit-
MAP decoding, if
$\text{rate}\left(\mathcal{C}^{(n)}\right)\xrightarrow{n\to\infty}R$, with
$P_{b}^{(n)}\xrightarrow{n\to\infty}0$. Hence, any sequence of subcodes of
$\left\\{\mathcal{C}^{(n)}\right\\}_{n\geq 1}$ are also such that their bit-
error probabilities go to zero, as the blocklength goes to infinity.

###  II-C Reed-Muller Codes: Definitions and BMS Channel Performance

We recall the definition of the binary Reed-Muller (RM) family of codes.
Codewords of binary RM codes consist of the evaluation vectors of multivariate
polynomials over the binary field $\mathbb{F}_{2}$. Consider the polynomial
ring $\mathbb{F}_{2}[x_{1},x_{2},\ldots,x_{m}]$ in $m$ variables. Note that in
the specification of a polynomial
$f\in\mathbb{F}_{2}[x_{1},x_{2},\ldots,x_{m}]$, only monomials of the form
$\prod_{j\in S:S\subseteq[m]}x_{j}$ need to be considered, since $x^{2}=x$
over the field $\mathbb{F}_{2}$, for an indeterminate $x$. For a polynomial
$f\in\mathbb{F}_{2}[x_{1},x_{2},\ldots,x_{m}]$ and a binary vector
$\mathbf{z}=(z_{1},\ldots,z_{m})\in\mathbb{F}_{2}^{m}$, let
Eval${}_{\mathbf{z}}(f):=f(z_{1},\ldots,z_{m})$. We let the evaluation points
be ordered according to the standard lexicographic order on strings in
$\mathbb{F}_{2}^{m}$, i.e., if $\mathbf{z}=(z_{1},\ldots,z_{m})$ and
$\mathbf{z}^{\prime}=(z_{1}^{\prime},\ldots,z_{m}^{\prime})$ are two distinct
evaluation points, then, $\mathbf{z}$ occurs before $\mathbf{z}^{\prime}$ in
our ordering if and only if for some $i\geq 1$, it holds that
$z_{j}=z_{j}^{\prime}$ for all $j<i$, and $z_{i}<z_{i}^{\prime}$. Now, let
Eval$(f):=\left(\text{Eval}_{\mathbf{z}}(f):\mathbf{z}\in\mathbb{F}_{2}^{m}\right)$
be the evaluation vector of $f$, where the coordinates $\mathbf{z}$ are
ordered according to the standard lexicographic order.

######  Definition II.3 (see [35], Chap. 13, or [27]).

The $r^{\text{th}}$-order binary Reed-Muller code RM$(m,r)$ is defined as the
set of binary vectors:

$\text{RM}(m,r):=\\{\text{Eval}(f):f\in\mathbb{F}_{2}[x_{1},x_{2},\ldots,x_{m}],\
\text{deg}(f)\leq r\\},$

where $\text{deg}(f)$ is the degree of the largest monomial in $f$, and the
degree of a monomial $\prod_{j\in S:S\subseteq[m]}x_{j}$ is simply $|S|$.

It is a known fact that the evaluation vectors of all the distinct monomials
in the variables $x_{1},\ldots,x_{m}$ are linearly independent over
$\mathbb{F}_{2}$. It then follows that RM$(m,r)$ has dimension $\binom{m}{\leq
r}:=\sum_{i=0}^{r}{m\choose i}$. Furthermore, RM$(m,r)$ has minimum Hamming
distance ${d}_{\text{min}}(\text{RM}(m,r))=2^{m-r}$. The weight of a codeword
$\mathbf{c}=\text{Eval}(f)$ is the number of $1$s in its evaluation vector,
i.e,

$\text{wt}\left(\text{Eval}(f)\right):=\left\lvert\\{\mathbf{z}\in\mathbb{F}_{2}^{m}:f(\mathbf{z})=1\\}\right\rvert.$

The number of codewords in RM$(m,r)$ of weight $w$, for $w\in[2^{m-r}:2^{m}]$,
is given by the weight distribution function at $w$:

$A_{m,r}(w):=\left\lvert\\{\mathbf{c}\in\text{RM}(m,r):\text{wt}\left(\mathbf{c}\right)=w\\}\right\rvert.$

The subscripts $m$ and $r$ in $A_{m,r}$ will be suppressed when clear from
context.

We also set $G_{\text{Lex}}(m,r)$ to be the generator matrix of
$\text{RM}(m,r)$ consisting of rows that are the evaluations, in the
lexicographic order, of monomials of degree less than or equal to $r$. The
columns of $G_{\text{Lex}}(m,r)$ will be indexed by $m$-tuples
$\mathbf{b}=(b_{1},\ldots,b_{m})$ in the lexicographic order.

In this work, we shall use $(d,\infty)$-RLL constrained subcodes of RM codes,
over BMS channels. We now recall the main result of Reeves and Pfister in
[17], which provides context to our using RM codes over input-constrained BMS
channels. For a given $R\in(0,1)$, consider any sequence of RM codes
$\left\\{\hat{\mathcal{C}}_{m}(R)=\text{RM}(m,r_{m})\right\\}_{m\geq 1}$,
under the lexicographic ordering of coordinates, such that
rate$\left(\hat{\mathcal{C}}_{m}(R)\right)\xrightarrow{m\to\infty}R$. We let
$C$ be the capacity of the unconstrained BMS channel under consideration. The
following theorem then holds true:

######  Theorem II.1 (Theorem 1 of [17]).

Any rate $R\in[0,C)$ is achieved by the sequence of codes
$\left\\{\hat{\mathcal{C}}_{m}(R)\right\\}_{m\geq 1}$, under bit-MAP decoding.

As an example, consider the sequence of RM codes
$\left\\{{\mathcal{C}}_{m}(R)=\text{RM}(m,r_{m})\right\\}_{m\geq 1}$ with

$r_{m}=\max\left\\{\left\lfloor\frac{m}{2}+\frac{\sqrt{m}}{2}Q^{-1}(1-R)\right\rfloor,0\right\\},$
(1)

where $Q(\cdot)$ is the complementary cumulative distribution function
(c.c.d.f.) of the standard normal distribution, i.e.,

$Q(t)=\frac{1}{\sqrt{2\pi}}\int_{t}^{\infty}e^{-\tau^{2}/2}d\tau,\
t\in\mathbb{R}.$

From Remark 24 in [6], it holds that
rate$\left({\mathcal{C}}_{m}(R)\right)\xrightarrow{m\to\infty}R$. Theorem II.1
then states that the sequence of codes $\\{{\mathcal{C}}_{m}(R)\\}_{m\geq 1}$
achieves a rate $R$ over any unconstrained BMS channel, so long as $R<C$.

######  Remark.

We note that by Theorem II.1, for the unconstrained BEC (resp. unconstrained
BSC) with erasure probability $\epsilon\in(0,1)$ (resp. crossover probability
$p\in(0,0.5)\cup(0.5,1)$), the sequence of codes
$\\{\mathcal{C}_{m}(1-\epsilon-\delta)\\}_{m\geq 1}$ (resp.
$\\{\mathcal{C}_{m}(1-h_{b}(p)-\delta)\\}_{m\geq 1}$) achieves a rate of
$1-\epsilon-\delta$ (resp. a rate of $1-h_{b}(p)-\delta$), for all $\delta>0$
suitably small.

The following important property of RM codes, which is sometimes called the
Plotkin decomposition (see [35, Chap. 13] and [27]), will come of use several
times in this paper: any Boolean polynomial
$f\in\mathbb{F}_{2}[x_{1},\ldots,x_{m}]$, such that
Eval$(f)\in\text{RM}(m,r)$, can be expressed as:

$f(x_{1},\ldots,x_{m})=g(x_{1},\ldots,x_{m-1})+x_{m}\cdot
h(x_{1},\ldots,x_{m-1}),$ (2)

where $g,h$ are such that Eval$(g)\in\text{RM}(m-1,r)$ and
Eval$(h)\in\text{RM}(m-1,r-1)$. Given the sequence of RM codes
$\left\\{{\mathcal{C}}_{m}(R)=\text{RM}(m,r_{m})\right\\}_{m\geq 1}$, where
$r_{m}$ is as in (1), we use the notations
$\mathcal{C}_{m}^{(g)}:=\text{RM}(m-1,r_{m})$ and
$\mathcal{C}_{m}^{(h)}:=\text{RM}(m-1,r_{m}-1)$, with
rate$\left(\mathcal{C}_{m}^{(g)}\right):=R_{m}^{(g)}$ and
rate$\left(\mathcal{C}_{m}^{(h)}\right):=R_{m}^{(h)}$.

In our $(d,\infty)$-RLL constrained code constructions in this paper, we shall
use constrained subcodes of a sequence
$\left\\{\hat{\mathcal{C}}_{m}(R)=\text{RM}(m,v_{m})\right\\}_{m\geq 1}$ of
rate $R$, and explicitly compute the rates of the coding schemes. From the
discussion in Section II-B2 above, we arrive at the fact that using the bit-
MAP decoder of $\hat{\mathcal{C}}_{m}(R)$, the rates of the constrained
subcodes of $\hat{\mathcal{C}}_{m}(R)$, computed in this paper, are in fact
achievable (with bit-error probabilities going to zero as the blocklength goes
to infinity) over $(d,\infty)$-RLL input-constrained BMS channels, so long as
$R<C$.

##  III Main Results

In this section, we briefly state our main theorems, and provide comparisons
with the literature. We assume that the BMS channel that we are working with,
has an unconstrained capacity of $C\in(0,1)$.

We first fix the coordinate ordering of the RM codes to be the standard
lexicographic ordering. Our first approach to designing $(d,\infty)$-RLL
constrained codes using RM codes is constructing a sequence of _linear_
subcodes of $\\{\mathcal{C}_{m}(R)=\text{RM}(m,r_{m})\\}_{m\geq 1}$, with
$r_{m}$ as in (1), which respect the $(d,\infty)$-RLL input-constraint, and
analyzing the rate of the chosen subcodes. We obtain the following result:

######  Theorem III.1.

For any $R\in(0,1)$, there exists a sequence of linear $(d,\infty)$-RLL codes
$\left\\{\mathcal{C}_{m}^{(d,\infty)}(R)\right\\}_{m\geq 1}$, where
$\mathcal{C}_{m}^{(d,\infty)}(R)\subset\mathcal{C}_{m}(R)$, of rate
$\frac{R}{2^{\left\lceil\log_{2}(d+1)\right\rceil}}$.

The proof of Theorem III.1 (which is Theorem III.2 in [36]), which contains an
explicit identification of the subcodes
$\left\\{\mathcal{C}_{m}^{(d,\infty)}(R)\right\\}_{m\geq 1}$, is provided in
Section IV. From the discussion in Section II-C, we see that by Theorem III.1,
using linear constrained subcodes of RM codes over the $(d,\infty)$-RLL input-
constrained BEC, a rate of $\frac{1}{d+1}(1-\epsilon)$ is achievable when
$d=2^{t}-1$, for some $t\in\mathbb{N}$, and a rate of
$\frac{1}{2(d+1)}(1-\epsilon)$ is achievable, otherwise. We note, however,
that using random coding arguments, or using the techniques in [10] or [16],
it holds that a rate of $C_{0}^{(d)}(1-\epsilon)$ is achievable over the
$(d,\infty)$-RLL input-constrained BEC, where $C_{0}^{(d)}$ is the noiseless
capacity of the input constraint (for example, $C_{0}^{(1)}\approx 0.6942$ and
$C_{0}^{(2)}\approx 0.5515$). For the $(d,\infty)$-RLL input-constrained BSC,
similarly, a rate of $\frac{1}{d+1}(1-h_{b}(p))$ is achievable when
$d=2^{t}-1$, for some $t\in\mathbb{N}$, and a rate of
$\frac{1}{2(d+1)}(1-h_{b}(p))$ is achievable, otherwise. Such a result is in
the spirit of, but is weaker than, the conjecture by Wolf [37] that a rate of
$C_{0}^{(d)}(1-h_{b}(p))$ is achievable over the $(d,\infty)$-RLL input-
constrained BSC.

For the specific case when $d=1$, we now state an existence result that
provides another lower bound on rates of (potentially non-linear)
$(1,\infty)$-RLL constrained subcodes of RM codes of rate $R$.

######  Theorem III.2.

For any $R\in(0,1)$ and for any sequence of codes
$\left\\{\hat{\mathcal{C}}_{m}(R)=\text{RM}(m,r_{m})\right\\}_{m\geq 1}$ of
rate $R$, following the lexicographic coordinate ordering, there exists a
sequence $\left\\{\tilde{\mathcal{C}}_{m}^{(1,\infty)}(R)\right\\}_{m\geq 1}$
of $(1,\infty)$-RLL codes with
$\tilde{\mathcal{C}}_{m}^{(1,\infty)}(R)\subseteq\hat{\mathcal{C}}_{m}(R)$, of
rate at least $\max\left(0,R-\frac{3}{8}\right)$.

The proof of Theorem III.2 is provided in Section IV. Again, we note from the
discussion in Section II-C, that Theorem III.2 implies that rates of at least
$\max\left(0,C-\frac{3}{8}\right)$ are achievable over the $(d,\infty)$-RLL
input-constrained BMS channel. Further, we observe that the lower bound in the
theorem above beats the achievable rate of $\frac{R}{2}$ in Theorem III.1,
when $R>0.75$.

Next, we state a theorem that provides upper bounds on the largest rate of
_linear_ $(d,\infty)$-RLL subcodes of RM codes, where the coordinates are
ordered according to the lexicographic ordering. Fix any sequence of codes
$\left\\{{\hat{\mathcal{C}}}_{m}(R)=\text{RM}(m,r_{m})\right\\}_{m\geq 1}$ of
rate $R\in(0,1)$ and let
$\overline{\mathsf{R}}_{\hat{\mathcal{C}}}^{(d,\infty)}(R)$ be the largest
rate of linear $(d,\infty)$-RLL subcodes of
$\left\\{{\hat{\mathcal{C}}}_{m}(R)\right\\}_{m\geq 1}$. Formally,

$\overline{\mathsf{R}}_{\hat{\mathcal{C}}}^{(d,\infty)}(R):=\limsup_{m\to\infty}\max_{\overline{\mathcal{C}}^{(d,\infty)}\subseteq\hat{\mathcal{C}}_{m}(R)}\frac{\log_{2}\left\lvert\overline{\mathcal{C}}^{(d,\infty)}\right\rvert}{2^{m}},$
(3)

where the maximization is over linear $(d,\infty)$-RLL subcodes
$\overline{\mathcal{C}}^{(d,\infty)}$ of $\hat{\mathcal{C}}_{m}(R)$. Then,

######  Theorem III.3.

For any $R\in(0,1)$ and for any sequence of codes
$\left\\{\hat{\mathcal{C}}_{m}(R)=\text{RM}(m,r_{m})\right\\}_{m\geq 1}$,
following the lexicographic coordinate ordering, with
rate$(\hat{\mathcal{C}}_{m}(R))\xrightarrow{m\to\infty}R$, it holds that

$\overline{\mathsf{R}}_{\hat{\mathcal{C}}}^{(d,\infty)}(R)\leq\frac{R}{d+1}.$

Thus, Theorem III.3 shows that the sequence of simple linear subcodes
$\left\\{\mathcal{C}_{m}^{(d,\infty)}(R)\right\\}_{m\geq 1}$, identified in
Theorem III.1, is rate-optimal whenever $d+1$ is a power of $2$, in that it
achieves the rate upper bound of $\frac{R}{d+1}$. Moreover, it follows from
Theorem III.3, that the subcodes
$\left\\{\tilde{\mathcal{C}}_{m}^{(1,\infty)}(R)\right\\}_{m\geq 1}$ in
Theorem III.2 must be _non-linear_ when $R>0.75$. Theorem III.3 is proved in
Section V-A. Also, from the discussion in Section II and from III.3, we see
that the largest rate achievable over a $(d,\infty)$-RLL input-constrained BMS
channel, using linear $(d,\infty)$-RLL subcodes of RM codes, when the sub-
optimal bit-MAP decoders of the larger RM codes are used, is bounded above by
$\frac{C}{d+1}$.

We remark here that the problem of identifying linear codes that are subsets
of the set of $(d,\infty)$-RLL sequences of a fixed length, has been studied
in [38]. The results therein show that the largest linear code within
$S_{(d,\infty)}^{(m)}$ has rate no larger than $\frac{1}{d+1}$, as
$m\to\infty$. However, such a result offers no insight into rates achievable
over BMS channels.

Concluding the discussion on rates achievable using subcodes of RM codes,
following the lexicographic coordinate ordering, we state a theorem that
provides an upper bound on the largest rate of $(1,\infty)$-RLL subcodes of
the sequence $\\{\mathcal{C}_{m}(R)=\text{RM}(m,r_{m})\\}_{m\geq 1}$, where
$r_{m}$ is as in (1). We formally define this largest rate to be

$\mathsf{R}^{(1,\infty)}_{{\mathcal{C}}}(R):=\limsup_{m\to\infty}\max_{\mathcal{C}^{(1,\infty)}\subseteq\mathcal{C}_{m}(R)}\frac{\log_{2}\left\lvert\mathcal{C}^{(1,\infty)}\right\rvert}{2^{m}},$

where the maximization is over $(1,\infty)$-RLL subcodes of
$\mathcal{C}_{m}(R)$. Then,

######  Theorem III.4.

For the sequence of codes
$\\{{\mathcal{C}}_{m}(R)=\text{RM}(m,r_{m})\\}_{m\geq 1}$, with $r_{m}$ as in
(1), it holds that:

$\mathsf{R}^{(1,\infty)}_{{\mathcal{C}}}(R)\leq\min\left(\frac{7R}{8},C_{0}^{(1)}\right),$

where $C_{0}^{(1)}=\log_{2}\left(\frac{1+\sqrt{5}}{2}\right)\approx 0.6942$ is
the noiseless capacity of the $(1,\infty)$-RLL constraint.

The proof of the theorem is taken up in Section V-B. We note that the upper
bound in the theorem above is an improvement over the upper bound in [36], due
to the use of better upper bounds on the weight distribution, from [31], as
compared to those in [39]. Figure 3 shows a comparison between the upper bound
in Theorem III.4, and the lower bounds of Theorems III.1 and III.2, for the
case when $d=1$. From the discussion in Section II-C, we see that Theorem
III.4 shows that the rate achievable over $(1,\infty)$-RLL input-constrained
BMS channels, using constrained subcodes of $\\{\mathcal{C}_{m}(R)\\}_{m\geq
1}$, when the sub-optimal bit-MAP decoders of the larger RM codes are used, is
bounded above by $\min\left(\frac{7C}{8},C_{0}^{(1)}\right)$, where $C$ is the
capacity of the unconstrained BMS channel. Figure 4 shows comparisons, for the
specific case of the $(1,\infty)$-RLL input-constrained BEC, of the upper
bound of $\min\left(\frac{7}{8}\cdot(1-\epsilon),C_{0}^{(1)}\right)$, obtained
by sub-optimal decoding, in Theorem III.4, with the achievable rate of
$C_{0}^{(1)}\cdot(1-\epsilon)$ (from [11] and [16]), and the numerically
computed achievable rates using the Monte-Carlo method in [40] (or the
stochastic approximation scheme in [15]). For large values of the erasure
probability $\epsilon$, we observe that the upper bound of
$\min\left(\frac{7}{8}\cdot(1-\epsilon),C_{0}^{(1)}\right)$ lies below the
achievable rates of [40], thereby indicating that it is not possible to
achieve the capacity of the $(1,\infty)$-RLL input-constrained BEC, using
$(1,\infty)$-RLL subcodes of $\\{\mathcal{C}_{m}(R)\\}_{m\geq 1}$, when the
bit-MAP decoders of $\\{\mathcal{C}_{m}(R)\\}_{m\geq 1}$ are used for
decoding. We conjecture that this numerically verified fact is indeed true.

Next, we consider situations where the coordinates of the RM codes follow
orderings different from the standard lexicographic ordering. First, we study
upper bounds on the rates of _linear_ $(d,\infty)$-RLL subcodes of RM codes,
whose coordinates are ordered according to a Gray ordering (see Section V-C
for a description of a Gray ordering). For a fixed $R\in(0,1)$, let
$\left\\{{\mathcal{C}}_{m}^{\text{G}}(R)\right\\}_{m\geq 1}$ be any sequence
of RM codes following a Gray coordinate ordering, such that
rate$\left(\mathcal{C}_{m}^{\text{G}}(R)\right)\xrightarrow{m\to\infty}R$. Let
$\overline{\mathsf{R}}_{{\mathcal{C}}^{\text{G}}}^{(d,\infty)}(R)$ denote the
largest rate of _linear_ $(d,\infty)$-RLL subcodes of
$\left\\{{\mathcal{C}}_{m}^{\text{G}}(R)\right\\}_{m\geq 1}$. Formally,

$\overline{\mathsf{R}}_{{\mathcal{C}}^{\text{G}}}^{(d,\infty)}(R):=\limsup_{m\to\infty}\max_{\overline{\mathcal{C}}_{\text{G}}^{(d,\infty)}\subseteq\mathcal{C}_{m}^{\text{G}}(R)}\frac{\log_{2}\left\lvert\overline{\mathcal{C}}_{\text{G}}^{(d,\infty)}\right\rvert}{2^{m}},$
(4)

where the maximization is over linear $(d,\infty)$-RLL subcodes
$\overline{\mathcal{C}}_{\text{G}}^{(d,\infty)}$ of
$\mathcal{C}_{m}^{\text{G}}(R)$. We obtain the following result:

######  Theorem III.5.

For any $R\in(0,1)$ and for any sequence of RM codes following a Gray
coordinate ordering, $\left\\{{\mathcal{C}}_{m}^{\text{G}}(R)\right\\}_{m\geq
1}$, with
rate$\left(\mathcal{C}_{m}^{\text{G}}(R)\right)\xrightarrow{m\to\infty}R$, it
holds that

$\overline{\mathsf{R}}_{{\mathcal{C}}^{\text{G}}}^{(d,\infty)}(R)\leq\frac{R}{d+1}.$

The proof of Theorem III.5 is provided in Section V-C. Again, Theorem III.5
provides an upper bound on the rates achieved over a $(d,\infty)$-RLL input-
constrained BMS channel, using linear subcodes of Gray-ordered RM codes of
rate $R$, when the sub-optimal bit-MAP decoders of
$\left\\{{\mathcal{C}}_{m}^{\text{G}}(R)\right\\}_{m\geq 1}$ are used, for
decoding.

Now, we consider arbitrary orderings of coordinates, defined by the sequence
of permutations $\left(\pi_{m}\right)_{m\geq 1}$, with
$\pi_{m}:[0:2^{m}-1]\to[0:2^{m}-1]$. As with the Gray coordinate ordering, we
define the sequence of $\pi$-ordered RM codes
$\left\\{\mathcal{C}_{m}^{\pi}(R)\right\\}_{m\geq 1}$, with

$\displaystyle\mathcal{C}_{m}^{\pi}(R):=\big{\\{}(c_{\pi_{m}(0)},c_{\pi_{m}(1)},\ldots,c_{\pi_{m}(N_{m}-1)}):(c_{0},c_{1},\ldots,c_{N_{m}-1})\in\hat{\mathcal{C}}_{m}(R)\big{\\}},$

where $\left\\{\hat{\mathcal{C}}_{m}(R)=\text{RM}(m,r_{m})\right\\}_{m\geq 1}$
is any sequence of RM codes such that
rate$(\hat{\mathcal{C}}_{m}(R))\xrightarrow{m\to\infty}R$. We also define
$\overline{\mathcal{C}}_{m}^{\pi,(d,\infty)}$ be the largest _linear_
$(d,\infty)$-RLL subcode of $\mathcal{C}_{m}^{\pi}(R)$. The theorem below is
then shown to hold:

######  Theorem III.6.

For any $R\in(0,1)$, for large $m$ and for all but a vanishing fraction of
coordinate permutations, $\pi_{m}:[0:2^{m}-1]\to[0:2^{m}-1]$, the following
rate upper bound holds:

$\frac{\log_{2}\left\lvert\overline{\mathcal{C}}_{m}^{\pi,(d,\infty)}\right\rvert}{2^{m}}\leq\frac{R}{d+1}+\epsilon_{m},$

where $\epsilon_{m}\xrightarrow{m\to\infty}0$.

Section V-C contains the proof of Theorem III.6.

Figure 3: A comparison between the upper bound of Theorem III.4 and achievable
rates of $R/2$ and $\max\left(0,R-\frac{3}{8}\right)$, from Theorems III.1 and
III.2, respectively, when $d=1$. Figure 4: A comparison between the upper
bound of Theorem III.4 and the achievable rates of [11] and [40]. For large
$\epsilon$, the upper bound of Theorem III.4, under sub-optimal decoding, lies
below the numerically-computed achievable rates in [40].

Finally, we design $(d,\infty)$-RLL constrained codes, whose rates improve on
those in Theorems III.1 and III.2, by using a two-stage (or concatenated)
encoding procedure that employs systematic RM codes of rate $R$.

######  Theorem III.7.

For any $R\in(0,1)$, there exists a sequence of $(d,\infty)$-RLL constrained
concatenated codes $\left\\{{\mathcal{C}}_{m}^{\text{conc}}\right\\}_{m\geq
1}$, constructed using systematic RM codes of rate $R$, such that

$\liminf_{m\to\infty}\text{rate}(\mathcal{C}_{m}^{\text{conc}})\geq\frac{C_{0}^{(d)}\cdot
R^{2}\cdot 2^{-\left\lceil\log_{2}(d+1)\right\rceil}}{R^{2}\cdot
2^{-\left\lceil\log_{2}(d+1)\right\rceil}+1-R+2^{-\tau}},$

where $\tau$ is an arbitrarily large, but fixed, positive integer. Further,
the rate lower bound above is achievable over a $(d,\infty)$-RLL input-
constrained BMS channel, when $R<C$, where $C$ is the capacity of the
unconstrained BMS channel.

It can be checked that the rates achieved using Theorem III.7 are better than
those achieved using Theorem III.1 (and in fact, better than those achieved
using any sequence of linear $(d,\infty)$-RLL subcodes of RM codes) and
Theorem III.2, for low noise regimes of the BMS channel. For example, when
$d=1$, the rates achieved using the codes in Theorem III.7 are better than
those achieved using linear subcodes, for $R\gtrapprox 0.7613$, and are better
than those achieved using the subcodes of Theorem III.2, for $R\lessapprox
0.55$ and $R\gtrapprox 0.79$. Figures 5 and 6 show comparisons between the
lower bounds (achievable rates) in Theorems III.1, III.2, and III.7, with the
coset-averaging bound of [23], for $d=1$ and $d=2$, respectively. While [23]
provides existence results on rates achieved using cosets of RM codes, with
the rates calculated therein being better than those in Theorem III.7 in the
low noise regimes of the BMS channel, our construction is more explicit. The
code construction leading to Theorem III.7, and the proof of achievability of
the rate lower bound, is taken up in Section VI. We mention here that Theorem
III.3 and Theorems III.5–III.7 first appeared in [41].

Figure 5: Plot comparing, for $d=1$, the rate lower bounds of
$\max\left(\frac{R}{2},R-\frac{3}{8}\right)$ achieved using subcodes, from
Theorems III.1 and III.2, with the rate lower bound achieved using Theorem
III.7, with $\tau=50$, and the coset-averaging lower bound of
$\max(0,C_{0}^{(1)}+R-1)$, of [23]. Here, the noiseless capacity,
$C_{0}^{(1)}\approx 0.6942$.

We end this section with a remark. Note that the all-ones codeword
$\mathbf{1}$ belongs to the RM code. Since any codeword $\mathbf{c}$ that
respects the $(0,1)$-RLL constraint can be written as
$\mathbf{c}=\mathbf{1}+\mathbf{\hat{c}}$, where $\mathbf{\hat{c}}$ respects
the $(1,\infty)$-RLL constraint, the lower and upper bounds of the theorems
above hold for the rate of $(0,1)$-RLL subcodes as well. Moreover, since for
any $k>1$, a $(0,1)$-RLL subcode of an RM code is a subset of a $(0,k)$-RLL
subcode, the lower bounds of Theorems III.1, III.2, and III.7, hold over
$(0,k)$-RLL input-constrained BMS channels as well.

##  IV Achievable Rates Using Subcodes

As mentioned in Section III, we work with the Reed-Muller (RM) family of
codes, $\\{\mathcal{C}_{m}(R)=\text{RM}(m,r_{m})\\}_{m\geq 1}$, under the
lexicographic coordinate ordering, with

$r_{m}=\max\left\\{\left\lfloor\frac{m}{2}+\frac{\sqrt{m}}{2}Q^{-1}(1-R)\right\rfloor,0\right\\},$

and rate $R\in(0,1)$. We then select subcodes of these codes that respect the
$(d,\infty)$-RLL constraint, and compute their rate. We first consider the
case when $d=1$. For this situation, we provide a complete characterization of
$(1,\infty)$-RLL constrained subcodes of RM codes, which will help us identify
$(1,\infty)$-RLL constrained subcodes of $\\{\mathcal{C}_{m}(R)\\}_{m\geq 1}$.
This characterization will also come of use in our derivation of upper bounds
on the rates of general (potentially non-linear) $(1,\infty)$-RLL subcodes of
RM codes, in Section V-B.

Figure 6: Plot comparing, for $d=2$, the rate lower bound of $R/4$ achieved
using subcodes, from Theorem III.1, the rate lower bound achieved using
Theorem III.7, with $\tau=50$, and the coset-averaging lower bound of
$\max(0,C_{0}^{(2)}+R-1)$, of [23]. Here, the noiseless capacity,
$C_{0}^{(2)}\approx 0.5515$.

We now set up some definitions and notation for our characterization: we
define a “run” of coordinates belonging to a set
$\mathcal{A}\in\\{0,1\\}^{m}$, to be a contiguous collection of coordinates,
$\left(i,i+1,\ldots,i+\ell-1\right)$, such that $\mathbf{B}(j)\in\mathcal{A}$,
for all $i\leq j\leq i+\ell-1$, and
$\mathbf{B}(i-1),\mathbf{B}(i+\ell)\notin\mathcal{A}$, if
$i\in[1:2^{m}-1-\ell]$, and if $i=0$ or $i=2^{m}-\ell$, we set
$\mathbf{B}(i-1)$ and $\mathbf{B}(i+\ell)$, respectively, to be the dummy
symbol $\times$, which does not belong to $\mathcal{A}$. The length of such a
run is $\ell$. For example, a run of $1$s in a vector
$\mathbf{v}\in\\{0,1\\}^{m}$ is a collection of contiguous coordinates,
$(i,\ldots,i+\ell-1)$, such that $v(i+k)=1$, for $0\leq k\leq\ell-1$. Finally,
given the code RM$(m,r)$, for $g$ as in equation (2), we let

$\Gamma(g):=\\{\boldsymbol{b}=(b_{1},\ldots,b_{m-1}):\ \boldsymbol{b}\text{ is
the end of a run of $0$s in Eval$(g)$,}\text{
$\boldsymbol{b}\neq(1,1,\ldots,1)$}\\}.$

We now present our characterization of $(1,\infty)$-RLL subcodes of the code
RM$(m,r)$:

######  Proposition IV.1.

For any Eval$(f)\in\text{RM}(m,r)$, it holds that Eval$(f)\in S_{(1,\infty)}$
if and only if the following two conditions (C1) and (C2) are simultaneously
satisfied:

(C1): supp$(\text{Eval}(g))\subseteq\text{supp}(\text{Eval}(h))$
$\displaystyle\text{(C2): $h(\boldsymbol{b})=0$, if
$\boldsymbol{b}\in\Gamma(g)$},$

where $g,h$ are as in (2).

###### Proof.

First, we shall prove that if Eval$(f)\in S_{(1,\infty)}$, then it holds that
(C1) and (C2) hold.

To show that (C1) must hold, let us assume the contrary. Suppose that there
exists some evaluation point
$\mathbf{b}=(b_{1},\ldots,b_{m-1})\in\mathbb{F}_{2}^{m-1}$ such that
$g(\mathbf{b})=1$ and $h(\mathbf{b})=0$. Then it follows that at evaluation
points $\mathbf{b}_{1},\mathbf{b}_{2}\in\mathbb{F}_{2}^{m}$ such that
$\mathbf{b}_{1}=\mathbf{b}0$ and $\mathbf{b}_{2}=\mathbf{b}1$, it holds that
$f(\mathbf{b}_{1})=f(\mathbf{b}_{2})=1$. Since by construction the points
$\mathbf{b}_{1}$ and $\mathbf{b}_{2}$ are consecutive in the lexicographic
ordering, the codeword Eval$(f)\notin S_{(1,\infty)}$.

Similarly, to show that (C2) must hold, we assume the contrary. Suppose that
there exists some evaluation point
$\mathbf{b}=\mathbf{B}(i)\in\mathbb{F}_{2}^{m-1}$, for some
$i\in[0:2^{m-1}-2]$, such that $\mathbf{b}\in\Gamma(g)$ and $h(\mathbf{b})=1$.
We let $\mathbf{b}^{\prime}=(b_{1}^{\prime},\ldots,b_{m-1}^{\prime})$ be such
that $\mathbf{b}^{\prime}=\mathbf{B}(i+1)$. We note that in the code
RM$(m,r)$, the coordinates $\mathbf{b}_{1}=\mathbf{b}1$ and
$\mathbf{b}_{2}=\mathbf{b}^{\prime}0$ occur successively. Again, by simply
evaluating (2) at the coordinates $\mathbf{b}_{1}$ and $\mathbf{b}_{2}$, we
obtain that $f(\mathbf{b}_{1})=f(\mathbf{b}_{2})=1$, implying that the
codeword Eval$(f)\notin S_{(1,\infty)}$.

Next, we shall prove the converse, i.e., that if (C1) and (C2) hold, then
Eval$(f)\in S_{(1,\infty)}$. Pick any pair of consecutive coordinates
$\mathbf{z}_{1}=\mathbf{B}(i)$ and $\mathbf{z}_{2}=\mathbf{B}(i+1)$, in the
lexicographic ordering, for some $i\in[0:2^{m}-2]$. Note that it suffices to
prove that if (C1) and (C2) hold, then it cannot be that
$f(\mathbf{z}_{1})=f(\mathbf{z}_{2})=1$. Now, consider the following two
cases, for $\mathbf{b},\mathbf{b}^{\prime}\in\\{0,1\\}^{m-1}$:

  1. 1.

$\mathbf{z}_{1}=\mathbf{b}0$ and $\mathbf{z}_{2}=\mathbf{b}1$: In this case,
if $f(\mathbf{z}_{1})=f(\mathbf{b}0)=1$, then, from the Plotkin decomposition
in (2), we see that $g(\mathbf{b})=1$. From (C1), it hence holds that
$h(\mathbf{b})=1$. Thus,
$f(\mathbf{z}_{2})=f(\mathbf{b}1)=g(\mathbf{b})+h(\mathbf{b})=0$.

  2. 2.

$\mathbf{z}_{1}=\mathbf{b}1$ and $\mathbf{z}_{2}=\mathbf{b}^{\prime}0$:
Suppose that $f(\mathbf{z}_{1})=f(\mathbf{b}1)=1$. This then implies that
$\mathbf{b}\notin\Gamma(g)$, since otherwise,
$f(\mathbf{z}_{1})=g(\mathbf{b})+h(\mathbf{b})=0$, by (C2). Further, it cannot
be that $g(\mathbf{b})=1$, as then, using (C1), we see that
$f(\mathbf{z}_{1})=g(\mathbf{b})+h(\mathbf{b})=0$. Hence, it must be that
$g(\mathbf{b})=0$ and $g(\mathbf{b}^{\prime})=0$, in which case, it
immediately holds that $f(\mathbf{z}_{2})=g(\mathbf{b}^{\prime})=0$.

∎

Given the characterization in Proposition IV.1, our first construction of a
_linear_ $(1,\infty)$-RLL subcode of $\mathcal{C}_{m}(R)$ is simply to pick
those codewords Eval$(f)\in\mathcal{C}_{m}(R)$ such that $g\equiv 0$, where
$g$ is as in equation (2). It is straightforward to verify that both (C1) and
(C2) in Proposition IV.1 are trivially satisfied.

In other words, we define the $(1,\infty)$-RLL constrained subcode
$\mathcal{C}_{m}^{(1,\infty)}(R)$ of $\mathcal{C}_{m}(R)$ to be

$\mathcal{C}_{m}^{(1,\infty)}(R):=\Big{\\{}\text{Eval}(f):f=x_{m}\cdot
h(x_{1},\ldots,x_{m-1}),\text{ where }\text{deg}(h)\leq r_{m}-1\Big{\\}}.$ (5)

Towards computing the rates of subcodes we work with in this paper, we state
and prove the following lemma:

######  Lemma IV.1.

For $r_{m}$ as defined in (1) and any sequence of positive integers
$(t_{m})_{m\geq 1}$ such that $t_{m}=o(\\!\\!\sqrt{m})$, we have

$\lim_{m\to\infty}\frac{1}{2^{m-t_{m}}}\binom{m-t_{m}}{\leq r_{m}}\ =\ R.$

In particular, for any fixed integer $t>0$,
$\lim\limits_{m\to\infty}\frac{1}{2^{m}}\binom{m-t}{\leq r_{m}}=2^{-t}R$.

###### Proof.

Let $S_{m}$ denote a Bin$(m,\frac{1}{2})$ random variable, and note that
$\frac{1}{2^{m-t_{m}}}\binom{m-t_{m}}{\leq r_{m}}$ equals $\Pr[S_{m-t_{m}}\leq
r_{m}]$. Further note that by our choice of $r_{m}$, for any integer $t>0$, we
have for all $m$ large enough,

$\displaystyle|r_{m}-r_{m-t}|$
$\displaystyle\leq\biggl{|}\frac{m}{2}+\frac{\sqrt{m}}{2}Q^{-1}(1-R)\,-\
\left(\frac{m-t}{2}+\frac{\sqrt{m-t}}{2}Q^{-1}(1-R)\right)+1\biggr{|}$
$\displaystyle\leq\frac{t}{2}+\frac{\sqrt{t}}{2}\lvert Q^{-1}(1-R)\rvert+1.$
(6)

Hence, we have $r_{m-t_{m}}-\nu_{m}\leq r_{m}\leq r_{m-t_{m}}+\nu_{m}$, with
$\nu_{m}:=\frac{t_{m}}{2}+\frac{\sqrt{t_{m}}}{2}\lvert Q^{-1}(1-R)\rvert+1$.
Consequently, $\Pr[S_{m-t_{m}}\leq r_{m-t_{m}}-\nu_{m}]\leq\Pr[S_{m-t_{m}}\leq
r_{m}]\leq\Pr[S_{m-t_{m}}\leq r_{m-t_{m}}+\nu_{m}]$. Setting
$\overline{S}_{m-t_{m}}:=\frac{S_{m-t_{m}}-\frac{1}{2}(m-t_{m})}{\frac{1}{2}\sqrt{m-t_{m}}}$,
we have

$\displaystyle\Pr[\overline{S}_{m-t_{m}}\leq
Q^{-1}(1-R)-\frac{\nu_{m}}{\frac{1}{2}\sqrt{m-t_{m}}}]\ \leq\
\Pr[S_{m-t_{m}}\leq r_{m}]\ \leq\ \Pr[\overline{S}_{m-t_{m}}\leq
Q^{-1}(1-R)+\frac{\nu_{m}}{\frac{1}{2}\sqrt{m-t_{m}}}].$ (7)

Now, by the central limit theorem (or, in this special case, by the de Moivre-
Laplace theorem), $\overline{S}_{m-t_{m}}$ converges in distribution to a
standard normal random variable, $Z$. Therefore, via (7) and the fact that
$t_{m}$ and $\nu_{m}$ are both $o(\\!\\!\sqrt{m})$, we obtain that

$\lim_{m\to\infty}\Pr[S_{m-t_{m}}\leq r_{m}]\ =\ \Pr[Z\leq Q^{-1}(1-R)]\ =\
R,$

which proves the lemma. ∎

From Lemma IV.1, we calculate the rate of the $(1,\infty)$-RLL constrained
subcode $\mathcal{C}_{m}^{(1,\infty)}(R)$ in (5) as:

$\displaystyle\text{rate}\left(\mathcal{C}_{m}^{(1,\infty)}(R)\right)\ $
$\displaystyle=\
\frac{\log_{2}\left(\left\lvert\mathcal{C}_{m}^{(1,\infty)}\right\rvert\right)}{2^{m}}$
$\displaystyle=\ \frac{{m-1\choose\leq r_{m}-1}}{2^{m}}\ =\
\frac{\binom{m-1}{\leq r_{m}-1}}{\binom{m-1}{\leq
r_{m}}}\,\frac{{m-1\choose\leq r_{m}}}{2^{m}}\ \xrightarrow{m\to\infty}\
\frac{R}{2}.$ (8)

We now extend our simple construction of linear $(1,\infty)$-RLL subcodes in
(5) and the rate computation in (8) to general $d$, thereby proving Theorem
III.1. But before we do so, we state a simple observation, presented below as
a lemma. We recall the definition of the support of a vector
$\mathbf{c}\in\mathbb{F}_{2}^{n}$: $\text{supp}(\mathbf{c})=\\{i:c_{i}=1\\}.$

######  Lemma IV.2.

Given $d\geq 1$, if $\hat{\mathbf{c}}$ is such that $\hat{\mathbf{c}}\in
S_{(d,\infty)}$, and supp$(\mathbf{c})\subseteq\text{supp}(\hat{\mathbf{c}})$,
then it holds that $\mathbf{c}\in S_{(d,\infty)}$.

We are now in a position to prove Theorem III.1.

###### Proof of Theorem III.1.

For a fixed $d\geq 1$, let $z:=\left\lceil\log_{2}(d+1)\right\rceil$. Consider
the subcode $\mathcal{C}_{m}^{(d,\infty)}(R)$, of the code
$\mathcal{C}_{m}(R)$, defined as:

$\displaystyle\mathcal{C}_{m}^{(d,\infty)}(R):=\Bigg{\\{}\text{Eval}(f):f=\bigg{(}\prod_{i=m-z+1}^{m}x_{i}\bigg{)}\cdot
h(x_{1},\ldots,x_{m-z}),$ $\displaystyle\text{ where }\text{deg}(h)\leq
r_{m}-z\Bigg{\\}}.$

It is easy to verify that the polynomial
$q(x_{m-z+1},\ldots,x_{m}):=\prod_{i=m-z+1}^{m}x_{i}$ is such that its
corresponding evaluation vector, Eval$(q)$, obeys Eval$(q)\in
S_{(d,\infty)}^{(2^{m})}$. This is because Eval${}_{\mathbf{y}}(q)=1$ if and
only if $(y_{m-z+1},\ldots,y_{m})=(1,\ldots,1)$, and in the lexicographic
ordering, such evaluation points $\mathbf{y}$ are spaced out by $2^{z}-1$
coordinates, where $2^{z}-1\geq d$. Now, for any polynomial $f$ such that
$\text{Eval}(f)\in\mathcal{C}_{m}^{(d,\infty)}(R)$, it is true that
supp$(\text{Eval}(f))\subseteq\text{supp}(\text{Eval}(q))$. Hence, Eval$(f)\in
S_{(d,\infty)}^{(2^{m})}$ via Lemma IV.2.

Finally, the rate of the subcode $\mathcal{C}_{m}^{(d,\infty)}(R)$ can be
calculated as follows:

$\displaystyle\text{rate}\left(\mathcal{C}_{m}^{(d,\infty)}(R)\right)\ $
$\displaystyle=\
\frac{\log_{2}\left(\left\lvert\mathcal{C}_{m}^{(d,\infty)}\right\rvert\right)}{2^{m}}$
$\displaystyle=\ \frac{{m-z\choose\leq r_{m}-z}}{2^{m}}\ =\
\frac{\binom{m-z}{\leq r_{m}-z}}{\binom{m-z}{\leq
r_{m}}}\,\frac{{m-z\choose\leq r_{m}}}{2^{m}}\ \xrightarrow{m\to\infty}\
2^{-z}R.$

To obtain the limit as $m\to\infty$, we have used Lemma IV.1 and the fact that
the ratio $\frac{\binom{m-z}{\leq r_{m}-z}}{\binom{m-z}{\leq r_{m}}}$
converges to $1$ as $m\to\infty$. Towards proving this fact, note that

$\displaystyle\binom{m-z}{\leq r_{m}-z}$ $\displaystyle=\binom{m-z}{\leq
r_{m}}-\sum_{i=r_{m}-z+1}^{r_{m}}\binom{m-z}{i}$
$\displaystyle\geq\binom{m-z}{\leq
r_{m}}-z\cdot\binom{m-z}{\left\lfloor\frac{m-z}{2}\right\rfloor},$

and hence, we have that

$1-\frac{z\cdot\binom{m-z}{\left\lfloor\frac{m-z}{2}\right\rfloor}}{\binom{m-z}{\leq
r_{m}}}\ \leq\ \frac{\binom{m-z}{\leq r_{m}-z}}{\binom{m-z}{\leq r_{m}}}\ \leq
1.$

Now, consider the expression
$\frac{z\cdot\binom{m-z}{\left\lfloor\frac{m-z}{2}\right\rfloor}}{\binom{m-z}{\leq
r_{m}}}$. We have that
$\lim_{m\to\infty}\frac{z\cdot\binom{m-z}{\left\lfloor\frac{m-z}{2}\right\rfloor}}{2^{m}}=0$
(in fact, it holds that
$\frac{z\cdot\binom{m-z}{\left\lfloor\frac{m-z}{2}\right\rfloor}}{2^{m}}=O\left(\frac{1}{\sqrt{m-z}}\right)$)
and that $\lim_{m\to\infty}\frac{\binom{m-z}{\leq r_{m}}}{2^{m}}=2^{-z}R$
(from Lemma IV.1). Hence, it follows that
$1-\frac{z\cdot\binom{m-z}{\left\lfloor\frac{m-z}{2}\right\rfloor}}{\binom{m-z}{\leq
r_{m}}}$ converges to $1$, as $m\to\infty$, implying that the ratio
$\frac{\binom{m-z}{\leq r_{m}-z}}{\binom{m-z}{\leq r_{m}}}$ also converges to
$1$ as $m\to\infty$. ∎

Now, we proceed to proving Theorem III.2, which establishes the existence of
$(1,\infty)$-RLL subcodes of rates better than those in Theorem III.1. Before
we do so, we state and prove a useful lemma on the expected number of runs of
$1$s in a codeword of a linear code with dual distance at least $3$. Let
$\mathcal{C}^{\perp}$ denote the dual code of a given length-$n$ linear code
$\mathcal{C}$, and for a binary vector $\mathbf{v}\in\\{0,1\\}^{n}$, let
$\tau_{0}(\mathbf{v})$ and $\tau_{1}(\mathbf{v})$ be the number of runs of
$0$s and $1$s, respectively, in $\mathbf{v}$, with
$\tau(\mathbf{v}):=\tau_{0}(\mathbf{v})+\tau_{1}(\mathbf{v})$.

######  Lemma IV.3.

Let $\mathcal{C}$ be an $[N,K]$ linear code with
$\text{d}_{\text{min}}(\mathcal{C}^{\perp})\geq 3$. Then, by drawing codewords
$\mathbf{c}\in\mathcal{C}$ uniformly at random, we have that

$\mathbb{E}_{\mathbf{c}\sim\text{Unif}(\mathcal{C})}[\tau(\mathbf{c})]=\frac{N+1}{2}.$

Further,

$\mathbb{E}_{\mathbf{c}\sim\text{Unif}(\mathcal{C})}[\tau_{0}(\mathbf{c})]=\mathbb{E}_{\mathbf{c}\sim\text{Unif}(\mathcal{C})}[\tau_{1}(\mathbf{c})]=\frac{N+1}{4}.$

###### Proof.

To prove the first part, we note that for any $\mathbf{c}\in\mathcal{C}$,
whose coordinates are indexed by $0,1,2,\ldots,N-1$,

$\tau(\mathbf{c})=1+\\#\\{0\leq i\leq N-2:(c_{i},c_{i+1})=(0,1)\text{ or
}(c_{i},c_{i+1})=(1,0)\\}.$ (9)

Further, since $\mathcal{C}^{\perp}$ has distance at least $3$, it implies
that in any two coordinates $i\neq j$ of $\mathcal{C}$, all binary $2$-tuples
occur, and each with frequency $\frac{1}{4}$. In particular, from (9), we have
that

$\displaystyle\mathbb{E}_{\mathbf{c}\sim\text{Unif}(\mathcal{C})}[\tau(\mathbf{c})]$
$\displaystyle=1+\sum_{i=0}^{N-2}\mathbb{E}[\mathds{1}\\{(c_{i},c_{i+1})=(0,1)\\}+\mathds{1}\\{(c_{i},c_{i+1})=(1,0)\\}]$
$\displaystyle=1+\sum_{i=0}^{N-2}\bigg{(}\text{Pr}[(c_{i},c_{i+1})=(0,1)]+\text{Pr}[(c_{i},c_{i+1})=(1,0)]\bigg{)}$
$\displaystyle=1+\sum_{i=0}^{N-2}\frac{1}{2}=\frac{N+1}{2}.$

To prove the second part, we note that since
$\mathbb{E}[\tau(\mathbf{c})]=\mathbb{E}[\tau_{0}(\mathbf{c})]+\mathbb{E}[\tau_{1}(\mathbf{c})]$,
it suffices to show that
$\mathbb{E}[\tau_{0}(\mathbf{c})]=\mathbb{E}[\tau_{1}(\mathbf{c})]$, when
$\mathbf{c}$ is drawn uniformly at random from $\mathcal{C}$. To this end,
observe that given any codeword $\mathbf{c}\in\mathcal{C}$, we have that

$\tau_{1}(\mathbf{c})-\tau_{0}(\mathbf{c})=\begin{cases}1,\ \text{if
$c_{0}=c_{N-1}=1$},\\\ -1,\ \text{if $c_{0}=c_{N-1}=0$},\\\ 0,\
\text{otherwise}.\end{cases}$

Hence, when $\mathbf{c}$ is drawn uniformly at random from $\mathcal{C}$,

$\displaystyle\mathbb{E}[\tau_{1}(\mathbf{c})]-\mathbb{E}[\tau_{0}(\mathbf{c})]$
$\displaystyle=\mathbb{E}[\mathds{1}\\{(c_{0},c_{N-1})=(1,1)\\}]-\mathbb{E}[\mathds{1}\\{(c_{0},c_{N-1})=(0,0)\\}]$
$\displaystyle=\frac{1}{4}-\frac{1}{4}=0,$

thereby proving that
$\mathbb{E}[\tau_{0}(\mathbf{c})]=\mathbb{E}[\tau_{1}(\mathbf{c})]$. ∎

The following standard coding-theoretic fact will also prove useful (see [35]
or [42] for discussions on shortening codes):

######  Lemma IV.4.

Consider an $[N,K]$ linear code $\mathcal{C}$, and let $T\subseteq[0:N-1]$ be
a collection of its coordinates. If $\mathcal{C}\big{\rvert}_{T}$ denotes the
restriction of $\mathcal{C}$ to the coordinates in $T$, and $\mathcal{C}_{T}$
denotes the code obtained by shortening $\mathcal{C}$ at the coordinates in
$T$, then

$\text{dim}(\mathcal{C}_{T})=K-\text{dim}(\mathcal{C}\big{\rvert}_{T}).$

In particular, we have that

$\text{dim}(\mathcal{C}_{T})\geq K-|T|.$

Now, we move on to the proof of Theorem III.2.

###### Proof of Theorem III.2.

Fix any sequence of codes
$\left\\{\hat{\mathcal{C}}_{m}(R)=\text{RM}(m,r_{m})\right\\}_{m\geq 1}$ of
rate $R\in(0,1)$. Let $\hat{\mathcal{C}}_{m}^{(1,\infty)}$ be the largest
$(1,\infty)$-RLL subcode of $\hat{\mathcal{C}}_{m}(R)$. Let
$\hat{\mathcal{C}}_{m}^{(g)}:=\text{RM}(m-1,r_{m})$ and
$\hat{\mathcal{C}}_{m}^{(h)}:=\text{RM}(m-1,r_{m}-1)$. The following set of
equalities then holds:

$\displaystyle\left\lvert\hat{\mathcal{C}}^{(1,\infty)}_{m}\right\rvert$
$\displaystyle=\sum_{f:\ \text{deg}(f)\leq
r_{m}}\mathds{1}\\{\text{Eval}(f)\in S_{(1,\infty)}\\}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{g:\ \text{deg}(g)\leq
r_{m}}\sum_{h:\ \text{deg}(h)\leq r_{m}-1}\mathds{1}\\{(g,h)\text{ satisfy
(C1) and (C2)}\\}$
$\displaystyle=\left\lvert\hat{\mathcal{C}}_{m}^{(g)}\right\rvert\cdot\mathbb{E}_{\text{Eval}(g)\sim\text{Unif}(\hat{\mathcal{C}}_{m}^{(g)})}\left[\sum_{h:\
\text{deg}(h)\leq r_{m}-1}\mathds{1}\\{(g,h)\text{ satisfy (C1) and
(C2)}\\}\right]$
$\displaystyle=\left\lvert\hat{\mathcal{C}}_{m}^{(g)}\right\rvert\cdot\mathbb{E}_{\text{Eval}(g)\sim\text{Unif}(\hat{\mathcal{C}}_{m}^{(g)})}\left[\\#\\{h:(g,h)\text{
satisfy (C1) and (C2)}\\}\right],$ (10)

where (a) holds from Proposition IV.1. The following fact will be of use to
us: if
$\hat{R}_{m}^{(g)}:=\text{rate}\left(\hat{\mathcal{C}}_{m}^{(g)}\right)$ and
$\hat{R}_{m}^{(h)}:=\text{rate}\left(\hat{\mathcal{C}}_{m}^{(h)}\right)$, then

$\displaystyle\hat{R}_{m}^{(g)}+\hat{R}_{m}^{(h)}$
$\displaystyle=\frac{{m-1\choose\leq r_{m}}+{m-1\choose\leq
r_{m}-1}}{2^{m-1}}\xrightarrow{m\to\infty}2R.$

Now, from the definitions of (C1) and (C2) in Proposition IV.1, we have that
for a fixed Eval$(g)\in\hat{\mathcal{C}}_{m}^{(g)}$,

$\displaystyle\\#\\{h:(g,h)\text{ satisfy (C1) and (C2)}\\}$
$\displaystyle=\\#\\{h:h(\mathbf{b})=1\ \forall\
\mathbf{b}\in\text{supp}(\text{Eval}(g)),\text{ and }h(\mathbf{b}^{\prime})=0\
\forall\ \mathbf{b}^{\prime}\in\Gamma(g)\\}$

The right-hand side of the above equality is precisely the number of codewords
in the code obtained by shortening $\hat{\mathcal{C}}_{m}^{(h)}$ at the
coordinates in $S:=\text{supp}(\text{Eval}(g))\cup\Gamma(g)$. Note that

$|S|=\left\lvert\text{supp}(\text{Eval}(g))\right\rvert+\left\lvert\Gamma(g)\right\rvert\leq\text{wt}(\text{Eval}(g))+\tau_{0}(\text{Eval}(g)).$

Hence, from the second part of Lemma IV.4, we have that

$\displaystyle\\#\\{h:(g,h)\text{ satisfy (C1) and
(C2)}\\}\geq\text{exp}_{2}\left({2^{m-1}\cdot\hat{R}_{m}^{(h)}-\left(\text{wt}(\text{Eval}(g))+\tau_{0}(\text{Eval}(g))\right)}\right)$
(11)

Plugging (11) back in equation (10), we get that for $m$ large enough,

$\displaystyle\left\lvert\hat{\mathcal{C}}^{(1,\infty)}_{m}\right\rvert$
$\displaystyle\geq\left\lvert\hat{\mathcal{C}}_{m}^{(g)}\right\rvert\cdot\mathbb{E}_{\text{Eval}(g)\sim\text{Unif}(\hat{\mathcal{C}}_{m}^{(g)})}\left[\text{exp}_{2}\left({2^{m-1}\cdot\left(\hat{R}_{m}^{(h)}-\frac{\text{wt}(\text{Eval}(g))}{2^{m-1}}-\frac{\tau_{0}(\text{Eval}(g))}{2^{m-1}}\right)}\right)\right]$
(12)
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\geq}}\left\lvert\hat{\mathcal{C}}_{m}^{(g)}\right\rvert\cdot\text{exp}_{2}\left({2^{m-1}\cdot\left(\hat{R}_{m}^{(h)}-\frac{\mathbb{E}[\text{wt}(\text{Eval}(g))]}{2^{m-1}}-\frac{\mathbb{E}[\tau_{0}(\text{Eval}(g))]}{2^{m-1}}\right)}\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\left\lvert\hat{\mathcal{C}}_{m}^{(g)}\right\rvert\cdot\text{exp}_{2}\left({2^{m-1}\cdot\left(\hat{R}_{m}^{(h)}-\frac{1}{2}-\frac{1}{4}-\delta_{m}\right)}\right)$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}\text{exp}_{2}\left(2^{m}\cdot\left(\frac{\hat{R}_{m}^{(g)}+\hat{R}_{m}^{(h)}}{2}-\frac{3}{8}-\frac{\delta_{m}}{2}\right)\right),$

where $\delta_{m}:=\frac{1}{4\cdot 2^{m-1}}\xrightarrow{m\to\infty}0$. Here,
(b) holds by an application of Jensen’s inequality and the linearity of
expectation, and (c) holds by Lemma IV.3, since the dual code of
$\hat{\mathcal{C}}_{m}^{(g)}$ has minimum distance at least $3$, for $m$ large
enough. Finally, (d) holds from the fact that
$\left\lvert\hat{\mathcal{C}}_{m}^{(g)}\right\rvert=\text{exp}_{2}\left(2^{m-1}\cdot\hat{R}_{m}^{(g)}\right)$.

Hence, we get that the largest rate of $(1,\infty)$-RLL constrained subcodes
of $\left\\{\hat{\mathcal{C}}_{m}(R)\right\\}_{m\geq 1}$ obeys

$\displaystyle\mathsf{R}^{(1,\infty)}_{\hat{\mathcal{C}}}(R)$
$\displaystyle=\limsup_{m\to\infty}\max_{\hat{\mathcal{C}}^{(1,\infty)}\subseteq\hat{\mathcal{C}}_{m}(R)}\frac{\log_{2}\left\lvert\hat{\mathcal{C}}^{(1,\infty)}\right\rvert}{2^{m}}$
$\displaystyle\geq\limsup_{m\to\infty}\frac{2^{m}\cdot\left(\frac{\hat{R}_{m}^{(g)}+\hat{R}_{m}^{(h)}}{2}-\frac{3}{8}-\frac{\delta_{m}}{2}\right)}{2^{m}}$
$\displaystyle=R-\frac{3}{8}.$

Thus, there exists a sequence
$\left\\{\tilde{\mathcal{C}}_{m}^{(1,\infty)}(R)\right\\}_{m\geq 1}$ of
$(1,\infty)$-RLL constrained subcodes of any sequence of RM codes
$\\{\hat{\mathcal{C}}_{m}(R)\\}_{m\geq 1}$ of rate $R$, such that the subcodes
achieve a rate of at least $\max\left(0,R-\frac{3}{8}\right)$ over a
$(1,\infty)$-RLL input-constrained BMS channel. ∎

Although Theorem III.2 proves the existence of non-linear $(1,\infty)$-RLL
subcodes of rate larger than (for high rates $R$) that of the linear subcodes
of Theorem III.1, it is of interest to check if further improvements on the
rates of $(1,\infty)$-RLL constrained subcodes are possible, by performing
numerical computations. For a fixed $R\in(0,1)$, we work with the sequence of
RM codes $\left\\{\hat{\mathcal{C}}_{m}(R)=\text{RM}(m,v_{m})\right\\}_{m\geq
1}$, where

$v_{m}:=\min\left\\{u:\sum_{i=0}^{u}\binom{m}{i}\geq\left\lfloor 2^{m}\cdot
R\right\rfloor\right\\}.$

It can be checked that
rate$\left(\hat{\mathcal{C}}_{m}(R)\right)\xrightarrow{m\to\infty}R$. We then
have from inequality (12) that

$\mathsf{R}^{(1,\infty)}_{\hat{\mathcal{C}}}(R)\geq\max\left\\{0,\limsup_{m\to\infty}\left(\frac{\hat{R}_{m}^{(g)}+\hat{R}_{m}^{(h)}}{2}+\frac{\log_{2}\left(\mathbb{E}\left[\text{exp}_{2}\left(-\text{wt}(\text{Eval}(g))-\tau_{0}(\text{Eval}(g))\right)\right]\right)}{2^{m}}\right)\right\\},$
(13)

where the expectation is taken over codewords
$\text{Eval}(g)\sim\text{Unif}(\hat{\mathcal{C}}_{m}^{(g)})$. Inequality (13)
suggests that one can estimate a lower bound on
$\mathsf{R}^{(1,\infty)}_{\hat{\mathcal{C}}}(R)$, by picking a large $m$ and
replacing the expectation by a sample average over codewords $\text{Eval}(g)$
chosen uniformly at random from $\hat{\mathcal{C}}_{m}^{(g)}$. We can then
obtain a new (numerical) lower bound, which does not make use of a further
lower bounding argument via Jensen’s inequality. We performed this Monte-Carlo
sampling and estimation procedure, with $m=11$, and for varying values of $R$,
by averaging over $10^{4}$ uniformly random samples of codewords,
$\text{Eval}(g)$. Figure 7 shows a plot comparing the lower bound in (13),
with the lower bound that is approximately $\hat{R}_{m}-\frac{3}{8}$, from
Theorem III.2, where $\hat{R}_{m}:=$
rate$\left(\hat{\mathcal{C}}_{m}(R)\right)$. We observe that there is a
noticeable improvement in the numerical rate lower bound, as compared to the
bound in Theorem III.2, for some values of $\hat{R}_{m}$.

Figure 7: Plot comparing, for $d=1$, the rate lower bound of approximately
$\hat{R}_{m}-\frac{3}{8}$, from Theorem III.2, with the numerical lower bound
obtained by Monte-Carlo simulation, using (13).

##  V Upper Bounds on Rates of Constrained Subcodes

In this section, we derive upper bounds on the rates of $(d,\infty)$-RLL
constrained subcodes of RM codes of rate $R\in(0,1)$. In the first subsection,
we restrict our subcodes to be linear, while in the second subsection, we fix
$d$ to be $1$ and relax the assumption of linearity of the subcodes.
Additionally, in the first two subsections, we assume that the RM codes follow
a lexicographic coordinate ordering. We consider RM codes under other
coordinate orderings in the last subsection, and derive upper bounds on the
rates of linear $(d,\infty)$-RLL constrained subcodes.

###  V-A Linear Subcodes

We fix a sequence of codes
$\left\\{\hat{\mathcal{C}}_{m}(R)=\text{RM}(m,r_{m})\right\\}_{m\geq 1}$ of
rate $R$, whose coordinates follow a lexicographic ordering. We first state
and prove a fairly general proposition on the rates of linear $(d,\infty)$-RLL
subcodes of linear codes. Recall that for an $[N,K]$ linear code $\mathcal{C}$
over $\mathbb{F}_{2}$, of blocklength $N$ and dimension $K$, an information
set is a collection of $K$ coordinates in which all possible $K$-tuples over
$\mathbb{F}_{2}$ can appear. Equivalently, if $G$ is any generator matrix for
$\mathcal{C}$, an information set is a set of $K$ column indices such that $G$
restricted to those columns is a full-rank matrix. As usual, we index the
coordinates of the code from $0$ to $N-1$.

######  Proposition V.1.

Let ${\mathcal{C}}$ be an $[N,K]$ binary linear code. If $\mathcal{I}$ is an
information set of ${\mathcal{C}}$ that contains $t$ disjoint $(d+1)$-tuples
of consecutive coordinates
$(i_{1},i_{1}+1,\ldots,i_{1}+d),(i_{2},i_{2}+1,\ldots,i_{2}+d),...,(i_{t},i_{t}+1,\ldots,i_{t}+d)$,
with $i_{1}\geq 0$, $i_{j}>i_{j-1}+d$, for all $j\in[2:t]$, and $i_{t}\leq
N-1-d$, then the dimension of any linear $(d,\infty)$-RLL subcode of
${\mathcal{C}}$ is at most $K-dt$.

###### Proof.

Suppose that the information set $\mathcal{I}$ contains exactly $t$ disjoint
$(d+1)$-tuples of consecutive coordinates as in the statement of the
proposition. By definition, all possible $K$-tuples appear in the coordinates
in $\mathcal{I}$. Now, consider any linear $(d,\infty)$-RLL subcode
$\overline{\mathcal{C}}$ of ${\mathcal{C}}$, and any $(d+1)$-tuple of
consecutive coordinates $\\{i_{j},i_{j}+1,\ldots,i_{j}+d\\}\in\mathcal{I}$,
for $j\in[t]$. Since the $(d,\infty)$-RLL constraint requires that successive
$1$s be separated by at least $d$ $0$s, the only possible tuples of $d+1$
consecutive symbols in any codeword of the linear subcode are $(0,0,\ldots,0)$
and at most one of $\mathbf{e}_{i}^{(d+1)}$, $i\in[d+1]$. This is because, if
$\mathbf{e}_{i}^{(d+1)}$ and $\mathbf{e}_{j}^{(d+1)}$ both occur in a
collection of $d+1$ consecutive positions, then, by linearity of the subcode
$\overline{\mathcal{C}}$, it holds that
$\mathbf{e}_{i}^{(d+1)}+\mathbf{e}_{j}^{(d+1)}$ (where the addition is over
vectors in $\mathbb{F}_{2}^{d+1}$) must occur in some codeword of the subcode,
thereby making the codeword not $(d,\infty)$-RLL compliant. Hence, for every
$(d+1)$-tuple of consecutive coordinates in $\mathcal{I}$, only a $2^{-d}$
fraction of the $2^{d+1}$ possible tuples are allowed. Thus, overall, the
number of possible $K$-tuples that can appear in the information set
$\mathcal{I}$ in the codewords of the linear subcode is at most
$\frac{2^{K}}{2^{dt}}$. Hence, the number of codewords in the linear subcode
is at most $2^{K-dt}$.

∎

In order to obtain an upper bound, as in Theorem III.3, on the rate of linear
$(d,\infty)$-RLL subcodes of the sequence of codes
$\left\\{\hat{\mathcal{C}}_{m}(R)\right\\}_{m\geq 1}$, we shall first identify
an information set of ${\hat{\mathcal{C}}_{m}(R)}=\text{RM}(m,r_{m})$. We then
compute the number of disjoint $(d+1)$-tuples of consecutive coordinates in
the information set, and apply Proposition V.1 to get an upper bound on the
dimension of the linear constrained subcodes.

Given the integers $m$ and $r$, consider the binary linear code (a subspace of
$\mathbb{F}_{2}^{2^{m}}$), $\tilde{\mathcal{C}}({m,r})$, spanned by the
codewords in the set

$\mathcal{B}_{m,r}:=\left\\{\text{Eval}\left(\prod_{i\in
S}x_{i}\right):S\subseteq[m]\ \text{with }|S|\geq r+1\right\\}.$ (14)

From the discussion in Section II-C, it holds that vectors in
$\mathcal{B}_{m,r}$ are linearly independent, and, hence, $\mathcal{B}_{m,r}$
forms a basis for $\tilde{\mathcal{C}}({m,r})$, with
dim$\left(\tilde{\mathcal{C}}({m,r})\right)={m\choose\geq r+1}$. Moreover, the
codewords in $\tilde{\mathcal{C}}({m,r})$ are linearly independent from
codewords in RM$(m,r)$, since the evaluation vectors of all the distinct
monomials in the variables $x_{1},\ldots,x_{m}$ are linearly independent over
$\mathbb{F}_{2}$.

The following lemma identifies an alternative basis for
$\tilde{\mathcal{C}}({m,r})$, which will prove useful in our analysis, later
on.

######  Lemma V.1.

Consider the code
$\tilde{\mathcal{C}}({m,r})=\text{span}\left(\mathcal{B}_{m,r}\right)$, where
$\mathcal{B}_{m,r}$ is as in (14). It holds that
$\tilde{\mathcal{C}}({m,r})=\text{span}\left(\\{\mathbf{e}_{\mathbf{b}}:\text{wt}(\mathbf{b})\geq
r+1\\}\right)$.

###### Proof.

Note that any standard basis vector $\mathbf{e}_{\mathbf{b}}$, with
wt$(\mathbf{b})\geq r+1$, can be written as Eval$(f)$, where

$f(x_{1},\ldots,x_{m})=\prod_{i\in\text{supp}(\mathbf{b})}x_{i}\cdot\prod_{i\notin\text{supp}(\mathbf{b})}(1+x_{j}).$

From the fact that wt$(\mathbf{b})\geq r+1$, it holds that the degree of any
monomial in $f$ is at least $r+1$, and hence,
Eval$(f)=\mathbf{e}_{\mathbf{b}}\in\text{span}(\mathcal{B}_{m,r})=\tilde{\mathcal{C}}({m,r})$.
The result follows by noting that
$\\{\mathbf{e}_{\mathbf{b}}:\text{wt}(\mathbf{b})\geq r+1\\}$ is a collection
of linearly independent vectors of size ${m\choose\geq r+1}$, which, in turn,
equals dim$\left(\tilde{\mathcal{C}}({m,r})\right)$. ∎

We now introduce some further notation: given a $p\times q$ matrix $M$, we use
the notation $M[\mathcal{U},\mathcal{V}]$ to denote the submatrix of $M$
consisting of the rows in the set $\mathcal{U}\subseteq[p]$ and the columns in
the set $\mathcal{V}\subseteq[q]$. We recall the definition of the generator
matrix $G_{\text{Lex}}(m,r)$, of RM$(m,r)$, and the indexing of columns of the
matrix, from Section II-C. Finally, towards identifying an information set of
RM$(m,r)$, we define the set of coordinates

$\mathcal{I}_{m,r}:=\\{\mathbf{b}=(b_{1},\ldots,b_{m})\in\mathbb{F}_{2}^{m}:\text{wt}(\mathbf{b})\leq
r\\}.$ (15)

######  Lemma V.2.

The set of coordinates $\mathcal{I}_{m,r}$ is an information set of
$\text{RM}(m,r)$.

###### Proof.

In order to prove that $\mathcal{I}_{m,r}$ is an information set of RM$(m,r)$,
it is sufficient to show that $G_{\text{Lex}}(m,r)$ restricted to the columns
in $\mathcal{I}_{m,r}$ is of full rank.

Now, consider the generator matrix $\tilde{G}(m,r)$, of
$\tilde{\mathcal{C}}(m,r)$, consisting of rows that are vectors in
$\mathcal{B}_{m,r}$. We build the $2^{m}\times 2^{m}$ matrix

$\mathsf{H}:=\begin{bmatrix}\begin{array}[]{c}\tilde{G}(m,r)\\\ \hline\cr\\\
G_{\text{Lex}}(m,r)\end{array}\end{bmatrix},$

with $\mathsf{H}$ being full rank. Note that, from Lemma V.1, any standard
basis vector $\mathbf{e}_{\mathbf{b}}$, with
$\mathbf{b}\in\mathcal{I}_{m,r}^{c}$, belongs to rowspace$(\tilde{G}(m,r))$.
By Gaussian elimination, it is then possible to replace the first
${m\choose\geq r+1}$ rows of $\mathsf{H}$, corresponding to the submatrix
$\tilde{G}(m,r)$, with the standard basis vectors $\mathbf{e}_{\mathbf{b}}$,
with $\mathbf{b}\in\mathcal{I}_{m,r}^{c}$. Clearly, from the fact that
$\mathsf{H}$ is full rank, this then means that
$\mathsf{H}\left[\left[{m\choose\geq
r+1}+1:2^{m}\right],\mathcal{I}_{m,r}\right]$ is full rank, or equivalently,
$G_{\text{Lex}}(m,r)$ restricted to columns in $\mathcal{I}_{m,r}$ is full
rank. ∎

We thus have that an information set of $\hat{\mathcal{C}}_{m}(R)$ is
$\mathcal{I}_{m,r_{m}}$. Note that in order to get an upper bound on the rate
of linear $(d,\infty)$-RLL subcodes of $\hat{\mathcal{C}}_{m}(R)$, we need
only calculate the number of disjoint $(d+1)$-tuples of consecutive
coordinates in $\mathcal{I}_{m,r_{m}}$.

To this end, for any $0\leq r\leq m-1$, we define

$\displaystyle\Gamma_{m,r}:=\left\\{s\in[0:2^{m}-2]:\mathbf{B}(s)\in\mathcal{I}_{m,r},\text{
but }\mathbf{B}(s+1)\notin\mathcal{I}_{m,r}\right\\},$ (16)

to be the set of right end-point coordinates of runs that belong to
$\mathcal{I}_{m,r}$. The number of such runs is
$\left\lvert\Gamma_{m,r}\right\rvert$. Observe that since $r\leq m-1$, it
holds that $2^{m}-1\notin\mathcal{I}_{m,r}$. In the case where $r=m$, we have
that $\mathcal{I}_{m,r}=[0:2^{m}-1]$, and we define $\Gamma_{m,r}$ to be
$\\{2^{m}-1\\}$. However, this special case need not be considered, for our
purposes.

######  Lemma V.3.

For $0\leq r\leq m-1$, it holds that
$\left\lvert\Gamma_{m,r}\right\rvert={m-1\choose r}$.

###### Proof.

Let $r\in[0:m-1]$. Note that every right end-point of a run,
$s\in\Gamma_{m,r}$, with $s\in[0:2^{m}-2]$, is such that
wt$(\mathbf{B}(s))\leq r$, but wt$(\mathbf{B}(s+1))\geq r+1$. We now claim
that an integer $s\in\Gamma_{m,r}$ iff B$(s)=(b_{1},\ldots,b_{m-1},0)$, for
$b_{1},\ldots,b_{m-1}\in\\{0,1\\}$, with wt$((b_{1},\ldots,b_{m-1},0))=r$.

To see this, note that if B$(s)=(b_{1},\ldots,b_{m-1},0)$, then
B$(s+1)=(b_{1},\ldots,b_{m-1},1)$. Hence, if wt$((b_{1},\ldots,b_{m-1}))=r$,
then $s\in\Gamma_{m,r}$. Conversely, if $s\in\Gamma_{m,r}$, then B$(s)$ cannot
end in a $1$. Indeed, if this were the case, then we would have B$(s)$ being
of the form $(b_{1},\ldots,b_{\ell},0,1,\ldots,1)$, with
$b_{1},\ldots,b_{\ell}\in\\{0,1\\}$, so that B$(s+1)$ would be
$(b_{1},\ldots,b_{\ell},1,0,\ldots,0)$, the weight of which does not exceed
that of B$(s)$. So, B$(s)$ must be of the form $(b_{1},\ldots,b_{m-1},0)$, and
so, B$(s+1)=(b_{1},\ldots,b_{m-1},1)$. From wt$(\mathbf{B}(s))\leq r$ and
wt$(\mathbf{B}(s+1))\geq r+1$, we obtain that wt$(b_{1}\ldots b_{m-1})=r$.

This then implies that the number of runs, which is equal to the number of
right end-points of runs, exactly equals ${m-1\choose r}$. ∎

With the ingredients in place, we are now in a position to prove Theorem
III.3.

###### Proof of Theorem III.3.

Fix a sequence of codes
$\left\\{\hat{\mathcal{C}}_{m}(R)=\text{RM}(m,r_{m})\right\\}_{m\geq 1}$ of
rate $R\in(0,1)$, with $r_{m}\leq m-1$, for all $m$. We use the notation
$K_{m}:={m\choose\leq r_{m}}$ to denote the dimension of
${\hat{\mathcal{C}}_{m}(R)}$.

Now, for a given $m$, consider the information set $\mathcal{I}_{m,r_{m}}$
(see (15)). We know from Lemma V.3 that the number of runs,
$\left\lvert\Gamma_{m,r_{m}}\right\rvert$, of coordinates that lie in
$\mathcal{I}_{m,r_{m}}$, is exactly ${m-1\choose r_{m}}$. Now, note that the
$i^{\text{th}}$ run $(s_{i},\ldots,s_{i}+\ell_{i}-1)$, of length $\ell_{i}$,
with $s_{i}\in\Gamma_{m,r_{m}}$ and
$i\in\left[\left\lvert\Gamma_{m,r_{m}}\right\rvert\right]$, contributes
$\left\lfloor\frac{\ell_{i}}{d+1}\right\rfloor$ disjoint $(d+1)$-tuples of
consecutive coordinates in $\mathcal{I}_{m,r}$. It then holds that the overall
number of disjoint $(d+1)$-tuples of consecutive coordinates in
$\mathcal{I}_{m,r}$ is $t_{m}$, where

$\displaystyle t_{m}$
$\displaystyle=\sum_{i=1}^{\left\lvert\Gamma_{m,r_{m}}\right\rvert}\left\lfloor\frac{\ell_{i}}{d+1}\right\rfloor$
$\displaystyle\geq\sum_{i=1}^{\left\lvert\Gamma_{m,r_{m}}\right\rvert}\left(\frac{\ell_{i}}{d+1}-1\right)$
$\displaystyle=\frac{K_{m}}{d+1}-\left\lvert\Gamma_{m,r_{m}}\right\rvert=\frac{K_{m}}{d+1}-{m-1\choose
r_{m}},$

where the last equality follows from Lemma V.3.

Using Proposition V.1, it follows that the dimension of any linear
$(d,\infty)$-RLL subcode
$\overline{\mathcal{C}}^{(d,\infty)}\subseteq\hat{\mathcal{C}}_{m}(R)$ is at
most $K_{m}-dt_{m}$. It then holds that

$\displaystyle\overline{\mathsf{R}}_{\hat{\mathcal{C}}}^{(d,\infty)}(R)$
$\displaystyle=\limsup_{m\to\infty}\max_{\overline{\mathcal{C}}^{(d,\infty)}\subseteq\hat{\mathcal{C}}_{m}(R)}\frac{\log_{2}\left\lvert\overline{\mathcal{C}}^{(d,\infty)}\right\rvert}{2^{m}}$
$\displaystyle\leq\limsup_{m\to\infty}\frac{K_{m}-dt_{m}}{2^{m}}$
$\displaystyle\leq\limsup_{m\to\infty}\frac{K_{m}-\frac{dK_{m}}{d+1}+d\cdot{m-1\choose
r_{m}}}{2^{m}}$
$\displaystyle\leq\lim_{m\to\infty}\frac{\frac{K_{m}}{d+1}+d\cdot{m-1\choose\left\lfloor\frac{m-1}{2}\right\rfloor}}{2^{m}}$
$\displaystyle=\frac{R}{d+1},$

where the last equality holds from the fact that
${m-1\choose\left\lfloor\frac{m-1}{2}\right\rfloor}$ is
$O\left(\frac{2^{m}}{\sqrt{m-1}}\right)$, and
$\lim_{m\to\infty}\frac{K_{m}}{2^{m}}=R$. ∎

###  V-B General Subcodes

In this section, we provide upper bounds on the rates of $(1,\infty)$-RLL
subcodes of $\\{\mathcal{C}_{m}(R)=\text{RM}(m,r_{m})\\}_{m\geq 1}$, where

$r_{m}=\max\left\\{\left\lfloor\frac{m}{2}+\frac{\sqrt{m}}{2}Q^{-1}(1-R)\right\rfloor,0\right\\}.$

Recall that from Theorem II.1, it holds that
$\\{\mathcal{C}_{m}(R)=\text{RM}(m,r_{m})\\}_{m\geq 1}$ is a sequence of RM
codes of rate $R$. We fix the coordinate ordering to be the standard
lexicographic ordering.

Recall, from Lemma IV.1, that any $(1,\infty)$-RLL subcode of
$\mathcal{C}_{m}(R)$ must be such that both conditions (C1) and (C2) are
simultaneously satisfied. Therefore, to obtain an upper bound on the number of
codewords Eval$(f)\in{\mathcal{C}}_{m}(R)$ that respect the $(1,\infty)$-RLL
constraint, it is sufficient to obtain an upper bound on the number of
Eval$(f)\in{\mathcal{C}}_{m}(R)$ that satisfy (C1) alone. In other words, we
wish to obtain an upper bound on the number of pairs of polynomials $(g,h)$
(see the Plotkin decomposition in (2)), with Eval$(g)\in\mathcal{C}_{m}^{(g)}$
and Eval$(h)\in\mathcal{C}_{m}^{(h)}$, such that
supp$(\text{Eval}(g))\subseteq\text{supp}(\text{Eval}(h))$.

The following two lemmas from the literature will be useful in the proof of
Theorem III.4.

######  Lemma V.4 ([28], Lemma 36).

Let $\mathcal{V}\subseteq\mathbb{F}_{2}^{m}$ be such that $|\mathcal{V}|\geq
2^{m-u}$, for some $u\in\mathbb{N}$. Then, it holds that

$\text{rank}(G(m,r)[\mathcal{V}])>{m-u\choose\leq r},$

where $G(m,r)$ is a generator matrix of the RM$(m,r)$ code, and
$G(m,r)[\mathcal{V}]$ denotes the set of columns of $G(m,r)$, indexed by
$\mathcal{V}$.

The lemma below follows from Theorem 1 in [31], by noting that the Reed-Muller
code is transitive:

######  Lemma V.5.

Let $\mathcal{C}=\text{RM}(m,r)$ and let the weight distribution of
$\mathcal{C}$ be $\left(A_{m,r}(w):0\leq w\leq 2^{m}\right)$. Then, it holds
that

$A_{m,r}(w)\leq\text{exp}_{2}\left({m\choose\leq r}\cdot
h_{b}\left(\frac{w}{2^{m}}\right)\right),$

where $h_{b}(\cdot)$ is the binary entropy function.

We now provide the proof of Theorem III.4.

###### Proof of Theorem III.4.

Fix the sequence $\\{{\mathcal{C}}_{m}(R)=\text{RM}(m,r_{m})\\}_{m\geq 1}$ of
RM codes, with

$r_{m}=\max\left\\{\left\lfloor\frac{m}{2}+\frac{\sqrt{m}}{2}Q^{-1}(1-R)\right\rfloor,0\right\\},$

as in the statement of the theorem. Now, for any codeword
Eval$(g)\in\mathcal{C}_{m}^{(g)}$ of weight $w$, we shall first calculate the
number, $N_{w}(g)$, of codewords Eval$(h)\in\mathcal{C}_{m}^{(g)}$ such that
supp$(\text{Eval}(g))\subseteq\text{supp}(\text{Eval}(h))$. Note that
$N_{w}(g)$ serves as an upper bound on the number of codewords
Eval$(h)\in\mathcal{C}_{m}^{(h)}$ such that the same property holds.

To this end, suppose that for any weight $w$, the integer $u=u(w)$ is the
smallest integer such that wt$(\text{Eval}(g))=w\geq 2^{m-1-u}$. Note that for
any polynomial $g$ as above of weight $w$, the number of codewords in the code
produced by shortening $\mathcal{C}_{m}^{(g)}$ at the indices in
supp$(\text{Eval}(g))$, equals $N_{w}(g)$. Now, since
dim$\left(\mathcal{C}_{m}^{(g)}\right)={m-1\choose\leq r_{m}}$, and from the
fact that $w\geq 2^{m-1-u}$, we obtain by an application of Lemmas IV.4 and
V.4, that

$\displaystyle N_{w}(g)$ $\displaystyle\leq\text{exp}_{2}\left({m-1\choose\leq
r_{m}}-{m-1-u\choose\leq r_{m}}\right)$ (17) $\displaystyle=:M_{u(w)}.$

Let $\mathcal{C}_{m}^{(1,\infty)}$ denote the largest $(1,\infty)$-RLL subcode
of ${\mathcal{C}}_{m}(R)$, and let
$\mathsf{R}_{{\mathcal{C}},m}^{(1,\infty)}(R)$ denote its rate, i.e.,

$\mathsf{R}_{{\mathcal{C}},m}^{(1,\infty)}(R)=\frac{\log_{2}\left(\left\lvert\mathcal{C}_{m}^{(1,\infty)}\right\rvert\right)}{2^{m}}.$

Then, it holds that

$\displaystyle\left\lvert\mathcal{C}_{m}^{(1,\infty)}\right\rvert$
$\displaystyle\leq\sum_{g:\text{Eval}(g)\in\mathcal{C}_{m}^{(g)}}{N_{w}(g)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum\limits_{w=2^{m-1-r_{m}}}^{2^{m-1}}A_{m-1,r_{m}}(w){M_{u(w)}}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\left\\{\sum\limits_{w=2^{m-1-r_{m}}}^{2^{m-2}}A(w){M_{u(w)}}\right\\}+\frac{1}{2}\cdot\text{exp}_{2}\left(m-1\choose\leq
r_{m}\right)\cdot\text{exp}_{2}\left({m-1\choose\leq r_{m}}-{m-2\choose\leq
r_{m}}\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\left\\{\sum\limits_{w=2^{m-1-r_{m}}}^{2^{m-2}}A(w){M_{u(w)}}\right\\}+\frac{1}{2}\cdot\text{exp}_{2}\left({m-1\choose\leq
r_{m}}+{m-2\choose\leq r_{m}}\right)$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}\Bigg{\\{}\sum\limits_{i=1}^{{r_{m}-1}}A\left(\left[2^{m-2-i}:2^{m-1-i}\right]\right)\cdot\text{exp}_{2}\left({m-1\choose\leq
r_{m}}-{m-2-i\choose\leq
r_{m}}\right)\Bigg{\\}}+\frac{1}{2}\cdot\text{exp}_{2}\left({m-1\choose\leq
r_{m}}+{m-2\choose\leq r_{m}}\right),$ (18)

where, for ease of reading, we write $A(w):=A_{m-1,r_{m}}(w)$, in inequalities
(b)–(d). Further, $A([a:b])$ is shorthand for $\sum_{i=a}^{b}A(w)$. Here,

  1. (a)

follows from (17), and

  2. (b)

holds due to the following fact: since the all-ones codeword $\mathbf{1}$ is
present in $\mathcal{C}_{m}^{(g)}=\text{RM}(m-1,r_{m})$, it implies that
$A(w)=A(2^{m-1}-w)$, i.e., that the weight distribution of
$\mathcal{C}_{m}^{(g)}$ is symmetric about weight $w=2^{m-2}$. Therefore,

$A\left(\left[2^{m-2}+1:2^{m-1}\right]\right)\leq\frac{1}{2}\cdot\text{exp}_{2}{m-1\choose\leq
r_{m}}.$ (19)

Next,

  1. (c)

follows from the fact that for positive integers $n,k$ with $n>k$:

${n-1\choose k}+{n-1\choose k-1}={n\choose k}.$

Picking $n=m-1$, we obtain that for $k\leq m-2$,

${m-1\choose k}-{m-2\choose k}={m-2\choose k-1},$

and hence that

${m-1\choose\leq r_{m}}-{m-2\choose\leq r_{m}}<{m-2\choose\leq r_{m}},\
\text{and}$

  2. (d)

holds again by (17).

It is clear that a simplification of (18) depends crucially on good upper
bounds on the weight distribution function. Recall the notation
$R_{m}^{(g)}:=\frac{{m-1\choose\leq r_{m}}}{2^{m-1}}$. We now use the result
in Lemma V.5, to get that for $1\leq i\leq r_{m}-1$,

$\displaystyle A_{m-1,r_{m}}\left(\left[2^{m-2-i}:2^{m-1-i}\right]\right)$
$\displaystyle\leq\sum_{w=2^{m-2-i}}^{2^{m-1-i}}\text{exp}_{2}\left(2^{m-1}\cdot
R_{m}^{(g)}\cdot h_{b}\left(\frac{w}{2^{m-1}}\right)\right)$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{\leq}}\sum_{w=2^{m-2-i}}^{2^{m-1-i}}\text{exp}_{2}\left(2^{m-1}\cdot
R_{m}^{(g)}\cdot h_{b}(2^{-i})\right)$
$\displaystyle=\text{exp}_{2}\left(2^{m-1}\cdot R_{m}^{(g)}\cdot
h_{b}(2^{-i})+o(2^{m})\right):=B_{i}(m),$ (20)

where inequality (e) above follows from the fact that the binary entropy
function, $h_{b}(p)$, is increasing for arguments
$p\in\left[0,\frac{1}{2}\right)$. Therefore, putting (20) back in (18), we get
that

$\displaystyle 2^{m}\mathsf{R}^{(1,\infty)}_{{\mathcal{C}},m}(R)$
$\displaystyle=\log_{2}\left\lvert\mathcal{C}_{m}^{(1,\infty)}\right\rvert$
$\displaystyle\leq{m-1\choose\leq
r_{m}}+\log_{2}\Bigg{\\{}\frac{1}{2}\cdot\text{exp}_{2}{m-2\choose\leq
r_{m}}+\sum_{i=1}^{r_{m}-1}B_{i}(m)\cdot\text{exp}_{2}\left(-{m-2-i\choose\leq
r_{m}}\right)\Bigg{\\}}$ $\displaystyle={m-1\choose\leq
r_{m}}+\log_{2}\left(\alpha(m)+\beta(m)\right),$ (21)

where we define

$\displaystyle\alpha(m)$
$\displaystyle:=\frac{1}{2}\cdot\text{exp}_{2}{m-2\choose\leq r_{m}},\
\text{and}$ $\displaystyle\beta(m)$
$\displaystyle:=\sum_{i=1}^{r_{m}-1}B_{i}(m)\cdot\text{exp}_{2}\left(-{m-2-i\choose\leq
r_{m}}\right).$ (22)

In Appendix A, we show that for all $\delta\in(0,1)$ sufficiently small and
for $m$ sufficiently large, it holds that

$\displaystyle\beta(m)\ $ $\displaystyle\leq\
\text{exp}_{2}\left(2^{m-1}R\cdot\left(\frac{3}{4}+\delta\right)+o(2^{m})\right)$
$\displaystyle=:\ \theta(m).$ (23)

Now, using Lemma IV.1, we have

$\lim_{m\to\infty}\frac{1}{2^{m}}{m-2\choose\leq r_{m}}=\frac{R}{4}.$

Hence, for small $\delta\in(0,1)$, and for $m$ large enough, it holds that

${m-2\choose\leq r_{m}}\leq(1+\delta)\cdot 2^{{m}-2}\cdot R.$

Therefore, we get that

$\displaystyle\alpha(m)\ \leq\ \text{exp}_{2}\left((1+\delta)\cdot
2^{{m}-2}\cdot R\right)\ =:\ \eta(m).$ (24)

Now, substituting (23) and (24) in (21), we get that

$\displaystyle
2^{m}\mathsf{R}^{(1,\infty)}_{{\mathcal{C}},m}(R)\leq{m-1\choose\leq
r_{m}}+\log_{2}\left(\eta(m)+\theta(m)\right).$ (25)

Putting everything together, we see that

$\displaystyle\mathsf{R}^{(1,\infty)}_{{\mathcal{C}}}(R)$
$\displaystyle=\limsup_{m\to\infty}\mathsf{R}^{(1,\infty)}_{{\mathcal{C}},m}(R)$
$\displaystyle\leq\lim_{m\to\infty}\frac{1}{2^{m}}\left[{m-1\choose\leq
r_{m}}+\log_{2}\left(\eta(m)+\theta(m)\right)\right]$
$\displaystyle\stackrel{{\scriptstyle(p)}}{{\leq}}\lim_{m\to\infty}\frac{1}{2^{m}}\left[{m-1\choose\leq
r_{m}}+\log_{2}\left(2\cdot\theta(m)\right)\right]$
$\displaystyle\stackrel{{\scriptstyle(q)}}{{=}}\frac{R}{2}+\lim_{m\to\infty}\frac{1}{2^{m}}\cdot\log_{2}\theta(m)$
$\displaystyle=\frac{R}{2}+\frac{3R}{8}+\frac{\delta R}{2}$
$\displaystyle=\frac{7R}{8}+\frac{\delta R}{2}.$ (26)

Note that inequality (p) follows from the fact for any $R\in(0,1)$,
$\eta(m)\leq\theta(m)$ holds for all sufficiently small $\delta>0$. Further,
equation (q) is valid because $\lim_{m\to\infty}\frac{1}{2^{m}}{m-1\choose\leq
r_{m}}=\frac{R}{2}$, by Lemma IV.1. Since (26) holds for all $\delta>0$
sufficiently small, we can let $\delta\to 0$, thereby obtaining that

$\displaystyle\mathsf{R}^{(1,\infty)}_{{\mathcal{C}}}(R)\leq\frac{7R}{8}.$

Moreover, since for any $m\geq 1$, we have that
$\mathcal{C}_{m}^{(1,\infty)}\subseteq S_{(1,\infty)}^{(2^{m})}$, with
$\lim_{m\to\infty}\frac{\log_{2}\left\lvert
S_{(1,\infty)}^{(2^{m})}\right\rvert}{2^{m}}=C_{0}^{(1)}$, it holds that
$\mathsf{R}^{(1,\infty)}_{{\mathcal{C}}}(R)\leq C_{0}^{(1)}$. ∎

###  V-C Alternative Coordinate Orderings

Throughout the previous subsections, we have assumed that the coordinates of
the RM codes are ordered according to the standard lexicographic ordering. In
this subsection, we shall address the question of whether alternative
coordinate orderings allow for larger rates of _linear_ $(d,\infty)$-RLL
constrained subcodes of RM codes of rate $R$, as compared to the upper bound
of $\frac{R}{d+1}$ derived for RM codes under the lexicographic coordinate
ordering, in Theorem III.3.

First, we consider a Gray ordering of coordinates of the code RM$(m,r)$. In
such an ordering, consecutive coordinates $\mathbf{b}=(b_{1},\ldots,b_{m})$
and $\mathbf{b}^{\prime}=(b_{1}^{\prime},\ldots,b_{m}^{\prime})$ are such that
for some bit index $i\in[m]$, $b_{i}\neq b_{i}^{\prime}$, but
$b_{j}=b_{j}^{\prime}$, for all $j\neq i$. In words, consecutive coordinates
in a Gray ordering, when represented as $m$-tuples, differ in exactly one bit
index. Note that there are multiple orderings that satisfy this property.
Indeed, Gray orderings correspond to Hamiltonian paths (see, for example,
[43], Chap. 10) on the $m$-dimensional unit hypercube.

In what follows, we work with a fixed sequence of Gray orderings defined as
follows: let $(\pi_{\text{G},m})_{m\geq 1}$ be a sequence of permutations,
with $\pi_{\text{G},m}:[0:2^{m}-1]\rightarrow[0:2^{m}-1]$, for any $m\geq 1$,
having the property that B$(\pi_{\text{G},m}(j))$ differs from
B$(\pi_{\text{G},m}(j-1))$ in exactly one bit index, for any
$j\in[1:2^{m}-1]$.

Now, as before, fix a sequence of codes
$\left\\{\hat{\mathcal{C}}_{m}(R)=\text{RM}(m,r_{m})\right\\}_{m\geq 1}$ of
rate $R\in(0,1)$. Note that for large enough $m$, we have that $r_{m}\leq
m-1$. We again use the notation $K_{m}:={m\choose\leq r_{m}}$ to denote the
dimension of ${\hat{\mathcal{C}}_{m}(R)}$. We then define the sequence of
Gray-ordered RM codes $\left\\{\mathcal{C}_{m}^{\text{G}}(R)\right\\}_{m\geq
1}$, via

$\displaystyle\mathcal{C}_{m}^{\text{G}}(R):=\big{\\{}(c_{\pi_{\text{G},m}(0)},c_{\pi_{\text{G},m}(1)},\ldots,c_{\pi_{\text{G},m}(2^{m}-1)}):(c_{0},c_{1},\ldots,c_{2^{m}-1})\in\hat{\mathcal{C}}_{m}(R)\big{\\}}.$

Clearly, the sequence of codes
$\left\\{\mathcal{C}_{m}^{\text{G}}(R)\right\\}_{m\geq 1}$ is also of rate
$R\in(0,1)$. In order to obtain an upper bound on the rate of the largest
linear $(d,\infty)$-RLL subcode of the code $\mathcal{C}_{m}^{\text{G}}(R)$,
as in Theorem III.3, we shall work with the information set
$\mathcal{I}_{m,r_{m}}$ (see (15) for the definition of the set
$\mathcal{I}_{m,r}$ of coordinates of RM$(m,r)$).

Analogous to (16), we define the set

$\displaystyle\Gamma_{m}^{\text{G}}:=\\{s\in[0:2^{m}-1]:\
\textbf{B}(\pi_{\text{G},m}(s))\in\mathcal{I}_{m,r_{m}},\ \text{but}\
\textbf{B}(\pi_{\text{G},m}(s+1))\notin\mathcal{I}_{m,r_{m}}\\}.$ (27)

We use the convention that when $s=2^{m}-1$,
$\textbf{B}(\pi_{\text{G},m}(s+1))$ is defined to be a dummy symbol ‘$\times$’
that does not belong to $\mathcal{I}_{m,r_{m}}$. The number of such runs is
$\left\lvert\Gamma_{m}^{\text{G}}\right\rvert$. Note now that unlike in (16),
it is possible that $2^{m}-1\in\Gamma_{m}^{\text{G}}$, since, depending on the
specific Gray coordinate ordering chosen, it is possible that
$\textbf{B}(\pi_{\text{G},m}(2^{m}-1))\in\mathcal{I}_{m,r_{m}}$.

We now state and prove a lemma analogous to Lemma V.3:

######  Lemma V.6.

Under a fixed Gray ordering defined by $\pi_{m}^{\text{G}}$, it holds that
$\left\lvert\Gamma_{m,r_{m}}^{\text{G}}\right\rvert\leq{m\choose r_{m}+1}+1$,
for $0\leq r_{m}\leq m-1$.

###### Proof.

For any $s\in[0:2^{m}-2]$ that belongs to $\Gamma_{m}^{\text{G}}$, we have
wt$(\mathbf{B}(\pi_{\text{G},m}(s)))\leq r_{m}$, but
wt$(\mathbf{B}(\pi_{\text{G},m}(s+1)))\geq r_{m}+1$. In fact, since
consecutive coordinates differ in exactly one bit index in the Gray ordering,
it must be the case that wt$(\mathbf{B}(\pi_{\text{G},m}(s+1)))=r_{m}+1$.
Thus, the number of integers $s\in[0:2^{m}-2]$ belonging to
$\Gamma_{m}^{\text{G}}$ is bounded above by ${m\choose r_{m}+1}$, which is the
number of coordinates whose binary representation has weight exactly
$r_{m}+1$. In order to account for the possibility that
$2^{m}-1\in\Gamma_{m}^{\text{G}}$, we state the overall upper bound on the
number of runs as ${m\choose r_{m}+1}+1$. ∎

With Lemma V.6 established, we now embark on a proof of Theorem III.5.

###### Proof of Theorem III.5.

Similar to the proof of Theorem III.3, the calculation of the overall number,
$t_{m}^{\text{G}}$, of disjoint $(d+1)$-tuples of consecutive coordinates in
$\mathcal{I}_{m,r_{m}}$, for large enough $m$, results in

$\displaystyle t_{m}^{\text{G}}\geq\frac{K_{m}}{d+1}-{m\choose r_{m}+1}-1.$

Again, using Proposition V.1, it follows that the dimension of any linear
$(d,\infty)$-RLL subcode
$\overline{\mathcal{C}}_{\text{G}}^{(d,\infty)}\subseteq{\mathcal{C}_{m}^{\text{G}}(R)}$
is at most $K_{m}-dt_{m}^{\text{G}}$. Now, recalling the definition of
$\overline{\mathsf{R}}_{{\mathcal{C}}^{\text{G}}}^{(d,\infty)}(R)$, from
equation (4), we see that

$\displaystyle\overline{\mathsf{R}}_{{\mathcal{C}}^{\text{G}}}^{(d,\infty)}(R)$
$\displaystyle\leq\limsup_{m\to\infty}\frac{K_{m}-dt_{m}^{\text{G}}}{2^{m}}$
$\displaystyle\leq\limsup_{m\to\infty}\frac{K_{m}-\frac{dK_{m}}{d+1}+d\cdot{m\choose
r_{m}+1}+d}{2^{m}}$
$\displaystyle\leq\lim_{m\to\infty}\frac{\frac{K_{m}}{d+1}+d\cdot{m\choose\left\lfloor\frac{m}{2}\right\rfloor}+d}{2^{m}}$
$\displaystyle=\frac{R}{d+1},$

where the last equality holds for reasons similar to those in the proof of
Theorem III.3. ∎

Now, we shift our attention to $\pi$-ordered RM codes
$\left\\{\mathcal{C}_{m}^{\pi}(R)\right\\}_{m\geq 1}$, defined by the sequence
of arbitrary permutations $(\pi_{m})_{m\geq 1}$, with
$\pi_{m}:[0:2^{m}-1]\to[0:2^{m}-1]$ (see the discussion preceding Theorem
III.6 in Section III). Also recall the definition of
$\overline{\mathcal{C}}_{m}^{\pi,(d,\infty)}$ being the largest _linear_
$(d,\infty)$-RLL subcode of $\mathcal{C}_{m}^{\pi}(R)$.

We shall now prove Theorem III.6.

###### Proof of Theorem III.6.

We wish to prove that for “most” orderings, and for large $m$, it holds that
the rate of $\overline{\mathcal{C}}_{m}^{\pi,(d,\infty)}$ is bounded above by
$\frac{R}{d+1}+\delta_{m}$, where $\delta_{m}\xrightarrow{m\to\infty}0$.

To this end, we first make the observation that the sequence of RM codes
$\left\\{\hat{\mathcal{C}}_{m}(R)=\text{RM}(m,r_{m})\right\\}_{m\geq 1}$
achieves a rate $R$ over the BEC, under block-MAP decoding too (see [6] and
[44]). Hence, for large enough $m$, the (linear) RM code
$\hat{\mathcal{C}}_{m}(R)$ can correct erasures that are caused by a
BEC$(1-R-\gamma_{m})$, with $\gamma_{m}>0$, and
$\gamma_{m}\xrightarrow{m\to\infty}0$. This then means that for large $m$,
$\hat{\mathcal{C}}_{m}(R)$ can correct
$2^{m}(1-R-\gamma_{m})-c\cdot\sqrt{2^{m}(1-R-\gamma_{m})}$ erasures, with high
probability (see Lemma 15 of [28]), for $c>0$ suitably small. Finally, from
Corollary 18 of [28], it then holds that for large enough $m$, any collection
of $2^{m}R(1+\beta_{m})$ columns of $G_{\text{Lex}}(m,r_{m})$, chosen
uniformly at random, must have full row rank, $K_{m}$, with probabilty
$1-\delta_{m}$, with $\beta_{m},\delta_{m}>0$ and
$\beta_{m},\delta_{m}\xrightarrow{m\to\infty}0$.

In other words, the discussion above implies that for large enough $m$, a
collection of $K_{m}(1+\alpha_{m})$ coordinates, chosen uniformly at random,
contains an information set, with probabilty $1-\delta_{m}$, where, again,
$\alpha_{m}>0$, with $\alpha_{m}\xrightarrow{m\to\infty}0$. An equivalent view
of the above statement is that for large enough $m$, for a $1-\delta_{m}$
fraction of the possible permutations $\pi_{m}:[0:2^{m}-1]\to[0:2^{m}-1]$, the
first block of $K_{m}(1+\alpha_{m})$ coordinates of the code
$\mathcal{C}_{m}^{\pi}(R)$, contains an information set,
${\mathcal{J}}_{m,r_{m}}$. Now, within these “good” permutations, since
$|{\mathcal{J}}_{m,r_{m}}|=K_{m}$, it follows that the number of runs,
$\left\lvert\Gamma_{m}^{\pi}\right\rvert$, of consecutive coordinates that
belong to ${\mathcal{J}}_{m,r_{m}}$, obeys
$\left\lvert\Gamma_{m}^{\pi}\right\rvert\leq K_{m}\alpha_{m}+1$, with
$\Gamma_{m}^{\pi}$ defined similar to equation (27). This is because the
number of runs, $\left\lvert\Gamma_{m}^{\pi}\right\rvert$, equals the number
of coordinates $s$, such that $s\in{\mathcal{J}}_{m,r_{m}}$, but
$s+1\notin{\mathcal{J}}_{m,r_{m}}$. Hence, accounting for the possibility that
the last coordinate in the $K_{m}(1+\alpha_{m})$-block belongs to
${\mathcal{J}}_{m,r_{m}}$, we get that the number of such coordinates $s$ is
at most $K_{m}(1+\alpha_{m})+1-K_{m}$, which equals $K_{m}\alpha_{m}+1$.

Hence, the overall number, $t_{m}^{\pi}$, of disjoint $(d+1)$-tuples of
consecutive coordinates in $\mathcal{J}_{m,r}$, satisfies (see the proof of
Theorem III.3)

$t_{m}^{\pi}\geq\frac{K_{m}}{d+1}-K_{m}\alpha_{m}-1,$

for a $1-\delta_{m}$ fraction of permutations $\pi_{m}$. Again, applying
Proposition V.1, it holds that for a $1-\delta_{m}$ fraction of permutations,
with $\delta_{m}\xrightarrow{m\to\infty}0$, the rate of the largest
$(d,\infty)$-RLL subcode obeys

$\displaystyle\frac{\log_{2}\left\lvert\overline{\mathcal{C}}_{m}^{\pi,(d,\infty)}\right\rvert}{2^{m}}$
$\displaystyle\leq\frac{K_{m}-dt_{m}^{\pi}}{2^{m}}$
$\displaystyle\leq\frac{K_{m}-\frac{dK_{m}}{d+1}+dK_{m}\alpha_{m}+d}{2^{m}}$
$\displaystyle=\frac{R}{d+1}+\epsilon_{m},$

where $\epsilon_{m}\xrightarrow{m\to\infty}0$, thereby showing what we set out
to prove. ∎

##  VI A Two-Stage Constrained Coding Scheme

The results summarized in the previous sections provide lower and upper bounds
on rates of $(d,\infty)$-RLL constrained subcodes of RM codes of rate $R$. In
particular, Theorem III.1 identifies linear subcodes of RM codes of rate
$2^{-\left\lceil\log_{2}(d+1)\right\rceil}\cdot R$, and for the special case
when $d=1$, Theorem III.2 improves upon this lower bound, for a range of $R$
values, by proving the existence of (non-linear) subcodes of rate at least
$\max\left(0,R-\frac{3}{8}\right)$. Furthermore, using the bit-MAP decoders
corresponding to the parent RM codes, we observe that these rates are
achievable over $(d,\infty)$-RLL input-constrained BMS channels, so long as
$R<C$, where $C$ is the capacity of the unconstrained BMS channel. In this
section, we provide another explicit construction of $(d,\infty)$-RLL
constrained codes via a concatenated (or two-stage) coding scheme, the outer
code of which is a systematic RM code of rate $R$, and the inner code of which
employs the $(d,\infty)$-RLL constrained subcodes identified in Theorem III.1.
The strategy behind our coding scheme is very similar to the “reversed
concatenation” scheme that is used to limit error propagation while decoding
constrained codes over noisy channels (see [18, 19, 20, 21] and Section 8.5 in
[1]). However, to keep the exposition self-contained, we describe the scheme
from first principles, here. We then derive a rate lower bound for this scheme
(see Theorem III.7), and prove that this lower bound is achievable (with bit-
error probabilities going to zero as the blocklength goes to infinity) over
$(d,\infty)$-RLL input-constrained BMS channels, if $R<C$. Hence, the lower
bound given in Theorem III.7 is achievable, when $R\in(0,1)$ is replaced by
$C$.

We now describe our two-stage coding scheme. Fix a rate $R\in(0,1)$ and any
sequence $\left\\{\hat{\mathcal{C}}_{m}(R)=\text{RM}(m,r_{m})\right\\}_{m\geq
1}$ of RM codes of rate $R$. We interchangeably index the coordinates of any
codeword in $\hat{\mathcal{C}}_{m}(R)$ by $m$-tuples in the lexicographic
order, and by integers in $[0:2^{m}-1]$. Recall, from Lemma V.2 and (15), that
the set
$\mathcal{I}_{m,r_{m}}:=\\{\mathbf{b}=(b_{1},\ldots,b_{m})\in\mathbb{F}_{2}^{m}:\text{wt}(\mathbf{b})\leq
r_{m}\\}$ is an information set of $\hat{\mathcal{C}}_{m}(R)$. For the
remainder of this section, we let $m$ be a large positive integer.

We set $K_{m}=$ dim$\left(\hat{\mathcal{C}}_{m}(R)\right)={m\choose\leq
r_{m}}$ and $N_{m}:=2^{m}$ and note that
$N_{m}-K_{m}=(1+\beta_{m})N_{m}(1-R)$, where $\beta_{m}$ is a correction term
that vanishes as $m\to\infty$. For the outer code, or the first stage, of our
coding scheme, we shall work with an RM code in systematic form, in which the
first $K_{m}$ positions form the information set $\mathcal{I}_{m,r_{m}}$.
Consider any permutation $\pi_{m}:[0:N_{m}-1]\to[0:N_{m}-1]$ with the property
that $\pi_{m}([0:K_{m}-1])=\mathcal{I}_{m,r_{m}}$, where, for a permutation
$\sigma$, and a set $\mathcal{A}\subseteq[0:N_{m}-1]$, we define the notation
$\sigma(\mathcal{A}):=\\{\sigma(i):i\in\mathcal{A}\\}$. We then define the
equivalent systematic RM code ${\mathcal{C}}^{\pi}_{m}(R)$ as

$\displaystyle{\mathcal{C}}^{\pi}_{m}(R)=\big{\\{}(c_{\pi_{m}(0)},c_{\pi_{m}(1)},\ldots,c_{\pi_{m}(N_{m}-1)}):(c_{0},c_{1},\ldots,c_{N_{m}-1})\in\hat{\mathcal{C}}_{m}(R)\big{\\}}.$

We let $G^{\pi}_{m}$ be a _systematic_ generator matrix for
${\mathcal{C}}^{\pi}_{m}(R)$. Our $(d,\infty)$-RLL constrained coding scheme
comprises two stages: an outer encoding stage (E1) and an inner encoding stage
(E2) as given below.

  1. (E1)

Pick a $(d,\infty)$-RLL constrained $K_{m}$-tuple, $w_{0}^{K_{m}-1}$. Encode
$w_{0}^{K_{m}-1}$ into a codeword $\mathbf{c}\in\mathcal{C}_{m}^{\pi}(R)$,
using the systematic generator matrix $G_{m}^{\pi}$, with
$\mathbf{c}=w^{K_{m}-1}_{0}G_{m}^{\pi}$. Note that
$c_{0}^{K_{m}-1}=w_{0}^{K_{m}-1}$ is $(d,\infty)$-RLL constrained.

  2. (E2)

Encode the last $N_{m}-K_{m}$ bits, $c_{K_{m}}^{N_{m}-1}$, of $\mathbf{c}$,
using $(d,\infty)$-RLL constrained codewords of RM codes of rate $R$, as we
describe next.

Choosing an RLL constrained word in Step (E1) above can be accomplished using
well-known constrained encoders (see, for example, [45] and Chapters 4 and 5
of [1]), of rates arbitrarily close to the noiseless capacity, $C_{0}^{(d)}$,
of the $(d,\infty)$-RLL constraint.

We now elaborate on Step (E2). By Theorem III.1, using RM codes
$\\{\mathcal{C}_{n}(R)=$ RM$(n,r_{n})\\}_{n\geq 1}$ of rate $R$ (where $r_{n}$
is as in (1)), we can explicitly identify linear $(d,\infty)$-RLL subcodes
$\left\\{{\mathcal{C}}_{n}^{(d,\infty)}(R)\right\\}_{n\geq 1}$ of rate
$2^{-\left\lceil\log_{2}(d+1)\right\rceil}\cdot R$. We shall use these
subcodes to encode the last $N_{m}-K_{m}$ bits of $\mathbf{c}$. We take $n$ to
be large enough that the rate of the subcode
${\mathcal{C}}_{n}^{(d,\infty)}(R)$ is $R_{n}^{(d,\infty)}\geq
2^{-\left\lceil\log_{2}(d+1)\right\rceil}\cdot R(1-\epsilon)$, for some
suitably small $\epsilon>0$.

Now, suppose that we were to use a $(d,\infty)$-RLL constrained code, whose
rate is at least $2^{-\left\lceil\log_{2}(d+1)\right\rceil}\cdot
R(1-\epsilon)$, to encode the last bits $c_{K_{m}}^{N_{m}-1}$. The blocklength
required for encoding will then be at most
$\frac{N_{m}-K_{m}}{2^{-\left\lceil\log_{2}(d+1)\right\rceil}\cdot
R(1-\epsilon)}=\frac{(1-R)(1+\beta_{m})}{R(1-\epsilon)}\cdot
2^{m+\left\lceil\log_{2}(d+1)\right\rceil}$, since $N_{m}=2^{m}$. Suppose
further that for some integer $m_{0}$ and for all $m\geq m_{0}$, it holds that

$\frac{(1-R)(1+\beta_{m})}{R(1-\epsilon)}\subseteq\left[2^{-\tau^{\prime}-1},2^{-\tau^{\prime}}\right],$

for some $\tau^{\prime}\in\mathbb{R}$. Now, if the constrained code that we
were using was $\mathcal{C}_{n}^{(d,\infty)}(R)$, for some large $n$, the
blocklength of the constrained codeword would have to be a power of $2$.
Hence, we would have to pad the information bits $c_{K_{m}}^{N_{m}-1}$, of the
inner code, with additional $0$s, so that the blocklength of the constrained
codeword obtained after encoding will be
$2^{m-\tau^{\prime}+\left\lceil\log_{2}(d+1)\right\rceil}$. However, depending
on the value of $R$, for large enough $m$, the value of $\tau^{\prime}$ could
be quite small; in other words, the blocklength of the constrained codeword
could be quite large, leading to our coding scheme being of small rate. To
alleviate this problem, we first divide the $N_{m}-K_{m}$ bits to be encoded
into smaller parts, each of which will be separately encoded into a
$(d,\infty)$-RLL constrained codeword of an RM code.

To execute this strategy, we choose large positive integers $m_{0}$ and
$\tau$, and a positive integer $L$, such that

$\displaystyle\frac{(1-R)(1+\beta_{m})}{R(1-\epsilon)}\subseteq\left[\frac{L-1}{2^{\tau}},\frac{L}{2^{\tau}}\right],\
\text{for all $m\geq m_{0}$}.$ (28)

Note that $L$ and $\tau$, though large, are constants, and that if (28) holds
for some $\epsilon>0$, then, it continues to hold for all
$0\leq\epsilon^{\prime}<\epsilon$. We then chop up the $N_{m}-K_{m}$ bits,
$c_{K_{m}}^{N_{m}-1}$, into $L$ equal parts, with each part having
$\frac{N_{m}-K_{m}}{L}$ bits111For ease of description, we assume that $m$ is
such that $L$ divides $N_{m}-K_{m}$. However, the general case can be handled
by appending at most $L-1$ $0$s at the end of the $N_{m}-K_{m}$ bits, so that
the overall length is divisible by $L$, thereby giving rise to the same lower
bound in Lemma LABEL:lem:ratecoset.. By the same reasoning as before, we then
have that the number of channel uses, $N_{\text{exact}}$, needed to transmit
each part using a $(d,\infty)$-RLL constrained code of rate at least
$2^{-\left\lceil\log_{2}(d+1)\right\rceil}\cdot R(1-\epsilon)$, for $m$ much
larger than $m_{0}$, is now at most
$\frac{(1-R)(1+\beta_{m})}{R(1-\epsilon)}\cdot\frac{1}{L}\cdot
2^{m+\left\lceil\log_{2}(d+1)\right\rceil}$. Now, if the constrained code that
we were using was $\mathcal{C}_{n}^{(d,\infty)}(R)$, for some large $n$, we
would have from (28) that the blocklength of the constrained code (which has
to be a power of $2$) is

$\displaystyle
N_{\text{part}}:=2^{m-\tau+\left\lceil\log_{2}(d+1)\right\rceil},$ (29)

since $N_{m}=2^{m}$, and $m\geq m_{0}$. We hence set
$n^{\star}:=m-\tau+\left\lceil\log_{2}(d+1)\right\rceil$, with
$N_{\text{part}}=2^{n^{\star}}$. Thus, Step (E2) of the encoding strategy can
be replaced by the following two steps:

  * (E2a)

Divide $c_{K_{m}}^{N_{m}-1}$ into $L$ equal parts,
${\mathbf{c}}_{1},\ldots,{\mathbf{c}}_{L}$.

  * (E2b)

Encode each part $\mathbf{c}_{i}$, for $i\in[L]$, into a codeword of the code
${\mathcal{C}}^{(d,\infty)}_{n^{\star}}(R)$ (see the proof of Theorem III.1),
of blocklength $2^{n^{\star}}=N_{\text{part}}$.

Note that the number of channel uses needed for all the $L$ parts is
$N_{\text{part}}\cdot L$, and the total number of channel uses is
$N_{\text{tot}}:=K_{m}+N_{\text{part}}\cdot L$. The construction of our two-
stage (or concatenated) code $\mathcal{C}^{\text{conc}}_{m}$ is given in
Algorithm 1, for large $m$, with the assumption that $L$ divides
$N_{m}-K_{m}$. We let a generator matrix of the linear code
${\mathcal{C}}^{(d,\infty)}_{n}(R)$ be denoted by $G_{n}^{(d)}$.

Algorithm 1 Construction of $(d,\infty)$-RLL constrained code
$\mathcal{C}^{\text{conc}}_{m}$

1:procedure Coding-Scheme($G^{\pi}_{m}$, $G_{n^{\star}}^{(d)}$)

2: Pick a $(d,\infty)$-RLL constrained $K_{m}$-tuple $w_{0}^{K_{m}-1}$.

3: Obtain $\mathbf{c}\in\mathcal{C}_{m}^{\pi}(R)$ as
$\mathbf{c}=w_{0}^{K_{m}-1}G_{m}^{\pi}$, with
$c_{0}^{K_{m}-1}=w_{0}^{K_{m}-1}$.

4: Set $\mathbf{x}_{1}:=w_{0}^{K_{m}-1}$.

5: Divide $c_{K_{m}}^{N_{m}-1}$ into $L$ equal parts,
${\mathbf{c}}_{1},\ldots,{\mathbf{c}}_{L}$.

6: for $i=1:L$ do

7: Set $\mathbf{x}_{2,i}={\mathbf{c}}_{i}G_{n^{\star}}^{(d)}$.

8: Set $\mathbf{x}_{2}=\mathbf{x}_{2,1}\ldots\mathbf{x}_{2,L}$.

9: Transmit $\mathbf{x}=\mathbf{x}_{1}\mathbf{x}_{2}$.

We note from the construction of ${\mathcal{C}}^{(d,\infty)}_{n}(R)$ in the
proof of Theorem III.1 in Section IV that the first $d$ symbols in
$\mathbf{x}_{2,i}$ are $0$s, for all $i\in[L]$. Hence, the $(d,\infty)$-RLL
input constraint is also satisfied at the boundaries of the concatenations in
Steps 8 and 9 of Algorithm 1.

Since we intend transmitting the $(d,\infty)$-RLL constrained code
$\mathcal{C}^{\text{conc}}_{m}$ over a noisy BMS channel, we now specify the
decoding strategy. Let $y_{0}^{N_{\text{tot}}-1}$ be the vector of symbols
received by the decoder. Decoding is, as encoding was, a two-stage procedure.
In the first stage, the bit-MAP decoder of the code
$\mathcal{C}_{n^{\star}}(R)\supseteq\mathcal{C}_{n^{\star}}^{(d,\infty)}(R)$,
is used for each of the $L$ parts $\mathbf{c}_{1},\ldots,\mathbf{c}_{L}$, to
obtain the estimate
$\hat{c}_{K_{m}}^{N_{m}-1}:=(\hat{c}_{K_{m}},\ldots,\hat{c}_{N_{m}-1})$ of the
last $N_{m}-K_{m}$ bits $c_{K_{m}}^{N_{m}-1}$. In the second stage, the bit-
MAP decoder of the systematic RM code ${\mathcal{C}}^{\pi}_{m}(R)$ takes as
input the vector $y_{0}^{K_{m}-1}\hat{c}_{K_{m}}^{N_{m}-1}$, and produces as
(the final) estimate,
$\hat{c}_{0}^{K_{m}-1}:=(\hat{c}_{0}\ldots,\hat{c}_{K_{m}-1})$, of the
information bits $c_{0}^{K_{m}-1}=w_{0}^{K_{m}-1}$. The decoding strategy is
summarized below.

  * (D1)

Decode each of the $L$ parts $\mathbf{c}_{1},\ldots,\mathbf{c}_{L}$, using the
bit-MAP decoder of $\mathcal{C}_{n^{\star}}(R)$, to obtain the estimate
$\hat{c}_{K_{m}}^{N_{m}-1}$.

  * (D2)

Using the vector $y_{0}^{K_{m}-1}\hat{c}_{K_{m}}^{N_{m}-1}$ as input to the
bit-MAP decoder of $\mathcal{C}_{m}^{\pi}(R)$, obtain the estimate
$\hat{c}_{0}^{K_{m}-1}$ of the information bits $w_{0}^{K_{m}-1}$.

A rate lower bound of the coding scheme in Algorithm 1 and a lower bound on
the probability of correct decoding is provided in the proof of Theorem III.7
below.

###### Proof of Theorem III.7.

Consider the code $\mathcal{C}_{m}^{\text{conc}}$, given in Algorithm 1, for
large values of $m$, and the decoding procedure given in (D1)–(D2). By picking
$m$ large enough (and hence $K_{m}$ large enough), we note that for Step 2 of
Algorithm 1, there exist constrained coding schemes (see [45] and Chapters 4
and 5 of [1]) of rate $C_{0}^{(d)}-\alpha_{m}$, for $\alpha_{m}>0$, with
$\alpha_{m}\xrightarrow{m\to\infty}0$. Hence, we see that for large $m$, the
number of possible $K_{m}$-tuples, $w_{1}^{K_{m}}$, that can be picked, equals
$2^{K_{m}(C_{0}^{(d)}-\alpha_{m})}$. Since the codeword $\mathbf{c}$ and the
words $\mathbf{x}_{1}$ and $\mathbf{x}_{2}$ are determined by $\mathbf{w}$, it
holds that for large $m$, the rate of the code $\mathcal{C}_{m}^{\text{cos}}$
obeys

$\displaystyle\text{rate}(\mathcal{C}_{m}^{\text{conc}})\geq\frac{\log_{2}\left(2^{K_{m}(C_{0}^{(d)}-\alpha_{m})}\right)}{K_{m}+N_{\text{part}}\cdot
L},$

where the denominator, $K_{m}+N_{\text{part}}\cdot L$, is the total number of
channel uses. The following statements then hold true:

$\displaystyle\text{rate}(\mathcal{C}_{m}^{\text{conc}})$
$\displaystyle\geq\frac{\log_{2}\left(2^{K_{m}(C_{0}^{(d)}-\alpha_{m})}\right)}{K_{m}+N_{\text{part}}\cdot
L}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\frac{\frac{\left(C_{0}^{(d)}-\alpha_{m}\right)\cdot{K_{m}}}{N_{m}}}{\frac{K_{m}}{N_{m}}+L\cdot
2^{-\tau+\left\lceil\log_{2}(d+1)\right\rceil}}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\geq}}\frac{\frac{\left(C_{0}^{(d)}-\alpha_{m}\right)\cdot{K_{m}}}{N_{m}}}{\frac{K_{m}}{N_{m}}+2^{\left\lceil\log_{2}(d+1)\right\rceil}\cdot\left(\frac{(1-R)(1+\beta_{m})}{R(1-\epsilon)}+2^{-\tau}\right)},$

where (a) follows from equation (29) and (b) holds due to equation (28), with
$L\cdot
2^{-\tau}\leq\left(\frac{(1-R)(1+\beta_{m})}{R(1-\epsilon)}+2^{-\tau}\right)$.
Hence, by taking $\liminf_{m\to\infty}$ on both sides of the inequality (b)
above, we get

$\displaystyle\liminf_{m\to\infty}\text{rate}(\mathcal{C}_{m}^{\text{cos}})$
$\displaystyle\geq\frac{C_{0}^{(d)}\cdot
R}{R+2^{\left\lceil\log_{2}(d+1)\right\rceil}\cdot\left(\frac{1-R}{R(1-\epsilon)}\right)+2^{\left\lceil\log_{2}(d+1)\right\rceil-\tau}}$
$\displaystyle=\frac{(1-\epsilon)\cdot C_{0}^{(d)}\cdot R^{2}\cdot
2^{-\left\lceil\log_{2}(d+1)\right\rceil}}{(1-\epsilon)R^{2}\cdot
2^{-\left\lceil\log_{2}(d+1)\right\rceil}+1-R+R\cdot 2^{-\tau}(1-\epsilon)}$
$\displaystyle\geq\frac{(1-\epsilon)\cdot C_{0}^{(d)}\cdot R^{2}\cdot
2^{-\left\lceil\log_{2}(d+1)\right\rceil}}{(1-\epsilon)R^{2}\cdot
2^{-\left\lceil\log_{2}(d+1)\right\rceil}+1-R+2^{-\tau}(1-\epsilon)}$

where the first inequality holds since
$\frac{K_{m}}{N_{m}}\xrightarrow{m\to\infty}R$ and
$\alpha_{m},\beta_{m}\xrightarrow{m\to\infty}0$, and the last inequality holds
since $R\in(0,1)$. Finally, taking $\epsilon\downarrow 0$, we obtain the rate
lower bound in the statement of the Lemma.

We now prove that the rate lower bound derived above, is achievable over
$(d,\infty)$-RLL input-constrained BMS channel, using the decoding procedure
given in (D1)–(D2), so long as $R<C$. To this end, note that Step (D1) decodes
the $L$ parts, $\mathbf{c}_{1},\ldots,\mathbf{c}_{L}$, each with probability
of error at most $\eta_{m}>0$, with $\eta_{m}\xrightarrow{m\to\infty}0$, if
$R<C$. Hence, the probability of error
Pr$\left[\hat{c}_{K_{m}}^{N_{m}-1}\neq{c}_{K_{m}}^{N_{m}-1}\right]$ of the
decoding stage (D1), is at most $L\cdot\eta_{m}$. Moreover, given the event
$\left\\{\hat{c}_{K_{m}}^{N_{m}-1}={c}_{K_{m}}^{N_{m}-1}\right\\}$, Step (D2)
determines the information bits $w_{0}^{K_{m}-1}$, with probability of error
Pr$\left[\hat{c}_{0}^{K_{m}-1}\neq w_{0}^{K_{m}-1}\big{|}\
\hat{c}_{K_{m}}^{N_{m}-1}={c}_{K_{m}}^{N_{m}-1}\right]\leq\delta_{m}$, with
$\delta_{m}>0$ such that $\delta_{m}\xrightarrow{m\to\infty}0$, if $R<C$.
Hence, the overall probability of correct estimation of the information bits
$w_{0}^{K_{m}-1}$ can be bounded as

$\displaystyle\text{Pr}\left[\hat{c}_{0}^{K_{m}-1}=w_{0}^{K_{m}-1}\right]$
$\displaystyle\geq\text{Pr}\left[\hat{c}_{K_{m}}^{N_{m}-1}={c}_{K_{m}}^{N_{m}-1}\right]\cdot\text{Pr}\left[\hat{c}_{0}^{K_{m}-1}=w_{0}^{K_{m}-1}\big{|}\
\hat{c}_{K_{m}}^{N_{m}-1}={c}_{K_{m}}^{N_{m}-1}\right]$
$\displaystyle\geq(1-L\cdot\eta_{m})\cdot(1-\delta_{m}).$

As $L$ is a constant, the lower bound on the probability of correct estimation
converges to $1$, as $m\to\infty$. ∎

In Section III, we compared the achievable rate of $\frac{C}{2}$, for $d=1$,
obtained using linear subcodes of RM codes (Theorem III.1), with rates
achievable by the two-stage coding scheme above. An equivalent way of stating
our observations there is that the two-stage coding scheme achieves a higher
rate for erasure probabilities $\epsilon\lessapprox 0.2387$, when used over
the $(1,\infty)$-RLL input-constrained BEC, and for crossover probabilities
$p$ that are in the approximate interval $(0,0.0392)\cup(0.9608,1)$, when used
over the $(1,\infty)$-RLL input-constrained BSC.

##  VII Conclusion

This work proposed explicit, deterministic coding schemes, without feedback,
for binary memoryless symmetric (BMS) channels with $(d,\infty)$-runlength
limited (RLL) constrained inputs. In particular, achievable rates were
calculated by identifying specific constrained linear subcodes and proving the
existence of constrained, potentially non-linear subcodes, of a sequence of RM
codes of rate $R$. Furthermore, upper bounds were derived on the rate of the
largest linear $(d,\infty)$-RLL subcodes of RM codes of rate $R$, showing that
the linear subcodes identified in the constructions were essentially rate-
optimal. A novel upper bound on the rate of general $(1,\infty)$-RLL subcodes
was derived using properties of the weight distribution of RM codes, and a new
explicit two-stage coding scheme was proposed, whose rates are better than
coding schemes using linear subcodes, for large $R$.

There is much scope for future work in this line of investigation. Firstly,
following the close relationship between the sizes of $(1,\infty)$-RLL
subcodes and the weight distributions of RM codes established in this work, a
more sophisticated analysis of achievable rates can be performed with the
availability of better lower bounds on the weight distributions of RM codes.
Likewise, sharper upper bounds on the weight distributions of RM codes will
also lead to better upper bounds on the rate of any $(1,\infty)$-RLL subcodes
of a certain canonical sequence of RM codes. It would also be of interest to
derive good upper bounds on the rates of general $(d,\infty)$-RLL subcodes of
RM codes, via weight distributions or otherwise.

Further, we wish to explore the construction of general doubly-transitive
linear codes that contain a large number of $(d,\infty)$-RLL constrained
codewords. Such constructions will also help lend insight into the capacity of
input-constrained BMS channels without feedback, which is a well-known open
problem.

##  Appendix A Proof of Inequality (23)

In this section, we show that the inequality $\beta(m)\leq\theta(m)$ holds,
for large $m$ and sufficiently small $\delta>0$, with $\beta(m)$ and
$\theta(m)$ defined in equations (22) and (23), respectively.

We start with the expression

$\beta(m)=2^{o(2^{m})}\cdot\sum_{i=1}^{r_{m}-1}\exp_{2}\left(2^{m-1}\cdot
R_{m}^{(g)}\cdot h_{b}(2^{-i})-{m-2-i\choose\leq r_{m}}\right)$ (30)

We will split the sum $\sum\limits_{i=1}^{r_{m}-1}$ into two parts:
$\sum\limits_{i=1}^{t_{m}}$ and $\sum\limits_{i={t_{m}}+1}^{r_{m}-1}$, where
$t_{m}:=\lfloor m^{1/3}\rfloor$. For $i\in[t_{m}+1:r_{m}-1]$, we have

$2^{m-1}\cdot R_{m}^{(g)}\cdot h_{b}(2^{-i})-{m-2-i\choose\leq r_{m}}\ \leq\
2^{m-1}\cdot R_{m}^{(g)}\cdot h_{b}(2^{-i})\ =\ o(2^{m}),$

since $h_{b}(2^{-i})\leq h_{b}(2^{-t_{m}-1})$, and
$h_{b}(2^{-t_{m}-1})\xrightarrow{m\to\infty}0$, by the continuity of entropy.
Thus, the contribution of each term of the sum
$\sum\limits_{i={t_{m}}+1}^{r_{m}-1}$ is $2^{o(2^{m})}$, and since there are
at most $r_{m}=O(m)$ terms in the sum, the total contribution from the sum is
$2^{o(2^{m})}$.

Turning our attention to $i\in[t_{m}]$, we note first that for $m$ large
enough, it holds that $R_{m}^{(g)}\leq R(1+\epsilon)$, for $\epsilon\in(0,1)$
suitably small. Also, we write

$\displaystyle 2^{m-1}\cdot R_{m}^{(g)}\cdot$ $\displaystyle
h_{b}(2^{-i})-{m-2-i\choose\leq r_{m}}$ $\displaystyle\ \ \ \ \leq\
2^{m-1}\cdot\left[R(1+\epsilon)\cdot
h_{b}(2^{-i})-2^{-(i+1)}\cdot\frac{1}{2^{m-2-i}}{m-2-i\choose\leq
r_{m}}\right].$ (31)

By Lemma IV.1, we obtain that $\frac{1}{2^{m-2-i}}{m-2-i\choose\leq r_{m}}$
converges to $R$ for all $i\in[t_{m}]$. In fact, with a bit more effort, we
can show that this convergence is uniform in $i$. Indeed, since $i\leq t_{m}$,
by virtue of (6), we have
$|r_{m}-r_{m-2-i}|\leq\frac{t_{m}+2}{2}+\frac{\sqrt{t_{m}+2}}{2}\lvert
Q^{-1}(1-R)\rvert+1=:\nu_{m}$. Using the notation in the proof of Lemma IV.1,
we have $\frac{1}{2^{m-2-i}}{m-2-i\choose\leq r_{m}}=\Pr[S_{m-2-i}\leq
r_{m}]$. Thus, analogous to (7), we have for all sufficiently large $m$,

$\displaystyle\Pr[\overline{S}_{m-2-i}\leq
Q^{-1}(1-R)-\frac{\nu_{m}}{\frac{1}{2}\sqrt{m-2-t_{m}}}]\leq\
\Pr[S_{m-2-i}\leq r_{m}]\leq\ \Pr[\overline{S}_{m-2-i}\leq
Q^{-1}(1-R)+\frac{\nu_{m}}{\frac{1}{2}\sqrt{m-2-t_{m}}}].$

Now, we apply the Berry-Esseen theorem (see e.g., [46, Theorem 3.4.17]) which,
in this case, asserts that
$\left\lvert\Pr[\overline{S}_{m}\leq x]-\Pr[Z\leq x]\right\rvert\leq
3/\sqrt{m}$, for all $x\in\mathbb{R}$ and positive integers $m$, where $Z\sim
N(0,1)$. Thus,
$\left\lvert\Pr[\overline{S}_{m-2-i}\leq x]-\Pr[Z\leq
x]\right\rvert\leq\frac{3}{\sqrt{m-2-i}}\leq\frac{3}{\sqrt{m-2-t_{m}}}$ holds
for all $x\in\mathbb{R}$ and $i\in[t_{m}]$. This yields

$\displaystyle\Pr[Z\leq
Q^{-1}(1-R)-\frac{\nu_{m}}{\frac{1}{2}\sqrt{m-2-t_{m}}}]-\frac{3}{\sqrt{m-2-t_{m}}}$
$\displaystyle\ \ \leq\ \Pr[S_{m-2-i}\leq r_{m}]$ $\displaystyle\ \ \ \ \leq\
\Pr[Z\leq
Q^{-1}(1-R)+\frac{\nu_{m}}{\frac{1}{2}\sqrt{m-2-t_{m}}}]+\frac{3}{\sqrt{m-2-t_{m}}}.$

Since $t_{m}$ and $\nu_{m}$ are both $o(\\!\\!\sqrt{m})$, we deduce that, as
$m\to\infty$, $\Pr[S_{m-2-i}\leq r_{m}]=\frac{1}{2^{m-2-i}}{m-2-i\choose\leq
r_{m}}$ converges to $R$ uniformly in $i\in[t_{m}]$.

Hence, for small $\epsilon\in(0,1)$ and $m$ large enough, it holds for all
$i\in[t_{m}]$ that

$\frac{1}{2^{m-2-i}}{m-2-i\choose\leq r_{m}}\geq(1-\epsilon)R,$

so that, carrying on from (31), we have that

$\displaystyle R(1+\epsilon)\cdot
h_{b}(2^{-i})-2^{-(i+1)}\cdot\frac{1}{2^{m-2-i}}{m-2-i\choose\leq r_{m}}\leq
R\left[(1+\epsilon)\cdot h_{b}(2^{-i})-2^{-(i+1)}\cdot(1-\epsilon)\right].$
(32)

Now, we claim that for any $i\in\mathbb{N}$, the expression within square
brackets above can be bounded above as:

$\displaystyle(1+\epsilon)\cdot h_{b}(2^{-i})-2^{-(i+1)}\cdot(1-\epsilon)$
$\displaystyle\leq\frac{3}{4}+2\epsilon,$ (33)

The proof of equation (33) relies on simple calculus, and is relegated to
Appendix B.

To put it all together, recall that we split the sum
$\sum\limits_{i=1}^{r_{m}-1}$ in (30) into two parts:
$\sum\limits_{i=1}^{t_{m}}$ and $\sum\limits_{i={t_{m}}+1}^{r_{m}-1}$, where
$t_{m}:=\lfloor m^{1/3}\rfloor$. Given an arbitrarily small $\delta>0$, settng
$\epsilon=\delta/2$, we obtain via (31)–(33) that, for all sufficiently large
$m$, the contribution from the sum $\sum_{i=1}^{t_{m}}$ is at most

$m^{1/3}\cdot\exp_{2}\left(2^{m-1}R\cdot\left(\frac{3}{4}+\delta\right)\right).$

We noted earlier that the contribution from the sum
$\sum_{i=t_{m}+1}^{r_{m}-1}$ is $\text{exp}_{2}(o(2^{m}))$. Therefore, the
overall sum $\sum\limits_{i=1}^{r_{m}-1}$ in (30) can be bounded above, for
all sufficiently large $m$, by

$2m^{1/3}\cdot\exp_{2}\left(2^{m-1}R\cdot\left(\frac{3}{4}+\delta\right)\right),$

Consequently,

$\beta(m)\ \leq\
\text{exp}_{2}\left(2^{m-1}R\cdot\left(\frac{3}{4}+\delta\right)+o(2^{m})\right)\
=:\ \theta(m).$

##  Appendix B Proof of inequality (33)

In this section, we show that the inequality in (33) holds.

Firstly, we note that the expression on the left of (33) obeys, for $i\geq 1$,

$\displaystyle(1+\epsilon)\cdot h_{b}(2^{-i})-2^{-(i+1)}\cdot(1-\epsilon)$
$\displaystyle=h_{b}(2^{-i})-2^{-(i+1)}+\epsilon\left(h_{b}(2^{-i})+2^{-(i+1)}\right)$
$\displaystyle\leq h_{b}(2^{-i})-2^{-(i+1)}+2\epsilon.$ (34)

Now, consider the function $f(x)=h_{b}(2^{-x})-2^{-(x+1)}$, where
$x\in[0,\infty)$. By taking the derivative with respect to $x$ on both sides,
we get

$f^{\prime}(x)=(2^{-x}\ln
2)\cdot\left[\frac{1}{2}-\log_{2}\left(\frac{1-2^{-x}}{2^{-x}}\right)\right].$

The term within square brackets above is positive when
$x\in\left(0,\log_{2}(1+\sqrt{2})\right)$, and is negative for
$x\in\left(\log_{2}(1+\sqrt{2}),\infty\right)$. Importantly, this implies that
$f$ is decreasing in the interval $[2,\infty)$. Furthermore, we note that
$f(1)=h_{b}(\frac{1}{2})-\frac{1}{4}=\frac{3}{4}$, and
$f(2)=h_{b}(\frac{1}{4})-\frac{1}{8}\approx 0.68<f(1)$. Hence, $f$ is
decreasing over integers $i\in\mathbb{N}$.

With this, we obtain that the right side of the inequality in (34) is at most
$\frac{3}{4}+2\epsilon$.

## References

  * [1] B. H. Marcus, R. M. Roth, and P. H. Siegel, “An introduction to coding for constrained systems,” lecture notes. [Online]. Available: https://ronny.cswp.cs.technion.ac.il/wp-content/uploads/sites/54/2016/05/chapters1-9.pdf
  * [2] K. A. S. Immink, P. H. Siegel, and J. K. Wolf, “Codes for digital recorders,” _IEEE Transactions on Information Theory_ , vol. 44, no. 6, pp. 2260–2299, Oct. 1998.
  * [3] K. A. S. Immink, “Runlength-limited sequences,” _Proceedings of the IEEE_ , vol. 78, no. 11, pp. 1745–1759, 1990.
  * [4] A. M. Fouladgar, O. Simeone, and E. Erkip, “Constrained codes for joint energy and information transfer,” _IEEE Transactions on Communications_ , vol. 62, no. 6, pp. 2121–2131, 2014.
  * [5] E. Arikan, “Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels,” _IEEE Transactions on Information Theory_ , vol. 55, no. 7, pp. 3051–3073, 2009.
  * [6] S. Kudekar, S. Kumar, M. Mondelli, H. D. Pfister, E. Şaşoǧlu, and R. L. Urbanke, “Reed-Muller codes achieve capacity on erasure channels,” _IEEE Transactions on Information Theory_ , vol. 63, no. 7, pp. 4298–4316, 2017.
  * [7] M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman, “Efficient erasure correcting codes,” _IEEE Transactions on Information Theory_ , vol. 47, no. 2, pp. 569–584, 2001.
  * [8] T. J. Richardson, M. A. Shokrollahi, and R. L. Urbanke, “Design of capacity-approaching irregular low-density parity-check codes,” _IEEE Transactions on Information Theory_ , vol. 47, no. 2, pp. 619–637, 2001.
  * [9] S. Kudekar, T. Richardson, and R. L. Urbanke, “Spatially coupled ensembles universally achieve capacity under belief propagation,” _IEEE Transactions on Information Theory_ , vol. 59, no. 12, pp. 7761–7813, 2013.
  * [10] E. Zehavi and J. K. Wolf, “On runlength codes,” _IEEE Transactions on Information Theory_ , vol. 34, no. 1, pp. 45–54, Jan. 1988.
  * [11] Y. Li and G. Han, “Asymptotics of input-constrained erasure channel capacity,” _IEEE Transactions on Information Theory_ , vol. 64, no. 1, pp. 148–162, Jan. 2018.
  * [12] G. Han and B. Marcus, “Asymptotics of input-constrained binary symmetric channel capacity,” _The Annals of Applied Probability_ , vol. 19, no. 3, pp. 1063–1091, 2009. [Online]. Available: https://doi.org/10.1214/08-AAP570
  * [13] E. Ordentlich and T. Weissman, “Bounds on the entropy rate of binary hidden Markov processes,” in _Entropy of Hidden Markov Processes and Connections to Dynamical Systems: Papers from the Banff International Research Station Workshop_ , B. Marcus, K. Petersen, and T. Weissman, Eds. London Mathematical Society Lecture Notes Series, Cambridge University Press, 2011, pp. 117–171.
  * [14] O. Ordentlich, “Novel lower bounds on the entropy rate of binary hidden Markov processes,” in _Proc. 2016 IEEE International Symposium on Information Theory (ISIT 2016)_ , Barcelona, Spain, 10–15 July 2016, pp. 690–694.
  * [15] V. A. Rameshwar and N. Kashyap, “Numerically computable lower bounds on the capacity of the $(1,\infty)$-RLL input-constrained binary erasure channel,” in _Proc. 2021 National Conference on Communications (NCC 2021)_ , Kanpur, India, 27–30 July 2021.
  * [16] V. A. Rameshwar and N. Kashyap, “Computable lower bounds for capacities of input-driven finite-state channels,” in _Proc. 2020 IEEE International Symposium on Information Theory (ISIT 2020)_ , virtual conference, 21–26 June 2020, pp. 2002–2007.