HP Labs Technical Reports

Nested Input-Constrained Codes

Hogan, Josh; Roth, Ron M; Ruckenstein, Gitit

HPL-98-165

Keyword(s): constrained systems; deterministic encoders; finite- state encoders; input-constrained channels; nested encoders

Abstract: An input-constrained channel, or simply a constraint, is a set of S of words that is generated by a finite labeled directed graph. In the context of coding, the study of constraints mainly aims at designing encoders that map unconstrained input words into words of S in a lossless manner. In most applications, the encoders are finite-state machines that map in each time slot a fixed-length input block into a fixed-length channel block, and decoding is carried out by looking ahead at finitely-many upcoming channel blocks. The state diagram of a finite-state encoder provides a graph presentation of that encoder. In the special case where this graph is (output) deterministic, only the current channel block is needed for decoding the current input block. In this work, the problem of designing encoders that can serve two constraints simultaneously is considered. Specifically, given two constraints S (sub)1 and S (sub)2 such that S (sub)1 is contained as a subset of S (sub)2 and two prescribed rates, conditions are provided for the existence of respective deterministic finite-state encoders E (sub)1 and E (sub)2, at the given rates, such that (the state diagram of) E (sub)1 is a subgraph of E (sub)2. Such encoders are referred to as nested encoders. The provided conditions are also constructive in that they imply an algorithm for finding such encoders when they exist. The nesting structure allows to decode E (sub)1 while using the decoder of E(sub)2. Recent developments in optical recording suggest a potential application that can take a significant advantage of nested encoders.

39 Pages

Back to Index