| Author |
Message |
Himanshu
Guest
|
 Posted:
Thu Dec 15, 2005 11:54 pm Post subject:
Interpolation And Low-Pass filtering |
|
|
Hello Group!
I read that while interpolaton for upsampling we pad zeros (their
number decided by the factor of upsampling) and then the resultant is
low-passed. Its like that the data is being compressed (in time) in the
time domain and the corresponding frequency domain is expanding,
"pushing" the frequencies into the adjacent periods.
But when we pad a period with zeros (all zeros in the last of the
period), The frequency spectrum resolution is increased. Why isn't any
kind of filter needed there. The data is being compressed in time.
What I think is when you pad in between like:
xxxxxxx000xxxx000xxxx000xxx000xxx000xxx000xxx
You are basically moving "non-zero" frequency components into the
"adjacent" periods.
There "non-zero" components add to the signal already present there.
In contrast to when you pad at the end like:
xxxxxxxxxxxxxxxxxxxxxxxxxx000000000000000000000
These "zeros" are still going into the adjacent periods but because
they are zeros, their addition has no effect on the signal present in
the range they are aliasing.
Am I right in my thinking?
Thanks and regards
--Himanshu |
|
| Back to top |
|
 |
Fred Marshall
Guest
|
| Posted:
Fri Dec 16, 2005 1:04 am Post subject:
Re: Interpolation And Low-Pass filtering |
|
|
"Himanshu" <hs.chauhan@gmail.com> wrote in message
news:1134669245.172396.282710@o13g2000cwo.googlegroups.com...
| Quote: | Hello Group!
I read that while interpolaton for upsampling we pad zeros (their
number decided by the factor of upsampling) and then the resultant is
low-passed. Its like that the data is being compressed (in time) in the
time domain and the corresponding frequency domain is expanding,
"pushing" the frequencies into the adjacent periods.
But when we pad a period with zeros (all zeros in the last of the
period), The frequency spectrum resolution is increased. Why isn't any
kind of filter needed there. The data is being compressed in time.
What I think is when you pad in between like:
xxxxxxx000xxxx000xxxx000xxx000xxx000xxx000xxx
You are basically moving "non-zero" frequency components into the
"adjacent" periods.
There "non-zero" components add to the signal already present there.
In contrast to when you pad at the end like:
xxxxxxxxxxxxxxxxxxxxxxxxxx000000000000000000000
These "zeros" are still going into the adjacent periods but because
they are zeros, their addition has no effect on the signal present in
the range they are aliasing.
Am I right in my thinking?
|
Himanshu,
The quick answer goes like this:
(I call putting zeros at the end "zero padding" and putting zeros in between
"zero stuffing")
Zero padding makes a record longer / increases the number of samples without
changing the sample rate.
So, when a transform is computed, it is interpolated by virtue of the added
samples.
Zero stuffing makes a record longer also. But, it does so by increasing the
sample rate.
You can see that increasing the sample rate is an essential ingredient in
interpolation - adding interim samples, right?
And, doing this all by itself really does nothing because you really added
"nothing".
In fact, there's a way to "do it without doing it" as I'll describe below.
It implies that there's another step which is to convert the stuffed zeros
to nonzero values.
The operation is lowpass or interpolation filtering.
One way to interpolate that's equivalent to zero stuffing is to do it in the
frequency domain.
1) Take the original N samples in time. Don't bother to stuff with zeros.
2) Compute their FFT.
3) Repeat (perhaps simply by manipulating indexing / addressing arithmetic)
the transform M times - thus getting a higher apparent sample rate.
4) Lowpass filter by multiplying in frequency. This does the interpolation.
5) IFFT to get the interpolated time sequence.
An even faster although perhaps aliasing way to do the same thing using
indexing:
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].
Now, back to your first question:
| Quote: | But when we pad a period with zeros (all zeros in the last of the
period), The frequency spectrum resolution is increased. Why isn't any
kind of filter needed there. The data is being compressed in time.
|
This is because you're doing the same thing as above only in the time domain
instead of in the frequency domain. It's funny that people do this all the
time and don't complain much. But, if you do it in the frequency domain,
some do complain.
In fact, it doesn't matter which domain you're in - the dual process in the
other domain is the same dual process - at least in gross terms.
Well, there is one caveat or observation in the practical world:
We most often deal with real signals that all have a finite or limited
effective bandwidth.
We often deal with real signals that continue over long time epochs.
So, in comparison, these characteristics might have some affect:
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.
By this I mean: when you pad a period with zeros it's the same as
1) repeat the period M times to get M*N samples.
[Now look at the frequency domain. We have a new, longer "period" in time
so the number of frequency samples increases. But, there is no new spectral
information. The frequency spectrum has been zero stuffed!]
2) multiply (M-1)*N zeros to get the zero padded version. This is a perfect
"lowpass filter" but in the time domain. It is multiplying by a "gate"
function in time.
[Now look at the frequency domain. Now the zero-stuffed samples are
nonzero - they have been interpolated.]
So, we can more readily ask: "what does this do in terms of aliasing?"
First, adding the zeros does nothing at all does it?
In the frequency domain it has the effect of increasing the number of
frequency samples over the same sample rate or frequency period.
When the zero-padding is done in time it's the same as convolving the
zero-stuffed frequency samples with a sinc. That causes frequency domain
aliasing or "spectral leakage" which is a "nicer" term for the same thing.
So, what we do to eliminate this aliasing is to use a "window" on the
nonzero time sequence. The window function has a transform that has much
lower sidelobes or tails on it than does a sinc. So, the convolution in
frequency causes less leakage, thus aliasing.
The bottom line is:
Zero stuffing in time is the same as repeating the frequency domain M
times - increasing the sample rate. This causes no aliasing.
Zero stuffing in frequency is the same as repeating the time sequence M
times - increasing the time span. This causes no aliasing.
Zero padding in time is the same as zero stuffing in frequency plus
convolution with a sinc.
Zero padding in time is the same as:
1) repeating the time sequence M times
and
2) zeroing out the repetitions of the time sequence in the MN samples.
(multiplication by a gate).
It is step 2 that introduces aliasing.
Zero padding in frequency is the same as zero stuffing in time plus
convolution with a sinc (in time). It's the convolution that introduces
temporal aliasing or signal overlap. So, zero padding in frequency also
introduces aliasing.
Zero padding in time is the same as:
1) repeating the frequency sequence M times
and
2) zeroing out the repetitions of the frequency sequence in the MN samples.
(multiplication by a lowpass filter).
Fred |
|
| Back to top |
|
|
Himanshu
Guest
|
| Posted:
Fri Dec 16, 2005 5:16 pm Post subject:
Re: Interpolation And Low-Pass filtering |
|
|
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...
| Quote: | 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?
| Quote: | 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.
| Quote: | 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 |
|
| Back to top |
|
|
Fred Marshall
Guest
|
| Posted:
Sat Dec 17, 2005 12:14 am Post subject:
Re: Interpolation And Low-Pass filtering |
|
|
"Himanshu" <hs.chauhan@gmail.com> wrote in message
news:1134741316.351797.113470@g49g2000cwa.googlegroups.com...
| Quote: | 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,
| Quote: | 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.
| Quote: | 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 |
|
| Back to top |
|
|
Himanshu
Guest
|
| Posted:
Sun Dec 18, 2005 5:15 pm Post subject:
Re: Interpolation And Low-Pass filtering |
|
|
Fred,
Thank you very much. Its clear to me now!
Regards
--Himanshu
P.S.: Aren't you thinking about writing a book on DSP? |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in