Первичный алфавит состоит из букв А и В. Построить код по методу Хаффмана для передачи сообщений, если кодировать по одной, две, три буквы в блоке. Сравнить эффективность полученных кодов. Вероятности появления букв первичного алфавита имеют следующие значения:
, .
Решение
Кодирование по одной букве в блоке.
Построим код Хаффмана для всевозможных однознаковых комбинаций (рис. 1). Затем строим кодовое дерево (рис. 2).
740529-2183000,75 1
B 0,25
Рисунок 1 – Код Хаффмана для всевозможных однознаковых комбинаций
1
0,75
0,25
0
1
1
0,75
0,25
0
1
Рисунок 2 – Кодовое дерево Хаффмана для всевозможных однознаковых комбинаций
Составляем коды комбинаций:
A – 0
B – 1
Энтропия:
.
Среднее число элементарных символов на блок:
.
Информация на один элементарный символ:
дв. ед.
Кодирование по две букве в блоке.
Построим код Хаффмана для всевозможных двух знаковых комбинаций (рис. 3). Затем строим кодовое дерево (рис. 4).
AA 0,5625 0,5625 0,5625 53686835311
0,25 937260-18858800-70680160655000,4375
AB 0,1875 776450-198601000,1875
BA 0,1875 77763-30149900
BB 0,0625 -129540-20320000
Рисунок 3 – Код Хаффмана для всевозможных двух знаковых комбинаций
1
0,5625
0
1
0,4375
0,25
0
1
0,625
0,1875
0
1
0,1875
1
0,5625
0
1
0,4375
0,25
0
1
0,625
0,1875
0
1
0,1875
Рисунок 4 – Кодовое дерево Хаффмана для всевозможных двух знаковых комбинаций
Составляем коды комбинаций:
AA – 1
AB – 00
BA – 011
BB – 010
Энтропия:
.
Среднее число элементарных символов на блок:
.
Информация на один элементарный символ:
дв
. ед.
Кодирование по две букве в блоке.
Построим код Хаффмана для всевозможных двух знаковых комбинаций (рис. 3). Затем строим кодовое дерево (рис. 4).
Составляем коды комбинаций:
AAA – 0
AAB – 110
ABA – 101
ABB – 11111
BAA – 100
BAB – 11110
BBA – 11101
BBB – 11100
66241117987000,578125 4248175623001
AAA 0,421875 0,421875 0,421875 0,421875 0,421875 0,421875 0,421875
0,15625 0,15625 726359-41501900-3829347327006161629525000,296875
AAB 0,140625 0,140625 0,140625 611505148590000,140625 621665-165735000,140625
ABA 0,140625 0,140625 0,140625 0,140625 -1037254610000,28125 0,28125
BAA 0,140625 0,140625 0,140625 0,140625
ABB 0,046875 0,046875 072390000,09375 29255-63512400
BAB 0,046875 644525-184150000,046875 624205-19367500
BBA 0,046875 2540059055000,0625 0,0625
BBB 640715-187960000,015625
Рисунок 5 – Код Хаффмана для всевозможных трех знаковых комбинаций
1
0,15625
0
1
0,09375
0
1
0,015625
0,046875
0
1
0,0625
0, 0,046875
0,046875
0
1
0,140625
0
1
0,296875
0,140625
0,140625
1
1
0
0
0,28125
0,578125
0,421875
1
0,15625
0
1
0,09375
0
1
0,015625
0,046875
0
1
0,0625
0, 0,046875
0,046875
0
1
0,140625
0
1
0,296875
0,140625
0,140625
1
1
0
0
0,28125
0,578125
0,421875
Рисунок 6 – Кодовое дерево Хаффмана для всевозможных трех знаковых комбинаций
Энтропия:
.
Среднее число элементарных символов на блок:
.
Информация на один элементарный символ:
дв
Задать вопрос
на новый заказ в Автор24.
