Coding Schemes Based on Reed-Muller Codes for (d, ∞)-RLL Input-Constrained Channels
V. Arvind Rameshwar, Navin Kashyap · IEEE Transactions on Information Theory · 2023
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 1s be separated by at least$d~0\text{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.