FFT's

Hey all:

I'm a newbie here, and have a FFT related question.  Some background 
first.

I've written a VB program that takes an FFT of a time function 
comprised of fixed pulse width impulses.  The timing of the impulses 
vary from pulse to pulse in a predetermined arrangement, and there 
are only two type of impulses, call them Pulse A and Pulse B

Now if I arrange these pulses like this:   

A B A A A A B B A A 

and do an FFT, I get result #1.  Now, I shift the pulses in time 
without changing the relationships to get:

A A A B A A A A B B

and get an FFT result #2.  I'm thinking that result #1 and result #2 
should be identical.  Problem is, in my program, they're not.

I'm not using any windowing in the FFT (OK i'm using rectangular 
weighting) , since the arrangement does contain 1 cycle of 
information. 

So, given this information, can anyone help me out as to where I need 
to start looking to check for errors?

Thanks

John
	

From: "John Skurka" <jskurka@jsku...>

> Now if I arrange these pulses like this:
>
> A B A A A A B B A A
>
> and do an FFT, I get result #1.  Now, I shift the pulses in
time
> without changing the relationships to get:
>
> A A A B A A A A B B
>
> and get an FFT result #2.  I'm thinking that result #1 and
result
> #2 should be identical.  Problem is, in my
program, they're
not.

They should be equivalent up to a constant phase difference
corresponding to two times the duration of A.
	

>They should be equivalent up to a constant phase
difference  
>corresponding to two times the duration of A.  
>  

OK, well could you further explain your statement "constant phase
difference corresponding to two times the duration of A".  I'm not
sure I understand. 

Let me also try to draw the impulses, a & B:

       -----
       |   |
       |   |
       |   |
       |   |
A = ---|   |-----
	    -----
    |   |
    |   |
B = |   |--------

Both pulse widths are of the same duration, but A is of a higher aplitude.  The
total time of each pulse is also the same.

So, since my routine does not give the same results for the pattern change, can
anyone tell me where to start looking as to why the results are different?

John
	

From: <jskurka@jsku...>

> OK, well could you further explain your statement
"constant
> phase difference corresponding to two times the duration of A".

Sorry -- I shot from the hip and missed. What I said is only true
when your sequence length and FFT size are equal. Otherwise,
there is no pointwise relation between the two spectra. Let us
look closer at those two cases.
	Let # denote linear convolution, delta[n] = {1, n=0;  0, else},
and call the duration of a pulse in samples d. Here are your
example pulse arrangements, labeled:

    x = (A B A A A A B B A A)
    y = (A A A B A A A A B B)

So x[n] and y[n] are finite signals of length 10 * d. Form two
infinite-length signals u, v by repeating x and y, respectively,
in both directions. As u and v are periodic we can write them as
Fourier series with coefficients U[k], V[k]. Note that U is
precisely the 10*d-point DFT of x, and V is the 10*d-point DFT
of y.

Now observe that since y is a rotation of x, then its periodic
extension v is a shifted version of u -- specifically,

    v[n] = u[n - 2*d]
         = u[n] # delta[n - 2*d].

Finding the Fourier series coefficients of both sides gives

    V[k] = U[k] * exp(j * phi * k),

where phi is a constant you can easily find by writing down the
10*d-point DFT sum over delta[n - 2*d], which has a single
nonzero term. That number phi I referred to as "constant phase
difference" between U and V.
	There are fast DFT algorithms for arbitrary sizes; FFTW
implements those, for instance. But it has now occurred to me
that you probably use a power-of-two size. To explain that case I
presume you extend x and y with zeros before transforming. That
is the same as applying a boxcar window w[n] to u and v, so we
have

    x[n] = u[n] * w[n]
    y[n] = u[n - 2*d] * w[n]
         = (u[n] # delta[n - 2*d]) * w[n],

and after FFT'ing

    X[k] = U'[k] # W[k]
    Y[k] = (U'[k] * exp(j*phi*k)) # W[k].

This is different from the first case because we cannot pull the
exponential out of the convolution in the last equation; i.e., we
cannot put things into the form Y[k] = X[k] * some_function(k).

There are two notational side issues with that last bit. First,
U' is the FFT of some sufficiently long chunk of u -- it is not
generally the same as U since different-length transforms
assign different frequencies to the same index. Second, if you
were to write out the last two convolutions you would have to
take indices modulo the FFT size, for the FFT spectra are
actually finite but notionally periodic. (Incidentally, I could
have used circular convolution throughout and do away with
u and v but I think that would have provided less intuition.)
	> So, since my routine does not give the same results for the
> pattern change, can anyone tell me where to start
looking
> as to why the results are different?

Forgetting about the nitty-gritty, the DFT is a bijective map on
sequences. Different inputs yield different outputs.
	

John, I presume you meant to send this to the list?

> > Forgetting about the nitty-gritty, the DFT is
a bijective map
> > on sequences. Different inputs yield different outputs.
>
> But, if in reality, the two ends of the above sequences are
> connected together (such as a pattern in a tire lug sequence)
> then by rights, they should be identical.

Should sin(t) and sin(t+p) then have identical transforms too?

> Now for a second question.  If the sequences are
reversed,
> should the FFT results be the same as well?

Because of linearity, you can look at each of the sinusoids
making up the sequence individually. The cosines do not change
and the sines flip signs under time reversion, i.e., the
transforms of forward and reverse sequence are hermitian
symmetric.
	From: "John Skurka" <jskurka@jsku...>

> > Forgetting about the nitty-gritty, the DFT is
a bijective map
> > on sequences. Different inputs yield different outputs.
>
> But, if in reality, the two ends of the above sequences are
> connected together (such as a pattern in a tire lug sequence)
> then by rights, they should be identical.
>
> Now for a second question.  If the sequences are reversed,
> should the FFT results be the same as well?  As an example
> of what I mean, take the 1st 10 seconds of song and perform
> an FFT vs. time plot.  Now take and record the song
> backwards and do the same analysis.  Will the plots
> look the same or not?
>
> Thanks for everyone's help.
>
> John