Explicit and Efficient Construction of (nearly) Optimal Rate Codes for Binary Deletion Channel and the Poisson Repeat Channel
share
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 codes for these channels can be split into two main categories: inefficient constructions that prove the capacities of these channels are greater than 1-p/9, λ/9 respectively, and more recently, codes with efficient encoding and decoding algorithms that have lower rates 1-p/16, λ/17. In this work, we present a new method for concatenating synchronisation codes. This method can be used to transform lower bounds on the capacities of these channels into efficient constructions, at a negligible cost to the rate of the code. This yields a family of codes with quasi-linear encoding and decoding algorithms that achieve rates of 1-p/9, λ/9 respectively for these channels.
READ FULL TEXT