Hot answers tagged

7

Start with what we know: The DFT works perfectly for a single cycle waveform input. For a single cycle waveform, all harmonics have an integer number of cycles (by the definition of “harmonic”). “Spectral leakage” occurs when the input is not a single cycle waveform. As such, at least one frequency component is not represented by an integer number of cycles....


5

Let's assume we have a sample rate of $f_s=10 kHz$ and FFT size of $N=1000$ Your bin spacing is $\delta f = 10 Hz$. It's simply the sample rate divided by the FFT size. That's all there is to it. Keep in mind that the FFT requires both the time domain and the frequency domain signal to be perodic. Most signals are not, so there needs to be some sort "...


4

(1) I'm not sure my intuition is right Almost, but you're missing the fact that if you're sampling at 4000kHz, the signals alias; after sampling at 4000kHz, a sine wave at 1500Hz is indistinguishable from one at 2500Hz or 5500Hz, etc. Also, because the work is being done in complex numbers, negative frequencies have meaning: $e^{-j \omega t}$ is different ...


4

Here's the pure math: $$ x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{i \frac{2\pi}{N} nk } $$ $$ x[n] = \frac{1}{8} \left[ (5.657 + i 5.657) e^{i \frac{2\pi}{8} n 3 } +(5.657 - i 5.657) e^{i \frac{2\pi}{8} n 5 } \right] $$ $$ e^{i \frac{2\pi}{8} n 5 } = e^{-i \frac{2\pi}{8} n 3 } $$ $$ \begin{aligned} x[n] &= \frac{1}{8} \left[ (5.657 + i 5.657) ...


4

Please see below diagram to see the Stage 2 and Stage 3 butterflies.


3

I don't think Hilmar's answer is very good as it interprets the DFT within a specific application context. That confuses issues. The DFT is a tranform that works on a set of N samples. The samples are presumed to be evenly spaced in their domain on a finite interval of samples is called a frame. It may be time, it may be distance, or it could even be ...


3

Since your signal isn't sampled uniformly some strange things might happen when you apply FFT and look at the results. What you should do is estimate the Uniform DFT of the Non Uniform Time Series. One easy way to do it is use the reference code and analysis I posted on the question - Frequency Analysis of a Signal Without a Constant Sampling Frequency (...


3

Depends a bit on the indexing convention, but in typically you would interpret the frequency interval as $[-f_s/2, f_s/2]$ and not as $[0,f_s]$. The DFT is periodic in N so you you have $$X(N-1) = X(-1) $$ Keep in mind that that the sampling theorem requires the signal to be band limited to $f_s/2$ so assuming that you have actual independent information ...


3

Edit: I've come to realize that my definition below of "Frequency Resolution" is completely wrong (as well as OP's question). Frequency resolution is how similar the window function's magnitude in frequency space is to the Dirac delta function. This is because the product of the window and the signal in the time domain becomes convolution in the ...


3

Zero-padding does not affect DFT magnitude of the original N-DFT Samples. Overall energy does increase in the longer DFT and that is because we have introduced non-zero samples in between N-point DFT. Zero-padding does not add noise to the DFT. The side-lobes appearing are as a consequence of polynomial interpolation which happens when we take DFT of a zero-...


3

Imagine that a continuous signal has a frequency component of amplitude $A$ at exactly 20 Hz (you can imagine it is alone, a single perfect wave). With a FFT, or any discrete Fourier transform, you could hope that, if you have acquired the signal correctly (above Nyquist), the discrete spectrum will give you a clear peak with amplitude $A$ at 20 Hz. This is ...


3

IMHO, leakage is a poor term for it. Best representation is a much more descriptive though wordy description. Imagine a stereo with one of those displays with the bars that correspond to frequency. They usually bounce around a lot, but they do give a representative view of the frequency content. Now, let's take the stereo into the lab and feed it a sweep ...


3

They perform two different mathematical operations FFT executes a 1-dimensional Discrete Fourier Transform one each column of the input matrix (or the first non-singleton dimension) FFT2 executes a full 2-dimensional Discrete Fourier Transfrom on the entire matrix. Which one you want to use depends on your specific application. One is not inherently "...


3

Let’s be clear on what we will refer to as time delay and phase shift. Due to the common association of individual frequencies as sinusoids many confuse delay and phase shift as being equivalent. However a phase shift in time is simply multiplying a time sample by $e^{j\phi}$ while a time delay is displacing the sample in time such as done with $x(t-\tau)$. ...


3

Myth: DTFT is Sinc-interpolated DFT. Problem with the above statement: Sinc is not $2\pi$-Periodic function, but all DTFTs are. Correct Answer: Theoretical, Continuous-$\omega$ $2\pi$-Periodic DTFT can be obtained by continuous Lagrangian-interpolation of the DFT Samples. So that the values at $\omega = 2\pi k/N$ will be the DFT Samples $X[k]$ for $k=0,1,...


3

If you want to take DFT of a cosine wave $cos(\theta)$ sampled at N equally spaced values between $[0, 2\pi]$, then you need to consider taking N-point DFT of the sequence : $$x[n] = cos[2\pi \frac{n}{N}], n = 0,1,2,...,N-1$$ $cos(\theta)$"> And, for this $x[n]$, you dont even have to apply the DFT formula. It can be done pretty simply by using the Euler's ...


3

The maximum frequency for a real waveform is $F_s/2$, while the maximum frequency for a complex waveform is $F_s$. The DFT is a transformation of N samples in time to N samples in frequency, with bins numbers $0$ to $N-1$, with bin $0$ representing "DC", and bin $N-1$ representing 1 bin less than the sampling rate. Complex signals are resented as phasors ...


3

But I want to see why either the bin width is 1/T where T is the duration the samples are taken over, or why the DTF is Fs Hz periodic. (I think bin width as Fs/N is a red herring) The fourier transform of a finite length sequence $x[n]$ ,$0 \le N \le N-1$ is $$ X(e^{j\omega}) = \sum_0^{N-1}x[n]e^{-j\omega n} $$ This function is continuous and its ...


3

$$X_4[0] = x[0] + x[1]$$ $$X_4[2] = x[0] - x[1]$$ Now $$X_2[0] = x[0] + x[1]$$ $$X_2[1] = x[0] - x[1]$$ Therefore $$X_2[0] = X_4[0]$$ $$X_2[1] = X_4[2]$$ An alternative explanation is the following, if we were to decimate in the frequency domain by 2 (the 4 point FFT), you would incur circularly shifted Aliasing in discrete time domain. Since we ...


3

it seems like the bigger problem is that subsampling the signal would result in aliasing frequencies No, subsampling in frequency domain corresponds to aliasing in time domain. So the idea here is to purposefully alias in time domain so that you get a sub-sampled FFT. That is exactly why 'Claim 3.7' of paper mentions $y_i=\sum_{j=0}^{n/B-1}x_{i+Bj}$. These ...


3

Let $x$ and $y$ be signals of $N$ samples each, numbered as $x(0),\ldots,x(N-1)$. Then their DFTs are $X$ and $Y$, which also have $N$ entries each: \begin{eqnarray} X(k) &=& \sum_{n=0}^{N-1}x(n)e^{-2\pi i kn/N},\\ Y(k) &=& \sum_{m=0}^{N-1}y(m)e^{-2\pi i k m/N}, \end{eqnarray} where the indices run from $0$ to $N-1$. The $k^{\textrm{th}}$ ...


3

Frequencies in DFT, $\omega = \frac{2\pi}{N}k, \ k = 0,1,2,...,N-1 $, only depends on the Length $N$ of DFT, and nothing else. $$X[k] = \sum^{N-1}_{n=0}x[n]e^{-j\frac{2\pi}{N} nk}, \qquad k = 0,1,2,...,N-1$$ It is very important to understand this expression as the projection of time-domain finite length sequence $x[n], n=0,1,2,3,...,N-1$, of length $N$, ...


3

It will match for circular convolution modulo $N$, where $N$ is 4 here. For finite length sequences product of DFT of 2 sequences is equivalent to DFT of circular-convolution of the 2 sequences. >> cconv([0,1,2,1], [0,1,-1,1], 4) ans = 0 1 2 1 >>ifft(fft([0,1,2,1]).*fft([0,1,-1,1])) ans = 0 1 2 1


3

1. Duality between discrete frequency and discrete time domain. DFT Duality is generally referred to the duality of DFT-IDFT pairs. This in turn comes from the similarity between analysis and synthesis expressions of DFT and IDFT. $$X[k] = \sum_{n=0}^{N-1}x[n]e^{-j\frac{2\pi}{N}nk}$$ $$x[n] = \frac{1}{N}\sum_{k=0}^{N-1}X[k]e^{j\frac{2\pi}{N}nk}$$ (Although ...


3

Duality in DFT would mean that if $x[n]$ has DFT coefficients as $X[k]$, then DFT of $X[n]$ would be $Nx[(N-k) \mod N]$ Proof: Given, $$X[k] = \sum^{N-1}_{n=0}x[n]e^{-j\frac{2\pi}{N}nk}, k=0,1,2,3,...,(N-1)$$ If we take DFT of the sequence X[n], then what we get is the following : $$Y[k] = \sum^{N-1}_{n=0}X[n]e^{-j\frac{2\pi}{N}nk} = N \left(\frac{1}{N}\...


3

The reason the Radix-4 FFT is of interest is in the simplicity of multiplying by $\pm j$ in actual implementation. Below shows the Radix-4 4 point DFT core processing element as part of the Radix-4 FFT Butterfly in comparision to the Radix-2 FFT butterfly (with 2 point DFT core processing element) and the resulting decrease in number of operations, ...


2

The DFT Matrix for Non Uniform Time Samples Series Problem Statement We have a signal $ x \left( t \right) $ defined on the interval $ \left[ {T}_{1}, {T}_{2} \right] $. Assume we have $ N $ samples of it given by $ \left\{ x \left( {t}_{i} \right) \right\}_{i = 0}^{N - 1} $. The samples time $ {t}_{i} $ is arbitrary and not necessarily uniform. We're ...


2

I would like to give another take on @DanielSank's answer. We first suppose that $v_{n} \sim \mathcal{CN}(0, \sigma^{2})$ and is i.i.d. Its Discrete Fourier Transform is then: $$ V_{k} = \frac{1}{N} \sum_{n=0}^{N-1} v_{n} e^{-j 2 \pi \frac{n}{N} k}$$. We want to calculate the distribution of $V_{k}$ To start, we note that since $v_{n}$ is white Gaussian ...


2

Incidentally, DFT is the only bijective linear transformation that exchanges convolution and termwise multiplication (up to permutation of the coefficients, obviously). This is not difficult to prove, but I have found no reference on this result before I spelled it out in Music Through Fourier Space, Thm. 1.11 (Springer 2016). It is messier in the continuous ...


2

Check my answer on a similar question : H(z) as N-DFT Only thing to add it that for both the systems, it is possible to compute $H[k]$ by figuring that the numerator and denomenator are as follows : Numerator = $[1]$, Denominator = $[1, -\frac{1}{2}]$. Numerator = $[1]$, Denominator = $[1, -2]$. Take $N_b$-DFT of numerator and $N_b$-DFT of Denominator ...


Only top voted, non community-wiki answers of a minimum length are eligible