Exponential-Golomb Codes¶
As this type of representation of integers isn’t as well known as the standard base-2 representation I thought that a short explanation of them might be welcome. This section can be safely skipped if you’re not interested.
Exponential-Golomb codes represent integers using bit patterns that get longer for larger numbers. For unsigned and signed numbers (the bitstring properties ue
and se
respectively) the patterns start like this:
Bit pattern |
Unsigned |
Signed |
---|---|---|
|
0 |
0 |
|
1 |
1 |
|
2 |
-1 |
|
3 |
2 |
|
4 |
-2 |
|
5 |
3 |
|
6 |
-3 |
|
7 |
4 |
|
8 |
-4 |
|
9 |
5 |
|
10 |
-5 |
|
11 |
6 |
|
… |
… |
They consist of a sequence of n ‘0’ bits, followed by a ‘1’ bit, followed by n more bits. The bits after the first ‘1’ bit count upwards as ordinary base-2 binary numbers until they run out of space and an extra ‘0’ bit needs to get included at the start.
The advantage of this method of representing integers over many other methods is that it can be quite efficient at representing small numbers without imposing a limit on the maximum number that can be represented.
Exercise: Using the table above decode this sequence of unsigned Exponential Golomb codes:
001001101101101011000100100101
The answer is that it decodes to 3, 0, 0, 2, 2, 1, 0, 0, 8, 4. Note how you don’t need to know how many bits are used for each code in advance - there’s only one way to decode it. To create this bitstring you could have written something like:
a = BitStream().join([BitArray(ue=i) for i in [3,0,0,2,2,1,0,0,8,4]])
and to read it back:
while a.pos != a.len:
print(a.read('ue'))
The notation ue
and se
for the exponential-Golomb code properties comes from the H.264 video standard, which uses these types of code a lot. There are other ways to map the bitstrings to integers:
Interleaved exponential-Golomb codes¶
This type of code is used in the Dirac video standard, and is represented by the attributes uie
and sie
. For the interleaved codes the pattern is very similar to before for the unsigned case:
Bit pattern |
Unsigned |
---|---|
|
0 |
|
1 |
|
2 |
|
3 |
|
4 |
|
5 |
|
6 |
|
7 |
|
8 |
|
9 |
|
… |
For the signed code it looks a little different:
Bit pattern |
Signed |
---|---|
|
0 |
|
1 |
|
-1 |
|
2 |
|
-2 |
|
3 |
|
-3 |
|
4 |
|
-4 |
|
5 |
|
-5 |
|
… |
I’m sure you can work out the pattern yourself from here!