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

1.

2.

Кодирование - представление информации с помощью некоторого
кода, это переход от одной формы представления информации к
другой, более удобной для хранения, передачи или обработки.
? Зачем кодируют информацию?
кодирование
данные (код)
Информация передается,
обрабатывается и хранится в
виде кодов.
10101001010
передача
данные (код)
11111100010
борьба с помехами
(специальные способы
кодирования)
передача
обработка
хранение

3.

4.

Задача 1. Закодируйте свое имя с помощью азбуки Морзе.
ВАСЯ
! Код неравномерный, нужен разделитель!

5.

Задача 2. Закодируйте свое имя с помощью кодовой
таблицы (Windows-1251):
0 1 2 3 4 5 6 7 8 9 A B C D E F
C А Б В Г Д Е Ж З И Й К Л М Н О П
D Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я
ВАСЯ
В
С2
А
С0
С
Я
D1 DF
! Код равномерный, разделитель НЕ нужен!

6.

Текст:
в России: Привет, Вася!
Windows-1251: CFF0E8E2E52C20C2E0F1FF21
передача за рубеж (транслит): Privet, Vasya!
стенография:
шифрование: Рсйгжу-!Гбта”
Числа:
для вычислений: 25
прописью: двадцать пять
римская система: XXV
? Как зашифровано?
! Информация (смысл сообщения) может
быть закодирована разными способами!

7.

символы
рисунки
кодировщик
101011011101110110101
•в такой форме можно закодировать (почти) все виды
информации
•нужны только устройства с двумя состояниями
•почти нет ошибок при передаче данных
•компьютеру легче обрабатывать данные
человеку сложно воспринимать двоичные коды
? Можно ли использовать не «0» и «1», а другие
символы, например, «А» и «Б»?

8.

Декодирование – это восстановление сообщения из
последовательности кодов.
М
А
Ы
Л
У
пробел
00
1
01
0
10
11
МАМА МЫЛА ЛАМУ → 00 1 00 1 11 00 01 0 1 11 0 1
00 10
Приняли сообщение:
0010011100010111010010 ???
ЛЛАЛЛАААЛЛЛАЛАА
АЛАЛЛАЛ
Не все коды допускают однозначное
декодирование!
!

9.

Пример 1.
Ваня шифрует русские слова, записывая вместо каждой буквы ее
номер в алфавите (без пробелов). Номера букв даны в таблице.
А
Б
В
Г
Д
Е
Ё
Ж
З
1
2
3
4
5
6
7
8
9
И
Й
К
Л
М
Н
О
П
Р
10
11
12
13
14
15
16
17
18
С
Т
У
Ф
Х
Ц
Ч
Ш
Щ
19
20
21
22
23
24
25
26
27
Ь
Ы
Ъ
Э
Ю
Я
28
29
30
31
32
33
Некоторые шифровки можно расшифровать несколькими способами.
Например, 311333 может означать «ВАЛЯ», может «ЭЛЯ», а может
«ВААВВВ».
Даны четыре шифровки: 3113 9212 6810 2641
Найдите ту, которая расшифровывается единственным способом.

10.

Решение задачи:
А
Б
В
Г
Д
Е
Ё
Ж
З
1
2
3
4
5
6
7
8
9
И
Й
К
Л
М
Н
О
П
Р
10
11
12
13
14
15
16
17
18
С
Т
У
Ф
Х
Ц
Ч
Ш
Щ
19
20
21
22
23
24
25
26
27
Ь
Ы
Ъ
Э
Ю
Я
28
29
30
31
32
33
Шифровки: 3113 9212 6810 2641
1) 3113: Поскольку в алфавите 33 буквы, то либо первая цифра 3 означает букву В,
либо первым стоит число 31 (буква Э). Следующие цифры 1 и 3 могут быть либо
одним числом (буква Л), либо двумя отдельными (буквы А и В). Таким образом,
первая запись имеет варианты: ВААВ, ЭАВ, ЭЛ. Не подходит.
2) 9212: Во второй записи цифра 9 – это буква З. Далее могут быть варианты – 2-1-2,
2-12 и 21-2, что не удовлетворяет условию задачи.
3) 6810: В последней записи 6810 первая цифра 6 имеет однозначное решение –
буква Е (номера 68 в таблице нет). Далее аналогично может стоять только номер 8
(буква Ж). Последние две цифры 10 могут означать только букву И, поскольку буквы
с номером 0 в таблице нет.
4) 2641: 26 может означать Ш, а может означать БЕ. Тоже не подходит.
Ответ: ЕЖИ.

11.

Пример 2.
Валя шифрует русские слова (последовательности букв),
записывая вместо каждой буквы её код:
А
Д
К
Н
О
С
01 100 101 10 111 000
Некоторые цепочки можно расшифровать не одним
способом. Например, 00010101 может означать не только
СКА, но и СНК. Даны три кодовые цепочки:
100101000
101111100
100111101
Найдите среди них ту, которая имеет только одну
расшифровку, и запишите в ответе расшифрованное слово.

12.

Решение задачи:
А
01
Д
К
100 101
Н
10
О
С
111 000
1) В первой цепочке 100101000 на конце может быть только буква
С (000). Оставшаяся часть 100101 может быть расшифрована
двояко: 10-01-01 или 100-101, поэтому этот вариант не подходит.
2) Во второй цепочке 101111100 на конце может быть только
буква Д (100). Оставшаяся часть 101111 может быть расшифрована
только одним способом: 101-111 (КО), поскольку если в начале
будет стоять буква Н (10), то далее может быть только буква О (111)
и тогда остается одна цифра 1, а такой буквы в условии нет.
Цепочка удовлетворяет условию задачи.
3) Проверим 100111101. В ней может быть два варианта
расшифровки: 100-111-101 или 10-01-111-01.
Поэтому эта цепочка не может быть ответом.
Ответ: КОД.

13.

Пример 3.
Мальчики играли в шпионов и кодировали сообщения собственным
шифром. Фрагмент кодовой таблицы приведён ниже:
К
Л
М
П
@+
~+
+@ @~+
О
И
+
~
Расшифруйте сообщение, если известно, что буквы в нём не
повторяются:
+~+~+@@~+
Запишите в ответе расшифрованное сообщение.

14.

Решение задачи:
К
Л
М
П
О
И
@+
~+
+@
@~+
+
~
+~+~+@@~+
В начале цепочки стоит однозначно читаемый символ, это " +
" (О). Рассматриваем цепочку далее " ~ + ~+@@~ + ".
Поскольку по условию задачи все буквы в шифровке разные,
то цепочку нельзя разбить на отдельные символы "~" и " + " .
Значит, следующей буквой может быть только Л (~ +). Далее
может идти только буква И (~). Следующая буква также
однозначно читаемая, это М (+ @).
И остаются символы "@ ~ +" , это буква П.
Ответ: ОЛИМП

15.

Пример 4.
От разведчика была получена следующая шифрованная радиограмма,
переданная с использованием азбуки Морзе:
– –•– – – – –•••– – –•–•–
При передаче радиограммы было потеряно разбиение на буквы, но
известно, что в радиограмме использовались только следующие буквы:
А
Г
М
К
Ю
•–
– –
––
–•–
••– –
Расшифруйте радиограмму. Запишите в ответе расшифрованную
радиограмму.
Решение: выделяем буквы согласно таблице.
нет в таблице
– –•– – – – –•••–––•–•–
– –•– – – – –•••–––•–•–
Ответ: МАМГЮКА

16.

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

17.

Решение
1. Представим данные в условии числа в виде
двоичного кода:
О
0
00
В
1
01
Д
2
10
П
3
11
А
4
100
2. Закодируем последовательность букв
ВОДОПАД = 01 00 10 00 11 100 10
3. Разобьем это представление на тройки справа
налево, переведя полученный набор в
восьмеричный код:
010 010 001 110 010 = 22162.

18.

Задача 1.
Олеся шифрует слова, записывая вместо каждой буквы её номер в алфавите
(без пробелов). Номера букв даны в таблице:
А1
Й 11
У 21
Э 31
Б2
К 12
Ф 22
Ю 32
В3
Л 13
Х 23
Я 33
Г4
М 14
Ц 24
Д5
Н 15
Ч 25
Е6
О 16
Ш 26
Ё7
П 17
Щ 27
Ж8
Р 18
Ъ 28
З9
С 19
Ы 29
И 10
Т 20
Ь 30
Некоторые шифровки можно расшифровать несколькими способами.
Например, 12112 может означать «АБАК», может — «КАК», а может —
«АБААБ». Даны четыре шифровки: 20335 21120 31321 51201
Только одна из них расшифровывается единственным способом. Найдите её
и расшифруйте. То, что получилось, запишите в качестве ответа.

19.

Задача 2
Кира шифрует русские слова (последовательности
букв), записывая вместо каждой буквы её код:
А
Д
К
Н
О
С
01 100 101 10 111 000
Некоторые цепочки можно расшифровать не одним
способом. Например, 00010101 может означать не
только СКА, но и СНК. Даны три кодовые цепочки:
10111101 00011110 100111101
Найдите среди них ту, которая имеет только одну
расшифровку, и запишите в ответе расшифрованное
слово.

20.

Задача 3
Никита и Даниил играли в шпионов и кодировали
сообщения собственным шифром. Фрагмент
кодовой таблицы приведён ниже:
Н
М
Л
И
Т
О
~
*
*@ @~* @* ~*
Расшифруйте сообщение, если известно, что буквы в
нём не повторяются: *@@~**~*~
Запишите в ответе расшифрованное сообщение.

21.

Задача 4
От разведчика была получена следующая
шифрованная радиограмма, переданная с
использованием азбуки Морзе:
••-•••-•--•-••••При передаче радиограммы было потеряно
разбиение на буквы, но известно, что в радиограмме
использовались только следующие буквы:
Т
А
У
-
•-
••-
Ж
Х
•••- •••
Определите текст радиограммы

22.

Задача 5
От разведчика было получено сообщение:
100001110010111001100
В этом сообщении зашифрован пароль – последовательность
русских букв. В пароле использовались только буквы А, Б, К, Л, О,
С; каждая буква кодировалась двоичным словом по таблице,
показанной на рисунке. Расшифруйте сообщение. Запишите в
ответе пароль.
Задача 6
Стёпа и Ксюша играли в разведчиков и закодировали сообщение
придуманным шифром. В сообщении присутствуют только буквы
из приведённого фрагмента кодовой таблицы.
С
М
А
О
Р
К
ΛΩΩ ΩΛ ΩΩ ΩΩΛ ΛΩΛ ΩΛΩ
Определите, какое сообщение закодировано
строчке ΛΩΛΩΩΛΩΛΩ
в

23.

Задача 7.
Для кодирования букв Р, С, Н, О, Г решили использовать
двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с
сохранением одного незначащего нуля в случае
одноразрядного представления). Закодируйте
последовательность букв НОСОРОГ таким способом и
результат запишите восьмеричным кодом.
Задача 8.
Для кодирования букв А, Б, В, Г решили использовать
двухразрядные последовательные двоичные числа (от 00 до
11, соответственно). Закодируйте таким образом
последовательность символов ББГА и запишите полученное
двоичное число в шестнадцатеричной системе счисления.

24.

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

25.

Задача 10*.
Для кодирования некоторой последовательности, состоящей из букв И, К,
Л, М, Н, решили использовать неравномерный двоичный код,
удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово
0, для буквы К – кодовое слово 10. Какова наименьшая возможная суммарная
длина всех пяти кодовых слов?
Примечание. Условие Фано означает, что никакое кодовое слово не
является началом другого кодового слова. Это обеспечивает возможность
однозначной расшифровки закодированных сообщений.
Задача 11*.
Для кодирования некоторой последовательности, состоящей из букв А, Б,
В и Г, решили использовать неравномерный двоичный код, позволяющий
однозначно декодировать двоичную последовательность, появляющуюся на
приёмной стороне канала связи. Для букв А, Б, В используются такие кодовые
слова: А — 000, Б — 1, В — 011.
Укажите кратчайшее кодовое слово для буквы Г, при котором код будет
допускать однозначное декодирование. Если таких кодов несколько, укажите
код с наименьшим числовым значением.