Как найти суммарную длину кодовых слов

Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Л использовали кодовое слово 1, для буквы М  — кодовое слово 01. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

Примечание.

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

Информатика ЕГЭ 4 задание разбор, кодирование и декодирование информации

4-е задание: «Кодирование и декодирование информации»
Уровень сложности — базовый,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 2 минуты.

Проверяемые элементы содержания: Умение кодировать и декодировать информацию

Плейлист видеоразборов задания на YouTube:

Закодируйте последовательность букв ВОДОПАД таким способом и результат запишите восьмеричным кодом.

Ответ: 22162

Ответ: b a c d e

Результат: b a c d e.

Этот вариант решения 4 задания ЕГЭ более сложен, но тоже верен.

Ответ: 6 5 4 3

Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

Ответ: 9

Ответ: 00

Ответ: 101

Укажите кратчайшее кодовое слово для буквы Б, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Ответ: 1100

Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Ответ: 00

Дерево по условию Фано (однозначно декодируется с начала):

Дерево по обратному условию Фано (однозначно декодируется с конца):

Результат: 00

По каналу связи передаются сообщения, содержащие только буквы: А, Е, Д, К, М, Р; для передачи используется двоичный код, удовлетворяющий условию Фано. Известно, что используются следующие коды:

Укажите наименьшую возможную длину закодированного сообщения ДЕДМАКАР.
В ответе напишите число – количество бит.

Ответ: 20

Источник

Как найти длину кодового слова

Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К — кодовое слово 10. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

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

Найдём наиболее короткие представления для всех букв. Кодовые слова 01 и 00 использовать нельзя, поскольку тогда нарушается условие Фано. Используем, например, для буквы Л кодовое слово 11. Тогда для четвёртой буквы нельзя подобрать кодовое слово, не нарушая условие Фано. Следовательно, для оставшихся двух букв нужно использовать трёхзначные кодовые слова. Закодируем буквы Л и М кодовыми словами 110 и 111. Тогда суммарная длина всех четырёх кодовых слов равна

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А — 1; Б — 0100; В — 000; Г — 011; Д — 0101. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать?

Для однозначного декодирования получившееся в результате сокращения кодовое слово не должно быть началом никакого другого. Первый вариант ответа не подходит, поскольку код буквы А является началом кода буквы Г. Второй вариант ответа подходит. Третий вариант ответа не подходит, т. к. в таком случае код буквы Г является началом кода буквы Д.

Правильный ответ указан под номером: 2.

Для кодирования некоторой последовательности, состоящей из букв И, К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К – кодовое слово 10. Какова наименьшая возможная суммарная длина всех пяти кодовых слов?

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Нельзя использовать кодовые слова, которые начинаются с 0 или с 10. 11 также не можем использовать, поскольку тогда мы больше не сможем взять никакое другое кодовое слово, а нам их нужно пять. Поэтому берём трёхзначное 110. 111 опять же не можем использовать, потому что понадобиться ещё одно кодовое слово, а вместе с этим не останется больше свободных. Теперь осталось взять всего два слова и это будут 1110 и 1111. Итого имеем 0, 10, 110, 1110 и 1111 — 14 символов.

Для кодирования некоторой последовательности, состоящей из букв И, К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Л использовали кодовое слово 1, для буквы М – кодовое слово 01. Какова наименьшая возможная суммарная длина всех пяти кодовых слов?

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Условие Фано — никакое кодовое слово не может быть началом другого кодового слова. Так как уже имеется кодовое слово 1, то никакое другое не может начинаться с 1. Только с 0. Также не может начинаться с 01, поскольку у нас уже есть 01. То есть любое новое кодовое слово будет начинаться с 00. Но это не может быть 00, так как иначе мы не сможем взять больше ни одного кодового слова, поскольку все более длинные слова начинаются либо с 1, либо с 00, либо с 01. Мы можем взять либо 000, либо 001. Но не оба сразу, поскольку опять же в таком случае мы больше не сможем взять ни одного нового кода. Тогда возьмём 001. И так как нам осталось всего два кода, то можем взять 0000 и 0001. Итого имеем: 1, 01, 001, 0000, 0001. Всего 14 символов.

Источник

Как найти длину кодового слова

010 010 001 110 010

Результат: 22162

Решение ЕГЭ данного задания по информатике, видео:

ЕГЭ 5.2: Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти коды представлены в таблице:

Результат: b a c d e.

2 вариант решения: Этот вариант решения 5 задания ЕГЭ более сложен, но тоже верен.

Результат: b a c d e.

Кроме того, вы можете посмотреть видео решения этого задания ЕГЭ по информатике:

Решим следующее 5 задание:

Где сами цифры исходного числа: 0010 1 0011 0 (0010 — 2, 0011 — 3)

Первая добавленная цифра 1 после двоичной двойки — это проверка четности (1 единица в 0010 — значит нечетное), 0 после двоичной тройки — это также проверка нечетности (2 единицы в 0011, значит — четное).

Исходя из разбора примера решаем нашу задачу так: поскольку «нужные» нам цифры образуются из групп по 4 числа в каждой плюс одно число на проверку четности, то разобьем закодированное сообщение на группы по 5, и отбросим из каждой группы последний символ:

01100 01010 01001 00110

0110 0101 0100 0011

Вы можете посмотреть видео решения этого задания ЕГЭ по информатике:

Кодовые слова 01 и 00 использовать нельзя, так как тогда нарушается условие Фано (начинаются с 0, а 0 — это Н).

Возьмем для буквы Л кодовое слово 11. Тогда для четвёртой буквы нельзя подобрать кодовое слово, не нарушая условие Фано (если потом взять 110 или 111, то они начинаются с 11).

Значит для надо использовать трёхзначные кодовые слова. Закодируем буквы Л и Мкодовыми словами 110 и 111.

Суммарная длина всех четырёх кодовых слов равна (Н)1 + (К)2 + (Л)3 + (М)3 = 9.

1 вариант решения: будем использовать дерево

Суммарная длина всех четырёх кодовых слов равна (Н)1 + (К)2 + (Л)3 + (М)3 = 9.

РАЗБОР ЗАДАНИЯ 5 ЕГЭ ПО ИНФОРМАТИКЕ 2017

Следующим наименьшим кодом было бы двухбуквенное слово 00. Так как оно не является префиксом ни одного из представленных кодовых слов, то Г = 00.

Результат: 00

Результат: 101

Подробней разбор урока можно посмотреть на видео ЕГЭ по информатике 2017:

1 — не подходит (все буквы кроме А начинаются с 1)
10 — не подходит (соответствует коду Д)
11 — не подходит (начало кодов Б, В и Г)
100 — не подходит (код Д — 10 — является началом данного кода)
101 — не подходит (код Д — 10 — является началом данного кода)
110 — не подходит (начало кода В и Г)
111 — не подходит (соответствует коду Б)
1000 — не подходит (код Д — 10 — является началом данного кода)
1001 — не подходит (код Д — 10 — является началом данного кода)
1010 — не подходит (код Д — 10 — является началом данного кода)
1011 — не подходит (код Д — 10 — является началом данного кода)
1100 — не подходит (начало кода В и Г)
1101 — подходит

Результат: 1101

Более подробное решение данного задания представлено в видеоуроке:

Источник

Как найти длину кодового слова

По каналу связи передаются сообщения, содержащие только шесть букв: А, B, C, D, E, F. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв A, B, C используются такие кодовые слова: А – 11, B – 101, C – 0. Какова наименьшая возможная суммарная длина всех кодовых слов?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование.

Заметим, что для алфавита из трёх букв, код с наименьшей суммарной длиной кодовых слов, удовлетворяющий условию Фано имел бы длину 1 + 2 + 2 = 5. Для алфавита из четырёх букв: 1 + 2 + 3 + 3 = 9. Аналогично можно получить минимальную длину суммарную длину кодовых слов для алфавита, содержащего произвольное число символов.

Удостоверимся, что, используя кодовые слова, приведённые в условии можно построить код, удовлетворяющий условию Фано и имеющий наименьшую суммарную длину. Будем использовать для буквы D кодовое слово 1000, для буквы E кодовое слово 10010, для буквы F 10011.

Суммарная длина такого кода 1 + 2 + 3 + 4 + 5 + 5 = 20.

По каналу связи передаются сообщения, содержащие только четыре буквы: З, А, Р, Я; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв Я, Р, З используются такие кодовые слова: Я — 0, Р — 101; З — 110.

Укажите кратчайшее кодовое слово для буквы А, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наибольшим числовым значением.

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Заметим, что кодовое слово не может начинаться с нуля, поскольку будет нарушено условие Фано. Кодовые слова 10 и 11 взять нельзя, поскольку будет нарушено условие Фано. Можно взять кодовые слова длины 3: 100 и 111. Поскольку числовое значение кодового слова 100 меньше, возьмём кодовое слово 111.

Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К — кодовое слово 10. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

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

Найдём наиболее короткие представления для всех букв. Кодовые слова 01 и 00 использовать нельзя, поскольку тогда нарушается условие Фано. Используем, например, для буквы Л кодовое слово 11. Тогда для четвёртой буквы нельзя подобрать кодовое слово, не нарушая условие Фано. Следовательно, для оставшихся двух букв нужно использовать трёхзначные кодовые слова. Закодируем буквы Л и М кодовыми словами 110 и 111. Тогда суммарная длина всех четырёх кодовых слов равна

Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Л использовали кодовое слово 1, для буквы М — кодовое слово 01. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

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

Найдём для оставшихся двух символов наиболее короткое представление, удовлетворяющее условию Фано. Кодовое слово 0 использовать нельзя, так как тогда нарушится условие Фано. Из двузначных кодовых слов можно использовать слово 00, а слова 10 и 11 использовать нельзя. При таком построении кодов для четвёртого символа невозможно подобрать кодовое слово.

Поэтому 00 использовать не будем, а будем использовать трёхзначные кодовые слова, например, 000 и 001. Тогда суммарная длина всех четырёх кодовых слов равна 1 + 2 + 3 + 3 = 9.

Аналоги к заданию № 7658: 7685 Все

Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К — кодовое слово 110. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Найдём для оставшихся двух символов наиболее короткое представление, удовлетворяющее условию Фано. Кодовое слово 1 использовать нельзя, так как тогда нарушится условие Фано. Из двузначных кодовых слов можно использовать слово 10, а слова 11 и 01 использовать нельзя. При таком построении кодов для четвёртого символа невозможно подобрать двухзначное кодовое слово. Поэтому используем трёхзначное слово, а именно — 111.

Таким образом, наименьшая возможная суммарная длина всех четырёх кодовых слов будет 1 + 3 + 2 + 3 = 9.

Правильный ответ указан под номером 3.

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

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Найдём для оставшихся двух символов наиболее короткое представление, удовлетворяющее условию Фано. Кодовое слово 0 использовать нельзя, так как тогда нарушится условие Фано. Из двузначных кодовых слов можно использовать слово 00, а слова 11 и 01 использовать нельзя. При таком построении кодов для четвёртого символа невозможно подобрать двухзначное кодовое слово. Поэтому используем трёхзначное слово, а именно 010.

Таким образом, наименьшая возможная суммарная длина всех четырёх кодовых слов будет 1 + 3 + 2 + 3 = 9.

Правильный ответ указан под номером 2.

По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В используются такие кодовые слова: А — 0;

Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

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

Рассмотрим варианты для буквы Г, начиная с самого короткого.

1) Г=1: код буквы Г является началом кода буквы Б — 110, поэтому этот вариант не подходит.

2) Если код Г=01, то условие Фано нарушается, поскольку тогда код буквы А является началом кода буквы Г.

3) Если код Г=101, то условие Фано не нарушается. Данное кодовое слово является кратчайшим для буквы Г.

По каналу связи передаются сообщения, содержащие только шесть букв: А, B, C, D, E, F. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв A, B, C используются такие кодовые слова: А – 00, B – 010, C – 1. Какова наименьшая возможная суммарная длина всех кодовых слов?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование.

Для нахождения кодовых слов будем использовать двоичное дерево, в котором от каждого узла отходит две ветви, соответствующие выбору следующей цифры кода. Буквы будем размещать на конечных узлах дерева — листьях. Условие Фано выполняется, поскольку при проходе от корня дерева к букве в середине пути не встречается других букв.

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

Суммарная длина такого кода 1 + 2 + 3 + 4 + 5 + 5 = 20.

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали соответственно кодовые слова 000, 001, 10, 11. Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Однозначные коды не подходят по условию Фано. Кратчайшее подходящее кодовое слово — 01. Но выбирая его, не останется вариантов закодировать букву E, значит, нужно взять минимум трехзначный код. Минимальный из них, подходящий по условию Фано — 010. Тогда букву Е можно закодировать как 011.

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали соответственно кодовые слова 000, 001, 10, 11. Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Поскольку все однозначные и двузначные слова не подходят по условию Фано, нужно найти трехзначное слово, которое было бы максимально и удовлетряло условию. Так как 111, 101 и 110 нарушают условие Фано, то искомое слово — 010.

Заметим, что двузначное кодовое слово 01 не подходит, поскольку при его использовании нельзя подобрать кодовое слово для буквы Е.

Дублирует задание 13481.

По каналу связи передаются сообщения, содержащие только шесть букв: А, B, C, D, E, F. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв A, B, C используются такие кодовые слова: А — 11, B — 101, C — 0. Укажите кодовое слово наименьшей возможной длины, которое можно использовать для буквы F. Если таких слов несколько, укажите то из них, которое соответствует наименьшему возможному двоичному числу. Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование

Поскольку все однозначные и двузначные слова не подходят по условию Фано, значит, нужно найти трехзначное слово, которое было бы минимально и удовлетворяло условию. Это слово — 100. Однако при выборе кода 100 мы закрываем возможные варианты для D И E. Значит, трехзначные слова нам тоже не подходят, если взять четырехзначные то там мы для кодирования можем взять слово 1000. Тогда для кодирования D и E можно использовать слова 10010 и 10011.

По каналу связи передаются сообщения, содержащие только шесть букв: А, B, C, D, E, F. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв A, B, C используются такие кодовые слова: А — 11, B — 101, C — 0.

Укажите кодовое слово наименьшей возможной длины, которое можно использовать для буквы F. Если таких слов несколько, укажите то из них, которое соответствует наибольшему возможному двоичному числу.

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование.

Имеющиеся кодовые слова имеют длину один, два и три, следовательно, наименьшая длина кодового слова для буквы F равна четырём. Кодовое слово, удовлетворяющее условию Фано — 1001.

Заметим, что более короткое кодовое слово 100 не подходит, поскольку тогда невозможно найти кодовые слова для букв D и E.

Код 1000 не подходит, так как сказано «Если таких слов несколько, укажите то из них, которое соответствует наибольшему возможному двоичному числу».

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 00, Г — 101. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАГИЯ?

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

Следующая буква должна кодироваться как 011, поскольку 01 мы взять не можем, иначе код для буквы А не будет удовлетворять условию Фано. 10 из-за Г взять не можем, тогда следующая буква будет кодироваться как 100. Следующая буква должна кодироваться как 110, поскольку 11 взять не можем, иначе не останется кодовых слов для оставшейся буквы, которые удовлетворяют условию Фано. Значит, последняя буква будет кодироваться как 111. Тогда наименьшее количество двоичных знаков, которые потребуются для кодирования слова МАГИЯ равно

Заметим, что после кодирования всех букв, входящих в слово МАГИЯ, должен остаться хотя бы один свободный код для кодирования буквы Р, которая не входит в данное слово, но может передаваться по каналу связи. Проверить наличие свободного кода можно, построив дерево кодов, как показано в задаче 18553.

По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 0, Б — 1011. Укажите сумму длин кратчайших кодовых слов для букв В и Г, которые будут удовлетворять условию Фано.

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

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

Кодовые слова не могут начинаться с 0, поскольку 0 является кодовым словом для буквы А. Кодовым словом для буквы В будет являться 11. Кодовым словом для буквы Г будет являться 100, кодовое слово 101 взять не можем, поскольку кодовым словом для буквы Б является 1011.

Таким образом, сумма длин кратчайших кодовых слов для букв В и Г будет равна 2 + 3 = 5.

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

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

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

Кодовым словом не могут быть ни 0, ни 1, потому что есть кодовые слова, начинающиеся с 0 и 1. Для оставшихся букв можно использовать кодовые слова 10 и 011. Кратчайшее слово — 10.

Для кодирования некоторой последовательности, состоящей из букв И, К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Л использовали кодовое слово 1, для буквы М – кодовое слово 01. Какова наименьшая возможная суммарная длина всех пяти кодовых слов?

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Условие Фано — никакое кодовое слово не может быть началом другого кодового слова. Так как уже имеется кодовое слово 1, то никакое другое не может начинаться с 1. Только с 0. Также не может начинаться с 01, поскольку у нас уже есть 01. То есть любое новое кодовое слово будет начинаться с 00. Но это не может быть 00, так как иначе мы не сможем взять больше ни одного кодового слова, поскольку все более длинные слова начинаются либо с 1, либо с 00, либо с 01. Мы можем взять либо 000, либо 001. Но не оба сразу, поскольку опять же в таком случае мы больше не сможем взять ни одного нового кода. Тогда возьмём 001. И так как нам осталось всего два кода, то можем взять 0000 и 0001. Итого имеем: 1, 01, 001, 0000, 0001. Всего 14 символов.

Источник

Кодирование – это перевод информации, представленной символами первичного алфавита, в последовательность кодов.
Декодирование (операция, обратная кодированию) – перевод кодов в набор символов первичного алфавита.
Кодирование может быть равномерное и неравномерное. При равномерном кодировании каждый символ исходного алфавита заменяется кодом одинаковой длины. При неравномерном кодировании разные символы исходного алфавита могут заменяться кодами разной длины.

Задача 1

Для кодирования букв О, В, Д, П, А решили использовать двоичное представление
чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если закодировать последовательность букв ВОДОПАД таким способом и результат записать восьмеричным кодом, то получится
1) 22162
2) 1020342
3) 2131453
4) 34017

Решение:
Представим коды указанных букв в дво­ич­ном коде, добавив незначащий нуль для одноразрядных чисел:

Закодируем по­сле­до­ва­тель­ность букв: ВО­ДО­ПАД — 010010001110010.
Разобьём это пред­став­ле­ние на трой­ки спра­ва на­ле­во и пе­ре­ведём каждую тройку в восьмеричное число.
010 010 001 110 010 — 22162.
Пра­виль­ный ответ ука­зан под но­ме­ром 1.
Ответ: 1

Задача 2

Для пе­ре­да­чи по ка­на­лу связи со­об­ще­ния, со­сто­я­ще­го толь­ко из сим­во­лов А, Б, В и Г, ис­поль­зу­ет­ся по­сим­воль­ное ко­ди­ро­ва­ние: А-10, Б-11, В-110, Г-0. Через канал связи пе­ре­даётся со­об­ще­ние: ВАГ­БА­А­ГВ. За­ко­ди­руй­те со­об­ще­ние дан­ным кодом. По­лу­чен­ное дво­ич­ное число пе­ре­ве­ди­те в шест­на­дца­те­рич­ный вид.
1) D3A6
2) 62032206
3) 6A3D
4) CADBAADC

Решение:
За­ко­ди­ру­ем по­сле­до­ва­тель­ность букв: ВАГ­БА­А­ГВ — 1101001110100110. Разобьем это пред­став­ле­ние на четвёрки спра­ва на­ле­во и пе­ре­ведём каждую четверку в шестнадцатеричное число:
1101 0011 1010 01102 = D3A6₁₆
Пра­виль­ный ответ ука­зан под но­ме­ром 1.
Ответ: 1

Задача 3
Для 5 букв ла­тин­ско­го ал­фа­ви­та за­да­ны их дво­ич­ные коды (для не­ко­то­рых букв – из двух бит, для не­ко­то­рых – из трех). Эти коды пред­став­ле­ны в таб­ли­це:

Опре­де­ли­те, какой набор букв за­ко­ди­ро­ван дво­ич­ной стро­кой 1000110110110, если из­вест­но, что все буквы в по­сле­до­ва­тель­но­сти – раз­ные:
1) cbade
2) acdeb
3) acbed
4) bacde

Решение:
Мы видим, что усло­вия Фано и об­рат­ное усло­вие Фано не вы­пол­ня­ют­ся, зна­чит код можно рас­ко­ди­ро­вать не­од­но­знач­но.
Значит, будем перебирать варианты, пока не получим подходящее слово :
1) 100 011 01 10 110
Пер­вая буква опре­де­ля­ет­ся од­но­знач­но, её код 100: a.
Пусть вто­рая буква — с, тогда сле­ду­ю­щая буква — d, потом — e и b.
Такой ва­ри­ант удо­вле­тво­ряет усло­вию, зна­чит, окон­ча­тель­но по­лу­чи­ли ответ: acdeb.
Ответ: 2

Задача 4

Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4, и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23, то получим последовательность 0010100110). Определите, какое число передавалось по каналу в виде 01010100100111100011?
1) 59143 2) 5971 3) 102153 4) 10273

Решение:
При кодировании под саму цифру отводится 4 разряда, и еще один под код проверки четности (т.е. всего под цифру отводится 5 разрядов).
Разобьем заданную последовательность на группы по 5 бит в каждой:
01010, 10010, 01111, 00011.
отбросим пятый (последний) бит в каждой группе:
0101, 1001, 0111, 0001.
это и есть двоичные коды передаваемых чисел:
01012 = 5, 10012 = 9, 01112 = 7, 00012 = 1.
таким образом, были переданы числа 5, 9, 7, 1 или число 5971.
Ответ: 2

Задача 5

По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко 4 буквы — П, О, Р, Т. Для ко­ди­ро­ва­ния букв ис­поль­зу­ют­ся 5-би­то­вые ко­до­вые слова:
П — 11111, О — 11000, Р — 00100, Т — 00011.
Для этого на­бо­ра ко­до­вых слов вы­пол­не­но такое свой­ство: любые два слова из на­бо­ра от­ли­ча­ют­ся не менее чем в трёх по­зи­ци­ях.
Это свой­ство важно для рас­шиф­ров­ки со­об­ще­ний при на­ли­чии помех (в пред­по­ло­же­нии, что пе­ре­да­ва­е­мые биты могут ис­ка­жать­ся, но не про­па­да­ют). За­ко­ди­ро­ван­ное со­об­ще­ние счи­та­ет­ся при­ня­тым кор­рект­но, если его длина крат­на 5 и каж­дая пятёрка от­ли­ча­ет­ся от не­ко­то­ро­го ко­до­во­го слова не более чем в одной по­зи­ции; при этом счи­та­ет­ся, что пятёрка ко­ди­ру­ет со­от­вет­ству­ю­щую букву. На­при­мер, если при­ня­та пя­тер­ка 00000, то счи­та­ет­ся, что пе­ре­да­ва­лась буква Р.

Среди при­ведённых ниже со­об­ще­ний най­ди­те то, ко­то­рое при­ня­то кор­рект­но, и ука­жи­те его рас­шиф­ров­ку (про­бе­лы не­су­ще­ствен­ны).
11011 11100 00011 11000 01110
00111 11100 11110 11000 00000

1) ПОТОП
2) РОТОР
3) ТОПОР
4) ни одно из со­об­ще­ний не при­ня­то кор­рект­но

Решение:
Длина обоих со­об­ще­ний крат­на пяти.
Ана­ли­зи­руя пер­вое со­об­ще­ние «11011 11100 00011 11000 01110», при­хо­дим к вы­во­ду, что оно при­ня­то не­кор­рект­но, по­сколь­ку нет та­ко­го слова, ко­то­рое бы от­ли­ча­лось от слова «01110» толь­ко в одной по­зи­ции.
Рас­смот­рим вто­рое со­об­ще­ние. Учи­ты­вая, что каж­дая пятёрка от­ли­ча­ет­ся от не­ко­то­ро­го ко­до­во­го слова не более чем в одной по­зи­ции, его воз­мож­но рас­шиф­ро­вать толь­ко как «ТОПОР».
Ответ: 3

Задача 6

Для пе­ре­да­чи дан­ных по ка­на­лу связи ис­поль­зу­ет­ся 5-би­то­вый код. Со­об­ще­ние со­дер­жит толь­ко буквы А, Б и В, ко­то­рые ко­ди­ру­ют­ся сле­ду­ю­щи­ми ко­до­вы­ми сло­ва­ми: А — 11010, Б — 10111, В — 01101.
При пе­ре­да­че воз­мож­ны по­ме­хи. Од­на­ко не­ко­то­рые ошиб­ки можно по­пы­тать­ся ис­пра­вить. Любые два из этих трёх ко­до­вых слов от­ли­ча­ют­ся друг от друга не менее чем в трёх по­зи­ци­ях. По­это­му если при пе­ре­да­че слова про­изо­шла ошиб­ка не более чем в одной по­зи­ции, то можно сде­лать обос­но­ван­ное пред­по­ло­же­ние о том, какая буква пе­ре­да­ва­лась. (Го­во­рят, что «код ис­прав­ля­ет одну ошиб­ку».) На­при­мер, если по­лу­че­но ко­до­вое слово 10110, счи­та­ет­ся, что пе­ре­да­ва­лась буква Б. (От­ли­чие от ко­до­во­го слова для Б толь­ко в одной по­зи­ции, для осталь­ных ко­до­вых слов от­ли­чий боль­ше.) Если при­ня­тое ко­до­вое слово от­ли­ча­ет­ся от ко­до­вых слов для букв А, Б, В более чем в одной по­зи­ции, то счи­та­ет­ся, что про­изо­шла ошиб­ка (она обо­зна­ча­ет­ся ‘х’).

По­лу­че­но со­об­ще­ние 11000 11101 10001 11111. Де­ко­ди­руй­те это со­об­ще­ние — вы­бе­ри­те пра­виль­ный ва­ри­ант.

1) АххБ
2) АВхБ
3) хххх
4) АВББ

Решение:
Де­ко­ди­ру­ем каж­дое слово со­об­ще­ния. Пер­вое слово: 11000 от­ли­ча­ет­ся от буквы А толь­ко одной по­зи­ци­ей. Вто­рое слово: 11101 от­ли­ча­ет­ся от буквы В толь­ко одной по­зи­ци­ей. Тре­тье слово: 10001 от­ли­ча­ет­ся от любой буквы более чем одной по­зи­ци­ей. Четвёртое слово: 11111 от­ли­ча­ет­ся от буквы Б толь­ко одной по­зи­ци­ей.
Таким об­ра­зом, ответ: АВхБ.
Ответ: 2

Однозначное декодирование. Условие Фано

Код называется однозначно декодируемым, если любое сообщение, составленное из кодовых слов, можно декодировать единственным способом.
Равномерное кодирование всегда однозначно декодируемо.
Для неравномерных кодов существует следующее достаточное (но не необходимое) условие однозначного декодирования:
Сообщение однозначно декодируемо с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова.
Сообщение однозначно декодируемо с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова.

Задача 7

Для пе­ре­да­чи по ка­на­лу связи со­об­ще­ния, со­сто­я­ще­го толь­ко из букв А, Б, В, Г, ре­ши­ли ис­поль­зо­вать не­рав­но­мер­ный по длине код: A=1, Б=01, В=001. Как нужно за­ко­ди­ро­вать букву Г, чтобы длина кода была ми­ни­маль­ной и до­пус­ка­лось од­но­знач­ное раз­би­е­ние ко­ди­ро­ван­но­го со­об­ще­ния на буквы?
1) 0001
2) 000
3) 11
4) 101

Решение:
Для анализа соблюдения условия однозначного декодирования (условия Фано) изобразим коды в виде дерева. Тогда однозначность выполняется, если каждая буква является листом дерева:

Видим, что ближайший от корня дерева свободный лист (т.е. код с минимальной длиной) имеет код 000.
Ответ: 2

Задача 8

Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв У, Ч, Е, Н, И и К, ис­поль­зу­ет­ся не­рав­но­мер­ный дво­ич­ный пре­фикс­ный код. Вот этот код: У — 000, Ч — 001, Е — 010, Н — 100, И — 011, К — 11. Можно ли со­кра­тить для одной из букв длину ко­до­во­го слова так, чтобы код по-преж­не­му остал­ся пре­фикс­ным? Коды осталь­ных букв ме­нять­ся не долж­ны.
Вы­бе­ри­те пра­виль­ный ва­ри­ант от­ве­та.
При­ме­ча­ние. Пре­фикс­ный код — это код, в ко­то­ром ни одно ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го; такие коды поз­во­ля­ют од­но­знач­но де­ко­ди­ро­вать по­лу­чен­ную дво­ич­ную по­сле­до­ва­тель­ность.
1) ко­до­вое слово для буквы Е можно со­кра­тить до 01
2) ко­до­вое слово для буквы К можно со­кра­тить до 1
3) ко­до­вое слово для буквы Н можно со­кра­тить до 10
4) это не­воз­мож­но

Решение:
Для анализа соблюдения условия однозначного декодирования (условия Фано) изобразим коды в виде дерева. Тогда однозначность выполняется, если каждая буква является листом дерева:

Легко заметить, что если букву Н перенести в вершину 10, она останется листом. Т.е. ко­до­вое слово для буквы Н можно со­кра­тить до 10.
Пра­виль­ный ответ ука­зан под но­ме­ром 3.
Ответ: 3

Задача 9

Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв К, Л, М, Н, ре­ши­ли ис­поль­зо­вать не­рав­но­мер­ный дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Для буквы Н ис­поль­зо­ва­ли ко­до­вое слово 0, для буквы К — ко­до­вое слово 110. Ка­ко­ва наи­мень­шая воз­мож­ная сум­мар­ная длина всех четырёх ко­до­вых слов?
1) 7
2) 8
3) 9
4) 10
При­ме­ча­ние. Усло­вие Фано озна­ча­ет, что ни­ка­кое ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го ко­до­во­го слова. Это обес­пе­чи­ва­ет воз­мож­ность од­но­знач­ной рас­шиф­ров­ки за­ко­ди­ро­ван­ных со­об­ще­ний.

Решение:
Для анализа соблюдения условия однозначного декодирования (условия Фано) изобразим коды в виде дерева. Тогда однозначность выполняется, если каждая буква является листом дерева:

Легко заметить, что ближайшие от корня свободные листы (т.е. свободные коды с наименьшей длиной) – это 10 и 111. Таким об­ра­зом, наи­мень­шая воз­мож­ная сум­мар­ная длина всех четырёх ко­до­вых слов будет 1 + 3 + 2 + 3 = 9.
Пра­виль­ный ответ ука­зан под но­ме­ром 3.
Ответ: 3

Задача 10

По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко че­ты­ре буквы: П, О, С, Т; для пе­ре­да­чи ис­поль­зу­ет­ся дво­ич­ный код, до­пус­ка­ю­щий од­но­знач­ное де­ко­ди­ро­ва­ние. Для букв Т, О, П ис­поль­зу­ют­ся такие ко­до­вые слова: Т: 111, О: 0, П: 100.
Ука­жи­те крат­чай­шее ко­до­вое слово для буквы С, при ко­то­ром код будет до­пус­кать од­но­знач­ное де­ко­ди­ро­ва­ние. Если таких кодов не­сколь­ко, ука­жи­те код с наи­мень­шим чис­ло­вым зна­че­ни­ем.

Решение:
Для анализа соблюдения условия однозначного декодирования (условия Фано) изобразим коды в виде дерева. Тогда однозначность выполняется, если каждая буква является листом дерева:

Легко заметить, что ближайшие от корня свободные листы (т.е. свободные коды с наименьшей длиной) – это 101 и 110. Наименьшее числовое значение имеет код 101.
Ответ: 101