Technical Report MSC-1996-01

Title: Encoding for Input-Constrained Channels
Authors: Gitit Ruckenstein (Ronny Roth)
Abstract: Input-constrained channels are models for describing the read-write requirements of secondary storage systems, such as magnetic disks or optical devices. Examples for such requirements are the widely used (d,k)-run-length-limited (RLL) constraints, where each run of 0's between consecutive 1's in a binary sequence must have length at least d and at most k. A constrained system S is defined as the set of constrained sequences obtained by reading the labels of paths of a finite labelled directed graph G. The graph G is then called the presentation of S. One goal in the study of constrained systems is designing encoders that map unconstrained sequences into constrained sequences of a given constrained system S. A fixed rate p:q finite-state encoder for S encodes p-blocks of input bits to q-blocks in S, in a state-dependent and lossless manner. The anticipation (or decoding look-ahead) of an encoder is the smallest integer A, if any, such that the encoder state at each time slot t, together with the q-blocks generated at times t,t+1,...,t+A, determine uniquely the p-block input at time slot t. One of the well known schemes for constructing finite-state encoders is the Adler-Coppersmith-Hassner algorithm, also known as the state-splitting algorithm. Any encoder obtained by the state-splitting algorithm from a deterministic presentation G has finite anticipation. In this work, we present lower bounds on the anticipation of encoders for given constrained systems, while strengthening the universality of the state-splitting algorithm. It is shown that if there exists an encoder with anticipation A for a given system, then an unreduced version of this encoder can be obtained by the state-splitting algorithm, using A rounds of splitting. Furthermore, by specifying several properties of those splittings, we obtain a lower bound on the anticipation of any encoder for a given constrained system. The new lower bound improves on previous known bounds and in particular, it is tight for several known and widely used systems, such as the (1,7)-RLL and the (2,7)-RLL constrained systems.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 1996
To the main CS technical reports page

Computer science department, Technion