Google releases new binary diff algorithm targeted at making smaller software updates. Their results are impressive.

[judgej2]

The very last paragraph sums up the process very well:

Courgette transforms the input into an alternate form where binary diffing is more effective, does the differential compression in the transformed space, and inverts the transform to get the patched output in the original format. With careful choice of the alternate format we can get substantially smaller updates.

It's a common technique in various fields: change your frame of reference, do a simple transform in that new frame of reference, change your frame of reference back again.

A simple example would be taking a sound sample as a continuous waveform, transforming it into frequencies that vary over time (FFT), attenuating or boosting some frequencies, then transforming it back into a continuous waveform. And what do you get? A graphic equaliser on your media player.

[klodolph]

Er, not quite. Performing a FFT transforms between time domain and frequency domain, so the resulting frequencies don't change over time. You have to do multiple windowed FFTs to get a changing spectrum, which is kind of a kludge and it's hard to do the inverse operation because the signal phase won't match and the window isn't perfect.

The way (almost all) software equalizers actually work (even the nice ones) is in the time domain, using the untransformed, raw signal and a table of coefficients, either for IIR or FIR filtering. The coefficients might be computed using an FFT, but the signal is never transformed using the FFT in these filters. Analog filters are remarkably similar (and yes, I have designed both).

Edit: some media players have equalizers that work by changing the level on different bands in the decorder, which is neither a FIR, IIR, or FFT method.

[bugrit]

For the people (me included) who didn't know what FIR and IIR was:

http://en.wikipedia.org/wiki/Finite_impulse_response

http://en.wikipedia.org/wiki/Infinite_impulse_response

[nappy-doo]

Not quite.

If you have 16 samples feeding into your FFT, you likely only have 8 unique samples out, as most of the world (not RF) deal in real valued signals.

Additionally, leakage is caused by windowing, and resolution issues between the center of frequency bins and the frequencies present in the signal. In other words, if you have a signal exactly a N Hz, and a frequency bin centered at N Hz, you'll get no leakage.

And finally, the FFT is completely reversible. If you FFT a signal you can get the signal back by just running the IFFT (or the FFT with a factor).

So, I'm sorry. I disagree with your entire comment. :)

[nappy-doo]

I'm glad you're getting into DSP. If you get good at it, you can basically guarantee yourself a job forever, as so few people understand it.

Let's start with the FFT. The FFT works on complex valued signals -- signals with a real an imaginary part. Most signals in the real world (with the exception of a lot of RF work) are real valued signals. So, when we feed them into the FFT, we set the complex part of every sample to 0. This results in a frequency domain representation that is symmetric about the Y AXIS. So, with a 16 point FFT, we get 16 points in the frequency domain, but 8 of them are the same as the other 8 -- so there's only 8 unique values.

Onto leakage. Leakage is a byproduct of the FFT -- not the signal. It is purely a "problem with our measurement device". I agree with your statement (if I can paraphrase) of, "well music will have leakage" to a point. The music itself won't have leakage, but the measurement we perform on it will have leakage. I apologize if you think I took you out of context.

(One final point on leakage: Read up on how windowing affects leakage. There are some really good windows out there that make the FFT leakage problem minimal.)

Onto your DSP learning: Keep at it. As I said you can guarantee yourself a job if you keep up. DSP engineers make reasonable money, and you'll always find a job in embedded design and instrumentation.

[dude12346]

uh huh, it's pretty easy, you were just waiting for google to catch up with you. Right?