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
Which pitch?
In western music, some frequencies have names:
..., 
, 
, 
, 
,
, 
, 
, 
, 
, 
, 
, 
, 
, 
, 
...
The subscript denotes the octave
For the rest of the presentation, it is very useful to rename:
...
...
...
-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?
...
...
...
-1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
...
Back to frequency names
...
...
...
-1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
...
A lot of people remember 
(= 9), corresponds to 440 Hz
Write this as 
A semitone higher, means frequency increases by factor 
:
So,
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:
But the same formula holds for negative k
Putting everything together,
Hz = 440 × 
Hz
And from the frequency, we can go back to n
We found relationship between frequency f and note n
Hz
So,
= 
= 
n = 9 + 12 
Summary
In western music, some frequencies got names, we gave alternative names:
...
...
...
-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 × 
Hz
And if we have a frequency f, the corresponding semitone n is
n = 9 + 12 
Table of Frequencies
-1
246.94 Hz
0
261.63 Hz
1
277.18 Hz
2
293.66 Hz
3
311.13 Hz
4
329.63 Hz
5
349.23 Hz
6
369.99 Hz
7
392.00 Hz
8
415.30 Hz
9
440.00 Hz
10
466.16 Hz
11
493.88 Hz
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...
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 
, k=1,2,3, ...
If for instance, there is a lot of a building block with frequency 
in the vibration of the air, you will probably also hear a sound with that frequency
Plot of 
Plot of 
Plot of 
Plot of 
Sampling: consider signal at N points in time
At: points t/T = 0/N, 1/N, ..., (N-1)/N
Store values in a list / array / vector
In[1]:=
Out[1]=
If you pick more points, it looks more like real plot
Sample sin(
) and put it in vector 
, for k = 1, ..., N/2-1
Sample 
and put it in vector 
for k=0,...,N/2
Build a signal y from samples of cos and sin
Want to find 
and 
such that
Dot product
The dot product takes two vectors of same size N
and calculates a real number,
Some properties:
Dot product
Write |x| for the length of x. Then
If x and y are perpendicular,
Building components are perpendicular to each other
Also, for 0 < k < N/2
Finally,
It gives us a great trick
Remember: we want to find 
and 
such that
Take dot product of both sides with 
So 
!
The Transformation
You get the rest of the coefficients in the same way:
A little test
In[5]:=
In[6]:=
Out[6]=
In[2]:=
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
A little FFT
The most famous version of FFT is the Cooley-Tukey algorithm, basic idea: (divide and conquer)
/ \
, 
, 
/ \ / \
FFT( 
, 
) FFT( 
, 
) FFT(
, 
) FFT( 
, 
)
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 
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,
For every integer k , k multiple of N/2
For every integers k and l,
And if k ≠ l,
