Cryptography Reference
In-Depth Information
•
Second, we define the function
H
n
for
n
probability values
p
1
,...,p
n
.
The value
H
n
([
p
1
,...,p
n
]) represents the average uncertainty associated with
the events (
X
=
x
i
) for
i
=1
,...,n
(or the average uncertainty removed by
revealing
X
, respectively). More specifically, we require that
∈
N
n
H
n
([
p
1
,...,p
n
]) =
p
i
h
(
p
i
)
.
i
=1
In this topic, we write
H
([
p
1
,...p
n
]) instead of
H
n
([
p
1
,...,p
n
]) most
of the time.
The function
h
is only used to introduce the function
H
. The function
H
is then used to measure the uncertainty of a probability distribution or a random
variable. In fact,
H
(
X
) is called the
entropy
of the random variable
X
,andit
measures the average uncertainty of an observer about the value taken on by
X
.
The entropy plays a central role in data compression. In fact, it can be shown that
an optimal data compression technique can compress the output of an information
source arbitrarily close to its entropy, but that error-free compression below this
value is not possible.
In the literature, the function
H
is usually introduced by first setting up
requirements (or axioms), and then showing that the only function satisfying these
requirements is
H
([
p
1
,...,p
n
]) =
−
C
p
i
log
p
i
i
:1
≤i≤n
;
p
i
>
0
where
C
is an arbitrary positive number, and the logarithm base is any number
greater than one. In this case, we have
h
(
p
i
)=log
1
p
i
=
−
log
p
i
and
h
(
p
i
) measures the unexpectedness of an event with probability
p
i
. The units
of
H
are usually called bits; thus the units are chosen so that there is one bit of
uncertainty associated with the toss of an unbiased coin. Unless otherwise specified,
we assume
C
=1and take logarithms to the base 2 for the rest of this topic.
At this point it is important to note that the average uncertainty of a random
variable
X
(i.e.,
H
(
X
)) does not depend on the values the random variable assumes,
