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

Extracting Peak Frequencies Using FFT vs. Time Domain Peak Finding

I am trying to compare two processing algorithms that I believe should be producing very similar results. I am processing acceleration signals over the course of the day and we expect to see a ...
3
votes
4answers
207 views

Estimate Filter Coefficients from the Result of Linear Convolution with a Known Signal

If I have samples of input say x(1:500) and it passes through FIR filter with 9 taps and some unknown coefficients. The output y(1:508) is also known. The aim is to estimate the filter response in ...
3
votes
2answers
100 views

How can I take a fixed number of bins after N-point DFT when N is unknown?

I am working with machine learning for time series classification. I am trying to extract features from the amplitude spectrum. My current concern is that I cannot tell the length of the signal in ...
3
votes
1answer
1k views

How to “scale” the FFT when using it to calculate discrete convolution?

As you probably know, the discrete convolution $ H = F \ast G $ of some $ F \left[ x \right] $ and some $ G \left[ x \right] $ can be calculated using the Fast Fourier Transform (FFT). To do this, ...
3
votes
3answers
1k views

Analysis frequency of the DFT?

So I'm reading Richard G. Lyons' book "Understanding Digital Signal Processing" and I've just started to make my way through the DFT chapter. While most of his examples and explanations make sense, I ...
3
votes
1answer
146 views

Independence of Noise at Each DFT Output

My math may be a little rusty, so I would like confirmation or correction or my calculations here. Given white noise samples, $x_i$, which are IID and zero-mean, and variance $\sigma^2_x$. I want to ...
3
votes
3answers
360 views

DFT for something similar to convolution

I have the following problem: Let $x$, $y$ be finite real valued sequences defined on $0, \ldots, N-1$ and let $g$ be a non negative integer. Define: $$z_n=\sum_{k=0}^n x_{n-k}y_k, \quad \text{also ...
3
votes
1answer
184 views

What is the optimal adaptive grid for calculating a DFT using a fixed number of sampling points?

I'm currently facing the following problem: I want to approximate the Fourier transform $F(\omega)$ of a (let's say, $L^2(\mathbb R)$) function $f(x)$ by calculating the discrete Fourier transform, ...
3
votes
1answer
1k views

Chirp z algorithm clarification

I am attempting to implement a chirp z algorithm to handle random sized DFTs, and I can not seem to obtain any meaningful results. I have gone over several write ups and "think" I have a handle on ...
3
votes
1answer
275 views

Why is this recursive DFT algorithm not equivalent to this iterative method?

Edit 1/30 - Taking @Fat32's edits into account, it seems like there is still an issue with the scale of the frequency axis. While version 2 correctly identifies the response at 1 HZ, version 1 seems ...
3
votes
2answers
135 views

Use samples of Fourier transform as DFT?

Consider the LTI system given by: $H(z) = 1 - \frac{1}{2}z^{-1}+\frac{3}{4}z^{-2}$ Let $x[n] = (\frac{1}{2})^nu[n]$ be the input to the system. We want to find the output for $n = 0,1,...,N_a$, using ...
3
votes
1answer
104 views

Restriction of Fourier Transform

I am currently reading Candes et. al.'s 2006 paper[1] on recovery of sparse signals from incomplete frequency samples. I am having trouble figuring out what is the form of the Fourier transform ...
3
votes
2answers
250 views

Can FFT information be used to obtain the DTFT?

If $x[n] = \left\{\frac 14, \frac 14, \frac 14, \frac 14\right\}$ and the resulting DTFT is $$ \frac 12\exp\left(\frac 32\omega\right)\left(\cos\left(\frac 32\omega\right)+\cos\left(\frac 12\omega\...
3
votes
3answers
457 views

What is the physical significance of the Fourier coefficients in the DFT of audio signals and how can they be best displayed in a spectrogram?

I am trying to display the spectrogram of an input audio signal (a newcomer to all things spectral here). The amplitudes of my audio signal can be assumed to be normalized between -1 and +1. Suppose ...
3
votes
1answer
191 views

Accuracy of IFFT(FFT(X)) unit transformation

I want to use FFTs to do seriously accurate interpolation on band-limited data. To do that, I need to get a handle on the fundamental accuracy of the FFT() and IFFT() algorithms available. My idea ...
3
votes
2answers
1k views

Using Goertzel Algorithm in under-sampling

I plan to calculate a signal's phase using Goertzel Algorithm. I have 2 signals coming to microcontroller's ADC. Need to measure the phase difference between them. Signals are 15MHz sinusoids. Sample ...
3
votes
1answer
238 views

Where does homomorphic filtering stand in regards to DSP applications?

I am studying my Oppenheim and Shaffer book, (New Edition), and the last chapter deals with something called homomorphic filtering. I have read the wiki and some other websites about it, but they do ...
3
votes
2answers
1k views

Phase Correlation and Negative Shifts

I am implementing phase correlation algorithm to determine shift between two images. It generally works, but I am not sure how to interpret the resulting shift. Pseudocode: ...
3
votes
1answer
6k views

How to calculate the power of a discrete signal? / Clarification on PSD estimates

I want to calculate the channel power $ P_\mathrm{x}$ of a given discrete and complex signal $x[n]$ (with a length of N) in a given bandwidth $B$. I'm aware, that I could probably apply a sharp ...
3
votes
1answer
49 views

Can cross-c.(x,y) be positive if signals x and y do not share frequencies?

The question is if the cross-correlation of two signals $x$ and $y$ can be non-zero even if $x$ and $y$ do not share frequencies. My approach is the following: The cross-correlation $\rho_{xy}\left(\...
3
votes
0answers
8k views

Horizontal banding (flickering) due to electronic rolling shutters

It is a well-known artifact that in CMOS cameras with electronic rolling shutter, horizontal banding (flickering), i.e. brightness intensity variations, are observed when the image is recorded under ...
3
votes
0answers
632 views

Incorrect Frequency results when using Multiple Signal Classification (MUSIC)

I am using MUSIC (Multiple Signal Classification) to determine Direction Of Arrival (DOA) and frequency of signals impinging on an Antenna Array. I am using a function ...
3
votes
0answers
5k views

1/3 octave spectra from fft

I have got a signal in frequency domain. This is a frequency response function from software, so I can do nothing about it and have to leave it in frequency domain. I want to transfer the data to 1/3 ...
2
votes
5answers
4k views

What does the exponential term in the Fourier transform mean?

We know that Fourier transform $F(\omega)$ of function $f(t)$ is summation from $-\infty$ to $+\infty$ product of $f(t)$ and $e^{-j \omega t}$: $$ F(\omega) = \int\limits_{-\infty}^{+\infty} f(t) \ e^...
2
votes
5answers
762 views

To what extent can we see signals that fall between frequency bins?

I have a simple problem I would like to figure out for fourier analysis of seismic data. Let us say that we have a signal $z[n]$, of length $N$. If I take its (same size) FFT, I will get $Z[k]$, ...
2
votes
5answers
355 views

DFT derivative property?

Does it have one? The continuous variant does, $f'(t) \rightarrow j \omega F(\omega)$ - but $jkX[k]$ definitely isn't it for DFT. To find it there must be a useful simplification of $\text{DFT}(x[n] - ...
2
votes
3answers
1k views

Theoretical Maximum of DFT

For any discrete input signal between +1 and -1, what is the theoretical maximum DFT? If the input is a cosine of $N$ samples with amplitude $A$, the peak spectral magnitude is $A*N/2$. But what ...
2
votes
4answers
2k views

Why does the frequency in the DFT have to be an integer?

I don't know why the result of DFT and FFT in MATLAB like below images.. fs=128; t=0:1/fs:1-1/fs; x=cos(2*pi*3.5*t); X=fft(x); N=length(x); n=0:N-1; f=fs*n/N; plot(f,abs(X)/N); If I set the ...
2
votes
1answer
2k views

simplest Notch filter in the world

What do you think of this notch / band reject filter for a very very narrow band ? ...
2
votes
2answers
1k views

Sinc Interpolation Using DFT (FFT)

Lets say I want to double the number of points in an array f. I had the idea to do this: F=fft(f);N=length(f); FF=[F(1:N/2) zeros(1,N) F(N/2+1:N)]; f=ifft(FF); ...
2
votes
3answers
1k views

Why does an 8 point DFT behave differently from a 16 point?

I have a 50 Hz sine wave sampled at 1600 Samples/second.I'm computing the 16 point DFT.So my fundamental frequency is 100 Hz. I then decimated the 1600 samples to 400 samples.I then computed the 8 ...
2
votes
3answers
14k views

FFT amplitude or magnitude

Can I use the word amplitude instead of magnitude when I describe FFT bins? I dont see any similar word in my language.
2
votes
2answers
493 views

Fourier Decomposition

Hello everyone have a look at this video of Fourier Decomposition of an image(otherwise you can also refer the image which shows few plots of different extracted waves from an image) . We also know ...
2
votes
3answers
607 views

Analyse audio/music frequencies without STFT, at 1/f temporal resolution, using probe phasors at logarithmically-spaced frequencies, O(N log N)?

First, some background: The STFT is the best general-purpose tool I know of for analysing a (musical or other) signal into its component frequencies. For many purposes the STFT works fine, but there ...
2
votes
1answer
1k views

Calculate harmonics using DFT from real points

I have a real data of 144 points, when I perform a 144-point DFT on this data, I get $X$ with real and complex values. I want to calculate harmonics using these $X$'s. The $X[0]$ and $X[72]$, added ...
2
votes
2answers
55 views

Dominant Frequency Peak Decreases with Increasing Window Size

I have a signal that looks like this. I analyse it using fast Fourier transforms to identify the frequency with the largest peak, which is always close to zero. (There are no other clear peaks.) If I ...
2
votes
1answer
630 views

Proving that the IDTFT is the inverse of the DTFT?

The DTFT is given by: $$X(e^{j\omega}) = \sum_{n=-\infty}^{\infty}x[n]e^{-j\omega n}$$ The IDTFT is given by: $$x[n]=\frac{1}{2\pi}\int_{0}^{2\pi}X(e^{j\omega})e^{j\omega n}d\omega$$ I have been ...
2
votes
1answer
237 views

Understanding the DCT

I have been trying to understand the definition of the DCT and found a really good website describing its definition. Here is the link DCT. What I don't understand is the part of the DFT. Why is the ...
2
votes
2answers
10k 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 ...
2
votes
2answers
128 views

DFT of pure sinusoidal wave

I'm writing a program in which you can synthesize waves by adding to a sound's Fourier transform, and then inverse the transform to get the modified sound. In order to do this, I need to know what to ...
2
votes
2answers
123 views

Effect of changing sample rate, window duration and zero padding on DTFT and DFT

Let $T$ be the window duration, $N$ be the DFT size, $F_s$ be the sample rate, and $F_{max}$ be the frequency of the highest bin. In the context of image below: halving the $F_s$ (keeping $T$ ...
2
votes
1answer
87 views

IDFT of $Y[k]=2X[k]$ for even $k$

If the 16-point DFTs of $x[n]$ and $y[n]$ are given as $Y[k]=\begin{cases}2X[k], & k=0,2,4,...,14 \\ 0, & k=1,3,5,...,15\end{cases}$, where $x[n],y[n]=0, \forall n<0, n>15$, how can I ...
2
votes
2answers
664 views

Can you calculate the absolute/amplitude values of a Fourier transform without complex/imaginary?

The DFT formula is $$X(k) = \sum x(n)e^{-i2πkn/N}$$ Is it possible to obtain absolute values from the DFT without having to calculate the imaginary components? I only need the signal amplitude values,...
2
votes
3answers
5k views

Calculating the Spectral Centroid of a Signal

Here is the equation: $$C_i=\frac{\displaystyle \sum_{k=1}^{W_{f_L}}kX_i(k)}{\displaystyle\sum_{k=1}^{W_{f_L}}X_i(k)} $$ The MATLAB code for the equation is: ...
2
votes
2answers
578 views

Inverse Sliding DFT

From paper: Bradford R., Dobson R., ffitch J. - Sliding is Smoother than jumping In chapter 6 - Signal Reconstruction, the inverse of the sliding DFT can be achieved by this formula: $$f_0=\...
2
votes
1answer
4k views

Correlation between real and imaginary parts of a Fourier transform of zero mean Gaussian

From this previous post, the real and imaginary parts of the Fourier transform of a zero mean Gaussian are uncorrelated (and i.i.d. Gaussians) This some how seems counter-intuitive. It seems if the ...
2
votes
1answer
5k views

retrieving original data from phase and magnitude of Fourier transform

I use this snippet of python code to transform data to Fourier phase and magnitude and then retrieving original data. ...
2
votes
2answers
5k views

Time domain interpolation using FFT with zero padding on the end

I've got a situation where I'd like to use an FFT to do interpolation in time on some complex data (I need to go to the frequency domain anyways to window my data). The notional way of doing this ...
2
votes
1answer
1k views

DFT of complex signal using Goertzel algorithm in C

I am implementing a BFSK frequency hopping system with TX and Rx modules. I am using Goertzel Algorithm at the receiver end to demodulate the data i.e. to determine the carrier frequency of the ...
2
votes
1answer
468 views

Calculating the first derivative of an image using DFT

I need to calculate the first derivative of a greyscale image (a 2D array) using a DFT function I built (which works). Unfortunately, the results don't seem to be correct. In the fourier domain, the ...

1 2 3
4
5
16