WO2002060090A1 - Particulate receiver for joint optimal estimation of discrete and continuous information in pulse-modulated signals - Google Patents

Abstract

The invention concerns an optimal particulate receiver recurrently delivering maximum likelihood joint estimation of source information (discrete variables and their synchronisation, as well as continuous parameters) transmitted by pulsed modulation, with possible access and channel codes for communications, and picked up in the form of noisy sampled data after Doppler effect and optional multipath effect and input filter and adapted correlator. The invention is characterised by K x L x M x N initial digital processors, virtual or real, said to be particulate, receiving in parallel said data and calculating the global probability measurement. The maximum likelihood delivered comprises in particular the maximum values of probabilities corresponding to the most likely message useful in telecommunications, and to the most likely state of continuous parameters useful in remote positioning with possibility of modularity of two functions and, for the latter, possible discrimination of multipath effects less than the (over)sampling period.

Description

 Particulate receiver for optimal joint estimation of discrete and continuous information in pulsed modulation signals

The object of the present invention is to jointly restore in an optimal probabilistic manner all of the information both discrete (pulses and their synchronizations) and continuous (wave and motion parameters) transmitted by pulsed modulation signals, with possible codes. access and channel, received in the form of noisy sampled measurements through a transmission channel comprising Doppler effects and possible multipaths.

The receiver according to the invention is based on the long coherent integration which allows the relevant exploration and memorization, by virtual or real digital processors known as particulate, of the global state space and its probabilities. This relates more particularly to the probability of continuous parameters in the form of sums of multinormal local densities over their tangent linear space, called extended Gaussian particles and subject to dynamic redistribution, as well as the tree of sequences of discrete variables present in the source signal , in the form of discrete states in reduced number. This receiver has the particularity of being able to discriminate by calculating different Doppler effects as well as multi-paths whose time offset is less than the sampling period of the input measurements. Its implementation, recurrent by its very principle, allows operation and application in real time and ensures, for a given computing capacity (number of parallel real processors, or sequential virtual equivalents), the optimal estimate of 1 most likely source of information (maximum likelihood).

The technical sector of the invention is that of digital reception of information transmitted under pulsed modulation, through the global transmission channel including filters, Doppler effects and the possible multi-paths between transmitter, reflectors and receiver equipped with relative mobility. Among the applications of this invention are:

- optimal reception of telecommunications messages, especially in cellular telephony for mobile use such as UMTS, EDGE, OR GSM systems. - the optimal estimation of the remote positioning signals, either by passive satellite way such as GPS, GNSS Galileo, or terrestrial like LORAN-C, or by both active and passive way like RADAR, or according to the acoustic mode of SONAR.

The precise context is that of the transmission signals comprising the following elements, included in FIG. 2:

- a carrier pulse ω ₀ which can be canceled or moved upon reception by means of a demodulator 2, by lowering the frequency to the useful band called base.

- a modulating envelope, which can be the subject of nested codes (access code, channel code) whose respective pulses of width δ and Δ are the discrete symbols {b ¹ } of an alphabet of complex numbers or constellation (phase-amplitude) and form source sequences comprising in particular the free symbols of the useful message in the channel code. - an additive disturbing noise assumed to be Gaussian white noise in the base frequency band.

- an analog-digital converter (3/3 'in Figure 2) producing data indexed by their time order t, the input filter of which provides either anti-aliasing (telepositioning) or adaptation to the pulse elementary (telecommunications) by preserving the whiteness of additive noise in discrete time.

a linear deformation by superposition of multi-paths consisting, after sampling, of a sum of delays indexed from 0 to R, maximum order, and weighted each by their amplitude with complex value.

- a non-linear deformation of frequency shift, due to the possible relative speeds between transmitter, reflectors and receiver as well as to the residual error in the descent in frequency, the whole constituting the oscillation at the so-called Doppler frequency. After passing through the correlator 4 with the possible entry code, the data to be processed 5, denoted y, have the model:

*-< ^{c < (}*⁽*' ' ^{m)) + υ}*

* - < ^{c <(} * ⁽ * '' ^{m)) + υ} *

where U designates the exclusive union, ∑ the numerical summation, j the pure imaginary number (j ² = -1),

C _t ^k (s _t ) is the complex value of the symbol at time t, before convolution by the response input filter f (.), Of the message produced by means of the channel code modulating the access code C ¹ , in their respective states (k, l) of synchronization, by a source sequence s _t indexed m among M possible, in the form of output:

C _t ^k (s _t ) = h (φ _t ^k (s _t )) of a sequential coding machine whose internal state φ obeys the dynamic transition equation with discrete values noted: φ _t = F ^{k, : L} (φ _t -i _/ b _t ), initial state φ ₀ = k, b _t being the discrete symbol at time t, updating the corresponding source sequence noted s _t , ie until time t. r is the integer part of the delays in sampling units δ, τ _{r, v} ^d their real remainder, v _r being the multiplicity index of these delays for the same whole part. The coefficients A _r ^d constitute the complex amplitudes of the indexed paths from r = 0 (direct path) to R corresponding to the maximum delay, for a Doppler shift ω _d numbered d from 0 to the maximum integer D. The unknown Doppler ω _d is linked to the unknown relative speed v _d between transmitter or reflector and receiver by the known relation ω _d = co ₀ v _d / c. The delays τ _{r / V} ^d are related to the speed v _a , and to the accelerations a _a , by the sampled dynamic equations:

où a^x(t) est la valeur particulaire gaussienne de l'accélération- source parmi les {i} discrétisations nécessaires à sa linéarisation locale, w(t) son bruit additif gaussien de covariance Q. v est le bruit additif à temps discret après échantillonnage, comprenant interférences et colorations possibles. _e jω ₀ τ * _u t) ₌ - 1) + 6 {a {t) + w (t))

where a ^x (t) is the Gaussian particle value of the source acceleration among the {i} discretizations necessary for its local linearization, w (t) its Gaussian additive noise of covariance Q. v is the additive noise at discrete time after sampling, including possible interference and coloring.

Three remarks should be noted: i) When the delay variables τ _r , _v ^d are not sought, as is the case in telecommunications, a change of variable in the coherent equation of y absorbs them in two ways : either in the form

α_i/r ^d étant les amplitudes des réflexions retardées de r unités, soit sous la forme

α _{i / r} ^d being the amplitudes of the delayed reflections of r units, ie in the form

R Vr

r = 0 v = \ oi ^d being the amplitudes of the global channel of reflections. ii) When the input filter approaches the ideal low-pass, the influence of past symbols is slowly extinguished (in 1 / t). This results in a reverberating channel of long memory, making observable small differences between delays, and facilitating the discrimination of multi-paths close to the direct path, in particular of less than a sampling period. This advantage, useful in telepositioning, manifests itself in the Jacobian of the non-linear parametrization in amplitudes and delays, which the following particle estimate uses by means of local Gausian particles in the tangent plane associated with this Jacobian. iii) Note that the raw sampled data, after input filter, are additive noise colored by multi-code interference (in communications) as well as due to oversampling (in telepositioning). This coloring of the reception noise v _t , known for each of the two concerned cases mentioned above, is easily included in the previous model in the form of the correlation matrix Λ _{t / t} , expressing the mathematical expectation than E [v _t , v _t .]. The colored reception noise, whose Gaussian character is preserved by the central limit theorem, is thus characterized by a parametric increase according to known methods, and allows the operation of the particulate receiver described below, without any other procedure than that of 'an increase in size of its particulate state.

Recall the problem posed by reception:

If one knows the source information to be transmitted, as well as the constituent elements of the transmission channel (reflections and Doppler effects included), one can deduce by means of a coherent model the signal which will be captured. Reception consists in solving the opposite problem, which is precisely that which the solution of the present invention has as its subject: The content of the source information being unknown, as well as that of the channel and reception disturbances, it s 'is to make an estimate at all times that best reflects the data received so far, in an optimal sense from a probabilistic point of view. This estimate relates to the value of a set of state variables or parameters, of a discrete and / or continuous nature, necessary and sufficient to restore useful information-source. More precisely, to obtain such an optimal solution, it is a question of constructing the probability distribution of these variables, conditionally on the set of observations accumulated over the time elapsed since a certain initial instant.

The problem posed, for the general situation described by the above model, has no exact solution achievable by the currently known reception methods, nor a satisfactory approximate solution by those currently implemented when dealing with situations common reviews such as close multipath and multi-Doppler. The difficulty lies both in the discrete-continuous joint nature of the dynamic estimation problem and in the presence of non-linearities on the continuous variables, leading to a combinatorial and dimensional double explosion beyond the reach of the computational structures considered up to 'now. Thus, for a set of fixed discrete variables, there is indeed a constructive estimate of the continuous parameters by means of the known Kalman algorithm, using a global linear approximation, but this presents two pitfalls: on the one hand, it does not accurately reflect the non-linearities which hinder the validity of this approximation in demanding situations (dynamic telepositioning with low signal / noise ratio and / or high Doppler); on the other hand, its feasible character in finite dimension is no longer preserved with the joint evolution of the possible free sequences presented by the real problem (mobile telecommunications).

Conversely, for fixed continuous parameters, there is indeed an optimal estimator of free message sequences, using the known Viterbi algorithm, using the corresponding discrete state model. But it loses its feasibility in finite dimension when the continuous variables become unknown and must themselves be estimated jointly.

The process closest to this, and aimed at solving the joint optimization problem mentioned, is that known under the name of PSP ("Per Survivor Processing"), the subject of publications and a patent pending in the United States of America in 1995. This method addresses the difficulty of optimal discrete-continuous joint estimation described above, by jointly applying the Viterbi algorithm for the discrete states of the problem on the one hand, and the algorithm for linear estimation of continuous parameters ^' restricted to the optimal sequences retained for each discrete state, on the other hand. However, this arbitrary separation by juxtaposition of the two aspects of the problem does not account for their interdependence creating the aforementioned combinatorial and dimensional explosion. The impossibility of achieving optimality by this route has been confirmed by mathematical proofs in previous scientific articles such as that of ZS Roth and KA Loparo "Nonlinear filtering problems with finite dimensional algebras", published in the journal Systems & Control Letters , N.7, The original solution to the technical problem exposed above, which is the object of the present invention, extends and completes the general principles of particle estimation introduced by a previous invention of the same author entitled "Method and system of optimal estimation no linear dynamic processes in real time ", whose patent was filed in France under number 94/07274, in Europe under number 9595256.5-2206, and in the United States of America as US Patent 5933352. This prior invention use of Dirac point particles in large numbers, whose supports reproduce the a priori stochastic evolution of state variables by random draws, to then be weighted conditionally to the data according to the Bayes formula, and possibly redistributed accordingly.

The present invention of a particulate receiver firstly comprises two general innovations, absent from the previous one, essential in the performance of said receiver both in terms of precision and of calculation time:

- it introduces to estimate the continuous variables of the local diffuse particles called Gauss, that is to say with non-point support, localized by their means and extent characterized by their covariances. The interest of sums of such particles, in addition to a capacity of universal approximation of the measures of probability, just like the measures of Dirac, is to allow that with a reduced number of them due to their extended character and their automatic displacement conditionally to the data.

- it introduces into combinatorial exploration-selection of sequences of discrete source variables (a, b) a deterministic tree exploration as well as a redistribution, also deterministic. The latter is based on the memorization of a fixed number of them, particles with the highest probabilities conditional on the data collected, thus achieving the optimal probabilistic allocation of the computed computational capacities.

Other innovations, more specific to the dreaming problem, appear in the technical description below, and are recalled in the claims. The particulate receiver according to the invention, for the optimal joint estimation of digital and continuous information in pulsed modulation, intervenes according to FIG. 2 on the data 5 originating from the antenna signal 1 after the descent in base frequency by a demodulator 2 and the digital conversion ensured by the sampler 3 'provided with its input filter 3, either adapted to the frequency of (over) sampling (telepositioning), or adapted to the elementary pulse (telecommunications) and, possibly after the correlator 4, to the access code; it includes a calculation unit 6 consisting of KXLxMXN initial processors δOO ^ ¹ real or virtual, called particulate, receiving said data in parallel; each of these processors carries, in the associated memories, a local particulate representation called klmn of the composite state (k, l, m, x) of the signal to be estimated, according to the following structure illustrated in FIG. 1.

- x = (ω _d , A _r , _v ^d , τ _r , _v ^d ) summarizes the vector of continuous parameterization governed by the non-linear dynamic system (f, h):

x _t = f (x _t -ι k, m _t (a _t , b _t )) y _t = h (x _t , k, l, m _t (a _t , b _t )) 4- υ _t

- the pair (k, l) represents the possible state of synchronization of access code and channel code among the possible K XLs.

- the integer index m identifies one of the sequences of discrete source variables (a, b) among the most likely M retained until time t, according to the finite storage capacity imposed by construction. - the integer index n identifies, for each preceding triplet (k, l, m), the local multinormal distribution G _mn ^kl (x) that the probabilization of the state x of the continuous parameters previously contains in each point of its tangent space defined (ω _d , A _r , _v ^d , τ _r , _v ^d or û _{d /} -i _{, r} ^d depending on the two cases) in a global sum of the form:

NOT

avec

with

this sum having the property of universal probabilistic representation with respect to x, convergent when N increases.

Each particle klmn therefore represents a local density, gaussian with respect to x, stored digitally by the composite state (k, l, m, μ ⁿ , P ⁿ ), the last two components of which are respectively the mean and the covariance of the associated Gaussian density, and by the real scalar p (k, l, m, n) which represents the probability or associated weight of the particle klmn, the whole forming the particulate state.

Each of the 600 _mn ^kl processors comprises a generator 604 _tnn ^kl of state transition of said particles between two sampling instants t-1 and t which, taking into account the dynamics of the sequences imposed by the access code and / or of those possible in the message of the channel code, as well as the kinematics of the relative movement transmitter-receiver, delivers the new values 612 _min ^kl of the particulate state at time t. In each processor δOO _mn ¹¹¹ , a corrector ôOS, ^ ¹ calculates, from said values 612 _mn ^kl and sampled data 5, the new values δlS _ron ^ of this particulate state. Each particle processor is therefore characterized by information which it is responsible for calculating recurrently and keeping in memory permanently: the state (k, l, m, μ ^π , P ⁿ ) of the gaussian particle klmn, thus than its weight p (k, l, m, n). The components k, l represent, remember, the discrete synchronization states (channel code and access code); the component m designates the branch considered in the tree of source sequences of discrete variables (a, b); the components μ ⁿ and P ⁿ are the mean and the covariance of the n-th Gaussian necessary for the representation of the probability density of the continuous parameter x, knowing k, l, m, n. The weight of each Gaussian particle and its location in the state space thus collectively reconstruct the probability over the entire state space. This probability, as announced in the previous paragraph, evolves by conditional prediction-correction to the data, which is the subject of the particle estimation introduced.

The detailed description of the sequential functioning of a particle processor _{δOO tnn} ¹¹ is as follows:

- Initialization:

At the initial instant t = 0, the switch 607 _πffl ^kl delivers to the evolution generator 604 _mn ^kl the components δlO ^ ¹ of the initial state of the particle klmn, supplied by the initial state generator βQS _m P ¹ according to an a priori probability law representative of the uncertainty over the entire state space.

Concerning (k, l), the K X L states are equiprobable and all initially retained. Concerning m, the initial state is reduced to the alphabet of discrete variables (a, b). Concerning x, the initial Gaussian n must at least cover the multimodal possibilities due to nonlinearity (multiplicity of blind Doppler speeds, for example).

At the following moments t, the switch 607 _ran ^kl delivers to the evolution generator 604 _ran ^kl the components of the particulate state ôlS _mn ¹ * ¹ after redistribution at the instant t-1.

- The prediction :

The evolution generator 604 _min ^kl then calculates the new particle state components 612 _ιraι ^kl at the instant t in accordance with the state transitions between t and t-1. The discrete state (k, l) of the particle denoted klmn remains invariant as long as it is not concerned by the redistribution member 606. The discrete state m of the particle klmn, which represents the sequence m among M retained since the previous instant, is temporarily increased by branches representing each of the following symbol possibilities (m 'among M') in the alphabet considered, before it is redistributed by 606 after the measurement. The continuous state x evolves on its tangent space according to the doubly linear kinematics (in x and w), with Gaussian fluctuation centered around a ¹ and of covariance Q, and its prediction provides the new means μ ⁿ and local covariances P ⁿ of the Gaussian particle klmn, for each (k, l, m), according to: | --ι = JW-I | * -U ^k > ™ * (<h> h)) ^p % t-ι = m - 1)? ι wj (* - 1) r +) QVÙ r

where: J _x ^f (t-1) designates the Jacobian of f with respect to x _t . _x in μ ⁿ _t - _{ι | t} - _ι , J _w ^f (t) designates the Jacobian of f with respect to w, taken in the argument (a _t , b _t ) of each m.

If we denote by G '^ ¹ (x, 111-1) the distribution locally

Gaussian obtained after the prediction and by p (k, l, m ', n, t j t-1) its weight, we can follow below its transformation after each new datum 5, under the conventional notation

111-1 (prediction) - »t 11 (correction):

- The correction:

From the components of the particulate state 612 _min ^kl and of the measurement 5 at time t, the weighter supplies the new weighted particle conditionally to this new datum by application of the Bayes formula, in the form:

«Ffc / _™ '« «• ₊ IA - P ( ^fc ' ^l > ^m '> ⁿ ^ 1 ^{l ~} ) ^G ™ n ( ^x - ^t \ ^{t ~ 1} ) PJV ^t 1 ^k ι ^l . ^me . ⁿ . ^x t = x) p (yt \ t - i)

The local character of the Gaussian particles considered allows linearization with respect to x of the expression of the measures y; we thus obtain the multiplication of two local Gaussians which provides after normalization a new local Gaussian particle represented with its weight by: p (k, l, m ', n, x, t \ t) = p (k, l, m' , n, t \ t) .G _n (x, t \ t), with the means μ ¹¹ and local covariances P ⁿ corrected for each (k, l, m), according to:

where J _x ^h (t) designates the Jacobian of h with respect to x in μ ⁿ _{t | t} - _ι - - Redistribution:

After weighting by the data at time t, the Gaussian particles are all given new weights, depending on their location. The redistribution procedure uses them to redistribute on these locations the (KxLxM'xN) renormalized particles by affecting the (KxLxMxN) which have the maximum likelihood (i.e. at maximum weight).

This redistribution procedure introduces a coupling between all the processors ôûO _π , ^ ¹ of the unit 6 via the redistribution unit. This being activated, it redistributes all the particulate states 612 _πra ^l into βlS, ™ ¹ .

Thus very unlikely discrete synchronization states (k, l) disappear very quickly, lowering their initial cardinality KXL to that of the non-negligible residual states p (k, l), as shown in Figure 1, freeing up the corresponding computing capacity on M, N for real-time tracking.

- The estimate:

The function of the terminal member 609 is to deliver the recurrent estimate 7 with maximum likelihood. The maximum joint likelihood corresponds to the argument (k *, l *, m *, x *) of the maximum of the densities p (k, l, m, x). The marginal likelihood maxima correspond to:

- the argument m of the maximum of the marginal p (m), designating the most likely message, for telecommunications use. - the argument of the maximum of the marginal p (x), designating the most likely value of the dynamic variables x, for the use of telepositioning.

The result is a new type of digital receiver. Its particle calculation method is adapted to the non-linear and combinatorial difficulties of joint estimation of continuous and discrete variables and allows a coherent integration preserving as long as possible, for a given calculation capacity, all the states of probability sufficient to contribute to the final estimate, this for an optimal extraction of information in critical situations commonly encountered (multiple close ti-paths, Doppler at blind speeds, low signal / noise ratios).

Claims

1. Particulate receiver for the optimal joint estimation of discrete (pulses and their synchronizations) and continuous (wave and motion parameters) information in pulsed modulation signals (1) with possible access and channel codes , after demodulation (2), through the global channel including multipath and Doppler effects, input filter (3), sampler (3 ') as well as adapted correlator (4), and characterized in that: - KXLXMXN processors initial numerical (600 _ιraι ^kl ), real or virtual, called particulate each represent a state (k, l) of the synchronization of possible codes, a sequence m of the combinatorics of discrete-source variables, a real vector state x of continuous parameters probabilized in sum of N multinormal local measures on their tangent space by Gaussian particles klmn with probability distributions G _tnπ ^kl (x, t | t) conditional on the data, of associated weight p (k, l, m, n , 111), a new type of general purpose particle. - A generator (604 _ran ^kl ), initialized by

, calculates at each instant t the multinormal density of evolution a priori G ^ ¹ (x, 111-1) of each particle klmn, taking into account the combinatorics of the augmented sequences of the discrete variables possible at the instant t current and of the dynamics of the continuous state variable x. - A corrector (eos ^ ¹ ) calculates after each instant t the particular state (βlB ^ ¹ ) a posteriori from its value at the previous instant t-1 and new data y _t (5), at using Bayes' formula using the probability density of the additive noise. - The redistribution unit (606) coupled to all the processors (δOO _mn ¹ * ¹ ) redistributes all the particulate states

in (eiδ _ran ¹¹¹ ), retaining the particles of the highest weight. The terminal organ (609) delivers the recurrent estimate (7) of the joint maximum likelihood p (k *, l *, m *, x *) of the discrete and continuous variables, as well as the respective marginal likelihood maxima p ( m ^f ) and p (x) of the message m useful in telecommunications and parameters x useful in telepositioning. 2. Receiver according to claim 1, characterized in that the redistribution member (606) automatically reduces the cardinality KXL of the synchronization states (k, l) after the initial acquisition period, leaving only the particles remaining of significant weight. 3. Receiver according to claims 1 and 2, characterized in that the generator (604 _min ^kl ) increases after each data the cardinality of the variable m by the possibilities of the free discrete variables (a, b) at this instant, this cardinality taking over its nominal value after redistribution by the organ (606), in order to memorize the most likely sequences of the possible combinatorics. 4. Receiver according to claims 1, 2, 3, characterized in that the optimal processing carried out is based on the conditional probability of the data (5) which may include colored interference noise (telecommunications) or oversampling of the access code which colors the resulting additive noise (telepositioning). 5. Receiver according to claims 1, 2, 3, 4, characterized in that in telepositioning, it uses the long impulse response of the input filter approaching the ideal low-pass to discriminate by calculation the multi-paths close to the direct path of less than a period of (over) sampling. 6. Receiver according to claims 1, 2, 3, 4, characterized in that in the absence of an explicit estimate of the delay (case of telecommunications), a change of variable absorbs the multiplicity of whole delays or not while leaving unchanged the other elements of the receiver, and thus allows the modularity of the two telecommunication and telepositioning functions. 7. Receiver according to claims 1,2,4, characterized in that in the absence of a channel code (RADAR, SONAR and LORAN case), the index k disappears, giving Gaussian particles indexed by min, 1 representing the synchronization of the pulses (possibly coded), and in that in the absence of fast dynamics of the movements (case SONAR and LORAN), the discretization {a ¹ } is reduced to {θ}.