CSE logo University of Washington Computer Science & Engineering
 CSE326 Autumn 2007
  CSE Home    326 Home   About Us    Search    Contact Info 

Projects
 Project 1
 Project 2 A
 Project 2 B
 Project 3
Homework
 Homework 1
 Homework 2
 Homework 3
 Homework 4
 Homework 5
 Homework 6
 Homework 7
Midterms
 Sample 1
 Sample 2
Administrative
 Home
 Message Board
 Annoucement ArchiveCSE only
 Class List ArchiveCSE only
 Anonymous Feedback
 Mail Instructor & TAs
 Assignment Dropbox
Lectures
 Calendar & Slides
Handouts
 First Day Handout
Policies
 General Guidelines
 Grading Policies
 Programming Guidelines
 Writeup Guidelines
Computing
 Unix Basics
   

Karplus-Strong Algorithm

Ready for some fancy stuff? This time around we are going to create the .dat file from scratch. We are going to synthesize the sound (create the second column of the .dat file) using a method called the "Karplus-Strong" algorithm. This algorithm depends on Queues. So before we get started, you must first implement a Queue (see Weiss chapter 3).

What we want to do is create two Queues, Q1 and Q2. Into Q1 we will enqueue n random numbers between -1.0 and 1.0. In Q2 we will enqueue a single 0.0. At every stage of the algorithm this is what we do (in pseudo-code):
 

a <- Q1.dequeue();
b <- Q2.dequeue();
c <- 0.99 * average(a, b);
Q1.enqueue(c);
Q2.enqueue(a);
output(c);


... and we repeat this over and over m times. The following block diagram of the algorithm may make what's going on clearer:

This program should be called ks.

Basically, the "idea" behind the algorithm is that Q1 is initially filled with a "burst" of sound n samples long. We want to keep sending out the same burst of sound over and over again. That's why we enqueue the output back into Q1, creating a "feedback loop." But we want the sound to get softer each time it goes through the loop so we multiply it by that constant 0.99 each time it goes through. Ok. That's fine. Q1 is a big feedback loop through which we are putting an initial burst of sound over and over again, making the sound slightly softer each time, but what is the point of Q2? Well, if you think about it, Q2 makes it so that every time we output a number, it is averaged with the number that came before it. This "smooths out" the guitar string sound over time, reducing the timbre of the sound with each period.

One more question, what are n and m? Well, n is the number of samples in the loop. If S is the sample rate, then S / n is the number of times the sound repeats itself per second. This is the so called "frequency" of the sound, and it is what we hear as pitch. Double the size Q1 and you will halve the frequency, lowering the pitch by one octave. Similarly, halve the size of the Queue and you will increase the pitch of your guitar sound by one octave.  Finally, m is the total number of samples in the output file. This implies that m / S is the number of seconds in the output file.

After you create the .dat file, convert it to a .wav with sox and listen to it! There's a lot of cool stuff to play around with here. Change the size of Q1 (or Q2!). What happens? Change the dampening constant from 0.99 to something else. What happens?

When you are done, turn in a copy of your source code. Your compiled source code should create a file with 5 seconds worth of "guitar sound" at a sample rate of 44.1kHz , at a frequency of 220Hz, and with a dampening constant of 0.99 (as in the pseudo-code example).


CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to James Fogarty]