Expected complexity analysis of increasing radii algorithm by considering multiple radius schedules

Expected complexity analysis of increasing radii algorithm by considering multiple radius schedules

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IET Communications — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

In this study, the authors investigate the expected complexity of increasing radii algorithm (IRA) in an independent and identified distributed Rayleigh fading multiple-input–multiple-output channel with additive Gaussian noise and then present its upper bound result. IRA employs several radii to yield significant complexity reduction over sphere decoding, whereas performing a near-maximum-likelihood detection. In contrast to the previous expected complexity presented by Gowaikar and Hassibi (2007), where the radius schedule was hypothetically fixed for analytic convenience, a new analytical result is obtained by considering the usage of multiple radius schedules. The authors analysis reflects the effect of the random variation in the radius schedule and thus provides a more reliable complexity estimation. The numerical results support their arguments, and the analytical results show good agreement with the simulation results.


    1. 1)
      • 1. Hassibi, B., Vikalo, H.: ‘On the sphere decoding algorithm. Part I: The expected complexity’, IEEE Trans. Signal Process., 2005, 53, (8), pp. 28062818.
    2. 2)
      • 2. Chang, X.-W., Han, Q.: ‘Solving box-constrained integer least squares problems’, IEEE Trans. Wirel. Commun., 2008, 7, (1), pp. 277287.
    3. 3)
      • 3. Damen, M.O., Gamel, H.E., Caire, G.: ‘On maximum-likelihood detection and the search for the closest lattice point’, IEEE Trans. Inf. Theory, 2003, 49, (10), pp. 23892402.
    4. 4)
      • 4. Windpassinger, C., Lampe, L., Fischer, R., Hehn, T.: ‘A performance study of MIMO detectors’, IEEE Trans. Wirel. Commun., 2006, 5, (8), pp. 20042008.
    5. 5)
      • 5. Barbero, L.G., Thompson, J.S.: ‘Performance of the complex sphere decoder in spatially correlated MIMO channels’, IET Commun., 2007, 1, (1), pp. 122130.
    6. 6)
      • 6. Brunel, L.: ‘Multiuser detection techniques using maximum likelihood sphere decoding in multicarrier CDMA systems’, IEEE Trans. Wirel. Commun., 2004, 3, (3), pp. 949957.
    7. 7)
      • 7. Mow, W.: ‘Maximum likelihood sequence estimation from the lattice viewpoint’, IEEE Trans. Inf. Theory, 1994, 40, (5), pp. 15911600.
    8. 8)
      • 8. Ajtai, M.: ‘The shortest vector problem in L2 is NP-hard for randomized reductions’. Proc. 30th Annual ACM Symp. on Theory of Computing, Dallas, TX, USA, May 1998, pp. 1019.
    9. 9)
      • 9. Agrell, E., Eriksson, T., Vardy, A., Zeger, K.: ‘Closest point search in lattices’, IEEE Trans. Inf. Theory, 2002, 48, (8), pp. 22012214.
    10. 10)
      • 10. Gowaikar, R., Hassibi, B.: ‘Statistical pruning for near-maximum likelihood decoding’, IEEE Trans. Signal Process., 2007, 55, (6), pp. 26612675.
    11. 11)
      • 11. Ghaderipoor, A., Tellambura, C.: ‘A statistical pruning strategy for Schnorr-Euchner sphere decoding’, IEEE Commun. Lett., 2008, 12, (2), pp. 121123.
    12. 12)
      • 12. Liang, Y., Ma, S., Ng, T.-S.: ‘Low complexity near-maximum likelihood decoding for MIMO systems’. Proc. IEEE PIMRC, Tokyo, Japan, September 2009, pp. 24292433.
    13. 13)
      • 13. Seethaler, D., Bölcskei, H.: ‘Performance and complexity analysis of infinity-norm sphere-decoding’, IEEE Trans. Inf. Theory, 2010, 56, (3), pp. 10851105.

Related content

This is a required field
Please enter a valid email address