Discrete fourier transform Definition and 55 Threads

In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex-valued function of frequency. The interval at which the DTFT is sampled is the reciprocal of the duration of the input sequence. An inverse DFT is a Fourier series, using the DTFT samples as coefficients of complex sinusoids at the corresponding DTFT frequencies. It has the same sample-values as the original input sequence. The DFT is therefore said to be a frequency domain representation of the original input sequence. If the original sequence spans all the non-zero values of a function, its DTFT is continuous (and periodic), and the DFT provides discrete samples of one cycle. If the original sequence is one cycle of a periodic function, the DFT provides all the non-zero values of one DTFT cycle.
The DFT is the most important discrete transform, used to perform Fourier analysis in many practical applications. In digital signal processing, the function is any quantity or signal that varies over time, such as the pressure of a sound wave, a radio signal, or daily temperature readings, sampled over a finite time interval (often defined by a window function). In image processing, the samples can be the values of pixels along a row or column of a raster image. The DFT is also used to efficiently solve partial differential equations, and to perform other operations such as convolutions or multiplying large integers.
Since it deals with a finite amount of data, it can be implemented in computers by numerical algorithms or even dedicated hardware. These implementations usually employ efficient fast Fourier transform (FFT) algorithms; so much so that the terms "FFT" and "DFT" are often used interchangeably. Prior to its current usage, the "FFT" initialism may have also been used for the ambiguous term "finite Fourier transform".

View More On Wikipedia.org
Recent contents Top users
  1. A

    I Question on invertibility in finite fields

    Hello all, I have here an excerpt from Wikipedia about the discrete Fourier transform: My question(s) are about the red underlined part. 1.) If ##n## divides ##p-1##, why does this imply that ##n## is invertible? 2.) Why does Wikipedia take the effort to write out the ##n## as ##n =...
  2. thereddy

    Discrete Fourier transform question

    Summary:: Discrete Fourier transform exam question Hi there, I'm not really sure how to do this question at all. Any help would be appreciated.
  3. T

    I Informational content in 2D discrete Fourier transform

    When you do a discrete Fourier transform (DFT) of a one-dimensional signal, I understand that the second half of the result is the complex conjugate of the first half. If you threw out the second half of the result, you're not actually losing any data and you would be able to recreate the entire...
  4. N

    I Why is the Signal from a Discrete Fourier Transform considered periodic?

    https://en.wikipedia.org/wiki/Discrete_Fourier_transform Why is the signal obtained from a DFT periodic? The time signal x[n] is finite and the number of sinusoids being correlated with it is finite, yet its said the frequency spectrum obtained after the DFT is periodic. I've also read the...
  5. J

    Testing my Discrete Fourier Transform program

    Homework Statement I've written a program that calculates the discrete Fourier transform of a set of data in FORTRAN 90. To test it, I need to "generate a perfect sine wave of given period, calculate the DFT and write both data and DFT out to file. Plot the result- does it look like what you...
  6. S

    How Does Increasing 'n' Affect the Cut-off Frequency 'k_cut' in DFT Analysis?

    Homework Statement I have this function ##f(\theta)=cos(n \ sin(\frac{\theta}{2})\pi)## and I need to take the discrete Fourier transform (DFT) numerically. I did so and I attached the result for ##\theta \in [0,2\pi)## and n =2,4,8,16,32, together with the function for a given n. I need to...
  7. S

    Python Discrete Fourier Transform in Python

    Homework Statement I need to calculate the derivative of a function using discrete Fourier transform (DFT). Below is a simplified version of my code (just for sin function) in python Homework Equations from __future__ import division import numpy as np from pylab import * pi = np.pi def...
  8. kaniello

    A Help with Discrete Sine Transform

    Hi, I am a neophyte in Discrete Fourier Transform and I am procticing with discrete Sine-transform. Specifically I want to calculate $$ \mathcal{F}_s \lbrace x \cdot e^{-x^2} \rbrace = \int\limits_{0}^{\infty } x \cdot e^{-x^2} \cdot \sin\left(x\right)\, \mathrm{d}x = \frac{1}{2} \pi^2 \omega...
  9. Telemachus

    Doubt about a discrete Fourier Transform

    Hi. I was checking the library for the discrete Fourier transform, fftw. So, I was using a functition ##f(x)=sin(kx)##, which when transformed must give a delta function in k. When I transform, and then transform back, I effectively recover the function, so I think I am doing something right...
  10. R

    Matching Discrete Fourier Transform (DFT) Pairs

    Homework Statement [/B] I am trying to match each of the following 28-point discrete-time signals with its DFT: Set #1: Set #2: Homework EquationsThe Attempt at a Solution Set #1 We have already established (here) that: ##Signal 1 \leftrightarrow DFT3## ##Signal 4 \leftrightarrow...
  11. R

    Discrete Fourier Transform (DFT) Matching

    Homework Statement Match each discrete-time signal with its DFT: Homework EquationsThe Attempt at a Solution I am mainly confused about Signal 7 and Signal 8. Signal 1 is the discrete equivalent to a constant function, therefore its DFT is an impulse (Dirac ##\delta##), so it corresponds...
  12. Jezza

    Domain of a discrete fourier transform

    Homework Statement The (computing) task at hand is to take a function f(x) defined at 2N discrete points, and use the Discrete Fourier Transform (DFT) to produce F(u), a plot of the amplitudes of the frequencies required to produce f(x). I have an array for each function holding the value of...
  13. Jezza

    How Does Slit Height Affect the Discrete Fourier Transform?

    Homework Statement [/B] This is a computing coursework problem. (There is a reasonably long theory preamble). Create a single slit centred on the origin (the centre of your array) width 10 and height 1. The array containing the imaginary parts will be zero and the array containing the real...
  14. K

    Different forms of the discrete Fourier Transform

    Hi I am trying to program excel to take the DFT of a signal, then bring it back to the time domain after a low pass filter. I have a code that can handle simple data for example t = [ 0, 1, 2, 3] y = [2, 3, -1, 4] So I think everything is great and so I plug in my real signal and things go off...
  15. D

    Discrete Fourier Transform of Sine Function

    (1) For a real function, g(x), the Fourier integral transform is defined by g(x) = \int_{0}^{\infty} A(\omega )cos(2\pi \omega x)d\omega - \int_{0}^{\infty} B(\omega )sin(2\pi \omega x)d\omega where A(\omega ) = 2 \int_{-\infty}^{\infty} g(x)cos(2\pi \omega x)dx and B(\omega ) = 2...
  16. Legend101

    Fourier transform of a shifted and time-reversed sign

    Homework Statement given a continuous-time signal g(t) . Its Fourier transform is G(f) ( see definition in picture / "i" is the imaginary number) . It is required to find the Fourier transform of the shifted-time-reversed signal g(a-t) where a is a real constant . That is , find the Fourier...
  17. electronic engineer

    Calculating FFT for discrete values

    Homework Statement We have a set of values: f(n)=f(0,1,2)=(1,3,2) so f(0)=1, f(1)=3, f(2)=2, where n=0,1,2the number of values N=3 The question is to calculate the FFT of this signal, the Fourier spectrum the power spectrum and phase spectrum. I'm not sure concerning FFT. And also about...
  18. K

    Fourier transformation on discrete function

    Hi there, I am reading a material on the application of Fourier transformation in physics. One application is to transform the position-dependent function to k-dependent function, i.e.## F(k) = FFT[f(x)]## We know that the in physics, the wavenumber could be written in momentum as...
  19. M

    Discrete Fourier Transforms of Signals

    Homework Statement Homework EquationsThe Attempt at a Solution I'd like to see if I have the right line of thinking in my solutions: a. The sampling frequency should be such that no aliasing or folding occurs, so it should be twice the frequency of the original signal. $$x(t) = -17...
  20. W

    Sampling a signal and do the discrete Fourier transform

    When I sample a certain digital signal with increasing sampling frequency, the fast Fourier transform of the sampled signal becomes finer and finer. (the image follows) Previously I thought higher sampling frequency makes the sampled signal more similar to the original one, so the Fourier...
  21. K

    Discrete fourier transform data of 2 different sampling frequencies

    Hi All, I have a problem I've been thinking about for a while, but I haven't come up with a really satisfactory solution: I want to do a discrete Fourier transform on data that has been sampled at 2 different sampling frequencies. I've attached a picture of what my data will look like...
  22. E

    Is the Discrete Fourier Transform a Unitary Transformation?

    I'm trying to prove that the discrete form of the Fourier transform is a unitary transformation So I used the equation for the discrete Fourier transform: ##y_k=\frac{1}{\sqrt{N}}\sum^{N-1}_{j=0}{x_je^{i2\pi\frac{jk}{N}}}## and I put the Fourier transform into a N-1 by N-1 matrix form...
  23. Z

    Analogue Frequency of Band-limited signal (Discrete Fourier Transform)

    Hi, I have the following question: A signal x(t) which is band-limited to 10kHz is sampled with a sampling frequency of 20kHz. The DFT (Discrete Fourier Transform) of N= 1000 samples of x(n) is then computed. To what analogue frequency does the index k=120 respond to? I'm trying to...
  24. B

    Discrete Fourier Transform (DFT) Help

    I took f(t) = SIN(10*t) +SIN(5*t) and got this f(0) = 0 f(1) = -1.5 f(2) = 0.4 f(3) = -0.3 now I tried to do the DFT Fs = 4Hz N = 4 samples 3 f[r] = Ʃ x[k]ε^(-j(2πkr/4) k=0 f[r] = 0 -1.5ε^(-j(2πr/4) + 0.4ε^(-j(2π(2)r/4) -0.3ε^(-j(2π(3)r/4) f[0] = 0 - 1.5 +...
  25. Z

    Interpolating Data with the Discrete Fourier Transform

    Hello everyone: I have some question using the FFT in MATLAB for data interpolating. I don't know what the relation between the normal Fourier series and the real, image number. For example, given a set of measurement data, I can use the curve fitting toolbox to fit a curve. The general...
  26. B

    Circulant linear systems and the Discrete Fourier Transform

    Homework Statement Hi, this is not a homework question per se, but something I'm wondering. Let C be a circulant n x n matrix, let x, b, be vectors such that C x = b. We would like to find a solution x. One way is to use the DFT: According to section 5, In Linear Equations, in the wikipedia...
  27. U

    Explanation of the discrete fourier transform

    Hi all, I'm a complete novice when it comes to describing images in frequency space and i understand that it is a way of representing images as being composed of a series of sinusoids. So a horizontal striped pattern with a single spatial frequency would have a magnitude image in frequency...
  28. L

    Two dimensional discrete Fourier transform units

    Homework Statement I have am doing a two dimensional discrete Fourier transform on an image (using MATLAB). What are the units associated with each pixel of the image in the frequency domain? Homework Equations The Attempt at a Solution I thought that the frequency should be...
  29. K

    Discrete Fourier Transform question

    Hi, I am learning Fourier transformation by my own. I am reading a book "Fourier Transformation" by R. Bracewell. In chapter 11, in examples of discrete Fourier transforms, it gives for N =2, {1 0} transforms to 1/2{1 1}. I can do this in MATLAB but I can't figure it out how to do it by hand...
  30. M

    Discrete Fourier Transform and Hand-waving

    Hi all, I'm reading the following PDF about the DFT: http://www.analog.com/static/imported-files/tech_docs/dsp_book_Ch8.pdf Please see pages 152-153. So the inverse DFT (frequency to space, x[i] = ...) is given on page 152. Then it is claimed that the amplitudes for the space-domain...
  31. M

    Discrete Fourier Transform on even function

    The DCT of an even function is comprised of just cosine coefficients, correct? I'm playing around in MATLAB and I came up with a simple even function 1.0000 0.7500 0.5000 0.2500 0 0.2500 0.5000 0.7500 1.0000 0.7500 0.5000 0.2500 0 0 0 0...
  32. L

    Discrete Fourier transform mirrored?

    Why does a discrete Fourier transform seems to produce two peaks for a single sine wave? It seems to be the case that the spectrum ends halfway through the transform and then reappears as a mirror image; why is that? And what is the use of this mirror image? If I want to recover the frequency...
  33. J

    Why complex discrete Fourier transform?

    I've been trying to figure out why it's standard to use complex discrete Fourier transforms instead of just the real version. It's discussed a bit here. http://dsp.stackexchange.com/questions/1406/real-discrete-fourier-transform As far as I can tell there's a hypothetical efficiency...
  34. G

    Discrete Fourier transform in k and 1/k

    Say you have some function that is periodic in a parameter k. The discrete Fourier transform from a sampling may be found in the usual way, giving the frequency spectrum in k. But what if I want to find the frequency spectrum in 1/k ? I'm not really sure what this is called, and so I've had a...
  35. V

    Discrete Fourier Transform with different period

    Hi all, I have a seemingly simple problem which is I'd like to efficiently evaluate the following sums: Y_k = \sum_{j=0}^{n-1} c_j e^{\frac{i j k \alpha}{n}} for k=0...n-1. Now if \alpha = 2\pi, then this reduces to a standard DFT and I can use a standard FFT library to compute the...
  36. C

    Ambiguity about roots of unity in discrete Fourier transform

    Hi everyone, I have a question on the discrete Fourier transform. I already know its a change of basis operator on C^N between the usual orthonormal basis and the "Fourier" basis, which are vectors consisting of powers of the N roots of unity. But if i recall correctly from complex...
  37. R

    Discrete Fourier Transform of Even Function

    I'm confused about the DFT of the data, fn = cos(3\pin/N) for n=0,1,...,N. It is definitely an even function, and I read that the Fourier coefficients of an even function is real. But when I take the FFT of this in Matlab I get complex numbers, not real numbers. What am I missing? Thanks ...
  38. S

    MATLAB Discrete Fourier Transform in MATLAB

    Hello all, first time here and I have really silly problem... I am working on something in MATLAB, in which I have to make discrete Fourier transform of gaussian distributed variable. i.e. array of numbers which are taken from f(x)~exp(-x^2). I know that when you Fourier transform it with...
  39. C

    Mathematica Discrete Fourier Transform of NDsolve in Mathematica?

    I want to do a discrete Fourier transform of the solution I have found using NDSolve, however, because the NDSolve creates Interpolating functions rather than numbers I can't do this. Any help is appreciated. I've attatched the file I'm working with. Catrin
  40. B

    Discrete Fourier transform of sampled continuous signal

    Homework Statement Let a system that converts a continuos-time signal to a discrete-time signal. The input x(t) is periodic with period of 0.1 second. The Fourier series coefficients of x(t) are X_k = \displaystyle\left(\frac{1}{2}\right)^{|k|}. The ideal lowpass filter H(\omega) is equal to 0...
  41. F

    Signal Discrete Fourier Transform

    Hi guys, I'm a bit embarassed that my first post here is in this section, but I'm taking a Elec. Eng. course abroad, which is out of my confort zone (i'm majoring in automotive eng.) and I'm trying to solve a few model problems. This one in particular deals with the DFT. Anyway:Homework...
  42. W

    Scaling the output of Discrete Fourier Transform

    I have a feeling this question has a very simple answer, yet I cannot find it anywhere online. Let's say that I have a data set that represents and evenly-spaced sample of a function, taken uniformly over the interval (a,b) \qquad a,b \in \mathbb{Z} I perform a discrete Fourier transform to...
  43. Z

    Is the Data Set Real or Complex Based on DFT Output?

    Homework Statement A 8-point data set is transformed with a DFT and the resulting array has values 1,2,3,4,5,6,7,8 was the data set real or complex? why? Homework Equations The Attempt at a Solution kind of confused with this question all i know is the discrete Fourier...
  44. 4

    Discrete Fourier Transform: How does independent varialbe spacing change?

    Hey guys, I was imagining that I have a sine function: y = sin(x) where x represents a distance in meters for instance. Now let us say that I sample the function at x = 0,1,2,3...,10 (meters) producing a list of values: {sin(1), sin(2), sin(3),...,sin(10)} = {0.000, 0.841, 0.909, 0.141...
  45. R

    Matlab graphing using discrete fourier transform

    Homework Statement Compute the discrete Fourier transform of the ecg signal, graph the amplitude and phase response. The problem gives data in the form of a ecg.mat file. Contained are two double variables: voltage data for the ecg and a time vector for the ecg. both the voltage and time...
  46. C

    Continuous and Discrete Fourier Transform at the Nyquist frequency

    Hi there, A quick question concerning the FFT. Let's say I explicitly know a 2D function \tilde{f}\left(\xi_1,\xi_2 \right) in the frequency domain. If I want to know the values of f\left(x_1,x_2 \right) in the time domain at some specific times, I can calculate \tilde{f} at N_jdiscrete...
  47. N

    Mathematica Mathematica: Discrete Fourier Transform

    Hi all I have a function F, which depends on a discrete variable x, and I need to Fourier Transform it. I have put all the values of F in a table. Then I have used the command "Fourier" on the table, which - according to http://reference.wolfram.com/mathematica/ref/Fourier.html - results...
  48. C

    Discrete Fourier Transform Frequency

    Hi everybody, I'm in the process of writing a discrete Fourier transform program using the algorithm on the DFT wikipedia page. When I throw in functions that I know the frequency domain signal of it gives the predicted shape but I have absolutely know idea how to generate a frequency axis...
  49. D

    MATLAB Calculating Discrete Fourier Transform Coefficient with Matlab

    I've been asked to write a function (.m file) in Matlab to calculate the discrete Fourier transform coefficient for an arbitrary function x. So far this is what I've done: function a = mydft(x,N) %MYDFT Calculates the discrete Fourier transform %usage: %[a]=mydft(x) %x=[ x[0] x[1] ... x[N-1] ]...
  50. D

    Help with digital signals (discrete fourier transform)

    I've been working on this problem for around three hours, and I'm getting nowhere... I think it may be that I don't have even the most basic grasp of the material to even get a decent start on the problem, but hopefully someone here will be able to help me... Homework Statement Calculate...
Back
Top