From WolfWikis

Fourier transforms

Fourier transforms are everywhere in science, but I introduced them rather surreptiously in the previous chapter. Few people realize that they are just another application of group theory. Let's look at a few properties.

FFT and its quirks

The term Fast Fourier Transform refers to a particular algorithm that makes it possible to perform a Discrete Fourier Transform as fast as possible on a computer. The algorithm itself adds a few quirks to our story, but they do not really require a full description of the algorithm. The most important quirk is that it is much easier to perform an FFT if the number of data points (the size N of our translation group) is a binary power: N=2ⁿ= 2,4,8,16,32,64, etc. This requirement is not absolute. If e.g. N=2ⁿ.3^m, e.g. N=32*9=288 the algorithm gets a little more involved and a wee bit slower but not seriously so.

Some software allows other primes than 2, although e.g. the FFT in Excel does not. However if N contains factor of large prime numbers, say N=1001 one may be hard pressed to find software designed to do the trick. In such cases it may be useful to add 23 dummy data points, unless you really like to program...

The conjugate symmetry of the FFT

We need to examine the question of conjugate irreps a little more closely. Let's do that with a slightly larger translation group T⁸.
Its generating root-of-one is ε=exp(2πi/8) = √i = (1+i)/√2

	E	t	t2	t3	t4	t5	t6	t7
Γ0	1	1	1	1	1	1	1	1
Γ1	1	√i	i	i√i	-1	-√i	-i	-i√i
Γ2	1	i	-1	-i	1	i	-1	-i
Γ3	1	i√i	-i	√i	-1	-i√i	i	-√i
Γ4	1	-1	1	-1	1	-1	1	-1
Γ-3	1	-i√i	i	-√i	-1	i√i	-i	-i√i
Γ-2	1	-i	-1	i	1	-i	-1	i
Γ-1	1	-√i	-i	-i√i	-1	√i	i	i√i

From the above table we can see that there is a form of symmetry around Γ₄. This irrep functions as a kind of mirror plane around which the irreps occur in complex conjugate pairs. (Actually we could say the same about Γ₀ if you look at the complex plane, we will revisit that point). The conjugate mirror means that if we apply an FFT on a real data set of 8 points this symmetry will also appear in the results. Instead of doing this by hand, let me show you the results as obtained using the FFT module that is contained in the Data Analysis pack of Excel.

Conservation of information

The symmetry is a consequence of the fact that the original data consist of real numbers. There are exactly 8 independent reals in both representations of the data (indicated in pink). The other numbers in the data on the right can either be derived by taking an complex conjugate or, in the case of the totally symmetric irrep Γ₀ and what is known as the Nyqvist frequency: Γ₄ they are zero. (In fact the figure in the complex plane gives a hint why this is so. Both ε⁰=1 and ε⁴=i are on the conjugate mirror plane. This means that both Γ₄ and Γ₀ must be their own conjugates, in other words they must be real!) The order in which we listed our irreps above is essentially arbitrary. We could also list the negative ones above the zero one and think of their frequencies as negative in stead of larger than the Nyqvist one:

In a sense the negative frequencies behave as a kind of alias for the frequencies above Nyqvist and we will revisit this important point.

The eight 'pink' reals illustrate an important point about decompositions using irreps (and thus of FFT's): we neither create nor lose information. We had eight pieces of information and we still have exactly eight after decomposition.

If we were to transform a set of 8 complex numbers, e.g. data obtained in complex impedance measurements the conjugate symmetry would no longer hold.

It is possible to perform manipulations on the data in the frequency domain and transform the data back to the time domain. However care should be taken to maintain the conjugate symmetry, otherwise the result will not be a real data set but a complex one.

Some important cases of FFT's

1. The FFT of a random signal of normal distribution (white noise) is a random signal. I.e. it contains all frequencies equally in magnitude but with random phases.
2. The FFT of a Gaussian is a Gaussian, but with inverse width. Narrow becomes broad and vice versa.