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
125 votes
5 answers
80k 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 ...
user avatar
100 votes
4 answers
82k 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 ...
user avatar
  • 1,117
48 votes
3 answers
87k 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 ...
user avatar
  • 905
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 ...
user avatar
  • 463
23 votes
2 answers
10k 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 ...
user avatar
  • 3,603
20 votes
3 answers
6k 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] ...
user avatar
  • 391
19 votes
3 answers
9k 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 ...
user avatar
  • 1,383
18 votes
8 answers
17k 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 ...
user avatar
  • 181
18 votes
4 answers
42k 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, ...
user avatar
  • 293
17 votes
7 answers
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 ...
user avatar
  • 275
17 votes
2 answers
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 ...
user avatar
  • 295
16 votes
2 answers
16k 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 ...
user avatar
  • 1,217
16 votes
2 answers
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. ...
user avatar
  • 351
15 votes
3 answers
18k 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 ...
user avatar
15 votes
2 answers
27k 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 ...
user avatar
  • 323
15 votes
3 answers
15k 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 ...
user avatar
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 ...
user avatar
  • 1,217
14 votes
2 answers
13k 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=...
user avatar
14 votes
3 answers
663 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 ...
user avatar
13 votes
7 answers
2k 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 ...
user avatar
  • 131
13 votes
2 answers
13k 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?
user avatar
  • 1,016
13 votes
3 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 ...
user avatar
  • 15k
13 votes
2 answers
14k 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 ...
user avatar
  • 133
13 votes
2 answers
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 ...
user avatar
12 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 ...
user avatar
12 votes
2 answers
6k 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 ...
user avatar
  • 4,958
12 votes
4 answers
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 ...
user avatar
11 votes
3 answers
25k 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 ...
user avatar
  • 307
11 votes
2 answers
2k 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 ...
user avatar
10 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 ...
user avatar
  • 701
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 ...
user avatar
  • 199
10 votes
3 answers
29k 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 ...
user avatar
  • 634
10 votes
1 answer
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 ...
user avatar
10 votes
1 answer
3k 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 ...
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 ...
user avatar
10 votes
2 answers
566 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/...
user avatar
  • 279
9 votes
5 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 ...
user avatar
  • 192
9 votes
1 answer
13k views

Symmetry of real and imaginary parts in FFT [duplicate]

...
user avatar
  • 1,330
9 votes
1 answer
2k 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 ...
user avatar
  • 601
9 votes
1 answer
527 views

Determining Power of White Noise Component of an Incomplete Time Signal

I want to determine the power of the noise component of a time dependend signal x(t) (similar to picture below) With constant sampling rate I use Parceval's Therorem and calculate the standard ...
user avatar
  • 470
8 votes
3 answers
5k 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 ...
user avatar
8 votes
5 answers
16k 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 ...
user avatar
  • 83
8 votes
4 answers
5k 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 ...
user avatar
8 votes
5 answers
798 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 ...
user avatar
8 votes
2 answers
2k views

Difference Between Convolution and Multiplication of Frequency Response and Frequency Spectrum

Suppose I have impulse response like [1/25,2/25,3/25,4/25,5/25,4/25,3/25,2/25,1/25]. I did convolution with 600 samples of test signal (it seems that I did some filtering). Then I calculated the ...
user avatar
  • 293
8 votes
3 answers
1k 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 ...
user avatar
8 votes
1 answer
9k 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 ...
user avatar
  • 141
8 votes
2 answers
12k 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 ...
user avatar
8 votes
4 answers
2k views

The Number of Sine and Cosine Waves in an $ N $ Point DFT

This is bound to be an embarrassingly simple question, but here it goes... I was reading the chapter on discrete Fourier transforms (DFT) of this really didactic online book, The Scientist and ...
user avatar
8 votes
3 answers
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 ...
user avatar

1
2 3 4 5
19