**The Effects of zero-padding FFT's and the**

**Windowing Function on Time sampled Waveforms**

**1. Introduction**

The United Sates administration performed a series of measurements on
High Frequency (HF) radars that employed FMCW and gated FMCW waveforms
in January 2007. The measurements were done according to the techniques
M1177 for peak sampled emission spectra in the frequency domain using a
spectrum analyzer, and in the time domain using an Agilent Vector Signal
Analyzer (VSA). The details of this measurement are in JRG-80 and
JRG-81.

The measurements have indicated that a zero-padded time series has a
different power spectrum density (PSD) than non-zero-padded time series.
The issue is important since at least one administration is proposing
the use of zero-padded time series as an input to the PSD computation
for ITU-R SM1541 compliance measurements. The purpose of this
contribution is to describe the effect of zero-padding in mathematical
terms and to serve as a starting point for the discussion of using
Fourier transformed (FT) time sampled data for radio spectrum emission
compliance measurements.

For the purposes of this contribution, zero-padding is defined as
appending zero values to a time series. The time series is typically a
time-sampled waveform collected with a sample rate *f~s~*. The appended
zero values are treated as additional samples collected at the same
rate, and therefore extending the total collection time.

**2. Numerical evaluation of the Fourier Transform for a discrete time
series**

The Fast Fourier Transform (FFT) is a computational algorithm for the
efficient evaluation of the Discreet Fourier Transform (DFT), which is
in turn a special case of the Discreet Time Fourier Transform (DTFT).
The FFT is a DTFT evaluated at a set of uniformly-spaced points in
frequency.

Definition of the DTFT:

The Discreet Time Fourier Transform for a time series $h(n)$ is
defined[^1] to be:

$H\left( e^{j\omega} \right) = \sum_{n = - \infty}^{\infty}{h(n)ealignl\begin{array}{r}

\end{array}^{- j\omega n}}$ (1).

For a fixed-length time series with N samples this becomes:

$H\left( e^{j\omega} \right) = \sum_{n = 0}^{N - 1}{h(n)e^{- j\omega n}}$
(2).

Suppose that we create a new time series, $g(n)$ of length N+M, that is
defined as follows:

$g(n) = h(n) + \text{zeros}(N \leq n \leq N + M - 1)$.

This is the equivalent of appending *M* zeros onto the end of $h(n)$.
The DTFT of $g(n)$is (from eq. 2):

$\begin{array}{r}
G\left( e^{j\omega} \right) = \sum_{n = 0}^{N + M - 1}{g(n)e^{- j\omega n}} \\
\sum_{n = 0}^{N - 1}{h(n)e^{- j\omega n}} + \sum_{n = N}^{M - 1}{0 \cdot e^{- j\omega n}} \\
H(e^{j\omega})
\end{array}$ (3).

Equation 3 shows that zero-padding does not alter the Fourier transform
of the time series. This is consistent with an intuitive argument that
by appending zeros that, additional energy is not added to the signal
nor is there any re-arranging of the energy content. Therefore, there
can be no change to the PSD.

So what can account for the difference in calculated PSD's in the
experiments? Part of the answer lies in the subtleties of calculation
itself. The transform in equations 1 -- 3 is a continuous function of
$\omega$. To achieve a numerical result, the transform is evaluated at a
fixed set of values in $\omega$. The number and choice of these
evaluation points can give dramatically different curves.

**2.1 The Discreet Fourier Transform and Fast Fourier Transform**

Most data processing algorithms that estimate the PSD perform a Fast
Fourier Transform (FFT). The FFT is an optimized algorithm for computing
a special case of the Discreet Fourier Transform (DFT). The DFT is
defined as[^2]:

$H(k) = \sum_{n = 0}^{N - 1}{h(n)e^{- j2\pi\frac{\text{nk}}{N}}}$ for
$0 \leq k \leq N - 1$ (4).

This is the same transform as defined in equation 1, but evaluated at N
equally-spaced points from ω = 0 to (N-1)2π/N (the frequency units are
normalized with 2π being the angular sample rate). When N is a power of
2, symmetries in the transform can be exploited to reduce the
computational complexity. The result is the FFT.

When computing the FFT, the evaluation points are fixed. The only way to
compute more detail in the PSD is to increase the number of points, N.
The simplest way to do this without acquiring more samples in the time
series is to add zeros. This is a way to force the FFT algorithm to
sample the spectrum at smaller frequency intervals.

**2.1.2 Zero-padding Simulated Waveforms**

Example 1 -- rectangular pulse.

Consider the time series in Figure 1. This is a real-valued rectangular
pulse with no windowing and a small amount of noise.

![](media/image1.png){width="4.303472222222222in"
height="3.2395833333333335in"}

Figure 1 - Rectangular pulse. N = 1024.

In Figure 2, the computed FFT's are shown for N=1024, and zero-padded
versions with N = 2048 and N = 4096. Note that the computed points are
common to each curve. The effect of zero-padding is to fill-in more
detail in the spectrum.

![](media/image2.png){width="4.303472222222222in"
height="3.2395833333333335in"}

Figure 2 - PSD of the original time series, the series with 2X padding,
and the series with 4X padding.

This is the only impact that zero-padding can have on a given set of
time samples. In cases where other differences are evident, there must
be other artifacts in the processing. These may be:

-   Scaling.

-   Windowing

-   Post-FFT processing, such as averaging multiple PSD's.

Each of these techniques are common to FFT-based PSD processing
routines.

Example 2: $\text{cos}(\omega t)$

Figure 3 is a real-valued time signal that is sampled on an interval.
The sampling operation consists of a) multiplying the function by
sequence of dirac delta functions in time and b) selecting a finite set
of samples by multiplying the infinite set with a rectangular window.

![](media/image3.png){width="5.013194444444444in"
height="3.7465277777777777in"}

Figure 3 -- Real-valued time signal,$\text{cos}(\omega t)$, sampled on
an interval.

The Fourier transform of these discrete samples is a continuous function
that is the convolution of the transforms of the cosine function, the
set of Dirac delta functions, and the rectangular window. The result is
a sinc function of width 1/(window size) that is centered at the
frequency of the cosine, shown in Figure 4.

![](media/image4.png){width="4.804861111111111in"
height="3.6145833333333335in"}

Figure 4 -- Continuous Fourier transform of the samples shown in Figure
3. Only the first Nyquist region is plotted.

The FFT of these samples is a set of points from the Fourier transform
in Figure 4 at a set of frequency values uniformly spaced between 0
and$2{\pi f}_{s}$, where$f_{s}$ is the sampling frequency. Figure 5 is a
plot of the samples. Figure 6 is a plot of 3 FFT's: the first using only
the original points, a second using the original points zero-padded to
twice the original length, and a third using the original points
zero-padded to 4 times the original length. The zero padded versions
show the sinc characteristic that is present but missed in the red
curve. The common sampling points are the same for all three curves,
subject to small differences due to added noise.

![](media/image5.png){width="5.084722222222222in" height="3.81875in"}

Figure 5 - Samples of$\text{cos}(\omega t)$. The sample time was chosen
to include exactly 8 periods of cosine. One cycle of the cosine is 128
samples.

![](media/image6.png){width="5.151388888888889in"
height="3.8631944444444444in"}

Figure 6 - Three versions of the FFT, the unpadded version in red shows
that the spectrum is uniquely sampled at the zeros with the exception of
the two center frequency points.

Next, the function is changed slightly in frequency. The time series now
includes almost 8 full cycles of the cosine function (the period is 121
instead of 128). The FFT's are shown in Figure 7. Note in this figure
how the FFT of the original sample sequence results in the calculation
points being near the maxima of the underlying sinc function (except for
near the center frequency). As in Figure 6, the common points are the
same in all three emission plots in Figure 7. Changing the frequency of
the cosine waveform could not have caused its emissions to roll-off at a
different rate. The window function is the same for both time sequences.
The difference for the emissions levels for the red curves in Figures 6
and 7 is due entirely to the change in the position of the lobes in the
sinc function (due to the change in frequency) relative to the fixed FFT
calculation points.

![](media/image7.png){width="5.309027777777778in"
height="3.9805555555555556in"}

Figure 7 - FFT's of a cosine with period 121. The zero padding was done
in the same manner as for the FFT's of Figure 6.

**2.1.2 Zero-padding Measured Waveforms**

To address the matter of zero padding an actual time sampled waveform
and taking multiple pulses in the FFT to transform it to the frequency
domain, the VSA was used to collect 10 seconds (\~20 pulses) of time
data (both magnitude and phase information) on each waveform. This data
was used in the following analyses.

The total sweep time T~sweep~ of the FMCW radar was 0.5 seconds. Between
each sweep, the waveform returns to the start frequency over a short
period known as the flyback time. For this radar, the flyback time was
estimated from the measured data to be approximately 100 μs. The chirp
bandwidth was 49.4 kHz. Figure 8 shows the FFT of 1 pulse of the data
with no zero padding and with 4 times zero padding, with a no other
windowing applied to the data. The figure shows that the 4 times padded
FFT reveals more power distributed along the out-of-band domain (OOB)
than the non-zero padded version. This is due to the same phenomena
described previously, namely the change in position of the underlying
sinc functions. Figure 9 zooms in on the out-of-band domain for this
waveform where the sinc function becomes more observable. The blue curve
(4 times zero padding) shows the familiar structure of the sinc
function, while the red curve has a much wider and unevenly sampled sinc
function. The blue curve better shows the appearance of the sinc
function, because the zero-padding has added more samples in the
frequency domain. As in the simulated results above, the points in the
non-zeropadded FFT are common to the zero-padded curve.

![](media/image8.png){width="5.183333333333334in" height="3.8875in"}

Figure 8 -- 1 Pulse of HF FMCW collected data, FFT'ed with 0x padding
and with 4x padding, no window function used.

![](media/image9.png){width="5.335416666666666in"
height="4.006944444444445in"}

Figure 9 -- Zoomed in view of 1 Pulse of HF FMCW collected data, FFT'ed
with 0x padding and with 4x padding, no window function used.

When multiple pulses are used in the FFT, the longer total collection
time results in a narrower frequency-domain effect of the windowing
function, and therefore the emissions seem to roll-off at a faster rate,
i.e., a time sampled waveform transformed to the frequency domain using
multiple pulses will exhibit a faster roll-off than a single pulse
transformed to the frequency domain. This was first reported in JRG-73
by the Australian administration. In addition to a narrower window, a
longer time sequence provides an increase in spectral resolution. The
real spectral resolution of an FFT is$\frac{f_{s}}{N}$, where$f_{s}$ is
the sampling rate, and N is the number of data samples. Adding zeros
will allow one to observe greater detail in the emission spectrum (by
interpolating samples in the frequency domain), but it will not allow
greater spectral resolution in the original data. Figure 10 shows a plot
of the FMCW waveform for 4 pulses used in the FFT with no padding and 4x
zero padding. Figures 11 and 12 show a comparison between 1 and 4 pulses
(both have been zero padded to the same length). It is evident in Figure
11 that the 4 pulse case exhibits 5 to 6 dB lower calculated emissions
in the OOB than the 1 pulse case due to the narrower window effect.
Figure 12 shows a zoomed in portion of Figure 11. It is easier to see
the difference in the spectral resolution in Figure 11, as the 4 pulse
case represented by the red trace shows a much narrower sinc function
than the 1 pulse case represented by the blue trace, even though the
spectral sampling is the same. This shows the difference in adding data
versus adding zeros to an FFT.

![](media/image10.png){width="5.399305555555555in"
height="4.054861111111111in"}

Figure 10 -- 4 Pulses of HF FMCW collected data, FFT'ed with 0x padding
and with 4x padding, no window function used.

![](media/image11.png){width="5.527083333333334in"
height="4.145138888888889in"}

Figure 11 -- Comparison of 1 pulse versus 4 pulses of HF FMCW collected
data, FFT'ed with 4x padding and no window function used.

![](media/image12.png){width="5.454861111111111in"
height="4.097222222222222in"}

Figure 12 -- Zoomed comparison of 1 pulse versus 4 pulses of HF FMCW
collected data, FFT'ed with 4x padding and no window function used.

**3. Conclusion**

Zero-padding a time series prior to processing (using the FFT) results
in the generation of frequency-domain samples that are more tightly
spaced. There is no additional information regarding the spectral
emissions that is revealed by this method. The apparent differences in
computed spectra for zero-padded versus non-zero-padded time series is
entirely the result of a tighter sampling of the windowing effects
present in the non-padded series. This contribution has shown the
differences in the output of various FFT's using both simulated signals
and transforming frequency domain measurements of actual radar systems.
The analyses shows that adding zeros or multiple pulses to the FFT of
time-sampled emission data changes the representation of the emission
spectra roll-off in the OOB in the frequency domain, but it does not
change the underlying spectrum. Therefore, before allowing transformed
time sampled data to be used for regulatory purposes, the inputs,
resolution, and windowing functions of the transforming FFT must be
carefully studied.

Appendix: MATLAB code for Simulated Examples

**Example 1**

samples = 1024;

pulsesize = fix(samples/(2\*sqrt(2)));

ts = \[ones(1,pulsesize),zeros(1,1024-pulsesize)\];

ts_zp2x = \[ts,zeros(1,length(ts))\];

ts_zp4x = \[ts_zp2x,zeros(1,length(ts_zp2x))\];

%add noise

ts = ts + 1e-3\*randn(1,length(ts));

ts_zp2x = ts_zp2x + 1e-3\*randn(1,length(ts_zp2x));

ts_zp4x = ts_zp4x + 1e-3\*randn(1,length(ts_zp4x));

%fft\'s

psd_ts = 20\*log10(abs(fft(ts)));

psd_ts_zp2x = 20\*log10(abs(fft(ts_zp2x)));

psd_ts_zp4x = 20\*log10(abs(fft(ts_zp4x)));

%plot

plot((\[0:length(psd_ts)-1\]-length(psd_ts)/2)/length(ts),fftshift(psd_ts),\'r\',\...

(\[0:length(psd_ts_zp2x)-1\]-length(psd_ts_zp2x)/2)/length(psd_ts_zp2x),fftshift(psd_ts_zp2x),\'b\',\...

(\[0:length(psd_ts_zp4x)-1\]-length(psd_ts_zp4x)/2)/length(psd_ts_zp4x),fftshift(psd_ts_zp4x),\'g\');

**Example 2** Note: change cwsize to 121 in line 4 to create figure 7.

samples = 1024;

%pulsesize = fix(samples/(2\*sqrt(2)));

%ts = \[ones(1,pulsesize),zeros(1,samples-pulsesize)\];

cwsize = 128;

ts = cos(2\*pi\*\[0:samples-1\]/cwsize);

ts_zp2x = \[ts,zeros(1,length(ts))\];

ts_zp4x = \[ts_zp2x,zeros(1,length(ts_zp2x))\];

%add noise

ts = ts + 1e-3\*randn(1,length(ts));

ts_zp2x = ts_zp2x + 1e-3\*randn(1,length(ts_zp2x));

ts_zp4x = ts_zp4x + 1e-3\*randn(1,length(ts_zp4x));

%fft\'s

psd_ts = 20\*log10(abs(fft(ts)));

psd_ts_zp2x = 20\*log10(abs(fft(ts_zp2x)));

psd_ts_zp4x = 20\*log10(abs(fft(ts_zp4x)));

%plot

plot((\[0:length(psd_ts)-1\]-length(psd_ts)/2)/length(ts),fftshift(psd_ts),\'r\',\...

(\[0:length(psd_ts_zp2x)-1\]-length(psd_ts_zp2x)/2)/length(psd_ts_zp2x),fftshift(psd_ts_zp2x),\'b\',\...

(\[0:length(psd_ts_zp4x)-1\]-length(psd_ts_zp4x)/2)/length(psd_ts_zp4x),fftshift(psd_ts_zp4x),\'g\');

set(gca,\'xlim\',\[-0.02,0.02\]);

set(gca,\'ylim\',\[-70,70\]);

legend(\'Orig.\',\'2X zeropad\',\'4X zeropad\');

ylabel(\'PSD (dB)\');

xlabel(\'Normalized Frequency\');

title(\'COS(\\omegat), \\omega = 2\\pi\*8\*n/1024\')

grid

[^1]: Kuc, Roman; Introduction to Digital Signal Processing; New York;
    McGraw-Hill; 1988; p. 67.

[^2]: Kuc, Roman; Introduction to Digital Signal Processing; New York;
    McGraw-Hill; 1988; p. 123.