Nerd wannabe

lazy weblog

How does one split 3 bits between two persons?

You noticed it: you had problem with you dial-up, you fiddled with your modem settings, you thought you knew something about how computers work, then it struck you: stop bits: 1, 1.5 or 2

How does one define half a bit?

First, let’s say how do we define a bit: binary digit. In the binary system, only 0 and 1 are digits. So one bit is either 0 or 1… we’re not getting anywhere, aren’t we?

Let’s go further and dig the Shannon definition: the information gathered from tossing a coin, each side having equal probabilities to show up.

So one bit of information is gathered from a coin with equal probabilities for the sides. How would a coin that emits a half bit look like?

What happens if the sides don’t have equal probabilities? Let’s say the probabilities are p1 and p2

$bits = -p_1log_2(p_1)-p_2log_2(p_2)$

For $p_1=p_2=\frac{1}{2}, log_2(\frac{1}{2}) = -1$ therefore the number of bits is $-\frac{1}{2}\cdot(-1)-\frac{1}{2}\cdot(-1)=\frac{1}{2}+\frac{1}{2}=1$ bit. Exactly one bit.

Question is, what are the probabilities the coin’s sides should have to transmit a full half-a-bit?

Given that the two probabilities must sum exactly 1, therefore are $x$ and $1-x$ respectively (just like $\frac{1}{2}+\frac{1}{2}=1$), the problem of how does one split one bit in two becomes

If $-xlog_2(x)-(1-x)log_2(1-x)=0.5$ bits, what’s the value of $x$?

Using an online newton approximation and guessing 0.25 as the ‘seed’ the solution becomes 0.11002786443836 or roughly 0.11.

So, each time a modem wants to send 1.5 bits, it sends a bit and it tosses a special coin that has 0.11 probability to fall on one side and 0.89 probability to fall on the other side.

Now that’s some light shed on modem’s speed bottleneck!