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
Interpolation And Low-Pass filtering
Started by ●December 15, 2005
Reply by ●December 15, 20052005-12-15
"Himanshu" <hs.chauhan@gmail.com> wrote in message news:1134669245.172396.282710@o13g2000cwo.googlegroups.com...> 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:> 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
Reply by ●December 16, 20052005-12-16
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
Reply by ●December 16, 20052005-12-16
"Himanshu" <hs.chauhan@gmail.com> wrote in message news:1134741316.351797.113470@g49g2000cwa.googlegroups.com...> 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
Reply by ●December 18, 20052005-12-18
