discrete fourier series and transform

Sirs,

While reading on frequency representation, I am a little confused with
discrete fourier series (as opposed to discrete fourier transform) and its
application.

Can I get some inputs please.

Thanks, manish	 

_____________________________		
Posted through www.DSPRelated.com

On 29.07.2013 10:28, manishp wrote:
> Sirs,
>
> While reading on frequency representation, I am a little confused with
> discrete fourier series (as opposed to discrete fourier transform) and its
> application.

The discrete Fourier transform transforms one vector into another. The 
output of a discrete Fourier transform is a vector whose elements are 
the coefficients in the corresponding Fourier series.

As far as applications go: Oh well, look, you could also ask for 
applications of a screw driver. Manifold! Separation of a signal into 
its frequency components certainly.

A discrete Fourier series gives the representation of
a **periodic continuous-time signal** as a sum of sinusoids
or complex exponentials.   For example,

x(t) = sum c_n exp(j 2pi nt/T) for all t, -infty < t < infty

where T is the period of the signal x(t). The continuous-time
signal is effectively represented by the sequence of complex
numbers .... c_{-2}, c_{-1}, c_{0}, c_{1}, c_{2}, ...
This sequence might be finite in length (e.g. c_{n} = 0
for all n such that |n| > N) or extend out to plus/minus
infinity.  However, x(t), being periodic, extends all the
way out to plus/minus infinity and for each and every
one of those times, its value is given by the expression\
above.

A discrete Fourier transform gives the representation of
the elements of a **vector** of N numbers as a weighted
sum of complex N-th roots of unity exp(j 2pi k/N).  Thus, 
each entry in the vector

(x[0], x[1], ... , x[N-1])

can be represented as 

x[k] = (1/N) sum from 0 to N-1 X[i]exp(j 2pi ik/N)

where each exp(j 2pi ik/N) = exp(j 2pi m/N) is a
complex N-th root of unity weighted by (1/N)X[i].
The vector

(X[0], X[1], ... , X[N-1])

is called the discrete Fourier transform of the
vector (x[0], x[1], ... , x[N-1]). Note that the
discrete Fourier transform is of finite length
just as (x[0], x[1], ... , x[N-1]) is. The rb-j's
of this world will tell you that actually both
x and X are actually one period of **sequences**
of period N that extend out to plus/minus infinity,
that is, for **any** integer M, x[M] = x[M mod N]
and X[M] = X[M mod N] and the mathematics supports
them, but lots of other folks will equally 
vehemently insist that this is sheer nonsense, and
the value of x[N], say, has nothing to do with the
values of x[0], x[1], ... , x[N-1]. Which side
you choose to believe is up to you.

Dilip Sarwate

On 7/29/13 6:36 AM, dvsarwate wrote:
> A discrete Fourier series gives the representation of
> a **periodic continuous-time signal** as a sum of sinusoids
> or complex exponentials.   For example,
>
> x(t) = sum c_n exp(j 2pi nt/T) for all t, -infty<  t<  infty
>
> where T is the period of the signal x(t). The continuous-time
> signal is effectively represented by the sequence of complex
> numbers .... c_{-2}, c_{-1}, c_{0}, c_{1}, c_{2}, ...
> This sequence might be finite in length (e.g. c_{n} = 0
> for all n such that |n|>  N) or extend out to plus/minus
> infinity.

but Dilip, i think the term we have for that is simply "Fourier series" 
or, in the case of c_n * e^(j*2*pi*n*t/T),  we might call it the 
"complex Fourier series".  at least in my copy of O&S, the term 
"Discrete Fourier Series" is about "a sequence ~x[n] that is periodic 
with period N so that ~x[n] = ~x[n+rN] for any integer value of r." (the 
tilde ~ is meant to be above the "x".)  that's what O&S call the 
"Discrete Fourier Series".  it's explicitly a mapping of one discrete 
and periodic sequence with period N to another discrete and periodic 
sequence of period N.


and, other than the little tilde above the x[n] (or X[k]), there is not 
one single equation that differentiates DFS from DFT with the exception 
of what they *must* do to make x[n] (without the tilde) work with the 
mathematically imposed circularity of the DFS (*and* the DFT, that's 
what the whole argument is about).  with *all* of the DFT theorems that 
*potentially* shift x[n] or X[k] (that is *all* of the theorems except 
for linearity), then it is necessary to use the "~x[n] = x[n mod N]" or 
"~X[k] = X[k mod N]".  there is no exception other than linearity (which 
is a trivial exception).  so periodicity is imposed on us by the 
mathematics (unless you do nothing of substance in the transformed 
domain), whether you call it "DFS" or "DFT".  that's why those other 
guys are wrong about this, Dilip.

The Discrete Fourier Series is one and the same as the Discrete Fourier 
Transform.    adding a tilde to the symbols is not a salient difference.


-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

On Monday, July 29, 2013 6:36:51 AM UTC-7, dvsarwate wrote:
> ...
>   Note that the
> discrete Fourier transform is of finite length
> just as (x[0], x[1], ... , x[N-1]) is. The rb-j's
> of this world will tell you that actually both
> x and X are actually one period of **sequences**
> of period N that extend out to plus/minus infinity,
> that is, for **any** integer M, x[M] = x[M mod N]
> and X[M] = X[M mod N] and the mathematics supports
> them, 

Specifically this is the case of "sequences periodic-in-N" if you want to find the supporting math.

> but lots of other folks will equally 
> vehemently insist that this is sheer nonsense, and
> the value of x[N], say, has nothing to do with the
> values of x[0], x[1], ... , x[N-1].

A clearer statement of the other side is that there are people who believe that they can assume, construct or measure sequences of arbitrary length that have values independent of rbj's choice of N and that can be periodic-in-rbj's-N, periodic-in-integer-other-than-rbj's-N or aperiodic. Mathematics supports all these cases. (Corollaries of this are that values of the terms in their sequences need not be a function of rbj's choice of N and that it is possible to pick their own value M and think about the M-point DFT without changing the values of terms in their sequences like rbj's must when he picks or changes N.)

> Which side
> you choose to believe is up to you.
> 
> Dilip Sarwate

Dale B. Dalrymple

On Monday, July 29, 2013 12:10:52 PM UTC-5, robert bristow-johnson wrote:

> but Dilip, i think the term we have for that is simply "Fourier series" 
> 
> or, in the case of c_n * e^(j*2*pi*n*t/T),  we might call it the 
> 
> "complex Fourier series".  at least in my copy of O&S, the term 
> 
> "Discrete Fourier Series" is about "a sequence ~x[n] that is periodic 
> 
> with period N so that ~x[n] = ~x[n+rN] for any integer value of r." (the 
> 
> tilde ~ is meant to be above the "x".)  that's what O&S call the 
> 
> "Discrete Fourier Series".  it's explicitly a mapping of one discrete 
> 
> and periodic sequence with period N to another discrete and periodic 
> 
> sequence of period N.


Robert:

With genuflections and obeisances in the general
direction of O&S which tome I do not have on my
bookshelf, I suggest that you are misinterpreting
what O&S are saying, and if not, I am willing to
entertain the possibility that what O&S are saying
is flat out wrong.

The discrete Fourier transform maps a vector x of
N complex-valued numbers to another vector X of
length N of complex-valued numbers. If we extend
x periodically to construct a complex-valued
sequence of period N, then the discrete Fourier
transform of the sequence can be defined as the
the corresponding periodic extension of X.

On the other hand, a discrete Fourier series
(manishp's choice, not the one I would have
chosen) represents a periodic continuous-time
signal x(t) as the sum of complex exponentials
exp(j 2pi nt/T) weighted by complex numbers
c_n. There is _nothing_ that is periodic about 
the sequence {c_n}: indeed, if the sequence of
c_n's were repeating periodically, the
continuous-time signal x(t) would deliver infinite
energy in each period, and we could all retire
since the energy crisis will have been solved!

So, I disagree with you, and possibly O&S, if you
are asserting that there is no difference except
for the typographical notation ~ between these
two notions: the representation of a periodic
sequence of complex numbers in terms of another
periodic sequence of complex numbers, and the
representation of a continuous-time periodic
signal by an aperiodic sequence of complex
numbers. There is considerable family resemblance:
they are kissing cousins, maybe even first cousins
or siblings, but identical twins, No.

>With genuflections and obeisances in the general
>direction of O&S which tome I do not have on my
>bookshelf, I suggest that you are misinterpreting
>what O&S are saying, and if not, I am willing to
>entertain the possibility that what O&S are saying
>is flat out wrong.
>
>The discrete Fourier transform maps a vector x of
>N complex-valued numbers to another vector X of
>length N of complex-valued numbers. If we extend
>x periodically to construct a complex-valued
>sequence of period N, then the discrete Fourier
>transform of the sequence can be defined as the
>the corresponding periodic extension of X.
>
>On the other hand, a discrete Fourier series
>(manishp's choice, not the one I would have
>chosen) represents a periodic continuous-time
>signal x(t) as the sum of complex exponentials
>exp(j 2pi nt/T) weighted by complex numbers
>c_n. There is _nothing_ that is periodic about 
>the sequence {c_n}: indeed, if the sequence of
>c_n's were repeating periodically, the
>continuous-time signal x(t) would deliver infinite
>energy in each period, and we could all retire
>since the energy crisis will have been solved!
>
>So, I disagree with you, and possibly O&S, if you
>are asserting that there is no difference except
>for the typographical notation ~ between these
>two notions: the representation of a periodic
>sequence of complex numbers in terms of another
>periodic sequence of complex numbers, and the
>representation of a continuous-time periodic
>signal by an aperiodic sequence of complex
>numbers. There is considerable family resemblance:
>they are kissing cousins, maybe even first cousins
>or siblings, but identical twins, No.
>

Dilip, as far as I remember O&S (and I read it a long time ago), when O&S
mentions Discrete Fourier Series, they address the representation of a
*discrete-time* periodic sequence while keeping the term Fourier Series for
a continuous-time periodic signal (the one you are taking as discrete
Fourier series). If you think about the above choice, Robert is also right,
as much as you are in clarifying the difference between the two.	 

_____________________________		
Posted through www.DSPRelated.com

manishp <58525@dsprelated> wrote:
 
> While reading on frequency representation, I am a little confused 
> with discrete fourier series (as opposed to discrete fourier 
> transform) and its application.

The naming does get confusing, and maybe isn't always consistent.

If you consider the possible Fourier transform pairs, among other
you find that periodic data transforms to discrete points in the
transform space (and vice versa, as usual). Non-periodic data
(limit as the period goes to infinity) transforms to/from a 
continuous spectrum.

Some additional transform pairs are that real data transform to
symmetric (even) functions, and imaginary to asymetric (odd)
functions, and again vice versa. 

The Fourier series, then, is used to describe a periodic continuous
signal as a sum of sinusoids that are integer multiples of the
source frequency, but continuous. That is, a periodic continuous
function has a discrete non-periodic transform. From the symmetry
of the transform, a discrete non-periodic function will have a
periodic continuous transform. These allow one to consider
a (periodic) square wave as an infinite sum of sines and/or cosines,
or (following Nyquist) to consider a band limited source sampled
at a series of discrete points.

Since computers can't represent either continuous data or data
of infinite extent, the FFT (or DFT) represent periodic discrete
input with a discrete periodic transform. (Note the symmetry.)
This is usually called the discrete Fourier transform, though
it seems that discrete Fourier series would be more appropriate.

-- glen

On 7/29/13 2:54 PM, dvsarwate wrote:
>
> On the other hand, a discrete Fourier series
> represents a periodic continuous-time
> signal x(t) as the sum of complex exponentials
> exp(j 2pi nt/T) weighted by complex numbers
> c_n. There is _nothing_ that is periodic about
> the sequence {c_n}:

yup.  c_n need not be periodic, and cannot be for an x(t) that is finite 
(which leaves out dirac delta).  but we call that "Fourier series". 
continuous in time and discrete in frequency.

> indeed, if the sequence of
> c_n's were repeating periodically, the
> continuous-time signal x(t) would deliver infinite
> energy in each period,

not just each period, but each sample.  if the c_n's were periodic, they 
would be the same as the periodic X[n] of the DFT (or DFS, as one might 
call it).  *but* what would add up in continuous time would be a 
periodic sequence of delta functions (and they each have infinite 
energy, even if they have finite area).

remember: periodic in one domain means sampled (or discrete) in the 
reciprocal domain (and vise versa).

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

On Mon, 29 Jul 2013 14:54:08 -0700 (PDT), dvsarwate
<dvsarwate@yahoo.com> wrote:

>On Monday, July 29, 2013 12:10:52 PM UTC-5, robert bristow-johnson wrote:
>
>> but Dilip, i think the term we have for that is simply "Fourier series" 
>> 
>> or, in the case of c_n * e^(j*2*pi*n*t/T),  we might call it the 
>> 
>> "complex Fourier series".  at least in my copy of O&S, the term 
>> 
>> "Discrete Fourier Series" is about "a sequence ~x[n] that is periodic 
>> 
>> with period N so that ~x[n] = ~x[n+rN] for any integer value of r." (the 
>> 
>> tilde ~ is meant to be above the "x".)  that's what O&S call the 
>> 
>> "Discrete Fourier Series".  it's explicitly a mapping of one discrete 
>> 
>> and periodic sequence with period N to another discrete and periodic 
>> 
>> sequence of period N.
>
>
>Robert:
>
>With genuflections and obeisances in the general
>direction of O&S which tome I do not have on my
>bookshelf, I suggest that you are misinterpreting
>what O&S are saying, and if not, I am willing to
>entertain the possibility that what O&S are saying
>is flat out wrong.
>
>The discrete Fourier transform maps a vector x of
>N complex-valued numbers to another vector X of
>length N of complex-valued numbers. If we extend
>x periodically to construct a complex-valued
>sequence of period N, then the discrete Fourier
>transform of the sequence can be defined as the
>the corresponding periodic extension of X.
>
>On the other hand, a discrete Fourier series
>(manishp's choice, not the one I would have
>chosen) represents a periodic continuous-time
>signal x(t) as the sum of complex exponentials
>exp(j 2pi nt/T) weighted by complex numbers
>c_n. There is _nothing_ that is periodic about 
>the sequence {c_n}: indeed, if the sequence of
>c_n's were repeating periodically, the
>continuous-time signal x(t) would deliver infinite
>energy in each period, and we could all retire
>since the energy crisis will have been solved!
>
>So, I disagree with you, and possibly O&S, if you
>are asserting that there is no difference except
>for the typographical notation ~ between these
>two notions: the representation of a periodic
>sequence of complex numbers in terms of another
>periodic sequence of complex numbers, and the
>representation of a continuous-time periodic
>signal by an aperiodic sequence of complex
>numbers. There is considerable family resemblance:
>they are kissing cousins, maybe even first cousins
>or siblings, but identical twins, No.

Hi Dilip,
  for what it's worth, at the beginning of their chapter 
titled: "The Discrete Fourier Transform", on page 541 of 
their 2nd Edition, Oppenheim & Schafer state:

  "Although several points of view can be taken toward the 
  derivation and interpretation of the DFT representation 
  of a finite-duration sequence, we have chosen to base 
  our presentation on the relationship between periodic 
  sequences and finite-length sequences. We will begin by 
  considering the Fourier series representation of 
  periodic sequences. While this representation is 
  important in its own right, we are most often interested 
  in the application of Fourier series results to the 
  representation of finite-length sequences. We accomplish 
  this by constructing a periodic sequence for which each 
  period is identical to the finite-length sequence. As we 
  will see. the Fourier series representation of the 
  periodic sequence corresponds to the DFT of the 
  finite-length sequence. Thus, our approach is to define 
  the Fourier series representation for periodic sequences 
  and to study the properties of such representations. 
  Then we repeat essentially the same derivations, assuming 
  that the sequence to be represented is a 
  finite-length sequence."


Notice their initial words: "Although several points of 
view can be taken ..."

Dilip, as far as I can tell, I conform to your viewpoint 
concerning this topic.

[-Rick-]