Oron Sabag – Input constained channels with feedback


Event Details

  • Date:

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. The capacity for this setting is derived using dynamic programming (DP) methods. It is also proved that a-priori knowledge of the erasure at the encoder does not increase the feedback capacity. Furthermore, an optimal encoding procedure is obtained from the DP solution, 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.

We then proceed and consider the family of Binary-Input Binary-Output (BIBO) channels, where inputs should admit the (1,\infty)-RLL constraint as well. The capacity of this setting is derived by the explicit solution of the Bellman equation in the corresponding DP problem. A byproduct of this solution is the characterization of the feedback-dependent optimal inputs distribution. Among the special cases of the BIBO channel are the binary symmetric channel (BSC), the S-channel and the Z-channel, and thus, their feedback capacity is also obtained. For the input-constrained BSC, an asymptotic formula of feedback capacity is derived in the high SNR regime, i.e., when transition probability tends to zero. This formula together with a known result on input-constrained channels without feedback shows that feedback increases capacity in the high SNR regime, which contradicts a conjecture proposed by Shannon.