Задание 4 ЕГЭ по информатике. Неравномерное кодирование и условие Фано

Теория: кодирование, декодирование и условие Фано

Кодирование — это перевод информации с одного языка на другой (например, с «человеческого» на двоичный).

Декодирование — обратный процесс. Один символ исходного текста может соответствовать одному или нескольким символам в коде, и наоборот.

Равномерный и неравномерный код

• Равномерный код — все символы имеют одинаковую длину кода.
• Неравномерный код — длины кодовых слов разные, что делает передачу информации более эффективной, но требует дополнительного условия для однозначной расшифровки.

Условие Фано

Никакое кодовое слово не является началом другого кодового слова.

Если это условие выполняется, сообщение можно расшифровать однозначно, двигаясь слева направо по последовательности битов.
Условие Фано — достаточное, но не обязательное для однозначного декодирования.
Чтобы проверить его, удобно построить дерево кодирования.

             (начало)
             /      \
            0        1
           / \      / \
         00  01   10  11

В листьях дерева (узлы без продолжений) располагаются коды символов. Если все используемые коды — листья дерева, условие Фано выполняется.

Простое задание: выбор кода по условию Фано

Условие:
Для кодирования букв Л, М, Н, П, Р используется неравномерный двоичный код, удовлетворяющий условию, что никакое кодовое слово не является началом другого.
Известно:
Л — 00, М — 01, Н — 11.
Нужно выбрать кратчайший возможный код для буквы П, чтобы условие Фано сохранялось.
Если таких кодов несколько — выбрать код с наименьшим числовым значением.

Пошаговое решение

1. Построим дерево по имеющимся кодам:

             (начало)
             /      \
            0        1
           / \        \
         00  01       11
         Л   М        Н

Коды 00, 01 и 11 заняты. Свободна ветка 10 — она пока не используется.

2. Поскольку нам нужно добавить две буквы (П и Р), «навешиваем» их на ветку 10, создавая два подуровня:

             (начало)
             /      \
            0        1
           / \      / \
         00  01   10  11
         Л   М    / \
                 100 101
                 П   Р

3. Таким образом, оба новых слова (100 и 101) не пересекаются с другими.
Ответ: 100 — кратчайший возможный код с наименьшим числовым значением.

Задание посложнее: подсчёт количества возможных кодов

Условие:
Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, где никакое кодовое слово не является началом другого (условие Фано).
Известные коды:

    И — 110
    Н — 011
    Ф — 00
    О — 1111
    Р — 11100
    М — 11101
    А — 1001
    Т — 101
    К — 1000

Сколько существует способов назначить для буквы Ю код длиной ≤ 6 бит, чтобы условие Фано сохранялось?

1. Строим дерево кодов

           (начало)
           /      \
          0        1
         / \     /   \
       00  01  10   11
       Ф   Н   / \   / \
          (конец)  ...  ...

Наносим все известные коды; «занятые» узлы — это листья, на которых уже размещены буквы:

    Ф — 00          А — 1001
    Н — 011         К — 1000
    И — 110         Т — 101
    О — 1111        Р — 11100
                     М — 11101

Промежуточное дерево (занятые листья отмечены ✦):

             (начало)
             /      \
            0        1
           / \      / \
         00✦ 01✦  10✦ 11
                 / |   | \
              100✦101✦110✦111
                        / \
                     1110✦1111✦

Узлы, помеченные ✦, заняты. Новые коды могут размещаться только там, где ветвь ещё свободна.

2. Свободные ветви

• Из ветви «0»: после 00 и 01 свободно — ничего (всё занято).
• Из ветви «1»: свободных мест нет на глубинах ≤ 5, кроме подветвей, не ведущих к занятым листьям.

Чтобы не нарушить условие Фано, новый код не должен быть ни началом, ни продолжением уже имеющегося кода.
Проверив все возможные сочетания длиной ≤ 6 бит, получаем 14 возможных вариантов.

Ответ: 14

Мини-практика для учеников

1. Постройте дерево для кодов из первого примера самостоятельно. Проверьте, где появляются листья, а где — внутренние узлы.
2. Попробуйте добавить новую букву С, выбрав для неё код, который не нарушает условие Фано.
3. Для второго примера создайте таблицу всех допустимых кодов длиной ≤ 6, вычеркнув запрещённые префиксы, чтобы убедиться, что остаётся ровно 14 вариантов.