Multi-user lattice coding for the multiple-access relay channel Chung-Pi Lee, Shih-Chun Lin, Hsuan-Jung Su and H. Vincent Poor Abstract Thispaperconsidersthemulti-antennamultipleaccessrelaychannel(MARC),inwhichmultipleuserstransmit 3 1 messages to a common destination with the assistance of a relay. In a variety of MARC settings, the dynamic 0 2 decode and forward (DDF) protocol is very useful due to its outstanding rate performance. However, the lack of n a good structured codebooks so far hinders practical applications of DDF for MARC. In this work, two classes of J 5 structuredMARC codesare proposed:1) one-to-onerelay-mapperaided multiuser lattice coding(O-MLC), and 2) ] modulo-sum relay-mapper aided multiuser lattice coding (MS-MLC). The former enjoys better rate performance, T I while the latter provides more flexibility to tradeoff between the complexity of the relay mapper and the rate . s c performance. It is shown that, in order to approach the rate performance achievable by an unstructured codebook [ 1 withmaximum-likelihooddecoding,itiscrucialtousea newK-stagecosetdecoderforstructuredO-MLC,instead v 5 of the one-stage decoder proposed in previous works. However, if O-MLC is decoded with the one-stage decoder 3 9 only, it can still achieve the optimal DDF diversity-multiplexing gain tradeoff in the high signal-to-noise ratio 0 . 1 regime. As for MS-MLC, its rate performance can approach that of the O-MLC by increasing the complexity of 0 3 themodulo-sumrelay-mapper.Finally,forpracticalimplementationsofbothO-MLCandMS-MLC,practicalshort 1 : length lattice codes with linear mappersare designed,which facilitate efficient lattice decoding.Simulation results v i X show that the proposed coding schemes outperform existing schemes in terms of outage probabilities in a variety r a of channel settings. I. INTRODUCTION In recent years, cooperative communication has drawn a significant amount of interest as a means of providing spatial diversity when time, frequency or antenna diversities are unavailable due to delay, bandwidth or terminal size constraints, respectively. Cooperative communication techniques for single- sourcenetworkshavebeen extensivelystudiedin termsofrate, outageprobabilityordiversity-multiplexing C.-P. Lee and H.-J. Su are with Department of Electrical Engineering and Graduate Institute of Communication Engineering, National TaiwanUniversity,Taipei,Taiwan, 10617. S.-C.LiniswiththeDepartment of ElectronicandComputer Engineering, National TaiwanUni- versityofScienceandTechnology,Taipei,Taiwan,10607.H.V.PooriswiththeDepartmentofElectricalEngineering,PrincetonUniversity, Princeton, NJ, 08544, USA. Emails: {[email protected], [email protected], [email protected], [email protected]}. 2 tradeoff (DMT) perspectives [1] [2] [3]. However, practical communication networks usually involve more than one source (user), leading to the study of the multiple-access channel (MAC). In this paper, we consider an important multi-user cooperative communication channel, that is, the multi-antenna multiple- access relay channel (MARC). The MARC is a MAC with an additional shared half-duplex relay [4]. It has been shown that the MARC provides a much larger achievable rate region [4] and diversity gain per user [5], compared to those of the MAC. Also, since a single relay is shared by multiple users in the MARC, the extra cost of adding such a relay is acceptable. However, the code design for the MARC needs to jointly consider the codebooks of the multiple users and the relay [4] [6] [7], and is thus not a trivial extension of those for the single-user relay channel or the multiple access channel. The achievable rate region of the MARC has been characterized in [4] [6] and [7]. The decode and forward protocol, which is a special case of the dynamic decode and forward (DDF) protocol [8], was shown to achieve the capacity region of the MARC when the source-relay link is good enough [7], thus having a larger achievable rate region than those of the multiple-access amplify and forward (MAF) [5] and compress and forward (CF) protocols [9]. However, the capacity region of the general MARC remains unknown. The DMT for the MARC with single antenna nodes was studied in [5] [8] and [9]. Although the MAF and CF are both DMT optimal in the high multiplexing gain regime [5] [9], compared with the DDF strategy, they both achieve lower diversity gains in the low to medium multiplexing gain regimes [5] [9]. Moreover, in [5], simulation results show that the DDF protocol yields a better outage probability than that of MAF and CF over a large range of signal-to-noise ratio (SNR), even at the high multiplexing gain regime. Thus we focus on the DDF in this paper due to its good performance in a variety of operation settings. However, previous results in [4]–[9] are based on unstructured random codebooks and maximum likelihood (ML) decoders, and are very difficult to implement in practice. In this paper, we propose structured multiuser lattice coding aided by a relay mapper for the MARC under the DDF protocol, in which each node in the MARC has multiple antennas. To simplify the joint codebook design problem for the multiple users and the relay, we introduce a relay mapper which selects the codeword to be transmitted at therelay to aid the users’transmissions.The relay mapperis a key new ingredient for ourcoding design, which can also help implement the unstructured codebooks in [4], [6], [7] and [8] in practice, and does 3 not appear in [4]–[9]. However, the introduction of the relay mapper makes the decoding much more difficult than that for the MAC [10]. We will see that the one-stage coset decoding proposed in [10] fails to achieve the rate performance of the unstructured codebook with the ML decoding demonstrated in [7]. Instead, we propose a new K-stage coset decoder that achieves the rate performance in [7] by successive cancellation on the multiuser decoding tree. Two classes of relay mapper aided multiuser lattice coding are proposed: 1) one-to-one relay mapper aided multiuser lattice coding (O-MLC), and 2) modulo-sum relay mapper aided multiuser lattice coding (MS-MLC). The first enjoys better rate performance while the second provides more flexibility to tradeoff between the complexity of the relay mapper and the rate performance. With the K-stage coset decoder, the structured O-MLC can achieve the rate performance obtained by the unstructured codebook in [7]. If only one-stage coset decoding is used, we also show that O-MLC is DMT optimal for the DDF, and has better DMT than that in [5] and [9] for the low to medium multiplexing gain regime. As for MS-MLC, when the codomain size of the modulo-sum relay mapper becomes larger, the error performance of MS-MLC approaches that of O-MLC. Moreover, our decoder is no longer a simple lattice decoder as that of [10], since the lattice structure for decoding may be destroyed by the relay mapper. Further, a naive application of the theoretical error analysis in [10] suffers from significant losses in prediction of the achievable rates of proposed coding. We overcome this problem by introducing a new technique for bounding the error probability over the random relay-mapper codebook ensemble. Finally, to implement our theoretical results, we construct practical lattice codebooks with linear mappings for both O-MLC and MS-MLC, which enable the decoder to use the efficient lattice decoding algorithms in [11] and [12]. Compared with codes appearing in previous works [4], [6]–[9] which are difficult to implement, our structured MARC coding can be implemented in practice as we will see below. Some practical MARC code designs were proposed in [13] and [14], but these studies lack theoretical performance analysis. In [13] and [14], an orthogonal protocol was used in which users and the relay must transmitted in different time slots to avoid interference, while our scheme allows them to transmit simultaneously. Moreover, in [14], instead of joint code design, the relay’s transmitted symbol is formed from the users’ symbols with a simple transformation. Due to the above reasons, there are significant losses in the achievable rates and DMTs for the methods in [13] and [14], compared with our schemes. In simulations, we show that our 4 Mu Antennas Hd,1 Phase 1: Phase 2: H r,1 NAntennas Mr Antennas H d,K+1 H r,K H d,K Fig.1. Dynamicdecodeandforward(DDF)fortheK-usermultiple-antennamultiple-accessrelaychannel (MARC),wherePhase1isthe relay’s listening phase while Phase 2 is the relay’s transmitting phase. proposed lattice coding schemes also outperform the schemes in [5] [9] [13] and [14] in terms of outage probabilities. The rest of this paper is organized as follows. Section II introduces the system model and some frequently used notation is summarized in Table I. In Section III, O-MLC and MS-MLC are introduced. In Section IV, we establish the achievable rate region for both O-MLC and MS-MLC and show that O-MLC is DMT optimal. In Section V, simulation results are presented, and Section VI concludes the paper. II. SYSTEM MODEL We consider the K-user multiple-antenna MARC as shown in Fig. 1, in which a relay node is assigned to assist the multiple-access users in transmitting data to a common destination. Each user and the relay is equipped with M and M antennas, respectively, and the destination has N antennas. In the DDF for u r MARC, each codeword spans L slots each consisting of T vector symbols, and the block of LT vector 5 symbols is split into two phases due to the half-duplex constraint at the relay node (i.e., it cannot transmit and receive simultaneously). In Phase 1, the relay receives the signals from the users, then it tries to decode the users’ messages until the decision time ℓ T. Following [8], ℓ T is chosen to be the earliest 1 1 time index such that after ℓ T symbols, the relay can decode the users’ messages without error. If there 1 is no such ℓ ∈{1,...,L−1}, the relay remains silent. Let the M ×M , N×M channel matrices from 1 r u u user i to the relay and the destination be H and H , respectively, which are perfectly known at the r,i d,i corresponding receivers. For Phase 1, the received M ×1 vector of symbols at the relay is∗ r r K r (cid:229) y = H x +n , l =1,2,...,ℓ T (1) r,l r,i i,l l 1 M r u i=1 where r is the received SNR at the relay, x is the M ×1 vector signal transmitted by user i at time r i,l u index l, and the noise at the relay n ∼CN(0,I ) is a Gaussian vector with independent and identically l Mr distributed (i.i.d.) entries. Similar to (1), the received vector symbols at the destination in Phase 1 is r K d (cid:229) y = H x +v , l =1,2,...,ℓ T (2) d1,l M d,i i,l l 1 r ui=1 where r is thereceived SNR and v ∼CN(0,I ) is thenoisevectorat thedestination.In Phase 2 of DDF, d l N based on the decoded messages obtained at the decision time ℓ T, the relay transmits the corresponding 1 coded vector symbols to the destination. The signal received by the destination is then r K r d (cid:229) d y = H x + H x +v , l =ℓ T +1,ℓ T +2,...,LT (3) d2,l M d,i i,l M d,K+1 K+1,l l 1 1 r u i=1 r r where x denotes for the signal transmitted by the relay and H is the channel matrix from the K+1,l d,K+1 relay to destination. As for the (normalized) MARC input power constraint, it is imposed on each user and the relay as E 1 (cid:229)LT |x |2 ≤M , E 1 (cid:229)LT |x |2 ≤M , i=1,...,K (4) i,l u K+1,l r LT LT " l=1 # " l=1 # where the expectation E[] is taken over all codewords in the codebook. ∗Notation:LetAbeaset,thenA∗=A\{0}.Ac denotesthecomplementofA,and|A|denotesthecardinalityofA.ForamatrixM,MH is theconjugatetransposeand|M|isthedeterminant.Weuselog(·)forthelogarithmwithbase2,and×forthedirectproduct.Ann-dimensional reallatticeL isadiscreteadditivesubgroupofRn.ThelatticequantizationfunctionisdefinedasQL (y),argminl ∈L |y−l |fory∈Rn,and the modulo-lattice operation y¯=y modL ,y−QL (y) [15]. The second-order moment of L is defined as s 2(L ), nVf1(L )RVL x2dx, where VL andVf(L ) are given in (T1.2) and (T1.3) in Table I, respectively. Some other frequently used notation is also summarized in Table I. 6 To simplifythepresentationfortheproposed latticecoding scheme,it is usefulto transform ourreceived signal model (1), (2) and (3) into the equivalent real channel model form as in (5) and (6), for the relay and the destination, respectively, y =H x +n (5) relay relay relay relay y =H x +n . (6) dst dst dst dst The equivalent channel for the destination (6) is formed by concatenating the received signal (2) in Phase 1 and (3) in Phase 2, and the 2(KM +M )LT ×1 super signal vector x in (6) is u r dst x , xT,...,xT T, (7) dst 1 K+1 T (cid:2) (cid:3) where x = {xR }T,...,{xR }T with xR = Re{x }T,Im{x }T T; while the 2NLT×1 super received i i,1 i,LT i,l i,l i,l h i signal and noise at the destination y and n(cid:2) in (6) are simila(cid:3)rly defined respectively. The 2NLT × dst dst 2(KM +M )LT super-channel matrix H in (6) is H , Hd,...,Hd , where the 2NLT ×2M LT u r dst dst 1 K+1 u equivalent channel matrix Hd for user i comes from (2) as (cid:2) (cid:3) i r Re{H } −Im{H } Hd , d I ⊗ d,i d,i (8) i M LT   r u Im{Hd,i} Re{Hd,i}     where ⊗ denotes the Kronecker product and i=1,...,K, while the equivalent channel matrix H for K+1 the relay comes from (3) as r Re{H } −Im{H } Hd ,diag I ⊗0 , d I ⊗ d,K+1 d,K+1 , (9) K+1  ℓ1T 2N×2Mr M (L−ℓ1)T   r r Im{Hd,K+1} Re{Hd,K+1}       if 1≤ℓ ≤L−1, where the first 2Nℓ T×2M ℓ T is a zero matrix because the relay is listening in Phase 1 1 r 1 1 (if ℓ =L, Hd ,0 since the relay is silent). As for the equivalent channel for the relay (5), 1 K+1 2NLT×2MrLT it can be similarly obtained from (1) as above, with the dimensions of H being 2M LT ×2KM LT. relay r u We consider two kinds of channel settings, the fixed channel and the slow fading channel. In the fixed channel setting, the channels are deterministic and we use the achievable rate as a performance metric. For the slow fading channel, H and H are random but remain constant over the whole code block. dst relay Since the MARC cannot support any non-zero rate pairs with vanishing error probabilities now, we use the DMT or the outage probabilities as performance metrics. The entries of the channel matrices are assumed to be i.i.d. CN(0,1) when they are slow faded; i.e., we assume Rayleigh fading in this case. 7 III. PROPOSED RELAY-MAPPER AIDED MULTIUSER LATTICE CODING SCHEMES In this section, we specify the proposed multiuser lattice coding schemes for the MARC, i.e., O-MLC and MS-MLC. Each of O-MLC and MS-MLC consists of three building blocks: 1) the relay mapper which decides which codeword to be transmitted at the relay, 2) Loeliger-type nested lattices for the users’ and the relay’s codebooks and 3) a K-stage coset decoder, which generalizes the one-stage decoder of [10]. We first briefly introduce the adopted lattice codebooks. Tailored for them, the relay mappers, the one-to-one mapper y one and the modulo-sum mapper y mod, for O-MLC and MS-MLC, respectively are shown in Section III-B. Then the whole encoding/decoding blocks are introduced in Section III-C. A. Loeliger-type Nested Lattice Codebooks In our code construction, codebooks of the i-th user (1≤i≤K) and the relay (i=K+1) are generated from Loeliger-type nested lattices. To be specific, we introduce the following definitions. Definition 1 (Self-similar nested lattice code): For user i, let L be a 2M LT-dimensional coding lat- C u i tice and L ⊂L be the shaping lattice. The nested lattice codebook is defined as Cnest ,{c¯ :c¯ =c Si Ci i i i i modL ,c ∈L }, where c¯ are the coset leaders [15] of the partition L /L (the set of cosets of L Si i Ci i Ci Si Si relative to L ). The codebook size is |Cnest| = 2RiLT, where the code rate is R bits per channel use Ci i i (BPCU). When L =(2Ri/2Mu)L where (2Ri/2Mu)∈N is the nesting ratio, the nested lattice code Cnest Si Ci i is called a self-similar nested code.† For a Loeliger-type nested-lattice ensemble, the coding lattice L for user i is randomly chosen from the C i Loeliger lattices ensemble which is generated from linear codes CLo [17]. The detailed definition is given i in Definition 5 in the Appendix A-(I). The codebook for the relay is generated similarly as above but with dimension 2M LT. r B. Proposed Relay Mappers The relay mapper y is used to select the codeword (coset leader) c¯ to be transmitted from the relay K+1 (transmitterK+1) according to thecodewords (coset leaders) c¯ , i=1,..,K,of the K users. In other words, i by concatenating the total K+1 codewords as a super one c¯ =[(c¯T,...,c¯T),c¯T ]T =[c¯T,c¯T]T((T1.5) in 1 K K+1 u r Table I), then y (c¯ )=c¯ . Now we introduce the proposed mappers. The first one is as follows. u r Definition 2 (One-to-one mapper): The one-to-one mapper y one:Cnest →Cnest for O-MLC is a one-to- u r one bijective mapping that maps coset leaders in the super-codebook of users Cnest to the relay codebook u † Our results can be easily generalized to the case in which good (but maybe not self-similar) nested codes as in [16] are used. 8 TABLE I LISTOFFREQUENTLYUSEDNOTATION Notation Definition Description (T1.1) Znp n-dimensional finite field over Zp ={0,1,...,p−1}, Prime p finitefield where p is a prime (T1.2) VL Theset of v∈Rn closer to0than toanyother l ∈L , Voronoi Region for a lattice L (T1.3) Vf(L ) Volume of Voronoi region VL in (T1.2) Fundamental Volume (T1.4) vi ni×1 vector vi∈L i consists of the elements of v in Vector for transmitter i, where 1≤i≤ L i, where v=[vT1,...,vTK+1]T is (cid:229) iK=+11ni ×1, and Kcorrespondtotheuserswhilei=K+ L i is transmitter i’s lattice (coding(cid:16)or shapin(cid:17)g) 1 corresponds to the relay (T1.5) vu, vr vu=[vT1,...,vTK]T,vr=vK+1,withvidefinedin(T1.4) Super-vector for all users, and vector for relay (T1.6) CLo CLo×···×CLo ,whereCLoistheLoeligerlinearcode SuperLoeliger-linear-codeofusersand ur 1 K+1 i for transmitter i as in Definition 5 relay (T1.7) L Cu, L Su L C1×···×L CK, L S1×···×L SK Super-coding and shaping lattices of users (T1.8) L , L L , L Super-coding and shaping lattices of Cr Sr CK+1 SK+1 relay (T1.9) L Cur, L Sur L C1×···×L CK+1, L S1×···×L SK+1 Super-coding and shaping lattices of users and relay ((TT11..1110)) v¯p,i,v¯g ii DvefimnoidtioL nSu5r, vi modL Si LMooedliugleorllaattttiicceeoepnesreamtibolne parameters (T1.12) y one, y mod Definition 2, 3 One-to-one Mapper, Modulo-sum Mapper (T1.13) Cnest,Cnest Definition 2 Users’ Codebooks, Relay’s Codebook u r (T1.14) y oD ne, y mD od y oD ne:y oD ne d¯u(w) =d¯r(w), y mD od:y mD od d¯u(w) = Differentialmapperforone-to-oneand d¯r(w) modulo-sum mapper (T1.15) (CCy D ,E)∗ (CCy D ,E)∗,(cid:0){d¯ :d¯ ∈(cid:1)Cy∗D ,Cy D ∈Cy D ,E} (cid:0) (cid:1) DCifferential codewords in ensemble (T1.16) Oy D (13) DyifDf,eErential ambiguity cosets (T1.17) MS Matrix MS , [Mi1,...,Mi|S|] is formed from M = Matrix for users in set S [M1,...,MKM],whereKM isthenumber ofthesubma- trices of M, S={i1,...,i|S|}, 1≤i1<···<i|S|≤KM (T1.18) Rdst (H{S,K+1}) 1log|I + H{S,K+1} HH{S,K+1}| Rateconstraintatthedestinationusing unG dst 2 2(|S|Mu+Mr)LT dst dst unstructured Gaussian codebook (cid:16) (cid:17) (T1.19) Rrelay(HS ) 1log|I + HS HHS | Rate constraint at the relay using un- unG relay 2 2|S|MuLT relay relay structured Gaussian codebook (cid:16) (cid:17) (T1.20) d(r) Thediversity gain rl→im¥ −lologgPrE(r ) given a certain mul- Diversity and multiplexing tradeoff (DMT) tiplexing gain r, where PE(r )$ is the probability that not all users are correctly decoded, r is the received SNR,andr=[r1,...,rK]withri,rl→im¥ Rloi(grr) andRi(r ) is the transmission rate of user i (T1.21) z¯p Apply componentwise modulo p operation on z Modulo p (T1.22) z¯p [(z¯1)Tp1,...,(z¯1)TpK+1], for p = (p1,...,pK+1), z = Modulo vector p [zT,...,zT ]T 1 K+1 (T1.23) g z [g 1zT1,...,g K+1zTK+1]T, for g = (g 1,...,g K+1), z = “Vector” Hadamard product [zT,...,zT ]T 1 K+1 $Instead of PE(r ), the outage probability is used for the calculation of DMT of the relay node in the DDF [3], [8] 9 Cnest. Here Cnest , {c¯ : c¯ = (c modL ),c ∈ L } and Cnest , {c¯ : c¯ = (c modL ),c ∈ L }, r u u u u Su u Cu r r r r Sr r Cr where L and L are defined in (T1.7) while L and L are defined in (T1.8) in Table I. Su Cu Sr Cr Note that |Cnest|=|Cnest| since the aforementioned mapping is bijective. The one-to-one relay mapper r u may require high complexity as the size of super-user codebook |Cnest| becomes large. To reduce the u complexity of the mapper, we introduce another mapping y mod, where the modulo-sum operation is performed at the relay, which is motivated by the XOR operations in network coding [18]. Definition 3 (Modulo-sum mapper): The modulo-sum mapper y mod : Cnest → Cnest for MS-MLC is u r defined as y mod(c¯ ) = (cid:229) K y mod(c¯ ) modL , where y mod :Cnest →Cnest is an injective mapping for u i=1 i i Sr i i r user i with nested user codebook Cnest given in Definition 1, while Cnest and Cnest are given in Definition i u r 2. Note we require that |Cnest|≥max {|Cnest|} to ensure that the mapping y mod in Definition 3 is injective. r i i i The domain dimension of y mod is at most max{|Cnest|} while that of the one-to-one mapper y one is i i (cid:213) K |Cnest|, and y mod has less complexity compared with y one. However, the one-to-one mapper y one i=1 i ensures that two different users’ super-codewords are mapped to different codewords at the relay, and results in better error performance. In contrast, it is possible that two different super-codewords map to the same codeword of the relay due to the modulo-sum operation in y mod, and ambiguity occurs while decoding. C. Encoders and Proposed K-stage Coset Decoders 1) Encoders at the K transmitters and the relay: User i selects the codeword c¯ according to its message i w from the codebook described in Section III-A, and sends signal x into the MARC (5)-(6) (cf. (7)) i i x =([c¯ −u ] modL ) (10) i i i Si where ui is a dither signal uniformly distributed over the Voronoi region VL Si of the shaping lattice L Si ((T1.2) in Table I). From [19], due to the dither ui, xi is uniformly distributed over VL and independent Si of c¯ . To meet the input power constraints (4) as in [16], we let the second-order moment of the shaping i lattice s 2(L )=1/2. Si As for the relay (transmitter K +1), it will first decode the users’ messages, using the operation introducedbelow.Thentherelayselectsitscodewordc¯ accordingtothedecodedtransmittedcodewords K+1 c¯ s using the mappers in Section III-B, and then transmits x as in (10) with the power constraint (4). i K+1 10 k (cid:32)1 (1,1) 1 2 3 k (cid:32)2 (2,1) (2,2) (2,3) 2 3 1 3 1 2 k (cid:32) K (cid:32)3 (3,1) (3,2) (3,3) (3,4) (3,5) (3,6) Fig.2. Themultiuser decoding treefor theK-stagecoset decoding inTableII withK=3.Herefor eachnode, thelabel (k,j) denotes the j-thnodefromtheleftatthek-thstage(Node stageinTableII),whilethenumber iinsideacircledenotes theindexiof theuser assumed tohavebeencorrectlydecodedatthepreviousstage(Node userinTableII).Forexample,whenthecosetdecodinginTableIIisperformed at node (2,1) (the leftmost child node of the root node), user 1 is assumed to have been correctly decoded. The path from root node (1,1) to node (3,1) is illustrated with bolder lines. 2) K-stage coset decoder: We first introduce the decoder at the destination, which generalizes the single stage coset decoder in [10] to the multi-stage one. The coset decoder disregards the boundaries of the codewords and avoids the complicated boundary control [12], which allows for significant complexity reductions compared to ML decoding. Moreover, it facilitates the efficient sphere decoding algorithm [11], [12]. To decode messages from the received signal y in (6), the proposed K-stage coset decoder dst works as in Table II with the detailed steps explained as follows. According to Table II, the decoder first generates the decoding tree as in Step A. An example for K=3 is given in Fig. 2. The decoder will traverse nodes from stage 1 to K in the tree, and produce the candidate codewords. We take the root node in Fig. 2 as an example to explain Steps B.1 and B.2 in Table II. We use the notation c¯(w ) to represent the super-codeword for the K+1 transmitters corresponding to the t