Daily Archives: 12/13/2010

What ideas infect my brain and why…

Some of you might be wondering what it is about this Karplus-Strong algorithm that has got me interested. Of course, long time readers of my blog might well have wondered that about any of a number of things that I’ve written about. What is it about checkers that prompted me to write a checkers program? What is it about prime numbers or pi that made me write programs to compute them? What is it about the FFT? What is it about FPGAs and computer architecture? Why did I find Brian Beckman’s Physics of Racing intriguing?

I think it has something to do with hidden complexity.

Consider for example the Karplus-Strong algorithm that I coded up. It’s relatively simple: just a few lines of code. But it has complex behavior: behavior that is in some sense surprising. It’s hard to see from examining it how it can generate the kind of sounds it produces. Ken Steiglitz’s book doesn’t really provide enough background on how it works until 100 pages in, and even then, there is a lot of subtlety which isn’t really apparent. There is genuine genius in the dozen or so lines of code that make it up: genius that hints at hidden knowledge and new ideas.

Ditto for checkers. Payne did some of the first analysis of so-called “First Position” back in the late 1700s. These are some of the most basic checker positions: two king versus one king and one man endgames. Yet, inside these positions are some deeply complex principles, principles which still make writing a good checker playing program difficult.

Beckman’s Physics of Racing provides some insight into how race cars actually work. Making a car go fast around a track is more than just weight and horsepower. It’s about understeer and oversteer. It’s about balance. It’s about friction and slip.

There is more in these systems that are evident from first glance. In many cases, mathematics provides an insight into the underlying structure and complexity. Computers can lend insight into systems which are too complicated to understand from first principles. And in the end, engineering and actual physical implementation provides us with the glory of music, the fun of games, and the thrill of racing.

Richard Feynman once famously mused that science provided a glimpse into a kind of deep beauty. Rather than paraphrase him, I’ll let him talk…


httpv://www.youtube.com/watch?v=zSZNsIFID28

The world of mathematics and physics and computing provides us an opportunity to explore the deeper inner beauty of things in new ways. And geeky as it is, that’s what I think underlies some of the themes I explore on this blog.

There, glad I got that off my chest. Now, back to work.

Plink2!

Okay, I finally found my copy of Ken Steiglitz’s A DSP Primer (a great book, but sadly more expensive now than when I got my copy) and read through the implementation of the tunable plucked string instrument. A couple of things really need to be added: first of all, I was off considerably in my tuning because the averaging operation inserts a delay of 1/2 a sample, and the tuning was necessarily coarse because the frequency was entirely determined by the length of the delay buffer, which was an integer. To make that work, you need to introduce an all-pass filter, which has a pretty simple form. Without any additional explanation, here’s the source code that I tinkered together over a half an hour of reading and typing.

[sourcecode lang=”C”]
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <sndfile.h>

/*
* ks.c
* an implementation of the Karplus-Strong algorithm, revised after
* reading Ken Steiglitz’s treatment in "A DSP Primer".
*/

#define SAMPLE_RATE (22050)

double freq = 440. ;

main(int argc, char *argv[])
{
SNDFILE *sf ;
SF_INFO sfinfo ;
double delay ;
int L ;
int i, j ;
int sample ;
double a ;
double w0 ;
double x0, y0, x1, y1 ;

freq = atof(argv[1]) ;

sfinfo.samplerate = SAMPLE_RATE ;
sfinfo.channels = 1 ;
sfinfo.format = SF_FORMAT_WAV | SF_FORMAT_PCM_16 ;

sf = sf_open(argv[2], SFM_WRITE, &sfinfo) ;

/* first of all, figure out the total delay…
* freq = SAMPLE_RATE / (L + 0.5)
* or L = SAMPLE_RATE / freq – 0.5 ;
*/

delay = SAMPLE_RATE / freq – 0.5 ;
fprintf(stderr, "… delay = %f\n", delay) ;
L = floor(delay) ;
delay -= L ;
fprintf(stderr, "… buffer size is = %d\n", L) ;
fprintf(stderr, "… fractional delay is = %f\n", delay) ;

fprintf(stderr, "… approximate value for a = %f\n", (1-delay)/(1+delay)) ;
w0 = 2.0 * M_PI * freq / SAMPLE_RATE ;
a = sin((1. – delay) * w0/2.) / (sin((1. + delay) * w0/2.)) ;
fprintf(stderr, "… exact value for a = %f\n", a) ;

/* okay, now generate one second of the plucked string sound.
*/

double *buf = calloc(L, sizeof(double)) ;

/* initialize with random numbers. */
for (i=0; i<L; i++)
buf[i] = 2.0 * drand48() – 1.0 ;

x0 = y0 = 0. ;
for (sample=i=0; sample < SAMPLE_RATE * 0.25 ; sample++) {
j = i + 1 ;
if (j >= L) j = 0 ;
x1 = (buf[i] + buf[j]) / 2. ;
/* implement the "allpass" filter. */
y1 = a * x1 + x0 – a * y0 ;
sf_write_double(sf, &y1, 1) ;
y0 = y1 ;
x0 = x1 ;
buf[i] = y1 ;
i = j ;
}

sf_close(sf) ;
}
[/sourcecode]

This just writes out 1/4 of a second of a note tuned at the frequency that you specify. I wrote a little python program, and computed an mp3 of a simple two octave run of notes.

Addendum: I synthesized the small set of three note chords just to test how them merged. They do sound a bit plinky and a little thin, but not terrible.