about sphere-decoding algorithm

Jenewy

【文件名】:06711@52RD_here-decoding algorithm I. Expected complexity.rar
【格　式】:rar
【大　小】:342K
【简　介】:Abstract—The problem of finding the least-squares solution
to a system of linear equations where the unknown vector is
comprised of integers, but the matrix coefficient and given vector
are comprised of real numbers, arises in many applications:
communications, cryptography, GPS, to name a few. The problem
is equivalent to finding the closest lattice point to a given point and
is known to be NP-hard. In communications applications, however,
the given vector is not arbitrary but rather is an unknown
lattice point that has been perturbed by an additive noise vector
whose statistical properties are known. Therefore, in this paper,
rather than dwell on the worst-case complexity of the integer
least-squares problem, we study its expected complexity, averaged
over the noise and over the lattice. For the “sphere decoding”
algorithm of Fincke and Pohst, we find a closed-form expression
for the expected complexity, both for the infinite and finite lattice.
It is demonstrated in the second part of this paper that, for a wide
range of signal-to-noise ratios (SNRs) and numbers of antennas,
the expected complexity is polynomial, in fact, often roughly cubic.
Since many communications systems operate at noise levels for
which the expected complexity turns out to be polynomial, this
suggests that maximum-likelihood decoding, which was hitherto
thought to be computationally intractable, can, in fact, be implemented
in real time—a result with many practical implications.
Index Terms—Expected complexity, integer least-squares
problem, lattice problems, multiple-antenna systems, NP hard,
sphere decoding, wireless communications.
【目　录】:
I. INTRODUCTION AND PROBLEM STATEMENT
II. OVERVIEW OF METHODS
III. SPHERE DECODING
IV. RANDOM MODEL
V. CONCLUSION

Jenewy

【文件名】:statistics, and applications to communications.rar
【格　式】:rar
【大　小】:417K
【简　介】:Abstract—In Part I, we found a closed-form expression for
the expected complexity of the sphere-decoding algorithm, both
for the infinite and finite lattice. We continue the discussion in
this paper by generalizing the results to the complex version of
the problem and using the expected complexity expressions to
determine situations where sphere decoding is practically feasible.
In particular, we consider applications of sphere decoding to
detection in multiantenna systems.We show that, for a wide range
of signal-to-noise ratios (SNRs), rates, and numbers of antennas,
the expected complexity is polynomial, in fact, often roughly cubic.
Since many communications systems operate at noise levels for
which the expected complexity turns out to be polynomial, this
suggests that maximum-likelihood decoding, which was hitherto
thought to be computationally intractable, can, in fact, be implemented
in real-time—a result with many practical implications.
To provide complexity information beyond the mean, we derive
a closed-form expression for the variance of the complexity of
sphere-decoding algorithm in a finite lattice. Furthermore, we
consider the expected complexity of sphere decoding for channels
with memory, where the lattice-generating matrix has a special
Toeplitz structure. Results indicate that the expected complexity
in this case is, too, polynomial over a wide range of SNRs, rates,
data blocks, and channel impulse response lengths.
Index Terms—Expected complexity, frequency-selective channels,
multiple-antenna systems, polynomial-time complexity,
sphere decoding, wireless communications.
【目　录】:
I. INTRODUCTION
II. GENERALIZATION OF COMPLEXITY RESULTS TO THE COMPLEX CASE
III. EXPECTED COMPLEXITY EXPONENT OF SPHERE DECODING IN FINITE LATTICES: ML DETECTION IN MULTIANTENNA SYSTEMS
IV. VARIANCE OF COMPUTATIONAL COMPLEXITY OF SPHERE DECODING
V. SPHERE DECODING FOR DETECTION IN FREQUENCY-SELECTIVE CHANNELS
VI. REMARKS
VII. CONCLUSION