2015/03/11 by Oron Sabag, Haim H. Permuter, Sabag, Oron +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #Cellular Automata and Applications #DNA and Biological Computing #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.1503.03359
openalex publication_date 2015/03/11 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
The input-constrained erasure channel with feedback is considered, where the binary input sequence contains no consecutive ones, i.e., it satisfies the (1,∞)-RLL constraint. We derive the capacity for this setting, which can be expressed as Cε=max0 ≤ p ≤ (1)/(2)\fracHb(p)p+(1)/(1-ε), where ε is the erasure probability and Hb(⋅) is the binary entropy function. Moreover, we prove that a-priori knowledge of the erasure at the encoder does not increase the feedback capacity. The feedback capacity was calculated using an equivalent dynamic programming (DP) formulation with an optimal average-reward that is equal to the capacity. Furthermore, we obtained an optimal encoding procedure from the solution of the DP, leading to a capacity-achieving, zero-error coding scheme for our setting. DP is thus shown to be a tool not only for solving optimization problems such as capacity calculation, but also for constructing optimal coding schemes. The derived capacity expression also serves as the only non-trivial upper bound known on the capacity of the input-constrained erasure channel without feedback, a problem that is still open.