Nerd wannabe

lazy weblog

How does one split 3 bits between two persons?

leave a comment »

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

stop bits

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!

Advertisements

Written by vlad

December 4, 2007 at 9:23 am

Posted in laugh

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: