кодує символи джерела запропонованим кодом, буде така двійкова послідовність 000101. Ця послідовність допускає декілька різних результатів декодування, а саме: збігається з послідовністю, що була закодована; та відрізняються від послідовності, яку згенерувало джерело. Це означає, що такий код не забезпечує однозначне декодування.
Необхідною умовою однозначного декодування нерівномірного двійкового коду є виконання співвідношення ( нерівність Крафта )
(2.1) |
де кількість кодових комбінацій коду;
довжина i - ої кодової комбінації.
Для запропонованого вище коду ця умова не виконується:
При нерівність Крафта буде виконуватись, наприклад, якщо
Однозначне декодування забезпечують коди, в яких жодна з більш коротких кодових комбінацій не збігається з початковою частиною кожної більш довгої кодової комбінації. Такі коди називають префіксними. У запропонованому коді кодова комбінація 0 для символу співпадає з початком кодової комбінації 01 для символу тобто цей код не є префіксним.
Побудова префіксних кодів пов’язана зі спеціальними графами, які мають назву кодових дерев (або просто дерев). m - ковим деревом називають граф, тобто систему вузлів і гілок (ребер), в якому відсутні петлі (замкнені шляхи) та із кожного вузла виходить не більше ніж m гілок, а в кожний вузол, крім одного (кореня дерева), входить точно одна гілка. Вузол, з якого не виходить жодної гілки, називають кінце