Кодирование

1. КОДИРОВАНИЕ ИНФОРМАЦИИ

Теория информации

2. Кодирование vs Шифрование

Кодирование и шифрование информации –
достаточно близкие по смыслу термины.
Тем не менее, они имеют существенные отличия.
КоДиРоВаНие
• Кодирование – смысл текста должен быть ясен всем.
Любой, кто знает способ кодирования, может понять
смысл закодированной информации.
RjLbHjDfYbt
• Шифрование – смысл текста должен быть ясен только
определенным лицам, но скрыт от остальных.
КоДиРоВаНие
2

3. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

4. Знак

+
–
*
/
=
Знак – элемент конечного множества,
обладающий информационным содержанием,
отличающийся от других знаков данного множества.
A = { +; –; /; *; =}
Запас знаков – конечное множество знаков.
B = { ; ; ; ; ; ; }
4

5. Алфавит

A = { A; B; C; D; E;
F; G; H; I; J; K; L;
M; N; O; P; Q; R; S;
T; U; V; W; X; Y; Z }
Алфавит – конечное и линейно
упорядоченное множество знаков.
Z = { ; ; ; ;
; ; ; ;
; ; ; }
5

6. Подмножества знаков

A16 = { 0; 1; 2; 3; 4;
5; 6; 7; 8; 9;
A;B;C;D;E;F }
Множество А может включать подмножества,
которые могут образовывать
запасы знаков меньших алфавитов.
D10 = { 0; 1; 2; 3; 4;
5; 6; 7; 8; 9 }
O8 = { 0; 1; 2; 3;
4; 5; 6; 7 }
6

7. Бинарное множество

B = { 0; 1 }
Бинарное множество B
содержит только два знака.
7

8. Слово

мода
Слово – конечная последовательность знаков.
A = {а; д; м; о}
Множество слов над А – множество конечных
последовательностей знаков А* над запасом знаков А.
A* = {мода; дама; дома; мама;
а; да; дом; ад; мадам}
8

9. Двоичные слова

B = { 0; 1 }
В – двоичный алфавит.
В* – множество двоичных слов.
B* = { 0; 1 }*
Элементы множества В*
называются двоичными словами длины n
или n-битовыми словами.
n=3
{ 000; 001; 010; 011;
100; 101; 110; 111 }
9

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

Кодирование – отображение, переводящее
множество символов (запас знаков) А в
множество символов (запас знаков) В.
Аналогично обозначается кодирование слов.
10

11. Декодирование информации

Декодирование – обратное отображение
символов множества В в множество А.
В общем случае предполагается,
что кодирование является обратимой операцией.
11

12. КОДИРОВАНИЕ ТЕКСТОВОЙ И ЧИСЛОВОЙ ИНФОРМАЦИИ

13. Позиционные системы счисления

Представление числа в позиционной системе счисления
с основанием В имеет вид:
Разряды числа нумеруются от 0 (младший разряд, справа)
до n (старший разряд, слева).
13

14. Запись чисел в позиционной системе

Цифры аi входят в алфавит {a1, a2, a3, … , ai},
содержащий ровно В элементов.
B6 = { 0; 1; 2; 3; 4; 5 }
Числовое значение каждой цифры в записи числа в позиционной
системе счисления зависит от её положения в записи числа
(от номера разряда).
1116 = 1*62 + 1*61 + 1*60 = 36 + 6 + 1 = 4310
1236 = 1*62 + 2*61 + 3*60 = 36 +12 + 3 = 5110
2136 = 2*62 + 1*61 + 3*60 = 72 + 6 + 3 = 8110
14

15. Сравнение чисел

Числовое значение каждой цифры в записи числа в позиционной
системе счисления зависит от основания системы счисления.
1236 = 1*62 + 2*61 + 3*60 = 36 + 12 + 3 = 5110
12310 = 1*102 + 2*101 + 3*100 = 100 + 20 + 3 = 12310
12316 = 1*162 + 2*161 + 3*160 = 256 + 32 + 3 = 29110
Для сравнения чисел, записанных в разных системах счисления,
необходимо привести их в одну систему счисления
(например, двоичную или десятичную).
15

16. Перевод чисел в двоичную систему

Для перевода числа из десятичной системы счисления
в двоичную систему счисления методом вычитания
из исходного числа поочередно вычитаются
целые степени двойки,
не превосходящие
37 - 32 = 5 (32 = 25 )
остаток от вычитания.
5 - 4 = 1 ( 4 = 22 )
1- 1=0
( 1 = 20 )
В двоичной записи числа единицы записываются в тех разрядах,
номера которых соответствуют вычтенным степеням двойки.
3710 = 1*25 + 1*22 + 1*20 = 32 + 4 + 1 = 1001012
16

17. Непозиционные системы

I=1
X=10
C=100
V=5
L=50
M=1000
В римской системе счисления каждый знак
имеет строго определенное числовое значение.
MCLXVI =
= 1000 + 100 + 50 + 10 + 5 + 1 =
= 116610
17

18. Кодировка ASCII

ASCII – стандартная кодировка букв английского алфавита
(American Standard Code for Information Interchange –
Американский стандартный код для обмена информацией).
Буквы других алфавитов (кроме латинского) представлены
в расширенном 8-битном коде (исходный код – семибитный).
18

19. Многобайтовые кодировки

Многобайтовые кодировки необходимы
для кодирования текстов на языках,
имеющих более 255 знаков в алфавите.
Наиболее распространенной многобайтовой кодировкой
является кодировка Unicode, поддержка которой включена
во все современные операционные системы.
19

20. КОДЫ ПОСТОЯННОЙ ДЛИНЫ

21. Код постоянной длины

Код постоянной длины –
двоичное кодирование,
отображающее каждый
кодируемый знак
на двоичное слово
одинаковой длины.
Если число знаков
в алфавите А равно n,
то можно построить
код постоянной длины l
(где l – наименьшее натуральное
число, удовлетворяющее условию).
21

22. Пример кода постоянной длины

Наиболее компактное кодирование достигается в том случае,
когда число букв в алфавите равняется целой степени двойки.
Для кодирования 32-х заглавных букв русского алфавита
(за исключением буквы Ё) будет достаточно кода длины
L = log232 = 5
22

23. Расстояние Хэмминга

Расстояние Хэмминга h(a,b) – количество позиций,
в которых отличаются двоичные слова a и b
одинаковой длины.
Расстоянием Хэмминга h кода называется наименьшее
расстояние Хэмминга между его кодовыми словами.
23

24. Код Грэя

Код Грэя (одношаговый код) – код постоянной длины,
в котором коды двух последовательных знаков
из линейно упорядоченного алфавита А
различаются точно в одном бите.
Циклический код Грэя – код Грэя,
в котором коды первого и последнего знаков
из линейно упорядоченного алфавита А
различаются точно в одном бите.
24

25. Надежность кодирования

ТЕОРЕМА. Если код имеет расстояние Хэмминга h,
то все ошибки, которые встречаются меньше чем в h битах,
могут быть обнаружены. Все ошибки, появившиеся
менее чем в h/2 битах, могут быть успешно устранены.
Код с добавлением бита четности
позволяет обнаружить единичную
ошибку, поскольку для него h(a,b)=2.
Бит четности равен нулю, если количество единиц
в исходном слове четно (как в коде слова a=01101010),
и равен единице, если нечетно (как в коде слова b=01101011).
25

26. Исправление единичных ошибок

К исходному 4-битному коду
слова b=b1b2b3b4 добавляются
три контрольных бита b5b6b7.
При декодировании
вычисляются 3 бита,
образующие код
позиции ошибки.
26

27. КОДЫ ПЕРЕМЕННОЙ ДЛИНЫ

28. Коды переменной длины

Код Морзе строится из трех знаков:
(.) точка – короткая передача;
(–) тире – длинная передача;
(_) пробел – пауза в передаче.
Код телефонных систем для импульсного набора цифр:
28

29. Префиксные коды

Код называется префиксным, если
кодовое слово ни одного знака
не является началом (префиксом)
кодового слова другого знака
(условие Фано).
Слова префиксного кода можно записывать в одну цепочку,
не используя разделительных символов.
Любую такую цепочку можно единственным образом
разделить на ее компоненты.
29

30. Полные префиксные коды

Префиксный код называется полным, если добавление к нему
любого нового кодового слова нарушает свойство префиксности.
Так, например,
с(х) является
префиксом
с(А) и с(В),
а с(С) является
префиксом
с(у) и с(z).
При прочих равных условиях полные префиксные коды
более компактны, чем неполные.
30

31. ТЕОРЕМА КОДИРОВАНИЯ

32. Стохастический источник сообщений

Стохастический источник сообщений генерирует тексты
в виде последовательности символов с заданным алфавитом
и стационарными (не зависящими от времени)
статистическими характеристиками появления элементов
алфавита в последовательности.
В простейшем случае каждый символ ai A
появляется независимо от других с вероятностью p(i).
32

33. Энтропия источника сообщений

Количество информации, приносимое в среднем одним
элементом сообщения (текста), по определению равно
энтропии источника.
Энтропия источника H является непрерывной функцией от p(i).
При фиксированном n энтропия максимальна и равна log2n
в случае, если все p(i) равны между собой.
33

34. Длина кодового слова

l – длина i-го кодового слова.
Средняя длина кодовых слов
может быть определена
следующим образом:
34

35. Теорема кодирования

Для любого двоичного кодирования L H.
Каждый источник может быть закодирован так,
что разность L–H будет сколь угодно малой.
При выборе метода кодирования следует
стремиться к тому, чтобы разность (L–H) 0
Эффективность кода
H/L 1
Избыточность кода
(L – H) / L 0
35

36. Построение эффективных кодов

Общее правило построения наиболее
эффективного кода неизвестно.
Однако, предложен ряд алгоритмов, приводящих
к построению двоичных кодов с эффективностью,
близкой к максимальной.
Для повышения эффективности двоичного кода
необходимо соблюдение следующих условий:
1. вероятности появления двоичных символов «0» и «1»
должны быть равны;
2. вероятности появления «0» и «1»
не должны зависеть от того,
какие символы им предшествовали.
36