Philippe Benabes
email: philippe.benabes@supelec.fr

Sylvie Guessab
email: sylvie.guessab@supelec.fr

A Sigma-Delta Converter with Adjustable Tradeoff between Resolution and Consumption

This paper proposes an analog-to-digital converter with two working modes. In the first mode, the system is a sigma-delta passive converter: the analog modulator uses a passive switched-capacitor low-pass filter and the only active element is the comparator. The consumption is low and the resolution is moderate (9 bits). In the second mode, the expected resolution is 15 bits. For that, the passive sigma-delta modulator is put in a loop with a low-pass amplifier and some digital processing elements. The principle of this two-mode system is validated by functional simulations and by the test of a circuit realized in a 0.35µm CMOS technology.

I. INTRODUCTION

Passive sigma-delta (Σ∆) analog-to-digital modulators [START_REF] Chen | A 0.25 mW low-pass passive sigma-delta modulator with built-in mixer for a 10 Mhz IF Input[END_REF][START_REF] Song | A low power 1.1 MHz CMOS continuous-time delta-sigma modulator with active-passive loop filters[END_REF] are a very attractive way to build very-low consumption analog to digital (A/D) converters. In these modulators, the active low-pass filters which are generally used for sigmadelta conversion are replaced by passive ones. The only active element is a one-bit comparator working as an A/D converter.

The main advantage of such an approach is the very low consumption of the analog part of the converter. However, the resolution and the bandwidth are limited. For these reasons, the applications of passive sigma-delta conversion are essentially the monitoring of steady signals. It has to be noticed that the non-linearity error caused by the passive modulator is high and has to be digitally corrected, which means that the modulator has to be calibrated.

We are proposing in this paper a new conversion system which uses a passive sigma-delta modulator and has two possible working modes. In the "low consumption mode" (also named "passive mode"), the modulator is simply followed with a low-pass digital filter which also decimates the signal. The expected resolution is then 9 bits. In the "high resolution mode" (also named "active mode"), the modulator is inserted in a loop with an active low-pass filter and digital functions. The expected resolution is then 15 bits. The active mode can be used for example to calibrate the passive modulator.

In this paper, we are first presenting the principle of this two-mode topology (II) and some high-level simulation results (III). Then, the circuit realized to validate this principle and to investigate the limitations is described (IV). Finally, some measurement results are presented (V).

II. HIGH-LEVEL TOPOLOGIES

A. Passive modulator

The design of a passive low-pass discrete-time secondorder sigma-delta modulator has already been presented [START_REF] Benabes | Passive sigma-delta converters design[END_REF]. The architecture consists of a single loop (Fig. 1) and is calculated from the MSCL (Multi Stage Closed Loop [START_REF] Benabes | A Multistage Closed-Loop Sigma-Delta Modulator (MSCL)[END_REF]) architecture shown in Fig. 2. The transfer functions G j (z) should be integrators. Due to some physical limitations, they behave generally as low-pass active filters and can be written by using their Q-factor (which is the inverse of their cutoff frequency):

1 1 1 1 1 ) ( - - + - + = z Q Q z Q Q z G j j j j j (1)
As shown in [START_REF] Benabes | A Multistage Closed-Loop Sigma-Delta Modulator (MSCL)[END_REF], the MSCL architecture is equivalent to the single-loop architecture with F(z) given by formula (2): :

( ) ∏ = = - + = 2 1 1 ) ( 1 ) ( order j j j z G c z F
(2)

In our case, the loop filter is passive, therefore its gain must be equal to 0 dB for a null frequency. Formula (3) is adjusted to satisfy this requirement:

1 ) 1 ( 1 ) 1 1 1 1 ( ) (
Q c z Q Q z Q Q c z F  (3)
Formula (3) exhibits several degrees of freedom: coefficients Q j and coefficients c j . Some high-level simulations were performed to analyze their effect on the modulator performances (resolution, stability) and on the signal level at the comparator input. We showed [START_REF] Benabes | Passive sigma-delta converters design[END_REF] that a good compromise for a second-order structure can be found with:

c 1 = c 2 = 0.5, Q 1 = 10 et Q 2 = 50 (4)
With these values, the expected theoretical resolution for an over-sampling ratio of 100 is about 9 bits. The comparator input is about 10 mV, compatible with low-consumption electronics.

B. Active topology principle

The passive modulator causes a high non-linearity error when the input signal is far from the full scale mid-point. The principle of active topologies is to insert the modulator in a loop in order to keep its input signal closed to the midpoint. This principle is illustrated by Fig. 3. The analog part of the converter is composed with an active low-pass filter and the passive modulator. The digital part is composed with a digital low-pass filter, which also decimates the signal, a predictor and a D/A sigma-delta modulator. The predictor estimates the value of the input signal at the current time from the samples delivered by the digital filter. This predictor can be a simple integrator (with a gain lower than 1 in order to ensure the stability of the loop). After crossing the D/A modulator, the prediction is subtracted from the input signal. The active low-pass filter reduces the quantization noise introduced by the D/A Σ∆ modulator.

The delay introduced by the digital filter increases the response time of the closed loop. Consequently, this topology is well suited only for slow signals. In order to get a faster response time, a new digital processing is proposed (Fig. 4). The digital filter has been divided into two parts. The first part reduces the quantization noise without introducing a too large delay. Elements (E) and (F) are digital models of the analog part. They help increase the response speed and the bandwidth of the converter. They should be matched with the analog part as well as possible.

A. Linearity and resolution

Some transient simulations with a static input signal were performed in order to evaluate the expected linearity and resolution. Two converter configurations were compared:

in passive mode : passive modulator followed with digital filters 1 and 2 (A and B in Fig. 4) ; in active mode : active fast topology as shown in Fig. 4 ; for the active filter, the gain g is taken equal to 8 and α to 40 ; digital parts E and F are supposed fully matched to analog ones (G and H) ; the predictor (C) is a linear interpolator. In both cases, the over-sampling ratio is equal to 256 and the sampling frequency is 8 MHz. Fig. 5 shows the converter output as a function of time in passive and active modes. The DC input signal is taken equal to -0.5 (the full scale here is normalized between -1 and 1). The mean output value in passive mode is -0.4972 (non-linearity errordifference between the input value and the output mean valueequivalent to a resolution of 9.5 bits) whereas it is -0.49998 in active mode (non-linearity error equivalent to a resolution of 16.6 bits). Besides, the precision can be calculated from the residual noise at the output and expressed in bits. It is about 12.3 bits in passive mode and 15.5 bits in active mode. The linearity is enhanced by 7 bits in active mode and the precision by 3 bits.

IV. CIRCUIT AND PHYSICAL DESIGN

A prototype circuit was realized in order to validate the principle of the two-mode topologies and to investigate the limitations.

The digital part (A to F in Fig. 4) was defined as a HDL code and implemented in an Altera board whereas the analog parts (G and H) were integrated in the AMS 0.35µm technology. The chip is composed with: the comparator ; the passive switched-capacitor filter ; the active switched-capacitor filter ; the V DD /2 reference generators (virtual ground) where V DD is the supply voltage ; a digital part using standard cells (essentially switches command). The comparator, the passive filter and the reference generators were presented in the article [START_REF] Guessab | A passive delta-sigma modulator for low-power applications[END_REF]. As far as the active filter is concerned, regarding our objectives (validation and investigation), the choice criterion was simplicity. Consequently, the circuit (Fig. 8) is single-ended and there is only one capacitor at the input. The transfer function is:

( ) 1 3 1 1 3 2 1 1 ) ( 2 1 - - - - - = - z C C z C C V V V e e S ( 5
)
V e1 is the input signal to convert and V e2 is the feedback signal (delivered by the digital sigma-delta modulator). As V e2 is a binary signal, this input is connected to the ground or to the V DD supply by adequate switches. The signal reference (represented by a virtual ground in Fig. 8) is V DD /2. It is produced by a switched-capacitor voltage divider. This amplifier can be bypassed when the passive mode is used. In this case, the biasing sources of the operational amplifier are switched off, in order to reduce the global consumption.

The chip layout is shown in Fig. 9. All the components are duplicated for test purpose.

A. Linearity

The tested configurations are the same than the ones described in III.A. The supply voltage is 3.3 V. The measurement precision of the input voltage is about 0.1%. In active mode, the digital parts (E and F) are calibrated so that they are fully matched with the analog parts (G and H). Fig. 10 gives the non-linearity error as a function of the DC input value (normalized between 0 and 1) in passive and active (fast topology) modes. Offset and gain error have already been compensated. In passive mode, the nonlinearity error is below 1.5×10 -3 in the range [0.1 ; 0.9], which corresponds to an equivalent resolution of 9.3 bits. In active mode, it is below 4×10

-4 in the range [0.1 ; 0.7] which corresponds to an equivalent resolution of 11.3 bits. The non-linearity increases drastically above 0.7. Thus, the linearity is the one expected in passive mode, but it is far lower than expected in active mode. Besides, the conversion is not rail-to-rail. Further high-level and transistor simulations, which are not presented here, have demonstrated that this is due to the active filter: its commonmode rejection is not high enough (about 32 dB) and the common-mode gain is deeply non-linear.

B. Precision

The precision is calculated from the residual noise at the output for a DC input. It is 9.6 bits in passive mode and 12.3 bits in active fast mode. Thus, in passive mode, it is lower than expected with high level simulations (9.5 bits measured instead of 12.3 bits expected). The reasons are:

-charge injection effects ;

-sensitivity to digital noise in the analogue part (due to the low amplitude of the comparator input) There are 2.5 bits of difference between the active and the passive modes (3 bits were expected).

C. Bandwidth

The measured bandwidth in active fast mode is about 15 kHz, which is compatible with audio applications.

D. Consumption

The measured consumption for F s = 1MHz is 1.4 µA for the passive modulator and 173 µA for the input active filter. The consumption of the digital part on the Altera board can not be measured.

VI. CONCLUSION

This paper proposes a new conversion system based on passive sigma-delta modulation, which offers two working modes: the "low consumption" (passive) mode and the "high resolution" (active) mode. Measurements validate the principle demonstrated at the functional level and point out some limitations. The experimental resolution is 8 bits in passive mode (passive modulator followed by a digital filter) with the use of a digital post-correction. The measured analogue consumption is lower than 2µA at a 1 MHz data rate. In active mode, the modulator is inserted in a loop composed with an active filter and some digital functions. The resolution should theoretically be increased by 6 bits but it is only by 2.7 bits experimentally. This could be enhanced by redesigning the active filter (use of full differential circuits and bottom-plate technique). We are investigating through high-level simulations the effect of the predictor and active filter parameters, and of the mismatch between digital models and their analogue counterparts.

Figure 1 .Figure 2 .

 12 Figure 1. Sigma-delta single-loop modulator

Figure 3 .

 3 Figure 3. Active simple topology

Figure 4 .

 4 Figure 4. Active fast topology

Figure 5 .

 5 Figure 5. Converter transient response for a static input equal to -0.5 Fig. 6 shows the non-linearity error as a function of the DC input value. The input signal is rescaled between -1 and 1. Fig. 6(a) is obtained after a first-order gain correction. It can be clearly seen that the modulator is highly non-linear for the extreme input values. Fig. 6(b) demonstrates the benefit of the active topology. It is obtained without any post-correction. We get a theoretical rail-to-rail conversion with a very linear DC transfer function: the non-linearity error is kept below 2×10 -5 on the whole input range (equivalent to a resolution of 16.6 bits). The quantization noise becomes the predominant error source.

Figure 6 .

 6 Figure 6. Non-linearity error in passive and active modesB. BandwidthSome simulations were performed with sinus input signals in order to compare the bandwidth of the simple and fast active topologies. Fig.7shows the transient response of the simple topology when the input frequency is 20kHz and the sampling frequency is 10MHz. The gain is below 0.3. The same simulation with the fast active topology gives a gain above 0.8.

Figure 7 .

 7 Figure 7. Transient simulation with a sinus input signal (f input = 20kHz ; f sampling = 10MHz)

Figure 8 .

 8 Figure 8. Switched-capacitor active filter

  Figure 9. Chip layout

1 Figure 10 .

 110 Figure 10. Non-linearity measurement

VII. ACKNOWLEDGEMENTS

This research work was supported by grants from Texas Instruments Inc.


Henri Sohier

Sahar Guermazi
email: s.guermazi@sherpa-eng.com

Mouadh Yagoubi

Pascal Lamothe
email: pascal.lamothe@mpsa.com

Aldo Maddaloni
email: aldo.maddaloni@renault.com

Pascal Menegazzi
email: pascal.menegazzi@valeo.com

Yining Huang

A Tooled Methodology for the System Architect's Needs in Simulation with Autonomous Driving Application

Keywords: MBSE, SysML, System architect, Solicitation, Simulation architect, Model Identity Card

Model Based Systems Engineering (MBSE) is a promising solution to formalize and communicate information about the design of complex systems, in particular for the automotive industry which faces new challenges associated to autonomous driving. Numerical simulation is commonly used to support the design of these complex systems, but the possible relations with MBSE should be further investigated. This work, conducted with academic and industrial partners at the research institute IRT SystemX, aims at further bridging the gap between system architecture and numerical simulation. An industrial design problem related to the design of an autonomous vehicle passing traffic lights is used to validate and illustrate new methods and tools based on SysML. Their aim is to: 1) guide the formulation of a question requiring simulation, called solicitation, by the system architect 2) guide the design of a simulation architecture by the simulation architect with a special focus on the consistency with the system. A Java plugin was developed in the SysML editor Papyrus for the solicitation, and a SysML metamodel was defined for the simulation architecture. The solicitation associated to the industrial design problem is answered by a multiobjective optimization of the vehicle's cost and electrical consumption using a co-simulation between the tools Simulink and Amesim.

I. INTRODUCTION

A. Context

The research institute IRT SystemX gathers industrial and academic partners to complete projects which generally last three to four years. One of the main objectives of the project AMC is to bridge the gap between systems engineering on one hand and complex simulations on the other hand by defining a step-by-step methodology supported by new software functions. Simulation is considered itself a potential complex system which can have a different topology from the original system it represents, especially because of the implementation of physics phenomena. It also includes different specifications from the system, typically regarding the accuracy or the speed of the simulation models. In this case, the role of simulation architect, which has recently emerged ( [START_REF] Retho | Collaborative methodology for virtual product building to support aerial vehicles with electrical propulsion design[END_REF]), seems to be necessary to specify the simulation. As shown in Fig. 1, the left branch of the idealized system V-model can lead to multiple needs in terms of simulation, at any step. A simulation architect can answer these needs by designing and integrating the simulations which will provide the results necessary for the system, following idealized simulation V-models. The industrial partners involved on this topic in the project AMC include large companies from the automotive and aeronautics industry (PSA Groupe, Renault, Valeo, Airbus) as well as software developers and service providers (Sherpa Engineering, Digital Product Simulation, Siemens). In the project AMC, a practical design problem allows the different partners first to identify the issues and lacks in the current design processes, and then to test possible solutions. This design problem concerns the early design of an autonomous vehicle which can pass traffic lights. It is presented in section II and then used to illustrate each proposition.

Stakeholder needs Final system

Needs in terms of simulation Fig. 1. Use of the simulation in a system V-model.

B. Today's role of systems engineering and simulation

Companies show a growing interest for systems engineering which aims at formalizing the multidisciplinary design of complex systems offering multiple services to the user. It is especially true in the automotive industry where new services gradually improve the autonomous driving capacity of the cars, from parking to lane keeping or platooning. Autonomous driving sheds light on the control systems which have been historically designed with systems engineering-like approaches ( [START_REF] Forrai | Embedded Control System Design: A Model Based Approach[END_REF]). In the general landscape of systems engineering, Model-Based Systems Engineering (MBSE) appears as particularly promising. In a model, diagrams are easier to formalize than text, and they are an efficient way to communicate. MBSE is under maturation and efforts are now underway to offer userfriendly tools, a clear design methodology, and a modeling language at the right level of complexity. Regarding the tools, the SysML editor Papyrus has an open-source code which forms a great basis for new developments ( [START_REF] Bordeleau | Model-based engineering: A new era based on Papyrus and open source tooling[END_REF]) in spite of a relatively complex interface and certain bugs. Some commercial tools like MagicDraw have customers in the automotive industry like the car manufacturer Renault ([4]). New tools or new plugins are also made available by startup companies whose funders often have experience in the automotive industry ( [START_REF]CIL4Sys Engineering[END_REF], [START_REF]Syscience[END_REF]). However, the MBSE tools are generally still not the design backbone they could be. Regarding the methodology, different approaches exist and some of them are gaining in importance, often by means of courses and certifications ( [START_REF]Architecture and systems engineering[END_REF], [START_REF] Cesames | Formation d'introduction à l'architecture[END_REF]), some of which are specifically addressed to the employees of car manufacturers like PSA Groupe ( [START_REF] Cesames | Formation d'introduction à l'architecture[END_REF]). Some approaches aim at partially automatizing the design process through the reuse of functions and components ( [START_REF] Yang | MBSE approach adapted to vehicle energy consumption optimization[END_REF]). Finally, regarding the language, SysML can be considered as relatively hard to use, which can lead to a new organizational silo in the company. However, SysML is a well-known, rich standard which is often taken as a reference or as a source of inspiration, like for the language used in the tool Capella ( [START_REF] Roques | MBSE with the ARCADIA method and the Capella tool[END_REF]).

Although still relatively independent from systems engineering, simulation is now a common tool in most companies. The simulation development and the system development can be carried out by the same experts, but large companies can distinguish these tasks. PSA Groupe organized the simulation in groups adapted to different physics, from vibration to combustion and electricity, but also to computing issues such as optimization, uncertainties and model reduction. The resulting simulations are sometimes labeled as "functional", "multibody", or "finite elements" ( [START_REF] Psa Groupe | Challenges et enjeux de la simulation numérique[END_REF]). Renault started a division called "Model Factory" with hundred people in France, India and Korea dedicated to the simulation ( [START_REF]Chef d'équipe Model Factory[END_REF]). The representativeness of the simulation, i.e. its likeness with the system it represents, is still often hard to quantify and can limit some decisions. In spite of its limits, the use of simulation is expected to grow with the development of autonomous vehicles. Indeed, the validation of their reliability may need billions miles of driving ( [START_REF] Kalra | Driving to safety: How many miles of driving would it take to demonstrate autonomous vehicle reliability?[END_REF]) which could be partially virtualized.

C. Gap between systems engineering and simulation

In systems engineering, some of the questions raised by the design process can be answered thanks to simulation. The link between systems engineering and simulation is sometimes very direct, like in the tool STIMULUS ( [START_REF] Argosim | STIMULUS for requirements[END_REF]) where formal textual requirements and state diagrams can be tested thanks to random variables, or like in the tool CIL4Sys ( [START_REF]CIL4Sys Engineering[END_REF]) where formal sequence and state diagrams typically representing control laws can be tested thanks to on-the-shelf or simple plant simulation models and user-defined environments. However, finer and more complex simulation models can be required for a better representation of the effects of control laws, or to test a physical solution. In this case, it becomes more difficult to mix the system and the simulation as they generally start to involve different people and have different topologies. Furthermore, while experts in control have the ability to make the necessary formal diagrams, MBSE can be considered as semi-formal or even informal ( [START_REF] Rauzy | Five theses for model-based systems engineering and modelbased safety assessment[END_REF]), which limits such automations.

Thus, the design process can raise questions which can only be answered by simulation experts. There is currently little help to identify the information to communicate to these experts as well as the format to use. How to describe the system or the part of the system to simulate, the level of detail, the environment scenarios, or the simulation objectives? MBSE, which facilitates the communication of system specifications, should be used as a basis to formulate the questions about the system. New methodology, metadata and tool based on SysML are first presented in the section III dedicated to the solicitation from the system architect.

This solicitation represents the simulation needs. It is used to design the simulation means respecting the desired quality, cost, and delivery. The corresponding architecture tasks are considered to be carried out by a simulation architect. For example, the simulation architect has to find existing simulation models as well as pre-and post-processing functions in a cross-disciplinary approach given the expected accuracy or the costs of acquisition and execution. He also has to specify the missing simulation models and functions, and to check whether the simulation models correctly represent the system. New methodology and metadata guiding the architecture of the simulation are presented in section IV.

Thus, the simulation architecture is distinguished from the system architecture. This separation appears in [START_REF] Huang | System and simulation modeling using SysML[END_REF] which refers to a "domain model" describing the system and to an "analysis model" describing the simulation, with blockto-block relations. However, these relations are mainly based on a generic simulation block and cannot alone show the complexity of the simulation architecture. In many works, simulation is seen as an enriched version of the system and the distinction between the system and the simulation is more tenuous. In [START_REF] Cao | SysML-based uniform behavior modeling and automated mapping of design and simulation model for complex mechatronics[END_REF], the simulation includes a system and simulation parameters. In [START_REF] Peak | Simulation-based design using SysML -Part 1: A parametrics primer[END_REF] and [START_REF]Simulation-based design using SysML -Part 2: Celebrating diversity by example[END_REF], the simulation is based on blocks called "Analyzable Product Models" dedicated to design properties and on blocks called "Analysis Building Blocks" dedicated to generic equations like physical laws.

In several works, a SysML architecture is converted into a runable format, like in [START_REF]ModelCenter MBSEPak[END_REF] which focuses on parametric diagrams, or in [START_REF] Paredis | Using OMG's SysML to support simulation[END_REF] and [START_REF] Renier | De SysML à Modelica : Aide à la formalisation de modèles de simulation en conception préliminaire[END_REF]. Depending on the approach, additional modeling can be required in the runable format.

The remainder of this paper is organized as follows. The industrial design problem of the project AMC is first presented in section II; New methodology, metadata and tool for the solicitation from the system architect for a new simulation are then presented in section III; New methodology, metadata and tool specification for the design of a new simulation architecture answering the needs of the system architect are presented in section IV; Finally, the simulation obtained for the industrial design problem and its results are presented in section V.

II. INDUSTRIAL DESIGN PROBLEM

The industrial design problem used in the project and in this paper is related to the design of an autonomous vehicle passing traffic lights. A SysML model has first been developed with the tool PhiSystem based on Papyrus and provided by the partner Sherpa. It represents the complete car, with a special focus on the ability to pass traffic lights. The process followed is a synthesis of the different partners' approaches in systems engineering.

As represented in Fig. 2, the stakeholders are first identified, from marketing to logistics or regulations. The needs in terms of function, performance or constrain are then reviewed for each stakeholder. For example, the marketing requires to have an electrical consumption and a noise below certain thresholds. The needs are finally organized in services, like "autonomous driving", "acoustics" and "energy". The system design is then carried out at three different levels. First, in the operational level, the system is described for each service as a black box. The use cases permit to list for each service the systems expected capacities, like "staying on a lane", "passing the traffic lights" or "following a car". For each use case, the necessary exchanges between the system and the environment actors are defined in operational sequence diagrams. Operational activity diagrams help to specify the behavior of the system between these exchanges. Each operational sequence diagram is associated to a single operational state like "active", "non active" or "fault". All the operational states are summarized in an operational state diagram.

The operational sequence diagrams, where the system is a black box, are then transformed into functional sequence diagrams where the system is divided into functions like "Control the vehicle" or "Provide power". Likewise, each function can then be divided into sub-functions in more functional sequence diagrams. All the functions, sub-functions and functional exchanges interconnecting them are summarized in a multi-layer internal block diagram. The first layer is represented in Fig. 3. Functional activity diagrams can specify the behavior of the functions used in the functional sequence diagrams. Fig. 4 shows an activity diagram for the control function. If there is a traffic light within a certain range, the control function can output three different commands: 1) In "Speed envelop", the vehicle goes at the maximum safe speed 2) In "Pass", the vehicle keeps its current speed to pass the traffic light 3) In "Stop", the vehicle breaks to stop. The "time to light" is the ratio of the distance between the vehicle and the traffic light, to the current speed of the vehicle. Two properties can be tuned: 1) the range from which the traffic light starts to be taken into account 2) the shape of the speed envelop, defined by the maximum acceptable deceleration. These control properties affect the electrical consumption of the vehicle. The last layer of sub-functions is finally allocated to components like "Controller" or "Powertrain" which are also represented in a multi-layer internal block diagram. The detection of the traffic light is carried out by a component called "Sensor". One of its properties represents the uncertain distance from which the traffic light is detected. The better this property is, the more expensive the sensor is. The properties of the functions and components can be associated to requirements. Fig. 5 represents a simplified version of the data model of the system architecture. In this context, it is considered that the system architect is looking for the best control properties and the best sensor properties to minimize both the cost and the electrical consumption when passing traffic lights.

III. SOLICITATION FROM THE SYSTEM ARCHITECT

The solicitation from the system architect is a documented question. It describes the needs in terms of simulation, independently from any choice in terms of simulations means. Thus, the system architect does not handle simulation models. In the design problem considered, the solicitation is the documented question regarding the choice of control and sensor properties to minimize both the cost and the electrical consumption when passing traffic lights.

A. Filtered system architecture

If a question raises during the development of a system, the system architect can formalize it thanks to the model-based system architecture. Indeed, it precisely aims at facilitating the communication of the system specifications which should be used for the development of the simulation. However, the system architect should not communicate the whole system architecture every time a question raises. For example, the system architect should not communicate information about the color of the windows control buttons if he wants a fast answer regarding the electrical consumption of the vehicle when passing traffic lights. Similarly, the system architect should not communicate precise details about the sensor design if he wants a general simulation which does not take them into account. The system architect has the global understanding of the system which is required for such filtering, and he can limit the information before it is shared with the simulation developers.

The system architect needs a methodology and a tool to filter the information. The tool is prototyped as a Java plugin in PhiSystem and Papyrus. The following paragraphs focus on the tool and its graphical interface as they validate the underlying methodology and permit to understand it from a user point of view. As shown in Fig. 6, a menu "Solicitation for simulation" is added to the top bar. A sub-menu first permits to copy the system architecture. This copy is an opportunity to select a specific version and configuration of the system, and to later modify or simplify some specifications of the system in the simulation. Thus, it is way to acknowledge possible differences between the designed system and the simulated system, typically when it is too expensive to modify existing simulations. However, it also complicates configuration management. After the copy, the system architect must define the perimeter and the level of detail he expects in the simulation. An important proposition is to select the elements to be simulated following steps similar to the design process. The operational level is first used to define the perimeter of the simulation, and the functional level is then used to define the level of detail of the simulation. The copied use case diagram can be opened thanks to the submenu "Operational level / Use case diagram". As shown in Fig. 7, the use cases can be selected or unselected with a right-click menu (the figure has been edited to hide non-related menus). When a use case is selected, like "to pass a traffic light", the selection is extended to all the use-cases it includes and all the use cases which include it. When a use case is unselected, the unselection is extended to all the use cases it includes, except if they are included in other selected use cases. The selected use cases appear in orange.

The tool directly looks for the related operational sequence diagrams. These sequence diagrams and a summary of these sequence diagrams can be opened with "Operational level" submenus. They allow the system architect to narrow the simulation perimeter by unselecting exchanges between the system and its environment. The summary is a table in a popup window where it is possible to unselect an individual message, all the messages of a diagram, or all the messages related to an element of the environment in all the diagrams. The next "Operational level" submenu shows the environment involved in the simulation, and the following one shows the states involved in the simulation (Fig. 8). When the user clicks on the submenu "Functional level / Sequence diagrams", the tool looks for and open the related functional sequence diagrams. The exchanges shown in these diagrams are selected for the simulation, except those which appear in the operational level and which have been unselected. The next "Functional level" submenu shows the functions hierarchy in a Block Definition Diagram (BDD). As shown in Fig. 9, a right click on a selected function permits to ignore its subfunctions and lower the level of detail of the simulation. For example, it is possible to ignore that the function "Navigate", corresponding to the sensors, has been designed with subfunctions such as "Acquire the shapes", "Acquire the motions" or "Merge the information". Finally, the last "Functional level" submenu shows the internal block diagram with the functions selected for the simulation.

The submenu "Requirements" opens a popup window which shows the requirements associated to all the functions and components properties. It first highlights the requirements directly coming from the needs of the stakeholders, like the electrical consumption of the car. It also highlights the requirements which arose during the design of the system and which still have to be associated to specific numerical values. The requirements from the needs represent the constraints of the problem, and the requirements with no specific numerical values represent the unknowns. It is possible to unselect the requirements from the needs of specific services like "acoustics" if they are out of the simulation's scope.

Finally, the submenu "Filter out" deletes all the elements which have not been selected for the simulation. This deletion is done in the copy of the system architecture and keeps the original system architecture unchanged.

B. Resulting question

The filtered requirements help to formulate the question as they show the values which still have to be set, like the control and sensor properties, as well as the values constrained by stakeholder needs, like the cost or the electrical consumption. Thus, the system architect can easily ask for an optimization of the control and sensor properties to minimize the cost and electrical consumption. The related software functions will be part of a later article.

C. Environment scenarios to be tested

By definition, the environment, which is not under control, is associated to uncertainty. For example, the system architecture specifies how the system behaves if it faces a traffic light, but the traffic light is only a hypothetical event. Many uncertainties are implicit, like the location of the traffic lights. In a simulation, these uncertainties can either be defined in an explicit form, or be reduced to specific values in order to keep the number of simulation runs under an acceptable threshold. For example, the simulation can be done with a traffic light at exactly 500 meters.

The definition of the environmental scenarios is progressively refined, from the general point of view of the system architect which can choose a traffic light at 500 meters along a straight road, to the more accurate points of view of the simulation architect and experts. The related software functions will be part of a later article.

IV. SIMULATION ARCHITECTURE

The solicitation from the system architect is handled by a simulation architect. The simulation architect has a role similar to the system architect, but instead of specifying components to answer customer needs, he specifies simulation models and software functions to answer the solicitation from the system architect. It is chosen to describe the simulation models with the properties of the "Model Identity Card" (MIC) which was initially defined in a PhD thesis at Renault in interaction with IRT SystemX ( [START_REF] Sirin | Supporting multidisciplinary vehicle modeling: towards an ontology-based knowledge sharing in collaborative model based systems engineering environment[END_REF]). The MIC and FMI/FMU ( [START_REF] Blochwitz | The functional mockup interface for tool independent exchange of simulation models[END_REF]) have some properties in common, but the MIC aims at specifying or describing a simulation model rather than executing it. Thus, [START_REF] Fontaine | Modélisation théorique et processus associés pour architectes modèle dans un environnement multidisciplinaire[END_REF] presents a software function converting a MIC into an empty Modelica model, but this model then needs to be filled with equations in order to be executed.

It is also chosen to represent the simulation models with SysML blocks. These blocks are associated to the MIC properties through a stereotype defined in the profile diagram of Fig. 10. Working in a SysML environment makes it convenient to map the simulation to the system it represents, with two major benefits. First, if a library archives the systems represented in the past simulations, it is possible to identify those similar to the solicitation, and re-use the corresponding simulation models. Second, it permits to validate the correct representation of the system in the simulation. As shown in the data model of Fig. 11, it is chosen to map: 1) the simulation model to the system function it represents 2) the ports and variables. A simulation model can be directly mapped to a system component fulfilling different functions.

When a simulation model exists, the information describing the simulation model is gathered in a "capitalization MIC". When an existing simulation model can be re-used after som e modifications to solve some inconsistencies with the solicitation, the simulation architect can change the "capitalization MIC" into a "negotiation MIC" to specify these modifications. Fig. 12 shows an example of negotiation MIC for an existing simulation model (on the right) based on the mapping with a system function (on the left) related to the vehicle's control. In the simulation model, the ports in white are consistent with the system function,the ports in grey are not, and the ports in red are specifications of new ports replacing the ports in grey. Thus, the port "Sensor", which was covering very different ports of the system function, is split into two.

The simulation architect can finally specify a new model, to be developed from scratch, in a "specification MIC". The interface of the specification MIC, and in particular its ports, can be generated from the function (or component) it represents in the solicitation.

All the simulation models are integrated in an internal block diagram, whether they are associated to a capitalization, a negotiation, or a specification MIC. The resulting architecture of MICs, illustrated in Fig. 13, represent the system and the environment defined in the solicitation. The MIC architecture has global inputs and outputs. In the problem of the autonomous vehicle passing traffic lights, the global inputs are the control and sensor properties to be optimized, as well as the environment properties to be changed in the different scenarios. The global outputs, which typically are functions of time, include the state of charge of the battery and the position of the vehicle which permit together to calculate the electrical consumption of the vehicle.

The architecture of MICs is completed by pre and posttreatment as well as non-physical black boxes, like an economic model outputting a cost, to finally form the simulation architecture represented in Fig. 14. Indeed, the architecture of MICs cannot reach alone the objective set by the system architect, i.e. optimizing the control and sensor properties to minimize the cost and electrical consumption. Each block of the simulation architecture is allocated to software resources (such as Amesim or Simulink), and each software resource is allocated to hardware resources (such as a computer or a server), thus leading to a three-level representation of the simulation. It is for example possible to check that the resources respect the implementation constrains described in each MIC (e.g. regarding the version of Simulink to use), and to estimate the cost and performance of these resources. The different tasks described in this section will be supported by new software functions for the simulation architect. V. NUMERICAL SIMULATION After the design of the simulation architecture by the simulation architect, the missing models are developed by the experts of different simulation areas. The simulation models are then integrated and the simulation is executed. In the industrial design problem, the functions to sense and control are simulated using Matlab-Simulink, while the powertrain and the vehicle energetics are simulated using a library of Amesim. Matlab-Simulink and Amesim are integrated in a co-simulation illustrated in Fig. 15. This co-simulation is called at each iteration of the optimization process to evaluate candidate solutions. We consider a multiobjective optimizer as we aim at minimizing two conflictual objectives, namely: the cost and the electrical consumption averaged over multiple traffic lights. Among several state-of-the-art algorithms, we choose the NSGA-II (Non dominated Sorting Genetic Algorithm [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF]) which is one of the most popular and widely used algorithms in the field of evolutionary multiobjective optimization. Experiments were conducted using the following settings. Four design parameters were considered. The first two are related to the control and were presented in section II : the distance from which the traffic light starts to be taken into account, and the maximum acceptable deceleration. The two others permit to describe the uncertain distance from which the traffic light is detected: the detection mode and the scale of a Gumbel probabilistic law. The population size was set to fifty. The optimization was stopped after fifty iterations. After running the optimization, the simulation architect provides post-treated results to the system architect in order to take decisions. In our example, the returned results are represented by a Pareto front that illustrates the trade-off between optimal solutions (see Fig.

VI. CONCLUSION

This work further bridges the gap between system architecture and simulation. Two tasks carried out by two different roles are clearly distinguished. First, the system architect formulates a solicitation for a simulation by using the part of the system architecture associated to specific use cases. A Java plugin has been implemented in a SysML editor based on Papyrus to allow the system architect to define the perimeter and the level of detail of the simulation, sparing him from the tedious processing of SysML data. The definition of a question based on the system requirements and the choice of an environment scenario have been explored and will also be facilitated by the plugin in the future. The second task considered in this work is the design of a simulation architecture by a simulation architect. A methodology supported by a metamodel has been developed to specify the connections between the simulation models, to identify their relations with the systems functions and components, and to solve any inconsistency coming from the re-use of former simulation models or from the lack of communication between the system architect and the simulation experts. The solutions presented in this work have been defined and validated thanks to the industrial design problem of an autonomous vehicle passing traffic lights. These solutions facilitate Agile project management by permitting frequent simulation loops and by improving the capitalization and re-use of simulation models. They will be combined with additional software developments whose objective is to improve the decision of the architects, when looking for former simulation models or when reviewing the simulation results for example.

Fig. 2 .

 2 Fig. 2. Stakeholders of the considered industrial design problem.

Fig. 3 .

 3 Fig. 3. Internal block diagram at the functional level.

Fig. 5 .

 5 Fig. 5. Simplified data model of the system architecture.

Fig. 6 .

 6 Fig. 6. Menus added to the top bar in PhiSystem.

Fig. 7 .

 7 Fig. 7. Selection of use cases.

Fig. 8 .

 8 Fig. 8. Representation of the selected states.

Fig. 9 .

 9 Fig. 9. Unselection of subfunctions in the BDD.

Fig. 10 .

 10 Fig. 10. The profile used for the MIC in PhiSystem.

Fig. 11 .

 11 Fig. 11. The MIC data model.

Fig. 12 .

 12 Fig. 12. Mapping of a function to a MIC in PhiSystem.

Fig. 13 .

 13 Fig. 13. Architecture of MICs for the system and environment.

Fig. 14 .

 14 Fig. 14. Top-level view of the simulation architecture.

Fig. 15 .

 15 Fig. 15. Simulink view of the co-simulation (with Amesim).

16

 16

  .

  )

Fig. 16 .

 16 Fig. 16. Optimization results : Pareto Front.


Ali Beydoun
email: ali.beydoun@supelec.fr

Philippe Benabes
email: philippe.benabes@supelec.fr

BANDPASS / WIDEBAND ADC ARCHITECTURE USING PARALLEL DELTA SIGMA MODULATORS

This paper presents a new method for digitizing wideband signals. It is based on the use of parallel analog delta sigma modulators, where each modulator converts a part of the input signal band. A major benefit of the architecture is that it widens the conversion band of the input signal and increases its dynamic range. Two solutions are proposed to reconstruct the signal: the first one uses bandpass filters without demodulation and the second demodulates the signal of each modulator, and then processes it in a lowpass filter. This paper focuses essentially on the digital part of the system and the overall performances are compared by using simulation results.

INTRODUCTION

The current trend in telecommunication is high data rates, versatility and interoperability between digital mobile systems. Most of these systems are designed in a way that puts the digital processing as close to the antenna end of the receiver as possible in order to obtain a more robust system. This is due to the fact that a direct digitization of the Radio Frequency (RF) signal simplifies processing tasks like channel filtering and demodulation. In order to evolve in that direction, many problems must be handled such as: enlarging the frequency bandwidth of the analog to digital converter and improving technology efficiency (for instance using parallelism technology).

Recently, several solutions such as Time Interleaved Delta Sigma (T I∆Σ) [START_REF] Eshraghi | A time-interleaved parallel ∆Σ A/D converter[END_REF] [2] [START_REF] Eshraghi | High-Speed Parallel Delta-Sigma Analog-TO-Digital Converters[END_REF], Parallel Delta Sigma (Π∆Σ) [START_REF] Galton | Delta-sigma modulator based A/D conversion without oversampling[END_REF] and Frequency Band Decomposition (FBD) [START_REF] Aziz | Multiband sigma-delta modulation[END_REF] [START_REF] Aziz | Multiband sigma-delta analog to digital conversion[END_REF] have been proposed to widen the band of operation of the converters using discrete-time delta sigma modulators for their higher accuracy. These architectures are all based on the implementation of parallel delta sigma modulators but have two main drawbacks: first, the whole frequency band between 0 and f S /2 is converted, f S being the sampling frequency, instead of the limited useful signal band. Moreover an increase in resolution implies an increase in the number of modulators and therefore a larger silicium area.

Finding a proper solution for this problem is the main goal of our method. Our architecture is able to convert a band-limited signal by using N parallel analog bandpass modulators, each of which processes an equal share of the useful signal band, as shown in Figure 1. By limiting the processing to the useful band, the resolution will be improved compared to the previous method using the same number of modulators. This combination of modulators must be followed by a digital system to reconstruct the signal with a transfer function as close as possible to a simple delay (minimum in-band ripple and linear phase). The remaining problem is the digital reconstruction of the input signal. In this paper, we consider that the characteristics of the modulators are known and we try to evaluate the computing power needed for this reconstruction. Even though, this processing cannot be achieved in real time today, this should become possible using near future technologies. We choose to separate phase issues in the transition zone between adjacent modulators from amplitude issues related to the Signal Transfer Function (STF) of each modulator and the quantization noise. An example with eight third order modulators will be given to illustrate the proposed architecture.

ARCHITECTURE

In order to widen the converter's band and increase the resolution, one may use parallel delta sigma modulators as in the architecture represented in Figure 2. In this case, the Oversampling Ratio (OSR) of each modulator is equal to the global OSR multiplied by N. The input signal is processed simultaneously by multiple analog delta sigma modulators as shown in part A. The outputs from all the channels are then recombined by a digital system (part B) in order to reconstruct the signal.

Analog modulators

Continuous-time modulators (Figure 2, part A) are used to overcome difficulties related to the frequency limitations of the discrete-time integrators that are built with switched capacitor circuits [START_REF] Benabes | A methodology for designing continuous-time sigma-delta modulators[END_REF]. These modulators are uniformly dis-

Digital reconstruction

For reconstructing the signal, two conditions must be met by the digital system :

• A minimum global quantization noise which is equivalent to a minimum quantization noise outside every subband. • A reconstruction of the output signal with as little in-band ripple as possible. Two approaches may meet these criteria:

• Direct processing using bandpass filters.

• Digital demodulation followed by a decimation filter, and lowpass filter. It is shown that (due to the decimation) the second solution has a better performance with the same number of filter coefficients.

Solution without demodulation (solution I)

This solution consists in reconstructing directly the signal by using a bandpass filter for each output S k (Figure 2, part B). Then the outputs of all bandpass filters S f k are recombined to rebuild the signal. The signal is then decimated to decrease the signal data rate. This solution involves high order bandpass filters that complicates the digital process. For instance, only an 11.5 bit resolution can be reached using an 8 modulator filter bank with 256 taps Hann bandpass FIR filters compared to an expected 14 bit resolution : 1024 coefficients would be required to reach this resolution, this implies enormous computing resources and makes this solution difficult to realize.

Solution with demodulation (solution II)

In this solution (Figure 4), the outputs of all the channels are digitally demodulated so that their frequency band is centred on zero. Because of the previous oversampling by the modulators, the outputs must be decimated to reduce the data rate. Then, each signal is processed by a lowpass filter, before being remodulated and recombined with the signals of all the other channels. The value of the maximum decimation factor is equal to the floor value of the global OSR, that is f s /2B, B being the input signal's bandwidth. The lowpass filters' transfer functions carry significantly fewer coefficients thanks to the decimation that eases the constraints on digital filters by widening the transition zone. The choice This will be illustrated in section 4 by simulating three types of windows and comparing their results. Figure 5 represents the frequency response of the filters which are used in all of the channels, eight in this case, and also their sum. This sum shows a very weak ripple inside the frequency band, about 10 -3 , with attenuations on the edges as high as 6 dB. Note that the band is limited to [0 f S /2] due to the decimation.

CORRECTION PROCESS

The STF of analog modulators is not a simple time-delay transfer function as in discrete-time modulators. However, it can be calculated and plotted if the input signal is band limited. During calibration that might be mandatory to adapt to the specifications of real modulators, we prefer to separate between amplitude correction of the STF, modulator phases alignment, decimation filter's amplitude correction and elements phase alignment in low frequency.

Amplitude correction of the STF

As shown in Figure 3, the STF of each modulator is not flat in the band, but presents approximatively a parabolic form. A correction filter with three coefficients (Figure 6) is enough to flatten the STF.

Modulator phases alignment

The delta sigma converters have an almost linear phase in the band around the central frequency (Figure 7.a). However, their phases are not connected in the transition zone. So a signal in the transition zone between two adjacent modulators will have two different phases which can influence the output signal. This phase mismatch is compensated for by multiplying the signal in each channel with a complex number which allows an almost linear phase in the full band that is being processed (Figure 7.b).

Decimation filter's amplitude correction

The frequency response of the comb filter used for the decimation has a sinc shape, with a cut-off frequency of 1

N d

, N d being the decimation factor. It is given by ( 1) :

H(e jΩ ) = 1 N d 1 -(e jΩ ) N d 1 -e -jΩ k+1 (1)
k : modulator's order This filter is followed by a three-coefficient correction filter in order to obtain an almost flat gain limited by 1

N d
and prevent the attenuation of the signal.

Elements phase alignment in low frequency

The lowpass filters that are used, such as the decimation filters, have a linear phase. Due to demodulation and remodulation, the signals in the transition zone between two adjacent channels will have opposite phases. This creates in-band ripple in the output signal that can be countered by multiplying every channel by the complex number e -j∆ϕ , ∆ϕ being the total band phase mismatch :

∆ϕ = πB(L -1) (2)
L : filter's length

Integration in the main filter

Practically, the low pass filter following the decimation filter (Figure 4) includes all the elements that contribute to the previous corrections. Its frequency response is equal to the product of all contributing elements including the original lowpass filter.

MAIN RESULTS AND SIMULATIONS

To illustrate the discussion above, an architecture with eight third order modulators and a large band input signal are given as an example. The input signal is a cardinal sine and has a square limited band of 320 MHz centered around 800 MHz for a sampling frequency f s = 3.2GHz which is equivalent to a normalized band B = [0.2 0.3]. The resolution obtained by solution I with a 256 taps Hann bandpass FIR filters is 11.5 bits. On the other hand, solution II gives a 13.9 bit resolution by using 64 taps Hann lowpass FIR filters. Figure 8 represents the power spectral densities of the input signal, the output signal, and the output noise that are obtained with solution II. There is a slight difference on the edges of the spectral densities between the input signal and the output signal. This is related to the fact that the sum of lowpass filters responses is attenuated on the edges, (Figure 5), and that the ripple inside the band is about 10 -3 which doesn't decrease the signal's reconstruction. The sampling frequency f S is equal to 4 × f 0 , f 0 being the central frequency of the useful signal's band. This choice facilitates the implementation of delta sigma modulators [START_REF] Schreier | Decimation for bandpass sigma-delta analog-to-digital conversion[END_REF].

Figure 9 shows the evolution of the theoretical resolution as function of the number of modulators for different orders. It can be noticed that the resolution is increased by k bits every time the number of modulators is doubled, k being the order of the modulators. Even though, the improvement of resolution requires an increase in the number of modulators, the advantage of this architecture compared to the architectures proposed in [START_REF] Eshraghi | A time-interleaved parallel ∆Σ A/D converter[END_REF]- [START_REF] Aziz | Multiband sigma-delta analog to digital conversion[END_REF] is the fact that to obtain the same resolution fewer modulators are required which means smaller silicium area. The resolution can be improved by increasing the order but this may lead to unstable modulators . The number of coefficients of the lowpass filters is carefully chosen in a way that does not decrease the overall performance.

Table 1 describes the loss of resolution compared to the one obtained with ideal lowpass filter (14.6 bits) according to the number of coefficients in the lowpass filters with three types of windows. One can notice that the best resolution is obtained with the Hann window due to its particular shape that attenuate the noise outside every subband. It is worth mentioning that after reaching a certain threshold (96 coefficients), increasing the number of coefficients doesn't improve the resolution more than 0.5 bits. In the previous example with a sampling frequency of 10 × B, B being the input signal's band, and a decimation factor of 5, the problem is reduced to realizing 8 FIR filters with 64 coefficients each, that is 512 Multiply-Accumulate (MAC) operations at 2 × B frequency, in addition to the decimation and correction filters. To date, the maximum DSP performance available on the market is 8000 MIPS. The number of DSP needed in the -1.2 -0.9 -0.7 -0.25 -0.15 -0.01 (bits), Hann previous example ( section 4) is 41. This number is too high to be applicable in current technologies. On the other hand, due to the silicium evolution, these computing resources will be soon available in a single chip.

CONCLUSION

This paper describes an architecture for limited wideband signal conversion that helps reaching the requirements for improving telecommunication systems. It is based on the use of analog modulators. Two solutions are proposed to reconstruct the input signal and have been tested by digital simulations. The results of these simulations further the adoption of the digital reconstruction with demodulation and decimation as it requires less computing resources. We also estimated the computing power needed for the implementation with future technology.

Figure 1 :

 1 Figure 1: Decomposition of the input signal band

Figure 2 :Figure 3 :

 23 Figure 2: Wide band converter's architecture

Figure 4 :

 4 Figure 4: Digital processing with demodulation

Figure 5 :

 5 Figure 5: Frequency response for eight 128 taps Hamming FIR filters in the band (a) and a zoom on the ripples (b).

Figure 6 :

 6 Figure 6: Signal Transfer Function for analog modulator before and after correction

Figure 7 :

 7 Figure 7: Delta sigma phases before correction (a) and after correction (b).

Figure 8 :Figure 9 :

 89 Figure 8: Power spectral density for output signal, input signal and output noise signal (a) and a larger view (b)..

Table 1 :

 1 Resolution loss with different windows

	Number of	48	56	64	96	128	256
	coefficients
	Resolution loss	-3.8	-3	-1	-0.5	-0.3	-0.1
	(bits), Hamming
	Resolution loss	-1.7 -1.3	-1	-0.5	-0.3	-0.1
	(bits), Blackman
	Resolution loss


V Owczarek

P Franco

R Mullot

A genetic algorithm to solve a space-filling curve problem

1 Space-filling curve: A pattern driven algorithm A space-filling curve (SFC) is an ordering function which creates a bijection between integers I and points X lying in a D-dimensional regular grid. Let consider a point X a ∈ X = [0, 2 n -1] D , the associate integer corresponds to I a ∈ I = [0, 2 nD -1] where n is the order of the curve. This ordering has the property to conserve the distance, i.e. close points in the space have close indices. This property known as the locality preserving. At this time, the Hilbert curve defined by D. Hilbert [START_REF] Hilbert | Ueber die stetige Abbildung einer Line auf ein Flächenstück[END_REF] in 1891 achieve the best locality preserving level [START_REF] Faloutsos | Fractals for Secondary Key Retrieval[END_REF]. In various domain, many applications are drawn on the locality preservation properties of space-filling curves. For example, one could concern global optimization, data visualization, image compression and encryption.

Recently, G. Nguyen [START_REF] Nguyen | Courbes remplissant l'espace et leur application en traitement d'images[END_REF] proposed a new algorithm to compute SFCs where the curve at order n = 1 is used to recursively define the bijection between the D-dimensional grid and the indices. This new formulation is able to define any Hilbert like SFC, by using any pattern that respects the adjacency rule: if I a and I b are separated by one unit then their associate points X a and X b are separated by a unit distance. The well know Hilbert curve is defined by using the Reflected binary gray code (RBG).

Using this new definition of SFC, relevant studies have been performed by P. Franco [START_REF] Franco | Alternative patterns of the multidimensional Hilbert curve[END_REF] to investigate the influence of the pattern for the locality preserving level of the n order curve. The results proved that it is possible to create comparable or better SFC than the regular Hilbert curve which is considered, in the literature, as the best locality preserving curve.

In fact, finding patterns which have a high level of locality preservation level is equivalent to find all Hamiltonian paths in a hypercube graph, which is NP-complete according to R. Karp [START_REF] Karp | Reducibility among Combinatorial Problems[END_REF]. A hypercube graph in dimension D is defined by 2 D nodes along with D 2 D-1 edges, and each node has a degree of D. Obviously, this problem can not be solved by regular graph traversal techniques when D > 5. Moreover, our goal is not to find one unique pattern but a set of non-dominated solutions according to the Faloutsos criteria [START_REF] Faloutsos | Fractals for Secondary Key Retrieval[END_REF] as

F r (X) = 1 2 D k,l∈[2 D ], k<l, d(k,l)≤r max{d(X k , X l )}, ( 1
)
where X is the set of points in the D-dimensional regular grid ordered by a SFC and d is the Manhattan distance.

In the next section, different stochastic local search algorithms are briefly explained and results of our experiments are discussed.

Stochastic local search algorithms for hamiltonian chain

In our work, genetic algorithms (GAs) [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: Nsga-ii[END_REF][START_REF] Derbel | A set-oriented MOEA/D[END_REF] are used to find hamiltonian chains. GAs use successively mutation/crossover and selection on a population of solutions to find the optima. In every algorithm, the mutation operator is 2-opt defined by Georges A. Croes [START_REF] Croes | A method for solving traveling-salesman problems[END_REF] and the crossover is single point. The algorithms described in Table 1, are different in terms of selection and fitness function. The distance of the chain is denoted by |C| and the Faloutsos criteria at radius α by F α .

In the elitist selection method "Top 100" the first hundred hamiltonian chain corresponding at each generation to the hundred lowest fitness score are conserved to be the next generation. Whereas "Non-dominated set" stands for the conservation over generations of the set of all nondominated solutions. 1). Multi is a multiobjective GA version with a non-dominated set selection method.

For each algorithm the non-dominated set of the results of 1000 runs, for D = 5, is saved. Thus three created fronts are compared, as proposed in [START_REF] Knowles | A Tutorial on the Performance Assessment of Stochastic Multiobjective Optimizers[END_REF], using the hypervolume (to be maximized) and the additive epsilon (to be minimized) indicators.

For the hypervolume indicator, Multi is better with a score of 0.1254 compared to 0.1197 and 0.0772 for respectively Sum and Classic. The additive epsilon indicator point out the same performances: Multi reached the first place with a score of 0.0625 whereas Sum and Classic respectively obtained 0.0937 and 0.1875 scores.

The results are promising: Multi provided close sets to the exact known front, according to the hypervolume and the additive epsilon indicators. Similarly, Sum reached comparable results which would be consistent for further improvements. Indeed extended investigations will be ensure to confirm the results on grids of higher dimension. Moreover, the non-dominated set found during this study, on dimension D = 5, shows the non-optimality of the Hilbert curve pattern: the associated Faloutsos scores are dominated by several other patterns.

Table 1 .

 1 The different GAs used to find hamiltonian paths, according to |C| the length of a path and Fα, the Faloutsos criteria. Multi Multi-objective Non-dominated set {F3.|C|, ..., F6.|C|} According to Table 1, Each of them differs in term of selection and fitness function. Classic uses only |C| whereas Sum and Multi use the Faloutsos criteria F α (Equation

	Name	Type	Selection method	Fitness Function
	Classic Single-objective Top 100	|C|
	Sum	Single-objective Top 100	|C| 2 +	6 i=3 Fi