Swaminath Venkateswaran
email: swaminath.venkateswaran@ls2n.fr

Damien Chablat

A new inspection robot for pipelines with bends and junctions

Keywords: Piping inspection robot, Bio-inspired, Elephant trunk, Tensegrity structure, Universal joint

The application of robots for the inspection of pipelines are of greater significance in industries such as nuclear, chemical and sewage. The major problem in the design of these robots lies in the selection of a suitable locomotion principle, selection of an articulation unit that facilitates the robot to pass through pipe bends and management of cables. In this context, the design of a new bio-inspired piping inspection robot that resembles an elephant trunk has been presented. With the help of leg mechanisms and actuators, a caterpillar locomotion is used within this trunk for establishing adaptive contact points with the walls of pipeline. For the passage through bends and junctions, several case studies of existing researches have been taken into account for the design of an articulation unit. Two solutions, (i) a passive tensegrity structure and (ii) an active tensegrity structure have been proposed for the robot to pass through pipe bends and junctions. A detailed design analysis of the passive solution that uses a universal joint has been presented in this article.

Introduction

Manual inspection and maintenance of pipelines in industries such as nuclear and chemical are not only time consuming but also pose threat to human life and causes long term radiation effects. Piping inspection robots play an important role in such situations and they have a major attraction in the scientific research community. The main design criteria for these robots are locomotion, contact type with walls, cable management and articulation unit to pass through bends. Roh et al. [START_REF] Roh | Differential-drive in-pipe robot for moving inside urban gas pipelines[END_REF] proposed a classification of in-pipe inspection robots viz. Pig type, Wheel type, Caterpillar type, Wall-press type, Walking type, Inchworm type,and Screw type. This classification provides a glimpse of the contact type with walls and the locomotion principle of the robot. However, detailed research on the design of an articulation system for bends and cable management inside complicated pipeline trajectories have not been carried out. In this article, we focus mainly on the key issues to be addressed for a piping inspection robot to pass through bends and junctions. Based on that, two articulation units have been proposed. These systems can be classified as active and passive units. For example, Hirose et al. [START_REF] Hirose | Design of in-pipe inspection vehicles for φ 25,φ 50,φ 150 pipes[END_REF] proposed THES-I robot which employs a universal joint actuated by a DC-Motor. Anthierens et al. [START_REF] Anthierens | Design of an electro pneumatic micro robot for in-pipe inspection[END_REF] developed an electro pneumatic robot which employs a metallic bellow system to pass through bends. A steering mechanism powered by servo-motors was designed by Ankit et al. [START_REF] Nayak | Design of a new in-pipe inspection robot[END_REF] to work through pipe bends. However, some interesting passive systems include the robot developed by Kwon et al. [START_REF] Kwon | Design and motion planning of a two-moduled indoor pipeline inspection robot[END_REF] where a compression spring is employed to push and pull the two motor modules when working through T-sections and bends. Zhang et al. [START_REF] Zhang | Design and motion analysis of a flexible squirm pipe robot[END_REF] also proposed a robot with a passive flexible helical axle articulation unit. A bio-inspired piping inspection robot has been presented in [START_REF] Chablat | Mechanical Design Optimization of a Piping Inspection Robot[END_REF] and [START_REF] Chablat | Dynamic Model of a Bio-Inspired Robot for Piping Inspection[END_REF]. By coupling leg mechanisms with linear actuators, the robot moves like a caterpillar and establishes a tight contact with the walls of pipeline [START_REF] Chablat | Mechanical Design Optimization of a Piping Inspection Robot[END_REF] . However, the robot is incapable of working inside junctions and bends as it is a rigid prototype. In this article, the design of this caterpillar robot has been completely modified into a reconfigurable system. The new design of the robot resembles the trunk of an elephant having articulation units as well as the caterpillar modules being retained for establishing contact points at all instances of locomotion. Two tensegrity structures have been proposed for the articulation unit. For the first one, a passive universal joint with tension loaded springs at 120 • has been designed for the robot to pass through bends. The spring system tends to limit the bending angle of the universal joint to a certain value. The second one incorporates cables to drive the mechanism to facilitate the robot to travel inside pipe bends and junctions. This article explains in detail the design and analysis of the first solution and brief discussions are made for the second solution.

Design factors and constraints for developing a new architecture

Recently, Henry et al. and Chablat et al. [START_REF] Chablat | Mechanical Design Optimization of a Piping Inspection Robot[END_REF][START_REF] Chablat | Dynamic Model of a Bio-Inspired Robot for Piping Inspection[END_REF][START_REF] Henry | Multiobjective design optimization of the leg mechanism for a piping inspection robot[END_REF] have proposed a bio-inspired piping inspection robot that is capable of inspecting pipelines between diameter range of 40-94 mm. The schema of the robot proposed in [START_REF] Chablat | Mechanical Design Optimization of a Piping Inspection Robot[END_REF] is represented in Fig. 1. By using slot-follower leg mechanisms and linear actuators, the robot accomplishes its locomotion as well as contact with pipeline walls in 6 steps. However, the major disadvantages of this robot are it is a rigid prototype and the management of cables have not been studied in detail.

Factors to be considered for linear, bent and branched pipes

In general, for the design of a piping inspection robot, three main considerations have to be taken into account which are rectilinear motion, passive compliance, and active compliance. The architecture represented in Fig. 1 criteria as it holds good inside perfectly vertical and horizontal pipelines. It is essential to address the other two criteria in order to make the robot work through bends and junctions. Passive compliance could be imagined by a robot that passes through bends at 90 • or less. The articulation unit that drives the robot through such bends need not be necessarily active. Examples of such robots include the squirm pipe robot proposed by Zhang et al. [START_REF] Zhang | Design and motion analysis of a flexible squirm pipe robot[END_REF] and the caterpillar type robot proposed by Kwon et al. [START_REF] Kwon | Design and motion planning of a two-moduled indoor pipeline inspection robot[END_REF]. For active compliance, it is essential for the articulation unit as well as the contact mechanism with walls to be actuated and adaptable. Robots passing through T-branches and junctions need to adopt active compliance. However, the direction of movement inside a T-branch or junction is usually controlled through software programming and sensors. An interesting example is the robot proposed by Ryew et al. [START_REF] Ryew | Inpipe inspection robot system with active steering mechanism[END_REF] which employs a double active universal joint (actuated by two motors and two clutches) where the articulation remains active while passing through junctions and remains passive through an elbow . This robot also uses a wheel system with a pantograph mechanism to have contact with pipeline walls which adapts according to bends and straight profiles. The general representation of the passive and active compliance is shown in Figs. 2a and2b. Another important factor for the articulation unit is the maximum angle at which it bends when encountering a curvilinear profile. Depending on the center line radius (CLR) of the pipe bend, the articulation unit can facilitate the robot to bend either at x • or -x • which could be referred to as "Tilt". The tilting range of ±x • is depicted in Fig. 2c.

Architecture of the new piping inspection robot

In order to address the compliance factors and tilt limits, a new architecture of the bio-inspired robot has been proposed and it is represented in Fig. 3. The caterpillar locomotion from [START_REF] Chablat | Mechanical Design Optimization of a Piping Inspection Robot[END_REF] has been retained in this architecture. This module ensures tight contact with pipeline walls through a force control algorithm inside vertical and horizontal orientations. By the introduction of suitable articulation units between each motor modules, the robot can be made to pass through pipe bends. While moving through bends, the entire robot resembles an † 3D model of this robot in CATIA with joints/links and robot simulation available in -https://www.youtube.com/watch?v=7z6-by83mtw a b c "Elephant trunk" wherein the force is transmitted from the front to rear module to pull the robot in order to pass through the curvature and vice-versa. The articulation units are designed with a view that they undergo deflection like a beam without torsion. In Fig. 3, O A B P represents the slot-follower mechanism which is being unchanged. They are attached with the front and rear clamping modules for accomplishing the contact points with pipeline walls. The parameters ρ and ρ c represents the actuation units of the leg and central elongation modules. The joints J represents the articulations that are being introduced in the robot. A spring-loaded four-bar mechanism with a wheel is introduced in the front and rear end of the robot. OB, BC and AB represents the links of four-bar and OA denotes the tension spring having a stiffness of k N/mm. This mechanism ensures contact with the walls of the pipeline during static and dynamic modes. The wheel mechanism also helps the robot to easily enter and exit through pipe bends and junctions.

3 Tensegrity structures as joints for the robot to pass through pipe bends and junctions

We focus mainly on the introduction of a suitable articulation unit that can facilitate the robot to work through bends at 90 • or less. As the contact point criterion for the robot has been addressed by retaining the caterpillar module and introduction of wheel mechanism, we look for an articulation unit to work through bends. Two tensegrity structures have been proposed for articulation unit in this article: a passive structure in order to pass through bends and an active structure to pass through junctions. We go in detail with the former mechanism and its design. A universal joint is proposed for the passive solution.

To keep in balance the individual parts of the universal joint assembly, three tension loaded springs at an angle of 120 • are mounted at a radius r f from the central axis of the universal joint. The universal joint transmits the necessary force from the front to the rear end of the robot while passing through bends thereby making the robot to resemble like an "Elephant trunk". The proposed articulation unit is represented in Fig. 4.

holes for wiring passage holes for holding springs Wires of actuator Tension springs of length 'l'

Side view Front view r f

Fig. 4. Proposed tensigrity structure with three springs and a universal joint

In Fig. 4, r f represents the radius on the flange where the tension springs are mounted. l represents the free length of each spring. The other three holes of the flange are used as a passage for the wiring coming from the actuators. Fig. 4 also represents the default posture of the joint under non-working condtions as well as inside a perfectly vertical and horizontal pipeline. It is necessary to derive the equations for the joint in order to determine the stable configurations. With the help of SIROPA package in Maple [START_REF] Jha | Workspace, Joint space and Singularities of a family of Delta-Like Robot[END_REF][START_REF] Moroz | Cusp points in the parameter space of RPR-2PRR parallel manipulators[END_REF], the passive universal joint system with the spring is constructed in the form of a parallel manipulator similar to a 3-SPS -U [START_REF] Alici | Topology optimisation and singularity analysis of a 3-SPS parallel manipulator with a passive constraining spherical joint[END_REF] configuration and it is represented in Fig. 5.

In Fig. 5, B 1 , B 2 and B 3 represents the base mounting point for the three springs. C 1 , C 2 and C 3 represents the other end of the mounting point for the springs. A represents the central origin (universal joint). The springs are represented by the three red actuators. The vector coordinates for the base points B i from the center of mounting flange is given by: In Eq. ( 1),the minus sign indicates that the base mounting points are on the negative side with respect to origin A = [0, 0, 0]. For the estimation of mounting points C i , the theory of Tilt-torsion (T&T) is employed. Parallel Kinematic Machines (PKM) adopt the concept of T&T where the platform of the robot is usually mobile and asymmetric [START_REF] Bonev | Advantages of the modified Euler angles in the design and control of PKMs[END_REF]. However, torsion is not considered for the proposed actuation unit. Thus, only the tilt angle and azimuth is essential for determining the position of mounting points C i . The representation of tilt and azimuth with the articulation unit is shown in Fig. 6. In Fig. 6, β represents the azimuth angle between x-axis and the face of zaxis. A rotation of α about axis M causes a shift of xyz axes to x * y * z * axes and this refers to the tilt. The rotation matrix R for the tilt and azimuth is given by:

B 1,2,3 =   r f cos 2πj 3 r f sin 2πj 3 -r f   where j = 0, 1, 2 (1
R = R z (β)R x (α)R z (-β) (2)
When α and β = 0 or in other words when the base and the mobile platform are parallel, Eq. ( 2) becomes an identity matrix. The vector coordinates for C i in this condition is given by:

C 1,2,3 =   r f cos 2πj 3 r f sin 2πj 3 r f   where j = 0, 1, 2 (3)
For finding the exact position of C i at a certain tilt, the rotation matrix obtained from Eq. ( 2) is multiplied by Eq. ( 3). The length of the springs l i can now be estimated by calculating the distance between B i and C i and the equation is given by:

l i = (B i [1] -C i [1]) 2 + (B i [2] -C i [2]) 2 + (B i [3] -C i [3]) 2 with i = 1, 2, 3 (4)
While passing through bends and junctions, it is not necessary for the coupling to bend up to a certain angle. The tension loaded spring mechanisms restricts the bending angle till a certain limit. In order to estimate the limits, it is essential to calculate the feasible workspace for the articulation unit. The tilt angle α is critical when the robot encounters a bend inside pipeline. For ease of calculations, we set the limits for azimuth angle as β ∈ [-π, π]. With the help of Maple, the feasible maximum and minimum workspace range constraint equations C are estimated which are given by:

C 1+3i = [2 r f 2 (-1 + cos (α)) (cos (β)) 2 -4 r f 2 sin (β) sin (α) +4 r f 2 -l x 2 ] (5)
C 2+3i = [-2 r f 2 cos (β) (sin (β) cos (α) -sin (β) -2 sin (α)) √ 3 -2 r f 2 (-1 + cos (α)) (cos (β)) 2 + 4 r f 2 sin (β) sin (α) +3 r f 2 cos (α) + 5 r f 2 -2 l x 2 ] (6)
C 3+3i = [2 r f 2 cos (β) (sin (β) cos (α) -sin (β) -2 sin (α)) √ 3 -2 r f 2 (-1 + cos (α)) (cos (β)) 2 + 4 r f 2 sin (β) sin (α) +3 r f 2 cos (α) + 5 r f 2 -2 l x 2 ] ( 7
)
where for i = 0, 1 we have l x = l min , l max

The limits l x = l min and l max represents the minimum and maximum extension of each spring while passing through a pipe bend. The radius r f for the mounting points of the spring from flange center is taken as 11 mm from the existing design [START_REF] Chablat | Mechanical Design Optimization of a Piping Inspection Robot[END_REF]. By setting the limits l min = 7 mm and l max = 31 mm, we compute the feasible range of α in Maple and the result is represented in Fig. 7.

In Fig. 7, the blue regions highlight the feasible solutions. The ideal values of tilt (α) lies between [-π/3, π/3]. Various postures can be generated for a fixed (not shown in Fig. 7) but the azimuth angle is highly limited and there exists collision between parts in this zone. Using the ideal range of tilt and varying azimuth angles, the spring lengths and their limits could be designed and realized in CATIA. The cables coming from the actuators can be made to pass through the holes provided in the flange in a uniform pattern to the central control unit. By assembling the tensegrity mechanism, caterpillar module, four-bar wheel mechanisms, and standard fasteners, the entire robot can be realized in CATIA. The rendered model of the robot which resembles an "Elephant trunk" is represented in Fig. 8.

For the second tensegrity structure, cable mechanisms could be added to the passive solution. The analysis of an actuated X-shape Snelson mechanism was done by van Riesen et al [START_REF] Van Riesen | Dynamic Analysis and Control of an Antagonistically Actuated Tensegrity Mechanism[END_REF]. This mechanism uses a four-bar mechanism with crossed links and tension springs. Cables passing through the springs are used to actuate this mechanism. However, this analysis was done for a 2D structure. By introducing the cables in the passive configuration through the springs, the issue of active compliance could be addressed and when passing through a junction, these cables can be actuated thereby allowing the robot to choose the best path. The static and dynamic force analysis performed by van Riesen et al [START_REF] Van Riesen | Dynamic Analysis and Control of an Antagonistically Actuated Tensegrity Mechanism[END_REF] will be extended to the proposed 3D architecture to determine stable configurations and feasible workspaces. The key criteria for a piping inspection robot such as passing through curvilinear trajectories and tilt angles have been addressed in detail. The compliances discussed in this article facilitated in the modification of existing caterpillar robot of rigid type into a reconfigurable system that resembles an "Elephant trunk". For the passive configuration, a tensegrity mechanism with universal joint and three tension springs was proposed and for the active configuration, cables are added through the springs to control the same mechanism [START_REF] Yigit | Design and Modelling of a Cable-Driven Parallel-Series Hybrid Variable Stiffness Joint Mechanism for Robotics[END_REF]. The design and analysis of the first solution were studied in detail. The feasible workspace limits were calculated for the universal joint with respect to the tilt and azimuth angles. The results of this analysis helped in realizing a digital prototype of the entire robot in CATIA. The cable management is also addressed by letting the wires of actuators to pass through the holes of flange units. However, it is necessary to make an initial prototype of this robot to understand the configurations and look for alternate solutions if necessary.

In the future, workspace analysis of the universal joint with respect to azimuth angle and spring extension length will be carried out. This calculation will be essential to determine the optimal length and width of actuator units that will be used in the robot when they pass through pipe bends and elbows. A detailed analysis will be done on the second tensegrity structure for addressing the issue of active compliance. For the active tensegrity structures, based on the weight factors and cables, an analysis will be done to determine if a single or stacked model is required for the robot. The design and analysis of four-bar wheel mechanism will also be studied in detail through optimization techniques for determining the dimensions of bars, tension spring, and wheel.

Fig. 1 .

 1 Fig. 1. Schema of the existing bio-inspired piping inspection robot †

Fig. 2 .Fig. 3 .

 23 Fig. 2. Typical representation of passive (a) & active (b) compliances and tilt range (c) for a piping inspection robot

Fig. 5 .

 5 Fig. 5. Correlation of the proposed articulation unit to a parallel manipulator of type 3-SPS -U

Fig. 6 .

 6 Fig. 6. Representation of tilt (α) and azimuth (β) angles on the universal joint

Fig. 7 .

 7 Fig. 7. Plot of workspace for the universal joint with respect to Tilt(α) and Azimuth(β) angles

Fig. 8 .

 8 Fig. 8. Rendered model of the new "Elephant trunk" type bio-inspired robot


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

Silviu-Ioan Filip

Luc Forget
email: luc.forget@insa-lyon.fr

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

Table-Based versus Shift-And-Add constant multipliers for FPGAs

The multiplication by a constant is a frequently used operation. To implement it on Field Programmable Gate Arrays (FPGAs), the state of the art offers two completely different methods: one relying on bit shifts and additions/subtractions, and another one using look-up tables and additions. So far, it was unclear which method performs best for a given constant and input/output data types. The main contribution of this work is a thorough comparison of both methods in the main application contexts of constant multiplication: filters, signalprocessing transforms, and elementary functions. Most of the previous state of the art addresses multiplication by an integer constant. This work shows that, in most of these application contexts, a formulation of the problem as the multiplication by a real constant allows for more efficient architectures. Another contribution is a novel extension of the shift-and-add method to real constants. For that, an integer linear programming (ILP) formulation is proposed, which truncates each component in the shift-and-add network to a minimum necessary word size that is aligned with the approximation error of the coefficient. All methods are implemented within the open-source FloPoCo framework.

I. INTRODUCTION

When building hardware circuits, multiplication by a constant is a pervasive operation. For instance, the present work is motivated by two application domains: a/ the implementation of elementary functions, where range reduction involves constants such as log(2) and π, and b/ digital signal processing, where constant multiplication is the central operation of many filters and other kernels, such as Fourier transforms. For lowthroughput operation, one may use a standard multiplier in a sequential way and read the constant from a table. If a high throughput is needed, parallelism can be exploited by building specific multipliers specialized for each constant. The construction of such constant multipliers is the subject of the present article.

A general technique for implementing constant multiplication is to build an optimized shift-and-add tree. It has been widely studied for software, for ASICs, and for FPGAs. When targeting software, the function to optimize is the number of additions [START_REF] Dempster | Constant integer multiplication using minimum adders[END_REF]- [START_REF] Kumm | Optimal Constant Multiplication using Integer Linear Programming[END_REF]. When targeting ASICs or FPGAs, the functions to optimize are the overall area at the level of fulladders [START_REF] Dempster | Constant integer multiplication using minimum adders[END_REF], [START_REF] Johansson | A detailed complexity model for multiple constant multiplication and an algorithm to minimize the complexity[END_REF], [START_REF]Bit-Level Optimization of Shift-and-Add Based FIR Filters[END_REF] or even gates [START_REF] Aksoy | Optimization of area in digital FIR filters using gate-level metrics[END_REF] as well as the overall speed [START_REF] Gustafsson | Low-Complexity and High-Speed Constant Multiplications for Digital Filters Using Carry-Save Arithmetic[END_REF] or throughput [START_REF] Kumm | Pipelined Adder Graph Optimization for High Speed Multiple Constant Multiplication[END_REF]. These are only correlated to the number of additions and depth of the tree, as different additions in the tree will be of different sizes, hence different area and delay.

For FPGAs, whose elementary logic cells are based on lookup tables (LUTs) with 4 to 6 inputs depending on the FPGA family, there is another technique, based on table lookups and addition. It is called KCM after the name of its inventor, Ken Chapman [START_REF] Chapman | Fast integer multipliers fit in FPGAs (EDN 1993 design idea winner)[END_REF], and has been refined by Wirthlin [START_REF] Wirthlin | Constant coefficient multiplication using look-up tables[END_REF] and recently by Walters [START_REF] Walters | Reduced-area constant-coefficient and multiple-constant multipliers for Xilinx FPGAs with 6-input LUTs[END_REF].

Which method performs best strongly depends on the parameters of the problem: the input and output formats, and the constant itself. The two methods are reviewed in detail in Section II, the first objective of this work being too explicit which technique works best in which context. We are aware of only two earlier comparisons of KCM and shift-andadd [START_REF] Faust | Bit-parallel Multiple Constant Multiplication using Look-Up Tables on FPGA[END_REF], [START_REF] Kumm | FIR Filter Optimization for Video Processing on FPGAs[END_REF], both limited to the case of multiple constant multiplication (MCM) of small integer constants.

One may remark that most of the state of the art addresses the multiplication by an integer constant, but most applications require a multiplication by a real constant, such as the previous log [START_REF] Voronenko | Multiplierless Multiple Constant Multiplication[END_REF] or π examples. The mainstream approach for this is to round the constant C to a fixed-point value C which is a scaled integer, then use an optimized multiplier by this scaled integer and finally round the result of this multiplication to the result format. There, most of the literature assumes the same number of bits for the input, the constant, and the output. However, it is often not what applications require, as shown by the following two examples. 1/ In a floating-point exponential [START_REF] De Dinechin | Floating-point exponential functions for DSP-enabled FPGAs[END_REF], we need two constant multipliers: the first by 1/ log(2) whose input size is larger than its output size, followed by a multiplier of a small integer (a floating-point exponent) by log(2), to a high accuracy: e.g. in double-precision, 11 input bits and 68 output bits 1 . 2/ Accurate filter implementations [START_REF] Volkova | Towards hardware IIR filters computing just right: Direct form I case study[END_REF] are based on a sum of products by constants. The rounding errors of each multiplier add up. Therefore, "guard" bits must be added to the internal datapath to absorb these errors and their amplification by the filter. Here again, the output precision of each multiplier is systematically higher than that of the input.

Section III of this work therefore defines the problem of multiplying a fixed-point input by a real number with all the 1 With FloPoCo version 4.1.2, try the command flopoco FPExp we=11 wf=53 and look in the produced VHDL for the signal absKLog2.

2 m -4 -3 -2 -1 0 1 2 3 4 5 bit weight bit position 2 0 2 l -2 m 2 m-1 s -4 -3 -2 -1 0 1 2 3 4 5 2 0 2 l
unsigned case signed case Fig. 1. The bits of a fixed-point format, here (m, l) = (5, -4).

generality needed by applications. This enables us to refine both techniques (shift-and-add, and KCM) on this relevant problem. The evaluation in Section IV shows that up to 40% resources can be saved, compared to the previous three-step solution, for the same application-level accuracy. Section V concludes and lists future works.

Common definitions, notations and conventions

Throughout the paper we denote the constant with C and the input with X. The sign of the constant is trivial to manage. The input X can be either unsigned, or signed in two's complement. From the application point of view, both are equally relevant. For instance, signals are usually signed, while floating-point mantissas are usually unsigned. Therefore, we must consider both. The signedness of the input has some architectural impact (need for sign extensions in some cases). However, it is always possible to minimize the corresponding overhead, using techniques exposed in the sequel. Thus, in practice, the costs of a signed and unsigned multiplier are very close. Therefore, for clarity, we chose to report only results obtained with signed multipliers.

Integers being a special case of fixed-point numbers, we use the following definition (inspired by the VHDL sfixed standard) for fixed-point formats. As illustrated by Fig. 1, a fixed-point format is fully specified by two integers (m, l) that denote the positions of the most and least significant bits (MSB and LSB) respectively. Both m and l can be negative if the format includes fractional bits. The weight of the bit at position i is always 2 i , except for the bit at position m if the format is signed: its weight is -2 m due to two's complement representation. The LSB position l denotes the absolute precision of the format. The MSB position m denotes its range. The total word size is m -l + 1. Other notations used in this article are gathered in Table I.

II. STATE OF THE ART IN INTEGER SINGLE-CONSTANT

MULTIPLICATION

In this section we review the major work that has been done regarding integer constant multiplication over the years.

A. Shift-and-add multipliers

Most of the literature addresses single-constant multiplication (SCM) by a combination of shift-and-add operations. For instance, the multiplication by 17 can be computed as 17X = X + 2 (one addition), then compute 2228241X = (T • 2 17 + T ) (another addition).

Given a constant C of w C bits, the problem of finding an implementation in a minimal number of additions is an NP-complete optimization problem [START_REF] Cappello | Some Complexity Issues in Digital Signal Processing[END_REF]. Booth recoding of the constant naturally leads to an implementation in w C /3 adders, but this is not optimal: the optimal number of additions is asymptotically sublinear in w C [START_REF] Dimitrov | Multiplication by a constant is sublinear[END_REF]. Methods based on exhaustive enumerations of adder graphs have shown [START_REF] Dempster | Constant integer multiplication using minimum adders[END_REF], [START_REF] Gustafsson | Simplified Design of Constant Coefficient Multipliers[END_REF] that not more than 5 adders are sufficient to realize SCM with any 19-bit number. Another optimal approach based on an exhaustive search indicates that 6 additions are sufficient for integer constants up to 32 bits [START_REF] Thong | An optimal and practical approach to single constant multiplication[END_REF]. This optimal number of adders will be denoted as the "adder complexity" of the constant. The trend of the adder complexity for constants up to 19 bits is shown in Fig. 2. Beyond 32 bits, good heuristics exist which match the optimal complexity or typically require not more than one additional adder [START_REF] Voronenko | Multiplierless Multiple Constant Multiplication[END_REF].

So far we have evaluated the cost in terms of number of additions. This is indeed the relevant metric for software. However, in hardware, not all adders have the same cost [START_REF] Dempster | Constant integer multiplication using minimum adders[END_REF]. Firstly, the intermediate results grow in the adder graph from input to outputs, and so do the adder sizes. Secondly, in a shiftand-add operation with a left shift of s bits, the s lower bits can be simply transferred from input to output as long as they are not negated (like in subtractions). If the shift is large enough compared to the data word size, the addition corresponds to a concatenation, at no cost. For these reasons, the relevant cost metric in hardware is the number of full adders [START_REF] Dempster | Constant integer multiplication using minimum adders[END_REF], which we

C

a (real or integer) constant X fixed-point input to a constant multiplier w C ∈ N word size of the integer constant in bits m X ∈ Z weight of the most significant bit of the input fixed-point format l X ∈ Z weight of the least significant bit of the input fixed-point format w X ∈ N size of the fixed-point input in bits:

w X = m X -l X + 1 R, m R , l R , w R the same, for the fixed-point output R α ∈ N number of inputs of an FPGA's architectural LUT •(x)
rounding to the nearest integer (i.e., •(x

) = x + 1/2 ) X Look-Up Table / w X / w X + w C CX X = x 0 x 1 x 2 x 3 x 4 x 5 / α LUT LUT LUT LUT LUT LUT LUT LUT LUT LUT LUT / α CX =
(bit-level view) Fig. 3. Storing in a look-up table the product by C of all the possible values of X (w X = α = 6, w C = 5).

will also denote as bit-level cost. Two shift-and-add trees with the same number of adders may have different bit-level costs, and algorithms that optimize for this bit-level cost have also been extensively studied [START_REF] Dempster | Constant integer multiplication using minimum adders[END_REF], [START_REF] Johansson | A detailed complexity model for multiple constant multiplication and an algorithm to minimize the complexity[END_REF]- [START_REF] Aksoy | Optimization of area in digital FIR filters using gate-level metrics[END_REF].

All this is relevant both for ASIC synthesis and for FPGA implementations, since integer addition is efficiently supported by the hardware structure of most FPGAs: the full-adder cost can directly be translated to the number of LUTs. Some FPGAs support ternary adders at almost the same cost as binary adders. Shift-and-add graphs based on such ternary adders have also been studied [START_REF] Kumm | Multiple Constant Multiplication with Ternary Adders[END_REF], [START_REF] Kumm | Optimal Single Constant Multiplication using Ternary Adders[END_REF].

B. KCM multipliers

Most mainstream FPGAs are based on small look-up tables (LUTs). Let α denote the number of inputs of the architectural LUT of the target FPGA. For instance, on current FPGAs, α ranges from 4 to 6. Specific table-and-addition methods exploiting these LUTs have been developed. The simplest technique is, for small values of w X , to pre-compute and tabulate the product of the constant by all the possible values of the input. At run-time, the SCM operation resumes to a table read, and for input sizes up to α, the cost is one FPGA LUT per output bit, as illustrated by Fig. 3.

For larger input sizes, the complexity of this naive approach becomes exponential with the input size w X , but a technique introduced by Chapman [START_REF] Chapman | Fast integer multipliers fit in FPGAs (EDN 1993 design idea winner)[END_REF] allows for architectures whose cost is linear with w X . The principle is to decompose the input X in sub-words of α bits (or to view it as a radix-2 α number, hexadecimal being a popular example when α = 4) :

X = w X α i=0 X i • 2 αi
(see Fig. 4).

Now the product becomes CX = CX i • 2 αi and we have a sum of (shifted) products CX i , each of which can be computed by a look-up table with α input bits (back to Fig. 3). The cost of each table is α + w C FPGA LUTs.

There are quite a few ways of implementing the summation, from a simple rake to a compressor tree. As a rule of thumb, the area cost of the summation is comparable to that of the tables. Wirthlin [START_REF] Wirthlin | Constant coefficient multiplication using look-up tables[END_REF] then Walters [START_REF] Walters | Reduced-area constant-coefficient and multiple-constant multipliers for Xilinx FPGAs with 6-input LUTs[END_REF] showed that in a rake, tables and additions could be merged, under the conditions that the tables input only α -1 bits (i.e., using a radix-2 α-1 decomposition of the input), which means more tables. Overall, this technique reduces the area by about one third, but due to the rake structure the latency is larger than with tree summations [START_REF] Walters | Reduced-area constant-coefficient and multiple-constant multipliers for Xilinx FPGAs with 6-input LUTs[END_REF].

CX 0 xxxxxxxxxxxxxxxxxxx +2 α CX 3 xxxxxxxxxxxxxxxxxxx +2 2α CX 3 xxxxxxxxxxxxxxxxxxx = CX xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx α bits (a) Aligment of the partial products X = x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17 α bits + Look-Up Table X 0 / α / α + w C CX 0 Look-Up Table X 1 / α / α + w C CX 1 α Look-Up Table X 2 / α / α + w C CX 2 2α / w C + w X CX (b) Architecture

C. Comparison and discussion

To sum up, the cost of KCM depends on the size of the constant but not2 on its "adder complexity" as defined above. Conversely, the cost of shift-and-add mostly depends on the complexity of the constant. At a first approximation, the bitlevel cost should be linear in w X . However, the addition sizing at the bit level strongly depends on w X . To take an extreme example, multiplying a w X = 4-bit unsigned number by 2228241 has cost zero, since all the additions can be done via concatenation. Multiplying the same constant by a w X = 16bit unsigned number costs one single 16-bit addition.

For all these reasons, for a given constant and a given w X , there is probably no best way to select the best technique other than "try both, evaluate their costs, keep the best". The good news is that, although there is no simple closed formula giving the cost of a solution, it is easy to program in both cases very accurate bit-level cost models: such programs input C, w X and the signedness of the input, and can predict the full-adder cost (or LUT cost) very accurately.

Work is therefore in progress for integrating the state of the art for integer SCM in a single FloPoCo operator that performs this design-space exploration. This also includes SCM based on ternary adders [START_REF] Kumm | Optimal Single Constant Multiplication using Ternary Adders[END_REF].

III. MULTIPLICATION BY A REAL CONSTANT So far we have discussed multiplication of an integer input

X by an integer constant C (possibly with some fixed-point scaling). The result is then a number R of size w R = w C +w X bits. However, most applications actually involve multiplications by a real constant, such as the previous log(2) or π. These are irrational constants with an infinite number of bits: they must be rounded first to a finite-size constant C of size w C . If the precision w R of the desired result is the same as the precision of the input: w R = w X , then one will typically round the constant to w C = w R = w X . One may then use one of the previous fixed-point techniques. However, the result is a 2w R -bit number, and has to be rounded again. This is inefficient for two reasons. Firstly, there are two rounding errors in this process (rounding the constant, then rounding the product). Secondly, half of the computed bits are discarded in the final rounding.

A. Problem formulation

In this work, we define the single real constant multiplication (SRCM) operation as follows. Given a maximum error bound > 0, an input fix-point format (m X , l X ), an output fix-point format (m R , l R ), and a real constant C, an SRCM operator computes for each fix-point input X a fix-point output R such that

R = X × C + (1)
with | | < . The maximum absolute error bound cannot, by definition, be smaller than 2 l R -1 (one half ulp of the result format): this corresponds to rounding to the nearest number in the result format. The cost of achieving this accuracy depends on the constant, and can be arbitrarily large 3 [START_REF] Brisebarre | Integer and floatingpoint constant multipliers for FPGAs[END_REF]. However, for small input sizes, the plain tabulation offers correct rounding as shown in Fig. 5. On FPGAs, this is perfectly acceptable for input sizes up to w c = α + 2, or 8 bits in current technology. A correctly rounded 8-bit in, 8-bit out multiplier will cost 32 LUTs and have unit delay.

Fixing the error bound to 2 l R corresponds to what is commonly known as faithful rounding: the operator will return one of the two fixed-point numbers surrounding the exact (unrounded) result. Besides, as the constraint | | < is strict, if the exact product happens to be representable in the result format, then the operator will return this exact result. 3 Consider for instance the multiplication of 8-bit integers by the constant C = 1.97058823529412, with the result rounded to an integer (l R = 0). For the value X = 17, the correctly rounded result is •(CX) = 34. However, the value of in this case is = 34 -CX = 0.49999999999996: it is very close to a half-ulp -this example was constructed for this purpose. This makes it tricky to compute the correct rounding to the nearest. For illustration, if in the process of building a constant multiplier we use a rounded down value C of the constant, for instance to the decimal value C = 1.97 (with an error smaller than 6 • 10 -4 ), or to the nearest 8-bit number, or even to the nearest 32-bit number, or even to C = 1.9705882352941 (removing only the last decimal digit of C), then the computation •( CX) will yield the wrong value (33 instead of 34). Given a constant, it is a non-trivial problem to determine the accuracy of the intermediate computations that will guarantee correct rounding to the nearest for all the possible inputs. It has been solved elsewhere [START_REF] Brisebarre | Integer and floatingpoint constant multipliers for FPGAs[END_REF].

X Look-Up Table / (m X , l X ) / (m R , l R )
•(CX) Fig. 5. Storing in a look-up table the rounded product by C of all the possible values of X.

On FPGAs, we have the choice of the formats, especially if the result of the multiplier is an intermediate data hidden inside a filter or a function. In this case, it is in general more economical to achieve the same accuracy 2 l using faithful rounding to a format of LSB weight 2 l+1 than using correct rounding to a format of LSB 2 l .

For this reason, the remainder of this article focuses on faithful rounding.

B. Naive three-step approach

It is always possible to achieve faithful rounding using the naive three-step technique introduced above, with the following error decomposition (given here first in the case of unsigned fixed-point inputs, such that 0 ≤

X < 2 m X +1 ). Noting • l (x) = 2 -l • •(2 l x), let C = • l R -m X -1 (C) hence C = C -C ≤ 2 l R -m X -2 (2) R = • l R ( C × X) hence × = R -C × X ≤ 2 l R -1 (3)
Then, the total absolute error due to the operator can be described as

= R -CX (4) = R -CX + CX -CX (5) = × + C X (6)
The triangle inequality yields

| | ≤ | × | + | C | • |X|, and from the bound on the input 0 ≤ X < 2 m X +1 we conclude that | | < 2 l R , hence R is CX faithfully rounded.
The extension to signed input is straightforward, with one subtlety: as m x is the weight of the sign bit, we have -2 m X ≤ X < 2 m X . There is the opportunity to save one bit in the rounding of the constant, using

C = • l R -m X (C), but only if the inequality C = C -C ≤ 2 l R -m X -1 is strict, to achieve a strict inequality | | < 2 l R
. This is the most common case, but it has to be checked nevertheless.

C. Fix×real constant multiplication using KCM

This operator has been described in detail in [START_REF] Volkova | Towards hardware IIR filters computing just right: Direct form I case study[END_REF]. It is illustrated in Figs. 56. It is radically different from the threestep approach, since there is no rounding of C to some C: the exact, real value of C is used to compute each table entry. Each entry is rounded directly to the target accuracy that will ensure faithful rounding, defined by a number of guard bits g whose value is computed as follows. Each table entails a rounding

T2 ≈ 2 2α+l CX2 xxxxxxxxxxxxxxxxxxxxxxxxxx... T1 ≈ 2 α+l CX1 xxxxxxxxxxxxxxxxxxxx... T0 ≈ 2 l CX0 xxxxxxxxxxxxxx... 2 l R -g α bits α bits (a) Aligment of the partial products 2 -l X = x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17 T 2 X 2 T 1 X 1 T 0 X 0 + / q + g t 2 / q -α + g t 1 / q -2α + g t 0 Final rounding T i stores • l R -g (CX i ) / q + g Q / q R ≈ CX (b) Architecture
Fig. 6. FixRealKCM with an 18-bit input X split in 3 chunks of 6 bits.

error of at most 2 l R -g-1 (correct rounding of each table entry), so the overall rounding error is w X /α • 2 l R -g-1 . Hence, g has to be selected such that w X /α • 2 l R -g-1 < 2 l R -1 holds which is given for any g > log 2 ( w X /α ). The "Final rounding" box in Fig. 6(b) is then a simple truncation, provided that a rounding bit 2 l R -1 has been added to all the entries of one of the tables. Then this truncation becomes the rounding to the nearest ( x+1/2 = •(x)) of the intermediate sum Q with its g guard bits to the final format, with an error smaller than 2 l R -1 . The sum of all these errors ensures faithful rounding.

The original integer KCM could be viewed as a special case when C is an integer. In this case, the tables contain LSB zeroes that the synthesis tools will in principle optimize out. However, it should still be handled as a special case, in particular because the integer KCM is exact and therefore does not need the g guard bits and the rounding bit.

D. Fix×real constant multiplication using shift-and-add

In contrast to the KCM case of the previous section, we have to find a proper rounding of C to some C. However, we do not have to decompose the error as described in Section III-B. There is a large range from which valid coefficients can be selected. Taking the error definition

= XC -X C = X∆C < X max ∆C max = (7)
with |X| < 2 m X +1 in the unsigned case and |X| < 2 m X in the signed case we get

∆C max = /2 m X +1 for X unsigned /2 m X for X signed (8)
Clearly, there will be one fixed-point constant C minw with minimal word size w C,min that will fulfill the above condition. As the shift-and-add constant multiplication strongly depends on the constant, the idea here is to take a slightly larger coefficient word size w C,min +q and to evaluate the complexity of all the fixed-point coefficients that lie in the valid range C -∆C max < C < C + ∆C max . We then choose the one with least complexity. This is illustrated in Fig. 7. The procedure follows a concept previously presented as additionaware quantization [START_REF] Gustafsson | Addition Aware Quantization for Low Complexity and High Precision Constant Multiplication[END_REF]. However, in our case, each valid fixed-point coefficient is not only defined by its complexity, but also gives a remaining error margin that can be used for truncations in the shift-and-add computations. Hence, C candidates close to C result in a small C allowing a larger error for truncations in the multiplier × and vice versa. The multiplier error × can be tuned by a novel truncation method introduced in Section III-E. An example for the constant multiplication with C = π/4 with a maximum overall error of = 2 -25 when evaluating 2 q = 16 different fixed-point coefficients is given in Table II. The table shows the different fixed-point coefficients, their error distributions, the number of adders (#add) obtained by the RPAG algorithm [START_REF] Kumm | Pipelined Adder Graph Optimization for High Speed Multiple Constant Multiplication[END_REF] as well as the number of full adders (#FA) before and after the truncation (#FA trunc). The coefficient for k = -1 is the closest to C and provides the smallest | C | which allows the highest | × | for truncating the multiplier. However, the coefficient that can be realized with the minimum number of adders is found for k = 3. It also requires the least number of full adders before and after the truncation. Note also that it is a better choice compared to the minimum word size coefficient which is obtained for k = 5.

E. Truncated SCM

The goal of truncation is to minimize the required number of full adders in an SCM instance with a given adder graph solution, such that the output error is upper bounded by a maximum tolerable value × .

To do so, we have devised a method that models the problem using integer linear programming (ILP). The objective is the maximization of the number of FAs saved by allowing truncation. It is given in ILP Formulation 1. The complexity model used for counting the FAs is based on [START_REF] Johansson | A detailed complexity model for multiple constant multiplication and an algorithm to minimize the complexity[END_REF], which is extended to also take truncation into account. Note that the method works for generic adder graphs which includes multiple constant multiplication (MCM) or even constant matrix multiplications (CMM) operations based on shift-and-add networks.

The binary variables t a,w are used to encode the position where truncation takes place on each edge a, which is why there is only one active t a,w per edge (constraint C1). Every value a represents an upper bound on the error propagated in the adder graph until edge a due to truncation, before the shift by s a bits is applied. It is defined by constraint C2 as the maximum between the sum of the appropriately shifted error bounds on the input edges of the adder with output edge a (denoted with a and ar for the left and right operand edges a and a r ) and the truncation error et a on the output a. If a is not the output edge of any adder (i.e., it starts from the input X), then a = ar = 0 and a = et a . At the end of the error propagation, the (shifted) error bounds on the output edges are bounded by × (constraint C3).

The g a variables defined by constraint C4 correspond to the number of FAs that can be saved in the adder graph due to truncation for each adder/subtractor. These values are computed with respect to a fully naive implementation in which no savings due to shifts and truncations are considered. They are the equivalents of the cases exemplified in [START_REF] Johansson | A detailed complexity model for multiple constant multiplication and an algorithm to minimize the complexity[END_REF]Sec. 2].

Considering that only odd fundamentals are computed at each adder node with output edge a, there are two possibilities for the values of the shifts s and s r : (a) s ≥ 0, s r = 0 or (b) s = s r < 0. Both (a) and (b) can be further decomposed based on the signs of the left and right operands (sign(a ), sign(a r )) ∈ {(1, 1), (-1, 1), (1, -1)} (the case where both operands are negative does not appear in common adder graphs as it is more hardware demanding to compute).

If we are in (a) with (sign(a ), sign(a r )) ∈ {(1, 1), (-1, 1)} then one can save in terms of FAs the maximum between the sums of the shifted and truncated bits on each of the two operands (the first case in constraint C4). This is exemplified (without truncations) in [6, Fig. 5 (a)-(b)]. If on the other hand, sign(a r ) = -1, then the most FAs we can save are the number of truncated bits on the right operand (the second case in C4). An example (without truncation) is [6, Fig. 5 (c)]. For situation (b), which seldom occurs in practice, we make the same simplifying assumption as in [START_REF] Johansson | A detailed complexity model for multiple constant multiplication and an algorithm to minimize the complexity[END_REF]Fig. 6] and consider that no FAs are saved (third case of constraint C4).

ILP
The gain in number of FAs is essentially limited by how tight the error bounds in the C2 constraints will be. Nevertheless, the results we obtain in practice compare well with other approaches found in the literature. Take for instance the heuristic pattern modification technique for truncated MCM in the context of finite impulse response filter implementations [START_REF] Guo | Truncated MCM using pattern modification for FIR filter implementation[END_REF] used on the adder graph from Fig. 8. Using their algorithm with × = 2 10 , the reduction in terms of FAs with respect to the fully naive implementation is 45, whereas with our ILP model we obtain a slightly better reduction of 46 FAs.

IV. RESULTS

Several synthesis experiments have been performed to compare the state of the art using fixed-point by fixedpoint constant multiplication (FixFix) as described in Section III-B as well as the fixed-point by real constant multiplication (FixReal) using the KCM and the shift-and-add techniques described in Section III. All synthesis results were obtained using Vivado 2018.2 targeting a Xilinx Kintex7 FPGA (7k70tfbv484-3) with timing constraints for a 10 ns clock period. Table III summarizes the synthesis results.

For the FixFix cases, we used the integer constants approximating π/4 from [START_REF] Walters | Reduced-area constant-coefficient and multiple-constant multipliers for Xilinx FPGAs with 6-input LUTs[END_REF], while for the FixReal case we used the actual real number. Note that some of the integer numbers from [START_REF] Walters | Reduced-area constant-coefficient and multiple-constant multipliers for Xilinx FPGAs with 6-input LUTs[END_REF] are not exactly the rounding of π/4 to the nearest number on w C bits but the closest odd number, "to avoid obvious optimizations" [START_REF] Walters | Reduced-area constant-coefficient and multiple-constant multipliers for Xilinx FPGAs with 6-input LUTs[END_REF]. From an application context this choice is doubly disputable since 1/ optimizations are welcome and 2/ it increases the error. We nevertheless follow it here for the purpose of comparison with [START_REF] Walters | Reduced-area constant-coefficient and multiple-constant multipliers for Xilinx FPGAs with 6-input LUTs[END_REF].

Column 'FixFixKCM' describes the results for the latest work on KCM using fixed point numbers by Walters as reported in [START_REF] Walters | Reduced-area constant-coefficient and multiple-constant multipliers for Xilinx FPGAs with 6-input LUTs[END_REF]. Column 'FixRealKCM' shows results from recent work by Volkova et al. [START_REF] Volkova | Towards hardware IIR filters computing just right: Direct form I case study[END_REF]. The shift-and-add results are given in column 'FixFixShiftAdd' by using the RPAG algorithm [START_REF] Kumm | Pipelined Adder Graph Optimization for High Speed Multiple Constant Multiplication[END_REF] for obtaining the adder graphs for the same integers as in [START_REF] Walters | Reduced-area constant-coefficient and multiple-constant multipliers for Xilinx FPGAs with 6-input LUTs[END_REF]. Finally, column 'FixRealShiftAdd' presents results obtained from the method introduced in Section III-D.

Two important results can be observed from this experiment. First, the common approach of just quantizing the constant shows a much higher resource utilization than considering the constant as a real number. Second, the KCM approaches always outperform the shift-and-add methods, independent of the FixFix or FixReal case. This is confirmed by Table IV which compares the two FixReal variants on the multipliers needed inside a floatingpoint exponential [START_REF] De Dinechin | Floating-point exponential functions for DSP-enabled FPGAs[END_REF]. No results could be obtained for the high precision log(2) constant using FixRealShiftAdd as the current RPAG implementation is limited to 64 bits.

It is also confirmed by Figure 9 which compares the variation of the area (in LUTs) of the operators with input and output size. One can observe that the plot for FixRealKCM is smoother: for FixRealShiftAdd, adding one bit may introduce subgraph sharing opportunities that reduce the total size. A general conclusion of this study is that KCM is more efficient, even for large sizes. This can be understood considering the large LUTs of modern FPGAs. However, it was not expected, as previous work showed that the shift-and-add approach was better for input word sizes larger than 8 bit in the case of multiple constant multiplication [START_REF] Kumm | FIR Filter Optimization for Video Processing on FPGAs[END_REF]. This can be explained by the fact that in this case, much more sharing is possible when multiplying with several constants. Besides, in this case, the truncation method introduced in Section III-E will help.

However, there exist combinations of constants and input sizes for which the shift-and-add method wins. The real conclusion is therefore that the best way to address this comparison is on a case-by-case basis, using a versatile tool that tracks the state of the art in both methods, provides the same general interface to them (including the option to input signed or unsigned numbers), and performs the comparison using accurate cost models. The present work introduces such a tool in the FloPoCo framework.

A shortcoming of the current truncation optimization phase from Section III-E is that it assumes a given adder graph. The next step is to investigate if the choice of adder graph can be directly integrated in the optimization phase effectively, potentially offering greater savings in terms of adder cost.

Fig. 4 .

 4 Fig.4. KCM multiplication of a 18-bit constant C by an 18-bit input X split in 3 chunks of α =6 bits. Each subproduct CX i is of size 24 bits.

CFig. 7 .

 7 Fig. 7. Possible values of fixed-point coefficient C.

Fig. 8 .

 8 Fig. 8. Adder graph used for the MCM implementation with constants 2458, 3206 and 3907 from [25, Sec. II-B].

Fig. 9 .

 9 Fig. 9. Area of FixRealKCM(left) and FixRealShiftAdd (right) for log(2)

  4 X, where the multiplication by 2 4 is a bit shift that (in hardware) costs nothing. The multiplication by 2228241 can be implemented in two additions only if one remarks that 2228241 = 17 • 2 17 + 17: first compute T = 17X

		6
	Adder complexity	2 4			number of adders (avg.) number of adders (max.)
		0	0	2	4	6	8 10 12 14 16 18 20
						Coefficient word size
	Fig. 2. Number of adders versus word size for optimal-adder adder graphs.

TABLE II EXAMPLE

 II COEFFICIENTS C FOR C = π/4 FOR = 2 -25 2.98 • 10 -8 ,

	THEIR CORRESPONDING ERROR DISTRIBUTION AND FULL ADDER COST
		(#FA) BEFORE AND AFTER TRUNCATION OF THE ADDER GRAPH
	k	C	| C |	| × |	#add #FA #FA
						trunc
	-8	210828707/2 28 2.65 • 10 -8	3.22 • 10 -9	7	226 175
	-7	52707177/2 26 2.28 • 10 -8	6.95 • 10 -9	8	237 185
	-6	210828709/2 28 1.91 • 10 -8	1.06 • 10 -8	6	210 152
	-5	105414355/2 27 1.53 • 10 -8	1.44 • 10 -8	7	229 174
	-4	210828711/2 28 1.16 • 10 -8	1.81 • 10 -8	7	238 174
	-3	26353589/2 25 7.94 • 10 -9	2.18 • 10 -8	6	182 151
	-2	210828713/2 28 4.22 • 10 -9	2.55 • 10 -8	7	225 165
	-1	105414357/2 27 4.96 • 10 -10 2.93 • 10 -8	7	225 167
	0	210828715/2 28 3.22 • 10 -9	2.65 • 10 -8	6	197 141
	1	52707179/2 26 6.95 • 10 -9	2.28 • 10 -8	7	218 173
	2	210828717/2 28 1.06 • 10 -8	1.91 • 10 -8	6	204 132
	3	105414359/2 27 1.44 • 10 -8	1.53 • 10 -8	5	156 125
	4	210828719/2 28 1.81 • 10 -8	1.16 • 10 -8	6	182 151
	5	13176795/2 24 2.18 • 10 -8	7.94 • 10 -9	6	176 136
	6	210828721/2 28 2.55 • 10 -8	4.22 • 10 -9	6	194 148
	7	105414361/2 27 2.93 • 10 -8	4.96•10 -10	7	230 190

  Formulation 1 ILP formulation for the truncated SCM/MCM/CMM problem for a given adder graph.

					max	g a
					a∈N A
	subject to
	Wa-1
	C1:		t a,w = 1, ∀a ∈ E
	w=0
	C2: a = max (2 sa	a + 2 sa r ar , et a ) , ∀a ∈ E
	C3: 2 sa	a ≤ × , ∀a ∈ O
	C4: g a =	       	max (t a + s a , t ar + s ar ) if s a ≥ 0 and sign(a r ) = 1 t ar if s a ≥ 0 and	,
			      	0	sign(a r ) = -1 otherwise
	∀a ∈ N A
	where t a,w ∈ {0, 1}, a ∈ {0, 1, . . . , 2 Wa -1},
					Wa-1
				et a =	(2 w -1)t a,w ,
					w=0
	and				Wa-1
				t a =	wt a,w .
					w=0
	Constant				Meaning
	W a ∈ N				Word size on the edge a
	×				Maximum tolerable error
	s a				Bits shifted on edge a
	a and a r				Input edges for adder with output
					edge a
	E				Set of edges
	O ⊆ E				Set of output edges
	N A ⊆ E				Set containing one output edge for
					each adder in the graph
	Variable				Meaning
	t a,w ∈ {0, 1}		true, if edge a is truncated at
					position w
	a ∈ N				Maximum error on edge a after
					truncation

Of course, synthesis tools will optimize out the table content when they find opportunities to do so, which happens e.g. for trivial constants (powers of two), but also for periodic constants[START_REF] De Dinechin | Multiplication by rational constants[END_REF].