Arithmetic Approaches for Rigorous Design of Reliable Fixed-Point LTI Filters

• Published in: IEEE transactions on computers 2020-04, Vol.69 (4), p.489-504
• Main Authors: Volkova, Anastasia, Hilaire, Thibault, Lauter, Christoph
• Format: Article
• Language: English
• Subjects: Algorithms; Arithmetic; Computer Arithmetic; Computer Science; Computer simulation; Digital filters; eigendecomposition; Error analysis; Evaluation; Filter design (mathematics); Fixed point arithmetic; Floating point arithmetic; Gershgorin circles; Heuristic algorithms; interval arithmetic; Linear matrix inequalities; Linear systems; Mathematical model; Mathematical Software; Model accuracy; multiple precision; Numerical Analysis; Reliability; reliable computations; Rounding; Signal and Image Processing; Signal processing algorithms; table maker's dilemma
• ISSN: 0018-9340; 1557-9956
• DOI: 10.1109/TC.2019.2950658

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.