Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

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
131 votes
5 answers
88k 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 ...
Abid Rahman K's user avatar
117 votes
4 answers
53k views

Why is it a bad idea to filter by zeroing out FFT bins?

It's very easy to filter a signal by performing an FFT on it, zeroing out some of the bins, and then performing an IFFT. For instance: ...
endolith's user avatar
  • 15.8k
107 votes
4 answers
95k 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 ...
Nate Glenn's user avatar
  • 1,187
101 votes
6 answers
211k views

Why should I zero-pad a signal before taking the discrete Fourier transform?

In an answer to a previous question, it was stated that one should zero-pad the input signals (add zeros to the end so that at least half of the wave is "blank") What's the reason for this?...
Jonas's user avatar
  • 3,081
50 votes
3 answers
102k 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 ...
bobobobo's user avatar
  • 945
43 votes
5 answers
169k views

Difference between Discrete Time Fourier Transform and Discrete Fourier Transform

I have read many articles about DTFT and DFT but am not able to discern the difference between the two except for a few visible things like DTFT goes till infinity while DFT is only till $N-1$. Can ...
BaluRaman's user avatar
  • 689
36 votes
9 answers
14k 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 ...
Slamice's user avatar
  • 463
23 votes
2 answers
11k 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 ...
nibot's user avatar
  • 3,803
21 votes
3 answers
10k 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 ...
bryhoyt's user avatar
  • 1,433
21 votes
4 answers
51k 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, ...
Domi's user avatar
  • 323
20 votes
9 answers
7k views

Is there an algorithm to compute the phase for a single frequecy?

If you have a function $f(t)=A \cdot \sin(\omega t+\phi)$, and reference sin wave $\sin(\omega x)$ what would be a fast algorithm to compute $\phi$? I was looking at Goertzel algorithm, but it doesn'...
SamFisher83's user avatar
20 votes
3 answers
7k 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] ...
finnw's user avatar
  • 401
19 votes
2 answers
19k 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 ...
Basj's user avatar
  • 1,277
18 votes
7 answers
7k 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 ...
Seph Reed's user avatar
  • 305
18 votes
3 answers
19k 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 ...
TheGrapeBeyond's user avatar
18 votes
2 answers
2k 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 ...
Brannon's user avatar
  • 305
17 votes
8 answers
22k 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 ...
user10839's user avatar
  • 171
17 votes
2 answers
3k 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. ...
Jacob's user avatar
  • 361
16 votes
3 answers
34k views

What is normalized frequency

I am learning DSP and finding difficulty understanding the term Normalized frequency often used with DFT & DTFT. What does normalized frequency mean in DSP and how it is different from analog ...
user6363's user avatar
  • 333
16 votes
3 answers
16k 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=...
user782220's user avatar
15 votes
3 answers
16k 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 ...
Patrick Oscity's user avatar
15 votes
3 answers
715 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 ...
Mark Borgerding's user avatar
14 votes
7 answers
3k views

Why does a longer observation time improve DFT resolution, but repeating a signal does not?

As was proven here: https://math.stackexchange.com/questions/228614/why-doesnt-repeating-a-signal-give-rise-to-a-finer-resolution-of-dft-fft repeating a certain sequence does not improve DFT frequency ...
Ariane's user avatar
  • 141
14 votes
4 answers
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 ...
endolith's user avatar
  • 15.8k
14 votes
7 answers
12k views

The difference between DFT and DFS

In the literature, I've found that DFS and DFT are one and the same. If they are one and the same why to use two different names for them? If there is really a difference what is it and what is the ...
phanitej's user avatar
  • 450
14 votes
2 answers
15k 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 ...
spede's user avatar
  • 143
14 votes
3 answers
5k 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 ...
Basj's user avatar
  • 1,277
13 votes
3 answers
3k 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 ...
user3616359's user avatar
13 votes
2 answers
18k 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?
DanielSank's user avatar
  • 1,056
13 votes
2 answers
5k 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 ...
neuviemeporte's user avatar
12 votes
5 answers
22k views

How to get Fourier coefficients to draw any shape using DFT?

I'm teaching myself about Fourier Series and the DFT and trying to draw a stylised $\pi$ symbol by fourier epicycles as detailed by Mathologer on youtube (from 18:39 onwards), and the excellent ...
Chris's user avatar
  • 123
12 votes
3 answers
29k 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 ...
someguy's user avatar
  • 317
12 votes
2 answers
8k 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 ...
Phonon's user avatar
  • 5,216
12 votes
4 answers
3k 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 ...
Pier-Yves Lessard's user avatar
11 votes
2 answers
4k 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 ...
Kitchi's user avatar
  • 721
11 votes
2 answers
590 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/...
igorauad's user avatar
  • 299
10 votes
6 answers
2k 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 ...
hassan789's user avatar
  • 202
10 votes
3 answers
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 ...
Nimitz14's user avatar
  • 199
10 votes
1 answer
14k views

Symmetry of real and imaginary parts in FFT [duplicate]

...
gpuguy's user avatar
  • 1,370
10 votes
3 answers
1k views

Why doesnt DFT Padding cause sinc like features

I'm new to the land of DSP so any incorrect terms please let me know. It seems padding the time domain signal can make the magnitude spectrum look 'nicer', the fact it doesn't gain any more useful ...
George kirby's user avatar
10 votes
1 answer
11k views

What happens when N increases in N-point DFT [duplicate]

I am curious about DFT, and I wrote a simple MATLAB code to test what happens when $N$ increases. I took a rectangular signal with length $L=15$, an then found th DFT of 16, 32 and 64 points. I looked ...
Canberk's user avatar
  • 161
10 votes
4 answers
12k views

What is Frequency Resolution?

Im trying to tackle the following problem while still not having a firm idea on what "frequency resolution" means : Suppose we sample a continuous time signal with sampling period Ts = 1/2000, and ...
Αποστολης Καρασμανογλου's user avatar
10 votes
3 answers
2k views

DFT of discrete signals, why do we only analyze frequency bins equal to number of input samples?

If we have a signal $x[n]$ such that we have $N$ samples i.e. $n=0, \ldots, N-1$, then when we analyze the DFT $X[k]$ we only analyze for $k=0,\dots,N-1$ as well. Why is the range of $k$ tied to the ...
GrowinMan's user avatar
  • 351
10 votes
2 answers
3k views

FFT vs DFT Run Time Comparison (Complexity Analysis) in MATLAB

So we were given an assignment to plot the time taken by the FFT algorithm by MATLAB and a DFT algorithm written by me in MATLAB.G The expected output should have been the DFT algorithm following the ...
Abhinav Jain's user avatar
10 votes
1 answer
13k 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 ...
John Smith's user avatar
10 votes
1 answer
3k views

Matrix form of 2D-DFT for a vectorized image

I want to apply 2d DFT to a N by N image. However, image is vectorized such that it is NxN by 1. How can i find the matrix form of 2d DFT such that resulting vector from multiplication is the ...
strahd's user avatar
  • 169
10 votes
1 answer
4k 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 ...
Sentry's user avatar
  • 203
10 votes
2 answers
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 ...
Drew Cummins's user avatar
9 votes
3 answers
1k views

Why do sinusoids have DFT magnitudes of N / 2 while we typically normalize by N?

I'm wondering why evaluating a sinusoid that matches one of the frequencies of the DFT basis functions has a magnitude of $N / 2$. Using this definition of the Discrete Fourier transform, it looks ...
bluenote10's user avatar
9 votes
3 answers
6k 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 ...
Alan Wolfe's user avatar

1
2 3 4 5
23