New Lower Bounds on the Fraction of Correctable Errors under List Decoding in Combinatorial Binary Communication Channels
A.G. D'yachkov, D. Yu. Goshkoder · Problems of Information Transmission · 2021
The aim of the paper is to revive and develop results of an unpublished manuscript of A.G. D'yachkov. We consider a discrete memoryless channel (DMC) and prove a theorem on the exponential expurgation bound for list decoding with fixed list size $$L$$ . This result is an extension of the classical exponential error probability bound for optimal codes over a DMC to the list decoding model over a DMC. As applications of this result, we consider a memoryless binary symmetric channel (BSC) and a memoryless binary asymmetric channel (Z-channel). For the both channels, we derive a lower bound on the fraction of correctable errors for zero-rate transmission over the corresponding channels under list decoding with a fixed list size $$L$$ at the channel output. For the Z-channel, we obtain this bound for an arbitrary input alphabet distribution $$(1-w,w)$$ ; we also find the optimum value of the obtained bound and prove that the fraction of errors correctable by an optimal code tends to 1 as the list size $$L$$ tends to infinity.