License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.105
URN: urn:nbn:de:0030-drops-164466
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16446/
Go to the corresponding LIPIcs Volume Portal

Rubinstein, Ittai

Explicit and Efficient Construction of Nearly Optimal Rate Codes for the Binary Deletion Channel and the Poisson Repeat Channel

pdf-format:
LIPIcs-ICALP-2022-105.pdf (0.9 MB)

Abstract

Two of the most common models for channels with synchronisation errors are the Binary Deletion Channel with parameter p (BDC_p) - a channel where every bit of the codeword is deleted i.i.d with probability p, and the Poisson Repeat Channel with parameter λ (PRC_λ) - a channel where every bit of the codeword is repeated Poisson(λ) times.
Previous constructions based on synchronisation strings yielded codes with rates far lower than the capacities of these channels [Con and Shpilka, 2019; Guruswami and Li, 2018], and the only efficient construction to achieve capacity on the BDC at the time of writing this paper is based on the far more advanced methods of polar codes [Tal et al., 2021].
In this work, we present a new method for concatenating synchronisation codes and use it to construct simple and efficient encoding and decoding algorithms for both channels with nearly optimal rates.

BibTeX - Entry

@InProceedings{rubinstein:LIPIcs.ICALP.2022.105,
  author =	{Rubinstein, Ittai},
  title =	{{Explicit and Efficient Construction of Nearly Optimal Rate Codes for the Binary Deletion Channel and the Poisson Repeat Channel}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{105:1--105:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16446},
  URN =		{urn:nbn:de:0030-drops-164466},
  doi =		{10.4230/LIPIcs.ICALP.2022.105},
  annote =	{Keywords: Error Correcting Codes, Algorithmic Coding Theory, Binary Deletion Channel}
}

Keywords: Error Correcting Codes, Algorithmic Coding Theory, Binary Deletion Channel
Collection: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Issue Date: 2022
Date of publication: 28.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI