Hot answers tagged

43

Real signals are "mirrored" in the real and negative halves of the Fourier transform because of the nature of the Fourier transform. The Fourier transform is defined as the following- $H(f) = \int h(t)e^{-j2\pi ft}dt$ Basically it correlates the signal with a bunch of complex sinusoids, each with its own frequency. So what do those complex sinusoids look ...


35

I think this was put very well in the well known "DSP guide" (chapter 24, section 5): Fourier analysis is used in image processing in much the same way as with one-dimensional signals. However, images do not have their information encoded in the frequency domain, making the techniques much less useful. For example, when the Fourier transform is ...


21

The FFT (or Fast Fourier Transform) is actually an algorithm for the computation of the Discrete Fourier Transform or DFT. The typical implementation achieves speed-up over the conventional computation of the DFT by exploiting the fact that $N$, the number of data points, is a composite integer which is not the case here since $101$ is a prime number. (While ...


20

The naive implementation of an $N$-point DFT is basically a multiplication by a $N \times N$ matrix. This results in a complexity of $\mathcal{O}(N^2)$. One of the most common Fast Fourier Transform (FFT) algorithm is the radix-2 Cooley-Tukey Decimation-in-Time FFT algorithm. This is a basic divide and conquer approach. First define the "twiddle factor" ...


19

Resolution has a very specific definition in this context. It refers to your ability to resolve two separate tones at nearby frequencies. You have increased the sample rate of your spectrum estimate, but you haven't gained any ability to discriminate between two tones that might be at, for instance, 236 Hz and 237 Hz. Instead, they will "melt together" into ...


19

http://nbviewer.jupyter.org/gist/leftaroundabout/83df89a7d3bdc24373ea470fb50be629 DFT, size 16 FFT, size 16 The difference in complexity is pretty evident from that, isn't it? Here's how I understand FFT. First off, I would always think about Fourier transforms foremostly as transforms of continuous functions, i.e. a bijective mapping $\operatorname{FT} ...


18

This phenomenon has nothing to do with spectral leakage. What you are observing is the effect of zero padding. Given a number of samples $N$, there is a maximum possible frequency resolution $\Delta f$ that can be achieved: $$\Delta f=\frac{f_s}{N} $$ In your case $\Delta f$ is exactly $2\;\mathrm{Hz}$. If you zero-pad your signal, there is no extra ...


17

The differences you see are due to numerical errors in floating point format. All operations needed to perform an FFT and an inverse FFT can only be done with finite precision and you've shown the result of this finite accuracy in your lower right plot.


17

DFT and DTFT are obviously similar as they both generate the fourier spectrum of time-discrete signals. However, while the DTFT is defined to process an infinitely long signal (sum from -infinity to infinity), the DFT is defined to process a periodic signal (the periodic part being of finite length). We know that the number of frequency bins in your ...


16

ifft(fft(a) * fft(b)) performs a cyclic convolution, convolve apparently zero-pads the inputs. If you pad both arrays with zeros, the result should be the same: a = [0,0,0,1+0j, 2+0j,0,0,0] b = [0,0,0,4+0j, 5+0j,0,0,0] print list(ifft(fft(a) * fft(b))) print list(convolve(a, b))


16

You have a bug in ft2. You are incrementing i, and freq together. That's not how you want your summation to work. I messed around with fixing it, but it got messy. I decided to rewrite it from a discrete perspective instead of trying to use the continuous terminology. In the DFT, the sampling rate is irrelevant. What matters is how many samples are ...


15

Note that an FFT result is mirrored (as in conjugate symmetric) only if the input data is real. For strictly real input data, the two conjugate mirror images in the FFT result cancel out the imaginary parts of any complex sinusoids, and thus sum to a strictly real sinusoid (except for tiny numerical rounding noise), thus leaving you with a representation ...


15

Math tools We can do the calculation using some basic elements of probability theory and Fourier analysis. There are three elements (we denote the probability density of a random variable $X$ at value $x$ as $P_X(x)$): Given a random variable $X$ with distribution $P_X(x)$, the distribution of the scaled variable $Y = aX$ is $P_Y(y) = (1/a)P_X(y/a)$. The ...


15

Here is a picture to add to Robert's good answer demonstrating the "re-use" of operations, in this case for an 8 point DFT. The "Twiddle Factors" are represented in the diagram using the notation $W_N^{nk}$ which is equal to $e^{j2\pi \frac{nk}{N}}$ Note the path shown and the equation underneath shows the result for the frequency bin X(1), as given by ...


14

Yes, this is always true if the input to the DFT is real valued. It's called the "conjugate complex symmetry", because $$ X_{N-n} = {X_n}^* $$ where $X_n$ is the DFT output and $()^*$ denotes the conjugate. It can be proven by inserting the property into the transformation formula of time domain sequence $x_k$: $$ X_n = \sum_{k=0}^{N-1}x_ke^{-j\frac{2\pi k n}...


14

Normalized frequency is frequency in units of cycles/sample or radians/sample commonly used as the frequency axis for the representation of digital signals. When the units are cycles/sample, the sampling rate is 1 (1 cycle per sample) and the unique digital signal in the first Nyquist zone resides from a sampling rate of -0.5 to +0.5 cycles per sample. This ...


13

The term "resolution" has multiple meanings, which can confuse people trying to communicate when using two different meanings. In the optical sense, of being able to resolve two nearby clearly separated points (or two adjacent peaks in the spectrum) instead of one blurry blob, zero-padding won't help. This is the meaning most likely being used when ...


12

There are already some good answers, but I still feel like adding yet another explanation, because I consider this topic extremely important for the understanding of many aspects of digital signal processing. First of all it is important to understand that the DFT does not 'assume' periodicity of the signal to be transformed. The DFT is simply applied to a ...


11

The DC term is the 0 Hz term and is equivalent to the average of all the samples in the window (hence it's always purely real for a real signal). The terminology does indeed come from AC/DC electricity - all the non-zero bins correspond to non-zero frequencies, i.e. "AC components" in an electrical context, whereas the zero bin corresponds to a fixed value, ...


11

Mainly because its easier. The FFT is a specific algorithm to calculate the DFT. However, it only works if you calculate ALL frequencies (regardless if you want them or not). It takes in N complex values and it spits out N complex values. So the FFT can be used to evaluate the your first equation but not your second. In your example, that's a trivial ...


10

The difference applies only to the borders of the image. In the linear convolution you assume the values of pixels beyond the border (examples being mirror of the image pixels, or 50% grey). In the circular convolution (or DFT, product, IDFT), the pixels beyond the border are the pixels on the other side of the image, just as if you had a repeated tiling ...


9

As you said, you can simply plot the frequency response of your filter from $-\pi$ to $+\pi$. However since this is a filter only has real co-efficients, you can also just plot the frequency response from $0$ to $\pi$, as this will give you all the information you need. This is because for a real signal, the DFT is conjugate symmetric, meaning that all ...


9

I think that you could get the best performance in terms of demodulator bit-error rate (BER) with a phase-locked loop. You need it to be fast, though. I think your best bet for a fast algorithm that still performs reasonably well is zero crossing. On a side note, I would like to suggest that you change the 2200 Hz to 2400 Hz. A naive implementation of ...


9

This derivation is a tricky one. The approach suggested before has a flaw. Let me demonstrate this first; then I will give the correct solution. We wish to relate the $\mathcal{Z}$-transform of the downsampled signal, $Y_D(z) = \mathcal{Z}\{x[Mn]\}$, to the $\mathcal{Z}$-transform of the original signal $X(z) = \mathcal{Z}\{x[n]\}$. The wrong way One ...


9

It should be OK. You did not specify how you obtain the vector $t$ used in generating $x$, but otherwise everything seems fine. I haven't used $\tt{bsxfun}$ but I would simply write the DFT like this: $$\tt{dummydft=x*exp(-2*pi*i*(n'*k)/N);}$$ I've tried it and it gives the same result as $\tt{fft(x)}$.


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


9

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

It's true that zero-padding in the time domain corresponds to interpolation in the frequency domain. If you have a length $N$ signal $x[n]$, its discrete Fourier transform (DFT) is given by $$X[k]=\sum_{n=0}^{N-1}x[n]e^{-j2\pi nk/N}\tag{1}$$ The signal $x[n]$ can be expressed in terms of its DFT coefficients $X[k]$ by the inverse DFT $$x[n]=\frac{1}{N}\...


8

Even & odd refer to the symmetry around $n = 0$. Even means $x[n] = x[-n]$; you can get the part for $n < 0$ by simply mirroring the part for $n > 0$ at the $n=0$ line. Odd means $x[n] = -x[-n]$; you can get the part for $n < 0$ by simply mirroring the part for $n > 0$ at the $n=0$ line and multiplying it by $-1$. A cosine wave is even, ...


8

There are several key insights you need in order to understand how DFT allows you to shift an image. First, Fourier's theorum: It's probably easier to look at the continuous (i.e., analog) case first. Imagine you have some function, call it g(t). For simplicity, let's say that g(t) is an analog audio recording, so it's a one-dimensional function, which ...


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