On the complexity of sphere decoding for differential detection

TitleOn the complexity of sphere decoding for differential detection
Publication TypeJournal Article
Year of Publication2007
AuthorsPauli, V., and L. Lampe
JournalIEEE Transactions on Information Theory

Multiple-symbol differential detection (MSDD) for multiple-input-multiple-output Rayleigh-fading channels is considered. 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, the authors showed that computational efficient sphere decoding algorithms can be used to accomplish MSDD. In this correspondence, the computational complexity of this sphere-decoding based MSDD is analyzed. In particular, it is proven 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. Furthermore, both exact and simple approximate expressions for the complexity of FP-MSDSD are derived, which allow for quick assessment of ranges of useful window sizes N of FP-MSDSD and show that the exponential rate of growth of the complexity of FP-MSDSD is asymptotically equal to that of brute-force MSDD.


a place of mind, The University of British Columbia

Electrical and Computer Engineering
2332 Main Mall
Vancouver, BC Canada V6T 1Z4
Tel +1.604.822.2872
Fax +1.604.822.5949

Emergency Procedures | Accessibility | Contact UBC | © Copyright 2021 The University of British Columbia