FOURIER TRANSFORM: How can i find the index of data points

Question

I am a senior in high school and am currently trying to conduct an exploration of Fourier Analysis, specifically using the Discrete Fourier Transform to analyse a chord played on my piano. Basically, I'd play a chord of 3 notes, deduce the different frequencies of the sound wave, and estimate the chord played. According to the formula below, I have recorded the sound wave of the Amplitude-time domain however I do not understand what is meant by the "index of data points" and how to find it from this graph. Is there any way someone could help with that, I am a bit unfamiliar with this. Thanks.

$$ \hat{f}_{k} = \sum_{j = 0}^{n - 1} f_{j} e^{- 2 \pi i k \frac{j}{n}} \tag{1} \label{1} $$

Where $\hat{f}_{k}$ is the Fourier coefficient, $k$ is the different frequencies, $n$ the number of data points, and $f_{j}$ being an index of the data points.

Answer 1

In your DFT equation variable $k$ is the integer "index" of your calculate spectral samples. The $k$ index sequence is 0, 1, 2, 3, ..., $n-1$. Let's call your DFT output sequence $F_k$. So your first calculated DFT output sample, $F_0$, is centered at $0f_s/n$ Hz, where $f_s$ is the sample rate (in Hz) of your $f_j$ time-domain samples.

Your second calculated DFT output sample, $F_1$, is centered at $1f_s/n$ Hz. Your third calculated DFT output sample, $F_2$, is centered at $2f_s/n$ Hz. And so on.

Because your $f_j$ time-domain samples are real valued, you only need be concerned with the first $n/2$ $F_k$ DFT output samples (the first half of the $F_k$ DFT output samples). That is, your "frequency range of analysis" goes from zero Hz to $F_s/2$ Hz.

Answer 2

Here some practical tips for your project.

Frequency resolution

As Richard has already pointed out in his excellent answer the frequency resolution is simply the sample rate divided by the FFT length. So if you have a sample rate of $48kHz$ and an FFT length of 2400 samples, the resolution will be $f_{\Delta} = \frac{48kHz}{2400} = 20Hz$. So you FFT values would correspond to frequencies 0Hz, 20Hz, 40Hz, 60Hz, etc. If you use Matlab or Octave as a language you need to also account for that fact that these languages use index "1" for the first element, whereas most other languages (C, Python, ect) use index 0.

The FFT provides a linear frequency grid (constant absolute difference). However human hearing (and thus musical instruments) use a logarithmic pitch grid (i.e. constant relative difference). Take a look at a table that shows the frequency of the musical notes: https://pages.mtu.edu/~suits/notefreqs.html

You'll notice that the low notes are VERY close together whereas the high notes have lots of space between them. For example the two lowest notes on a 4-string bass guitar ($E_1$ and $F_1$) are less than 2.5Hz apart. That means a frequency resolution 20Hz as described above will not be sufficient to distinguish between these two notes (unless you deploy some fairly complicated math on top of it). So they choice of FFT length will depend how stationary and clean your recording is and how low you want to go.

Start with a single note

A single note on the piano does NOT consist of a single frequency. You will have so-called harmonics. For example, if you play an $A_2$ with a nominal frequency of 110Hz you will see in the spectrum 110Hz, 220Hz, 330Hz, 440Hz, etc with varying amplitudes. In fact the ratio and distribution of these amplitudes determine much of the timbre of the instrument. The nominal note called "fundamental" does not need to have the highest energy and in some cases it may be missing altogether. What determines the perceived pitch is NOT the lowest or the strongest frequency, it's the spacing between the harmonics.

Make sure you can reliably detect a single note before trying chords.

Detecting chords

Even if you look at a spectrum of a simple triad (say C, E, G), you will see a LOT of spectral lines. The trick here is to look at spacing between lines and see of there is a regular pattern that emerges. If you are lucky, the lowest frequencies with significant energy are the musical notes, but that's not always the case. However, it's a good starting point and you can use the harmonic relationship to verify any "note hypothesis".

Good luck and have fun.

Answer 3

As others have already explained, the DFT is defined for integer multiples of the fundamental frequency, which is $\frac{f_{s}}{N}$, where $f_{s}$ is your sampling frequency and $N$ is the length of your signal. So, your DFT locations can be easily computed using that formula

For the note/chord detection, also known as fundamental frequency estimation, the basic idea for a single note is to find the median frequency and match that to the nearest known note. The frequency of the note being played is not guaranteed to have its harmonics evenly spaced between according to the DFT sample frequencies, so there will be slight variation in the distances between harmonics. The median distance between harmonics is typically a little better at achieving a more accurate fundamental frequency estimate, particularly at lower notes.

There is also the problem, as another user mentioned, that many low notes are more closely spaced together than high notes due to humans interpreting sound on a logarithmic scale as opposed to a uniform scale. For adequate resolution without any other processing, you would need a rather large FFT, which at that point the signal may start decaying, or in the case of extending this to a song, a new note may have started playing. This is an issue because often the middle third of a note (for plucked string instruments) is the ideal portion to analyze. One option for getting around this could be to use a channelizer, which divides the spectrum into a bunch of narrowband representations. Each narrowband representation will have a reduced sample rate, giving a much finer FFT grid for that narrowband signal, but you would have to perform the FFTs in parallel for each channel. Another option that I've seen thrown around in the past is a Mel-frequency cepstrum, but I'm not super familiar with the inner workings of this.

For extending this to multiple notes, harmonic comb filters are probably a good place to start. You would threshold the output of a series of harmonic comb filters for the notes of interest. Getting better results than this gets very complicated, and is the subject of much ongoing research. But definitely start with a single note and get that reliably working.