Cryptography Reference
In-Depth Information
|
f
(
m
)
|
. Now we define a
weighted length
of an encoding by
L
(
f
)=
s
p
(
s
)
|
f
(
s
)
|
.
(11.6)
∈
S
The goal is to find an encoding
f
that minimizes
L
(
f
).
Huffman Encoding Algorithm
Given a message source
S
=
{
with probabilitydistribution given by
p
j
for
j
=1
,
2
,...,n
,
we encode as follows.
1. The two elements
m
i
≤
m
1
,m
2
,...,m
n
}
m
j
with lowest probabilityare encoded, the lowest
with a 0 and the largest with a 1. In the event theyare equal,
m
i
is
encoded with a 0 and
m
j
with a 1.
2. The
m
i
and
m
j
from step 1 are treated as a single entity
m
i,j
, with proba-
bilityequal to the sum of their individual probabilities,
p
i,j
=
p
i
+
p
j
.
3. Step 1 and 2 are repeated until there is a single element remaining. Then
go to step 4.
4. The binaryoutput for each
s
j
∈
S
is obtained byreading backward through
the above procedure to
m
j
in the message source.
Example 11.6
Let
with
p
1
=0
.
1
,
p
2
=0
.
2
,
p
3
=0
.
3
,
p
4
=0
.
4
, we illustrate the above algorithm via the following table.
S
=
{
s
1
,s
2
,s
3
,s
4
}
s
1
s
2
s
3
s
4
0
.
1 0
.
2 0
.
3 0
.
4
0
1
0
.
3
0
.
3 0
.
4
0
1
0
.
6
0
.
4
1
0
1
.
0
The encoding is determined by reading backward through the procedure to
get
f
(
s
1
) = 100;
f
(
s
2
) = 101;
f
(
s
3
) = 11;
f
(
s
4
)=0
. Therefore,
L
(
f
)=
0
.
1
·
3+0
.
2
·
3+0
.
3
·
2+0
.
4
·
1=1
.
9
, and when we compare this with the entropy
of
S
, we get
H
(
S
)=0
.
1
·
log
2
(10)+0
.
2
·
log
2
(5)+0
.
3
·
log
2
(10
/
3)+0
.
4
·
log
2
(5
/
2)
≈
1
.
84644
.
Hence, the Huffman encoding is approximately equal to the entropy.
Example 11.6 is motivation for the following fact.
Huffman Encoding and Entropy
If
L
is given byEquation (11.6) and
the assumptions surrounding it, then
H
(
S
)
≤
L<H
(
S
)+1
.
(11.7)
Search WWH ::
Custom Search