TY - JOUR

T1 - Optimal ultrasmall block-codes for binary discrete memoryless channels

AU - Chen, Po-Ning

AU - Lin, Hsuan Yin

AU - Moser, Stefan M.

PY - 2013/11/4

Y1 - 2013/11/4

N2 - Optimal block-codes (in the sense of minimum average error probability, using maximum likelihood decoding) with a small number of codewords are investigated for the binary asymmetric channel (BAC), including the two special cases of the binary symmetric channel (BSC) and the Z-channel (ZC), both with arbitrary cross-over probabilities. For the ZC, the optimal code structure for an arbitrary finite blocklength is derived in the cases of two, three, and four codewords and conjectured in the case of five codewords. For the BSC, the optimal code structure for an arbitrary finite blocklength is derived in the cases of two and three codewords and conjectured in the case of four codewords. For a general BAC, the best codebooks under the assumption of a threshold decoder are derived for the case of two codewords. The derivation of these optimal codes relies on a new approach of constructing and analyzing the codebook matrix not rowwise (codewords), but columnwise. This new tool leads to an elegant definition of interesting code families that is recursive in the blocklength n and admits their exact analysis of error performance. This allows for a comparison of the average error probability between all possible codebooks.

AB - Optimal block-codes (in the sense of minimum average error probability, using maximum likelihood decoding) with a small number of codewords are investigated for the binary asymmetric channel (BAC), including the two special cases of the binary symmetric channel (BSC) and the Z-channel (ZC), both with arbitrary cross-over probabilities. For the ZC, the optimal code structure for an arbitrary finite blocklength is derived in the cases of two, three, and four codewords and conjectured in the case of five codewords. For the BSC, the optimal code structure for an arbitrary finite blocklength is derived in the cases of two and three codewords and conjectured in the case of four codewords. For a general BAC, the best codebooks under the assumption of a threshold decoder are derived for the case of two codewords. The derivation of these optimal codes relies on a new approach of constructing and analyzing the codebook matrix not rowwise (codewords), but columnwise. This new tool leads to an elegant definition of interesting code families that is recursive in the blocklength n and admits their exact analysis of error performance. This allows for a comparison of the average error probability between all possible codebooks.

KW - Binary asymmetric channel (BAC)

KW - Z-channel (ZC)

KW - binary symmetric channel (BSC)

KW - finite blocklength

KW - flip codes

KW - maximum likelihood (ML) decoder

KW - minimum average error probability

KW - optimal codes

KW - weak flip codes

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

U2 - 10.1109/TIT.2013.2276893

DO - 10.1109/TIT.2013.2276893

M3 - Article

AN - SCOPUS:84886694123

SN - 0018-9448

VL - 59

SP - 7346

EP - 7378

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 11

M1 - 6576303

ER -