Prev: CFP: The 2010 International Conference on Data Mining (DMIN'10), USA, July 2010
Next: FFTW Power Spectrum
From: Fred Marshall on 9 Feb 2010 07:08 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 10 Feb 2010 09:11 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 10 Feb 2010 11:56 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 11 Feb 2010 12:20 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 13 Feb 2010 07:19
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 |