Контрольная работа по "Криптологии"

1)Вычислить  энтропию последовательности букв  ФИО. Для оценки вероятностей  символов использовать частоты  вхождения букв в ФИО.

ФИО: Русских Екатерина Владимировна

символы	Частота вхождения  символа в ФИО
и	0,1333
а	0,1333
р	0,1
с	0,0667
к	0,0667
пробел	0,0667
е	0,0667
н	0,0667
в	0,0667
у	0,0333
х	0,0333
т	0,0333
л	0,0333
д	0,0333
м	0,0333
о	0,0333

 

 

= 0,1333*log(1/0,1333) + 0,1333*log(1/0,1333) + 0,1*log(1/0,1) + 0,0667*(1/0,0667) + 0,0667*(1/0,0667) + 0,0667*(1/0,0667) + 0,0667*(1/0,0667) + 0,0667*(1/0,0667) + 0,0667*(1/0,0667) + 0,0333*(1/0,0333) + 0,0333*(1/0,0333) + 0,0333*(1/0,0333) + 0,0333*(1/0,0333) + 0,0333*(1/0,0333) + 0,0333*(1/0,0333) + 0,0333*(1/0,0333) = 2*0,1333*log(1/0,1333) + 0,1*log(1/0,1) + 6*0,0667*(1/0,0667) + 7*0,0333*(1/0,0333) = 0,7750 + 0,3322 + 1,5631 + 1,1440 = 3,8143.

2) По заданной матрице совместных вероятностей появления сообщений зависимых источников информации и вычислить величины  , , , , .

 

Y X	y1	y2	y3	y4
x1	0.12	0.05	0	0
x2	0	0.06	0.4	0.05
x3	0.05	0	0	0.27

 

Решение

1. Сначала вычислим безусловные вероятности и .

а) Сложив вероятности  по строкам таблицы, получим вероятности появления значений

б) Сложив вероятности по столбцам таблицы, получим вероятности  появления значений

2. Вычислим теперь  энтропии источников  информации  и по формуле Шеннона, используя вычисленные ранее значения безусловных вероятностей.

 -(-0,4345 – 0,4952 – 0,5260) = 1,4557 бит

 -(-0,4345 – 0,3502 – 0,5288 - 0,5260) = 1,8395 бит

3. Определим условные  вероятности события  при условии выполнения события по формуле . Тогда . Величины заданы в таблице, а – вычислены ранее.

Вычисленными  результатами заполним таблицу условных вероятностей события при условии выполнения события .

Y X	y1	y2	y3	y4
x1	0.7058	0.2941	0	0
x2	0	0.1176	0.7843	0.0980
x3	0.1562	0	0	0.8437

 

4. Определим  условную энтропию источника  информации  при условии, что сообщения источника известны, по формуле

= -(-0.0603 – 0.0883 – 0 – 0 – 0 – 0.1852 – 0.1404 – 0.1675 – 0.1339 – 0 – 0 – 0.0661) = 0.8417.

Аналогично  можно вычислить условную энтропию источника информации при условии, что сообщения источника известны.

5. Общая энтропия  зависимых источников информации и определяется по формуле

 

=-(-0.3670 – 0.2161 – 0 – 0 – 0 – 0.2435 – 0.5288 - 0.2161 - 0.2161 – 0 – 0 – 0.5100) = 2.2976.

 

Проверим результат по формуле

 бит

Значения совпадают.

3)Построить  равномерный двоичный код с наименьшей длиной кодового слова для букв, входящих в ФИО.

 

ФИО: Русских Екатерина Владимировна

символы	Частота вхождения  символа в ФИО
и	0,1333
а	0,1333
р	0,1
с	0,0667
к	0,0667
пробел	0,0667
е	0,0667
н	0,0667
в	0,0667
у	0,03333
х	0,03333
т	0,03333
л	0,03333
д	0,03333
м	0,03333
о	0,03333

 

 

Составляем  таблицу:

0,1333	0,1333	0,1333	0,1333	0,1333	0,1334	0,1334	0,1334	0,1334	0,2	0,2666	0,2668	0,2668	0,4666	0,53	0
0,1333	0,1333	0,1333	0,1333	0,1333	0,1333	0,1334	0,1334	0,1334	0,1334	0,2	0,2666	0,2668	0,2668	0,46	1
0,1	0,1	0,1	0,1	0,1	0,1333	0,1333	0,1334	0,1334	0,1334	0,1334	0,2	0,2666	0,2668
0,0667	0,0667	0,0667	0,0667	0,1	0,1	0,1333	0,1333	0,1334	0,1334	0,1334	0,1334	0,2
0,0667	0,0667	0,0667	0,0667	0,0667	0,1	0,1	0,1333	0,1333	0,1334	0,1334	0,1334
0,0667	0,0667	0,0667	0,0667	0,0667	0,0667	0,1	0,1	0,1333	0,1333	0,1334
0,0667	0,0667	0,0667	0,0667	0,0667	0,0667	0,0667	0,1	0,1	0,1333
0,0667	0,0667	0,0667	0,0667	0,0667	0,0667	0,0667	0,0667	0,1
0,0667	0,0667	0,0667	0,0667	0,0667	0,0667	0,0667	0,0667
0,0333	0,0667	0,0667	0,0667	0,0667	0,0667	0,0667
0,0333	0,0333	0,0667	0,0667	0,0667	0,0667
0,0333	0,0333	0,0333	0,0667	0,0667
0,0333	0,0333	0,0333	0,0333
0,0333	0,0333	0,0333
0,0333	0,0333
0,0333

 

символ			Кодовое слово
и	0,1333	3	1	0	0
а	0,1333	3	1	0	1
р	0,1	3	1	1	0
с	0,0667	4	1	1	1	0
к	0,0667	4	0	0	0	0
пробел	0,0667	4	0	0	0	1
е	0,0667	4	0	0	1	0
н	0,0667	4	0	0	1	1
в	0,0667	4	0	1	0	0
у	0,03333	4	1	1	1	1
х	0,03333	5	0	1	0	1	0
т	0,03333	5	0	1	0	1	1
л	0,03333	5	0	1	1	0	0
д	0,03333	5	0	1	1	0	1
м	0,03333	5	0	1	1	1	0
о	0,03333	5	0	1	1	1	1

 

Lср = 3,83328

4)Последовательность  букв ФИО преобразовать следующим  образом:  буквы от ‘А’ до  ‘З’ заменить символом а, буквы от ‘И’ до ‘Т’ заменить символом b, остальные буквы – символом c. Закодировать полученную последовательность словарным методом Лемпела-Зива (размер словаря 8). Декодировать закодированную последовательность.

 

Пусть алфавит  источника  , размер словаря . Необходимо закодировать исходное сообщение bcbbbbccabababbba.

Кодировка:

№	1	2	3	4	5	6	7	8
Код	0,b	0,c	1,b	3,c	2,a	1,a	6,b	3,a

 

Декодировка:

bcbbbbccabababbba

0,b – b

0,c – c

1,b – bb

3,c – bbc

2,a – a

1,a – ca

6,b – cab

3,a – bba

 Результат: bcbbbbccabababbba.

 

 

5)Закодировать  последовательность букв ФИО  адаптивным кодом «стопка книг».

Есть алфавит

ФИО: Русских Екатерина Владимировна

№

Кодове слово

Поч. “Стопка”

Преобразования  «стопки»

1

0

и

р

у

с

с

к

и

х

-

е

к

а

т

е

р

и

н

а

-

в

л

а

д

и

м

и

р

о

в

н

а

2

01

а

и

р

у

у

с

к

и

х

-

е

к

а

т

е

р

и

н

а

-

в

л

а

д

и

м

и

р

о

в

н

3

10

р

а

и

р

р

у

с

к

и

х

-

е

к

а

т

е

р

и

н

а

-

в

л

а

д

д

м

и

р

о

в

4

11

с

с

а

и

и

р

у

с

к

и

х

-

е

к

а

т

е

р

и

н

а

-

в

л

а

а

д

м

и

р

о

5

100

к

к

с

а

а

и

р

у

с

к

и

х

-

-

к

а

т

е

р

и

н

н

-

в

л

л

а

д

м

и

р

6

101

_

_

к

к

к

а

а

р

у

с

с

и

х

х

-

к

а

т

е

р

и

и

н

-

в

в

л

а

д

м

и

7

110

е

е

_

_

_

_

_

а

р

у

у

с

и

и

х

-

к

к

т

е

р

р

и

н

-

-

в

л

а

д

м

8

111

н

н

е

е

е

е

е

_

а

р

р

у

с

с

и

х

-

-

к

т

е

е

р

р

н

н

-

в

л

а

д

9

1000

в

в

н

н

н

н

н

е

е

а

а

р

у

у

с

с

х

х

х

к

т

т

е

е

р

р

н

-

-

л

л

10

1001

у

у

в

в

в

в

в

н

н

н

н

н

р

р

у

у

с

с

с

х

к

к

т

т

е

е

е

н

н

-

-

11

1010

х

х

х

х

х

х

х

в

в

в

в

в

н

н

н

н

у

у

у

с

х

х

к

к

т

т

т

е

е

е

е

12

1011

т

т

т

т

т

т

т

т

т

т

т

т

в

в

в

в

в

в

в

у

с

с

х

х

к

к

к

т

т

т

т

13

1100

л

л

л

л

л

л

л

л

л

л

л

л

л

л

л

л

л

л

л

л

у

у

с

с

х

х

х

к

к

к

к

14

1101

д

д

д

д

д

д

д

д

д

д

д

д

д

д

д

д

д

д

д

д

д

д

у

у

с

с

с

х

х

х

х

15

1110

м

м

м

м

м

м

м

м

м

м

м

м

м

м

м

м

м

м

м

м

м

м

м

м

у

у

у

с

с

с

с

16

1111

о

о

о

о

о

о

о

о

о

о

о

о

о

о

о

о

о

о

о

о

о

о

о

о

о

о

о

у

у

у

у