IIR to TIIR

Hi there,
I tried to understand that TIIR stuff but actually it seems a little "too
complicated" for me (I'm not really a 120 years old DSP engineer :-)).

Is there some simple way to convert biquad IIR to TIIR? (I'm traditionally
using r-b-j's biquads). I mean to get the secondary filter which cancels
the first one. From the stuff I found on TIIRs it seems that it is
necessary to do some transformations to the poles and zeros -> design the
filters again. And I don't really feel I'm good enough to do it :-).

Btw. when talking about the Powel/Chau thing, everyone is talking about
taking the signal and pad it with zeros - but the edge teoretically contain
all frequencies, therefore any amplifying filter would make this a big
trouble, wouldn't it? I did this and it indeed created some nonexisting
frequencies and I successfuly got rid of it by padding it with the real
signal before and after it, smoothing using hann window and than just
cutting it off.

dmnc

jungledmnc wrote:
..........everyone is talking
> about taking the signal and pad it with zeros - but the edge
> teoretically contain all frequencies, therefore any amplifying filter
> would make this a big trouble, wouldn't it? I did this and it indeed
> created some nonexisting frequencies and I successfuly got rid of it
> by padding it with the real signal before and after it, smoothing
> using hann window and than just cutting it off.
>
> dmnc

Q: What's the difference between padding with zeros and padding with pre and 
post replicas?  (Assuming the zero-padding is with 2X zeros for X samples). 
In both cases the sequence is of length 3X.

A:

- In both cases the frequency resolution is 1/3T where T is the length of 
the original sequence.

- In the first case there is the affect of the rectangular "window" that is 
the length of the nonzero sample sequence.  So, there is "leakage" 
associated with the sinc nature of the Fourier Transform of that window. 
Padding with zeros just decreases the frequency sample interval by 3 - a 
form of interpolation in frequency.  The interpolation lets you see the 
leakage more clearly.  If you didn't zero-pad you wouldn't see it - not that 
it isn't still there!

- In the latter case the sequence still has the abrupt edges but they may 
not be so noticeable.  In fact, if one were to have a periodic waveform to 
begin with and if one were to have selected an integer number of periods in 
the original sample, then there would be no "leakage" and only every 3rd 
sample in frequency would be nonzero.
So, this approach provides the opportunity to suppress 2 of 3 samples in 
frequency compared with the first case.  That's an effect that you may or 
may not like.

- So, as above, in the latter case (pre-windowing), the sequence is periodic 
(3 periods) and will have more or less periodic character accentuating every 
3rd frequency sample at 1/T .  The "integer periods" case is the extreme. 
Having a sequence of length 3T to begin with is the other extreme where 
there is no artificial periodicity.

- In the latter case (post windowing), the window does another form of 
interpolation in frequency and smears the harmonics so they may not be so 
noticeable.  Then, in general, all of the frequency samples will be nonzero.

I'd have to ponder this question further:

"Why does simple zero padding by 3 show greater "out of signal band" energy 
as compared to replicating the sample sequence 3 times?"

Fred 

Hi Fred, thanks for the reply.

I didn't mean replicate the signal - that would have no sense, since the
abrupt edges may (and probably would) persist. I'm processing in realtime,
so let's this signal is coming:
XXXABBBBBBBBBBAXXX
where each letter is let's say 1024 samples. Then X are ignored, that is
just signal before and after. A is the signal used instead of zero padding
and B is the input signal which remains - I process the ABBBBBBBBBA part,
then reverse process and finally discard the A parts. My idea was that if
the filter has leakage short enough (shorter than 1024 samples in this
case), then it should "adapt" in the A part and when I'm processing the
next block later (which starts with out last A and uses the previous B as
the padding), it should produce the same output. This of course relies on
the linear-phase property.
Was it possible to understand? :-) (it wasn't so easy to explain)

As to the abrupt edges when zero padding is used in the above scenario.
Imagine 44100Hz sampling rate, and put 50Hz in it. The period is so long,
that most of the block will have really sharp edges at the beginning and
the and. Since the edge represents "all frequencies" moment (at least as I
understand the fact that a single sample 1 between all zeros contains all
frequencies), any amplyfing filter would try to make those frequencies
louder and since it has leakage, I'd expect some kind of "whistling" in the
signal. But I want it to contain only the original 50Hz, attenuated or
amplyfied, but only it. Yes, DSP is not perfect, but seems to me that
leaving the sharp edge there is not a good idea.

Actually this comes from the experience - when I tested my first "version"
of it, it used the zero padding, and it created some nasty frequencies
indeed.

But do not hesitate to tell me I'm stupid! ;) I mean really!

dmnc

>Hi Fred, thanks for the reply.
>
>I didn't mean replicate the signal - that would have no sense, since the
>abrupt edges may (and probably would) persist. I'm processing in
realtime,
>so let's this signal is coming:
>XXXABBBBBBBBBBAXXX
>where each letter is let's say 1024 samples. Then X are ignored, that is
>just signal before and after. A is the signal used instead of zero
padding
>and B is the input signal which remains - I process the ABBBBBBBBBA
part,
>then reverse process and finally discard the A parts. My idea was that
if
>the filter has leakage short enough (shorter than 1024 samples in this
>case), then it should "adapt" in the A part and when I'm processing the
>next block later (which starts with out last A and uses the previous B
as
>the padding), it should produce the same output. This of course relies
on
>the linear-phase property.
>Was it possible to understand? :-) (it wasn't so easy to explain)

I kind of think what you mean with "adapt", but forget about it.
Your filters adapt to nothing. they behave allways the same way,
for any input.
Maybe you should have posted your questions related to your equalizer
in the same thread, since my reply could be confusing to people that
did not read your previous questions in other threads.
(To be clear: I don't mind. I just think it would be easier to
give you usefull answers in context of the thing you are trying to
make)

Just out of curiousity I have programmed a block based linear-phase
filter which passes the blocks forward and reverse through an
iir bandpass filter and it works, as long as the pre and post-padding
is long enough to let the impulse response decay to a neglectable
amplitude.

1. prepad the block with N zeros
2. send it in reverse through the filter (the whole block, don't
   discard anything!)
3. overlap add the blocks, so that the acausal part of your lin-phase
   filter (which is exactly the part of the prepadded zeros) overlaps
   the previous block
4. send the result of this process through the same filter
   (There is no need to do the forward directed part of the
    filtfilt in blocks)

This scheme works.  If you want I can put the code in the net
and post a link (it's gpl).

gr.
Bjoern 

 


>As to the abrupt edges when zero padding is used in the above scenario.
>Imagine 44100Hz sampling rate, and put 50Hz in it. The period is so
long,
>that most of the block will have really sharp edges at the beginning and
>the and. Since the edge represents "all frequencies" moment (at least as
I
>understand the fact that a single sample 1 between all zeros contains
all
>frequencies), any amplyfing filter would try to make those frequencies
>louder and since it has leakage, I'd expect some kind of "whistling" in
the
>signal. But I want it to contain only the original 50Hz, attenuated or
>amplyfied, but only it. Yes, DSP is not perfect, but seems to me that
>leaving the sharp edge there is not a good idea.

No not exactly.  you don't create artefacts by the block based
filtering, if you make sure to keep the tails of the impulse-response.
That is what I've tried to tell you. 
If the overlap-add is done correctly (again, don't discard anything
from your filtered blocks - keep the "tails" of your filter. This
is the reason for zero padding in this case) you will not introduce
any frequencies.  If you hear frequencies related to the frame
rate you do something wrong. 
Whenever I code any overlap-add scheme, I try to make
sure that the overlap-add comes together in the correct way, by
splitting in blocks without processing.  The smallest slip with
the indices in a for-loop etc.. and you hear the frame-rate.


>Actually this comes from the experience - when I tested my first
"version"
>of it, it used the zero padding, and it created some nasty frequencies
>indeed.

Did you use the zero-padding in the way I described it above and
are you 100% sure that it is not just a coding bug?
I got it working with simple 2 pole bandpass filters, just
if I use q-values which are too high it starts to introduce some
artefacts, but that can be avoided by prepadding with more
zeros (-> longer buffers, more delay, more latency).
You can make any trade-off between the maximal sharpness of
your filters and the blocksize. 

gr.
Bjoern


>But do not hesitate to tell me I'm stupid! ;) I mean really!
>
>dmnc
>

>
>1. prepad the block with N zeros
>2. send it in reverse through the filter (the whole block, don't
>   discard anything!)
>3. overlap add the blocks, so that the acausal part of your lin-phase
>   filter (which is exactly the part of the prepadded zeros) overlaps
>   the previous block
>4. send the result of this process through the same filter
>   (There is no need to do the forward directed part of the
>    filtfilt in blocks)
>


Thanks, could you please send the code? I'm not sure if I understand it
correctly :
1) You create 0AAAA, perform reverse filtering, so that it becomes /AAAA
and than add previous block to the "/" part? This does not seem very
logical, since the previous block is already linear phase, but "/" is very
not.
2) What about the tail of the forward filter?

dmnc

>>
>>1. prepad the block with N zeros
>>2. send it in reverse through the filter (the whole block, don't
>>   discard anything!)
>>3. overlap add the blocks, so that the acausal part of your lin-phase
>>   filter (which is exactly the part of the prepadded zeros) overlaps
>>   the previous block
>>4. send the result of this process through the same filter
>>   (There is no need to do the forward directed part of the
>>    filtfilt in blocks)
>>
>
>
>Thanks, could you please send the code? I'm not sure if I understand it
>correctly :

The code:
http://www.koncon.nl/sono-bits/ugens/Filtfilt.cpp 

It's a SuperCollider plugin.  So there are some specific macros
in the code:  e.g.  ZXP(x) is a macro used for in and output
arrays.  It's simply *x++.  Also note that there is a little
weirdness with the input and output pointers.  The pointers 
have an offset of 1 sample.
 

>1) You create 0AAAA, perform reverse filtering, so that it becomes /AAAA
>and than add previous block to the "/" part? This does not seem very
>logical, since the previous block is already linear phase, but "/" is
very
>not.

Yes, that's how it's done.  I'll try your notation to explain:

Collect the first block from the input signal
Read this with fixed-width font:

  AAAAAAAAAA
  A             first block
 0A             prepad with zeros
 /A             reverse filter
  /A            next block, prepadded and filtered
   /A           and the next block
 ++++           overlap add (It's allways previous '/' + 
                             next 'A')

And the previous block is not linear-phase filtered, it's just
reverse filtered.  The forward directed filter is applied to
the output of this process.  There is no need to do the forward
filtering in blocks, since it's just a normal iir (the same iir
that you previously used for the reverse filtering).

Do you understand regular overlap-add fir filtering?
It's just the same, just the blocks are prepadded rather than
postpadded because of the reverse direction of the filters.

Imagine you have an impulse response

[ 1, 0.5, 0.25, 0.125 ]

now you send in this block

[ 0, 0, 0, 1 ]

if you wouldn't zero pad you would loose the tail of the response
(in other words the block wouldn't be filtered in this case)

but you postpad (I'm talking bout the regular forward filter case here)
so you get

[0, 0, 0,  1,   0.5, 0.25, 0.125, 0]
                --------------------  postpad region (tail of response)
                 +    +    +    +
               [ 0,  0,   0,    0, ]  next input block

Now you can do overlap add and you don't loose any output from
the filter.  In the end it's the same as if you would have processed
the signal without splitting in blocks.
And you can just do the same with the reverse directed filters
but you have to prepad.

You usually just do this with FIR filters since with IIR's you
have to artificially "chop off" the (theoretically) infinite
filter tails.  So with the scheme of the Filtfilt.cpp code
you have to make sure to use a blocksize which is big enough,
so that the responses are cut at a point where they have
decayed enough (so that you don't get audible artefacts)

Hope that helps.

gr.
Bjoern

>>
>>1. prepad the block with N zeros
>>2. send it in reverse through the filter (the whole block, don't
>>   discard anything!)
>>3. overlap add the blocks, so that the acausal part of your lin-phase
>>   filter (which is exactly the part of the prepadded zeros) overlaps
>>   the previous block
>>4. send the result of this process through the same filter
>>   (There is no need to do the forward directed part of the
>>    filtfilt in blocks)
>>
>
>
>Thanks, could you please send the code? I'm not sure if I understand it
>correctly :

The code:
http://www.koncon.nl/sono-bits/ugens/Filtfilt.cpp 

It's a SuperCollider plugin.  So there are some specific macros
in the code:  e.g.  ZXP(x) is a macro used for in and output
arrays.  It's simply *x++.  Also note that there is a little
weirdness with the input and output pointers.  The pointers 
have an offset of 1 sample.
 

>1) You create 0AAAA, perform reverse filtering, so that it becomes /AAAA
>and than add previous block to the "/" part? This does not seem very
>logical, since the previous block is already linear phase, but "/" is
very
>not.

Yes, that's how it's done.  I'll try your notation to explain:

Collect the first block from the input signal
Read this with fixed-width font:

  AAAAAAAAAA
  A             first block
 0A             prepad with zeros
 /A             reverse filter
  /A            next block, prepadded and filtered
   /A           and the next block
 ++++           overlap add (It's allways previous '/' + 
                             next 'A')

And the previous block is not linear-phase filtered, it's just
reverse filtered.  The forward directed filter is applied to
the output of this process.  There is no need to do the forward
filtering in blocks, since it's just a normal iir (the same iir
that you previously used for the reverse filtering).

Do you understand regular overlap-add fir filtering?
It's just the same, just the blocks are prepadded rather than
postpadded because of the reverse direction of the filters.

Imagine you have an impulse response

[ 1, 0.5, 0.25, 0.125 ]

now you send in this block

[ 0, 0, 0, 1 ]

if you wouldn't zero pad you would loose the tail of the response
(in other words the block wouldn't be filtered in this case)

but you postpad (I'm talking bout the regular forward filter case here)
so you get

[0, 0, 0,  1,   0.5, 0.25, 0.125, 0]
                --------------------  postpad region (tail of response)
                 +    +    +    +
               [ 0,  0,   0,    0, ]  next input block

Now you can do overlap add and you don't loose any output from
the filter.  In the end it's the same as if you would have processed
the signal without splitting in blocks.
And you can just do the same with the reverse directed filters
but you have to prepad.

You usually just do this with FIR filters since with IIR's you
have to artificially "chop off" the (theoretically) infinite
filter tails.  So with the scheme of the Filtfilt.cpp code
you have to make sure to use a blocksize which is big enough,
so that the responses are cut at a point where they have
decayed enough (so that you don't get audible artefacts)

Hope that helps.

gr.
Bjoern

Fred wrote:
>Q: What's the difference between padding with zeros and padding with pre
and 
>post replicas?  (Assuming the zero-padding is with 2X zeros for X
samples). 
>In both cases the sequence is of length 3X.
>
>A:
>
>- In both cases the frequency resolution is 1/3T where T is the length of

>the original sequence.
>
>- In the first case there is the affect of the rectangular "window" that
is 
>the length of the nonzero sample sequence.  So, there is "leakage" 
>associated with the sinc nature of the Fourier Transform of that window.

>Padding with zeros just decreases the frequency sample interval by 3 - a

>form of interpolation in frequency.  The interpolation lets you see the 
>leakage more clearly.  If you didn't zero-pad you wouldn't see it - not
that 
>it isn't still there!
>
>- In the latter case the sequence still has the abrupt edges but they may

>not be so noticeable.  In fact, if one were to have a periodic waveform
to 
>begin with and if one were to have selected an integer number of periods
in 
>the original sample, then there would be no "leakage" and only every 3rd

>sample in frequency would be nonzero.
>So, this approach provides the opportunity to suppress 2 of 3 samples in

>frequency compared with the first case.  That's an effect that you may or

>may not like.
>
>- So, as above, in the latter case (pre-windowing), the sequence is
periodic 
>(3 periods) and will have more or less periodic character accentuating
every 
>3rd frequency sample at 1/T .  The "integer periods" case is the extreme.

>Having a sequence of length 3T to begin with is the other extreme where 
>there is no artificial periodicity.
>
>- In the latter case (post windowing), the window does another form of 
>interpolation in frequency and smears the harmonics so they may not be so

>noticeable.  Then, in general, all of the frequency samples will be
nonzero.
>
>I'd have to ponder this question further:
>
>"Why does simple zero padding by 3 show greater "out of signal band"
energy 
>as compared to replicating the sample sequence 3 times?"
>
>Fred 

Hi Fred,

Replicate the sequence would be what you get from the dft
of the original sequence plus some zeros stuffed in.  That's why people
talk about the periodic nature of the dft. 
I think you are trying to emphasize that there is something
going on between the frequency samples and if you use zero-padding
you have a way to see that (and if you look for out of band energy
you find the energy which is hidden between the samples).

What I am trying to tell the OP is that in his specific case
(of overlap-add convolution) he should first forget about
the frequency domain implications of splitting the signal into
blocks and concentrate on the time-domain interpretation.
Just to make the most trivial case:
If you split a sinusoid into blocks (with a rect window)
you have discontinuities at the frame boundaries and you
introduce new frequencies to the blocks (the leakage).
But obviously if you just splice the blocks together again you
get exactly the signal that you had before and your frequencies
introduced by the windowing are gone again.  Now the OP worries that
filtering would "pick up" or amplify this introduced frequencies
in a block based scheme.  (But I guess,) he needs to understand that
block based processing puts the filtered signal together in 
a way that you do not introduce any new frequencies (by modulation
with the windoow .. rect window or whatever).
It's like the trivail example I gave with splitting a sinusoid
and putting it together again.  When it is split the individual
frames are subject to leakage, but if it is put together again
obviously it's the same as before.  And if you filter and
you do not discard any output from the filter (don't cutoff
the filter-tails), it's ok.  The filter does not emphasize
the frequencies occur in the dfts of the individual frames.
It's all allright if the signal is spliced together.

I have noticed that recently there were multiple questions about window
shapes and zero-padding in connection with linear filters.
Zero-padding in connection with linear convolution has no other
purpose as to take the tail of the impulse response into account
and to avoid time-aliasing (in case of fft based fast conv.) or
to clip the tails.  It's a very simple thing:
Pad enough zeros to hold the "tail" of the response for the last
sample in the block and overlap-add. If you pad more zeros it is
wastefull if you pad less it gives you wrong results.

gr.
Bjoern

banton <bantone@web.de> wrote:
(big snip, probably leaving out important stuff)
 
> Replicate the sequence would be what you get from the dft
> of the original sequence plus some zeros stuffed in.  
> That's why people talk about the periodic nature of the dft. 
> I think you are trying to emphasize that there is something
> going on between the frequency samples and if you use zero-padding
> you have a way to see that (and if you look for out of band energy
> you find the energy which is hidden between the samples).

I recommend (the OP) read the explanations in "Numerical Recipes".

They have good explanations of the differences between the different
transforms.  The DFT (FFT) has periodic boundary conditions.
The DST has the boundary condition that the function goes to
zero at the boundary.  For the DCT, the derivative goes to zero
at the boundary.  In EE terms these correspond to the boundary
conditions at the end of a shorted or open transmission line.

(This reminds me of a lecture in my undergrad physics class
that was trying to show the connection between sound waves in
a tube and electrical waves in a coax cable, except that the
explanation came out wrong.  Instead of changing the analogy,
the professor came back the next week with a current probe on
the oscilloscope.  For sound waves we usually measure the pressure:
node at an open end antinode at a closed end.  For electrical
waves the voltage has a node at a closed (shorted) end, antinode
at an open (open) end.  Current has the opposite boundary conditions.)

(snip)

-- glen

>Yes, that's how it's done.  I'll try your notation to explain:
>
>Collect the first block from the input signal
>Read this with fixed-width font:
>
>  AAAAAAAAAA
>  A             first block
> 0A             prepad with zeros
> /A             reverse filter
>  /A            next block, prepadded and filtered
>   /A           and the next block
> ++++           overlap add (It's allways previous '/' + 
>                             next 'A')
>
>And the previous block is not linear-phase filtered, it's just
>reverse filtered.  The forward directed filter is applied to
>the output of this process.  There is no need to do the forward
>filtering in blocks, since it's just a normal iir (the same iir
>that you previously used for the reverse filtering).
>
>Do you understand regular overlap-add fir filtering?
>It's just the same, just the blocks are prepadded rather than
>postpadded because of the reverse direction of the filters.
>
>Imagine you have an impulse response
>
>[ 1, 0.5, 0.25, 0.125 ]
>
>now you send in this block
>
>[ 0, 0, 0, 1 ]
>
>if you wouldn't zero pad you would loose the tail of the response
>(in other words the block wouldn't be filtered in this case)
>
>but you postpad (I'm talking bout the regular forward filter case here)
>so you get
>
>[0, 0, 0,  1,   0.5, 0.25, 0.125, 0]
>                --------------------  postpad region (tail of response)
>                 +    +    +    +
>               [ 0,  0,   0,    0, ]  next input block
>
>Now you can do overlap add and you don't loose any output from
>the filter.  In the end it's the same as if you would have processed
>the signal without splitting in blocks.
>And you can just do the same with the reverse directed filters
>but you have to prepad.
>
>You usually just do this with FIR filters since with IIR's you
>have to artificially "chop off" the (theoretically) infinite
>filter tails.  So with the scheme of the Filtfilt.cpp code
>you have to make sure to use a blocksize which is big enough,
>so that the responses are cut at a point where they have
>decayed enough (so that you don't get audible artefacts)
>
>Hope that helps.
>
>gr.
>Bjoern


Hi Bjoern,
interesting idea. But one more veryfication - about the "adapting" the
filter. I know it is not some technical term, but see this:
You have a 100Hz sine starting at phase 0, pass it through a filter.
Next have the same sine wave starting at PI/2, therefore the first value
is 0. Pass it through the same filter.

Now the question: Are both responses same at PI/2? (thus PI/2 in first
case and 0 in the second case).

I think the second filter would mingle the beginning somehow, therefore
the responses are not the same.

dmnc