Asymptotically optimum energy profile for successive interference cancellation in DS-CDMA under a power unbalance constraint

1 Asymptotically optimum energy profile for Successive Interference Cancellation in DS-CDMA under a power unbalance constraint Josep Sala (Senior Member IEEE), Francesc Rey (Member IEEE), Javier Villares (Member IEEE) Abstract—1A new Ordinary Differential Equation (ODE) governing the SNIR evolution of a Successive Interference Canceller (SIC) for DS-CDMA is derived when the number of users tends to infinity and all users share the same channel encoder. Using Variational Calculus, this ODE is applied to obtaining the energy profile that maximizes the average spectral efficiency when a constraint on the power unbalance (maximum power to minimum power ratio) of received users is enforced. The conditions for extremality of the optimum energy profile are established in terms of the common encoder’s Packet Error Rate (PER) function. Index Terms— Successive Interference Cancellation, power unbalance, differential equation, Variational Calculus, Packet Error Rate, CDMA, error propagation. I. INTRODUCTION AND INITIAL DEFINITIONS Spectral efficiency studies carried out for DS-CDMA Successive Interference Cancellation (SIC) may be found in the literature in terms of capacity-achieving codes and a constraint on the average received energy of all users. With this setting, an exponential energy profile, which leads to a uniform peruser Signal to Noise plus Interference Power Ratio (SNIR) profile, is shown to optimize the average capacity [1]. In constrast, in this work we consider real (implementable) noncapacity-achieving channel encoders characterized by their Packet Error Rate (PER) function versus the per-user symbol energy Esto noise plus interference power spectral density ratio Nt:Es=Nt(SNIR), with Nt=N0+Ni, and we seek to maximize the average spectral efficiency over all users, ¥, using the expression previously derived in [2] for SIC and summarized in section II. Although the average received symbol energy per user Esis the usual constraint when optimizing the average capacity over the per-user symbol energy distribution at the SIC input, it does not reflect possible and practical limitations in terms of the dynamic range of users, as upper/lower bounds on the received symbol energy profile (i.e. minimum/maximum transmission power constraints). Hence, we set out to derive the maximum average spectral efficiency under a power unbalance constraint h=Es;max=Es;min, or ratio of maximum to minimum per-user symbol energy at the SIC input. We will show that, when some conditions on the PER function and operating Es=Ntare met, the 1The authors are with the dept. of Signal Theory and Communications at the Technical University of Catalonia, Barcelona (Spain). E-mail: fjosep.sala,francesc.rey,[email protected]. ’This work has been supported by the Catalan and Spanish governments under projects 2009SGR1236 (AGAUR), DYNACS (TEC201021245-C02/TCM), COMONSENS (CONSOLIDER INGENIO CSD2008-00010) and THOFU (CENIT CEN-20101019). exponential energy profile asymptotically achieves maximum average spectral efficiency under such a constraint. II. ASYMPTOTIC PER In this section, we summarize the basic definitions and results in [2] used for the computation of the asymptotic PER. New results will be presented in section III onwards. We consider that, for a scenario of Kactive users, SIC operation proceeds from user k=1up to user k=K, with Es[k]the per-user symbol energy. In the asymptotic case K!1, we may define the continuous index tas: 0< t=lim K!1 k=K ∑1, associated with the corresponding continuous energy profile Es(t)=lim K!1 Es[tK]. Although the results in [2] are valid for an arbitrary Es(t), we will understand that Es(t)is non-increasing in t(ordered users), as is usually assumed when optimizing SIC performance. Then, the power unbalance and average symbol energy parameters mentioned in section I may be defined as h=Es(0)=Es(1) and Es=R1 0Es(t)dt, respectively. It was shown in [2] that the average PER, PER(Æ), is given by the following expression, where Æ=lim K!1 K=N is the load factor (ratio of users K to spreading factor N) in the long spreading code model [3] and µis a generic decorrelation factor accounting for inter-user timing misalignment and/or carrier phase differences, PER(Æ)=Z1 0 PER £°(tj∑ ª(t))§dt(1) °(tj∑ ª(t)) : =Es(t) N0+∑ ª(t)+Ƶ R1 tEs(u)du(2) with °(tj∑ ª(t)) the per-user Es=Ntat an interference level Ƶ R1 tEs(u)dufrom yet uncanceled users and ∑ ª(t)the aggregate residual interference level incorporating error propagation from previous users [4]. The usual error propagation model considers that at each stage, a fraction "(t)of the current user’s energy affects users in subsequent stages with "(t)=≤ (imperfect cancellation under successful decoding) or "(t)=1 (no cancellation under unsuccessful decoding). Thus, it was shown in [2] that ∑ ª(t)becomes deterministic and constitutes a solution to the following Ordinary Differential Equation (ODE), with boundary constraint ∑ ª(0) = 0, d∑ ª(t)=dt=ƵEs(t)°≤+(1°≤)PER £°(tj∑ ª(t))§¢(3) Now, we may define the average Packet Success Rate (PSR) from (1) as PSR(Æ)=1°PER(Æ), so that the average sucAccepted version of the article published in IEEE Communications Letters, vol. 16, num. 2, Feb. 2012. DOI: 10.1109/LCOMM.2011.121311.111964. Available at: http://ieeexplore.ieee.org © 2012 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. 2 cessfully delivered spectral efficiency ¥(Æ)[b/s/Hz] becomes, ¥(Æ)=ÆRcPSR(Æ)=ÆRcZ1 0 PSR[∑ °(t)]dt(4) with Rc=brc=(1+Ø)(Ø: roll-off factor of chip pulse shaping; b: bits per constellation symbol; rc: channel coding rate) and PSR[°] = 1 °PER[°] the Packet Success Rate function of the common channel coding/modulation scheme. The integral for PSR(Æ)is defined implicitly. III. DIFFERENTIAL EQUATION ON °(tj∑ ª(t)) We derive a new ODE for °(tj∑ ª(t)) to obtain the optimum energy profile in section IV. For shorter notation, we consider the dependence on ∑ ª(t)implicit, with ∑ °(t): = °(tj∑ ª(t)). Let M(t)denote the denominator in (2), with M(t)= Es(t)=∑ °(t)=N0+∑ ª(t)+Ƶ R1 tEs(u)du. Then, we may express its derivative dM(t)=dtusing the ODE in (3) to get, d dtM(t)=ƵEs(t)°≤+(1°≤)PER[∑ °(t)]¢°ÆµEs(t) =°ÆµM(t)(1 °≤)∑ °(t)PSR[∑ °(t)] (5) Dividing by M(t)on both sides and letting log denote Napier’s base-elogarithm, we finally obtain, d dtlog Es(t)= d dtlog ∑ °(t)°Æµ©[∑ °(t)] (6) ©[°] : =(1°≤)¢°¢PSR[°] (7) which is the ODE for ∑ °(t)with initial condition ∑ °(0) = Es(0)=°N0+Ƶ R1 0Es(t)dt¢for an input energy profile Es(t), where the nonlinearity ©[°] depends on the decoder’s PSR function and on the residual interference factor ≤. We remark that the ODE in (6) for determining ∑ °(t)is valid for an arbitrary Es(t)(regardless of whether users are ranked according to power or not). For an ordered non-increasing energy profile Es(t), with h=Es(0)=Es(1) the power unbalance, we get a useful expression for hin terms of ∑ °(t)for later use in Section IV: integrating (6) over the interval [0;1], it results that, log 1 h°log ∑ °(1) ∑ °(0) =°Æµ Z1 0 ©[∑ °(t)]dt(8) IV. OPTIMUM ENERGY PROFILE The previous section has shown how to compute the Es=Nt profile ∑ °(t)from the received energy profile Es(t). In this section, we intend to maximize the average spectral efficiency ¥(Æ)over Es(t), subject to a power unbalance constraint and for a specific load Æand noise spectral density N0. We follow an indirect procedure where, inspired by the relationship (4), optimization of ¥(Æ)is carried out first over ∑ °(t)(setting the appropriate constraints), and used later to compute the corresponding Es(t). We consider the functional G(∑ °; Æ)= ¥(Æ)=(ÆRc)=PSR(Æ), where, for clarity, its dependence on ∑ °(t)is now made explicit and the constant factor ÆRc irrelevant for maximization is dropped. Two point constraints are considered on ∑ °(t):∑ °(0) = °0(to account for the initial condition of the ODE in (6), and therefore, N0) and ∑ °(1) = °1 (a technicality whose necessity will become apparent during optimization). One additional integral constraint is also required to incorporate the power unbalance hby way of (8). The following variational optimization problem results, where G(∑ °; Æ)is to be maximized over ∑ °(t)at a specific load Æ, ¥(Æ)ØØmax ÆRc = max ∑ °(t)∑G(∑ °; Æ)=Z1 0 PSR[∑ °(t)]dt∏(9) s:t:∑ °(0) = °0;∑ °(1) = °1(10) s:t:Z1 0°∑ °0(t)=∑ °(t)°Æµ©(∑ °(t))¢dt= log 1 h(11) with ∑ °0(t)=d ∑ °(t)=dt. Note that the integral constraint in (11) is obtained by moving the term log(∑ °(1)=∑ °(0)) in (8) to the integral’s first term on the left-hand side of (11). For a stationary point ∑ °(t)of G(∑ °; Æ), the corresponding profile Es(t)with power unbalance hcan be derived from (6) by direct integration over the interval [0;t]as, Es(t) Es(0) =∑ °(t) ∑ °(0) exp ∑°Æµ Zt 0 ©[∑ °(u)]du∏(12) The constrained optimization problem (9) can be solved using standard Variational Calculus techniques. We consider the following equivalent problem, Jmax = max ∑ °(t)∑Z1 0 F(t; ∑ °(t);∑ °0(t))dt∏(13) s:t:∑ °(0) = °0;∑ °(1) = °1 s:t:Z1 0 G(t; ∑ °(t);∑ °0(t))dt= log 1 h(14) where we set F(t; ∑ °;∑ °0)=PSR[ ∑ °] and G(t; ∑ °;∑ °0)=∑ °0=∑ °° Ƶ©(∑ °) the terms within the two integrals in (9,11). As proved in [5], the Euler-Lagrange Equation (ELE) can be used to compute the stationary point ∑ °(t)when applied to the Lagrangian H=F+ΩG, with Ωa Lagrange multiplier, @∑ °[H]°d dt@∑ °0[H](E:L:E:) =0 (15) where @xdenotes the partial differentiation operator w.r.t. variable x. The two differentiation operators on Hyield, @∑ °[H]=PSR 0[∑ °(t)] + Ω¢µ°∑ °0(t) ∑ °2(t)°Æµ©0(∑ °(t))∂ d dt@∑ °0[H]= d dt∑0+Ω1 ∑ °(t)∏(16) with PSR0;©0the derivatives w.r.t. ∑ °. When the two previous results are substituted into (15), an ODE in tis obtained for ∑ °(t), which must be solved subject to the boundary conditions ∑ °(0) = °0and ∑ °(1) = °1for a suitable value of the Lagrange multiplier Ω. As the terms depending on ∑ °0(t)cancel each other out, the ELE (15) is turned from a differential equation to the following nonlinear equation on ∑ °(t), PSR0[∑ °(t)] = Ω¢Æµ©0(∑ °(t)) (17) which is fulfilled when ∑ °(t)=° ?is constant over t. Then, a Lagrange multiplier Ωcan always be found such that Ω= (Ƶ)°1PSR0[°0]=©0(°0)>0(PSR;©are increasing in °) and a stationary point to the optimization problem in (9) is 3 obtained, with ∑ °(t)=° ?uniform. Thus, ∑ °(t)cannot be a stationary point unless we have equality of the two boundary conditions on ∑ °(t)at t=0and t=1:°0=° 1=° §. V. EXTREMALITY CONDITIONS We prove under what conditions the stationary point ∑ °(t)= °0of the constrained optimization problem (9) yields a maximum. Hence, we consider an infinitesimal variation of ∑ °(t)which fulfils the constraints in (10,11): °(t)=° 0+v(t), with v(t)converging uniformly to 0(v(t)!0) in 0<t∑1, with v(0) = v(1) = 0 so that the constraints in (10) are met and, additionally, from (8), the constraint (11) becomes, log 1 h=°Æµ Z1 0 ©[°0+v(t)]dt(18) As v(t)!0uniformly, vmax : = max0∑t∑1[jv(t)j]is asymptotically small and we may use the second-order Taylor expansions in v(t)of the functional G(°; Æ)about °(t)=° 0 and of the integral constraint (18). Thus, we may write, G(°; Æ)=PSR[° 0]+PSR 0[°0]Z1 0 v(t)dt+ +1 2PSR00[°0]Z1 0 v2(t)dt+o(v2 max)(19) with PSR0[°];PSR00[°] the first/second derivatives of PSR[°] w.r.t. °and o(¢)Landau’s small-o. Further, the second-order approximation to the integral constraint (18) yields (20), with ©0[°];©00[°] the first/second derivatives of ©[°] w.r.t. °, log 1 h=°Æµ°©[°0]+© 0[°0]Z1 0 v(t)dt+ +1 2©00[°0]Z1 0 v2(t)dt¢+o(v2 max)(20) As (18) must also be fulfiled for v(t)=0, we have log 1 h= °Æµ©[°0]and thus, (20) reduces to the following equality between the integrals on v(t)and v2(t), ©0[°0]Z1 0 v(t)dt+1 2©00[°0]Z1 0 v2(t)dt+o(v2 max)=0 (21) As v(t)!0uniformly: v2(t)<< jv(t)j, and the constraint (21) requires that v(t)have positive and negative fluctuations so that its integral mean over 0<t∑1be in the order of the integral mean of v2(t)over the same interval. Substituting (21) into (19), with G(°0;Æ)=PSR[° 0], we get, G(°; Æ)=G(°0;Æ)°≠(°0)¢1 2Z1 0 v2(t)dt+o(v2 max) (22) ≠(°0): =PSR 0[°0]©00[°0] ©0[°0]°PSR00[°0](23) Hence, the condition for °(t)=° 0to be a maximum is that ≠(°0)>0, which is analyzed in Lemma 1. Additionally, from (22), and as v(t) = °(t)°°0, we see that ≠(°0)is measuring the sensitivity to deviations from the uniform profile while preserving constraints (power unbalance and point constraints). The value of ≠(°0)depends on the encoder’s PSR characteristic and the operating point °0. Hence, letting jj ¢ jj2denote the L2[0;1] norm, we may write from (22), ≠(°0)=°2lim °(t)!°0 G(°(t); Æ)°G(°0;Æ) jj°(t)°°0jj2 2 (24) We now seek a more direct expression of ≠(°) in terms of PSR[°] than its definition in (23) to examine what property is required of PSR[°] to guarantee ≠(°0)>0and hence, optimality of ∑ °(t)=° 0. Let r°=d=d° denote diffentiation w.r.t. °. Then, (23) can be expressed as follows, ≠(°) = PSR0[°] ¢r °log s(°) (25) s(°) : =1 1°≤¢©0[°] PSR0[°] =°+ PSR[°] PSR0[°] As PSR[°] is increasing in °, we have PSR0[°] >0. Hence, from (25), ≠(°) >0implies that log s(°), and consequently, s(°), be increasing in °. This reduces to r°s(°) >0, where, r°s(°) = 1 + r°[(r°log PSR[°])°1](26) Differentiating on the right-hand side, r°s(°) >0leads to, jr°log PSR[°]j2>r2 °log PSR[°] (27) Using PSR[°] = 1 °PER[°] in (27), we get its equivalent condition in the PER after some straightforward algebra, 2(PER0[°])2+PER 00[°](1 °PER[°]) >0(28) Finally, the property sought is established by Lemma 1, Lemma 1:≠(°0)>0is equivalent to conditions (27,28) at °=° 0. A sufficient condition for (28) to hold is that PER00[°] >0, with °expressed in linear scale ®. No explicit general expression is available for the PER of any code, which would provide a quantitative assessment of the range of °’s where (28) holds. Nonetheless, the more restricted condition PER00[°] >0already guarantees ≠(°) > 0where PER[°] is convex-[. This is reasonably fulfilled by all practical codes for some semi-infinite interval °∏°min, where °min is associated with rather high values of the PER. We may extract some additional insight from the average Es=Nt, defined as °av =R1 0°(t)dt. Then, we have R1 0v(t)dt=° av °°0, and, from (21), °av °°0=°©00[°0] 2©0[°0]jj°(t)°°0jj2 2+o(v2 max)(29) Hence, substituting this expression into (24), we get, ≠(°0)=©00[°0] ©0[°0]lim °(t)!°0 G(°(t); Æ)°G(°0;Æ) °av °°0 (30) and then, plugging (30) into (23), we obtain the sensitivity to deviations from the average value when constraints are met, ¢(°0)= lim °(t)!°0 G(°(t); Æ)°G(°0;Æ) °av °°0 (31) =PSR 0[°0]°PSR00[°0]©0[°0] ©00[°0](32) Hence, as G(°0;Æ)is a maximum (the denominator in (31) is negative), the sign of ¢(°0)in (31) determines the sign of the deviations of °av from °0:¢(°0)>0) 4 °av <°0and ¢(°0)<0)°av >°0. Some tedious but straightforward algebra shows that ¢(°) = °r°[s°1(°)] ¢ (©0[°])2=((1 °≤)©00[°]). As we saw before, for ≠(°) >0, we have r°[s(°)] >0and thus r°[s°1(°)] <0, which leads to the following result for °(t)!°0(when also ≠(°) >0), sign[¢(°)] = sign[©00[°]] = °sign[°av °°0](33) VI. THE EXPONENTIAL ENERGY PROFILE We determine the energy profile Es(t)maximizing ¥(Æ) under the given constraints, proving that, as in capacity studies, it is also exponential. Setting ∑ °(t)=° 0in (12), we get, Es(t)=Es(0)e°∏t ;∏=Ƶ(1 °≤)°0PSR[°0](34) with PSR[°0]=G(°0;Æ)and ∏= log h. This energy profile is optimum only at the given load Æ: (i) at Æ06=Æthe corresponding °Æ0(t)associated with Es(t)in (34) is no longer uniform; (ii) the optimum exponential profile is different for each Æ. We intend now to derive a relationship for the power unbalance hin terms of the set of inputs f≤; pE;snr0g, where, 1) pEdenotes the target PER, associated from (4) with the average spectral efficiency ¥(Æ)=ÆRc(1 °pE)and where pE=PER[° 0], for °0the operating Es=Nt. 2) snr0=Es(0)=N0constitutes the SNR of the first user and allows to incorporate direct information on the channel noise power spectral density N0. Substituting (34) into (2) at t=0and using ∑ ª(0) = 0, °(0) = °0and PSR[°0]=1°pE, some tedious algebra shows that, for the target pE, the relationship between hand snr0becomes h°1=1°(1°≤)(1°pE)(1°°0=snr0), where °0=PER °1[pE]∑snr0must hold. VII. SIMULATIONS AND CONCLUSIONS Figure 1(a) shows an estimation b ≠(°) of ≠(°) for an implementation of the following codes: (i) the DVB-RCS/QPSK turbo-code [6] with blocklength L= 482 information bits and rates r=1=2(TC1) and r=1=3(TC2) using max-log-MAP decoding; (ii) the rate r=1=2quasi-cyclic LDPC/QPSK code (LDPC1) of the DVB-S2 standard [7]. The horizontal axis has been chosen to be Eb=Ntinstead of °for each channel code: °=(brc)Eb=Nt. The estimate b ≠has been obtained by local parabolic fitting of the measured PER characteristic over 5 points for computing the derivatives in (23), represented in Figure 1(b) for all codes. It is thus experimentally verified that ≠(°) >0and that the uniform profile ∑ °(t)=° 0achieves a maximum of the average spectral efficiency for the given constraints. We note that largest sensitivity is associated with low °’s, whereas a decrease ≠!+0 is manifested at high °’s (a flat maximum for ¥(Æ)about ∑ °(t)=° 0). As an example, Figure 1(c) shows the average PER over all SIC stages versus Eb=NtØØt=0 =° 0=(brc)for a family of profiles °d(t)=© °1[©[°0]¢(1 + dsin(2ºt))] parametrized by 0∑d∑0:3,°=© °1[¡]the inverse function of ¡= ©[°] and the average PER given by PER=R1 0PER[°d(t)]dt. As can be checked using (8), any °d(t)fulfils the same power unbalance constraint h(9 dB) as well as °d(0) = °d(1) = °0 (the uniform profile is obtained for d=0). The associated 0 0.5 1 1.5 2 2.5 3 3.5 −10 0 10 20 30 40 (a) Omega Eb/Nt 0 0.5 1 1.5 2 2.5 3 3.5 10−6 10−4 10−2 100(b) PER Eb/Nt TC r=1/2 TC r=1/3 LDPC r=1/2 TC r=1/2 TC r=1/3 LDPC r=1/2 0 0.5 1 1.5 2 2.5 3 3.5 10−6 10−4 10−2 100(c) average PER Eb/Nt at t=0 d=0 (opt.) d=0.05 d=0.1 d=0.2 d=0.3 Fig. 1. (a) ≠, (b) PER versus Eb=Ntfor the TC1, TC2 and LDPC1 codes; (c) PER vs. Eb=NtØ Øt=0 for d=0;0:05;0:1;0:2;0:3. Es(t)is easily found substituting °d(t)in (6). The parameter dcontrols the fluctuations of °d(t)about °0, so that larger d’s lead to increased degradation of the average PER in Figure 1(c), shifting the waterfall region toward higher Eb=Nt’s. Concluding, we have validated that, for a common noncapacity-achieving channel encoder, the uniform Es=Ntprofile ∑ °(t)=° 0of DS-CDMA SIC and its corresponding exponential per-user symbol energy profile asymptotically achieve maximum average spectral efficiency under a power unbalance constraint, if the second derivative of the encoder’s PER function fulfils PER00[°0]>0. A more compact ODE for ∑ °(t)than in the one in [2] for ∑ ª(t)has also been derived. REFERENCES [1] D. Djonin and V. K. Bhargava, ”Asymptotic Analysis of the Conventional Decision Feedback Receiver in Fading Channels”, IEEE Trans. on Wireless Comm., Sept. 2003. [2] J.Sala, J.Villares and F.Rey, ”Asymptotic and Finite-User PER Analysis of Successive Interference Cancellation for DS-CDMA”; (accepted for publication in IEEE Communication Letters, 2011). [3] S. Verdu and S. Shamai, ”Spectral Efficiency of CDMA with Random Spreading”, IEEE Trans. on Information Theory, March 1999. [4] V. K. N. Lau and Wing Kwan Ng, ”Per-User Packet Outage Analysis in Slow Multiaccess Fading Channels with Successive Interference Cancellation for Equal Rate Applications”, IEEE Trans. on Wireless Communications, May 2008. [5] C. Ray Wilie, ”Advanced Engineering Mathematics”, 6th edition, McGraw-Hill, 1995. [6] ”Digital video broadcasting (DVB); interaction channel for satellite distribution systems”. ETSI EN 301 790 V1.2.2 (2000-12) European Telecommunications Standards Institute (ETSI). [7] ”Digital video broadcasting (DVB); Second generation framing structure, channel coding and modulation systems for broadcasting, interactive services, news gathering and other broad-band satellite applications”, ETSI EN 302 307, v1.2.1 (2009-08) European Telecommunications Standards Institute (ETSI).