The coding of messages subject to chance errors
Jacob Wolfowitz · Illinois Journal of Mathematics · 1957
The transmission of messages Throughout this paper we assume that all "alphabets" involved contain exactly two symbols, say 0 and 1.What this means will be apparent in a moment.This assumption is made only in the interest of simplicity of ex- position, and the changes needed when this assumption is not fulfilled will be obvious.Suppose that a person has a vocabulary of S words (or messages), any or all of which he may want to transmit, in any frequency and in any order, over a "noisy channel".For example, S could be the number of words in the dictionary of a language, provided that it is forbidden to coin words not in the dictionary.What a "noisy channel" is will be described in a moment.Here we want to emphasize that we do not assume anything about the fre- quency with which particular words are transmitted, nor do we assume that the words to be transmitted are selected by any random process (let alone that the distribution function of the random process is known).Let the words be numbered in some fixed manner.Thus transmitting a word is equivalent to transmitting one of the integers 1, 2, S.We shall now explain wtiat is meant by a "noisy channel" of memory m.A sequence of (m W 1) elements, each zero or one, will be called an a-sequence.A function p, defined on the set of all a-sequences, and such that always 0 = 0 (the symbol