In a blind taste test, both Liz and I chose the Haribo gummi bear over the Black Forest (“made with real (= apple) juice!”) gummi bears. It was as I suspected — Haribo is the best. After all, kids and grown-ups love it so.

# Monthly Archives: May 2005

# big singing

I have an audition coming up next week for the San Francisco Symphony Chorus. It’s pretty nerve-racking, really. I think there are only 5 or so slots open for tenors and the chorus is huge. The consolation prize is that I might still be able to sing the Mahler even if I’m not accepted into the regular chorus. The concerts I’m hoping to sing in are:

- Stravinsky —
*The Nightingale*and*Oedipus Rex* - Ives —
*New England Holidays* - Shostakovich —
*Symphony No. 13 “Baba Yar”* - Mahler —
*Symphony No. 8*

My audition is on the 25th — which is also when we’re going to try to finish recording the Britten.

# subtitles for english movies

One advantage — you can tell what the lyrics are in the background music. For a movie like *Six-String Samurai*, it adds to the experience. Maybe I should actually buy a Red Elvises CD.

# even birds have their rebellious phase

An article just came out that says

Young canaries happily learn songs that sound nothing like their species, but they revert to a strict canary-like melody as they mature, Science reports.

I guess canaries eventually grow up and settle down to become just like their parents. Scary, innit?

# jon robin baitz

I just discovered, via the Huffington Blog, that Jon Robin Baitz wrote episodes of the West Wing and Alias. He’s a playwright originally recommended to me by Alan Brody for the playwriting workshop. I just started rereading *The Film Society* so it was a nice little convergence.

Perhaps I should reconsider watching TV again. Nah.

# some things get better

A few years ago, I would run large MATLAB programs and then sleep under the desk while I waited for them to run. Now I can run a large MATLAB program and sleep on the nice leather sofa in our new office space. That is, I could sleep if it worked.

# Guruswami-Sudan algorithm in MATLAB

**Read the updates at the end! Comments are disabled because people don’t actually read the post. This is sad to me, since it really shows that the majority of people commenting on this post are really just trolling for a free pass at an implementation, think that I or someone else will send it to them or port it into C for them, and are so lazy that they can’t scroll through the post themselves.**

For part of my class project in coding theory this semester I’ve implemented the Guruswami-Sudan decoding algorithm for Reed-Solomon codes. Reed-Solomon codes are used widely in practice for error-control coding. For example, CDs use a Reed-Solomon code to provide resilience to errors introduced by scratches or machine error. The math behind RS codes is somewhat complicated, but the idea is as follows. Suppose you have some *k* symbols of data that you want to encode into *n* symbols. The redundancy (and hence error correction capability) can be thought of as the difference *(n – k)*. This is the “fat” we add into the data to make it resistant to errors.

RS codes take these *k* symbols and think of them as the coefficients of a polynomial

f(X) = f_0 + f_1 x + f_2 x^2 + … + f_{k-1} x^{k-1}

The encoder and decoder agree to fix *n* points *{a_1, a_2, … a_n}*. The encoding map consists of evaluating *f(X)* at these *n* points and sending the evaluations:

codeword = (f(a_1), f(a_2), … f(a_n))

The key is in decoding — if the decoder gets any *k* symbols correctly, it should be able to interpolate a unique polynomial *f* through them perfectly (this is from linear algebra). Thus in the CD example, if the CD player can’t read some of the symbols, it can only tell the decoder those symbols that it did read. As long as *k* of those symbols were received the decoder can recover the polynomial and hence the data sequence.

Now of course the math is a little more complicated than that, but not by too much. RS codes are actually defined as polynomials over the ring *F[x]* where *F* is the finite field with *2^m* elements, and the encoding is the evaluation of a degree *k-1* polynomial on all the nonzero elements of the field.

The Guruswami-Sudan algorithm algorithm works in two steps — it interpolates a certain bivariate polynomial *Q[x,y]* in a F[x,y], and then factors it into factors of the form *(y – f_i(x))*. The y-roots *{f_i(x)}* can be thought of as “candidate polynomials” for the data sequences. The algorithm works in polynomial time and outputs a small list of candidates which is guaranteed to contain the transmitted codeword under certain conditions on how bad the errors are. The real key is that the list will often contain the true codeword even if more errors occurred than the code was designed for.

My implementation is based on a very nice tutorial paper by Robert McEliece, who is a really fantastic writer. It uses the Koetter algorithm for interpolation and the Roth-Ruckenstein algorithm to factor the resulting polynomial. This posting is mostly so that Google will possibly pop up this page if people are looking for MATLAB implementations of this algorithm and don’t want to waste sleepless nights like I did trying to force it to work. Caveat emptor, as they always say.

UPDATE : I’ve moved several times since this post was written and in the meantime taken down the code since implementing this is a common course project. It was tricky but not too hard, and I’ve decided the learning benefits of implementing it yourself outweigh the (now negligible) time savings for projects involving follow-on work.