Note: Descriptions are shown in the official language in which they were submitted.
CA 02201460 2004-02-24
Joint Detector for Multiple Coded Digital Signals
Field of Invention
This invention relates to the joint detection of a multiple digital signals
that are forward
error correction coded and share the same transmission medium in a manner that
causes
mutual interference, More specifically, the present invention relates to a
novel method
for detection that allows the permissible interference to be increased and
bandwidth to
be conserved.
Background of the Invention
In order to maximize the number of signals that can share a transmission
medium, the
frequency spectrum is re-used in a variety of ways. The traditional approach
is to
physically isolate communications signals of the same frequency in order to
reduce
their mutual interference to acceptable levels. Less traditional approaches
use spread
spectrum techniques to average the effects of interference over a bandwidth
significantly greater than the information bandwidth. In both of these cases,
interference will exist to some extent and, in some cases, can significantly
reduce the
system capacity, i.e., the informationlunit time/unit bandwidth.
To increase the capacity, joint detection schemes have been proposed that take
into
account the effect of the interference between the different signals and
perform
interference cancellation. Examples of such schemes are found in
S.Verdu, "Minimum probability of error for asynchronous Gaussian multiple-
access
channels," IEEE Trans. Inf.~ Th., vol. 32, No. 1, pp.85-96, January 1986.
R.Lupas and S.Verdu, "Linear multiuser detectors for synchronous code-division
multiple-access channels," IEEE Trans. Inf. Th., vol. 35, No.l, pp.123-136,
January
1989;
Doc. No. 18-9CA
';~
R.Lupas and S.Verdu, "Near-far resistance of multiuser detectors in
asynchronous
channels," IEEE Trans. Comm. , vol. 38, No.4, pp.496-508, April 1990;
M.K.Varanasi and B.Aazhang, "Multistage detection in asynchronous code-
division
multiple access communications," IEEE Trans. Comm. , vol. 38, No.4, pp.509-
519,
Apri11990;
D.L.Ayerst et al, U.S. Patent No.: 5323418, 1994;
D.L.Schilling et al, U.S.Patent No.: 5553062, 1996;
and include techniques such as applying linear transformations to the received
samples
to decorrelate the interference, and techniques such as estimating the
strongest user
1o first, subtracting it from the received signal and repeating it for the
next strongest
signal, etc. These techniques work well if the interference does not overwhelm
the
desired signal at any stage in the processing. Because of the latter
constraint, these
techniques have generally only been considered for spread spectrum signals.
The
aforementioned joint detection schemes do not take into account any forward
error
IS correction coding of the signals.
To achieve the theoretically optimum capacity when multiple signals share the
same
transmission medium requires the use of forward error correction coding as is
described by T.M.Cover and J.A.Thomas, in Elements of Information Theory, New
2o York: Wiley, 1991. Pedagogical techniques for achieving the theoretical
capacity
suggest applying a different code to each user at the transmitter and, at the
receiver,
estimating the digital signal with the largest signal to noise ratio (or the
strongest code),
subtracting its effect, and then repeating for the next digital signal; very
similar to the
techniques which have been proposed for uncoded systems. These techniques
require
25 powerful codes that do not lead to a practical implementation. Such a
technique, that is
"almost practical", has been presented in the literature, for example by
A.J.Viterbi, in
a paper entitled " Very low rate convolutional codes for maximum theoretical
performance of spread-spectrum multiple-access channels" , IEEE J. Sel. Areas
Comm. ,
2
Doc. No. 18-9CA
vol. 8, no.4, pp.641-649, May 1990, but it has the drawback that it treats the
digital
signals asymmetrically and requires some co-ordination between transmitters.
An
alternative approach to joint detection of multiple coded digital signals that
is known to
be optimum in a maximum likelihood sense for certain types of forward error
s correction codes, is described by T.R.Giallorenzi and S.G.Wilson, in a paper
entitled
"Multiuser ML sequence estimator for convolutional coded asynchronous DS-CDMA
systems," IEEE Trans. Comm. , vol. 44, No. 8, pp.997-1008, August 1996.
This latter technique is a Viterbi-like algorithm that has a complexity, which
is
exponential in both the code memory and the number of digital signals, making
it
to impractical for implementation. There are other approaches to the joint
detection of
multiple coded signals that are obvious to those practicing the art. These
include
approaches such as cascading a joint detector for multiple uncoded signals
with
standard decoding algorithm. These approaches however, are fundamentally
limited by
the performance of the joint detector for multiple uncoded signals.
Examples of schemes related to and for obtaining reliability estimates from
the
preliminary estimates are found in H.L.van Trees, Detection, Estimation and
Modulation Theory: Part I, New York: Wiley, 1968.
Examples of schemes related to soft-output decoding are found in
2o L.R.Bahl et al, "Optimal decoding of linear codes for minimizing symbol
error rate,"
IEEE Trans. Inf. Th. , vo1.20, pp284-287, March 1974;
G.Battail, "Coding for the Gaussian channel: the promise of weighted output
decoding," Int.J.Sat.Comm., vol.7, pp.183-192, 1989.
J.Hagenauer and P.Hoeher, "A Viterbi algorithm with soft decision outputs and
its
applications," Proc. IEEE Globecom, pp.47.1.1-47.1.7, November 1989;
P.Robertson et al, "A comparison of optimal and suboptimal MAP decoding
algorithms operating in the log domain," Proc. ICC, pp.1009-1013, Seattle,
June
1995.
3
Doc. No. 18-9CA
Summary of the Invention
It is an object of this invention is to reduce the effects of the interference
between a
s multiplicity of coded digital signals sharing the same transmission medium
so as to
permit greater interference and conserve bandwidth.
It is a further object to provide a method that does not require asymmetrical
treatment
of the digital signals.
to
It is a further object of the invention to provide a method that has a
practical
implementation.
The present invention provides an iterative method for reliably estimating
multiple
15 coded digital signals that share the same medium causing mutual
interference. The
digital signals, in general, come from different sources but they need not.
The method
is comprised of two steps that are applied to preliminary estimates of each
digital
signal, one or more times. There are various known methods of obtaining these
preliminary estimates. In many cases, the best approach is to detect each
digital signal
2o as if it were the only digital signal present in the transmission medium.
The
performance of the present invention will depend upon the quality of these
preliminary
estimates. With regard to the approach taken to obtain these preliminary
estimates, the
present invention relies only on a statistical model of the interference
between these
preliminary estimates.
The first step of the method is to provide reliability estimates for each data
element of
each digital signal using the preliminary estimates, a statistical model for
the
interference, and any a priori information regarding the data elements. This
interference model corresponds to the statistical distribution of the
preliminary
4
Doc. No. 18-9CA
estimates assuming the transmitted data is known. The reliability estimate is
defined as
the conditional probability of the data elements given the interference model,
the
preliminary estimates, and the a priori information. On the first iteration
there is often
no a priori information and the reliability estimates are based on the
preliminary
s estimate and the interference model. For binary data elements, the resulting
reliability
estimate is often expressed as the probability that the data element is a "0"
or a " 1" .
Properties of the forward error correction coding are not used in this step.
The second step of the method is to revise these reliability estimates for
each digital
1o signal based on the forward error correction code used for that digital
signal. In the
literature, decoders that revise the symbol reliabilities are often called
soft-output
decoders. The revised probability estimates are the conditional probabilities
of the data
elements given the reliabilities of all the data elements for that digital
signal, and the
relationships between them, as defined by the forward error correction code.
In this
15 step, the digital signals are independently decoded. This results in a
significant
computational saving over joint decoding.
The subsequent iterations use the revised reliability estimates for each data
element of
each digital signal obtained from the second step as a priori information for
the first
2o step. This improves the performance of the latter, which in turn can be
used to improve
the performance of the second step. On the last iteration, the decoders of the
second
step are configured to produce reliability estimates or hard decisions
corresponding to
the information elements of those digital signals of interest. The information
elements
may or may not be explicitly contained in the data elements of each digital
signal, but
2s they may be always be estimated through the knowledge of the forward error
correction
code.
Doc. No. 18-9CA
In accordance with the invention, a method is provided of detecting a
plurality of
digital signals that are forward error correction encoded and mutually
interfere. The
method comprises the steps of:
a) obtaining preliminary estimates of the plurality of digital signals;
s b) calculating a reliability estimate for each data element of each digital
signal from
preliminary estimates of those data elements, a statistical model of the
interference, and
a priori information, if any, concerning those data elements;
c) calculating a revised reliability estimate for each data element based on
the reliability
estimates from the first step and the properties of the forward error
correction code for
to the corresponding digital signal; and
d) repeating the previous two steps, one or more times, using the revised
reliability
estimates provided by step (c) as a priori information for step (b).
In accordance to another aspect of the invention, a system is provided of
detecting a
15 plurality of digital signals that are forward error correction encoded and
mutually
interfere, given preliminary estimates of those signals, comprising:
means for calculating a reliability estimate for each data element of each
digital signal
in dependence upon the preliminary estimates of those data elements, a
statistical model
of the interference, and a priori information, if any, concerning those data
elements;
2o and, for calculating a revised reliability estimate for each data element
based on the
reliability estimates calculated and the properties of the forward error
correction code
for the corresponding digital signal.
The present invention can be applied to digital signals in any shared
transmission
25 medium, or in distinct transmission media where there is crosstalk between
the media.
6
Doc. No. 18-9CA
Brief Description of the Drawings
Exemplary embodiments of the invention will now be described in conjunction
with the
drawings, in which:
s Fig. 1 is schematic block diagram of a communication system to which the
present
invention can be applied;
Fig. 2 is a schematic block diagram of an iterative joint detector for
multiple decoded
signals;
Fig. 3 is flow chart of the steps required for obtaining reliability
estimates;
1o Fig. 4 is a graph illustrating performance of present invention in a
synchronous
Gaussian channel for the case of five digital signals with a pairwise
correlation of 0.75;
Fig. 5 is a block diagram illustrating a serial implementation of this
invention;
Fig. 6 is a block diagram illustrating an alternative serial implementation to
that shown
in Fig 5;
is Fig. 7 is a block diagram illustrating the use of multiple preliminary
estimates, in
accordance with this invention; and,
Fig. 8 is a block diagram illustrating a feedback arrangement for implementing
each
iteration of the method.
2o Detailed Description
The present invention is a method of processing the received signal samples
obtained
when multiple coded signals share the same transmission medium. An example of
a
communications system to which this invention can be applied is illustrated in
Fig. 1.
2s In this example, each of the K independent data sequences {bk(i): k=1..K,
i=1,...} are
modulated with a signaling waveform to produce a digital signal. These
signaling
waveforms may include filtering, frequency translations, spreading codes, etc.
The
signaling waveforms need not be unique. These signals then enter the
transmission
medium and may suffer corresponding delays and attenuation, and be degraded by
Doc. No. 18-9CA
noise. In this example, the communications receiver has K parallel
subreceivers, one
for each digital signal. These subreceivers provide preliminary estimates of
the data
elements of each digital signal. These preliminary estimates are often called
soft
decisions in the technical literature. In many cases, the best subreceiver is
one that is
s matched to the signaling waveform for the corresponding digital signal,
ignoring the
presence of the other digital signals. This matching refers not only to the
transmitted
signaling waveform but also any delay, frequency translation, or phase
rotation that
may have been incidentally applied to the signal after transmission. The
present
invention also applies to non-optimum subreceivers. The output of these
matched
detectors is then sampled, once per data element period, to produce a soft
decision for
each data element in the corresponding digital signal.
The present invention is a method of processing the preliminary estimates
provided by
these K subreceivers to reduce the effects of interference. An exemplary
arrangement
for the processing performed in the present invention is shown in Fig 2. In
the simplest
embodiment for this invention, the digital signals have the same signaling
rate and are
synchronous. Let b(i) be the vector of K symbols, one from each digital
signal, with a
common symbol time i, and let y(i) be the corresponding vector of K
preliminary
2o estimates from the K subreceivers. The statistical model for the
interference, in this
case, is the conditional distribution of y(i) given the transmitted data b(i).
If the noise
is Gaussian then, in this case, the conditional distribution of y(i) given
b(i) is
multivariate Gaussian for the symbol time i and independent from one symbol
time to
the next.
The first step of the invention requires a means for estimating reliability of
the data
elements of each of the digital signals. The conventional approach is to use
Bayes' rule
for conditional probability, one then computes the reliability estimate
(conditional
s
Doc. No. 18-9CA
~Q~ ~~
probability) of each data element of each digital signal that is based only on
the vector
of preliminary estimates y(i), the statistical model for the interference, and
the a priori
information regarding those data elements. Mathematically, joint reliability
estimates
for the K digital signals is given by
Pr~b(i)IY(i)~ = pLY(i)Ib(1)l PrLb(z)l
h~Y~i)~
The reliability estimates for the individual digital signals are given by the
corresponding marginal distributions.This constitutes the first step.
Exemplary steps
to for determining these reliability estimators are shown in Fig. 3.
In the second step of the method, each digital signal is considered
independent of the
others. As shown in Fig. 2, this can be implemented as K parallel decoders.
For each
digital signal, the reliability estimates provided by the first step are
revised based on the
known relationships between data elements. These known relationships are due
to the
forward error correction encoding. When the data sequences are finite, a
preferred means
for soft-output decoding is described by L.R.Bahl, J.Cocke, F.Jelinek, and
J.Raviv, in a
paper entitled"Optimal decoding of linear codes for minimizing symbol error
rate," IEEE
Traps. Inf. Th., vol. 20, pp.284-287, March 1974.
In subsequent iterations, the revised reliability estimates provided by the
second step
are used as a priori probabilities in the first step. In the preferred
embodiment, the
revised reliability estimates are treated as independent of one another; and
in the
preferred embodiment, not all of the revised reliability estimates provided by
the
second step are used in each first step calculation. In particular, the first
step
reliability estimates for a particular digital signal only use the a priori
information for
those digital signals other than the one of interest.
9
Doc. No. 18-9CA
~~,
An example of the bit error rate performance obtained with this method for the
case of
a synchronous Gaussian channel with five independent pseudo-randomly
interleaved
digital signals, when the cross-correlation between each pair of the signaling
waveforms (a measure of the interference) is 0.75, is shown in Fig. 4 for 1,
2, 4, and 8
iterations. Also shown in Fig. 4 is the performance obtained when there is no
interference between the users (p=0).
Investigations have shown that performance improves if each of the K digital
signals is
pseudo-randomly interleaved relative to one another at the transmitter after
forward
to error correction encoding. In the description of the present invention, the
interleaving
is considered part of the forward error correction code. However, the approach
can be
applied with any type of interleaving, or even with no interleaving.
The present invention does not require that the digital signals are
synchronous.
1 s However, it is recommended that the interference model for the preliminary
estimates
include the effects of any asynchronism. The complexity of the present
invention
depends in part on the complexity of this interference model. There is the
possibility of
reducing the complexity by appropriate design of the K subreceivers. If the
digital
signals are not only asynchronous but also have different signaling rates then
to
20 optimize performance may require oversampling of the received signal, and
constructing a corresponding interference model. Oversampling is defined as
sampling
at a rate higher than the transmission rate of the data elements.
The present invention does not require that all data sequences use the same
forward error
25 correction code. The use of different error correction codes will only
affect the second
step of the method. If the digital signals are asynchronous or the data
sequences have
different lengths then the direct implementation of the soft decoding method
of L.R.Bahl
et al, may not be appropriate. Alternatively, in this case and others where
the sequence
to
Doc. No. 18-9CA
.w..
length is an issue, the soft decoding techniques can be applied to a series of
overlapping
blocks where the block size is less than the sequence length. In addition to
L.R.Bahl et al,
there are alternative soft decoding techniques as presented by J.Hagenaur and
P.Hoeher, in a paper entitled" A Viterbi algorithm with soft-decision outputs
and its
applications" , Proc. IEEE Globecom'89, pp.47.1. l-47.1.7, November, 1989.
[and by P.Robertson et al, in a paper entitled "A comparison of optimal and
sub-optimal
MAP decoding algorithms operating in the log domain," Proc. ICC'95, pp.1009-
1013,
June 1995, that can also be used in the second step of the method.
1o The digital signals are not required to have the same modulation format.
There are no
particular issues associated with different modulation formats except to note
that in the
exemplary communications shown in Fig. 1, the sampling will correspond to
sampling
both the in phase and quadrature components of a digital signal with some
modulation
formats. With a binary modulation format, only the reliability of the data
element "1"
is or a "0",but not both, needs to be stored; while with a M-ary modulation
formats, at
least M-1 or M reliability values should be stored corresponding to the M
possible
values for each data element.
The invention also applies when the digital signals have the same, different,
or even
2o time-varying power levels. The latter may be due to different propagation
losses,
fading and mufti-path. For the best performance the available knowledge
concerning
the power levels and time-variations, whether it be deterministic or
statistical, should
be included in the interference model.
25 Complexity may often be an issue in either the first or the second step of
the method.
Sometimes, in the first step, simplifications are made to the interference
model to
reduce this complexity. These simplifications often result from a
consideration of a
subset of the available data in the model. For example, for each digital
signal, the
11
Doc. No. 18-9CA
interference model may only consider the interference from the two strongest
interferers and ignore the effects of the other signals. Similarly, in
addition to the
block processing approach mentioned above, in the second step simplifications
can
often be made to the decoding technique to reduce the complexity. These
s simplifications often result from considering only a subset of the available
data. For
example, some simplified decoding techniques only consider the most probable
sequences (paths) at each step and ignore the less probable ones. In practice,
there is
usually a tradeoff between complexity and performance.
1 o Additional material is found in the appendix that further elaborates and
provides
additional examples in accordance with the invention.
The parallel implementation shown in Fig. 2 is one implementation of this
invention;
however, the invention can also be implemented serially. In particular, one
need not
is decode all K signals in the second step. It is only necessary to decode a
subset of the
digital signals, containing at least one signal, in the second step before
repeating the
first step. This approach may be appropriate when a subset of the signals has
significantly greater power, and it is desirable to characterize their effect
accurately
first. Such an approach affects the convergence time of the algorithm.
Referring now to Fig. 8, the invention does not need to be implemented with
distinct
hardware or software for each iteration of the method as may be suggested by
Fig. 2.
One can also use the same hardware or software in a feedback arrangement, as
is more
obviously suggested by Fig. 8, for implementing each iteration of the method,
wherein
the revised reliability estimates are fed back to the initial means for
estimating
reliability, and the two steps of the algorithm are repeated. This feedback
implementation can also be applied to all embodiments of the method. In
practice, the
12
Doc. No. 18-9CA
approach illustrated in Fig. 8 may require some buffering of the incoming
preliminary
estimates .
In Fig. 5, a serial implementation is shown that decodes only one signal at
the second
step, selecting a different one of the K digital signals for each second step.
According
to the invention, any number from one to all of the K digital signals is
decoded on
execution of the second step. The signals need not be decoded in any
particular order,
nor do all signals have to be decoded an equal number of times. An alternative
serial
implementation is shown in Fig. 6. In this case, two decodings are performed
with
to each second step but the decoded digital signals are not distinct on
subsequent
decodings. In Figs 2, 5, and 6, the phrase "Means for soft-output decoding k"
indicates a means for soft-output decoding of digital signal k.
Note that any existing interference cancellation method for uncoded signals
can be
applied, prior to this invention, to provide the preliminary estimates. The
only
requirement is that the interference model applies to the preliminary
estimates after the
initial interference cancellation, if any, is done.
The invention is also applicable when there are multiple preliminary estimates
of the
2o signal such as may occur when one has a number of distinct receivers. This
is known
in the literature as diversity reception. There are a number of ways to use
the multiple
preliminary estimates according to the invention. The simplest approach is
using a
means of combining the multiple estimates into a single estimate prior to this
invention.
This is illustrated in Fig. 6.
There are many methods in the literature for combining a plurality of
estimates of the
same signal or set of signals. Examples of such combining schemes can be found
in
13
Doc. No. 18-9CA
W.C.Jakes (ed.), Microwave Mobile Communications, (1974) reprinted by New
York:
IEEE Press , 1993 .As shown in Fig. 7, the method remains unchanged in this
application. An alternative to the approach shown in Fig. 7 is to include the
multiple
preliminary estimates in the interference model. In this case, the method
remains the
s same although the means for calculating the reliability estimates may
change.
Of course, numerous other embodiments other than those described heretofore
and
those described in the appendix may be envisaged, without departing from the
spirit
and scope of the invention.
14
