The expectation-maximization Viterbi algorithm for blind channel identification and equalization

A broadly applicable algorithm for blind maximum-likelihood (ML) equalization and detection of signals transmitted over dispersive and noisy channels is presented. Since the approach employs the Viterbi algorithm (VA) to execute the expectation step of the expectation-maximization (EM) iteration, we call it the expectation-maximization Viterbi algorithm (EMVA). The EMVA is a computationally efficient technique for simultaneous ML channel identification and signal detection whenever the transmission system admits a finite-state hidden Markov model (HMM) description. Applications of the EMVA to both static and fading channels are considered. For static channels, the HMM is described by a deterministic finite-state machine (FSM), while for fading channels it is associated with a stochastic FSM. In either case, the FSM is represented by a deterministic trellis to which the VA is applicable. Extensive simulation results are presented which show that the bit-error rate achieved by the EMVA is close to the ML error-rate performance based on true channel parameters.; The broad applicability of the algorithm is illustrated by considering a wide range of applications. Specifically, we apply the EMVA to blind equalization of frequency selective fading channels, nonlinear continuous-phase modulated signals, fractionally-spaced sampled signals, dually-polarized channels, and code-division multiple-access (CDMA) transmissions.; The convergence properties of the EMVA are investigated. In particular, we obtain a closed-form expression for the convergence-rate matrix evaluated at any stationary point of the observed-data likelihood function. The rate matrix is useful in estimating the error covariance matrix for the parameter estimate. Analysis reveals that the EMVA can be interpreted as a special quasi-Newton or gradient ascent algorithm that naturally encompasses a scale-rotation matrix which guarantees convergence to a local maximum. This property ensures the existence of a capture set for every local maximum. If the initial iterate falls within such a set, then the algorithm converges to the local or global maximum associated with the set. The existence of a capture set for the global maximum leads to the development of a blind channel acquisition technique which achieves global convergence with a probability approaching 100% for general classes of channels.