In this work, we consider the analysis and design of optimal block-decodable M-ary runlength-limited (RLL) codes. We present two general construction methods: one based on permutation codes due to Datta and McLaughlin (1999), and the other, a nonbinary generalization of the binary enumeration methods of Patrovics and Immink (1996), and Gu and Fuja (1994). The construction based on permutation codes is simple and asymptotically (in block length) optimal, while the other construction is optimal in the sense that the resulting codes have the highest rate among all block-decodable codes for any block length. In the process, we shall also extend a result due to Zehavi and Wolf (1988) on the capacity of binary (d, k) constraints to M-ary channels. Finally, we present examples of template codes: remarkably low-complexity (M,d,k) block codes which achieve the optimal rate without the use of enumeration.

Permutation codes, introduced by Slepian (1965), were shown to perform well on an additive white Gaussian noise (AWGN) channel. Unfortunately, these codes required large lookup tables, making them quite complex to implement even though the maximum-likelihood decoder is very simple. In this correspondence, we present an enumeration scheme which encodes and decodes permutation codes with low complexity. We concentrate on the use of permutation codes for constructing high-rate codes that satisfy runlength-limited constraints. Wolf (1990) showed that permutation codes can be used for runlength constraints and that they have rate that asymptotically achieves the capacity of a noiseless, runlength-limited constrained channel. Wolf, however, gave no efficient encoders/decoder. Our code construction is enumerative, but unlike other enumerative codes, has storage requirements that are a function of the runlength parameters d and k instead of the block length n. In addition, these codes have error detection and correction capabilities. Finally, we use this approach to construct (0, G/I) codes whereby all odd-numbered occurrences of double-adjacent errors are detected. As an example, a 99.2% efficient, rate 498/528, (0, 6/3) code is presented.