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
4
votes
1answer
214 views

A kind of Phase Retrieval problem

I know there are lots of papers proposing algorithms for the problem of reconstructing a signal from modulus of its Fourier Transform (so-called Phase Retrieval Problem). Also, recently it is studied ...
4
votes
1answer
639 views

Mapping the Value of a Sample in a 2D DFT to Cycles/Pixel

If I have an image and its 2-D DFT of that image, what is the mapping between the value of the DFT at (u,v), and the frequency in the spatial domain in the x and y components, in cycles/pixel? I want ...
4
votes
1answer
104 views

Amplitude Estimating Using a Windowed DFT

Let's say we want to estimate the amplitude A of a mono-frequent signal using a windowed DFT. The frequency of the signal is unknown, and the frequency resolution of the DFT is limited, thus it cannot ...
4
votes
2answers
812 views

Why is my DFT/FFT always 90° out of phase?

I'm doing an FFT using Python and Numpy on one machine, and C# on another. I'm using some dummy data that mimics how I'll eventually be gathering data from sensors in the C#/UWP application. The two ...
4
votes
1answer
7k 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 ...
4
votes
1answer
809 views

Why is the DFT used for spectrograms rather than the DCT?

Related to Could a DCT be used for an audio magnitude spectrum rather than DFT?, but more on the (audio) spectrogram side of things I've been reading about the DCT (such as from here) and it ...
4
votes
2answers
429 views

please give the reason why every notation for DFT is valid?

$X$ represents sample in frequency domain and $x$ represents samples in time domain. NOTATION 1 $ X[k] = \sum\limits_{n=0}^{N-1} x[n] \ e^{-j \frac{2\pi}{N} n k} $ $ x[n] = \frac{1}{N} \sum\limits_{...
4
votes
2answers
587 views

Is $O (N \log N)$ FFT speed the fastest we can ever attain?

I am wondering about whether or not there is a theoretical limit as to the speed at which we can compute a DFT. We all know that the FFT executes in $O (N \log N)$ time. However, is this a lower bound ...
4
votes
2answers
4k views

Discrete Fourier Transform for beginners

I want to make image processing programs which talk about homomorphic filter. But when I read some articles, I can't get it. Maybe can anyone help it. I very need this. Sorry about my english. I ...
4
votes
1answer
2k views

Goertzel algorithm: Relationship of magnitude

I've written a quick test app that uses the Goertzel algorithm to determine if a given frequency is present in the signal. This is to pick up DTMF tones and various other signals. The app appears to ...
4
votes
3answers
1k views

Phase measurement

I have a problem with phase measuring. I'm acquiring two signal with a USRP (complex signals) with a coherent generator and I want to measure the phase different between them.. One is at 150Mhz and ...
4
votes
4answers
524 views

Do you know this phenomenon in DFT?

Please let me ask you about a phenomenon in DFT. Below DFT program outputs excellent results for low sample rates, but for high results are very bad. Specifically: for sample rate 50 samples/sec, ...
4
votes
1answer
563 views

Would it be feasible to implement the Sliding DFT on a digital signal processor?

The Sliding DFT generates the spectrum for every input sample. Using the FFT, the spectrum is generated only after a certain number of samples (N) are obtained. It appears to me as though the cycles ...
3
votes
6answers
2k views

Definition of the DFT / FFT Bin Size

When reconstructing the frequency domain for an FFT, what is the most self-consistent way to do this -- i.e. how is it best to define the bin width, $\Delta f$? For example, previously I thought it a ...
3
votes
2answers
11k views

FFT for a single frequency

I was looking for a more efficient way of finding the magnitude and phase of a signal at a certain frequency without performing an FFT because it produces more information than I need and I came ...
3
votes
3answers
139 views

Inverse DFT: Is there a valid / intuitive interpretation of results for non-integral timestamps?

I implemented the plain DTF / inverse DFT algorithm in C++ in order to help me understand the method. As a sample input I considered f(x) = sin( x * PI / 5 ) and ...
3
votes
2answers
752 views

A system that perfoms Fourier Transform operation - is it an LTI system?

If a system takes input as the time domain signal and outputs the frequency domain signal, is such a system an LTI system? For if the input time domain signal can be represented as a linear ...
3
votes
3answers
718 views

Finding the time domain equation corresponding to a given DFT

I'm stuck with the following exercise while self-studying the Discrete Fourier Transform: Consider sampling exactly three cycles of a continuous $x(t)$ sinusoid resulting in an 8-point $x(n)$ time ...
3
votes
2answers
2k views

Online DFT Algorithm

I have a discrete audio stream $x$ that needs to be processed in real-time. Specifically, as the each new sample is received, I would like to compute a Fourier transform of the last $n$ samples of the ...
3
votes
2answers
282 views

Deriviation of the “Twiddle Sum” property

I can't seem to understand how to derive the "twiddle sum" property: $$\sum_{n=0}^{N-1}W_{N}^{kn}=N \ \delta[k\bmod N] $$ where $$ W_{N} \triangleq e^{\frac{j 2 \pi }{N}} $$ and $$ \delta[n] \...
3
votes
3answers
3k views

disadvantages of FFT, it can not extract enough frequencies without enough samples

Let's say sampling rate is $Fs = 44\mathtt{kHz}$, now I have $N = 2048$ samples, then I can get $N/2 + 1 = 1025$ frequencies. I'm confused by Matlab's FFT documentation that says the frequencies are ...
3
votes
4answers
399 views

How to derive the bin width / maximum frequency of DFT/STFT

The bin width is given by the $F_s / N$ and the maximum frequency is given by $F_s / 2$ where $F_s$ is the sample rate and $N$ is the number of samples of the DFT. Going between these is trivial, but ...
3
votes
2answers
11k views

Considering the FFT of Real & Complex Signals

I've been implementing a website to perform the FFT of various signals, real & complex. Examining the first example, a real signal $x[n] = 10 cos(2\pi\times4n)$, I got the following FFT: Which ...
3
votes
2answers
153 views

Multiplying the imaginary part of DFT with a linear ramp to get a derivative

I am trying to understand the statement in a relatively old publication from 1970s, when Fourier transforms found applications in chemical analysis. The author quotes the derivative theorem citing ...
3
votes
2answers
3k views

Link between DFS, DFT, DTFT

My understanding of DFT is as follows For a signal $x[n]$ of finite-length, the DFT is DFS of the periodic extension, $\tilde{x}[n]$, of that signal $x[n]$ and also another way to view DFT is that it’...
3
votes
2answers
1k views

What is the most precise frequency analysis spectrography algorythm?

Everyone uses Fast Fourier Transform, which is fast at the detriment of precision. The input audio has sample accuracy and the FFT has 1/64 sample accuracy. What algorithms can output high resolution ...
3
votes
1answer
3k views

Why is X(0) the DC component

Why exactly is X(0) the DC component of a signal? How is it equal to N times x(n)'s average value and why it is at X(0)?
3
votes
3answers
472 views

Non Uniform DFT Algorithm by Dutt & Rokhlin

I have implemented Dutt & Rokhlin's FFT algorithm [1] for non-equispaced data but for some reason I am getting very large errors ($E_2=0.04$ and $E_\infty=0.1$). I was wondering if there are any ...
3
votes
2answers
677 views

Duality Property for DFT

I was watching a youtube video for the duality property for continuous time Fourier transforms, which shows that if Fourier transform of $x(t)$ is $X(\omega)$ then Fourier transform of $X(t)$ is $2\pi ...
3
votes
2answers
13k views

Magic of twiddle factor in DFT

In DFT calculation following formula is used $$X[k] = \sum_{n=0}^{N-1} x[n] e^{-j2\pi\frac{kn}{N}}$$ where the Twiddle factor is known as complex root of unity, that is a complex number $W_N$ such ...
3
votes
2answers
2k views

Fast Hartley Transform Implementation in MATLAB

I want to implement Fast Hartley Transform (Specifically Discrete Hartley Transform) in a script file in MATLAB. Does anyone know have a reference implementation of this in MATLAB or another language ...
3
votes
2answers
6k views

DFT vs FFT: does odd number works for DFT only?

I am always confused between FFT and DFT. In both algorithm, it has been assumed that the signal is periodic (so my understanding is that, if you have a 20 sample point signal, and you do DFT or FFT, ...
3
votes
2answers
8k views

Hermitian symmetry in OFDM systems

I am trying to understand the usage of Hermitian symmetry in OFDM systems and have a couple of questions regarding this. What is the reason of using the Hermitian symmetry in OFDM? How can we arrange ...
3
votes
2answers
557 views

Getting an specific frequency component from sampled audio

I have a half second audio data sampled at $44.1\textrm{ kHz}$. If I FFT it I get frequency components in $2\textrm{ Hz}$ increments. Now suppose I want the component of an arbitrary frequency, like $...
3
votes
2answers
5k views

Result of conjugate symmetry property of DFT

I know one of the properties of DFT for real-valued time series is conjugate symmetry. But what does it imply? In the textbook it says that for a DFT of the length M, this makes M/2-1 spectral ...
3
votes
2answers
323 views

Basics of leakage phenomena in DFT and its approximation with sinc function

I am trying to understand leakage phenomena when using DFT. In the following I am reffering to Lyons: Understanding Digital Signal Processing (2nd ed.), p.69-71. Having real valued cosine with $N$ ...
3
votes
1answer
497 views

Why is this DFT of a real symmetric signal resulting in complex valued coefficients?

I am trying to understand exactly how sampling the DTFT to get the DFT works. The signal I'm trying to analyze is $x(n)$ seen below. $$x(n) = \delta(n\pm2) + 2\delta(n\pm1) + 3\delta(n)$$ Taking the ...
3
votes
2answers
800 views

Zero-padding the middle of a signal

I sample a signal at a certain frequency for a finite amount of time to get a sequence $$(x_n)_{n=1}^N = (x_1, x_2, ... , x_N)$$ with the intention of analyzing its power spectral density by ...
3
votes
2answers
785 views

Butterworth filtering behaving unexpectedly -MATLAB

I'm new to signal processing but I'm trying to understand how the Butterworth filter works. To do so, I did the following: I assumed a sampling frequency of 100Hz and wanted to attentuate everything ...
3
votes
1answer
2k 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 ...
3
votes
3answers
2k views

What Are the Alternatives to FFT for Computing High Resolution Tone Power Levels?

I have a system where there's a transceiver which transmits tones on specific frequencies (about 260kHz) and a receiver which is supposed to recognize those tones. The transmitted tones are of low ...
3
votes
1answer
431 views

Exercise Related to Frequency Resolution and SNR

I'm studying a book about DSP and trying to make exercises. Here is one I'm interested in: A scientist acquires 65,536 samples from an experiment at a sampling rate of 1 MHz. He knows that the signal ...
3
votes
1answer
180 views

The Proper Way to Do Sinc Downsampling (DFT Downsampling) 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 downsample it in the frequency domain (Sinc interpolation)?
3
votes
1answer
450 views

MATLAB FFT Amplitude

I am trying to understand FFT, DFT through Matlab and I am fairly inexperienced in all of these. I have a time vector t and a corresponding simple sine wave x = 0.25*sin(t). Now I would like to view ...
3
votes
2answers
904 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} ...
3
votes
1answer
992 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 ...
3
votes
2answers
138 views

How to do DFT of this signal

I am trying to get $X[k]$ when $x[n]$ is equal to $$x[n] = \cos\left(\tfrac{\pi}{4}n-\tfrac{\pi}{4}\right)$$ I'm using this equation: $$X[k] = \sum_{n=0}^{N-1}x[n]e^{-j \frac{2 \pi}{N}kn}$$ but ...
3
votes
2answers
450 views

Should the phase coefficients of the DFT of a real, even input signal all be zero?

The phase coefficients of a real, even input signals should all apparently be $0$ or a multiple of $\pi$. That's a property of the DFT I've learned about in the Audio Signal processing course on ...
3
votes
2answers
2k views

Frequency Analysis (DFT / FFT) of a Signal Without a Constant Sampling Frequency (Non Uniform Sampling in Time Domain)

I'm a stack exchange user for some time and now I'm registering to ask a simple question (I think!). I have a vibration signal with an amplitude and time (sampling frequency not constant) in a $...
3
votes
2answers
3k views

Difference between Fourier Transform and DFT? - Example

I have read many excellent answers to similar questions, but never one this specific. Here is another way to ask it. Why is the modulation transfer function (MTF) of $\textrm{rect}(x/5) = \textrm{...

1 2
3
4 5
17