brainwagon

One of the greatest things about computing technology is simply how much information is available to anyone who is interested. Technical reports, papers, and most importantly, open source software tools are all available to whomever wants them. This represents a significant democratization of technology. Major universities like MIT are even making entire college level courses available to the public.

It’s nice to see that Google is trying to do the same by establishing the Google Code University. Lots of good information available here.

Google Code University - Google Code

This website provides tutorials and sample course content so CS students and educators can learn more about current computing technologies and paradigms. In particular, this content is Creative Commons licensed which makes it easy for CS educators to use in their own classes.

The Courses section contains tutorials, lecture slides, and problem sets for a variety of topic areas:

• AJAX Programming
• Algorithms
• Distributed Systems
• Web Security
• Languages

While my blog has been dominated by radio related stuff lately, I do continue to be interested in lots of different subjects, including various topics related to computer security and codes. While scanning my feeds today, I found reference to this work, which I hadn’t seen before, but which I find interesting both for its security implications and its use of machine learning. Very cool.

Keyboard Acoustic Emanations Revisited

We examine the problem of keyboard acoustic emanations. We present a novel attack taking as input a 10-minute sound recording of a user typing English text using a keyboard, and then recovering up to 96% of typed characters. There is no need for a labeled training recording. Moreover the recognizer bootstrapped this way can even recognize random text such as passwords: In our experiments, 90% of 5-character random passwords using only letters can be generated in fewer than 20 attempts by an adversary; 80% of 10- character passwords can be generated in fewer than 75 attempts. Our attack uses the statistical constraints of the underlying content, English language, to reconstruct text from sound recordings without any labeled training data. The attack uses a combination of standard machine learning and speech recognition techniques, including cepstrum features, Hidden Markov Models, linear classification, and feedback-based incremental learning.

Well, I’m sitting at The Standard (a frankly far too chic hotel for a forty something computer geek like myself), it’s not quite 7 A.M. and I spent my first day at SIGGRAPH. I’m hear mostly for the benefit of recruiting: sitting in the booth, answering questions and showing up at our Pixar User’s Group Meeting. We are handing out 20th anniversary Renderman walking teapots: very nice, I managed to get one for Josh, but haven’t picked up one of my own: I’ll try to later and get a picture here.

I’m not really attending papers (you can get links here) but there seems to be quite a bit of buzz about Intel’s Larrabee architecture. Broadly speaking, the trend of GPUs has been to slowly work to expand both the number and capability of the different functional units: more shader units, that can execute more arbitrary code, and more texture units, which can present results which are available to more units. Larrabee leapfrogs this: we are back to having X86 cores (not my favorite architecture, but ubiquitous) which are fully general, linked together by a fast shared cache with scheduling done in software. To me, this represents the obvious end game to the evolution of GPUs. Companies like nVidia have been trying to tell us that we can use GPUs to do more general computation: Intel has delivered an architecture where that claim is much more obviously true.

Oh well, I’m gonna get some pancakes at IHOP, then walk the show floor a bit. I want to try to see what the state of the art in stereo monitors is, and maybe see who I can bump into. I’ve got booth duty again at 1:30 (more teapots handed out at 2:00) and then the User’s Group meeting at 6:30. If any readers are at SIGGRAPH, feel free to come by the booth and say hi.

Various projects that I’ve worked on rely on building efficient hash tables for looking up, well, all sorts of stuff (wow, that was vague). Say, storing transposition table entries in my checkers program. Cuckoo hashing is a way of resolving hash table collisions.

Here are some references:

My Biased Coin: Cuckoo Hashing, Theory and Practice : Part 1
Wikipedia entry on Cuckoo Hashing

I’ve bitched before about CSI and their use of “video enhancement” to read displays and the like using low resolution security cameras reflecting off objects. It’s interesting to see what is actually possible using this basic idea though. Link courtesy of Bruce Schneier’s security blog:

Schneier on Security: Spying on Computer Monitors Off Reflective Objects

While trying to find out if Python included some built-in capabilities for dealing with BCD numbers (it appears not) I encountered this rather interesting page about decimal arithmetic.

General Decimal Arithmetic

I do like programming “for fun”, and this includes writing programs that, well, have been written hundreds of times before, but which I never have bothered doing. Often, this is just an exercise: freely available libraries often exist for many tasks which are considerably better than anything that I write. Nevertheless, I don’t consider it pointless. There are situations where having simple, self-contained code that is free from any particular licensing issues.

For instance, I’ve never really bothered coding up an FFT implementation. (Actually, this isn’t entirely true: I helped work on an i860 based assembly language version twenty years ago when I was at Princeton, but I must admit that I didn’t do much of the heavy lifting.) When forced to use one, I typically just fire up FFTW and use it. It’s a fast, relatively simple and flexible FFT library, and well worth using. But there are some circumstances where it seems like overkill. So, I sat down and implemented a basic radix-2 in-place FFT in C using the algorithm from Crandall and Pomerance’s Prime Numbers. Running it on my MacBook, for an 8192 length complex forward transform, I get a time of about 3.95 ms per transform. The same size transform running with FFTW is almost a factor of ten faster: about .413ms per transform. Of course, my code is a big stomping 43 comfortable, loafing lines long.

But this got me thinking about how it might be possible to speed it up. I have a couple of books on my shelf at work that will probably useful (I looted them from people who were more knowledgeable than me at DSP who, for some reason, decided to give them away, but I haven’t read them). Even doubling the speed of this “naive” implementation would make it significantly more useful. And, it seems like it could be a reasonably fun thing to tinker with.

It’s too late today to make any significant progress, but I did dig up a useful link.

Efficient FFT Algorithm and Programming Tricks

Addendum: Updating the so-called “twiddle factors” in the inner loop was being done in a stupid way in my code before. It really only requires a complex multiply in the inner loop, which speeds it up considerably. Now, my 8192 element FFT takes a mere 1.16ms on my MacBook, a speedup of nearly 4x, and now it’s within a factor of 3 of the speed of FFTW. I don’t like the way it really looks yet, but it’s better than most. I’ll tidy it up soon and archive it here for future consumption.

Addendum: Now that it’s basically working, I’m left wondering about numerical accuracy. Accuracy of the discrete Fourier transform and the fast Fourier transform would appear to be relevent. It appears that my choice of recurrence relationship for the twiddle factors probably results in rather significant errors (although I also suspect that it’s more than entirely adequate for the normal audio tasks which I use these things for typically).

Well, my excursion into FFT multiplication the other day left me with some more interesting questions, including trying to find out more information about the integer version of the FFT called the NTT (number theoretic transform). Instead of computing the transform to an orthogonal basis consisting of the complex roots of unity, the NTT transforms to a basic formed by discrete vectors over an orthogonal basis consisting of the primitive roots of some prime power. Any of that make any sense to you? Yeah, it’s pretty hard going for me too, requiring me to dust off some of my number theory knowledge that has been dormant for quite some time. But while digging, I found this link:

Jörg’s useful and ugly FXT page

Jörg Arndt is working on a textbook which appears chocked full of good stuff that actually has to do with computing things (as opposed to the stylish modern trend of merely using gigaflops of compute power to wait for mouse clicks). Very neat stuff: I suspect that if I read the chapter on the NTT a few more times, I’ll have it figured out.

Tom Duff recommended this blog for my perusal, and I filed it away. Today I discovered that it was linking back to one of my more popular posts: the one in which Tom Duff talks a little bit about Duff’s device. But there’s a lot of good reasons to check it out. I found this post about Unix viruses, which contained a link to one of Tom’s papers that I never read, although Tom and I have discussed at various times. Very neat. Lots of other good things in there too! Worth reading.

It’s 8:22AM, and I’m just waking up, checking my email and surveying my usual blogs with Google Reader. I don’t have time to explain why this link seems interesting, but if you are interested in random walks, computability or cellular automata, check out the following link. I haven’t had time to absorb it yet (and probably won’t until tonight, given that I should be on the road shortly) but it seems very interesting.

To me, anyway.

The photon/XOR system

This week I’m busy at work trying to complete dozens of SIGGRAPH sketch reviews, so it seems like an opportune time to present the usual link to  online copies of the SIGGRAPH 2006 Papers that have been accepted.  I haven’t had a chance to review these yet, but there is usually something good in this pile.

[tags]SIGGRAPH,Computer Graphics[/tags]

There is a new security update for Wordpress, which I’ve already installed without any serious mishap/problems. If you run Wordpress, you might think about giving it an upgrade.

[tags]Wordpress,Blogging,Security[/tags]

Addendum: I’ve been having minor problems with the Dashboard in this release not displaying correctly.  I’m still trying to figure it out.

You might have noticed if you are a long time reader of this blog that I’m fascinated by codes and ciphers, particularly the kind that were developed before computers really came on the scene.   That’s why I’m finding the M4 Message Breaking Project interesting: they are attempting to break three two as yet unbroken code intercepts that presumably use the Nazi 4-Rotor Naval Enigma machine.

Years ago when Simon Singh’s The Code Book came out, he ran a cipher challenge that invited readers to compete for a $10,000 prize by being the first to break 10 codes.   I broke 7 out of the 10 (all the ones I thought I had a shot) including a 3 rotor Enigma encrypt.   Breaking the 4 rotor variant with a much shorter message is a significant challenge, and they’ve managed to break one of the three already.

I’ve got their distributed client running on my machine.   We shall see how it goes.

[tags]Enigma Machine,Cryptanalysis,Codes,Ciphers,Distributed Computing[/tags]

Josh over at tinyscreenfuls is digging some of the fancy “pencil sketch” effects that the Mac can do with its internal camera.  Back in 1998, I experimented with writing some filters that did much the same, with some examples that I generated shown on the right.   Macintosh?  I don’t need no steekin’ Macintosh.

And now, for your next project, render an entire feature length film.   Beneath your desk, you’ll find a pencil, a yellow pad, and a C compiler…

This is just completely nuts, an 8 bit computer constructed entirely from 12 volt relays. It consumes 12 amps at 13.5 volts (160 watts). Hilarious.

[tags]Retrocomputing,Hacks[/tags]