On the Complexity of Sphere Decoding for MSDD

We consider multiple-symbol differential detection (MSDD) for multiple-input multiple-output Rayleigh-fading channels. MSDD, which jointly processes blocks of N received symbols to detect N - 1 data symbols, allows for power-efficient transmission without requiring channel state information at the receiver. In previous work, we showed that computationally efficient sphere decoding algorithms can be used to accomplish MSDD. In this paper, we analyze the computational complexity of this sphere-decoding based MSDD. In particular, we prove by means of a lower bound that the complexity of the Fincke-Pohst multiple-symbol differential sphere decoder (FP-MSDSD), while being very low over wide ranges of N and signal-to-noise ratios, is exponential in N in principle. We further derive expressions for the exact complete of FP-MSDSD, which allow for quick assessment of ranges of useful window sizes N