Feedback Insertion-Deletion Codes

A new problem of transmitting information over the adversarial insertion-deletion channel with feedback is introduced. Assume that the encoder transmits 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,...

Full description

Saved in:
Bibliographic Details
Published in:Problems of information transmission 2021-07, Vol.57 (3), p.212-240
Main Authors: Maringer, G., Polyanskii, N. A., Vorobyev, I. V., Welter, L.
Format: Article
Language:English
Subjects:
639/301/1034/1035
639/925/357/995
Asymptotic properties
Coders
Coding Theory
Communications Engineering
Control
Deletion
Electrical Engineering
Engineering
Feedback
Information Storage and Retrieval
Insertion
Lower bounds
Networks
Substitutes
Symbols
Systems Theory
Transmission
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A new problem of transmitting information over the adversarial insertion-deletion channel with feedback is introduced. Assume that the encoder transmits 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 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 , . 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 completed 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.
ISSN:0032-9460
1608-3253
DOI:10.1134/S0032946021030029