A parallel filtered-based EM algorithm for hidden Markov model and sinusoidal drift parameter estimation with systolic array implementation

In this paper we derive finite-dimensional discrete-time filters for estimating the parameters of discrete-time finite-state Markov chains imbedded in a mixture of Gaussian white noise and deterministic signals of known functional form with unknown parameters. The filters that we derive, estimate quantities used in the expectation-maximization (EM) algorithm for maximum likelihood (ML) estimation of the Markov chain parameters (transition probabilities and state levels) as well as the parameters of the deterministic interference. Specifically, we consider two important types of deterministic signals: Periodic, or almost periodic signals with unknown frequency components, amplitudes and phases; polynomial drift in the states of the Markov process with the coefficients of the polynomial unknown. The advantage of using filters in the EM algorithm is that they have negligible memory requirements, indeed independent of the number of observations. In comparison, implementing the EM algorithm using smoothed variables (forward-backward variables) requires memory proportional to the number of observations. In addition our filters are suitable for multiprocessor implementation whereas the forward-backward algorithm is not