# Better Than Entropy Compression... Just Joking!

I’ve been working on a long-term project to do with sending messages by encoding the data in time, it’s a free quantity so use it instead of something physical like electrons! What do I mean by “encoding in time” - well here’s a little trick you can try with your kids. You can communicate a number with two blinks - the first blink starts the clock, the second stops the clock. The number communicated is the the interval span between the blinks. So two bits communicate an arbitrary integer - as long as you have accurate clocks. Sub-entropy compression …. Nature beckons …. (I kid :))

There are two problems with getting this system working. The first is to figure out how to send more than one number. The second is how to work with inaccurate clocks. Lets look at these individually.

## How to send more than one number

So you send a bit, leave the channel open leaving a gap, then send another bit. What to do with the gap? Clearly there’s scope to send more than one integer in the gap, the question is how to do this at all, and then efficiently. Remember, the hope is to generate some form of compression.

I’ve got two schemes which rely on self-delimiting codes to record indexes. The self-delimiting code I used is Elias coding . To find out about these read the section on Integer Codes in the fantastic Information Theory Textbook by David Mackay.

## Scheme 1

My first effort at coding scheme algorithm,

1.  For a list of integers say [5,4,7,8]
2.  Index the list using (index,value) [(1,5),(2,4),(3,7),(4,8)]
3,  Sort the list in descending order [(4,8),(3,7),(1,5),(2,4)]
4.  For each tuple write the index twice with a gap of value between them
in a self-delimiting way at the next available spot,
5.  Result: (4,_,3,_,_,1,_,_,4,3,1)


Here’s the pythons to encode and decode this, I using self-delimiting codes so I don’t have to worry about decoding:

## Scheme 2

Another go - trying to remove the start bits, let everything start at 0:

1.  For a list of integers, say [5,4,7,8]
2.  Index the list using (index,value) [(1,5),(2,4),(3,7),(4,8)]
3.  For each tuple write the index once in a self-delimiting way , value distance from the start
4.  Result (_,_,_,2,1,_,3,4]


Orginally, I thought this was a really clever variation on scheme 1, then I realised it’s just a histogram!!

Here’s the code:

Comparing schemes against each other it’s 8,11 to scheme two, So how am I doing when compared to real-world compression? … to be continued