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 [math]\displaystyle{ p }[/math]) or does not receive anything without being notified that the bit was dropped (with probability [math]\displaystyle{ 1-p }[/math]). 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 [math]\displaystyle{ p }[/math] be the deletion probability, [math]\displaystyle{ 0 \lt p \lt 1 }[/math]. The iid binary deletion channel is defined as follows:
Given an input sequence of [math]\displaystyle{ n }[/math] bits [math]\displaystyle{ (X_i) }[/math] as input, each bit in [math]\displaystyle{ X_n }[/math] can be deleted with probability [math]\displaystyle{ p }[/math]. The deletion positions are unknown to the sender and the receiver. The output sequence [math]\displaystyle{ (Y_i) }[/math] is the sequence of the [math]\displaystyle{ (X_i) }[/math] 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 [math]\displaystyle{ p }[/math]) is unknown. It has a mathematical expression[citation needed]. Several upper and lower bounds are known.
References
- ↑ "A survey of results for deletion channels and related synchronization channels", Probability Surveys 6: 1–33, 2009, doi:10.1214/08-PS141.
- ↑ 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.
External links
 |  |
