normalization for fft when zero padding the original signal.

Hi all,

I posted up  the question in an earlier post but have not received a
clear answer yet. I would like to re-post my question in this
separated post. Please help.


Normally, to normalize a signal  s[n] with length N such that a real
sinusoid signal x[n] with the same length N and amplitude of 1 will
yield an FFT magnitude of unity, we simply divide the obtained FFT
spectrum S[k] by N/2 (with assumption that the sinusoid x[n] is
perfectly periodic in N).

Now I want to zero pad the signal s[n] to length M (M>N and desired to
be a power of 2 or a highly composite number), to get the goal : the
sinusoid x[n] with amplitude of 1 yields an FFT magnitude of 1, can I
again divide the FFT  S[k] by N/2?
I know this means I am normalizing S[k] such that a sinusoid with
amplitude of 1 and length N which is perfectly periodic both in N and,
if not windowed, will perfectly periodic in new length M , will yield
an FFT magnitude of 1 after zero padded. Is that the way people do
when normalizing the FFT of  zero-padded signals?

I guess somebody can argue that there are not many sinusoids that are
perfectly periodic both in N and M. So I am thinking of an
alternative  way: I will divide the FFT of the zero padded signal by a
scale number A.  the scale A  would be the maximum FFT magnitude I
obtained by Fourier transforming a zero-padded sinusoid ( amplitude of
1, original length N, perfectly periodic in N, length after zero
padded  M, not necessary to be perfectly periodic in M). Do you think
this way will work?

If you have any idea or propose another way, please tell me.  Thank
you for your help.

Regards,

Aelover

On Nov 24, 8:58 am, "A.E lover" <aelove...@gmail.com> wrote:
> Hi all,
>
> I posted up  the question in an earlier post but have not received a
> clear answer yet. I would like to re-post my question in this
> separated post. Please help.
>
> Normally, to normalize a signal  s[n] with length N such that a real
> sinusoid signal x[n] with the same length N and amplitude of 1 will
> yield an FFT magnitude of unity, we simply divide the obtained FFT
> spectrum S[k] by N/2 (with assumption that the sinusoid x[n] is
> perfectly periodic in N).
>
> Now I want to zero pad the signal s[n] to length M (M>N and desired to
> be a power of 2 or a highly composite number), to get the goal : the
> sinusoid x[n] with amplitude of 1 yields an FFT magnitude of 1, can I
> again divide the FFT  S[k] by N/2?
> I know this means I am normalizing S[k] such that a sinusoid with
> amplitude of 1 and length N which is perfectly periodic both in N and,
> if not windowed, will perfectly periodic in new length M , will yield
> an FFT magnitude of 1 after zero padded. Is that the way people do
> when normalizing the FFT of  zero-padded signals?
>
> I guess somebody can argue that there are not many sinusoids that are
> perfectly periodic both in N and M. So I am thinking of an
> alternative  way: I will divide the FFT of the zero padded signal by a
> scale number A.  the scale A  would be the maximum FFT magnitude I
> obtained by Fourier transforming a zero-padded sinusoid ( amplitude of
> 1, original length N, perfectly periodic in N, length after zero
> padded  M, not necessary to be perfectly periodic in M). Do you think
> this way will work?

If the sinusoid of amplitude 1 is not also periodic in M,
then its energy will be spread by an FFT of length M into
multiple bins, and the total energy may depend on the
phase of the sinusoid with respect to the center of the
M width aperture.  If you interpolate the maxima between
resulting FFT bins, you might get somewhere near N/2
anyway, but no single bin will have that magnitude by
itself.



IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M

On Sat, 24 Nov 2007 08:58:05 -0800 (PST), "A.E lover"
<aelover11@gmail.com> wrote:

>I guess somebody can argue that there are not many sinusoids that are
>perfectly periodic both in N and M. 

...

>If you have any idea or propose another way, please tell me.  Thank
>you for your help.

If I'm interpreting your intent correctly, a search for "flat top
window" should give you what you need.

Greg

hi Ron:

Yes, what you said is true and I knew it. That is why I said to divide
FFT by N/2 we need the sinusoid to be perfectly periodic in both N and
M.
And what I really want to know is that in your opinion which way
should I do to normalize FFT to meet my requirement? : still divide
the  FFT of the zero- padded signal by N/2 or use the alternative way
( divide by a scale A equal to max FFT of the zero padded sinusoid)
which I said in my first post of this topic? Which one do you prefer?

Thanks


>
> If the sinusoid of amplitude 1 is not also periodic in M,
> then its energy will be spread by an FFT of length M into
> multiple bins, and the total energy may depend on the
> phase of the sinusoid with respect to the center of the
> M width aperture.  If you interpolate the maxima between
> resulting FFT bins, you might get somewhere near N/2
> anyway, but no single bin will have that magnitude by
> itself.
>
> IMHO. YMMV.
> --
> rhn A.T nicholson d.0.t C-o-M- Hide quoted text -
>
> - Show quoted text -

On Nov 24, 5:04 pm, Greg Berchin <gberc...@comicast.net> wrote:
> On Sat, 24 Nov 2007 08:58:05 -0800 (PST), "A.E lover"
>
> <aelove...@gmail.com> wrote:
> >I guess somebody can argue that there are not many sinusoids that are
> >perfectly periodic both in N and M.
>
> ...
>
> >If you have any idea or propose another way, please tell me.  Thank
> >you for your help.
>
> If I'm interpreting your intent correctly, a search for "flat top
> window" should give you what you need.
>
> Greg

Hi Greg, can you say something more: which one did you interpret? and
why " flat top window"? Thanks

On Sat, 24 Nov 2007 15:23:59 -0800 (PST), "A.E lover"
<aelover11@gmail.com> wrote:

>Hi Greg, can you say something more: which one did you interpret? and
>why " flat top window"? Thanks

My interpretation is that you want the FFT bin closest to the actual
frequency of your sinusoidal input signal to have magnitude equal to the
amplitude of the input signal, even when the input frequency falls
somewhere (anywhere) in-between FFT bins, whether the FFT is zeropadded
or not.  Flat top windows are designed to make the magnitude equal (to
within some tolerance) in all FFT bins within &#4294967295;&#4294967295; bin of the actual
signal frequency.  Having accomplished that magnitude equality, you'll
still have to play with the magnitude normalization, but I believe it
will then be dependent only upon the original number of points "N" and
not upon the zeropadded number of points "N+Z".

Greg

On Nov 24, 11:58 am, "A.E lover" <aelove...@gmail.com> wrote:
> Hi all,
>
> I posted up  the question in an earlier post but have not received a
> clear answer yet. I would like to re-post my question in this
> separated post. Please help.
>
> Normally, to normalize a signal  s[n] with length N such that a real
> sinusoid signal x[n] with the same length N and amplitude of 1 will
> yield an FFT magnitude of unity, we simply divide the obtained FFT
> spectrum S[k] by N/2 (with assumption that the sinusoid x[n] is
> perfectly periodic in N).
>
> Now I want to zero pad the signal s[n] to length M (M>N and desired to
> be a power of 2 or a highly composite number), to get the goal : the
> sinusoid x[n] with amplitude of 1 yields an FFT magnitude of 1, can I
> again divide the FFT  S[k] by N/2?
> I know this means I am normalizing S[k] such that a sinusoid with
> amplitude of 1 and length N which is perfectly periodic both in N and,
> if not windowed, will perfectly periodic in new length M , will yield
> an FFT magnitude of 1 after zero padded. Is that the way people do
> when normalizing the FFT of  zero-padded signals?
>

given the most common convention that puts the 1/N in the iDFT and
none of it in the DFT, yeah, i s'pose that's the case:

                 N-1
    X[k] =       SUM{ x[n] e^(-j*2*pi*n*k/N) }
                 n=0

with iDFT:
                 N-1
    x[n] = (1/N)*SUM{ X[k] e^(+j*2*pi*n*k/N) }
                 k=0


because when you zero pad the DFT summamtion that does not add terms,
there is no changed 1/N factor to worry about.  consider the other
convention:

DFT:
                 N-1
    X[k] = (1/N)*SUM{ x[n] e^(-j*2*pi*n*k/N) }
                 n=0

iDFT:
                 N-1
    x[n] =       SUM{ X[k] e^(+j*2*pi*n*k/N) }
                 k=0


now, in this case, no matter what N is, the amplitude of the kth bin
is the 1/2 the amplitude of the frequency component with frequency (k/
N)*Fs.

so if we zero pad M samples inside this N-lengthed DFT, i think you
could expect some gross reduction of amplitude by a factor of (N-M)/
N.  this would be the case if there is an integer number of cycles of
the sinusoid in N samples *and* in N-M samples.  i think you would
have to scale it up by N/(N-M), in this case.

but, using the convention where the 1/N factor is in the iDFT, then,
if you increased from N-M to N, you would decrease your 2/(N-M) factor
to 2/N, and in both cases, you are dividing by the unpadded number
samples.

> I guess somebody can argue that there are not many sinusoids that are
> perfectly periodic both in N and M. So I am thinking of an
> alternative  way: I will divide the FFT of the zero padded signal by a
> scale number A.  the scale A  would be the maximum FFT magnitude I
> obtained by Fourier transforming a zero-padded sinusoid ( amplitude of
> 1, original length N, perfectly periodic in N, length after zero
> padded  M, not necessary to be perfectly periodic in M). Do you think
> this way will work?
>
> If you have any idea or propose another way, please tell me.  Thank
> you for your help.

i don't understand the way you put it, but i hope the way i put it
made the issue clear.  given the most conventional definition (saying
"most conventional" is like saying "most unique" which is a malaprop,
i think), you divide by the number of samples that are not the pad.

r b-j

On 24 Nov, 17:58, "A.E lover" <aelove...@gmail.com> wrote:
> Hi all,
>
> I posted up  the question in an earlier post but have not received a
> clear answer yet. I would like to re-post my question in this
> separated post. Please help.
>
> Normally, to normalize a signal  s[n] with length N such that a real
> sinusoid signal x[n] with the same length N and amplitude of 1 will
> yield an FFT magnitude of unity, we simply divide the obtained FFT
> spectrum S[k] by N/2 (with assumption that the sinusoid x[n] is
> perfectly periodic in N).
>
> Now I want to zero pad the signal s[n] to length M (M>N and desired to
> be a power of 2 or a highly composite number), to get the goal : the
> sinusoid x[n] with amplitude of 1 yields an FFT magnitude of 1, can I
> again divide the FFT  S[k] by N/2?
> I know this means I am normalizing S[k] such that a sinusoid with
> amplitude of 1 and length N which is perfectly periodic both in N and,
> if not windowed, will perfectly periodic in new length M , will yield
> an FFT magnitude of 1 after zero padded. Is that the way people do
> when normalizing the FFT of  zero-padded signals?
>
> I guess somebody can argue that there are not many sinusoids that are
> perfectly periodic both in N and M. So I am thinking of an
> alternative  way: I will divide the FFT of the zero padded signal by a
> scale number A.  the scale A  would be the maximum FFT magnitude I
> obtained by Fourier transforming a zero-padded sinusoid ( amplitude of
> 1, original length N, perfectly periodic in N, length after zero
> padded  M, not necessary to be perfectly periodic in M). Do you think
> this way will work?
>
> If you have any idea or propose another way, please tell me.  Thank
> you for your help.
>
> Regards,
>
> Aelover

If you have access to matlab, try this:

%%%%%%%%%%%%%%%%%%%%%%%%%%%
N = 32;      % The number of samples in the time series
f1 = 4/32;   % A signal component exactly on a Fourier frequency...

tv = [0:N-1];
fv = [0:N-1]/N;

x1 = sin(2*pi*f1*tv);
X1= fft(x1);
X1zp = fft(x1,8*N);  % Compute and plot the zero-padded spectrum
                                % of signal 1
fvzp = [0:8*N-1]/(8*N);
plot(fv,abs(X1),'b+',fvzp,abs(X1zp),'g.')
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The reason for why it works has already been explained
by RBJ.

Rune

On Nov 24, 11:52 pm, robert bristow-johnson
<r...@audioimagination.com> wrote:
I use MATLAB and its FFT routine uses this convention, I guess.


>
>                  N-1
>     X[k] =       SUM{ x[n] e^(-j*2*pi*n*k/N) }
>                  n=0
>
> with iDFT:
>                  N-1
>     x[n] = (1/N)*SUM{ X[k] e^(+j*2*pi*n*k/N) }
>                  k=0
>




> but, using the convention where the 1/N factor is in the iDFT, then,
> if you increased from N-M to N, you would decrease your 2/(N-M) factor
> to 2/N, and in both cases, you are dividing by the unpadded number
> samples.
>

So do you mean that to normalize FFT in the case of zero padding, we
divide the FFT by N/2 ( N: length of signal after zero padded)?

Thanks

On Nov 28, 12:29 pm, "A.E lover" <aelove...@gmail.com> wrote:
> On Nov 24, 11:52 pm, robert bristow-johnson<r...@audioimagination.com> wrote:
>
> I use MATLAB and its FFT routine uses this convention, I guess.
>
>
>
> >                  N-1
> >     X[k] =       SUM{ x[n] e^(-j*2*pi*n*k/N) }
> >                  n=0
>
> > with iDFT:
> >                  N-1
> >     x[n] = (1/N)*SUM{ X[k] e^(+j*2*pi*n*k/N) }
> >                  k=0
>
> > but, using the convention where the 1/N factor is in the iDFT, then,
> > if you increased from N-M to N, you would decrease your 2/(N-M) factor
> > to 2/N, and in both cases, you are dividing by the unpadded number
> > samples.
>
> So do you mean that to normalize FFT in the case of zero padding, we
> divide the FFT by N/2 ( N: length of signal after zero padded)?

no, the length of the signal *before* padding (if you're using the
convention above, which is the most conventional convention).
remember "in both cases, you are dividing by the unpadded number [of]
samples."

r b-j