A Multistack Algorithm for Soft MIMO Demodulation

We propose a family of list-based soft demodulators for multiple-input–multiple-output (MIMO) communication systems based on a multistack algorithm for traversing the tree structure that is inherent in the MIMO demodulation problem. The existing stack algorithm for MIMO soft demodulation stores a single stack of visited nodes in the tree and expands the stack using the “best-first” principle. In the proposed multistack algorithm, the single stack is partitioned into a stack for each level of the tree, and the algorithm proceeds by performing one best-first search step in each of these stacks in the natural ordering of the tree. By assigning appropriate priorities to the level at which this “best-first search per level” processing restarts once a leaf node has been obtained, the proposed demodulators can achieve tradeoffs between performance and complexity that dominate those of several existing methods, including the stack algorithm, in the low-complexity region.