We introduce a novel framework for implementing error-correction in constrained systems. The main idea of our scheme, called Quantized-Constraint Concatenation (QCC), is to employ a process of embedding the codewords of an error-correcting code in a constrained system as a (noisy, non-invertible) quantization process. This is in contrast to traditional methods, such as concatenation and reverse concatenation, where the encoding into the constrained system is reversible. The possible number of channel errors QCC is capable of correcting is linear in the block lengthn, improving upon theO(√n) possible with the state-of-the-art known schemes. For a given constrained system, the performance of QCC depends on a new fundamental parameter of the constrained system – its covering radius. Motivated by QCC, we study the covering radius of constrained systems in both combinatorial and probabilistic settings. We reveal an intriguing characterization of the covering radius of a constrained system using ergodic theory. We use this equivalent characterization in order to establish efficiently computable upper bounds on the covering radius.

We introduce a novel framework for implementing error-correction in constrained systems. The main idea of our scheme, called Quantized-Constraint Concatenation (QCC), is to employ a process of embedding the codewords of an error-correcting code in a constrained system as a (noisy, irreversible) quantization process. This is in contrast to traditional methods, such as concatenation and reverse concatenation, where the encoding into the constrained system is reversible. The possible number of channel errors QCC is capable of correcting is linear in the block length n, improving upon the $O\left( {\sqrt n } \right)$ possible with the state-of-the-art known schemes. For a given constrained system, the performance of QCC depends on a new fundamental parameter of the constrained system – its covering radius.Motivated by QCC, we study the covering radius of constrained systems in both combinatorial and probabilistic settings. We reveal an intriguing characterization of the covering radius of a constrained system using ergodic theory.

Motivated by applications for error-correcting constrained codes, we study the essential covering radius of constrained systems. In a recent work, the essential covering radius was suggested as new fundamental parameter of constrained systems that characterizes the error-correction capabilities of the quantized-constraint concatenation (QCC) scheme. We provide general efficiently computable upper-bounds on the essential covering radius using Markov chains and sliding-block codes, which in some cases, we show to be tight.

We find a new formula for the limit of the capacity of certain sequences of multidimensional semiconstrained systems as the dimension tends to infinity. We do so by generalizing the notion of independence entropy, originally studied in the context of constrained systems, to the study of semiconstrained systems. Using the independence entropy, we obtain new lower bounds on the capacity of multidimensional semiconstrained systems in general, and d-dimensional axial-product systems in particular. In the case of the latter, we prove our bound is asymptotically tight, giving the exact limiting capacity in terms of the independence entropy. We show the new bound improves upon the best-known bound in a case study of (0, k, p)-RLL.

We generalize the notion of independence entropy to the study of semiconstrained systems. Using it, we obtain a new lower bound on the capacity of multi-dimensional semiconstrained systems. We show the new bound improves upon the best-known bound in a case study of (0, k, p)-RLL semiconstrained systems.

Semiconstrained systems were recently suggested as a generalization of constrained systems, commonly used in communication and data-storage applications that require certain offending subsequences be avoided. In an attempt to apply techniques from constrained systems, we study sequences of constrained systems that are contained in, or contain, a given semiconstrained system, while approaching its capacity. In the case of contained systems we describe to such sequences resulting in constant-to-constant bit-rate block encoders and sliding-block encoders. Surprisingly, in the case of containing systems we show that a “generic” semiconstrained system is never contained in a proper fully-constrained system.

When transmitting information over a noisy channel, two approaches, dating back to Shannon's work, are common: assuming the channel errors are independent of the transmitted content and devising an error-correcting code or assuming the errors are data dependent and devising a constrained-coding scheme that eliminates all offending data patterns. In this paper, we analyze a middle road, which we call a semiconstrained system. In such a system, which is an extension of the channel with the cost constraints model, we do not eliminate the error-causing sequences entirely, but rather restrict the frequency in which they appear. We address several key issues in this paper. The first is proving closed-form bounds on the capacity, which allow us to bound the asymptotics of the capacity. In particular, we bound the rate at which the capacity of the semiconstrained (0,k) -RLL tends to 1 as k grows. The second key issue is devising efficient encoding and decoding procedures that asymptotically achieve capacity with vanishing error. Finally, we consider delicate issues involving the continuity of the capacity and a relaxation of the definition of semiconstrained systems.

When transmitting information over a noisy channel, two approaches are common: assuming the channel errors are independent of the transmitted content and devising an error-correcting code, or assuming the errors are data dependent and devising a constrained-coding scheme that eliminates all offending data patterns. In this paper we analyze a middle road, which we call a semiconstrained system. In such a model, which is an extension of the channel with cost constraints, we do not eliminate the error-causing sequences entirely, but rather restrict the frequency in which they appear. We address several key issues in this study. The first is proving closed-form bounds on the capacity which allow us to bound the asymptotics of the capacity. In particular, we bound the rate at which the capacity of the semiconstrained (0, k)-RLL tends to 1 as k grows. The second key issue is devising efficient encoding and decoding procedures that asymptotically achieve capacity with vanishing error. Finally, we consider delicate issues involving the continuity of the capacity and a relaxation of the definition of semiconstrained systems.