Fast Fourier Transform Tuner

How do guitar tuners work?
There’s music, maths and physics behind it! Here’s a little insight:

A “note” has a specific frequency.
Notes and their corresponding frequencies:

note freqInstruments get out of tune (whether you use them or not) and need to be “tuned back” to the correct notes so that musicians produce harmonies and not cacophonies!

A tuner tries to find out the note, i.e. the frequency of what it hears so that we can correct the note.
How does it do this?

The audio waveform is a spectrum with respect to time. It converts this to a spectrum with respect to frequency using what is known as a Fast Fourier Transform which looks something like this :
(frequency along the horizontal axis and amplitude along the vertical axis)

frequency spectrumThese peaks help us decide what the frequency of the sound is using a Harmonic Product Spectrum.

The details are a bit more complex than that. :

(If the Maths looks too daunting, skip to the part about decrypting chords in “A hard day’s night” )

———————————–FAST FOURIER TRANSFORM—————————————-

We start with a
Fourier Transform
It transforms a function f(t) in time space into a function g(k) in frequency space

fourier transformBut, while physically analyzing signals, we have discrete data points, hence we need a discrete version of the fourier transform:

Discrete Fourier Transform
N discrete points xi in time space transformed to points Xi in frequency space

discrete fourier transformN is the no. of points and n is the index no. of those discrete points

FFT  –  twiddling with the DFT

Making the DFT easily computable using the Radix 2 decimation in frequency algorithm

split summation

substitutionk caseseven kodd kfinal conversion dft

  =>            one  (N) DFT is converted to two  (N/2) DFT

Computing Two (N/2) DFTs is faster that computing one  (N) DFT
We continue splitting the summation in such a manner till we are left with 2 DFTs only
This is known as a butterfly-  a portion of the computation that combines results of smaller DFTs into larger DFTs or vice versa.

butterfly algorithm diagram

This is the algorithm employed to compute the Fast Fourier Transform (FFT)

The DFT algorithm complexity is proportional to N2
While FFT algorithm complexity is proportional to NlogN <  N2

Hence FFT is employed

——————————HARMONIC PRODUCT SPECTRUM————————————–

HPS is a method used in Pitch Detection Algorithm to estimate the fundamental frequency a quasi-periodic signal. (Other methods of PDA in the frequency domain are: cepstral analysis, maximum likelihood, Grandke interpolation, etc)

The human auditory system responds the most sensitively to the equivalent of the lowest common denominator (i.e. the FCF -highest common factor) of the produced frequencies which is  the fundamental frequency

Digitally,  how do we
-decide which peak to pick when there are multiple peaks
-account for noise that produces its own tiny peaks
-instruments themselves do not produce only a single frequency but a multitude of frequencies

The problem gets more complicated
If C4 (261.6 Hz) is played, harmonics C5 (523.3 Hz), A6 (1046.5 Hz), etc. will also be visible in the FFT frequency spectrum
But , the peak at fundamental frequency of 261.6 Hz is not necessarily the largest

This is where HPS comes into the picture

harmonic product spectrum diagram

The harmonic product spectrum is the geometric mean of amplitudes of the harmonics associated with a particular frequency in the spectrum:

harmonic product spectrum formula

The original spectrum is squeezed so that each successive harmonic of the original signal is aligned with the fundamental harmonic. To do this, the spectrum is squeezed by 1/2 to align the first overtone with the fundamental (it doesn’t matter what frequency the fundamental is at because the first overtone is always twice the frequency of the fundamental). Then the spectrum is squeezed to 1/3 to align the second overtone with the fundamental, and so on (typically for about 5 harmonics, higher harmonics have lower amplitude and will die down).

——————————————————————————————————————–
————————————-HOW DOES A TUNER WORK ?————————————

– analog sound waveform x(t) is recorded using a microphone
– an analog to digital conversion of a specific sampling rate provides a discrete time signal x(n)
– FFT of x(n) gives  X(k)
-find fundamental frequency using the FPS

—————————————-DECRYPTING CHORDS——————————————-

Using Fast Fourier Transforms to solve some of the mysteries of the music world!

a hard days night album coverThe opening chord to “A Hard Day’s Night” (1964) by the Beatles was a mystery for many years. The exact notes of the chord were often debated . When George Harrison was questioned about it in an interview in 2001, this is what he had to say:

Q: Mr. Harrison, what is the opening chord you used for ” A Hard Day’s Night”?
A: It is F with a G on top, but you’ll have to ask Paul about the base note to get the proper story

Apparently, no one knew the exact chord, no one could reproduce it perfectly!

James Brown, Beatles fan and a professor at the Faculty of Computer Science, Dalhousie University (Canada) used the FFT to decrypt what the chord could be

The chords notes were estimated using fourier analysis
-a 1 second window was selected
-29,375 frequencies were present
-only notes above at certain threshold frequency were observed
-frequencies were written in terms of the no. of semitone above or below a reference frequency
-the type of intruments used had to be taken into consideration

He worked along these line. To read his paper click here

After extensive analysis, this is what he found the chord to be:

a hard days night opening chord

Fourier Transforms seem to have some really interesting applications in Music !

———-SOURCES

Theory:
Report on Fast Fourier Transform Guitar Tuner (EE 113D Final Report, Winter 2011) by Jeff Wang and Kay-Won Chang
Lecture notes on The Fourier Transform and it’s Applications by Prof. Brad Osgood, Electrical Engineering Department, Stanford University
Music- a Mathematical Offering by Dave Benson, Department of Mathematics, University of Aberdeen
Mathematics, Physics and A Hard Day’s Night by Jason I. Brown, Dalhousie University
Pitch detection methods review, Stanford University
Harmonic Spectrum by Mazurka Project, Centre for he History and Analysis of Recorded Music

Programs:
By  Dr. William A. Steer

Spectrum Analyzer (SpecAn_3v5)    and    Tuner (tuner1v3)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s