Sara Bouraine

Thierry Fraichard

Hassen Salhi

Provably Safe Navigation for Mobile Robots with Limited Field-of-Views in Unknown Dynamic Environments

This paper addresses the problem of navigating a mobile robot with a limited field-of-view in a unknown dynamic environment. In such a situation, absolute motion safety, i.e. such that no collision will ever take place whatever happens, is impossible to guarantee. It is therefore settled for a weaker level of motion safety dubbed passive motion safety: it guarantees that, if a collision takes place, the robot will be at rest. Passive motion safety is tackled using a variant of the Inevitable Collision State (ICS) concept called Braking ICS, i.e. states such that, whatever the future braking trajectory of the robot, a collision occurs before it is at rest. Passive motion safety is readily obtained by avoiding Braking ICS at all times. Building upon an existing Braking ICS-Checker, i.e. an algorithm that checks if a given state is a Braking ICS or not, this paper presents a reactive collision avoidance scheme called PASSAVOID. The main contribution of this paper is the formal proof of PASSAVOID's passive motion safety. Experiments in simulation demonstrates how PASSAVOID operates.

I. INTRODUCTION

Robotics technology has matured and Autonomous Ground Vehicles are becoming a reality. However such systems remains prone to accidents (see [START_REF] Fletcher | The MIT-Cornell collision and why it happened[END_REF]). The literature review of §II shows that the Robotics community is displaying a growing interest in designing navigation schemes for which motion safety can be characterized or even guaranteed (see the 2012 special issue of Autonomous Robots on Guaranteeing Motion Safety for Robots). It also shows that motion safety in the real world remains an open problem as soon as the term real world implies that:

1) The environment features both fixed and moving objects whose future behaviour is unknown.

2) The robot has only a partial knowledge of its surroundings because of its sensory limitations. The purpose of this paper is precisely to address such problems. It can be argued that absolute motion safety is impossible to guarantee in general unless questionable assumptions concerning the robot and its environment are made, e.g. requiring that the velocity of the robot is a multiple of the maximum velocity of the objects [START_REF] Lumelsky | Velocity bounds for motion planning in the presence of moving planar obstacles[END_REF], or that the moving objects should appear beyond a distance which is a function of their number, sizes and velocities [START_REF] Kohout | Guaranteeing safety in spatially situated agents[END_REF]. To cope with that issue, the position taken in this work is: better guarantee less than guarantee nothing. To that end, it is settled for a weaker level of motion safety that guarantees that, if a collision takes place, the robot will be at rest. As per [START_REF] Macek | Towards safe vehicle navigation in dynamic urban scenarios[END_REF], this motion safety level is dubbed passive motion safety. As limited as it may appear at first sight, passive † CDTA (AL); ‡ INRIA (FR); Blida Univ. (AL).

Journal article [START_REF]Provably safe navigation for mobile robots with limited fieldof-views in dynamic environments[END_REF] combines [START_REF] Bouraine | Relaxing the inevitable collision state concept to address provably safe mobile robot navigation with limited field-of-view in unknown dynamic environments[END_REF] and this paper.

motion safety is interesting for two reasons: (1) it allows to provide at least one form of motion safety guarantee in the challenging scenarios considered and more important (2) if every moving object in the environment enforces it then no collision ever take place at all. The central idea behind passive motion safety, i.e. using braking trajectories, is not new, it has been used before in different contexts (see §II). However, to the best of the authors' knowledge, it is the first time it is given a formal treatment in as general a context as possible whether it concerns the robot's dynamics, its fieldof-view, or the knowledge (or lack thereof) about the future behaviour of the moving objects. Passive motion safety is tackled herein using a variant of the Inevitable Collision State (ICS) concept [START_REF] Fraichard | Inevitable collision states. a step towards safer robots?[END_REF] called Braking ICS, i.e. states such that, whatever the future braking trajectory followed by the robot, a collision occurs before it is at rest. Passive motion safety is readily obtained by avoiding Braking ICS at all times. Braking ICS have been introduced by the authors of this paper in [START_REF] Bouraine | Relaxing the inevitable collision state concept to address provably safe mobile robot navigation with limited field-of-view in unknown dynamic environments[END_REF] along with a Braking ICS-Checker, i.e. an algorithm that determines whether a given state is a Braking ICS or not. To validate the Braking ICS concept and demonstrate its usefulness, the Braking ICS-Checker of [START_REF] Bouraine | Relaxing the inevitable collision state concept to address provably safe mobile robot navigation with limited field-of-view in unknown dynamic environments[END_REF] is integrated here in a reactive collision avoidance scheme (henceforth called PASSAVOID) for a mobile robot with a limited field-of-view placed in an unknown dynamic environment. It operates with a given time step and its purpose is to compute the control that will be applied to the robot at the next time step. The main contribution of this paper is the formal proof of PASSAVOID's passive motion safety: it is guaranteed that the robot will always avoid Braking ICS no matter what happens in the environment.

The paper is organized as follows: a review of the relevant literature is done in §II while the problem addressed is defined in §III. PASSAVOID is then detailed in §IV, the proof of its passive motion safety is established there along with the proof that if every moving object enforces it then no collision ever take place. Finally, experimental results obtained in simulation are presented in §V.

II. RELATED WORKS

As mentioned above, the Robotics literature is teeming with works concerned with collision avoidance but most of them do not offer an explicit formulation of the safety guarantees they provide or the conditions under which they must operate (see [START_REF] Fraichard | A short paper about motion safety[END_REF]). The earliest relevant works addressed the so-called "Asteroid Avoidance Problem": in 3D, [START_REF] Reif | Motion planning in the presence of moving obstacles[END_REF] shows that collision avoidance is always possible if the robot's velocity is greater than the asteroids' velocities. In 2D, [START_REF] Kohout | Guaranteeing safety in spatially situated agents[END_REF] shows that collision avoidance is always possible iff the asteroids appear beyond a "threat horizon". Likewise, [START_REF] Lumelsky | Velocity bounds for motion planning in the presence of moving planar obstacles[END_REF] shows that, for a 2D robot among arbitrarily moving objects, collision-avoidance is guaranteed iff the maximum velocity of the robot is a multiple of the maximum velocity of the objects. Such results are very interesting. Unfortunately, they rely on assumptions that rarely occur in the real world. A related family of research works are those seeking to coordinate the motion of a set of robots. Different distributed coordination schemes have been proposed for which collision avoidance is guaranteed, e.g. [START_REF] Bekris | Safe and distributed kinodynamic replanning for vehicular networks[END_REF], [START_REF] Lalish | Decentralized reactive collision avoidance for multivehicle systems[END_REF]. However, this guarantee is lost if the environment contains uncontrolled moving objects. General motion safety issues have been studied thanks to the Inevitable Collision States (ICS) concept developed in [START_REF] Fraichard | Inevitable collision states. a step towards safer robots?[END_REF]. An ICS is a state for which, no matter what the future trajectory of the robot is, a collision eventually occurs. ICS provides insight into the complexity of guaranteeing motion safety since it shows that it requires to reason about the future evolution of the environment and to do so with an appropriate lookahead 1 that can possibly be infinite. Such conditions being next to impossible to obtain in the real world plus the fact that ICS characterization is very complex has led a number of authors to consider relaxations of ICS such as:

• ICS approximation, e.g. [START_REF] Kalisiak | Faster motion planning using learned local viability models[END_REF]: such approximations being not conservative, the motion safety guarantee is lost. • τ -Safety, e.g. [START_REF] Frazzoli | Real-time motion planning for agile autonomous vehicle[END_REF]: the robot is guaranteed to remain in states where it is safe for a given duration (hopefully sufficient to compute an updated safe trajectory. . . ). • Evasive trajectories, e.g. [START_REF] Hsu | Randomized kinodynamic motion planning with moving obstacles[END_REF]: they guarantee that the robot can only be in states where it is possible to execute an evasive trajectory, e.g. a braking manoeuvre for a car or a circling manoeuvre for a plane. Recently, authors have proposed probabilistic versions of the ICS concept, e.g. [START_REF] Bautin | Inevitable collision states, a probabilistic perspective[END_REF], so as to better capture the uncertainty that prevails in real world situations. These approaches are interesting but offer no strict motion safety guarantees since probabilistic models are used. There are a few research works taking into account sensory limitations. For instance, the occlusion problem, i.e. the existence of regions that are hidden by other objects, is addressed in [START_REF] Sadou | Occlusion in obstacle detection for safe navigation[END_REF] and [START_REF] Chung | Safe navigation of a mobile robot considering visibility of environment[END_REF]. The occlusion and the limited field-of-view problems are addressed in [START_REF] Fraichard | Inevitable collision states. a step towards safer robots?[END_REF] and [START_REF] Madhava Krishna | Safe proactive plans and their execution[END_REF].

The contribution of this paper is an extension of [START_REF] Macek | Towards safe vehicle navigation in dynamic urban scenarios[END_REF] that deals with limited field-of-views, occlusions and unknown future behaviour of the objects. The approach proposed is based upon a relaxation of ICS that falls into the "evasive trajectories" family.

III. STATEMENT OF THE PROBLEM

Let A denote the mobile robot at hand. It operates in a 2D workspace W. Its motion is governed by differential equations of the form:

ṡ = f (s, u) subject to g(s, ṡ) ≤ 0 (1)
1 I.e. how far into the future the reasoning is done. where s ∈ S is the state of A, ṡ its time derivative and u ∈ U a control. S and U respectively denote the state space and the control space of A. Let A(s) denote the closed subset of the workspace W occupied by A when it is in s.

Let ũ : [0, t f ] -→ U denote a control trajectory, i.e. a time-sequence of controls, t f is the duration of ũ. The set of all possible control trajectories is denoted Ũ. Starting from an initial state s 0 at time 0, a state trajectory s, i.e. a timesequence of states, is derived from a control trajectory ũ by integrating (1); s(s 0 , ũ, t) denotes the state reached at time t. A control trajectory ũb ∈ Ũ such that sb (s 0 , ũb , t b ) is a state where A comes to a halt (and remains so) is a braking trajectory for s 0 and t b is its braking time. The set of all possible braking trajectories for s 0 is denoted Ũs 0 b . Assuming that A is equipped with range sensors such as laser telemeters or range cameras, it can only perceive a subset of W; this subset is A's field-of-view; its shape is arbitrary. It is henceforth denoted FOV. Accordingly, W is partitioned in three subsets: (1) FOV, (2) FOV c , the part which is unseen (FOV c = W \ cl(FOV)) and (3) ∂FOV, the boundary between the two. Both FOV and FOV c are open sets. It seems reasonable to assume that A is "looking around itself"; in other words that A(s) ⊂ FOV where A(s) denotes the region of W occupied by A when it is in s. To account for the existence of 3D range sensors, e.g. Velodyne LIDAR, FOV can contain holes representing objects entirely perceived by the sensory system of A. Accordingly, ∂FOV and FOV c are not necessarily singly connected (see Fig. 1).

FOV represents the region of W which is free of objects at the sensing time while ∂FOV ∪ FOV c represent objects (fixed or moving, seen and unseen). Recall that motion safety requires reasoning about the future motion of the objects in the environment. The model of the future used herein is conservative: it is assumed that A cannot distinguish the fixed from the moving objects (hence every object observed is treated as a potentially moving object), and that it has no information whatsoever about their future behaviour. Accordingly, given an upper-bound on the velocity of the objects, every point in ∂FOV ∪ FOV C d is modeled as a disc that grows as time passes, i.e. a cone in space×time (see [START_REF] Bouraine | Relaxing the inevitable collision state concept to address provably safe mobile robot navigation with limited field-of-view in unknown dynamic environments[END_REF]).

IV. PASSIVELY SAFE NAVIGATION

A. Braking ICS

Ref. [START_REF] Bouraine | Relaxing the inevitable collision state concept to address provably safe mobile robot navigation with limited field-of-view in unknown dynamic environments[END_REF] introduces a relaxation of the original ICS concept called Braking ICS. A Braking ICS (henceforth denoted ICS b ) is a state for which, no matter what the future trajectory of the robot is, it is impossible to stop before a collision takes place. Braking ICS and passive safety are two dual concepts: a state which is not a Braking ICS is p-safe. An efficient Braking ICS-Checker (henceforth called ICS b -CHECK) is also presented in [START_REF] Bouraine | Relaxing the inevitable collision state concept to address provably safe mobile robot navigation with limited field-of-view in unknown dynamic environments[END_REF], it checks whether a given state is a Braking ICS or not for a given model of the future.

B. PASSAVOID

In order to demonstrate passive motion safety and to validate the Braking ICS concept, a navigation scheme (henceforth called PASSAVOID) has been developed for a mobile robot A with a limited field-of-view placed in a unknown dynamic environment. PASSAVOID's primary task is to keep A in p-safe states, or equivalently, to drive A away from Braking ICS. PASSAVOID guarantees passive motion safety no matter what happens in the environment. In other words, if a collision takes place, it is guaranteed that A will be at rest when it occurs. PASSAVOID relies upon ICS b -CHECK to operate. It is a reactive navigation scheme that operates with a given time step δt. At each time step, its purpose is to compute the constant control u that will be applied to A during the next time step; u must be admissible, i.e. the corresponding state trajectory must be p-safe (in other words, it must be ICS b -free).

PASSAVOID operates like most standard reactive collision avoidance schemes, (e.g. [START_REF] Fiorini | Motion planning in dynamic environments using velocity obstacles[END_REF], [START_REF] Fox | The dynamic window approach to collision avoidance[END_REF]). In all cases, their operating principle is to first characterize forbidden regions in a given control space and then select an admissible control, i.e. one which is not forbidden. Accordingly collision avoidance also depends on the ability of the collision avoidance scheme at hand to find such an admissible control. In the absence of a formal characterization of the forbidden regions, all schemes resort to some form of sampling of the control space with the inherent risk of missing the admissible regions. PASSAVOID also resorts to sampling in order to find an admissible control. However, in contrast with standard collision avoidance schemes, PASSAVOID is designed in such a way that it is guaranteed that, if an admissible control exists, it will be part of the sampling set. The operating principle of PASSAVOID is illustrated in Fig. 2. Let s 0 denote the current state of A and U a sampled set of controls: U = {u 1 . . . u m }. A given control u j ∈ U is applied to A for a duration δt. It takes A from the state s 0 to the state s j = s(s 0 , u j , δt). If the state trajectory between s 0 and s j is p-safe then u j is admissible. Using the Sufficient Safety Condition established in [START_REF] Petti | Safe motion planning in dynamic environments[END_REF], the admissibility of u j can equivalently be verified by checking that (1) the state trajectory between s 0 and s j is collision-free (with respect to the model of the future), and that (2) s j is p-safe, i.e. it is not a Braking ICS. This procedure is applied for every control in U ; it yields a set of admissible controls denoted U * from which PASSAVOID can pick the control to apply during the next time step. This selection can be made arbitrarily if one is only concerned with the survival of A or it can be made so as to ensure convergence towards a given goal (using for instance a global navigation function, a potential field, or even a partial motion planning scheme).

Such a scheme works well as long as an admissible control can be found in U . But if, at the end of the day, U * is empty, it means that every control in U takes A to a Braking ICS. In other words, passive motion safety will not be achieved and a collision will take place while A is still moving. To address this issue, it is necessary to guarantee that U = {u 1 . . . u m } contains at least one admissible control. It is possible to achieve this by carefully designing PASSAVOID. To that end, a number of definitions and properties are required. They are introduced now. The concepts of δ-braking trajectory and δpassive safety are defined first. They are just specific types of braking trajectory and passive safety:

Def. 1 (δ-Braking Trajectory): A braking trajectory ũ * ∈ Ũs 0 b of duration t * is a δ-braking trajectory if it is constant over intervals of fixed duration δt.

A δ-braking trajectory is just a special type of braking trajectory (see Fig. 2). It yields a corresponding type of passive motion safety:

Def. 2 (δ-Passive Safety): A state s 0 is δ-passively safe or δ-p-safe if it exists one δ-braking trajectory ũ * starting at s 0 which is collision-free until A has stopped. Then two useful properties are established:

Property 1 (P-Safe States): If the state s 0 is p-safe and the braking trajectory ũb ∈ Ũs 0 b starting at s 0 is collision-free until A has stopped then every state s(s 0 , ũj , t), 0 < t ≤ t b is also p-safe.

Proof: Suppose that ∃t i ∈]0, t b ] such that s(s 0 , ũb , t i ) is not p-safe then, by definition, ∀ũ j ∈ Ũs i b , ũj yields a collision before A stops. This also applies to the braking trajectory corresponding to the restriction of ũb to the time interval [t i , t b ] which yields a contradiction. Note that Property 1 also applies to δ-p-safe states.

Property 2 (δ-Passive Safety Guarantee): If the state s 0 is δ-p-safe then there exists at least one admissible control u * that PASSAVOID can use to drive A to a state which is also δ-p-safe.

Proof: Since s 0 is δ-p-safe, there exists at least a one δ-braking trajectory ũ * starting at s 0 which is collision-free until A has stopped. As per Property 1, the state s(s 0 , ũ * , δt) is δ-p-safe. Let u * denote the value of ũ * over the time interval [0, δt[, u * is an admissible control.

Property 2 is fundamental for the design of a version of PASSAVOID whose passive motion safety can be guaranteed. PASSAVOID simply has to drive A from one δ-p-safe state to the next. Now, assuming that s 0 is δ-p-safe, property 2 12 guarantees the existence of at least one admissible control u * which, if applied to A for the duration δt, will take it to another δ-p-safe state. In general, a δ-p-safe state s has more than one admissible control. Let K(s) denote this set of admissible controls, it is dubbed the kernel K(s). Now, in order to guarantee its passive motion safety, PASSAVOID must include K(s 0 ) in its control space sampling set. This is precisely what PASSAVOID does (see Algorithm 1, line #2). PASSAVOID features two important steps: computing the kernel K(s 0 ) (line #2) and checking whether the state s(δt) is δ-p-safe (line #6). It turns out that these two procedures are related and can be done by a straightforward adaptation of ICS b -CHECK which is not detailed here due to lack of space (see [START_REF]Provably safe navigation for mobile robots with limited fieldof-views in dynamic environments[END_REF]). Now, provided that the initial state of the system A is δp-safe, Property 2 allows PASSAVOID to have at its disposal at each time step an admissible control that can be used to drive A from one δ-p-safe state to the next (forever if need be). Concerning the assumption on the initial state being δ-p-safe, it is satisfied when A is at rest, and the null control is admissible. In other words, starting with A at rest, PASSAVOID has an admissible control readily available that can be used right away if the situation demands it (this is true even if δt is very small). At the end of the day, PASSAVOID is provably passively safe in the sense that it is guaranteed that A will always stay away from Braking ICS no matter what happens in the environment.

C. Passively Safe Multi-Robot Navigation

In the introduction, it was stated that, if every moving object in a given environment was passively safe, then no collision should take place at all. It turns out that this property is straightforward to demonstrate. Let A 1 and A 2 denote two robots that are driven by a provably passively safe navigation scheme such as PASSAVOID. As per Properties 1 and 2, both A 1 and A 2 are in a δ-p-safe state at all times.

In other words, the following holds:

∀t, s 1 (t) ∈ ICS b 1 and s 2 (t) ∈ ICS b 2 (2)
where s i (t) and ICS b i respectively denote the state at time t and the corresponding Braking ICS set for robot A i , i = 1, 2. Assuming that a collision can take place between A 1 and A 2 with one of them having a non zero velocity yields a contradiction. It cannot happen.

V. SIMULATION RESULTS

To validate the Braking ICS concept and demonstrate its usefulness, ICS b -CHECK and PASSAVOID have both been implemented and tested in simulation.

A. Model of the Robot

The model of A is that of a standard car-like vehicle with two fixed rear wheels and two orientable front wheels. A state of A is a 5-tuple s = (x, y, θ, v, ξ) with (x, y) the coordinates of the rear axle midpoint, θ the orientation of A, v the linear velocity of system, and ξ the orientation of the front wheels (steering angle). A control of A is a couple u = (u α , u ξ ) with u α the linear acceleration of the rear wheels and u ξ the steering angle velocity. Let L denote the wheelbase of A. The motion of A is governed by the following differential equations:

      ẋ ẏ θ v ξ       =       v cos θ v sin θ v tan ξ/L 0 0       +       0 0 0 1 0       u α +       0 0 0 0 1       u ξ (3) with |v| ≤ v max , |ξ| ≤ ξ max , |u α | ≤ u αmax and |u ξ | ≤ u ξmax .

B. PASSAVOID at Work

To illustrate how PASSAVOID works, two scenarios have been selected. The first one is called the 1D Compactor scenario, it is simple but it helps to understand the kind of behaviour that PASSAVOID will yield when A is confronted to a clearly identified dangerous situation. The second one is called the Blind Crowd scenario; its primary purpose is to illustrate the performances of PASSAVOID in complex situations. The results obtained are also illustrated in a short film provided as a multimedia attachment to this paper 2 . In both cases, PASSAVOID had no information regarding the future trajectories of the moving objects. PASSAVOID did not attempt to drive A to a given goal. Its primary purpose was to keep A in p-safe states. Its secondary purpose was to keep A moving. In other words, the admissible control selection (line #10 of Algorithm 1) was biased towards controls yielding a non-zero linear velocity. This choice was made so as to avoid the straightforward answer to the passive motion safety problem which is simply to brake down and stop forever (by doing so, A reaches and stays in a p-safe state). In this scenario, when driven by PASSAVOID, A exhibits the following behaviour in order to always remain in p-safe states:

1) the increasing approach of B m forces A to gradually decrease its velocity until it stops. 2) A backs up in order to avoid collision with B m (recall that PASSAVOID is biased towards keeping A in motion). 3) while backing up, A gets closer to B f . At some point, it forces A to reduce its velocity. 4) A is now at rest next to B f , it will soon be hit by B m . 5) A is in collision with B m (t = 7s). 6) when the collision with B m is over3 , A resumes its upward motion.

The evolution of A's velocity in this scenario is depicted in Fig. 3-right. As simple as it may appear, this scenario shows how PASSAVOID seeks to avoid collision with B m in a natural way (by braking down and shifting in reverse). However, when A is trapped, PASSAVOID guarantees that the robot will be at rest when the collision occurs.

2) Blind Crowd Scenario: The blind crowd scenario is more challenging. It features 22 moving objects moving arbitrarily in a 2D workspace. The objects are blind in the sense that their motion is unaffected by the other objects. The parameters for this scenario were set as follows: v max = 15m.s -1 (maximum velocity of A and of the moving objects), ξ max = π/3rad, u αmax = 7m.s -2 , u ξmax = 1.54rad.s -1 . The radius of the disk objects was 2. Note: looking at the provided video for the two scenarios considered, it may appear that PASSAVOID could do better in terms of collision avoidance and overall behaviour. Recall however that PASSAVOID is just a reactive collision avoidance scheme, it has no foresight and is not concerned with driving A to a given goal. In the authors' opinion, the important result concerning PASSAVOID is the formal proof of its passive motion safety. These simulations merely serve as a proof of concept and to illustrate how PASSAVOID operates. Ways to improve PASSAVOID are discussed in §VI.

C. Complexity and Performance

The computational time complexity of PASSAVOID grows linearly with n s , the size of the control space sampling set U (forall loop of Algorithm 1), and the complexity of one iteration depends primarily on the complexity of ICS b -CHECK (δ-p-safety test in line #6 of Algorithm 1). Given that the complexity of ICS b -CHECK grows linearly with n b (the size of the set of braking trajectories), n o (number of objects) and n t (number of the time steps used to represent the model of the future), the final time complexity of PASSAVOID is O(n s n b n o n t ). The current implementation of both ICS b -CHECK and PASSAVOID has been done in C++ on an average laptop computer (Intel Core i7 1.6GHz CPU, 4GB RAM, ATI Mobility Radeon HD 4500 GPU). Table I gives the average running times of ICS b -CHECK wrt n 0 , the number of objects. These running times are encouraging and could further be improved thanks to code optimization (a CUDA implementation is underway), or the use of a more powerful desktop.

VI. CONCLUSION AND FUTURE WORK

This paper has addressed the problem of navigating in a provably safe manner a mobile robot with a fieldof-view placed in a unknown dynamic environment. The position taken in this paper was to guarantee of motion safety dubbed passive motion safety: if a collision takes place, the robot will be at rest. Passive motion safety has been tackled using a variant of the Inevitable Collision State (ICS) concept called Braking ICS [START_REF] Bouraine | Relaxing the inevitable collision state concept to address provably safe mobile robot navigation with limited field-of-view in unknown dynamic environments[END_REF], i.e. states such that, whatever the future braking trajectory followed by the robot, a collision occurs before it is at rest. To validate the Braking ICS concept and demonstrate its usefulness, the Braking ICS-Checker of [START_REF] Bouraine | Relaxing the inevitable collision state concept to address provably safe mobile robot navigation with limited field-of-view in unknown dynamic environments[END_REF] has been integrated in a reactive collision avoidance scheme called PASSAVOID. The main contribution of this paper has been to formally prove PASSAVOID's passive motion safety. This work could be extended in the following directions:

In certain situations, PASSAVOID may drive the robot to a collision state although such a collision could have been avoided. This is due to PASSAVOID's lack of foresight 4 . Besides, PASSAVOID is not concerned with driving the robot to a given goal. These issues could be addressed by turning PASSAVOID into a Partial Motion Planner à la [START_REF] Petti | Safe motion planning in dynamic environments[END_REF]. Such an extension would yield a navigation scheme better able to avoid collisions and to reach a given goal while retaining the passive motion safety guarantee.

It could also be interesting to explore more sophisticated levels of motion safety such as the passive friendly motion safety mentioned in [START_REF] Macek | Towards safe vehicle navigation in dynamic urban scenarios[END_REF]: it guarantees that, if a collision takes place, the robot will be at rest and the colliding object

Fig. 1 .

 1 Fig. 1. Robot with a limited field-of-view (left) and its corresponding planar field-of-view FOV (right).

Fig. 2 .

 2 Fig. 2. PASSAVOID's operating principle (left), and example of a δ-braking trajectory (right).

Algorithm 1 : 1 ] 2 U 5 s/ u j admissible 8 end 9 end 10 /

 11258910 PASSAVOID. Input: s 0 , the current δ-p-safe state of A; δt, the time step; model of the future. Output: u Sample U ; U = {u 1 . . . u m }// [ Select the control space sampling set U * = K(s 0 ); // Initialize adm. controls 3 forall u j ∈ U ; // Compute adm. controls 4 do (δt) = s(s 0 , u j , δt); 6 if s(s 0 , u j , [0, δt[) is collision-free and s(δt) is 7 δ-p-safe then U * = U * ∪ {u j }; // Select and return one adm. control Select u ∈ U * ; 11 return u;

Fig. 3 .

 3 Fig. 3. 1D compactor scenario (left); corresponding velocity profile of A (right).

1 )

 1 1D Compactor Scenario: The 1D Compactor scenario features one fixed object B f and one moving object B m . The moving object is moving towards the fixed object (see Fig. 3-left). B f and B m are like the two jaws of a compactor (hence the name of the scenario). A is placed between B f and B m and it is further assumed that A can only move along the vertical line connecting B f and B m . At the beginning, A is moving upward with a positive linear velocity. In such a situation, the initial state s 0 of A is clearly an ICS (no matter what A does it will end up being crushed by B m ). It is however possible to select A's initial position and linear velocity such that s 0 is p-safe. The parameters for this scenario were set as follows: v max = 20m.s -1 (maximum velocity of A and B m ), u αmax = 7m.s -2 . The radius of A and B m was 2.5m and the sensor range, i.e. the maximum radius of the field-of-view, was 80m. The control space sampling set U was obtained through a regular discretization of the control set [-u αmax , u αmax ]. The set of braking trajectories E used by ICS b -CHECK comprised one δ-braking trajectory defined by a constant minimum linear deceleration u α = -u αmax .

  5m and the sensor range, i.e. the maximum radius of the field-ofview, was 80m. The control space sampling set U was obtained through a regular discretization of the 2D control set [-u αmax , u αmax ] × [u ξmax , u ξmax ], and the set of braking trajectories E used by ICS b -CHECK comprised 9 δ-braking trajectories defined by a constant minimum linear deceleration u α = -u αmax and a constant steering angle velocity |u ξ | ≤ u ξmax .

Fig. 4 .

 4 Fig. 4. Snapshots of PASSAVOID at work in the blind crowd scenario (the black region represents the ICS b ).

Fig. 4

 4 Fig.4presents snapshots taken at different time instants of one run of PASSAVOID in this scenario. Each snapshot feature A (at the center), the moving objects and the corresponding field-of-view. The set of ICS b are also overlaid on the figure (black region).In the sequence, A is generally moving to the right. In the course of several runs, these experiments have demonstrated the capability of PASSAVOID to enforce passive motion safety: whenever a collision took place, A was at rest.Note: looking at the provided video for the two scenarios considered, it may appear that PASSAVOID could do better in terms of collision avoidance and overall behaviour. Recall however that PASSAVOID is just a reactive collision avoidance scheme, it has no foresight and is not concerned with driving A to a given goal. In the authors' opinion, the important result concerning PASSAVOID is the formal proof of its passive motion safety. These simulations merely serve as a proof of concept and to illustrate how PASSAVOID operates. Ways to improve PASSAVOID are discussed in §VI.

TABLE I AVERAGE

 I RUNNING TIME OF ICS b -CHECK wrt no, THE NUMBER OF OBJECTS (n b = 9, nt = 71).

	no	4	10	17	22
	Running time (ms) 49 101	123 138

Downloadable from http://emotion.inrialpes.fr/fraichard/films/11-auropassavoid.wmv.

[START_REF] Bouraine | Relaxing the inevitable collision state concept to address provably safe mobile robot navigation with limited field-of-view in unknown dynamic environments[END_REF] Assuming that Bm sort of passes through A.

PASSAVOID is purely reactive, its sole purpose is to compute the control to apply for the next time step.could have had the time to stop or avoid the collision (if it wanted to). Such a motion safety level assume that the moving objects have cognitive abilities and are not hostile (which happens to be true in many situations).


Morgan Barbier
email: morgan.barbier@unicaen.fr

Clément Pernet
email: clement.pernet@imag.fr

Guillaume Quintin
email: quintin@lix.polytechnique.fr

On the decoding of quasi-BCH codes

Keywords: Quasi-cyclic code, quasi-BCH code, BCH code, Reed-Solomon, interleaved code

In this paper we investigate the structure of quasi-BCH codes. In the first part of this paper we show that quasi-BCH codes can be derived from Reed-Solomon codes over square matrices extending the known relation about classical BCH and Reed-Solomon codes. This allows us to adapt the Welch-Berlekamp algorithm to quasi-BCH codes. In the second part of this paper we show that quasi-BCH codes can be seen as subcodes of interleaved Reed-Solomon codes over finite fields. This provides another approach for decoding quasi-BCH codes.

Introduction

Many codes with best known minimum distances are quasi-cyclic codes or derived from them [START_REF] Ling | Good self-dual quasi-cyclic codes exist[END_REF][START_REF] Grassl | Bounds on the minimum distance of linear codes and quantum codes[END_REF]. This family of codes is therefore very interesting. Quasi-cyclic codes were studied and applied in the context of McEliece's cryptosystem [START_REF] Mceliece | A Public-Key Cryptosystem Based On Algebraic Coding Theory[END_REF][START_REF] Berger | Reducing Key Length of the McEliece Cryptosystem[END_REF] and Niederreiter's [START_REF] Niederreiter | Knapsack-type cryptosystems and algebraic coding theory[END_REF][START_REF] Li | On the equivalence of McEliece's and Niederreiter's public-key cryptosystems[END_REF]. They permit to reduce the size of keys in opposition to Goppa codes. However, since the decoding of random quasi-cyclic codes is difficult, only quasi-cyclic alternant codes were proposed for the latter cryptosystem. The high structure of alternant codes is actually a weakness and two cryptanalysis were proposed in [START_REF] Faugère | Algebraic Cryptanalysis of McEliece Variants with Compact Keys[END_REF][START_REF] Umaña | Practical Key Recovery Attacks On Two McEliece Variants[END_REF] Theorem 1. Let Γ ∈ M ℓ×ℓ (F q s ) be a primitive m-th root of unity and C = Q-BCH q (m, ℓ, δ, Γ). Then there exists a RRS code R over the ring M ℓ×ℓ (F q s ) with parameters [n, nδ + 1] M ℓ×ℓ (F q s ) and a F q -linear, F q -isometric embedding ψ : C → R.

In the second part we show that quasi-BCH codes can be seen as subcodes of interleaved Reed-Solomon codes.

Theorem 2. The quasi-BCH code C over F q is an interleaved code of ℓ subcodes of Reed-Solomon codes over F q s ′ in the following sense: there exists ℓ Reed-Solomon codes C 1 , . . . , C ℓ over F q and an isometric isomorphism from C, equipped with the ℓ-block distance, to a subcode of the interleaved code with respect to C 1 , . . . , C ℓ .

Related work

In [START_REF] Lally | Algebraic structure of quasicyclic codes[END_REF][START_REF] Ling | On the algebraic structure of quasi-cyclic codes .I. Finite fields[END_REF], ℓ-quasi-cyclic codes of length mℓ are seen as R-submodules of R ℓ for a certain ring R. However, in [START_REF] Lally | Algebraic structure of quasicyclic codes[END_REF], Gröbner bases are used in order to describe polynomial generators of quasi-cyclic codes whereas in [START_REF] Ling | On the algebraic structure of quasi-cyclic codes .I. Finite fields[END_REF], the authors decompose quasi-cyclic codes as direct sums of shorter linear codes over various extensions of F q (when gcd(m, q) = 1). This last work leads to an interesting trace representation of quasi-cyclic codes. In [START_REF] Cayrel | Quasi-cyclic codes as codes over rings of matrices[END_REF], the approach is more analogous to the cyclic case. The authors consider the factorization of X m -1 ∈ M ℓ (F q )[X] with reversible polynomials in order to construct ℓ-quasicyclic codes canceled by those polynomials and called Ω(P )-codes. This leads to the construction of self-dual codes and codes beating known bounds. But the factorization of univariate polynomials over a matrix ring remains difficult. In [START_REF] Chabot | Factorisation in M ℓ (F q )[X]. Construction of quasi-cyclic codes[END_REF] the author gives an improved method for particular cases of the latter factorization problem.

Prerequisites

Reed-Solomon codes over rings

We recall some basic definitions of Reed-Solomon codes over rings in this section. We let A be a ring with identity, we denote by A × the group of units of A and by Z(A) the center of A, the commutative subring of A consisting of all the elements of A which commutes with all the other elements of A. We denote by A[X] the ring of polynomials over A and by A[X] <k the polynomials over A of degree at most k -1.

Definition 1. Let f = d i=0 f i X i ∈ A[X]
be a polynomial with coefficients in A and a ∈ A. We call left evaluation of f at a the quantity

f (a) := d i=0 f i a i ∈ A
and right evaluation of f at a the quantity

(a)f := d i=0 a i f i ∈ A.
Remark 1. For f, g ∈ A[X] and a ∈ A, we obviously have f (a) = (a)f whenever a ∈ Z(A), (f + g)(a) = f (a) + g(a), (a)(f + g) = (a)f + (a)g. If a commutes with all the coefficients of g we also have (f g)(a) = f (a)g(a) and (a)(gf ) = (a)g(a)f . Definition 2. Let 0 < k ≤ n be two integers. Let (x 1 , . . . , x n ) and v = (v 1 , . . . , v n ) be two vectors of A n be such that x ix j ∈ A × and x i x j = x j x i for all i = j and v i ∈ A × for all i.

The left submodule of A n generated by the vectors

(f (x 1 ) • v 1 , . . . , f (x n ) • v n ) ∈ A n with f ∈ A[X] <k
is called a left generalized Reed-Solomon code (LGRS) over A with parameters [v, x, k] A or [n, k] if there is no confusion on x and v.

The right submodule of A n generated by the vectors

(v 1 • (x 1 )f, . . . , v n • (x n )f ) ∈ A n with f ∈ A[X] <k is called a right generalized Reed-Solomon code (RGRS) over A with parameters [v, x, k] A or [n, k]
if there is no confusion on x and v. The vector x is called the support of the code. If v = (1, . . . , 1), the codes constructed above are called left Reed-Solomon (LRS) and right Reed-Solomon (RRS) codes.

Definition 3. Let x = (x 1 , . . . , x n ) ∈ A n . We call the Hamming weight of x the number of nonzero coordinates.

w(x) := w(x 1 , . . . , x n ) = |{i : x i = 0}| .
Let y = (y 1 , . . . , y n ) ∈ A n . The Hamming distance between x and y is

d(x, y) = w(x -y) = |{i : x i = x j }| .
The minimum distance of any subset S ⊆ A n is defined as min {d(x, y) : x, y ∈ S and x = y} .

Proposition 1. A LGRS (resp. RGRS) code is a free left (resp. right) submodule of A n . A LGRS (resp. RGRS) code with parameters [n, k] has minimum distance nk + 1.

Proof. It suffices to see that the maps

A n -→ A n (a 1 , . . . , a n ) -→ (a 1 v 1 , . . . , a n v n ) (a 1 , . . . , a n ) -→ (v 1 a 1 , . . . , v n a n )
are respectively left and right isometric automorphisms of A n .

Quasi cyclic and quasi BCH codes

Quasi cyclic codes form an important family of codes defined as follow.

Definition 4. Let T : F n q → F n q to be the left cyclic shift defined by

T (c 1 , c 2 , . . . , c n ) = (c 2 , c 3 , . . . , c 1 ).
We call ℓ-quasi-cyclic code over F q of length n any code of length n over F q stable by T ℓ . If the context is clear we will simply say ℓ-quasi-cyclic code.

We will focus in this paper on quasi-BCH codes which form a subfamily of quasi-cyclic codes. They can be seen as a generalization of BCH codes in the context of quasi-cyclic codes. For we need primitive roots of unity defined in a extension of F q , say F q s to construct BCH codes over F q .

Proposition 2. Then there exists a primitive q sℓ -1-th root of unity in M ℓ (F q s ).

Proof. The proof can be found in [BCQ12b, Proposition 16, page 911].

Definition 5. Let Γ be a primitive m-th root of unity in M ℓ (F q s ) and δ ≤ m. We define the ℓ-quasi-BCH code of length mℓ, with respect to Γ, with designed minimum distance δ, over F q by

Q-BCH q (m, ℓ, δ, Γ) :=    (c 1 , . . . , c m ) ∈ (F ℓ q ) m : m-1 j=0 (Γ i ) j (c j+1 ) T = 0 for i = 1, . . . , δ -1    . Note that Q-BCH q (m, ℓ, δ, Γ) is a quasi-cyclic code.
Definition 6. The ℓ-block weight of (x 11 , . . . , x 1ℓ , . . . , x m1 , . . . , x mℓ ) ∈ F mℓ q is defined to be Block-w ℓ (x) := |{i : (x i1 , . . . , x iℓ ) = 0}| .

The ℓ-block distance between x, y ∈ F mℓ q is defined to be Block-w ℓ (xy).

3 Reed-Solomon codes and quasi-BCH codes

The relation between quasi-BCH and Reed-Solomon codes

We show in this section that under certain assumptions on the support of Reed-Solomon codes, the dual of a LRS code is a RRS code. From this fact we show that quasi-BCH can be constructed from Reed-Solomon codes over square matrices rings. In this Subsection we let A designate a finite ring with identity.

Definition 7. Let x = (x 1 , . . . , x n ) and y = (y 1 , . . . , y n ) be two vectors of A n . The inner product is defined as

x, y := n i=0
x i y i .

Remark 2. Let S be a subset of A n . Then the set {x ∈ A n : ∀s ∈ S, s, x = 0} denoted by S ⊥ is called the right dual of S and is a right submodule of A n . Similarly, Let S be a subset of A n . Then the set {x ∈ A n : ∀s ∈ S, x, s = 0} denoted by ⊥ S is called the left dual of S and is a left submodule of A n . Note that for all x, y ∈ A n and µ ∈ A we have µ x, y = µx, y and x, y µ = x, yµ . First note that L is generated by the vectors

Definition 8. We say that a ∈ A is a primitive m-th root of unity if a m = 1 and ∀0 ≤ i < m, (a i -1) ∈ A × . Remark 3. Let x = (1, γ, γ 2 , . . . , γ m-1 ) ∈ A m
(1, γ i , γ 2i , . . . , γ (m-1)i ) for i = 1, . . . , k and that R is generated by the vectors

(1, γ i , γ 2i , . . . , γ (m-1)i ) for i = 0, . . . , nk -1.

And we have for 0

≤ i + j < n -1 in the commutative ring Z(A)[γ] m-1 i=0 γ (i+1)ℓ • γ jℓ = m-1 i=0 γ i+j+1 ℓ = 1 -γ i+j+1 m 1 -γ i+j+1 = 0.
Therefore, by Proposition 1 and Remark 2, L ⊥ ⊆ R and ⊥ R ⊆ L.

Again by Proposition 1 and Remark 2 an element x ∈ A n lies in L ⊥ if and only if

          1 1 1 . . . 1 1 γ γ 2 . . . γ m-1 1 . . . . . . . . . 1 γ k-1 γ 2(k-1) . . . γ (k-1)(m-1)           1 γ . . . γ m-1                x 1 x 2 . . . x n      = 0.
(1) But in the commutative ring Z(A)[γ] the matrix

H =      1 1 1 . . . 1 1 γ γ 2 . . . γ 2(k-1) 1 . . . . . . . . . 1 γ k-1 γ 2(k-1) . . . γ (k-1)(k-1)      ∈ M k×k (Z(A)[γ])
is invertible. Therefore H is also invertible in M k×k (A) and thus induces a group automorphism of A k . If we let x H = (x 1 , . . . , x k ), x U = (x k+1 , . . . , x n ), we can rewrite equation (1) as

H U x H x U = 0 and H 0 x H 0 = -0 U 0 x U .
For each choice of x U we have only one possible value for x H . Thus |L ⊥ | = |A| n-k = |R| by Proposition 1 and therefore L ⊥ = R. Similarly, we have ⊥ R = L.

Theorem 3. Let Γ ∈ M ℓ×ℓ (F q s ) be a primitive m-th root of unity and C = Q-BCH q (m, ℓ, δ, Γ). Then there exists a RRS code R over the ring M ℓ×ℓ (F q s ) with parameters [n, nδ + 1] M ℓ×ℓ (F q s ) and a F q -linear, F q -isometric embedding ψ : C → R.

Proof. A parity-check matrix of C is

H =      I ℓ Γ • • • Γ m-1 I ℓ Γ 2 • • • Γ 2(m-1) . . . . . . . . . I ℓ Γ δ-1 • • • Γ (δ-1)(m-1)      ∈ M (δ-1)ℓ,mℓ (F q s ).
Remark that H is a generator matrix of the LGRS code with parameters [x, x, δ -1] M ℓ×ℓ (F q s ) over the ring M ℓ×ℓ (F q s ) and by Proposition 3 its dual is the RRS with parameters [x, δ -1] M ℓ×ℓ (F q s ) . Now let Obviously, ψ is F q -linear, injective and isometric and by the above remark we have ψ(C) ⊆ R.

ψ : C -→ (M ℓ×ℓ (F q s ))
Theorem 3 generalizes the well-known [MS86, Theorem 2, page 300] relation between BCH codes and Reed-Solomon codes. The above relation will allow us to adapt the unique decoding algorithm from [START_REF] Barbier | On Generalized Reed-Solomon Codes Over Commutative and Noncommutative Rings[END_REF] to quasi-BCH codes.

The Welch-Berlekamp algorithm for quasi-BCH codes

In this Subsection we let A designate a finite ring with identity. Before giving the Welch-Berlekamp decoding algorithm, we need to define what the evaluation of a bivariate polynomial over

A is. Let Q = Q i,j X i Y j ∈ A[X, Y ] be such a polynomial. We define the evaluation of Q at (a, b) ∈ A 2 to be (a, b)Q = a i b j Q i,j ∈ A.
Be careful of the order of a, b and Q i,j . This choice will be explained in the proof of Lemma 1. Let f ∈ A[X], we define the evaluation of

Q at f to be (X, f (X))Q = X j (f (X)) j Q i,j ∈ A[X].
As in the univariate case, the evaluation maps defined above are not ring homomorphisms in general.

Lemma 1. Let g ∈ A[X], Q ∈ A[X, Y ] of degree at most 1 in Y and a ∈ A. Then (a)((X, g(X))Q) = (a, (a)g)Q.
Proof. We write

Q(X, Y ) = Q 0 (X) + Q 1 (X)Y = Q 0 (X) + i Q 1i X i Y.
The proof is an easy calculation: Algorithm 1 Welch-Berlekamp for quasi-BCH codes Input: a received vector y ∈ F mℓ q with at most τ errors. Output: the unique codeword within distance τ of y.

(a)((X, g(X))Q) = (a) Q 0 (X) + i X i g(X)Q 1i = (a)Q 0 + i a i (a)gQ 1i = (a, (a)g)Q by definition. We let C = Q-BCH q (m, ℓ, δ, Γ), τ = δ-1 2 , n = m, k = n -δ + 1 and pr : (M ℓ×ℓ (F q s )) m -→ F mℓ q      
1: (Z 1 , . . . , Z m ) ← ψ(y) where ψ is the map from Theorem 3.

2: Find Q = Q 0 (X) + Q 1 (X)Y ∈ (M ℓ×ℓ (F q s )[X])[Y ] of degree 1 such that 1. (Γ i-1 , Z i )Q = 0 for all i = 1, . . . , m -1, 2. deg Q 0 ≤ n -τ -1, 3. deg Q 1 ≤ n -τ -1 -(k -1). 3: f ← the unique root of Q in (M ℓ×ℓ (F q s ))[X] <k such that d (Z 1 , . . . , Z m ), ((I ℓ )f, . . . , (Γ m-1 )f ) ≤ τ . 4: return pr (I ℓ )f, (Γ)f, . . . , (Γ m-1 )f .
Lemma 2. Let y ∈ F mℓ q be a received word containing at most τ errors. Then there exists a nonzero bivariate polynomial

Q = Q 0 + Q 1 Y ∈ (M ℓ×ℓ (F q s ))[X, Y ] satisfying 1. (Γ i-1 , Z i )Q = 0 for i = 1, . . . , n. 2. deg Q 0 ≤ n -τ -1. 3. deg Q 1 ≤ n -τ -1 -(k -1).
Proof. We solve the problem with linear algebra over F q s . We have, for each column of the solution, nℓ equations and ℓ [(nτ ) + (nτ -(k -1))] = ℓ(n + 1) unknowns by Proposition 1. Proof. This is a direct consequence of Lemmas 2 and 3.

Lemma 3. Let Q ∈ (M ℓ×ℓ (F q s ))[X, Y ] satisfying the three con- ditions of Lemma 2 and f ∈ (M ℓ×ℓ (F q s ))[X] <k be such that d((Z 1 , . . . , Z m ), ((I ℓ )f, . . . , (Γ m-1 )f )) ≤ τ . Then (X, f (X))Q = 0. Proof. The polynomial (X, f (X))Q has degree at most n -τ -1. By Lemma 1 we have (Γ i-1 )((X, f (X))Q) = (Γ i-1 , (Γ i-1 )f )Q = (Γ i-1 , Z i )Q = 0 for at least n -τ values of i ∈ {1, . . . , n}. And therefore we must have (X, f (X))Q = 0.

Quasi-BCH codes as interleaved codes

In this Section we prove that quasi BCH codes can be viewed as an interleaving of classical BCH codes. We fix for this Section Γ ∈ M ℓ×ℓ (F q s ) a primitive mth root of unity and C = Q-BCH q (m, ℓ, δ, Γ). We first recall the definition of interleaved codes.

Definition 9. Let C 1 , . . . , C ℓ be error correcting codes over F q . The interleaved code C with respect to C 1 , . . . , C ℓ is a subset of M ℓ×m (F q ), equipped with the ℓ-bloc distance with respect to the columns, such that c ∈ C if and only if the i-th row of c is a codeword of C i for i = 1, . . . , ℓ.

Lemma 4. The matrix Γ diagonalizes over an extension of F q s and its eigenvalues are all primitive m-th roots of unity.

Proof. Let F q s ′ ⊇ F q s be the splitting field of X m -1. The polynomial X m -1 is a multiple of the minimal polynomial µ(X) of Γ. Hence the egeinvalues of Γ are m-roots of unity. Let P ∈ GL ℓ (F q s ′ ) be such that P -1 ΓP is diagonal. Now if an eigenvalue λ i of Γ has order d < m, then

P -1 (Γ d -I ℓ )P =         λ d 1 . . . λ d i . . . λ d ℓ         -I ℓ
is singular as its i-th diagonal element would be zero. Consequently Γ d -I ℓ ∈ GL ℓ (F q s ′ ) which is absurd.

Theorem 4. The quasi-BCH code C over F q is an interleaved code of ℓ subcodes of Reed-Solomon codes over F q s ′ in the following sense: there exists ℓ Reed-Solomon codes C 1 , . . . , C ℓ over F q and an isometric isomorphism from C, equipped with the ℓ-block distance, to a subcode of the interleaved code with respect to C 1 , . . . , C ℓ .

Proof. We take the notation of the proof of Lemma 4. Recall that

H =      I ℓ Γ • • • Γ m-1 I ℓ Γ 2 • • • Γ 2(m-1) . . . . . . . . . I ℓ Γ δ-1 • • • Γ (δ-1)(m-1)      ∈ M (δ-1)ℓ,mℓ (F q s )
is a parity check matrix for C (proof of Theorem 3). By Lemma 4 we have that (c 11 , . . . , c 1ℓ , . . . , c m1 , . . . , c mℓ ) ∈ C ⇐⇒    P -1 . . . Then it is straightforward that σ is an isometric isomorphism from C equipped with the ℓ-block distance and σ(C), which is by equation (3) a subcode of the interleaved code with respect to ℓ subcodes of Reed-Solomon codes over F q . For i = 1, . . . , ℓ take C i to be the Reed-Solomon code defined by the parity check matrix of equation (3).

P -1         I ℓ Γ • • • Γ m-1 I ℓ Γ 2 • • • Γ 2(m-1) . . . . . . . . . I ℓ Γ δ-1 • • • Γ (δ-1)(m-1)         P . . . P    ×                 P -1 . . . P -1                 c 11 . . . c 1ℓ . . . c m1 . . . c mℓ                           = 0 and (c 11 , . . . , c 1ℓ , . . . , c m1 , . . . , c mℓ ) ∈ F mℓ q Let              v 11 . . . v 1ℓ . . . v m1 . . . v mℓ              =    P -1 . . . P -1                 c 11 . . . c 1ℓ . . . c m1 . . . c mℓ              (2)
Note that if the minimal polynomial of Γ has degree one: Γ = Xλ, then s ′ = s and Γ diagonalizes as λI ℓ . Consequently the Reed-Solomon codes C 1 , . . . , C ℓ are isomorphic, as they are defined by the same control equations in equation (3). In such a case, we can apply the result on the correction capacity for interleaved Reed-Solomon codes [START_REF] Schmidt | Error and Erasure Correction of Interleaved ReedSolomon Codes[END_REF][START_REF] Bleichenbacher | Decoding interleaved Reed-Solomon codes over noisy channels[END_REF].

Corollary 1. There exists a decoding algorithm that is guaranteed to correct up to δ-1 2 errors. In particular, if the minimal polynomial of Γ has degree 1 over F q s then it can correct up to ℓ ℓ+1 (δ -1) errors with high probability. Proof. Taking the notation of Theorem 4 and if y = c + e is a received word, one can decode σ(y) with the decoding algorithms of C 1 , . . . , C ℓ obtaining c ′ ∈ F mℓ q s ′ . Then c = σ -1 (c ′ ).

If the minimal polynomial of Γ has degree 1, then C 1 = C 2 = • • • = C ℓ and one can apply the algorithm of [START_REF] Bleichenbacher | Decoding interleaved Reed-Solomon codes over noisy channels[END_REF] or [START_REF] Schmidt | Error and Erasure Correction of Interleaved ReedSolomon Codes[END_REF].

  where γ is a primitive m-th root of unity. Then a RRS or LRS code whose support is x is cyclic. Proposition 3. Let γ ∈ A be a primitive m-th root of unity. Let x = (1, γ, γ 2 , . . . , γ m-1 ) ∈ A n . Then the right (resp. left) dual of the LGRS (resp. RGRS) code with parameters [x, x, k] A is the RRS (resp. LRS) code with parameters [x, nk] A .Proof. We denote respectively by L and R the left generalized Reed-Solomon code with parameters [x, x, k] A and the right Reed-Solomon code with parameters [x, nk] A .

m

  (c 11 , . . . , c 1ℓ , . . . , c m1 , . . . , c mℓ )

  . . , a 1 ℓ1 , . . . , a m 11 , . . . , a m ℓ1 ).

Proposition 4 .

 4 Algorithm 1 works correctly as expected and can correct up to δ-1 2 errors.

Denote by σ

  the application defined by equation (2). Then (c 11 , . . . , c 1ℓ , . . . , c m1 , . . . , c mℓ ) ∈ C ⇐⇒ σ -1 (v 11 , . . . , v 1ℓ , . . . , v m1 , . . . , v mℓ ) ∈ F mℓ q and for i = 1, . . . , ℓ . . . . . . . . . . . . . . . . . . . . . . . .


Dominique Andolfatto
email: dominique.andolfatto@u-bourgogne.fr

Dominique Labbé Pacte
email: dominique.labbe@iep-grenoble.fr

The Future of the French Trade Unions

This article investigates the transformations of the French unionism and of the French system of industrial relations over the last years and their probable future. It shows: an evolution from a militant unionism to a professionalized trade unionist system; the decline of collective actions; the increase of negotiation, especially at plant level; the dependence of unionists on their employers for their funding, their resources and their careers. This evolution marks a shift towards a new system which is very different from a "unionist Latin model" depicted in traditional literature on French unionism.

Résumé

Cet article analyse les transformations des syndicats français et, plus généralement, du système français de négociation professionnelle durant les dernières années, et leur futur probable. Il montre : la transformation d'organisations fondées sur le militantisme syndical en un système professionnalisé ; le déclin de l'action collective ; l'augmentation de la négociation, spécialement au niveau des entreprises ; la dépendance des syndicalistes envers les employeurs pour leur financement, leurs moyens et leurs carrières. Cette évolution aboutit à un nouveau système très éloigné du modèle du syndicalisme latin décrit dans les travaux sur le syndicalisme français.

Introduction

In the late 1990s, H. Slomp classified French trade unionism as being an example of the "Latin model" (Slomp, 1998, 35-36). According to him, similar to Italian unions, French unions valued the initiative and input of their members and activists. Organizations felt that their role was to support the spontaneous actions of their members and to develop this action within the context of larger protests against the State and not only against the employers.

Finally, H. Slomp emphasized that French trade-unionism was deeply politicized, but did not have the functional division of powers between parties and unions typical of the socialdemocratic model predominant in northern Europe (see also [START_REF] Jefferys | Liberté, Egalité and Fraternité at Work. Changing French Employment Relations and Management[END_REF]).

It will be seen that, at the time when H. Slomp was writing his book, the "Latin model" of unionism was disappearing in France. In less than thirty years, activists and supporters have been replaced by professional representatives who control cartels of non grass-root unions. In fact, these professionals do not seek to drum up membership or encourage social mobilization.

They spend most of their time negotiating with employers. This negotiation has devolved from the national level to that of the plants and the firms. Most of these professional unionists continue to be salaried by their employers with whom they negotiate on behalf of employees.

Indeed, these 'institutionalized' unions are not funded by their decreasing membership but are heavily subsidized by the State, local authorities and employers. This article will examine these new dynamics: how activists have been replaced by professionals; the decline of social mobilization and the advent of social bargaining on the plant level; the potential scope of this negotiation; the funding of unions by employers and the state. This new system is very similar to cartel parties [START_REF] Katz | Changing models of Party Organizations and Party Democracy, the Emergence of the Cartel Party[END_REF], and has a future which is not fully assured. Between 1958 and1978, more than a quarter of French workers were unionized. Between 1967 and 1977 there was even an increase where nearly three out of ten employees were unionized (Fig 1). These figures do not come from data provided by these organizations, but were observed in trade union archives or were calculated from the results of work council elections (comités d'entreprise) [START_REF] Labbé | Syndicats et syndiqués en France[END_REF]Andolfatto &[START_REF] Andolfatto | Les syndiqués en France[END_REF]. During these years of rapid economic growth, the French workforce increased from 13 to 18 million and was profoundly transformed and rejuvenated. The maintaining of the rate of unionization at the same level indicates that there was a significant increase in membership. In other words, during the trente glorieuses, the French trade unions adapted themselves to changes occurring in the labor market: the arrival of the baby boom generation, feminization of the workforce, the rise of the service sectors and of the white collars.

From militant unionism to professionalized trade unionists

During this period, the rate of unionization in France was lower than in Germany, in Scandinavian countries and in Belgium, but it was comparable to that of North America and Italy, at least until the early 1970s. Consequently, contrary to what is usually said, the present low level of unionization is not a French inevitability.

Why so many members?

Until the late 1970s, the major activity of French trade union activists was to provide individual assistance to their members to protect them against dismissal, sanctions, arbitrary transfers, bullying. These activists had to resolve many problems of everyday life at work: poor working conditions, dangerous equipment, unsociable hours, refusal to give holidays, unpaid premiums, etc. This assistance could extend beyond the workplace to include help with housing problems, procedures with social security funds... This function of "legal defense and formulation of demands" has become unpopular among political activists because it was time consuming, but it was nevertheless accepted by the militants because it allowed to collect union dues and to gain members, sympathizers and voters. This activity was the source of a kind of informal law regulating daily life in the workplace in a much more flexible and efficient way than the labor code or the industrial agreements. Finally, it was associated with a working-class culture which facilitated the integration of young workers and uprooted rural migrants [START_REF] Andolfatto | Histoire des syndicats 1906-2010[END_REF].

In 1975, the number of unionized workers was about 4.5 million, that is to say a union density (rate of unionization) of nearly 25 %. Not only were these members (in the flesh) a physical reality but they were loyal to their organization -their average seniority was over 10 yearsand a significant minority were prepared to bring, in addition to its membership fees, a voluntary contribution to some of their unions' activities. At that time, much of the life of trade unions relied on volunteer activists who gave dynamism and efficiency to these teams.

De-unionization

Between 1978 and 1988, the rate of unionization was halved, which means that very many members left their unions while recruitment dried up. Subsequently in the 1990s and 2000s, this decline continued without interruption, but at a slower pace. Despite repeated assertions, this decline has not yet been halted.

In 2003, membership was only 1.7 to 1.9 million, that is to say around 7 % of the total workforce of 23.5 million French workers [START_REF] Thomas | La transformation du paysage syndical depuis 1945[END_REF][START_REF] Andolfatto | Sociologie des syndicats[END_REF]. This is the lowest rate of all the OECD countries (alongside with Turkey) [START_REF] Visser | Database on Institutional Characteristics of Trade Unions, Wage Setting, State Intervention and Social Pacts in 34 countries between 1960 and 2010[END_REF]). These members were shared among seven "main" organizations (Table 1). These aggregate statistics need to be qualified by a number of remarks.

-Approximately 13 % of union members are retirees.

-Some dues are not paid by the members but they come from funds provided by some companies (Andolfatto & Labbé 2007, 131-176, 178-179). For the CGT, about one stamp out of five, sold by the confederal treasury, is paid with the help of this funding. The main unions The UNSA derives most of its resources from public services and from the main public companies.

-The two thirds of union members work in the public sector and in public companies. In the private sector, less than one employee out of 20 is unionized.

-A large proportion of the remaining members devote a large part of their working time to unionism. In most firms where a union exists, the only members are elected representatives (délégués) or union officials (mandatés).

Since 1978, the decline continued more or less at the same pace and the curve seems to have been insensitive to changes occurred in the economic and social situation of the country and to those occurred in the political majorities. Therefore, the main reasons for this decline cannot lie in the French economic, social or political situations. They must be sought for in the French unionism itself, especially in the changes in its organization (and militancy) which are described in this paper.

The rise of professional unionists

The representatives have become union professionals through the accumulation of mandates and functions. But their wages are still paid by their employers. Many French sociologists refer to this as an "institutionalization" of the unions, suggesting that, through their legal recognition in the workplace, unions are no longer simple associations but institutions.

However, as early as 1983, G. Adam (1983aAdam ( , 1983b) ) predicted that laws, adopted since 1968 in order to support unions, would profoundly change the nature of these unions in three ways.

Firstly, G. Adam announced that an elite of professionals would seize the control of unions;

secondly he conjectured that the voters would replace the members as a source of legitimacy and, thirdly, that the disappearance of union dues would be offset by public subsidies and funding by firms. Several surveys have clearly ascertained the reality of these three changes (for example: [START_REF] Croisat | La fin des syndicats ? Paris: L'Harmattan[END_REF][START_REF] Nezosi | La fin de l'homme du fer[END_REF][START_REF] Andolfatto | Les syndiqués en France[END_REF].

In fact, at the local level, unions are not operating as institutions. On the contrary, the general board and the statutory bodies no longer meet, even in large public companies (traditional union strongholds). The organizations are controlled by a few leaders who, through the accumulation of elected offices and responsibilities, have 'privatized' the collective benefits granted to the unions.

These union leaders are relatively old (average age between 45 and 55 years -according to the organizations). Many will retire in the near future. This raises the question of the very future of unionism [START_REF] Andolfatto | L'engagement syndical des jeunes postiers : déclin ou mutation ?[END_REF]. The firm managements appear to be very concerned about this future which is also threatened by the rise of abstention. But the unions' leaders continue to favor selective recruitment. More generally, despite some public declarations to the contrary, the recruitment of a large number of new members rarely appears as an objective.

In few firms, SUD -an extreme left federation -tries to keep some militant practices. But its teams are few and they are mainly present in the public sector.

The professionalization of unionism is also reflected in a weakening of the capacity for collective action.

The decline in participation and collective action

The decline in participation in plant floor elections (élections professionnelles) and the decreasing number of strikes are the most obvious signs of this weakening.

The decline in participation

The continuous rise in abstention is particularly significant, given the fact that, without members, the legitimacy of unions is legally based on the votes they obtain, especially in work council elections [START_REF] Bevort | Représentativité[END_REF]. This number justifies their participation in collective In other words, the declining level of participation suggests that trade unionists are less and less able to induce employees to vote, even if the number of voters in some plants remains consistent and sometimes important. Accordingly, there will soon be one half of employeeswhen it is not already the case -who no longer identify with 'their' union representatives.

The decline of the strikes

The decline in the number of strikes is another indication of the weakening of the union's ability to mobilize workers.

The image of France has always been one of a country that often goes on strike. In fact, conflicts in the private sector, have declined sharply since the 1970s. [START_REF] Eschtruth | La France, pays de grèves ? Etude comparative internationale sur la longue durée[END_REF] gives an overall view of this period.

In 2009, 2.2 % of companies -with 10 or more employees -experienced a strike, including stoppages of a few hours (débrayages). But this percentage increased in 2010 (3,3 %) due to pension reform (that caused two-thirds of the conflicts). Putting aside the protest against this reform, the number of companies experiencing a strike is a lower than in 2009 [START_REF] Desage | Négociation collective et grève dans les entreprises du secteur marchand en 2010[END_REF]. But the most interesting indicator is the number of workdays per 1,000 employees lost through strikes (table 2). To make the data intelligible, they are converted to the probability, for an employee, of going on a one-day strike during his life at work (last column). On average, during the years 2008-2009, an industrial French worker goes on a one-day strike once every six years; in the building sector, this average was 61 years, etc. The most frequent strikers are transportation workers (a day of strike every two years), especially in the railway and underground sectors; on the other side of the spectrum, the most infrequent strikers are in the building and the retail sectors.

Half of all French employees work in the retail and service sectors (excluding transportation).

During 2008-2009, they went on a one-day strike an average of every 38 years, that is to say once in their working live. For all the merchant sectors (including industry and transportation, private and public firms), the average probability of a one-day strike occurs every nine years (unchanged from 2006 and 2007). In 2010, due to the protests in some firms against pension reform, the figures increased but this does not fundamentally change the trend.

In the three public services (government services, health care, and local services), the average is about a one-day strike every 5 years (this figure is more or less stable since 2005). The statistical series is too recent to allow long-term comparisons.

Despite these figures, France has a reputation of being a striker's paradise. This perception comes from the great waves of strikes in the past : 1920, 1936, 1947, 1968, 1995. It also stems from the memory of a protest decade (from the late 1960s to the 1970s) and from the continuation of large-scale conflicts in public transportation (though decreasing in the recent past).

high number of meetings and many topics of discussion". In fact, over the past twenty years, Table 3 (first line) shows that the number of contracts all sectors, at the national level, has remained stable contrary to the branch contracts, at national and regional levels , the number of which has been growing during the last decade (Table 3, second line).

At the national and regional levels, branch bargaining concerns employees of some particular economic sectors (more than 700 branches exist excluding agriculture). At these levels, according to the same annual report, French workers apparently have the highest collective bargaining coverage in the world (with nearly 1,200 contracts in 2011: Table 3). It is estimated that 95 % of these employees would be covered by a national branch collective contract and /or by a regional one.

At the plant level, the overall figures of collective bargaining in the merchant sectors show a continuous increase in the number of firms and employees concerned. Over the past twenty years, the number of plant-level agreements has been multiplied by 17 (Table 3).

According to the last survey for the year 2009 (a representative sample of plants in the merchant sectors employing at least 10 employees: Bobbio, 2011), negotiations took place in 60 % of the plants with 50 or more employees and those negotiations involved 64 % of the 17,5 million workers employed in the merchant sectors. Because of a continuing extension of the contract terms, in all other developed countries, this rate appears to be unique in the world.

These surveys also show the growing nature and extent of the themes and scope of these texts : working hours, individualization of remunerations, career flexibility, employee savings, supplemental health insurances... (Table 3).

For a long time, these plant level agreements could obtain derogations from the law and from national conventions -especially about the working hours -that is to say applying less favorable rules.

It can be observed that the annual report pays little attention to the details of these agreements.

The fact remains that the wages and the working hours of a large part of the employees in the merchant sectors now depend at least as much as on a collective agreement as on the laws and on jurisprudence. It is highly likely that this trend will continue in the coming years, giving more importance to the unionists who negotiate with the employers -although they are also salaried and funded by them. This is a silent revolution that has occurred in recent years. France is moving quickly away from the continental model in which the main topics are decided in national negotiationsoften tripartite (Unions, Employers and government) -enclosed within a more or less detailed legal framework. France is moving quickly toward the British system centered on firms and on plants. This flexible system allows employers to adjust the salaries and working conditions to the economic situation and to the needs of their businesses, subject to one condition: they must obtain at least one union endorsement.

In the coming years it is likely that collective bargaining at national and branch levels will become obsolete, although this evolution is very different from the centralist French traditions.

However, few are aware of this silent revolution because the exact content of these "derogatory" agreements is rarely examined as is the manner in which these plant negotiations proceed.

An unbalanced negotiation

Reports also indicate that in 90 % of the firms which open negotiations, an agreement is reached and union representatives sign between 91 % (CFDT) and 83 % (CGT) of these texts.

Although meetings are held behind closed doors, several eyewitnesses exist. For example, consider the description given of the discussions during 2008 -between the organizations of employers and the trade unions -that led to the agreement that changed the legal framework of trade union actions (Andolfatto & Labbé, 2009, 177-179). The meetings were hosted by the organizations of employers who set the agenda and calendar, held the secretariat, drafted the preparatory texts and drew up the final version. The same situation occurs at any level -from the plant level to national global negotiations.

At plant level, the number of agreements signed can be correlated with some elements mentioned above. These elements include: the low level of collective mobilizations, the professionalization of the unionists, and some special clauses in these agreements which are devoted to the funds and means granted to the unions by the employers (second to last line of Table 3 above). In the current economic crisis, one must also consider the use of blackmail in some companies.

In 2008, a study of the Ministry of Labor revealed a paradoxical situation: despite fewer and fewer members, French unions are present in an increasing number of plants and firms [START_REF] Wolff | Le paradoxe du syndicalisme français : un faible nombre d'adhérents, mais des syndicats bien implantés[END_REF]. The asymmetry of the industrial relations may explain this apparent paradox of the French trade unionism with less and less members but which constantly expands. Indeed, at plant level, the employer provides the union office and all the necessary means for day-today functioning. Many companies add a large endowment.

Institutional funding

Trade unions have received a lot of financial resources and above all many supports in-kind [START_REF] Adam | Des comptes enfin publics[END_REF][START_REF] Andolfatto | Le financement des syndicats : la part des cotisations[END_REF][START_REF] Perruchot | Rapport sur les mécanismes de financement des organisations syndicales d'employeurs et de salariés[END_REF].

Regarding the former, members' contributions cover a further 10 to 20 % of expenditure (depending on different organizations and levels). But, as noted above, a significant proportion of these contributions come from funding that companies pay to their unions.

Some of this funding is surrendered to the federations and confederations as if it had been provided by members.

Some firms report the details of sums they pay to their unions. For example every year, the insurance company AXA gives its employees a cheque of fifty euros to be allotted to the union of their choice. Air France, Casino, EADS, France Telecom, Groupama, LCL, Renault, Safran, Thales... make direct payments to their unions. Several federations, including metallurgy, are directly funded by their employer interlocutors.

The funds levied from the work councils, from the social security agencies and the government grants make up the rest of the union financial resources. For example, for confederations, the levies from the lifelong learning organizations exceeded the total amount of member's contributions. However, this funding is not fully reflected in the official accounts, but in unpublished records of some subsidiaries such as union training organizations.

A government enquiry in 2010 gives an estimate of the level of support from the public purse [START_REF] Desforges | Rapport sur le bilan des moyens alloués aux organisations syndicales dans la fonction publique[END_REF]. In national and local public services, the annual cost of the release time (paying for releasing unionists from their professional duties) and of aids for trade unions represent about 250 euros per employee. The authors indicate that this is minimal given the lack of information found for some services (education, police, customs ...) and the very patchy information on others. If we accept these quantitative indications and extrapolate them for the entire public services, this would represent a total of 1.319 billion euros allocated to the various unions. This means that -for the Civil Service alone -it would be far more than any previous estimate (around one billion euros for all sectors, merchant and non-merchant).

Secondly, resources in-kind consist primarily in facilities and staff made available to the unions. These people spend all or part of their time working for the union while continuing to be paid by their employers and pursuing their own careers. For the Civil Service as a whole, the report mentioned above makes it possible to estimate that the total number of people mis à disposition for the unions, is between 13,200 and 15,240 employees.

When one includes in these statistics engineering grandes écoles, public research institutions, the Bank of France, central government and the large national companies (public transportation, energy and the various social security organizations) the equivalence of at least 30,000 full time jobs are made available, free of charge, to French trade unions by employers.

Conclusions

Superficially, one might consider that de-unionization in France seems to be in line with a global trend [START_REF] Visser | Database on Institutional Characteristics of Trade Unions, Wage Setting, State Intervention and Social Pacts in 34 countries between 1960 and 2010[END_REF][START_REF] Hayter | Review Essay: Collective Bargaining for the 21st Century[END_REF], but, apart from its exceptional magnitude, it presents many specific characteristics that are summarized in conclusion.

The main resources of the French unions come from private and public employers. This dependency of unionists on employers may be the principal cause of the impotence of unions and of the imbalance inherent in French industrial relations. Weakness of unions, as well as their institutionalization can also explain that French workers are increasingly likely to express their suspicion of unions, especially in public opinion surveys, and to abstain in elections held in the workplaces. This situation may also be related to the development of strikes or protest movements outside union initiatives or union control (Basilien & al., 2010, 18).

The situation of French trade unionism illustrates the side effects of some public policies.

After 1968, all French governments and many directors of large companies attempted to strengthen trade unionism because they considered this force to be a key player in social dialogue and a major asset for the modernization of business and of government. The numerous rights, protection, subsidies of all kinds that have been granted to the unions were designed as a public good that would benefit all employees, within the scope of these measures. But these rights, these forms of protection, these funds have been privatized by a few tens of thousands union managers -who have few links -except during electoral campaigns -with the workers they represent.

French unions and parties have evolved in relatively parallel ways. The theory of a "cartel party" [START_REF] Katz | Changing models of Party Organizations and Party Democracy, the Emergence of the Cartel Party[END_REF]& 2009) explains many of their transformations: loss of membership, development of stand-alone apparatuses removed from their former social bases, strong interconnections within organizations and institutions of all types -that provide unions with increasing resources, and which give them independence, disconnection even, from the workers -sharing the resources, reducing the competition between unions and preventing the emergence of new competitors.

Will this spiral continue? For the moment, it seems inevitable. But the history of French unionism is punctuated with sudden periods of revolt that open the door to unforeseeable developments. For example, in 1968, who could have predicted that the biggest strike movement in modern history would lead to the current situation as summarized in this paper?

Aknowledgments

We thank Edward Arnold (Centre for European Studies, Trinity College, Dublin), for his valuable comments and for his careful reading of a previous version of this paper, and the anonymous reviewer who made us many helpful remarks.

Fig. 1

 1 Fig. 1 Evolution of unionization in France since 1949 (all organizations combined)

  involved are : Postal and Telecom services, Railways, Energy, Press and Broadcasting, Chemicals and Metal industries, Civil servants, Security and Cleaning companies... In the CFDT, almost one fee out of four comes from the following federations: Postal and Telecom services, Retailing, Health and care services, Railways, Agribusiness, Building, Local government, Energy, Metallurgy and Mechanics, Press and Broadcasting. In these sectors, the same large companies also fund other trade union confederations (FO, CFTC and CFE-CGC).

  bargaining and in the management of the Welfare State. And this participation generates the greatest proportion of their resources (see discussion below).The number of voters has collapsed in the prud'homales (election of judges for individual labor disputes): 25.6 % of voters in 2008, against 63.1% in 1979, despite the fact that these elections were organized to reestablish the legitimacy of unions... The next election -to be held in 2013 -has been postponed to 2015 to allow the government to change the system (and it may abandon these elections).Unlike prud'homales, work council elections (comités d'entreprise) are held in the workplace and during working hours, thus allowing the employee to leave his post for a few minutes.Moreover, as the lists of voters are not secret, some employees fear being frowned upon if they do not exercise their vote... However, all the available statistics indicate a continuous growth in abstention. For the comités d'entreprise, the most recent results(2005)(2006), before the removal of this statistic, indicate an average abstention level of 40 % as opposed to 20 % in the 1960s. For the joint committees of the Civil Service, abstention was only12-13 % in 1950-1960 and it now exceeds 30 %, to which more than 5 % of blank and spoiled ballots needs to be added. The teachers -who were the most civically responsible during the 1970sare now the most prone to abstention. In hospitals, the decline is even more pronounced: only 40 % of nurses employed by the Hôpitaux de Paris go to the polls today.

Table 1 . Number of members in French trade unions in the early twenty-first century

 1

	Memberships

Table 2 . Strikes in the French merchant sectors in 2008-2009

 2

	Sector	Working days lost in strikes	Probability for a worker to
		(per 1 000 workers)	go on a one day strike
	Industry	168	6 years
	Building	17	61 years
	Commerce	20	50 years
	Transportation	492	2 years
	Services	60	17 years
	All sectors	117	9 years
	Sources : Ministry of Labour & our calculus (last column).

The French social situation is paradoxical: the fewer the members, the more trade union representatives there seems to be; while the union apparatuses have significantly grown, the amount of collected fees has shrunk and collective mobilization declined while negotiating increased.

Increase in the negotiation

In most major industrial countries, collective bargaining has developed considerably in the late twentieth century and early twenty-first, even though unionism has been stagnating or declining [START_REF] Hayter | Review Essay: Collective Bargaining for the 21st Century[END_REF]. But in France, these two movements have experienced a considerable change (Cézard & Dayan,1999 ;Andolfatto, 2007).

The growing scope of the French collective bargaining

Collective bargaining in the merchant sectors (involving 17.5 million employees) takes place at two different levels (Table 3). According to the annual report published by the Ministry of Labor, "The dynamism of negotiations, observed since 2008, has grown in 2011 with a new increase in the number of texts recorded" (Ministère du travail, 2012).


CONTENTS

Ce rapport est une introduction au manuscrit de thèse intitulé "High Performance by Exploiting Information Locality through Reverse Computing". Il aborde le contexte et les principales problématiques de recherche auxquelles nous nous sommes intéressées. Il donne un aperçu des solutions proposées, puis présente l'organisation du manuscrit de thèse. Le manuscrit a eté rédigé en anglais et peut être consulté à la bibliothèque de l'université Paris-Sud XI.

Abstract

Les trois principales ressources du calcul sont le temps, l'espace et l'énergie, les minimiser constitue un des défis les plus importants de la recherche de la performance des processeurs. Cependant, la minimisation de l'une de ces ressources à tout prix nécessite une quantité disproportionnée des autres ressources. L'usage de la mémoire peut être réduit au prix d'une exécution plus lente du programme, et le temps de calcul peut être réduit au prix d'une augmentation de la consommation d'énergie. C'est pourquoi trouver un compromis entre ces trois facteurs est devenu le défi de la théorie de calcul.

Dans cette thèse, nous nous intéressons à un quatrième facteur qui est l'information. L'information a un impact direct sur ces trois facteurs, et nous montrons comment elle contribue ainsi à l'optimisation des performances.

Landauer [START_REF] Landauer | Irreversibility and heat generation in the computing process[END_REF] a montré que c'est la destruction -logique -d'information qui coûte de l'énergie, ceci est un résultat fondamental de la thermodynamique en physique. Sous cette hypothése, un calcul ne consommant pas d'énergie est donc un calcul qui ne détruit pas d'information. On peut toujours retrouver les valeurs d'origine et intermédiaires à tout moment du calcul, le calcul est réversible.

L'information peut être portée non seulement par une donnée mais aussi par le processus et les données d'entrée qui la génèrent. Quand un calcul est réversible, on peut aussi retrouver une information au moyen de données déjà calculées et du calcul inverse. Donc, le calcul réversible améliore la localité de l'information. Par exemple, pour l'instruction c: = a + b, l'informations dans (a, b, c), (a, b), (a, c) ou (b, c) est la même, donc pas besoin de garder les trois valeurs en vie en même temps car nous pouvons toujours recalculer la troixième valeur à partir des deux autres. ′ a ′ peut être calculé à partir de (b, c) et ′ b ′ à partir de (a, c) par une simple soustraction. Donc les valeurs qui portent la même information peuvent partager le même registre. Par conséquent on dit que la localité de l'information peut optimiser l'espace de stockage.

Pour tirer profit de la localité de l'information, nous étudions la conservation de l'information au cours d'un processus irrversible. Un calcul conventionnel est à priori un calcul irréversible et ne conserve pas l'information. L'addition de deux nombres, par exemple, détruit l'information, sauf si nous conservons l'un de ces nombres. Cela nous a conduit à la question quelle est la taille minimal de l'information, que nous devons garder afin de générer toutes les valeurs d'entrée, d'intermédiaire et de sortie, sans avoir besoin d'un espace mémoire supplémentaire ?. Comme l'avantage du calcul réversible est sa capacité à conserver l'information, nous abordons la question de rendre un programme réversible en terme d'espace mémoire.

La réversibilité des programmes a été étudié par Bennett [START_REF] Bennett | Logical reversibility of a computation[END_REF]. Une première manière facile pour rendre un programme réversible est de sauvergarder l'historique de calculvariables intermédiaires -au long de l'exécution. Cependant le problème d'effacer -oublier -cette information, appelé déchet, demeure. Ce déchet peut être utilisé comme une estimation de la consommation d'énergie intrinsques des programmes et le minimiser est notre objectif. Bennett [START_REF] Bennett | Logical reversibility of a computation[END_REF] a prouvé que si la sortie peut être calculé à partir de l'entrée, alors il existe un moyen réversible pour calculer l'entrée à partir de la sortie tout en éliminant le déchets de calcul. Cela peut-être au prix d'un espace de stockage additionel pour stocker toutes les états intermédiaires au cours du calcul. C'est pourquoi nous nous intréssons à étudier la complexité spatiale des programmes réversibles.

L'optimisation des performances en exploitant la localité de l'information peuvent provenir en diminuant la pression en registre et par conséquent en réduisant le spill code. Dans ce travail, nous revisitons le problème d'allocation de registres sous l'angle de calcul réversible. Tout en étant un très vieux problème en informatique, l'allocation de registres est toujours un problème préoccupant en architecture où le fossé entre la vitesse des processeurs et celle de la mémoire continue de se creuser. Dans l'allocation de registres, on peut utiliser la rematérialisation au lieu de spilling, autrement dit, on recalcule une valeur v localement à partir des valeurs encore stockées dans les registres au lieu de la garder en vie en mémoire. Par conséquent, l'hiérarchie mémoire est peu solicitée. Le recalcul est effectué de la même manière comme il est spécifié dans le programme, mais il y a une partie de l'information sur v portée par d'autres valeurs w qui ont été calculées directement ou indirectement de v, ce qui donne de nouvelles opportunités pour régénerer la valeur v: en recalculant v à l'envers de w. Par conséquent, l'une des questions que nous abordons dans cette thèse est de savoir si la rematérialisation via le calcul inverserematérialisation inverse -peut aider à l'amélioration de l'allocation de registres.

Cette approche, recalcul versus stockage, conduit également à augmenter significativement le parallélisme d'instructions (Cell BE), et le parallélisme de threads sur un multicore avec mémoire et/ou banc de registres partagés (GPU), dans lequel le nombre de threads dépend de manière importante du nombre de registres utilisés par un thread. Ainsi, l'ajout d'instructions du fait du calcul inverse pour la rematrialisation de certaines variables est largement compensé par le gain en paralllisme. Nos exprimentations sur le code de Lattice QCD porté sur un GPU Nvidia montrent un gain de performances atteignant 11%. nous montrons que la rematérialisation via le calcul inverse est moins couteuse en terme d'opérations ajoutées que la rematérialisation classique (recalcul directe).

Contribution

Le but de cette thèse est double:

1. Tout d'abord, nous abordons la question de rendre un programme réversibles en termes de compléxité spatiale. La complexité spatiale est la taille mémoire / nombre de registres nécéssaire pour effectuer un calcul dans les deux sens direct et inverse. Nous donnons une borne infèrieure de la complexité spatiale d'un DAG de calcul (graphe dirigé acyclique ) avec oprations réversibles, ainsi qu'une heuristique visant à trouver le nombre minimum de registres requis pour une exécution directe et inverse d'un DAG. Nous définissons le déchet énergétique comme étant le nombre de regitres supplémentaires nécessaires ce calcul réversible. Nous avons effectué des expérimentations qui suggèrent que la taille du déchet n'est jamais plus de 50% de la taille du DAG pour un DAG avec des oprations unaires/binaires. Ce travail a été publié dans la conférence CASES'2009, International Conference on Compilers, Architecture, and Synthesis for Embedded Systems [START_REF] Bahi | Spatial complexity of reversibly computable dag[END_REF].

2. Deuxièmement, nous revisitons les problèmes d'allocation de registre de point de vue du calcul reversible et nous présentons une nouvelle technique de rematérialisation basée sur le recalcul inverse. Nous détaillons un algorithme heuristique pour effectuer la rematérialisation inverse et nous utilisons l'application LQCD (Lattice chromodynamique CONTENTS quantique) pour démontrer qu'un gain important pouvant aller jusqu' 33% sur la pression en registre peut être obtenu. Nous montrons aussi comment le parallélisme d'instructions et le paralllisme de threads peuvent être améliorés en effectuant une allocation de registres avec du recalcul inverse. L'application de ces optimisations sur les processeurs graphiques GPU permet d'augmenter le nombre de threads par Streaming Multiprocesor (SM). Cela s'est fait sur le kernel du programme de simulation de la Lattice chromodynamique quantique (LQCD) où nous avons gagné 11% de performance. Ces résultats ont été publiés dans deux conférences internationales: ACM International Conference on Computing Frontiers-CF'2011 [START_REF] Bahi | Rematerialization-based register allocation through reverse computing[END_REF] et l'International Symposium on Computer Architecture and High Performance Computing -SBAC-PAD'2011 [START_REF] Bahi | High performance by exploiting information locality through reverse computing[END_REF]. Ce travail a été choisi comme le Best Paper de la session Architecture, et a remporté le prix de Jùlio Salec Aude de la conference SBAC-PAD'2011.

Organisation du manuscrit de thèse

Après avoir présenté dans la section 1 le contexte, les problèmes de recherche auxquels nous nous sommes intéressés, et avoir présenté dans la section 2 nos contributions, nous présentons ici le plan de la thèse.

La partie 1 est consacré à expliquer en détail les concepts du calcul réversible et de la conservation de l'informations. Cette partie est composée des chapitres suivants: Chapitre 1 récapitule les travaux antrieurs relatifs à ces concepts et discute des différentes applications et approches du calcul réversible. Dans le chapitre 2, nous nous attaquons au problème d'inversement d'un programme et nous examinons le coût mémoire de la réversibilité.

La partie 2 de cette thèse décrit les diffrentes approches pour améliorer les performances des programmes en exploitant la localité de l'informations via le calcul inverse. Cette partie est organisée comme suit: Dans le chapitre 3, nous discutons les travaux antérieurs sur les techniques de l'allocation de registres liés à notre travail, dans l'objectif de réduire la pression en registre, . Dans le chapitre 4, nous présentons une nouvelle technique de rematérialisation basée basée sur le calcul inverse pour résoudre le problème d'accès à la mémoire. Les chapitres 5 et 6 adressent les problématiques du parallélisme d'instructions et de threads sur processeurs multi-coeur et montrent comment la rematerialisation inverse peut les améliorer en augmentant la disponibilité des ressources, typiquement les registres. Nous présentons ensuite les résultats de nos expérimentations sur Cell BE et NVIDIA GPU. Enfin, le chapitre 7 contient la conclusion de ce travail et propose des orientations possibles pour des recherches futures.