Linear phase IIR filter

Jani Huhtanen wrote:

> Andor wrote:
> > robert bristow-johnson wrote:
> >
> > ...
> >> there are three things that i can understand being what you are
> >> refering to.  first of all, there are no *exactly* linear phase IIR
> >> filters.
> >
> > You meant: There are no *exactly* linear phase _causal_ IIR filters.
> >
> You meant: There are no *exactly* linear phase _causal_ and _stable_ IIR
> filters. ;)

My claim:

An (non-zero) IIR filter has linear-phase   =>  the filter is acausal.

(By acausal I mean there exists no number N such that h(n) = 0 for all
n < N, where h(n) is the impulse response of the filter).

Stability of the filter is a property which is independent of this
claim.

Regards,
Andor

Andor wrote:
>
> 4. The "filtfilt" technique: Forwards and backwards filtering with any
> filter (IIR, FIR, TIIR,...) squares magnitude response and cancels
> phase response. The Powell and Chau implementation of this technique is
> true IIR (only the pre-response is finite, the post-response is
> infinite) and approximate linear-phase.

oh yeah, i keep forgetting about Powell/Chau and mixing it up with
Wang/Smith actually what i was meaning to propose in 3 was previously
discussed in

http://groups.google.com/group/comp.dsp/browse_frm/thread/84325b2fccd4b0a8

and earlier threads.  both have square magnitude response, but
Wang/Smith follow the "normal" TIIR filter with an unstable mirror TIIR
filter and then they have a way of ping/ponging between two identical
unstable filters in such a way that they clear out the crap before it
blows up.

Powell/Chau (and later Azizi) was the buffer, reversal, filter (with a
stable identical filter), and reverse back.

both require ping-ponging and overlap adding. both have a problem (in
my opinion).  Wang/Smith just seems like walking on a knife edge with
an unstable TIIR. the Powell/Chau actually has a real error because
they use a regular IIR and just stop when the IIR tail gets "small
enough".

*my* little idea is to combine the use of TIIR from Wang/Smith and use
that with the filtfilt of Powell/Chau.  there are no unstable filters
and no theoretical errors.

r b-j

Andor wrote:

> Jani Huhtanen wrote:
> 
>> Andor wrote:
>> > robert bristow-johnson wrote:
>> >
>> > ...
>> >> there are three things that i can understand being what you are
>> >> refering to.  first of all, there are no *exactly* linear phase IIR
>> >> filters.
>> >
>> > You meant: There are no *exactly* linear phase _causal_ IIR filters.
>> >
>> You meant: There are no *exactly* linear phase _causal_ and _stable_ IIR
>> filters. ;)
> 
> My claim:
> 
> An (non-zero) IIR filter has linear-phase   =>  the filter is acausal.
> 
> (By acausal I mean there exists no number N such that h(n) = 0 for all
> n < N, where h(n) is the impulse response of the filter).
> 
> Stability of the filter is a property which is independent of this
> claim.
> 
> Regards,
> Andor


You claimed that there are no *exactly* linear phase _causal_ IIR filters
(right?). I claim that there exists *exactly* linear phase _causal_ IIR
filters but those filters are not _stable_. For example,

        H(z) = 1/(1 - z^-1)

is _causal_ and it has linear phase.

-- 
Jani Huhtanen
Tampere University of Technology, Pori

Jani Huhtanen wrote:

> You claimed that there are no *exactly* linear phase _causal_ IIR filters
> (right?).

Yes. However, I'm having second thoughts about that claim ... :-)

> I claim that there exists *exactly* linear phase _causal_ IIR
> filters but those filters are not _stable_. For example,
>
>         H(z) = 1/(1 - z^-1)
>
> is _causal_ and it has linear phase.

The sequence h(n) = 1 for n >=0, which is the causal inverse of the
above transfer function, has no Fourier transform (which you need to
define the phase response). In fact, any transfer function with a pole
on the unit circle has no ROC that includes the unit circle (and
therefore has no Fourier transform) ...

Do you know a causal infinite impulse response filter which does not
have a pole on the unit circle and has a linear phase response?

robert bristow-johnson wrote:

> Andor wrote:
> >
> > 4. The "filtfilt" technique: Forwards and backwards filtering with any
> > filter (IIR, FIR, TIIR,...) squares magnitude response and cancels
> > phase response. The Powell and Chau implementation of this technique is
> > true IIR (only the pre-response is finite, the post-response is
> > infinite) and approximate linear-phase.
>
> oh yeah, i keep forgetting about Powell/Chau and mixing it up with
> Wang/Smith actually what i was meaning to propose in 3 was previously
> discussed in
>
> http://groups.google.com/group/comp.dsp/browse_frm/thread/84325b2fccd4b0a8
>
> and earlier threads.  both have square magnitude response, but
> Wang/Smith follow the "normal" TIIR filter with an unstable mirror TIIR
> filter and then they have a way of ping/ponging between two identical
> unstable filters in such a way that they clear out the crap before it
> blows up.
>
> Powell/Chau (and later Azizi) was the buffer, reversal, filter (with a
> stable identical filter), and reverse back.
>
> both require ping-ponging and overlap adding. both have a problem (in
> my opinion).  Wang/Smith just seems like walking on a knife edge with
> an unstable TIIR. the Powell/Chau actually has a real error because
> they use a regular IIR and just stop when the IIR tail gets "small
> enough".

Close enough is fine for me :-). Anycase, the elegance of the Powell /
Chau implementation is that you can use any H(z), and make it have as
close to linear-phase response as you wish. You can use fixed-point
fraction saving algorithms, or special low-noise filter topologies and
your favourite IIR filter design routines, and plug them into the
Powell / Chau algorithm. This makes it a very flexible way to achieve
(approximate) linear-phase at moderate computational cost (memory usage
is just as high as the equivalent FIR implementation).

>
> *my* little idea is to combine the use of TIIR from Wang/Smith and use
> that with the filtfilt of Powell/Chau.  there are no unstable filters
> and no theoretical errors.

How do you get rid of the instability problem of the TIIR topology? The
Powell / Chau algorithm uses overlap-add only for the inverse filter
response (as I'm sure you know). The forward filter response is
computed using the standard filter architecture, where you still have
potential exponentiation of round-off errors.

I must read that TIIR paper one of these days ...

Andor wrote:
> robert bristow-johnson wrote:
>
> > both require ping-ponging and overlap adding. both have a problem (in
> > my opinion).  Wang/Smith just seems like walking on a knife edge with
> > an unstable TIIR. the Powell/Chau actually has a real error because
> > they use a regular IIR and just stop when the IIR tail gets "small
> > enough".
>
> Close enough is fine for me :-). Anycase, the elegance of the Powell /
> Chau implementation is that you can use any H(z), and make it have as
> close to linear-phase response as you wish.

well, it's perfectly linear-phase, it's just that it might "click" a
little when they snip off the tail.

> > *my* little idea is to combine the use of TIIR from Wang/Smith and use
> > that with the filtfilt of Powell/Chau.  there are no unstable filters
> > and no theoretical errors.
>
> How do you get rid of the instability problem of the TIIR topology?

it's not that the TIIR is inherently unstable.  both the Wang/Smith and
Powell/Chau have one filter that is normal and then followed by another
that has the same magnitude but will cancel the phase.  to do that
"same magnitude, opposite phase", they both ping-pong (which has the
potential for a click when one switches from "ping" to "pong") but at
that point they are different.

in Wang/Smith, there is no reversing of the data but the second filter
is one identical to the first but the both the poles and zeros are
reflected about the unit circle (reciprocals).  presuming the first
filter was stable, then the second one *must* be unstable, but since
it's a *truncated* IIR, theoretically the impulse response is a growing
exponential sinusoid that gets truncated.  but, even if the output went
to zero, internally the states are exploding.  so before the exploding
states hit the numerical limit (and then the "truncated" output will no
longer be zero), they switch with another identical unstable TIIR with
clean states and overlap-add two results.  when the zeroed input to the
TIIR that was switch out, finally passes through the whole FIR length
(then the output should theoretically be zero forever if it weren't for
those nasty numerical realities), that's when they "clean up" the
states (zero them) and, then the switch from pong back to ping.\

in Powell/Chau the second filter is a stable one identical to the
first, but the data coming out of the first filter is passed through
the second one in reverse order, zero padded.   when the zero pad data
is passing through the second filter output decays toward zero, but
never quite gets there because, in Powell/Chau, it's an IIR.  my point
is that the Powell/Chau will be theoretically *perfect* and still have
no unstable filters if they use (for both forward and reverse filters)
stable TIIR filters that are essentially the IIRs they originally
designed but with the tail cancelled.  that changes the impulse
response and frequency response ever so slightly, but, in the
reverse-time filter, the output actually gets to zero theoretically and
there will be no click at all.

> The Powell / Chau algorithm uses overlap-add only for the inverse filter
> response (as I'm sure you know). The forward filter response is
> computed using the standard filter architecture, where you still have
> potential exponentiation of round-off errors.
>
> I must read that TIIR paper one of these days ...

the idea of the TIIR is great, but the idea of the unstable TIIR to do
the phase cancelling is, in my opinion, too scary.  that's why i
thought they should do the TIIR thing with the Powell/Chau idea and
instead of waiting for the filter output to decay down to where "it's
good enough", they can wait until the TIIR (which is really an FIR)
actually *does* go to zero.  no clicks.

r b-j

Andor wrote:

> Jani Huhtanen wrote:
> 
>> You claimed that there are no *exactly* linear phase _causal_ IIR filters
>> (right?).
> 
> Yes. However, I'm having second thoughts about that claim ... :-)
> 
>> I claim that there exists *exactly* linear phase _causal_ IIR
>> filters but those filters are not _stable_. For example,
>>
>>         H(z) = 1/(1 - z^-1)
>>
>> is _causal_ and it has linear phase.
> 
> The sequence h(n) = 1 for n >=0, which is the causal inverse of the
> above transfer function, has no Fourier transform (which you need to
> define the phase response). In fact, any transfer function with a pole
> on the unit circle has no ROC that includes the unit circle (and
> therefore has no Fourier transform) ...

Ah.. caught me :). Though, my opinion is that for H(z) there exists phase
response (atleast for w!=k2pi) even though the impulse response h(n) is not
absolutely summable or square summable. The impulse response h(n) is the
discrete unit step function. It can be shown that the following Fourier
transform: 

        U(exp(j*w)) = 1/(1-exp(-j*w)) + \sum_{k=-\infty}^\infty pi*delta(w+k2pi)

represents the discrete unit step function, where delta(.) is the Dirac's
delta (i.e., has "infinite height, zero width, and unit area").

> Do you know a causal infinite impulse response filter which does not
> have a pole on the unit circle and has a linear phase response?

Nope ;)
as linear phase response requires symmetric impulse response. 

-- 
Jani Huhtanen
Tampere University of Technology, Pori

Jani Huhtanen wrote:

> Andor wrote:
>
> > Jani Huhtanen wrote:
> >
> >> You claimed that there are no *exactly* linear phase _causal_ IIR filters
> >> (right?).
> >
> > Yes. However, I'm having second thoughts about that claim ... :-)
> >
> >> I claim that there exists *exactly* linear phase _causal_ IIR
> >> filters but those filters are not _stable_. For example,
> >>
> >>         H(z) = 1/(1 - z^-1)
> >>
> >> is _causal_ and it has linear phase.
> >
> > The sequence h(n) = 1 for n >=0, which is the causal inverse of the
> > above transfer function, has no Fourier transform (which you need to
> > define the phase response). In fact, any transfer function with a pole
> > on the unit circle has no ROC that includes the unit circle (and
> > therefore has no Fourier transform) ...
>
> Ah.. caught me :). Though, my opinion is that for H(z) there exists phase
> response (atleast for w!=k2pi) even though the impulse response h(n) is not
> absolutely summable or square summable. The impulse response h(n) is the
> discrete unit step function. It can be shown that the following Fourier
> transform:
>
>         U(exp(j*w)) = 1/(1-exp(-j*w)) + \sum_{k=-\infty}^\infty pi*delta(w+k2pi)
>
> represents the discrete unit step function, where delta(.) is the Dirac's
> delta (i.e., has "infinite height, zero width, and unit area").

Ok, and what is the phase response of U(exp(j*w))?

It always astonishes me what kinds of tricks can be pulled to make
sense out of divergent series and integrals. For example, the
(continuous) Fourier transform of a sinsuoid clearly does not converge.
Still, it makes perfect sense to use two weighted Diracians (haha:-) as
its Fourier transform. It is amazing how we can completely ignore the
functional nature of the Dirac pulse without paying any consequential
price.

>
> > Do you know a causal infinite impulse response filter which does not
> > have a pole on the unit circle and has a linear phase response?
>
> Nope ;)
> as linear phase response requires symmetric impulse response.

Not necessarily. For example, if you sample a sinc pulse with T =
1/sqrt(2), the sequence is neither symmetric nor periodic, but still
linear-phase (which is a simple consequence of the sampling theorem).

The necessary and sufficient condition for linear-phase FIR filters is
well known
(http://groups.google.ch/group/comp.dsp/msg/9be6c8f2861d1d3a). Do you
know some similar condition for linear-phase filters with infinite
impulse response?

Regards,
Andor

robert bristow-johnson wrote:

> Andor wrote:
> > robert bristow-johnson wrote:
> >
> > > both require ping-ponging and overlap adding. both have a problem (in
> > > my opinion).  Wang/Smith just seems like walking on a knife edge with
> > > an unstable TIIR. the Powell/Chau actually has a real error because
> > > they use a regular IIR and just stop when the IIR tail gets "small
> > > enough".
> >
> > Close enough is fine for me :-). Anycase, the elegance of the Powell /
> > Chau implementation is that you can use any H(z), and make it have as
> > close to linear-phase response as you wish.
>
> well, it's perfectly linear-phase, it's just that it might "click" a
> little when they snip off the tail.

It's not perfectly linear-phase, because the backward response of the
filter impulse response is finite and not equal to the forward response
(which is infinite).

> > > *my* little idea is to combine the use of TIIR from Wang/Smith and use
> > > that with the filtfilt of Powell/Chau.  there are no unstable filters
> > > and no theoretical errors.
> >
> > How do you get rid of the instability problem of the TIIR topology?
>
> it's not that the TIIR is inherently unstable.  both the Wang/Smith and
> Powell/Chau have one filter that is normal and then followed by another
> that has the same magnitude but will cancel the phase.  to do that
> "same magnitude, opposite phase", they both ping-pong (which has the
> potential for a click when one switches from "ping" to "pong") but at
> that point they are different.
>
> in Wang/Smith, there is no reversing of the data but the second filter
> is one identical to the first but the both the poles and zeros are
> reflected about the unit circle (reciprocals).  presuming the first
> filter was stable, then the second one *must* be unstable, but since
> it's a *truncated* IIR, theoretically the impulse response is a growing
> exponential sinusoid that gets truncated.  but, even if the output went
> to zero, internally the states are exploding.  so before the exploding
> states hit the numerical limit (and then the "truncated" output will no
> longer be zero), they switch with another identical unstable TIIR with
> clean states and overlap-add two results.  when the zeroed input to the
> TIIR that was switch out, finally passes through the whole FIR length
> (then the output should theoretically be zero forever if it weren't for
> those nasty numerical realities), that's when they "clean up" the
> states (zero them) and, then the switch from pong back to ping.\
>
> in Powell/Chau the second filter is a stable one identical to the
> first, but the data coming out of the first filter is passed through
> the second one in reverse order, zero padded.   when the zero pad data
> is passing through the second filter output decays toward zero, but
> never quite gets there because, in Powell/Chau, it's an IIR.  my point
> is that the Powell/Chau will be theoretically *perfect* and still have
> no unstable filters if they use (for both forward and reverse filters)
> stable TIIR filters that are essentially the IIRs they originally
> designed but with the tail cancelled.  that changes the impulse
> response and frequency response ever so slightly, but, in the
> reverse-time filter, the output actually gets to zero theoretically and
> there will be no click at all.

Ok, I get it. That's a good idea. Why don't you write it up?

Regards,
Andor

Andor wrote:

> Jani Huhtanen wrote:
> 
>> Andor wrote:
>>
>> > Jani Huhtanen wrote:
        *snip*
>> Ah.. caught me :). Though, my opinion is that for H(z) there exists phase
>> response (atleast for w!=k2pi) even though the impulse response h(n) is
>> not absolutely summable or square summable. The impulse response h(n) is
>> the discrete unit step function. It can be shown that the following
>> Fourier transform:
>>
>>         U(exp(j*w)) = 1/(1-exp(-j*w)) + \sum_{k=-\infty}^\infty
>>         pi*delta(w+k2pi)
>>
>> represents the discrete unit step function, where delta(.) is the Dirac's
>> delta (i.e., has "infinite height, zero width, and unit area").
> 
> Ok, and what is the phase response of U(exp(j*w))?

Unless i'm mistaken the phase response is

w!=k2pi:
        arg(U(exp(j*w))) = -atan(sin(w)/(1-cos(w)) = -atan(sin(w/2)/cos(w/2) 
        = -atan(tan(w/2)) = -w/2

I don't comment on w=k2pi ;) (although I'm slightly inclined to say that it
would not be (well) defined).

> 
> It always astonishes me what kinds of tricks can be pulled to make
> sense out of divergent series and integrals. For example, the
> (continuous) Fourier transform of a sinsuoid clearly does not converge.
> Still, it makes perfect sense to use two weighted Diracians (haha:-) as
> its Fourier transform. It is amazing how we can completely ignore the
> functional nature of the Dirac pulse without paying any consequential
> price.

Sometimes I have the exact same feeling.
 
>>
>> > Do you know a causal infinite impulse response filter which does not
>> > have a pole on the unit circle and has a linear phase response?
>>
>> Nope ;)
>> as linear phase response requires symmetric impulse response.
> 
> Not necessarily. For example, if you sample a sinc pulse with T =
> 1/sqrt(2), the sequence is neither symmetric nor periodic, but still
> linear-phase (which is a simple consequence of the sampling theorem).

True, didn't think of that. Although the sampled version is symmetric when
sampling is "centered" so that one sample is taken at point t=0  (I presume
that T is sampling interval).


> The necessary and sufficient condition for linear-phase FIR filters is
> well known
> (http://groups.google.ch/group/comp.dsp/msg/9be6c8f2861d1d3a). Do you
> know some similar condition for linear-phase filters with infinite
> impulse response?

No.

> 
> Regards,
> Andor

-- 
Jani Huhtanen
Tampere University of Technology, Pori