Digital Signal Processing Reference
In-Depth Information
The less predictable a set of digital data is, the more infor-
mation it carries. Here is a simple example: assume that a bit can
be equally likely to be either zero or one. By definition, this will be
one bit of data information. Now assume that this bit is known to
be one with 100% certainty. This will carry no information,
because the outcome is predetermined. This relationship can be
generalized by:
Info of outcome
¼
log
2
(1 / probability of outcome)
¼
log
2
(probability of outcome)
Let's look at another example. If there is a four outcome event,
with equal probability of outcome
1
, outcome
2
, outcome
3
,or
outcome
4
:
Outcome 1: Probability
¼
0.25, encode as 00.
Outcome 2: Probability
¼
0.25, encode as 01.
Outcome 3: Probability
¼
0.25, encode as 10.
0.25, encode as 11.
The entropy can be defined as the sum of the probabilities of
each outcome multiplied by the information conveyed by that
outcome.
Entropy
Outcome 4: Probability
¼
¼
prob (outcome
1
)
info (outcome
1
)
þ
prob (outcome
2
)
info (outcome
2
)
þ
.
prob (outcome
n
)
info (outcome
n
)
For our simple example:
Entropy
¼
0.25
log
2
(1 / 0.25)
þ
0.25
log
2
(1 / 0.25)
þ
0.25
log
2
(1 / 0.25)
þ
0.25
log
2
(1 / 0.25)
¼
2 bits
two bits is normally what would be used to
convey one of four possible outcomes.
In general, the entropy is the highest when the outcomes
are equally probable, and therefore totally random. When this
is not the case, and the outcomes are not random, the
entropyislower,anditmaybepossibletotakeadvantageof
this and reduce the number of bits to represent the data
sequence.
If the probabilities are not equal, for example:
Outcome 1: Probability
This is intuitive
e
¼
0.5, encode as 00.
Outcome 2: Probability
¼
0.25, encode as 01.
Outcome 3: Probability
¼
0.125, encode as 10.
Outcome 4: Probability
¼
0.125, encode as 11.
Entropy
¼
0.5
log
2
(1 / 0.5)
þ
0.25
log
2
(1 / 0.25)
þ
0.125
log
2
(1 / 0.125)
þ
0.125
log
2
(1 / 0.125)
¼
1.75 bits
