Three classes of decisionmaking problems are distinguished, and notions of common information appropriate thereto are discussed for cases involving two or more decisionmakers.

The first moment of the decoding effort for stack sequential decoding is overbounded by a relatively simple technique. The resulting lower bound toR_{comp}is shown to be equivalent to the best known lower bound.

We derive sequences of upper and lower bounds that converge to the capacity of a binary channel in which a one takes twice as long to send as does a zero and may be received either as a one or as a pair of zeros. Such a fission mechanism can occur, for example, in the use of Morse code over a noisy channel. Next we present a sequential decoding algorithm for the channel which is particularly easy to implement. By means of the Perron-Frobenius theorem and an extension of Zigangirov's analysis of sequential decoding, we overbound error probability and thereby again underbound capacity. The resulting lower bound turns out to be within 0.014 nats of the fourteenth-order upper bound to capacity, uniformly in the fission probability. By extending an analytical method due in part to Jelinek, we overbound expected decoding computation and thereby lowerboundR_{comp}.

Tree codes are known to be capable of performing arbitrarily close to the rate-distortion function for any memoryless source and single-letter fidelity criterion. Tree coding and tree search strategies are investigated for the discrete-time memoryless Gaussian source encoded for a signal-power-to-mean-squared-error ratio of about 30 dB (about 5 binary digits per source output). Also, a theoretical lower bound on average search effort is derived. Two code search strategies (the Viterbi algorithm and the stack algorithm) were simulated in assembly language on a large digital computer. After suitable modifications, both strategies yielded encoding with a signal-to-distortion ratio about 1 dB below the limit set by the rate-distortion function. Although this performance is better than that of any previously known instrumentable scheme, it unfortunately requires search computation of the order ofl0^5machine cycles per source output encoded.