Page  341 ï~~Fractional Delay Lines using Lagrange Interpolators Ph. Depalle S. Tassart IRCAM, Analysis/Synthesis Department I place Igor-Stravinsky, 75004 PARIS, FRANCE Abstract We propose in this paper an original approach to the implementation of the Lagrange Interpolator Filter (LIF) based on the formal power series expansion of the transfer function of the ideal fractional delay digital filter. This approach leads to a different, new, modular and robust algorithm usable for real-time delay-varying applications. 1 Introduction Many studies have been undertaken on the modeling of physical systems by means of waveguide filters. These methods consist mainly in simulating the propagation of acoustic waves with digital delay lines [Smith, 1994]. Such models are constrained by a fixed spatial step determined by the sampling rate. This usually prevents the length of the waveguide to vary progressively in time and the spatial resolution is very poor for standard sampling rate. The use of digital filters approximating fractional delays is one way of overcoming these limitations. Lagrange Interpolator Filters (LIFs) are approximations for fractional delay line filters according to a maximally flat error criterion [Laakso et al., 1996]. As waveguide filters imply feedback loops which may cause numerical instabilities, fractional delay lines must be passive filters. This paper focuses on a new passive implementation of LIFs based on a power series expansion of the ideal transfer function and on its time-varying properties. 2 Lagrange Interpolators 2.1 Ideal Fractional Delay Filters Continuous time-delay filters are analog all-pass filters whose Laplace transform is e-sT. Extension of time-delay filters to digital filters leads for integer delay d = p to a basic delay line whose ztransform is z-'. For any other rational value of the delay d, fractional delay digital filters (FDDF) shall be defined by reference to analog time-delay filters [Crochiere and Rabiner, 1983]" from a time sequence (xk)k z we rebuild the original analog signal, then we delay it from the proper delay and finally we re-sample it in order to get (xk.d)kEz. Notice that this process makes sense if and only if the original time sequence (xk)kEz corresponds to the sampling of a band limited analog signal. This means that (xk)kEz has no component at the Nyquist frequency. The Fourier transform Hd(eiw) of these filters exists and is equal to eidw. Notice that the ztransform of the impulse response doesn't exist but we shall use the analytic extension of Hd(e3') which plays the same role as the usual transfer function. This analytic extension is Hd(z) = z-'. 2.2 Lagrange Interpolator Filter The Lagrange Interpolator Filter (LIF) of order N consists in a FIR filter, H(z)- = "k=o Nhdz-k, whose coefficients Nhk are polynomial in d. By definition, the LIF corresponds to an exact delay filter when d is an integer, which means that H (z) must equal z-k for each k between 0 and N. This leads to a system of linear equations whose solution is given in [Laakso et al., 1996]: VN N Vk - o..N, - [ d --i 0<i <N i:-t, (1) As pointed out in [Hermanowicz, 1992], it appears that any filter which verifies the so called maximally flat condition (eq. (2)) is also a LIF. Said differently, it means that the LIF corresponds to the FIR filter whose Fourier transform best fits the ideal Fourier transform for a frequency of zero. Vk E [0, N], a-k-(HN(e w) - e-'d)=o)- 0 (2) 2.3 Power Series Expansion Lets consider the function zd defined over the C plane minus the real semi-axis ] - oo, 0]. Since this function is analytic in its definition domain, it permits a power series expansion around z = 1. For convenience we set w-1 = z-1 - 1. It is clear that the family of FIR filters, whose transfer functions Hk (z) are given in equation (3), is exactly a LIF family since each transfer function is a partial series expansion for z-d around z = 1 and thus verifies the maximally flat condition (eq. (2)). These ICMC Proceedings 1996 341 Depalle & Tassart

Page  342 ï~~are new expressions for LIFs. H _ Nd(d- 1)...(d-k+1) -k k=0 Initialization Output 4- Input b 4- Input e 4- Input (3) 14-1 d 4- -Delay --t While i < N 0 4- (oe- Stil X[i 4- b b 4-e i 4-- i+ d -- d+ 1 Output f- Output+e -i Last loop 0 t- (e -X() X[i]Jf- b b 4-0e i t-i+l X[ 4- b 2.4 Iterative Definition From equation (3), we can easily deduce the transfer function of the LIF of order N from the transfer function of the LIF of order N - 1. This leads to a modular implementation (see section 3.1). Table 1: Modular LIF algorithm for even N. Furthermore, as experimentally noticed in [Laakso et al., 1996], the LIFs are passive filters (i.e. their gain is less than 1) when the delay verifies relation (7). This condition is necessary for applications which involve feedback loops since a non-passive component in a feedback loop may cause numerical instabilities. Finally for each value of delay, two different LIFs, resp. order [d/2J and order [d/2], verify relation (7). {Hg(z)=1 Hft(z) - HkN.l(z) + d(d-1)"d-N'+1)w-N (4) 2.5 Horner's scheme We derive another new expression for transfer functions by rewriting the former expression (3) in nested form. H 1~(z) -- l+ dw-1 1+ d-1w-1(... (5) 1+ dN--- -w 1 + N+Iw N.. This expression corresponds to the Horner's scheme relatively to w-1, which means that this form is the most efficient way of evaluating Hk+1 (z) considered as a polynomial in w-1. 2.6 Influence of the Parity Order Even and odd order LIFs are experimentally known to behave differently ([Laakso et al., 1996]). We present new expressions for the Taylor series expansions at order N + 2 of respectively the gain and the phase of LIF (eq. (6)) which clearly prove that even order filters optimally flatten the gain, while odd order filters flatten the phase. lN-1 N+I[ dE 2 ' 2 [ (7) 3 Delay-Varying Implementation 3.1 Modular LIF structure We implement directly equation (5) by the structure described in figure 1. This implementation is modular since the LIF of order N is deduced from the LIF of order N - 1 just by connecting a new module to it. Each module involves basically two multiplications and two additions. The complete structure for a LIF of order N has N modules. In a delay varying environment, updating the delay costs one additional addition and multiplication for each module. Notice that in timevarying application, this structure implies fewer arithmetic operations than any other known structure. For instance, the modified Farrow structure ([Farrow, 1988]) of a LIF of order 3 involves 11 additions and 9 multiplications whereas our modular structure involves only only 8 additions and 5 multiplications. [arg H,(ej ) +dw]6 [-sin- cos N"][c cos N r sinrth2 with the following notation: I {a Q3 -N Nfd - x N+1 3.2 Algorithm Wd We propose in table 1 the following algorithm + o(wN+2) (6) for simulating the fractional delay system where Input is the input of the filter, Output is the output, and Delay is the desired fractional delay. The state of the system is X[i]; e, b, d and i are intermediary values. The central loop is processed N times, where N is one of the two integers verifyN ing relation (7). The last loop is needed only for -2-)a time-varying applications (this will be explained in section 3.3). r The signal to noise ratio due to round-off floats king point errors in this algorithm increases with is known to be the filter's order, but it is now known to be less nterval the worst A and d = N4- than -80dB in single precision arithmetic for filters 2 of order less than 20 [Tassart and Depalle, 1996]. 2.7 Choice of the Orde] The optimal delay range for LIF around half of the order, in this it case being d =N for odd order Depalle & Tassart 342 ICMC Proceedings 1996

Page  343 ï~~input d N-(z ) output d HN (z) Figure 1: Modular LIF structure with w-1 = z-1- 1 3.3 LIF Order Adaptation In typical implementations, using LIF in its optimal range (eq. (7)), constrains variations of the delay to remain within a rather restrictive interval. When the delay bypasses these limits, the filter is swapped out for the most appropriate one (fig. 2). --------------I [, I. Fiue2 wthbtwe frn t ies SHd IN I. Figure 2: Switch between different filters As seen in figure 1 our modular structure actually implicitly runs N different filters corresponding to the N first orders. At each time and for any value of the delay, we are free to chose amongst the different filters the most appropriate one without any extra computation. This also means that, for each input sample, we compute the output sample which corresponds to the best approximation of the ideal response. In section 2.7 we have seen that we had the choice between two different filters. From these two filters we use the one which optimizes either the gain or the phase profile according to section 2.6. Practically speaking, the order of the LIF is dynamically adapted to the most appropriate order whenever the delay bypasses the limits of relation (7) by connecting or disconnecting appropriate modules from the main structure. When the delay is decreasing, two modules are disconnected from the main structure. Inversely, two modules are connected to the main structure when the delay is increasing. The state of these two modules is properly initialized by connecting two supplementary degenerated; modules (corresponding to the last loop in the algorithm of table 1) whose function consists in updating the state for the future modules. 4 Conclusion This paper has presented a new point of view for considering Lagrange Interpolator Filters applied to Fractional Delay Digital Filters approximations. This leads to a new closed form for the transfer function of LIFs, and to a new robust and efficient time-varying structure for the LIF (See [Vilimiki, 1995]) implementation. References [Crochiere and Rabiner, 1983] Crochiere, R. E. and Rabiner, L. R. (1983). Multirate Digital Signal Processing. Prentice-Hall, Englewood Cliffs, NJ. [Farrow, 1988] Farrow, C. W. (1988). A continuously variable digital delay element. In Proc. 1988 IEEE Int. Symp. on Circuit and Systems (ISCAS'88), volume 3, pages 2641-2645. [Hermanowicz, 1992] Hermanowicz, E. (1992). Explicit formulas for weighting coefficients of maximally flat tunable FIR delayers. Electronic Letters, 28(20):1936-1937. [Laakso et al., 1996] Laakso, T. I., Valimaki, V., Karjalainen, M., and Laine, U. K. (1996). Splitting the unit dealy. IEEE Signal Processing magazine, 13(1). [Smith, 1994] Smith, J. 0. (1994). Bandlimited interpolation - introduction and algorithm. Unpublished. [Tassart and Depalle, 1996] Tassart, S. and Depalle, P. (1996). Fractional delays using Lagrange interpolators. In Proc. Nordical Acoustic Meeting (NAM'96), Helsinki, Finland. [Viilimiki, 1995] Viilimaki, V. (1995). Discretetime modelling of acoustique tubes using fractional delay filters. Master's thesis, Helsinski University of Technology, Lab. of Acoustics and Audio Signal Processing, Espoo, Finland. Report 37. ICMC Proceedings 1996 343 Depalle & Tassart