Nested Input-Constrained Codes

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

HP Development Company

关键词: constrained systems;    deterministic encoders;    finite- state encoders;    input-constrained channels;    nested encoders;   

RP-ID  :  HPL-98-165

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

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