Hostname: page-component-8448b6f56d-dnltx Total loading time: 0 Render date: 2024-04-18T08:56:13.012Z Has data issue: false hasContentIssue false
  • English
  • Français

A Binary Deletion Channel With a Fixed Number of Deletions

Published online by Cambridge University Press:  07 October 2014

BENJAMIN GRAHAM
BENJAMIN GRAHAM*
Affiliation:
Department of Statistics, University of Warwick, Coventry CV4 7AL, UK (e-mail: b.graham@warwick.ac.uk)
Get access Rights & Permissions [Opens in a new window]

Abstract

Suppose a binary string x = x1 . . . xn is being broadcast repeatedly over a faulty communication channel. Each time, the channel delivers a fixed number m of the digits (m < n) with the lost digits chosen uniformly at random and the order of the surviving digits preserved. How large does m have to be to reconstruct the message?

Keywords

Primary 68R05Secondary 68P30
Type
Problem Papers
Information
Combinatorics, Probability and Computing , Volume 24 , Issue 3 , May 2015 , pp. 486 - 489
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Drinea, E. and Mitzenmacher, M. (2007) Improved lower bounds for the capacity of i.i.d. deletion and duplication channels. IEEE Trans. Inform. Theory 53 2693–2714.CrossRefGoogle Scholar
[2]Holenstein, T., Mitzenmacher, M., Panigrahy, R. and Wieder, U. (2008) Trace reconstruction with constant deletion probability and related results. In Proc. 19th Annual ACM–SIAM Symposium on Discrete Algorithms: SODA'08, pp. 389–398.Google Scholar
[3]Mitzenmacher, M. (2009) A survey of results for deletion channels and related synchronization channels. Probab. Surv. 6 1–33.Google Scholar