A parallel linear-complexity implementation structure for lagrange interpolation

Lagrange interpolation is widely used in signal processing applications such as variable fractional delay filtering (VFD) or arbitrary sample rate conversion (ASRC). From the computational point of view, the main advantage of this technique is that the coefficients of the interpolation filter are computed using explicit formulas. For resource-efficient applications, the complexity of Lagrange interpolation algorithms is of utmost importance. Most algorithms in use have a complexity of O(N2) per output sample, N being the order of interpolation. On the other hand, algorithms with a lower complexity published so far are either not suited for general-purpose VFD applications or show drawbacks when implemented on modern signal processing hardware. In this paper, we present an implementation structure for Lagrange interpolation with linear complexity which is suited for general-purpose VFD applications. It is shown how symmetry relations inherent to Lagrange interpolation ca n be used for further complexity improvements. The structure has a high degree of inherent parallelism, thus enabling efficient implementations in hardware or on modern parallel, pipelined or superscalar processors. The complexity of the proposed implementation structure is compared to existing algorithms