July 31, 2018

Pairing functions are used to reversibly map a pair of number onto a single number—think of a number-theoretical version of std::pair. Cantor was the first (or so I think) to propose one such function. His goal wasn’t data compression but to show that there are as many rationals as natural numbers.

Cantor’s function associates pairs (i,j) with a single number:

…but that’s not the only way of doing this. A much more fun—and spatially coherent—is the boustrophedonic pairing function.

Read the rest of this entry »

Universal Coding (Part I)

October 8, 2013

It’s been a while since I last talked about data compression. Let us return to the topic this week with universal codes. Universal codes are entropy-like codes, but, unlike, say, Huffman codes, they presuppose very little on the distribution of the integers to code.


We can use optimally a universal code for a random variable X if

  • all integers may show up: P(X=n)\neq 0, \forall n \in \mathbb{N},
  • and if beyond n_0, the distribution is non-increasing, that is, for n>n_0 and m>n_0, n<m, we have P(X=n)\geqslant P(X=m).

We will show how to build an universal code in a moment, but we will first state the condition that makes a code universal if the probability distribution satisfies the above condition. A code with length function L_u(n) (the length of the code for the integer n) is k-universal if, and only if

\displaystyle\lim_{n\to\infty}\frac{\sum_{i=1}^n P(X=n)L_u(n)}{\sum_{i=1}^n P(X=n)\log_2 n}=k

That is, the expectation of the length (in bits) of the code is proportional to the logarithm of the number being coded.

Let’s now see what an universal code looks like

Read the rest of this entry »

Programming Challenge: Luminance

August 9, 2011

A few years ago, I posted on my personal web page a number of programming challenges for my friends. This week, I present one of the old challenges: computing luma from RGB triplets using integer arithmetic only.

Read the rest of this entry »