Non--binary error correcting codes with noiseless feedback, localized errors, or both

Authors Rudolf Ahlswede, Christian Deppe, Vladimir Lebedev



PDF
Thumbnail PDF

File

DagSemProc.06201.4.pdf
  • Filesize: 89 kB
  • 4 pages

Document Identifiers

Author Details

Rudolf Ahlswede
Christian Deppe
Vladimir Lebedev

Cite As Get BibTex

Rudolf Ahlswede, Christian Deppe, and Vladimir Lebedev. Non--binary error correcting codes with noiseless feedback, localized errors, or both. In Combinatorial and Algorithmic Foundations of Pattern and Association Discovery. Dagstuhl Seminar Proceedings, Volume 6201, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006) https://doi.org/10.4230/DagSemProc.06201.4

Abstract

We investigate non--binary error correcting codes with noiseless feedback, localized errors, or both. It turns out that the Hamming bound is a central concept. For block codes with feedback we present here a coding scheme based on an idea of erasions, which we call the {\bf rubber method}.  It gives an optimal rate for big error correcting fraction $\tau$ ($>{1\over q}$) and infinitely many points on the Hamming bound for small $\tau$.

We also consider variable length codes with all lengths bounded from above by $n$ and the end of a word carries the symbol $\Box$ and is thus recognizable by the decoder. For both, the $\Box$-model with feedback and the $\Box$-model with localized errors, the Hamming bound is the exact capacity curve for $\tau <1/2.$ Somewhat surprisingly, whereas with feedback the capacity curve coincides with the Hamming bound also for 
$1/2\leq \tau \leq 1$, in this range for localized errors the capacity curve equals 0.

Also we give constructions for the models with both, feedback and localized errors.

Subject Classification

Keywords
  • Error-correcting codes
  • localized errors
  • feedback
  • variable length codes

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail