Transformation

Written by Richard Murison

What is the biggest, most fundamental difference between Mathematics and Physics?  I would say that it is the fact that Mathematics is absolute.  Let me put it this way, our present understanding of Physics allows – in principle – for there to exist an infinite number of parallel universes, and for the laws of Physics in each of those universes to be different.  However, in each of those universes, the exact same rules of Mathematics would still apply.  Bizarre notions like these cause many people to look askance at hard science and prefer a simpler home-spun approach to life.  It is perhaps more comforting to simply dismiss Einstein’s theory of relativity, and the many mind-bending paradoxes it entails, while at the same time being prepared to rely unquestioningly on your GPS system, which would not work at all if not for a strict implementation of relativistic principles.  At least Mathematics tends to avoid the apparent paradoxes of advanced Physics.

The Fourier Transform is a nice example of a simple, yet powerful mathematical proof.  It arose from the realization that many continuous functions (a description that applies perfectly to an audio waveform) can be perfectly decomposed into a sum of individual pure-tone sine waves.  The Fourier Transform provides the exact mathematical relationship between the continuous function and its sine wave frequency components.  It is a relatively simple equation, but its use requires analyzing the continuous function over all time, from the infinite past to the infinite future, which clearly introduces some practical limitations.  For this reason, Fourier Transforms on real data can only ever be done in the digital domain.

The digital version of a Fourier Transform is called a Discrete Fourier Transform (DFT), and requires that the continuous function is sampled at regular intervals – which is good for digital audio.  However, the underlying principle still applies – the continuous function (the waveform) must still be processed over all time, including the infinite past and infinite future.  The way the DFT gets around this is that it takes a single finite snippet of the waveform and makes the assumption that this snippet is repeated ad infinitum into both the infinite past and future.

If this snippet does in fact repeat infinitely, then it must follow that any individual frequencies which comprise the waveform must also repeat infinitely.  In fact, they must more than just repeat.  Their phase relationships must also repeat.  In other words, during the specific duration of the waveform snippet, each frequency must go through an exact integer number of oscillations, so that the frequency component is at exactly the same phase of its oscillation at the end of the snippet as it was at the beginning.  That way, each repeating snippet, extending into the infinite past and future, must be exactly the same.

The lowest frequency F1 that fulfills this criterion is given by F1 = (Fs/N), where Fs is the sampling frequency, and N is the number of samples in the snippet.  All of the other frequencies that fulfill the criterion are its harmonics:  Fn = nF1.  Now, if we set n= N/2 then we get Fn = Fs/2 which is the Nyquist frequency.  Finally, I must add F0 =0 to the list, because we need to account for a DC component.  Therefore, in summary, a waveform comprising N data points at a sampling frequency Fs, and repeating infinitely, can comprise ONLY (N/2 + 1) frequencies given by:

Fn = (n/N)Fs,  where n = 0, 1, 2, 3, … N/2.

And this is exactly what a DFT delivers.  It transforms the N waveform values into (N/2 + 1) equally spaced frequencies from DC to the Nyquist frequency.  For each of these frequencies it tells you both the amplitude and the phase of the original waveform’s component at that frequency.

But can we relate what the DFT tells us about the waveform to the actuality of the waveform itself?  Can we relate it to what a proper Fourier Transform would have told us?  Are they the same thing?  Well, not quite.  Remember that the snippet of waveform we selected is assumed to repeat ad infinitum.  The problem is that where the end of each of those repeating segments joins up to the start of the succeeding segment, there is no guarantee that the join with be smooth.  In fact, it is almost assured that there will be an abrupt discontinuity at each of those boundaries.  Those discontinuities are not part of the original waveform, but they will by definition be fully represented within the DFT analysis.

Standard practice is to artificially fade out the signal at the start and the end of the snippet so that there is de facto no discontinuity at the join.  What this achieves is to replace an uncontrolled discontinuity with a controlled one.  This process is called ‘windowing’, and there are a large selection of useful windowing functions that can be gainfully employed.  Each of those different windowing functions will affect the way in which the resultant DFT relates to the original waveform itself, but other than introducing the concept, it is beyond the scope of this article to elaborate further.

Bear in mind that what the DFT tells us about the data snippet is not merely an approximation – it is a full and complete representation.  It tells you everything there is to know about the data that you feed it with.  In particular, anything that is not in the DFT is not in the data.  Similarly, anything that cannot be accommodated within the DFT representation cannot be encoded or captured within the data.  Despite what you might think, the data contains only the frequencies which the DFT spits out, and no others.

So, what happens if the original waveform from which we took our snippet contains a frequency which lies between two of the permitted frequencies spat out by the DFT (whose frequencies, you’ll recall, are determined by the number of samples in the DFT)?  Well, such a frequency will not fit neatly into the repeating DFT snippet with an exact number of cycles.  Therefore it will produce a discontinuity at the boundaries, and will therefore result in spurious data appearing within the DFT.  Managing this issue is the reason why windowing functions are important.  They control how that spurious data is distributed.  Those characteristics of windowing functions have been thoroughly analyzed, and are well understood, although it is a deeply technical subject.  Depending on what you are using the DFT to achieve, one windowing function may be a better choice than another.

I want to conclude by clarifying the relationship between a DFT and a FFT (Fast Fourier Transform).  The DFT is a transform – a relationship between two sets of numbers governed by a set of equations.  On the other hand, FFT is an algorithm, a methodology for implementing a DFT in practical terms by breaking the DFT down into progressively smaller pieces.  There is nothing, for example, that limits the number of samples on which a DFT can be performed.  But the most efficient FFT algorithms rely on the number of samples being an integer power of two, which is a limitation imposed only by the algorithm itself, and not by the underlying theorem.

Back to Copper home page

1 of 2