Source-linked AI summary
Generalised Sphere Decoding for Spatial Modulation
Abdelhamid Younis, Sinan Sinanović, Marco Di Renzo, Raed Mesleh, Harald Haas
TL;DR
The paper addresses the high complexity of ML detection for spatial modulation by designing two sphere decoders tailored to SM’s single-active-antenna structure. It analyzes their BER and computational complexity, showing that suitable radius selection preserves ML-level BER while reducing complexity, with the preferred decoder depending on spectral efficiency and setup.
Problem
ML detection and conventional sphere decoding remain computationally demanding for large-scale MIMO, motivating lower-complexity detection that exploits SM’s single-active-antenna structure.
Method
The paper proposes receiver-centric SM-Rx and transmit-centric SM-Tx sphere decoders, analyzes their BER and complexity, and derives a closed-form BER expression with an initial-radius selection method.
Results
SM-SD retains the same BER as ML while substantially reducing computational complexity; SM-Rx is generally preferred at lower spectral efficiencies and SM-Tx at higher ones.
Takeaways & Limitations
The best SM sphere decoder depends on the MIMO setup, receiver SNR, and target spectral efficiency rather than one decoder dominating universally.
Takeaways & Limitations
The analysis assumes R2.
Abstract
from arXiv · showhide
In this paper, Sphere Decoding (SD) algorithms for Spatial Modulation (SM) are developed to reduce the computational complexity of Maximum-Likelihood (ML) detectors. Two SDs specifically designed for SM are proposed and analysed in terms of Bit Error Ratio (BER) and computational complexity. Using Monte Carlo simulations and mathematical analysis, it is shown that by carefully choosing the initial radius the proposed sphere decoder algorithms offer the same BER as ML detection, with a significant reduction in the computational complexity. A tight closed form expression for the BER performance of SM-SD is derived in the paper, along with an algorithm for choosing the initial radius which provides near to optimum performance. Also, it is shown that none of the proposed SDs are always superior to the others, but the best SD to use depends on the target spectral efficiency. The computational complexity trade-off offered by the proposed solutions is studied via analysis and simulation, and is shown to validate our findings. Finally, the performance of SM-SDs are compared to Spatial Multiplexing (SMX) applying ML decoder and applying SD. It is shown that for the same spectral efficiency, SM-SD offers up to 84% reduction in complexity compared to SMX-SD, with up to 1 dB better BER performance than SMX-ML decoder.
I. INTRODUCTION
SM addresses the complexity, hardware, and energy costs of large-scale MIMO by activating one antenna at a time and using its spatial index for data transmission. The paper develops two SM-specific sphere decoders and analyzes their BER and complexity trade-offs.
- Motivation: SMX spectral efficiency increases linearly with transmit antennas but incurs increasing computational and hardware complexity in large-scale MIMO.SMX-ML searches all antenna-symbol combinations and must resolve inter-channel interference from simultaneous transmission.
- Spatial Modulation: SM activates one antenna per time instance and encodes data through both the transmitted constellation symbol and active-antenna index.This avoids inter-channel interference and increases spectral efficiency by log2 of the number of transmit antennas.
- Spatial Modulation: A single active antenna gives SM one RF chain, lower energy consumption, and SM-ML complexity independent of the number of transmit antennas.The resulting detection complexity depends on spectral efficiency and receive-antenna count, like SIMO detection.
- Proposed Sphere Decoders: The proposed SM-Rx decoder reduces the receive search space, while SM-Tx reduces the transmit search space by restricting examined spatial and constellation points.SM-Rx is especially suited to many receive antennas, whereas SM-Tx is designed around points inside a sphere.
- Radius Selection: The initial radius controls the BER-complexity trade-off: larger radii increase search complexity, while smaller radii can exclude the solution.The paper therefore studies radius selection alongside detector performance and complexity.
- Comparative Findings: SM-Rx is less complex at lower spectral efficiencies, whereas SM-Tx is preferred at higher spectral efficiencies.The paper reports no universally superior decoder and compares both against SM-ML and SMX detectors.
A. SM Modulator
The SM modulator divides each input block into antenna-selection and constellation-symbol bits, transmitting one symbol from one active antenna. This structure yields lower antenna-related complexity and RF-chain requirements than SMX.
- Bit Mapping: Each SM input block contains m = log2(Nt) + log2(M) bits, where Nt is the antenna count and M is the constellation size.The first term selects the active antenna and the second selects the transmitted constellation symbol.
- Bit Mapping: Only one transmit antenna is active at each time instance, while all other transmit antennas remain silent.The active antenna is selected by the first log2(Nt) input bits.
- Bit Mapping: The selected antenna transmits one QAM constellation symbol chosen by the second log2(M) input bits.The emitted complex symbol is denoted by st and belongs to the M-point constellation.
- Spectral Efficiency: SM spectral efficiency does not increase linearly with transmit antennas, unlike SMX.Matching SMX spectral efficiency may therefore require more transmit antennas or a larger constellation.
- Complexity and Hardware: SM computational complexity is independent of transmit-antenna count, and only one RF chain is required.The paper relates SM detection complexity to SIMO complexity and motivates SM for large-scale MIMO.
- Channel Model: The analysis assumes a frequency-flat i.i.d. Rayleigh channel with perfect receiver CSI and no transmitter CSI.The received signal includes AWGN with variance σ2 per dimension.
C. ML–Optimum Detector
The paper formulates the ML detector over all possible transmitted vectors and exploits SM’s single-active-antenna structure to simplify the search. It then introduces SM-Rx as a reduced-complexity decoder that prunes receive-side computations using a sphere radius.
- ML Detector: The ML receiver searches the complete set of possible transmitted vectors and selects the spatial and constellation symbols minimizing the received-signal distance.The search uses the Frobenius-norm metric over the transmitted-vector space Qm.
- ML Detector: Because SM activates only one antenna, the ML metric can be simplified into sums over receive antennas and candidate antenna-symbol pairs.The simplified formulation uses yr and hℓ,r for receive-antenna entries and channel coefficients.
- SM-Rx Detector: SM-Rx reduces the number of receive-antenna summations required by the ML receiver.It targets the receive search space rather than reducing the number of candidate antenna-symbol points.
- SM-Rx Detector: SM-Rx combines received signals while their Euclidean distance remains within radius R, updating R whenever an interior point is found.The minimum-distance point after the search is selected as the solution.
B. SM–Tx Detector
SM-Tx is a sphere decoder tailored to SM that reduces the transmit search space by evaluating only antenna-symbol points inside a radius. Its interval computations exploit SM’s single-active-antenna structure and include pre-computation costs in complexity analysis.
- Transmit Search Reduction: SM-Tx searches only antenna-symbol pairs inside a sphere centered on the received signal, rather than exhaustively evaluating all transmit candidates.The candidate pair consists of an antenna index ℓ and constellation symbol s.
- Search Formulation: SM-Tx uses a Cholesky factorization of the positive-definite matrix Ḡ = H̄^T H̄ + ϕĪ_Nt to support its search formulation.The factorization is written as Ḡ = D̄D̄^T.
- Search Formulation: The subset ΘR contains transmit-space points within radius R and is computed around z̄ = D̄ρ̄, with ρ̄ = Ḡ^-1H̄^T ȳ.These points define the candidates retained by SM-Tx.
- Transmit Search Reduction: SM-Tx reduces ML complexity by efficiently computing ΘR and restricting evaluation to points inside the resulting intervals.The radius is updated when an interior point is found, and dependent intervals need not be recomputed independently.
- SM-Specific Structure: SM-specific properties require the intervals to be calculated once per transmit point, unlike conventional sphere decoding, and allow SM-Tx in both underdetermined and overdetermined MIMO.The supported setups include Nt > Nr and Nt ≤ Nr.
- Complexity Accounting: SM-Tx requires pre-computations to estimate points inside the sphere, and these costs are included in its complexity comparison with ML detection.Ignoring these computations can misrepresent the detector’s overall complexity.
IV. COMPUTATIONAL COMPLEXITY OF SM–RX AND SM–TX
The paper compares the computational complexity of SM–ML, SM–Rx, and SM–Tx using real multiplication and division operations. SM complexity is independent of transmit-antenna count, while SMX complexity increases linearly with it, producing increasing reductions relative to SMX as transmit antennas grow.
- Complexity is measured as the number of real multiplication and division operations required by each receiver.
- SM complexity does not depend on the number of transmit antennas, whereas SMX complexity increases linearly with that number.
- For the same spectral efficiency, the reduction in SM–ML complexity relative to SMX–ML is quantified by a dedicated reduction expression.
- 60% complexity reduction is achieved by SM relative to SMX when N_t = 4, with larger reductions as the number of transmit antennas increases.
B. SM–Rx
The SM–Rx receiver computes its complexity from candidate points examined across antenna and symbol combinations. Its complexity is bounded by 3×2^m and 6N_r2^m, while interval calculations avoid repeated evaluations for equivalent antenna and symbol-imaginary-part combinations.
- The SM–Rx complexity is expressed as a sum over transmit-antenna and constellation-symbol combinations.
- 3×2^m ≤ C_Rx−SD ≤ 6N_r2^m, with bounds determined by the number of candidate points examined.
- SM–Rx retains a complexity interval of 3×2^m to 6×2^m even when N_r = 1 and requires no ML-relative pre-computations.
- SM–Tx complexity includes pre-computation, interval calculation, and the operations required to find points in the subset Θ_R.
- Interval expression (19) is evaluated only for eligible points with new antenna indices and imaginary symbol parts, reducing repeated calculations.
V. ERROR PROBABILITY OF SM–SDS AND INITIAL RADIUS SELECTION METHOD
The paper derives SM–SD error probability by separating errors caused by incorrect decisions inside the sphere from errors caused by excluding the transmitted point. It uses this analysis to select a noise-dependent initial radius and obtain a closed-form BER expression.
- SM–SD BER is estimated with a union bound and decomposed according to whether the transmitted point lies inside the search sphere.
- Errors arise either from deciding on an incorrect symbol–antenna combination inside the sphere or from excluding the transmitted point from Θ_R.
- SM–SD approaches optimum performance when the probability of excluding the transmitted point is sufficiently small.
- The initial sphere radius is chosen as a function of noise variance, with α selected by setting the transmitted-point exclusion probability to 10^-6.
- A closed-form expression for SM–SD BER is obtained by substituting the derived expected pairwise error result into the union-bound formulation.
VI. RESULTS
The results section uses Monte Carlo simulations over at least 10^6 Rayleigh-fading channel realizations to compare large-scale MIMO, SM–ML, SM–SD, and SMX–SD.
- At least 10^6 Rayleigh-fading channel realizations are simulated to compare large-scale MIMO, SM–ML, SM–SD, and SMX–SD.
A. Analytical performance of SM–SD
SM and SMX exhibit similar BER at equal constellation sizes in several settings, while SM gains an advantage with more receive antennas. The analytical bound closely matches simulations below BER < 10^-2.
- BER < 10^-2 closely matches the analytical bound for SM–ML, SM–Rx, and SM–Tx at m = 6, 8 and N_r = 4.Both proposed sphere decoders overlap with SM–ML in the reported simulations.
- Similar BER is observed for SM and SMX when they use the same constellation size, including m = 6, 8 with N_r = 2.The comparison is reported for Figs. 3 and 5.
- 1 dB better performance is achieved by BPSK–SM than BPSK–SMX when N_r = 4 and m = 6.8–QAM SM is also approximately 0.5 dB better than 8-QAM SMX in this setting.
- Increasing the number of receive antennas improves SM BER and produces better SM performance than SMX in the reported comparisons.The paper summarizes SM as similar or better than SMX, with performance depending on constellation size and receive-antenna count.
C. Complexity Analysis
The proposed SM sphere decoders reduce computational complexity relative to ML and SMX-SD, with the preferred variant depending on constellation size, SNR, and antenna configuration.
- Variant selection: SM–Tx is preferred for large constellation sizes, while SM–Rx is preferred for smaller constellation sizes.For m = 6, the choice also varies with receive-antenna configuration and SNR.
- m = 6: 40% to 16%: SM–Tx with Nt = 2 has this relative complexity range for large constellations at low to high SNR.For smaller constellations, SM–Rx ranges from 56% to 26%.
- m = 6: 32% less complex: SM–SD than SMX–SD for 32–QAM, while the reduction is 22% for BPSK.These comparisons use SMX–SD with Nt = 2.
- m = 8: 4%: SM–Tx with Nt = 2 reaches this relative complexity at high SNR for high constellation sizes when m = 8 and Nr = 2.For Nr = 4, SM–Tx with Nt = 2 and Nt = 4 reaches 3% and 10%, respectively.
- m = 8: Approximately 20% and 10%: SM–SD is less complex than SMX–SD for Nr = 2 and Nr = 4, respectively.SM–Rx also becomes approximately 10% less complex when Nr increases from 2 to 4.
- Summary: The two proposed decoders retain near-optimum BER while substantially reducing computational complexity, with SM–Tx favored for few transmit antennas and SM–Rx for more receive antennas.The lowest-complexity choice depends on the antenna configuration.
VII. CONCLUSION
The paper introduces two sphere decoders tailored to spatial modulation and evaluates their performance–complexity trade-off. They retain ML-equivalent BER while substantially reducing complexity, with the preferable decoder depending on system conditions.
- Conclusion: The proposed SM sphere decoders substantially reduce computational complexity while retaining the same BER as the ML-optimum detector.The paper analyzes this performance–complexity trade-off for decoders designed specifically for SM.
- Conclusion: Closed-form analytical SM performance in i.i.d. Rayleigh flat-fading channels closely agrees with simulation results.The conclusion reports agreement between analytical and numerical evaluation.
- Conclusion: No proposed sphere decoder is superior in every case; the preferable decoder depends on the target spectral efficiency and system configuration.The conclusion emphasizes a performance–complexity trade-off rather than a universally best decoder.
- Conclusion: SM–SD hardware complexity and power consumption do not depend on the number of transmit antennas, while BER improves as transmit antennas increase.The paper presents SM–SD as an appropriate candidate for large-scale MIMO systems.