Introduction

In this paper we address the problem of estimation of a sequence of digital communication symbols transmitted over random ISI channels. For a known FIR channel, it is well known that the Viterbi algorithm [1] solves the ML sequence estimation (MLSE) problem. Although the computationally efficiency of this algorithm has lead to its broad use, the Viterbi algorithm requires knowledge of the channel (e.g. its impulse response) [2]. Here we are concerned with solving the blind MLSE problem, when the channel is unknown and no training data is employed.

Sequence estimation over a channel with unknown coefficients can be formulated as either a joint sequence/channel estimation problem, a channel estimation problem (followed by MLSE), or a direct sequence estimation problem. For joint estimation of both the transmitted sequence and channel coefficients, optimum methods have been developed (e.g. [3]). In this paper we develop an algorithm which accounts for random channel parameters and we pursue MLSE by marginalizing over the channel coefficients in order to improve sequence estimation performance over joint sequence/channel estimators.

The Expectation Maximization (EM) method is an approach to development of iterative ML and Maximum a Posterior (MAP) estimation algorithms, which was introduced into the signal processing community by Dempster, et al. [4]. For digital communications, the EM approach has been applied to the channel estimation problem [5,6]. It has also been employed for MLSE with unknown nuisance channel, interference or receiver parameters. For example, Georghiades, et al. [7] use EM to account for unknown phase given unsynchronized reception. Zeger and Kobayashi [8] estimate GMSK modulated symbols in the presence of unknown multipath parameters. In these examples, either simple prior distributions on the nuisance parameters are assumed in order to develop algorithms, or a high SNR approximation is derived.

This paper presents a new approach using an EM derived algorithm for MLSE over channels having unknown FIR impulse coefficients. The ML formulation for optimal sequence estimation over random channels is generally intractable to solve directly. However, the EM algorithm is a technique which can effectively be used to solve such intractable ML problems. Specifically, by using EM to marginalize over the channel coefficient distribution, optimal estimates of the transmitted sequence are derived which can achieve lower bit-error-rates than methods which jointly estimate both the transmitted sequence and the channel coefficients, and methods based on first optimally estimating the channel coefficients.