universal code | Harder, Better, Faster, Stronger

Universal Coding (Part II)

03/12/2013

Last time, we presented universal codes and two simple code. This week, let’s revisit the topic and present Elias codes, which are much better universal codes than Chaitin’s and modified Chaitin codes.

We will use the idea of recursion introduced before, but we will push the idea further, getting codes with lengths $O(\lg n + \lg\lg n + \lg\lg\lg n + \cdots)$ , which are pretty much as good as it gets.

Read the rest of this entry »

1 Comment | algorithms, data compression, Mathematics | Tagged: 1948, Chaitin, Elias, Entropy, Shannon, universal code | Permalink
Posted by Steven Pigeon

Universal Coding (Part I)

08/10/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