Luis Rodríguez-Rodríguez

MD José Ramón Lamas

PhD Jezabel Varadé

PhD Pedro López-Romero

PhD Pilar Tornero-Esteban

PhD Lydia Abasolo

Emilio Gomez

La Concha

Juan Angel Jover

Elena Urcelay

PhD Benjamín Fernández-Gutiérrez

Emilio Gomez De La Concha

Juan Angel Jover

Md / Phd

Plasma soluble IL-6 receptor concentration in rheumatoid arthritis: associations with the rs8192284 polymorphism and with disease activity

Keywords: Rheumatoid Arthritis, Interleukin-6 receptor, rs8192284 IL6R polymorphism

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Rheumatoid arthritis (RA) is a systemic immune-mediated disease characterized by chronic inflammation and cellular proliferation of the synovial lining of joints. It has been previously demonstrated that the balance between pro-and anti-inflammatory cytokines plays an essential role in the progression, severity, and morbidity of this condition. Cytokines are critical mediators of synovial cell activation, which leads to joint destruction [START_REF] Mcinnes | Cytokines in the pathogenesis of rheumatoid arthritis[END_REF].

Interleukin 6 (IL-6) is a cytokine overproduced in RA, both in serum [START_REF] Houssiau | Interleukin-6 in synovial fluid and serum of patients with rheumatoid arthritis and other inflammatory arthritides[END_REF][START_REF] Polgar | Soluble interleukin-6 receptor in plasma and in lymphocyte culture supernatants of healthy individuals and patients with systemic lupus erythematosus and rheumatoid arthritis[END_REF][START_REF] Robak | Serum levels of interleukin-6 type cytokines and soluble interleukin-6 receptor in patients with rheumatoid arthritis[END_REF] and in the synovial fluid [START_REF] Klimiuk | Interleukin-6, soluble interleukin-2 receptor and soluble interleukin-6 receptor in the sera of patients with different histological patterns of rheumatoid synovitis[END_REF]. Although its exact role is unclear, it has been reported to have both pro- [START_REF] Gauldie | Interferon beta 2/B-cell stimulatory factor type 2 shares identity with monocytederived hepatocyte-stimulating factor and regulates the major acute phase protein response in liver cells[END_REF][START_REF] Kopf | Impaired immune and acutephase responses in interleukin-6-deficient mice[END_REF][START_REF] Lotz | B cell stimulating factor 2/interleukin 6 is a costimulant for human thymocytes and T lymphocytes[END_REF] and anti-inflammatory properties in vivo and in vitro [START_REF] Taga | Interleukin-6 triggers the association of its receptor with a possible signal transducer, gp130[END_REF][START_REF] Xing | IL-6 is an antiinflammatory cytokine required for controlling local or systemic acute inflammatory responses[END_REF].

The IL-6 receptor is formed by two different membrane glycoproteins: IL-6Rα, an 80-kDa type I protein referred to as the ligand-binding subunit, and IL-6Rβ, a 130-kDa (gp130) protein referred to as the signal-transducing subunit [START_REF] Taga | Interleukin-6 triggers the association of its receptor with a possible signal transducer, gp130[END_REF]. IL-6 and IL-6Rα form a low-affinity complex that must bind with gp130 to form a high affinity complex that can transduce signals to the cytoplasm. IL-6Rα can be released as a soluble receptor (sIL-6R), bind to IL-6 and then interact with a gp130 moiety located on the surface of any cell [START_REF] Jones | The soluble interleukin 6 receptor: mechanisms of production and implications in disease[END_REF][START_REF] Jones | The role of soluble receptors in cytokine biology: the agonistic properties of the sIL-6R/IL-6 complex[END_REF]. This process, referred to as trans-signaling, may be the most prominent mechanism of IL-6 signaling in the human body [START_REF] Jones | The role of soluble receptors in cytokine biology: the agonistic properties of the sIL-6R/IL-6 complex[END_REF] because the sIL-6R/IL-6 complex can exert an agonist effect on cell types expressing gp130.

The main mechanisms of generating sIL-6R are proteolytic cleavage (PC) of the ectodomain or shedding of the membrane-bound form [START_REF] Jones | The soluble interleukin 6 receptor: mechanisms of production and implications in disease[END_REF][START_REF] Mullberg | The soluble interleukin-6 receptor is generated by shedding[END_REF][START_REF] Mullberg | The soluble human IL-6 receptor. Mutational characterization of the proteolytic cleavage site[END_REF]. A single nucleotide polymorphism (rs8192284 A>C) located at the proteolytic cleavage site (Gln357/Asp358) [START_REF] Mullberg | The soluble human IL-6 receptor. Mutational characterization of the proteolytic cleavage site[END_REF] has been described that results in an amino acid substitution from aspartic acid to alanine (D358A) [START_REF] Kim | Identification of novel SNPs in the interleukin 6 receptor gene (IL6R)[END_REF]. This sequence variation has a marked effect on the shedding of IL-6R [START_REF] Galicia | Polymorphisms in the IL-6 receptor (IL-6R) gene: strong evidence that serum levels of soluble IL-6R are genetically influenced[END_REF], with individuals carrying the minor C allele shedding more membrane-bound receptors than non-C allele carriers.

The aim of this study was to assess the association between the IL6R rs8192284 polymorphism and plasma sIL-6R levels in RA patients. We also assessed the correlation between sIL-6R plasma levels and disease activity.

Material and Methods

Patients and blood samples

Thirty-nine RA patients of Spanish descent were randomly selected from the Rheumatology Outpatient Clinic of Hospital Clinico San Carlos (Madrid, Spain).

RA diagnoses were established using the 1987 ACR criteria [START_REF] Arnett | The American Rheumatism Association 1987 revised criteria for the classification of rheumatoid arthritis[END_REF]. Written informed consent was obtained from all patients, and the study was approved by the hospital's ethics committee.

Blood samples were obtained after 8-12 h of fasting. The samples were centrifuged at 3,000 rpm for 10 min to obtain plasma that was then aliquoted and stored at -70°C until the day of analysis.

Socio-demographic and clinical data, including age, gender, and anticitrullinated cyclic peptide antibody (anti-CCP) status (Euro-Diagnostica, Malmö, Sweden, Immunoscan CCPlus®, considered positive if least one ELISA determination yielded a level >25 IU) were obtained from OBDAR (Prospective Rheumatoid Arthritis Clinical Data of Rheumatology Department, Hospital Clinico San Carlos). The median age at the time of plasma extraction was 66.05 years (inter-quartile rank (IQR) 58.05 -74.87). Thirty-five (89.74%) patients were female and 22 (56.41%) were anti-CCP positive. The tests performed included a 28-joint count for tender and swollen joints, a VAS for the patient's global status, and determination of erythrocyte sedimentation rate (ESR). The tests were performed the same day as the blood extraction, and disease activity scores using 28-joint counts (DAS28) were calculated as previously described [START_REF] Prevoo | Modified disease activity scores that include twentyeight-joint counts. Development and validation in a prospective longitudinal study of patients with rheumatoid arthritis[END_REF]. The mean DAS28 was 4.15 (standard deviation (SD) 1.41).

All subjects were genotyped to determine their IL-6R rs8192284 polymorphism status (see below). The genotype distribution was 14 AA, 15 AC, and 10 CC.

Enzyme-linked immunosorbent assay (ELISA) to evaluate plasma sIL-6R levels

A home-made ELISA kit was developed using high binding 96-well plates that had been coated overnight at 4ºC with a monoclonal anti-IL-6R antibody (R&D Minneapolis, MN, USA), #MAB207, 50 µl/well, diluted in PBS). After each well was washed twice with 200 µl/well of PBS-T (PBS 0.05% Tween 20), 50-µl plasma samples that had been diluted 1:200 in PBS with 1% BSA were plated in duplicate. Samples were incubated for two hours at room temperature.

Samples were washed five times with PBS-T with 1% BSA. Biotinylated polyclonal antibodies against IL-6R (R&D #BAF227) were used as detection antibodies (50 µl/well, diluted in PBS with 1% BSA at 0.3 µg/ml) and the samples were incubated with these antibodies for two hours at room temperature. The samples were then washed with PBS-T with 1% BSA. Then, 50 µl/well of streptavidin-HRP was added to each well and the samples were incubated for 30 minutes. The samples were then washed five times and developed using TMB (eBioscience, San Diego, CA, USA). After 15 minutes at room temperature, the color reaction was stopped using 1 M H 2 SO 4 .

Absorbance was measured using a plate reader (Labsystems iEMS Reader MF, Helsinki, Finland) at 450 nm and corrected at 550 nm.

Genotyping

Subjects were genotyped to determine their IL6R rs8192284 A>C polymorphism status using TaqMan Assays-on-Demand from Applied Biosystems following the manufacturer's protocol and analyzed using the ABI 7900HT Fast Real-Time PCR System (Applied Biosystems, Foster City, CA, USA)

Statistical analysis

The association between plasma sIL-6R levels and the IL6R rs8192284 polymorphism was assessed using a Kruskal-Wallis test. The association between both gender and anti-CCP status and plasma sIL-6R levels were assessed using a Mann-Whitney test. The association between DAS28 and sIL-6R plasma levels was assessed using the Spearman correlation. We decided to perform a sub-analysis of the association between DAS28 and plasma sIL-6R levels according to anti-CCP status. Statistical analyses were performed using Stata v.9 software.

Results

Effect of the IL6R rs8192284 polymorphism on plasma sIL-6R levels

The mean plasma sIL-6R level of the RA patients was 43.63 ng/ml (SD 7.90). Plasma sIL-6R concentrations according to IL6R rs8192284 polymorphism genotype were AA 35.27 (SD 3.50), AC 45.50 (SD 4.58) and CC 52.55 ng/ml (SD 3.18; p = 0.0001) (Figure 1). These results indicate an influence of the rs8192284 polymorphism on sIL-6R plasma levels in RA patients, which is similar to that previously observed in healthy subjects. We also observed a significantly different sIL-6R plasma concentration between the AA and AC genotypes (p < 0.0001) and between the AC and CC genotypes (p = 0.0011).

No significant difference in plasma levels was found due to gender (females 44.07 (SD 8.17) vs. males 39.85 (SD 3.50), p = 0.29) or anti-CCP status (anti-CCP positive 42.56 (SD 8.47) vs. anti-CCP negative 45.02 (SD 7.10), p = 0.34).

Influence of sIL-6R plasma level on disease activity

We analyzed the influence of sIL-6R plasma levels on disease activity, which was measured as DAS28. We found no significant correlation between the two variables (r 2 = 0.03, p = 0.85). However, when we assessed this correlation separately in the anti-CCP positive and anti-CCP negative patients, we observed a significant positive correlation between disease activity and sIL-6R plasma levels in the anti-CCP positive patients (r 2 = 0.45, p = 0.034) and a negative trend in the anti-CCP negative patients (r 2 = -0.45, p = 0.083) (Figure 2).

Discussion

We observed that the presence or absence of anti-CCP antibodies determines the influence that sIL-6R plasma levels have on RA disease activity. Many authors have previously investigated the association between sIL-6R levels and disease activity, but this is the first study that has used the DAS28 score to estimate disease activity and the first to address the influence of anti-CCP status. We decided to divide our sample according to the presence or absence of anti-CCP owing to evidence gathered in recent years that suggested that this auto-antibody could define two different conditions [START_REF] Skogh | Does a positive anti-CCP test identify a distinct arthritis entity?[END_REF][START_REF] Ronnelid | Longitudinal analysis of citrullinated protein/peptide antibodies (anti-CP) during 5 year follow up in early rheumatoid arthritis: anti-CP status predicts worse disease activity and greater radiological progression[END_REF][START_REF] Van Der Helm-Van Mil | The HLA-DRB1 shared epitope alleles are primarily a risk factor for anti-cyclic citrullinated peptide antibodies and are not an independent risk factor for development of rheumatoid arthritis[END_REF].

In previous studies, many variables have been used as measures of disease activity with differing results: while some studies failed to find associations between serum sIL-6R levels and ESR, CRP [START_REF] Klimiuk | Interleukin-6, soluble interleukin-2 receptor and soluble interleukin-6 receptor in the sera of patients with different histological patterns of rheumatoid synovitis[END_REF][START_REF] Franke | Interleukin-6, soluble interleukin-2-receptor and soluble interleukin-6-receptor in sera of patients with rheumatoid arthritis: influences of disease activity and drug therapy[END_REF][START_REF] Uson | Soluble interleukin 6 (IL-6) receptor and IL-6 levels in serum and synovial fluid of patients with different arthropathies[END_REF], a count of tender/swollen joints, or Ritchie's index [START_REF] Uson | Soluble interleukin 6 (IL-6) receptor and IL-6 levels in serum and synovial fluid of patients with different arthropathies[END_REF], others were able to find a positive association between these variables and disease activity (measured as a four level scale) [START_REF] Polgar | Soluble interleukin-6 receptor in plasma and in lymphocyte culture supernatants of healthy individuals and patients with systemic lupus erythematosus and rheumatoid arthritis[END_REF][START_REF] Robak | Serum levels of interleukin-6 type cytokines and soluble interleukin-6 receptor in patients with rheumatoid arthritis[END_REF] or Ritchie's index [START_REF] Robak | Serum levels of interleukin-6 type cytokines and soluble interleukin-6 receptor in patients with rheumatoid arthritis[END_REF]. None of the studies characterized the anti-CCP status of the sample. We found that the presence or absence of these auto-antibodies was essential for determining the association between sIL-6R plasma level and disease activity. Therefore, varying composition of the RA samples included in each study may explain their apparently conflicting results.

As reported by Galicia et al. [START_REF] Galicia | Polymorphisms in the IL-6 receptor (IL-6R) gene: strong evidence that serum levels of soluble IL-6R are genetically influenced[END_REF] and Marinou et al. [START_REF] Marinou | A gain of function polymorphism in the interleukin 6 receptor influences RA susceptibility[END_REF], the IL6R rs8192284 polymorphism influences the serum level of sIL-6R in healthy individuals, with more copies of the minor C allele causing higher concentrations. In our sample of RA patients, this polymorphism showed a similar influence on plasma sIL-6R levels. We assessed the influence of gender and anti-CCP status on plasma sIL-6R concentration, but none of these factors showed a significant influence.

Many authors [START_REF] Skogh | Does a positive anti-CCP test identify a distinct arthritis entity?[END_REF][START_REF] Ronnelid | Longitudinal analysis of citrullinated protein/peptide antibodies (anti-CP) during 5 year follow up in early rheumatoid arthritis: anti-CP status predicts worse disease activity and greater radiological progression[END_REF][START_REF] Van Der Helm-Van Mil | The HLA-DRB1 shared epitope alleles are primarily a risk factor for anti-cyclic citrullinated peptide antibodies and are not an independent risk factor for development of rheumatoid arthritis[END_REF] consider RA with anti-CCP antibodies as a different condition and/or disease than RA without anti-CCP. The fact that the association of sIL-6R concentration with DAS28 depended on anti-CCP status could be a reflection of different pathophysiological processes underlying the presence or absence of this autoantibody. Moreover, as previously mentioned, IL-6 is a pleiotropic cytokine. We hypothesize that the balance between the proand anti-inflammatory effects of IL-6 may be tilted towards the pro-inflammatory side in anti-CCP-positive patients and tilted towards the anti-inflammatory side in anti-CCP-negative patients.

Tocilizumab [START_REF] Maini | Doubleblind randomized controlled clinical trial of the interleukin-6 receptor antagonist, tocilizumab, in European patients with rheumatoid arthritis who had an incomplete response to methotrexate[END_REF] is a novel biological therapy used in the treatment of RA that is composed of antibodies directed against IL-6Rα. Because disease activity only correlated with sIL-6R plasma level in anti-CCP positive subjects, we speculate that this subset of RA patients should show a better response to this treatment.

A replication of these observations is needed. Soluble IL-6R plasma levels (ng/ml)

Figure 1 .

 1 Figure 1. sIL-6R plasma concentration according to the genotype of the IL-

Figure 2 .

 2 Figure 2. Correlation between disease activity score (DAS28) and sIL-6R

This work was supported by a research grant from Roche Farma S.A. It was also partially supported by the RETICS Program, RD08/0075 (RIER) from Instituto de Salud Carlos III (ISCIII).


Miguel Lopes

Cécile Saint Cloment Olivier Goupille

Yvan Lallemand

Ana Cumano

Benoît Robert

Msx genes define a population of mural cell precursors

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.


Jérôme Brulin
email: jerome.brulin@saint-gobain.com

Frédéric Roulet
email: frederic.roulet@saint-gobain.com

Amna Rekik
email: amna.rekik@univ-orleans.fr

Eric Blond
email: eric.blond@univ-orleans.fr

Alain Gasser
email: alain.gasser@univ-orleans.fr

Rory Mc Nally

Muriel Micollier

Éric Blond

Rory Mcnally
email: rory.mcnally@saint-gobain.com

Latest Evolution in Blast Furnace Hearth thermo-Mechanical Stress Modelling

Keywords: blast-furnace, modeling, hearth, ceramic cup

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The BF Hearth is the most critical part within the whole integrated steel plant. A major incident with the hearth impacts all downstream activity resulting in serious loss. In some cases, such an episode can endanger overall viability of the whole site. When long, stable BF operation is achieved optimum operating conditions can be maintained throughout the process; efficiency and profitability can be maximised. Problems above tuyere level can often be resolved with minimal disturbance, but not hearth problems. With Savoie/Saint-Gobain BF design and supply experience, the importance of the hearth was recognised, a major R&D programme (still ongoing) commenced and the first "Ceramic Cup" technology was pioneered in 1984. Major improvements were also made in carbon quality around the same time resulting in finer pored structures (minimising metal penetration) and additions of ceramics (to improve erosion resistance). The graphite approach had limited success but the importance of freezing a protection layer on the carbon hot-face was recognised leading to further carbon quality changes (higher conductivity) and a reassessment of optimum wall thickness.

Even if all these improvements have been shown, it becomes more and more necessary to quantify their impact in terms of stress fields in the structure. It is in fact essential to bring the guarantee that new proposed materials and designs still allow to support the thermomechanical stresses in the BF hearth. In order to meet these requirements, Saint-Gobain has developed a thermomechanical model for the BF hearth. This paper will summarise the specific behaviour laws implemented for the ramming mix and the masonries. The parameters of these models were all identified thanks to specific tests up to 1500°C. These behaviour laws were then validated and implemented in the final BF hearth model. The modelling of a hearth is compared with in-situ instrumentation results. A good agreement is reached between these results.

The BF hearth

The blast furnace hearth is mainly composed of refractory materials to support strong thermomechanical loads. Indeed, there is a direct contact between its internal walls and the molten pig iron at 1500°C. As shown on figure 1, the hearth is divided into five parts which must be accurately modelled: a steel shell, a carbon ramming mix layer, carbon blocks and two kinds of masonries (bricks with mortar joints) called the bottom and the ceramic cup. Although the temperature distribution has been for a long time the most important result to compute [START_REF] Gdula | Mathematical model of steady state heat transfer in blast furnace hearth and bottom[END_REF][START_REF] Kurpisz | A method for determining steady state temperature distribution within blast furnace hearth lining by measuring temperature at selected points[END_REF][START_REF] Verdeja | Using FEM to determine temperature distribution in a blast furnace crucible[END_REF], thermomechanical models for the BF hearth progressively appeared [START_REF] Piret | Study of behaviour of cement and mass joint utilisated in aggregates of steel industry[END_REF][START_REF] Gruber | FEM simulation of the thermomechanical behaviour of the refractory lining of a blast furnace[END_REF]. These ones have shown the mains efforts which must be made in order to build a model closer to reality:

-The temperature-dependant behaviour of bricks and mortars must be identified up to 1500°C; -An accurate modelling of the ramming mix is essential in order to reproduce its hardening behaviour in compaction; -The behaviour of joints in masonries must be taken into account. These three parts were studied by Saint-Gobain to build this new BF hearth model.

The ramming mix

A particular attention was paid to the modelling of the ramming mix whose hardening behaviour allows absorbing the thermal expansion of refractory bricks and so protecting the steel shell. This material is porous with voids filled with fluids (air, hydrocarbon binder). That is why during a compaction step, plastic deformations appear leading to volume changes and increasing stiffness. For this kind of materials, a cap plasticity model seems to be the best way to take into account the hardening behaviour [START_REF] Roscoe | On the yielding of soils[END_REF]. Moreover, when submitted to shearing conditions, the material can reach a critical state in which shearing occurs without any changes in stress or volume. Both behaviours under shear and compression loads will be simply reproduced thanks to the "modified Cam-Clay" material model of ABAQUS finite element software [START_REF]Abaqus Standard Reference Manuals[END_REF]. This model is an extension of the theory developed by Roscoe [START_REF] Roscoe | On the generalized stress-strain behaviour of 'wet' clay[END_REF] for geotechnical materials.

The modified Cam-Clay model

This model is composed of non-linear elastic and plastic behaviours. The inelastic behaviour is activated when the yield function CCM F is reached. A strain hardening theory allows the size of the yield surface to change according to the inelastic volumetric strain. The plastic strain rate is defined by an associated flow assumption. The model (figure 2) is based on the following yield surface:

0 1 1 1 2 2 2 = - ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ + ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ - = Ma q a p F CCM β
where is the equivalent pressure stress; is the Mises equivalent stress; is the deviatoric stress; is a constant that defines the slope of the critical state line; is the size of the yield surface; is the yield stress in hydrostatic compression; is a constant which can modify the shape of the cap. The parameter is used to take into account the influence of temperature on the hardening behaviour.

When this surface is reached for values of q upper than the product Mp, the material has a softening behaviour. In the other case, a hardening behaviour is defined. As shown on figure 3, the hardening law is written in the (e,ln(p)) plane, where e is the void ratio of the the logarithmic bulk modulus for the elastic behaviour;

the logarithmic hardening constant for the plasticity;

the void ratio for a hydrostatic pressure of 1 MPa;

the initial conditions of consolidation of the material.

Parameters identification

An instrumented floating die compaction test was developed to identify the parameters of the hardening behaviour and their evolution with temperature.

Triaxial tests were carried out to determine the parameter M which defines the critical state in shearing. In these tests, the ramming mix sample is a cylinder submitted to an increasing axial stress. The radial stress applied is kept constant in the triaxial test although it increases in the die compaction test.

Accounting for the loads applied on the ramming mix in the BF hearth, these tests were done for temperatures lower than 80°C and velocities lower than 1 mm/min. The details on these tests and the parameters identification method are described in [START_REF] Brulin | Characterization and modelling of a carbon ramming mix used in hightemperature industry[END_REF]. The identified parameters of the modified Cam-Clay model allow to accurately reproduce the shearing (figure 4) and hardening behaviours (figure 5) of the ramming mix. The ability of the model to fit with the elastic and plastic parts of the hardening behaviour was shown as well.

Validation of the model

In order to validate the previous results, another die compaction at a variable temperature is performed.

As shown on figure 6, it confirms the faculty of this model to reproduce the temperature effect on the hardening behaviour. It is the influence of the parameter β which is pointed out. The stresses applied on the sample decrease when the temperature increases. This phenomenon is also observed in [START_REF] Graham | Modified cam-clay modelling of temperature effects in clays[END_REF] and induces a decrease of the yield surface (and so the elastic region) with temperature.

The behaviour of the considered ramming mix was described by a modified Cam-Clay model. The model parameters have been experimentally determined for different temperatures and velocities. A good agreement between results of simulations and tests is reached with this model.

The masonries

Accounting for the behaviour of masonries (bottom and ceramic cup) is also important because they are submitted to high thermal loads which can lead to the opening of mortar joints. So, it is essential to characterize the behaviour of bricks, mortars and their interfaces up to 1500°C.

Characterization of masonries

For that purpose, new compressive tests at high temperature on cylindrical samples have been developed (they were used to characterize the carbon blocks behaviour as well). They allowed to identify the Young modulus E of the linear elastic behaviour for bricks and mortars. A slight decrease of the Young modulus with temperature was observed. Moreover, the Young modulus of bricks was identified ten times stiffer than the mortars' one. These results clearly show temperature influence and mortar's role which lead to a softer behaviour for the masonry. This softening behaviour may be often due to joint openings, considering their small thickness. Specific shear and tensile tests on brick-mortar samples were built up to 1500°C. Thanks to the tensile tests, the brittle failure (figure 7) of the brick/mortar interfaces was observed. In fact, the load applied on the sample leads to a shear stress τ and a normal compressive stress n σ on the interface. It is worth noting that a high decrease in tensile strength and cohesion is observed as temperature increases. It reinforces the need to take into account these possible joint openings which will lead to stress softening in the masonry.

Masonry modelling

Considering the high number of joints in the masonries of the BF hearth, instead of a discrete approach which could lead to numerical problems, a micro-macro approach with homogenization method was developed. It allows to replace bricks and mortars by an equivalent homogenous material. To that end, the masonry is first studied at the microscopic level, considering a representative elementary volume loaded with homogeneous boundaries conditions [START_REF] Bornert | Homogenization in Mechanics of Materials[END_REF]. Due to the periodicity of the studied masonries (bottom and ceramic cup), a periodic homogenization method is applied [START_REF] Anthoine | Derivation of the in-plane elastic characteristics of masonry through homogenization theory[END_REF]. The periodic elementary cell is composed of two components whose behaviours were experimentally identified as previously explained:

-The brick with a linear elastic behaviour; -The mortar with a linear elastic behaviour and a yield surface in tension and in shear (figure 8). Once the mortar yield surface is reached, a loss of stiffness is defined.

The macroscopic model built from this microscopic approach is thus based on the assumption that the failure will occur in the mortar due to its small thickness. It defines a joint states model inspired from [START_REF] Luciano | Homogenization technique and damage model for old masonry material[END_REF]. The proposed model is an extension of previous works [START_REF] Gasser | Modelling of joint effects on refractory lining behaviour[END_REF][START_REF] Nguyen | Mechanical homogenisation of masonry wall without mortar[END_REF][START_REF] Landreau | Modelling of a coke oven heating wall[END_REF] dealing with the modelling of mortarless masonries.

Working on a periodic elementary cell with head and bed joints, 4 states can be reached according to the joint openings. For each one of them, an Equivalent Homogeneous Material (EHM with orthotropic elasticity) must be obtained. Moreover as shown on Displacement (mm) figure 9, a stress criterion is defined between these states.

Figure 9: Macroscopic joint states model.

In order to identify the various EHM and stress criteria (at different temperatures), the periodic elementary cell is submitted to chosen strain fields E (uniaxial, biaxial en shear strains). For each applied strain field, the strain energy is computed by the ABAQUS software. The knowledge of the applied strain and the computed energy allows to deduce the macroscopic stress Σ (direct identification from energetic equivalence). From this one, the macroscopic stress criterion between the states and the effective orthotropic stiffness tensor of each state C ~

(from

E C : = Σ ) are identified.
The developed masonry model, accounting for temperature effects and joint openings, was implemented in Abaqus/Explicit thanks to a VUMAT subroutine.

Validation of the model

A shear wall test available in the literature [START_REF] Vermeltfoort | Shear tests on masonry walls[END_REF] was chosen for the validation of the developed model. As described on figure 10(a), the masonry is first submitted to a vertical pressure (p=0.3 MPa). Then, a monotonic horizontal displacement of the upper steel beam is imposed in a confined way (figure 10(b)). The upper beam is kept horizontal during the whole test. This test is particularly interesting for the validation of our model because joint openings in tension occur in the corners of the wall as a diagonal opening in shear (figure 11(a)). Figure 12 presents the evolution of the horizontal load applied on the upper beam needed to impose its horizontal displacement. This result clearly shows the ability of the developed model based on a homogenization approach to reproduce the nonlinear behaviour of masonry.

BF hearth thermomechanical modelling

The new ramming mix and masonry behaviours are implemented in the axisymmetric BF hearth modelling. For the bottom and the ceramic cup, equivalent homogeneous materials with different states were identified at 20°C, 900°C and 1450°C, thanks to a large experimental campaign. The masonry behaviour evolves as a function of temperature and joint opening state. The thermomechanical modelling of the BF hearth was divided in two steps. The thermal computation is first achieved, defining the thermal field which is then applied as a load for the mechanical computation. Results of simulations are compared with in-situ measurements.

Thermal computation

The BF hearth is submitted to high thermal exchanges. They are due to the cooling systems in the external part and to the molten pig iron in the internal part. From these loads, the thermal field presented on figure 13 is computed. This result shows the insulation power of the ceramic cup which protects the carbon blocks from high temperatures (maximum of 500°C). In order to validate the temperature profile, 17 thermocouples were located in the carbon blocks: 12 around the ceramic cup and 5 below the bottom. Figure 14 shows the good agreement which is reached between measured and computed temperatures.

Mechanical computation

For the mechanical computation, the ramming mix and the masonries are modelled with the behaviour laws previously described. Moreover a linear elasticity with temperature dependence is considered for the carbon blocks. Between these blocks, contact conditions (friction for the tangential behaviour and no penetration condition for the normal behaviour) are defined. The BF hearth is submitted to the computed thermal field, gravity, gas and pig iron pressures. In order to check the improvements due to the developed behaviour laws for the ramming mix and the masonries, four different cases are modelled. They differ from the masonry model (with or without possible joint openings) and the initial relative density RD of the ramming mix in the BF hearth (80% or 92%). The relative density is linked with the void ratio by:

e RD + = 1 1
For each model, the evolution of the von Mises stress on the steel shell height is plotted on figure 15. Studying the stresses in the steel shell which is the external part of the hearth allows to demonstrate the influence of the improvements done. Thanks to the new ramming mix model, it is possible to quantify the impact of the initial state. In fact, the more the ramming mix is initially compacted, the less it can absorb thermal expansion of refractory blocks. In that case, a high stress is computed in the steel shell. The effect of joint openings in masonries is clearly shown thanks to the stress softening which occurs. Moreover, the result obtained with "Openings + RD=80%" (close to in-situ situations) is closer to reality (100 MPa is the highest authorized stress in the steel shell).

Conclusion

The materials and solutions proposed for the design of new BF hearths need to bring the guarantee they will support the thermomechanical stresses in the structure. For that purpose, Saint-Gobain has built a new model of BF hearth based on an ambitious program of material modelling and characterization. This work mainly concerns the ramming mix and the masonries for which specific tests were carried out. From these, the parameters of new behaviour laws were identified: -a Cap model for the ramming mix which allows to reproduce the hardening behaviour in compaction and the temperature influence. -a joint states model based on homogenization technique for the masonries. Stress softening due to temperature increase and joint openings are taken into account.

Temperature (°C)

Finally the implementation of these models in the BF hearth modelling gave results closer to reality.

Figure 1 :

 1 Figure 1: Constituents of the hearth.

Figure 2 :

 2 Figure 2: Modified Cam-Clay model.

ρ

  a sample of mass m, volume V and real density r ρ , the void ratio is calculated as: Linear relations for the elastic and inelastic parts are described.

Figure 3 :

 3 Figure 3: Hardening behaviour. The different parameters of the hardening behaviour are:the logarithmic bulk modulus for the elastic behaviour;

Figure 4 :

 4 Figure 4: Triaxial tests for different radial pressures.

Figure 5 :

 5 Figure 5: Die compaction test at room temperature.

Figure 6 :

 6 Figure 6: Die compaction test at variable temperature.

Figure 7 :

 7 Figure 7: Brittle failure from a tensile test.

Figure 8 :

 8 Figure 8: Yield surface for the mortar behaviour.

Figure 10 :

 10 Figure 10: (a) Vertical pressure; (b) Horizontal displacement.

Figure 11 :

 11 Figure 11: Crack patterns comparison: (a) Experimental result; (b) Numerical result.

Figure 12 :

 12 Figure 12: Experimental and numerical evolutions of the horizontal load applied on the upper beam.

Figure 13 :

 13 Figure 13: Thermal field in the BF hearth.

Figure 14 :

 14 Figure 14: Comparison for 17 thermocouples between measured and computed temperatures.

Figure 15 :

 15 Figure 15: Comparison of the von Mises stress computed on the steel shell between four models.


Thomas Braibant

Coquet: a Coq library for verifying hardware

come

Introduction

Formal methods are widely used in the verification of circuit design, and appear as a necessary alternative to test and simulation techniques. Among them, model checking methods have the advantage of being fully automated but can only deal with circuit of fixed size and suffer from combinatorial explosion. On the other hand, circuits can be formally specified and certified using theorem provers [START_REF] Hanna | Veritas + : A specification language based on type theory[END_REF][START_REF] Gordon | Why higher-order logic is a good formalisation for specifying and verifying hardware[END_REF][START_REF] Hunt | The Verification of a Bit-slice ALU[END_REF]. For instance, the overall approach introduced in [START_REF] Gordon | Why higher-order logic is a good formalisation for specifying and verifying hardware[END_REF][START_REF] Melham | Higher Order Logic and Hardware Verification[END_REF] to model circuits in higher-order logic is to use predicates of the logic to express the possible behaviour of devices.

We present a study for specifying and verifying circuits in Coq. Our motivations are two-fold. First, there has been a lot of works describing and verifying circuits in logic in the HOL and ACL2 family of theorem provers. However, Coq features dependent types that are more expressive. The Veritas language experiment [START_REF] Hanna | Veritas + : A specification language based on type theory[END_REF] hinted that these allow for specifications that are both clearer and more concise. We also argue that dependent types are invaluable for developing circuits reliably: some errors can be caught early, when type-checking the circuits or their specifications. Second, most of these works model circuits using a shallow-embedding: circuits are defined as predicates or functions in the logic of the theorem prover, with seldom, if any, way to reason about the devices inside the logic: for instance, functions that operate on circuits must be built at the meta-level [START_REF] Slind | Proof producing synthesis of arithmetic and cryptographic hardware[END_REF], which precludes one from proving their correction. We define a data-type for circuits and a meaning function: we can write (and reason about) Coq functions that operate on the structure of circuits.

Circuit diagrams describe the wire connections between gates and have nice algebraic properties [START_REF] Brown | Categories, allegories and circuit design[END_REF][START_REF] Lafont | Towards an algebraic theory of boolean circuits[END_REF]. While we do not prove algebraic laws, our library features a set of basic blocks and combinators that allows one to describe such diagrams in a hierarchic and modular way. We make precise the interconnection of circuits, yet, we remain high-level because we make implicit the low-level diagram constructs such as wires and ports. Circuit diagrams are also used to present recursive or parametric designs. We use Coq recursive definitions to generate circuits of parametric size, e.g., to generate a n-bit adder for a given n. Then, we reason about these functions rather than on the tangible (fixed-size) instantiations of such generators. Circuits modelled by recursion have already been verified in other settings [START_REF] Hunt | The Verification of a Bit-slice ALU[END_REF][START_REF] Melham | Higher Order Logic and Hardware Verification[END_REF]. The novelty of our approach is that we derive circuit designs in a systematic manner: we structure circuits generators by mimicking the usual circuit diagrams, using our combinators. Then, the properties of these combinators allow us to prove the circuits correct.

We are interested in two kinds of formal dependability claims. First, we want to capture some properties of well-formedness of the diagrams. Second, we want to be able to express the functional correctness of circuits -the fact that a circuit complies to some specification, or that it implements a given function. Obviously, the well-formedness of a circuit is a prerequisite to its functional correctness. We will show that using dependent types, we can get this kind of verification for free. As an example, the type-system of Coq will preclude the user to make invalid compositions of circuits. Hence, we can focus on what is the intrinsic meaning of a circuit, and prove that the meaning of some circuits entails a high-level specification, e.g., some functional program.

Our contributions can be summarized as follows: we propose a new framework to model and verify circuits in Coq that allows to define circuits in a systematic manner by following usual diagrams; we provide tactics that allow to reason about circuits; we demonstrate that our approach is practicable on practical examples: text-book n-bit adders, high-level combinators, and sequential circuits.

Outline. In §1, we give a small overview of all the basic concepts underlying our methodology to present how the various pieces fit together. We present the actual definitions we use in §2. Then, in §3 and §4, we demonstrate the feasibility of our approach on some examples. We analyse some benefits of using a deepembedding in §5. Finally, we compare our study to other related work in §6.

Overview of our system

We give a global overview of the basic concepts of our methodology first, before giving a formal Coq definition to these notions in the next section. We take this opportunity to illustrate the use of our system to represent parametrized systems through the example of a simple n-bit adder: it computes an n-bit sum and a 1-bit carry out from two n-bit inputs and a 1-bit carry in. The recursive construction scheme of this adder is presented in Fig. 1 (data flows from left to right), using a full-adder, i.e., a 1-bit adder, as basic building block.

Circuit interfaces. Informally, we want to build circuits that relate n input wires to m output wires, where n, m are integers. For instance, the door AND has two inputs and one output. However, using integers to number the wires does not give much structure: the n-bit adder has 2n + 1 input wires, this does not specify how they are grouped. Hence, we use arbitrary finite-types as indexes for the wires rather than using integers [START_REF] Harrison | A HOL theory of Euclidean space[END_REF]. A circuit that relates inputs indexed by n to outputs indexed by m has type C n m, where n and m are types. For instance, the full-adder, a circuit with three inputs and one output, has type

C (1 ⊕ (1 ⊕ 1)) (1 ⊕ 1)
, where ⊕ is the disjoint sum (associative to the left) and 1 is a singleton type. Hence, the n-bit adder has type

C (1 ⊕ sumn 1 n ⊕ sumn 1 n) (sumn 1 n ⊕ 1)
, where sumn A n is a n-ary disjoint sum.

Circuits combinators. The n-bit adder is made of several sub-components that are composed together. We use circuit combinators (or combining forms [START_REF] Sheeran | µFP, A Language for VLSI Design[END_REF]) to specify the connection layout of circuits. For instance, in Fig. 1, the dashedbox is built by composing in parallel two HL circuits, that are then composed serially with a combinator that reorders the wires. These combinators leave implicit the connection points in the circuits, and focus on how informations flow through the circuit: the wire names given in Fig. 1 do not correspond to variables, and are provided for the sake of readability.

In our "nameless" setting, wires have to be forked and reordered using plugs: a plug is a circuit of type C n m, defined using a map from m to n that defines how to connect an output wire (indexed by m) to an input wire (indexed by n). Since we use functions rather than relations, this definition naturally forbids short-circuits (two input wires connected to the same output wire).

Meaning of a circuit. We now depart from the syntactic definitions of circuits to give an overview of their semantics. We assume a type T of what is carried by the wires, for instance booleans (B) or streams of booleans (nat → B). Let x be a circuit of type C n m. The inputs (resp. outputs) of x are a finite function ins of type n → T (resp. outs of type m → T). The meaning of x is a relation x ⊢ n m ins ⊲⊳ outs between ins and outs that we define by induction on x.

This is an abstract mathematical characterization, which may or may not be computational (we will come back to this point later).

Abstracting from the implementation. The meaning of a circuit is defined by induction on its structure: this relation may be complex and may give informations about the internal implementation of a circuit. Thus, we want to move from the definition of this relation, for instance, to give high-level specifications, or to abstract their behavior. These abstractions can be expressed through the following kind of entailment [START_REF] Melham | Higher Order Logic and Hardware Verification[END_REF]:

∀ins, ∀outs, RIPPLE n ⊢ ins ⊲⊳ outs → R outs ins
We use data-abstraction [START_REF] Melham | Higher Order Logic and Hardware Verification[END_REF] to be more elegant. Indeed, a value of type

1 ⊕ sumn 1 n ⊕ sumn 1 n → B is isomorphic to a value of type B × W n × W n
(where W n is the type of integers from 0 to 2 n ). We use type-isomorphisms to give tractable specifications for circuits: we prove that the parametric n-bit adder depicted in fig 1 implements the addition with carry function on W n .

Formal development

We now turn to define formally the concepts that were overviewed in the previous section. We use Coq type-classes to structure our development and parametrize code.

Circuit interfaces

We use arbitrary finite types (types with finitely many elements) as interfaces for the circuits, i.e., as indexes for the wires. One can create such finite types by using the disjoint-sum operator ⊕ and the one-element type 1. This construction can be generalized to n-ary disjoint sums written sumn A n, for a given A. However, using a single singleton type for all wires can be confusing: there is no way to distinguish one 1 from another, except by its position in the type (which is frustrating). Hence, we use an infinite family of singleton types 1 x where x is a tag. Circuits are parametrised by some tags, which allows the Coq type-system to rule out some ill-formed combinations. This tagging discipline allows to easily follow circuit diagrams to define circuits in Coq, without much room for mistakes.

Inductive tag (t : string) : Type := _tag : tag t. (** we write 1t for tag t*) Finite types are defined as a class Fin A that packages a duplicate-free list of all the elements of the type A, defined along the lines of [START_REF] Gonthier | An introduction to small scale reflection in Coq[END_REF].

Type isomorphisms

We use type-isomorphisms as "lenses" to express the specification of circuits in user-friendly types, without loss of information. In a nutshell, we define in Coq an isomorphism between two types A and B as a pair of functions iso : A → B and uniso : A → B that are proved to be inverse of each other. We use the notation A ∼ = B for an isomorphism between A and B, and we define some notations for operations (or instances)that allow one to build such isomorphisms in Fig. 2. The most important instance state the duality between disjoint-sums in the domain of the finite functions to a cartesian product.

Class Iso (A B : Type) :={ iso : A → B; uniso : B → A}.

Class Iso_Props {A B: Type} (I : Iso A B):= { iso_uniso : ∀ (x : B), iso (uniso x) = x; uniso_iso : ∀ (x : A), uniso (iso x) = x}.

Plugs

Rewiring circuits of type C n m are defined by mapping output wires indexed by m to input wires indexed by n. We define plugs using usual Coq functions to get small and computational definition of maps. (Note that, since we map the indexes of the wires, there is no way to embed an arbitrary function inside our circuits to compute, e.g., the addition of the value carried by two input wires.)

We give three examples: (a) is a circuit that forgets its first input (types must be read bottom-up on diagrams); (b) is a circuit that duplicates its inputs; (c) implements some re-ordering and duplication of the wires. (We leave implicit the associativity of wires on the diagrams.)

(a) (b) (c) C (n ⊕ m) m C n (n ⊕ n) C (n ⊕ m ⊕ p) (p ⊕ (n ⊕ n))
A possible implementation for (a) is fun x ⇒ inr x and (b) can be implemented as fun x ⇒ match x with inl e ⇒ e | inr e ⇒ e end. If the type of the circuit gives enough informations, like the examples above, it is possible to define such plugs using proof-search. Indeed, plugs that deal with the associativity of the wires, or even re-orderings, are completely defined by their type, and we use tactics to write the map between wires (it amounts to some case splitting and little automation). Hence, in the formal definition of circuits, we omit the plugs that deal with associativity or re-orderings of the wires, not only for the sake of readability, but also because we do so in the actual Coq code: we leave holes in the code (thanks to the Coq Program feature) that will be filled automatically.

• • • A → T ∼ = σ B → T ∼ = τ A ⊕ B → T ∼ = (σ × τ ) ιx 1x → T ∼ = T A → T ∼ = σ sumn A n → T ∼ = vector σ n
m → n), C n m | Ser : ∀ {n m p : Type}, C n m → C m p → C n p | Par : ∀ {n m p q : Type}, C n p → C m q → C (n ⊕ m) (p ⊕ q) | Loop : ∀ {n m p : Type}, C (n ⊕ p) (m ⊕ p) → C n m.
Fig. 3: Syntax

Abstract syntax

In the following, we use some basic gates from which all other circuits are defined. Hence, we parametrize the definition of circuits by the type of the gates:

Class Techno := techno : Type → Type → Type.

The Fig. 3 presents the dependent type that models circuits, as defined in Coq. This abstract syntax is strongly typed: it ensures that circuits built using the provided combinators are well-formed: dimensions have to agree, and it is not possible to connect circuits in the wrong direction. (Note that this is not anecdotal: if we were to describe circuits with ports and wires, ensuring these properties would require some boilerplate.) We denote serial composition (Ser) with the infix ⊲ symbol, and parallel composition (Par) with &. (Note that these definitions do not deal with what transit in the wires.)

Structural specifications

Let T be the type of what is carried in the wires. We now define the meaning relation for circuits. For a given circuit of type C n m, we build a relation between two functions of type n → T and m → T. We define several operations on such functions, in order to express the meaning relation in a legible manner: We define the semantics of a given set of basic gates tech: Techno by defining instances of the following type-class, (typically, one instance for the boolean setting, and one instance in the stream of boolean setting):

Class Technology_spec (tech : Techno) T:= spec : ∀ {a b: Type}, tech a b → (a → T) → (b → T) → Prop.
The meaning relation for circuits is generated by this parameter and rules for each combinator. These rules are presented on Fig. 4 using inference rules rather than the corresponding Coq inductive, for the sake of readability.

Abstractions

The meaning relation defines precisely the behavior of a circuit, but cannot be used as it is. First, it may be too precise, e.g., with some internal details leaking, or imposing constraints between the inputs and the outputs of a circuit that are not relevant from an external point of view. Second, it defines a constraint between the inputs and outputs of a circuit as a relation between two functions n → T and m → T, which is not user-friendly. In his book [START_REF] Melham | Higher Order Logic and Hardware Verification[END_REF], Melham defines two kinds of abstractions that are relevant here: behavioral abstraction (expressed through the logical entailment of a weak specification R by the meaning relation) and data-abstraction (when the specification is expressed in terms of higher-level types than the above function types).

We combine these two notions to specify that a given circuit realises a specification R up-to two type isomorphisms, and to get more concise specifications, we also define the fact that a circuit implements a function f up-to isomorphisms:

Context {n m N M : Type} (Rn : (n→ T) ∼ = N) (Rm : (m→ T) ∼ = M). Class Realise (c : C n m) (R : N → M → Prop) := realise: ∀ ins outs, c ⊢ n m ins ⊲⊳ outs → R (iso ins) (iso outs). Class Implement (c : C n m) (f : N → M) := implement: ∀ ins outs, c ⊢ n m ins ⊲⊳ outs → iso outs = f (iso ins).

Atoms and modular proofs

We develop circuits in a modular way: to build a complex circuit, we define a functor that takes as argument a module that packages the implementations of the sub-components, and the proofs that they meet some specification. This means that our proofs are hierarchical: we do not inspect the definition of the sub-components when we prove a circuit. These functors can then be applied to a module that contains a set of basic doors (of type 3 Proving some combinatorial circuits

In this section, we focus on acyclic combinational circuits, and implements some arithmetic circuits. We assume a set of basic gates (AND, XOR among others, that can all be defined and proved correct starting from NOR only). Wires carry booleans, i.e., the meaning relation is defined on booleans for the basic gates. We first illustrate our proof methodology on a half-adder. Then, we present operations on n-bits integers, that will be used to specify n-bit adders.

Proving a half-adder

A half-adder adds two 1-bit binary numbers together, producing a 1-bit number and a carry out. However, they cannot be chained together since they have no carry in input. We present a diagram of this circuit, along with its formal definition, in Fig. 5. The left-hand side of the following Coq excerpt is the statement we prove: the circuit HADD implements the function hadd on booleans (defined as λ(a,b).(a ⊕ b, a ∧ b), where ⊕ is the boolean exclusive-or, and ∧ is the boolean and) up-to isomorphisms (we use the notations from Fig. 2 for isos). The Coq system ask us to give evidence of the right-hand side.

Instance HADD_Spec : Implement (ιa • ιb) ( * iso on inputs * ) (ιs • ιc) ( * iso on outputs * ) HADD hadd.

I : 1a ⊕ 1b → B, O : 1s ⊕ 1c → B H : HADD ⊢ 1a⊕1b 1s⊕1c ins ⊲⊳ outs ==================== @iso (ιs • ιc) O = hadd (@iso (ιa • ιb) I)
We have developed several tactics that help to prove this kind of goals. First, we automatically invert the derivation of the meaning relation in the hypothesis H, following the structure of the circuit, to get rid of parallel and serial combinators. This leaves the user with one meaning relation hypothesis per sub-component in the circuit (plugs included). Second, we use the type-class Implement as a dictionary of interesting properties. This allows one to make fast-forward reasoning by applying implements in any hypothesis stating a meaning relation for a sub-component. The type-class resolution mechanism will look for an instance of Implement for this sub-component, and transform the "meaning relation" hypothesis into an equation. (Note that at this point, the user may have to interact with the proof-assistant, e.g., to choose other Implement instances than the one that are picked automatically, but in many cases, this step is automatic.) At this point, the goal looks like the left-hand side of the following excerpt: Third, we move to the right-hand side of the excerpt: we massage the goal to make some iso commute with the left, right and app operations, in order to generalize the goal w.r.t. the isos. (Note that the user may be required to interact with Coq if different isos are applied to the same term in different equations.) Finally, the proof context deals only with high-level data-types, and functions operating on these. The user may then prove the "interesting" part of the lemma.

I : 1a ⊕ 1b → B, O : 1s ⊕ 1c → B M : (1a ⊕ 1b) ⊕ (1a ⊕ 1b) → B H0: iso M = (fun x ⇒ (x,

n-bits integers

From now, we use a dependently typed definition of n-bits integers, along the lines of the fixed-size machine integers of [START_REF] Leroy | A formally verified compiler back-end[END_REF]. We omit the actual definitions of functions when they can be infered from the type. In the following, we prove that various (recursive) circuits implement the carry_add function (that adds two n-bit numbers and a carry).

Two specifications of a 1-bit adder

A full-adder adds two 1-bit binary numbers with a carry in, producing a 1-bit number and a carry out, and is built from two half-adders. We present a diagram of this circuit, along with its formal definition in Fig. 6.

From this circuit, we can derive two specifications of interest. First, the meaning of the full-adder can be expressed in terms of a boolean function, that mimics the truth-table of the circuit. Second, we can prove that this circuit actually implements the carry_add function up-to isomorphism. Both these specifications are proved using the aforementioned tactics, only the interesting parts differ.

Instance FADD_1 : Implement (ιcin • (ιa • ιb)) ( * iso on inputs * ) (ιsum • ιcout) ( * iso on outputs * ) FADD (fun (c,(x,y)) ⇒ (x ⊕ (y ⊕ c),(x ∧ y) ∨ c ∧ (x ⊕ y))). Instance FADD_2 : Implement (ιcin • (Φ 1 a • Φ 1 b )) ( * iso on inputs * ) (Φ 1 sum • ιcout) ( * iso on outputs * ) FADD (fun (c,(x,y)) ⇒ carry_add 1 x y c).

Ripple-carry adder

We present in Fig. 7 the formal definition of the ripple-carry adder from Fig. 1 (we omit the rewiring plugs). This definition is based on two new circuits to split wires, and combine them. Indeed, to build a 1 + n-bit adder, the lowest-order wire of each parameter is connected to a full-adder, while the n high-order wires of each parameter are connected to another ripple-carry adder. Conversely, the wires corresponding to the sum must be combined together. We use two plugs to define the HL and the COMBINE circuits. Then, we prove that these functions on wires implements their counterparts on words. These gates are then easily combined two-by-two to build HIGHLOWS and COMBINES that works with two sets of wires at the same time to get more economical designs (i.e., designs with less sub-components).

Lemma HL_Spec x n p: Implement

(Φ n+p x ) (Φ n x • Φ p x ) (HL x n p) (fun x ⇒ (low n p x, high n p x)). Lemma COMBINE_Spec x n p: Implement (Φ n x • Φ p x ) (Φ n+p x ) (COMBINE x n p) (fun x ⇒ (combine n p (fst x) (snd x))).
Finally, we prove by induction on the size of the circuit that it implements the high-level carry_add addition function on words. (Note that this is a high-level specification of the circuit: the carry_add function is not recursive and disclose nothing of the internal implementation of the device.) This boils down to the proof of lemma add_parts. Instance RIPPLE_Spec cin a b cout sum n :

Implement (RIPPLE cin a b cout s n) (ιcin • (Φ n a • Φ n b )) (Φ n sum • ιcout) (fun (c,(x,y)) ⇒ carry_add c x y).
This design is simple (a linear chain of 1-bit adders) and slow (each fulladder must wait for the carry-in bit from the previous full-adders). In the next subsection, we address the case of a more efficient adder, which is incidentally more complicated, and a better benchmark for our methodology.

Divide and conquer adder

A text-book [START_REF] Aho | Foundations of Computer Science[END_REF] solution to improve on the delay of the ripple-carry adder is to use a divide and conquer scheme, and to compute both the sum when there is a carry in, and the sum when there is no carry in. It is then possible to compute at the same time the sum for the high-order bits, and the sum for the low order bits. Hence, we build a circuit that computes four pieces of data: s (resp. t), the n-bit sum of the inputs, assuming that there is no carry in (resp. assuming that there is a carry in); p the carry-propagate bit (resp. g the carry-generate bit), which is true when there is a carry out of the circuit, assuming that there is a carry in (resp. that there is no carry in).

We provide a diagram in Fig. 8 that depicts the base case and the recursive case, but we omit the actual Coq implementation, for the sake of readability. We prove that this circuit implements the following Coq function:

Definition dc n :W2n * W2n → B * B * W2n * W2n := fun (x,y) ⇒ let (s,g) := carry_add 2 n x y false in let (t,p) := carry_add 2 n x y true in (g,p,s,t).
Again, this is a high-level specification w.r.t. the definition of the circuit: it does not disclose how the circuit compute its results (for instance, the dc function is not recursive). In a nutshell, the circuit computes in parallel the 4uple of results for the high-order and low-order part of the inputs. Then, the propagate and generate bits for both parts can be combined by the PG circuit to compute the propagate and generate bits for the entire circuit. In parallel, the FIX circuit is made of two 2 n-1 -bit multiplexers (easily defined with a fixpoint using 1-bit multiplexers), and update the high-order parts of the sum, w.r.t. the propagate and generate carry-bits of the low-order adder. While we have focused our case studies on combinational circuits, our methodology can be applied to sequential circuits, with or without the loops that were allowed in the syntax of circuits in §2.4. In this section, the wires carry streams of booleans (of type nat → B), and we assume a basic gate DFF that implements the pre function (in the particular case of booleans):

Definition pre {A} (d : A): stream A → stream A := fun f t ⇒ match t with | 0 ⇒ d | S p ⇒ f p end.
Instance DFF_Realise_stream {a out}: Implement (DFF a out) (ιa) (ιout) (pre false).

A buffer. A DFF delays one wire by one unit of time; a FIFO buffer generalize this behavior in two dimensions, by chaining layers of DFF one after another. This circuit is simple, but is a good example for the use of high-level combinators. These combinators capture the underlying regularity in some common circuit pattern, for instance replicating a sub-component in a serial or parallel manner. We prove that the COMPOSEN combinator implements a higher-order iteration function, up-to isomorphism: if CELL implements a given function f, then COMPOSEN k implements the iteration of f. Respectively, we prove that the MAP circuit implements the higher-order map function on vectors. Hence, a FIFO buffer in one-line, and we prove that it implements the function below. The proof of this specification relies on the above useful isomorphism between groups of wires that carries streams of booleans, and a stream of vectors of Simulating and checking designs. One key feature of our first-order encoding of circuits in Coq is that it allows to check designs by simulation before attempting to prove them. This verification is done on the same definition than the one which will be proved later, allowing a seamless approach. While simulation cannot be done on circuits parametrized by a size, this remains a valuable help to avoid dead-ends. We define a simulation function sim that works on loopfree circuits, if the user provide a computational interpretation of each basic gate. For instance, it allows to simulate the adders of §3.

Delay and pretty-printing. Using the same ideas, we can build functions that compute the list of gates of circuits (with or without loops), or compute the length of the critical path in combinatorial circuits. While this is more anecdotal, and less directly useful than the previous simulation function, these functions are still interesting: one could, for instance, prove that some complex designs meet some time (or gate-count) complexity properties. (Note that is the only place where we exploit the finiteness of types.)

Comparisons with related works

Verifying circuits with theorem provers. There has been a substantial amount of work on specification and verification of hardware in HOL. In [START_REF] Gordon | Why higher-order logic is a good formalisation for specifying and verifying hardware[END_REF][START_REF] Melham | Higher Order Logic and Hardware Verification[END_REF], HOL is used as a hardware description language and as a formalism to prove that a design meets its specification. They model circuits as predicates in the logic, using a shallow-embedding that merges the architecture of a circuit and its behavior. Building on the former methodology, [START_REF] Slind | Proof producing synthesis of arithmetic and cryptographic hardware[END_REF] defines a compiler from a synthetisable subset of HOL that creates correct-by-construction clocked synchronous hardware implementations of mathematical functions specified in HOL. This methodology allows the designer to focus on high-level abstraction instead of reasoning and verifying at the gate level, admitting the existence of some base low-level circuits (like the addition on words [START_REF] Iyoda | Translating HOL functions to hardware[END_REF]). By contrast, our work complement their behavioral "correct by design" synthesis from a subset of the high-level language of the theorem-prover with structural verification of circuits.

In the Boyer-Moore theorem prover (untyped, quantifier-free and first-order), Brock and Hunt proved the correctness of functions that generate correct hardware designs. They studied the correctness of an arithmetic and logic unit, parametrised by a size [START_REF] Hunt | The Verification of a Bit-slice ALU[END_REF]. This verified synthesis approach was used to verify a microprocessor design [START_REF] Brock | The DUAL-EVAL Hardware Description Language and Its Use in the Formal Specification and Verification of the FM9001 Microprocessor[END_REF]. While our proofs are not as automated, and our examples are less ambitious, we are able to prove higher-order circuits. Moreover, the dependent-types we use are helpful when defining complex circuits.

In Coq, Paulin-Mohring [START_REF] Paulin-Mohring | Circuits as Streams in Coq: Verification of a Sequential Multiplier[END_REF] proved the correction of a multiplier unit, using a shallow-embedding similar to the methodology used in HOL: circuits are modelled as functions of the Coq language. More recently, [START_REF] Coupet-Grimal | Certifying circuits in type theory[END_REF] investigated how to take advantage of dependent types and co-inductive types in hardware verification: they use a shallow embedding of Mealy automata to describe sequential circuits. By contrast with both works, we use a deep-embedding of circuits in Coq, that makes explicit the definition of circuits. We still need to investigate the examples of sequential circuits studied in these papers.

Algebraic definitions of circuits. Circuit diagrams have nice algebraic properties. Lafont [START_REF] Lafont | Towards an algebraic theory of boolean circuits[END_REF] studied the algebraic theory of boolean circuits and Hinze [START_REF] Hinze | An Algebra of Scans[END_REF] studied the algebra of parallel prefix circuits. Both settings are close to ours: however the former focused on the algebraic structure of circuits, while the latter defined combinators that allows to model (and prove correct using algebraic reasoning) all standard designs of a restricted class of circuits.

Functional languages in hardware design. Sheeran [START_REF] Sheeran | Hardware Design and Functional Programming: a Perfect Match[END_REF] made a thorough review of the use of functional languages in hardware design, and of the challenges to address. Our work is a step toward one of them: the design and verification of parametrized designs, through the use of circuit combinators. Lava [START_REF] Bjesse | Lava: Hardware Design in Haskell[END_REF] is a language embedded in Haskell to describe circuits, allowing one to define parametric circuits or higher-order combinators. While much of our goals are common, one key difference is that our encoding of circuits in Coq avoid the use of bound variables (we use only combinators). Moreover, we use dependent types, that are required to deal precisely with parametric circuits. Finally, we prove the correctness of these parametric circuits in Coq, while verification in Lava is reduced to the verification of finite-size circuits.

Conclusion and future works

We have presented a deep-embeding of circuits in the Coq proof-assistant that allows to build and reason about circuits, proving high-level specifications through the use of type-isomorphism. We have demonstrated that dependent types are useful to prove automatically some well-formedness conditions on the circuits, and helps to avoid time consuming mistakes. Then, we proved by induction the correctness of some arithmetic circuits of parametric size: this could not have been possible without mimicking the structure of the usual circuit diagrams to define circuit generators in Coq. The formal development accompanying this paper is available from the authors web-page [START_REF] Braibant | Coquet: a coq library for verifying hardware[END_REF].

In the immediate future, we plan to continue the case studies described in §3. In particular, we would like to investigate how to construct parallel prefix circuits in our framework [START_REF] Hinze | An Algebra of Scans[END_REF][START_REF] Sheeran | Hardware Design and Functional Programming: a Perfect Match[END_REF], and to investigate combinational multipliers. In the more distant future, it would be interesting to study some front-ends to automatically generate some circuits: this could range to the reduction of the boiler-plate inherent to the definition of plugs, to the compilation of circuits from automaton. A major inspiration on behavioral synthesis is the work of Ghica [START_REF] Ghica | Geometry of synthesis: a structured approach to VLSI design[END_REF]. We also look forward to study how our methodology applies to other settings that booleans or streams of booleans. For instance, if we move from booleans to the three-valued Scott's domain (unknown, true, false), we may interpret circuits in the so-called constructive semantics. We also hope that some of our methods could be applied to the probabilistic setting.

Fig. 1 :

 1 Fig. 1: A recursive n-bit ripple-carry adder

Fig. 2 :

 2 Fig. 2: Isomorphisms between types

Context

  {T : Type}. Definition left {n} {m} (x : (n ⊕ m) → T) : n → T := fun e ⇒ (x (inl _ e)). Definition right {n} {m} (x : (n ⊕ m) → T) : m → T := fun e ⇒ (x (inr _ e)). Definition lift {n} {m} (f : m → n) (x : n → T) : m → T := fun e ⇒ x (f e). Definition app {n m} (x : n → T) (y : m → T) : n ⊕ m → T := fun e ⇒ match e with inl e ⇒ x e | inr e ⇒ y e end.

Fig. 4 :

 4 Fig. 4: Meaning of circuits (omitting the rule for Atom)

Fig. 5 :

 5 Fig. 5: Definition of a half-adder

  x)) (iso I) H1: iso (left O) = uncurry ⊕ (iso (left M)) H2: iso (right O)= uncurry ∧ (iso (right M)) ========================== iso O = hadd (iso I) I: B * B, O: B * B, M : (B * B) * (B * B), H0: M = (fun x ⇒ (x,x)) I H1: fst O = uncurry ⊕ (fst M) H2: snd O = uncurry ∧ (snd M) ================== O = hadd I

  Record word (n:nat) := mk_word {val : Z; range: 0 ≤ val < 2 n }. ( * Wn * ) Definition repr n (x : Z) : Wn := ... Definition high n m (x : W (n+m) ) : Wm := ... Definition low n m (x : W (n+m) ) : Wn := ... Definition combine n m (low : Wn) (high : Wm) : W (n+m) := ... Definition carry_add n (x y : Wn) (b : B) : Wn * B := let e := val x + val y + (if b then 1 else 0) in (e mod 2 n ,2 n ≤ e) Definition Φ n x : Iso (sumn 1x n → B) (Wn) := ...

  Context a b cin sum cout : string. Program Definition FADD : C (1cin ⊕ (1a ⊕ 1 b )) (1sum ⊕ 1cout) := (ONE 1cin & HADD a b "s1" "c1") ⊲ ... ( * associativity plug * ) ⊲ (HADD cin "s1" sum "c2" & ONE 1 "c1" ) ⊲ ... ( * associativity plug * ) ⊲ (ONE 1sum & OR "c2" "c1" cout).

Fig. 6 :

 6 Fig. 6: Definition of a full-adder

Fig. 7 :

 7 Fig.7: Implementation of the ripple-carry-adder from Fig.1

Definition

  HL x n p : C (sumn 1x (n + p)) (sumn 1x n ⊕ sumn 1x p):= Plug ... Definition COMBINE x n p : C (sumn 1x n ⊕ sumn 1x p) (sumn 1x (n + p)):= Plug ...

  Lemma add_parts n m (xH yH: word m) (xL yL : word n) cin: let (sumL,middle) := carry_add n xL yL cin in let (sumH,cout) := carry_add m xH yH middle in let sum := combine n m sumL sumH in carry_add (n + m) (combine n m xL xH)(combine n m yL yH) cin = (sum,cout).

Fig. 8 :

 8 Fig. 8: Divide and conquer adder

  Variable CELL : C n n. Fixpoint COMPOSEN k : C n n := match k with | 0 ⇒ Plug id | S p ⇒ CELL ⊲ (COMPOSEN p) end. Variable CELL : C n m. Fixpoint MAP k : C (sumn 1n k) (sumn 1m k):= match k with | 0 ⇒ Plug id | S p ⇒ CELL & (MAP p) end.

  Definition FIFO x n k : C (sumn 1x k) (sumn 1x k) := COMBINEN (MAP (DFF x x) k) n. Definition fifo n k (v : stream (vector B k)) : stream (vector B k) := fun t ⇒ if n < t then v (tn) elseVector.repeat k false. Remark useful_iso : sumn 1 n → stream B ∼ = stream (vector B n) := ...

  Techno) and its meaning relation (of type Technology_spec).

			KSer	x ⊢ n m ins ⊲⊳ middle x ⊲ y ⊢ n p ins ⊲⊳ outs y ⊢ m p middle ⊲⊳ outs
	KPar	x ⊢ n p left ins ⊲⊳ left outs x&y ⊢ n⊕m p⊕q ins ⊲⊳ outs y ⊢ m q right ins ⊲⊳ right outs
	KPlug	Plug f ⊢ n m ins ⊲⊳ lift f ins	KLoop	x ⊢ n⊕p m⊕p app ins r ⊲⊳ app outs r Loop x ⊢ n m ins ⊲⊳ outs

Context a load out : string. Program Definition REGISTER: C (1load ⊕ 1a) 1out := @Loop (1load ⊕ 1a) 1out 1out (... ⊲ MUX2 a out load "in_dff" ⊲ DFF "in_dff" out ⊲ Fork2 1out). A memory element. Our next goal is to demonstrate how we deal with stateholding structures. Hence, we turn to the implementation of a 1-bit memory element, as implemented in Fig. 9. The register is meant to hold 1-bit of information through time, which does not fit nicely in the Implement framework (we cannot easily express the meaning of the register in terms of a stream transformer). Hence, we use a relational specification through the use of Realise:

outs = pre false (fun t ⇒ if fst (ins t) then snd (ins t) else outs t)).

Here, the state of the register is stored inside the history of the stream (the previous values that were taken by the output). While we do not advocate that this is the nicest way to reason about state holding devices, we were able to prove this specification in the same fashion as the previous combinatorial devices. We leave more thorough investigation of state-holding devices to future work.

Interesting corollaries

We now turn on to investigate some interesting consequences of the use of a concrete data-type to represent circuit. First, we prove that the behavior of combinatorial circuits without delay can be lifted to the stream setting. Second, we build some functions (or interpretations [START_REF] Bjesse | Lava: Hardware Design in Haskell[END_REF]) that operates on circuits.

Lifting combinatorial circuits. The meaning relation is parametrized by the semantics of the basic gates. This can be put to good use to prove the functional correction of some designs in the boolean setting, and then, to mechanically lift this proof of functional correction to the boolean stream setting (for the same set of gates). For instance, if a loop-less and delay-less circuit implements a function f in the boolean setting, we can prove that the very same circuit implements the function Stream.map f in the boolean stream setting.


Anna-Lena Trautmann

Joachim Rosenthal

A Complete Characterization of Irreducible Cyclic Orbit Codes ⋆

Constant dimension codes are subsets of the finite Grassmann variety. The study of constant dimension codes with good distances have been central in random linear network coding theory. Orbit codes represent a subclass of constant dimension codes. They are characterized that the elements of the code can be viewed as the orbit under a group action. The paper gives a complete characterization of orbit codes that are generated by an irreducible cyclic group, i.e. an irreducible group having one generator. We show how some of the basic properties of these codes, the cardinality and the minimum distance, can be derived using the isomorphism of the vector space and the extension field.

Introduction

In network coding one is looking at the transmission of information through a directed graph with possibly several senders and several receivers [START_REF] Ahlswede | Network information flow[END_REF]. One can increase the throughput by linearly combining the information vectors at intermediate nodes of the network. If the underlying topology of the network is unknown we speak about random linear network coding. Since linear spaces are invariant under linear combinations, they are what is needed as codewords [START_REF] Kötter | Coding for errors and erasures in random network coding. Information Theory[END_REF]. It is helpful (e.g. for decoding) to constrain oneself to subspaces of a fixed dimension, in which case we talk about constant dimension codes.

The set of all k-dimensional subspaces of a vector space V is often referred to as the Grassmann variety (or simply Grassmannian) and denoted by G(k, V ). Constant dimension codes are subsets of G(k, F n q ), where F q is some finite field. The general linear group GL(V ) consisting of all invertible transformations acts naturally on the Grassmannian G(k, V ). If G ≤ GL(F n q ) = GL n is a subgroup then one has an induced action of G on the finite Grassmannian G(k, F n q ). Orbits under the G-action are called orbit codes [START_REF] Trautmann | Orbit codes -a new concept in the area of network coding[END_REF]. The set of orbit codes comes with nice algebraic properties. E.g. for the computation of the distance of an orbit code it is enough to compute the distance between the base point and any of its orbit elements. This is in analogy to linear block codes where the distance can also be computed from the weights of the non-zero code words.

Orbit codes can be classified according to the groups used to construct the orbit. In this work we characterize orbit codes generated by irreducible cyclic subgroups of the general linear group.

The paper is structured as follows: The second section gives some preliminaries, first of random network coding and orbit codes. Then some facts on irreducible polynomials are stated and the representation of finite vector spaces as Galois extension fields is explained in 2.2. In part 2.3 we introduce irreducible matrix groups and give some properties, with a focus on the cyclic ones. The main body of the paper is Section 3, where we study the behavior of orbit codes ⋆ Research partially supported by Swiss National Science Foundation Project no. 126948 generated by these groups and compute the cardinality and minimum distances of them. We begin by characterizing primitive orbit codes and then study the non-primitive irreducible ones. Finally we give a conclusion and an outlook in Section 4.

Preliminaries

Random Network Codes

Let F q be the finite field with q elements (where q = p r and p prime). For simplicity we will denote the Grassmannian G(k, F n q ) by G(k, n). The general linear group of dimension n, GL n , is the set of all invertible n × n-matrices with entries in F q . Moreover, the set of all k × n-matrices over F q is denoted by M at k×n .

Let U ∈ M at k×n be a matrix of rank k and

U = rs(U ) := row space(U ) ∈ G(k, n).
One can notice that the row space is invariant under GL k -multiplication from the left, i.e. for any T ∈ GL k U = rs(U ) = rs(T U ).

Thus, there are several matrices that represent a given subspace. A unique representative of these matrices is the one in reduced row echelon form. Any k × n-matrix can be transformed into reduced row echelon form by a T ∈ GL k . The subspace distance is a metric on G(k, n) given by

d S (U, V) =2(k -dim(U ∩ V)) =2 • rank U V -2k
for any U, V ∈ G(k, n) and some respective matrix representations U and V . It is a suitable distance for coding over the erasure channel [START_REF] Kötter | Coding for errors and erasures in random network coding. Information Theory[END_REF][START_REF] Silva | A rank-metric approach to error control in random network coding[END_REF]. A constant dimension code C is simply a subset of the Grassmannian G(k, n). The minimum distance is defined in the usual way.

A code C ⊂ G(k, n) with minimum distance d S (C) is called an [n, d S (C), |C|, k]-code.
In the case that k divides n one can construct spread codes [START_REF] Manganiello | Spread codes and spread decoding in network coding[END_REF], i.e. optimal codes with minimum distance 2k. These codes are optimal because they reach the Singleton-like bound, which means they have q n -1 q k -1 elements. Given U ∈ M at k×n of rank k, U ∈ G(k, n) its row space and A ∈ GL n , we define

UA := rs(U A).
Let U, V ∈ M at k×n be matrices such that rs(U ) = rs(V ). Then one readily verifies that rs(U A) = rs(V A) for any A ∈ GL n .

This multiplication with matrices from GL n actually defines a group operation from the right on the Grassmannian:

G(k, n) × GL n -→ G(k, n) (U, A) -→ UA Let U ∈ G(k, n) be fixed and G a subgroup of GL n . Then C = {UA | A ∈ G} is called an orbit code [10]. Since G(k, n) ∼ = GL n /Stab(U),
where Stab(U) := {A ∈ GL n |UA = U}, it is possible that different subgroups generate the same orbit code. An orbit code is called cyclic if it can be defined by a cyclic subgroup G ≤ GL n .

Irreducible Polynomials and Extension Fields

Let us state some known facts on irreducible polynomials over finite fields (cf. [START_REF] Lidl | Introduction to Finite Fields and their Applications[END_REF] Lemmas 3.4 -3.6):

Lemma 1 Let p(x) be an irreducible polynomial over F q of degree n, p(0) = 0 and α a root of it.

Define the order of a polynomial p(x) ∈ F q [x] with p(0) = 0 as the smallest integer e for which p(x) divides x e -1. Then 1. the order of p(x) is equal to the order of α in F q n \{0}.

2. the order of p(x) divides q n -1.

3. p(x) divides x c -1 iff the order of p(x) divides c (where c ∈ N).

There is an isomorphism between the vector space F n q and the Galois extension field F q n ∼ = F q [α], for α a root of an irreducible polynomial p(x) of degree n over F q . If in addition p(x) is primitive, then

F q [α]\{0} = α = {α i |i = 0, ..., q n -2}
i.e. α generates multiplicatively the group of invertible elements of the extension field.

Lemma 2 If k|n, c := q n -1 q k -1 and α a primitive element of F q n , then the vector space generated by 1, α c , ..., α (k-1)c is equal to

{α ic |i = 0, ..., q k -2} ∪ {0} = F q k .
Proof. Since k|n it holds that c ∈ N. Moreover, it holds that (α c ) q k -1 = α q n -1 = 1 and (α c ) q k -2 = α -c = 1, hence the order of α c is q k -1. It is well-known that if k divides n the field F q n has exactly one subfield F q k . Thus the group generated by α c has to be F q k \{0}, which again is isomorphic to F k q as a vector space. ⊓ ⊔

Irreducible Matrix Groups

Definition 3 1. A matrix A ∈ GL n is called irreducible if F n q contains no non-trivial A- invariant subspace, otherwise it is called reducible. 2. A subgroup G ⊆ GL n is called irreducible if F n q contains no G-invariant subspace, otherwise it is called reducible. 3. An orbit code C ⊆ G(k, n) is called irreducible if C can
be viewed as the orbit under the group action of an irreducible group.

A cyclic group is irreducible if and only if its generator matrix is irreducible. Moreover, an invertible matrix is irreducible if and only if its characteristic polynomial is irreducible.

Example 4 Over F 2 the only irreducible polynomial of degree 2 is p(x) = x 2 + x + 1. The irreducible matrices in GL 2 must have trace and determinant equal to 1 and hence are 0 1 1 1 and 1 1 1 0 .

We can say even more about irreducible matrices with the same characteristic polynomial. For this, note that the definition of an irreducible matrix G implies the existence of a so called cyclic vector v ∈ F n q having the property that {v, vG, vG 2 , . . . , vG n-1 } forms a basis of F n q . Let S ∈ GL n be the basis transformation which transforms the matrix G into this new basis. Then it follows that

SGS -1 =        0 1 0 . . . 0 0 0 1 . . . 0 . . . . . . . . . . . . . . . 0 0 0 . . . 1 -c 0 -c 1 . . . -c n-1       
.

The matrix appearing on the right is said to be in companion form. By convention we will use row vectors and accordingly companion matrices where the coefficients of the corresponding polynomials are in the last row (instead of the last column). One readily verifies that

p(x) := x n + c n-1 x n-1 + • • • + c 1 x + c 0
is the characteristic polynomial of both G and SGS -1 . It follows that every irreducible matrix in GL n is similar to the companion matrix of its characteristic polynomial. Hence all irreducible matrices with the same characteristic polynomial are similar. Furthermore, we can say something about the order of a matrix when viewed as an element of the finite group GL n . For this assume that G ∈ GL n is an invertible matrix having p(x) as characteristic polynomial. Then one readily verifies that the order of G is equal to the order of p(x). Hence G is a primitive element of GL n if and only if its characteristic polynomial is primitive.

The next fact is a well-known group theoretic result:

Lemma 5 (cf. [START_REF] Lidl | Introduction to Finite Fields and their Applications[END_REF] Theorem 1.15.) In a finite cyclic group G = G of order m, the element G l generates a subgroup of order m gcd(l,m) . Hence each element G l with gcd(l, m) = 1 is a generator of G.

Lemma 6 (cf. [START_REF] Manganiello | On conjugacy classes of subgroups of the general linear group and cyclic orbit codes[END_REF] Theorem 7) All irreducible cyclic groups generated by matrices with a characteristic polynomial of the same order are conjugate to each other.

Example 7 Over F 2 the irreducible polynomials of degree 4 are p 1 (x) = x 4 + x + 1, p 2 (x) = x 4 + x 3 + 1 and p 3 (x) = x 4 + x 3 + x 2 + x + 1, where ord(p 1 ) = ord(p 2 ) = 15 and ord(p 3 ) = 5. Let P 1 , P 2 , P 3 be the respective companion matrices: One verifies that P 1 and P 2 are conjugate to each other but P 3 is not conjugate to them.

One can describe the action of an irreducible matrix group via the Galois extension field isomorphism.

Theorem 8 Let p(x) be an irreducible polynomial over F q of degree n and P its companion matrix. Furthermore let α ∈ F q n be a root of p(x) and φ be the canonical homomorphism

φ : F n q -→ F q n (v 1 , . . . , v n ) -→ n i=1 v i α i-1 .
Then the following diagram commutes (for v ∈ F n q ):

v P -→ vP φ ↓ ↓ φ v ′ -→ α v ′ α
If P is a companion matrix of a primitive polynomial the group generated by P is also known as a Singer group. This notation is used e.g. by Kohnert et al. in their network code construction (see [START_REF] Elsenhans | Construction of codes for network coding[END_REF], [START_REF] Kohnert | Construction of large constant dimension codes with a prescribed minimum distance[END_REF]). Elsewhere P is called Singer cycle or cyclic projectivity (e.g. in [START_REF] Hirschfeld | Projective Geometries over Finite Fields[END_REF]).

Irreducible Cyclic Orbit Codes

The irreducible cyclic subgroups of GL n are exactly the groups generated by the companion matrices of the irreducible polynomials of degree n and their conjugates. Moreover, all groups generated by companion matrices of irreducible polynomials of the same order are conjugate.

It is sufficient to characterize the orbits of cyclic groups generated by companion matrices of irreducible polynomials of degree n. The following theorem shows that the results are then carried over to any irreducible cyclic orbit code via the choice of a starting point of the orbit. Proof. Trivially the cardinality of both codes is the same. It remains to be shown that the same holds for the minimum distance.

The following diagram commutes:

U G -→ UG S ↓ ↓ S V -→ S -1 GS

UGS

Since the subspace distance is invariant under GL n -action and (S -1 GS)

i = S -1 G i S it holds that d S (U, UG i ) = d S (V, UG i S)
hence the minimum distances of the codes defined by G and by H are equal. ⊓ ⊔

Primitive Generator

Let α be a primitive element of F q n and assume k|n and c := q n -1 q k -1 . Consider once more the F q -subspace F q k = {α ic |i = 0, ..., q k -2} ∪ {0}.

Lemma 10 For every β ∈ F q n the set

β • F q k = {βα ic |i = 0, ..., q k -2} ∪ {0}
defines an F q -subspace of dimension k.

The following fact has been formulated by Kohnert and Kurz in [START_REF] Kohnert | Construction of large constant dimension codes with a prescribed minimum distance[END_REF]: Lemma 14 Over the binary field let p(x) be a primitive polynomial and α a root of it. Assume k > 1 and U

= {0, u 1 , . . . , u 2 k -1 } ∈ G(k, n) such that φ(u i ) = α bi ∀i = 1, . . . , 2 k -1 and the set {b m -b l mod 2 n -1|l, m ∈ Z 2 k -1 , l = m}
has no multiple elements, i.e. all quotients in the field representation are pairwise different.

Then the orbit of the group generated by the companion matrix P of p(x) on U is an orbit code of cardinality 2 n -1 and minimum distance 2k -2.

Proof. In field representation the elements of the orbit code are:

C 0 ={α b1 , α b2 , . . . , α b 2 k -1 } C 1 ={α b1+1 , α b2+1 , . . . , α b 2 k -1 +1 } . . . C q n -2 ={α b1+q n -2 , . . . , α b 2 k -1 +q n -2 }
We show that the intersection between any two code words is at most one element. Therefore, assume w.l.o.g. that the first element of C h is equal to the second element of C j : By condition the only solution for this equation is y = 1, z = 2. Thus there is no second element in the intersection.

α b1+h = α b2+j ⇐⇒ h ≡ b 2 -b 1 + j mod 2 n
On the other hand one can always find h = j such that there is a solution to b y + h ≡ b z + j mod 2 n -1, hence, the minimum distance is exactly 2k -2.

⊓ ⊔

As can be found in [START_REF] Elsenhans | Construction of codes for network coding[END_REF], a subspace fulfilling the condition of Lemma 14 exists for any k, n. Moreover, it is shown how to combine different orbits to a network code of minimum distance 2k -2 and how one-error-correcting decoding can be done.

The result and proof from above can be carried over to arbitrary finite fields and any starting point U ∈ G(k, n) in the following way:

Theorem 15 Over F q let p(x) be a primitive polynomial and α a root of it. Assume U = {0, u 1 , . . . , u q k -1 } ∈ G(k, n), φ(u i ) = α bi ∀i = 1, . . . , q k -1

Theorem 9

 9 Let G be an irreducible matrix, G = G and H = S -1 GS for an S ∈ GL n . Moreover, let U ∈ G(k, n) and V := US. Then the orbit codes C := {UA|A ∈ G} and C ′ := {VB|B ∈ H} have the same cardinality and minimum distance.

- 1 To

 1 have another element in common it has to hold b y + h ≡ b z + j mod 2 n -1for some y = 1 (or z = 2). Insert h from above:b y + b 2 -b 1 + j ≡ b z + j ⇐⇒ b 2 -b 1 ≡ b z -b y mod 2 n -1

Proof.

ϕ β : F q n -→ F q n u -→ βu is an F q -linear isomorphism, ϕ β (F q k ) = β • F q k is hence an F q -linear subspace of dimension k. ⊓ ⊔ Theorem 11 The set S = α i • F q k | i = 0, . . . , c -1 defines a spread code.

Proof. By a simple counting argument it is enough to show that the subspace α i • F q k and α j • F q k have only trivial intersection whenever 0 ≤ i < j ≤ c -1. For this assume that there are field elements c i , c j ∈ F q k , such that

But this means i -j ≡ 0 mod c and α i • F q k = α j • F q k . It follows that S is a spread.

⊓ ⊔

We now translate this result into a matrix setting. For this let φ denote the canonical homomorphism as defined in Theorem 8.

Corollary 12 Assume k|n. Then there is a subspace U ∈ G(k, n) such that the cyclic orbit code obtained by the group action of a a primitive companion matrix is a code with minimum distance 2k and cardinality q n -1 q k -1 . Hence this irreducible cyclic orbit code is a spread code. Proof. In the previous theorem represent F q k ⊂ F q n as the rowspace of a k × n matrix over F q and using the same basis over F q represent the primitive α with a primitive companion matrix P . The orbit code defined in this way has then all the desired properties.

⊓ ⊔

Example 13 Over the binary field let p(x) := x 6 + x + 1 be primitive, α a root of p(x) and P its companion matrix.

1. For the 3-dimensional spread compute c = 63 7 = 9 and construct a basis for the starting point of the orbit:

The starting point is

and the orbit of the group generated by P on U is a spread code. 2. For the 2-dimensional spread compute c = 63 3 = 21 and construct the starting point

The starting point is U = rs 1 0 0 0 0 0 1 1 1 0 0 0 = rs 1 0 0 0 0 0 0 1 1 0 0 0 and the orbit of the group generated by P is a spread code.

and d < k be minimal such that any element of the set

has multiplicity less than q d -1, i.e. a quotient of two elements in the field representation appears at most q d -1 times in the set of all pairwise quotients. Then the orbit of the group generated by the companion matrix P of p(x) on U is an orbit code of cardinality q n -1 and minimum distance 2k -2d.

Proof. In analogy to the proof of Lemma 14, to have another element in common it has to hold

By condition there are up to q d -1 solutions in (y, z) for this equation, including y = 1, z = 2. Thus the intersection of C i and C j has at most q d -1 elements. On the other hand, since d is minimal, one can always find h = j such that there are q d -1 solutions to

e. all quotients are the same, one gets elements with full intersection which means they are the same element. This can only happen if k|n (since k|n if and only if q k -1|q n -1). In this case one can construct spread codes as explained in Corollary 12.

Non-Primitive Generator

Theorem 16 Let P be an irreducible non-primitive companion matrix, G the group generated by it and denote by vG and UG the orbits of

then UG on is an orbit code with minimum distance 2k and cardinality ord(P ).

Proof. The cardinality follows from the fact that each element of U hast its own orbit of length ord(P ). Moreover, no code words intersect non-trivially, hence the minimum distance is 2k. ⊓ ⊔ Note that, if the order of P is equal to q n -1 q k -1 , these codes are again spread codes.

Example 17 Over the binary field let p(x) = x 4 + x 3 + x 2 + x + 1, α a root of p(x) and P its companion matrix. Then F 2 4 \{0} is partitioned into

Choose

such that each u i is in a different orbit of P and U = {0, u 1 , u 2 , u 3 } is a vector space. Then the orbit of P on U has minimum distance 4 and cardinality 5, hence it is a spread code.

Proposition 18 Let P and G be as before and U = {0, v 1 , . . . , v q k -1 } ∈ G(k, n). Let O 1 , ..., O l be the different orbits of G in F n q . Assume that m < q k -1 elements of U are in the same orbit, say O 1 , and all other elements are in different orbits each, i.e.

Apply the theory of Section 3.1 to the orbit O 1 and find d 1 fulfilling the conditions of Theorem 15. Then the orbit of G on U is a code of length ord(P ) and minimum distance 2k -2d 1 .

Proof. 1. Since there is at least one orbit O i that contains exactly one element of U, each element of O i is in exactly one code word. Hence the cardinality of the code is ord(G) = ord(P ). 2. In analogy to Theorem 16 the only possible intersection is inside O 1 , which can be found according to the theory of cyclic primitive groups.

⊓ ⊔

We generalize these results to any possible starting point ∈ G(k, n):

Theorem 19 Let P, G, U and the orbits O 1 , ..., O l be as before. Assume that m i elements of U are in the same orbit O i (i = 1, . . . , l). Apply the theory of Section 3.1 to each orbit O i and find the corresponding d i from Theorem 15. Then the following cases can occur:

1. No intersections of two different orbits coincide. Define d max := max i d i . Then the orbit of G on U is a code of length ord(P ) and minimum distance 2k -2d max . 2. Some intersections coincide among some orbits. Then the corresponding d i 's add up and the maximum of these is the maximal intersection number d max .

Mathematically formulated: Assume b (j,1) , . . . , b (j,ord(P )-1) are the exponents of the field representation of elements of U on O j . Define

and denote by m µ,λ (a) the multiplicity of an element a in the (multi-)set {a (i,µ,λ) | i = 1, . . . , l} for given µ and λ. Moreover, let δ (µ,λ) := max{a (i,µ,λ) • m µ,λ (a (i,µ,λ) ) | i = 1, . . . , l},

Then the orbit of G on U is a code of length ord(P ) and minimum distance 2k -2d max .

Note that in the case that the minimum distance of the code is 0 one has double elements in the orbit. Then one has to consider the set of different code words and compute the cardinality and minimum distance again.

Conclusion

We listed all possible irreducible cyclic orbit codes and showed that it suffices to investigate the groups generated by companion matrices of irreducible polynomials. Moreover, polynomials of the same degree and same order generate codes with the same cardinality and minimum distance. These two properties of the code depend strongly on the choice of the starting point in the Grassmannian. We showed how one can deduce the size and distance of an orbit code for a given subgroup of GL n from the starting point U ∈ G(k, n). For primitive groups this is quite straight-forward while the non-primitive case is more difficult.

Subsequently one can use this theory of irreducible cyclic orbit codes to characterize all cyclic orbit codes.