4
$\begingroup$

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!

$\endgroup$
4
$\begingroup$

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(\log\log 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 $x\ge2$ the following holds: $$\lfloor\log x\rfloor\le l(x)\le \lceil\log x\rceil$$

Secondly, lets define $s(x_1x_2...x_n)=\underbrace{11...1}_{n\text{ 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+2\log\log x+1$ (ignoring the rounding error).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.