Note: Descriptions are shown in the official language in which they were submitted.
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
[0001] REDUCED COMPLEXITY SLIDING WINDOW BASED EQUALIZER
[0002] FIELD OF INVENTION
[0003] The invention generally relates to wireless communication
systems, In particular, the invention relates to data detection in such
systems.
[0004] ' BACKGROUND
[0005] Due to the increased demands for improved receiver
performance, many advanced receivers use zero forcing (ZF) block linear
equalizers and minimum mean square error (MMSE) equalizers.
[0006] In both these approaches, the received signal is typically modeled
per Equation 1.
r = Hd + n Equation 1
[0007] r is the received vector, comprising samples of the received
signal. H is the channel response matrix. d is the data vector to be
estimated.
In spread spectrum systems, such as code division multiple access (CDMA)
systems, d may be represented as data symbols or a composite spread data
vector. For a composite spread data vector, the data symbols for each
individual
code are produced by despreading the estimated data vector d with that code. n
is the noise vector.
[0008] In a ZF block linear equalizer, the data vector is estimated, such
as per Equation 2.
d=(HHH)IHHr Equation 2
[0009] ~~)H is the complex conjugate transpose (or Hermetian) operation.
In a MMSE block linear equalizer, the data vector is estimated, such as per
Equation 3.
d=(HHH+aZI~IHHr Equation 3
[0010] In wireless channels experiencing multipath propagation, to
accurately detect the data using these approaches requires that an infinite
number of received samples be used, which is not practical. Therefore, it is
desirable to use an approximation technique. One of the approaches is a
sliding
-1
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
window approach. In the sliding window approach, a predetermined window of
received samples and channel responses are used in the data detection. After
the
initial detection, the window is slid down to a next window of samples. This
process continues until the communication ceases.
[0011] By not using an infinite number of samples, 'an error is
introduced into the symbol model shown in Equation 1 and, therefore causes
inaccurate data detection. The error is most prominent at the beginning and
end
of the window, where the effectively truncated portions of the infinite
sequence
have the largest impact. One approach to reduce these errors is to use a large
window size and truncate the results at the beginning and the end of the
window.
The truncated portions of the window are determined in previous and
subsequent windows. This approach has considerable complexity, especially
when the channel delay spread is large. The large window size leads to large
dimensions on the matrices and vectors used in the data estimation.
Additionally, this approach is not computationally efficient by detection data
at
the beginning and at the ends of the window and then discarding that data.
[0012] Accordingly, it is desirable to have alternate approaches to data
detection.
[0013] SUMMARY
[0014] The present invention has many aspects. One aspect of the
invention is to perform equalization using a sliding window approach. A second
aspect reuses information derived for each window for use by a subsequent
window. A third aspect utilizes a discrete Fourier transform based approach
for
the equalization. A fourth aspect relates to handling oversampling of the
received signals and channel responses. A fifth aspect relates to handling
multiple reception antennas. A sixth embodiment relates to handling both
oversampling and multiple reception antennas.
-2-
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
[0015] BRIEF DESCRIPTION OF THE DRAWINGS)
[0016] Figure 1 is an illustration of a banded channel response matrix.
[0017] Figure 2 is an illustration of a center portion of the banded
channel response matrix.
[0018] Figure 3 is an illustration of a data vector window with one
possible partitioning.
[0019] Figure 4 is an illustration of a partitioned signal model.
[0020] Figure 5 is a flow diagram of sliding window data detection using
a past correction factor.
[0021] Figure 6 is a receiver using sliding window data detection using
a past correction factor.
[0022] Figure 7 is a flow diagram of sliding window data detection using
a noise auto-correlation correction factor.
[0023] Figure 8 is a receiver using sliding window data detection using
a noise auto-correlation correction factor.
[0024] Figure 9 is a graphical representation of the sliding window
process.
[0025] Figure 10 is a graphical representation of the sliding window
process using a circulant approximation.
[0026] Figure 11 is a circuit for an embodiment for detecting data using
discrete Fourier transforms (DFTs).
[0027] DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS)
[0028] Although the features and elements of the present invention are
described in the preferred embodiments in particular combinations, each
feature
or element can be used alone (without the other features and elements of the
preferred embodiments) or in various combinations with or without other
features and elements of the present invention.
[0029] Hereafter, a wireless transmit/receive unit (WTRU) includes but
is not limited to a user equipment, mobile station, fixed or mobile subscriber
unit,
pager, or any other type of device capable of operating in a wireless
environment.
-3-
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
When referred to hereafter, a base station includes but is not limited to a
Node-B,
site controller, access point or any other type of interfacing device in a
wireless
environment.
[0030] Although reduced complexity sliding window equalizer is
described in conjunction with a preferred wireless code division multiple
access
communication system, such as CDMA2000 and universal mobile terrestrial
system (UMTS) frequency division duplex (FDD), time division duplex (TDD)
modes and time division synchronous CDMA (TD-SCDMA), it can be applied to
various communication system and, in particular, various wireless
communication systems. In a wireless communication system, it can be applied
to transmissions received by a WTRU from a base station, received by a base
station from one or multiple WTRUs or received by one WTRU from another
WTRU, such as in an ad hoc mode of operation.
[0031] The following describes the implementation of a reduced
complexity sliding window based equalizer using a preferred MMSE algorithm.
However, other algorithms can be used, such as a zero forcing algorithm. h(~)
is
the impulse response of a channel. d (k) is the k th transmitted sample that
is
generated by spreading a symbol using a spreading code. It can also be sum of
the chips that are generated by spreading a set of symbols using a set of
codes,
such as orthogonal codes. ~(~) is the received signal. The model of the system
can expressed as per Equation 4.
~(t) _ ~ d (k)h(t - kT~ ) + n(t) - oo < t < oo Equation 4
k=-~o
[0032] n(t) is the sum of additive noise and interference (intra-cell and
inter-cell). For simplicity, the following is described assuming chip rate
sampling
is used at the receiver, although other sampling rates may be used, such as a
multiple of the chip rate. The sampled received signal can be expressed as per
Equation 5.
-4-
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
r(j) _ ~d(k)h(j-k)+n(j) _ ~d(>-k)h(k)+ra(j) .7 ~ f...,-2,-1,0,1,2,...
k=-~o k=-~o
Equation 5
T~ is being dropped for simplicity in the notations.
[0033] Assuming h(~) has a finite support and is time invariant. This
means that in the discrete-time domain, index L exists such that h(i) = 0 for
i < 0
and i >- L . As a result, Equation 5 can be re-written as Equation 6.
L-1
r( j) _ ~ h(k)d ( j - k) + rz( j) j E f ...,-2,-1,0,1,2,... Equation s
k=0
[0034] Considering that the received signal has M received signals
\ r'(0), - ~ ~, r~(M -1) , Equation 7 results.
r=Hd+n
where,
r = [y~(0)~ . . . ~ y.(M -1)]T E C'u ,
d = ~d (-L + 1), d (-L + 2),..., d (0), d (1),.'., d (M -1)~T E ~M+L.1
n = [ra(0), "',1Z M -1)]T E CM
h(L -1) h(L - 2) ~ ~ ~ h(1) h(0) 0
H - 0 h(L -1) lz(L - 2) ~ ~ ~ h(1) h(0) 0 ~ ~ ~ E ~,Mx(M+L-1)
0 h(L-1) h.(L-2) ~~~ la(1) h(0)
Equation 7
[0035] In Equation 7, CM represents the space of all complex vectors
with dimension M.
[0036] Part of the vector d can be determined using an approximate
equation. Assuming M > L and defining N = M - L + 1, vector d is per Equation
8.
d = [d (-L + 1), d (-L + 2),..., d (-1),d (0), d (1),..., d (N -1),d (N),...,
d (N + L - 2)]T E G'N+2L-2
L-1 N L-1
Equation 8
_5_
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
[0037] The H matrix in Equation 7 is a banded matrix, which can be
represented as the diagram in Figure 1. In Figure 1, each row in the shaded
area
represents the vector [h(L -1), h(L - 2),..., h(1), h(0)], as shown in
Equation 7.
[0038] Instead of estimating all of the elements in d, only the middle N
elements of d are estimated. d is the middle N elements as per Equation 9.
d = [d (0),..., d (N -1)]T
Equation 9
[0039] Using the same observation for r, an approximate linear relation
between r and d is per Equation 10.
r=Hd+n
Equation 10
[0040] Matrix H can be represented as the diagram in Figure 2 or as
per Equation 11.
h(0) 0
h(1) h(0)
h(1) . 0
H= h(L-1) . , h(0)
0 h(L -1) . h(1)
0
h(L -1)
Equation 11
[0041] As shown, the first L-1 and the last L-1 elements of r are not
equal to the right hand side of the Equation 10. As a result, the elements at
the
two ends of vector d will be estimated less accurately than those near the
center.
Due to this property, a sliding window approach, as described subsequently, is
preferably used for estimation of transmitted samples, such as chips.
[0042] In each kth step of the sliding window approach, a certain number
of the received samples are kept in r [h] with dimension N+L-1. They are used
to
estimate a set of transmitted data d[k] with dimension N using equation 10.
After vector d[k] is estimated, only the "middle" part of the estimated vector
d [k]
is used for the further data processing, such as by despreading. The "lower"
part
-6-
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
(or the later in-time part) of d[k] is estimated again in the next step of the
sliding
window process in which r [k+1] has some of the elements r [h] and some new
received samples, i.e. it is a shift (slide) version of r [k].
[0043] Although, preferably, the window size N and the sliding step size
are design parameters, (based on delay spread of the channel (L), the accuracy
requirement for the data estimation and the complexity limitation for
implementation), the following using the window size of Equation 12 for
illustrative purposes.
N=4NS xSF
Equation 12
SF is the spreading factor. Typical window sizes are 5 to 20 times larger than
the channel impulse response, although other sizes may be used.
[0044] The sliding step size based on the window size of Equation 12 is,
preferably, 2NS x SF . NS ~ ~1,2,...~ is, preferably, left as a design
parameter. In
addition, in each sliding step, the estimated chips that are sent to the
despreader
are 2NS x SF elements in the middle of the estimated d[k] . This procedure is
illustrated in Figure 3.
[0045] In the sliding window approach described above, the system
model is approximated by throwing away some terms in the model. In the
following, a technique is described where terms are kept by either using the
information estimated in previous sliding step or characterizing the terms as
noise in the model. The system model is corrected using the keptlcharacterized
terms.
_7_
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
[0046] One algorithm of data detection uses an MMSE algorithm with
model error correction uses a sliding window based approach and the system
model of Equation Z0.
[0047] Due to the approximation, the estimation of the data, such as
chips, has error, especially, at the two ends of the data vector in each
sliding step
(the beginning and end). To correct this error, the H matrix in Equation 7 is
partitioned into a block row matrix, as per Equation 13, (step 50).
H=~HP ~ H I Hf]
Equation 13
[0048] Subscript "p" stands for "past", and "f" stands for "future". H is
as per Equation 10. HP is per Equation 14.
h(L -1) h(L - 2) ~ ~ ~ h(1)
0 lz(L-1) ~~~ h(2)
H 0 ~ ~ ~ 0 h(L -1) E ~'(N+L-1)x(L-I)
P -
... ...
... ...
Equation 14
[0049] H f is per Equation 15.
0 ~~~ ~~~ 0
~ ... ... 0
H f = h(0) p ... 0 E ecrr+L-~>x~L-~>
0
h(L - 3) ~ ~ ~ la(0) 0
h(L - 2) h(L - 3) ~ ~ ~ h(0)
Equation 15
[0050] The vector d is also partitioned into blocks as per Equation 16.
d = Ldn I dT I df
Equation 16
_g_
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
[0051] d is the same as per Equation 8 and dp is per Equation 17.
d p = ~d (-L + 1) d (-L + 2) ~ ~ ~ d (-1)]T E CL-'
Equation 17
[0052] d f is per Equation 18.
d f = ~d(N) d(N+1) ~~~ d(N+L-2)]T E CL-'
Equation 18
[0053] The original system model is then per Equation 19 and is
illustrated in Figure 4.
r = HPd~ +Hd+H fd f +n
Equation 19
[0054] One approach to model Equation 19 is per Equation 20.
r =Hd+nl
where r = r - H p d p and n, = H f d f + n
Equation 20
[0055] Using an MMSE algorithm, the estimated data vector d is per
Equation 21.
d = g~HH (gdHHH + E1)-'r
Equation 21
[0056] In Equation 21, gd is chip energy per Equation 22.
E{d(i)d*(.I)}= gds
Equation 22
[0057] r is per Equation 23.
r =r-HPdp
Equation 23
_g_
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
[0058] dP , is part of the estimation of d in the previous sliding window
step. ~1 is the autocorrelation matrix of n1 , i.e., El = E f nlnlH }. If
assuming
H rd f and n are uncorrelated, Equation 24 results.
E, =gaHfH f +E{nnH}
Equation 24
[0059] The reliability of d~ depends on the sliding window size (relative
to the channel delay span L) and sliding step size.
[0060] This approach is also described in conjunction with the flow
diagram of Figure 5 and preferred receiver components of Figure 6, which can
be
implemented in a WTRU or base station. The circuit of Figure 6 can be
implemented on a single integrated circuit (IC), such as an application
specific
integrated circuit (ASIC), on multiple IC's, as discrete components or as a
combination of IC('s) and discrete components.
[0061] A channel estimation device 20 processes the received vector r
producing the channel estimate matrix portions, H p , H and H f , (step 50). A
future noise auto-correlation device 24 determines a future noise auto-
correlation
factor, gdH fH f , (step 52). A noise auto-correlation device 22 determines a
noise
auto-correlation factor, E{nnH ~, (step 54). A summer 26 sums the two factors
together to produce ~, , (step 56).
[0062] A past input correction device 28 takes the past portion of the
channel response matrix, H p , and a past determined portion of the data
vector,
dp, to produce a past correction factor, HpdP, (step 58). A subtractor 30
subtracts the past correction factor from the received vector producing a
modified
received vector, r , (step 60). An MMSE device 34 uses ~" H, and r to
determine the received data vector center portion d , such as per Equation 21,
(step 62). The next window is determined in the same manner using a portion of
d as dp in the next window determination, (step 64). As illustrated in this
~ approach, only data for the portion of interest, d , is determined reducing
the
-10-
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
complexity involved in the data detection and the truncating of unwanted
portions of the data vector.
[0063] In another approach to data detection, only the noise term is
corrected. In this approach, the system model is per Equation 25.
r=Hd+nz,where nz=Hpdp+Hfdf+n
Equation 25
[0064] Using an MMSE algorithm, the estimated data vector d is per
Equation 26.
d-gdHH(gdHHH+~2) 1r
Equation 26
[0065] Assuming HpdP, Hfd f andn are uncorrelated, Equation 27
results.
~z =gdHpH~ +gdH fH f +E{nnH
Equation 27
[0066] To reduce the complexity in solving Equation 26 using Equation
27, a full matrix multiplication for H pHP and H fH f are not necessary, since
only the upper and lower corner of Hp and H f, respectively, are non-zero, in
general.
[0067] This approach is also described in conjunction with the flow
diagram of Figure 7 and preferred receiver components of Figure 8, which can
be
implemented in a WTRU or base station. The circuit of Figure 8 can be
implemented on a single integrated circuit (IC), such as an application
specific
integrated circuit (ASIC), on multiple IC's, as discrete components or as a
combination of IC('s) and discrete components.
[0068] A channel estimation device 36 processes the received vector
producing the channel estimate matrix portions, H p , H and H f , (step 70). A
noise auto-correlation correction device 38 determines a noise auto-
correlation
correction factor, gdHPH p +gdH fH f , using the future and past portions of
the
channel response matrix, (step 72). A noise auto correlation device 40
determines
-11-
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
a noise auto-correlation factor, E{nnH }, (step 74). A summer 42 adds the
noise
auto-correlation correction factor to the noise auto-correlation factor to
produce
EZ , (step 76). An MMSE device 44 uses the center portion or the channel
response matrix, H , the received vector, r , and Ez to estimate the center
portion
of the data vector, d , (step 78). One advantage to this approach is that a
feedback loop using the detected data is not required. As a result, the
different
slided window version can be determined in parallel and not sequentially.
[0069] Discrete Fourier Transform Based Equalization
[0070] The sliding window approach described above requires a matrix
inversion, which is a complex process. One embodiment for implementing a
sliding window utilizes discrete Fourier transforms (DFTs), as follows.
Although
the preferred implementation of the DFT based approach is with a MMSE
algorithm, it can be applied to other algorithms, such as a zero forcing (ZF)
based
algorithm.
[0071] A matrix A~;r E G'NxN , for some integer N, is a circulant matrix if
it has the following form per Equation 28.
a~ aN aN-1 az
as al aN . . ,
A~,r = . a2 al . aN_~
as . aN
aN aN_1 . a1
Equation 28
[0072] This kind of matrix is expressed using the DFT and the IDFT
operators, such as per Equation 29.
A~;r =FN A(A~;r[~alDFN
Where, A~~r [:,l] _ (a0, al,..., aT,)T E CN , 1.e. It 1S the first column of
matrix A~~r
Equation 29
-12-
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
Columns other than the first column can be used if properly permuted. FN is
the
N point DFT matrix which is defined as, for any x E CN, as per Equation 30.
N-1 ~_Znkn
(FNx)k =~x(h)e N k=0,...,N-1
n=0
Equation 30
FN' is the N-point inverse DFT matrix which is defined as, for any x E CN, as
per
Equation 31.
(FNIx)k = 1 (FNx)k = 1 ~x(h)e JzN 1 k = 0,...,N 1
N N n=0
Equation 31
AN (~) is a diagonal matrix, which is defined as, for any x E CN, as per
Equation
32.
AN (x) = diag(FNx)
Equation 32
[0073] The inverse of matrix A~,r is expressed, such as per Equation 33.
A~~r -FN1AN(A~;r[~~1DFN
Equation 33
[0074] The following is an application of a DFT based approach to the
data estimation process using the sliding window based chip level equalizer.
The
first embodiment uses a single receiving antenna. Subsequent embodiments use
multiple receiving antennas.
[0075] The receiver system is modeled as per Equation 34.
r(t) _ ~ d (k)7Z(t - kT~ ) + f~(t) - oo < t < o0
k- ~
Equation 34
-13-
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
h(~) is the impulse response of the channel, d (k) is the k th transmitted
chip
samples that is generated by spreading symbols using a spreading code. r(~) is
the received signal. n(~) is the sum of additive noise and interference (intra-
cell
and inter-cell).
[0076] Using chip rate sampling and h(~) having a finite support, which
means, in discrete-time domain, there is an integer L such that h(i) = 0 for i
< 0
and i >- L , the sampled received signal can be expressed (T~ is dropped for
simplicity of the notations), as per Equation 35.
L-1
r(,j)=~h(k)d(j-k)+h(j) j E f...,-2,-1,0,1,2,...}
k=0
Equation 35
[0077] Based on M (M > L ) received signals Y(0),- ~ ~, r(M -1) , Equation 36
results.
r=Hd+n
where
r = [~"(0)~ ~ . . ~ y~(Nj' -1)]T E CM
d = [d (-L + 1), d (-L + 2),..., d (0), d (1),..., d (M -1)]T E CM+L=~
n=[h(0)~~..~y~(M-1)]T EC'~r
h(L -1) h(L - 2) ~ ~ ~ h(1) h(0) 0 ~ ~ . .. .
- 0 h(L -1) h(L - 2) ~ ~ ~ 1Z(1) h(0) 0 ~ ~ v E ~,Mx(M+L-1)
0 la(L -1) h(L - 2) ~ ~ ~ h(1) h(0)
Equation 36
[007] As illustrated by Equation 36, the H matrix is Toeplitz. As
described subsequently in the application for multiple chip rate sampling
and/or
multiple receive antennas, the H matrix is block Toeplitz. Using the block
-14-
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
Toeplitz property, discrete Fourier transform techniques can be applied. The
Toeplitzlblock Toeplitz nature is produced as a result of the convolution with
one
channel or the convolution of the input signal with a finite number of
effective
parallel channels. The effective parallel channels appear as a result of
either
oversampling or multiple receive antennas. For one channel, a single row is
essentially slide down and to the right producing a Toeplitz matrix.
[0079] The statistics of the noise vector are treated as having the
autocorrelation property, per Equation 37.
Efn nH}=a-zI
Equation 37
[0080] The left hand side of equation (5) can be viewed as a "window" of
continuous input signal stream. To estimate the data, an approximated model is
used. In this approximated model, the first L-1 and the last L-1 elements of
vector d are assumed to be zero before applying the MMSE algorithm and the
reset M - L + 1 elements of d forms a new vector d = [d (0),..., d (M - L +
1)]T . The
approximated model can be expressed explicitly as per Equation 38.
r=Hd+n
h(0) 0
h(1) h(0)
h(1) . 0
where h(L-1). . h(0)
H=
0 h(L-1) . h(1)
0
h(L -1)
Equation 38
[0081] After the vector d is estimated, only the middle part of it is
taken for de-spreading. Subsequently, the window of observation (i.e. the
-15-
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
received signal) is slid by (M - L + 1) l2 elements and the process is
repeated.
Figure 9 is a graphical representation of the sliding window process, as
described
above.
[00S2] Using MMSE algorithm, the estimated data is expressed per
Equation 39.
d -- R_'Hxr
where R = HHH + o-ZI
Equation 39
[00S3] In Equation 39, neither the matrix R nor the matrix H is
circulant to facilitate a DFT implementation. To facilitate a DFT
implementation, for each sliding step, the approximated system model per
Equation 40 is used.
r=Hd+n
h(0) 0 ...
h(1) h(0)
h(1) . 0
where H = h(L -1) . . h(0) 0 E ~MxM
0 h(L-1) . h(1) h(0)
0 . . . . 0
h(L -1) h(L - 2) ~ ~ ~ h(0)
d = [d (0),..., d (M -1)]T E CM~'
Equation 40
-16-
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
In Equation 40, only the first L -1 elements (equations) are approximations of
those of Equation 36.
[0084] The matrix H is replaces by a circulant matrix, such as per
Equation 41.
h(0) 0 ~ ~ ~ 0 h(L .. . h(1)
-1)
h(1) h(0) . . 0 . .
h(1) . 0 . h(L -1)
H~;r h(L-1). . h(0) 0 . 0
=
0 h(L . h(1) h(0) . .
-1)
0 . . . . 0
0 . . h(L-1)h(L-2) ~~~ h(0)
Equation 41
[0085] The system model, for each sliding step, is per Equation 42.
r = H~ird + n
with d = [d (0),..., d (M -1)]T E CMx'
Equation 42
The vector d in Equation 42, due to the new model, is different than the
vector d in Equation 36. Equation 42 adds additional distortion to the first L-
1
element of Equation 39. This distortion makes the two ends of the estimated
vector d inaccurate. Figure 10 is a graphical representation of the model
construction process.
[0086] Using approximated model per Equation 42, the MMSE
algorithm yields the estimated data as per Equation 43.
_ 1 H
d RcirHcirr
-17-
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
where R~,r = HH H~" + o-ZI
Equation 43
Both HH and R~;, are circulant and R~;r is of the form per Equation 44.
Ro RI ... RL-1 0 0 ... R2 Ri
R; . R, RL_I . 0 RL_,
RL_t . Ro RI . 0 0 0 RL_I
0 RL_1 Ri Ro . RL_I 0 . 0
' 0 . R, . . RL_I . 0
R"r - 0 . . RL_1 . . R, . 0 0
RL_1 0 . 0 RL_1 . Ro Rl RL_1 0
* *
RL_1 . 0 RL_1 R1 Ro . RL_,
0 0 . R; . R,
*
0 . RL_, . Ro R,
RI Rz ... 0 ... 0 0 RL_1 ... Ri Ro
Equation 44
[0087] Applying the properties of circulant matrices, the estimated data
is per Equation 45.
d = FM ~M (R~;r[~~l])~M (HH [-~ll)FMr
Equation 45
[0088] Figure 11 is a diagram of a circuit for estimating the data per
Equation 45. The circuit of Figure 11 can be implemented on a single
integrated
circuit (IC), such as an application specific integrated circuit (ASIC), on
multiple
IC's, as discrete components or as a combination of IC('s) and discrete
components.
[0089] The estimated channel response H is processed by an H
determination device 80 to determine the Toeplitz matrix H . A circulant
approximation device 82 processes H to produce a circulant matrix H~,r . A
-18
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
Hermetian device 84 produces the Hermetian of H ~,r , H H . Using H ~~r , H H
and
the noise variance 6~, R~;r is determined by a R~,r determining device 86.
Using
a first column of HH , a diagonal matrix is determined by a AM (HH [:,1])
determining device 88. Using a first column of R~;r, an inverse diagonal
matrix
is determined by a AM (R~IY [:,1]) determination device 90. A discrete Fourier
transform device 92 performs a transform on the received vector, r. The
diagonal, inverse diagonal and Fourier transform result are multiplied
together
by a multiplier 96. An inverse Fourier transform device 94 takes an inverse
transform of the result of the multiplication to produce the data vector d .
[0090] The sliding window approach is based on an assumption that the
channel is invariant within each sliding window. The channel impulse response
near the beginning of the sliding window may be used for each sliding step.
[0091] One preferred approach for determining the window step size NSS
and window size M is per Equation 46, although others may be used.
Nss - 2Nsymbol ~ SF and M = 4NSymvor ~ SF
Equation 46
Nsymbor E f 1,2,...} is the number of symbols and is a design parameter which
should
be selected, such that M > L . Since M is also the parameter for DFT which may
be implemented using FFT algorithm. M may be made large enough such that
the radix-2 FFT or a prime factor algorithm (PFA) FFT can be applied. After
the
data is estimated, ZNSy",bo, x SF samples are taken to process despreading
starting
from Nsymb~!'~ SFth sample. Figure 11 is an illustration of taking the samples
for
despreading.
-19-
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
[0092] Multiple Receive Antenna Equalization
[0093] The following is an embodiment using multiple receive antennas,
such as Kreceive antennas. Samples of the received vector and estimates of the
channel impulse response are taken for each antenna independently. Following
the same process as for the single antenna embodiment, each antenna input, rk
,
is approximated per Equation 47.
rk = H~;,,kd+nk for k = 1, ..., K
Equation 47
or in block matrix form per Equation 48
r2 H~rr,z d+ na
rx H~~r,x nx
Equation 4~
[0094] Equations 49 and 50 are estimates of the auto-correlation and
cross-correlation properties of the noise terms.
E{nknk }= a-ZI for k =1,...,K
Equation 49
and
EfnknH}=0 forks j
Equation 50
[0095] Applying MMSE algorithm, the estimated data can be expressed
as per Equation 51.
-20-
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
x
-1 ~ H
d = Rcir Ilcir,krk
k=I
K
where R~ir =~I3H,kflcir,k +~'zI
k=I
Equation 51
R~,r is still a circulant matrix and the estimated data can be determined per
Equation 52.
K
d = FM AM (Rcir [~~l])~ AM (IIH ,k [~~l])FMrk
k=I
Equation 52
[0096] If the receive antennas are positioned close to each other, the
noise terms may be correlated in both time and space. As a result, some
degradation in the performance may result.
[0097] Multiple Chip Rate Sampling (Oversampling) Equalization
[0098] The following describes embodiments using a sliding window
based equalization approach with multiple chip rate sampling. Multiple chip
rate sampling is when the channel is sampled at a sampling rate which is an
integer multiple of the chip rate, such as two times, three times, etc.
Although
the following concentrates on two times per chip sampling, these approaches
can
be applied to other multiples.
[0099] Using a sliding window of width of N chips and two time chip
rate sampling, our received vector is r=[ro,rl,...,Y2N-1]T ~ This vector may
be
rearranged and separated into an even received vector re = [r~, r2,. .., rZN-z
]T and an
odd received vector ro = [3"I, K3 ~"' ~ ~2N-I ]T = with r = [re, ro ]T .
Without loss of
generality, the data transmission model is per Equation 53.
-21-
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
r H a CI -~- n a
re Ho no
Equation 53
Equation 53 separates the effective 2-sample-per-chip discrete-time channel
into
two chip-rate discrete-time channels.
[00100] The matrices He and Ho in Equation 53 are, correspondingly, the
even and odd channel response matrices. These matrices are constructed from
the even and odd channel response vectors he and ho, which are obtained by
sampling the channel response at 2 samples per chip and separating it into the
even and odd channel response vectors.
[00101] The channel noise is modeled as white with a variance o-2 , as per
Eqaution 54.
E[neneH] = E[nonoH] = a.aI
Equation 54
[00102] If the channel is an additive white Gaussian noise (AWGN)
channel and the received data is provided directly from the sampled channel,
then Equation 55 results.
E[nenex] = 0
Equation 55
[00103] As a result, the problem is mathematically similar to the case of
the chip-rate equalizer for 2 receive antennas with uncorrelated noise, as
previously described. However, the received antenna signals in many
implementations are processed by a receive-side root-raised cosine (RRC)
filter
before being provided to the digital receiver logic for further processing.
Following such processing, the received noise vector is no longer white, but
has a
raised-cosine (RC) autocorrelation function. RC is the frequency-domain square
of a RRC response. Since the RC pulse is a Nyquist pulse, Equation 54 holds,
however Equation 55 does not. The (a~j)th element of the matrix
def
A~rass = ~z E[neneH] is per Equation 56.
-22-
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
H
6z E[neno ](y.i) = xxc ~~ i -.7 ~ +0.5)
Equation 56
xRC is the unity-symbol-time normalized RC pulse shape.
[00104] Properties of A~,oss are it is real, symmetric and Toeplitz; it is not
banded and has no zero entries and its entries do get smaller and tend to 0 as
they get farther and farther away from the main diagonal.
[00105] En represent the cross-correlation matrix of the total noise vector
and is per Equation 57.
= 6 z I E cross
~,
~ cross I
Equation 57
[00106] Exact Solution
[00107] The exact solution to the problem of linear minimum mean-
square estimation of d from the observation of r is per Equation 58.
dMMSE =(HH~~t'H+I)'HH~,~'r
where y = HH~n'r is the whitening matched filtering (WMF)
dMMSE = (HHE~'H+I) 1y is the linear MMSE equalization
Equation 58
[00108] Neither HHE;,' nor HH~n'H +I are Toeplitz and neither can be
made Toeplitz through elemental unitary operations (e.g. row/column re-
arrangements), due to the structure of E" . Accordingly, DFT-based methods
based on circulant approximations of Toeplitz matrices cannot be applied here
and an exact solution is highly complex.
-23-
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
[00109] Two embodiments for deriving an efficient algorithm for solving
this problem are described. The first embodiment uses a simple approximation
and the second embodiment uses an almost-exact solution.
[00110] Simple Approximation
[00111] The simple approximation ignores the correlation between ne
and no, E~ross = 0 . As a result, the same approach as multiple chip -rate
receive
antennas is used.
[00112] The complexity of this simple approximation approach is as
follows. N-chip data blocks are considered. For rough approximation, an N
point
DFT complexity, given by NlogN operations per second (ops), is assumed.
Additionally, N point vector multiplications are assumed to take N ops and
vector additions are ignored.
[00113] The complexity of the DFT-based approach can be roughly
partitioned into 2 components: the processing which has to be performed on
every
received data set and the processing which is performed when the channel
estimate is updated, which is typically done one to two orders of magnitude
less
frequently then the former operation.
[00114] For processing performed on each received data set, the following
operations are performed: 2 N point DFTs to transform the received vector into
the frequency domain; 2 N point vector multiplications (multiply each received
vector by the appropriate "state" vector"); and one more DFT to transform the
result back into time domain. Thus, the approximate complexity is per Equation
59.
G,,, = 3N log N + 2N
Equation 59
-24-
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
[00115] For processing performed when the channel response is updated,
the following operations are performed: 2 DFT operations, 6 N point vector
multiplies and a vector division, which need to be taken 10 times the
operations
of a vector multiply. Thus, the complexity of this step is roughly given per
Equation 60.
C1,, = ZN log N + 16N
Equation 60
[00116] Almost Exact Solution
[00117] For the almost-exact solution which uses a block-Toeplitz
solution, the vector and matrices are rearranged in their natural order, such
that
the vector r is given by r=[ro,rl,...,~'2N-1]T ~ Equation 61 is the natural
order
model.
r = HbTd+n
he,t G1
where HvT is defined as Hb~. = h°'' Gz
h°,N GN
Equation 61
he,i is the ith row of He and ho,i is the ith row of Ho. G; is a 2xN matrix
whose 1St
row is he,i and whose 2nd row is ho,i. Using Gi [x,y] as the row-x, column y
element
of Gi, HaT is block-Toeplitz as illustrated in Equation 62.
G i Lxa ,Y] - r-T j ~p .y + ~t
provided that 1 _<< y + (i - j) << N
Equation 62
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
[00118] The block-Toeplitz structure of HaT follows immediately from the
Toeplitz structure of He and Ho and the row-rearrangement. From the Toeplitz
structure of I and across a the autocorrelation matrix of the noise in the re-
defined
problem is also block Toeplitz. Because this matrix is also symmetric, it can
be
rewritten per Equation 63.
~bT [~'i,j ] l5i,j5N
where Ei, j are 2x2 matrices with the property that Ei, j = ~~~_;~
Equation 63
[00119] Subsequently, block-circulant approximations to the ~ block-
Toeplitz matrices are produced. Since the HbT matrix is also banded, the block
circulant approximation of HbT is then obtained directly. However, EbT is not
banded and therefore it is not possible to produce a block-circulant
approximation
directly from it. Since the elements of AbT tend to 0 as they get farther away
from the main diagonal, a banded approximation to EbT is per Equation 64.
~'bT ~ ~bT - [~'i,j, l5i,j5N
where ~i,~ are 2x2 matrices with the property that
~~, j = ~~;_ j~ if ~ i - j ~<- Bn and Ei, j = 0 otherwise
Equation 64
The noise-covariance-bandwidth, Bn, is a design parameters that is selected.
Due
to the decay properties of the RC pulse shape, it is likely to be only several
chip.
Now ~6T is banded block-Toeplitz and a circulant approximation to it is
produced.
[00120] The circulant approximations of HaT and ~bT are Hbc and Ebc,
respectively. Wn denotes the n-point DFT matrix, that is if x is an n-vector,
then
-26-
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
x~=Wnx is the DFT of x. A block-circulant matrix C is of the form of Equation
65.
C1 CZ ... CM
C CZ C
CM C'1 ... CM_1
where C; is an NxN matrix and therefore C is an MNxMN matrix
Equation 65
[00121] C can also be written as Equation 66.
C - wMxN AMxN (C) WMxN
where WMxN 1S the block-N-DFT matrix defined as WMxN = ~'fM ~ IN
Equation 66
AMxN (C) is a block diagonal matrix that depends on C and is given by Equation
67.
A,(C)
AMxN (~) = A2 C
A M (C)
Equation 67
A; (C) is an NxN matrix. To completely specify Al (C) , ~,,,(k,l) denotes the
(h, Z)th
def
element of A; (C) and is defined as ~(k~l) -[~,(k,l)~a'2,(k,l)~'wa'M,(k,l).1T
' Ci,(k,l) denotes
def
the (h,l)th element of C and is defined aS C(k 1) =[Cl,(k,l)~ C2,(k,l) ~"'
~CM,(k,l). .1T' a'(k,l) 1S the
M-point DFT of c(k,l) and is per Equation 68.
~"(k,l) - wMC(k,l)
Equation 68
_~7_
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
[00122] Equations 66-68 specify the block-DFT representation of square
block circulant matrices. N2 DFTs are required to compute AM~N (C) .
[00123] The MMSE estimator is rewritten per Equation 69.
dMMSE -HH~n +HHH) 1r
Equation 69
[00124] The MMSE estimator form as per Equation 68 has several
advantages. It requires only a single inverse matrix computation and thus in
the
DFT domain only a single vector division. This provides a potentially
significant
savings as divisions are highly complex.
[00125] The almost-exact solution has two steps in the most preferred
embodiment, although other approaches may be used. Every time a new channel
estimate is obtained, the channel filter is updated, ( HH (E" + HHH )-1 is
determined). For every data block, this filter is applied to the received data
block. This partition is utilized because the channel is updated very
infrequently
compared to the received data block processing and therefore significant
complexity reduction can achieved by separating the overall process into these
two steps.
[00126] The DFT of ~o is the DFT of the pulse shaping filter multiplied
by the noise variance ~z . Since the pulse shaping filter is typically a fixed
feature of the system, its DFT can be precomputed and stored in memory and
thus only the value ~Z is updated. Since the pulse-shaping filter is likely to
be
close to the "ideal" (IIR) pulse shape, the DFT of the ideal pulse shape can
be
used for ~" , reducing the complexity and is also far away from the carrier.
[00127] To channel update step, the following is performed:
-28-
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
1. The "block-DFT" of H needs to be computed. Since the block is of
width 2, it requires 2 DFTs. The result is a Nx2 matrix whose rows are
the DFTs of he and ho.
2. The "block-DFT" of HHH is computed by finding element-by-element
autocorrelations and the crosscorrelation of he and ho. This required 6N
complex multiplies and 2N complex adds: the products of N 2x2 matrices
are computed with there own Hermitian transposes.
3. The block-DFT of E" is added, which requires 3N multiplies (scale
the stored block-DFT of the RRC filter by ~z ) and 3N adds to add the
block-DFT of the two matrices.
4. An inverse of ~o + HHH is taken in the block-DFT domain. To do
this an inverse of each of the N 2x2 matrices is taken in the block-DFT
domain. To estimate the total number of operations, consider a Hermitian
matrix M = b* a . The inverse of this matrix is given per Equation 70.
M_~ _ 1 a _b
_ az_ ~ b ~z _b* a
Equation 70
Accordingly, the complexity of computing each inverse involves 3 real
multiplications and 1 real subtraction (roughly 1 complex multiply) and 1
real division.
5. The result are block-multiplied by the block-DFT of HH, which,
takes a total of 8N multiplies + 4N adds (since HH is not Hermitian).
[00128] To summarize, the following computation are required: 2 N-point
DFTs; 18N complex multiplies (17 N-point vector multiplies + N stand-alone
multiplies); 11N complex adds (11 N-point vector adds); and 1N real divisions.
[00129] The complexity of processing a data block r of 2N values (N chips
long) involves: 2 N-point DFTs; one product of the N-point block-DFTs (filter
and
-29-
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
data), which required 8N complex multiplies and 4N complex adds; and 1 N-point
inverse DFTs.
[00130] To summarize, the following is required: 3 N-point DFTs; 8N
complex multiplies (8 N-point vector multiplies); and 4N complex adds (4 N-
point
vector adds).
[00131] Multiple Chip Rate Sampling and Multiple Receive Antenna
Equalization
[00132] The following are embodiments using multiple .chip rate sampling
and multiple receive antennas. For L receive antennas, 2L channel matrices -
one "even" and one "odd" matrix for each antenna result. The channel matrices
for lth antenna are denoted as Hi,e and Hi,o and hl,e>n and hi,o,n denote the
nth row of
such matrix. Each channel matrix is Toeplitz and with the appropriate re-
arrangement of rows the joint channel matrix is a block-Toeplitz matrix, per
Equation 71.
h~,e,~ G~
hi,o,i Ga
H 6T
hL,o,N GN
Equation 71
The matrices Gi are the Toeplitz blocks of HbT. Each Gi is a 2LxN matrix.
[00133] Estimating the vector d from the received observations r can be
modeled per Equation 72.
r = HbTd+n
Equation 72
[00134] The MMSE estimation formulation is per Equation 73.
dMMSE - ~bTH~n +HbT~bTH~ 1r
Equation 73
E" is the covariance of the noise vector n. The form that the solution of
Equation
73 depends on the assumptions that are made for E" . The introduction of the
-30-
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
multiple receive antenna introduces an additional spatial dimension. Although
the interplay of temporal and spatial correlations can be extremely complex,
it
can be assumed that the spatial correlation properties of the noise do not
interplay with the temporal correlation properties, except as a direct product
of
the two, as per Equation 74.
~n - ~'n,lant ~ ~sp
Equation 74
~n,lant is the noise covariance matrix of the noise observed at a single
antenna as
per Equation 57. ~n~lant is of dimension 21Vx2N. ~Sp is the normalized
synchronous spatial covariance matrix, i.e. it is the covariance matrix
between
the L noise samples observed at the L antennas at the same time normalized to
have 1's on the main diagonal ~ denotes the I~roenecker product.
[00135] ~n is a 2LNx2LNHermitian positive semi-definite matrix, which
is block-Toeplitz with 2Lx2L blocks. To estimate the data, four preferred
embodiments are described: an exact solution; a simplification by assuming
that
the L receive antenna have uncorrelated noise; a simplification by ignoring
the
temporal correlation of the noise in the odd and even streams from the same
antenna; and a simplification by assuming that all 2L chip-rate noise streams
are
uncorrelated.
[00136] The complexity of DFT-based processing using the circulant
approximation may be partitioned into two components: the processing of
channel estimation which need not be done for every new data block and the
processing of data itself which is performed for every data block. In all four
embodiments, the complexity of processing data involves: 2L forward N point
DFTs; 2LN complex multiplies; and 1 inverse N point DFT. The complexity of
processing the channel estimate varies for each embodiment.
[00137] In the case of the exact MMSE solution, the complexity of computing
the "MMSE filter" from the channel estimate is as follows: 2L N-point DFT's ;
N
2Lx2L matrix products + N 2Lx2L matrix additions to compute (E" + HbTHbTH
-31-
CA 02530518 2005-12-21
WO 2005/004338 PCT/US2004/020427
N 2Lx2L matrix inverses to compute the inverse of (En + HbTHbTH ) ; andN2Lx2L
matrix products to produce the actual filter.
[00138] A major contributor to the overall complexity of this process is
the matrix inverse step in which an inverse of 2Lx2L matrices has to be taken.
It
is precisely this complexity that can be reduced by various assumptions on the
uncorrelated nature of the noise, as follows:
1. If it is assumed that the noise is uncorrelated both temporally
(oddleven samples) and spatially (across antennas), then En reduces to a
diagonal matrix and the problem is identical to single-sample-per-chip
sampling with 2L antennas with spatially uncorrelated noise. As a result,
the operation of matrix inverse simply reduces to a division since all the
matrices involved are Toeplitz.
2. If it is assumed that the noise is spatially uncorrelated, then the
matrix inverses involved are those of 2x2 matrices.
3. If it is assumed that a temporal uncorrelation of odd/even streams
but a spatial noise correlation is retained, the matrix inverses involved are
LxL.
-32-
