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:

[code lang=’cpp’]message = 0110 
bot = 0
top = 15[/code]

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.