# Tag Info

21

The fast Fourier transform ($\textrm{FFT}$) algorithms are fast algorithms for computing the discrete Fourier transform ($\textrm{DFT}$). This is achieved by successive decomposition of the $N$-point $\textrm{DFT}$ into smaller-block $\textrm{DFT}$, and taking advantage of periodicity and symmetry. Now, the $N$-point $\textrm{DFT}$ of a sequence $\{x[0], x[... 12 You need Parseval's theorem. For the discrete-time Fourier transform (DTFT) you have the following relation: $$\sum_{n=-\infty}^{\infty}|x[n]|^2=\int_{-1/2}^{1/2}|X(f)|^2df\tag{1}$$ where$f$is normalized by the sampling frequency. For the DFT you have $$\sum_{n=0}^{N-1}|x[n]|^2=\frac{1}{N}\sum_{k=0}^{N-1}|X[k]|^2$$ So due to Parseval's theorem it is ... 11 Whether you scale the output of your DFT, forward or inverse, has nothing to do with convention or what is mathematically convenient. It has everything to do with the input to the DFT. Allow me to show some examples where scaling is either required or not required for both the forward and inverse transform. Must scale a forward transform by 1/N. To start ... 9 I can think of several reasons involving computational precision issues, but that probably would not do justice because mathematically we're defining it the same way no matter what, and mathematics knows no precision issues. Here's my take on it. Let's conceptually think about what DFT means in signal processing sense, not just purely as a transform. In ... 8 Creating the Frequency Vector The arrangement of the output of fft() depends on whether you use an odd or even number of points for your fft. I think this post nicely summarises how the frequencies are arranged. Have a look at it. Since you are using an even number of points, the Nyquist frequency,$F_N = F_s/2$, is present in the output of your fft, and is ... 7 Actually, 3 different ways to put the scale factors are common in various and different FFT/IFFT implementations: 1.0 forward and 1.0/N back, 1.0/N forward and 1.0 back, and 1.0/sqrt(N) both forward and back. These 3 scaling variations all allow an IFFT(FFT(x)) round trip, using generic unscaled sin() and cos() trig functions for the twiddle factors, to ... 6 All effects you see have to do with windowing. Your signal can be seen as a truncated (i.e., rectangularly windowed) sinusoid. If$s[n]$is your signal, and$w[n]$is the window, the signal you analyze is $$\tilde{s}[n]=w[n]\cdot s[n]\tag{1}$$ With the discrete-time Fourier transform (DTFT) defined by $$S(f)=\sum_{n=-\infty}^{\infty}s[n]e^{-j2\pi nf}\tag{... 5 The correct way to group multiple bins together is to multiply each complex fft bin output by its complex conjugate (which gives the bin power) then add all the bin powers together and divide by the number of bins in the group. If you want to display in db (which is the conventional approach) then take 10*log10() of the result. Negative db values are normal ... 5 Warning: |e^{j\omega}| is equal to 1 if and only if \omega is a real number. More generally, for z complex, |e^{z}|=e^{\Re{z}}. This really depends in your prior knowledge, because functions like exponentials, sines or cosines, can be developed in different ways. Here, I'll assume you know about sines and cosines, as you refer to angular ... 4 The FFT is the Fast Fourier Transform. It is a special case of a Discrete Fourier Transform (DFT), where the spectrum is sampled at a number of points equal to a power of 2. This allows the matrix algebra to be sped up. The FFT samples the signal energy at discrete frequencies. The Power Spectral Density (PSD) comes into play when dealing with stochastic ... 4 Use the transformation z = e^{j\omega}, you will get$$H(e^{j\omega}) = \frac{1-e^{-j\omega}}{5\left(1+2e^{-j\omega}\right)}$$Solving this (using e^{j\omega} = \cos \omega + j \sin \omega), you should get something like (please double check):$$H(\omega) = \frac{\left(\cos\omega-1 \right) + j4\sin\omega}{5\left(5+4\cos\omega\right)}$$Here,$$\text{... 4 If you want to code your own application that plot the magnitude response, you first need to extract the poles and zeros from your transfer function in the$Z$domain. The process that follows can either be analytic or graphical. I will try to cover both, starting with the analytic approach, then graphical. Extracting the poles and zeros Taking your time ... 4 By Euler's formula, assuming$\omega$is a real number: $$e^{j \omega} = \cos(\omega) + j \sin(\omega)$$ The definition of magnitude for a complex number$z = x + jy$is: $$|z| = \sqrt{x^2 + y^2},$$ therefore: $$\left|e^{j \omega} \right| = \sqrt{\cos^2\omega + \sin^2\omega} = 1$$ by trigonometric identity. 4 Wouldn't it be much easier to just compare the left-hand side and the right-hand side of $$e^{-j2\pi ft_0}=|H(f)|e^{j\phi(f)}\tag{1}$$ to see that$|H(f)|=1$and$\phi(f)=-2\pi ft_0$? 4 Know that each bin in the FFT is the value for the exponential$e^{j\omega t}$, not sine or cosine. So for the OP's case$5sin(2\pi 3 x-2)$in terms of exponentials (see Euler's identity) this is: $$\frac{5}{2j}e^{j(6\pi x -2)} - \frac{5}{2j}e^{-j(6\pi x -2)}$$ Each is a DFT bin with that magnitude and phase given by the exponentials above, as long as ... 3 Some of the cues you want to look for are the following: A zero on the unit circle causes a zero in the magnitude response at the corresponding frequency ($z=1$is DC, and$z=-1$is Nyquist) For a zero at DC ($z=1$), the sum of all impulse response coefficients must be zero. A zero near the unit circle causes a dip in the magnitude response at the ... 3 Use euler identity to expand the exponential to cos and sin. Then rationalize the denominator, and the last step is to group it to real part and imaginary part. To compute the magnitude just use the pythagoras theorem. For an example I'll use simple transfer function like: $$H(z) = \frac {z}{z-0.5}$$ Then substitue the$z$:$$H(e^{jw})=\frac{e^{jw}}{e^{jw}-0.... 3 The FFT magnitude, for non-zero sinusoidal-like signals, will only be the same, given a change in phase relative to the window, for signals that are exactly periodic in the window width (the non-zero padded portion of the FFT aperture). 3 Is this a well-known phenomenon? Yes, of course. You will see harmonics as soon as your clip point is lower than the maximum amplitude in the time domain. The latter is a function of the relative phases between the harmonic components. In your case the max amplitude is indeed 2.5 (plus whatever the noise adds). If you change the phases you will get a ... 3 In the image you gave, the right-hand scale is in decibels (dB). So, essentially, the square turns into an affine scaling in the logarithm domain, which essentially yields the same image, at least the same relative dynamic range. So, in that case, it does not matter. Aside, x \to x^\alpha transformations with x\ge 0 (a positive signal, a magnitude ... 3 These are just rounding errors, and you only get a flipped sign for phase values of \pm\pi, which is not an issue because the phase value is ambiguous, i.e., adding or subtracting multiples of 2\pi doesn't change the value of the complex coefficient. I assume that your code is just for an educational purpose, because it is neither efficient nor ... 2 Many audio FFT visualizations use log(magnitude) instead of linear, as that makes it easier to find a scale that makes data visible a graph. The energy contained in band that contains multiple FFT result bins would be the sum, not the max. If the "certain amount" of samples you grab for each FFT is a small fraction of those per 1/24 second, then you may ... 2 To add a bit to the previous answers: the FFT result is "binned", not continuous. A plot of an FFT result often fools people by being smooth for large enough FFT lengths. But the result is really more like a bar chart for a sequence of bins, rather than a line graph. And the bins are not rectangular in shape (in terms of frequency response). The nearer a ... 2 I did a fair amount of frequency-content visualization in the past, although I don't have the code in front of me... Sorry I don't have more time but I think this might be of help, so here's what I recall: First off, I'm not sure if this is part of what is giving you headaches, but since a real signal run through an FFT doesn't have a complex (phase) signal ... 2 It's derived using Euler's equation http://en.wikipedia.org/wiki/Euler's_formula. You start with$$H(z) = (\frac{1}{1 - \frac{1}{5}z^{-1}}) (\frac{1}{1 + \frac{1}{2}z^{-1}})$$Then plug in e^{-jwT} for z^{-1} and you get$$H(z) = (\frac{1}{1 - \frac{1}{5}e^{-j\frac{\pi }{2}}}) (\frac{1}{1 + \frac{1}{2}e^{-j\frac{\pi }{2}}})$$Now according to Euler ... 2 For a rough sketch, you can eyeball or measure the distance of the poles and zeros to a point on the unit circle, multiply/divide to get a magnitude, and sum/difference the angles from the poles and zeros to that point to get a phase. A protractor and ruler might be useful. The angles and distances change more rapidly when a pole or zero is near the unit ... 2 If the magnitude spectrum is symmetric$$M(\omega)=M(-\omega)\tag{1}$$(as I assume), then your system is real-valued. The phase response of a real-valued system is asymmetric:$$\phi(\omega)=-\phi(-\omega)\quad(\mod 2\pi)\tag{2}$$This means that there can be two cases: The phase goes through zero at$\omega=0$, i.e. the phase is given by$\phi(\omega)=...

2

I tried running the same code, and it works fine, except for 2 minor points: It's preferable to use exp(1i*phase) instead of exp(sqrt(-1)*phase) The final result will deviate from the original signal due to rounding noise (typically around 1e-16). Also, some of this noise will appear in the imaginary part of the result (so, even if y was real, yinv will be ...

2

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-...

2

Ideal low pass filter is supposed to attenuate/remove all the frequencies above the cutoff. but in practice the filters have non zero magnitude even for frequencies in their attenuation region, still they are called low pass. if the magnitude of filter is quite high for frequencies above cutoff it might be called bad lowpass filter, but is still a low pass ...

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