Python Programming for Biology: Bioinformatics and Beyond

The theory of FFT

Fourier  transformation  is  effectively  the  weighted  summation  of  sinusoidal  waves  that

reproduces  the  original,  oscillating  signal.  The  transformed  frequency  plot  (often  called

the spectrum) is then the graph of the amount of each frequency found.

If we consider a signal sampled uniformly in time, so that there is time Δt in between

every measurement, we can represent the series of values as x

k

, where k is the time index

(k = 0, …, N−1). Assuming that the first measurement is made at time t = 0, the signal x

k

is

measured  at  time  k  multiplied  by  Δt.  Here  we  allow  the  x

k

 to  be  complex  numbers,

although  we  could  instead  restrict  them  to  being  real  numbers.  The  discrete  Fourier

transform  of  this  signal  gives  the  amount  of  frequency  y  at  frequency  index  j.  This  is

calculated by measuring the amount of coincidence between the signal values and a pure

sinusoid at each frequency. Hence, we sum, over all the time points k, the signal value x

k

multiplied by the sinusoid value for frequency index j:

Here the minus sign in the exponent is a convention. For each frequency point j there are

N  terms  in  the  sum  and,  since  j  itself  has  N  possible  values,  there  are  N

2

 operations  to

determine the entire transformed signal. We use the notation O(N

2

) to describe this where

the  ‘O’  stands  for  the  ‘order’,  or  approximate  number,  of  the  operations.  In  fact  we  can

view this transform as a multiplication of a matrix by a vector, where the vector is x

k

and

the matrix has components as given by the exponential term in the sum. O(N

2

) algorithms

are not ideal in computing because if you scale N by say 10 then the number of operations

scales by 100.

Note that although we restrict the range of j to be between 0 and N−1, one could allow

an arbitrary integer j, noting that if we add the total sampled width N (or multiples thereof)

to a frequency there is no difference in the sum.

5

For example, sampling 10 points along

an  oscillation  of  frequency  1  gives  the  same  result  as  a  frequency  of  11,  where  faster

oscillations match the same heights at the sampled points. Thus the transformed signal is

periodic with period N.

---

In the 1960s, Cooley and Tukey published a fast algorithm for determining the discrete

Fourier transform when N is a power of 2.

6

The number of operations for the algorithm is

O(N log N), which is much better than O(N

2

) for large N, and this has become the basis for

the  widespread  use  of  Fourier  transforms  in  science.  Later  developments  improved  the

algorithm,  for  example,  to  deal  with  the  case  when  N  was  not  an  exact  power  of  2,  and

generalisations  to  other  transforming  functions  than  the  simple  exponential,  to  give  a

‘wavelet’ transform.