DROPS

Document

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

Authors: Rudolf Ahlswede, Christian Deppe, and Vladimir Lebedev

Published in: Dagstuhl Seminar Proceedings, Volume 6201, Combinatorial and Algorithmic Foundations of Pattern and Association Discovery (2006)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{ahlswede_et_al:DagSemProc.06201.4,
  author =	{Ahlswede, Rudolf and Deppe, Christian and Lebedev, Vladimir},
  title =	{{Non--binary error correcting codes with noiseless feedback, localized errors, or both}},
  booktitle =	{Combinatorial and Algorithmic Foundations of Pattern and Association Discovery},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6201},
  editor =	{Rudolf Ahlswede and Alberto Apostolico and Vladimir I. Levenshtein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06201.4},
  URN =		{urn:nbn:de:0030-drops-7849},
  doi =		{10.4230/DagSemProc.06201.4},
  annote =	{Keywords: Error-correcting codes, localized errors, feedback, variable length codes}
}

Search Results

Documents authored by Lebedev, Vladimir

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

Abstract

Cite as

Thanks for your feedback!

Could not send message