COMPLEXITY AND SLIDING-BLOCK DECODABILITY

A constrained system, or sofic system, S is the set of symbol strings generated by the finite-length paths through a finite labeled, directe d graph, Karabed and Marcus, extending the work of Adler, Coppersmith, and Hassner, used the technique of state-splitting to prove the exist ence of a noncatastrophic, rate p:q finite-state encoder from binary d ata into S for any input word length p and codeword length q satisfyin g p/q less than or equal to cap(S), the Shannon capacity, For constrai ned systems that are almost-finite-type, they further proved the exist ence of encoders enjoying a stronger form of decodability-namely, slid ing-block decodability. In particular, their result implies the existe nce of a 100% efficient (rate 1/2), sliding-block code for the charge- constrained, runlength-limited constraint with parameters (d, k; c) = (1, 3; 3), an almost-finite-type system with capacity precisely 1/2, I n this paper, we describe two quite different constructions of such co des, The constructions highlight connections between the problem of de termining. sliding-block decodability of a finite-state encoder and ce rtain problems of colorability for graphs and sets. Using these connec tions, we show that the problem of determining the existence of a bloc k-decodable input tag assignment for a given rate p:q, finite-state en coder is NP-complete, for p > 1, We also prove NP-completeness results for several related problems in combinatorics and coding.