Cryptography Reference
In-Depth Information
which means that there is more choice (uncertainty) when there exist more
equallylikelyoutcomes.
3. If the
j
th outcome is replaced bytwo successive outcomes, the first with
probability
cp
j
and the second with probability(1
−
c
)
p
j
, for 0
<c<
1,
S
then the entropyof
should be a weighted sum of the entropies of the
two choices. More precisely,
H
(
p
1
,...,cp
j
,
(1
−
c
)
p
j
,...,p
n
)=
H
(
p
1
,...,p
j
,...,p
n
)+
p
j
H
(
c,
1
−
c
)
.
This sas that the entropyis increased bythe uncertaintycaused bythe
choice between the two outcomes, multiplied by
p
j
.
Based on the above three properties, Shannon established the following def-
inition for entropy.
What Is Entropy?
Entropy, the measure of information (uncertainty), is formalized as follows.
Suppose that we have a set of messages
S
=
{
m
1
,m
2
,...,m
n
}
for some
n
∈
N
, and
p
j
for 1
≤
j
≤
n
is the probabilitythat message
m
j
is the message
sent, with
j
=1
p
j
= 1. Then
n
n
H
(
S
)=
H
(
p
1
,p
2
,...,p
n
)=
p
j
·
log
2
(1
/p
j
)=
−
p
j
·
log
2
(
p
j
)
(11.1)
j
=1
j
=1
denotes the entropyof
S
, which is independent of the set of messages since an-
m
1
,m
2
,...,m
n
}
other distinct set
with the same probabilitydistribution
has the same entropy.
11.2
Also, Equation (11.1) defines a mathematical value
called
the number of bits per message source
.
11.3
T
=
{
This definition captures the earlier notion since, for instance, if the outcome
is certain to be
m
1
, namely,
p
1
= 1 and
p
j
= 0 for all
j>
1, then
H
(
)=0,so
there is no information in a predictable outcome. In fact, this is the onlyway
that
H
(
S
S
) = 0 is possible, that is, if there is an
m
j
∈
S
such that
p
j
= 1 and
p
k
= 0 for all
m
k
∈
S
=
k
. Since the goal is to record minimal amounts
of bits on a computer to represent information, then there is no point in storing
information with zero content such as the above. When
H
(
with
j
)
>
0, then the
following illustrates the measure of certain minimal bits we have to employin
order to record output from
S
S
, namely, the average number, given by
H
(
S
).
11.2
Since there is an undefined quantity when
p
j
= 0, we agree by convention that 0log
2
0=0.
11.3
Shannon chose log
2
as a suitable measure of entropy to which he could ascribe the term
“bits”, which he says in [249], was a word suggested by J.W. Tukey. In that paper, he gave
three substantive reasons for the logarithmic measure: (1) It is practically more useful; (2) It
is nearer to our intuitive feeling as to the proper measure; and (3) It is mathematically more
suitable.
Search WWH ::
Custom Search