User:IMalc/Punctured Elias codes

This is not a Wikipedia article: It is an individual user's work-in-progress page, and may be incomplete and/or unreliable. For guidance on developing this draft, see Wikipedia:So you made a userspace draft.  Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL Easy tools: Citation bot (help) | Advanced: Fix bare URLs This page was last edited by [[User:|]] ([[User talk:|talk]] | contribs) 0 seconds ago. (Update timer) Finished writing a draft article? Are you ready to request an experienced editor review it for possible inclusion in Wikipedia? Save your work by pressing the "Publish page" button below, and a button will appear here allowing you to submit your draft for review.

Punctured Elias Codes are a universal code developed by Peter Fenwick^[1]. 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