Contents

Introduction

In digital communication systems it is necessary to provide symbol
synchronizing of the transmitter and receiver.
At the same time using independent clock generators leads to a
difference of signal sampling frequencies of the transmitter and receiver.

In addition, in many cases there is a compensating task of the so-called
fractional time delay by the value which is less than the sampling interval.
The filter capable to compensate the arbitrary fractional time delay can be
also used for synchronizing clock generators in view of their slow instability.
For this purpose it is necessary to use an additional time error detector to
calculate the fractional delay of signals.

Sometimes it is necessary to perform the sample rate conversion
to the fractional number

, where

and

— are integers.

In this section we will consider one of the effective methods of
solving the specified tasks on the basis of Lagrange polynomial interpolation [1].
Farrow filter realizing the method of Lagrange polynomial interpolation for
digital resampling of signals will be also considered [2-5].

Problem definition

Let the input signal be

,

0,1,2 which samples are taken with the
sampling frequency

Hz.
Then the sample

corresponds to the timepoint

sec.

It is necessary to recalculate digital values of the input signal

into digital values of the signal

,

taken with the
sampling frequency

, where

and

are integers.
Besides, the first sample

shall be delayed in time concerning the first sample
of the input signal

for value

sec.,

.

Further in this section the variable

will be indexed with samples of the
input signal

taken with the sampling frequency

, and the
variable

will be indexed with the signal samples after resampling

.

Thus, the

sample

corresponds to the timepoint:

Having performed normalization concerning the sampling frequency

1 Hz, it is possible to write:

Temporal ratios of moments of capturing signal samples

and

at various values

,

and

, are shown in Figure 1.

Figure 1. Temporal ratios of moments of capturing signal samples

and

,

at various values

,

and

Sampling moments of the input signal

are black, and — moments
of capturing samples of the resampled signal

are red.

Special case 1.

,

. In this case the sampling
frequency is

, and the signal

completely repeats

.

Special case 2.

,

. In this case the sampling frequency is

, but the signal

has a fractional delay
concerning the pickup signal

.

Special case 3.

,

,

.
In this case the signal sampling frequency is

,

, that is

higher than
the signal sampling frequency

.
Thus, we have the signal

digital interpolation .

Special case 4.

,

,

,

.
In this case we have the fractional resampling of

signal.
The signal sampling frequency

is equal to

.

Special case 5.

,

,

.
In this case we have the fractional signal resampling

plus adding the fractional delay.
It is the most general case of the considered special ones.
The signal sampling frequency

is equal to

.

To solve the resampling task it is necessary to carry out the continuous signal
restoration

according to the available discrete signal

,

,
and to calculate its discrete values for the timepoints

where

is calculated according to (2).

The resampling process for special case 2 (the fractional delay compensation)
is shown in Figure 2.

Figure 2. Signal resampling

As we use only indexes of signal samples, values

are also set not as absolute time values,
but as normalized ones concerning the sampling frequency.

Lagrange polynomial interpolation

There is such a proof in mathematical analysis that the only polynomial of

degree passes through

points.
For example, only one straight line can be drawn through two points,
only one parabola can be drawn through three points.
The only polynomial of

degree passing through

points is called
Lagrange polynomial interpolation:

where

— are polynomial coefficients which are calculated on
the basis of the discrete values

,

To calculate coefficients

we can compose the linear system (see Figure 2):

This system can be written down in the matrix form as:

where

The solution of the equation system can be as follows:

where

— is the matrix inverse for the matrix

.

The calculation procedure of the matrix inverse is one of the most costly ones
from the point of view of computing resources.
In the general case the number of transactions

, which is in proportion
to the dimension cube of the square matrix is required.
For example, to calculate coefficients of the cubic polynom for

in
the general case

of multiplication is required that is implemented
in practice in a difficult way.
Further we will see how it is possible to reduce the number of multiplication
operations to three, and at that, two of them will be multiplication by

that is easily realized in integer arithmetic by one bit shifting on the right.

We will return to the matter below.
Now we will consider effective representation of polynomials according to Horner structure.

Effective polynomial representation according to Horner structure

We will consider polynomial (3) in more detail:

We will put

outside the brackets and get:

Again we will put

outside the brackets and get:

Thus, putting

outside the brackets possible number of times,
we will get a set of the nested parentheses:

For example, we will get a cubic polynomial for

:

which can be realized in the form of the structure shown in Figure 3.

Figure 3. Calculating a cubic polynomial according to Horner structure.

This representation is called Horner structure and it is widely used for
effective calculating values of polynomials [6].
Its main benefit is the fact that the multiplier and adder

are required
to calculate the polynom value of

degree, in case of the known coefficients.

Using polynomial interpolation for digital signal resampling

Setting up polynomial interpolation is often carried out when using Lagrange orthogonal polynomial.
However solving the system of linear equations (4) is a more general approach
which can be applied not only to Lagrange interpolation, but also to other methods
of polynomial interpolation (Hermite polynomial interpolation, spline interpolation and others).

We have already said that the calculation operation of the matrix inverse is a
computationally complex challenge.
Besides, the input data flow can be very long, and we can apply
piecewise polynomial interpolation to processing.
At the same time there is a question of choosing the polynomial order
(the sample number of the input signal for interpolation).

The most often used method is piecewise and polynomial cubic interpolation in
view of compromise between accuracy and computing costs.
We will consider a method of piecewise and polynomial cubic interpolation in more detail.

The cubic polynomial can be constructed with four points according to (7).
For any

it is possible to get two samples more to the right and
more to the left of

as it is shown in Figure 4a.
Then the value

can be calculated on the basis of four
input samples

,

,

,

.

Figure 4. Piecewise and cubic interpolation

Let us pay attention to the fact that the matrix

depends only on
indexes of input signal samples.
It means that to escape recalculating

and the matrix inverse

for each new

, we can hold fix X-direction indexes.
Let it be

(see Figure 4a), then instead of

we will use
the value

as it is shown in Figure 4b.
In this case we can calculate the matrix inverse

once and use it for any

.

The system of equations to calculate polynomial coefficients with constant
indexes according to Figure 4b is as follows:

Then we can present the matrix

and get the inverse one to it

:

We do not give the calculation procedure of the matrix inverse.
You can independently be convinced that

,
where

is the identity matrix.

Polynomial coefficients according to (7) can be got as result of the matrix
inverse multiplication

by the vector of the input
signal samples

:

We will perform matrix multiplication (15) and get expressions for polynomial coefficients:

Owing to expression (16) it is possible to notice that polynomial coefficients
depend on held values of the input signal

.
We can interpret (16) for calculating coefficients as differential equations of the FIR-filter.
Then the separate FIR-filter will carry out calculating each coefficient and the
resampling filter structure can be presented as it is shown in Figure 5.

Each FIR-filter calculates one polynomial coefficient, then they will be transferred to Horner
structure to calculate a polynomial at the current value of the fractional delay

.
The structure given in Figure 5 bears the name of the Farrow filter in honor of the scientist
who used the similar filter to change of the signal delay for the first time [2-5].

Figure 5. Structure of Farrow filter for digital resampling by using

Lagrange polynomial interpolation

It is important to mark that the Farrow filter output

is delayed corresponds
to the input signal

by one sample in units of input signal samples
(in case of the sampling frequency

).

Using fixed X-direction values allows to get rid of the matrix inversion on
a real time basis.
However Farrow filter also demands a significant amount of multipliers
by

,

and

.
At the same time in case of realizing in integer arithmetic multiplications
by

can be considered trivial because they are realized as
one place shifting on the right.

In the following paragraph we modify Farrow filter to reduce the number
of multipliers when calculating polynomial coefficients.

Minimization of multipliers when calculating Lagrange polynomial interpolation

Upon realizing signal resampling filters we have to aim at minimizing the number
of multipliers when calculating polynomial coefficients.

Let’s look attentively at (16). The coefficient

can be presented in the form of:

In (16) it is also possible to notice that

from which it is possible to calculate the coefficient

as:

To calculate the coefficient

it is possible to use the following conclusion from (16):

then:

Thus, we can rewrite (16) in the optimized form only with three multipliers
(and at that, two of them are equal to

):

The optimized digital resampling filter structure corresponding to (22) is given in Figure 6.

Figure 6. Optimized filter function chart of digital resampling

Thus, we have got the algorithm which calculates coefficients of Lagrange
polynomial interpolation using only one multiplier by

and
two trivial multipliers by

.
In the

following sections
we will review examples of using the filter of digital resampling on the basis of
Lagrange polynomial interpolation.

Conclusions

In this section we have considered structures of digital resampling
filters on the basis of Lagrange polynomial interpolation.

Horner structure to calculate polynomial values was considered.
The number of multipliers and adders of Horner structure is equal to the polynomial order.

The Farrow filter structure is got, and its optimization is performed.
As a result coefficients of Lagrange polynomial interpolation
can be calculated when using only three multipliers.
One multiplication by

and two trivial multiplication
by

are required.

In the

following section
we will consider characteristics of the digital resampling filter and examples of
its use to compensate the fractional time delay, interpolation of
signals and fractional signal sampling frequency change.

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.