>

   
APPENDIX: A Tutorial On Logarithms

Understanding the Log Function. In the mathematical operation of addition we take two numbers and join them to create a third:

1 + 1 = 2. (21)

We can repeat this operation:

1 + 1 + 1 = 3. (22)

Multiplication is the mathematical operation that extends this:

$$\frac{1}{12} \times \log_2(\frac{1}{12}) \; + \; \frac{8}{12} \times \log_2(\frac{8}{12}) ]$$ (23)

In the same way, we can repeat multiplication:

$$\;$$ (24)

and

$$\log_2 8 = 3$$ (25)

The extension of multiplication is exponentiation:

$$\sqrt{P_y + N_y}$$ (26)

and

$$\sqrt{N_y}$$ (27)

This is read ``two raised to the third is eight''. Because exponentiation simply counts the number of multiplications, the exponents add:

$$\sqrt{P_y}$$ (28)

The number `2' is called the base of the exponentiation. If we raise an exponent to another exponent, the values multiply:

$$\lambda$$ (29)

The exponential function y = 2^x is shown in this graph⁴:

Now consider that we have a number and we want to know how many 2's must be multiplied together to get that number. For example, given that we are using `2' as the base, how many 2's must be multiplied together to get 32? That is, we want to solve this equation:

2^B = 32. (30)

Of course, 2⁵ = 32, so B = 5. To be able to get a hold of this, mathematicians made up a new function called the logarithm:

$$\frac{4}{3}\pi r^3$$ (31)

We pronounce this as ``the logarithm to the base 2 of 32 is 5''. It is the ``inverse function'' for exponentiation:

$$v_{before} \propto r_{before}^D = \sqrt{P_y + N_y}^D$$ (32)

and

$$v_{after} \propto r_{after}^D = \sqrt{N_y}^D$$ (33)

The logarithmic function $M = v_{before} / v_{after} = \sqrt{\frac{P_y}{N_y} + 1}^D$ is shown in this graph⁵:

This graph was created by switching the x and y of the exponential graph, which is the same as flipping the curve over on a 45 $\log_{2} M$ line. Notice in particular that $$C_y = d_{space}\log_{2}{\left( \frac{P_y}{N_y} + 1 \right)} \;\;\;\;\;\mbox{(bits per operation).}$$and $\log_2(0)=-\infty$.

The Addition Law. Consider this equation:

$$\fbox{ $2^{a + b} = 2^a \times 2^b$ }$$ (34)

which is just a generalization of equation (28). Take the logarithm of both sides:

$$\log_2{2^{a + b}} = \log_2 \left( {2^a \times 2^b} \right)$$ (35)

Exponentiation and the logarithm are inverse operations, so we can collapse the left side:

$${\cal E}\equiv \frac{P_y}{C_y}$$ (36)

Now let's be tricky and substitute: ${\cal E}$and $${\cal E}_{min}$$:

$$\equiv$$ (37)

Again, exponentiation and the logarithm are inverse operations, so we can collapse the two cases on the right side:

This is the additive property that Shannon was interested in.

The ``Pull Forward'' Rule. From equation (32):

$$\lim_{P_y \rightarrow 0} \frac{P_y} {d_{space}\ln \left( \frac{P_y}{N_y} + 1 \right) / \ln(2) }$$ (39)

Raise both sides to the u:

$${\cal E}_{min}= \lim_{P_y \rightarrow 0} \frac {\ln(2) \left... ... 1 \right) N_y} {d_{space}} = \frac{\ln(2) N_y }{ d_{space}}$$ (40)

Now, we can combine the exponents by multiplying, as in (29):

$$\frac{1}{2} k_{\mbox{\scriptsize B}}T$$ (41)

Finally, take the log base 2 of both sides and collapse the right side:

$$N_y = ({\textstyle \frac{1}{2}} k_{\mbox{\scriptsize B}}T) \times (2 d_{space}) .$$ (42)

This can be remembered as a rule that allows one to ``pull'' the exponent forward from inside the logarithm.

How to Convert Between Different Bases. Calculators and computers generally don't calculate the logarithm to the base 2, but we can use a trick to make this easy. Start by letting:

$${\cal E}_{min}= k_{\mbox{\scriptsize B}}T \ln(2) \;\;\;\;\; \mbox{(joules per bit)} .$$ (43)

Rearrange it as:

$$H \equiv - \sum_{i = 1}^\Omega P_i \log_2 P_i \;\;\;\;\;\mbox{(bits per microstate)}$$ (44)

Now use a ``reverse pull forward'' (!):

$$i^{\mbox{\scriptsize th}}$$ (45)

and drop the logs:

a = b^x. (46)

Now take the log base b:

$$\Omega$$ (47)

This simplifies to:

$$R = H_{before} - H_{after} = - \Delta H \;\;\;\;\;\mbox{(bits per operation)}$$ (48)

But we know what x is from equation (43):

$$S \equiv - k_{\mbox{\scriptsize B}}\sum_{i = 1}^\Omega P_i \l... ... {\mbox{${}^\circ \mbox{K}$ } \cdot \mbox{microstate}} \right)$$ (49)

The conversion rule to get logarithms base 2 from any base z is:

$$(1.38 \times 10^{-23}$$ (50)

Notice that since the z does not appear on the left hand side it doesn't matter what kind of logarithm you have available, because you can always get to another base using this equation! Try this example on your calculator:

$${}^\circ \mbox{K}$$ (51)

You should get `5'.

Tricks With Powers of 2. In calculus we learn about the natural logarithm with base $$\Delta S = S_{before} - S_{after}$$⁶ Calculations with this base can easily be done by a computer or calculator, but they are difficult for most people to do in their head.

In contrast, the powers of 2 are easy to memorize and remember:

choices	bits
M	B
1	0
2	1
4	2
8	3
16	4
32	5
64	6
128	7
256	8
512	9
1024	10

where 2^B = M and $$\Delta S = -k_{\mbox{\scriptsize B}}\ln(2) R .$$.

We can use this table and a trick to make quick estimates of the logs of higher numbers. Notice that

$$dS \geq \frac{dq}{T}$$ (52)

So to take the log base 2 of $$- T \Delta S \leq -q$$, we think:

$$\int dq = q k_{\mbox{\scriptsize B}}T \ln(2) \leq -q / R \;\;\;\;\; \mbox{(joules per bit)} .$$ = (53)

$$k_{\mbox{\scriptsize B}}T \ln(2)$$ = (54)

$${\cal E}\equiv -q / R$$ = (55)

$${\cal E}\geq k_{\mbox{\scriptsize B}}T \ln(2) \;\;\;\;\; \mbox{(joules per bit)} . k_{\mbox{\scriptsize B}}T$$ (56)

$${\cal E}\geq k_{\mbox{\scriptsize B}}T \ln(2) \;\;\;\;\; \mbox{(joules per bit)} .$$ 2 + 10 + 10 (57)

$${\cal E}\geq k_{\mbox{\scriptsize B}}T \ln(2) \;\;\;\;\; \mbox{(joules per bit)} .$$ 22 (58)

The actual value is 21.93.

            Viewing Files    Accessibility