David Romero
email: david.romero.diaz@gmail.com

Ovidiu Noran
email: o.noran@griffith.edu.au

Johan Stahre
email: johan.stahre@chalmers.se

Peter Bernus
email: p.bernus@griffith.edu.au

Åsa Fast-Berglund

Towards a Human-Centred Reference Architecture for Next Generation Balanced Automation Systems: Human-Automation Symbiosis

Keywords: Balanced Automation Systems, Human-Centred Manufacturing, Reference Architecture, Level of Automation, Social Sustainability

Human-centricity in manufacturing is becoming an essential enabler to achieve social sustainable manufacturing. In particular, human-centric automation can offer new means to increase competitiveness in the face of new social challenges for the factories of the future. This paper proposes a Human-Centred Reference Architecture that can structure and guide efforts to engineer Next Generation Balanced Automation Systems featuring adaptive automation that take into account various criteria in the operating environment such as time-lapse, performance degradation, age-, disability-and inexperience-related limitations of operators to increase their working capabilities.

Introduction

According to the European Factories of the Future Research Association (EFFRA) Roadmap 2020, human-centricity will be a prerequisite for the factories of the future seeking to increase flexibility, agility and competitiveness in the face of new social challenges (e.g. demographics). Thus, future manufacturing enterprises will need to be proficient in assisting ageing, disabled and apprentice operators by using evolved information and communication technology capabilities in order to enhance their understanding and thus enable better execution of advanced manufacturing operations [1]. Importantly, this endeavour is likely to require the dynamic (re-)configuration of automation levels driven by the operator execution limitations (gaps) in advanced production management systems in order to enhance competitiveness and compensate for age-, disability-, and inexperience-related limitations of operators to increase their working capabilities.

In this paper, the authors contrast the Tayloristic paradigm of Balanced Automation Systems characterised by a selected mix of independent automated activities and human activities, having humans at subservient roles to machines and automation -(e.g. supervisors [START_REF] Rosenbrock | Machines with a Purpose[END_REF]), towards a human-automation symbiosis [START_REF] Tzafestas | Concerning Human-Automation Symbiosis in the Society and the Nature[END_REF], or Next Generation Balanced Automation Systemcharacterised by the cooperation of machines and automation with humans, and designed not to replace the skills and abilities of humans, but rather to assist humans in being more efficient [START_REF] Tzafestas | Concerning Human-Automation Symbiosis in the Society and the Nature[END_REF].

The authors explore the bodies of knowledge of intelligent (smart) automation systems [START_REF] Ohno | Toyota Production System[END_REF] and the Enterprise Architecture discipline [START_REF] Williams | PERA and GERAM: Establishment of the Place of the Human in Enterprise Integration[END_REF] [START_REF]Industrial Automation Systems: Concepts & Rules for Enterprise Models[END_REF] to propose a Human-Centred Reference Architecture for engineering the Next Generation Balanced Automation Systems, featuring adaptive automation [START_REF] Hancock | Adaptive Control in Human-Machine Systems[END_REF].

Current Efforts to Evolve Balanced Automation Systems

The basic principle leading to the envisioned Next Generation Balanced Automation System is human-centricity, meaning that "humans should never be subservient to machines and automation, but machines and automation should be subservient to humans" [START_REF] Rosenbrock | Machines with a Purpose[END_REF].

According to Tzafestas [START_REF] Tzafestas | Concerning Human-Automation Symbiosis in the Society and the Nature[END_REF], the human-automation symbiosis necessary to achieve sustainable development in human society can only be secured by the use of intelligent (smart) automation systems and interfaces, where the assumed 'intelligence' allows inclusion of the explicit representation of human goals and plans and thus constitutes the basis of human-machine interaction. Hence, human-centred design should go beyond the traditional human factors that merely focus on helping operators manage their workload in a healthy and safe manner, to a higher humanistic level such as job inclusion and satisfaction.

Furthermore, according to Hancock et al. [START_REF] Hancock | Human-Automation Interaction Research: Past, Present and Future[END_REF] the idea of having machines and automation adapt to the cognitive and physical demands of humans in a momentary and dynamic manner (adaptive automation)is one of the most important ideas in the history of human-automation interaction research towards social sustainability 1 [8] [9]. In this sense, adaptive automation aims to optimise cooperation and to efficiently allocate labour (cognitive and physical) and distribute tasks between the automated part and the humans in the system [START_REF] Kay | Adaptive Automation Accelerates Process Development[END_REF]; importantly, this paradigm also allows the user and/or the machines to modify the level of automation by shifting the control of specific functions whenever predefined conditions are met [START_REF] Calefato | The Adaptive Automation Design[END_REF].

Adaptive automation will help improve a manufacturing system performance in a sustainable way by providing different types of automation solutions ranging from pure manual to fully automatic 2 [START_REF] Fasth-Berglund | Cognitive Automation Strategy -For Reconfigurable and Sustainable Assembly Systems[END_REF] according to human-centred automation criteria 3 [START_REF] Sheridan | Human-Automation Interaction[END_REF], thus making it possible to rely on humans and automation to jointly achieve 1 Social Sustainability -"the freedom to choose at any stage in life between different forms of work (work arrangements, field of work) or lifestyles, while being at all times entitled to individual social security" [START_REF] Hancock | Human-Automation Interaction Research: Past, Present and Future[END_REF]. 2 Levels of Automation -"the allocation of physical and cognitive tasks between resources (humans and technology), described as discrete steps from 1 (totally manual) to 7 (totally automatic), forming a 7 by 7 levels of automation matrix containing 49 possible types of automation solutions" [START_REF] Fasth-Berglund | Cognitive Automation Strategy -For Reconfigurable and Sustainable Assembly Systems[END_REF]. 3 Criteria -1. Allocate to the human the tasks best suited to the human, and allocate to the automation the tasks best suited to it 2. Keep the human operator in the decision-and-control loop. 3. Maintain the human operator as the final authority over the automation. 4. Make the human operator's job easier, more enjoyable, or more satisfying through friendly automation. 5. Empower or enhance the human operator to the greatest extent possible through automation. 6. Support trust by the human operator. 7. Give the operator computer-based advice about everything he or she should want to know. 8. Engineer the automation to reduce human error and minimize response variability. 9. Make the operator a supervisor of subordinate automatic control systems. 10. Achieve the best combination of human and automatic control, where best is defined by explicit system objectives [START_REF] Sheridan | Human-Automation Interaction[END_REF]. production objectives. Essentially, assistance is to be provided in an adaptive and dynamic manner and only when required (i.e. to help an operator in difficulty to perform his/her tasks according to the expected quality of performance). Nevertheless, the functional state of the operator is to be continuously monitored in order to provide the assistance (aiding) only when necessary and in an unobtrusive manner, i.e. without interfering with the operator's cognitive and physical resources [START_REF] Hancock | Human-Automation Interaction Research: Past, Present and Future[END_REF]. Thus, one can use advanced trained classifiers [START_REF] Willson | Performance Enhancement in a UAV Task Using Psychophysiologically determined Adaptive Aiding[END_REF] relying on psycho-physiological measures (neuroergonomics) in order to determine when an operator actually requires assistance and subsequently to prompt the advanced manufacturing system to provide an appropriate type and level of automation facilitating optimal operator performance.

Hence, the main envisaged goals of adaptive automation are to prevent errors and to reduce out-of-the-loop performance by preserving an adequate level of situation awareness [START_REF] Endsley | Toward a Theory of Situation Awareness in Dynamic Systems[END_REF] and mental workload, while providing a crucial perception of empowerment materialised into an appropriate level of freedom for the operator [START_REF] Kaber | On the Design of Adaptive Automation for Complex Systems[END_REF].

Towards a Human-Centred Automation Reference Architecture

Tzafestas [START_REF] Tzafestas | Concerning Human-Automation Symbiosis in the Society and the Nature[END_REF] argues that the design and engineering of cooperation between human and machine or automation system must start from the very beginning and permeate all lifecycle phases of the system. Consequently, human-automation symbiosis engineering projects that design such systems must also implement processes that observe the human-centricity principle, in the context of their own lifecycle.

It is hereby argued by the authors that an optimal way to integrate the lifecycle and human aspects in a human-centred automation reference architecture is by involving the Enterprise Architecture (EA) body of knowledge. For the purpose of this work, authors adopt the mainstream definition of EA, seen as a holistic change management paradigm that bridges management and engineering best practices, providing the "[…] key requirements, principles and models that describe the enterprise's future state […] EA comprises people, processes, information and technology of the enterprise and their relationships to one another and to the external environment" [START_REF]IT Glossary[END_REF]. Thus, EA considers the socio-technical aspect of systems [START_REF] Pava | Managing New Office Technology. An Organisational Strategy[END_REF], seen as composed of commitments assumed by voluntaristic people [START_REF] Mcgregor | The Human Side of Enterprise[END_REF] in a complex organisational, political and behavioural context [START_REF] Iivari | A Paradigmatic Analysis of Contemporary Schools of IS Development[END_REF] [START_REF] Markus | Power, Politics, and MIS Implementation[END_REF]. Therefore, the authors argue that EAbased artefacts such as reference frameworks are capable to provide comprehensive 'shopping lists' of potentially applicable aspects and at the same time integrate all necessary viewpoints (as determined by the stakeholders for the project at hand) in a lifecycle-based set of models ensuring the consistency and sustainability of complex projects (with human-automation symbiosis engineering as a prime example).

In line with this stance, the authors propose the adoption of the Purdue Enterprise Reference Architecture (PERA) [START_REF] Williams | PERA and GERAM: Establishment of the Place of the Human in Enterprise Integration[END_REF] and ISO14258 [START_REF]Industrial Automation Systems: Concepts & Rules for Enterprise Models[END_REF] (which places the PERA concepts within a conceptual framework enabling coverage and completeness assessment) as a starting point in building a human-centred automation reference architecture. PERA incorporates an explicit representation of the human role in any type of system and importantly, it also shows the extent of automation, defined as "the absolute extent of pure technologies in their capability to actually automate the tasks and functions of the […] system" [START_REF] Williams | PERA and GERAM: Establishment of the Place of the Human in Enterprise Integration[END_REF] [START_REF] Li | A formalization and extension of the Purdue Enterprise Reference Architecture and the Purdue Methodology[END_REF]. PERA also shows the relationship between the level of automation (of both the control and information systems and the production/service systems), and its effect on the human and organisational element of the enterprise [START_REF] Williams | PERA and GERAM: Establishment of the Place of the Human in Enterprise Integration[END_REF].

In the following, the PERA lifecycle architecture (see Fig. 1) will be used in order to reflect a 'master plan' [START_REF] Williams | PERA and GERAM: Establishment of the Place of the Human in Enterprise Integration[END_REF] [START_REF] Li | A formalization and extension of the Purdue Enterprise Reference Architecture and the Purdue Methodology[END_REF] outlining the specifications of a human-automation symbiosis engineering project. The sample business entity selected for this purpose is a typical factory production line.

Identification Phase

At this phase, the architect (meaning a stakeholders group, including the operators) conducts the typical feasibility (e.g. economic and socio-technical) and SWOT studies at the production line in question in order to identify potential gains and benefits balanced against costs and risks presented by including the proposed workstation(s) in the human-centric automation engineering program.

Concept Definition Phase

 The Mission is to design and engineer a human-centred production system [START_REF] Charles | Prospects and Conditions for Anthropocentric Production Systems in Britain[END_REF] based on a human-automation symbiosis paradigm that allows operators to feel empowered and in control of their workstation, while also fostering the optimal use of human competencies (knowledge, skills, abilities and behaviours).

The system is also to compensate for operators' limitations, thus ensuring a socially sustainable working environment without compromising production objectives.  The Vision is to provide adaptive balanced automation systems that comply with mainstream models of human-centred production systems [START_REF] Charles | Prospects and Conditions for Anthropocentric Production Systems in Britain[END_REF] and factories [START_REF] May | A New Humancentric Factory Model[END_REF].  Values: Ergonomics, Human Factor, Occupational Health, Safety, Inclusiveness.  Strategy: To develop a master plan featuring adaptive automation in order to achieve human-automation symbiosis in the workstations of a production system. [START_REF] Bailey | Human Performance Engineering[END_REF] function allocation catalogue provides three human-centred strategies: humanized allocation (priority to the operator over the machine), flexible allocation (according to values, needs and interests) and allocation by users (operator chooses according to conditions), in order to support decision-making from the point of view of the ability of humans to perform.

According to Inagaki [START_REF] Inagaki | Adaptive Automation: Sharing and Trading of Control[END_REF], in adaptive automation, functions (tasks) can be shared or traded between humans and machines in response to changes in situations or human performance. There are three classes of automation invocation strategies: critical-event, measurement-based and modelling-based.

Architectural Design Phase

The operations involved in a project or production line can be classified according to their purpose into mission fulfilment tasks and information management and control tasks; humans (including system operators) are inherently involved in all these operations for technological, economic and social reasons.

Mission Fulfilment Task Information & Control Tasks Manufacturing Architecture

Management & Control Architecture Mechanised Tasks Human Implemented Tasks Automated Tasks Specification of equipment needed for adaptive control tasks of operators

Tasks of operators working with the adaptive automation system

Tasks of operators to be controlled by the adaptive automation system Specification design of the adaptive automation system  Adaptive Automation  According to Inagaki's [START_REF] Inagaki | Adaptive Automation: Sharing and Trading of Control[END_REF] adaptive automation strategies, within the critical-event strategy, functions' allocations change when specific events (called critical-events) occur, e.g. in the human-automation symbiosis. Allocation of functions would not be altered if the critical events did not occur during the human-machine system operation; in this sense, function allocation within a critical-event strategy is adaptive. In measurement-based strategies, functions' allocations are dynamic between operators and machines so that the momentary operator workload (based on psychophysiological measures) can be regulated around an optimal level. In modelling-based strategies, functions' allocations are based on operator performance models (intent inferencing models, optimal (mathematical) models or resource models) that can be used to estimate current and predicted operator state and to infer whether workload is excessive or not.

The ultimate aim of human-automation symbiosis is the achievement of adaptive automation across all workstations of a human-centred production system in order to allow a dynamic and seamless transition of functions (tasks) allocation between humans and machines that optimally leverages human skills to provide inclusiveness and job satisfaction while also achieving production objectives.

Human-Automation Symbiosis Scenarios

In contrast with the traditional view of automation, adaptive automation is designed to anticipate changes under active control of an operator while maintaining precise control of all background variables not currently of interest [START_REF] Kay | Adaptive Automation Accelerates Process Development[END_REF]; thus, dynamic allocation of task control [START_REF] Fasth-Berglund | Task Allocation in Production Systems -Measuring and Analysing Levels of Automation[END_REF] [26] [START_REF] Inagaki | Adaptive Automation: Sharing and Trading of Control[END_REF] (in whole or in parts) crossing over various types and levels of automation should be considered to exist in a continuum between the manual and fully automated operational boundaries [START_REF] Calefato | The Adaptive Automation Design[END_REF]. There is growing evidence pointing that beyond thinking of adaptive systems as co-workers, humans are increasingly expecting them to display human behaviour. Consequently, adaptive automation ventures into potentially uncharted territories, featuring new challenges for both users and designers that go beyond the traditional ideas of human-computer interaction and system design [START_REF] Scerbo | Adaptive Automation[END_REF].

In the following sub-sections, the authors introduce three scenarios illustrating the way adaptive automation can help achieve human-automation symbiosis in the context of human-centred production systems [START_REF] Charles | Prospects and Conditions for Anthropocentric Production Systems in Britain[END_REF] and factory models [START_REF] May | A New Humancentric Factory Model[END_REF]. Naturally, the scenarios presented make use of the adaptive automation aspects structured in Section 3 using PERA, such as shared and traded control principles, flexible task allocation strategies, including levels of automation and function allocation decision and hybrid automation invocation strategies.

In relation to the latter aspect, critical-event function allocation should apply to all scenarios, while measurement-based and modelling-based strategies application may vary in their applicability. This is because the critical-event strategy is aimed to take care of the operator health and safety, as well as of the production objectives. Thus, a critical-event emergency logic involves automation invocation without human involvement e.g. if the operator violates occupation health and safety regulations. A critical-event executive logic invokes the sub-processes leading up to the decision to activate automation, with only the final decision requiring the human's approval, e.g. in case of a drop in performance. Finally, a critical-event automated display logic allows all non-critical display findings to be automated in preparation for a particular event (e.g. troubleshooting), so that the human can concentrate on the most important tasks to fix the critical event problem(s).

Senior Operators (Aging Challenge)

In this case, adaptive automation can help a senior operator in a twofold manner: either by increasing automation to compensate for ageing-related limitations and thus help keep with the physical and cognitive quality performance of the job by, or by reducing the level of automation, on request, in order to provide the senior operator with a 'craftsman' experience and increase the level of job satisfaction. Furthermore, the operator may influence the functions allocation within the measurement-based strategy (e.g. by sharing and trading control) outside the 'optimal' level if this action does not compromise personal health and safety and the production objectives. Flexibility in functions allocation is allowed, but at the same time workload will be monitored in real-time in case of physical or mental over-stress (critical-event), so automation can take over. The modelling-based function allocation strategy (utilising models to estimate current and predicted operator state) has a very limited role in this scenario (if at all present) as the focus should be on recreating the craftsman experience or compensating for ageing-related limitations. In addition, by collecting senior operators' knowledge and experience in a particular task, the system could improve the learning curve of new operators by providing adaptive automated expert help [START_REF] Fast-Berglund | Developing Flexible ICT-tools for Education and Assembly support[END_REF], as also shown in sub-section 4.3.

Operator with a Disability (Inclusiveness Challenge)

Adaptive physical and cognitive automation can assist an operator with a disability to be able to perform 'normal' tasks (i.e. suitable for workers with no-disabilities). Modelling-based function allocations should be prevalent, based on models obtained from regular disability degree assessments, in order to allow the proper aiding and freedom of automation levels. Measurement-based function allocation could be used to fine-tune the level of automation based on the disabled operator condition.

Apprentice Operator (Learning Curve Challenge)

In this case, apprentice operators can learn new routines with (mainly cognitive) automation assistance. Measurement-based function allocation would play a major role here; as the operator learns and performs operations faster and with fewer errors, the system can gradually surrender automated tasks to the human side. Modelling-based strategies could also be used to achieve stability for specific periods of time (e.g. supporting regular performance reviews).

Summary of the Scenarios

It must be noted that scenarios such as those shown above vary in content depending on the specific application and may also have overlapping areas, depending on the particular lifecycle phase that the context system finds itself currently in. For example, the necessity to learn new tasks, typical to scenario 4.3 during Operation phase, can also manifest itself in scenarios 4.1 and 4.2, e.g. during Obsolesce and Decommissioning phases when humans may need to be trained in order to be re-assigned, or during Manifestation (Implementation) phase when design changes bringing new functionality for the system require new operator competencies.

Conclusions and Further Work

The paper has presented the use of modelling artefacts provided by an Enterprise Reference Architecture in order to guide and structure the efforts to define a Human-Centred Reference Architecture for Next Generation Balanced Automation Systems. After populating the areas deemed to be the most relevant to human-automation symbiosis, the paper has briefly illustrated the practical use of these aspects in several typical scenarios.

More research is required in order to delve deeper into the structured aspects provided by PERA, possibly by using other reference architectures that further subdivide these aspects and/or represent them orthogonally in relation to other aspects (e.g. Function, Information, Organisation, Resources, Risk, Economical, Hardware, Software etc.see ISO15704 Annex A: GERAM [START_REF]Industrial Automation Systems -Requirements for Enterprise-Reference Architectures and Methodologies[END_REF]). This would provide more detailed guidance as to the available viewpoints and areas that may need to be addressed in specific adaptive automation projects, so as to advance the work towards the creation of a truly human-centred factory model.

This research work has been driven by EFFRA (industrial association) Roadmap 2020 that calls for human-centricity in the factories of the future.

Figure 1 .

 1 Figure 1. The Purdue Enterprise Reference Architecture (PERA) [Complete set of lifecycle phases shown on right, current research scope on left]


Alexandre Soro

Jérôme Lacan
email: jerome.lacan@isae.fr

Vincent Roca

Valentin Savin
email: valentin.savin@cea.fr

Mathieu Cunche
email: mathieu.cunche@inria.fr

Enhanced Recursive Reed-Muller Erasure Decoding

Recent work have shown that Reed-M üller (RM) codes achieve the erasure channel capacity. However, this performance is obtained with maximum-likelihood decoding which can be costly for practical applications. In this paper, we propose an encoding/decoding scheme for Reed-M üller codes on the packet erasure channel based on Plotkin construction. We present several improvements over the generic decoding. They allow, for a light cost, to compete with maximum-likelihood decoding performance, especially on high-rate codes, while significantly outperforming it in terms of speed.

I. INTRODUCTION

Introduced in 1951 by Mitani [START_REF] Mitani | On the Transmission of Numbers in a Sequential Computer[END_REF] and popularized by Reed [START_REF] Reed | Decoding of Reed-Muller Codes with a Large Number of Errors[END_REF] and Müller [START_REF] Muller | Application of Boolean algebra to switching circuit design and to error detection[END_REF], Reed-Müller codes are still used in many applications (e.g. [START_REF] Etsi | Digital Video Broadcasting (DVB) ; Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive[END_REF]). Their structural properties allow the use of very simple but efficient coding and decoding algorithms. Traditionally, Reed-Müller codes were mainly considered for the Gaussian channel because they are able to reach their Maximum-Likelihood (ML) decoding performance with fast soft decision decoding algorithms [START_REF] Dumer | Soft-decision decoding of Reed-Muller codes: recursive lists[END_REF], [START_REF]Recursive and permutation decoding for Reed-Muller codes[END_REF], [START_REF] Oster | Benchmark of Reed-Mller Codes for Short Packet Transmission[END_REF]. But recently, very interesting results have shown that Reed-Müller codes achieve the capacity of the erasure channel [START_REF] Kumar | Reed-Muller Codes Achieve Capacity on Erasure Channels[END_REF], [START_REF] Abbe | Reed-Muller Codes for Random Erasures and Errors[END_REF]. These results were followed by new contributions on decoding algorithms of these codes [START_REF] Abbe | Reed-Muller Codes for Random Erasures and Errors[END_REF], [START_REF] Saptharishi | Decoding high rate Reed-Muller codes from random errors in near linear time[END_REF].

Capacity-achieving erasure codes have interesting practical applications. For example, they are used on higher layers of communication protocols stacks for multicast or real-time transmissions [START_REF] Hänle | Feasibility study of erasure correction for multicast file distribution using the network simulator ns-2[END_REF]. In this context, the data are transmitted into packets and the erasure code is used to generate repair packets from information packets. On the channel, called packet erasure channel, each packet is correctly received or erased. Classically, packet erasure codes are Fountain codes [START_REF] Luby | Raptor Forward Error Correction Scheme for Object Delivery[END_REF], LDPC codes [START_REF] Roca | Low Density Parity Check (LDPC) Staircase and Triangle Forward Error Correction (FEC) Schemes[END_REF] or MDS (Reed-Solomon-based) codes [START_REF] Lacan | Reed-Solomon Forward Error Correction (FEC) Schemes[END_REF].

The main issue concerning the use of Reed-Müller codes on the packet erasure channel is that the traditional decoding algorithm achieving the capacity is based on an inversion (through a Gaussian elimination) of the submatrix of generator matrix corresponding to the received symbols and a matrixvector multiplication. The gaussian elimination, which has a cubic complexity, is done only once for a codeword of packets but the matrix-vector multiplication is done z times, where z is the size of the packets. This operation can be very costly when the code length increases.

The main contribution of this paper is to propose a subquadratic decoding algorithms of Reed-Müller codes for the packet erasure channel which obtain performances very close to the capacity. For that, we extend some results presented in [START_REF] Soro | Mécanismes de fiabilisation pro-actifs[END_REF]. The decoding algorithm make use of various structural properties of Reed-Müller codes like the Plotkin recursive decomposition [START_REF] Plotkin | Binary codes with specified minimum distance[END_REF] and the doubly transitive permutation group. A similar technique was shown to obtain excellent decoding performance on the Gaussian channel [START_REF] Dumer | Soft-decision decoding of Reed-Muller codes: recursive lists[END_REF]. Decoding based on recursive strategies was also successfully applied to Polar codes, which have a structure similar to the one of Reed-Müller codes [START_REF] Korada | Polar codes for channel and source coding[END_REF].

Our main contribution is to show that, when used in a different way and combined with additional tools (partial information passing and blank decoding), this techniques yields decoding performance close to maximum likelihood on the packet erasure channel with a very low complexity cost.

In the next Section, we present the Plotkin construction of Reed-Muller codes and then our algorithm. In Section III, we compare the recovering performance and the speed of our decoding algorithm to the ML decoding with Gaussian Elimination (GE). Finally, we draw some conclusions and perspectives for this algorithm.

II. PROPOSED DECODING ALGORITHM

A. Introduction to Reed-Muller codes

Reed-Muller codes defined by parameters r and m, where r ≤ m, are denoted by RM (r, m). The dimension k, and the length n of RM (r, m) are given by k = r i=0 m i and n = 2 m .

One way to construct Reed-Muller codes is to use the recursive decomposition introduced by Plotkin. For any m, RM (0, m) is defined as the repetition code and RM (m, m) is the identity code. In the general case, for 0 < r < m, any codeword a ∈ RM (r, m) can be uniquily built from two codewords u ∈ RM (r, m -1) and v ∈ RM (r -1, m -1). Precisely, we have:

RM (r, m) = {(u|u + v), u ∈ RM (r, m -1), v ∈ RM (r -1, m -1)}
By using the above decomposition in a recursive manner, it follow that any RM code can be built from repetition and identity codes. This also implies that any RM (m-1, m) code is a Single Parity Check (SPC) code.

Over the erasure channel, a codeword a is received with some erased positions. One can try to decode u and v with a = (u|u + v) recursively.

For example, if a ∈ RM (1, 3), we have u ∈ RM (1, 2), which is an SPC code, and v ∈ RM (0, 2), which is a repetition code. Therefore, u can be decoded if it has at most one lost position, and v can be decoded if at least one of its position is known. Moreover, decoding new positions on either u or v can reveal some new positions on the other vector, as we have a n 2 +i = u i + v i , for any 0 ≤ i < n 2 . This decoding decomposition will be referred to as the classical recursive algorithm. By nature, this algorithm has a O(n log n) complexity.

B. Permutation Decoding

One interesting property of RM (r, m) codes is that they admit the general affine group GA(m) as a permutation group [START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF]. In other words, if a = (a 0 , a 1 , ..., a n-1 ) ∈ RM (r, m), then a = (a Π(0) , a Π(1) , ..., a Π(n-1) ) ∈ RM (r, m), where Π(x) = Ax + b, A is a m × m binary invertible matrix and b a vector of (F 2 ) m . This group is known to be doubly-transitive, i.e. there exists a permutation that sends any pair of positions onto any other pair of positions.

It can be observed that the success of the recursive decoding depends on the erasure pattern. Applying some specific permutation on a received word can make successful a decoding that has initially failed. The effects of permutations on the iterative erasure decoding was studied in [START_REF] Hehn | Permutation Decoding and the Stopping Redundancy Hierarchy of Cyclic and Extended Cyclic Codes[END_REF] for cyclic and extended cyclic codes, but not for general Reed-Müller codes.

Example : Let us consider that a received pattern of a ∈ RM (1, 3) is (a 0 , ×, ×, ×, ×, a 5 , a 6 , a 7 ). Only one in u = (a 0 , ×, ×, ×) is known thus it can not be decoded. Moreover, no positions of v, obtained by summing u and (u + v), are known. Decoding is then impossible. Using the permutation matrix

A =   1 0 0 1 1 0 0 0 1   and b =   0 0 0   ,
the vector to be decoded is then a = (a 0 , ×, ×, ×, a 6 , a 7 , ×, a 5 ) and thus u = (a 0 , ×, ×, ×) and u + v = (a 6 , a 7 , ×, a 5 ). By summing u and u + v , we obtain v = (a 0 + a 6 , ×, ×, ×). Since v is a codeword of the RM (0, 2) which is the repetition code of length 4, v decoded = (a 0 + a 6 , a 0 + a 6 , a 0 + a 6 , a 0 + a 6 ). By summing v decoded and the received u +v , we obtain an updated version of u , u updated = (a 0 , a 7 + a 0 + a 6 , ×, a 5 + a 0 + a 6 ). Since u belongs to the RM (1, 2) which is a SPC code, we can decode it as u decoded = (a 0 , a 7 + a 0 + a 6 , a 0 + a 5 + a 7 , a 5 + a 0 + a 6 ). We can then rebuild the decoded version of u + v and finally apply the inverse permutation on a to obtain the decoded word a.

The key challenge in the previous example is to find a specific permutation, suited for the given erasure pattern. Simulation results have shown that decoding is more efficient by starting the decoding process with the decoding of v. As a consequence, the main point is to determine a permutation which maximizes the number of received positions in v for a small complexity cost.

First we can notice that the vector b is useless. Indeed, for a received word a = (u|u + v), the known positions of v are the positions where a i and a i+ n 2 are known. We can observe that the number of known positions of v will not change when the vector b is added to all positions. Without loss of generality, in the following, we restrict ourselves to the set of invertible matrices A, i.e. the general linear group GL(m, 2). For all binary invertible matrices of size m, we have to process the images of the n positions. Following [START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF] which gives the number of invertible matrices of size n, the complexity of testing all possible matrices corresponding to a permutation of size n is roughly O(n × 0.29 × 2 log 2 n ).

In order to avoid such a prohibitive cost, we propose a lower complexity algorithm. Instead of testing the whole set of invertible matrices, we only select the matrices that leave the n 2 leftmost positions, i.e. the vector u, invariant. It means that their first m-1 columns correspond to the first m-1 columns of the identity matrix. Hence, the number of permutations to be tested is equal to n 2 , since corresponding matrices are completely determined by their last column, which must be chosen outside the vector subspace spanned by the first m -1 columns. For each of these permutations, as the leftmost positions are invariant, only the images of the n 2 rightmost positions are processed. The complexity of testing this set of matrices for one permutation of size n is thus O( n 2 4 ). The impact of this permutation selection on the global complexity of the decoding process is discussed in Section II-D.

C. Partial Decoding

Orthogonally to the previous point, we propose a second improvement to the algorithm. One of the weaknesses of the raw recursive decoding algorithm is that, if one recursion fails, the whole decoding fails. This is harmful for the performance as for instance a recursion in v can fail but some new symbols from other recursions may have been recovered. We propose to pass this partial recovered information to the higher levels of the recursion.

For example, let a be decomposed by u and v, which itself is decomposed by v 1 and v 2 . Let the decoding of v 2 succeed and v 1 fail. v 2 may bring some new symbols to v, which can themselves bring new symbols to a and then improve the decoding of u. Finally, if u reveals new symbols, they can be useful for v and v 1 and so forth. Simulation results have shown that most of the time (over 95%), the number of recursive calls is two, especially for higher levels of recursion, which also means that the use of this mechanism is limited.

D. Blank Decoding

Unlike the previous improvements enhancing the decoding capability, "blank decoding" is focused on speed.

To explain this mechanism, let us consider a packet erasure code generating n -k repair packets from k information packets. By assuming that all packets have size z bits, the encoding of the packet code can be seen as the parallel encoding of z binary codewords of size n. Each one of the n transmitted packets contains exactly one bit of each of the z encoded vectors. The interest of this scheme is that the erased packets produce the same erasure pattern on all the binary codewords. In the decoding process of the packet code, this property is used to pool together operations that are common to the z decodings of the binary codewords.

Actually, before each packet block decoding, a blank block (i. e. a block with packets of null size) decoding is processed with the received loss pattern. During this process, the decoder searches the best permutation to apply and the best partial information passing strategy, according to the algorithms described above and records it. If this decoding succeeds, the actual decoding of the z binary codewords are simply done by following the path traced by the blank pattern. If the blank decoding fails, a partial decoding may however be possible. A Gaussian Elimination may also be attempted, also in a blank mode, either after or instead of this partial decoding.

As seen previously, the main point is to find the permutations recursively. Consequently the complexity of this blank decoding is roughly O(n 2 log n), processed only once per packet block. This cost must be compared to the decodings of the z binary codewords (each one having a complexity O(n log n)). The impact of blank decoding on the global decoding complexity of a packet block is evaluated in next section.

III. RESULTS

We have compared our proposal with maximum likelihood decoding using Gaussian Elimination (GE) on an Intel Core 2 Extreme @3.06Ghz on Mac OS X 10.6 in 64-bit mode. Fig. 1 shows the decoding failure probabilities for RM (3, 7) code (k = 64, n = 128), in terms of extra-packets. By extra-packets, we mean the number of received symbols above the source block size k, which corresponds to the erasure channel capacity. We compare ML, which is optimal, with our algorithm and the classical recursive algorithm. In addition, we provide results for the recursive algorithm with only permutation selection and only partial information passing. We can see that our algorithm performs well compared to the optimal GE and requires only 3 extra-symbols in average to match the performances of GE. On the opposite, the raw recursive algorithm is not able to recover anything with up to 20% of extra-symbols. For RM [START_REF] Muller | Application of Boolean algebra to switching circuit design and to error detection[END_REF][START_REF] Oster | Benchmark of Reed-Mller Codes for Short Packet Transmission[END_REF], the decoding speed of both algorithms is provided in Table I. For the sake of completeness, the encoding speed for the RM(3,7) code is in the order of 4Gbps, and the decoding speed of a Reed-Solomon code with the same parameters is around 350Mbps [START_REF] Lacan | Reed-Solomon Forward Error Correction (FEC) Schemes[END_REF].

In Table I, we provide a comparison of the decoding speed and the average overhead between GE and our algorithm for various Reed-Müller codes. All results are provided for packets of 1500 bytes.

For the RM (6, 9) (k = 466, n = 512) code, we compare the decoding speed of GE with our implementation. We For this code, the speed up ratio between our code and the GE is between 40x and 60x, depending on the packet size. This variation can be explained by the fact that the smaller is the packet size, the longer is the pre-decoding phase compared to the actual decoding. This pre-decoding is more complex for GE (a cubic complexity matrix inversion) than the blank decoding for the recursive algorithm. Note, however, that the blank decoding represents 86%, 38% and 17% of decoding time for recursive decoding for packet sizes of 50, 500 and 1500 bytes. It is worth pointing out that for the recursive decoding, only the encoded vector is recovered. We do not take into account the final step which consists in recovering the source symbols from the whole encoded vector, which is in the magnitude of 8 Gbps for this code, and thus far faster than the decoding. In high code rates scenarios, our algorithm is able to decode with only 1% -2% more symbols than the optimal GE decoding. Depending on the target application, one may be interested to use this decoding algorithm, as it allows a ratio of 5x -20x decoding speed compared to GE.

IV. CONCLUSIONS

In this contribution, we have presented a recursive decoding algorithm for Reed-Muller codes based on Plotkin construction. We have shown that the permutation selection and the blank decoding dramatically improve the performances of the decoder. In many scenarios, our algorithm can achieve decoding performance close to the capacity, while achieving speeds of several Gbps. Because of their high decoding speed, Reed-Müller codes are an interesting alternative for the packet erasure channel, when the decoding cost is a bottleneck (e.g. in low power devices and real-time applications).

Fig. 1 .

 1 Fig. 1. Decoding failure rate of GE and recursive algorithms in terms of extra-symbols for RM (3, 7)

TABLE I DECODING

 I SPEED AND OVERHEAD FOR VARIOUS RM CODES provide results for packets of 50, 500 and 1500 bytes which represent classical VoIP, median Internet and LAN data units, in TableII.

	Packet Size Recursive Alg.	Gaussian Elim. Speed Ratio
	50 bytes	546 Mbps	8 Mbps	66x
	500 bytes	2463 Mbps	51 Mbps	49x
	1500 bytes	3291 Mbps	80 Mbps	41x

TABLE II DECODING

 II SPEED FOR RM (6, 9) CODE WITH 5% OF EXTRA-SYMBOLS


Keywords: ad hoc, bi-connectivity, k-connectivity, multipoint relays, OLSR

Résumé : Les multipoints relais ont été introduits pour optimiser l'inondation dans un réseau ad hoc. Ils servent aussi, dans le protocole OLSR, à déterminer une sous-topologie qui conserve les plus courts chemins. Nous montrons, comment une généralisation des multipoints relais permet d'obtenir une sous-topologie conservant des propriétés de biconnexité et plus généralement de k-connexité. Nous montrons de plus, que cette structure de multipoints relais est intrinsèque à toute sous-topologie montrant les mêmes propriétés.

Mots-clés : ad hoc, bi-connexité, k-connexité, multipoints relais, OLSR

Introduction

To allow all pairs of nodes of a network to communicate, the underlying graph has to be connected. If it is k-connected, this property is preserved even under the failure of k -1 nodes. However, optimized link state protocols use only a subset of links, and the resulting sub-topology used for routing may loose this k-connectivity property met by the full network. For better resilience, it is thus interesting to design some sub-topology selection mechanism that preserves k-connectivity if possible. Similarly, we also focus on resilience to link failures.

We show that OLSR routing protocol [START_REF] Clausen | Optimized link state routing protocol (OLSR)[END_REF] when it is parameterized with multipoint relay coverage k preserves k-connectivity of the topology included in the link state advertisements. Moreover, if k ′ ≤ k disjoint paths exist between two nodes, the OLSR topology will include k ′ disjoint routes between them with smallest length sum. In other words, any node is able to compute disjoint routes from the topology it learns from OLSR and these routes are short.

Related work study the influence of power-control on k-connectivity of the network [START_REF] Lloyd | Algorithmic aspects of topology control problems for ad hoc networks[END_REF][START_REF] Kang | Maximizing static network lifetime of wireless broadcast ad hoc networks[END_REF][START_REF] Jennings | Topology control for efficient information dissemination in ad-hoc networks[END_REF]. Our approach is complementary, and acts at routing level instead of link level. Given some power control policy, a link state routing protocol such as OLSR detects neighborhoods and optimizes the quantity of topology information broadcasted to enable efficient pro-active route construction. The results given here apply to any link state protocol where a subset of the topology is broadcasted.

Connectivity graph and k-connectivity

The set of all possible connections in a network can be modeled through a graph G = (V, E) where the vertices u ∈ V are the nodes of the network and where an edge uv ∈ E in the graph indicates that u and v can communicate together. In the case of OLSR, E is made of the links uv with symmetric state, i.e. u and v receive HELLO messages from each other. We then say that u and v are neighbors. We also say that u covers v (or that v covers u) by analogy with radio communications. Let N (u) denote the neighbors of u (excluding u itself). By extension, we will abusively write N (A) to denote the set of neighbors of some node in A excluding nodes in A (N (A) = {v|v / ∈ A and there exists u ∈ A such that uv ∈ E}). N (N (u)) is thus the set of two hop neighbors of u.

A path is a sequence u 0 , . . . , u n of nodes such that u i-1 u i ∈ E for all 1 ≤ i ≤ n. n is the length of the path. A graph is connected when all pair of nodes can be connected by a path. Two paths u 0 , . . . , u n and v 0 , . . . , v m are internal node disjoint when the sets of nodes {u 1 , . . . , u n-1 } and {v 1 , . . . , v m-1 } are disjoint. They are edge disjoint when the sets of edges

{u 0 u 1 , . . . , u n-1 u n } and {v 0 v 1 , . . . , v m-1 v m } are disjoint.
Definition 1 (k-connectivity) A graph is k-connected when it is connected and remains connected after removal of any subset of k -1 vertices. Equivalently, Menger's theorem states that a graph is k-connected iff every pair of nodes is connected by at least k internal node disjoint paths.

Similarly, connectivity can be viewed with respect to edge deletion.

Definition 2 (k-edge-connectivity) A graph is k-edge-connected when it is connected and remains connected after removal of any subset of k -1 edges. Equivalently, a graph is k-edge-connected iff every pair of nodes is connected by at least k -1 edge disjoint paths.

Multipoint relays sub-topology

When the density of a wireless network increases, the number of links may become quadratic. To maintain a sub-quadratic control traffic, OLSR protocol disseminates only a subset of links: MPR links (MPR states for multipoint relay). A node computes its routing table based on these links and links to neighbors. Definition 3 (MPR) Every OLSR node selects a subset of neighbors called multipoint relays (or MPRs for short) such that every two hop neighbor is covered by some MPR.

This covering property is fundamental to the proper functioning of OLSR. It is further parameterized by the MPR coverage parameter [START_REF] Clausen | Optimized link state routing protocol (OLSR)[END_REF] described bellow. A simple greedy heuristic [START_REF] Laouiti | Multipoint relaying: An efficient technique for flooding in mobile wireless networks[END_REF] allows to compute multipoint relay sets with small size. Finding a minimal size set is NP-hard and the greedy heuristic is within a factor 1 + log d from optimal [START_REF] Laouiti | Multipoint relaying: An efficient technique for flooding in mobile wireless networks[END_REF] (d denotes the maximal degree of a node).

When u selects m as MPR, the directed link mu is said to be an MPR link. We also say that u is an MPR selector of m. OLSR protocol disseminates links existence by letting nodes flood topology control messages (TC) containing their list of MPR selectors.

Every node computes its routing table from shortest paths in the directed graph containing all MPR links and links to its neighbors. (Recall that neighbors are discovered through HELLO messages.) More precisely, OLSR protocol constructs routes of the form u 0 , . . . , u n such that u 1 is a neighbor of u 0 (neighbor link) and u 1 u 2 , . . . , u n-1 u n are MPR links. Such a path is called an OLSR route.

Every node uses a different topology to compute its routes. Indeed all MPR links are shared but each node uses its own neighbor links.

To enable more redundancy, the definition of MPRs is parameterized through the MPR coverage parameter [START_REF] Clausen | Optimized link state routing protocol (OLSR)[END_REF][START_REF] Clausen | Investigating the impact of partial topology in proactive manet routing protocols[END_REF]: Definition 4 (MPR Coverage) An MPR set has coverage k if every two hop neighbor covered by d neighbors is covered by min(d, k) MPRs.

In other words, a two hop neighbor must be covered by k MPRs if possible or all its common neighbors if not. The greedy heuristic proposed in [START_REF] Laouiti | Multipoint relaying: An efficient technique for flooding in mobile wireless networks[END_REF] can easily be adapted to compute MPRs with coverage k. Higher coverage enables more redundancy in MPR flooding [START_REF] Clausen | Investigating the impact of partial topology in proactive manet routing protocols[END_REF]. We are going to see that it also enables some k-connectivity property of the MPR link sub-topology.

INRIA 4 k-connectivity and MPR coverage k

As OLSR uses a sub-topology, the existence of k disjoint routes in OLSR topology is not guaranteed by the existence of k disjoint paths in the connection graph. The following theorem makes the link between MPR coverage k and k-connectivity.

Theorem 1 Consider an OLSR network where MPRs are selected with coverage k. If two non neighbor nodes are linked by k internal node disjoint paths in the connection graph, then there exists k internal node disjoint routes from one to the other.

Proof: Consider a connection graph such that two nodes u and v are connected by k internal node disjoint paths. Suppose that each node has elected an MPR set with coverage k. We show that there must exist k disjoint OLSR routes from u to v.

Let C 1 , . . . , C k be k internal node disjoint paths from u to v such that the sum of their length is minimal. Let u 0 = u, . . . , u n = v be the sequence of nodes in C 1 . Let us show by recurrence that there exist a path m i , . . . , m n = v such that m i covers u i-1 , m i m i+1 , . . . , m n-1 m n are MPR links, and none of the paths C 2 , . . . , C k include m i , . . . , m n-1 .

It is obviously verified for i = n. Suppose that the property is verified for i > 1 and let m i , . . . , m n = v be such a path. As m i covers u i-1 , u i-2 is a two hop neighbor. (It cannot be a direct neighbor as C 1 , . . . , C k have been chosen with minimal length sum.) Let d denote the number of neighbors of m i linked to u i-2 . In the case d < k, m i must select all these d neighbors (including u i-1 ) as MPRs. The property is then verified by the path m i-1 = u i-1 , . . . , m n . Now consider the case d ≥ k. m i has selected k MPRs that cover u i-2 . Suppose by contradiction that they all lie in some path C 2 , . . . , C k . There must thus exist a path C j (with 2 ≤ j ≤ k) containing at least two MPRs of m i . Let v 0 = u, . . . , v p = v be the sequence of nodes of C j and let v a and v b (a < b) be two MPRs of m i in C j . Now consider the two paths C ′ 1 = v 0 , . . . , v a , m i , . . . , m n and C ′ j = u 0 , . . . , u i-2 , v b , . . . , v p . They form with C 2 , . . . , C j-1 , C j+1 , . . . , C k k internal node disjoint paths from u to v with smaller length sum since

|C ′ 1 |+|C ′ j | = (a+n-i+1)+(i-2+p-b+1) = n+p-(b-a) < n+p = |C 1 |+|C j |.
To avoid this contradiction, some MPR of m i covering u i-2 must be outside C 2 , . . . , C k . Let m i-1 be this node. The property is then verified by m i-1 , . . . , m n .

We can thus conclude by recurrence that the property must be verified for i = 1. This implies the existence of a path M 1 = u, m 1 , . . . , m n from u to v with same length as C 1 , disjoint from C 2 , . . . , C k and such that links m i-1 m i , 1 < i ≤ n are MPR links. This path is thus an OLSR route.

Similarly, M 1 , C 2 , . . . , C k are k internal node disjoint paths from u to v with minimal length sum. There must thus exist an OLSR route M 2 disjoint from M 1 , C 3 , . . . , C k . Iterating the argument, we can conclude to the existence of k internal disjoint OLSR routes M 1 , . . . , M k included in the OLSR sub-topology known by u.

6 Sub-topology preserving k-connectivity Any link state protocol disseminates in the network the existence of links. If the network may become dense, such as in wireless networks, the protocol has to disseminate only a subset of links to maintain control traffic low. For that purpose, let us formally define the notion of sub-topology.

Definition 6 A sub-topology H = (V, E H ) is a subgraph of the connection graph G (E H ⊆ E).
As every node knows its neighborhood N (u), it knows the graph

H u = (V, E H ∪ {uv|v ∈ N (u)}). H is k-sub-connected if for every pair u, v of nodes, the existence of k ′ ≤ k internal node disjoint paths from u to v in G implies the existence of k ′ internal node disjoint paths from u to v in H u . Additionally, H is optimally k-sub-connected if such disjoint paths have minimal length sum.
This definition simply states that a node u knowing a common broadcasted topology H and its neighborhood can compute k ′ disjoint routes to any destination v when there exists k ′ ≤ k disjoint paths in the full topology. Considering paths from a two hop neighbor of u to u, we can obviously state the following theorem.

Theorem 4 If H is an optimally k-sub-connected sub-topology of G, then the neighbors of a node in H form an MPR set with coverage k in G.

With k = 1, this theorem states that MPRs are an intrinsic structure to obtain routes which are shortest paths. As intuitively mentioned before, a similar theorem can be stated concerning k-edge-connectivity.

Conclusion

Multipoint relays are a necessary and sufficient structure allowing k-connectivity with minimal length sum of the routes provided. They thus appear as an intrinsic structure when optimizing the sub-topology broadcasted in a link state routing protocol.

RR n 6169

Remarks:

The proof still holds if MPR selection is made with MPR coverage k ′ ≥ k.

The proof implies the existence of k disjoint OLSR routes with minimal length sum. In particular, this gives a proof of the existence of shortest path routes in OLSR topology (case k = 1).

A slight modification of the MPR coverage notion allows to extend the theorem to the case where the two nodes are neighbors: Consider two neighbors u and v sharing d other neighbors. There thus exist at least d + 1 internal node disjoint paths from u to v. With complete coverage k ≥ d + 1, u will find these d + 1 paths as OLSR routes. If there exists k ′ > d + 1 disjoint paths, the construction of the previous proof allows to find k -(d + 1) more disjoint routes in the OLSR topology known by u. We can thus state the more general theorem: Theorem 2 Consider an OLSR network where MPRs are selected with complete coverage k. If two nodes are linked by k ′ ≤ k internal node disjoint paths in the connection graph, then there exists k ′ internal node disjoint OLSR routes from one to the other. Moreover, these routes can be chosen with minimal length sum.

k-edge-connectivity and MPR coverage k

Consider the similar problem of selection a sub-topology containing k edge disjoint routes if possible. Consider first the special case where two nodes u and v are two hops away from each other. If they have k common neighbors, we would like to find k edge disjoint routes from u to v. If we additionally require that these routes have minimal length sum, this implies that k advertised links join v to N (u) (all routes must have length 2). In OLSR, this means that v has k MPRs that cover u. Requiring some k-edge-connectivity property with smallest length sum again drives to MPR selection with coverage k.

Conversely, it is not immediate that the existence of k edge disjoint OLSR routes is guaranteed by MPR selection with coverage k. However, the construction of the previous proof is still valid considering edge disjoint paths. We can thus state the following theorem.

Theorem 3 Consider an OLSR network where MPRs are selected with coverage k ′ ≥ k. If two non neighbor nodes are linked by k edge disjoint paths in the connection graph, then there exists k edge disjoint routes from one to the other. Moreover, such routes can be chosen with minimal length sum.

A similar theorem holds for neighboring nodes when MPRs are selected with complete coverage k.

INRIA