Shannon Theory
S.6.3
Lecture
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

## 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.

## Presenters

#### Amaael Antonini

University of California, Los Angeles

#### Hengjie Yang

University of California, Los Angeles

#### Richard D. Wesel

University of California, Los Angeles

Paper

## Session Chair

#### Masahito Hayashi

Nagoya University