Re: Interpolation And Low-Pass filtering


"Himanshu" <hs.chauhan@xxxxxxxxx> wrote in message
news:1134741316.351797.113470@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
> Fred,
>
> I have a few questions. Sorry, If you find them really dumb, but I want
> to be crystal clear about these facts.
> So, here I go...
>
>>4) Lowpass filter by multiplying in frequency. This >does the
>>interpolation.
>
> How does it do the interpolation? How actually are the zero values
> converted to non-zero values? Is there anything I am missing?
>
>>Replace steps 3 and 4 with:
>>3) zero pad the FFT around fs/2 to get the MN samples >you need.
>>4) IFFT to get the interpolated time sequence.
>>[Purists will point out, rightly so, that this is the
>>same as multiplying by
>>a "perfect" lowpass filter - but without the multiplies >of course].
>
> This causes no problem because we are padding zero. What if we padded
> some non-zero values? Thats going to cause
> problems, I think.
>
>>If we zero pad a time sequence we are tacitly making >the assumption that
>>the
>>nonzero part is a single period of a periodic waveform. >So, it's already
>>time-limited in that sense because of the assumed >periodicity. When we
>>zero
>>stuff or, equivalently, multiply multiple periods by >zero, the
>>corresponding
>>frequency domain affect is to convolve the spectrum >with a sinc.
>
> What is meant by multiplying multiple periods by zeros.
> That would zero them out! And how's that equivalent to convolving
> spectrum with a sinc?
>
> I would really like to continue this discussion further
> until I am really clear with all that stuff.
>
> Thanks for you help, Fred.

Himanshu,

>>4) Lowpass filter by multiplying in frequency. This >does the
>>interpolation.
>
> How does it do the interpolation? How actually are the zero values
> converted to non-zero values? Is there anything I am missing?
>
Here is a somewhat lengthy description accompanied by "cartoons" of the
transform pairs at each step:

INTERPOLATION OF TIME SAMPLES

| | | | | |
x x x x x x x
| x |x x|x x|x x|x x|x x|
| | x | | | | | |
| | | | | | | | |
| | x | | | | | | |
| | | <-> | | | | | | |
| | | | <-> | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| T | T | T | | | | | | |
+-----------------------+ +-ooo-+-ooo-+-ooo-+-ooo-+-ooo-+
time -> 0 fs 2fs 3fs 4fs 5fs
1/T frequency ->

Original samples <-> Original spectrum
multiplied by this: convolved withthis:


X *
o o
o o o o o o o o o o o o o | |
| | | | | | | | | | | | | | |
| | | | | | | | | | | | | | |
| | | | | | | | | | | | | | |
| | | | | | | | | | | | | | |
| | | | | | | | | | | | | | |
| | | | | | | | | | | | | <-> | |
| | | | | | | | | | | | | | |
| | | | | | | | | | | | | | |
| | | | | | | | | | | | | | |
| | | | | | | | | | | | | | |
| | | | | | | | | | | | | | |
+-----------------------+ +-----------------------|------>
time -> 0 frequency ->
fs=4/T
yields: yields:
V V

x x x x x x x
| x |x x|x x|x x|x x|x x|
| | x | | | | | |
| | | | | | | | |
| | x | | | | | | |
| | | | <-> | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
+-o-o-o---o-o-o---o-o-o-+ |-ooo-+-ooo-+-ooo-+-ooo-|-ooo-+
time -> 0 frequency -> fs=4/T

Thus:
stuffing zeros in time increases the sample rate without changing the
frequency spectrum - only the perspective.
Adding N zeros(e.g. 3)
increases the sample rate by (N+1) (e.g. 4)

Now, we will "zero out" the spectrum around the original fs, 2fs
and 3fs to get a sequence that is sampled at 4fs.
There are two ways to do this:
- use a lowpass filter designed for this purpose.
In this case an "eighth band" filter perhaps.
- multiply the spectrum by a perfect frequency "gate" function.

Samples Spectrum
convolved by this: <-> multiplied by this:
* X


o ooooo ooooo
| ||||| |||||
| ||||| |||||
| ||||| |||||
| ||||| |||||
| <-> ||||| |||||
| ||||| |||||
| ||||| |||||
o | o ||||| |||||
| | | ||||| |||||
o | | | o ||||| |||||
| | | | | ||||| |||||
o---o---o---+---o---o---o- oooo|oooooooooooooooooooooo|ooooo+
| time -> | 0 frequency -> fs=4/T
o o


Yields: Yields
V V


X x x
| x x x X x|x x|x
| | | | | x x X | |
| | | | | | x x | | | |
| | | | | | | x X x | | | | |
| | | | | | | | | | | | | <-> | |
| | | | | | | | | | | | | | |
| | | | | | | | | | | | | | |
| | | | | | | | | | | | | | |
| | | | | | | | | | | | | | |
| | | | | | | | | | | | | | |
T | | | | | | | | | | | | | | |
+-----------------------+ - | --------------------- + -
time -> 0 frequency -> fs=4/T

The filtering process is more computationally intensive in that the
frequency domain multiplication must actually be done.

Of course, the frequency multiplication with zeros is so simple
that it need not be done by multiplying at all!
The issue with this process is that there may be time domain aliasing.

How might this temporal aliasing be alleviated?
Well, the problem with stuffing zeros in frequency is that the "gate"
function we use conceptually for multiplying has a very long time
sequence due to the sharp edges.
A "real" filter doesn't have those sharp edges and some of the filters
designed for this purpose actually have a double zero at fs/2, 3fs/2,
5fs/2, 7fs/2 - or even a higher order zero at this point.
These zeros assure that there are no sharp edges of the filter.
Sharp edges of a filter can truncate an otherwise "continuous" spectrum
This creates temporal spreading the same way that a rectangular
window in time will cause spectral spreading. Thus, temporal aliasing.


How might we accomplish something very similar and still take advantage
of the zero-multiplying process?

First, note that if we filter a highly replicated spectrum then there
are lots of points to compute.
So, it may be more efficient to filter in stages so that the
corresponding sample rate is doubled at each step.

Also, we note that a sequence of time samples may or may not have
come from a properly bandlimited signal. This has two effects:
- the sampling will have caused spectral aliasing
- the spectrum of the samples may be far from zero at fs/2.
There is nothing to be done about the aliasing.
However, if the spectrum of the samples is not zero at fs/2
then subsequent processing may introduce temporal aliasing.

So, lowpass filtering of the data may be a good idea.

******************************

>From the above you can see that lowpass filtering after zero-stuffing fills
in the *temporal* zeros that were stuffed.

> This causes no problem because we are padding zero. What if we padded
> some non-zero values? Thats going to cause
> problems, I think.
>

Here there's no padding, just stuffing - the essence of interpolation.
I can't think of what the fundamental underlying operation would be to pad
with nonzero values - at least one that would make sense.
Now, if we're talking about stuffing with nozero values then: you see the
convolution in time with a sinc above (the lowpass filter)?
You can convolve the original samples in time with a sinc-shaped filter
whose delays are 1/M closer together than the original samples. This
accomplishes all the steps above into one operation. That's the common
method of doing temporal interpolation - and it introduces nonzero values
just as the process above eventually introduces nonzero (interpolated
values). So, no, there aren't "problems" as such - just the task of doing
interpolation in some reasonable way. There are lots of methods for
computing the values.

Fred






.

Relevant Pages

  • Re: dividing two signals using fft
    ... Otherwise set estimate of that point to zero. ... filter, given just the output of the filter. ... Guessing that the input signal's spectrum in the bandstop region is ...
    (comp.dsp)
  • Re: Should the normal SINE and Zero padded SINE curves be the same for fft output?
    ... Under more general conditions, and assuming adequate sample rate, then all of the information is preserved and temporal zero padding works to interpolate the frequency domain with redundant samples. ... At this point there has been a rectangular windowing and the original spectrum that we "know" has been convolved with a sinc. ... The spectral spreading of a rectangular window with an equal number of zeros appended is +/- 1 spectral sample and the values are pretty large. ...
    (comp.dsp)
  • Re: Desired Sum of Two Curves; suggestions?
    ... > I'm working on an adaptive digital filter that requires two ... The sum b+cresults in a curve that rises from zero at ... squared error of Ea and the squared error of Eb. ...
    (sci.math)
  • Re: FFT and time domain amplitude after FFT convolution
    ... the values of both signals by the square root of the number of samples ... multiplies of a "normal" DSP scaling approach. ... The lowpass filter has gain 1.0 in the passband - so all the low frequency ... Now, if you zero pad the filter unit sample response, the passband response ...
    (comp.dsp)
  • Re: DSP Riddle: Infinitely Narrow Notch Filter
    ... Then filter the output with the inverse filter - ... For a sinusoid with frequency w0, ... output of the FIR would be equal to zero, ... A real notch filter, like r b-j's, has ...
    (comp.dsp)