Variable-Length Feedback Codes Over Known and Unknown Channels with Non-Vanishing Error Probabilities

We study variable-length feedback (VLF) codes with noiseless feedback for discrete memoryless channels. We present a novel non-asymptotic bound, which analyzes the average error probability and average decoding time of our modified Yamamoto-Itoh scheme. We then optimize the parameters of our code in the asymptotic regime where the average error probability <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\epsilon$</tex> remains a constant as the average decoding time <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N$</tex> approaches infinity. Our second-order achievability bound refines Polyanskiy et al.'s (2011) achievability bound. We also universal-ize our code by employing the empirical mutual information in our decoding metric and derive a second-order achievability bound for universal VLF codes. The proof of our result for universal VLF codes uses a refined version of the method of types and an asymptotic expansion from the nonlinear renewal theory literature.