Abstract

Block-codes with a very small number of codewords are investigated for
the two special binary memoryless channels, 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 cases of two, three, and four
codewords and an arbitrary blocklength. It is shown that for two
possible messages, on a BSC, the so-called flip codes of type
t
are optimal for any t, while on a ZC, the flip code of type 0
is optimal. For codes with three or four messages it is shown that the
so-called weak flip codes of some given type are optimal where
the type depends on the blocklength. For all cases an algorithm is
presented that constructs an optimal code for blocklength n
recursively from an optimal code of length n-1. For the ZC a
recursive optimal code design is conjectured in the case of five
possible messages.

The derivation of these optimal codes relies heavily on a new approach
of constructing and analyzing the code-matrix not row-wise
(codewords), but column-wise. Moreover, these results also
prove that the minimum Hamming distance might be the wrong design
criterion for optimal codes even for very symmetric channels like the
BSC.



-||-   _|_ _|_     /    __|__   Stefan M. Moser
[-]     --__|__   /__\    /__   Senior Scientist, ETH Zurich, Switzerland
_|_     -- --|-    _     /  /   Adjunct Professor, National Yang Ming Chiao Tung University, Taiwan
/ \     []  \|    |_|   / \/    Web: https://moser-isi.ethz.ch/


Last modified: Mon Nov 14 13:11:04 UTC+8 2011