Hi all,
Our next meeting in the Information Theory and Applications seminar will
take place on Monday, June 3 at 10:00, in room A500.
The speaker is Dor Elimelch, who will tell us about error correction in
constrained systems.
See you there,
Or, Oron, Yuval and Alex
---------------------------------------------
*Title:* Quantized-Constraint Concatenation and the Covering Radius of
Constrained Systems
*Abstract:* 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
length $n$, improving upon the $O(\sqrt{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, which we use
in order to establish efficiently computable upper bounds on the covering
radius.
