class sdr.FarrowFractionalDelay

Implements a piecewise polynomial Farrow fractional delay filter.

Consider the series of input samples \(x[n-D], \ldots, x[n], \ldots, x[n+p-D]\). The goal is to interpolate the value of \(x(t)\) at the time \(t = n + \mu\). The Lagrange polynomial interpolation is computed as

\[x[n + \mu] = \sum_{k=0}^{p} x[n + k - D] \cdot \ell_k(\mu) ,\]

where \(D\) is the delay offset (usually so the center tap is at zero) and \(\ell_k(\mu)\) is the Lagrange basis polynomial corresponding to tap \(k\). Note that \(\ell_k(\mu)\) is independent of the data and only depends on the fractional shift \(\mu\).

The \(k\)-th Lagrange basis polynomial is defined as

\[\begin{split}\ell_k(\mu) = \prod_{\substack{j=0 \\ j \ne k}}^{p} \frac{\mu - j}{k - j} ,\end{split}\]

which is a polynomial of degree \(p\) in \(\mu\). The Lagrange basis polynomials are 1 at \(\mu = k\) and 0 at \(\mu = j\) for \(j \ne k\).

It is often desirable to change \(\mu\) on the fly, which means that the Lagrange basis polynomials must be recomputed for each new value of \(\mu\). Instead, the Farrow structure selects the coefficients of each Lagrange basis polynomial for a given degree of \(\mu\) and forms it into a correlator

\[h_m[n] = \{\ell_{0,m}, \ell_{1,m}, \ldots, \ell_{p,m}\} ,\]

where \(h_m[n]\) is the \(m\)-th correlator and \(\ell_{k,m}\) is the coefficient of \(\mu^m\) in the \(k\)-th Lagrange basis polynomial.

The output of the \(m\)-th correlator is

\[z_m[n] = x[n] \star h_m[n] = \sum_{k=0}^{p} x[n + k - D] \cdot \ell_{k,m} .\]

The Farrow structure allows the interpolation calculation to be reorganized as

\[x[n + \mu] = \sum_{k=0}^{p} x[n + k - D] \cdot \ell_k(\mu) = \sum_{k=0}^{p} z_m[n] \cdot \mu^k .\]

which can be efficiently computed using Horner’s method.

\[x[n + \mu] = \sum_{k=0}^{p} z_m[k] \cdot \mu^k = z_0[n] + \mu \cdot (z_1[n] + \mu \cdot (z_2[n] + \ldots)) .\]

References

Examples

Plot the 3rd order Lagrange basis polynomials. Notice that each polynomial is 1 and 0 at the corresponding indices.

In [1]: farrow = sdr.FarrowFractionalDelay(3)

In [2]: mu = np.linspace(0, farrow.order, 1000) - farrow.lookahead

In [3]: plt.figure();

In [4]: for i in range(0, farrow.order + 1):
   ...:     y = np.poly1d(farrow.lagrange_polys[i])(mu)
   ...:     sdr.plot.time_domain(mu, y, label=rf"$\ell_{i}(\mu)$");
   ...: 

In [5]: plt.xlabel("Fractional sample delay, $\mu$"); \
   ...: plt.title("3rd order Lagrange basis polynomials");
   ...:
../../_images/sdr_FarrowFractionalDelay_1.svg

Suppose a signal \(x[n]\) is to be interpolated. The interpolated signal \(y[n]\) is calculated by evaluating the Lagrange interpolating polynomial at the fractional sample delay \(\mu\) and scaling by the input signal \(x[n]\).

In [6]: x = np.array([1, 3, 2, 0])

In [7]: y = 0;

In [8]: for i in range(0, farrow.order + 1):
   ...:     y += x[i] * np.poly1d(farrow.lagrange_polys[i])(mu)
   ...: 

In [9]: plt.figure(); \
   ...: sdr.plot.time_domain(x, offset=-farrow.lookahead, marker=".", linestyle="none", label="Input"); \
   ...: sdr.plot.time_domain(mu, y, label="Interpolated"); \
   ...: plt.title("3rd order Lagrange interpolation");
   ...:
../../_images/sdr_FarrowFractionalDelay_2.svg

Compare fractional sample delays for various order Farrow fractional delay filters.

In [10]: sps = 6; \
   ....: span = 4; \
   ....: x = sdr.root_raised_cosine(0.5, span, sps, norm="power")
   ....: 

In [11]: mu = 0.25; \
   ....: plt.figure(); \
   ....: sdr.plot.time_domain(x, marker=".", color="k"); \
   ....: sdr.plot.time_domain(sdr.FarrowFractionalDelay(1)(x, mu=mu), label="Farrow 1"); \
   ....: sdr.plot.time_domain(sdr.FarrowFractionalDelay(2)(x, mu=mu), label="Farrow 2"); \
   ....: sdr.plot.time_domain(sdr.FarrowFractionalDelay(3)(x, mu=mu), label="Farrow 3"); \
   ....: plt.title(f"Fractional advance {mu} samples");
   ....: 

In [12]: mu = 0.5; \
   ....: plt.figure(); \
   ....: sdr.plot.time_domain(x, marker=".", color="k"); \
   ....: sdr.plot.time_domain(sdr.FarrowFractionalDelay(1)(x, mu=mu), label="Farrow 1"); \
   ....: sdr.plot.time_domain(sdr.FarrowFractionalDelay(2)(x, mu=mu), label="Farrow 2"); \
   ....: sdr.plot.time_domain(sdr.FarrowFractionalDelay(3)(x, mu=mu), label="Farrow 3"); \
   ....: plt.title(f"Fractional advance {mu} samples");
   ....: 

In [13]: mu = 1; \
   ....: plt.figure(); \
   ....: sdr.plot.time_domain(x, marker=".", color="k"); \
   ....: sdr.plot.time_domain(sdr.FarrowFractionalDelay(1)(x, mu=mu), label="Farrow 1"); \
   ....: sdr.plot.time_domain(sdr.FarrowFractionalDelay(2)(x, mu=mu), label="Farrow 2"); \
   ....: sdr.plot.time_domain(sdr.FarrowFractionalDelay(3)(x, mu=mu), label="Farrow 3"); \
   ....: plt.title(f"Fractional advance {mu} samples");
   ....:
../../_images/sdr_FarrowFractionalDelay_3.svg ../../_images/sdr_FarrowFractionalDelay_4.svg ../../_images/sdr_FarrowFractionalDelay_5.svg

Constructors

FarrowFractionalDelay(order: int, alpha: float = 0.5, ...)

Creates a new Farrow arbitrary fractional delay filter.

Special methods

__call__(x: ArrayLike, m: ArrayLike | None = None, ...) → NDArray

Applies the fractional sample advance \(\mu(k)\) to the input signal \(x[n]\) at the given basepoint sample indices \(m(k)\).

Streaming mode only

reset()

Resets the filter state.

property streaming : bool

Indicates whether the filter is in streaming mode.

property state : NDArray

The filter state consisting of the previous self.taps.shape[1] - 1 inputs.

Properties

property order : int

The order \(p\) of the Lagrange interpolating polynomial.

property lagrange_polys : NDArray

The Lagrange basis polynomials \(\ell_k(\mu)\).

property taps : NDArray

The Farrow filter taps.

property delay : int

The delay \(D\) of the Farrow FIR filters in samples.

property lookahead : int

The number of samples needed before the current input sample.