ap-5-11.dvi Acta Polytechnica Vol. 51 No. 5/2011 Numerically Optimized Uniformly Most Powerful Alphabets for Hierarchical-Decode-and-Forward Two-Way Relaying M. Hekrdla Abstract Weaddress the issue of the parametric performance of theHierarchical-Decode-and-Forward (HDF) strategy in awireless 2-way relay channel. PromisingHDF, representing theconceptofwireless network coding, performswellwithapre-coding strategy that requires Channel State Information (CSI) on the transceiver side. Assuming a practical case when CSI is available only on the receiver side and the channel conditions do not allow adaptive strategies, the parametrization causes significant HDF performance degradation for some modulation alphabets. Alphabets that are robust to the parametrization (denoted Uniformly Most Powerful (UMP)) have already been proposed restricting on the class of non-linear multi-dimensional frequency modulations. In this work, we focus on the general design of unrestricted UMP alphabets. We formulate anoptimization problemwhich is solvedbystandardnon-linear convex constrained optimization algorithms, particularly by Nelder-Mead global optimization search, which is further refined by the local interior-points method. Keywords: wireless network coding, hierarchical-decode-and-forward relaying, wireless two-way relay channel, modu- lation alphabet design, non-linear convex optimization. 1 Introduction Cooperative wireless network protocols which utilize network coding in the physical layer have recently attracted strong research interest due the significant capacity gains that theyoffer; for citations see [1] and the references therein. The terms Wireless Network Coding (WNC) or Physical-Layer Network Coding (PLNC) are usually used to stress the fact that oper- ations similar to Network Coding (NC) [2] principles are carriedout in thewireless domain andcompletely in the physical layer. Even in awireless 2-WayRelay Channel (2-WRC), which is the simplest cooperative network, WNC almost doubles the achievable com- munication sum-rates. 2-WRCconsists of two termi- nals, A andB, bi-directionally communicatingwith a supporting relaynodeR in ahalf-duplexmanner (the terminals cannot send and receive at the same time). In [3] and [4], the authors show that a two-stage DeNoise-and-Forward (DNF)/Hierarchical-Decode- and-Forward (HDF) strategy is very promising in 2-WRC since it can reliably operate outside the clas- sicalMultiple-ACcess (MAC) capacity region [5]. In- stead of DNF, we feel that a more generic term HDF is better suited, especially for more compli- cated multi-source networks. HDF consists of an MAC stage when A and B are simultaneously trans- mitting to the relay R with only hierarchical (exclu- sively coded) data decoding, and a BroadCast (BC) stage when R broadcasts the previously-decoded hi- erarchicaldata. Exclusiveoperationallowsthe termi- nals to decode the hierarchical data using their own data serving as Complementary-Side Information (C-SI) [6]. Assuming canonical linear (one complex dimension; PSK, ASK, QAM) modulation alpha- bets, HDF strategy suffers fromunavoidablewireless channel parametrization in the practical case when only Channel State Information at the Receiver side (CSIR) is available. The problem of parametrization can be suppressed by adaptive extended-cardinality network coding [7]; the adaptation requires moder- ate channel dynamics, and it is sensitive to chan- nel estimation errors. According to [8], we are able to overcome the parametrization effects by proper multi-dimensional alphabet design. Paper [9] defined a class ofUniformlyMostPowerful (UMP)alphabets which are robust to the parametrization. It has been shown that the parametrization is not harmful when the terminals use binary alphabets, but non-binary linear alphabets always suffer from this effect. In this case,more dimensions need to be accommodated to meet the UMP condition. Paper [9] exploits ad- ditional dimensions of non-linear multi-dimensional frequency alphabets to fulfill the UMP condition. In this paper, we study the design of unrestricted multi-dimensional UMP alphabets. We reformulate the UMP alphabet design as a complex optimization problem(maximizing theminimalEuclideandistance constrained by the UMP condition and a unit mean symbol energy constraint) which is to be solved by standard non-linear convex constrained optimization algorithms, particularly by Nelder-Mead global opti- 53 Acta Polytechnica Vol. 51 No. 5/2011 mization search, which is further refined by the lo- cal interior-points method [10]. The results are pre- sented inTable 1, and the relevant error performance is presented in Sec. 4. 2 System Model 2.1 Signal space description and used notation Let symbol AT be a modulation alphabet at the ter- minal T ∈ {A, B}. We distinguish two cases: a) both terminals use the same alphabets AA = AB or b) the alphabets are assumed to be unequal AA �= AB. We assume that both terminals have the same alphabet cardinality Md = |AA| = |AB| to be a power of two. Further,wedonot consider channel codingbecause it canbe seriallyconcatenatedwith theproposedalpha- bets, not affecting the results [4,7]. The modulation function M : ZMd = {0,1, . . . Md − 1} → C Ns is as- sumed to be a memoryless per-symbolmapper, how- ever the output constellation space signals are gener- ally allowed to bemulti-dimensionalwith dimension- ality Ns. Let the mapping correspond directly to the signal indexation, M(dT)= sdT , where dT ∈ ZMd de- notes a data symbol from terminal T ∈ {A, B} and sT is a multi-dimensional constellation space signal vector. 2.2 HDF in a wireless two-way relay channel The HDF strategy is a two-way relaying concept which consists of two independent stages: MAC and BC.Considering thehalf-duplex constraint,HDFhas the minimum number of stages for two-way relay- ing. We assume an accurate time synchronized sys- tem with full CSIR available (synchronization issues are beyond the scope of our paper) and the channel dynamics does not allow us any adaptation strate- gies. In the MAC stage, both A and B transmit at the relay in an interfering manner. The received sig- nal is x= hAsdA + hBsdB +w, (1) where w is AWGN with variance 2N0 per complex dimension, and the channel parameters hA and hB are complex Gaussian random variables with unit variance for flat Rayleigh fading, and have a Rician distributed envelope with a certain Rician factor for Rice fading. The Rician factor is defined as a power ratio between stationary (Line-Of-Sight) and scat- tered components. MaximumLikelihood (ML) based processing at R decodes hierarchical data from the received signal (1) [4], where the hierarchical data is dAB = χ(dA, dB); an exclusive operation is a func- tion χ : Z2Md → ZMdAB , where MdAB denotes the cardinality of exclusive symbol alphabets. The ex- clusive operation meets the exclusive law [7], which guarantees the existence of the invertible function χ−1 : (ZMd , ZMdAB) → ZMd. We assume the mini- mal cardinality exclusive operation Md = MdAB , and based on [9] the exclusive operation is fixed on bit- wiseXOR; χ(dA, dB)= dA ⊕ dB. In the BC stage, R transmits hierarchical data receivedpreviously in the MAC stage; the BC stage is similar to the standard broadcast channel. The terminals decode the desired data from the hierarchical data with the help of its own data and the invertible function, similarly as in NC concepts. 2.3 UMP alphabets It was shown in [9] that the hierarchicalminimal Eu- clidean distance d2min(α)= min k⊕l �=m⊕n ||ukl −umn||2 (2) mostly determines the ML-error performance with CSIR [7] and it is parametrized by α, where uij = sdA + αsdB ∈ C Ns and α ∈ C denote a hierarchi- cal signal in the constellation space and a channel parameter, respectively. In the same paper, the au- thors propose the alphabets and exclusive operations whose minimal distance reaches the upper-bound d2min(α) ! = |α|2δ2min, ∀α ∈ C, |α| ≤ 1, (3) and they are robust w.r.t. parametrization by α; In other words, its performance is parametric, but for all possible parameter values its performance ismax- imal, therefore such alphabets are denoted as Uni- formly Most Powerful (UMP) alphabets. The sym- bol δ2min stands for aminimal distance of the primary alphabet A, δ2min = min k �=l ||sk − sl||2, k, l ∈ ZMd . The initial definition of the UMP alphabet (3) is equiva- lent to the following condition [9] ||sk −sm||2 + |α|2||sl −sn||2− (4) 2|α| |〈sk −sm,sl −sn〉| ≥ |α|2δ2min, for k �= m, l �= n, k ⊕ l �= m ⊕ n and ∀α ∈ C, |α| ≤ 1. 3 Design of UMP Alphabets In contrast to [9], whereUMP frequency-modulation alphabets have been designed, we face a problem of general UMP alphabet design with a natural unit mean symbol energy constraint, ε̄ = 1 Md Md−1∑ i=0 ||si||2. The optimization goal can be formulated as: maximize δ2min (5) s. t. ε̄ =1 and the UMP condition (4) 54 Acta Polytechnica Vol. 51 No. 5/2011 The proposed optimization search has free pa- rameters: alphabet cardinality Md and alphabet di- mensionality Ns. The optimization problem (5) is a standardmin-max problemwhich is conveniently de- scribed as maximize t (6) s. t. t ≤ ||sk −sl||2, k �= l, k, l ∈ ZMd , ε̄ =1 and the UMP condition (4) The optimization problem (6) is recognized to be a convex quadratic continuous optimization problem for which standard optimization techniques converge very well, with reasonable precision [10]. Specif- ically, we have used a Nelder-Mead global-search method with several different starting points of its random number generator, and the results are then refined by the local-search interior-points method. We do not use the direct analytical solution based on the Karush-Kuhn-Tucker conditions due to the large number of constrained conditions (4). We distinguish two cases, a) both terminals use the same alphabet AA = AB and case b) AA �= AB where the terminals use unequal alphabets. Case b) needs to incorporate the fact that optimal alpha- bets should have both minimal distances of AA, AB greater than some threshold; therefore we re-define δ2min = min{||sdA − sd′A|| 2, ||sdB − sd′B || 2}, where dA �= d′A, dB �= d ′ B;dA, d ′ A, dB , d ′ B ∈ ZMd to reflect the additional requirement for unequal alphabets. 3.1 Resulting optimized UMP alphabets The results arepresented inTable 1. In the third col- umn, maximal attainableminimal distances δ2min not constrainedby theUMPcondition are listed as a ref- erence because they form a natural upper-bound at δ2min ofUMPalphabets [9]. The 4th and 5th columns contain the obtained UMP alphabets. Table 1: Numerically optimized UMP alphabets Md Ns δ 2 min, not UMP δ 2 min, AA = AB δ 2 min, AA �= AB 2†) 1 4 4 4 4 1‡) 2 0.4 0.68 4†) 2 2.6 2 2.18 4 3 2.6 2.6 2.6 Alphabets † have the identical spectral efficiency r = log2 Md Ns = 1, where the extra dimensional- ity is taken as extra time-slots and a fair mutual comparison by minimal Euclidean distance can be made; here we need to reflect that the modulation should have the same mean symbol energy per time- slot (i.e. with the same mean power), thus in fact the case (Md = 4, Ns = 2, AA = AB), called a 4ary 2D-UMP alphabet, has δ2min = 4, which is directly equal to BPSK, and the alphabet (Md = 4, Ns = 2, AA �= AB), called a 4ary unequal 2D- UMP alphabet, then has δ2min = 4.36, which is bet- ter by 10log10 4.36 4 � 0.37dB than BPSK, see its hierarchical minimal distance in Figure 2 and the error performance comparison in Fig. 6. Alpha- bets ‡ for both AA = AB and AA �= AB fulfill the UMP condition only for the channel parameter |α| = 1 (we call these weak-UMP alphabets), since 1D-UMPalphabetsmust be binary only [9]. The op- timal alphabet for (Md = 4, Ns = 1, AA = AB) : A = {−2 √ 2 5 , − √ 2 5 , √ 2 5 ,2 √ 2 5 }, see the constella- tion in Figure 3 and its hierarchicalminimal distance depicted in Figure 1, surprisingly resembles 4-ASK Fig. 1: Parametric hierarchical minimal distance of qua- ternary 1D-weak UMP with equal alphabets Fig. 2: Parametric hierarchical minimal distance of qua- ternary 2D-UMP with equal alphabets 55 Acta Polytechnica Vol. 51 No. 5/2011 �1.5 �1.0 �0.5 0.5 1.0 1.5 Re �1.0 �0.5 0.5 1.0 Im Fig. 3: The constellation of 4ary 1D-UMP with equal alphabets resembles standard 4-ASK modulation �1.5 �1.0 �0.5 0.5 1.0 1.5 Re �1.5 �1.0 �0.5 0.5 1.0 1.5 Im �1.5 �1.0 �0.5 0.5 1.0 1.5 Re �1.5 �1.0 �0.5 0.5 1.0 1.5 Im Fig. 4: The constellations of quaternary 1D-UMP with unequal alphabets, alphabets AA and AB , respectively, resembles the scaled versions of standard QPSK constel- lations modulation: A = {− 3 √ 5 , − 1 √ 5 , 1 √ 5 , 3 √ 5 }. The other optimal case ‡ with (Md =4, NS =1) and AA �= AB astonishingly seems to correspond to the scaled ver- sions of two QPSK constellations, see Figure 4. 4 Performance Evaluation In this section, we compare the Symbol Error Rate (SER) of quaternary 1D alphabets: QPSK, 4-ASK and theproposed4ary1D-UMPalphabetswith equal and unequal alphabets ‡. The error performance in Figure 5 is in accordance with our expectations. In the Rayleigh fading channel the UMP condition is not so interesting, rather the overall δ2min is deter- mining. In contrast to Rayleigh fading, it is prefer- able to useUMPalphabets even at the price of lower δ2min in the Rician fading channel (here the Rician factor K =10dB). A remarkable observation is that for sufficiently strong SNR the performance of 4ary 1D-UMP for equal and unequal alphabets is almost identical. 0 5 10 15 20 25 30 35 10 −4 10 −3 10 −2 10 −1 10 0 Symbol error performance of HDF in 2−WRC with Rayleigh/Rice fading Mean Es/N0 [dB] S ym b o l e rr o r ra te QPSK in Rayleigh 4−ASK modSum in Rayleigh 4−ASK bitXOR in Rayleigh 4ary 1D−UMP equal alphabets in Rayleigh 4ary 1D−UMP unequal alphabets in Rayleigh QPSK in Rice K=10dB 4−ASK modSum in Rice K=10dB 4−ASK bitXOR in Rice K=10dB 4ary 1D−UMP equal alphabets in Rice K=10dB 4ary 1D−UMP unequal alphabets in Rice K=10dB Fig. 5: Symbol error rate of quaternary alphabets with a single complex dimension Bit throughput is a relevant performance mea- sure for alphabets with the same spectral efficiency†. In Figure 6 we compare BPSK with Quaternary 2D- UMP alphabets with the case of equal and unequal alphabets. As expected, the quaternary unequal 2D- UMP alphabet outperforms BPSK by ∼ 0.5dB. At the cost of lower spectral efficiency, 4ary 3D-UMP has better error performance. 0 5 10 15 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Throughput of HDF strategy in Rician channel Mean Eb/N0 [dB] B it th ro u g h p u t UMP BPSK in Rice K=10dB 4ary 3D−UMP in Rice K=10dB 4ary 2D−UMP equal alphabets in Rice K=10dB 4ary 2D−UMP unequal alphabets in Rice K=10dB Fig. 6: Bit throughput of the proposed alphabets of HDF strategy in Rice fading with Rician factor K =10dB 5 Conclusions and Discussion We have applied canonical convex constrained non- linear optimization methods for general unrestricted designofUniformlyMostPowerful (UMP)alphabets, 56 Acta Polytechnica Vol. 51 No. 5/2011 which are convenient for the Hierarchical-Decode- and-Forward (HDF) strategy in a wireless 2-way re- lay channel with Channel State Information (CSI) on the receiver side, where the channel conditions do not allow adaptive strategies. UMP alphabets that are robust to parametrization (denoted Uniformly Most Powerful (UMP)) have already been proposed restricting onnon-linearmulti-dimensional frequency modulations. We have re-formulated the optimiza- tion problem and solved by the Nelder-Mead global optimizationmethod, which provided starting points to the interior-points method. The proposed non- binary linear (one dimensional) alphabets outper- form canonical linear alphabets (PSK, ASK, QAM), and the proposed multi-dimensional alphabets out- perform UMP-BPSK modulation. Utilization of the proposed alphabets with suitable mappings on the transitions of convolutional codes (similarly to the concept of trellis codedmodulation), possibly further serially concatenated with an inner code forming a turbo coded system, would be preferable in a practi- cal design. We have supported the idea that unequal alphabets which are made as a power-scaled version of canonical linearmodulations arewell robust to the parametrization problem. This work may serve as a basis for multi-dimensional Multiple-Input Multiple- Output (MIMO)-UMP alphabet design, which will be a topic for future work. Acknowledgement ThisworkwassupportedbytheFP7-ICTSAPHYRE project; by Grant Agency of the Czech Republic, project 102/09/1624; and by the Grant Agency of the Czech Technical University in Prague, grant No. SGS10/287/OHK3/3T/13. About the author Miroslav Hekrdla received his M.Sc. degree in ElectricalEngineering fromtheCzechTechnicalUni- versity in Prague, Czech Republic, in 2009. His re- search interests include nonlinear space-time modu- lation, coding and processing, relay-based wireless communication systems with distributed, coopera- tive and MIMO processing, and aspects of informa- tion theory and channel coding. References [1] Fu, S., Lu,K., Zhang,T.,Qian,Y., Chen,H.-H.: Cooperative wireless networks based on physi- cal layer network coding, Wireless Communica- tions, IEEE, vol. 17, no. 6, 2010, pp. 86–95. [2] Yeung, R. W., Li, S.-Y. R., Cai, N., Zhang, Z.: Network Coding Theory. now Publishers, 2006. [3] Popovski, P., Yomo, H.: Physical network cod- ing in two-way wireless relay channels, In Proc. IEEE Internat. Conf. on Commun. (ICC), jun. 2007, pp. 707–712. [4] Sykora, J., Burr, A.: Hierarchical alphabet and parametric channel constrained capacity re- gions for HDF strategy in parametric wireless 2-WRC, InProc. IEEE Wireless Commun. Net- work. Conf. (WCNC), (Sydney, Australia), apr 2010, pp. 1–6. [5] Cover, T. M., Thomas, J. A.: Elements of In- formation Theory. John Wiley & Sons, 1991. [6] Sykora, J., Burr,A.: Network codedmodulation with partial sideinformationandhierarchicalde- code and forward relay sharing in multisource wireless network, InWireless Conference (EW), 2010 European, 2010, pp. 639–645. [7] Koike-Akino, T., Popovski, P., Tarokh, V.: Op- timized constellations for two-waywireless relay- ingwith physical network coding,SelectedAreas in Communications, IEEE Journal on, vol. 27, jun. 2009, pp. 773–787. [8] Uricar, T., Sykora, J.: Design criteria for hier- archical exclusive codewith parameter-invariant decision regions forwireless 2-way relay channel, EURASIP Journal on Wireless Communica- tions andNetworking, vol.2010, 2010, pp. 1–13. Article ID 921427. [9] Hekrdla, M., Sykora, J.: Channel parameter in- variant network coded FSK modulation for hi- erarchical decode and forward strategy in wire- less 2-way relay channel, In COST 2100 MCM, (Aalborg, Denmark), June 2010, pp. 1–8. TD- 10-11087. [10] Boyd, S., Vandenberghe, L.: Convex Optimiza- tion. New York, NY, USA : Cambridge Univer- sity Press, 2004. Miroslav Hekrdla E-mail: miroslav.hekrdla@fel.cvut.cz Department of Radio Engineering Faculty of Electrical Engineering Czech Technical University in Prague Technická 2, 166 27 Prauge, Czech Republic 57