Abdelmalek Mennad
email: amennad@spg.tu-darmstadt.de

Arezki Younsi

Mohammed Nabil

El Korso

Abdelhak M Zoubir

Adaptive detection of range-spread target in compound-Gaussian clutter without secondary data

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Range-spread target detection has received an increasing attention in the last two decades [START_REF] Conte | GLRT-based adaptive detection algorithms for range-spread targets[END_REF], which is mainly due to the rise of high resolution radar (HRR). Indeed, an HRR can resolve a single target as multiple scattering centers, depending on the range extent of the target and the range resolution of the radar system [START_REF] Wehner | High Resolution Radar[END_REF]. The improvement of the range resolution capabilities results in a reduction of the clutter power in each range cell, hence improving the detection performance. It is worth mentioning that range-spread target detectors are useful in many situations, e.g., for the detection of large ships with coastal radars or detection of a cluster of point like target, moving at the same velocity and in close spatial proximity to each other [START_REF] Bandiera | CFAR detection of extended and multiple point-like targets without assignment of secondary data[END_REF].

Nevertheless, performing range-spread target detection requires to develop a proper strategy since classical adaptive detection schemes, originally proposed for point-like targets, may lead to poor performances [START_REF] Gerlach | The effects of signal contamination on two adaptive detectors[END_REF][START_REF] Farina | High resolution radar for enhanced target detection[END_REF]. This is mainly due to the fact that the target signal may contaminate the secondary cells, while these are generally assumed to be target-free in the classical context of point-like target detection.

Range-spread target detection under Gaussian distributed clutter has been extensively investigated. In [START_REF] Gerlach | Detection of a spatially distributed target in white noise[END_REF], the authors proposed a detector for spatially distributed targets embedded in white Gaussian noise, based on a priori knowledge of the target scatterer density. A modified generalized likelihood ratio test (MGLRT) detector was proposed in [START_REF] Gerlach | Adaptive detection of range distributed targets[END_REF] to account for a singular estimated clutter covariance matrix. Furthermore, a fast converging detector with bounded constant false alarm rate (CFAR) property was derived in [START_REF] Gerlach | Fast converging adaptive detection of Doppler-shifted, range-distributed targets[END_REF], under the assumption of dominant thermal noise at the receiver. On the other hand, an adaptive detection of range-spread target in homogeneous and partially homogeneous environments was addressed in [START_REF] Conte | GLRT-based adaptive detection algorithms for range-spread targets[END_REF] and [START_REF] Conte | CFAR detection of distributed targets in non-Gaussian disturbance[END_REF]. Specifically, [START_REF] Conte | GLRT-based adaptive detection algorithms for range-spread targets[END_REF] and [START_REF] Conte | CFAR detection of distributed targets in non-Gaussian disturbance[END_REF] assume that the secondary data are signal-free components and that they share the same covariance matrix structure, but with possibly fluctuating power.

Nevertheless, for HRR operating at low grazing angles or in a maritime environment, the Gaussian model of the clutter is no longer valid. More precisely, in [START_REF] Watts | Special Issue on Radar Clutter and Multipath Propagation[END_REF], the clutter has been successfully modeled as a compound-Gaussian process. A compound-Gaussian process is the product of a real positive random process, named texture, and a complex Gaussian process, named speckle. In the last few years, many results have been obtained for the adaptive target detection in compound-Gaussian clutter. As an example, Gini and Farina proposed the so-called generalized matched subspace detector (GMSD) [START_REF] Gini | Matched subspace CFAR detection of hovering helicopters[END_REF]. The GMSD, which is a CFAR detector, aims to detect an unknown deterministic signal, but known to lie in a given subspace, corrupted by a compound-Gaussian clutter. In [START_REF] Bon | GLRT subspace detection for range and Doppler distributed targets[END_REF], the authors have derived an adaptive detector for range and Doppler distributed targets, embedded in a compound-Gaussian clutter, assuming target-free secondary cells.

In practice, the clutter covariance matrix is often unknown and commonly estimated from signal free-target secondary data in the context of compound-Gaussian process. In [START_REF] Younsi | Performance of the adaptive generalised matched subspace constant false alarm rate detector in non-Gaussian noise: an experimental analysis[END_REF], the authors used the approximated maximum likelihood method (AML), to estimate the clutter covariance matrix, from a set of homogeneous and signal free-target secondary data. Nevertheless, to respect the nonsingularity condition of the estimated covariance matrix, a large number of secondary data is required, which in practice, can contain interfering targets or other kind of non-homogeneities [START_REF] Himed | Analyzing space-time adaptive processors using measured data[END_REF]. To cope with the issue of low sample, structural information about the clutter covariance matrix can be exploited. Specifically, in this paper, we take advantage of modeling the clutter as an autoregressive process. Such modeling does not rely on a covariance matrix estimation step and consequently, avoids the need for large homogeneous secondary data set. This methodology has already been applied in the context of radar. More precisely, adaptive detection in unknown colored noise, modeled by an autoregressive process is addressed in [START_REF] Kay | Asymptotically optimal detection in unknown colored noise via autoregressive modeling[END_REF], for known point-like target signals and in [START_REF] Sheikhi | Adaptive detection algorithm for radar signals in autoregressive interference[END_REF] for a target signal known up to a scaling factor. In [START_REF] Shuai | AR-model-based adaptive detection of range-spread targets in compound Gaussian clutter[END_REF] and [START_REF] Alfano | Model-based adaptive detection of range-spread targets[END_REF], the authors modeled the speckle component of the clutter by a complex Gaussian autoregressive process of order P , for range-spread target detection in homogeneous and heterogeneous environment.

Nevertheless, in this paper, for each range cell and for an autoregressive process of order P and N samples, we propose to predict the P first samples in a backward manner, and samples from P + 1 until N in a forward manner, using only cells under test. The proposed scheme is compared with some existing ones, especially the recent algorithms presented in [START_REF] Shuai | AR-model-based adaptive detection of range-spread targets in compound Gaussian clutter[END_REF] and [START_REF] Alfano | Model-based adaptive detection of range-spread targets[END_REF], which use only the forward prediction, by considering just N -P samples, unlike the proposed algorithm which uses all available samples. A performance analysis in terms of false alarm probability and detection probability is performed for different target models. Our numerical results indicate that the proposed detector outperforms the autoregressive GLRT (ARGLRT) detector from [START_REF] Shuai | AR-model-based adaptive detection of range-spread targets in compound Gaussian clutter[END_REF] and [START_REF] Alfano | Model-based adaptive detection of range-spread targets[END_REF] in homogeneous and heterogeneous environment, especially when few samples are available. In addition, the proposed method outperforms the GLRT detector based on the AML estimator of the clutter covariance matrix, which requires a large number of secondary data [START_REF] Gini | Covariance matrix estimation for CFAR detection in correlated heavy tailed clutter[END_REF].

This paper is organized as follows. In section 2, we describe the data model. In section 3, we present the classical AR modeling and the proposed forward-backward AR modeling. Section 4 is devoted to the proposed detection algorithm. Simulation results are discussed in section 5 and finally a conclusion is given in section 6.

Problem setup

Let us consider a radar that collects N pulses during the time on target. For the i-th range cell, these pulses form the following complex valued received vector

z i = [z i (1) , . . . , z i (N)] T , i = 1, . . . , L (1)
where [.] T denotes the transpose operator and L is the number of range cells under test. For sake of simplicity, we assume that the received data vectors are independent among range cells [START_REF] Conte | GLRT-based adaptive detection algorithms for range-spread targets[END_REF][START_REF] Gini | Matched subspace CFAR detection of hovering helicopters[END_REF] and that the target is completely contained within L cells.

The detection problem is formulated as the following binary hypothesis testing problem

H 0 : z i = c i , i = 1, . . . , L H 1 : z i = c i + α i p, i = 1, . . . , L (2)
in which, c i = [c i (1) , . . . , c i (N)] T denotes the clutter vector, p = [p (1) , . . . , p (N)] T = 1, e j2π f d , . . . , e j2π (N-1) f d T is the N-dimensional time steering vector, where f d denotes the normalized target Doppler frequency. In addition, we assume that f d is known [START_REF] Conte | CFAR detection of distributed targets in non-Gaussian disturbance[END_REF][START_REF] Sheikhi | Adaptive detection algorithm for radar signals in autoregressive interference[END_REF][START_REF] Alfano | Model-based adaptive detection of range-spread targets[END_REF][START_REF] Gini | Covariance matrix estimation for CFAR detection in correlated heavy tailed clutter[END_REF][START_REF] Jian | Adaptive detection of sparsely distributed target in non-Gaussian clutter[END_REF], or efficiently estimated, see e.g., [START_REF] Bon | GLRT subspace detection for range and Doppler distributed targets[END_REF][START_REF] Gini | Maximum likelihood, ESPRIT, and periodogram frequency estimation of radar signals in K-distributed clutter[END_REF]. Finally, the unknown complex amplitudes α i are accounting for both the channel attenuation and the target cross section.

According to the compound-Gaussian model, the clutter c i for the i-th range cell, is modeled as the product of two independent random variables. Specifically, c i = √ τ i x, where x is a N-dimensional zero-mean complex circular Gaussian vector, representing the speckle component, and τ i denotes the variance of the underlying conditional Gaussian vector, named texture and represents the local clutter power, for each range cell. In shorthand notation, we write x ∼ CN (0, M), where M is the normalized covariance matrix of the speckle, such that trace(M) = N. We assume that τ i and x are mutually independent, consequently, one

has E c i c H i = τ i M = M c ,
f (z i | H 0 ; τ i , M) = 1 (πτ i ) N |M| exp - z H i M -1 z i τ i (3) f (z i | H 1 ; α i , τ i , M) = 1 (πτ i ) N |M| exp - (z i -α i p) H M -1 (z i -α i p) τ i (4)
in which, |.| denotes the determinant.

AR modeling

Forward modeling

Let us assume that the clutter model is given by an AR process of order P . Then, for n = P + 1, . . . , N and i = 1, . . . , L, we can write

c i (n) = - P k=1 a i (k)c i (n -k) + w i (n) ( 5
)
where a i = [a i (1), . . . , a i (P )] T is the P -dimensional vector of complex forward AR coefficients in the range cell i and w i (n) is zero mean complex Gaussian white noise with variance τ i [START_REF] Haykin | Adaptive Filter Theory[END_REF]. Under the AR model [START_REF] Sheikhi | Adaptive detection algorithm for radar signals in autoregressive interference[END_REF], we can rewrite (2) as:

⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ H 0 : z i (n) = -P k=1 a i (k)z i (n -k) + w i (n) i = 1, . . . , L; n = P + 1, . . . , N H 1 : z i (n) = -P k=1 a i (k) (z i (n -k) -α i p(n -k)) + α i p(n) + w i (n) i = 1, . . . , L; n = P + 1, . . . , N (6)
The conditional pdfs (3) and ( 4) can be approximated for N P [START_REF] Alfano | Model-based adaptive detection of range-spread targets[END_REF][START_REF] Haykin | Adaptive Radar Detection and Estimation[END_REF], respectively, by

f (z i | H 0 ; τ i , a i ) 1 (πτ i ) N-P exp - (z i + Z i a i ) H (z i + Z i a i ) τ i (7) f (z i | H 1 ; α i , τ i , a i ) 1 (πτ i ) N-P × exp - (z i + Z i a i -α i ( p + Pa i )) H (z i + Z i a i -α i ( p + Pa i )) τ i ( 8
)
where the (N -P ) dimensional vectors zi and p are given by zi = [z i (P + 1), . . . , z i (N)] T and p = [p(P + 1), . . . , p(N)] T , whereas, the (N -P ) × P -dimensional matrices Z i and P are expressed by 1)

Z i = ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ z i (P ) z i (P -1) . . . z i (1) z i (P + 1) z i (P ) . . . z i (2) . . . . . . . . . . . . z i (N -1) z i (N -2) . . . z i (N -P ) ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ and P = ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ p(P ) p(P -1) . . . p(
p(P + 1) p(P ) . . . p(2) . . . . . . . . . . . . p(N -1) p(N -2) . . . p(N -P ) ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ .
In the above equations, we used samples from P + 1 to N to model the received observation in a forward manner. In the following, we propose to extend this modeling by adding the prediction of samples from 1 to P , in a backward manner in order to gain more information, thus enhancing the performance of the proposed detector.

The proposed forward-backward modeling

In the backward prediction, we propose to predict the (n -P )th sample from the P future samples. Thus, for n = P + 1, . . . , N and i = 1, . . . , L, we obtain

c i (n -P ) = - P k=1 b i (k)c i (n -k + 1) + w i (n) (9)
where b i = [b i (1), . . . , b i (P )] T is the P -dimensional vector of complex backward AR coefficients in the i-th range cell and w i (n) denotes a zero mean complex Gaussian white noise with variance τ i [START_REF] Haykin | Adaptive Filter Theory[END_REF].

In the backward context, we can rewrite (2), for n = P + 1, . . . , N and i = 1, . . . , L,

⎧ ⎪ ⎨ ⎪ ⎩ H 0 : z i (n -P ) = -P k=1 b i (k)z i (n -k + 1) + w i (n) H 1 : z i (n -P ) = -P k=1 b i (k)(z i (n -k + 1) -α i p(n -k + 1)) + α i p(n -P ) + w i (n). ( 10
)
Let

z i = [z T i zT i ] T ( 11
)
in which zi = [z i (1), ..., z i (P )] T and zi = [z i (P + 1), ..., z i (N)] T . In the following, samples of the vector zi are predicted by a backward manner and samples of the vector zi are predicted by a forward manner.

Prediction under H 0 hypothesis

Under H 0 hypothesis and from [START_REF] Watts | Special Issue on Radar Clutter and Multipath Propagation[END_REF], the backward prediction of zi is given by ẑi = -Z i b i [START_REF] Bon | GLRT subspace detection for range and Doppler distributed targets[END_REF] with

Z i = ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ z i (P + 1) z i (P ) . . . z i (2) z i (P + 2) z i (P + 1) . . . z i (3) . . . . . . . . . . . . z i (2P ) z i (2P -1) . . . z i (P + 1) ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ . ( 13
)
Using ( 6), the forward prediction of zi is given by ẑi = -Z i a i . [START_REF] Himed | Analyzing space-time adaptive processors using measured data[END_REF] Consequently, from ( 12) and ( 14), and under H 0 , the forwardbackward prediction of z i is given by

ẑi = ⎡ ⎣ ẑi ẑi ⎤ ⎦ = -Z i d i ( 15
)
with

Z i = bdiag( Z i , Z i ) and d i = [b T i , a T i ] T .
The residual of the forward-backward prediction of z i is given by

w i = z i -ẑi = z i + Z i d i (16)
Then, the conditional pdf (3), under H 0 , can be approximated for N P by [START_REF] Haykin | Adaptive Radar Detection and Estimation[END_REF] f

(z i | H 0 ; τ i , d i ) 1 (πτ i ) N exp - (z i + Z i d i ) H (z i + Z i d i ) τ i (17)

Prediction under H 1 hypothesis

Let us denote

s i = [s T i sT i ] T ( 18
) with si = [s i (1), ..., s i (P )] T , ( 19
) si = [s i (P + 1), ..., s i (N)] T (20) in which, s i (n) = z i (n) -α i p(n), for n = 1, . . . , N.
⎤ ⎥ ⎥ ⎥ ⎥ ⎦ . ( 22
)
On the other hand, from (6), the forward prediction of si condi- tioned to α i , can be expressed by

ŝi = -Si a i ( 23
) with Si = ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ s i (P ) s i (P -1) . . . s i (1)
s i (P + 1) s i (P ) . . . s i (2) . . . . . . . . . . . . s i (N -1) s i (N -2) . . . s i (N -P ) ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ . ( 24
)
Finally, from ( 21) and ( 23), the forward-backward prediction of s i under H 1 is given by

ŝi = ⎡ ⎣ ŝi ŝi ⎤ ⎦ (25)
and its error vector is expressed as

w i = s i -ŝi = w w ( 26
)
in which w = si + Si b i [START_REF] Greco | Statistical analysis of measured polarimetric clutter data at different range resolutions[END_REF] and w = si + Si a i . [START_REF] Greco | Non-stationary sea clutter: impact on disturbance covariance matrix estimate and detector CFAR[END_REF] In addition, using [START_REF] Watts | Special Issue on Radar Clutter and Multipath Propagation[END_REF]

⎤ ⎥ ⎥ ⎦ . ( 31
)
Then, from ( 27), ( 29), (30) and after straightforward manipulations, we obtain

w = zi + Z i b i -α i p + P b i . ( 32
)
Using the same methodology for w, we have from ( 6) and ( 20):

si = zi -α i p. ( 33
)
On the other hand, ( 6) and ( 24) lead to

Si = Z i -α i P (34)
Consequently, combining ( 28), ( 33) and (34), we obtain

w = zi + Z i a i -α i p + Pa i (35)
Finally, from (32) and ( 35), the forward-backward residual vector of s i conditioned to α i is given by

w i = z i + Z i d i -α i (p + P d i ) ( 36
)
with P = bdiag P , P = P 0 0 P . In summary, using the same methodology as for H 0 , we conclude that the conditional pdf given in (4), under H 1 , can be approximated for N P by

p(z i |H 1 ; α i , τ i , d i ) 1 (πτ i ) N × exp - (z i + Z i d i -α i (p + P d i )) H (z i + Z i d i -α i (p + P d i )) τ i ( 37
)
4. The proposed adaptive detection algorithm

Homogeneous environment

In a homogeneous environment, it is commonly assumed that the clutter parameters do not change from cell to cell, which means that d d 1 = . . . = d L , and τ τ 1 = . . . = τ L [START_REF] Shuai | AR-model-based adaptive detection of range-spread targets in compound Gaussian clutter[END_REF][START_REF] Alfano | Model-based adaptive detection of range-spread targets[END_REF].

The optimum decision rule for target detection is the well known Neyman-Pearson criterion, which leads to the likelihood ratio test. Nevertheless, in our context, the parameters α = [α 1 , . . . , α L ], τ and d are unknown. We therefore resort to the suboptimal GLRT detector given by

GLRT (z 1 , . . . , z L ) = max α,τ ,d f (z 1 , . . . , z L | H 1 ; α, τ , d) max τ ,d f (z 1 , . . . , z L | H 0 ; τ , d) H 1 ≷ H 0 δ (38)
where δ denotes the detection threshold which is set according to the desired value of the false alarm probability [START_REF] Kay | Fundamentals of Statistical Signal Processing[END_REF]. Assuming independent z i for i = 1, . . . , L and using [START_REF] Shuai | AR-model-based adaptive detection of range-spread targets in compound Gaussian clutter[END_REF] and (37), the conditional joint pdfs of the total observation vectors z 1 , . . . , z L under H 0 and H 1 are, respectively, approximated by

f (z 1 , . . . , z L | H 0 ; τ , d) 1 (πτ ) N L exp - L i=1 (z i + Z i d) H (z i + Z i d) τ (39) and f (z 1 , . . . , z L | H 1 ; α, τ , d) 1 (πτ ) N L × exp - L i=1 (z i + Z i d -α i (p + P d)) H (z i + Z i d -α i (p + P d)) τ ( 40
)
in which, the estimation of the unknown parameters are performed by the maximum likelihood method in the following.

Maximum likelihood estimate of α

Under H 1 hypothesis, we can rewrite (40) as:

f (z 1 , . . . , z L | H 1 ; α, τ , d) 1 (πτ ) N L exp - L i=1 |g i -α i ψ| 2 τ ( 41
)
in which g i = z i + Z i d and ψ = p + P d. The maximum likelihood estimator (MLE) of α i is given by αi = arg min

α i |g i -α i ψ| 2 = ψ H g i ψ H ψ . ( 42
)
Plugging (42) into (41), we obtain

f (z 1 , . . . , z L | H 1 ; α, τ , d) 1 (πτ ) N L exp - L i=1 (z i + Z i d) H P ⊥ ψ (z i + Z i d) τ ( 43
)
where the orthogonal projector onto the subspace spanned by ψ is given by P

⊥ ψ = I N -ψψ H ψ H ψ
in which I N is the N × N identity matrix and α = [ α1 , . . . , αL ] T .

Maximum likelihood estimates of τ and d

To find the maximum likelihood estimate of τ under H 0 and H 1 , we maximize (39) and (43) with respect to τ , respectively.

After some manipulations, we obtain

τH 0 = L i=1 z i + Z i d H 0 H z i + Z i d H 0 N L (44) τH 1 = L i=1 z i + Z i d H 1 H P ⊥ ψ z i + Z i d H 1 N L ( 45
)
Following the same methodology as in [START_REF] Alfano | Model-based adaptive detection of range-spread targets[END_REF], the MLE of the forward part, i.e., a under H 0 and H 1 , respectively, is given by

âH 0 = - L i=1 Z H i Z i -1 L i=1 Z H i zi (46) âH 1 = - L i=1 Z H i P ⊥ φ Z i -1 L i=1 Z H i P ⊥ φ zi ( 47
)
where the orthogonal projector onto the subspace spanned by φ = [1, . . . , e j2π f d (N-P -1) ] T is given by P ⊥ φ = I N-P -φ φH φH φ . Consequently, the backward coefficients are deduced, under H 0 and H 1 , thanks to the following relationship (c.f. [START_REF] Haykin | Adaptive Filter Theory[END_REF] for proof) b(k) = a * (Pk + 1), k = 1, . . . , P (48)

Decision rule of the proposed forward-backward autoregressive GLRT detector

We replace the unknown parameters by their MLE estimates, in the joint conditional pdfs of the total observation z 1 , . . . , z L under H 0 and H 1 , from (39) and (40), we find, respectively,

f (z 1 , . . . , z L | H 0 ; τH 0 , dH 0 ) ⎡ ⎢ ⎣ N L π exp(1) L i=1 z i + Z i dH 0 H z i + Z i dH 0 ⎤ ⎥ ⎦ N L ( 49
)
and

f (z 1 , . . . , z L | H 1 ; α, τH 1 , dH 1 ) ⎡ ⎢ ⎣ N L π exp(1) L i=1 z i + Z i dH 1 H P ⊥ ψ z i + Z i dH 1 ⎤ ⎥ ⎦ N L . ( 50
)
where P ⊥ ψ is evaluated for dH 1 .

Consequently, from the above equations, the decision rule of the proposed detector is given thanks to approximations (49) and (50), i.e., FBD-H (z 1 , . . . ,

z L ) = L i=1 (z i + Z i dH 0 ) H (z i + Z i dH 0 ) L i=1 (z i + Z i dH 1 ) H P ⊥ ψ (z i + Z i dH 1 ) H 1 ≷ H 0 δ. ( 51
)
The proposed detector (51) is named forward-backward autoregressive GLRT detector in a homogeneous context (FBD-H). It uses all available samples (i.e., from 1 to N) in contrast to the ARGLRT-CG detector given in [START_REF] Shuai | AR-model-based adaptive detection of range-spread targets in compound Gaussian clutter[END_REF] and the ARGLRT detector given in [START_REF] Alfano | Model-based adaptive detection of range-spread targets[END_REF], which use only N -P samples.

Heterogeneous environment

In a heterogeneous environment, the clutter parameters change in space. This means that the autoregressive coefficients d i , as well the clutter power τ i , change from range cell to range cell. As in the homogeneous environment context, we resort to the GLRT strategy in order to setup our detector. Let us denote α

= [α 1 , . . . , α L ] T , τ = [τ 1 , . . . , τ L ] T and d = [d T 1 , . . . , d T L ]
T , which represent the unknown parameters. The GLRT is expressed as follows:

GLRT (z 1 , . . . , z L ) = max α,τ ,d f (z 1 , . . . , z L | H 1 ; α, τ , a) max τ ,d f (z 1 , . . . , z L | H 0 ; τ , a) H 1 ≷ H 0 δ. ( 52
)
Using ( 17) and (37), the conditional joint pdfs of the total observation under H 0 and H 1 and for independent z i , i = 1, . . . , L, are approximated, respectively, by

f (z 1 , . . . , z L | H 0 ; τ , d) 1 L i=1 (πτ i ) N exp - L i=1 (z i + Z i d i ) H (z i + Z i d i ) τ i (53) f (z 1 , . . . , z L | H 1 ; α, τ , d) 1 L i=1 (πτ i ) N × exp - L i=1 (z i + Z i d i -α i (p + P d i )) H (z i + Z i d i -α i (p + P d i )) τ i (54)
in which, the estimation of the unknown parameters will be performed by the maximum likelihood method in the following.

Maximum likelihood estimate of α

Let us denote, under H 1 hypothesis, g i = z i + Z i d i and ψ i = p + P d i . Then (54) can be rewritten as

f (z 1 , . . . , z L | H 1 ; α, τ , d) 1 L i=1 (πτ i ) N exp - L i=1 |g i -α i ψ i | 2 τ i . ( 55
)
The MLE of α i is given by

αi = ψ i H g i ψ i H ψ i . ( 56
)
Plugging ( 56) into (55), we obtain

|g i -αi ψ i | 2 = |g i | 2 - |g i H ψ i | 2 ψ i H ψ i = g i H P ⊥ ψ i g i ( 57
)
in which the orthogonal projector onto the subspace ψ is given by

P ⊥ ψ i = I N - ψ i ψ i H ψ i H ψ i , ( 58
) leading to f (z 1 , . . . , z L | H 1 ; α, τ , d) 1 L i=1 (πτ i ) N × exp - L i=1 (z i + Z i d i ) H P ⊥ ψ i (z i + Z i d i ) τ i . ( 59
)

Maximum likelihood estimates of τ and d

To find the maximum likelihood estimate of τ i under H 0 and H 1 we maximize ( 53) and (59) with respect to τ i , respectively.

After some manipulations, we obtain

τH 0 ,i = z i + Z i dH 0 ,i H z i + Z i dH 0 ,i N (60) τH 1 ,i = z i + Z i dH 1 ,i H P ⊥ ψ i z i + Z i dH 1 ,i N ( 61
)
Following the same methodology as in [START_REF] Alfano | Model-based adaptive detection of range-spread targets[END_REF], the MLE of the forward coefficients under H 0 and H 1 , are given, respectively, by

âH 0 ,i = -Z H i Z i -1 Z H i zi (62)
and

âH 1 ,i = -Z H i P ⊥ φ Z i -1 Z H i P ⊥ φ zi . ( 63
)
Then, we deduce the backward coefficients estimation thanks to

b i (k) = a * i (P -k + 1), k = 1, . . . , P [22].

Decision rule of the proposed forward-backward autoregressive GLRT detector

Let us replace the unknown parameters by their MLE estimates, in the joint conditional pdfs of the total observation vector under H 0 and H 1 , from ( 53) and (54), we find, respectively,

f (z 1 , . . . , z L | H 0 ; τ H 0 , dH 0 ) ⎡ ⎢ ⎣ N L π L exp(L) L i=1 z i + Z i dH 0 ,i H z i + Z i dH 0 ,i ⎤ ⎥ ⎦ N ( 64
)
and

f (z 1 , . . . , z L | H 1 ; α, τ H 1 , dH 1 ) ⎡ ⎢ ⎣ N L π L exp(L) L i=1 z i + Z i dH 1 ,i H P ⊥ ψ i z i + Z i dH 1 ,i ⎤ ⎥ ⎦ N ( 65
)
Consequently, from the above equations, we obtain the following decision rule

FBD-T (z 1 , . . . , z L ) = L i=1 (z i + Z i dH 0 ,i ) H (z i + Z i dH 0 ,i ) (z i + Z i dH 1 ,i ) H P ⊥ ψ i (z i + Z i dH 1 ,i ) H 1 ≷ H 0 δ (66) in which P ⊥ ψ i is evaluated for dH 1 ,i .
We name this proposed detector as forward-backward autoregressive GLRT detector in a heterogeneous environment (FBD-T). Unlike ARGLRT-HTG [START_REF] Shuai | AR-model-based adaptive detection of range-spread targets in compound Gaussian clutter[END_REF] and [START_REF] Alfano | Model-based adaptive detection of range-spread targets[END_REF], FBD-T uses all available samples, i.e., from 1 to N. We will demonstrate in the next section that the proposed detectors, namely, FBD-H and FBD-T, have better performance compared respectively to the ARGLRT and ARGLRT-HTG detectors for small data records, both in homogeneous and heterogeneous environment.

Performance analysis

This section is dedicated to numerical analysis of the proposed detectors in the homogeneous and heterogeneous contexts.

In both contexts, we perform a numerical comparison between the detectors ARGLRT, ARGLRT-HTG [START_REF] Alfano | Model-based adaptive detection of range-spread targets[END_REF], the AML-GLRT [START_REF] Younsi | Performance of the adaptive generalised matched subspace constant false alarm rate detector in non-Gaussian noise: an experimental analysis[END_REF][START_REF] Gini | Covariance matrix estimation for CFAR detection in correlated heavy tailed clutter[END_REF] and the proposed FBD-H and FBD-T detectors, in terms of the false alarm probability P fa and the detection probability P d .

Simulation setup

The standard Monte Carlo technique based on 100/P fa0 and 10000 independent trials is used to estimate P fa and P d respectively, for a nominal value of the false alarm probability P fa0 = 10 -4 and a number of cells under test L = 8. Furthermore, the order of the AR model is set to P = 3, which is expected to give good performance for radar sea clutter [START_REF] Shuai | AR-model-based adaptive detection of range-spread targets in compound Gaussian clutter[END_REF][START_REF] Alfano | Model-based adaptive detection of range-spread targets[END_REF].

The covariance matrix is derived according to an exponentcorrelation structure [START_REF] Shuai | AR-model-based adaptive detection of range-spread targets in compound Gaussian clutter[END_REF] given by [M]

m,n = ρ |m-n| , 1 ≤ m, n ≤ N, 0 ≤ ρ ≤ 1
where ρ represents the one-lag correlation coefficient. Typical values of ρ for radar sea clutter are in the interval [0.9, 0.99]. For these simulations, we set, e.g., ρ = 0.92 [START_REF] Gini | Covariance matrix estimation for CFAR detection in correlated heavy tailed clutter[END_REF].

In the following, the clutter is assumed to be K-distributed, which models well the sea clutter [START_REF] Ward | Maritime surveillance radar. Part I: radar scattering from the ocean surface[END_REF]. In this latter case, the texture is gamma distributed as

f τ (τ i ) = 1 (ν) ν μ ν τ ν-1 i exp - ν μ τ i u(τ i ) i = 1, . . . , L (67)
where (.) denotes the gamma function, μ and ν are, respectively, the scale and shape parameters and u(.) is the standard unit step function. Typical values of ν for sea clutter are greater than 0.4. Let us consider ν = 0.5, which represents a spiky clutter situation [START_REF] Bon | GLRT subspace detection for range and Doppler distributed targets[END_REF].

Background on the AML-GLRT detector

In the following, we give a brief description of the GLRT detector using the so-called AML estimator. We assume that the receiver collects K i.i.d. vectors of secondary data z k = { √ τ k x k } K k=1 from K adjacent range cells. The AML estimator of the covariance matrix is given for K i.i.d. vectors of secondary data as

MAML (m + 1) = N K K k=1 z k z H k z H k M-1 AML (m)z k ( 68
)
with m = 1, . . . , t and t denotes the iteration number [START_REF] Gini | Covariance matrix estimation for CFAR detection in correlated heavy tailed clutter[END_REF]. Regarding the initialization, we use the normalized sample covariance matrix estimator, i.e.,

MAML (1) = MNSCM = N K K k=1 z k z H k z H k z k . ( 69
)
The convergence criterion used for the iterative algorithm is given by [START_REF] Younsi | Performance of the adaptive generalised matched subspace constant false alarm rate detector in non-Gaussian noise: an experimental analysis[END_REF]

C (m) = MAML (m + 1) -MAML (m) MAML (m) ≤ 10 -3 (70)
where . denotes the Frobenius norm.

In our scenario, the number of iterations t is found to be equal to 3 most of the time. Greater values do not lead to further performance improvements, this result was also noticed in [START_REF] Younsi | Performance of the adaptive generalised matched subspace constant false alarm rate detector in non-Gaussian noise: an experimental analysis[END_REF] and [START_REF] Gini | Covariance matrix estimation for CFAR detection in correlated heavy tailed clutter[END_REF].

Finally, the AML-GLRT detector based on the AML estimator is given by [START_REF] Shuai | Performance analysis of GLRT-based adaptive detector for distributed targets in compound-Gaussian clutter[END_REF] AML-GLRT (z 1 , . . . , z L , z 1 , . . . , z K )

= -N L i=1 ln 1 - |p H M-1 AML z i | 2 (z H i M-1 AML z i )(p H M-1 AML p) H 1 ≷ H 0 δ (71)

Performance in terms of false alarm probability

• From Fig. 1, we note that the FBD-H detector and the AML-GLRT detector outperforms the ARGLRT detector in terms of the CFAR property, especially for f d = 0, where we have a maximum in the power spectral density (PSD) of the clutter. This is due to the use of the whole sample set in the prediction procedure of the FBD-H detector, while the ARGLRT scheme uses only N -P samples.

On the other hand, we observe comparable performance of the AML-GLRT and the proposed FBD-H detector. Nevertheless, it is worth mentioning that the AML-GLRT uses a large number of secondary data (in this case K = 64), which are supposed to contain clutter only, to estimate the clutter covariance matrix, whereas, the FBD-H uses only L = 8 cells under test without the strong assumptions of homogeneous and not corrupted secondary data.

• In Fig. 2, we compare the false alarm probabilities of the FBD-H, ARGLRT and AML-GLRT detectors for different values of N in a homogeneous context. We observe that the proposed FBD-H detector and the AML-GLRT detector have almost a constant false alarm probability equal to the nominal value P fa0 , contrary to the classical detector ARGLRT which has higher value of the P fa .

• Let us focus on the robustness of the aforementioned detectors w.r.t. non-homogeneities of the secondary data. We assume that the primary and the secondary data do not share the same covariance matrix. Specifically, let us assume a slight difference of the correlation coefficient ρ p = 0.92 for the primary data, whereas, the first half of the secondary data share a correlation coefficient ρ s,1 = 0.9 and the other half of the secondary data share a correlation coefficient ρ s,2 = 0.91. The probability of false alarm for such scenario is represented in Fig. 3. From this figure, we notice, as expected, a severe degradation of the false alarm probability of the AML-GLRT detector compared with the FBD-H detector. This represents one of the major drawbacks of the AML-GLRT detector whereas the proposed detector remains robust in such scenario.

• In order to consider the heterogeneous version FBD-T of the proposed detector and the heterogeneous version ARGLRT-HTG of the classical detector, we assume a K-distributed clutter In Fig. 4, we plot the false alarm probability vs. the normalized Doppler frequency of the detectors FBD-H, FBD-T, ARGLRT and ARGLRT-HTG. As expect, the homogeneous version of the proposed algorithm, namely FBD-H, outperforms the ARGLRT detector and its heterogeneous version ARGLRT-HTG. This is due to the spikiness nature of the clutter, for which the estimated value of the clutter power for each range cell is injected on the detector, knowing that, the clutter power changes from range cell to range cell.

• In Fig. 5, we perform a numerical analysis of the false alarm probability w.r.t. different values of the shape parameter ν for N = 8. We observe that the ARGLRT-HTG, FBD-T and AML-GLRT detectors have the CFAR property with respect to ν. This is due to the fact that the aforementioned detectors take into account the heterogeneous nature of the clutter and perform a normalization with respect to the clutter power in each range cell.

Performance in terms of detection probability

• Let us study the influence of samples number N on detection probability of the FBD-H and the ARGLRT detectors for three different target models (see Table 1). From Figs. 6 and7, we observe that the FBD-H has a better detection performance compared with the ARGLRT for low values of N. In fact, for N = 8 (cf., Fig. 6), the difference in the signal to clutter ratio (SCR) between these two detectors is greater than 1 dB for a detection probability equal to 0.5. This difference becomes less than 1 dB for N = 16 (cf., Fig. 7) and as N increases, the two detectors have almost the same detection probability. The advantage of working with low values of N is to ensure the temporal stationarity of the clutter. In fact, previous analysis of recorded real sea clutter data [START_REF] Greco | Statistical analysis of measured polarimetric clutter data at different range resolutions[END_REF][START_REF] Greco | Non-stationary sea clutter: impact on disturbance covariance matrix estimate and detector CFAR[END_REF], showed that this process is non-stationary, both in time and space. In addition, the aforementioned figures show that the knowledge of the fraction of the cells under test containing the target, is very important (see Table 1).

In the case where the target occupies a fraction of L range cells (e.g., M 2 and M 3 models), we observe a degradation in the probability of detection. For example, with the target model M 2 , where the target occupies three range cells with a dominant scatterer in the first range cell, the detection probability of the FBD-H decreases from 0.81 for M 1 to 0.61 for M 2 under SCR = 0 dB and N = 8. In the case where the target occupies one range cell, which is given by the target model M 3 , we observe a heavy degradation of the detection probability.

This latter decreases to 0.44 for SCR = 0 dB and N = 8, which is due to the fact that one range cell over L cells under test is occupied by the target signal and the rest are occupied by the clutter, decreasing thus the SCR.

• In addition, Fig. 8 shows a comparison between the AR based detectors for M 1 , from which we observe that the proposed FBD-T detector gives better detection probability compared with the FBD-H detector. Specifically, we deduce that the proposed schemes (FBD-T, FBD-H) improve detection performance of the classical scheme, i.e., ARGLRT and ARGLRT-HTG detectors.

• Finally, we study the influence of the number of samples N and K on detection probability of the FBD-H and the AML-GLRT detectors, for a target uniformly distributed among the L range cells. From Fig. 9, we observe that the FBD-H de- tector gives better detection performance compared with the AML-GLRT detector for K ≤ 2N. Furthermore, we notice that the performance becomes equivalent for K N (not reported here), but in practice it is difficult to obtain a large number of homogeneous secondary data, whereas the FBD-H detector uses only L cells under test, to estimate the clutter covariance matrix and without any secondary data.

Conclusion

In this paper, we proposed two detectors that require no secondary data, based on both forward and backward auto-regressive GLRT scheme, for which the clutter is modeled by an autoregressive model of order P . The proposed FBD-H and FBD-T detectors use the totality of the samples available for the prediction procedure contrary to the classical detectors ARGLRT and ARGLRT-HTG that use only N -P samples. The proposed detectors give better detection performance and have lower false alarm probability compared to the classical detectors ARGLRT and ARGLRT-HTG. Furthermore, it is worth mentioning that they overcome the need for large homogeneous data set, which may be unavailable in practice, contrary to the AML-GLRT detector which requires a number of homogeneous secondary data K ≥ 2N in order to achieve same performance as the proposed detectors.

Fig. 1 .

 1 Fig. 1. P fa versus f d for N = 32 and K = 64 in a homogeneous context.

Fig. 2 .

 2 Fig. 2. P fa versus N for f d = 0.

Fig. 3 .

 3 Fig. 3. P fa versus f d for N = 32, K = 64 in a non-homogeneous secondary data context.

Fig. 4 .Fig. 5 .

 45 Fig. 4. P fa versus f d for N = 32, K = 64 of FBD-H, FBD-T, ARGLRT and ARGLRT-HTG detectors.

Fig. 7 .

 7 Fig. 7. P d versus SCR for N = 16.

Fig. 8 .

 8 Fig. 8. Comparison between FBD-T, FBD-H, ARGLRT and ARGLRT-HTG for N = 8 in term of detection probability.

Fig. 9 .

 9 Fig. 9. Comparison between FBD-H and AML-GLRT for N = 8 and different values of K in term of detection probability.

  with M c denoting the clutter covariance matrix and [.] H indicates the conjugate transpose operator. The conditional probability density functions (pdf) of z i under H 0 and H 1 can be expressed, respectively, as

  and (19), we have si = ziα i p,

					(29)
	Si = Z i -α i P		(30)
	with p = [p(1), . . . , p(P )] T and
		⎡	p(P + 1) . . .	p(2)
	P =	⎢ ⎢ ⎣	. . .	. . .	. . .
			p(2P )	. . . p(P + 1)

Table 1

 1 Target models, location of different scatterers and ratio of cells energy with respect to the total energy reflected.

	Target models	Cell number
		1	2	3	4	5	6	7	8
	M 1	1/8	1/8	1/8	1/8	1/8	1/8	1/8	1/8
	M 2	5 / 8	2 / 8	1 / 8	0	0	0	0	0
	M 3	1	0	0	0	0	0	0	0

Fig. 6. P d versus SCR for N = 8.


Laurent Capocchi
email: capocchi@univ-corse.fr

Fabrice Bernardi
email: bernardi@univ-corse.fr

Dominique Federici
email: federici@univ-corse.fr

Paul Bisgambiglia

A DEVS-based Concurrent and Comparative Fault Simulation Algorithm

Keywords: Discrete Event Simulation, Concurrent and Comparative Simulation, Fault Simulation, DEVS, VHDL

Concurrent and Comparative Simulation (CCS) with

Multi-List Propagation (MLP) provides a way to perform several simulations in a single execution run and Concurrent Fault Simulation (CFS) has been one of its first applications. The main obstacles to a wide use of this technique are the high complexity of the concurrent simulation algorithms, along with the difficulty to integrate them in a simulation kernel. We focus in this paper on the CFS with MLP of systems described in the BFS-DEVS formalism, an extension of the original DEVS simulator that integrates the CCS algorithm. Application is performed in the behavioral digital domain of systems described in the VHDL language.

Introduction

Over the last 40 years discrete event simulation has begun to replace physical experimentation, as modeling and simulation offer efficient alternatives to expensive and complex physical experiments. Discrete event modeling allows designing an easy-to-handle and reusable representation of a system. However classical discrete event simulation only permits one simulation at a time for a system. This solution can appear to be very time consuming when many successive simulations are required for the complete experiment, especially in terms of result analysis and observability. In order to escape from these limitations the CCS with MLP appears to be an adapted solution, by providing a way to perform several simulations or other tasks in a single execution run.

We focus in this paper on the CFS with MLP of systems described in the BFS-DEVS formalism (Behavioral Fault Simulation for Discrete EVent system Specification) based on the DEVS formalism introduced by Zeigler in the late 70's in [START_REF] Zeigler | Theory of Modeling and Simulation[END_REF]. DEVS provides a modular and modeling approach, and automatically defines a simulator directly from a model using formal elements and algorithms. It also allows the integration of concurrent simulation algorithms in a simple, evolutive and transparent fashion for the system modeler.

Discrete event simulation has been used in hundreds of different domains (graph analysis, economical studies, symbolic simulation,...) and CCS can be virtually used in each of them. However even if CFS is approximately 20 years old, it is the only real existing application of CCS, and is not or not much used in the discrete event domain. Indeed, for many years, fault simulation has been an essential basic tool of CAD (Computer Aided Design) systems for digital circuits (see [START_REF] Larsson | Behavioral and structural model based approaches to discrete diagnosis[END_REF], [START_REF] Giambiasi | Test pattern generation for behavioral descriptions in VHDL[END_REF] and [START_REF] Santucci | Behavioral testing of digital circuits[END_REF]), but has never been used in the discrete event domain where it could help to analyze faulty behaviors. [START_REF] Kofman | FDEVS: A general DEVS-based formalism for fault modeling and simulation[END_REF] proposed a first approach for fault simulation of systems described using DEVS but did not formally integrate the concurrent algorithms. We present in this paper the BFS-DEVS formalism integrating the CFS with MLP algorithms in its kernel, and allowing the modeler to specify the faulty behavior of a system using a new faulty transition function.

The main objective of our work consists in defining a behavioral concurrent fault simulator implementing the BFS-DEVS formalism. We modify for that the original DEVS formalism by introducing a new transition function allowing the modeler to describe the faulty behavior of a system. The BFS-DEVS simulator kernel is an evolution of the original DEVS simulator kernel that integrates the CCS algorithms. These lasts are based on fault lists propagated and directed by propagation rules inside BFS-DEVS models. Validation of our approach is performed on behavioral fault simulation of digital circuits described in high level description languages.

This article is structured as follows. We describe in a first section the modeling specifications including the DEVS formalism and its extension BFS-DEVS. In a second section, we introduce the fault simulation environment and the general architecture of this environment is described. We introduce the BFS-DEVS library concept and the fault model used by the BFS-DEVS simulation kernel. Finally, we provide some results, a conclusion and some perspectives of work.

Modeling Specifications

DEVS Formalism

Introduced by Zeigler in the early 70's and completed in [START_REF] Zeigler | Theory of Modeling and Simulation[END_REF], DEVS is a set-theoretic formalism that provides a mean of modeling discrete event systems in a hierarchical and modular fashion. Using this formalism, modeling can be easily performed by decomposing a large system into smaller component models with coupling specifications between them.

DEVS Modeling

As in General System Theory (see [START_REF] Zeigler | An introduction to set theory[END_REF]), a DEVS atomic model contains a set of states and transition functions triggered by the simulator. It is represented by the following structure:

AM =< X, Y, S, δ int , δ ext , λ, t a >
where:

• X : {(p, v)|(p ∈ inputports, v ∈ X p )} is the
input ports set and values for the reception of external events.

• Y : {(p, v)|(p ∈ outputports, v ∈ Y p )} is the output ports set and values for the emission of events.

• S: is the internal sequential states set.

• δ int : S → S is the internal transition function that will bring the system to the next state after the time returned by the time advance function.

• δ ext : Q × X → S is the external transition function that will schedule state changes in reaction to an input event.

• λ : S → Y is the output function that will generate external events just before the internal transition takes place.

• ta : S → R + ∞ is the time advance function, that will give the life time of the current state (returns the time to the next internal transition).

A DEVS coupled model CM is a structure:

CM =< X, Y, D, {M d ∈ D}, EIC, EOC, IC >
where:

• X is the input ports set for the reception of external events.

• Y is the output ports set for the emission of external events.

• D is the components set (coupled or basic models).

• M d is the DEVS model for each d ∈ D.

• EIC is the input links set, that connects the inputs of the coupled model to one or more of the inputs of the components that it contains.

• EOC is the output links set, that connects the outputs of one or more of the contained components to the output of the coupled model.

• IC is the set of internal links, that connects the output ports of the components to the input ports of the components in the coupled models.

In a coupled model, an output port from a model M d ∈ D can be connected to the input of another M d ∈ D but cannot be connected directly to itself.

DEVS Simulation

As described in [START_REF] Chow | Abstract simulator for the parallel DEVS formalism[END_REF], DEVS allows a hierarchical and modular modeling of decomposable discrete event systems thanks to these specifications. One the main advantages of DEVS is that the simulator is directly and automatically extracted from the model. This DEVS simulator uses the modeling hierarchy and associates a simulator component to each atomic model and a coordinator component to each coupled model. This association allows the control of the behavior of each atomic model and the synchronization of the whole set of models. 1 is performed using four types of messages. The initialization message (i, t) is used to perform an initial temporal synchronization between all actors of the system (messages 1a and 1b on the figure). The internal transition message ( * , t) implies the execution of an internal event (message 2a), while the output message (y, t) allows the output communication to the parent elements, and results from the reception of a ( * , t) message (message 2b). Finally the external transition message (x, t) allows the execution of an external event (message 3). All these messages are more precisely discussed in the next sections.

BFS-DEVS Formalism

As [START_REF] Kofman | FDEVS: A general DEVS-based formalism for fault modeling and simulation[END_REF] we consider a behavioral fault as a modification of the transition functions, and/or of the output functions of the DEVS models. Thus a fault influences the behavior (or the state) of an affected DEVS model and can lead to a faulty behavior.

BFS-DEVS Modeling

The BFS-DEVS formalism introduced in this paper allows the specification and the simulation of faulty discrete event models. A BFS-DEVS model is defined by a classical DEVS structure with the following additional features first introduced by [5]:

• Transition and/or output functions are modified if behavioral faults are present in the DEVS model.

• Faulty behavior of DEVS models is specified by a new faulty external transition function δ f ault .

Consider a DEVS atomic model whose healthy behavior can be represented by the following DEVS structure:

AM h =< X h , S h , Y h , δ h int , δ h ext , λ h , ta h >
We define the following structure to take the faulty behavior into account:

AM f =< X, S, Y, F, δ int , δ ext , δ fault , λ, ta >
where,

• X = X h X f is the set of input values, with X f representing a set of new faulty values.

• S = S h S f is the set of state values, and S f is the set of new faulty states that the model can present due to the presence of a faulty input event.

• Y = Y h Y f is the set of output values, with Y f representing the set of new faulty values that the output ports can take when a faulty input event occurs.

• F = {F 1 , F 2 , F 3 }
is the faults set, with {F 1, F 2, F 3} is the fault model described further.

• δ int : S × F → S is the internal transition function modified by the presence of faults and presents the restriction δ int (s, ) = δ h int (s).

• δ ext : Q × X × F → S is the external transition function modified by the presence of faults and verifies δ ext (s, e, x,

) = δ h ext (s, e, x) if x ∈ X h .
• δ f ault : Q × X × F → S is the faulty external transition function providing the faulty behavior when a faulty event occurs.

• λ : X × F → S is the output function, which verifies λ(s, ) = λ h (s).

• ta : S × F → R + ∞ is the time advance function,f with the restriction ta(s, ) = ta h (s).

BFS-DEVS specifications are very similar with the original DEVS ones. The difference is that any time a faulty event x f (x f ∈ X f ) occurs, the new faulty state is calculated by the faulty external transition function δ f ault . If the healthy event x h (x h ∈ X h ) occurs, then the new healthy state is calculated by the healthy external transition function δ h ext .

BFS-DEVS Simulation

Communication between components is achieved in the original DEVS formalism using four types of messages. To distinguish a faulty behavior inside a simulation, we introduce a new message type that activates the model as soon as a fault event x f is present on one of its ports at a given time t. Activation of the faulty behavior of a component is performed using a message representing a faulty external event as shown in Algorithm 1 and Algorithm 2.

3 The Fault Simulation Environment

General Architecture

Concurrent fault simulation is approximately 20 years old and is one of the only existing applications of the concurrent simulation. However discrete event simulation has been employed in many applications and CCS can virtually be applied to each of them. Figure 2 (a) extracted from [START_REF] Ulrich | Concurrent and Comparative Discrete Event Simulation[END_REF] illustrates the relationships between the CCS simulation kernel and applications. We can see that this kernel implies the use of a mandatory modeling interface for a given application. However CCS allows the simulation of models created independently from their execution (concurrent) simulation environment. Thus CCS permits simplicity in writing simulation models and generality in how they are used.

Figure 2: BFS-DEVS Positioning

To define the software interface, we propose the BFS-DEVS formalism allowing:

• Concurrently modeling and simulating faults of discrete event systems issued from one application.

• Distinguishing between the model of the system and the simulation kernel.

• Implementing the model and the concurrent algorithms inside the simulation kernel using an object-oriented approach.

• Plugging fault models on demand.

• An easy updating of models in a hierarchical and modular fashion. shows that an application will be represented by a network of BFS-DEVS components (atomic and/or coupled model) constituting the Library. This network is directly simulable by the simulation kernel. This modeling is the interface between the physical applications and the BFS-DEVS simulation kernel based on the CCS. Thus to simulate a given application the modeler would design a domain specific BFS-DEVS library without thinking about the simulation part.

BFS-DEVS Library and Fault Models

Each application owns a BFS-DEVS components library defined by the user. As shown in Figure 3, this library is composed by models (atomic and/or coupled) used to compose the final model to be simulated. Its construct implies the knowledge of a fault model mandatory for the definition of the faulty behaviors.

The behavioral rules associated to the data and structure graphs of the application allow defining the models, their interfaces and behaviors. Determining the control and data structures for a given application is not straightforward, and implies a strong collaboration with a studied domain specialist. Recurrent types of these models will constitute the BFS-DEVS library. Building a library for a given domain is not easy, but is the only "delicate" phase of our approach.

Inside the BFS-DEVS formalism, a new transition function δ f ault is introduced that permits to specify a faulty behavior for the model. This faulty behavior is obviously related to the fault type the model is affected by. Each fault type able to affect a BFS-DEVS model will change its state using the δ f ault function.

BFS-DEVS Simulation Kernel

A concurrent fault simulation inside a BFS-DEVS network (aka. BFS-DEVS simulation) is a healthy simulation of this network along with the concurrent execution of faulty simulations induced by multiple propagated fault lists.

Figure 4: Concurrent Fault Simulation Scheme Figure 4 shows how i ∈ N + faulty simulations are generated starting from one unique healthy simulation. These faulty simulations in faults contained the F i propagated lists. Moreover a faulty simulation induced by the fault list F L i can imply j ∈ N + faulty simulations propagating the lists F L ij such as F L ij ⊂ F L i ∀i, j ∈ N + . This propagation of faulty simulations by fault lists cutting up and re-orientation can be performed until one fault list is found, i.e. F L ij ≥ 1.

Experiments and Results: Application on Behavioral Digital Domain

Our approach has been applied in the digital circuits domain. We designed a BFS-DEVS library that allow us to model and simulate a circuit described in the VHDL hardware description language (see [START_REF] Ashenden | The designer guide to VHDL[END_REF]). This transformation is fully described in [START_REF] Capocchi | Transformation of VHDL descriptions into DEVS models for fault modeling and simulation[END_REF].

In order to show the validity of our approach, we chose a sub-set of the VHDL ITC'99 benchmarks of [START_REF]High time for high-level test generation[END_REF] shown in Table 1. Columns in this table sum up the information at the Behavior level in terms of number of VHDL lines of code #Lines , number of processes #Proc , number of assignment #Assig and conditional statements a #Cond and number of signals #S and variables #V.

Figure 5 shows the architecture of the developed prototype. A parser allows obtaining the BFS-DEVS network representation file. This network is simulated to generate the fault list obtained from a test sequence provided by a pseudo-random test pattern generator. This generator provides several pseudo-random test vectors arranged in independent sequences, and each one of these sequences contains the "reset" signal with the value "1". The fault Model used is similar to [START_REF] Fulvio Corno | RTlevel fault simulation techniques based on simulation command scripts[END_REF] and is based on the bit and conditional coverage metrics.

Calculus of the fault coverage FC is obtained by the number of detected faults on the total number of faults given by the parser. Results are reported in Table 2 and show the number of detected faults along with the associated fault coverage. Experiments show the validity of the BFS-DEVS formalism and prototype presented in this paper. We can indeed determine the faults effects on the VHDL instructions of the behavioral descriptions. The use of a pseudo-random test pattern generator allows obtaining of significant fault coverages to show the validity of our approach. However the length of the test pattern is sufficiently large to detect the most easily observable faults.

BFS-DEVS Simulator

Conclusion and Perspectives

We presented in this paper the BFS-DEVS formalism for the simulation of discrete event systems behavioral defaults in a simple and efficient fashion. We saw that this formalism is based on the CCS with MLP algorithms to simulate many input patterns against many faulty scenarios inside the BFS-DEVS network.

The proposed simulation environment is homogeneous and allows simply and generically integrating the domain-specific fault model. The design of a BFS-DEVS component library following the behavioral rules of a system is sufficient for the modeling and concurrent simulation of the defaults that can appear in the network. This simulation is also automatic and transparent for the user.

We validated this approach in the domain of behavioral faults for digital circuits. The fault coverages we obtained on the ITC'99 benchmarks are very satisfying.

More generally we have several perspectives concerning this research essentially about analysis and performance aspects. First distributed computing is more and more used in the discrete event simulation domain under the name of PDES (Parallel Discrete Event Simulation). We believe that our approach would take advantage of this technology and plan to a Distributed BFS-DEVS based simulator. Second we think that this work can help testing and debugging classical software programs, and that integrating the CSS (Concurrent Simulation for Software) domain metrics would be easy to perform in our architecture.

Figure 1 :

 1 Figure 1: DEVS Simulator Message Exchange

Figure 2 (

 2 Figure 2 (b) shows that an application will be represented by a network of BFS-DEVS components (atomic and/or coupled model) constituting the Library. This network is directly simulable by the simulation kernel. This modeling is the interface between the physical applications and the BFS-DEVS simulation kernel based on the CCS. Thus to simulate a given application the modeler would design a domain specific BFS-DEVS library without thinking about the simulation part.

Figure 3 :

 3 Figure 3: Building of a BFS-DEVS Library

Figure 5 :

 5 Figure 5: General prototype architecture

Table 1 :

 1 Benchmark Characteristics

	Benchmark	#Lines	#Proc	#Assig	#Cond	#S	#V
	b01	110	1	35		12	6	1
	b02	70	1	19		7	4	1
	b03	141	1	56		14	7	14
	b04	102	1	40		12	7	13
	b05	310	3	99		46	19	5
	b06	128	1	50		11	8	1
	b07	92	1	33		9	4	6
	b08	89	1	22		8	8	4
	b09	103	1	34		8	7	2
	b10	167	1	74		19	13	8
	Benchmark	#Vect	#Total Faults	#Detected Faults		FC [%]
	b01	117	79			73		92,94
	b02	209	48			42		87,50
	b03	707	130			108		83,07
	b04	103	105			89		84,76
	b05	542	251			61		24.30
	b06	200	95			78		82,10
	b07	400	76			66		86,84
	b08	373	64			63		98,43
	b09	395	68			57		83,82
	b10	4913	163			143		87,67

Table 2 :

 2 VHDL BFS-DEVS Simulation Results

A coordinator, using the X set, is then able to send two types of external messages to its imminent children, a "x-message" for a healthy simulation, and a "f-message" for a faulty simulation. This specification is shown bold on the Algorithm 2.

The faulty simulation can only be performed if the healthy simulation has already been achieved, because values of the first are used as references for the second. Error: bad synchronisation receivers = {r | r ∈ D, N ∈ Ir, Z N,r (x f ) = } for each r in receivers:

send f-message to r with x f r = Z N,r (x f ) update listevent with t nd and select t l = t tn = min{t nd | d ∈ D} Thus the simulator associated to a DEVS model receiving an external event x (x = x h ∈ X h ), and supposed to present a faulty behavior, receives in fact two types of messages. In a first step a x-message (x s , t) implying the activation of the external transition for the healthy part of the simulation, followed in a second step by a f-message ( , t) implying the execution of the external fault transition function for the faulty part of the simulation. If the model receives an external faulty event x f (x f ∈ X f ), the associated simulator will only receive a f-message (x f , t) from its parent coordinator. Thus it is the nature of the external events that allows the distinction on simulation paths.


Capocchi Laurent
email: capocchi@univ-corse.fr

Bernardi Fabrice
email: bernardi@univ-corse.fr

Federici Dominique
email: federici@univ-corse.fr

Bisgambiglia Paul

A DEVS-based Modeling and Behavioral Fault Simulator for RT-Level Digital Circuits

Keywords: DEVS, fault simulation, testability, modeling, simulation

The domain of fault simulation for digital circuits described at the RT-level is currently under heavy researches. The goal of these researches is to define a fast and efficient methodology for the validation of test patterns very early in the design flow. We propose in this article a new approach for the modeling and the simulation of behavioral faults for digital circuits described in the VHDL language, using a discrete event approach. This methodology, based on the DEVS formalism, is implemented in a working prototype, and experimental results show the correctness of our approach and the efficiency of our behavioral fault simulator called BFS-DEVS. The fault model used to validate our results is essentially based on the stuck-at fault model since a good simple stuck-at faults coverage rate implies a good real faults coverage rate.

INTRODUCTION

With the increasing complexity of digital circuits, test patterns generation and fault simulation have become very complex steps in the design flow. The use of structural models described at the gate level implies heavy and costly test environments, and also very expensive execution times unacceptable for the industry. In order to answer these problems, there is a need to define new methodologies that can be applied as soon as the behavioral level and that are also efficient for the test at the hardware level.

For many years, researches in the simulation domain have contributed to the development of the RT-level test. These researches concerns fault models [START_REF] Ghosh | On behavior fault modeling for digital designs[END_REF][START_REF] Keutzer | An observabilitybased code coverage metric for fonctional simulation[END_REF][START_REF] Riesgo | A fault model for vhdl descriptions at the register transfer level[END_REF], fault simulators [START_REF] Franco | A vhdl error simulator for functional test generation[END_REF][START_REF] Fallah | OCCOM: Efficient computation of observability-based code coverage metrics for functional verification[END_REF] and testability or test generators analysis [START_REF] Ferrandi | Implicit test generation for behavioral VHDL models[END_REF]. The main problem of the fault simulation is the difficulty to integrate these classical algorithms inside the HDL simulators. This problem comes from the complexity and the particular goals of the HDL languages which are languages for hardware de-scription. Even if these algorithms are very well known for many years, commercial tools do not integrate them. Our approach proposed in this paper shows that, using a VHDL behavioral description transformation in the DEVS formalism, we can easily integrate these complex simulation algorithms and simulate the digital circuits faulty behavior in an efficient and concurrent way.

Fault injection in HDL descriptions existing approaches can be based on the modification of the HDL code [START_REF] Franco | A vhdl error simulator for functional test generation[END_REF] or on the modification of the simulator or its interaction [START_REF] Corno | Rtlevel fault simulation techniques based on simulation command scripts[END_REF]. However the coding lines that are added during this modification imply an increase of the simulation time, but also an access to the source code of the simulator. On the other hand, the interactive method implies a perfect knowledge of the very complex simulation process. In our approach, the VHDL code is transformed but not modified, and no interaction with the simulation engine is needed thanks to the DEVS abstract simulator derived directly from the whole model. As described in [START_REF] Bernardi | Transformation of vhdl description into devs models for fault modeling[END_REF], each VHDL instruction is transformed in a DEVS component able to present an healthy or faulty behavior following a given fault model. The interconnection composed by all the DEVS components is directly simulable using the BFS-DEVS simulator.

We chose the fault model used in [START_REF] Ghosh | On behavior fault modeling for digital designs[END_REF][START_REF] Buonanno | How an evolving fault model improves the behavioral test generation[END_REF] based on the stuck-at fault model allowing a good correlation with the real faults. We chose also the concurrent fault simulation since this approach is fast and uses complex simulation algorithms allowing us to show how easy is the integration inside the BFS-DEVS methodology. This article is organized as follows. Section 2 is devoted to the presentation of the DEVS discrete event modeling and simulation formalism. Section 3 presents the fault simulator with the general simulation space architecture, the transformation of VHDL descriptions into DEVS components network, and the BFS-DEVS simulator. We provide the fault model and the fault simulation approach in Section 4, some experimental results in Section 5 and we conclude and give some perspectives of work in Section 6.

THE DEVS FORMALISM

Since the seventies, some formal works have been directed in order to develop the theoretical basements for the modeling and simulation of dynamical discrete event systems [START_REF] Zeigler | Theory of Modeling and Simulation[END_REF]. DEVS (Discrete EVent system Specification) has been introduced as an abstract formalism for the modeling of discrete event systems, and allows a complete independence from the simulator using the notion of abstract simulator.

DEVS Modeling

DEVS defines two kinds of models: atomic models and coupled models. An atomic model is a basic model with specifications for the dynamics of the model. It describes the behavior of a component, which is indivisible, in a timed state transition level. Coupled models tell how to couple several component models together to form a new model. This kind of model can be employed as a component in a larger coupled model, thus giving rise to the construction of complex models in a hierarchical fashion [START_REF] Zeigler | Theory of the Modeling and Simulation, 2nde Edition[END_REF]. As in general systems theory, a DEVS model contains a set of states and transition functions that are triggered by the simulator.

A DEVS atomic model AM with the healthy behavior is represented by the following structure :

AM h =< X h ,Y h , S h , δ h int , δ h ext , λ h ,t h a >
where:

• X h : {(p, v)|(p ∈ input ports, v ∈ X h p )
} is the set of input ports and values for the reception of healthy external events,

• Y h : {(p, v)|(p ∈ out put ports, v ∈ Y h p )
} is the set of output ports and values for the emission of healthy events,

• S h : is the set of internal sequential healthy states,

• δ h int : S h → S h is the healthy internal transition function that will move the system to the next healthy state after the time returned by the time healthy advance function,

• δ h ext : Q × X h → S h
is the healthy external transition function that will schedule the states changes in reaction to an input healthy event,

• λ h : S h → Y h is the healthy output function that will generate external healthy events just before the healthy internal transition takes places,

• ta h : S h → R + ∞ is the healthy time advance function, that will give the life time of the current healthy state (returns the time to the next healthy internal transition).

The dynamic interpretation is the following:

• Q = {(s, e)|s ∈ S h , 0 < e < ta h (s)} is the total state set,
• e is the elapsed time since last transition, and s the partial set of healthy states for the duration of ta h (s) if no healthy external event occur,

• δ h int : the model being in a healthy state s at t i , it will go into s , s = δ h int (s), if no healthy external events occurs before t i + ta h (s),

• δ h ext : when an healthy external event occurs, the model being in the healthy state s since the elapsed time e goes in s , The next healthy state depends on the elapsed time in the present healthy state. At every healthy state change, e is reset to 0.

• λ h : the healthy output function is executed before an healthy internal transition, before emitting an output healthy event the model remains in a transient healthy state.

• The DEVS coupled model CM is a structure :

CM =< X,Y, D, {M d ∈ D}, EIC, EOC, IC >
where:

• X is the set of input ports for the reception of external events,

• Y is the set of output ports for the emission of external events,

• D is the set of components (coupled or basic models),

• M d is the DEVS model for each d ∈ D,
• EIC is the set of input links, that connects the inputs of the coupled model to one or more of the inputs of the components that it contains,

• EOC is the set of output links, that connects the outputs of one or more of the contained components to the output of the coupled model,

• IC is the set of internal links, that connects the output ports of the components to the input ports of the components in the coupled models.

In a coupled model, an output port from a model M d ∈ D can be connected to the input of another M d ∈ D but cannot be connected directly to itself.

DEVS Simulation

The DEVS abstract simulator is derived directly from the model. A simulator is associated with each atomic model and a coordinator is associated with each coupled model. In this approach, simulators allows to control the behavior of each model, and coordinators allows the global synchronization between each of them. The communication between all these elements is performed using four kinds of messages. The initialization messages (i,t) are used to achieve an initial temporal synchronization between all actors. The internal transition messages ( * ,t) allow the processing of an internal event, while the external transition messages (x,t) allow the processing of an external event. Finally, the output messages (y,t) allow the transportation of the output values to the parent elements and is the result of an ( * ,t) message.

THE BFS-DEVS BEHAVIORAL FAULT SIMULATOR General Architecture

For the validation of our approach proposed in this article, we developed a simulation environment shown in Figure 1 and composed by:

• A VHDL description to DEVS components transformation module achieved using a parser that transforms each VHDL instruction (describing the healthy behavior of the digital circuit) in a DEVS representation, store these components in a models library and generates the list of all faults that could happen inside the circuit. The resulting network of components is an easy-handling oriented instruction graph. The behavioral fault model will be later integrated in the models specifications.

• A pseudo-random test pattern generator providing the stimuli that will be applied to the circuit following the knowledge of the faults to be simulated. In order to validate our approach, we chose to use a pseudo-random test pattern generator without any knowledge of the faults to be tested.

• A DEVS-based behavioral fault simulator called BFS-DEVS based on one of the main advantages of the DEVS formalism that is its ability to generate automatically the simulator from the models. Our simulator needs the DEVS models from the transformation but also input data from the pseudo-random test pattern generator. Since the fault model is integrated inside each atomic model, the faulty behavior of the whole system is simulable. This fault simulation is performed in order to define the quality of a test pattern. This quality is described by a coverage rate which is the number of detected faults by the number of simulated ones.

VHDL into DEVS Transformation

The first step for the fault simulation is the transformation of each VHDL instruction into a DEVS model in order to define a directly simulable network. This transformation presents many advantages:

• DEVS allows to model and simulate structural languages;

• We can easily insert a behavioral fault model in an atomic model;

Table 1: Mapping of the VHDL instructions with DEVS components

• We obtain the fault simulator directly from the DEVS model;

• DEVS allows a hierarchical and component-oriented modeling for a better reusability of the fault models.

The selected approach for the transformation of VHDL behavioral descriptions with sequential instructions relies on the association of each VHDL instruction with a DEVS atomic model and each VHDL process with a coupled model. We define four kinds of models described in Table 1:

The Allocation atomic model is mapped to the VHDL allocation instruction, the Junction atomic model to the selection instructions (end if, end case, end loop...) and allowing to make a junction between atomic models, the Conditional atomic model to the if, for, case... instructions, and the Parallel atomic model to the management of the processes.

In the simple example provided in Figure 2, we can see how the sequential instruction flow is transformed in an interconnection of atomic models encapsulated in a coupled model MC representing the following process: process2: process(sensitive signal list) begin if (conditional statement 1) allocation statement 1 elsif (conditional statement 2) allocation statement 2 else (conditional statement 3) allocation statement 3 end if; end process;

The behavioral fault simulation using a fault list propagation will happen in this network. The Generator atomic model is used only for the activation events generation for the process.

BFS-DEVS Simulation

The basic principles of our approach can be sum up in some steps:

• The Generator model build the initial fault list composed by the faults relative to the sensitive signals of the processes;

• This list is propagated inside the network of all atomic models. The list is modified by the nature of the atomic model (and so, by the nature of the VHDL instruction) and the nature of the traversed path;

• When the fault simulation is achieved, the Parallel component analyzes the faults observability. If a fault is observable, it is added to the detected fault list and is no longer propagated in order to speed up the simulation process. The modifications we performed inside the DEVS simulation engine allow us to concurrently simulate the digital circuits described using the DEVS formalism. These modifications are the following: The integration of a fault model inside a DEVS atomic model is performed through the modification of the δ ext and δ int functions, and/or the λ function. The faulty behavior of an atomic model is managed using a new external faulty transition function δ f ault : S × ℜ + 0 × X f → S as proposed in [START_REF] Kofman | Fdevs: A general devs-based formalism for fault modeling and simulation[END_REF] activated by the reception of a new kind of messages called ( f ,t).

The faulty behavior of a DEVS atomic model is activated by a ( f ,t) message associated with a faulty external event as shown in Figure 3. The coordinator, using its X input event set, is then able to send two kinds of external events: an (x,t) message for an healthy behavior, and a ( f ,t) for a faulty behavior and the simulation. Using this distinction, we are able to achieve concurrently the healthy and faulty simulations. Indeed, the fault simulation can only be performed if the healthy simulation has been already performed. In this case, the healthy values are known and can be used as a reference for the fault simulation.

The simulator associated with the DEVS atomic model receiving an external event x (and supposed to present a faulty behavior) receives two messages: an (x,t) message (for the healthy simulation) followed by a ( f ,t) message (for the faulty simulation). If the DEVS model receives a faulty external event x f the associated simulator will only receive a ( f ,t) message from its parent coordinator.

FAULT MODEL AND FAULT SIMULA-TION APPROACH

The fault model used in order to validate our approach is inspired by the works presented in [START_REF] Courbis | Test pattern generation for behavioral description in vhdl[END_REF][START_REF] Ghosh | On behavior fault modeling for digital designs[END_REF]. We consider only the permanent faults acting on the logical function of the circuit. We defined three kinds of faults which can affect the behavior of the DEVS models:

• The F1 fault type: these are stuck-at faults on signals and variables corresponding to the fault type number 1 described in [START_REF] Ghosh | On behavior fault modeling for digital designs[END_REF]. The signal (or the variable) get a forced value until its next variation. Following the Table 1, this kind of faults can appear inside the four kinds of models.

• The F2 fault type: These are branch stuck-at faults on control structures corresponding to the fault type number 2 described in [START_REF] Ghosh | On behavior fault modeling for digital designs[END_REF]. The result of the conditional instruction is forced to a boolean value during the simulation cycle. Following the Table 1, this kind of faults can appear in conditional models.

• The F3 fault type: These are the jump faults on instructions corresponding to a part of the fault type number 5 described in [START_REF] Ghosh | On behavior fault modeling for digital designs[END_REF]. The affectation instruction is not evaluated if the signal value must be updated. Following the Table 1, this kind of faults can appear in allocation models.

We can note that these faults are behavioral ones, and their effects are taken into account in the atomic models behaviors. If the chosen fault model presents some structural faults, their effects will only be taken into account in the specification of the coupled models.

The selected simulation approach is concurrent. Even if an expensive memory space is needed, this approach presents many advantages compared to the parallel, deductive or serial approaches:

• we can apply this approach at the behavioral level, and then we can integrate it easily in the DEVS formalism;

• this approach is fast. The fault propagation process inside the DEVS component allows the determination of multiple faults in a same time. There is no need to perform a simulation for each fault. Moreover, the propagated lists are reduced during the simulation;

• We can perform concurrently the simulation of the healthy and the faulty circuit. This propriety is completed by the use of the DEVS formalism allowing the parallelization of these two kinds of simulations.

EXPERIMENTAL RESULTS

The implementation of our approach has been performed using the PythonDEVS simulator proposed by [START_REF] Bolduc | A modeling and simulation package for classic hierarchical devs[END_REF]. The validation has been performed using the VHDL ITC'99 benchmarks [START_REF]Benchmarks included in itc'99 suite[END_REF]. Table 2 presents our results. The total number faults are simulated using a pseudo-random test pattern generator that generates 500 vectors. The high coverage rates obtained using a simple pseudo random test bench show that we are able to predict the random testability of a circuit very early in the design process.

CONCLUSIONS AND PERSPECTIVES

This article proposes a new behavioral faults modeling and simulation approach of digital circuits described in the VHDL language. This approach is based on the DEVS formalism for the modeling and the simulation of complex discrete event systems. The presented BFS-DEVS simulator allows to simulate the circuits in their healthy configuration, but also with behavioral faults thanks to a concurrent simulation without any modification to the VHDL code. The experimental results performed on the ITC'99 benchmarks show the validity of our approach.

We have three main perspectives to this work. We want to implement a whole test environment with the integration of an automatic test pattern generator, to add the management of structural faults and to generalize this approach to any kind of complex discrete event systems.

Figure 1 :

 1 Figure 1: Data flow of the proposed approach for behavioral fault simulation.

Figure 2 :

 2 Figure 2: Example of a VHDL to DEVS transformation

Figure 3 :

 3 Figure 3: BFS-DEVS simulator architecture

Table 2 :

 2 Fault Simulation Results for ITC'99 benchmarks

		Total Faults Test Sequence Length Detected Faults Coverage (%)
	B01	79	54	73	92.40
	B02	48	56	41	85.45
	B03	134	81	125	93.28
	B04	105	72	95	90.47
	B05	145	102	131	90.34
	B06	95	172	82	86.31
	B07	76	63	63	82.89
	B08	64	70	53	82.81
	B09	68	57	60	88.23
	B10	163	110	150	92.02