В сообщении встречается 7 разных букв: Информатик БУ - В сообщении встречается 7 разных букв. П...

Задача №5. Кодирование в различных системах счисления, расшифровка сообщений, выбор кода.

Автор материалов — Лада Борисовна Есакова.

Кодирование – это перевод информации, представленной символами первичного алфавита, в последовательность кодов.

Декодирование (операция, обратная кодированию) – перевод кодов в набор символов первичного алфавита.

Кодирование может быть равномерное и неравномерное. При равномерном кодировании каждый символ исходного алфавита заменяется кодом одинаковой длины. При неравномерном кодировании разные символы исходного алфавита могут заменяться кодами разной длины.

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

Равномерное кодирование всегда однозначно декодируемо.

Для неравномерных кодов существует следующее достаточное (но не необходимое) условие однозначного декодирования:

Сообщение однозначно декодируемо с начала, если выполняется

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

Сообщение однозначно декодируемо с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова.

Кодирование в различных системах счисления

Пример 1.

Для кодирования букв О, В, Д, П, А решили использовать двоичное представление

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

1) 22162

2) 1020342

3) 2131453

4) 34017

Решение:

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

О	В	Д	П	А
0	1	2	3	4
00	01	10	11	100

Закодируем последовательность букв: ВОДОПАД — 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 0110₂ = D3A6₁₆

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

Ответ: 1

Расшифровка сообщений

Пример 3.

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

a	b	c	d	e
100	110	011	01	10

Определите, какой набор букв закодирован двоичной строкой 1000110110110, если известно, что все буквы в последовательности – разные:

1) cbade

2) acdeb

3) acbed

4) bacde

Решение:

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

Значит, будем перебирать варианты, пока не получим подходящее слово :

1) 100 011 01 10 110

Первая буква определяется однозначно, её код 100: a.

Пусть вторая буква — с, тогда следующая буква — d, потом — e и b.

Такой вариант удовлетворяет условию, значит, окончательно получили ответ: acdeb.

Ответ: 2

Пример 4.

Для передачи данных по каналу связи используется 5-битовый код. Сообщение содержит только буквы А, Б и В, которые кодируются следующими кодовыми словами: А — 11010, Б — 10111, В — 01101.

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

(Говорят, что «код исправляет одну ошибку».) Например, если получено кодовое слово 10110, считается, что передавалась буква Б. (Отличие от кодового слова для Б только в одной позиции, для остальных кодовых слов отличий больше.) Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка (она обозначается ‘х’).

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

1) АххБ

2) АВхБ

3) хххх

4) АВББ

Решение:

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

Таким образом, ответ: АВхБ.

Ответ:

Однозначное кодирование

Пример 5.

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

1) 0001

2) 000

3) 11

4) 101

Решение:

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

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

Ответ: 2

Пример 6.

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

Выберите правильный вариант ответа.

Примечание. Префиксный код — это код, в котором ни одно кодовое слово не является началом другого; такие коды позволяют однозначно декодировать полученную двоичную последовательность.

1) кодовое слово для буквы Е можно сократить до 01

2) кодовое слово для буквы К можно сократить до 1

3) кодовое слово для буквы Н можно сократить до 10

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

Решение:

Легко заметить, что если букву Н перенести в вершину 10, она останется листом.

Т.е. кодовое слово для буквы Н можно сократить до 10.

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

Ответ: 3

Благодарим за то, что пользуйтесь нашими публикациями. Информация на странице «Задача №5. Кодирование в различных системах счисления, расшифровка сообщений, выбор кода.» подготовлена нашими редакторами специально, чтобы помочь вам в освоении предмета и подготовке к экзаменам. Чтобы успешно сдать необходимые и поступить в ВУЗ или колледж нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий. Также вы можете воспользоваться другими материалами из данного раздела.

Публикация обновлена: 08.03.2023

Задачи для подготовки к ЕГЭ по информатике

Кодирование. Правило Фано. Передача данных с ошибками

Типы только для начальной подготовки (не нужно тренировать для экзамена):

Правило Фано ( 16 )
Подобрать код для новой буквы, чтобы допускалось однозначное декодирование.
Правило Фано и длительность сообщения ( 18 )