FFT, zero padding and DFT bins

Hello,

I have a confusion regarding FFTs, zero padding and DFT bins. This is my
understanding, I wanted to know if it is correct since this is what I
understand from books but my tutor says otherwise.


Zero padding the signal in the Time domain and computing its FFT results in
the frequency spectrum being sampled more densely. It does not affect the
Spectral(Frequency) Resolution of the resulting FFT since the added zeros
don't matter in the FFT computation. This however, does change the Visual
Resolution (have 'data points' between the original bins) and for a plot in
Matlab for e.g, I can move (read off) between two DFT bins. (Ofcourse the
plot is Matlab is a linear interpolation of the data points).

I wanted to know if my understanding is correct. If so then do we say that
the DFT resolution has increased by zero padding the signal? 
Shouldn't the DFT resolution mean the frequency resolution?

Thanks.

wond3rboy <47228@dsprelated> wrote:
 
> I have a confusion regarding FFTs, zero padding and DFT bins. This is my
> understanding, I wanted to know if it is correct since this is what I
> understand from books but my tutor says otherwise.
 
> Zero padding the signal in the Time domain and computing its FFT results in
> the frequency spectrum being sampled more densely. It does not affect the
> Spectral(Frequency) Resolution of the resulting FFT since the added zeros
> don't matter in the FFT computation. This however, does change the Visual
> Resolution (have 'data points' between the original bins) and for a plot in
> Matlab for e.g, I can move (read off) between two DFT bins. (Ofcourse the
> plot is Matlab is a linear interpolation of the data points).

This sounds right. 

Note that an unpadded FFT gives you all the information that is in
the input data. Padding with zeros can't give you anything more.

Consider doubling the length by zero padding. Now all the original bins
are there, in addition to new bins between each one. Where do the values
for those new bins come from?
 
> I wanted to know if my understanding is correct. If so then do we 
> say that the DFT resolution has increased by zero padding the signal? 

Yes, you can say that.

> Shouldn't the DFT resolution mean the frequency resolution?

No. Say you plot a continuous curve from the data. Now the frequency
resolution is infinite. But there is no additional data to 
generate additional resolution.

-- glen

On Tuesday, 19 February 2013 19:35:53 UTC, wond3rboy  wrote:
> Hello,
> 
> 
> 
> I have a confusion regarding FFTs, zero padding and DFT bins. This is my
> 
> understanding, I wanted to know if it is correct since this is what I
> 
> understand from books but my tutor says otherwise.
> 
> 
> 
> 
> 
> Zero padding the signal in the Time domain and computing its FFT results in
> 
> the frequency spectrum being sampled more densely. It does not affect the
> 
> Spectral(Frequency) Resolution of the resulting FFT since the added zeros
> 
> don't matter in the FFT computation. This however, does change the Visual
> 
> Resolution (have 'data points' between the original bins) and for a plot in
> 
> Matlab for e.g, I can move (read off) between two DFT bins. (Ofcourse the
> 
> plot is Matlab is a linear interpolation of the data points).
> 
> 
> 
> I wanted to know if my understanding is correct. If so then do we say that
> 
> the DFT resolution has increased by zero padding the signal? 
> 
> Shouldn't the DFT resolution mean the frequency resolution?
> 
> 
> 
> Thanks.

You should get two answers. The first is that zero-padding simply implements an interpolation, according to some assumption of how the spectrum changes between data points. The second is more nuanced and depends on the application. For example in NMR spectroscopy (the basis for MRI scans), Ernst showed that zero-padding up to doubling the number of data points was justifiable in terms of genuine increase in spectral resolution - see E Bartholi and RR Ernst, Journal of Magnetic Resonance 11, 9 (1973).

The idea that zero-padding can effectively 'add information' by increasing resolution is disputed: however the DFT itself does not 'add information' it simply transforms it - the argument for NMR (simplified) is that all the information is in the original samples but that the DFT discards half that information. (Better not to take this talk of 'information' too pedantically). The basic idea, as I have always understood it, is that interpolation by zero-padding interpolates frequency spectrum samples that are derived from an assumption about the spectrum - in cases such as NMR we deal with 'spectral lines' - that is spectra where the predominant shape is quite narrow lines that have a shape (and whose shape is important in showing the chemistry) - and the characteristics of the spectrum are such, under certain conditions, that the zero-padding does increase resilution. To see details you need to read his paper and some others on NMR.

I know this point of view will be controversial, but RR Ernst was awarded the Nobel prize for his application of the Fourier Transform to NMR spectroscopy so his analysis is at least worth considering.

>Hello,
>
>I have a confusion regarding FFTs, zero padding and DFT bins. This is my
>understanding, I wanted to know if it is correct since this is what I
>understand from books but my tutor says otherwise.
>
>
>Zero padding the signal in the Time domain and computing its FFT results
in
>the frequency spectrum being sampled more densely. It does not affect the
>Spectral(Frequency) Resolution of the resulting FFT since the added zeros
>don't matter in the FFT computation. This however, does change the Visual
>Resolution (have 'data points' between the original bins) and for a plot
in
>Matlab for e.g, I can move (read off) between two DFT bins. (Ofcourse the
>plot is Matlab is a linear interpolation of the data points).
>
>I wanted to know if my understanding is correct. If so then do we say
that
>the DFT resolution has increased by zero padding the signal? 
>Shouldn't the DFT resolution mean the frequency resolution?
>
>Thanks.
>
>

I prefer to get fft without any zero padding. Zero padding adds a sudden
discontinuity to the signal implying some high frequencies. The zero
section itself does not add any power but the transition to zero does.

Kadhiem

>>Hello,
>>
>>I have a confusion regarding FFTs, zero padding and DFT bins. This is my
>>understanding, I wanted to know if it is correct since this is what I
>>understand from books but my tutor says otherwise.
>>
>>
>>Zero padding the signal in the Time domain and computing its FFT results
>in
>>the frequency spectrum being sampled more densely. It does not affect
the
>>Spectral(Frequency) Resolution of the resulting FFT since the added
zeros
>>don't matter in the FFT computation. This however, does change the
Visual
>>Resolution (have 'data points' between the original bins) and for a plot
>in
>>Matlab for e.g, I can move (read off) between two DFT bins. (Ofcourse
the
>>plot is Matlab is a linear interpolation of the data points).
>>
>>I wanted to know if my understanding is correct. If so then do we say
>that
>>the DFT resolution has increased by zero padding the signal? 
>>Shouldn't the DFT resolution mean the frequency resolution?
>>
>>Thanks.
>>
>>
>
>I prefer to get fft without any zero padding. Zero padding adds a sudden
>discontinuity to the signal implying some high frequencies. The zero
>section itself does not add any power but the transition to zero does.
>
>Kadhiem
>
>

adding to my previous post:

Any direct fft implies discontinuities at both ends of signal and this adds
false high frequencies unless a window is used. I can view zero padding in
this sense as making no difference, one can imagine the added zeros wrapped
up to both ends and so becomes equivalent to original discontuity.
Thus in either case it is the windowing that can remove effect of sudden
transitions.

Kadhiem

Chris Bore <chris.bore@gmail.com> wrote:

(snip, someone wrote)
>> I have a confusion regarding FFTs, zero padding and DFT bins. This is my
>> understanding, I wanted to know if it is correct since this is what I
>> understand from books but my tutor says otherwise.

(snip)

> You should get two answers. The first is that zero-padding simply 
> implements an interpolation, according to some assumption of how the 
> spectrum changes between data points. The second is more nuanced and 
> depends on the application. For example in NMR spectroscopy 
> (the basis for MRI scans), Ernst showed that zero-padding up to 
> doubling the number of data points was justifiable in terms of 
> genuine increase in spectral resolution - see E Bartholi and RR 
> Ernst, Journal of Magnetic Resonance 11, 9 (1973).

I have previously mentioned the book "Deconvolution of Images
and Spectra" by Jansson:

http://www.amazon.com/gp/product/0486453251/

It is now on Dover paperback, and more affordable than the hardback
when it was in print. (And especially the hardback now, where
there are scalpers trying to sell them.)

Unlike much of DSP, spectroscopy is done with intensity 
(usually called power in DSP). That is, the phase information
has been lost. The book deals with non-linear deconvolution,
where the fact that intensity can't be negative is used.

As I remember, there are cases in infra-red spectroscopy (far IR,
from the vibrational modes of molecules) where the signal/noise
is nonlinear such that using larger slits and deconvolution gives
better results than the more obvious narrow slits. 

The "spectral change" mentioned above often comes when two
peaks are near each other. That is, can you tell two small
peaks from one larger peak?

> The idea that zero-padding can effectively 'add information' by 
> increasing resolution is disputed: however the DFT itself does not 
> 'add information' it simply transforms it - the argument for NMR 
> (simplified) is that all the information is in the original 
> samples but that the DFT discards half that information. 
> (Better not to take this talk of 'information' too pedantically). 

Without reading the paper, I suspect it is the lost phase information
that is being discussed. But FFT is linear. The non-linear
transformations used in the book can extract even more information.

> The basic idea, as I have always understood it, is that interpolation 
> by zero-padding interpolates frequency spectrum samples that are 
> derived from an assumption about the spectrum - in cases such as NMR 
> we deal with 'spectral lines' - that is spectra where the predominant 
> shape is quite narrow lines that have a shape (and whose shape is 
> important in showing the chemistry) - and the characteristics of 
> the spectrum are such, under certain conditions, that the 
> zero-padding does increase resilution. 

-- glen

kaz <37480@dsprelated> wrote:

(snip)

> I prefer to get fft without any zero padding. Zero padding adds a sudden
> discontinuity to the signal implying some high frequencies. The zero
> section itself does not add any power but the transition to zero does.

Yes, that is a separate question.

Consider the case for data that goes smoothly to zero at both ends,
and so no discontinuity (or discontinuous low derivatives).

-- glen

>On Tuesday, 19 February 2013 19:35:53 UTC, wond3rboy  wrote:
>> Hello,
>>=20
>>=20
>>=20
>> I have a confusion regarding FFTs, zero padding and DFT bins. This is
my
>>=20
>> understanding, I wanted to know if it is correct since this is what I
>>=20
>> understand from books but my tutor says otherwise.
>>=20
>>=20
>>=20
>>=20
>>=20
>> Zero padding the signal in the Time domain and computing its FFT results
=
>in
>>=20
>> the frequency spectrum being sampled more densely. It does not affect
the
>>=20
>> Spectral(Frequency) Resolution of the resulting FFT since the added
zeros
>>=20
>> don't matter in the FFT computation. This however, does change the
Visual
>>=20
>> Resolution (have 'data points' between the original bins) and for a plot
=
>in
>>=20
>> Matlab for e.g, I can move (read off) between two DFT bins. (Ofcourse
the
>>=20
>> plot is Matlab is a linear interpolation of the data points).
>>=20
>>=20
>>=20
>> I wanted to know if my understanding is correct. If so then do we say
tha=
>t
>>=20
>> the DFT resolution has increased by zero padding the signal?=20
>>=20
>> Shouldn't the DFT resolution mean the frequency resolution?
>>=20
>>=20
>>=20
>> Thanks.
>
>You should get two answers. The first is that zero-padding simply
implement=
>s an interpolation, according to some assumption of how the spectrum
change=
>s between data points. The second is more nuanced and depends on the
applic=
>ation. For example in NMR spectroscopy (the basis for MRI scans), Ernst
sho=
>wed that zero-padding up to doubling the number of data points was
justifia=
>ble in terms of genuine increase in spectral resolution - see E Bartholi
an=
>d RR Ernst, Journal of Magnetic Resonance 11, 9 (1973).
>
>The idea that zero-padding can effectively 'add information' by increasing
=
>resolution is disputed: however the DFT itself does not 'add information'
i=
>t simply transforms it - the argument for NMR (simplified) is that all the
=
>information is in the original samples but that the DFT discards half that
=
>information. (Better not to take this talk of 'information' too
pedanticall=
>y). The basic idea, as I have always understood it, is that interpolation
b=
>y zero-padding interpolates frequency spectrum samples that are derived
fro=
>m an assumption about the spectrum - in cases such as NMR we deal with
'spe=
>ctral lines' - that is spectra where the predominant shape is quite narrow
=
>lines that have a shape (and whose shape is important in showing the
chemis=
>try) - and the characteristics of the spectrum are such, under certain
cond=
>itions, that the zero-padding does increase resilution. To see details you
=
>need to read his paper and some others on NMR.
>
>I know this point of view will be controversial, but RR Ernst was awarded
t=
>he Nobel prize for his application of the Fourier Transform to NMR
spectros=
>copy so his analysis is at least worth considering.
>


Thank you both for replying to the post, really helped clear my confusion.

"kaz" <37480@dsprelated> wrote:

> I prefer to get fft without any zero padding.

You are idiot.

> Zero padding adds a sudden
> discontinuity to the signal implying some high frequencies.
.
With or without zero padding, discontinuity is still there.

VLV
 

On Tuesday, 19 February 2013 20:55:05 UTC, glen herrmannsfeldt  wrote:
> Chris Bore <chris.bore@gmail.com> wrote:
> 
> 
> 
> (snip, someone wrote)
> 
> >> I have a confusion regarding FFTs, zero padding and DFT bins. This is my
> 
> >> understanding, I wanted to know if it is correct since this is what I
> 
> >> understand from books but my tutor says otherwise.
> 
> 
> 
> (snip)
> 
> 
> 
> > You should get two answers. The first is that zero-padding simply 
> 
> > implements an interpolation, according to some assumption of how the 
> 
> > spectrum changes between data points. The second is more nuanced and 
> 
> > depends on the application. For example in NMR spectroscopy 
> 
> > (the basis for MRI scans), Ernst showed that zero-padding up to 
> 
> > doubling the number of data points was justifiable in terms of 
> 
> > genuine increase in spectral resolution - see E Bartholi and RR 
> 
> > Ernst, Journal of Magnetic Resonance 11, 9 (1973).
> 
> 
> 
> I have previously mentioned the book "Deconvolution of Images
> 
> and Spectra" by Jansson:
> 
> 
> 
> http://www.amazon.com/gp/product/0486453251/
> 
> 
> 
> It is now on Dover paperback, and more affordable than the hardback
> 
> when it was in print. (And especially the hardback now, where
> 
> there are scalpers trying to sell them.)
> 
> 
> 
> Unlike much of DSP, spectroscopy is done with intensity 
> 
> (usually called power in DSP). That is, the phase information
> 
> has been lost. The book deals with non-linear deconvolution,
> 
> where the fact that intensity can't be negative is used.

When I was doing it, in the early 1970s when Ernst's work was also done, we used quadrature RF detection so the signal was inherently complex and phase was preserved. The paper I quoted does not base its argument son the loss of phase. However my work was in the early development of MRI (imaging, then called 'zeugmatography') and so I only looked into the spectroscopy issues as background to that. Zero padding, even though Ernst recommended it, was even then not universally accepted and my own view was that it came down to interpolation based on assumptions.


> 
> 
> 
> As I remember, there are cases in infra-red spectroscopy (far IR,
> 
> from the vibrational modes of molecules) where the signal/noise
> 
> is nonlinear such that using larger slits and deconvolution gives
> 
> better results than the more obvious narrow slits. 
> 
> 
> 
> The "spectral change" mentioned above often comes when two
> 
> peaks are near each other. That is, can you tell two small
> 
> peaks from one larger peak?
> 
> 
> 
> > The idea that zero-padding can effectively 'add information' by 
> 
> > increasing resolution is disputed: however the DFT itself does not 
> 
> > 'add information' it simply transforms it - the argument for NMR 
> 
> > (simplified) is that all the information is in the original 
> 
> > samples but that the DFT discards half that information. 
> 
> > (Better not to take this talk of 'information' too pedantically). 
> 
> 
> 
> Without reading the paper, I suspect it is the lost phase information
> 
> that is being discussed. But FFT is linear. The non-linear
> 
> transformations used in the book can extract even more information.
> 
> 
> 
> > The basic idea, as I have always understood it, is that interpolation 
> 
> > by zero-padding interpolates frequency spectrum samples that are 
> 
> > derived from an assumption about the spectrum - in cases such as NMR 
> 
> > we deal with 'spectral lines' - that is spectra where the predominant 
> 
> > shape is quite narrow lines that have a shape (and whose shape is 
> 
> > important in showing the chemistry) - and the characteristics of 
> 
> > the spectrum are such, under certain conditions, that the 
> 
> > zero-padding does increase resilution. 
> 
> 
> 
> -- glen