Share Email Print

Proceedings Paper

Efficient coding for a two-dimensional runlength-limited constraint
Author(s): Ronald M. Roth; Paul H. Siegel; Jack Keil Wolf
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

Runlength-limited (d,k) constraints and codes are widely used in digital data recording and transmission applications. Generalizations of runlength constraints to two dimension are of potential interest in page-oriented information storage systems. However, in contrast to the one-dimensional case, little is known about the information-theoretic properties of two-dimensional constraints or the design of practical, efficient codes for them. In this paper, we consider coding schemes that map unconstrained binary sequences into two- dimensional, runlength-limited (d, (infinity) ) constrained binary arrays, in which 1's are followed by at least d 0's in both the horizontal and vertical dimensions. We review the derivation of a lower bound on the capacity of two-dimensional (d, (infinity) ) constraints, for d greater than or equal to 1, obtained by bounding the average information rate of a variable-to-fixed rate encoding scheme, based upon a 'bit- stuffing' technique. For the special case of the two- dimensional (1, (infinity) ) constraint, upper and lower bounds on the capacity that are very close to being tight are known. For this constraint, we determine the exact average information rate of the bit-stuffing encoder, which turns out to be within 1% of the capacity of the constraint. We then present a fixed- rate, row-by-row encoding scheme for the two-dimensional (1, (infinity) ) constraint, somewhat akin to permutation coding, in which the rows of the code arrays represent 'typical' rows for the constraint. It is shown that, for sufficiently long rows, the rate of this encoding technique can almost achieve that of the variable-rate, bit-stuffing scheme.

Paper Details

Date Published: 22 November 1999
PDF: 10 pages
Proc. SPIE 3802, Advanced Optical Data Storage: Materials, Systems, and Interfaces to Computers, (22 November 1999); doi: 10.1117/12.370243
Show Author Affiliations
Ronald M. Roth, Technion--Israel Institute of Technology (Israel)
Paul H. Siegel, Univ. of California/San Diego (United States)
Jack Keil Wolf, Univ. of California/San Diego (United States)

Published in SPIE Proceedings Vol. 3802:
Advanced Optical Data Storage: Materials, Systems, and Interfaces to Computers
Pericles A. Mitkas; Zameer U. Hasan; Hans J. Coufal; Glenn T. Sincerbox, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?