Sergey Zverlov
email: zverlov@fortiss.org

Maged Khalil
email: khalil@fortiss.org

Mayank Chaudhary
email: chaudhary@fortiss.org

Pareto-efficient deployment synthesis for safety-critical applications in seamless model-based development

Keywords: Design Space Exploration, AutoFOCUS, Optimization, SMT, Safety, Resource Optimization, Deployment, Scheduling

Increasingly complex functionality in automotive applications demand more and more computing power. As room for computing units in modern vehicles dwindles, centralized architectures -with larger, more powerful processing units -are the trend. With this trend, applications no longer run on dedicated hardware, but share the same computing resources with others on the centralized platform. Ascertaining efficient deployment and scheduling for co-located applications is complicated by the extra constrains which arise if some of them have a safety-critical functionality.

Building on our pre-existing design space exploration solution, we integrated safety constraints, such as ASIL and HW failure rates, as well as practical aspects, such as component costs, and extended the approach to allow for multi-criteria optimization. The work was implemented into our seamless model-based research CASE tool AutoFOCUS3 and evaluated using a nontrivial industrial-inspired case study. The solution is capable of synthesizing deployments together with corresponding schedules, which satisfy different safety and resource constraints. The deployments can subsequently be integrated into the safety case argumentation of AutoFOCUS3, leveraging the tool's seamless capabilities to support safety evidence and certification.

Moreover, we are not interested in merely valid solutions, but in good ones. We hence developed a multi-objective optimization algorithm, which synthesizes solutions pareto-optimized for safety, resource usage, timing and any other constraints the user defines. Our approach demonstrates the feasibility and effectiveness of using formal methods to generate correct solutions for safety-critical applications, increasing the confidence and validity of safety cases.

I. INTRODUCTION

Connected vehicles and advanced driver assistance systems (ADAS) are just a few of the latest technological drivers increasing the demand on computing power in classical domains of embedded systems development, such as the automotive sector. Given the already high number of ECUs (electronic control unit) in today's automobiles, there is a clear trend towards centralized architectures featuring larger, more powerful (potentially multi-core) platforms. This trend lends increased urgency to the problem of mapping logical computational tasks to the hardware (HW) nodes that will execute them. This task is intrinsically difficult in embedded systems, because their limited resources add many constraints to the deployment problem that have to be respected, e.g., execution timing, memory constraints, power consumption, bus loads and many more. If the applications to be deployed are safety-relevant, this adds a new dimension to the deployment problem, increasing the difficulty many-fold. Safety standards dictate design patterns, such as partitioning according to criticality, to maintain freedom from interference, but also set requirements for the hardware nodes' reliability. This adds multiple criteria (some orthogonal) to both the problem space (software components) and the solution space (hardware nodes). Mapping logical/software components to a hardware architecture goes beyond the simple task of mere allocation, and onto the generation of a deployment and corresponding schedule, which satisfies different constraints, be it related to safety, resource or cost.

The work presented in this paper is a part of ongoing research efforts into design space exploration (DSE), which aims at facilitating the seamless development of safety-critical applications in the embedded domain. DSE is defined as a process of systematically finding a solution from a set of possible designs, w.r.t. a set of given constraints [START_REF] Voss | Design space exploration in autofocus3an overview[END_REF]. Building on our pre-existing approach for the efficient generation of embedded system architectures with multi-criteria optimization (e.g., memory usage, power consumption, bus loads), we expanded the approach to include safety attributes, such as hardware failure metrics, but also practical aspects of realtime development, such as HW costs. The presented approach computes task and message schedules that are optimized with respect to a global discrete time base. As a part of the solution, the approach generates an optimized assignment of tasks to computation resources (cores). The approach is integrated into the AutoFOCUS3 (AF3) tool-chain, as presented in [START_REF] Voss | Deployment and scheduling synthesis for mixed-critical shared-memory applications[END_REF].

This paper presents the approach, and demonstrates its usefulness using examples which illustrate the effect of different criteria on deployment synthesis and how the approach can be used to optimize the generated valid solution for one or more criteria. Prior to this work, there was no support for generating and optimizing deployments in AF3 while simultaneously satisfying safety metrics, resource constraints and hardware costs.

Furthermore, AF3 integrates multiple dedicated architectural views, covering not only logical (software) and technical (hardware) architectures, but also requirements and safety case expression. Therefore, the method presented here can be integrated into a seamless development approach that allows arguing evidence on a formal basis, as well as reusing argument structures and reducing the costs of component as well as design (re-)certification for safety-critical applications.

A. Related Work

Approaches where computer-aided methods are used for system analysis and optimization are not new, having been proposed as early as in the late fifties, such as the optimization approach for register transfer systems towards cost and performance presented in [START_REF] Breuer | Recent developments in the automated design and analysis of digital systems[END_REF].

Recent works address higher levels of abstraction, such as the mapping of software to hardware and the corresponding scheduling [START_REF] Kang | An approach for effective design space exploration[END_REF]; memory optimization [START_REF] Kuenzli | Efficient design space exploration for embedded systems[END_REF]; or finding suitable platform architectures [START_REF] Fernandez | Bounds on the number of processors and time for multiprocessor optimal schedules[END_REF][7] [START_REF] Thompson | A framework for rapid systemlevel exploration, synthesis, and programming of multimedia mp-socs[END_REF]. In this paper we address the joint problem of finding an optimized platform, deployment and schedule w.r.t. to safety, cost, performance and resource consumption.

The applicability of solvers for finding deployments and schedules was shown in [START_REF] Metzner | Scheduling distributed real-time systems by satisfiability checking[END_REF] and [START_REF] Voss | Deployment and scheduling synthesis for mixed-critical shared-memory applications[END_REF]. The possibility of using various solvers for DSE problems was further discussed in [START_REF] Kugele | On the Deployment Problem of Embedded Systems[END_REF] and [START_REF] Saxena | A generic framework for design space exploration[END_REF], which -similarly to our work -use a solver to find valid or optimized solution.

Furthermore there are approaches, which take safety into account. [START_REF] Ortmeier | Safety optimization: a combination of fault tree analysis and optimization techniques[END_REF] -for instance -combines FTA analysis and optimization techniques to find optimal system configurations; [START_REF] Dhouibi | Safety driven optimization approach for automotive systems[END_REF] optimizes automotive architectures towards cost and safety; and [START_REF] Hilbrich | Deploying Safety-Critical Applications on Complex Avionics Hardware Architectures[END_REF] uses a brute-force algorithm to generate safety-compliant deployments for avionic systems. Compared to those approaches, the optimization problem we are considering is more complicated (higher number of criteria and/or degrees of freedom), and furthermore we integrate our approach into a model-based framework, which makes it more usable for practitioners.

There are a number of frameworks with Design Space Exploration capabilities, which were proposed over the years. Some of them use their own DSLs to specify DSE Problems, such as FORMULA [START_REF] Kang | An approach for effective design space exploration[END_REF] and AAOL [START_REF] Kugele | Model-based optimization of automotive E/E-architectures[END_REF]. Others use wellestablished formalisms, such as EAST-ADL [START_REF] Walker | Automatic optimisation of system architectures using EAST-ADL[END_REF], UML [START_REF] Selic | Modeling and Analysis of Real-Time and Embedded Systems with UML and MARTE: Developing Cyber-Physical Systems[END_REF] and AADL [START_REF] Aleti | ArcheOpterix: An extendable tool for architecture optimization of AADL models[END_REF]. We integrated our approach in the AutoFO-CUS3 Framework 1 , which is based on the FOCUS methodology [START_REF] Broy | Specification and development of interactive systems: focus on streams, interfaces, and refinement[END_REF] and was shown to be compliant to AUTOSAR 1 http://af3.fortiss.org/2 in [START_REF] Schaetz | Automating design-space exploration: Optimal deployment of automotive sw-components in an iso26262 context[END_REF], leveraging the framework's seamless development capabilities.

The safety metrics used in the multi criteria optimization have their foundations in the ISO26262 automotive functional safety standard, and investigations into architecture benchmarking in the ITEA2 SAFE research project3 published in [START_REF] Safe-E | Deliverable d4.4b: Final version of plug-in for safety and multi criteria architecture modeling and benchmarking[END_REF].

Due to the seamless nature of AF3, our approach demonstrates how an integrated model-based framework can pragmatically provide formal support for practical problems in the development and certification of safety-critical systems in compliance with the relevant standards -in our case ISO26262.

B. Structure of Paper

Chapter II gives an overview of background information building the fundamentals of this paper. In III the modelbased CASE tool AutoFOCUS is presented. In this tool, we integrate our proposed approach from chapter IV. We evaluate our work using a non-trivial case-study in chapter V and finally we conclude in VI.

II. BACKGROUND

This section introduces briefly some concepts necessary for understanding the rest of the paper.

A. SMT

A satisfiability (SAT) problem consists of variables represented in a formula, with the goal being to determine whether there exists an assignment of variables that makes the whole Boolean formula satisfiable [START_REF] Gu | Local search for satisfiability (sat) problem[END_REF]. Satisfiability modulo theories (SMT) generalize boolean satisfiability by adding equality reasoning, arithmetic, arrays, quantifiers and other first order theories. SMT solvers are tools for deciding the satisfiability of formulas in those theories [START_REF] Moura | Z3: An efficient smt solver[END_REF], which can be used to solve various classes of problems, such as software and hardware verification; test case generation; planning; or scheduling and deployment [START_REF] Van Harmelen | Handbook of knowledge representation[END_REF]Ch. 2,p. 89ff]. Solvers may be designed to not only be capable of determining whether a formula is unsatisfiable or not but also point to the set of clauses which are not satisfiable, called unsatisfiable cores or UnSAT Cores.

B. Safety

The work presented here was carried out within the SAFE research project, which targeted the model-based development of software architectures for safety-critical applications in the automotive domain. Hence, we focus on metrics identified in the ISO26262 automotive safety standard. These include ASIL (Automotive Safety Integrity Level), as well as hardware failure metrics identified in clauses of part 5 of the standard. The proposed metrics include PMHF (probabilistic measure of random hardware failures) the maximum probability of violating a top level safety goal, shown mapped to corresponding ASIL levels in Table 1 -and FRC (failure rate classes) an evaluation of each cause of safety goal violation. These metrics are explained in more detail in [START_REF] Safe-E | Deliverable d4.4b: Final version of plug-in for safety and multi criteria architecture modeling and benchmarking[END_REF].

C. Multi-objective Optimization

As an optimization problem, we consider the search of a good (optimized) or best (optimal) solution of a decision problem among a set of alternatives, assuming the existence of a set of objectives, according to which the quality of the alternatives can be measured [START_REF] Ehrgott | Multicriteria optimization[END_REF]. Cases in which an optimization problem does not only have one objective, but several ones are called: multi-objective optimization, and these objectives are often contradictory. Therefore, in most cases of multi-criteria optimization problems, there is no single optimal solution for the problem under consideration, but a set of solutions, where each is optimal to a subset of objectives. This set of solutions is called Pareto-efficient or the Pareto front.

III. AUTOFOCUS3

AUTOFOCUS3 (http://af3.fortiss.org) is a research CASE tool that allows modeling and validating concurrent, reactive, timed systems on the basis of formal semantics [START_REF] Bauer | Automode -notations, methods, and tools for model-based development of automotive software[END_REF]. Furthermore -in [START_REF] Schaetz | Automating design-space exploration: Optimal deployment of automotive sw-components in an iso26262 context[END_REF] -it was illustrated how AF3 modeling concepts fit into concepts provided by AUTOSAR.

A. Levels of Abstraction

An AF3 system model is divided into several models that provide different levels of abstraction, while supporting different views on the system model, e.g., from the model-based requirements view down to the hardware-related platform view.

The Requirements Specification and Analysis View provides for requirements specification, documentation, and analysis of the requirements of a system.

The Logical Architecture View of a system is defined by means of components communicating via message passing through typed channels, using a clearly defined model of computation. Messages exchange is synchronized with respect to a global, discrete time base. Components can directly implement behavior or consist of other components that do so.

The Technical Architecture View describes a hardware topology that is composed of hardware units, e.g. CPUs of a Multi-Core Board, hardware ports (sensors or actuators), buses and a shared-memory component.

Furthermore, AF3 supports so-called integrated or weaving models, which hold information from different levels of abstraction and thereby connect them. The deployment view is one example of such an integrated model, which maps elements from the component to elements of the technical architecture. This provides traceability between modeling artifacts [START_REF] Voss | Design space exploration in autofocus3an overview[END_REF].

Another example is the AF3 support for a safety-case view, which is supported by integrated models, linking the safety case elements to all the other AF3 artifacts in support of the argument structure.

B. Design Space Exploration in AF3

A valid deployment and schedule pair for any system under consideration has to fulfill certain constraints, for instance, precedence constraints or resource utilization (two tasks can't run in parallel on the same node). These constraints can be formalized in such a way that they can be used as input for a state-of-the-art SMT solver. In this sub-section we provide a small overview of work done in [START_REF] Voss | Deployment and scheduling synthesis for mixed-critical shared-memory applications[END_REF], which we extend in the following sections.

The approach uses the integrated deployment model, which combines information from the logical and technical architecture (cf. III-A). From the logical architecture this model contains a set of logical components (which, in this context, we call tasks) T = t 0 , t 1 , ..., t n passing messages M = m 0 , m 1 , ..., m k via channels. This communication structure results in dependencies between the tasks. Those dependencies can be used to derive constraints, such as the execution order of tasks, for the schedule generation.

Additionally, this model contains information from the technical architecture, such as a set of computational resources (nodes) N , a set of buses B, and in some cases memories MEM. Nodes are used to store and execute the tasks from the logical architecture, whereas buses and memories are used to exchange messages between the tasks.

By encoding this information in a SMT solver, it is possible to synthesize a valid deployment and schedule pair, if they exist. Furthermore, it is possible to produce not only valid but also optimized solutions (cf. [START_REF] Voss | Deployment and scheduling synthesis for mixed-critical shared-memory applications[END_REF] or [START_REF] Zverlov | Synthesis of pareto efficient technical architectures for multi-core systems[END_REF]), using a meta-search on top of the SMT solver, which manipulates constraintsmax. execution time, for instance-after every SMT request.

IV. SAFETY-ORIENTED DEPLOYMENT AND SCHEDULING IN AF3

In this section we present how using a SMT solver makes it possible to synthesize safety oriented deployments, which are either valid or optimized w.r.t. to certain criteria. Furthermore we discuss how we integrated this approach in AutoFOCUS3.

A. Artefact properties in AF3

As already explained in III, AutoFOCUS3 view on the system is divided in different levels of abstraction. Each of these levels contains a set of artifacts (i.e. ECU in Technical Architecture). Using the "annotation" concept of AF3 it is possible to assign properties to each artifact (i.e. Failure Rate to an ECU). For our approach a set of safety and resource related properties were needed, which partly already existed and partly were added by us.

In context of safety we added the possibility of annotating PMHF values for ECUs and busses. This value is then Furthermore we added the possibility of assigning energy consumption, memory and cost to the hardware elements as well as memory consumption and taswk duration to the logical components.

B. Scheduling and Deployment Constraints

The constraints -introduced in this sub-section -are already formalized. Together with instructions, such as in [START_REF] Eén | Translating pseudo-boolean constraints into sat[END_REF] or examples such as in [START_REF] Voss | Deployment and scheduling synthesis for mixed-critical shared-memory applications[END_REF], these formalized constraints provide enough information to be encoded as a SMT problem.

1) PMHF Constraint for ECU: This constraint states that a task t 2 T can only be mapped on a node n 2 N , if the PMHF value of the node n is compliant to the ASIL value of the task t according to table I. Let : T 7 ! N be a function that allocates tasks to nodes, then the constraint can be formalized as follows:

8t 2 T 0
, where 3) Memory Constraint: In real-life embedded systems resources, such as memory, are limited. We assume that each hardware node n offers a certain amount of memory that can be used by the tasks t allocated to it, and must not be exceeded. To define this constraint, we first have to sum up the memory which is used by each node:

T 0 = {t 0 | (t 0 ) = n} ! t.asil  n.asil (
8t 2 T 0
, where T 0 = {t 0 | (t 0 ) = n} ! n.used memory = X t.mem (3) Having determined the memory used by each node, we can now ascertain that the used memory does not exceed the available memory (n.ram):

n.used memory  n.ram (4)

4) Maximum Number of Nodes:

In some cases it is interesting to know whether the deployment of tasks is possible on less nodes than currently used or available. To define a constraint limiting the number of used nodes, we first have to find out which nodes are currently used (has tasks deployed on it). We can formalize this as follows:

n.used = ( 1, 9t 2 T : (t) = n 0, otherwise (5)
Next, we identify how many nodes are currently used:

total used nodes = N X n n.used (6)
Finally, we can formalize the constraint as follows:

total used nodes  max nodes (7)

5) Cost: Cost is a very important factor in industrial projects. This is especially true in context of automobile industry, since even a small saving in component costs can impact a lot due to the large numbers of produced cars. As already discussed, PMHF values of hardware components can be mapped to ASIL values, but also to component costs, under the assumption that hardware with more stringent failure rates is also more expensive to build. It is thus relevant to define a separate constraint to limit component costs, without violating any other constraints. We first need to know which nodes are used in the current deployment, the formalization of which has already been shown in (eq. 5). Based on this knowledge, it is possible to calculate the total cost of the system:

total cost = N X n n.cost ⇥ n.used (8)
Subsequently we restrict the maximum cost of the system as follows:

total cost  max cost (9)
6) Power Constraint (Energy Constraint): Energy consumption is another important factor in embedded systems and hence we generate deployments that take energy efficiency into account. In our simplified energy model we assume that each node consumes energy only as long it is active (non-idling). Therefore the non-idling time can be calculated as follows:

n non idle time = X t2T 0 t duration where T 0 = {t 0 | (t) = n} (10)
Since power is defined as energy over time the energy consumption of a node n can be formalized with the following equation:

n.energy = n.power ⇥ n.non idle time [START_REF] Saxena | A generic framework for design space exploration[END_REF] Using (eq. 12) it is now is possible to calculate the total energy consumption of the system. This value again can be constrained by the maximum allowed energy consumption (eq. 13).

total energy consumed =

N X n n.energy (12)
total energy consumed  max energy

C. Pareto-efficient Deployments

In the previous sub-section we presented the constraints, which -in scope of this work -are used to synthesize valid deployments with certain characteristics. In the following subsection we discuss how to find optimal (or at least optimized) deployments w.r.t. certain criteria.

The problem of generating the pareto-optimal deployments can be formulated in terms of objectives to be optimized and constraints to be satisfied (as shown below). The formulation is followed by a brief explanation of the objectives and an introduction of the proposed optimization algorithm. The values of variables max nodes, max memory and upper bound sil are entered by the user, if they choose to generate pareto-optimal deployments. The PMHF constraint are also needed to be satisfied while generating the paretooptimal deployments. Since we are aiming at minimizing the total SIL of the hardware architecture, we do not use cost constraint and energy consumption constraint explicitly. 1) Optimization Criteria: In [START_REF] Diebold | Practitioners' and researchers' expectations on design space exploration for multicore systems in the automotive and avionics domains -a survey[END_REF], it was illustrated that participants of the survey -if it comes to system design optimization -are interested in such criteria as safety, timing, resource usage, energy consumption and cost.

Minimize

Following this line of argumentation we implemented a multi-objective optimization algorithm which takes number of used nodes, used memory per node, as well as hardware costs and energy consumption as optimization criteria. For simplicity, we assumed hardware costs and power consumption to be directly correalted to the ASIL value, and thus used total ASIL as a proxy optimization criterion.

Furthermore, we took timing (end-to-end latency) into account using a solution, which, while not being Pareto-optimal according to the definition in II-C, was still optimized as explained in IV-C2.

2) Optimization Algorithm: Our algorithm works in three steps: reduction of the search-space, generation of all valid solutions for the reduced search-space, and elimination of dominated solutions, i.e., those solutions which are superseded by the pareto front.

In the first step, our approach reduces the search-space by calculating lower bounds for the criteria memory per node and number of nodes. Consider a scenario wherein the logical architecture contains 5 components and each component requires 10 units of memory. Let the values of variables max nodes and max memory (as entered by the user) be 4 and 20 respectively. It is clear that there will be no possible solution if the number of nodes in the technical architecture is less than 3, since the total memory needed to accommodate the 5 logical components is 50 and maximum memory allowed per node is 20. Similarly, the memory per node can be no less than 20 (assuming memory per node is a multiple of 10). As the result of this step we get a set of possible configurations in terms of a range for number of nodes i.e. [min nodes, max nodes] and for memory per node i.e [min memory, max memory].

In the second step, we generate valid solutions for all possible combinations of nodes and memory found in the previous step. This is illustrated in the algorithm 1 below.

Lines 2-4 shows that for each pair of nodes and memory in decision variable space, a constraint satisfaction problem Algorithm 1 Valid Solutions if result is SAT then 13: solution parse(result) 14:

store solution to UniqueSolutions is created which is solved by the Z3 SMT solver. The checkSAT () function formulates the problem in Z3 syntax, where the parameters nodes, memory and upper bound sil defines the upper limits for assertions used in node usage, memory per node and total sil constraints, respectively . Line 5 checks if the constraint satisfaction problem is satisfiable.

In case it is satisfiable, the output of the Z3 solver is parsed to fetch number of nodes, memory per node, total sil and e2e latency. These variables are combined into a solution (line 6) and stored into a set of unique solutions (line 7), as we do not want to duplicate the set of valid deployments. We then try to optimize the total sil by reducing it in steps of 1 (line 10) and check the satisfiability of new constraint satisfaction problem (line The reduction of total sil continues until Z3 cannot find a solution to the constraint satisfaction problem (line 9). In the last step, the algorithm eliminates the solutions which are dominated by other solutions w.r.t. number of nodes, memory per node, total ASIL and thereby builds a Pareto front. As mentioned earlier our approach chooses a solution with the lowest end-to-end latency from the set of valid solutions, which were produced in step 2. For that reason we call this solution not optimal but optimized.

D. Integration in AutoFOCUS3

In scope of this work we integrated our synthesis approach together with the constraints and the optimization algorithm (introduced in the previous sub-sections) in the AutoFOCUS3 development methodology.

A typical development process in AF3 could look as follows. An engineer, designing a safety-critical system in Aut-oFOCUS3, ideally starts with the definition of requirements. Among other things in this phase, he will identify a set of safety goals which the system under development will have to fulfill. One of the safety goals could be that safety-critical software should not be compromised due unsafe hardware it is running on, which corresponds to the constraints 1) and 2) from IV-B.

In the next step, the engineer starts to design the structure and the behavior of the system in the logical architecture (cf. III-A). After that he can assign certain properties (cf. IV-A), such as Safety Integrity Level, to the elements of this level of abstraction. At this step it possible either to continue with the design of the technical architecture (i.e. the technical platform of the system is already fixed) or use the optimization approach from IV-C to find an optimized technical architecture together with the corresponding deployment and schedule. Regardless which option the engineer takes at some point he will end up with a logical and a technical architecture. Now he can use either the constraints from IV-B or the approach from IV-C to find either valid or optimized deployments and schedules w.r.t. the constraints he is interested in (cf. fig. 2).

Fig. 2: Choosing constraints in AF3

The deployments and schedules which are found during this Design Space Exploration activity are valid towards certain constraints (such as 1) and 2) from IV-B). Therefore, the results of this DSE run can now be used as an evidence in a safety case to prove that the safety goal is reached by design. The integration of safety cases into AF3 development process was demonstrated in [START_REF] Voss | Towards modular certification using integrated model-based safety cases[END_REF]. Fig. 3: Finding the unsatisfiable constraints Given the potential complexity of the optimization problems addressed by our approach, it is possible to define the constraints so tightly that no solution can satisfy them all. For instance, the provided pool of ECUs -even if all of them were used in combination -does not provide enough memory to run all the software components. It is thus just as useful to support the user by providing guidance as to which constraints could not be satisfied. For this case we integrated the Z3s UnSAT Core functionality (cf. sec. II-A), which identifies unsatisfiable constraints for the current DSE problem. As seen in figure 3, this feature points the user exactly to the constraint which is not satisfiable and, hence, needs to be adjusted.

V. EVALUATION

A. Description of the Case Study

We evaluated our approach using an industrial-like case study, which was created in the scope of the SAFE Project. This case study was modeled in AutoFOCUS3 and consists

B. Cost versus Safety

In our investigations, we analyzed how manipulating the criteria -both individually and collectively -affects the deployment and schedule generation process. The investigation is too large to list in detail here; more results are provided in [START_REF] Safe-E | Deliverable d4.4b: Final version of plug-in for safety and multi criteria architecture modeling and benchmarking[END_REF]. To demonstrate the approach, we will focus on one example: how cost reduction affects safety-oriented deployments; an optimization problem reflecting design trade-offs, under the assumption that hardware with more stringent failure rates is more expensive to build. deployments to satisfy the multi-criteria problem, while optimizing for power consumption, total cost of hardware, and total number of nodes. The results show that it is possible to satisfy the problem with various configurations and allows the user to choose which criteria are more relevant, and hence which deployment -among the multiple valid ones -is most suitable to their needs.

C. Evaluation of the Optimization Approach

In our second experiment, we investigated how long our approach would take to find a set of non-dominated, i.e., optimized, solutions. As input we used the case-study from section V-A. The search space was restricted using the following intervals: 1 to 9 nodes; 1 to 36 as total ASIL; and 10 to 100 MB memory per node (using a 10 MB iteration step). As discussed in section IV-C, the end-to-end latency does not have to be restricted because our approach picks the solution with the best end-to-end latency from all the solutions it finds. The total ASIL constraint represents the hardware cost factor, by assigning a high number to more capable hardware nodes. In our experiment we used the Z3 solver with a 6 hours time limit for each evaluation. This means, that after this time period the Z3 solver times out with the best solution so far, which might be not the overall optimal solution. The result of this experiment, presented in table IV, was calculated in 126 hours. Given the size of the case study and the degrees of freedom under consideration (deployment, schedule, memory, SIL distribution, timing) we think that this time period is reasonable and feasible in a practical setting.

Most importantly, the approach allows for the explicit optimization for selected criteria, the impact of which can be seen in the last tables. One can have different deployments on the same as well as different numbers of nodes with different effects on resource usage, system attributes, and hardware costs. For instance, if the number of nodes is the absolute limiting factor, then one can choose the first deployment with 5 nodes. If however, one can accommodate a design with 6 hardware nodes, then it is possible to choose a solution optimized for Memory consumption and hardware costs, which also provides a comparatively low latency value. More details on the different effects of optimizing for different criteria are given in [START_REF] Safe-E | Deliverable d4.4b: Final version of plug-in for safety and multi criteria architecture modeling and benchmarking[END_REF]. Above all, these outcomes are based on formal methods, they are deterministically reproducible, and form a solid foundation for safety assurance and correct/safe-by-construction solutions.

VI. CONCLUSION AND FUTURE WORK

In the engineering of reliable and safe automotive systems, the process of mapping software to hardware is an essential design step. In this paper we presented a design space exploration approach for multi-criteria optimization of the deployment problem, formalizing constraints relevant for system development according to ISO26262.

Not limiting our interest to generating merely valid solutions, but in good ones, we developed a multi-objective optimization algorithm, which synthesizes solutions paretooptimized for safety, resource usage, timing and any other constraints the user defines. A state-of-the-art SMT solver is used in conjunction with the formalized constraints to find valid solutions, which satisfy the constraints, while a meta-search on top of the SMT solver provides the optimized solutions.

In our example, we derived 6 constraints and implemented an optimization algorithm for 4 criteria, with ongoing work to give users more freedom to define their own constraints and criteria. Above all, the generated results are based on formal methods, they are deterministically reproducible, and form a solid foundation for safety assurance and correct/safeby-construction solutions.

Our approach demonstrates the feasibility and effectiveness of using formal methods to generate correct solutions for safety-critical applications under real-world scenarios, increasing the confidence and validity of safety evidence for certification.

Solutions to software engineering problems are most useful when bolstered by tool-support; we integrated our work in a model-based framework, called AutoFOCUS3. Due to the seamless nature of AF3, our approach demonstrates how an integrated model-based framework can pragmatically provide support for practical problems in the development and certification of safety-critical systems in compliance with the relevant standards, and just as importantly, how formal methods can easily be made more accessible to practitioners without a formal background.

Fig. 1 :

 1 Fig. 1: Seamless model-based development in AF3

Fig. 4 :

 4 Fig. 4: Effect of Cost Constraint (non-uniform cost) on deployment (ASIL-D BUS)

TABLE I :

 I Target values for hardware architectural metrics

  B, which also has a PMHF value. Furthermore, we respect ASIL propagation, which means that tasks can only exchange messages via bus, if the bus is sufficiently reliable, as indicated by its PMHF value. This constraint affects the allocation of communciating tasks. If t

	1)
	2) PMHF Constraint for BUS: As defined in [2], if two
	tasks t on different nodes, such that (t i t k 2 T communicate with each other and are deployed j ), they have to i ) 6 = (t communicate over a bus b 2

i sends a message to t k and those tasks are mapped on different nodes, the constraint can be formalized as follows: b.asil t k .asil (2)

TABLE II :

 II Logical Architecture of the Case-Study of both a logical and technical architecture. The logical architecture consists of 48 components, connected by 65 channels. The components have different ASIL levels, as described in table II.The technical architecture consists of 9 nodes connected by a bus. Each hardware component was assigned a predetermined PMHF value (and ergo ASIL compliance) and cost (cf. tableIII). These values can, of course, be modified by the user to represent different hardware characteristics.

	ECUt	1	2	3	4	5	6	7	8	9
	PMHF 0.1	0.1	0.3	0.4	0.6 0.6	0.8	0.9	1.0
	ASIL	D	D	C	C	B	B	A	A	QM
	Cost	10	10	8	8	5	5	3	3	1

TABLE III :

 III Technical Architecture of the Case-Study

TABLE IV :

 IV Pareto deployments for industry-like use case

http://www.autosar.org/

http://www.safe-project.eu/


Keywords: Mathematics Subject Classification. 30D15, 41A05, 46E10, 44A35 entire functions, convolution equations, mean-periodic functions, interpolating sequences

EXPANSION IN SERIES OF EXPONENTIAL POLYNOMIALS OF MEAN-PERIODIC FUNCTIONS

H. OUERDIANE AND M. OUNA ÏES ABSTRACT. Let θ be a Young function and consider the space F θ (C) of all entire functions on C with θ-exponential growth. In this paper, we are interested in the solutions f ∈ F θ (C) of the convolution equation T f = 0, called mean-periodic functions, where T is in the topological dual of F θ (C). We show that each mean-periodic function admits an expansion as a convergent series of exponential polynomials.

INTRODUCTION.

A periodic function f with period t may be defined in terms of convolution equation as a function satisfying the convolution equation (δ t -δ 0 ) f = 0, while a function with zero average over an interval of length t > 0 satisfies the convolution equation µ f = 0, where µ is defined by < µ, f >=

1 t t/2 -t/2
f (x)dx. From the observation that the second notion is more natural from the point of view of experimental physics, Delsartes generalized the concept of periodic functions by introducing in [START_REF] Delsarte | Les fonctions moyennes-périodiques[END_REF] the notion of "mean-periodic" functions as the solutions of homogeneous convolution equations.

In this paper, we are dealing with the problem of expressing mean periodic functions as series of exponentials polynomials.

Let us denote by H(C) the space of all entire functions on C. Let θ : [0, +∞[→ [0, +∞[ be a Young function that is, a convex, continous and increasing function, vanishing at the origin and such that t = o(θ(t)). Let θ * be its Legendre transform, which is also a Young function. Denote by F θ (C) the space of all functions f ∈ H(C) such that, for all constants m > 0, [START_REF] Berenstein | Complex variables[END_REF] sup z∈C |f (z)|e -θ * (m|z|) . < ∞ endowed with the projective limit topology.

Examples of Young functions are

• θ(t) = t a , a > 1,

• θ(t) = t ln t -t,

• θ(t) = e t -1. We will also consider the limit case where θ(t) = t. In this case, the associated conjugate function θ * is formally infinite. Therefore, no growth condition of the type ( 1) is involved and we put F θ (C) = H(C) endowed with the topology of uniform convergence on compact sets.

It follows from the definitions that the spaces F θ (C) are invariant under translation and contain all exponential monomials z n e αz , n ∈ N, α ∈ C.

We will say that f ∈ F θ (C) is a mean-periodic function if, for a certain non zero analytic functional T ∈ F θ (C), f verifies the convolution equation [START_REF] Berenstein | Complex analysis and special topics in harmonic analysis[END_REF] T f = 0.

In this case, we say that f is T -mean-periodic.

If we denote by {α k } k the zeros of the Fourier-Borel transform of T and m k their order of multiplicity, then all exponential monomials z j e α k z , with j < m k are T -mean-periodic functions (see Lemma 5). Theses exponential monomials are called the elementary solutions of (2).

Let us note that the kernel of T is a closed subspace of F θ (C) which is invariant under translation.

Our work is related to the classical spectral synthesis problem, that is, the one of finding conditions under which a closed subspace S ∈ F θ (C) which is invariant under translation coïncides with the closure of the span of the exponential monomials contained in S. When this is the case, S is said to admit spectral synthesis. It is a famous result of L. Schwartz ([18]) that when we're dealing with H(C), every non zero closed invariant subspace admits spectral synthesis.

The problem of spectral synthesis for a large class of spaces of entire functions with growth conditions is dealt with in the works by I.F. Krasičkov ([11,[START_REF] Krasičkov | Closed ideals in locally convex algebras of entire functions. Algebras of minimal type[END_REF][START_REF] Krasičkov | Closed ideals in locally convex algebras of entire functions[END_REF]). These spaces have in common with our setting the cases θ(t) = t a .

The fundamental principal problem concerns closed invariant subspaces admitting spectral synthesis, in particular, when dealing with the kernel of T , it asks whether every solution to the equation ( 2) can be represented in terms of elementary solutions as an absolutely convergent series in F θ (C) of the form

k e zα k m k -1 l=0 c k,l z l .
This question is closely connected to the theory of interpolation in spaces of entire functions (see [START_REF] Berenstein | Complex analysis and special topics in harmonic analysis[END_REF], [START_REF] Berenstein | A new look at interpolation theory for entire functions of one variable[END_REF]).

We will use the interpolation result obtained in [START_REF] Ounaïes | Interpolation by entire functions with growth conditions[END_REF] to obtain an explicit expansion of every function in the kernel of T in terms of the elementary solutions (see Theorem 6), using an Abel summation procedure in order to make the sum convergent. In fact, we prove that any T -mean-periodic function f ∈ F θ (C) admits the following expansion as a convergent series in

F θ (C) (3) f (z) = k m k -1 l=0 c k,l   k j=1 e zα j P k,j,l (z)   ,
where P k,j,l are polynomials of degree < m j , explicitely given by ( 23) and (24) in terms of {(α k , m k )} k . Moreover, the coefficients c k,l verify the growth condition [START_REF] Isaacson | Analysis of numerical methods[END_REF] and can be explicitly computed in terms of f and T . When V = {(α k , m k )} k is an interpolating variety (see Definition 5), we don't need the Abellike summation, we simply obtain that any T -mean-periodic function f ∈ F θ (C) admits the following expansion as a convergent series in F θ (C)

(4) f (z) = k e zα k m k -1 l=0 d k,l z l l! ,
where the coefficients d k,l verify the growth estimate (26) (see Theorem 12). These results generalize those obtained in [START_REF] Berenstein | Complex analysis and special topics in harmonic analysis[END_REF] and [START_REF] Berenstein | A new look at interpolation theory for entire functions of one variable[END_REF], where the authors considered the case F θ (C) = H(C). In fact, they showed that, given T ∈ H (C)), there exists a sequence of indices

k 1 = 1 < k 2 < • • • such that any T -mean periodic function f ∈ H(C) admits a unique expansion, convergent in H(C), of the form (5) f (z) = n≥1 kn≤k<k n+1 e α k z m k -1 j=0 d k,j z j j! .
In [START_REF] Berenstein | Several complex variables. V: Complex analysis in partial differential equations and mathematical physics[END_REF], the sum converges by grouping the terms and not by an Abel process, but in general, the sequence {k n } n is not explicit, except in the case when V is an interpolating variety, where the sequence k n = n works, thus formula (5) leads to [START_REF] Berenstein | Dirichlet series and convolution equations[END_REF].

The paper is organized as follows : Section 2 is devoted to preliminary definitions and useful results from functional analysis. The main results are stated in Section 3 and the proofs are given in Section 4. Finally, in Section 5, we study the particular case when V is an interpolating variety. Note that the Legendre transform of a Young function is a Young function and θ * * = θ. We refer the reader to [START_REF] Krasnosel | Convex Functions and Orlicz Spaces[END_REF] for further details about Young functions.

PRELIMINARIES AND DEFINITIONS.

Throughout the paper, θ will denote either the function θ(x) = x or a Young function.

For any m > 0, consider E θ,m (C), the Banach space of all functions f ∈ H(C) such that

f θ,m := sup z∈C |f (z)|e -θ(m|z|) < +∞ and define G θ (C) = ∪ p∈N * E θ,p (
C) endowed with the inductive limit topology. It is clear that G θ (C) is an algebra under the ordinary multiplication of functions.

Remark 1. When θ(x) = x k , k ≥ 1, G θ (C)
is the space of all entire functions, either of order < k or of order k and finite type. In particular, when k = 1, G θ (C) is the space of all entire functions of exponential type, usually denoted by Exp(C).

We define the space F θ (C) as follows : (i) In the case where θ(x) = x, we put F θ (C) = H(C), the space of all entire functions endowed with the topology of uniform convergence on every compact of C. It is a Fréchet-Schwartz space (see [START_REF] Berenstein | Complex analysis and special topics in harmonic analysis[END_REF]).

(ii) In the case where θ is a Young function, we denote

F θ (C) = ∩ p∈N * E θ * ,1/p (C)
endowed with the projective limit topology. The space F θ (C) is a nuclear Fréchet space (see [START_REF] Gannoun | Un théorème de dualité entre espaces de fonctions holomorphes à croissance exponentielle[END_REF]), hence it is a Fréchet-Schwartz space (see [START_REF] Schwartz | Espaces nucléaires[END_REF]).

For any fixed ξ ∈ C, and l ∈ N, we will denote by M l,ξ the exponential monomial z → z l e ξz . It is easy to see that M l,ξ ∈ F θ (C). In the next we denote by F θ (C) the strong topological dual of F θ (C).

Let us recall some definitions and properties from functional analysis. We refer to [START_REF] Berenstein | Complex analysis and special topics in harmonic analysis[END_REF] for further details in the case (i) and to [START_REF] Gannoun | Un théorème de dualité entre espaces de fonctions holomorphes à croissance exponentielle[END_REF] for the case (ii).

To any fixed u ∈ C, define the translation operator τ u on F θ (C) by

(τ u f )(z) = f (z + u), for all f ∈ F θ (C) and z ∈ C.
It's easy to see that F θ (C) is invariant under these translation operators. For all S ∈ F θ (C) and f ∈ F θ (C), the function z →< S, τ z f >, where < , > denotes the duality bracket, is an element of F θ (C). Therefore, for any S ∈ F θ (C), the map S :

F θ (C) → F θ (C) defined by S f (z) =< S, τ z f >
is a convolution operator, i.e., it is linear, continuous and commute with any translation operator.

For any S ∈ F θ (C), the Fourier-Borel transform of S, denoted by L(S) is defined by

L(S)(ξ) =< S, e ξ• >
,

where e ξ• = M 0,ξ is the function z ∈ C → e ξz .
For any two elements S and

U of F θ (C), the convolution product S U ∈ F θ (C) is defined by ∀f ∈ F θ (C), < S U, f >=< S, U f > .
Moreover for any S, U ∈ F θ (C)

L(S U ) = L(S)L(U )
Under this convolution, F θ (C) is a commutative algebra admitting δ 0 , the Dirac measure at the origin, as unit.

Proposition 2. The Fourier-Borel transform L is a topological isomorphism between the algebras F θ (C) and G θ (C).

MAIN RESULTS.

Throughout the rest of the paper, let T be a fixed non-zero element of F θ (C). Our main goal in this section is to show that any function f ∈ F θ (C) satisfying the equation ( 6)

T f = 0 can be represented as convergent series of exponential-polynomials which are themselves solution of (6).

Definition. We say that a function f ∈ F θ (C) is "T -mean-periodic" if it satisfies the equation ( 6).

Denote by Φ the entire function in G θ (C) defined by Φ = L(T ). Before going further, let us show the following division property :

Lemma 3. Let h ∈ H(C) and g ∈ G θ (C). If g is not identically zero and if f = gh ∈ G θ (C), then h ∈ G θ (C).
Proof. Up to a translation, we may assume that g(0) = 0. Let us apply the minimum modulus theorem and it's corollary given in [START_REF] Berenstein | Complex analysis and special topics in harmonic analysis[END_REF]Lemma 2.2.11] to the function g in the disc of center 0 and radius 2 n+1 e, where n is any positive integer.

As g ∈ G θ (C), there exists p ∈ N * and C p > 0 (not depending on n) such that

max |ξ|≤2 n+3 e |g(ξ)| ≤ C p e θ(p2 n ) .
Thus, there exists ε p > 0 (not depending on n) and R n ,

2 n ≤ R n ≤ 2 n+1 such that min |ξ|=Rn |g(ξ)| ≥ ε p e -θ(p2 n ) .
Let n ∈ N and |ξ| = R n . As f ∈ G θ (C), there exists q > 0 and C q > 0 (not depending on n),

such that |f (ξ)| ≤ C q e θ(q2 n ) .
Using the convexity of θ and the fact that θ(0) = 0, we have

θ(p2 n ) ≤ 1 2 θ(p2 n+1 ).
If we assume, for example, that p ≥ q, we deduce that 4p|z|) .

|h(ξ)| = |f (ξ)| 1 |g(ξ)| ≤ C q ε p e θ(q2 n )+θ(p2 n ) ≤ B p e θ(p2 n+1 ) . Now let z ∈ C, be such that 2 n-1 ≤ |z| ≤ 2 n < R n . By the maximum modulus theorem, |h(z)| ≤ B p e θ(p2 n+1 ) ≤ B p e θ(
This proves that h ∈ G θ (C).

Corollary 4. In the case where Φ has no zeros, the only mean-periodic function f ∈ F θ (C) is the zero function.

Proof. Assume that Φ has no zeros. Then 1 Φ ∈ H(C) and, by Lemma 3,

1 Φ ∈ G θ (C). By Proposition 2, S = (L) -1 ( 1 Φ ) ∈ F θ (C).
Then, we have S T = T S = δ 0 . If we assume T f = 0, then δ 0 f = f = 0.

We will throughout the rest of the paper assume that Φ has zeros, and denote them by

|α 0 | ≤ |α 1 | ≤ • • • ≤ |α k | ≤ • • • , α k = α k if k = k .
We will denote by m k be the order of multiplicity of Φ at α k and we will consider the "multiplicity variety" V = {(α k , m k )} k∈N (see [START_REF] Berenstein | Complex variables[END_REF] for an introduction to the concept of multiplicity variety). We may denote V = Φ -1 (0).

Lemma 5. (i) For all ξ ∈ C and l ∈ N, we have < T, M l,ξ >= Φ (l) (ξ). (ii) Each exponential monomial M l,α k , for 0 ≤ l < m k , is T -mean-periodic.

Proof.

To prove (i), we proceed by induction on l ≥ 0. The property is true for l = 0 by definition of the Fourier-Borel transform of T .

Suppose the property true for l. Let ξ ∈ C be fixed. Let us verify that the function M l,ξ+u -M l,ξ u converges in F θ (C) to M l+1,ξ when u tends to 0. For all z ∈ C and u ≤ 1, we have

e uz -1 u -z = uz 2 n≥2 (uz) n-2 n! ≤ |u||z| 2 e |z| .
This implies that

M l,ξ+u (z) -M l,ξ (z) u -M l+1,ξ (z) = |z l e ξz | e uz -1 u -z ≤ |u||z| l+2 e (1+|ξ|)|z| .
Therefore, M l,ξ+u -M l,ξ u converges to M l+1,ξ for the topology of F θ (C) when u tends to 0. From this, we obtain

Φ (l+1) (ξ) = lim u→0 Φ (l) (ξ + u) -Φ (l) (ξ) u = lim u→0 < T, M l,ξ+u > -< T, M l,ξ > u (7) = lim u→0 < T, M l,ξ+u -M l,ξ u >=< T, M l+1,ξ >, (8)
by continuity of T . This completes the proof of (i). In order to prove (ii), it is sufficient to see that

T M l,α k (z) =< T, τ z M l,α k >= e α k z l n=0 C n l z l-n < T, M n,α k >= e α k z l n=0 C n l z l-n Φ (n) (α k ).
Theorem 6. (i) Any T -mean-periodic function f ∈ F θ (C) admits the following expansion as a convergent series in F θ (C)

(9) f (z) = k≥0 m k -1 l=0 c k,l   k j=0 e zα j P k,j,l (z)   ,
where P k,j,l are the polynomials of degree < m j given by ( 23) and (24). The coefficients c k,l verify the following estimate

(10) ∀m > 0, k≥0 e θ(m|α k |)   m k -1 l=0 |c k,l |(|α k | + 1) -(m 1 +•••+m k-1 +l)   < +∞
and are given by

c k,l =< S k,l , f > where S k,l ∈ F θ (C) is defined by L(S k,l )(ξ) = (ξ -α k ) l k-1 n=0 (ξ -α n ) mn .
(ii) Conversely, any such serie whose coefficients c n,l satisfy the estimate [START_REF] Isaacson | Analysis of numerical methods[END_REF] converges in F θ (C) to a function f solving the equation ( 6).

Corollary 7.

Assume that all the multiplicities m k are equal to 1. Then (i) any T -mean-periodic function f ∈ F θ (C) admits the following expansion as a convergent series in F θ (C)

(11) f (z) = k≥0 c k   k j=0 e zα j 0≤n≤k,n =j (α j -α n ) -1   ,
where the coefficients c k satisfy the following estimate

(12) ∀m > 0, k≥0 e θ(m|α k |) |c k |(|α k | + 1) -(k-1) < +∞
and are given by

c k =< S k , f > where S k ∈ F θ (C) is defined by L(S k )(ξ) = k-1 n=0 (ξ -α n ) mn .
(ii) Conversely, any such series whose coefficients c k satisfy the estimate [START_REF] Krasičkov | Closed ideals in locally convex algebras of entire functions. Algebras of minimal type[END_REF] converges in F θ (C) to a function f solving the equation (6).

PROOF OF THEOREM 6

It will be a crucial point in the proof of the main theorem, to determine the image of the restriction operator ρ defined on G θ (C) by

ρ(g) = { g l (α k ) l! } k≥0,0≤l<m k , g ∈ G θ (C).
As an immediate consequence of Lemma 3, we have the following lemma. We are going to use a characterization, obtained in [START_REF] Ounaïes | Interpolation by entire functions with growth conditions[END_REF], of the elements a = {a k,l } k∈N,0≤l<m k-1 belonging to ρ(G θ (C)). This characterization is given in terms of growth conditions involving the divided differences (see [START_REF] Isaacson | Analysis of numerical methods[END_REF] for further details about divided differences).

To any discrete doubly indexed sequence a = {a k,l } k∈N,0≤l<m k of complex numbers, we associate the sequence of divided differences Ψ(a) = {b k,l } k∈N,0≤l<m k . We recall that they are the coefficients of the Newton polynomials, [START_REF] Krasičkov | Closed ideals in locally convex algebras of entire functions[END_REF] Q q (ξ) =

q k=0 k-1 n=0 (ξ -α n ) mn   m k -1 l=0 b k,l (ξ -α k ) l   ,
defined, for any q ≥ 1, as the unique polynomial of degree

m 0 + • • • + m q -1 such that Q (l) q (α k ) l! = a k,l , for 0 ≤ k ≤ q and 0 ≤ l ≤ m k -1.
When all the multiplicities m k = 1, we may give a simple formula for the coefficients b k :

b k = k j=0 a j 0≤n≤k,n =j (α j -α n ) -1 .
In the general case, we define them by induction :

b 1,l = a 1,l , for all 0 ≤ l ≤ m 1 -1, b k,0 = a k,0 -Q k=1 (α k ) Π k-1 (α k ) , b k,l = a k,l - Q (l) k-1 (α k ) l! -l-1 n=0 1 (l-n)! Π (l-k) k-1 (α j )b k,n Π k-1 (α k ) for 1 ≤ l ≤ m k -1
where we have denoted by

Π k (ξ) = k n=0 (ξ -α n ) mn , for all k ≥ 0.
In [START_REF] Ounaïes | Interpolation by entire functions with growth conditions[END_REF], we showed that the elements a = {a k,l } k∈N,0≤l<m k belonging to ρ(G θ (C)) are precisely those verifying the growth condition

sup k≥0 sup 0≤l<m k |b k,l |(|α k | + 1) m 1 +•••+m k-1 +l e -θ(m|α k |) < +∞, for a certain m > 0, where b = {b k,l } k,0≤l<m k = Ψ -1 (a).
In order to give a topological structure to this space, let us denote by B θ,m (V ) the Banach space of all doubly indexed sequences of complex numbers b

= {b k,l } k∈N,0≤l<m k such that b θ,m = sup k∈N sup 0≤l<m k |b k,l |(|α k | + 1) m 1 +•••+m k-1 +l e -θ(m|α k |) < +∞.
Let us consider the space A θ,m (V ) = Ψ -1 (B θ,m (V )), that is, the space of all doubly indexed sequences of complex numbers a = {a k,l } k∈N * ,0≤l<m k such that

Ψ(a) θ,m < +∞.
It is easy to see that A θ,m (V ) endowed with the norm a θ,m = Ψ(a) θ,m is a Banach space and that Ψ is an isometry from A θ,m (V ) into B θ,m (V ). Now, we define the spaces

A θ (V ) = ∪ p∈N * A θ,p (V ) and B θ (V ) = ∪ p∈N * B θ,p (V )
endowed with the topology of inductive limit of Banach spaces. We define the linear map

α = Ψ • ρ • L : F θ (C) → B θ (V ).
Proposition 9. The map α is continuous and surjective.

Proof. By Proposition 2, we know that L :

F θ (C) → G θ (C) is a topological isomorphism.
The fact that the operator ρ : G θ (C) → A θ (V ) is continuous and surjective are easy consequences of [16, Proposition 1.8 and Theorem 1.11].

Finally, by construction, it is clear that

Ψ : A θ (V ) → B θ (V )
is a topological isomorphism.

Recall that F θ (C) is a Fréchet-Schwartz space, therefore it is reflexive. Then, the transpose α t of α is defined from the strong dual of B θ (V ), denoted by B θ (V ), into F θ (C).

In the next lemma, we will characterize the dual space B θ (V ).

Lemma 10. The space B θ (V ) is topologically isomorphic through the canonical bilinear form

< c, b >= +∞ k=0 m k -1 l=0 c k,l b k,l
to the space C θ (V ) = ∩ p∈N * C θ,p (V ) endowed with the projective limit topology, where, for all p, C θ,p (V ) is the Banach space of the sequences c = {c k,l } k≥0,0≤l<m k such that

(14) c θ,p := k≥0 e θ(p|α k |)   m k -1 l=0 |c k,l |(|α k | + 1) -(m 1 +•••+m k-1 +l)   < +∞. Moreover, C θ (V ) is a Fréchet-Schwartz space.
Proof.

Let us show that β :

C θ (V ) → B θ (V ) defined by β(c)(b) =< c, b >= +∞ k=0 m k -1 l=0 c k,l b k,l is a topological isomorphism. Let c = {c k,l } k,0≤l<m k be an element of C θ (V ) and b = {b k,l } k,0≤l<m k ∈ B θ,p (V )
, for a certain p. For any k ≥ 0, we have, by definition of b θ,p ,

m k -1 l=0 |b k,l c k,l | ≤ e θ(p|α k |) b θ,m m k -1 l=0 |c k,l |(|α k | + 1) -(m 1 +•••+m k-1 +l) .
Using the estimate ( 14), we see that the sum converges (absolutely) and that

| < c, b > | ≤ c θ,p b θ,p .
This shows the continuity of β. Let B k,l be the doubly indexed sequence of C defined by (using the Kronecker symbols) : [START_REF] Ounaïes | Geometric Conditions for Interpolation in Weighted Spaces of Entire Functions[END_REF] B k,l = {δ kj δ ln } j,0≤n<m j .

We easily see that B k,l ∈ B θ,p (V ). For all k and 0 ≤ l < m k , we have c k,l =< β(c), B k,l >. It is then clear that β is injective. Conversely, to an element ν ∈ B θ (V ), consider the doubly indexed sequence c = {c k,l } k,0≤l<m k defined by

c k,l =< ν, B k,l > We verify that c ∈ C θ (V ). let p ∈ N * be fixed and define b = { bk,l } k,0≤l<m k by bk,l = e θ(p|α k |) ck,l |c k,l | (|α k | + 1) -(m 1 +•••+m k-1 +l) if c k,l = 0, bk,l = 0 otherwise. It is clear that b ∈ B θ,p (V ) and that b θ,p ≤ 1.
Therefore, all the finite sequences bK = K k=0 m k -1 l=0 bk,l B k,l satisfy bK θ,p ≤ 1. Denoting by ν p the operator norm, we have, for all K,

| < ν, bK > | ≤ ν p bK θ,p ≤ ν . On the other hand, < ν, bK >= K k=0 m k -1 l=0 bk,l < ν, B k,l >= K k=0 e θ(p|α k |) m k -1 l=0 |c k,l |(|α k | + 1) -(m 1 +•••+m k-1 +l) ,
by definition of bk,l . Letting K tend to infinity, we obtain that c ∈ C θ,p (V ) and that [START_REF] Ounaïes | Interpolation by entire functions with growth conditions[END_REF] c θ,p ≤ ν p .

Consider now an element

b = {b k,l } k,0≤l<m k of B θ,p (V ) and put b K = K k=0 m k -1 l=0 b k,l B k,l .
Let q be an integer strictly larger than p. Note that by convexity of θ, for all k the following inequality holds

(17) -θ(q|α k |) + θ(p|α k |) ≤ -(1 -p/q)θ(q|α k |).
Using this inequality, we find

b -b K θ,q ≤ b θ,p sup k>K e -θ(q|α k |)+θ(p|α k |) ≤ b θ,p e -(1-p/q)θ(q|α K |) .
We readily deduce that b K converges to b when K tends towards infinity and that β(c) = ν.

The continuity of β -1 is a direct consequence of the inequality [START_REF] Ounaïes | Interpolation by entire functions with growth conditions[END_REF]. We have proved that β is a topological isomorphism.

In order to prove that C θ (V ) is a Fréchet-Schwartz space, in view of [START_REF] Berenstein | Complex analysis and special topics in harmonic analysis[END_REF]Proposition 1.4.8.], it is sufficient to see that, for any p ∈ N * , the canonical injection

i p : C θ,p+1 (V ) → C θ,p (V )
is compact. Let {c n } n be a sequence of elements in C θ,p+1 (V ) such that, for all n, c n θ,p+1 ≤ 1. It suffices to show that one can extract a subsequence of {c n } n converging in C θ,p (V ).

It is easy to see that, for all k ∈ N and 0 ≤ l < m k the sequence {c n k,l } n is bounded. Thus, up to taking a subsequence, we may assume without loss of generality that c n k,l converges to a certain c k,l ∈ C. Putting c = {c k,l } k,0≤l<m k , we readily see that c ∈ C θ,p+1 (V ) and c θ,p+1 ≤ 1.

Let us verify that c n -c θ,p tends to 0 when n tends to infinity. We assume that |α k | → ∞, otherwise, the result is trivial. Then, again using inequality [START_REF] Schwartz | Espaces nucléaires[END_REF] we find that e θ(p|α k |)-θ((p+1)|α k |) tends to 0 when k tends towards infinity. Let ε > 0. For a certain K ∈ N and for all k ≥ K, e θ(p|α k |)-θ((p+1)|α k |) < ε 4 . Thus, for all n ∈ N,

k≥K e θ(p|α k |) m k -1 l=0 |c n k,l -c k,l |(|α k | + 1) -(m 1 +•••+m k-1 +l) (18) ≤ ε 4 k≥K e θ((p+1)|α k |) m k -1 l=0 |c n k,l -c k,l |(|α k | + 1) -(m 1 +•••+m k-1 +l) (19) ≤ ε 4 c n -c θ,p+1 ≤ ε 4 ( c n θ,p+1 + c θ,p+1 ) ≤ ε 2 . (20) (21)
Moreover, for a certain N ∈ N and for all n ≥ N , we have

K-1 k=0 e θ(p|α k |)   m k -1 l=0 |c n k,l -c k,l |(|α k | + 1) -(m 1 +•••+m k-1 +l)   ≤ ε 2 .
Finally, for n ≥ N , c n -c θ,p < ε.

From now on, we will identify B θ (V ) with the space C θ (V ). The duality is given by, for all

c = {c k,l } k,0≤l<m k ∈ C θ (V )and for all b = {b k,l } k,0≤l<m k ∈ B θ (V ), (22) < c, b >= +∞ k=0 m k -1 l=0 c k,l b k,l .
The next step is to prove the following lemma :

Lemma 11. (i) α t is a topological isomorphim onto its image and Im α t = (Ker α) • , the orthogonal space of Ker α .

(ii) Ker α = {T U, U ∈ F θ (C)}. (iii) (Ker α) • =Ker T = {f ∈ F θ (C) | T f = 0}.
Proof. (i) From Proposition 9, α is a surjective continuous linear map. Therefore, α t is a topological isomorphism onto its image and Im α t = (Ker α) • (see [START_REF] Berenstein | Complex analysis and special topics in harmonic analysis[END_REF]Proposition 1.4.12]). (ii) Recalling Remark 8, we have

Ker α = Ker (ρ • L) = L -1 (Kerρ) = {T L -1 (g), g ∈ G θ (C)}) = {T U, U ∈ F θ (C)}.
(iii) Let f be an element of (Ker α) • . For all z ∈ C,

(T f )(z) =< T, τ z f >=< T, δ z f >=< T δ z , f >= 0, using the fact that T δ z ∈ Ker α.
Conversely, let f ∈ F θ (C) be such that T f = 0 and let U ∈ F θ (C). We have

< T U, f >=< U, T f >= 0.
This shows that f ∈(Ker α) • and concludes the proof of the lemma. Let us proceed with the proof of Theorem 6.

(i) Let f ∈ F θ (C) be a T -mean-periodic function, that is, f ∈ Ker T . From Lemmas 11 and 10, there is a unique sequence c ∈ C θ (V ) such that f = α t (c).

For z ∈ C, denoting by δ z the Dirac measure at z, we have

f (z) =< δ z , f >=< δ z , α t (c) >=< c, α(δ z ) >=< c, Ψ(ρ(g z )) >
where we have denoted by

g z = L(δ z ), that is, the function in G θ (C) defined by g z (ξ) = e zξ . Let us compute Ψ(ρ(g z )) = b(z) = {b k,l (z)} k,0≤l<m k , which is an element of B θ (V )
. By well known formulas about Newton polynomials (See, for example [2, Definition 6.2.8]), we have, for k ∈ N, and denoting by

∂ m j = 1 m! ∂ m ∂α m j , for 0 ≤ l < m k , b k,l (z) = ∂ m 1 -1 1 • • • ∂ m k-1 -1 k-1 ∂ l k   k j=0 e zα j 0≤n≤k,n =j (α j -α n ) -1   = k j=0 e zα j P k,j,l (z),
where we have denoted by

(23) P k,j,l (z) = m k -1 i=0 z i i! ∂ m j -1-i i   0≤n≤k-1,n =j (α j -α n ) -mn (α j -α k ) -(l+1)   and, for 0 ≤ l < m k , ( 24
) P k,k,l (z) = l i=0 z i i! ∂ l-i k   0≤n≤k-1 (α k -α n ) -mn   .
Thus,

f (z) = k≥0   m k -1 l=0 c k,l b k,l (z)   = k≥0   m k -1 l=0 c k,l k j=0 e zα j P k,j,l (z)   .
So, the equality (11) is established.

Let us verify the convergence in F θ (C) of the series. Case where θ(x) = x. Here, F θ (C) = H(C). We have to verify that the serie converges uniformly on every compact of C. Let p ∈ N * and z ∈ C, |z| ≤ p.

We have, for all ξ ∈ C, |g z (ξ)| = |e zξ | ≤ e p|ξ| , that is,

g z θ,p ≤ 1.
Thus, by continuity of Ψ • ρ, there exists p ∈ N * and C p > 0 such that b(z) θ,p ≤ C p g z θ,p ≤ C p .

For all k ≥ 0, we have

m k -1 l=0 c k,l b k,l (z) ≤ b(z) θ,p m k -1 l=0 |c k,l |(|α k | + 1) -(m 1 +•••+m k-1 +l) e θ(p |αn|) .
We obtain

sup |z|≤p m k -1 l=0 c k,l b k,l (z) ≤ C p m k -1 l=0 |c k,l |(|α k | + 1) -(m 1 +•••+m k-1 +l) e θ(p |α k |)
Recalling that c ∈ C θ (V ), the right term is the general term of a convergent serie, thus, the right-hand side of ( 11) is convergent in F θ (C). Moreover,

sup |z|≤p k≥0 m k -1 l=0 c k,l b k,l (z) ≤ C p c θ,p .
Case where θ is a Young function.

For any p ∈ N * , observe that g z θ,p ≤ e θ * ( 1 |z|) . Thus, by continuity of Ψ • ρ, there exists p ∈ N * and

C p > 0 such that b(z) θ,p ≤ C p g z p ≤ C p e θ * ( 1 p |z|) .
For all k ≥ 0 and z ∈ C, we have

m k -1 l=0 c k,l b k,l (z) ≤ b(z) θ,p m k -1 l=0 |c k,l |(|α k | + 1) m 1 +•••+m k-1 +l e -θ(p |α k |) .
We obtain

sup z∈C m k -1 l=0 c k,l b k,l (z) e -θ * ( 1 p |z|) ≤ C p m k -1 l=0 |c k,l |(|α k | + 1) m 1 +•••+m k-1 +l e -θ(p |α k |) .
As in the previous case, we deduce that the right-hand side of ( 11) is absolutely convergent in F θ (C). Moreover,

sup z∈C k≥0 m k -1 l=0 c k,l b k,l (z) ≤ C p c θ,p .
In order to find an explicit formula for the coefficients c n,l , consider the elements B k,l of B θ (C) defined by [START_REF] Ounaïes | Geometric Conditions for Interpolation in Weighted Spaces of Entire Functions[END_REF] and observe that, by the definition of the Newton polynomials (see [START_REF] Krasičkov | Closed ideals in locally convex algebras of entire functions[END_REF]) with respect to the coefficients of B k,l , for all q ≥ k, we have

Q q (ξ) = (ξ -α k ) l k-1 l=0 (ξ -α l ) m l
and for q < k, Q q = 0. We readily deduce that α(S k,l

) = Ψ • ρ • L(S k,l ) = B k,l .
Now, for all k ∈ N and 0 ≤ l < m k , < S k,l , f >=< S k,l , α t (c) >=< α(S k,l ), c >=< B k,l , c >= c k,l .

(ii) The converse part is easily deduced from the proof of (i) and Lemma 5.

CASE WHERE V IS AN INTERPOLATING VARIETY.

Definition. We say that V is an interpolating variety for G θ (C) if, for any doubly indexed sequence a = {a k,l } k∈N * ,0≤l<m k such that, for a certain m > 0,

sup k∈N m k -1 l=0 |a k,l |e -θ(m| k |) < +∞,
there exists a function g ∈ G θ (C) such that, for all k and all 0 ≤ l < m k -1,

g (l) (α k ) l! = a k,l .
We assume from now on that V is an interpolating variety for G θ (C). Then we have the following result :

Theorem 12. (i) Any T -mean-periodic function f ∈ F θ (C) admits the following expansion as a convergent series in F θ (C) (25) f (z) = k≥0 e zα k m k -1 l=0 d k,l z l l! ,
where the coefficients a k,l verify the following estimate :

(26) k≥0 e θ(m|α k |)   m k -1 l=0 |d k,l |   < +∞
for every m > 0. Moreover, for all k ∈ N and 0 ≤ l < m k , we have the equality Note that L(T k,l ) ∈ G θ (C) by Proposition 3.

d k,l =< T k,l , f > where T k,l ∈ F θ (C) is defined by L(T k,l )(ξ) = Φ(ξ)(ξ -α k ) l-m k (m k !/Φ (m k ) (α k )), (
Remark 13. In the case where θ(x) = x, this is also a consequence of [2, Theorem 6.2.6.].

We will denote by A θ,m (V ) the space of all doubly indexed sequences of complex numbers a = {a k,l } k∈N,0≤l<m k such that

a θ,m := sup k∈N m k -1 l=0 |a k,l |e -θ(m|α k |) < +∞ and A θ (V ) = ∪ p∈N * A θ,p (V )
endowed with the strict inductive limit of Banach spaces. We define the linear map

α = ρ • L : F θ (C) → A θ (V ).
Proposition 14. The map α is continuous and surjective.

Proof.

It is sufficient to show that the map ρ : G θ (C) → A θ (V ) is continous and surjective. The surjectivity follows from the fact that V is an interpolating variety.

In order to show the continuity, let g ∈ G θ,p (C) and let z ∈ C. By the Cauchy estimates applied to the disc of center z and radius 2, for all l ∈ N,

g (l) (z) l! ≤ 1 2 l sup |ξ-z|≤2 |g(ξ)|.
For |ξ -z| ≤ 2, we have |g(ξ)| ≤ g θ,p e θ(p|ξ|) ≤ g θ,p e θ(2p+p|z|) ≤ g θ,p e 1/2θ(4p) e 1/2θ(2p|z|) by convexity of θ. Thus, 2p|z|) .

∞ l=0 g l (z) l! ≤ 2 g θ,p e 1/2θ(2p) e θ(
In particular, we deduce that ρ(g) ∈ A θ,2p (V ) and that ρ(g) θ,2p ≤ 2 g θ,p e 1/2θ(2p) .

The continuity of ρ follows from the last inequality and the surjectivity from the definition 5. We need to characterize A θ (V ), the strong dual of A θ (V ).

Lemma 15. The space A θ (V ) is topologically isomorphic to the space D θ (V ) = ∩ p∈N * C θ,p (V ) endowed with the projective limit topology, where, for all p, D θ,p (V ) is the Banach space of the sequences d

= {d k,l } k,0≤l<m k such that (27) d θ,p := k≥0 e θ(p|α k |)   m k -1 l=0 |d k,l |(|α k | + 1) -(m 1 +•••+m k-1 +l)   < +∞.
Moreover, D θ (V ) is a Fréchet-Schwartz space.

The proof is similar to the one of Lemma 10. Lemma 8 still holds with the new definition of α. We are now ready to prove Theorem 12.

By Lemma 8, any T -mean-periodic function f is the image by α t of a unique d ∈ A θ (V ). We have, for all z ∈ C, f (z) =< δ z , f >=< δ z , α t (d) >=< d, α(δ z ) >=< d, ρ(g z ) >= The last equality follows from the observation that α(T k,l ) = B k,l .

The rest of the proof is similar to the one of Theorem 6.

Let us recall some results about interpolating varieties that enables one to determine whether V is interpolating or not. The following is an analytic characterization given in [2, Chapter 2]. The spaces of entire functions considered are slightly different, but is clear how to adapt these results to our spaces.

Theorem 16. Assume V = Φ -1 (0). Then V is an interpolating variety for G θ (C) if and only if, there are constants ε > 0 and m > 0 such that, for all k and all 0 ≤ l < m k ,

Φ (m k ) (z) l! ≥ εe -θ(m|α k |) .
We also have a geometric characterization of interpolating varieties, in terms of the distribution of the points {(α k , m k )} k .

Define the counting function and the integrated counting function : Actually, in this paper, since V = Φ -1 (0) and Φ ∈ G θ (C), condition (28) is necessarily verified (see [START_REF] Ounaïes | Interpolation by entire functions with growth conditions[END_REF]Theorem 1.13]). Thus, V is an interpolating variety if and only if condition (29) holds.

Remark 18. We can obtain Theorem 12 as a corollary of Theorem 6, using the density condition (29). This second proof is rather technical, we will skip it here. Let us just give the correspondence between the coefficients c k,l and d k,l :

d k,l = m k -1 i=l c k,i ∂ i-l k   0≤n≤k-1 (α k -α n ) -mn   (30) + ∞ j=k+1 m j -1 i=0 c j,i ∂ m k -1-l k   0≤n≤j-1,n =k (α k -α n ) -mn (α k -α j ) -(i+1)   , ( 31
)
the convergence of the second sum being a consequence of conditions ( 29) and ( 28). In the case where all m k = 1, we have

d k = ∞ j=k c j 0≤n≤j,n =k (α k -α n ) -1 .

  Definition. A function θ : [0, +∞[→ [0, +∞[ is called a Young function if it is convex, continuous, increasing and verifies θ(0) = 0 and r = o(θ(r)) when r → +∞. Definition. Let θ be a Young function. The Legendre transform θ * of θ is the function defined by θ * (x) = sup t≥0 (tx -θ(t)).

Lemma 8 .

 8 The kernel of the restriction operator ρ is the ideal generated by Φ in G θ (C)}, i.e., Ker ρ = {Φg, g ∈ G θ (C)}.

  ii) Conversely, any such series whose coefficients d k,l satisfy the estimate (26) converges in F θ (C) to a function f solving the equation (6).

k≥0 e zα k m k - 1

 1 l=0 z l l! d k,l .To compute the coefficients d k,l :< T k,l , f >=< T k,l , α t (d) >=< d, α(T k,l ) >= d k,l .

Definition.

  For z ∈ C and r > 0,n(z, r) = |z-α k |≤r m k , N (z, r) = r 0 n(z, t) -n(z, 0) t dt + n(z, 0) ln r = 0<|z-α k |≤r m k ln r |z -α k | + n(z, 0) ln r.Adapting[START_REF] Berenstein | Interpolating varieties for spaces of meromorphic functions[END_REF] Corollary 4.8] or [15, Theorem 2.9] to our spaces :Theorem 17. V is an interpolating variety for G θ (C) if and only if conditions(28) ∃A > 0, ∃m > 0 ∀R > 0, N (0, R) ≤ A + θ(mR) and (29) ∃A > 0, ∃m > 0 ∀k ∈ N, N (α k , |α k |) ≤ A + θ(m|α k |)hold.


Yoann Roth
email: yoann.roth@cea.fr

Jean-Baptiste Dor
email: jean-baptiste.dore@cea.fr

Laurent Ros
email: laurent.ros@gipsa-lab.grenoble-inp.fr

Vincent Berg
email: vincent.berg@cea.fr

Turbo-FSK: a New Uplink Scheme for Low Power Wide Area Networks

Keywords: Turbo code, FSK, Low rate, Low SNR, Internet of Things, IoT, Machine-to-Machine, M2M, Low Power Wide Area, LPWA, Shannon's limit, Channel Capacity

The Internet of Things aims to connect several billions of devices. Terminals are expected to be low cost, low power, and able to achieve successful communication at long range. While current Machine-to-Machine technologies tend to use spreading factors to meet the required specifications, we propose a more sophisticated use of redundant waveforms in a scheme called Turbo-FSK. This scheme involves Frequency-Shift-Keying (FSK) modulation at the transmission, and a turbodecoder dedicated to the FSK waveforms at the receiver. Highly robust communication is achieved with a mere transmitter, as complexity is deported on the receiver side. Results are compared to common modulations using spreading factors, a significant gain in performance is achieved even with small packet sizes.

I. INTRODUCTION

Machine-to-Machine (M2M) communication is growing exponentially such that several billions of devices are expected to be connected to the Internet-of-Things (IoT) in the next decade [START_REF] Rebbeck | Low-powered wireless solutions have the potential to increase the M2M market by over 3 billion connections[END_REF], [START_REF] Ghosh | Low Power Wide Area Machine-to-Machine Communications using LTE[END_REF]. In this field, research on the design of a Low Power Wide Area (LPWA) network is required where challenges for terminals include low power consumption, low cost and fair sensitivity. The choice of the physical layer has a critical impact on these issues: it needs to be robust, efficient, and working at very low levels of sensitivity. It can be assumed that the numerous connected devices only transmit in a sporadic way, sending a few packets from time to time [START_REF] Ghosh | Low Power Wide Area Machine-to-Machine Communications using LTE[END_REF]: a low data rate communication per user is expected. This scenario is currently considered by the first generation of IoT commercial networks such as [START_REF]SigFox website[END_REF], [START_REF]LoRa from Semtech[END_REF], [START_REF] Young | Introduction to "Clean-Slate" Cellular IoT radio access solution[END_REF].

Reducing the level of sensitivity is challenging as the radio-frequency front end needs to be optimized, and the physical layer, the modulation and associated signal processing have to be carefully chosen. M -ary Orthogonal modulations appear to be a natural choice for low data rate and low power applications, as they offer a possible trade-off between energy and bandwidth. These modulations are power efficient and are known to reach the channel capacity for infinite sizes of alphabet M (hence infinite size of signaling waveform duration) [START_REF] Proakis | Digital Communications 3rd Edition, ser. Communications and signal processing[END_REF]. However, since an infinite size alphabet is an unrealistic option, a well known alternative is to increase energy efficiency by means of channel coding [START_REF] Costello | Channel coding: The road to channel capacity[END_REF], notably using turbo processing [START_REF] Berrou | Near Shannon limit error-correcting coding and decoding: Turbo-codes. 1[END_REF].

The idea of combining orthogonal codes in a parallel concatenated scheme with turbo decoding was first proposed in [START_REF] Ping | Iterative decoding of concatenated Hadamard codes[END_REF], using Hadamard binary codes. A further study [START_REF] Ping | Low-rate turbo-Hadamard codes[END_REF] observed strong error floors because of the poor minimal distance of the code. The authors proposed the addition of a convolutional code before the Hadamard mapping and achieved outstanding performance for large block sizes and large sizes of alphabet; limits of such a code have been studied in [START_REF] Wu | On the limiting performance of turbo-Hadamard codes[END_REF] and extensions have been proposed in [START_REF] Shimanuki | Improvements and extensions of low-rate Turbo-Hadamard codes[END_REF]. On the other hand, Frequency-Shift-Keying (FSK) is an interesting choice of orthogonal modulation because of its constant envelope property, the simplicity of the modulator and its robustness to frequency-selective multi-path channels. Demodulation may simply be based on Fast-Fourier-Transform (FFT) as in an Orthogonal-Frequency-Division-Multiplexing receiver [START_REF] Kikuchi | Highly-sensitive coherent optical detection of M-ary frequency-shift keying signal[END_REF]. FSK has been exploited in a turbo coding scheme, Bit-Interleaved Coded Modulation with Iterative Decoding (BICM-ID) (see [START_REF] Liang | Algorithm for joint decoding of turbo codes and M-ary orthogonal modulation[END_REF], [START_REF] Panaro | Simple iterative decoding for bit-interleaved coded orthogonal modulation[END_REF]), where the steps of binary channel coding and M -ary FSK modulation are separated by an interleaver to ensure diversity at the receiving side. The receiver shares information of the decoded soft bits between the decoder and the orthogonal soft demodulator. Even though this scheme offers good performance, complexity is high because of the use of a 64-state convolutional encoder, and a large block size is used.

In this paper, we propose a new scheme called Turbo-FSK, and perform its analysis. Unlike [START_REF] Panaro | Simple iterative decoding for bit-interleaved coded orthogonal modulation[END_REF], where a binary coding step was performed before FSK signaling, the new idea is to directly consider FSK signals as codewords. This scheme is an extension of the Turbo Hadamard scheme from [START_REF] Ping | Low-rate turbo-Hadamard codes[END_REF] to the FSK modulation, replacing the binary Hadamard codes by the FSK waveforms. The transmitter uses then orthogonal FSK waveforms as codewords in a concatenated scheme, and the receiver is based on turbo decoding of these FSK codewords. To the best of our knowledge, FSK has never been presented before as potential orthogonal modulation for the scheme proposed in [START_REF] Ping | Low-rate turbo-Hadamard codes[END_REF]. Neither decoder computations nor performance have been introduced. Also, the use of such a scheme as a physical layer for low data rate communications has never been explored. In our present study, after the presentation of the low complexity transmitter, the equations of the turbo decoder are derived for the FSK case. Performance of the Turbo-FSK is compared to other known modulations, including BICM-ID and spreading factors-based schemes, showing an interesting alternative. The use of Turbo-FSK scheme for LPWA is justified as the uplink M2M communication needs to be power efficient, low data rate and with fair sensitivity.

The paper is organized as follows. The motivations that led us to the use of such a scheme are presented in Section II. The system model is described in Section III and Section IV introduces the Turbo-FSK soft decoding computations. Simulation results are presented in Section V and Section VI concludes the paper.

II. MOTIVATIONS

Because long range is linked to low sensitivity level and the terminal must be kept simple, a widely used technique to improve sensitivity of a primary technique is achieved by means of a spreading, or repetition factor, λ. At the reception in presence of Additive White Gaussian Noise (AWGN), the required Signal-to-Noise Ratio (SNR) using a spreading factor (denoted SNR λ ) is decreased (i.e improved) as

SNR (dB) λ = SNR (dB) 1 -10 log 10 (λ), (1)
where SNR 1 is the required SNR of the primary technique. This is done at the cost of a data transmission rate reduction equal to the factor λ. However, the impact on the spreading factor is different for the E b /N 0 , the energy per bit to noise spectral density ratio (or SNR per bit), defined by

E b N 0 = SNR η , ( 2
)
where η is the normalized spectral efficiency, in bit/s/Hz. Indeed, if a spreading factor is used, η is divided by λ, with then η λ = η 1 /λ, where η 1 (resp. η λ ) is the spectral efficiency of the primary technique (resp. using the repetition λ). As a consequence, eq. ( 1) and ( 2) clearly demonstrate that the processing gain on the SNR with a spreading factor will be compensated in E b /N 0 by the reduction of the rate. If the spreading factor scheme allows a decrease of the required SNR, it does not permit a decrease in terms of E b /N 0 . The Shannon capacity [START_REF] Shannon | A mathematical theory of communication[END_REF], or Shannon's limit, is the maximal transmission rate with arbitrarily small bit-error probability, for a given SNR and a given bandwidth. It is straightforward that reaching this limit for a certain rate allows for a better energy efficiency of the system. The limit can be reformulated in terms of maximum spectral efficiency, or in terms of minimum E b /N 0 as

η ≤ log 2 (1 + SNR) ⇔ E b N 0 ≥ 2 η -1 η , (3)
and is depicted Figure 1 along with the performance of several common modulations: Phase-Shift-Keying (PSK), Mary orthogonal modulation, and Binary-PSK (BPSK) combined with a spreading factor (primary technique BPSK repeated by λ). Values are obtained by simulations of the considered modulations and denoting the required E b /N 0 for a Bit-Error-Rate (BER) of 10 -5 . The figure highlights the fact that the spreading factor only improves sensitivity, but does not enhance energy efficiency; for ultra-low rates, the gap with Shannon's limit reaches a constant value of 11.1dB. On the contrary, for M -ary orthogonal modulations, increasing the alphabet size induces an improvement (i.e a reduction) in E b /N 0 while the rate is decreased. However, very high values of M (thus very small spectral efficiency) are required to approach the Shannon's limit. The proposed Turbo-FSK scheme combines both orthogonal modulation and turbo processing in the perspective to get closer to Shannon's limit with a reasonable size of alphabet.

III. SYSTEM MODEL

First let us introduce some notations. Bold lowercase letters denote vectors, e.g. x, and bold uppercase letters matrices, e.g. X. Exponents indicate the row number, indices the column.

S (0)

S (1) S (K-1)

P/S
x Fig. 2. The Turbo-FSK transmitter with K stages.

The Fourier Transform (DFT) matrix of size 2 r ×2 r is denoted F r . j is the complex number, z the complex conjugate of z and Z is the Hermitian transpose of the matrix Z. Re(z) (resp. Im(z)) is the real part (resp. imaginary part) of complex number z.

A. Transmitter and Channel

We denote D the information bit matrix of size P × r, made from P row vectors b = {b n } n∈[0,...r-1] . The transmitter is shown in Figure 2. It is composed of K stages, each one having for input an interleaved version of D.

The convolutional-FSK encoder is presented in Figure 3. The parity of each row of D is computed, giving the P × 1 parity vector q . After passing through the accumulator (representing the row-wise cumulative sum modulus 2 of the elements of q ), the vector q of size P × 1 is obtained. The concatenation of D and q is a P × (r + 1) binary matrix. Each row is an information word, and there are 2 r+1 possible words.

To perform FSK signaling, we map each information word to a FSK symbol taken from the alphabet A (which contains 2 r+1 elements). FSK symbols will be denoted as FSK codewords, each of them being composed of a fixed number of chips (or complex values). A can be constructed using the Hermitian transpose DFT matrix (i. . . .

y (0)
y (1) y (K-1)

APP decoder APP decoder APP decoder . . .

Y (0) Y (1)
Y (K-1) L S/P Fig. 4. The Turbo-FSK receiver with K stages.

(2 r+1 orthogonal codewords composed of 2 r+1 chips), or the concatenation A = F r ; F r e jπ , a 2 r+1 × 2 r matrix (thus 2 r+1 bi-orthogonal codewords composed of 2 r chips). The use of bi-orthogonality allows to save one dimension, and will be referred to as the bi-orthogonal case.

The single memory of the accumulator takes part in the mapping of two consecutive FSK codewords. This share of information between codewords will allow the use of the Bahl, Cocke, Jelinek and Raviv (BCJR) algorithm [START_REF] Bahl | Optimal decoding of linear codes for minimizing symbol error rate (corresp.)[END_REF] at the decoder side, as introduced in [START_REF] Ping | Low-rate turbo-Hadamard codes[END_REF].

Each stage output consists of P FSK codewords, that can be multiplexed in quadrature by summing the first P/2 codewords with the last P/2 codewords multiplied by j (assuming P is a multiple of 2). We denote αP the number of output FSK codewords, with α = 1/2 if codewords are sent in quadrature, and α = 1 otherwise. The output of the k-th stage is denoted

S (k) , k ∈ [0, . . . K -1],
and is a αP × µ2 r+1 matrix, where µ = 1 for the orthogonal case, µ = 1/2 for the bi-orthogonal case. The output x of the Parallel-to-Serial (P/S) block is composed of αKP codewords, or αµKP 2 r+1 chips. It contains the succession of all FSK codewords from each stage. During one codeword period, only one FSK waveform (i.e one pure frequency) is sent if α = 1, and two FSK waveforms are added in quadrature if α = 1/2.

The spectral efficiency of the Turbo-FSK is

η = r αµK2 r+1 . (4)
We consider an AWGN channel, which output y is defined by

y = x + n, (5)
where n is a zero-mean circular complex noise with variance σ 2 . All vectors are composed of αµKP 2 r+1 chips.

B. Receiver

The turbo FSK receiver is depicted Figure 4. After passing through the AWGN channel, y is decomposed, by the Serialto-Parallel (S/P) block, into K vectors y (k) , containing the αP codewords of each stage. Each vector is then sent to a FSK detector, that performs the product of the received noisy codewords with A, i.e the DFT of the vector y (k) (that can be done using FFT algorithm). The outputs Y (k) of the detectors will be used as channel observations in the a posteriori probability (APP) computations, detailed in Section IV and symbolized by the APP decoder blocks. The turbo principle is to iteratively share information among all the decoders. After appropriate interleaving, one decoder will use the information from all the other decoders and the channel observations, to create an estimation of the information bits with more or less likelihood. The P × r matrix L contains the log ratio (LR) of the information bits, defined by

L(b) = log p(b = 1) p(b = 0) , (6)
where p(b = 0) (resp. p(b = 1)) is the probability of event b = 0 (resp. b = 1). The sign of L(b) is the hard bit decision while the magnitude gives the reliability. L is initialized to all-zero and propagated through all decoders. Each one of them uses L as a priori information and updates the matrix with its APP computation. At the end of each iteration, a hard decision can be made from L, as it represents all the information acquired.

IV. TURBO-FSK SOFT DECODING

The principle of soft decoding is to compute the APP knowing an a priori information and the channel observation. For one stage k and case α = 1, we consider one of the received noisy FSK codeword y p , p ∈ [0, . . . P -1] (such as y (k) = [y 0 , y 1 , . . . y P -1 ]). d = {d n } n∈[0,...r-1] is the decoded information word. c i is a codeword from the FSK alphabet A, and b i = {b i n } n∈[0,...r-1] its associated information word (i ∈ [0, . . . 2 r+1 -1]). The APP of a codeword is the probability of having the codeword knowing the observation, and p(c i |y p ) = p(y

p |c i ) p(c i ) p(y p ) , (7)
by applying Bayes' law. p(c i ) is the a priori probability of having the codeword c i , or that the decoded information word d is b i . Considering that c i and y p are composed of µ2 r+1 chips, the APP becomes :

p(c i |y p ) = 1 p(y p ) M -1 m=0 p(y p m |c i m ) r-1 n=0 p(d n = b i n ), (8)
with M = µ2 r+1 . The term p(y p m |c i m ) value is, in the complex AWGN case,

p(y p m |c i m ) = 1 2πσ 2 exp - 1 2σ 2 y p m -c i m 2 . ( 9
)
y p m and c i m being complex numbers, the first product in (8) becomes

M -1 m=0 p(y p m |c i m ) = B exp 1 σ 2 M -1 m=0 Re y p m .c i m , = B exp 1 σ 2 Re (Y p i ) , (10)
where Y p i is the i-th component of the DFT 1 of y p , and B a constant that will be canceled out in further computations. Using [START_REF] Proakis | Digital Communications 3rd Edition, ser. Communications and signal processing[END_REF] andp(d

n = 1) = 1 -p(d n = 0), p(d n = b i n ) = C exp L(d n )(1 -2b i n )/2 (11)
with C a constant that will be later canceled out. Finally, using [START_REF] Ping | Low-rate turbo-Hadamard codes[END_REF] and ( 11), ( 8) can be expressed as

p(c i |y p ) = D exp 1 σ 2 Re (Y p i ) + r-1 n=0 1 -2b i n 2 L(d n ) , (12)
with D a constant eliminated in further computations. One can notice this expression conveniently uses the result of the DFT of received codeword y p (the observation part, only computed once), and a particular combination of the soft bits L(d n ) (the a priori part, that will be updated at each iteration). By feeding the decoder with the soft bits matrix L and the result of the DFT, the APP of all codewords of the alphabet can be computed using [START_REF] Shimanuki | Improvements and extensions of low-rate Turbo-Hadamard codes[END_REF]. As previously mentioned, the use of the accumulator and then orthogonal modulation can be seen as sharing information between two consecutive symbols, and codewords probabilities can be updated using the BCJR algorithm. Updated probabilities are denoted P (c i |y p ).

Soft bits can be computed [START_REF] Hagenauer | Iterative decoding of binary block and convolutional codes[END_REF] with

L(d n |y p ) = log 2 r+1 i,b i n =1 P (c i |y p ) -log 2 r+1 i,b i n =0 P (c i |y p ), (13)
where the indexes of the sums mean probabilities are summed only if c i encodes an information word for which b i n = 1 (left sum) or 0 (right sum). The factor D in ( 12) is suppressed at this step.

Complexity of the hereby presented Maximum-A-Posteriori (MAP) decoding process can be reduced by using the well-known max-log approximation

log i e xi max i (x i ). ( 14
)
This simplification is done at the expense of some performance loss.

For each decoder, computations can be summarized in three steps:

-Computation of the APP of the P codewords (with (12) ∀ p ∈ [0, . . . P -1]), -Update the symbols APP using the BCJR algorithm, -Compute the APP of the information bits by summing the appropriate probabilities of codewords with (13).

V. SIMULATION RESULTS

To illustrate the performance of the Turbo-FSK scheme, simulations were performed for the AWGN channel, with coherent reception and random interleavers. Because the processing gain after 10 iterations is small, our simulations are restricted to this number of iterations.

Figure 5 shows the BER for the case r = 4, K = 4, P = 256. The transmitted FSK symbols are chosen in an alphabet of size 2 r+1 = 32. A block of P × r = 1024 information bits is considered. We consider here the orthogonal case where symbols are not sent in quadrature (α = µ = 1 in ( 4)). The spectral efficiency is η = 1/32 = 0.0312. The results for both MAP and max-log-MAP algorithms are given. The Block-Error-Rate (BLER) for max-log decoding is also depicted. The difference between exact computation and maxlog approximation is roughly equal to 0.5dB. This performance loss is acceptable considering the reduction of complexity of the decoders, and it should be mentioned that the gap could be reduced by applying a weighting function on the exchanged a priori informations. The spectral efficiency of an orthogonal modulation of same size of alphabet would be η 1 = (r + 1)/2 r+1 ; by using the spreading factor scheme to repeat 5 times this orthogonal modulation, the spectral efficiency (now equals to η 1 /5) is equivalent to the one of the Turbo-FSK with our parameters. The performance gain over repeated 32-FSK is 6dB at BER = 10 -5 . Considering now λ the spreading factor as introduced in Section II, a spectral efficiency of 1/32 is equivalent to a BPSK (η 1 = 1) with a spreading factor of λ = 32. At BER = 10 -5 , Turbo-FSK shows a 8.9dB gain over repeated BPSK. Shannon's limit for the considered spectral efficiency is also represented, showing that with these parameters, Turbo-FSK is only 2.3dB away from the capacity limit. At a E b /N 0 of 1.6dB, the error floor is reached: BER decreases slower than in the previous waterfall region. The error floor can be shown to be directly related to the values of K and the block size. A BLER of 10 -3 is achieved for an E b /N 0 of 1.05dB. Figure 6 depicts the BER for another case of the Turbo-FSK, versus the SNR. The considered case is r = 3, K = 3. Multiple values of P are represented, leading to several sizes of block of information bits, from 1023 to 16383 (denoted N = P × r). The bi-orthogonal case is considered (µ = 1/2, α = 1). Spectral efficiency is η = 0.125 = 1/8, and is equivalent to an 8-FSK modulation with spreading factor λ = 3, or BPSK modulation with λ = 8. For a BER of 10 -5 , Turbo-FSK with N = 1023 shows 6.6dB of gain versus repeated 8-FSK and 7.8dB gain over repeated BPSK. This BER is reached for a E b /N 0 of 1.8dB (case N = 1023), and can be compared to the BICM-ID scheme with a similar spectral efficiency presented in [START_REF] Panaro | Simple iterative decoding for bit-interleaved coded orthogonal modulation[END_REF] (using N = 65536). Our scheme shows an improvement of 1dB over BICM-ID, while using a much smaller block size. This BER is achieved at SNR of -7.24dB, showing the system is able to work at low levels of SNR. The figure clearly shows the influence of the number of interleaved bits N : increasing this value significantly improves the error floor region. However small block sizes are more suitable to the LPWA context.

Figure 1 has been completed with the results achieved by Turbo-FSK in Figure 7. It shows the evolution of the spectral efficiency depending on the parameters r and K, versus E b /N 0 , for a BER of 10 -5 . Increasing K from 2 to 3 induces a significant improvement in E b /N 0 , and the gap to the capacity limit is reduced, while spectral efficiency decreases. For K > 4, improvement in E b /N 0 is small, and these cases have not been represented. The value of r has a similar effect: increasing the alphabet allows better performance, while the spectral efficiency is decreased. Setting r to higher values would get the system closer to Shannon's limit, however this may not be sensible in the LPWA context. Moreover, using larger values of N would improve the performance for every case. BICM-ID from [START_REF] Panaro | Simple iterative decoding for bit-interleaved coded orthogonal modulation[END_REF] is shown on the graph. Results are obtained using a 64-state convolutional code, involving a high decoding complexity due to the Soft-Output Viterbi Algorithm combined with the turbo processing of BICM-ID. Again, the block size considered is 2 16 and is then large compared to the size used in our simulations. For a reduced complexity and smaller block size, our scheme offers better performance.

VI. CONCLUSION

In the context of M2M communications, terminals are expected to be low power, low cost and to work at very low levels of sensitivity. Used as uplink communication in LPWA network, the newly proposed Turbo-FSK scheme is adapted to these requirements. Simulation results show a significant performance gain that increases with the alphabet size, the number of stages and the information block size. The interleaving strategy of turbo coding is as costly as the repetition scheme, but performance is significantly enhanced thanks to a more complex receiver. The choice of FSK allows the use of basic components to emit the signal (such as a voltage controlled oscillator), and the constant envelope property enable to release some constraints on the power amplifier, because of the low peak-to-average-power ratio of the modulated signal. One way to interpret the observed gains in E b /N 0 is the reduction of transmitted power at the connected object, while achieving the same level of performance. The system works at low levels of SNR (hence low levels of sensitivity) even when relatively small information block sizes are considered, while the flexibility of available configurations (values of r, K and P ) makes it versatile for various use cases.

EFig. 1 .

 1 Fig. 1. Spectral efficiency versus E b /N 0 , for different modulations and for BER = 10 -5 .

Fig. 3 .

 3 Fig. 3. The convolutional-FSK encoder

Fig. 5 .

 5 Fig.5. Turbo-FSK BER performances in E b 0 for the case r = 4, P = 256, K = 4, α = µ = 1, η = 0.0312, after 10 iterations. Shannon's limit is equal to -1.545dB for this spectral efficiency.

Fig. 6 . 4 EFig. 7 .

 647 Fig. 6. Turbo-FSK BER performances in SNR for the case r = 3, K = 3, α = 1, µ = 1/2, η = 0.125, after 10 iterations, for different values of N = P × r. The MAP algorithm was used.

For the case α = 1/2 (i.e y (k) = [y 0 + jy 1 , . . . , y P -2 + jy P -1 ]), the real part in[START_REF] Ping | Low-rate turbo-Hadamard codes[END_REF] would be replaced by the imaginary part for odd values of p.