The List-Sequential (LISS) Algorithm and Its Application

For iterative detection/decoding (turbo) schemes, we modify sequential decoding, which contrary to a posteriori probability (APP) Bahl-Cocke-Jelinek-Raviv (BCJR) decoding, enjoys a complexity almost independent of the number of states. This novel list-sequential (LISS) decoder avoids most of the drawbacks of the classical sequential decoders, such as variable workload and erased frames when working within a turbo scheme. It uses a metric containing a priori and channel values, a metric length bias term for speeding up the tree search, a soft extension of paths without increasing the stack size, and soft weighting to obtain a soft output. We present several turbo applications using the LISS including equalization, single-antenna interference cancellation, multiuser and multiple-input multiple-output detection. It is shown that the LISS achieves the optimal (genie) or APP performance at a bit-error rate after the outer decoder of less than 10-4, but it also works with channels which have a high number of taps, constellation points, antennas, and states where the APP (BCJR) algorithm becomes infeasible