
HP Labs Technical Reports
Click here for full text:
Nested InputConstrained Codes
Hogan, Josh; Roth, Ron M; Ruckenstein, Gitit
HPL98165
Keyword(s): constrained systems; deterministic encoders; finite state encoders; inputconstrained channels; nested encoders
Abstract: An inputconstrained 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 finitestate machines that map in each time slot a fixedlength input block into a fixedlength channel block, and decoding is carried out by looking ahead at finitelymany upcoming channel blocks. The state diagram of a finitestate 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 finitestate 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
