Pipeline structure Schnorr-Euchner Sphere Decoding Algorithm

Xinyu Mao, Jianjun Wu, Haige Xiang

State Key Laboratory of Advanced Optical Communication Systems & Networks, School of Electronics Engineering and Computer Science, Peking University, Beijing, China.

DOI: 10.4236/cn.2013.53B2021                

Abstract

We propose a pipeline structure for Schnorr-Euchner sphere decoding algorithm in this article. It divides the search tree of the original algorithm into blocks and executes the search from block to block. When one block search of a signal is over, the part in the pipeline structure that processes this block search can load another signal and search. Several signals can be processed at the same time in one pipeline. Blocks are arranged to lower the whole complexity in the way that the previously search blocks are the blocks those have more probability to generate the final solution. Simulation experiment results show the average process delay can drop to the range from 48.77% to 60.18% in a 4-by-4 antenna system with 16QAM modulation, or from 30.31% to 61.59% in a 4-by-4 antenna system with 64QAM modulation.

Keywords

Multiple-Input Multiple-Output System; Schnorr-Euchner Sphere Decoding; Pipeline Structure

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	A. J. Paulraj, D. A. Gore, R. U. Nabar and H. Bolcskei, “An Overview of MIMO Communications - A Key to Gigabit Wireless,” Proc. Ieee, Vol. 92, No. 2, pp. 198-218, 2004. doi:10.1109/JPROC.2003.821915
[2]	A. Goldsmith, S. A. Jafar, N. Jindal and S. Vishwanath, “Capacity Limits of MIMO Channels,” Selected Areas in Communicatio IEEE J., Vol. 21, No. 5, 2003, pp. 684-702. doi:10.1109/JSAC.2003.810294
[3]	P. W. Wol-niansky, G. J. Foschini, G. D. Golden and R. A. Valen-zuela, “V-BLAST: An Architecture for Realizing very High Data Rates over the Rich-scattering Wireless Channel,” in 1998 URSI International Symposium on Signals, Systems, and Electronics. Conference Proceedings, Pisa, Italy, 1998, pp. 295-300.
[4]	B. Hassibi and H. Vikalo, “On the Sphere-decoding Algorithm I. Expected Complexity,” Signal Process. IEEE Transacions, Vol. 53, No. 8, 2005, pp. 2806-2818. doi:10.1109/TSP.2005.850352
[5]	C. P. Schnorr and M. Euchner, “Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems,” Mathematical Programming, Vol. 66, No. 1-3, 1994, pp. 181-199. doi:10.1007/BF01581144
[6]	K. Nikitopoulos and G. Ascheid, “Approximate MIMO Iterative Processing With Adjustable Complexity Requirements,” IEEE Transactions Vehicular Technology, Vol. 61, No. 2, 2012, pp. 6390-650. doi:10.1109/TVT.2011.2179324
[7]	X. Mao, S. Ren and H. Xiang, “Adjustable Reduced Metric-First Tree Search,” Proceedings of the 7th International Conference on Wireless Communications, Networking and Mobile Computing, 23-25 Sep. 2011, pp. 1-4.
[8]	T. Cui, S. Han and C. Tellambura, “Probability Distribution Based Nodes Pruning for Sphere Decoding,” IEEE Transactions Vehicular Technology, No. 99, 2012, p. 1.
[9]	J. Ahn, H.-N. Lee and K. Kim, “A Near-ML Decoding with Improved Complexity over Wider Ranges of SNR and System Dimension in MIMO Systems,” Wireless Communications IEEE Transactions, Vol. 11, No. 1, 2012, pp. 33-37. doi:10.1109/TWC.2011.110811.110471
[10]	X. Dai, R. Zou, J. An, X. Li, S. Sun and Y. Wang, “Reducing the Complexity of Quasi-Maximum-Likelihood Detectors Through Companding for Coded MIMO Systems,” Veh. Technol. IEEE Transactions, Vol. 61, No. 3, 2012, pp. 1109-1123. doi:10.1109/TVT.2012.2183008
[11]	B. Shim and I. Kang, “Sphere Decoding With a Probabilistic Tree Pruning,” Signal Process. IEEE Transactions, Vol. 56, No. 10, 2008, pp. 4867-4878. doi:10.1109/TSP.2008.923808
[12]	X. Y. Mao, Y. X. Cheng, L. L. Ma and H. G. Xiang, “Step Reduced K-best Sphere Decoding,” Proceedings of the 76th IEEE Vehicular Technology Conference, Quebec City, Canada, 3-6, Sep. 2012, pp. 1-4.
[13]	J. W. Choi, B. Shim and A. C. Singer, “Efficient Soft-Input Soft-Output Tree Detection via an Improved Path Metric,” Inf. Theory Ieee Trans., Vol. 58, No. 3, 2012, pp. 1518-1533. doi:10.1109/TIT.2011.2177590
[14]	K. J. Choi and K. S. Kim, “Hierarchical Tree Search for Runtime-Constrained Soft-Output MIMO Detection,” IEEE Transactions Vehicular Technology, Vol. 62, No. 2, 2013, pp. 890-896. doi:10.1109/TVT.2012.2227868
[15]	S.-L. Shieh, R.-D. Chiu, S.-L. Feng and P.-N. Chen, “Low-Complexity Soft-Output Sphere Decoding with Modified Repeated Tree Search Strategy,” IEEE Communications Letters, Vol. 17, No. 1, 2013, pp. 51-54. doi:10.1109/LCOMM.2012.112012121728
[16]	A. Schenk, R. F. H. Fischer and L. Lampe, “A Stopping Radius for the Sphere Decoder and Its Application to MSDD of DPSK,” Communications Letters, IEEE, Vol. 13, No. 7, 2009, pp. 465-467. doi:10.1109/LCOMM.2009.090940