Fenintsoa Andriamasinoro
email: f.andriamasinoro@brgm.fr

Daniel Cassard
email: d.cassard@brgm.fr

Bruno Martel-Jantin
email: b.martel-jantin@brgm.fr

ISATEM: An Integration of Socioeconomic and Spatial Models for Mineral Resources Exploitation

Keywords: spatial shape data, socioeconomic model, simulation, agent, component, mineral resources exploitation

In the spatial-integrated socioeconomic model field, a multi-agent approach is appropriate for supporting applications modelled at a detailed territory scale, but it is less used than other approaches when supporting applications modelled at a larger scale. One possibility would be to have a more generic platform that is capable of supporting both levels. Moreover, at the spatial level, integration of dynamic spatial data and, in our case, spatial shape data should be reinforced so that, at any moment during a simulation, a user should be capable of exporting the temporal evolution of the spatial state as a (new) shape map, exploitable in a GIS tool. This paper aims to contribute to the improvement of these two aspects. We began the study with ADK, an existing agent platform, ending up with a new platform known as ISatEM. Our thematic interest is the field of mineral resources exploitation.

Introduction

Socio-economic modelling can be described as the representation of the relationship between economic activity and social life [START_REF] Haberl | Towards an integrated model of socioeconomic biodiversity drivers, pressures and impacts. A feasibility study based on three European long-term socioecological research platforms[END_REF]. Spatial-integrated socioeconomic models (hereafter SISM) are models that often concern the management of natural resources, in which economic or social activities often apply pressure to a geographical space, measured at the territory scale where the social actors are situated. SISM application domains are various: not just water resources [START_REF] Lanini | Socio-hydrosystem modelling for integrated water-resources management -The Herault catchment case study, southern France[END_REF], bioenergy [START_REF] Madlenera | Introduction to the special section "Modeling socio-economic aspects of bioenergy use: methodologies, case studies, and policy evaluation and guidance[END_REF], fisheries [START_REF] Versmisse | Developing a bioeconomic simulation tool of fisheries dynamics: a case study[END_REF], etc., but also mineral resources exploitation [START_REF] Andriamasinoro | High-Level vs. Low-Level Abstraction Approach for the Model and Simulation Design of Ultra-pure Quartz Exploitation in Northeastern Madagascar[END_REF]. Mineral resources exploitation is a SISM composed of socioeconomic actors performing a set of tasks 1 , starting from the production of ores, continuing through their transport to the transformation area and ending with the (second) transport of the final product to the area of consumption, where it is either sold and used. The study scale may be micro (local site scale), medium (regional) or macro (national). Socioeconomic impacts are jobs and incomes. Spatial interests are transport distance (impacting on cost), environmental impact (generally due to production and transport) and also spatial (re)distribution of production centres and resources availability [START_REF] Deschamps | Germanium potential in Africa: a predictive approach methodology[END_REF].

Designing a SISM involves the selection of the appropriate modelling approach, depending on the application territory scale. A multi-agent system (hereafter MAS) [START_REF] Wooldridge | An Introduction To Multiagent Systems[END_REF] is often used, especially if the application territory is defined at a micro scale [START_REF] Calderoni | Ethologie Artificielle et Contrôle Auto-Adaptatif dans les Systèmes d'Agents Réactifs: de la Modélisation à la Simulation[END_REF] [START_REF] Hugues | Synthesis of Robot's Behaviors from few Examples[END_REF]. At a larger scale, other approaches, such as dynamic systems [START_REF] Lanini | Socio-hydrosystem modelling for integrated water-resources management -The Herault catchment case study, southern France[END_REF], may be more appropriate even if a MAS is still acceptable. Besides, simulating a SISM results in a constant evolution of the state at both socioeconomic and spatial levels. As such, simulation is a way to constantly acquire new temporal data for these levels. In particular, at a spatial level, it should be possible for the simulation user, at any time during an ongoing simulation, to export this dynamic spatial data as (new) shape map data. Consequently, the user, after importing these successive maps in a Geographic Information System (GIS) tool, will be presented with a superposition of files showing the spatial state of one system at different times.

By focusing, at an application level, on the field of mineral resources exploitation, the objective of the work described in this paper is to present and discuss our contribution to two aspects: (a) the improvement of a multi-agent model, formerly designed to support applications modelled at a micro-territory scale, to a more generic object model, capable of also coping with an application modelled at a larger territory scale; and (b) the improvement of the conceptual integration of dynamic spatial shape2 data in a SISM, as explained in the previous paragraph. In this paper, shape object refers to these spatial entities having line, circle and polygon forms, and a shape map only refers to ESRI® shape file specification, composed of the three files shp (for entity geometry), dbf (for entity attributes) and shx (for the indexes).

Our approach is to start, as an initial case-study, with an existing multi-agent system known as ADK (for Agent Developer Kit) to finally end up with a new resulting model and simulation platform known as ISatEM (Integrated Systems applied to Exploitation of Mineral resources). Temporal storage of the simulated SISM data is the main issue that must be handled during the work.

Section 2 presents ADK. Section 3 presents our proposal, ISatEM, which is then discussed in Section 0. Section 5 concludes the paper and outlines perspectives.

ADK: an initial case study

ADK was developed by Calderoni [START_REF] Calderoni | Ethologie Artificielle et Contrôle Auto-Adaptatif dans les Systèmes d'Agents Réactifs: de la Modélisation à la Simulation[END_REF] with the idea of simulating a society of artificial agents. ADK contains three of the main components generally found in Multi-Agent Systems: agents, objects and environment. At a spatial level, ADK uses shape format to model its data. The agent behaviour is based on the triad "perception-ISATEM: An Integration of Socioeconomic and Spatial Models for Mineral Resources Exploitation deliberation-action". Messages exchanged inside ADK are then called percepts. At each simulation time step, percepts are propagated throughout the environment according to the previous state of the system. For example, a visual percept, which contains the position of an agent or an object, is propagated so that all agents can behave accordingly, regarding what to do and where to go.

Scope of the ADK approach.

The ADK approach is appropriate for applications modelled at a very detailed scale, such as robot foraging problems [START_REF] Calderoni | Ethologie Artificielle et Contrôle Auto-Adaptatif dans les Systèmes d'Agents Réactifs: de la Modélisation à la Simulation[END_REF], [START_REF] Hugues | Synthesis of Robot's Behaviors from few Examples[END_REF]. In the domain of mineral resources exploitation, it is also appropriate for applications such as the exploitation of quartz at the scale of Rantabe in Madagascar [START_REF] Andriamasinoro | Modeling the Ultra-pure Quartz Exploitation in Northeastern Madagascar: Impact of the Activity on the Socio-Economical Situation of the Population In[END_REF] or artisanal and small-scale gold mining at the Alga site in Burkina Faso [START_REF] Andriamasinoro | Artisanal and Small-scale Gold Mining in Alga (Burkina Faso): Building a Decision-Aid Model for Development and Governance[END_REF] (let Asgma). At a larger application scale (cf. Section 3.1), the ADK approach may still be employed, but it may be cumbersome to use the above triad to model an application at such a level: it does not provide more information to the application and it may overburden the simulation performance.

State of the art regarding spatial representation.

Regarding the spatial level, the fact that ADK uses shape format is interesting for our purpose but it has some limitations. To ascertain the details of these limitations, let us focus on the application of ADK to Asgma. Asgma is a mineral resources exploitation that is composed of a task sequence, from shaft extraction to successive treatments of crushing, grinding, sluice washing, winnowing and mill grinding. Each task is performed by a team of actors. Transport is carried out by boys with carts. The Asgma model is a SISM, the socioeconomic part of which is modelled in [START_REF] Andriamasinoro | Artisanal and Small-scale Gold Mining in Alga (Burkina Faso): Building a Decision-Aid Model for Development and Governance[END_REF].

The spatial representation of Asgma is shown in Fig. 1. In detail, Fig. 1.a shows the content of the unique file, designated asgma.ads that ADK uses to initialise the simulation illustrated in Fig. 1.b. Lines starting by # are comments. Only position, nb_agents, id and dimension properties concern the spatial initialisation.

The formal syntax of each line in asgma.ads is described in Equation

Fig. 1.b shows agents having a circular shape and task areas having a polygonal shape. We can see that spatial dynamic representation exists, in particular in the transport process: not only can the conveyor agent move but it is also possible to track the spatial evolution of such movement.

However, the spatial information presentation is currently approximate: in asgma.ads, the content is set by the user according to his/her own perception. Regarding the conveyor movement in particular, the conveyor goes in a straightforward manner, from the shafts to the crushing area whereas, in real-field, the conveyor cart actually follows determined paths that should allow the model to evaluate the transport cost. These limitations are due to two reasons: not only did realfield data collection in the upstream phase not consider spatial aspects [START_REF] Jaques | Artisanal and small-scale gold mines in Burkina Faso: today and tomorrow[END_REF], but even if this was the case, ADK cannot read data from a shape map (these two actions should both exist). As a result, the economic impact of the transport activity in the Asgma network could not be modelled, as noted in [START_REF] Andriamasinoro | Artisanal and Small-scale Gold Mining in Alga (Burkina Faso): Building a Decision-Aid Model for Development and Governance[END_REF].

Besides, ADK displays all polygonal shapes, obligatory in the same form (cf. Finally, it is not possible for ADK to store the temporal evolution of spatial data during a simulation [3] [5]. When a simulation stops and ADK is closed, all simulated data is lost. Due to a real-word demand, in the field of mineral resources management, a new application called FlowMod, defined at a regional scale, has to be modelled. Since the modelling process at this scale requires going beyond a multi-agent approach, an improvement needs to be made to have a framework that is conceptually capable of supporting both FlowMod and Asgma applications and of having a better data storage mechanism regarding the previous ADK limitations. A collection of real-field data should also be made to avoid an approximate spatial representation, as was explained concerning Asgma. Section 3.2 describes how we conceptually translate from ADK to the new framework known as ISatEM (for Integrated System applied to Exploitation of Mineral resources). Beforehand, let us introduce FlowMod.

Presentation of the larger-scale application

Description. FlowMod corresponds to the modelling and prospective simulation of the production (from a quarry) and the flow management of aggregates3 in Seine-Normandie, a region of France. If we compare Asgma and FlowMod with regards to territory scale, the whole Asgma system is equivalent, in FlowMod, to one quarry. Technically, FlowMod models the following situation: after aggregates are produced, they are supplied to communities4 by trucks. During transport, the shortest itinerary is chosen because the producing companies are obliged to keep transportation distances to a minimum for the large volumes of materials involved in order to remain economically viable. Each quarry has a lifetime after which it is definitely closed, unless the regional administrative authority agrees to re-open it. After a quarry is closed, a new quarry resource and then a new itinerary leading to that resource, has to be searched for.

The dynamic spatial modelling case study presented in this paper concerns the modelling and exportation to a GIS tool of the temporal evolution of the itinerary between a given community and a quarry, knowing that the latter changes over time after a previous quarry is closed and assumed not to be renewed.

Real-field data used. At a spatial level, we acquired the following shape layers, temporarily noted here layer_name{form}: quarry{point}, obtained from the 'GIS for Mineral resources' project [START_REF] Leistel | SIG Ressources Minérales Françaises -Architecture et mode d'emploi des applications de saisie[END_REF], and community_node{point}, road{line}, and road_node{point} layers, obtained from the Route500® numerical product [START_REF]The Route 500® numerical product[END_REF].

At a socioeconomic level, we used the results of the data collection performed in [4], containing, for example, the average income that a quarry exploitation can bring. F.Andriamasinoro, D.Cassard, B. Martel-Jantin

From ADK to ISatEM

ISatEM resumes the essential concepts of ADK (agents, objects, environment, simulation and behaviour), with the difference that the concept of agents and objects is generalized to that of components that may be spatial or transversal. The ADK environment then becomes an ISatEM environment for components.

The concept of spatial components.

A spatial component is a dynamic entity composed of input ports (which receive events), fire ports (which send events), behaviour and properties. There are two generic properties: a spatial property designated Geometry, which may be a line, circle or polygon and a behavioural property designated state. The possible values for state are contained in a static property designated possible states. All non-generic properties are either socioeconomic properties or component properties, i.e. properties referring to other components. Geometry, state and socioeconomic properties are called temporal properties, namely properties whose value can evolve over the simulation time.

An output fire port takes the form of FireEvent(), where Event Y is the event to be sent from that port. Symmetrically, an input event port is associated with the function that should be performed on receiving the associated event. It takes the form of OnEventX(). There is always at least one input port named OnTimeChanged(), which continuously receives the system timer event at each simulation time step. The current value of state determines the unit goal and then the unit behaviour (which may include a thinking process if the component represents a cognitive agent) to be adopted during that time step, after which state is re-evaluated by a StateTransition() function, invoked after OnTimeChanged ().

In FlowMod, spatial components are Quarry (circle), RoadNode (point), Road (line), Community (circle), Itinerary (line) and Truck (polygon). It may be noted that only the four first components have a corresponding shape map of real-field data.

Fig. 2 illustrates what a spatial component is. As an example in FlowMod, the Quarry component is shown (in a simplified way, for space reasons).

ISATEM: An Integration of Socioeconomic and Spatial Models for Mineral Resources Exploitation

From the behavioural points of view, a quarry is an entity in which behaviour is driven by the goal to produce the necessary aggregates needed by its corresponding community while avoiding having too much stock of non-consumed production. Likewise, a truck conveys the maximum of aggregates in a day to maximize its profits while trying to diminish as much as possible the quantity of CO 2 produced, and a community tries to acquire the appropriate quantity of aggregates corresponding to its population's needs (local building of houses or roads, etc).

Transversal components.

A transversal component is a component with the following differences compared to a spatial component: (a) it has a global view to all spatial components, allowing it to perform a computation involving all of the latter elements, and (b) it does not have state and Geometry properties.

In FlowMod, transversal components are: -ItinerarySearch, which looks for the itinerary and the quarry that should supply a community requiring aggregates: research criteria are the existence of a nonused quarry and the shortest itinerary between it and the community. -TruckManager, which adds or removes a truck, depending on the quantity produced for a community. -CO2Evaluator (and resp. FlowEvaluator), which computes, at each OnTimeChanged(), all the CO 2 released by the production and the transport processes (resp. that computes the quantity of aggregates conveyed by trucks). During a simulation, the OnTimeChanged() of all transversal components is always run before that of spatial components.

A global view of the ISatEM architecture

At a generic level, ISatEM is composed of three packages: a kernel, a user interface and a document, as detailed below and illustrated in Fig. 4.

The kernel. The ISatEM kernel is based on three modules: a library module, a model module and a simulation module. One module corresponds to one stage of an application design, and is inspired by the architecture proposed by [START_REF] Serment | For a generic software architecture facilitating environmental decision support system development: Illustration with the Camargue Ecosystem[END_REF].

The library module is like a factory that creates all the types of components required by the application. It only is an environment development where the code of the components is written and compiled. We will not go further into this module here.

Model module instantiates the component types designed in the previous module. There are three ways to instantiate a component: either manually, or by computation during a simulation, or by a (shape file) importation process, via an importation/exportation engine (let I/E engine) included in this module. Created components may be in interaction with each other or not, depending on the application.

Simulation module simulates the content of the component environment. There are three modes of simulation: the none mode, during which nothing is saved during the simulation, the execution mode during which, at each time step of the simulation, the F.Andriamasinoro, D.Cassard, B. Martel-Jantin value of each temporal property of each component is saved "online" by a property logger, and the replay mode, which reviews the simulation at the "offline" phase, only by retrieving the corresponding property values of the current simulation time, previously saved. In that mode, it is possible to go back and forth during the simulation, without performing any computation from the beginning again.

The user interface (UI).

This contains the interface of the functions described above. Furthermore, it contains (a) a map displayer, which shows all shape maps imported by the I/E engine via a layer manager, and (b) a comment editor, at the user's disposal. Simulation and model modules have the same UI as is presented in Fig. 3. FlowMod components; at bottom, two shape layers (quarries and roads); at top right, the simulation time as well as the simulation time step and the three simulation modes.

The ISatEM document. An ISatEM document contains all the data corresponding to an application. When the ISatEM software starts, no application is actually loaded until the ISatEM document containing that application is opened by the user, (exactly like a user opens an MS-Word® document in MS-Word® software). An ISatEM document is a container, in the form of a ZIP file, generated by ISatEM, and containing the following files: -The files generated/used by the property logger during the execution mode. There is one file per component, as formalized later in Equation 2. The files are in CSV (Common-Separated Values) format. -A list of the current imported shape files.

-The files currently managed by the comment editor. They are in HTML format.

-A file storing the current order in which layers of imported shapefile are successively displayed, from top to bottom, as in a GIS tool. For example, in Fig. 3, the quarry layer is above the road layer (cf. the layer manager view). -All classes designed by the library module. They are stored in a simple object (binary) file, to which we allot the extension .LBR (referring to the library term) Organisation of the property logger files. The organisation of the information in the CSV file managed by the property logger is inspired from that of asgma.ads with, in addition, the introduction of temporal values. However, one CSV file corresponds not to the whole simulation, as in Asgma, but to one component only. Equation 2 explains the process, where expressions in "[ ]" are optional. As an example: for a quarry (a circle shape) designated q2, having an initial stock of 1000 tonnes, and being capable of producing 0.5 tonnes of aggregates per simulation time unit, we will have the information below inside the file named quarry.q2.csv after one simulation time step, and under the execution mode. → and written on a whole line // Regarding the Geometry property, we have currentTime, "circle", xCentre, yCentre, radius // for circles currentTime, "polygon", x 0 , y 0 , x 1 , y 1 , x 2 , y 2 [, …, x n , y n ] // for polygons currentTime, "line", x a , y a , x b , y b [, …, x m , y m ] // for lines (2)

Generation of new dynamic shape data

The only mechanism that drives the dynamic (i.e. the evolution of the system state) of ISatEM is the simulation of the content of the component environment. The full process is presented in Fig. 5 and explained in the next paragraph. If the user wants to evolve the state of entities contained in a shp/dbf file, he/she has to (a) import the map into ISatEM via the I/E engine and (b) select the area of interest (let aoi) from the maps, via the map displayer. This selection transfers the content of each entity in the shp/dbf files to a created instance of the corresponding spatial component as follows: the shp content is transferred to the Geometry property of that component and the dbf content to the socioeconomic properties. For example, the content of a quarry entity from the shp/dbf layer is transferred to an instance of quarry component, a sample of which has been described in Fig. 2.a. Next, during ISATEM: An Integration of Socioeconomic and Spatial Models for Mineral Resources Exploitation simulation, values of these spatial components will evolve via their interaction to other spatial components and via the action of transversal components. At any time, the temporal property values of these spatial components can be exported to a new shape file. As a result, a user can export two types of (new) shape data layers, classified in the way the corresponding upstream components have been created: -Existing evolved layers, viewed as the temporal evolution of the initial imported shape, at the time t where it is exported. -New layers, resulting from the exportation of instances of spatial component types that are not initialised by a previous importation process but by computation during the simulation. It is, in FlowMod, the case for the Itinerary (cf. Fig. 6, simplified for space reasons) and Truck layers. Note that the state property is not manipulated by the I/E engine. State is preinitialised in the component type declaration (e.g. in the quarry component, the initial value of state is in_production, as illustrated in Fig. 2.b), is saved by the property logger during simulation, and is not concerned by the exportation process.

Results

Let us take a scenario where, each time an aggregate supplying the community of Rouen (Seine-Maritime) has produced over 100 days it is closed and is not renewed. As explained before, this situation systematically involves the search for a new quarry and itinerary after 100 days. At each newly found itinerary, the Itinerary layer is exported and integrated in a GIS tool where, for better visibility, only the itinerary starting from Rouen is kept. In ISatEM, time for exportation is not important as long as exportation is made inside the itinerary lifetime. The simulation time step is 30 minutes. Fig. 8 shows the final result visible in the GIS tool, after three exportations.

General discussion

The result illustrated in Fig. 8 is still being adjusted and validated by the domain experts, regarding the itinerary search rules (the quarries found are not always exactly those expected by them) and the simulation lifetime: at present, we are able to stabilise tests of up to around 15,000 time steps (i.e. 300 days of 30 minutes) with the replay mode. However, this current validation does not affect the capacity of the system to generate new shape data by simulation, whatever the simulation mode. In a more general manner, Isatem can be viewed as a complement to a GIS tool. It generates new dynamic spatial information by simulation, can display such information by itself (e.g. truck moving) and can store and reproduce the action (via the replay mode). However, Isatem cannot analyze spatial data to the same extent as a GIS. Inversely, a GIS can represent spatial information but in a static way only. One solution is to make them operate in close collaboration since, in the end, they are both data providers and analyzers at their respective levels. As one result, the quality of a map to be produced as a decision aid support, for example, can be the result of its iterative design between both tools.

Returning to the modelling work, and compared to the ADK state of the art as described in Section 2, it is now possible to import and export shape files. Besides, spatial and socioeconomic temporal data can be saved and restored at any time. At a methodological level, this improvement has been achieved thanks to the improvements made from (a) the asgma.ads file syntax formalized in Equation 1, to (b) the quarry.q2.csv file (taken as example) formalized in Equation 2, and to (c) finally the concept of the ISatEM document. Nevertheless, we agree that choosing .CSV as the format to store the components' property value may be open to discussion. In fact, our first idea was to apply the document concept. A better optimized format for saving temporal values undoubtedly exists and should be a subject for further research. Besides, if ISatEM appears overall to be conceptually better than ADK, one feature that ADK currently only has compared to ISatEM is, at a display level, the ADK capacity to follow the track of a moving entity (cf. Fig. 1). Integrating this feature into ISatEM needs to be investigated. Integrating a generic track layer may be a first manner of approaching this situation.

Regarding SISM design, generalizing the concept of agents and objects of ADK to ISatEM components has the following advantage 5 : two application territory scales can be managed. Indeed, if FlowMod can be modelled with ISatEM components, using the ISatEM component to model ADK architecture (recall the presentation in Section 2), then the Asgma application is still feasible. The result is shown in Fig. 9 where a PerceptsPropagator is transversal and an ADKAgent is spatial. The notion of components may lead the reader to think about the DEVS (Discrete EVent System specification) components [START_REF] Dalle | Extending DEVS to support multiple occurrences in component-based simulation[END_REF], widely used in modelling and simulation contexts, integrating space [e.g. 19]. The reason we do not use DEVS is a visualization issue: we want to see the continuous movement of our trucks in the system, as has been done with the conveyor in Asgma (cf. Fig. 1). We think that DEVS is not the appropriate approach for that purpose, unless the duration of the internal state transition of the DEVS component is statically set to that of the simulation time. But in such case, the actual interest of using DEVS formalism is diminished.

Conclusions and Perspectives

Summary. Spatial-integrated socioeconomic models (SISM) are models that can represent the relationship between economic activity, social life and the pressure social actors apply to the geographical space containing them. Although a multi-agent approach is often used to support applications modelled at a detailed territory scale, it may be less appropriate when an application is modelled at a larger scale. Moreover, since SISM is a spatial model, conceptual integration of dynamic spatial data and, in our case, spatial shape data should be reinforced.

By focusing on the domain of mineral resources exploitation, we have proposed, in this paper (a) to improve a multi-agent model to obtain a more generic object model

  Fig. 1.b). This is because the position parameter only has two values, which actually refer to the barycentre of each task area polygon. All polygon drawings start from this barycentre. All other coordinates that should exist in a polygon are ignored.

Fig. 1 .

 1 Fig. 1. (a) Content of the file asgma.ads, which launches the Asgma simulation illustrated in (b).

Fig. 2 .

 2 Fig. 2. The generic scheme of a spatial component (a), followed by an example from the FlowMod application: the quarry component (b).

Fig. 3 .

 3 Fig. 3. The user interface of both model and simulation modules. Are displayed: at top left, all

Fig. 4 .

 4 Fig. 4. Illustration of the general architecture of ISatEM (the area inside the dashed line).

  , 700, 240, 4 // the same because the quarry does not move F.Andriamasinoro, D.Cassard, B. Martel-Jantin // Recall of Equation 1, applied to asgma.ads classId: (prop 1 val 11 [val 12 ]) [(prop 2 val 21 [val 22 ])] // Transformation for the CSV file classId → a CSV file named classId.componentId. (prop 1 , val 11 , [val 12 ]) → currentTime, prop 1 , val 11 , [val 12 ]

Fig. 5 .

 5 Fig. 5. The mechanism of the importation/exportation engine (the area inside the dashed line)

Fig. 6 .

 6 Fig. 6. Block diagram of how an Itinerary component is generated during simulation.

Fig. 7 .

 7 Fig. 7. Mechanism for generation of the Itinerary shape layers over time, starting from the importation/exportation engine, to the simulation of the content of component environment.

Fig. 8 .

 8 Fig. 8. Result of the exportation of three itinerary layers to three successive resources, obtained during one simulation. The start of the itinerary is the Rouen community.

Fig. 9 .

 9 Fig. 9. Design of the ADK architecture using the ISatEM component. The 'perceptiondeliberation-action' triad as well as the propagator concepts of ADK are still present.

prop 1 val 11 [val 12 ]) [(prop 2 val 21 [val 22 ])]

	1, in which
	expressions written in "[ ]" are optional.
	classId: (

At the application level, some tasks may be abstracted if not necessary for the modelling. F.Andriamasinoro, D.Cassard, B. Martel-Jantin

The choice of shape spatial format was made only because it was of interest to us. A discussion about which is better, grid or shape spatial format, is beyond the scope of this paper.

Aggregates are unconsolidated materials used as one of the main components of concrete and as foundations for road and railway infrastructures.

In France, a "community" corresponds to an administrative unit at a town scale.

F.Andriamasinoro, D.Cassard, B. Martel-Jantin

Another interest of this change is that it offers the possibility of supporting other SISM applications based on approaches other than a multi-agent approach, such as for example the system dynamics approach as used by[START_REF] Lanini | Socio-hydrosystem modelling for integrated water-resources management -The Herault catchment case study, southern France[END_REF].

for Mineral Resources Exploitation that is capable of also supporting applications modelled at a larger scale, and (b) to integrate the mechanism of dynamic spatial shape data, in which the temporal evolution of the spatial state of an ongoing simulation can be exported at any time, as (new) shape data stored in a map exploitable in a GIS tool. Our approach was to start from an existing multi-agent platform known as ADK, ending up with a new platform known as ISatEM.

Perspectives. Although ISatEM seems to be a better result for us, regarding dynamic spatial modelling, ADK still has the capacity to follow the track of a moving component, a feature that ISatEM does not yet integrate. The integration of such a feature constitutes the first perspective for ISatEM. The other perspective is the integration of what we call indicator display. An indicator is one component property, the evolution of which a user wants to visualize via one feature of the shape representing this component in a screen. A shape feature may be a width (for a line), a surface size (for a polygon and circle), or a colour (for all of them). Features may be combined if possible. During a simulation, when an indicator evolves, the corresponding shape feature also evolves. It results in a display of dynamic spatial shape data information, even on non-moving shapes. For example, the colour of a quarry shape may evolve according to its current stock (the indicator). Regarding the mineral resources field, one technique of selecting indicators is presented in [6].


Quang Trung

Matthieu Arzel

Christophe Jego

Warren J Gross
email: wjgross@ece.mcgill.ca

Stochastic decoding of Turbo Codes

Stochastic computation is a technique in which operations on probabilities are performed on random bit streams. Stochastic decoding of Forward Error-Correction (FEC) codes is inspired by this technique. This paper extends the application of the stochastic decoding approach to the families of convolutional codes and turbo codes. It demonstrates that stochastic computation is a promising solution to improve the data throughput of turbo decoders with very simple implementations. Stochastic fully-parallel turbo decoders are shown to achieve the error correction performance of conventional A Posteriori Probability (APP) decoders. To our knowledge, this is the first stochastic turbo decoder which decodes a state-of-the-art turbo code. Additionally, an innovative systematic technique is proposed to cope with stochastic additions, responsible for the throughput bottleneck. EDICS HDW-

I. INTRODUCTION

Iterative Soft-Input Soft-Output (SISO) decoding was first presented by Berrou et al in 1993 [START_REF] Berrou | Near shannon limit errorcorrecting coding and decoding: Turbo-codes[END_REF] for the turbo decoding of two parallel concatenated convolutional codes, widely known as turbo codes. Since their invention, turbo codes have received considerable attention due to their performance close to the theoretical limits. They are especially attractive for mobile communication systems and have been adopted as part of several channel coding standards for high data rates such as UMTS and CDMA2000 (third-generation) or 3GPP-LTE (the last step toward the 4 th generation). The general concept of iterative SISO decoding has been extended to other families of error-correcting codes such as product codes. It also prompted the rediscovery of Low-Density Parity-Check (LDPC) codes. After many years of research, many decoding algorithms, decoder architectures and circuits were proposed. Although the industrial products were digitally designed, J. Hagenauer [START_REF] Hagenauer | The analog decoder[END_REF] and H.-A. Loeliger [START_REF] Loeliger | Probability propagation and decoding in analog VLSI[END_REF] simultaneously proposed to apply the SISO concept to a continuous-time continuous-value decoding scheme with analog circuits to provide high decoding speeds and/or low power consumptions with extremely simple computation units working in parallel. In 2003, V. Gaudet, a member of the analog decoding community, and A. Rapley, proposed a novel approach [START_REF] Gaudet | Iterative decoding using stochastic computation[END_REF] based on stochastic computation.

Principles of stochastic computation were described in the 1960's by Gaines [START_REF] Gaines | Stochastic computing[END_REF] and Poppelbaum et al. [START_REF] Poppelbaum | Stochastic computing elements and systems[END_REF] as a method to carry out complex operations with a low hardware complexity. The main feature of this method is that the probabilities are converted into streams of stochastic bits using Bernoulli sequences, in which the information is given by the statistics of the bit streams. As a result, complex arithmetic operations on probabilities such as multiplication and division are transformed into operations on bits using elementary logic gates. This advantage allows architectures to be designed with low computational complexity and enables high data rates to be achieved.

Stochastic computations have been recently considered to decode FEC codes. Early stochastic decoding has been applied to some short error correcting codes such as the [START_REF] Winstead | Stochastic iterative decoders[END_REF][START_REF] Gaudet | Iterative decoding using stochastic computation[END_REF] Hamming code [START_REF] Gaudet | Iterative decoding using stochastic computation[END_REF] and a (256,121) block turbo code based on two [START_REF] Winstead | Error-control decoders and probabilistic computation[END_REF][START_REF] Sharifi Tehrani | Stochastic decoding of linear block codes with high-density parity-check matrices[END_REF] Hamming codes [START_REF] Winstead | Stochastic iterative decoders[END_REF]. The first implementation of a stochastic decoder with a (16,8) LDPC code was described in [START_REF] Gross | Stochastic implementation of LDPC decoders[END_REF]. An improved stochastic decoding approach was then proposed to decode practical LDPC codes [START_REF] Sharifi Tehrani | Stochastic decoding of LDPC codes[END_REF], [START_REF] Sharifi Tehrani | Survey of stochastic computation on factor graphs[END_REF]. This approach was also extended to well-known linear block codes with high-density parity-check matrices, namely BCH codes, Reed Solomon codes and product codes [START_REF] Sharifi Tehrani | Stochastic decoding of linear block codes with high-density parity-check matrices[END_REF]. When compared with conventional Sum-Product implementations, stochastic decoding could provide near-optimal performance for practical LDPC codes. The potential of the stochastic technique for low complexity and high throughput was recently demonstrated by the FPGA implementation of a (1056,528) LDPC decoder [START_REF] Sharifi Tehrani | Fully parallel stochastic LDPC decoders[END_REF] which achieved a throughput of 1.66Gb/s. Thus, state-ofthe-art decoders combine high throughput and low complexity thanks to the stochastic approach.

This paper proposes to extend stochastic computation to the design of turbo decoders. A major challenge in the implementation of turbo decoders is to achieve high-throughput decoding. Indeed, the next generations of mobile communication systems will require data rates of 1 Gb/s and beyond. Thanks to stochastic decoding, a fully-parallel architecture is a promising response to this challenge. In order to provide a typical study case, the investigation is limited to a singlebinary turbo code similar to the ones adopted for the next generation of mobile systems (3GPP-LTE).

This paper is organized as follows. Section II provides a brief overview of the turbo codes, the APP algorithm and the principles of stochastic computation. Section III describes the APP-based stochastic processing applied to the iterative decoding of practical turbo codes. Section IV introduces a method to increase the stochastic decoding throughput. Some simulation results are given in section V to compare the stochastic processing with a conventional decoding using the

d i y i 1 d i = 0 d i = 1 (b) u i v i 1 v i 2 Extrinsic Extrinsic information information Decision SISO 1 SISO 2 Π Π Π -1 (c)

II. BACKGROUND

A. Turbo codes

Fig. 1a shows the structure of a turbo encoder made up of two tail-biting Recursive Systematic Convolutional (RSC) encoders concatenated in parallel thanks to an interleaver. Each RSC code has a coding rate R=1/2, a codeword length n = 2k and a constraint length ν = 4. It can be represented by means of a trellis diagram as shown in Fig. 1b. The overall code rate of the turbo code is R = 1/3. At each time i, the information bit (or systematic bit) d i and two redundancies (or parity bits) y i 1 and y i 2 corresponding to the contributions of each RSC code are provided by the encoder. The architecture of the turbo decoder illustrated in Fig. 1c is composed of two SISO decoders that exchange some probabilities thanks to an interleaver (Π) and a de-interleaver (Π -1 ). Each SISO decoder is fed with three different inputs: the channel output corresponding to the systematic bit (u i ), the parity bit produced by the corresponding component encoder (v i 1 or v i 2 ), and the extrinsic probabilities computed by the other component decoder. The iterative exchange of extrinsic probabilities between the SISO decoders greatly improves the error correction performance.

B. SISO decoding algorithm

In order to decode convolutional codes, an algorithm known as BCJR was introduced by Bahl et al. [START_REF] Bahl | Optimal decoding of linear codes for minimizing symbol error rate (corresp.)[END_REF]. It was adapted by

Anderson and Hladik to deal with tail-biting codes [START_REF] Anderson | Tailbiting MAP decoders[END_REF]. The APP decoding process performed by each SISO component decoder can be summarized by the following steps.

1) Branch metric computation: First, the branch metrics γ i (s ′ , s) can be expressed as:

γ i (s ′ , s) = Pr a d i = j ×Pr ex in d i = j|u, v 2 × Pr u i , v i 1 |d i , y i (1)
where d i is the information bit for the transition from state s ′ to state s of the trellis at time i. Pr a (d i = j) is the a priori probability corresponding to the transition d i = j. If a uniform source is considered, all the symbols have the same probability during the transmission, then Pr a (d i = j) = 1/2. Pr ex in d i = j|u, v 2 is the incoming extrinsic probability computed by the other component decoder. It is calculated from the input sequences u and v 2 . In the case of an Additive White Gaussian Noise (AWGN) channel, the third factor is given by:

Pr u i , v i 1 |d i , y i = exp u i , d i + v i 1 , y i 1 σ 2 (2)
where σ 2 is the variance of the AWGN and a, b represents the scalar product of two symbols a and b.

2) State metric computation: Second, the forward and backward metrics are recursively calculated as follows:

α i+1 (s) = 2 ν-1 -1 s ′ =0 α i (s ′ ) γ i (s ′ , s) (3)
β i (s ′ ) = 2 ν-1 -1 s=0 β i+1 (s) γ i (s, s ′ ) (4)
The state metric values are initialized at the same probability, i.e. α 0 (s

) = β k (s) = 1/2 ν-1 for any s ∈ [0..2 ν-1 -1].
During the decoding process, the state metrics have to be kept in a given range and therefore are normalized regularly.

3) Extrinsic probability computation: Third, in the context of an iterative process, the component decoders exchange extrinsic probabilities calculated as:

Pr ex out d i = j|u, v 1 = (s ′ ,s)/d i (s ′ ,s)=j φ i e (s ′ , s) (s ′ ,s) φ i e (s ′ , s) (5)
where

φ i e (s ′ , s) = α i (s ′ ) β i+1 (s) γ i e (s ′ , s) (6)
γ i e (s ′ , s) = exp v i 1 , y i 1 σ 2 (7)
4) A posteriori probability computation: Finally, a posteriori probabilities are computed so that:

Pr (d i = j|u, v 1 ) = (s ′ ,s)/d i (s ′ ,s)=j φ i (s ′ , s) (8)
where

φ i (s ′ , s) = α i (s ′ ) β i+1 (s) γ i (s ′ , s) (9)
The decoded symbol d i at time i is equal to the value j that maximizes this a posteriori probability.

A sub-optimal version in the logarithmic domain with an acceptable loss of performance referred to as Max-Log-MAP (or Sub-MAP) algorithm was introduced by Robertson et al. [START_REF] Robertson | A comparison of optimal and sub-optimal map decoding algorithms operating in the log domain[END_REF].

C. Stochastic decoding principles 1) Stochastic computation:

In a stochastic computing process, the probabilities are converted into Bernoulli sequences using random number generators and comparators [START_REF] Gaines | Stochastic computing[END_REF]. The number of bits at "1" in a stream represents the corresponding probability. For instance, a 10-bit sequence with 4 bits equal to "1" represents a probability of 0.4. Therefore, different stochastic streams may represent the same probability. In order to obtain a good precision, the length of a sequence has to be large. The conventional arithmetic operations, such as multiplication or division, are thus processed by simple logic gates. For instance, the multiplication of a set of N probabilities p 0 , p 1 , . . . , p N -1 can be achieved by an N -input AND logic gate fed with N mutually independent stochastic streams. The output probability of the AND logic gate is exactly equal to N -1 i=0 p i . At each time, the bit of each input sequence contributes directly to the output bit. Similarly, the normalisation of two Bernoulli sequences is carried out by means of JK flip-flops [START_REF] Gaudet | Iterative decoding using stochastic computation[END_REF].

2) The thorny addition: From the equations of the APP algorithm, it can be noted that besides the multiplication and division operations, a huge number of additions is necessary. Since the addition of N values in the interval [0,1] may take values bigger than 1, this operation cannot be done directly with stochastic streams. The addition operands can be scaled equally so that the sum always lays in the interval [0,1]. In practice, a multiplexer that randomly selects one of the N inputs with probability 1/N will produce an output stream that is the scaled sum of the input probabilities

N -1 i=0 1 N p i .
At each time, each input bit does not contribute directly to the output bit. Consequently, the output sequence length has to be about N times larger than the input sequence lengths to achieve the same precision. This constraint is particularly problematic for the APP-based decoding process. Indeed, many additions are necessary to normalize the state metrics and to compute the extrinsic probabilities. Thus, processing addition operations with multiplexers severely slows down the decoding convergence speed of a turbo decoder.

III. STOCHASTIC DECODING APPLIED TO TURBO CODES

A. SISO component decoder architecture

The stochastic decoding of turbo codes requires the stochastic computation to be applied to a tail-biting APP algorithm, which relies on the trellis representation. Fig. 2 details the exchange of information between the various sections of a tailbiting APP decoder. There are as many sections as symbols to decode and each section is made up of four modules. A Γ module is fed by the channel outputs u i and v i , which are associated with the i th transmitted symbol d i and its parity bit y i . This module converts u i and v i into a priori probabilities, represented by two stochastic streams to compute the branch metrics and then the forward metrics in an A module and the backward metrics in a B module. These modules are involved in a recursive process since they use the forward and backward metrics α i and β i+1 from their neighbors and provide them α i+1 and β i . A Dec module decides the final value of each binary symbol, d i for the transmitted symbol d i . A last module is also required if the APP decoder is part of a turbo decoder: the Ext module. This module computes the output extrinsic probability P r ex out which is then used by a Γ module of the second APP decoder as the input P r ex in . All the modules exchange stochastic streams over a logic gate network based on the code trellis representation. Each stochastic decoding step is referred to as a decoding cycle (DC) and corresponds to the output of one new bit for each stochastic unit. The decoding process terminates when a maximum number of DCs is reached.

B. Hardware complexity

One major problem in stochastic decoding that deeply degrades the decoding performance is known as the latching problem [START_REF] Winstead | Stochastic iterative decoders[END_REF]. It is related to the sensitivity to the level of random switching activity (bit transition) [START_REF] Winstead | Error-control decoders and probabilistic computation[END_REF]. This problem can be easily observed at high Signal-to-Noise Ratios (SNRs). Different solutions have been suggested to solve the latching problem, and thus, to improve the BER performance of stochastic decoding, such as : using supernodes [START_REF] Winstead | Stochastic iterative decoders[END_REF], scaling the received Log-Likelihood Ratios (LLRs) up to a maximum value [START_REF] Winstead | Error-control decoders and probabilistic computation[END_REF], Edge Memories (EMs) insertion and Noise-Dependant Scaling (NDS) [START_REF] Sharifi Tehrani | Fully parallel stochastic LDPC decoders[END_REF]. The APP decoders proposed in this paper take advantage of EMs and NDS. In particular, EMs are assigned to stochastic streams that represent forward and backward metric values α i and β i to break the correlation using re-randomization. Similarly, EMs are assigned to stochastic streams used for the output extrinsic computation in the module Ext. Overall, ten 32-bit EMs are necessary for each section of the stochastic SISO decoder ...

G x 1 x 2 x n x ′ y exp(-x) exp(-x) exp(-x)
-log(y) Fig. 3: Principle of exponential-domain computation.

to circumvent the latching problem. The complexity of one section of the stochastic decoder in terms of elementary hardware resources and random bits is detailed in Table I. Vectors of 7 random bits are used by the stochastic SISO decoder to convert the channel outputs into stochastic streams. As already mentioned in this paper, the main drawback of this architecture is the need of N -to-1 multiplexers to perform additions. For this reason, solutions have to be investigated to replace these large multiplexers.

IV. STOCHASTIC ADDITION IN THE EXPONENTIAL COMPUTATION DOMAIN

In order to remove N -to-1 multiplexers for stochastic addition operations, a novel approach is proposed. The main idea is to carry out a critical operation F in the exponential domain thanks to the exp(-x) function. The output values of exp(-x) modules are then processed by using a simple operation G. Then, the result is converted back into a probability thanks to the function -log(x) as illustrated in Fig. 3. If F is the addition operation, then G is the multiplication operation, processed by an AND logic gate. Therefore, no large multiplexer is required to perform the stochastic addition operation.

A. Exponential and logarithmic transformations

The idea of processing stochastic streams in the exponential domain was first introduced by Janer et al. [START_REF] Janer | Fully parallel stochastic computation architecture[END_REF]. The exp(-x) function is chosen instead of exp(x) so that the output value can be represented by stochastic streams. In practice, the exponential function can be easily approximated by the first terms of its Taylor's expansion. In [START_REF] Janer | Fully parallel stochastic computation architecture[END_REF], the authors described some circuits for the first-, second-and third-order approximations. They also demonstrated that the accuracy of this approximation does not depend on the number of input probabilities that are being added. Therefore, this stochastic exponential transformation opens an efficient way to carry out the conversion of stochastic additions into stochastic multiplications. In [START_REF] Janer | Fully parallel stochastic computation architecture[END_REF], the result in the exponential domain was sufficient to end the data processing. Unfortunately in a turbo decoder architecture, the result of the addition operation has to be used by another module. Thus, the exponential stochastic stream has to be converted back into a conventional stochastic stream that corresponds to the addition of n terms. A logarithm function is necessary to perform this transformation. A Taylor's expansion is also considered in this case.

B. Hardware complexity

Table II gives a summary of the complexity of one section of the stochastic single-binary 8-state turbo decoder with additions in the exponential domain. Expanding the Taylor series to the second order is sufficient for both exponential and logarithmic modules. The additional cost of addition operations in the exponential domain in terms of hardware resources is reasonable. Indeed, 162 NAND2 logic gates, 205 AND2 logic gates, 98 D Flip-flops and eighteen 2-to-1 multiplexers are necessary to replace the twenty 8-to-1 multiplexers used for addition operations in the probability domain. The hardware complexity of one section of a stochastic single-binary 8state turbo decoder has to be compared with an fixed-point Sub-MAP counterpart. For such a SISO decoder, the received symbols are 5-bit quantized while the extrinsic information and state metrics are both 7-bit quantized to achieve almost ideal performance [START_REF] Montorsi | Design of fixed-point iterative decoders for concatenated codes with interleavers[END_REF]. A conventional Sub-MAP decoder is composed of three main parts, namely processing, memory and control. The major problem of the turbo decoders is the memory bottleneck. In order to reduce the state metric memory size, the sliding window principle can be applied, where each received frame has to be divided into several sliding windows. Such a sub-block processing is constrained by the sliding window initialization. To solve this constraint, additional costs in terms of resources and/or latency have to be considered. For a stochastic decoder, a randomization engine is necessary for providing random bits. These random bits are used in 2to-1 multiplexers and as the addresses of stochastic stream generators. Although this amount of random bits for one section might seem large, as shown in Table II, random bits can be significantly shared by different modules without having an impact in terms of BER performance [START_REF] Sharifi Tehrani | Fully parallel stochastic LDPC decoders[END_REF]. Moreover, random number generators using unreliable device behavior have to be considered since they require less hardware resources than conventional linear feedback shift registers. It means that a direct comparison between the two decoding techniques can only be done for the processing unit of one section. The FPGA implementation cost of a fixed-point Sub-MAP decoder must

Fig. 4: Performance of the stochastic decoding of a rate-1/2 convolutional code for codewords of 400 bits (a) and 4000 bits (b) and of a rate-1/3 turbo code for codewords of 600 bits (c).

be compared with the results given in Table II. One LUT is allocated for each elementary hardware resources of the Table II. In this case, 633 and 638 LUTs are necessary for the fixedpoint Sub-MAP and the stochastic versions, respectively. In contrast, the stochastic decoding of one section is less costly in terms of flip-flops. Indeed, the flip-flop number can be decreased from 1398 down to 680 if a stochastic decoder is considered. It means that stochastic decoding is competitive in terms of hardware complexity for turbo codes.

V. SIMULATION RESULTS

In this section, the decoding performance is given for different versions of stochastic decoders for both convolutional and turbo codes. Fig. 4a shows the BER performance of the stochastic decoding of a tail-biting RSC code (n = 400 bits, code rate R = 1/2) with 30K DCs and different optimizations. A decoder combining NDS and EMs provides a BER performance similar to the one of a conventional APP floating-point algorithm. Moreover, processing additions in the exponential domain enables a decrease of the number of DCs from 30K to 4K with an acceptable performance loss of 0.1dB when compared with the floating-point APP algorithm. Similar conclusions are obtained with a 4000-bit RSC code as shown in Fig. 4b. Thus, the extension of the stochastic decoding to convolutional codes is possible. The BER performance of the proposed stochastic decoding method is provided also for a (n = 600, R = 1/3) turbo code in Fig. 4c. The turbo code is designed with an S-Random interleaver [START_REF] Dolinar | Weight distributions for turbo codes using random and non-random permutations[END_REF]. The EM and NDS techniques are required to achieve good decoding performance. Stochastic turbo decoding needs 250K DCs to achieve the performance of the floating-point Sub-MAP decoding with 6 iterations. Fortunately, the exponential stochastic approach proposed in this paper enables the number of DCs to be reduced from 250K to 32K without any performance degradation. Thus, the proposed summation is a necessary step toward the implementation of high-speed stochastic turbo decoders. To compete with state-of-the-art turbo decoders, a stochastic decoder requires a higher level of parallelism. Two ways have to be explored. First, parallel processing of larger frames of a few thousands of bits -as in wireless communications standards -would be of major interest. Second, representing any probability with p parallel independent streams could divide the number of DCs by p and multiply the throughput by p. Naturally, a higher parallelism will impact the decoder complexity, which is the price to pay for high throughput devices.

VI. CONCLUSION

This paper extends the application of the stochastic decoding to the families of convolutional codes and turbo codes. Simulation results show performance close to the floatingpoint Sub-MAP decoding algorithm for (n = 600, R = 1/3) turbo codes. One major problem of a conventional stochastic decoding of turbo codes is the large number of decoding cycles. To reduce the number of cycles, a novel technique for implementing the stochastic addition operation has been investigated. It consists in transforming the stochastic additions into stochastic multiplications in the exponential domain. The number of decoding cycles is thus considerably reduced with no performance degradation. The results provided in this paper validate the potential of stochastic decoding as a practical approach for high-throughput turbo decoders and encourage to keep on investigating in this way.

Fig. 1 :

 1 Fig. 1: (a) Turbo encoder; (b) Trellis diagram; (c) Turbo decoder architecture.

Fig. 2 :

 2 Fig. 2: Stochastic tail-biting APP decoder.

TABLE I :

 I Complexity of one section of a stochastic single-binary 8-state turbo decoder with multiplexers for additions.

	Module	NAND2 AND2	OR2	Elementary hardware resources XOR2 Mux2:1 Mux8:1	3-bit counter	D Flip-flop	Random bits 7 bits 1 bit
	Γ	34	12						2
	A / B	32	8	8	24	8		256		96
	Ext	32	2	2	4	2		64		16
	Dec	37	2			2	2			6
	Total	167	32	18	52	20	2	576	2	214

TABLE II :

 II Complexity of one section of a stochastic single-binary 8-state turbo decoder with additions in the exponential domain.

			Module	NAND2 AND2	OR2	Elementary hardware resources XOR2 Mux2:1 Mux8:1	3-bit counter	D Flip-flop	Random bits 7 bits 1 bit
			Γ		34	12							2
			A / B	48	120	8	8	32			288		88
			Ext	34	52	2	2	6			82		16
			Dec	32	46		1			1	16		16
			Total	162	372	30	19	70		1	674	2	208
			(400 bits, R=1/2) tail-biting RSC code, 100 block errors			(4000 bits, R=1/2) tail-biting RSC code, 100 block errors
		1e-01
										1e-02
		1e-02
	Bit Error Rate	1e-03							Bit Error Rate	1e-04 1e-03
		1e-04								1e-05
			Stochastic decoding without NDS and EMs, 30k DCs
			Stochastic decoding with NDS, without EMs, 30k DCs
			Conventional stochastic dec. with NDS and EMs, 30k DCs		1e-06	Conventional stochastic dec. with NDS and EMs, 30K DCs
		1e-05	Exponential stochastic dec. with NDS, EMs, 4k DCs			Exponential stochastic dec. with NDS, EMs, 4K DCs
			APP algorithm decoding							APP algorithm decoding
		0	1	2	3		4	5	6	0	1	2	3	4	5	6	7
				Eb/No (dB)							Eb/No (dB)
				(a)									(b)
								APP turbo decoding (600 bits, R=1/3), 100 block errors
						1e-01
						1e-02
					Bit Error Rate	1e-03
						1e-04
								Conventional stochastic dec. with NDS and EMs, 100K DCs
								Conventional stochastic dec. with NDS and EMs, 250K DCs
						1e-05		Exponential stochastic dec. with NDS, EMs, 32K DCs subMAP normal turbo decoding 6 iterations
						0		0.5	1	1.5	2	2.5
									Eb/No (dB)


C Jégo

P Adde

Row-column parallel turbo decoding of product codes

Introduction:

In telecommunications, forward error correction (FEC) is a system of error control that improves digital communication quality. The most recent development in error correction is turbo coding [START_REF] Berrou | Near Shannon limit error correcting coding and decoding : Turbo Codes[END_REF]. The turbo code family refers to two classes of codes: Convolutional Turbo Codes (CTC) and Block Turbo Codes (BTC). Indeed, an iterative Soft Input Soft Output (SISO) decoding was successfully applied [START_REF] Pyndiah R | Near optimum decoding of product codes[END_REF] to product codes, first introduced by Elias [START_REF] Elias | Error-free coding[END_REF]. Product codes are a series of concatenated systematic linear block codes. The product code inherits the properties of the elementary codes that it is composed of. Let us consider an example with two identical BCH (n,k,δ) codes. The parameters of the resulting product code are therefore given by: n 2 (code length), k 2 (number of information symbols), δ 2 (minimum Hamming distance) and r 2 (code rate). The iterative decoding algorithm involves performing the successive decoding of rows and columns (two half-iterations).

Note that each iteration provides decoding operations for all rows and all columns of a matrix (product code). Moreover, a reconstruction of the matrix is necessary between each decoding. The block diagram of an elementary SISO decoder is presented in Figure 1, where k stands for the number of halfiterations.

R is the initial word received from the channel, W k is the pattern that contains the extrinsic information, that is, the additional information given by the decoder concerning the reliability of the decoded symbol, R' k is the result of extrinsic information weighted by a factor of α k , D k is the result of symbol decoding, α k and β k are constants that depend on the current half-iteration.

Previous work:

In the last few years, many block turbo decoder architectures have been designed [START_REF] Cuevas | New architecture for high data rate turbo decoding of product codes[END_REF]. The conventional approach involves decoding all the rows or all the columns of a matrix before the next half-iteration. When an application requires high-speed decoders, an architectural solution is to cascade SISO elementary decoders for each half-iteration as shown in Figure 2. In this case, memory blocks are necessary between each half-iteration to store channel data and extrinsic information. Each memory block is composed of four memories of qn 2 symbols where q is the number of bits to quantify the matrix symbols. Thus, duplicating a SISO elementary decoder results in duplicating the memory block which is very costly in terms of area. The latency can be defined as the number of symbols that was input into the turbo decoder before one symbol was fully handled. In the case of cascaded decoders, the architecture latency is equal to 2k*(n 2 +n) where n is the code length and 2k is the iteration number. For one half-iteration, n 2 and n are block memory latency and row or column decoding latency, respectively.

Row-column parallel turbo decoder for product codes:

In this letter, a rowcolumn parallel turbo decoding of product code is proposed. Since all the rows and all the columns of the matrix are distinct code words, they can be handled independently. Moreover, the symbol decoding for the rows and the columns does not have any particular order. For these reasons, the rows and the columns of a same matrix can be decoding in parallel. The matrix of extrinsic information is then updated during the decoding process. The aim of the row-column parallel approach is to use the more reliable extrinsic information each time. Let us consider S i and S j as the positions of the i-th symbol for a row and the j-th symbol for a column respectively. i and j are included between 1 and n. It can be also noted that the codeword length n of BCH codes is always a power of 2. For row-column parallel turbo decoding, one solution is to take j equal to n-i to avoid simultaneous access to the same symbol by the two SISO decoders. Thus, the row decoder begins with the first symbol S 1 of the row codeword and the column decoder begins with the last symbol S n of the column codeword, as shown in Figure 3. In this approach, the elementary decoders have to handle only one code word at a time. For this reason, a pipeline architecture cannot be used for the elementary SISO decoder. The architecture of our row-column parallel turbo decoder for one iteration is described in Figure 4. It is composed of two identical elementary SISO decoders and three memories of qn 2 symbols with double accesses.

This structure needs only one memory block per iteration. This enables the memory complexity be reduced by a factor of 8/3. Indeed, two memory blocks per iteration are necessary for the conventional cascaded architecture of a block turbo decoder. Moreover, the proposed parallel architecture is also interesting from a latency point of view. In this case, the architecture latency is equal to k*(n 2 +n), which enables the latency to be reduced by a factor of two.

Performance comparison: Bit-error performance of block turbo codes using extended BCH component codes with single error correction power after 8 iterations is given in Figure 4. We considered an AWGN channel and a system employing BPSK modulation. Simulation results are presented for three BCH components codes with the code lengths being 32, 64 or 128 bits.

The performance of the proposed row-column parallel turbo decoding is similar to that of conventional turbo decoding.

Conclusion:

In this letter, a row-column parallel architecture of a turbo decoder dedicated to product codes has been presented. Unlike the conventional BTC decoding approach, this architecture uses the more reliable extrinsic information at each step. This reduces the decoding latency by a factor of two, and the memory necessary for the block reconstruction between row decoding and column decoding is removed. It is clear that this innovative proposal provides an attractive solution from the complexity and decoding delay points of view. Simulation results revealed that there is no performance degradation for row-column parallel approach.

1 SISO decoder R' k R k D k F k W k W k+1 α k delay delay R k+1 β k Figure 2
Elementary SISO decoder

β 2k α 2k M atrix W 2k [qn 2 ] M atrix R 2k [qn 2 ] M atrix R 2k [qn 2 ] W 2k W 2k+1 memory block R 2k R 2k M atrix W 2k [qn 2 ] R 2k+1 W 2k
Elementary SISO decoder

β 2k+1 α 2k+1 M atrix W 2k+1 [qn 2 ] M atrix R 2k+1 [qn 2 ] M atrix R 2k+1 [qn 2 ] W 2k+1 W 2k+2 memory block R 2k+1 R 2k+1 M atrix W 2k+1 [qn 2 ] R 2k+2 W 2k+1

Figure captions : Fig. 1 Fig. 4

 :14 Figure captions:

Figure

  Figure 1

  Figure 3

Authors' affiliations:

C. Jégo and P. Adde (GET/ENST Bretagne, CNRS TAMCIC UMR 2872, Brest, France)


C Jégo

P Adde

C Leroux

Full-parallel architecture for turbo decoding of product codes

A full-parallel architecture for turbo decoding, which achieves ultra high data rates when using product codes as error correcting codes, is proposed. This architecture is able to decode product codes using binary BCH or m-ary Reed Solomon component codes. The major advantage of our architecture is that it enables the memory blocks between all half-iterations to be removed.

Moreover, the latency of the turbo decoder is strongly reduced. In fact, the proposed architecture opens the way to numerous applications such as optical transmission and data storage. In particular, our block turbo decoding architecture can support optical transmission at data rates above 10 Gb/s.

Introduction:

In recent years, turbo codes [START_REF] Berrou | Near Shannon limit error correcting coding and decoding : Turbo Codes[END_REF] have been adopted by several digital communication applications. In fact, they are particularly attractive to increase transmission rates and/or to guarantee the Quality of Service (QoS).

Currently, research is under way to use turbo codes to protect data stored on hard drive or DVD and in fiber optical transmission. The earliest FEC for optical communication [START_REF] Azadet | Equalization and FEC techniques for optical transceivers[END_REF] employed the well-known Reed-Solomon (RS) codes to recover the degradation in bit error rate (BER) due to the effects of fiber nonlinearity and polarization-dependent phenomena. A net coding gain of around 6 dB is provided by the RS(255,239) code. Very high-speed data transmission developed for fiber optical networking systems necessitate the implementation of ultra high-speed FEC architectures to meet the continuing demands for ever higher data rates. Currently, the RS(255, 239) code can be used in ultra high-speed (40 Gb/s [START_REF] Leilei | 10-and 40-Gb/s forward error correction devices for optical communications[END_REF] and 80 Gb/s [START_REF] Hanho | A high-speed low-complexity Reed-Solomon decoder for optical communications[END_REF]) fiber optic systems.

More powerful FECs as Block Turbo Codes (BTC) have a theoretical potential net coding gain of around 10 dB with a redundant overhead of less than 25 % [START_REF] Mizuochi | Recent Progress in Forward Error Correction for Optical Communication Systems[END_REF]. Typically, realistic block turbo codes can operate at less than 1 dB from the Shannon limit for a binary symmetric channel. In 2005, Mitsubishi Electric announced the development of the first block turbo decoder for 10 Gb/s optical transmission [START_REF] Tagami | A 3-bit soft-decision IC for powerful forward error correction in 10-Gb/s optical communication systems[END_REF].

Previous work: Many block turbo decoder architectures have been previously

designed. The classical approach involves decoding all the rows or all the columns of a matrix before the next half-iteration. When an application requires high-speed decoders, an architectural solution is to cascade SISO elementary decoders for each half-iteration. In this case, memory blocks are necessary between each half-iteration to store channel data and extrinsic information. Each memory block is composed of four memories of qn 2 symbols where q is the number of bits to quantify the matrix symbols. Thus, duplicating a SISO elementary decoder (e_dec) results in duplicating the memory block which is very costly in terms of area. In 2002, a new architecture for turbo decoding product codes was proposed [START_REF] Cuevas | New architecture for high data rate turbo decoding of product codes[END_REF]. The idea is to store several data at the same address and to perform parallel decoding to increase the data rate. However, it is necessary to process these data by row and by column. Let us consider m adjacent rows and m adjacent columns of the initial matrix. The m 2 data constitute a word of the new matrix that has m 2 times fewer addresses. This data organization does not require any particular memory architecture. The results obtained show that the turbo decoding is increased by m 2 when m elementary decoders processing m data simultaneously are used and its latency is divided by m. The area of the m elementary decoders (m-e_dec) is increased by m 2 /2 while the memory is constant.

Full-parallel turbo decoding principle:

The codewords of all rows (or all columns) of a matrix can be decoded in parallel. If the architecture is composed of n elementary decoders, an appropriate treatment of the matrix enables the elimination of the reconstruction of the matrix between each decoding. Let i and j be the indices of a row and a column of the n 2 matrix. In full-parallel processing, the row decoder i begins the codeword decoding by the symbol in the i th position. Moreover, each row decoder processes the codeword symbols by increasing the index by one modulo n. Similarly, the column decoder j begins the codeword decoding by the symbol in the j th position. Besides, each column decoder processes the codeword symbols by decreasing the index by one modulo n. Thus only one time cycle is necessary between two successive decoding the matrix. The full-parallel decoding of a n 2 product code matrix is detailed in Figure 1. A similar strategy was previously presented in [START_REF] Chi; Parhi | High speed VLSI architecture design for block turbo decoder[END_REF]. In this case, the conflicts of n independent RAM memories are eliminated by the appropriate treatment of the matrix. The elementary decoder latency can be defined as the symbol number processed by the decoder during the decoding of one symbol. This latency L depends on the structure of the elementary decoder and the n codeword length. As the reconstruction matrix is removed, the latency between row and column decoding is null.

Full-parallel turbo decoder for product codes: The major advantage of our full-parallel architecture is that it enables the memory block of 4qn 2 symbols between each half-iteration to be removed. But, the codeword symbols exchanged between the row and column decoders have to be switched. One solution is to use a connection network for this task. In our case, we have chosen an Omega network. The Omega network is one of several connection networks that are used in parallel machines [START_REF] Lawrie | Access and alignment of data in an array processor[END_REF]. It is composed of log 2 n stages, each having n/2 exchange elements. In fact, the Omega network complexity in terms of number of connections and of 2*2 switch transfer blocks is n*log 2 n and (n*log 2 n)/2 respectively. For example, the equivalent gate complexity of a 32x32 network can be estimated to be 200 per exchange bit. The proposed full-parallel architecture for product codes is presented in Figure 2. It is composed of cascaded modules for the block turbo decoder.

Each module is dedicated to one iteration. However, it is possible to process several iterations by a same module. In our approach, 2n elementary decoders and 2 connection networks are necessary for one module. In fact, the full-parallel turbo decoder complexity essentially depends on the complexity of the elementary decoder. In order to compare our architectural solution with the previous solutions, Table 1 gives the features of these architectures. The features depend on different parameters: symbol codeword n, decoding iteration it, elementary decoder throughput D ref , elementary decoder latency L, symbol quantization bits q and adjacent symbol group m.

The e_dec and m-e_dec architecture types correspond to the classical solution and the solution in [START_REF] Cuevas | New architecture for high data rate turbo decoding of product codes[END_REF] respectively.

Towards the implementation of architectures for ultra high rates: By using the full-parallel decoding principle, block turbo decoders using BCH component codes have been implemented. An architecture of BCH(32,26) 2 product codes with single correction power was synthesized. The decoding algorithm is chosen with q=4 quantization levels, 8 test vectors, 1 competitor and it=4 iterations. The elementary decoding of a codeword is split into three pipelined phases. Each phase requires 32/m clock periods and the elementary decoder latency is equal to 64/m clock periods. Syntheses were performed using the Synopsys tool with an STMicrolectronics 0.09-νm CMOS process target library. Two architecture types were chosen: e_dec as the reference and 4-e_dec where m=4 symbols are simultaneously processed by an elementary decoder. Elementary decoders have a clock period equal to 2 ns which corresponds to a frequency of 500 MHz. The estimated area complexity in terms of equivalent gates for the two elementary decoders are: 4400 for BCH(32,26) e_dec and 5700 for BCH(32,26) 4-e_dec. This complexity includes all the elementary decoder elements (processing and memorization).

The processing unit gate numbers of the block turbo decoders are equivalent between previous and proposed architectures: 1.13 and 1.45 millions for e_dec and 4-e_dec respectively. The latency is strongly reduced for the proposed architecture. It decreases from 270336 to 512 for e_dec and from 5120 to 128 for 4-e_dec. The memory complexity of the previous architecture in terms of equivalent gates is 126400. It corresponds to 10 percent of BCH(32,26) 2 block turbo decoder complexity. On the other hand, the equivalent gate complexity of connection networks is only 5600 for the proposed architecture of BCH(32,26) 2 block turbo decoder.

Conclusion:

A full-parallel turbo decoding architecture for product codes has been proposed. This architecture enables the memory blocks between all half-iterations to be removed. Moreover, the latency of the turbo decoder is strongly reduced. The ultra high-speed FEC architectures obtained meet the demands for ever-higher data rates. In particular, our architectural solution can support optical transmission at data rates above 10 Gb/s. In this context, using more powerful FEC as block turbo codes open up new opportunities for the next generation of optical communication systems.

Figure captions : Fig. 1

 :1 Figure captions:

Table 1 :

 1 Features of different architectures for block turbo decoding

	Figure 1
		one symbol (0,0)		n columns of n symbols j
		n rows of n
		symbols
			i
	index (i+1) = i + 1 mod n
	index (j+1) = j -1 mod n
	Figure 2
	elementary		elementary			elementary		elementary
	decoder		decoder for			decoder		decoder for
	for row 1 elementary decoder for row 2 elementary	connection network	column 1 elementary decoder for column 2 elementary	connection network	connection network	for row 1 elementary decoder for row 2 elementary	connection network	column 1 elementary decoder for column 2 elementary
	decoder		decoder for			decoder		decoder for
	for row n		column n			for row n		column n
	a module for one iteration

Table 1

 1

		Previous architectures	Proposed architectures
	latency (symbol number)	e_dec n*(2it*n 2 + 2it*L)	m-e_dec n/m*{2it*(n 2 /m 2 ) +2it*(L/m)}	e_dec 2it*L	m-e_dec 2it*(L/m)
	throughput (Gb/s)	n*(2it*D ref ) n/m*(m 2 *2it*D ref ) n*(2it*D ref ) n/m*(m 2 *2it*D ref )
	e_dec number	n*2it		n/m*(m*2it)	n*2it	n/m*(m*2it)
	memory size (Kb)	2it*4qn	2	2it*4qn	2	0	0
	connection network number	0		0		2it-1	2it-1