5
$\begingroup$

Let's simulate sinusoids of two frequencies using the following Matlab code:

fs = 1000;
t = 0 : 1/fs : 1 - 1/fs;
f1 = 3; f2 = 3.5;
x1 = cos(2*pi*f1*t);
x2 = cos(2*pi*f2*t);
L1 = length(x1); L2 = length(x2);

If I take the FFT of the first signal using:

X1 = fft(x1);

and plot the resulting magnitude spectrum using:

figure; subplot(2, 1, 1); plot(t, x1)
subplot(2, 1, 2); plot([-L1/2 : (L1/2 -1)]*fs/L1, fftshift(abs(X1)))

I find that the resulting magnitude spectrum exactly matches what I would expect (i.e. frequencies of $\pm$ 3 Hz have a height of 500 - which is 0.5*L1 times the magnitude of the 3 Hz component - and all other frequencies have a height of 0).

enter image description here

When I produce the same plot for x2, I find that the spectral energy has been distributed over frequencies around 3-4 Hz, resulting in a decrease in the magnitude of the peak at 3 Hz from 500 to around 320:

X2 = fft(x2);
figure; subplot(2, 1, 1); plot(t, x2)
subplot(2, 1, 2); plot([-L2/2 : (L2/2 -1)]*fs/L2, fftshift(abs(X2)))

enter image description here

From my understanding, this is due to the way that the DFT operates: it correlates sinusoids that have an integer number of cycles over the length of the signal with the signal. Since x2 has 3.5 cycles over its 1000 samples, neither a sinusoid of 3 Hz nor one of 4 Hz can exactly match the signal, although these two frequencies are the closest of all frequencies. Hence, we see large peaks at both of these frequencies.

If I zero-pad the signal, however, with 1000 additional zeros, I am able to find a 3.5 Hz component because the sinusoid that has 7 cycles in 2000 samples (with each sample corresponding to 1/1000 = 0.001 s) corresponds to a 3.5 Hz sinusoid (since we always scale the bins by fs/L = 1000/2000 = 0.5; so 0.5*7 = 3.5 Hz), and this exactly matches the signal in the first 1 second. Moreover, the magnitude of the peak is now 500, which matches the magnitude of the peak found for the 3 Hz signal without zero-padding.

x2 = [x2 zeros(1, 1000)];
X2 = fft(x2);
L2 = length(x2);
t_zeropad = [0:L2-1]/fs;
figure; subplot(2, 1, 1); plot(t_zeropad, x2)
subplot(2, 1, 2); plot([-L2/2 : (L2/2 -1)]*fs/L2, fftshift(abs(X2)))

enter image description here

This leads to a several related questions:

  1. What gives rise to the side lobes in the third figure? It's not because of the discontinuity at t = 1 because the effect is still present when the input signal is changed from cosine to sine, which makes the signal continuous at t = 1.
  2. By what factor do you scale the magnitude of the FFT by when you've zero-padded your signal? I know that for a sinusoidal signal that has not been zero padded and for which the number of cycles of the sinusoid within the length of the signal is an integer, you divide the magnitude by L/2. So in the first example, you'd divide 500 by (1000/2) to get 1, which matches the amplitude of the cosine wave. After zero-padding, the length of the signal is now 2000, so L/2 would be 1000, which means the peak amplitude in the magnitude plot would be 0.5. Should this scaling factor change when you zero pad?
  3. Does the factor change when the sinusoid does not evenly fit within the number of samples being analyzed, when you are dealing with a signal that is a linear combination of multiple sinusoids, or when you are dealing with a more complex signal (e.g. e(-t))?
  4. If someone just gave you a signal and didn't tell you whether zero-padding had been done or not, how would you be able to tell by what factor to scale the magnitude of the FFT to compute the amplitudes of the frequency components?
  5. Lastly, I noticed that if you zero-pad the signal x1, which has a frequency of 3 Hz, by 1000 samples, and take the FFT, we again see that at a frequency of 3 Hz, the magnitude is 500; that the spectral energy is spread out near 3 Hz; and that there are side lobes present (see figure below). With the original signal though (not zero-padded), I did not have these artifacts. This leads me to believe that, in a sense, zero-padding adds noise because, based on the magnitude spectrum, you are introducing frequency components which are not actually present. Is this a sensible way of thinking about this? Does this mean that you should not zero-pad unless you "have to," and if so, how do you know whether you have to or not? By how much should you zero-pad?

enter image description here

$\endgroup$
  • $\begingroup$ Check this video on Frequency resolution using Zero Padding. $\endgroup$ – Satadru Mar 31 at 7:58
5
$\begingroup$

All effects you see have to do with windowing. Your signal can be seen as a truncated (i.e., rectangularly windowed) sinusoid. If $s[n]$ is your signal, and $w[n]$ is the window, the signal you analyze is

$$\tilde{s}[n]=w[n]\cdot s[n]\tag{1}$$

With the discrete-time Fourier transform (DTFT) defined by

$$S(f)=\sum_{n=-\infty}^{\infty}s[n]e^{-j2\pi nf}\tag{2}$$

we can rewrite Eq. $(1)$ in the frequency domain

$$\tilde{S}(f)=W(f)\star S(f)\tag{3}$$

where $\star$ denotes convolution. If $s[n]$ is a sinusoid, then Eq. $(3)$ implies that $\tilde{S}(f)$ is just the spectrum of the window shifted to the sinusoid's frequency.

What does this have to do with what you see in your figures? If we realize that the discrete Fourier transform (DFT) of a sequence is just a sampled version of the DTFT of the same (finite length) sequence, then everything you see can be explained by that sampling process. Note that the DFT of $\tilde{s}[n]$ is given by

$$\tilde{S}_{DFT}[k]=\sum_{n=0}^{N-1}s[n]e^{-j2\pi kn/N}=\tilde{S}\left(\frac{2\pi k}{N}\right)\tag{4}$$

Zero-padding means changing the DFT length $N$ without adding more signal (i.e., information), which just results in a denser sampling of the underlying DTFT of the signal. So you could say that the side-lobes have always been there, but they only become visible by sampling on a denser frequency grid, which is achieved by zero-padding. Zero-padding definitely does not introduce noise in the sense you suspect it would do.

Since zero-padding just changes the sampling interval in the frequency domain, it does not change any scaling factors.

Also have a look at the following related answers: here, here, here, and here.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I follow you until your second-to-last statement about scaling factors. If the scaling factor doesn't change when you zero-pad, then, according to the amplitude spectrum, the amplitude of the 3 Hz wave when the signal is zero-padded is 0.5 (since dividing 500 by 2000/2 = 0.5), which is incorrect since it should be 1. I looked at the third related answer and saw your note there that amplitude scaling only takes place when performing the IDFT. If this is the case, how can you tell what the amplitude should be from the DFT if scaling by L/2 doesn't always guarantee that the amplitude is correct? $\endgroup$ – Vivek Subramanian Oct 20 '16 at 16:36
  • $\begingroup$ @VivekSubramanian: I mean that even after zero-padding the scaling factor remains the same as without zero-padding; so in both cases you'd have $L/2$, where $L$ is the length of the original signal, without the appended zeros. In practice you usually know if the signal was zero-padded before applying the DFT or not. $\endgroup$ – Matt L. Oct 20 '16 at 21:59
2
$\begingroup$
  1. Zero-padding does not affect DFT magnitude of the original N-DFT Samples. Overall energy does increase in the longer DFT and that is because we have introduced non-zero samples in between N-point DFT.
  2. Zero-padding does not add noise to the DFT. The side-lobes appearing are as a consequence of polynomial interpolation which happens when we take DFT of a zero-padded sequence. Please see below explanation.
  3. And, NO, the side-lobes were not always there. Because zero-padding cannot increase spectral information in any way. So, it cannot reveal any new information which N-point DFT was not showing.
  4. If you do not know how many zeros were added before DFT was taken, you can take IDFT to figure out how many zeros were added, because IDFT will give you zero-padded time-domain sequence back.

Explanation:

Zero-padding an N-length sequence to get an L-length sequence before taking Discrete Fourier Transform, essentially means adding (L-N) zeros at the end of the sequence. Now, any length N sequences maximum frequency resolution is $2\pi/N$ and by zero-padding the sequence with (L-N) zeros, are we increasing the resolution to a finer $2\pi/L$ ?

The answer is NO.

The separation between two frequency component has decreased to $2\pi/L$, but this decrease in frequency separation will not reveal any finer details in the DFT. Ofcourse, it looks like it does show finer details but it is not so. Why?

Because, taking L-point DFT $X^{(L)}$ of a N-length sequence $x$ whose N-point DFT is $X^{(N)}$ can be achieved by the following Matrix multiplication :

$X^{(L)} = M_{L,N}.X^{(N)}$, where $M_{L,N}$ is a matrix formed from first N columns of L x L DFT Matrix $W_{L}$ multiplied with Conjugate of N x N DFT matrix $W_{N}$, so,

$M_{L,N} = W^{'}_{L}.W^{H}_{N}$, where $W^{'}_L$ is a L-by-N matrix of first N columns of $W_{L}$.

So, the whole point I am trying to make is that we are not adding any extra spectral information by taking DFT of zero padded sequence. Zero-padding adds no extra spectral information which was already not there.

Further, it can be shown that L-point DFT of a N-Length sequence is actually a Lagrange Polynomial interpolation of the N-point DFT samples and hence there is no spectral information increment.

Zero-padding is just Cosmetics to make the DFT look more attractive.

The side-lobes or the fattening of DFT plot that appears in DFT of zero-padded sequences is a consequence of this Lagrange polynomial interpolation of the N-Point DFT samples. We can interpolate any N-length sequence to L-length by doing this polynomial interpolation, zero-padding and taking L-point DFT will not even be required. You can obtain the same L-point DFT samples via Lagrangian Interpolation.

And as you increase zeros at the end of time domain length N sequence, Lagrange Polynomial Interpolation converges to Sinc interpolation of N-point original DFT Samples. This can again be verified by zero-padding your sinusoidal signal by a large value and then taking DFT, you will see a Sinc shape forming at the sinusoidal frequency sample. That is only a result of Lagrangian interpolation converging to Sinc interpolation.

This answers your question of whether zero-padding affects magnitude of DFT or not. It just introduces non-zero interpolated samples in between original N-point DFT samples. Anyone who is telling that frequency resolution increases by zero-padding is not well-informed or has learned from not so reliable resource.

You can go through the following book by Vetterli & Prandoni for reliable understanding of Discrete Signal processing : [https://www.sp4comm.org/][1]

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.