The A* algorithm is applied to maximum-likelihood soft-decision decoding of binary linear block codes. This paper gives a tutorial on the A* algorithm, compares the decoding complexity with that of exhaustive search and Viterbi decoding algorithms, and presents performance curves obtained for several codes.

In this partially tutorial paper, we examine minimal trellis representations of linear block codes and analyze several measures of trellis complexity: maximum state and edge dimensions, total span length, and total vertices, edges and mergers. We obtain bounds on these complexities as extensions of well-known dimension/length profile (DLP) bounds. Codes meeting these bounds minimize all the complexity measures simultaneously; conversely, a code attaining the bound for total span length, vertices, or edges, must likewise attain it for all the others. We define a notion of "uniform" optimality that embraces different domains of optimization, such as different permutations of a code or different codes with the same parameters, and we give examples of uniformly optimal codes and permutations. We also give some conditions that identify certain cases when no code or permutation can meet the bounds. In addition to DLP-based bounds, we derive new inequalities relating one complexity measure to another, which can be used in conjunction with known bounds on one measure to imply bounds on the others. As an application, we infer new bounds on maximum state and edge complexity and on total vertices and edges from bounds on span lengths.

The idea of thermodynamic depth put forth by S. Lloyd and H. Pagels (1988) requires the computation of the entropy of Markov trajectories. Toward this end, the authors consider an irreducible finite state Markov chain with transition matrix P and associated entropy rate H(X)=- Sigma /sub i,j/ mu /sub i/P/sub ij/ log P/sub ij/ where mu is the stationary distribution given by the solution of mu = mu P. A trajectory T/sub ij/ of the Markov chain is a path with initial state i, final state j, and no intervening states equal to j. It is shown that the entropy H(T/sub ii/) of the random trajectory originating and terminating in state i is given by H(T/sub ii/)=H(X)/ mu /sub i/. Thus the entropy of the random trajectory T/sub ii/ is the product of the expected number of steps 1/ mu /sub i/ to return to state i and the entropy rate H(X) per step for the stationary Markov chain. A general closed form solution for the entropies H(T/sub ij/) is given by H=K-K+H/sub Delta /, where H is the matrix of trajectory entropies H/sub ij/=H(T/sub ij/); K=(I-P+A)/sup -1/ (H*-H/sub Delta /); K is a matrix in which the ijth element K/sub ij/ equals the diagonal element K/sub jj/ of K; A is the matrix of stationary probabilities with entries A/sub ij/= mu /sub j/; H* is the matrix of single-step entropies with entries H*/sub ij/=H(P/sub i/)=- Sigma /sub k/ P/sub ik/ log P/sub ik/; and H/sub Delta / is a diagonal matrix with entries (H/sub Delta /)/sub ii/=H(X)/ mu /sub i/.>

A Wald-like equation is proved for the entropy of a randomly stopped sequence of independent identically distributed discrete random variables X/sub 1/, X/sub 2/. . ., with a nonanticipating stopping time N. The authors first define a general stopping time and the associated stopped sequence, and then present the two main theorems for the entropy of a stopped sequence. The formal proofs of the lemmas necessary for the proof of the theorems are given. The randomness in the stopped sequence X/sup N/ is the expected number of calls for X times the entropy per call plus the residual randomness in the stopping time conditioned on the unstopped sequence X/sup infinity /.>