Note: Descriptions are shown in the official language in which they were submitted.
WO 95J3331~ 218 9121 P~~S95106801
-1-
DIVERSITY RECEIVER FOR SIGNALS WITH MULTIPATH
TIME DISPERSION
FIELD OF THE DISCLOSURE
The present invention relates to diversity combining and equalization in a
receiver for digital wireless communications.
BACKGROUND OF THE DISCLOSURE
In recent years, digital wireless communication systems have been used to
convey a variety of information between multiple locations. With digital
communications, information is translated into a digital or binary form,
referred to
as bits, for communications purposes. The transmitter maps this bit stream
into a
modulated symbol stream, which is detected at the digital receiver and mapped
back
into bits and information.
In digital wireless communications, the radio environment presents many
difficulties that impede successful communications. One difficulty is that the
signal
level can fade, because the signal may travel in multiple paths. As a result,
signal
images arrive at the receiver antenna out of phase. This type of fading is
commonly referred to as Rayleigh fading or fast fading. When the signal fades,
the
signal-to-noise ratio becomes lower, causing a degradation in the
communication
link quality.
A second problem occurs when the multiple signal paths are much different
in length. In this case, time dispersion occurs, in which multiple fading
signal
images arrive at the receiver antenna at different times, giving rise to
signal echoes.
This causes intersymbol interference (ISI), where the echoes of one symbol
interfere
with subsequent symbols.
Raleigh fading can be mitigated by using diversity, such as antenna diversity,
at the receiver. The signal is received on a plurality of antennas. Because
the
antennas have slightly different locations and/or antenna patterns, the fading
levels
on the antennas are different. In the receiver, these multiple antenna signals
are
WO 95/33314 218 9121 p~~S95106801
-2-
combined either before or after signal detection using such techniques as
maximal- .
ratio-combining, equal-gain-combining, and selective combining. These
techniques
are well known to those skilled in the art and can be found in standard '
textbooks,such as W.C.Y. Lee, Mobile Communications Engineering, New York:
McGraw-Hill, 1982.
The time dispersion can be mitigated by using an equalizer. Common forms
of equalization are provided by linear equalizers, decision-feedback
equalizers, and
maximum-likelihood sequence-estimation (MLSE) equalizers. A linear equalizer
tries to undo the effects of the channel by filtering the received signal. A
decision-
feedback equalizer exploits previous symbol defections to cancel out the
intersymbol
interference from echoes of these previous symbols. Finally, an MLSE equalizer
hypothesizes various transmitted symbol sequences and, with a model of the
dispersive channel, determines which hypothesis best fits the received data.
These
equalization techniques are well known to those skilled in the art, and can be
found
I5 in standard textbooks such as ).G. Prvakis, Digital Communications, 2nd
ed., New
York: McGraw-Hili, 1989.
Of the three common equalization techniques, MLSE equalization is
preferable from a performance point of view. In the MLSE equalizer, all
possible
transmitted symbol sequences are considered. For each hypothetical sequence,
the
received signal samples are predicted using a model of the multipath channel.
The
difference between the predicted received signal samples and the actual
received
signal samples, referred to as the prediction error, gives an indication of
how good
a particular hypothesis is. The squared magnitude of the prediction error is
used as
a metric to evaluate a particular hypothesis. This metric is accumulated for
different hypotheses for use in determining which hypotheses are better. This
process is efficiently realized using the Viterbi algorithm, which is a form
of
dynamic programming. .
Ideally, the diversity combining process and the equalization process should
be combined in some optimal way. Recent research has shown that for MLSE
equalization, diversity combining should be done within the equalizer. This
CA 02189121 2004-10-12
-3-
research can be found in W.H. Sheen and G.L. Stuber, "MLSE equalization and
decoding for multipath-fading channels," IEEE Trams. Commun., vol. 39, pp.
1455-
1464, Oct. 1991; Q. Liu and Y. Wan "An adaptive maximum-likelihood sequence
estimation receiver with dual diversity combining/selection," Irul. Symp. on
Personal, Indoor and Mobile Radio Commun., Boston, MA, pp. 245-249, Oct. 19
21, 1992; and Q. Liu and Y. Wan, "A unified MLSE detection technique for
TDMA digital cellular radio," 43rd IEEE Vehicular Technology Conference,
Seacaucus, NJ, pp. 265-268, May 18-20, 1993. In the above mentioned research,
diversity combining is performed by adding together the magnitude squared
prediction errors from different diversity channels when forming metrics.
Further improvement is obtained by scaling the squared prediction errors
from the different diversity branches. A detailed description of such an MLSE
equalizer is given in U.S. Patent No. 5,191,598 to T.O Backstrom et al.
Unfortunately, the MLSE equalizer involves computing many squared prediction
error
terms. This can be costly in terms of hardware or software complexity. Thus,
there is a
need to reduce the complexity of the MLSE equalizer/diversity combiner.
For the MLSE equalizer without diversity combining, the Ungerboeck
method applies two steps to reduce complexity, as described in G. Ungerboeck,
"Adaptive maximum likelihood receiver for carrier modulated data transmission
systems," IEEE Trans. Commun., vol. COM-22, no. 4, pp. 624-535, May 1974.
The first step is to expand the magnitude square term and to eliminate terms
that are
common to all hypotheses. As a simple example, the term (a-b)z can be expanded
into az - tab + b2. If "a" does not depend on the hypothesized data, then the
a2
term can be dropped from the metric computation.
The second step used by Ungerboeck is to re-arrange the order of the metric
computations. With standard MLSE equalization, metrics are computed and
updated based on successively received data samples. Each iteration of the
Viterbi
algorithm corresponds to a new received data sample. Using the second step,
each
iteration of the Viterbi algorithm corresponds to a newly transmitted symbol.
._ WO 95/33314 218 912 ~ PCT~S95~0~01
-4-
These two steps can be further explained by a simple example. Suppose the
transmitter transmits a symbol stream s(n), in which each s(n) can take on one
of S
possible complex values. At the receiver, the received signal is sampled once
every
T seconds, where T is the symbol period, to give a received signal stream
r(n).
Suppose the intervening channel consists of two fading rays, a main ray and an
echo, where the echo arrives T seconds later. Then, the received signal can be
modeled as:
r(n) = c(0) s(n) + c(I) s(n-1) + n(n)
where c(0) and c(1) are complex channel tap values and n(n) is additive noise
of
some kind.
In the MLSE equalizer, at iteration n, there would be S different previous
"states", corresponding to the S possible values for s(n-1). Associated with
each
previous state would be an accumulated metric, accumulated from previous
iterations. There would also be S current states, corresponding to the S
possible
values for s(n). Each possible pairing of a previous state with a current
state
corresponding to a hypothetical sequence {sti(n), s~(n-1)}. For each
hypothesis, the
predicted received signal value would be:
rP,z,,(n,h) = c(0) sb(n) + c(1) sh(n-1).
The corresponding branch or delta metric would be given by
Mb(n) _ ~ r(n) - rp"~(n,h) ~ Z
The candidate metric for a current state would be the sum of the branch metric
and
the previously accumulated metric associated with sh(n-1). For each current
state,
there are S possible previous states. For each current state, the previous
state
._ WO 95/33314 218 91 ~ 1 p~~s~~~l
-5-
which gives the smallest candidate metric is selected as the predecessor
state, and
the candidate metric becomes the accumulated metric for that current state.
At the next iteration, using r(n+1), the current states from time n become
the previous states at time n+ 1. After all the data have been received, the
state
with the smallest accumulated metric, and all the predecessors, indicate the
most
likely transmitted symbol sequence, which becomes the detected symbol
sequence.
Sometimes decisions are made before all the data are received using a decision
depth.
The first Ungerboeck step can be illustrated by expanding the expression for
Me(n). This gives
Me(n) = A(n) + B{n) + C{n) + D(n)
where
A(n) _ ( r(n) ~ 2
B(n) = 2 Re{ r(n) c*(0) sti*(n)} + 2 Re{ r(n) c*(1) sh* (n-1)}
C(n) _ ~ c(0) ( Z ~ %(n) ~ Z ~' ~ c(1) ~ Z ( ~(n-1) ~Z
D(n) = 2 Re{ c(0) c*(1) sti(n) sh*(n-1))}
where "*" denotes complex conjugation. The Ungerboeck method drops the term
A(n), which is common to all M~(n).
The second Ungerboeck step combines terms proportional to sti*(n) from
different iterations. At iteration n+ l, the terms become:
B(n+ I) = 2 Re{ r(n+ 1) c*(0) sh*(n+1)} + 2 Re{ r(n+ 1) c*(1) sh*(n)}
. C(n+i) _ ~c(0)(z ~sb{n+1)~2 + ~c(1)~2 ~sh(n)~Z
D(n+I) = 2 Re{ c(0) c*(1) sb(n+i) sti*(n)}
WO 95133314 . PCT/IJS95106801
2189121
-6-
Thus, there are terms proportional to s~*(n) in both iterations. These can be
recombined by defining a new metric, M'6(n), as
M'b(n) = B'(n) + C'(n) + D(n)
where
B'(n) = 2 Re{ f(n) sb*(n)}
f(n) = r(n) c*(0) + r(n+1) c*(1)
c'(n)=tl~(o)l2+ I~(1)I~ Is~(n)IZ
As a result, B'(n) contains f(n), which can be realized by filtering the
received data
r(n) with a filter using taps c*(0) and c*(1).
Thus, the new metric uses two data samples, r(n) and r(n+1), instead of just
one, r(n). Also, unlike B(n) and C(n), B'(n) and C'(n) depend only on one
hypothesized symbol, sb(n), instead of two, se(n) and sh(n-1). Thus,
conceptually,
iteration n corresponds to the transmitted symbol sb(n) rather than the
received data
value r(n).
When MLSE equalization and diversity combining are performed together,
the Ungerboeck form can be used to reduce the complexity. The situation where
c(0) and c(1) do not change with time, referred to as the static channel case,
was
described in U.S. Patent No. 5,031,193 to Atkinson et al. In the Atkinson et
al.
patent, both Ungerboeck steps are used to obtain the demodulator shown in
Figures
1 and 2 of U.S. Patent No. 5,031,193. In Figure 2 of the Atkinson et al.
patent,
the term f(n) is realized with a matched filter on the diversity branch 1, and
a
matched filter on the diversity branch 2.
However, there are disadvantages with using the Ungerboeck form. One is
the problem that the channel tap values, c(0) and c(1) in the above example,
may
change with sample time n. In the conventional form, all of the c(0) and c(1)
terms
can be replaced with c(O,n) and c(l,n). As a result, the Ungerboeck form
contains
WO 95133314 PGT/US95106801
2189121
_7_
a mixture of channel taps from time n and from time n+1. This would require
storage capability for multiple sets of channel taps and may make channel
tracking
more difficult. Channel tracking and prediction are well understood and
examples
can be found in A.P. Clark and S. Hariharan, "Adaptive channel estimator for
an
HF radio link. " IEEE Traps. Convnun. , vol. 37, pp. 918-926, Sept. 1989.
in U.S. Patent No. 5,031,193, an alternative solution is given to address the
case of time-varying channel taps. However, this solution does not use the
Ungerboeck form, and it does not combine equalization and diversity combining
in
an optimal manner. Instead, each diversity branch has a separate equalizer.
Channel tracking is performed using branch detections, not detections which
have
benefitted from diversity combining. The outputs of these equalizers are then
combined using standard diversity combining techniques. So, the equalization
and
diversity combining steps have been performed separately, not jointly.
Thus, there is a need for a receiver that jointly performs MLSE equalization
and diversity combining and that lends itself to the case where the channel
varies as
a function of time.
SiJIVIIVtARY OF THE DISCLOSURE
An object of the present invention is to provide an efficient form of joint
MLSE equalization and diversity combining for use in a wireless digital
communications receiver. This is achieved by expanding the metric expressions
and
collecting terms that correspond to the same hypothesized transmitted symbol.
Embodiments of the present invention will be given for both the static and
time-
varying channel cases.
One embodiment of the present invention discloses a digital communications
receiver comprising means for signal processing a plurality of diversity
branches to
produce complex receive data samples and synchronization information. Channel
estimate means then form channel estimates from the data samples and
synchronization information. The data samples and the channel estimates are
then
used by pre-processing means to produce metric multipliers. Finally, combining
CA 02189121 2005-O1-14
8
means combine the metric multipliers with hypothesized data sequences to
generate
and accumulate metrics using a sequence estimation algorithm to produce a
demodulated data stream.
According to another embodiment of the present invention, a digital
communication receiver is disclosed which comprises means for signal
processing a
plurality of diversity branches to produce complex receive data samples and
synchronization information. Channel estimate means then form channel
estimates
using synchronization information and initial data detection to produce time-
varying
channel estimates. The data samples and the channel estimates are then used by
=pre-processing means to produce metric multipliers. Finally, combining means
combine the metric multipliers with hypothesized data sequences to generate
anrf
accumulate metrics using a sequence estimation algorithm to produce a
demodulated
data stream.
According to an aspect of the present invention there is provided a digital
communications receiver, comprising means for signal processing a plurality of
diversity
branches to produce complex receive data samples and synchronization
information from
received signals, means for forming channel tap estimates from the data
samples and the
synchronization information, means for forming weighting factors using the
data
samples, the channel tap estimates, and the synchronization information, means
for pre-
2 0 processing the data samples, the channel tap estimates, and the weighting
factors to
produce metric multipliers, and means for combining the metric multipliers
with
hypothesized data sequences to generate and accumulate metrics using a
sequence
estimation algorithm, producing a demodulated data stream. Preferably a
digital
communications receiver comprising means for signal processing a plurality of
diversity
2 5 branches to produce complex receive data samples and synchronization
information from
received signals, means for forming time-varying channel tap estimates from
the data
samples, the synchronization information, and tentative data detections
produced by a
combining means, means for forming time-varying weighting factors using the
data
samples, the channel tap estimates, the synchronization information, and the
tentative
3 0 data detections, means for pre-processing the data samples, the channel
tap estimates, and
the weighting factors to produce metric multipliers, and the combining means
for
combining the metric multipliers with hypothesized data sequences to generate
and
CA 02189121 2004-10-12
8a
accumulate metrics using a sequence estimation algorithm, producing a
demodulated data
stream.
According to another aspect of the present invention there is provided a
digital
communications receiver comprising means for signal processing a plurality of
diversity
' 5 branches to produce complex receive data samples and synchronization
information from
received signals, means for forming time-varying channel tap estimates from
the data
samples, the synchronization information, and tentative data detections
produced by a
combining means, means for forming time-varying weighting factors using the
data
samples, the channel tap estimates, the synchronization information, and the
tentative
data detections, means for pre-processing the data samples, the channel tap
estimates, and
the weighting factors to produce metric multipliers, and the combining means
for
combining the metric multipliers with hypothesized data sequences to generate
and
accumulate metrics using a sequence estimation algorithm, producing a
demodulated data
stream. Preferably a method for joint equalization and diversity combining in
a digital
communications receiver, comprising the steps of signal processing a plurality
of
diversity branches to produce complex receive data samples and synchronization
information from received signals, forming channel tap estimates from the data
samples
and the synchronization information, forming weighting factors using the data
samples,
the channel tap estimates, and the synchronization information, pre-processing
the data
2 0 samples, the channel tap estimates, and the weighting factors to produce
metric
multipliers, and combining the metric multipliers with hypothesized data
sequences to
generate and accumulate metrics using a sequence estimation algorithm,
producing a
demodulated data stream.
According to a further aspect of the present invention there is provided a
method
2 5 for joint equalization and diversity combining in a digital communications
receiver,
comprising the steps of signal processing a plurality of diversity branches to
produce
complex receive data samples and synchronization information from received
signals,
forming channel tap estimates from the data samples and the synchronization
information, forming weighting factors using the data samples, the channel tap
estimates,
3 0 and the synchronization information, pre-processing the data samples, the
channel tap
estimates, and the weighting factors to produce metric multipliers, and
combining the
metric multipliers with hypothesized data sequences to generate and accumulate
metrics
using a sequence estimation algorithm, producing a demodulated data stream.
CA 02189121 2004-10-12
8b
According to a further aspect of the present invention there is provided a
method
for joint equalization and diversity combining in a digital communications
receiver,
comprising the steps of signal processing a plurality of diversity branches to
produce
complex receive data samples and synchronization information from received
signals,
forming time-varying channel tap estimates from the data samples, the
synchronization
information, and tentative data detections produced by a processor, forming
time-varying
weighting factors using the data samples, the channel tap estimates, the
synchronization
information and the tentative data detections, pre-processing the data
samples, the
channel tap estimates, and the weighting factors to produce metric
multipliers, and
combining the metric multipliers with hypothesized data sequences to generate
and
accumulate metrics using a sequence estimation algorithm, producing a
demodulated data
stream.
According to a further aspect of the present invention there is provided in an
IS54-based Time Division Multiple Access digital communications system, a
receiver
comprising means for signal processing a plurality of diversity branches to
produce
complex receive data samples and synchronization information from received
signals,
means for forming time-varying channel tap estimates from the data samples,
the
synchronization information, and tentative data detections produced by a
combining
means, means for forming time-varying weighting factors using the data
samples, the
2 0 channel tap estimates, the synchronization information, and the tentative
data detections,
means for pre-processing the data samples, the channel tap estimates, and the
weighting
factors to produce metric multipliers, and the combining means for combining
the metric
multipliers with hypothesized data sequences to generate and accumulate
metrics using a
sequence estimation algorithm, producing a demodulated data stream.
2 5 According to a further aspect of the present invention there is provided
in an
IS54-based Time Division Multiple Access digital communications system, a
method for
joint equalization and diversity combining in a digital communications
receiver,
comprising the steps of signal processing a plurality of diversity branches to
produce
complex receive data samples and synchronization information from received
signals,
3 0 forming time-varying channel tap estimates from the data samples, the
synchronization
information, and tentative data detections produced by a processor, forming
time-varying
weighting factors using the data samples, the channel tap estimates, the
synchronization
information, and the tentative data detections, pre-processing the data
samples, the
CA 02189121 2004-10-12
8c
channel tap estimates, and the weighting factors to produce metric
multipliers, and
combining the metric multipliers with hypothesized data sequences to generate
and
accumulate metrics using a sequence estimation algorithm; producing a
demodulated data
stream.
BRIEF DESCRIPTION OF THE DRAWINGS
These and other features and advantages of the invention will be readily
apparent to one of ordinary sitill in the art from the following written
description,
used in conjunction with the drawings, in which:
Figure 1 illustrates a digital communication receiver according to one
embodiment of the present invention;
Figure 2 illustrates a branch signal processor according to one embodiment
of the present invention;
Figure 3 illustrates a metric pre-processor according to one embodiment of
the present invention;
Figure 4 illustrates a digital communication receiver according to one
embodiment of the present invention;
Figure 5 illustrates a branch signal processor according to one embodiment
of the present invention; and
Figure 6 illustrates a metric pre-processor according to one embodiment of
~e present invention.
WO 95!33314 218 9 ) 21 P~~S95106801
-9-
DETAILED DESCRIPTION OF THE DISCLOSURE
In the present invention, MLSE equalization and diversity combining are
preformed jointly in a diversity equalizer. In this embodiment, the term s(nT)
is a
sequence of transmitted symbols, where the symbol period is T seconds. Pulse
shaping is used to generate a continuous time signal, t(t). In addition, the
term rd(t)
is the baseband, complex received signal from diversity branch d. After
synchronization, sampled received values are processed, where there are M
samples
per symbol period T. This allows for both symbol-based equalization (M = 1)
and
fractionally-spaced equalization (M > 1).
Thus, in the time period (nT,(n+1)T), samples rd(nT),
rd((n+ 1JM)T) ... ra((n+(M-1)JM)T) are received on each diversity branch, one
sample for each sampling phase. The following channel models are used for
these
received signals:
rd((n+mJM)T) = c~m(O,n) s(nT) + c~m(l,n) s((n-1)T) + ...
+ c~,m(J-l,n) s((n-J+1)T) for m = 0,1, ... M-1
where J is the number of channel taps in each model and cd,~(j,n) is the j'th
channel
tap for diversity branch d, sampling phase m, at time interval n.
The following delta metric is used in the Viterbi algorithm at iteration n:
D-I AI-1
Mn(n) ~ ~ ~ rd((n+'I1J~~ 1'd~~((IT+nIJ~Ty) ~ 2
d=0 m=0
where
r-I
rd.vr~((n+mJ~T~h) - ~ Cd.mV n)ShVJ
!'a
and sti(j) denotes a hypothesized symbol s(jT). This metric requires a
significant
amount of computation
In some applications, it may be advantageous to employ a weighted sum
when forming the metrics. This leads to the new form
WO 95/33314 218 9121 pCT~S9510680I
-10-
D-l M-1
Mh(n) _ ~ ~'~'d.~(n)~ ''d((n+'n1~1~ - T~r~((n+ml~T,h) ~ 2
a.o m-o
where w~m(n) are noncomplex weighting factors.
For optimal-combining, these weights would be estimates of the reciprocals
of the noise powers on Iink d at sampling phase m, i.e., w~,m(n) = 1/Nd,,m(n).
The
noise powers can be kept constant over all or some iterations, or they can
vary with
each iteration n. The noise powers could be obtained from initial channel tap
estimates and the synchronization data, since noise samples can be obtained by
taking the difference between the received signal samples and the predicted
signal
samples, based on the known synchronization sequence. These noise samples can
be magnitude squared and averaged tv get an estimate of Nd,m(n). It may be
desirable to combine the estimates from different sampling phases, m, to
obtain
weights wa = I/Nd, which are independent of time and sampling phase. If the
channel is time-varying, then signals internal to each channel tracker can be
used to
estimate the time-varying noise power. Alternatively, this may be done using
detected symbols, the channel tap estimates, and the received data. The
results
from multiple sampling phases may be combined, thus giving wd(n) = 1/Nd(n).
For semi-optimal-combining, these weights would all be unity and could be
ignored in the implementation. For selection combining, these weights would
all be
zero, except for the diversity channels(s) and sampling phases) selected.
Selection
could be based on a number of criteria, such as an estimate of the signal-to-
noise
ratio on each branch, and possibly the sampling phase, as well as an estimate
of the
signal or received power on each branch, and possibly the sampling phase.
Other
possibilities for these weights exist. These would in some way be related to
diversity branch quality.
To reduce the complexity, the first Ungerboeck step is applied to each
diversity branch and to each sampling phase. Terms common to ali hypotheses
are '
eliminated. This gives
Mti(n) = B,,(n) + Cb(n) + Dh(n)
WO 95133314 218 9 ~ ~ ~ ~~595/06801
-11-
where
D-i A(-1 I-i
Bh(n) _ -2~ ~ ~'~'a.m(n)~ Re{rd((n+~~~ cd,m(1'n) s h (n-17~
e.o m.o j-o
D-( Al-I J-I
Ch(n) ~ ~ wd.min)Lr ~ CdmV n) [ 2 ~ Sh~n J~ ~ 2
d=0 m=0 j=0
D-1 Af-1 J-1 K-t
D,,(n) = 2~ ~ wd~(n)~ ~ Re{ca,~(j,n) c,~",(k,n)sh (n ~~ s,,(n-k)~
d=0 m=0 j=0 k=0
k~j
At this point, the second Ungerboeck step, collecting terms from different
iterations, is not performed. _ Instead, according to the present invention,
the order
of summation is changed within the same iteration. This leads to the novel
form:
J-1 D-I M-I
B',,(n) _ -2~ Re ~ ~ wd~,(n)rd((n+mlll~~ cd,m~'n) s h (n ~)
j=o a=o m=o
J-1 D-I M-i
C,h(n) ~ ~ ~ wd.m~n)~d.m~~n)l Z ~Sh(n ~~~ 2
j=0 d=0 m=0
I-1 J-1 D-1 M-1
D~h(n) ' 2~ ~ Re ~ ~ wd.m(n) cd.m(l,n) cd,,"(k~n) sh (n-17 s,,(n-k)
j=0 k=U d=0 m=0
k>j
The terms in the brackets 0 do not depend on the hypothesized data. Thus,
these
terms can be computed in a metric pre-processor and used multiple times when
computing the metrics in a metric processor.
WO 95133314 ~ ~ ~ PCTlUS95106801
-12-
In the term in the brackets 0 in B'h(n), the inner summation over m gives ,
rise to an M-tap FIR filter on the received data in diversity branch d. Since
this
summation is different for each value of j, i.e., different rays or channel
taps, this
implies a bank of FIR filters on each branch, one for each value of j. The
filter
data and coefficients would both be complex. For the case of T-spaced
equalization, when M =1, each FIR filter would simply be a 1-tap filter, which
is
equivalent to a multiplier.
The output of each FIR filter does not have to be computed for every shift of
the input data. In general, only one output is needed for every M shifts of
the input
data. This output corresponds to the case when the FIR data contents are the M
values r(nT) through r((n+(M-1)/M)T). Thus, this can be equivalently realized
by
a register which, at time n, is loaded with these data values. Then, channel
tap
estimates for time n are used to multiply the register contents, the products
being
accumulated in an accumulator.
The outer summation over d implies combining the outputs of the FIR filter
banks to one bank of combined outputs, each element corresponding to a
different
channel tap j. Also, for terms C'b(n) and D'b(n), the terms in the brackets p
only
depend on the channel taps. If the channel taps do not change, or are only
updated
every so many iterations, then these terms in the brackets ~ can be reused in
multiple iterations.
These implementation considerations lead to the following form of the
present invention. The delta metric is computed as
~h{n) = g~h(n) .~ C~h(n) + D~h{n)
where
l-1
B'h{n) _ -2~ Re{e(j,n) s h (n ~)}
j=0
and
wo 95133314 2 ~ 8 9121 PCTJUS95/06801
-13-
r-1
~h(n) _ ~~~n) ~h(n ~~i z
j.p
r-i !-1
D',,(n) = 2~ ~ Re~g(j,k,n) sh (n ~) s~,(n-k)?
j~0 k.p
k>j
D-i A/-1
e~~n) _ ~ ~ rd((n+~~~ cd,m (I°n) ~''d.~(n)
d-o ~.o
D-1 Al-i
.W n) - ~ ~ wd.m(n) ~d.m~,n)I 2
d=0 m.p
D-1 M-1
&(1 ~k~n) _ ~ ~ H'd"",(n) ca.m(l ~n) cd.m (k~n) k ~>.7
d~ m~
The terms e(j,n), f(j,n) and g(j,k,n) can be pre-computed in a metric
preprocessor.
These are referred to as metric multipliers, since they are used in
multiplications to
form the equalizer metrics. Then, the metric processor would implement the
Viterbi algorithm, taking advantage of the pre-computed quantities.
It should be noted that one may employ further techniques to trade-off
memory and processing requirements when computing the metric multipliers. For
example, one can define xd.~(n) as the square root of wd.m(n). Then, one could
replace the ca.~,(j,n) terms with cd.m(j,n) = xd.m(n) cd.m(j,n) and replace
rd((n+m!M)T) with id((n+mlM)T) = xd.m(n) rd((n+m/M)T). Alternatively, one
could define c'a.m(j,n) = wa.~(n) cd.m(j,n) and use a mixture of primed and
unprimed
channel models. Also, the factors of 2 may be dropped from B'e(n) and D'6(n),
and
a factor of 1!2 included in C'e(n). Finally, all terms may be negated, giving
a
metric to be maximized.
It should also be noted that for certain modulation schemes, all transmitted
symbols have the same amplitude, i.e., ~ sb(n) ~ is the same for all h and n.
In this
WO 95!33314 218 9121 p~~S9510680i
-14-
case, the terms C'~(n) and f{j,n) do not need to be computed. Also, in certain
modulation schemes, the term s~(n j)sb*(n-k) does not need to be computed J(J-
1)
times, since it typically takes on fewer possible values. One possibility is
to store
these values in a lookup table whose index is determined by the hypothetical
symbol
values. Finally, for certain modulations, the hypothesized symbol values are
simple
values, so that the multiplication operation is not necessary. For example,
BPSK
gives hypothesized symbol values of + 1 and -1, so that multiplication can be
replaced with a possible sign change. Similar properties hold for QPSK or QPSK-
based modulations.
First, consider the case where it is assumed that the channel model is static,
i.e., not time varying, for demodulating the data associated with a particular
synchronization field. This can occur in a digital TDMA system which uses a
short
burst duration, as in the GSM system. This implies that ca,m(j,n) = c~(j),
e(j,n) = e(j), f(j,n) _ f(j), and g(j,k,n) = g(j,k), independent of n. Thus, a
single
set of channel estimates is needed for each diversity branch and sampling
phase.
Also, if optimal-combining is used, the weights w~(n) become w0.m.
The above described concepts are implemented into a receiver according to
one embodiment of the present invention which is illustrated in Figure 1.
Radio "'
signals are received by a plurality of antennas 100. Each antenna signal is
processed by a branch signal processor 101, which produces baseband, complex
data samples, as well as synchronization information. This information
includes
timing information and possibly initial channel tap estimates, which may be
obtained
from the correlations of the known synchronization sequence with the received
data.
The branch signal processor may also include a buffer for storing data
samples.
A channel estimator 104 uses the synchronization information and the
sampled data corresponding to the synchronization field to determine channel
tap
estimates. The channel estimator 104 can use a variety of methods to determine
the
channel tap estimates. One such method is described in U.S. Patent No.
5,031,193,
in which the synchronization correlation values are simply kept as the channel
tap
estimates. An alternative is to find channel tap estimates that, in a least
squares
CA 02189121 2004-10-12
-15-
sense, best predict the received data that corresponds to the synchronization
field.
Because these channel tap estimates may be noisy, it may be useful to further
process these channel tap estimates.
The data samples and channel tap estimates are processed by a metric
preprocessor 102, which essentially computes the metric multipliers e(j),
g(j,k), and
f(j), as required. These multipliers are supplied to a metric processor 103,
which
performs the Viterbi equalization process. This results in a detected symbol
sequence which may be converted into an information bit stream. The data or
bit
stream may be in soft form or passed with soft information, which may be used
in
subsequent decoding. In making the conversion to data values, the metric
processor
103 effectively demodulates the data, which may have been modulated using any
form of modulation, such as BPSK, GMSK, QP.SK, DBPSK, DQPSK, or ~/4-shift
DQPSK.
Because the channel is static, the terms f(j) and g(j,k) need only be computed
once, or once per a predetermined demodulation interval. Also, in the metric
processor 103, the C'h and D'6 terms can be pre-computed for all possible
hypotheses and stored in a table for use in each iteration. If ~ sti(n) ~ is
the same for
all hypotheses, as is the case in commonly used digital modulation schemes,
then
the terms f(j) and C'ti need not be computed.
An embodiment of the branch signal processor, one per diversity branch, is
described in more detail in Figure 2. The radio receiver 200 converts the
radio
signal into a sampled, complex baseband received signal. There are many ways
of
performing this conversion, though most involve some form of filtering, mixing
with local oscillator signals, and amplification. One well known approach is
shown
in Figure 2 of U.S. Patent No. 5,031,193. Another approach involves the use of
log-polar quantization, later followed by conversion to complex samples, as
shown
in U.S. Patent No ~. 5,048,059. The received signal samples are stored in a
buffer 201. If
the digital cellular system is TDM or TDMA, the buffer allows storage of at
least one
time slot of data. In an FDM or FDMA system, the buffer 201 may be omitted.
wo 95r~331a 21 8 91 21 Pcr~s9s~o~so1
-16-
The synchronizer 202 determines which of the data samples to keep for
further processing by selecting one or more sampling phases, where each
sampling
phase corresponds to keeping 1 sample every T seconds. For fractionally-spaced
equalization, two or more sample phases are kept (M sample phases are kept).
The
art of synchronization is well known. Typically, the synchronizer correlates
the
received data samples to one or more known synchronization sequences.
Sometimes
only a portion, or sub-sequence, of the known synchronization sequence is
used.
The correlation values are typically combined in some way and then compared
with
one another, to determine the position of the synchronization and the best
sampling
phase or phases. This sampling information is provided to a decimator 203
which,
for every sampling phase selected, keeps only one sample of the data every T
seconds. The synchronizer also supplies synchronization information, such as
frame
timing information and channel tap information. The channel tap information
can
be related directly to the correlation values computed during synchronization.
An alternative embodiment of the diversity branch signal processor is shown
in Figure 5. The radio receiver S00 converts the radio signal into a sampled
complex baseband received signal which can be stored in a buffer 501 as
described
above with respect to Figure 2. Unlike the embodiment shown in Figure 2, the
radio receiver 500 does not oversample the received data. Instead, the radio
receiver provides MT samples of data per symbol period T. Thus, there is no
need
for decimation of the complex data stream. However, the synchronizer 502 only
provides synchronization information.
The metric pre-processor is described in more detail in Figure 3. This pre-
processor is used to compute the metric multipliers e(j), g(j,k) and f(j) if
needed.
For each diversity branch, there is a FIR filter bank 301 consisting of a
plurality of
FIR filters 300. There are 1 FIR filters 300 in each filter bank 301, i.e.,
one FIR
filter per ray in the channel models. The outputs of these FIR filters are
summed
such that the first FIR filter outputs are summed, the second FIR filter
outputs are
summed, and so forth. These summations are performed by adders 302. This
gives J metric multipliers for term B'e(n).
CA 02189121 2004-10-12
- 17-
The metric pre-processor also computes the metric multipliers for C'e(n),
and D'e(n). Each of 'these terms consists of a sum of channel tap products.
These
can be computed by using the channel tap processor 303, and they need only be
computed once if the channel is static. All pre-processor results are then
stored in a
buffer 304.
The embodiment illustrated in Figure 1 is applicable for the case where the
channel does not change appreciably for the data associated with a particular
synchronization field. However, when this is not the case, the channel taps
must be
adaptively estimated or predicted on each diversity branch. A receiver for use
in
this situation is illustrated in Figure 4, in which like elements correspond
to like
elements in Figure 1. In this embodiment, initial channel tap estimates can be
obtained from the synchronization process and these estimates may be further
refined by training a channel tracker over the synchronization field. Finally,
tentative symbol detections may be fed back to the diversity branch channel
trackers
to allow refinement of the channel estimates or predictions.
In Figure 4, each diversity branch has an associated channel tracker 404.
This tracker estimates or predicts the channel taps that correspond to the
sampled
data provided to the metric pre-processor 402. The tracker can be initialized
using
synchronization information provided by the diversity branch signal processor
401.
A method for both initialization and tracking is given in U.S. Patent Serial
No.
5,465,276. The channel tracker may have two modes: a training mode and a
decision-directed mode. During the training mode, the channel tracker uses
knowledge of what was transmitted to train the channel tap estimates. This
knowledge can correspond to the synchronization sequence or other known
sequences within the transmitted symbol stream. During the decision-directed
mode, the channel tracker takes tentatively detected data from the metric
processor
403 and assumes that they are correct. This allows the channel tracker to
update
WO 95/33314 PCTlUS95l06801
21891 ?1
- is -
channel tap estimates. Those skilled in the art will be aware that there are
many ,
forms of channel tracking and prediction.
The metric pre-processor 402 computes the necessary metric multipliers
from the sampled data and channel tap estimates or predictions. The metric
processor 403 uses the metric multipliers with the sequence estimation
algorithm to
provide both tentative and final detected data. The tentative data are used
for
channel tracking purposes. At time n, the tentative data correspond to
decisions on
transmitted symbols s(n-upd) through s(n-upd-1+ 1), where upd is an update
delay
design parameter, which is some non-negative integer. Knowledge of these
symbol
values allows the channel trackers to predict certain received data values and
to
compare the predictions with the actual values. The difference can be used to
update the channel tap estimates, which are used to predict channel values for
time
n+1.
According to one preferred embodiment of the present invention, the present
invention is used in a receiver for IS54 TDMA digital cellular signals. Two-
branch
antenna diversity would be used (D=2) and T/2-spaced equalization (M=2). The
number of channel taps (J) would be 2. Whike the modulation is ~r/4-shift
DQPSK,
the ~r/4-shift can be removed from the received data. For data sample
(n+mIM)T,
this is achieved by a multiplication with exp(-x(n+m/M)4). The resulting data
can
be treated as a QPSK symbol stream.
The embodiment shown in Figure 4 would be used to demodulate the
received signal. At iteration n, the metric multipliers are given by:
e(O~n) =~''o.o(n)co o(0~)ro(n~ +wo,l(n)co',i (0~)ro((n+I!2)T )
+wi.o(n)ci o(0,n)rl(n?j+u'i.i(n)ci O0~)ri((n+Il2)~
WO 95133314 218 9121 p~~s~,o~l
-19-
e( 1 ~n) =~''o,o(n)co of 1 ~)TO(nT7 +wo,l(n)co~ ( l,n)ro((n + 1/2)?7
+~''i.ofn)ci.a(1~)Tl(n??+w~(n)c~i(l,n)rl((n+1/2)?7
g(4~1~)=woo(n)coo(0~)coo(1~) ~"'o,~(nko i(0~)c0.1(1~)
+"'i,o(n)c~o(0~)y.otl~)+wl,l(n)ci i(0~)cl,l(1~)
The f(j,n) terms are omitted since ~ sb(n) ~ Z = 1 for all h. When forming the
metric, the term C'b would also be omitted.
An embodiment of the metric pre-processor is given in Figure 6. Received
data values are stored in a data buffer 6~, channel tap estimates are stored
in a
channel tap buffer 601, and weighting factors are stored in a weighting factor
buffer
602. At time n, the metric multipliers are computed one at a time. A selection
device 603 selects two complex values, either a data value and a channel tap
value
or two channel tap values. These selected values are multiplied in a
complex/complex multiplier 604, which multiplies one of the values with the
conjugate of the other value to form a first product. A selection device 605
selects
one scalar weighting factor, which is multiplied by the first product in a
complex/scalar multiplier 606, which multiplies complex and scalar values to
produce a second product. This second product is accumulated in an accumulator
607. This process is repeated four times to produce a particular metric
multiplier.
Then, the accumulator contents are reset and the process is repeated until all
three
metric multipliers are produced.
In the metric processor, at time n, there are four previous states
corresponding to hypothetical (n-1)th symbols and four current states
corresponding
to hypothetical n'th symbol values. This gives 16 possible hypotheses to
consider.
The delta metric associated with a given hypothesis h is given by:
WO 95/33314 PCT/US95I06801
2189121
-20-
M~(n) =Re{e(U,n~rh (n) +e( l,n)sh (n -1)?
_Re{8(0~1 ~~h (n~h(n_ 1)}
The metric multipliers are not explicitly multiplied with hypothetical symbol
values,
since these hypothetical values for sh (n), s~ (n-1),and sh (n)sh(n-1) are all
+1, -1,
+i, and -i, where i denotes the unity imaginary number. Thus, multiplication
of
a+ib by these values is equivalent to forming a+ib, -a-ib, -b+ia, and b-ia,
respectively. Thus, the 16 branch metrics can be formed by a set of adders and
invertors, which add and negate the real and imaginary parts of the metric pre-
multipliers
It will be known to those skilled in the art that other sequence estimation
algorithms, besides the Viterbi algorithm, can be used to exploit the metrics
in
finding a detection decision. For example, sequential decoding and other non-
exhaustive search methods can be used. It will be known to those skilled in
the art
that the above invention can be applied to other forms of diversity, such as
frequency diversity, time diversity, and polarization diversity. Finally, the
above
invention can be used to efficiently implement a combination of MLSE and
decision-feedback equalization, as described in M.V. Eyuboglu and S.U.H.
Qureshi, "Reduced-state sequence estimation and set partitioning and decision
feedback", IEEE Trans. Commun., Vol. 36, pp. 13-20, lan. 1988.
It will be appreciated by those of ordinary skill in the art that the present
invention can be embodied in other specific forms without departing from the
spirit
or essential character thereof. The presently disclosed embodiments are
therefore
considered in all respects to be illustrative and not restrictive. The scope
of the
invention is indicated by the appended claims rather than the foregoing
description,
and all changes which come within the meaning and range of equivalents thereof
are
intended to be embraced therein.
