A Limited Search Variant of the Tree-Search (1996)

A limited search variant of the fixed delay tree search detector is described for recovery of digital signals corrupted with intersymbol interference and additive noise. The limited search algorithm uses a variant of the equalizer decision device, a simple slicer, to reduce the number of paths that are considered by the tree search detector from MD+l to D + 1 paths, significantly reducing the complexity of the tree-search detector. Simulation results are provided that show the new detector suffers a nearly negligible loss in performance, compared to that of the full fixed delay tree search, due to the path reduction. I. Introduction In data transmission over time-dispersive channels, intersymbol interference (ISI) is often a major factor limiting performance of digital communication systems. Over the past few decades, many techniques have been developed for receivers for channels with ISI. These techniques notably include linear equalization, decision feedback equalization, and maximum likelihood sequence estimation. Both linear and decision feedback equalization are oriented toward simplicity and low complexity, sacrificing performance. On the other hand, the maximum likelihood sequence estimator (MLSE) (FORN72), and the less well known maximum a priori symbol-by-symbol estimator (A&F70, HCR821 seek optimum or near optimum performance, but at a cost of substantially increased computational and storage requirements. More recently, detection algorithms have been developed that approach the performance of these optimal techniques but at a much lower complexity. These techniques include the reduced state sequence estimator (RSSE) (DH&H89, E&Q88), and the fixed delay tree search (FDTS) algorithm (CLHSZ, M&C90, M&C94, PKT86, WKF'921. The RSSE is a simplification of the MLSE, which reduces complexity by limiting the dimensionality of the trellis. The FDTS is a simplification of the maximum a priori (MAP) symbol-by-symbol detector, using decision feedback to limit the complexity. (The use of the term FDTS in this document refers to the general techniques used in a variety of sources under various names, not the specific FDTSDF proposed by Moon (M&C94) for the magnetic recording channel.) Both types of reduced complexity techniques (RSSE and FDTS) accomplish the reduction in complexity by only considering a portion of channel IS1 in the enhanced decision algorithm, and using the low complexity linear or decision feedback equalization to handle the remaining portion of the ISI. In this paper, we present a new limited search algorithm which substantially reduces complexity of the FDTS when M- O-7803-3336-5/96 $5.00 O 1996 IEEE ary signaling is used. This algorithm uses low-complexity single dimensional detectors to reduce the FDTS tree with MDfl paths to one with only D + 1 paths. Performance is shown to be only slightly worse than that of the FDTS and virtually indistinguishable under high signal to noise ratio (SNR) conditions. 11. Model We assume a discrete FIR additive white Gaussian noise (AWGN) channel model. Such a model can be applied to a continuous time linear system with correlated noise by using the whitened matched filter developed by Fomey (FORN72). In the discrete model, we transmit a sequence of symbols {u~} chosen from an M-ary alphabet A = {-M + 1, -M + 3, ..., M - 3, M - 1 }. The passage of the input sequence {U,} through the channel results in the output sequ N yi = U,-k hk + W, = Si + W,