MULTIUSER DETECTOR FOR VARIABLE SPREADING FACTORS

DETECTEUR MULTI-UTILISATEUR POUR FACTEURS D'ETALEMENT VARIABLES

English Abstract

A multiuser detector that detects and decodes synchronous or asynchronous CDMA subchannels having different spreading factors with reduced computational complexity. The multiuser detector is compatible with ZF-BLE, MMSE, decorrelating detectors and the like using Cholesky decomposition to minimize numeric operations. The system and method arranges the columns of system transmission response matrices representing the response characteristics of individual users into a total system transmission response matrix which represents a plurality of matched-filter responses for a given block of received data. The invention in conjunction with Cholesky decomposition reduces the number of required mathematic operations prior to parallel matched filtering.

French Abstract

Détecteur multi-utilisateur à complexité de calcul réduite qui détecte et décode des voies intermédiaires d'AMRC synchrones ou asynchrones à facteurs d'étalement différents. Le détecteur multi-utilisateur est compatible avec des solutions ZF-BLE ou MMSE, des détecteurs de décorrélation et d'autres moyens semblables utilisant la décomposition de Cholesky pour réduire les opérations numériques. Le système et la méthode permettent d'organiser les colonnes de matrices de réponse de transmission de système correspondant aux caractéristiques de réponse d'utilisateurs individuels dans une matrice totale de réponse de transmission de système qui représente plusieurs réponses de filtre adapté pour chaque bloc de données reçues. L'invention, en employant la décomposition de Cholesky, réduit le nombre d'opérations mathématiques requises avant l'utilisation d'un filtre adapté parallèle.

Claims

WHAT IS CLAIMED IS:
1. A method of detecting in a received code division multiple access
(CDMA) communication a plurality of data communications each corresponding
with a specific user, comprising:
(a) acquiring impulse response estimates for symbols within each data
communication;
(b) constructing a system transmission response matrix for each of the user
data communications from said impulse response estimates;
(c) assembling a well-banded total system transmission response matrix
from all of said user system transmission response matrices;
(d) filtering said received CDMA communication with said total system
transmission response matrix yielding a matched filter output;
(e) forming an objective matrix based upon said total system transmission
response matrix;
(f) inverting said objective matrix;
(g) multiplying said matched filter output with said inverted objective
matrix yielding estimated user data;
(h) descrambling said estimated user data yielding user data corresponding
to the plurality of data communications; and
(i) repeating steps (a)-(h) for a next CDMA communication.
-32-

2. The method according to claim 1 wherein step (c) comprises:
(c1) examining each of said system transmission response matrix columns
for vector top and bottom offsets;
(c2) assigning an index value for each of said examined columns based
upon said columns having a small top offset with a large bottom offset to said
columns having a large top offset with a small bottom offset, respectively;
and
(c3) arranging said examined total system transmission response matrix
columns in accordance with said index values according to increasing
magnitude.
3. The method according to claim 2 wherein step (c2) comprises:
(c2a) obtaining a difference between top offsets and a difference between
bottom offsets for two columns if a first column has a larger top offset and a
larger
bottom offset than a second column;
(c2b) comparing said top offset difference and said bottom offset difference
yielding a greater top or bottom offset difference; and
(c2c) if the top offset difference is greater than the bottom offset
difference,
assigning the lower index value for said column with a larger top offset
difference.
4. The method according to claim 3 wherein step (c2b) comprises:
(c2b1) if the bottom offset difference is greater than the top offset
difference, assigning the lower index value for said column with a larger
bottom
offset difference.
-33-

5. The method according to claim 4 wherein forming said objective
matrix is performed by a decorrelator.
6. The method according to claim 4 wherein forming said objective
matrix is performed by a minimum mean square error detector.
7. The method according to claim 4 wherein forming said objective
matrix is performed by a zero-forcing block linear equalizer.
8. The method according to claim 1 wherein step (c) comprises:
(c1) grouping said system transmission response matrices according to like
spreading factors;
(c2) assembling spreading factor group transmission response matrices from
said groups of system transmission response matrices with like spreading
factors;
and
(c3) forming a base total system response matrix from a common spreading
factor group matrix having the lowest spreading factor.
9. The method according to claim 8 further comprising:
(c4) choosing one spreading factor group transmission response matrix for
consideration from said remaining spreading factor group matrices;
-34-

(c5) deriving a column placement reference for a first column of said
chosen spreading factor group transmission response matrix;
(c6) deriving a reference location in said base total system transmission
response matrix;
(c7) deriving a column set from said chosen spreading factor group
transmission response matrix;
(c8) inserting said column set after said column placement reference in said
base total system response matrix;
(c9) repeating steps (c5) through (c8) for each successive column of said
spreading factor group transmission response matrix under consideration; and
(c10) repeating steps (c5) through (c8) for remaining spreading factor group
matrices.
10. The method according to claim 9 wherein step (c5) comprises:
(c5a) assigning a column placement reference index m for said spreading
factor group matrix under consideration using,
<IMG>
where Q(g) denotes the spreading factor associated with the spreading factor
group
transmission matrix under consideration, Q(1) denotes the lowest spreading
factor
among all groups and n is the column of the spreading factor group
transmission
response matrix under consideration.
-35-

11. The method according to claim 10 further comprising the step of
rounding said column placement reference index m if not an integer.
12. The method according to claim 11 wherein step (c6) comprises:
(c6a) assigning a reference location in said base total system transmission
response matrix using,
m x L (1)
where L(1) is total number of system transmission response matrices that
constitute
said spreading factor group matrix having the lowest spreading factor and m is
said
column placement reference index for said spreading factor group matrix under
consideration.
13. The method according to claim 12 wherein step (c7) comprises:
(c7a) assigning a column set from said spreading factor group transmission
response matrix under consideration using,
L(g) x (n - 1) + 1 through L(g) x n
where L(g) is said number of system transmission response matrices comprising
said
spreading factor group transmission matrix under consideration.
14. The method according to claim 13 wherein step (e) comprises
forming said objective matrix using a decorrelator.
-36-

15. The method according to claim 13 wherein step (e) comprises
forming said objective matrix using a minimum mean square error detector.
16. The method according to claim 13 wherein step (e) comprises
forming said objective matrix using a zero-forcing block linear equalizer.
17. A method of detecting in a received code division multiple access
(CDMA) communication a plurality of user data communications, each user data
communication comprising symbols and having a spreading factor, the method
comprising:
(a) acquiring impulse estimates corresponding with each symbol in each of
the plurality of user data communications;
(b) constructing a system transmission response matrix for each of the
plurality of user data communications from said respective impulse response
estimates;
(c) assembling a well-banded total system transmission response matrix
from all of said system transmission response matrices;
(d) filtering the received CDMA communication with said total system
transmission response matrix to yield estimated data outputs;
(e) forming an objective matrix from said total system response matrix;
(f) inverting said objective matrix;
-37-

(g) multiplying said estimated outputs with said inverted objective matrix tp
yield user data corresponding to the plurality of user data communications;
and
(h) repeating steps (a)-(g) for a next CDMA communication.
18. The method according to claim 17 wherein step (c) comprises:
(c l) examining each column of said system transmission response matrices
for top and bottom offsets;
(c2) assigning an index value for each of said examined columns based
upon said columns having a small top offset with a large bottom offset to said
columns having a large top offset with a small bottom offset, respectively;
and
(c3) arranging said examined total system transmission response matrix
columns in accordance with said index values according to increasing
magnitude.
19. The method according to claim 18 wherein step (c2) comprises:
(c2a) obtaining a difference between top offsets and a difference between
bottom offsets for two columns if a first column has a larger top offset and a
larger
bottom offset than a second column;
(c2b) comparing said top offset difference and said bottom offset difference
yielding a greater top or bottom offset difference; and
(c2c) if the top offset difference is greater than the bottom offset
difference,
assigning the lower index value for said column with a larger top offset
difference.
-38-

20. The method according to claim 19 wherein step (c2b) further
comprises:
(c2b 1) if the bottom offset difference is greater than the top offset
difference, assigning the lower index value for said column with a larger
bottom
offset difference.
21. The method according to claim 20 wherein forming said objective
matrix is performed by a decorrelator.
22. The method according to claim 20 wherein forming said objective
matrix is performed by a minimum mean square error detector.
23. The method according to claim 20 wherein forming said objective
matrix is performed by a zero-forcing block linear equalizer.
24. The method according to claim 17 wherein step (c) comprises:
(c1) grouping said system transmission response matrices according to like
spreading factors;
(c2) assembling spreading factor group transmission response matrices from
said groups of system transmission response matrices with like spreading
factors;
and
-39-

(c3) forming a base total system response matrix from a common spreading
factor group matrix having the lowest spreading factor.
25. The method according to claim 24 further comprising:
(c4) choosing one spreading factor group transmission response matrix for
consideration from said remaining spreading factor group matrices;
(c5) deriving a column placement reference for a first column of said chosen
spreading factor group transmission response matrix;
(c6) deriving a reference location in said base total system transmission
response matrix;
(c7) deriving a column set from said chosen spreading factor group
transmission response matrix;
(c8) inserting said column set after said column placement reference in said
base total system response matrix;
(c9) repeating steps (c5) through (c8) for each successive column of said
spreading factor group transmission response matrix under consideration; and
(c10) repeating steps (c5) through (c8) for remaining spreading factor group
matrices.
26. The method according to claim 25 wherein step (c5) comprises:
(c5a) assigning a column placement reference index m for said spreading
factor group matrix under consideration using,
-40-

<IMG>
where Q(g) denotes the spreading factor associated with the spreading factor
group
transmission matrix under consideration, Q(1) denotes the lowest spreading
factor
among all groups and n is the column of the spreading factor group
transmission
response matrix under consideration.
27. The method according to claim 26 further comprising the step of
rounding said column placement reference index m if not an integer.
28. The method according to claim 27 wherein step (c6) comprises:
(c6a) assigning a reference location in said base total system transmission
response matrix using,
m x L(1)
where L(1) is total number of system transmission response matrices that
constitute
said spreading factor group matrix having the lowest spreading factor and m is
said
column placement reference index for said spreading factor group matrix under
consideration.
29. The method according to claim 28 wherein step (c7) comprises:
-41-

(c7a) assigning a column set from said spreading factor group transmission
response matrix under consideration using,
L(g) x (n - 1) + 1 through L(g) x n
where L(g) is said number of system transmission response matrices comprising
said
spreading factor group transmission matrix under consideration.
30. The method according to claim 29 wherein forming said objective
matrix is performed by a decorrelator.
31. The method according to claim 29 wherein forming said objective
matrix is performed by a minimum mean square error detector.
32. The method according to claim 29 wherein forming said objective
matrix is performed by a zero-forcing block linear equalizer.
33. A wireless communication apparatus that detects in a received code
division multiple access (CDMA) communication a plurality of user data
communications, comprising:
means for acquiring impulse estimates corresponding with each symbol in
each of the plurality of user data communications;
-42-

means for assembling a system transmission response matrix for each of the
plurality of user data communications from said respective impulse response
estimates;
means for assembling a total system transmission response matrix from all
of said system transmission response matrices yielding a well-banded matrix;
means for filtering the received CDMA communication with said total
system transmission response matrix yielding estimated data outputs;
means for forming an objective matrix from said arranged total system
response matrix;
means for inverting said objective matrix; and
means for multiplying said estimated outputs with said inverted objective
matrix yielding user data corresponding to the plurality of user data
communications.
34. The wireless communication apparatus according to claim 33 wherein
said means for assembling an arranged total system transmission response
matrix
comprises:
means for examining each of said total system transmission response matrix
columns for top and bottom offsets;
means for assigning an index value for each of said examined columns based
upon said columns having a small top offset with a large bottom offset to said
columns having a large top offset with a small bottom offset respectively; and
-43-

means for re-arranging said examined total system transmission response
matrix columns in accordance with said index values according to increasing
magnitude.
35. The wireless communication apparatus according to claim 34 wherein
said means for assigning comprises:
means for obtaining a difference between top offsets and a difference
between bottom offsets for two columns if a first column has a larger top
offset and
a larger bottom offset than a second column;
means for comparing said top offset difference and said bottom offset
difference yielding a greater top or bottom offset difference; and
means for assigning a lower index value for said column with a larger top
offset difference if the top offset difference is greater than the bottom
offset
difference.
36. The wireless communication apparatus according to claim 35 wherein
said means for comparing further comprises by means for assigning a lower
index
value for said column with a larger bottom offset difference if the bottom
offset
difference is greater than the top offset difference.
37. The wireless communication apparatus according to claim 36 wherein
said means for forming an objective matrix is a decorrelator.
-44-

38. The wireless communication apparatus according to claim 36 wherein
said means for forming an objective matrix is a minimum mean square error
detector.
39. The wireless communication apparatus according to claim 36 wherein
said means for forming an objective matrix is a zero-forcing block linear
equalizer.
40. The wireless communication apparatus according to claim 33 wherein
said means for assembling an arranged total system transmission response
matrix
comprises:
means for grouping said system transmission response matrices according to
like spreading factors;
means for assembling spreading factor group transmission response matrices
from said groups of system transmission response matrices with like spreading
factors; and
means for forming a base total system response matrix from a common
spreading factor group matrix having the lowest spreading factor.
41. The wireless communication apparatus according to claim 40 further
comprising:
means for choosing one spreading factor group transmission response matrix
for consideration from said remaining spreading factor group matrices;
-45-

means for deriving a column placement reference for a first column of said
chosen spreading factor matrix;
means for deriving a reference location in said base total system
transmission response matrix;
means for deriving a column set from said chosen spreading factor group
transmission response matrix; and
means for inserting said column set after said column placement reference in
said base total system response matrix.
42. The wireless communication apparatus according to claim 41 wherein
said means for deriving a column placement reference comprises:
means for assigning a column placement reference index m for said
spreading factor group matrix under consideration using,
<IMG>
where Q(g) denotes the spreading factor associated with the spreading factor
group
transmission matrix under consideration, Q(1) denotes the lowest spreading
factor
among all groups and n is the column of the spreading factor group
transmission
response matrix under consideration.
-46-

43. The wireless communication apparatus according to claim 42
including means for rounding said column placement reference index m if not an
integer.
44. The wireless communication apparatus according to claim 43 wherein
said means for deriving a reference location comprises:
means for assigning a reference location in said base total system
transmission response matrix using,
m x L (1)
where L(1) is total number of system transmission response matrices that
constitute
said spreading factor group matrix having the lowest spreading factor and m is
said
column placement reference index for said spreading factor group matrix under
consideration.
45. The wireless communication apparatus according to claim 44 wherein
said means for deriving a column set comprises:
means for assigning a column set from said spreading factor group
transmission response matrix under consideration using,
L (g) x (n - 1) + 1 through L (g) x n
where L (g) is said number of system transmission response matrices comprising
said
spreading factor group transmission matrix under consideration.
-47-

46. The wireless communication apparatus according to claim 45 wherein
said means for forming an objective matrix is a decorrelator.
47. The wireless communication apparatus according to claim 45 wherein
said means for forming an objective matrix is a minimum mean square error
detector.
48. The wireless communication apparatus according to claim 45 wherein
said means for forming an objective matrix is a zero-forcing block linear
equalizer.
-48-

Description

CA 02617242 2008-01-21
TITLE OF THE INVENTION
MULTIUSER DETECTOR FOR VARIABLE SPREADING FACTORS
This application is a divisional of Canadian patent application Serial No.
2,385,082 filed internationally on February 2, 2000 and entered nationally on
March 15, 2002.
BACKGROUND OF THE INVENTION
Field of the Invention
The present invention relates generally to multiple access digital
communication systems. More specifically, the invention relates to a multiuser
detector system and method for the simultaneous reception of data from
multiple
users having different spreading factors.
Description of the Related Art
A multiple-access communication system allows a plurality of users to
access the same communication medium to transmit or receive information. The
media may comprise, for example, a network cable in a local area network or
lan, a
copper wire in the classic telephone system, or an air interface for wireless
communication.
A prior art multiple access communication system is shown in FIG. 1. The
communication media is referred to as a communication channel. Communication
techniques such as frequency division multiple access or FDMA, time division
-1-

CA 02617242 2008-01-21
multiple access or TDMA, carrier sense multiple access or CSMA, code division
multiple access or CDMA and others allow access to the same communication
medium for more than one user. These techniques can be mixed together creating
hybrid varieties of multiple access schemes. For example, time division duplex
or
TDD mode of the proposed third generation W-CDMA standard is a combination
of TDMA and CDMA.
An example CDMA prior art communication system is shown in FIG. 2.
CDMA is a communication technique in which data is transmitted with a
broadened band (spread spectrum) by modulating the data to be transmitted with
a
pseudo-noise signal. The data signal to be transmitted may have a bandwidth of
only a few thousand Hertz distributed over a frequency band that may be
several
million Hertz. The communication channel is being used simultaneously by K
independent subchannels. For each subchannel, all other subchannels appear as
interference.
As shown, a single subchannel of a given bandwidth is mixed with a unique
spreading code which repeats a predetermined pattern generated by a wide
bandwidth, pseudo-noise (pn) sequence generator. These unique user spreading
codes are typically pseudo-orthogonal to one another such that the cross-
correlation
between the spreading codes is close to zero. A data signal is modulated with
the
pn sequence producing a digital spread spectrum signal. A carrier signal is
then
modulated with the digital spread spectrum signal and transmitted in
dependence
upon the transmission medium. A receiver demodulates the transmission
extracting
-2-

CA 02617242 2008-01-21
the digital spread spectrum signal. The transmitted data is reproduced after
correlation with the matching pn sequence. When the spreading codes are
orthogonal to one another, the received signal can be correlated with a
particular
user signal related to the particular spreading code such that only the
desired user
signal related to the particular spreading code is enhanced while the other
signals
for all other users are not enhanced.
Each value of the spreading code is known as a chip and has a chip rate that
is the same or faster than the data rate. The ratio between the chip rate and
the
subchannel data rate is the spreading factor.
To extend the possible range of values of the data signal, a symbol is used to
represent more than two binary values. Ternary and quaternary symbols take on
three and four values respectively. The concept of a symbol allows for a
greater
degree of information since the bit content of each symbol dictates a unique
pulse
shape. Depending upon the number of symbols used, an equal number of unique
pulse or wave shapes exist. The information at the source is converted into
symbols which are modulated and transmitted through the subchannel for
demodulation at the destination.
The spreading codes in a CDMA system are chosen to minimize interference
between a desired subchannel and all other subchannels. Therefore, the
standard
approach to demodulating the desired subchannel has been to treat all other
subchannels as interference, similar to interference that manifests itself in
the
-3-

CA 02617242 2008-01-21
communication medium. Receivers designed for this process are single-user,
matched filter and RAKE receivers.
Since different subchannels do interfere with each other somewhat, another
approach is to demodulate all subchannels at a receiver. The receiver can
listen to
all of the users transmitting at once by running a decoding algorithm for each
of
them in parallel. This ideology is known as multiuser detection. Multiuser
detection can provide a significant performance improvement over single-user
receivers.
Referring to FIG. 3, a system block diagram of a prior art CDMA receiver
using a multiuser detector is shown. As one skilled in this art realizes, the
receiver
may include such functions as radio frequency or rf down conversion and
associated filtering for radio frequency channels, analog-to-digital
conversion or
optical signal demodulation for a specific communication media. The output of
the
receiver is a processed signal, either analog or digital, containing the
combined
spread signals of all active subchannels. The multiuser detector performs
multiuser
detection and outputs a plurality of signals corresponding to each active
subchannel. All or a smaller number of the total number of subchannels may be
processed.
Optimal multiuser detectors are computationally intensive devices
performing numerous complex mathematic operations and are therefore difficult
to
implement economically. To minimize expense, suboptimal multiuser detectors
such as linear detectors have been developed requiring less computational
-4-

CA 02617242 2008-01-21
complexity as a compromise approximating the performance of optimal detectors.
Linear detectors include decorrelators, minimum mean square error or MMSE
detectors, and zero-forcing block linear equalizers or ZF-BLEs.
A system block diagram of a prior art linear multiuser detector for
synchronous or asynchronous CDMA communication is shown in FIG. 4. Data
output from the communication media specific receiver (as in FIG. 3) is
coupled to
a subchannel estimator which estimates the impulse response of each symbol
transmitted in a respective subchannel. The linear detector uses the impulse
response estimates along with a subchannel's spreading code to demodulate each
subchannel's data. The data is output to subchannel data processing blocks for
respective users.
To effect parallel detection of K subchannel users in a physical system,
linear multiuser detector methods are executed as fixed gate arrays,
microprocessors, digital signal processors or DSPs and the like. Fixed logic
systems allow for greater system speed while microprocessor driven systems
offer
programming flexibility. Either implementation that is responsible for the
multiuser detection performs a sequence of mathematic operations. To describe
the
functions, the following variables typically define the structure and
operation of a
linear multiuser detector:
K = the total number of users/transmitters that are active in the
system.
-5-

CA 02617242 2008-01-21
N= the number of chips in a data block. The number of chips is
required since with varying spreading factors this number is a
measure common to all users. The number of chips is divisible by the
largest spreading factor allowed. For the case of synchronous
CDMA, a symbol from the user with the largest spreading factor may
constitute a block of data. Therefore, N, can be reduced to be equal
to the largest spreading factor.
W = the communication channel impulse response length in chips.
This is generally a predefined parameter of the system.
Q(k) = the spreading factor of user k. The spreading factor is equal to
the number of chips that are used to spread a symbol of user's data.
A system knows the spreading factors in advance and does not need
to estimate them from the received data.
Ns(k) = the number of symbols sent by user k. Ns(k) = Nc / Q(k).
K
NS'= J:Nsk' = the total number of symbols sent.
k=1
d~k~ = the data (information) sent by user k. The data is presented in
the form of a vector, where a vector is an array of data indexed by a
-6-

CA 02617242 2008-01-21
single index variable. For the purposes of vector and matrix
operations which follow, all vectors are defined as colunm vectors.
The n'h element of d(k) is the n" symbol transmitted by the k'h user.
h(k) = the impulse response of the subchannel experienced by user k
presented as a vector. This quantity needs to be estimated at the
receiver. The receiver's estimates of the subchannel impulse
responses are referred to as h(k). The elements of the vector h(k) are
typically complex numbers, which model both amplitude and phase
variations that can be introduced by the subchannel.
v(k) = the spreading code of user k, presented as a vector. For the
purposes of linear multiuser detection, it is useful to think of vectors
containing the section of the spreading code which spreads a
particular symbol. Therefore, the vector v(k'n) is defined as the
spreading code which is used to spread the n'h symbol sent by the k'h
user. Mathematically, it is defined as: vi (k n) = v,(k) for (n-1)Q(k)+1 # i #
nQ(k) and 0 for all other i, where i is the index of vector elements.
r(k) = a vector which represents user k's data, spread by the spreading
sequence v(k) and transmitted through that user's subchannel h(k) . The
vector r(k) represents channel observations performed during the
-7-

CA 02617242 2008-01-21
period of time when a block of data arrives. The i'h element of the
vector r(k) can be defined as:
jVk'
s w
r(k) _ Idnk) ~h(k)V(k,n)
j i-j+l
n=1 j=1 Equation 1
The signal received at the receiver includes all user signals r(k) plus noise.
Therefore, we can define the received data vector r as follows:
K
r I r (k) + n. Equation 2
k=1
The vector n in Equation 2 represents noise introduced by the communication
channel.
FIG. 5 shows a system and method of a prior art linear multiuser detector.
The estimated subchannel impulse response vectors h(k) and the spreading codes
v(k)
are used to create a system transmission response matrix for each user k. A
matrix
is a block of numbers indexed by two indexing variables and is arranged as a
rectangular grid, with the first indexing variable being a row index and the
second
indexing variable being a column index.
A system transmission response matrix for user k is typically denoted as A.
The i'h-row, n'h-column element is denoted as A, n(k) and is defined as:
-8-

CA 02617242 2008-01-21
w
A ',n h ~k)V~k' n~
j i- j+ t Equation 3
j =I
Each column of the matrix A(k) corresponds to a matched filter response for a
particular symbol sent by user k during the period of interest. Referring back
to
FIG. 5, the received data r is matched to a combination of all user's
spreading
codes and subchannel impulse responses. Therefore, A(k) contains N'k, matched
filter responses.
The columns of A(k) are of the form
0
0
A( k~ = b(k)
n 0 n Equation 4
0
where each vector bõ(k) has a dimension of
Q(k) + W- 1, Equation 5
and is offset from the top of the matrix A(k) by
Qk)(n-1). Equation 6
-9-

CA 02617242 2008-01-21
Since the spreading codes are not periodic over symbol times; b<(k) ... bj(k)
for i... j.
The elements of a vector which may be non-zero values are referred to as the
support of the vector. Therefore, b,(k) is the support of An(k).
Once a system transmission matrix for each user is created, a total system
transmission response matrix, denoted as A is created by concatenating the
system
transmission matrices for all the users as shown below:
A = [41) 9. = ~ ~k~, = = =, 4K)]. Equation 7
In accordance with prior art modulation techniques, the elements of h(k) can
be complex numbers. It then follows that the non-zero elements of A can be
complex numbers.
An example total system transmission response matrix A for a hypothetical
prior art multiuser detector assembled in accordance with Equations 4, 5, 6
and 7 is
-10-

CA 02617242 2008-01-21
b(l) 0 0 0 0 0 0 0;b(,) 0 0 0
b;,2 0 0 0 0 0 0 0;b; z~ 0 0 0
) 0 0 0
b; 3 bz'; 0 0 0 0 0 0b1,3
b;'4 b~'~ 0 0 0 0 0 0;b(2 ) 0 0 0
b~ s) bz'3 b3'~ 0 0 0 0 0;b~ s b~ ~, 0 0
0 b2('4 b3'z 0 0 0 0 0b, 6 b~2z 0 0
0 b(l) b3'3 b4', 0 0 0 0;b, ~ bz~3 0 0
0 0 b3'4 b4'~ 0 0 0 0 0 b~~4 0 0
0 0 b3'5 ) b4'3 bs', 0 0 0 0 b(2 ) b3 ;) 0
A 0 0 0 b4'4 bs'z 0 0 0 0 b2 6 b3 z) 0
0 0 0 b4'5 b5'3 b6'l 0 0 0 b2 ,) b3 3) 0
0 0 0 0 bs'4 bb'z 0 0 0 0 b3 4 0
0 0 0 0 bs's bb'3 b~'i 0 0 0 b(2 ) b(2 )
0 0 0 0 0 b6('4 b~'2 0 0 0 b(2 ) ba z
0 0 0 0 0 bb's b~'3 bg'1) 0 0 b(2 ) b(2 )
0 0 0 0 0 0 b(') bg'z 0 0 0 ba~a
0 0 0 0 0 0 b;'s bg'3 0 0 0 b(2 )
0 0 0 0 0 0 0 b8'4 0 0 0 (2 6
0 0 0 0 0 0 0 bg'S 0 0 0 b4~;
A (l) A (Z) Equation 8
for two (k = 2) users, A(l) and A(2) , having sixteen chips in a data block
(N, = 16), a
channel impulse response length of four ( W= 4) and a spreading factor for the
first
user of two (Q(1) = 2) and a spreading factor for the second user of four
(Q(2) = 4).
In the resultant total system transmission response matrix A, b,,;(k) denotes
the i'"
elenient of the combined system and channel response for the n'h symbol of the
k'"
user.
The received data r is processed using the total system transmission
response matrix A which represents a bank of matched filter responses to
create a
-11-

CA 02617242 2008-01-21
vector of matched-filter outputs which is denoted as y. The matched filtering
operation is defined as
H
y= A r= Equation 9
The matrix AH represents the Hermitian (or complex) transpose of the matrix
4 H
j = AJi
A. The Hermitian transpose is defined as where the over-bar denotes the
operation of taking a conjugate of a complex number. The matched filter
outputs
are then multiplied by the inverse of an objective matrix O. The objective
matrix 0
represents the processing which differentiates each type of linear receiver
model. It
is derived from the system transmission matrix A.
The zero-forcing block linear equalizer (ZF-BLE) receiver is a linear
receiver with an objective matrix specified as O= AHA. The minimum mean
square error block linear equalizer (MMSE-BLE) receiver is a linear receiver
with
an objective matrix specified as O= AHA + F2I where F2 is the variance of the
noise
present on each of the symbols of the received data vector r and the matrix I
is
known as an identity matrix. An identity matrix is square and symmetric with 1
s
on its main diagonal and zeros everywhere else. The size of the identity
matrix is
chosen so as to make the addition operation valid according to the rules of
linear
algebra.
For a decorrelator (decorrelating receiver), matrix A is simplified by
ignoring the channel responses h(~'), considering only the spreading codes and
their
-12-

CA 02617242 2008-01-21
cross-correlation (interference) properties. A cross-correlation matrix,
commonly
referred to as R, is generally constructed for decorrelator type receivers.
This
matrix can be constructed by assuming that W=1 and hl (k)=1 in the definition
of A
above (i.e. the channel response of every subchannel is an impulse). Then the
cross
correlation matrix R is the objective matrix 0 as defined for the ZF-BLE
receiver.
A decorrelator often serves as a sub-process of a more complex multiuser
detection
receiver. Once the objective matrix is created, the multiuser detector will
invert the
matrix, denoted as O-' .
The inverse of the objective matrix is then multiplied by the matched filter
output vector y to produce estimates of the data vector d where d(estimate) =
O-'y.
The inversion of the objective matrix 0 is a complex, computationally
intensive
process. The number of operations required to perform this process increase as
the
cube of the size of the matrix O. For most asynchronous CDMA receivers, the
size
of 0 is very large which makes the process of inversion impracticable.
To overcome this limitation, and to make the system physically realizable, a
numerical method due to Cholesky is used. Cholesky decomposition can
significantly reduce the computational complexity of inverting the matrix 0 if
the
matrix is banded.
A banded matrix is a square matrix that contains non-zero values only on
several diagonals away from the main diagonal. The number of non-zero
diagonals
adjacent to the main diagonal that have at least one non-zero element is
referred to
-13-

CA 02617242 2008-01-21
as bandwidth. Thus, a symmetric matrix M is said to be banded with bandwidth p
if
mr~=0forallj>i+p, Equation 10
where m~~ is an element of M, with i being the row index and j the column
index.
For a banded matrix with size denoted as n and bandwidth denoted as p,
Cholesky
decomposition can reduce the required numeric operations of inverting the
objective matrix 0 from varying as the cube of the size of the matrix, n3, to
varying
as the size of the matrix times the square of the bandwidth, npl.
As discussed above, the objective matrix for a ZF-BLE receiver is O= AHA.
To illustrate the numeric complexity, the objective matrix 0 for the total
system
response matrix A shown in Equation 6 is
x x x 0 0 0 0 0 x x 0 0
x x x x 0 0 0 0 x x 0 0
x x x x x 0 0 0 x x x 0
0 x x x x x 0 0 x x x 0
0 0 x x x x x 0 0 x x x
0 0 0 x x x x x 0 x x x
0 =
0 0 0 0 x x x x 0 0 x x Equation 1 1
0 0 0 0 0 x x x 0 0 x x
x x x x 0 0 0 0 x x 0 0
x x x x x x 0 x x x x 0
0 0 x x x x x x 0 x x x
0 0 0 0 x x x x 0 0 x x
where zeros denote all elements that by mathematical operation yield zero and
with
x's representing non-zero values. If the non-zero elements of the i'" row and
j h
column of the total system response matrix A do not have the same vector
index,
-14-

CA 02617242 2008-01-21
then the corresponding element of objective matrix 0 with row index i and
column
index j will be 0. The bandwidth of O(Equation 11) is equal to 9 since there
are
non-zero elements as far as nine columns away from the main diagonal.
The objective matrix 0 as it is constructed in the prior art receiver shown in
FIG. 5 is not well banded. Therefore, Cholesky decomposition cannot be used
effectively to reduce the operational complexity when inverting matrix O.
However, the prior art discloses that when all users transmit with equal
spreading
factors, a re-arrangement of the total system transmission response matrix A
can be
performed prior to calculating an objective matrix 0, turning matrix 0 into a
banded matrix. A system block diagram for this process is shown in FIG. 6.
The process which computes the column re-arrangement of matrix A
performs the re-arrangement without any additional information. The re-
arrangement reduces the operational complexity when inverting the matrix. Once
the detection procedure is complete, a user data vector d is computed, a
reversed re-
arrangement process is performed descrambling vector d back to its original
form
for further processing.
In a typical asynchronous CDMA system, the bandwidth of a re-arranged
objective matrix is at least ten times less than its original size. Therefore,
a savings
of at least a factor of 100 in processing time is achieved when Cholesky
decomposition is performed on an objective matrix based upon a re-arranged
total
system response matrix. However, the prior art has not addressed a re-
arrangement
method for when different spreading factors are in use between active users.
-15-

CA 02617242 2008-01-21
Klein et al., "Zero Forcing and Minimum Mean-Square-Error Equalization
for Multiuser Detection in Code-Division Multiple-Access Channels," IEEE
Transactions on Vehicular Technology, Vol. 45, No. 2, May 1996, pp. 276-287,
discloses multiuser detection approaches. These approaches use a system
response
matrix in a zero forcing equalizer and a minimum mean square error
equalization to
recover data.
Karimi et al., "A Novel and Efficient Solution to Block-Based Joint-
Detection Using Approximate Cholesky Factorization," IEEE International
Symposium in Personal, Indoor and Mobile Radio Communications, XX, XX, Vol.
3, 1998, pp. 1340-1345, discloses a zero forcing-block linear equalizer using
an
approximate Cholesky factor. The Cholesky factor is derived using a system
response matrix.
Accordingly, there exists a need to determine a method to reduce the number
of inversion steps when different spreading factors are in use.
SUMMARY OF THE INVENTION
The present invention relates to a multiuser detector that detects and decodes
synchronous or asynchronous CDMA subchannels having different spreading
factors with reduced computational complexity. The multiuser detector of the
present invention is compatible with ZF-BLE, MMSE, decorrelating detectors and
the like using Cholesky decomposition to minimize numeric operations. The
system and method arranges the columns of system transmission response
matrices
-16-

CA 02617242 2008-01-21
representing the response characteristics of individual users into a well-
banded total
system transmission response matrix which represents a plurality of matched-
filter
responses for a given block of received data. The invention in conjunction
with
Cholesky decomposition reduces the number of required mathematic operations
prior to parallel matched filtering.
Accordingly, it is an object of the invention to detect a plurality of users
transmitting over a CDMA interface with reduced computational complexity where
each user may employ a different spreading factor.
It is another object of the invention to use existing linear detectors in a
multiuser detector without requiring a uniform spreading factor among all CDMA
subchannels.
It is a further object of the invention to efficiently limit the bandwidth of
a
matrix that represents a plurality of matched filters prior to inversion.
Other objects and advantages of the system and the method will become
apparent to those skilled in the art after reading the detailed description of
the
preferred embodiment.
According to an aspect, the invention relates to a method of detecting in a
received code division multiple access (CDMA) communication a plurality of
data
communications each corresponding with a specific user, comprising: (a)
acquiring
impulse response estimates for symbols within each data communication; (b)
constructing a system transmission response matrix for each of the user data
communications from the impulse response estimates; (c) assembling a well-
-17-

CA 02617242 2008-01-21
banded total system transmission response matrix from all of the user system
transmission response matrices; (d) filtering the received CDMA communication
with the total system transmission response matrix yielding a matched filter
output;
(e) forming an objective matrix based upon the total system transmission
response
matrix; (f) inverting the objective matrix; (g) multiplying the matched filter
output
with the inverted objective matrix yielding estimated user data; (h)
descrambling
the estimated user data yielding user data corresponding to the plurality of
data
communications; and (i) repeating steps (a)-(h) for a next CDMA communication.
According to another aspect, the invention relates to a method of detecting
in a received code division multiple access (CDMA) communication a plurality
of
user data communications, each user data communication comprising symbols and
having a spreading factor, the method comprising: (a) acquiring impulse
estimates
corresponding with each symbol in each of the plurality of user data
communications; (b) constructing a system transmission response matrix for
each
of the plurality of user data communications from the respective impulse
response
estimates; (c) assembling a well-banded total system transmission response
matrix
from all of the system transmission response matrices; (d) filtering the
received
CDMA communication with the total system transmission response matrix to yield
estimated data outputs; (e) forming an objective matrix from the total system
response matrix; (f) inverting the objective matrix; (g) multiplying the
estimated
outputs with the inverted objective matrix tp yield user data corresponding to
the
-18-

CA 02617242 2008-01-21
. .=
plurality of user data communications; and (h) repeating steps (a)-(g) for a
next
CDMA communication.
According to yet another aspect, the invention relates to a wireless
communication apparatus that detects in a received code division multiple
access
(CDMA) communication a plurality of user data communications, comprising:
means for acquiring impulse estimates corresponding with each symbol in each
of
the plurality of user data communications; means for assembling a system
transmission response matrix for each of the plurality of user data
communications
from the respective impulse response estimates; means for assembling a total
system transmission response matrix from all of the system transmission
response
matrices yielding a well-banded matrix; means for filtering the received CDMA
communication with the total system transmission response matrix yielding
estimated data outputs; means for forming an objective matrix from the
arranged
total system response matrix; means for inverting the objective matrix; and
means
for multiplying the estimated outputs with the inverted objective matrix
yielding
user data corresponding to the plurality of user data communications.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a simplified block diagram of a prior art multiple access
communication system.
FIG. 2 is a simplified block diagram of a prior art CDMA communication
system.
-19-

CA 02617242 2008-01-21
FIG. 3 is a simplified block diagram of a prior art CDMA receiver with
multiuser detection.
FIG. 4 is a simplified block diagram of a prior art multiuser detector.
FIG. 5 is a block diagram of a prior art linear multiuser detector.
FIG. 6 is a block diagram of a prior art linear multiuser detector using
Cholesky decomposition.
FIG. 7 is block diagram of a linear multiuser detector of the present
invention.
FIG. 8 depicts system transmission response matrix A(k) top and bottom
column offsets.
FIG. 9 depicts matrix column index value assignment.
FIGs. 10A and lOB are flow diagrams of an alternative method
implementing the present invention.
FIG. 11 depicts the steps for assembling a spreading factor group matrix
AG~~.
FIG. 12 depicts the steps for assembling an AN matrix in accordance with
the present invention.
DETAILED DESCRIPTION OF THE INVENTION
The embodiments will be described with reference to the drawing figures
where like numerals represent like elements throughout.
-20-

CA 02617242 2008-01-21
Shown in FIG. 7 is a multiuser detector 17 of the present invention for
detecting, after reception, a plurality of users transmitting over a common
CDMA
channel. The multiuser detector 17 comprises a plurality of processors having
collateral memory which perform various vector and matrix operations.
Alternate
embodiments of the invention include fixed gate arrays and DSPs performing the
functions of the various processors. The detector 17 also comprises a first
input 19
for inputting individual k subchannel impulse response estimates modeled as
vectors h(k) to correct intersymbol interference or ISI caused by a
subchannel's own
symbols and multiple access interference or MAI caused by symbols from other
user's subchannels for all received data signals, a second input 21 for
inputting data
from all users k transmitted in a discreet block of time in the form of an
input
vector r containing the combined data from each user's subchannel and an
output
23 for outputting user data d(k) for each user k from the received channel
data r in
the form of an output vector. The total number of users K and the spreading
factor
Q(k) for each user (k = 1, 2, 3... K) are known a priori.
To obtain user data d(k) for a specific user from the combined user data r,
the
user data must be filtered using a matched filter 25 or the like. One
knowledgeable
in this art recognizes that a matched filter 25 requires a response
characteristic
which is the complex conjugate of the combination of the spread pulse shape
and
the user's subchannel impulse response to produce an output with a level
representative of the signal prior to transmission. Signals input to the
filter 25
which do not match with a given response characteristic produce a lower
output.
-21 -

CA 02617242 2008-01-21
Each individual k subchannel impulse response estimate h(k) is input to a
first memory 27 where it is combined with the same user's spreading code 29
(Equation 3) creating a system transmission response estimate matrix A(k) for
that
user. An arrangement processor 33 of the present invention 17 performs a re-
ordering of all matrix Aõ(k) columns. The arrangement method 99 requires that
each subchannel system transmission response matrix A(k) have the column
structure defined by Equation 4 which is typical of linear receivers. If the
system
transmission response matrices A(k) are not of the form defined by Equation 4,
the
arrangement processor 33 first re-arranges the columns to the structure
defined by
Equation 4. The present invention 17 does not require that all system
transmission
response matrices A(k) be concatenated into a total system transmission
response
matrix A as defined by Equation 7.
The arrangement processor 33 examines each system transmission response
matrix A(1), A(Z) , A(3), ... A(k) column for the number of zero-value
elements from the
support of each vector b,, (k) (Equation 4) defining top o(k)T,, and bottom
offsets o(k)Bõ
as shown in FIG. 8 (for one matrix). As previously described, each system
transmission response matrix A(k) has the same number of rows; only the number
of
colunms vary. As shown in FIG. 9, the arrangement processor 33 assigns an
index
value n; for each column of each system transmission response matrices A(k)
based
upon their respective top o(k) Tõ and bottom o(k) Bõ offsets. The column
values are
assigned in the order of increasing magnitude from columns having minimal top
-22-

CA 02617242 2008-01-21
offset with maximum bottom offset to columns having maximum top offset with
minimal bottom offset.
If two columns are encountered where one has a greater top offset and a
greater bottom offset than another, if the difference between top offsets is
greater
than the difference between bottom offsets, the column with the lower top
offset is
assigned the lower index ni. If the difference between bottom offsets is
greater than
the difference between top offsets, the column with the greater bottom offset
is
assigned the lower index ni. If the differences between top and bottom offsets
are
equal, either of the two columns can be assigned the lower index n;.
The arrangement processor 33 assembles a total system transmission response
matrix AN in the order of the assigned column indices n,. The column indices
n;
are retained in memory 33 for use during the descrambling process 45. As an
example, using the total system response matrices A(') and A(2) described and
shown in Equation 8, the arrangement method 99 of the present invention 17
produces the total system transmission response matrix A shown below
-23-

CA 02617242 2008-01-21
b; ;) b; ;) 0 0 0 0 0 0 0 0 0 0
b,( z) b; z) 0 0 0 0 0 0 0 0 0 0
b; 3) b; 3 bz'; 0 0 0 0 0 0 0 0 0
b1,4 b14 bz'z 0 0 0 0 0 0 0 0 0
bi s) bi,2 bz'3 b3'1) bi i) 0 0 0 0 0 0 0
0 b; 6 bz'4 b3'z bz ~) 0 0 0 0 0 0 0
0 b; , bz's b3'3 b(2 ) b4'; 0 0 0 0 0 0
0 0 0 b3'4 bz24 b412 ) 0 0 0 0 0 0
0 0 0 b3'5 ) bi2s bal3 b5('1) b3 ~) 0 0 0 0
A' = 0 0 0 0 b~ 26 b4'4 bs'z b3 z) 0 0 0 0
0 0 0 0 bz2, b4'5 ) b5('3 b3 3) b6'1) 0 0 0
0 0 0 0 0 0 b5('4 (2 4) bb'z 0 0 0
0 0 0 0 0 0 b5'5 b3 5) b6'3 b;'~ b(2 ) 0
0 0 0 0 0 0 0 (2 6) b(l) b,'z b(2 ) 0
0 0 0 0 0 0 0 b(2 ) bb~s b~~3 ba 3 bg~1)
0 0 0 0 0 0 0 0 0 b7l4 b4 4 b8l2
0 0 0 0 0 0 0 0 0 b(l) b4,5 ) b8 l3
0 0 0 0 0 0 0 0 0 0 bq2b b8'4
0 0 0 0 0 0 0 0 0 0 b4,7 ) b8's
Equation 12
The arrangement method 99 indexed the eight columns (1-8) of system
transmission response matrix A(') and the four columns (9-12) of system
transmission response matrix A(2) in an order of 1, 9, 2, 3, 10, 4, 5, 11, 6,
7, 12, 8 to
create a well-banded total system transmission response matrix A (Equation
12).
The arrangement method 99 embodiment described above involves an
examination of each system transmission response matrix A(l), A(Z), A(3), ...
A(k)
comparing each column with every other column for top o(k) Tõ and bottom o(k)
Bõ
offsets. Given the special structure of each system transmission response
matrix
A(k) , namely, that the columns of each matrix are arranged in order of
increasing top
-24-

CA 02617242 2008-01-21
offsets and decreasing bottom offsets as you progress from left to right
(reference
Equation 8, matrices A"' and A"'), an alternative method 199 can be performed
without having to examine each system transmission response matrix A(k)
directly.
The alternative method 199 is shown in FIGs. 10A and lOB. All system
transmission response matrices A(k) corresponding (step 201) to users having
equal
spreading factors are grouped together (step 203). For each spreading factor
group
g, memories are allocated within the processor 33 capable of storing all of
the
columns from all system transmission matrices A('), A(2), A(3), ... A(k). The
spreading factor groups g are arranged in order of increasing spreading
factor.
An exemplary system illustrating the performance of the present invention
199 contains seven users having four different spreading factors Q(k) assigned
as
follows:
User 1(Q')) = 8 User 2(Q(2)) = 8 User 3 (Q(3)) = 8 User 4 (Q(4)) = 32
User 5 (Q(5)) = 16 User 6 (Q(6)) = 16 User 7 (Q(7)) = 4.
Using the system and method 199 of the present invention 17, the system
transmission response matrices A(k) are separated into spreading factor
groups:
group 1(spreading factor 4) A(7)
group 2 (spreading factor 8) A(), A(2) A(3)
group 3 (spreading factor 16) A(5) A(6)
group 4 (spreading factor 32) A(4)
-25-

CA 02617242 2008-01-21
A respective spreading factor group g comprises at least one system
transmission
response matrix A(k), where each matrix A(k) is arbitrarily indexed from 1 to
L(,).
Each spreading factor group g is indexed according to increasing spreading
factor
magnitude.
Within each spreading factor group, the columns of the associated system
transmission response matrices A(k) are assembled into common spreading factor
group transmission response matrices AG(9), where g = 1, 2, 3, ... G (step
205). As
shown in FIG. 11, the method 199 copies the first column of the system
transmission response matrix having index one to the first blank column of
Ac(9);
the first column of the system transmission response matrix having index two
to the
second blank column of Ac(9); continuing throughout the remaining system
transmission response matrices in a respective spreading factor group g until
all
first columns are copied. The method 199 proceeds with copying the second
columns, the third columns, etc., for each matrix A(k) in the respective
spreading
factor group AG(9)
All matrices in a spreading factor group g have the same number of columns
due to the same spreading factor. Therefore, the assembled spreading factor
group
transmission response matrices AG(9) will have L("') times the number of
columns in
one associated system transmission response matrices A(k) . For equal
spreading
factors, the arrangement method as-applied to each individual system
transmission
response matrix per group is similar to prior art techniques for assembling a
total
system transmission response matrix A.
-26-

CA 02617242 2008-01-21
To assemble a total system transmission response matrix AN
accommodating variable spreading factors, the spreading factor group
transmission
response matrix AG(-) having the lowest spreading factor is copied
sequentially
(step 207) into memory 33a, beginning with the first column, i.e., column one
of
ACto the first allocated colunm of AN. The spreading factor group transmission
response matrix AG(",) having the lowest spreading factor has the maximum
number
of columns. All other spreading factor group transmission response matrix
columns will be inserted into this base matrix AN.
If the system spreading factors are even integer multiples of each other (step
209), the processor 33 assembles the total system transmission matrix AN (step
211) by considering the remaining spreading factor group transmission matrices
AC(-') in any order (step 209). For each spreading factor group transmission
matrix
A (9~~, the processor 33 derives a column placement reference index m,
Q(g) Q (g)
m- n~~(1) 2 ~(1) Equation 13
where Q(9) denotes the spreading factor associated with the spreading factor
group
transmission matrix AG Q-) under consideration, Qlt denotes the lowest
spreading
factor among all groups and n is the colulnn of the spreading factor group
transmission response matrix AG(1) under consideration where n= 1, 2, 3, ...
N(step
211).
-27-

CA 02617242 2008-01-21
To use the colunm placement index m, a reference location in AN is derived
(step 215) using the total number of system transmission response matrices
L(l) that
constitute the spreading factor group matrix having the lowest spreading
factor,
m H L('). Equation 14
The processor 33 derives a column set from the spreading factor group
transmission response matrix AG'~' '3 under consideration (step 217) using the
number
of system transmission response matrices that belong to the spreading factor
group
currently under consideration,
L(9) H (n - 1) + 1 through L(9) H n. Equation 15
The processor 33 copies the column set defined by Equation 15 from AG(93 and
inserts it (step 219) into the base matrix AN after the column of AG (1) which
has the
reference location defined by Equation 14 as shown in FIG. 12. The remaining
columns of the spreading factor group matrix under consideration are copied
and
inserted into the base matrix AN similarly (step 221). After all columns from
one
spreading factor group matrix are placed, the processor 33 chooses the next
spreading factor group matrix AG(-) (step 223) and executes the above method.
Equations 13, 14 and 15 allow the a''" columns from the remaining spreading
factor
-28-

CA 02617242 2008-01-21
group transmission matrices Ao~9l to be placed in AN after an m'h column that
has
similar support (step 225).
When the system spreading factors are not even integer multiples of each
other, the right side expression of Equation 13 does not yield an integer. In
this
case, the processor 33 will round the result of Equation 13 to the nearest
integer
above or the nearest integer below the value (step 213). The rounding
direction has
negligible effect on overall system performance. The order in which the rest
of the
group system transmission matrices Ao'~' ') are considered may have some
effect on
the system performance. A priori knowledge of the spreading factors can be
used
to choose an optimum order in advance.
Using the arrangement techniques described above, and for the case when
spreading factors are even integer multiples of each other, a matrix bandwidth
B
can be achieved which can be shown to be bounded as:
Equation 16
Equation 16 predicts that the bandwidth of the total system transmission
response matrix of Equation 11 will be between 3 and 6. An examination of
Equation 12 reveals that the bandwidth after either arrangement method 99, 199
of
the present invention 17 is 4.
The improvement the present invention 17 provides is further appreciated as
the number of transmitted symbols increase. If a system transmitted 16,000
chips
(800 symbols for a first user and 400 symbols for a second user), the
bandwidth of
the matrix AHA would be approximately 800. Using the arrangement method 99 to
-29-

CA 02617242 2008-01-21
produce a total system response matrix A, the bandwidth of ANHAN remains four
since bandwidth (Equation 16) is independent of the number of transmitted
symbols. After all of the elements of objective matrix 0 are derived, the
inverse 41
is performed. Since the complexity of inverting a matrix is proportional to
the
square of its bandwidth, the present invention 17 provides a reduction of
computational complexity by a factor of approximately (800/4)2=2002=40,000.
The total system transmission response matrix AN provides the response
characteristics to the matched-filter 25. Each colunm of the system response
matrix
AN is a vector which represents the response characteristics of a particular
symbol.
The received data vector r is input to the matched-filter 25 where it is
matched with
every response characteristic from the total system transmission response
matrix
AN to produce a matched filter output vector y. Each element of output vector
y
corresponds to a preliminary estimate of a particular symbol transmitted by a
given
user. The output vector y from the matched-filter 25 is loaded into a
multiplier 43
with the inverted objective matrix O. Both the matched-filter 25 output vector
y
and the inverted objective matrix 0 are multiplied yielding a user data vector
d.
The user data vector d contains all of the data transmitted from all users
during the
discreet time block. Since the objective matrix 0 and the matched filter 25
output
are based on the total system response matrix AN, the user data vector d must
be
de-scrambled. The de-scrambling process 149 is the inverse of the arrangement
methods 99, 199.
-30-

CA 02617242 2008-01-21
A descrambler 45 re-arranges each element of the user data vector d based
upon the column re-assignments performed while undergoing either arrangement
method 99, 199. The elements of the data vector d are in the same order
dictated
by the total transmission response matrix A, 1, 9, 2, 3, 10, 4, 5, 11, 6, 7,
12, 8,
transposed vertically. The descramber 45 allocates a memory space having the
same dimension and places each vector element in sequential order, 1-12. After
the
user data vector d is descrambled 149, the user data is output 23 for further
processing.
While the present invention has been described in terms of the preferred
embodiment, other variations which are within the scope of the invention as
outlined in the claims below will be apparent to those skilled in the art.
-31 -

Representative Drawing