CS 353 Fall 2020 Syllabus Labs/Projects

Project 04 Setup FFT Frequency Detector Extensions Submission

Project 04	Goals Implement the FFT algorithm. Use the FFT algorithm to detect frequency with the largest magnitude from a microphone input. Determine nearest musical note from frequency. Visualize the note with the LED.
Setup	Setup Start with your code from Lab 4. Save it as a new Arduino project titled `colbyUsername_P04` (with your colby username, mine would be `hewolfe_P04`). Timer Setup Starting with the compare match timer1 from the lab, modify your prescalar and OCR1A so that the timer is called at 2000Hz. Create a global array of integers `data` that is the length of your sampling window (128). In `ISR(TIMER1_COMPA_vect)` fill the data array cyclically (like the array for the rolling average in Project 1). Test your code to make sure that the data array fills up in approximately 32 milliseconds. Library Setup Create a library FFT, create headers and constant tables in the .h file, and implement the functions in the .cpp file. Add a header guard to the top of `FFT.h` Sine / Cosine look-up table and functions Hardcode a constant lookup table for powers of 2. It should be 12 unsigned integers representing 2⁰ to 2¹¹. Hardcode a constant 91 unsigned char sine lookup table. This should represent 255sine(0^o) to 255sine(90^o) rounded to the nearest integer. Create a function that calculates sine using the lookup table. Parameters: integer in degrees (any value) Return: float, (lookup table value divided by 255). Create a function that calculates cosine using the lookup table. Write code to test your approximation functions, include negative values, positive values and values > 360 and < -360.
FFT	Fast Fourier Transform Implement the `float FFT(int in[], int p, float Frequency, float f_peaks[])` function. This function will update a global float array, `peaks` with the top 5 frequency peaks. Input Parameters in[]: input array (data) p: power of 2, where 2^p=Number of samples Frequency: sampling frequency required as input (Hz) peaks: array to return the frequencies with the largest magnitude Set-up Data in FFT function Create an array, `index`, the same length as the input data, that contains the indicies of the rearranged array using bit reversal. `{0,1,2,3,4,5,6,7}` becomes `{0,4,2,6,1,5,3,7}` Create an array of floats, `ft_a`, the same length as the input data, that contains the input rearranged based on the bit reversal indexing. This will be used to store the amplitude later. Create an array of floats, `ft_b` which is the same length as the input data. This will be used to store the imaginary component and frequency later. Implement the iterative fft algorithm below (pseudocode) The result of this algorithm is ft_a and ft_b the DFT of input array. F represents an array of complex numbers with ft_a as the real component and ft_b as the imaginary component. Do not actually create an array F. n = f.length for s = {0, 1, ... log2(n)-1 } do m = 2^s angle = -360/(2^s+1) for j = {0, 1, ... m-1} do cos = cosine(anglej) sin = sine(anglej) n1 = j for k = {0, 1, 2, ... n/(2^s+1)} do complex = (cosft_a[m+n1]-sinft_b[m+n1], sinft_a[m+n1]+cosft_b[m+n1]) F[m+n1] = F[n1] – complex F[n1] = F[n1] + complex n1 += 2m Find peaks Update `ft_a` to represent the magnitude of each complex number Update `ft_b` to represent the frequency associated with the magnitude. frequency = samplingFrequency(sampleIndex/totalNumberOfSamples) To get the list of peaks, check each magnitude to see if it is greater than the magnitude of the frequency bin above and below. Out of the peaks, find the 5 with the largest magnitude, and add the corresponding frequency in order of magnitude to your `peaks` array.
Frequency Detector	Frequency Detector Modify your code, so that when you're interrupt has reached the end of the array, it notifies the loop that the array is full, and doesn't update the array again until the loop has completed an FFT. Using a frequency generator test to see if it works. Analysis Determine how accurate your frequency detector is. Try at least 2 octaves of notes (24 notes) and record the 5 frequency peaks for each note. What is the percent error? Are there portions of the frequency spectrum that it is more or less accurate? Are there any frequency bands that are always present? Note visualization From the Frequencies, calculate the closest note to it (note name eg. A4). I would recommend converting it to a midi note. Use the midi note determine the letter using a modulus and number using integer division. Write test code to check to make sure that your conversion is correct. Design a way to represent the note using an LED, it should communicate both the letter and the number. Implement your visualization.
Extension	Minor Extensions Minor extensions build on the pre-existing circuit for this project. Here are a few examples: Try sampling the data at 5 a different frequencies (updating your timer/OCR1A). How does each sampling rate effect your note detection accuracy? Test to see how efficient your FFT is. Try making changes to your code to make it more efficient, document your changes and the changes in efficiency. Test to see how efficient your FFT is. Try different implementations of sine and cosine, using the C++ math library, arduino sin()/cos() method, look-up table with ints, and look up table with floats, and see how it effects your efficiency and accuracy. Try to implement the recursive implementation of the FFT algorithm. Document your minor extension: Submit your code on filer in a folder inside your project folder. A 1-3 minute video documenting your extension working. (If different from project) A description of the extension. A section on implementation. A section on results & reflection. Include any relevant charts or graphs. Major Extension Design and implement an idea for a new project which involves adding new components and modifying the circuitry. It must incorporate the materials from this project; the microphone and RGB LED. It must include atleast one of the following components: a piezo element, the IR emitters, IR receivers, and/or the vibrating motors. It can include potentiometers, buttons and/or red LEDs. Document your major extension: Submit your code on filer in a folder inside your project folder. A 1-3 minute video of the system working. A description of the extension. A circuit diagram. A photograph of the circuit board. A section on implementation. A section on results & reflection.
Submission	Submit your code on Filer Submit your arduino code in a folder titled `colbyUsername_P04` (with your colby username, mine would be `hewolfe_P04`). Submit your report and video on Google Classroom Upload a 1-3 min Documentation Video of your frequency detector working. Describe what is happening, by saying how the sensor should respond to a specific frequency and then playing the note and showing the response. Show at least 4 different notes from at least 2 different octaves. Attach a Google Doc Report which includes: Photo of circuit. Clear photo of the circuit in which the wiring is clearly visible. Implementation Section Explain how you implemented the project. Explain what algorithms or techniques you used. Draw a diagram and explain how you designed your visualization of the notes. Results & Reflection Section How well does your implementation work? What were the results of your analysis? Acknowledgements Section What resources did you use? Include websites, books and anyone you received help from or discussed the project with.