Technical Program

Paper Detail

Paper IDS.6.3
Paper Title Low Complexity Algorithms for Transmission of Short Blocks over the BSC with Full Feedback
Authors Amaael Antonini, Hengjie Yang, Richard D. Wesel, University of California, Los Angeles, United States
Session S.6: Finite-blocklength Analysis
Presentation Lecture
Track Shannon Theory
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract 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.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!