Форум » Кодирование и декодирование информации » Задание 4, № 166, в Генераторе № 3504 » Ответить
Задание 4, № 166, в Генераторе № 3504
Осипенко: Находим суммарную длину приведённых кодов из условия: 4+3+4+3+3=17. При построении двоичного дерева выясняем, что "свободные места" для букв "О" и "Я" наименьшей длины - это коды 000, 011, 111. Для двух букв суммарная длина кодов = 6. Тогда в ответе должно быть 17+6=23. С ответом в "Генераторе" не сходится. Там 22. Где я ошибаюсь?
Ответов - 5
polyakovss: Используйте обратное условие Фано. Тогда "свободные места" для букв "О" и "Я" наименьшей длины - это коды 11 и 000.
JuliaSt: *PRIVAT*
JuliaSt: Но там же Р=110. К – 1010, Т – 100, Б – 0101, Р – 110, Ь – 001. Остаются две буквы нераспределенные. Три ветки длиной в 3 бита. Мы можем переместить букву в 4 бита на ветку в 3 бита?
polyakovss: Здравствуйте, JuliaSt! Для однозначного декодирования достаточно выполнения либо условия Фано, либо обратного условия Фано (достаточно одного из них). Используется обратное условие Фано, для которого можно построить дерево, в котором движение от корня к букве дает её код с конца (обратный код): К - 1010 --> 0101 T - 100 --> 001 Б - 0101 --> 1010 Р - 110 --> 011 Ь - 001 --> 100 О - 11 --> 11 Я - 000 --> 000 P.S. Посмотрите Р-06 (Решение (2 способ, дерево)) в ege4.doc. Программа для построения дерева двоичного кода - здесь.
elpov06: Здравствуйте, подскажите пожалуйста, тогда при решении задач на условие фано нужно проверять по двум условиям по прямому и по обратному условию фано?
полная версия страницы