2006/01/01 by Rudolf Ahlswede, Christian Deppe, Ahlswede, Rudolf +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Cellular Automata and Applications #DNA and Biological Computing #Error-correcting codes #feedback #localized errors #variable length codes
paper · doi:10.4230/dagsemproc.06201.4
openalex publication_date 2006/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 τ (>1\over q) and infinitely many points on the Hamming bound for small τ. 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 τ <1/2. Somewhat surprisingly, whereas with feedback the capacity curve coincides with the Hamming bound also for 1/2≤ τ ≤ 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.