Кодирование и декодирование информации

Задача 1.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–10, Б–001, В–0001, Г–110, Д–111.
Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
1) это невозможно
2) для буквы В – 000
3) для буквы Б – 0
4) для буквы Г – 11

В секундах.
Задача 1.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Решение.
Мы видим, что выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова, поэтому однозначно можем раскодировать сообщение с начала.
Чтобы сократить код одной буквы, необходимо выполнение условия Фано в новом коде.
Вариант 1 оставляем, пока не проверим остальные.
Вариант 2 подходит, так как не нарушает условия Фано.
Вариант 3 не подходит, потому что 0 является началом кода 0001.
Вариант 4 не подходит, потому что код 11 является началом кода 111.
Правильный ответ указан под номером 2.
Ответ 2

Рассмотрим варианты ответов.
1) ОК. Разбивать на части нужно так: 11 и 2. Возможные исходные 618 и 318.
2) Не подходит. Разбить на части можно только так: 21 и 11. Число 218 нельзя получить, как сумму однозначных восьмеричных чисел. (нарушено условие в2).
3) Не подходит. Цифра 9 не может встречаться в восьмеричном числе.
4) Не подходит. Разбить на части можно только так: 2 и 7. При этом 2 > 7 (нарушено условие в3 - первое число должно быть больше второго)
Правильный ответ: 1
Задача 2.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
По каналу связи передаются сообщения, содержащие только 4 буквы:
А, И, С, Т.
В любом сообщении больше всего букв А, следующая по частоте буква — С, затем — И. Буква Т встречается реже, чем любая другая.
Для передачи сообщений нужно использовать неравномерный двоичный код, допускающий однозначное декодирование; при этом сообщения должны быть как можно короче. Шифровальщик может использовать один из перечисленных ниже кодов. Какой код ему следует выбрать?
1) А−0, И−1, С−00, Т−11
2) С−1, И−0, А−01, Т−10
3) А−1, И−01, С−001, Т−000
4) С−0, И−11, А−101, Т−100

В секундах.
Задача 2.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Решение.
Выберем коды, для которых выполнено условие Фано. Это коды 3 и 4. Чтобы сообщение было как можно короче, необходимо, чтобы чем чаще встречалась буква, тем короче был ее код.
Следовательно, ответ 3, поскольку буква А — самая часто встречающаяся буква и для ее кодирования в варианте 3 используется один символ.
Ответ 3

Рассмотрим варианты ответов.
1) ОК. Разбивать на части нужно так: 11 и 2. Возможные исходные 618 и 318.
2) Не подходит. Разбить на части можно только так: 21 и 11. Число 218 нельзя получить, как сумму однозначных восьмеричных чисел. (нарушено условие в2).
3) Не подходит. Цифра 9 не может встречаться в восьмеричном числе.
4) Не подходит. Разбить на части можно только так: 2 и 7. При этом 2 > 7 (нарушено условие в3 - первое число должно быть больше второго)
Правильный ответ: 1
Задача 3.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Для кодирования букв О, В, Д, П, А решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если закодировать последовательность букв ВОДОПАД таким способом и результат записать восьмеричным кодом, то получится
1) 22162
2) 1020342
3) 2131453
4) 34017

В секундах.
Задача 3.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Решение.
Сначала следует представить данные в условии числа в двоичном коде:
Затем закодировать последовательность букв:
ВОДОПАД — 01-00-10-00-11-100-10.
Теперь разобьём это представление на тройки справа налево и переведём полученный набор чисел в десятичный код, затем в восьмеричный (восьмеричное представление совпадает с десятичным при разбиении тройками, воспользуемся таблицей из А1)
010-010-001-110-010 — 22162.
Правильный ответ указан под номером 1.
Ответ 1
«сохранение одного незначащего нуля в случае одноразрядного представления»

Рассмотрим варианты ответов.
1) ОК. Разбивать на части нужно так: 11 и 2. Возможные исходные 618 и 318.
2) Не подходит. Разбить на части можно только так: 21 и 11. Число 218 нельзя получить, как сумму однозначных восьмеричных чисел. (нарушено условие в2).
3) Не подходит. Цифра 9 не может встречаться в восьмеричном числе.
4) Не подходит. Разбить на части можно только так: 2 и 7. При этом 2 > 7 (нарушено условие в3 - первое число должно быть больше второго)
Правильный ответ: 1
Задача 4.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
По каналу связи передаются сообщения, содержащие только 5 букв А, И, К, О, Т. Для кодирования букв используется неравномерный двоичный код с такими кодовыми словами:
А — 0, И — 00, К — 10, О — 110, Т — 111.
Среди приведённых ниже слов укажите такое, код которого можно декодировать только одним способом. Если таких слов несколько, укажите первое по алфавиту.
1) КАА
2) ИКОТА
3) КОТ
4) ни одно из сообщений не подходит

В секундах.
Задача 4.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Решение.
Закодируем каждое слово.
КАА — 1000
ИКОТА — 00101110
КОТ — 10110111
Слово КАА можно декодировать как КИ
Слово ИКОТА можно декодировать как ААКОТА
Слово КОТ никак нельзя декодировать по-другому.
Следовательно, ответ 3.
Ответ 3

Вопросы.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
По каналу связи передаются сообщения, содержащие только 4 буквы: П, О, Р, T. Для кодирования букв П, О, Р используются 5-битовые кодовые слова: П — 11111, О — 11000, Р — 00100.
Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трех позициях.
Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы T, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?
1) 00000
2) 11100
3) 00011
4) не подходит ни одно из указанных слов
Ответ 3

Вопросы.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
По каналу связи передаются сообщения, содержащие только 4 буквы: А, Т, О, М; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, М используются такие кодовые слова: Т: 100, О: 00, М: 11. Укажите такое кодовое слово для буквы А, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите тот, у которого меньшая длина.
1) 1
2) 0
3) 01
4) 101
Ответ 3

Вопросы.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Для кодирования букв И, Д, Т, О, X решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если закодировать последовательность букв ТИХОХОД таким способом и результат записать шестнадцатеричным кодом, то получится
1) CD89
2) 89CD
3) 3154542
4) 2043431
Ответ 2