Universal Codes for Integers

Lloyd Allison, Arun S. Konagurthu & Daniel F. Schmidt, 'On universal codes for integers: Wallace Tree, Elias Omega and beyond', Data Compression Conference (DCC), pp.313-322, 22-26 March 2021 [doi:10.1109/DCC50243.2021.00039].

N=
Ints≥  

Above: CW:=enc(N) then check that dec(CW)=N, for each of several codes – Fibonacci, Elias's omega, our omega2 and omega*, and Wallace Tree Code – all for integers ≥0 or ≥1. Note, treat the timings with great caution as who knows when javascript's garbage collector kicks in.

Above: Code-word lengths for powers of 10.

N fib1 omega1 WTC1
1 2 1* 1*
2 3* 3* 3*
3 4 3* 5
4 4* 6 5
13 7* 7* 9
16 7* 11 9
610 15* 17 15*
627 15* 17 17
1597 17* 18 17*
2057 17* 19 19
4181 19* 20 19*
6765 20 20 19*
6919 20* 20* 21
8192 20* 21 21
10946 21* 21* 21*
16384 21* 22 21*
17711 22 22 21*
23715 22* 22* 23
28657 23 22* 23
32768 23* 23* 23*
46368 24 23* 23*
6553624 28 23*
8250125*28 25*
12139326 28 25*
29051327*30 27*
31781128 30 27*

Above: Code-word lengths, early points of change of the lead.

w fib1 omega1 WTC1
1 0 0.5 0.5
2 0.25 0.5 0.5
3 0.375 0.75 0.625
4 0.5 0.75 0.625
10 0.859 0.875 0.754
100 0.999... 0.947 0.920
1000 -"- 0.957 0.975
10000 -"- 0.963 0.992
100000 -"- 0.9688 0.997
1000000 -"- 0.9692 0.9992
∑N s.t. |codeword(N)|≤w p(N)

Above: Cummulative probabilities upto code-word length w (bits).

Code:     

Above: Experiment with robustness; Ns→code-words→code-string→mutate(CW[0])→decode.
Key: || correct number of Ns, # wrong number of Ns, = late numbers correct, non-trivial remnant ⇒ v. bad (error msg shows why).