The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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
0answers
5 views

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

If $X(k)$ is the $N$-point DFT of $x(n)$, and $y(n)= x\frac {n+1} 2$ 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 noticed that $y(...
0
votes
0answers
7 views

What are BFCCs and where are they used?

I am doing a project on noise-cancelation based on deep learning and I came across a research paper where some of the features fed to the neural network are BFCCs of the noisy signal, I have a basic ...
0
votes
1answer
27 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
18 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
40 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 ...
0
votes
0answers
60 views

Relationship between DFT and DTFT

Let $x[n]$ be an $N$-point sequence, i.e. $x[n] = 0$ for $n < 0$ and $n \ge N$. Let $X[k]$ be the $N$-point DFT of $x[n]$. Let $$y[n]= \left \{ \begin{array}{ll} \displaystyle\sum_{l=-\infty}^{+\...
2
votes
0answers
35 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
25 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
64 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
22 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
41 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
56 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
57 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
33 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
57 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
33 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
55 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
62 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
46 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
18 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
81 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
69 views

Practical question about DFT in Matlab

Please consider this piece of code: ...
1
vote
2answers
113 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 ...
2
votes
6answers
672 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
91 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
29 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
39 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
83 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
108 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
389 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
49 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
832 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
52 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
141 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
155 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
47 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 ...
0
votes
1answer
166 views

inverse discrete fourier transfor with plain python

I am trying to calculate inverse discrete fourier transform for an array of signals. I am using the following formula: And my python code looks as follow. ...
1
vote
0answers
57 views

How to express STFT and ISTFT as a 1d convolution and 1d deconvolution in tensorflow/keras

I'm trying to implement this paper in tensorflow and keras. At the end of section 3 it says. ...
1
vote
0answers
35 views

DFT equivalent circular convolution weight matrix with a symmetric filter of length 2K+1

$\DeclareMathOperator{\diag}{diag}$In a research paper, I read that: For optimization, the $n\times n$ weight matrix of DFT can be equivalent to circular convolution with a symmetric filter of length ...
1
vote
0answers
40 views

How to select the sign of the square root of each element of a DFT in obtaining the square root of a polynomial?

I want to find the square root of a polynomial by the following process: Compute the N-element DFT of its coefficients, maybe padded with zeros. Compute the complex square root of each of the N ...
0
votes
1answer
67 views

STFT Spectrum Analyzer: power drops over 15 kHz with songs, not with pure signals

I'm developing an audio file spectrum analyzer for a University Project. My main goal is to have an application that plots the Db Spectrum of a 16 Bit WAV PCM audio file (at this time only mono files) ...
0
votes
2answers
78 views

Resolution of Discrete Fourier Transform is 1/T - Mathematical proof?

In many articles I see that the frequency resolution of the Discrete Fourier Transform (DFT) equals Fs/N where Fs is the sampling rate and N is the total number of samples. Fs/N is equivalent to 1/T ...
1
vote
1answer
146 views

Cepstrum Calculation of Rational Function H(z)

I am trying to solve my first problems at cepstrum calculation. I want to calculate the complex cepstrum $\hat{h}[n]$ of a signal $h[n]$ with Z-Transform: $$H(z)=\frac{(1-0.5z^{-1})(1+4z^{-2})}{(1-0....
0
votes
2answers
76 views

What is the interpretation of Fourier Transform containing only imaginary part?

The FT of a unit step function is taken as: $$ X(\omega) = \int_0^\infty e^{-j\omega t}dt = \frac{-1}{jw}e^{-j\omega t} \Biggr |_{0}^{\infty} = \frac{j}{\omega} $$ The transform only has the ...
0
votes
0answers
22 views

Calculating N for DFT

We want to compute an N-point DFT of a one-second duration compact disc (CD) audio signal x[n], whose sample rate is $f_s = 44.1Khz$ with a DFT sampling of 1 Hz. (a) What is the number of necessary x[...
1
vote
1answer
41 views

How Could I extract the signal in the below Image

This is my first post so sorry if I make any mistake. The entire signal length in the screen shot below is 10 second. I ran a first order low pass filter (digital) at 10Hz cut-off frequency, and I ...
0
votes
2answers
143 views

Circular Convolution Matrix of $ {H}^{H} {H} $

We all know that Discrete Fourier Transform (DFT) corresponds to circular (not linear) convolution. That is to say, if $x(n),h(n)$ and $y(n)$ is the original signal, the filter and output signal in ...