Limits to list decoding of insertions and deletions

Antonia Wachter-Zeh

doi:10.1109/ISIT.2017.8006869

Limits to list decoding of insertions and deletions

Antonia Wachter-Zeh

Associate Professorship of Coding and Cryptography

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

3 Scopus citations

Abstract

List decoding of insertions and deletions in the Levenshtein metric is considered. In this paper, a Johnson-like upper bound on the maximum list size when decoding in the Levenshtein metric is derived. This bound depends only on the length and minimum Levenshtein distance of the code, the length of the received word, and the alphabet size. It shows that polynomial-time list decoding beyond half the Levenshtein distance is possible for many parameters. For example, list decoding of two insertions/deletions with the well-known Varshamov-Tenengolts (VT) codes is feasible. Further, we also show a lower bound on list decoding VT codes and an efficient list decoding algorithm for two insertions/deletions with VT codes.

Original language	English
Title of host publication	2017 IEEE International Symposium on Information Theory, ISIT 2017
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1948-1952
Number of pages	5
ISBN (Electronic)	9781509040964
DOIs	https://doi.org/10.1109/ISIT.2017.8006869
State	Published - 9 Aug 2017
Event	2017 IEEE International Symposium on Information Theory, ISIT 2017 - Aachen, Germany Duration: 25 Jun 2017 → 30 Jun 2017

Publication series

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

Conference

Conference	2017 IEEE International Symposium on Information Theory, ISIT 2017
Country/Territory	Germany
City	Aachen
Period	25/06/17 → 30/06/17

Keywords

Deletions
Insertions
Levenshtein metric
List decoding
Varshamov-Tenengolts (VT) codes

Access to Document

10.1109/ISIT.2017.8006869

Cite this

@inproceedings{e1f4bdec09824e1088af54c7fe10e7f1,

title = "Limits to list decoding of insertions and deletions",

abstract = "List decoding of insertions and deletions in the Levenshtein metric is considered. In this paper, a Johnson-like upper bound on the maximum list size when decoding in the Levenshtein metric is derived. This bound depends only on the length and minimum Levenshtein distance of the code, the length of the received word, and the alphabet size. It shows that polynomial-time list decoding beyond half the Levenshtein distance is possible for many parameters. For example, list decoding of two insertions/deletions with the well-known Varshamov-Tenengolts (VT) codes is feasible. Further, we also show a lower bound on list decoding VT codes and an efficient list decoding algorithm for two insertions/deletions with VT codes.",

keywords = "Deletions, Insertions, Levenshtein metric, List decoding, Varshamov-Tenengolts (VT) codes",

author = "Antonia Wachter-Zeh",

note = "Publisher Copyright: {\textcopyright} 2017 IEEE.; 2017 IEEE International Symposium on Information Theory, ISIT 2017 ; Conference date: 25-06-2017 Through 30-06-2017",

year = "2017",

month = aug,

day = "9",

doi = "10.1109/ISIT.2017.8006869",

language = "English",

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

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

pages = "1948--1952",

booktitle = "2017 IEEE International Symposium on Information Theory, ISIT 2017",

}

Wachter-Zeh, A 2017, Limits to list decoding of insertions and deletions. in 2017 IEEE International Symposium on Information Theory, ISIT 2017., 8006869, IEEE International Symposium on Information Theory - Proceedings, Institute of Electrical and Electronics Engineers Inc., pp. 1948-1952, 2017 IEEE International Symposium on Information Theory, ISIT 2017, Aachen, Germany, 25/06/17. https://doi.org/10.1109/ISIT.2017.8006869

Limits to list decoding of insertions and deletions. / Wachter-Zeh, Antonia.
2017 IEEE International Symposium on Information Theory, ISIT 2017. Institute of Electrical and Electronics Engineers Inc., 2017. p. 1948-1952 8006869 (IEEE International Symposium on Information Theory - Proceedings).

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

TY - GEN

T1 - Limits to list decoding of insertions and deletions

AU - Wachter-Zeh, Antonia

PY - 2017/8/9

Y1 - 2017/8/9

N2 - List decoding of insertions and deletions in the Levenshtein metric is considered. In this paper, a Johnson-like upper bound on the maximum list size when decoding in the Levenshtein metric is derived. This bound depends only on the length and minimum Levenshtein distance of the code, the length of the received word, and the alphabet size. It shows that polynomial-time list decoding beyond half the Levenshtein distance is possible for many parameters. For example, list decoding of two insertions/deletions with the well-known Varshamov-Tenengolts (VT) codes is feasible. Further, we also show a lower bound on list decoding VT codes and an efficient list decoding algorithm for two insertions/deletions with VT codes.

AB - List decoding of insertions and deletions in the Levenshtein metric is considered. In this paper, a Johnson-like upper bound on the maximum list size when decoding in the Levenshtein metric is derived. This bound depends only on the length and minimum Levenshtein distance of the code, the length of the received word, and the alphabet size. It shows that polynomial-time list decoding beyond half the Levenshtein distance is possible for many parameters. For example, list decoding of two insertions/deletions with the well-known Varshamov-Tenengolts (VT) codes is feasible. Further, we also show a lower bound on list decoding VT codes and an efficient list decoding algorithm for two insertions/deletions with VT codes.

KW - Deletions

KW - Insertions

KW - Levenshtein metric

KW - List decoding

KW - Varshamov-Tenengolts (VT) codes

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

U2 - 10.1109/ISIT.2017.8006869

DO - 10.1109/ISIT.2017.8006869

M3 - Conference contribution

AN - SCOPUS:85034033016

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1948

EP - 1952

BT - 2017 IEEE International Symposium on Information Theory, ISIT 2017

PB - Institute of Electrical and Electronics Engineers Inc.

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

Y2 - 25 June 2017 through 30 June 2017

ER -

Limits to list decoding of insertions and deletions

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this