Zero padding and the Shannon information content

Hello all,

I am confused about how zero-filling / windowing a signal alters its
information content and I'm hoping someone here can help.

I have a continuous signal (time domain) and I Fourier transform it to
get a band-limited spectrum (frequency domain).  From Shannon &
Weaver, I can compute the information content of the time domain
signal from the signal variance and, given the linearity of a DFT, I
expect the information content of the frequency domain signal is the
same.

The DFT code that I have has the option of zero-filling/zero-padding
the original signal as a means of interpolating in the frequency
domain.  This doesn't change the location/frequency of the peaks in
the spectrum but does make it easier to accurately locate the maximum
of each peak.  So, does zero-filling/zero-padding change the
information content of the signal?

Many thanks,
Dave

"Dave" <Confused.Scientist@gmail.com> writes:

> Hello all,
>
> I am confused about how zero-filling / windowing a signal alters its
> information content and I'm hoping someone here can help.
>
> I have a continuous signal (time domain) and I Fourier transform it to
> get a band-limited spectrum (frequency domain).  From Shannon &
> Weaver, I can compute the information content of the time domain
> signal from the signal variance and, given the linearity of a DFT, I
> expect the information content of the frequency domain signal is the
> same.
>
> The DFT code that I have has the option of zero-filling/zero-padding
> the original signal as a means of interpolating in the frequency
> domain.  This doesn't change the location/frequency of the peaks in
> the spectrum but does make it easier to accurately locate the maximum
> of each peak.  So, does zero-filling/zero-padding change the
> information content of the signal?

Intuitively, no. How to show analytically? Perhaps you could use the
Data Processing theorem?
-- 
%  Randy Yates                  % "Maybe one day I'll feel her cold embrace,
%% Fuquay-Varina, NC            %                    and kiss her interface, 
%%% 919-577-9882                %            til then, I'll leave her alone."
%%%% <yates@ieee.org>           %        'Yours Truly, 2095', *Time*, ELO   
http://home.earthlink.net/~yatescr

> > So, does zero-filling/zero-padding change the
> > information content of the signal?
>
> Intuitively, no. How to show analytically? Perhaps you could use the
> Data Processing theorem?

Indeed! intuitively, I expect the information content after zero
padding to be the same, but I'm at a total loss as to how to prove
it.  To me, the data processing theorem suggests the opposite as the
act of interpolating has altered the signal and hence, destroyed the
original information.  I suspect that in the early days of information
theory someone worked out an analytic proof showing that tapering/
windowing and interpolation does not change the information content of
a signal.

On Mar 16, 10:00 am, "Dave" <Confused.Scient...@gmail.com> wrote:
> > > So, does zero-filling/zero-padding change the
> > > information content of the signal?
>
> > Intuitively, no. How to show analytically? Perhaps you could use the
> > Data Processing theorem?
>
> Indeed! intuitively, I expect the information content after zero
> padding to be the same, but I'm at a total loss as to how to prove
> it.  To me, the data processing theorem suggests the opposite as the
> act of interpolating has altered the signal and hence, destroyed the
> original information.  I suspect that in the early days of information
> theory someone worked out an analytic proof showing that tapering/
> windowing and interpolation does not change the information content of
> a signal.

I should add that I'm only interested in linear systems and the signal
noise is a Gaussian process model.  The FFT is a linear transformation
of the original signal and by virtue of its inverse (i.e. the IFFT
transform) it does not add/destroy information.  This suggests that
any linear and invertible transformation does not change the
information content of a signal.

Can anyone recommend a good book on signal processing that considers
the information content of the input/output of each process?

Dave wrote:
>>> So, does zero-filling/zero-padding change the
>>> information content of the signal?
>> Intuitively, no. How to show analytically? Perhaps you could use the
>> Data Processing theorem?
> 
> Indeed! intuitively, I expect the information content after zero
> padding to be the same, but I'm at a total loss as to how to prove
> it.  To me, the data processing theorem suggests the opposite as the
> act of interpolating has altered the signal and hence, destroyed the
> original information.  I suspect that in the early days of information
> theory someone worked out an analytic proof showing that tapering/
> windowing and interpolation does not change the information content of
> a signal.

How does interpolating destroy original information? Zero padding adds 
no new information, but if you can tell the added zeros from original 
data, it removes or subtracts nothing either.

What would you consider an analytic proof? Do encrypted and clear 
versions of the same message carry the same information?

Jerry
-- 
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

Dave wrote:
> On Mar 16, 10:00 am, "Dave" <Confused.Scient...@gmail.com> wrote:
>>>> So, does zero-filling/zero-padding change the
>>>> information content of the signal?
>>> Intuitively, no. How to show analytically? Perhaps you could use the
>>> Data Processing theorem?
>> Indeed! intuitively, I expect the information content after zero
>> padding to be the same, but I'm at a total loss as to how to prove
>> it.  To me, the data processing theorem suggests the opposite as the
>> act of interpolating has altered the signal and hence, destroyed the
>> original information.  I suspect that in the early days of information
>> theory someone worked out an analytic proof showing that tapering/
>> windowing and interpolation does not change the information content of
>> a signal.
> 
> I should add that I'm only interested in linear systems and the signal
> noise is a Gaussian process model.  The FFT is a linear transformation
> of the original signal and by virtue of its inverse (i.e. the IFFT
> transform) it does not add/destroy information.  This suggests that
> any linear and invertible transformation does not change the
> information content of a signal.
> 
> Can anyone recommend a good book on signal processing that considers
> the information content of the input/output of each process?

Any entry-level book on signal processing will discuss the properties of 
direct and inverse Fourier transforms in enough depth to resolve the 
issues you raise. Like many here, I like Lyons: "Understanding Digital 
Signal Processing". Smith's "The Scientist and Engineer's Guide to 
Digital Signal Processing" is on line at http://www.dspguide.com/. There 
may be material for you in Chapter 8 http://www.dspguide.com/ch8.htm .

Zero padding has profound implications processing, aside from the 
obvious interpolation that makes curves easier to read. DFTs come 
conceptually from periodic signals, and the math behaves as if it is 
dealing with complete period(s). Artifacts occur when that's not the 
case; windowing helps to suppress those at some cost. The inherent 
periodicity of the math can cause an overlap of the beginning and end 
data, confusing the result often to the point of uselessness. Zero 
padding can render the overlap harmless; think of it as a guard band for 
the real data. The sequence FFT - Multiply by a mask - IFFT achieves 
convolution, often more quickly than classical convolution. Usually, 
linear convolution is wanted. Without a sufficient zero-padded guard 
band, circular convolution results. http://www.dspguide.com/ch7.htm

Jerry
-- 
Engineering is the art of making what you want from things you can get.
&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;

On Mar 16, 1:23 pm, Jerry Avins <j...@ieee.org> wrote:
> Dave wrote:
> >>> So, does zero-filling/zero-padding change the
> >>> information content of the signal?
> >> Intuitively, no. How to show analytically? Perhaps you could use the
> >> Data Processing theorem?
>
> > Indeed! intuitively, I expect the information content after zero
> > padding to be the same, but I'm at a total loss as to how to prove
> > it.  To me, the data processing theorem suggests the opposite as the
> > act of interpolating has altered the signal and hence, destroyed the
> > original information.  I suspect that in the early days of information
> > theory someone worked out an analytic proof showing that tapering/
> > windowing and interpolation does not change the information content of
> > a signal.
>
> How does interpolating destroy original information? Zero padding adds
> no new information, but if you can tell the added zeros from original
> data, it removes or subtracts nothing either.

Sigh, I should have re-read that before posting it.  What I intended
to write is that interpolation should not destroy any information but
it may (superficially at least) appear to increase it.  I was thinking
about the data processing theorem which states that the system's
output can not contain more information than present in its input.  A
Fourier transform recasts the input onto a different basis but it
doesn't alter the information content.  After a little more thought, I
think that zero-filling/interpolating/windowing are all methods that
result in signal enhancement.  In the case of zero-padding, the
increase in information content is observed as an improved
representation of each spectra line.

> What would you consider an analytic proof?

Ideally, I'd like to show is that the information content of a signal,
H(s), is equal to or less than the information content of a zero-
padded signal, H(s'), or a windowed signal, H(s'').  In practice, I
think it may be easier to show this with a matlab simulation.

Thanks,
Dave

On Mar 16, 11:26 am, "Dave" <Confused.Scient...@gmail.com> wrote:
> On Mar 16, 1:23 pm, Jerry Avins <j...@ieee.org> wrote:...
...
>   I was thinking
> about the data processing theorem which states that the system's
> output can not contain more information than present in its input.  A
> Fourier transform recasts the input onto a different basis but it
> doesn't alter the information content.  After a little more thought, I
> think that zero-filling/interpolating/windowing are all methods that
> result in signal enhancement.  In the case of zero-padding, the
> increase in information content is observed as an improved
> representation of each spectra line.
>
> Dave

A zero-padded (Discrete) Fourier transform casts the input onto a
larger set of different bases but it doesn't alter the information
content. The new bases are not independent and do not contain any new
information. The larger set of bases allows a more accurate estimation
of the peak by a peak picking process. The 'improved representation'
is only a matter finding a better estimate of a different basis:
frequency peaks with amplitudes, than the set that the non-extended
DFT provides by peak picking. A variety of interpolation methods allow
the same 'improved representation' to be determined.

I use quotes around 'improved representation' because it is 'improved'
for a specific purpose that is not an information content criteria but
a parameter estimation criteria.

Dale B. Dalrymple
http://dbdimages.com

On Mar 15, 11:06 pm, "Dave" <Confused.Scient...@gmail.com> wrote:
[snip]
> of each peak.  So, does zero-filling/zero-padding change the
> information content of the signal?
>
> Many thanks,
> Dave

No.  I think you're confusing "information content" and
"convenience of representation."

It's like when you receive a noisy version of a PAM signal.
Quantizing it makes it look nicer and many people then say
that it has more information content, but it's the raw
data that carries the most information about your transmitted
bits.

Hope that helps a bit,
Julius

On Mar 16, 2:26 pm, "Dave" <Confused.Scient...@gmail.com> wrote:
> On Mar 16, 1:23 pm, Jerry Avins <j...@ieee.org> wrote:
>
>
>
> > Dave wrote:
> > >>> So, does zero-filling/zero-padding change the
> > >>> information content of the signal?
> > >> Intuitively, no. How to show analytically? Perhaps you could use the
> > >> Data Processing theorem?
>
> > > Indeed! intuitively, I expect the information content after zero
> > > padding to be the same, but I'm at a total loss as to how to prove
> > > it.  To me, the data processing theorem suggests the opposite as the
> > > act of interpolating has altered the signal and hence, destroyed the
> > > original information.  I suspect that in the early days of information
> > > theory someone worked out an analytic proof showing that tapering/
> > > windowing and interpolation does not change the information content of
> > > a signal.
>
> > How does interpolating destroy original information? Zero padding adds
> > no new information, but if you can tell the added zeros from original
> > data, it removes or subtracts nothing either.
>
> Sigh, I should have re-read that before posting it.  What I intended
> to write is that interpolation should not destroy any information but
> it may (superficially at least) appear to increase it.  I was thinking
> about the data processing theorem which states that the system's
> output can not contain more information than present in its input.  A
> Fourier transform recasts the input onto a different basis but it
> doesn't alter the information content.  After a little more thought, I
> think that zero-filling/interpolating/windowing are all methods that
> result in signal enhancement.  In the case of zero-padding, the
> increase in information content is observed as an improved
> representation of each spectra line.
>
> > What would you consider an analytic proof?
>
> Ideally, I'd like to show is that the information content of a signal,
> H(s), is equal to or less than the information content of a zero-
> padded signal, H(s'), or a windowed signal, H(s'').  In practice, I
> think it may be easier to show this with a matlab simulation.
>
> Thanks,
> Dave

Your intuition seems to be at odds with what you said previously. You
had (correctly, I believe) pointed out that since the FFT has an
inverse that can be used to exactly reconstruct the FFT's input, the
FFT operation doesn't add or destroy any information content. The same
can be said about zero-padding or bandlimited interpolation. Both have
exact inverse operations that yield the original signal, so they can't
possibly change the information content.

Jason