On the complexity of sphere decoding in digital communications

By Joakim Jaldén, Björn E. Ottersten. IEEE Transactions on Signal Processing, 2005

754 citations recorded by the source corpus.

Sphere decoding has been suggested by a number of authors as an efficient algorithm to solve various detection problems in digital communications. In some cases, the algorithm is referred to as an algorithm of polynomial complexity without clearly specifying what assumptions are made about the problem structure. Another claim is that although worst-case complexity is exponential, the expected complexity of the algorithm is polynomial. Herein, we study the expected complexity where the problem size is defined to be the number of symbols jointly detected, and our main result is that the expected complexity is exponential for fixed signal-to-noise ratio (SNR), contrary to previous claims. The sphere radius, which is a parameter of the algorithm, must be chosen to ensure a nonvanishing probability of solving the detection problem. This causes the exponential complexity since the squared radius must grow linearly with problem size. The rate of linear increase is, however, dependent on the noise variance, and thus, the rate of the exponential function is strongly dependent on the SNR. Therefore sphere decoding can be efficient for some SNR and problems of moderate size, even though the number of operations required by the algorithm strictly speaking always grows as an exponential function of the problem size.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/84bce981b0bd0b7a0b5d6d0feb01fcee1cb5aaa7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Electrical and Electronic Engineering

Citations in the corpus

An introduction to convex optimization for communications and signal processing (2006, methodology): “This method, while enjoying a good practical complexity/performance tradeoff for small system size and high SNR, is known to have exponential average-case complexity for each fixed SNR value [27].”
Scaling Up MIMO: Opportunities and Challenges with Very Large Arrays (2012, background): “ stack decoder [42], where the nodes of the tree are expanded in the order of least Euclidean distance to the received signal. The average complexity of the sphere decoder is however exponential in K [4], and SD is thus not suitable in the large MIMO regime where K is large. The Fixed Complexity Sph”
Large-Scale MIMO Detection for 3GPP LTE: Algorithms and FPGA Implementations (2014, methodology): “…optimal data detection methods, such as maximum-likelihood (ML) detection [13]–[15] or soft-output sphere decoding (SD) [16]–[18], whose (average) computational complexity scales exponentially in the number of transmitted data streams [19], [20], would simply result in prohibitive complexity.”
Soft-output sphere decoding: algorithms and VLSI implementation (2008, methodology): “Contributions: In this paper, we describe a tunable MIMO detector based on the sphere decoder [3]–[8], with performance ranging from that of hard-output successive interference cancellation (SIC) [9] to that of max-log APP detection [10].”
MIMO over Satellite: A Review (2011, background): “Random opportunistic beamforming offers a way of handling both the beamforming and scheduling problems simultaneously with scalar only SNR feedback.”
A unified framework for tree search decoding: rediscovering the sequential decoder (2005, background): “The complexity of the state of the art sphere decoder, however, remains prohibitive for problems characterized by a large dimensionality [10].”
Complex Lattice Reduction Algorithm for Low-Complexity Full-Diversity MIMO Detection (2009, methodology): “However, these lattice-reduction-aided detectors are based on the traditional Lenstra–Lenstra–Lovász (LLL) reduction algorithm that was originally introduced for reducing real lattice bases, in spite of the fact that the channel matrices are inherently complex-valued.”
Fixing the Complexity of the Sphere Decoder for MIMO Detection (2008, background): “However, it still has an exponential lower bound in the complexity for high number of antennas and constellation orders [5].”
Fifty Years of MIMO Detection: The Road to Large-Scale MIMOs (2015, result): “Contrary to this claim, Jaldén and Ottersten [60],”
Quantized Precoding for Massive MU-MIMO (2016, background): “While SD reduces (often significantly) the average complexity compared to an exhaustive search, it was shown to exhibit exponential complexity in the number of variables for data detection in multi-antenna wireless systems [69], [70].”