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

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)3501-3510
Number of pages10
JournalIEEE Transactions on Information Theory
Volume68
Issue number6
DOIs
StatePublished - 1 Jun 2022

Keywords

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

Fingerprint

Dive into the research topics of 'Decoder Ties Do Not Affect the Error Exponent of the Memoryless Binary Symmetric Channel'. Together they form a unique fingerprint.

Cite this