





















This work gives an explicit construction of a family of error correcting codes for the binary deletion channel and for the Poisson repeat channel. In the binary deletion channel with parameter $p$ (BDC$_p$) every bit is deleted independently with probability $p$. A lower bound of $(1-p)/9$ is known on the capacity of the BDC$_p$ \cite{mitzenmacher2006simple}, yet no explicit construction is known to achieve this rate. We give an explicit family of codes of rate $(1-p)/16$, for every $p$. This improves upon the work of Guruswami and Li \cite{guruswami2017efficiently} that gave a construction of rate $(1-p)/120$. The codes in our family have polynomial time encoding and decoding algorithms. Another channel considered in this work is the Poisson repeat channel with parameter $λ$ (PRC$_λ$) in which every bit is replaced with a discrete Poisson number of copies of that bit, where the number of copies has mean $λ$. We show that our construction works for this channel as well. As far as we know, this is the first explicit construction of an error correcting code for PRC$_λ$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。