From: Fred Marshall on
rsk wrote:
>> Fred Marshall wrote:
>>
>> I should have added:
>>
>> 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.
>>
>> So, if we're talking about the continuous Fourier Transform then this
>> works just fine as the extents are infinite or at least finite over a
>> single or multiple periods of a periodic waveform. And, the
>> interpolation is nice but not necessary for such things as
> reconstruction.
>> Of course, when one uses a rectangular window or gate function then it
>> introduces high frequency components which then suggests that the
>> sampling frequency is inadequate - because of the introduction of those
>> higher frequency components.
>>
>> It's interesting that because we're fairly well forced to use a window
>> of some sort that this aspect is often ignored - while other aspects are
>> more highly emphasized. It's as if it's *IMPORTANT* to sample at Fs>2B
>> and then blithely impose a finite window on the data. :-)
>>
>> Fred
>>
>
> Just the last question, if the Sine and zero padded Sine are different
> because the former being multiplied by a rectangular window in the time to
> get the later, wouldn't it be improper to zero-pad a data that is acquired
> on field? The data contains 700 samples and if I zero pad it to go to the
> 1024 mark(for fft to be fast), my concern is that I will be introducing
> additional frequencies(leakages) by this.
>
> I asked this because there is a field problem for which vibration data has
> been collected and the test person has given me data with only 700 samples.
> If I just 'FFT' it and if I 'FFT' it with adding zero's upto 1024, I would
> get data at additional frequencies which, if I input to my computer
> simulation model, would give me wrong response at those frequencies which
> have been introduced due to zero padding.
>
> Any comments?
>
> Rahul

Rahul,

"Improper" is too strong a term to use. Other terms like "useful",
"reasonable", "acceptable" are a bit more to the point in all this.

Starting with the 700 samples:

- I will assume that there is an underlying signal that goes on for a
longer temporal epoch. And, we'll assume that we know its spectrum.

- Let's say that even before sampling that a shorter temporal epoch is
chosen which will support just 700 samples. At this point there has
been a rectangular windowing and the original spectrum that we "know"
has been convolved with a sinc. Thus, spectral spreading has occurred
which we might also refer to as "leakage". That is, lines become wider
by virtue of the main lobe of the sinc (that's the spreading part) and
otherwise "zero" areas become not so zero due to the "tails" of the sinc
(that's the leakage part). This has all happened before any sampling or
actual transforming (except in our heads).

- At this stage you may as well just take the 700 samples and DFT / FFT
the 700 samples and be done with it.

- But, since we've now introduced sampling then it's worth mentioning:
Because there is now a discrete time sequence, it's spectrum is now
periodic around multiples of Fs.

- And, although we could Fourier Transform (the continuous kind) those
700 samples, we decide to DFT them instead. This means the spectral
result is also sampled. Because the spectrum is now a discrete sequence
then the temporal sequence is likewise periodic around multiples of T
where T is the length of the original temporal epoch and T=1/NFs.

- Should we decide to zero-pad the 700 samples to either 1024 or 1400
then we effectively change the temporal period which increases the
spectral sample rate - obviously the temporal sample rate stays the
same. It's the increase in spectral sample rate that is the
interpolation in frequency that results.

So, no, you don't effectively introduce new frequencies by doing this.
What you do is introduce new frequency samples that interpolate what
would have been the original ones. And, in so doing, you may introduce
non-zero samples that weren't evident before. Viewing these as "new
frequencies" is pretty awkward I think.

A good way to think of this is that the windowing, sampling and
transforming is a "system" that you will apply to a variety of signals.
This system introduces spectral effects well before the zero padding
step and you can see those effects by using various signals as inputs to
the system.

The sine wave has good and bad aspects because you can obscure the
spectral spreading by selecting a single or another integer number of
cycles in the sample. But, if you double the spectral samples in your
original example then you will see the peaks of the spectral spreading
and leakage as well. The spectral spreading of a rectangular window
with an equal number of zeros appended is +/- 1 spectral sample and the
values are pretty large. So, for a 1Hz line you will see energy at 0.5,
1.0 and 1.5Hz if you zero pad to 2X the number of samples. But, that
was there all the time, you just didn't compute it. And, you will see
peaks of spectral leakage at 1Hz intervals on the 1/2Hz. Those were
also already there but you just didn't compute them either.

This is why a more general signal with multiple lines and noise is a
better test case for your "system".

Fred
From: Greg Heath on
On Feb 8, 3:05 pm, dbd <d...(a)ieee.org> wrote:
> On Feb 8, 6:04 am, Greg Heath <he...(a)alumni.brown.edu> wrote:
>
> >...
>
> > Why not just periodically extend the 700 samples to 1400
> > or 2100 . I'm not worried about powers of 2, just a "cleaner"
> > interpolation.
>
> > Hope this helps.
>
> > Greg
>
> Zero-extending by an integer multiple of the original sample count
> simply assures that the new frequency domain sample set includes the
> samples obtained from transforming just the original sample set. You
> might consider this a 'cleaner' interpolation.
-----SNIP

I meant periodic extension by an integer multiple of the original
sample count would yield a cleaner interpolated spectrum than
integer multiple zero-padding because it would not have the
zeropad sinc function lobe artifacts.

> Periodic extension is a theoretical construct that is only implemented
> if the signal in the sample set is stationary and periodic in the
> sample set. If so, the new sample set represents the original signal
> with a longer window with a narrower response about each component in
> the frequency domain.

without the sidelobes caused by zeropad windowing.

> With real world data, how do you perform periodic extension? You can't
> get better results by just repeating the data set unless the signal is
> stationary and periodic in the sample set.

It depends what you mean by "better" (.. sounds like Bill Clinton).

In comparison with zero-padding it would have narrower mainlobes
without zeropad sinc function sidelobes. Otherwise it would still
have all of the usual problems ... aliasing, Gibbs, ...

------SNIP

> If you do have signals that consist only of components that are
> periodic in the sample set, it serves no purpose to 'extend' the data
> set without additional samples because the fft of the original data
> set will produce samples only at the frequencies of the possible
> periodic components. There will be no 'leakage' if the periodic
> assumption is valid because the response of the rectangular window (a
> sinc function) convolved with the signal components will have zeros at
> all other frequency samples.

Good point.

> This is also the motivation for
> techniques such as synchronous sampling: choose to sample so that the
> assumption is valid for the signals of interest. If you have
> synchronously sampled, you can synchronously average to get signal
> processing gain against noise and interference that aren't synchronous
> to your samples. In this case you average multiple sample sets before
> the fft and reduce fft size and processing load.

Hope this helps.

Greg
From: dbd on
On Feb 10, 6:11 am, Greg Heath <he...(a)alumni.brown.edu> wrote:
> On Feb 8, 3:05 pm, dbd <d...(a)ieee.org> wrote:
>>..
>
> I meant periodic extension by an integer multiple of the original
> sample count would yield a cleaner interpolated spectrum than
> integer multiple zero-padding because it would not have the
> zeropad sinc function lobe artifacts.

Zero-extending doesn't produce any artifacts, windowing does that.

Extending the data with another copy of the data gives a gain of 2 and
inserts alternate zeros in the fft output, so what is the point in
that?

>
> > Periodic extension is a theoretical construct that is only implemented
> > if the signal in the sample set is stationary and periodic in the
> > sample set. If so, the new sample set represents the original signal
> > with a longer window with a narrower response about each component in
> > the frequency domain.
>
> without the sidelobes caused by zeropad windowing.

Again, sidelobes come only from windowing. If the signals are
periodic before extension there are no artifacts in the samples
because you have calculated no samples at frequencies where the
artifacts are not zero. If you use an fft larger than the data set by
zero extending at least some of your frequency samples will be at
frequencies where the windowing-generated artifacts are not zero. (You
can also get samples at different frequencies with a smaller fft by
'wrapping' the data.)

>
> > With real world data, how do you perform periodic extension? You can't
> > get better results by just repeating the data set unless the signal is
> > stationary and periodic in the sample set.

Actually, as I've pointed out above you can't get better results
without more independent data.

>
> It depends what you mean by "better" (.. sounds like Bill Clinton).
>
> In comparison with zero-padding it would have narrower mainlobes
> without zeropad sinc function sidelobes. Otherwise it would still
> have all of the usual problems ... aliasing, Gibbs, ...

Extending with copies of the data does not produce 'narrower'
sidelobes. Only a bigger original data window does that. If you go to
a rectangular window twice as long and your signal actually repeats in
the windowed samples, every other frequency component -is- actually
zero and your frequency samples will be at frequencies where the
windowing artifacts are zero. (And you could have calculated the
response with a smaller transform.)

Oh, did I mention that the sinc function characteristics are a
characteristic of the window and are independent of the zero-
extension? Zero-extension only changes where you sample the frequency
response.

> ...

Periodic extension may be a useful pedagogical deceit, but it is not
an operation that you need to explicitly perform to analyze real-world
data.

Dale B. Dalrymple
From: dbd on
On Feb 11, 2:49 am, "rsk" <kalera...(a)yahoo.com> wrote:

> ...
> All of you talked about the effect of zero padding on the frequency. Those
> were quite valuable comments. However, can I be sure that by zero padding,
> i would not see difference in amplitudes in FFT?( compared to that without
> padding)

If you sample a non-constant curve, the values of the samples will
depend on where you sample the curve. Zero padding controls where you
sample the curve that consists of the convolution of your signal and
the non-zero window that selected your samples of that signal.

>
> As someone said in the previous replies to my original post, the energy
> would distribute over more points if I increase the # of samples used for
> FFT.

If someone actually said that,they were mistaken. If you mean zero-
extension when you say 'increase the # of samples', it does not change
the energy 'distribute'. It changes where you sample the 'distribute'.
If you have N samples in your data window and calculate a N point fft,
you get a set of frequency samples you can calculate the magnitudes
of. If you zero-extend with another N zeros and calculate the fft and
then the magnitude, you will get the same sample values as the N point
fft gave you with an additional samples in between each of the
original samples. Look at the .jpg files I gave urls for to see
examples with a 4 Hz signal that has a peak the one of the frequencies
of the N point samples and a 4.5 Hz signal that has a peak at one of
the new samples in the 2N samples. There are also figures that show x4
and x16.

Dale B. Dalrymple
From: Greg Heath on
On Feb 10, 11:56 am, dbd <d...(a)ieee.org> wrote:
> On Feb 10, 6:11 am, Greg Heath <he...(a)alumni.brown.edu> wrote:
>
> > On Feb 8, 3:05 pm, dbd <d...(a)ieee.org> wrote:
> >>..
>
> > I meant periodic extension by an integer multiple of the original
> > sample count would yield a cleaner interpolated spectrum than
> > integer multiple zero-padding because it would not have the
> > zeropad sinc function lobe artifacts.
>
> Zero-extending doesn't produce any artifacts, windowing does that.

In this comparison zeropadding must be considered windowing.

The zeropadded function [z zeros(1,N)] is the windowed
periodically estended function [ones(1,N) zeros(1,N)] .* [ z z].

> Extending the data with another copy of the data gives a gain of 2 and
> inserts alternate zeros in the fft output, so what is the point in
> that?

For periodic functions, zeros instead of sinc sidelobes
cause the resulting spectra to appear "cleaner".
Granted, this can be done directly without using up
fft resources. However, my original query was more
interested in the comparison w.r.t. windowed samples
of nonperiodic functions that can be considered as
windowed samples of the periodic extension calculated
using ifft(fft(z)).

Then there is a distinct difference in the spectra for
the periodically extended and zeropadded functions.
In particular, the former was able to display peaks
between the original bin frequencies much more clearly.

> > ...
>
> Periodic extension may be a useful pedagogical deceit, but it is not
> an operation that you need to explicitly perform to analyze real-world
> data.

My experience with real world data has been pretty
much limited to the inverse operation of deducing
physical motion of radar targets by zeropadding
Doppler spectra.

However, it has been rather fascinating to compare
the spectra of periodic extensions and windowed
periodic extensions (= to zeropadded originals) for
cooked-up nonperiodic time functions:

close all; clear all; clc; k=0;

f01 = 1 % 1 Hz signal
T01 = 1/f01 % 1 sec period
Fs = 16
dt = 1/Fs % = 0.0625 sec sampling interval
T = T01 % 1 period sample
N = T/dt % = 16 No of points
t = 0:dt:T-dt; % = dt*(0:N-1);

w01 = 2*pi*f01; w02 = 1.5*w01; w03 = 2*w01; w04 = 2.5*w01;
z(:,1) =[ rand*cos(w01*t'+2*pi*rand) + rand*cos(w02*t'+2*pi*rand)...
+ rand*cos(w03*t'+2*pi*rand) + rand*cos(w04*t'+2*pi*rand)];
z(:,2) = exp(-(t'-T/2).^2).*z(:,1);
z(:,3) = exp(-t'/T).*z(:,1);
z(:,4) = exp((t'-T)/T).*z(:,1);
k=k+1; figure(k)
for i = 1:4
subplot(2,2,i)
plot(t,z(:,i))
end
subplot(2,2,1); title('Original Time Functions')

N2 = 2*N % = 32
T2 = N2*dt % = 2*T = 2
t2 = 0:dt:T2-dt; % = dt*(0:2*N-1);

z2 = [z; z]; % Periodic continuation of z
k=k+1; figure(k)
for i = 1:4
subplot(2,2,i)
plot(t2,z2(:,i))
end
subplot(2,2,1); title('Periodically Extended Functions')

w = [ones(size(z)); zeros(size(z))] ; % Square window filter
z3 = w.*z2; % Windowed Sample
k=k+1; figure(k)
for i = 1:4
subplot(2,2,i)
plot(t2,z3(:,i))
end
subplot(2,2,1); title('Zero-Padded Functions')

df = 1/T % = Fs/N = 1
f = df*(-N/2:N/2-1); % = -Fs/2:df:Fs/2-df

Z = fft(z/N);
k=k+1; figure(k)
for i = 1:4
subplot(2,2,i)
plot(f,abs(fftshift(Z(:,i))))
end
subplot(2,2,1); title('Spectra of Original Time Functions')


df2 = 1/T2 % = df/2 = 0.5
f2 = df2*(-N2/2:N2/2-1);

Z2 = fft(z2/N2);
k=k+1; figure(k)
for i = 1:4
subplot(2,2,i)
plot(f2,abs(fftshift(Z2(:,i))))
end
subplot(2,2,1); title('Spectra of Periodically Extended Functions')

Z3 = 2*fft(z3/N2);
k=k+1; figure(k)
for i = 1:4
subplot(2,2,i)
plot(f2,abs(fftshift(Z3(:,i))))
end
subplot(2,2,1); title('Spectra of Zero-Padded Functions')

for j = k:-1:1
figure(j)
end

% tilefigs % See the MATLAB File Exchange
return

Hope this helps.

Greg