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.
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.
The Nth order FSD filter has to approximate an ideal frequency
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
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:
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 .
The ideal frequency response shown in Figure 1 is
approximated by an Nth-order FIR filter with frequency response
where h[n] denotes the filter impulse response. We define the
complex approximation error with removed bulk delay factor as
You can state an optimal in the Chebyshev sense filter design
problem as the minimization of peak error
for a given approximation bandwidth B. For FSD filters, usually
(-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
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
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.
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
In order to solve the foregoing set of equations, you need a set
of extremal pointsthe 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 Br of r frequency
points n k
B the one with the maximal peak error on Br .
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
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
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.
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
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
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
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
for any arbitrary net delay e .
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