October 7th, 2007


Drip drip drip, little Fountain Encoder!

Well, it looks like my Digital Fountain Encoder is working! However, I have no easy way of testing that short of writing a Digital Fountain Decoder, which is a lot more difficult.

All the encoder has to do is select a random number of source packets from the file to be encoded, XOR them together and output them, along with enough meta-information to know which packets have been used.

The Decoder has to read each Drop and work out which source packets it's made of. Easy enough so far. In then has to store the Drop in a digraph (Source Packets:Drops) and wait until it has sufficient drops to retrieve a source packet.

Let's learn a nice bit of information theory, shall we?

Firstly, what is XOR? XOR stands for Exclusive Or. It's the type of OR that we use in everyday speach - "One OR the other BUT NOT both OR neither." The truth table for XOR is thus:

aba XOR b

XOR holds an interesting property: a XOR b XOR b == a
This holds true for any number of operations:
a XOR b XOR c XOR d = x
x XOR d XORc XOR b = a

Oh, and the numbers don't have to be XOR'd together in any particular order:
a XOR b XOR c XOR d = x
x XOR b XOR d XOR c = a

Any number is retrievable from the sum:
a XOR b XOR c XOR d = x
x XOR d XOR a XOR c = b

And that's precisely what it is - a sum. XOR has the same truth table as modulus 2 addition.

Here's the XOR'ing of two binary numbers:
------------------- =

That's basically what the encoder does - it takes binary data from the file in several places and XORs it together.

The decoder needs to keep track of which source packets are contained in each drop and wait for situations such as the following:

Source Packets = {a,b,c,d,e,f,g}

Drop 1 = aXbXcXd
Drop 2 = bXcXdXeXfXg
Drop 3 = eXfXg
Drop 4 = eXg

We can only do a couple of operations here:
Drop 4 X Drop 3 => f
Drop 3 X Drop 2 => bXcXd = k
k X Drop 1 => a
f X Drop 2 => bXcXdXg

This doesn't decode the file, as we don't have enough drops. However, we have managed to decode 2 source packets and simlify our remaining drops.

If you have managed to follow me through this entry, give yourself a pat on the back and 3 gold stars.

Oh, and on a related note? Today I learnt how to do random file access in Java! (That's reading from any given point within a file without having to read all the data up to that point) It's with the RandomAccessFile class, believe it or not.... ¬_¬