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

The paper considers coding schemes derived from Reed-Muller (RM) codes, for transmission over input-constrained memoryless channels. Our focus is on the $(d,\mathrm{\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,\mathrm{\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,\mathrm{\infty })$-RLL subcodes of rate $R\cdot 2^{-\lceil {\log }_2(d+1)\rceil }$. We then show that our construction is essentially rate-optimal, by deriving an upper bound on the rates of linear $(d,\mathrm{\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,\mathrm{\infty })$-RLL subcodes that achieve a rate of $\max (0,R-\frac{3}{8})$. This, for $R>3\mathrm{/}4$, beats the $R\mathrm{/}2$ rate obtainable from linear subcodes. We further derive upper bounds on the rates of $(1,\mathrm{\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,\mathrm{\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,\mathrm{\infty })$-RLL subcodes, for values of $R$ close to $1$.