Alphabetic Codes Revisited.

An alphabetic code for an ordered probability distribution

is a prefix code in which p sub k is assigned to the kth codeword of the coding tree in the left-to- right order. This class of codes is applied to binary test problems. We derive the characteristic inequality for alphabetic codes which is analogous to the Kraft Inequality for prefix codes. With this inequality, we are able to unify and enhance many previous results on alphabetic codes. We discover that when

is in ascending or descending order, the expected length of an optimal alphabetic code for

is the same as that of a Huffman code for the unordered distribution {p sub k}. We also prove two new lower bounds of the expected length of an optimal alphabetic code, and propose a simple method for constructing good alphabetic codes when optimality is not critical.