Fractional Delay Filters Using the Farrow Structure

In the discussion on piecewise polynomial interpolation, we emphasized on the fact that the fractional interval $\mu_m$ needs to be updated for each symbol time $mT_M$ and hence the subscript $m$ in $\mu_m$. For this reason, the interpolation process becomes a two-step procedure.

1. Update the filter coefficients $h_p[n]$.
2. Perform the convolution between $z(nT_S)$ and $h_p[n]$.

This process can be simplified if the two steps above can be combined in such a way that $\mu_m$ update is weaved into the convolution operation. In other words, instead of a two-input hardware multiplication with two variable quantities, complexity can be reduced by restructuring the problem such that one input in the two-input hardware multiplication remains fixed. This is accomplished by separating the constant factors from the powers of $\mu_m$ in filter equations, which is discussed in detail below.

Cubic Interpolation

Odd degree polynomials approximate the interpolant by using an even number of samples that ensures the linear phase property. After $p=1$, the next odd degree polynomial is with $p=3$ and is known as cubic interpolation. Plugging $p=3$ in the interpolation equation,
\[
z(t) \approx c_p t^p + c_{p-1}t^{p-1} + \cdots + c_1 t + c_0
\]

we get
\begin{equation*}
z(t) \approx c_3t^3 + c_2 t^2 + c_1 t + c_0
\end{equation*}

Therefore,
\begin{align}
z(nT_S+\mu_m T_S) &\approx c_3 (nT_S+\mu_m T_S)^3 + c_2 (nT_S+\mu_m T_S)^2 + \nonumber \\
&\hspace{1.7in}c_1 (nT_S+\mu_m T_S) + c_0 \label{eqTimingSyncCubicInterpolation1}
\end{align}

Following the same derivation as in linear interpolation, the coefficients $c_3$, $c_2$, $c_1$ and $c_0$ need to be found every time $\mu_m$ changes. The four samples around the interpolant are given by
\begin{align*}
z((n-1)T_S) &= c_3((n-1)T_S)^3 + c_2((n-1)T_S)^2 + c_1(n-1)T_S + c_0 \\
z(nT_S) &= c_3(nT_S)^3 + c_2 (nT_S)^2 + c_1 nT_S+c_0 \\
z((n+1)T_S) &= c_3((n+1)T_S)^3 + c_2((n+1)T_S)^2 + c_1(n+1)T_S + c_0 \\
z((n+2)T_S) &= c_3((n+2)T_S)^3 + c_2((n+2)T_S)^2 + c_1(n+2)T_S + c_0
\end{align*}

These are four equations with four unknowns that can be easily solved to compute $c_3$, $c_2$, $c_1$ and $c_0$. Substituting them back in Eq~\eqref{eqTimingSyncCubicInterpolation1} yields

As before, the desired interpolant can again be written as the output of a filter as
\begin{align}
z(nT_S+\mu_m T_S) &= h_3[-2] z((n+2)T_S) + h_3[-1] z((n+1)T_S) + \nonumber\\
&\hspace{1.3in}h_3[0] z(nT_S) + h_3[1] z((n-1)T_S) \nonumber\\
&= \sum \limits _{i=-2} ^1 h_3[i] z((n-i)T_S) \label{eqTimingSyncCubicFiltering}
\end{align}
where the filter coefficients are given by
$$ \begin{equation}
\begin{aligned}
h_3[-2] &= \frac{\mu_m^3}{6}- \frac{\mu_m}{6} \\
h_3[-1] &= -\frac{\mu_m^3}{2}+\frac{\mu_m^2}{2}+\mu_m\\
h_3[0] &= \frac{\mu_m^3}{2}-\mu_m^2-\frac{\mu_m}{2}+1\\
h_3[1] &= -\frac{\mu_m^3}{6}+\frac{\mu_m^2}{2} – \frac{\mu_m}{3}
\end{aligned}
\end{equation}\label{eqTimingSyncCubicFilter}$$

In the above equations, the subscript $3$ denotes cubic interpolation as $p=3$. An example of cubic interpolation is drawn in the figure below.

Observe how the curve has been smoothed out as compared to linear interpolation. This gain comes at a price of higher computational complexity paid for cubic interpolation.

Simplification through Farrow Technique

Begin with filter coefficients from cubic interpolation in Eq (\ref{eqTimingSyncCubicFilter}) and rewrite it as
\begin{align*}
h_3[-2] &= \frac{1}{6}\mu_m^3 + 0\cdot\mu_m^2 – \frac{1}{6}\mu_m + 0 \\
&= b_3[-2]\mu_m^3 + b_2[-2]\mu_m^2 +b_1[-2]\mu_m^1 + b_0[-2]\mu_m^0 = \sum \limits_{l=0}^{3} b_l[-2]\mu_m^l
\end{align*}

where $b_3[-2] = 1/6$, $b_2[-2]=0$, etc. Similarly, for other coefficients, we can write
\begin{align*}
h_3[-1] &= -\frac{1}{2}\mu_m^3+\frac{1}{2}\mu_m^2+1\cdot\mu_m + 0 = \sum \limits_{l=0}^{3} b_l[-1]\mu_m^l \\
h_3[0] &= \frac{1}{2}\mu_m^3-1\cdot\mu_m^2-\frac{1}{2}\mu_m+1 = \sum \limits_{l=0}^{3} b_l[0]\mu_m^l \\
h_3[1] &= -\frac{1}{6}\mu_m^3+\frac{1}{2}\mu_m^2 – \frac{1}{3}\mu_m+0 = \sum \limits_{l=0}^{3} b_l[1]\mu_m^l
\end{align*}

In general,
\begin{equation*}
h_3[i] = \sum \limits_{l=0}^{3} b_l[i]\mu_m^l
\end{equation*}

Observe that $b_l[i]$ are fixed coefficients independent of $\mu_m$ in the above expression and are given in the table below.

With this understanding in place, the filtering process from Eq (\ref{eqTimingSyncCubicFiltering}) can be rearranged such that convolution of the matched filter output is performed with the fixed coefficients $b_l[i]$.
\begin{align*}
z(nT_S+\mu_m T_S) &= \sum \limits _{i=-2} ^1 h_3[i] z((n-i)T_S)\\
&= \sum \limits _{i=-2} ^1 \cdot \sum \limits_{l=0}^{3} b_l[i]\mu_m^l \cdot z((n-i)T_S)\\
&= \sum \limits_{l=0}^{3}\mu_m^l \underbrace{\sum \limits _{i=-2} ^1 b_l[i] \cdot z((n-i)T_S)}_{y(l)}\\
&= \sum \limits_{l=0}^{3} y(l) \mu_m^l
\end{align*}

To obtain a hardware efficient filter structure known as Farrow structure, the above expression can be opened as
\begin{align*}
z(nT_S+\mu_m T_S) &= y(3)\mu_m^3 + y(2)\mu_m^2 + y(1)\mu_m^1 + y(0)\mu_m^0\\
&= \Big\{y(3)\mu_m^2 + y(2)\mu_m + y(1)\Big\}\mu_m + y(0)
\end{align*}

One more such step produces the Farrow structure for a cubic interpolator.

The Farrow structure for cubic interpolation is drawn in the figure below where $T_S$ is a sample delay. Notice the fixed coefficients $b_l[i]$ operating on the matched filter output samples while a changing $\mu_m$ operates on the subsequent output $y(l)$. Although its block diagram looks complicated, the expression above is quite simple. Click on the figure to see the enlarged image.

A similar strategy can be applied to devise Farrow structures for polynomial interpolation for the cases when $p \neq 3$. For example, for $p=2$, it is given by
\begin{equation*}
z(nT_S+\mu_m T_S) = \Big\{y(2)\mu_m +y(1)\Big\}\mu_m + y(0)
\end{equation*}