Abstract—Although lattice reduction aided decoding improves the decoding performance, it has a performance gap to Maximum Likelihood (ML) decoding increasing with the lattice dimension. In view of this, efficient suboptimal decoding algorithms that can narrow the gap are desirable. In this paper, an efficient Best-First Derandomized Sampling (BFDS) decoding algorithm is proposed to achieve near optimal performance. The existing DS algorithm recently proposed adopts breadth-first search and a probability threshold pruning strategy to generate the candidate lattice point list, without making full use of sampling probabilities. Different from the existing DS algorithm, the cumulative sampling probability, which is the product of sampling probabilities of each sampled integer, is taken into account to generate a list by best-first search strategy, which brings complexity reduction compared to the existing DS algorithm without performance loss. Moreover, to enhance the performance, statistical properties of the cumulative sampling probability are considered to build candidate list instead, which yields better performance. It is shown that the proposed BFDS algorithm has much lower complexity compared to the known DS algorithm without performance loss. In addition, the further improved algorithm considering statistical information outperforms those without considering statistical information. 
 

Index Terms—lattice reduction, derandomization sampling, lattice decoding

Cite: Yanhua Sun, Xishuang Chen, Ruizhe Yang, and Yanhua Zhang, "An Efficient Best-First Derandomization Sampling Algorithm for Lattice Decoding," International Journal of Signal Processing Systems, Vol. 4, No. 5, pp. 354-361, October 2016. doi: 10.18178/ijsps.4.5.354-361