Optimal Fractional Sample Delay Filter with Variable Delay

	ABOUT THE AUTHOR Marek Blok received an MSc degree in Information Systems from Technical University of Gdansk in 1994. Since 1994, he has been with the Faculty of Electronics, Telecommunications, and Informatics at the Technical University of Gdansk engaged in DSP algorithm research and development. He is currently preparing his PhD thesis concerning fractional sample delay filter design.

This article presents a concept of a fractional sample delay (FSD) filter, optimal in the Chebyshev sense, with variable fractional delay. We first present a computationally efficient method for optimal FSD filter design based on the complex Remez algorithm. We show that you can simplify the design algorithm for an FSD. Moreover, numerical costs can further be decreased for a variable-delay filter. The paper proposes an optimal variable delay FSD filter design method and its derivation, and presents the FSD filter's properties. Additionally, we present and discuss illustrative examples of optimal FSD filters.

Introduction

Fractional sample delay filters find applications in many areas, such as synchronization of digital modems, incommensurate sampling rate conversion, high-resolution pitch prediction, and musical-instrument sound synthesis. In contrast to an integer sample delay, implementation of a fractional delay is very difficult. Although there exist several FSD-filter design methods, the problem is that computationally effective methods, such as a windowing method for a maximally flat filter-design, give us poor-quality filters. On the other hand, designers use numerically intensive iterative methods, for example the complex Remez algorithm proposed by Karam and McClellan, to design high-quality filters. In some cases, you can pre-design FSD filters and store these filters in memory. However, when a large number of filters or a variable delay are necessary, memory requirements become unacceptable.

FSD Filter

The Nth order FSD filter has to approximate an ideal frequency response

      (1)

where n [1/Sa] denotes normalized frequency and t_d [Sa] is the total delay of the filter. The magnitude response of an ideal FSD filter is equal to one, and group or phase delay equals t_d over the entire frequency range.

You can partition the total delay t_d into two components: the net delay e and the bulk delay L or into the fractional delay d and the integer delay D:

      (2)

where L = N/2 and D = round(t_d). For a given fractional delay d [-0.5, 0.5), the approximation error is smallest when the total delay t_d is closest to the bulk delay L. Therefore, in most practical cases the net delay satisfies the condition e [-0.5, 0.5). In addition, if both even and odd filter orders are considered, the net delay e will be more useful than the fractional delay d since it is a continuous function (Figure 1) of the total delay t_d.

Figure 1:  Presentation of filter delays for even-order (left) and odd-order (right) filters.

Optimal FSD Filter Design Method

The ideal frequency response shown in Figure 1 is approximated by an Nth-order FIR filter with frequency response

      (3)

where h[n] denotes the filter impulse response. We define the complex approximation error with removed bulk delay factor as

      (4)

You can state an optimal in the Chebyshev sense filter design problem as the minimization of peak error

      (5)

for a given approximation bandwidth B. For FSD filters, usually B (-n_off, n_off).

The most important property of the Chebyshev complex approximation error is an alternation property, which states that if there exist (at least) N+2 frequency points n_k arranged in an increasing order such that the error E(n) satisfies

      (6)

then the filter is optimal for a given approximation bandwidth. The frequency points n_k are known as the extremal points of the complex approximation error of the optimal filter. Additionally, if the set of extremal points of an optimal FSD filter consists exactly of N+2 points, you can calculate the optimal filter by solving the set of N+2 linear equations

      (7)

with N+2 unknowns: h[n] are the filter coefficients and d is the approximation error (peak error equals | d |). This set of equations can be rewritten as a matrix equation, which can be easily solved through matrix inversion.

      (8)

Fortunately, the optimal FSD filters have only N+2 extremal points, so you need to consider only the first stage of the complex Remez algorithm. This feature considerably simplifies the algorithm, since you can pass over the ascend-descent part of the algorithm.

In order to solve the foregoing set of equations, you need a set of extremal points—the only problem is in the construction of such a set. To solve this problem, we'll take advantage of another theorem, as follows.

If the set of extremal points of an filter optimal on B consists of r points, then the optimal filter can be found by selecting among all filters optimal on set B_r of r frequency points n_k B the one with the maximal peak error on B_r.

We base the strategy of constructing the set of extremal points of the optimal filter on the multiple exchange theorem, which creates subsequent sets of N+2 frequency points with an increasing peak error on those sets. The rule of creating the new set of extremal points n'_k can be stated as follows. A new frequency point will take place of the old one (Figure 2), when a real phase rotated error

      (9)

for this point has its absolute value greater than | d |, and for the new set of extremal points arranged in an increasing order the following requirements are fulfilled

      (10)

Figure 2:  Presentation of functioning of the multiple exchange algorithm, where o = old extremal points and x = new extremal points).

For every new set of frequency points, we calculate a filter optimal on that set. The new sets of extremal points are created for as long as | d | increases or, equivalently, the frequency points of new sets change.

The properties of extremal points of the optimal FSD filter lead to further simplifications. As the FSD filter has real-valued coefficients, its frequency response is symmetric. It results in extremal-point symmetry (Figure 3). Additionally, there are always extremal points at approximation band limits (at -n_off and n_off) and for odd-order filters at 0 (Figure 3). On the basis of these properties, you can transform the complex matrix equation (Equation 8) into a real matrix equation (different for even and odd filter order) and the numerical complexity of the computations decreases.

Figure 3:  Extremal points of the real phase rotated error for an FSD filter of even (6th) order (left) and odd (7th) order (right).

Note that all three extremal points of the first-order optimal FSD filter are known. These points are: -n_off, n_off, and 0. Therefore, explicit formulas for the two-sample optimal FSD filter coefficients and error are

      (11)

where

      (12)

Moreover, when the approximation bandwidth approximates zero, the filter tends to a maximally flat two-sample linear interpolator

      (13)

Figure 4:  First stage of the complex Remez algorithm.

Optimal Variable-Delay FSD Filter

Although the algorithm we previously described is relatively efficient, it is still too complicated when we need the fractional delay to be updated in real time. The most extensive part of the optimal FSD filter design algorithm (Figure 4) is the process of constructing the set of extremal points for the optimal filter. For every iteration, you must solve the set of linear equations (Equation 8), calculate the real-phase rotated error by means of interpolation (via a fast Fourier Transform, FFT), and form the new set of extremal points. For case of the FSD filter, you usually need several such iterations.

Fortunately, all optimal FSD filters of given length and approximation bandwidth have the same set of extremal points. Thus, when one designs a family of FSD filters with the same length and approximation bandwidth but with different delays, you need to apply the extensive extremal points searching algorithm only once. If the set of extremal points is formed beforehand, you can update the filter coefficients easily. When you use matrix inversion to obtain the filter coefficients, the matrix being inverted is independent of the delay value and you have to invert the matrix only once.

Figure 5:  Absolute value of the complex approximation error [dB] of an optimal FSD filter. On the left is a 4th-order filer with n_off=0.3, and on the right a 9th-order filter with n_off=0.4. Net delay values are: e = ±1/2, ±1/8, ±1/32, ±1/128 [Sa].

The above observations allow for the formulation of the variable delay optimal FSD filter concept.

First, you evaluate the extremal points n_k of the optimal FSD filter with a given approximation bandwidth and the matrix

      (14)

beforehand. For example, you can obtain the points as a by-product of an optimal FSD filter design process.

Since the extremal points n_k and, thus, the matrix E do not depend on the net delay e, you can easily update the filter coefficients by using

      (15)

for any arbitrary net delay e.

Conclusions

The optimal in Chebyshev sense FSD filter design method presented here is based on the complex Remez algorithm introduced by Karam and McClellan. We base the proposed simplifications of the original algorithm on the properties of optimal FSD filter. Those simplifications allow for an easy implementation of the design algorithm and for the formulation of explicit formulas for the first-order FSD filter. The main result, however, is the variable-delay optimal FSD filter concept. Computational costs of the optimal FSD filter redesign when only the delay is changed are considerably reduced.