4
$\begingroup$

Here is a schematized binary channel that neatly conveys a decimal number. $ \require{begingroup}\begingroup \def\T {{ \cal T }} \def \Ti {{ \T \raise5mu{ \text- \scriptsize 1 } }} \def\Bx #1{{ ~ \rightarrow ~ \boxed{\, #1 \,\Large\strut} \: \rightarrow ~ }} \def \BTi {\Bx { \kern 1mu \Ti \kern1mu }} \def \BT { \Bx{ \rlap{\kern6mu \T} \phantom\Ti }} $

$$ 123_{(10)} \BT 1111011_{(2)} \BTi 123_{(10)} $$

But how to keep up with an endless stream of decimal digits?

$$ 1, \, 2, \, 3, \, \ldots _{\, (10)} \BT \ldots \, ? \ldots _{\, (2)} \BTi 1, \, 2, \, 3, \, \ldots _{\,(10)} $$

Binary coding with 4 bits for each decimal digit works readily:

$$ 1, \, 2, \, 3, \, \ldots _{\, (10)} \BT 0001 ~ 0010 ~ 0011 \, \ldots _{\, (2)} \BTi 1, \, 2, \, 3, \, \ldots _{\,(10)} $$

Yet this wastes the binary channel's capacity, with a bitwise efficiency of just $ \, \frac{\log_2 10}{4} = 0.83^+ $. The waste can be reduced with larger groupings, such as coding 3 digits at a time with 10 bits for an efficiency of $ \, \frac{\log_2 1000}{10} = \frac{3}{10} \, \log_2 10 = 0.996^+ $, which remains measurably less than $1$ and increases maximum lag from 4 bits to 10 bits.

Is there a straightforward algorithm pair, $\T$ and $\,\Ti$, with bounded lag, that is asymptotically wasteless when given an input stream of evenly random decimal digits?

$$ \dfrac {\small\text {cumulative number of decimal digits conveyed}} { \small\text{cumulative number of bits used in transmission}} ~ {\log_2 10} {\large~\xrightarrow{\quad}~} 1 $$

Please ground any algorithms in terms of specific bases, not necessarily decimal and binary, perhaps ternary and binary, that are not rational powers of each other. A general solution would be easy enough to gather from that. This is an inquiry into ideal, not just efficient, conversion of information.


Addenda

Another straightforward suboptimal approach is to Huffman code each digit as in the following table. This has a respectable average efficiency of $ \, \frac{1}{3.4} \, \log_2 10 = 0.977^+ $ and maximum lag of 4 bits.

$$ \small \begin{array}{lrrrrrrrrrr} \rm Decimal & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\\rm Binary & 000 & 001 & 010 & 011 & 100 & 101 & 1100 & 1101 & 1110 & 1111 \\\rm Bit~count & 3 & 3 & 3 & 3 & 3 & 3 & 4 & 4 & 4 & 4 \\[1ex] \rm \rlap{Average~bit~count~~~~3.4} & & & & & & & & & & \end{array} $$

Any table-lookup encoding, such as every approach mentioned above, will indeed have bounded lag but nonetheless be measurably inefficient.

An optimally efficient approach with unbounded lag, as commented by leonbloy, is arithmetic coding, which interprets sequences as fractions that readily convert between decimal and binary. The potential for unlimited lag can be seen already in the first decimal digit, below, as the binary transmissions for $ \, 5,9,8, \ldots _{\, (10)} \, $ and $ \, 6,0,0, \ldots _{\, (10)} \, $ are indistinguishable until the 9th bit.

$$ 5,9,8, \ldots _{\, (10)} \Bx{~ 0.598 ... _{(10)} = 0.100110010..._{(2)} \raise-6mu\strut~} 1,0,0,1,1,0,0,1,0, \ldots _{\, (2)} \\[3ex] 6,0,0, \ldots _{\, (10)} \Bx{~ 0.600 ... _{(10)} = 0.100110011..._{(2)} \raise-6mu\strut~} 1,0,0,1,1,0,0,1,1, \ldots _{\, (2)} \endgroup $$

$\endgroup$
  • $\begingroup$ Can you transmit them right to left? $\endgroup$ – MJD Jun 6 '16 at 5:51
  • $\begingroup$ Now I think my idea won't work, sorry. $\endgroup$ – MJD Jun 6 '16 at 6:10
  • 1
    $\begingroup$ I doubt there's any algorithm with bounded lag and asymptotically no waste. No matter how many bits you look at, there will be some ambiguity in the binary equivalent. $\endgroup$ – Gerry Myerson Jun 6 '16 at 7:19
  • 1
    $\begingroup$ The optimal way would be with arithmetic coding. But the lag is unbounded. $\endgroup$ – leonbloy Jun 7 '16 at 21:20
  • 1
    $\begingroup$ You may want to look at O. Shayevitz et al. "Delay and Redundancy in Lossless Source Coding," in IEEE Transactions on Information Theory, vol. 60, no. 9, pp. 5470-5485, Sept. 2014. and references within. $\endgroup$ – Batman Jun 15 '16 at 1:48

Your Answer

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

Browse other questions tagged or ask your own question.