A new approach to constructing optimal block codes for runlength-limited channels

The paper describes a technique for constructing fixed-length block codes for (d, k)-constrained channels. The codes described are of the simplest variety-codes for which the encoder restricted to any particular channel state is a one-to-one mapping and which is not permitted to “look ahead” to future messages. Such codes can be decoded with no memory and no anticipation and are thus an example of what Schouhamer Immink (1992) has referred to as block-decodable. For a given blocklength n and given values of (d, k), the procedure constructs a code with the highest possible rate among all such block codes, and it does so without the iterative search that is typically used (i.e., Franaszek´s recursive elimination algorithm). The technique used is similar to Beenker and Immink´s (1983) “Construction 2” in that every message is associated with a (d, k, l, r) sequence of length n-d; however the values used in the present approach are l=k-d and r=k-1, as opposed to Beenker and Schouhamer Immink´s values of l=r=k-d. Thus the present approach demonstrates that “Construction 2” is optimal for d=1 but is suboptimal for d>1. Furthermore, the structure of the present codes permits enumerative coding techniques to simplify encoding and decoding