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

1.

Презентация 10-2
КОДИРОВАНИЕ ИНФОРМАЦИИ

2.

ЧТО ТАКОЕ ИНФОРМАЦИЯ?
С позиции человека информация – это содержание
сообщений, это самые разнообразные сведения,
которые человек получает из окружающего мира
через свои органы чувств.

3.

ЧТО ТАКОЕ ИНФОРМАЦИЯ?
Компьютер работает с битами, с двоичными кодами .
Компьютер не вникает в смысл информации.
Информацию, циркулирующую в устройствах
компьютера правильнее назвать данными.

4.

ШИФРОВАНИЕ. ДЕШИФРОВАНИЕ.
Шифрование – процесс применения шифра к
защищаемой информации, то есть преобразование
защищаемой информации в шифрованное сообщение
с помощью определенных правил, содержащихся в
шифре.
Дешифрование – процесс, обратный шифрованию, то
есть преобразование шифрованного сообщения в
защищаемую информацию с помощью определенных
правил, содержащихся в шифре.

5.

КЛАССИЧЕСКИЕ ШИФРЫ
Большое влияние на развитие криптографии оказали
появившиеся в середине прошлого века работы
американского математика Клода Шеннона. В этих
работах были заложены основы теории информации.
В своей работе «Математическая теория секретной
связи» Клод Шеннон обобщил накопленный до него
опыт разработки шифров. Оказалось, что даже в
сложных шифрах в качестве типичных компонентов
можно выделить шифры замены, шифры
перестановки или их сочетания.

6.

КЛАССИЧЕСКИЕ ШИФРЫ
Шифрами перестановки называются такие шифры,
преобразования из которых приводят к изменению
только порядка следования символов исходного
сообщения. Обычно открытый текст разбивается на
отрезки равной длины и каждый отрезок шифруется
независимо.
Шифрами замены называются такие шифры,
преобразования из которых приводят к замене
каждого символа открытого сообщения на другие
символы – шифробозначения, причем порядок
следования шифробозначений совпадает с порядком
следования соответствующих им символов открытого
сообщения.

7.

КЛАССИЧЕСКИЕ ШИФРЫ
Самые важные составляющие любого шифра – это
• общее правило, по которому преобразуется
исходный текст (алгоритм шифра);
• конкретная особенность именно этой серии
шифрованных сообщений (так называемый ключ).

8.

Задание

9.

Задание

10.

ДВОИЧНОЕ КОДИРОВАНИЕ
Двоичное кодирование – представление информации
с помощью двоичного алфавита.
0/1
+/-
хорошо/
плохо
Двоичный
алфавит
истина/
ложь
да/нет
А/Б
Примеры символов двоичного алфавита

11.

Двоичные коды
Равномерные
Неравномерные
Одинаковое число
символов в кодовых
комбинациях
Различное число
символов в кодовых
комбинациях

12.

ЗАДАЧА 1
Пусть для кодирования фразы «Доброе утро» выбран
такой код:
Д
О
Б
Р
Е
У
Т
Пробел
111 000
00
1
01
0
10
11

13.

Д
О
Б
Р
Е
У
Т
Пробел
111 000
00
1
01
0
10
11
Коды букв «сцепляются» в единую битовую строку и
передаются, например, по сети:
Доброе утро → 11100000100001110101000
В пункте назначения возникает проблема – как
восстановить исходное сообщение, и возможно ли это.
Раскодировать данное сообщение можно разными
способами. В том числе предположим, что оно состоит
только из букв Р – 1 и У – 0.
Тогда получим РРРУУУУУРУУУУРРРУРУРУУУ, т.е.
бессмысленный набор букв.

14.

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

15.

ЗАДАЧА 2
Равномерные коды. Для той же фразы используем
равномерный код:
Д
О
Б
Р
Е
111 000 001 101 011
У
Т
Пробел
010 100 110

16.

Равномерные коды неэкономичны – гораздо длиннее
неравномерных. Это приводит к усложнению
кодирования, но при этом они раскодируются
однозначно, что, естественно, облегчает задачу.
Чтобы сократить длину сообщения, можно
попробовать применить неравномерный код, т.е. код,
в котором кодовые слова, соответствующие разным
символам исходного алфавита, могут иметь разную
длину, от одного до нескольких символов.

17.

ЗАДАЧА 3
Используем следующий код:
Д
О
Б
Р
01
00
1011
100
Е
У
Т
Пробел
1010 1101 1110 1111
0100101110000101011111101111010000
Эта битовая цепочка декодируется однозначно.
Первая буква – Д (код 01), т.к. ни одно другое кодовое
слово не начинается с 01.
Вторая буква – О (код 00). Никакое другое слово не
начинается с 00.
Это же свойство, которое называется условием Фано,
выполняется и для кодовых слов других букв.

18.

УСЛОВИЕ ФАНО
Никакое кодовое слово не может быть
началом другого кодового слова.
Такие коды называются префиксными
(раскодируются с начала сообщения) и
декодируются однозначно.

19.

УСЛОВИЕ ФАНО
Примером кода, удовлетворяющего условию Фано,
являются телефонные номера в традиционной телефонии.
Если в сети существует номер 101, то номер 1012345 не
может быть выдан: при наборе трёх цифр АТС прекращает
понимать дальнейший набор и соединяет с адресатом по
номеру 101.
Однако для набора с сотового телефона это правило уже не
действует, потому что требуется явное завершение
последовательности знаков соответствующей кнопкой
(обычно – с изображением зелёной трубки), при этом 101,
1010 и 1012345 могут одновременно пониматься как
разные адресаты.

20.

ЗАДАЧА
ЗАДАЧА44
Рассмотрим ещё один код:
Д О
Б
Р
Е
У
Т
Пробел
10 00 1011 001 0101 1000 0111 1111
Он не является префиксным, т.к. код буквы Д (10) совпадает
с началом кода буквы Б (1011), У(1000) и код буквы О(00)
совпадает с началом кода буквы Р (001).

21.

Д О
Б
Р
Е
У
Т
Пробел
10 00 1011 001 0101 1000 0111 1111
Закодируем наше сообщение:
ДОБРОЕ УТРО → 10 00 1011 001 00 0101 1111 1000
0111 001 00
Начнём раскодировать с начала. Первая – Д, или У, а
дальше идут вообще разные варианты: Р или Б… Т.е.
надо «заглядывать» вперёд, что очень неудобно.

22.

ОБРАТНОЕ УСЛОВИЕ ФАНО
Попробуем раскодировать сообщение с конца – оно
однозначно декодируется! Выполняется обратное
условие Фано:
никакое кодовое слово не совпадает
с окончанием другого кодового слова.
Коды, для которых выполняется обратное условие Фано,
называются постфиксными.

23.

СДЕЛАЕМ ВЫВОД:
Сообщение декодируется однозначно, если
для используемого кода выполняется прямое
или обратное условие Фано.

24.

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

25.

ЗАДАЧА 5
Для кодирования некоторой последовательности, состоящей
из букв А, Б, В, Г и Д используется неравномерный двоичный
код, позволяющий однозначно декодировать полученную
двоичную последовательность. Вот этот код: А – 00, Б – 01, В
– 100, Г – 101, Д – 110.
Можно ли сократить для одной из букв длину кодового
слова так, чтобы код по-прежнему можно было
декодировать однозначно? Коды остальных букв меняться
не должны. Выберите правильный вариант ответа:
1) для буквы Д – 11
3) для буквы Г – 10
2) это невозможно
4) для буквы Д – 10

26.

РЕШЕНИЕ:
А – 00, Б – 01, В – 100, Г – 101, Д – 110
*
*
0
0
А
1) для буквы Д – 11
2) это невозможно
3) для буквы Г – 10
4) для буквы Д – 10
1
0
1
Б
0
В
1
1 0
Г Д
Ответ: 1) для буквы Д – 11
0
0
А
1
0
1
Б
0
В
1
Д
1
Г

27.

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

28.

РЕШЕНИЕ:
Н – 0, К – 10, Л – ?, М – ?
*
0
Н
1
0
К
1
0
Л
Ответ: 9
Какова наименьшая возможная
суммарная длина всех четырёх
кодовых слов?
Н – 0, К – 10, Л – 110, М – 111
1
М

29.

ЗАДАЧА 7
Для 5 букв латинского алфавита заданы их двоичные коды
(для некоторых букв из двух бит, для некоторых – из трех).
Эти коды представлены в таблице:
a
b
c
d
e
000 110 01 001 10
Какой набор букв закодирован двоичной строкой
1100000100110?

30.

ЗАДАЧА 8
По каналу связи передаются сообщения, содержащие
только семь букв: А, Б, Г, И, М, Р, Я. Для передачи
используется двоичный код, удовлетворяющий условию
Фано. Кодовые слова для некоторых букв известны: А –
010, Б – 011, Г – 100. Какое наименьшее количество
двоичных знаков потребуется для кодирования слова
МАГИЯ?
Примечание. Условие Фано означает, что ни одно кодовое
слово не является началом другого кодового слова

31.

ЗАДАЧА 9
Для 5 букв латинского алфавита заданы их двоичные коды
(для некоторых букв – из двух бит, для некоторых – из
трех). Эти коды представлены в таблице:
a b c d e
100 110 011 01 10
Какой набор букв закодирован двоичной строкой
1000110110110?
Все буквы в последовательности – разные.

32.

ЗАДАЧА 10
Для 6 букв латинского алфавита заданы их двоичные коды
(для некоторых букв из двух бит, для некоторых – из трех).
Эти коды представлены в таблице:
A
B
C
D
E
F
00 100 10 011 11 101
Какая последовательность из 6 букв закодирована двоичной
строкой 011111000101100?

33.

ЗАДАЧА 11
Для кодирования растрового рисунка, напечатанного с
использованием шести красок, применили
неравномерный двоичный код. Для кодирования цветов
используются кодовые слова.
Цвет
Кодовое слово
Цвет
Кодовое слово
Белый
0
Синий
Зелёный
11111
Фиолетовый
11110
Красный
1110
Чёрный
10
Укажите кратчайшее кодовое слово для кодирования
синего цвета, при котором код будет удовлетворять
условию Фано. Если таких кодов несколько, укажите код с
наименьшим числовым значением.

34.

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

35.

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

36.

ДОМАШНЕЕ ЗАДАНИЕ
Решить задачи из презентации 10-2,
подготовка к самостоятельной работе