Choice of Table Size

It is desirable that the stored filter impulse response be sampled sufficiently densely so that interpolating linearly between samples does not introduce error greater than the quantization error. We will show that this condition is satisfied whenever the filter table contains at least $L=2^{1+n_c/2}$ entries per zero-crossing, where $n_c$ is the number of bits allocated to each table entry.

Linear Interpolation Error Bound.

Let $h(t)$ denote the lowpass filter impulse response, and assume it is twice continuously differentiable for all $t$. By Taylor's theorem [166, p. 119], we have

$$h(t_0+\eta) = h(t_0) + \eta h^\prime(t_0) + {1\over 2} \eta^2 h^{\prime\prime}(t_0+\lambda \eta),$$

for some $\lambda \in[0,1]$, where $h^\prime(t_0)$ denotes the time derivative of $h(t)$ evaluated at $t=t_0$, and $h^{\prime\prime}(t_0)$ is the second derivative at $t_0$.

The linear interpolation error is defined as

$$\tilde{h}(t) \isdef h(t) - {\hat h}(t),$$

where $t=t_0+\eta$, $t_0=\lfloor t\rfloor$, $\eta=t-t_0$, and ${\hat h}(t)$ is the interpolated value given by

$${\hat h}(t) \isdef \overline{\eta}h(t_0) + \eta h(t_1),$$

where $\overline{\eta}\isdef 1-\eta$ and $t_1\isdef t_0+1$. Thus $t_0$ and $t_1$ are successive time instants for which samples of $h(t)$ are available, and $\eta\in[0,1)$ is the linear interpolation factor. (We ignore errors in the linear interpolation itself at this point.)

Expressing $h(t)$ as

$$h(t_0+\eta) = \overline{\eta}h(t_0+\eta) + \eta h(t_1-\overline{\eta})$$

applying Eq.$\,$(J.3.4) to both terms on the right-hand side, and subtracting Eq.$\,$(J.3.4) gives

$$\tilde{h}(t_0+\eta) = \eta\overline{\eta}\left[h^\prime(t_0) -h^\... ...ime\prime}(\xi_0)+\overline{\hat \eta}^{\prime\prime}(\xi_1) \over 2} \right],$$

where both $\xi_0$ and $\xi_1$ are in $[t_0,t_1]$. Defining

$$M_2 \isdef \max_{t} \left\vert h^{\prime\prime}(t)\right\vert$$

and noting that $h^\prime(t_1) = h^\prime(t_0) + h^{\prime\prime}(t_0+\lambda )$ for some $\lambda \in[0,1]$ which implies

$$\left\vert h^\prime(t_0) - h^\prime(t_1)\right\vert \leq M_2,$$

we obtain the upper bound

$$\left\vert\tilde{h}(t_0+\eta)\right\vert \leq \eta\overline{\eta}\left[M_2 + {M_2\over 2}\right]\leq {3\over 8} M_2.$$

Application to the Ideal Lowpass Filter.

For the ideal lowpass filter, we have

$$h(t) =$$   sinc$$(\omega_L t/ \pi) \isdef {\sin(\omega_L t)\over \omega_L t} = {1\over \omega_L}\int_0^{\omega_L}\cos(\omega t)\do ,$$

where $\omega_L=\pi/L$, and $L=2^{n_l}$ is the number of table entries per zero-crossing. Note that the rightmost form in Eq.$\,$(J.3.4) is simply the inverse Fourier transform of the ideal lowpass-filter frequency response. Twice differentiating with respect to $t$, we obtain

$$h^{\prime\prime}(t) = -{1\over\omega_L}\int_0^{\omega_L} \omega^2\cos(\omega t) \do,$$

from which it follows that the maximum magnitude is

$$M_2 = {\omega_L^2\over 3} = {\pi^2\over 3L^2}.$$

Note that this bound is attained at $t=0$. Substituting Eq.$\,$(J.3.4) into Eq.$\,$(J.3.4), we obtain the error bound

$$\left\vert\tilde{h}(t_0+\eta)\right\vert \leq {\pi^2\over 8 L^2} < {1.234\over L^2} = 1.234\cdot2^{-2n_l}.$$

Thus for the ideal lowpass filter $h(t)=$sinc$(t/L)$, the pointwise error in the interpolated lookup of $h(t)$ is bounded by $1.234/L^2$. This means that $n_l$ must be about half the coefficient word-length $n_c$ used for the filter coefficients. For example, if $h(t)$ is quantized to $16$ bits, $L$ must be of the order of $2^{16/2}=256$. In contrast, we will show that without linear interpolation, $n_l$ must increase proportional to $n_c$ for $n_c$-bit samples of $h(t)$. In the $16$-bit case, this gives $L\sim 2^{16}=65536$. The use of linear interpolation of the filter coefficients reduces the memory requirements considerably.

The error bounds obtained for the ideal lowpass filter are typically accurate also for lowpass filters used in practice. This is because the error bound is a function of $M_2$, the maximum curvature of the impulse response $h(t)$, and most lowpass designs will have a value of $M_2$ very close to that of the ideal case. The maximum curvature is determined primarily by the bandwidth of the filter since, generalizing equations Eq.$\,$(J.3.4) and Eq.$\,$(J.3.4),

$$h^{\prime\prime}(0) = -{1\over\pi}\int_0^{\pi} \omega^2 H(\omega) \do,$$

which is just the second moment of the lowpass-filter frequency response $H(\omega)$ (which is real for symmetric FIR filters obtained by symmetrically windowing the ideal sinc function [366]). A lowpass-filter design will move the cut-off frequency slightly below that of the ideal lowpass filter in order to provide a ``transition band'' which allows the filter response to give sufficient rejection at the ideal cut-off frequency which is where aliasing begins. Therefore, in a well designed practical lowpass filter, the error bound $M_2$ should be lower than in the ideal case.

Relation of Interpolation Error to Quantization Error.

If $h(t)\in[-1,1-2^{-n_c}]$ is approximated by $h_q(t)$ which is represented in two's complement fixed-point arithmetic, then

$$h_q(t_0) = -b_0 + \sum_{i=1}^{n_c-1} b_i 2^{-i},$$

where $b_i\in\{0,1\}$ is the $i$th bit, and the worst-case rounding error is

$$\left\vert h(t)-h_q(t)\right\vert \leq 2^{-n_c}.$$

Letting $h_q(t_i)=h(t_i)+\epsilon_i$, where $\vert\epsilon_i\vert\leq2^{-n_c}$, the interpolated look-up becomes

$${\hat h}_q(t_0+\eta) = \overline{\eta}h_q(t_0) + \eta h_q(t_1) = {\hat h}(t_0+\eta) + \overline{\eta}\epsilon_0 + \eta\epsilon_1.$$

Thus the error in the interpolated lookup between quantized filter coefficients is bounded by

$$\left\vert\tilde{h}_q(t)\right\vert \leq {3\over 8} M_2 + 2^{-n_c},$$

which, in the case of $h(t)=$sinc$(t/L)$, can be written

$$\left\vert\tilde{h}_q(t)\right\vert < {1.234\over L^2} + 2^{-n_c} = 1.234 \cdot 2^{-2n_l} + 2^{-n_c}.$$

If $L=2^{1+n_c/2}$, then $\vert\tilde{h}_q(t)\vert < 1.5\cdot 2^{-n_c}$, and the interpolation error is less than the quantization error by more than a factor of $2$.

Error in the Absence of Interpolation.

For comparison purposes, we derive the error incurred when no interpolation of the filter table is performed. In this case, assuming rounding to the nearest table entry, we have

$$\begin{eqnarray*} t & = & t_0+\eta,\qquad \left\vert\eta\right\vert\leq {1\over ... ...t\vert\tilde{h}(t)\right\vert & \leq &{M_1\over2} + {M_2\over8}, \end{eqnarray*}$$

where $M_1 \isdef \max_{t} \vert h^\prime(t)\vert$. For the ideal lowpass, we have

$$h^\prime(t) = -{1\over\omega_L}\int_0^{\omega_L}\omega\sin(\omega t) d\omega = {\omega_L t\cos(\omega_L t) - \sin(\omega_L t)\over \omega_L t^2} .$$

Note that $h^\prime(L)=1/L$ and $\vert h^\prime(t)\vert < \omega_L/2 = \pi/2L$. Thus $M_1=a/L$ where $1\leq a <\pi/2$. The no-interpolation error bound is then

$$\left\vert h^\prime(t)\right\vert \leq {a\over2L} + {\pi^2\over24L^2} < {0.7854\over L} + {0.4113\over L^2}.$$