1 Capacity Bounds of Finite Dimensional CDMA Systems with Fading/Near-Far Effects and Power Control P. Kabir, Student Member, IEEE, M. H. Shafinia, Student Member, IEEE, F. Marvasti, Senior Member, IEEE , P. Pad, Student Member, IEEE Abstract 2 1 This paper deals with fading and/or near-far effects with or without power control on the evaluation of the 0 2 sum capacity of finite dimensional Code Division Multiple Access (CDMA) systems for binary and finite non- binary inputs and signature matrices. Important results of this paper are that the knowledge of the received power n variationsdue to input power differences, fading and/or near-far effects can significantly improve the sum capacity. a J Also traditional power controls can not improve the sum capacity; for the asymptotic case, any type of power 0 control on the near-far effects is equivalent to the case without any power control. Moreover, for the asymptotic 1 case,wehavedevelopedamethodthatdeterminesboundsforthefading/near-farsumcapacitywithimperfectpower estimation from the actualsum capacity of a CDMA system with perfectpower estimation. To show the powerand ] T utility of the results, a number of sum capacity bounds for special cases are numerically evaluated. I . s c I. INTRODUCTION [ 2 In a CDMA system, each user is assigned a signature vector to transmit its data through a common channel. v 1 4 Different users have different distances from the receiver; thus, the received signals do not have the same power 8 5 6. at the receiver end. Flat fading due to multi-path can also create power variations at the receiver end for different 0 1 users. In the present paper, we develop a common analytical tool for the evaluation of the sum capacity bounds 1 : v i for finite CDMA systems with fading/near-far effects with/without power control. In addition, we evaluate the X r a asymptotic sum capacity bounds with imperfect power estimation from the sum capacity evaluations of Tanaka [1] and Guo-Verdu [2] with perfect power estimation for finite CDMA systems. In the absence of near-far effects, the channel capacity has been evaluated for real and complex inputs [3] and [4]. However, for overloaded CDMA systems with finite input alphabets, only lower and upper bounds have been evaluated [5]–[8]; a recent review of these papers is published in [9]. Asymptotic results for finite input sum capacity have been derived by [1] and [2]. These asymptotic results are based on replica theory that has been Manuscript received P. Kabir, M. H. Shafinia, F. Marvasti and P. Pad are affiliated with ACRI and Electrical Engineering Department, Sharif University of Technology, Tehran, Iran. 2 proven rigorously for special cases [10]. The asymptotic results discussed in [2] also cover the near-far effects with perfect power estimation. ForfinitedimensionalCDMAsystems,wederiveboundsforfading/near-fareffectswithorwithoutpowercontrol. In this derivation, we will show that if we have perfect power estimation at the receiver end, the lower bound for sum capacity is actually increased. This implies that even in the absence of fading/near-far effects, if we allocate random powers to different users, we can actually improve the sum capacity. Also we will show that the traditional power control technique is surprisingly worse than no power control. Also, we shall see that water filling power control seems to be optimum for even binary input systems, although water filling power control is optimal for only Gaussian input signals [11], [12]. For the asymptotic case, we derive bounds for the near-far CDMA systems in the absence of power estimation. Essentially, we derive a method that can estimate the sum capacity when perfect power estimation is not available. This method depends on the sum capacity evaluations of Tanaka [1] and Guo-Verdu [2] in the absence of near-far effects. At the transmitter side, there are several strategies to allocate powers to different users. In power control, the strategy is to compensate for the fading channelor the near-far effects. This type of power control tries to make the received powers from different users to be equal. This is not an optimum power policy. References [11], [12] have shownthat for Gaussianreal inputs, optimal powercontrol is a generalizationof water filling concept.Optimization of power control given a fading/near-far scenario for binary or finite size input alphabets are parts of future work. However, based on our numerical results, to be discussed later, water filling and even a random power allocation can increase the sum capacity. Therestof thepaperis organizedas follows:In SectionII, somemathematicalpreliminaries are given.In Section III, we will derive lower and upper bounds for the sum channel capacity for finite CDMA systems. In Section IV, we will develop lower and upper bounds for asymptotic CDMA systems with imperfect power estimation. Numerical computations of these bounds for special cases are in Section V. The conclusion and future works are covered in Section VI. 3 II. PRELIMINARIES In a DS-CDMA system, each user is assigned a signature vector. Each user multiplies its signature by its data, possibly with different powers, and transmits it through a common channel. All vectors are added up together in the channeland the resultant vector embeddedin noise is received.In such a system, without perfect powercontrol, the assumption of receiving equal powers from all transmitters is no longer valid. Thus, in a synchronous CDMA system with n users and m chips in the presence of noise and near-far effects, the channel model is n 1 Y = A C M X +N = i i i i √m i=1 X 1 1 ACMX +N = AC(G+E)X +N, (1) √m √m whereA = [A A ] m n isthesignaturematrixand is thesetofsignaturealphabets.Also,MandC,are 1 n × |···| ∈ S S diagonal matrices corresponding to channel gain/loss and power allocation, respectively. X = [X , ,X ]T n 1 n ··· ∈ I is the user data vector, where is the set of input alphabets. Here, and can be arbitrary binary, non-binary, I I S real or complex numbers. In addition, N = [N , ,N ]T is i.i.d. Gaussian noise vector in which each entry has 1 m ··· a variance of σ2. Also M = G +E , where G is the estimation of the near-far or fading at the receiver and E i i i i i is the estimation error. We assume that E , G and C are i.i.d. random variables with distribution (0,ρ2), g, i i i N and c, respectively. We define the Channel Estimation Ratio (CER) of a CDMA system as E Re(G )2 i CER = 10log , (2) dB 10 Var[Re(E )] (cid:2) i (cid:3) where Re() is the real part of a complex function. CER is the ratio of the estimated channel power divided by the · power estimation error. Define (m,n, , ,η,g,c,ρ) to be the sumcapacity overall randommatrices A with independentcomponents π C I S of distribution π(), where π() is the distribution on . The normalized Signal to Noise Ratio (SNR), η, is defined · · S 4 σ2(σ2+µ2)(σ2+µ2) by η = p π π c c , where µ and σ are the mean and the variance of the random variables. Also, we assume 2σ2 that µ = 0, where p() is the probability distribution function on . p · I III. BOUNDS FOR THE FINITE DIMENSIONAL CDMA SYSTEM WITH PERFECT POWER ESTIMATION In this section, we will derive lower and upper bounds for capacity of finite dimensional CDMA systems with fading or near-far effects. Throughout this section we assume that perfect power estimation is available, i.e., ρ = 0. First, we propose a general lower bound for (m,n, , ,η,g,c,ρ = 0). π C I S Theorem 1: Lower Bound for Finite Dimensional CDMA Systems with Perfect Power Estimation For the above channel model, when power estimation is perfect, we have (m,n, , π,η,g,c,ρ =0) EG,C supsup m(γloge C I S ≥ − ( p γ n m −log(1+γ))−logEX˜ Eb e2(−1+γγr2)m|bTCGX˜|2 , (3) ) (cid:18)(cid:18) (cid:18) (cid:19)(cid:19) (cid:19) o where r = 2η ; b and X˜ are, respectively, vectors of length n with i.i.d. entries of distribution σ2(σ2+µ2)(σ2+µ2) p π π c c q π() and p˜(), in which p˜() is defined to be the probability law on ˜ = , which is the difference of two · · · I I −I independent random variables of pdf p(). · For the proof, refer to Appendix A. Now, we propose a general upper bound for the finite case. Theorem 2: Upper Bound for Finite Dimensional CDMA Systems with Perfect Power Estimation For the above channel model, when power estimation is perfect, we have (m,n, , ,η,g,c,ρ = 0) π C I S ≤ min mlog ,EC,G,A1 m(H(Y1) H(N1)) , (4) |I| − ! n o where Y = 1 n a X C G +N and A1 = [a ,...,a ] is the first row of matrix A. 1 √m i=1 i i i i 1 1 n P The proof is presented in Appendix B. In the next section we will use these bounds to find lower and upper bounds for asymptotic CDMA systems. 5 IV. ASYMPTOTIC BOUNDS FOR THE INFINITE DIMENSIONAL CDMA SYSTEMS WITH IMPERFECT POWER ESTIMATION For the asymptotic case, we need to define the sum capacity as given by ζ(β, , ,η,g,c,ρ) = lim (m,n, , ,η,g,c,ρ), (5) π π I S m,n C I S →∞ n/m β → where β = n is the loading factor. m Asymptotic results for binary CDMA is developed by Tanaka [1]. Guo-Verdu’s paper [2] has extended Tanaka’s results to non-binary finite size alphabet with near-far effects with perfect power estimation, including various optimal and suboptimal detectors. In this section, we plan to obtain bounds for sum capacity when perfect power estimation is not available (ρ = 0). Below, we will give examples where we can find bounds for Tanaka and 6 Guo-Verdu results when perfect power estimation is not available. Throughout this section we assume that C= I, which means that there is no power allocation mechanism. Theorem 3: Lower and Upper Bounds for the Sum Capacity of CDMA Systems with Imperfect Power Estimation Suppose that ρ is not zero, which implies that we have an imperfect estimation of user powers. We then have ζ(β, 1 , ,η,g,δ( 1),ρ) ζ(β, 1 , ,η ,g,δ( 1),ρ = 0), (6) π π l {± } S ·− ≥ {± } S ·− ζ(β, 1 , ,η,g,δ( 1),ρ) ζ(β, 1 , ,η ,g,δ( 1),ρ = 0), (7) π π u {± } S ·− ≤ {± } S ·− where c() = δ( 1) is the Dirac delta function representing the pdf of a point process at point 1 and · ·− η η = , l 1+ξρ2η 1+√β 2 η η = (cid:0) (cid:1) (8) u 1+ξρ2η 1 √β 2 − (cid:0) (cid:1) in which, ξ = 1 for real CDMA systems and ξ = 2 for complex CDMA systems. For the proof, please refer to Appendix C. 6 Example 1: Tanaka’s Capacity For the binary input vectors and signature matrices, from Theorem 3 and [1], the sum capacity is bounded by 1 log(1+2η β(1 θ))+q(λ,θ)log(e) 2β u − ζ(β, 1 , 1 ,η,δ( 1),ρ) ≥ {± } {± } ·− ≥ 1 log(1+2η β(1 θ))+q(λ,θ)log(e), (9) 2β l − where q(λ,θ) is defined by λ q(λ,θ)= (1+θ) ln cosh √λZ +λ D , (10) Z 2 − Z (cid:16) (cid:16) (cid:17)(cid:17) in which D is the standard normal measure, Z 1 λ = , θ = tanh √λZ +λ D . (11) σ2+β(1 θ) Z l − Z (cid:16) (cid:17) This result is based on replica theory, a rigorous proof of [1] is given in [10] for β α 1.49. s ≤ ≈ Example 2: Guo-Verdu’s Capacity Forthebinaryinputvectorsandsignaturematrices,GuoandVerdu[2]derivethechannelcapacityin theasymptotic case when the power estimation is perfect, ζ(β, , ,η,g,c,ρ = 0) = π I S z2 e 2 βE logcosh ψsnr z ψsnr dz {− √2π − } Z (cid:16) p (cid:17) 1 +βψ E(snr)loge+ [(ψ 1)loge logψ], (12) 2 − − where ψ is the solution of this fixed point equation: z2 1 e − 2 = 1+βE snr 1 tanh ψsnr z (ψsnr) dz , (13) ψ { " − √2π − #} Z (cid:16) p (cid:17) The expectationsis oversnr = n η (G 2+C 2), where G and C are the randomvariables with probability m×µ2c+σc2 1 1 1 1 distribution functions g and c, respectively. 7 V. NUMERICAL RESULTS In this section we try to numerically evaluate the bounds derived in the previous sections. For finite CDMA systems because of computational complexity, the simulation results are for small values of m and n, namely, (m = 5, n =10) and (m = 3, n = 9). For asymptotic results, we have used β = 2,3. Figure 1 shows a comparison of the sum capacity lower bound versus the normalized SNR (η) for four different scenarios. The dotted line in the figure in the lower bound for the sum capacity for a binary CDMA system without any near-far effects. The solid curve is the lower bound for the sum capacity with near-far effects when we have perfect knowledge about the power at the receiver. The dashed curve is for the case when we have the traditional power compensation for near-far effects with perfect power estimation. Pale solid line is the sum capacity lower bound with random power allocation. These numerical results are for a CDMA system with dimensions of (m=5, n=10) and hence an overloading factor β = 2. The results in this figure are quiet surprising for the normalized SNR values of η greater than 9 dB; a CDMA system with near-far effects has a higher lower bound for the sum capacity than that of a case without any near-far effects when we have perfect knowledge about the variation of power at the receiver end1. The second surprise is that the traditional power compensation for the near-far effects is worse than the near-far effects without any compensation when we have perfect knowledge about the received power. This implies that, equivalently, if we have random power allocation at the transmitter side, we can improve the lower bound for the sum capacity. Essentially, the solid curve in Fig. 1 is shifted to the left by a fixed amount as explained in footnote2. Figure 2 shows a comparison of three strategies for power control. The lower solid line in this figure is the same as the lower curve in Fig. 1 where the near-far effects are compensated by traditional power control. The middle solid curve showsthe lower bound for the sum capacity when a Gaussianrandompowercontrol is used.The dotted 1In power allocation schemes, assigning the same power to all users might not be the best strategy. Thus, we expect the existence of power allocation schemes that improve the sum capacity. Our lower bounds confirm this proposition. Although the improvement of lower bounds do not mean that the actual capacity has increased, since the sum capacity is defined as the supremum over all input powers and distributions and signature matrices, the sum capacity can only improve. 2η is normalized by the transmitter power, this implies that in power control and power allocation strategies we have to consider the average power variations in the normalized η. However, in fading or near-far effects, the parameter η is not changed; this creates a shift in the curve. 8 curve in this figure shows power control using water filling. Clearly, the water filling power control has the best performance. However, an appropriate random strategy for power control can approach the water filling strategy. The lower bounds for the sum capacity for the water filling and the random power control are approaching 1 for high values of η; this implies that the lower bounds become very tight for the noiseless case. Figure 3 is similar to the previous figure except that the dimension of the CDMA system is (m=3, n=9) and hence β = 3. The same observations as Fig. 2 also hold. On the otherhand,theasymptotic behaviorsare drastically different. In the absenceof near-fareffects,anypower allocation does not change the lower bound. Also, in the presence of new-far/fading channels, no types of power compensation can improve the results. Essentially, we have two lower bounds as shown in Fig. 4. This figure is the numerical results of Tanaka [1] and Guo-Verdu [2] sum capacities with or without near-far effects. We have also evaluatedthe asymptotic sumcapacity with imperfect powerestimation. Figure 5 showsa compari- son among the actual normalized asymptotic sum capacity derived by Tanakawhen there is no near-far effects with perfect power estimation and bounds for the equivalent CDMA system with near-far effects and imperfect power estimation (CER=20dB). This figure clearly shows the degradation of the sum channel capacity in near-far/fading environments. Figure 6 gives a comparison of the asymptotic bounds for the sum capacity for two values of β in the presence of near-far effects with a CER of 25dB. This figure also shows the bounds are tight for high values of CER. VI. CONCLUSION AND FUTURE WORKS The first contribution of this paper is the development of lower and upper bounds for the sum channel capacity of finite dimensional CDMA systems with fading and/or near-far effects for binary and finite non-binary inputs. An interesting observation in the simulations of such finite dimensional systems is that when we have fading or near-far effects with perfect power estimation, the sum capacity of the ”degraded” CDMA system is surprisingly greater than the ideal case for SNR values greater than a certain threshold. For the asymptotic case, the inequality in the previous system becomes equality. Also, the effects of power allocation and power control on the sum capacity with near-far effects are studied. We 9 1 y t i c a p 0.9 a C m u 0.8 S d e iz 0.7 l mi r No 0.6 e h t WithoutNear-FarEffectswith Random PowerAllocation 1+0.2Z r 0.5 o f WithoutNear-FarEffectsand PowerAllocation d n Near-FarEffectswithoutPowerAllocation u 0.4 o B Near-FarEffectswith Traditional PowerControl r we 0.3 o L 0.2 0 10 20 30 40 50 60 η (dB) Fig. 1. Sum capacity bounds for binary CDMA systems with m=5 and n=10, where Gi the uniform distribution between 0.5 and 1, also Z ∼N(0,1).. have concluded that traditional power control can not improve the sum capacity unlike water filling and appropriate random power allocation methods. Again power control strategies can not improve the sum capacity for infinite dimensional systems. Equivalently, we could consider random power allocation for the users at the transmitters without fading/near-far effects. In this case, the sum capacity is always greater than or equal to the case of equal power allocation for the finite dimensional CDMA. In the asymptotic case, the sum capacities coincide, which is also a surprise. The other contribution is the development of a method that translates a near-far sum capacity problem with imperfect power estimation to the evaluation of the capacity for a CDMA system with perfect power estimation. For future work, we suggest to use a Markov chain for the power model which can improve the bounds. Also, optimal power allocation for binary and non-binary CDMA systems is an interesting subject. 10 y t 1 i c a p a C0.9 m u S 0.8 d e z i l mi0.7 r o N e0.6 h t r o f0.5 d n u Near-Far Effects with Water Filling Power Control o B0.4 r Near-Far Effects with Random Power Allocation 1+0.2Z e w Lo0.3 Near-Far Effects with Traditional Power Control 0.2 0 10 20 30 40 50 60 η (dB) Fig. 2. Sum capacity bounds for binary CDMA systems with m=5 and n=10, where Gi the uniform distribution between 0.5 and 1, also Z ∼N(0,1). APPENDIX A. Proof of Theorem 1, Lower Bound for Finite Dimensional CDMA Systems with Perfect Power Estimation For a fixed A, G and C, we have I(X;Y) =h(Y) h(N) = − E ( logf (Y)) E ( logf (N)) Y Y N N − − − f 1 ACGX +N = E log Y √m . X,N− (cid:16) f (N) (cid:17) N   Using Jensen’s inequality, we get the following : I(X;Y)= f 1 ACG(x x)+N E log P (x)P (x) N √m ′− . N−  X X ′ (cid:16) f (N) (cid:17) N x,x X′    Using Jensen’s inequality, we get