[Solved]: Designing a prefix code for integers?

Problem Detail: trying to figure out how to approach this problem.

Suppose a sender in a network wanted to communicate the length n of the block it will be using in a subsequent transmission. If there were not limits on the value of n, there would be a problem to simply send the number in binary, since the receiver would find it difficult to know where the end of the number is. Hence we need to encode the integer n using some variable length prefix code, and send the code for n before the code of the length-n block. Design a prefix code for integers and show that an integer n can be encoded with a codeword of length at most log n + O(log log n) – bits.

So I know Huffman’s greedy algorithm for generating prefix codes, but I don’t have any frequencies to build the 2-tree. I was thinking to solve the problem, I would build a tree for 0-9, but I have a feeling I’m way off with that approach. I’m also not quite sure how to show that an integer can be encoded using log n + O(log log n) bits. Any help to get me started would really be appreciated. Thank you for your time!

Asked By : hedgerh

Answered By : Danny

The following code is often used as a standard prefix-code for natural numbers, which bounds the length of each codeword by $log n+O(loglog n)$: At first, we identify the natural numbers by binary strings: $$(0,epsilon),(1,0),(2,1),(3,00),(4,01),…$$ Lets call $l(x)$ the length of the binary representation of the natural number $x$. Note that for each $xge2$ the following holds: $$lfloorlog xrfloorle l(x)le lceillog xrceil$$ Secondly, lets define $s(x_1x_2…x_n)=underbrace{11…1}_{ntext{ times}}0x_1x_2…x_n$ for binary sequences $x_1x_2…x_n$. Note that the length of $s(x_1x_2…x_n)$ is $2n+1$. Lets further define $x’=s(l(x))x$, where both, $l(x)$ and $x$ are interpreted as their binary representations. Finally, the code $D(x’)=x$ is a prefix code satisfying that for each natural number $x$, the length of the encoding $x’$ is $log x+2loglog x+1$ (ignoring the rounding error).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32730 Ask a Question Download Related Notes/Documents