Задание 4
тема 1 из 1

Неравномерный код и условие Фано

Неравномерный двоичный код даёт буквам кодовые слова разной длины, и сообщение читается однозначно, если код удовлетворяет условию Фано. По этому условию никакое кодовое слово не является началом другого, поэтому все слова стоят в листьях кодового дерева. Свободные ветки дерева дают новые кодовые слова: самые короткие ветки отдают частым буквам, а ветку делят надвое, только если веток не хватает.

Главная тема в задании4На карте навыков

Как подобрать кодовые слова по условию Фано

Условие Фано: никакое кодовое слово не является началом другого кодового слова. Код с этим условием декодируется однозначно.

  • Нарисуйте кодовое дерево: от каждой вершины ветка 0 идёт влево, ветка 1 — вправо. Каждое известное кодовое слово — лист дерева.
  • Найдите свободные ветки: вершины, на пути к которым нет кодового слова и под которыми нет кодового слова. Каждая свободная ветка — новое кодовое слово.
  • Если свободных веток меньше, чем букв, делите самую короткую ветку длины dd на две ветки длины d+1d + 1. Сумма длин растёт на d+2d + 2.
  • Длина сообщения — сумма длин кодовых слов всех его букв. Самые короткие слова отдайте самым частым буквам.
  • Если условие просит слово с наименьшим числовым значением, из слов одной длины берут меньшее: 100<101100 < 101.

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

Двоичный код ставит каждой букве алфавита в соответствие кодовое слово — цепочку из нулей и единиц. В равномерном коде все кодовые слова одной длины ii. Таких слов 2i2^i, поэтому для алфавита из NN букв нужна наименьшая длина ii, при которой 2i≥N2^i \ge N. Так же находят длину кода символа.

В неравномерном коде кодовые слова разной длины. Частая буква получает короткое слово, редкая — длинное, и всё сообщение становится короче. Длина сообщения равна сумме длин кодовых слов всех его букв, с учётом повторов.

Пример

Сообщения пишут буквами Б, К, Л, О, Н. Сколько двоичных знаков займёт слово КОЛОБОК в равномерном коде наименьшей длины?

  1. 1.В алфавите 5 букв. 22=4<52^2 = 4 < 5, 23=8≥52^3 = 8 \ge 5, значит, каждое кодовое слово — 3 знака.
  2. 2.В слове КОЛОБОК 7 букв: 7⋅3=217 \cdot 3 = 21.

Ответ: 2121

Условие Фано

В неравномерном коде нет границ между словами, и одну цепочку можно иногда разрезать на слова по-разному. Условие Фано (прямое) запрещает это: никакое кодовое слово не является началом другого кодового слова. Код с этим условием называют префиксным. Его сообщение читают слева направо, и каждое слово узнают сразу, как только оно прочитано.

Обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова. Такой код тоже декодируется однозначно, но сообщение читают с конца.

Чтобы проверить код, сравните каждую пару слов: короткое слово не должно совпадать с началом длинного. Слово из одного знака 0 запрещает все слова, которые начинаются с 0.

Пример

Буквы закодированы так: А — 0, Б — 01, В — 10. Выполнено ли условие Фано? Сколькими способами можно прочитать сообщение 010?

  1. 1.Слово А (0) — начало слова Б (01). Условие Фано нарушено.
  2. 2.Первый способ: 0 и 10, это АВ.
  3. 3.Второй способ: 01 и 0, это БА.

Ответ: условие не выполнено, два способа: АВ и БА

Декодирование сообщения

Сообщение в коде с прямым условием Фано читают слева направо. Набирайте знаки по одному, пока цепочка не совпадёт с кодовым словом. Запишите букву и начните новую цепочку со следующего знака. Ошибки быть не может: короткое слово не является началом длинного, поэтому первое совпадение — единственное.

Если код удовлетворяет только обратному условию Фано, так же читают сообщение с последнего знака к первому.

Пример

Код: А — 00, Б — 01, В — 100, Г — 101, Д — 11. Расшифруйте сообщение 0110010011.

  1. 1.0 — не слово, 01 — слово Б.
  2. 2.Дальше 1, 10 — не слова, 100 — слово В.
  3. 3.Снова 100 — В.
  4. 4.Осталось 11 — слово Д.

Ответ: БВВД

Кодовое дерево

Кодовое дерево — схема всех двоичных цепочек. Из корня и из каждой вершины выходят две ветки: 0 влево, 1 вправо. Путь от корня до вершины записывает цепочку. Код удовлетворяет условию Фано тогда и только тогда, когда каждое кодовое слово — лист: на пути к нему нет другого слова и ниже него слов нет.

Свободная ветка — вершина, на пути к которой нет кодового слова и под которой нет кодового слова. Любая свободная ветка может стать новым кодовым словом. Чтобы найти свободные ветки, спускайтесь по путям всех известных слов. Каждая ветка, от которой не идёт ни одно известное слово, свободна.

Пример

Код: А — 0, Б — 10, В — 110. Найдите кодовое слово для буквы Г, при котором условие Фано сохранится.

010101АБВГ
Слова А, Б, В — листья дерева. Ветка 111 свободна, её отдаём букве Г.
  1. 1.Ветка 0 занята словом А. Ветка 1 ведёт к словам Б и В.
  2. 2.Под вершиной 1 ветка 10 занята словом Б, ветка 11 ведёт к слову В.
  3. 3.Под вершиной 11 ветка 110 занята словом В, ветка 111 свободна.

Ответ: Г — 111

Кратчайшее кодовое слово

Чтобы найти кратчайшее слово для новой буквы, выпишите все свободные ветки и возьмите самую короткую. Если коротких веток несколько, ответ — ветка с меньшим числовым значением: цепочки одной длины сравнивают как двоичные числа.

Если после этой буквы код получит ещё буквы, для них тоже должна остаться свободная ветка. Последнюю свободную ветку нельзя отдать целиком: её делят на две ветки на один знак длиннее, и новая буква берёт меньшую из них.

Пример задания

Открытый банк ФИПИ

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

Наименьшая сумма длин новых слов

Найдите все свободные ветки и их длины. Если веток не меньше, чем новых букв, отдайте буквам самые короткие ветки. Если веток не хватает, делите ветку: ветка длины dd превращается в две ветки длины d+1d + 1. Одно слово длины dd меняется на два слова длины d+1d + 1, и сумма длин растёт на d+2d + 2. Поэтому делят самую короткую ветку.

Иногда выгоднее взять ещё одну длинную свободную ветку, чем делить короткую. Сравните оба варианта: добавить ветку длины ee стоит ee, деление ветки длины dd стоит d+2d + 2.

Пример

Код: А — 1, Б — 01. Ещё трём буквам В, Г, Д нужны кодовые слова. Найдите наименьшую сумму длин этих слов при условии Фано.

  1. 1.Ветка 1 занята словом А, ветка 01 — словом Б. Свободна только ветка 00 длины 2.
  2. 2.Нужно три слова. Делим 00 на 000 и 001: два слова длины 3.
  3. 3.Нужно ещё одно. Делим 000 на 0000 и 0001.
  4. 4.Слова 0000, 0001, 001: 4+4+3=114 + 4 + 3 = 11.

Ответ: 1111

Наименьшее произведение длин

Если ответ — произведение длин двух новых слов, сначала найдите наименьшую сумму длин. Затем среди всех вариантов с этой суммой выберите вариант с наименьшим произведением. При одной сумме произведение меньше, когда длины сильно различаются: 2⋅4=82 \cdot 4 = 8, а 3⋅3=93 \cdot 3 = 9.

Пример

Код: А — 0, Б — 100, В — 1010. Буквам Г и Д нужны слова с наименьшей суммой длин. Найдите наименьшее произведение их длин.

  1. 1.Свободные ветки: 11 (длина 2) и 1011 (длина 4).
  2. 2.Вариант 1: слова 11 и 1011, сумма 2+4=62 + 4 = 6.
  3. 3.Вариант 2: делим 11 на 110 и 111, сумма 3+3=63 + 3 = 6. Сумма та же.
  4. 4.Произведения: 2⋅4=82 \cdot 4 = 8 и 3⋅3=93 \cdot 3 = 9. Наименьшее — 8.

Ответ: 88

Слово, которое нарушает условие Фано

Новое слово нарушает условие Фано в двух случаях: оно является началом известного слова или известное слово является его началом. Чтобы найти самое короткое такое слово, перебирайте цепочки по длине, начиная с длины, которую требует условие. Цепочки одной длины проверяйте по возрастанию числового значения. Слова, которые уже есть в коде, пропускайте.

Пример

Код: А — 1, Б — 01, В — 000, Г — 001. Найдите самое короткое слово для буквы Д из двух и более знаков, которое нарушает условие Фано и не совпадает с известными словами. Если таких слов несколько, укажите слово с наименьшим числовым значением.

  1. 1.Слова из двух знаков по возрастанию: 00, 01, 10, 11.
  2. 2.00 — начало слов 000 и 001. Условие нарушено.
  3. 3.00 — первое слово длины 2, оно не совпадает с известными словами.

Ответ: 00

Наименьшая длина сообщения

Посчитайте, сколько раз каждая буква стоит в сообщении. Длина сообщения — сумма произведений: число повторов буквы на длину её кодового слова. Чтобы сумма была наименьшей, самое короткое свободное слово отдайте самой частой букве, следующее — следующей по частоте.

Варианты деления веток сравнивайте по длине сообщения, а не по сумме длин слов: частой букве выгодна короткая ветка, даже если редкие буквы получат длинные.

Пример

Сообщения пишут буквами Б, К, Л, О, Н в коде с условием Фано. Известно: Б — 00, Н — 010, Л — 111. Сколько двоичных знаков займёт слово КОЛОБОК при наименьшей длине кода?

  1. 1.Свободные ветки: 10 (длина 2), 011 и 110 (длина 3). Букв К и О две, ветки делить не нужно.
  2. 2.В слове О встречается 3 раза, К — 2 раза. О получает 10, К — слово длины 3.
  3. 3.Длина: К:2⋅3=6\text{К}: 2 \cdot 3 = 6, О:3⋅2=6\text{О}: 3 \cdot 2 = 6, Л:1⋅3=3\text{Л}: 1 \cdot 3 = 3, Б:1⋅2=2\text{Б}: 1 \cdot 2 = 2.
  4. 4.6+6+3+2=176 + 6 + 3 + 2 = 17. Это меньше 21 в равномерном коде.

Ответ: 1717

Кодовое слово нужно каждой букве алфавита

Код строят для всего алфавита, а не для одного сообщения. Буква, которой нет в слове, всё равно занимает свободную ветку. В длину сообщения она не входит, поэтому ей отдают самую длинную ветку.

Пример задания

Открытый банк ФИПИ

По каналу связи передаются сообщения, содержащие только буквы из набора: Д, И, К, Л, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Д — 1, Я — 011. Для трёх оставшихся букв И, К и Л кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова ИДИЛЛИЯ, если известно, что оно закодировано минимально возможным количеством двоичных знаков? 

Потренируйте навык

Все задания на этот навык

Решать