# Tag Info

## New answers tagged fft

1

hint only, since this is homework and you could get a lot out of this! The mathematical operation a filter performs between filter impulse response and signal is called __________(1). When we process both filter and signal with an FFT (which is just a fast implementation of __________(2)), then that operation on the originals is equivalent to __________(3) ...

1

Figured I'd post this since I wrote it anyway, just a confirmation of Fat32's answer. Letting $N' = \frac{N}{2} - 1$ we have $\sum_{0}^{\frac{N}{2} - 1} e^{\frac{-j2\pi k (2n)}{N}} = \sum_{0}^{N'} e^{\frac{-j2\pi k n}{(N'+1)}}$ Then plugging in the geometric sum formula: $=\frac{1 - e^{\frac{-j2\pi k(N'+1)}{(N'+1)}}}{1-e^{\frac{-j2\pi k}{(N'+1)}}}=\frac{1 ... 3 Assuming$Neven : \begin{align} X[k] &= \sum_{n=0}^{N-1} x[n] ~ W_N^{kn} ~~~,~~~k=0,1,...,N-1\\ \\ &= \sum_{n=0}^{N/2-1} 1 ~ W_N^{k ~2n} \\ \\ &= \sum_{n=0}^{N/2-1} e^{-j 4\pi kn/N} \\ \\ & = \frac{ 1 - e^{-j \frac{4\pi k}{N}N/2 }}{ 1 - e^{-j 4\pi k/N}} \\ \\ & = \frac{ 1 - e^{-j 2\pi k}}{ 1 - e^{-j 4\pi k/N}}~~~,~~~k=0,1,...,N-1\\ ... 0 The factor of "2" comes from the contribution of the negative frequencies, which doesn't apply to DC. A better way to plot this is to NOT multiply with 2 but plot the entire FFT range from -400Hz to +400Hz. There you will see three components: 1 W at DC and 0.25W each at -50Hz and +50Hz which is exactly what's happening here. If you want to plot ... 1 You forget that what you did was describing the passband signals (i.e. some waveform on a carrier frequency == on a wavelength) in baseband. So, of course, after calculating the baseband spectrum, you need to shift it back where it came from - to the carrier frequency. It's as easy as that. If this isn't clear to you, you might want to revisit what (complex ... 1 HINT: Try introducing the sampling frequency F_s. Then f in the relation in Equation (1) is relative to the sampling frequency \omega = 2\pi f\quad\text{where}\quad f = \frac FF_s\tag{1} $$Where the units are as follows: \omega in [radians/sample] f in [cycles/sample] F_s in [samples/second] F in [cycles/second] or [Hz] Your discrete time ... 1 The reason is very simple in the context of the DFT and Sampling Theorem. In that context the sampling duration is about the duration you have full knowledge of and able to reconstruct under the assumption of proper sampling. For discrete signals, in the context of the DFT, the model is about the signals being periodic. Hence teh last sample gives you the ... 3 It's convention, they're equivalent:$$ \exp{\left(j2 \pi \frac{N}{2}n/N \right)} = \exp{\left(j2\pi \frac{-N}{2}n/N\right)} \\ \Rightarrow e^{j\pi n} = e^{-j \pi n} \Rightarrow \cos(\pi n) = \cos(-\pi n)=(-1)^n,\ j\sin(\pi n) = j\sin(-\pi n) = 0 $$MATLAB and Numpy go [-N/2, ..., N/2-1], which is unfortunate for analytic representations (+ freqs only). ... 0 Assuming x[n] is real, resulting in X[k] being "Hermitian symmetric";$$ X[N-k] = (X[k])^*$and if$N$is even, then the value in the DFT bin$X[\tfrac{N}{2}]$(which is a real quantity with zero imaginary part) should be split into two equal halves. One half should be placed at$k=-\tfrac{N}{2}$and the other half placed at$k=+\tfrac{N}{2}$... 1 Is that to be expected when doing FFT analysis of any signal? No. Either your calculation or the implementation of your analysis is off. Secondly, I thought that the fundamental frequencies in my signal should have the highest amplitudes from all other peaks. Why did you think that? There are many signals where the fundamental is lower than the harmonics ... 2 What may explain why your spectrum is noisy is that you are computing it using a single burst of data. You will have to smooth it by averaging successive spectrums applied on your measurements. The number of samples that shall be used for the averaging have to be tuned depending on the speed of variation of your phenomena. After having done this, the other ... 2 Your resulting audioFile in the line audioFile= length(audioFile) / distortionPeriod; is a single number and not a vector signal. And for this reason your audioFileFft and audioFileDftMat are computed from the processing of that number and not your initial signal vector in audioFile; which is not your intention. However if that line is for newLength, and ... 2 The command fft computes the FFT along each column of its input matrix. If I understand correctly, you want the FFT along the rows. One way to do that is audioFileFft = fft(audioFile'); The same can be done using the DFT matrix (albeit much less efficient): audioFileDftMat = dftmtx(distortionPeriod) * audioFile'; 0 This part is clearly wrong (but there might be other issues as well) float max=0; for(int c=0;c<SIZE2;c++) { if(max<=sample[c]) max=sample[c]; } for(int c=0;c<SIZE2;c++) { if(sample[c]>127) sample[c]=sample[c]-max; sample[c]=sample[c]/32768; } To convert samples stored in S16_LE format (which corresponds to 16 ... 1 Here is how I think about it. The FFT outputs an array of size$N$. The spectral bin spacing is$ \Delta \omega = 2 \pi / ( N \Delta t)$where$ \Delta t$is the spacing of the samples in time and$N$is the number of points in the FFT. For a given$j$, the associated FFT frequency in the usual output format (e.g. FFTW) is given by$\omega_j = j \Delta \...

1

Since you didn’t (and can’t, unless you use strictly symbolic transformations) use infinite precision arithmetic and values, you are seeing numerical noise instead of zeros (etc.). And the phase of noise values can be random. An FFT does less arithmetic than a DFT, so has less opportunities to add more numerical noise.

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

Any place you would like to filter an image with anti symmetric filter.

5

If you're using the FFT and iFFT to perform fast convolution, yes, you can do it in-place and you can do without bit-reversing in the sample processing, but you will have to bit-reverse the transfer function $H[k]$. You would use the DIF for the forward FFT and the DIT for the inverse FFT. O&S have the clearest treatment, in my opinion. I am robbing ...

3

Yes the basic DIT and DIF FFT butterfly structures (with in-place computation, and buffered input, as shown on RBJ's answer) require an index reversal (via bit reversing for radix-2) at the input for DIT, and at the output for DIF respectively, so that normal order input vs normal order output is maintained. If bit-reversal is skipped, DIT output will be in ...

1

What are you planning to do with the STFT? The time-domain mean of the signal is the DC component and this should usually be close to zero for audio. Any DC offsets or low frequencies below the threshold of hearing (eg. around 20Hz, give or take) are generally considered defects and usually removed by filtering during production if present to a significant ...

0

A hand clap has a very high intensity and so I believe that you can detect the time location using an intensity threshold. For comparison purposes you can do a direct comparison of FFT, using for example mean square error or other metric.

0

What you're interested in sounds like a generic version of a matched filter. I'm not going to be able to speak to the software aspect of how you implement the file handling and "always-on" listening ability of this problem, but from a signal processing perspective, that's what you want to look into. It's worth noting that your filter is unlikely to ...

1

You seem to be computing phase near the beginning of your window, where there can be a circular discontinuity. There are (at least) 2 ways to solve this issue. One is to use a window and FFT or DFT length that are exact integer multiples of the period of any sinusoidal inputs. The second way is to measure phase from the middle of your data window, by doing ...

3

There are a few things going on: The complex representation of frequency is such that the real part corresponds to a cosine component and the imaginary part to a sine component. So a complex phase of 0 corresponds to a cosine wave, not a sine wave. This is why the computed phases are off by about 90 degrees from what you expect, according to the trig ...

2

This is probably the single most asked question on this forum. A similar one was asked and answered just a few hours ago: Spectral leakage from mathematical point of view Your expectations are wrong: you only get a spectral dirac impulse if the frequency of the complex exponential on he FFT grid, i.e. an integer multiple of the sample rate divided by the ...

0

Sanity check your data layouts. It is very common for FFT libraries to pack the (real-valued) Nyquist-bin into the unused imaginary component of the DC-bin and it happens almost naturally when you implement a real-transform as a half-size complex-transform. As far as I can tell, vDSP wants such "packed" layout, where as Python apparently stores it ...

1

In practice you would make sure that your filters don't have very large gains, at least not over a large frequency range. The filter you're using in the given example has a maximum gain of almost $26$ dB (at DC), and the gain is no less than $12$ dB for any frequency. I.e., you're applying a flat gain of $12$ dB, and on top of that you boost a relatively ...

1

Typically if you're designing to an amplitude response, you set the phase at zero. In processing time-domain signals, this is to keep the group delay of the filter constant. In processing images, this will keep the filter effects centered, rather than displacing different spectral components of the image with respect to one another. At least in time-domain ...

4

Since you care about the time it takes, you'll want to use an optimized FFT implementation. That would be FFTw or FFTS, realistically. Historically, FFTw is way dominant in software (I mean, even Matlab uses that), but FFTS works really well on ARM, so might be the better choice for your Pi. Then you'd just write a minimal C++ program that creates an ...

4

Circular convolution is just linear convolution aliased by DFT length $n$. The length of linear convolution of $a$ and $b$ will be $2n-1$. So take $FFTs$ of $a$ and $b$ , padding each of them to length nearest power of 2 more than or equal to $2n-1$. Multiply the corresponding $FFTs$ point by point to get a power of 2 length sequence and take $IFFT$ of it. ...

Top 50 recent answers are included