Quentin Gaudel
email: quentin.gaudel@laas.fr

Elodie Chanthery
email: elodie.chanthery@laas.fr

Pauline Ribot
email: pauline.ribot@laas.fr

Hybrid Particle Petri Nets for Systems Health Monitoring under Uncertainty

This paper focuses on how to treat uncertainty in health monitoring of hybrid systems by using a model-based method. The Hybrid Particle Petri Nets (HPPN) formalism is defined in the context of health monitoring to model hybrid systems and to generate diagnosers of such systems. The main advantage of this formalism is that it takes into account knowledgebased uncertainty and uncertainty in diagnosis process. The HPPN-based diagnoser deals with occurrences of unobservable discrete events (such as faults) and is robust to false observations. It also estimates the continuous state of the system by using particle filtering. Finally, HPPN can represent the system degradation that is often dealt with using probabilistic tools. A hybrid technique is thus used to group all this knowledge and to deduce the diagnosis results. The approach is demonstrated on a three-tank system. Experimental results are given, illustrating how different kinds of uncertainty are taken into account when using HPPN.

INTRODUCTION

Real systems have become so complex that it is often impossible for humans to capture and explain their behaviors as a whole, especially when they are exposed to failures. It is therefore necessary to develop tools that can support operator tasks but that also reduce the global costs due to unavailability and repair actions. An efficient health monitoring technique has to be adopted to detect, isolate (diagnosis) and predict faults (prognosis) leading to failures.

Recent industrial systems exhibit an increasing complexity of dynamics that are both continuous and discrete. It has become difficult to ignore the fact that most systems are hy- Quentin Gaudel et al. This is an open-access article distributed under the terms of the Creative Commons Attribution 3.0 United States License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. brid [START_REF] Henzinger | The theory of hybrid automata[END_REF]. In [START_REF] Chanthery | An integrated framework for diagnosis and prognosis of hybrid systems[END_REF], we extended the diagnosis approach proposed in [START_REF] Bayoudh | Hybrid systems diagnosis by coupling continuous and discrete event techniques[END_REF] in order to integrate diagnosis and prognosis for hybrid systems. The approach uses hybrid automata and stochastic models for the system degradation. Diagnosis is performed using a Discrete Event System (DES) approach.

The main drawback of this approach is that the DES-oriented diagnosis framework explodes in number of states and it does not seem to be the most suited for the incorporation of the prognosis task. Prognosis is indeed a probabilistic prediction process and is highly subject to uncertainty. The health monitoring task usually has to take into account the different sources of uncertainty, such as model approximation, partial observability of the system and measurement noise. Diagnosis should help the decision making process. In case of ambiguity in diagnosis results, the traditional diagnoser fails at providing relevant information. By taking all uncertainty sources into account, the method we propose succeeds in quantifying each diagnosis result.

Our previous works introduced a two-level framework called Hybrid Particle Petri Nets (HPPN). [START_REF] Gaudel | Hybrid systems diagnosis using modified particle Petri nets[END_REF] proposed to use the behavioral level of the HPPN (HPPN-BL) to both specify the system behavior, which is hybrid but also uncertain, and track the system current health state with a diagnoser representation. (Gaudel, Chanthery, & Ribot, 2014) extended this work by introducing the hybrid level of the HPPN (HPPN-HL). The purpose of the hybrid level is to represent system hybrid characteristics, such as degradation, which can depend on both the discrete and continuous parts of the system. Getting some information about the degradation of the system is a significant advantage for elaborating a more precise diagnosis and to perform prognosis. This paper recalls these two contributions and illustrates all the concepts step by step with a running example International Journal of Prognostics and Health Management, ISSN2153-2648, 2015 022 consisting in a three-tank system. The main contribution of the paper is to expose simulation results of the implemented HPPN-based health monitoring method. Experimental results are given, illustrating how different kinds of uncertainty are taken into account when using HPPN.

The paper is organized as follows. Section 2 presents related work on health monitoring based on Petri net formalism in the case of hybrid systems under uncertainty. Section 3 recalls the HPPN-BL formalism. Section 4 presents how HPPN-BL is applied to health monitoring and explains the generation of a behavioral diagnoser using the HPPN formalism. Section 5 presents the HPPN-HL formalism. Section 6 explains how HPPN-HL is applied to health monitoring and enrich the diagnosis results. Section 7 provides the results obtained by testing the HPPN-based health monitoring method on a threetank system, focusing on the uncertainty management. Some conclusions and future work are discussed in the final section.

RELATED WORK

The diagnoser approach was introduced by [START_REF] Sampath | Diagnosability of discrete-event systems[END_REF]. The diagnoser is basically a monitor that is able to process any possible observable event on the system. It consists in recording these observations and providing the set of possible faults whose occurrence is consistent with the observations. However, this approach is restricted to DES and does not manage uncertainty. Some approaches, such as [START_REF] Boubour | A Petri net approach to fault detection and diagnosis in distributed systems. part i: application to telecommunication networks, motivations, and modelling[END_REF] [START_REF] Genc | Distributed diagnosis of place-bordered Petri nets[END_REF] [START_REF] Soldani | On-board diagnosis system for intermittent fault: Application in automotive industry[END_REF] [START_REF] Cabasino | Diagnosability of discrete-event systems using labeled Petri nets[END_REF], extend the diagnoser to DES modelled by Petri nets. [START_REF] Genc | Distributed diagnosis of place-bordered Petri nets[END_REF] proposes a distributed version of the diagnoser in "Petri net diagnosers". In [START_REF] Cabasino | Diagnosability of discrete-event systems using labeled Petri nets[END_REF], the authors study the diagnosability of a system, inspired by the diagnosability approach for finite state automata proposed by [START_REF] Sampath | Diagnosability of discrete-event systems[END_REF]. They used the Modified Basis Reachability Graph in order to build the reachability diagnoser that is represented as a graph. However, none of these approaches take into account continuous aspects, nor do they consider uncertainties in the system. [START_REF] Soldani | On-board diagnosis system for intermittent fault: Application in automotive industry[END_REF] proposes an approach for the localization of intermittent faults. This article proposes some clues for dealing with partial observability in the discrete event framework. It proposes a method based on Petri net modeling the normal functioning of the system observable behavior. The detection step consists in comparing the flow of observable events emitted by the monitored system to the flow predicted by the model. A localization mechanism, based on the diagnoser approach, points out the set of events potentially responsible for the faults. Some works [START_REF] Koutsoukos | Monitoring and diagnosis of hybrid systems using particle filtering methods[END_REF], [START_REF] Ru | Fault diagnosis in discrete event systems modeled by partially observed Petri nets[END_REF], (Basile, Chiacchio, & Tommasi, 2009), [START_REF] Jianxiong | Performability analysis of avionics system with multilayer hm/fm using stochastic Petri nets[END_REF] try to take into account uncertainty. [START_REF] Koutsoukos | Monitoring and diagnosis of hybrid systems using particle filtering methods[END_REF] uses a particle filtering technique to estimate the state of a hybrid system modeled as a hybrid automaton. Uncertainty related to discrete events is not taken into account and the system degradation is not considered. [START_REF] Ru | Fault diagnosis in discrete event systems modeled by partially observed Petri nets[END_REF] uses partially observed Petri nets. Partially observed Petri nets are transformed into an equivalent labelled Petri net and an online monitor is built to diagnose faults and provide beliefs (degrees of confidence) regarding the occurrences of faults. However, this approach is limited because it only takes into account the uncertainties in the diagnosis results, not about the model or the event observations. (Basile et al., 2009) proposes to reduce the explosion of the state space by introducing generalized markings (negative tokens) to take into account uncertainty about the firing of transitions. [START_REF] Jianxiong | Performability analysis of avionics system with multilayer hm/fm using stochastic Petri nets[END_REF] uses the stochastic Petri nets to build a formal model of each component of integrated modular avionics architecture. However, for all these approaches, no continuous aspect in the model is taken into account.

To get a more compact representation and to capture all uncertainties related to the system, the observations and the diagnosis results, we propose to consider the Modified Particle Petri Nets (MPPN) formalism defined in (Zouaghi, Alexopoulos, Wagner, & Badreddin, 2011a). MPPN are an extension of particle Petri nets [START_REF] Lesire | Particle Petri nets for aircraft procedure monitoring under uncertainty[END_REF] that combine a discrete event model (Petri net) with a continuous model (differential equations). The main advantage of MPPN is that uncertainties and hybrid dynamics are taken into account. A particle filter is used to integrate probabilities in the continuous state estimation process. In (Zouaghi et al., 2011a), the application is based on the mission monitoring. It does not consider different health states for the system. There is no matching with the diagnoser approach and the problem of ambiguous state tracking is not considered. In [START_REF] Zouaghi | Probabilistic online-generated monitoring models for mobile robot navigation using modified Petri net[END_REF], the authors propose a design approach for the specification and the realization of dynamic system monitoring. They present the integration of system design and monitoring into a unified framework for the reuse of component descriptions and the automatic monitoring component generation. They automatically convert MPPN into an XML description and the monitoring parameters are added to the file. However, this observer is not formally defined, and no equivalence with a diagnoser is given. In addition, there is no mention of the health state notion for the system. This paper proposes to use HPPN for health monitoring. The HPPN-BL is based on the MPPN formalism and takes into account the hybrid dynamics and the inherent uncertainty of real systems. Then the work formally specifies a diagnoser object for computing online diagnosis. This paper also introduces the HPPN-HL that captures the system hybrid characteristics.

BEHAVIORAL LEVEL OF HYBRID PARTICLE PETRI NETS

This section recalls the behavioral level of the Hybrid Particle Petri Nets formalism (HPPN-BL). This formalism is directly inspired from (Zouaghi et al., 2011a) and adapted to fit diagnosis requirements. First the model structure is detailed, then its online use is presented.

Throughout the paper, a running example of the three-tank system, described in Figure 1, is used to illustrate the definitions and concepts, and the proposed extensions to diagnosis.

Figure 1. Three-tank system description.

The tanks are configured in a series circuit. The water comes from Pump 1 into tank T 1 . Flow Q 1 (t) delivered by the pump is supposed to be constant. The tank T 2 empties with flow Q 20 (t). The available measurements at time t are the water level in tank T 1 denoted h 1 (t) and the total mass of water in the three-tank system denoted W (t). Valves v 13 and v 32 allow the flow to transfer between tanks. They are controlled by discrete control inputs open v13 , close v13 , open v32 and close v32 . Fault events f 1 , f 2 and f 3 model leaks that may occur in tanks T 1 , T 2 and T 3 . The leak f 1 is three times larger than f 2 and f 3 . f 4 and f 5 are fault events that may occur on the valves. The valve v 13 (respectively v 32 ) may become stuck closed f 4 (respectively f 5 ). The goal of the system is to maintain the water level in tank T 2 greater than a minimum value h 2min . The leak in tank T 1 is considered too large and therefore leads to system failure when f 1 occurs because the system is not able to achieve the goal anymore. Leaks in tanks T 2 and T 3 are separately not large enough to prevent the goal achievement, but the occurrences of the two leaks lead to system failure. Both f 4 and f 5 prevent the water delivered by the pump to reach the tank T 2 and then lead to system failures. It is then supposed that the system is in a failure mode either if f 1 or f 4 or f 5 occurs, or if f 2 and f 3 occur.

Definition

The HPPN formalism is an extension of Petri nets. A Petri net is a directed bipartite graph, in which a node can be either a place or a transition. The directed arcs cannot link two places or two transitions. Places may contain tokens. The distribution of tokens over the places is called the marking of the net. A transition may be fired if it is enabled (ie. there is enough tokens in its input places). The firing of a transition consumes the required tokens in its input places and creates tokens in its output places.

The HPPN-BL is defined as a tuple < P, T, P re, P ost, X, C, γ, Ω, M 0 > where:

• P is the set of places, partitioned into numerical places P N and symbolic places P S . • T is the set of transitions (numerical T N , symbolic T S and mixed T M ). • P re and P ost are the incidence matrices of the net, of dimension |P | × |T |. • X ⊂ n is the state space of the numerical state vector.

• C is the set of dynamic equation sets of the system associated with numerical places, representing continuous state evolution. • γ(p S ) is the application that associates tokens with each symbolic place p S ∈ P S . • Ω is the set of conditions (numerical Ω N and symbolic Ω S ) associated with transitions. • M 0 is the initial marking of the net.

The marking of the net is composed of tokens, that can be numerical tokens (particles) or symbolic tokens (configurations).

A numerical place p N ∈ P N is associated with a set of dynamic equations representing the continuous behavior of the system. Numerical places thus model system continuous dynamics. Numerical places are marked by a set of particles

π i k = [x i k , w i k ] with i ∈ {1, ..., |M N k |}
where M N k is the set of all the particles in the net at time k. Particles are defined by their corresponding numerical state vector x i k ∈ X and their weight w i k ∈ [0, 1] at time k. The set of particles represents a distribution over the value of the numerical state vector.

Symbolic places model the discrete states of the system. A symbolic place p S ∈ P S is marked by configurations δ j k with j ∈ {1, ..., |M S k |} where M S k is the set of configurations in the net at time k. The set of configurations represents all the possible current modes of the system.

The marking M k of the HPPN-BL at time k consists of both kinds of tokens:

M k = {M S k , M N k }. ( 1
)
Example 1 For the three-tank system, there exist 4 nominal discrete states, denoted nom 1 , nom 2 , nom 3 , nom 4 , representing the conditions on the valves defined in Table 1. A fault event f j , 1 ≤ j ≤ 5 may occur in any nominal mode and leads to anticipated fault mode 1f j , 2f j , 3f j , 4f j , respectively, so that 16 one-fault modes exist. For example, if f 2 occurs in nominal mode nom 3 , the system evolves in mode 3f 2 . Multiple faults are considered and faults are assumed to be independent, that is to say that xf i f j is the same mode as xf j f i . For the three-tank system, 20 two-fault modes are determined. Each discrete state is represented by a symbolic place. For example the set P S nom = {nom 1 , nom 2 , nom 3 , nom 4 } represents the nominal discrete states of the system. Each nominal discrete state is associated with a set of dynamic equations representing the different continuous behaviors of the system. For some cases, two or more discrete states have the same dynamic equations, so it is not necessary to define different continuous behaviors for all these discrete states. Each identified continuous dynamic is represented by a numerical place, for example the set of nominal behaviors

P N nom = {D 1 , D 2 , D 3 , D 4 }
where D 1 , D 2 , D 3 , D 4 are the system dynamics defined in Table 1, with S 1 , S 2 , S 3 the tank sections and K ij real coefficients. All continuous dynamics of the three-tank system are provided in the appendix.

Firing Rules

A transition models a change in the continuous dynamics and/or a change of system mode. A symbolic transition is conditioned by an observable discrete event. A numerical transition is conditioned by a set of constraints on continuous observable variables. Finally, a mixed transition is conditioned by an observable discrete event and a set of constraints on continuous observable variables.

Let P re(t j ) be the set of input places of a transition t j ∈ T :

P re(t j ) = {p i |P re(i, j) = 0, i ∈ {1, ..., |P |}}. (2)
P ost(t j ) is the set of its output places:

P ost(t j ) = {p i |P ost(i, j) = 0, i ∈ {1, ..., |P |}}.
(3)

∀p i ∈ P , M k (p i ) is the set of tokens in p i at time k and m k (p i ) = |M k (p i )|
is the number of tokens in p i at time k.

Definition 1 A numerical or a symbolic transition t j is fireenabled at time k if:

∀p i ∈ P re(t j ), m k (p i ) ≥ P re(i, j). (4)
A numerical transition t N j ∈ T N is associated with numerical conditions Ω N (t N j ), where Ω N (t N j )(π) = 1 if the particle satisfies the conditions. For example, if π = [x, w] follows the constraint equation c and b is a trigger value, numerical conditions can be defined as Ω N (t N j )(π) = (c(x) > b). Ω S (t S j ) = (occ(e)) are the symbolic conditions assigned to a symbolic transition t S j ∈ T S . occ(e) is a boolean indicator of the occurrence of the discrete event e: occ(e) = 1 if e occurs. Then, a configuration δ satisfies symbolic conditions Ω S (t S j )

when Ω S (t S j )(δ) = 1, i.e. when the event e occurs. Firing rules of a transition t j ∈ T use the following set of variables over their domains of definition. It is assumed that: p N ∈ (P re(t j ) ∩ P N ), p N ∈ (P ost(t j ) ∩ P N ), p S ∈ (P re(t j ) ∩ P S ), p S ∈ (P ost(t j ) ∩ P S ).

If t j ∈ (T N ∪ T M ), let S N k (p N
) be the set of particles in p N that satisfy the conditions Ω N (t j ) at time k:

S N k (p N ) ⊆ M N k (p N ) with π ∈ S N k (p N ) if Ω N (t j )(π) = 1 at time k.
The numerical firing uses the concept of classical firing with the particles satisfying the numerical conditions and the concept of pseudo-firing (ie. duplication) for the configurations. The duplication of configurations represents uncertainty about the occurrence of an unobservable discrete event.

Definition 2 The firing of a fire-enabled numerical transition t N j ∈ T N at time k is defined by:

M N k+1 (p N ) = M N k (p N )\S N k (p N ) M N k+1 (p N ) = M N k (p N ) ∪ S N k (p N ), (5)
M S k+1 (p S ) = M S k (p S ) M S k+1 (p S ) = M S k (p S ) ∪ M S k (p S ). (6)
An example of a numerical firing at time k is illustrated in Figure 2(a) adapted from (Zouaghi et al., 2011a). In this example, t N 1 has only numerical conditions because it is a numerical transition. Particle π 3 satisfies the numerical conditions Ω N (t N 1 ) and thus is moved to p N 4 . The configuration in place p S 1 is duplicated in p S 2 . The symbolic firing uses the concept of pseudo-firing for particles and configurations. The pseudo-firing of all the tokens models uncertainty about the non-occurrence of a discrete Table 1. Three-tank system example: state equations for nominal discrete states.

Ω N (t N 1 ) Ω S (t S 2 ) Ω S (t M 3 ) Ω N (t M 3 ) Ω N (t N 1 ) Ω S (t S 2 ) Ω S (t M 3 ) Ω N (t M 3 ) π 1 π 2 π 3 π 1 π 2 π 3 π 4 π 5 π 6 π 4 π 5 π 6 π 4 π 5 π 6 π 7 π 8 π 9 π 7 π 8 π 9 k k + 1 (a) (b) (c)

Valve state

State equations

nom 1 v 13 = open v 32 = open D 1      ḣ1 (t) = 1 S1 (Q 1 (t) -K 13 |h 1 (t) -h 3 (t)|) ḣ2 (t) = 1 S2 (K 32 |h 3 (t) -h 2 (t)| -Q 20 (t)) ḣ3 (t) = 1 S3 (K 13 |h 1 (t) -h 3 (t)| -K 32 |h 3 (t) -h 2 (t)|) nom 2 v 13 = closed v 32 = open D 2      ḣ1 (t) = 1 S1 Q 1 (t) ḣ2 (t) = 1 S2 (K 32 |h 3 (t) -h 2 (t)| -Q 20 (t)) ḣ3 (t) = -K32 S3 |h 3 (t) -h 2 (t)| nom 3 v 13 = closed v 32 = closed D 3      ḣ1 (t) = 1 S1 Q 1 (t) ḣ2 (t) = -Q20(t) S2 ḣ3 (t) = K13 S3 |h 1 (t) -h 3 (t)| nom 4 v 13 = open v 32 = closed D 4      ḣ1 (t) = 1 S1 (Q 1 (t) -K 13 |h 1 (t) -h 3 (t)|) ḣ2 (t) = Q20(t) S2 ḣ3 (t) = K13 S3 |h 1 (t) -h 3 (t)| event.
Definition 3 The firing of a fire-enabled symbolic transition t S j ∈ T S at time k is defined by:

M N k+1 (p N ) = M N k (p N ) M N k+1 (p N ) = M N k (p N ) ∪ M N k (p N ), (7)
M S k+1 (p S ) = M S k (p S ) M S k+1 (p S ) = M S k (p S ) ∪ M S k (p S ). (8)
Figure 2(b) illustrates an example of a symbolic firing. The symbolic transition t S 2 has only symbolic conditions and is fire-enabled. No configuration satisfies the symbolic conditions Ω S (t S 2 ), however, all the tokens are duplicated. Mixed transitions (also called hybrid transitions in (Zouaghi et al., 2011a)) model the interactions between discrete events and system continuous dynamics. A mixed transition merges a symbolic transition with a numerical transition to consider the correlation between discrete observations and continuous observations. A mixed transition t M j ∈ T M is then associated with both numerical conditions Ω N (t M j ) and symbolic conditions Ω S (t M j ).

Definition 4 A mixed transition t M j ∈ T M is fire-enabled at time k if ∀p i ∈ P re(t M j ): m k (p S i ) ≥ P re(i, j), if p S i ∈ P re(t M j ) ∩ P S m k (p N i ) ≥ 0, if p N i ∈ P re(t M j ) ∩ P N . (9)
The mixed firing uses the concept of classical firing with the particles satisfying the numerical conditions and the concept of pseudo-firing with the configurations. The pseudo-firing of configurations models uncertainty about the occurrence of an observable discrete event that is supported by a change of continuous dynamics.

Definition 5 The firing of a mixed transition t M j ∈ T M at time k is defined by:

M N k+1 (p N ) = M N k (p N )\S N k (p N ) M N k+1 (p N ) = M N k (p N ) ∪ S N k (p N ), (10)
M S k+1 (p S ) = M S k (p S ) M S k+1 (p S ) = M S k (p S ) ∪ M S k (p S ). (11)
An example of a mixed firing is illustrated in Figure 2(c). t M 3 is a mixed transition therefore it has symbolic conditions and numerical conditions. The configuration in place p S 9 is duplicated. Regarding the numerical part, particles π 8 and π 9 satisfy Ω N (t M

3 ) so they are moved to p N 12 . Furthermore, π 7 stays in place p N 11 because it does not satisfy Ω N (t M 3 ).

State Estimation

HPPN-BL hybrid estimation is based on the marking evolution and on the particle filtering: a prediction step and a correction step are performed on the tokens.

For the sake of clarity, in this paper, it is assumed that a hybrid state is represented by a couple (p S i , p N j ). The initial marking of the HPPN-BL is

M 0 = {M S 0 , M N 0 } and the estimated marking at time k is Mk = { M S k , M N k } where Mk = Mk|k . The observations start at time k = 1, O 1 = (O S 1 , O N 1 )
where O S and O N respectively represent the observations corresponding to the symbolic part and the numerical part.

(1) The prediction step is based on the evolution of the marking of the HPPN-BL and on the estimation of the parti-cle values. It aims at determining all possible next states of the system Mk+1|k = { M S k+1|k , M N k+1|k }. Noise is added during the particle values update to take into account uncertainty about the dynamic equations and thus about the continuous system model.

(2) The correction step is based on the update of the prediction according to new observations on the system. Finally, in order to update the complete predicted marking Mk+1|k , a decision making method is required. The result of the whole state estimation process is the estimated marking at time k + 1, Mk+1|k+1 = { M S k+1|k+1 , M N k+1|k+1 }. The main advantage provided by HPPN is the way they manage uncertainty. This article focuses on a way to use them in a context of health monitoring.

APPLICATION TO BEHAVIORAL MONITORING

Diagnosis is used to identify the possible causes of failures by reasoning on system observations. Diagnosis reasoning consists in detecting and isolating faults that may cause a system failure. Results of the diagnosis function lead to the current health state of the system. We are interested in representing changes in the system dynamics when one or several anticipated faults occur. We defined a health mode as a discrete health state coupled to a continuous dynamics [START_REF] Gaudel | Hybrid systems diagnosis using modified particle Petri nets[END_REF]. As long as the system does not encounter any fault, it is in a nominal mode. Tracked faults are assumed to be permanent, i.e. once a fault happens, the system moves from a nominal mode to a degraded mode or faulty mode. Without repair, the system evolution is unidirectional as illustrated in Figure 3 and the system ends in a failure mode in which it is not operational anymore.

Example 2 The evolution of the three-tank system is illustrated in Figure 4. There are 8 degraded modes defined by the occurrence of fault events f 2 or f 3 and 28 failure modes defined either by the occurrence of f 1 or f 4 or f 5 or by the occurrence of f 2 and f 3 . 16 one-fault modes and the 20 twofault modes are identified.

Behavior Modeling

With the definition of the HPPN-BL, it is possible to model a hybrid system behavior in a health monitoring context. Numerical places can represent the system continuous dynamics, and symbolic places can represent the different discrete health states of the system. Thus, a hybrid state (p S i , p N j ) will represent a health mode of the system. Let Q = {q m } denote the set of health modes of the system:

q m = (p S i , p N j ) ∈ Q if ∃t l ∈ T, (p S i , p N j ) ∈ (P ost(t l )) 2 .
(12) Symbolic conditions are used to model the occurrence of observable discrete events belonging to Σ o and unobservable discrete events belonging to Σ uo (faults, mission events, interaction with the environment, ...). Σ = Σ o ∪ Σ uo is defined as the set of discrete events of the system. Numerical conditions model an observable change of continuous dynamics. System continuous dynamics are represented by differential equations.

A generic example of a system behavioral model is described in Figure 5. In this example, the system has three continuous behaviors represented by p N 5 , p N 6 , p N 7 and four health states p S 1 , p S 2 , p S 3 and p S 4 . Using Equation ( 12), five health modes are distinguishable. Health modes q 1 = (p S 1 , p N 5 ) and q 2 = (p S 1 , p N 6 ) are two nominal modes switching from one to the other when sym-bolic conditions Ω S (t S 1 ) = (occ(e 1 )) or symbolic conditions Ω S (t S

2 ) = (occ(e 2 )) are satisfied. Symbolic transitions t S 1 and t S 2 represent the occurrence of observable events e 1 ∈ Σ o and e 2 ∈ Σ o supporting a change of continuous dynamics between p N 5 and p N 6 , respectively. Health modes q 3 = (p S 2 , p N 6 ) and q 4 = (p S 3 , p N 6 ) are two degraded modes reachable from health mode q 1 by satisfying the symbolic conditions Ω S (t S

3 ) = (occ(f 1 )) and Ω S (t S 4 ) = (occ(f 2 )), respectively. Symbolic transitions t S 3 and t S 4 represent the occurrence of two unobservable fault events f 1 ∈ Σ uo and f 2 ∈ Σ uo , respectively. Finally, q 5 = (p S 4 , p N 7 ) is a failure mode in which both events f 1 and f 2 occurred and that is reachable from the two degraded modes.

Ω N (t S 5 ) = (occ(f 1 )) represent the occurrence of f 1 and Ω S (t S 6 ) = (occ(f 2 )) rep- resent the occurrence of f 2 . p S 1 p S 2 p S 3 p S 4 p N 5 p N 6 p N 7 Ω S (t S 1 ) Ω S (t S 2 ) Ω S (t S 3 ) Ω S (t S 5 ) Ω S (t S 4 ) Ω S (t S 6 )
Figure 5. Example of system behavioral model using the HPPN-BL.

Example 3 The behavioral model of the three-tank system is limited to only two nominal modes and three failure modes for illustration purposes in Figure 6. Four dynamic equation sets are associated with D 1 , D 2 , D 1f1 and D 2f1 and five discrete health states are represented by nom 1 , nom 2 , 12f 4 , 1f 1 and 2f 1 . Five health modes are defined. Health modes q 1 = (nom 1 , D 1 ) and q 2 = (nom 2 , D 2 ) are nominal modes in which the system switches from one to the other when the condition occ(close v13 ) or occ(open v13 ) is satisfied. Notations are simplified in the illustration with only the discrete event shown for the sake of readability. Three failure modes q 3 = (12f 4 , D 2 ), q 4 = (1f 1 , D 1f1 ), q 5 = (2f 1 , D 2f1 ) can be reached from nominal modes q 1 or q 2 by satisfying conditions occ(f 1 ) or occ(f 4 ) (simplified in f 1 and f 4 for illustration purposes).

Figure 6. Three-tank partial behavioral model using the HPPN-BL.

The next section presents the methodology to build a state tracker object called a diagnoser from the behavioral system model.

Behavioral Diagnosis

In health monitoring context, diagnosis aims at tracking the system current health state. A common way in DES framework is to generate a diagnoser of the system from its model [START_REF] Sampath | Diagnosability of discrete-event systems[END_REF]. A diagnoser is basically a monitor that is able to process any possible observable event on the system. It consists in recording these observations and providing the set of possible faults whose occurrence is consistent with these observations. Concerning hybrid systems, one approach is to build a hybrid diagnoser [START_REF] Bayoudh | Hybrid systems diagnosis by coupling continuous and discrete event techniques[END_REF]) from a hybrid automaton. The idea is to abstract the continuous part of the system to work with a discrete view of the system. This abstraction is done by using consistency tests, which take the form of a set of residuals. The diagnoser method is then directly applied to the resulting discrete event system. In previous work [START_REF] Chanthery | An integrated framework for diagnosis and prognosis of hybrid systems[END_REF], we extended this approach in order to integrate diagnosis and prognosis for hybrid systems. The main drawback of this approach is that the DES oriented diagnosis framework is not the most suited to incorporate the highly probabilistic prognosis task. Using the HPPN-BL, we succeeded in capturing knowledge-based and observation-based uncertainty. Consequently, we proposed a new diagnoser built from a HPPN-BL (Gaudel, Chanthery, nite state machine. Although this theoretical object is very interesting for studying properties of a system, such as diagnosability or controllability, it is absolutely not suited to embedded systems, because the diagnoser state number explodes for large models. Consequently, we choose to build a diagnoser based on a HPPN-BL model for the following reasons:

• it is not necessary to transform the specification of the system behavior another formalism, • the HPPN model captures uncertainty, so the integration with prognosis becomes more natural, • this representation is more compact than a hybrid automaton description, so the problem of embeddability of the diagnoser is reduced.

The diagnoser takes as inputs the HPPN-BL specifying the system behavior and the set of online observations on the system. The output of the diagnoser is an estimation of the system health state that takes the form of a marking of the diagnoser

∆ k = Mk = { M S k , M N k }.

Diagnoser Generation Based on HPPN-BL

Let us suppose that the system behavioral model is a HPPN-BL given by a tuple < P, T, P re, P ost, X, F, γ, Ω, M 0 > as defined in Section 3.1.

The set of places of the diagnoser remains the same as the one of the system behavioral model. Concerning the transitions, two aspects have to be taken into account.

First, it is necessary to follow the system continuous dynamics with information resulting from the observed variables. Two sources of information can be taken into account:

• It is possible to generate a set of residuals from the set of differential equations C of the model. The residual generation has been widely studied in diagnosis studies. Fundamental results can be found in [START_REF] Maquin | Generation of analytical redundancy relations for fdi purposes[END_REF]. In the case where the system equations are linear, residuals can be generated by computing a set of analytical redundancy relations (ARR) with the parity space approach [START_REF] Staroswiecki | Analytical redundancy relations for fault detection and isolation in algebraic dynamic systems[END_REF]. The parity space approach has been extended to multi-mode systems in [START_REF] Cocquempot | Fault detection and isolation for hybrid systems using structured parity residuals[END_REF]. In our case, we consider that it is possible to generate a residual r i (or to simply have one by expert knowledge) for some numerical places p N i . Then, numerical conditions Ω N (t l ) are associated with a transition t l linking two numerical places p N j and p N i and carry a satisfaction test r i , with (i, j) ∈ {1, ..., |P N |} 2 and l ∈ {1, ..., |T |}. However, for some other places, only discrete information is available. The HPPN framework encompasses these characteristics and the diagnoser generation is adapted. If a residual r i is available, this means that Ω N (t l )(π) is satisfied when r i is satisfied for π.

Residuals allow for checking the consistency of observations with the model constraints. Since residuals are computed from observable continuous variables, they can be evaluated online with the incoming observations given by the sensors.

• The numerical correction process is used to update the prediction, by comparing the predicted particle values to observations of some continuous variables. This second way to check the consistency of the observed system behavior with the predicted one is implicit and does not appear in the diagnoser.

Secondly, because the diagnoser only captures the observable behavior of the system, a condition representing the occurrence of an unobservable discrete events would never be satisfied. The management of unobservable discrete event is done following these rules:

R1. For any mixed transition t M j ∈ T M with symbolic conditions Ω S (t M j ) covering the occurrence of some unobservable events and some observable events, remove the symbolic part covering the occurrence of unobservable events, because these conditions would never be satisfied. The mixed transition t M j remains a mixed transition. R2. For any mixed transition t M j ∈ T M with symbolic conditions Ω S (t M j ) covering only the occurrence of unobservable events, remove the symbolic part of the transition. The mixed transition t M j is transformed in a numerical transitions t N j ∈ T N . R3. For any symbolic transition t S j ∈ T S with symbolic conditions Ω S (t S j ) covering the occurrence of some unobservable events and some observable events, remove the symbolic part covering the occurrence of unobservable events. The transition t S j remains a symbolic transition. R4. For any symbolic transition t S j ∈ T S with symbolic conditions Ω S (t S j ) covering only the occurrence of some unobservable events, replace symbolic conditions with a test function always satisfied (true() function). The transition t S j remains a symbolic transition. Concerning the observable discrete part of the system, occurrences of observable discrete events will be used as symbolic conditions.

Once the system behavioral model is defined and all numerical conditions are computed from the residual generation, the corresponding diagnoser can be generated with the following steps:

Step 1: Add the available numerical conditions Ω N (t S j ) to symbolic transition t S j ∈ T S , with j ∈ {1, ..., |T |}, if they exist. As a result, the symbolic transition t S j will be upgraded into a mixed transition t M j ∈ T M .

Step 2: Manage the unobservable events with rules R1 to R4.

Ambiguity:

The challenge of diagnosis is to have the ability to diagnose anticipated but unobservable faults in the system. In this context, modeling unobservable events can lead to ambiguity in the diagnoser. The occurrence of faults that cannot be distinguishable from the system observations will lead to ambiguous health states for the diagnoser. Therefore, a third step is needed during the diagnoser generation to track ambiguity. To do so, it is necessary to define a rule to merge two transitions of the same type. Two numerical transitions are mergeable if they are conditioned by the same change of dynamics and if they share the same symbolic places in their sets of inputs places.

Definition 6 (Mergeable numerical transitions)

Two numerical transitions (t N i , t N j ) ∈ (T N ) 2 , with (i, j) ∈ {1, ..., |T N |} 2 and i = j are mergeable if:

(P re(t N i ) = P re(t N j )) ∧ (P ost(t N i )∩P N ∩P ost(t N j ) = ∅). (13)
Note that condition (13) implies that the two transitions share the same numerical condition:

Ω N (t N i ) = Ω N (t N j ).
Definition 7 (Mergeable symbolic transitions) Two symbolic transitions (t S i , t S j ) ∈ (T S ) 2 , with (i, j) ∈ {1, ..., |T S |} 2 and i = j are mergeable if:

(P re(t S i ) = P re(t S j )) ∧ (P ost(t S i ) ∩ P S ∩ P ost(t S j ) = ∅). ( 14
)
Step 3: Merge all mergeable transitions while there are at least two mergeable transitions using the following definitions.

Definition 8 (Merging of two numerical transitions)

The merging of two mergeable numerical transitions (t N i , t N j ) ∈ (T N ) 2 , with (i, j) ∈ {1, ..., |T N |} 2 and i = j is defined by two steps as follows:

(1) Creation of a new transition t N ij characterized by:

   P re(t N ij ) = P re(t N i ) P ost(t N ij ) = P ost(t N i ) ∪ P ost(t N j ) Ω N (t N ij ) = Ω N (t N i ), (15)
(2) Addition of t N ij and deletion of t N i and t N j in T :

T = (T \{t N i , t N j }) ∪ {t N ij }. ( 16
)
Definition 9 (Merging of two symbolic transitions)

The merging of two mergeable symbolic transitions (t S i , t S j ) ∈ (T S ) 2 , with (i, j) ∈ {1, ..., |T S |} 2 and i = j is defined by two steps as follows:

(1) Creation of a new transition t S ij characterized by:

   P re(t S ij ) = P re(t S i ) P ost(t S ij ) = P ost(t S i ) ∪ P ost(t S j ) Ω S (t S ij ) = Ω S (t S i ), (17)
(2) Addition of t S ij and deletion of t S i and t S j in T :

T = (T \{t S i , t S j }) ∪ {t S ij }. ( 18
)
The resulting diagnoser of the model given in Figure 5 is presented in Figure 7.

p S 1 p S 2 p S 3 p S 4 p N 5 p N 6 p N 7 Ω S (t M 1 ) Ω N (t M 1 ) Ω S (t M 2 ) Ω N (t M 2 ) Ω N (t N 3 ) Ω N (t N 5 ) Ω N (t N 6 )
Figure 7. Example of system diagnoser using the HPPN-BL.

In Figure 7, Step 1 generates numerical conditions Ω N to every transitions. All transitions are indeed supported by a change of dynamics that can be observed with the generation of residuals. All transitions are then upgraded into mixed transitions. As there are unobservable events, symbolic conditions associated with the occurrence of f 1 and f 2 are removed from the diagnoser model during Step 2, transforming t 3 , t 4 , t 5 and t 6 into numerical transitions. Finally, because transitions t 3 and t 4 are generating a change of dynamics from p N 1 to p N 2 , they are merged into one single numerical transition t N 3 .

Example 4 For the three-tank system example illustrated in Figure 8, transitions with the symbolic conditions closev 13 and openv 13 remain symbolic. Symbolic conditions f 1 and f 4 are deleted, as they are unobservable.

Figure 8. Three-tank system example diagnoser using the HPPN-BL.

Behavioral Diagnosis Result

The diagnosis result is given at each clock tick from the diagnoser state. By using the HPPN-BL and the state estimation process based on particle filtering described in Section 3.3, the diagnosis ∆ k at time k is the distribution of health mode beliefs, which depends on particle values and weights and is deduced from the marking of the diagnoser at time k:

∆ k = Mk = { M S k , M N k }. ( 19
)
The marking Mk indicates the belief on the fault occurrences. It gives the same information as a classical diagnoser in terms of fault occurrences, with the same ambiguity. The difference is that in a classical diagnoser, every possible diagnosis has the same belief degree. With a HPPN-BL-based diagnoser, the ambiguity is valued by particle weights.

As a consequence, using diagnosis for health management becomes easier. In the case of classical diagnoser, it is indeed very difficult to "choose" a system belief state in case of decision making. In the case of a HPPN-BL-based diagnoser, each possible state of the system is valued, so it is easy to evaluate the most probable state at each clock tick. Another advantage is that several types of uncertainty are taken into account.

1. Configuration pseudo-firing during numerical transition firing may represent uncertainty about the occurrence of an unobservable discrete event, especially a fault event.

2. Configuration and particle pseudo-firing during symbolic transition firing may represent uncertainty about the nonoccurrence of an observed discrete event, i.e. a false ob-servation.

Configuration pseudo-firing during mixed transition fir-

ing may represent uncertainty about the occurrence of an unobservable discrete event, supported by a change of continuous dynamics. 4. The noise added on particle values during the prediction step models uncertainty about system dynamic equations and continuous observations.

HYBRID LEVEL OF HYBRID PARTICLE PETRI NETS

The previous part describes a way to use the HPPN-BL to monitor the system health state based on its behavioral model. It could be interesting to look at a higher level of representation to illustrate a different level of dynamics, or to have a more aggregate view of the system. For instance, in health monitoring context, it is interesting to take into account the degradation dynamics. Getting some information about the degradation of the system is a significant advantage for elaborating a more precise diagnosis and to perform prognosis.

The next sections describe the hybrid level of Hybrid Particle Petri Nets formalism (HPPN-HL). The purpose of HPPN-HL is to represent some hybrid state characteristics, and not just either continuous dynamics or discrete states. For example, it will be possible to study properties such as stability or diagnosability of hybrid systems, or to monitor degradation and build a prognosis process. As stated before, this paper focuses on the degradation laws for system health monitoring, which depend on health modes. A set of dynamic equations is used to monitor the hybrid information we focus on. The update of the degradation value at each clock tick defines a degradation diagnosis function.

Hybrid Level

The HPPN-HL is defined as a tuple < P H , T H , H, F, Ω H > where:

• P H is the set of hybrid places.

• T H is the set of hybrid transitions.

• H ⊂ n is the state space of the hybrid state vector.

• F is the set of dynamic equations of the system associated with hybrid places, representing hybrid state evolution.

• Ω H is the set of conditions associated with the hybrid transitions.

A complete HPPN combines a behavioral level with a hybrid level and is thus defined as a tuple < P, T, P re, P ost, X, C, H, F, γ, Ω, M 0 >.

Hybrid places are used to compose the HPPN-HL and represent possible hybrid states. A hybrid state is a couple (p S i , p N j ). For the sake of clarity, p H l = (p S i , p N j ) denotes that a hybrid place p H l represents the hybrid state (p S i , p N j ). Because hybrid states are combinations of symbolic places and numerical places, the hybrid state set of a given behavioral model is always finite. However, only couples that are part of the set of output places of the same transition are considered as hybrid states:

p H l = (p S i , p N j ) ∈ P H if ∃t m ∈ T, (p S i , p N j ) ∈ (P ost(t m )) 2 .
(20) Hybrid states that do not satisfy Equation ( 20) are considered as intermediate states. This means there is no information in the model about them.

A hybrid place is marked by hybrid tokens

h i k = [s i k , d i k ] with i ∈ {1, ..., |M H k |}
where M H k is the set of all the hybrid tokens in the net at time k. A hybrid token is defined by a couple s i k = (δ j k , π l k ) of tokens running in the HPPN-BL and its corresponding hybrid state vector d i k ∈ H. The whole marking at time k of the HPPN is

M k = {M S k , M N k , M H k }.
Hybrid tokens are created and deleted as follows.

Creation: Because of their dependency on configurations and particles, hybrid tokens are created at the same time as the creation of a configuration or a particle. If a hybrid token h depends on a particle π that is duplicated during the prediction step of the state estimation process in a new particle π , then h is also duplicated in h but h depends on the new particle π .

Deletion: A hybrid token h depending on a configuration δ and a particle π is deleted when δ or π is deleted during the online process of the HPPN-BL.

Considering the two rules above, the HPPN-HL online process totally depends on the HPPN-BL online process but both processes are simultaneous.

Any hybrid place is linked with all the other hybrid places through a hybrid transition t H j ∈ T H .

∀p i ∈ P , M k (p i ) is the set of tokens in p i at time k and m k (p i ) = |M k (p i )| is the number of tokens in p i at time k. Definition 10 A hybrid transition t H j ∈ T H is fire-enabled at time k if: ∃p H i ∈ P re(t H j ), m k (p H i ) ≥ P re(i, j) (21)
A hybrid place is associated with a set of dynamic equations representing a hybrid state characteristics. The idea is to let a hybrid token h i = [s i , d i ] evolve in the HPPN-HL in accordance to symbolic and numerical places in which its associated configuration δ j k and its associated particle π l k , with s i = (δ j , π l ), are evolving.

To formally define the firing of hybrid transitions, we need to define the following notations: P (δ j ) = p S j and P (π l ) = p N l denote the projections of δ j and π l on the set of places P , P (s i ) = (p S j , p N l ) denotes the hybrid place of a couple s i = (δ j , π l ).

Each hybrid transition carries a set of hybrid conditions

Ω H (t H j ) that are satisfied if Ω H (t H j )(h i ) = 1.
Hybrid tokens h i are moved to another hybrid place p H if P (s i ) = p H :

∀h i = [s i , d i ], Ω H (t H j )(h i ) = 1 if P (s i ) = p H 0 otherwise. (22) S H k (p H ) is the set of hybrid tokens in p H satisfying the con- ditions Ω H (t H j ) at time k.
Definition 11 The firing of a fire-enabled hybrid transition t H j ∈ T H at time k is defined by:

M H k+1 (p H ) = M H k (p H )\S H k (p H ) M H k+1 (p H ) = M H k (p H ) ∪ S H k (p H ). (23)
An example of hybrid transition firing in a HPPN-HL is shown in Figure 9. There are two hybrid places

p H 1 = (p S 1 , p N 1 ) and p H 2 = (p S 2 , p N 2 ). At time k, the two hybrid tokens h 1 k = [s 1 k , d 1 k ] and h 2 k = [s 2 k , d 2 k ]
are following the characteristics of the hybrid state represented by p H 1 , so hybrid transitions t H 1 and t H 2 are fire-enabled.

P (s 1 k ) = (p S 1 , p N 1 ) but P (s 2 k ) = (p S 2 , p N 2 ) so Ω H (t H 2 )(h 2 ) is satisfied and h 2 is moved to p H 2 . h 2 thus follows at time k + 1 the characteristics of the hybrid state p H 2 = (p S 2 , p N 2 ). p H 1 p H 2 Ω H (t H 1 ) Ω H (t H 2 ) k k + 1 p H 1 p H 2 Ω H (t H 1 ) Ω H (t H 2 ) h 1 h 2 h 1 h 2 Figure 9
. Illustration of firing rules of fire-enabled hybrid transitions.

Hybrid tokens evolve according to laws defined for hybrid places. HPPN-BL tokens are changing places during the prediction step of the state estimation process (see Section 3.3), and then hybrid tokens are simultaneously changing places and their values are updated as follows:

∀h i k+1|k ∈ M H k+1|k (p H j ), d i k+1 = F j k+1 (d i k ), (24)
where F j k ∈ F is the set of dynamic equations associated with the hybrid place p H j . Because d i k+1 depends on d i k , the continuity of the value d i can be ensured. If F is not empty, the values d i k can be taken into account in the decision making process at time k that determines the marking at time k + 1 of the HPPN-BL.

APPLICATION TO DEGRADATION MONITORING

This section introduces a way to represent uncertainty about degradation for each system health mode using probability measures.

Degradation Modeling

In the context of health monitoring, the HPPN-HL formalism is used to include degradation laws in the system model. We propose to consider health modes as hybrid states of a HPPN. The system description is enriched with a set of degradation laws modeling the degradation depending on health mode stress levels. The set of degradation laws is supposed to be accurately known. F = {F p H l , p H l ∈ P H } is the set of degradation laws associated with hybrid places of the system. F p H l is a vector of degradation laws for each anticipated fault in the hybrid place p H l = (p S i , p N j ):

F p H l (t) =        f p H l 1 (t) f p H l 2 (t) . . . f p H l n f (t)        , (25)
where

f p H l j
represents the probability distribution of the fault f j at any time in the hybrid place p H l and n f is the number of anticipated faults.

Example 5 The right side of Figure 11 represents the HPPN-HL of the three-tank system model illustrated by Figure 6. This partial model has five health modes (see Section 4.1), thus the corresponding HPPN-HL has five hybrid places p H

1 = (nom 1 , D 1 ), p H 2 = (nom 2 , D 2 ), p H 3 = (12f 4 , D 2 ), p H 4 = (1f 1 , D 1f1 ), and p H 5 = (2f 1 , D 2f1 ). Five hybrid transitions t H 1 . . . t H
5 deliver accesses to the five hybrid places when associated hybrid conditions are satisfied (Equation ( 22)). Not all transitions are represented in Figure 11 for the sake of readability. Fault probability distributions F j associated with each hybrid place p H j are represented with the 2-parameter Weibull model. By setting β = 1, the Weibull model describes random failures and is similar to the exponential law. The second parameter η of the Weibull model depends on the system stress level in each health mode associated with a hybrid place:

f p H l j (t) = W (t, η j (p H l )) = t t0 1 η j (p H l ) exp - t η j (p H l )
dt.

(26) Fault probability distributions for leak faults f 1 , f 2 and f 3 are defined with three different value for parameter η (η a = 100000, η b = 80000, η c = 60000) representing three different stress levels defined for the system health modes. Fault probability distributions associated with each hybrid place of Figure 11 are given in Table 2. All degradation laws of the three-tank system are provided in the appendix.

Fault probability distributions for f 4 and f 5 mainly evolve with the number of closings/openings. Thus, the parameter η 13 for the valve v 13 (resp. η 32 for the valve v 32 ) depends on a cycle coefficient α 13 (resp. α 32 ) that increases after each occurrence of discrete events openv 13 or closev 13 (resp. openv 32 or closev 32 ) :

f p H l 4 (t) = W (t, η 13 (α 13 )), f p H l 5 (t) = W (t, η 32 (α 32 )). ( 27
)
At first, the system is supposed to be in health mode (nom 1 , D 1 ) and α 13 = α 32 = 1, η 13 = η 32 = 20000.

Diagnosis Based on HPPN

The diagnoser extended with the HPPN-HL is called a HPPNbased diagnoser. The HPPN-based diagnoser generation step does not modify the degradation model defined in Section 6.1. It is a HPPN that monitors both the behavior and the degradation of the system. Using a HPPN-based diagnoser, the diagnosis ∆ k of the system at time k is the complete marking of the diagnoser. Equation (28) represents the distribution of health mode beliefs Figure 11. Three-tank system example HPPN-based partial diagnoser. and the system degradation for each mode:

∆ k = Mk = { M S k , M N k , M H k }. ( 28
)
Example 6 Figure 11 shows a part of the HPPN-based diagnoser for the three-tank system. It illustrates the interactions between the HPPN-BL and the HPPN-HL of the diagnoser. At time k, two configurations and three particles are running in the HPPN-BL. One configuration is in the symbolic place nom 2 and the other one in the symbolic place 12f 4 . Three particles π 1 , π 2 and π 3 are in numerical place D 2 . Three hybrid tokens are running in the HPPN-HL. h 1 and h 2 are in the hybrid place p H 2 because they are linked to the configuration in nom 2 and respectively π 1 and π 2 . These two hybrid tokens follow degradation laws F p H 2 . h 3 is in the hybrid place p H 4 because it is linked to the configuration in 12f 4 and π 3 . This hybrid token follows degradation laws F p H 3 . For this example, the result of diagnosis can be written as follows:

∆ k = {(nom 2 , D 2 , h 1 ), (nom 2 , D 2 , h 2 ), (12f 4 , D 2 , h 3 )},
(29) where the degradation vectors of hybrid tokens h 1 , h 2 and h 3 at time k are respectively

d 1 k = F p H 2 (d 1 k-1 ), d 2 k = F p H 2 (d 2 k-1 ) and d 3 k = F p H 3 (d 3 k-1 ).
To sum up, the main steps of the proposed method are re-minded in Algorithms 1 and 2.

Mk ← StateEstimation(diagnoser, Mk-1 , O k ) 3: ∆ k ← Mk 4: end for
The first offline step (Algorithm 1, line 1) is to model the system considered using the HPPN framework (see Sections 4.1 and 6.1). The second offline step (Algorithm 1, line 2) is to generate the HPPN-based diagnoser from the system model (see Sections 4.2 and 6.2). Then the online process (Algorithm 2) uses consecutive observations to update the diagnoser marking and compute diagnosis (see Sections 3.3, 4.2 and 6.2).

From the HPPN-based diagnoser are provided two estimations:

• The belief on the system health modes takes the form of a marking { M S k , M N k } of the HPPN-BL, Table 2. Three-tank system example: health modes degradation laws.

Health mode

Valve state Degradation laws

p H 1 = (nom 1 , D 1 ) v 13 = open v 32 = open F p H 1        f p H l 1 (t) = W (t, η a ) f p H l 2 (t) = W (t, η a ) f p H l 3 (t) = W (t, η a ) p H 2 = (nom 2 , D 2 ) v 13 = closed v 32 = open F p H 2        f p H 2 1 (t) = W (t, η c ) f p H 2 2 (t) = W (t, η a ) f p H 2 3 (t) = W (t, η a ) p H 3 = (12f 4 , D 2 ) v 13 = closed v 32 = open F p H 3        f p H 3 1 (t) = W (t, η c ) f p H 3 2 (t) = W (t, η a ) f p H 3 3 (t) = W (t, η a ) p H 4 = (1f 1 , D 1f1 ) v 13 = open v 32 = open F p H 4        f p H 4 1 (t) = 1 f p H 4 2 (t) = W (t, η a ) f p H 4 3 (t) = W (t, η a ) p H 5 = (2f 1 , D 2f1 ) v 13 = closed v 32 = open F p H 5        f p H 5 1 (t) = 1 f p H 5 2 (t) = W (t, η a ) f p H 5 3 (t) = W (t, η a )
• The belief on the system degradation state takes the form of a marking of the HPPN-based diagnoser

∆ k = Mk = { M S k , M N k , M H k }.
The marking value { M S k , M N k } represents the belief on the health modes through a probability distribution. The marking value M H k represents the degradation state through a degradation distribution over the health modes. Because each hybrid token depends on a particle and a configuration, its degradation value is linked with the belief of its health mode. Consequently, the health mode belief and the degradation values can be considered in case of decision making in the context of health management.

CASE STUDY

The HPPN-based diagnoser generation has been implemented in Python 3.4. The tests described below were performed under Linux 4.9.2(x86 6 4 -linux -gnu) on a 1.90 GHzi5 -3437U CPU. Simulations use one CPU and a maximum of 2GB of RAM.

Three-Tank System Diagnoser

The three-tank model has been loaded, including its behavioral description and its degradation laws. The tank sections are S 1 = S 2 = S 3 = 0.0154m 2 and the pipe section between tanks is S n = 5.10 -5 m. Noise is modeled as Gaussian noise. Gaussian noise with a 0 mean value and a standard deviation of 0.01m has been added to each state equation. The mea-sure of h 1 is subjected to Gaussian noise with a 0 mean and a standard deviation of 0.01m. The measure of the water mass is subjected to Gaussian noise with 0 mean and a standard deviation of 0.1kg. The initial state is H 0 = [H 10 , H 20 , H 30 ] = [0.48, 0.55, 0.58] and valves v 13 and v 32 are open. The simulation sampling period is 60s because of the slow system continuous dynamics. The complete three-tank model has 40 symbolic places, 28 numerical places and 120 transitions. When using the merging rules in the diagnoser generation, the HPPN-based diagnoser has only 40 transitions, which represents a transition number reduction of about 66%. It shows that the diagnoser generation method is efficient and will be able to manage models for real systems. The initial symbolic and numerical places are respectively nom 1 and D 1 and the initial hybrid places is p H 1 = (nom 1 , D 1 ).

Results

Three scenarios have been simulated. Scenario 1 illustrates that the method is robust to occurrences of unobservable events, such as fault events. f 1 occurs at 660s and the system ends in failure mode (1f 1 , D 1 f 1 ). Figure 12 shows the mean value of the diagnoser particles compared to the real water levels. Areas around mean values represent particle value uncertainty.

Figure 13 shows the diagnoser health mode belief degrees compared to the real one at different times of the simulation.

The black dot indicates the real health mode of the system Figure 13. Scenario 1: health mode belief degrees.

Figure 13 shows that the health mode with the highest belief degree is always the real one (nom 1 , D 1 ) at 540s and then (1f 1 , D 1 f 1 ) at 1020s and 1560s. The leak in tank T 1 was thus well diagnosed. The diagnoser also considers other health modes because of the similarity between continuous dynamics. However, the discrete part of the system is used to restrain the health mode distribution and exclude health modes that do not match with observations and dynamic equations, such as (1f 1 , D 1 f 1 ) at 540s and (21f 1 , D 2 f 1 ) during the whole simulation.

Scenario 2 illustrates that the proposed method is robust to oc-currences of unobservable events where continuous dynamics are ambiguous. close v13 occurs and is observed at 660s and valve v 13 is closed, leading the system to health mode (nom 2 , D 2 ). Then at 1920s, f 4 occurs and the system ends in failure mode (12f 4 , D 2 ). Finally, open v13 occurs and is observed at 3180s, but the health mode of the system does not change.

Figure 14. Scenario 2: health mode belief degrees.

Figure 14 shows the diagnoser health mode belief degrees compared to the real one at different times of the simulation. At 240s, the health mode with the highest belief degree is the real one (nom 1 , D 1 ). At 1020s, both health modes (12f 4 , D 2 ) and (nom 2 , D 2 ) have high belief degrees because the diagnoser particles follow the same dynamic equations D 2 properly. The belief degree of (nom 2 , D 2 ) is slightly higher than the one of (12f 4 , D 2 ) because configurations in symbolic place nom 2 entirely match with the discrete observations (close v13 at 660s). Still, the possibility that the observation of close v13 at 660s could have been a false observation is kept in the marking, and thus in the diagnosis and in the computed belief degree distribution. At 2520s, the health mode with the highest belief degree is still (nom 2 , D 2 ) because the occurrence of f 4 does not involve any change of continuous dynamics. Once again, the diagnosis carries the possibility that the system is in the real health mode (12f 4 , D 2 ) with a high belief degree. Considering that f 4 is unobservable and the continuous dynamics of the two health modes are similar, it is the best diagnosis that can be pro-duced at this time. After open v13 is observed, configurations in nom 2 do not match with the observations as well as before and then the belief degrees of the two health modes become the same. Scenario 2 shows that the diagnoser is robust to occurrences of fault events even in case of ambiguous continuous dynamics.

Scenario 3 illustrates that the proposed method is robust to knowledge-based uncertainty, such as faulty modeling of the discrete behavior of the system or unreliable continuous dynamics, and observation uncertainty, such as occurrences of unobserved observable events or false observations. In this scenario, the standard deviations of state equation noise and the noise associated with the measure of h 1 have been quintupled and the simulation sampling period has been doubled. Events close v13 and open v13 occur respectively at 720s and 2040s but none of them are observed. At 3360s, f 1 occurs, leading the system to failure mode (1f 1 , D 1 f 1 ). Figure 15 shows the diagnosis of the system over time. The diagnoser monitors the three-tank health mode properly even if observable events are not observed and detects the fault f 1 in only one sample period. It also shows that the amplification of noise has consequences on the belief degree distribution: at 480s and 2040s, the real health mode is not the highest one but still remains in the diagnosis result. From 720s to 1920s, the diagnosis is ambiguous: (12f 4 , D 2 ) and (nom 2 , D 2 ) have the same belief degree due to the non observation of close v13 . However, some information such as f 4 probability could be useful for decision making during this period. Figure 16 shows fault f 4 degradation monitoring by hybrid tokens in hybrid place p H 1 from 0s to 600s. Degradation is monitored by estimating fault f 4 occurrence probability and is the mean of all hybrid token values. At 600s, f 4 occurrence probability is around 0.006. This very low probability could be taken into account in case of decision making at time 720s, and then disambiguate diagnosis by preferring health mode (nom 2 , D 2 ).

Faults are always detected in one sampling period because HPPN consider all possibilities during the online process pre- Table 3 shows that the average diagnosis computation time is around 6.5s and the average number of all the diagnoser tokens at any time is 44780. These metrics point out that the diagnosis computation time increases with the diagnoser token number but remains acceptable compared to the system time constraint.

Simulation results show that HPPN-based diagnosis is robust to different types of uncertainty. In Scenario 1, the diagnoser detects and identifies properly a leak fault in tank T 1 , but always considers possibilities of other modes having almost the same dynamic equations. Scenario 2 illustrates how the diagnoser deals with undetectable fault occurrences. Finally, Scenario 3 shows that the diagnoser is robust in case of noisy knowledge and observations and introduces the need to consider degradation monitoring in case of diagnosis ambiguity.

CONCLUSION AND FUTURE WORK

This article illustrates the HPPN approach to process health monitoring of hybrid systems under uncertainty. The HPPN approach takes into account knowledge-based and observationbased uncertainty.

A HPPN-based diagnoser has been defined to monitor both discrete and continuous behaviors of the system. The HPPN-BL-based diagnoser is enriched to consider a level representing a hybrid property depending on the hybrid state of the system. The article focuses on the degradation property, in order to introduce concepts that will be useful to perform prognosis and health management of hybrid systems under uncertainty.

In addition, diagnosis results can be used as probability distributions for decision making. Throughout the paper, concepts are illustrated with a three-tank system example. The HPPNbased diagnoser deals with event occurrence possibility and knowledge imprecision. Three scenarios have been tested to illustrate the proposed method advantage. The HPPN-based diagnoser results are consistent with the expected ones.

In future work, the HPPN-based diagnoser will be tested on a real three-tank system. The proposed method may be adapted to meet real system constraints. We also aim at formalizing and developing a prognosis process that will interleave diagnosis and prognosis methods to obtain more accurate results.

Figure 2 .

 2 Figure 2. Illustration of firing rules of numerical (a), symbolic (b) and mixed (c) fire-enabled transitions.

  (a) A numerical correction, based on the particle filter algorithm, produces a probability distribution Pr DN of the particles M N k+1|k+1 over the numerical places. At this step, particle weights are updated using a probability distribution function depending on random noise that models uncertainty about continuous observations O N k+1 . (b) A symbolic correction then computes a probability distribution Pr DS over the symbolic states of the system, depending on discrete observations O S k+1 and on Pr DN making the process hybrid.

Figure 3 .

 3 Figure 3. Unidirectional system evolution without maintenance or repair action.

Figure 4 .

 4 Figure 4. Unidirectional evolution of the three-tank system.

Figure 10

 10 Figure 10 illustrates the evolution of the value d 2 of hybrid token h 2 of Figure 9. It shows that d 2 k+1 is computed with dynamic equations F 2 k+1 . F 2 k+1 is associated with p H 2 and depends on d 2 k , the value of d 2 at time k. This ensures the continuity between F 1 k and F 2 k+1 at time k + 1.

Figure 10 .

 10 Figure 10. Illustration of the continuities of hybrid token values.

Algorithm 1

 1 Offline process 1: model ← CreateHP P N M odel() 2: diagnoser ← GenerateHP P N Diagnoser(model) Algorithm 2 Online process Input: diagnoser, M 0 1: for all O k do 2:

Figure 12 .

 12 Figure 12. Scenario 1: monitoring of water levels.

Figure 15 .

 15 Figure 15. Scenario 3: diagnosis.

Figure 16 .

 16 Figure 16. Scenario 3: degradation monitoring in mode (nom 1 , D 1 ).

  diction step and keep matching marking during the correction step. Diagnosis computation times and token numbers are given in Table 3. |M S |, |M N | and |M H | respectively represent the diagnoser configuration, particle and hybrid token number at the time the diagnosis is performed.

  places of a HPPN P N the set of numerical places of a HPPN P S the set of symbolic places of a HPPN P H the set of hybrid places of a HPPN T the set of transitions of a HPPN T N the set of numerical transitions of a HPPN T S the set of transitions of a HPPN T M the set of mixed transitions of a HPPN T H the set of hybrid transitions of a HPPN P re(t) the set of input places of a transitions t ∈ T P ost(t) the set of output places of a transitions t ∈ T X the state space of the numerical state vector C the set of dynamic equation sets associated with numerical places, representing continuous state evolution of the system H the state space of the hybrid state vector F the set of dynamic equations associated with hybrid places Ω the set of conditions of a HPPN Ω N the set of numerical conditions of a HPPN Ω S the set of symbolicconditions of a HPPN Ω H the set of hybrid conditions of a HPPN M k the marking of a HPPN at time k M N k the set of particles of a HPPN at time k M S k the set of configurations of a HPPN at time k M H k the set of hybrid tokens of a HPPN at time k M k (p) the marking of the place p at time k m k (p) the numbers of tokens in the place p at time k S k (p) the tokens in p ∈ P re(t) that satisfy the conditions Ω N (t) at time k π k a particle of M N k in a HPPN at time k with a value x k ∈ X and a weight w k ∈ [0, 1] δ k a configuration of M S k in a HPPN at time k h k a hybrid token of M H k in a HPPN at time k with a value d k ∈ H and associated with a couple of tokens s k = (δ k , π k ) P (s k ) the hybrid place of a couple of token s = (δ k , π k ) at time k Σ the set of discrete events Σ o the set of observable discrete events Σ uo the set of unobservable discrete events O k the set of observations at time k O N k the set of continuous observations at time k O S k the set of discrete observations at time k Q the set of health modes ∆ k the diagnosis at time k REFERENCES Basile, F., Chiacchio, P., & Tommasi, G. D. (2009). Fault diagnosis and prognosis in Petri nets by using a single generalized marking estimation. In 7th ifac symposium

Table 3 .

 3 Diagnosis computation time for different scenarios.

		Scenario	computation time (s)	|M S |	|M N |	|M H |
		average	1.123	4	330	1848
	1	minimum	0.581	2	200	400
		maximum	2.595	9	696	6264
		average	7.305	63	774	50427
	2	minimum	1.802	8	600	4800
		maximum	18.287	130	800	104000
		average	8.495	118	524	66349
	3	minimum	0.906	8	200	1600
		maximum	118.509	2304	607	1398528
		total average	6.274	65	610	44105

[START_REF] Gaudel | Hybrid systems diagnosis using modified particle Petri nets[END_REF]. The classical diagnoser is a fi-

APPENDIX

This section provides the three-tank system model. Tables 4 and5 detail state equations and degradation laws associated with the system health modes. Table 4. Three-tank system example: state equations and degradation laws.

Valve state

State equations Degradation laws for leak faults

Table 5. Three-tank system example: state equations and degradation laws.

Valve state State equations Degradation laws for leak faults


C Vanstraceele

B Geller

J M Brossier

J P Barbot

A Low Complexity Block Turbo Decoder Architecture

Keywords: Block codes, Iterative decoding, Low-complexity design, Turbo codes

We present a low-complexity architecture designed for the decoding of block turbo codes. In particular we simplify the implementation of Pyndiah's algorithm by not memorizing any of the concurrent codewords generated by the Chase search.

A Low Complexity Block Turbo Decoder Architecture I. INTRODUCTION Forward-Error Correction (FEC) is used in many digital communication systems to provide reliability and coding gains over the overall power budget of the link. Convolutional turbo-codes allow performance close to Shannon's theoretical limit. Block Turbo Codes (BTCs), i.e. product block codes with iterative column and row decodings, also achieve near-capacity decoding with high coding rates [START_REF] Hagenauer | Iterative decoding of binary block and convolutional codes[END_REF].

Pyndiah [START_REF] Pyndiah | Near optimum decoding of product codes : Block Turbo Codes[END_REF] has devised a low-complexity block turbo decoding algorithm. Each iteration m of this algorithm can be summarized as follows:

• For each row (or column) of an n × n product word, perform a Chase search [START_REF] Chase | A class of algorithms for decoding block codes with channel measurement information[END_REF] in order to have a list of codewords and a decided code word d = (d 0 , . . ., d j , . . ., d n-1 ) with d j ∈ {-1, +1}.

• Evaluate a vector of decision reliabilities Λ = (Λ(d 0 ), . . ., Λ(d j ), . . ., Λ(d n-1 )) in terms of normalized log-likelihood ratio (LLR); for each position j (j < n), the reliability of each decision is:

Λ(d j ) ≈ r -c -1(j) 2 -r -c +1(j) 2 4 , (1)
where c -1(j) (respectively c +1(j) ) is the codeword in the Chase list at minimum Euclidean distance of the updated received codeword r = (r 0 , . . ., r j , . . ., r n-1 ), such that c -1(j) = -1

(respectively c +1(j) = +1). One of these two codewords is equal to d and the other is then referred as c d .

• Obtain for each position j the extrinsic information w j :

w j =    Λ(d j ) -r j if a competing c d exists,
β(m)d j if no competing word exists.

(2)

• Once the extrinsic information has been evaluated, update the input to the next Soft-Input/Soft-Output (SISO) decoding stage with:

July 16, 2007 DRAFT

r j = r j + α(m)w j (3)
where α(m) is a weight factor increasing along the convergence process.

There were several refinements to Pyndiah's original work. For instance, [START_REF] Adde | Recent simplifications and improvements in Block Turbo Codes[END_REF] (respectively [START_REF] Chi | On the performance/complexity tradeoff in block turbo codes[END_REF]) proposes to update the algorithm without the need of using any of the coefficients β(m) in equation ( 2) (respectively α(m) in equation ( 3)). [START_REF] Argon | A parallel decoder for low latency decoding of turbo product codes[END_REF] considers parallel rows and columns decoding of the product code in order to half the latency of the decoder. [START_REF] Hirst | Fast Chase algorithm with an application in turbo decoding[END_REF] presents a lowcomplexity Chase decoder.

The purpose of this letter is to show that it is absolutely unnecessary to put any of the Chase codewords into memory and that at each iteration, one can readily update the output of the SISO decoder.

II. SIMPLIFICATION OF THE IMPLEMENTATION

A. Principle

We consider the decoding process of a given updated received (line or column) vector r of

length n. Let p(c) = n-1 j=0
r j c j be the ordinary scalar product of r with a codeword c. A codeword is at minimum distance of r if, and only if, its scalar product is maximum. Equation ( 1) can be written as the difference between two scalar products:

Λ(d j ) = 1 2 p c +1(j) -p c -1(j) (4)
This illustrates that instead of memorizing codewords to evaluate the reliabilities, it is sufficient to memorize scalar products [START_REF] Geller | Contribution à l'étude des systèmes de communications numériques[END_REF], [START_REF] Vanstraceele | Turbo-Codes et estimation paramétrique pour les communications à haut débit[END_REF]. One then observes that one such memorized scalar product can be used several times during the updating of a vector of reliabilities Λ if the corresponding code word is at minimum Euclidean distance for several different coordinates. More precisely, a given scalar product will be used every time that the corresponding code word is one of the possibly two minimum distance competing codewords. For instance, for every coordinate, the scalar product p(d) of the decided codeword d will necessarily be one of the two competing scalar product of equation ( 4) as the decoded word d is at minimum Euclidean distance of r.

We thus adopt the following strategy requiring only two shift registers of n real values.

s + = (s + 0 , ..., s + j , ..., s + n-1 ) designates a shift register of scalar products p(c +1(j) ).

July 16, 2007 DRAFT s -= (s - 0 , ..., s - j , ..., s - n-1 ) designates a shift register of scalar products p(c -1(j) ).

Initialization : s + and s -are both initialized at the minimum possible values (-∞).

First step :

Let c 1 = (c 1,0 , . . ., c 1,j , . . ., c 1,n-1 ) be the first Chase decoded codeword with scalar product p(c 1 ),

J + 1 = {j ∈ {0, 1, • • • , n -1}|c 1,j = +1} , J - 1 = {j ∈ {0, 1, • • • , n -1}|c 1,j = -1}. For j ∈ J + 1 , s + j = P [c 1 ]. For j ∈ J - 1 , s - j = P [c 1 ].
Following steps :

For each different Chase decoded c k = (c k,0 , . . ., c k,j , . . ., c k,n-1 ) with scalar product

P (c k ), J + k = {j ∈ {0, 1, • • • , n -1}|c k,j = +1}, J - k = {j ∈ {0, 1, • • • , n -1}|c k,j = -1}. For j ∈ J + k , if p(c k ) > s + j then s + j = p(c k ). For j ∈ J - k , if p(c k ) > s - j then s - j = p(c k ).
Result :

Λ = (Λ(d 0 ), . . ., Λ(d j ), . . ., Λ(d n-1 )) = 1 2 (s + -s -) (
The indexes where there is no competing codeword c d are simply β positions -see equation [START_REF] Pyndiah | Near optimum decoding of product codes : Block Turbo Codes[END_REF] or reference [START_REF] Adde | Recent simplifications and improvements in Block Turbo Codes[END_REF]).

B. Example

We now illustrate the previous procedure with a simple example. Let c i , be the four codewords generated by a Chase search with their scalar product p(c i ) (i ∈ {1, 2, 3, 4}) evaluated by the decoder.

July 16, 2007 DRAFT First step :

c 1 = (-1, +1, -1, +1, +1, -1, -1, +1), p(c 1 ) = 1.6 s + = (-∞, 1.6, -∞, 1.6, 1.6, -∞, -∞, 1.6) s -= (1.6, -∞, 1.6, -∞, 1.6, 1.6, -∞).
Second step :

c 2 = (+1, -1, +1, -1, +1, +1, -1, -1), p(c 2 ) = 2.5
s + = (2.5, 1.6, 2.5, 1.6, 2.5, 2.5, -∞, 1.6)

s -= (1.6, 2.5, 1.6, 2.5, -∞, 1.6, 2.5, 2.5).

Third step :

c 3 = (+1, +1, +1, +1, -1, +1, -1, +1), p(c 3 ) = 6.4
s + = (6.4, 6.4, 6.4, 6.4, 2.5, 6.4, -∞, 6.4)

s -= (1.6, 2.5, 1.6, 2.5, 6.4, 1.6, 6.4, 2.5).

Fourth step :

c 4 = (+1, -1, +1, +1, -1, -1, +1, -1), p(c 4 ) = 2.4
s + = (6.4, 6.4, 6.4, 6.4, 2.5, 6.4, 2.4, 6.4)

s -= (1.6, 2.5, 1.6, 2.5, 6.4, 2.4, 6.4, 2.5).

Result :

Λ = 1 2 (s +s -) = (+2.4, +1.95, +2.4, +1.95, -1.95, +2.0, -2.0, +1.95). We notice that the maximum scalar product vector c 3 = d is such that

c 3 = (sign[Λ(d 0 )], . . ., sign[Λ(d j )], . . ., sign[Λ(d n-1 )]).

C. Further discussion

The previous procedure simplifies the whole architecture of a BTC decoder. Not only there is no need to put into memory the competing codewords, but also, with the simplification of the reliabilities evaluation, many of the existing functionalities of a BTC decoder [START_REF] Kerouedan | How we implemented Block Turbo Codes[END_REF] disappear as, for instance, the search for every bit of a relevant competing codeword. It is even unnecessary to identify which is the maximum likelihood vector d among the competing codewords.

One can take advantage of the reduction in architecture complexity to use more test patterns dedicated to the Chase search. Figure 1 illustrates in the case of a BCH(128, 113) 2 product code July 16, 2007 DRAFT the Bit Error Rate (BER) improvement at the fourth iteration when one increases the number of least reliable bits used for the generation of the test patterns from t = 4 to t = 6. A gain of 0.3 dB is then observed at a BER of 10 -5 which leads this code of coding rate R = 0.78 to be at 2.1 dB from the Shannon's capacity in only 4 iterations.

The proposed procedure is particularly light when used in conjunction with a Fast Chase algorithm [START_REF] Hirst | Fast Chase algorithm with an application in turbo decoding[END_REF]; this is because if two words c and c differ in one position k (c k = -c k ), their scalar products are linked by the equality p(c ) = p(c )r k c k .

We now display the improvement on the complexity brought by the proposed architecture in terms of required memory. This architecture being totally independant on the way the concurrent codewords are generated, we suppose that for a given row (or line) of the product code, one has obtained a list of codewords. Most often, a Chase algorithm is chosen to generate this codewords list for both Pyndiah's original architecture and the present proposal.

Let q be the number of quantification bits and N c be the number of generated codewords;

in the sequel we display numerical results where N c is equal to 2 p . With Pyndiah's traditional algorithm, one has to store N c codewords with the associated Euclidean distance. One thus has to store N P Y b bits where:

N P Y b = N c (n + q) (5)
With the proposed algorithm, one has to store two real vectors s + and s -; one thus needs N P R b bits where:

N P R b = 2qn (6)
The following table allows to compare the required memory for typical parameters values : on the contrary, the required memory of the proposed method is not affected by the number of generated codewords.

III. CONCLUSION

This letter presented a particularly low-complexity procedure to implement block turbo decoding and giving exactly the same results as Pyndiah's work [START_REF] Pyndiah | Near optimum decoding of product codes : Block Turbo Codes[END_REF]. This low-complexity allows the implementation of larger codes for which Pyndiah's algorithm gives near-capacity results.

This algebraic based decoding scheme seems particularly suited for high data rate systems.

n

  = 32, NC = 64, q = 4 2304 256

Fig. 1 .

 1 Fig. 1. Bit Error Rates at iteration m = 4 for different numbers of tested bits using QPSK signalling on an additive white Gaussian noise channel.

  It is straightforward that when one wants to store more codewords, the required memory with the traditional Pyndiah's decoder becomes large and this becomes critical as in practice several elementary decoders are used in parallel. To circumvent this inconvenient, practical decoders just take into account a limited number of codewords. This leads to a Bit Error Rate degradation;

	TABLE I
	COMPARISON OF THE REQUIRED MEMORY
	July 16, 2007	DRAFT