A Class of Binary Signaling Alphabets

This paper is concerned with a class of signaling alphabets, called "group alphabets," for use on the symmetric binary channel. The class in question is sufficiently broad to include the error correcting codes of Hamming,1 the Reed-Muller codes,2 and all "systematic codes"/ On the other hand, because they constitute a rather small subclass of the class of all binary alphabets, group alphabets possess many important special features of practical interest. In particular, (1) all letters of the alphabets are treated alike under transmission; (2) the encoding scheme is particularly simple to instrument; (3) the decoder -- a maximum likelihood detector-- is the best possible theoretically and is relatively easy to instrument; and (4) in certain cases of practical interest the alphabets are the best possible theoretically. It has very recently been proved by Peter Elias4 that there exist group alphabets which signal at a rate arbitarily close to the capacity, C, of the symmetric binary channel with an arbitrarily small probability of error. Elias' demonstration is an existence proof in that it does not show explicitly how to construct a group alphabet signaling at a rate greater than C -- E with a probability of error less than 8 for arbitrary positive 8 and e. Unfortunately, in this respect and in many others, our understanding of group alphabets is still fragmentary. In Part I, group alphabets are defined along with some related con203