Pierre-Antoine Versini
email: pierre-antoine.versini@leesu.enpc.fr

Pascal Jouve

David Ramier

Emmanuel Berthier

Bernard De Gouvello

Use of green roofs to solve storm water issues at the basin scale -Study in the Hauts-de-Seine County (France)

Keywords: Flooding, green roof, hydrological modelling, scale study, sewage network, SWMM

Use of green roofs to solve storm water issues at the basin scale -

Study in the Hauts-de-Seine county (France)

At the building scale, green roof has demonstrated a positive impact on urban runoff (decrease in the peak discharge and runoff volume). This work aims to study if similar impacts can be observed at basin scale. It is particularly focused on the possibility to solve some operational issues caused by storm water.

For this purpose, a methodology has been proposed. It combines: a method to estimate the maximum roof area that can be covered by green roof, called green roofing potential, and an urban rainfall-runoff model able to simulate the hydrological behaviour of green roof. This methodology was applied to two urban catchments affected one by flooding and the other one by combined sewage overflow. The results show that green roof can reduce the frequency and the magnitude of such problems depending on the covered roof surface. Combined with other infrastructures, they represent an interesting solution for urban water management.

Introduction

The increase in impervious surfaces typically associated with urban development is responsible for numerous water management issues both within and outside cities. Storm water runoff affects water quantity and quality causing urban flooding and overflows. It is especially the case in combined sewer systems where urban pollution represents an important issue. Many techniques have been developed (storm water ponds, retention basin, open channels, infiltration systems…) to address these problems and limit the saturation of the storm water sewage network [START_REF] Ferguson | Introduction to Stormwater: Concept, Purpose and Design[END_REF][START_REF] White | Building the Ecological City[END_REF][START_REF] Campisano | A simplified approach for the design of infiltration trenches[END_REF]. Usually, these infrastructures aim to temporarily store excess water before sending it slowly back into the network or the environment (by the mean of discharge, infiltration, or evaporation).

Nevertheless, these infrastructures require available land spaces that are more scarce in densely built downtown urban areas. To cope with urbanization and the problem of space, storm water source control (SC) has gained relevance over traditional sewer approaches [START_REF] Delleur | The evolution of urban hydrology: past, present, and future[END_REF][START_REF] Urbonas | Summary of emergent urban stormwater themes[END_REF][START_REF] Chouli | La gestion des eaux pluviales urbaines en Europe: analyse des conditions de développement des techniques alternatives[END_REF][START_REF] Petrucci | Do stormwater source control policies deliver the right hydrologic outcomes?[END_REF]. The principle of SC is to develop at small-scale (about 10 2 -10 3 m 2 ), simultaneously to urban growth, facilities to prevent storm water problems at intermediate scales (10 4 -10 6 m 2 ). These techniques include green roofs, porous pavements or harvesting tanks, for instance.

Green roofs appear to be particularly relevant because roof areas represent a significant part of the impervious surfaces in urban areas (between 40 and 50%, [START_REF] Villarreal | Response of a Sedum green-roof to individual rain events[END_REF]. At the building scale, the main performance of green roofs in quantitative management of storm water is known to be the reduction of runoff volume at the annual scale and the peak attenuation and delay at the rainfall event scale depending on the green roof structure, the rainfall intensity and the antecedent soil moisture conditions (see [START_REF] Palla | Unsaturated 2D modelling of subsurface water flow in the coarse-grained porous matrix of a green roof[END_REF][START_REF] Vanwoert | Green Roof Stormwater Retention: Effects of Roof Surface, Slope, and Media Depth[END_REF]Jarret et al., 2006 for detailed studies). Moreover, green roofs can avoid the direct contribution of toxic metals as those produced by zinc or lead roof [START_REF] Egodawatta | Understanding the physical processes of pollutant build-up and wash-off on roof surfaces[END_REF][START_REF] Gromaire | Zn and Pb emissions from roofing materials -Modelling and mass balance attempt at the scale of a small urban catchment[END_REF]. For these reasons, over recent years the spread of green roofs is currently underway in developed countries, and more and more green roofs are established. The annual growth in green roof covering is estimated to be between 0.1 to 1 km 2 in several countries all over the world (Spain, Brazil, Canada, Korea, UK or Japan), while it is estimated to reach 2 km 2 in France and higher than 10 km 2 in Germany [START_REF] Lassalle | Panorama technique, historique et géographique[END_REF].

Despite the current spread of green roofs, few works have been published on their impacts on stormwater runoff to solve urban management issues. To our knowledge, most of the previous quoted studies have been focused on the hydrological impact of green roof at the building scale where these impacts initially occur. These works usually present the results provided by an experimental green roof instrumented to collect continuous runoff and precipitation data over short periods of time (not exceeding 3 years): see [START_REF] Bengtsson | Peak flows from thin sedum-moss roof[END_REF]Palla et al., 2008a;[START_REF] Voyde | Hydrology of an extensive living roof under sub-tropical climate conditions in Auckland, New Zealand[END_REF][START_REF] Gregoire | Effect of a modular extensive green roof on stormwater runoff and water quality[END_REF][START_REF] Stovin | The hydrological performance of a green roof test bed under UK climatic conditions[END_REF] instance. In some cases, a rainfall-runoff model has especially been developed to simulate the green roof response [START_REF] Hilten | Modeling stormwater runoff from green roofs with HYDRUS-1D[END_REF][START_REF] Palla | Unsaturated 2D modelling of subsurface water flow in the coarse-grained porous matrix of a green roof[END_REF][START_REF] Berthier | Simulation of Green Roof Hydrological Behavior with a Reservoir Model[END_REF]. In these cases, the observations provided on the experimental set up are used to calibrate the model. Finally, very few studies assessed the possible impacts of green roof at larger catchment scale (Mentens et al., 2003;[START_REF] Carter | Vegetated roofs for stormwater management at multiple spatial scales[END_REF]Palla et al., 2008b), and even less to directly test the implementation of green roof to improve storm water management.

Based on these considerations, this paper aims to study how the spatial distribution of green roofs throughout the watershed can reduce the total volume entering into the drainage network. It is particularly focussed on how far the implementation of green roofs at large scale may impact urban runoff and can eventually solve some operational issues.

This work has been conducted on real cases where the current configuration of the sewage network causes risk situations. A methodology has been proposed to assess the green roof impact at the urban scale. It has been applied on two urban basins affected by flooding and Combined Sewage Overflows (CSO) that are presented in Section 2. The methodology is developed in Section 3. It combines a method of defining green roofing scenarios which estimate the maximum roof area that can be covered, the green roofing potential and a modelling tool able to simulate the hydrological behaviour of green roofs. Integrated into an urban rainfall-runoff model, this tool has been used to study the consequences of several green roofing scenarios in terms of discharge and CSO reduction (Section 4). Finally, the results are synthesized and discussed in Section 5.

Presentation of the Case study (the Hauts-de-Seine county)

The Hauts-de-Seine County is located west of Paris (France). It is a highly populated and urbanized area (1.5 million inhabitants for a surface of 176 km 2 ). The northern part is very urbanized and limited by the Seine River, whereas the southern part is less populated with the presence of several forests. The Hauts-de-Seine climate is very close to the rest of the Paris Basin with mild Winters, frequent rainfalls in Autumn, mild Spring and high Summer temperatures with possible occurrence of intense rainfalls. The average annual rainfall over the county is about 700 mm, whereas the decennial hourly rainfall is about 35 mm.

Because of the rapid growth of urbanization during the 90's and the difficulty to build new management infrastructures due to its density, the stormwater network is very sensitive to intense precipitation which can cause local flooding. Since the beginning of the 2000's, the local authority in charge of water management (Water Direction of the Haut-de-Seine county) tries to mitigate these problems by the use of Sustainable Urban Drainage System (SUDS). In this context, the Hauts-de-Seine county has set up a grant policy to promote regulated flat roofs. An extension of 40 mm with small diameter holes located on the top of the downspouts is used to regulate the roof flow rate. This regulated system is not always accepted by green roof professionals, because of the unknown impacts on the vegetation structure. The Water Direction is also interested in studying the impacts of existing and future green roofs on urban runoff in order to refine their approach in urban hydrology.

As a consequence, two urban watersheds have been chosen, in coordination with the Water Direction, to study the possible impact of green roofs at the basin scale. They are located in Châtillon and Boulogne-Billancourt. Their combined sewer networks are both affected by urban runoff problems during storm events.

Châtillon is a basin of 2.4 km 2 characterized by quite steep topography with an average slope of 3.5%. The upstream part of the basin is essentially covered by individual housing, whereas the downstream part is covered by collective housing and economical activities. Local floodings often occur along the Boulevard de Vanves (see Figure 1), a main road crossing the city center. The pipe along the Boulevard up to the outlet is not large or/and steep enough to route the runoff during intense rainfall. It seems that flooding occurs (almost every year) when the discharge exceeds the limit value of 5 m 3 /s at the outlet. Boulogne-Billancourt (5.5 km 2 ) is a densely urbanized basin near Paris with an average slope of 0.5%, and mainly occupied by collective housing. The southern periphery is more diversified with offices, parks, and industrial wasteland. The basin is often affected by CSOs to the Seine River, which surround a large part of the city (see Figure 1). The frequency of these CSOs is approximately monthly with significant volumes that could be discharged during intense storm. During the last significant event, in July 2010, the total monthly overflowed volume reached 150,000 m 3 .

In order to assess the hydrological impact of green roofs on both basins, several geographical, technical and hydrometeorological data have been obtained. They are useful to:

(i) estimate their green roofing potential, and (ii) model their hydrological behaviour. These data comprise:

• Land use information: The database, called MOS (for "Mode d'Occupation des Sols" in French, see IAU-IDF, 2008), classifies the land surface into 81 main land use categories.

• Topological information: This database called BD TOPO® data (IGN, 2011) includes surface information on the spatial distribution of buildings, roads, rail or hydrographic network.

• Basin information: basin contours, disaggregation into sub-basins and sewage network data (including the layout and the geometrical properties of pipes and sewage infrastructures, operating rules and dry weather flow data) were provided by the Water Direction of the Hauts-de-Seine county.

• Precipitation and potential evapotranspiration (ETP) data: A continuous precipitation database from a rain gauge located close to both basins was provided by the Water Direction. A continuous ETP database was provided by Meteo-France. They cover a full time period from 1993 to 2011 (excepted 1996) with a time resolution of 5 minutes.

• Discharge data: No automatic continuous stream gauge station is installed in the Châtillon basin, but a monitoring programme was conducted from April to June in 2009 to evaluate the discharge at the outlet. On the other hand, Boulogne-Billancourt basin outlet is instrumented by a stream gauge (characterized by a 5-minute resolution). Flow measurements were provided on the 2010-11 time period.

Hydrological modelling framework

In order to test the possibility to mitigate the basin vulnerability and to reduce both flooding and CSO risks, the impact of virtual green roofs has been assessed. Firstly, the studied basins have been modelled to simulate their current response to rainfall. Secondly, this model was used with a specific module representing green roof hydrological behaviour previously developed and presented in details in [START_REF] Versini | Assessment of the hydrological impacts of green roof: from roof scale to basin scale[END_REF]. Finally, the potential for green roofing has been defined at the sub-basin scale by combining several geographic data, this potential is used to compute realistic green roofing scenarios.

Rainfall-runoff simulations with SWMM

Both basins have been represented in the Storm Water Management Model (SWMM, see [START_REF] Rossman | Storm water management model User's manual version 5.0[END_REF] which is a dynamic rainfall-runoff model especially developed for urban/suburban areas by the United States Environmental Protection Agency (EPA). Both sewer networks including junction nodes, conduits, and specific infrastructures (weir, orifice, storage unit …), have been designed to simulate and estimate the hydrological behaviour of the Châtillon and Boulogne-Billancourt basins. As SWMM is a semi-distributed model, each basin is divided into several sub-basins onto which the water balance is computed (see Figure 2).

In order to reproduce correctly the hydrological behaviour of both studied basins, SWMM representations have been tested on past events and compared to discharge observations. In the Châtillon basin, where no continuous measurements were available, simulations have been performed on 3 rainfall events (total precipitation higher than 12 mm).

SWMM simulations appeared to be excellent with a good representation of the peak discharges and a significant Nash-Sutcliffe efficiency [START_REF] Nash | River flow forecasting through conceptual models part I -A discussion of principles[END_REF] higher than 0.85. The Boulogne-Billancourt basin simulation was evaluated by a Nash-Sutcliffe efficiency equal to 0.65 over the 2010-2011 time period. As every peak discharge was well represented, it seems the efficiency deteriorated because of the poor representation of dry weather inflows. Some examples of these simulations are illustrated in Figure 2: one of the 3 rainfall events available on the Châtillon basin and the most severe rainfall event for the Boulogne-Billancourt basin. These results show that observations and simulations match very well at the event scale.

Presentation of the green roof module

The SWMM module called "Bio-retention Cell" has been significantly modified to simulate the hydrological response of green roofs. This module is based on the model developed by [START_REF] Berthier | Bilan hydrique des toitures végétalisées : vers de meilleures compréhension et modélisation[END_REF][START_REF] Berthier | Simulation of Green Roof Hydrological Behavior with a Reservoir Model[END_REF] representing each layer of green roof infrastructure (vegetation, The whole area of the CETE roof (about 400 m²) was split into several compartments (35 m²) differentiated by their type of green roof (type of vegetation, substrate thickness, type of drainage). A detailed presentation of the experimental site is available in [START_REF] Gromaire | Incidence of extensive green roof structures on the quantity and the quality of runoff waters[END_REF]. The reservoir model has been especially adjusted (for more details, please refer to [START_REF] Versini | Assessment of the hydrological impacts of green roof: from roof scale to basin scale[END_REF], for two configurations comprising an extensive vegetation (sedum), a substrate layer and a drainage layer with expanded polystyrene. Both green roof configurations differ in the substrate depth. For the first one, called SE3Y, the thickness is 3 cm and for the second one, called SE15Y the thickness is 15 cm. Meteorological and hydrological data (time step of 3 minutes) compiled from June 2011 to July 2012 have been used to calibrate and validate the model. Satisfactory results were obtained for both configurations, especially for the largest rainfall events. Dynamics of runoff were well reproduced with a Nash-Sutcliffe efficiency close to 0.8 at the storm event scale.

Moreover, the total water balance was correctly respected with an error in volumes close to 10% (this underestimation seems to be related with the overestimation of evapotranspiration but do not affect the representation of peak discharges). Some of these performances are illustrated in Figure 3, where the cumulative runoff and a couple of storm events (one in winter and one in summer) are depicted for SE15Y configuration.

Finally, as the green roof module and SWMM basin configurations provide very satisfactory results, they have been combined for testing the green roof impact on flooding and CSO issues. The green roof module is applied at the sub-basin scale on an area representing the total green surface (not at the building scale).

Evaluation of a green roofing potential

Definition

The potential of green roofing is estimated by combining land use (IAU-IDF, 2008) and building data contained in BD TOPO® (IGN, 2011). The hypothesis has been made that buildings belonging to some specific classes (collective housing, industrial and economic activities, public buildings) could be easily implemented with green roofs (assuming that these roofs are mainly flat). In each class, the roof areas have been deduced by identifying the building areas from the second database (BD TOPO®).

Finally, the potential of green roofing is defined as the percentage of the total subbasin area that could be covered by such technology. It is a high estimation of the real green roofing potential since it assumes that all selected buildings roofs: (i) are flat and without any other equipment (sky-domes, technical materials), (ii) can effectively and technically be "greenable". Note that the assumption on flat roofs is consistent with both cities urbanism.

These potentials also represent a maximum value. Green roofing scenarios will be deduced by selecting a part of this potential.

Spatial distribution on the studied basins

The methodology has been applied to both case studies and the results are illustrated in Figure 1. The potential of green roofing appears to vary significantly from one sub-basin to another.

An average green roofing potential value of 20% of the total catchment is calculated for Châtillon basin. The downstream part of the basin (where individual housing are located) is characterized by a low potential, close to 10%, whereas almost all the sub-basins located upstream from the Boulevard de Vanves have a higher potential, locally reaching more than 50%. The green roof potential is higher and more spatially homogeneous on the Boulogne-Billancourt basin. The average green roofing value is 29.1% and ranges from 5% in the south part (which is currently a former industrial site) to 45% in the central part (where collective housing and economical activities are concentrated).

Study of Green roof impacts

Methodology

For both studied basins, different scenarios of green roofing have been provided. They are based on the potential of green roofing computed at the sub-basin scale. These scenarios correspond to the covering of 12.5, 25, 50 and 100% of the previously defined green roofing surface by SE3Y and SE15Y configurations. In SWMM, these green roof surfaces have been subtracted from the impervious areas at the sub-basin scale. The green roof module, previously integrated into SWMM, is used to compute runoff for these particular surfaces.

Acting in parallel, discharges computed for every contributing surface are added to provide the total sub-basin response.

Precipitation time series on the 1993-2011 time period have been used to simulate the hydrological behaviour of both basins. Such a long period seems sufficient to capture current events (peak discharge and monthly overflowed volumes) characterized by a return period lower than 10 years. For both basins, 35 storm events for which sewage problems occurred have been analysed to see the possible impact of green roofs at the event scale. The accumulated rainfalls of these events reached 2.6 to 120 mm (representing an intensity of 2.5 to 41 mm per hour). Regarding the Intensity-Duration-Frequency (IDF) curves, these events are characterized by some return periods ranging from one month to more than 10 years.

Before being used, potential evapotranspiration data have been adjusted by using a coefficient calibrated on the experimental site (0.5 in winter and 0.7 in summer for SE15Y for example).

Since both studied basins are exposed to a different issue (flooding and CSO), a specific framework has been defined for each case:

•

In the Châtillon basin, which is affected by flooding, the peak discharge flowing through the Boulevard de Vanves has been studied and the return period of annual maximum peak discharge has been particularly calculated. The corresponding midbasin (100 ha) is located downstream of the Boulevard de Vanves.

•

For the Boulogne-Billancourt basin, which is affected by CSOs, the volumes overflowing into the Seine River have been studied. The analysed value represents the cumulative overflowed volumes to the receiving environment by the different outlets located around the basin (see Figure 1). As these overflows are very usual, the frequency of the monthly overflowed volume has also been calculated.

The resulting hydrological indicators (simulated peak discharges and overflowed volumes)

have been computed for the different green roofing scenarios. Then, they have been compared

to the values corresponding to the current situation (without green roof).

Presentation of the results

Simulation results are synthesised in the following sub-sections. First the general impact and scale effect are studied, then the results concerning flooding and combined sewage overflow issues are presented.

General impact on urban runoff and scale effect

Results are synthesized in Table 1. Firstly, it has to be noticed that there is no significant difference between the results obtained for SE3Y and SE15Y green roof configurations. The influence of the total covered area appears to be more important than the substrate thickness.

The decrease in total runoff volume, peak discharge or overflowed volume due to green roofing obviously appears to be higher for SE15Y, but this difference is stronger for the lowest rainfall events. In fact, retention depends on the amount of moisture lost by evapotranspiration prior to rainfall intensity. This has also been noticed on the experimental green roof setup in Trappes and in previous studies [START_REF] Voyde | Hydrology of an extensive living roof under sub-tropical climate conditions in Auckland, New Zealand[END_REF][START_REF] Versini | Assessment of the hydrological impacts of green roof: from roof scale to basin scale[END_REF].

For this reason and for a question of clarity, only the results provided for SE15Y are represented in the next figures (3, 4, 5, and 6).

The total annual runoff volume drained by each basin has been computed for every year of the studied time period (not represented here). The impact of green roofs appears to be quite marginal at the annual scale. The runoff volume reduction ranges from 0.1% (for a coverage of 12.5% of the green roofing potential) to 6% (for a coverage of 100%) on the Châtillon basin. As the average green roofing potential is 20%, these values are quite low.

The influence of green roofs is more significant for the Boulogne-Billancourt basin: here the runoff volume reduction ranges from 0.1% to 14% depending on the green roofing scenarios and the considered year. The reduction seems to be proportional to the green roofing potential covered.

No scale effect is visible when comparing the results for the three studied scales (subbasin, mid-basin, basin). The results are clearly related to the green roofing potential and not on the size of the three entities (see Figure 5). A low potential has to be compensated by a higher percentage of covering in the same proportion. As both basin and mid-basin are characterized by a similarly low potential (between 15% and 25%), the impact of green roofing represents a decrease in approximately 35% for peak flow and 15% for runoff volume in the best case (scenario with 100% SE15Y). A significant modification of discharge appears when at least 50% of the potential is covered. In this case, a peak discharge decrease of 15% is observed. At the sub-basin scale, characterized by a green roofing potential higher than 50%, these modifications are more important, with a maximum decrease of 60% for peak flow and 45% for runoff volume (for the 100% SE15Y scenario). It should be noted that a low covering of the potential (25%) appears to be enough to reduce significantly the peak discharge (of about 15%).

Impacts on flooding (Châtillon basin)

The simulated peak discharges appear to be influenced by the implementation of green roofs when large roof surfaces are covered. The statistical distribution of annual peak discharge represented in Figure 4 shows that 50% of the green roofing potential (representing 10% of the total basin area and 25% of the total impervious area) has to be covered to reduce the peak discharge by 15%, whatever the considered return period. When 100% of the potential is covered, the decrease in peak discharge can reach up to 35%. The performance of green roof is also to be reduced for the larger events. For these cases, the substrate is at field capacity and cannot infiltrate anymore. The effect of the finite retention capacity was already mentioned in previous studies [START_REF] Carson | Hydrological performance of extensive green roofs in New York City: observations and multi-year modeling of three full-scale systems[END_REF][START_REF] Fassman-Beck | 4 Living roofs in 3 locations: Does configuration affect runoff mitigation[END_REF]. Moreover, a seasonal effect can be seen. For the reason mentioned above (the substrate is at field capacity), green roof has less impact in winter than in summer.

The simulated discharge time series for the basin outlet is also represented for the particular storm event of June 2009, for which the value was over the threshold of 5 m 3 /s (Figure 4). As for the statistical distribution, a significant decrease in peak discharge (about 20%) only occurs when almost 50% of the potential is covered (a decrease in 35% is noticed for 100% of the potential). Nevertheless, a potential coverage (12% or 25%) is enough to reduce the peak discharge to below 5 m 3 /s and theoretically avoid flooding (see also Figure 4).

Impact on Combined Sewage Overflow (Boulogne-Billancourt basin)

Monthly volumes of CSO have been computed for the complete time series. Their statistical distribution is illustrated in Figure 6. Whatever the green roofing scenario, the distribution is modified from the normal values to the rarest ones. The overflowed volume is completely avoided for the more common events (return period lower than 2 months) when 100% of the potential is covered. For less frequent events (2 months < T < 1 year), CSO volumes can be divided by two in the same circumstances. Intermediate scenarios (50% of the potential covered) provide a 30% reduction of these volumes. Note that the reduction in CSO volume seems to be higher for the lowest frequencies.

Regarding the results for the 35 studied events (Figure 6), the covering of only 12.5% of the potential seems to produce only a low impact in terms of overflowed volume reduction (an average decrease about 7.6%). The covering of 50% generates an average decrease about 35%, whereas the covering of 100% induces a significant decrease reaching 60% of the CSO volume.

Discussion

These encouraging results are based on a number of implicit hypotheses and limitations that are worth discussing:

• Optimistic estimation of the green roofing potential: as described in this paper, the methodology implemented to estimate the potential of green roofing at the sub-basin scale probably overestimates the real potential. It is assumed that all buildings belonging to the selected land use categories can effectively be covered by green roof, meaning that they have flat roofs, without impeding micro-structure and for which the implementation of green roof is technically possible and not already implemented.

Although the green roofing of slightly sloping roofs may be possible, scenarios based on the covering of 100% of the defined potential are clearly unrealistic. Nevertheless, they illustrate the potential of such structures and encourage the implementation of green roofs for future rehabilitation and developing projects. The results obtained for intermediate scenarios (covering of 25 to 50% of the potential) demonstrate the covering of a significant -but more realistic-part of roof surfaces can provide satisfactory improvement in terms of urban runoff management. Moreover, this study has been conducted by using traditional green roofs. The use of regulated ones -as encouraged by the Hauts-de-Seine County -could still improve their performance by storing more water in the drainage roof structure.

• Short time period for the calibration of the hydrological model: hydrological model parameters have been adjusted using one year of observed discharge. Nevertheless, from June 2011 to July 2012, no severe events were observed. That means the model has been developed to reproduce common events (characterized by a return period lower than 1 year), and we assume it is able to represent correctly rarer events characterized by more intense precipitation. For this reason, the observation of experimental green roofs has to continue in order to capture some more significant storm events. These additional data will be used to improve and/or validate the model in the future. However, the use of current data allows the conclusion that the implementation of green roofs can be useful to limit the consequences of common storm events on sewage network.

•

These results have been computed for two particular urban basins belonging to the Hauts-de-Seine county. For this reason, the figures obtained in terms of flooding and CSO reduction cannot be generalized and transferred to other locations. Indeed, they depend on the basin configuration, especially in terms of green roofing potential but also on the geometry. In different cases, concomitance problems (when a sub-basin response slowed by green roof coincides now with the response of another sub-basin and finally produce an higher discharge) could occur.

Conclusion

A methodology to study the impact of green roof at the catchment scale has been developed.

It includes the design of green roofing scenarios based on a land use analysis and a model simulating the hydrological behaviour of these surfaces. Integrated into an urban rainfallrunoff model, this tool has been applied on two urban catchments suffering specific operational issues (flooding and CSO) in the Haut-de-Seine county.

The presented results illustrate the interest of using green roof to reduce risks due to sewage overflow. The magnitude of both peak discharge and overflowed volumes decrease depends strongly on the effective green roof covering (which is the product of green roof potential and green roof covering). The covering of 100% of the identified implementable roof surfaces result in a significant decrease in peak discharge (between 30 and 60%

depending on the green roofing potential), runoff volume (between 15 and 45%) and overflowed volume (more than 60%). A lower covered area (25 to 50 % of the identified potential), more representative of the reality, is expected to partially reduce the studied problems. It has also appeared that substrate thickness is not really significant regarding the impacts noted at the basin scale.

The definition of generalized recommendation to reduce urban runoff depending on green roof implementation represents a large perspective for future investigations. It is one of the objectives of the TVGEP project supporting this work. Based on this study, the following conclusions can be provided. One hectare of green roof allows the retention of 4500 m 3 per year (representing 450 mm of precipitation). At the basin scale, if 10% of the basin area is covered by green roof, peak discharge is reduced by 16% and overflowed volume by 20%. It also seems that green roof is more efficient in reducing the overflowed volumes than flooding.

These results encourage the large implementation of green roofs to locally reduce sewage network overflows. Combined with other stormwater source controls and/or retention infrastructures, green roofs could participate to significantly reduce the quantity of water flowing into the sewage network during storm events. In addition to thermal and environmental benefits, green roofs can be valuable from an urban water management point of view. This kind of study could be used by policy makers and water management authorities to promote the implementation of green roofs in the future.

  substrate and drainage) by 3 different reservoirs. The model parameters have been adjusted by using an experimental green roof setup on the site of CETE Ile-de-France in Trappes (45 km South-West from Paris, France).

Figure 1 .

 1 Figures

Figure 2 .

 2 Figure 2. Comparison between observations and SWMM simulations for Châtillon (left) and Boulogne-Billancourt (right)

Figure 3 .

 3 Figure 3. Comparison between observed and simulated discharges for the SE15Y configuration. Two storm events are depicted on the left (one in winter and one in summer).The cumulative runoff is represented on the right.

Figure 4 .Figure 5 .Figure 6 .

 456 Figure 4. Results of the SWMM simulations for Châtillon basin by using the different green roofing scenarios: the statistical distribution of annual peak discharge is represented on the left (5 m3/s threshold is indicated) and the storm event of June 2009 is represented on the right.

Table Table1 .

 Table1 At the annual scale, runoff volume reduction (min/mean/max) is computed for every green roofing scenarios on both studied basins (ΔVtot expressed in %). At the event scale,

	peak discharge reduction (ΔQp) is indicated for Châtillon and overflowed volume reduction
	(ΔVcso) is indicated for Boulogne-Billancourt basin.


Mohamed Mourad Hafidhi
email: mohamed.hafidhi@univ-ubs.fr

Emmanuel Boutillon
email: emmanuel.boutillon@univ-ubs.fr

Chris Winstead
email: chris.winstead@usu.edu

Reliable Gold Code Generators for GPS Receivers

This paper 1 examines five strategies for upset protection in Gold sequence generators used to maintain signal acquisition in GPS receivers. This work is motivated by the increased prevalence of single-event upsets in ultra low-power GPS receivers. If any upset occurs in the Linear Feedback Shift Register (LFSR) modules, then the corresponding satellite signal must be re-acquired, resulting in high energy expenditure and time delay. We evaluate the performance and complexity of methods based on error correction and modular redundancy.

I. INTRODUCTION

Global Positioning System (GPS) receivers are heavily used in mobile contexts, and there is motivation to minimize power consumption and maximize battery life in these devices. When operating at minimal power levels, there is greater occurrence of internal logic upsets due to noise processes and external interference in combination with process/voltage/temperature (PVT) variation [START_REF] Borkar | Tackling variability and reliability challenges[END_REF], and these problems increase with the advancement of CMOS technology [START_REF] Jayanth Srinivasan | The impact of technology scaling on lifetime reliability[END_REF]. Logic upsets can manifest as momentary faults in the device's behavior, or as persistent faults that require re-start or signal reacquisition. Fault tolerance has been studied for data fusion in navigational systems that incorporate GPS receivers along with other sensor devices. For example, the authors of [START_REF] Jaradat | Enhanced, delay dependent, intelligent fusion for ins/gps navigation system[END_REF] consider an intelligent data fusion system to compensate for delayed or erroneous GPS data due to acquisition loss or signal obstruction. To our knowledge, there has not been a detailed study of options for internal fault-tolerance to prevent acquisition loss from occuring in GPS receivers.

GPS systems use a family of ranging signals called Course/Acquisition (C/A) codes belonging to the family of Gold pseudo random noise (PRN) sequences. The C/A codes are generated from the product of two 1,023-bit PRN sequences called G1 and G2. Both G1 and G2 are generated by 10-stage LFSR modules [START_REF] Tsui | Fundamentals of Global Positioning System Receivers[END_REF]. Fig. 1 shows the standard G1 generator. If the LFSR register states are disturbed, then the corresponding C/A code state becomes corrupted, resulting in loss of the GPS signal tracking. This problem can be mitigated if the LFSR state registers are protected by an error correction method. This paper presents five solutions to make a system formed of four G1 registers (four is the minimum number of 1 This work has received a French government support granted to the COMIN Labs excellence laboratory and managed by the National Research Agency in the "Investing for the Future" program under reference ANR-10-LABX-07-01. It has also received support from the Brittany Region. Support was also from the US NSF award ECCS-0954747 and the Franco-American Fulbright Commission. satellites to determine the position of a receiver) more robust to upset errors, and evaluates those solutions in terms of their performance benefit and gate overhead. These solutions can be extended and generalized for any type of LFSR register.

Values stored in all registers, at the clock cycle t, will be represented by the matrix R (t) = (r (t) i,j ) with 1 ≤ i ≤ 4 and 1 ≤ j ≤ 10, where j is the j th position of the i th LFSR.

The remainder of this paper is organized as follows. Sec. II describes two Triple Modular Redundancy (TMR) methods, Sec. III presents a row×column parity-check solution, and Sec. IV presents two solutions based on Hamming codes. Each of these sections evaluates the solutions' performance by computing the mean time to failure (MTTF). Sec. V provides synthesis and performance results, and compares the complexity as the number of equivalent NAND gates for each solution. Finally Sec. VI offers conclusions.

II. TRIPLE MODULAR REDUNDANCY (TMR)

TMR is a classical solution for fault tolerance in electronic systems [START_REF] Lyons | The use of triple-modular redundancy to improve computer reliability[END_REF]. In a TMR system, the original module (i.e. the LFSR) is replicated three times, and error correction is achieved by a majority vote operation. In our analysis, we assume every flip-flop is triplicated and assigned a single voter as shown in Fig. 2(a). We note that there are several alternative configurations, such as the triple-voter method or the restorative-feedback voter [START_REF] Winstead | Error correction via restorative feedback in M-ary logic circuits[END_REF], but to minimize overhead we only consider the most basic TMR strategy. If an upset occurs in any one of the three LFSR modules, the other two devices can correct and mask the fault. But once two of the three devices fail an uncorrectable failure results. An uncorrectable failure is inevitable in a long-running LFSR, so we evalute the system's reliability by calculating the system's Mean Time to Failure (MTTF): larger MTTF implies a more reliable system. denotes the x th replica of the j th flip-flop in the i th LFSR of a G1 sequence generator group at the step t.

r t,0 i,j-1 r t,1 i,j-1 r t,2 i,j-1 voter r t,0 i,j r t,1 i,j r t,2 i,j voter corrected state shifted forward (a) Multi-column TMR r t,0 i,j-1 r t,1 i,j-1 r t,2 i,j-1 r t,0 i,3 r t,1 i,3
To compute the MTTF it is first necessary to solve the probability distribution of system failures. It is assumed that upset events in the replicated flip-flops are independent. Let p be the flip-flop upset probability per time step (i.e clock cycle), and X k,t a random variable describing the upset state of the k th bit in an LFSR at time step t. The stored value is either correct (X k,t = 0) or erroneous (X k,t = 1). Given no overall failure prior to time step t -1, Pr(X k,t-1 = 1) = p for all k. After applying the majority vote operation, the probability of a correct state at the voter's output, q v , is given by:

q v = (1 -p) 3 + 3p (1 -p) 2 . (1)
Now let p c be the probability that the entire LFSR state is correct after applying majority vote operations on all flip-flops:

p c = 10 k=1 q v
Let P Fail be the probability of an instantaneous failure in the complete system. This probability is expressed as

P Fail = 1 -p c 4 . (2)
Finally, we calculate P e (t), the probability that the failure of the complete system occurs at time step t:

P e (t) = (1 -P Fail ) (t-1) P Fail . (3)
Since P e (t) has a geometric distribution, the mean of this distribution is well known and yields the MTTF:

MTTF ∞ t=1 tP e (t) = 1 P Fail . (4)
As an example, given a flip-flop upset probability p = 10 -3 , we find P Fail = 1.2 × 10 -4 , and the mean time to failure (MTTF) is equal to 8339 cycles.

In the TMR solution the vote operation is done for every bit of every LFSR. To reduce the complexity, it is possible to perform voting in a single column as described in Fig. 2(b). Since the data is shifted in a circular pattern around the LFSR, any single error will eventually pass through the voter where it can be corrected. The LFSR has length ten, so a single error may persist in the system for at most ten clock cycles. Onecolumn voting tends to decrease (i.e. worsen) the MTTF of TMR. In order to model the propagation of errors through the LFSR, we use the trellis model shown in Fig. 3, which assumes the voter is placed in column three. By choosing this position of the voter, we garantee that every error in this system will pass by the voter and will be corrected in at most 10 clock cycles. Given that no system failure has occured prior to time step t, we only need to consider a trellis depth of ten stages, since a successul correction would have eliminated any errors in the voter's column at time t -10. Let p f (t -τ ) be the error probability in a flip-flop τ time-steps before it's data reaches the voter. Clearly p (t -10) = 0, and for subsequent stages we have

p f (t -τ ) = p (1 -p f (t -τ -1)) + (1 -p)p f (t -τ -1) . (5)
Iterating this calculation in the trellis model, we determine p v , the probability of flip-flop error in the voting column, as the second element in the state vector P v given by

P v = 1 -p p p 1 -p 10 × 1 0 (6)
Using this model, we find the probability of a correct state at the one-column voter's output, q v , by substituting p v in place of p in [START_REF] Borkar | Tackling variability and reliability challenges[END_REF]. Then the instantaneous failure probability for the four-LFSR system is

P Fail = 1 -q 4 v . (7)
The MTTF, in this case and for p = 10 -3 , is equal to 854 clock cycles, nearly ten times lower than TMR. The onecolumn approach trades reliabiliy for complexity gains, as evaluated and compared in Sec. V.

III. METHOD WITH PARITY-CHECK ERROR DETECTION

In this section, we will modify the architecture of each LFSR by adding a parity flip-flop to each row. We define the row parity v (t) i as the modulo-2 sum over all ten values in a single LFSR i at time step t, hence v Given r

(t+1) i,1 = r (t) i,3 ⊕ r (t) i,10 , the expression for v (t+1) i can be simplified as v (t+1) i = 10 j=1 r (t+1) i,j = (r (t) i,3 ⊕ r (t) i,10 ) ⊕ ( 9 j=1 r (t) i,j ) = r (t) i,3 ⊕ ( 10 j=1 r (t) i,j ) = v t i ⊕ r (t) i,3 . (8)
Based on this equation, we add the new parity flip-flop to every LFSR in the system, according to the architecture shown in Fig. 4. In order to detect errors in LFSR i, we independently compute the error as e (t)

h (i) = ( 10 j=1 r (t) i,j ) ⊕ v (t) i . If e (t)
h (i) = 0, an odd number of errors has occurred.

The row-parity solution based on Fig. 4 is sufficient to detect errors but cannot identify their position. In order to detect the location of errors, a new LFSR is added to the system comprised of the column-parity, so that

r (t) 5,j = 4 i=1 r (t) i,j . (9)
Since the parity LFSR is identical to the others, it only needs to be initialized with (9) at a single time t 0 . Under errorfree operation, the condition described by ( 9) is preserved in the LFSR state evolution. The new LFSR sytem consists of five LFSRs: The fifth row is the parity LFSR, and the eleventh column is the set of parity-check bits corresponding to Fig. 4. The column and row errors are detected as e (t)

v (j) = ( 4 i=1 r (t) i,j ) ⊕ r (t)
5,j and e (t) h (i), respectively. If there is a row l where e (t) h (l) = 0, then we should find all positions q for which e (t) v (q) = 0. Errors are corrected by flipping the bit in these positions q using the XOR function as shown in the architecture in Fig. 5. Corrected register values are denoted as r in this figure. With this method, an odd number of errors can be corrected if they occur in only one row. The probability of a system failure in this case is

P Fail = 1 -(1 -p) 55 + 55p(1 -p) 54 .
(10)

Continuing the example from the previous sections with p = 10 -3 , we find that P Fail = 0.0014 and the MTTF is 697. This is far below the performance of TMR. Due to its simplicity, the parity method provides good complexity gain as discussed in Sec. V.

IV. SOLUTION USING HAMMING CODES

Researchers previously considered the theoretical characteristics of multi-LFSR systems protected by linear error correcting codes. For example, Hadjicostis and Verghese considered the asymptotic properties of a large group of identical LFSRs jointly encoded using LDPC codes [START_REF] Hadjicostis | Coding approaches to fault tolerance in linear dynamic systems[END_REF]. In this section, we describe a similar but much smaller scale approach using a basic Hamming code. As in the row/column parity solution, we are using in this method parity LFSRs, which are constructed as linear transformations of the original system. In order to jointly encode the consituent LFSRs and produce valid parity LFSRs, the system must obey to two criteria. First they should be described by the same polynomial as all LFSRs in the original system. Second, the initial states of the parity LFSRs, represented by the matrix R (0) , are obtained using a Hamming encoding operation:

C (0) = G T × R (0)
where G T is the transpose of the generator matrix G of the [START_REF] Hadjicostis | Coding approaches to fault tolerance in linear dynamic systems[END_REF][START_REF] Tsui | Fundamentals of Global Positioning System Receivers[END_REF] Hamming code and R (0) represents initial states of the original four LFSRs. For this encoding we use the standard Hamming generator matrix given by G =     1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1 0 1 1 1 0 0 0 1 1 0 1

   
Since the LFSR states are updated by a linear transformation at each time step, if no errors are generated in the system, then the parity LFSRs will preseve the Hamming code structure [START_REF] Hadjicostis | Coding approaches to fault tolerance in linear dynamic systems[END_REF], i.e. at any time step t,

C (t) = G T × R (t) .
Let Q (t) be the new encoded system, defined by

Q (t)
S (t) C (t) . The system is now a matrix with 10 columns

Q (t) = (Q (t) 1 , • • • , R (t)
10 ). By decoding all columns of Q (t) , we are able to detect and correct errors present in each column decoded at a step t. We assume a syndrome decoding method, which is able to correct a single error. The system in this case fails once two errors are generated in the same column. The probability that a failure is not declared in one column is:

q h = (1 -p) 7 + 7p (1 -p) 6 . (11)

Fig. 1 .

 1 Fig. 1. G1 sequence generator.

Fig. 2 .

 2 Fig. 2. Shift register with TMR protection in each flip-flop, where R t,x i,j

Fig. 3 .

 3 Fig. 3. Trellis graph describing error propagation in the one-column error correction solution.

Fig. 4 .Fig. 5 .

 45 Fig. 4. New architecture of G1 LFSR with row parity.

The probability of an instantaneous failure in the system is:

Using this method, with p = 10 -3 , the MTTF is equal to 4713 clock cycles. To reduce the complexity, decoding can be performed only in one column. To determine the MTTF for this method, we modify the method used for the one-column TMR method. Since Hamming decoding is performed for a single column only, the flip-flop error propagation is modeled by the trellis process in Fig. 3, and the probability of flip-flop error in the decoder's column is p v as given by ( 6). Since a system failure is produced by two or more errors among the flip-flops in the decoded column, we find that

We find, with p = 10 -3 , MTTF = 501. Once again the MTTF is made worse, with a possible gain in complexity.

V. COMPLEXITY AND PERFORMANCE COMPARISON

All of the described methods were evaluated in term of hardware complexity and MTTF. The designs are composed of simple components: flip-flops (FF), 1bit XOR2 modules, and 3-input AND (AND3) gates. The associated equivalent NAND complexity is evaluated for each synthesis product as reported in Table I. Given a probability of an upset in one flip flop, p = 10 -3 , results from the analyse of the mean time to failure and the complexity of diferents method are summarised in Fig. 6. From this figure we can see that the full TMR method provides MTTF close to ten thousand clock cycles, but this is more than what is needed since the PRN are of length 1023. The full Hamming method's MTTF of 4713 is not really a loss since all registers are reinitialized to ones every 1023 cycles. Now by varying the probability of the upset p, the MTTF of all solutions are compared in Fig. 7. The 1023 MTTF threshold is shown as a dashed line in Figs. 6 and7.

VI. CONCLUSION

Our results show a roughly exponential improvement in MTTF with increasing gate complexity. The best choice of protection depends on the technology's upset probability. For a high upset probability, the full Hamming or TMR method may be necessary to achieve an acceptable MTTF. For a small upset probability, the the Hamming (one col.) method provides the required MTTF, but reduces the gate complexity by 42% compared to full TMR.


P Schläfer
email: schlaefer@eit.uni-kl.de

N Wehn
email: wehn@eit.uni-kl.de

M Alles

T Lehnigk-Emden

E Boutillon
email: emmanuel.boutillon@univ-ubs.fr

Syndrome Based Check Node Processing of High Order NB-LDPC Decoders

Non-binary low-density parity-check codes have superior communications performance compared to their binary counterparts. However, to be an option for future standards, efficient hardware architectures must be developed. State-of-theart decoding algorithms lead to architectures suffering from low throughput and high latency. The check node function accounts for the largest part of the decoders overall complexity. In this paper a new, hardware aware check node algorithm is proposed. It has state-of-the-art communications performance while reducing the decoding complexity. Moreover the presented algorithm allows for parallel processing of the check node operations which is not applicable with currently used algorithms. It is therefore an excellent candidate for future high throughput hardware implementations.

I. INTRODUCTION

Upcoming standards like 5G will increase the demands on throughput and latency of communication systems. Especially applications like the Tactile Internet [START_REF] Fettweis | The Tactile Internet: Applications and Challenges[END_REF] require a significantly reduced latency. At the same time, error free transmission has to be guaranteed, which requires forward error correction schemes. Low-Density Parity-Check (LDPC) codes where first proposed by R.G. Gallager in 1963 [START_REF] Gallager | Low-Density Parity-Check Codes[END_REF] and rediscovered by D. Mackay and others in 1996 [START_REF] Mackay | Near Shannon limit performance of Low-Density Parity-Check Codes[END_REF]. In the following almost two decades a lot of research has been carried out in this field. Today many commercial standards (WiMAX, WiFi, DVB-C2, DVB-S2, DVB-T2) make use of LDPC codes. Very long binary LDPC codes have been proven to perform close to the Shannon limit. However when considering short blocks of only some hundred bit length for low latency applications, they suffer under degradation in communications performance of more than 0.5 dB. The extension of binary LDPC codes to Galois Field (GF(q)) with q > 2 is a promising approach to solve this problem. Moreover Non-Binary Low-Density Parity-Check (NB-LDPC) codes are closely related to high-order modulation schemes. Thus an additional gain in communications performance can be observed for systems combining high-order modulation and NB-LDPC codes [START_REF] Pfletschinger | Getting Closer to MIMO Capacity with Non-Binary Codes and Spatial Multiplexing[END_REF]. The performance gain of NB-LDPC codes comes at the cost of significantly increased decoding complexity. The decoding can be performed by message passing algorithms like Belief Propagation (BP), however the complexity increases with the size of the GF(q). A straightforward implementation of the BP algorithm has a complexity of O(q 2 ) [START_REF] Davey | Low-Density Parity Check Codes over GF(q)[END_REF]. In the last years several approaches have been proposed to reduce the decoding complexity without sacrificing the communications performance. Algorithms working in the Fourier domain [START_REF] Barnault | Fast decoding algorithm for LDPC over GF(2q)[END_REF] [7] have an excellent communications performance, but are still too complex for efficient hardware architectures. Symbol flipping algorithms [START_REF] Lu | An efficient majoritylogic based message-passing algorithm for non-binary LDPC decoding[END_REF] [START_REF] Garcia-Herrero | Non-Binary LDPC Decoder Based on Symbol Flipping with Multiple Votes[END_REF] in general have low complexity but suffer from heavily degraded communications performance. Approaches based on stochastic decoding [START_REF] Ciobanu | Adaptive Multiset Stochastic Decoding of Non-Binary LDPC Codes[END_REF] [START_REF] Yang | Area-efficient TFM-based stochastic decoder design for nonbinary LDPC codes[END_REF] have been presented as an alternative decoding method but introduce very high decoding latency. An extension of the well known binary Min-Sum algorithm to the non-binary domain, called Extended Min-Sum (EMS) algorithm [START_REF] Declercq | Decoding Algorithms for Nonbinary LDPC Codes Over GF[END_REF] [13] [START_REF] Li | Trellis-Based Extended Min-Sum Algorithm for Non-Binary LDPC Codes and its Hardware Structure[END_REF] gives the best compromise between hardware complexity and communications performance. Therefore in this paper we will focus on the EMS algorithm which is the most promising starting point for efficient architectures.

To achieve the required throughput of today's applications, executing the algorithms in software is not sufficient. Dedicated hardware architectures become mandatory. The largest complexity in the EMS algorithm is the computation of the Check Node (CN). State-of-the-art architectures apply a so called Forward-Backward (FWBW) scheme [START_REF] Wymeersch | Log-domain decoding of LDPC codes over GF(q)[END_REF] to process the CN. A serial calculation is carried out to reduce the hardware cost and to allow for reuse of intermediate results during the computation. However this scheme introduces high latency and degrades the throughput. This effect increases significantly when the size of the GF(q) or the CN degree grows.

In this paper we propose a new hardware aware algorithm to perform the CN processing within the EMS decoding, we call it Syndrome-Based (SYN) CN processing. While achieving slightly better communications performance than state-of-the-art hardware aware decoding algorithms, the SYN CN processing has a lower complexity. Moreover it allows for increased parallelism of the CN computation. Thus the SYN CN processing is the first hardware aware algorithm for NB-LDPC decoding, enabling low latency and high throughput decoder architectures.

The paper is structured as follows. In Section II we review the decoding of NB-LDPC codes making use of the EMS algorithm. Section III describes the state-of-the-art FWBW hardware aware decoding approach. Our new algorithm is presented in Section IV and further optimizations are discussed in Section V. Finally Section VI presents a comparison with other decoding methods in means of complexity and communications performance.

II. EMS DECODING

This section reviews the EMS algorithm to give an overview of the complete decoding process.

Let us consider an (N, K) NB-LDPC code over GF(q) where N is the codeword length and K the number of information symbols. The code is defined by a sparse parity check matrix H with N columns, M rows and elements h m,n . The transmitted codeword consists of the codeword symbols c = (c 0 , c 1 , . . . , c N ), c i ∈ GF (q). The decoder receives the noisy representation of the codeword symbols, y = (y 0 , y 1 , . . . , y N ).The decoding process can be partitioned in four main parts, the initialisation, the Variable Node (VN) update, the CN update and the permutations in the Permutation Nodes (PNs). For the optimal decoding performance each message from one CN to VN or vice versa contains q Logarithmic Likelihood Ratio (LLR) values representing the reliability of each of the q GF symbols.

The first step in the EMS algorithm is the calculation of the symbol LLRs for the received codeword. From each received symbol y i a set of q LLR values is calculated. Under the assumption that all GF(q) symbols are equiprobable, the LLRs for VN v can be computed as follows:

L v [x] = ln P (y v |c v = xv ) P (y v |c v = x) , ∀x ∈ GF (q) . (1)
Instead of single LLR the set of q LLRs has to be transmit between the nodes. This fact accounts for the significant increase in complexity compared to binary LDPC decoding. Note, that xv is the GF(q) symbol that maximizes In the first iteration the VNs do only forward the channel values to the according CNs. The VN outputs are calculated as

P (y v |c v = x) and L[x v ] = 0. Given this definition all L v [x] ≥ 0
U vp [x] = L v [x]
. For all other iterations the VN operation is to combine the channel values L v with the d v incoming message sets V pv , where d v is the VN degree. The updated extrinsic messages U vp for VN v are calculated as follows:

U vp [x] = L v [x] + dv t=1,t =p V tv [x], ∀x ∈ GF (q), p = 1 . . . d v .
(2) The VN function is to sum up all values for a certain Galois field element received from the connected CNs and the according channel information L v [q]. This however has to be performed for all q elements of the GF(q). To achieve the same message structure as before (LLR = 0 for the most reliable symbol, increasing LLR values for lower reliability), a normalisation of the U vp messages with respect to the most reliable symbol has to be applied at the output of the VN. The next step in the decoding is the permutation according to the parity check matrix H. The permutation of the VN v outputs U vp is defined as:

U pc [x] = U vp [h -1 vc • x], ∀x ∈ GF (q), p = 1 . . . d v , (3)
where U pc represents the input for CN c.

In the CN update d c edges from U pc are processed. The outputs for CN c are calculated as follows:

V cp [x] = min x t =p ; t xt=x dc t=1;t =p U tc [x t ], ∀x ∈ GF (q), p = 1 . . . d c .
(4) For every Galois field element x all possible input combinations fulfilling the parity check constraint are evaluated. The parity check constraint is given by the sum of the according Galois field elements

dc t=1;t =p U tc [x t ] = x.
From all valid combinations the one with the highest reliability (smallest LLR) is chosen. Again, this task has to be performed for all q elements of the Galois field. The CN computation is the most complex part of the decoding and has a complexity of O(q 2 ) when calculated straightforward with the FWBW scheme [START_REF] Wymeersch | Log-domain decoding of LDPC codes over GF(q)[END_REF]. Before one iteration is completed the outputs of CN c must be reverse permuted.

V pv [x] = V cp [h vc • x], ∀x ∈ GF (q), p = 1 . . . d c . (5)
This closes the loop and another iteration starts. The processing of a block is stopped as soon as a valid codeword is detected.

To make this decision the estimated symbols x need to be computed for each VN v:

xv = min x∈GF (q) L v [x] + dv p=1 V pv [x] . (6)
In state-of-the-art EMS decoding one important simplification is applied. As it has been shown in [START_REF] Declercq | Decoding Algorithms for Nonbinary LDPC Codes Over GF[END_REF] the sets of q messages exchanged between VNs and CNs can be truncated to carry only the n m most reliable values per edge without sacrificing the communications performance. This approach significantly reduces the implementation complexity and is used for the algorithms presented in the following sections.

III. FWBW CN PROCESSING

In this section we will first review the state-of-the-art decoding method for the CN calculation, the FWBW scheme.

The FWBW method applies a divide and conquer approach to the CN processing. Each CN processes d c edges at a time following Eq. ( 4). The FWBW scheme splits the processing in three layers of d c -2 so called Elementary Check Nodes (ECNs). Each ECN processes only two edges at a time. Figure 1 shows the resulting structure for a six input CN. Intermediate results of the ECNs are reused in the later stages and avoid recomputations. This significantly reduces the problem size and allows for efficient architectures for the ECN [START_REF] Boutillon | Design of a GF(64)-LDPC Decoder Based on the EMS Algorithm[END_REF]. The processing of the ECN is based on the assumption that the input sets are sorted according to their LLR. Therefore the search space for the best elements can be reduced systematically. In [START_REF] Boutillon | Bubble check: a simplified algorithm for elementary check node processing in extended min-sum non-binary LDPC decoders[END_REF] the authors present a low complexity scheme for the ECN processing which can be implemented efficiently. However, due to the serial processing it requires n m clock cycles. For the complete CN an additional latency penalty of 2(d c -2) + 4 clock cycles is introduced by the structure pointed out in Fig. 1, see [START_REF] Boutillon | Design of a GF(64)-LDPC Decoder Based on the EMS Algorithm[END_REF] for a detailed timing analysis. The overall computation time in clock cycles for one CN is then calculated as follows:

T f wbw = n m + 2(d c -2) + 4 . (7)
This is the drawback of the FWBW approach. With increasing n m and d c the processing time for a CN rises and leads to high latency and low throughput of the complete NB-LDPC decoder. Thus the FWBW method for the CN processing is only an option for moderate sizes of the GF (n m is closely coupled to q) and low Code Rates (CRs) as d c increases significantly for high rate codes. Moreover a parallelization of the FWBW processing is hardly possible which makes low latency decoding infeasible.

IV. SYNDROME-BASED CN PROCESSING

As discussed before, the state-of-the-art way of CN processing with the FWBW scheme has several drawbacks. Architectures making use of the FWBW scheme suffer from low throughput and high latency. Todays approaches to solve these issues are limited to small GF(q)s with q ≤ 4 which have only small gain in Frame Error Rate (FER) compared to their binary counterparts [START_REF] Li | Trellis-Based Extended Min-Sum Algorithm for Non-Binary LDPC Codes and its Hardware Structure[END_REF]. Only with Galois fields of high order significantly higher communications gains can be achieved. Therefore we propose a new algorithm, the so called SYN CN processing which can also be applied to Galois field sizes of practical interest (q ≥ 64). The SYN CN can be implemented in a parallel fashion to achieve high throughput and low latency.

The basic structure of the SYN CN processing is depicted in Fig. 2. In the first step of the algorithm the syndromes are calculated. One syndrome is defined as the sum of one GF(q), LLR tuple from each input. As for each input U , n m tuples can be chosen, there is not just one syndrome but a set of syndromes which we call S. Individual syndromes are distinguished by the elements which are chosen for the sum and denoted as subscripts S x1,...x dc . To achieve S, all possible syndromes are calculated:

S x1,...x dc = dc t=1 U pt [x t ], ∀x 1 , . . . , x dc ∈ GF (q) . ( 8
)
Syndrome Calculator Sorter Decorrelat.

... ... ...

Sorter

Decorrelat.

Fig. 2: Syndrome-based CN processing

Each syndrome is represented by a tuple of LLR and GF(q) values.

S = S x1,...x dc , ∀x 1 , . . . , x dc ∈ GF (q) . (9)
The syndrome set S is the union of all possible syndromes S x1,...x dc .

Calculating the syndromes in S as the sum of elements over all input edges (Eq. ( 8)), disregards one of the basic concepts of BP algorithms: In-and output of the same edge must not be correlated. Thus an additional step in the SYN CN processing is the decorrelation of in-and output:

S i = S x1,...x dc -U pi [x i ], ∀S x1,...,x dc ∈ S, i = 1 . . . d c . ( 10
)
The result is a dedicated syndrome set S i for every output, which has no correlation with input i. Once the S i sets are computed, they are sorted by the syndrome reliability, represented by the LLRs. This gives direct access to the n m most reliable syndromes which constitute the CN output sets V cp .

The algorithm we proposed is an alternative to the conventional FWBW processing. It is the first algorithm for high order Galois fields allowing for massive parallel implementations and thus high throughput and low latency. However, without special treatment the calculation of the syndrome set S and the sorting of S i introduce a high complexity. It has to be reduced to make the algorithm attractive for an efficient hardware implementation.

V. COMPLEXITY REDUCTION

In this section we are presenting an approach to reduce the complexity of the afore introduced SYN CN algorithm. The target is to allow the algorithm to be implemented efficiently in hardware. Therefore we discuss algorithmic modifications for simplifications of the syndrome set generation and the sorting while maintaining the communications performance.

A. Reducing the syndrome set cardinality:

The first point to optimize is the calculation of the syndrome set S. For the output computation only the most reliable The first step for a reduction of |S| is the separation of syndromes with high reliability from ones with low reliability. In the following, a concept similar to the configuration sets introduced in [START_REF] Declercq | Extended minsum algorithm for decoding LDPC codes over GF(q)[END_REF] [19] is applied to the computation of S. Therefore we define d c + 1 deviation sets D i with i ∈ 0 . . . d c . This procedure is just a separation of the syndrome set in subsets:

S = dc i=0 D i . (11)
Each set has i elements deviating from the most reliable element as shown in Fig. 3. Each set contains only syndromes deviating in exactly i elements from the most reliable element as shown in Fig. 3. The subset D 0 contains only one syndrome, which is the sum of the most reliable elements from all inputs. These sub-sets structure the data in a way that allows for easier access to syndromes with high reliability. Figure 4 shows the average LLR values of the syndromes in the sorted deviation sets D i . One can observe, that the distribution of reliable LLRs depends on the Signal-to-Noise Ratio (SNR). Syndromes with more than two deviations e.g. D i for i > 2 have such a low reliability that they rarely contribute to the generation of the outputs. Thus we can limit the calculation of sub-sets D i to the ones with a low amount of deviations.

Another parameter for reduction of |S| is the maximum allowed distance d i of elements contributing to deviation D i . The distance describes the position of the element in the input set relative to the most reliable element. The most reliable element has the index zero. Less reliable elements have higher indices which describe their distance to the most reliable element. For the calculation of D i only elements with indices less or equal to d i are considered. The maximum allowed distance for a certain deviation can be set dynamically based on the LLR value of the elements or it is fixed, as a predefined parameter. For each deviation a different maximum distance can be set, see Fig. 3, e.g. the higher the number of allowed deviations, the lower the maximum distance of the deviations,

d 1 ≥ d 2 ≥ • • • ≥ d dc
Using this scheme implicitly keeps the best syndromes in each D i and removes the less reliable ones. The cardinality of the subsets D i can be calculated as follows:

|D i | =        d c i • (d i ) i if d i ≥ 1; i > 0 1 if i = 0 0 else (12)
Combining both proposed techniques strictly reduces the cardinality of S and thus the computational complexity. The most reliable syndromes are calculated and only unreliable ones are removed. The parametrization for the number of deviations and their maximum distances is a critical step in the algorithm. Using for example only D 0 , D 1 and D 2 with fixed distances

d 0 = 0, d 1 = n m -1, d 2 = 2, d c = 4
and n m = 13, shrinks |S| from 28561 to 73. For a code in GF(64) this has been shown to be a very good trade-off between complexity and communications performance, see Section VI.

B. Simplifying sorting:

One big drawback of the original SYN CN algorithm presented in Section IV is that every syndrome set S i must be sorted separately to output the n m most reliable syndromes. This is the case because of the decorrelation step applied before. To avoid the sorting of the decorrelated syndrome sets S i , a simple but effective approach can be chosen. Instead of decorrelating every value, only syndromes using the most reliable element from the current edge (LLR = 0) are considered. All other syndrome are not used for the current edge output. By this approach the order of the syndromes is not changed and it is sufficient to sort S instead of the d c S i sets. In addition, the LLR values are not modified in the decorrelation step which saves a real valued subtraction for every output message. Finally only the most reliable input element and not the complete input sets must be stored for the decorrelation.

Figure 5 shows the schematic operations of one decorrelator. Each syndrome is denoted with the additional information about which of the input edges contributed to the syndrome with a deviation. SRC in Fig. 5 stores the edges where deviations occurred and ADDR i represents the current edge. A simple comparison evaluates if a deviation from the current edge was involved in the syndrome calculation and thus if the syndrome is valid for the current edge or not. Only if no deviation occurred on the current edge, the decorrelated message is marked as valid and used for the output V i .

Even though the sorting has been reduced to the syndrome set S, there is more potential for simplification. Sorting S can be divided into sorting the deviation sets D i and merging them. Especially for D 1 the sorting can be further simplified. This is achieved due to the previous knowledge we have of the input data. We implicitly know that the sets U pc are sorted according to their LLRs. The sorting of D 1 thus is limited to merging d c sorted sets. serially, is a trivial task that introduces only minimal hardware overhead.

For the higher order deviations D i for i ≥ 2, the ...

Decorrelat.

Sorter

Fig. 8: Syndrome-based CN processing after algorithmic transformation can also be simplified because of the sorted input sets. Sorted sub-sets can be generated with little effort which only have to be merged to achieve the final set. An example of the sub-set generation for D 2 with d 2 = 2 is given in Fig. 7 which can be extended easily to other deviations and distances. Once the sub-sets D i are sorted, the outputs are generated by merging them sequentially as shown in Fig. 6. In the presented case with d c = 4 exactly six sub-sets exist which are then merged for further processing.

The proposed algorithmic modifications result in a slightly different data flow, see Fig. 8. Summarized, three notable benefits arise from the transformation:

• Significant reduction of |S|.

• Simplified sorting of S instead of S i .

• No LLR subtractions and no storage for U i in the decorrelation step.

VI. COMMUNICATIONS PERFORMANCE AND COMPLEXITY COMPARISON

In the following section we discuss the quality of the proposed algorithm in means of communications performance and decoding complexity in means of required basic operations. All results for the communications performance are obtained with a bit true C++ model using Binary Phase Shift Keying (BPSK) modulation and an Additive White Gaussian Noise (AWGN) channel. The simulated NB-LDPC code has a code word length N of 16 GF(64) symbols (96 bits), a CR of 0.5, d v = 2 and d c = 4. The code has been generated based on the approach presented in [START_REF] Poulliat | Design of regular (2,dc)-LDPC codes over GF(q) using their binary images[END_REF]. Both, the FWBW and the SYN CN make use of truncated vectors of size n m = 13, and perform a maximum of 10 iterations with a two-phase scheduling. A bit true fixed-point model with 8 bits for the LLR representation is implemented. Figure 9 shows the performance of different implementations of the EMS algorithm compared with an optimal EMS decoding (no message truncation). For the syndrome based CN we have considered up to four deviations with

d i = (d 1 , d 2 , d 3 , d 4 ).
A second comparison shows the difference with respect to the state-of-the-art hardware aware FWBW decoding. After ten iterations the syndrome based CN computation has a superior performance compared to the FWBW implementation, see Fig. 10. To compare the complexity of the proposed algorithm with state-of-the-art decoding methods Table I lists the number of required basic operations. On the one hand, the SYN CN algorithm requires additional GF(q) additions. In a hardware architecture they can be implemented with simple XOR logic and thus are very cheap in means of required area. On the other hand, the SYN approach uses only a small fraction of adders (24%) and comparators (79%) for LLR values compared to the FWBW algorithm. These operations require real valued adders which are way more expensive than GF(q) adders. Thus the comparison shows a significant benefit for the SYN CN algorithm. Finally our investigation shows, that this holds also for higher order Galois fields.

Regarding future hardware architectures, the proposed algorithm generates a whole new design space. Both, serial and partially parallel architectures can be explored. A serial processing may achieve higher efficiency in means of throughput per area, than state-of-the-art architectures but suffers from the same drawbacks, i.e. high latency and low throughput. Another possibility is the parallelization of the syndrome generation and sorting, leading to a high throughput and low latency architecture. First hardware experiments show promising results for the area efficiency of the proposed architectures. In the future, an extensive study on architectures will be carried out.

VII. CONCLUSION

We have presented a new hardware aware algorithm for the CN processing of NB-LDPC decoders. Our investigations have shown slightly better communications performance compared to state-of-the-art hardware aware decoding algorithms. In addition a comparison of the algorithmic complexity reveals that the proposed SYN CN processing has a lower complexity. The SYN CN algorithm is the first hardware aware CN processing, allowing for low latency and high throughput decoder architectures. In the next step we will design hardware architectures based on the proposed algorithm to further explore its potential.

Fig. 1 :

 1 Fig.1: CN architecture implementing the FWBW scheme. The red line marks one of the serial processing paths.

Fig. 3 :

 3 Fig. 3: Exemplary syndromes with two (filled circles) and three deviations (open circles) and maximum distances d 2 and d 3 .

Fig. 4 :

 4 Fig. 4: Averaged LLR values of D i for a GF(64), d c = 4 code. D i for i > 1 are truncated and show only 48 most reliable syndromes.

Fig. 5 :

 5 Fig. 5: Decorrelator for edge i.

Fig. 6 :

 6 Fig. 6: Syndrome sorting for D 1 and D 2 with d c = 4.

Fig. 7 :

 7 Fig. 7: Sub-set generation for D 2 with d 2 = 2, and SRC denoting the deviation positions.

Fig. 9 :

 9 Fig. 9: Communications performance of the SYN CN compared to EMS decoding.

SYN: Iteration 3 SYN: Iteration 10 FWBW: Iteration 3 FWBW: Iteration 10 Fig. 10 :

 31031010 Fig. 10: Communications performance of the SYN CN compared to the state-of-the-art FWBW scheme.

  and an increasing LLR represents a decreasing symbol reliability. Within the decoding process messages from VN to PN are denoted as U vp , messages from PN to CN as U pc . Respectively messages from CN to PN are called V cp and messages from PN to VN as V pv .

TABLE I :

 I Comparison of algorithmic complexity for GF(64) and GF(256). Parameters for GF(64) n m = 13, d 1 = n m -1, d 2 = 2. Parameters for GF(256) n m = 61, d 1 = n m -1, d 2 = 3.

	Component	LLR add.	LLR comp.	GF add.
	FWBW CN GF(64)	102 (100%)	234 (100%)	102 (100%)
	SYN CN GF(64)	24 (24%)	186 (79%)	271 (265%)
	FWBW CN GF(256)	390 (100%)	1080 (100%)	390 (100%)
	SYN CN GF(256)	60 (15%)	936 (87%)	787 (201%)