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
0
votes
2answers
34 views

Length of DFT defines whether I see the harmonic or the dominant frequency

I have a number of signals that are periodic. I use an fft transformation to obtain the dominant frequency of each signal. In order to increase the frequency resolution I zero pad the signal before ...
0
votes
0answers
35 views

Where to apply zero-padding for convolution dealiasing and appropriate scale

After hours of browsing the DSP posts and resources online, I still struggle to understand why my code diverges when I activate zero-padding dealiasing. When I deactivate it, everything 'works well', ...
0
votes
0answers
15 views

DFT of a function and array convolution

I saw some questions (and answers) on this subject, but they were all about a specific example and I'm not sure I understood. I'm trying to understand the meaning of computing the DFT of an array ...
0
votes
0answers
52 views

Convolution of a non-symmetrical window function by a cosine signal in the frequency domain

A have a time signal: The associated DFT spectrum of this signal: The time signal can be considered as a non-symmetrical rectangular window function multiplied by a cosine signal with a frequency $...
2
votes
1answer
53 views

Amplitude estimation of sinusoid in known spiky spectral noise

What is the "best" way to estimate amplitude of a known-frequency sinusoid in the presence of known spiky spectral noise (i.e. noise comprising a few spectral peaks at known frequencies)? By "best", ...
0
votes
2answers
49 views

DFT frequency resolution exercise [closed]

I have a discrete signal that goes as follows: $$x[n]=[-1,4,-1,0]$$ I have already done the DFT for the signal, with the following result: $$X[0] = 2, X[1]=-4i,X[2]=-6,X[3]=4i$$ But for some reason, I ...
1
vote
1answer
50 views

solution on the time domain becomes “periodic” after the inverse fourier transform

I was trying to solve european option pricing problem using Conv method (introduced by Lord in 2008 https://pdfs.semanticscholar.org/0632/460bd50b2151f74ac40028df4cc60e73a884.pdf). The final step of ...
0
votes
1answer
23 views

Bin sizes for non-uniform discrete Fourier transforms

For a non-uniform discrete Fourier transforms, do the specified frequencies – i.e., $f_k$ in – refer to the midpoint of the bin or the lower bound? I read the answer here, but that stated that ...
0
votes
1answer
24 views

DFT calculations returning different results

My coworker ran a DFT query using a software in C downloaded to his PC. His results was the following chart: I am using a JS tool from corbanbrook/dsp.js My results were very different. any ideas ...
0
votes
0answers
42 views

Scaling of the PWELCH function in MATLAB

I am trying to compute the power spectral density of a random signal using the PWELCH function in MATLAB. Since I think have not understood properly how Pwelch scales the PSD, I wrote a sample ...
0
votes
1answer
61 views

Is it possible to reduce the complexity of radix-2 FFT if the input vector contains identical elements?

my question is about reducing the complexity of radix-2 FFT when the input vector has a specific structure. For an input vector of x with N elements, the complexity is given by O(N log2 N). My input ...
0
votes
1answer
66 views

Orthogonal Basis for a 2D Signals (Compressive Sensing)

I have a 2-D signal that is (1536x128) and that is sparse in the Fourier domain (after applying fft2). I want to apply compressive sensing to recover the signal using fewer random elements, but I am ...
1
vote
1answer
54 views

Inverse discrete Fourier transform

If anyone can help solving this exercise I'll be grateful. It's urgent. (I've added my answer, but I think it's wrong)
1
vote
1answer
46 views

Derive DFT of $x((n+1)/2)$

If $X(k)$ is the $N$-point DFT of $x(n)$, and $y(n)= x\left(\frac {n+1}{2}\right)$ for odd $n$, and $0$ for even $n$. What is the $2N$ point DFT of $y(n)$ in terms of $X(k)$? So far, I've ...
0
votes
1answer
33 views

The effect of upsampling on DFT coefficients

I am learning DSP by myself and I encountered a problem that bewilders me. If I have a sequence of length N, and I upsample it by a factor of 3. How would the DFT change or related? For example: <...
0
votes
1answer
20 views

What is the form of the spectral derivative in the all-positive-frequency notation in DFT?

The Discrete Fourier Transform (DFT) of a function $u:[0,2\pi] \to \mathbb R$ sampled over $N$ equidistant points $\theta_j = 2\pi j/N,\, j = 0, \dots, N-1,$ is defined by $$ \tilde U_k = \frac1N \...
2
votes
2answers
41 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
0answers
40 views

Understanding convolution of Chirp z algorithm

I dont´t understand how works the convolution part of the Chirp z. I understand how the DFT is transformed \begin{align*} x(k) = \sum_{n=0}^{N-1} x(n) W_N^{kn} \end{align*} to this expresion: \...
0
votes
0answers
32 views

Find repeating sequences in audio file

I have a long audio file (12+ hours). I know that there are some unknown small (2 minutes each or thereabout, it varies) repeating (not bit by bit: it is recorded with a mic) chunks in it, repeating ...
2
votes
1answer
66 views

Frequency estimation of circularly shifted single tone signal

I have a discrete signal $y[n] = <e^{j ~ 2 \pi f ~ n}>_J + ~w[n]$ with $n \in [0, N[$ and $w[n]$ AWGN, $<x[n]>_K$ denotes the signal $x[n]$ circularly shifted by $K$ samples. Let's define $...
1
vote
0answers
33 views

How to compute properties of a song like key, bpm? [closed]

How to compute the key and BPM of a piece of music? Is the Fourier transform necessary? I tried to approach this issue from the music theory angle and I found that I get stuck at trying to understand ...
0
votes
0answers
26 views

Do twiddle factors of the fixed-point DFT have to be scaled to the input signal?

I have sensor data that is digitized by a 12-bit ADC that has analog range -1.65 to 1.65 V. The digital sensor data has thus scaling $3.3\cdot 2^{-12}$. I need to perform fixed-point DFT using ...
0
votes
0answers
52 views

FFT algorithm for real-time analysis

In a project, I have real-time voice audio being delivered in buffers of around 128 samples at a time. I want to calculate the autocovariance of the signal and use it to control an AR filter. To do ...
0
votes
3answers
65 views

Phase of the DFT

I'm new to the numerical processing of sampled measurements so my question is probably trivial. Let's suppose that I have the following sampled signal generated in MATLAB: ...
0
votes
1answer
80 views

Prove that, in DFT ,interpolation in time domain is equal to replication in frequency domain

Given: $x[n]$ is an $N$-point sequence whose DFT is $X[k]$ $$x[n]\xrightarrow{\mathcal{DFT}} X[k]$$ then, Prove that: DFT of the same sequence after insertion of $(M-1)$ zeroes between successive ...
0
votes
2answers
40 views

Why there is error between My DFT and built in Matlab FFT?

I'm trying to implement DFT/IDFT and FFT/IFFT in Matlab and C. I got wrong values while I implement IDFT/IFFT. So I'm trying to find a mistake. Just for DFT, I used this algorithm to implement it in ...
1
vote
1answer
64 views

Why would FFT interpolation using zero-padding undershoot the true frequency of a single tone sinusoid?

Why would FFT interpolation by zero-padding or using the Chirp Z-Transform produce a maximum at a bin that corresponds to a frequency less than the input frequency of a single tone sinusoid? I am ...
0
votes
1answer
35 views

Contributions to a DFT frequency bin

So, a frequency bin is centered around an interesting frequency $f_0$. Assume the spectrum is such that there is no spectral leakage from other frequencies to that specific frequency $f_0$. Now. I ...
1
vote
2answers
66 views

Is the value of a frequency bin of a DFT-output the average of the 'real' frequency values within that bin's range?

I am wondering whether the value of a frequency bin with a certain resolution is the average of the fourier transform values of the 'real' frequencies within that bin's range.
1
vote
2answers
65 views

Does the DFT calculate spectral components up to half the sampling frequency, $f_s/2$?

This question is prompted by a statement made in this response (reproduced below): The DFT calculates spectral components up to $f_s/2$, no matter what the input signal is. A book I'm reading ...
0
votes
1answer
52 views

DFT and integer valued basis functions'sf requencies

In Matlab the function W=dftmtx(N) gives the DFT matrix of size N. Each row is computed for an integer frequency k. $W_{k,n} = e^{-i2\pi kn/N}$, k-th frequency, ...
0
votes
0answers
19 views

Should PSD be smoothed for SNR computation in frequency domain?

When taking the Power Spectral Density of a short duration signal (say 1 second, sampled at 4096 Hz), should it be smoothed to compute SNR? I want to computed the matched filter SNR, perfectly knowing ...
0
votes
0answers
27 views

How to use a size N complex DFT to compute a size N/2 real DCT? [duplicate]

Can someone (maybe @hotpaw?) Explain How to use a size N complex DFT to compute a size N/2 real DCT? Also, I noticed that the DCT matrix (which can be obtained in Matlab by dctmtx(n)) contains dct ...
0
votes
1answer
91 views

How can I “smooth” square wave/pulse data to remove/reduce harmonics?

First, I have reviewed close-match questions, but can't find something that seems to match what I'm looking for. Also, it's been 30 years since college, so forgive me for forgetting stuff.. :) I am ...
0
votes
1answer
73 views

Practical question about DFT in Matlab

Please consider this piece of code: ...
1
vote
2answers
142 views

DCT vs DFT why do we need/want phase?

Why do we use complex exponentials in the Fourier transform, why do we want the phase part? As opposed to in DCT where there is no phase and only magnitude? Moreover, what does this phase concretely ...
3
votes
6answers
790 views

Clarification on defining FFT bin sizes

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 ...
2
votes
1answer
107 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 ...
2
votes
1answer
47 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 ...
0
votes
1answer
45 views

Proof that DFT does not require more than N points

I'm trying to show how the discrete Fourier transform (DFT) arises from the equation for the continuous-time Fourier Transform. I've run into an interesting caveat which I can't seem to find an ...
0
votes
2answers
84 views

Have you seen these kind of DFT artifacts?

we've been working with the Spiral DFT Implementation on an FPGA and managed to get it working. Unfortunately we see these strange artifacts and have no idea where they come from. Our input is a ...
0
votes
1answer
212 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 ...
4
votes
3answers
401 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 ...
0
votes
0answers
58 views

DFT truncation of signals

How can I calculate 8 point DFT of signals whose length is less then 8 ( say 2,4) then what will I assume other members in formulae "0" or rotation or keep repeating the same two numbers Consider I ...
2
votes
1answer
57 views

Goertzel derivation

Referring to this link, about Goertzel,I am confused about the final equation after N iterations Where does real = (q1 - q2 * cosine) and ...
4
votes
4answers
1k 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 ...
0
votes
1answer
58 views

FFT of a signal with 0 added between samples

I'm having a rough time doing the following question from a HW. Given a sequence of your choice, what happens to the DFT if we add a 0 between every sample? I.e. if we have x[n] = [A,B,C], we turn it ...
3
votes
1answer
161 views

Why is the Fourier (or cosine) transform decorrelating?

The discrete Fourier transform (DFT) and the discrete cosine transform (DCT) both decompose a signal into its frequency-domain spectrum. One property that I have seen praised across various domains ...
2
votes
1answer
178 views

Comparing arithmetic complexity of FFT radix-2 and convolution

Let's assume we have a discrete linear time invariant system and we have a real signal $x[n]$ with length N=50 as input for the system. The impulse response $h[n]$ of the system is considered to be ...
0
votes
0answers
48 views

Discrete Fourier Transform by longhand using MATLAB - what is the lower limit for N?

I'm seeking some guidance/reassurance on my understanding so far of the DFT, as demonstrated by my MATLAB script below. I deliberately compute the DFT longhand. My first question: Are my ...