Real DFT and Complex DFT in Matlab

[bcosta]

dft in matlab

Hi all,

I have recently been reviewing DSP (I did DSP at university a number of years ago and am trying to refresh). I have recently just read a textbook I found (not from my University studies) that has been very helpful. In the book they distinguish between the “Real DFT” and the “Complex DFT” and went through most of the book using just the real DFT. I do not remember coming across this distinction while at University.

I want to play around with a few things in matlab now, but as I understand it the fft() and ifft() functions in Matlab implement the “Complex DFT” using the fast fourier transform algorithm. Is anyone aware of functions for computing the “Real DFT” in Matlab?

Also, could someone let me know if my understanding of the relationship between the two as described below is correct?

Real DFT:
Converts N samples to two sets of N/2 + 1 samples (ImX[] and ReX[] according to the text book). These are not really complex numbers but are the amplitudes of the basis functions (cosine and sine waves) that can be combined to make up the time domain signal. Since they are the amplitudes of cosine and sine basis functions they can be treated as the real and imaginary parts of complex numbers through substitution. One purpose of doing this is to convert them into polar form by creating N/2 + 1 size magnitude and phase vectors RMagX[] RPhaseX[] from the complex numbers, giving the magnitude and phase of the frequency response.

If converting to polar form, the values for RMagX and RPhaseX give the magnitude and phase from k = 0 (DC) to k = fs/2.


Complex DFT:
Converts N complex number samples in the “time domain” into N complex number samples in the frequency domain. This includes the negative frequencies from –fs/2 to 0 which are generally a duplicate of the positive frequencies (as I understand it when the time domain samples are purely real then the negative frequencies mirror the positive ones).

The values can be represented in polar form CMagX, CPhaseX both N samples in size.

The relationship between the real DFT polar form and the complex DFT polar form, is that the first N/2 samples of CMagX and RMagX would be the same (possibly with scaling differences), and the first N/2 samples of CPhaseX and RPhaseX would also be the same. This comes from the fact that the real DFT “assumes” a mirrored set of negative frequencies due to the fact that the real DFT only ever transforms real time domain signals and never complex ones (thus producing mirrored negative frequencies).

If this is correct and I have the samples for a “Real DFT” in the frequency domain, I could create the “Complex DFT" samples in the frequency domain by simply mirroring the values for RMagX and RPhaseX in the range 0 to N/2 into the range N/2 + 1 N for CMagX and CPhaseX. Is this correct?

Finally as a last question, do people generally use the real DFT or the complex DFT for most of their DSP work? What sorts of applications would you choose to use each of these for?

Thanks,
Brendon.

 

[rramya]

matlab dft

hi bcosta,
where did you read the article.
can U provide me the article. ( prescribe any book U read)

out of curiosity i ask U

happy learning

 

[bcosta]

dft matlab

The book was called: Digital Signal Processing: A Practical Guide for Engineers and Scientists by Steven W Smith

It was good to read from the start as it explained the concepts of most everything it presented which helped me to understand the mathematics much better. The relevant chapters for my question are Chapter 8 (The Discrete Fourier Transform) and Chapter 31 (The Complex Fourier Transform).

 

[rramya]

real dft

Thank you Bsosta. I learn that and come back to U regarding the question.

Happy learning

 

[rramya]

complex dft

Hi Bcosta,

for your last question i have an answer.

"do people generally use the real DFT or the complex DFT for most of their DSP work? What sorts of applications would you choose to use each of these for? "


The polymorphic FFT VI computes the FFT of a signal and has two
instances—Real FFT and Complex FFT.

The difference between the two instances is that the Real FFT instance
computes the FFT of a real-valued signal, whereas the Complex FFT
instance computes the FFT of a complex-valued signal. However, the
outputs of both instances are complex. ( if the real i/p seq is not symmetric)

Most real-world signals are real valued. Therefore, you can use the
Real FFT instance for most applications.

You also can use the Complex FFT instance by setting the imaginary part of the signal to zero.

An example of an application where you use the Complex FFT instance
is when the signal consists of both a real and an imaginary component.

A signal consisting of a real and an imaginary component occurs frequently
in the field of telecommunications, where you modulate a waveform by a
complex exponential.

eg.
The process of modulation by a complex exponential
results in a complex signal

Happy learning

Added after 21 minutes:

Hi BCOSTA,
but still i can't get the meaning of " mirorred set of negative freq" What do you infer from the above statement.

if we take the Fourier series of cosine waveform (even symmetry)
Then Fourier series coefficients A = A
-k k

whether we can say it as a mirrored set of negative freq. ( whose Fourier coefficient values is same as that of positive k fourier coefficients) especially when the signal is even signal.



if we take fourier series of sinewaveform (odd symmetry)
Then Fourier series coefficients A = A*
-k k
here only imaginary part of the A is conjugated.
k

Whether we can say it as a conjugate symmetric set of negative frequecies (whose fourier coefficient values is complex conjugate of positive k fourier coefficients) especially when signal is odd.

Happy learning.

Added after 44 minutes:

As we all know, digital dreq lies bet -pi to pi or (0,2*pi).
if signal is real & even , it is enough if we calculate o to pi
then from pi to 2*pi or (0 to -pi), the spectrum will be folded with respect to pi (or with respect to 0)
to extend up to 2*pi ( - pi).

My question is :
whether mirored set of negative freq is same as positive freq (range of positive freq= 0 to pi,range of negative freq -pi to 0 )which when folded w.r.to zero ????????


happy learning

Added after 4 hours 48 minutes:

Hi bcosta,
U wrote:
I have the samples for a “Real DFT” in the frequency domain, I could create the “Complex DFT" samples in the frequency domain by simply mirroring the values for RMagX and RPhaseX in the range 0 to N/2 into the range N/2 + 1 N for CMagX and CPhaseX. Is this correct?

answer:
It's symmetrical only if the input data are real-valued even signal.

Note:
with N even, for real valued signal ,outputs 0 and N/2 will be real and unique, and conjugate symmetric with outputs N-1 to N/2+1).

It is symmetric with respect to N/2


If you try to apply the DFT to complex-valued data the spectrum is not symmetric.

Note:
When you compute the inverse DFT or FFT using the above symmetry, you get your real valued samples back. In contrast, if your input to the inverse DID NOT display the required symmetry, then the result of the inverse would be complex valued with non-zero imaginary parts

therefore,
by simply mirroring the values for RMagX and RPhaseX in the range 0 to N/2 into the range N/2 + 1 to N-1 for CMagX and CPhaseX. is NOT correct to the best of my knowlege


Happy Learning

 

[bcosta]

dft matlab code

Hi rramya,

Thanks for taking the time to look into this. I just looked at the statement:

"It's symmetrical only if the input data are real-valued even signal. "

I did some tests in matlab, and every real time domain signal (including non even ones) i attempt to perform a normal fourier transform produces a frequency domain signal where the values 1 to N/2 are the complex conjugate of N - 1 to N/2 + 1 (I may be off by one in these ranges).

I.e. It seems to me that the fourier transform of all real signals will produce a symmetrical frequency domain signal. It is only when you start using complex time-domain signals that the frequency domain looses symmetry.


For example, the matlab code below:

time_signal = [sin(linspace(0, 1, 100) * 2 * pi) ...
                  linspace(0, 1, 100)...
                  sin(linspace(0, 1, 312) * 2 * pi * 0.4)];

freq_signal = fft(time_signal);
amplitude = abs(freq_signal);
phase = angle(freq_signal);

backwards_freq_signal = conj(freq_signal(end:-1:1));
diff_freq_signal = freq_signal(2:end) - backwards_freq_signal(1:end - 1)

subplot(4,1,1);
plot(time_signal);

subplot(4,1,2);
plot(amplitude);

subplot(4,1,3);
plot(phase);

subplot(4,1,4);
plot(diff_freq_signal);

My question is :
whether mirored set of negative freq is same as positive freq (range of positive freq= 0 to pi,range of negative freq -pi to 0 )which when folded w.r.to zero ????????

Yes. The values for the "negative" frequencies -pi to 0 are the same as the values for the frequencies from pi to 2pi, which I think from what i discussed above is a "mirror" or better the mirrored complex conjugate of the frequencies from 0 to pi.

Notice in the matlab code the vector freq_signal is both reversed and its complex conjugate found.

I think i was using "mirrored" as a term and I should have been using mirrored complex conjugate. So to change my original question:

If this is correct and I have the samples for a “Real DFT” in the frequency domain, I could create the “Complex DFT" samples in the frequency domain by simply using the complex conjugate of the values RMagX and RPhaseX that are in the range 0 to N/2 into the range N - 1 to N/2 + 1 for CMagX and CPhaseX.

This means that the frequency domain values from pi to 2pi are unnecessary when we know the input signal is always real as they can be obtained as a mirrored complex conjugate of the samples from 0 to pi. This is why the "real fourier transform" produces half as many values as the complex fourier transform.

I wish I had a "Real FFT" function that I could play with in matlab...

[/quote]

 

[rramya]

real time fft for complex signal form

Hi bcosta,

first of all thank you very much for your long well explained reply. In addition to that i will state a few para and try to conclude a solution which might be thrilling.
i adding this concept because i have struggled to get this concept.


If your input signal is real and even (i.e. symmetric around zero, such that s(t) = s(-t)), then the spectrum will be real and even -- so you
don't even have to worry about those imaginary parts. (that is imaginary parts should be zero when U do fft i.e., freq domain sample values)


If your input signal is real and odd (i.e. anti-symmetric around zero, such that s(t) = -s(t)), then the spectrum will be purely imaginary and
off -- so you don't have to worry about those real parts. (that is real should be zero when U do fft i.e., freq domain sample values)


If your input signal is just plain real, without necessarily being odd or
even, then you can decompose it to an even part and an odd part .Then from the above two statements, the spectrum will be even in it's real part, and odd in it's imaginary part in other words, the it'll have conjugate symmetry around zero.

In short, Symmetry comes about due to the use of a complex exponential in the DFT .


If you have a N point real valued input waveform, your samples are the real valued inputs to the DFT or FFT, and the imaginary parts are set
to zero. After forward transforming it, you get N outputs that display some symmetry (e.g.: with N even, outputs 0 and N/2 will be real and unique, and outputs 1 to N/2-1 will be conjugate symmetric
with outputs N-1 to N/2+1).

That s why it is enough if we compute ceil(N+1)/2 without computing N-point DFT. (saving 50% dft computations , also memory storage)
As it displays conjugate symmetry of the spectrum that is in the range 0 to N/2.



1. when U take real & even signal (say cosine)& compute fft , freq domain values should not contain imaginary part. spectrum should also be real & even

2. When U take real & odd signal (say sine)& compute fft, freq domain values should not contain real part. spectrum should also be real & even

but in your code say real and odd signal, fft values produces real part as well even though it exhibit conjugate spectrum from N/2+1 to N-1.
So to avoid the real part in freq domain one has to follow DFT circular symmetry
i.e., for real odd signal for N (=even/odd value)
x[N-n] = - x[N] ;

also note: for even N especially for real-odd signal
X[p] DELf

X[0] DC ( zero freq) ===> 0
X[1] DEL f
X[2] 2 DEL f
X[3] 3 DEL f
X[4] 4 DELf (Nyquist frequency)===>0
X[5] –3 DEL f
X[6] –2 DEL f
X[7] –DEL f

For N = 8, X[1] and X[7] have the same magnitude(but complex conjugatein exist making real vlues to zero); X[2] and X[6] have the same magnitude; (but complex conjugatein exist making real vlues to zero); and X[3] and X[5] have the same magnitude. (but complex conjugatein exist making real vlues to zero); The difference is that X[1], X[2], and X[3] correspond to positive frequency components, while X[5], X[6], and X[7] correspond to negative frequency components. X[4] is at the Nyquist frequency. A representation where you see the positive and negative frequencies is the
two-sided transform. It is symmetric with respect to nyquist freq.

If incase N=7 (odd)
X[p] DEL f

X[0] DC ===> 0
X[1] DEL f
X[2] 2DEL f
X[3] 3DEL f
X[4] –3DELf
X[5] –2DELf
X[6] –DEL f


For N = 7, X[1] and X[6] have the same magnitude; (but complex conjugatein exist making real vlues to zero); X[2] and X[5] have the same magnitude; (but complex conjugatein exist making real vlues to zero); and X[3] and X[4] have the same magnitude. (but complex conjugatein exist making real vlues to zero); However, X[1], X[2], and X[3] correspond to positive frequencies, while X[4], X[5], and X[6] correspond to negative frequencies. Because N is odd, there is no component at the Nyquist frequency.


one would normally expect zero padding at the end.
(DFT CIRCULAR SYMMERTRICITY IS BROKEN)
but if do so, then real values do occur at the freq domain sample values of REAL -ODD SIGNAL.

INSTEAD PAD symmetrically. ( AT THE CENTRE)


X[0] DC ===> 0
X[1] DEL f
X[2] 2DEL f
X[3] 3DEL f
X[4] 4DEL f nyquist freq ==> 0
X[5] –3DELf
X[6] –2DELf
X[7] –DEL f


For example,
1. the array [1 2 3 8 3 2] is a real-even signal , where "1" is the zero-
frequency (DC) element, "8" is the Nyquist element, and "2 3" and "3
2" are the symmetric positive and negative frequency amplitudes,
respectively. To pad it symmetrically to length 8 ,you would do [1 2 3 4 0 4 3 2],
where the Nyquist frequency "8" has been split equally between
positive and negative frequencies.
if u want to compute N=16-point DFT. then the padded symmetrical array will look like
[1 2 3 4 0 0 0 0 0 0 0 0 0 4 3 2] so being padded symmetrically we can compute DFT for 0 to N/2. in matlab ceil(N+1)/2.

2. As per theory, 0th and nyquist component is made zero (for real-odd signal)
so real-odd signal with (N even) will {0, 10, 20,40,0,-40,20,-10}.
suppose if needs to do padding for N=16.
padded real-odd signal would be
{0, 10, 20,40,0,0,0,0,0,0,0,0,0,-40,20,-10}.
with (N+1)/2 data points are unique points. rest is redundant
symmetric.



So that we wont get real part WHEN WE DO FFT OF REAL-ODD SIGNALS.

I WILL TELL U WITH EXAMPLE CODE:
code:
time_signal=sin(linspace(0, 1, 10)*2*pi);

time_signal =
Columns 1 through 8

0 0.6428 0.9848 0.8660 0.3420 -0.3420 -0.8660 -0.9848

Columns 9 through 10

-0.6428 -0.0000

HERE IT DOESN'T EXHIBIT DFT CIRCULAR SYMMETRICITY.
SO CHANGE THE CODE LIKE THIS:

time_signal=sin(linspace(0, 1, 10)*2*pi);
N=length(time_signal);
time_signal=[time_signal(1:N/2) time_signal(N) time_signal(N/2+1:N-1) ];
freq_signal = fft(time_signal);

time_signal =

Columns 1 through 8

0 0.6428 0.9848 0.8660 0.3420 -0.0000 -0.3420 -0.8660

Columns 9 through 10

-0.9848 -0.6428

freq_signal =

Columns 1 through 5

-0.0000 -0.0000 - 4.6782i -0.0000 - 0.7117i 0.0000 + 0.3026i -0.0000 - 0.1276i

Columns 6 through 10

0.0000 -0.0000 + 0.1276i 0.0000 - 0.3026i -0.0000 + 0.7117i -0.0000 + 4.6782i


SEE THE REAL PART IS ZERO OFCOURSE AS PER THEORY (IT IS
BECAUSE OF DFT CIRCULAR SYMMETRIC)

IT IS ENOUGH IF WE CALCULATE DFT COMPUTATION FOR CEIL(N+1)/2 [ in matlab, as it
process the array from number 1 onwards ]
FOR BOTH N=EVEN CASE & N=ODD CASE

iN CASE OF REAL-EVENSIGNAL ( SAY CAUSE SIGNAL THE ZEROTH (DC COMPONENT) AS
WELL AS NYQUIST FREQ (N/2) SHOULD BE REAL (ANY ARBITRARY VALUE).

FINALLY, IF x[n] is made or padded symmetrically (i.e., if it follows dft symmetry)
one wont get real part in X[k] when x[n] is real & odd signal.spectrum will exhibit conjugate symmetric
from (N/2+1) to (N-1)
one wont get imaginary part in X[k] when x[n] is real & even signal.
spectrum will exhibit symmetric from (N/2+1) to (N-1)

it is enough if we compute dft for 0 to N/2.


happy learning

 

[Aya2002]

dft on complex number

thanks

 

[diaks]

from magnitude and phase to complex number matlab

Hi all
I went trough all this post, but still have problem.
I have autocorrelation data and trying calculate energy spectrum. When I was performing Fourier transform of half of signal I was obtaining as results real and imaginary part and wrong energy spectrum. When I mirrored my signal (made it even) I obtained really small imaginary part and big real, but real part is flipping from positive value to negative value. If I take ABS of real part the energy spectrum is perfect but it bother me really much why is like this. Why is not real part just positive.
Many thanks.
Maybe this picture better explain my problem. Why this fft is not positive only?
lower one is a picture is signal
upper one is a part of fft graph near the pick.