Presentation_1.gif

What I am going to speak about

Sound waves, frequencies, musical notes

Our tool: Fast Fourier Transform

Putting it to the test:
Can my computer recognize pitch?

Waves and frequencies

If you whistle, sing or strum a guitar, you create vibrations in the air

If you look over a short interval in time, a vibration seems periodic

The period T is the time after which signal repeats itself

The frequency f is the reciprocal of the period: f = 1/T

Presentation_2.gif

Which pitch?

In western music, some frequencies have names:
..., Presentation_3.gif, Presentation_4.gif, Presentation_5.gif, Presentation_6.gif,Presentation_7.gif, Presentation_8.gif, Presentation_9.gif, Presentation_10.gif, Presentation_11.gif, Presentation_12.gif, Presentation_13.gif, Presentation_14.gif, Presentation_15.gif, Presentation_16.gif, Presentation_17.gif ...

The subscript denotes the octave

For the rest of the presentation, it is very useful to rename:

... Presentation_18.gif Presentation_19.gif Presentation_20.gif Presentation_21.gif Presentation_22.gif Presentation_23.gif Presentation_24.gif Presentation_25.gif Presentation_26.gif Presentation_27.gif Presentation_28.gif Presentation_29.gif Presentation_30.gif Presentation_31.gif Presentation_32.gif ...
... -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 ...

We will write n for such a number, and we call it a semitone

So ... What is a G 6?

... Presentation_33.gif Presentation_34.gif Presentation_35.gif Presentation_36.gif Presentation_37.gif Presentation_38.gif Presentation_39.gif Presentation_40.gif Presentation_41.gif Presentation_42.gif Presentation_43.gif Presentation_44.gif Presentation_45.gif Presentation_46.gif Presentation_47.gif ...
... -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 ...

Presentation_48.gif

Back to frequency names

... Presentation_49.gif Presentation_50.gif Presentation_51.gif Presentation_52.gif Presentation_53.gif Presentation_54.gif Presentation_55.gif Presentation_56.gif Presentation_57.gif Presentation_58.gif Presentation_59.gif Presentation_60.gif Presentation_61.gif Presentation_62.gif Presentation_63.gif ...
... -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 ...

A lot of people remember Presentation_64.gif (= 9), corresponds to 440 Hz
Write this as Presentation_65.gif

A semitone higher, means frequency increases by factor Presentation_66.gif:

Presentation_67.gif

So,

Presentation_68.gif

An octave higher means double the frequency!

We can give a formula for the frequency

f( 9 ) = 440 Hz

If k is a number larger than 0:

Presentation_69.gif

But the same formula holds for negative k

Putting everything together,
Presentation_70.gif Hz = 440 × Presentation_71.gif Hz

And from the frequency, we can go back to n

We found relationship between frequency f and note n

Presentation_72.gifHz

So,
Presentation_73.gif = Presentation_74.gif

Presentation_75.gif = Presentation_76.gif

n = 9 + 12 Presentation_77.gif

Summary

In western music, some frequencies got names, we gave alternative names:

... Presentation_78.gif Presentation_79.gif Presentation_80.gif Presentation_81.gif Presentation_82.gif Presentation_83.gif Presentation_84.gif Presentation_85.gif Presentation_86.gif Presentation_87.gif Presentation_88.gif Presentation_89.gif Presentation_90.gif Presentation_91.gif Presentation_92.gif ...
... -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 ...

Then the frequency of semitone  n  is f( n ) = 440 × Presentation_93.gif Hz

And if we have a frequency f, the corresponding semitone n is
n = 9 + 12 Presentation_94.gif

Table of Frequencies

Presentation_95.gif -1 246.94 Hz
Presentation_96.gif 0 261.63 Hz
Presentation_97.gif 1 277.18 Hz
Presentation_98.gif 2 293.66 Hz
Presentation_99.gif 3 311.13 Hz
Presentation_100.gif 4 329.63 Hz
Presentation_101.gif 5 349.23 Hz
Presentation_102.gif 6 369.99 Hz
Presentation_103.gif 7 392.00 Hz
Presentation_104.gif 8 415.30 Hz
Presentation_105.gif 9 440.00 Hz
Presentation_106.gif 10 466.16 Hz
Presentation_107.gif 11 493.88 Hz
Presentation_108.gif 12 523.25 Hz

Alternative music notation

Besides the classical music notation, there are alternative suggestions

Very interesting ones make use of chromatic scales: in such a case, the distance between a semitone n and a semitone n+1 is always the same

My favorite notation graphs the semitones you hear as a function of time

Alternative music notation example

Let's continue with FFT now...

Presentation_109.gif

Let's continue with FFT now...

FFT has many many applications

Music Analysis and Speech Analysis

Image Analysis, Image compression

Simulation of fluids and many other physical systems

Filtering

Making money (Finance):

...

What FFT does...

FFT takes a periodic signal apart into easy building blocks

The building blocks are sine's and cosine's of different frequencies Presentation_110.gif, k=1,2,3, ...

If for instance, there is a lot of a building block with frequency Presentation_111.gif in the vibration of the air, you will probably also hear a sound with that frequency

Plot of Presentation_112.gif

Presentation_113.gif

Plot of Presentation_114.gif

Presentation_115.gif

Plot of Presentation_116.gif

Presentation_117.gif

Plot of Presentation_118.gif

Presentation_119.gif

Sampling: consider signal at N points in time

At: points t/T = 0/N, 1/N, ..., (N-1)/N

Presentation_120.gif

Store values in a list / array / vector

In[1]:=

Presentation_121.gif

Out[1]=

Presentation_122.gif

If you pick more points, it looks more like real plot

Presentation_123.gif

Sample sin(Presentation_124.gif) and put it in vector Presentation_125.gif, for k = 1, ..., N/2-1

Presentation_126.gif

Presentation_127.gif

Sample Presentation_128.gif and put it in vector Presentation_129.gif for k=0,...,N/2

Presentation_130.gif

Presentation_131.gif

Build a signal y from samples of cos and sin

Want to find Presentation_132.gif and Presentation_133.gif such that

Presentation_134.gif

Presentation_135.gif

Dot product

The dot product takes two vectors of same size N

Presentation_136.gif

Presentation_137.gif

and calculates a real number,

Presentation_138.gif

Some properties:

Presentation_139.gif

Dot product

Write |x| for the length of x. Then

Presentation_140.gif

If x and y are perpendicular,

Presentation_141.gif

Building components are perpendicular to each other

Presentation_142.gif

Also, for  0 <  k  < N/2

Presentation_143.gif

Finally,

Presentation_144.gif

It gives us a great trick

Remember: we want to find Presentation_145.gif and Presentation_146.gif such that

Presentation_147.gif

Take dot product of both sides with Presentation_148.gif

Presentation_149.gif

So Presentation_150.gifPresentation_151.gif Presentation_152.gif  !

The Transformation

You get the rest of the coefficients in the same way:

Presentation_153.gif

A little test

In[5]:=

Presentation_154.gif

In[6]:=

Presentation_155.gif

Out[6]=

Presentation_156.gif

Presentation_157.gif

Presentation_158.gif

Presentation_159.gif

In[2]:=

Presentation_160.gif

I'm sorry, this was not FFT

What I told you is true, and it works for our purposes, but it is not yet FAST

Rather than the FFT, I explained the Discrete Fourier Transform

Actually, there is no 'FFT'.  There are a lot of ways to make the above algorithm fast, and they are all called FFT

Presentation_161.gif

A little FFT

The most famous version of FFT is the Cooley-Tukey algorithm, basic idea: (divide and conquer)

        Presentation_162.gif
            /                \
                   Presentation_163.gif, Presentation_164.gif, Presentation_165.gif        Presentation_166.gif
                     /                \                /            \
    FFT( Presentation_167.gif, Presentation_168.gif )    FFT( Presentation_169.gif, Presentation_170.gif )        FFT(Presentation_171.gif, Presentation_172.gif)       FFT( Presentation_173.gif, Presentation_174.gif)

Putting it to the test

The setup

Voice or guitar to microphone in

Soundcard samples signal from microphone

A computer program asks soundcard for sample data

Program performs FFT

Program displays Presentation_175.gif for the different values of k

The computer program

Open source computer program Frequency Analyzer

Modified to the ‘note’ scale rather than the frequency scale

Conclusion

I hope you have some idea of what FFT is

If you are continuing in exact sciences, you will definitely meet FFT later in your life, it is extremely useful

There is a lot more to say and discover on this subject. I put a few references on the next slide

The slides will be available on the Csplash website, and on my website:
www.cims.nyu.edu/~jim

On my website you can also find links to more information, and a link to Frequency Analyzer, so you can try it out for yourself

Appendix

For every integer k, k not a multiple of N/2,

Presentation_176.gif

For every integer k , k multiple of N/2

Presentation_177.gif

For every integers k and l,

Presentation_178.gif

And if k ≠ l,

Presentation_179.gif

Spikey Created with Wolfram Mathematica 8.0