2024
Hilaire, T.
From filters/controllers to code – Contributions to Fixed-Point arithmetic implementations under accuracy constraint Miscellaneous
Habilitation à Diriger des Recherches (HDR) – Sorbonne Université, 2024.
@misc{Hila24a,
title = {From filters/controllers to code – Contributions to Fixed-Point arithmetic implementations under accuracy constraint},
author = {T. Hilaire},
year = {2024},
date = {2024-01-01},
school = {Sorbonne Université},
howpublished = {Habilitation à Diriger des Recherches (HDR) – Sorbonne Université},
keywords = {},
pubstate = {published},
tppubtype = {misc}
}
2023
Ferro, Quentin; Graillat, Stef; Hilaire, Thibault; Jézéquel, Fabienne
Precision Auto-Tuning of High-Performance Neural Networks Proceedings Article
In: European Conference on Numerical Mathematics and Advanced Applications (ENUMATH), minisymposium ''Mixed Precision Computations in Theory and Practice'', Lisbon, Portugal, 2023.
@inproceedings{Ferr23b,
title = {Precision Auto-Tuning of High-Performance Neural Networks},
author = {Quentin Ferro and Stef Graillat and Thibault Hilaire and Fabienne Jézéquel},
year = {2023},
date = {2023-09-01},
booktitle = {European Conference on Numerical Mathematics and Advanced Applications (ENUMATH), minisymposium ''Mixed Precision Computations in Theory and Practice''},
address = {Lisbon, Portugal},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Ferro, Quentin; Graillat, Stef; Hilaire, Thibault; Jézéquel, Fabienne
Precision auto-tuning using stochastic arithmetic Proceedings Article
In: 10th International Congress on Industrial and Applied Mathematics (ICIAM), minisymposium ``Exploring Arithmetic and Data Representation Beyond the Standard in HPC'', Tokyo, Japan, 2023.
@inproceedings{Ferr23a,
title = {Precision auto-tuning using stochastic arithmetic},
author = {Quentin Ferro and Stef Graillat and Thibault Hilaire and Fabienne Jézéquel},
year = {2023},
date = {2023-08-01},
booktitle = {10th International Congress on Industrial and Applied Mathematics (ICIAM), minisymposium ``Exploring Arithmetic and Data Representation Beyond the Standard in HPC''},
address = {Tokyo, Japan},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
2022
Ferro, Quentin; Graillat, Stef; Hilaire, T.; Jézéquel, Fabienne; Lewandowski, Basile
Neural Network Precision Tuning Using Stochastic Arithmetic Proceedings Article
In: NSV'22, 15th International Workshop on Numerical Software Verification,, Haifa, Israel, 2022.
@inproceedings{Ferr22,
title = {Neural Network Precision Tuning Using Stochastic Arithmetic},
author = {Quentin Ferro and Stef Graillat and T. Hilaire and Fabienne Jézéquel and Basile Lewandowski},
url = {https://hal.science/hal-03682645},
year = {2022},
date = {2022-08-01},
booktitle = {NSV'22, 15th International Workshop on Numerical Software Verification,},
address = {Haifa, Israel},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
2021
Jézéquel, F.; Hoseininasab, S.; Hilaire, T.
Numerical validation of half precision simulations Proceedings Article
In: 9th World Conference on Information Systems and Technologies, WorldCist'21, 2021.
@inproceedings{Jeze21,
title = {Numerical validation of half precision simulations},
author = {F. Jézéquel and S. Hoseininasab and T. Hilaire},
year = {2021},
date = {2021-04-01},
booktitle = {9th World Conference on Information Systems and Technologies, WorldCist'21},
abstract = {In this article, we show how to control the numerical quality of half precision computations using stochastic arithmetic. The CADNA library that is used to estimate rounding errors and detect numerical instabilities in floating-point codes has been improved and extended to support half precision. A performance gain up to a factor 20 has been observed w.r.t. accuracy estimation in arbitrary precision. Furthermore we present how to generate codes mixing half, single, and double precision with a requested accuracy on results providing a user-defined numerical quality of the code. Control of robustness and floating-point auto-tuning taking into account half precision have been successfully performed on various numerical simulations, in particular a control application.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
In this article, we show how to control the numerical quality of half precision computations using stochastic arithmetic. The CADNA library that is used to estimate rounding errors and detect numerical instabilities in floating-point codes has been improved and extended to support half precision. A performance gain up to a factor 20 has been observed w.r.t. accuracy estimation in arbitrary precision. Furthermore we present how to generate codes mixing half, single, and double precision with a requested accuracy on results providing a user-defined numerical quality of the code. Control of robustness and floating-point auto-tuning taking into account half precision have been successfully performed on various numerical simulations, in particular a control application.
2020
Boldo, S.; Gallois-Wong, D.; Hilaire, T.
A Correctly-Rounded Fixed-Point-Arithmetic Dot-Product Algorithm Proceedings Article
In: 2020 IEEE 27th Symposium on Computer Arithmetic (ARITH), pp. 9-16, 2020.
@inproceedings{Bold20,
title = {A Correctly-Rounded Fixed-Point-Arithmetic Dot-Product Algorithm},
author = {S. Boldo and D. Gallois-Wong and T. Hilaire},
doi = {10.1109/ARITH48897.2020.00011},
year = {2020},
date = {2020-01-01},
booktitle = {2020 IEEE 27th Symposium on Computer Arithmetic (ARITH)},
pages = {9-16},
abstract = {Dot products (also called sums of products) are ubiquitous in matrix computations, for instance in signal processing. We are especially interested in digital filters, where they are the core operation. We therefore focus on fixed-point arithmetic, used in embedded systems for time and energy efficiency. Common dot product algorithms ensure faithful rounding. For the sake of accuracy and reproducibility, we want to ensure correct rounding. This article describes an algorithm that computes a correctly-rounded sum of products from inputs whose format is known in advance. This algorithm relies on odd rounding (that is easily implemented in hardware) and comes with a careful proof and some cost analysis.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Dot products (also called sums of products) are ubiquitous in matrix computations, for instance in signal processing. We are especially interested in digital filters, where they are the core operation. We therefore focus on fixed-point arithmetic, used in embedded systems for time and energy efficiency. Common dot product algorithms ensure faithful rounding. For the sake of accuracy and reproducibility, we want to ensure correct rounding. This article describes an algorithm that computes a correctly-rounded sum of products from inputs whose format is known in advance. This algorithm relies on odd rounding (that is easily implemented in hardware) and comes with a careful proof and some cost analysis.
Volkova, A.; Hilaire, T.; Lauter, C.
Arithmetic Approaches for Rigorous Design of Reliable Fixed-Point LTI Filters Journal Article
In: IEEE Transactions on Computers, vol. 69, no. 4, pp. 489-504, 2020, ISSN: 2326-3814.
@article{Volk19a,
title = {Arithmetic Approaches for Rigorous Design of Reliable Fixed-Point LTI Filters},
author = {A. Volkova and T. Hilaire and C. Lauter},
doi = {10.1109/TC.2019.2950658},
issn = {2326-3814},
year = {2020},
date = {2020-01-01},
journal = {IEEE Transactions on Computers},
volume = {69},
number = {4},
pages = {489-504},
abstract = {In this paper we target the Fixed-Point (FxP) implementation of Linear Time-Invariant (LTI) filters evaluated with state-space equations. We assume that wordlengths are fixed and that our goal is to determine binary point positions that guarantee the absence of overflows while maximizing accuracy. We provide a model for the worst-case error analysis of FxP filters that gives tight bounds on the output error. Then we develop an algorithm for the determination of binary point positions that takes rounding errors and their amplification fully into account. The proposed techniques are rigorous, i.e., based on proofs, and no simulations are ever used. In practice, Floating-Point (FP) errors that occur in the implementation of FxP design routines can lead to overestimation/underestimation of resulting parameters. Thus, along with FxP analysis of digital filters, we provide FP analysis of our filter design algorithms. In particular, the core measure in our approach, Worst-Case Peak Gain, is defined as an infinite sum and has matrix powers in it. We provide fine-grained FP error analysis of its evaluation and develop multiple precision algorithms that dynamically adapt their internal precision to satisfy an a priori absolute error bound. Our techniques on multiple precision matrix algorithms, such as eigendecomposition, are of independent interest as a contribution to Computer Arithmetic. All algorithms are implemented as C libraries, integrated into an open-source filter code generator and tested on numerical examples.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
In this paper we target the Fixed-Point (FxP) implementation of Linear Time-Invariant (LTI) filters evaluated with state-space equations. We assume that wordlengths are fixed and that our goal is to determine binary point positions that guarantee the absence of overflows while maximizing accuracy. We provide a model for the worst-case error analysis of FxP filters that gives tight bounds on the output error. Then we develop an algorithm for the determination of binary point positions that takes rounding errors and their amplification fully into account. The proposed techniques are rigorous, i.e., based on proofs, and no simulations are ever used. In practice, Floating-Point (FP) errors that occur in the implementation of FxP design routines can lead to overestimation/underestimation of resulting parameters. Thus, along with FxP analysis of digital filters, we provide FP analysis of our filter design algorithms. In particular, the core measure in our approach, Worst-Case Peak Gain, is defined as an infinite sum and has matrix powers in it. We provide fine-grained FP error analysis of its evaluation and develop multiple precision algorithms that dynamically adapt their internal precision to satisfy an a priori absolute error bound. Our techniques on multiple precision matrix algorithms, such as eigendecomposition, are of independent interest as a contribution to Computer Arithmetic. All algorithms are implemented as C libraries, integrated into an open-source filter code generator and tested on numerical examples.
2019
Hilaire, T.; Ouzia, H.; Lopez, B.
Optimal Word-Length Allocation for the Fixed-Point Implementation of Linear Filters and Controllers Proceedings Article
In: 2019 IEEE 26th Symposium on Computer Arithmetic (ARITH), 2019.
@inproceedings{Hila19a,
title = {Optimal Word-Length Allocation for the Fixed-Point Implementation of Linear Filters and Controllers},
author = {T. Hilaire and H. Ouzia and B. Lopez},
year = {2019},
date = {2019-01-01},
booktitle = {2019 IEEE 26th Symposium on Computer Arithmetic (ARITH)},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Volkova, A.; Istoan, M.; Dinechin, F. De; Hilaire, T.
Towards Hardware IIR Filters Computing Just Right: Direct Form I Case Study Journal Article
In: IEEE Transactions on Computers, vol. 68, no. 4, pp. 597-608, 2019, ISSN: 0018-9340.
@article{Volk19b,
title = {Towards Hardware IIR Filters Computing Just Right: Direct Form I Case Study},
author = {A. Volkova and M. Istoan and F. De Dinechin and T. Hilaire},
doi = {10.1109/TC.2018.2879432},
issn = {0018-9340},
year = {2019},
date = {2019-01-01},
journal = {IEEE Transactions on Computers},
volume = {68},
number = {4},
pages = {597-608},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
2018
Gallois-Wong, Diane; Boldo, Sylvie; Hilaire, Thibault
A Coq Formalization of Digital Filters Proceedings Article
In: Intelligent Computer Mathematics - 11th International Conference, CICM 2018, Hagenberg, Austria, August 13-17, 2018, Proceedings, pp. 87–103, 2018.
@inproceedings{Gall18a,
title = {A Coq Formalization of Digital Filters},
author = {Diane Gallois-Wong and Sylvie Boldo and Thibault Hilaire},
year = {2018},
date = {2018-01-01},
booktitle = {Intelligent Computer Mathematics - 11th International Conference, CICM 2018, Hagenberg, Austria, August 13-17, 2018, Proceedings},
pages = {87–103},
abstract = {Digital filters are small iterative algorithms, used as basic bricks in signal processing (filters) and control theory (controllers). They receive as input a stream of values, and output another stream of values, computed from their internal state and from the previous inputs. These systems can be found in communication, aeronautics, automotive, robotics, etc. As the application domain may be critical, we aim at providing a formal guarantee of the good behavior of these algorithms in time-domain. In particular, we formally proved in Coq some error analysis theorems about digital filters, namely the Worst-Case Peak Gain theorem and the existence of a filter characterizing the difference between the exact filter and the implemented one. Moreover, the digital signal processing literature provides us with many equivalent algorithms, called realizations. We formally defined and proved the equivalence of several realizations (Direct Forms and State-Space).},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Digital filters are small iterative algorithms, used as basic bricks in signal processing (filters) and control theory (controllers). They receive as input a stream of values, and output another stream of values, computed from their internal state and from the previous inputs. These systems can be found in communication, aeronautics, automotive, robotics, etc. As the application domain may be critical, we aim at providing a formal guarantee of the good behavior of these algorithms in time-domain. In particular, we formally proved in Coq some error analysis theorems about digital filters, namely the Worst-Case Peak Gain theorem and the existence of a filter characterizing the difference between the exact filter and the implemented one. Moreover, the digital signal processing literature provides us with many equivalent algorithms, called realizations. We formally defined and proved the equivalence of several realizations (Direct Forms and State-Space).
2017
Volkova, Anastasia; Hilaire, Thibault; Lauter, Christoph Q.
Rigorous determination of recursive filter Fixed-Point Implementation with input signal frequency specifications Proceedings Article
In: Asilomar Conference on Signals, Systems and Computers, 2017.
@inproceedings{Volk17b,
title = {Rigorous determination of recursive filter Fixed-Point Implementation with input signal frequency specifications},
author = {Anastasia Volkova and Thibault Hilaire and Christoph Q. Lauter},
year = {2017},
date = {2017-11-01},
booktitle = {Asilomar Conference on Signals, Systems and Computers},
abstract = {In this article, we focus on the Fixed-Point implementation of Linear Time Invariant (LTI) in state-space representation. For that purpose, we give an algorithm to determine the fixed-point formats of all the involved variables (states and outputs).
For the sake of generality, algorithm has been applied to the case of Multiple Inputs Multiple Outputs (MIMO) filters.
The computational errors in the intermediate steps of the
filter evaluation as well as their accumulation over time is
fully taken into account. We handle several rounding modes
(round to nearest and truncation) for a two's-complement based
Fixed-Point Arithmetic. Our approach is fully rigorous in the
way that the output Fixed-Point formats are shown to avoid
overflows and we do not use
any (non-exhaustive) filter simulation steps.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
In this article, we focus on the Fixed-Point implementation of Linear Time Invariant (LTI) in state-space representation. For that purpose, we give an algorithm to determine the fixed-point formats of all the involved variables (states and outputs).
For the sake of generality, algorithm has been applied to the case of Multiple Inputs Multiple Outputs (MIMO) filters.
The computational errors in the intermediate steps of the
filter evaluation as well as their accumulation over time is
fully taken into account. We handle several rounding modes
(round to nearest and truncation) for a two's-complement based
Fixed-Point Arithmetic. Our approach is fully rigorous in the
way that the output Fixed-Point formats are shown to avoid
overflows and we do not use
any (non-exhaustive) filter simulation steps.
For the sake of generality, algorithm has been applied to the case of Multiple Inputs Multiple Outputs (MIMO) filters.
The computational errors in the intermediate steps of the
filter evaluation as well as their accumulation over time is
fully taken into account. We handle several rounding modes
(round to nearest and truncation) for a two's-complement based
Fixed-Point Arithmetic. Our approach is fully rigorous in the
way that the output Fixed-Point formats are shown to avoid
overflows and we do not use
any (non-exhaustive) filter simulation steps.
Qureshi, F.; Takala, J.; Volkova, A.; Hilaire, T.
Multiplierless unified architecture for mixed radix-2/3/4 FFTs Proceedings Article
In: 2017 25th European Signal Processing Conference (EUSIPCO), pp. 1334-1338, 2017, ISSN: 2076-1465.
@inproceedings{Faha17,
title = {Multiplierless unified architecture for mixed radix-2/3/4 FFTs},
author = {F. Qureshi and J. Takala and A. Volkova and T. Hilaire},
doi = {10.23919/EUSIPCO.2017.8081425},
issn = {2076-1465},
year = {2017},
date = {2017-08-01},
booktitle = {2017 25th European Signal Processing Conference (EUSIPCO)},
pages = {1334-1338},
abstract = {This paper presents a novel runtime-reconfigurable, mixed radix core for computation 2-, 3-, 4- point fast Fourier transforms (FFT). The proposed architecture is based on radix-3 Wingorad Fourier transform, however multiplication is performed by constant multiplication instead of general multiplier. The complexity is equal to multiplierless 3-point FFT in terms of adders/subtractors with the exception of a few additional multiplexers. The proposed architecture supports all the FFT sizes which can be factorized into 2, 3, 4 point systems. We also show that the proposed architecture has the same bound on the accuracy as the classical one.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
This paper presents a novel runtime-reconfigurable, mixed radix core for computation 2-, 3-, 4- point fast Fourier transforms (FFT). The proposed architecture is based on radix-3 Wingorad Fourier transform, however multiplication is performed by constant multiplication instead of general multiplier. The complexity is equal to multiplierless 3-point FFT in terms of adders/subtractors with the exception of a few additional multiplexers. The proposed architecture supports all the FFT sizes which can be factorized into 2, 3, 4 point systems. We also show that the proposed architecture has the same bound on the accuracy as the classical one.
Volkova, A.; Lauter, C.; Hilaire, T.
Reliable Verification of Digital Implemented Filters Against Frequency Specifications Proceedings Article
In: 2017 IEEE 24th Symposium on Computer Arithmetic (ARITH), pp. 180-187, 2017, ISSN: 1063-6889.
@inproceedings{Volk17a,
title = {Reliable Verification of Digital Implemented Filters Against Frequency Specifications},
author = {A. Volkova and C. Lauter and T. Hilaire},
issn = {1063-6889},
year = {2017},
date = {2017-01-01},
booktitle = {2017 IEEE 24th Symposium on Computer Arithmetic (ARITH)},
pages = {180-187},
abstract = {Reliable implementation of digital filters in finiteprecision is based on accurate error analysis. However, a small error in the time domain does not guarantee that the implemented filter verifies the initial band specifications in the frequency domain. We propose a novel certified algorithm for the verification of a filter's transfer function, or of an existing finite-precision implementation. We show that this problem boils down to the verification of bounds on a rational function, and further to the positivity of a polynomial. Our algorithm has reasonable runtime efficiency to be used as a criterion in large implementation space explorations. We ensure that there are no false positives but false negative answers may occur. For negative answers we give a tight bound on the margin of acceptable specifications.We demonstrate application of our algorithm to the comparison of various finite-precision implementations of filters already fully designed.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Reliable implementation of digital filters in finiteprecision is based on accurate error analysis. However, a small error in the time domain does not guarantee that the implemented filter verifies the initial band specifications in the frequency domain. We propose a novel certified algorithm for the verification of a filter's transfer function, or of an existing finite-precision implementation. We show that this problem boils down to the verification of bounds on a rational function, and further to the positivity of a polynomial. Our algorithm has reasonable runtime efficiency to be used as a criterion in large implementation space explorations. We ensure that there are no false positives but false negative answers may occur. For negative answers we give a tight bound on the margin of acceptable specifications.We demonstrate application of our algorithm to the comparison of various finite-precision implementations of filters already fully designed.
Hilaire, T.; Volkova, A.
Error analysis methods for the fixed-point implementation of linear systems Conference
Proc. IEEE Workshop on Signal Processing Systems (SiPS), 2017.
@conference{Hila17a,
title = {Error analysis methods for the fixed-point implementation of linear systems},
author = {T. Hilaire and A. Volkova},
year = {2017},
date = {2017-01-01},
booktitle = {Proc. IEEE Workshop on Signal Processing Systems (SiPS)},
keywords = {},
pubstate = {published},
tppubtype = {conference}
}
2016
Volkova, A.; Lauter, C.; Hilaire, T.
Computing the Worst-Case Peak Gain of Digital Filter in Interval Arithmetic Proceedings Article
In: Proceedings of the 17th International Symposium on Scientific Computing, Computer Arithmetics and Verified Numerics, 2016.
@inproceedings{Volk16a,
title = {Computing the Worst-Case Peak Gain of Digital Filter in Interval Arithmetic},
author = {A. Volkova and C. Lauter and T. Hilaire},
year = {2016},
date = {2016-01-01},
booktitle = {Proceedings of the 17th International Symposium on Scientific Computing, Computer Arithmetics and Verified Numerics},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Hilaire, T.; Volkova, A.; Ravoson, M.
Reliable fixed-point implementation of linear data-flows Proceedings Article
In: Proc. IEEE Workshop on Signal Processing Systems (SiPS), 2016.
@inproceedings{Hila16a,
title = {Reliable fixed-point implementation of linear data-flows},
author = {T. Hilaire and A. Volkova and M. Ravoson},
year = {2016},
date = {2016-01-01},
booktitle = {Proc. IEEE Workshop on Signal Processing Systems (SiPS)},
abstract = {In this article, we propose a complete methodology to implement a signal processing or control-engineering algo- rithm described with a linear data-flow into numerical code using fixed-point arithmetic. Our approach is based on a reliable determination of the Worst-Case Peak gain of a filter as well as on rigorous error analysis of roundoff error propagation. It guarantees that no overflow will occur and that the output error due to the finite precision implementation is less than a given bound.
Without loss of generality, we consider the linear data- flows given in the form of Simulink block diagram. It is first transposed into an internal matrix-based representation and then the reliable evaluation of the magnitudes of each internal variable is performed. Our approach allows determining the minimum word-length required to achieve a given accuracy. Finally, the methodology is illustrated with numerical examples.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
In this article, we propose a complete methodology to implement a signal processing or control-engineering algo- rithm described with a linear data-flow into numerical code using fixed-point arithmetic. Our approach is based on a reliable determination of the Worst-Case Peak gain of a filter as well as on rigorous error analysis of roundoff error propagation. It guarantees that no overflow will occur and that the output error due to the finite precision implementation is less than a given bound.
Without loss of generality, we consider the linear data- flows given in the form of Simulink block diagram. It is first transposed into an internal matrix-based representation and then the reliable evaluation of the magnitudes of each internal variable is performed. Our approach allows determining the minimum word-length required to achieve a given accuracy. Finally, the methodology is illustrated with numerical examples.
Without loss of generality, we consider the linear data- flows given in the form of Simulink block diagram. It is first transposed into an internal matrix-based representation and then the reliable evaluation of the magnitudes of each internal variable is performed. Our approach allows determining the minimum word-length required to achieve a given accuracy. Finally, the methodology is illustrated with numerical examples.
2015
Volkova, A.; Hilaire, T.
Fixed-Point implementation of Lattice Wave Digital Filter: comparison and error analysis Proceedings Article
In: Proc. European Signal Processing Conference (EUSIPCO'15), 2015.
@inproceedings{Volk15b,
title = {Fixed-Point implementation of Lattice Wave Digital Filter: comparison and error analysis},
author = {A. Volkova and T. Hilaire},
year = {2015},
date = {2015-09-01},
booktitle = {Proc. European Signal Processing Conference (EUSIPCO'15)},
abstract = {A consistent analysis of the filter design along with its further implementation in fixed-point arithmetic requires a large amount of work, and this process differs from one filter representation to another. For the unifying purposes of such flow, a Specialized Implicit Form (SIF) had been proposed.Various sensitivity and stability measures have been adapted to it along with an a priori error analysis (quantization of the coefficients and output error).
In this paper a conversion algorithm for the widely used Lattice Wave Digital Filters (LWDF) to the SIF is presented, along with a finite precision error analysis. It allows to compare fairly LWDF to other structures, like direct forms and state-space. This is illustrated with a numerical example.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
A consistent analysis of the filter design along with its further implementation in fixed-point arithmetic requires a large amount of work, and this process differs from one filter representation to another. For the unifying purposes of such flow, a Specialized Implicit Form (SIF) had been proposed.Various sensitivity and stability measures have been adapted to it along with an a priori error analysis (quantization of the coefficients and output error).
In this paper a conversion algorithm for the widely used Lattice Wave Digital Filters (LWDF) to the SIF is presented, along with a finite precision error analysis. It allows to compare fairly LWDF to other structures, like direct forms and state-space. This is illustrated with a numerical example.
In this paper a conversion algorithm for the widely used Lattice Wave Digital Filters (LWDF) to the SIF is presented, along with a finite precision error analysis. It allows to compare fairly LWDF to other structures, like direct forms and state-space. This is illustrated with a numerical example.
Volkova, Anastasia; Hilaire, Thibault; Lauter, Christoph Q.
Determining Fixed-Point Formats for a Digital Filter Implementation using the Worst-Case Peak-Gain measure Proceedings Article
In: Asilomar Conference on Signals, Systems and Computers, 2015.
@inproceedings{Volk15c,
title = {Determining Fixed-Point Formats for a Digital Filter Implementation using the Worst-Case Peak-Gain measure},
author = {Anastasia Volkova and Thibault Hilaire and Christoph Q. Lauter},
year = {2015},
date = {2015-01-01},
booktitle = {Asilomar Conference on Signals, Systems and Computers},
abstract = {In this article, we focus on the Fixed-Point implementation of Linear Time Invariant (LTI) in state-space representation. For that purpose, we give an algorithm to determine the fixed-point formats of all the involved variables (states and outputs).
For the sake of generality, algorithm has been applied to the case of Multiple Inputs Multiple Outputs (MIMO) filters.
The computational errors in the intermediate steps of the
filter evaluation as well as their accumulation over time is
fully taken into account. We handle several rounding modes
(round to nearest and truncation) for a two's-complement based
Fixed-Point Arithmetic. Our approach is fully rigorous in the
way that the output Fixed-Point formats are shown to avoid
overflows and we do not use
any (non-exhaustive) filter simulation steps.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
In this article, we focus on the Fixed-Point implementation of Linear Time Invariant (LTI) in state-space representation. For that purpose, we give an algorithm to determine the fixed-point formats of all the involved variables (states and outputs).
For the sake of generality, algorithm has been applied to the case of Multiple Inputs Multiple Outputs (MIMO) filters.
The computational errors in the intermediate steps of the
filter evaluation as well as their accumulation over time is
fully taken into account. We handle several rounding modes
(round to nearest and truncation) for a two's-complement based
Fixed-Point Arithmetic. Our approach is fully rigorous in the
way that the output Fixed-Point formats are shown to avoid
overflows and we do not use
any (non-exhaustive) filter simulation steps.
For the sake of generality, algorithm has been applied to the case of Multiple Inputs Multiple Outputs (MIMO) filters.
The computational errors in the intermediate steps of the
filter evaluation as well as their accumulation over time is
fully taken into account. We handle several rounding modes
(round to nearest and truncation) for a two's-complement based
Fixed-Point Arithmetic. Our approach is fully rigorous in the
way that the output Fixed-Point formats are shown to avoid
overflows and we do not use
any (non-exhaustive) filter simulation steps.
Volkova, Anastasia; Hilaire, Thibault; Lauter, Christoph Q.
Reliable evaluation of the Worst-Case Peak Gain matrix in multiple precision Proceedings Article
In: 22nd IEEE Symposium on Computer Arithmetic, Jun 2015, Lyon, France. 2015, Lyon, France, 2015.
@inproceedings{Volk15a,
title = {Reliable evaluation of the Worst-Case Peak Gain matrix in multiple precision},
author = {Anastasia Volkova and Thibault Hilaire and Christoph Q. Lauter},
year = {2015},
date = {2015-01-01},
booktitle = {22nd IEEE Symposium on Computer Arithmetic, Jun 2015, Lyon, France. 2015},
address = {Lyon, France},
abstract = {The worst-case peak gain (WCPG) of an LTI filter is an important measure for the implementation of signal processing algorithms. It is used in the error propagation analysis for filters, thus a reliable evaluation with controlled precision is required. The WCPG is computed as an infinite sum and has matrix powers in each summand. We propose a direct formula for the lower bound on truncation order of the infinite sum in dependency of desired truncation error. Several multiprecision methods for complex matrix operations are developed and their error analysis performed. We present a multiprecision complex matrix inversion algorithm using Newton-type iteration, along with its error analysis and proof of convergence. A multiprecision matrix powering method is presented. All methods yield a rigorous solution with an absolute error bounded by an a priori given value. The results are illustrated with numerical examples.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
The worst-case peak gain (WCPG) of an LTI filter is an important measure for the implementation of signal processing algorithms. It is used in the error propagation analysis for filters, thus a reliable evaluation with controlled precision is required. The WCPG is computed as an infinite sum and has matrix powers in each summand. We propose a direct formula for the lower bound on truncation order of the infinite sum in dependency of desired truncation error. Several multiprecision methods for complex matrix operations are developed and their error analysis performed. We present a multiprecision complex matrix inversion algorithm using Newton-type iteration, along with its error analysis and proof of convergence. A multiprecision matrix powering method is presented. All methods yield a rigorous solution with an absolute error bounded by an a priori given value. The results are illustrated with numerical examples.
2014
Lopez, Benoit; Hilaire, Thibault; Didier, Laurent-Stéphane
Formatting bits to better implement signal processing algorithms Proceedings Article
In: 4th international Conference on Pervasive and Embedded Computing and Communication Systems (PECCS), Lisbon, Portugal, 2014.
@inproceedings{Lope14,
title = {Formatting bits to better implement signal processing algorithms},
author = {Benoit Lopez and Thibault Hilaire and Laurent-Stéphane Didier},
year = {2014},
date = {2014-01-01},
booktitle = {4th international Conference on Pervasive and Embedded Computing and Communication Systems (PECCS)},
address = {Lisbon, Portugal},
abstract = {This article deals with the fixed-point computation of the sum-of-products, necessary for the implementation of several algorithms, including linear filters. Fixed-point arithmetic implies output errors to be controlled. So, a new method is proposed to perform accurate computation of the filter and minimize the word-lengths of the operations. This is done by removing bits from operands that don't impact the final result under a given limit. Then, the final output of linear filter is guaranteed to be a faithful rounding of the real output.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
This article deals with the fixed-point computation of the sum-of-products, necessary for the implementation of several algorithms, including linear filters. Fixed-point arithmetic implies output errors to be controlled. So, a new method is proposed to perform accurate computation of the filter and minimize the word-lengths of the operations. This is done by removing bits from operands that don't impact the final result under a given limit. Then, the final output of linear filter is guaranteed to be a faithful rounding of the real output.
2013
Hilaire, T.; Lopez, B.
Reliable Implementation of Linear Filters with Fixed-Point Arithmetic Conference
Proc. IEEE Workshop on Signal Processing Systems (SiPS), 2013.
@conference{Hila13a,
title = {Reliable Implementation of Linear Filters with Fixed-Point Arithmetic},
author = {T. Hilaire and B. Lopez},
year = {2013},
date = {2013-01-01},
booktitle = {Proc. IEEE Workshop on Signal Processing Systems (SiPS)},
abstract = {This article deals with the implementation of linear filters or controllers with fixed-point arithmetic. The finite precision of the computations and the roundoff errors induced may have an important impact on the numerical behavior of the implemented system. Moreover, the fixed-point transformation is a time consuming and error- prone task, specially with the objective of minimizing the quantization impact.
Based on a formalism able to describe every structure of linear filters/controllers, this paper proposes an automatic method to generate fixed-point version of the inputs-to-outputs algorithm and an analysis of the global error added on the output. An example illustrates the approach.},
keywords = {},
pubstate = {published},
tppubtype = {conference}
}
This article deals with the implementation of linear filters or controllers with fixed-point arithmetic. The finite precision of the computations and the roundoff errors induced may have an important impact on the numerical behavior of the implemented system. Moreover, the fixed-point transformation is a time consuming and error- prone task, specially with the objective of minimizing the quantization impact.
Based on a formalism able to describe every structure of linear filters/controllers, this paper proposes an automatic method to generate fixed-point version of the inputs-to-outputs algorithm and an analysis of the global error added on the output. An example illustrates the approach.
Based on a formalism able to describe every structure of linear filters/controllers, this paper proposes an automatic method to generate fixed-point version of the inputs-to-outputs algorithm and an analysis of the global error added on the output. An example illustrates the approach.
2012
Lopez, Benoit; Hilaire, Thibault; Didier, Laurent-Stéphane
Sum-of-products Evaluation Schemes with Fixed-Point arithmetic, and their application to IIR filter implementation Proceedings Article
In: Conference on Design and Architectures for Signal and Image Processing (DASIP), Karlsruhe, Germany, 2012.
@inproceedings{Lope12,
title = {Sum-of-products Evaluation Schemes with Fixed-Point arithmetic, and their application to IIR filter implementation},
author = {Benoit Lopez and Thibault Hilaire and Laurent-Stéphane Didier},
year = {2012},
date = {2012-10-01},
booktitle = {Conference on Design and Architectures for Signal and Image Processing (DASIP)},
address = {Karlsruhe, Germany},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Menard, D.; Rocher, R.; Sentieys, O.; Simon, N.; Didier, L-S.; Hilaire, T.; Lopez, B.; Goubault, E.; Putot, S.; Vedrine, F; Najahi, A.; Revy, G.; Fangain, L; Samoyeau, C.; Lemonnier, F; Clienti, C.
Design of Fixed-point Embedded Systems (DEFIS) Proceedings Article
In: Chips, ECSI - European Electronic; Initiative, Systems (Ed.): 2012 Conference on Design and Architectures for Signal and Image Processing (DASIP), Karlsruhe, Germany, October 23 - 25, 2012, pp. 365-366, ECSI - European Electronic Chips and Systems design Initiative, 2012, ISSN: 1966-7116.
@inproceedings{Mena12,
title = {Design of Fixed-point Embedded Systems (DEFIS)},
author = {D. Menard and R. Rocher and O. Sentieys and N. Simon and L-S. Didier and T. Hilaire and B. Lopez and E. Goubault and S. Putot and F Vedrine and A. Najahi and G. Revy and L Fangain and C. Samoyeau and F Lemonnier and C. Clienti},
editor = {ECSI - European Electronic Chips and Systems Initiative},
issn = {1966-7116},
year = {2012},
date = {2012-01-01},
booktitle = {2012 Conference on Design and Architectures for Signal and Image Processing (DASIP), Karlsruhe, Germany, October 23 - 25, 2012},
pages = {365-366},
publisher = {ECSI - European Electronic Chips and Systems design Initiative},
abstract = {Embedded applications are usually coming with stringent constraints in term of cost, energy consumption and realtime. Consequently, fixed-point arithmetic is mainstream for their implementation into embedded systems. Hence, the main objective of the french ANR project DEFIS is to provide a complete design flow for fixed-point refinement of complex applications. This tool flow is like the missing link between high-level application specification tools and low-level implementation.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Embedded applications are usually coming with stringent constraints in term of cost, energy consumption and realtime. Consequently, fixed-point arithmetic is mainstream for their implementation into embedded systems. Hence, the main objective of the french ANR project DEFIS is to provide a complete design flow for fixed-point refinement of complex applications. This tool flow is like the missing link between high-level application specification tools and low-level implementation.
Hilaire, Thibault; Chevrel, Philippe
Réalisations optimales pour l'implantation de systèmes LTI paramétrés Proceedings Article
In: Septième Conférence Internationale Francophone d'Automatique, Grenoble, 2012.
@inproceedings{Hila12a,
title = {Réalisations optimales pour l'implantation de systèmes LTI paramétrés},
author = {Thibault Hilaire and Philippe Chevrel},
year = {2012},
date = {2012-01-01},
booktitle = {Septième Conférence Internationale Francophone d'Automatique},
address = {Grenoble},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Hilaire, Thibault; Chapoutot, Alexandre
Interval-based Robustness of Linear Parametrized Filters Proceedings Article
In: Proceedings of the 15'th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic and Verified Numerical Computations, 2012, 2012.
@inproceedings{Hila12b,
title = {Interval-based Robustness of Linear Parametrized Filters},
author = {Thibault Hilaire and Alexandre Chapoutot},
year = {2012},
date = {2012-01-01},
booktitle = {Proceedings of the 15'th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic and Verified Numerical Computations, 2012},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
2011
Bajard, J. C.; Didier, L. S.; Hilaire, T.
ρ-Direct Form Transposed and Residue Number Systems for Filter implementations Proceedings Article
In: Circuits and Systems (MWSCAS), 2011 IEEE 54th International Midwest Symposium on, 2011.
@inproceedings{Baja11a,
title = {ρ-Direct Form Transposed and Residue Number Systems for Filter implementations},
author = {J. C. Bajard and L. S. Didier and T. Hilaire},
year = {2011},
date = {2011-08-01},
booktitle = {Circuits and Systems (MWSCAS), 2011 IEEE 54th International Midwest Symposium on},
abstract = {This paper deals with a new approach for Infinite Impulse Response (IIR) Filter based on specific structure and arithmetic.
The ρ-Direct Form II transposed, introduced by G. Li, is an numerically efficient structure for FIR or IIR filters. Compared to classical direct forms, it uses more computations but less bits are necessary for the same precision. These properties made it well conditioned for fixed point arithmetic and its implementations are economical and numerically efficient comparing to other forms. In other hand, Residue Number Systems (RNS) offer an interest- ing parallelism where operations are made on small values. RNS are well known for improving the performances of DSP filters. We compare our RNS approach to fixed-point implementations of DFI and ρ-DFIIt.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
This paper deals with a new approach for Infinite Impulse Response (IIR) Filter based on specific structure and arithmetic.
The ρ-Direct Form II transposed, introduced by G. Li, is an numerically efficient structure for FIR or IIR filters. Compared to classical direct forms, it uses more computations but less bits are necessary for the same precision. These properties made it well conditioned for fixed point arithmetic and its implementations are economical and numerically efficient comparing to other forms. In other hand, Residue Number Systems (RNS) offer an interest- ing parallelism where operations are made on small values. RNS are well known for improving the performances of DSP filters. We compare our RNS approach to fixed-point implementations of DFI and ρ-DFIIt.
The ρ-Direct Form II transposed, introduced by G. Li, is an numerically efficient structure for FIR or IIR filters. Compared to classical direct forms, it uses more computations but less bits are necessary for the same precision. These properties made it well conditioned for fixed point arithmetic and its implementations are economical and numerically efficient comparing to other forms. In other hand, Residue Number Systems (RNS) offer an interest- ing parallelism where operations are made on small values. RNS are well known for improving the performances of DSP filters. We compare our RNS approach to fixed-point implementations of DFI and ρ-DFIIt.
Hilaire, T.
Le problème d'implantation emphoptimale de filtres Miscellaneous
Présentation équipe Arénaire (LIP, ENS Lyon), 2011.
@misc{Hila11c,
title = {Le problème d'implantation emphoptimale de filtres},
author = {T. Hilaire},
year = {2011},
date = {2011-04-01},
howpublished = {Présentation équipe Arénaire (LIP, ENS Lyon)},
keywords = {},
pubstate = {published},
tppubtype = {misc}
}
Hilaire, T.
Implantation "optimale" en virgule fixe d'algorithmes de traitement du signal Miscellaneous
Rencontres Arithmétique-Informatique-Mathématique (RAIM-2011), 2011.
@misc{Hila11d,
title = {Implantation "optimale" en virgule fixe d'algorithmes de traitement du signal},
author = {T. Hilaire},
year = {2011},
date = {2011-02-01},
howpublished = {Rencontres Arithmétique-Informatique-Mathématique (RAIM-2011)},
keywords = {},
pubstate = {published},
tppubtype = {misc}
}
Hilaire, T.
Towards Tools and Methodology for the Fixed-Point Implementation of Linear Filters Proceedings Article
In: Digital Signal Processing Workshop and IEEE Signal Processing Education Workshop (DSP/SPE), 2011 IEEE, pp. 488-493, 2011.
@inproceedings{Hila11a,
title = {Towards Tools and Methodology for the Fixed-Point Implementation of Linear Filters},
author = {T. Hilaire},
year = {2011},
date = {2011-01-01},
booktitle = {Digital Signal Processing Workshop and IEEE Signal Processing Education Workshop (DSP/SPE), 2011 IEEE},
pages = {488-493},
abstract = {For embedded systems, Finite Word Length (FWL) effect is still a critical issue in digital filter implementation with fixed-point arithmetic. Few partial solutions exist, but none tackles it in its global nature and consider the complete tradeoff between performance, precision, complexity and hardware cost. This paper proposes to formalize this complex problem and exhibits a unifying approach for the optimal implementation problem of linear filters/controllers. The proposed methodology is based on previously proposed formal description and measures of the FWL effects. A two steps optimization is proposed and a small example emphasizes the process.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
For embedded systems, Finite Word Length (FWL) effect is still a critical issue in digital filter implementation with fixed-point arithmetic. Few partial solutions exist, but none tackles it in its global nature and consider the complete tradeoff between performance, precision, complexity and hardware cost. This paper proposes to formalize this complex problem and exhibits a unifying approach for the optimal implementation problem of linear filters/controllers. The proposed methodology is based on previously proposed formal description and measures of the FWL effects. A two steps optimization is proposed and a small example emphasizes the process.
Hilaire, T.; Chevrel, P.
Sensitivity-based Pole and Input-Output Errors of Linear Filters as Indicators of the Implementation Deterioration in Fixed-Point Context Journal Article
In: EURASIP Journal on Advances in Signal Processing, 2011, (special issue on Quantization of VLSI Digital Signal Processing Systems).
@article{Hila11b,
title = {Sensitivity-based Pole and Input-Output Errors of Linear Filters as Indicators of the Implementation Deterioration in Fixed-Point Context},
author = {T. Hilaire and P. Chevrel},
year = {2011},
date = {2011-01-01},
journal = {EURASIP Journal on Advances in Signal Processing},
abstract = {Input-output or poles sensitivity is widely used to evaluate the resilience of a filter realization to coefficients quantization in an FWL implementation process. However, these measures do not exactly consider the various implementation schemes and are not accurate in general case. This paper generalizes the classical transfer function sensitivity and pole sensitivity measure, by taking into consideration the exact fixed-point representation of the coefficients. Working in the general framework of the specialized implicit descriptor representation, it shows how a statistical quantization error model may be used in order to define stochastic sensitivity measures that are definitely pertinent and normalized. The general framework of MIMO filters and controllers is considered. All the results are illustrated through an example.},
note = {special issue on Quantization of VLSI Digital Signal Processing Systems},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Input-output or poles sensitivity is widely used to evaluate the resilience of a filter realization to coefficients quantization in an FWL implementation process. However, these measures do not exactly consider the various implementation schemes and are not accurate in general case. This paper generalizes the classical transfer function sensitivity and pole sensitivity measure, by taking into consideration the exact fixed-point representation of the coefficients. Working in the general framework of the specialized implicit descriptor representation, it shows how a statistical quantization error model may be used in order to define stochastic sensitivity measures that are definitely pertinent and normalized. The general framework of MIMO filters and controllers is considered. All the results are illustrated through an example.
Feng, Y.; Chevrel, P.; Hilaire, T.
Generalised modal realisation as a practical and efficient tool for FWL implementation Journal Article
In: International Journal of Control, vol. 84, no. 1, pp. 66-77, 2011.
@article{Feng11a,
title = {Generalised modal realisation as a practical and efficient tool for FWL implementation},
author = {Y. Feng and P. Chevrel and T. Hilaire},
year = {2011},
date = {2011-01-01},
journal = {International Journal of Control},
volume = {84},
number = {1},
pages = {66-77},
abstract = {Finite word length (FWL) effects have been a critical issue in digital filter implementation for almost four decades. Although some optimisations may be attempted to get an optimal realisation with regards to a particular effect, for instance the parametric sensitivity or the round-off noise gain, the purpose of this article is to propose an effective one, i.e. taking into account all the aspects. Based on the specialised implicit form, a new effective and sparse structure, named q-modal realisation, is proposed. This realisation meets simultaneously accuracy (low sensitivity, round-off noise gain and overflow risk), few and flexible computational efforts with a good readability (thanks to sparsity) and simplicity (no tricky optimisation is required to obtain it) as well. Two numerical examples are included to illustrate the q-modal realisation's interest.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Finite word length (FWL) effects have been a critical issue in digital filter implementation for almost four decades. Although some optimisations may be attempted to get an optimal realisation with regards to a particular effect, for instance the parametric sensitivity or the round-off noise gain, the purpose of this article is to propose an effective one, i.e. taking into account all the aspects. Based on the specialised implicit form, a new effective and sparse structure, named q-modal realisation, is proposed. This realisation meets simultaneously accuracy (low sensitivity, round-off noise gain and overflow risk), few and flexible computational efforts with a good readability (thanks to sparsity) and simplicity (no tricky optimisation is required to obtain it) as well. Two numerical examples are included to illustrate the q-modal realisation's interest.
2010
Sluciak, O.; Hilaire, T.; Rupp, M.
A General Formalism for the Analysis of Distributed Algorithms Conference
Acoustics Speech and Signal Processing (ICASSP), 2010 IEEE International Conference on, 2010.
@conference{Sluc10,
title = {A General Formalism for the Analysis of Distributed Algorithms},
author = {O. Sluciak and T. Hilaire and M. Rupp},
year = {2010},
date = {2010-03-01},
booktitle = {Acoustics Speech and Signal Processing (ICASSP), 2010 IEEE International Conference on},
pages = {2890-2893},
abstract = {The major contribution of this paper is the presentation of a general unifying description of distributed algorithms allowing to map local, node-based algorithms onto a single global, network-based form.
As a first consequence the new description offers to analyze their learning and steady-state behavior by classical methods. A further consequence is the analysis of implementation issues as they appear due to quantization in computing and communication links.
Exemplarly we apply the new method on several different averaging algorithms:
the Push-Sum protocol, Consensus Propagation as well as its quantized form
and furthermore examine the effects of quantization noise which is introduced
by the bandwidth limited communication links and finite
precision computation ability of every node. Statistical properties of
these quantization noises are provided and verified by simulations.},
keywords = {},
pubstate = {published},
tppubtype = {conference}
}
The major contribution of this paper is the presentation of a general unifying description of distributed algorithms allowing to map local, node-based algorithms onto a single global, network-based form.
As a first consequence the new description offers to analyze their learning and steady-state behavior by classical methods. A further consequence is the analysis of implementation issues as they appear due to quantization in computing and communication links.
Exemplarly we apply the new method on several different averaging algorithms:
the Push-Sum protocol, Consensus Propagation as well as its quantized form
and furthermore examine the effects of quantization noise which is introduced
by the bandwidth limited communication links and finite
precision computation ability of every node. Statistical properties of
these quantization noises are provided and verified by simulations.
As a first consequence the new description offers to analyze their learning and steady-state behavior by classical methods. A further consequence is the analysis of implementation issues as they appear due to quantization in computing and communication links.
Exemplarly we apply the new method on several different averaging algorithms:
the Push-Sum protocol, Consensus Propagation as well as its quantized form
and furthermore examine the effects of quantization noise which is introduced
by the bandwidth limited communication links and finite
precision computation ability of every node. Statistical properties of
these quantization noises are provided and verified by simulations.
Hilaire, T.; Chevrel, P.; Whidborne, J. F.
Finite Wordlength Controller Realizations using the Specialized Implicit Form Journal Article
In: Int. Journal of Control, vol. 83, no. 2, pp. 330-346, 2010.
@article{Hila10a,
title = {Finite Wordlength Controller Realizations using the Specialized Implicit Form},
author = {T. Hilaire and P. Chevrel and J. F. Whidborne},
year = {2010},
date = {2010-02-01},
journal = {Int. Journal of Control},
volume = {83},
number = {2},
pages = {330-346},
abstract = {A specialised implicit state-space representation is introduced to deal with finite wordlength effects in controller implementations. This specialised implicit form provides a macroscopic description of the algorithm to be implemented. So, it constitutes a unifying framework, allowing to encompass various implementation forms, such as the ρ-operator, the ρ Direct Form II transposed, observer-based and many other realisations usually considered separately in the literature. Different measures quantifying the finite wordlength effects on the overall closed-loop behaviour are defined in this new context. They concern both stability and performance. The gap with the infinite precision case is evaluated classically through the coefficient sensitivity and roundoff noise analysis. The problem of determining a realisation with minimum finite wordlength effects can subsequently be solved using appropriate numerical methods. The approach is illustrated with an example.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
A specialised implicit state-space representation is introduced to deal with finite wordlength effects in controller implementations. This specialised implicit form provides a macroscopic description of the algorithm to be implemented. So, it constitutes a unifying framework, allowing to encompass various implementation forms, such as the ρ-operator, the ρ Direct Form II transposed, observer-based and many other realisations usually considered separately in the literature. Different measures quantifying the finite wordlength effects on the overall closed-loop behaviour are defined in this new context. They concern both stability and performance. The gap with the infinite precision case is evaluated classically through the coefficient sensitivity and roundoff noise analysis. The problem of determining a realisation with minimum finite wordlength effects can subsequently be solved using appropriate numerical methods. The approach is illustrated with an example.
2009
Reyes, C.; Hilaire, T.; Mecklenbräuker, C.
Distributed Projection Approximation Subspace Tracking based on Consensus Propagation Conference
3rd International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP'09), 2009.
@conference{Reye09,
title = {Distributed Projection Approximation Subspace Tracking based on Consensus Propagation},
author = {C. Reyes and T. Hilaire and C. Mecklenbräuker},
year = {2009},
date = {2009-12-01},
booktitle = {3rd International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP'09)},
abstract = {We develop and investigate a distributed algorithm for signal subspace tracking with a wireless sensor network without the need for a fusion center, in order to improve the robustness and scalability. We assume that all sensor nodes may broadcast messages to sensors in their neighborhood defined by a finite (small) communication radius.
To this aim, we start from Projection Approximation Subspace Tracking (PAST) which is a well-investigated algorithm suitable for implementation in a fusion center. We arrive at a distributed approximation of the PAST algorithm by letting each sensor broadcast its local observation variable x_n(t) and a filtered observation vector y_n(t) to its neighborhood. Vice versa, the received messages at sensor node n from its neighborhood are fused by employing consensus propagation.
Finally, we investigate the proposed distributed algorithm in simulation runs.},
keywords = {},
pubstate = {published},
tppubtype = {conference}
}
We develop and investigate a distributed algorithm for signal subspace tracking with a wireless sensor network without the need for a fusion center, in order to improve the robustness and scalability. We assume that all sensor nodes may broadcast messages to sensors in their neighborhood defined by a finite (small) communication radius.
To this aim, we start from Projection Approximation Subspace Tracking (PAST) which is a well-investigated algorithm suitable for implementation in a fusion center. We arrive at a distributed approximation of the PAST algorithm by letting each sensor broadcast its local observation variable x_n(t) and a filtered observation vector y_n(t) to its neighborhood. Vice versa, the received messages at sensor node n from its neighborhood are fused by employing consensus propagation.
Finally, we investigate the proposed distributed algorithm in simulation runs.
To this aim, we start from Projection Approximation Subspace Tracking (PAST) which is a well-investigated algorithm suitable for implementation in a fusion center. We arrive at a distributed approximation of the PAST algorithm by letting each sensor broadcast its local observation variable x_n(t) and a filtered observation vector y_n(t) to its neighborhood. Vice versa, the received messages at sensor node n from its neighborhood are fused by employing consensus propagation.
Finally, we investigate the proposed distributed algorithm in simulation runs.
Hilaire, T.
On the Transfer Function Error of State-Space Filters in Fixed-Point Context Journal Article
In: IEEE Trans. on Circuits & Systems II, vol. 56, no. 12, pp. 936–940, 2009.
@article{Hila09c,
title = {On the Transfer Function Error of State-Space Filters in Fixed-Point Context},
author = {T. Hilaire},
year = {2009},
date = {2009-12-01},
journal = {IEEE Trans. on Circuits & Systems II},
volume = {56},
number = {12},
pages = {936–940},
abstract = {This brief presents a new measure used for the imple- mentation of filters/controllers in state-space form. It investigates the transfer function deviation generated by the coefficient quan- tization. The classical L2-sensitivity measure is extended with precise consideration on their fixed-point representation in order to make a more valid measure. By solving the related optimal re- alization problem, fixed-point accurate realizations in state-space form can be found.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
This brief presents a new measure used for the imple- mentation of filters/controllers in state-space form. It investigates the transfer function deviation generated by the coefficient quan- tization. The classical L2-sensitivity measure is extended with precise consideration on their fixed-point representation in order to make a more valid measure. By solving the related optimal re- alization problem, fixed-point accurate realizations in state-space form can be found.
Hilaire, T.
FWR Toolbox User's Guide (v0.99) Technical Manual
http://fwrtoolbox.gforge.inria.fr/, 2009.
@manual{Hila09e,
title = {FWR Toolbox User's Guide (v0.99)},
author = {T. Hilaire},
year = {2009},
date = {2009-01-01},
address = {http://fwrtoolbox.gforge.inria.fr/},
keywords = {},
pubstate = {published},
tppubtype = {manual}
}
Feng, Y.; Chevrel, P.; Hilaire, T.
A Practical Strategy of an Efficient and Sparse FWL Implementation of LTI Filters Proceedings Article
In: European Control Conference (ECC'09), pp. 1383-1388, 2009.
@inproceedings{Feng09a,
title = {A Practical Strategy of an Efficient and Sparse FWL Implementation of LTI Filters},
author = {Y. Feng and P. Chevrel and T. Hilaire},
year = {2009},
date = {2009-01-01},
booktitle = {European Control Conference (ECC'09)},
pages = {1383-1388},
abstract = {The problem of finite word length implementation is discussed in this paper. Alternatively to the rho-DFIIt recently proposed by G. Li et al., and leaning on the specialized implicit form for a unified analysis, a new effective and sparse structure, named rho-modal realization, is developed. This realization meets simultaneously accuracy (low sensitivity, round-off noise gain and overflow risk), few and flexible computational efforts with a good readability (owing to sparsity), and simplicity (no tricky optimization is involved) as well. Two numerical examples are presented to confirm the theoretical results and illustrate the rho-modal realization interest.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
The problem of finite word length implementation is discussed in this paper. Alternatively to the rho-DFIIt recently proposed by G. Li et al., and leaning on the specialized implicit form for a unified analysis, a new effective and sparse structure, named rho-modal realization, is developed. This realization meets simultaneously accuracy (low sensitivity, round-off noise gain and overflow risk), few and flexible computational efforts with a good readability (owing to sparsity), and simplicity (no tricky optimization is involved) as well. Two numerical examples are presented to confirm the theoretical results and illustrate the rho-modal realization interest.
Hilaire, T.
Low Parametric Sensitivity Realizations with relaxed $L_2$-dynamic-range-scaling constraints Journal Article
In: IEEE Trans. on Circuits & Systems II, vol. 56, no. 7, pp. 590–594, 2009.
@article{Hila09a,
title = {Low Parametric Sensitivity Realizations with relaxed $L_2$-dynamic-range-scaling constraints},
author = {T. Hilaire},
year = {2009},
date = {2009-01-01},
journal = {IEEE Trans. on Circuits & Systems II},
volume = {56},
number = {7},
pages = {590–594},
abstract = {This brief presents a new dynamic-range scaling for the implementation of filters/controllers in state-space form. Re- laxing the classical L2-scaling constraints by specific fixed-point considerations allows for a higher degree of freedom for the optimal L2-parametric sensitivity problem. However, overflows in the implementation are still prevented. The underlying constrained problem is converted into an unconstrained problem for which a solution can be provided. This leads to realizations that are still scaled but less sensitive.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
This brief presents a new dynamic-range scaling for the implementation of filters/controllers in state-space form. Re- laxing the classical L2-scaling constraints by specific fixed-point considerations allows for a higher degree of freedom for the optimal L2-parametric sensitivity problem. However, overflows in the implementation are still prevented. The underlying constrained problem is converted into an unconstrained problem for which a solution can be provided. This leads to realizations that are still scaled but less sensitive.
Hilaire, T.
New L2-dynamic-range-scaling Constraints for Low Parametric Sensitivity Realizations Proceedings Article
In: Eusipco'09, pp. 988-992, 2009.
@inproceedings{Hila09d,
title = {New L2-dynamic-range-scaling Constraints for Low Parametric Sensitivity Realizations},
author = {T. Hilaire},
year = {2009},
date = {2009-01-01},
booktitle = {Eusipco'09},
pages = {988-992},
abstract = {This paper presents a new dynamic-range scaling for the implementation of filters/controllers in state-space form.
Specific fixed-point considerations allow us to relax the classical L2-scaling constraints while still preserving the implementation from overflows. It gives more degrees of freedom for the optimal L2-parametric sensitivity problem. The underlying constrained problem is converted into an unconstrained problem for which a solution can be provided. This leads to realizations which are still scaled but less sensitive.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
This paper presents a new dynamic-range scaling for the implementation of filters/controllers in state-space form.
Specific fixed-point considerations allow us to relax the classical L2-scaling constraints while still preserving the implementation from overflows. It gives more degrees of freedom for the optimal L2-parametric sensitivity problem. The underlying constrained problem is converted into an unconstrained problem for which a solution can be provided. This leads to realizations which are still scaled but less sensitive.
Specific fixed-point considerations allow us to relax the classical L2-scaling constraints while still preserving the implementation from overflows. It gives more degrees of freedom for the optimal L2-parametric sensitivity problem. The underlying constrained problem is converted into an unconstrained problem for which a solution can be provided. This leads to realizations which are still scaled but less sensitive.
2008
Hilaire, T.; Ménard, D.; Sentieys, O.
Bit Accurate Roundoff Noise Analysis of Fixed-Point Linear Controllers Conference
Computer-Aided Control Systems, 2008. CACSD 2008. IEEE International Conference on, 2008.
@conference{Hila08c,
title = {Bit Accurate Roundoff Noise Analysis of Fixed-Point Linear Controllers},
author = {T. Hilaire and D. Ménard and O. Sentieys},
year = {2008},
date = {2008-09-01},
booktitle = {Computer-Aided Control Systems, 2008. CACSD 2008. IEEE International Conference on},
pages = {607-612},
abstract = {The analytic evaluation of roundoff noise is an interesting approach to analyze the effects of fixed-point implementation of linear filters or controllers.
This paper is based on a generic framework to describe controller algorithms. It exhibits the fixed-point implementations (in different schemes) that are associated and the analytic expression of the output roundoff noise power.
Finally, the optimal realization problem, according to the roundoff noise power, is considered.},
keywords = {},
pubstate = {published},
tppubtype = {conference}
}
The analytic evaluation of roundoff noise is an interesting approach to analyze the effects of fixed-point implementation of linear filters or controllers.
This paper is based on a generic framework to describe controller algorithms. It exhibits the fixed-point implementations (in different schemes) that are associated and the analytic expression of the output roundoff noise power.
Finally, the optimal realization problem, according to the roundoff noise power, is considered.
This paper is based on a generic framework to describe controller algorithms. It exhibits the fixed-point implementations (in different schemes) that are associated and the analytic expression of the output roundoff noise power.
Finally, the optimal realization problem, according to the roundoff noise power, is considered.
Hilaire, T.
Hardware Fixed-point implementation of filters/controllers Unpublished
2008, (Séminaire d'équipe, Laboratoire de Cryptographie et de sécurité des informations, Université de Tsukuba).
@unpublished{Hila08g,
title = {Hardware Fixed-point implementation of filters/controllers},
author = {T. Hilaire},
year = {2008},
date = {2008-06-01},
note = {Séminaire d'équipe, Laboratoire de Cryptographie et de sécurité des informations, Université de Tsukuba},
keywords = {},
pubstate = {published},
tppubtype = {unpublished}
}
Hilaire, T.
Optimal fixed-point implementation of signal processing algorithms Unpublished
2008, (Séminaire d'équipe, Institute of Communication and Radio-Frequency Engineering, Vienna University of Technology).
@unpublished{Hila08f,
title = {Optimal fixed-point implementation of signal processing algorithms},
author = {T. Hilaire},
year = {2008},
date = {2008-03-01},
note = {Séminaire d'équipe, Institute of Communication and Radio-Frequency Engineering, Vienna University of Technology},
keywords = {},
pubstate = {published},
tppubtype = {unpublished}
}
Hilaire, T.
Implémentation de filtres/régulateurs - à la recherche d'une réalisation optimale Unpublished
2008, (Séminaire de l'équipe DALI (LIRMM, Université de Perpignan)).
@unpublished{Hila08d,
title = {Implémentation de filtres/régulateurs - à la recherche d'une réalisation optimale},
author = {T. Hilaire},
year = {2008},
date = {2008-01-01},
note = {Séminaire de l'équipe DALI (LIRMM, Université de Perpignan)},
keywords = {},
pubstate = {published},
tppubtype = {unpublished}
}
Hilaire, T.; Chevrel, P.
On the compact formulation of the derivation of a transfer matrix with respect to another matrix Technical Report
INRIA no. RR-6760, 2008.
@techreport{Hila07d,
title = {On the compact formulation of the derivation of a transfer matrix with respect to another matrix},
author = {T. Hilaire and P. Chevrel},
year = {2008},
date = {2008-01-01},
number = {RR-6760},
institution = {INRIA},
abstract = {A new operator is considered, allowing compact formulae and proofs in the context of the derivation of a transfer matrix with respect to another matrix. The problem of the parametric sensitivity matrix calculation is chosen for illustration. It consists in deriving a Multiple Input Multiple Output transfer function with respect to a parametric matrix and is central in robust control theory. Efficient algorithms may be straightforwardly got from the compact analytic formulae using the operator introduced.},
keywords = {},
pubstate = {published},
tppubtype = {techreport}
}
A new operator is considered, allowing compact formulae and proofs in the context of the derivation of a transfer matrix with respect to another matrix. The problem of the parametric sensitivity matrix calculation is chosen for illustration. It consists in deriving a Multiple Input Multiple Output transfer function with respect to a parametric matrix and is central in robust control theory. Efficient algorithms may be straightforwardly got from the compact analytic formulae using the operator introduced.
Hilaire, T.
Optimal fixed-point implementation of Signal Processing Algorithms Unpublished
2008, (Lecture at University of Hiroshima, Electronic Control Lab.).
@unpublished{Hila08e,
title = {Optimal fixed-point implementation of Signal Processing Algorithms},
author = {T. Hilaire},
year = {2008},
date = {2008-01-01},
abstract = {The digital implementation leads to a numerical degradation of filters/controllers such as performance, characteristics, etc. due to the quantization of the involved coefficients or round-off noise in the numerical computations. These degradations depend on the structure of the algorithm used. An analytical framework able to unifying these various realizations and numerical algorithm will be presented. Some finite word length criteria that can evaluate the induced degradation will be discussed. The optimal design problem will also be considered with the optimal word-length problem.},
note = {Lecture at University of Hiroshima, Electronic Control Lab.},
keywords = {},
pubstate = {published},
tppubtype = {unpublished}
}
The digital implementation leads to a numerical degradation of filters/controllers such as performance, characteristics, etc. due to the quantization of the involved coefficients or round-off noise in the numerical computations. These degradations depend on the structure of the algorithm used. An analytical framework able to unifying these various realizations and numerical algorithm will be presented. Some finite word length criteria that can evaluate the induced degradation will be discussed. The optimal design problem will also be considered with the optimal word-length problem.
Hilaire, T.; Chevrel, P.; Whidborne, J. F.
Finite Wordlength Controller Realizations using the Specialized Implicit Form Technical Report
INRIA no. RR-6759, 2008.
@techreport{Hila08b,
title = {Finite Wordlength Controller Realizations using the Specialized Implicit Form},
author = {T. Hilaire and P. Chevrel and J. F. Whidborne},
year = {2008},
date = {2008-01-01},
number = {RR-6759},
institution = {INRIA},
abstract = {A specialized implicit state-space representation is introduced to deal with finite wordlength effects in controller implementations. This special- ized implicit form provides a macroscopic description of the algorithm to be implemented. So, it constitutes a unifying framework, allowing to encompass various implementation forms, such as the δ-operator, the ρ-Direct Form II trans- posed, observer-based and many other realizations considered usually separately in the literature. Different measures quantifying the finite wordlength effects on the overall closed loop behaviour, are defined in this new context. They con- cern both stability and performance. The gap with the infinite precision case is evaluated classically through the coefficient sensitivity and roundoff noise anal- ysis. The problem of determining a realization with minimum finite wordlength effects can subsequently be solved using appropriate numerical methods. The approach is illustrated with two examples.},
keywords = {},
pubstate = {published},
tppubtype = {techreport}
}
A specialized implicit state-space representation is introduced to deal with finite wordlength effects in controller implementations. This special- ized implicit form provides a macroscopic description of the algorithm to be implemented. So, it constitutes a unifying framework, allowing to encompass various implementation forms, such as the δ-operator, the ρ-Direct Form II trans- posed, observer-based and many other realizations considered usually separately in the literature. Different measures quantifying the finite wordlength effects on the overall closed loop behaviour, are defined in this new context. They con- cern both stability and performance. The gap with the infinite precision case is evaluated classically through the coefficient sensitivity and roundoff noise anal- ysis. The problem of determining a realization with minimum finite wordlength effects can subsequently be solved using appropriate numerical methods. The approach is illustrated with two examples.
2007
Hilaire, T.
Implémentation virgule fixe de filtres/régulateurs Unpublished
2007, (Séminaire d'équipe Arénaire, LIP (ENS Lyon)).
@unpublished{Hila07f,
title = {Implémentation virgule fixe de filtres/régulateurs},
author = {T. Hilaire},
year = {2007},
date = {2007-12-01},
note = {Séminaire d'équipe Arénaire, LIP (ENS Lyon)},
keywords = {},
pubstate = {published},
tppubtype = {unpublished}
}
Hilaire, T.; Ménard, D.; Sentieys, O.
Roundoff Noise Analysis of Finite Wordlength Realizations with the Implicit State-Space Framework Proceedings Article
In: 15th European Signal Processing Conference (EUSIPCO'07), pp. 1019–1023, 2007.
@inproceedings{Hila07c,
title = {Roundoff Noise Analysis of Finite Wordlength Realizations with the Implicit State-Space Framework},
author = {T. Hilaire and D. Ménard and O. Sentieys},
year = {2007},
date = {2007-09-01},
booktitle = {15th European Signal Processing Conference (EUSIPCO'07)},
pages = {1019–1023},
abstract = {The analytic evaluation of the system output roundoff noise is an interesting approach to analyze the effect of a Finite Word Length implementation of linear filters. Previous works have
introduced the Roundoff Noise Gain in this context and applied it to shift and delta-realizations.
To generalize them, the paper is based on a more general representation and exhibits the output noise power in the general case.
Finally, the problem optimal realization problem, according to the Roundoff Noise Gain measure, is considered.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
The analytic evaluation of the system output roundoff noise is an interesting approach to analyze the effect of a Finite Word Length implementation of linear filters. Previous works have
introduced the Roundoff Noise Gain in this context and applied it to shift and delta-realizations.
To generalize them, the paper is based on a more general representation and exhibits the output noise power in the general case.
Finally, the problem optimal realization problem, according to the Roundoff Noise Gain measure, is considered.
introduced the Roundoff Noise Gain in this context and applied it to shift and delta-realizations.
To generalize them, the paper is based on a more general representation and exhibits the output noise power in the general case.
Finally, the problem optimal realization problem, according to the Roundoff Noise Gain measure, is considered.
Hilaire, T.; Chevrel, P.; Whidborne, J. F.
A Unifying Framework for Finite Wordlength Realizations Journal Article
In: IEEE Trans. on Circuits and Systems, vol. 8, no. 54, pp. 1765-1774, 2007.
@article{Hila07b,
title = {A Unifying Framework for Finite Wordlength Realizations},
author = {T. Hilaire and P. Chevrel and J. F. Whidborne},
year = {2007},
date = {2007-08-01},
journal = {IEEE Trans. on Circuits and Systems},
volume = {8},
number = {54},
pages = {1765-1774},
abstract = {A general framework for the analysis of the finite wordlength (FWL) effects of linear time-invariant digital filter implementations is proposed. By means of a special implicit system description, all realization forms can be described. An algebraic characterization of the equivalent classes is provided, which enables a search for realizations that minimize the FWL effects to be made. Two suitable FWL coefficient sensitivity measures are proposed for use within the framework, these being a transfer function sensitivity measure and a pole sensitivity measure. An illustrative example is presented.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
A general framework for the analysis of the finite wordlength (FWL) effects of linear time-invariant digital filter implementations is proposed. By means of a special implicit system description, all realization forms can be described. An algebraic characterization of the equivalent classes is provided, which enables a search for realizations that minimize the FWL effects to be made. Two suitable FWL coefficient sensitivity measures are proposed for use within the framework, these being a transfer function sensitivity measure and a pole sensitivity measure. An illustrative example is presented.
Hilaire, T.; Chevrel, P.; Whidborne, J.
Low Parametric Closed-Loop Sensitivity Realizations using Fixed-Point and Floating-Point Arithmetic Proceedings Article
In: Proc. European Control Conference (ECC'07), 2007.
@inproceedings{Hila07e,
title = {Low Parametric Closed-Loop Sensitivity Realizations using Fixed-Point and Floating-Point Arithmetic},
author = {T. Hilaire and P. Chevrel and J. Whidborne},
year = {2007},
date = {2007-01-01},
booktitle = {Proc. European Control Conference (ECC'07)},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}