Efficient coding for a two-dimensional runlength-limited constraint

Ronald M. Roth; Paul H. Siegel; Jack Keil Wolf

doi:10.1117/12.370243

22 November 1999 Efficient coding for a two-dimensional runlength-limited constraint

Ronald M. Roth, Paul H. Siegel, Jack Keil Wolf

Proceedings Volume 3802, Advanced Optical Data Storage: Materials, Systems, and Interfaces to Computers; (1999) https://doi.org/10.1117/12.370243
Event: SPIE's International Symposium on Optical Science, Engineering, and Instrumentation, 1999, Denver, CO, United States

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.

Citation Download Citation

Ronald M. Roth, Paul H. Siegel, and Jack Keil Wolf "Efficient coding for a two-dimensional runlength-limited constraint", Proc. SPIE 3802, Advanced Optical Data Storage: Materials, Systems, and Interfaces to Computers, (22 November 1999); https://doi.org/10.1117/12.370243

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available