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
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
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
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
2 votes
3 answers
6k views

DFT coefficients meaning?

What "are" they? What's a sensible way to interpret the coefficients (and what isn't)? To pose specifics: DFT coefficients describe the frequencies present in a signal They describe the ...
OverLordGoldDragon'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
2 votes
2 answers
828 views

What is "filter periodization"?

A library defines periodize_filter_fourier, which is an equi-spaced averaging formulated by $$ v_f[k] = \sum_{i=0}^{\text{n_periods}-1} h_f[i\cdot N + k], $$ where $v_f$ is periodization of $h_f$, $N=\...
OverLordGoldDragon's user avatar
2 votes
4 answers
2k views

Does Zero Padding Distort the Spectrum of a Signal?

It's said to "sample the DTFT", revealing what "DFT fails to see". And I fail to see how this sampling isn't distortion. The "spectrum" aims to provide the sinusoidal ...
OverLordGoldDragon's user avatar
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
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
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
5 votes
3 answers
7k views

How to calculate resolution of DFT with Hamming/Hann window?

The frequency resolution of a DFT with a rectangular window of size $N$ is given by $f_s/N$. However, when using other window functions like a Hamming or Hanning window the resolution gets worse. How ...
sigy's user avatar
  • 151
8 votes
1 answer
1k views

The Proper Way to Do Sinc Downsampling (DFT Downsampling) for Uniformly Sampled Discrete Signals with Finite Number of Samples

Given a discrete signal $ \left\{ x [ 0 ], x [ 1 ], \ldots, x [ N - 1 ] \right\} $ what would be the correct way to downsample it in the frequency domain (Sinc interpolation)?
David's user avatar
  • 144
6 votes
1 answer
645 views

Equivalence between "windowed Fourier transform" and STFT as convolutions/filtering

I've heard, that "windowed Fourier transform" is but one perspective on STFT, and that STFT is fundamentally convolutions of windowed complex sinusoids with the input, i.e. bandpass ...
OverLordGoldDragon's user avatar
4 votes
1 answer
2k views

PyWavelets CWT: normalization? Vs Scipy?

Related. The equation being implemented normalizes by sqrt(1 / scale): $$ C_{a, b} = \frac{1}{\sqrt{a}} \sum_k s(k)\left( \int_{-\infty}^{k+1} \overline{\psi \left(\...
OverLordGoldDragon's user avatar
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
4 votes
1 answer
2k views

What determines the accuracy of the phase result in a DFT bin?

What are the factors that affect the accuracy and precision for the phase that is given by the DFT? Just thinking medium-hard about this, it occurs to me that it must have something to do with the ...
Ben S.'s user avatar
  • 192
5 votes
3 answers
914 views

Absolute convergence of periodic sinc interpolation

An $N$-periodic complex discrete-time sequence $[x_0, \dots, x_{N-1}]$ can be resampled to an $M$-periodic sequence $[y_0, \dots, y_{M-1}]$ with $M>N$, using sinc interpolation: $$\begin{align}y_m ...
Olli Niemitalo's user avatar
4 votes
3 answers
2k views

2D Cross-Correlation using 1D FFT

I need to calculate cross correlation between 2 images which I read in 2 vectors, both of them uni-dimensional. As per my understanding I need to do the following operations: FFT(1D) on vector 1 and ...
user3253067's user avatar
1 vote
1 answer
407 views

Subsampling in frequency domain? Effect of sampling rate on spectrum?

Given a sequence $$ x[n] = [0, 1, 2, 3, 4, 5, 6, 7] $$ and its subsampling (by e.g. factor of 2) $$ x_\text{sub}[n] = [0, 2, 4, 6] $$ are $x_\text{sub}$ and $x$ related in spectrum? That is, given $X =...
OverLordGoldDragon's user avatar
3 votes
2 answers
2k views

Can anyone explain how dft works as a filter bank?

When we take the fft of input signal, the fft formulas say us to down convert the 2pik/N frequency content of input signal and sum one period interval. This gives us a just one complex number,not an ...
Ahmet Serdar's user avatar
2 votes
2 answers
905 views

DFT exercise in the book Understanding digital signal processing 3 Ed

I am trying to solve exercises from the book Understanding digital signal processing 3 Ed - Richard Lyons. I will repeat the question as it is in the book: 3.3 We want to calculate an N-point DFT ...
Henrique Luna's user avatar
1 vote
2 answers
480 views

DFT of a sine, closed form solution and insights

I seek to calculate, mathematically, the Discrete Fourier Transform, $$ \texttt{DFT}\{x\}[k] = \sum_{n=0}^{N - 1} x[n] e^{-j2\pi k n / N} $$ of any arbitrary real-valued sine: any frequency, duration, ...
OverLordGoldDragon's user avatar
0 votes
1 answer
2k views

Using fourier coefficients to reconstruct data in matlab

When doing a discrete fourier transform on some data using matlab's fft function, its output is a set of fourier coefficients but I was wondering how do I go about converting these into an and bn so I ...
Tom's user avatar
  • 1
3 votes
2 answers
1k views

Amplitude extraction using STFT

I'm trying to recover amplitude/magnitude from an audio stream. I'm using FFT to go from time domain to frequency. If I feed in a signal of known amplitude, the results I get from either windowing or ...
dizzy's user avatar
  • 253
3 votes
1 answer
762 views

Why is CWT implemented with FFT convolution?

Some implementations generate wavelets in frequency domain. Besides speed per FFT convolution, is there any reason? All wavelets will be sampled at same length - 100,000 samples even for those having ...
OverLordGoldDragon's user avatar
0 votes
1 answer
2k views

Specific Frequency Resolution

I have an audio signal SampleRate Fs: 44100 Hz TotalSamples: 94144 samples Duration t: 2.1348 s The frequency resolution is given by ...
Learthgz's user avatar
  • 132
9 votes
1 answer
3k views

Zero Padding of FFT

There are many question related to the zero padding a time domain signal to get more frequency bins after performing Fourier transform. As I understand this process is equivalent to trigonometric ...
Creator's user avatar
  • 88
9 votes
4 answers
651 views

Least Squares Solution Using the DFT vs Wiener-Hopf Equations

Least Squares channel estimation (or equalization) can be accomplished using the "Wiener Hopf Equations", or the Discrete Fourier Transform. Both appear to be least squares solutions. How do ...
Dan Boschen's user avatar
  • 51.9k
5 votes
2 answers
2k views

Amplitude after Fourier transform

How to obtain the correct amplitude after the numerical Fourier transform of a signal? Example: consider an exponential decaying wave $y(x)=e^{-x}\sin(100\pi x)$ with Fourier transform $y_f(x_f)$ ...
Frederic's user avatar
  • 173
2 votes
1 answer
716 views

The Proper Way to Do Sinc Upsampling (DFT Upsampling) for Uniformly Sampled Discrete Signals with Finite Number of Samples

Given a signal $ \left\{ x [ 0 ], x [ 1 ], ..., x [ N - 1 ] \right\} $ what would be the correct way to upsample it in the frequency domain (Sinc interpolation)? Note: Added as a request by the answer ...
David's user avatar
  • 144
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
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
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
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
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
1 vote
2 answers
676 views

Relationship between energy, power and sampling rate?

Excuse my silly question, but I think the energy increases as the sampling rate increases. In the time domain, the number of samples increases so the energy increases; In the frequency domain, ...
qian zhang's user avatar
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
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
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
9 votes
3 answers
8k views

Extract Sine Phase and Amplitude - accurate and robust method

This is a followup question to one I asked earlier based on the chat after the answer given by @hotpaw2, and cross-posted from stackoverflow since it was suggested it is more relevant to DSP. I have a ...
KBriggs's user avatar
  • 320
9 votes
2 answers
13k 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 ...
c0dehunter's user avatar
9 votes
1 answer
10k views

Non Uniform FFT / DFT with FFTW?

Can FFTW perform the FFT on data which is not uniform in time? I can't seem to find a straight-forward answer to this question anywhere online.
John's user avatar
  • 101
9 votes
3 answers
32k 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 ...
Vinod's user avatar
  • 654
7 votes
2 answers
3k 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 ...
Olli Niemitalo's user avatar
7 votes
1 answer
11k views

The necessity of null subcarrier in OFDM?

In looking to LTE specifications, with the subcarrier spacing $\Delta f = 15 \textrm{kHz}$, for bandwidth $10 \textrm{MHz}$, fft size $N_{fft} = 1024$ that needs a sampling rate $F_s \geq 1024 \times ...
AlexTP's user avatar
  • 6,595
4 votes
3 answers
200 views

Inverse DFT on the first half time domain ("DFT unpad property"?)

Assume to have c[] representing N DFT coefficients. The complex-valued signal of N samples in the time domain is computed by ...
diegor's user avatar
  • 181
3 votes
1 answer
3k views

Time scaling in DFT?

Let $x[n]$ be a real signal whose length $N$ is even. Let $y[n]=x[2n]+jx[2n+1]$ a signal whose length is $M=\frac{N}{2}$. $X[k]$ for $k=0,...,N-1$ and $Y[k]$ for $k=0,...,M-1$ are the respective DFTs ...
Tendero's user avatar
  • 5,020
3 votes
2 answers
2k views

Symmetry and periodicity of frequency-shifted discrete Fourier transform

The unitary discrete Fourier transform (DFT) of a sequence of numbers $x_n$ to $X_k,$ with integer $0 \le n < N$ and $0 \le k < N,$ can be defined as: $$X_k = \frac{1}{\sqrt{N}} \sum_{n=0}^{N-1} ...
Olli Niemitalo's user avatar
2 votes
1 answer
3k views

PyWavelets CWT implementation

I seek to understand PyWavelets' implementation of the Continuous Wavelet Transform, and how it compares to the more 'basic' version I've coded and provided here. In particular: How is integrated ...
OverLordGoldDragon's user avatar
2 votes
2 answers
3k views

How is wavelet time & frequency resolution computed?

Mallat gives analytic wavelet time & frequency widths/uncertainties as $$ \begin{align} \sigma_{ts}^2 &= \int_{-\infty}^{\infty} (t - u)^2 |\psi_{u, s}(t)|^2 dt = s^2 \sigma_t^...
OverLordGoldDragon's user avatar

1
2 3 4 5