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.
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
