Frequencies represented in a DFT list (Fourier[])

Question

I have a sound sample (sample rate: 44100).

When I have a list l with n successive elements from the sample, Fourier[l] returns a list with n elements.

Which frequency is represented at the nth place in the Fourier-transformed list?

Answer 1

Here is an explicit way to calculate the frequency corresponding to each element of the output of the Fourier command. The frequencies will depend on two values: the sampling interval and the number of points in the data analysis.

ssf = RotateRight[Range[-n/2, n/2 - 1]/(n sampInt), n/2];

where n is the number of points analyzed and sampInt is the time between sampling points. The first half of ssf gives the positive frequencies and the second half shows the negative frequencies (as this is how they are arranged in the output of Fourier).

To see this in action, here is a 3000 Hz sine wave.

n = 2048;
sampInt = 1.0/44100;
data = Sin[2 Pi 3000 Range[1, n] sampInt];
ssf = RotateRight[Range[-n/2, n/2 - 1]/(n sampInt), n/2];
fft = Fourier[data, FourierParameters -> {-1, 1}];
ListPlot[Transpose[{ssf, Abs[fft]}], PlotRange -> All, Filling -> Axis]

This looks a lot like the classic Fourier transform of a sinusoid (showing both positive and negative frequencies). It is also easy to plot the corresponding phase values by replacing Abs with Arg

ListPlot[Transpose[{ssf, Arg[fft]}], PlotRange -> All, Filling -> Axis]

To help understand the ssf vector, observe that the DC (zero-frequency) term appears in the first element so that ssf[[1]] is zero and fft[[1]] is the value of the DC term (the mean value of the data). The value of ssf[[2]] (in this case 21.5 Hz) is the smallest frequency that can be resolved by this analysis window. All other terms are integer multiples of this fundamental frequency. The highest frequency that can be represented is the Nyquist rate (22050 Hz = 44100/2 in this case). Because the data signal is real-valued, the spectra above have the left-right symmetries, which is why one often (as pointed out by Szabolcs) only needs to look at the positive frequencies.

What is the meaning of these negative frequencies?

These are basically the result of Euler's formula (see the section on "Relationship to trigonometry"), which combines a positive and a negative frequency to give a real-valued sinusoid. For example,

Clear[t];
sig[n_]:= fft[[n]]*Exp[I Pi ssf[[n]] t] + fft[[-n + 1]]*Exp[I Pi ssf[[-n + 1]] t]

indexes into fft and ssf to add together two complex-valued sinusoids (the Exp functions) with appropriate arguments. Then it is easy to calculate

ExpToTrig[sigN[140]] // Chop

0.832817 Cos[9403.15 t] - 0.116205 Sin[9403.15 t]

which shows how the two complex-valued exponentials combine (with appropriate weightings and frequencies) to give a real-valued signal.

Answer 2

The $k^\text{th}$ element of the result will be the coefficient of the wave that has $k-1$ full periods in the complete sample. Thus if the length of your sample is $t$ time units, the $k^\text{th}$ element of the result will correspond to frequency $\frac{k-1}{t}$, regardless of the sample rate.

It should be noted that due to aliasing, element $k$ of a result of length $n$ will correspond to the same frequency as $n-k+2$ for $k=2..n$. Usually one is interested in amplitudes only, not phase, i.e. you're working with (Abs@Fourier[sample])^2. Because the input is real you only need to use elements $k = 2..\lceil \frac{n}{2}\rceil$.