 |
Description  |
|
|
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method and a device for real-time
separation of mixed signals.
2. Discussion of the Related Art
The problem posed is the blind identification of a mixture of signals.
Signals are received on a certain number of sensors, equal to p in number
for example. These signals come from a mixture, which is by assumption
linear but whose transfer function is unknown, of a number n less than or
equal to p of "source" signals which are also unknown, and which, also by
assumption, come from independent and non-Gaussian (except strictly for
one of them alone) sources. It therefore involves at the same time
separating, that is to say identifying, these source signals and
determining the transfer function effecting the mixture of signal which
are received on the p abovementioned sensors: it is therefore a problem of
blind deconvolution.
Taking the simple example from the field of radar of sonar, the signals
received by the sensors which together constitute the reception antenna,
are generally processed to form channels in directions chosen a priori,
this making it possible to spatially separate "sources" constituted by
echoes or noise-makers. The problem posed here is to identify there
channels directly.
Thus, to fix ideas, if two sources x.sub.1 (t) and x.sub.2 (t), where t is
the time variable, and two sensors providing two signals e.sub.1 (t) and
e.sub.2 (t) such that:
e.sub.1 (t)=x.sub.1 (t)+.beta.x.sub.2 (t)
e.sub.2 (t)=.alpha.x.sub.1 (t)+x.sub.2 (t)
are considered, if it is then possible to obtain .alpha. and .beta., that
is to say to identify the transform matrix:
##EQU1##
the two channels
e.sub.1 (t)-.beta.e.sub.2 (t)
and e.sub.2 (t)-.alpha.e.sub.1 (t)
are available which effect the desired separation of the source signals
x.sub.1 (t) and x.sub.2 (t).
In this example, the source signals are taken at the same instant t: the
mixture of signals is termed "instantaneous". In general, mixtures are not
instantaneous but "convolutive". It is nevertheless possible to reduce a
convolutive problem to an instantaneous problem by decomposing the signals
into signals with pure frequencies by spectral analysis obtained by
FOURIER Transformation. Denoting the frequency by f, each observed signal
can then be written:
##EQU2##
and each source signal can be written:
##EQU3##
Finally, the blind deconvolution problem to be solved here can be stated
thus:
p signals (p greater than or equal to 2) are observed, and for which it is
known that they arise from n unknown source signals (n less than or equal
to p) through an unknown linear, stationary transformation A(f) such that:
##EQU4##
the signals e(t), x(t) and the transformation A possibly being complex
data. Moreover, independent and, except strictly for one of them along,
non-Gaussian sources are involved. Blind deconvolution then consists in
the determination of the transfer function A and thereby of each of the
source-signals.
A known solution for effecting a time separation of an instantaneous
mixture A(f)=A of signals is proposed by Messrs. C. JUTTEN and J. HERAULT
in several articles including the one published in the French journal
"Traitement du Signal", volume 5, No. 6, 1988, pages 389 to 403. In
involves a method of separation which uses a fully interconnected
signal-layer array of linear neurons whose weights are supervised by an
algorithm akin to that of stochastic iteration.
This known method nevertheless has some disadvantages:
the algorithm used does not always converge, and it may therefore provide
erroneous outputs, which would diverge if there were no natural
saturation;
when there is convergence, the speed of convergence of this algorithm can
be extremely slow;
whether or not convergence occurs depends on the initialization, as well as
on the speed of convergence and on the solution provided.
SUMMARY OF THE INVENTION
The invention aims to remedy these disadvantages. To this effect it relates
to a method of real-time separation of signals received by a predetermined
number p of sensors, these signals coming from a linear mixture, but of
unknown transfer function, of a number n less than or equal to p of
source-signals which are also unknown and which come from independent and,
except strictly for one of them, non-Gaussian sources, this method
consisting in processing these received, sensed and sampled signals, in
two steps, including:
a first step of obtaining, in a manner known per se, p decorrelated signals
s(t) from these received signals e(t); and
a second step of calculating an orthogonal matrix Q such that x(t)=Q s(t),
x(t) being the required source-signals, this orthogonal matrix Q, which
effects a linear transformation, being obtained from polynomial
transformations of the data with the aid of polynomials of degree 3 or 4,
and being determined, with the aid of a stochastic algorithm which stores
average statistics called moments and cumulants, and which then uses these
estimated moments and cumulants to effect the real-time determination of
the matrix Q.
Preferably moreover, adjustable omission factors are introduced into the
calculation to enable the separator to deal with variable, that is to say
non-stationary phenomena.
If the p observed signals arise from a number n of source-signals which is
less than p, the separator merely operates better: it then automatically
supposes the existence of virtually-null fictitious sources, solely
generating calculation errors.
BRIEF DESCRIPTION OF THE DRAWINGS
At any event, the invention will be better understood, and its advantages
and other characteristics will emerge during the following description of
a non-limiting exemplary embodiment, with reference to the attached
diagrammatic drawing in which:
FIG. 1 is an overall synoptic diagram of the signal separator according to
the invention;
FIG. 2 is a synoptic diagram of the "rotator" used in the separator of FIG.
1;
FIG. 3 is one of the elementary "rotation" cells used in the rotator of
FIG. 2;
FIG. 4 is one of the "product" cells used in this same rotator;
FIGS. 5a-c shows an example of three source-signals;
FIGS. 6a-c shows the three signals actually observed, corresponding to
these three source-signals; and
FIGS. 7a-c shows the signals obtained with the aid of the separator in
accordance with the invention.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
Referring to FIG. 1, this real-time signal separator comprises a
"decorrelator-conditioner" 1 able to provide, on its p outputs 2, p
decorrelated signals s(t) from the p received, sensed and sampled signals
e(t) which are applied to it on its p inputs (3). The operation of the
decorrelator-conditioner 1 is well known per se, and is for example
described in an article by J. G. WHIRTER and T. J. SHEPHERD published in
"Proceedings SPIE", vol. 975, Advanced Algorithms and Architectures, San
Diego, 1988, and also in a communication by P. COMON, GRETSI Colloquium,
June 1989, Juan-Les-Pins, pages 137 to 140.
The p outputs s(t) at 2 are applied to a device 4 able to perform the
calculation of the abovementioned orthogonal matrix Q, such that:
x(t)=Q.s(t)
x(t) being the required source-signals obtained at 5 on the p outputs of
block 4.
This block 4 is here called the "rotator", since, as will be seen later,
obtaining the orthogonal matrix Q amounts to identifying a rotation.
The structure of the rotator is represented in FIG. 2. The p signals s(t)
are processed in a calculation chain in order to obtain the matrix Q. In
the cell denoted F, the product of Q times the signals s(t) is performed.
The p output signals x(t) are statistically independent and reproduce the
absolute value of the normalized source-signals.
Two algorithms can be employed:
an algorithm I using the moments of order 3,
an algorithm II using the cumulants of order 4, in particular with respect
to narrow-band source-signals.
The calculation chain is composed of a cell C for calculating moments or
cumulants. It possesses p inputs and the number of output thereof depends
on the algorithm chosen. It is also composed of
##EQU5##
"elementary rotators" Q.sup.(1), Q.sup.(2), . . . Q.sup.(j), . . .
Q.sup.(m), associated in cascade with (m-1) multiplication cells X.
With each sampling period, that is to say with each arrival of p samples of
signals s(t), the calculations are performed. These calculations are now
described:
Algorithm I
Cell C performs the calculation of the moments g.sub.ijk :
g.sub.ijk :=a.sup.2.s.sub.i (t).s.sub.j (t)*.s.sub.k (t)+b.sup.2.g.sub.ijk
where the symbol (*) denotes the complex conjugate, and where the triple
(i,j,k) describes the subset of {1, 2, . . . p}.sup.3 for which
i.ltoreq.j.ltoreq.k.
In this expression, a and b are the omission factors. They are real numbers
from ]0 to 1[ satisfying a.sup.2 +b.sup.2 =1. It is possible to adapt a or
b in order to adjust the power of the statistical averaging, and
simultaneously the duration of the local stationarity exploited. For a
small value of a, there will be much averaging, and the stationarity of
the processes will be assumed to be lengthy (the equivalent equiweighted
duration of averaging is of the order of 1/a.sup.2). For example,
0.01.ltoreq.a.ltoreq.0.05 is reasonable.
Cell Q.sup.(J) (see FIG. 3) has the role of evaluating the two numbers, c
and s, characterizing the elementary rotation matrix Q(q,r), denoted
Q.sup.(J) for simplicity. When 1.ltoreq.q<r.ltoreq.p, p(p-1)/2 pairs (q,r)
are described, this corresponding to p(p-1)/2 elementary rotators.
Choosing a description of rows, Q.sup.(1) =Q(1,2), Q.sup.(2) =Q(1,3), . .
. Q.sup.(p) =Q(1,p), Q.sup.(p+1) =Q(2,3), . . . This clearly establishes a
bijective relationship between J and the pair (q,r).
In FIG. 2, the lower wire 6 therefore transports the values of the
cumulants of the inputs s.sub.i (t) whereas the value of the cumulative
matrix H(J)=Q.sup.(J-1). . . Q.sup.(2) Q.sup.(1) travels on the top wire
7, and the output from each cell Q.sup.(j) appears at 8. The unit matrix
is applied to the first cell at 9.
With the aid of the information coming from the top wire 7 and from the
bottom wire 6 (cf. FIG. 3), the updating of the 4 cumulants G.sub.qqq,
G.sub.qqr, G.sub.qrr, and G.sub.rrr is firstly performed in cell Q.sup.(J)
through the formula:
##EQU6##
Once this updating is completed (it will be rapid since many of the
H.sub.jv are null or equal to 1), the cell will evaluate two numbers, c
and s, defined by:
##EQU7##
after calculating .theta. in the manner described below:
##EQU8##
Then calculate
##EQU9##
(k being equal indifferently to 0 or 1).
Cell X produces the product of the matrix described by the data coming from
the bottom at 8, times the matrix pxp coming from the left (cf. FIG. 4).
Two numbers, c and s, arrive from the bottom on the lower input of the
cell, as well as two indices, q and r. The matrix delivered at output (on
the right of the cell) is defined by H.sub.output =Q.sup.(J) H.sub.input,
where the matrix Q.sup.(J) differs from the unit matrix only in four
coordinates:
Q.sup.(J) (q,q)=c,Q.sup.(J) (q,r)=s,Q.sup.(J) (r,q)=-s*, and
Q.sup.(J) (r,r)=c, with 1.ltoreq.q.ltoreq.r.ltoreq.p.
This cell does fairly little work since most of the rows of Q.sub.input are
unchanged in the calculation H.sub.output =Q.sup.(J) H.sub.input (only two
of them need be calculated).
The last cell X provides the matrix Q which corresponds to
##EQU10##
Algorithm II
Cell C calculates the quantities:
M.sub.hijk :=a.sup.2.s.sub.h (t).s.sub.i (t)*.s.sub.j (t).s.sub.k (t).sup.*
+b.sup.2. M.sub.hijk,
with 1.ltoreq.h.ltoreq.i.ltoreq.j.ltoreq.k.ltoreq.p,
M.sub.jk :=a.sup.2.s.sub.j (t).s.sub.k (t)*+b.sup.2.M.sub.jk,
with 1.ltoreq.j.ltoreq.k.ltoreq.p.
Then the cumulants:
g.sub.hijk :=M.sub.hijk -M.sub.hi M.sub.jk -M.sub.hj M.sub.ik -M.sub.hk
M.sub.ij
are calculated.
We note that if the observations are complex and have been obtained after
FOURIER Transformation of real signals, these observations satisfy the
property termed "circularity" which implies that M.sub.hj =0 and M.sub.ik
=0. It is therefore possible to forgo calculation of these terms.
Furthermore, if the decorrelator operates correctly, it should in a steady
state enforce M.sub.jk =0 if j.noteq.k and M.sub.jj =1 if j=k. If the
means of calculation are modest, it will also be possible for these terms
to be replaced by their ideal value at the cost of a slight decrease in
the speed of convergence.
With the aid of the information coming from the top wire and from the
bottom wire, the updating of the 3 cumulants G.sub.qqqr, G.sub.qqrr, and
G.sub.qqqr [sic] is firstly performed in cell Q.sup.(J) through the
formula:
##EQU11##
As previously, the two numbers c and s are nest evaluated after calculating
.theta. in the manner described below:
If .vertline.G.sub.qqrr .vertline.>20.a.sup.2.M.sub.qq.M.sub.rr, calculate
.rho.=[G.sub.qqqr -G.sub.qrrr ]/G.sub.qqrr else .rho.=0.
Then
##EQU12##
c and s are deduced from .theta. through
##EQU13##
Referring now to the graphs of results obtained (FIGS. 5 to 7), the numbers
of samples are plotted as abscissae on these graphs, and the signal
amplitudes as ordinates.
The three source-signals (FIG. 5) are, in this stimulation, composed of
noise 10, a sawtooth signal 11, and a sinusoid 12.
The three signals 13, 14, 15 actually observed are represented in FIG. 6:
they have no resemblance to the source-signals of FIG. 5.
After processing by the separator which has just been described, this
separator using the algorithm II in this example, the three signals 16,
17, 18 represented in FIG. 7 are obtained. These three signals are
obtained for 1/a.sup.2 =100.
Note that these signals are obtained on non-corresponding channels, and
apart from the sign, this not being a very big disadvantage. The sinusoid
12 is obtained at 16, on the first channel instead of the third, and with
opposite sign. The noise 10 is obtained at 17, on the second channel
instead of the first, and with opposite sign, and the sawtooth 11 is
obtained at 18, on the third channel instead of the first and without
reversal of sign.
The signals which correspond to the sinusoid and to the noise are obtained
with a change of sign.
Among the advantages of the invention as compared with the other prior art
can be cited:
equally good operation in regard to real signals as in regard to complex
signals,
the possibility of operation when the number of sources is less than or
equal to p;
the possibility of using 2 algorithms, one of order 3, the other of order
4; only algorithm II operates in respect of narrow-band signals,
the real-time operation made possible by virtue of a single calculation of
G.sub.ijk or G.sub.ijkl, even when p>2,
the use of a conditioning test (algorithm I) or of a break-even threshold
(algorithm II) in each of the elementary rotators: see the conditions
regarding G for the calculation of .rho..
Among the novel applications made possible by virtue of this method, it is
expedient to note:
blind noise reduction:
solution performing an analysis by independent components;
high-performance processing if the noise is Gaussian and the signal
non-Gaussian;
the processing operates on all real signals whose statistics are known;
no recourse to lone noise or lone signal references;
location by sonar or radar:
on disturbed or uncalibrated antennae;
elimination of strong jamming sources very similar to the useful signal, or
even of exactly identical statistics (the separator is capable of
separating processes of like statistics); identification of a
"cocktail-party";
separation of uncorrelated multiple paths;
location of p sources with p sensors;
estimation of an unknown signal received on an unknown antenna;
blind equalization (application to telecommunications in particular).
As will be apparent, the invention is not limited to the exemplary
embodiment which has just been described, but on the contrary it is well
able to be employed in other embodiments using equivalent means, even if
they are more sophisticated.
* * * * *
|
|
 |
|
 |
Description |
|
