Linear phase IIR filters?

[Sarah Thompson]

I always thought that achieving linear phase response predicated the need
for FIR filters, and that IIR filters could not approach this. However, when
trawling around on AltaVista recently I spotted a few references to linear
phase IIR filters, but couldn't find anything on line that went as far as
owning up to the maths involved. I'm new to the list, so I have no idea if
this has been discussed already. However, due to the enormous run time
performance advantages of IIR over FIR filter architectures, it would seem
to be enormously interesting if this really is possible.

Has anyone had any involvement in this area? If so, pointers towards useful
references would be much appreciated.

Sarah Thompson

PS: I'm interested in DSP for mastering purposes, so to avoid blurring of
transients I'd like to be able to achieve constant group delay across all
bands of a multiband compressor. FIR filters would be too expensive to
implement, unfortunately, but I still would like to achieve better than
Butterworth/Bessel/Chebychev/whatever characteristics.

PPS: Has anyone tried designing IIR filters using genetic algorithms and/or
simulated annealing, in order to get around the 'no inverse transform'
problem?

[robert bristow-johnson]

Post by Sarah Thompson
I always thought that achieving linear phase response predicated the need
for FIR filters, and that IIR filters could not approach this.

if real-time is not an issue you can filter a sound file once in the normal
forward direction and then again in the backward direction and the phase
shifts will kill each other off. you must design the gain of your IIR
filter to be half the number of dB as your original specification.

now, if you segment and overlap-add your audio, you can do it in real-time
using _truncated_ IIR filters (which are really FIR filters in IIR clothing
or, maybe, the other way around - a moving average filter is a simple
example of a truncated IIR implementation) if your willing to put up with a
lot of delay.

Post by Sarah Thompson
However, when
trawling around on AltaVista recently I spotted a few references to linear
phase IIR filters, but couldn't find anything on line that went as far as
owning up to the maths involved. I'm new to the list, so I have no idea if
this has been discussed already.

it hasn't here yet but there were a few breif discussions about it on
comp.dsp (try that instead of Alta Vista if you want to search newsgroup, i
don't think anyone has built a web site to the topic yet). i'm willing to
own up to the math involved here on the list but only to the point that the
concept gets understood (i.e. dialog). i'm not prepared to do a treatise
on it.

Post by Sarah Thompson
However, due to the enormous run time
performance advantages of IIR over FIR filter architectures, it would seem
to be enormously interesting if this really is possible.
Has anyone had any involvement in this area? If so, pointers towards useful
references would be much appreciated.

here is a reprint of a comp.dsp post of mine. for more info, go to Deja
News and search comp.dsp for the topic.


Subject: Re: Linear phase IIR filters
Author: robert bristow-johnson
Email: ***@viconet.com
Date: 1998/08/13
Forums: comp.dsp

Post by Sarah Thompson

Hi,a while back I saw a message here which read an IIR filter could be
given a linear phase response by simply feeding the signal through a second
filter with reversed coefficients (which was said to be the same as feeding
the signal backwards through the filter - which is not very practical in a
real-time algorithm).

Reversing the coefficients of an IIR filter will make the filter
unstable. Trying to filter any data with an unstable filter will
generally lead to undesirable overflow results.
Thus it will NOT produce the same results as feeding the signal
through the filter backwards.
There is no real way to get linear phase IIR responses in real-time.

depending on semantics, this is not exactly true, Peter. with
_truncated_ IIR filters (these happen to have pole-zero cancellation so
their impulse response is actually finite in length but they're
implemented with an IIR filter and a delay line) you can get exactly
phase linear response if by passing the signal through the forward
truncated IIR and then backwards or time-reversed (in segments, using
overlap-add) through an identical truncated IIR.

also, see below, Smith and Wang also did this using _unstable_ truncated
IIR instead of the time-reversed IIR.

Post by Sarah Thompson
You can get good approximations, but not exactly linear phase.

fished out of DejaNews:

Subject: Re: Zero-phase filtering
From: robert bristow-johnson <***@viconet.com>
Date: 1998/06/24
Message-ID: <***@viconet.com>
Newsgroups: comp.dsp

Post by Sarah Thompson
I am trying to find some literature on the handling of initial conditions
and transients when implementing forward-backward zero-phase filters.
The forward-backward step is pretty straightforward, but I have not been
able to find literature on the initial condition treatment . The only
reference I have is the "Discrete-Time Signal processing" book by Alan
Oppenheim and the implementation of Matlab of this zero-phase filter.

i presume you are looking into using real-time IIR filters in forward
and reverse on segments to get the zero-phase (or more accurately,
linear phase) response. if the application is not real-time but applied
to sound files, then issue is trivial: run it thought once forward and
then run the resulting sound file through the same IIR filter backward.

in either case the initial conditions for the IIR are zero.

i think the seminal paper reference is

S. R. Powell & P. M. Chau, "A Technique for Realizing Linear Phase IIR
Filters", IEEE ASSP-39, no.11, pp. 2425-2435, (Nov. 1991).

there is another AES preprint about the same topic:

S. A. Azizi, "Performance Analysis of Linear Phase Audio Filters Based
on the Zero Phase Filtering Concept", 103rd AES Convention (Sept. 1997),
AES preprint no. 4535.

in both of these cases, you time reverse a segment of audio, run it
through (backwards) an IIR filter with initial states set to zero. by
knowing the pole locations of the IIR filter, you can predict how long
it will take the IIR to decay to "zero" (to within a given precision)
after the finite audio segment has passed through. you then time
reverse the result back and overlap-add the tails over succesive
segments (this is easy if you choose the segment size to be exactly the
same length as the length of the IIR impulse response).

Julius Smith and Avery Wang did a paper (it was an internal CCRMA paper
but i think it's published somewhere) on zero-phase filters using
_truncated_ IIR filters (but the non-causal IIR was a truncated unstable
IIR which i don't like too much). these are a pair of IIR with
identical poles but one is scaled, phased, and delayed so that when it
is subtracted from the first IIR the result is _zero_ forevermore. it's
really an FIR implemented as IIR with pole-zero cancellation. if you
implement your time-reversed filters with _truncated_ IIR then you don't
have to worry about how much error you get from truncating the tail in
the time reversed filter.

a possible ref: http://cm.stanford.edu/~jos/tiir.ps.gz

there used to be a publication list for CCRMA but i can't find it. does
anybody know what they did with it?


--

r b-j
***@viconet.com a.k.a. ***@audioheads.com
a.k.a. ***@wavemechanics.com

"Don't give in to the Dark Side. Boycott intel and microsoft."

Post by Sarah Thompson
PS: I'm interested in DSP for mastering purposes, so to avoid blurring of
transients I'd like to be able to achieve constant group delay across all
bands of a multiband compressor. FIR filters would be too expensive to
implement, unfortunately, but I still would like to achieve better than
Butterworth/Bessel/Chebychev/whatever characteristics.

you'll get some blurring anyway unless all bands of your compressor are at
the same gain. but it will be phase-linear blurring which means an equal
amount (and symmetrical) of blur before and after the transient.

Post by Sarah Thompson
PPS: Has anyone tried designing IIR filters using genetic algorithms and/or
simulated annealing, in order to get around the 'no inverse transform'
problem?

i would think that someone in an IEEE paper has published about that. i'm
not in IEEE so i can't, at the moment cite anything, but if you have access
to an engineering library, look in both ASSP (and it's decendents) and
Circuits and Systems.

i _am_ in AES and no one has published genital, errrr, genetic algorithms
there for filter design but Andrew Horner _has_ published about the
application of G.A. to synthesis parameter extraction (FM and wavetable).
personally, i'm not entirely sold on the benefit.




r b-j
***@viconet.com a.k.a. ***@audioheads.com
a.k.a. ***@wavemechanics.com

"Don't give in to the Dark Side. Boycott intel and microsoft."

[Chris Townsend]

Post by Sarah Thompson
Has anyone had any involvement in this area? If so, pointers towards useful
references would be much appreciated.

A great place to look is the following article on Julius Smith's web page.

Truncated Infinite Impulse Response Filters (TIIR) (159 Kbytes): tiir.ps.gz
http://www-ccrma.stanford.edu/~jos/

Post by Sarah Thompson
PS: I'm interested in DSP for mastering purposes, so to avoid blurring of
transients I'd like to be able to achieve constant group delay across all
bands of a multiband compressor. FIR filters would be too expensive to
implement, unfortunately, but I still would like to achieve better than
Butterworth/Bessel/Chebychev/whatever characteristics.

Why not use FFT based filtering?


Chris

[Toth Laszlo]

Post by robert bristow-johnson

Post by Sarah Thompson
There is no real way to get linear phase IIR responses in real-time.

depending on semantics, this is not exactly true, Peter. with
_truncated_ IIR filters (these happen to have pole-zero cancellation so
their impulse response is actually finite in length but they're
implemented with an IIR filter and a delay line) you can get exactly
phase linear response if by passing the signal through the forward
truncated IIR and then backwards or time-reversed (in segments, using
overlap-add) through an identical truncated IIR.

Sorry, it's maybe because I'm a mathematician and not an engineer, but I
don't like it that you call this solution an IIR filter. Just as you said
THEORETICALLY (considering their impulse response) this is a FIR filter,
only the way of IMPLEMENTATION is a recursive, IIR-like one.
When I give lectures on DSP, I always emphasize that the form of
the impulse response and the way of implementation are two different
points of view for categorizing filters. I don't like it, e.g., that many
books use the words "IIR" and "recursive" interchangeably. One of them
categorizes filters based on the impluse resonse, and the other is based
on the implementation technique. Even though practically these are almost
always the same, still you can realize a FIR filter by a recursive
technique. In you case - if I understood your method correctly - you
approximate an IIR filter by truncating its impulse response - so you get
a FIR filter, but you still implement it by recursion. Is it correct?
Than why call it IIR?

(P.S.: I didn't read any of the papers you mentioned. If I misunderstood
your short explanation, just ignore this. Sorry.)

Laszlo Toth
Hungarian Academy of Sciences * "Military intelligence:
Research Group on Artificial Intelligence * two words combined that
e-mail: ***@inf.u-szeged.hu * can't make sense"
http://www.inf.u-szeged.hu/~tothl *

[robert bristow-johnson]

Post by Toth Laszlo

Post by robert bristow-johnson

Post by Sarah Thompson
There is no real way to get linear phase IIR responses in real-time.

depending on semantics, this is not exactly true, Peter. with
_truncated_ IIR filters (these happen to have pole-zero cancellation so
their impulse response is actually finite in length but they're
implemented with an IIR filter and a delay line) you can get exactly
phase linear response if by passing the signal through the forward
truncated IIR and then backwards or time-reversed (in segments, using
overlap-add) through an identical truncated IIR.

Sorry, it's maybe because I'm a mathematician and not an engineer, but I
don't like it that you call this solution an IIR filter. Just as you said
THEORETICALLY (considering their impulse response) this is a FIR filter,
only the way of IMPLEMENTATION is a recursive, IIR-like one.

this is why i qualified the statement using the word "semantics". because
of smeantics, lots of words we use have different meanings to different
people in different contexts.

how about "audio engineer"? that could include me (or you, even though you
disclaim the title) or some guy who mixes music in a studio or concert
venue.

or "sample"? i usually means just one point on a sampled waveform but a
musician would usually mean the whole sampled waveform.

speaking of samples, how about "wavetable synthesis"? i would usually mean
a _real_ synthesis technique that uses a very few wavetables (of equal
number of points, say, 256) to create a quasi-periodic musical tone. now,
in the industry, "wavetable synthesis" essentially means PCM sample
playback which i find hard to call any kind of synthesis.

one more example: "modulation". means different things to musicians than
to signal processing engineers.

even though i've tried to correct it, "pitch shifting" has been used on
comp.dsp to describe the same basic operation as sample rate conversion.
of course the term means to me any process (real-time or not - hey, check
out comp.realtime and see what those guys mean by the term and you'll get
at least 5 different answers) that shifts pitch _without_ changing the
duration of the sound.

all of these examples of semantic differences in meaning of identical words
lie within the context of audio/music signal processing. a very narrow
field.

Post by Toth Laszlo
When I give lectures on DSP, I always emphasize that the form of
the impulse response and the way of implementation are two different
points of view for categorizing filters.

well, i haven't taught EE or DSP in nearly a decade so if you want an
academic authority about the usage, i would cite Julius O. Smith of
Stanford-CCRMA. i think he is who coined the term "truncated IIR" which i
thought was a very apt term. when i first came across the term i knew
_immediately_ without having to ask anyone, what was meant. (i was groping
for a good name for these kindof FIR/IIR filters of which the moving
average is the simplest non-trivial example.)

Post by Toth Laszlo
I don't like it, e.g., that many
books use the words "IIR" and "recursive" interchangeably.

there are lots of things i don't like in DSP books. one pet peeve is that
in describing the sampling theorem, they do not weight the sampling
function with the sampling time T. then the spectrum (with all the images)
is scaled up by 1/T and then to correct that, they usually put the T as the
passband gain of the brickwall reconstruction filter. not only is that
dimensionally inappropriate, we normally think of the LPF as simply
rejecting the images and passing the baseband. that means a passband gain
of 1. this also ends up confusing students when you want to conceptualize
the (sinc) effect of the zero-order hold of a conventional D/A. i also
hate that some books attribute the source of that effect to be in the
sample-and-hold perceding the A/D. totally wrong and confusing.

anyway, i can identify with you, in general, about books screwing up usage
or, even, concepts.

Post by Toth Laszlo
One of them
categorizes filters based on the impluse resonse, and the other is based
on the implementation technique. Even though practically these are almost
always the same, still you can realize a FIR filter by a recursive
technique. In you case - if I understood your method correctly - you
approximate an IIR filter by truncating its impulse response - so you get
a FIR filter, but you still implement it by recursion. Is it correct?

yawohl.

Post by Toth Laszlo
Than why call it IIR?
Even though practically these are almost
always the same...

the other reason is that, in our everyday usage, we normally _do_ equate
the concepts of "recursive" and "IIR". it's just the way it is. when
someone says "IIR", i think "feedback" and "poles". and vis-versa. so i'm
pretty pragmatic about it. (yeah, i know that FIR filters have poles, too,
but i don't count them since their at the origin.)

the last reason is the numerical behavior of truncated IIRs (what you want
not to be called "IIR") is qualitatively closer to IIR than to FIR. a
moving average filter will likely not have this problem, but the general
truncated IIR will have residual noise like reponses that will ring forever
due to rounding and limit cycling. a "true" FIR (or what you might call a
"conventional FIR" to differentiate it from what i call a "truncated IIR")
will simply be finite in response if the non-zero input is also finite. a
conventional FIR is more "bullet-proof" than a truncated IIR.

Post by Toth Laszlo
(P.S.: I didn't read any of the papers you mentioned. If I misunderstood
your short explanation, just ignore this. Sorry.)

oh, no. you understood it well.

Post by Toth Laszlo
* two words combined that
* can't make sense"

we call that an "oxymoron", a term that is internally self-contradictory.
other example: "business ethics" (depends on one's politics). perhaps you
might include "truncated IIR" in that class.



r b-j
***@viconet.com a.k.a. ***@audioheads.com
a.k.a. ***@wavemechanics.com

"Don't give in to the Dark Side. Boycott intel and microsoft."

[Sarah Thompson]

Thanks for the responses. I particularly liked the 'flip the signal and
filter again in the other direction' idea - extremely elegant. Wish I'd
thought of it myself! Unfortunately it isn't an option that is usable for me
because I'm working to a plugin format (currently VST, but my core code will
port to other platforms by changing the wrapper code around the core).

The 'granular time reversal' + TIIR idea (for want of a better description)
sounds more practical, but I'm a little worried that it may introduce
artefacts due to the window function that the time reversal requirement
predicates - have I misunderstood the concept somehow? Or is the idea that
you simply cut up the audio with a rectangular window function, allowing
enough overlap outside the window for the filter to have stabilised by the
time it hits the first for-real sample? If the latter is the case, then
shouldn't it be possible, with a long enough pre-roll, to use an IIR rather
than a TIIR, with the proviso that the IIR must have enough time to settle
down to its last bit? Of course, this probably ends up more expensive than a
FIR anyway.

On the subject of FIRs, I've been attempting to get the
Remez/Parkes-McLellan algorithm to work, armed mostly with some copylefted C
source that I found which had been ported from the original Fortran. I
ported the code to C++ and created a class wrapper for it without too much
trouble, but I became a little stuck in trying to get the algorithm to do
anything sensible. The thing I couldn't find out about was the meaning of
the weighting vector - is that a measure of how close to the requested
response is required to be relative to the actual response, or is it a
coefficient that in some way represents the 'importance' of a point in the
desired response vector? I tried feeding a variety of test data to the
algorithm, but in each case I seemed to end up with filter coefficients that
had little or no resemblance to anything that might give the response I'd
asked for. Any comments anyone might have who has got this algorithm to work
would be appreciated.

Thanks,
Sarah