Передача информации. Выбор кода.

Передача информации. Выбор кода

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

Примечание.

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

Решение.

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

 

Ответ: 9.

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

 

1) для буквы Г — 11

2) для буквы В — 00

3) для буквы Г — 01

4) это невозможно

Решение.

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

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

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

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

Решение.

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

 

Ответ: 14.

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

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

Решение.

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

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

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

Решение.

Буква С не может кодироваться строкой, которая начинается с 0, поскольку О имеет код 0.

Буква С не может кодироваться как 1, так как кодирование буквы Т начинается с 1.

Буква С не может кодироваться как 10, так как кодирование буквы П начинается с 10.

Буква С не может кодироваться как 11, так как кодирование буквы Т начинается с 11.

Буква С может кодироваться как 101 − это наименьшее возможное значение.

 

Ответ: 101.

6. По каналу связи передаются сообщения, содержащие только пять букв: A, B, С, D, E. Для передачи используется двоичный код, допускающий однозначное декодирование. Для букв A, B, C используются такие кодовые слова:

A – 1, B – 010, C – 000.

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

Решение.

Буква E не может кодироваться как 0, так как кодирование буквы B начинается с 0.

Буква E не может кодироваться как 1, так как это кодирование буквы А.

Буква E не может кодироваться как 10 и 11 − так как кодирование буквы А — 1.

Буква E не может кодироваться как 01 и 00 — так как кодирование буквы B начинается с 01, а кодирование буквы C с 00. Буква E может кодироваться как 001 — это наименьшее возможное значение.

 

Ответ: 001.

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

любые два слова из набора отличаются не менее чем в трёх позициях.

Это свойство важно для расшифровки сообщений при наличии помех. Для кодирования букв П, Р, С используются 5-битовые кодовые слова: П: 01111, Р: 00001, С: 11000. 5-битовый код для буквы Т начинается с 1 и заканчивается на 0. Определите кодовое слово для буквы Т.

Решение.

Код Т начинается с 1 и заканчивается на 0. Код С также начинается с 1 и заканчивается на 0. Поэтому для того, чтобы коды отличались не менее чем в трёх позициях, нужно, чтобы в остальных позициях все цифры были разные. И раз у С в середине 100, то у Т должно быть 011. Итого получили код 10110.

8. По каналу связи с помощью равномерного двоичного кода передаются сообщения, содержащие только 4 буквы А, Б, В, Г. Каждой букве соответствует своё кодовое слово, при этом для набора кодовых слов выполнено такое свойство:

любые два слова из набора отличаются не менее чем в трёх позициях.

Это свойство важно для расшифровки сообщений при наличии помех. Для кодирования букв Б, В, Г используются 5-битовые кодовые слова: Б: 00001, В: 01111, Г: 10110. 5-битовый код для буквы А начинается с 1 и заканчивается на 0. Определите кодовое слово для буквы А.

Решение.

Код А начинается с 1 и заканчивается на 0. Код Г также начинается с 1 и заканчивается на 0. Поэтому для того, чтобы коды отличались не менее чем в трёх позициях, нужно, чтобы в остальных позициях все цифры были разные. И раз у Г в середине 011, то А Т должно быть 100. Итого получили код 11000.

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

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

Решение.

Перечислим возможные коды в порядке возрастания длины. Стоит сразу сказать, что любой код, начинающийся с 0, не подходит, так как код А - 0, поэтому смотрим только на те, что начинаются с 1.

1 - нельзя, Б, В начинаются с 1.

10 - нельзя из-за Б.

11 - нельзя из-за В.

111 - можно использовать, пусть это будет код Д.

100 - также можно использовать, но если мы его возьмём, то не будет больше кодов, которые можно будет взять, так как все коды, начинающиеся с 0, уже нельзя брать, а все коды, начинающиеся с 1 и имеющие длину больше трёх, начинаются с одной из этих строк: 100, 101, 110, 111.

Рассмотрели все коды с длинами от 1 до 3, поэтому теперь достаточно взять любые два подходящие кода длины 4. Например, 1000 и 1001.

В сумме длина кодов 1 + 3 + 3 + 3 + 4 + 4 = 18.

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

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

Решение.

Перечислим возможные коды в порядке возрастания длины. Стоит сразу сказать, что любой код, начинающийся с 1, не подходит, так как код А - 1, поэтому смотрим только на те, что начинаются с 0.

0 - нельзя, Б, В начинаются с 0.

01 - нельзя из-за Б.

00 - нельзя из-за В.

000 - можно использовать, пусть это будет код Д.

011 - также можно использовать, но если мы его возьмём, то не будет больше кодов, которые можно будет взять, так как все коды, начинающиеся с 1, уже нельзя брать, а все коды, начинающиеся с 0 и имеющие длину больше трёх, начинаются с одной из этих строк: 011, 010, 001, 000.

Рассмотрели все коды с длинами от 1 до 3, поэтому теперь достаточно взять любые два подходящие кода длины 4. Например, 0111 и 0110.

В сумме длина кодов 1 + 3 + 3 + 3 + 4 + 4 = 18.

11. Для кодирования некоторой последовательности, состоящей из букв А, Б, В и Г, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В используются такие кодовые слова: А — 000, Б — 1, В — 011.

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

Решение.

Код не может начинаться с 1, так как Б − 1.

0 не подойдёт, так как А и В начинаются с 0.

Двоичные коды 00 или 01 не подходят, поскольку А и В — 000 и 011.

010 и 001 подойдут, так как не конфликтуют ни с каким другим уже имеющимся кодом, из них 001 меньше.

 

Ответ: 001.

12. Для кодирования некоторой последовательности, состоящей из букв А, Б, В и Г, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В используются такие кодовые слова: А — 010, Б — 1, В — 011.

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

Решение.

Код не может начинаться с 1, так как Б − 1.

0 не подойдёт, так как А и В начинаются с 0.

00 же не включает в себя никакой из кодов и также не является подстрокой какого-либо кода, поэтому подойдёт.

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

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

 

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

Решение.

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

 

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

 

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

 

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

 

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

 

Ответ: 101.

14. По каналу связи передаются сообщения, содержащие только шесть букв: А, 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.

 

Ответ: 20.

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

 

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

Решение.

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

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

 

 

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

 

Ответ: 20.

16. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10. Какова наименьшая возможная сумма длин всех шести кодовых слов?

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

Решение.

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

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

 

 

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

 

Ответ: 19.

17. Для кодирования растрового рисунка, напечатанного с использованием шести красок, применили неравномерный двоичный код. Для кодирования цветов используются кодовые слова.

 

 

Цвет Кодовое слово Белый 0 Зелёный 11111 Красный 1110

Цвет Кодовое слово Синий Фиолетовый 11110 Чёрный 10

 

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

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

Решение.

Подберём кодовое слово для синего цвета. Заметим, что кодовые слова 1 и 10 использовать нельзя, так как они уже заняты. Попробуем трёхзначные кодовые слова. Можно использовать только кодовое слово 110.

 

Ответ: 110.

18. По каналу связи с помощью равномерного двоичного кода передаются сообщения, содержащие только 4 буквы: Ц, Ч, Ш, Щ; для кодировки букв используются кодовые слова длины 5. При этом для набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях . Это свойство важно для расшифровки сообщений при наличии помех. Для кодирования букв Ц, Ч, Ш используются 5-битовые кодовые слова: Ц: 01111, Ч: 00001, Ш: 11000. 5-битовый код для буквы Щ начинается с 1 и заканчивается 0. Определите кодовое слово для буквы Щ.

Решение.

Заметим, что буква Ш также начинается на 1 и заканчивается на 0, значит, для выполнения условия нужно, чтобы все остальные 3 бита в Ш и Щ отличались. Поскольку в Ш эти три бита — 100, то в Щ они будут 011, соответственно. Тогда Щ: 10110.

 

Ответ: 10110.

19. По каналу связи с помощью равномерного двоичного кода передаются сообщения, содержащие только 4 буквы: К, Л, М, Н; для кодировки букв используются кодовые слова длины 5. При этом для набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Для кодирования букв К, Л, М используются 5-битовые кодовые слова: К: 11100, Л: 01111, М: 00001. 5-битовый код для буквы Н начинается с 1 и заканчивается 0. Определите кодовое слово для буквы Н.

Решение.

Заметим, что буква K также начинается на 1 и заканчивается на 0, значит, для выполнения условия нужно, чтобы все остальные 3 бита в K и Н отличались. Поскольку в К эти три бита — 110, то в Н они будут 001, соответственно. Тогда Н: 10010.

 

Ответ: 10010.

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

Решение.

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

 

Ответ: 010.

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

Решение.

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

 

Ответ: 010.

 

Примечание.

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

 

 

----------

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

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

Решение.

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

Ответ: 1000.