logo

SCIENTIA SINICA Informationis, Volume 49, Issue 7: 853-867(2019) https://doi.org/10.1360/N112018-00160

Low complexity and high performance EP-SU large-scale MIMO detection based on expectation propagation

More info
  • ReceivedJun 19, 2018
  • AcceptedJul 23, 2018
  • PublishedJul 16, 2019

Abstract

In recent years, the detection algorithm based on expectation propagation in high-dimension high-order modulation multiple-input-multiple-output (MIMO) systems shows a huge advantage over the traditional detection algorithm; however, this MIMO-based detection algorithm suffers from the prohibited complexity caused by matrix inversion in each iteration. In this paper, an EP-SU detection algorithm for large-scale MIMO systems is proposed. On the one hand, a successive updating method of information nodes is proposed, which speeds up the efficiency of information updating and avoids the matrix inversion of original EP; on the other hand, the single node update algorithm is optimized, which improves the efficiency and accuracy of information update. Simulation results show that the proposed EP-SU detection algorithm in various large-scale MIMO scenarios exhibits a more outstanding detection performance, faster convergence rate, lower error flat layer, and lower computational complexity compared with traditional EP detection; most importantly, these advantages will be more significant at higher antenna scales.


Funded by

国家自然科学基金(61571083,61501084)


References

[1] Mishra A, S. Y N, Jagannatham A K. SBL-Based Joint Sparse Channel Estimation and Maximum Likelihood Symbol Detection in OSTBC MIMO-OFDM Systems. IEEE Trans Veh Technol, 2018, 67: 4220-4232 CrossRef Google Scholar

[2] Agarwal S, Sah A K, Chaturvedi A K. Likelihood-Based Tree Search for Low Complexity Detection in Large MIMO Systems. IEEE Wireless Commun Lett, 2017, 6: 450-453 CrossRef Google Scholar

[3] Jang H, Nooshabadi S, Kim K. Circular Sphere Decoding: A Low Complexity Detection for MIMO Systems With General Two-dimensional Signal Constellations. IEEE Trans Veh Technol, 2017, 66: 2085-2098 CrossRef Google Scholar

[4] Liu X, Li Y, Li X. Pilot Reuse and Interference-Aided MMSE Detection for D2D Underlay Massive MIMO. IEEE Trans Veh Technol, 2017, 66: 3116-3130 CrossRef Google Scholar

[5] Studer C, Fateh S, Seethaler D. ASIC Implementation of Soft-Input Soft-Output MIMO Detection Using MMSE Parallel Interference Cancellation. IEEE J Solid-State Circuits, 2011, 46: 1754-1765 CrossRef ADS Google Scholar

[6] Felzenszwalb P F, Huttenlocher D R. Efficient belief propagation for early vision. In: Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004. 261--268. Google Scholar

[7] 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

[8] Gao Y, Niu H, Kaiser T. Massive MIMO detection based on belief propagation in spatially correlated channels. In: Proceedings of 11th International ITG Conference on Systems, Communications and Coding, Hamburg, 2017. 1--6. Google Scholar

[9] Narasimhan T L, Chockalingam A. Detection and decoding in large-scale MIMO systems: a non-binary belief propagation approach. In: Proceedings of 2014 IEEE 79th Vehicular Technology Conference (VTC Spring), Seoul, 2014. 1--5. Google Scholar

[10] Minka T P. Expectation propagation for approximate Bayesian inference. UAI Morgan Kaufmann Publishers Inc, 2001. 362--369. Google Scholar

[11] Jakubisin D J, Buehrer R M, Silva C R C M D. BP, MF, and EP for Joint Channel Estimation and Detection of MIMO-OFDM Signals. In: Proceedings of 2016 IEEE Global Communications Conference (GLOBECOM), Washington, 2016. 1--6. Google Scholar

[12] Wei C, Zhang Z C, Liu H P. Expectation-propagation based low-complexity channel estimation for massive MIMO systems. In: Proceedings of 2017 IEEE International Conference on Communications (ICC), Paris, 2017. 1--5. Google Scholar

[13] Zhang D, Mendes L L, Matthe M. Expectation Propagation for Near-Optimum Detection of MIMO-GFDM Signals. IEEE Trans Wireless Commun, 2016, 15: 1045-1062 CrossRef Google Scholar

[14] Ghavami K, Naraghi-Pour M. Noncoherent massive MIMO detection by expectation propagation. In: Proceedings of GLOBECOM 2017 - 2017 IEEE Global Communications Conference, Singapore, 2017. 1--6. Google Scholar

[15] Cé spedes J, Olmos P M, Sá nchez-Ferná ndez M, et al. Improved performance of LDPC-coded MIMO systems with EP-based soft-decisions. In: Proceedings of 2014 IEEE International Symposium on Information Theory, Honolulu HI, 2014. 1997--2001. Google Scholar

[16] Cespedes J, Olmos P M, Sanchez-Fernandez M. Expectation Propagation Detection for High-Order High-Dimensional MIMO Systems. IEEE Trans Commun, 2014, 62: 2840-2849 CrossRef Google Scholar

[17] Wu N, Yuan W, Guo Q. A Hybrid BP-EP-VMP Approach to Joint Channel Estimation and Decoding for FTN Signaling over Frequency Selective Fading Channels. IEEE Access, 2017, 5: 6849-6858 CrossRef Google Scholar

[18] Takeuchi K, Wen C K. Rigorous dynamics of expectation-propagation signal detection via the conjugate gradient method. In: Proceedings of 2017 IEEE 18th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), Sapporo, 2017. 1--5. Google Scholar

[19] Ghavami K, Naraghi-Pour M. MIMO Detection With Imperfect Channel State Information Using Expectation Propagation. IEEE Trans Veh Technol, 2017, 66: 8129-8138 CrossRef Google Scholar

[20] Ghavami K, Naraghi-Pour M. Blind Channel Estimation and Symbol Detection for Multi-Cell Massive MIMO Systems by Expectation Propagation. IEEE Trans Wireless Commun, 2018, 17: 943-954 CrossRef Google Scholar

[21] Sung H, Lee S R, Lee I. Generalized channel inversion methods for multiuser MIMO systems. IEEE Trans Commun, 2009, 57: 3489-3499 CrossRef Google Scholar

[22] Lin C T, Wu W R. QRD-based antenna selection for ML detection of spatial multiplexing MIMO systems: algorithms and applications. IEEE Trans Veh Technol, 2011, 60: 3178-3191 CrossRef Google Scholar

[23] Brent R P, Zimmermann P. Modern Computer Arithmetic. Cambridge: Cambridge University Press, 2010. 18. Google Scholar

  • Figure 1

    (Color online) Conceptual illustration of MIMO system

  • Figure 4

    Comparison of complexity of different MIMO detectors with different antenna scales. (a) $M=N=8$; (b) $M=N=16$; (c) $M=N=32$; (d) $M=N=64$

  • Figure 5

    Convergence of the different MIMO detectors when $M=N=16$, SNR $=15$ dB

  • Table 1   The different operations times for different mimo detectors
    Operations Multiplication Addition/subtraction Exp$(\cdot)$
    BP $L\left(~{24MN~\cdot~{2^{Q/2}}~+~20MN~+~14M}~\right)$ $L\left(~{36MN~\cdot~{2^{Q/2}}~-~4MN~-~2M}~\right)$ $4LMN~{2^{Q/2}}$
    EP(GE) $\begin{array}{lr} L\left(~{4{N^3}~+~4{N^2}~+~10~\cdot~{2^Q}N~+~13N}~\right)~\\ +~3M{N^2}~+~4{N^3}~+~4MN~+~4N \end{array}$ $\begin{array}{lr} L\left(~{4{N^3}~+~10~\cdot~{2^Q}N~+~5N}~\right)~\\ +~M{N^2}~+~4{N^3}~+~2MN~+~4N \end{array}$ $LN{2^Q}$
    EP(QRD) $\begin{array}{lr} L({{{\rm{11}}{N^3}}~\mathord{\left/ ~{\vphantom~{{{\rm{11}}{N^3}}~{\rm{2}}}}~\right. ~\kern-\nulldelimiterspace}~{\rm{2}}}~+~{\rm{9}}{N^2}~+~10~\cdot~{2^Q}N~+~{{{\rm{23}}N}~\mathord{\left/ ~{\vphantom~{{{\rm{23}}N}~{\rm{2}}}}~\right. ~\kern-\nulldelimiterspace}~{\rm{2}}})~\\ +~{\rm{3}}M{N^2}~+~{{{\rm{11}}{N^3}}~\mathord{\left/ ~{\vphantom~{{{\rm{11}}{N^3}}~{\rm{2}}}}~\right. ~\kern-\nulldelimiterspace}~{\rm{2}}}~+~{\rm{4}}MN~+~{\rm{9}}{N^2}~+~{{{\rm{13}}N}~\mathord{\left/ ~{\vphantom~{{{\rm{13}}N}~{\rm{2}}}}~\right. ~\kern-\nulldelimiterspace}~{\rm{2}}} \end{array}$ $\begin{array}{lr} L({{3{N^3}}~\mathord{\left/ ~{\vphantom~{{3{N^3}}~{\rm{2}}}}~\right. ~\kern-\nulldelimiterspace}~{\rm{2}}}~+~{N^2}~+~10~\cdot~{2^Q}N~+~{{7N}~\mathord{\left/ ~{\vphantom~{{7N}~{\rm{2}}}}~\right. ~\kern-\nulldelimiterspace}~{\rm{2}}})~\\ +~M{N^2}~+~{{3{N^3}}~\mathord{\left/ ~{\vphantom~{{3{N^3}}~{\rm{2}}}}~\right. ~\kern-\nulldelimiterspace}~{\rm{2}}}~+~2MN~+~{N^2}~+~{{5N}~\mathord{\left/ ~{\vphantom~{{5N}~{\rm{2}}}}~\right. ~\kern-\nulldelimiterspace}~{\rm{2}}} \end{array}$ $LN{2^Q}$
    EP-SU $\begin{array}{lr} L\left(~{2{N^3}~+~8{N^2}~+~10~\cdot~{2^Q}N~+~11N}~\right)~\\ +~3M{N^2}~+~4{N^3}~+~4{N^2}~+~4MN~+~4N \end{array}$ $\begin{array}{lr} L\left(~{{N^3}~+~6{N^2}~+~10~\cdot~{2^Q}N~+~N}~\right)~\\ +~M{N^2}~+~4{N^3}~+~2MN~+~4N \end{array}$ $LN{2^Q}$
  •   

    Algorithm 1 Expectation propagation

    Initialize all approximation term ${\tilde~t_i}\left(~x~\right)$;

    Compute the posterior of $x$ from ${\tilde~t_i}\left(~x~\right)$: $q\left(~x~\right)~=~{f\left(~x~\right)\prod\limits_i~{{{\tilde~t}_i}\left(~x~\right)}~}~/~{\int~{f\left(~x~\right)\prod\limits_i~{{{\tilde~t}_i}\left(~x~\right)}~{\rm~d}x}~} {\int~{f\left(~x~\right)\prod\limits_i~{{{\tilde~t}_i}\left(~x~\right)}~{\rm~d}x}~}$;

    Repeat until all ${\tilde~t_i}\left(~x~\right)$ converge;

    Choose a factor term ${\tilde~t_i}\left(~x~\right)$;

    Remove ${\tilde~t_i}\left(~x~\right)$ form $q\left(~x~\right)$ to get an 'old' posterior: ${q^{\backslash~i}}\left(~x~\right)~\propto~{{q\left(~x~\right)}~\mathord{\left/ {\vphantom~{{q\left(~x~\right)}~{{{\tilde~t}_i}\left(~x~\right)}}}~\right. \kern-\nulldelimiterspace}~{{{\tilde~t}_i}\left(~x~\right)}}$;

    Combine ${q^{\backslash~i}}\left(~x~\right)$ with ${t_i}\left(~x~\right)$ and minimize the KL divergence to get a new posterior $q'\left(~x~\right)$ with normalizer ${Z_i}$;

    Update ${\tilde~t_i}\left(~x~\right)~=~{{{Z_i}q'\left(~x~\right)}~\mathord{\left/ {\vphantom~{{{Z_i}q'\left(~x~\right)}~{{q^{\backslash~i}}\left(~x~\right)}}}~\right. \kern-\nulldelimiterspace}~{{q^{\backslash~i}}\left(~x~\right)}}$

  • Table 2   Complexity of different operations
    Operations Multiplication Addition/subtraction Exp$(\cdot)$
    Complexity ${k^2}$ $k$ $m{k^2}$
  •   

    Algorithm 2 Original EP for large-scale MIMO detection

    $\bf{Input:}$ ${\boldsymbol{y}},{\boldsymbol{H}},\sigma~_n^2$;

    $\bf{Initialization:}$ $\lambda~_i^{\left(~1~\right)}~=~E_s^{~-~1}$, $\gamma~_i^{\left(~1~\right)}~=~0$, $p~=~64,\beta~~=~0.2$, Iter-times, $\tau$;

    $\bf{Pre\text{-}Processing:}$ ${{\boldsymbol{C}}^{\left(~1~\right)}}~=~{(~{\sigma~_n^{~-~2}{{\boldsymbol{H}}^{\rm~H}}{\boldsymbol{H}}~+~{\rm~diag}\left(~{\boldsymbol{\lambda~}}~\right)}~)^{~-~1}},{{\boldsymbol{u}}^{\left(~1~\right)}}~=~\sigma~_n^{~-~2}{{\boldsymbol{C}}^{\left(~1~\right)}}{{\boldsymbol{H}}^{\rm~H}}{\boldsymbol{y}}$;

    $\bf{for}$ $l~=~1:$ Iter-times // Loop1;

    $\bf{for}$ $i~=~1:N$ // Loop2;

    $\varepsilon~_i^{2(l)}~=~{{{\boldsymbol{C}}^{(l)}\left(~{i,i}~\right)}~/~{(~{1~-~{\boldsymbol{C}}^{(l)}\left(~{i,i}~\right)~\cdot~\lambda~_i^{(l)}}~)}}$, $m_i^{(l)}~=~\varepsilon~_i^{2(l)}(~{{{{\boldsymbol{u}}^{(l)}\left(~i~\right)}~/~{{\boldsymbol{C}}^{(l)}\left(~{i,i}~\right)}}~-~\gamma~_i^{(l)}}~)$;

    ${u'}_i^{(l)}~=~{\rm~E}[~{{p}_r^{(l)}\left(~{{x_i}|{\boldsymbol{y}}}~\right)}~]$, ${\sigma~'}_i^{2(l)}~=~\max~(~{{\rm~V}[~{{p}_r^{(l)}\left(~{{x_i}|{\boldsymbol{y}}}~\right)}~],\tau~}~)$;

    $\bf{if~}$ ${\sigma~'}_i^{2(l)}~>~\varepsilon~_i^{2(l)}$ // Unsuitable approximation;

    $\lambda~_i^{\left(~{l~+~1}~\right)}~=~\lambda~_i^{\left(~{l}~\right)}$, $\gamma~_i^{\left(~{l~+~1}~\right)}~=~\gamma~_i^{\left(~{l~+~1}~\right)}$;

    $\bf{else~~}$ // Normal updating;

    $\lambda~_i^{\left(~{l~+~1}~\right)}~=~\beta~(~{{\sigma~'}_i^{~-~2(l)}~-~\varepsilon~_i^{~-~2(l)}}~)~+~\left(~{1~-~\beta~}~\right)\lambda~_i^{(l)}$, $\gamma~_i^{\left(~{l~+~1}~\right)}~=~\beta~(~{{u'}_i^{(l)}{\sigma~'}_i^{~-~2(l)}~-~m_i^{(l)}\varepsilon~_i^{~-~2(l)}}~)~+~\left(~{1~-~\beta~}~\right)\gamma~_i^{(l)}$ ;

    $\bf{end~~~}$ $\bf{if~~}$

    $\bf{end~}$ $\bf{for}$ // Loop 2;

    ${{\boldsymbol{C}}^{(l+1)}}~=~{(\sigma~_n^{~-~2}{{\boldsymbol{H}}^{\rm~H}}{\boldsymbol{H}}~+~{\rm~diag}({{\boldsymbol{\lambda~}}^{(l+1)}}))^{~-~1}}$, ${{\boldsymbol{u}}^{(l+1)}}~=~\sigma~_n^{~-~2}{{\boldsymbol{C}}^{(l+1)}}\left(~{{{\boldsymbol{H}}^{\rm~H}}{\boldsymbol{y}}{\rm{~+~}}{{\boldsymbol{\gamma~}}^{(l+1)}}}~\right)$ ;

    $\bf{end~}$ $\bf{for}$ // Loop1;

    $\bf{Output:}$ ${{\rm~LLR}_{i,k}}~=~\ln~{\sum\nolimits_{{x_k}~\in~\chi~_i^1}~{p\left(~{{x_k}|{\boldsymbol{y}}}~\right)}~}~/~{\sum\nolimits_{{x_k}~\in~\chi~_i^0}~{p\left(~{{x_k}|{\boldsymbol{y}}}~\right)}~}$

  •   

    Algorithm 3 Proposed EP-SU for large-scale MIMO detection

    $\bf{Input:}$ ${\boldsymbol{y}},{\boldsymbol{H}},\sigma~_n^2$;

    $\bf{Initialization:}$ $\lambda~_i^{\left(~1~\right)}~=~E_s^{~-~1}$, $\gamma~_i^{\left(~1~\right)}~=~0$, $p~=~64,\beta~~=~0.2$, Iter-times, $\tau$;

    $\bf{Pre\text{-}Processing:}$ ${{\boldsymbol{C}}^{\left(~1~\right)}}~=~{(~{\sigma~_n^{~-~2}{{\boldsymbol{H}}^{\rm~H}}{\boldsymbol{H}}~+~{\rm~diag}\left(~{\boldsymbol{\lambda~}}~\right)}~)^{~-~1}},{{\boldsymbol{u}}^{\left(~1~\right)}}~=~\sigma~_n^{~-~2}{{\boldsymbol{C}}^{\left(~1~\right)}}{{\boldsymbol{H}}^{\rm~H}}{\boldsymbol{y}}$;

    $\bf{for}$ $l~=~1:$ Iter-times // Loop1;

    $\bf{for}$ $i~=~1:N$ // Loop2;

    $\varepsilon~_i^{2(l)}~=~{{{\boldsymbol{C}}_{i~-~1}^{(l)}(~{i,i}~)}~/~{(~{1~-~{\boldsymbol{C}}_{i~-~1}^{(l)}\left(~{i,i}~\right)~\cdot~\lambda~_i^{(l)}}~)}}$, $m_i^{(l)}~=~\varepsilon~_i^{2(l)}(~{{{{\boldsymbol{u}}_{i~-~1}^{(l)}\left(~i~\right)}~/{{\boldsymbol{C}}_{i~-~1}^{(l)}\left(~{i,i}~\right)}}~-~\gamma~_i^{(l)}}~)$ ;

    ${u'}_i^{(l)}~=~{\rm~E}[~{{p}_r^{(l)}\left(~{{x_i}|{\boldsymbol{y}}}~\right)}~]$, ${\sigma~'}_i^{2(l)}~=~\max~(~{{\rm~V}[~{{p}_r^{(l)}\left(~{{x_i}|{\boldsymbol{y}}}~\right)}~],\tau~}~)$ ;

    $\bf{if~}$ ${\sigma~'}_i^{2(l)}~>~\varepsilon~_i^{2(l)}$ // Unsuitable approximation;

    $\lambda~_i^{\left(~{l~+~1}~\right)}~=~p~\cdot~{\sigma~'}_i^{2(l)}$, $\gamma~_i^{\left(~{l~+~1}~\right)}~=~\lambda~_i^{\left(~{l~+~1}~\right)}~\cdot~{u'}_i^{(l)}$ ;

    $\bf{else~~}$ // Normal updating;

    $\lambda~_i^{\left(~{l~+~1}~\right)}~=~\beta~(~{{\sigma~'}_i^{~-~2(l)}~-~\varepsilon~_i^{~-~2(l)}}~)~+~\left(~{1~-~\beta~}~\right)\lambda~_i^{(l)}$, $\gamma~_i^{\left(~{l~+~1}~\right)}~=~\beta~(~{{u'}_i^{(l)}{\sigma~'}_i^{~-~2(l)}~-~m_i^{(l)}\varepsilon~_i^{~-~2(l)}}~)~+~\left(~{1~-~\beta~}~\right)\gamma~_i^{(l)}$ ;

    $\bf{end~~~}$ $\bf{if~~}$

    ${\boldsymbol{C}}_i^{(l)}~=~{\boldsymbol{C}}_{i~-~1}^{(l)}{\bf{~-~}}[~{{{\Delta~\lambda~_i^{(l)}{\boldsymbol{C}}_{i~-~1}^{(l)}\left[~i~\right]{\boldsymbol{C}}_{i~-~1}^{(l)}\left\langle~i~\right\rangle~}~/{(~{1~+~\Delta~\lambda~_i^{(l)}~\cdot~{\boldsymbol{C}}_{i-1}^{(l)}(i,i)}~)}}}~]$, ${\boldsymbol{u}}_i^{(l)}\left(~{i~+~1}~\right)~=~{\boldsymbol{C}}_i^{(l)}\left[~{i~+~1}~\right]~\cdot~(~{{{\boldsymbol{H}}^{\rm~H}}{\boldsymbol{y}}/\sigma~_n^2{+\boldsymbol{~\gamma~}}_i^{(l)}}~)$ ;

    $\bf{end~}$ $\bf{for}$ // Loop 2;

    $\bf{end~}$ $\bf{for}$ // Loop1;

    $\bf{Output:}$ ${{\rm~LLR}_{i,k}}~=~\ln~{\sum\nolimits_{{x_k}~\in~\chi~_i^1}~{p\left(~{{x_k}|{\boldsymbol{y}}}~\right)}~}~/~{\sum\nolimits_{{x_k}~\in~\chi~_i^0}~{p\left(~{{x_k}|{\boldsymbol{y}}}~\right)}~}$

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1       京公网安备11010102003388号