SCIENCE CHINA Information Sciences, Volume 62 , Issue 4 : 042302(2019) https://doi.org/10.1007/s11432-018-9637-5

Lattice reduction aided belief propagation for massive MIMO detection

More info
  • ReceivedSep 4, 2018
  • AcceptedNov 12, 2018
  • PublishedDec 29, 2018



[1] Andrews J G, Buzzi S, Choi W, et al. What will 5G be? IEEE J Sel Areas Commun, 2014, 32: 1065--1082. Google Scholar

[2] Boccardi F, Heath R W, Lozano A, et al. Five disruptive technology directions for 5G. IEEE Communications Magazine, 2014, 52: 74--80. Google Scholar

[3] Ji H, Kim Y, Lee J, et al. Overview of full-dimension mimo in lte-advanced pro. IEEE Communications Magazine, 2017, 55: 176--184. Google Scholar

[4] Yang S, Hanzo L. Fifty years of MIMO detection: the road to large-scale MIMOs. IEEE Commun Surv Tutorials, 2015, 17: 1941-1988 CrossRef Google Scholar

[5] Tang C, Tao Y, Chen Y. Approximate iteration detection and precoding in massive MIMO. China Commun, 2018, 15: 183-196 CrossRef Google Scholar

[6] Chen Y, Gao X Q, Xia X G. Robust MMSE precoding for massive MIMO transmission with hardware mismatch. Sci China Inf Sci, 2018, 61: 042303 CrossRef Google Scholar

[7] Hu J, Duman T M. Graph-based detector for blast architecture. In: Proceedings of IEEE International Conference on Communications, Glasgow, 2007. 1018--1023. Google Scholar

[8] Yang J, Zhang C, Liang X, et al. Improved symbol-based belief propagation detection for large-scale mimo. In: Proceedings of IEEE Workshop on Signal Processing Systems (SiPS), Hangzhou, 2015. 1--6. Google Scholar

[9] Long F, Lv T, Cao R, et al. Single edge based belief propagation algorithms for mimo detection. In: Proceedings of the 34th IEEE Sarnoff Symposium, Princeton, 2011. 1--5. Google Scholar

[10] Bickson D, Dolev D. Linear detection via belief propagation. In: Proceedings of the 45th Annual Allerton Conference on Communication, Control, and Computing, Allerton, 2007. 7. Google Scholar

[11] Yoon S, Chae C B. Low-complexity MIMO detection based on belief propagation over pairwise graphs. IEEE Trans Veh Technol, 2014, 63: 2363-2377 CrossRef Google Scholar

[12] Pearl J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. San Francisco: Morgan Kaufmann Publishers Inc., 1988. Google Scholar

[13] Kschischang F R, Frey B J, Loeliger H A. Factor graphs and the sum-product algorithm. IEEE Trans Inform Theor, 2001, 47: 498-519 CrossRef Google Scholar

[14] Montanari A, Prabhakar B, Tse D. Belief propagation based multiuser detection. In: Proceedings of the 43th Allerton Conference on Communications, Control and Computing, Monticello, 2005. 86. Google Scholar

[15] Takahashi T, Ibi S, Sampei S. Design of adaptively scaled belief in large mimo detection for high-order modulation. In: Proceedings of Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC), Kuala Lumpur, 2017. 1800--1505. Google Scholar

[16] Som P, Datta T, Chockalingam A, et al. Improved large-mimo detection based on damped belief propagation. In: Proceedings of IEEE Information Theory Workshop on Information Theory, Cairo, 2010. 1--5. Google Scholar

[17] Bickson D, Dolev D, Shental O, et al. Gaussian belief propagation based multiuser detection. In: Proceedings of IEEE International Symposium on Information Theory, Toronto, 2008. 1878--1882. Google Scholar

[18] 3rd Generation Partnership Project (3GPP). Study on 3d channel model for LTE. TR-36.873. http://www.3gpp.org/DynaReport/36873.htm. Google Scholar

[19] Xu W. Capacity improvement analysis of 3D-beamforming in small cell systems. Sci China Inf Sci, 2018, 61: 022305 CrossRef Google Scholar

[20] Wubben D, Seethaler D, Jalden J. Lattice Reduction. IEEE Signal Process Mag, 2011, 28: 70-91 CrossRef ADS Google Scholar

[21] Wubben D, Bohnke R, Kuhn V, et al. Mmse-based lattice-reduction for near-ml detection of mimo systems. In: Proceedings of ITG Workshop on Smart Antennas, Munich, 2004. 106--113. Google Scholar

[22] Shabany M, Gulak P G. The application of lattice-reduction to the k-best algorithm for near-optimal mimo detection. In: Proceedings of IEEE International Symposium on Circuits and Systems, Seattle, 2008. 316--319. Google Scholar

[23] Peng G, Liu L, Zhou S. Algorithm and Architecture of a Low-Complexity and High-Parallelism Preprocessing-Based K -Best Detector for Large-Scale MIMO Systems. IEEE Trans Signal Process, 2018, 66: 1860-1875 CrossRef ADS Google Scholar

[24] Liu T H. Comparisons of Two Real-Valued MIMO Signal Models and Their Associated ZF-SIC Detectors over the Rayleigh Fading Channel. IEEE Trans Wireless Commun, 2013, 12: 6054-6066 CrossRef Google Scholar

[25] 3rd Generation Partnership Project (3GPP). Physical channels and modulation. TS-36.211. http://www.3gpp.org/DynaReport/36211.htm. Google Scholar

[26] Lenstra A K, Lenstra Jr. H W, Lov\'{a}sz L. Factoring polynomials with rational coefficients. Math Ann, 1982, 261: 515-534 CrossRef Google Scholar

[27] Jensen J. Statistics for Petroleum Engineers and Geoscientists. Amsterdam: Elsevier, 2000. 207. Google Scholar

[28] WINDPASSINGER C. Detection and precoding for multiple input multiple output channels. Dissertation for Ph.D. Degree. Nurnberg: University Erlangen, 2004. 33--36. Google Scholar

[29] Rasmussen C E, Williams C. Gaussian Processes for Machine Learning. Cambridge: The MIT Press, 2006. Google Scholar

[30] Robertson P, Hoeher P, Villebrun E. Optimal and sub-optimal maximum a posteriori algorithms suitable for turbo decoding. Eur Trans Telecomm, 1997, 8: 119-125 CrossRef Google Scholar

[31] 3rd Generation Partnership Project (3GPP). Multiplexing and channel coding. TS-36.212. http://www.3gpp.org/DynaReport/36212.htm. Google Scholar

[32] Rusek F, Persson D, Lau B K, et al. Scaling up mimo: opportunities and challenges with very large arrays. IEEE Signal Processing Magazine, 2013, 30: 40--60. Google Scholar

[33] Studer C, Seethaler D, Bolcskei H. Finite lattice-size effects in mimo detection. In: Proceedings of the 42nd Asilomar Conference on Signals, Systems and Computers, Pacific Grove, 2008. 2032--2037. Google Scholar

  • Figure 1

    Real-domain constellation for 256-QAM.

  • Figure 2

    Pairwise graph for MIMO detection.

  • Figure 3

    Comparison of receiver performance: $12\times~12$, Rayleigh channel.

  • Figure 4

    Comparison of iteration number: $32\times~4$, 3GPP 3D channel, SU.

  • Figure 5

    Comparison of receiver performance: $32\times~4$, 3GPP 3D channel, SU-MIMO. (a) $N_r=32~~(M=16,N=1,P=2),~N_t=4$; (b) $N_r=32~(M=8,N=2,P=2),~N_t=4$.

  • Figure 6

    Comparison of receiver performance: $32\times~4$, 3GPP 3D channel, MU-MIMO (two uplink 2-antenna UEs). protectłinebreak(a) $N_r=32~~(M=16,N=1,P=2),~N_t=4$; (b) $N_r=32~~(M=8,N=2,P=2),~N_t=4$.

  • Table 1   General computational complexity (in terms of equivalent additions)
    Log-domain MRF-BP LRA-BP
    Iteration (38) $2TN_t(2N_t-1)^2~\big|\boldsymbol{\Omega}\big|^2$
    Translation function (20) $80N_r^2N_t$
    LLL reduction 0 $24N_r^2N_t$
    In total $2TN_t(2N_t-1)^2~\big|\boldsymbol{\Omega}\big|^2~+~80N_r^2N_t$ $2TN_t(2N_t-1)^2~\big|\boldsymbol{\Omega}\big|^2~+~104N_r^2N_t$

    Algorithm 1 LRA-BP

    Initialization: $m_{i\to~j}^{(0)}(z_j)~=~\mathrm{log}(|\boldsymbol{\Omega_z}^{(j)}|^{-1})$ for $j=1,2,\ldots,2N_t$. Pre-processing: $\boldsymbol{K}_{\{j,i\}}=\frac12\sigma^2\boldsymbol{I}+\sum_{k\ne~j,i}\boldsymbol{\tilde~h}_k\boldsymbol{t}_k\boldsymbol{t}_k^{\rm~T}\boldsymbol{\tilde~h}_k^{\rm~T}$; $y^\prime_{j|i}=\boldsymbol{\tilde~h}_j^{\rm~T}\boldsymbol{K}^{-1}_{\{j,i\}}\boldsymbol{y}$; $a_{j|i,i}=\boldsymbol{\tilde~h}_j^{\rm~T}\boldsymbol{K}^{-1}_{\{j,i\}}\boldsymbol{\tilde~h}_i$; $\sigma^2_{j|i}=\boldsymbol{\tilde~h}_j^{\rm~T}\boldsymbol{K}^{-1}_{\{j,i\}}\boldsymbol{\tilde~h}_j$. $ p\big(z_j~\big|~z_i,~\boldsymbol{y}~\big) = \sqrt{ \frac {\beta} {2\pi} } {\rm~e}^{d_{i\to~j}(z_j)} $, $\beta=\sigma^2_{j|i}+\sigma_j^{-2}$, $d_{i\to~j}(z_j)=-(\beta~z_j-y^\prime_{j|i}+a_{j|i,i}z_i)^2/(2\beta)$.

    Iteration: For all possible $(i,j)$ pairs repeat message updating as $t=1,2,\ldots,T$ and $\forall~z_j\in~\boldsymbol{\tilde~\Omega_z}^{(j)}$ $m_{i\to~j}^{(t)}(z_j)= \mathop{\mathrm{argmax}}_{z_i\in~\boldsymbol{\tilde~\Omega_z}^{(i)}} \left\{ d_{i\to~j}(z_j)~+~\sum_{k\in~V(i)\setminus~j}{m_{k\to~i}^{(t-1)}(z_i)} \right\}$

    Output: $M(z_j)=\sum_{k\in~V(j)}m_{k\to~j}^{(T)}(z_j),~\forall~z_j\in~\boldsymbol{\tilde~\Omega_z}^{(j)}$ $P(z_j)=\alpha~{\rm~e}^{M(z_j)}$

  • Table 2   Computational complexity with specific parameters (in terms of equivalent additions)
    Rayleigh channel 3GPP 3D channel
    Log-domain MRF-BP LRA-BP Log-domain MRF-BP LRA-BP
    $N_r$ 12 32
    $N_t$ 12 4
    $T$ 5 5 2
    $\big|\boldsymbol{\Omega}\big|$ 16 9 16 9
    Complexity 16389120 5321592 829440 489488