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.