Friendly Robot Overlord

Google street view car taking a picture of itself:

I'm not a big user of street view, so maybe this is more common than I realise. On the other hand, it did make me realise how cool it is that it works so well everywhere else.

This is a bit of experimental code for working with sounds in the PDM domain. The simple explaination of what that is would probably be these pictures:

Input signal:

Converted to PDM (the three lines are independent, I wrapped it to avoid horizontal scrolling), oversampling 32 times:

So as the waveform goes up, the PDM version gets darker, and when the waveform goes down, the PDM gets lighter. This is not quite the same as PWM, as we don't have a specific time window which we try to encode, and so we generally have more transitions from on to off in a time period.

People generally seem to pass the PDM signal to an amplifier, which then spits out a bigger version of the signal, which is then low pass filtered to get back to something resembling the original. This is a simple way to build a D/A converter, and they can be quite cheap, efficient and I believe also sound good.

I thought it would be interesting to do some processing on the signal while it is still in the PDM domain. So, I built a quick test application for taking a wave-file, putting it into PDM domain, doing something to it, and then returning it to PCM and spitting out another wave file.

Things which are trivial in PCM domain (like adjusting the volume) are a bit more involved for a PDM signal. This is (a simplified form of) the code I used:

for (int i = 0; i < get_length(this_channel); i++) {
  this_bit = get_bit(i);

  if (this_bit) error += VOLUME_FACTOR;
  else          error -= VOLUME_FACTOR;

  if (error > 0)   this_value = 0;
  else (error < 0) this_value = 1;

  if (this_value) error += 1;
  else            error -= 1;

  set_bit(this_channel, i, this_value);
}

Whereas for PCM, you would write something like:

for (int i = 0; i < get_length(this_channel); i++) {
  this_value = get_value(i);
  set_value(this_channel, i, this_value * VOLUME_FACTOR);
}

However, this also means that it isn't as obvious when we are going to clip. In PCM, you know you have clipped if the value ends up out of the range you are working in. But here, we are always working with 0 and 1, and there is no way we can get a -1 or a 2. If you drive it too hard, the output will still clip, but it just won't be as obvious that it will clip until you do the conversion back to PCM.

So what the included code does is:

1. Split the input signal into high frequencies (> 2KHz) and low frequencies.
2. Put the low frequency signal into PDM domain.
3. Drive the low frequency signal using code like the code above, where VOLUME_FACTOR is big enough to make it clip frequently.
4. Mix together the high frequencies, some clean lows and some distorted lows.

And it can transform something like this into something like this. Even though it destroys the bass drum (in a cool way), the filtering makes it one of the subtler things I've put up here :)

The code isn't written for speed. On the other hand, you should look at some of the hacks used to get the filters right. I use a stack of 1st order IIR filters to do the low pass filter. Then for the high pass, I delay it by a magic number and subtract this from the original. From what I understand, this shouldn't work very well thanks to the phase response of the IIR... but in practice it seems to work (just don't change the frequency without retuning the cutoff).

The C, GPL3 code.

I got a new toy last week. Today I discovered that the colours on it match the ubuntu palette.

I thought my computer was being sluggish, and I didn't know why. It turned out that it was just my left mouse button dying, and hence the computer seemed unresponsive.

Now I have the left/right buttons switched, and for some reason, it is putting my mind into "whacky input mode", and I keep on thinking the keyboard is dvorak.

For the cube, it is pretty much the same as any other > 3x3 rubik's cube, except bigger and more awesome. With the larger cubes, if you solve them the way I do (and I think most other people do) you get parity issues, where you get really close to the end, and then realise that some pieces are out of place and if you just use the set of moves you have been using, then you won't be able to fix them. Up until a few days ago, my solution had been to scramble the cube and try again.

Wikipedia originally made me think that it wouldn't have parity issues:

Because the centers, middle edges and corners can be treated as equivalent to a 3x3x3 cube, the parity errors sometimes seen on the 4x4x4 and 6x6x6 cannot occur on the 7x7x7 unless the cube has been tampered with.

But it was just referring to the parity issue you get with the even sized cubes that you don't discover until the very end. With the 5x5 and 7x7, you realise there is a parity problem a bit sooner, but it is still there. My first solve I got lucky and had no parity problems, which confirmed my misreading of wikipedia. The second time around, I had a double parity problem, which made me think that I should get a method for deterministically fixing the parity problems (which I have now).

I have a square-1 puzzle which I've solved once. Unfortunately my algorithm wasn't general enough to work all the time, and I don't have a good sense for probabilities on those puzzles, so I don't know what the chances of it working are (my guess would be 1/8 or 1/16). I think my big problem with the square-1 is that it is difficult to remember the state of the puzzle before you do a move sequence, so you can work out what has changed. Even notating a move sequence is difficult. (though I don't understand the notation people use for rubik's cubes either).

I was recently given the task of cleaning up some audio tracks that were recorded on a setup where there were word clock synchronisation issues between two of the boxes in the recording chain. The glitches looked a bit like this:

And they were very frequent (about 1 a second, but sometimes more or less, sometimes two within a few samples of each other).

I wrote a program that would fix them automatically, it was written fairly quickly, and fairly experimentally (I didn't know exactly which approach would be best for fixing them, so I tried several, and hacked lots of methods to see if they could be improved). As a result, the code isn't particularly nice to follow, but it is farily short, and gives a nice starting point if you have a similar problem.

The basic approach was to look at windows of samples, and calculate some statistics about them (e.g. mean and variance) then calculate those same statistics, but with the very middle sample ignored. If the statistics for these two windows were too different, then the middle sample is declared to be a possible glitch and given some sort of score for how wrong the stats were.

Then, all the possible glitches are filtered somehow, to get rid of some of the common cases for false positives. For me, this was somewhere in the middle still, there were still some glitches that were missed, and lots of false positives in noisy sounds (like 'esses'). I did experiment with an 'ess' detection thing, but the repairing was so subtle, I turned it off in order to fix as many glitches as possible, since they were very noticable.

Repairing was done by just taking the mean of the adjacent samples. This was fine, but I'm guessing if the glitches were longer than 1 sample, then this would sound bad.

Get the GPL3 C Code for it. Should compile without anything fancier than gcc and make.

This is a game I made last week. It mixes together three different video games into one. It is actually quite fun to play, which is something that surprised me. The interaction of tetris and asteroids adds a whole lot to the asteroids game (and basically destroys the tetris game). While you are out shooting and dodging asteroids, you can build a safe haven out of the tetris blocks that have fallen, so you can get yourself into a safer area when there are lots of asteroids around. But you can't just camp there the whole game, or else the tetris blocks will reach the top of the screen.

I think I'm a big fan of games where you can do some sort of construction, even if it is as basic as shooting out a hole in a stack of tetris blocks and calling it a bunker. That part of me makes me want to call myself creative, but then when I look at the people that you would typically call creative (i.e. the artsie types), I don't see many similarities.

The code is C code (GPL3), it uses SDL for graphics and input. There is even a precompiled linux (x86) binary in there (but there is also a working makefile). Theoretically it should compile and run in Windows. I tried and failed (you might think that a compiler with the year 2005 in its name would be able to compile C99 code, but you would be wrong) and don't really have enough access to Windows machines or desire to fiddle with them in order to get a Windows binary. I'd be happy to host it though if someone makes one (send me the files you used to build it too, since that sort of thing is useful).

Finally, press Escape to exit, I never got around to listening to the window manager events.

---

This is another non-linear audio filter. The idea is that you take the original signal (which is a line of zero thickness in a time-amplitude scale) and trace over it with a thick elliptical brush. This gives an area which follows the shape of the line, but some of the little kinks will be taken out, and the peaks will be rounded. We then have to convert this area into a line, this is done by just taking a point in time and finding the average of the minimum and maximum amplitudes for that time. There are other ways of doing this step which will give different results, but I used this one because it is simple.

In my mind, I was expecting it to be a sort of low-pass filter, as the high frequency stuff would be blurred out by the "brush". What actually happened was that it has more of a comb-filter like effect. If you run it on pink noise you get a frequency response curve that looks like this:

(without filtering, this wouldn't have all the bumps in it).

Since the filter isn't linear, you can't generalise and say it will have a comb filter effect for all input signals, but for the stuff I've tried it on, it generally gives a comb filter like effect. On more aggressive settings, certain notes will sound much louder than other notes. I've chosen two examples that I'd think are usable, and while they are quite obvious, they aren't so aggressive as to add the really noticable loud notes:

Original signal, Paint Filtered 1, Paint Filtered 2.

Get the source (C, GPL3, includes makefile, and is a little bit dumb in one spot where instead of using a circular buffer I shift every value in a buffer across a spot).

Answers

Check with a piece of paper (cover up the distracting bits) or open it in a graphics program.

The Annoyance

One of the things that always annoys me with optical illusions is that typically as soon as you read the question, you know what the answer is. e.g. "Which line is longer?" (they are the same length) "Are these two squares the same colour?" (yes). Are these lines parallel? (yes).

So I made these illusions such that you can't really guess the answer just by reading the question. In some of them, what your eyes see will actually give you the correct answer (just your eyes are seeing an exaggerated form), other times they will be right off.

It doesn't include any of my favourite illusions, because they are too hard to make.

Generally, suburbs that are near each other have postcodes that are in the same ballpark. Since postcodes are only 1 dimension, and locations are 2 dimensions, there are obviously going to be plenty of exceptions to the rule. But not so many that you can't make a graph like this:

So if you have two postcodes which are 10 apart (say 2000 and 2010), then on average they should be 105km apart (assuming you are working with Australian postcodes).

The graph can be drawn so it goes further in the x-direction, but things get a bit silly then:

Towards the very right, there aren't many datapoints at all (there aren't many postcodes 8000 apart) so it is actually quite accurate there, it just doens't look as cool.

I sourced my postcode data from sixfive.co.uk, processed it with python (since I'm using it at work, I figure I might as well do more with it) and plotted it with gnuplot. I also worked under the assumption that 1 degree of longitude or latitude is 111km, which I think is about right for most of Australia (though I was doing this from memory, not wikipedia). In any case, if you are using the actual numbers here for anything serious, then you are doing something wrong.

Another quick post (quick in terms of me writing this bit - not much proof reading or going out of my way to make things clear), this time with some toys to play with.

Compressor

The first is a cool compressor, which is way more general than anything I've seen. (This is talking about dynamic range compression, not compression in the file size domain like mp3).

For those not in the know, a compressor will try to increase the volume of the quieter signals, and keep the loud signals loud (hence it compresses the dynamic range). There are a couple of uses for it, one is destroying the sound of a song (see commercial radio), another is for making something sound better. This compressor should be general enough to do both.

Basically, the compressor will track the loudness of the signal passing through it, and once it goes beyond a certain threshold, it reduce the gain of the signal by some ratio. The exact time that the gain is reduced is controlled by the attack and release (in order to preserve transients, the gain reduction won't kick in straight away, and once the signal drops below the threshold it should also slowly return to the original signal).

This compressor has a very general method for tracking loudness. It takes the power mean of the samples inside a window (this gives us two parameters - the size of the window, and the type of power mean (a power mean is the generalisation of most means, so you can do an arithmetic mean, rms, or anywhere in between (or outside))). Power mean is then low pass filtered, which prevents it from jumping around lots (another parameter).

So then for every loudness, we have a response curve which maps an input value to an output value. e.g. we could have a curve that halved all the inputs, which would then halve the amplitude of the output, or we could have something that followed a square root curve, or any other curve. Since there are lots of different loudness levels, we can just specify a couple of these response curves, and assign them to loudness levels, the compressor will then interpolate between these curves to get the actual curve for a particular loudness level.

Frequency Splitter

The next toy is a frequency splitter. This takes a wave file and splits it into a bunch of new wave files each with different band pass filters applied to them. The filters aren't particularly steep edged, so you will get plenty of overlap between the output files in the frequency space. For some things this is bad, for others I can imagine it would be good. I made this as a step to make the compressor a bit more general (so it could be a multi-band compressor). Converting the compressor to being multi-band using this should be trivial, the only reason I didn't do it was because I couldn't decide what the interface would look like (that is, the code interface, not the user interface).

It just uses a whole bunch of low pass filters, and then subtracts the outputs from adjacent filters to get particular bands. Writing a simple low pass filter is super easy (output = a * input + (1 - a) * last_input) and different values of a will give you different frequency responses.

64-bit and Naming Conventions

So in the time between writing the audio library I use and now, I have changed my home coding convention (I did it at the time to ensure I wouldn't confuse work code with home code, now I don't know what the new naming convention will be as I start tomorrow). Also in that time, I moved from being a person who used x86 only to a person who uses x86, Ix86-64 and armel architectures. Some of the code in the libary was assuming 32 bits, now it should work in 32-bit, and does work in 64-bit (testing it is boring).

I also can't decide what type to use for referring to a chunk of memory that I know I'm going to access by byte. I previously used a mixture of char* and unsigned char, now I've changed to void which forces me to be really explicit in places. I'm not sure if I'll stick with this, but that is how it is now.

Download

This should compile in amkel, but there is also a make file. Although I don't like writing them, there is the big advantage that make is everywhere, so for the moment I'm going to write them... until I find/make a better solution.

compress and fsplit (C, GPL3)

There are two armies on either side of an enemy city. They can't see each other. They can only communicate by sending messengers to each other. When they send a messenger, they might get captured. If both armies attack at the same time, then they will win. If only one army attacks, then they will both lose. All of the information in this question is known to both sides. What should the General commanding each army do?

This is the Two Generals' Problem which I've rephrased slightly to make it quicker to explain, and also to introduce a loophole so you can actually get a solution. I'm not being particularly formal about this, mainly because it makes it easier for me to handwave over the details that I'm trying to handwave over, but also because it is slightly more pleasant to read.

Why it is impossible

Suppose that there is a strategy which lets them agree on the plan. Then, there must also be some sequence of events that happen which mean that they can agree by sending the fewest number of messengers. What if, the very last messenger that was sent was captured? According to our assumption, there is still an agreement so that is fine. But in that case, the strategy could be simplified by not bothering to send that last messenger. Once you do that, you have a contradiction, because we were going for the fewest number of messengers - but we just found a strategy that sends one less messenger.

Why it is possible

The correct strategy is to just attack immediately and not send any messengers. Each General should realise that sending messages will result the problem mentioned above and they will never be able to attack. But, if no messengers are sent, then the proof breaks, as there is no 'last messenger' to capture. Each General should know that the other General is infinitely smart and perfectly rational, so they can know that the other General will realise that the only way they can win is to not send any messengers.

Sneaky Tricks

So in my rephrasing, I gave the Generals a bit more knowledge - they both knew that they were making their decision at the same time. The fact that they are both making the same decision at the same time was difficult to put into the wording without making it obvious that this was the trick I was doing - I tried to do it by not mentioning time at all, and presenting all the facts in the same tense, so there is some concept of a base reference of time.

So there you have it. If you word the problem poorly enough, you can solve it.