SPC10-5: Computationally Efficient List Sphere Detectors with Reduced Storage Requirements

One method for approximating a-posteriori symbol probabilities is to marginalise over a reduced list of possible vectors. Several methods exist for obtaining suitable lists (e.g. the list sphere detector), but in many cases the list size required for an accurate approximation may still be large. This paper describes an implementation technique which removes the requirement for list storage, with minimal increase in complexity. The method updates the posterior probabilities in place, and works with any depth-first tree-search based detector. We then introduce a novel depth-first branch and bound algorithm, which is shown to be more computationally efficient than standard Fincke-Pohst enumeration. It is particularly effective in difficult channels, characterized by having channel matrices with small determinants.