2021/11/30 by Hengjie Yang, Yang, Hengjie, Minghao Pan +5
Biochemistry, Genetics and Molecular Biology · Computer Science · #Cellular Automata and Applications #Cooperative Communication and Network Coding #DNA and Biological Computing #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2111.15042
openalex publication_date 2021/11/30 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28
In this paper, we consider the problem of variable-length coding over the class of memoryless binary asymmetric channels (BACs) with noiseless feedback, including the binary symmetric channel (BSC) as a special case. In 2012, Naghshvar et al. introduced an encoding scheme, which we refer to as the small-enough-difference (SED) encoder, which asymptotically achieves both capacity and Burnashev's optimal error exponent for symmetric binary-input channels. Building on the work of Naghshvar et al., this paper extends the SED encoding scheme to the class of BACs and develops a non-asymptotic upper bound on the average blocklength that is shown to achieve both capacity and the optimal error exponent. For the specific case of the BSC, we develop an additional non-asymptotic bound using a two-phase analysis that leverages both a submartingale synthesis and a Markov chain time of first passage analysis. For the BSC with capacity 1/2, both new achievability bounds exceed the achievability bound of Polyanskiy et al. for a system limited to stop-feedback codes.