Trellis-and-tree search algorithms for equalization and multiuser detection

This thesis deals with the detection of digital signals in the presence of inter-symbol interference (ISI) and/or multiple-access interference. We develop a new fractional maximum likelihood sequence estimation (MLSE) receiver which is suitable for wireless communication systems with excess signal bandwidth and fast time-varying channels. We investigate the effect of the receive filter and the branch metric on decision feedback sequence estimation (DFSE) and M-algorithm receivers, which are reduced-complexity alternatives to MLSE. The analysis leads to the classification of these receivers on the basis of the presence of untreated interference components, referred to as bias, which dominate the error-rate performance of the receiver. Bias arises in a DFSE or M-algorithm receiver due to a mismatch between the receive filter and the branch metric. We show that an unbiased receiver comprises a front-end filter matched to the overall channel or the transmit filter response followed by the appropriate noise-whitening or zero-forcing filter and a reduced trellis or tree search algorithm. Receivers with just a matched filter followed by a reduced trellis or tree search algorithm belong to the class of biased receivers.;We compare various trellis-based receivers on the basis of the distance of a given error sequence, which characterizes the probability of the associated error event. We show that whitening filter DFSE receivers maximize the error distance among unbiased DFSE receivers and truncated-memory MLSE receivers with pre-filtering. For matched filter DFSE receivers, we describe bias compensation methods employing hard as well as soft tentative decisions, which significantly enhance performance in most cases without adding much complexity. Union bounds on the error probability of the various receivers are derived and evaluated using a modified generating function approach.;We derive an optimum forward-recursive soft-output algorithm which operates on the standard matched filter statistics and has complexity that grows exponentially with the channel memory only. We also derive a reduced-state soft-output algorithm which provides good symbol reliability estimates with reduced complexity. The performance of the various algorithms is compared for equalization of ISI and multiuser detection for direct-sequence code-division multiple-access systems via simulation and analytical examples.