|
How many
bits do we need for a given number of messages?
 As
a review, you will remember that the general
formula for determining how many messages we could get for a given number of
bits, we applied the formula:
I = Bn
| where: |
I = |
The amount of information (messages) available. |
| |
B =
|
The base we are working in (Decimal,
Binary, Octal, etc.) |
| |
n
=
|
The number of digits (in
any base) that we have
|
OK,
but we are asking the Question:
"How many bits do we need for a given number of messages?"
NOT
"How many messages we could transmit for a given number of
bits?"
True, but the idea
is the same. All we have to do is Reverse
the procedure:
|
I = |
Bn |
|
log (I) =
|
n
* log (B) |
| n =
|
log
(I)
log (B) |
In Decimal and
Binary, this would mean:
|
Decimal: |
|
Binary: |
|
|
I = |
10n |
I = |
2n |
|
log (I)
=
|
n
* log (10) |
log (I)
=
|
n
* log (2) |
| = |
n * 1 |
= |
n * 0.30103 |
| = |
n |
n = |
log(I)/0.30103 |
| n
=
|
log
(I) |
|
|
What does
this mean??
Suppose I wanted to have, let's say, 25 messages?
Once again, In Decimal and
Binary, this would mean:
|
Decimal: |
|
Binary: |
|
|
25 = |
10n |
25 = |
2n |
|
log (25)
=
|
n
* log (10) |
log (25)
=
|
n
* log (2) |
| = |
n * 1 |
= |
n * 0.30103 |
| = |
n |
n = |
log(25)/0.30103 |
| n
=
|
log
(25) |
n = |
1.397/0.30103 |
| = |
1.397 |
= |
4.644 |
OR, you
would need 1.397 decimal digits or 4.644 binary digits
That
makes no sense at all!!
Actually, it makes perfect sense. Remember what a log means
(in this case log(10)):
To what power must I raise 10 to get the value 10?
Obviously:
101 = 10, or to get the value 10, I
must raise 10 to the 1 power, Similarly:
|
log(100) = |
2
(since
102 = 100) |
|
log (1,000)
=
|
3
(since
103 = 1,000) |
|
log (10,000)
=
|
4 (since
104 = 10,000) |
|
log (100,000)
=
|
5
(since
105 = 100,000) |
|
log (1,000,000)
=
|
6
(since
106 = 1,000,000) |
In the case of log(25) =
1.397, we know that the value must be greater than 1 (since log(10) = 1)
and less than 2 (since log(100) = 2)
 OK,
OK. But that still makes no sense!!
You said that in binary, if I want to be able to represent 25 messages, I need
4.644 bits.
HOW CAN I HAVE 4.644 LIGHT
SWITCHES!!!
Very good point! In fact,
You can't!
The formula should be:
Meaning, the ceiling of Log(I)/Log(B).
That means that IFF (if and only if) the resultant value is a real number
greater than n+.0000, we must raise it to the next whole integer.
What???
Suppose we had 8 light switches. We know that
28 = 256, meaning we can have 256 different combinations. Could we
somehow sneak in 257 combinations??
NOT A CHANCE!!!
log
(256)
log (2) |
= |
2.40824
0.30103 |
= |
8 |
whereas |
Log (257)
log (2) |
= |
2.40993
0.30103 |
= |
8.006 |
Meaning we would need MORE
than 8-bits to represent 257 messages (we would need 9)
GREAT!! So now I have to carry a
calculator at all times!!!
Not At All! This goes back to our
previous tutorial. Suppose I want to represent 78 messages:
|
Given |
I
can Represent |
| 0-bits |
20
= 1 Messages |
| 1-bit
|
21
= 2 Messages |
| 2-bits |
22
= 4 Messages |
| 3-bits |
23
= 8 Messages |
| 4-bits |
24
= 16 Messages |
| 5-bits |
25
= 32 Messages |
| 6-bits |
26
= 64 Messages |
| 7-bits |
27
= 128 Messages |
| 8-bits |
28
= 256 Messages |
| 9-bits |
29
= 512 Messages |
|
10-bits |
210
= 1,024 Messages |
I can't represent 78 messages with 6 bits
(since 26 = 64), but I CAN represent it using 7 bits (since
27 = 128)
I can't represent 12 messages with 3 bits (since 23 = 16), but I
CAN represent it using 4 bits (since 24 = 16)
I can't represent 301 messages with 8 bits (since 28 = 256), but I
CAN represent it using 9 bits (since 29 = 512)
I can't represent 513 messages with 9 bits (since 29 = 512), but I
CAN represent it using 10 bits (since 210 = 1,024)
Once again, notice that this formula works
regardless of the base. To represent the value 78, for example:
|
Base |
Formula |
|
|
|
|
Digits Needed |
| 2
|
log
(78)
log (2) |
= |
1.892
0.301 |
= |
6.286 |
7 |
| 3
|
log
(78)
log (3) |
= |
1.892
0.477 |
= |
3.966 |
4 |
| 4
|
log
(78)
log (4) |
= |
1.892
0.602 |
= |
3.143 |
4 |
| 5
|
log
(78)
log (5) |
= |
1.892
0.699 |
= |
2.707 |
3 |
| 6
|
log
(78)
log (6) |
= |
1.892
0.778 |
= |
2.432 |
3 |
| 7
|
log
(78)
log (7) |
= |
1.892
0.845 |
= |
2.239 |
3 |
| 8
|
log
(78)
log (8) |
= |
1.892
0.903 |
= |
2.095 |
3 |
| 9
|
log
(78)
log (9) |
= |
1.892
0.954 |
= |
1.983 |
2 |
| 10
|
log
(78)
log (10) |
= |
1.892
1.000 |
= |
1.892 |
2 |
| 16
|
log
(78)
log (16) |
= |
1.892
1.204 |
= |
1.571 |
2 |
Once
again, why
would I care about any bases but base 10 and base 2???
Once again, Stay tuned --- We will get to that
Some good references include:
-
How Bits and Bytes Work
-
Data
Structures And Number Systems
- Bits
and Bytes : An Explanation
At this point in time, you should be
able to Answer the following questions:
- What is the
formula to calulate "How many messages we could transmit for a given number of
bits?", and how does it differ from the formula for "How many messages we
could transmit for a given number of bits?"
The formula is the reverse of the
formula for
"How many messages we could transmit for a given number
of bits?"
|
I = |
Bn |
| log (I) =
|
n
* log (B) |
| n =
|
log
(I)
log (B) |
- How would we apply
this formula in decimal and binary? How many digits would it take to represent
the value 123 in decimal and binary?
|
Decimal: |
|
Binary: |
|
|
I = |
10n |
I = |
2n |
|
log (I)
=
|
n
* log (10) |
log (I)
=
|
n
* log (2) |
| = |
n * 1 |
= |
n * 0.30103 |
| = |
n |
n = |
log(I)/0.30103 |
| n
=
|
log
(I) |
|
|
If we wished to
represent the value 123, In Decimal and
Binary, this would mean:
|
Decimal: |
|
Binary: |
|
|
123 = |
10n |
123 = |
2n |
|
log (123)
=
|
n
* log (10) |
log (123)
=
|
n
* log (2) |
| = |
n * 1 |
= |
n * 0.30103 |
| = |
n |
n = |
log(123)/0.30103 |
| n
=
|
log
(123) |
n = |
2.0899/0.30103 |
| = |
2.0899 |
= |
6.9425 |
OR, you
would need 2.0899 decimal digits or 6.9425 binary digits
-
How can the number of
digits required to represent messages be a real number?
IT CANT'T!!!
The formula should
be:
Meaning, the ceiling of Log(I)/Log(B).
That means that IFF (if and only if) the resultant value is a real
number greater than n+.0000, we must raise it to the next whole integer.
- How many digits would we need to represent the values
18, 789, and 10956 in binary?
|
Value |
Formula |
|
|
|
|
Digits Needed |
| 18
|
log
(18)
log (2) |
= |
1.255
0.301 |
= |
4.048 |
5 |
| 789
|
log
(789)
log (2) |
= |
2.897
0.301 |
= |
9.345 |
10 |
|
10,956 |
log
(10956)
log (2) |
= |
4.040
0.301 |
= |
13.031 |
14 |
We could also have found the answer since we know 24
= 16, 25 = 32, and 29 = 512, 210 = 1024, and
213 = 8192, 214 = 16384.
The formula used to determine how many digits we need
for a given number of messages is:
a. n = IB
b. n = BI
c. n = I log(B)
d. n = log(B)/log(I)
e. n = log(I)/log(B)
Answer: e
The value of log(167) is:
a. Between 0 and 1
b. Between 1 and 2
c. Between 2 and 3
d. Between 3 and 4
e. Between 4 and 5
Answer: c
To represent 513 messages in binary, we need
a. 7 bits
b. 8 bits
c. 9 bits
d. 10 bits
e. 11 bits
Answer: d
This page was last updated on
01/06/05
|
CIS3355:
Business Data Structures