Decoder Ties Do Not Affect the Error Exponent of the Memoryless Binary Symmetric Channel

Ling Hua Chang; Po Ning Chen; Fady Alajaji; Yunghsiang S. Han

doi:10.1109/TIT.2022.3150597

Decoder Ties Do Not Affect the Error Exponent of the Memoryless Binary Symmetric Channel

Ling Hua Chang^*, Po Ning Chen, Fady Alajaji, Yunghsiang S. Han

^*Corresponding author for this work

Institute of Communications Engineering

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

The generalized Poor-Verdú error lower bound established by Chang et al. (2020) for multihypothesis testing is studied in the classical channel coding context. It is proved that for any sequence of block codes sent over the memoryless binary symmetric channel (BSC), the minimum probability of error (under maximum likelihood decoding) has a relative deviation from the generalized bound that grows at most linearly in blocklength. This result directly implies that for arbitrary codes used over the BSC, decoder ties can only affect the subexponential behavior of the minimum probability of error.

Original language	English
Pages (from-to)	3501-3510
Number of pages	10
Journal	IEEE Transactions on Information Theory
Volume	68
Issue number	6
DOIs	https://doi.org/10.1109/TIT.2022.3150597
State	Published - 1 Jun 2022

Keywords

Binary symmetric channel
block codes
channel reliability function
error exponent
error probability bounds
hypothesis testing
maximum likelihood decoder ties

Access to Document

10.1109/TIT.2022.3150597

Cite this

@article{336a05259c3146f59ff8d0249150ace9,

title = "Decoder Ties Do Not Affect the Error Exponent of the Memoryless Binary Symmetric Channel",

abstract = "The generalized Poor-Verd{\'u} error lower bound established by Chang et al. (2020) for multihypothesis testing is studied in the classical channel coding context. It is proved that for any sequence of block codes sent over the memoryless binary symmetric channel (BSC), the minimum probability of error (under maximum likelihood decoding) has a relative deviation from the generalized bound that grows at most linearly in blocklength. This result directly implies that for arbitrary codes used over the BSC, decoder ties can only affect the subexponential behavior of the minimum probability of error.",

keywords = "Binary symmetric channel, block codes, channel reliability function, error exponent, error probability bounds, hypothesis testing, maximum likelihood decoder ties",

author = "Chang, {Ling Hua} and Chen, {Po Ning} and Fady Alajaji and Han, {Yunghsiang S.}",

note = "Publisher Copyright: {\textcopyright} 1963-2012 IEEE.",

year = "2022",

month = jun,

day = "1",

doi = "10.1109/TIT.2022.3150597",

language = "English",

volume = "68",

pages = "3501--3510",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "6",

}

TY - JOUR

T1 - Decoder Ties Do Not Affect the Error Exponent of the Memoryless Binary Symmetric Channel

AU - Chang, Ling Hua

AU - Chen, Po Ning

AU - Alajaji, Fady

AU - Han, Yunghsiang S.

PY - 2022/6/1

Y1 - 2022/6/1

N2 - The generalized Poor-Verdú error lower bound established by Chang et al. (2020) for multihypothesis testing is studied in the classical channel coding context. It is proved that for any sequence of block codes sent over the memoryless binary symmetric channel (BSC), the minimum probability of error (under maximum likelihood decoding) has a relative deviation from the generalized bound that grows at most linearly in blocklength. This result directly implies that for arbitrary codes used over the BSC, decoder ties can only affect the subexponential behavior of the minimum probability of error.

AB - The generalized Poor-Verdú error lower bound established by Chang et al. (2020) for multihypothesis testing is studied in the classical channel coding context. It is proved that for any sequence of block codes sent over the memoryless binary symmetric channel (BSC), the minimum probability of error (under maximum likelihood decoding) has a relative deviation from the generalized bound that grows at most linearly in blocklength. This result directly implies that for arbitrary codes used over the BSC, decoder ties can only affect the subexponential behavior of the minimum probability of error.

KW - Binary symmetric channel

KW - block codes

KW - channel reliability function

KW - error exponent

KW - error probability bounds

KW - hypothesis testing

KW - maximum likelihood decoder ties

UR - http://www.scopus.com/inward/record.url?scp=85124752192&partnerID=8YFLogxK

U2 - 10.1109/TIT.2022.3150597

DO - 10.1109/TIT.2022.3150597

M3 - Article

AN - SCOPUS:85124752192

SN - 0018-9448

VL - 68

SP - 3501

EP - 3510

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 6

ER -

Decoder Ties Do Not Affect the Error Exponent of the Memoryless Binary Symmetric Channel

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this