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

FT of data points with (measurement) errors

I am measuring the oscillatory behaviour of a probability over time, and from the theory I know that the total probability should be a (weighted) sum of cos^2 at ...
0 votes
0 answers
48 views

Origin of the definitions of 16 types of discrete normalized/non-normalized Sine and Cosine transforms

I am a Ph.D in pure math. In the literature of signal processing, I observe that 16 types of discrete normalized/non-normalized Sine and Cosine transforms are being extensively studied. They have some ...
  • 295
0 votes
0 answers
45 views

What is $z[n]$ , when $Z[k]=X[2k]H[2k]$ with $y[n] = x[n]∗h[n]$ and $Z[k] = X(\omega)H(\omega)$ at $\omega = \frac{4πkn}{N}$

How do I express $z[n]$ in terms of $y[n]$, with: $$y[n] = x[n]∗h[n]$$ $x[n]$ and $h[n]$ being 16 length sequences. $X(\omega)$ and $H(\omega)$ are DTFT of $x[n]$ and $h[n]$ $Z[k]$ is defined as $$Z[k]...
3 votes
1 answer
82 views

Is there an analogue to the 2D DFT that is rotation equivariant?

I'd like to know if there is some general Fourier transform or other signal processing algorithm, such as a discrete wavelet transform, that is rotation equivariant. Rotational equivariance of a ...
0 votes
1 answer
51 views

Should calculated time domain RMS and frequency domain RMS be approximately similar?

I have an acceleration measurement for a full day with sampling rate 10.24 Hz. I have divided the signal into 30 minute intervals because I want to compare the amplitude spectra for each 30 minute ...
  • 3
0 votes
1 answer
51 views

Discrete Fourier Transform as Memory?

I am looking to ways to store data points in the format $\left( x, y \right)$ where $x$ goes from $0$ to $255$, while $y$ can be either $0$ or $1$: (e.g. $\left[ 0, 1 \right]$ $\left[ 1, 1 \right]$ $\...
2 votes
0 answers
43 views

Synthesizing a pure tone in Frequency Domain: can it be done more efficiently?

I came to the conclusion that synthesizing pure tones in Frequency Domain is much less efficient than synthesizing cosines in Time Domain and then computing the FFT. But I suspect this is the case ...
  • 311
0 votes
1 answer
115 views

How to reconstruct original signal using IFFT after cutting past Nyquist limit

I'm working on a pitch shifting program. Everything works up to the point where I try to do the IDFT. Because I cut the DFT array past the Nyquist limit, when I run the IDFT, I don't get the same ...
5 votes
4 answers
1k views

Is the negative spectrum (by DFT) of a real signal "needed" to reconstruct it?

I'm trying to grasp the "ah-ha!" moment for the DFT/FFT. One of the points I struggle with is: if the original time signal $x[n]$ is real, then the values of the DFT $X[k]$ are (correct me ...
1 vote
1 answer
38 views

How do I estimate possible aliased frequencies in sampling limited measurements?

Say I've got some data made from measurements with a too infrequent sampling rate; I know for certain there is aliasing. What I'm interested in is figuring out what frequencies are likely present ...
  • 239
1 vote
0 answers
31 views

Pitch successfully changes with Phase Vocoder, but there's an issue

I've been working on a phase vocoder program. The goal is to change the pitch of a recording of my voice. While doing research on how to change pitch, I came across this from a paper on phase vocoders ...
0 votes
1 answer
87 views

How to change fundamental frequency with DFT?

I'm working on a voice changer. My plan is to make it so that it can change your voice in various different ways, but right now I'm just trying to make it change your voice to "chipmunk voice&...
1 vote
1 answer
82 views

(Fast?) Fractional Discrete Fourier Transform

Is there a simple algorithm for computing the fractional discrete fourier transform analog to the FFT algorithm or even naive DFT matrix multiplication? I am kind of new into signal processing. For my ...
1 vote
0 answers
19 views

When is perfect analytic filtering (discrete) suboptimal?

Defined as "negative DFT bins zero", when are such filters suboptimal for AM/FM extraction or related filtering? This answer reads, [nulling] also has the worst performance compared to ...
0 votes
2 answers
40 views

The dft magnitudes aren't linear with dft point number in my matlab code

Dft magnitudes conclusion from Richard Lyons [Understanding digital signal processing] my verification code ...
  • 19
1 vote
1 answer
44 views

Overlap correlation indices in Harris 1978

In the heavily cited paper by Harris 1978, there is a section on "Overlap Correlation" where he's using a "fractional overlap r" in his equation. Here is a screen shot from the ...
0 votes
1 answer
30 views

perform fourier-type integration using DFT misunderstanding

I need to perform the following integral ($i^2 = -1$) (with a fixed value of $m$): $ \int_{\phi=0}^{\phi=2\pi} \psi(\phi) e^{-im \phi} \hspace{0.7mm} d\phi $ for all values of $m$ in $\{-N_{\theta}, -...
  • 135
1 vote
1 answer
67 views

Why do I get a phase of the FFT of a cosine function when the phase is zero?

I'm trying to find the phase of a cosine function with the FFT but I don't understand the results from the plots. I did two separate examples for two phases $\phi$: $\phi_1 = 0$ and $\phi_2 = \pi/3$. ...
  • 113
0 votes
1 answer
51 views

Scaling factor in DFT: pure math or bandwidth issues?

I'm trying to match the amplitudes of a signal before performing DFT and after. So, let's consider a 64-point sine signal with amplitude of $1$: The DFT of such a signal will give us the amplitude (...
  • 95
2 votes
3 answers
398 views

Difference in having even number and odd number of samples in DFT?

In the DFT we sample one period of the spectrum in the frequency domain. What is the difference between having an odd or an even number of samples? We know that DFT is just a sampled version of the ...
  • 320
0 votes
3 answers
181 views

Number of periods of signal required when doing an FFT

I'm using numpy.fft in python to compute Fast Fourier Transforms. In particular, I'm using rfft as I have a real signal and don'...
  • 11
0 votes
1 answer
52 views

basics of DFT padding

If $x[n]$ is length 4 sequence, with DFT $T.F\{x[n]\} = X[k]$ and $y[n]$ is a length 8 sequence obtained from $x[n]$ by padding with 4 zeros: $$y = [x[n],0,0,0,0]$$ For $k$ even, we have $X[k] = Y[k]$ ...
  • 1
2 votes
2 answers
43 views

Combing FFTs with multiple batch sizes

When processing audio with DFT, a common strategy is to keep a buffer of many samples (maybe 8192) which is continuously updated, but compute the DFT of this buffer more quickly (say every 1024 ...
4 votes
2 answers
172 views

Why only calculating N frequency bins in DFT/FFT?

I have a rough understanding of DFT/FFT. By definition: $$ X_{k}=\sum_{n=0}^{N-1} x_{n} \cdot e^{-\frac{i 2 \pi}{N} k n} $$ To me , DFT/FFT works like correlating the signal $x_{n}$ and a signal with ...
  • 43
2 votes
1 answer
78 views

The autocorrelation vector of frequency data

I am trying to find the correlation of audio frequency data resulting from an FFT with itself. It would be interesting to hear what you all think on the following question : Should one use the complex ...
  • 31
2 votes
2 answers
154 views

DFT filter bank interpretation, and perfect reconstruction?

I think I understand how the DFT can be seen as a bank of bandpass filters. I am trying to understand the IDFT within the same framework. I understand that the IDFT can be seen as summing linear ...
  • 23
0 votes
1 answer
72 views

Having Nyquist bin = aliasing?

Here I motivate the question by deriving FFT upsampling for $N \rightarrow 2N$ with even $N$. One might naively try xup = 2*ifft([xf[:N//2], zeros(N), xf[-N//2:]]), ...
1 vote
1 answer
52 views

FFT Artifacts and their cause beyond frequency resolution

I am trying to work through an issue with an FFT for audio : I have no spectral leakage while playing back audio, but the moment I change or zero out a value in any of the FFT bins, artifacts are ...
  • 31
7 votes
2 answers
911 views

Downsample a signal by a non-integer factor

I have a signal with a sample rate of 8.9286 MHz and I want to downsample it to 500 kHz. Since 8.9286 is not an integer multiple of 0.5 I can't simply decimate. Which downsample techniques are ...
3 votes
1 answer
79 views

Can we recover $|X(k)|$, given $|x(n)|$?

Given a complex vector $x[n]$, we can find the magnitudes of the spectrum by computing: $X_m[k] = |X[k]| = |FFT[x]|$ This involves performing a complex FFT and computing the absolute value of the ...
  • 55
0 votes
1 answer
79 views

How to create an ideal sine wave that will be the best fit for given sine wave with noise and distortion

I have a sine waveform that is a result of simulation. This is always single tone with a constant offset, but with distortion and noise and may have some jitter: $$s[k] = A\sin\left(2\pi \frac{f}{f_\...
  • 261
1 vote
1 answer
65 views

Can I reduce the complexity of multiplication with FFT if the input vector is repeating?

I have a Fourier matrix $F$ with size $N \times N$, such that $y = F \times x$, if I have the vector $x$ contains four identical parts, for example $x = [x_1, x_2,x_3,x_4]’$ and $x_1 = x_2 = x_3 = ...
  • 640
1 vote
0 answers
103 views

Fourier transform of a top-hat function in the Faraday Measurement synthesis context

I'm currently trying to calculate the Fourier transform of a top-hat function in the context of Faraday Measurement Synthesis. This is pretty straightforward, however, I cannot understand why I cannot ...
1 vote
1 answer
126 views

Axes of Discrete Fourier Transform

Problem Given $X[k] = \sum_{n=0}^{N-1} x[n]e^{-j2\pi kn/N}, k = 0, ..., N-1$ What are the units on the x-axis and y-axis? Note that for the x-axis there are two answers. Attempted solution My first ...
-2 votes
2 answers
117 views

Is it true that the “DFT can only deal with causal signals"?

I don't understand this remark and it's the first I hear it. Isn't this directly at odds with "DFT assumes input is periodic"? The full statement, the signals are nonzero for $t < 0$, ...
4 votes
2 answers
543 views

Fourier transform of modulus of sum of sines

$$ x(t) = |\cos(\omega_0 t) + \cos(\omega_1 t)| $$ with $\omega_0, \omega_1 > 0$. Is there a known result for $\mathcal{F}\{x(t)\}$? Derivation not needed but is welcome. Of main interest is the ...
4 votes
0 answers
93 views

Fourier transform of modulus of sum of weighted sines

$$ x(t) = |a \cos(\omega_0 t) + b \cos(\omega_1 t)| $$ with $a, b \geq 0$, $\omega_0, \omega_1 > 0$, but $a, b > 0$ or all $a, b$ (negatives included) is also acceptable, or replacing $\cos$ ...
0 votes
0 answers
42 views

How to calculate DFT of signal which occurs from 3 to 8?

How can I calculate discrete fourier transform of this signal? I'm confused as in the normal cases signal always start from 0 to N-1 but in this case it starts from 3 to 8 instead. So what would be ...
  • 143
0 votes
2 answers
60 views

Zero Padding in Implementing FFT from scratch

I'm trying to implement an FFT algorithm from scratch. I'm using the recursive algorithm where if N is a power of 2, then I have M = N/2. The algorithm is divided into even and odd parts and I have ...
0 votes
1 answer
48 views

Strided unpadding energy relationship?

If x1 = x0[::2] is unaliased subsampling, then $E(x_1) = E(x_0)/2$, which can be proven via Parseval's theorem. For same $x_0, x_1$, however, ...
0 votes
1 answer
165 views

Phase extraction from Fourier transform

Is it possible in principle to correctly extract the phase from Fourier transform? I just tried to do so using Python, here some attempts: ...
  • 95
0 votes
1 answer
508 views

FFT of a gaussian signal in Python

I've been trying to get the FFT of a gaussian in Python. When I use the following parameters, the FFT goes hand in hand with the theoretical FT of the gaussian, but if I increase $\sigma$ they rapidly ...
  • 101
1 vote
2 answers
460 views

Can anyone explain how dft works as a filter bank?

When we take the fft of input signal, the fft formulas say us to down convert the 2pik/N frequency content of input signal and sum one period interval. This gives us a just one complex number,not an ...
0 votes
2 answers
153 views

Bandwidth visualization in frequency domain

Consider some signal in frequency domain: the maximum length of which corresponds to the half of the original signal ($N/2$), here $N=32$. It is known that the bandwidth of each sample is $2/N$, so ...
  • 95
0 votes
0 answers
123 views

What is going wrong with the plot of 2D spatial spectrum at a specific frequency?

I've a set of 09 sensors in the following arrangement and the script for the sensor positions as follows: ...
  • 19
1 vote
1 answer
58 views

Lowering Spectral Resolution of FFT

I find myself in the position of having to lower the FFT resolution. Basically I have a signal of length M and I would like to make an FFT with N<M frequency bins. I cannot simply make several FFT'...
1 vote
1 answer
46 views

What Does "Reduced Modulo N" mean in this context?

I am trying to understand a piece of notation used in several papers, the simplest/shortest of which is this paper by Crochiere. The equation in question is Equation 7 on the second page: $x_m(sR) = ...
  • 175
3 votes
1 answer
118 views

Sparse signal FFT

Say I had a time domain signal $x[k]$ wich is sparse: $\log(N)^2$ nonzero samples and the fourier transform has only a very (very!) small number of high frequency components. Are there any techniques ...
  • 33
0 votes
0 answers
31 views

Confusion Understanding the mathematical expression of duality property of dft?

Duality Property for DFT Above dsp.se question provides good understanding about dft duality property but i am having difficulty understanding its mathematical expression because on Google when i try ...
  • 1,134
0 votes
1 answer
33 views

Expression for DFT of linear 2D ramp

One dimensional solution is in “Expression for discrete fourier transform of linear ramp“ I need two-dimensional for image processing. We have function f(x,y) = $a_1 \cdot x + a_2 \cdot y$, My ...
  • 99

1
2 3 4 5
20