Question about difference between Discrete and Continous Fourier Series

[BurnedResistor]

According too Prof. Brian Osgood's Public Standford lectures, the complex exponential frequency components summed for a continuous Fourier series are from -infinity to infinity, stemming from the conversion of the sin waves of varying phases and amplitudes into a single complex exponential:





Where the C_n is the conjugate of C_?n  and C_0 is the average.

However, in the book "Discrete Fourier Transform" by Sundarajan, a complex exponential is used but only frequencys from 0 to N-1 are considered: Only positive n values are used:



Why is this? What about the discrete fourier transform allows it to ommit that?

[mark03]

For some reason I can't see any of your math.  But the Fourier transform can be discrete or continuous in either the time or frequency domain, neither domain, or both domains.  Discretization in one domain implies periodicity in the other domain.  The DFT is discrete in both domains, thus periodic in both domains.

[ejeffrey]

Nomenclature varies, and is often used sloppily by people who assume you know what they are talking about, but you can do fourier analysis with 4 types of transforms:

1) Fourier Transform.  Continuous and unbounded.  Integrate[f(x) * e*(ikx), {x, -inf, inf}]  The input is defined for all values of x, and the output is defined for all values of k.  This would be considered the "normal" fourier transform by physicists and mathematicians because it is a map from regular functions to regular functions, thus it is the easiest to do analytically, and represents real world analog signals.

2) Fourier Series.  Continuous but bounded.  Integrate(f(x), e*(i k_i x), {x, 0, N}).  The input is a continuous function over some interval and is effectively treated as periodic in that interval.  The output is a series of sin/cos amplitudes index by integers (i.e., discrete and unbounded)

3) Discrete time Fourier Transform.  Discrete but unbounded:  Sum[f(x) e*ikx, {x, -inf, inf}]  The input function f(x) is defined at discrete sample times.  The output is a continuous function of 'k', but is completely specified by the first nyquist band, that is, k < 1/sample rate, or equivalently on the interval (- 0.5/sample rate < k < 0.5/sample rate). 

4) Discrete Fourier transform.  Discrete and bounded.  Sum[f(x) * e^(i * k_i * x), {x, 0, N}].  Both the input and outputs are discrete and bounded (or periodic).  All numerical computation is done with the discrete Fourier transform since computers have finite memory, and real data is sampled at discrete intervals anyway.  Also called the FFT (Fast Fourier Transform) after the family of algorithms that makes it practical to compute.

Type 1 and 4 are their own inverses, while 2 and 3 are inverses of each other.  Which one you use depends on your application.  Very often what you want is to do a DFT in such a way that it approximates the continuous Fourier Transform.  You can do this by making sure that your signal is limited in both frequency and time.  You limit by frequency by analog filtering before digitization. You limit in time by applying a window function -- multiplication by a function that goes to zero at the beginning and end of the sample interval.  If you do that, the discrete fourier transform will be a close approximation of the continuous Fourier transform.  This is the big reason people tend to use the terms somewhat interchangeably: under the conditions you normally want to operate, they provide the same result even though they are technically different.

[mark03]

Adding even more confusion, if you are an engineer (rather than a physicist or mathematician), you

a) use j instead of i (this part is trivial),
b) tend to write omega or 2*pi*f instead of k (wavenumber),
c) flip the sign in the exponential (negative for the forward transforms, positive for the inverse transforms).

So, borrowing ejeffry's notation, the engineering forward transform is usually presented as Integrate[f(t) * e^(-j*omega*t), {t, -inf, inf}]

Like he says, once you understand what's going on, it's easy to decipher somebody else's notation based on the way you know it "should" be.   It's getting to that point the first time that is difficult.

[ejeffrey]

Yes, once you get the ideas down and need to have actual numbers come out right, the variations explode.

The basic principle of a "transform" like this is that you are writing a function as a weighted sum / integral of some orthogonal set of basis functions.  Fourier analysis uses complex exponentials (or sin and cos if you prefer), but there are still multiple ways you can parameterize them as basis functions.  It doesn't really change what you are doing, but if you want to compare answers with someone you better make sure you are using them consistently.

[BurnedResistor]

Yes, once you get the ideas down and need to have actual numbers come out right, the variations explode.

The basic principle of a "transform" like this is that you are writing a function as a weighted sum / integral of some orthogonal set of basis functions.  Fourier analysis uses complex exponentials (or sin and cos if you prefer), but there are still multiple ways you can parameterize them as basis functions.  It doesn't really change what you are doing, but if you want to compare answers with someone you better make sure you are using them consistently.

Adding even more confusion, if you are an engineer (rather than a physicist or mathematician), you

a) use j instead of i (this part is trivial),
b) tend to write omega or 2*pi*f instead of k (wavenumber),
c) flip the sign in the exponential (negative for the forward transforms, positive for the inverse transforms).

So, borrowing ejeffry's notation, the engineering forward transform is usually presented as Integrate[f(t) * e^(-j*omega*t), {t, -inf, inf}]

Like he says, once you understand what's going on, it's easy to decipher somebody else's notation based on the way you know it "should" be.   It's getting to that point the first time that is difficult.

Sorry about the late reply. Super busy with school work. Edited the post to now include the math.

Thanks for the detailed responses. I am still however somewhat confused:

In the stanford lecture it was explained that for the sum of the fourier series to be real, the positive and negative frequencys have to be conjugates of each other. This makes sense, as it causes the imaginary parts to cancel out. It seems however that this is not the case in the discrete case.

Am I interpreting what you are saying correctly in that running the frequency from negative infinity to infinity is simply a choice of notation, and a continuous Fourier series would still work if only run from 0 to infinity? This seems strange.

I think the answer lies somewhere in this:

For some reason I can't see any of your math.  But the Fourier transform can be discrete or continuous in either the time or frequency domain, neither domain, or both domains.  Discretization in one domain implies periodicity in the other domain.  The DFT is discrete in both domains, thus periodic in both domains.

[orin]

Yes, once you get the ideas down and need to have actual numbers come out right, the variations explode.

The basic principle of a "transform" like this is that you are writing a function as a weighted sum / integral of some orthogonal set of basis functions.  Fourier analysis uses complex exponentials (or sin and cos if you prefer), but there are still multiple ways you can parameterize them as basis functions.  It doesn't really change what you are doing, but if you want to compare answers with someone you better make sure you are using them consistently.

Wow, that said an awful lot in one paragraph... if you understand the idea of a change of basis.

I'd highly recommend the following course at Coursera to the OP:

https://www.coursera.org/learn/dsp

It goes far beyond the usual DFT coverage...  The math can be tricky if it's twenty-odd years since you've done this stuff!  Fortunately, this course is still free if you don't want a certificate.

[RoGeorge]

I'd highly recommend the following course at Coursera to the OP:

https://www.coursera.org/learn/dsp

It goes far beyond the usual DFT coverage...  The math can be tricky if it's twenty-odd years since you've done this stuff!  Fortunately, this course is still free if you don't want a certificate.

Is it possible to take the quiz and assignments (and check your answers against the correct ones) for the free version of the course?

[JacquesBBB]

Let us denote
$$ F = \sum_{n=-\infty}^{+\infty} c_n \exp ( i {2\pi\over N} n t ) $$

and

$$ F_N = \sum_{n=0}^{N-1} c_n \exp ( i {2\pi\over N} n t ) $$

Both \$F\$ and \$F_N\$ are periodic functions of period \$ N\$

but \$F\$ can be any function of period \$N\$, while \$F_N\$ is only defined by its first \$N\$ harmonics. This is what you  will do if you have a function \$f\$ that is only defined on \$N\$ equally spaced points. You represent it with only \$N\$ Fourier coefficients, and thus by \$F_N\$. You do this through a discrete Fourier transform that transform your \$N\$ values into \$N\$  Fourier coefficents.

If you do not know more of your function, it is useless to try to invent what would be the extra harmonics.

[JacquesBBB]

How do you do inline Latex ?   $$x$$ is display Latex. But $x$ is not inline  Latex ?. Maybe \$x\$ ?

Yes ! this is it so I can edit the above message.

[orin]

I'd highly recommend the following course at Coursera to the OP:

https://www.coursera.org/learn/dsp

It goes far beyond the usual DFT coverage...  The math can be tricky if it's twenty-odd years since you've done this stuff!  Fortunately, this course is still free if you don't want a certificate.

Is it possible to take the quiz and assignments (and check your answers against the correct ones) for the free version of the course?

That's what it says in the FAQ - "...submit assignments and earn a grade for free".  You just don't get a certificate.  It looks like they aren't enforcing deadlines in the current run of the course so it would be possible to join now and still do all the quizzes.  It would be challenging to catch up...

[ejeffrey]

Sorry about the late reply. Super busy with school work. Edited the post to now include the math.

Thanks for the detailed responses. I am still however somewhat confused:

In the stanford lecture it was explained that for the sum of the fourier series to be real, the positive and negative frequencys have to be conjugates of each other. This makes sense, as it causes the imaginary parts to cancel out. It seems however that this is not the case in the discrete case.

That is the case for both the continuous and discrete transform, with two caveats.

First is that discrete fourier transforms are usually written with only positive frequency.  If you have a sample rate Fs, then the DFT is periodic with period Fs.  You have a choice as to how you label the points.  They can either span from -Fs/2 to Fs/2, or from 0 to Fs.  The data is the same, it is just a question of how you label the plot.  If you assume that the input signal came from a sampled analog signal that has been band limited to < Fs/2, then it is more natural to think about the former representation and the negative frequency components will be the conjugate of the positive, but numerical FFT algorithms almost universally present the data in the latter format.  In that case, the components above Fs/2 will be the conjugates of the lower frequency elements.

The second caveat is that when you know that the input signal is real, it is common to simply omit the redundant data.  That is, you only report the elements between 0 and Fs/2.  The negative / high frequency components are omitted because they don't carry any new information.  If you see a representation of the "real FFT", it won't have the complex conjugate structure because those elements are simply omitted.  This is good because it saves you a factor of two in memory and computation speed.

Am I interpreting what you are saying correctly in that running the frequency from negative infinity to infinity is simply a choice of notation, and a continuous Fourier series would still work if only run from 0 to infinity? This seems strange.

If the time domain signal is real, yes: you only need to include the positive frequency components.  It isn't that the negative components "don't exist", you just don't have to keep track of them.  Once you allow complex signals you need to include both.