Deletion channel

(Redirected from Deletion error)

A deletion channel is a communications channel model used in coding theory and information theory. In this model, a transmitter sends a bit (a zero or a one), and the receiver either receives the bit (with probability ) or does not receive anything without being notified that the bit was dropped (with probability ). Determining the capacity of the deletion channel is an open problem.[1][2]

The deletion channel should not be confused with the binary erasure channel which is much simpler to analyze.

Formal description

edit

Let   be the deletion probability,  . The iid binary deletion channel is defined as follows:

Given an input sequence of   bits   as input, each bit in   can be deleted with probability  . The deletion positions are unknown to the sender and the receiver. The output sequence   is the sequence of the   which were not deleted, in the correct order and with no errors.

Capacity

edit
Unsolved problem in computer science:
What is the capacity of a deletion channel?

The capacity of the binary deletion channel (as an analytical expression of the deletion rate  ) is unknown. It has a mathematical expression[citation needed]. Several upper and lower bounds are known.

References

edit
  1. ^ Mitzenmacher, Michael (2009), "A survey of results for deletion channels and related synchronization channels", Probability Surveys, 6: 1–33, doi:10.1214/08-PS141, MR 2525669.
  2. ^ Kanoria, Yashodhan; Montanari, Andrea (2013), "Optimal coding for the binary deletion channel with small deletion probability", IEEE Transactions on Information Theory, 59 (10): 6192–6219, doi:10.1109/TIT.2013.2262020, MR 3106824.
edit