IRUS Total

Coding against synchronisation and related errors

File Description SizeFormat 
LourencoRibeiro-JM-2021-PhD-Thesis.pdfThesis2.71 MBAdobe PDFView/Open
Title: Coding against synchronisation and related errors
Authors: Lourenço Ribeiro, João Miguel
Item Type: Thesis or dissertation
Abstract: In this thesis, we study aspects of coding against synchronisation errors, such as deletions and replications, and related errors. Synchronisation errors are a source of fundamental open problems in information theory, because they introduce correlations between output symbols even when input symbols are independently distributed. We focus on random errors, and consider two complementary problems: We study the optimal rate of reliable information transmission through channels with synchronisation and related errors (the channel capacity). Unlike simpler error models, the capacity of such channels is unknown. We first consider the geometric sticky channel, which replicates input bits according to a geometric distribution. Previously, bounds on its capacity were known only via numerical methods, which do not aid our conceptual understanding of this quantity. We derive sharp analytical capacity upper bounds which approach, and sometimes surpass, numerical bounds. This opens the door to a mathematical treatment of its capacity. We consider also the geometric deletion channel, combining deletions and geometric replications. We derive analytical capacity upper bounds, and notably prove that the capacity is bounded away from the maximum when the deletion probability is small, meaning that this channel behaves differently than related well-studied channels in this regime. Finally, we adapt techniques developed to handle synchronisation errors to derive improved upper bounds and structural results on the capacity of the discrete-time Poisson channel, a model of optical communication. Motivated by portable DNA-based storage and trace reconstruction, we introduce and study the coded trace reconstruction problem, where the goal is to design efficiently encodable high-rate codes whose codewords can be efficiently reconstructed from few reads corrupted by deletions. Remarkably, we design such n-bit codes with rate 1-O(1/log n) that require exponentially fewer reads than average-case trace reconstruction algorithms.
Content Version: Open Access
Issue Date: Feb-2021
Date Awarded: Jun-2021
URI: http://hdl.handle.net/10044/1/91403
DOI: https://doi.org/10.25560/91403
Copyright Statement: Creative Commons Attribution-Non Commercial 4.0 International Licence
Supervisor: Cheraghchi Bashi Astaneh, Mahdi
Department: Computing
Publisher: Imperial College London
Qualification Level: Doctoral
Qualification Name: Doctor of Philosophy (PhD)
Appears in Collections:Computing PhD theses

This item is licensed under a Creative Commons License Creative Commons