\documentclass[12pt]{article}

%   Dr. Thomas D. Schneider
%   National Cancer Institute
%   Laboratory of Experimental and Computational Biology
%   Molecular Information Theory Group
%   Frederick, Maryland  21702-1201
%   toms@ncifcrf.gov
%   permanent email: toms@alum.mit.edu (use only if first address fails)
%   http://www.lecb.ncifcrf.gov/~toms/

% This is a LaTeX document.  See
% http://www.lecb.ncifcrf.gov/~toms/latex.html

\date{version = 2.58 of primer.tex 2005 Mar 15}
%  2005 Mar 15, 2.58: circles on the exponential and log graphs.
%  2005 Mar 15, 2.57: thanks to Paul C. Anagnostopoulos for many comments!
%  2005 Feb  8, 2.56: original mention nits, thanks to Huey P. Dugas
% 2003 Jan 6, 2.54: correction of faq pointer after first para, thanks
%                   to John Hoppner
% 2002 October 19, 2.53: mention nats, thanks to Shu-Kun Lin
% 2002 September 16, 2.52: previous changes
% 1999 Feb 8 try latex2html
% previous last change: 1996 September 19

% Sorry I won't be able to add your name to an acknowledgment list - it
% would be unfair to the many people who contributed whose email records
% are too buried to find anymore.  But I DO appreciate it much!
% These are the OLDEST records I have:
% 
% 1995 July 27 Amy Caplan (amyc@well.com)
%    log graph, log 1 = 0, log 0 = -infty
% 
% 1995 July 27 Maarten Keijzer (keijzer@phil.ruu.nl)
%    teletype example extended to Shannon's example
% 
% 2004 Sep 24: Frederick Tan, see email.

% These settings create a 1" margin around the edge of each page:
\textheight 9.0 in % this works
%\topmargin -0.5in % -0.5 would shift the whole thing up
%\headheight 0in
%\headsep 0in
\textwidth 6.5in
\oddsidemargin 0in

\usepackage{html}
\usepackage{graphics}
\usepackage{color}
\usepackage{pslatex} % Times New Roman Font

% \input{navigation}

% it appears to be impossible to make the latter part of the title
% small using constructions like this:
% \latex{\normalsize}
% \html{\small}
% latex2html ignores the command.
% further, latex2html also ignores the \normalsize

\title{
Information Theory Primer\\
\normalsize
With an
{Appendix} % HOLD THE HYPERREF FOR NOW
%\hyperref
%{ONE}
%{TWO}
%{THREE}
%{appendix}
%
% Previous version:
%\hyperref
%{Appendix}
%{Appendix (see section }
%{)}
%{appendix}
      % notes on how to use hyperref:
      %\hyperref
      %{hypertex}
      %{latex}
      %{}
      %{referencename}
on Logarithms \\
% {\normalsize \small is too small
\vspace{12pt}
Postscript version:
\htmladdnormallink
{ftp://ftp.ncifcrf.gov/pub/delila/primer.ps}
{ftp://ftp.ncifcrf.gov/pub/delila/primer.ps}
\\
web versions:
\htmladdnormallink
{http://www.lecb.ncifcrf.gov/$\sim$toms/paper/primer/}
{http://www.lecb.ncifcrf.gov/~toms/paper/primer/}
% }
}

% \title{
% Information Theory Primer\\
% \normalsize
% With an
% \hyperref
% {Appendix}
% {Appendix}
% {appendix}
% % This isn't helping anything:
% %{Appendix (see section }
% %{)}
% %{appendix}
%       %\hyperref
%       %{hypertex}
%       %{latex}
%       %{}
%       %{referencename}
% on Logarithms \\
% % {\normalsize \small is too small
% Postscript version:
% \htmladdnormallink
% {ftp://ftp.ncifcrf.gov/pub/delila/primer.ps}
% {ftp://ftp.ncifcrf.gov/pub/delila/primer.ps}
% \\
% web versions:
% \htmladdnormallink
% {http://www.lecb.ncifcrf.gov/$\sim$toms/paper/primer/}
% {http://www.lecb.ncifcrf.gov/~toms/paper/primer/}
% % }
% }

\author{
Thomas D. Schneider\thanks{National Cancer Institute,
        National Cancer Institute,
        Laboratory of Experimental and Computational Biology,
        P. O. Box B,
        Building 144, Room 469,
        Frederick, MD 21702.
        email address:
        \latex{toms@ncifcrf.gov.}
        \html{
          {
            \htmladdnormallink
            {toms@ncifcrf.gov}
            {mailto:toms@ncifcrf.gov}
          }
        }
        \latex{http://www.lecb.ncifcrf.gov/$\sim$toms/}
        \html{
          {   
            \htmladdnormallink
            {http://www.lecb.ncifcrf.gov/$\sim$toms/}
            {http://www.lecb.ncifcrf.gov/~toms/}
          }
        }
This text originated as chapter II of my PhD thesis:
``The Information Content of Binding Sites on
Nucleotide Sequences'', University of Colorado, 1984.
As a U. S. government work, this document cannot be copyrighted.}
}

\bodytext{
<body
bgcolor="#ffffff"
text="#000000"
link="#0000ff"
alink="#00ff00"
vlink="#888888"
>
}

\newcommand{\eq}[1]{(\ref{#1})} % equation numbers are within parenthesis
\newcommand{\fig}[1]{Fig.~\ref{#1}} % figure referencing mechanism
\newcommand{\degrees}{${}^{\circ}$}

\begin{document}

% latexonly only works in the simplest possible form.
%\hbadness 4500 % avoids silly messages about underfull boxes
% \latex{\hbadness 4500}

\begin{rawhtml}
<font size=+2>
\end{rawhtml}

\pagestyle{myheadings}
\markright{Tom Schneider's Information Theory Primer}
\bibliographystyle{unsrt}
\maketitle

\vspace{-12pt}

This primer is written for molecular
biologists who are unfamiliar with information theory.
Its purpose is to introduce you to these ideas so that
you can understand how to apply them
to binding sites
\cite{Schneider1986,Schneider1988,Schneider1989,Schneider.Stephens1990,
Herman.Schneider1992,Papp.helixrepa,Stephens.Schneider.Splice,
Schneider.nano2,Rogan.Schneider.hmsh2.1995}.
Most of the material in this primer can also be found in introductory
texts on information theory.
Although
Shannon's original paper on the theory of information \cite{Shannon1948}
is sometimes difficult to read, at other points
it is straight forward.  Skip the hard parts, and you
will find it enjoyable.
Pierce later published a popular book \cite{Pierce1980}
which is a great introduction to information theory.
Other introductions are listed in reference \cite{Schneider1986}.
A workbook that you may find useful is reference \cite{Sacco1988}.
Shannon's complete collected works have been published \cite{Sloane.Wyner1993}.
Information about ordering this book is given in

\begin{quote}
\htmladdnormallink
{http://www.lecb.ncifcrf.gov/$\sim$toms/bionet.info-theory.faq.html
\\
\#REFERENCES-Information\_Theory}
{http://www.lecb.ncifcrf.gov/~toms/bionet.info-theory.faq.html#REFERENCES-Information\_Theory}
\end{quote}

\noindent
Other papers and documentation on programs can be found at

\begin{quote}
\htmladdnormallink
{http://www.lecb.ncifcrf.gov/$\sim$toms/}
{http://www.lecb.ncifcrf.gov/~toms/}
\end{quote}

% \vspace{12pt}
Note:  If you have trouble getting through one or more steps in this primer,
please send email to me describing the exact place(s) that you had the
problem.  If it is appropriate, I will modify the text to smooth the path.  My
thanks go to the many people whose stubbed toes led to this version.

\newpage % This is needed to get the header to the next page.
\vspace{12pt}
{\bf Information and Uncertainty}

Information and uncertainty are technical terms that describe
any process that selects one or more objects from a set of objects.
We won't be dealing with the meaning or implications
of the information since nobody knows how to do that mathematically.
Suppose we have a device that can produce 3 symbols, A, B, or C.
As we wait for the next symbol, we are {\em uncertain}
as to which symbol it will produce.
Once a symbol appears and we see it,
our uncertainty {\em decreases}, and we remark that we have
received some {\em information}.  That is, information is a
decrease in uncertainty.
How should uncertainty be measured?
The simplest way would be to say that we have an
``uncertainty of 3 symbols''.  This would work well until
we begin to watch a second device at the same time, which,
let us imagine, produces symbols 1 and 2.
The second device gives us an ``uncertainty of 2 symbols''.
If we combine the devices into one device,
there are six possibilities,
A1, A2, B1, B2, C1, C2.
This device has an ``uncertainty of 6 symbols''.
This is not the way we usually think about information, for if we
receive two books, we would prefer to say that we received
twice as much information than from one book.
That is, we would like our measure to be additive.

\vspace{12pt}
It's easy to do this if we first take the logarithm of
the number of possible symbols
because then we can add the logarithms instead of multiplying the number
of symbols.
In our example, the first device makes us uncertain by $\log(3)$,
the second by $\log(2)$ and the combined device by $\log(3)+\log(2)=\log(6)$.
The base of the logarithm determines the units.
When we use the base 2 the units are in bits
(base 10 gives digits and the base of the natural logarithms, $e$,
gives nats \cite{Cover.Thomas1991} or
% nits, though I don't have a reference for the latter).
nits \cite{MacDonald1952}).
Thus if a device produces one symbol,
we are uncertain by $\log_2 1 = 0$ bits, and we have no uncertainty about
what the device will do next.
If it produces two symbols our uncertainty would be
$\log_2 2 = 1$ bit.
In reading an mRNA, if the ribosome encounters any one of 4
equally likely bases,
then the uncertainty is 2 bits.

\vspace{12pt}
So far, our formula for uncertainty is $\log_2 ( M )$, with $M$ being the
number of symbols.  The next step is to extend the formula
so it can handle cases where the symbols are not equally likely.
For example, if there are 3 possible symbols, but one of them never
appears, then our uncertainty is 1 bit.  If the third symbol appears
rarely relative to the other two symbols,
then our uncertainty should be larger
than 1 bit, but not as high as $\log_2(3)$ bits.
Let's begin by rearranging the formula like this:
\begin{eqnarray}
\log_2 ( M ) & = & - \log_2 ( M^{-1} ) \\
             & = & - \log_2 ( \frac{1}{M} ) \nonumber \\
             & = & - \log_2 ( P ) \nonumber
\end{eqnarray}
so that $P = 1/M$ is the probability that any symbol appears.
(If you don't remember this trick of `pulling the sign out', recall
that $\log M^b = b \log M$ and let $b = -1$.)

\vspace{12pt}
Now let's generalize this
for various probabilities of the symbols, $P_i$, so that
the probabilities sum to 1:
\begin{equation}
\sum_{i = 1}^M P_i = 1 .
\end{equation}
(Recall that the $\sum$ symbol means to add the $P_i$ together, for
$i$ starting at $1$ and ending at $M$.)
The surprise that
we get when we see the i${}^{th}$ kind of symbol
was called the ``surprisal'' by Tribus \cite{Tribus1961}
and is defined by analogy with $- \log_2 P$ to be%:
\footnote{ % new as of 2005 Mar 15
Why use `$u$' as the symbol for surprisal?
$S$ is the standard symbol
for entropy and that is not easily distinguished from $s$,
so the `$u$' stands for uncertainty \ldots
we are running out of symbols in molecular information theory!}
\begin{equation}
u_i = - \log_2 ( P_i ) .
\end{equation}
For example, if $P_i$ approaches 0, then we will be
{\em very surprised\/} to see the i${}^{th}$ symbol (since
it should almost never appear), and the formula
says $u_i$ approaches $\infty$.  On the other hand, if $P_i$=1,
then we won't be surprised at all
to see the i${}^{th}$ symbol
(because it should always appear) and $u_i$ = 0.

\vspace{12pt}
Uncertainty is the {\em average surprisal\/} for the infinite
string of symbols produced by our device.
For the moment, let's find the average for a string
% of only % deleted 2004 Sep 24
of length $N$ % fixed 2005 Mar 15
that has an alphabet of $M$ symbols. % fixed 2005 Mar 15
Suppose that the i${}^{th}$ type
of % NEW 2004 Sep 24
symbol appears $N_i$ times
so that
\begin{equation}
N = \sum_{i = 1}^M N_i .
\end{equation}
There will be $N_i$ cases where we have surprisal $u_i$.
The average surprisal for the N symbols is:
\begin{equation}
\frac
     {\sum_{i = 1}^M N_i u_i}
     {\sum_{i = 1}^M N_i} .
\end{equation}
By substituting $N$ for the denominator and bringing it inside the upper
sum, we obtain:
\begin{equation}
{\sum_{i = 1}^M {\frac{N_i}{N}} u_i}
\end{equation}
If we do this measure for an infinite string of symbols, then
the frequency $N_i / N$ becomes
$P_i$, the probability of the i${}^{th}$ symbol.
Making this substitution, we see that our
average surprisal (H) would be:%
\footnote{
The name $H$ comes through Shannon
from Boltzmann's $H$-Theorem in thermodynamics.
I don't know why this symbol was chosen
by Boltzmann.
}
\begin{equation}
H =  \sum_{i = 1}^M P_i u_i .
\end{equation}

\vspace{12pt}
Finally, by substituting for $u_i$, we get
Shannon's famous general formula for uncertainty:

% this works to change the size of the box:
%$ \rule[-0.5cm]{0cm}{1cm}
% The command \displaystyle forces the formula to have the stuff over
% and under the sums

\begin{equation}
\framebox{$\displaystyle
H = - \sum_{i = 1}^M P_i \log_2 P_i
\;\;\;\;\;\mbox{(bits per symbol).}
$}
\label{def.famous}
\end{equation}

\vspace{12pt}
Shannon got to this formula by a much more rigorous route
than we did, by setting
down several desirable properties for uncertainty,
and then deriving the function.
Hopefully the route we just followed gives you a feeling for
how the formula works.

\newpage

To see how the H function looks, we can plot it for the case of
two symbols.
This is shown below\footnote{\raggedright The program to create this graph
is at
%ftp://ftp.ncifcrf.gov/pub/delila/hgraph.p}:
\htmladdnormallink
{http://www.lecb.ncifcrf.gov/$\sim$toms/delila/hgraph.html}
{http://www.lecb.ncifcrf.gov/$\sim$toms/delila/hgraph.html}}:

%%% figure %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[htb] % h here; t top; b bottom; p page of floats
% \vspace{10cm}
\htmlimage{transparent,thumbnail=1.0}
% the old way:
%\special{psfile="fig/hgraph.ps"
% hoffset=0 voffset=-130
% hscale=100 vscale=100
% angle=0}
\begin{center}
\rotatebox{0}{\scalebox{1.00}{\includegraphics*{fig/hgraph.eps}}}
\end{center}
%\caption{H function for 2 symbols.}
%\label{fig.hgraph}
\end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Notice that the curve is symmetrical, and rises to a maximum when the two
symbols are equally likely (probability = 0.5).
It falls towards zero whenever one of the symbols becomes dominant
at the expense of the other symbol.

\vspace{12pt}
As an instructive exercise, suppose that all the symbols are equally likely.
What does the formula for H (equation \eq{def.famous}) reduce to?
You may want to try this yourself before reading on.

\begin{center}
*********************************
\end{center}
\pagebreak

Equally likely means that $P_i = 1/M$, so if we substitute
this into the uncertainty equation we get:
\begin{equation}
H_{equiprobable} =  - \sum_{i = 1}^M \frac{1}{M} \log_2 \frac{1}{M}
\end{equation}
Since $M$ is not a function of $i$,
we can pull it out of the sum:
\begin{eqnarray}
H_{equiprobable} & = & - ( \frac{1}{M} \log_2 \frac{1}{M} )
   \sum_{i = 1}^M 1 \\
  & = & - \left( \frac{1}{M} \log_2 {\frac{1}{M}} \right) M \nonumber \\
  & = & - \log_2 \frac{1}{M} \\
  & = &   \log_2 M \nonumber
\end{eqnarray}
which is the simple equation we started with.
It can be shown that for a given number of symbols (ie., $M$ is fixed)
the uncertainty
$H$ has its largest value only when the symbols are equally probable.
For example, an unbiased coin is harder to guess than
a biased coin.
As another exercise, what is the uncertainty when there are
10 symbols and only one of them appears?
(clue: $\displaystyle \lim_{p \rightarrow 0} p \log p = 0$ by setting $p = 1/M$
and using l'H\^{o}pital's rule, so $0 \log_2  0 = 0$.)

\vspace{12pt}
What does it mean to say that a signal has 1.75 bits per symbol?
It means that we can convert the original signal into a string of
1's and 0's (binary digits),
so that {\em on the average\/} there are 1.75 binary digits for
every symbol in the original signal.
Some symbols will need more binary digits (the rare ones)
and others will need fewer (the common ones).
Here's an example.  Suppose we have $M = 4$ symbols:
\begin{equation}
  A
\;\;\;\;\;
  C
\;\;\;\;\;
  G
\;\;\;\;\;
  T
\end{equation}
with probabilities ($P_i$):
\begin{equation}
  P_A =  \frac{1}{2} ,
\;\;\;\;\;
  P_C =  \frac{1}{4} ,
\;\;\;\;\;
  P_G =  \frac{1}{8} ,
\;\;\;\;\;
  P_T =  \frac{1}{8} ,
\end{equation}
which have surprisals ($- \log_2 P_i$):
\begin{equation}
  u_A =  1  \mbox{ bit},
\;\;\;\;\;
  u_C =  2  \mbox{ bits},
\;\;\;\;\;
  u_G =  3  \mbox{ bits},
\;\;\;\;\;
  u_T =  3  \mbox{ bits},
\end{equation}
so the uncertainty is
\begin{equation}
H = 
\frac{1}{2} \cdot 1  + 
\frac{1}{4} \cdot 2  + 
\frac{1}{8} \cdot 3  + 
\frac{1}{8} \cdot 3  = 
1.75
\mbox{ (bits per symbol)} .
\end{equation}
Let's recode this so that the number
of binary digits equals the surprisal:
\begin{eqnarray}
  A & = & 1 \nonumber \\
  C & = & 01 \nonumber \\
  G & = & 000 \nonumber \\
  T & = & 001
\label{eqn.fanocode}
\end{eqnarray}
so the string
\begin{equation}
  ACATGAAC
\end{equation}
which has frequencies the same as the probabilities defined above,
is coded as
\begin{equation}
  10110010001101 .
\end{equation}
14 binary digits were used to code for 8 symbols, so the
average is 14/8 = 1.75 binary digits per symbol.
This is called a Fano code.
Fano codes have the property
that you can decode them without needing spaces between symbols.
Usually one needs to know the ``reading frame'', but in
this example one can figure it out.
In this particular coding (equations \eq{eqn.fanocode}),
the first binary digit distinguishes between
the set containing $A$, (which we symbolize as {$A$})
and the set {$C, G, T$}, which are equally likely.
The second digit, used if the first digit is $0$,
distinguishes {$C$} from {$G, T$}.
The final digit distinguishes {$G$} from {$T$}.
Because each choice is equally likely (in our original definition of the
probabilities of the symbols),
every binary digit in this code carries 1 bit of information.
{\em Beware!\/}
This won't always be true.
A binary digit can supply 1 bit {\em only\/}
if the two sets represented by the digit are equally likely
(as rigged for this example).
If they are not equally likely, one binary digit supplies
less than one bit.  (Recall that H is at a
maximum for equally likely probabilities.)
So if the probabilities were
\begin{equation}
  P_A =  \frac{1}{2},
\;\;\;\;\;
  P_C =  \frac{1}{6},
\;\;\;\;\;
  P_G =  \frac{1}{6},
\;\;\;\;\;
  P_T =  \frac{1}{6},
\label{eqn.irrational.example}
\end{equation}
there is no way to assign a (finite) code so that
each binary digit has the value of one bit
(by using larger blocks of symbols, one can approach it).%
% 2004 Sep 24:
\footnote{This is because the fractions in equations
\eq{eqn.irrational.example}
evaluate to irrational numbers when the logarithm is base 2,
and since a Fano code divides by rational numbers, no binary Fano
code can be made that exactly matches.}
%
In the rigged example, there is no way to use fewer
than 1.75 binary digits per symbol,
but we could be wasteful and use extra
digits to represent the signal.
The Fano code does reasonably well
by splitting the symbols into successive
groups that are equally likely to occur; you can read more about it
in texts on information theory.
The uncertainty measure tells us what could be done ideally, and
so tells us what is impossible.  For example, the signal with 1.75 bits
per symbol could not be coded using only 1 binary digit per symbol.

\vspace{12pt}
{\bf Tying the Ideas Together}

In the beginning of this primer we took information to be a decrease
in uncertainty.
Now that we have a general formula for uncertainty,
\eq{def.famous}, we can express information using this formula.
Suppose that a computer contains some information in its memory.
If we were to look at individual flip-flops, we would have an uncertainty
$H_{before}$ bits per flip-flop.
Suppose we now clear part of
the computer's memory (by setting the values there to zero),
so that there is a new uncertainty, smaller
than the previous one: $H_{after}$.  Then the computer memory has lost
an average of%
\footnote{
The symbol $R$ comes from Shannon.
It stands for rate of information transmission.
}
%
\begin{equation}
R =  H_{before} - H_{after}
\label{def.decrease}
\end{equation}
%
bits of information per flip-flop.
If the computer was completely cleared, then $H_{after} = 0$ and
$R = H_{before}$.

\vspace{12pt}
Now consider a teletype receiving characters over a phone line.
If there were no noise in the phone line and no other source
of errors, the teletype would print the text perfectly.
With noise, there is some uncertainty about whether a character printed
is really the right one.  So before a character is printed, the
teletype must be prepared for any of the letters, and this prepared state
has uncertainty $H_{before}$,
while after each character has been received there is still some uncertainty,
$H_{after}$.
This uncertainty
is based on the probability that the symbol that came through 
is not equal to the symbol that was sent, and it measures the
amount of noise.

\vspace{12pt}
Shannon gave an example of this in section 12 of \cite{Shannon1948}
(pages 33-34 of \cite{Sloane.Wyner1993}).
A system with two equally likely symbols transmitting every second
would send at a rate of 1 bit per second without errors.
Suppose that the probability that a 0 is received when a 0 is sent is
0.99 and the probability of a 1 received is 0.01.
``These figures are reversed if a 1 is received.''
Then the uncertainty after receiving a symbol is
$H_{after} = 
- 0.99 \log_2 0.99
- 0.01 \log_2 0.01
= 0.081$,
so that the actual rate of transmission is
$R = 1 - 0.081 = 0.919$ bits per second.\footnote{Shannon used the notation $H_y(x)$,
meaning the conditional uncertainty at the receiver $y$ given
the message sent from $x$, for what we call
$H_{after}$.  He also used the term ``equivocation''.}
The amount of
information that gets through is given by the decrease
in uncertainty, equation \eq{def.decrease}.

\vspace{12pt}
Unfortunately
many people have made errors because they did not keep this point clear.
The errors occur because people implicitly
assume that there is no noise in the communication.
When there is no noise,
$R = H_{before}$, as with the completely cleared computer memory.
That is {\em if there is no noise, the amount of information communicated is
equal to the uncertainty before communication.}
When there is noise and someone assumes that there isn't any,
this leads to all kinds of confusing philosophies.
One must always account for noise.

\vspace{12pt}
{\bf One Final Subtle Point.}
In the previous section
you may have found it odd that I used the word ``flip-flop''.
This is because I was intentionally avoiding the use of the
word ``bit''.  The reason is that there are two meanings to this word,
as we mentioned before while discussing Fano coding,
and it is best to keep them distinct.
Here are the two meanings for the word ``bit'':
\begin{enumerate}
\item
A binary digit, 0 or 1.  This can only be an integer.
These `bits' are the individual pieces of data in computers.
\item
A {\em measure\/} of uncertainty, $H$, or information $R$.
This can be any real number because it is an average.
It's the measure that Shannon used to discuss communication systems.
\end{enumerate}

\newpage
\bibliography{primer}

\newpage

%\section{Appendiecseafiower}
\begin{center}
\section{
{\Large \bf APPENDIX: A Tutorial On Logarithms}
\label{appendix}
}
\end{center}

\begin{rawhtml}
<font size=+2>
\end{rawhtml}

\vspace{12pt}
\noindent
{\large \bf Understanding the Log Function.}
In the mathematical operation of addition we take two numbers
and join them to create a third:
\begin{equation}
1 + 1 = 2.
\end{equation}
We can repeat this operation:
\begin{equation}
1 + 1 + 1 = 3.
\end{equation}
Multiplication is the mathematical operation that extends this:
\begin{equation}
3 \times 1 = 3.
\end{equation}
In the same way, we can repeat multiplication:
\begin{equation}
2 \times 2 = 4.
\end{equation}
and
\begin{equation}
2 \times 2 \times 2 = 8.
\end{equation}
The extension of multiplication is exponentiation:
\begin{equation}
2 \times 2 = 2^2 = 4.
\end{equation}
and
\begin{equation}
2 \times 2 \times 2 = 2^3 = 8.
\end{equation}
This is read ``two raised to the third is eight''.
Because exponentiation simply counts the number of multiplications,
the exponents add:
\begin{equation}
2^2 \times 2^3 = 2^{2+3} = 2^5.
\label{eq.sum2.3.5}
\end{equation}
The number `2' is called the base of the exponentiation.
If we raise an exponent to another exponent, the values multiply:
\begin{equation}
\left( 2^2 \right) ^3 =
2^2 \times 2^2 \times 2^2 =
2^{2 + 2 + 2} =
2^{2 \times 3} =
2^6.
\label{eq.exponent.exponent}
\end{equation}

\newpage
The exponential function $y = 2^x$ is shown in this
graph\footnote{The program to create this graph
is at
\htmladdnormallink
{http://www.lecb.ncifcrf.gov/$\sim$toms/delila/expgraph.html}
{http://www.lecb.ncifcrf.gov/$\sim$toms/delila/expgraph.html}
}:

%%% figure %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[htb] % h here; t top; b bottom; p page of floats
%\vspace{12cm}
%\htmlimage{transparent,thumbnail=2.0}
%\special{psfile="fig/expgraph.ps"
 %hoffset=0 voffset=0
 %hscale=60 vscale=60
 %angle=0}
\begin{center}
\rotatebox{0}{\scalebox{0.60}{\includegraphics*{fig/expgraph.eps}}}
\end{center}
\vspace{-24pt}
\caption{The exponential function.}
\label{fig.expgraph}
\end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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:
\begin{equation}
2^B = 32.
\end{equation}
Of course, $2^5 = 32$,
so $B = 5$.
To be able to get a hold of this,
mathematicians made up a new function called the logarithm:
\begin{equation}
\log_{2}32 = 5.
\end{equation}
We pronounce this as ``the logarithm to the base 2 of 32 is 5''.
It is the ``inverse function'' for exponentiation:
\begin{equation}
2^{\log_{2}a} = a
\label{eqn.2log2aa}
\end{equation}
and
\begin{equation}
\log_2(2^a) = a.
\label{eqn.log22aa}
\end{equation}

\newpage
The logarithmic function $y = \log_2 x$ is shown in this
graph\footnote{The program to create this graph
\htmladdnormallink
{http://www.lecb.ncifcrf.gov/$\sim$toms/delila/expgraph.html}
{http://www.lecb.ncifcrf.gov/$\sim$toms/delila/expgraph.html}
}:
%is at ftp://ftp.ncifcrf.gov/pub/delila/expgraph.p}:

%%% figure %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[htb] % h here; t top; b bottom; p page of floats
%\vspace{10.5cm}
%\htmlimage{transparent,thumbnail=2.0}
%\special{psfile="fig/loggraph.ps"
% hoffset=0 voffset=0
% hscale=60 vscale=60
% angle=0}
\begin{center}
\rotatebox{0}{\scalebox{0.60}{\includegraphics*{fig/loggraph.eps}}}
\end{center}
\vspace{-24pt}
\caption{The logarithmic function.}
\label{fig.loggraph}
\end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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\degrees\ line.
Notice in particular that
$\log_2(1)=0$
and
$\log_2(0)=-\infty$.

\vspace{12pt}
\noindent
{\large \bf The Addition Law.}
Consider this equation:
\begin{equation}
\fbox{
$2^{a + b} = 2^a \times 2^b$
}
\end{equation}
which is just a generalization of equation \eq{eq.sum2.3.5}.
Take the logarithm of both sides:
\begin{equation}
\log_2{2^{a + b}} = \log_2 \left( {2^a \times 2^b} \right)
\end{equation}
Exponentiation and the logarithm are inverse operations, so
we can collapse the left side:
\begin{equation}
a + b = \log_2 \left( {2^a \times 2^b} \right)
\end{equation}
Now let's be tricky and substitute:
$\log_2 x = a$
and
$\log_2 y = b$:
\begin{equation}
\log_2 x + \log_2 y = \log_2 \left( {2^{\log_2 x} \times 2^{\log_2 y}} \right)
\end{equation}
Again, exponentiation and the logarithm are inverse operations, so
we can collapse the two cases on the right side:
\begin{equation}
\fbox{
$\log_2 x + \log_2 y = \log_2 \left( x \times y \right)$
}
\end{equation}
This is the additive property that Shannon was interested in.

\vspace{12pt}
\noindent
{\large \bf The `Pull Forward' Rule.}
From equation \eq{eqn.2log2aa}:
\begin{equation}
a = 2^{\log_{2}a}.
\end{equation}
Raise both sides to the $u$:
\begin{equation}
a^u = \left(2^{\log_{2}a}\right)^u.
\end{equation}
Now,
we can combine the exponents by multiplying, as in
\eq{eq.exponent.exponent}:
\begin{equation}
a^u = 2^{u\log_{2}a}.
\end{equation}
Finally, take the log base 2 of both sides and collapse the right side:
\begin{equation}
\fbox{
$\log_2 a^u = u\log_{2}a$
}
\end{equation}
This can be remembered as a rule that allows one to ``pull'' the 
exponent forward from inside the logarithm.

\vspace{12pt}
\noindent
{\large \bf 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:
\begin{equation}
x = \log_{z} a / \log_{z} b
\label{eqn.x-convert}
\end{equation}
Rearrange it as:
\begin{equation}
\log_{z} a = x \log_{z} b.
\end{equation}
Now use a ``reverse pull forward'' (!):
\begin{equation}
\log_{z} a = \log_{z} b^x
\end{equation}
and drop the logs:
\begin{equation}
a = b^x.
\end{equation}
Now take the log base $b$:
\begin{equation}
\log_b a = \log_b b^x.
\end{equation}
This simplifies to:
\begin{equation}
\log_b a = x.
\end{equation}
But we know what $x$ is from equation \eq{eqn.x-convert}:
\begin{equation}
\log_b a = \log_{z} a / \log_{z} b
\end{equation}
The conversion rule to get logarithms base 2
from any base z is:
\begin{equation}
\fbox{
$\log_2(a) = \log_z(a)/\log_z(2)$
}
\end{equation}
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:
\begin{equation}
\log_2(32) =
\frac{\log_{ \mbox{\scriptsize whatever!} }(32)}
     {\log_{ \mbox{\scriptsize whatever!} }(2)}.
\end{equation}
You should get `5'.

\vspace{12pt}
\noindent
{\large \bf Tricks With Powers of 2.}
In calculus we learn about the natural logarithm
with base $e = 2.718281828459045 \ldots$\footnote{
Want to impress your friends by memorizing this number?
Note that after the 2.7 (you are on your own for that!)
we have two 1828's followed by a 45\degrees-90\degrees-45\degrees triangle.}
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: \\
\begin{center}
\begin{tabular}{rr}
choices & bits \\
M & B \\ \hline
1 & 0 \\
2 & 1 \\
4 & 2 \\
8 & 3 \\
16 & 4 \\
32 & 5 \\
64 & 6 \\
128 & 7 \\
256 & 8 \\
512 & 9 \\
1024 & 10
\end{tabular} \\
\end{center}
where $2^B = M$ and $\log_2 M = B$.

We can use this table and a trick to make quick estimates
of the logs of higher numbers.  Notice that
\begin{equation}
2^{10} = 1024 \approx 1000 = 10^3.
\end{equation}
So to take the log base 2 of $4 \times 10^6$, we think:
\begin{eqnarray}
\log_2 (4 \times 10^6) & = & \log_2(4) + \log_2(10^6) \\
                       & = & 2 + \log_2(10^3 \times 10^3) \\
                       & = & 2 + \log_2(10^3) + \log_2(10^3) \\
                 & \approx & 2 + \log_2(2^{10}) + \log_2(2^{10}) \\
                 & \approx & 2 + 10 + 10 \\
                 & \approx & 22
\end{eqnarray}
The actual value is 21.93.

\end{document}
