The input-constrained erasure channel with feedback is considered, where the binary input sequence contains no consecutive ones, i.e., it satisfies the    $(1,\infty )$   -RLL constraint. We derive the capacity for this setting, which can be expressed as    $C_{\epsilon }=\max _{0\leq p\leq 0.5} \frac {(1-\epsilon )H_{b}(p)}{1+(1-\epsilon )p}$   , where    $\epsilon $    is the erasure probability and    $ H_{b}(\cdot )$    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.
['Oron Sabag', 'Haim H. Permuter', 'Navin Kashyap']
The Feedback Capacity of the Binary Erasure Channel With a No-Consecutive-Ones Input Constraint