Bounds on the size of runlength-limited codes.
Shih‐Hsuan Yang · Deep Blue (University of Michigan) · 1994
During the last two decades storage density, in terms of bits per unit length or per unit area, has increased greatly, in part because of advances in coding and signal processing techniques. In this dissertation, coding problems associated with digital storage systems are investigated. In particular, we examine one of the most important coding techniques in digital recording practice, the runlength-limited (RLL) code. When a RLL code is used on a noisy channel, error-correction control is often needed in order to obtain the desired system reliability. It is of fundamental importance to find high rate codes which satisfy both runlength-limited and error-correction requirements. A lower bound on the maximum size of an error-correcting RLL code, has recently been reported by Kolesnik and Krachkovsky, using a generating function technique. General upper bounds on the maximum size of error-correcting RLL codes, however, have not been extensively studied. In this dissertation, we derive three asymptotic upper bounds for the rate of such codes. We also generalize Kolesnik and Krachkovsky's technique to derive a number of new results. A write-once memory is a binary storage medium in which the storage cells can be changed from the 0-state to the 1-state only once. Many digital storage systems, including punch cards, paper tapes, PROMs and optical disks, have this "write-once" property. In this dissertation, the reusability of write-once memory is investigated. In addition to the write-once restriction, a runlength-limited constraint is imposed. The maximum amount of information that can be stored in a write-once memory which satisfies the RLL constraint is derived. A practical coding scheme which achieves at least 1/4 of the maximum capacity for a class of RLL-constrained write-once memories, is also presented.