Measuring Information

• Claude Shannon's work involved measuring information flow.

• Why bother?

  • Measuring information allows you to analyze it, optimize it, charge for it.

• Information measurements earlier to Shannon included

  • Fourier on composing signals,

  • Nyquist on telegraph efficiency, and

  • Hartley on information content.

Information Content

• Given a message that contains

  • itl(n) randomly selected symbols drawn from

  • an alphabet of itl(s) symbols

  Hartley determined (in 1928) that the amount of information in the message is

  itl(H) = itl(n) log itl(s)

• Shannon adjusted this work to remove the random selection assumption.

What is Information?

• Information is anything that removes uncertainty.

  • There must be uncertainty.

  • The information must be unambiguously interpreted.

  • The information must reduce uncertainty.

• Remember sending one of itl(n).

  • A sequence of yes-no questions does the trick

Data Representation

• Information sources ultimately produce a time-varying signal itl(S)(itl(t)).

  • There can be additional parameters, as in itl(S)(itl(x), itl(y), itl(t)), which is a useful model of 2-d image transmission.

  • It's sometimes helpful to think of all parameters as a function of time: itl(S)(itl(x)(itl(t)), itl(y)(itl(t)), itl(t)).

• For binary transmission the range of itl(S)() has two elements.

Telegraph Efficiency

• Nyquist modeled a communication system (telegraphs) with

  • a signal itl(S)(itl(t)) = sum(itl(i) = 1..itl(n), itl(s)_itl(i)(itl(t))) as a linear combination of periodic signals.

  • itl(m) is the number of symbols itl(S)(itl(t)) can assume.

  • itl(F) is the frequency of the highest frequency component itl(s)_itl(i)(itl(t)) of itl(S)(itl(t)).

• C = 2itl(F) log₂ itl(m) is information-flow rate across a noiseless channel.

  • The two is related to the Nyquist Sampling Rate.

Information and Predictability

• A totally predictable source does not provide information.

  • A predictable source tells you nothing.

• Think of a fair coin being tossed.

  • Each flip tells you something new: heads or tails.

• A stopped clock, an always-unfair coin is predictable.

• One way to quantify information is to relate it its predictability.

Entropy

• Shannon defined the entropy of an information source.

• Information entropy indicates how unpredictable an information source is.

  • This is not the same use of "entropy" as used in physics or mechanics.

Entropy Definition

• Given

  • an alphabet { itl(x)₁, itl(x)₂, ..., itl(x)_itl(n) } messages and

  • a probability itl(p)_itl(i) that itl(x)_itl(i) will be used in a message, then

  the entropy itl(H) of the information source is

  itl(H) = -sum(itl(i) = 1..itl(n), itl(p)_itl(i) log₂ itl(p)_itl(i))

  • If itl(p)_itl(i) = 0, then let itl(p)_itl(i) log₂ itl(p)_itl(i) = 0.

Interpreting Entropy

• What does -sum(itl(i) = 1..itl(n), itl(p)_itl(i) log₂ itl(p)_itl(i)) mean?

  • It has no units.

• 0 <= itl(p)_itl(i) <= 1, so itl(p)_itl(i) log₂ itl(p)_itl(i) is non-positive

  • The initial minus and sum gives a non-negative value.

• 0 log₂ 0 = 0 by definition; 1 log₂ 1 = 1(0) = 0.

  • In general, 2^-itl(n) log₂ 2^-itl(n) = -n/2^itl(n).

  • In particular, 0.5 log 0.5 = 0.5(-1) = -0.5.

An Entropy Example

• An information source sends itl(H) for heads and itl(T) for tails with a probability of itl(p)_itl(H) and itl(p)_itl(T) respectively.

• Find the source's entropy when:

  • itl(p)_itl(H) = itl(p)_itl(T) = 0.5 (a fair coin).

  • itl(p)_itl(H) = 1, itl(p)_itl(T) = 0 (a sure thing).

  • itl(p)_itl(H) = 0.75, itl(p)_itl(T) = 1 - itl(p)_itl(H) (an unfair coin).

• Remember that

  • itl(H) = -sum(itl(i) = 1..itl(n), itl(p)_itl(i) log₂ itl(p)_itl(i))

  • itl(p)_itl(i) log₂ itl(p)_itl(i) = 0 when itl(p)_itl(i) = 0.

Doing the Math

• Substituting into the entropy definition gives

  itl(H) = -itl(p)_itl(H) log₂ itl(p)_itl(H) - itl(p)_itl(T) log₂ itl(p)_itl(T)

• The information content of a fair coin is

  itl(H)	=	-0.5 log2 0.5 - 0.5 log2 0.5
  	=	-0.5(-1) - 0.5(-1)
  	=	1

• The other cases are similar

Noiseless Channel Capacity

• Given

  • a source with entropy itl(H) bits per symbol,

  • a noiseless channel with capacity itl(C) bits per second, and

  • an arbitrarily small value itl(e), then

  it is possible to send information at a rate of itl(C)/itl(H) - itl(e) but no faster.

• As itl(e) goes to zero, this implies that a noiseless channel can transmit at a maximum rate of itl(C)/itl(H).

Example

• The letter frequency in the 45,406 most common Engilsh words is

  e 0.117 i 0.086 s 0.081 a 0.079 r 0.074

  n 0.074 t 0.067 o 0.059 l 0.053 c 0.041

  d 0.038 u 0.032 g 0.028 p 0.027 m 0.027

  h 0.021 b 0.020 y 0.016 f 0.013 v 0.010

  k 0.008 w 0.008 z 0.004 x 0.002 j 0.002

  q 0.001

• The entropy of a source with these letter frequencies is 4.15 bits per character.

• log₂ 26 = 4.7 bits per character.

• What does the difference between 4.15 and 4.7 mean?

This page last modified on 14 i2m(11) 2004.