Exponential Columbus encoding is a variable length encoding, similar to Huffman encoding, different from Huffman encoding is that it does not need to save a code table in decoding, can be directly decoded according to the code word.

coding

The exponential Columbus code consists of a prefix and a suffix, both of which depend on the order K of the exponential Columbus code. For a non-negative integer N, the exponential Columbus code of order K is generated by the following steps.

  1. Convert the non-negative integer N to binary form, remove the lowest k bit, and add 1.
  2. Count the remaining bits and subtract 1 from this number, which is the number of prefix zeros to add.
  3. Replace the lowest k bit removed in Step 1 with the end of the bit string.

Example: Compute the 1st order exponential Columbus code of 4

  1. The binary form of 4 is 100, which becomes 10 by removing the lowest bit, and 11 by adding 1.
  2. The number of bits in 11 is 2, so the number of prefixes of 0 is 1.
  3. Add the 0 removed in step 1 to the end of the bit string, resulting in the code word 0110.

decoding

Analytic K-order exponential Columbus coding process is as follows:

  1. Search for the first non-zero bit from the current bitstream location, and count the number of zeros found as m.
  2. The decimal value of m+ K bits after the first non-zero bit is value.
  3. Press the following formula to compute the decode value CodeNum.

As can be seen from the above procedure, exponential Columbus encoding based on these rules, the decoder can quickly determine the length of a code word and decode it by simple calculation.

Exponential Columbus codes are variable-length codes, and the basic principle is to use short codes to represent higher frequency codes and long codes to represent lower frequency codes.

The exponential Columbus code of order 0 is a common one in the exponential Columbus code family. It can directly parse the code word according to the formula and has low decoding complexity.

Zero order exponential Columbus code

The zero-order exponential Columbus code is composed of prefix and suffix, and prefix length L_pfx and suffix length L_sfx satisfy l_PFX-1 =L_sfx.

The prefix has the unary code form 00…. 01, where the number of 0 M is

The binary representation of an INFO decimal value with a suffix:

CodeNum is the coded numeric index; for the unsigned number V, CodeNum=V.

For signed numbers,

The zero-order exponential Columbus decoding is performed by reading M bits before the first 1 and M bits after the first 1 INFO. The CodeNum is computed using this notation.

And then compute V depending on whether it’s signed or unsigned.

Again, take Vlaue =4 as an example to explain the zero-order exponential Columbus encoding and decoding process:

Code:

M=log of 4+1 =2, so the prefix is 001. The prefix length is 3, and the suffix length is 2.

INFO=4+1-2^M=1. The binary form is 1 and the suffix is 01.

The final coding result is 00101. That’s exactly what we did in the last video.

Decoding:

The number of zeros before the first 1, M, is equal to 2. M bits after the first 1, INFO=01=1.

CodeNum = 2 ^ M = 4 + 1-1.

If vlaue is unsigned, V=CodeNum=4.

If vlaue is a signed number, V=-2.

The zero-order exponential Columbus coding is mainly used in VPS, SPS, PPS grammar element coding.

If you are interested, please pay attention to wechat public account Video Coding