What is Discrete fourier transform: Definition and 55 Discussions
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".
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 =...
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...
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...
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...
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...
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...
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...
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...
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...
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...
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...
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...
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...
(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...
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...
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...
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...
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...
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...
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...
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...
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...
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...
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...
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...
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...
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...
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...
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...
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...
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...
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...
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...
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...
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 ...
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...
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
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...
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...
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...
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...
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...
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...
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...
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...
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...
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] ]...
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...