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.