TELK OMNIKA , V ol. 16, No . 1, F ebr uar y 2018, pp . 182 188 ISSN: 1693-6930, accredited A b y DIKTI, Decree No: 58/DIKTI/K ep/2013 DOI: 10.12928/telk omnika.v16.i1.7365 182 Lo w Comple xity Multi-User MIMO Detection f or Uplink SCMA System Using Expectation Pr opa gation Algorithm Alv a K osasih* , Onn y Sety a wati , and Rahmad wati Univ ersity of Br a wija y a J alan V eter an, K eta w anggede , K ec. Lo w okw ar u, K ota Malang, J a w a Tim ur 65145, (0341) 5516 11 *Corresponding author , e-mail: alv ak osasih@gmail.com Abstract Sparse code m ultiple access (SCMA), which combines the adv antages of lo w density signature (LDS) and code-division m ultiple access (CDMA), is regarded as one of the pr omising modulation technique candidate f or the ne xt gener ation of wireless systems . Con v entionally , the message passing algor ithm (MP A) is used f or data detector at the rece iv er side . Ho w e v er , the MP A-SCMA cannot be implemented in the ne xt gener ation wireless systems , because of its unacceptab le comple xity cost. Specifically , the comple xity of MP A-SCMA g ro ws e xponentially with the n umber of antennas . Consider ing the use of high dimensional systems in the ne xt gener ation of wireless systems , such as massiv e m ulti-user MIMO systems , the con v en- tional MP A-SCMA is pro hibitiv e . In this paper , w e propose a lo w comple xity detector algor ithm named the e xpectation propagation algor ithm (EP A) f or SCMA. Mainly , the EP A-SCMA solv es the comple xity prob lem of MP A-SCMA and enab les the implementation of SCMA in massiv e MU-MIMO systems . F or instance , the EP A-SCMA also enab les the implemantation of SCMA in the ne xt gener ation wireless systems . W e fur ther sho w that the EP A can achie v e the optimal detection perf or mance as the n umbers of tr ansmit and receiv e antennas g ro w . W e also demonstr ate that a rotation design in SCMA codebook is unnecessar y , which is quite r ather diff erent from the gener al assumption. K e yw or d: SCMA, e xpectation propagation, lo w comple xity , detection, MU-MIMO Cop yright c 2018 Univer sitas Ahmad Dahlan. All rights reser ved. 1. Intr oduction Ne xt gener ation wireless netw or ks are e xpected to satisfy tighter requirements such as massiv e connectivit y , better quality of ser vice , higher throughput, lo w er latency , and lo w er con- trol signaling o v erhead, than the f our th gener ation system. These requirements can be met with ne w w a v ef or m and access designs [1]. As one of the most promising non-or thogonal m ultiple access candidate , sparse code m ultiple access (SCMA) has been addressed to co v er these re- quirements . SCMA f eatures the adv antages of code division m ultiple xing (CDMA) and lo w density signature (LDS) [2]. SCMA is a modulation technique that directly modulates each g roup of binar y data into a comple x m ultidimensional code w ord. This code w ord is tak en from a codebook [1]. At the receiv er side , the message passing algor ithm (MP A) can be implemented to achie v e near optimal detec- tion perf or mance [3]. MP A calculates marginal distr ib ution f or each tr ansmitted signal, conditional on receiv ed signal. Th e completeness probability inf or mation in each MP A’ s node results an out- standing perf or mance of MP A. The sparsity of SCMA code w ord mak es a possibility to implement MP A on SCMA. Ho w e v er , the str ucture of MP A requires a recursiv e f eedbac k message computa- tion on e v er y iter ation. Theref ore , the comple xity of MP A detection g ro ws e xponentially with the codebook siz e . T o solv e the comple xity issue , man y w or ks ha v e been completed either to reduce the comple xity through the codebook design, using compressed sensing str ategy [4, 5], or consider se v er al e xtensions of the MP A, such as max-log MP A [6], SIC MP A [7], and e v en combined e x- tensions of the MP A technique . Ho w e v er , these MP A-based detectors are suff er ing from an e x- Receiv ed September 21, 2017; Re vised October 26, 2017; Accepted No v ember 14, 2017 Evaluation Warning : The document was created with Spire.PDF for Python.
TELK OMNIKA ISSN: 1693-6930 183 EP A  SCMA    E S TI MA TI O N   MO DULE SI GNAL NOI SE EP A  SCMA  DEMO DULA TI O N   MO DULE EXT EXT Q AM  DEM APP ER Q AM  DEM APP ER Q AM  DEM APP ER Figure 1. Bloc k diag r am of uplink scheme SCMA receiv er ponentially incremental comple xity because the str ucture of MP A is still remained. Specifically , if the codebook siz e or the deg ree of freedom significantly increased, the MP As f or SCMA quic kly becomes prohibitiv e due to its computational comple xity . In this w or k, w e solv e the comple xity prob lem of the MP A-SCMA. W e adopt the EP A in [8] and apply the EP A to the SCMA detection. The EP A appro ximates the marginal distr ib ution of the poster ior probability b y using an e xponential f amily . Theref ore , the comple xity of EP A is m uch lo w er than MP A. With the theoretical v er ification, 1) w e e v aluate the EP A-SCMA perf or mance and sho w that the EP A f or SCMA can achie v e near optimal detection perf or mance . 2) W e pro v e that appending a rotation v alue [9, 10 ] in SCMA encoder is unnecessar y . The remo v al of the rotation v alue can omit man y unnecessar y calculations not only in decoding b ut also in encoding. Our h ypotheses are also v er ified b y the e xper imental results . 2. Resear c h Method In this section, w e e xplain our system model and the implementation of EP A in SCMA f or massiv e MU-MIMO systems detection scheme . Our system model is configured based on the or iginal SCMA codebook as in [1]. The implementation of EP A to SCMA will be descr ibed afterw ards . Finally , the comple xity compar ison of our EP A-SCMA and the or iginal MP A-SCMA will be discussed. 2.1. System Model W e consider a SCMA system with U users oper ating on S or thogonal subcarr iers . Each user equipment f eatures N t tr ansmit antennas and the base station (BS) possesses N r receiv e antennas . Let K = U N t and N = S N r . In the SCMA, each tr ansmit symbol x k is tr ansmitted o v er S subcarr iers using d deg ree , and diff erent phase rotation v alues are introduced at diff erent subcarr iers [1]. F or e xample , if S = 4 and d = 2 , the mapping can be k = [ k ;s ] = 2 6 6 4 e j 2 1 e j 2 2 0 0 3 7 7 5 ; h k = 2 6 6 6 4 k ; 1 h k ; 1 k ; 2 h k ; 2 . . . k ;S h k ;S 3 7 7 7 5 : where i 2 [0 ; 1) , h k ;s 2 C N r denote the channel v ector from the k -th tr ansmit antenna to the BS at the s -th subcarr ier . The ref ore , at the BS , the N -dimensional channel output v ector y is e xpressed as y = P K k =1 h k x k + , where is the additiv e white Gaussian noise (A WGN) v ector with z ero mean and co v ar iance matr ix 2 I . H = h 1 h 2 h K ; x = x 1 x 2 x K T : Finally , w e obtain y = Hx + : (1) Lo w Comple xity Multi-User MIMO Detection f or Uplink SCMA System ... (Alv a K osasih) Evaluation Warning : The document was created with Spire.PDF for Python.
184 ISSN: 1693-6930 The input-output relationship of the SCMA can be vie w ed as a MIMO comm unication system with K inputs and N outputs . 2.2. EP A f or SCMA Alg. 1: EP A-SCMA Algor ithm Initialization: 0 B ! A = 0 ; 0 B ! A = 1 E s I ; d ( Q ) = diag( Q ); f or t = 1 : T max do Estimation Module: (1) Compute the a poster ior i mean/v ar iance of x A : v p ost A;t = t = 2 H H H + d ( t 1 B ! A ) 1 (2a) x p ost A;t = t 2 H H y + t 1 B ! A (2b) (2) Compute the e xtr insic mean/v ar iance of x A : v ext A;t = 1 d ( t ) d ( t 1 B ! A ) 1 (3a) x ext A;t = d ( v t A ! B ) t d ( t ) t 1 B ! A (3b) Demodulation Module: (3) Compute the a poster ior i mean/v ar iance of x B : x p ost B ;t   E f x j x ext A;t ; v ext A;t g (4a) v p ost B ;t   V ar f x j x ext A;t ; v ext A;t g (4b) (4) Compute the e xtr insic mean/v ar iance of x B : v ext B ;t = t B ! A =   1 v p ost B ;t 1 v ext A;t ! 1 (5a) x ext B ;t = t B ! A =   x p ost B ;t x p ost B ;t x ext A;t v ext A;t ! 1 (5b) end The input v ector x to the equiv alent MIMO channel H is a combined constellation 1 K , where k is the set of constellation of the th tr ansmission. Our target is to detect tr ansmitted signals x o v er the receiv ed signals y in a giv en full kno wledge of channel matr ix H . The comple xity of the optimal detection g ro ws e xponentially with the siz e of the tr ansmission and thus becomes prohibitiv e . T o solv e this prob lem, w e adopt the EP A in Alg.1 which is an iter ativ e algor ithm. As der iv ed in our system model, the input-output relationship of SCMA can be configured as a MIMO comm unication system. Theref ore , w e can directly apply the EP A algor it hm to the SCMA detector side . The detail of the EP A algor ithm is the same as [8] and not mentioned in this paper due to limited space . As sho wn in Figure 1b , the EP A-SCMA can be divided into tw o modules , i.e ., estima- tion and demodulation. In the estimation module , giv en the channel model (1), w e estimate x that minimiz es the mean squared error (MMSE) giv en pr ior kno wledge of x . Let ( x ext A ; v ext A ) and ( x p ost B ; v p ost B ) be the input -output of demodulation module . The e xpectation and v ar iance of the poster ior estimator are computed as giv en b y x p ost B   E f x j x ext A ; v ext A g , v p ost B   V ar f x j x ext A ; v ext A g : (6) TELK OMNIKA V ol. 16, No . 1, F ebr uar y 2018 : 182 188 Evaluation Warning : The document was created with Spire.PDF for Python.
TELK OMNIKA ISSN: 1693-6930 185 Specifically , consider ing that j k j = M , the e xpectations in (6) are wit h respect to P ( x k j x A;k ) , which can be obtained b y the Ba y es r ule P ( x k j x A;k ) = P ( x A;k j x m ) P x ( x m ) P ( x A;k ) ; (7) where P ( x A;k j x m ) P x ( x m ) = 1 M 1 v A;k exp j x A;k x m j 2 v A;k ; (8) P ( x A;k ) = 1 M 1 v A;k M X m =1 exp j x A;k x m j 2 v A;k : (9) W e then emplo y the perf or mance analysis fr ame w or k in [11] to de v elop the state e v olution (SE) of the EP A-SCMA which is der iv ed from a large scale system. F or a large scale system, the e xtr insic v alue of each EP A-SCMA module can be appro ximated b y their a v er age v alues , respectiv ely . As giv en in [8], the input-output tr ansf er function of estimation module can be der iv ed from linear mean square error estimator , that is v A = K 1 tr ( 2 H H H + v 1 B I ) 1 1 v 1 B : (10) where , tr fg denotes tr ace oper ation, v A is a v er age e xtr insic v alue of estimation module , and v B is a v er age e xtr insic v alue of demodulation module . Fur ther more , v A can also be regarded as the SNR of the equiv alent scalar additiv e white gaussian noise (A WGN) channel i.e . y = x + v A . Consistent with our assumption, where v B and v A are the a v er age e xtr insic v alues of demodu- lation and estimation EP A-SCMA mod ules , equiv alent A WGN channel can be considered as a k -th channel under K users which has an identical channel v alue f or e v er y k -th user . Similar ly , w e define v as the scalar v ersion of (6). Theref ore , v can be calculated b y v = V ar f x j x A ; v A g = E fj x E f x j x A ; v A gj 2 g ; where the e xpectation is with respect to P ( x j x A ) giv en b y (7). Ref err ing to [8], v B can be defined as v B = v 1 v A 1 : (11) The iter ation of the E P A is identical to the SE in (10) an d (11) whose fix ed points ha v e MSE consistent with the MMSE from [12]. Moreo v er , the iter ation of estimation and demodulation module can be tr aced from (10) and (11) without iter ating the entire algor ithm. Finally , w e compare the computational comple xity of the three diff erent algor ithms: MP A, threshold-MP A [13], and EP A. Threshold-MP A-SCMA is recogniz ed as a one of successful re- cently w or k to reduce the computational comple xity of the or iginal MP A-SCMA. T ab le 1. Computational comple xity compar ison. Compar ison Setting1 M = 4 , N = 128 , K = 196 , I t =10, d =2 MP A O (7 : 63617 X 10 64 ) Threshold-MP A O (5 : 71086 X 10 64 ) EP A O (62914560) Compar ison Setting2 M = 4 , N = 64 , K = 96 , I t =10, d =2 MP A (BL) O (1 : 24128 X 10 35 ) Threshold-MP A O (9 : 25765 X 10 34 ) EP A O (7864320) T ab le 1 sho ws the comple xity orders of tw o settings . Let I t denotes the n umber of It- er ation. The implementation of MP A is prohibitiv e . Although threshold-MP A can decrease ap- pro ximately 25% of the comple xity , its implementation remains prohibitiv e . The EP A f or SCMA successfully handles these situations , and its comple xity is less than 10 20 % of the MP A com- ple xity . Lo w Comple xity Multi-User MIMO Detection f or Uplink SCMA System ... (Alv a K osasih) Evaluation Warning : The document was created with Spire.PDF for Python.
186 ISSN: 1693-6930 0 2 4 6 8 10 12 14 SNR(dB) 10 -4 10 -3 10 -2 10 -1 10 0 BER EPA SCMA 4X6, MU-MIMO 32X16 EPA SCMA 4X6, MU-MIMO 64X32 EPA SCMA 4X6, MU-MIMO 128X64 EPA SCMA 4X6, MU-MIMO 256X128 Theoretical BER (State Evolution) Figure 2. P erf or mance analysis of EP A-SCMA 3. Result and Anal ysis The sim ulation par ameters are set as f ollo ws: the codebook siz e is M = 4 point codebook proposed in [2], the n umber of subcarr ier is S = 4 , and the n umber of m ulti-antennas users is U = 6 . Each user has tr ansmit antennas N t = 2 and the BS has receiv er antennas N r = 4 . As the SE is der iv ed from a large scale system, w e increase the tr ansmit antennas and receiv er antennas in the f our f ollo wing settings: 1) N t = 16 , N r = 32 , 2) N t = 32 , N r = 64 , 3 ) N t = 64 , N r = 128 , 4) N t = 128 , N r = 256 . In this w a y , w e can obser v e the BER perf or mance of EP A- SCMA from small to the large scale system. Channel used in this sim ulation is a nor mal r andom channel model. The rotation r ule in codebook design is based on the codebook design proposed in [9]. Ob viously , in small scale system as presented in Figure 3, MP A-SCMA which can be vie w ed as an optimal detector has a better perf or mance than EP A-SCMA. Ho w e v er , as the n um- bers of tr ansmit and receiv e antennas g ro w , EP A-SCMA perf or mance impro v es significantly . Fur- ther more , EP A-SCMA successfully can match the theoretical BER perf or mance as illustr ated in Figure 2. As pro v ed in [12], the theoretical perf or mance can be vie w ed as near optimal perf or- mance . Theref ore , the EP A-SCMA can achie v e the near optimal perf or mance . At t he same time , under the par ameter setting in Figure 2, w e cannot e v aluate the MP A-SCMA perf or mance . W e indicate that the comple xity of MP A-SCMA increases e xtremely high, and becomes prohibitiv e to be implemented. F or this reason, there is no MP A-SCMA BER perf or mance can be presented in Figure 2 as MP A-SCMA f ails to o v ercome its comple xity prob lem. Figure 3 also pro v es the argument on the need of putting a rotation v alue in the SCMA codebook as proposed in [1], [2], and [9]. Figure 3 descr ibes that the BER perf or mance betw een the EP A-SCMA and MP A-SCMA without rotation is identical to that wit h rotation. Consequently , the rotation v alue is unnecessar y f or the uplink scheme SCMA system. T o suppor t this argument, let the channel response on diff erent users are v ar y and i = 0 indicating that no rotation is included. Channel v ector h k ;s f or all k and s remains distinct. Theref ore , no data interf erence occurs . 4. Conc lusion In this paper , w e pro pose the EP A as the SCMA data detection which is solv ed the com- ple xity prob lem of or iginal MP A-SCMA. W e proof that our EP A-SCMA can match the theoretical analysis , thus our EP A-SCMA achie v e the near optimal perf or mance . W e also sho w that the rotation design in codebook is unnecessar y in the uplink SCMA. TELK OMNIKA V ol. 16, No . 1, F ebr uar y 2018 : 182 188 Evaluation Warning : The document was created with Spire.PDF for Python.
TELK OMNIKA ISSN: 1693-6930 187 0 2 4 6 8 10 12 14 SNR(dB) 10 -4 10 -3 10 -2 10 -1 10 0 BER MPA SCMA with rotation 4X6, MU-MIMO 4X2 MPA SCMA no rotation 4X6, MU-MIMO 4X2 EPA SCMA with rotation 4X6, MU-MIMO 4X2 EPA SCMA no rotation 4X6, MU-MIMO 4X2 Figure 3. SCMA rotation and no rotation perf or mance compar ison Ac kno wledg ement W e thank Prof essor Chao-Kai W en f or His guidance and suppor t. This w or k is suppor ted b y Labor ator y of Wireless Comm unication T echnology , National Sun Y at-sen Univ ersity , Kaohsi- ung 804, T aiw an. Ref erences [1] M. T aherzadeh, H. Nik opour , A. Ba y esteh, and H. Baligh, “Scma codebook design, ” in 2014 IEEE 80th V ehicular T echnology Conf erence (VTC2014-F all) , Otta w a, Ontar io , Canada, Sept 2014, pp . 1–5. [2] H. Nik opour and H. Baligh, “Sparse code m ultiple access , ” in 2013 IEEE 24th A nn ual In- ter national Symposium on P ersonal, Indoor , an d Mobile Radio Comm unications (PIMRC) , Otta w a, Ontar io , Canada, Sept 2013, pp . 332–336. [3] J . Ni and S . T atik onda, “Analyzing product-f or m stochastic netw or ks via f actor g r aphs and the sum-product algor ithm, ” IEEE T r ansactions on Comm unications , v ol. 55, no . 8, pp . 1588– 1597, A ug 2007. [4] A. F . Mor abito , “P o w er synthesis of mask-constr ained shaped beams through maximally- sparse planar arr a ys , ” T elk omnika (T elecomm unication Computing Electronics and Control) , v ol. 14, no . 4, pp . 1217–1219, 2016. [5] G. S . A. F . Mor abito , A. R. Lagan and T . Iser nia, “Mask-constr ained po w er synthesis of max- imally sparse linear arr a ys through a compressiv e-sensing-dr iv en str ategy , ” Jour nal of Elec- tromagnetic W a v es and Applications , v ol. 29, no . 10, pp . 1384–1396, 2015. [6] S . Zhang, X. Xu, L. Lu, Y . W u, G. He , and Y . Chen, “Sparse co de m ultiple access: An energy efficient uplink approach f or 5g wireless systems , ” in 2014 IEEE Global Comm unicati ons Conf erence , Shanghai, China, Dec 2014, pp . 4782–4787. [7] J . Zou, H. Zhao , and W . Zhao , “Lo w-comple xity interf erence cancellation receiv er f or sparse code m ultiple access , ” in 2015 IEEE 6th Inter national Symposium on Micro w a v e , Antenna, Propagation, and EMC T echnologies (MAPE) , San Diego , USA, Oct 2015, pp . 277–282. [8] J . Cspedes , P . M. Olmos , M. Snchez-F er nndez, and F . P erez-Cr uz, “Expectation propagation detection f or high-order high-dimensional mimo systems , ” IEEE T r ansactions on Comm uni- cations , v ol. 62, no . 8, pp . 2840–2849, A ug 2014. [9] D . Cai, P . F an, X. Lei, Y . Liu, and D . Chen, “Multi-dimensional scma codebook design based on constellation rotation and inter lea ving, ” in 2016 IEEE 83rd V ehicular T echnology Conf er- ence (VTC Spr ing) , Chengdu, China, Ma y 2016, pp . 1–5. Lo w Comple xity Multi-User MIMO Detection f or Uplink SCMA System ... (Alv a K osasih) Evaluation Warning : The document was created with Spire.PDF for Python.
188 ISSN: 1693-6930 [10] J . v an de Beek and B . M. P opo vic , “Multiple access with lo w-density signatures , ” in GLOBE- COM 2009 - 2009 IEEE Global T elecomm unications Conf erence , Kista, Sw eden, no v 2009, pp . 1–6. [11] X. Y uan, J . Ma, and L. Ping, “Energy-spreading-tr ansf or m based mimo systems: Iter ativ e equalization, e v olution analysis , and precoder optimization, ” IEEE T r ansactions on Wireless Comm unications , v ol. 13, no . 9, pp . 5237–5250, Sept 2014. [12] M. Ba y ati and A. Montanar i, “The dynamics of message passing on dense g r aphs with ap- plications to compressed sensing, ” IEEE T r ansactions on Inf or mation Theor y , v ol. 57, no . 2, pp . 764–785, F eb 2011. [13] L. Y ang, Y . Liu, and Y . Siu, “Lo w comple xity message passing algor ithm f or scma system, ” IEEE Comm unications Letters , v ol. 20, no . 12, pp . 2466–2469, Dec 2016. TELK OMNIKA V ol. 16, No . 1, F ebr uar y 2018 : 182 188 Evaluation Warning : The document was created with Spire.PDF for Python.