Deterministic Sampling Decoding: Where Sphere Decoding Meets Lattice Gaussian Distribution

Abstract

In this paper, the paradigm of sphere decoding (SD) based on lattice Gaussian distribution is studied, where the sphere radius $D>0$ in the sense of Euclidean distance is characterized by the initial pruning size $K>1$, the standard deviation $\sigma >0$ and a regularization term ${\rho }_{\sigma ,\mathbf{y}}(\Lambda )>0$ ($\Lambda$ denotes the lattice, $\mathbf{y}$ is the query point). In this way, extra freedom is obtained for analytical diagnosis of both the decoding performance and complexity. Based on it, the equivalent SD (ESD) algorithm is firstly proposed, and we show it is exactly the same with the classic Fincke-Pohst SD but characterizes the sphere radius with $D=\sigma \sqrt{2\ln K}$. By fixing $\sigma$ properly, we show that the complexity of ESD measured by the number of visited nodes is upper bounded by $|S|<nK$, thus resulting in a tractable decoding trade-off solely determined by $K$. In order to further exploit the decoding potential, the regularized SD (RSD) algorithm based on Klein's sampling probability is proposed, which achieves a better decoding trade-off than the equivalent SD by fully utilizing the regularization terms. Moreover, besides the designed criterion of pruning threshold, another decoding criterion named as candidate protection is proposed to solve the decoding problems in the cases of small $K$, which generalizes both the regularized SD and equivalent SD from maximum likelihood (ML) decoding to bounded distance decoding (BDD). Finally, simulation results based on MIMO detection are presented to confirm the tractable decoding trade-off of the proposed lattice Gaussian distribution-based SD algorithms.

arXiv commentsubmitted to IEEE Transactions on Information Theory

References in corpus (9)

• Massive MIMO for Next Generation Wireless Systems
• LLL Reduction Achieves the Receive Diversity in MIMO Decoding
• Low-Complexity Detection/Equalization in Large-Dimension MIMO-ISI Channels Using Graphical Models
• On the Proximity Factors of Lattice Reduction-Aided Decoding
• Faster Projection in Sphere Decoding
• Decoding by Sampling: A Randomized Lattice Algorithm for Bounded Distance Decoding
• Optimized Markov Chain Monte Carlo for Signal Detection in MIMO Systems: an Analysis of Stationary Distribution and Mixing Time
• Decoding by Embedding: Correct Decoding Radius and DMT Optimality
• Decoding by Sampling - Part II: Derandomization and Soft-output Decoding