Overview of my Articles
This article is a summary of all the articles I've written here at DspRelated. The main focus has always been an increased understanding of the Discrete Fourier Transform (DFT). The references are grouped by topic and ordered in a reasonable reading order. All the articles are meant to teach math, or give examples of math, in context within a specific application. Many of the articles also have sample programs which demonstrate the equations derived in the articles. My testing, and independent testing, has shown them to be superior to current teaching. HIgher accuracy aside, my articles attempt to encompass an alternative approach to obtain a working understanding of how a DFT can be used in tonal analysis.
Knowing vs Understanding
An analogy can be made between engineering formulas and computer library function calls. In order to use them, only what the terms are and what the formula is expected to do needs to be known. This is purposeful design in software which allows the entire reworking of an implementation without affecting any source code which use the functions. In an engineering formula, the analogy to the reworking would be an alternative derivation. Those happen all the time.
The articles in this blog are written for an emphasis of understanding, as knowledge of proper usage is then inherent. They are also written to be practical with usage demonstrated with numerical examples or programs. You can learn and use the quadratic formula without ever knowing how to complete a square. Likewise, with these formulas, but understanding them is much more meaningful.
Understanding the DFT requires understanding complex numbers and Trigonometric functions thoroughly. In actuality, the Trigonometric functions are exponential functions using imaginary numbers, and that relationship is key.
- The Exponential Nature of the Complex Unit Circle
- Angle Addition Formulas from Euler's Formula
- A Recipe for a Common Logarithm Table
- A Recipe for a Basic Trigonometry Table
- Pentagon Construction Using Complex Numbers (2023-10-13)
The DFT is a mathematical tranform performed on a set of samples to pruduce a likewise sized set of values representing the frequency content of the signal. It can be expressed as a Matrix mulitiplication in Linear Algebra, or as a summation formula. It is determinative, meaning that if you will always get the same answer for the same inputs. Pure tone inputs are a special subset of signals which give a characteristic pattern to the output depending on the tone's defining parameters. These patterns can be described by formulas found by plugging the signal definitions into the DFT definition and applying algebra to achieve the results. These formulas are not invertible. [Edit 2022-12-26: They are invertible, after all. There will be an upcoming article with the first exact formulas for DTFT values, as far as I know. Already sent to the experts, let's see if they take note.] However, if you recognize that the DFT tone functions will only be evaluated at integer values, a simplifying assumption can be made that results in a proxy function which yields the correct bin values, but more importantly, is invertible. This is why they are called "Bin Value Formulas". They match the DFT definition at whole bins, but differ in between.
Complex values tones are a lot simpler than real valued tones. The approach in trying to find the parameter values of a tone given the DFT bin values is the same in both cases. First the frequency is estimated, then the calculated value is used with the DFT bins to find the phase and amplitude.
- A Two Bin Exact Frequency Formula for a Pure Complex Tone in a DFT
- Three Bin Exact Frequency Formulas for a Pure Complex Tone in a DFT
- Candan's Tweaks of Jacobsen's Frequency Approximation
- Phase and Amplitude Calculation for a Pure Complex Tone in a DFT
- Phase and Amplitude Calculation for a Pure Complex Tone in a DFT using Multiple Bins
- Frequency Formula for a Pure Complex Tone in a DTFT (2023-11-12)
Real tones are more difficult because they are the sum of two complementary complex tones. Deriving the Bin Value formulas was done chronologically first, but is a lot harder. The three bin formula was my original. The two bin version, and the improved three bin version, are a result of applying the techniques developed in the complex tone cases.
- DFT Bin Value Formulas for Pure Real Tones
- An Alternative Form of the Pure Real Tone DFT Bin Value Formula
- Exact Frequency Formula for a Pure Real Tone in a DFT
- Two Bin Exact Frequency Formulas for a Pure Real Tone in a DFT
- Improved Three Bin Exact Frequency Formula for a Pure Real Tone in a DFT
Multiple Tone Resolution
All the formula derivation articles presume a single pure tone in a DFT. When the tone is varying, either in amplitude or phase (thus also frequency), they become closest fits. When the signal is a mixture of tones, the formulas can be interfered with by the presence of other tones that are nearby in frequency. To a large extent, the formulas can mitigate this interference, but to get the best results it should simply be removed.
This can be achieved by an iterative algorithm that converges rapidly to a closest fit answer. The approach is the same for the real case or the complex case, just use the appropriate formulas. Multiple tones will present as multiple peaks in the DFT. In real life audio signals, the lower frequency peaks tend to be larger, so scanning for peaks from low to high is about the same as scanning from largest to smallest. It doesn't matter much, as soon as a peak is found, its parameters are estimated and stored. When the next peak is found, the effects of the prior found peaks can be largely removed by subtracting their impact on the immediate patch of DFT for the current tone using the bin value formulas. Once the effects of the other known tones are removed from th immediate patch, the calculation becomes much more accurate. After a round or two, the values become close enough that the removal process is nearly perfect. As if the other tones aren't even there at the time of calculation.
The only really meaningful definition of an "instantaneous frequency" is that of a constant amplitude tone with a slightly varying frequency. The DFT formulas assume the tone is constant frequency and amplitude across the DFT analysis frame. Although fractional frequencies (cycles larger than the frame) are possible to calculate, they are more sensitive to noise and other tones than frequencies near the half-Nyquist which are least sensitive. In contrast, these formulas were derived to determine the frequency from a portion of a real valued cycle. Fortuitously, it turns out they are also applicable to complex tones in which the distinction of being near a crossing or a peak is irrelevant.
- Exact Near Instantaneous Frequency Formulas Best at Peaks (Part 1)
- Exact Near Instantaneous Frequency Formulas Best at Peaks (Part 2)
- Exact Near Instantaneous Frequency Formulas Best at Zero Crossings
This is the only article I've written on filtering, and it is not done with standard filtering terminology. I actually see it as my favorite pseudo-differentiator since a remarkably fast version can be made on the integers using a 50/50 weighting and a shift for division. It allows you to find zero crossings and peaks on noisy data very efficiently.
The field of windowing functions was the last place I expected to make any new discoveries, but this is definitely one of the coolest. There are no window functions used in my previous formulas, and introducing them greatly complicates, if not eliminates, being able to make bin value formulas for pure tones. There is no numerical advantage gained either. There can be great display advantage though, and simplification of frequency band energy content estimation, but since parameter estimation has been my main goal (from which those other answers can be more precisely had), I have not studied window functions all that much.
These are special because they zero out a lot of values (narrowing the effective frame) and they contain the set of primary Eigenvectors for the DFT. An eigenvector is one that goes through a transform without changing direction, but it may change in length. In the case of signals, this means the DFT of the signal is the same as the signal. In the continous case of the Fourier Transform, this has the shape of a pure Bell curve, known as a Gaussian. In the discrete case, the shape is near Gaussian. The eigenvectors of the DFT are also important in the study of fractional Fourier transforms.
These are my most important articles by far. The marginal improvement (even if it is to exactness) of parameter resolution of pure tones using a DFT is just a very small part of what the DFT is good for, and even a smaller part of DSP in general. In contrast, these articles overturn the entire order of Physics.
My Physics thesis remains unchallenged, and unconfirmed, despite over a thousand pageviews of each article and contrary to my comments in the latter article, an extensive email campaign to appropriate Academic departments all over the world. The reply rate is near zero, and the few replies haven't addressed the issue. I'm not surprised.
My prior experience trying to bring my DSP formulas to Academia was somewhat similar, so this was not unexpected. Back then, in 2008, email was treated differently, and DSP is not a field that says "we know we don't have the right answer" so it doesn't elicit as many outsider contributions as Physics. I got more responses, but they weren't any more on target. Mostly were "That's not my specialty.", even though they taught the courses in the subject. Otherwise, I was sent on wild goose chases when I asked for references to my equations in the literature. When I returned saying those aren't the same, I was simply told "Good luck" and disregarded.
In other discussions, such as comp.dsp and email, I was told in no uncertain terms that an exact frequency formula was impossible because of the "DFT uncertainty principle". Furthermore, that no expert in the field would ever take a serious look at it. My articles clearly show the first one false, and turn the second into a spotlight of shame.
My articles have thousands of pageviews. I have no doubt that these formulas are being applied in private industry. It's time for Academia to catch up.
If you read these articles in order, and understand them, you should end up with a much better working understanding of the DFT than what you will get via the traditional EE continuous case route. Especially if your goal is to do audio processing. You will end up with better formulas.
One of the intents of my blog here is to serve as a rough draft for a textbook. If any publisher has interest, please contact me. There's a bunch of novel formulas throughout by blogs. You won't find them in Academia, even though they are better than the ones they got, and that isn't due to my lack of effort.
All the articles will hopefully give a different perspective on things and at the very least, serve as tool for becoming more facile with math.
To post reply to a comment, click on the 'reply' button attached to each comment. To post a new comment (not a reply to a comment) check out the 'Write a Comment' tab at the top of the comments.
Please login (on the right) if you already have an account on this platform.
Otherwise, please use this form to register (free) an join one of the largest online community for Electrical/Embedded/DSP/FPGA/ML engineers: