Maxentropic Markov chains (Corresp.)

The Markov chain that has maximum entropy for given first and second moments is determined. The solution provides a discrete analog to the continuous Gauss-Markov process.     

Reverse-time Markov processes (Corresp.)

The problem of representing a Markov process as a reverse-time Markov process is discussed. Diffusions and finite-state Markov processes are two important classes of Markov processes for which this problem has been considered. A gap in a paper of Castanon is pointed out which discusses diffusions; reverse-time finite and discrete-state Markov processes are then considered using martingale methods.     

Ternary graph theoretic error-correcting codes (Corresp.)

It is shown that directed graphs can be used to generate a class of moderately efficient error-correcting codes, which are easily decodable.     

Sequential decision feedback with a MAP strategy (Corresp.)

A computer simulation technique is used to evaluate the performance of the MAP strategy for sequential block orthogonal signaling over a Gaussian channel with noiseless and delayless feedback. The system performance is given in terms of the character error probability. The obtained results are compared with those derived using other suboptimum strategies previously proposed.     

An information - theoretic proof of Hadamard's inequality (Corresp.)

Hadamard's inequality follows immediately from inspection of both sides of the entropy inequalityh(X_{1}, X_{2},, cdots, X_{n})leq sum h(X_{i}), when(X_{l}, X_{2},cdots, X_{n})is multivariate normal.     

On critical distortion for Markov sources (Corresp.)

The authors underbound the critical distortion below which the rate-distortion function of a Markov chain equals its Shannon lower bound. The bound is tight in all cases in which the exact answer is currently known.     

A sufficient condition of nonergodicity of a Markov chain (Corresp.)

A natural and easily verifiable sufficient condition is given for the nonergodicity of a Markov chain. The result provides a converse to a theorem of Pakes and implies as special cases several recently published sufficient conditions for the instability of various forms of slotted ALOHA systems with Markovian retransmissions.     

Note on a partition for a decision feedback strategy (Corresp.)

A partition of the channel output space, which has the property that no other partition yields both a smaller probability of erasure and a smaller probability of error, is obtained and compared with a previous result due to Forney.     

Noiseless coding of binary finite-order Markov sources (Corresp.)

The performance of several simple noiseless coding schemes for binary finite-order Markov sources is considered. Bounds are derived on the maximum difference between the performance achievable by the schemes and the entropy of the sources. The schemes can be modified for the case where the source statistics are unknown.     

An algorithm for a selective nearest neighbor decision rule (Corresp.)

A procedure is introduced to approximate nearest neighbor (INN) decision boundaries. The algorithm produces a selective subset of the original data so that 1) the subset is consistent, 2) the distance between any sample and its nearest selective neighbor is less than the distance from the sample to any sample of the other class, and 3) the subset is the smallest possible.     

Bayesian decision procedure for interfering digital signals (Corresp.)

The Bayesian decision procedure is given to determine a finite sequence ofn m-ary(m geq 2)digits that have been transmitted through a channel that has memory and introduces additive noise. Minimum probability of digit estimation error is used as the criterion of goodness. Intersymbol interference at the receiver input is assumed to exist betweenLsuccessive digits. The parameternis chosen so thatn gg L. This procedure is compared with several suboptimal procedures that are used to combat intersymbol interference and additive noise.     

On the source matching approach for Markov sources (Corresp.)

The source matching approach is a universal noiseless source coding scheme used to approximate the solution of minimax coding. A numeric solution of the source matching approach is presented for the class of binary first-order Markov sources.     

Diffusion approximations for the analysis of digital phase locked loops (Corresp.)

Recent results for getting diffusion limits of a sequence of suitably scaled stochastic processes are applied to the synchronization problem for a digital phase locked loop (DPLL). For small filter gains and symbol intervals a diffusion (Gauss-Markov) process approximation is rigorously obtained. This approximation yields approximate error variances, passage time distributions, and correlation properties (among other properties) for the DPLL. The problem of tracking a drifting clock is also treated.     

A Markov chain analysis of the sequential decoding metric (Corresp.)

Using Massey's Markov chain model of the correct path metric, closed-form expressions are derived for the average separation between nonsearch nodes for the single path and the multiple path sequential decoder. An exact expression for the cumulative distribution of the correct path metric dips is also derived. All expressions are given in matrix form in terms of the correct path branch metric values and their probability assignments.     

Computing approximations for the generalized Q function and its complement (Corresp.)

The Chernoff bound is used to derive useful approximations for the generalizedQfunction and its complement.     

A note on the observation of a Markov source through a noisy channel (Corresp.)

A signal is sent by a two-state Markov source through a noisy channel. The objective is to develop a decoding scheme to obtain a reconstruction of the original signal. Necessary and sufficient conditions are presented, in both a sequential and a nonsequential context, for the optimality of several decoding schemes, including the singlet decoding rule and the data-independent decoding rule. A generalization of the simple noise process given by Drake [1] is presented, and analogous results are derived.     

Polynomial cost approximations in Markov decision theory based calladmission control

The problem of call admission control and routing in a multiservice circuit-switched loss network can be solved optimally under certain assumptions by the tools of Markov decision theory. However, in networks of practical size a number of simplifying approximations are needed to make the solution feasible. Assuming link independence, we propose a new method for approximating the state-dependent link costs accurately and relatively efficiently, even on links with extremely large state spaces. The proposed polynomial approximations are optimal in the sense of minimizing the residual in the continuous-time Howard equations of the Markov decision processes associated with the links. Numerical results are presented, and the proposed approximations are found superior to some earlier link-cost approximation methods     

Minimax universal noiseless coding for unifilar and Markov sources (Corresp.)

Constructive upper bounds are presented for minimax universal noiseless coding of unifilar sources without any ergodicity assumptionS. These bounds are obtained by quantizing the estimated probability distribution of source letters with respect to the relative entropy. They apply both to fixed-length to variable-length (FV) and variable-length to fixed-length (VF) codes. Unifilar sources are a generalization of the usual definition of Markov sources, so these results apply to Markov sources as well. These upper bounds agree asymptotically with the lower bounds given by Davisson for FV coding of stationary ergodic Markov sources.     

Some comments on conditionally Markov and reciprocal Gaussian processes (Corresp.)

Mehr and McFadden's conditionally Markov processes and Jamison's reciprocal processes are two independent extensions of Slepian's work on a particular stationary Gaussian process. The relationship between them and their relationship with Gauss-Markov processes are discussed.