Feedback insertion-deletion codes

DOI10.1134/S0032946021030029MaRDI QIDQ2068653zbMATH OpenOpenAlexFDO

Authors Georg Maringer, Nikita Polyanskii, L. Welter, I. V. Vorob'ev

Publication date 20 January 2022

Published in Problems of Information Transmission (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2010.15928

zbMATH Keywords

asymptotic ratecoding with feedbackinsertions and deletions

Mathematics Subject Classification ID

Source coding (94A29)

Abstract: In this paper, a new problem of transmitting information over the adversarial insertion-deletion channel with feedback is introduced. Suppose that the encoder transmits $n$ binary symbols one-by-one over a channel, in which some symbols can be deleted and some additional symbols can be inserted. After each transmission, the encoder is notified about the insertions or deletions that have occurred within the previous transmission and the encoding strategy can be adapted accordingly. The goal is to design an encoder that is able to transmit error-free as much information as possible under the assumption that the total number of deletions and insertions is limited by $aun$, $0<au<1$. We show how this problem can be reduced to the problem of transmitting messages over the substitution channel. Thereby, the maximal asymptotic rate of feedback insertion-deletion codes is completely established. The maximal asymptotic rate for the adversarial substitution channel has been partially determined by Berlekamp and later finished by Zigangirov. However, the analysis of the lower bound by Zigangirov is quite complicated. We revisit Zigangirov's result and present a more elaborate version of his proof.

Recommendations

• Reliable communication over channels with insertions, deletions, and substitutions
• Error correction for channels with substitutions, insertions, and deletions
• Asymptotically good codes correcting insertions, deletions, and transpositions
• Optimally resilient codes for list-decoding from insertions and deletions
• On multiple insertion/deletion correcting codes

Cites work

• A class of simple and optimal strategies for block coding on the binary symmetric channel with noiseless feedback
• An improved bound on the fraction of correctable deletions
• An Improved Bound on the Fraction of Correctable Deletions
• An Overview of Capacity Results for Synchronization Channels
• Asymptotically good codes correcting insertions, deletions, and transpositions
• Coding with noiseless feedback
• scientific article; zbMATH DE number 3566730 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• Sequential transmission using noiseless feedback

Cited in

(1)

• Asymptotically good codes correcting insertions, deletions, and transpositions

This page was built for publication: Feedback insertion-deletion codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2068653)