IIR not fully causal?

"Jerry Avins" <jya@ieee.org> wrote in message 
news:kYydnRBxe9k2HOPfRVn-hQ@rcn.net...
> Carlos Moreno wrote:
>>
>> Ok...  Either I'm being excessively dense and am not understanding
>> that the replies so far are indeed answering my question, or no-one
>> has really understood what I'm asking...
>>
>> So, let's try to re-phrase it...
>>
>> I need to digitally oversample a signal.  With high presicion in
>> the time domain.  In real-time (with low delay).
>
> Why? Any sample rate above the minimum adds no information.

I think "upsample" or "interpolate" would be a better term than "oversample". 
Maybe that is part of the confusion?

A common reason for upsampling a signal is to make the analog reconstruction 
filter simpler/cheaper/easier to construct.  Essentially, you are doing some of 
the reconstruction digitally so the analog section doesn't need to work so hard. 
This is very common in audio and allows you to use, for example, a 2-3 pole 
filter with a 40kHz cut-off instead of a "brick wall" 8 or more pole filter with 
a 20kHz cut-off for reconstruction a 20kHz audio bandwidth. 

Carlos Moreno wrote:
> Ok...  Either I'm being excessively dense and am not understanding
> that the replies so far are indeed answering my question, or no-one
> has really understood what I'm asking...
>
> So, let's try to re-phrase it...
>
> I need to digitally oversample a signal.  With high presicion in
> the time domain.  In real-time (with low delay).

Seems to me that the spec is no good. If you need high
precision, you generally needs lots of data available,
and you would probably have to allow for processing time.

> One obvious solution that fails the last requirement is to use an
> FIR filter.  A two-million taps low-pass filter at the appropriate
> frequency  (the "two-million taps" is a figure of speedh -- what I
> mean is that if I require lots of precision, I could increase the
> length of the FIR response, and accomplish the task...  At the
> expense of longer and longer delays).

That's how the story usually goes, yes...

> What if I told you that I can afford a delay of two samples?

Then I'd reply you have a problem. Well, you could of course
make sure the spec is very, very close to what can be done
with a 1-tap FIR filter...

> Is there a way to reconstruct the value of x[n-1] at time n
> with high precision in the time-domain?  (in the context of a
> low-pass oversampling filter)

As Peter said, at that time x[n] is known, so you could try
an AR(1) smoothing filter. If it's atypo and you really wanted
to estimate x[x+1], you could try an AR(1) prediction filter,
but bear in mind that AR methods are based on the theory of
stationary signals. The signal you describe in your original
post is hardly stationary.

> Perhaps what I'm asking is equivalent to an IIR filter with
> quasi-linear phase for frequencies below some point?  (a quasi-
> linear phase corresponding to a physical delay of 1 sample?)

It's not as much about the properties of the filter as it
is about how much data you need to get the job done. You said
it yourself, precision requires lots of data. You just have
to wait for all those data to fill up the input buffer to
your filter. For IIR filters, it is a matter of waiting until
the impulse response has faded away, which could take far
longer than the number of coefficients in the filter indicates.
Once you have the needed data available, you can do all sorts
of nifty filtering on them.

Rune

Rune Allnor wrote:
> If it's atypo and you really wanted
> to estimate x[x+1], ...

Heh, commenting on other people's possible typos in
a sentence that contains at least two of my own...
blame it on the monday morning.

It should be

"If it's a typo and you really wanted to estimate x[n+1], ..." 

Rune

On Sun, 08 May 2005 17:16:26 -0400, Jerry Avins <jya@ieee.org> wrote:

>Carlos Moreno wrote:
>> 
>> Ok...  Either I'm being excessively dense and am not understanding
>> that the replies so far are indeed answering my question, or no-one
>> has really understood what I'm asking...
>> 
>> So, let's try to re-phrase it...
>> 
>> I need to digitally oversample a signal.  With high presicion in
>> the time domain.  In real-time (with low delay).
>
>Why? Any sample rate above the minimum adds no information.
>
Sure the information is embedded in the samples but he actually
doesn't have it in his hands.  One application he might be trying to
implement would be a low latency interpolator for digital clock
recovery. 

>Filters don't do sampling, they process samples. What do you mean by 
>"oversampling filter"?

I think he wants an interpolator ie an FIR filter which implements the
Farrow algorithm. In the sense he using the term, you give the sampled
data to the oversampling filter and a fraction and you get another
sample which is fraction away from the center tap so it is an
oversampling filter.

On 8 May 2005 17:19:32 -0700, "Manuel M" <manuel.matias@gmail.com>
wrote:

>
>Jerry Avins ha escrito:
>> Carlos Moreno wrote:
>> > I need to digitally oversample a signal.  With high presicion in
>> > the time domain.  In real-time (with low delay).
>>
>> Why? Any sample rate above the minimum adds no information.
>>
>
>That is *almost* true (it can't be applied to time-limited signals,
>except in approximation). However, oversampling *can* have some
>uses (not that I know many, to be honest).
>
>It would help a lot if we knew why there is a need to oversample
>and exacly why there must be a low delay.

I think he doesn't need all the "oversampled" data, he just needs some
specific data out of all the possible oversampled data. ie as someone
already mentioned here, he wants to do digital interpolation. Low
latency is always good :-) Never heard of anyone asking for high
latency. If this interpolator in a  feedback loop (filter of a control
system or a loopfilter of a communication system) low delay/latency is
a must for easy stabilization of the said loop. Also some
communication systems have required delays from channel to output
which necessiates a low delay interpolator if one does a digital
interpolating clock recovery.

Instead of thinking about a IIR working with one sample from the
"future", other people here will more easily wrap their less flexible
brains around the identical problem if stated as that you want to allow
the average delay of an IIR to increase by up to one more sample time,
if this degree of freedom will allow an IIR to be designed with a lower
amount of phase non-linearity in the frequency range of interest.

Another possible solution is to design a FIR filter closer to minimum
phase in response than your typical symmetric linear phase FIR filter.
This will help meeting a max delay requirement without drastically
changing the filter frequency response.  I think there are papers on
the web on using Cepstrum techniques to approximate this.

Or you could look at designing an IIR which has an impulse response
similar looking to a FIR with a phase response closer to minimum rather
than linear.

In article <Co4fe.60629$pe1.955226@wagner.videotron.net>,
Carlos Moreno  <moreno_at_mochima_dot_com@xx.xxx> wrote:
>
>I've been thinking about this crazy idea that I assume has
>to be something that someone did already.
>
>Say that I'm trying to do oversampling;  let's take, as an
>example, oversampling by a factor of 4.  So, what we do is,
>just put a sample of the signal, then three samples with
>zero, then apply a low-pass filter (with cutoff pi/4).
>
>This low-pass filter should, in principle, be a 0-phase FIR
>(in reality, it is a linear-phase FIR, and we determine the
>oversampled signal with some delay).
>
>Now, the above technique is not acceptable for real-time
>applications with critical/tough delay requirements (i.e.,
>if we can not afford the delay introduced by the length
>required for the FIR, then the above is not an option).
>
>Let's say that we have a situation where non-linear phase
>is also out of the question (i.e., we must reconstruct the
>signal such that it is very close to the "true" signal *in
>the time domain* -- i.e., quasi-zero-phase is a requirement).
>
>An IIR would have a very hard time with that task, right?
>
>I'm thinking, what if we do an IIR in which the output of
>the filter is the previous sample (or N samples before, in
>general).
>
>The idea is that, intuitively, a casual IIR has a hard time
>reconstructing with quasi-zero-phase because it can not know
>where the signal is going.  But then, if we allow it to
>know one sample in the future (or, in general, N samples in
>the future, where N is much smaller than the N we would need
>for a linear phase FIR), it could do a much better job.
>
>Is this a standard technique?  Are there existing algorithms
>to design IIR filters as close as zero-phase as possible
>given these conditions?  Or is it completely impossible with
>this approach?  (i.e., would I have to do a regular IIR and
>then use a non-linear estimator?  Or simply use a non-linear
>estimator with the input signal alone?)
>
>I'll be grateful for any ideas/pointers.
>
>Thanks,
>
>Carlos
>--


IMHO. YMMV.
-- 
Ron Nicholson   rhn AT nicholson DOT com   http://www.nicholson.com/rhn/ 
#include <canonical.disclaimer>        // only my own opinions, etc.

Ronald H. Nicholson Jr. wrote:
> Instead of thinking about a IIR working with one sample from the
> "future", other people here will more easily wrap their less flexible
> brains around the identical problem if stated as that you want to
allow
> the average delay of an IIR to increase by up to one more sample
time,

Eh... it might be a problem with my intellectual flexibility, but I
tend not to like signal processing schemes that somehow are based
on the user/designer being either clairvoyant or omniscient.
[ And no, these are not sarcastic stings directed at any of the
participants in this thread. I have actually been asked by
previous employers to work with such schemes. ]

It might, on the other hand, be a problem with me understanding
the posts stating the problem. It is my distinct impression that
the OP has a strict limit on how much time delays he is willing
to accept. I may have midunderstood, but I understand the stated
problem such that at reference time n, no more than 1 previous
sample is available. If more data is needed to obtain the required
spec, the remaining data must be taken from "the future".

> if this degree of freedom will allow an IIR to be designed with a
lower
> amount of phase non-linearity in the frequency range of interest.

Agreed. However, the OP seems to be very clear on that this degree
of freedom is not available or acceptable to him.

Rune

Rune Allnor wrote:
> Ronald H. Nicholson Jr. wrote:
> > Instead of thinking about a IIR working with one sample from the
> > "future", other people here will more easily wrap their less
flexible
> > brains around the identical problem if stated as that you want to
> allow
> > the average delay of an IIR to increase by up to one more sample
> time,
>
> Eh... it might be a problem with my intellectual flexibility, but I
> tend not to like signal processing schemes that somehow are based
> on the user/designer being either clairvoyant or omniscient.

I actually found Ronald's response the most suited to answer the OP's
question. It has nothing to do with clairvoyance.

Here is my take on it:

First, we have to agree that the term "delay of a filter" is only
defined for linear-phase filters. It is not possible to trade "delay"
by allowing deviation from the filter's phase response from linear
towards minimum, as non-linear-phase filters do not have a well defined
delay.

Second, as I understand, the OP wants to design a lowpass filter to
remove spectral images created during an integer upsampling process
(which he calls "oversampling", a term which seems to throw everybody
off track here for some reason). Usually, this is done using polyphase
(for computational efficiency) linear-phase FIR filters with high order
(as the sampling rate of the lowpass filter is high w.r.t the cutoff
frequency). He also correctly mentions that the accuracy of the
interpolation achieved by this process can be improved by increasing
the order of the FIR.

The OP wants a linear-phase FIR filter to maintain the shape of the
signal, but cannot live with their real-time processing latency (he
calls this delay), which is always equal to (N T)/2, where N is the
order of the FIR, and T is the period of the upsampled signal. He is
asking if it is possible to use a non-linear phase filter with less
delay that still maintains the shape of the signal. The simple answer
is no.

However, one can continually trade-off linear towards minimum phase
response in an FIR filter, which reduces the main impulse transmission
latency of the FIR filter (which of course is not equal to the delay,
as mention above, but related). That's what Ronald suggested, and I
find it a sensible trade-off. Whether the OP can achieve an acceptable
trade-off using this scheme can only be answered by him.

Regards,
Andor

Andor wrote:
> Rune Allnor wrote:
> > Ronald H. Nicholson Jr. wrote:
> > > Instead of thinking about a IIR working with one sample from the
> > > "future", other people here will more easily wrap their less
> flexible
> > > brains around the identical problem if stated as that you want to
> > allow
> > > the average delay of an IIR to increase by up to one more sample
> > time,
> >
> > Eh... it might be a problem with my intellectual flexibility, but I
> > tend not to like signal processing schemes that somehow are based
> > on the user/designer being either clairvoyant or omniscient.
>
> I actually found Ronald's response the most suited to answer the OP's
> question. It has nothing to do with clairvoyance.
>
> Here is my take on it:
>
> First, we have to agree that the term "delay of a filter" is only
> defined for linear-phase filters. It is not possible to trade "delay"
> by allowing deviation from the filter's phase response from linear
> towards minimum, as non-linear-phase filters do not have a well
defined
> delay.

Sorry, I have to disagree here. The "delay" (in the sense of
the impulse response having non-vanishing duration in time)
is a general concept for any interesting filter. Granted,
the concept becomes a bit cumbersome when dealing with
non-linear phase, group delays and dispersion, but "cumbersome"
does not imply "undefined".

> Second, as I understand, the OP wants to design a lowpass filter to
> remove spectral images created during an integer upsampling process
> (which he calls "oversampling", a term which seems to throw everybody
> off track here for some reason). Usually, this is done using
polyphase
> (for computational efficiency) linear-phase FIR filters with high
order
> (as the sampling rate of the lowpass filter is high w.r.t the cutoff
> frequency). He also correctly mentions that the accuracy of the
> interpolation achieved by this process can be improved by increasing
> the order of the FIR.

True, but he unequivocally states that he has to do all this
withing two - 2 - samples worth of time. Is it possible to obtain
this in general, with a 2-tap FIR filter or a 2nd order IIR filter?

No.

> The OP wants a linear-phase FIR filter to maintain the shape of the
> signal, but cannot live with their real-time processing latency (he
> calls this delay), which is always equal to (N T)/2, where N is the
> order of the FIR, and T is the period of the upsampled signal. He is
> asking if it is possible to use a non-linear phase filter with less
> delay that still maintains the shape of the signal. The simple answer
> is no.

Agreed.

> However, one can continually trade-off linear towards minimum phase
> response in an FIR filter, which reduces the main impulse
transmission
> latency of the FIR filter (which of course is not equal to the delay,
> as mention above, but related).

Well, I agree with your arguments, except for the above comments
about the delay. The problem is how they fit with the stated
problem. As far as I can see, the OP unequivocally states that
at time n, he needs to produce an output y[n] and has available
only the samples x[n], x[n-1] and x[n-2] to do so. That's all.
As far as I can find out, he sees that three samples are too
few to get sufficiently close to the desired response.
The question, then, where he can get the remaining samples, if
he can't afford to wait for x[n-3] and beyond.

Again, I could have misunderstood the scope of the problem.

> That's what Ronald suggested, and I
> find it a sensible trade-off.

I can't see the point in that. An N-tap filter requires N
samples to be available regardless of whether the filter
is linear phase or not. The limiting factor in this problem
is that N<= 3.

The sensible trade-off is, in my view, to wait for *enough* samples
to become available to meet the spec, and disregard the very tight
real-time requirement. The actual spec says, as specified
by the OP (and subject to my interpretation!), that "one can wait
for no more than two samples". This is the troublesome part that
invokes clairvoyance, if you need more than two or three samples
to get the required precision in the filter response.

> Whether the OP can achieve an acceptable
> trade-off using this scheme can only be answered by him.

Agreed. I still think the problem is solvable, provided the
spec is adjusted slightly.

Rune

Man, this new Google Groups is up to shit. Every time I want to reply
to a post such that the original post is cited, I first have to log out
and then log in again. Not really efficient ... :(


Rune Allnor schrieb:

> > First, we have to agree that the term "delay of a filter" is only
> > defined for linear-phase filters. It is not possible to trade
"delay"
> > by allowing deviation from the filter's phase response from linear
> > towards minimum, as non-linear-phase filters do not have a well
> defined
> > delay.
>
> Sorry, I have to disagree here. The "delay" (in the sense of
> the impulse response having non-vanishing duration in time)
> is a general concept for any interesting filter. Granted,
> the concept becomes a bit cumbersome when dealing with
> non-linear phase, group delays and dispersion, but "cumbersome"
> does not imply "undefined".

Of course we can talk about group delay. But if the group delay of a
filter varies with frequency, one cannot speak of the delay of a
filtered signal. It doesn't exist. I think the closest concept to
"delay" of non-linear-phase filters is the length for pre-ringing in
the impulse response (pre-ringing is the part of the impulse response
before the main lobe - minimum-phase FIR filters have no pre-ringing,
linear-phase FIR filters have a pre-ringing of (N T)/2, where T is the
sampling period and N the order of the filter, and maximum-phase FIRs
have pre-ringing length equal to N T).


> > Second, as I understand, the OP wants to design a lowpass filter to
> > remove spectral images created during an integer upsampling process
> > (which he calls "oversampling", a term which seems to throw
everybody
> > off track here for some reason). Usually, this is done using
> polyphase
> > (for computational efficiency) linear-phase FIR filters with high
> order
> > (as the sampling rate of the lowpass filter is high w.r.t the
cutoff
> > frequency). He also correctly mentions that the accuracy of the
> > interpolation achieved by this process can be improved by
increasing
> > the order of the FIR.
>
> True, but he unequivocally states that he has to do all this
> withing two - 2 - samples worth of time. Is it possible to obtain
> this in general, with a 2-tap FIR filter or a 2nd order IIR filter?

I understand his requirement as meaning that the overall processing is
allowed to have 2 samples (at the original sampling rate) of processing
latency. If we denote the original sampling period by T_0 and the
period of the upsampled signal by T_1, this means that the order N of
the linear-phase FIR interpolation filter is restricted to

N = 4 T_0 / T_1.

However, if one relaxes the linear-phase requirement, one can trade the
processing latency of the FIR filter (which is equal to the amount of
pre-ringin time before the main lobe of the FIR filter's impulse
response) for deviation from linear-phase. In particular, one can use
any filter (of arbitrary order), as long as the filters pre-ringing is
not longer than 2 T_0.


> Well, I agree with your arguments, except for the above comments
> about the delay. The problem is how they fit with the stated
> problem. As far as I can see, the OP unequivocally states that
> at time n, he needs to produce an output y[n] and has available
> only the samples x[n], x[n-1] and x[n-2] to do so.

I think the OP wants to allow the filter a maximum of two samples
"look-ahead" (by which I mean to limiting the impulse response
pre-ringing to 2 * T_0).

> > That's what Ronald suggested, and I
> > find it a sensible trade-off.
>
> I can't see the point in that. An N-tap filter requires N
> samples to be available regardless of whether the filter
> is linear phase or not. The limiting factor in this problem
> is that N<= 3.

Again, think of the processing latency induced by the pre-ringing of
the impulse response. The order of the filter is irrelevant.

Regards,
Andor