DSP Theory
The Discrete Fourier Transform (DFT) is a change of basis on a length N discrete time signal accomplished by the following mathematical transformation:
As one may see, the DFT is a method converting a discrete time signal to frequency.
In our project we used the Fast Fourier Transform (FFT) due to our need for a quick transform into the frequency domain. The FFT is an algorithimic implementation of the Discrete Fourier Transform (DFT). The FFT decreases the computation time of large sequences significantly. This decrease is completed in a number of ways of reusing calculations, but the result is a decrease from O(n2) to O(n log(n)). Since a key section of project is identifying pitch, working in the frequency domain is much more attractive than the time domain.
In Matlab, the FFT gives an output in sample. For our analysis, we would prefer the output to be in hertz. To accomplish this conversion we used the following equation, where Fs is our sampling frequency and N is the length of our signal:
The DFT Algorithm
