A Practical Coding Scheme for the BSC with Feedback

We provide a practical implementation of the rubber method of Ahlswede et al. for binary channels. The idea is to create the skeleton sequence therein via an arithmetic decoder designed for a particular k-th order Markov chain. For the stochastic binary symmetric channel, we show that the scheme is nearly optimal in a strong sense for certain parameters. A byproduct of the analysis is a strict enlargement of the rates for which the sphere-packing bound is known to be achievable with feedback for this channel.

Automated summary

In this paper, we present a practical implementation of the rubber method by Ahlswede et al. for binary channels, creating a skeleton sequence using an arithmetic decoder designed for a specific k-th order Markov chain. We demonstrate that the scheme is nearly optimal for certain parameters in the stochastic binary symmetric channel, and we also show a strict enlargement of achievable rates with feedback for this channel beyond the sphere-packing bound.