Sirs, 

Looking at each frequency component in discrete fourier transform

X[k] = sum(x(n) * exp (-j2*pi*k*n/N));

Here each x term is multiplied by sine and cosine term.

As as we take each x and multiply by cosine and sine term, only n changes.

I have few questions,

1) is every sine and cosine term just a discrete representation of
continuous value
2) every time, we change n value in sine and cosine, what are we really
doing. Speaking, in theoretically?
3) is it correct to assume that for a fixed K above, the frequency of
corresponding sine and cosine terms remain the same
4) if I am converting a digital signal to its dft representation, what is
the max frequency of sine/cosine terms

On Thu, 11 Oct 2012 23:44:05 -0500, manishp wrote:

> Sirs,
> 
> Looking at each frequency component in discrete fourier transform
> 
> X[k] = sum(x(n) * exp (-j2*pi*k*n/N));
> 
> Here each x term is multiplied by sine and cosine term.
> 
> As as we take each x and multiply by cosine and sine term, only n
> changes.
> 
> I have few questions,
> 
> 1) is every sine and cosine term just a discrete representation of
> continuous value

Yes and no.  It depends on how you hold your mouth.  If you're using the 
DFT because you want to approximate continuous-time spectral 
measurements, then you can certainly think that way and get further 
along.  Such thinking is fraught with pitfalls, however, so you should 
keep in mind that it's an _approximation_.

I prefer to think of the DFT as it's own thing, with samples that only 
exist at discrete points; that way the math all makes sense, and if you 
are doing spectral analysis of continuous-time signals then you have two 
well-defined points of approximation: where you sample, and where you 
truncate.  Everything else is exact.

> 2) every time, we change n value in sine and cosine, what are we really
> doing. Speaking, in theoretically?

Changing the n value in the sine and cosine.

It may be easier to think of it as advancing in time, however.

> 3) is it correct to assume that for a fixed K above, the frequency of
> corresponding sine and cosine terms remain the same

No, it is not correct to assume an assertion that can easily be proven to 
be true or false.  What do _you_ think, why, and can you prove it?

> 4) if I am
> converting a digital signal to its dft representation, what is the max
> frequency of sine/cosine terms

k = infinity.  But you might find it interesting to experiment with the 
difference between X[N + k] and X[k] -- then I think you'll be able to 
answer your own question.

-- 
My liberal friends think I'm a conservative kook.
My conservative friends think I'm a liberal kook.
Why am I not happy that they have found common ground?

Tim Wescott, Communications, Control, Circuits & Software
http://www.wescottdesign.com

manishp <58525@dsprelated> wrote:

> Looking at each frequency component in discrete fourier transform

> X[k] = sum(x(n) * exp (-j2*pi*k*n/N));

> Here each x term is multiplied by sine and cosine term.

> As as we take each x and multiply by cosine and sine term, only n changes.

> I have few questions,

> 1) is every sine and cosine term just a discrete representation of
> continuous value

For finite k, yes, for infinite k, no. The latter case (Fourier
series) allows for a sum of continuous functions. (In the latter,
they are a continuous representation for a continuous value.)

> 2) every time, we change n value in sine and cosine, what are we really
> doing. Speaking, in theoretically?

OK, all of Fourier analysis comes from the solutions of
differential equations. Different equations use different basis
functions, but the simpler second order differential equations
use sine and cosine (or exp(ikx) and exp(-ikx)) as a basis.

Consider the equation for a displacement (pluck or bow) of
a violin string. Without too much explanation of the physics,
for a string of uniform mass density under uniform tension,
the resulting equation is the wave equation.

The displacement y, as a function of x (position) and t (time):

d2y/dt2 = A d2y/dx2

(Hopefully all can read that, as second partial derivatives with
respect to t (left) and x (right). It should be easy to see that
A has units of velocity squared, which, in the case of string
under tension, is T/u, T being the tension, u being mass per
unit length.

Note that the general solutions to this equation are f(x-vt)
and g(x+vt), where f and g are arbitrary functions, and v**2=a.
(It isn't hard to show from the definition of partial derivative
that those are the solutions.)

A separable partial differential equation allows one to separate
the dependence of two variables, in this case resulting in two
ordinary differential equations. Write

y(x,t)=X(x)T(t) (that is, a product of functions of x and of t.)

Put that into the equation taking derivatives as needed.

X(x)T''(t)=A X''(x)T(t) and divide by X(x)T(t) such that

T''(t)/T(t) = A X''(x)/X(x) =B.

Since one side only depends on t, the other only on x, either
both are zero (not very interesting) or both are equal to a 
constant, B.  (The equation allows for complex B.)

If T''(t)= B T(t), a nice ODE, then we can see that
solutions like sin(wt) and cos(wt) or exp(wt) and exp(-wt)
are possible for a given w (that should be small omega)
where -w^2=B. 

The right have has solutions like sin(kx) and cos(kx)
or exp(ikx) and exp(-ikx) for -k^2 = B/A.  (Allowing
for complex A and B, but simplifying for the real case.)

Applying the boundary conditions, and remembering that the
sum of the solutions to a linear homogeneous differential 
equation is also a solution, we find solutions of the form

X(x)T(t)=(a sin(kx)+b(cos kx))(c sin(wt)+d cos(wt))
(or a similar expansion in terms of exp.)

where A k^2 = w^2, and remembering that A has velocity squared unit.

Note that the solutions are continuous, and that all a, b, c, 
and d are still allowed along with all k (or w).

Now, put the string on a violin such that it has length L,
with the coordinate system 0 and one end, L at the other.

The X(0)=0 boundary condition at one end means all b are zero.
The X(L)=0 at the other end only allows for discrete k,
such that kL is an integer multiple of pi. Since A is constant
(based on tension and string mass per unit length) this allows
for discrete w such that w/k=sqrt(A)=v (the velocity of the
wave on the string). 

The allowed modes are called normal modes. k is the wavenumber
(2 pi/wavelength), w is the angular frequency (usually 
radians/second) and is 2 pi f (f in cycles per second).

If we add a restriction on w (or k) such that it be less
than a certain value, then a finite number of solutions
are allowed, allowing for a discrete transform.

Note that in this case the boundary condition allowed
for only sines, and so the appropriate transform is the DST.

What problems have the periodic boundary conditions of the DFT?

Consider rotating a loop of rope, stories are that cowboys
can do this with a lasso. If you rotate it, then there will
be tension due to the centrifugal force, again the wave equation
applies with solutions f(kx-wt) and g(kx+wt) in the rotating
frame, and we could use the DFT, with periodic boundary
conditions to solve for the solutions.

In this case, though, it is easier to see the answer in
terms of the general solutions to the wave equation. 
f(kx-wt) and g(kx+wt) correspond to waves going in opposite
directions around the loop (in the rotating frame).

Consider a small piece of rope of length Rdtheta, mass per
unit length u (usually mu), on a rope rotating at w (radians
per unit time). The centrifugal force is m R w^2, or in
this case u r^2 w^2 dtheta. The tension needed to keep in 
place causes an inward force of T dtheta. (T dtheta/2 for
each end of the small piece of rope.) Putting the two
together (equilibrium) T = u R^2 w^2. As previously
noted, the velocity of the wave along the rope, 
squared is T/u, so now equals R w. 

But note that the velocity of the rotating rope is also R w.

In the non-rotating frame, then, the two waves will move
with velocity 0 and 2Rw. Supposedly this is an old cowboy
trick. If you rotate the end of a lasso, then kick it
(to supply an impulse) it will seem to stay stationary.
(You mostly don't see the one going around at 2Rw for
sufficiently large w, and it has to be large enough to
hold the rope up.)

(By the way, the math is much easier with k and w instead
of f and lambda. Not so many 2pi around, and k increases with
spatial frequency, instead of lambda decreasing.)

> 3) is it correct to assume that for a fixed K above, the frequency of
> corresponding sine and cosine terms remain the same


> 4) if I am converting a digital signal to its dft representation, 
     what is the max frequency of sine/cosine terms

Depends on the sampling rate. Note that for a longer time signal,
higher N will correspond to higher n, such that the highest k
(approximately) doesn't increase.

-- glen

On 10/12/12 12:44 AM, manishp wrote:
>
> Looking at each frequency component in discrete fourier transform
>
> X[k] = sum(x(n) * exp (-j2*pi*k*n/N));
>
> Here each x term is multiplied by sine and cosine term.
>
> As as we take each x and multiply by cosine and sine term, only n changes.
>
> I have few questions,
>
> 1) is every sine and cosine term just a discrete representation of
> continuous value

sampled continuous-time value.  that makes it discrete time.

> 2) every time, we change n value in sine and cosine, what are we really
> doing. Speaking, in theoretically?

just going around a unit circle, in your example above, in the clockwise 
direction.

> 3) is it correct to assume that for a fixed K above, the frequency of
> corresponding sine and cosine terms remain the same

yes.  and it's not an assumption.

    s^(J*theta)  =  cos(theta) +  j*sin(theta)

same theta in the cos() or the sin().

> 4) if I am converting a digital signal to its dft representation, what is
> the max frequency of sine/cosine terms

if your discrete-time signal x[n] is real, then the DFT will have this 
Hermtian symmetry that causes the "negative" frequency components to be 
the complex conjugate or their positive counterparts.  and in the DFT, 
the second half, X[N/2] to X[N-1] are the "negative" frequencies.  if 
the DFT length, N, is even, there is a component at Nyquist, X[N/2], 
that i don't recommend using since there will be an ambiguity of 
amplitude and phase.  so that means the highest frequency is
(N/2 - 1)/(N/2)*Nyquist.  every discrete frequency from DC (spaced by 
(2/N)*Nyquist) to that is independently representable in the DFT with a 
real signal x[n].



-- 

r b-j                  r...@audioimagination.com

"Imagination is more important than knowledge."