Apply Fourier transform to create a guitar tuner on Android. Part 1

The basis of the spectral analysis of audio data is an algorithm called the Fourier transform. When unfolding the original sound signal into frequency components, the individual frequencies are called harmonics. The main harmonic determines the pitch of the sound, and the minor harmonics determine its timbre. There are many mobile applications that use Fourier transform in order to display the entire spectrum of frequencies (harmonics). Also, there are mobile applications that serve to customize guitars. They work according to the principle: the main harmonic is at the highest amplitude value in the spectrum. This statement is not quite true, because the main harmonic is determined by the smallest of all multiples of this harmonic, or the step between the harmonics. There is a need to find a way to display the value of the main harmonic in the spectrum of the sound signal.

In the first part of the article we will consider the principle of the discrete Fourier transform, as well as the ability to record sound data from an Android device using the AudioRecord class.

DFT, FFT. JTransforms Library.

Audio data recorded in the form of pulse code modulation (PCM), show the amplitude of the sound wave at a particular point in time. In the 19th century, Jean Baptiste Fourier proved that any periodic signal can be represented as the sum of an infinite series of simple sinusoidal signals. From which it follows that our original audio signal can be represented as a sum, ordered by frequency, of simple sinusoidal signals with their own amplitudes. Thus, to move from one dependence (amplitude-time) to another (amplitude-frequency). Such a transform is called a Fourier transform.
')
To calculate the Fourier transform on computers, we introduced the concept of the discrete Fourier transform (DFT), which requires a discrete function as an input.

Consider the principle of the discrete Fourier transform in a Java programming environment. To begin with, we describe some function that will represent the sum of two harmonics (cosines) with frequencies of 100 Hz and 880 Hz, respectively.

private double someFun(int index, int sampleRate) { final int amplitudeOfFirstHarmonic = 15; final int amplitudeOfSecondHarmonic = 1; final int frequencyOfFirstHarmonic = 100; final int frequencyOfSecondHarmonic = 880; return amplitudeOfFirstHarmonic * Math.cos((frequencyOfFirstHarmonic * 2 * Math.PI * index ) / sampleRate) + amplitudeOfSecondHarmonic *Math.cos((frequencyOfSecondHarmonic * 2 * Math.PI * index) / sampleRate); } 

As the sampling frequency, we take the value of 8000 Hz and fill the array of 8000 elements with data, calling the function someFunc () in a loop

 final int sampleRate = 8000; final int someFuncSize = 8000; double[] someFunc = new double[someFuncSize]; for (int i = 0; i < someFunc.length; i++) { someFunc[i] = someFun(i, sampleRate); } 

As a result, we get an array of values ​​that defines the discrete representation of our function. For a visual representation of the data, we derive the values ​​obtained from the array into a .csv file and plot the graph in Excel


As can be seen from the diagram, a harmonic with a frequency of 100 Hz has an amplitude of 15, the value of which was indicated in the amplitudeOfFirstHarmonic constant. Above the first harmonic with a frequency of 100 Hz and an amplitude of 15, the second harmonic is drawn with a frequency of 880 Hz and an amplitude equal to one.
By the same principle, we create two basic functions of cosine and sine. Only now, we will pass the frequency value into the parameters of the methods of our basic functions.

 private double cos(int index, int frequency, int sampleRate) { return Math.cos((2 * Math.PI * frequency * index) / sampleRate); } private double sin(int index, int frequency, int sampleRate) { return Math.sin((2 * Math.PI * frequency * index) / sampleRate); } 

Now, define the method that will perform the discrete Fourier transform. As parameters of the method, we will give an array of values ​​of the initial discrete function consisting of the sum of simple cosines and the sampling frequency of this function.

 private double[] dft(double[] frame, int sampleRate) { final int resultSize = sampleRate / 2; double[] result = new double[resultSize * 2]; for (int i = 0; i < result.length / 2; i++) { int frequency = i; for (int j = 0; j < frame.length; j++) { result[2*i] +=frame[j] * cos(j, frequency, sampleRate); result[2*i + 1] +=frame[j] * sin(j, frequency, sampleRate); } result[2*i] =result[2*i] / resultSize; result[2*i + 1] = result[2*i + 1] / resultSize; } return result; } 

After performing the Fourier transform, the obtained values ​​determine the projections of all the vectors ordered by frequency on the axes of cosines and sines. In order to find the length of such a vector, it is necessary to apply the Pythagorean theorem$$ $ inline $ A = \ sqrt {a ^ 2 + b ^ 2} $ inline $ .

 double[] result; long start = System.currentTimeMillis(); result = dft(someFunc, sampleRate); long finish = System.currentTimeMillis(); long timeConsumedMillis = finish - start; System.out.println("Time's dft: " + timeConsumedMillis); double[] amplitude = new double[sampleRate/2]; for (int i = 0; i < result.length / 2; i++) { amplitude[i] = Math.sqrt(result[2*i]*result[2*i] + result[2*i+1]*result[2*i+1]); System.out.println(i + ": " + "Projection on cos: " + result[2*i] + " Projection on sin: " + result[2*i + 1] + " amplitude: "+ amplitude[i] + "\n"); } 

As a result of executing the code from the previous listing, we got the representation of our discrete function someFunc () as a set of amplitude values, which are ordered by frequency, from zero to half of the sampling rate.

Thus, for harmonics with frequencies of 100 Hz and 880 Hz, the amplitude values ​​will correspond to those specified in the amplitudeOfFirstHarmonic and amplitudeOfSecondHarmonic constants of the someFunc () method. And for the other harmonics, which remains exactly 3998, the amplitude values ​​will be close to zero, because the other harmonics were not defined in the original discrete function someFunc (), which was transmitted to the discrete Fourier transform.




Let's output the amplitudes obtained after the Fourier transform of the function someFunc () to the .csv file and plot the graph in Excel. As a result of the Fourier transform, we get the spectrum of the original signal



The discrete Fourier transform algorithm on the computer runs in time.$$ $ inline $ O (n ^ 2) $ inline $ that is too slow. For fast calculations of the discrete Fourier transform, a fast Fourier transform (FFT) was invented. The FFT algorithm performs calculations using a recursive approach, due to which the execution time of the algorithm is reduced to$$ $ inline $ O (n * \ lg {n}) $ inline $ . There is a ready-made implementation of the FFT algorithm in the Java programming environment, which is represented as a JTransforms library.

Record data from a microphone. Audiorecord

AudioRecord class is responsible for receiving PCM audio data from a mobile device on the Android platform.
To create an instance of the AudioRecord class, in the constructor of the AudioRecord class, you must specify the following parameters:

• audioSource - the source from which to record.
• sampleRateInHz is the sampling rate in Hertz.
• channelConfig is the type of audio channel.
• audioFormat is a data encoding format.
• minBufferSize - minimum buffer size.

After creating an instance of the AudioRecord class, you must call the startReading () method, which will start recording from a mobile device. Recorded audio data will be stored in the AudioRecord class internal buffer in the chunk size specified in the minBufferSize parameter when creating an instance of the class. From the internal buffer of the AudioRecord class, it is necessary to periodically retrieve the recorded data by calling the read () method of the AudioRecord class.
For example, we will record the sound data from a mobile device, and then we will output this data into a text file .csv and plot the received sound data using Excel


When creating an instance of the AudioRecord class, we use a sampling rate of 8000 Hz and a buffer size of 1024.

If this part of the article was interesting, then in the second part of the article we will deal with the creation of a guitar tuner on Android.