Questions tagged [dft]

The Discrete Fourier Transform (DFT) is a mapping between a finite set of discrete points in a (primal) domain (time, space) and the dual frequency domain. DFT requires an input sequence which is discrete, such as a sampling from an analogue audio signal.

Filter by
Sorted by
Tagged with
119
votes
6answers
70k views

What does frequency domain denote in case of images?

I was just learning about the frequency domain in images. I can understand the frequency spectrum in case of waves. It denotes what frequencies are present in a wave. If we draw the frequency ...
80
votes
4answers
65k views

What is the difference between a Fourier transform and a cosine transform?

In speech recognition, the front end generally does signal processing to allow feature extraction from the audio stream. A discrete Fourier transform (DFT) is applied twice in this process. The first ...
39
votes
3answers
68k views

Why is the FFT “mirrored”?

If you do an FFT plot of a simple signal, like: t = 0:0.01:1 ; N = max(size(t)); x = 1 + sin( 2*pi*t ) ; y = abs( fft( x ) ) ; stem( N*t, y ) 1Hz sinusoid + DC ...
34
votes
9answers
13k views

Is there an algorithm for finding a frequency without DFT or FFT?

I was looking in the Android app store for a guitar tuner. I found a tuner app that claimed it was faster than other apps. It claimed it could find the frequency without using the DFT (I wish I still ...
20
votes
2answers
7k views

How can I compute a log-spaced power spectrum?

I would like to compute a power spectrum in which the frequencies are logarithmically spaced. In Welch's method there is a trade-off between the frequency resolution of the resulting power spectrum ...
19
votes
2answers
5k views

Frequency-domain zero padding - special treatment of X[N/2]

Suppose we wish to interpolate a periodic signal with an even number of samples (e.g. N=8) by zero-padding in the frequency domain. Let the DFT X=[A,B,C,D,E,F,G,H] ...
18
votes
3answers
8k views

Why are magnitudes normalised during synthesis (IDFT), not analysis (DFT)?

In most examples and FFT code that I've seen, the output (frequency magnitudes) of the forward DFT operation is scaled by N -- i.e. instead of giving you the magnitude of each frequency bin, it gives ...
16
votes
7answers
6k views

What are some of the differences between DFT and FFT that make FFT so fast?

I'm trying to understand FFTs, here's what I have so far: In order to find the magnitude of frequencies in a waveform, one must probe for them by multiplying the wave by the frequency they are ...
16
votes
2answers
1k views

DFT with geometrically-spaced bins?

The traditional Discrete Fourier Transform (DFT) and its cousin, the FFT, produce bins that are spaced equally. In other words, you get something like the first 10 hertz in the first bin, 10.1 through ...
15
votes
3answers
14k views

How to demodulate an AFSK signal in software

I am trying to transmit binary data from one device to another over an audio channel (speaker/mic). I use AFSK (Audio Frequency Shift Keying) as in Packet Radio, with $1200 \text{ Baud}$ and two ...
14
votes
3answers
17k views

When to use the DTFT vs the DFT (and their inverses) in analysis?

In many of my readings, whenever some author speaks about working in the frequency (transform) domain (of a digital signal), they often times take the DFT, or the DTFT, (and of course their ...
14
votes
3answers
30k views

Discrete Fourier Transform: What is the DC Term really?

I am currently toying around with the Discrete Fourier Transform (DFT) in Matlab to extract features from images. I like to fully understand the concepts that I use. I have read several explanations, ...
14
votes
3answers
637 views

How to efficiently calculate only the low coefficients of a zero-padded FFT

I've got an algorithm that zero pads a sequence to 4N, does an FFT, and only uses the lowest frequency N points out of the generated 4N. This seems like a lot of wasted work, any ideas how this can ...
14
votes
2answers
2k views

Could a DCT be used for an audio magnitude spectrum rather than DFT?

From what I understand, the DCT has half the bin size as a DFT of the same size N. The DFT also includes phase information, but often this is not needed when only the magnitude spectrum is desired. ...
13
votes
2answers
4k views

How does subpixel image shifting using DFT really work?

I am trying to assess the quality of several image interpolation methods for an application that involves generating subpixel-shifted images. I thought I could compare the results of a subpixel shift ...
12
votes
2answers
12k views

Why do we say that “zero-padding doesn't really increase frequency resolution”

Here is a sinusoid of frequency f = 236.4 Hz (it is 10 milliseconds long; it has N=441 points at sampling rate ...
12
votes
3answers
2k views

Why do I have frequency leakage in DFT after zero padding if frequency resolution is fine?

Let's consider this example: Fs=1000; Ns=500; t=0:1/Fs:(Ns-1)*1/Fs; f1=10; f2=400; x=5+5*sin(2*pi*f1*t)+2*sin(2*pi*f2*t); X=fft(x); In this scenario, frequency ...
12
votes
2answers
5k views

Z-transform of a downsampler

In this paper or multirate filtering, the author establishes the following mathematical relationship. Let $y_D$ be the output of a downsampler such that $$y_D[n] = x[Mn]$$ where $M$ is the ...
12
votes
2answers
12k views

When should I calculate PSD instead of plain FFT magnitude spectrum?

I have a thirty-second speech signal that was sampled at 44.1 kHz. Now, I would like to show what frequencies the speech has. However, I'm not sure what would be the best way to do that. It seems ...
12
votes
3answers
4k views

STFT and DWT (Wavelets)

STFT can be successfully used on sound data (with a .wav soundfile for example) in order to do some frequency-domain modifications (example : noise removal). With ...
12
votes
1answer
10k views

Real discrete Fourier transform

I am trying to understand the real DFT and the DFT and why the distinction exists. From what I know so far the DFT uses $e^{i2\pi kn/N}$ for basis vectors and gives the representation $$x[n]=\sum_{k=...
11
votes
7answers
12k views

Why Does the DFT Assume the Transformed Signal Is Periodic?

In many signal processing books, it is claimed that the DFT assumes the transformed signal to be periodic (and that this is the reason why spectral leakage for example may occur). Now, if you look at ...
11
votes
2answers
19k views

What is normalized frequency

I am working on DSP and finding difficulty to understand the term Normalized frequency often used with DFT & DTFT. What is normalized frequency in DSP ? and how it is different from analog ...
11
votes
3answers
2k views

Is the discrete Gaussian kernel an eigenfunction of the DFT?

So the Gaussian function is an eigenfunction of the Fourier transform because it transforms into itself, right? But this isn't true for the sampled Gaussian in the DFT because the tails of the ...
11
votes
4answers
2k views

DFT - Removing window effect in spectral domain with convolution

I was thinking about the DFT windowing subject and a thought came to my mind. A DFT will yield the spectrum of a signal convoluted with spectrum of the window used, therefore having a main lobes and ...
10
votes
2answers
3k views

Artifacts in FFT

I recently realized that FFT's aren't perfect. Meaning if I take a signal and then take it's FFT, and then do an inverse FFT, the resulting output isn't exactly the same as the input. Here's an image ...
10
votes
3answers
2k views

Implementation of Wikipedia Equation for the DFT

I was writing a simple fourier transform implementation and looked at the DFT equation on wikipedia for reference, when I noticed that I was doing something differently, and after thinking about it ...
10
votes
2answers
7k views

What are the statistics of the discrete Fourier transform of white Gaussian noise?

Consider a white Gaussian noise signal $ x \left( t \right) $. If we sample this signal and compute the discrete Fourier transform, what are the statistics of the resulting Fourier amplitudes?
10
votes
1answer
12k views

What is the meaning of the DFT? [duplicate]

Possible Duplicate: Real Discrete Fourier Transform What is the most lucid, intuitive explanation for the various FTs - CFT, DFT, DTFT and the Fourier Series? Discrete-time Fourier transform ...
10
votes
2answers
2k views

Log-Polar DFT Based Scale-Invariant Image Registration

I'm trying to do image registration using phase correlation as described in the Reddy Chatterji paper. In my case, the images may be scaled and translated relative to each other. The algorithm for ...
10
votes
2answers
550 views

Conditions for precoding matrix to preserve complex conjugate symmetry on DFT vector

Suppose there is a DFT vector $\mathbf{X}$ with length N, which presents complex conjugate symmetry around its middle point, i.e., $X(1) = X(N-1)^*$, $X(2) = X(N - 2)^*$ and so forth. $X(0)$ and $X(N/...
9
votes
3answers
20k views

Discrete Fourier transform symmetry

I was reading the chapter on discrete Fourier transforms in Lyons' book -- Understanding Digital Signal Processing -- and could not understand the last paragraph about symmetry. There’s an ...
9
votes
4answers
1k views

DFT-like transform using triangle waves instead of sin waves

We know that DFT (discrete Fourier transform) breaks down a signal into multiple frequencies of sine waves. Does there exist a transform that does the same thing, but for triangle waves? For my ...
9
votes
1answer
11k views

Symmetry of real and imaginary parts in FFT [duplicate]

...
9
votes
1answer
2k views

How can I decompose a signal into square waves?

I am dealing with signals that are a superposition of different square waves with different amplitudes and phases. Normally, one would decompose a signal into sine waves with help of the Fourier ...
8
votes
5answers
654 views

Estimators for improved spectral subtraction of noise

Real zero-mean Gaussian white noise, independent of a clean signal $x$ and of known variance is added to $x$ producing a noisy signal $y.$ Discrete Fourier transform (DFT) $Y$ of the noisy signal is ...
8
votes
3answers
2k views

FFT for line detection

I am trying use the FFT in a different way then most people ask about. I want to be able to take a picture of a graph with regular repeating vertical lines, and to process the image to determine how ...
7
votes
2answers
4k views

Why calculate negative frequencies of DFT?

This answer says that when calculating the DFT on a real valued signal, the (roughly) second half of the bins are the complex conjugates of the first half of the bins. Firstly I was curious if that is ...
7
votes
3answers
856 views

Spectral Leakage in layman's terms

I'm trying to understand the concept of spectral leakage for the DFT, without going deep to the mathematical intricacies (it's for practical purposes). I've read from the book "Introduction to Digital ...
7
votes
2answers
942 views

Coherent Sampling And The Distribution Of Quantization Noise

I have a question concerning the distribution of noise in the frequency domain in case of Coherent Sampling. I read up about Coherent Sampling and understood that in order for a frequency $f_{in}$ to ...
7
votes
2answers
2k views

Interpolation of magnitude of discrete Fourier transform (DFT)

For example for peak frequency finding, it seems valid to use band-limited interpolation methods on the complex DFT bins, or separately on their real and imaginary parts and to calculate the ...
7
votes
1answer
231 views

Deriving 2-D discrete Fourier transforms

I have a problem in DFT. It was one of my past-year exam papers questions. Question: Let $F(u,v)$ be the 2-D Fourier transform of a 2-D continuous function $f(x,y)$. Derive in terms of $F(:,:)$ ...
7
votes
2answers
1k views

DFT and multiplication/convolution equivalence

Is there a simple or potentially intuitive explanation for, with the DFT, vector multiplication in one domain being equivalent to circular convolution of the transforms of the vectors in the other ...
7
votes
1answer
2k views

Failed to implement Goertzel algorithm in Python

After some questioning on stackoverflow, I tried to implement a Goertzel algorithm in Python. But it doesn't work : https://gist.github.com/4128537 ...
6
votes
2answers
881 views

Which unit does the power spectrum of microphone output have?

If I sample sound with a microphone and find the absolute square of the (non-normalized) DFT, I get the discrete power spectrum (correct me if I'm wrong). Which unit does it have?
6
votes
3answers
24k views

Number of DFT (FFT) Points Required for a Specific Frequency Resolution for an Oversampled Signal

I have a bandpass signal centered at 2 MHz and bandwidth of 50 kHz (the signal frequency varies from 2 MHz - 25 kHz to 2 MHz + 25 kHz). This signal is being sampled at 10 MHz. I want a frequency ...
6
votes
2answers
10k views

Frequency resolution and timestep in DFT

I am learning DFT and I am not sure I understand it correctly. I am just going to write out the process of DFT and I am asking you to tell me if I am thinking the right way. Suppose we have a signal ...
6
votes
1answer
137 views

How does DCT decorrelate images?

I've read in multiple places that DCT decorrelates Toeplitz matrices and images usually have Toeplitz structure. Can you explain with an example how DCT decorrelates a Toeplitz matrix? Example for DFT:...
6
votes
3answers
1k views

Determining the mean of of a sampled signal (improvements to time averaging method)

I am sampling a signal at 1kHz, which is essentially a single-frequency sinusoid with a DC offset (and a small amount of noise). I don't know the precise frequency of the sinusoid (it is at most 10Hz),...
6
votes
2answers
320 views

How to separate the upwards-propagating from the downwards-propagating waves?

I've got a real 2D image of propagating waves in both directions. How can I separate this image into one with the upward-propagating waves and one with the downward-propagating ones? This example has ...

1
2 3 4 5
16