1
$\begingroup$

I've not clear how to pass from final interval to code value, for example:

Suppose we have the set of symbols={0,1,2,3} with probability={0.2, 0.5, 0.2 , 0.1} and that we have to encode a source S={2,1,0,0,1,3};

After the encoding process we'll have an interval $[ 0.7426, 0.7428 ) $.

Now the final step is to find the shortest representation to transmit and in the book the chosen value is 0.10111110001 = 0.74267578125.

How is it possible to calculate the shortest representation and the code value to transmit having the final interval?

$\endgroup$
3
$\begingroup$

You transmit the bit pattern of the left(smaller) end, until you either run out of bits or you find a difference of the left and the right (bigger) number. The first difference will have a 0 on the left side, and a 1 on the right side. If this 1 is not the last bit on the right side, you transmit this 1 and you are done, you transmitted the shorted number from within the interval.

a=0011001100
b=0011010010
->001101

If this 1 is the last bit you cannot transmit it directly, because then you would send exactly the right end which is not within the interval. In this case you have to continue sending bits from the left side, until you hit the next 0. Here you transmit a 1, and you are done.

a=00110010101
b=00110011000
->0011001011
$\endgroup$
1
$\begingroup$

One method that comes to mind is computing in tandem the next value (in lexicographic order), and storing enough bits to separate the two. This doesn't incur double computation, since most of the time carry lasts only for the few last symbols.

$\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.