New Lower Bounds on the Fraction of Correctable Errors under List Decoding in Combinatorial Binary Communication Channels.
Saved in:
| 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 |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 154708532 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: New Lower Bounds on the Fraction of Correctable Errors under List Decoding in Combinatorial Binary Communication Channels. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22D'yachkov%2C+A%2E+G%2E%22">D'yachkov, A. G.</searchLink><relatesTo>1</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Goshkoder%2C+D%2E+Yu%2E%22">Goshkoder, D. Yu.</searchLink><relatesTo>1</relatesTo> (AUTHOR) – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Problems+of+Information+Transmission%22">Problems of Information Transmission</searchLink>. Oct2021, Vol. 57 Issue 4, p301-320. 20p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Error+probability%22">Error probability</searchLink><br /><searchLink fieldCode="DE" term="%22Infinity+%28Mathematics%29%22">Infinity (Mathematics)</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=154708532 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1134/S0032946021040013 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 20 StartPage: 301 Subjects: – SubjectFull: Error probability Type: general – SubjectFull: Infinity (Mathematics) Type: general Titles: – TitleFull: New Lower Bounds on the Fraction of Correctable Errors under List Decoding in Combinatorial Binary Communication Channels. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: D'yachkov, A. G. – PersonEntity: Name: NameFull: Goshkoder, D. Yu. IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 10 Text: Oct2021 Type: published Y: 2021 Identifiers: – Type: issn-print Value: 00329460 Numbering: – Type: volume Value: 57 – Type: issue Value: 4 Titles: – TitleFull: Problems of Information Transmission Type: main |
| ResultId | 1 |
