Shannon Theory
Finite-blocklength Analysis

Low Complexity Algorithms for Transmission of Short Blocks over the BSC with Full Feedback

Amaael Antonini, Hengjie Yang, Richard D. Wesel

Date & Time

01:00 am – 01:00 am


Building on the work of Horstein, Shayevitz and Feder, and Naghshvar \emph{et al.}, this paper presents algorithms for low-complexity sequential transmission of a $k$-bit message over the binary symmetric channel (BSC) with full, noiseless feedback. To lower complexity, this paper shows that the initial $k$ binary transmissions can be sent before any feedback is required and groups messages with equal posteriors to reduce the number of posterior updates from exponential in $k$ to linear in $k$. Simulation results demonstrate that achievable rates for this full, noiseless feedback system approach capacity rapidly as a function of average blocklength, faster than known finite-blocklength lower bounds on achievable rate with noiseless active feedback and significantly faster than finite-blocklength lower bounds for a stop feedback system.


Amaael Antonini

University of California, Los Angeles

Hengjie Yang

University of California, Los Angeles

Richard D. Wesel

University of California, Los Angeles

Session Chair

Masahito Hayashi

Nagoya University