# A Low Complexity Near-Optimal MIMO Antenna Subset Selection Algorithm for Capacity Maximisation

Authors: Ayyem Pillai Vasudevan; R. Sudhakar
Journal: International Journal of Antennas and Propagation
 (2013)

---

## Abstract

Multiple input multiple output (MIMO) wireless systems employ a scheme called antenna subset selection for maximising the data rate or reliability for the prevailing channel conditions with the available or affordable number of radio frequency (RF) chains. In this paper, a low-complexity, and near-optimal performance fast algorithm is formulated and the detailed algorithm statements are stated with the exact complexity involved for capacity-maximising receive-only selection. The complexities of other receive-only selection comparable algorithms are calculated. Complexities have been stated in terms of both complex-complex flops and real-real flops. Significantly, all the algorithms are seen in the perspective of linear increase of capacity with the number of selected antennas up to one less than the total number of receive antennas. It is shown that our algorithm will be a good choice in terms of both performance and complexity for systems, which look for linear increase in capacity with the number of selected antennas up to one less than the total receive antennas. Our algorithm complexity is much less dependent on the number of transmit antennas and is not dependent on the number of selected antennas and it strikes a good tradeoff between performance and speed, which is very important for practical implementations.


---

## Body

## 1. Introduction

Multiple input and multiple output (MIMO) wireless systems can be used for increasing Shannon capacity, or decreasing bit error rate through, respectively, spatial multiplexing or diversity. The more the number of antennas, the more will be the capacity and diversity order. But, regardless of spatial multiplexing or diversity concepts, important difficulty in using a MIMO system is an increased complexity and hence cost due to the need of increased radio frequency (RF) chains, which consist of power amplifiers, low noise amplifiers, downconverters, upconverters, and so forth.This paper focuses on maximising the capacity. Because of the high cost burden involved in RF chains, it is necessary to have less number of RF chains, yet maximise the capacity. This is done by having a larger number of space links at our disposal and selecting the best as many number of links as equal to the number of the RF chains. Selecting the best subset links out of a larger number of links is obviously done by having a larger number of antennas and selecting the best subset of antennas corresponding to the best links. The antenna subset selection can be at the transmit side or at the receive side or at both sides. This paper is concentrating on the selection at the receive side. For a system, which hasMR total receive antennas and MT total transmit antennas, the optimal way to select a subset of LR antennas for maximizing capacity is to carry out determinant calculation [MRLR] times as required by the capacity formula given by Telatar [1] and then arrive at the highest capacity-giving antenna subset. Such an exhaustive search method was used in [2] for diversity reception. Similar argument is applicable for transmit side also. Surely, [MRLR] computations of determinants will become prohibitively large. To solve this complexity problem with minimal loss on the capacity performance, suboptimal algorithms have been developed.Various capacity-based single-sided antenna selection problems have been discussed in the literature [3–13]. In [3], antenna selection was considered at the transmitter for a low rank channel. In this paper, there was no mention of RF chain constraint concept with regard to antenna selection; rather, an optimization criterion was built up for maximizing the capacity and the algorithm of antenna selection was left as a future direction. In [5], an SNR-based criterion was developed for antenna selection in transmitter side for spatial multiplexing systems employing zero forcing-based linear receivers. In [6], the concept of antenna selection with respect to the RF chain was introduced by Molisch et al. In that paper, an analytical bound for the capacity was derived. The system was called hybrid selection MIMO (H-S/MIMO), where in the case of standard diversity, it is called as hybrid selection maximum ratio combining (H-S/MRC). In [7], a selection rule for maximizing the average throughput was given for transmit antenna selection of spatial multiplexing systems. A norm-based antenna selection algorithm for transmit side was suggested by Gore et al. for the Alamouti space time coding system in [8]. In this, antennas of largest Euclidean norms were selected, where it is to be noted that the norm-based algorithm can be very suboptimaly. Norm-based selection can also be used for capacity criterion as suggested in [9]. A high-capacity achieving suboptimal antenna selection algorithm, whose performance in terms of capacity, is very close to that of the optimal one, and whose computational complexity is not that promising, was given by Gorokhov in [10]. This algorithm, which comes under greedy search, started with the full set of antennas and one by one deleted the least capacity contributing antenna. This algorithm also directly dealt with Telatar’s exact capacity expression [1]. This expression is shown as (1) later. The algorithm changed the problem of finding determinant into finding an inverse for the purpose of reducing the computational complexity. However, the inverse lemma used in the algorithm demands a huge number of flops. The complexity of this algorithm was calculated to be O(MT3+MT2MR)+O(MR2MT2)+O(MR2)+O(MT2MR)+O(MT2MR) in [11] for receive side selection. It can be noted that for receive side selection, it involves not only the total number of receive side antennas but also the total transmit antennas. Hence, this algorithm is computationally complex. A follow-up to [10] was made in [11] by Gharavi-Alkhansari and Gershman, who introduced an addition-based greedy sub-optimal algorithm for receive side selection. In that paper, the authors followed the procedure of starting with empty set of antennas and then added one by one maximum capacity contributing antenna. They used the well-known capacity equation given as (1) later, for their algorithm. The authors of [11] also changed the problem of finding determinants to finding inverse as done in [10], but the difference is that computation for finding the inverse was dramatically reduced by using a lemma that finds the inverse by addition and matrix multiplication. A computationally and constructionally simple algorithm was given by Molisch et al. in [12]. This algorithm does not directly deal with (1) and comes under the classification of fast selection sub-optimal algorithms group, where, it is understood that this kind of algorithms does not use directly (1) and surely there will be a small compromise on capacity. Clearly, this algorithm is simple, but there is considerable penalty in terms of capacity. In this, correlation between each pair of the rows, where rows correspond to receive antennas, is found and sequentially the first MR-LR highest correlation antennas are deleted for selecting LR antennas. After getting a particular high correlation antenna pair, the antenna corresponding to the lower norm row is deleted. In [13], an antenna selection algorithm based on Tanimoto similarity was proposed. However, this algorithm is computationally complex as it involves several matrix multiplications. Rate adaptation and single transmit antenna selection were studied in [4].Various articles have been published on the antenna selection at both sides for capacity maximisation. The paper have been on decoupled transmit/receive (Tx/Rx) antenna selection and greedy joint selection. The concept of both side selection was first proposed in [14]. The authors suggested decoupling or separating selections at transmit and receive sides. They suggested optimal search separately on receive antenna and transmit antenna sides reducing the otherwise required calculation of [MRLR][MTLT] determinants to calculation of [MRLR]+[MRLR] determinants without affecting the capacity much. Further in [9], the decoupling concept was suggested in terms of greedy algorithm of [11] at both sides. A greedy joint algorithm called efficient joint transmit and receive antenna selection (EJTRAS) algorithm was proposed for capacity maximisation in [15].Gharavi-Gershman’s receive-side greedy algorithm achieves good capacity performance, but its complexity is clearly a function of the number of transmitting antennas and the number of selected antennas. Their algorithm can be claimed to be of low complexity only for the case of low transmitting antenna number case. The complexity is of the order ofMT2, whereas reduction in MT will surely impose constraint on increase in LR, because if LR>MT, linear increase in capacity is not possible. These issues are brought out quantitatively in Sections 4 and 5. Though the algorithm proposed in [12] is devoid of these constraints, the algorithm is considerably sub-optimal.In this paper, the authors propose for receive side an addition-based fast algorithm, which is considerably superior in performance to algorithm given in [12] with only very small percentage increase in complexity as the simulations and computation calculations show. Our algorithm achieves a capacity, that is, almost equal to greedy algorithm proposed in [11] but, it is computationally independent of number of selected antennas and very importantly, its complexity is much less dependent on the number of transmitting antennas unlike the one in [11]. Our algorithm is devoid of the constraint imposed by greedy algorithm of [11] and is superior in performance to that in [12].The paper has been organized as follows. Section2 gives the theoretical model for capacity-based antenna selection at the receive side. In Section 3, the algorithm is developed, so that it takes better care of norm than that in [12] and the proposed algorithm and its pseudostatements with complexity involved are stated. In Section 4, the computational complexities of all the above mentioned algorithms are discussed with comparison. Section 5 is on simulation considerations, results and discussions. Section 6 gives conclusion. Table 5 gives the complexity break-up of Gharavi et al. algorithm. Table 6 gives the complexity break-up of Molisch et al. algorithm.Notations. All the bold and lower case letters refer to matrix vectors, whereas all the bold and upper case letters refer to matrices. Superscript H refers to Hermitian transpose. The following definitions are applicable for the whole paper.H≜ Channel matrix of MR×MT.MR≜ Number of available receive antennas.MT≜ Number of available transmitting antennas.ρ≜ Symbol energy to noise power ratio.IMR≜ Unit matrix of MR dimension.Hp,:≜pth row vector of H.£R≜ The selected antenna subset.LR≜ The number of selected antennas.H£R,:≜ The sub-channel matrix formed of rows corresponding to selected antennas and all columns of H.λi≜ Eigen values of HHH.θ≜ Angle between two row vectors.〈hi,hj〉≜ Inner product between vectors hi and hj.C≜ Channel capacity of MIMO system.∥hi∥≜ Euclidean norm of vector hi.


## 2. The System Model

The capacity of a MIMO system that usesMR receiving antennas and MT transmitting antennas fed of equal power is given by
(1)C=log2det[IMR+ρMTHHH].This expression can be brought to (2) by using singular value decomposition (SVD). Consider
(2)C=∑i=1rlog[ρMTλi+1]bps/Hz,
where r is the number of nonzero eigen values. Hence, it suggests that C depends on not only the number of independent columns or the number of independent rows but also on eigen value distribution. Simple independence is only a weak requirement as far as capacity is concerned. Capacity can be actually maximized by having not just independent columns or rows but by having orthogonal columns or rows. That is, the eigen values of orthogonal columns or rows will ensure that the capacity is maximized.Antenna selection is an approach, which tries to extract maximum benefit out of the prevailing channel conditions with the number of available or affordable RF chains. If available RF chains are onlyLR, effective receive antennas can be only LR in number. Since only LR antennas are to be selected, (1) will change to
(3)Cselect=log2det[ILR+ρMTH£R,:H£R,:H].The MIMO system with antenna subset selection approach for receive side is depicted in Figure1.Figure 1
A MIMO system with receive side antenna subset selection.


## 3. The Proposed Algorithm

In this section, a new uncorrelation-based algorithm is logically brought for receiver side selection. The expression for the capacity withLR receive antennas can be written with the application of SVD on it as given in (1).In [12], Molisch et al. proposed an algorithm, based on correlation among the rows, for receive side antenna subset selection. The idea was to remove the correlated rows and retain as far as possible maximally uncorrelated or optimally orthogonal rows. Molisch et al. algorithm is simple and of low complexity, but the capacity performance is considerably suboptimal.The reason for the underperformance of Molisch et al. algorithm is that one of the two rows, which have high correlation between them and high individual norm values will get deleted. That is, the norm values are less accounted in that algorithm. But norm values matter as suggested by productHHH in (1). The correlation or nonorthogonality between two rows is measured in terms of the inner product hihjH. The existence of high correlation among any two rows will mean that the inner product among the rows is high.Let us consider two rows,hi and hj of H, where
(4)H=[h1h2h3⋮hMR].The rowsh1,h2,h3,…,hMR are of 1×MT. The inner product between two rows, hi and hj, can be written as
(5)hihjH=∥hi∥∥hj∥cosθ.
That is, correlation = ∥hi∥∥hj∥cosθ, where i=1,2,3,…,MR, j=1,2,3,…,MR. Figure 2 describes the inner product.Figure 2
Interpretation of inner product betweenhj and interpretation of resolution of hj along hi and perpendicular to hi.In this,∥hj∥cosθ is the projection of hj vector on hi vector. Hence, correlation is the norm of vector hi multiplied by the component of hj along hi. The resolution of hj is shown in Figure 2. The uncorrelation between hi and hj will be the norm of hi multiplied by the component perpendicular to hi where the perpendicular is ∥hj∥sinθ. That is, the uncorrelation is given by
(6)uncorrelation=∥hi∥∥hj∥sinθ.Let us defineαhihj≜ correlation between hi and hjβhihj≜ uncorrelation between hi and hj.Then,(7)αhihj2+βhihj2=∥hi∥2∥hj∥2cos2θ+∥hi∥2∥hj∥2sin2θ=∥hi∥2∥hj∥2[cos2θ+sin2θ]=∥hi∥2∥hj∥2.Hence, the square of uncorrelation is given by(8)βhihj2=∥hi∥2∥hj∥2-αhihj2=∥hi∥2∥hj∥2-(hihjH)2.Molisch et al. algorithm was about finding the correlation and deleting the rows corresponding to high correlation, where correlation between two vectors was defined to be the inner product between the two row vectors. But the problem is that high inner products may be due to high values of norms of the vectors and not necessarily due to high values ofcosθ alone, in which case deletion of any one vector will penalize the capacity of the system as the product HHH suggests in (1). But, if the same algorithm is steered to addition concept, such a scenario of deletion of high-norm rows will not happen. Because in addition concept, the uncorrelation between the rows is found and those rows corresponding to high values of uncorrelation are retained. Hence, high norm rows will be retained rather than deleted.We have uncorrelation given by(9)βhihj2=∥hi∥2∥hj∥2-∥hi∥2∥hj∥2cos2θ.In the following, it will be seen that Molisch et al. algorithm does care about correlation aspect well but does not give due care for norm. For this, we take two pairs of rows, in which pair, 1 is more correlated than pair 2 by some percent, but the norm product of pair 1 is more than pair 2 by more percent. Let us consider(i,j) pair of rows and (k,l) pair of rows. Let θ1 be between ith and jth rows and let θ2 be between kth and lth rows. Let square of 〈hi,hj〉 be 1 percent greater than square of 〈hk,hl〉 and let ∥hi∥2∥hj∥2 be 2 percent greater than ∥hk∥2∥hl∥2. This means that the correlation between hi and hj is 1 percent greater than the correlation between hk and hl. Hence, hi and hj are more correlated than hk and hl. We will assume that each of ∥hi∥2 and ∥hj∥2 is greater than both ∥hk∥2 and ∥hl∥2. This is a situation of square norms multiplication of two rows, i and j being greater than square norms multiplication of the other two rows, k and l, whereas the cosθ1 is lower than cosθ2. Under the abovestated assumptions, the uncorrelation becomes
(10)βhihj2=[∥hk∥2∥hl∥2+0.02∥hk∥2∥hl∥2]-∥hk∥2∥hl∥2cos2θ2-0.01∥hk∥2∥hl∥2cos2θ2=[∥hk∥2∥hl∥2-∥hk∥2∥hl∥2cos2θ2]+0.02∥hk∥2∥hl∥2-0.01∥hk∥2∥hl∥2cos2θ2=βhkhl2+[0.02∥hk∥2∥hl∥2βhkhl2+-0.01∥hk∥2∥hl∥2cos2θ2].The bracketed part of (10) will be a +ve value because, 0.02∥hk∥2∥hl∥2 will be greater than 0.01∥hk∥2∥hl∥2cos2θ2. Hence, we see that βhihj2 will be greater than βhkhl2. Hence, if our algorithm is used, we can expect that the higher-norm row of i, j rows, whose individual norms are greater than the individual norms of k, l rows, will be selected. Due to this phenomenon, the proposed algorithm will fetch more capacity than that done by Molisch et al. algorithm and we see in the simulation this is the case. If Molisch et al. algorithm is applied, one among ith and jth rows will be deleted because 〈hi,hj〉 is higher than 〈hk,hl〉. This will cause a reduction in capacity because, among the rows i and j, one may be deleted. The proposed algorithm is stated next, and its statement version with the complexity involved is stated in Table 1. Consider the following.(1)
The channel vectorhi is defined as the ith row of H, with i being an element of the set SR={1,2,…,MR}.(2)
IfLR=MR, conclude £R=SR; otherwise, do the steps 3 to 7.(3)
For alli (with i∈SR), calculate square norm of hi, ∥hi∥2. The square uncorrelation βhihj2 is defined as βhihj2=∥hi∥2∥hj∥2-αhihj2, αhihj2 being the square correlation. The square correlation αhihj2 is defined as αhihj2 = square (|〈hi,hj〉|).(4)
IfLR=1, select i (with i∈SR), that gives the largest ∥hi∥2, and conclude £R={i}; otherwise, do steps 5 to 7.(5)
For alli and j, i>j, compute the square correlation, αhihj2 = square (|〈hi,hj〉|).(6)
For alli and j, i>j, compute the square uncorrelation, βhihj2=∥hi∥2∥hi∥2-αhihj2.(7)
For Loop, Consider the following.
(a)
Choose thei and j (with i, j∈SR, i>j) that give the largest βhihj2. If ∥hi∥2>∥hj∥2, add i to £R, otherwise, and add j to £R.(b)
Deletei (or j) from SR.(c)
Go to Loop untilLR indices are in £R.Table 1
Pseudostatements and complexity details of the  proposed algorithm.
Sl. no.
Algorithm statements
Complex flops required
Real flops required
1
S
R
=
{
1
,
2
,
3
,
…
,
M
R
}
2
M
R
M
T
-
M
R
8
M
R
M
T
-
4
M
R
2
ifLR<MR
3
forj=1 to MR
4
γj2=∥Hj,:∥2
5
end
6
ifLR>1
7
forp=1 to MR
(
2
M
T
+
2
)
(
M
R
2
-
M
R
)
2
(
4
M
T
-
0.5
)
(
M
R
2
-
M
R
)
8
forq=1 to MR
9
ifp>q
10
αp,q=(Hp,:Hq,:H)
11
βp,q=|γp2γq2-αp,q2|
12
end
13
end
14
end
15
forn=1 to LR
16
P,Q=argmaxp,q∈SRβp,q
17
if∥HP,:∥2>∥HQ,:∥2
18
SR=SR-P
19
βP,:=0
20
else
21
SR=SR-Q
22
βQ,:,=0
23
end
24
end
25
else
26
J=argmaxj∈SRγj2
27
SR=SR-J
28
end
29
£
R
=
{
1
,
2
,
,
…
,
M
R
}
-
S
R
30
end


## 4. Complexity Analysis of the Algorithms

In this section, a detailed analysis has been made on the complexity of the proposed Molisch et al., and Gharavi-Gershman algorithms. For complexity analysis, the numbers of multiplications and summations have been accounted. The multiplications and summations are together called as floating point operations, abbreviated as flops. The number of flops demanded by each of the three is taken as the benchmark for comparison of complexities of the algorithms. Firstly, complex-complex flops and then real-real flops are calculated. Each complex-complex multiplication involves four real multiplications and two real additions.N complex-complex additions involve 2N-2 real-real additions.In the case of the proposed algorithm, for single antenna selection, the complexity will be just2MRMT-MR. For more than 1, additionally, the inner product among all the rows and uncorrelation are calculated. Only the lower triangular matrix without the diagonal elements of the correlation matrix is required to be calculated. The correlation matrix is as follows:
(11)(α11α12⋯α1,MR⋮⋱⋮αMR,1αMR,2⋯αMR,MR).Hence, the total complexity of the proposed algorithm isMTMR2+MRMT+MR2-2MR, where it is to be noted that the expression is not a function of LR and hence the total number of multiplications and summations is constant with respect to LR. If LR=MR, no selection is required and hence no multiplications and summations are required. The corresponding real number flops for single antenna selection and more than one antenna selection are, respectively, 8MTMR-4MR and 4MTMR2+4MTMR-0.5MR2-3.5MR.In the case of the algorithm given by Molisch et al. the number of complex-complex flops for selection of both more than and equal to 1 antenna is the same. The number of complex-complex flops is given byMTMR2+MRMT-(1/2)MR2-(1/2)MR, where the complexity is slightly less than ours. It is to be noted that the authors of [12] did not make any provision for reduction of complexity for single antenna case. Also, there was no provision to suspend the selection process when LR=MR.The corresponding real-real flops are4MTMR2+4MTMR-2MR2-2MR for single and more than one antenna selections. In the case of Gharavi-Gershman’s greedy algorithm [11], for calculating B matrix (LR-1) times, 2MT2 complex-complex multiplications and complex-complex summations have to be calculated (LR-1) times. Similarly, a matrix, which consumes 2MT2-MT+4 complex-complex flops for one calculation, has to be calculated (LR-1) times. Further, αj needs to be calculated (LR-1) times. Hence, total flops corresponding to αj is (2MTMR+MR)(LR-1). Hence, the total complexity of Gharavi-Gershman algorithm is 2MRMT-MR+(4MT2-MT+4)(LR-1)+(2MTMR+MR)(LR-1).The corresponding real-real flops are, respectively, given by8MTMR-4MR and 8MTMR-4MR+(8MTMR+14MT2+4MTLR+2MT-4MR+2LR-2)(LR-1) for single antenna and more than one antenna cases. The problem with this algorithm is the computational complexity depends on the number of, not only receive antennas and transmit antennas, but also selected antennas. Also, the dependence on the number of transmit antennas and the number of selected antennas is large in scale. This is to be expected because this algorithm depends on calculating the expression of (1) for selecting the antennas. The complex-complex flops and real-real flops of each of the three algorithms have been, respectively, tabulated as Tables 2 and 3.Table 2
Complexity in complex flops for the proposed and other algorithms.
Sl. no.
The name of algorithm
The complexity in complex flops for more than 1 antenna
For single antenna
1
Proposed
M
T
M
R
2
+
M
R
M
T
+
M
R
2
-
2
M
R
2MRMT-MR
2
Molisch et al. [6]
M
T
M
R
2
+
M
R
M
T
-
1
2
M
R
2
-
1
2
M
R
Same as the previous column
3
Gharavi-Alkhansari and Gershman [11]
2MRMT-MR+(4MT2-MT+4)(LR-1)+(2MTMR+MR)(LR-1)
2
M
R
M
T
-
M
RTable 3
Complexity in real flops for the proposed and other algorithms.
Sl. no.
The name of algorithm
The complexity in real flops  for more than 1 antenna
For  single antenna
1
Proposed
4
M
T
M
R
2
+
4
M
T
M
R
-
0.5
M
R
2
-
3.5
M
R
8
M
T
M
R
-
4
M
R
2
Molisch et al. [6]
4
M
T
M
R
2
+
4
M
T
M
R
-
2
M
R
2
-
2
M
R
Same as the previous column
3
Gharavi-Alkhansari and Gershman [11]
(
16
M
T
M
R
+
14
M
T
2
+
4
M
T
L
R
+
2
M
T
-
8
M
R
+
2
L
R
-
2
)
(
L
R
-
1
)
8
M
T
M
R
-
4
M
RIt can be seen from the complexity analysis discussion as follows.(i)
The Molisch et al. algorithm complexity depends on only the number of physically present receive antennas and the transmit antennas. The dependence onMT is in O(MT). Hence it does not vary with number of selected antennas and the complexity is less dependent on MT.(ii)
The complexity of the proposed algorithm depends on only the number of physically present receive antennas and the transmit antennas. The dependence onMT is in O(MT). Hence, it does not vary with number of selected antennas and the complexity is less dependent on MT. Though the number of multiplications and summations required is very slightly greater than the Molisch et al. algorithm, this very small increase in complexity can be easily disregarded on considering the improvement in performance in terms of capacity given by our algorithm over Molisch et al. algorithm.(iii)
The calculation to be done by the algorithm of Gharavi-Alkhansari and Gershman [11] depends on the number of selected antennas and the number of transmit antennas. The dependence is of O(LR) and O(MT2). Hence, it is more computationally complex. The complexity is clearly a function of MT and LR. This fact clearly imposes a constraint on choice of MT and LR.


## 5. Simulation Considerations and Results

It is known that the capacity of a MIMO system is proportional to themin(MR,MT). In the case of receive-only selection, the capacity will be proportional to min(LR,MT). For LR greater than MT, the capacity improvement will not be on linear order, rather on logarithmic order. Hence, if the antenna selection has to provide a linear increase up to LR equal to one less than MR, it is necessary to keep MT=MR. The simulation carried out in [11] assumed that MT=4 and MR=16. Surely, this imposes a constraint on LR. Such a constraint will impose discomfort in capacity maximisation. Hence, the simulation is carried out for high values of MT, here in our case for MT=16. MR is assumed to be equal to 16.The following plots have been obtained for the proposed Molisch et al. and Gharavi-Gershman algorithms:(i)
the outage capacity in bits/s/Hz versusLR,(ii)
the outage capacity in bits/s/Hz versus SNR in dB for two differentLR, LR = 6 and 8,(iii)
the cumulative probability density versus Instantaneous capacity in bits/s/Hz for two differentLR, LR=6 and 8,(iv)
the number of flops versusLR.Because of huge time involvement, the optimal way of selection simulation for outage capacity versus the number selected antennas plot has been limited toMR=MT=8 case. Also, the random selection plot has been obtained only for this case, because the authors felt that it is clear that random selection is the poorest in terms of capacity performance and hence it is not necessary to regard further. Antenna selection approach of increasing capacity is applicable for slowfading and quasistatic channels. For such kind of channels, outage capacity concept is applicable rather than ergodic capacity concept.For all the simulations, a 2000-channel average has been obtained. Simulation was carried out for two types channels. One of the two was of Rayleigh flat-fading type, where the elements ofH are independent and identically distributed (i.i.d.) complex Gaussian of zero-mean and unit variance; that is, real and imaginary parts of H are of 0.5 variance It is assumed that the channel elements are uncorrelated; that is, there is no correlation at the transmit side antenna elements or receive side antenna elements. The other one type of the two channels for which simulation was carried out was a channel of some amount of correlation. It was assumed that there was no correlation at the base station end and there was correlation at the mobile station. This is based on the fact that there can be feasibility of maintaining sufficient decorrelating antenna separation at the base station, whereas it is difficult to maintain the same at the mobile station. The Kronecker model was used for modeling the channel matrix. The Kronecker model is as follows:
(12)H=Rr1/2HwRt1/2,
where Rr≜ Receive antenna correlation matrix of MR×MR, Rt≜ Transmit antenna correlation matrix of MT×MT, Hw≜ Spatially white channel.In our case,Rt is a unit matrix of MT×MT order. Rr is modelled in an exponential way as discussed in [16]. The model is as follows:
(13)Rr=(1rr4⋯r(MR-1)2r1r⋱⋮r4r1⋱r4⋮⋱⋱⋱rr(MR-1)2⋯r4r1),
where r is the correlation coefficient between the adjacent antennas. It was assumed in our simulation setup that the correlation coefficient was 0.2. In such a case, the correlation between nonadjacent antennas can be neglected and the corresponding terms in the correlation matrix can be set to be zero. Consequently, the receive correlation matrix becomes
(14)Rr=(1r0⋯0r1r⋱00r1⋱0⋮⋱⋱⋱r0⋯0r1),
where r=0.2.It can be concluded from Figure4 that the outage capacity performance with respect to LR of the proposed algorithm is superior to that of Molisch et al. algorithm. It is only slightly lower than the optimal one, and Gharavi-Gershman algorithm. The plots have been obtained for the proposed algorithm, the two other algorithms mentioned earlier, the optimal one, and random one. The norm-based algorithm is not considered, as it is known that it is applicable for only low SNR condition, though the complexity is very low. Figure 3 describes the variation of outage capacity with the number of selected antennas for MT=8, MR=8, and SNR=20 dB. The plots have been obtained for random and optimal selection in addition to the three algorithm-based selections. Figure 4 gives the simulation plot of outage capacity versus number of selected antennas for MT=16, MR=16, and SNR=20 dB. The variation of outage capacity in bits/s/Hz with the number of selected antennas for MT=MR=16 is tabulated as Table 4 for comparison clarity. It can be seen in the table that the capacity of the proposed algorithm is almost equal to that of Gharavi-Gershman algorithm and clearly superior to the original Molisch et al. algorithm. Plot as shown in Figure 5 has been obtained for cumulative probability density versus the instantaneous capacity for two different LR values, 6, and 8 with MT=16 and MR=16. It can be seen from Figure 5 that the capacity distribution of our algorithm is superior to Molisch et al. algorithm and the lowest capacity is only slightly lower than that of Gharavi-Gershman. Plots as shown in Figure 6 have been obtained to see the relation between outage capacity and SNR in dB. Under low SNR condition, the proposed algorithm and Gharavi-Gershman algorithms perform almost at the same level. However Molisch et al. algorithm suffers. This suffering is more for high SNRs.Table 4
Variation of outage capacity withLR for MT=MR=16.
No. of ant.
Capacity by Ghar-Gersh in bps/Hz
Capacity by Molisch in bps/Hz
Capacity by Proposed one in bps/Hz
Increase of Ghar-Gersh real flops over the proposed as      a per cent of the proposed
Complex
Real
1
7.01
7.01
7.01
0.0
0.0
2
13.85
13.25
13.79
−55.5
−56.7
3
20.59
19.55
20.43
−21.9
−25.6
4
27.09
25.76
26.88
11.8
4.7
5
33.44
31.88
33.13
45.5
34.3
6
39.68
37.79
39.25
79.1
63.2
7
45.70
43.63
45.10
112.8
91.4
8
51.54
49.31
50.75
146.4
118.9
9
57.02
54.74
56.16
180.1
145.6
10
62.43
59.90
61.34
213.7
171.6
11
67.48
64.87
66.37
247.4
196.9
12
72.07
69.66
70.87
281.0
221.5
13
76.40
74.10
75.21
314.7
245.4
14
80.12
78.22
79.10
348.3
268.5
15
83.03
81.90
82.28
382.0
290.9
16
85.36
85.36
85.36
—
—Table 5
Complexity break-up of Gharavi-Alkhansari and Gershman algorithm [11].
Sl. no.
Algorithm statements
Complex flops required
Real flops required
1
S
R
=
{
1
,
2
,
3
,
…
,
M
R
}
2
B
=
I
M
T
3
forj=1 to MR
2MRMT-MR
8
M
R
M
T
-
4
M
R
4
αj=∥Hj,:∥2
5
end
6
forn=1 to LR
7
J=argmaxαj
8
j∈SR
9
SR=SR-J
10
Ifn<LR
11
a=1LT/ρ+αJBHJ,:H
(
2
M
T
2
-
M
T
+
4
)
(
L
R
-
1
)
(
6
M
T
2
+
2
M
T
)
(
L
R
-
1
)
12
B=B-aaH
(
2
M
T
2
)
(
L
R
-
1
)
(
8
M
T
2
-
2
)
(
L
R
-
1
)
13
for allj∈SR
(
2
M
T
M
R
+
M
R
)
(
L
R
-
1
)
(
8
M
T
-
4
)
(
M
R
-
L
R
2
)
(
L
R
-
1
)
14
αj=αj-|aHHj,:H|2
15
end
16
end
17
end
18
£
R
=
{
1
,
2
,
3
,
…
,
M
R
}
-
S
RTable 6
Complexity break-up of Molisch et  al. algorithm [6].
Sl. no.
Algorithm statements
Complex flops required
Real flops required
1
S
R
=
{
1
,
2
,
3
,
…
,
M
R
}
2
forj=1 to MR
2
M
R
M
T
-
M
R
8
M
R
M
T
-
4
M
R
3
γj2=∥Hj,:∥2
4
end
5
forp=1 to MR
(
2
M
T
-
1
)
(
M
R
2
-
M
R
)
2
(
4
M
T
-
2
)
(
M
R
2
-
M
R
)
6
forq=1 to MR
7
ifp>q
8
αp,q=Hp,:Hq,:H
9
end
10
end
11
end
12
forn=1 to MR-LR
13
P,Q=argmaxp,q∈SRαp,q
14
if∥HP,:∥2>∥HQ,:∥2
15
SR=SR-Q
16
αQ,:=0
17
else
18
SR=SR-P
19
αP,:=0
20
end
21
end
26
£
R
=
S
RFigure 3
Plots showing the variation of outage capacity with number of selected antennas forMT=MR=8 under i.i.d. channel condition.Figure 4
Plots showing the variation of outage capacity with number of selected antennas forMT=16 and MR=16 under i.i.d. channel condition.Figure 5
Plots showing the variation of cumulative probability density versus instantaneous capacity forMT=16 and MR=16 for LR=6 and 8 under i.i.d. channel condition.Figure 6
Plots showing the variation of outage capacity versus SNR in dB forMT=16, MR=16, and LR=6 and 8 under i.i.d. channel condition.Figure7 shows simulated plots describing variation of outage capacity with LR for MR=MT=16 under correlated channel condition. It may be seen that the capacity reduces in general. It may also be noted that the capacity performance of the proposed algorithm slightly reduces. Since the proposed algorithm falls under uncorrelation concept, the correlation slightly affects the performance. Figure 8 is on variation of cumulative probability density with instantaneous capacity for MR=MT=16 and LR=6 and 8 under correlated channel condition. Figure 9 is on variation of outage capacity with SNR in dB for MR=MT=16 and LR=6 and 8 under correlated channel condition.Figure 7
Plots showing variation of outage capacity with number of selected antennas forMT=16 and MR=16 under correlated condition.Figure 8
Plots showing the variation of cumulative probability density versus instantaneous capacity forMT=16, MR=16 and LR=6 and 8 under correlated.Figure 9
Plots showing the variation of outage capacity versus SNR in dB for,MT=16, MR=16 and LR=6 and 8 under correlated condition.Figure10 is on the number of real-real flops versus the number of selected antennas. As seen in the figure, the number of flops demanded by the proposed algorithm is only very slightly greater than the Molisch et al. algorithm. However, the performance gain is of a significant amount as seen in Figure 3 to Figure 9. As seen in Figure 10, Gharavi-Gershman algorithm complexity increases almost linearly with LR. Columns 5 and 6 of Table 4 show complex-complex and real-real flop increase with LR of Gharavi-Gershman as a percent complexity of the proposed algorithm. Practically, real-real flops matter rather than complex-complex flops. Clearly, our algorithm performs well both in performance and complexity. Our algorithm will be a good choice for systems, which need to have liberty on LR up to MR-1 with linear increase in capacity with regard to increase in LR.Figure 10
Plots showing the variation of real-real flops as a function of the number of selected antennas forMT=16 and 10 and MR=16.


## 6. Conclusion

In this paper, a low complexity algorithm was formulated and the detailed steps of the algorithm were stated with the complexity involvement. The complexities of other existing algorithms were calculated. For all the three algorithms, complex-complex flops and real-real flops were calculated and a comparison was done. The performances of all the algorithms were seen in i.i.d. and correlated channel conditions. Our algorithm is balanced in terms of performance and complexity. Our algorithm will be a good choice for systems which need to have liberty onLR up to MR-1 with linear increase in capacity with regard to increase in LR.



---

*Source: 956756-2013-11-26.xml*