Optimal block-codes 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). The optimal (in the sense of minimum average error probability,
using maximum likelihood decoding) code structure is derived for the
ZC and for the BSC in the cases of two, three, and four codewords and
an arbitrary finite blocklength. For a general BAC, it is shown that
so-called flip codes are optimal codes with two codewords. For the BSC
and the ZC, it is shown that so-called weak flip codes are optimal
codes with three or four codewords. The derivation of these optimal
codes relies heavily on a new approach of constructing and analyzing
the codebook matrix not row-wise (codewords), but column-wise. This
new tool allows an elegant definition of interesting code families
that is recursive in the blocklength n and admits their exact analysis
of error performance that is not based on the union bound or other


Binary asymmetric channel (BAC), binary symmetric channel (BSC),
channel capacity, 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: Mon May 28 16:23:49 UTC+8 2012