Nested input-constrained codes

An input-constrained channel, or simply a constraint, is a set S of words t hat is generated by a finite labeled directed graph. An encoder for S maps in a lossless manner sequences of unconstrained input blocks into sequences of channel blocks, the latter sequences being words of S, In most applicat ions, the encoders are finite-state machines and, thus, presented by state diagrams. In the special case where the state diagram of the encoder is (ou tput) deterministic, only the current encoder state and the current channel block are needed for the decoding of the current input block. In this work, the problem of designing coding schemes that can serve two co nstraints simultaneously is considered. Specifically, given two constraints S-1 and S-2 such that S-1 subset of or equal to S-2 and two prescribed rat es, conditions are provided for the existence of respective deterministic f inite-state encoders epsilon(1) and epsilon(2), at the given rates, such th at (the state diagram of) epsilon(1) is a subgraph of epsilon(2). Such enco ders are referred to as nested encoders. The provided conditions are also c onstructive in that they imply an algorithm for finding such encoders when they exist. The nesting structure allows to decode epsilon(1) while using t he decoder of epsilon(2). Recent developments in optical recording suggest a potential application th at tan take a significant advantage of nested encoders.