Codes for Synchronization in Channels and Sources with Edits
Mahed Abrohsan, Ph.D.
Department of Applied Mathematics and Theoretical Physics, University of Cambridge
I will talk about coding for two models related to Edit channels. In the first model, there are two remote nodes (encoder and decoder), each having a binary sequence. The sequence $X$, available at the encoder, is the updated sequence and differs from $Y$ (available at the decoder) by a small number of edits. The goal is to construct a message $M$, to be sent via a one-way error-free link, such that the decoder can reconstruct $X$ using $M$ and $Y$. A coding scheme is devised for this one-way synchronization model. The scheme is based on multiple layers of VT codes combined with off-the-shelf linear error-correcting codes and uses a list decoder.
In the second model, motivated by DNA-based storage systems, we consider the problem of designing codes for the deletion channel when multiple observations (or traces) are available to the decoder. A simple binary and non-binary code is proposed that splits the codeword into blocks and employs a VT code in each block. The availability of multiple traces helps the decoder to identify deletion-free copies of a block, and to avoid mis-synchronization while decoding. The encoding complexity of the proposed scheme is linear in the codeword length; the decoding complexity is linear in the codeword length, and quadratic in the number of deletions and the number of traces. The list decoding technique for the proposed code is also considered.
Mahed Abrohsan is a Postdoctoral Researcher at the Department of Applied Mathematics and Theoretical Physics, University of Cambridge. He completed his PhD in July 2019 at the Engineering Department of University of Cambridge, where he worked on insertion/deletion channels and file synchronization problem. Before joining Cambridge, he got an MSc in Communication systems, a BSc in Mathematics, and a BSc in Electrical Engineering at 2015, 2014, and 2013 all from Sharif University, Tehran.