Page 175 - 4496

H = -0.22 log 20.22 -0.20 log 20.20 - ... -0.02  log 20.02 =
2.754.
Підрахуємо середню кількість символів кодової
комбінації на знак:
= i
N
L =  p  k i ,
= i 1 i
де p i, k i - імовірність та кількість символів кодової комбінації
знаку z i,
L =
0.222+0.203+0.163+0.162+0.103+0.104+0.045+0.025 =
2.84.
Середня кількість символів на знак L=2.84 завдяки
кодуванню виявилась меншою k=3, отже надмірність було
усунуто. В той же час середня кількість символів на знак
L=2.84 виявилась більшою ентропії H=2.754. Це означає, що
деяка надмірність залишилась і після кодування.

4.4.5. Ефективне кодування за методом Хаффмена

Розглянута методика Шеннона-Фано не завжди дає
однозначну побудову коду. Це пояснюється тим, що при
розбитті на підгрупи за сумарною імовірністю можна зробити
більшою як першу, так і другу підгрупи.
Так, для наведеного прикладу на першому ступені
сумарні імовірності було взято рівними 0.58 (для символів
z 1..z 3) і 0.42 (для символів z 4..z 8). Але їх можна було також
взяти рівними 0.42 (для символів z 1..z 2) і 0.58 (для символів
z 3..z 8). Зрозуміло, що інший код має дати інше значення
середньої кількості символів на знак. Але сказати наперед, в
якому варіанті коду це значення менше, неможливо.
Від указаного недоліку вільна методика Хаффмена. Вона
дає однозначну побудову коду з найменшим для даного
розподілу імовірностей середнім числом символів на знак.
Знаки алфавіту джерела повідомлень виписуємо в
основний стовпчик у порядку спадання імовірностей. Два
останніх знаки об’єднуємо в один допоміжний знак, якому
приписуємо сумарну імовірність. Імовірності знаків, що не
об’єднувались, а також одержану сумарну імовірність знову
розташовуємо в порядку спадання в додатковому стовпчику.
172