User:IMalc/Punctured Elias codes

Punctured Elias Codes are a universal code developed by Peter Fenwick. They are based upon Elias Gamma codes, but with some major differences. Fenwick describes two variations, P1 and P2. In variation P1 the data bits are written in reverse order, and are preceeded by a zero-terminated sequence of ones, to indicate the number of 1 bits. Zero is encoded as-is with no following bits. Unlike the Elias gamma code, it is not possible to merge the last bit of the prefix with the most significant data bit.

The feature of counting only the number of ones in the number being encoded rather than counting the total number of binary digits leads to codes that are not of strictly increasing length with respect to the number being encoded. This is most noticable when comparing the encoding of 2^N-1 and 2^N e.g. 15 and 16.

The P1 code begins:

 0 0
 1 10 1
 2 10 01
 3 110 11
 4 10 001
 5 110 101
 6 110 011
 7 1110 111
 8 10 0001
 9 110 1001
10 110 0101
11 1110 110
12 110 0011
13 1110 1011
14 1110 0111
15 11110 1111
16 10 00001
17 110 10001

In variation P2, each number n is coded as n+1, and because there will then always be at least one bit that is a 1, the leftmost 1 of the resulting code is omitted.

The P2 code begins:

 0 0 1
 1 0 01
 2 10 11
 3 0 001
 4 10 101
 5 10 011
 6 110 111
 7 0 0001
 8 10 1001
 9 10 0101
10 110 110
11 10 0011
12 110 1011
13 110 0111
14 1110 1111
15 0 00001
16 10 10001

Encoding

To P1 encode a number:

1. If the number is zero, encode a zero and stop. Otherwise:
2. Count the number of 'one' bits in the binary representation of the number (K).
3. Output (K) one bits.
4. Append a zero bit.
5. Append the number in binary from least significant bit to least significant bit (i.e. backwards).

Decoding

To P1 decode a Punctured Elias delta-coded integer:

1. Read and count ones from the stream until you reach the first zero. Call this count of zeroes N.
2. If there were no ones encountered before the zero, then output zero and stop. Otherwise:
3. Continue reading bits until N more 1 bits have been found. As each bit is read, prepend it to the result.

P1 Example:

11101101
1. three leading ones found in: 1110
2. continue reading until three more one bits are found: 1101
3. store these bits in the reverse order: 1011
3. encoded number = 1011 = 1110

See also

• Elias gamma coding

Category:Numeral systems Category:Lossless compression algorithms