Adaptive Sphere Decoding and Radius Selection with Error Analysis in Sphere Decoding

Abstract

<p>Many applications such as communications may be modeled as integer least squares problems. The goal is to find the solution to the integer least squares problem, which could be the encoded integer vector in these applications. From the point of view of lattice space, finding the solution to an integer least squares problem is equivalent to finding the closest lattice point to a given point. Sphere decoding is often applied to the searching of the closest lattice point.</p> <p>An improved sphere decoding method, named adaptive sphere decoding, is discussed in this thesis. This method is examined from various views such as geometric interpretation and tree representation. The algorithm of adaptive sphere decoding is also presented. In addition, an experiment is conducted to show the improvement of performance provided by adaptive sphere decoding over the original sphere decoding.</p> <p>One of the key issues in sphere decoding is the determination of the initial radius of a search hypersphere. For communication applications, the hypersphere radius could be computed from the statistical characteristics of signal noise or deterministically by Babai estimate. However, due to the computational error introduced during floating-point arithmetic, the initial radius computed by the deterministic method may make sphere decoding fail. So, based on the standard computational error analysis of matrix-matrix multiplication and vector-vector addition, we investigate an error analysis for the numerical computation of the initial radius by the deterministic method and propose a revised deterministic method in computing the initial radius by taking the computational error into account in order to make sphere decoding as successful as possible. An experiment of comparing the two methods is conducted and the failure of sphere decoding is eliminated perfectly with the initial radius computed by the revised deterministic method.</p>