Aslı Çakır

Hatice Akkoç

Socio-mathematical norms related to explanations: A case of a gifted and talented mathematics classroom

Keywords: Socio-mathematical norms, gifted students, mathematical explanations, classroom microculture, mathematical creativity

This study explores socio-mathematical norms (SMNs) related to explanations in a gifted and talented students' classroom as a response to calls for investigating their classroom micro-culture. Data consist of forty-three mathematics lessons. We defined two dimensions (teacher and student) of SMNs which were reported in the literature and analysed the data based on these dimensions. Findings revealed one SMN regarding acceptable mathematical explanations and justifications that has the potential to support creative mathematical activity through elaboration. However, the classroom community lacked explicit evaluations of ideas based on other creativity components such as fluency, flexibility, and originality. This study recommends some practical and theoretical implications for creating a classroom environment for gifted students.

Introduction

There has been an agreement in the mathematics education community that knowing and doing mathematics is a social and cultural activity [START_REF] Cobb | Mathematizing and symbolizing: The emergence of chains of signification in one first-grade classroom[END_REF][START_REF] Yackel | Sociomathematical norms, argumentation, and autonomy in mathematics[END_REF]. In line with this perspective, this study sees teaching as establishing and maintaining a classroom culture for doing mathematics, and the role of the teacher is "to support students' enculturation into the ways of speaking, working and thinking that are specific for mathematics" (Nowińska, 2022, p. 3450). Each classroom is considered a community in which different learning practices are adopted by teachers and students [START_REF] Goos | Learning mathematics in a classroom community of inquiry[END_REF]. In this context, socio-mathematical norms (SMNs) describe "normative aspects of mathematical discussions that are specific to students' mathematical activity" (Yackel & Cobb, 1996, p. 458). SMNs are concerned with what counts as mathematically different, efficient, or elegant, and what counts as an acceptable mathematical solution or justification [START_REF] Yackel | Creating a mathematics classroom environment that fosters the development of mathematical argumentation[END_REF]. Since norms are tied to the community in which they emerge because of their nature and can change according to the classroom [START_REF] Yackel | Creating a mathematics classroom environment that fosters the development of mathematical argumentation[END_REF], gifted students' classroom norms may differ from others. To deepen the mathematical understanding of gifted students, it is recommended to justify the reasoning behind the thoughts or solutions [START_REF] Singer | Research on and activities for mathematically gifted students[END_REF]. Therefore, teachers should initiate the negotiation process about mathematical explanations and justifications in the classrooms of gifted students and should provide the development of normative understandings in terms of conceptual explanations and mathematical creativity.

Mathematical creativity, which is associated with giftedness has been examined by researchers through the evaluation of products based on how novel (originality) or how flexible they are (flexibility), whether they contain in-depth explanations (elaboration), or the number of solutions made (fluency) [START_REF] Mann | The prominence of affect in creativity: Expanding the conception of creativity in mathematical problem solving[END_REF]. For thoughts or solutions to be evaluated in terms of originality and flexibility in the classroom community, it is necessary to understand how they differ from each other. Then, the classroom community can reach a mutual understanding of these issues.

This study examines SMNs related to explanations and justifications in a classroom of gifted students. The research aims to contribute to our understanding of norms that could be established in gifted students' classroom micro-culture, and norms that could support creativity [START_REF] Goldin | Mathematical creativity and giftedness: Perspectives in response[END_REF].

Socio-mathematical norms related to explanations and justifications

According to the interpretive framework, the social dimensions of the classroom micro-culture and the psychological dimensions of students' individual activities in the classroom are in a reflexive relationship [START_REF] Cobb | Participating in classroom mathematical practices[END_REF]. As the teacher and students interpret and respond to each other's actions (psychological perspective), normative activities emerge (sociological perspective) in the classroom. Conversely, negotiated norms of the classroom (sociological perspective) represent how the teacher and students interpret and respond to each other's actions (psychological perspective) [START_REF] Cobb | Participating in classroom mathematical practices[END_REF].

SMNs related to explanations (e.g., [START_REF] Cobb | Participating in classroom mathematical practices[END_REF][START_REF] Mcclain | An analysis of development of sociomathematical norms in one first-grade classroom[END_REF][START_REF] Yackel | Sociomathematical norms, argumentation, and autonomy in mathematics[END_REF][START_REF] Yackel | Explanation, justification, and argumentation in mathematics classrooms[END_REF][START_REF] Yackel | Theoretical perspectives for analyzing explanation, justification and argumentation in mathematics classrooms[END_REF] focused on a normative understanding of "acceptable mathematical explanations and justifications". Such SMNs in mathematics classrooms of gifted students should be supportive of students' mathematical abilities and creativity. However, in a classroom environment where all teacher answers are accepted as correct or a solution method in the textbook is strictly adhered to, students' creative abilities would likely be limited [START_REF] Mann | The prominence of affect in creativity: Expanding the conception of creativity in mathematical problem solving[END_REF]. In such a classroom environment, we probably cannot see a negotiation process among classroom participants about what constitutes acceptable mathematical explanations and justifications. Thus, we should consider the teacher's role in establishing norms, and other additional factors (such as textbooks used). If the normative understandings regarding mathematical explanations and justifications are mutually agreed on by the classroom community as conceptual explanations based on mathematical reasoning processes, it would be supportive of gifted students' creative mathematical activity. Therefore, examining the normative understandings of mathematical explanations and justifications would likely give an idea about SMNs that can be supportive of creative mathematical activity.

Methods

Since the investigation of classroom norms requires a long-term and in-depth analysis [START_REF] Yackel | Sociomathematical norms, argumentation, and autonomy in mathematics[END_REF], we conducted a descriptive case study [START_REF] Yin | Case study research: design and methods[END_REF] in a single fifth-grade mathematics classroom with twelve (three girls and nine boys) gifted students to be able to reflect the characteristics of the phenomenon [START_REF] Bleijenbergh | Case selection[END_REF]. The school is a private secondary school supported by a foundation for gifted and talented students which selects its students using the WISC-IV intelligence test. The mathematics teacher of the class had seven years of teaching experience. The first author observed the lessons as a non-participant observer aiming to investigate the SMNs of the classroom without any intervention. The primary source of data consisted of forty-three mathematics lessons that were video recorded during the 2018 autumn term.

We analysed the data (transcripts of 43 lesson videos) using the content analysis method. We developed a coding scheme for SMNs related to explanations reported in the literature [START_REF] Mcclain | An analysis of development of sociomathematical norms in one first-grade classroom[END_REF][START_REF] Levenson | Mathematically and practically-based explanations: Individual preferences and sociomathematical norms[END_REF][START_REF] Yackel | Sociomathematical norms, argumentation, and autonomy in mathematics[END_REF][START_REF] Yackel | Explanation, justification, and argumentation in mathematics classrooms[END_REF][START_REF] Yackel | Theoretical perspectives for analyzing explanation, justification and argumentation in mathematics classrooms[END_REF] utilising the notions of teacher and student dimensions of a norm [START_REF] Çakır | Examining socio-mathematical norms related to problem posing: a case of a gifted and talented mathematics classroom[END_REF]. We defined an initial version of the descriptors based on the literature on SMNs related to explanations. Since norms require a twoway negotiation between the teacher and students, we defined descriptors for both dimensions (teacher and student) as evidence of an SMN.

After preparing the verbatim transcripts of lessons, the first step of the data analysis was the identification of episodes in videos where classroom discussions took place related to explanations and justifications. Then, by following [START_REF] Cobb | Participating in classroom mathematical practices[END_REF], we focused on regularities in these discussions. Content analysis pointed out an SMN directly related to explanations. Based on the literature, we defined the descriptors of teacher and student dimensions of the SMN. We revised the descriptors as we analysed the data as shown below:

Acceptable mathematical explanations and justifications should be offered [START_REF] Mcclain | An analysis of development of sociomathematical norms in one first-grade classroom[END_REF][START_REF] Yackel | Sociomathematical norms, argumentation, and autonomy in mathematics[END_REF][START_REF] Yackel | Explanation, justification, and argumentation in mathematics classrooms[END_REF][START_REF] Yackel | Theoretical perspectives for analyzing explanation, justification and argumentation in mathematics classrooms[END_REF] Teacher dimension: The teacher's explanations are based on mathematical concepts previously experienced by students. The teacher expects students to do the same. The teacher expects explanations to be based on mathematical reasoning rather than repeating the procedures. Mathematical concepts under investigation and procedures or performed actions about them are conceptually meaningful for students.

Student dimension:

Students are aware of the necessity to base their explanations on previously learned mathematical concepts and to justify their solutions. They know that explanations merely based on procedures are not enough. Students attempt to make conceptual explanations. Their explanations are not only for themselves but also meaningful for their peers.

Findings

The data analysis revealed only one SMN related to explanations and justifications that was also reported in the literature. The student dimension of the SMN was coded thirty-eight, and the teacher dimension was coded thirty-four times. We will give illustrative examples of the teacher and student dimensions of the SMN that we observed. These examples will point out the teacher's and students' expectations, awareness of these expectations, and their actions which we will consider as evidence of the SMN.

The data showed that the teacher frequently asked the question "why" in response to students' answers during class discussions, which was considered a clear indication that the answer was not considered sufficient without explanation and that the thoughts were expected to be explained and justified. For example, the teacher expected an explanation regarding the concept of prime numbers, and one of the students was aware that explanations should be based on mathematical foundations. For this reason, this student made an explanation that can be conceptually described as "numbers that cannot be divided by anything other than itself and 1" (psychological perspective). Afterward, the student who answered "even" to the question of whether the sum of the largest and the smallest prime number is odd or even, said, "if we add an even and an odd, it is odd, that is, if we add even numbers or odd numbers, it is even." Upon the teacher's request for an explanation here, it can be said that the student gave a conceptual explanation by using the concepts he had previously experienced in natural numbers, instead of making a procedural explanation based on a concrete confirmatory example. This explanation about prime numbers, which is a subject of the sixth-grade curriculum, points to "elaboration", one of the creativity components, as it shows that the student reached a generalization. The students' mathematical explanations and justifications are evidence of action regarding the related SMN (psychological perspective). The existence of both student and teacher dimensions indicates a two-way negotiation.

The excerpt below illustrates the SMN in the context of a lesson on the order of operations:

Teacher:
What is the order of operation? Kayra:

We have to do the operations inside the parentheses first. Teacher:

Operations in the parentheses first. Next? Mete:

Then factorials and exponentials. Teacher:

There is such a thing as factorial. What was the factorial? Kayra, tell us about this. Kayra:

Three factorial is, 3 times 2, and multiply by 1. Teacher:

Okay, you know the concept of factorial. So, what does the factorial concept do for us, and where do we encounter it in daily life? Mete:

In the cinema. Teacher:

For example, in the cinema, Mete said. Okay, let Serkan also tell us about it Serkan:

For example, we will order a, b, and c. Since there are three, we use three factorials.

There are as many different orders as 3 factorials. Teacher:

Burak said that he doesn't know factorial at all. Can anyone explain it to him? (One of the students explained it using the cinema example and drawing it on the board)

As can be seen above, a student's answer included the concept of "factorial" which is not included in the curriculum at this grade level. This finding sets an example for the SMN about explanations and justifications. With the teacher's explicit demand for an explanation, the students gave conceptual explanations in response (psychological perspective). We see that one of the students explained the 3! as the multiplication of the numbers by going backward from 3 to 1 which was accepted by the teacher. In addition, we can say that the teacher's question about how the factorial concept is used in daily life reflects the expectation of a different explanation from the calculational explanation made by a student. Based on this, it was seen that a student also explained how this concept was used to find how many different ways the letters a, b, and c could be arranged side by side. Here, the student preferred a more conceptual explanation for the use of the concept in daily life (cinema context), in line with the teacher's expectation, instead of making an explanation about the calculation of the factorial through an example (psychological perspective). After this verbal explanation, the student presented his explanation to the classroom community with the help of a model on the board. It can be said that the teacher's multiple requests for explanation and justification enabled the students to deepen and elaborate their explanations for their ideas.

Another dialogue that points out to the SMN started when the teacher and students were questioning why a number should be considered a perfect square:

Teacher: What is the smallest three-digit perfect square with different digits? Students: 121 Teacher:

Mete said 121, but I said no, the digits should be different, next? Students:

144. (Then, students tried to find the next perfect square with different digits) Serkan:

Can I tell you how I did it? …I knew that 12x12 is 144. I changed the multiplier to 13 and added 12. Then I made the other multiplier 13 and added 13. 169

Serkan's desire to explain his method and then present his mathematical explanation and justification reflects the student dimension of the SMN. While explaining the solution method, he stated that he started from the fact that 12x12=144 and turned the operation into an addition by increasing each factor by one (12x(1+12) and (1+12)x13). In addition, since the student stated that he increased each factor by one while explaining his method, it was understood that he used the distributive property of multiplication over addition twice in a row, from the left and the right. This detail in the student's explanation of the solution (which could be considered flexible) was seen as related to elaboration, one of the creativity components. It is understood from the teacher's reaction that he accepted the solution without giving any feedback about the solution.

Another classroom dialogue exemplifying the SMN is presented below:

Teacher:

The question is just a difficult one... How many numbers are there with two natural number divisors greater than 20 and less than 50? Serkan, how did you answer this? Serkan:

Since it says two natural number divisors, I understood that he meant prime numbers. I looked for prime numbers between 20 and 50.

We can say that the teacher's asking the student "how" he answered the question is an indication of his expectation for a more conceptual explanation when making a conclusion and that results will not be sufficient without an acceptable explanation. The student's explanation in response to the teacher's question indicates that he perceived the teacher's expectation and offered a conceptual explanation instead of a procedural one (such as listing the numbers one by one and checking whether they are prime) considering the grade level (psychological perspective). It can be said that the class community has reached a common agreement on this SMN which was observed with both the teacher and student dimensions (sociological perspective).

Another dialogue reflecting the SMN is given below. Discussions took place after the class watched clips from the Lego movie [START_REF] Lord | The lego movie [Film]. Warner Animation Group; Lin Pictures; Lego System A/S; Vertigo Entertainment[END_REF]:

Teacher: What lessons can be drawn from this about mathematics? Doruk:

The lego pieces in constructions, x, y, and z coordinates are arranged in a row. Teacher:

Good, they have instructions. Kayra:

Geometric shapes Teacher:

You're close, but it's not. Yes, good answers, but I want you to see the bigger picture. Think more broadly, not a part of the video, but think of the whole video... Deniz:

Teacher, everything should go in a certain order… Teacher:

Yes, there is a certain order... The word "order" is correct, but it does not exactly have a mathematical meaning. We multiply 9 by 60. Teacher:

You don't have to answer, we just have to think about how we will do it. Then I ask this question, if a person who starts the day at 7 o'clock stays awake until 4:45 the next day, how many hours did he stay awake?

The teacher did not accept all of the answers regarding mathematical inferences drawn from the video. In addition, the teacher requested a mathematical explanation in response to one of the answers (psychological perspective). The teacher did not accept the explanation made by the student as "everything is in a certain order" and asked for a mathematical explanation. The demand for an acceptable mathematical explanation for the concept can be seen as a clear indication of the teacher dimension of this SMN. Afterward, while students were responding to the clock problem, a student's mathematical explanation of the process instead of telling the result shows the student dimension of the SMN (psychological perspective). The explanation presented is a procedural one. The teacher's statement "You don't have to answer, we just have to think about how we will do it." indicates that the teacher evaluated the explanation given the student as "acceptable". The teacher accepted the procedural explanation instead of demanding a more conceptual one because the problem is not so complex that it needs justification.

Discussion and implications

This study investigated SMNs as a response to calls for investigating both "the nature of classroom culture and the role of the teacher in fostering mathematical expertise" (Singer et al., 2016, p. 35) concerning mathematical explanations in the context of a classroom of gifted students. We observed an SMN related to explanations and justifications. Regarding this SMN, the data indicated that both the teacher and students offered mathematical explanations which were conceptual rather than procedural. From a cognitive perspective, it is not surprising that explanations of gifted students are more conceptual than the students at the same grade level. From a sociocultural perspective, offering acceptable mathematical explanations and justifications had become part of the classroom culture.

As norms are closely related to the roles of teachers and students [START_REF] Yackel | Sociomathematical norms, argumentation, and autonomy in mathematics[END_REF][START_REF] Cobb | Participating in classroom mathematical practices[END_REF], the observed SMN points out the role of the teacher in the classroom which was also compatible with recommended teacher roles in gifted classrooms such as asking students to "clarify, justify, connect, and extend their ideas" (Johnsen & Sheffield, 2021, p. 20). The SMN as being associated with elaboration, which is a component of mathematical creativity, allowed students to "describe, illuminate, and generalize ideas" (Leikin, 2010, p. 163) by explaining and justifying their thinking. So, the SMN has the potential to support creative mathematical activity by elaborating ideas or solutions which could also enable students to deepen their understanding of mathematics by reasoning and justifying [START_REF] Singer | Research on and activities for mathematically gifted students[END_REF]. On the other hand, findings point out just one component of creativity (elaboration). However, ideas and solutions should also be evaluated based on other components such as originality, fluency, and flexibility. This evaluation should be an essential part of the classroom micro-culture. The lack of an SMN regarding the evaluation of creativity components might be one of the reasons why explanations in the classroom dialogues were not at a high level.

Based on our findings we will discuss the implications. The first one is practical and concerned with the SMN: "Acceptable mathematical explanations and justifications should be offered". For this SMN, explicit evaluations of explanations and justifications were not made in the classroom. Although lacking explicit evaluations, there was a taken as shared understanding of conceptual explanations rather than procedural ones. The second implication is a theoretical one. Our study was conducted within a classroom of a teacher who had been teaching the same classroom for five years.

We focused on the established norms rather than the negotiation process during norm construction. Therefore, we could not observe explicit talk about what counts as an acceptable mathematical explanation and justification. For example, in the discussion of prime numbers, the teacher accepted the student's explanation about the sum of an even and an odd number without any feedback about why it is acceptable.

The reason for not observing explicit evaluations might also be related to our participant teacher's beliefs and pedagogical content knowledge. Researchers suggest more challenging problems (Leikin, 2018) for gifted students, which also could require more original or flexible explanations. Establishing the SMN regarding acceptable mathematical explanations and justifications, with appropriate task selection and explicit evaluations, could enhance gifted students' mathematical creativity and proving abilities. We also suggest establishing norms regarding explanations in regular classrooms according to students' levels and supporting their problem-solving practice.


Anastasia Volkova
email: anastasia.volkova@inria.fr

Garcia † Rémi
email: remi.garcia@univ-nantes.fr

Florent De Dinechin
email: florent.de-dinechin@insa-lyon.fr§

Martin Kumm
email: martin.kumm@cs.hs-fulda.de

Hardware-optimal digital FIR filters: one ILP to rule them all and in faithfulness bind them

This article addresses the implementation of Finite Impulse Response filters as digital hardware circuits. It formalizes, as a mathematical model, the problem of finding the optimal circuit for a given frequency specification and given input/output fixed-point formats. This model captures at the bit level a wide class of implementations (transposed-form circuits based on truncated shift-and-add adder graphs). It also captures formally the constraints due to the frequency specification, as well as those due to rounding to the output format. This model can be expressed as an Integer Linear Programming (ILP) problem, such that the optimal circuit (in terms of bit-level adders and registers) can be found by standard ILP solvers. This approach allows for a completely automatic tool from a frequency specification to a circuit with user-specified input and output formats. This tool is evaluated (with cost functions modeling FPGAs) on several benchmarks.

I. Introduction

The hardware implementation of digital filters has received a lot of attention in the last half century. This article addresses the construction of circuits implementing Finite Impulse Response (FIR) filters for a given frequency specification (Fig. 1).

Classically, this process begins with a filter design (FD) step that determines the real-valued coefficients h i of a polynomial transfer function H(z) = N i=0 h i z -i such that the frequency specification is strictly satisfied. A prerequisite for a hardware implementation is the quantization (Q) of the real coefficients into finite precision (fixed-point) data formats, in such a way that the frequency response is still respected. Using the quantized coefficients, a digital circuit C can be implemented (I) as one of a variety of filter structures (e.g., direct 1 or transposed form 2 in Fig. 1). For each filter structure, there are also multiple techniques to build the corresponding hardware multipliers and adders, and then each operator can be sized and rounded to optimize the resources. Two examples are shown in Fig. 1 as 3 and 4 .

The purpose of this article is to address the construction of optimal circuits. To our knowledge, the state of the art, so far, only partially answers this problem: previous works (reviewed in Section II) either explore only a subset of the implementation space, or use heuristics, or combine local optimizations instead of a single global one, or generally do not address the issue of rounding. This last issue is particularly relevant to actual applications: typical circuits have the same input and output formats (for instance 16-bit fixed-point), thus making rounding mandatory in practice. But rounding is not linear, therefore rounded circuits are not linear time-invariant (LTI), and strictly speaking their frequency response is illdefined.

In signal processing, rounding errors are typically modeled as noise, and the measure of the quality of the implementation step is a signal/quantification noise ratio (SQNR), in dB. This approach remains statistical, and founded on statistical hypotheses that are not always true in practice. The present work adopts a stricter point of view where the quality measure is the worst-case error. The format of the output word (e.g., 8 bits) can be used as a specification of the accuracy (e.g., the absolute error on the output should not exceed 2 -8 ). This is called faithful rounding, and it can be extended to the frequency domain [START_REF] De Dinechin | Towards Arithmetic-Centered Filter Design[END_REF] as follows: "A digital circuit C is faithful to a frequency specification S when there exists an LTI filter L satisfying S such that the output of C is a faithful rounding of the output of L."

This definition was a missing brick in the construction of a model of practical circuits (i.e., including rounding) respecting frequency specification constraints. In the proposed model,

• the implementation space is the set of transposedform circuits where the multiple constant multiplication (MCM) is implemented as a graph of (possibly truncated) add/subtract nodes; it is detailed in Section III. • the unknowns are the filter coefficients and the numerous parameters of the implementation (the shift-and-add graph, the positions of truncations, etc.); • the cost function is a function of the unknowns that models the cost of registers and adders at the bit level; • the quality constraints express faithfulness in the worst case as stated above. Finding the optimal circuit in this model can be expressed as a (mixed) Integer Linear Programming (ILP) problem. ILP is an efficient and versatile formalism to find optimal solutions of combinatorial problems over integer variables under linear constraints. Many powerful ILP solvers exist, so this approach can rely on them to actually perform the optimization. The detail of this ILP formulation is given in Section IV, and it is evaluated in practice in Section V.

II. Related work and positioning

This article completes a historical trend to replace a succession of local optimization steps FD, Q and I with a global one. The combination of the FD + Q steps has been studied since the 1960's [START_REF] Oppenheim | Discrete-Time Signal Processing[END_REF], and can even be regarded as solved for certain practical instances of fixed-point FIR design [START_REF] Kodek | LLL algorithm and the optimal finite wordlength FIR design[END_REF]- [START_REF] Kodek | An algorithm for the design of optimal finite wordlength FIR filters[END_REF].

The I step was historically treated separately, with a focus on multiplierless implementation of the MCM block using bit-shifts and additions. The construction of efficient MCM blocks can be based on the binary encoding of the coefficients [START_REF] Samueli | An improved search algorithm for the design of multiplierless FIR filters with powers-of-two coefficients[END_REF]- [START_REF] Shahein | A Novel Hybrid Monotonic Local Search Algorithm for FIR Filter Coefficients Optimization[END_REF], or can use graph-based heuristics [START_REF] Voronenko | Multiplierless Multiple Constant Multiplication[END_REF]- [START_REF]Towards Optimal Multiple Constant Multiplication: A Hypergraph Approach[END_REF]. Optimal MCM techniques were proposed relatively recently using dedicated Branch&Bound (B&B) algorithms [START_REF] Aksoy | Exact and approximate algorithms for the optimization of area and delay in multiple constant multiplications[END_REF], [START_REF] Lopes | Optimally solving the MCM problem using pseudo-boolean satisfiability[END_REF] or an ILP model [START_REF] Kumm | Optimal Constant Multiplication using Integer Linear Programming[END_REF], [START_REF] Garcia | Toward the Multiple Constant Multiplication at Minimal Hardware Cost[END_REF].

The combined FD+Q+I problem has been solved using dedicated heuristics and B&B algorithms but in a search space restricted to special encodings [START_REF] Yu | Optimization of Linear Phase FIR Filters in Dynamically Expanding Subexpression Space[END_REF], [START_REF] Shi | Design of Linear Phase FIR Filters With High Probability of Achieving Minimum Number of Adders[END_REF]. Recent optimal B&B [START_REF] Aksoy | SIREN: A depth-first search algorithm for the filter design optimization problem[END_REF], [START_REF]Exact and Approximate Algorithms for the Filter Design Optimization Problem[END_REF] and ILP-based [START_REF] Kumm | Design of Optimal Multiplierless FIR Filters With Minimal Number of Adders[END_REF] approaches solve a complete FD+Q+I problem, but only in the space of (impractical) circuits that compute the filter output exactly. Besides, these works optimize the number of adders, while adders in an MCM may have different costs. The optimal truncated MCM problem was solved only later [START_REF] Garcia | Toward the Multiple Constant Multiplication at Minimal Hardware Cost[END_REF].

In this work, we use as basis the versatile ILP model from [START_REF] Kumm | Design of Optimal Multiplierless FIR Filters With Minimal Number of Adders[END_REF], as it is not as sensitive as the B&B [START_REF] Aksoy | SIREN: A depth-first search algorithm for the filter design optimization problem[END_REF], [START_REF]Exact and Approximate Algorithms for the Filter Design Optimization Problem[END_REF] to design-space size explosion. We improve it to provide practical

+ 0 + 2 + 2 x 4 17x 1 7 -6 7 -6 5 49x 3 51x 3 + = + = + =
Fig. 2: An adder graph computing 49x and 51x in 3 additions, with its optimal truncations when the inputs are 3-bit numbers and a 3-bit output is needed. The cost of each adder is given in the green labels. implementations with internal data path truncations that are optimized but guarantee faithfulness. We achieve this by (1) using the truncated MCM model [START_REF] Garcia | Toward the Multiple Constant Multiplication at Minimal Hardware Cost[END_REF] counting resources at the bit-level (and not adder-level as in previous literature), and (2) linking the output accuracy requirement with truncation choices that are explored by the solver.

III. Truncated Multiple Constant Multipliers

In approaches based on shift-and-add circuits, an MCM may be represented as an adder-graphs, e.g., Fig. 2. The root of the adder graph is the input integer x. Each node represents the addition of two potentially negated and shifted inputs -a shift multiplies by a power of two. Each adder thus computes an intermediate factor, called its fundamental. For example, in Fig. 2 the first adder computes 17x

= x ≪ 4 + x = 2 4 • x + x.
For practical FIR filter implementations, the output of the MCM block will potentially be truncated to some intermediate format. To avoid computing unnecessary bits that will be rounded anyway, the truncations should be lifted into the adder graph while guaranteeing the faithfulness of the results. The Truncated MCM ILP model proposed in [START_REF] Garcia | Toward the Multiple Constant Multiplication at Minimal Hardware Cost[END_REF] solves this problem optimally: given a set of integer constants and associated input/output data word lengths, construct an adder graph describing a multiplierless solution together with the potential intermediate truncations that guarantee faithful rounding based on a worst-case error model.

At the bit level, an adder or subtracter is built out of full adders and half adders, and these may include inversions for subtractions. We do not distinguish these various cells in this work as they have the same cost on the FPGAs that we target for our experiments, and use the generic term one-bit adder. Fig. 2 also shows that for 3-bits inputs and outputs, the MCM requires 3 adders but these cost only 4 one-bit adders (green labels on each adder node). Indeed, since a 3-bit approximation to 51x is enough, removing the 6 lower bits from the 7-bit signal 17x (indicated as the label 7-6 on the wire) will save 5 one-bit adders while still ensuring the faithful rounding of both outputs. In total, truncations save 6 one-bit adders out of the 10 required for the exact MCM. In an ILP model [START_REF] Garcia | Toward the Multiple Constant Multiplication at Minimal Hardware Cost[END_REF], an adder node a compute the fundamental c a (see Fig. 3a). The model aims at finding the best adder-graph topology such that the leaves of the graph compute every constant in the target set. The formal constraint linking together the left and right inputs of an adder node (c a,l and c a,r ) with the shift (s a,l ), the negations (σ a,l and σ a,l ) and a potential right-shift after the node (s a ) is the following:

c a = 2 -s a (-1) σ a,l 2 s a,l c a,l + (-1) σ a,r c a,r . (1)
The number of one-bit adders in each node, B a , is in the worst case equal to its output word length and this can be propagated through the graph. However, certain topologies can be more advantageous (e.g., in Fig. 2, 17x is computed from non-overlapping numbers and uses no one-bit adders if x is unsigned). Similarly, truncating the data before additions can save one-bit adders. Numerous special cases were incorporated in the ILP model [START_REF] Garcia | Toward the Multiple Constant Multiplication at Minimal Hardware Cost[END_REF].

The objective is then to minimize the total number of onebit adders, min

a B a . (2)
Each truncation of t bits, however, induces an error |ε t | ≤ 2 t , which needs to be propagated. In the ILP model, an error ε a is associated to each adder-node a and is influenced by the incoming shifted errors and a truncation-induced error (see Fig. 3). This is formalized by the following constraint:

ε a = 2 -s a 2 s a,l ε a,l + ε a,r + 2 t a,l + 2 t a,r (3)
Finally, the error of each output adder c out must be bounded by the corresponding ε i , deduced from the user specification.

Equation ( 3), together with the one-bit adder gain due to truncations t a of each adder, permits the solver to automatically find the trade-off between the one-bit adder count B a and the error bounds ε i . We refer the reader to [START_REF] Garcia | Toward the Multiple Constant Multiplication at Minimal Hardware Cost[END_REF] for the complete linearized model, which we integrated into our tool.

IV. One ILP to rule them all

Hardware-aware filter design problems usually start with a functional specification of the frequency domain behavior, together with the number of filter coefficients. An optimization procedure constraints filter coefficients to integer values and aims at minimizing the hardware resources required for the

N 2 + 1 c m (ω) =      1 for m = 0 2 cos(ωm) for m > 0 II sym. odd N+1 2 c m (ω) = 2 cos(ω(m + 1/2)) III asym. even N 2 c m (ω) = 2 sin(ω(m -1)) IV asym. odd N+1 2 c m (ω) = 2 sin(ω(m + 1/2))
MCM block.This section incorporates the fine-grained Truncated MCM model [START_REF] Garcia | Toward the Multiple Constant Multiplication at Minimal Hardware Cost[END_REF] into the ILP formulation based on [START_REF] Kumm | Design of Optimal Multiplierless FIR Filters With Minimal Number of Adders[END_REF] and give a new model of all sources of errors to dispatch the acceptable error-budget between data paths and maximize truncations.

A. Design of linear-phase FIR filters with fixed-point coefficients

An N-th order linear phase FIR filter can be described by its zero-phase frequency response which has the property that its magnitude is identical to that of the transfer function. Let D(ω) and D(ω) be the desired lower and upper bounds of the output frequency response H R (ω). The associated frequency specification-based FIR filter design problem consists of finding real coefficients h m , m = 0, . . . , M -1 that fulfill

D(ω) ⩽ M-1 m=0 h m c m (ω) ⩽ D(ω), ∀ω ∈ Ω, (4)
where Ω ⊆ [0, π] is a set of target frequency bands (usually pass and stopbands) and c m (ω) terms are trigonometric functions. Relation between c m (ω), number of coefficients M, the degree N and the filter type is given in Table I The FD problem ( 4) is a semi-infinite constraint, but it is usually discretized over Ω d ⊆ Ω [START_REF] Kumm | Design of Optimal Multiplierless FIR Filters With Minimal Number of Adders[END_REF]. Fixed-point FIR filter design problems further restrict the search space to integer variables h ′ m with |h ′ m | < 2 B , where the coefficients of H R (ω) are

h m = 2 -B h ′ m (5)
and B is the maximum effective word length of each coefficient (excluding sign bit).

Applying [START_REF] Kodek | An algorithm for the design of optimal finite wordlength FIR filters[END_REF] to the discretized version of ( 4) we obtain a finite number of linear constraints over integer variables

h ′ m 2 B D(ω) ⩽ M-1 m=0 h ′ m c m (ω) ⩽ 2 B D(ω), ∀ω ∈ Ω d . (6)
B. Implementation space and cost function MCM block: The filter coefficients h ′ m should now be linked to the inputs of the truncated MCM problem. Similarly to [START_REF] Kumm | Design of Optimal Multiplierless FIR Filters With Minimal Number of Adders[END_REF], we exploit the versatility of ILP modeling and export the Truncated MCM model into the global ILP and provide the so-called glue constraints. First, we need to connect the integer filter coefficients h ′ m to the target constant set of Truncated MCM model:

h ′ m = (-1) ϕ 2 s c a M if o a,m,s,ϕ = 1 (7)
where a M denotes a multiplier-block adder, ϕ is the coefficient sign and binary variable o a,m,s,ϕ encodes if h ′ m , potentially shifted by s bits, is connected to the fundamental c a .

Structural adder chain: Then, we need to connect the outputs of the Truncated MCM model to the structural adders. Denote a S a set of at most N -1 structural adders, and B a S its one-bit adder cost. According to symmetries and even/odd degree of the filter (see Table I), most of the MCM-block coefficients h m will appear twice in the adder chain. Since inputs of the structural adder are independent, we have to compute the number of one-bit adders based on worst-case data word length. The only way to gain one-bit adders is to introduce truncations t a S -1 and t a M on the preceding structural adder and corresponding MCM-block output, respectively. Hence, the one-bit adder cost of a structural adder is, recursively,

B a S = msb a S -1 + msb a M -max(t a S -1 , t a M ), (8)
where msb a S -1 corresponds to the most significant bit position of the preceding structural adder, and msb a M corresponds to the correctly-computed multiplier-block output, respecting the filter type. We msb 0 to the MSB position of h 0 x. Cost function: In contrast to previous works, the use of Truncated MCM permits us to fine-tune the cost function to the gate-level. Our objective is to minimize the total number of one-bit adders in the MCM block and structural adder chain:

min a M ∪a S (B a M + B a S ) . (9)

C. Data-path sizing constraints

As introduced in [START_REF] De Dinechin | Towards Arithmetic-Centered Filter Design[END_REF], faithfulness of a digital circuit to frequency specifications has two components: behavior of the linear part of the circuit is guaranteed by the FD constraints (4) and behavior of the nonlinear part due to internal rounding should be suppressed to the last bit of the computed output signal. Denote ε out = y(k)y(k) the output error, where y is the finite-precision counterpart of the real signal y. The faithfulness to output word length specification, e.g., in terms of the least significant bit position 2 ℓ out translates into the constraint |ε out | < 2 ℓ out . Our task now is to define the link between the output error ε out , the structural adder errors ε a S and the MCM-block errors ε a M that constrain the truncations.

First, we need to account for the final rounding (see Fig. 1 bottom), which induces an error that is bounded by 2 ℓ out -1 . Hence, the last structural adder must actually satisfy the following constraint:

ε = |ε a S | < 2 ℓ out -1 , a S = N -1.
We can recursively define the error-propagation rule through each potentially truncated structural adder:

ε a S = ε a S -1 + ε a M + 2 t a S + 2 t a M , (10)
where the the errors from the preceding registers and from the MCM block are added to the potential truncation errors. By counting the number of trailing zeros in inputs of each adder, as in [START_REF] Garcia | Toward the Multiple Constant Multiplication at Minimal Hardware Cost[END_REF], we significantly tighten the propagated error bound, since truncating those does not induce any error. With [START_REF] Aktan | An algorithm for the design of low-power hardware-efficient FIR filters[END_REF] we provided the link to Truncated MCM block, and relate the truncations in structural adders with the overall rounding error, completing the global ILP model. The full list of constraints can be found in the tool's web page.

V. Experimental Results

To evaluate our method, we implemented the ILP model generation with Julia within the Shift-And-Add circuits for digital FIR filters (SAFIR) project 1 . To be able to perform hardware experiments, we used FloPoCo2 and implemented a new operator IntFIRTransposed. The automatic test bench generation of FloPoCo was used to validate the obtained designs. All implemented tools are published as open-source.

We test our method on a reference specifications from the literature commonly referred to as S 2 and used in many previous works [START_REF] Shahein | A Novel Hybrid Monotonic Local Search Algorithm for FIR Filter Coefficients Optimization[END_REF], [START_REF] Shi | Design of Linear Phase FIR Filters With High Probability of Achieving Minimum Number of Adders[END_REF], [START_REF]Exact and Approximate Algorithms for the Filter Design Optimization Problem[END_REF]- [START_REF] Yu | Design of Linear Phase FIR Filters in Subexpression Space Using Mixed Integer Linear Programming[END_REF]. We also introduce a small toy filter T for illustration purpose.

They are low-pass filters defined by

1 -δ p ⩽ H R (ω) ⩽ 1 + δ p , ω ∈ Ω p (passband), -δ s ⩽ H R (ω) ⩽ δ s , ω ∈ Ω s (stopband),
where the values of δ p , δ s , Ω p , Ω s for each specification are given in Table II.

For the ILP solving, we used Gurobi Optimizer [START_REF]Gurobi Optimization Website[END_REF] v10.0 with a timeout limit of 8 hours. The input word size was set to w in = 8 bit. The results for different filters and different values of ε are given in Table III. To get a target output word size of w out , ε has to be set to ε = 2 ∆w out -1 , where ∆w out = w out,fullw out is the difference between the output word size of the full precision output and the target output word size. The table gives the number of adder/subtractors, and the number of one-bit adders for the MCM block (MCM), the structural adders (SA) and the total number (tot). For T, the ILP proves the optimality of solutions (one is shown in Fig. 4), but for S2 the model is too large and the optimality cannot be proven within the timeout. Still, the found solutions save one-bit adders thanks to truncation as expected.

Synthesis experiments have been performed for all designs using Vivado 2019.1 targeting an AMD Kintex (xc7k70tfbv484-3). The resulting LUT numbers and the critical path delay t cp are shown in the last two columns of Table III. As each one-bit adder requires one LUT on current FPGAs (apart from unpredictable optimizations in synthesis), Fig. 4: The complete solution for the toy filter T faithful to 8 bits (ε < 2 6 ) on signed inputs. Note that three of the structural adders actually compute subtractions, to implement the coefficients -4.

the obtained LUTs closely follow the number of one-bit adders from the optimization.

VI. Conclusion

Based on the recent improvements in the ILP-based approaches for the design, quantization and implementation of multiplierless FIR filters, we develop a last missing piece in the mathematical modeling and optimal implementation of hardware-efficient FIR filters. The versatility of ILP models ensures that changing the metric or updating the implementation method is as simple as adding new variables and constraints into the model. We present a specifications-to-VHDL push-button tool, SAFIR, which takes care of all operator design, sizing and rounding automatically, letting the digital filter designer to focus on more high-level implementations questions, e.g., input/output word lengths.

Fig. 1 :

 1 Fig.1: From a frequency specification to an architecture.

Fig. 3 :

 3 Fig. 3: Modeling adder graph topology and errors

TABLE I :

 I Relation between filter order N, number of coefficients M and function c m (ω) for different filter types

	Type Sym.	N	M	c m (ω)
	I	sym.	even

TABLE II :

 II Specifications of the filters used in experiments

	Name Ω p /π	Ω s /π	δ p	δ s
	T	[0, 0.3]	[0.5, 1]	0.01	0.01
	S2	[0, 0.042] [0.14, 1] 0.026	0.001

TABLE III :

 III Optimization and synthesis results

	Filter	Target	#adders			#half/full adders	synthesis
		Error	MCM SA tot	MCM SA	tot	LUTs	t cp [ns]
		ε = 0	2		8	10	16		90	106	111	6.05
	T	ε < 2 4	2		8	10	16		85	101	111	6.05
		ε < 2 8	2		8	10	16		71	87	95	6.06
		ε = 0	15	51	66	139	892 1031	1038	9.79
	S2	ε < 2 4	15	51	66	134	886 1020	1025	9.40
		ε < 2 8	15	41	66	137	840 977	996	10.57
											MCM
			10-2				11				13-4	13-4
			10-2	+	9	11-4	+	8		12	+ 10	14	+ 11

https://gitlab.com/filteropt/safir

https://flopoco.org