Soukayna Ghandour-Haidar

Laurent Ros

Jean-Marc Brossier

Improving the tuning of First-Order Autoregressive Model for the estimation of Amplify and Forward Relay channel

Keywords: Amplify-and-Forward Relay, Channel estimation, Autoregressive model, Kalman Filter, Jakes' spectrum, Bessel function, Auto-correlation, Doppler Frequency

This paper deals with the estimation of the Amplify-and-Forward channel. Considering two widely accepted Rayleigh links with Jakes' spectrum, a first-order autoregressive model AR(1) is used to approximate the cascade of both links. A standard estimation algorithm is the Kalman filter. In this paper, we keep the choice of the AR(1)-Kalman filter, but we show that the method usually exploited in the literature to calculate the AR(1)-model parameter presents some disappointing results. We propose other values of the AR(1)-model parameter to improve the channel estimation, based on an off-line minimization of the asymptotic mean square error MSE for a given Doppler and signal to noise ratio. The simulation results show a considerable gain in terms of MSE of the well-tuned Kalman-based channel estimator, especially for the most common scenario of slowfading channel.

I. INTRODUCTION

Recently, engineers switched to cooperative communications. The principal cause of this switching is the need to exploit spatial diversity at low cost or sometimes in small space. When we talk about cooperative communication, we have to mention the Multiple Input Multiple Output systems due to the relation between them. After the revolution of the MIMO systems, the engineers and researchers proposed a new way to benefit from the MIMO systems, without need of multiple antennas at the source and/or destination. The simplest way to do this is to use one relay, and to send one version of the signal from the unique antenna placed at the source, but to receive at the destination two versions of the signal, from the direct path and the via-relay path. The cooperative communication is then summarized by a network composed of a source, a destination, and one or more relays. There are many types of relays, and the widely used types are the Amplify-and-Forward relay (AF) which amplifies the received signal and retransmits it, and the decode-and-Forward relay (DF) which decodes the received signal, then reencodes and retransmits it. We cite the Estimate-and-Forward relay (EF) [START_REF] Chakrabarti | Half-Duplex Estimate-and-Forward Relaying: Bounds and Code Design[END_REF] and Compress-and-Forward relay (CF) too [START_REF] Akhbari | Compress-and-Forward Strategy for The Relay Channel With Non-Causal State Information[END_REF]. The source-relay-destination and source-destination links should be independent, since their dependency expels the diversity benefits. Moreover, the source-relay and relaydestination links are supposed independent too [START_REF] Patel | Channel Estimation for Amplify and Forward Relay Based Cooperation Diversity Systems[END_REF], [START_REF] Zhou | Kalman Filter-based Channel Estimation for Amplify and Forward Relay Communications[END_REF], [START_REF] Liu | Channel Estimation for Amplify and Forward Relay in OFDM System[END_REF], [START_REF] Nevat | Channel Tracking in Relay Systems via Particle MCMC[END_REF]. Each of the Source-Relay and Relay-Destination links is modeled by a Rayleigh fading channel model with Jakes' Doppler spectrum. This is the most accepted random model that represents temporal variations of the equivalent baseband channel complex gain (CG) [START_REF] Nevat | Channel Tracking in Relay Systems via Particle MCMC[END_REF], [START_REF] Patel | Statistical Properties of Amplify and Forward Relay Fading Channels[END_REF], [START_REF] Baddour | Autoregressive modeling for fading channel simulation[END_REF], [START_REF] Ghandour-Haidar | On the use of first-order autoregressive modeling for Rayleigh Flat Fading Channel Estimation with Kalman filter[END_REF].

To estimate or equalize this channel, it is difficult to use directly this model, because it is not convenient for implementation and for computer simulation. In the literature, the authors of [START_REF] Wang | On verifying the first-order Markovian Assumption for a Rayleigh Fading Channel Model[END_REF] demonstrate that the autoregressive model with order one AR(1) is convenient enough for such correlated fading channel, especially in case of narrowband Doppler fading processes. So usually, the AR(1) model, accompanied with the assumption of zero-mean additive white circular complex Gaussian noise (CAWGN), is used to approach the one-link channel and facilitate its manipulation [START_REF] Baddour | Autoregressive modeling for fading channel simulation[END_REF], [START_REF] Barbieri | On the ARMA Approximation for Frequency Channels Described by the Clarke Model with Applications to Kalman-based Receivers[END_REF], [START_REF] Ghandour-Haidar | On the use of first-order autoregressive modeling for Rayleigh Flat Fading Channel Estimation with Kalman filter[END_REF], [START_REF] Al-Naffouri | An EM-based forward-backward Kalman for the estimation of time-variant channels in OFDM[END_REF]. Up to now, the appropriateness of AR(1) model for the Amplify-and-Forward channel is not demonstrated. Although, the AR(1) model has been used in the literature to model the Amplify-and-Forward channel [START_REF] Zhou | Kalman Filter-based Channel Estimation for Amplify and Forward Relay Communications[END_REF], [START_REF] Nevat | Channel Tracking in Relay Systems via Particle MCMC[END_REF]. This approximation has been used to track the true channel by a Kalman Filter (KF) in various wireless communication systems [START_REF] Zhou | Kalman Filter-based Channel Estimation for Amplify and Forward Relay Communications[END_REF], [START_REF] Barbieri | On the ARMA Approximation for Frequency Channels Described by the Clarke Model with Applications to Kalman-based Receivers[END_REF], [START_REF] Ghandour-Haidar | On the use of first-order autoregressive modeling for Rayleigh Flat Fading Channel Estimation with Kalman filter[END_REF], [START_REF] Al-Naffouri | An EM-based forward-backward Kalman for the estimation of time-variant channels in OFDM[END_REF], and sometimes by other particle filters [START_REF] Nevat | Channel Tracking in Relay Systems via Particle MCMC[END_REF], linear MMSE estimator [START_REF] Patel | Channel Estimation for Amplify and Forward Relay Based Cooperation Diversity Systems[END_REF], [START_REF] Liu | Channel Estimation for Amplify and Forward Relay in OFDM System[END_REF], or least square estimator [START_REF] Liu | Channel Estimation for Amplify and Forward Relay in OFDM System[END_REF]. In this work, we keep using the Kalman filter like in our previous work dealing with one-link channel in [START_REF] Ghandour-Haidar | On the use of first-order autoregressive modeling for Rayleigh Flat Fading Channel Estimation with Kalman filter[END_REF]. The use of an AR(1) model requires a good choice of the AR(1) coefficient. In many papers [START_REF] Zhou | Kalman Filter-based Channel Estimation for Amplify and Forward Relay Communications[END_REF], [START_REF] Nevat | Channel Tracking in Relay Systems via Particle MCMC[END_REF], [START_REF] Al-Naffouri | An EM-based forward-backward Kalman for the estimation of time-variant channels in OFDM[END_REF], the AR(1) coefficient calculation for a given normalized Doppler frequency is based on a same criterion, called Correlation Matching (CM) in this paper. However, the problem of poorly tuned coefficient by Correlation Matching criterion has just recently been pointed out and analyzed in [START_REF] Barbieri | On the ARMA Approximation for Frequency Channels Described by the Clarke Model with Applications to Kalman-based Receivers[END_REF], [START_REF] Ghandour-Haidar | On the use of first-order autoregressive modeling for Rayleigh Flat Fading Channel Estimation with Kalman filter[END_REF] for the case of one-link flat fading Rayleigh channel with Jakes' spectrum. In this paper, we extend our previous one-link work in [START_REF] Ghandour-Haidar | On the use of first-order autoregressive modeling for Rayleigh Flat Fading Channel Estimation with Kalman filter[END_REF] to the case of cooperative communications and more specifically for Amplify-and-Forward channel. This channel is the product of two Rayleigh channels approached with an AR(1) model. The filter used for estimation is the Kalman Filter (KF) and the goal is to minimize the asymptotic variance of estimation error (MAV). So we find numerically the optimal AR(1) coefficient under the MAV criterion, without the CM constraint and compare the performances for both cases. The paper is organized as follows: we first write the mathematical model used to represent the channel in section II. We then find numerically the value of optimal coefficient for the criterion of minimizing the estimation error variance in section III.A. We also emphasize in section III.B and III.C the poor performance with the CM-based method, compared to the proposed method. Moreover, we study the behavior of the optimal MSE for a given Doppler and SNR scenario.

S D R α 1 ¡ ¡ ¡ ¡ ¡ ¡ !

II. MATHEMATICAL MODEL

A. Real Transmission

We consider the estimation of the channel shown in figure 1. It consists of a source S, a destination D, and a relay R placed between them. We suppose that the direct link from source to destination is too poor, and we consider only the via-relay link. We divide our channel into two links, the Source-Relay link and the Relay-Destination link. Each of those links may be subject to be:

• A link where both extremities are mobile • A link where one extremity is fixed while the other one is mobile • A link where both of them are fixed From the different scenarios that derivate, we focus on the mobile-fixed-mobile scenario. The source is moving at a speed of v S , and the destination is moving at a speed of v D . The relay is fixed. We can assume in this case that each link (S -R and R -D) is a flat fading Rayleigh channel with Jakes' spectrum (Clarkes' model [START_REF] Akki | A Statistical Model of Mobile-to-Mobile Land Communication Channel[END_REF]), characterized by a complex gain CG α 1 and α 2 respectively, varying from one symbol to another, but we assume that the CG variation can be neglected during one symbol period. The variance of those gains are σ 2 α 1 and σ 2 α 2 respectively. For a sampling rate of T , the normalized Doppler frequency of the S -R link is f d1 T , where f d1 = v S λ , and the normalized Doppler frequency of the R-D link is f d2 T , where

f d2 = v D λ .
λ is the wavelength of the analog emitted signal. A Jakes' Doppler spectrum is assumed for the S -R link (the same will be for the R -D link by replacing f d1 by f d2 and σ 2 α 1 by σ 2 α 2 ):

Γ α 1 ( f ) =      σ 2 α 1 π f d1 √ 1- ( f f d1 ) 2 if | f | < f d1 0 if | f | > f d1 (1)
The autocorrelation coefficient for the k th tap of S-R link is given by: R α

1 [k] = σ 2 α 1 J 0 (2π f d1 T k) (2)
where J 0 is the zeroth-order Bessel function of the first kind.

The same holds for the R -D link.

The source sends the signal s k . The relay receives the signal r k , amplifies it with a factor of A called relay gain, and retransmits the amplified signal A.r k to the destination. The destination receives the signal y k at the end. Since the gain of both links is constant during the period of the symbol, we observe a sampled and noised signal ( sampling at rate T ).

r k = s k α 1k + n 1k ( 3
)
y k = Ar k α 2k + n 2k (4)
where n 1k and n 2k , k = 1, 2, ... are Complex Additive White Gaussian Noises (CAWGN), with variances σ n 1 2 and σ n 2 2 respectively.

The observation equation will be then

y k = s k α k + n k ( 5
)
where

α k = Aα 1k α 2k and n k = Aα 2k n 1k + n 2k , leading to σ α 2 = A 2 σ α 1 2 σ α 2 2 (6) and σ n 2 = A 2 σ α 2 2 σ n 1 2 + σ n 2 2 (7)
The Gain A is implicitly determined from the desired/required signal-to-noise ratio in the second link (SNR 2 ) defined below, which is related to the energy of symbols emitted given σ 2 α 1 , σ 2 α 2 , σ 2 n 1 and σ 2 n 2 . The signal s k is transmitted from the source with energy E 1 . The energy E 2 of the signal Ar k transmitted from relay is then

E 2 = A 2 (E 1 σ α 1 2 + σ n 1 2 ) (8)
The signal-to-noise ratio for the S-R link, R-D link, and all the channel are respectively given by :

γ 1 = E 1 σ α 1 2 σ n 1 2 (9) γ 2 = E 2 σ α 2 2 σ n 2 2 (10) γ = E 1 σ α 2 σ n 2 = γ 1 γ 2 γ 1 + γ 2 + 1 ( 11
)
And the corresponding values in (dB) are: Both links are supposed independent. This leads to a total Doppler spectrum and total autocorrelation function [START_REF] Akki | A Statistical Model of Mobile-to-Mobile Land Communication Channel[END_REF], [START_REF] Nevat | Channel Tracking in Relay Systems via Particle MCMC[END_REF]:

SNR 1,2 = 10log 10 γ 1,2 (dB) SNR = 10log 10 γ (dB)
Γ α ( f ) = AΓ α 1 ( f ) * Γ α 2 ( f ) (12) R α [k] = A 2 R α 1 [k]R α 2 [k] = A 2 σ 2 α 1 σ 2 α 2 J 0 (2π f d1 T k)J 0 (2π f d2 T k) (13)
We design by * the convolution product.

B. First-order autoregressive dynamical model

In the literature, the time-varying CG α k is often approached by a first-order autoregressive (AR(1)) model αk : αk = a. αk-1 + e k [START_REF] Kay | Fundamentals of Statistical Signal Processing -Estimation Theory[END_REF] where e k is a white circular complex Gaussian noise with variance σ 2 e = (1-a 2 )σ 2 α . The observation equation ( 5) is then approximated by:

y k = s k αk + n k (15)
The AR(1) coefficient verifies

a = R α [1] R α [0] (16)
In the literature, the correlation matching (CM) criterion is usually imposed [START_REF] Zhou | Kalman Filter-based Channel Estimation for Amplify and Forward Relay Communications[END_REF], [START_REF] Nevat | Channel Tracking in Relay Systems via Particle MCMC[END_REF]. It means that the autocorrelation of the exact channel gain α and the AR(1) approached process α coincide for the first two coefficients (i.e., R α

[0] = R α [0] = A 2 σ 2 α 1 σ 2 α 2 , and R α [1] = R α [1]
), and using equation ( 16) and (13) the AR(1) coefficient a noted a CM becomes

a CM = J 0 (2π f d1 T )J 0 (2π f d2 T ) (17)
The figure 2 shows the autocorrelation functions for both dual Rayleigh link and AR(1)-CM cases, at two values of Doppler frequencies. When the channel is varying slowly, that means when we have low Doppler frequencies (right figure, with f d1 T = f d2 T = 10 -3 ), we see that the AR(1)-CM autocorellation function seems to stay constant, since the AR(1) coefficient a CM ≈ 1 (see eq. ( 17), with J 0 (ε) ≈ 1 when 0 ≤ ε << 1). Then, the matching is less convincing in case of low frequencies, contrary to the situation with high frequencies where the autocorrelation function is less out of tune (left figure, with f d1 T = f d2 T = 10 -1 ). Based on this observation, we will not consider the CM criterion to compute the AR [START_REF] Patel | Channel Estimation for Amplify and Forward Relay Based Cooperation Diversity Systems[END_REF] parameter in the present study but a variance criterion, as already proposed for the one-link channel in [START_REF] Barbieri | On the ARMA Approximation for Frequency Channels Described by the Clarke Model with Applications to Kalman-based Receivers[END_REF] and [START_REF] Ghandour-Haidar | On the use of first-order autoregressive modeling for Rayleigh Flat Fading Channel Estimation with Kalman filter[END_REF]. The choice of the AR(1) parameter a will then be based on minimizing the asymptotic estimation error variance (MAV) as developed in the section III.A, and we will call it a MAV .

C. Kalman filter (KF)

Given the model and observation equations ( 14) and (15), we use a KF to get an on-line unbiased estimate, αk , of the true α k . The error is

ε k = α k -αk , with variance MSE = E{|ε k | 2 }.
In this work, we concentrate of the performance of the channel estimator. So we treat a simplified case assuming the symbols are known (pilot-aided scenario) or perfectly decided (decision-directed scenario), thus we assume s k = 1. Note that in practice, our channel estimator can be easily coupled with a detector in order to perform joint channel estimation and decision tasks, for example via the Expectation-Maximization algorithm framework (see [START_REF] Al-Naffouri | An EM-based forward-backward Kalman for the estimation of time-variant channels in OFDM[END_REF]).

The KF for this simplified case is given by (see p. 436 in [START_REF] Kay | Fundamentals of Statistical Signal Processing -Estimation Theory[END_REF]):

Prediction αk|k-1 = a αk-1 (i) Prediction MSE P k|k-1 = a 2 P k-1 + σ 2 e (ii) Kalman Gain K k = P k|k-1 σ 2 n +P k|k-1 (iii) Correction αk = αk|k-1 + K k (y k -αk|k-1 ) (iv) MSE P k = (1 -K k )P k|k-1 (v)
Replacing (ii) in (iii), (v) in (ii), and (i) in (iv), we obtain the simplified system:

K k = [a 2 P k-1 + σ 2 e ]/[a 2 P k-1 + σ 2 e + σ 2 n ] (18)
P k = (1 -K k )(a 2 P k-1 + σ 2 e ) (19) αk = a αk-1 + K k (y k -a αk-1 ) (20)
where K k is the Kalman gain at iteration k and P k is the estimation error variance. Without loss of generality, we assume

E 1 = 1 and σ 2 α 1 = σ 2 α 2 = 1. Given (6), σ α 2 = A 2
For the special case where σ 2 n 1 = σ 2 n 2 , given (7)

σ 2 n = A 2 σ 2 n 1 + σ 2 n 2 = σ 2 n 1 (A 2 + 1)
So for this case, and given [START_REF] Ghandour-Haidar | On the use of first-order autoregressive modeling for Rayleigh Flat Fading Channel Estimation with Kalman filter[END_REF], we have

γ = A 2 σ 2 n 1 (A 2 + 1) = γ 1 A 2 A 2 + 1 (21)
We clearly see that γ < γ 1 .

III. SIMULATION AND RESULTS

We present Monte Carlo simulations to demonstrate the channel estimation error variance of AF relaying. We apply the Kalman filter for the CM case where a = a CM , and calculate the corresponding error variance MSE CM as first step. As a second step, we apply the AR(1) Kalman filter for many other cases where a is taken manually, and found the MSE for each case. At the end, we choose the optimal value of a, denoted a MAV 1 , that minimizes the MSE. In our simulations, we are in the special case of σ 2 n 1 = σ 2 n 2 , and we take A = 1. Then σ 2 n = 2σ 2 n 1 and γ = γ 1 2 , similarly to say SNR = SNR 1 -3dB where SNR 1 is the signal to noise ratio for the S-R link.

A. Tuning of the AR(1)-parameter

The figure 3 shows the error variance in function of ε = 1a. We see that at low frequencies, the minimum value of MSE is attended for ε MAV >> ε CM , i.e, for a MAV < a CM while we can see that this difference is more reduced when the Doppler frequency and/or the SNR increase. Comparing the values of the MSE in the "valley" (i.e. in the minimum region) and the one obtained with CM criterion, MSE CM , we observe that the CM criterion is far from optimal, leading to a strong loss in performance in terms of MSE. The strict minimum is noted MSE MAV , from which we can measure the related AR(1)-parameter, a MAV . In tables I and II, we can compare the values of a MAV and a CM . It is clear, especially for low Doppler frequencies, that the CM coefficient is higher than the optimal coefficient. Thus, when we are in the optimal case, the AR(1)-based autocorrelation curve decreases more rapidly to zero and approaches better the values of the Bessel-based autocorrelation function [START_REF] Al-Naffouri | An EM-based forward-backward Kalman for the estimation of time-variant channels in OFDM[END_REF] than it was in figure 2 for the CM case.

a CM a MAV f d1 T = 1e -4 f d1 T = 1e -3 f d1 T = 1e -2 f d2
SNR = 0 dB a CM a MAV f d1 T = 1e -4 f d1 T = 1e -3 f d1 T = 1e -2 f d2 T = 1e -4 0.
In figure 4, we have plotted the state noise variance σ 2 e used in the Kalman filter as a function of f d T . We recall that the state noise variance is related to the AR(1)-parameter a by σ 2 e = (1-a 2 )σ 2 α . We can measure by this figure how much the state noise variance of the CM criterion is too weak compared to the optimal value (MAV criterion), leading about a factor 100 for f d T = 10 -4 , and about a factor 10 for f d T = 10 -2 .

It should be noted that the variation of σ 2 e CM versus f d T in a log/log scale is linear with a slope of 2 (i.e. 20 dB/decade). It can be explained analytically by an approximation of the Bessel function :

[J 0 (2π f d T )] 2 ≈ 1 -(2π f d T ) 2 /2 when 2π f d T << 1, leading to σ 2 e CM σ 2 α = 1 -a 2 CM ≈ (2π f d T ) 2 .

B. Same Doppler frequencies

In this case, we suppose the source and the destination moving at the same speed. We note f d1 T = f d2 T = f d T .

In figure 5, we plot the error variance for Correlation Matching case (MSE CM ) in function of SNR, and compare it to the minimum error variance we reached (MSE MAV ). The plots are dressed for different Doppler frequencies f d T . We see that MSE CM dB and MSE MAV dB varies linearly with SNR 1 dB. We deduce then that MSE MAV = K.γ β . Graphically, we can calculate the coefficient β

β = ∆[log 10 (MSE MAV )] ∆[log 10 (γ)] = 10 ∆[log 10 (MSE MAV )] ∆[SNR]
We obtain β ≈ -0.67 ≈ - 2 3 In figure 6, we plot the error variance for Correlation Matching case (MSE CM ) in function of f d T , and compare it to the minimum error variance we reached (MSE MAV ). The plots are dressed for different SNR. We see too that MSE MAV dB vary linearly with log 10 ( f d1 T ) = log 10 ( f d2 T ) = log 10 ( f d T ), while MSE CM seems constant with respect to f d T . In the same way, we can say that MSE MAV = K ′ .( f d T ) ζ and we calculate graphically the coefficient ζ . We obtain

ζ = ∆[log 10 (MSE MAV )] ∆[log 10 ( f d T )]
We obtain ζ ≈ 0.69 ≈ 2 3 . in our simulations, we can say that

MSE MAV = C.( f d T × σ 2 n ) 2 3
where C is a constant value. It is noteworthy that this optimal MSE for the AR(1) Kalmanbased estimation of the mobile-fixed-mobile relay channel (with two Clarkes' models) seems to take the same form than the one obtained for the one-link Clarkes'model channel established in [START_REF] Ghandour-Haidar | On the use of first-order autoregressive modeling for Rayleigh Flat Fading Channel Estimation with Kalman filter[END_REF], eq. (25) (i.e. with the same (2/3) power of f d T × σ 2 n ).

C. Different Doppler frequencies

In this case, we suppose the source and the destination moving at different speeds. The same reasoning persists. The minimum error variance MSE MAV increases with f d1 T and f d2 T , and with SNR, as can be observed in figure 6.

D. BER performances

Until now, all the performances are dressed in terms of MSE. Finally, we have a look at the consequences in terms of Bit Error Rate (BER) in figure 8. This figure refers to a binary PSK (BPSK) transmitted over an Amplify-and-Forward dual Rayleigh fading channel with f d1 T = f d2 T = 10 -3 . In order to ensure convergence of the iterative detection and decoding algorithm, 10 pilot symbols (known at the receiver) every 100 code symbols is placed in the transmitted codeword 2 . So we 2 To use the KF equations in (18), ( 19) and (20), which are given for known symbols case, i.e. for s k = 1 in (15), and since we have s k ∈ {-1; +1}, the KF equations are modified by substituting y k with y k × ŝ * k|k-1 where ŝk|k-1 = s k if s k is known (pilot) or ŝk|k-1 = sgn { ℜ( α * k-1 × y k ) } if s k is unknown (data). In this case, ŝk|k-1 represents the a priori decision, and the final decision will be ŝk = sgn { ℜ( α * k × y k ) } .

IV. CONCLUSION

This paper addresses the problem of estimating an Amplifyand-Forward channel using a first-order AR(1) model. Simulations show that the most widely used choice for the AR(1) pole estimation (the CM criterion) is not accurate for low SNR and low Doppler f d T . Therefore, varying the value of the AR(1) coefficient, we carry out the optimization of the AR(1) model. It is demonstrated graphically that the MSE MAV of the AR(1) KF is proportional to the (2/3) power of the product ( f d T × σ 2 n ), where σ 2 n is the observation noise variance.

Figure 1 .

 1 Figure 1. Relay-channel system model

Figure 2 .

 2 Figure 2. Comparison of the auto-correlation functions of the true process α (continuous line) and the approached AR(1) process α for high and low Doppler frequencies (respectively left and right figures)

Figure 3 .

 3 Figure 3. MSE in function of ε = 1a for different Doppler frequencies f d1 T = f d2 T = f d T . The ⋆ indicates the position of MSE CM and the corresponding 1a CM .

Figure 4 .

 4 Figure 4. State noise variance σ 2 e /σ 2 α = 1a 2 used in the AR(1)-model in function of Doppler frequency for MAV and CM cases

Figure 5 .

 5 Figure 5. Comparison between MSE CM and MSE MAV in function of signalto-noise ratio for different Doppler frequencies

Figure 6 .Finally, and given γ = 1 σ 2 n

 62 Figure 6. Comparison between MSE CM and MSE MAV in function of Doppler frequency for different signal-to-noise ratio

Figure 7 .

 7 Figure 7. MSE MAV in function of Doppler frequencies for high and low signal-to-noise ratios SNR

Figure 8 .

 8 Figure 8. BER in function of SNR for f d T = 10 -3

Table II COMPARISON

 II BETWEEN a CM AND a MAV FOR DIFFERENT DOPPLER FREQUENCIES AT SNR = 20 dB

		9999998	0.9999900	0.9990131
		0.9999800	0.9998000	0.9960000
	f d2 T = 1e -3	0.9999900 0.9998000	0.9999802 0.9997000	0.9990034 0.9950000
	f d2 T = 1e -2	0.9990131 0.9960000	0.9990034 0.9960000	0.9980275 0.9930000

Note that once the values of a MAV for different values of SNR and Doppler frequencies are stored in tables, we can use them for the on-line estimation.


Valérie Hanoka
email: valerie.hanoka@inria.fr

Benoît Sagot
email: benoit.sagot@inria.fr

Wordnet creation and extension made simple: A multilingual lexicon-based approach using wiki resources

Keywords: WordNet, Word Sense Disambiguation, Wiki resources

In this paper, we propose a simple methodology for building or extending wordnets using easily extractible lexical knowledge from Wiktionary and Wikipedia. This method relies on a large multilingual translation/synonym graph in many languages as well as synset-aligned wordnets. It guesses frequent and polysemous literals that are difficult to find using other methods by looking at back-translations in the graph, showing that the use of a heavily multilingual lexicon can be a way to mitigate the lack of wide coverage bilingual lexicon for wordnet creation or extension. We evaluate our approach on French by applying it for extending WOLF, a freely available French wordnet.

Introduction

In recent years, researchers working on languages other than English have tried to compensate for the lack of digital lexical databases such as the Princeton WordNet (PWN) (Fellbaum, 1998). Since manual taxonomy creation is a costly investment, automatic wordnet creation and extension has become a field of interest. Many methods have been developed for creating or extending wordnets in a growing number of languages. In this paper, following previous work, we introduce a technique that leverages existing wordnets using multilingual lexical resources extracted from Wiktionaries and the Wikipedia. We apply it for extending the free French wordnet WOLF [START_REF] Sagot | Building a free french wordnet from multilingual resources[END_REF][START_REF] Sagot | Automatic extension of WOLF[END_REF].

Related work

The question of multilinguality for bootstraping wordnets arose soon after the release of the PWN [START_REF] Vossen | EuroWordNet: a multilingual database with lexical semantic networks[END_REF] and still is an active research area [START_REF] Pianta | Multiwordnet: developing an aligned multilingual database[END_REF]Tufiş et al., 2004a;[START_REF] Diab | The feasibility of bootstrapping an arabic wordnet leveraging parallel corpora and and an english wordnet[END_REF][START_REF] Sagot | Building a free french wordnet from multilingual resources[END_REF][START_REF] De | Towards a universal wordnet by learning from combined evidence[END_REF][START_REF] Navigli | Babel-Net: Building a Very Large Multilingual Semantic Network[END_REF]. Multilingual approaches using the PWN as a reference for the creation of new wordnets in other languages tend to rely on the use of a similar synset inventory. Due to conceptual discrepancies between languages, finding a good translation for a given literal is not always easy. Following works of [START_REF] Resnik | A perspective on word sense disambiguation methods and their evaluation[END_REF] and [START_REF] Ide | Sense discrimination with parallel corpora[END_REF] on multilingual sense disambiguation, [START_REF] Dyvik | Translations as semantic mirrors: from parallel corpus to wordnet[END_REF] proposed to find accurate translations of synsets literals by looking at bilingual parallel corpora. [START_REF] Pianta | Multiwordnet: developing an aligned multilingual database[END_REF] used bilingual (back-)translations and contextual information (gloses) in order to ease lexicographers' work for the Italian MultiWordNet construction. [START_REF] Sagot | Building a free french wordnet from multilingual resources[END_REF] merged the results of two different approaches for synset filling: translations extracted from parallel corpora in 5 languages and bilingual lexicons extracted from freely available resources.

Beyond traditional wordnet extension/creation, some authors proposed to overcome the difficulty of constructing new wordnets for a bunch of languages other than English by using wiki resources: [START_REF] Navigli | Babel-Net: Building a Very Large Multilingual Semantic Network[END_REF] made the link between multilingual encyclopedic knowledge from Wikipedia and multilingual wordnet creation using the PWN as a seed wordnet. de [START_REF] De | Towards a universal wordnet by learning from combined evidence[END_REF] used machine learning technique over a multilingual knowledge graph (derived from mono-and bi-lingual resources) and a set of existing wordnets to build a large scale universal wordnet.

Methodology

Following the precepts of multilingual word sense disambiguation initiated by [START_REF] Dagan | Two languages are more informative than one[END_REF], we defend the idea that using a heavily multilingual lexicon is a way to mitigate the lack of wide coverage bilingual lexicon for wordnet creation or extension. Our strategy can be sketched as follows. First, we extract a largely multilingual translation and synonym lexical database. Then, using synset-aligned multilingual wordnets, we rank translation candidates in order to favour most plausible candidates for each synset. In this section, we describe these two steps in more details. In the next sections, we report on our experiments for extending the automatically developed French wordnet WOLF using this approach, and evaluate the results.

Building and filtering a large-scale multilingual translation graph

The first step of our methodology consists in extracting a directed translation and synonym graph from a set of Wiktionaries and Wikipedia articles (using inter-wiki links) in as many languages as possible. The use of directed edges prevents pervasive effects of erroneous translations in the graph. For the sake of the explanation, the resulting graph G will be referred to as the translation graph, synonymy links being treated as 'translations' from a language to the same language. As this method relies on heavy multilingualism, translations for languages we did not aim to extract are kept. For a broad group of languages, developing a simple parser for Wiktionary and Wikipedia dumps is possible. However, due to the collaborative nature of the wiki resources and the lack of a formal meta-syntax, resulting translation/synonym lists are noisy. What is more, depending on the number of languages considered for the extraction, the translation graph G may quickly become very large. It is therefore necessary to filter this list.

The filtering heuristic we used is twofold.

• We remove redundant translation pairs. This step filters true duplicates and translations of various senses of the input word into a same word;

• We remove translations that involve (word, language) pairs that are not present in at least n translations. In our experiments, we found that n = 3 offered a good trade-off between the reliability of translations and the resulting graph's coverage. This first step filters out pairs that are too isolated to be used by a multilingual approach, and allows for filtering most noise introduced by errors in the input resources. After this run, each node in the translation graph necessarily has a minimum degree of 3;

We now have built our highly-multilingual directed translation graph G. Each of its nodes represents a (word/term, language) pair.

Filling or extending synsets

As our system is designed to fill wordnet synsets using the extension approach, it requires as an input synset-aligned wordnets in m different languages (ideally with m ≥ 3).

As a reminder, we shall denote by the term synset the union of all literals present in the synsets of all input wordnets that correspond to a same id. Consistently with this definition, we shall call literal a triplet of the form (word/term, language, weight). For the sake of simplicity, we shall also consider that the nodes of the translation graph G represent a literal, although with a non-specified weight.

The algorithm for filling synsets we shall now present, and whose structure in pseudo-code is given in Algorithm 1, operates on a per-synset basis. It takes advantage of the directionality of the graph and simply uses the principle of back-translation in order to rank candidates.

The general idea, applied on each synset, is as follows. We start from an initial multilingual set Γ 0 filled with the literals from our input wordnets, our gold literals associated with a gold weight w = 100. Starting from this set Γ 0 , we use the translation graph G to build a set Θ 1 of candidate literals. We then put together the candidate literals from Θ 1 and the literals in Γ 0 , thus creating a new multilingual set Γ 1 . This Γ 1 might in turn be the input of the algorithm, thus creating a new multiligual set Γ 2 via a new set Θ 2 of candidate literals, and so on. Now, let us describe our algorithm in a more formalized way. At each step, and for a given synset, we start from an

Algorithm 1 Back-Translation Algorithm Require: Γ h ; a, b ∈ N; a < b for (γ i , l i , σ i ) ∈ Γ h do Θ ← GETTRANSLATIONSFOR(γ i , l i ) for (θ j , l j , ω j ) ∈ Θ do ω back ← 0 B ← GETTRANSLATIONSFOR(θ j , l j ) for (β k , l k , k )inB do if β k ∈ Γ h then σ β k ← GETSCOREINΓ h (β k ) if σ β k ≥ w then ω back + = a else if σ β k ≥ w/5 then ω back + = b else if σ β k < w/50 then ω back -= b end if end if end for if θ j ∈ Γ h then ω j ← ω j +GETSCOREINΓ h (θ j ) end if ω j ← ω j + ω back end for end for Γ h+1 ← MERGESETS(Γ h , Θ) return Γ h+1
input multilingual set, the set of source literals. These literals, of the form (γ i , l i , σ i ), are gathered in the input multilingual set Γ. The algorithm uses Γ to query the translation graph G in order to propose a new multilingual set Θ of candidate literals of the form (θ j , l j , ω j ). The candidate literals in Θ are then used to inflate Γ, under certain conditions.

In the reminder, we shall not explicit the difference between a node in G and the literal it represents. We defined the language degree of a vertex γ i in the translation graph G with regard to a language l, noted deg l (γ i ), as the number of outgoing edges in G incident to γ i leading to literals in the language l. For instance, in fig. 1 For each γ i that belongs to the set S of source literals, we add in Θ all translations of γ i in any language found in our translation graph. Apart from its language l, each of these Figure 2: Log-number of translations from source to target language contained in the translation graph after filtering. literals θ i ∈ Θ is assigned a weight ω i , initialized to the inverse of deg l (γ i ). This weight is then updated heuristically according to the quality of its back-translations. Let B be the set of backtranslations of all θ i 's, i.e., translations of the θ i 's that belong to the set S of source literals. For each β i ∈ B with weight i :

, deg tr (table en ) = 2 and deg id (table en ) = 1.
• if i ≥ w, we add a back-translation bonus a to ω i ;

• if i ≥ w
5 , we add a reduced back-translation bonus b to ω i ; As explained above, this algorithm might be repeated several times, taking the output multilingual set of one step as the input multilingual set of the next one. In our experiments, we executed it twice. After having applied this algorithm twice on each synset, we enriched all synsets in our input worndets and produced an expanded wordnet in which each (literal, synset) pair has retained its final output weight. This allowed for filtering out new (literal, synset) pairs that have a score lower than a certain threshold.

• if i < w 10 ,
Before we illustrate this algorithm on an example, we now provide details about our experiments.

Experiments

We extracted translation/synonym pairs from a set of Wiktionaries in 18 languages (Czech, Dutch, English, French, German, Hebrew, Indonesian, Italian, Japanese, Korean Polish, Portuguese, Romanian, Russian, Slovak, Spanish, Swedish and Turkish) and the French Wikipedia. The first raw extraction step resulted in 9,916,345 translations pairs and 748,385 synonymy pairs. After filtering 1,584,370 (16%) translations pairs and 366,826(49%) synonymy pairs remained. The average degree (both directions) of the translation graph is 3.522.

Figure 2 shows the number of translations pairs before and after filtering for each language.

For our experiment, we used the PWN 2.0 for English, and the BalkaNet wordnets for Czech, Bulgarian and Romanian (Tufiş et al., 2004b) which are aligned to the PWN 2.0. However, we did not use the French WOLF, in order to compare our approach to those used for developing this resource.

Here is an example of the algorithm applied to synset ENG20-01562015-a {obedient}. Table 1 presents the aligned synset after completion.

For this example, we have Γ = {(inequality, en, 100), (imparitate, ro, 100), (inegalitate, ro, 100), (HepaBeHcTBo, bg, 100)} for the first run.

Translations for inequality(en) result in 7 candidates literals in 6 different languages (de, it, fr, sv, en, es). Among them, three candidate literals gain the backtranslation bonus a: Ungleichung(de), inégalité(fr), olikhet (sv).

No translations were found for imparitate(ro), inegalitate(ro) and HepaBeHcTBo(bg).

English

Results and evaluation

Retaining only candidates with a score greater than 30, we created 10, 568 (literal, synset) candidates, among which as many as 6, 119 (58%) are not included in the WOLF. Table 2 show a random sample of these (literal, synset) candidates, associated with PWN literals and definition for the synset, the score of the candidate, our manual evaluation (YES if it is correct, NO otherwise), as well as information about whether this candidates was already included in the WOLF (YES if it was in the WOLF, NO otherwise). For evaluating our approach, we put together all (literal, synset) pairs we produced as well as all WOLF (literal, synset) pairs for synsets for which we generated at least one candidate. We performed a manual evaluation of 400 of these (literal, synset) pairs by assigning a boolean score (correct/incorrect) to all such pairs for a random sample of the synsets.

We evaluated our approach according to two parameters. The first one, t, is a threshold on the score associated by our approach to each candidate: setting the threshold at 30 retains all candidates, whereas setting it at a higher value discards all candidates with a lower score. The second parameter n max is an upper bound on the number of candidates retained for each synset: if this parameter is set to 3, the candidates for a given synset are sorted by decreasing score, and at most the first 3 candidates are retained (less than 3 if scores fall below t).

For each value of t and each value of n max we evaluate:

• the precision of our candidates, the ratio of correct candidates w.r.t. the total number of candidates; if we retain all 10, 568 candidates (i.e., t = 30 and n max = ∞), the precision is 74.1%;

• an estimation of the number of correct candidates we obtain, computed as the total number of candidates times the precision figure; again, if we retain all candidates, we can thus expect around 10, 568 × 0.741 = 6, 465 candidates; among them, 6, 119 are not in the WOLF, and their precision is 65%; this shown that not only our approach generated candidates not generated by previous approaches, but these candidates have a high precision as well; still, using more strict parameters can improve this precision figure (see below);

• an approximate "recall", measured w.r.t. these 6, 465 correct candidates that are kept if we retain them all (i.e., with t = 30 and n max = ∞);

• an approximate "f-score" based on the precision and "recall" figures.

Table 3 shows the precision figures and associated number of candidates that we obtain with different sets of parameter values. The outcome of these evaluations can be summarized as follows. First, as expected, increasing n max or t decreases the number of candidates but increases the precision. For n max = 1 and t = 50, the precision reaches 86% over 3, 353 candidates. Among them, 1, 601 candidates are not present in the WOLF, and the precision on these candidates is as high as 82%. On candidates already in the WOLF, the precision is over 89%, vs. 87% on all (literal, synset) pairs from the WOLF. However, such parameter values are quite restrictive. Based on the "f-score" figures, the optimal parameter values are (t = 30, n max = 3) With such values, we retain 10, 403 candidates (almost all of them) with a 74, 8% precision (slightly but significantly higher than with n max = ∞. A manual validation of all these candidates would add around 7, 781 correct candidates in the WOLF. As can be seen on Table 3, precision figures consistently correlate with t and with n max , which shows the relevance of the score computed by our algorithm. As a consequence, higher t values associated with n max = 1 lead to higher precision figures. For example, parameter values (t = 60, n max = 1) lead to as high a precision as 90, 5%, still retaining 2, 245 candidates among which around 2, 031% correct ones. Chosing (t = 30, n max = 3) as parameters, we performed a manual examination of correct generated candidates that are not in the WOLF. In almost all cases, these candidates correspond to high or medium frequency words that are polysemic, sometimes highly polysemic. In other words, these candidates correspond to the most useful information in any wordnet-based application, but also to cases for which previous approaches used for developing the WOLF performed the least satisfyingly: the alignment-based approach used for disambiguating polysemous words [START_REF] Sagot | Building a free french wordnet from multilingual resources[END_REF] was highly corpus-dependant and could not cover well medium frequency words; the lexicon-based approach was first restricted to monosemous words [START_REF] Sagot | Building a free french wordnet from multilingual resources[END_REF], and later efforts towards its use on polysemous words [START_REF] Sagot | Automatic extension of WOLF[END_REF] did not perform well on highly polysemous words. Examples of literals not present at all in WOLF but covered by our candidates include as basic and frequent words as manger 'eat', taper 'hit', lent 'slow', faim 'hunger' or dehors outside'.

Conclusion and perspectives

The method presented in this paper consists in extending/bootstraping synset-aligned wordnets simply by looking at back-translations found in a large multilingual translation graph extracted from a set of wiki resources in as many languages as possible. It is well suited for creating or enriching WordNets for languages that have at their disposal large or medium coverage Wiktionary and Wikipedia. An interesting point would be to determine if, for languages with smaller wiktionary and/or wikipedia, the use of larger wiktionaries for other languages and/or the improvement of translation graph can prove to be sufficient for a good quality extension. We plan to improve current results by upgrading the translation graph's quality as in [START_REF] Mausam | Compiling a massive, multilingual dictionary via probabilistic inference[END_REF] and computing scores for candidate literals by doing a march in the translation graph.

Figure 1 :

 1 Figure 1: An illustrative snippet of a node and some of its neighbours in the translation graph

  we subtract the reduced back-translation bonus b to ω i ; Different bounds and bonus values can be tried. For our experiment, we choose empirically a = w 10 and b = w 50 Once the set Θ of candidate literals is produced, we create a new multilingual set Γ by taking the union of the input multilingual set Γ and the content of Θ.

Table 1 :

 1 Synset ENG20-04543367-n aligned in different languages after completion. Bold words represents gold literals. Candidate literals are followed by their score. Empty column for Czech is omitted here.

		Romanian	Bulgarian	French
	inequality	imparitate HepaBeHcTBo
	triangle inequality(2.0) inegalitate		inégalité (12.0)
	dissimilarity(1.5)			dissemblance (1.0)
				inéquation (1.0)
	The preceding step results in a bigger Γ set whose cardinal
	is now |Γ| = 11, as 7 candidates literals have been added.
	For the second run of the algorithm:
	Translations for inequality(en) result in updating the
	scores of the 7 candidate literals added during last run,
	adding bonus to the same trio as before.
	Translations for new item Ungleichheit(de) whose score
	is 0.8 result in updating scores for 1 literal. Four new
	candidate literals are added in 4 languages (tr, fr, en,
	ru), among which one gain the a bonus (eşitsizlik(tr)).

Translations for new item Ungleichung(de) whose score is 11.0 result in updating scores for 1 literal. Two new candidate literals are added in 2 languages (fr, ru), among which one gain the a bonus (inéquation(fr)).

Translations for new item inégalité(fr) whose score is 12.0 result in updating scores for 2 English literals.

Translations for new item olikhet(sv) whose score is 12.0 result in updating scores for 1 literal, and add a new candidate literal in Swedish with no bonus.

No translations were found for HepaBeHcTBo(bg) and the other 5 candidate literals added during the first run.

The final result, as showed in table 1, managed to guess related candidate literals for French and English. The most accurate French candidate (inégalité) receive by far the best score among other French candidates (inéquation, dissemblance). Concerning the English candidates, poor scores show that they did not gain any bonus during the process, and should probably not be accepted in the synset.

Table 2 :

 2 Examples of (literal, synset) candidates produced by our algorithm

		t = 30	t = 40	t = 50	t = 60
	nmax = 1	8362/77.3	5340/81.5 3353/85.6 2245/90.5
	nmax = 3	10403/74.8 6298/80.6 3890/85.1 2582/89.6
	nmax = ∞ 10568/74.1 6357/80.3 3917/85.2 2594/89.6

Table 3 :

 3 Number of (literal, synset) candidates retained when using different values for the thresholds t and n max , with the corresdonding precision measure.


R P Bastos

G Di Natale
email: dinatale@lirmm.fr

M L Flottes
email: flottes@lirmm.fr

B Rouzeyre
email: rouzeyre@lirmm.fr

Timing Issues of Transient Faults in Concurrent Error Detection Schemes

Keywords: transient faults, soft errors, fault attacks, concurrent error dectection codes, fault tolerance, and security I

This work reveals additional timing difficulties by which concurrent error detection (CED) schemes can experience to deal efficiently with transients. It shows previously-unknown error scenarios where short-duration single transient faults in combinational logic circuits succeed in erroneously inverting stored results but CED schemes fail in detecting even single soft errors. The paper demonstrates that typical CED code-based schemes for protecting logic circuits are not as capable as they have been claimed whether flip-flops are used to register the error signals, and so timing conditions are suggested for a more efficient use of them.

INTRODUCTION

IC-based systems are liable to encounter transient voltage variations induced by environmental or even intentional perturbation events. These effectsso-called transient faults (TFs)are able to produce soft errors (SEs) by wrongly inverting stored results of circuit's operations, and so they can also make failure scenarios in fault-tolerance applications. Moreover, SE-succeeded TFs can be used as a form of faultbased attack to infer secret data during the execution of encryption operations in security applications.

Related researches until the end of 20th century were focused essentially on protecting systems against TFs arisen in memory elements, which were considered the system's most vulnerable circuits. Hence, many concurrent error detection and/or correction mechanisms were thus proposed to mitigate direct SEs induced by TFs originated in memory circuits. Nevertheless, in the last decade IC-fabrication deepersubmicron technologies as well as novel classes of malicious fault injection-based attackse.g. differential fault analysis (DFA)have also pushed on the use of countermeasures against indirect SEs arisen from TFs in system's combinational logic circuits.

A TF in a system works like an extra primary input of the system's circuit. Actually, it is such as a perturbation input that can be localized in any system's part and can be fed at any instant by any kind of transient shape. Most specifically, a TF is like an asynchronous input of a certain target circuit, which is normally synchronous in most typical design cases. Therefore, a "TF-created unexpected asynchronous input" can easily violate or even cover the latching windows (LWs) of flip-flops (FFs)i.e. a minimum period (defined as LW = setup time + hold time) for which synchronous circuits' data must be on steady state, otherwise they would not be properly sampled. LWs make circuit's internal synchronous operations very sensitive to SE-succeeded TFs.

The traditional solution to face this issue is adding information, spatial, or time redundancy to the circuit. So if for instance a circuit's original part fails, another redundant copy permits detecting or even correcting produced errors. In theory, such redundancy-based schemes cope very efficiently with scenarios of single SEs caused by short-duration Single TFs (i.e. STFs that last less time than a clock period), and they may not operate properly under long-duration STFs, multiple TFs, or multiple SEs. However, we reveal in this paper that timing features of a short-duration STF in logic circuits can actually provoke harmful effects at the same time upon the redundancy scheme and circuit's original parts, and so the protection can fail even in detecting a single indirect SE (SISE).

Such a SISE-succeeded-STF-timing problem comes likely from the large need in latter years for also protecting the system's logic parts. In fact, this need has led to the development of many new mitigation mechanisms (e.g. [ [START_REF] Lisboa | XOR-based low cost checkers for combinational logic[END_REF]) based on ideas originally proposed either to make memory elements robust or to mitigate permanent faults. However, more complex effects of STFs in logic circuits require analysis and use of additional design timing issues that often have not been taken into account in several recent protection propositions. Hence, some typical countermeasures against SISEs may indeed not be as efficient as they seem.

1][2] [3][4]
Let us take a scenario of a SISE due to a STF that produces a timing problem in circuits protected by concurrent error detection (CED) codes. Fig. 1 shows a typical implementation scheme [START_REF] Kermani | Parity-Based Fault Detection Architecture of S-box for Advanced Encryption Standard[END_REF][4][5] [START_REF] Maingot | Influence of Error Detecting or Correcting Codes on the Sensitivity to DPA of an AES S-Box[END_REF] for protecting logic circuits which uses information redundancy to make a CED and a FF to register the resultant error signal (i.e. an error flag). Fig. 2 Fig. 2's example scenario illustrates a STF on O Logic covering LW. Then, a wrong data value is registered at t 1i.e. a SISE happens as illustrated on O Reg , which stores logic value "1" instead of "0". On the other hand, Code Prediction block provides on its output O Predi the correct code that should be expected from the ideal value at the output O Logic under a faultfree scenario. This prediction is then compared with the code on O Code , which is computed from the actual value at the output O Logic under a fault scenario. If O Code and O Predi do not match, Comparator block's O Com results in "1". Fig. 2 Other previously-unknown SISE scenarios and STF-timing issues that make typical CED code-based schemes inefficient are further studied in 0. The schemes' fail situations which are detailed in 0 have not yet been illustrated in the literature. Furthermore, 0 and section II of this paper discusses timing conditions for a more efficient use of CED codes.

II. CONCLUSIONS AND TIMING CONDITIONS FOR AN EFFICIENT USE OF CED CODES

The vulnerability windows highlighted in this paper for Fig. 1-like scheme represent risks for operations of systems that require fault tolerance; moreover they are such as attack-prone slots which could compromise secure systems. Another more efficient scheme solution is the use of a latch with an extra clock tree instead of a FF to register the error flag, but this approach would make much more complex the IC design due to the additional clock signals. Otherwise, another alternative could be improving the efficiency of Fig. 1's scheme by minimizing the STF-timing intervals (STF-TIs) for failsdiscussed in 0in function of fitting the delay of blocks. However, this solution would not meet better timing conditions than schemes that avoid associating their redundant parts before a timing barrier. It is not the case of Fig. 1's scheme that joins their redundant partsi.e. Logic Block and Code Prediction blockby using the Code and Comparator blocks before the timing barrier of the Data and Error Flag Register.

In fact, this type of protection like in Fig. 1 allows a single eventi.e. a STF starting before or even during the action of registeringto wrongly affect at the same moment the redundancy scheme and circuit's original blocks. Then, the comparison mechanisms have not enough time to suitably accomplish their function. Hence, a more efficient approach is using Fig. 3's scheme which compares the results of the redundant parts after the timing barrier. The comparison mechanisms Code and Comparator blocks thus evaluate signals O Reg and O PrediReg that have steady conditions during the clock cycle. Furthermore, otherwise Fig. 1's scheme, an eventual single direct SE, which is provoked by a STF originated in Data Register or Prediction Register, can be detected by Fig. 3's scheme. One could yet argue that any eventual STF arisen in Code or Comparator blocks could do Fig. 3's scheme not properly operating. However, such a scenario in the worst case would produce just a false-positive error flag (FPEF) 0. This Fig. 3's scheme therefore prevents the fail situations analyzed in 0, and then it is much more efficient than Fig. 1's scheme.

Figure 2 .Figure 3 .

 23 Figure 2. Timing characteristics of the CED scheme in Fig. 1

  renders timing characteristics of Fig.1's signals under an occurrence of a STF. The STF starts at instant t S and finishes at t F on Logic Block's output node O Logic . The clock cycle that is analyzed starts at time t 0 and finishes at t 1 , and registers' FFs require a Figure 1. A state-of-the-art CED code-based scheme set-up time T Set-up and a hold time T Hold . Code block's delay and Comparator block's delay are respectively D Code and D Com .

	Block Logic	OLogic				Data Register	OReg
	Code Prediction	Code OPredi	OCode	Comparator	OCom	Error Flag	Register	OFlag

  's example therefore illustrates that the STF on O Logic arises too late in the clock cycle, and so Code and Comparator blocks are not able to generate an Error Flag (i.e. "1" on O Com ) on time to detect SISE on O Reg . In fact, as shown in the figure, the Error Flag on O Com rises later than LW, and so it is not registered on Error Flag Register's O Flag . Therefore, this flag on O Com has not a steady condition during the clock cycle for the system deals later with. The CED scheme thus fails in detecting the SISE.