Sunday 6 July 2014

Time Based Compression for Data Transmission

I have been working on random data compression for a few years now, my hobby project, it's been mostly a brute force attempt to steal a bit from a randomly generated data stream. I do realize that recursive compression of data is theoretically impossible, what keeps me going is the belief that random data is just a particular type of data; meaning that randomly generated data is only a subset of all data, if this is true then compression of this data becomes possible.

Since years have passed on this project and I have nothing to show for it but better knowledge and some logical tools and tricks at bit level; I have recently decided to shift my focus to something a bit more possible, compressing random data once during transport. 

Trick being that time itself can be used to transfer more data than what is sent. For this to work, we need a synchronized clock at the source of transmission and another one at the destination and a some estimates of transmission delays.

We can use different number of time windows to send "invisible" bits into. Working with two time-frames we have a saving of 1bit for every 1bit that is transmitted; that is a saving of 50% on the amount of data being sent.


The way this works is the following. We get two bits at a time from the input stream and then send the second bit in the first bit's time window. The four possible values for two bits are 00,01,10 and 11. If the first bit is 0 we send the second bit into the first time window, otherwise we send the second bit into the second time window.

At the receiving end the receiver checks it's clock and determines at what time-frame the data arrived; the transmission delay should be considered, I'm assuming minimal delay in the example. If the data arrived at time-frame 0 a 0 is enqueued followed by the data that has arrived. Otherwise a 1 is enqueued followed by the data. This yields two bits of data for every bit that is sent.

The way this is at the moment is very hard to use for things such as network transmission, it could probably be implemented for on-board systems with little trouble, systems that have a synchronized clock running and that have small stable latency variations. 


The current code is proof of concept and can be optimized. Also, in this example there is no increase of transmission speed, because two time-frames expire before two bits of data are collected. However if the time-frame is reset after the first bit, there is a 50% chance (considering random data) that two bits will be transmitted in one time-frame, thus increasing the transfer rate.

Code below is C# using VS2013.

/// <summary>
/// Time Based Compression for Data Transmission
/// by Sasha Adamovic 
/// 2014
/// sasha.adamovic@gmail.com
/// </summary>
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace timeCompression
{
    class Program
    {
        const long timeWindow = (long)(TimeSpan.TicksPerMillisecond * 5);
        const long halfWindow = (long)(TimeSpan.TicksPerMillisecond * 2.5);

        private Random rnd = new Random((int)DateTime.Now.Ticks);
        private long total = 0;

        static void Main(string[] args)
        {
            Program app = new Program();

            while (true)
            {
                Queue<bool> dataToSend = new Queue<bool>();

                //get some data
                for (int i = 0; i < 1024; i++)
                {
                    bool bit = app.rnd.Next(2) == 0 ? false : true;
                    dataToSend.Enqueue(bit);
                }

                //store original so we can check it
                Queue<bool> original = new Queue<bool>(dataToSend.ToArray());
                Queue<bool> result = new Queue<bool>();
                
                //count the number of bits sent, just to be sure
                int bitsSent = 0;
                while (dataToSend.Count != 0)
                {
                    //check the first bit
                    if (!dataToSend.Dequeue())
                    {
                        //wait for proper time-frame
                        while (DateTime.UtcNow.Ticks % timeWindow > halfWindow)
                            ;

                        //send one bit
                        app.sendData(dataToSend.Dequeue(), ref result);
                        bitsSent++;
                    }
                    else
                    {
                        while (DateTime.UtcNow.Ticks % timeWindow < halfWindow)
                            ;
                        app.sendData(dataToSend.Dequeue(), ref result);
                        bitsSent++;
                    }
                }
                //add to running total
                app.total += bitsSent;
                app.total -= original.Count;

                //check data
                for (int i = 0; i < original.Count; i++)
                    if (original.Dequeue() != result.Dequeue())
                        Console.WriteLine("!!!!!!!!!!");

                //show off
                Console.WriteLine("saving:" + app.total + "bits");
            }
        }

        /// <summary>
        /// send/recieve a bit, then append to data
        /// </summary>
        /// <param name="bit">bit being sent</param>
        /// <param name="result">result</param>
        private void sendData(bool bit, ref Queue<bool> result)
        {
            if (DateTime.Now.Ticks % timeWindow < halfWindow)
            {
                result.Enqueue(false);
                result.Enqueue(bit);
            }
            else
            {
                result.Enqueue(true);
                result.Enqueue(bit);
            }
        }
    }
}