Thread Subject: Purely real result of IFFT

I know that generally if you have a real waveform, the DFT
is complex symmetric (the -f component is the conjugate of
the +f component).

So to do this backwards (i'm trying to create a random
frequency spectrum that will give a real waveform upon
taking the ifft), I had to write a function like this:

CN = zeros(1, RandLength);
CN(1 : RandLength/2) = randn(1, RandLength/2) - j*randn(1,
RandLength/2);
CN(RandLength/2 + 1 : RandLength) = conj(CN(RandLength/2 :
-1 : 1));

However, that didn't work unless i did this:

%force the element (1) and (N/2 + 1) to be real
CN(1) = randn(1);
CN(RandLength/2 + 1) = randn(1);

which i found by just seeing what the fft of a small real
vector was (trial and error i guess you could say).

My question is, why is this not the type of symmetry i am
used to?

I would expect for a vector of length 6, that
3,4 are conjugates
2,5 are conjugates
1,6 are conjugates

but instead i need
3,5 are conjugates
2,6 are conjugates
1,4 are real

This is very very important because before I take the ifft,
i am multiplying with a symmetric, real function, and that
is producing something that is not symmetric!! (so the my
ifft is not purely real)

Any guidance would be greatly appreciated.

Thanks,

David

"David Doria" <daviddoria@gmail.com> wrote in message
<fe346p$8no$1@fred.mathworks.com>...
> I know that generally if you have a real waveform, the
DFT
> is complex symmetric (the -f component is the conjugate
of
> the +f component).
>
> So to do this backwards (i'm trying to create a random
> frequency spectrum that will give a real waveform upon
> taking the ifft), I had to write a function like this:
>
> CN = zeros(1, RandLength);
> CN(1 : RandLength/2) = randn(1, RandLength/2) - j*randn
(1,
> RandLength/2);
> CN(RandLength/2 + 1 : RandLength) = conj(CN
(RandLength/2 :
> -1 : 1));
>
> However, that didn't work unless i did this:
>
> %force the element (1) and (N/2 + 1) to be real
> CN(1) = randn(1);
> CN(RandLength/2 + 1) = randn(1);
>
> which i found by just seeing what the fft of a small real
> vector was (trial and error i guess you could say).
>
> My question is, why is this not the type of symmetry i am
> used to?
>
> I would expect for a vector of length 6, that
> 3,4 are conjugates
> 2,5 are conjugates
> 1,6 are conjugates
>
> but instead i need
> 3,5 are conjugates
> 2,6 are conjugates
> 1,4 are real
>
> This is very very important because before I take the
ifft,
> i am multiplying with a symmetric, real function, and
that
> is producing something that is not symmetric!! (so the my
> ifft is not purely real)
>
> Any guidance would be greatly appreciated.
>
> Thanks,
>
> David

just a quick thought, is this because the base index of
the vector has to be 1 in matlab? doesn't this offset all
the values by 1 index? maybe see the doc ifft where it
talks about the conjugate symmetric condition and see if
the +1 in that agrees with what you are seeing.

Ok that tells me that I came to the correct conclusion, but
here is a bit further question

I thought the sum in the IDFT was from k = -N/2 to N/2, but
here it is from k=0 to N-1

if you assume that Xk is a complex number (a+bi), and use
Eulers formula to get cos(2*pi*j*k*n/N) + i*sin(2*pi*j*k*n/N)

you can show that if X(k) = X(-k)* then all the imaginary
terms cancel. This doesn't work if there are never negative
numbers in the exponent. How could you show this property
using k = 0 to N-1 ??

Thanks,

David

"David Doria" <daviddoria@gmail.com> wrote in message
<fe346p$8no$1@fred.mathworks.com>...
> I know that generally if you have a real waveform, the DFT
> is complex symmetric (the -f component is the conjugate of
> the +f component).
>
> So to do this backwards (i'm trying to create a random
> frequency spectrum that will give a real waveform upon
> taking the ifft), I had to write a function like this:
>
> CN = zeros(1, RandLength);
> CN(1 : RandLength/2) = randn(1, RandLength/2) - j*randn(1,
> RandLength/2);
> CN(RandLength/2 + 1 : RandLength) = conj(CN(RandLength/2 :
> -1 : 1));
>
> However, that didn't work unless i did this:
>
> %force the element (1) and (N/2 + 1) to be real
> CN(1) = randn(1);
> CN(RandLength/2 + 1) = randn(1);
>
> which i found by just seeing what the fft of a small real
> vector was (trial and error i guess you could say).
>
> My question is, why is this not the type of symmetry i am
> used to?
>
> I would expect for a vector of length 6, that
> 3,4 are conjugates
> 2,5 are conjugates
> 1,6 are conjugates
>
> but instead i need
> 3,5 are conjugates
> 2,6 are conjugates
> 1,4 are real
>
> This is very very important because before I take the ifft,
> i am multiplying with a symmetric, real function, and that
> is producing something that is not symmetric!! (so the my
> ifft is not purely real)
>
> Any guidance would be greatly appreciated.
>
> Thanks,
>
> David

"David Doria" <daviddoria@gmail.com> wrote in message
<fe36l0$i5h$1@fred.mathworks.com>...
> Ok that tells me that I came to the correct conclusion,
but
> here is a bit further question
>
> I thought the sum in the IDFT was from k = -N/2 to N/2,
but
> here it is from k=0 to N-1
>
> if you assume that Xk is a complex number (a+bi), and use
> Eulers formula to get cos(2*pi*j*k*n/N) + i*sin
(2*pi*j*k*n/N)
>
> you can show that if X(k) = X(-k)* then all the imaginary
> terms cancel. This doesn't work if there are never
negative
> numbers in the exponent. How could you show this
property
> using k = 0 to N-1 ??

i am probably not the best one to explain this, but take a
good look at the fftshift function and the indexing they
explain in the description of the fft function itself in
the help. i rarely have use for ifft and usually only
worry about psd... but i think what you would expect to be
the -N/2 to 0 part is actually the high end of the vector,
the fftshift function moves it around so the '0' index (DC
component) is in the middle of the result vector, which is
easier for some people to handle... then you just have to
subtract N/2 from each index to line up the indexing with
the classical formulas. again, this is all because matlab
indexes have to be integers >0... so everything is shifted
to accomodate this limitation.

David Doria wrote:
> I know that generally if you have a real waveform, the DFT
> is complex symmetric (the -f component is the conjugate of
> the +f component).

I would say that the discrete-time Fourier transform (DTFT) is conjugate
symmetric such that X(f) = conj(X(-f)). The discrete Fourier transform
(DFT) is defined over a discrete sample index from 0 to N-1, so the
symmetry property is similar but not exactly the same.

 > I would expect for a vector of length 6, that
 > 3,4 are conjugates
 > 2,5 are conjugates
 > 1,6 are conjugates
 >
 > but instead i need
 > 3,5 are conjugates
 > 2,6 are conjugates
 > 1,4 are real

That's not quite correct.

Suppose you have this DFT transform pair:

x[n], 0 <= n <= N-1
X[k], 0 <= k <= N-1

If x[n] is real, then X[k] satisfies this symmetry relationship:

X[k] = conj(X[mod(N-k,N)])

Note that this symmetry relationship implies that X[0] must be real,
because X[0] = conj(X[mod(N,N)]) = conj(X[0]).

If N is even, it also implies that X[N/2] is real, because X[N/2] =
conj(X[mod(N - N/2,N)]) = conj(X[mod(N/2,N)]) = conj(X[N/2]).

If we switch to 1-based vector indexing, then the conjugate symmetry
relationship becomes:

X(k) = conj(X(mod(N-k+1,N)+1)), 1 <= k <= N.

> This is very very important because before I take the ifft,
> i am multiplying with a symmetric, real function, and that
> is producing something that is not symmetric!! (so the my
> ifft is not purely real)

The function you are multiplying with needs to satisfy the symmetry
condition I described above.

--
Steve Eddins
http://blogs.mathworks.com/steve

I looked at that... it still seems to give a very weird result.

If i take a=[1 2 3 4 5 6]

b=fft(a) is in the strange form (not symmetric over the 3/4
break)

fftshift(b) is actually just as not symmetric, simply the 2
halves switched.

Any more ideas?

David

"David " <dave@bigcompany.com> wrote in message
<fe385v$coq$1@fred.mathworks.com>...
> "David Doria" <daviddoria@gmail.com> wrote in message
> <fe36l0$i5h$1@fred.mathworks.com>...
> > Ok that tells me that I came to the correct conclusion,
> but
> > here is a bit further question
> >
> > I thought the sum in the IDFT was from k = -N/2 to N/2,
> but
> > here it is from k=0 to N-1
> >
> > if you assume that Xk is a complex number (a+bi), and use
> > Eulers formula to get cos(2*pi*j*k*n/N) + i*sin
> (2*pi*j*k*n/N)
> >
> > you can show that if X(k) = X(-k)* then all the imaginary
> > terms cancel. This doesn't work if there are never
> negative
> > numbers in the exponent. How could you show this
> property
> > using k = 0 to N-1 ??
>
> i am probably not the best one to explain this, but take a
> good look at the fftshift function and the indexing they
> explain in the description of the fft function itself in
> the help. i rarely have use for ifft and usually only
> worry about psd... but i think what you would expect to be
> the -N/2 to 0 part is actually the high end of the vector,
> the fftshift function moves it around so the '0' index (DC
> component) is in the middle of the result vector, which is
> easier for some people to handle... then you just have to
> subtract N/2 from each index to line up the indexing with
> the classical formulas. again, this is all because matlab
> indexes have to be integers >0... so everything is shifted
> to accomodate this limitation.
>

So does anyone know how to show that the IFFT of a complex
symmetric function is purely real when you use the k=0 to
N-1 definition? My current method completely relies on the
exponent of the exponential switching signs, which it in
fact does not do here... Does it now happen because sine and
cosine of integer multiples of 2*pi have opposite signs than
odd multiples of pi ?

Thanks,

David

"David Doria" <daviddoria@gmail.com> wrote in message
<fe39c9$1p3$1@fred.mathworks.com>...
> I looked at that... it still seems to give a very weird
result.
>
> If i take a=[1 2 3 4 5 6]
>
> b=fft(a) is in the strange form (not symmetric over the 3/4
> break)
>
> fftshift(b) is actually just as not symmetric, simply the 2
> halves switched.
>
> Any more ideas?
>
> David
>
> "David " <dave@bigcompany.com> wrote in message
> <fe385v$coq$1@fred.mathworks.com>...
> > "David Doria" <daviddoria@gmail.com> wrote in message
> > <fe36l0$i5h$1@fred.mathworks.com>...
> > > Ok that tells me that I came to the correct conclusion,
> > but
> > > here is a bit further question
> > >
> > > I thought the sum in the IDFT was from k = -N/2 to N/2,
> > but
> > > here it is from k=0 to N-1
> > >
> > > if you assume that Xk is a complex number (a+bi), and use
> > > Eulers formula to get cos(2*pi*j*k*n/N) + i*sin
> > (2*pi*j*k*n/N)
> > >
> > > you can show that if X(k) = X(-k)* then all the imaginary
> > > terms cancel. This doesn't work if there are never
> > negative
> > > numbers in the exponent. How could you show this
> > property
> > > using k = 0 to N-1 ??
> >
> > i am probably not the best one to explain this, but take a
> > good look at the fftshift function and the indexing they
> > explain in the description of the fft function itself in
> > the help. i rarely have use for ifft and usually only
> > worry about psd... but i think what you would expect to be
> > the -N/2 to 0 part is actually the high end of the vector,
> > the fftshift function moves it around so the '0' index (DC
> > component) is in the middle of the result vector, which is
> > easier for some people to handle... then you just have to
> > subtract N/2 from each index to line up the indexing with
> > the classical formulas. again, this is all because matlab
> > indexes have to be integers >0... so everything is shifted
> > to accomodate this limitation.
> >
>

On Oct 4, 9:26 am, "David Doria" <daviddo...@gmail.com> wrote:
> I know that generally if you have a real waveform, the DFT
> is complex symmetric (the -f component is the conjugate of
> the +f component).
>
> So to do this backwards (i'm trying to create a random
> frequency spectrum that will give a real waveform upon
> taking the ifft), I had to write a function like this:
>
> CN = zeros(1, RandLength);
> CN(1 : RandLength/2) = randn(1, RandLength/2) - j*randn(1,
> RandLength/2);
> CN(RandLength/2 + 1 : RandLength) = conj(CN(RandLength/2 :
> -1 : 1));
>
> However, that didn't work unless i did this:
>
> %force the element (1) and (N/2 + 1) to be real
> CN(1) = randn(1);
> CN(RandLength/2 + 1) = randn(1);
>
> which i found by just seeing what the fft of a small real
> vector was (trial and error i guess you could say).
>
> My question is, why is this not the type of symmetry i am
> used to?
>
> I would expect for a vector of length 6, that
> 3,4 are conjugates
> 2,5 are conjugates
> 1,6 are conjugates
>
> but instead i need
> 3,5 are conjugates
> 2,6 are conjugates
> 1,4 are real
>
> This is very very important because before I take the ifft,
> i am multiplying with a symmetric, real function, and that
> is producing something that is not symmetric!! (so the my
> ifft is not purely real)
>
> Any guidance would be greatly appreciated.
>
> Thanks,
>
> David

The issue here is a common difficulty in translating the sense of
symmetry from the continuous domain to the discrete domain. The topic
has a long history. The classic Harris windows paper discusses it and
uses the term "DFT-even" for the result.

The paper is available at:
http://www.eng.vt.edu/me5714/textbook/windows.pdf

The topic is explained on the first and second pages of the paper.

Dale B. Dalrymple
http://dbdimages.com
http://stores.lulu.com/dbd