Deletion channel explained

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 an 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

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

Notes and References

1. .
2. .