In the list-of-L decoding of a block code the receiver of a noisy sequence lists L possible transmitted messages, and is in error only if the correct message is not on the list. Consideration is given to (n,e,L) codes, which correct all sets of e or fewer errors in a block of n bits under list-of-L decoding. New geometric relations between the number of errors corrected under list-of-1 decoding and the (larger) number corrected under list-of-L decoding of the same code lead to new lower bounds on the maximum rate of (n,e,L) codes. They show that a jammer who can change a fixed fraction p>

Shannon's zero-error channel capacities C/sub OF/, C/sub O/ with and without noiseless feedback are generalized to list decoding: the receiver lists L messages, erring if the correct one is not listed. The corresponding capacities C/sub OF/(L), C/sub O/(L) are nondecreasing in L. For an I-letter input alphabet, C/sub OF/(L) attains its maximum at L=I-1. A lower bound to C/sub O/(L) approaches that maximum as L increases.>

In the schemes presented the encoder maps each message into a codeword in a prefix-free codeword set. In interval encoding the codeword is indexed by the interval since the last previous occurrence of that message, and the codeword set must be countably infinite. In recency rank encoding the codeword is indexed by the number of distinct messages in that interval, and there must be no fewer codewords than messages. The decoder decodes each codeword on receipt. Users need not know message probabilities, but must agree on indexings, of the codeword set in an order of increasing length and of the message set in some arbitrary order. The average codeword length over a communications bout is never much larger than the value for an off-line scheme which maps thejth most frequent message in the bout into thejth shortest codeword in the given set, and is never too much larger than the value for off-line Huffman encoding of messages into the best codeword set for the bout message frequencies. Both schemes can do much better than Huffman coding when successive selections of each message type cluster much more than in the independent case.

In an interactive multi-user data-processing system, a user knows the probabilities of his messages and must encode them into a fixed system-wide variable-length codeword set. He needs to receive the answer to his last message before selecting the next, so his encoding is one-shot. To minimize average codeword length he encodes his messages in order of decreasing probability into codewords in order of increasing length. An algorithm is given which, for each of several measures of performance, finds the codeword set best by that measure for the worst user, and some of the minimax optimal codeword sets the algorithm has found. Some of the results hold for all user distributions: others require, e.g., that all users send exactly or at most m distinct messages, or that there is an integerksuch that no user has a message of probability greater thanl/k.

For a given finite set of messages and their assigned probabilities, Huffman's procedure gives a method of computing a length set (a set of codeword lengths) that is optimal in the sense that the average word length is minimized. Corresponding to a particular length set, however, there may be more than one code. LetL(n)consist of all length sets with largest termn, and, for any\ell \in L(n), let{\cal S}( \ell)be the smallest number of states in any finite-state acceptor which accepts a set of codewords with length set\ell. It is shown that, for alln > 1,n^{2}/(16 \log_{2} n) \leq max {\cal S}(\ell) \leq 0(n^{2}).\ell \in L(n)

Four costs of a retrieval algorithm are the number of bits needed to store a representation of a data base, the number of those bits which must be accessed to answer a retrieval question, the number of bits of state information required, and the logic complexity of the algorithm.Firm lower bounds are given to measures of the first three costs for simple binary retrieval problems.Systems are constructed which attain each bound separately.A system which finds the value of the kth bit in an N-bit string attains all bounds simultaneously.For two other more complex retrieval problems there are trading curves between storage and worst-case access, and between storage and average access.Lower and upper bounds to the trading curves are found.Minimal storage is a point of discontinuity on both curves, and for some complex problems large increases in storage are needed to approach minimal access.The cost of a complete updating algorithm is taken to be the number of bits it reads and/or writes in updating the representation of a data base.Lower bounds to measures of this cost are cited.Optimal minimal-storage systems also have minimal update cost.Optimal minimal-access systems with large storage cost also have large update cost, but a small increase in storage for such a system may reduce update cost dramatically.

Countable prefix codeword sets are constructed with the universal property that assigning messages in order of decreasing probability to codewords in order of increasing length gives an average code-word length, for any message set with positive entropy, less than a constant times the optimal average codeword length for that source. Some of the sets also have the asymptotically optimal property that the ratio of average codeword length to entropy approaches one uniformly as entropy increases. An application is the construction of a uniformly universal sequence of codes for countable memoryless sources, in which thenth code has a ratio of average codeword length to source rate bounded by a function ofnfor all sources with positive rate; the bound is less than two forn = 0and approaches one asnincreases.

In data processing, a transmitterTandreceiverRcommunicate via a random-access memorymthat they share with a setUof other users.Tselects a codewordcfrom a setCknown toRand storescin some of the cells ofm, not necessarily adjacent to one another.Udoes not change the valuesThas stored but fills in the values stored in the other cells ofm.Cis said to be distinguishable ifRcan always find which codewordTstored inmno matter whatUstores in the other cells and to be locally distinguishable ifRcan do so reading only the values written byTnot byU. Necessary and sufficient conditions for distinguishability and local distinguishability are given. Generalizations of the Kraft inequality to this setting follow and give lower bounds to the numbers of cells occupied by the members of a distinguishable set of codewords and to the numbers of cells inmthatRmust access to distinguish among them. Upper bounds to numbers of necessary accesses are also given.

We consider a set of static files or inventories, each consisting of the same number of entries, each entry a binary word of the same fixed length selected (with replacement) from the set of all binary sequences of that length, and the entries in each file sorted into lexical order. We also consider several retrieval questions of interest for each such file. One is to find the value of the j th entry, another to find the number of entries of value less than k . When a binary representation of such a file is stored in computer memory and an algorithm or machine which knows only the file parameters (i.e. number of entries, number of possible values per entry) accesses some of the stored bits to answer a retrieval question, the number of bits stored and the number of bits accessed per retrieval question are two cost measures for the storage and retrieval task which have been used by Minsky and Papert. Bits stored depends on the representation chosen: bits accessed also depends on the retrieval question asked and on the algorithm used. We give firm lower bounds to minimax measures of bits stored and bits accessed for each of four retrieval questions, and construct representations and algorithms for a bit-addressable machine which come within factors of two or three of attaining all four bounds at once for files of any size. All four factors approach one for large enough files.

A quantizerQdivides the range [0, 1] of a random variablexintoKquantizing intervals theith such interval having length\Delta x_i. We define the quantization error for a particular value ofx(unusually) as the length of the quantizing interval in whichxfinds itself, and measure quantizer performance (unusually) by therth mean value of the quantizing interval lengthsM_r (Q) = \overline{\Delta x^{r^{1/r}}}, averaging with respect to the distribution functionFof the random variablex.Q_1is defined to be an optimum quantizer ifM_r (Q_1) \leq M_r (Q)for allQ. The unusual definitions restrict the results to bounded random variables, but lead to general and precise results. We define a classQ^{\ast}of quasi-optimum quantizers;Q_2is inQ^{\ast}if the different intervals\Delta x_imake equal contributions to the meanrth power of the interval size so thatPr \{ \Delta x_i \} \Delta x_{i^{r}}is constant for alli. Theorems 1, 2, 3, and 4 prove thatQ_2 \in Q^{\ast}exists and is unique for givenF, K, andr: that1 \geq KM_r (Q_2) \geq KM_r (Q_1) \geq I_r, whereI_r = \{\int_0^{1} f (x)^p dx\}^ {1/q}, fis the density of the absolutely continuous part of the distribution functionFofx, p = 1/(1+ r), andq = r /(1 + r): thatlim KM_r (Q_2) = I_rasK \rightarrow \infty; and that ifKM_r (Q) = I_rfor finiteK, thenQ=Q^{\ast}.

This paper discusses networks (directed graphs) having one input node, one output node, and an arbitrary number of intermediate nodes, whose branches are noisy communications channels, in which the input to each channel appears at its output corrupted by additive Gaussian noise. Each branch is labeled by a non-negative real parameter which specified how noisy it is. A branch originating at a node has as input a linear combination of the outputs of the branches terminating at that node. The channel capacity of such a network is defined. Its value is bounded in terms of branch parameter values and procedures for computing values for general networks are described. Explicit solutions are given for the classD_{0}which includes series-parallel and simple bridge networks and all other networks havingrpaths,bbranches, andvnodes withr = b - \upsilon + 2, and for the classD_{1}of networks which is inductively defined to includeD_{0}and all networks obtained by replacing a branch of a network inD_{1}by a network inD_{1}. The general results are applied to the particular networks which arise from the decomposition of a simple feedback system into successive forward and reverse (feedback) channels. When the feedback channels are noiseless, the capacities of the forward channels are shown to add. Some explicit expressions and some bounds are given for the case of noisy feedback channels.

This note discusses the problem of maximizing the rate of flow from one terminal to another, through a network which consists of a number of branches, each of which has a limited capacity. The main result is a theorem: The maximum possible flow from left to right through a network is equal to the minimum value among all simple cut-sets. This theorem is applied to solve a more general problem, in which a number of input nodes and a number of output nodes are used.

Predictive coding is a procedure for transmitting messages which are sequences of magnitudes. In this coding method, the transmitter and the receiver store past message terms, and from them estimate the value of the next message term. The transmitter transmits, not the message term, but the difference between it and its predicted value. At the receiver this error term is added to the receiver prediction to reproduce the message term. This procedure is defined and messages, prediction, entropy, and ideal coding are discussed to provide a basis for Part II, which will give the mathematical criterion for the best predictor for use in the predictive coding of particular messages, will give examples of such messages, and will show that the error term which is transmitted in predictive coding may always be coded efficiently.

In Part I predictive coding was defined and messages, prediction, entropy, and ideal coding were discussed. In the present paper the criterion to be used for predictors for the purpose of predictive coding is defined: that predictor is optimum in the information theory (IT) sense which minimizes the entropy of the average error-term distribution. Ordered averages of distributions are defined and it is shown that if a predictor gives an ordered average error term distribution it will be a best IT predictor. Special classes of messages are considered for which a best IT predictor can easily be found, and some examples are given. The error terms which are transmitted in predictive coding are treated as if they were statistically independent. If this is indeed the case, or a good approximation, then it is still necessary to show that sequences of message terms which are statistically independent may always be coded efficiently, without impractically large memory requirements, in order to show that predictive coding may be practical and efficient in such cases. This is done in the final section of this paper.