University of Cambridge > Talks.cam > Optimization and Incentives Seminar > A Survey of Results for Deletion Channels and Related Synchronization Channels

  Browse A-Z

Log in

Googledetails Microsoftdetails

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

A Survey of Results for Deletion Channels and Related Synchronization Channels

Download to your calendar using vCal

If you have a question about this talk, please contact Neil Walton .

Joint With Probability Seminar Series.

At this point, it seems that most everything is known about the basic channels studied in information theory. For the i.i.d. (independent and identically distributed) binary erasure channel and the i.i.d. binary symmetric error channel, the capacity has long been known, and there are very efficient encoding and decoding schemes that are near capacity.

The situation is very different for the i.i.d. binary deletion channel. With this channel, the sender sends n bits, and each bit is deleted with some fixed probability p. So, for example, the sender might send 10110010, and the receiver obtains 1100. The i.i.d. binary deletion channel is perhaps the most basic channel that incorporates the challenge of synchronization. Surprisingly, even the capacity of the deletion channel remains unknown!

In this talk, I will survey what is known about the deletion channel, focusing on our recent work on bounds on the capacity. The main result is that the for any probability p, the deletion channel has capacity at least (1-p)/9. Hence, the capacity of the deletion channel is always within a constant factor of the erasure channel (which has capacity (1-p)). We also discuss the many remaining open problems in the area of synchronization channels.

No previous background is necessary.

This talk is part of the Optimization and Incentives Seminar series.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Leslie Stephen Room, Trinity Hall Faculty of Education, 184 Hills Road, Cambridge, CB2 8PQ, DMB, Room 2S4 On-line

Other talks

Title to be confirmed Cambridge RNA Club - ONLINE Morning Break Title to be confirmed External Seminar - Jenn Brophy TBC Royal Papworth Hospital and Acute Medicine
 

Š 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity