Technical Program

Paper Detail

 Paper ID S.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.