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, and the receiver either receives the bit or does not receive anything without being notified that the bit was dropped. Determining the capacity of the deletion channel is an open problem.
The deletion channel should not be confused with the binary erasure channel which is much simpler to analyze.

Formal description

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

The capacity of the binary deletion channel is unknown. It has a mathematical expression. Several upper and lower bounds are known.