Torn-Paper Coding

Ilan Shomorony, Alireza Vahid

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the problem of communicating over a channel that randomly 'tears' the message block into small pieces of different sizes and shuffles them. For the binary torn-paper channel with block length n and pieces of length {\mathrm{ Geometric}}(p-{n}) , we characterize the capacity as C = e^{-\alpha } , where \alpha = \lim-{n\to \infty } p-{n} \log n. Our results show that the case of {\mathrm{ Geometric}}(p-{n})-length fragments and the case of deterministic length-(1/p-{n}) fragments are qualitatively different and, surprisingly, the capacity of the former is larger. Intuitively, this is due to the fact that, in the random fragments case, large fragments are sometimes observed, which boosts the capacity.

Original languageEnglish (US)
Pages (from-to)7904-7913
Number of pages10
JournalIEEE Transactions on Information Theory
Volume67
Issue number12
DOIs
StatePublished - Dec 1 2021

Keywords

  • data storage
  • DNA storage
  • Torn paper
  • unordered communication

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint

Dive into the research topics of 'Torn-Paper Coding'. Together they form a unique fingerprint.

Cite this