Farrow Filter of Signal Digital Resampling on the Basis of Spline Interpolation

Contents

Introduction

In the previous section we considered digital resamplers on the basis of Lagrange piecewise and polynomial interpolation. The equation for polynomial coefficients was received in the form of:

\begin{equation*}
\begin{array}
&
\mathbf{a} = \mathbf{M^{-1}} \cdot
\mathbf{s} = \left[
\begin{array}{cccc}
0 & 0 & 1 & 0\\
\frac{1}{6} & -1 & \frac{1}{2} & \frac{1}{3}\\
0 & \frac{1}{2} & -1 & \frac{1}{2}\\
-\frac{1}{6} & \frac{1}{2} & -\frac{1}{2}& \frac{1}{6}\\
\end{array}
\right]
\cdot
\left[
\begin{array}{c}
s(n-3) \\ s(n-2) \\ s(n-1) \\ s(n)\\
\end{array}
\right],
\end{array}
\end{equation*}

(1)

where $\mathbf{a}$ is a vector of polynomial coefficients, $\mathbf{M^{-1}}$is an inverse system matrix, $\mathbf{s}$ is a vector of delayed input signal samples.

As a result of multiplier minimization equations for polynomial coefficients were received:

$$
\begin{cases}
a_0 = s(n-1),\\
a_3= \frac{1}{6} \cdot \left( s(n) - s(n-3)\right) + \frac{1}{2} \cdot \left( s(n-2) - s(n-1)\right), \\
a_1 = \frac{1}{2} \cdot \left( s(n) - s(n-2) \right)-a_3,\\
a_2 = s(n) - s(n-1) - a_1 - a_3.\\
\end{cases}
$$

(2)

The functional chart of the optimized signal digital resampling filter on the basis of Lagrange piecewise and polynomial interpolation corresponding to (2) is given in Figure 1.

Figure 1. Functional Chart of the Optimized Digital Resampling Filter

Thus, we received the filter structure which calculates coefficients of Lagrange polynomial interpolation using only one multiplier by $\frac{1}{6}$ and two trivial multipliers by $\frac{1}{2}$.

We also considered in details examples of using Farrow filter for problems of signal digital resampling including digital compensation of fractional delay and signal interpolation.

Upon considering examples we mentioned that the pulse characteristic $h(n)$ of Farrow filter under signal digital interpolation has no continuous derivative in interpolation knots.
As a result, the rejection level within the scope of the received filter blocking is only 28 dB as it is shown in Figure 2.

Figure 2. Pulse Characteristic and AFR of Digital Interpolation Farrow Filter

Besides Lagrange interpolation there are also other methods of piecewise and polynomial interpolation, for example, spline interpolation [1] which provides continuous derivatives in interpolation knots in contrast to Lagrange polynomial interpolation.

In this section we will consider creating Farrow filter on the basis of Hermite splines [1].

Creating Cubic Hermite Spline

Upon creating cubic Lagrange polynomial four signal samples $s(n) \ldots s(n-3)$ are used and the received polynomial interpolation $p(t)$ passes through these knots as it is shown in Figure 3a.

Figure 3. Creating Polynomial Interpolation: a - Cubic Lagrange Polynomial b - Cubic Hermite Spline

However such creating polynomial does not impose restrictions upon values of derivatives in extreme points $t = 1$ and $t = -2$. As a result there is discontinuity of the pulse characteristic derivative of the interpolator filter as it is shown in Figure 2.
To provide derivative continuity upon “conjugating” cubic polynomial we will use cubic Hermite spline which is created in the interval $t = [-1 \ldots 0]$ as it is shown in Figure 3b.

We will calculate Hermite spline coefficients by solving the linear equations set. Two set equations result from Figure 3b:

\begin{eqnarray*}
{
\begin{cases}
p(0)= s(n-1),
\\
p(-1) = s(n-2);
\end{cases}
}
&
\Longrightarrow
&
{
\begin{cases}
a_0 + a_1 \cdot 0 + a_2 \cdot 0^2 + a_3 \cdot 0^3 = s(n-1),
\\
a_0 + a_1 \cdot (-1) + a_2 \cdot (-1)^2 + a_3 \cdot (-1)^3 = s(n-2).
\end{cases}
}
\end{eqnarray*}

(3)

It is necessary to add two more equations into the set (3).
For this purpose we demand for Hermite spline derivatives $p^\prime(t)$ in the knots $t = 0$ and $t = -1$ to be equal to derivatives of the input signal $s^\prime(n)$ in these points, i.e.

\begin{eqnarray*}
{
\begin{cases}
p^\prime(0)= s^\prime(n-1),
\\
p^\prime(-1) = s^\prime(n-2);
\end{cases}
}
&
\Longrightarrow
&
{
\begin{cases}
a_1 + 2 \cdot a_2 \cdot 0 + 3 \cdot a_3 \cdot 0^2 = s^\prime(n-1),
\\
a_1 + 2 \cdot a_2 \cdot (-1) + 3\cdot a_3 \cdot (-1)^2 = s^\prime(n-2).
\end{cases}
}
\end{eqnarray*}

(4)

Uniting Equations (3) and (4) in the unified equations set to calculate cubic Hermite spline coefficients, we get:

\begin{equation*}
\begin{cases}
a_0 &+ & a_1 \cdot 0 + a_2 \cdot 0^2 + a_3 \cdot 0^3 & = s(n-1),
\\
a_0 & + & a_1 \cdot (-1) + a_2 \cdot (-1)^2 + a_3 \cdot (-1)^3 & = s(n-2),
\\
& & a_1 + 2 \cdot a_2 \cdot 0 + 3 \cdot a_3 \cdot 0^2 & = s^\prime(n-1),
\\
& & a_1 + 2 \cdot a_2 \cdot (-1) + 3\cdot a_3 \cdot (-1)^2 & = s^\prime(n-2),
\end{cases}
\end{equation*}

(5)

Or in the matrix form:

\begin{equation*}
\begin{array}
&
\mathbf{M \cdot a = s}
&
\Longrightarrow
&
\left[
\begin{array}{cccc}
1 & 0 & 0 & 0 \\
1 & -1 & 1 & -1 \\
0 & 1 & 0 & 0\\
0 & 1 & -2 & 3
\end{array}
\right]
&
\cdot
&
\left[
\begin{array}{cccc}
a_0 \\ a_1 \\ a_2 \\ a_3
\end{array}
\right]
&
=
&
\left[
\begin{array}{cccc}
s(n-1) \\ s(n-2) \\s^\prime(n-1) \\ s^\prime(n-2)
\end{array}
\right].
\end{array}
\end{equation*}

(6)

Then the system solution (6) can be as follows:

\begin{equation*}
\begin{array}
&
\mathbf{ a = M^{-1} \cdot s}
&
\Longrightarrow
&
\left[
\begin{array}{cccc}
a_0 \\ a_1 \\ a_2 \\ a_3
\end{array}
\right]
&
=
&
\left[
\begin{array}{cccc}
1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 \\
-3 & 3 & 2 & 1\\
-2 & 2 & 1 & 1
\end{array}
\right]
&
\cdot
&
\left[
\begin{array}{cccc}
s(n-1) \\ s(n-2) \\s^\prime(n-1) \\ s^\prime(n-2)
\end{array}
\right].
\end{array}
\end{equation*}

(7)

After multiplying the return matrix $\mathbf{M^{-1}}$ by the vector $\mathbf{s}$ we get the equations for cubic Hermite spline coefficients in the form:

\begin{equation*}
\begin{cases}
a_0 = s(n-1),
\\
a_1 = s^\prime(n-1),
\\
a_2 = -3 \cdot s(n-1) + 3 \cdot s(n-2) + 2 \cdot s^\prime(n-1) + s^\prime(n-2),
\\
a_3 = -2 \cdot s(n-1) + 2 \cdot s(n-2) + s^\prime(n-1) + s^\prime(n-2).
\end{cases}
\end{equation*}

(8)

Thus, we received the equations for cubic Hermite spline coefficients. At the same time the coefficients depend on values of signal derivatives $s^\prime(n-1)$ and $s^\prime(n-2)$ which we have to value taking into account input signal samples.

Values of a Discrete Signal Derivative

The numerical differentiation problem of discretely set signals is solved when using approximation of a signal derivative by means of final differences.
The simplest derivative approximation is the finite difference of the form:

$$
s^\prime(n-1) \approx s(n-1) - s(n-2),
\\
s^\prime(n-2) \approx s(n-2) - s(n-3).
$$

(9)

Values of derivatives (9) are realized upon using the input signal linear interpolation. This method requires only one subtraction, however, it has the greatest inaccuracy as the residual member in case of derivative value (9) is equal to $O(h)$ [2], i.e. it decreases linearly with reducing the sampling step.

The more exact derivative value method is the central difference method:

$$
s^\prime(n-1) \approx \frac{s(n) - s(n-2)}{2},
\\
s^\prime(n-2) \approx \frac{s(n-1) - s(n-3)}{2}.
$$

(10)

The central difference results from the derivative value with using the input signal parabolic interpolation, and the residual member in case of the derivative value (10) is equal to $O(h^2)$ [2], i.e. it decreases quadratically in case of reducing the sampling step $h$.

At the same time the central difference (10) requires additional multiplication by $\frac{1}{2}$ which can be realized in integer arithmetics as the single position shifting to the right.

Thus, we can use values of derivative (10) in Equation (8) to calculate Hermite spline coefficients and provide derivative continuity at the digital resampling filter output.

Optimized Structure of Farrow Filter on the Basis of Hermite Splines

Plug (10) into (8) and get equations for Hermite spline coefficients in the form:

\begin{equation*}
\begin{cases}
a_0 = s(n-1),
\\
a_1 = \frac{1}{2}\cdot (s(n) - s(n-2)),
\\
a_2 = -3 \cdot s(n-1) + 3 \cdot s(n-2) + s(n) - s(n-2) + \frac{1}{2}\cdot (s(n-1) - s(n-3)),
\\
a_3 = -2 \cdot s(n-1) + 2 \cdot s(n-2) + \frac{1}{2}\cdot (s(n) - s(n-2)) + \frac{1}{2}\cdot (s(n-1) - s(n-3)).
\end{cases}
\end{equation*}

(11)

Equation (11) allows to note that:

$$
a_2 - a_3 = -s(n-1) + s(n-2) + \underbrace{\frac{1}{2}\cdot (s(n) - s(n-2))}_{a_1},
$$

(12)

then

$$
a_2 = s(n-2)-s(n-1) + a_3 + a_1,
$$

(13)

and finally it is possible to write down:

$$
\begin{cases}
a_0 = s(n-1),
\\
a_1 = \frac{1}{2}\cdot \Big(s(n) - s(n-2)\Big),
\\
a_3 = 2 \cdot \Big(s(n-2) - s(n-1)\Big) + a_1 + \frac{1}{2}\cdot \Big(s(n-1) - s(n-3)\Big),
\\
a_2 = s(n-2)-s(n-1) + a_3 + a_1.
\end{cases}
$$

(14)

Calculation of Hermite spline coefficients requires only multiplication by $2$ and $\frac{1}{2}$ which can be considered as trivial.
Besides we can get rid of multiplication by $\frac{1}{2}$ when calculating $a_3$ if we consider that $\frac{1}{2}\cdot \Big(s(n-1) - s(n-3)\Big)$ is nothing but the delayed single position value $a_1 = \frac{1}{2}\cdot \Big(s(n) - s(n-2)\Big)$.

The functional chart of the optimized digital resampling filter on the basis of cubic Hermite splines is shown in Figure 4.

Figure 4. Optimized Digital Resampling Filter on the Basis of Cubic Hermite Splines

Comparing Figures 1 and 4, it is possible to note that the optimized digital resampling filter on the basis of cubic Hermite splines requires only one trivial multiplication by $\frac{1}{2}$ (multiplication by 2 can be replaced with one adder) while the filter on the basis of Lagrange polynomial interpolation requires two trivial multiplication by $\frac{1}{2}$ and one multiplier by $\frac{1}{6}$. The total quantity of adders required to calculate coefficients is also less when using cubic Hermite splines.

Conclusions

In this section the Farrow filter structure of signal digital resampling on the basis of cubic Hermite splines is considered. The question of input signal derivative values to provide derivative continuity when using cubic Hermite splines is also considered.

The received digital resampling filter requires only one multiplication by $\frac{1}{2}$ which can be considered as trivial. The total quantity of adders required to calculate polynomial coefficients is also less when using cubic Hermite splines in comparison with Lagrange polynomial interpolation.

In the following section we will consider examples of using the Farrow filter of signal digital resampling on the basis of cubic Hermite splines and compare results of this using with the signal resampling filter on the basis of Lagrange polynomial interpolation.

You can provide your any feedbacks, questions and wishes in the message board or guestbook.

Reference

[1]
Kahaner D., Moler C., Nash S.
Numerical Methods and Software.
Prentice Hall, 1988.

[2]
Farrow C.W.
A Continuously Variable Digital Delay Element.
Circuits and Systems, IEEE International Symposium. 1988, p. 2641–2645. vol. 3

[3]
Gardner Floyd M.
Interpolation in Digital Modems-Part I: Fundamentals:
IEEE Transactions on Communications, Vol. 41, No. 3, March 1993, P. 501-507.

[4]
Erup L., Gardner Floyd M., Harris Robert A.
Interpolation in Digital Modems-Part II: Implementation and Performance:
IEEE Transactions on Communications, Vol. 41, No. 6, June 1993, p.998-1008.

[5]
Franck A.
Efficient Algorithms for Arbitrary Sample Rate
Conversion with Application to Wave Field
Synthesis.
PhD thesis. Universitätsverlag Ilmenau, Ilmenau, 2012. [PDF]

[6]
McConnell J.
Analysis of Algorithms: An Active Learning Approach.
Jones and Bartlett Publishers, 2001.