Advertisement

Article

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 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

     
(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.

1 comment on “Optimal Fractional Sample Delay Filter with Variable Delay

  1. joiafsjefe
    July 28, 2015

    Looking to buy a home? It's better to be on a “Way” than a “Street,” pick a female real-estate agent and try to be close to a Starbucks.
    That's the advice of Spencer Rascoff, CEO of Zillow.com, who collected statistics from his site's database of 110 million homes to find trends in real-estate pricing. Along with Zillow economist Stan Humphries, he has written “The New Rules of Real Estate” (Grand Central), out Tuesday. Some of his findings:
    The Starbucks effect. Take two identical homes sold in 1997. One near Starbucks would have sold for an average of $137,000, while the same home without a Starbucks would have sold for $102,000. Fast-forward 15 years: the average US home appreciated 65 percent to $168,000, but the property next to Starbucks skyrockets 96 percent to $269,000.
    All renovations are not created equal. The greatest return for your investment is a mid-range bathroom remodel, a $3,000 job that returns $1.71 for every dollar spent. The worst home improvements for value are kitchen remodeling and finishing a basement. A top-of-the-line kitchen reno will cost you $22,000, and you'll only get about $0.51 back for every $1 you spend.
    Use the right words in a listing. Avoid “unique,” “TLC,” “investment” and “potential” — these could lower sale prices by as much as 7 percent. But words like “luxurious” for bottom-tier homes and “captivating” for top-tier homes could add 8.2 percent to your home's value. Longer, more-detailed listings often sell for more.
    “When” is as important as “how much.” In New York, the worst time to sell is the second week of December (listings sold for 2.8 percent less than average). The best time is March, when homes sold faster and for 2 percent more.
    Seven is an unlucky number. Homes with “777” as their address sell for 2.1 percent less than their estimated value; house numbers that just include 777 (such as 17779 Main St.), sell for 1.8 percent less. Oddly, houses with just 7 as their number sell for 1.8 percent more than the estimated sale price.
    Psychological pricing works. Listings with a nine in the thousand digit ($450,000 vs. $449,000) sell anywhere from four days to a full week faster.
    Female agents tend to sell homes faster and for higher prices.
    What's in a name? A lot of cash, according to Zillow's data. Homes on named streets tend to be 2 percent more valuable ­nationwide than numbered ones (unless you're talking about New York City, where it's a wash). But Main Street homes garner 4 percent less than America's median home value. Street names with Lake or Sunset will sell upwards of 16 percent higher. Suffixes also matter. Avoid “Street,” which has the lowest home values of $183,120 nationally, and find a “Way,” which has the highest home values averaging around $312,000.

     

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.