Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronic Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

Register Log in

In real input DFT,Why one term is more instead of N/2 terms?

Status
Not open for further replies.

naresh850

Full Member level 3
Joined
Jun 9, 2006
Messages
157
Helped
6
Reputation
12
Reaction score
4
Trophy points
1,298
Activity points
2,249
real valued fft

I have one query about DFT.

In DFT, when input is real, we get even symmetry magnitude spectrum.

It means that if we perform N-point DFT on a real input sequence, we'll get N separate complex DFT output terms but first (N/2 + 1) terms are independent.

Why one term is more instead of N/2 terms?

Please clarify my confusion.

Thanks and regards,
Naresh
 

mahdithdn

Advanced Member level 4
Joined
Aug 18, 2004
Messages
107
Helped
27
Reputation
54
Reaction score
9
Trophy points
1,298
Location
Iran
Activity points
896
real input dft

hi,

note that the first (zero index) and the last term (N/2 index) are always real (their computation deals with real calculation) so these two terms have half computational complexity.

regards
 

naresh850

Full Member level 3
Joined
Jun 9, 2006
Messages
157
Helped
6
Reputation
12
Reaction score
4
Trophy points
1,298
Activity points
2,249
fft output is it independent

could u please clarify it brifly

Regards
 

naresh850

Full Member level 3
Joined
Jun 9, 2006
Messages
157
Helped
6
Reputation
12
Reaction score
4
Trophy points
1,298
Activity points
2,249
real input to the dft

hello I got something like.

Well, for an 8-point DFT the last three
DFT samples (m=5, m=6, & m=7) are the
conjugates of the m=3, m=2, & m=1 DFT samples,
respectively. So what we say is:

The last three samples of an 8-pt DFT
give us *NO* new information about the
DFT's spectrum. (For an 8-point DFT, the
m=4 DFT sample is independent.) In fact,
once we have computed the first (N/2)+1 = 5
DFT samples, we don't need to compute the
last (N/2)-1 DFT samples.

Of course, that is only true for real-valued
input samples applied to the DFT, *AND* if the
DFT length, N, is an even number.

If N happens to be an odd number, then only the
first (N+1)/2 samples of the DFT are independent.
For example, with a 9-point DFT only the first
five DFT samples are independent.
 

mahdithdn

Advanced Member level 4
Joined
Aug 18, 2004
Messages
107
Helped
27
Reputation
54
Reaction score
9
Trophy points
1,298
Location
Iran
Activity points
896
dft half first input

hi naresh850,

return back to the problem of an even 8 point DFT of real-valued signal. because the signal is real-valued we suspect that the computational complexity of DFT should be half of a DFT of a complex-valued signal. we justify our guess with the hermitian property of DFT so samples 7,6,5 are dependent to samples 1,2,3 ,respectively. hence, we need half computations in contrast with DFT of a complex-valued signal (of course only for this 6 points). but what about samples 0 and 4. I should mentioned here that referring to the forward DFT equation for calculation of samples 1,2,3 we deal with complex-valued computations, because DFT kernel is complex. but for samples 0 and 4 the kernel is 1 (exp(0)) and -1^kn (exp(-jkn)), respectively, so we deal with real-valued computations and therefore we have half the computational complexity in contrast with DFT of a complex-valued signal.

hope this will help you
 

naresh850

Full Member level 3
Joined
Jun 9, 2006
Messages
157
Helped
6
Reputation
12
Reaction score
4
Trophy points
1,298
Activity points
2,249
real-valued fft

Hi,

The question is y m= 4 is independent of 8 point DFT for real valued input?
 

bulx

Full Member level 4
Joined
Aug 7, 2004
Messages
225
Helped
47
Reputation
94
Reaction score
17
Trophy points
1,298
Activity points
1,520
input to real fft

Guess it becomes clear when you look at what frequencies the FFT output corresponds to. The correspond to 0, Fs/N, 2* Fs/N, 3*Fs/N, ... (N-1) * Fs/N.
(N = Numer of points, Fs= sampling frequncy)

Given the real input, the output at Fs/N will match that at (N-1)*Fs/N, 2*Fs/N will match that at (N-2)*Fs/N, and so on. So every output has a matching pair (except when N is odd, where one frequncy Fs/2 will have no pair).

However, whether N be even or odd, there is no pair for 0 Hz, ie; FFT gives no output for f = Fs. (If it was present in the signal it would get aliased to 0). So the DC component will be unmatched and unique. This explains the +1 in your original question. Agree?
-b
 

naresh850

Full Member level 3
Joined
Jun 9, 2006
Messages
157
Helped
6
Reputation
12
Reaction score
4
Trophy points
1,298
Activity points
2,249
fft for real input

In N = 8 point DFT, m = 4 is unmatched in spectrum, when input is real.

at m =1,2 and 3 there is matching pair at m = 7,6,and 5.

so absolute power at m = 1,2,3 is half coz there is a matching pair.

what about absolute power at m = 4, when input is real in 8 point DFT?

Regards,
Naresh
 

bulx

Full Member level 4
Joined
Aug 7, 2004
Messages
225
Helped
47
Reputation
94
Reaction score
17
Trophy points
1,298
Activity points
1,520
dft real as input

you are not an easy one to please :)

Point is that the FFT output makes sense (for reals) only till half the number of points, the rest will always be the reflection. This means that, for example, the spectral component at (N-1) * Fs/N is not what the FFT output says it is, the ouput here is the spectral component at 1*Fs/N + all frequencies that alias to 1*Fs/N. If you really wanted to see the spectral component at (N-1) * Fs/N alone, then you should change your sampling frequncy to 2*Fs, after putting in an anti aliasing filter at Fs.

The value of the FFT output is proportional to the square of the amplitude of the constituent sinewave at that frequency. This is true for the "unmatched" FFT output point (in earlier example) also, in addition to all other points. That there are "reflected" values doesnt mean that the power of the constituent sines are doubled. If you think about it the reflections go on till infinity, so then if you add up reflections, all components go to infinity, which is absurd.

Perhaps you are mistaking it for the two-sided spectrum (-ve and +ve freqs), then the total power at any freq f is the sum of the powers at +f and -f.
-b
 

brmadhukar

Advanced Member level 3
Joined
Jun 21, 2002
Messages
840
Helped
42
Reputation
84
Reaction score
11
Trophy points
1,298
Location
India
Activity points
6,783
fft output spectrum symmetry

hi bulx,
You are doing a pretty good job.

we know 0 corresponds to dc components. N/2+1,what does it correspond to is the basic question as I see and the secondary question is why is it real?

Your first explantion say there is no matching pair, but does not give physical explantion ....

BRMadhukar
 

bulx

Full Member level 4
Joined
Aug 7, 2004
Messages
225
Helped
47
Reputation
94
Reaction score
17
Trophy points
1,298
Activity points
1,520
dft real input complex output

Madhu,
In case of odd number of points, the output you mentioned would correspond to something slightly less than Fs/2. In case of N being even, it would correpsond to exactly Fs/2, which is the max frequency that can be handled by an FFT with sampling rate Fs.

I dont have an exact answer as to why is it real. From a mathematical view point it has to be real due to symmetry. From a physical view point, dont know if it is correct to say that the component at this freq looks like DC to the FFT.
-b
 

Status
Not open for further replies.
Toggle Sidebar

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Top