F. Perez-Gonzalez, D. Docampo, and C. Abdallah, "Bounding the frequency response for digital transfer functions: results and applications", Proc. of IEEE Digital Signal Processing Workshop, 1994, pp. 15-18.

A {\it digital filter} is a linear processing device that transforms the incoming signal $x(n)$, $n=\ldots,0,1,2,\ldots,$ into a {\it filtered} signal $y(n)$ so that $$y(n)-\sum a_ky(n-k)=\sum b_k x(n-k)$$ for some coefficients $a_k$ and $b_k$. Digital filters can increase signal-to-noise ratio and compensate for the distortions imposed by the measuring device. An important characteristic of a filter is its (complex) {\it frequency characteristic} $H(z)=H(\exp(i\omega))$ that describes how the filter transforms a sinusoidal periodic signal: if $x(n)=x(\omega)\exp(i\omega n)$, then $y(n)=y(\omega)\exp(i\omega n)$, where $y(\omega)=H(\exp(i\omega))x(\omega)$.

If we know the coefficients $a_k$, $b_k$ precisely, then, for every $\omega$, we can compute $H(z)$ as $H(z)=B(z)/A(z)$, where $B(z)=\sum b_kz_k$ and $A(z)=1+\sum a_kz^k$. In real life, we often know only the {\it intervals} $\bf a_k$ and $\bf b_k$ of possible values of the coefficients $a_k$ and $b_k$; in this case, we must describe the set of possible values of $H(z)$.

In principle, we can consider real and imaginary parts of $H(z)$, and apply interval computations to find a box that contains all possible values of $H(z)$. However, this box is an {\it overestimation} of the desired set (in the sense that not all values from the box are possible).

In the paper under review, the authors describe a simple (quadratic-time) algorithm that, given $\omega$ and the intervals $ a_k$ and $ b_k$, describes the exact polygons of possible values of $A(z)$ and $B(z)$, and thus, enables us to describe the set of possible values of the ratio $H(z)=A(z)/B(z)$. As a result, the authors get exact bounds on the magnitude and phase of the frequency response $H(z)$.

Sergio Cabrera