Умение кодировать и декодировать информацию · 26 заданий
- Задание №4№4
Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий усло…
Двоичное кодирование, условие Фано
- Задание №4№4
По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Ч. Для передачи используется двоичный код, удовлетворяющий прямом…
Двоичное кодирование, условие Фано
- Задание №4№4
Для кодирования некоторой последовательности, состоящей из букв Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию…
Двоичное кодирование, условие Фано
- Задание №4№4
По каналу связи передаются шифрованные сообщения, содержащие только семь букв: А, Б, В, Г, Д, Е, Ж. Для передачи используется неравномерный двоичный к…
Двоичное кодирование, условие Фано
- Задание №4№4
По каналу связи передаются шифрованные сообщения, содержащие только семь букв: А, Б, В, Г, Д, Е, Ж. Для передачи используется неравномерный двоичный к…
Двоичное кодирование, условие Фано
- Задание №4№4
По каналу связи передаются шифрованные сообщения, содержащие только семь букв: А, Б, В, Г, Д, Е, Ж. Для передачи используется неравномерный двоичный к…
Двоичное кодирование, условие Фано
- Задание №4№4
По каналу связи передаются шифрованные сообщения, содержащие только пять букв: А, Б, В, Г, Д. Для передачи используется неравномерный двоичный код. Дл…
Двоичное кодирование, условие Фано
- Задание №4№4
По каналу связи передаются сообщения, содержащие только буквы из набора: Д, И, К, Л, Я. Для передачи используется двоичный код, удовлетворяющий услови…
Двоичное кодирование, условие Фано
- Задание №4№4
По каналу связи передаются шифрованные сообщения, содержащие только 9 букв: А, Б, В, Г, Д, Е, Ж, 3, И; для передачи используется неравномерный двоичны…
Двоичное кодирование, условие Фано
- Задание №4№4
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, В, Г, Д, Е и Ж. Для передачи используется двоичный код, удовлетворяющий услов…
Двоичное кодирование, условие Фано
- Задание №4№4
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и 3. Для передачи используется двоичный код, удовлетворяющий…
Двоичное кодирование, условие Фано
- Задание №4№4
По каналу связи передаются сообщения, содержащие только шесть букв: А, Б, В, Г, Д, Е и Ж. Для передачи используется двоичный код, удовлетворяющий усло…
Двоичное кодирование, условие Фано
По каналу связи передаются сообщения, содержащие только буквы из набора: В, Е, М, Н, Р. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: В — 1, М — 001. Для трёх оставшихся букв Е, Н и Р кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова ВЕРМЕЕР, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
Правильный ответ
18
Пояснение
Решение:
Условие Фано означает, что ни одно кодовое слово не является началом другого. Удобно представлять коды как вершины двоичного дерева: выбор кодового слова «закрывает» всю ветку, которая из него растёт, и все его начала.
Буква В кодируется словом 1, поэтому никакой другой код не может начинаться с 1: коды букв Е, Н и Р начинаются с 0. Буква М кодируется словом 001, поэтому оставшиеся коды не могут быть словами 0 и 00 (они были бы началом кода 001) и не могут начинаться с 001. Свободными остаются ветка 01 и ветка 000 со всеми их продолжениями.
В слове ВЕРМЕЕР буква Е встречается 3 раза, Р — 2 раза, В и М — по одному разу, а буква Н не встречается ни разу. Значит самый короткий свободный код надо отдать самой частой букве Е, а букве Н можно дать сколь угодно длинный код.
Кратчайший свободный код — 01 (длина 2), отдаём его букве Е. Тогда для Р и Н остаётся только ветка 000. Само слово 000 занять нельзя: тогда второй букве не осталось бы кода. Берём его продолжения: Р — 0000, Н — 0001 (по 4 знака). Набор кодов 1, 001, 01, 0000, 0001 условию Фано удовлетворяет.
Считаем длину сообщения: В даёт 1⋅1=1 знак, Е — 3⋅2=6 знаков, Р — 2⋅4=8 знаков, М — 1⋅3=3 знака. Всего 1+6+8+3=18.
Меньше получить нельзя. Код буквы Е не может состоять из одного знака: единственный вариант 0 является началом кода 001. Если длина кода Е равна 2, то это обязательно 01, и тогда для Р и Н остаётся одна ветка 000, из которой два разных кода короче четырёх знаков не получить, — это разобранный случай с ответом 18. Если же длина кода Е равна 3, то и код Р не короче 3 знаков, и общая длина будет не меньше 1+9+6+3=19.
Ответ: 18