Для кодирования растрового рисунка, напечатанного с использованием шести красок, применили неравномерный двоичный код, удовлетворяющий условию Фано.

Задача №3 Используемые коды: Белый — 0 Фиолетовый — 110 Зелёный — 1111 Красный — 10 Чёрный — 1110 Для кодирования шестого цвета нужно выбрать такое кодовое слово, которое удовлетворяет условию Фано (никакое кодовое слово не является началом другого). Посмотрим на занятые префиксы: - 0 (белый) - 10 (красный) - 110 (фиолетовый) - 1110 (чёрный) - 1111 (зелёный) Свободные «ветви» дерева кодирования: - Если мы начнем с 111, то это занято (1110, 1111). - Если мы начнем с 11, то это занято (110, 111). - Если мы начнем с 1, то это занято (10, 11). Единственный свободный вариант — использовать префикс, который не занят другими словами. Посмотрим на бинарное дерево: Код 111 уже нельзя использовать, так как заняты 1110 и 1111. Нужно взять код, который начинается на 11, но не является префиксом существующих. У нас есть 110 (фиолетовый), 1110 (черный), 1111 (зеленый). Посмотрим код, начинающийся на 10... (занято красным). Посмотрим код, начинающийся на 0... (занято белым). Кажется, все ветки, начинающиеся на 1, заблокированы, кроме тех, что ведут к уже занятым листьям. Подождите, посмотрим внимательнее: 1 - свободно (но это префикс для 10, 110, 111). На самом деле, свободного короткого слова нет, так как все комбинации длины 1, 2, 3 частично заняты. Самый короткий свободный код — это код длиной 4, не совпадающий с 1110 и 1111. Но таких нет. Следующая длина — 5. Например, 11100 или 11101. Ответ: 11100 Задача №4 Известны коды: А — 011 Б — 010 В — 001 Г — 000 Нужно добавить коды для Д и Е так, чтобы условие Фано соблюдалось и код был кратчайшим. Использованные префиксы: 000 (Г) 001 (В) 010 (Б) 011 (А) Все коды начинаются на 0. Значит, ветка 1 полностью свободна. Кратчайшее слово для Д — 1. Теперь для Е нужно слово, которое не начинается на 1 (так как 1 занято Д) и не является префиксом А, Б, В, Г. Все коды А, Б, В, Г начинаются на 0. Если мы возьмем 10 для Е, это будет корректно. Значит, Д = 1, Е = 10. Ответ: Д — 1, Е — 10