# Deletion channel

Jump to navigation Jump to search

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 ${\displaystyle p}$) or does not receive anything without being notified that the bit was dropped (with probability ${\displaystyle 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 ${\displaystyle p}$ be the deletion probability, ${\displaystyle 0. The iid binary deletion channel is defined as follows: given a input sequence of ${\displaystyle n}$ bits ${\displaystyle (X_{i})}$ as input, each bit in ${\displaystyle X_{n}}$ can be deleted with probability ${\displaystyle p}$. The deletion positions are unknown to the sender and the receiver. The output sequence ${\displaystyle (Y_{i})}$ is the sequence of the ${\displaystyle (X_{i})}$ which were not deleted, in the correct order and with no errors.

## Capacity

 What is the capacity of a deletion channel?

The capacity of the binary deletion channel (as a function of the deletion rate ${\displaystyle p}$) is unknown. Several upper and lower bounds are known.