Question

Для кодирования последовательности, состоящей из букв А, Б, В, Г, Д, использовали неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Г использовали кодовое слово 1, для буквы Д — кодовое слово 01. Какова наименьшая возможная суммарная длина всех пяти кодовых слов?

Answer 1

Для розрахунку наименьшої можливої сумарної довжини всіх п'яти кодових слів, використовується умова Фано, за якою кодові слова не повинні бути префіксами одне одного. З цією умовою, можна побудувати оптимальне префіксне кодування.

Задані кодові слова:

Г - 1

Д - 01

Побудуємо префіксне кодування, де кодові слова не є префіксами одне одного:

Г - 1

Д - 01

В - 001

А - 0001

Б - 0000

Сумарна довжина всіх п'яти кодових слів дорівнює сумі довжин цих кодів:

1 + 2 + 3 + 4 + 4 = 14

Тому наименьша можлива сумарна довжина всіх п'яти кодових слів - 14.