On Decoder Ties for the Binary Symmetric Channel with Arbitrarily Distributed Input

Ling-Hua Chang; Po-Ning Chen; Fady Alajaji

doi:10.3390/e25040668

On Decoder Ties for the Binary Symmetric Channel with Arbitrarily Distributed Input

Entropy (Basel). 2023 Apr 16;25(4):668. doi: 10.3390/e25040668.

Authors

Ling-Hua Chang¹, Po-Ning Chen², Fady Alajaji³

Affiliations

¹ Department of Electrical Engineering, Yuan Ze University, Taoyuan 32003, Taiwan.
² Institute of Communications Engineering, National Yang-Ming Chiao-Tung University, Taipei 112304, Taiwan.
³ Department of Mathematics and Statistics, Queen's University, Kingston, ON K7L 3N6, Canada.

Abstract

The error probability of block codes sent under a non-uniform input distribution over the memoryless binary symmetric channel (BSC) and decoded via the maximum a posteriori (MAP) decoding rule is investigated. It is proved that the ratio of the probability of MAP decoder ties to the probability of error grows most linearly in blocklength when no MAP decoding ties occur, thus showing that decoder ties do not affect the code's error exponent. This result generalizes a similar recent result shown for the case of block codes transmitted over the BSC under a uniform input distribution.

Keywords: binary symmetric channel; block codes; decoder ties; error exponent; error probability; joint source-channel coding; maximum a posteriori (MAP) decoding; non-uniformly distributed channel inputs.

Grants and funding

The work of Ling-Hua Chang is supported by the Ministry of Science and Technology, Taiwan under Grant MOST 109-2221-E-155-035-MY3. The work of Po-Ning Chen is supported by the Ministry of Science and Technology, Taiwan, under Grant MOST 110-2221-E-A49-024-MY3. The work of Fady Alajaji is supported by the Natural Sciences and Engineering Research Council (NSERC) of Canada.