Optimal code rates for constrained systems with unconstrained positions: An approach to combining error correction codes with modulation codes for digital storage systems.

摘要

Error-control codes (ECCs) and constrained codes are both widely used in digital storage systems, where the situation corresponds to a noisy channel with a modulation constraint on the input. For practical reasons, independent error correction and modulation encoders are typically used and cascaded in some fashion. Constrained systems with unconstrained positions is a recent scheme that mitigates error propagation and facilitates soft decoding. In this scheme, the modulation encoder produces constrained sequences such that certain bit positions are unconstrained , in the sense that these positions can take on either bit value without violating the constraint. These positions are then used for the insertion of ECC parity bits. Although it has been implemented in some commercial disk drives, usage has been limited by the lack of a systematic approach to code design and an understanding of the achievable rate regions.; To this end, we present a new general framework for analyzing this scheme. We construct a graph containing all information on permissible sets of unconstrained positions, without requiring a pre-specified period or set of unconstrained positions. Properties of this graph are established. We also investigate the maximum insertion rate (maximum density of unconstrained positions permitted by the constraint), which corresponds to the highest redundancy permissible for any ECC that can be used with the constraint. It is shown that this quantity is rational and computable. We formally define the tradeoff function, which represents the frontier of the achievable code rate region over the range of permissible insertion rates. The tradeoff function is shown to be monotonic, continuous, and concave for finite-type constraints. We also show that periodic patterns of unconstrained positions achieve the optimal code rate for a given insertion rate. A result on timesharing is given, which allows for weighted combinations of configurations and makes it possible to exactly meet the rate of any ECC in the permissible range. Exact tradeoff functions for certain MTR and RLL constraints are determined. For a general constraint, the tradeoff function remains difficult to compute exactly, but we present several efficient algorithms for computing upper and lower bounds.