Fixed-Rate Maximum-Runlength-Limited Codes From Variable-Rate Bit Stuffing

We introduce the fixed-rate bit stuff (FRB) algorithm for efficiently encoding and decoding maximum-runlength-limited (MRL) sequences. Our approach is based on a simple, variable-rate technique called bit stuffing. Bit stuffing produces near-capacity achieving codes for a wide range of constraints, but encoding is variable-rate, which is unacceptable in most applications. In this work, we design near-capacity fixed-rate codes using a three-step procedure. The fixed-length input data block first undergoes iterative preprocessing, followed by variable-rate bit stuffing, and finally dummy-bit padding to a fixed output length. The iterative preprocessing is key to achieving high encoding rates. We discuss rate computation for the proposed FRB algorithm and show that the asymptotic (in input block length) encoding rate is close to the average rate of the variable-rate bit stuff code. Then, we proceed to explore the effect of decreasing/increasing the number of preprocessing iterations. Finally, we derive a lower bound on the encoding rate with finite-length input blocks and tabulate the parameters required to design FRB codes with rate close to 100/101 and 200/201.