2026-07-22T03:34:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:784 2024-03-06T11:06:53Z ddc:004 open_access

Non--binary error correcting codes with noiseless feedback, localized errors, or both Ahlswede, Rudolf Deppe, Christian Lebedev, Vladimir Error-correcting codes localized errors feedback variable length codes 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rudolf Ahlswede and Christian Deppe and Vladimir Lebedev 2006 Is Part Of Dagstuhl Seminar Proceedings, Volume 6201, Combinatorial and Algorithmic Foundations of Pattern and Association Discovery (2006) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.06201.4 urn:nbn:de:0030-drops-7849 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06201.4 eng https://creativecommons.org/licenses/by/4.0/legalcode