A Stopping Radius for the Sphere Decoder: Complexity Reduction in Multiple-Symbol Differential Detection

Abstract:
With the aim of reducing its search complexity, we study a stopping radius for the sphere decoder (SD) algorithm. We compare two variants in setting this stopping radius. In particular, we consider a stopping radius, based on a lower bound on the packing radius, which preserves the optimality of the SD output, and a stopping radius which is based on the statistics of the underlying search problem. We adopt this SD with early termination to maximum-likelihood multiple-symbol differential detection (ML-MSDD) of differential phase-shift keying (DPSK), and compare the different stopping criteria in terms of achievable complexity reduction.