Sphere decoding (SD) for multiple-input and multiple-output systems is a well-recognized approach for achieving near-maximum likelihood performance with reduced complexity. SD is a tree search process, whereby a large number of nodes can be searched in an effort to find an estimation of a transmitted symbol vector. In this paper, a simple and generalized approach called layer pruning is proposed to achieve complexity reduction in SD. Pruning a layer from a search process reduces the total number of nodes in a sphere search. The symbols corresponding to the pruned layer are obtained by adopting a QRM-MLD receiver. Simulation results show that the proposed method reduces the number of nodes to be searched for decoding the transmitted symbols by maintaining negligible performance loss. The proposed technique reduces the complexity by 35% to 42% in the low and medium signal-to-noise ratio regime. To demonstrate the potential of our method, we compare the results with another well-known method — namely, probabilistic tree pruning SD.
Multiple-input and multiple-output (MIMO) architecture provides considerable gain in wireless channels and achieves high spectral efficiency without the need for an increase in bandwidth [1]–[2]. In MIMO, signal detection is a challenging task since it involves a tradeoff between performance and complexity; that is, greater performance can be achieved at the expense of greater complexity. Many signal-detection algorithms have been proposed in the relevant wider literature to achieve expected performance with reasonable complexity. All these algorithms mainly come under two categories: linear and nonlinear detection. The zero-forcing and minimum mean square error (MMSE) receivers are two simple main linear receivers. They provide the estimation of a transmitted signal with less complexity but incur substantial losses in symbol error rate (SER) performance.Among the nonlinear methods, maximum-likelihood detection (MLD) provides the optimal solution but at the cost of high complexity; thus, making an optimal solution impossible to realize in real time. Sphere decoding (SD), a tree search algorithm, was proposed to reduce the complexity of MLD [3]–[4]. The SD algorithm provides a near-MLD performance with acceptable complexity by limiting the search space inside the sphere of fixed radius [5]. SD works by transforming the distorted matrix linearly into an upper triangular matrix structure — this structure being the most suitable for searching. But the complexity of SD is, both on average and in the worst case, exponential [6]. Many modifications for the original SD have been proposed to reduce the complexity of the search procedure, therefore making it easier to obtain the estimate of a transmitted signal more quickly. Hassibi and Vikalo [6] proposed a novel radius based on noise statistics and the concept of increasing radii. In [7], a simple stopping criterion based on lattice reduction, that aided successive interference cancellation, was proposed. Algorithms such as increasing radius search [8] and inter-search radius control [9], use radius control by choosing an appropriate initial radius or varying a radius after a candidate is found. Increasing radii algorithm [10] and probabilistic tree pruning with sphere decoding (PTP-SD) [11] reduce complexity by adopting different radii in each layer. This is instead of using fixed radii, which until then had been the norm. These methods prune the tree earlier compared to other methods.In this paper, we applied layer pruning (LP) to the SD for further reduction of decoding complexity. In the proposed algorithm, the bottom layers are pruned, in view of the fact that they contain a larger number of nodes compared to the other layers. The QRM-MLD receiver [12]–[13] is used to find the transmitted symbol corresponding to the pruned layers. This paper demonstrates that LP-SD accomplishes MIMO signal detection quicker than all other variants of SD and that it does so with negligible performance loss.This paper is organized as follows. The MIMO system model is discussed in section II. The SD algorithm procedure is described in section III. Our proposed method, LP-SD, is presented in section IV. Section V presents the simulation results and a comparison with PTP-SD [11]. Section VI concludes this paper.
II. System Model
Consider a MIMO system comprising M_{T} transmit antennas and M_{R} receive antennas. The complex received signal vector is commonly expressed as$${y}_{c}={H}_{c}{x}_{c}+{n}_{c},$$where y_{c} is an M_{R} × 1 complex received signal vector, H_{c} is an M_{R} × M_{T} complex channel matrix of independent and identically distributed complex Gaussian coefficients with zero mean and unit variance (that is, N(0, 1)), and x_{c} represents the M_{T} × 1 complex transmitted signal vector. In this paper, we consider the L^{2}-QAM transmission, whose components are chosen from the equiprobable set x_{c} = {a + jb | a,b∈{−L−3/τ, ... , L−3/τ, L−1/τ}}∈ℂ. Let us assume ℝ is the vector of L integer values present in the modulation scheme. Note, τ is constant to make E(| a + jb |^{2}) unity in complex modulation. For example,
τ=1/ 10
for 16 QAM and
τ=1/ 42
for 64 QAM. The unknown complex additive white Gaussian noise vector is n_{c} — that is, N(0,1). Given the model in (1), the MLD that minimizes the error probability is given by$${x}_{c}=\mathrm{arg}{\mathrm{min}}_{{x}_{c}\in \u2102}{\Vert {y}_{c}-{H}_{c}{x}_{c}\Vert}^{2}.$$To perform SD, the complex signal model in (1) needs to be converted to a real-number signal model as$$\begin{array}{l}y=\left[\begin{array}{c}\Re ({y}_{c})\\ \Im ({y}_{c})\end{array}\right],\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}x=\left[\begin{array}{c}\Re ({x}_{c})\\ \Im ({x}_{c})\end{array}\right],\\ n=\left[\begin{array}{c}\Re ({n}_{c})\\ \Im ({n}_{c})\end{array}\right],\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}H=\left[\begin{array}{cc}\Re ({H}_{c})& -\Im ({H}_{c})\\ \Im ({H}_{c})& \Re ({H}_{c})\end{array}\right].\end{array}$$Then, the real number system model can be represented as$$y=Hx+n.$$Let m = 2M_{T}, n = 2M_{R}, then H becomes an n × m real channel matrix. We now describe the problem of estimating x from (4) in the context of SD. We use MATLAB notations to represent the equations throughout this paper. For example,$$\begin{array}{l}{R}_{k,k:m}{x}_{k:m}=\left\{R(k,k)\times x\left(k\right)\right\}+\left\{R(k,k+1)\times x\left(k+1\right)\right\}\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}+,\cdots \hspace{0.17em}\hspace{0.17em},+\{R(k,m)\times x(m)\}.\end{array}$$
III. SD
MLD searches the entire constellation ( ℂ ) for the transmitted vector with the smallest Euclidean distance. Hence, this searching is accomplished with non-deterministic polynomial-time (NP)-hard. SD reduces this complexity by limiting the search space within the sphere radius R_{SD}. The SD problem can be formulated as$$x=\mathrm{arg}{\mathrm{min}}_{x\in \u2102\subset {R}_{SD}}{\Vert y-Hx\Vert}^{2}.$$To achieve greater efficiency in the search process, QR decomposition (QRD) of the channel matrix has to be performed; this is symbolized by
H=[ Q Q' ] [ R T 0 T ] T ,
where R is an upper triangular matrix of size m × m with positive diagonal entries, 0 is a zero matrix, and Q and Q' are n × m and n × (n − m) unitary matrices, respectively. Applying QRD to (5) yields$$\begin{array}{l}{\Vert y-\left[\begin{array}{cc}Q& Q\text{'}\end{array}\right]\left[\begin{array}{c}R\\ 0\end{array}\right]x\Vert}^{2}\le {R}_{SD}^{2},\\ \Vert {Q}^{T}y-Rx\Vert \le {R}_{SD}^{2}-{\Vert Q\text{'}x\Vert}^{2},\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\Vert \tilde{y}-Rx\Vert \le {\tilde{R}}_{SD},\end{array}$$where ỹ = Q' y and
R ˜ SD = R SD 2 − ‖ Q'y ‖ 2 .
After applying QRD to (5), the SD problem can be reformulated as$$\widehat{x}=\mathrm{arg}{\mathrm{min}}_{x\in \u2102\subset {\tilde{R}}_{SD}}{\Vert \tilde{y}-Rx\Vert}^{2}.$$The inequality in (6) can then be expressed as$$\sum _{i=1}^{m}\left({\tilde{y}}_{i}-{\displaystyle \sum _{k=i}^{m}{R}_{i,k}{x}_{k}}\right)}\le {\tilde{R}}_{SD}.$$Again, the inequality in (8) can be expanded and rewritten as$$\begin{array}{l}{\tilde{R}}_{SD}\ge {({\tilde{y}}_{m}-{R}_{m,m}{x}_{m})}^{2}+{({\tilde{y}}_{m-1}-{R}_{m-1,m-1:m}{x}_{m-1:m})}^{2}\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}+\hspace{0.17em}\hspace{0.17em}\cdots \hspace{0.17em}\hspace{0.17em}{({\tilde{y}}_{1}-{R}_{1,1:m}{x}_{1:m})}^{2}.\end{array}$$In (9), x_{m} can be obtained first by taking advantage of the upper triangular property of R. This point must be chosen so as to be within the following range:$$\lceil \frac{-{\tilde{R}}_{SD}+{\tilde{y}}_{m}}{{R}_{m,m}}\rceil \le {x}_{m}\le \lfloor \frac{{\tilde{R}}_{SD}+{\tilde{y}}_{m}}{{R}_{m,m}}\rfloor ,$$where
⌈ . ⌉
and
⌊ . ⌋
are the ceiling and flooring of its arguments, respectively, to the nearest integer spanning the lattice. Furthermore, for every lattice point x_{m}, found between the lower bound (LB) and upper bound (UB) in (10), a new Z and a new ỹ can be found as follows:$${Z}_{m-1}^{2}={\tilde{R}}_{SD}-{({\tilde{y}}_{m}-{R}_{m,m}{x}_{m})}^{2},$$$${\tilde{y}}_{m-1}={\tilde{y}}_{m-1}-{R}_{m-1,m-1:m}{x}_{m}.$$Then, x_{m−1} can be obtained using$$\lceil \frac{-{Z}_{m-1}+{\tilde{y}}_{m-1}}{{R}_{m-1,m-1}}\rceil \le {x}_{m-1}\le \lfloor \frac{{Z}_{m-1}+{\tilde{y}}_{m-1}}{{R}_{m-1,m-1}}\rfloor .$$Following the above procedure, intervals can be obtained for x_{m–2}, x_{m–3} and so on until we reach x_{1}. In general, the kth layer LB and UB can be computed as$$LB=\lceil \frac{-{Z}_{k}+{\tilde{y}}_{k}}{{R}_{k,k}}\rceil ,$$$$UB=\lfloor \frac{{Z}_{k}+{\tilde{y}}_{k}}{{R}_{k,k}}\rfloor ,$$where ỹ and Z_{k} are obtained as follows:$${\tilde{y}}_{k}={\tilde{y}}_{k}-{R}_{k,k+1:m}{x}_{k+1:m},$$$${Z}_{k}=\sqrt{{Z}_{k+1}^{2}-{({\tilde{y}}_{k+1}-{R}_{k+1,k+1:m}{x}_{k+1:m})}^{2}}.$$If no lattice points lie inside LB and UB, for all k, then the search has to be restarted with the higher radius greater than
R ˜ SD .
Hence, the performance and complexity are greatly affected by the initial radius. For each layer k, the order of the search of candidates lying in between LB and UB plays an important role in reducing complexity. Fincke and Pohst [1] followed the Phost enumeration, which searches the candidates in the order LB, LB + 1, ..., UB. In [14] and [15], Schnorr–Euchner (SE)’s [4] enumeration — based on branch metric (B_{k}) — was used as the search order. After the LB and UB were found, the SE enumeration orders the total number of lattice points (N) lying in the interval into ascending order in accordance with the B_{k}. The candidates are ordered, using SE’s strategy, as SE_{k.1}, SE_{k.2}, ... , SE_{k.N}, which implies that B_{k}(SE_{k.1}) ≤ B_{k}(SE_{k.2}). The SE_{k.1} is given by$$S{E}_{k,1}=round\left(\frac{1}{{R}_{k,k}}\left({\tilde{y}}_{k}-{\displaystyle \sum _{j=k+1}^{m}{R}_{k,j}{x}_{j}}\right)\right).$$SE enumeration updates the radius of the sphere after the first point is found. This point is known as the Babai point. Hence, SE allows us to fix the highest initial radius and to find the right path earlier than Phost enumeration.
IV. LP on SD
The number of nodes visited is often treated as a benchmark for computational complexity in SD [6]. Recently, TP has been adopted in SD for the reduction of complexity. TP is a method of assigning different radii to different layers, instead of using a fixed radius — which until now has been the norm. In TP, the search process avoids unlikely nodes much earlier and is therefore able to estimate transmitted lattice points by visiting fewer nodes. In this paper, one such method, PTP-SD [11], is taken for comparison with our proposed LP-SD method. PTP-SD exploits the nature of the chi-square distribution for noise and takes into account unvisited layers in the path metric calculation.
- 1. LP
LP-SD is based on the idea that if the total number of nodes needed for searching the closest lattice points decreases, then it will lead to a reduction in complexity. For reducing the total number of nodes, we proposed a technique called LP. This is defined as pruning or excluding layers from a search, as depicted in Fig. 1. For example, consider the real-valued tree search diagram of a 2 × 2 MIMO with 16 QAM. As shown in Fig. 1, the proposed method uses SD only for finding the lattice points corresponding to the top three layers (that is, k = 4, k = 3, and k = 2). Note that the crossed nodes are skipped and that the white nodes are not included by SD. This way of excluding a layer from SD is termed as LP.
Tree-search diagram of LP-SD in a 2×2 MIMO system with 16 QAM modulation. SD omits the crossed nodes; white nodes corresponding to layer k = 1 are not included in SD, since the layer is pruned.
The major consideration in LP-SD is choosing the layer to be pruned. The proposed method works by pruning the bottom layer (that is, k = 1 in Fig. 1), as shown in Fig. 1. The two main reasons for choosing the bottom layer are:
• The estimate of a transmitted symbol belonging to the bottom layer (x1) can be obtained with the help of previously detected symbols corresponding to the upper layersx2,x3, ... ,xm.
• The number of nodes is greater in the bottom layer compared to other layers. The problem in hand is to find the transmitted symbol corresponding to the pruned layerx1. For this, we propose a QRM-MLD[12]–[13]method withM=1 for the real-valued channel matrix.
- 2. QRM-MLD
In the abstract, the QRM-MLD detection process can be explained as given in [16]. Performing QRD on (4) yields$$\begin{array}{l}{\Vert \tilde{y}-Rx\Vert}^{2}={({\tilde{y}}_{m}-{R}_{m,m}{x}_{m})}^{2}+{({\tilde{y}}_{m-1}-{R}_{m-1,m-1:m}{x}_{m-1:m})}^{2}\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}+\hspace{0.17em}\hspace{0.17em}\cdots \hspace{0.17em}\hspace{0.17em}+{({\tilde{y}}_{1}-{R}_{1,1:m}{x}_{1:m})}^{2},\end{array}$$where ỹ = Q^{T} y. Each term on the right-hand side of (19) is considered as a separate function given by$${\Vert \tilde{y}-Rx\Vert}^{2}={f}_{m}+{f}_{m-1}+\hspace{0.17em}\hspace{0.17em},\hspace{0.17em}\hspace{0.17em}\cdots \hspace{0.17em}\hspace{0.17em},+{f}_{1}.$$Among ℝ real constellation points, the M of a candidate vector that corresponds to the M smallest values of the corresponding f_{m} is chosen and stored, in ascending order, along with all other Ms in the register x_{m}[1, 2, ..., M] ∈ ℝ. Next, the M smallest values producing candidates for f_{m–1} can be obtained using all the combinations of x_{m} ∈ x_{m}[1, 2, ... , M] and x_{m-1} ∈ ℝ. Following this way, one can find an M value for all functions until f_{1} is reached. Finally, the smallest value (among the M values of each register) producing candidates from the m registers is taken as the estimate of the transmitted signal. Now, let us describe how this method can be adopted in LP-SD.
- 3. LP-SD with QRM-MLD
In LP-SD, we are pruning the last layer (k = 1) in the search process. Hence to find x_{1}, assuming it’s a perfect decoding, the values x_{2}, x_{3}, ... , x_{m} obtained in the SD method are considered. QRM-MLD with M = 1, as previously stated, is used for finding the candidate vector (x_{1} ∈ ℝ) that produces the lowest value of function f_{1}. It can be written as$${x}_{1}=\mathrm{arg}{\mathrm{min}}_{{x}_{1}\in \mathbb{R}}{({\tilde{y}}_{1}-{R}_{1,1:m}{x}_{1:m})}^{2}.$$Hence, the transmitted vector can be decoded through a combination of SD and QRM-MLD with the help of the LP approach. These steps are listed in Algorithm 1. Our algorithm follows SE enumeration and terminates a search at the layer k = m − L. Note that the difference between our LP-SD algorithm and the original SD algorithm lies only in lines 20 to 31. To revert back to the original SD algorithm, P_{L} can be changed to P_{1} in line 20.Algorithm 1. LP-SD. Input: ${\tilde{R}}_{SD}$, $\tilde{y}$, and ROutput: x1. k = m; denotes the kth layer being examined.2. i1, i2, … , i_{m} = 0; denotes the lattice point index values.3. ${\tilde{y}}_{m}={\tilde{y}}_{k};$ P_{m+1} = 0; L = 2; denotes layer up to which SD has to be performed4. ${Z}_{m}={\tilde{R}}_{SD}$;5. Compute LB and UB according to (14) and (15).6. Perform SE ordering as given in (18) and obtain $\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}S{E}_{k}=\left\{S{E}_{k,1},S{E}_{k,2},\hspace{0.17em}\mathrm{\hspace{0.17em}...\hspace{0.17em}}\hspace{0.17em},S{E}_{k,N}\right\}$7. N_{k} = Number of candidates present in SE_{k} ; i_{k} = 0;8. i_{k} = i_{k}+1; ${x}_{k}=S{E}_{k,{i}_{k}}$9. while i_{L} ≤ N_{L}10. if i_{k} > N_{k}11. k = k + 1 ; i_{k} = i_{k} + 1 ; ${x}_{k}=S{E}_{k,{i}_{k}}$ ;12. else13. if k > L14. k = k − 1 ;15. ${Z}_{k}=\sqrt{{Z}_{k+1}^{2}-{({\tilde{y}}_{k+1}-{R}_{k+1,k+1:m}{x}_{k+1:m})}^{2}}$;16. ${\tilde{y}}_{k}={\tilde{y}}_{k}-{R}_{k,k+1:m}{x}_{k+1:m}$;17. Repeat the lines 5, 6, 7, and 8;18. ${B}_{k}={\left({\tilde{y}}_{k}-{R}_{k,k:m}{x}_{k:m}\right)}^{2}$ ; ${P}_{k}={P}_{k+1}+{B}_{k}$ ;19. else {k = L}20. if ${P}_{L}<{\tilde{R}}_{SD}$21. ${\tilde{R}}_{SD}={P}_{L}$ ;22. k = k + 1 ; i_{k} = i_{k} + 1 ; x_{k} = SE_{k,ik}23. else {${P}_{L}>{\tilde{R}}_{SD}$}24. save x ; k = k + 1 ; i_{k} = i_{k} + 1 ; x_{k} = SE_{k,ik}25. end {if at line 20}26. end {if at line 13}27. end {if at line 10}28. end {while}29. for i = L−1:1:1 { QRM-MLD with M = 1}30. find x_{i}, such that ${x}_{i}=\mathrm{arg}{\mathrm{min}}_{{x}_{i}\in \mathbb{R}}{\left|{\tilde{y}}_{i}-{R}_{i,i:m}{x}_{i:m}\right|}^{2}$ ;31. end{for at line 36}32. Output xIt is worth noting the following important properties of the LP-SD algorithm:
•The total number of layers to search is reduced in the SD method, which directly reduces the total number of nodes.
•This is a general approach and can be applied with any variant of the original SD. We applied it with PTP-SD[11]and observed that LP-SD achieves complexity reduction at the expense of negligible performance loss.
•No additional arithmetic operations need to be performed, since arithmetic operations involved in QRM-MLD, performed at (21), are approximately equal to the SE ordering of a pruned layer in the SD method.
•Number of layers to be pruned at the bottom can be increased when the number of antennas or modulation order is high by simply changing the value ofLin Algorithm 1.
V. Simulation Results
In this section, we provide simulation results to illustrate the performance of the proposed algorithm. The average search time is computed by performing simulations in MATLAB 7.14 on an Intel Core i5 3.10 GHz with 2 GB RAM PC running Windows 7 starter. In simulations, L^{2}-QAM transmission over MIMO systems is considered with the Rayleigh fading channel, where L represents levels of QAM. The SD algorithm in our paper exploits a depth-first search algorithm with SE enumeration. Hence, we have chosen the initial radius as
R ˜ SD =∞
and will change it whenever a new candidate is found. For each SNR point, we run at least 10,000 channel realizations. MMSE receiver performance was also simulated to show the performance gain achieved by SD. SER, average search time per symbol, and average nodes visited as a function of SNR are the metrics chosen for performance and complexity analysis.Figures 2(a) and 2(b) show the SER performance of LP-SD and the average number of nodes visited by LP-SD, respectively, for the proposed algorithm in the case of an M_{T} = 2, M_{R} = 2 MIMO system with 16 QAM. The influence of LP achieves an approximate reduction in complexity of 42% and 30% at 14 dB and 26 dB SNR point, respectively, with respect to the original SD. Additionally, the number of nodes visited is much less when compared to a PTP-SD algorithm having a pruning probability set equal to 0.2. This reduction in complexity is achieved at the expense of a 2 dB SNR loss with an SER of 10^{−2}. In Fig. 2, LP-PTP-SD denotes that LP is applied to PTP-SD [11].
Performance of LP-SD for M_{T} = 2, M_{R} = 2 MIMO system with 16 QAM: (a) SER and (b) avg. no. of nodes visited.
In Figs. 3(a) and 3(b), we consider a MIMO system employing M_{T} = 4, M_{R} = 4 with 64 QAM for comparing LP-SD, SD, and PTP-SD. The SNR loss is reduced to almost less than 1 dB. In this system configuration, our algorithm (LP-SD) achieves a complexity reduction of almost 42% and 9% over SD and PTP-SD, respectively. Furthermore LP was applied to PTP-SD with pruning probability set equal to 0.4, where it was observed that the average number of nodes visited was reduced by 46% when compared to PTP-SD.
Performance of LP-SD for M_{T} = 4, M_{R} = 4 MIMO system with 64 QAM: (a) SER and (b) avg. no. of nodes visited.
Next, we consider the SER and average number of nodes visited for a MIMO system configuration employing M_{T} = 8, M_{R} = 8 with 16 QAM. Simulation results in Figs. 4(a) and 4(b) show that at 12 dB complexity is reduced by approximately 35% in the proposed method when compared to SD. It is interesting to note from Table 1 that our proposed method significantly reduces levels of complexity. LP-SD is the most effective method for achieving low-complexity SD algorithms, especially at low and medium SNR. Additionally, while applying LP to PTP-SD, complexity is reducing linearly with the increase in the number of antennas.
Reduction of average number of nodes visited by LP-SD.
Comparison reduction achieved by
M_{T} = 2, M_{R} = 2 with 16 QAM at 12 dB
M_{T} = 4, M_{R} = 4 with 64 QAM at 20 dB
M_{T} = 8, M_{R} = 8 with 16 QAM at 12 dB
LP-SD over SD
42%
41%
35%
PTP-SD over SD
15%
35%
57%
LP-SD over PTP-SD
32%
9%
–34%(complexity is higher in LP-SD)
LP-PTP-SD over SD
48%
65%
76%
LP-PTP-SD over PTP-SD
38%
46%
45%
To claim that our algorithm works faster, Figs. 5 and 6 compare the average search time of the LP-SD algorithm with that of other SD algorithms for M_{T} = 2, M_{R} = 2 with 16 QAM and M_{T} = 4, M_{R} = 4 with 64 QAM MIMO systems, which shows that by applying LP to SD algorithms one can accomplish the detection process more quickly.
Average search time per vector for M_{T} = 4, M_{R} = 4 MIMO systems with 64 QAM.
Finally, as stated in the previous section (that is, multiple LP), we look at when two layers are pruned at the bottom, say k = 1 and k = 2 in an M_{T} = 8, M_{R} = 8 with 16 QAM MIMO system. From Figs. 7(a) and 7(b), we observe that double-layer pruning (LP-SD with L = 3) reduces complexity by 49% and 30% at 12 dB when compared to SD and single-layer pruning (LP-SD with L = 2), respectively.
LP-SD for single and double layer pruning of MIMO systems with 16 QAM having antennas of M_{T} = 8, M_{R} = 8: (a) SER comparison and (b) complexity comparison.
VI. Conclusion
In this paper, we proposed a layer-pruning SD algorithm. The detection process search time is reduced by pruning the bottom layer in the search process. Through the technique of LP, complexity is reduced by approximately 35% to 45% for low and medium SNR values. The proposed method, LP-SD, can also be used effectively when there is a greater number of transmit and receive antennas. One of the main advantages is that there are no extra arithmetic operations involved in our proposed method when compared to SD. Our simulation results show that with some negligible performance loss a significant complexity reduction can be achieved in various configurations of MIMO systems. In a 4 × 4 MIMO, our algorithm achieves 29% complexity reduction at the expense of about less than 0.5 dB SNR degradation for an SER of 10^{−2}. Futhermore, LP-SD can be applied to any variant of the original SD to further reduce the computational cost.
BIO
Madurakavi Karthikeyan received his BE degree in electronics and communication engineering from S.K.P Engineering College, Tiruvannamalai, India, in 2008 and his ME degree in communication systems from Mailam Engineering College, Mailam affiliated to Anna University, Tamilnadu, India, in 2011. He is now working toward his PhD at the Department of Electronics and Communication Engineering, Pondicherry Engineering College, Puducherry, India. His current research area includes MIMO receiver design, iterative decoding, and MIMO-OFDM link adaptation.
D. Saraswady received her BTech and MTech degrees from Pondicherry Engineering College, Pondicherry University, Puducherry, India, in 1993 and 1996, respectively, and her PhD degree from Anna University, Tamilnadu, India, in 2006. She is currently serving as a professor at the Department of Electronics and Communication Engineering, Pondicherry Engineering College, Puducherry, India. Her research interests include image processing, cognitive radio networks, wireless ad hoc networks, and enhancement of MIMO systems.
Foschini G.J.
,
Gans M.J.
1998
“On Limits of Wireless Communication in a Fading Environment when Using Multiple Antennas,”
Wireless Pers. Commun.
6
(3)
311 -
335
DOI : 10.1023/A:1008889222784
Fincke U.
,
Pohst M.
1985
“Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis,”
Math. Comput.
44
463 -
471
DOI : 10.1090/S0025-5718-1985-0777278-8
Hassibi B.
,
Vikalo H.
2005
“On the Sphere-Decoding Algorithm I. Expected Complexity,”
IEEE Trans. Signal Proc.
53
(8)
2806 -
2818
DOI : 10.1109/TSP.2005.850352
Gowaikar R.
,
Hassibi B.
“Efficient Statistical Pruning for Maximum Likelihood Decoding,”
Proc. Int. Conf. Acoust., Speech Signal Process.
Apr. 6-10, 2003
5
49 -
52
DOI : 10.1109/ICASSP.2003.1199865
Shim B.
,
Kang I.
2010
“On Further Reduction of Complexity in Tree Pruning Based Sphere Search,”
IEEE Trans. Commun.
58
(2)
417 -
422
DOI : 10.1109/TCOMM.2010.02.080340
Gowaikar R.
,
Hassibi B.
2007
“Statistical Pruning for Near-Maximum Likelihood Decoding,”
IEEE Trans. Signal Process.
55
(6)
2661 -
2675
DOI : 10.1109/TSP.2006.890912
Shim B.
,
Kang I.
2008
“Sphere Decoding with a Probabilistic Tree Pruning,”
IEEE Trans. Signal Process.
56
(10)
4867 -
4878
DOI : 10.1109/TSP.2008.923808
Kim K.J.
,
Yue J.
“Joint Channel Estimation and Data Detection Algorithms for MIMO-OFDM System,”
Asilomar Conf. Signals, Syst. Comput.
CA, USA
2
1857 -
1861
DOI : 10.1109/ACSSC.2002.1197096
Higuchi K.
“Likelihood Function for QRM-MLD Suitablefor Soft-Decision Turbo Decoding and its Performance for OFCDM MIMO Multiplexing in Multipath Fading Channel,”
Personal, Indoor Mobile Radio Commun.
1142 -
1148
DOI : 10.1109/PIMRC.2004.1373877
Damen M.O.
,
Gamel H.
,
Caire G.
2003
“On Maximum-Likelihood Detection and the Search for the Closest Lattice Point,”
IEEE Trans. Inf. Theory
49
(10)
2389 -
2402
DOI : 10.1109/TIT.2003.817444
@article{ HJTODO_2014_v36n4_564}
,title={Performance Analysis of Layer Pruning on Sphere Decoding in MIMO Systems}
,volume={4}
, url={http://dx.doi.org/10.4218/etrij.14.0113.1182}, DOI={10.4218/etrij.14.0113.1182}
, number= {4}
, journal={ETRI Journal}
, publisher={Electronics and Telecommunications Research Institute}
, author={Karthikeyan, Madurakavi
and
Saraswady, D.}
, year={2014}
, month={Jun}
TY - JOUR
T2 - ETRI Journal
AU - Karthikeyan, Madurakavi
AU - Saraswady, D.
SN - 1225-6463
TI - Performance Analysis of Layer Pruning on Sphere Decoding in MIMO Systems
VL - 36
PB - Electronics and Telecommunications Research Institute
DO - 10.4218/etrij.14.0113.1182
PY - 2014
UR - http://dx.doi.org/10.4218/etrij.14.0113.1182
ER -
Karthikeyan, M.
,
&
Saraswady, D.
( 2014).
Performance Analysis of Layer Pruning on Sphere Decoding in MIMO Systems.
ETRI Journal,
36
(4)
Electronics and Telecommunications Research Institute.
doi:10.4218/etrij.14.0113.1182
Karthikeyan, M
,
&
Saraswady, D
2014,
Performance Analysis of Layer Pruning on Sphere Decoding in MIMO Systems,
ETRI Journal,
vol. 4,
no. 4,
Retrieved from http://dx.doi.org/10.4218/etrij.14.0113.1182
[1]
M Karthikeyan
,
and
D Saraswady
,
“Performance Analysis of Layer Pruning on Sphere Decoding in MIMO Systems”,
ETRI Journal,
vol. 4,
no. 4,
Jun
2014.
Karthikeyan, Madurakavi
and
,
Saraswady, D.
and
,
“Performance Analysis of Layer Pruning on Sphere Decoding in MIMO Systems”
ETRI Journal,
4.
4
2014:
Karthikeyan, M
,
Saraswady, D
Performance Analysis of Layer Pruning on Sphere Decoding in MIMO Systems.
ETRI Journal
[Internet].
2014.
Jun ;
4
(4)
Available from http://dx.doi.org/10.4218/etrij.14.0113.1182
Karthikeyan, Madurakavi
,
and
Saraswady, D.
,
“Performance Analysis of Layer Pruning on Sphere Decoding in MIMO Systems.”
ETRI Journal
4
no.4
()
Jun,
2014):
http://dx.doi.org/10.4218/etrij.14.0113.1182