Max Silberztein
email: max.silberztein@univ-fcomte.fr

Syntactic parsing with NooJ

When parsing a text, NooJ's parsers store all the annotations that they produce in the Text's Annotation Structure (TAS). At each level of the various linguistic analyses and the corresponding parser, a given parser may add annotations to, or remove annotations from, the TAS. As annotations are attached to larger and larger sequences of texts, the TAS represents the hierarchical structure of the sentence and its syntactic constituents. We have added a new module that processes this structured information in order to display the structural tree of sentences. We discuss the difference between a structural tree and a derivation tree, and we show how NooJ's structural trees can represent any type of linguistic units, including discontinuous ones.

Linguistic Units

One characteristic of NooJ is that its parsers process several types of linguistic units in texts: prefixes and suffixes (e.g. dis-, -ization), simple words (e.g. table ), multiword units (e.g. as a matter of fact) and discontinuous frozen expressions (e.g. to take … into account). 1 All linguistic units recognized by NooJ's morphological, lexical, syntactic and semantic parsers are represented as annotations, rather than tags. 2 An annotation might represent either an Atomic Linguistic Unit (ALU), i.e. an element of the vocabulary of a language, or any type of sequences of ALUs that constitutes a meaningful syntactic or semantic unit, such as a noun phrase (e.g. the head of the company), a verbal group (e.g. may not have wanted to read) or an adverbial complement (e.g. Monday February the 11th at 2PM), etc.

When parsing a text, NooJ's parsers store all the annotations that they produce in the Text's Annotation Structure (TAS). Lexical annotations (ALUs) are displayed as black labeled arrows in the TAS; syntactic annotations are generally displayed in green in the TAS. At each level of the various linguistic analyses and the corresponding parser (orthographical, lexical, morphological, syntactic and semantic), a given parser may add annotations to, or remove annotations from, the TAS. Usually parsers look up any type of information in the TAS, and enrich the TAS as they produce different types of analysis.

As a large number of linguistic units are ambiguous, the TAS often represents more than one annotation at a given location in the text, thus representing any type of ambiguity that might occur within one level of linguistic analysis, or between various levels of analysis. For instance, in the following figure that represents the TAS after the lexical parsing of a text, we can see that the multi-word unit round table (meaning a meeting) has been annotated in parallel with other literal interpretations for the same exact sequence. A number of ambiguities produced by low-level parsers might be solved by higher-level parsers: for instance it is easy to disambiguate the word "that" in the following sentence:

I brought that with that table.
When a syntactic parser produces an analysis for the whole sentence, it annotates the first occurrence as a pronoun and the second occurrence as a determiner. Indeed, NooJ contains also a number of disambiguation mechanisms that can be used to remove annotations from the TAS, either automatically (via syntactic grammars selected in Info > Preferences), semi-automatically (via regular expressions selected from the TEXT > Locate panel) or manually (directly in the TAS window)3 However, it is often impossible to automatically disambiguate words, phrases or sentences with purely linguistic tools. For instance, in the sentence: .

There is a round table in room A32

there is no way a computer (or even a human, for that matter) can detect for sure if the round table refers to a meeting or to a piece of furniture with a round shape. In the real world, figuring out what this round table refers to might involve a complex discourse analysis (to understand the semantic context of the sentence), or even a pragmatic analysis (to understand the context of the situation).

Figure 1.Lexical ambiguity is represented by parallel paths

In consequence, NooJ's TAS is designed to store potential ambiguities along several levels of linguistic analyses, and each of NooJ's parsers (at the morphology, syntactic and semantic levels) is designed to process ambiguous inputs and produce ambiguous outputs.

Structured Annotations

NooJ syntactic grammars are typically used in order to describe sequences of words that constitute meaningful units or entities (e.g. "the head of the European Central Bank", "Monday, June the 12th at 3PM"). In other applications, linguists write syntactic grammars in order to locate syntactic constructions of interest, such as idiomatic or frozen expressions4 or sentences that contain certain grammatical words or syntactic constructs. 5 NooJ Syntactic grammars can associate matching (recognized) sequences in the text input with different kinds of information produced as an output; the information produced in the output of the syntactic grammars is represented as annotations that NooJ stores in the TAS. For instance, NooJ's Date.nog syntactic grammar, which represents date complements such as "Monday, June 13th at a quarter to 9", annotates every recognized date with the annotation <ADV+Date>; after having applied this grammar to a text, the corresponding annotations appear directly in the TAS in Figure 2.

A given grammar may produce more than one annotation for a given region of text in order to represent structural information for a phrase or a sentence. Moreover, as annotations can be recursively attached to substrings of the matching sequences, it is possible to represent and annotate embedded phrases.

Figure 2. A syntactic annotation in the TAS

For instance, NooJ will annotate all the sentences recognized by the syntactic grammar of Figure 3 as <SENTENCE>; inside each of these annotated sentences, the sequence of words recognized by the embedded graph NP at the left of the verb will be annotated as <NP+Sub>, the sequence recognized by the graph VG will be annotated as <VG>, and the sequence recognized by the graph NP after the verb will be annotated as <NP+Obj>. Inside each of the graphs NP and VG (which themselves contain other embedded graphs), there might or might not be other annotations.

When such grammars are applied to a given text, the resulting TAS contains annotations that are structured, and the structure of the TAS reflects on the structure of the original sentence or phrase in Figure 4. It is important to realize that the syntactic TAS produced after a syntactic analysis has a different nature than the lexical TAS:

--in the lexical TAS, parallel annotations correspond to various types of ambiguities. For instance, in Figure 1, the annotation for "round table" is parallel to the sequence of two annotations for "round" followed by "table". Obviously, these two analyses are concurrent, as they cannot exist at the same time.

--in the syntactic TAS, parallel annotations may correspond to different levels of constituents in the phrase or sentence structure. For instance, in Figure 4, the annotation <SENTENCE> co-exists with the sequence of the three annotations <NP+Sub>, <VG> and <NP+Obj>. Of course, these parallel paths are both valid at the same time: they correspond to two different levels in the structure. 6 We have added the functionality of displaying this structured set of annotations to NooJ in the form of a structural tree that represents the structure of the recognized sequence, usually a phrase or a sentence (CONCORDANCE > Display Syntactic Analysis), see Figure 5: Note finally that if there are more than one set of syntactic annotations, or if there are remaining lexical ambiguities in the TAS, NooJ will produce and display more than one syntactic structural tree.

Structural trees vs Derivation trees

NooJ can display both structural and derivation trees and it is important to understand their difference. NooJ's structural trees, such as the one in Figure 5 that was produced by the grammar of Figure 3, have a different nature than derivation trees produced by traditional syntactic parsers.

NooJ structural trees represent the structure of the annotations that were attached to the recognized sentences or phrases, whereas derivation trees represent the syntactic parsing process, i.e. the path in the grammar that the parser took while it was parsing the text.

For instance, consider the following grammar that contains a number of embedded rules (or graphs):

…

The corresponding derivation tree is displayed in Figure 6. Traditional syntactic parsers produce derivation trees as their main result. Although derivation trees are very useful for figuring out how a given text was actually parsed7 , they represent the structure of the grammars, rather than the structure of the sentence. And, of course, derivation trees are highly dependent on the structure of the grammar: if a linguist decides to reorganize the DET grammar for instance, the derivation trees produced by the parser will change accordingly.

Figure 6. The corresponding derivation tree

On the contrary, the structural information represented in NooJ's structural trees is quite independent from the way the grammar is organized: that independence allows different linguists to construct and accumulate a large number of grammars over time, and their merging does not jeopardize the integrity of the resulting analysis.

Complex Atomic Linguistic Units

NooJ's syntactic parser processes represents affixes, simple words, multi-word units as well as discontinuous expressions in a unified way.

Figure 7.A complex TAS and the corresponding syntactic tree

Figure 7 shows the TAS for the text "He cannot turn the lights off": the contracted word cannot is represented by two annotations, whereas the discontinuous phrasal verb8 Since NooJ's syntactic parser operates on the TAS rather than on the text itself, it processes the two annotations "<can,V>" and "<not,ADV>" as if they were two separate words. The discontinuous annotation for the phrasal verb "<turn off,V+PV>" is not a problem for NooJ's syntactic parser either: NooJ knows how to handle discontinuous annotations. turn off is represented by a "bridge-type" annotation:

The ability to process all types of ALUs, including contracted or agglutinated as well as simple words, allows linguists to design simple syntactic grammars. For instance, in French, the word form au is a contraction of the preposition à and the determiner le. Usually, these two components do not belong to the same phrase: the preposition à belongs to the main verb's structure (e.g. parler à quelqu'un) or to a prepositional phrase (e.g. être à Paris), whereas determiners introduce noun phrases. Because NooJ transparently solves contractions, syntactic grammars built into NooJ do not need to take them into account: a regular, simple grammar for noun phrases that start with a determiner will automatically work in NooJ, even if the initial determiner happens to be contracted.

Figure 8 shows that the contracted word aux is processed as two ALUs (à and les) that belong to different substructures of the structural tree. This capability is useful for taking care of the dozen contractions in English and in Romance languages, and it is absolutely crucial for agglutinative languages such as Arabic and Hebrew, where series of grammatical words that belong to different structures of the sentence are agglutinated: in these languages, sequences such as "and in my house" are written as one word form 9 .

Figure 8. Syntactic parsers process contracted words transparently

Disambiguation

Until now, the only method for automatically disambiguating words in texts was to filter out annotations from the TAS by applying local grammars. Although local grammars are easy to develop, perform very efficiently, and produce spectacular results, in most cases, only a syntactic analysis of the whole sentence can produce a perfect syntactic disambiguation of all ALUs in the sentence. 10 NooJ's syntactic parser makes it easy to perform this perfect syntactic disambiguation: when one applies a syntactic grammar to the text with the option "syntactic analysis" checked, NooJ keeps all matching ALUs in the concordance; the concordance entry can then be reapplied to the original TAS as a filter, which in effect removes all other ALUs: the resulting TAS is disambiguated. Figure 4 shows such a resulting TAS: all the ALUs for the verb "to man" (such as in "you man the ship").

Conclusion

NooJ's syntactic parser now allows linguists to build and accumulate larger syntactic grammars up to the sentence level. As opposed to traditional syntactic parsers, NooJ processes and represents all types of linguistic units: affixes, simple words, multi-word units and also discontinuous expressions, which are transparently represented as chains of linked leaves in the syntactic tree.

NooJ, as opposed to traditional syntactic parsers, distinguishes structural trees from derivational trees: in particular, structural trees represent the structure of the text which may be largely independent and different from the structure of the grammar that was used to parse the text. This allows structural trees to be much more robust and standardized, as any local or global reorganization of a syntactic grammar does not need to have any impact on the representation of the resulting sentence structure. This framework allows NooJ to process contractions and agglutinations transparently: for instance, contracted words have no impact in the design of syntactic grammar because they are taken care of before the syntactic parsing. Another characteristic of NooJ's syntactic parser is that it does not require the text's linguistic units to be fully disambiguated beforehand: in particular, lexical ambiguities between multi-word units and sequences of simple words may remain unresolved, both before and after the syntactic parsing of texts.

Structural syntactic grammars are used to produce a structural analysis of the matching phrases and sentences, which can then be displayed as trees. As opposed 10 By perfect syntactic disambiguation, I mean that all the ALUs that cannot possibly occur in the sentence, according to syntactic rules, will be deleted. Of course, the TAS still might contains a number of remaining lexical ambiguities, see the ambiguity in "there is a round table in room A32" (a meeting or a table?).

to traditional syntactic parsers, NooJ allows linguists to control the structure produced independently from the organization of the grammar. I believe this feature is crucial to the project of accumulating and sharing large numbers of grammars. Finally, the resulting structured matches can be used as filters to disambiguate the TAS in a more powerful and systematic way than possible when using local grammars.

Figure 3 .

 3 Figure 3. A grammar may produce embedded syntactic annotations

Figure 4 .

 4 Figure 4. A structured system of annotations

Figure 5 .

 5 Figure 5.The corresponding structural tree

  | your | his | her | our | their; DemonstrativeDet = this | that | these | those;

Cf. (Silberztein

2008). 2 Cf. (Silberztein 2007).

see (Silberztein 2010a).

See for instance[START_REF] Simonetta | The Formalization of Italian Lexicon-Grammar Tables in a NooJ pair Dictionary/Grammar[END_REF].

See for instance (Silberztein Max 2010b).

Note however that some lexical ambiguities might still remain in the TAS after the syntactic parsing.

NooJ's grammar debugger uses derivation trees to display the path of each matching solution (see Grammar > Debugger).

See (Machonis 2008).


Alain Y Kibangou
email: alain.kibangou@ujf-grenoble.fr

Laurent Ros
email: laurent.ros@gipsa-lab.grenoble-inp.fr

Cyrille Siclet
email: cyrille.siclet@gipsa-lab.grenoble-inp.fr

Doppler Estimation and Data detection for Underwater Acoustic ZF-OFDM Receiver

A new scheme for Doppler estimation and data detection for OFDM underwater acoustic communications is derived in this paper. We design the OFDM symbol as a concatenation of two sub-blocks. The first one is shorter and carries out few data with few subcarriers whereas the second one contains both informative and pilot symbols. The first sub-block serves to estimate the Doppler scaling factor while the pilots in the second sub-block are used for estimating the equivalent channel. Both estimation approaches are based on high resolution methods for solving harmonic retrieval problems in time and frequency domains respectively. Each sub-block contains a cyclic suffix, which allows having more data to be processed. The effectiveness of the proposed scheme is evaluated by means of simulation results.

I. INTRODUCTION

Underwater acoustic channels are typically wideband in nature due to the small ratio of carrier frequency to the signal bandwidth, which introduces frequency-dependent Doppler shifts [START_REF] Li | Multicarrier communication over underwater acoustic channels with nonuniform doppler shifts[END_REF]. They also exhibit several propagation paths, so that the received signal is equivalent to the sum of several signals with different amplitude and time delays. Multipath delay and Doppler effects constitute the main obstacles to robust underwater acoustic communication. One common approximation is to treat the channel as having a common Doppler scaling factor on all propagation paths.

Orthogonal Frequency Division Multiplexed (OFDM) signals are particularly attractive because they lead to relatively simple channel estimation and data detection algorithms. Indeed, since subcarrier only experiences flat fading, complex time-domain equalizers are not necessary [START_REF] Bahai | Multi-carrier digital communications: theory and applications of OFDM[END_REF]. However, OFDM signals are particularly vulnerable to Doppler effects that destroy the orthogonality between subcarriers and thus induce intercarrier interference (ICI). In order to adequately recover the transmitted information, algorithms at the receiver must include estimation and compensation of the Doppler scaling factor, channel estimation, and information symbols estimation.

For estimating the Doppler scaling factor, several approaches have been suggested in the literature (see [START_REF] Sharif | A computationally efficient doppler compensation for underwater acoustic communications[END_REF] for example). In the OFDM case, they are based on the use of preamble and postamble of a packet consisting of multiple OFDM blocks [START_REF] Li | Multicarrier communication over underwater acoustic channels with nonuniform doppler shifts[END_REF] or by exploiting correlation induced by the cyclic prefix [START_REF] Kim | Parameter study of OFDM underwater communications system[END_REF]. Then, the received signal is resampled by using a sampling period related to the estimated Doppler scaling factor. Recently, the authors introduced a new scheme for estimating both Doppler and channel parameters by solving harmonic retrieval problems [START_REF] Kibangou | Joint channel and doppler estimation for multicarrier underwater communications[END_REF]. In this paper, we propose an improved version of the previous algorithm with a better use of the bandwidth and without explicitly estimating the paths gain and delay. Indeed, the lack of robustness to noise of the channel parameter estimators was a major drawback of the approach in [START_REF] Kibangou | Joint channel and doppler estimation for multicarrier underwater communications[END_REF], [START_REF]ZF OFDM receiver for underwater communications[END_REF]. Herein, instead of using a zero padding scheme, we introduce a cyclic suffix in the OFDM signal design. As in [START_REF] Kibangou | Joint channel and doppler estimation for multicarrier underwater communications[END_REF], the received data are processed block-byblock. The advantage of the proposed scheme is to avoid data resampling and residual CFO estimation and compensation.

II. SYSTEM MODEL

We consider an OFDM transmission system where each OFDM block is constituted with two sub-blocks of respective length 𝑇 𝑢 and 𝑇 𝑑 , with 𝑇 𝑑 /𝑇 𝑢 ∈ ℕ, as depicted in Fig. 1. Each sub-block is followed by a cyclic suffix (CS) of duration 𝑇 𝑔 . Therefore, the overall OFDM block duration is 𝑇 = 𝑇 𝑢 + 𝑇 𝑑 + 2𝑇 𝑔 . We denote by 𝑐 𝑞 the data symbols in the first sub-block. They are all informative and thus unknown to the receiver. In the second sub-block, all data symbols 𝑑 𝑘 are not informative; some of them are known to the receiver and will serve to estimate the equivalent channel parameters. In baseband, the signal 𝑠(.) to be transmitted can be viewed as a mixture of two signals 𝑠 𝑢 (.) and 𝑠 𝑑 (.), each one corresponding respectively to the first and to the second sub-blocks:

Data

𝑠(𝑡) = 𝑠 𝑢 (𝑡) + 𝑠 𝑑 (𝑡) (1)
with

𝑠 𝑢 (𝑡) = 𝜂 ∑ 𝑞∈𝒦𝑢 𝑐 𝑞 𝑒 𝑗2𝜋𝑞𝑄Δ𝑓𝑡 Π 𝑇𝑢+𝑇𝑔 (𝑡) 𝑠 𝑑 (𝑡) = ∑ 𝑘∈𝒦 𝑑 𝑑 𝑘 𝑒 𝑗2𝜋𝑘Δ𝑓𝑡 Π 𝑇 𝑑 +𝑇𝑔 (𝑡 -𝑇 𝑢 -𝑇 𝑔 )
where Δ𝑓 = 1/𝑇 𝑑 denotes the minimal frequency spacing between consecutive subcarriers, Π 𝑇 allows taking the CS operation into account, i.e. Π 𝑇 (𝑡) = 1, 𝑡 ∈ [0, 𝑇 ], and Π 𝑇 (𝑡) = 0, otherwise, 𝜂 allows controlling the power of the first sub-block so that both sub-blocks have the same power, 𝑄 is an integer that allows increasing the frequency spacing between the subcarriers in 𝑠 𝑢 (.), 𝒦 𝑢 (resp. 𝒦 𝑑 ) the set of subcarriers in the first (resp. second) sub-block.

In the sequel, we consider that 𝒦 𝑢 ⊂ 𝒦 𝑑 , meaning that some of the subcarriers of the second sub-block are reused in the first sub-block. By denoting 𝐾 𝑢 (resp. 𝐾 𝑑 ) the cardinality of 𝒦 𝑢 (resp. 𝒦 𝑑 ), i.e. the number of used subcarriers, we get 𝐾 𝑢 < 𝐾 𝑑 , 𝒦 𝑑 = {-𝐾 𝑑 /2, ⋅ ⋅ ⋅ , 𝐾 𝑑 /2 + 1}, and 𝒦 𝑢 = {𝑞 0 , ⋅ ⋅ ⋅ , 𝑞 0 + 𝐾 𝑢 -1}, for a given integer 𝑞 0 .

In passband, the analytical representation of the signal to be transmitted is

𝑥(𝑡) = 𝑠 𝑢 (𝑡)𝑒 𝑗2𝜋𝑓𝑐𝑡 + 𝑠 𝑑 (𝑡)𝑒 𝑗2𝜋𝑓𝑐𝑡 , 𝑡 ∈ [0, 𝑇 ],
with 𝑓 𝑐 the central carrier frequency. This signal is transmitted through a multipath underwater channel whose impulse response is given by:

ℎ(𝑡, 𝜏 ) = 𝑃 ∑ 𝑝=1 𝐴 𝑝 (𝑡)𝛿(𝜏 -𝜏 𝑝 (𝑡)),
where 𝐴 𝑝 (𝑡) and 𝜏 𝑝 (𝑡) are respectively the gain and the delay associated with the 𝑝th path. The following assumptions are adopted:

• All paths are affected by a similar Doppler scaling factor 𝑎 such that 𝜏 𝑝 (𝑡) = 𝜏 𝑝 -𝑎𝑡. • The path delays 𝜏 𝑝 , the gains 𝐴 𝑝 , and the Doppler scaling factor 𝑎 are constant over the block duration 𝑇 .

• The guard interval 𝑇 𝑔 is chosen so that 𝑇 𝑔 > max{𝜏 𝑝 } = 𝜏 𝑚𝑎𝑥 .
Therefore, the received signal results on a mixture of scaled, dilated or compressed, and delayed versions of the original OFDM block as shown in Fig. ] and

𝐼 2 = [ 𝑇𝑢+𝑇𝑔+𝜏𝑚𝑎𝑥 𝜆 , 𝑇 +𝜏𝑚𝑖𝑛 𝜆 ]
, where 𝜏 𝑚𝑖𝑛 ≤ 𝜏 𝑝 ≤ 𝜏 𝑚𝑎𝑥 , 𝑝 = 1, ⋅ ⋅ ⋅ , 𝑃 , and 𝜆 = 1 + 𝑎.

In 𝐼 1 and 𝐼 2 , the analytical representation of the received signal is respectively given as follows:

𝑦(𝑡) = 𝜂 𝐾𝑢+𝑞0-1 ∑ 𝑞=𝑞0 𝐵 𝑞 𝑐 𝑞 𝑒 𝑗2𝜋(1+𝑎)𝜑𝑞𝑡 + 𝑤(𝑡), 𝑡 ∈ 𝐼 1 (2) 𝑦(𝑡) = 𝐾 𝑑 /2-1 ∑ 𝑘=-𝐾 𝑑 /2 𝐵 𝑘 𝑑 𝑘 𝑒 𝑗2𝜋(1+𝑎)𝑓 𝑘 𝑡 + 𝑤(𝑡), 𝑡 ∈ 𝐼 2 (3)
where

𝜑 𝑞 = 𝑓 𝑐 + 𝑞𝑄Δ𝑓 , 𝑓 𝑘 = 𝑓 𝑐 + 𝑘Δ𝑓 , 𝑤(𝑡) denoting the additive noise, 𝐵 𝑞 = 𝑃 ∑ 𝑝=1 𝐴 𝑝 𝑒 -𝑗2𝜋𝜑𝑞𝜏𝑝
, and

𝐵 𝑘 = 𝑃 ∑ 𝑝=1 𝐴 𝑝 𝑒 -𝑗2𝜋𝑓 𝑘 𝜏𝑝 . ( 4
)
In both 𝐼 1 and 𝐼 2 , the received signal 𝑦(.) can be respectively viewed as a mixture of 𝐾 𝑢 and 𝐾 𝑑 harmonics with constant magnitudes. In the sequel, we intend to solve the problem of Doppler scale factor estimation as a Harmonic retrieval one. We make use of these two time windows for first estimating the Doppler scaling factor and then recovering the informative symbols contained in the OFDM block. Since the time windows involved in the estimation process depend on 𝜆, we assume that 𝜆 is bounded, such that 𝜆 𝑚𝑖𝑛 ≤ 𝜆 ≤ 𝜆 𝑚𝑎𝑥 . One can note that 𝜆 𝑚𝑎𝑥 and 𝜆 𝑚𝑖𝑛 are related to the maximal and minimal velocities of the underwater vehicles, which can be a priori known. In addition, we assume that 𝜏 𝑚𝑎𝑥 is known and 𝜏 𝑚𝑖𝑛 = 0. Therefore the involved time windows are modified as follows

𝐼 1 = [ 𝜏 𝑚𝑎𝑥 𝜆 𝑚𝑖𝑛 , 𝑇 𝑢 + 𝑇 𝑔 𝜆 𝑚𝑎𝑥 ] 𝐼 2 = [ 𝑇 𝑢 + 𝑇 𝑔 + 𝜏 𝑚𝑎𝑥 𝜆 𝑚𝑖𝑛 , 𝑇 𝜆 𝑚𝑎𝑥 ]
.

(5) Owing to the CS, the time windows to be used are larger than those obtained when using a ZP scheme as in [START_REF]ZF OFDM receiver for underwater communications[END_REF]. Obviously, with more observations, an improvement of the resulting estimation method is expected.

III. DOPPLER ESTIMATION

The harmonic retrieval problem has been extensively studied in the literature (see [START_REF] Kay | Modern spectral estimation, Theory and Application[END_REF], [START_REF] Stoica | Introduction to spectral analysis[END_REF], [START_REF] Roy | ESPRIT-Estimation of signal parameters via rotational invariance techniques[END_REF], [START_REF] Papy | Exponential data fitting using multilinear algebra: The single-channel and multi-channel case[END_REF] for example). In general the magnitude are assumed to be constant as in the case for 𝑦(.) in 𝐼 1 and 𝐼 2 . For solving (2) as a harmonic retrieval problem, we make use of the high resolution method called HTLS (Hankel Total Least Squares) [START_REF] Van Huffel | Enhanced resolution based on minimum variance estimation and exponential data modeling[END_REF]. This algorithm can be viewed as a special case of the ESPRIT algorithm [START_REF] Roy | ESPRIT-Estimation of signal parameters via rotational invariance techniques[END_REF] and also as a Total Least Squares variant of Kung et al.'s algorithm [START_REF] Kung | State-space and singular value decomposition-based approximation methods for harmonic retrieval problem[END_REF]. Resorting to a high resolution method is mandatory since the Doppler is to be estimated from a very slight deviation of the actual subcarrier frequencies. A search on discretized space of frequencies could need a very short step of discretization, implying a huge complexity. In other hand, FFT based methods have a lower bound of resolution incompatible in such a situation.

In the noiseless case, we consider the 𝑁 samples 𝑦 𝑛 , 𝑛 = 𝑛 0 , ⋅ ⋅ ⋅ , 𝑁 + 𝑛 0 -1, of the first portion (2) of the received signal:

𝑦 𝑛 = 𝜂 𝐾𝑢+𝑞0-1 ∑ 𝑞=𝑞0 𝑐 𝑞 𝐵 𝑞 𝑒 𝑗2𝜋𝜑𝑞(1+𝑎)𝑛𝑇𝑒 = 𝜂 𝐾𝑢+𝑞0-1 ∑ 𝑞=𝑞0 𝑐 𝑞 𝐵 𝑞 𝜙 𝑛 𝑞 , ( 6
) 𝑇 𝑠 being the sampling period. In a harmonic retrieval problem, we aim to estimate both the poles 𝜙 𝑞 = 𝑒 𝑗2𝜋𝜑𝑞(1+𝑎)𝑇𝑠 and the magnitudes 𝜂𝑐 𝑞 𝐵 𝑞 of the 𝐾 𝑢 harmonics.

For this purpose, let us first build with the samples 𝑦 𝑛 the following 𝐿 × 𝑀 Hankel matrix

Y = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 𝑦 𝑛0 𝑦 𝑛0+1 𝑦 𝑛0+2 ⋅ ⋅ ⋅ 𝑦 𝑛0+𝑀 -1 𝑦 𝑛0+1 𝑦 𝑛0+2 . . . ⋅ ⋅ ⋅ 𝑦 𝑛0+𝑀 𝑦 𝑛0+2 . . . . . . ⋅ ⋅ ⋅ 𝑦 𝑛0+𝑀 +1 . . . . . . . . . . . . . . . 𝑦 𝑛0+𝐿-1 𝑦 𝑛0+𝐿 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 𝑦 𝑛0+𝑁 -1 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ , with 𝑁 = 𝐿 + 𝑀 -1, 𝐿 > 𝐾 𝑢 , 𝑀 ≥ 𝐾 𝑢 .
It admits the Vandermonde decomposition:

Y = S 1 𝑑𝑖𝑎𝑔(𝛼 𝛼 𝛼)T 𝑇 1 , (7)
where S 1 and T 1 are two Vandermonde matrices with 𝜙 𝑞 as generators:

S 1 = ⎛ ⎜ ⎜ ⎜ ⎝ 1 ⋅ ⋅ ⋅ 1 𝜙 𝑞0 ⋅ ⋅ ⋅ 𝜙 𝐾𝑢+𝑞0-1 . . . . . . . . . 𝜙 𝐿-1 𝑞0 ⋅ ⋅ ⋅ 𝜙 𝐿-1 𝐾𝑢+𝑞0-1 ⎞ ⎟ ⎟ ⎟ ⎠ ∈ ℂ 𝐿×𝐾𝑢 T 1 = ⎛ ⎜ ⎜ ⎜ ⎝ 1 ⋅ ⋅ ⋅ 1 𝜙 𝑞0 ⋅ ⋅ ⋅ 𝜙 𝐾𝑢+𝑞0-1 . . . . . . . . . 𝜙 𝑀 -1 𝑞0 ⋅ ⋅ ⋅ 𝜙 𝑀 -1 𝐾𝑢+𝑞0-1 ⎞ ⎟ ⎟ ⎟ ⎠ ∈ ℂ 𝑀 ×𝐾𝑢 ,
while 𝛼 𝛼 𝛼 contains the complex magnitudes of the 𝐾 𝑢 harmonics:

𝛼 𝛼 𝛼 = 𝜂 ( 𝑐 𝑞0 𝐵 𝑞0 𝜙 𝑛0 𝑞0 ⋅ ⋅ ⋅ 𝑐 𝐾𝑢+𝑞0-1 𝐵 𝐾𝑢+𝑞0-1 𝜙 𝑛0 𝐾𝑢+𝑞0-1
) 𝑇

We intend to estimate the Doppler scaling factor from the angle of the generators 𝜙 𝑞 . In order to avoid any ambiguity since angles are obtained up to 2𝜋, the sampling period can be selected such that the angle of the generators belongs to [-𝜋, 𝜋]. For this purpose, it is enough to select 𝑇 𝑠 such that:

𝑇 𝑠 ≤ 1 2𝜆 𝑚𝑎𝑥 max{𝜑 𝑞 } . ( 8
)
It should be noted that this condition corresponds precisely to the Nyquist-Shannon sampling theorem condition applied to the Doppler scaled spectrum of the received signal. We can also derive the following proposition:

Proposition 1: If the sampling period is such that 𝑇 𝑠 ≤ 1 2𝜆𝑚𝑎𝑥 max{𝜑𝑞} , the Vandermonde matrices S 1 ∈ ℂ 𝐿×𝐾𝑢 and T 1 ∈ ℂ 𝑀 ×𝐾𝑢 , 𝐿 > 𝐾 𝑢 , 𝑀 ≥ 𝐾 𝑢 , with 𝜙 𝑞 = 𝑒 𝑗2𝜋𝜑𝑞(1+𝑎)𝑇𝑠 as generators are full column rank. Proof: The Vandermonde matrices loose their rank if at least two generators have the same angle modulo 2𝜋. Owing to condition (8) on the sampling period we know that the angles of the generators belong to [0, 𝜋]. Therefore, the angle of the generator are all distinct modulo 2𝜋. Thus, the resulting Vandermonde matrices are full column rank.

Let us denote by φ𝑞 the poles estimated with the HTLS method (see [START_REF] Kibangou | Joint channel and doppler estimation for multicarrier underwater communications[END_REF] for details). If the sampling period 𝑇 𝑠 is chosen according to [START_REF] Stoica | Introduction to spectral analysis[END_REF], then the angle of φ𝑞 , denoted ∠ φ𝑞 , belongs to [-𝜋, 𝜋]. We deduce the following estimator for the Doppler scaling factor:

â = -1 + 1 𝐾 𝑢 𝐾𝑢+𝑞0-1 ∑ 𝑞=𝑞0 ∠ φ𝑞 2𝜋𝜑 𝑞 𝑇 𝑒 . ( 9
)
One can note that such a Doppler scaling factor estimator is completely blind. However, since it is a SVD-based estimator, the computation load becomes significant when increasing 𝐾 𝑢 . So, we suggest to use few active subcarriers 𝐾 𝑢 . The choice of the optimal number is still an open question. Moreover, when dealing with subspace-based methods, the dimension of the initial matrix is very important. When applying HTLS, it has been shown that very good results are obtained for 𝐿 × 𝑁 -𝐿 + 1 matrices where 𝐿 ∈ [𝑁/3, 2𝑁/3] [13].

IV. DATA DETECTION Now, for recovering the transmitted information symbols, we assume that some pilot symbols have been inserted in the second OFDM sub-block. We first estimates channel parameters using pilot symbols before recovering the informative symbols. Recall that the symbols 𝑐 𝑞 are informative whereas only some of 𝑑 𝑘 are also informative. The samples corresponding to the time interval 𝐼 2 are given by:

𝑦 𝑛 = 𝑦(𝑡)| 𝑡=𝑛𝑇𝑒 = 𝐾 𝑑 /2-1 ∑ 𝑘=-𝐾 𝑑 /2 𝑑 𝑘 𝐵 𝑘 𝑒 𝑗2𝜋(1+𝑎)𝑓 𝑘 𝑛𝑇𝑒 .
In matrix form, we get: 𝑇𝑒 , and

y = Hb, ( 10
)
with y = ( 𝑦 𝑛1 ⋅ ⋅ ⋅ 𝑦 𝑛1+𝑁1-1 ) 𝑇 , b = ( 𝑏 -𝐾 𝑑 /2 ⋅ ⋅ ⋅ 𝑏 𝐾 𝑑 /2-1 ) 𝑇 , 𝑏 𝑘 = 𝑑 𝑘 𝐵 𝑘 , φ𝑘 = 𝑒 𝑗2𝜋(1+â)𝑓 𝑘
H = ⎛ ⎜ ⎜ ⎝ φ𝑛1 -𝐾 𝑑 /2 ⋅ ⋅ ⋅ φ𝑛1 𝐾 𝑑 /2-1 . . . . . . . . . φ𝑛1+𝑁1-1 -𝐾 𝑑 /2 ⋅ ⋅ ⋅ φ𝑛1+𝑁1-1 𝐾 𝑑 /2-1 ⎞ ⎟ ⎟ ⎠ ∈ ℂ 𝑁1×𝐾 𝑑 .
It is straightforward to check that H is a full column rank matrix if 𝑁 1 > 𝐾 𝑑 and 𝑇 𝑠 ≤ 1 2𝜆𝑚𝑎𝑥 max{𝑓 𝑘 } . As a consequence, we can compute the least squares (LS) solution of [START_REF] Papy | Exponential data fitting using multilinear algebra: The single-channel and multi-channel case[END_REF] as: b = H † y [START_REF] Van Huffel | Enhanced resolution based on minimum variance estimation and exponential data modeling[END_REF] where H † denotes the pseudo-inverse operator of the matrix H. Since the entries of b result on the product of a symbol 𝑑 𝑘 and the equivalent channel parameters 𝐵 𝑘 , without lack of generality, by assuming that the subcarriers numbered 𝑘 = 0, 1, ⋅ ⋅ ⋅ , 𝐾 𝑝 -1, 𝐾 𝑝 < 𝐾 𝑑 /2, are devoted to pilot symbols, i.e. 𝑑 𝑘 ,𝑘 = 0, 1, ⋅ ⋅ ⋅ , 𝐾 𝑝 -1, are known to the receiver, we get:

B𝑘 = b𝑘 /𝑑 𝑘 . ( 12
)
Now, the question is: how constructing B𝑘 associated with the information symbols from those estimated using the 𝐾 𝑝 pilots? First, we can note that (4) can also be written as

𝐵 𝑘 = 𝑃 ∑ 𝑝=1 𝛾 𝑝 𝜁 𝑘 𝑝 , 𝛾 𝑝 = 𝐴 𝑝 𝑒 -𝑗2𝜋𝑓𝑐𝜏𝑝 , 𝜁 𝑝 = 𝑒 -𝑗2𝜋Δ 𝑓 𝜏𝑝 .
(13) The expression above is particularly meaningful. Indeed, 𝐵 𝑘 can be viewed as a mixture of exponentials in the frequency domain. We can therefore obtain both 𝛾 𝑝 and 𝜁 𝑝 by solving a harmonic retrieval problem.

Assuming that the number of significative paths 𝑃 is known and provided 𝐾 𝑝 ≥ 2𝑃 , we make use of the HTLS method for solving the problem [START_REF] Van Huffel | Algorithm for time-domain NMR data fitting based on total least squares[END_REF] where 𝐵 𝑘 is replaced by its estimated value B𝑘 . For this purpose, we build an 𝐿 × 𝑀 Hankel matrix B, with 𝐾 𝑝 = 𝐿 + 𝑀 -1, 𝐿 > 𝑃 , 𝑀 ≥ 𝑃 , which admits the following Vandermonde decomposition:

B = S 2 𝑑𝑖𝑎𝑔(𝛾 𝛾 𝛾)T 𝑇 2 . ( 14
)
with S 2 and T 2 some Vandermonde matrices having 𝜁 𝑝 as generators, and 𝛾 𝛾 𝛾 the vector with 𝛾 𝑝 as entries.

Let us denote ζ𝑝 the estimated poles. By replacing the poles by their estimated values in S 2 and T 2 , we can solve the following equation:

𝑣𝑒𝑐(B) = (T 2 ⊙ S 2 ) 𝛾 𝛾 𝛾, ( 15
)
𝑣𝑒𝑐(.) denoting the vectorization operator whereas ⊙ stands for the Khatri-Rao product, i.e. a columnwise Kronecker product.

The entries of the least squares solution of (15), denoted γ, can be used for computing B𝑘 for any value of 𝑘 as B𝑘 = 𝑃 ∑ 𝑝=1 γ𝑝 ζ𝑘 𝑝 . Therefore, we can deduce the information symbols in the second sub-block as:

d𝑘 = b𝑘 𝑃 ∑ 𝑝=1 γ𝑝 ζ𝑘 𝑝 . ( 16
)
while those of the first sub-block can be obtained as ĉ𝑞 = α𝑞

𝜂𝑒 𝑗2𝜋𝜑𝑞(1+â)𝑛0𝑇𝑠 𝑃 ∑ 𝑝=1 γ𝑝 ζ𝑞 𝑝 . ( 17
)
α𝑞 being the corresponding entry of the least squares solution of the vectorized version of equation ( 7), i.e. 𝑣𝑒𝑐(Y) = (T 1 ⊙ S 1 ) 𝛼 𝛼 𝛼.

V. SIMULATION RESULTS

In these simulations, the range of frequency used by the underwater vehicles was [16𝑘𝐻𝑧 -27𝑘𝐻𝑧]. The Doppler scaling factor was set to 𝑎 = 8 × 10 -4 . We assume that |𝑎 𝑚𝑎𝑥 | = 10 -3 , meaning that the maximal relative speed is 1.5 m/s. The carrier frequency was set equal to 𝑓 𝑐 = 21 kHz, whereas the guard interval was 𝑇 𝑔 = 10 ms. We used 𝐾 𝑑 = 256 subcarriers for the second OFDM sub-block. The duration of this sub-block is 𝑇 𝑑 = 𝐾 𝑑 /𝐵, with 𝐵 = 11 kHz, whereas that of the first sub-block is 𝑇 𝑢 = 𝑇 𝑑 /10. Hence, the duration of one OFDM block is 45.6 ms. The data was modulated using a QPSK constellation. All the results presented below are averaged values over 100 independent Monte Carlo runs. The channel impulse response used for the simulation is depicted in figure 3. The additive noise was a complex valued white Gaussian noise. We evaluate the performance of the proposed scheme by computing the mean square error between the estimated and the actual values of the Doppler scaling factor. The data detection method is evaluated by means of the bit-error-rate (BER).

Fig. 4 depicts the mean value of the estimated Doppler scaling factor whereas the mean square error on the estimation of this factor is depicted in Fig. 5.

We can note the effectiveness of the Doppler estimation scheme. However, the performance is degraded when decreasing the SNR. The degradation is more accentuated when increasing the number of subcarriers in the first sub-block of the OFDM symbol. Indeed, by increasing 𝐾 𝑢 , the frequency spacing of the subcarriers is reduced. Therefore, the harmonic retrieval problem needs higher resolution and precision. Such a precision is difficult to obtain when the SNR decreases. Increasing 𝐾 𝑢 seems to be relevant only for high SNR values. This observation is directly related to the behaviour of HTLS in noisy cases. In Fig. 6, we depict the BER for three numbers 𝐾 𝑝 of pilots and two values for 𝐾 𝑢 . Increasing the number of pilot allows improving the BER.

From these simulations, we can conclude that increasing the number of pilots has a positive effect on the performance of the receiver while increasing the number of subcarriers 𝐾 𝑢 has a contrary effect.

VI. CONCLUSION

In this paper, we have presented a new scheme for both estimating the Doppler scaling factor and detecting the informative data. In the proposed scheme, each OFDM symbol is divided in two parts. The first one is shorter and carries out few data with few subcarriers whereas the second one contains both informative and pilot symbols. The first sub-block serves to estimate the Doppler scaling factor while the pilots in the second sub-block are used for estimating the equivalent channel. Both estimation methods are based on high resolution methods for solving harmonic retrieval problems in time and frequency domains respectively. The proposed scheme is particularly efficient for moderate to high SNR. Robustness to noise, for lower levels of SNR, and extension to the multi- user case will be investigated. In addition, effectiveness of the proposed approach using experimental data is to be considered in future works.

Fig. 1 .

 1 Fig. 1. Structure of the OFDM block

Fig. 3 .

 3 Fig. 3. Impulse response of the simulated channel

Fig. 4 .Fig. 5 .

 45 Fig. 4. Estimated value of the Doppler scaling factor.

Fig. 6 .

 6 Fig. 6. BER for different number of pilots and two numbers of subcarriers in the first sub-block (𝐾 𝑑 = 256)

ACKNOWLEDGMENT

This work was supported by the EU project FeedNetBack and the ANR project CONNECT.


Karim Khémiri
email: kemiri.karim@yahoo.fr

Fayçal Ben Hmida

José Ragot
email: jose.ragot@ensem.inpl-nancy.fr

Moncef Gossa

Observateur proportionnel multi-intégral pour les systèmes linéaires à entrées inconnues

Keywords: Diagnostic, estimation d'état, système linéaire, entrées inconnues, action intégrale, découplage

Ce travail s'intéresse à l'estimation d'état de systèmes linéaires à temps discret et en présence d'entrées inconnues en utilisant un observateur de type proportionnel multi-intégral sous une forme générale (P I p ). L'introduction de multiples actions intégrales dans l'observateur d'état, permet d'assurer une bonne précision de l'estimation même en présence des entrées inconnues décrites par des polynômes de degré p. Un exemple d'application numérique montre la validité de cette approche en utilisant un observateur doté de trois actions intégrales sur un système affecté par une entrée inconnue polynomiale.

I. Introduction

L'estimation d'état des systèmes a été et est largement étudiée dans la littérature en raison de l'importance considérable donnée aux procédure de surveillance de ces systèmes. En effet, l'élaboration d'une loi de commande ou la mise en place d'une stratégie de surveillance ou de diagnostic, nécessite, en général, la connaissance parfaite et complète de l'état d'un système. Cependant, en pratique,l'état d'un système n'est disponible que partiellement et les grandeurs accessibles pratiquement par mesure directe ne sont que les signaux d'entrée et de sortie. Une solution pour résoudre ce problème consiste à coupler au système un système auxiliaire, appelé estimateur ou observateur d'état capable de recouvrer cet état.

L'observateur fournit une estimation de l'état du système a partir de son modèle et des mesures de ses entrées et de ses sorties. Parmi la panoplie des observateurs utilisables, celui de luenberger [START_REF] Luenberger | An introduction to observers[END_REF] à gain proportionnel, est un observateur classique pour les systèmes linéaires. Cependant, les performance de l'observateur proportionnel se dégradent si la connaissance du modèle du système n'est pas parfaite ou sous l'effet des perturbations inconnues affectant l'état ou la sortie du système. Afin d'améliorer l'estimation malgré la présence de ces perturbations inconnues dans le système, l'observateur à gain Proportionnel-Intégral (P I) a fait l'objet de nombreux travaux. Le P I était une solution efficace pour résoudre les problèmes d'estimation d'état, de détection de défauts soit en temps continue [START_REF] Duan | Eigenstructure assignment design for proportional-integral observers : continuous time case[END_REF], [START_REF] Busawon | Disturbance attention using proportional integral observers[END_REF], [START_REF] Marx | Robust fault diagnosis for linear derscriptor systems using proportional integral observers[END_REF], [START_REF] Gao | Proportional multiple-intral observer design for descriptor systems with measurement output disturbances[END_REF] soit en temps discret [START_REF] Shafai | LTR Design of discrete-time proportional-integral observers[END_REF], [START_REF] Duan | Eigenstructure assignment design for proportional-integral observers : discrete-time case[END_REF], [START_REF] Chang | Applying discrete-time proportional-integral observers for state and disturbance estimations[END_REF]. En effet, un observateur proportionnel intégral permet d'avoir une estimation non biaisée de l'état malgré la présence des incertitudes ou des entrées inconnues [START_REF] Beal | Robust control system design with a proportional integral observer[END_REF], [START_REF] Zhiwei | Discrete-time proportional and integral observer and observer based controller for systems with both unknown input and output disturbances[END_REF], [START_REF] Weinman | Uncertain models and robust control[END_REF], [START_REF] Koenig | Unknown Input Proportional Multiple-Integral Observer Design for Linear Descriptor Systems : Application to State and Fault Estimation[END_REF].

Dans cette communication, on propose une version générale d'un observateur proportionnel intégral (P I p ) des systèmes linéaires à temps discret en présence des entrées inconnues. L'idée de cette approche est de procéder à des intégrations successives de l'erreur d'estimation de sortie pour estimer précisément les entrées inconnues puis de les utilisées pour corriger l'estimation de l'état et de la sortie du système. Une telle opération n'est possible que si on assure un découplage parfait entre l'état observé du système et les entrées inconnues.

Ce papier est organisé comme suit. Dans la deuxième section, on positionne le problème et on donne les hypothèses nécessaires à l'établissement de l'observateur. La section III traitera le problème de synthèse d'un observateur proportionnel multi-intégral. Des résultats de simulation sur un exemple numérique seront présentés dans la section IV. Enfin, on terminera dans la section V par une conclusion de ce travail.

II. Formulation du problème

On considère un système linéaire à temps discret décrit sous forme d'équation d'état : Dans la suite, on considère des observateurs de type Luenberger permettant de reconstruire l'état et les entrées inconnues du système.

x k+1 = Ax k + Bu k Dd k y k = Cx k + Ed k (1) où x ∈ R n représente l'état du système, y ∈ R m sa sor- tie, u ∈ R
L'estimation de l'état est effectuée de la façon suivante

   xk+1 = Ax k + Bu k + D dk + K ỹk ỹk = y k -ŷk ŷk = C xk + E dk (2) où K ∈ R r×m , E ∈ R m×q .
L'estimation des entrées inconnues est réalisée par l'observateur :

dk = ∆z k z k+1 = Λz k + Γỹ k (3) où z ∈ R pq , ∆ ∈ R q×pq , Λ ∈ R pq×pq
, et où la matrice Λ contient sur sa diagonale des blocs identité. L'observation est ainsi caractérisé par les matrices K et Γ dont il conviendra d'estimer les coefficients. Les développements qui suivent visent à expliciter les équations qui régissent l'évolution des erreurs d'estimation. Compte tenu de la structure de la matrice Λ, le vecteur z k est donc construit à partir des intégrations successives de l'erreur d'estimation ỹ de la sortie. Ce vecteur, ainsi que les différentes matrices introduites dans la structure de l'observateur, sont partitionnés sous la forme :

z k =     z 1,k z 2,k . . . z p,k     , Λ =       I 0 0 . . . 0 I I 0 . . . . . . 0 . . . I I 0 0 . . . 0 I I       (4) ∆ = 0 0 . . . I , Γ =       Γ 1 Γ 2 . . . Γ p-1 Γ p       (5)
Compte tenu de (3) et de l'expression de ∆, on note que :

dk = z p,k (6)
Ainsi, l'entrée inconnue est estimée uniquement à partir de la dernière variable d'intégration. Considérons la variable :

ε k = Hd k -z k (7)
avec

ε k =     ε 1,k ε 2,k . . . ε p,k     , H =       H 1 H 2 . . . H p-1 I       (8)
En particulier, la dernière composante de ε s'explicite :

ε p,k = d k -z p,k (9)
et en comparant ( 6) et [START_REF] Beal | Robust control system design with a proportional integral observer[END_REF], on vient de définir très simplement l'erreur d'estimation de l'entrée inconnue par :

dk = ε p,k = ∆ ε k (10)
Définissons les erreurs d'estimation d'état et de sortie respectivement par :

xk = x k -xk ỹk = C xk + E dk (11)
A partir des équations (1), ( 2), ( 7), ( 10), [START_REF] Weinman | Uncertain models and robust control[END_REF] et en utilisant l'opérateur d'avance q d'un pas d'échantillonnage, les expressions suivantes permettent d'obtenir la dynamique de l'erreur ε :

           ε k+1 = Hd k+1 -z k+1 = Hd k+1 -(Λz k + Γỹ k ) = Hqd k -Λ(Hd k -ε k ) -Γỹ k = Hqd k -Λ(Hd k -ε k ) -Γ(C xk + E dk ) = (qI -Λ)Hd k + (Λ -ΓE∆)ε k -ΓC xk (12) puis celle de l'état :    xk+1 = x k+1 -xk+1 = Ax k + Bu k + Dd k -(Ax k + Bu k + F dk + K ỹk ) = (A -KC)x k + (D -KE) dk (13)
Finalement, compte tenu des équations (10), ( 12) et ( 13), les deux erreurs d'estimation sont régies par une équation d'état sous la forme matricielle suivante :

ε k+1 xk+1 = Λ -ΓE∆ -ΓC (D -KE)∆ A -KC ε k xk + (qI -Λ)H 0 d k (14)
L'équation (14) traduit la dynamique d'évolution des erreurs d'estimation de l'état et de l'entrée inconnue en fonction de l'entrée inconnue d k .

On note aussi que les matrices K et Γ interviennent de façon linéaire dans cette équation. Il est donc tout à fait possible de régler les coefficients de ces deux matrices de façon à respecter la stabilité de l'équation (14), où la Dstabilité (technique de placement de pôles par exemple) et de minimiser l'influence de l'entrée inconnue sur l'erreur d'estimation (technique de type H ∞ par exemple).

En fait dans ce qui suit, on s'intéresse à un découplage exact de l'influence de l'entrée inconnue sur l'erreur d'estimation en précisant la classe d'entrée inconnue permettant ce découplage III. Synthèse de l'observateur P I p Au cours de cette section, on va présenter les différentes étapes de la synthèse d'un observateur proportionnel multiintégral. On commence, tout d'abord, par le cas le plus simple. Il s'agit d'un observateur P I puis on abordera le cas le plus général, c'est-à-dire celui d'un observateur P I p .

A. Observateur P I

Dans ce paragraphe, on s'intéresse à la synthèse d'un observateur ayant un seul intégrateur, c'est-à-dire caractérisé par :

Λ = I 0 I I , Γ = Γ 1 Γ 2 , ∆ = 0 I (15)
Si on choisit la matrice H (8) sous la forme :

H = (q -1)I I (16)
on obtient :

(qI -Λ)H = (q -1) 2 I 0 ( 17
)
Compte tenu de ce résultat, en vertu de l'équation (14), on peut écrire :

  ε 1,k+1 ε 2,k+1 xk+1   =   I -Γ 1 E Γ 1 C I I -Γ 2 E Γ 2 C 0 D -KE A -KC     ε 1,k ε 2,k xk   +   (q -1) 2 I 0 0   d k (18)
Ainsi, pour garantir un découplage total de l'influence de l'entrée inconnue d k sur les erreurs d'estimation, il faut respecter la condition :

(q -1) 2 d k = 0 (19)
Une solution de l'équation (19) est donnée pour une entrée inconnue de la forme :

d k = a 1 k + a 0 (20)
L'estimation de l'entrée inconnue peut donc s'obtenir à partir de l'erreur d'estimation de la sortie :

   z 1,k+1 = z 1,k + Γ 1 ỹk z 2,k+1 = z 1,k + z 2,k + Γ 2 ỹk dk = z 2,k (21)
Finalement, il reste à montrer que l'erreur d'estimation dk de l'entrée inconnue tend asymptotiquement vers zéro, c'est-à-dire dk → 0 quand k → ∞. Or, compte tenu de la contrainte (19) sur la nature de l'entrée inconnue, le système (18) est alors autonome et sa stabilité est assurée par un choix judicieux des gains K, Γ 1 et Γ 2 . Les erreurs d'estimation ε et x convergent donc vers 0, et compte tenu de [START_REF] Zhiwei | Discrete-time proportional and integral observer and observer based controller for systems with both unknown input and output disturbances[END_REF], cela garantit la convergence asymptotique de d vers 0. L'observateur proposé répond bien aux exigences de reconstruction de l'état et de l'entrée inconnue, les erreurs de reconstruction ayant une convergence garantie vers l'origine.

B. Observateur P I p

Dans ce paragraphe on traite le cas général, c'est-à-dire le cas d'un observateur P I p . La démarche est tout à fait semblable à celle décrite précédemment pour l'observateur P I, en prenant maintenant pour généraliser ( 16) :

H =     (q -1) p (q -1) p-1 • • • I     (22)
L'équation (14) s'applique toujours et ici avec :

(qI -Λ)H =     (q -I) p+1 0 • • • 0     (23)
En vertu de (14), pour avoir une erreur d'estimation découplée totalement des entrées inconnues il faut donc que :

(q -1) p+1 d k = 0 ( 24
)
ce qui correspond à la classe d'entrée suivante :

d k = a p k p + a p-1 k p-1 + • • • + a 1 k + a 0 ( 25
)
Pour cette classe d'entrées inconnues, la dynamique de l'erreur d'estimation se réduit à :

ε k+1 xk+1 = Λ -ΓE∆ -ΓC (D -KE)∆ A -KC ε k xk (26)
La matrice d'état de cet observateur peut aussi se mettre sous la forme :

Λ -ΓE∆ -ΓC (D -KE)∆ A -KC = Ā -K C (27) avec Ā = Λ 0 D∆ A , K = Γ K , C = E∆ C (28)
Ainsi, sous réserve de l'observabilité de la paire ( Ā, C), le réglage de l'observateur (c'est-à-dire le choix des gains K et Γ) peut être réalisé par placement de pôles. La condition d'observabilité de Hautus [START_REF] Hautus | Controllability and observability conditions of linear autonomous systems[END_REF] ici traduite par :

rang   sI -Λ 0 -D∆ sI -A E∆ C   = n + pq ∀s ∈ C (29)
est satisfaite si la paire(A, C) est observable, la matrice Λ étant par définition de plein rang. Enfin, l'estimation de l'entrée inconnue est réalisée à partir des équations d'état :

           xk+1 z k+1 = A -KC D∆ -ΓC Λ -ΓE∆ xk z k + B K 0 Γ u k y k dk = ∆z k (30)

IV. Exemple

On considère les matrices du système décrit par les équations (1) et (2) avec les valeurs numériques suivantes :

A = 0.3 0.1 0.1 0.8 , B = 2 -1.5 , D = 1.2 0.5 C = 1 -1 0 1 , E = 1 2
Dans cet exemple, on utilise un observateur ayant trois intégrateurs et comme entrée inconnue le signal de la forme suivante :

d k = a 3 k 3 + a 2 k 2 + a 1 k + a 0 avec a 3 = 0.0006, a 2 = -0.08, a 1 = 2 et a 0 = -35. La figure (
x 0 = 20 -50 , x0 = 0 0 , z 0 =     0 0 0 0     ,
D'après les résultats obtenus, on constate bien que l'observateur P I 3 permet d'obtenir une bonne estimation de l'état du système et de l'entrée inconnue, les écarts d'estimation costatés, au voisinage de l'origine, étant dus aux conditions initiales arbitrairement choisies.

La mise en oeuvre de l'observateur proposé nécessite l'ajustement de quelques paramètres. Outre le choix des gains de l'observateur liés aux pôles souhaités et qui doit être fait en fonction du niveau de bruit affectant les mesures de la sortie, l'utilisateur peut aussi modifier certains coefficients de la matrice Λ (4) qui intervient dans la définition de

V. Conclusion

Dans ce travail, on a présenté une forme générale d'observateur à entrée inconnue des systèmes linéaires à temps discret. L'approche était de concevoir un observateur proportionnel multi-intégral (P I p ) qui permet de garantir une bonne précision de l'estimation de l'état du système malgré la présence des entrées inconnues sous forme polynomiale de degré p. L'idée sur laquelle repose cet observateur consiste à introduire des intégrations successives sur l'erreur d'estimation de sortie pour obtenir une bonne estimation de l'entrée inconnue et à partir de laquelle on corrige l'estimation de l'état. L'observateur proposé est testé sur un exemple numérique pour un système affecté par une entrée inconnue sous forme de polynôme de degré 3. Les résultats de simulation montrent la bonne précision avec laquelle l'entrée inconnue et l'état du système sont estimés en utilisant un observateur ayant trois actions intégrales (P I 3 ).

Dans la suite de nos travaux, il semble intéressant de généraliser cette approche à la recherche d'une classe d'entrées plus générale en recherchant d'autres structure de l'observateur multi-integral.

Références

1 )Fig. 1 .

 11 Fig. 1. Entrée et sorties mesurées

Fig. 2 .Fig. 3 . 2 Fig. 4 .Fig. 6 .

 23246 Fig. 2. Etats vrai et estimés

Fig. 8 .

 8 Fig. 8. Entrée inconnue et son estimée