Hostname: page-component-745bb68f8f-d8cs5 Total loading time: 0 Render date: 2025-02-11T20:25:49.405Z 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)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 

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