Abstract

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 row-wise
(codewords), but column-wise. 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.


Keywords

Binary asymmetric channel (BAC), binary symmetric channel (BSC),
finite blocklength, flip codes, maximum likelihood (ML) decoder,
minimum average error probability, optimal codes, weak flip codes,
Z-channel.



-||-   _|_ _|_     /    __|__   Stefan M. Moser
[-]     --__|__   /__\    /__   Senior Researcher & Lecturer, ETH Zurich, Switzerland
_|_     -- --|-    _     /  /   Adj. Professor, National Chiao Tung University (NCTU), Taiwan
/ \     []  \|    |_|   / \/    Web: http://moser-isi.ethz.ch/


Last modified: Thu Sep 5 10:18:56 UTC+8 2013