Multiplex communications – Communication over free space – Having a plurality of contiguous regions served by...
Reexamination Certificate
2002-05-22
2004-02-10
Marcelo, Melvin (Department: 2663)
Multiplex communications
Communication over free space
Having a plurality of contiguous regions served by...
C375S149000, C375S348000
Reexamination Certificate
active
06690660
ABSTRACT:
BACKGROUND
This invention generally relates to solving linear systems. In particular, the invention relates to using Cholesky approximations to perform a matrix inversion of a Hermitian, block-banded and block Toeplitz matrix to solve linear systems.
In code division multiple access (CDMA) communication systems, multiple communications may be simultaneously sent over a shared frequency spectrum. Each communication is distinguished by the code used to transmit the communication.
In some CDMA communication systems to better utilize the shared spectrum, the spectrum is time divided into frames having a predetermined number of time slots, such as fifteen time slots. This type of system is referred to as a hybrid CDMA/time division multiple access (TDMA) communication system. One such system, which restricts uplink communications and downlink communications to particular time slots, is a time division duplex communication (TDD) system.
Two approaches to receive the communications transmitted within the shared spectrum is single user detection (SUD) and multiuser detection (MUD). SUD is used when all received communications experience the same channel response. This condition typically occurs in the downlink where all communications are transmitted from the base station or in the uplink where only one user transmits at a particular time. In these cases, all the transmitted communications experience a common channel response. To compensate for the common channel response, all of the received signals are passed through a channel equalization,stage. After equalization, the data for each communication is recovered using that communications code.
The single user data detection problem is typically modeled per Equation 1
r=Hs+n
Equation 1
r is the received vector. H is the channel response matrix for all the users. n is the noise vector. s is the spread data symbols as per Equation 2.
s=Cd
Equation 2
C is the spreading codes of all the users' communications and d is the data vector.
Two common approaches to solve Equation 1 are a least squares errors (LSE) solution and a minimum mean squares (MMSE) solution. Equation 3 is the LSE solution.
s
=(
H
H
H
)
−1
H
H
r
Equation 3
(·)
H
is the complex conjugate transpose (Hermitian) operation. Equation 4 is the MMSE solution.
s
=(
H
H
H
+&sgr;
2
I)−
1
H
H
r
Equation 4
&sgr;
2
is the noise variance and I is the identity matrix.
After solving for s, the data vector d is determined by despreading per Equation 5.
d=C
−1
s
Equation 5
In multiuser detection, all the communications' data is determined together. Multiuser detection can be used when communications experience differing or a common channel response(s). A multiuser detector uses the, known or determined, codes of the multiple communications and the determined channel responses to estimate the data of all the communications.
The multiuser detection problem is typically modeled per Equation 6.
r=Ad+n
Equation 6
A is the system response matrix, which is a convolution of the channel response matrix, H, and the code matrix, C.
Two common approaches to solve Equation 6 are a zero-forcing (ZF) solution and a minimum mean square error MMSE solution. Equation 7 is the ZF solution.
d
=(
A
H
A
)
−1
A
H
r
Equation 7
Equation 8 is the MMSE solution.
d
=(
A
H
A+&sgr;
2
I
)
−1
A
H
r
Equation 8
A brute force solution to Equations 3 and 4 for SUD or Equations 7 and 8 have an extremely high complexity. One approach to reduce complexity is Cholesky decomposition. Cholesky decomposition is explained in conjunction with the linear equation of Equations 9 and 10.
p
=(
R
)
−1
x
Equation 9
x=o
H
q
Equation 10
For a ZF solution, R is o
H
o. For a MMSE solution, R is o
H
o+&sgr;
2
I.
Performing a matrix inversion is a complex operation. To reduce the complexity, a Cholesky factor, G, is used when the matrix R is Hermitian block-banded and block Toeplitz. G and its conjugate transpose, G
H
, are upper and lower triangular matrices. The Cholesky factor, G, is per equation 11.
GG
H
=R
Equation 11
After the Cholesky factor, G, is determined, backward substitution is performed to determine y per Equation 12.
y=G
H
q
Equation 12
To determine p, forward substitution is performed per Equation 13.
x=y G
Equation 13
For SUD, p becomes r and q becomes s in Equations 9 and 10. For a ZF solution, R is H
H
H and o
H
is H
H
. For a MMSE solution, R is H
H
H+&sgr;
2
I and o
H
is H
H
.
For MUD, p becomes r and q becomes d in Equations 9 and 10. For a ZF solution, R is A
H
A and o
H
is A
H
. For a MMSE solution, o
H
o is A
H
A+&sgr;
2
I and o
H
is A
H
.
Although the linear system solution based on Cholesky decomposition reduces complexity, determining the Cholesky factor G still involves considerable complexity. To reduce the complexity in determining the Cholesky factor G, an approximate Cholesky factor Ĝ is used. Approaches to determine Ĝ have been to determine a column or row of Ĝ and to replicate that column or row to generate the Ĝ matrix. The approximation of Ĝ may introduce an error into the data detection process. This error may reduce performance of the receiver to an unacceptable level.
Accordingly, it is desirable to have alternate approaches for determining the Cholesky factor.
SUMMARY
Data is to be detected in a wireless communication system. A plurality of communication signals are received. A solution for estimating data of the received communication signals is modeled using a linear system requiring a matrix inversion. Columns or rows of an approximate Cholesky factor are determined. A difference between the determined columns or rows is determined. If the determined difference is less than a threshold, subsequent columns or rows are determined by previously determined columns or rows. The data of the received communication signals is estimated using the approximate Cholesky factor.
REFERENCES:
patent: 6064689 (2000-05-01), Vollmer et al.
patent: 1 065 799 1 (2001-01-01), None
Boariu et al., “The Cholesky-Iterative Detector: A New Multiuser Detector for Synchronous CDMA Systems”, Mar. 2000, IEEE Communications Letters, vol. 4, No. 3, pp. 77-79.*
Haardt et al., “Comparative Study of Joint-Detection Techniques for TD-CDMA based Mobile Radio Systems”, Aug. 2001, IEEE Journal on Selected Areas in Communications, vol. 19, No. 8, pp. 1461-1475.*
H.R. Karimi and N.W. Anderson, “A Novel and Efficient Solution to Block-Based Joint-Detection using Approximate Cholesky Factorization”,Personal, Indoor and Mobile Communications PIMRC' 98, Conference Proceedings, vol. 3, pp. 1340-1345, Sep. 1998, Boston, MA.
Kim Younglok
Zeira Ariela
Do Nhat
InterDigital Technology Corporation
Marcelo Melvin
Volpe and Koenig P.C.
LandOfFree
Adaptive algorithm for a Cholesky approximation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Adaptive algorithm for a Cholesky approximation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive algorithm for a Cholesky approximation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3344704