
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 variabledelay 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, highresolution pitch
prediction, and musicalinstrument sound synthesis. In contrast to an integer sample delay,
implementation of a fractional delay is very difficult. Although
there exist several FSDfilter design methods, the problem is that
computationally effective methods, such as a windowing method for a
maximally flat filterdesign , give us poorquality filters. On the other hand,
designers use numerically intensive iterative methods, for example
the complex Remez algorithm proposed by Karam and McClellan , to design highquality filters. In some cases,
you can predesign 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
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 evenorder
(left) and oddorder (right) filters.
The ideal frequency response shown in Figure 1 is
approximated by an Nthorder 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 ascenddescent 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 realvalued
coefficients, its frequency response is symmetric. It results in
extremalpoint symmetry (Figure 3 ). Additionally, there are
always extremal points at approximation band limits (at –n _{off} and n _{off} ) and for oddorder 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 firstorder optimal
FSD filter are known. These points are: –n _{off} , n _{off} , and 0. Therefore, explicit
formulas for the twosample optimal FSD filter coefficients and
error are
Â Â Â Â Â
(11)
where
Â Â Â Â Â
(12)
Moreover, when the approximation bandwidth approximates zero,
the filter tends to a maximally flat twosample linear
interpolator
Â Â Â Â Â
(13)
Figure 4: Â First stage of the complex Remez
algorithm.
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 realphase 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 4thorder
filer with n _{off} =0.3, and on
the right a 9thorder 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
byproduct 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 .
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
firstorder FSD filter. The main result, however, is the
variabledelay optimal FSD filter concept. Computational costs of
the optimal FSD filter redesign when only the delay is changed are
considerably reduced.
Looking to buy a home? It's better to be on a “Way” than a “Street,” pick a female realestate 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 realestate 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. Fastforward 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 midrange 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 topoftheline 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 bottomtier homes and “captivating” for toptier homes could add 8.2 percent to your home's value. Longer, moredetailed 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.
Â