Part 2 – Encoding a simple value

For the second part, we will encode a simple 4 bit integer value – let’s use the the 4 bit integer 6 to encode, this is our “message”. The integer six has a 4 bit binary value of 0110. To help us understand the process of encoding we will illustrate step by step how it is done. For our simple encoder we will use the following variables top(top), bottom(bot),bit (bit), probability(prob), message(message). This example will assume a 50% probability of any bit value 0 or 1 to be encoded.

First we initialize our range. Now remember from the first example, our range is our decimal values. Well let’s start with the same range 0 to 15 (a 4 bit range). Our range has a top and a bottom. We will assign the bottom variable the bottom value of the range, that value is a 0. Next we assign the top value, the top portion of our range, that value is a 15.

Currently we have assigned the following variables some initial values:

message = 0110 
bot = 0
top = 15

Here are the steps of the encoding process for our message;

  1. Extract our first bit to encode, from our message; bit = 0   {message=0110}
  2. Always get the probability of the zero bit; prob = 0.5 (use 0.5 for our example)
  3. Encode our first bit using our range of 0 to 15. Partition the range into two new ranges using the probability of the zero bit.
    1. first partition is 0 to 7 (50% of the total range).  The second partition is 8 to 15 (what is left over of the total range).
    2. Now we need to update our variables with our new range. The new range will depend on the current bit we are encoding. If the bit is 0 then we choose the first partition if the bit is 1 then we choose the second partition. In this example the bit is 0 so our variables would be update like so:
      bot = 0
      top = 7

Quick overview of encoding our message:

  1. Extract bit from message
  2. Get probability of the zero bit
  3. Partition the range into two ranges
  4. Choose partition depending on bit, 0 bit=first partition, 1 bit=second partition
  5. Update top and bot variables with the new range
  6.  Goto step 1, extracting the next bit in the message

You would continue this process until you are at the end of your message or if the range is equal to zero ie:  (top bot) is equal to zero.  We will get into more detail on this in the next part of our series. Below is an illustration of the process of encoding our message.  

 4 bits have been successfully encoded with an end result/code of 6. This is the same as the original message only because the probabilities for each bit to be encoded are equal, 50%. So the message has no compression and the code or result does not change from the original message.  This is the beginning of bit encoding.

Posted in Compression | Leave a comment

Part 1 – Introduction to a simple bit encoder

To start off in the first part our series we will take a look at the properties of a 4 bit integer to help imagine where our simple bit encoder comes from. For purposes of encoding and decoding data we will refer to our decimal values as our range, and every range has a top and a bottom value.

Looking at the illustration below we can see that the msb of our range can be partitioned into two groups. The second table illustrates the partioning of the msb, as you can see an integer range of 0 to 7 has a msb of 0, and an integer range of 8 to 16 has a msb value of 1. This table can be further partitioned into two ranges using the third bit. The range of 0 to 3 has a 3rd bit of 0,  and the range of 4 to 7 has a 3rd bit of 1.

Binary Partitioning of a 4 bit integer

Following this sequence you can continue to equally sub divide our 4 bit integer ranges into  further binary nodes, creating a binary tree. What is the signfigance in this ? Well our bit encoder will work with a range of values and partition that range depending on the probability of the bit we wish to encode. For the simplest example we will use a 50% probability for every bit, for encoding in our next part.

Continue to Part 2 – Encoding a simple value

Posted in Compression | Leave a comment