# Discrete fourier tranforms -help

• rainbowings
In summary, discrete Fourier transforms help one understand a periodic sequence by mapping it to another periodic sequence. The inverse DFT is used to differentiate between two periods.
rainbowings
discrete Fourier tranforms -help!

How does one write the orthogonality condition for discrete Fourier tranforms - alternatley, how does one express the kronecker delta as a sum over exp(i k x) kind of thing. One last thing - what is the mormalization constant in front of the sum (analogous to the 1/2 pi for the Fourier resolution of the dirac delta function)?

i would suggest posting to comp.dsp your question. i can maybe deal with it here if you could be a bit more specific.

do you want to know why the basis functions are orthogonal to each other? is that your first question?

the kronecker delta is not periodic, so a sum of exp(i k x) would have to be an integral instead. the inverse DFT of a sequence all having 1 for coefficients is a repeated delta, but i wouldn't call that a kronecker delta.

usually the forward DFT has not normalization constant in front and the inverse DFT has a 1/N in front. but that could be switched, or you could have 1/sqrt(N) in front of both.

Are you just asking for the DFT formula?

$$\hat{f}(s) = \frac{1}{N} \sum_{t=0}^{N-1} \omega^{-st} f(t)$$

Or maybe it's +st, not -st, I forget.

&omega; is your favorite (primitive) N-th root of unity. exp(2 &pi; i / N) is usually a good choice.

Thanks rbj and Hurkyl. Two more questions - what does DFT stand for and how would i derive this? what happens if "s" is a vector?

Then the sum is over the whole vector space (change the normalization appropriately), and the exponent is a dot product.

(P.S. I think I might have made an assumption in that formula...)

rainbowings said:
Two more questions -

well it's not exactly the question(s) you started with. and it looks like you have three.

what does DFT stand for

that's kinda funny when i look at the title you gave the thread.

and how would i derive this?

it's in textbooks. it might be a little much to derive here. there's a hint below.

what happens if "s" is a vector?

i don't get where "s" comes from at all. using the language of Electrical Engineers (who are the folks i think that deal with the DFT the most), the most common expression of the DFT:

DFT:

$$X[k] = \sum_{n=0}^{N-1} x[n] e^{-j 2 \pi n k/N}$$

inverse DFT:

$$x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{+j 2 \pi n k/N}$$

[ i deleted some text because it made the math rendering break. ] ... essentially the DFT maps a periodic sequence of period N to another periodic sequence of period N.

you can define one equation arbitrarily and, given that, prove the other is true by noting

$$\sum_{n=0}^{N-1} e^{-j 2 \pi n (k-m)/N} = 0$$

when $k \ne m$ (both are integers) and

$$\sum_{n=0}^{N-1} e^{-j 2 \pi n (k-m)/N} = N$$

when $k = m$.

the rest is plug and chug.

r b-j

Last edited:
rbj said:
DFT:

$$X[k] = \sum_{n=0}^{N-1} x[n] e^{-j 2 \pi n k/N}$$

inverse DFT:

$$x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{+j 2 \pi n k/N}$$

because we use the symbol i for electic current, EEs use the symbol $j = \sqrt{-1}$ for the imaginary unit. n, k, and N are integers. usually $0 \le n \le N-1$ and $0 \le k \le N-1$ in the DFT, but it doesn't have to be since the DFT effectively periodically extends the data given it. essentially the DFT maps a periodic sequence of period N to another periodic sequence of period N.

you can define one equation arbitrarily and, given that, prove the other is true by noting

$$\sum_{n=0}^{N-1} e^{-j 2 \pi n (k-m)/N} = 0$$

when $k \ne m$ (both are integers) and

$$\sum_{n=0}^{N-1} e^{-j 2 \pi n (k-m)/N} = N$$

when $k = m$.

boy, i don't know what wrong with this thing, but i can't get the tex to come out right at all, so i am giving up trying. hey PF folks, your tex rendering is a little bit schitz.

r b-j

thanx r-b-j ... that helped. and yes, i thought of density functional theory but not the title of my own thread when i saw DFT - sometimes one does overlook the obvious!

rainbowings said:
thanx r b-j ... that helped. and yes, i thought of density functional theory but not the title of my own thread when i saw DFT - sometimes one does overlook the obvious!

did the hint help you derive the validity of the inverse transform (assuming the forward DFT definition)? you have to look at the 2nd post where i quote myself because the stupid tex rendering doesn't work right.

r b-j

## 1. What is a discrete Fourier transform?

A discrete Fourier transform (DFT) is a mathematical technique used to convert a signal from its original domain (often time or space) to a representation in the frequency domain. It decomposes a signal into its constituent frequencies, allowing for analysis and manipulation of the signal's frequency components.

## 2. How is a discrete Fourier transform different from a continuous Fourier transform?

The main difference between a discrete Fourier transform and a continuous Fourier transform is that the DFT is applied to a discrete, sampled signal, while the CFT is applied to a continuous signal. This means that the DFT can only analyze a finite number of data points, while the CFT can analyze an infinite number of data points.

## 3. What is the purpose of using a discrete Fourier transform?

The main purpose of using a discrete Fourier transform is to analyze the frequency components of a signal. This can be useful in a variety of fields, such as signal processing, image processing, and data analysis. It can also be used to solve differential equations and filter out unwanted noise from a signal.

## 4. How do I perform a discrete Fourier transform?

To perform a discrete Fourier transform, you can use a variety of software tools, such as MATLAB or Python. These programs have built-in functions that can compute the DFT for a given signal. Alternatively, you can also write your own code to calculate the DFT using mathematical formulas.

## 5. What are some common applications of discrete Fourier transforms?

Discrete Fourier transforms have many applications in various fields. They are commonly used in digital signal processing, image processing, and data analysis. They are also used in solving differential equations, filtering out noise from signals, and analyzing the frequency components of a signal. They are essential tools for understanding and manipulating signals in both scientific and engineering applications.

Replies
1
Views
830
• Calculus and Beyond Homework Help
Replies
3
Views
281
Replies
17
Views
2K
• Calculus
Replies
3
Views
1K
• Cosmology
Replies
4
Views
946
Replies
6
Views
1K
• Programming and Computer Science
Replies
2
Views
2K
• Quantum Physics
Replies
8
Views
7K
• Classical Physics
Replies
7
Views
2K
• Programming and Computer Science
Replies
26
Views
4K