number of bits of information for n stable states?

Question

my text book says

"An element with N stable states conveys log2N bits of information"

i don't understand it since i expect if we have n stable states we would have n/2 bits since one of them is the bit it self and the other one is it's complement .

why the textbook takes lg of n ?

PS. i think flip flop is the closest tag (in existing tags) for my question

Answer 1

1 bit can have two states: 0 or 1. \$\log_2(2)=1\$.

2 bits can have four states: 00, 01, 10, or 11. \$\log_2(4)=2\$.

3 bits can have eight states: 000, 001, 010, 011, 100, 101, 110, or 111. \$\log_2(8)=3\$.

And so on.

Answer 2

Turn it around: How many different states can B bits represent? The answer is 2^B.

Therefore, if you want to know how many bits it takes to represent N states, you need to find a value for B for which 2^B is at least N.

$$2^B \ge N$$

Take the log₂ of both sides:

$$B \ge log_2(N)$$

The binary bit, representing one choice, such as Yes/No, is the smallest unit of "information". Therefore, any number of states can be expressed in terms of the number of bits that carry the equivalent amount of information.

In the general case, this can be fractional. For example, a 10-state system carries log₂10 = 3.322 bits of information.

Answer 3

It's basically binary.

If you have, say 23 states, those states can be represented by the numbers 0 to 22.

How many bits do you need to represent the numbers 0 to 22?

• 1 bit = 0-1 (\$2^1 = 2\$)
• 2 bits = 0-3 (\$2^2 = 4\$)
• 3 bits = 0-7 (\$2^3 = 8\$)
• 4 bits = 0-15 (\$2^4 = 16\$)
• 5 bits = 0-31 (\$2^5 = 32\$) So you need 5 bits to represent the numbers 0 to 22, since 4 bits is too few. Yes, you have space left over, but you can't have a fraction of a bit.

So, \$log_2(23) = 4.52356195606\$ - rounded up is 5.