2023/05/17 by Dar Arava, Arava, Dar, Ido Tal +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #DNA and Biological Computing #Error Correcting Code Techniques #Advanced biosensing and bioanalysis techniques
paper · pdf · doi:10.48550/arxiv.2305.10155
In this paper we show a polar coding scheme for the deletion channel with a probability of error that decays roughly like 2-√Λ, where Λ is the length of the codeword. That is, the same decay rate as that of seminal polar codes for memoryless channels. This is stronger than prior art in which the square root is replaced by a cube root. Our coding scheme is similar yet distinct from prior art. The main differences are: 1) Guard-bands are placed in almost all polarization levels; 2) Trellis decoding is applied to the whole received word, and not to segments of it. As before, the scheme is capacity-achieving. The price we pay for this improvement is a higher decoding complexity, which is nonetheless still polynomial, O(Λ4).