Fourier Transform Coefficients Of Real Valued Audio Signals
2018-02-10 - By Robert Elder
This article is effectively an appendix to the article The Fast Meme Transform: Convert Audio Into Linux Commands. In this article, we will review various properties of the coefficients that result from applying the Discrete Fourier transform to a purely real signal. This discussion will place a particular emphasis on storing as little information as possible in order to recover the original waveform.
Visit the non-AMP page for the Interactive Fourier Transform Demo.
What Does The Above Visualization Mean?
The above diagrams are intended to provide insights into how the coefficients of the discrete Fourier transform affect the resulting output signal. The graph at the very top, titled 'Purely Real Input Waveform Elements' represents a purely real time domain signal. This could be something like the amplitude of a sound wave, for example from a PCM wave format, or it could be the amplitude of a radio signal over time. In any case, the point here is that we're particularly interested in input signals where there is no imaginary part to the input.
Underneath the input sequence graph, there are four graphs that, together, describe all of the Fourier coefficients that result from taking the Fourier transform of the input sequence. Normally, these four graphs would be displayed joined together: Either into a separate chart for the imaginary and one for the real part, or simply as a single chart that only displays magnitude. In this article, they have been separated in order to examine various meaningful effects that result from ignoring certain subsections of the Fourier transform coefficients. This is what the 'Force To Zero' buttons are for.
More formally, if we consider the general formula for the discrete Fourier transform:
you can see that the chart titled 'Imaginary Frequency Components 0...[n/2]' consists of the following sequence:
and the chart titled 'Real Frequency Components 0...[n/2]' consists of the following sequence:
The other two charts 'Imaginary Frequency Components [n/2]+1...N-1' and 'Real Frequency Components [n/2]+1...N-1' show basically the same thing, but for the interval
The next four charts clearly isolate the contribution of the low frequency (
The chart 'Low Frequency Real Time Domain Contribution 0...N-1' shows the result of calculating the following sequence:
and similarly, the other three charts depict the high frequency real part contribution, the low frequency imaginary part, and the high frequency imaginary part.
The final graph is simply the sum of the previous two graphs that show the real part time domain contributions. When none of the 'Force To Zero' buttons have been pushed, this is simply the result you'd get after taking the inverse Fourier transform of the coefficients, which should recover the original input exactly. Since we indicated that we're only considering signals that are purely real, this inverse Fourier transform should only yield real results, but in cases where we force certain coefficients to zero, this might no longer be the case. In either case, the imaginary part of the output is not displayed here to save space.
One final note: The above visualization will never set to zero the coefficients for the 0 or N/2 frequency even though they appear in the interval depicted above. This was done to make the analysis of high and low frequencies more obvious since when N is an even number, the zero and N/2 frequency does not have a matching pair in the relation
The Symmetry Of Real Valued Signals
If a signal is purely real, it has some interesting symmetries. Specifically, the discrete Fourier transform of a purely real valued sequence will result in a sequence where N-2 of the values are simply complex conjugates of each other[1][2][3]:
See Hermitian function for more details.
This symmetry is interesting because it implies that we don't actually need to remember all of the Fourier coefficients of a real valued signal in order to perfectly re-construct it. In fact, as long as we save the coefficients from N = 0 to N/2, we could just use the above relationship to get the missing coefficients back and complete the inverse Fourier transform.
What If We Just Drop Coefficients From N/2+1 to N?
Let's consider what would happen if we wanted to be even lazier and completely drop the coefficients from N/2+1 to N instead of indirectly calculating them. Let's begin with the formula for the inverse Fourier transform:
If we first consider values of N that are even, we can perform a trivial split on the inverse transform summation as follows:
Note that in the above expansion, the sum interval between 1 and N/2 -1 represents the 'low frequencies' and the sum interval between N/2 +1 and N-1 represents the 'high frequencies' (aka negative frequencies). Keep an eye on these terms as we'll draw some conclusions about them later. Then, for clarity's sake, let's simplify the special cases when n=0 or N/2 and stuff them into the variable C:
We then have:
Then consider that we can express the last summation formula as a count down from N-1 instead of a count up to N-1 and perform the substitution m = N - n:
Now, remember that
And perform further simplifications noting that e raised to a power that is an integer multiple of
If we then decompose
If we then note that
And after cancelling the imaginary parts, this simplifies to:
A similar analysis can be done when N is odd, but in this case the 'middle' frequency around N/2 now has a matching frequency through the
The resulting final simplification for N odd will be:
Now that we've gone through all of the math, we should be able to review the calculations above and consider how the result would change if we simply didn't even include the 'high' frequencies (aka negative frequencies) in the calculation of the inverse Fourier transform of a purely real signal. It should be possible to make the following observations:
- 1) The amplitude of the real part will be half of what it would have been if the high (aka negative) frequency contribution had been kept.
- 2) There will be a lingering imaginary part that would have otherwise been cancelled with the time domain contribution of the high (aka negative) frequencies.
Fact 2) isn't really a problem if we know that we're reconstructing purely real signals since we know that we can safely throw away any imaginary part time domain contribution. Fact 1) isn't really a problem either because we know that the overall shape of the waveform will be preserved and that we can simply multiply by two to achieve the amplitude of the original waveform.
In conclusion, if we want to accurately re-construct the time domain signal from the Fourier coefficients of a purely real signal, we can do so as long as we keep all of the Fourier coefficients up to
Sampled Audio And Band-limiting
If a signal is band-limited then it can be sampled and fully recovered only when observing the Nyquist Criterion[4] This is relevant to our consideration of which coefficients are important when re-constructing audio examples when we consider that some of the most commonly encountered audio sample rates are around 44khz to 48khz. The highest frequencies that humans can hear are around 20 to 24khz[5], and applying the Nyquist sampling Criterion to this would require a sampling rate of around 40khz to 48hkz. Given this sampling rate, analysis of the audio samples would produce frequency bins representing frequencies in the 24khz to 48khz range, but given that these are above the range of human hearing anyway omitting them shouldn't cause any audible difference.
What If We Just Drop Imaginary Parts From Coefficients?
The real part of coefficients quantifies the 'evenness' of the signal, and the imaginary part quantifies the 'oddness' of the signal. In the context of analysing frequencies found in audio, if all of the samples we considered always consisted of even function (cos for example), then discarding the imaginary parts would have no effect, since the original signal could be completely expressed in terms of even functions. However, in reality, whatever audio interval you analyze likely consists of cos functions that can be shifted 90 degrees to produce a sin function which is odd! You can see this in the example diagram above if you set it to play a cos wave with changing phase shift and in addition use the 'Force To Zero' buttons on both imaginary parts. When the cos function is in-phase, you get exactly the same signal. As it shifts toward being 90 degrees out of phase, the re-constructed signal gets attenuated to zero. As you go past 90 degrees to 180 degrees it gets inverted. After 180 degrees it attenuates back again, then after 270 degrees becomes a cos wave again.
Therefore, to address the question again: What if you simply drop the imaginary part of your stored Fourier transform coefficients? In this case, whenever your signal has frequencies that are in-phase with a cosine function, they will be unmodified. Any frequencies that are out of phase with a perfect cosine wave will tend to be attenuated as they approach 90 degrees out of phase, and will become inverted as they approach 180 degrees out of phase. The human ear is not particularly sensitive to phase information in audio, so whenever the phase shift is 0 or 180, there shouldn't be a perceptible difference in the tone. As the phase shift approaches 90 or 270 degrees, there should be a noticeable decrease in volume until it becomes inaudible for that particular frequency. Furthermore, complex sounds are made up of many frequencies, so these effects also create the opportunity to cause complex constructive and destructive interference effects. This will obviously cause distortion and inaccurate re-production of the original signal, but in practice I have found it to produce audio which is actually still quite understandable. In this case, if changes are made in the frequency domain in an ad-hoc manner, further work will be needed to be done in order to prevent popping noises due to endpoint discontinuities. A method such as overlap add or overlap save can address this problem.
What Are Negative Frequencies In The Fourier Transform?
Throughout the literature on the subject and in this document, the frequency bins from N/2 to N-1 are commonly referred to as the 'negative' frequencies. This interpretation of these frequencies as being negative is accurate since you can simply plug them into the sin or cos function with a negative sign and everything will work out mathematically. It is also correct to consider them as though they were positive frequencies too. In reality, the Discrete Fourier transform can't tell the difference. If you take the discrete Fourier transform of a sequence of N values, the contribution of each bin
Below, is an animation that shows how this effect of ambiguity between frequencies can occur with discrete sampling:
Conclusion
In this article, we've reviewed a number of different aspects of the discrete Fourier transform coefficients and how they affect the reconstructed audio. It was found that for purely real signals, half of the information in the Fourier coefficients is redundant. In addition, it was also found that it is possible to avoid half of the calculation when performing the inverse Fourier transform of real signals. This assumes that you discard the unnecessary un-cancelled imaginary part, and in addition, it must be noted that the resulting signal will have half amplitude. Furthermore, if distortion can be tolerated, it is possible to simply ignore the imaginary parts of the coefficients since the effect on the reconstructed audio will be to cause phase shifts and volume changes.
As a final note, this article represents the limits of my knowledge on this subject, and if you find any mistakes you can email me as info@robertelder.org.
References
[1] http://northstar-www.dartmouth.edu/doc/idl/html_6.2/Displaying_FFT_Results.html
[2] https://www.dsprelated.com/freebooks/sasp/Symmetry_DTFT_Real_Signals.html
[3] https://en.wikipedia.org/wiki/Discrete_Fourier_transform#The_real-input_DFT
[4] https://www.maximintegrated.com/en/app-notes/index.mvp/id/3628
[5] https://en.wikipedia.org/wiki/Hearing_range
Overlap Add, Overlap Save Visual Explanation
Published 2018-02-10 |
$35.00 CAD |
Using Fourier Transforms To Multiply Numbers - Interactive Examples
Published 2019-01-10 |
Endpoint Discontinuities and Spectral Leakage
Published 2018-02-10 |
The Regular Expression Visualizer, Simulator & Cross-Compiler Tool
Published 2020-07-09 |
Why Is It so Hard to Detect Keyup Event on Linux?
Published 2019-01-10 |
Myers Diff Algorithm - Code & Interactive Visualization
Published 2017-06-07 |
Interfaces - The Most Important Software Engineering Concept
Published 2016-02-01 |
| Join My Mailing List Privacy Policy |
Why Bother Subscribing?
|