# Controlling Initial and Final Radii to Achieve a Low-Complexity Sphere Decoding Technique in MIMO Channels

Authors: Fatemeh Eshagh Hosseini; Shahriar Shirvani Moghaddam
Journal: International Journal of Antennas and Propagation
 (2012)

---

## Abstract

In order to apply sphere decoding algorithm in multiple-input multiple-output communication systems and to make it feasible for real-time applications, its computational complexity should be decreased. To achieve this goal, this paper provides some useful insights into the effect of initial and the final sphere radii and estimating them effortlessly. It also discusses practical ways of initiating the algorithm properly and terminating it before the normal end of the process as well as the cost of these methods. Besides, a novel algorithm is introduced which utilizes the presented techniques according to a threshold factor which is defined in terms of the number of transmit antennas and the noise variance. Simulation results show that the proposed algorithm offers a desirable performance and reasonable complexity satisfying practical constraints.


---

## Body

## 1. Introduction

The Nondeterministic Polynomial-time hard (NP-hard) complexity of Maximum Likelihood (ML) decoding, the optimal decoder, generally prohibits its use in practical Multiple-Input Multiple-Output (MIMO) systems [1], especially when a large signal constellation and/or many transmit antennas are involved. Some suboptimum detection algorithms, such as Kannan’s algorithm which searches only over restricted parallelograms [2], the KZ algorithm [3] based on the Korkin-Zolotarev-reduced basis, and the Sphere Decoding (SD) algorithm of Fincke and Pohst [4, 5], can perform detection with much lower complexity, but at a performance degradation.SD was first introduced in [6] to perform ML detection, and it achieves reduced complexity by searching for the closest lattice point over the points that lie in a certain sphere around a given vector. Although it significantly reduces the computational complexity of ML, it requires huge amount of computations in MIMO systems. There are several approaches to reduce the complexity of SD algorithm such as the Schnorr-Euchner (SE) enumeration [7], descending probabilistic ordering [8], increasing radius sphere decoder [9], parallel competing branch algorithm [10], and reduced dimension maximum likelihood search [11]. Other approaches trading performance for complexity include the radius scheduling method [12], probabilistic tree pruning algorithm [13], sequential Fano decoders [14], and semidefinite relaxation [15]. The work of [16] proposes the utilization of the SE refinement of the Pohst enumeration in the closest lattice pointsearch. Based on the numerical results, [16] concludes that the SE enumeration is more efficient than the Viterbo-Boutros implementation in [6]. According to the proposed method in [16], an algorithm is presented in [17] and it has been shown that it is robust to the initial choice of the sphere radius. This concept has been further discussed in different pieces of research that try to improve its performance and computational complexity which make it possible for practical real time systems.Various papers have analyzed the complexity of SD such as [18] which shows that the expected complexity of SD the expected number of operations required by the algorithm, C(P,ρ), depends on the both number of transmit antennas, P, and the Signal-to-Noise Ratio (SNR), ρ. It is also shown in [18] that when the SNR is high, the expected number of operations required by the SD, can be approximated by a polynomial function for small P. An exact but complicated expression for the expected number of operations required by the sphere decoder has been obtained in [18]. In [19] by obtaining a lower bound, it is shown that the expected complexity of SD applied to a large class of problems is exponential in P. In this work the complexity of SE-SD algorithm is discussed from a new point of view.Stopping criteria can be used to reduce the complexity of SD, since it results in terminating the decoding process earlier and thus prevents a huge amount of extra calculations. Some researchers have worked on these criteria for some special scenarios. This paper also discusses the convergence radius and proposes a new stopping criterion.SD searches a lattice through a given set of points that is bounded by the search sphere with the received point as center. Therefore, the method requires determining an initial search radius,C0. The concept of choosing a suitable C0 plays a crucial role in finding the nearest lattice point in a sphere. The initial radius should not only be small enough to contain at least one lattice point but also big enough to have a practical enumeration complexity of finding closest point among containing lattice points. Even though it is claimed that SE-SD is less sensitive to initial radius than the original SD, [17] shows that the complexity of SE-SD is still controlled byC0. To the best of our knowledge, there are no general guidelines for choosing appropriateC0. This paper focuses on the suitableC0 and discusses the way of finding it easily, which is applicable to the complexity-limited wireless communication systems. This paper also demonstrates that the initial radius can affect not only the computational complexity but also BER of SE-SD algorithm significantly.In this paper,ℤ,ℝ,and ℂare the sets of integer, real, and complex numbers, respectively. 𝒞𝒩(·) denotes circularly symmetric complex Normal distribution.In the assumed MIMO system,X̃(x̃1,x̃2,…,x̃P)∈ℂP is the complex transmitted vector of dimensionP, whose elements are members of a squared M-dimension Quadrature Amplitude Modulation (M-QAM) constellation. It is assumed that the channel coefficients matrix, H̃∈ℂP×Q, which is comprised of i.i.d 𝒞𝒩(0,1)entries, can be estimated accurately at the receiver. The noise vector comprised of i.i.d 𝒞𝒩(0,2σ2) entries is presented byÑ∈ℂQ, where σ2=QE̅S10-0.1SNR/2log2M,and E̅Sis the average signal energy of the constellation. A symbol, defined asS:x1…xP, is transmitted over Pantennas, and Ỹ∈ℂQ, which is given byỸ=H̃X̃+Ñ, is received.To obtain a lattice representation of this multiple antenna system, the complex matrix equation is transformed into the real matrix equation as(1)Y=HX+N,
whereYandN, similar to X are obtained through X=[real(X̃T)Timag(X̃T)T] and H̃ is transformed to(2)H=[real(H̃)-imag(H̃)imag(H̃)real(H̃)]∈Rp×q,
where for easier notation, p=2Pand q=2Q.The reminder of this paper is organized as follows. Section2 describes sphere decoding and SE-SD algorithm, briefly. The initial radius and complexity of the algorithm is discussed through simulation results over a wide range of SNRs and channel sizes in Section 3. Section 4 goes into the ideas of stopping criteria for the algorithm. In Section 5 a new low-complexity algorithm is introduced. Finally, Section 6 draws the conclusion.


## 2. Sphere Decoding

A finite lattice can be defined asΛ={HX:X∈ℤp} where His the generator matrix of the lattice andXcontains the coordinates of lattice points. The ML estimates XML that minimizes the Euclidean distance betweenY and XML, as follows:(3)XML=argmin⁡X∈ZΩp⁡‖Y-HX‖2,
where ∥·∥2represents the vector norm and ℤΩp={a+jb|a,b∈{-M+1,-M+3,…,M-3,M-1} represents the set of points of the M-QAM constellation.As mentioned earlier, SD searches the lattice through a given set of points bounded by a sphere with the received point as center and a specific initial radius. Whenever a point is found inside the sphere, the radius is reduced to the value of the distance between the new and the received point. Under assumption ofp=q, the channel matrix can be transformed into H=QR by performing QR-decomposition. Ris an upper triangular matrix, and Qis an orthogonal matrix. Therefore, the ML problem will be simplified to find the lattice point that satisfies the following condition:(4)C02≥‖Y´-RX‖2,
where Y´=Q*Y and (·)*represents Hermitian matrix transposition. The inequality can be rewritten and then expanded as(5)C02≥∑i=1p(y´i-∑j=ipri,jxj)2=(y´p-rp,pxp)2+(y´p-1-rp-1,pxp-rp-1,p-1xp-1)2+⋯,
where ri,jdenotes the (i,j)entry ofR. The previous inequality results inpdifferent inequalities. By taking advantage of the upper triangular property of R the first term of right-hand side of (5) depends only onxp and thus it belongs to the following interval:(6)⌈-C0+y´prp,p⌉≤xp≤⌊C0+y´prp,p⌋,
where⌈·⌉ and ⌊·⌋ denote rounding to the nearest larger and smaller element in the set of numbers that spans the lattice, respectively. The intervals for xp-1,xp-2,…,x1 are found in a similar fashion, in which xi is a function of onlyj, j=i,…,p. Generally speaking, all possible candidates for xishould be searched within a sphere with radius C0 and dimension p-i+1.The first candidate forxi, namely, x̂i, is:(7)x̂i=⌊1ri,i(yi´-∑j=i+1pri,jxj)⌉.By SE enumeration, the candidates are spanned in a zigzag order, starting from the midpoint. Hence, at each leveli, the SE enumeration will produce this sequence of candidates for xi: {xı̂,xı̂+1,xı̂-1,xı̂+2,xı̂-2,…}if yı´-∑j=ı+1prı,jxj-rı,ıxı̂<0 and otherwise {xı̂,xı̂-1,xı̂+1,xı̂-2,xı̂+2,…}.A full search can be depicted as a search tree, like Figure1, which its root is the Pth entries of the possible symbol and each node in the ith level shows one of the possible values for the ith entry of the symbol. The search starts from the root down to the 1st level (leaf node), where at the ith level, all possible (i-1) entries are found so that the symbol lies in the sphere. When the search reaches the leaf node, all the entries of the symbol are discovered. Therefore, each path through the tree corresponds to a possible symbol. As a result, SD can be viewed as a pruning algorithm on this tree from which, based on violation of the constraint given by (4), a branch can be removed at any level.Figure 1
The possible searching paths in a tree forP=3 and 4—QAM.The work of [17] proposed an algorithm with 6 recursive steps to implement SE-SD algorithm. After initialization, leading to start from the highest level of the tree and setC0, the algorithm begins with step 2, by offering the first candidate for the root of the tree. The testing node at each level is offered by steps 2 and 6 through SE enumeration. By using the lattice boundary (maximum and minimum of ℤΩp) in steps 2 and 6, the algorithm works with only the finite square M-QAM constellation. Step 3 examines the constraint given by (5) which may lead to two cases.(1)
If the candidate is valid and a leaf node is reached(i=1), the symbol is recorded as the ML solution, the radius is updated in step 5, and the algorithm restarts from (i=2). But if the valid candidate is found in other levels, the search proceeds in a lower level.(2)
If the candidate is not valid, the algorithm will go to step 4. If the algorithm is in the top level, it means that there is no valid symbol in the sphere. Thus, the algorithm terminates. Otherwise, the algorithm will go up toi+1 and the next candidate of that level will be tested.This paper uses the SE-SD algorithm introduced in [20] which is the modified version of the proposed algorithm in [17] which does not consider any point outside the finite lattice through lattice boundary awareness. This algorithm is preferred because of the lower complexity without any performance degradation.


## 3. Initial Radius of SE-SD Algorithm

Several approaches have been proposed to find an appropriate initial radius. Because of the advantages of the Schnorr-Euchner enumeration, the conventional methods choose the positive infinity as the initial radius. Obviously, this approach avoids declaring an empty sphere. It is also clear that the first point found withC0=∞ corresponds to the Babai point [16]. Thus, a more suitable choice for C0 is to use the distance between the Babai point andY, since this radius guarantees the existence of at least one lattice point inside the sphere. Generally, it is not clear whether this choice of initial radius leads to too many lattice points lying inside the sphere [18]. In [21] through some examples it is shown that this sphere contains at least one point, if the radius is computed exactly. However, in practice, due to rounding errors introduced by floating-point computation, this radius cannot be calculated exactly. It offers an upper bound for the computational error ofC0 and defines C0+2qμ(q∥H∥2∥X∥2) as the initial radius, where μ is the unit of round-off. The work of [22] mentions that this method is useful when the noise variance is relatively small. The work of [23] proposes a method that utilizes the result of QR decomposition and reordering of Hto obtain Babai point and defines the initial radius as the distance between the received signal and the lattice point mapped by the suboptimal solution.Another case forC0is the covering radius of the lattice, defined to be the smallest radius of spheres centered at the lattice points that covers the entire space [24]. This is clearly the smallest radius that guarantees the existence of a point inside the sphere for anyY. The problem with this choice of C0is that determining the covering radius for a given lattice is itself NP-hard [25].Some works consider a small fixed number asC0 for all cases, which is increased if no lattice point is found in the sphere. The work of [26] sets the initial radius to the distance between the lattice point mapped by Minimum Mean Square Error (MMSE) solution and the received signal. In general, the approaches that use the suboptimal solutions to findC0 contribute to higher complexity.A useful approach is to chooseC0 according to the noise distribution, so (3) can be helpful to determine the desiredC0. ∥Y-HX∥2=∥N∥2 is a Chi-square random variable with q degrees of freedom. Therefore, a radius may be chosen to be a scaled variance of the noise [18]:(8)C02=Kqσ2.In such a way, a lattice point can be found inside the sphere with a high probability:(9)∫00.5kqλ0.5q-1Γ(0.5q)e-λdλ=1-ϵ,
where the integrand is the probability density function of the Chi-square random variable withq degrees of freedom, and ϵ is set to a value close to 1. If the point is not found, the probability will be increased and a newC0 is calculated; consequently, the searching will be restarted considering the new radius.It is important to note that the radius is chosen based on the statistics of the noise and notH. Making the choice based on H quickly leads us to NP hard problems (such as determining the covering radius). Moreover, as noted in [1], selection of the radius based on the noise has a beneficial effect on the computational complexity. The work of [27] proposes an empirical definition for Kin special situations (64 and 16-QAM) in a small SNR range.To investigate the behavior of the algorithm, we find the average number of flops, a measure for the complexity, and Bit Error Rate (BER) of the SE-SD algorithm for variousρ, M and p through computer simulations. Our experimental setup corresponds to the transmission of M-QAM constellations over a multiple antenna flat Rayleigh fading channel, which is reasonable for many communication problems. The channel matrixH, changes randomly after transmitting 100 symbols. In order to plot BER or complexity versus initial radius for certain ρ, M, and p, a set of 100 initial radii are examined, and 108 random symbols per any particular C0, are tested. Note that only the flops of the search process are counted without considering the cost of QR decomposition. In practice, at least one lattice point should be found by the algorithm, and if C0 does not contain any point the initial radius is multiplied by 1.5and the algorithm is restarted.The work of [17] investigates the effect of C0 on the average complexity of SE-SD algorithm for a 16-QAM constellation at a range of ρ=15 to 25 dB and it is shown that forρ>20 dB, the complexity is less insensitive to the initial radius than the original SD. However, the relationship between the computational complexity and the initial radius does not discussed in [17].Although (9) implies that the probability of finding lattice point inside the sphere changes as initial radius changes, there are no known paper on the effect of C0 on the performance of SE-SD for finite lattices. Figure 2 illustrates the significant effect of initial radius on the performance of the algorithm. It shows BER as a function of initial radius for P=4 and M=64when ρ=18.4, 21.46, and 24dB (σ2 = 0.203, 0.1, and 0.056). A particularC0that leads to the lowest BER calling “the best performance initial radius”,C0BP, can be seen in each subfigure of Figure 2. For instance, whenρ=18.4dB, BER of C0=C0BP is 21% less than that of C0=70. The average Babai Radius is depicted by a line in Figure 2, and this figure shows thatC0BP is close to Cba but not exactly equal to it.BER versus initial radius of SE-SD algorithm whenP=4,M=64. (a) ρ=18.4dB, (b) ρ=21.46dB, (c) ρ=24dB.
(a)(b)(c)A huge number of figures that show the complexity versusC0have been obtained from simulations when P=4,M=64 and ρ is choosing from 7.5dB to 30dB with the step of 0.5dB, which is the typical SNR range for wireless communication applications. In this paper only 6 examples of these simulation results are depicted in Figures 3 and 4 due to the limited space. These figures depict the complexity of SE-SD algorithm as a function of initial radius for ρ=7.5,11.4,13.3,18.4,24, and 30dB. All of the simulated curves follow a similar pattern and can be fitted to a rational function of two fourth-order polynomials [28].The average number of flops versus initial radius of SE-SD algorithm whenP=4, M=64. (a) σ2=2.49(ρ=7.5dB), (b) σ2=1.02(ρ=11.4dB), (c) σ2=0.65(ρ=13.3dB).
(a)(b)(c)The average number of flops versus initial radius of SE-SD algorithm whenP=4 and  M=64. (a) σ2=0.203(ρ=18.4dB), (b) σ2=0.056(ρ=24dB), and (c) σ2=0.014(ρ=30dB).
(a)(b)(c)For anyC0 less thanC0LC, as the initial radius decreases, the complexity soars. Because the smaller spheres force the algorithm to restart several times, this contributes to huge computational complexity. The curves show that the complexity gets its lowest value whenC0 is nearCba. This C0can be defined as the “lowest complexity initial radius”, C0LC. There is three cases related to ρ and C0.(1)
The curves related to lowρ (Figures 3(a) and 3(b)) are smoother, and for any C0 bigger than Cba the complexity seems almost constant, so, in this case a big initial radius should be chosen to have low complexity however, it should be small enough (second-order value) not to degrade the performance noticeably (noting Figure 2). For example C0=60 is suitable for the case of P=4, M=64, and ρ=10to 5dB.(2)
Moderateρ results can be seen in Figures 4(a) and 3(c). In this curve the lowest complexity is obtained whenC0 is aroundCba and it grows considerably whenC0increases. For instance, the complexity grows about 40% as C0=70 is chosen for ρ=11.4dB. Therefore, in this case the most suitable C0should be chosen slightly less thanCba.(3)
Highρ makes the complexity of the algorithm less sensitive to any C0 (greater thanCba), as Figures 4(b) and 4(c) illustrate. Although the raise in the complexity can be neglected for highC0, the performance degradation is significant. It comes to the conclusion that an initial radius greater than Cba and less than 1 can be acceptable in this situation to comprise between the performance and the complexity.From Figures3 and 4 it is obvious that decreasing of ρleads to decline in C0LCand also smoothing the curves which supports the theory in [18] that recommends choosing C0 according to the noise variance.Simulation results that depict the average complexity and BER of SE-SD algorithm as a function ofC0when P=4, σ2=0.203, and M = 4, 16, 64, and 128 show that not only C0LC but also C0BP does not change as the constellation’s size grows. It comes to the conclusion that the size of constellation does not affect the performance and the complexity of SE-SD.While an approach is to chooseCba as the initial radius [16, 17], Figures 2, 3, and 4 show that neither C0LCnor C0BP is exactly equal toCba. Using Cba as the initial radius in some practical scenarios causes a noticeable increase in BER and the complexity due to the rounding problem. In addition, calculating Cba costs extra complexity which cannot be negligible in some scenarios.Figure5 shows Cba and the proper C0 (which is obtained from a comprise between performance and complexity) of SE-SD algorithm as a function ofnumber of transmit antennas when M=64 andσ2 = 0.65,0.203, and 0.05. As it can be seen from Figures 5(b) and 5(c), for a low σ2 scenario in spite ofCba, the number of transmit antennas does not affect the suitable C0and it remains almost constant for any number of antennas. Thus, in this case, finding suitable C0 for small problem size (low P) concludes to solving the initial radius problem for the big one (high P). Since the complexity of calculatingCba for scenarios with small number of antennas is considerably less than the big one, the cost of finding suitable initial radius reduces significantly.Cf, the proper C0, and Cba of SE-SD versus the number of antennas for 64QAM. (a) σ2=0.65, (b) σ2=0.203, and (c) σ2=0.05.
(a)(b)(c)However, as it can be seen from Figure5(a), high σ2 scenario needs calculating of Babai radius to use as initial radius. Because of the rounding problem for any scenarios withσ2>0.5, the suitable C0is approximately 8% smaller thanCba.


## 4. Stopping Criteria for SE-SD Algorithm

Stopping criterion is a potential mean for saving computational complexity in iterative algorithms like SE-SD. The work of [29] suggests that if an enumerated lattice point is found to be at a distance less than half the length of shortest lattice vector (packing radius) from Y, it is clearly a nearest lattice point and thus the enumeration process can be terminated right away. The work of [29] utilizes a lower bound on the packing radius as a stopping test. The work of [30] introduces a parameter, Vth, based on the target symbol error rate and σ2, and the proposed probabilistic search stops when x̂ is within it.The idea of [31] is to first run a lattice reduction-aided SIC detector. If this results in a valid vector, with all elements within the symbol alphabet, the algorithm stops. Otherwise, it proceeds by running the sphere decoder.It was mentioned that when the algorithm finds a symbol in the sphere, calculates a new radius for the sphere and when the algorithm reaches its convergence radius, it still tries to find a symbol inside the new sphere, but it does not succeed, because there is no one. Of course, the attempts to find a new symbol after reaching the convergence radius cause significant extra calculations. Thus, if SE-SD algorithm terminates as soon as it reaches the convergence radius, the huge amount of unnecessary computations can be prevented. Consequently, the complexity of the algorithm will be reduced considerably.Finding the convergence radius is itself really complicated. Through the computer simulations of SE-SD for each scenario we recorded the averageFinal Radius,Cf, the radius of the last sphere in which the algorithm cannot find any lattice point after a huge amount of calculations. Figure 5 showsCf, Cba, and the proper C0 of SE-SD algorithm as a function ofthe number of transmit antennas when M=64andσ2 = 0.65, 0.203, and 0.05. It seems that the final radius, similar to Babai radius, increases as the number of antennas grows. This growth in lowσ2 scenarios is negligible (Figures 5(b) and 5(c)) but for high σ2 it cannot be ignored (Figure 5(a)). The distance between the final radius and Babai radius for high σ2 seems to be a function of the number of antennas and the noise variance. When suitable C0is chosen 8% less than Cba for high σ2 is the final radius empirically found to be approximately equal to(10)Cf=Cba-σ2×P3.
So, in this case calculating Cba results in not only a proper initial radius but also the final one.When a new sphere radius is calculated in step 5 of the algorithm, it should be compared to the estimatedCf, and when it is found to be less than Cf, the SE-SD algorithm terminates to avoid extra useless calculations after reaching the convergence radius. This technique can be defined as Early terminated SE-SD.Although the problem of finding suitableCf can be solved easily usingCbaand (10), yet there is a question about the cost of calculatingCba. To find out the complexity growth, we take into account the complexity of three types of performing SE-SD:SE-SD withC0=Cba,SE-SD whichC0 is chosen through previous section’s recommendation, namely, proposed initiated SE-SD (PSE-SD),early terminated PSE-SD (EPSE-SD).Table1 indicates the percentage reduction in the complexity of these three types of SE-SD in comparison with the case of C0 equal to a certain rough value like 20, when M=64, P=20,12,10,6,4, and σ2=0.203. The negative number in the table means the increasing in the complexity.Table 1
Reduction in complexity corresponding the number of transmit antennas.
Number of transmit antennasSE-SD complexity reduction (%) whenC0=CbaPSE-SD complexity reduction (%)EPSE-SD complexity reduction (%)203040581215213310916276−5−244−13−71According to Table1 if P is greater than 10, the complexity declines by at least 9% viaC0=Cba compared to the case thatC0=20. The reduction soars to at least 16% using PSE-SD. In addition, utilization of EPSE-SD results in a substantial decrease (more than27%) in the complexity. Therefore, the slight additional complexity entailed by calculating Cbaleads to significant reduction in the total complexity of SE-SD.However, ifP<10, the number of flops of calculating Cba is comparable to the overall SE-SD complexity and the complexity reduction of EPSE-SD seems to be negligible. For example, Figure 4(a) indicates that for the case of σ2=0.203 and P=4<10 the average number of flops for decoding a burst of 100 symbols is around48000, and so, 14600 flops of calculating Cba is comparable to the SE-SD complexity.Table2 demonstrates a comparison between the three techniques, SE-SD withC0=Cba, PSE-SD and EPSE-SD, when M=64, P=4,and σ2=2.49,1.14,1.02,0.203, and 0.056. In this table the percentage reduction of the complexity of the three types of SE-SD reflects the apparent discrepancy betweenσ2≤1.02, and σ2>1.02. On one hand, EPSE-SD causes a significant fall in complexity when  σ2≤1.02; on the other hand, calculating Cba increases the number of flops of PSE-SD dramatically when σ2>1.02.Table 2
Reduction in complexity corresponding noise variance.
Noise varianceSE-SD Complexity reduction (%) whenC0=CbaPSE-SD complexity reduction (%)EPSE-SD complexity reduction (%)2.492030521.1438221.02−23130.203−13−710.056−32−30−27In fact the noticeable beneficial effect of allocatingCf as a criterion for early termination of SE-SD is evident in the case of high noise variance or big problem size. For instance the complexity declines by 52% in the case of M=64, P=4, and σ2=2.49.


## 5. Proposed TF-Based Algorithm

As a result of the presented discussion, EPSE-SD seems not to be the efficient decoding algorithm for some cases; a criterion should be introduced to help us to choose one of the initiation and termination techniques of SE-SD. We propose the TF-based algorithm performing different decoding techniques via a Threshold Factor (TF). TF of this algorithm is defined as a function ofP and σ2:(11)TF≜10×P×(σ2)2.There are four major cases according to the value of TF. First, when TF is greater than 300, the TF-based algorithm only performs SIC decoding. For instance, ifP=4 and σ2 is greater than 2.74, TF>300, SE-SD leads to a huge amount of computational complexity, and its performance is more or less identical to SIC decoding.In the second case when TF is between 3.2 and 300, the algorithm initially performs SIC decoding to findCba and consequently calculates suitable C0 and Cf usingCba and then performs SE-SD algorithm. According to Tables 1 and 2, if P≥10 andσ2=0.204, or in a case of P=4 and0.283≤σ2<2.74, so 3.2≤TF<300, the PESE-SD can make an acceptable performance with a reasonable complexity.In the third case, when TF is between 0.4 and3.2, the algorithm only performs SE-SD withC0=1. Because the complexity of finding Cba is comparable to SE-SD, it is not logical to use either PSE-SD or EPSE-SD. Based on Figures 2 and 4, when P=4 and 0.1≤σ2<0.283, 0.4<TF<3.2, a certain C0 equal to 1 can make a sensible complexity without any performance degradation.Finally, the fourth case is when TF is less than 0.4 and the algorithm performs SE-SD withC0=0.5. In this case SE-SD can find the closest lattice point quickly which costs a quiet small number of flops. The proposed algorithm can be summarized as Algorithm 1.Algorithm 1:TF-Based algorithm.
(1) Calculate TF(2) IfTF>300 Then Do SIC algorithm(3) If3.2<TF<300Then Do SIC decoding,CalculateCba,Cf. Do EPSE-SD(4) If0.4<TF<3.2 Then let C0=1. Do SE-SD(5) IfTF<0.4Then let C0=0.5. Do SE-SD


## 6. Conclusion

In order to make SE-SD feasible for real applications, some techniques should be utilized to decrease the complexity of this algorithm. We presented new methods of initiation and termination of the SE-SD algorithm that can contribute to achieve the goal of having a reasonable complexity.We showed that for a high number of transmit antennas, using Babai distance as initial radius leads to considerable performance degradation due to the big problem size. The suitable initial sphere radius which results in low complexity and desirable performance in the range ofρ which covers wireless communication applications can be found by the our proposed method. Moreover, this paper offers a technique to estimate the final radius to which SE-SD converges. Utilizing the estimated final radius as a criterion for early terminating of SE-SD is a way of controlling the complexity of the algorithm because it avoids considerable amount of unnecessary calculations. Simulation results show that employing proposed initiation and early termination of SE-SD causes a significant reduction in the complexity. For example, when M=64, P=4, and ρ=7.5dB, the technique leads to reduction in the complexity by 52%.To estimate the initial radius and the final one, Babai distance should be found through SIC decoding. Therefore, the presented technique sounds not to be useful for some cases in which the extra complexity of SIC decoding is comparable to that of SE-SD process. This investigation proposed an algorithm that utilizes different techniques according to a threshold factor defined in terms of the number of transmit antennas and noise variance. Using threshold factor, the novel algorithm offers a reasonable complexity without any performance degradation.



---

*Source: 192964-2012-03-06.xml*