Capacity Results for the Noisy Shuffling Channel

Ilan Shomorony; Reinhard Heckel

doi:10.1109/ISIT.2019.8849789

Capacity Results for the Noisy Shuffling Channel

Ilan Shomorony, Reinhard Heckel

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

41 Scopus citations

Abstract

Motivated by DNA-based storage, we study the noisy shuffling channel, which can be seen as the concatenation of a standard noisy channel (such as the BSC) and a shuffling channel, which breaks the data block into small pieces and shuffles them. This channel models a DNA storage system, by capturing two of its key aspects: (1) the data is written onto many short DNA molecules that are stored in an unordered way and (2) the molecules are corrupted by noise at synthesis, sequencing, and during storage. For the BSC-shuffling channel we characterize the capacity exactly (for a large set of parameters), and show that a simple index-based coding scheme is optimal.

Original language	English
Title of host publication	2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	762-766
Number of pages	5
ISBN (Electronic)	9781538692912
DOIs	https://doi.org/10.1109/ISIT.2019.8849789
State	Published - Jul 2019
Externally published	Yes
Event	2019 IEEE International Symposium on Information Theory, ISIT 2019 - Paris, France Duration: 7 Jul 2019 → 12 Jul 2019

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
Volume	2019-July
ISSN (Print)	2157-8095

Conference

Conference	2019 IEEE International Symposium on Information Theory, ISIT 2019
Country/Territory	France
City	Paris
Period	7/07/19 → 12/07/19

Access to Document

10.1109/ISIT.2019.8849789

Cite this

Shomorony, I., & Heckel, R. (2019). Capacity Results for the Noisy Shuffling Channel. In 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings (pp. 762-766). Article 8849789 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2019-July). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2019.8849789

@inproceedings{f3107766a2814529930a45762620738d,

title = "Capacity Results for the Noisy Shuffling Channel",

abstract = "Motivated by DNA-based storage, we study the noisy shuffling channel, which can be seen as the concatenation of a standard noisy channel (such as the BSC) and a shuffling channel, which breaks the data block into small pieces and shuffles them. This channel models a DNA storage system, by capturing two of its key aspects: (1) the data is written onto many short DNA molecules that are stored in an unordered way and (2) the molecules are corrupted by noise at synthesis, sequencing, and during storage. For the BSC-shuffling channel we characterize the capacity exactly (for a large set of parameters), and show that a simple index-based coding scheme is optimal.",

author = "Ilan Shomorony and Reinhard Heckel",

note = "Publisher Copyright: {\textcopyright} 2019 IEEE.; 2019 IEEE International Symposium on Information Theory, ISIT 2019 ; Conference date: 07-07-2019 Through 12-07-2019",

year = "2019",

month = jul,

doi = "10.1109/ISIT.2019.8849789",

language = "English",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "762--766",

booktitle = "2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings",

}

Shomorony, I & Heckel, R 2019, Capacity Results for the Noisy Shuffling Channel. in 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings., 8849789, IEEE International Symposium on Information Theory - Proceedings, vol. 2019-July, Institute of Electrical and Electronics Engineers Inc., pp. 762-766, 2019 IEEE International Symposium on Information Theory, ISIT 2019, Paris, France, 7/07/19. https://doi.org/10.1109/ISIT.2019.8849789

Capacity Results for the Noisy Shuffling Channel. / Shomorony, Ilan; Heckel, Reinhard.
2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2019. p. 762-766 8849789 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2019-July).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Capacity Results for the Noisy Shuffling Channel

AU - Shomorony, Ilan

AU - Heckel, Reinhard

PY - 2019/7

Y1 - 2019/7

N2 - Motivated by DNA-based storage, we study the noisy shuffling channel, which can be seen as the concatenation of a standard noisy channel (such as the BSC) and a shuffling channel, which breaks the data block into small pieces and shuffles them. This channel models a DNA storage system, by capturing two of its key aspects: (1) the data is written onto many short DNA molecules that are stored in an unordered way and (2) the molecules are corrupted by noise at synthesis, sequencing, and during storage. For the BSC-shuffling channel we characterize the capacity exactly (for a large set of parameters), and show that a simple index-based coding scheme is optimal.

AB - Motivated by DNA-based storage, we study the noisy shuffling channel, which can be seen as the concatenation of a standard noisy channel (such as the BSC) and a shuffling channel, which breaks the data block into small pieces and shuffles them. This channel models a DNA storage system, by capturing two of its key aspects: (1) the data is written onto many short DNA molecules that are stored in an unordered way and (2) the molecules are corrupted by noise at synthesis, sequencing, and during storage. For the BSC-shuffling channel we characterize the capacity exactly (for a large set of parameters), and show that a simple index-based coding scheme is optimal.

UR - http://www.scopus.com/inward/record.url?scp=85073143940&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2019.8849789

DO - 10.1109/ISIT.2019.8849789

M3 - Conference contribution

AN - SCOPUS:85073143940

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 762

EP - 766

BT - 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2019 IEEE International Symposium on Information Theory, ISIT 2019

Y2 - 7 July 2019 through 12 July 2019

ER -

Capacity Results for the Noisy Shuffling Channel

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this