Deletion channel

From Wikipedia, the free encyclopedia
Jump to: navigation, 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 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[edit]

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[edit]

List of unsolved problems in computer science
What is the capacity of a deletion channel?

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

External links[edit]

References[edit]

  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 .