On the complexity of sphere decoding in digital communications

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.     

MIMO capacity of antenna arrays evaluated using radio channel measurements, reverberation chamber and radiation patterns

We compare different methods of evaluating arrays for multiple-input multiple-output (MIMO) systems through calculation of the MIMO capacity of a compact antenna array for mobile or WLAN applications at 1766 MHz and comparing it to a reference array of four mono- poles. Three different methods were used: evaluation using radiation patterns and a channel model, measurements in a reverberation chamber and simultaneous measurement of radio channel data using the two arrays. We conclude that all methods give very similar relative results and that the main difference in the two arrays is the 1.3 dB lower radiation efficiency of the compact array. The channel measurements also show that the arrays provide between 80% and 90% of the capacity of a 4 times 4 MIMO system.     

The Diversity Order of the Semidefinite Relaxation Detector

In this paper, we consider the detection of binary (antipodal) signals transmitted in a spatially multiplexed fashion over a fading multiple-input-multiple-output (MIMO) channel and where the detection is done by means of semidefinite relaxation (SDR). The SDR detector is an attractive alternative to maximum-likelihood (ML) detection since the complexity is polynomial rather than exponential. Assuming that the channel matrix is drawn with independent identically distributed (i.i.d.) real-valued Gaussian entries, we study the receiver diversity and prove that the SDR detector achieves the maximum possible diversity. Thus, the error probability of the receiver tends to zero at the same rate as the optimal ML receiver in the high signal-to-noise ratio (SNR) limit. This significantly strengthens previous performance guarantees available for the semidefinite relaxation detector. Additionally, it proves that full diversity detection is also possible in certain scenarios when using a noncombinatorial receiver structure.     

The Error Probability of the Fixed-Complexity Sphere Decoder

The fixed-complexity sphere decoder (FSD) has been previously proposed for multiple-input multiple-output (MIMO) detection in order to overcome the two main drawbacks of the sphere decoder (SD), namely its variable complexity and its sequential structure. Although the FSD has shown remarkable quasi-maximum-likelihood (ML) performance and has resulted in a highly optimized real-time implementation, no analytical study of its performance existed for an arbitrary MIMO system. Herein, the error probability of the FSD is analyzed, proving that it achieves the same diversity as the maximum-likelihood detector (MLD) independent of the constellation used. In addition, it can also asymptotically yield ML performance in the high-signal-to-noise ratio (SNR) regime. Those two results, together with its fixed complexity, make the FSD a very promising algorithm for uncoded MIMO detection.