Кодирование - это перевод информации с одного языка, в последовательность кодов. Для удобства ее хранения, передачи и обработки.
При вводе в компьютер информации, происходит ее двоичное кодирование. Информация может быть текстовая, графическая, звуковая. Код символа хранится в оперативной памяти компьютера. В процессе вывода символа на экран производится обратная операция — декодирование, т. е. преобразование кода символа в его изображение, символ или звук.
Декодирование - процесс обратный кодированию, т.е. расшифровка кодов.
Кодирование информации может быть равномерным и неравномерным.
При равномерном кодировании каждому символу соответствует код одинаковой длины.
При неравномерном кодировании различным символам могут соответствовать коды различной длины.
Условие Фано
Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.
Например пара кодовых слов 10 и 101 не выполняют условие Фано, потому что 101 является началом 10. А вот 100 и 101 уже выполняют условие Фано.
В конце статьи мы разберем задание в котором нужно найти кодовое слово для буквы удовлетворяющее условию Фано. На примере часто бывает проще разобраться!
Код который удовлетворяет условию Фано, называется префиксным. Префиксный код однозначно декодируется с начала.
Вы можете встретить еще постфиксный код - это код, в котором никакое кодовое слово не является концом другого кодового слова. Такое закодированное сообщение декодируется однозначно и только с конца. Постфиксный код удовлетворяет обратному условию Фано.
Бинарное дерево на рисунке построено до значений из таблицы триад, можно продолжить строить дерево, но принцип я думаю понятен.
Для кодирования некоторой последовательности, состоящей из букв У, К, Е, Н, Г решили использовать неравномерный двоичный код удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Для букв У, К, Е использовали соответственно кодовые слова 00, 010, 11. Для двух оставшихся букв - Н и Г - кодовые слова не известны.
Укажите кратчайшее возможное кодовое слово для буквы Н, при котором код будет удовлетворять указанному условию. Если таких кодов несколько, то укажите код с наименьшим числовым значением.
В тех местах где мы находим кодовые слова букв которые нам уже известны, ветка дерева обрывается. Если мы продолжим ее строить, то коды которые будем получать дальше не будут удовлетворять условию Фано.
Если вы уже знакомились с Разбором демоверсии 2021 и делали это внимательно, то вы заметите, что данная задача очень похожа на №4. Я вам предлагаю решить четвертый номер из демоверсии, будьте внимательны, там есть подвох!
Задание №4 по информатике. Демоверсия ЕГЭ. Разбор.
А свои ответы и разборы можете писать в комментариях. И не забывайте подписываться, чтобы не пропустить новые статьи!
