IFFT wrapping?

Hello All,

I did some very simple ifft of real valued vector representing
frequency domain samples ie. X[n]=[1 2 3 3 2]; imaginary part is 0 for
all samples, to my surprise recreated time domain signal is h[n]=[2.2
-0.52  -0.076 -0.076 -0.52].Those two last samples in h[n] look like
they are just symmetry around first sample. According to my knowledge
this should represent noncausal filter with symmetry around sample 0 -
zero imaginary part hence phase for all samples is 0. Why this
repetition of last two samples - shouldn't they be at the begining. Or
in the other words how to define filter that is symmetrical around
sample 0?

Kind regards

Pawel

Pawel wrote:
> Hello All,
> 
> I did some very simple ifft of real valued vector representing
> frequency domain samples ie. X[n]=[1 2 3 3 2]; imaginary part is 0 for
> all samples, to my surprise recreated time domain signal is h[n]=[2.2
> -0.52  -0.076 -0.076 -0.52].Those two last samples in h[n] look like
> they are just symmetry around first sample. According to my knowledge
> this should represent noncausal filter with symmetry around sample 0 -
> zero imaginary part hence phase for all samples is 0. Why this
> repetition of last two samples - shouldn't they be at the begining. Or
> in the other words how to define filter that is symmetrical around
> sample 0?
> 
> Kind regards
> 
> Pawel

Your results are correct, only your interpretation of them is confused.

The FFT and IFFT use math that is exactly appropriate for sampled, 
strictly periodic data.  So if you have samples ranging from 0..N-1, 
your (N-1)th sample is equal to sample -1, your (N-2)th sample is equal 
to sample -2, etc.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Do you need to implement control loops in software?
"Applied Control Theory for Embedded Systems" gives you just what it says.
See details at http://www.wescottdesign.com/actfes/actfes.html

On Mar 24, 5:46 pm, Tim Wescott <t...@seemywebsite.com> wrote:
> Pawel wrote:
> > Hello All,
>
> > I did some very simple ifft of real valued vector representing
> > frequency domain samples ie. X[n]=[1 2 3 3 2]; imaginary part is 0 for
> > all samples, to my surprise recreated time domain signal is h[n]=[2.2
> > -0.52  -0.076 -0.076 -0.52].Those two last samples in h[n] look like
> > they are just symmetry around first sample. According to my knowledge
> > this should represent noncausal filter with symmetry around sample 0 -
> > zero imaginary part hence phase for all samples is 0. Why this
> > repetition of last two samples - shouldn't they be at the begining. Or
> > in the other words how to define filter that is symmetrical around
> > sample 0?
>
> > Kind regards
>
> > Pawel
>
> Your results are correct, only your interpretation of them is confused.
>
> The FFT and IFFT use math that is exactly appropriate for sampled,
> strictly periodic data.  So if you have samples ranging from 0..N-1,
> your (N-1)th sample is equal to sample -1, your (N-2)th sample is equal
> to sample -2, etc.
>
> --
>
> Tim Wescott
> Wescott Design Serviceshttp://www.wescottdesign.com
>
> Do you need to implement control loops in software?
> "Applied Control Theory for Embedded Systems" gives you just what it says.
> See details athttp://www.wescottdesign.com/actfes/actfes.html

Hi Tim,

Thanks for Your explanation, however (sorry for trivial question but
only stupid do not ask), shouldn't be that N-1 sample in time domain
should be followed by 0  sample - to create periodic picture, in my
example N-1 is followed by value of sample -1.

Pawel

On Mar 24, 6:36 pm, Pawel <prulikow...@gmail.com> wrote:
> On Mar 24, 5:46 pm, Tim Wescott <t...@seemywebsite.com> wrote:
>
>
>
> > Pawel wrote:
> > > Hello All,
>
> > > I did some very simple ifft of real valued vector representing
> > > frequency domain samples ie. X[n]=[1 2 3 3 2]; imaginary part is 0 for
> > > all samples, to my surprise recreated time domain signal is h[n]=[2.2
> > > -0.52  -0.076 -0.076 -0.52].Those two last samples in h[n] look like
> > > they are just symmetry around first sample. According to my knowledge
> > > this should represent noncausal filter with symmetry around sample 0 -
> > > zero imaginary part hence phase for all samples is 0. Why this
> > > repetition of last two samples - shouldn't they be at the begining. Or
> > > in the other words how to define filter that is symmetrical around
> > > sample 0?
>
> > > Kind regards
>
> > > Pawel
>
> > Your results are correct, only your interpretation of them is confused.
>
> > The FFT and IFFT use math that is exactly appropriate for sampled,
> > strictly periodic data.  So if you have samples ranging from 0..N-1,
> > your (N-1)th sample is equal to sample -1, your (N-2)th sample is equal
> > to sample -2, etc.
>
> > --
>
> > Tim Wescott
> > Wescott Design Serviceshttp://www.wescottdesign.com
>
> > Do you need to implement control loops in software?
> > "Applied Control Theory for Embedded Systems" gives you just what it says.
> > See details athttp://www.wescottdesign.com/actfes/actfes.html
>
> Hi Tim,
>
> Thanks for Your explanation, however (sorry for trivial question but
> only stupid do not ask), shouldn't be that N-1 sample in time domain
> should be followed by 0  sample - to create periodic picture, in my
> example N-1 is followed by value of sample -1.
>
> Pawel
I always thought that the output of ifft is periodic but represents
only one period of a data, how does it relate to my results?

"Pawel" <prulikowski@gmail.com> wrote in message 
news:02e81e1a-4202-40c6-aa74-b848aa09c99b@s12g2000prg.googlegroups.com...
> Hello All,
>
> I did some very simple ifft of real valued vector representing
> frequency domain samples ie. X[n]=[1 2 3 3 2]; imaginary part is 0 for
> all samples, to my surprise recreated time domain signal is h[n]=[2.2
> -0.52  -0.076 -0.076 -0.52].Those two last samples in h[n] look like
> they are just symmetry around first sample. According to my knowledge
> this should represent noncausal filter with symmetry around sample 0 -
> zero imaginary part hence phase for all samples is 0. Why this
> repetition of last two samples - shouldn't they be at the begining. Or
> in the other words how to define filter that is symmetrical around
> sample 0?
>
> Kind regards
>
> Pawel

Pawel,

What you have is correct.  The frequency sequence is even and real so the 
time sequence is even and real.

The sequence in frequency goes from f=0 to f=(1/T)*(N-1) where T is the time 
span of the time sequence and N is the number of samples in both time and 
frequency.
So the frequency sequence is [3 2 1 2 3] *if* aligned centered on f=0.
But, we typically arrange the sequence as above so it's [1 2 3 3 2].

The sequence in time goes from t=0 to t=(T/N)*(N-1).
So the time sequence is [-0.076 -0.52 2.2 -0.52 -0.076] *if* aligned 
centered on t=0.
But, we typically arrange the sequence as above so it's 
[2.2 -0.52 -0.076 -0.076 -0.52]

Because both domains are discrete with uniform sampling interval, their 
transforms are periodic and all of these sequences are one period of 
that....

Note that if you use the sequences centered on zero then the things are 
still periodic but likely aren't purely even or odd.  In that case the FFT 
of the time sequence won't be  purely real - to reflect the "delay" in what 
had been purely even and real.

Fred 

On Mar 24, 8:15 am, Pawel <prulikow...@gmail.com> wrote:
> Hello All,
>
> I did some very simple ifft of real valued vector representing
> frequency domain samples ie. X[n]=[1 2 3 3 2]; imaginary part is 0 for
> all samples, to my surprise recreated time domain signal is h[n]=[2.2
> -0.52  -0.076 -0.076 -0.52].Those two last samples in h[n] look like
> they are just symmetry around first sample. According to my knowledge
> this should represent noncausal filter with symmetry around sample 0 -
> zero imaginary part hence phase for all samples is 0. Why this
> repetition of last two samples - shouldn't they be at the begining. Or
> in the other words how to define filter that is symmetrical around
> sample 0?

You have an odd length vector, so a symmetric result
will end up with one center value instead of the center
being between two equal valued samples.

On Mar 24, 7:27 pm, "Fred Marshall" <fmarshallx@remove_the_x.acm.org>
wrote:
> "Pawel" <prulikow...@gmail.com> wrote in message
>
> news:02e81e1a-4202-40c6-aa74-b848aa09c99b@s12g2000prg.googlegroups.com...
>
>
>
> > Hello All,
>
> > I did some very simple ifft of real valued vector representing
> > frequency domain samples ie. X[n]=[1 2 3 3 2]; imaginary part is 0 for
> > all samples, to my surprise recreated time domain signal is h[n]=[2.2
> > -0.52  -0.076 -0.076 -0.52].Those two last samples in h[n] look like
> > they are just symmetry around first sample. According to my knowledge
> > this should represent noncausal filter with symmetry around sample 0 -
> > zero imaginary part hence phase for all samples is 0. Why this
> > repetition of last two samples - shouldn't they be at the begining. Or
> > in the other words how to define filter that is symmetrical around
> > sample 0?
>
> > Kind regards
>
> > Pawel
>
> Pawel,
>
> What you have is correct.  The frequency sequence is even and real so the
> time sequence is even and real.
>
> The sequence in frequency goes from f=0 to f=(1/T)*(N-1) where T is the time
> span of the time sequence and N is the number of samples in both time and
> frequency.
> So the frequency sequence is [3 2 1 2 3] *if* aligned centered on f=0.
> But, we typically arrange the sequence as above so it's [1 2 3 3 2].
>
> The sequence in time goes from t=0 to t=(T/N)*(N-1).
> So the time sequence is [-0.076 -0.52 2.2 -0.52 -0.076] *if* aligned
> centered on t=0.
> But, we typically arrange the sequence as above so it's
> [2.2 -0.52 -0.076 -0.076 -0.52]
>
> Because both domains are discrete with uniform sampling interval, their
> transforms are periodic and all of these sequences are one period of
> that....
>
> Note that if you use the sequences centered on zero then the things are
> still periodic but likely aren't purely even or odd.  In that case the FFT
> of the time sequence won't be  purely real - to reflect the "delay" in what
> had been purely even and real.
>
> Fred

Fred,

Thanks a lot for an explanation, I guess it is one of those things
that is not fully explained in books (I went through a couple of
them), they mainly state that DFT/FFT is periodic - this is no
surprise as it uses complex exponentials.
Could you please elaborate on this more:

>Note that if you use the sequences centered on zero then the things are
> still periodic but likely aren't purely even or odd.  In that case the FFT
> of the time sequence won't be  purely real - to reflect the "delay" in what
> had been purely even and real.

How is it possible that it is not purely even or odd and how does it
relate to "delay".
My problem is how to recreate time domain data (essentially impulse
response) from frequency domain data (transfer function), the problem
is that algorithm that I am using requires impulse response centered
on zero.

>> > Pawel wrote:
>> > > Hello All,
>>
>> > > I did some very simple ifft of real valued vector representing
>> > > frequency domain samples ie. X[n]=[1 2 3 3 2]; imaginary part is 0
for
>> > > all samples, to my surprise recreated time domain signal is
h[n]=[2.2
>> > > -0.52  -0.076 -0.076 -0.52].Those two last samples in h[n] look
like
>> > > they are just symmetry around first sample. According to my
knowledge
>> > > this should represent noncausal filter with symmetry around sample
0 -
>> > > zero imaginary part hence phase for all samples is 0. Why this
>> > > repetition of last two samples - shouldn't they be at the begining.
Or
>> > > in the other words how to define filter that is symmetrical around
>> > > sample 0?
>>
>> Pawel
>I always thought that the output of ifft is periodic but represents
>only one period of a data, how does it relate to my results?

Hello Pawel,

Since it is periodic, you can as well think of the last two samples
as being in front of the first (the one with value 2.2).
Imagine you draw the result around an empty role of toilet-paper (or
any cylinder), so
that the end (the -0.52) fits to the beginning (the 2.2).
Now you have a periodic image of it.
It's periodic, so when you say the last two samples are at the end
while you expect them at the beginning, you forget that you can
think of them as being at the beginning, because of the periodicity.
What I want to say is that "beginning and end" are maybe confusing
words for something which is periodic or cyclic.

As somebody said before you can also interpret the sample N-1
as sample -1.

In matlab you often use the function 'fftshift', for plotting.
To see the symmetric picture more clearly. 

gr.
Bjoern

"Pawel" <prulikowski@gmail.com> wrote in message 
news:f18b7336-d47d-416d-86c1-48e55556197d@t54g2000hsg.googlegroups.com...
>
> Fred,
>
> Thanks a lot for an explanation, I guess it is one of those things
> that is not fully explained in books (I went through a couple of
> them), they mainly state that DFT/FFT is periodic - this is no
> surprise as it uses complex exponentials.
> Could you please elaborate on this more:
>
>>Note that if you use the sequences centered on zero then the things are
>> still periodic but likely aren't purely even or odd.  In that case the 
>> FFT
>> of the time sequence won't be  purely real - to reflect the "delay" in 
>> what
>> had been purely even and real.
>
> How is it possible that it is not purely even or odd and how does it
> relate to "delay".
> My problem is how to recreate time domain data (essentially impulse
> response) from frequency domain data (transfer function), the problem
> is that algorithm that I am using requires impulse response centered
> on zero.
>

Here are some examples:

f(nT)=[1 2 3 4 4 3 2] Real and even / centered at zero.

F(nW)=[19 -5.048  -0.307  -0.643  -0.643  -0.307  -5.048] Real and even 
centered at zero.

g(nT-2T)=[3 4 4 3 2 1 2] Real but not even / not centered at zero.

G(nW)=[19 1.123+j4.922 0.277-j0.133 -0.400-j0.502 -0.400+j0.502 0.277+j0.133
  1.123-j4.922]  Not purely even or odd.  The real part is even, the 
imaginary part is odd .. this resulting from the fact that g is real.

Fred 

Pawel wrote:
(snip)

> Thanks a lot for an explanation, I guess it is one of those things
> that is not fully explained in books (I went through a couple of
> them), they mainly state that DFT/FFT is periodic - this is no
> surprise as it uses complex exponentials.
> Could you please elaborate on this more:

DFT (FFT) have periodic boundary conditions.

First, consider the Fourier series, describing a periodic function
as in infinite sum of sine and cosine, integer multiples of the
frequency of the function being described.

Next, consider a finite sum and a finite number of terms.
The resulting transform describes a sampled (discrete) signal
instead of a continuous (periodic) signal.

Sometimes FFT is used on non-periodic signals, but when that is
done it should be realized that the solutions are periodic.

If you want non-periodic solutions look at the DST and DCT.

-- glen