Marco Di Renzo
email: marco.direnzo@lss.supelec.fr

Harald Haas
email: h.haas@ed.ac.uk

Marco Di

Renzo L2s

Space Shift Keying (SSK) Modulation: On the Transmit Diversity / Multiplexing Trade-Off

, and that a transmit-diversity equal to two can still be obtained while increasing the data rate with respect to SSK modulation; and iii) we propose a general encoding scheme that allows us to get transmit-diversity greater than two. The solution combines TOSD and GSSK principles in a unique fashion, and is flexible enough to accommodate various transmit-diversity gains by trading-off the number of transmit-antenna, the number of simultaneously-active transmit-antenna, and the achievable data rate. Furthermore, proposed methods and findings are substantiated via analysis and numerical simulations.

I. INTRODUCTION

Spatial Modulation (SM) is a recently proposed modulation scheme for multiple-antenna wireless systems, which increases the data rate of single-antenna systems (multiplexing gain) without the need of multiplexing multiple datastreams at the transmitter and, thus, avoiding multi-stream detectors at the receiver [START_REF] Yang | Information-guided channel-hopping for high data rate wireless communication[END_REF]- [START_REF] Di Renzo | A general framework for performance analysis of space shift keying (SSK) modulation for MISO correlated Nakagami-m fading channels[END_REF]. The fundamental benefit introduced by SM for multiple-antenna wireless systems can be readily understood by regarding this technology as a highrate coding mechanism [7, Eq. ( 1)]. SM uses the spatial domain as an additional dimension (the so-called spatialconstellation diagram), on top of the conventional signalconstellation diagram [START_REF] Di Renzo | Performance analysis of spatial modulation[END_REF], to convey part of the information bits. This is realized by exploiting the spatial de-correlation property of the wireless medium for data modulation, which allows the encoder to establish a one-to-one mapping between the information messages and the channel impulse responses on the available transmit-to-receive wireless links [START_REF] Di Renzo | A general framework for performance analysis of space shift keying (SSK) modulation for MISO correlated Nakagami-m fading channels[END_REF].

However, it is well-known that the performance of a given transmission technology is only in part determined by the multiplexing gain, and that another important component to be analyzed is the so-called diversity gain [START_REF] Wang | A simple and general parameterization quantifying performance in fading channels[END_REF]. Furthermore, a large multiplexing gain can be easily offset by a small diversity gain. Thus, it is very important to study the diversity offered by SM and to understand the multiplexing/diversity tradeoff provided by this technology. This problem has recently attracted the interest of some researchers. More specifically, most research is focused on a low complexity implementation of SM, which is known as Space Shift Keying (SSK) modulation [START_REF] Jeganathan | Space shift keying modulation for MIMO channels[END_REF]. Unlike SM, in SSK modulation only the spatial-constellation diagram is used for data modulation, thus trading-off transmitter and receiver complexity for the achievable data rate [START_REF] Di Renzo | Performance analysis of spatial modulation[END_REF]. In [START_REF] Jeganathan | Space shift keying modulation for MIMO channels[END_REF] and [START_REF] Di Renzo | On the performance of space shift keying MIMO systems over correlated Rician fading channels[END_REF], it is shown that SSK modulation can achieve a receive-diversity gain that increases linearly with the number of antennas at the receiver. In [START_REF] Jeganathan | Generalized space shift keying modulation for MIMO channels[END_REF], it is shown that, regardless of the number of simultaneously-active antennas at the transmitter, SSK modulation is unable to provide transmit-diversity gains. In [START_REF] Di Renzo | Performance comparison of different spatial modulation schemes in correlated fading channels[END_REF], a simple method is introduced to overcome that limitation. The solution is applicable to a transceiver with two transmit-antenna and one receiveantenna, and it neither results in a loss of spectral efficiency, nor does it require multiple simultaneously-active antennas at the transmitter. In [START_REF] Sugiura | A unified MIMO architecture subsuming space shift keying, OSTBC, BLAST and LDC[END_REF], transmit-diversity is achieved by sending redundant information in non-overlapping time-slots, and thus resulting in a spectral efficiency loss. In [START_REF] Di Renzo | Space shift keying (SSK-) MIMO over correlated Rician fading channels: Performance analysis and a new method for transmitdiversity[END_REF], it is proved that the method in [START_REF] Di Renzo | Performance comparison of different spatial modulation schemes in correlated fading channels[END_REF] is unable to provide fulldiversity for an arbitrary number of antennas at the transmitter and, in general, it allows us to achieve transmit-diversity only equal to two. Finally, in [START_REF] Handte | BER analysis and optimization of generalized spatial modulation in correlated fading channels[END_REF] the authors have studied the achievable transmit-diversity of SM and have pointed out that SM cannot achieve transmit-diversity. However, no solutions are provided to cope with this issue and it is shown that the absence of transmit-diversity may result, especially for high correlated fading channels, in a substantial performance loss. The design of transmit-diversity for SM is investigated in [START_REF] Di Renzo | Transmit-diversity for spatial modulation (SM): Towards the design of high-rate spatially-modulated space-time block codes[END_REF], and a simple solution to achieve transmit-diversity equal to two is proposed. Another solution can be found in [START_REF] Basar | Space-time block coding for spatial modulation[END_REF]. From all the above, it is apparent that while receivediversity is well understood for SM and SSK modulation, transmit-diversity is an open research issue, which deserves further investigation for the successful application of this technology especially in the downlink of wireless communication systems. In fact, in this scenario it is more economical to add complexity to a single central entity rather than at multiple remote and primarily low-cost devices. Motivated by these considerations, this paper aims at shedding light on the design of transmit-diversity for SSK modulation. The specific contributions of this paper are as follows. 1) We move from the Time-Orthogonal-Signal-Design (TOSD) principle in [START_REF] Di Renzo | Performance comparison of different spatial modulation schemes in correlated fading channels[END_REF], and propose a practical method to design a SSK modulation scheme with transmit-diversity equal to two for any number of antennas at the transmitter. The method uses time-orthogonal waveforms to shape the signals emitted by the antenna-array at the transmitter. 2) In order to increase the data rate of SSK modulation without reducing the performance too much, we show that the method in 1) can be applied to Generalized SSK (GSSK) modulation [START_REF] Jeganathan | Generalized space shift keying modulation for MIMO channels[END_REF], which allows multiple transmitantenna to be simultaneously active for data transmission. This additional degree of freedom comes at the expenses of increasing both transmitter and receiver complexity. However, single-stream detection can still be used at the receiver. 3) Finally, we propose an advanced transmit-diversity scheme which combines TOSD and GSSK modulation in a unique fashion, and allows us to achieve transmit-diversity gains greater than two by adequately choosing the number of transmit-antenna and active transmit-antenna. The price to be paid for this flexibility is twofold [START_REF] Di Renzo | A general framework for performance analysis of space shift keying (SSK) modulation for MISO correlated Nakagami-m fading channels[END_REF]: i) multiple antennas at the transmitter have to transmit data at the same time, and ii) a reduction in the achievable data rate with respect to the maximum rate achieved by GSSK modulation. This results in a transmit-diversity/multiplexing trade-off that is accurately investigated in this paper. Furthermore, we emphasize that our solutions still retain a single-stream receiver for data detection regardless of the number of simultaneously-active antennas at the transmitter. Finally, we note that the results described in this paper are novel in different ways: i) with respect to [START_REF] Di Renzo | Performance comparison of different spatial modulation schemes in correlated fading channels[END_REF], we provide a practical scheme to achieve transmitdiversity and do not limit ourselves to merely identifying the general conditions that the transmitted pulses should satisfy for performance improvement, ii) for the first time, we report a transmit-diversity method for GSSK modulation, and iii) we document, for the first time for SSK modulation, a coding scheme with transmit-diversity greater than two, which does not exploit spectrally inefficient repetition coding.

The reminder of this paper is organized as follows. In Section II, we review SSK and GSSK modulation schemes in order to highlight their limits in achieving transmitdiversity. In Section III, we propose a general method to design SSK and GSSK modulation schemes with transmitdiversity equal to two. In Section IV, we extend the analysis in Section III to design SSK modulation schemes with transmitdiversity greater than two. In Section V, we provide some general guidelines to designing SSK modulation schemes with arbitrary transmit-diversity and study the related transmitdiversity/multiplexing trade-off. In Section VI, we analyze differences and similarities of our proposed transmit-diversity schemes with respect to conventional methods. In Section VII, our claims are substantiated through Monte Carlo simulations. Finally, Section VIII concludes the paper.

II. BACKGROUND: SSK MODULATION WITH

TRANSMIT-DIVERSITY 1

A. System Model

We consider a general Multiple-Input-Single-Output (MISO) communication system with N t antennas at the transmitter and N r = 1 antennas at the receiver. The assumption N r = 1 does not limit the generality of the results derived in this paper since we are mainly interested in studying transmit-diversity. From [START_REF] Di Renzo | On the performance of space shift keying MIMO systems over correlated Rician fading channels[END_REF], it can be readily proved that the solutions described in this paper can be extended to multiple receive-antenna and that the overall diversity achieved by the resulting system is simply multiplied by N r . We assume that the receiver uses a Maximum-Likelihood (ML) detector with Full Channel State Information (F-CSI) [START_REF] Jeganathan | Spatial modulation: Optimal detection and performance analysis[END_REF].

Notation. The following notation is used throughout this paper: i) |•| 2 and • 2 denote the square absolute value of a complex number and the square Euclidean norm of a complex vector, respectively; ii) N a is the number of simultaneously-active antennas at the transmitter, with 1 ≤ N a ≤ N t ; iii) E m is the average total energy transmitted by the N a active antennas that emit a non-zero signal. E m is equally distributed among the active antennas, i.e. each active antenna emits a signal with energy E m /N a ; iv) N 0 is the power spectral density per dimension of the Additive White Gaussian Noise (AWGN) at the receiver input; v)

γ=E m /(4N 0 ); vi) Q (x) = 1 √ 2π +∞ x exp -t 2 2 dt is the Q-function; vii) {α i } Nt i=1
is the complex channel gain on the wireless link from the i-th transmit-antenna to the receive-antenna; viii) {w i (•)} N t i=1 is the pulse shape used at the i-th transmit-antenna. Unless otherwise stated, we assume:

+∞ -∞ w i (t) w j (t) dt = 0 if i = j and +∞ -∞ w i (t) w j (t) dt = 1 if i = j; ix) R denotes the rate in bits/s/Hz; x) • is the floor function; and xi) •
• is the binomial coefficient.

B. SSK Modulation

SSK modulation works as follows [START_REF] Di Renzo | A general framework for performance analysis of space shift keying (SSK) modulation for MISO correlated Nakagami-m fading channels[END_REF], [START_REF] Jeganathan | Space shift keying modulation for MIMO channels[END_REF]: i) the transmitter encodes blocks of log 2 (N t ) data bits into the index of a single transmit-antenna (i.e., N a = 1), which is switched on for data transmission while all the other antennas are kept silent, and ii) the receiver solves a N t -hypothesis testing problem to estimate the transmit-antenna that is not idle, which results in the estimation of the unique sequence of bits emitted by each encoder [START_REF] Di Renzo | On the performance of space shift keying MIMO systems over correlated Rician fading channels[END_REF]Sec. III]. The block of bits encoded into the index of the i-th transmit-antenna is called "message", and the N t messages are equiprobable. Furthermore, in SSK modulation the shaping filters used by the transmit-antenna are the same, i.e., w i (t) = w 0 (t) for i = 1, 2, . . . , N t , and

+∞ -∞ w 0 (t) w 0 (t) dt = 1.
In [START_REF] Di Renzo | A general framework for performance analysis of space shift keying (SSK) modulation for MISO correlated Nakagami-m fading channels[END_REF], we have shown that the Bit Error Probability (BEP) of SSK modulation can be tightly upper-bounded as follow:

BEP SSK ≤ 1 Nt -1 N t X t 1 =1 N t X t 2 =t 1 +1 Q "q γ |αt 2 -αt 1 | 2 « (1)
We emphasize that (1) is conditioned upon fading channel statistics. The Average Bit Error Probability (ABEP) can be computed either numerically or analytically [START_REF] Di Renzo | A general framework for performance analysis of space shift keying (SSK) modulation for MISO correlated Nakagami-m fading channels[END_REF], [START_REF] Di Renzo | On the performance of space shift keying MIMO systems over correlated Rician fading channels[END_REF].

From (1), we conclude that SSK modulation has transmitdiversity equal to one. In fact, each term in the two-fold summation depends on the difference of two complex channel gains, which turns out to be equivalent to a Single-Input-Single-Output (SISO) system with an equivalent channel gain given by the difference of them. From [START_REF] Wang | A simple and general parameterization quantifying performance in fading channels[END_REF], it can be concluded that SSK achieves no transmit-diversity gain.

C. GSSK Modulation

In [START_REF] Jeganathan | Generalized space shift keying modulation for MIMO channels[END_REF], the authors have introduced GSSK modulation, which is a generalized version of SSK modulation that does not restrict the number of simultaneously-active antennas to N a = 1. With respect to [START_REF] Jeganathan | Generalized space shift keying modulation for MIMO channels[END_REF], in this paper we have a different view of the usefulness of GSSK modulation for multiple-antenna wireless systems. In [START_REF] Jeganathan | Generalized space shift keying modulation for MIMO channels[END_REF], the GSSK concept is proposed as a modulation scheme that exploits CSI at the transmitter for optimizing the spatial-constellation diagram. Numerical results have shown some performance improvements with respect to SM, but at the cost of requiring a feedback channel. In this paper, we use GSSK modulation without CSI at the transmitter. In our opinion, the main flexibility introduced by the GSSK concept is not in the optimization of the spatialconstellation diagram for performance improvement, but in the inherent possibility of switching on multiple antennas at the transmitter for increasing the data rate. In fact, this flexibility, which comes at the expenses of transmitter complexity [START_REF] Jeganathan | Space shift keying modulation for MIMO channels[END_REF], allows GSSK modulation to enlarge the size of the spatialconstellation diagram, and, thus, to increase the achievable data rate. In particular, while the achievable rate of SSK modulation is R SSK = log 2 (N t ), GSSK modulation can provide a data rate up to R GSSK = log 2 N t Na , where the floor function stems form the fact that the constellation size is constrained to be a power of two to use the SSK principle. It can be shown that R GSSK achieves its maximum value when N a = N t /2 . So, in this paper we are mainly interested in studying transmit-diversity schemes for GSSK modulation that do not require any CSI at the transmitter.

The working principle of GSSK modulation used in this paper can be summarized as follows: i) the transmitter encodes blocks of log 2

N t Na bits into one point of an enlarged spatial-constellation diagram of size N H = 2 log 2 ( N t
Na ) , which enables N a antennas to be switched on for data transmission while all the other antennas are kept silent, and ii) similar to SSK modulation, the receiver solves a N Hhypothesis testing problem to estimate the N a antennas that are not idle, which results in the estimation of the unique message emitted by the encoder. Similar to SSK modulation, w i (t) = w 0 (t) for i = 1, 2, . . . , N t , and

+∞ -∞ w 0 (t) w 0 (t) dt = 1.
Under these assumptions, the performance of GSSK modulation can be estimated by using the result summarized in Theorem 1. We note that the BEP in ( 2) is much tighter than the framework provided in [START_REF] Jeganathan | Generalized space shift keying modulation for MIMO channels[END_REF] for the same reasons as those provided in [START_REF] Di Renzo | A general framework for performance analysis of space shift keying (SSK) modulation for MISO correlated Nakagami-m fading channels[END_REF] for SSK modulation.

Theorem 1: Let S comb be the set of N a -combination of the set of N t antennas at the transmitter. The size of S comb is N t Na . Let ᾱk denote the k-th element of S comb for k = 1, 2, . . . , N t N a . ᾱk is a N a -dimension vector whose elements (ᾱ k (q) for q = 1, 2, . . . , N a ) are the fading coefficients {α i } N t i=1 . Then, the BEP can be upper-bounded as follows:

BEP GSSK ≤ 1 N H -1 N H X t 1 =1 N H X t 2 =t 1 +1 Q 0 B B @ v u u u t γ Na ˛Na X q=1 [ ᾱt 2 (q) -ᾱt 1 (q)] ˛21 C C A (2)
where we have assumed that the first N H (with N H < Nt N a ) elements of S comb have been chosen to implement the GSSK modulation scheme (no optimization on the spatialconstellation diagram is considered).

Proof: The result in (2) follows from the analytical development in [START_REF] Di Renzo | A general framework for performance analysis of space shift keying (SSK) modulation for MISO correlated Nakagami-m fading channels[END_REF], [START_REF] Di Renzo | On the performance of space shift keying MIMO systems over correlated Rician fading channels[END_REF], and by taking into account that: i) the equivalent transmitted message is given by the summation of the signals emitted by the N a active transmit-antenna, ii) the spatial-constellation diagram has size N H , and iii) the energy emitted by each antenna is scaled by N a to keep constant the total radiated energy per transmission.

To clarify the notation in Theorem 1, let us consider a simple example with (N t , N a ) = [START_REF] Di Renzo | Performance analysis of spatial modulation[END_REF][START_REF] Jeganathan | Generalized space shift keying modulation for MIMO channels[END_REF]. In this case, we have: [START_REF] Jeganathan | Generalized space shift keying modulation for MIMO channels[END_REF], only the first N H = 8 elements of S comb , i.e., ᾱk for k = 1, 2, . . . , N H are considered. Also, the ABEP can be computed either from (2) by using the framework developed in [START_REF] Di Renzo | On the performance of space shift keying MIMO systems over correlated Rician fading channels[END_REF] or numerically.

ᾱ1 = [α 1 , α 2 ], ᾱ2 = [α 1 , α 3 ], ᾱ3 = [α 1 , α 4 ], ᾱ4 = [α 1 , α 5 ], ᾱ5 = [α 2 , α 3 ], ᾱ6 = [α 2 , α 4 ], ᾱ7 = [α 2 , α 5 ], ᾱ8 = [α 3 , α 4 ], ᾱ9 = [α 3 , α 5 ], ᾱ10 = [α 4 , α 5 ]. In
Finally, similar to SSK modulation, from (2) it is simple to conclude that no transmit-diversity is achieved by GSSK modulation. In fact, each term in the two-fold summation in (2) depends on the linear combination of 2N a channel gains, which turns out to be equivalent to a SISO system with a channel gain equal to this linear combination. Thus, with respect to SSK modulation, GSSK modulation can increase the data rate, but it is still unable to provide transmit-diversity.

III. SSK MODULATION WITH TRANSMIT-DIVERSITY 2

The aim of this section is to propose improved schemes that can overcome the limitations of SSK and GSSK modulation to achieve transmit-diversity. More specifically, we propose a general method to achieve transmit-diversity equal to two for arbitrary values of N t and N a . The method is based on the TOSD principle introduced in [START_REF] Di Renzo | Performance comparison of different spatial modulation schemes in correlated fading channels[END_REF], where we have shown that transmit-diversity can be achieved via adequate pulse shaping at the transmitter. However, we significantly improve the intuition in [START_REF] Di Renzo | Performance comparison of different spatial modulation schemes in correlated fading channels[END_REF]. More precisely, in [START_REF] Di Renzo | Performance comparison of different spatial modulation schemes in correlated fading channels[END_REF] the orthogonal signal design exploits the different propagation delays on the transmit-to-receive wireless links. However, this solution could require a signal with a very large transmission bandwidth. In this paper, we propose a different way to exploit the TOSD principle, which foresees time-orthogonal shaping filters across the transmit-antenna. Furthermore, we show that this approach can be used for any N t , while in [START_REF] Di Renzo | Performance comparison of different spatial modulation schemes in correlated fading channels[END_REF] only the setup with N t = 2 is considered. Finally, we show that the proposed idea can be extended to GSSK modulation.

A. TOSD-SSK Modulation

By using a terminology similar to [START_REF] Di Renzo | Performance comparison of different spatial modulation schemes in correlated fading channels[END_REF], the proposed modulation scheme is called TOSD-SSK modulation. Its working principle is the same as SSK modulation in Section II-B, but with a fundamental difference: each antenna, when active for data transmission, radiates a different pulse waveform, and the waveforms across the antennas are time-orthogonal as described in Section II-A. We emphasize that in TOSD-SSK modulation a single antenna is active for data transmission, and that the transmitted message is still encoded into the index of the transmit-antenna and not into the impulse response of the shaping filter. In other words, the proposed idea is different from conventional SISO schemes, which use Orthogonal Pulse Shape Modulation (O-PSM) [START_REF] Da | Spectrally efficient UWB pulse shaping with application in orthogonal PSM[END_REF] and are unable to achieve transmit-diversity, as only a single wireless link is exploited for communication.

The performance of TOSD-SSK modulation can be estimated by using the result summarized in Theorem 2.

Theorem 2: The BEP of TOSD-SSK modulation with time-orthogonal shaping filters is upper-bounded as follows:

BEP TOSD-SSK ≤ 1 Nt -1 N t X t 1 =1 N t X t 2 =t 1 +1 Q r γ " |αt 1 | 2 + |αt 2 | 2 " ! (3)
Proof: The result in (3) follows from [START_REF] Di Renzo | On the performance of space shift keying MIMO systems over correlated Rician fading channels[END_REF] by taking into account that: i) by exploiting the orthogonality of the shaping filters, the cross-product of the complex channel gains in [10, Eq. ( 9)] is always equal to zero, and ii) the noises at the output of the matched filters in [10, Eq. ( 11)] are uncorrelated due to the orthogonality of the shaping filters.

By carefully analyzing (3), we observe that, unlike SSK modulation, each summand depends on the power-sum of two channel gains. According to [START_REF] Wang | A simple and general parameterization quantifying performance in fading channels[END_REF], it can be shown that this system offers a transmit-diversity equal to two. We notice that if N t = 2 the system achieve full transmit-diversity. The ABEP can be computed by using well-consolidated frameworks for performance analysis of receive-diversity systems [START_REF] Wang | A simple and general parameterization quantifying performance in fading channels[END_REF].

B. TOSD-GSSK Modulation

Let us now generalize the GSSK modulation scheme for transmit-diversity. The new modulation concept is called TOSD-GSSK modulation, and exploits the same modulation principle as GSSK in Section II-C but uses time-orthogonal shaping filters at the transmitter. The performance of TOSD-GSSK modulation can be estimated from Theorem 3.

Theorem 3: By adopting the same notation as in Theorem 1, the BEP of TOSD-GSSK modulation with time-orthogonal shaping filters is upper-bounded as follows:

BEP TOSD-GSSK ≤ 1 N H -1 N H X t 1 =1 N H X t 2 =t 1 +1 Q "r γ N a ' ' ᾱt 1, t 2 ' ' 2 « ( 4
)
where ᾱt 1, t 2 is a vector whose components are all the distinct elements in ᾱt 1 and ᾱt 2 .

Proof: The result in (4) follows immediately by taking into account the comments in Theorem 1 and Theorem 2. Due to space constraints, the details of the derivation are omitted.

To clarify the notation in ( 4) and to better understand the achievable performance, we consider again the example in Section II-C with (N t , N a ) = (5, 2). We have, e.g.:

ᾱ1,2 = [α 2 , α 3 ], ᾱ1,3 = [α 2 , α 4 ], ᾱ1,8 = [α 1 , α 2 , α 3 , α 4 ]
, etc. By carefully analyzing (4) and the example, we observe that, unlike GSSK modulation, each term in (4) depends on the power-sum of at least two channel gains. Similar to TOSD-SSK modulation, we can conclude that the system can provide a transmit-diversity equal to two. Two important observations are worth being made in this case: i) the fact that the powersum of at least two channel gains is obtained is inherent in the "data bit" to "N a -active transmit-antenna index" mapping of GSSK modulation. In other words, for each pair of transmitted messages, the two subsets of active antennas contain at least two different transmit-antenna indexes; and ii) some terms in (4) have higher transmit-diversity. For example, the term corresponding to ᾱ1,8 in the example above has transmit-diversity equal to four. However, it is known that the overall transmitdiversity of the system depends on the worst summands in (2), i.e., the terms with transmit-diversity two. Similar to TOSD-SSK modulation, the ABEP can be easily computed [START_REF] Wang | A simple and general parameterization quantifying performance in fading channels[END_REF].

IV. SSK MODULATION WITH TRANSMIT-DIVERSITY GREATER THAN 2

The main drawback of the methods introduced in Section III is their limitation to provide transmit-diversity greater than two, even when N t > 2 and N a > 2. Basically, in TOSD-SSK and TOSD-GSSK modulation, N t and N a can only be used to adjust the data rate, which is equal to R TOSD-SSK = log 2 (N t ) and R TOSD-GSSK = log 2 N t Na , respectively. In this section, we describe a method that combines TOSD and GSSK principles to achieve a higher transmit-diversity. The main idea is based on the TOSD-GSSK modulation scheme, but instead of allowing the transmitter to exploit the whole spatial-constellation diagram (i.e., the N H message-toantenna mappings), we adequately choose a subset of points, N ⊥ H < N H , where to apply the SSK modulation principle. This limits the achievable data rate, which reduces to R = log 2 N ⊥ H , but allows us to increase the transmit-diversity. For reasons that will become apparent in the next sub-sections, the proposed method is called: TOSD-GSSK modulation with mapping by pairwise disjoint set partitioning. We emphasize that the choice of the spatial-constellation diagram is different from [START_REF] Jeganathan | Generalized space shift keying modulation for MIMO channels[END_REF], which is unable to provide transmit-diversity, and requires no CSI at the transmitter.

In this section, we introduce our idea with two examples. The general procedure is described in Section V along with the analysis of the transmit-diversity/multiplexing trade-off.

A. Transmit-Diversity 4 -An Example

Let us describe a simple scheme with N t = 4, N a = 2, and R = 1, which provides transmit-diversity equal to four. Similar to the TOSD-GSSK modulation principle, we assume that the N t antennas use time-orthogonal shaping filters.

The working principle is as follows1 : i) if the encoder emits a "0" ("1") bit, the SSK mapper encodes it into the pair of antennas {TX 1 , TX 2 } ({TX 3 , TX 4 }), which are switched on for transmission, while the antennas {TX 3 , TX 4 } ({TX 1 , TX 2 }) are kept silent; and ii) the receiver uses a single-stream MLoptimum detector similar to TOSD-GSSK modulation.

The BEP can be computed by using a methodology similar to Theorem 3. The final result is given in Corollary 1.

Corollary 1: The BEP of the (N t , N a , R) = (4, 2, 1) scheme with TOSD-GSSK modulation with mapping by pairwise disjoint set partitioning is as follows:

BEP Div4 = Q 0 @ v u u t γ Na N t X t=1 |αt| 2 1 A (5)
The formula in [START_REF] Di Renzo | Performance analysis of spatial modulation[END_REF] confirms that the transmit-diversity achieved by the proposed scheme is four, i.e., full transmitdiversity is obtained in this case.

B. Transmit-Diversity 6 -An Example

Let us describe a simple scheme with N t = 12, N a = 3, and R = 2, which provides transmit-diversity equal to six. Also in this case, we assume that the N t antennas use timeorthogonal shaping filters.

The working principle is as follows: i) If the encoder emits a "00" ("01", "10", "11") pair of bits, the SSK mapper encodes them into the triple of antennas {TX 1 , TX 2 , TX 3 } ({TX 4 , TX 5 , TX 6 }, {TX 7 , TX 8 , TX 9 }, {TX 10 , TX 11 , TX 12 }), which are switched on for transmission, while all the other antennas are kept silent; and ii) the receiver uses a single-stream ML-optimum detector similar to TOSD-GSSK modulation.

The BEP can be computed by still using Theorem 3. The final result is given in Corollary 2.

Corollary 2: The BEP of the (N t , N a , R) = (12, 3, 2) scheme with TOSD-GSSK modulation with mapping by pairwise disjoint set partitioning is upper-bounded as follows:

BEP Div6 ≤ 1 N ⊥ H -1 N ⊥ H X t 1 =1 N ⊥ H X t 2 =t 1 +1 Q "r γ Na SNR t 1 ,t 2 « (6)
where 6), we conclude that the proposed method achieves a very high transmit-diversity equal to six. Furthermore, this transmit-antenna. 2) The difference between our proposal and the OTD scheme can be understood even better by considering the TOSD-GSSK modulation with mapping by pairwise disjoint set partitioning in Section IV. In Theorem 5, it is shown that the transmit-diversity provided by this scheme is Div = 2N a , which means that the transmit-diversity is twice the number of active transmit-antenna. This is in net contrast to the OTD concept where the achievable diversity is equal to N a . Again, this is due to the antenna-index coded modulation principle inherent in SSK modulation. This result tells us that with the proposed approach we can achieve the same transmitdiversity as the OTD scheme but we can halve the number of active antenna elements, and, thus, the number of radio frequency chains at the transmitter, which is known to be a very desirable feature to reduce the complexity and the power consumption of the transmitter [START_REF] Jeganathan | Space shift keying modulation for MIMO channels[END_REF]. 3) Theorem 4 states that for SSK modulation is not sufficient to use time-orthogonal shaping filters at the transmitter to get transmit-diversity of any order, but the way the mapping "information-bit" to "spatial-constellation-point" is performed plays a crucial role to this end. More specifically, TOSD-GSSK modulation requires time-orthogonal filters in all the antennas at the transmitter, however it is unable to achieve transmit-diversity greater than two if the mapping by pairwise disjoint set partitioning is not used. In OTD, orthogonal pulse shaping is sufficient to achieve full transmit-diversity.

N ⊥ H = 4, and SNR 1,2 = |α 1 | 2 + |α 2 | 2 + |α 3 | 2 + |α 4 | 2 + |α 5 | 2 +|α 6 | 2 , SNR 1,3 = |α 1 | 2 +|α 2 | 2 +|α 3 | 2 +|α 7 | 2 +|α 8 | 2 + |α 9 | 2 , SNR 1,4 = |α 1 | 2 + |α 2 | 2 + |α 3 | 2 +
In conclusion, SSK modulation shares some features with OTD. However, it has some additional degrees of freedom to achieve transmit-diversity, which can be exploited by paying attention to the way the SSK modulator maps messages to points in the spatial-constellation diagram. VII. NUMERICAL EXAMPLES In this section, numerical examples are shown to validate the claims in the sections above. The setup is as follows: i) we consider a frequency-flat Rayleigh channel model with independent and identically distributed fading over all the transmit-to-receive wireless links; ii) we assume the mean power of each fading gain to be normalized to 1; iii) to have a large set of orthogonal shaping filters, we use the family of Hermite polynomials [START_REF] Da | Spectrally efficient UWB pulse shaping with application in orthogonal PSM[END_REF]; and iv) as a performance metric, we consider the ABEP, which is obtained by averaging the BEP discussed in the sections above over fading channel statistics.

In Fig. 1, we compare Monte Carlo simulations and the analytical models developed in this paper 4 . We can observe a very good agreement between analysis and simulation, especially in the high E m /N 0 region where our bounds are tighter. The slopes of the curves confirm our findings about the transmit-diversity gain achieved by the proposed schemes. In particular, we can notice that the slope of the ABEP gets steeper for increasing values of the transmit-diversity, which agrees with our analytical findings.

In Fig. 2, we analyze the performance of various proposed schemes for the same rate R. Numerical results confirm that the proposed schemes (Theorem 5) with transmit-diversity six and eight provide a substantial performance improvement with respect to already reported SSK modulation schemes with transmit-diversity one and two [START_REF] Di Renzo | Performance comparison of different spatial modulation schemes in correlated fading channels[END_REF]. The price to pay is the need of increasing N t and N a . However, this characteristic is shared with other state-of-the-art transmit-diversity schemes, such as OTD and Space Time Block Codes (STBCs) [START_REF] Derryberry | Transmit diversity in 3G CDMA systems[END_REF]. 4 The framework for Div=8 is not shown here due to space constraints. In Fig. 3, we compare the performance of various system setups for the same N t and N a . We believe that this is an important point to be addressed since some constraints might be imposed on the total and active number of antennas at the transmitter. The results show that, for the same hardware constraints, we can support a broad range of qualityof-service requirements and data rates. This highlights that SSK modulation is a flexible scheme, which can be easily implemented in an adaptive multiple-antenna system design, where we could switch among the SSK, GSSK, TOSD-SSK, TOSD-GSSK, and the more general TOSD-GSSK mapping by pairwise disjoint set partitioning schemes to find the best trade-off among complexity, performance, and data rate.

* ) Div=4, N t = 4, N a = 2, R = 1 (•) Div=6, N t = 6, N a = 3, R = 1 ( ) Div=8, N t = 5, N a = 4, R = 1.

VIII. CONCLUSION

In this paper, we have studied the transmitdiversity/multiplexing trade-off of SSK modulation. We have proposed a very flexible modulation scheme, which can accommodate a broad range of data rates, transmit-diversity, and performance requirements. It has been shown that the proposed system achieves a transmit-diversity that is twice the number of active antennas at the transmitter, and a data rate that increases logaritmically with the ratio of total and active antennas at the transmitter. Higher transmission rates can be achieved for systems with transmit-diversity one and two. We believe that the proposed modulation schemes are suitable for an adaptive multiple-antenna wireless system design, where the best quadruple (N t , N a , R, Div) can be tuned according to the specific needs of the end-user.

Fig. 1 .

 1 Fig. 1. ABEP against Em/N0: comparison of analytical model and simulation. Solid lines show the analytical model and markers show Monte Carlo simulations. (left) Diversity 1 and 2; Legend: ( * ) Div=1,N t = 5, N a = 2, R = 3 (GSSK) (•) Div=1, N t = 6, N a = 3, R = 4 (GSSK) ( ) Div=2, N t = 5, N a = 2, R = 3 (TOSD-GSSK) ( )Div=2, Nt = 6, Na = 3, R = 4 (TOSD-GSSK). (right) Diversity 4, 6, and 8 obtained with TOSD-GSSK modulation with mapping by pairwise disjoint set partitioning; Legend: ( * ) Div=4, N t = 4, N a = 2, R = 1 (•) Div=6, N t = 6, N a = 3, R = 1 ( ) Div=8, N t = 5, N a = 4, R = 1.

Fig. 2 .R = 1 ;

 21 Fig. 2. ABEP against Em/N0: performance comparison for the same rate. (left) R = 1; Legend: ( * ) Div=1, N t = 2, N a = 1 (SSK), (•) Div=2, N t = 2, N a = 1 (TOSD-SSK), ( ) Div=4, N t = 4, N a = 2 (TOSD-GSSK with set partitioning), ( ) Div=6, N t = 6, N a = 3 (TOSD-GSSK with set partitioning), (•) Div=8, N t = 8, Na = 4 (TOSD-GSSK with set partitioning). (right) R = 2; Legend: ( * ) Div=1, Nt = 4, Na = 1 (SSK), (•) Div=2, Nt = 4, Na = 1 (TOSD-SSK), ( ) Div=4, N t = 8, N a = 2 (TOSD-GSSK with set partitioning), ( ) Div=6, N t = 12, N a = 3 (TOSD-GSSK with set partitioning).

Fig. 3 .

 3 Fig. 3. ABEP against Em/N0: performance for the same total and active transmitantenna. (left) N t = 8; Legend: ( * ) Div=1, N a = 1, R = 3 (SSK), (•) Div=2, N a = 1, R = 3 (TOSD-SSK), ( ) Div=1, N a = 4, R = 6 (GSSK), ( ) Div=2, N a = 4, R = 3 (TOSD-GSSK), (•) Div=4, N a = 2, R = 2 (TOSD-GSSK with set partitioning), (>) Div=8, Na = 4, R = 1 (TOSD-GSSK with set partitioning). (right) Na = 3; Legend: ( * ) Div=1, Nt = 6, R = 4 (GSSK), (•) Div=1, Nt = 7, R = 5 (GSSK), ( ) Div=2, N t = 6, R = 4 (TOSD-GSSK), ( ) Div=2, N t = 7, R = 5 (TOSD-GSSK), (•) Div=6, N t = 6, R = 1 (TOSD-GSSK with set partitioning), (>) Div=6, N t = 12, R = 2 (TOSD-GSSK with set partitioning).

  |α 10 | 2 + |α 11 | 2 + |α 12 | 2 , SNR 2,3 = |α 4 | 2 + |α 5 | 2 + |α 6 | 2 + |α 7 | 2 + |α 8 | 2 + |α 9 | 2 , SNR 2,4 = |α 4 | 2 + |α 5 | 2 + |α 6 | 2 + |α 10 | 2 + |α 11 | 2 + |α 12 | 2 , SNR 3,4 = |α 7 |

2 + |α 8 | 2 + |α 9 | 2 + |α 10 | 2 + |α 11 | 2 + |α 12 | 2 . From (

We denote by TX i (i = 1,

2, . . . , Nt) the Nt antennas at the transmitter.

A partition of a set X is a set P of non-empty subsets of X such that the union of the elements of P is equal to X, and the intersection of any two distinct subsets of P is empty.

In[START_REF] Derryberry | Transmit diversity in 3G CDMA systems[END_REF] the time-orthogonal shaping filters are Walsh codes typically used in spread spectrum systems.

ACKNOWLEDGMENT

We gratefully acknowledge support from the EPSRC (EP/G011788/1) and the European Union (PITN-GA-2010-264759, GREENET project) for this work. M. Di Renzo acknowledges support of the Laboratory of Signals and Systems under the project "Jeunes Chercheurs". H. Haas acknowledges the Scottish Funding Council support of his position within the ERPem between the University of Edinburgh and Heriot Watt University.

transmit-diversity gain is achieved with only three active antennas at the transmitter.

V. TRANSMIT-DIVERSITY / MULTIPLEXING TRADE-OFF

Let us now summarize in two general theorems the transmit-diversity methods illustrated through examples in Section III and Section IV. These theorems provide a general procedure to design SSK modulation schemes with the desired transmit-diversity/multiplexing trade-off.

Theorem 4: Let a (N t , N a ) multiple-antenna wireless system using SSK modulation. Let N H = 2 log 2 ( N t N a ) be the size of the spatial-constellation diagram. Then: i) the system achieves transmit-diversity equal to Div = 1 and rate R = log 2 N t Na if the N t antennas at the transmitter use the same shaping filter. This scheme is called GSSK modulation and reduces to SSK modulation if N a = 1; and ii) the system achieves transmit-diversity equal to Div = 2 and rate R = log 2 N t Na if the N t transmit-antenna use timeorthogonal shaping filters. This scheme is called TOSD-GSSK modulation and reduces to TOSD-SSK modulation if N a = 1.

Proof: The proof follows immediately from Section III. Theorem 5: Let a (N t , N a ) multiple-antenna wireless system using the SSK modulation principle. Let N ⊥ H be the size of the partition 2 of the set of N t antennas such that

, each subset of the partition has N a distinct elements and the subsets are pairwise disjoint. Then, the system achieves transmit-diversity equal to Div = 2N a and rate R = log 2 N ⊥ H if the N t transmit-antenna use timeorthogonal shaping filters. This scheme is called TOSD-GSSK modulation with mapping by pairwise disjoint set partitioning.

Proof: The proof follows immediately from Section IV.

VI. DIFFERENCES AND SIMILARITIES WITH CONVENTIONAL TRANSMIT-DIVERSITY

In this section, we aim at providing some insights about differences and similarities among the proposed transmitdiversity schemes and those available in the literature for conventional modulation. By looking at some state-of-the-art proposals for transmit-diversity [START_REF] Derryberry | Transmit diversity in 3G CDMA systems[END_REF], we can readily recognize that the most similar solution to the transmit-diversity concepts for SSK modulation proposed in Section III and Section IV is the so-called Orthogonal Transmit-Diversity (OTD) method [18, Fig. 3]. In OTD, the signals emitted by multiple antennas at the transmitter are shaped by using time-orthogonal shaping filters 3 , as the TOSD principle in our proposals foresees. However, TOSD for SSK modulation and OTD are very different in the way transmit-diversity is achieved. The reason is threefold. 1) Let us consider the TOSD-SSK modulation scheme in Section III-A. In Theorem 4, it is shown that this scheme can achieve Div = 2 with a single active transmit-antenna, i.e., N a = 1. This is a property that is not shared with OTD, which achieves a transmitdiversity equal to the number of active antennas. In other words, TOSD-SSK modulation can achieve transmit-diversity even though there is only one active antenna, and this peculiar property stems from the SSK modulation principle, i.e., in conveying the information bits into the spatial positions of the


Abdelhamid Younis
email: a.younis@ed.ac.uk

Marco Di Renzo
email: marco.direnzo@lss.supelec.fr

Raed Mesleh
email: r.mesleh@jacobs-university.de

Harald Haas
email: h.haas@ed.ac.uk

Sphere Decoding for Spatial Modulation

Keywords: Multiple-Input-Multiple-Output (MIMO) Systems, Spatial Modulation (SM), Sphere Decoding (SD)

In this paper, Sphere Decoding (SD) algorithms for Spatial Modulation (SM) are developed to reduce the computational complexity of Maximum-Likelihood (ML-) optimum detectors, which foresee an exhaustive search of the whole search space and have a complexity that linearly increases with the product of number of transmit-antenna, receive-antenna, and size of the modulation scheme. Three SDs specifically designed for SM are proposed and analyzed in terms of Bit Error Probability (BEP) and computational complexity. By judiciously choosing some key parameters, e.g., the radius of the sphere centered around the received signal, it is shown that the proposed algorithms offer the same BEP as ML-optimum detection, with a significant reduction of the computational complexity. Also, it is shown that none of the proposed SDs is always superior to the others, but the best SD to use depends on the system setup, i.e., the number of transmit-antenna, receive-antenna, and the size of the modulation scheme. The computational complexity trade-off offered by the proposed solutions is studied via analysis and simulation, and numerical results are shown to validate our findings.

I. INTRODUCTION

Spatial Modulation (SM) is a recently proposed transmission technology for Multiple-Input-Multiple-Output (MIMO) wireless systems, which has been originally proposed to increase the spectral efficiency of single-antenna systems by avoiding Inter-Channel Interference (ICI) [START_REF] Mesleh | Spatial modulation[END_REF]. This is attained through the adoption of a new modulation and coding scheme, which foresees: i) the activation, at each time instance, of a single antenna that transmits a given data symbol (constellation symbol), and ii) the exploitation of the spatial position (index) of the active antenna as an additional dimension for data transmission (spatial symbol). Both constellation symbol and spatial symbol depend on the incoming data bits. Thereby, an overall increase, by the base-two logarithm of the number of transmit-antenna, of the spectral efficiency is achieved, while still retaining a complexity comparable to single-antenna systems.

In particular, at the receiver the Maximum Likelihood (ML) optimum decoder is a simple single-stream detector, which performs an exhaustive search over the whole constellation symbol and spatial symbol space, and whose computational complexity (C) linearly increases with the product of transmitantenna (N t ), receive-antenna (N r ), and size of the modulation scheme (M ), i.e., C ∝ M N t N r [START_REF] Jeganathan | Spatial modulation: optimal detection and performance analysis[END_REF]. Unlike other spatial multiplexing schemes for MIMO systems, such as the V-BLAST (Vertical Bell Laboratories Layered Space-Time) [START_REF] Foschini | Layered space-time architecture for wireless communication in a fading environment when using multi-element antennas[END_REF], [START_REF] Wolniansky | V-BLAST: an architecture for realizing very high data rates over the rich-scattering wireless channel[END_REF], there is a substantial reduction in receiver complexity, as no multi-stream detectors with exponential-growing complexity with N t are required. In addition to this significant complexity reduction, SM also outperforms many conventional single-antenna and multi-antenna wireless systems [START_REF] Mesleh | Spatial modulation[END_REF], [START_REF] Renzo | Performance analysis of spatial modulation[END_REF], thus potentially being an appealing transmission concept for the next generation of wireless systems.

In spite of its low-complexity implementation and superior performance results, there still is potential for further computational complexity reductions, especially when: i) high spectral efficiencies are required (i.e., the product M N t is large), or ii) high diversity gains and, thus, low error probabilities, are needed (i.e., N r is large). Furthermore, complexity issues become even more pressing when both M N t and N r are large. Motivated by these considerations, some recent research works have focused on developing low-complexity detectors for SM. For example, in [START_REF] Mesleh | Spatial modulation[END_REF] and [START_REF] Yang | Information-guided channel-hopping for high data rate wireless communication[END_REF] two sub-optimal two-step detectors based on heuristics are proposed. However, in [START_REF] Jeganathan | Spatial modulation: optimal detection and performance analysis[END_REF] it is shown that the detector in [START_REF] Mesleh | Spatial modulation[END_REF] belongs to the family of nonexact methods [START_REF] Hassibi | On the sphere-decoding algorithm I. expected complexity[END_REF], and is, in general, a few dB worse than ML-optimum detection. On the other hand, in [START_REF] Younis | Reduced complexity sphere decoder for spatial modulation detection receivers[END_REF] an exact low-complexity detector for SM has been proposed, which is based on the Sphere Decoding (SD) algorithm [START_REF] Viterbo | A universal lattice code decoder for fading channels[END_REF]. Therein, it is shown that the proposed solution has a computational complexity that is bounded by 8M N t ≤ C ≤ 8M N t N r , and provides error performance very close to the ML-optimum detector. This SD-based detector is especially suitable when the number of receive-antenna N r is very large, as it reduces the size of the search space related to the multiple antennas at the receiver (we denote this search space as "receive search space"). However, it has two main limitations: i) it does not reduce the dimension of the search space due to the number, N t , of transmit-antenna and the size, M , of the signal modulation diagram (we denote this search space as "transmit search space"), which prevents the detector to achieve a significant reduction in computational complexity when high data rates are required (i.e., when both N t and M are large), and ii) the detector has the same complexity as the ML-optimum decoder when N r = 1. In general, the reduction in decoding complexity is not very high when N r is small, as often happens in the downlink of cellular systems. The detector in [START_REF] Younis | Reduced complexity sphere decoder for spatial modulation detection receivers[END_REF] is here called Receiver-centric SD (Rx-SD).

Motivated by these considerations, in this paper we move from the results in [START_REF] Younis | Reduced complexity sphere decoder for spatial modulation detection receivers[END_REF] and propose two new low-complexity detectors for SM, which are based on the SD principle. The first solution aims at reducing the "transmit search space", and, thus, can be seen as a complementary solution to [START_REF] Younis | Reduced complexity sphere decoder for spatial modulation detection receivers[END_REF]. In particular, as opposed to [START_REF] Younis | Reduced complexity sphere decoder for spatial modulation detection receivers[END_REF], the proposed decoder is suitable when either N t or M , or both N t and M are large. On the other hand, it keeps the "receive search space" the same as the original ML-optimum decoder. This detector is called Transmitter-centric SD (Tx-SD). On the other hand, the second solution combines both Rx-SD and Tx-SD with the aim of reducing the complexity of the ML-optimum receiver in both the receive and transmit search spaces. This detector is called Combined-SD (C-SD). More specifically, the Tx-SD detector is based on a simplified implementation of the conventional SD proposed in [START_REF] Hassibi | On the sphere-decoding algorithm I. expected complexity[END_REF], which exploits the peculiar property of SM that only a single antenna is active at any time instance. Due to space constraints, in this paper we focus on the so-called non-underdetermined MIMO setup with N t ≤ N r . In the recent period, some efficient SD methods for the underdetermined MIMO setup have been proposed (see, e.g., [START_REF] Cui | An efficient generalized sphere decoder for rank-deficient MIMO systems[END_REF], [START_REF] Wang | A low-complexity generalized sphere decoding approach for underdetermined linear communication systems: performance and complexity evaluation[END_REF], [START_REF]A list sphere decoding algorithm with improved radius setting strategies[END_REF] and references therein). However, the analysis of this setup for SM is postponed to a future research contribution.

In this paper, we provide a careful study of the performance of these three detectors, along with an accurate comparison of their computational complexity. Numerical results show that the proposed solutions provide a substantial reduction in computational complexity with respect to the ML-optimum detector, and no loss in the Bit Error Probability (BEP). Furthermore, it is shown that the Rx-SD is less complex than the C-SD when M is not very large, while the C-SD is the best solution when either M is large or N r is small. The reason why Rx-SD outperforms C-SD when M is not very large is due to the some pre-computations required by the SD algorithm to determine the actual points of the reduced space to search through.

The reminder of this paper is organized as follow. In Section II, the system model along with the ML-optimum and Rx-SD detectors are summarized. In Section III, the new Tx-SD and C-SD receivers are described. In Section IV, an accurate analysis of the computational complexity of Tx-SD and C-SD is performed. In Section V, some numerical results are shown to compare the proposed receivers. Finally, Section VI concludes the paper.

II. SYSTEM MODEL

A. SM Modulator

SM works as follows [START_REF] Mesleh | Spatial modulation[END_REF]. The bitstream emitted by a binary source is divided into blocks containing log 2 (N t ) + log 2 (M ) bits each, with log 2 (N t ) and log 2 (M ) being the number of bits needed to identify the spatial symbol and the constellation symbol, respectively. Each block is split into two sub-blocks of log 2 (N t ) and log 2 (M ) bits each, and the following mapping rule is used:

• The bits in the first sub-block are used to select the antenna that is switched on for data transmission, while all the other transmit-antenna are kept silent. In this paper, the actual transmit-antenna that is active for transmission is denoted by ℓ t , with ℓ t ∈ {1, 2, . . . , N t }. • The bits in the second sub-block are used to choose a symbol in the signal-constellation diagram. Without loss of generality, Quadrature Amplitude Modulation (QAM) is considered. In this paper, the actual complex symbol emitted by the transmit-antenna ℓ t is denoted by s t , with s t ∈ {s 1 , s 2 , . . . , s M }. Accordingly, the N t × 1 transmitted vector is:

x ℓt,st = 0 1×(ℓt-1) , s t , 0 1×(Nt-ℓt) T (1)
where (•)

T denotes transpose operation, and 0 p×q is a p × q matrix with all-zero entries.

B. Channel Model

The modulated vector, x ℓt,st , in ( 1) is transmitted through a frequency-flat N r × N t MIMO fading channel with impulse response H. In this paper, a Rayleigh fading channel model is assumed, and, thus, the entries of H are modeled as complex independent and identically distributed (i.i.d.) Gaussian random variables with zero-mean and unit-variance.

Thus, the N r × 1 received vector can be written as follows:

y = Hx ℓt,st + n ( 2
)
where n is the N r -dimensional Additive White Gaussian Noise (AWGN) with zero-mean and variance σ 2 per dimension at the receiver input.

From (1), (2) simplifies as follows:

y = h ℓt s t + n (3)
where h ℓt is the ℓ t -th column of H.

C. ML-Optimum Detector

The optimum detector based on the ML principle has been derived in [START_REF] Jeganathan | Spatial modulation: optimal detection and performance analysis[END_REF]:

l(ML) t , ŝ(ML) t = arg min ℓ∈{1,2,...Nt} s∈{s1,s2,...sM } y -h ℓ s 2 F = arg min ℓ∈{1,2,...Nt} s∈{s1,s2,...sM } Nr r=1 |y r -h ℓ,r s| 2 (4)
where

• 2 F is the Frobenius norm,
• identifies the estimated spatial and constellation symbols, and y r and h ℓ,r is the r-th entry of y and h ℓ , respectively. The computational complexity of (4), in terms of real multiplications, is equal to:

C ML = 8M N t N r (5)
as the ML detector searches through the whole transmit and receive search spaces.

D. Rx-SD Detector

In [START_REF] Younis | Reduced complexity sphere decoder for spatial modulation detection receivers[END_REF], a reduced-complexity and close-to-optimal BEPachieving decoder is proposed, which, as mentioned in Section I, aims at reducing the receive search space. The detector can formally be written as follows: More specifically, the Rx-SD receiver works as follows. Given a sphere with radius R, the receiver computes the set of optimal Ñr (ℓ, s) for ℓ ∈ {1, 2, . . . N t } and s ∈ {s 1 , s 2 , . . . s M } as follows:

h l(Rx-SD) t , ŝ(Rx-SD) t i = arg
Ñr (ℓ, s) = min n∈{1,2,...Nr} n n r=1 |y r -h ℓ,r s| 2 > R 2 (7)
In other words, for each ℓ ∈ {1, 2, . . . N t } and s ∈ {s 1 , s 2 , . . . s M }, the Rx-SD receiver does not combine, according to the Maximal Ratio Combining (MRC) principle [START_REF] Jeganathan | Spatial modulation: optimal detection and performance analysis[END_REF], the signals received by all the N r antennas at the receiver, but it keeps combining the received signals until the Euclidean norm in [START_REF] Yang | Information-guided channel-hopping for high data rate wireless communication[END_REF] gives a point that lie inside a sphere of radius R and centered around the received signal itself. Since the number of antennas, Ñr (•, •), that are actually used for MRC are computed adaptively for each point in the transmit search space, in [START_REF] Younis | Reduced complexity sphere decoder for spatial modulation detection receivers[END_REF] it is shown that there is no loss in either diversity or coding gain: the BEP is exactly the same as the ML detector in [START_REF] Wolniansky | V-BLAST: an architecture for realizing very high data rates over the rich-scattering wireless channel[END_REF].

In [START_REF] Younis | Reduced complexity sphere decoder for spatial modulation detection receivers[END_REF], the interested reader can find an accurate analysis of the computational complexity of the Rx-SD detector along with an efficient method to choose the radius R, which significantly affects the performance of the algorithm. In this paper, we simply mention that:

• The complexity of the Rx-SD receiver is given by:

C Rx-SD = 8 Nt ℓ=1 M s=1 Ñr (ℓ, s) (8)
It is easy to show that C Rx-SD lies in the interval

8M N t ≤ C Rx-SD ≤ 8M N t N r
, where the lower bound corresponds to the scenario where Ñr (ℓ, s) = 1 for ℓ ∈ {1, 2, . . . N t } and s ∈ {s 1 , s 2 , . . . s M }, and the upper bound corresponds to the scenario where Ñr (ℓ, s) = N r for ℓ ∈ {1, 2, . . . N t } and s ∈ {s 1 , s 2 , . . . s M }. In other words, in the best-case scenario Rx-SD has the same complexity as a Multiple-Input-Single-Output (MISO) system, while in the worst-case scenario it has the same complexity as the ML-optimum detector in (4). These results suggest that the larger N r , the higher the potential gain with respect to the ML-optimum receiver. Let us note that the Rx-SD solution has no pre-computations with respect to the ML-optimum detector. In fact, Ñr (ℓ, s) for ℓ ∈ {1, 2, . . . N t } and s ∈ {s 1 , s 2 , . . . s M } in [START_REF] Hassibi | On the sphere-decoding algorithm I. expected complexity[END_REF] are implicitly computed when solving the hypothesisdetection problem in [START_REF] Yang | Information-guided channel-hopping for high data rate wireless communication[END_REF]. • The radius R can be chosen as R = 2αN r σ 2 , where α is the solution of the equation as follows [START_REF] Hassibi | On the sphere-decoding algorithm I. expected complexity[END_REF], [START_REF] Younis | Reduced complexity sphere decoder for spatial modulation detection receivers[END_REF]:

γ (N r , 2αN r ) Γ (N r ) = 1 -ε (9)
and γ (x, a) = a 0 ξ x-1 exp (-ξ) dξ is the lower incomplete Gamma function, Γ (x) = +∞ 0 ξ x-1 exp (-ξ) dξ is the Gamma function, and ε is an arbitrary small value close to zero, e.g., ε = 10 -6 .

III. NEW LOW-COMPLEXITY SPHERE DECODERS FOR SM

As anticipated in Section I, in this section two new SDs for SM are introduced. The first one (Tx-SD), aims at reducing the transmit search space, as opposed to the Rx-SD search space, and the second one (C-SD) combines Rx-SD and Tx-SD decoders in order to reduce both transmit and receive search spaces.

A. Tx-SD Detector

The Tx-SD for SM is a modified version of the wellknown SD for MIMO systems [START_REF] Hassibi | On the sphere-decoding algorithm I. expected complexity[END_REF], [START_REF] Viterbo | A universal lattice code decoder for fading channels[END_REF]. It, however, exploits the peculiar property of SM that only a single antenna is active for transmission. More specifically, similar to conventional SDs, the Tx-SD scheme reduces the number of points (ℓ, s) for ℓ ∈ {1, 2, . . . N t } and s ∈ {s 1 , s 2 , . . . s M } to be searched through in (4), i.e., the transmit search space, by computing the Euclidean distances only for those points that lie inside a sphere with radius R and centered around the received signal. However, unlike conventional SDs, in our scheme the set of points inside the sphere are much simpler to be computed, as there is only a single active antenna in SM. In this section, we show how to compute these intervals. While in the next section, we provide an estimate of the computational complexity of the proposed detector.

The analytical derivation follows the notation in [START_REF] Hassibi | On the sphere-decoding algorithm I. expected complexity[END_REF], which here is briefly summarized to make the paper self-contained. First, for ease of analytical derivation, the complex-valued model in ( 2) is replaced by its real-valued equivalent, as follows [START_REF] Kailath | Space-Time Wireless Systems: From Array Processing to MIMO Communications[END_REF]:

ȳ = Hx ℓt,st + n ( 10
)
where ȳ is a 2N r × 1 vector, H is a 2N r × 2N t matrix, xℓt,st is a 2N t × 1 vector, and n is a 2N r × 1 vector defined as follows:

               ȳ = Re y T , Im y T T H = Re {H} Im {H} -Im {H} Re {H} xℓt,st = Re x T ℓt,st , Im x T ℓt,st T n = Re n T , Im n T T (11)
and Re {•} and Im {•} denote real and imaginary parts, respectively.

By performing QR factorization of the matrix H, (10) can

Θ R = (ℓ, s) with ℓ ∈ {1, 2, . . . N t } and s ∈ {s 1 , s 2 , . . . s M }| ȳ -Hx ℓ,s 2 F ≤ R 2 =      (ℓ, s) with ℓ ∈ {1, 2, . . . N t } and s ∈ {s 1 , s 2 , . . . s M }| 2Nt i=1   zi - 2Nt j=i pi,j xj (ℓ, s)   2 ≤ R 2 Q      (14)
be re-written as follows [START_REF] Hassibi | On the sphere-decoding algorithm I. expected complexity[END_REF]:

ȳ = Q P 0 (2Nr-2Nt)×2Nt xℓt,st + n ( 12
)
where P is a 2N t × 2N t upper triangular matrix, Q = Q1 Q2 , and Q1 , Q2 are 2N r × 2N t and 2N r × (2N r -2N t ) matrices, respectively.

The Tx-SD scheme can be formally written as follows:

l(Tx-SD) t , ŝ(Tx-SD) t = arg min (ℓ,s)∈ΘR ȳ -Hx ℓ,s 2 F ( 13
)
where Θ R is the subset of points (ℓ, s) for ℓ ∈ {1, 2, . . . N t } and s ∈ {s 1 , s 2 , . . . s M } in the transmit search space that lie inside a sphere with radius R and centered around the received signal ȳ. In formulas, the subset Θ R can be written as shown in ( 14) on top of this page, where we have defined:

i) z = Q T 1 ȳ, ii) R 2 Q = R 2 -QT 2 ȳ 2 F
, iii) zi and xi (ℓ, s) are the i-th entry of vectors z and xℓ,s , respectively, and iv) pi,j is the (i, j)-th entry of matrix P.

The key point behind the application of SD for reducing the computational complexity of ML-optimum detectors is the efficient computation of the subset Θ R , which should avoid an exhaustive search in the whole transmit search space. As far as SM is concerned, these points can be computed in a very simple way, as summarized in Lemma 1.

Lemma 1: The subset of points Θ R in ( 14) lie in the intervals:

- 16), and we have defined zi,i+Nt = zipi,i+Nt xi+Nt (ℓ, s).

R Q + zi pi,i ≤ xi (ℓ, s) ≤ R Q + zi pi,i (15)
-R Q + zi,i+Nt pi,i ≤ xi (ℓ, s) ≤ R Q + zi,i+Nt pi,i (16)
for i = 2N t , 2N t -1, . . . , N t + 1 in (15), i = N t , N t - 1, . . . , 1 in (
Proof: This result can be obtained as follows.

1) First, we note that a necessary condition that the points of the transmit search space need to satisfy to belong to the subset Θ R in ( 14) is (for all i = 1, 2, . . . , 2N t ):

  zi - 2Nt j=i pi,j xj (ℓ, s)   2 ≤ R 2 Q (17)
which is a condition similar to conventional SD algorithms [START_REF] Hassibi | On the sphere-decoding algorithm I. expected complexity[END_REF]. 2) Second, we need to take into account that in SM only a single antenna is active at any time instance. In the equivalent real-valued signal model in [START_REF] Cui | An efficient generalized sphere decoder for rank-deficient MIMO systems[END_REF] and [START_REF] Kailath | Space-Time Wireless Systems: From Array Processing to MIMO Communications[END_REF] 15) and ( 16), respectively, which are directly obtained by solving the inequality in (17).

By comparing the intervals in ( 15) and ( 16) with those of a conventional SD [START_REF] Hassibi | On the sphere-decoding algorithm I. expected complexity[END_REF], we notice that (15) and ( 16) are much simpler, and this is due to the fact that in SM there is only one active antenna element, while in conventional SDs all the antennas transmit simultaneously. Note that, as (16) depends implicitly on (15), this means that (16) needs to be computed for all the points that lie in the interval in (15).

With respect to the Rx-SD scheme, the Tx-SD scheme foresees some pre-computations to estimate the points that lie inside the sphere of radius R. These additional computations are carefully taken into account in the analysis of the computational complexity of the Tx-SD scheme and its comparison with the ML-optimum detector (see Section IV). Furthermore, we note that the radius R in [START_REF] Aubert | Complexity gain of QR decomposition based sphere decoder in LTE receivers[END_REF] can still be computed from [START_REF] Viterbo | A universal lattice code decoder for fading channels[END_REF].

B. C-SD Detector

In Section II-D and Section III-A, we have seen that Rx-SD and Tx-SD aim at reducing the complexity of the MLoptimum detector by minimizing the size of the receive and transmit search spaces, respectively. So, it is natural to combine both of them to further decrease the receiver complexity by reducing the size of both the search spaces. The proposed C-SD is a two-step detector that works as follows:

1) First, the Tx-SD algorithm is used to reduce the transmit search space. The subset of points Θ R is computed as shown in [START_REF] Aubert | Complexity gain of QR decomposition based sphere decoder in LTE receivers[END_REF]. 2) Second, the Rx-SD algorithm is used to reduce the receive search space. More specifically, Rx-SD is applied only on the subset of points Θ R computed in the step above.

In formulas, we have:

l(C-SD) t , ŝ(C-SD) t = arg min (ℓ,s)∈ΘR    Ñr(ℓ,s) r=1 |y r -h ℓ,r s| 2    (18)
where Θ R and Ñr (ℓ, s) are computed by using ( 14) and ( 7), respectively.

IV. ANALYSIS OF COMPUTATIONAL COMPLEXITY

In this section, we analyze the computational complexity of Tx-SD and C-SD algorithms by taking into account the pre-computations needed to estimate the points of the reduced search space. The complexity is here computed as the number of real multiplications needed by each algorithm. Furthermore, we note that when divisions are involved, we take them into account and assume they have the same complexity as multiplications.

A. Tx-SD

The computational complexity of Tx-SD can be estimated by taking into account that:

1) The QR factorization in [START_REF]A list sphere decoding algorithm with improved radius setting strategies[END_REF], when computed by using the Householder algorithm [START_REF] Aubert | Complexity gain of QR decomposition based sphere decoder in LTE receivers[END_REF], requires a number of real multiplications equal to:

C QR = N ξ=1 2f (ξ) + f 2 (ξ) + 2f 3 (ξ) + 1 -N 3 r (19)
where

f (ξ) = N r + 1 -ξ and N = min {N r -1, N t }. 2) The computation of z = Q T 1 ȳ in (14) needs 4N t N r real multiplications, i.e., C z = 4N t N r . 3) The computation of QT 2 ȳ 2 F in (14) needs C QT 2 ȳ 2 F = 2N r (2N r -2N t + 1) real multiplications, i.e., C QT 2 ȳ 2 F = 2N r (2N r -2N t + 1).
4) The computation of the intervals in (15) and (16) requires: i) 2N t real divisions to compute (15) for N t antenna indexes; and ii) 1 real multiplication and 2 real divisions for a number of times equal to the total number of points that satisfy (15). In the worst-case scenario, the number of points computed in (15) is equal to the size, M I , of the imaginary constellation diagram composing the QAM constellation symbol. Accordingly, we have M I N t real multiplications and 2M I N t real divisions, and, thus, the complexity of computing the intervals in (15) and ( 16) can be upper-bounded by C interval = 2N t + 3M I N t . In summary, the analytical complexity resulting from the computation of the points in the subset Θ R can be upperbounded by:

C ΘR ≤ C QR + C z + C QT 2 ȳ 2 F + C interval (20)
Since ( 13) requires 8 real multiplications for each computed Euclidean distance, it follows that the computational complexity of the Tx-SD receiver can be upper-bounded as follows:

C Tx-SD ≤ C ΘR + 8N r card {Θ R } (21)
where card {•} denotes the cardinality, i.e., the number of points, in a set.

B. C-SD

The computational complexity of C-SD follows immediately from ( 8) and (21), as follows:

C C-SD ≤ C ΘR + 8 (ℓ,s)∈ΘR Ñr (ℓ, s) (22)
V. NUMERICAL RESULTS

In this section, Monte Carlo simulation results for at least 10 6 channel realisation are shown to compare the performance and computational complexity of ML-optimum and SD-based receivers. The numerical examples are obtained by assuming the system model in Section II. Furthermore, the radius R is chosen as described in [START_REF] Viterbo | A universal lattice code decoder for fading channels[END_REF] with ε = 10 -6 .

In Fig. 1, the BEP averaged over Rayleigh fading is shown by considering two different constellation sizes, and N t = N r = 4. We notice that all the SDs have the same performance, and all of them overlap with the ML-optimum detector. As expected, the performance of SM improves when M decreases.

In Fig. 2, Fig. 3, and Fig. 4, the computational complexity C is compared according to the estimates provided in the sections above. In particular, the figures show the relative computational complexity of the SDs with respect to the MLoptimum detector, i.e., C rel (%) = 100 × (C ML -C SD )/C ML . In Fig. 2, we observe that C-SD is always better than Tx-SD, while it is better than Rx-SD only for high SNRs. The reason for this latter result is due to the additional pre-computations required by both C-SD and Tx-SD solutions. As mentioned in Section I, we notice that the Rx-SD scheme is more effective in reducing the complexity when the number of antennas at the receiver is large.

Figures 3 and4 show an interesting setups where it is clearly highlighted that none of the proposed SDs is a priori superior to the others, and that the best detector to use actually depends on both the MIMO setup and the SNR. In particular, on the right-hand side of Fig. 3, we notice that the best receiver to use is the C-SD, while if we look at the left-hand side of Fig. 3 and Fig. 4 we notice that the best receiver to use is always the RX-SD. The reason is that in the former case the transmit search space is large enough to compensate for the pre-computations required by Tx-SD and C-SD receivers. On the contrary, in the latter case the transmit search space is not very large, and, thus, there is not too much gain in reducing it.

Finally, the right-hand side of Fig. 4 shows that Rx-SD and C-SD are almost equivalent, as both a large transmit search space and a large number of antennas at the receiver are considered.

In summary, we can conclude that Rx-SD turns out to be the best choice when the number of antennas at the receiver is large, as it can significantly reduce the receiver search space without any pre-computations. On the other hand, C-SD turns out to be the best choice when the transmit search space is very large and the number of antennas at the receiver is low. It is interesting to note that the Tx-SD scheme is never the best choice in the analyzed system setup. Since this latter decoder is the most similar to conventional SDs for MIMO systems, a main contribution of this paper is to have highlighted the importance of reducing both transmit and receive search spaces to get a significant reduction in receiver complexity with performance guarantees.

VI. CONCLUSION

In this paper, we have introduced and analyzed the performance/complexity trade-off of three SDs for SM. We have shown that the proposed solutions provide a substantial reduction of the computational complexity while retaining the same BEP as the ML-optimum detector. Numerical results have highlighted that no SD is superior to the others, and that the best solution to use depends on the MIMO setup, i.e., the triple (N t , N r , M ), and the SNR at the receiver. In general, Rx-SD is the best choice for large N r , and C-SD is the best option when either N r is low or M is large. Overall, analysis and results shown in this paper confirm that SD can be a viable and effective solution to reduce the complexity of SM without deteriorating its BER performance.

Fig. 1 .

 1 Fig. 1. BEP against the SNR. Nt = Nr = 4, (left) M = 8; (right) M = 64.

Fig. 2 .

 2 Fig. 2. Computational complexity against the SNR. Nt = Nr = 2, (left) M = 8; (right) M = 16.

Fig. 3 .

 3 Fig. 3. Computational complexity against the SNR. Nt = Nr = 4, (left) M = 8; (right) M = 64.

Fig. 4 .

 4 Fig. 4. Computational complexity against the SNR. Nt = Nr = 8, (left) M = 32; (right) M = 64.

  Ñr (ℓ, s) ≤ N r is the number of correlations in the receive search space that is computed by using the SD principle. Note that Ñr (•, •) can be different for each point in the transmit search space, i.e., for ℓ ∈ {1, 2, . . . N t } and s ∈ {s 1 , s 2 , . . . s M }.

	min ℓ∈{1,2,...Nt} s∈{s 1 ,s 2 ,...s M }	8 < :	Ñr (ℓ,s) X r=1	˛yr -h ℓ,r s	˛29 = ; (6)
	where 1 ≤

  By taking this remark into account, it follows that: a) if i = N t +1, N t +2, . . . , 2N t , then only the imaginary part of xℓ,s plays a role in (15), and, thus, only one entry xj (ℓ, s) can be non-zero; and b) if i = 1, 2, . . . , N t , then both real and imaginary parts of xℓ,s play a role in (16), and, thus, only two entries xj (ℓ, s) can be non-zero. The considerations in a) and b) lead to the intervals in (

, this is equivalent to having only two, out of 2N t , non-zero entries in the signal vectors xℓt,st and xℓ,s , respectively.