On the Complexity Distribution of Sphere Decoding

被引:40
作者
Seethaler, Dominik [1 ]
Jalden, Joakim [2 ]
Studer, Christoph [3 ]
Boelcskei, Helmut [4 ]
机构
[1] RobArt, A-4020 Linz, Austria
[2] KTH Royal Inst Technol, Signal Proc Lab, ACCESS Linnaeus Ctr, S-10044 Stockholm, Sweden
[3] Rice Univ, Dept Elect & Comp Engn, Houston, TX 77005 USA
[4] Swiss Fed Inst Technol, Dept Informat Technol & Elect Engn, CH-8092 Zurich, Switzerland
关键词
Closest lattice point problem; complexity distribution; MIMO wireless; random lattices; sphere decoding; LATTICE-BASIS; ALGORITHM; SEARCH; COMMUNICATION; COMPUTATION; DIVERSITY; TRADEOFF;
D O I
10.1109/TIT.2011.2162177
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We analyze the (computational) complexity distribution of sphere decoding (SD) for random infinite lattices. In particular, we show that under fairly general assumptions on the statistics of the lattice basis matrix, the tail behavior of the SD complexity distribution is fully determined by the inverse volume of the fundamental regions of the underlying lattice. Particularizing this result to N x M, N >= M, i.i.d. circularly symmetric complex Gaussian lattice basis matrices, we find that the corresponding complexity distribution is of Pareto-type with tail exponent given by N - M + 1. A more refined analysis reveals that the corresponding average complexity of SD is infinite for N = M and finite for N > M. Finally, for i.i.d. circularly symmetric complex Gaussian lattice basis matrices, we analyze SD preprocessing techniques based on lattice-reduction (such as the LLL algorithm or layer-sorting according to the V-BLAST algorithm) and regularization. In particular, we show that lattice-reduction does not improve the tail exponent of the complexity distribution while regularization results in a SD complexity distribution with tails that decrease faster than polynomial.
引用
收藏
页码:5754 / 5768
页数:15
相关论文
共 50 条
[21]   Tail Behavior of Sphere-Decoding Complexity in Random Lattices [J].
Seethaler, D. ;
Jalden, J. ;
Studer, C. ;
Boelcskei, H. .
2009 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY, VOLS 1- 4, 2009, :729-+
[22]   On the sphere-decoding algorithm I. Expected complexity [J].
Hassibi, B ;
Vikalo, H .
IEEE TRANSACTIONS ON SIGNAL PROCESSING, 2005, 53 (08) :2806-2818
[23]   Reduced-complexity Sphere Decoding Algorithm Based on Adaptive Radius in Each Dimension [J].
Li, Jianping ;
Chen, Si .
2015 IEEE INTERNATIONAL CONFERENCE ON COMPUTER AND COMMUNICATIONS (ICCC), 2015, :309-313
[24]   Lossless Dimension Reduction for Integer Least Squares With Application to Sphere Decoding [J].
Neinavaie, Mohammad ;
Derakhtian, Mostafa ;
Vorobyov, Sergiy A. .
IEEE TRANSACTIONS ON SIGNAL PROCESSING, 2020, 68 :6547-6561
[25]   A Low-Complexity Ordered Sphere Decoding Algorithm for Spatial Modulation [J].
Yang, Ping ;
Xiao, Yue ;
Tang, Qian ;
Zhou, Bin ;
Li, Shaoqian .
IEICE TRANSACTIONS ON COMMUNICATIONS, 2012, E95B (07) :2494-2497
[26]   MIMO fixed-complexity sphere decoding with low-complexity channel matrix ordering [J].
Wang, S.-L. (wangslzxr@gmail.com), 2013, Beijing University of Posts and Telecommunications (36) :41-45
[27]   Orthotope sphere decoding and parallelotope decoding-reduced complexity optimum detection algorithms for MIMO channels [J].
Sweatman, Catherine Z. W. Hassell ;
Thompson, John S. .
SIGNAL PROCESSING, 2006, 86 (07) :1518-1537
[28]   Low-Complexity Soft-Output Sphere Decoding with Modified Repeated Tree Search Strategy [J].
Shieh, Shin-Lin ;
Chiu, Rong-Dong ;
Feng, Shih-Lun ;
Chen, Po-Ning .
IEEE COMMUNICATIONS LETTERS, 2013, 17 (01) :51-54
[29]   Low-Complexity IRS Beamforming Based on Sphere Decoding and Tabu Search [J].
Kimaryo, Seraphin ;
Lee, Kyungchun .
JOURNAL OF COMMUNICATIONS AND NETWORKS, 2023, 25 (03) :299-311
[30]   EXPECTED COMPLEXITY OF SPHERE DECODING FOR SPARSE INTEGER LEAST-SQUARE PROBLEMS [J].
Barik, Somsubhra ;
Vikalo, Haris .
2013 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP), 2013, :4668-4672