I am almost middle aged no so don’t think this is homework! I recently saw a YouTube video on a related topic and wanted to test my understanding. To do so I want to decompose the sequence (1, 2, 3, 4) into sine waves. Here is some R code that attempts to do so
a = fft(1:4) / 4
amplitude = Mod(a)
phase = Arg(a)
x = seq(0, 4, 0.01)
plot(x = 0:3, y = 1:4, ylim = c(-2, 5), xlim = c(0, 4))
grid()
abline(h = amplitude[1]) # this makes a straight horizontal line
w = 2 * pi / 4
lines(x = x, y = amplitude[2]*sin((1*x + phase[2]) * w ), col = "red")
lines(x = x, y = amplitude[3]*sin((2*x + phase[3]) * w ), col = "green")
lines(x = x, y = amplitude[4]*sin((3*x + phase[4]) * w ), col = "blue")
The lines clearly do not add up to the desired sequence of integers at any point. I must be missing something about the phase or radial velocity or … something.
A Fourier transform is only valid when applied to a periodic function. If the function isn’t periodic it isn’t well defined. The usual answer is to wrap the function so that it effectively repeats - and this is what the fft used will do. But this gets the next problem. The transition across the wrap needs to be continuous and smooth. 4 to 1 isn’t. (The world of signals processing will talk about windowing functions, but with only four samples, this makes no sense.) With so few samples and violating the rules on periodicity the results will very poor, and you found.
Also, the Fourier transform is defined on a continuous function. The discrete Fourier transform is defined on a set of discrete samples from a continuous function. Your sequence 1:4 is the equivalent of sampling a continuous function at four points. The fft will do its best to get you a result, but with so few samples you run into all the other issues. This gets you into the rabbit hole of sampling and aliasing. (The input samples need to be bandwidth limited - aka smoothed - with a filter that removes energy above half the sample rate. With four samples this also makes little sense.)
For the most part you are working with far too few samples, and are violating the ground rules of periodicity.
I suspect that if you were to try a lot more samples and chose a function that was continuous and smooth across the wrap you could wrestle your example into something that worked. A few tens of samples at least. The output of the fft won’t directly re-create the input. You should expect ringing artefacts due to the range of issues not fully managed. The fft will reconstruct to something that gets close to interpolating the sample integer values at their sample position.
You would probably be better off trying to start from the basics of the Fourier transform and only worry about the discrete form later. The discrete form carries with it a lot of grief that gets in the way to start with. Code isn’t the right vehicle for that.
This is just a toy exampe to demonstrate that an arbitrary siglnal can be decomposed into sine waves. It certainly can be done (whether it should or is useful is another matter). I have managed to get it to work by shifting things by \pi/2 but I don’t know why that works.
I don’t read R and am not certain what you’re doing, but if you are looking at the sine component of a Fourier transform, it will change a great deal when you phase shift the inputs. The cosine component will, too. If you are actually looking at a periodogram, which looks at the real amplitudes, phase shifting the inputs shouldn’t do anything. You could take the square root of the sums of the squares of the sine and cosine coefficients to get that. Most people talking about discrete Fourier transforms actually mean periodograms, which throw away the phase information.
Actually, the Fourier transform is defined not only just a continuous periodic function but on complex exponential functions, generally represented as sinusoidal functions. As noted, undersampling can result in aliasing, and sampling at least than the Nyquist frequency is completely meaningless, and even at higher sample rates ‘information’ about the signal is lost in the transformation. The discrete Fourier transform (DFT) is often used to represent transient (non-periodic) signals in a way that breaks them down into periodic functions with variable amplitude (for signals containing information content), or as a statistical frequency spectral estimate (i.e. a power spectral density distribution or “PSD”) for random and quasi-random (ergodic) signals.
Agreed. I don’t know about ‘grief’, but the DFT, and especially FFT methods are not going to give you real insight into what the Fourier transform does, whereas starting with a general understanding of analysis of periodic functions and the basic properties of the Fourier series will give you an intuitive understanding of how frequency decomposition via Fourier methods works in transforming time series data into frequency spectra and why that is both mathematically convenient and practically useful. There are, of course, a lot of online resources that try to explain the Fourier transform but I highly recommend purchasing or renting Fourier Analysis: An Introduction by Stein and Shakarchi which will walk you through the fundamentals and derivation of the method starting with the intuitive example of a vibrating string. The Fourier transform is really quite powerful—arguably the most powerful tool in applied mathematics after calculus—and yet is fundamentally pretty straightforward once you grasp the essentials.
Periodograms are useful to identify frequency content in pseudo-random spectra (say, in mass spectrometry, specifying a random vibration test spectrum, or looking for 60 Hz ‘line noise’ contamination) but phase content is critical in controls, acoustics, and of course fundamental in quantum mechanics. That is another reason to actually study Fourier analysis rather than gin through some R code to perform DFTs.
Oooh! You may have answered a question I’ve had for a decade. I’m a mechanical engineer, and I was working on a product that required very precise measurement of phase offset in a pair of sinusoidal waveforms.
In the prototype stage, we were measuring the phase shift in the time domain—and we actually got pretty good results. All the literature I read, however, made it clear that phase-shift was much more precisely measured in the frequency domain.
I never understood why—I have zero formal training in signal processing; at one point, I had to tell my boss that it made no sense to have multiple electrical engineers doing other stuff while the ME wrote the signal processing code.
In our production model, we included an FPGA to do the FFT. I took a different job before the project was complete, so I never got to observe the benefit. But my question is why phase shift was more accurately measured in the frequency domain.
Am I right in thinking that the large change in the sine component post-FFT is why phase shift is more accurately measured in the frequency domain?
@Saffer the Fourier transform will, in this case, transform a sequence of 4 complex numbers (mathematically speaking, this is a function on an Abelian group) to another sequence of 4 complex numbers. You really need to ditch the computer for this exercise and work it out with pen and paper. Since there are 4 numbers, 4th roots of unity will show up and it will be much simpler to focus on these at first rather than deal with sines and cosines. So the 0th coefficient will be, up to a normalizing constant just the sum 1+2+3+4, the next coefficient will be 1 - 2i -3+4i, etc.
@EdelweissPirate maybe it has to do with the fact that if you add a sine wave to a shifted version of itself, the amplitude of the resulting sine wave will depend on the amount of phase shift. What did it say in the literature you read?
No, this isn’t exactly it. My point was that, if the signal stays the same except for a shift in time, the sine and cosine components will both change. However, their root sum of squares will not change. If your signal is a perfect sine wave at a single frequency, your sine component will be a single nonzero value at that frequency and zero at all others, and your cosine component will be zero at all frequencies. Then if you shift the signal later by 90 degrees, that is, by a quarter of the wave’s period, your sine component becomes zero and your cosine component at that frequency will take on that same nonzero value.
I think you could measure phase shift with equal precision in either the time or frequency domain, limited by noise in the original signal (and this is with the provision that your data set has a length exactly equal to an integer multiple of the frequency whose phase shift you care about, and also that you’re doing a discrete Fourier transform that is generalized and not the FFT or Fast Fourier Transform method, which can only measure a data set having 2^n observations with n an integer).
That bit about the Fast algorithm is often missed. It takes advantage of the fact that doing a discrete transform of a data set half as long takes (I think) less than half the effort, so breaking up the data in a series of halvings saves a lot of computation. The algorithm reassembles the results. And I’m stretching my understanding here, I don’t really know how that works inside, and it might be the “half as long” is incorrect and there’s some different scaling of the effort. I just know the FFT is much faster, and often involves picking 2^n observations to analyze and discarding the rest, which spoils accuracy. I also know that the tools I use on the data I deal with are fast enough without using the Fast algorithm so I don’t usually use it.
If I wanted the most accurate phase shift, I probably would try using iterative arbitrary form modeling of the signal, coming up with an expression for the repeating signal in a series of ever improving curve fittings by eye followed by parametric optimization. If the data set included slightly less than a very small integer number of cycles (e.g. 1.9 or 2.9 cycles), this is very likely to give the best accuracy. It would also work well for a signal that was partly periodic and partly not, for example the sound of a highly accurate oscillator tone that also captured random background noises, or for example circadian phenomena (because the Earth’s rotation is very highly periodic but there are typically lots of other influences that aren’t).
This is (thankfully) no longer an issue. A modern FFT doesn’t just break the sample space into powers of two, but can break it into segments built from the prime factors of the sample size. Indeed, it can even work with a prime number sample size. There are of course some efficiency tradeoffs, but they are relatively minor. Something like FFTW (the Fastest Fourier Transform in the West) dynamically builds code that performs the full butterfly combination on any sized sample. It s a fabulous bit of work. (Heck it can optimise itself within your cache architecture and schedule the sub-component calculations to maximise cache, knows how to use vector instructions and so on. Quite brilliant.)
The masterful efficiency gain in the FFT (Cooley and Tukey, and subsequent variants) was to realise that there were a massive number of common intermediate results inherent in how a conventional DFT was calculated. They worked out an optimal way of calculating these and reassembling the final result in a minimum of operations. The “butterfly” describes the form of a diagram that follows how these intermediate results are calculated and propagate through the calculation.
I suspect people like using an FFT for phase information as it provides a simple and robust system that provides all the noise rejection possible with longer samples with little to no additional effort. It is just a natural fit, whereas grinding out something in normal space would be an exercise in self inflicted pain.
That’s just it—the literature I read (mostly a set of Ph.D. dissertations) made casual references, like, “Because phase is most accurately measured in the frequency domain, we do an FFT…”
So it was received wisdom for me for sure.
Oooh! Yeah…that’s exactly what we were trying to do; your approach sounds ideal. We used to joke that our device doubled as a management detector, because managers would kind of clomp by cluelessly while we were testing the thing. The vibrations from their footsteps and even the heat of their breath would throw off our tests in a really obvious way. And our baseline oscillations were really stable, despite the extraneous noise.
I was definitely a babe in the signal-processing woods. We were toing our time-domain phase comparison in LabView, which was adequate for development. But I wasn’t able to get the FFT I needed within LabView, which surprised me. Others encountered the same problem, and dumped their data streams to Matlab to perform the FFT.
25 years ago I was playing around with the Discrete Fourier Transform to decode DTMF phone tones. This was a PIC16c84 microcontroller. The analog DTMF signal was wired to a DIGITAL input. So you’d get a bunch of zeroes and ones depending on if the signal was above or below the switching threshold of the input. I simulated it in QuickBasic first and found it should work. And it did. I was amazed.
I hope it then explains what exactly they do with the transformed data; maybe from that one can figure out how accurate it should be. But, off the top of my head, as I said above, after a discrete Fourier transform for each bin you have a complex number, indicating the magnitude and phase of the signal at that frequency. If there is noise like footsteps at a different frequency then it should not affect the reading too much despite the disturbance.
I think I’m being dense; maybe this will make clear what I’m missing:
————————
With the transformed data, the authors of these papers compare the change in relative phase between the two signals, a change which is proportional to the magnitude of a physical phenomenon. This is the primary output of the instrument we were developing (an instrument that was also the explicit subject of these papers).
As far as how accurate the phase shift should be, the goal is always the greatest accuracy achievable, because the primary output of the instrument we were working on was the phase shift. A number of other outputs are derived from it, and their accuracy scales directly with the accuracy of the phase shift measurement.
————————
Is my response concordant with what you wrote? I’m not sure whether it is.
I do not know—I was just wondering whether they were doing something simple, like subtracting the two signals (before or after the Fourier transform). If there were no phase difference, they would simply sancel out, and so on. You could get good frequency resolution using a “zoom FFT”.