A Caltech Library Service

Variable-Length Coding for Binary-Input Channels With Limited Stop Feedback

Yang, Hengjie and Yavas, Recep Can and Kostina, Victoria and Wesel, Richard D. (2022) Variable-Length Coding for Binary-Input Channels With Limited Stop Feedback. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


This paper focuses on the numerical evaluation of the maximal achievable rate of variable-length stop-feedback (VLSF) codes with m decoding times at a given message size and error probability for binary-input additive white Gaussian noise channel, binary symmetric channel, and binary erasure channel (BEC). Leveraging the Edgeworth and Petrov expansions, we develop tight approximations to the tail probability of length-n cumulative information density that are accurate for any blocklength n. We reduce Yavas et al.'s non-asymptotic achievability bound on VLSF codes with m decoding times to an integer program of minimizing the upper bound on the average blocklength subject to the average error probability, minimum gap, and integer constraints. We develop two distinct methods to solve this program. Numerical evaluations show that Polyanskiy's achievability bound for VLSF codes, which assumes m = ∞, can be approached with a relatively small m in all of the three channels. For BEC, we consider systematic transmission followed by random linear fountain coding. This allows us to obtain a new achievability bound stronger than a previously known bound and new VLSF codes whose rate further outperforms Polyanskiy's bound.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Yang, Hengjie0000-0003-3356-3726
Yavas, Recep Can0000-0002-5640-515X
Kostina, Victoria0000-0002-2406-7440
Wesel, Richard D.0000-0002-9139-8098
Additional Information:This research is supported by National Science Foundation (NSF) grant CCF-1955660. An earlier version of this paper was accepted for presentation at the 2022 IEEE International Symposium on Information Theory [1].
Funding AgencyGrant Number
Subject Keywords:Limited stop feedback, non-asymptotic analysis, random linear fountain coding, sequential differential optimization, variable-length coding
Record Number:CaltechAUTHORS:20220804-201311712
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:116133
Deposited By: George Porter
Deposited On:11 Aug 2022 23:36
Last Modified:11 Aug 2022 23:36

Repository Staff Only: item control page