Cédric Join § Sonia Rezk
email: sonia.rezk@supcom.rnu.tn

Cédric Join
email: cedric.join@cran.uhp-nancy.fr

Sadok El

Sadok El Asmi
email: elasmi@supcom.rnu.tn

An algebraic derivative-based method for R wave detection

In this paper, a new robust method for R wave detection in ECG signal is proposed by using algebraic derivative estimation based technique. In fact, this new and efficient method relies on differential algebra, non-commutative algebra together with operational calculus. This technique allows noisy signal to be filtered via iterated time integrals and R wave slope to be emphasized. The ECG signal is then Hilbert transformed to be enhanced and threshold compared. The performance of the algorithm was tested by using the annotated records of MIT-BIH Arrhythmia Database. The robustness of the proposed R wave detector in presence of noise was also tested according to records from MIT-BIH Noise Stress Test Database. The overall performance is quite good even SNR as low as 6 dB.

INTRODUCTION

The Electrocardiogram ECG represents the electrical activity of the heart. This is characterized by a number of waves P, QRS, T related to the heart activity. The QRS complex is the most perceptible waveform within ECG beat. Its high amplitude makes QRS detection easier than other waves. Detection of R-peaks and consequently QRS complex have many applications including R-R interval analysis, ST segment examination, ECG data compression and ECG waveform classification. Different approaches have been proposed to QRS detection. An extensive review of the approaches proposed in the last decade can be found in [START_REF] Köhler | The principles of software QRS detection[END_REF]. Recently, new approaches are mainly based on artificial neural networks [START_REF] Xue | Neural-network-based adaptive matched filtering for QRS detection[END_REF], genetic algorithms, wavelet transforms [START_REF] Li | Detection of ECG characteristic points using wavelet transforms[END_REF], hidden Markov models as well filter banks techniques [START_REF] Afonso | ECG beat detection using filter banks[END_REF]. In noisy-free case, all these algorithms have satisfactory performances but performances decrease when the noise corrupts measured signal. Consequently, these techniques require a pre-treatment step using the classical numeric filters which introduce signal distortions in frequency or temporal components. Indeed, we need methods preserving the signal information contents and particularly R wave positions, in the presence of noise. Our aim in this paper is to present a new method which permits essentially to overcome the difficulties that arise when considering the pre-treatment of the ECG signal. The algorithm based on algebraic-derivative allows to emphasize large slope of R wave. To enhance QRS complex, the differentiated signal is then Hilbert transformed. The output is finally examined using decision rules to detect the occurrence of QRS complexes. Noise treatment is the mean challenge of QRS detectors since noise is often present in all ECG signals. It comes from various sources: muscular activity, movements artifacts, power line interference and baseline wandering due to the respiration. In addition, P and T waves with high amplitudes may be considered challenging noise as they winder R wave detection. Algebraic derivative, initially developed in [START_REF] Mboup | Numerical differentiation with annihilators in noisy environment[END_REF], has already proved to be robust with respect to noise in image processing [START_REF] Join | Robust curvature extrema detection based on new numerical derivation[END_REF], signal processing [START_REF] Fliess | Algebraic change-point detection[END_REF], automatic control [START_REF] Fliess | Non-linear estimation is easy[END_REF] as well as in biomedical engineering. This feature is due to the iterated time integrals which play the role of low pass filter attenuating the noise power. Indeed, disturbing noise is viewed here as highly fluctuating phenomena [START_REF] Fliess | Analyse non standard du bruit[END_REF]. This investigation is essentially stimulated by the theory of M. Fliess. The underlying theoretical framework using, in particular, module theory and Mikusiński operational calculus can be found in [START_REF] Mikusiński | Operational Calculus[END_REF]. Recently, problem in biomedical engineering can be tackled with this new method which is of algebraic flavour. For instance, the works of Mboup [START_REF] Tiganj | An algebraic method for eye blink artifacts detection in single channel EEG recordings[END_REF], which aim at the neural information processing by the detection of neuronal spikes, show promising results in neuroscience field. The Hilbert transformation is of widespread interest because it is applied in the theoretical description of many systems and directly implemented in the form of Hilbert analog or digital filters (transformers). Hilbert transformer (or filter) finds numerous applications, especially in modern digital signal processing. This terminology is applied here as a part of R wave detection algorithm.

The remaining of the paper is organized as follows: section 2 outlines the algebraic derivative-based method as well as the properties of the Hilbert transform. Section 3 gives an overview of the R wave detection steps of our algorithm. Section 4 applies the methodology on reals ECG data excerpted from the MIT-BIH arrhythmia database [17] and gives the simulation results compared to other algorithms and section 5 draws the conclusion.

FUNDAMENTAL RELATIONSHIPS

Algebraic derivative

We address the problem of estimating the first order derivative. More precisely, let x(t) denotes the signal we want to estimate. We assume that x(t) is smooth enough to permit a polynomial approximation of a chosen order p locally over an interval I T t-= [t -T,t] where p is an integer. This integer corresponds to the derivation order, here p = 1. This assumption is motivated by the Weierstrass's Theorem which states that function, continuous in a finite closed interval can be approximated to a desired accuracy by a polynomial function. Because polynomials are the simplest functions, and computers can directly evaluate polynomials, this theorem has both practical and theoretical relevance. With this motivation, the signal can be approximated around t = 0 for example by the first degree polynomial time function: p 1 (t) = a 0 + a 1 t, t ≥ 0, a 1 , a 2 ∈ R. Accurate identification of the coefficients is immediate: a 0 and a 1 are respectively the estimators of the signal and its derivative around the time constant t = 0, i.e, a 0 = x(0) and a 1 = dx dt | t=0 . Rewrite thanks to classic operational calculus (cf [START_REF] Mikusiński | Operational Calculus[END_REF]) p 1 as P 1 = a 0 s + a 1 s 2 . We look for annihilate a 0 because we want to estimate a 1 . Thus, multiply both sides by s:

sP 1 = a 0 + a 1 s
Take the derivative of both sides with respect to s, in order to omit a 0 , which correspond in time domain to the multiplication by -t (cf [START_REF] Mikusiński | Operational Calculus[END_REF]);

P 1 (s) + s dP 1 (s) ds = - a 1 s 2 (1)
The time derivative; i.e, s dP 1 (s) ds , is removed by multiplying both sides of equations (1) by s -n , n > 1, for instance n = 2. This operation allows to obtain only iterated time integrals. Since x(t) is noisy, there is an error in computing polynomial coefficients and henceforwards we can only obtain an estimate of a 1 denoted by â1 . Finally, the above equation leads in the time domain to the linear estimator

â1 (t) = 6 ∫ t t-T τx(τ)dτ - ∫ t t-T ∫ τ t-T x(κ)dκdτ T 3 (2a) = 6 ∫ t t-T τx(τ)dτ - ∫ t t-T (T -τ)x(τ)dτ T 3 (2b) = 6 ∫ t t-T (2τ -T )x(τ)dτ T 3 (2c)
There are no derivatives with respect to time involved, but only integrations. This is particularly valuable in the presence of high frequency perturbations or measurements corrupted by noise. Besides, we may mention that almost all local polynomial modeling problems use the principle of sliding estimation window. An optimal choice of the size of this window remains an issue. In this approach, it is established that a quit short time window is sufficient for obtaining accurate value of a 1 . We note that the role of this window is to localise the model fitting around the instant t. We use an T -point window for simplicity, although other window functions can be used. More information can be found in the original paper [START_REF] Mboup | Numerical differentiation with annihilators in noisy environment[END_REF].

Hilbert transform

Let's x(t) a real signal. Generally speaking, the Hilbert transform of a real signal x(t) is defined by [START_REF] Hahn | Hilbert transforms[END_REF]:

x H (t) = H {x(t)} (3a) = 1 π P ∫ ∞ -∞ x(λ )dλ t -λ (3b) = 1 π P ∫ ∞ -∞ x(t -λ )dλ λ (3c) = x(t) * 1 πt (3d)
Here H {.} means the Hilbert transform and * denotes the usual convolution product. The integrals in definition (3b) and (3c) are improper because the integrand goes to infinity for λ = t. Therefore, the integral is defined as the Cauchy principal value (Sign P). Equation (3d) shows that the Hilbert transform of x(t) is obtained by filtering the signal through a linear filter with impulse response 1 πt .

A useful way of looking at the Hilbert transform, and perhaps a more intuitive definition, is in the frequency domain

X H (ω) = X(ω).[-j.sgn(ω)] (4a) = X(ω).H(ω) (4b)
where the transfer function of the Hilbert transform H(ω) is given by:

H(ω) =    -j, for ω > 0 j, for ω < 0 0, for ω = 0 (5)
In fact, a Hilbert transform simply shifts all positive frequency components by -90 o and all negative-frequency components by +90 o . The amplitude always remains constant throughout this transformation. As outlined in figure 2 Hilbert Transform requires a Fast Fourier Transform (FFT) and an Inverse FFT (IFFT). The implementation of the Hilbert Transform is fairly simple in the frequency domain. The so-colled analytic signal is then defined as:

z(t) = x(t) + jx H (t) (6)
It is witnessed that x(t) = Re{z(t)} and x H (t) = Im{z(t)} where Re is the real part of z(t) though Im is the imaginary part of z(t).

The name of analytic denotes numerous types of complex functions which satisfy the Cauchy Riemann conditions for differentiability and is traditionally called analytic functions. By taking the Fourier Transform of expression ( 6), we get

Z(ω) = X(ω) + jX H (ω) (7)
by using equation ( 5), we obtain that the analytic signal has the following spectrum:

Z(ω) =    2X(ω), for ω > 0 X(0), for ω = 0 0, for ω < 0 (8)
which is inverse transformed to obtain z(t). Therefore, the Hilbert transform can be easily computed by taking the imaginary part of the analytic signal z(t). Since the analytic signal is complex it can always be put into polar form

z(t) = B(t)e jφ (t) (9)
We can then unambiguously define the envelope B(t)(the amplitude) and the phase φ (t) of z(t) by

B(t) = √ x 2 (t) + x 2 H (t), φ (t) = tan -1 ( x H (t) x(t) ) (10)
which gives

ω(t) = φ (t) = x H (t) x(t) -x(t) x H (t) B 2 (t) (11)
for the instantaneous frequency (IF) in the complex plane. The signal (equation 9) is represented in the cartesian plane as shown in figure 1. The IF obtained by this means is often meaningless. A recent method pioneered by Huang and al. called Empirical Mode Decomposition (EMD) [START_REF] Huang | The empirical mode decomposition and the Hilbert spectrum for nonlinear and non-stationary time series analysis[END_REF] was introduced to address this problem. An innovative approach based on iterated application of the Hilbert Transform (IHT) that has asymptotical convergence property faster than that of EMD, is described in [START_REF] Gianfelici | Multicomponent AM-FM representations: An asymptotically exact approach[END_REF].

It's clear that the envelope B(t) coincides with x(t) when x H (t) = 0. Therefore, the maximum contribution of the envelope B(t) when x(t) = 0 is given by its Hilbert transform. These remarks can be exploited in our case by the following way: We can turn the first differential of the ECG into analytic signal using the Hilbert transform. The maximum contribution of the first derivative envelope(B( d dt (ECG))) is given by its Hilbert transform. Recall that if the real valued signal x(t) is even then X(ω) is purely real-valued while if x(t) is odd then X(ω) is purely imaginaryvalued. Now if X(ω) is purely real valued then certainly X H (ω) is purely imaginary valued( and vice-versa). Therefore, the Hilbert transformation changes any even term to an odd term and any odd term to an even term. Let's take the even part of the signal. The Hilbert transform will be an odd function. That is to mean it will cross zero on the x-axis every time there is an inflexion point in the original waveform. Similarly, a crossing of the zero between consecutive positive and negative inflexion points in the original waveform will be represented as a peak in its Hilbert transformed. This interesting property can be exploited to develop an elegant and much easier way to find the peak of the QRS complex in the ECG waveform corresponding to a zero crossing in its first derivative waveform d(ECG) dt .

ALGORITHM FOR DETECTING R WAVE

The fact of applying the first derivative followed by the Hilbert transform doesn't detect QRS complex, but it only aims to enhance the peaks corresponding to QRS complex and then find region for high probability to locate R wave. A second stage to detect R wave is required. It consists to detect peaks in the signal. When a peak is activated, peak detection function returns all samples reaching the current peak height. Thus, each time a peak is detected, it is classified as either QRS complex or noise. The algorithm uses the peaks height, peaks locations (relative to the last QRS peak) and maximum Hilbert transformation in order to classify peaks.

The following is an outline of the basic detection rules for the algorithm detailed in [START_REF] Hamilton | Quantitative investigation of QRS detection rules using the MIT-BIH arrhythmia database[END_REF] and [START_REF] Pan | A real time QRS detection algorithm[END_REF]:

1. Ignore all peaks that precede or follow larger peaks by less than a waiting time equal to Dist (refractory period). 2. If the peak is larger than the detection threshold we call it QRS complex, otherwise we call it noise. 3. If no QRS is detected within 1.5 R-to-R intervals so there is a peak larger than half the detection threshold, and the peak followed the preceding detection by at least 360ms, we classify that peak as a QRS complex (back search). Figure 2 shows the blocks diagram of the basic operations of our algorithm for beats detection. A true QRS peak is expected to appear after a delay equal to Dist following the latest detected QRS peak. Dist is related to the expected QT interval of the current RR interval. Initially, Dist = 200ms. It is updated further using a version of an empirical formula of the QT interval:

Dist = 0.4 * mRR (12)
Here mRR represents a combination of averaged latest four interval RR mean with the shortest one of them RR min :

7RR mean + RR min 8 When a beat is located nearer than Dist to the latest QRS complex, this candidate is ignored if its amplitude is smaller than the latest detected complex. The adaptive detection threshold used in 2 and 3 is calculated by using estimates of QRS peaks and noise peak heights. At each time a peak is classified as a QRS complex, it is added to a buffer containing the last eight QRS peaks. Otherwise, the peak is added to a another buffer containing the recent eight non-QRS peaks (noise peaks). The detection threshold is set according to: Detection Threshold= Mean Noise Peak (13) +TH*(Mean Peak-Mean Noise Peak)

Where TH is the threshold coefficient. We estimate the mean of QRS height (respectively noise height and R-R intervals) using the mean of the last eight peak values. We note that some initial threshold estimate in the beginning of the algorithm is needed. We initialize noise buffer to 0 and the QRS buffer to the eight maximum consecutive peaks in 1-second interval. The initial threshold is initialized according to formula [START_REF] Huang | The empirical mode decomposition and the Hilbert spectrum for nonlinear and non-stationary time series analysis[END_REF]. Figure 3 illustrates an example of R wave detection by the proposed algorithm. We can see in figure 3(b) the original signal after the derivative estimation. The resulting signal contains only R wave positions (refer to figure 3(c)). The '+' marker corresponds to the R-position Rp.

RESULTS AND DISCUSSIONS

To analyze the performance of the proposed technique, on real world signals, we choose the ECG samples excerpted from the MIT-BIH Arrhythmia database [17]. It contains 48 half-hour recording of annotated ECG with a sampling rate of 360Hz. Furthermore, beat annotations include R wave marks. Two benchmark parameters are used to compare the performance of the proposed detection algorithm: the sensitivity and the positive predictivity of the beat detection are defined as following [START_REF] Köhler | The principles of software QRS detection[END_REF]

Se(%) = 1 - FN T P + FN = T P T P + FN %, (14)
+P(%) = 1 - FP T P + FP = T P T P + FP %, (15)
where (T P) is the number of true positive, (FN) is the number of false negative and (FP) is the number of false positives. The (Se) reports the percentage of true beats that were correctly detected by the algorithm. The positive predictivity (+P) reports the percentage of beat detection which were in reality true beats. The performance of our algorithm is influenced by a given set of parameters. There are two principle parameters within our algorithm(T,TH). The length T of the sliding window should be small enough to improve estimation. We test our algorithm for each record nine times with threshold coefficient TH ranging from 0.1 to 0.9. We choose the value which minimizes the Detection Error Rate. In this paper, we selected TH as the mean of all optimal value corresponding to lower DER for each record. The mean value is roughly 0.3. In order to make objective comparison with other published works, we classify the reported results with respect to their score. On the first scenario, we analyze the first five minutes signals in 46 database records. The table 1 reports the detection performances of our algorithm. The results are Se = 99.76%, +P = 99.89% and DER= 0.34%. Consequently, based on this score, the proposed technique outperforms Dinh's method [START_REF] Dinh | Wavelets for QRS detection[END_REF] based on Cubic Spline method (DER= 0.75%), although it performs similarly to Ben Massaoud's method [START_REF] Masaoud | On the algorithm for QRS complexes localisation in electrocardiogram[END_REF] based on Equalize of the maxima (DER= 0.34%).

On the second scenario, the algorithm is tested against the whole noisy MIT-BIH record 105. This later is used through the literature to test QRS detectors and therefore comparisons are possible.

The predominant feature of this record is a high grade of noise and artifacts. The comparison made between the performance of the proposed algorithm and literature are listed in table 2. The reliability of the proposed detector compares favorably with that of other published results especially concerning the most noisy record 105 (see [START_REF] Afonso | ECG beat detection using filter banks[END_REF][START_REF] Christov | Real time electrocardiogram qrs detection using combined adaptive threshold[END_REF][START_REF] Hamilton | Quantitative investigation of QRS detection rules using the MIT-BIH arrhythmia database[END_REF][START_REF] Li | Detection of ECG characteristic points using wavelet transforms[END_REF][START_REF] Pan | A real time QRS detection algorithm[END_REF][START_REF] Xue | Neural-network-based adaptive matched filtering for QRS detection[END_REF]). 6.5 Filter banks [START_REF] Afonso | ECG beat detection using filter banks[END_REF] 266 4. In fact, applying algebraic derivative and the back search strategy result on a beat detection latency time of more than heartbeat interval. The detection delay will be roughly the sum of derivative delay plus the average of R-to-R interval if a back search detection is needed. The algebraic derivative for the used approximation introduces a delay in the estimation equals to T 2 samples length. See [START_REF] Mboup | Numerical differentiation with annihilators in noisy environment[END_REF] for more explanation. This delay is off-line corrected after derivative step. The back search strategy is incorporated to correct FN. A back search is activated when no beat detection has occurred in a time interval superior 1.5 R-to-R interval. This strategy may result in a significant delay before a beat is detected.

CONCLUSION

We proposed an algebraic derivative-based algorithm for R wave detection of noisy ECG signals. We use an empirical technique based on local polynomial model to estimate the derivative. This model is popular because it is flexible with respect to derivative and computational easy to use. The algorithm is tested on several records from MIT-BIH arrhythmia database. These records are corrupted by different noises and artifacts. The results is assessed in term of benchmark parameters. Beat detection accuracy is comparable to other algorithm reported in literature. It can also be categorized by a real-time algorithm since it has a minimal beat detection delay. Furthermore, our algorithm could be implemented more easily comparatively to other algorithm based for instance on wavelet transform and neural networks. Further improvements to the algorithm may be easily achieved by using more features of the frequency components of the ECG or by using a more suitable model to fit ECG signal variation.

Figure 2 :

 2 Figure 2: Block diagram of the R wave detector.

Figure 3 :

 3 Figure 3: R wave position definition: (a) ECG signal (record(100)); (b) The output of the algebraic derivative; (c) Hilbert transform.

Table 1 :

 1 Recapitulate results for the proposed R wave detector of a 5mn record (not including MIT 107 and 108)

	Annot TP	FN FP Se(%) +P(%) DER
	17658	17610 48	20	99.76	89.89	0.34
	Method				DER Se(%) +P(%)
	Proposed detector			1.05	99.38	99.45
	Combined adaptive threshold [5] 1.44	99.92	98.64
	Wavelet transform [16]		1.09	99.50	99.42
	Linear adaptive filtering [22]	2.41	99.15	98.47
	Bandpass filtering [12]		2.91	99.15	97.98
	and back search
	Bandpass filtering [20]		3.46	99.15	97.58
	Filter banks [1]			3.22	99.26	97.58

Table 2 :

 2 DER, Se(%), +P(%) scores for the proposed the R wave detector compared to literature for the record 105The robustness of the estimation method in the presence of noise is quantified by the noise stress test using recordings from the MIT-BIH Noise Stress Database[17]. The ECG recordings were created using two clean records (118 and 119) from the MIT-BIH ECG Database to which calibrated amounts of noise containing baseline wander, muscle artifact, and electrode motion artifact. The SNR of each record is ranged from 6 to 24 dB.

	The Detection Error Rate (DER) and the Average time error are
	calculated as follow:
	DER(%) =	FP + FN Total number of QRS complex	%	(16)
	Average time error(ms) =		(17)
	∑ T P i=1 |Detected QRS Time-Actual QRS Time|
		T P

Table 4 :

 4 Comparison results of QRS detection delay time and literature 6dB with high sensitivity values (about 94%) as well as high positive prediction (above 88%). The results are depicted table3. At high SNR as well as low SNR, DER for our detector is superior to the other techniques examined specially in[START_REF] Benitz | A new QRS detection algorithm based on the hilbert transform[END_REF]. Now let us discuss the delay time in QRS detection. Delay time is expressed by the average time error parameter. Simulation results show that our algorithm has minimal delay in detecting beat compared to other algorithms in literature[START_REF] Afonso | ECG beat detection using filter banks[END_REF][START_REF] Arzeno | Analysis of firstderivative based QRS detection algorithms[END_REF]. Comparative results are shown in table

19th European Signal Processing Conference (EUSIPCO 2011) Barcelona, Spain, August 29 -September 2, 2011 © EURASIP, 2011 -ISSN 2076-1465


Jean Marc Salotti
email: jean-marc.salotti@ensc.fr

-2 CONCEPT FOR MANNED MISSIONS TO MARS

In a previous paper, a new scenario for human missions to Mars has been presented. It can be named the 2-4-2 concept. The idea is to minimize IMLEO and the payload on Mars with a crew of only two astronauts. There are two astronauts in each rocket at departure from Earth. They meet on Mars to form a team of four and the pairs are reconstituted for the return (2-4-2). In the previous study it was proposed an assembly in LEO. We propose now a different approach with several small vehicles sent to Mars at the same time. There is no need for LEO assembly and the landers are lighter thus facilitating entry descent and landing on mars.

I. INTRODUCTION

In the last Design Reference Architecture (DRA) for manned missions to Mars from NASA, two major critical phases have been identified [START_REF] Drake | Mars Architecture Steering Group, Human Exploration of Mars, Design Reference Architecture 5.0 ([END_REF]. The first is the launching and assembly phase, which requires a large number of launches with an Ares V class launcher and several years operations in LEO before the spacecrafts are sent to Mars. The second critical phase is the descent and landing on the surface of Mars. Braun and Manning also have reported important difficulties for that phase [START_REF] Braun | Mars Entry, Descent and Landing Challenges[END_REF]. Because of the payload needed on the surface of Mars, the ballistic coefficient is high and the feasibility of the descent is questionable in terms of technology and timeline. According to NASA, the cumulative risks of the DRA are too high for a manned mission to Mars. In order to reduce the risks, it is important to find solutions to reduce the initial mass in LEO (IMLEO) and to reduce the payload on Mars.

We propose a different scenario that minimizes the two risks described above. It is called the 2-4-2 concept. The basic idea has already been presented [START_REF] Salotti | Simplified scenario for manned Mars missions[END_REF]. We propose in this paper some improvements and discuss the risks. In Section 2, new elements of the scenario are described. In Section 3, an analysis of the risks is presented.

II. DESCRIPTION OF THE 2-4-2 CONCEPT Basic idea

The main ideas of the paper have already been published but the scenario had no name [START_REF] Salotti | Simplified scenario for manned Mars missions[END_REF]. The "2-4-2" concept comes from the number of astronauts at different periods of the mission. There are only 2 astronauts onboard the manned spacecraft. In NASA or ESA reference missions, the number of crew is 6 [START_REF] Drake | Mars Architecture Steering Group, Human Exploration of Mars, Design Reference Architecture 5.0 ([END_REF], [START_REF] Esa Humex Team | Study on the Survivability and Adaptation of Humans to Long-Duration Interplanetary and Planetary Environments[END_REF]. 2 astronauts is not the optimum according to skills requirements but it does not increase much the risks of the mission [3], [START_REF] Kanasa | Psychology and culture during long-duration space missions[END_REF]. On the other hand, it is risky to have no backup vehicle on Mars. In order to reduce the risks, the mission is fully duplicated. There are therefore 2 spacecrafts with a crew of 2. At launch and during transit they are 2. On Mars, the spacecrafts should try to land close to each other. So they are 4 on the surface to explore the red planet. At take off from Mars, they are 2 again. Each Mars ascent vehicle joins an Earth return vehicle and the 2 Earth return vehicles finally return to our planet. This is what is expected if everything goes well. However, 2-4-2 also means 2 for 2: 2 astronauts are ready to help the 2 others in case of an emergency. At every step of the mission, and especially on the surface of Mars, in Mars orbit or in transit, if a problem occurs with a spacecraft, it should be possible to proceed to transhipment onto the other spacecraft. Such a possibility has important impacts in terms of payloads but some mass savings remain.

It is important to recall that Von Braun already proposed a similar scenario. However, in his original concept, Von Braun proposed 12 astronauts and the IMLEO was 1450 metric tons [START_REF] Portree | Humans to Mars: Fifty Years of Mission Planning, 1950 -2000[END_REF]. There are indeed other options in our scenario that differ from Von Braun's idea and allow important reductions of IMLEO and Mars payload. The main one is the use of in situ local resources to produce propellant for the Mars ascent vehicle.

In Situ Resource Utilization (ISRU)

We suggest bringing all the tools and chemical systems to extract water from the ground and carbon dioxide from the atmosphere to produce CH4/O2, which is a good propellant for rockets [START_REF] Zubrin | The Case for Mars, The Plan to Settle the Red Planet and Why We Must[END_REF]. In NASA reference missions or in Zubrin Mars Direct scenario, it is proposed to produce propellant automatically by means of a cargo mission sent 2 years in advance [START_REF] Drake | Reference Mission Version 3.0 Addendum to the Human Exploration of Mars: The Reference Mission of the NASA Mars Exploration Study Team -EX13-98-036 -Exploration Office[END_REF], [START_REF] Drake | Mars Architecture Steering Group, Human Exploration of Mars, Design Reference Architecture 5.0 ([END_REF], [START_REF]Human Exploration of Mars: The Reference Mission of the NASA Mars Exploration Study Team -NASA SP-6107 -NASA Johnson Space Center[END_REF], [START_REF] Zubrin | Mars Direct: Humans to the Red Planet by[END_REF], [START_REF] Zubrin | Practical Methods for Near-Term Piloted Mars Missions[END_REF]. The idea is to have a Mars ascent vehicle ready for launch before the launch of the manned spacecraft. However, such an option adds complexity to the scenario and does not allow using the most appropriate technologies. In the DRA report from NASA, it is clearly explained that the option minimizing Mars payload is the one that exploits as much Mars resources as possible [START_REF] Drake | Mars Architecture Steering Group, Human Exploration of Mars, Design Reference Architecture 5.0 ([END_REF]. But that option is IAC-11-A5.4.11 Page 2 of 5 not chosen because of its complexity and risks if it has to be accomplished by robots. The extraction of water from the ground is indeed a complex task for a robot and the reliability is not high. If humans were present, the risk of loosing a robot or the difficulties linked to the deployment and maintenance of the systems would be highly reduced. Furthermore, important improvements have been made in solar panels technology [START_REF] White | ULTRAFLEX-175 on Space Technology 8 (ST8) -Validating the Next Generation in Lightweight Solar Arrays[END_REF]. According to Cooper et al, new ultra light solar panels have a lower specific energy than nuclear power plants even on the surface of Mars [START_REF] Cooper | Assessment of architectural options for surface power generation and energy storage on human Mars missions[END_REF]. Obviously, it would be very difficult to deploy and maintain such panels with robots. However, with the help of humans, the deployment would be manageable [START_REF] White | ULTRAFLEX-175 on Space Technology 8 (ST8) -Validating the Next Generation in Lightweight Solar Arrays[END_REF].

The 2-4-2 concept therefore enables optimisation in the utilization of local resources.

Optimisations

Several other optimisations can be proposed around the 2-4-2 architecture.

• First, the same habitat can be used in space and on the surface. Surprisingly, such an idea has not been examined in NASA reference missions, though similar habitat designs have been suggested for transit and on the surface [START_REF] Drake | Mars Architecture Steering Group, Human Exploration of Mars, Design Reference Architecture 5.0 ([END_REF]. The reason for that omission is probably that the Mars ascent vehicle would be much heavier if the habitat is used instead of the capsule. However, with a habitat designed for only 2 astronauts and provided that most consumables for the return are left in Mars orbit, the mass penalty is not so important.

• Second, because the specifications are close, the same propulsion system can be used for landing and for take off from Mars. There are therefore mass savings in the reduction of the number of propulsion stages.

• Third, there are small spacecrafts for Mars landing. In the previous paper, it was proposed to land only 2 spacecrafts with a crew of 2 for each and ISRU systems onboard [START_REF] Salotti | Simplified scenario for manned Mars missions[END_REF]. The reduction in the number of astronauts enables mass savings but ISRU systems are a mass penalty. In order to reduce Earth descent and landing (EDL) risks, it might be interesting to adopt another strategy. ISRU systems can indeed be sent in another spacecraft. The payload would be split into 2 equal parts and the spacecraft would be very light, in the order of 30 tons all included. The ballistic coefficient would be highly reduced, thus enabling a less constrained EDL phase.

• Fourth, what is not necessary on the surface is left in the Earth return vehicle (ERV) waiting in Mars orbit. The ERV is only a propulsion system (service module as in the Apollo program) and an Earth reentry capsule (command module as in the Apollo program). The capsule can be used to store consumables and tools for the return. As in the Apollo moon return scenario, the Mars ascent vehicle joins the ERV. The main difference is that the habitat coming from the surface of Mars is much bigger than the lunar module. The propulsion system of the Mars ascent vehicle (MAV) is then jettisoned before the rocket engines of the ERV are fired. An illustration is proposed Fig. 1. • Finally, another interesting feature is that the ERV, the cargo and the manned spacecraft would have a similar mass. In order to send all the spacecrafts to Mars, the same launcher might be used with a reasonable IMLEO capability. An illustration of the payloads is proposed Fig. 2. Concerning the risks, the Apollo 13 problem suggests that there are not negligible. However, it is difficult to make an accurate estimation of the risks because many systems are involved and humans have strong capacities to mitigate the problems and repair the defected devices. We propose a qualitative analysis inspired from what has been done for the ISS [START_REF]NASA PRA Practices and Needs for the New Millenium, International Space Station Probabilistic Risk Assessment Stage 7A[END_REF]. What kind of accident may occur during the transit stage that would result in the loss of the crew? Our analysis in summarized in Table 1. In most cases, if the problem is linked with the life support system, the degradation of life conditions is slow. The astronauts could therefore survive several weeks. Let us assume that such a problem occurs. How to implement a rescue mission during that period? Obviously, during the transit stage, it is not possible to stop and come back to Earth. The only solution is to have another rocket on the way to Mars. If that rocket is sent a few hours before or after the other one, it could be possible to make a junction in space and to transship the crew from the unsafe rocket to the safe one. By doing so, an explosion of the oxygen tank as it occurred during Apollo 13 mission would not have a dramatic issue. Now if we allow the transhipment of a crew, what are the consequences on the specifications of the habitable modules? Dramatic problems onboard a space vehicle requiring crew transhipment must be rare. An exceptional restriction of the volume per person is probably acceptable. A critical issue could be to keep the life support system operational if most consumables of the first vehicle are lost. As a consequence, there should be enough consumables for a crew of 4. However, even with a crew of 2, supplementary consumables should be taken onboard to come up with exceptional losses. In the case of transhipment, some consumables might be recovered. It seems therefore reasonable to double the consumables but without additional margins. Another issue is to allow more astronauts in the Earth entry vehicle at the end of the trip. The capsule should be designed for a crew of 4. However, it can be designed for a crew of 2 plus 250 kg of rocks samples or a crew of 4 plus 50 kg of samples.

Risks assessments

We propose a comparison with NASA architecture [START_REF] Drake | Mars Architecture Steering Group, Human Exploration of Mars, Design Reference Architecture 5.0 ([END_REF]. The two major risks that have been identified by NASA are a failure during launch or LEO assembly and a failure during EDL of a lander. Since the number of launches is reduced (6 vs 10) and there is no LEO assembly, our scenario is less risky for that phase. Regarding EDL, the landers of our scenario are much lighter (3 times less) with shapes adapted for maximum control and reliability. The ballistic coefficient is also smaller, thus minimizing physical and timeline constraints and enabling the use of more simple technologies. EDL risks are therefore much less in our scenario. Other risks exist, see Table 2. Our scenario has important advantages. The good points are the relative simplicity and the ability to perform transhipment during transit. The most important drawback is probably the fact that the ERV is not ready for launch when the astronauts land on Mars. The risk of loosing a crew is nevertheless mitigated by two backup solutions. The first one is the transhipment onto the second spacecraft provided that the production of propellant works properly for that one. If it does not work either, we suggest waiting for the next mission, which would bring new ISRU systems. In the DRA scenario, a similar backup solution is proposed if the MAV is not usable. In order to avoid such extreme situations, it is important to prove the feasibility of ISRU systems before the first manned mission. As it is mentioned by many engineers in astronautics [3], the major risk is probably linked to the landing on Mars. We therefore recommend that a dedicated unmanned mission is designed prior to this one to test the landing of a heavy spacecraft and the production of propellant using similar ISRU systems.

III. CONCLUSION

The proposed 2-4-2 concept can be considered as an optimized version of Von Braun's scenario. The idea is to send to Mars at the same time several spacecrafts with a crew of two. The scenario enables several optimizations and minimizes the risks by allowing safe transshipments in case of an emergency. Three important principles emerged:

• The human presence during propellant production enables the most efficient ISRU options.

• Short astronaut numbers enables small spacecrafts thus minimizing EDL complexity and risks.

• Since no LEO assembly is required, the scenario is simple.

Other important problems have not been discussed. Long stays in microgravity have negative impacts on many organs, especially bones, muscles and cardiovascular activity. In order to reduce microgravity effects, it is possible to include in the spacecraft a small centrifuge. Another idea is to have a tether between a habitat lander and a cargo lander and to rotate the system in order to create artificial gravity as it is suggested in Mars Direct [START_REF] Zubrin | The Case for Mars, The Plan to Settle the Red Planet and Why We Must[END_REF]. IAC-11-A5.4.11

Page 4 of 5

System Problem Consequence

Power supply Partly broken. Not enough power.

Life support system insufficiently powered. Possible consequences: Temperature cooled down, atmosphere not revitalized. Air composition control system Out of order, not repairable.

Atmosphere becoming unbreathable (too much CO2, not enough O2, etc.) Trace contaminants removal system Out of order or not appropriate for unexpected contaminants Air poisoned by contaminants. Degradation of astronauts' health.

Water purification system

Poisoned water, system out of order and not repairable or not appropriate for unexpected contamination Water poisoned by contaminants. Degradation of astronauts' health.

Food conservation and storage

Microbial contamination of food or unexpected packaging degradation Astronauts starving.

Structure of the habitat

Explosion or meteorite impact or closure leakages Continuous loss of air. Astronauts might survive during a short period of time in their spacesuit or in a restricted area of the habitat.

Propulsion system

Out of order.

Not able to undertake any maneuver. Rocket going to crash on Mars or to orbit around the sun (with the exception of free return trajectories).

Human

Fatal error or madness of an astronaut. One of the above systems is broken down. One of the above.

Fig. 1 :

 1 Fig. 1: Junction between the ERV and the MAV. The ERV (left) has 2 parts: a wet propulsion stage and a capsule. The Mars ascent vehicle (right) also has 2 parts: the habitable module and a propulsion stage, which is jettisoned before trans-Earth injection (TEI).

Fig. 2 :

 2 Fig. 2: ERV, manned spacecraft and cargo during Earth-Mars transit. The shape of the vehicles is adapted for aerocapture or/and landing.II. RISKS ANALYSIS Risks during the outbound transit phaseThe Apollo program was a great success. All astronauts returned safely to Earth. However, during the Apollo 13 mission, a terrible explosion occurred during the transit between LEO and the moon, which caused abort of the mission and endangered the crew. If a similar problem occurred during the transit between Earth and Mars, there would be no abort option to save the crew. In most scenarios, there are abort options while the crew is in LEO, in Mars orbit or on the surface of Mars but not during the transit stage. Is it reasonable to assume that the risks during the transit period are very low? And if not, what can be done to reduce them? We propose to address both questions.

Table 1 :

 1 Possible dramatic accidents during the transit stage. Try to repair. If not possible, two crews in the same spacecraft at takeoff. If second ISRU also out of order, send appropriate tools to repair. Long range mobility reduced or unable to join MAV.

	Problem	Consequence in DRA scenario	Consequence in our scenario
	Crash of manned launcher	6 people dead	2 people dead and mission aborted on
			Earth or in LEO for the 2 nd spacecraft. The
			risk of a crash is multiplied by 2. On
			average, the number of deaths per mission
			is nevertheless smaller.
	Problem during outbound	No short term solution. 6 people	Transshipment onto the second spacecraft.
	with manned spacecraft	dead.	Insertion in Mars orbit. Then wait next
			conjunction for return.
	Problem in MO with manned	If problem with ERV, abort to	Transshipment onto the second spacecraft.
	spacecraft	Mars and wait for next ERV; if	Wait next conjunction for return.
		landing impossible, abort to ERV.
	Unable to produce propellant	Stop mission before sending
	using ISRU	astronauts.
		Wait next mission.	Wait next mission.
	Unable to takeoff from Mars	Wait next mission.	Transshipment. If second spacecraft unable
			to takeoff, too far or already gone, wait
			next mission.
	Crash of MAV	6 people dead	2 people dead, same as crash of launcher
	MAV safe but unable to join	6 people dead	Try transshipment. Otherwise 2 people
	ERV		dead.
	ERV unable to leave MO	If possible, wait next mission,	Try transshipment. Otherwise 2 people
		otherwise 6 people dead.	dead.
	Problem during inbound	Same as outbound, no short term	Same as outbound, transshipment.
		solution.

Table 2 :

 2 Comparison of the risks between the DRA scenario and ours.


Jean Marc Salotti
email: jean-marc.salotti@ensc.fr

Thomas Da Fonseca
email: thomas.dafonseca@ensc.fr

Adrien Lainé
email: adrien.laine@ensc.fr

Cédric Moisset
email: cedric.moisset@ensc.fr

IMPACT OF HUMAN FACTORS ON THE GROWING RATE OF A MARTIAN POPULATION

In a few decades, the problem of the permanent presence of humans on Mars will be addressed. With current space technology, it is not thinkable to send tons of resources every year from Earth to maintain the quality of life of the population during a long period of time. A sustainable development of the colony will therefore be possible only if the population grows and rapidly achieve a minimum number of persons in order to be able to develop and maintain industrial activities that will allow self sufficiency relatively to the Earth. The goal of our study is to examine possible impacts of human factors on the demographical evolution of the population during that development. It is assumed in this study that the settlement is technologically feasible and that the threshold for the minimum number of persons will be achieved thanks to demographical growing with a negligible number of immigrants per year. First of all, demographical data from several countries have been examined and the impact of human factors has been analysed. From these observations, we came to different options for a scenario of the Martian settlement and a simulator has been developed. The main conclusion of the proposed demographical analysis is that social factors such as religion, culture or public policy have a great impact on the growing rate. Simulations on the computer show that if appropriate options are chosen the population of the colony can easily reach 50000 people in less than 500 years. However, if the growing rate is too high, the development might not be sustainable any more. For instance, if the number of children is very high, their education would require the mobilization of too many human resources. A trade-off has therefore to be found.

I. INTRODUCTION

In a few decades, the difficult problem of the settlement of the red planet may be addressed. It is already mentioned in several reports from NASA and other Mars specialists as one of the key reasons to determine the best architecture for manned missions to Mars [START_REF] Drake | Reference Mission Version 3.0 Addendum to the Human Exploration of Mars: The Reference Mission of the NASA Mars Exploration Study Team -EX13-98-036 -Exploration Office[END_REF], [START_REF] Drake | Mars Architecture Steering Group, Human Exploration of Mars, Design Reference Architecture 5.0 ([END_REF], [START_REF] Esa Humex Team | Study on the Survivability and Adaptation of Humans to Long-Duration Interplanetary and Planetary Environments[END_REF], [START_REF] Zubrin | The Case for Mars, The Plan to Settle the Red Planet and Why We Must[END_REF]. However, the settlement is much more than just living one or two years in an extreme environment [START_REF] Kanasa | Psychology and culture during longduration space missions[END_REF]. In order to achieve that goal, the autonomy of the colony has to be developed. As long as the Martian base is settled with less than a few dozens of people, it is possible to send consumables and tools from the Earth to support the colony. Such a support becomes impractical if the colony grows because the amount of goods grows in same proportions and the cost of sending them to Mars would rapidly becomes prohibitive. If we assume that there are no possible trades between Earth and Mars (at least in the early ages of the colony), the only way to perform a sustainable development is to minimize the goods that have to be imported from Earth and therefore to achieve full autonomy as soon as possible. In a modern society, millions of people are required to produce all the goods and services. However, only a fraction of them are essential. The autonomy can be achieved without planes, boats, trains, toys, robots, computers, oil, and so on. It is difficult to determine the shortest list of industries that have to be developed. But even if that list could be elaborated, two key questions arise. The first is how many settlers are needed to make these industries functional so that the minimum level of autonomy is achieved? And the second is how many years does it take to reach that number? A demographic simulator has been developed to help answering the second question. In section 2, the problem is addressed in more details and several hypotheses are discussed. In section 3, some results are presented and analyzed.

II. DEMOGRAPHIC SIMULATION

Simulations are often used to help understanding social problems [START_REF] Gilbert | Simulation for the Social Scientist[END_REF]. Human factors play an important role on the growing rate of a population. The birth-rate especially depends on cultural variables, such as religion, customs, stress, security. It also depends on economical or political incentives and environmental constraints. The objectives of the colony are twofold. On the one hand, as many people as possible should work for the support and development of the colony. On the second hand, the population should grow as fast as possible to reach the population threshold (PT) from which the autonomy of the colony is possible. The problem is that the greater number of children, the greater number of adults is mobilized to assist and educate them. A trade-off has therefore to be found. Several hypotheses have been made for the simulation:

The initial number of settlers is 100. It is possible to send them in one or several vehicles, in several stages, eventually several years after the construction of the base. Although some recent works suggest that the landing vehicles and the crews will be very small [START_REF] Salotti | 2-4-2 Concept for Manned Missions to Mars[END_REF], [START_REF] Salotti | Simplified scenario for manned Mars missions[END_REF], it is beyond the scope of that study to determine the best way to start the settlement. From that number (100), it is assumed that the colony has to grow rapidly with the objective of total autonomy.

The set of settlers can be divided in four subsets. The first is called "active persons". Active persons work for the survival and development of the colony. They control and maintain the life support, they produce food and tools, they maintain and repair objects, they participate to the management, they propose sportive and cultural activities etc. The second is the subset of "children". Babies and young children do not produce anything. Moreover, they need parents and educational support. Teenagers and young adults still need education but they can also provide some help to active people. The third is the subset of "assistants" who have to educate and take care of children and eventually old or handicapped persons. The last is the subset of elderly people who also need some assistance. Obviously, if the number of children and very old persons is high, there is a risk to have too few human resources in the first subset. The colony has to grow rapidly but not at the expense of the survival and minimum comfort of the settlers. An important parameter is therefore the minimum percentage of active persons (first subset) that allows a sustainable development of the colony.

III. VARIABLES Initial population

The initial age structure diagram of the first 100 settlers may be very important. The distribution of the population can be random or very specific, for instance with all people older than 18 years. New colons may join later on but it is assumed that their number would be negligible. Different distributions will be examined.

Assistance to children

We propose to distinguish between 5 categories of children and their corresponding assistance level. See

End of life

The age of death is randomly determined according to a Gaussian variable (A d , σ d ). Some people live very old without assistance while others are handicapped very young. We propose to simplify the problem. It is assumed that only elderly people older than a specific age limit A l require assistance for living and that 0.5 persons are mobilized for that task.

Births

It is assumed that a man and a woman have to form a couple before giving births to children. The number of children per woman is determined by several variables and formulas. The first variable is the percentage of persons who are not fertile %NF. The second and third variables are the age A min from which a baby can be born and the age A max after which it is not possible or strongly not recommended. Then there are 2 contradictory factors. The first one is incentive. Since the colony has to grow as rapidly as possible, provided that there are enough active people for a sustainable development, women are incited to give birth to a large number of babies with the constraint of 1 new child per year. On the other hand, religion, customs and other cultural variables play an important role on birth-rate. In current occidental civilizations, the number of babies per woman is quite low. If the settlers come from such countries it might be very difficult to convince them to give birth to 4, 5 or even more babies. For the simulation, the number of babies per woman is not a priori fixed. Each year, a new baby is decided according to the following algorithm. Let N adu be the number of persons between 18 and A l (adults). Among those persons, there are active persons N act and assistants N ass (introduced in Section 2). N ch is the number of children and N old is the number of persons older than A l . The number of persons who need assistance is calculated first in order to determine the number of assistants N ass .: N act is equal to N adu -N ass . Three key parameters defined at the beginning of the simulation are then taken into account:

%maxN ass is the maximum number of adults who can be allocated to the "assistants" subset.

%cult determines the strength of the culture for the decision of giving birth to a new child and N cult is the average number of desired children according to cultural parameters. A birth is thus decided for a given couple if the 3 constraints are satisfied (recalculated each year):

The 2 persons of the couple are fertile and the age of the woman is less than A max .

N ass < %maxN ass x N adu (random(100) > %cult) or the current number of children < N cult ) Note: Random(100) is a random function returning a random value between 0 and 100.

IV. RESULTS

Several tests have been performed. See figures 1-6. Simulations are stopped after 1000 years or as soon as the number of people falls to 0 or is superior to 50000, which is assumed to be the minimum value to achieve full autonomy (PT). Several conclusions can be drawn. First, there is a strong constraint on human resources (Fig. 1 and Fig. 2). If the percentage of active persons has to be kept very high, there are not enough people for assistance to children and very old persons. If it is not too high, the colony rapidly grows but the birth-rate is automatically regulated by the requirements on human resources. The same regulation occurs with elderly people. We set the average death to 70 years old. If A l (age limit for no assistance) is greater than 70, few people require assistance. On the other hand, if people live on average much older than A l , (see Fig. 3) the number of active persons mobilized for assistance may endanger the development of the colony depending on the value set for %maxN ass . In certain circumstances, the colony would therefore have to face ethical problems.

Culture also has an important impact. If %cult is set very high and N cult is low, for instance 2 children, the colony slowly declines. If %cult is not too high, the birth-rate may become sufficient for the development of the colony but the growing rate may be very slow. Another important parameter is the percentage of fertile persons. If it is low, for instance less than 80%, the number of children per woman has to be more important. In that case, if %cult is not negligible, N cult should be greater than 3 to enable population growing.

Finally, it is important to note that with the same parameters, the result of the simulation can be very different (see Fig. 5 and Fig. 6). Numerous tests have been performed. The main conclusion is perhaps that it is very difficult to predict the results, depending on the initial set of parameters. In the best scenario, starting with 100 colons, the population reaches 50000 people in less than 300 years. However, constraints on human resources, human factors and assistance to children and elderly people may strongly slow down the growing rate. In some cases the development is even not possible.

The simulator can be provided on demand.

Fig. 1 :

 1 Fig. 1: Initial population: random in [1;60]; A d =A l =70; σ d =5; A min =20; A max =40; %maxN ass =20; %cult=0; %NF=10. 50000 people reached. Average number of children per woman (end of sim.): 4.6.

Fig. 2 :

 2 Fig. 2: Initial population: random in [1;60]; A d =A l =70; σ d =5; A min =20; A max =40; %maxN ass =12; %cult=0; %NF=10. Simulation stopped after 1000 years. Average number of children per woman (end of sim.): 2.4.

Fig. 3 :Fig. 4 :

 34 Fig. 3: Initial population: random in [1;60]; A d =75; A l =70; σ d =5; A min =20; A max =40; %maxN ass =15; %cult=0; %NF=10. 50000 people reached after 750 years.

Fig. 5 :

 5 Fig. 5: Initial population: random in [1;60]; A d =A l =70; σ d =5; A min =20; A max =40; %maxN ass =15; %cult=90; N cult =2; %NF=20. 50000 people reached after 725 years.

Fig. 6 :

 6 Fig. 6: Initial population: random in [18;60]; A d =A l =70; σ d =5; A min =20; A max =40; %maxN ass =15; %cult=90; N cult =2; %NF=20. 50000 people reached after 760 years. However for 3 tests with the same parameters, the population declined to 0 and for 1 test the simulation stopped at 1000 years with 2000 people. III. CONCLUSION A simulator has been developed to study the demographic development of a Martian colony.Numerous tests have been performed. The main conclusion is perhaps that it is very difficult to predict the results, depending on the initial set of parameters. In the best scenario, starting with 100 colons, the population reaches 50000 people in less than 300 years. However, constraints on human resources, human factors and assistance to children and elderly people may strongly slow down the growing rate. In some cases the development is even not possible.The simulator can be provided on demand.

Table 1 .

 1

	Age of children	Number of persons
	(years)	mobilized, default value
	0-3	0.5
	4-5	0.3
	6-9	0.2
	10-14	0.1
	15-22	0.05

Table 1 :

 1 Children categories.


Vincent Liquète

The numerical knowledge of reference in Elearning: the example of the students in a master's of documentation program

Keywords: Community of Practice, Training Documentation, Mutual Distance Training, Digital Knowledge I

This longitudinal study from 2007 to late 2010 consisted in observing and interviewing "Documentation and information systems' masters students working remotely in a digital work environment. The work structure was based on a virtual desktop coupled to a lesson generator. The survey identified five forms of digital knowledge required for successful course completion. These modes of organization and knowledge production also imply rethinking the role of university teachers.

INTRODUCTION

A. General background

This research, and the experimentation undertaken to reinforce the e-learning tool, began in September 2007. At that time, even though our university had made a rich technical environment available for distance learning, it already seemed, as underlined by Christensen [START_REF] Christensen | The Innovator's Dilemma[END_REF], that the tool should not constitute a "disruptive technology" and could not be imposed by the university or by those responsible for teaching within the university. Our idea was therefore to observe the actual practices of students and the patterns of sociability among them in order to design an e-learning tool as a training space negotiated between the stakeholders, ensuring pedagogical continuity and reinforcing links with the future professional sectors in which the students would work. Before joining our university, the students had completed three years at university and obtained a degree, mainly in the humanities and social sciences or in information and communication sciences. The training covered by this study concerns two years of study in a professional masters entitled "Documentation and information systems", which allows students at the end of their course to seek employment in the documentation departments of libraries, universities or schools, or to become a manager of documentary information systems in the corporate world 1

B. Context of the study and observation

The survey was conducted longitudinally and crosssectionally among three groups of twenty students during the years 2008, 2009 and 2010. To better understand the individual and collective construction of knowledge among the subjects, we surveyed the students three times during their two years of masters study. Three methods wereused:

-Semi-structured interviews on representations of their expectations and on the final evaluation of the e-learning tool; -Analysis of student productions, both those meeting the requirements of teachers-tutors and those co-constructed between students without any recommendation from the university; -Assessment of the use of information resources and elearning during internships in companies or institutions.

As suggested by the approach of Wenger, Mac Dermott and Snyder [START_REF] Wenger | Cultivating Communities of Practice: a Guide to Managing Knowledge[END_REF], we particularly considered the sociocultural dimension of learning in e-learning, where communities of individuals are organized as collective human resources invested in "mutual engagement" aiming at a form of social cohesion, embracing a "joint enterprise" in which actions are collectively negotiated between peers, based on a "shared repertoire" that combines a complex and multidimensional set of resources. We consider resources such as e-learning products as both learning objects and cultural objects, i.e. they are based on a set of routines, tools used and / or diverted from their primary function, as procedures for accessing and sharing, as symbols and beliefs shared among peers. This gradually leads to the construction of an informational approach that differs from the existing institutional and / or professional situation, forcing us as researchers to account for the implicit and informal forms of the "ordinary" production of resources, which themselves are not necessarily innovative but ensure group cohesion and learning. On this point we agree with Tough [START_REF] Tough | The adult's learning project: a fresh approach to theory and practice in adult learning[END_REF] for whom ordinary social information practices are effective in terms of the satisfaction that they provide on a daily basis and are structured in terms of sociability.

C. The e-learning environment offered to students

The technical environment made available to students is mainly organized around the university's intranet, which is accessible by identification / authentication. Three technical areas are available: -An area of communication using the university's bulletin board with access to forums, thematic or customized mailing lists, and focusing on the asynchronous dissemination of organizational information related to monitoring of the Web; -Access of all university stakeholders to a virtual office running under Contact Office, allowing every student access to containers of documents, providing various resources in various formats (PDF resources, Power Point, textual and graphic material, etc). There are also communication tools including the synchronization of messaging, sharing schedules, access to resources for teachers, establishment of chat groups on invitation, etc. Thus, the offer of content and functional tools is quite extensive because, as underlined by M. Bernard [START_REF] Bernard | Le e-learning : la distance en question dans la formation[END_REF], an elearning tool is a training system for managing all or part of resource centers, communication tools, and digital media coupled with networks. On a human level, all university professors involved in the masters are involved in the production of resources. In particular, two teachers ensure the coordination and monitoring of resources placed in the virtual office, and undertake the role of tutor-facilitator in exchanges with the students. The more ambitious production of specific resources via Dokeos is conducted on a voluntary basis. Nearly 40% of the members of the teaching team are currently participating in this venture.

II. THE PROCESS OF PRODUCTION BETWEEN ACTORS

A. Organization of learning between teacher-tutors and students

As suggested by M. Connolly, N. Jones and D. Turner [START_REF] Connolly | Repenser la cyberformation[END_REF], our students surveyed at the beginning of their first year of their Masters would like to receive a "hybrid" form of training in which the dissemination of online content is reinforced with traditional teaching methods and regular courses with teachers scheduled within the university. Therefore, our e-learning courses complement regular time spent in class, extending training offered in situ with problem-focused learning, the solving of exercises, production per se and the preparation of professional internships. In our view, the student does not become autonomous straightaway but gradually learns to become so (Liquète and Maury [START_REF] Liquète | Le travail autonome : comment aider les élèves à l'acquisition de l'autonomie ?[END_REF]), especially during phases of work-sharing and exchange with peers. Therefore, since 2008 we have reduced course time and tutorials by a third, focusing through the platform on modes of exchange, production and written correspondence between students. Currently we believe that a master is divided into two equivalent periods: one where the students are present, and the other involving distance learning according to the requirements and specific work instructions and free time of the students in which they mutually organize their learning.

B. The process of production by and between students: building a learning community

Over the months, our longitudinal survey has shown that groups of students who are gradually acquiring autonomy organize their productions in the form of collective work intelligence (Delamotte [START_REF] Delamotte | Eléments de réflexion pour la production d'une intelligence collective[END_REF]), where the question of the use and mastery of technical environments takes second place to the fundamental focus on the negotiated construction of knowledge among peers. Our data collection shows four main modes of work preferred by students, since they find them structuring and reassuring: -First, the main documents produced, organized and stored in the digital e-learning environment are based on forms of collective writing strongly influenced by the knowledge formats that they are accustomed to in their professional documentation. These formats available on the Web have a structuring effect with regard to pedagogical, cognitive and (ultimately) professional issues.

-Second, in the groups we observed and interviewed, the students have organized themselves in such a way as to watch for information to appear on the net. This task is strictly divided between the members of a group and characterizes forms of work-sharing and collective and sophisticated network monitoring procedures. -Third, there are the activities of re-appropriating documents originally issued by the teachers. The documents concerned are essentially methodological documents issued in connection with courses or tutorials, then reclaimed and reused freely by students, in particular to produce accounts of reading, exercises or thematic presentations. This constitutes an informational processing of the re-appropriation type, as the methodological approach and initial intentions of the teachers are diverted and re-appropriated by students in order to organize their own working strategies and knowledge production. -Finally, there is the organization between students of procedures that represent the more or less implicit validation of content learned within groups and based on forms of leadership. Thus, the "communities of practice" that students develop in the form of micro-groups at the beginning of their curriculum are gradually transformed into "communities of professional interests" (Wenger [START_REF] Wenger | La théorie des communautés de pratique : apprentissage, sens et identité[END_REF]). What happens is that the older students and those who are the most experienced in the field of documentary information come to speak with an authoritative voice across groups and decide to select or not select the content co-produced by the students themselves, in addition to the e-learning content proposed by the teachers.

C. The organization of learning around digital reference knowledge

As suggested by F. Morandi [START_REF] Morandi | Information et enseignement : les « savoirs » du numérique[END_REF], a set of skills and reference knowledge are increasingly utilized by students for educational purposes in the digital work environments offered to them. Most of the proposals and pedagogical scenarios offered by the teacher-tutors are based on specific acquisition targets and the realization of planned activities by students. The knowledge that we present results from a detailed observation of student practices, and is not just an enumeration of the functional intentions of the designers of e-learning programs. Five forms of digital knowledge seem to form the backbone of our digital learning tool.

-KNOWLEDGE WITH TEACHERS PRESENT: time spent with teachers who have technological assistance constitutes a strategic moment designed by teachers to optimize the transmission of future documents and content via the digital e-learning environment. Contrary to what one might assume, gathering students physically and geographically in one place not only helps in the transmission of essential knowledge in the program, but also makes it possible to explain and justify future mailings via the platform. Knowledge with teachers present helps in anticipating and projecting future scenarios. This form of anticipation is given substance by following up the students and their questions through their portfolio.

-TECHNICAL OPERATIONAL KNOWLEDGE: This is essential for accessing resources and accompanying documents. Each student must master the offer of information proposed by the teachers by promptly validating the technical certification procedure during the first 3 months of training. He/she must demonstrate a real instrumental ability to modify and activate the various features and potential offered by the e-learning environment. This certification is in line with national certification that exists in all university courses in the form of the C2i certificate, which is the current French benchmark for Computer and Internet Certification.

-SITUATED KNOWLEDGE: the objective is not only to strive simply for the acquisition of content and the search for performance in these environments but also to work with the student by analyzing the structure of environments, work situations, and identifying the critical limits of available environments. The purpose of this situated knowledge is to develop gradually the critical skills of students as librarians, who are themselves distributors of environments and administrators of documentary information systems. Situated knowledge is based primarily on the semiotic and ergonomic analysis of environments and on the digital tools of the documentary information sector.

-DOCUMENTARY KNOWLEDGE: the aim here is to design a pedagogy of resources, where documents placed within the e-learning space not only play a traditional role of content transmitter in connection with an educational issue, but must also be analyzed as social objects, by deciphering editing contexts, sources, editorial and authorial intentions, etc. In our opinion, the acquisition of knowledge is based not only on documentation but also on the creation of documents, in the sense that there is an intentional process of documenting thought and / or an enunciative register (political, ideological, activist, etc). Such documentary knowledge is basic knowledge, as it gradually gets students to question themselves about their own ability to "document"3 information within and outside an e-learning environment.

-KNOWLEDGE DIDACTIZED REMOTELY: placing some of the lessons at a distance in both the synchronous and asynchronous mode means that resources must be didactized, making sure that for each resource, and apart from the working instructions, it is made clear how the document is to be used and read and what is expected by the teacher. Our investigation and monitoring of students show that these methods of didactization are then reused by students themselves in their collective group work. The stakes are high, because gradually our students report that they incorporate the notion that an information resource is not limited to the mere transmission of content, but that it also provides an intended usage and a scenario for subsequent use.

These five forms of digital knowledge do not compete with each other. Rather, by interacting, they constitute an economical e-learning framework where the aim is not only to acquire knowledge but also to develop the capacity to analyze, to criticize, to rewrite, to rethink how information is received and to organize it as part of their future professional environment. The very notion of distance learning makes us better assess the requirements for the communication, appropriation and the creation of information by our students.

III. TOWARDS NEW HUMAN AND INFORMATIONAL POSTULATES IN E-LEARNING SPACE

A. Postures of Mediation revisited by faculty tutors

While teachers gradually adopt new positions in terms of their pedagogical relationship with students, and while they remain teachers who transfer content and knowledge, they also play the role of mediator, tailoring the space to the e-learning needs of their students by mediating contents (Liquète [START_REF] Liquète | Médiations[END_REF]). As pointed out by I. Fabre, C. Gardiès and V. Liquète [START_REF] Liquète | Faut-il reconsidérer la médiation documentaire ?[END_REF], the mediation of actions undertaken in e-learning should be reconsidered from three points of view:

-Mediation by the PROCESSING of documents, a component central to learning the trade of a documentalist. Educators in e-learning should consider mediation in terms of the systematic processing of the various resources available, rather than as offering the processing of exercises and objects of specific lessons. Among other things, this systematic processing involves the management of metadata and the analytical indexing of resources filed on the digital education base. Each e-learning resource becomes an object of analysis and training for the student. -Mediation by documentary PRODUCTION. The appropriation of knowledge, especially technical knowledge, cannot be achieved only by way of reading, training and problem-solving; it is also necessary to create a set of professional products. The products thus created by students become the subject of mediation, discussion, and understanding between teacher and student.

-Finally, there is mediation by documentary COMMUNICATION. As suggested by C. Gardiès [START_REF] Gardiès | L'éducation à l'information : guide d'accompagnement pour les professeurs-documentalistes[END_REF], mediation makes it possible to analyze and provide a context, and to develop awareness of the need for information and communication. Documentary mediation is no longer limited only to the most comprehensive analysis possible of informational offers and situations, nor simply to the listing of content. It also involves understanding situations and the intentions to communicate that educators, documentation professionals and the authors of resources may have. To do this, we have launched micro-seminars so that participants may collectively seek to explain the communication strategies adopted by the cultural and documentary industries.

B. Future trends in digital learning

In view of our experience and the results we have obtained to date, we have focused our attention since September 2010 on accompanying e-learning students in three areas that we had previously dealt with inadequately. First, we regularly update our methodological resources focused on helping students to analyze documents and on providing assistance with traditional editorial issues and matters concerning the web. Our aim is that by analyzing the strengths and weaknesses of resources, students should gradually reach a level of critical analysis of resources that will allow them, once they have found a job, to increase their own level of requirements before providing documents to users of the documentation system for which they will be responsible. Second, we insist on the provision of information writing formats to enable them to be able to produce attractive and professional resources for end users, so that they can share documents among their peers that are easily identifiable, with common writing and display forms that allow fruitful exchanges between students and teachers. Finally, we have set up joint activities between our two tutors and students with regard to accompanying the writing processes of the latter during their curriculum. There are three types of core target material for this process of accompaniment: their professional report 4 allowing them to validate their diploma at the end of their course, their documentary analysis of resources that they have produced with their peers, or which have been selected by them; and finally, the editorial support they receive for their portfolio.

CONCLUSION

Our work piloting a university training course in professional documentary skills, which is based in part on accompanying e-learning and a survey to analyze and understand the practices actually undertaken by students (student experience according to Thorpe [START_REF] Thorpe | Perceptions about time and learning: researching the student experience[END_REF]), shows a real gap between the rhetoric, institutional intentions and the actual practices of students (Benchenna and Brulois [START_REF] Benchenna | Usages et usagers des campus numériques : entre projections ministérielles et prémices d'une réalité[END_REF]). In his experience at the Open University of Israel in 2006, S. Guri-Rosenblit already referred to a set of paradoxes [START_REF] Guri-Rosenblit | Eight paradoxes in the implementation process of e-learning in higher education[END_REF].

Our data show that students gradually go beyond the prescriptive framework laid down by the teaching staff and focus on individual and collective approaches that both teachers and / or tutors do not necessarily witness. These informal study practices are meaningful to students. The challenge for teachers is to devise ways of harnessing these informal practices in order to capitalize on them, rather than to continue to provide resources based on a too rigid and preconceived pedagogic scenario. A further challenge is to account for the informational and editorial logic that students may still be unaware of in their thought process. Helping them to index resources and to analyze widely used editing formats, to understand the policy issues of traditional and digital editing, getting them to take users' requests into account, i.e. skills that they will need to implement in their future profession: these are the major issues for us in the future. E-learning tools should ultimately enhance the flexibility of pathways to knowledge, rather than reinforce systemic gridlocked approaches in highly developed technical frameworks.

Figure 1 .

 1 Figure 1. Homepage of students' virtual office -A lesson editor running under Dokeos 2 , allowing teachers to make elaborate resources in the form of multimedia podcasts, synchronous seminars, conferences, live workshops, assessment types, etc.

Figure 2 .

 2 Figure 2. Example of notional mapping in connection with the course on the epistemology of information developed by a group of 4 students, without any specific instructions from the teacher in charge of the course (2009).

  .

	1 For	overview	of	studies	online,	see	http://iufm.u-
	bordeaux4.fr/accueil/formation/Formation+Documentaliste+Presentatio
	n

Cf. as an illustration, http://dokeos.aquitaine.iufm.fr/index.php

We refer here to the act of placing information within a document, a core skill for any documentalist.

June 8 th -10 th , New York, NY, USA The International Conference on E-Learning in the Workplace 2011, www.icelw.org

The professionnal report consists in a document of about

pages that states a problematic issue and attempts to solve it by using readings, survey data and thinking undertaken during the second year of the Masters program.

AUTHORS

Vincent Liquète is with the Institut Universitaire de Formation des Maîtres (IUFM), UB4, 160, avenue de Verdun, BP 90152, 33705 Mérignac Cedex FRANCE (email: vincent.liquete@ims-bordeaux.fr).

Manuscript received 25 April 2011. This work was supported in part by the Ecole Nationale Supérieure de Cognitique (http://www.ensc.fr/ ) Published as submitted by the author.


Member, IEEE, Saied Hemati, Senior Member, IEEE, Shie Mannor, Senior Member, IEEE Camille Leroux

Senior Member, IEEE Warren J Gross

Stochastic Chase Decoding of Reed-Solomon Codes

Keywords: Stochastic decoding, Chase algorithm, soft decision decoding, Reed-Solomon codes

In this letter, we propose a probabilistic approach to the generation of test patterns in the Chase Algorithm (CA) denoted as the Stochastic Chase Algorithm (SCA). We compare the performance of SCA with the regular CA for different Reed-Solomon codes. Simulation results show that the probabilistic nature of the SCA helps in providing a more efficient test pattern generation. SCA avoids the use of least reliable bits selection and reduces the number of candidate codewords up to 60% for the same decoding performance.

I. INTRODUCTION

T HE Chase Algorithm (CA) [1] and Generalized Mini- mum Distance (GMD) decoding [START_REF] Forney | Generalized minimum distance decoding[END_REF] are soft-decoding methods satisfying the property that a Hard Decision Decoder (HDD) is used to generate a set of candidate codewords that are compared by a likelihood measure. GMD and CA provide near-Maximum-Likelihood (ML) performance for high SNR values. It is important to efficiently generate a set of candidate codewords in such a way that the ML-codeword is included in the set. This set becomes rapidly large as the minimum distance of the code increases. We propose a probabilistic approach, denoted by Stochastic Chase Algorithm (SCA), to generate the candidate codewords for soft-decoding of Reed-Solomon (RS) codes.

II. STOCHASTIC TEST PATTERN GENERATION IN THE CHASE ALGORITHM

A. Model of the Communication System

Let 𝐶(𝑛, 𝑘, 𝑑) be a linear block code of size 𝑛, with dimension 𝑘 and minimum distance 𝑑. An information vector 𝑈 = (𝑢 1 , 𝑢 2 , ..., 𝑢 𝑘 ) is encoded to a codeword 𝑋 = (𝑥 1 , 𝑥 2 , ..., 𝑥 𝑛 ) ∈ 𝐶. Each 𝑥 𝑖 is transmitted over an Additive White Gaussian Noise (AWGN) channel using Binary Phase Shift Keying (BPSK) modulation. At the receiver side, the soft input of the decoder is computed from the received sequence 𝑌 = (𝑦 1 , 𝑦 2 , ..., 𝑦 𝑛 ). The soft input can either be represented in the probability domain 𝑃 = (𝑝 1 , 𝑝 2 , ..., 𝑝 𝑛 ) with:

𝑝 𝑖 = Pr(𝑦 𝑖 |𝑥 𝑖 = 1) = 1 1 + 𝑒 2𝑦 𝑖 𝜎 2
Manuscript received April 12, 2010. The associate editor coordinating the review of this letter and approving it for publication was M. Lentmaier.

The authors are with the Department of Electrical and Computer Engineering, McGill University, Montreal, QC, H3A2A7, Canada (e-mail: {camille.leroux, saied.hemati, shie.mannor, warren.gross}@mcgill.ca). S. Mannor is also with the Department of Electrical Engineering, Technion, Haifa Israel (e-mail: shie@ee.technion.ac.il).

Digital Object Identifier 10.1109/LCOMM.2010.09.100594

or in log-likelihood ratio domain 𝑅 = (𝑟 1 , 𝑟 2 , ..., 𝑟 𝑛 ) where

𝑟 𝑖 = 2𝑦 𝑖 𝜎 2 , 𝑖 = 1, ..., 𝑛.
Let 𝑌 𝐻 = (𝑦 𝐻 1 , 𝑦 𝐻 2 , ..., 𝑦 𝐻 𝑛 ) be the bit-wise hard decision sequence such that:

𝑦 𝐻 𝑖 = { 0, if 𝑟 𝑖 ≥ 0 or 𝑝 𝑖 ≤ 0.5, 1, otherwise.
The reliability of the hard decision 𝑦 𝐻 𝑖 is measured by the magnitude |𝑟 𝑖 | in log-likelihood ratio domain or equivalently by |𝑝 𝑖 -0.5| in probability domain.

B. The Chase Algorithm

The CA [START_REF] Chase | Class of algorithms for decoding block codes with channel measurement information[END_REF] performs a hard decision decoding on a set of test patterns 𝑌 𝑚 . A test pattern is devised by inverting at most 𝜆 least reliable bits in the received sequence 𝑌 . The decoded codeword is selected using the soft distance between 𝑌 and the corrected test pattern 𝑋 𝑚 (candidate codeword). Reference [START_REF] Chase | Class of algorithms for decoding block codes with channel measurement information[END_REF] proposed three different versions of this algorithm. They differ in the least reliable bit selection and in the test pattern generation method. The performance and the complexity of the algorithm increase with 𝜆. In this work, we consider 𝜆 ≥ 𝑑. The CA can be described using the following steps:

1) For 1 ≤ 𝑖 ≤ 𝑛, compute 𝑟 𝑖 = 2𝑦𝑖 𝜎 2 . 2) Select the 𝜆 least reliable bits in 𝑅.

3) For 1 < 𝑚 < 2 𝜆 ,

• Form the test pattern 𝑌 𝑚 by inverting some of the least reliable bits,

• Perform Berlekamp-Massey (BM) HDD on 𝑌 𝑚 to get 𝑋 𝑚 , • Compute the soft weight of 𝑌 𝐻 ⊕ 𝑋 𝑚 : 𝑊 (𝑌 𝐻 ⊕ 𝑋 𝑚 ) = 𝑛 ∑ 𝑖=1 |𝑟 𝑖 |(𝑦 𝐻 𝑖 ⊕ 𝑥 𝑚 𝑖 ).
4) Select the decided word 𝐷 such that:

𝐷 = 𝑋 𝑗 , 𝑊(𝑌 𝐻 ⊕ 𝑋 𝑗 ) = 2 𝜆 min 𝑚=1 𝑊 (𝑌 𝐻 ⊕ 𝑋 𝑚 ).
For high-rate medium-size codes, the CA provides near-ML performance while having low complexity. But at lower rates (𝑖.𝑒., larger 𝑑), the number of required test patterns grows exponentially with 𝑑.

C. The Stochastic Chase Algorithm

In the proposed Stochastic Chase Algorithm, the test pattern selection is modeled as a bit-wise stochastic experiment directed by the observation of the channel output. Each test pattern bit 𝑦 𝑚 𝑖 is generated according to the reliability of the 1089-7798/10$25.00 c ⃝ 2010 IEEE received bit |𝑝 𝑖 -0.5|. The SCA consists of the following steps:

1) For 1 ≤ 𝑖 ≤ 𝑛,

• If 𝑝 𝑖 ≤ 0.5 -𝜃 then 𝑝 𝑖 = 0, where 0 < 𝜃 < 0.5,

• Else If 𝑝 𝑖 ≥ 0.5 + 𝜃 then 𝑝 𝑖 = 1, • Else 𝑝 𝑖 = 1 1+𝑒 𝛽𝑦 𝑖 , where 𝛽 > 0. 2) For 1 < 𝑚 < 𝜏 • For 1 < 𝑖 < 𝑛
-Generate a uniformly distributed random value:

𝑠 𝑖 ∈ [0, 1]. -Generate 𝑦 𝑚 𝑖 = { 0, if 𝑠 𝑖 ≤ 𝑝 𝑖 , 1, otherwise.
• Perform BM-HDD on 𝑌 𝑚 to get 𝑋 𝑚 .

• Compute the soft weight of 𝑌 𝐻 ⊕ 𝑋 𝑚 :

𝑊 (𝑌 𝐻 ⊕ 𝑋 𝑚 ) = 𝑛 ∑ 𝑖=1 |𝑝 𝑖 -0.5|(𝑦 𝐻 𝑖 ⊕ 𝑥 𝑚 𝑖 ).
3) Select the decided word 𝐷 such that:

𝐷 = 𝑋 𝑗 , 𝑊 (𝑌 𝐻 ⊕ 𝑋 𝑗 ) = 𝜏 min 𝑚=1 𝑊 (𝑌 𝐻 ⊕ 𝑋 𝑚 ).
Step 1 saturates the most reliable input according to some threshold 𝜃. It prevents the most reliable bits from being flipped. The parameter 𝛽 is a positive constant that has to be optimized for the code. This factor is equivalent to the Noise Dependent Scaling (NDS) used in stochastic decoding of LDPC codes [START_REF] Sharifi Tehrani | Stochastic decoding of LDPC codes[END_REF], which improves the decoding performance. This parameter reduces the average value of |𝑝 𝑖 -0.5|, and consequently the number of identical test patterns decreases. Furthermore, similar to the NDS, the soft input is independent from the noise power 𝜎 2 . Therefore, the noise power estimation is not required.

In step 2, 𝜏 test patterns are generated bit-wise in such a way that unreliable bits are more likely to be flipped. This probabilistic generation of test patterns is similar to stochastic computation used in LDPC decoding [START_REF] Gaudet | Iterative decoding using stochastic computation[END_REF]. As opposed to the CA, the SCA does not limit the search to the subset defined by the least reliable bits. For instance, if the error pattern contains an error on the (𝜆 + 1) 𝑡ℎ least reliable bit, the CA will not be able to correct it because the erroneous bit is out of the searched space. However, this particular bit may be flipped by the SCA and the correct codeword would be considered. Furthermore, in the CA, in order to get close to MLperformance, the number of considered Least Reliable Bits (LRB) 𝜆 should be proportionnal to 𝑑 and the LRB search complexity is 𝑂(𝜆𝑛). It means that the LRB search becomes rapidly complex for low rate codes (i.e., large minimum distance). However, in the SCA, the LRB search is replaced by a stochastic generation of test patterns. This probabilistic process is a bit-wise operation and has a complexity 𝑂(𝑛). The SCA is then well adapted to large block length and low rate codes. In terms of hardware implementation, a high parallelism level can be reached by implementing 𝑛 independent random generators. It is also possible to use several instanciations of the same SCA decoder (simply with different seeds) in order to reduce the latency. If we assume an infinite number of trials 𝜏 , 0 < 𝑝 𝑖 < 1, and 𝜃 = 0.5, then all the possible codewords will be generated which means that the SCA is an asymptotically ML-decoder.

III. SOFT DECODING OF RS CODES

An (𝑛, 𝑘, 𝑑) RS code is defined over the Galois field 𝐺𝐹 (2 𝑀 ) with length 𝑛 = 2 𝑀 -1, dimension 𝑘 and minimum distance 𝑑 at a symbol level. Each symbol in 𝐺𝐹 (2 𝑀 ) can be mapped to a binary image according to a basis in 𝐺𝐹 (2): 𝐵 = (𝑏 1 , 𝑏 2 , ..., 𝑏 𝑀 ). The resulting binary linear block code has a length 𝑛 𝑏 = 𝑛 × 𝑀 , a dimension 𝑘 𝑏 = 𝑘 × 𝑀 and a binary minimum distance 𝑑 𝑏 ≥ 𝑑.

Recently, several solutions have been proposed for soft decision decoding of RS codes. Some of these are based on polynomial interpolation [START_REF] Koetter | Algebraic soft-decision decoding of Reed-Solomon codes[END_REF], which provide good performance but require complex computation structures. Adaptive Belief Propagation (ABP) algorithm was proposed in [START_REF] Jiang | Iterative soft-input soft-output decoding of Reed-Solomon codes by adapting the parity-check matrix[END_REF], it provides even better performance but requires Gaussian eliminations on the parity check matrix which leads to a prohibitive complexity. In [START_REF] El-Khamy | Iterative algebraic soft-decision list decoding of Reed-Solomon codes[END_REF], it was shown that the association of ABP and the Koetter Vardy (KV) algorithm can achieve the ML lower bound for the RS(31,25). However, this solution also suffers from high complexity. In [START_REF] Jiang | Iterative soft decoding of Reed-Solomon codes[END_REF], a Stochastic Shifting based Iterative Decoding (SSID) provides reasonable coding gain but requires more than 10000 BP iterations for the RS(31,25) code and it only applies to cyclic codes. In [START_REF] Lee | Stochastic erasure-only list decoding algorithms for Reed-Solomon codes[END_REF] Gaussian noise is added to the received sequence in order to generate candidate codewords. After each iteration, the parameters of the Gaussian noise are updated according to the best candidate codeword, which requires a large amount of memory and complex computations. This method is called Stochastic Erasure-Only List Decoding (SEOLD). In [START_REF] Fossorier | Reliability-based decoding of Reed-Solomon codes using their binary image[END_REF], an Iterative Box and Match (IT-BMA) approach is used which provides good performance but requires complex computations. Finally, minimum distance based (Chase, GMD) algorithms are efficient solutions when a few test patterns have to be generated (i.e., for high rate codes). However, they become complex when the minimum distance increases.

IV. SIMULATION RESULTS

In this section, we simulate the performance of different RS codes on an AWGN with BPSK modulation scheme, such that soft inputs are computed bit-wise (see Section II.A.). We use the Berlekamp-Massey (BM) algorithm [START_REF] Berlekamp | Algebraic Coding Theory[END_REF], [START_REF] Massey | Shift-register synthesis and BCH decoding[END_REF] for HDD. SCA performance is compared with CA and also with different reported soft decoding algorithms. We refer to Adaptive Belief Propagation algorithm [START_REF] Jiang | Iterative soft-input soft-output decoding of Reed-Solomon codes by adapting the parity-check matrix[END_REF] as ABP(𝐴×𝐴 ′ ) where 𝐴 represents the number of BP iterations per outer round and 𝐴 ′ refers to the number of outer rounds (Gaussian elimination on the parity check matrix). We refer to the Koetter-Vardy algorithm [START_REF] Koetter | Algebraic soft-decision decoding of Reed-Solomon codes[END_REF] as KV(𝜇) where 𝜇 represents the maximum multiplicity. SSID [START_REF] Jiang | Iterative soft decoding of Reed-Solomon codes[END_REF] with 𝐴 BP-iterations per outer round and 𝐴 ′ outer rounds (stochastic shift) is labeled SSID(𝐴 × 𝐴 ′ ). SEOLD [START_REF] Lee | Stochastic erasure-only list decoding algorithms for Reed-Solomon codes[END_REF] with 𝐴 iterations is labeled SEOLD(𝐴). SCA(𝜏 ) and CA(𝑚) refer to SCA with 𝜏 trials and CA with 𝑚 = 2 𝜆 test patterns, respectively.

We first present results for the RS(31,25) code which has a binary minimum distance 𝑑 𝑏 = 7. In order to have a fair comparison between the CA and the SCA, we set the number of trials of the SCA and the number of test patterns in the CA to the same value: 𝜏 = 2 𝜆 = 1024. As shown in Fig. 1, SCA provides a 0.15dB coding gain over CA, and approaches the ML lower bound within 0.5dB at a Frame Error Rate (FER) of 10 -4 . It is also close to the ABP(20 × 3) performance which requires 60 BP iterations and 3 Gaussian eliminations on the parity check matrix. The SCA provides 0.4dB gain at FER= 10 -4 compared to existing stochastic methods (SEOLD and SSID) that also have higher computational complexity. Performance of the widely used RS(255,239) code is considered in Fig. 2. SCA(1024) provides 0.15dB coding gain compared to KV(100). The performance can be traded off with complexity by increasing 𝜏 , the performance of SCA(65K) is 0.4dB away from IT-BMA [START_REF] Fossorier | Reliability-based decoding of Reed-Solomon codes using their binary image[END_REF]. It is also 0.6dB away from the ABP(80 × 50) which requires 50 Gaussian eliminations and 4K BP iterations. The ML lower bound in this figure is based on [START_REF] El-Khamy | Bounds on the minimum distance and the maximum likelihood performance of Reed-Solomon codes[END_REF].

Table I compares the number of required test patterns in SCA with CA for different RS codes, at identical decoding performance. Results show that SCA reduces the number of test patterns by 46% to 60%.

V. CONCLUSION

In this letter, we proposed a modification of the Chase Algorithm in which a stochastic generation of test patterns is used. Simulations show that our modification provides a low cost solution for soft-decoding of RS codes. In the CA, the least reliable bits selection process requires at least (𝑛 × 𝜆) comparisons, which becomes complex for large codes. The test pattern generation can be seen as an exhaustive search in a predetermined subset of the code 𝐶. On the contrary, in the SCA no least reliable bits selection is required. It is replaced by a simple stochastic generator which consists of a random number generator and a comparator. The complexity of SCA is tractable even for large-size and low-rate codes. It is possible to further improve the performance of SCA by preventing the generation of identical test patterns but it would increase the complexity. Just like the CA, our modification can be applied to decoding of any linear block code that has an HDD algorithm. It could, for example, be used for soft decoding of BCH codes. It is also possible to add a soft output computation stage in order to perform iterative decoding of product codes [START_REF] Pyndiah | Near optimum decoding of product codes[END_REF].

Fig. 1 .

 1 Fig. 1. RS(31,25) code on AWGN, 𝛽 = 6, 𝜃 = 0.45.

Fig. 2 .

 2 Fig. 2. RS(255,239) code on AWGN, 𝛽 = 22, 𝜃 = 0.5.