A common technique to perform lattice basis reduction is the Lenstra, Lenstra, Lovasz (lll) algorithm. An implementation of this algorithm in real-time systems suffers from the problem of variable run-time and complex...
详细信息
A common technique to perform lattice basis reduction is the Lenstra, Lenstra, Lovasz (lll) algorithm. An implementation of this algorithm in real-time systems suffers from the problem of variable run-time and complexity. This correspondence proposes a modification of the lll algorithm. The signal flow is altered to follow a deterministic structure, which promises to obtain an easier implementation as well as a fixed execution time known in advance. In the case of a maximum number of iterations as it is likely in real-time systems, our modification clearly outperforms the original lll algorithm as far as the quality of the reduced lattice basis is concerned.
Lattice-reduction (LR) technique has been adopted to improve the performance and reduce the complexity in MIMO data detection. This paper presents an improved quantization scheme for LR aided MIMO detection based on G...
详细信息
Lattice-reduction (LR) technique has been adopted to improve the performance and reduce the complexity in MIMO data detection. This paper presents an improved quantization scheme for LR aided MIMO detection based on Gram-Schmidt orthogonalization. For the LR aided detection, the quantization step applies the simple rounding operation, which often leads to the quantization errors. Meanwhile, these errors may result in the detection errors. Hence the purpose of the proposed detection is to further solve the problem of degrading the performance due to the quantization errors in the signal estimation. In this paper, the proposed quantization scheme decreases the quantization errors using a simple tree search with a threshold function. Through the analysis and the simulation results, we observe that the proposed detection can achieve the nearly optimal performance with very low complexity, and require a little additional complexity compared to the conventional LR-MMSE detection in the high E-b/N-0 region. Furthermore, this quantization error reduction scheme is also efficient even for the high modulation order.
Reduction can be important to aid quickly attaining the integer least squares (ILS) estimate from noisy data. We present an improved lll algorithm with fixed complexity by extending a parallel reduction method for pos...
详细信息
Reduction can be important to aid quickly attaining the integer least squares (ILS) estimate from noisy data. We present an improved lll algorithm with fixed complexity by extending a parallel reduction method for positive definite quadratic forms to lattice vectors. We propose the minimum angle of a reduced basis as an alternative quality measure of orthogonality, which is intuitively more appealing to measure the extent of orthogonality of a reduced basis. Although the lll algorithm and its variants have been widely used in practice, experimental simulations were only carried out recently and limited to the quality measures of the Hermite factor, practical running behaviors and reduced Gram-Schmidt coefficients. We conduct a large scale of experiments to comprehensively evaluate and compare five reduction methods for decorrelating ILS problems, including the lll algorithm, its variant with deep insertions and our improved lll algorithm with fixed complexity, based on six quality measures of reduction. We use the results of the experiments to investigate the mean running behaviors of the lll algorithm and its variants with deep insertions and the sorted QR ordering, respectively. The improved lll algorithm with fixed complexity is shown to perform as well as the lll algorithm with deep insertions with respect to the quality measures on length reduction but significantly better than this lll variant with respect to the other quality measures. In particular, our algorithm is of fixed complexity, but the lll algorithm with deep insertions could seemingly not be terminated in polynomial time of the dimension of an ILS problem. It is shown to perform much better than the other three reduction methods with respect to all the six quality measures. More than six millions of the reduced Gram-Schmidt coefficients from each of the five reduction methods clearly show that they are not uniformly distributed but depend on the reduction algorithms used. The simulation results of
For a totally positive algebraic integer alpha not equal 0, 1 of degree d, we consider the set R of values of L(alpha)(1/d) = R(alpha) and the set L of values of M(alpha)(1/d) = Omega(alpha). where L(alpha) is the len...
详细信息
For a totally positive algebraic integer alpha not equal 0, 1 of degree d, we consider the set R of values of L(alpha)(1/d) = R(alpha) and the set L of values of M(alpha)(1/d) = Omega(alpha). where L(alpha) is the length of cc and M(alpha) is the Mahler measure of alpha. In this paper, we prove that all except finitely many totally positive algebraic integers alpha have R(alpha) >= 2.364950 and Omega(alpha) >= 1.721916. The computation uses a family of explicit auxiliary functions. We notice that several polynomials with complex roots are used to construct the functions. We also find eight totally positive irreducible polynomials with absolute length greater than 2.364950 and less than 2.37. (C) 2012 Elsevier Inc. All rights reserved.
In this paper, we present an efficient quantization scheme for lattice-reduction (LR) aided (LRA) MIMO detection using Gram-Schmidt orthogonalization. For the LRA detection, the quantization step applies the simple ro...
详细信息
ISBN:
(纸本)9781479910861;9781479910885
In this paper, we present an efficient quantization scheme for lattice-reduction (LR) aided (LRA) MIMO detection using Gram-Schmidt orthogonalization. For the LRA detection, the quantization step applies the simple rounding operation, which often leads to the quantization errors. Meanwhile, these errors may result in the detection errors. Hence, the motivation of the proposed detection is to further solve the problem of degrading the performance due to the quantization errors in the signal estimation. In this paper, the proposed quantization scheme decreases the quantization errors using a simple tree search with a threshold function. Through the analysis and the simulation results, the proposed detection can achieve the near-ML performance with only a little additional complexity.
The solution of integer ambiguity was regarded as a key technology of precise attitude measuring algorithm, which rapidity and accuracy is influenced by the relevance of ambiguity vector. Since the deficiency of prese...
详细信息
ISBN:
(纸本)9781479900305
The solution of integer ambiguity was regarded as a key technology of precise attitude measuring algorithm, which rapidity and accuracy is influenced by the relevance of ambiguity vector. Since the deficiency of present decorrelation way in LAMBDA algorithm, it was hard to solve. This paper used a sort way to optimization the method of decorrelation, and improved the iterative process of lll and white filter algorithms iterative process improvement. The simulation results shown that the optimized of decorrelation algorithm was suit for the lll and white filter algorithms. And the settlement effects were better to relevance with a higher success rate.
Lattice reduction (LR) and successive interference cancellation (SIC) are two well-known techniques that can be used to improve detection performance over linear detectors for multiple-input multiple-output (MIMO) sys...
详细信息
Lattice reduction (LR) and successive interference cancellation (SIC) are two well-known techniques that can be used to improve detection performance over linear detectors for multiple-input multiple-output (MIMO) systems. However, the LR technique and the SIC technique usually need perfect knowledge on the channel at the receiver, and the use of these techniques with an erroneous channel matrix even worsens the detection performance compared to linear detectors. In this correspondence, we shall show how to modify these techniques to make them robust under imperfect channel estimation. Information needed for the proposed algorithm is moderate;the variance of channel estimation error is the only requirement. Furthermore, our algorithm is not sensitive to the error in the variance of channel estimation error.
Recently, an efficient lattice reduction method, called the effective lll (Elll) algorithm, was presented for the detection of multiinput multioutput (MIMO) systems. In this letter, a novel lattice reduction criterion...
详细信息
Recently, an efficient lattice reduction method, called the effective lll (Elll) algorithm, was presented for the detection of multiinput multioutput (MIMO) systems. In this letter, a novel lattice reduction criterion, called diagonal reduction, is proposed. The diagonal reduction is weaker than the Elll reduction, however, like the Elll reduction, it has identical performance with the lll reduction when applied for the sphere decoding and successive interference cancelation (SIC) decoding. It improves the efficiency of the Elll algorithm by significantly reducing the size-reduction operations. Furthermore, we present a greedy column traverse strategy, which reduces the column swap operations in addition to the size-reduction operations.
The integer least squares (ILS) problem, also known as the weighted closest point problem, is highly interdisciplinary, but no algorithm can find its global optimal integer solution in polynomial time. We first outlin...
详细信息
The integer least squares (ILS) problem, also known as the weighted closest point problem, is highly interdisciplinary, but no algorithm can find its global optimal integer solution in polynomial time. We first outline two suboptimal integer solutions, which can be important either in real time communication systems or to solve high dimensional GPS integer ambiguity unknowns. We then focus on the most efficient algorithm to search for the exact integer solution, which is shown to be faster than LAMBDA in the sense that the ratio of integer candidates to be checked by the efficient algorithm to those by LAMBDA can be theoretically expressed by r(m) where r <= 1 and m is the number of integer unknowns. Finally, we further improve the searching efficiency of the most powerful combined algorithm by implementing two sorting strategies, which can either be used for finding the exact integer solution or for constructing a suboptimal integer solution. Test examples clearly demonstrate that the improved methods can perform significantly better than the most powerful combined algorithm to simultaneously find the optimal and second optimal integer solutions, if the ILS problem cannot be well reduced.
The integer least squares problem is known to be NP-hard, and the algorithms such as the sphere decoding algorithm, which give the optimal solution, are usually too slow. To obtain a solution efficiently one may use o...
详细信息
The integer least squares problem is known to be NP-hard, and the algorithms such as the sphere decoding algorithm, which give the optimal solution, are usually too slow. To obtain a solution efficiently one may use one of the suboptimal algorithms such as the ordered successive interference cancellation (OSIC) algorithm or the lll-aided OSIC algorithm that first modifies the system of equations using the lll algorithm due to Lenstra, Lenstra, and Lovasz. However, these suboptimal algorithms still may not be fast enough depending on the applications. In this paper we present two decoupling techniques to speed-up the lll-aided OSIC algorithm. Our lll-aided decoupled OSIC algorithm, which is applicable to clustered integer least squares problems, has the accuracy comparable to the ordinary lll-aided OSIC algorithm (without decoupling), but is much faster than the OSIC algorithm or the lll-aided OSIC algorithm. Copyright (C) 2011 John Wiley & Sons, Ltd.
暂无评论