Arithmetic code: from interval to code value

Question

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?

Answer 1

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

Answer 2

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.