View in EDS

New Lower Bounds on the Fraction of Correctable Errors under List Decoding in Combinatorial Binary Communication Channels.

Saved in:
Bibliographic Details
Title: New Lower Bounds on the Fraction of Correctable Errors under List Decoding in Combinatorial Binary Communication Channels.
Authors: D'yachkov, A. G.1 (AUTHOR), Goshkoder, D. Yu.1 (AUTHOR)
Source: Problems of Information Transmission. Oct2021, Vol. 57 Issue 4, p301-320. 20p.
Subjects: Error probability, Infinity (Mathematics)
Abstract: 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 . 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 at the channel output. For the Z-channel, we obtain this bound for an arbitrary input alphabet distribution ; 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 tends to infinity. [ABSTRACT FROM AUTHOR]
Copyright of Problems of Information Transmission is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract: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 . 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 at the channel output. For the Z-channel, we obtain this bound for an arbitrary input alphabet distribution ; 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 tends to infinity. [ABSTRACT FROM AUTHOR]
ISSN:00329460
DOI:10.1134/S0032946021040013