Feedback Capacity and Coding for Binary-Input Memoryless Channels with a No-Consecutive-Ones Input Constraint
Event details
| Date | 21.05.2019 |
| Hour | 15:15 › 16:15 |
| Speaker | Prof. Navin Kashyap - IIT Bangalore |
| Location | |
| Category | Conferences - Seminars |
We consider the input-constrained feedback capacity of certain binary-input
memoryless channels. Here, the channel inputs are constrained to be binary sequences in which consecutive 1s are disallowed, and the channel output at the end of one transmission is fed back to the transmitter ahead of the next transmission. It is known that the capacity computation for such channels can be formulated as an average-reward dynamic program (DP). In the case of the binary erasure channel, we obtain an exact expression for the capacity by explicitly solving the Bellman equation associated with the DP formulation. Furthermore, the optimal policy of the DP leads to a simple and elegant zero-error coding scheme that achieves capacity. More generally, for any binary-input, binary-output channel, we are able to obtain an explicit expression for feedback capacity under the no-consecutive-1s input constraint by solving a Bellman equation. In particular, our results apply to the binary symmetric channel and the Z channel. The optimal policy for the DP yields a capacity-achieving coding scheme based on the posterior matching principle. This is joint work with Oron Sabag and Haim Permuter (Ben-Gurion University, Israel).
memoryless channels. Here, the channel inputs are constrained to be binary sequences in which consecutive 1s are disallowed, and the channel output at the end of one transmission is fed back to the transmitter ahead of the next transmission. It is known that the capacity computation for such channels can be formulated as an average-reward dynamic program (DP). In the case of the binary erasure channel, we obtain an exact expression for the capacity by explicitly solving the Bellman equation associated with the DP formulation. Furthermore, the optimal policy of the DP leads to a simple and elegant zero-error coding scheme that achieves capacity. More generally, for any binary-input, binary-output channel, we are able to obtain an explicit expression for feedback capacity under the no-consecutive-1s input constraint by solving a Bellman equation. In particular, our results apply to the binary symmetric channel and the Z channel. The optimal policy for the DP yields a capacity-achieving coding scheme based on the posterior matching principle. This is joint work with Oron Sabag and Haim Permuter (Ben-Gurion University, Israel).
Practical information
- Informed public
- Free
Organizer
- IPG Seminar
Contact
- Prof. Kashyap is an invited Professor hosted by Rudiger Urbanke.