Efficient sphere decoding
Marco Falke · OPen Access Repositorium der Universität Ulm (OPARU) (Ulm University) · 2014
The continuously growing amount of wireless data can only be delivered by making use of computationally intense technology. Such technology results in a higher spectral efficiency and consequently in a higher data throughput. It is common to decode a received signal with the maximum likelihood approach. One implementation of the maximum likelihood strategy is called sphere decoder. The goal of this bachelor’s thesis is to give a profound background on the sphere decoder by discussing the Babai nearest plane algorithm, the Pohst strategy and the Schnorr-Euchner-Enumeration. The latter is a combination of the first two, proposed by Agrell et al. in 2002 ("Closest point search in lattices") by giving a pseudocode implementation of the sphere decoder. Furthermore, the improvements proposed by Ghasemmehdi and Agrell in 2011 ("Faster recursions in sphere decoding") are explained and applied to the pseudocode implementation of the sphere decoder. Derivatives of the old and new implementation were created by Ghasemmehdi and Agrell to solve not only infinite lattices but also finite ones. Also modifications to the algorithms were made to take the inverse of the generator matrix as input. Alongside the pseudocode implementation of all eight algorithms, an out-of-the-box GNU Octave and Matlab implementation is provided in this thesis. Finally, the complexity of each algorithm is determined for different signal-to-noise ratios and different constellations up to dimension 24. It is shown that the proposed improvements have a substantial effect on the complexity of the algorithms. Even in the worst case (2-ASK constellation at 20 dB SNR) it is at least 20 % easier in average to decode a given vector at dimension 24 with the new algorithms compared to the old ones. Also a proposal is made which of the new algorithms to choose when the lattice dimension and signal-to-noise ratio is given.