Note: Descriptions are shown in the official language in which they were submitted.
CA 02483850 2000-09-14
TITLE OF THE INVENTLON
REDUCED COMPUTATION LN JOINT DETECTION
This application is a divisional of Canadian patent application Serial No.
2,384,850 filed internationally on September 14, 2000 and entered nationally
on March 11, 2002.
BACKGROUND
The invention generally relates to wireless communication systems. In
particular, the invention relates to joint detection of multiple user signals
in a
wireless communication system.
Figure 1 is an illustration of a wireless communication system 10. The
communication system 10 has base stations 121 to 125 which communicate
with user equipments (UEs) 141 to 143. Each base station 121 has an
associated operational area where it communicates with UEs 141 to 143 in its
operational area.
In some communication systems; such as code division multiple access
(CDMA) and time division duplex using code division multiple access
(TDD/CDMA), multiple communications are sent over the same frequency
spectrum. These communications are typically differentiated by their chip code
sequences. To more efficiently use the frequency spectrum, TDD/CDMA
communication systems use repeating frames divided into time slots for
communication. A communication sent in such a system will have one or
multiple associated chip codes and time slots assigned to it based on the
communication's bandwidth.
Since multiple communications may be sent in the same frequency
spectrum and at the same time, a receiver in such a system must distinguish
between the multiple communications. One approach to detecting such signals
is single user detection. In single user detection, a receiver detects only
the
communication from a desired transmitter using a code associated with the
desired transmitter, and treats signals of other transmitters as interference.
-1-
CA 02483850 2000-09-14
In some situations, it is desirable to be able to detect multiple
communications simultaneously in order to improve performance. Detecting
multiple communications simultaneously is referred to as joint detection. Some
joint detectors use Cholesky decomposition to perform a minimum mean
square error (MMSE) detection and zero-forcing block equalizers (ZF-BLEs).
These detectors have a high complexity requiring extensive receiver resources.
Accordingly, it is desirable to have alternate approaches to joint
detection.
SUMMARY
A plurality of transmitted data signals are received at a receiver. The
receiver measures a channel response associated with the transmitted data
signals. A system response is determined. The system response is expanded
to be piecewise orthogonal. The received data signals data is retrieved based
on in part the expanded system response.
BRIEF DESCRIPTION OF THE DRAWLNGS
Figure 1 is a wireless communication system.
Figure 2 is a simplified transmitter and a receiver using joint detection.
Figure 3 is an illustration of a communication burst.
Figure 4 is an illustration of reduced computation joint detection.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS)
Figure 2 illustrates a simplified transmitter 26 and receiver 28 using joint
detection in a TDD/CDMA communication system. In a typical system, a
transmitter 26 is in each UE 141 to 143 and multiple transmitting circuits 26
sending multiple communications are in each base station 121 to iz5._A base
station 121 will typically require at least one transmitting circuit 26 for
each
actively communicating UE 141 to 143. The joint detection receiver 28 may be
at a base station 121, UEs 141 to 143 or both. The joint detection receiver 28
-2-
CA 02483850 2000-09-14
a
receives communications from multiple transmitters 26 or transmitting circuits
26.
Each transmitter 26 sends data over a wireless communication channel
30. A data generator 32 in the transmitter 26 generates data to be
communicated over a reference channel to a receiver 28. Reference data is
assigned to one or multiple codes and/or time slots based on the
communications bandwidth requirements. A spreading and training sequence
insertion device 34 spreads the reference channel data and makes the spread
reference data time-multiplexed with a training sequence in the appropriate
assigned time slots and codes. The resulting sequence is referred to as a
communication burst. The communication burst is modulated by a modulator
36 to radio frequency. An antenna 38 radiates the RF signal through the
wireless radio channel 30 to an antenna 40 of the receiver 28. The type of
modulation used for the transmitted communication can be any of those
known to those skilled in the art, such as direct phase shift keying (DPSK) or
quadrature phase shift keying (QPSK):
A typical communication burst 16 has a midamble 20, a guard period 18
and two data bursts 22, 24, as shown in Figure 3. The midamble 20 separates
the two data bursts 22, 24 and the guard period 18 separates the
. communication bursts to allow for the difference in arrival times of bursts
transmitted from different transmitters. The two data bursts 22, 24 contain
the communication burst's data and are typically the same symbol length.
The antenna 40 of the receiver 28 receives various radio frequency
signals. The received signals are demodulated by a demodulator 42 to produce
a baseband signal. The baseband signal is processed, such as by a channel
estimation device 44 and a joint detection device 46; in the time slots and
with
the appropriate codes assigned to the communication bursts of the
corresponding transmitters 26, The channel estimation device 44 uses the
training sequence component in' the baseband signal to provide channel
information, such as channel impulse responses. The channel information is
used by the joint detection device 46 to estimate the transmitted data of the
received- communication bursts as soft symbols.
_3_
CA 02483850 2000-09-14
The joint detection device 46 uses the channel information provided by
the channel estimation device 44 and the known spreading codes used by the
transmitters 26 to estimate the data of the various received communication
bursts. Although joint detection is described in conjunction with a TDD/CDMA
communication system, the same approach is applicable to other
communication systems, such as CDMA.
One approach to joint detection in a particular time slot in a TDD/CDMA
communication system is illustrated in Figure 4. A number of communication
bursts are superimposed on each other in the particular time slot, such as K
communication bursts. The K bursts may be from K different transmitters. If
certain transmitters are using multiple codes in the particular time slot, the
K
bursts may be from less than K transmitters.
Each data burst 22, 24 of the communication burst 16 has a predefined
number of transmitted symbols, such as NS. Each symbol is transmitted using
a predetermined number of chips of the spreading code, which is the spreading
factor (SF). In a typical TDD communication system, each base station 121 to
125 has an associated scrambling code mixed with its communicated data. The
scrambling code distinguishes the base stations from one another. Typically,
the scrambling code does not affect the spreading factor. Although the terms
spreading code and factor are used hereafter, for systems using scrambling
codes, the spreading code for the following is the combined scrambling and
spreading codes. Each data burst 22, 24 has NS x SF chips.
The joint detection device 46 estimates the value that each data burst
symbol was originally transmitted. Equation 1 is used to determine the
unknown transmitted symbols.
r=Ad+n
Equation 1
In Equation 1, the known received combined chips, r, is a product of the
system response, A, and the unknown transmitted symbols, d. The term, n,
represents the noise in the wireless radio channel.
For K data bursts, the number of data burst symbols to be recovered is
Ns x K. For analysis purposes, the unknown data burst symbols are arranged
-4-
CA 02483850 2000-09-14
into a column matrix, d. The d matrix has column blocks, di to dNS, of
unknown data symbols. Each data symbol block, d;, has the it" unknown
transmitted data symbol in each of the K data bursts. As a result, each column
block, d;, has K unknown transmitted symbols stacked on top of each other.
The blocks are also stacked in a column on top of each other, such that dl is
on top of d2 and so on.
The joint detection device 46 receives a value for each chip as received.
Each received chip is a composite of all K communication bursts. For analysis
purposes, the composite chips are arranged into a column matrix, r. The
matrix r has a value of each composite chip, totaling Ns * SF chips.
A is the system response matrix. The system response matrix, A, is
formed by convolving the impulse responses with each communication burst
chip code. The convolved result is rearranged to form the system response
matrix, A (step 48).
The joint detection device 46 receives the channel impulse response, h;,
for each it" one of the K communication bursts from the channel estimation
device 44. Each h; has a chip length of W. The joint detection device
convolves the channel impulse responses with the known spreading codes of
the K communication bursts to determine the symbol responses, sl to s,~, of
the K communication bursts. A common support sub-block, S, which is
common to all of the symbol responses is of length K x (SF + W - 1).
The A matrix is arranged to have Ns blocks, B1 to B,~S. Each block has
all of the symbol responses, sl to sK, arranged to be multiplied with the
corresponding unknown data block in the d matrix, dl to dNs. For example, dl
is multiplied with B1. The symbol responses, sl to ~K, form a column in each
block matrix, B;, with the rest of the block being padded with zeros. In the
first
block, Bi, the symbol response row starts at the first row. In the second
block, the symbol response row is SF rows lower in the block and so on. As
a result, each block has a width of K and a height of Ns x SF. Equation 2
illustrates an A block matrix showing the block partitions.
-5-
CA 02483850 2000-09-14
0 0 w 0 t 0 0 0 0 ~
S ... Sx i t
0 0 0 0 i : . . . i : . . . i
i i
i 0 0 0 0 i i
i i i
A_ ; 0 0 0 0 ; ; _r ... ~
~ : . . . ~ 0 0 ~ O i .. CBl B2 BN.,
f I ;
SK I
i i 0 0 0 0 i
i i i
i ~ : . i
t r . . . . ;
i i i
0 0 0 0 ; 0 0 0 0 ~ 0 0 0 0 ~ ~~~
Equation 2
The n matrix has a noise value corresponding to each received combined
chip, totaling Ns x SF chips. For analysis purposes, the n matrix is implicit
in the
received combined chip matrix, r.
Using the block notation, Equation 1 can be rewritten as Equation 3.
d,
d2 N
s
r - [B1 B2 B3 ' ~ . _$tVs,X C1~3 -f- YZ _ ~ + n
i ~ i
i=1
dNs
Equation 3
Using a noisy version of the r matrix, the value for each unknown
symbol can be determined by solving the equation. However, a brute force
approach to solving Equation 1 requires extensive processing.
To reduce the processing; the system response matrix, A, is
repartitioned. Each block, B;, is divided into Ns blocks having a width of K
and
a height of SF. These new blocks are referred to as A1 to A~ and 0. L is the
-6-
CA 02483850 2000-09-14
length of the common support S, as divided by the height of the new blocks,
A1 to A~, per Equation 4.
- SF+W-1~
SF
Equation 4
Blocks A~ to A~ are determined by the supports, sl to sK, and the
common support, S. A 0 block is a block having all zeros. A repartitioned
matrix for a system having a W of 57, SF of 16 and an L of 5 is shown in
Equation 5.
A, 0 0 0 0 0 0 -~~0 0 0
Az Ai 0 0 0 0 0 ~~~0 0 0 0
A3 Az Ai 0 0 0 0 0 0 0 0
Aa As Az Ai 0 0 0 - 0 0 0 0
~
~
As Aa As Az Ai 0 0 - 0 0 0 0
~
~
0 As Aa As Az Ai 0 ~ 0 0 0 0
A=
0 0 As Aa A3 AZ A, . 0 0 0 0
0. 0 0 AS Aa A3 AZ . 0 0 0 0
0 0 0 0 As Aa A3 . A1 0 0 0
0 0 0 0 0 As Aa . AZ Ai 0 0
0 0 0 0 0 0 As . As Az Ai
0 0 0 0 0 0 0 . A4.A3 Az Ai
Equation 5
To reduce the complexity of the matrix, a piecewise orthogonalization
approach is used. Any of the blocks B; for i being L or greater is non-
orthogonal to any of the preceding L blocks and orthogonal to any blocks
preceding by more than L. Each 0 in the repartitioned A matrix is an all zero
block. As a result to use a piecewise orthogonalization, the A matrix is
expanded (step 50).
CA 02483850 2000-09-14
The A matrix is expanded by padding L-1 zero blocks to the right of each
block of the A matrix and shifting each row in the A matrix by its row number
less one. To illustrate for the A1 block in row 2 of Figure 2, four (L-1)
zeros
are inserted between A2 and A1 in row 2. Additionally, block A1 (as well as
A2) is shifted to the right by one column (row 2 -1). As a result, Equation 5
after expansion would become Equation 6.
A, 0 0 0 0 0 0 0 0 0 0
0 Az 0 0 0 AI 0 0 0 0 0
0 0 A3 0 0 0 Az 0 0 0 A,
0 0 0 A4 0 0 0 A3 0 0 0
0 0 0 0 AS 0 0 0 A4 0 0
_ 0 0 0 0 0 0 0 0 0 AS 0
Ae"p 00000000000
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
Equation 6
To accommodate the expanded A matrix, the d matrix must also be
expanded, dexP. Each block, di to dNS, is expanded to a new block, dexpl to
aexpNs~ - -Each expanded block, dexpl to CIexpNsr is formed by repeating the
original
block L times. For example for deXpi, a first block row would be created
having
L versions of d 1, stacked one below the other.
As a result, Equation 1 can be rewritten as Equation 7.
_g_
CA 02483850 2000-09-14
Y = Aexp ' d exp + Yl d expl
d exp 2 N
- jBexpl Bexp2 Bexp3 "' BexpNs,X dexp3 +72 = ~ Bexpi- dexpi + h~
i=1
dexpN,
Equation 7
Equation 7 can be rewritten to partition each Bexp~ orthogonally in L
partitions,
U~~I~, j = 1 to L, as in Equation 8.
r=Aexp-dexp+n di
N~. di N, L N.,
c=~ co ... tl~ ~ _ ci>
=~~Ul UZ UL ~X di: +n=~~Uj di=~Bi_d;+n
i=1 _ i=1 j=1 ~ i=1
d;
Equation 8
To reduce computational complexity, a QR decomposition of the Aexp
matrix is performed (step 52). Equation 9 illustrates the QR decomposition of
Aexp.
Ae~ = Qe~ Rep
Equation 9
Due to the orthogonal partitioning of Aexp, the QR decomposition of Aexp is
less
complex. The resulting Qexp and Reap matrices are periodic with an initial
transient extending over L blocks. Accordingly, Qe~P and Reap can be
determined
by calculating the initial transient and one period of the periodic portion.
Furthermore, the periodic portion of the matrices is effectively determined by
-9-
CA 02483850 2000-09-14
orthogonalizing A1 to A~. One approach to QR decomposition is a Gramm-
Schmidt orthogonalization.
To orthogonalize AeXp as in Equation 6, B~xpl is othogonalized by
independently orthogonalizing each of its orthogonal partitions,
{U~i~}, j = l~ ~ ~L . Each ~A~}, j =1~~~L is independently orthogonalized, and
the
set is zero-padded appropriately. {g~} are the orthonormal sets obtained by
orthogonalizing {Uf'~} . To determine Bexp2~ its Uiz~ needs to be
orthogonalized with respect to only QZ'of BeXPl formed previously. U22~, U32~
and U42~ only need to be orthogonalized with respect to only Q3, Q4 and.Qs,
respectively. U52~ needs to be ortogonalized to all previous Qs and its
orthogonalized result is simply a shifted version of Q5 obtained from
orthogonalizing Bexpi~
As the orthogonalizing continues, beyond the initial transient, there
emerges a periodicity which can be summarized as follows. The result of
orthogonaiizing BeXp;, r > 6 can be obtained simply by a periodic extension of
the result of orthogonalizing Bexp5.
The orthogonalization Of BexpS~ is accomplished as follows. Its Q5 is
obtained by orthogonaiizing A5, and then zero padding. Its Q4 is obtained by
orthogonalizing the support of Q5 and A4, [sup(Q5) A4J, and then zero padding.
Since sup(Q5) is already an orthogonal set, only A4 needs to be othogonalized
with respect to sup(Q5) and itself. Its Q3 is obtained by orthogonalizing
[sup(Q5) sup(Q4) A3] and then zero padding. Its QZ is obtained by
orthogonalizing [sup(Q5) sup(Q4) sup(Q3) AZ] and then zero padding. Its Q1
is obtained by orthogonalizing [sup(Q5) sup(Q4) sup(Q3) sup(QZ) AiJ and then
zero padding. Apart from the initial transient, the entire AeXp can be
efficiently
orthogonalized, by just orthogonalizing: Ap per Equation 10.
Ap = [As A4 A3 A2 Ay
-10-
CA 02483850 2000-09-14
Equation 10
By effectively orthogonalizing the periodic portion of Aexp by using only Ap,
computational efficiency is achieved. Using a more compact notation, Qts ,for
sup(Q~), this orthogonalization of AP results in the orthonormal matrix, Qp,
of
Equation 11.
~p - ~~5 ~4 ~3 ~2 ~1
Equation 11
The periodic part of Qexp is per Equation 12.
0 0 0 0 0 0 0 0 0 0
Q; o 0 0 0 0 0 0 0
o QZ o 0 0 Q; o 0 0 0
O O 3 O O O i O O O
O O 0 4 O 0 0 3 O O
_
PeriodicPartofQ0 0 0 0 5 0 0 0 4 0
exp '
,
O O 0 O O O O O O QS
O 0 O O O O 0 O o 0
O
O O 0 O O O O O O O w
Equation 12
To constructing the upper triangular matrix ReXp, ~A; ~ is a block of size
J
K x K representing the projections of each column of A; onto all the columns
of Q~ . For example, the first column of ~A4~5 represents the projections of
the first column of A4 on each of the K columns of QS . Similarly, ~A4~4
represents the projections of the first column of A4 on each of the K columns
of Q4S . However, this block will be upper triangular, because the kt" column
of
-11-
CA 02483850 2000-09-14
A4 belongs to the space spanned by the orthonormal vectors of QS and the
first k vectors of ~5 . This block is also orthogonal to subsequent vectors in
Q4S; leading to an upper triangular ~A4~4 . Any ~AL~~ with i = j will be upper
triangular. To orthogonalize other blocks, the following results.
The first block Of BexpS, viz., U;S~ is formed by a linear combination of
{QS} j = l~ ~ ~S, with coefficients given by ~Ai~~, j = l~ ~ ~5 . The second
block,
U2S~, is formed by a Linear combination of {Q~ }, j = 2~ ~ ~5, with
coefficients
given by ~A2~~, j = 2~ ~ 5 . The third block, U35~, is formed by a linear
combination of {Q~ }, j = 3~~-5, with coefficients given by ~AZ~~, j = 3~~~5 .
The
fourth. block, U45~, is formed by a linear combination of {Q~ }, j = 4,S ,
with
coefficients given by ~A2~~, j = 4;5 . The fifth block, U55~, is formed by
QSX~~~g
5
Accordingly, the coefficients in the expansion of subsequent BeXp;, i > 6
are simply periodic extensions of the above. Since the Reap entries are
computed during the orthogonalization of Aexp, no additional computations are
needed to construct Reap. Disregarding the initial transient, the remainder of
ReXp IS periodic, and two periods of it are shown in Equation 13.
-12-
CA 02483850 2000-09-14
0 0 0 0 0 0 0 0 0 0
,A''
s
!\
/,
0
0
0
~A,~ 0 0 0 0 0 0 0 0
4 ~Az~ 0 0 0 ~A,~0 0 0
0
O O O O O O O O O
s s
O O O O 0 O O O 0
~A,~3 0 0 0 0 0 0 0 0
p ~Az~ 0 0 0 ~A,~0 0 0
4 4
O O ~A3~ O O O ~A2~ O O
5
O O 5 O 0 O O 0 O
0
~A,~ 0 0 0 0 0 0 0 0
Rexpz
- 0 0 ~Az~ 0 0 0 ~A,~0 0 0
0 3 ~Aa~ 0 0 0 ~Az~ 0 0
0
4
O O O ~A4~ 0 O O ~A3> O
5 5
~A,~ 0 0 0 0 0 0 0 0
,
1 ~Az~ 0 0 0 ~A,~0 0 0
0
2 2
0 0 ~A3~ 0 0 0 ~Az~ 0 0
3
0 0 3 ~A4~ 0 0 0 ~A3~ 0
0
4 4
0 0 0 0 ~As~ 0 0 0 ~A4~
s s
0 0 0 0 0 ~A,~0 0 0
0 0 0 0 0 0 ~Az~ 0 0
z
0 0 0 0 0 0 0 ~A3~ 0
3
0 0 0 0 0 0 0 0 CAc
4
0 0 0 0 0 0 0 0 0 ~As~
s
0 0 0 0 0 0 0 0 0 0 ~Ay
Equation 13
-13-
CA 02483850 2000-09-14
The least squares approach to solving Qexp and Rexp is shown in Equation 14.
Qexp ' Rexp ' dexp - ~
Equation 14
By pre-multiplying both sides of Equation i4 by the transpose of Qexp , Qe p ,
and using Q Xp ~ Qexp - ILxws ~ Equation 14 becomes Equation 15.
_ nT
Rexp ' dexp - ~exp r
Equation 15
Equation 15 represents a triangular system whose solution also solves the LS
problem of Equation 14.
Due to the expansion, the number of unknowns is increased by a factor
of L. Since the unknowns are repeated by a factor of L, to reduce the
complexity, the repeated unknowns can be collected to collapse the system.
ReXP is collapsed using L coefficient blocks, CFl to CFA, each having a width
and
a height of K. For a system having an L of 5, CFl to CFs can be determined as
in Equation 16.
CFi = ~Ay, + ~Az~z + ~A3~3 + ~Aa~4 + ~As~S
CFz = ~Ayz + ~Az~3 + ~As~4 + ~Aa~s
CFs = ~Ay3 + ~Az~4 + ~A3~5
CFa - ~AI~4 + ~Az~s
CFs = ~Ays
Equation 16
Collapsing RexP using the coefficient blocks produces a Cholesky like factor,
G
(step 54). By performing analogous operations on the right hand side of
Equation 15 results in a banded upper triangular system of height and width of
K x Ns as in Equation 17.
-14-
CA 02483850 2000-09-14
Try Trz Tr3 Tra CFs 0 0 0 0 0 --
0 Tr1 Trz CF3 CFa CFs 0 0 0 0 " a
z
0 0 CFI CFz CF3 CFa CFs 0 0 0 '
'
X d =
3 i~
0 0 0 CFI CFz CF3 CFa CFs 0 0 -
0 0 0 0 CFI CFz CF3 CFa CFs 0 '
-
~
d
.'
.
o . . . . o
Equation 17
Trl to Tr4 are the transient terms and y' . By solving the upper triangle via
back substitution, Equation 17 can be solved to determine d (step 56). As a
result, the transmitted data symbols of the K data bursts is determined.
Using the piecewise orthagonalization and Qft decomposition, the
complexity of solving the least square problem when compared with a banded
Cholesky decomposition is reduced by a factor of 6.5.
-15-
