Ce projet de recherche doctorale est publié a été réalisé par Laurent-Stéphane Didier
Description d'un projet de recherche doctoral
OPTIMAL FILTER IMPLEMENTATION IN FIXED-POINT ARITHMETIC
Résumé du projet de recherche (Langue 1)
Scientific context and subject description: Most of the control or signal processing systems are implemented in digital general-purpose processors, Digital Signal Processors (DSPs), Field Programmable Gate-Array (FPGAs), and so forth. Because these devices cannot compute with infinite precision and approximate real-number parameters with a finite binary representation, the numerical implementation of controllers (filters) leads to deterioration in characteristics and performance. This has two separate origins, corresponding to the quantization of the embedded coefficients and the round-off errors occurring during the computations. The fixed-point implementation of such algorithms and their finite precision performance are related to: a) their algorithmic relationship (it is well known that these finite wordlength effects depend on the structure of the realization. For example, in state-space form, the realization depends on the choice of the basis of the state-vector); b) the implementation scheme (depending on the target, the wordlength, the operators, the order of the computations, the quantization modes, etc. can be used as free parameters). This leads to various multi-objective optimization problems where, for example, the finite precision effects and the computational cost should be minimized.. In this thesis, we will focus on investigating and defining finite precision criteria and implementation criteria (area and/or power consumption, execution time, parallelism of operations according to the target resources, etc.). Based on the experience of the LIP6 on optimal realization filter and nonlinear programming methods, the PhD candidate will work on the implementation formalization and the exploration of the associated decision-space. Appropriate exact methods or heuristics will be proposed and applied to solve this multi-objective optimization problem. The theoretical achievements of this work will be implemented and included in the FWR Toolbox or SOFA tools developed at the LIP6. This work will be a part of the national project "DEFIS" (Design of fixed-point embedded systems) funded by ANR (Agence Nationale de la Recherche), in cooperation with three other academic lab (IRISA (Cairn Project), LIRMM (Dali team) and CEA (LMeASI)) and two industrial partners (Thales (Embedded System Laboratory) and InPixal). ______________________________________________________ Advisors: Laurent-Stephane DIDIER (firstname.lastname@example.org) and Thibault HILAIRE (email@example.com) both associate professor at the Universite Pierre et Marie Curie (Paris 6) ______________________________________________________ Practical details: This is a three years PhD studentship funded by ANR. The position is expected to start in October or November 2011. The student will be enrolled in the LIP6 (Laboratory of Computing Sciences of the Universite Pierre et Marie Curie (Paris 6), http://www.lip6.fr) and will be based at campus Jussieu located in Paris (4 place Jussieu, 75005 Paris). ______________________________________________________ How to apply: Applicants must have a Master degree in Computer Science, Applied Mathematics or other relevant field. Good programming skills are required. Experience with embedded systems, hardware architecture, algorithmic optimization and/or signal processing algorithms is a plus. Applicants should email a CV and contact information of one reference to firstname.lastname@example.org and email@example.com. ______________________________________________________ References:  G. Constantinides, P.Y.K. Cheung, and W. Luk. Synthesis and Optimization of DSP Algorithms. Kluwer Academic Publishers, 2004.  M. Gevers and G. Li. Parametrizations in Control, Estimation and Filtering Problems. Springer-Verlag, 1993.  Kyungtae Han and Brian L. Evans. Optimum wordlength search using sensitivity information. EURASIP J. Appl. Signal Process., 2006, January 2006.  H. Hanselmann. Implementation of digital controllers - a survey. Automatica, 23(1):7-32, January 1987.  N. Herve, D. Menard, and O. Sentieys. Data Wordlength Optimization for FPGA Synthesis. In IEEE International Workshop on Signal Processing Systems, (SIPS 2005), pages 623-628, Athens, Grece, November 2005.  T. Hilaire. Towards tools and methodology for the fixed-point implementation of linear filters. In Proc. IEEE Digital Signal Processing workshop (DSP'11), January 2011.  T. Hilaire, P. Chevrel, and J.F. Whidborne. Finite wordlength controller realizations using the specialized implicit form. Int. Journal of Control, 83(2):330-346, February 2010.  T. Hilaire, D. Menard, and O. Sentieys. Bit accurate roundoff noise analysis of fixed-point linear controllers. In Proc. IEEE Int. Symposium on Computer-Aided Control System Design (CACSD'08), September 2008.  T. Hinamoto, S. Yokoyama, T. Inoue, W. Zeng, and W. Lu. Analysis and minimization of L2-sensitivity for linear systems and two-dimensional state-space filters using general controllability and observability gramians. IEEE Transactions on Circuits and Systems, Fundamental Theory and Applications, 49(9), september 2002.  R. Istepanian and J.F. Whidborne. Digital controller implementation and fragility a modern perspective. Springer, 2001.  S. Kim, K. Kum, and S. Wonyong. Fixed-Point Optimization Utility for C and C++ Based Digital Signal Processing Programs. IEEE Transactions on Circuits and Systems II, 45(11):1455-1464, November 1998.  G. Li, C. Wan, and G. Bi. An improved rho-DFIIt structure for digital filters with minimum roundoff noise. IEEE Trans. on Circuits and Systems, 52(4):199-203, April 2005.  D. Menard and O. Sentieys. Automatic Evaluation of the Accuracy of Fixed-point Algorithms. In Design, Automation and Test in Europe 2002 (DATE 2002), Paris, France, March 2002.  S. Roy and P. Banerjee. An algorithm for trading off quantization error with hardware resources for matlab-based FPGA design. IEEE Transactions on Computers, 54:886-896, July 2005.  B. Widrow and I. Kollar. Quantization Noise: Roundoff Error in Digital Computation, Signal Processing, Control, and Communications. Cambridge University Press, Cambridge, UK, 2008.
Résumé du projet de recherche (Langue 2)
The main objective is to provide, for a given filter and target, an optimal fixed-point implementation (i.e. fixed-point algorithm and/or final code for the target) satisfying an appropriate trade-off (in a sense to define) of precision and performance versus area, power consumption and/or execution time.