Sequential detection for sparse channels via a multiple tree algorithm

In this paper, we propose a tree-search based approach to detecting symbols transmitted over a sparse intersymbol interference channel. The proposed method uses a novel multiple-tree structure that exploits the channel sparsity to reduce computational complexity. By using parallel tree searches to perform data detection, the algorithm avoids the redundant likelihood computations introduced by inactive taps in the sparse channel impulse response. Simulation results show that, for moderate to high SNR, the multiple tree-search algorithm can reduce complexity by a factor of approximately 30 relative to the conventional Viterbi algorithm and by a factor of nearly 4 relative to multi-trellis methods.