Deletion channel

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 $p$) or does not receive anything without being notified that the bit was dropped (with probability $1-p$). 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

Let $p$ be the deletion probability, $0 < p < 1$. The iid binary deletion channel is defined as follows: given a input sequence of $n$ bits $(X_i)$ as input, each bit in $X_n$ can be deleted with probability $p$. The deletion positions are unknown to the sender and the receiver. The output sequence $(Y_i)$ is the sequence of the $(X_i)$ which were not deleted, in the correct order and with no errors.

Capacity

Unsolved problem in computer science: What is the capacity of a deletion channel? (more unsolved problems in computer science)

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

External links

• Implementation of correction for deletion channel

References

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.