Harper's Bazaar

Homework 6: Harper's Bazaar

Assignment Goals

Learn how to create user-defined data types in Java
Turn your computer into a musical instrument
Learn about digital audio

Now that you've had a couple of months to get familiar with programming and testing, we expect you to think about good style and development habits as you program. We will therefore be stricter about these issues in both grading and office hours. This is a good time to review the following:

Write your comments first then fill in the code. Not only does this naturally lead to well-commented code, it helps you work through the problem you're solving.
The "Coding Style" section in the Resource menu gives the highlights of our style guidelines and a link to the booksite's style guide. Your code should comply with the style guidelines at all times, not just when you submit! This is no different than expecting paper drafts to have reasonable spelling and grammar—there will be a little bit of tidying up at the end, but you get to a better final version more quickly if your drafts are coherent and reasonably error-free to start with.
Pay special attention to variable naming. Checkstyle won't flag bad variable names, but they will still factor into your homework grades!
You can submit your code as often as you like to see the checkstyle output. Of course, you should get into the habit of writing well-styled code without relying on checkstyle. You'll end up writing better code faster if it isn't a mess to start with.
Your code should compile at all times. It should be correctly indented at all times. Masses of code that don't even compile are almost always nearly useless.
Test as you go! Every time you write a function, think about how you can test it, and add code to your main function to do so. Then run that code. If the assignment doesn't specify the behavior of main, you can leave your code uncommented. Otherwise just comment it out in your final submission.
To debug your code, add print statements that allow you to trace the path through your code (for example, you might print something out at the beginning of a function or an if statement so you can see the function was called or the if was taken) and the values of all variables. This will help you understand exactly what your program is doing and compare that to what you want it to do.
TAs WILL NOT HELP YOU DEBUG—OR EVEN READ—YOUR CODE if it is a stylistic mess, is a mass of completely untested (let alone uncompiled) code, if there are no comments, or if you can't tell them how you've tried to test it. Instead, they will go over the conceptual aspects of the part of the assignment you are working on, then leave you to clean up your code and apply your new understanding to debug it on your own. This policy applies both to office hours and piazza. It may sound (and feel) a bit mean, but it is an important part of learning.
All of these points have been posted all semester in the "Office Hours" tab of the "Ways to Get Help" page. We are reiterating them now because you're far enough along now to understand their purpose and put them into practice.

For this assignment, you will write a program to simulate plucking a harp string using the Karplus-Strong algorithm. This algorithm played a seminal role in the emergence of physically modeled sound synthesis (in which a physical description of a musical instrument is used to synthesize sound electronically).

When a harp string is plucked, the string vibrates and creates sound. The length of the string determines its fundamental frequency of vibration. We model a harp string by sampling its displacement (a real number between -1/2 and +1/2) at N equally spaced points (in time), where N equals the sampling rate (44,100) divided by the fundamental frequency (rounding the quotient up to the nearest integer).

Plucking the string. The excitation of the string can contain energy at any frequency. We simulate the excitation with white noise: set each of the N displacements to a random real number between -1/2 and +1/2.
The resulting vibrations. After the string is plucked, the string vibrates. The pluck causes a displacement which spreads wave-like over time. The Karplus-Strong algorithm simulates this vibration by maintaining a ring buffer of the N samples: the algorithm repeatedly deletes the first sample from the buffer and adds to the end of the buffer the average of the first two samples, scaled by an energy decay factor of -0.997.

Download the template for RingBuffer.java
Download the template for HarpString.java
Download MiniHarp.java. This program will help you test RingBuffer and HarpString, and serve as a starting point for the full Harp program that you will write.
Download the readme_harpersbazaar.txt template.
Review the material in the textbook on digital audio (pp. 147–151, 202–206).

The two primary components that make the Karplus-Strong algorithm work are the ring buffer feedback mechanism and the averaging operation.

Some intuition. An intuitive, if imprecise, explanation of the alogirhtm is the following. When you pluck a harp string, the middle of the string bounces wildly up and down. Over time, the tension on the string causes it to move more regularly and more gently until it finally comes to rest. High frequency strings have greater tension, which causes them to vibrate faster, but also to come to rest more quickly. Low frequency strings are looser, and vibrate longer. If you think about the values in the ring buffer as positions over time of a point in the middle of a string, filling the buffer with random values is equivalent to the string bouncing wildly (the pluck). Averaging neighboring samples brings them closer together, which means the changes between neighboring samples become smaller and more regular. The decay factor reduces the overall amount the point moves, so that it eventually comes to rest; using a negative decay factor removes even harmonics of the fundamental. The final kicker is the ring buffer length. Low notes have lower frequencies, and hence longer ring buffers (44,100 / N is bigger if N is smaller). That means it you will have to go through more random samples before getting to the first round of averaged samples, and so on. The result is it will take more steps for the values in the buffer to become regular and to die out, modeling the longer reverberation time of a low string.
The ring buffer feedback mechanism. The ring buffer models the medium (a string tied down at both ends) in which the energy travels back and forth. The length of the ring buffer determines the fundamental frequency of the resulting sound. Sonically, the feedback mechanism reinforces only the fundamental frequency and its harmonics (frequencies at integer multiples of the fundamental). The energy decay factor models the slight dissipation in energy as the wave makes a roundtrip through the string.
The averaging operation. The averaging operation serves as a gentle low-pass filter (which removes higher frequencies while allowing lower frequencies to pass, hence the name). Because it is in the path of the feedback, this has the effect of gradually attenuating the higher harmonics while keeping the lower ones, which corresponds closely with how a plucked harp string sounds.
From a mathematical physics viewpoint, the Karplus-Strong algorithm approximately solves the 1D wave equation, which describes the transverse motion of the string as a function of time.

1. RingBuffer.java Your first task is to create a data type to model the ring buffer. Write a class named RingBuffer that implements the following API:

public class RingBuffer
-----------------------------------------------------------------------------------------
        RingBuffer(int capacity)  // create an empty ring buffer, with given max capacity
    int size()                    // return number of items currently in the buffer
boolean isEmpty()                 // is the buffer empty (size equals zero)?
boolean isFull()                  // is the buffer full  (size equals capacity)?
   void enqueue(double x)         // add item x to the end
 double dequeue()                 // delete and return item from the front
 double peek()                    // return (but do not delete) item from the front

The design of your program should look like the provided RingBuffer.java, except that you will need to fill in all of the constructors and methods.
Since the ring buffer has a known maximum capacity from the argument to the constructor, you must implement it using a double array of that length. Your constructor for RingBuffer will need to allocate and initialize this array using new. Observe that you have to do this in the constructor (and not when you declare the instance variables) since otherwise you wouldn't know how big to make the array.

The instance variables are defined as follows:

public class RingBuffer {
    private double[] rb;          // items in the bufer
    private int first;            // rb[first]  = first item in the buffer
    private int last;             // rb[last-1] = last  item in the buffer
    private int size;             // current number of items in the buffer
}

Cyclic wrap-around: For efficiency, your RingBuffer must wrap around in the array. To do this, maintain one integer instance variable first that stores the index of the least recently inserted item; maintain a second integer instance variable last that stores the index one beyond the most recently inserted item. To insert an item, put it at index last and increment last. To remove an item, take it from index first and increment first. When either index equals capacity, make it wrap-around by changing the index to 0. Keep in mind, the size of the RingBuffer is not the same as the size of the array. To get an accurate count of the number of elements in your RingBuffer, increment the instance variable size each time you call enqueue() and decrement it each time you call dequeue(). Here is a demonstration of how the enqueue() and dequeue() methods work:
- Initial State:
- enqueue(0.5)
- enqueue(0.1)
- dequeue()
Implement RingBuffer to throw an exception if the client attempts to dequeue() from an empty buffer or enqueue() into a full buffer. This will cause your program to crash and print a stack trace that will help you identify the bug. (We have included these statements in the skeleton code for you.) The following is an example of how to throw an exception:
```
if (isEmpty())
  throw new RuntimeException("The ring buffer is empty.");
```
See Vector.java for some other examples and p. 446 in the book for a slighty expanded explanation of exceptions..
After you fill in the methods for RingBuffer, make sure to test it using the given test code in main()within the RingBuffer skeleton code before moving on. It enqueues the numbers 1 through N,and then repeatedly dequeues the first two, and enqueues their sum.
```
% java RingBuffer 10
Size after wrap-around is 10
55.0


% java RingBuffer 100
Size after wrap-around is 100
5050.0
```

2. HarpString.java Next, create a data type to model a vibrating harp string. Write a class named HarpString that implements the following API:

public class HarpString
------------------------------------------------------------------------------------------------------------------------
       HarpString(double frequency)  // create a harp string of the given frequency, using a sampling rate of 44,100
       HarpString(double[] init)     // create a harp string whose size and initial values are given by the array
  void pluck()                       // set the buffer to white noise
  void tic()                         // advance the simulation one time step
double sample()                      // return the current sample
   int time()                        // return number of tics

Start the harp string class with HarpString.java.It contains one of the private instance variables that you will need, and all of the constructors and methods ready to be filled in.
Constructors. There are two ways to create a HarpString object.
- The first constructor creates a RingBuffer of the desired capacity N (the sampling rate 44,100 divided by frequency, rounded up to the nearest integer), and initializes it to represent a harp string at rest by enqueueing N zeros.
- The second constructor creates a RingBuffer of capacity equal to the size of the array, and initializes the contents of the buffer to the values in the array. On this assignment, its main purpose is for debugging and grading.
Sample. Return the value of the item at the front of the ring buffer. Use peek() to implement this.
Time. Return the total number of times tic() was called.
Pluck. Replace all N items in the ring buffer with N random values between -0.5 and +0.5. To implement this, use a combination of the RingBuffer methods to replace the buffer with random values between -0.5 and 0.5.
Tic. Apply the Karplus-Strong update: compute the average of the first two samples, multiplied by the energy decay factor (see Tab 0), delete the sample at the front of the ring buffer, then add the new sample to the end. To implement this, use a combination of RingBuffer methods.
Are you getting a NullPointerException? Check the line number provided in the stack trace. An object you are using in this line has not been initialized correctly, and thus has the value of "null". Attempting to access variables or call functions on a null object will throw a NullPointerException.

Once you have filled in all the methods and constructors, make sure to test it using the given test code in main()within the HarpString skeleton code before moving on.

% java HarpString 25
     0   0.2000
     1   0.4000
     2   0.5000
     3   0.3000
     4  -0.2000
     5   0.4000
     6   0.3000
     7   0.0000
     8  -0.1000
     9  -0.3000
    10  -0.2991
    11  -0.4487
    12  -0.3988
    13  -0.0498
    14  -0.0997
    15  -0.3490
    16  -0.1496
    17   0.0499
    18   0.1994
    19   0.2987
    20   0.3728
    21   0.4225
    22   0.2237
    23   0.0746
    24   0.2237

3. Harp.java Write a program Harp.java that simulates a 37-string harp with notes ranging from 110Hz to 880Hz. In general, make character i of the string below play note i.

String keyboard = "q2we4r5ty7u8i9op-[=zxdcfvgbnjmk,.;/' ";

Note: i is 0 indexed. For example, i = 2 refers to w. Character i of the string corresponds to a frequency of 440 × 2^{(i - 24) / 12}, so that the character 'q' is 110Hz, 'i' is 220Hz, 'v' is 440Hz, and ' ' is 880Hz.

This keyboard arrangement imitates a piano keyboard: The "white keys" are on the qwerty and zxcv rows and the "black keys" on the 12345 and asdf rows of the keyboard.

The MiniHarp.java Example Program MiniHarp.java is a two-string version of Harp.java that you can use to test your RingBuffer.java, HarpString.java, and as a starting point for Harp.java. Type the lowercase letters 'a' or 'c' to pluck its two strings. Since the combined result of several sound waves is the superposition of the individual sound waves, we play the sum of all string samples. After you've completed RingBuffer.java and HarpString.java, run MiniHarp in order to check to see if everything works properly. You should hear two different pitches corresponding to A and C everytime you press the key.
public class MiniHarp { public static void main(String[] args) { // create two harp strings, for concert A and C double A = 440.0; double C = A * Math.pow(2, 3.0/12.0); HarpString stringA = new HarpString(A); HarpString stringC = new HarpString(C); while (true) { // check if the user has typed a key; if so, process it if (StdDraw.hasNextKeyTyped()) { char key = StdDraw.nextKeyTyped(); if (key == 'a') { stringA.pluck(); } else if (key == 'c') { stringC.pluck(); } } // compute the combined sound of all notes double sample = stringA.sample() + stringC.sample(); // play the sample on standard audio StdAudio.play(sample); // advance the simulation of each harp string by one step stringA.tic(); stringC.tic(); } } }

Note: In order to enter keystrokes in MiniHarp, make sure to first click on the standard draw window before typing the keystrokes. If you are having trouble running MiniHarp, refer to the FAQ tab.

Also, note how this code above uses an infinite loop to continually receive keystrokes from the user and generate new music samples. This infinite loop ends when the program terminates.

Debugging Harp.java can be a little tricky. The probably is that you can only hear sound if you are sending new samples to your speaker fast enough. "Fast enough" means 44,100 times per second. System.out.println() is surprisingly slow—it almost always takes longer that 1/44,100th of a second to print something. The result is that you will hear only clicks or silence if you have any print statements to help you debug.
Your best bet is to thoroughly test and debug RingBuffer.java, then thoroughly test and debug HarpString.java. Next, comment out, but do not delete any print statements you add for debugging and test MiniHarp. You may need to uncomment these statements and do further testing later (by adding new test cases to RingBuffer's and/or HarpString's main()). Do not start on Harp.java until you are certain everything else, including MiniHarp, works.

The number 37 should not appear anywhere in your code. Don't even think of including a 37-way if statement! Instead, create an array of HarpString objects and use keyboard.indexOf(key) to figure out which key was typed.
Make sure your program does not crash if a key is played that is not one of your notes.
Once you've completed Harp, try playing this familiar melody.
```
nn//SS/ ..,,mmn //..,,m //..,,m nn//SS/ ..,,mmn   (S = space)
```

Type the following into your harp to get the beginning of Led Zeppelin's Stairway to Heaven. Multiple notes in a column are dyads and chords.

                                              w q q
        8       u       7       y             o p p
i p z v b z p b n z p n d [ i d z p i p z p i u i i

The are lots of ways to building on Harp.java in interesting ways. Some of these can earn extra credit, while others will not, but are including for you to implement if you are interested.

Write a program VisualHarp.java (by modifying Harp.java) that plots the sound wave in real-time, as the user is playing the keyboard harp. The output could look something like this, but change over time. You are free to be as creative as you wish with your visualization, as long as the visualization is driven by the sound samples being emitted. Warning - this extra credit is fairly tough and should only be done if you are well prepared for the final.

Do not redraw the wave on every sample because StdDraw will not be able to keep up. Instead, draw the wave of the last n samples every n timesteps for an appropriate value of n. Experiment with different values of n to find one that you think looks good and draws smoothly. There is more than one way to handle the drawing — there is not a "right" way to do this. You may also do a different visualization, as long as it is tied to the audio samples.

Bring your laptop to recitation the week after this homework is due and perform a piece for your classmates. You may perform in groups if you wish, and you may use a modified version of your program for the performance if you wish.

Modify the Karplus-Strong algorithm to synthesize a different instrument. Consider changing the excitation of the string (from white-noise to something more structured) or changing the averaging formula (from the average of the first two samples to a more complicated rule) or anything else you might imagine. This is a challenge for the bored, so you will not receive extra credit for it. But you may use it as the basis for you visualizer and/or your performance in class.

Alexander Strong suggests a few simple variants you can try:

Stretched tuning: The frequency formula in the assignment uses "perfect tuning" the doesn't sound equally good in every key. Instead, most musicians use stretched tuning that equalizes the distortions across all keys. To get stretched tuning, using the formula f = 440 × 1.05956^i - 24. Try experimenting a bit with the base of the exponent to see what sounds best.
Extra notes: Add additional keys to your keyboard string to play additional notes (higher or lower). Higher notes especially will benefit from stretched tuning. You will need to update the 24 in your frequency formula to change the frequency of the lowest note.
Better decay factors: Make the decay factor dependent on the string frequency. Lower notes should have a higher decay factor; higher notes should have a smaller decay. Try different formulas and see what sounds best.
Guitar strings: Use a decay factor of +0.994 in tic() will change the sound from harp-like to guitar-like. You may want to play with the decay factors and note frequencies to improve the realism.
Drums: Randomly flipping (with probability 0.5) the sign of the new value before enqueing it in tic() will produce a drum sound. You will need lower frequencies for the drums than for the harp and guitar, and will want to use a decay factor of 1.0 (no decay). The note frequencies for the drums should also be spaced further apart.
Mix and match: Assign some keyboard keys to drums, others to harp, and still others to guitar (or any other instruments you invent) so you can play an ensemble.

The original paper describing this algorithm, including many variants and a mathermatical derivation of why it works is: Kevin Karplus, and Alexander Strong. "Digital Synthesis of Plucked-String and Drum Timbres". Computer Music Journal Vol. 7, No. 2 (Summer 1983), pp. 43-55. To access the full article, follow the link, then, click on "Login" in the upper right. Select "University of Pennsylvania" as your institution, and you will be able to log in with using your PennKey. (If you are on the Penn network, you may not need to log in.)
ChucK. ChucK as specialized programming language for real-time synthesis, composition, and performance originated by Ge Wang and Perry Cook at Princeton University. Here's the Karplus-Strong algorithm in ChucK.
Slide flute. Here's a description of a physically modeled slide flute by Perry Cook.

Submit RingBuffer.java, HarpString.java, Harpjava, and a completed readme_harpersbazaar.txt using the submission link on the left. Optional: Submit a fully functional VisualHarp.java for extra credit. If your VisualHarp program requires any additional files, you may submit them in a zip file named extra.zip. I get an ArrayOutOfBounds or NullPointerException error in RingBuffer. What could cause this? Does your constructor correctly initialize all of the instance variables? Did you allocate memory for your array? Did you inadvertently redeclare an instance variable in a method or constructor, thereby shadowing the instance variable with the same name?

How do I round a double up to the nearest int? Rounding up to the nearest int is the same as taking the ceiling; Java provides Math.ceil() for this purpose.

What happens if I call StdAudio.play(x) where x is greater than 1 or less than -1? The value is clipped—it is replaced by the value 1.0 or -1.0, respectively.

I get a Ring buffer underflow error in MiniHarp before I type any keystrokes. Why? Did you forget to initialize the ring buffer to contain N zeros in your HarpString constructor?

When I run MiniHarp for the first time, I hear no sound. What am I doing wrong? Make sure you have tested with the main() provided for HarpString. If that works, it is likely something wrong with pluck() since the main() provided for HarpString does not test that method. To diagnose the problem, print out the values of sample() and check that they become nonzero after you type lower case characters 'a' and 'c'.

When I run MiniHarp, I hear static (either just one click, and then silence or continual static). What am I doing wrong? It's likely that pluck() is working, but tic() is not. The best test is to run the main() provided for HarpString.

How do I use keyboard.indexOf(key)? If keyboard is a String and key is a character, then keyboard.indexOf(key) return the integer index of the first occurrence of the character key in the string keyboard (or -1 if it does not occur).

Should I hardwire the constants 44,100, 110.0, 440.0, 880.0, and 37 in my program? No, in general, we will deduct if you use an unnamed constant (such as 37) in your program more than once. We recommend using the name SAMPLING_RATE for 44,100 and A440 for 440. But you need not name all of the constants in the formula 2^{(i - 24) /&nbps;12}.

Do I need to follow the prescribed API? Yes, we will be testing the methods in the API directly. If your method has a different signature or does not behave as specified, you will lose a substantial number of points. You may not add public methods or instance variables to the API; however, you may add private methods (which are only accessible in the class in which they are declared). You may also add private instance variables for data that must be shared between methods.