Farrow filters using the example of a third-order filter. Resampling signals

To change the sampling frequency, or to shift the discrete signal in phase by a value smaller than the sampling interval, it is necessary to present the discrete signal as a continuous function of time and resampling it or else they say resampling.

Let there be discrete signal samples . You need to resample and get discrete signal samples as shown in Figure 1. The sampling interval . Black shows the original signal, red - the result of resampling.

In order to perform resampling, it is necessary for the existing discrete signal interpolate, i.e. continuous signal recovery then calculate its discrete values ​​for each new . Interpolation can be done in various ways, in this article we will discuss polynomial interpolation.

Polynomial interpolation. Polynomial representation

In the course of mathematical analysis it is proved that through points passes a polynomial degrees and with only one. For example, through two points it is possible to draw only one straight line, through three points only one parabola, and so on. Respectively through you can also draw a single polynomial of degree which will be the result of interpolation, that is:

Consider the expression (1) in more detail, namely, open the sum:

Put out in expression (2) for brackets:

We will again for brackets:

Thus enduring the possible number of times for brackets, we get a set of nested brackets:

A scheme for calculating the values ​​of a polynomial (5) with known coefficients is presented in Figure 2.

The first multiplier returns then added the “innermost brackets” of the expression (5) is obtained . "Innermost brackets" are multiplied by and so on all the brackets are collected and it turns out .

Consider an example for . Get the cubic polynomial:

The scheme for calculating a cubic polynomial is presented in Figure 3.

Thus, we need to get the coefficients of the polynomial based on discrete readings . To do this, you can create a system of linear equations:

However, this requires solving the system of equations for each new value . In addition, to solve the system of equations, matrix inversion is required, which is impossible to provide in real time, since for matrix inversion multiplication operations. Thus, to construct a cubic polynomial with 64 multiplications required! Of course, such an approach cannot be applied in practice. Next, the Farrow filter for constructing a cubic polynomial using only three multiplications will be considered.

Orthogonal Lagrange polynomials. Farrow Filter

When constructing Farrow filters, orthogonal Lagrange polynomials are used. Then a continuous signal can be represented as the sum of the product of its counts to the corresponding Lagrange polynomial :

Polynom lagrange is polynom of degree equal to one with where - sampling time - of the first counting and equal to zero at other moments of discretization. Figure 4 shows the cubic Lagrange polynomials for

Sampling times selected . Each of the polynomials is equal to one at one of the sampling times and is zero in the others (this is indicated by markers).

It is very important at this stage to understand that for signal samples used different polynomials. Each Lagrange polynomial can be written in the form:

We write the Lagrange polynomials for and sampling points :

Lagrange Polynomials:

Substitute the expression for the discretization points (10) in (11) and open all the brackets we get:

Similarly, you can paint the Lagrange polynomials for any .

We will complete the Farrow filter synthesis for using cubic Lagrange polynomials (12). With expression (8):

Since each of the Lagrange polynomials is a cubic polynomial, in expression (13) is the sum of cubic polynomials, which means also cubic polynomial with coefficients , .

We only need to calculate these coefficients. Substitute the polynomials (12) in the expression (13):

We open the brackets and give similar relative degrees. , we get a cubic polynomial:

Which coefficients are equal:

Each of the coefficients of the cubic polynomial (15) depends on the samples of the original signal. Wherein depend on the four previous values. Thus, the coefficients of polynomial (15), in accordance with formula (16), can be obtained using FIR filters of the third order. Figure 5 shows an example of calculating a polynomial coefficient. using FIR filter.

Similarly, you can draw the structure of FIR filters to calculate the remaining coefficients.

Earlier in Figure 3, a cubic polynomial scheme was presented with known coefficients. We found that the coefficients of a polynomial are third order filters. Now we can present the final structure of the third-order Farrow filter. This structure is shown in Figure 6.

Filters for calculating polynomial coefficients based on signal samples are represented by different colors: - black - red - blue - green. Gray marked branches multiplied by zero, which can be discarded from the scheme. According to the scheme, it is easy to calculate that the calculation of all coefficients of a polynomial requires 9 non-trivial multiplications (multiplication by zero and considered trivial). This is not 64 as required for the direct solution of the system of equations, but not three as stated above.

Let's optimize the structure shown in Figure 6. To do this, consider carefully the expression for the coefficients of the polynomial (16). It is easy to notice that:

In addition, you can pay attention:

Then from (18) it follows that

Look further:

Then from (20) it follows:

Then the expression for the coefficients of the polynomial can be represented in the form:

As stated, only three multiplications! The scheme that implements the calculation of a polynomial based on (22), called the modified Farrow filter, is presented in Figure 7.

At the first stage, the coefficient is formed (black branches), then it is used to calculate the coefficient blue branches. Further coefficients and used to calculate . Coefficient just removed after the second delay.

At this, the synthesis of the third-order Farrow filter can be considered complete and summarize some results:

1. A third-order Farrow filter has been synthesized that allows to obtain the value of a continuous signal at any time based on polynomial interpolation.

2. The filter of the third order requires only 3 multiplication operations and can be applied in real time.

Up to this point we have not said anything about the meaning required to be calculated . The filter was synthesized based on the following initial data: there are 4 samples taken at time points . Accordingly, in order to get the value of the polynomial value should be in the range of -2 to 1, while corresponds to the sampling time , but corresponds to the sampling time . Value must be recalculated in the interval from -2 to 1.

Consider an example. Let there be 4 samples of the signal , , , taken at a sampling frequency of 1 kHz, i.e. sec, sec, sec and sec (Figure 8). Calculate the value of the signal at time sec

The scale is normalized according to the following formula:

In our case:

Calculate the polynomial coefficients based on the modified third degree Farrow filter (22):

Then the value of the signal at time equally:

Figure 9 shows the polynomial and the value of a polynomial at a given point.

It should be noted that using such an approach it is impossible to calculate values ​​beyond the interval of taking four samples, i.e. Or . In the previous example, it is impossible to calculate the signal value from these four samples, for example, for , because . Of course, it is possible to calculate more precisely, but the value will not correspond to reality. With the greatest accuracy, the signal values ​​are calculated at normalized from -1 to 0. In practice, you should strive to recalculate the time scale in the interval from -1 to 0.

To change the sampling frequency, it is necessary to recalculate the time for sampling times in the range from -1 to 0. Figure 10 shows an example of resampling for a signal with a frequency of 3 kHz (red graph) digitized with a sampling frequency of 20 kHz to a frequency of 24 kHz (blue graph) .

It can be seen that after the oscillation one resampling there is an integer number of counts (8 pieces), while before resampling there were distortions caused by a non-integer number of counts per oscillation period. Since the sampling frequency increased from 20 to 24 kHz (6/5 times), every sixth count after resampling coincides with every fifth count before resampling (marked with markers).

Thus, the article describes the procedure for calculating the Farrow filter using the example of a third order filter. Modified filter to reduce computational operations. Shows an example of resampling the signal for a fractional change in the sampling rate