Теорія інформації та кодування в задачах
37


кодує символи джерела запропонованим кодом, буде така двійкова послідовність 000101. Ця послідовність допускає декілька різних результатів декодування, а саме: збігається з послідовністю, що була закодована;  та відрізняються від послідовності, яку згенерувало джерело. Це означає, що такий код не забезпечує однозначне декодування.

Необхідною умовою однозначного декодування нерівномірного двійкового коду є виконання співвідношення  ( нерівність Крафта )

(2.1)

де кількість кодових комбінацій коду;

довжина  i - ої кодової комбінації.

Для запропонованого вище коду ця умова не виконується:

При нерівність Крафта буде виконуватись, наприклад, якщо

Однозначне декодування забезпечують коди, в яких жодна з більш коротких кодових комбінацій не збігається з початковою частиною кожної більш довгої кодової комбінації. Такі коди називають префіксними. У запропонованому коді кодова комбінація 0 для символу  співпадає з початком кодової комбінації 01 для символу  тобто цей код не є префіксним.

Побудова префіксних кодів пов’язана зі спеціальними графами, які мають назву  кодових дерев  (або просто дерев). m - ковим деревом називають граф, тобто систему вузлів і гілок (ребер), в якому відсутні петлі (замкнені шляхи) та із кожного вузла виходить не більше ніж m гілок, а в кожний вузол, крім одного (кореня дерева), входить точно одна гілка. Вузол, з якого не виходить жодної гілки, називають кінце