Asynchronous Sample Rate Conversion (ASRC) for Matlab (and C)

Updated August 15, 2010

Acknowledged work of S. Tassart and others
Replaced C version of Lagrange with arbitrary order (instead of fixed 5th order)

Updated December 31, 2011

Minor bugfixes in farrow.zip (in scripts construct_farrow.m and test.m)

Background

I prefer the term Arbitrary as opposed to Asynchronous for situations where the sample rate clock(s) physically doesn't exist (such as a Matlab simulation) but asynchronous is the more accepted term and I succumb to that for the title. In the sequel I favor arbitrary.

I needed a block sample rate converter in Matlab but didn't find anything conveniently available at least in my version of Matlab (R11) and toolboxes (Signal Processing Toolbox only) so I created these. Consequently, these are written for Matlab R11.

Two methods are presented. The first is the well known Farrow method. The second is a clever Lagrange interpolation method by described by C. Candan in his paper which might be available here (or here) or see the code or in Matlab type "help asrc_lagrange" for the IEEE reference. The computational cost of the Candan algorithm is on the order of an ordinary FIR.

Since my original discovery of Candan's paper I have learned of other work in this area by Tassart, Depalle, Lehtinen, Renfors, and others - some of which precedes that of Candan, but here I will still refer to this structure as the Candan structure. It is worth noting though that the identical structure was proposed by Tassart and Depalle.

Lehtinen and Renfors propose a structure which is basically equivalent to my modified Candan structure. Both have the same practical improvement over the structure proposed by Candan, Tassart, and Depalle - the difference is that they split the coefficients each into two coefficients and distributed them between the input and output sections, while I kept them whole and moved them to the output section. They are equivalent in the sense that the improvement stems from moving the delay dependent part to the output section such that the filter state is independent of the interpolation delay.

Later I needed an ASRC for a realtime embedded application and coded the delayed Candan structure in C. This implemetation is well suited for block based or sample based processing although it was intended for block based (sample based is the same as block based but with a block size of one). The C version is suitable for DSP implementation (the circular state buffer could be optimized for your DSP's circular addressing).

My sincere thanks to Stephan Tassart for bringing much of this other work to my attention and for our interesting discussion. Below are links to his and related works:

"Fractional Delay Lines using Lagrange Interpolators", Ph. Depalle and S. Tassart, available here (or here).
"Analytical Approximations of Fractional Delays: Lagrange Interpolators and Allpass Filters", S. Tassart and Ph. Depalle, available here (or here).
"Structures for Interpolation, Decimation, and Nonuniform Sampling Based on Newton's Interpolation Formula", Vesa Lehtinen and Markku Renfors, available here (or here).

and for completeness

"An Efficient Filtering Structure For Lagrange Interpolation", Cagatay Candan, available here (or here).

Introduction

Arbitrary sample rate conversion consists of two steps:

Computing the position of the desired ouput sample relative to the input samples. Since sequences are integer indexed this can be thougt of as a floating point sample time where the integer portion refers to the input sample position and the fractional part refers to the distance between that sample and the next.
Computing the ouput sample given the inputs and the position calculated in 1.

In Matlab the desire in general is to work with vectors so the goal is to generate a vector of resampled outputs from a vector of inputs. The position of the first output sample is in general arbitrary. However, it may not be possible to store the entire input sequence at once and if so a segmented approach is necessary in which case the next segment needs to 'start' where the previous one 'left off'. A convenient way to think of this is to generate the output sample times as an initial time t0 plus time steps of dt where dt is the ratio of the input to output sample rates (Fsi/Fso).

To simplify the boundary conditions, in the Matlab code the maximum number of output samples are always generated from the input samples. Because of the initial offset t0 and the resampling ratio dt the number of output samples for a given length input can vary and it may not be possible to get exactly the number of desired outputs (i.e for block processing) by controlling the number of given inputs. In the case where a fixed output block size is needed, the input size can be controlled to produce at least the number of desired outputs and any extra have to be saved for the next block. In this situation, this has to be managed outside the provided functions but a corresponding testbench block_test.m is included.

The interface to both the Farrow and Lagrange sample rate converters are similar so it is easy to go between them. For more information see the Matlab code and refer to the testbenches.

Farrow Method

The Farrow method files are available here.

Three functions are provided:

construct_farrow() - Constructs the polynomial representation of a prototype filter.
asrc_farrow() - Runs the interpolator.
asrc_farrow_loop() - Same as above except using as a loop instead of a vector operation as reference for non-Matlab implementations.

The following testbenches are provided:

test - Runs the interpolator over an input signal for a given resampling ratio and increasing polynomial orders. The input block size is fixed, the output block size can vary.
impulse_test - Computes the impulse response of the resampling filter for a given filter order and increasing polynomial orders.

Additional testbenches are included with the Lagrange method which are easily adapted to the Farrow method.

Lagrange Method

The Lagrange method files are available here.

As mentioned above, the algorithm used is slightly modified from that proposed by Candan and pictured here.

One function is provided:

asrc_lagrange() - Runs the interpolator.

The following testbenches are provided:

test - Runs the interpolator over an input signal for a given resampling ratio and increasing Lagrange orders. The input block size is fixed, the output block size can vary.
block_test - Same as above but the output block size is fixed and the input block size can vary..
impulse_test - Computes the impulse response of the resampling filter for increasing polynomial Lagrange orders.

Delayed Modified Candan Algorithm and C Implementation

The C source files are available here.

The values stored in the delay elements of the differentiators are the the derivatives (but once delayed) needed by the algorithm. By introducing a delay in the calculation the delayed derivatives can be used. This is shown in the Delayed (Modified) Candan structure below.

Two functions are provided:

candan_interp() - Implements an arbitrary order Lagrange interpolator using the delayed modified Candan algorithm.
complex_candan_interp() - Same as candan_interp but for complex data..

The following testbenches are provided:

test1 - Runs the interpolator over a periodic input signal for a given resampling ratio and outputs the input and output in m-file format for plotting in Matlab. The input is periodic and repeated until the specified number of output points have been generated.
test2 - Runs the interpolator in a continuous fashion as it would be used in a real application. Input blocks are converted to output blocks and a block processing algorithm is run when a full output block is available.
complex_test1 - Same as test1 but for complex data.

Return to Matt's World