Dane jest źródło
S
=
{
x
1
,
x
2
,
…
}
{\displaystyle S=\{x_{1},x_{2},\dots \}}
p
=
{
p
1
,
p
2
,
…
}
.
{\displaystyle p=\{p_{1},p_{2},\dots \}.}
Prawdopodobieństwa (a wraz z nimi symbole) są sortowane w porządku nierosnącym, tj.
p
i
⩾
p
i
+
1
.
{\displaystyle p_{i}\geqslant p_{i+1}.}
Następnie dla tak uporządkowanych danych oblicza się niepełne prawdopodobieństwo kumulatywne:
P
(
x
i
)
=
p
1
+
p
2
+
…
+
p
i
−
1
{\displaystyle P(x_{i})=p_{1}+p_{2}+\ldots +p_{i-1}}
Kodowanie Shannona polega na wzięciu
⌈
−
log
2
p
i
⌉
{\displaystyle \lceil -\log _{2}{p_{i}}\rceil }
długość Shannona ) pierwszych bitów binarnego rozwinięcia liczby
P
i
{\displaystyle P_{i}}
po przecinku ). Średnia długość kodów mieści się w przedziale
[
H
(
S
)
,
H
(
S
)
+
1
)
,
{\displaystyle [H(S),H(S)+1),}
H
(
S
)
{\displaystyle H(S)}
entropia źródła (średnia liczba bitów na symbol).
Niech
S
=
{
a
,
b
,
c
,
d
}
,
{\displaystyle S=\{a,b,c,d\},}
p
=
{
0
,
45
;
0
,
3
;
0
,
2
;
0
,
05
}
{\displaystyle p=\{0{,}45;0{,}3;0{,}2;0{,}05\}}
H
(
S
)
=
1
,
72
{\displaystyle H(S)=1{,}72}
Długości Shannona (długości kodów w bitach):
l
a
=
⌈
−
log
2
0
,
45
⌉
=
2
{\displaystyle l_{a}=\lceil -\log _{2}{0{,}45}\rceil =2}
l
b
=
⌈
−
log
2
0
,
30
⌉
=
2
{\displaystyle l_{b}=\lceil -\log _{2}{0{,}30}\rceil =2}
l
c
=
⌈
−
log
2
0
,
20
⌉
=
3
{\displaystyle l_{c}=\lceil -\log _{2}{0{,}20}\rceil =3}
l
d
=
⌈
−
log
2
0
,
05
⌉
=
5
{\displaystyle l_{d}=\lceil -\log _{2}{0{,}05}\rceil =5}
Prawdopodobieństwa kumulatywne:
P
1
(
a
)
=
0
{\displaystyle P_{1(a)}=0}
P
2
(
b
)
=
p
1
=
0
,
45
{\displaystyle P_{2(b)}=p_{1}=0{,}45}
P
3
(
c
)
=
p
1
+
p
2
=
0
,
45
+
0
,
3
=
0
,
75
{\displaystyle P_{3(c)}=p_{1}+p_{2}=0{,}45+0{,}3=0{,}75}
P
4
(
d
)
=
p
1
+
p
2
+
p
3
=
0
,
45
+
0
,
3
+
0
,
2
=
0
,
95
{\displaystyle P_{4(d)}=p_{1}+p_{2}+p_{3}=0{,}45+0{,}3+0{,}2=0{,}95}
I ich rozwinięcia binarne (wzięte 5 pierwszych bitów po przecinku, zaznaczono słowa kodowe):
P
1
(
a
)
=
0
,
00
000
2
{\displaystyle P_{1(a)}=0{,}{\color {blue}00}000_{2}}
P
2
(
b
)
=
0
,
01
110
2
{\displaystyle P_{2(b)}=0{,}{\color {blue}01}110_{2}}
P
3
(
c
)
=
0
,
110
00
2
{\displaystyle P_{3(c)}=0{,}{\color {blue}110}00_{2}}
P
4
(
d
)
=
0
,
11110
2
{\displaystyle P_{4(d)}=0{,}{\color {blue}11110}_{2}}
Ostatecznie kody mają postać:
k
o
d
(
a
)
=
00
2
{\displaystyle kod(a)=00_{2}}
k
o
d
(
b
)
=
01
2
{\displaystyle kod(b)=01_{2}}
k
o
d
(
c
)
=
110
2
{\displaystyle kod(c)=110_{2}}
k
o
d
(
d
)
=
11110
2
{\displaystyle kod(d)=11110_{2}}
Średnia długość kodu
L
k
=
2
⋅
0
,
45
+
2
⋅
0
,
3
+
3
⋅
0
,
2
+
5
⋅
0
,
05
=
2
,
35
{\displaystyle L_{k}=2\cdot 0{,}45+2\cdot 0{,}3+3\cdot 0{,}2+5\cdot 0{,}05=2{,}35}
(
k
=
1
)
.
{\displaystyle (k=1).}
1
,
72
⩽
2
,
35
<
1
,
72
+
1
{\displaystyle 1{,}72\leqslant 2{,}35<1{,}72+1}
Jednak, jak wspomniano, efektywność kodowania Shannona nie jest duża – dla danych z powyższego przykładu wynosi
H
(
S
)
L
k
⋅
100
%
=
73
,
2
%
.
{\displaystyle {\frac {H(S)}{L_{k}}}\cdot 100\%=73{,}2\%.}
