Iphone
shpora.me - незаменимый помощник для студентов и школьников, который позволяет быстро создавать и получать доступ к шпаргалкам или другим заметкам с любых устройств. В любое время. Абсолютно бесплатно. Зарегистрироватся | Войти

* данный блок не отображается зарегистрированым пользователям и на мобильных устройствах

OTI -mike

 Тема: Кількісна міра інформації.

 

Мета роботи: навчатися визначати кількість інформації в повідомленні дискретного джерела.

 

1.1 Теоретичні відомості

1.1.1 Теорія інформації та передача сигналів

Дослідження інформації розпочалося з виникнення телеграфу й дослідження проблем передачі повідомлень у ньому. Сучасна теорія інформації виникла на основі математичної теорії зв’язку. У 1928 р. американський дослідник Хартлі опублікував роботу „Передача інформації”. Він запропонував та обґрунтував кількісну міру, яка дозволяє порівнювати спроможність різних систем передавати інформацію. Природною вимогою, що висувається до інформаційної міри, є вимога адитивності, тобто, кількість інформації, яка може бути збережена у двох однакових комірках, повинна бути удвічі більшою за ту, що зберігається в одній з них.  Якщо одна комірка для зберігання інформації має m можливих станів, то дві таких комірки будуть мати m2 можливих станів, а n однакових комірок – mn можливих станів. Це саме стосується і кількості можливих повідомлень. Якщо символ може прийняти значення «0» або «1», то з одного символу можуть бути одержані 2 повідомлення, з двох символів – 4, з трьох – 8 тощо. Таким чином кількість можливих повідомлень визначається кількістю символів, що входять до слова n та кількістю можливих станів символу mmn.  Оскільки між m та n є степенева залежність, то він запропонував логарифмічну міру інформації, яка відповідає умові адитивності (ємність суми комірок рівна ємності однієї, помноженої на кількість останніх)  і кількість інформації в повідомленні дорівнює І=nlogаmде n — кількість вибраних символів, а m — кількість різних символів у наборі, з яких роблять вибір, при умові, що вибір символів рівноімовірний..

Відомий математик  Клод Шеннон займався дослідженням того, якого типу сигнали потрібно посилати, щоби краще передати повідомлення певного типу по заданому каналу з шумами. В праці «Математична теорія зв’язку», він обґрунтував методику вимірювання інформації та запропонував теореми про оптимальне кодування. Таким чином, було поставлено проблему ефективного кодування й надійного отримання повідомлення. Так виникла класична (імовірнісна) теорія інформації. У повному викладі основні положення цієї теорії було опубліковано в 1948 р. у двох статтях.

 

1.1.2. Кількісна міра інформації

За Шеноном всяка інформація отримується одержувачем після прийому повідомлення, тобто в результаті досліду. Повідомлення, одержуване на прийомній стороні, несе корисну інформацію лише в тому випадку, якщо мається невизначеність щодо стану джерела. Якщо дослід може закінчитися тільки одним результатом і спостерігач заздалегідь знає результат досліду, то по його результаті він не одержує  ніякої інформації. Наприклад, якщо повідомлять, що сонце сходить на сході, то ніякої інформації це повідомлення не принесе, оскільки усі знають, що це вірно. У такій події, як щоденний схід сонця на сході, немає нічого невизначеного, імовірність цієї події дорівнює одиниці і кількість інформації, принесена повідомленням про таку подію, дорівнює нулеві. Інформація з'явиться лише тоді, коли джерело буде мати принаймні більш одного можливого стану.

Розглянемо джерело, що видає послідовність незалежних дискретних повідомлень {xi}, кожне з яких випадковим чином вибирають з алфавіту повідомлення X(xi) = x1, x2, x3, ... xk,  де k - розмір алфавіту джерела. Повідомлення, видані таким джерелом, називаються простими повідомленнями.

У кожному елементарному повідомленні xi для його одержувача утримується деяка інформація. До того, як зв'язок відбувся, в приймача завжди є велика або менша невизначеність щодо того,  яке повідомлення xi  з числа можливих буде передано.

Очевидно, що ступінь цієї невизначеності, або  несподіванки  передачі  xi, залежить від імовірності передачі того або іншого повідомлення. Наприклад,  якщоімовірність передачі якого-небудь повідомлення x дуже висока, то ще до передачі ми майже напевно знаємо, яке  повідомлення буде передано, і його прийом не принесе нам майже ніякої нової інформації.

Таким чином,  кількість інформації, що несе елементарне повідомлення xi, є  деякою функцією від імовірності передачі цього повідомлення  р(xi), тобто I(xi)=f{р(xi)} функція ймовірності цього повідомлення. Щоб визначити що це за функція, проаналізуємо міру кількості інформації.  Вона повинна задовольняти властивостям:

1. Якщо вибір повідомлення xi заздалегідь визначений (p(xi)=1 – невизначеності немає), то кількість інформації в цьому повідомленні  дорівнює нулеві:I(xi)=f{1}=0.

2. Якщо джерело послідовно вибирає повідомлення xi  і xj  та імовірність такого вибору p(x, x) є спільна імовірність подій xi і x, то кількість інформації в цих двох елементарних повідомленнях буде дорівнює сумі кількостей інформації в кожнім з них.

Імовірність спільного випадання подій xi і xj  p(x,xj), як відомо, визначається по формулі повної імовірності

p (xi , xj ) = p(xi )×p(xj /xi ) = P × Q,

тоді f(P×Q)=f(P)+f(Q).

Єдина функція f з такими властивостями є логарифмічна функція, тоді

I (xi) = k logap(xi),

де k – коефіцієнт, що узгоджує розмірності, основа будь-яка. Щоб кількість інформації була додатна k=-1, бо p(x)<1, logap(x)<0.

Основу логарифма звичайно вибирають  рівним  двом, і тоді

                    I (xi) = - log2 p(xi)                                          

Визначена в такий спосіб одиниця виміру інформації  називається двійковою одиницею, або бітом інформації. Наприклад, якщо яке-небудь з елементарних повідомлень  xi   може бути  обрано з алфавіту і передано  з   імовірністю p(xi) = 1/8, то  говорять,  що   в ньому  міститься  log2 (1/8)  =  3 біти інформації.

Іноді як підставу логарифма вибирають e, тоді інформація виміряється в натуральних одиницях, або натах.

 

Отже, кількість інформації для рівноймовірних випробувань за  формулою Р. Хартлі вимірюється як логарифм від кількості можливих варіантів (N) випробувань:

I = loga N.                                                                                                        (1)

Для випадку, коли події не є рівноймовірними за  формулою Шенона кількість інформації, що несе i-те елементарне повідомлення:

 Ii = -loga pi                                                                                                       (2)

 

Застосування цієї формули показує, що чим менша ймовірність певного випробування, тим більше інформації воно несе.

 

Приклад. Необхідно підняти вантаж на певний поверх 16-ти поверхового будинку (нумерація поверхів 0-15, N=16). Скільки біт інформації повністю визначають завдання?

I = log2 16

Отже, 4 біти інформації необхідні й достатні для повного зняття невизначеності вибору. У цьому можна переконатися застосуванням логіки вирахування з послідовним розподілом навпіл інтервалів станів. Наприклад, для 9-го поверху:

1) вище 7-го поверху? Так = 1;

2) вище 11-го поверху? Ні = 0;

3) вище 9-го поверху? Ні = 0;

4) вище 8-го поверху? Так = 1.

Підсумок: поверх номер 9 або 1001 у двійковому численні, чотири двійкових розряди.

Якщо в наведеному прикладі на поверхах є по 4 квартири з нумерацією на кожному поверсі 0-3 (М=4), то при адресації вантажу у квартиру буде потрібно ще 2 біти інформації. Такий же результат одержимо, якщо замість незалежної нумерації поверхів і квартир на поверхах (два джерела невизначеності) ми будемо мати тільки наскрізну нумерацію квартир (одне узагальнене джерело):

I = log2 N +  log2 М= log2 16+ log2 4= log2 (NМ)= log2 64 =6,

тобто, кількість інформації відповідає вимозі адитивності: невизначеність об'єднаного джерела дорівнює сумі невизначеностей вихідних джерел, що відповідає інтуїтивній вимозі до інформації: вона повинна бути однозначною, а її кількість повинна бути тією самою незалежно від способу задання.

Кількість інформації у всіх випробуваннях експерименту визначають як арифметичну суму по всіх подіях.

Кількість інформації, що утримується в одному елементарному повідомленні xi, ще ніяк не характеризує джерело. Одні елементарні повідомлення можуть нести багато інформації, але передаватися дуже рідко, інші - передаватися частіше, але нести менше інформації. Тому джерело  може бути охарактеризований середньою кількістю інформації, що приходиться на одне елементарне повідомлення, що носить назву “ентропія джерела” і обумовленим у такий спосіб:

,  i = 1, K.

В класичній ймовірнісній теорії інформації математична модель визначення кількості інформації досконало працює для тих випадків, коли мова йде про кодування інформації, тобто при передачі інформації каналами зв’язку чи її зберіганні на носіях інформації. Проте вона зовсім не працює, коли йдеться про визначення кількості інформації в об’єктах, позначених цими кодами. Покажемо це на прикладах.

Приклад. Визначаючи кількість інформації в літері Р, ця теорія зовсім не аналізує, що ця літера, по-перше, складається з двох компонентів: прямої лінії та півкола; по-друге, пряма та півколо з’єднані між собою; по-третє, товщина лінії, яка утворює півколо, в різних точках є різною; по-четверте, пряма лінія нахилена під певним кутом тощо.

Приклад. Вимірюючи кількість інформації у слові мама, ця теорія визначає лише кількість інформації в літерах цього слова, тобто

I(мама) = (-p(м) log p(м)) + (-p(а) log p(а)) + (-p(а) log p(а)) + (-p(м) log p(м))

проте зовсім не визначає, скільки інформації міститься в значенні цього слова (мама — людина, мама — жінка, мама — має двоє очей, ніг, рук і т. д., а конкретна моя мама має ще й певний вираз обличчя, колір очей, ріст, вагу тощо). Зрозуміло, що семантична інформація (що таке мама), тут повністю проігнорована, так само, як інші види інформації, що є в текстах — синтаксична, стилістична, граматична тощо .

Класична ймовірнісна теорія інформації: а) стосується вимірювання кількості інформації лише в технічних пристроях — каналах зв’язку та носіях інформації (наприклад, пам’яті комп’ютерів) тощо ; б) не має методів, які давали б можливість виміряти кількість інформації стосовно тих подій, які вже відбулися, оскільки їх імовірність завжди дорівнює одиниці (в цьому випадку I = 0); в) не має методів, які давали б змогу виміряти кількість семантичної інформації не тільки в словах, реченнях, текстах, а й загалом у будь-яких знаках, що позначають образи (наприклад, географічних картах).

 

 

1.2 Завдання

 (n – номер варіанту,  k – остання цифра залікової книжки)

1. Визначити кількість інформації (в бітах) джерела А, щомістить n  рівноймовірних повідомлень (значення n  взяти з табл. 1.1 згідно варіанту).

Таблиця 1.1

Вар.

1,14

2,15

3,16

4,17

5,18

6,19

7,120

8,21

9,22

10,23

11,24

12,25

13,26

n

128

512

2048

64

4096

32768

8192

256

32

1024

16384

65536

131072

 

 

2. Визначити кількість інформації в повідомленні довжиною в 100n символів, якщо алфавіт повідомлення складається з n рівноймовірних символів(значення n  взяти з табл. 1.1 згідно варіанту).

3. Ансамбль повідомлень джерела А визначено як А={а, b, с} та р(а)=,  р(b)=,  р(с)= . Визначити кількість інформації, що міститься в кожному повідомленні. Визначити кількість інформації, що передається в одному та 100 повідомленнях.

4. Розвязати задачі згідно варіанту.

Вар.

1

2

3

4

5

6

7

8

9

10

11

12

13

№ задач

1,21

2,26

3,22

4,28

5,30

6,27

7,23

8,21

9,29

10,24

11,28

12,25

13,28

 

 

Вар.

14

15

16

17

18

19

20

21

22

23

24

25

№ задач

14,25

15,22

16,24

17,27

18,26

19,21

20,25

8,29

5,23

20,27

13,30

12,24

 

 

1. Яку кількість інформації несе повідомлення: "Зустріч призначена на травень»?

2. Задано число з проміжку від 1 до 64. Яка кількість інформації необхідна для вгадування числа з цього проміжку?

3. Яку кількість інформації отримає другий гравець у грі «Вгадай число» при правильній стратегії, якщо перший гравець загадав число з інтервалу від 1 до 128?

4. Яку кількість інформації отримає перший гравець після першого ходу другого гравця в грі в «хрестики-нулики» на полі 3 на 3?

5. Яка кількість можливих подій, якщо після реалізації однієї з них ми отримали кількість інформації рівне 3 біта? 7 біт?

6. Яка кількість можливих подій, якщо після реалізації однієї з них ми отримали кількість інформації рівне 7 біт?

7. Який обсяг інформації містить повідомлення, що зменшує невизначеність знань в 8 разів?

8. Ви підійшли до світлофору, коли горіло жовте світло. Після цього загорівся зелений. Яку кількість інформації ви при цьому отримали?

9. Скільки біт інформації несе повідомлення про те, що на світлофорі горить зелене світло?

10. На залізничному вокзалі 8 колій відправлення поїздів. Вам повідомили, що ваш поїзд прибуває на четверту колію. Скільки інформації ви отримали?

11. Була отримана телеграма: «Зустрічайте, вагон 7». Відомо, що в складі поїзда 16 вагонів. Яка кількість інформації була отримана?

12. При вгадуванні цілого числа в діапазоні від 1 до N було отримано 9 біт інформації. Визначити N?

13. При вгадуванні цілого числа в деякому діапазоні було отримано 8 біт інформації. Скільки чисел містить цей діапазон?

14. Повідомлення про те, що ваш друг живе на 10 поверсі, несе 4 біти інформації. Скільки поверхів в будинку?

15. Скільки інформації несе повідомлення про те, що з колоди карт дістали  карту чорної масті?

16. Скільки інформації несе повідомлення про те, що з колоди карт дістали  карту бубнової масті?  

17. Скільки інформації несе повідомлення про те, що з колоди карт дістали  карту одну карту?

18. У шкільній бібліотеці 16 стелажів з книгами. На кожному стелажі 8 полиць. Яка кількість інформації міститься в повідомленнях  - «Книга лежить на 2-й полиці»?  «Книга знаходиться на 5-му стелажі на 3 полиці»?

19. Загадане слово з 10 букв. Ви просите відкрити п'яту букву. Вам її відкрили. Скільки інформації ви отримали?

20. Проводиться лотерея «6 із 42».

А) Скільки біт інформації ми отримуємо при випаданні 1-ої кулі з 42?

Б) Скільки біт інформації ми отримуємо при випаданні третьої кулі (з 41)?

В) Яка кількість інформації несе повідомлення про результати лотереї?

21. У кошику лежать 8 чорних куль і 24 білих. Скільки інформації несе повідомлення про те, що дістали чорну кулю?

22. У кошику лежать 48 чорних куль і 16 білих. Скільки інформації несе повідомлення про те, що дістали білу кулю?

23. У класі 30 чоловік. За контрольну роботу з математики отримано 6 п'ятірок, 15 четвірок, 8 трійок і 1 двійка. Яка кількість інформації в повідомленні про те, що Іванов отримав четвірку?

24. У класі 28 чоловік. За контрольну роботу з математики отримано 6 п'ятірок, 12 четвірок, 9 трійок і 1 двійка. Яка кількість інформації в повідомленні про те, що Іванов отримав трійку?

25. За чверть учень отримав 100 оцінок. Повідомлення про те, що він отримав четвірку, несе 2 біти інформації. Скільки четвірок учень отримав за чверть?

26. В ящику лежать рукавички (білі і чорні). Серед них - 2 пари чорних. Повідомлення про те, що з ящика дістали пару чорних рукавичок, несе 4 біти інформації. Скільки всього пар рукавичок було в ящику?

27. Для ремонту школи використовували білу, синю і коричневу фарби. Витратили однакову кількість банок білої та синьої фарби. Повідомлення про те, що закінчилася банка білої фарби, несе 2 біти інформації. Синьої фарби витратили 8 банок. Скільки банок коричневої фарби витратили на ремонт школи?

28. У кошику лежать білі і чорні кулі. Серед них 18 чорних куль. Повідомлення про те, що з корзини дістали білу кулю, несе 2 біти інформації. Скільки всього в кошику куль?

29. У кошику лежать білі і чорні кулі. Серед них 25 чорних куль. Повідомлення про те, що з корзини дістали білу кулю, несе 3 біти інформації. Скільки всього в кошику куль?

30. На зупинці зупиняються тролейбуси з різними номерами. Повідомлення про те, що до зупинки підійшов тролейбус з номером N1 несе 4 біти інформації. Імовірність появи на зупинці тролейбуса з номером N2 в два рази менше, ніж ймовірність появи тролейбуса з номером N1. Скільки інформації несе повідомлення про появу на зупинці тролейбуса з номером N2?

 

5. Знайти кількість інформації кожного символу випадкової величини Х, заданої розподілом р(xi) (значення р(xi) взяти з табл. 1.2 згідно варіанту), де N – кількість повідомлень.

Таблиця 1.2

Вар.

N

a

P(x1)

P(x2)

P(x3)

P(x4)

P(x5)

P(x6)

P(x7)

P(x8)

P(x9)

P(x10)

1

10

4

0,22

0,1

0,11

0,05

0,08

0,32

0,06

0,03

0,01

0,02

2

9

4

0,21

0,11

0,13

0,1

0,2

0,11

0,04

0,06

0,04

3

8

4

0,2

0,12

0,05

0,13

0,14

0,15

0,1

0,11

4

10

3

0,19

0,13

0,09

0,1

0,11

0,14

0,03

0,1

0,04

0,07

5

9

3

0,18

0,14

0,4

0,11

0,01

0,03

0,04

0,04

0,05

6

8

3

0,17

0,15

0,1

0,03

0,15

0,3

0,02

0,08

7

10

5

0,36

0,18

0,19

0,04

0,05

0,05

0,012

0,05

0,05

0,018

8

9

5

0,3

0,15

0,16

0,06

0,16

0,1

0,05

0,01

0,01

9

8

5

0,11

0,09

0,08

0,15

0,06

0,16

0,13

0,22

10

10

4

0,06

0,08

0,3

0,12

0,14

0,09

0,03

0,06

0,08

0,04

11

9

4

0,15

0,35

0,01

0,06

0,11

0,15

0,07

0,02

0,08

12

8

4

0,08

0,076

0,4

0,032

0,25

0,06

0,05

0,052

13

10

3

0,22

0,1

0,05

0,015

0,008

0,25

0,15

0,1

0,05

0,057

14

9

3

0,05

0,09

0,04

0,08

0,07

0,15

0,36

0,15

0,01

15

8

3

0,05

0,2

0,1

0,3

0,15

0,13

0,025

0,045

16

10

4

0,2

0,11

0,3

0,2

0,02

0,03

0,05

0,01

0,06

0,02

17

9

4

0,31

0,106

0,2

0,14

0,03

0,12

0,06

0,02

0,014

18

8

4

0,39

0,1

0,04

0,16

0,09

0,08

0,13

0,01

19

10

3

0,2

0,01

0,16

0,4

0,02

0,03

0,08

0,01

0,07

0,02

20

9

3

0,31

0,2

0,1

0,05

0,04

0,08

0,03

0,01

0,18

21

8

3

0,39

0,2

0,1

0,05

0,09

0,08

0,08

0,01

22

10

5

0,25

0,11

0,15

0,15

0,02

0,02

0,06

0,03

0,18

0,03

23

9

5

0,29

0,2

0,04

0,05

0,11

0,08

0,13

0,01

0,09

24

8

5

0,27

0,2

0,2

0,15

0,03

0,08

0,06

0,01

25

10

4

0,31

0,006

0,15

0,1

0,12

0,02

0,03

0,03

0,104

0,13

 

 

1.3. Зміст звіту по лабораторній роботі

Звіт по лабораторній роботі повинний містити розвязані задачі згідно варіанту, який відповідає номеру в списку групи.

  •  

Знайти кількість інформації (в бітах) кожного символу, ентропію заданої кодової комбінації і максимальну ентропію джерела інформації.

xi  X

х1

х2

х3

х4

х5

х6

pP

0,4

0,3

0,15

0,1

0,03

0,02

 

Розв’язання:

Кількість інформації, що містить кожне повідомлення 

хi

1

2

3

4

5

6

pi

0.4

0,3

0,15

0,1

0,03

0,02

І(хi)

1,322

1,737

2.737

3,22

5,059

5,644

ЛАБОРАТОРНА РОБОТА № 2

 

Тема: Ентропія та її властивості.

 

Мета роботи: навчатися визначати ентропію повідомлень дискретного джерела.

2.1 Теоретичні відомості

2.1.1 Ентропія

Кількісну міру апріорної невизначеності про те, яке повідомлення буде породжене дискретним джерелом повідомлень (або середню кількість інформації в кожному повідомленні)  в теорії інформації називають ентропією (“Эн-mpone” - від грецького – звертання) і позначають Н.  Тобто ентропія – це кількість інформації, яка в середньому приходиться на один символ в повідомленні.

Точно ентропію Н(А) можна визначити як математичне сподівання питомої кількості інформації:

 

     

 

 

 

У випадку рівної ймовірності повідомлень р(a1)= р(a2)=… р(ak)=1/n ентропія джерела обчислюється за формулою:

2.1.2 Властивості ентропії

Ентропія, як кількісна міра інформативності джерела, має наступні властивості:

1. Ентропія є величина дійсна, обмежена і невід’ємна. Ці її властивості випливають з вигляду виразу для Н(x), а також з  врахуванням того, що  0 < P(xi) < 1.

2. Ентропія  детермінованних  повідомлень  дорівнює  нулеві, тобто Н(x) = 0, якщо хоча б одне з повідомлень має імовірність, рівну одиниці.

3. Ентропія максимальна,   якщо   повідомлення    xi   рівноймовірні, тобто P(x1 )= P(x2 )= ....... P(xk) = 1/K , і тоді:

Як видно з останнього виразу, у випадку рівноймовірних повідомлень ентропія росте зі збільшенням обсягу алфавіту джерела (ростом числа повідомлень). При нерівноймовірних елементарних повідомленнях xi  ентропія, відповідно, зменшується.

4. Ентропія двійкового джерела (K = 2) може змінюватися від нуля до одиниці. Дійсно, ентропія системи з двох повідомлень    x1  і    x2

З останнього  виразу видно, що  ентропія дорівнює  нулеві при P(x1)= 0P(х2)=1, або  P(х1) = 1; P(х2) = 0; при цьому максимум ентропії  буде мати  місце, коли  P(х1)=P(х2)=1/2  і її максимальне значення буде дорівнює біт.

 

 

2.2 Завдання

1.  Джерела А та В мають розподіли ймовірностей повідомлень

РА = {х1х2; ... хк} і РB = {х1х2; ... хк } (дані наведені в таблиці 2.1).

Ентропія якого джерела більша? Яка максимальна ентропія цього джерела та за якої умови?

Таблиця 2.1

Вар

 

P(x1)

P(x2)

P(x3)

P(x4)

P(x5)

P(x6)

P(x7)

P(x8)

P(x9)

P(x10)

1

А

0,22

0,1

0,11

0,05

0,08

0,32

0,06

0,03

0,01

0,02

В

0,19

0,13

0,09

0,1

0,11

0,14

0,03

0,1

0,04

0,07

2

А

0,21

0,11

0,13

0,1

0,2

0,11

0,04

0,06

0,04

В

0,18

0,14

0,4

0,11

0,01

0,03

0,04

0,04

0,05

3

А

0,2

0,12

0,05

0,13

0,14

0,15

0,1

0,11

 

 

В

0,17

0,15

0,1

0,03

0,15

0,3

0,02

0,08

4

А

0,36

0,18

0,19

0,04

0,05

0,05

0,012

0,05

0,05

0,018

В

0,06

0,08

0,3

0,12

0,14

0,09

0,03

0,06

0,08

0,04

5

А

0,3

0,15

0,16

0,06

0,16

0,1

0,05

0,01

0,01

В

0,15

0,35

0,01

0,06

0,11

0,15

0,07

0,02

0,08

 

6

А

0,08

0,076

0,4

0,032

0,25

0,06

0,05

0,052

 

В

0,11

0,09

0,08

0,15

0,06

0,16

0,13

0,22

7

А

0,22

0,1

0,05

0,015

0,008

0,25

0,15

0,1

0,05

0,057

В

0,2

0,11

0,3

0,2

0,02

0,03

0,05

0,01

0,06

0,02

8

А

0,05

0,09

0,04

0,08

0,07

0,15

0,36

0,15

0,01

В

0,31

0,106

0,2

0,14

0,03

0,12

0,06

0,02

0,014

 

9

А

0,05

0,2

0,1

0,3

0,15

0,13

0,025

0,045

В

0,39

0,1

0,04

0,16

0,09

0,08

0,13

0,01

 

 

10

А

0,2

0,01

0,16

0,4

0,02

0,03

0,08

0,01

0,07

0,02

В

0,25

0,11

0,15

0,15

0,02

0,02

0,06

0,03

0,18

0,03

11

А

0,31

0,2

0,1

0,05

0,04

0,08

0,03

0,01

0,18

В

0,29

0,2

0,04

0,05

0,11

0,08

0,13

0,01

0,09

 

12

А

0,39

0,2

0,1

0,05

0,09

0,08

0,08

0,01

В

0,27

0,2

0,2

0,15

0,03

0,08

0,06

0,01

 

 

13

А

0,31

0,006

0,15

0,1

0,12

0,02

0,03

0,03

0,104

0,13

В

0,25

0,11

0,15

0,15

0,02

0,02

0,06

0,03

0,18

0,03

14

А

0,22

0,1

0,05

0,015

0,008

0,25

0,15

0,1

0,05

0,057

В

0,19

0,13

0,09

0,1

0,11

0,14

0,03

0,1

0,04

0,07

15

А

0,15

0,35

0,01

0,06

0,11

0,15

0,07

0,02

0,08

В

0,05

0,09

0,04

0,08

0,07

0,15

0,36

0,15

0,01

 

 

2. Для призначення іменних стипендій з двох факультетів (хіміко-біологічний і факультет інформатики і математики) відібрали по 9 студентів. За правилами обирається тільки один студент з факультету. При цьому відомо, що ймовірності вибору кожного студента хіміко-біологічного факультету приблизно однакові, а для факультету інформатики і математики – розподіляються так, як показано в таблиці: Обчислити ентропію досліду визначення студентів для призначення стипендії на обох факультетах.

вар

Ймовірність призначення стипендії студентів

Ст 1

Ст 2

Ст 3

Ст 4

Ст 5

Ст 6

Ст 7

Ст 8

Ст 9

1

0,31

0,08

0,05

0,14

0,02

0,20

0,08

0,07

0,05

2

0,11

0,16

0,03

0,26

0,04

0,05

0,03

0,02

0,30

3

0,08

0,05

0,11

0,07

0,33

0,24

0,04

0,04

0,04

4

0,22

0,18

0,04

0,06

0,03

0,04

0,06

0,29

0,08

5

0,07

0,41

0,13

0,09

0,06

0,11

0,05

0,04

0,04

6

0,35

0,15

0,06

0,02

0,03

0,08

0,02

0,07

0,22

7

0,12

0,03

0,05

0,40

0,12

0,08

0,05

0,04

0,11

8

0,28

0,03

0,04

0,15

0,05

0,04

0,07

0,3

0,04

9

0,2

0,02

0,05

0,1

0,05

0,14

0,07

0,34

0,08

10

0,13

0,24

0,05

0,08

0,06

0,12

0,05

0,07

0,2

11

0,2

0,11

0,03

0,16

0,07

0,02

0,05

0,32

0,04

12

0,1

0,27

0,08

0,05

0,04

0,14

0,01

0,11

0,2

13

0,2

0,2

0,05

0,06

0,02

0,06

0,04

0,19

0,18

14

0,05

0,43

0,03

0,09

0,16

0,1

0,05

0,05

0,04

15

0,1

0,31

0,1

0,09

0,06

0,21

0,08

0,04

0,01

 

3. а) Задати два дискретних джерела повідомлень, що вибирають повідомлення akÎА та bkÎB, де АB – множини літер прізвища, імені, по-батькові українською та англійською мовою відповідно.

б)  Розрахувати ансамблі для кожного джерела повідомлень, пов'язавши з кожним дискретним повідомленням ai та biймовірність pi його вибору джерелом.

в) Визначити кількість інформації, що містить кожне повідомлення, та ентропію обох джерел.

г) Визначити продуктивність обох джерел припустивши, що вони вибирають всі свої повідомлення за один і той самий проміжок часу t = tcep = 1с.

д)  Порівняти джерела за інформативністю та продуктивністю.

 

4. Оформити звіт.

 

Примітка: Збережіть отримані в результаті виконання лабораторної роботи програмні коди. Вони використовуватимуться в наступних лабораторних роботах.

 

2.3  Зміст звіту по лабораторній роботі

 

Звіт по лабораторній роботі повинний містити:

  1. Індивідуальне завдання згідно варіанту, який відповідає номеру в списку групи. Наприклад:

Знайти кількість інформації (в бітах) кожного символу, ентропію заданої кодової комбінації і максимальну ентропію джерела інформації.

xi  X

х1

х2

х3

х4

х5

х6

pP

0,4

0,3

0,15

0,1

0,03

0,02

 
  •  

Кількість інформації, що містить кожне повідомлення 

хi

1

2

3

4

5

6

pi

0.4

0,3

0,15

0,1

0,03

0,02

І(хi)

1,322

1,737

2.737

3,22

5,059

5,644

 

Ентропію можна визначити як математичне сподівання питомої кількості інформації

Згідно з умовою задачі маємо

H(X)=0.4*1.322+0.3*1.737+0.15*2.737+0.1*3.22+0.03*5.059

+0.02*5.644=2.0573 біт/повідомлення.

Максимум ентропії  буде мати  місце, коли  р(х1)=р(х2)=...=1/N.

 

  1. Індивідуальне завдання з множинами літер прізвища, імені, по-батькові українською та англійською мовою. Наприклад:

Перше джерело повідомлень – літери прізвища, імені, по-батькові українською мовою

ІВАНОВ_ІВАН_ІВАНОВИЧ             N=20

Розрахунок ансамблю джерела повідомлень

A={І, В, А, Н, О, И, Ч, _}

Кількість різних повідомлень     k=8.

              

літера

І

В

А

Н

О

И

Ч

_

ai

1

2

3

4

5

6

7

8

ni

3

5

3

3

2

1

1

2

pi

0.15

0.25

0.15

0.15

0.10

0.05

0.05

0.10

 

 

Кількість інформації, що містить кожне повідомлення 

ai

1

2

3

4

5

6

7

8

pi

0.15

0.25

0.15

0.15

0.10

0.05

0.05

0.10

І(ai)

2.737

2.000

2.737

2.737

3.322

4.322

4.322

3.322

 

Ентропія джерела   H(A)=2.828

Продуктивність джерела     V(A)=2.828

Друге джерело повідомлень літери прізвища, імені, по-батькові англійською мовою

IVANOV_IVAN_IVANOVICH    N=21

Розрахунок ансамблю джерела повідомлень

B={I, V, A, N, O, C, H, _}

Кількість різних повідомлень        k=8.

літера

I

V

A

N

O

C

H

_

bi

1

2

3

4

5

6

7

8

ni

4

5

3

3

2

1

1

2

pi

0.19

0.24

0.14

0.14

0.10

0.05

0.05

0.10

 

Кількість інформації, що містить кожне повідомлення 

bi

1

2

3

4

5

6

7

8

pi

0.19

0.24

0.14

0.14

0.10

0.05

0.05

0.10

І(bi)

2.392

2.070

2.807

2.807

3.392

4.392

4.392

3.392

 

Ентропія джерела           H(B)=2.815

Продуктивність джерела     V(B)=2.815

Висновки: Джерело _ є більш інформативним та більш продуктивним порівняно з джерелом _.

ЛАБОРАТОРНА РОБОТА №3

 

Тема: Ентропія складних повідомлень.

 

Мета роботи: навчатися визначати  ентропію складних повідомлень та надмірності джерела.

3.1 Теоретичні відомості

 

3.1.1Ентропія складних повідомлень

Розглянуті вище характеристики джерела  –  кількість інформації й ентропія - відносилися до одного джерела, що виробляє потік незалежних або простих повідомлень, або до джерела без пам'яті.

Однак у реальних умовах незалежність елементарних повідомлень - явище досить рідке. Частіше буває саме зворотнє  -  сильний детермінований або статистичний зв'язок між елементами повідомлення одного або декількох джерел.

Наприклад, при передачі тексту імовірності появи окремих букв залежать від того, які букви їм передували. Для російського тексту, наприклад, якщо передано букву "П", імовірність того, що наступної буде "А", набагато вище, ніж "Н", після букви "Ъ" ніколи не зустрічається "H" і т.д. Подібна ж картина спостерігається при передачі зображень - сусідні елементи зображення мають звичайно майже однакові яскравість і колір.

При передачі і збереженні даних часто також мають справа з декількома джерелами, що формують статистично зв'язані один з одним повідомлення. Повідомлення, вироблювані такими джерелами, називаються складними повідомленнями, а самі джерела - джерелами з пам'яттю.

Очевидно, що при визначенні ентропії і кількості інформації в повідомленнях, елементи яких статистично зв'язані, не можна обмежуватися тільки безумовними імовірностями  - необхідно обов'язково враховувати також умовні імовірності появи окремих повідомлень.

Визначимо ентропію складного повідомлення, вироблюваного двома залежними джерелами (подібним же чином визначається ентропія складного повідомлення, вироблюваного одним джерелом з пам'яттю).

Нехай повідомлення першого джерела приймають значення   x1, x2, x3,....xk з імовірностями,  відповідно,  P(x), P(x),..... P(x),  повідомлення  другого - y1, y2,.....ym з імовірностями   P(y), P(y),..... P(y).

Спільну ентропію двох джерел X і Y можна визначити в такий спосіб:

,                                                                                  (3.1)

де  P(xi,yj ) - імовірність спільної появи повідомлень xi і  yj .  Оскільки спільна імовірність P(xi,yj )  по формулі Байеса  визначається як

,                                                                                                         (3.2)

Тепер вираз для спільної ентропії можна записати в наступному вигляді:

        (3.3)

Тому що передачі повідомлення  xi  обов'язково  відповідає  передача одного з повідомлень (кожного) з ансамблю  , те

                                                                                                                                (3.4)

і спільна ентропія H(X,Y) визначиться як

,                                                     (3.5)

де  H ( Y/x-  так називана частинна умовна ентропія, що відображає ентропію повідомлення за умови, що мало місце повідомлення xi.  Другий доданок в останнім вираженні являє собою усереднення H ( Y/xi ) по всіх повідомленнях xі називається середньою умовною ентропією джерела Y за умови передачі повідомлення X.   І остаточно:

H (X,Y )  =  H (X)  + H (Y/X) .                                                                                            (3.6)

Таким чином, спільна ентропія двох повідомлень дорівнює сумі безумовної ентропії одного з них і умовної ентропії другого.

 

3.1.2 Властивості ентропії складних повідомлень

Можна відзначити наступні основні властивості ентропії складних повідомлень:

1. При статистично незалежних повідомленнях X і Y спільна ентропія  дорівнює сумі ентропій кожного з джерел:

H (X,Y) = H (X) + H (Y),                                                                                                                (3.7)

тому що  H (Y/X) = H (Y).

2. При повній статистичній залежності повідомлень X і Y спільна ентропія дорівнює безумовній ентропії одного з повідомлень. Друге повідомлення при цьому інформації не додає. Дійсно, при повній статистичній залежності повідомлень умовні імовірності  P(yj/xi) і P(xi/yj) рівні або нулеві, або 1, тоді

            P(x/y)*log P(x/yj ) =  P(yj /xi )*log P(y/xi ) = 0                                                                                                  (3.8)

і, отже,   H (X,Y)  = H (X)  = H (Y).

 

3. Умовна ентропія змінюється в межах

0 <   H (Y /X )  <  H (Y).                                                                                                                 (3.9)

4. Для спільної ентропії двох джерел завжди справедливе співвідношення

H (X,Y ) ≤ H (X) + H (Y),                                                                                                               (3.10)

при цьому умова рівності виконується тільки для незалежних джерел повідомлень.

Отже, при наявності зв'язку між елементарними повідомленнями ентропія джерела знижується, причому в більшому ступені, коли сильніший зв'язок між елементами повідомлення.

Таким чином, можна зробити наступні висновки щодо ступеня інформативності джерел повідомлень:

1. Ентропія джерела і кількість інформації тим більша, чим більше розмір алфавіту джерела.

2. Ентропія  джерела  залежить  від  статистичних властивостей повідомлень. Ентропія максимальна, якщо повідомлення джерела рівноймовірні і статистично незалежні.

3. Ентропія джерела, що виробляє не рівновймовірні повідомлення, завжди менше максимальної.

4. При наявності статистичних зв'язків між елементарними повідомленнями (пам'яті джерела) його ентропія зменшується.

Як приклад розглянемо джерело з алфавітом, що складається з букв російської мови а ,б, у,.....,ю, я.  Будемо вважати для простоти, що розмір алфавіту джерела  ДО = 25 = 32

Якби всі букви російського алфавіту мали однакову імовірність  і були статистично незалежні, то середня ентропія, що приходиться на один символ, склала б

H ( x )max = log2 32 5 біт/букву.

Якщо тепер врахувати лише різну імовірність букв у тексті (а неважко перевірити, що так воно і є), розрахункова ентропія складе

H (x ) = 4,39  біт/букву.

З урахуванням кореляції (статистичного зв'язку) між двома і трьома сусідніми буквами (після  букви  “П” частіше зустрічається  “A” і майже ніколи – “Ю” і “Ц”) ентропія зменшиться, відповідно, до

H ( x )   = 3,52  біт/букву  і  H ( x )  =  3,05 біт/букву.

Нарешті, якщо врахувати кореляцію між вісьма і більше символами, ентропія зменшиться до

H (x ) = 2,0 біт/букву

і далі залишається без змін.

 

3.2 Завдання

1.    Два статистично незалежних джерела А та В визначаються матрицею ймовірностей p(ai,bj) (див. таблицю 2.1 згідно варіанту). Визначити часткову та загальну умовну ентропію, ентропію об'єднання, безумовну ентропію цих джерел, а також кількість інформації, що припадає на пару повідомлень ai,bi.

2.    Провести аналіз та оцінку одержаних результатів.

3.    Оформити звіт.

 

Таблиця 3.1 – Матриця ймовірностей p(ai,bj)

№ вар.

p(ai,bj)

№ вар.

p(ai,bj)

№ вар.

p(ai,bj)

1)

0,1

0,25

0,1

0,14

0,16

0,1

0,1

0,04

0,01

 

2)

0,1

0,24

0,1

0,14

0,17

0,1

0,1

0,04

0,01

 

3)

0,1

0,24

0,1

0,14

0,17

0,1

0,1

0,04

0,01

 

 

 

 

 

 

 

4)

0,2

0,2

0,04

0,14

0,17

0,1

0,1

0,04

0,01

 

5)

0,2

0,01

0,04

0,14

0,4

0,1

0,1

0

0,01

 

6)

0,2

0,01

0,04

0,14

0,3

0,1

0,1

0,1

0,01

 

 

 

 

 

 

 

10)

0,01

0,02

0,04

0,1

0,33

0,19

0,11

0,1

0,1

 

11)

0,01

0,15

0,04

0,1

0,23

0,19

0,08

0,1

0,1

 

12)

0,01

0,15

0,24

0,1

0,03

0,19

0,08

0,1

0,1

 

 

 

 

 

 

 

13)

0,01

0,08

0,24

0,1

0,03

0,19

0,15

0,1

0,1

 

14)

0,01

0,08

0,24

0,1

0,04

0,18

0,15

0,1

0,1

 

15)

0,01

0,08

0,23

0,1

0,05

0,18

0,15

0,1

0,1

 

 

 

 

 

 

 

16)

0,02

0,07

0,23

0,1

0,05

0,18

0,15

0,1

0,1

 

17)

0,02

0,07

0

0,29

0,05

0,18

0,15

0

0,24

 

18)

0,02

0,07

0,1

0,29

0,05

0,08

0,15

0

0,24

 

 

 

19)

0,02

0,07

0,14

0,15

0,15

0,08

0,15

0

0,24

 

20)

0,02

0,03

0,14

0,15

0,15

0,12

0,15

0

0,24

 

21)

0

0,03

0,14

0,15

0

0,12

0,15

0,41

0

 

 

 

 

 

 

 

22)

0,17

0,03

0

0,15

0

0,12

0

0,41

0,12

 

23)

0,12

0

0,1

0,15

0,03

0,12

0,05

0,31

0,12

 

24)

0,17

0

0,1

0,15

0,03

0,12

0

0,31

0,12

 

 

 

 

 

 

 

25)

0,12

0

0,07

0,15

0,06

0,12

0,05

0,31

0,12

 

26)

0,12

0,05

0,07

0,15

0,01

0,12

0,05

0,31

0,12

 

27)

0

0,21

0

0,23

0

0,25

0

0,31

0

 

 

 

3.3 Приклад виконання завдання

Два статистично незалежних джерела А та В визначаються матрицею ймовірностей p(ai,bj)

Визначити часткову та загальну умовну ентропію, ентропію об'єднання, безумовну ентропію цих джерел, а також кількість інформації, що припадає на пару повідомлень ai,bj.

Розв’язання:

Оскілки – безумовні ймовірності ймовірності, для них виконується закон

Окрема розгортка по рядках (по i) без зміни j "поглинає" алфавіт aj і дає безумовну ймовірність p(bj), тобто ймовірні стну міру джерела B:

0,2+0+0,1=0,3= p(b1) при j =1;

0+0,2+0,1=0,3= p(b2) при j =2;

0,1+0,1+0,2=0,4= p(b3) при j=3.

Перевіримо нормування:

p(b1)+p(b2)+p(b3)=0,3+0,3+0,4=1.

Окрема розгортка по рядках (по j) без зміни i "поглинає" алфавіт bj і дає безумовну ймовірність p(ai), тобто ймовірні стну міру джерела A:

0,2+0+0,1=0,3= p(a1) при j =1;

0+0,2+0,1=0,3= p(a2) при j =2;

0,1+0,1+0,2=0,4= p(a3) при j=3.

Перевіримо нормування:

p(a1)+p(a2)+p(a3)=0,3+0,3+0,4=1.

 

З урахуванням p(b|a)=p(ab)/p(a); p(a/b)=p(ab)/p(b) дістаємо матрицю умовних ймовірностей:

Перевірка закону нормування дає позитивну відповідь, тобто

 при j=1;

 при j=2;

при j=3.

Отже, кожний  рядок є розподілом повідомлень ai, спотворений через статистичний вплив повідомлень:

.

Перевірка закону нормування дає позитивну відповідь, тобто

 при i=1;

 при i =2;

при i=3.

Таким чином, кожний  рядок є розподілом повідомлень bi, спотворений через статистичний вплив повідомлень.

Тепер маючи відповідні данні розраховуємо безумовну ентропію джерела A:

Аналогічно обчислимо безумовну ентропію джерела B:

Часткова ентропія джерела А за

 з урахуванням  становитиме

Загальна умовна ентропія джерела А відносно джерела В згідно 

Часткова ентропія джерела А за  з урахуванням 

становитиме

Загальна умовна ентропія джерела B відносно джерела A згідно 

Ентропія об'єднання цих джерел, враховуючи  становить

 

Кількість інформації, що припадає на одне повідомлення

ЛАБОРАТОРНА РОБОТА №4

 

Тема: ХАРАКТЕРИСТИКИ ДИСКРЕТНОГО ДЖЕРЕЛА ПОВІДОМЛЕНЬ

ТА КАНАЛУ ПЕРЕДАЧІ ІНФОРМАЦІЇ

 

Мета роботи: навчатися визначати продуктивність дискретного джерела повідомлень, швидкість передачі інформації каналами зв’язку

 

4.1 Теоретичні відомості

 

1. Продуктивність дискретного джерела інформації. Швидкість передачі інформації

Нехай дискретне джерело X видає послідовність повідомлень {xi}, заданих рядом ймовірностей {pi}.

Якщо джерелом вибирається одне повідомлення xi, то ним виробляється певна кількість інформації. Тоді швидкість утворення джерелом інформації повідомлень - продуктивність джерела щодо конкретного повідомлення можна визначити так:

де через ti позначено проміжок часу вибору повідомлення xi.

Оскільки джерелом за деякий часовий інтервал вибирається велика кількість повідомлень і в загальному випадку ti¹tj, то продуктивність джерела інформації прийнято характеризувати середнім значенням

де tсер – середній час вибору джерелом одного повідомлення.

Отже, продуктивність джерела інформації визначається середньою кількістю інформації, що виробляється джерелом за одиницю часу.

Повідомлення xi передається по каналу зв'язку спостерігачеві Y, роль якого відіграє приймальний пристрій. Вибір повідомлень yjÎYджерелом Y характеризує процес передачі інформації по каналу зв'язку від джерела X на вихід джерела Y. При цьому взаємна кількість інформації I(X, Y) - це середня кількість інформації про стан джерела X, що міститься в одному повідомленні джерела Y.

Оскільки на вибір кожного повідомлення yj джерелом Y витрачається час t, то швидкість передачі інформації по каналу зв'язку знаходиться за формулою

Надмірність ( надлишок ) R  дискретного джерела інформації дає відносну оцінку використання потенційних можливостей джерела з алфавітом заданої потужності :

R =

H max – H

=

log 2 M – H

=  1 –

     H

 

 

    H max

  log 2 

log 2 

 

 

Надмірність може приймати значення від 0 до 1. Вона дорівнює нулю, якщо H = H max ; в цьому випадку дискретне джерело інформації буде виробляти максимально можливий інформаційний потік.

 

2 Інформаційні втрати при передачі інформації по дискретному каналу зв'язку

Математично канал дискретної інформації описується ансамблем повідомлень на вході {xi}, {pi} та йому відповідними йому значеннями на виході {yj}, а також набором умовних ймовірностей p(yj/xi) вибору сигналу yj на виході при передачі сигналу xi.

Задача каналу зв'язку полягає в тому, щоб отримати однозначну відповідність повідомлення yi  повідомленню xi, тобто повинна виконуватися умова p(yi/xi)=1 при i=j і p(yj/xi)=0 при i¹j. У цьому випадку канал зв'язку називається каналом без шуму.

Виконання умов використання каналу без шуму означає повний збіг ансамблів X і Y, тобто повний статистичний взаємозв'язок джерел. Звідси випливає, що

H(X/Y)=H(Y/X)=0

Тоді середня кількість інформації на одне повідомлення джерела X, яка дорівнює ентропії H(X), при повній відсутності інформаційних втрат відповідає такій самій кількості прийнятої інформації H(Y), тобто

I(X,Y)=H(X)=H(Y)=H(X,Y).

Отже, при відсутності завад кількість переданої інформації дорівнює ентропії об'єднання двох джерел або безумовної ентропії одного з них.

При високому рівні завад спостерігається повна статистична незалежність джерел X і Y, тобто

H(X/Y)=H(X),

H(Y/X)=H(Y),

H(X,Y)= H(X)+H(Y).

У даному випадку через сильний вплив завад порушується взаємозв'язок джерел, і інформація від джерела X джерелу Y не передається, отже,

I(X, Y)= 0.

 У проміжному випадку неабсолютного статистичного взаємозв'язку джерел X, Y завади деякою мірою спотворюють передані повідомлення. При цьому умовна ентропія змінюється в межах від нуля (при повній статистичній залежності джерел) до безумовної ентропії (за відсутності статистичної залежності джерел), тобто

0 £ H(X/Y) £ H(X),

0 £ H(Y/X) £ H(Y).

Кількість інформації, що передається джерелом X спостерігачу Y, можна визначити так. Якщо джерелом вибрано повідомлення xiÎX, то ним, в середньому, передається кількість інформації H(X). Джерело Y, вибравши повідомлення yjÎY, за умови порушення повної статистичного залежності джерел X і Y виробляє певну кількість інформації H(X/Y).

Після вибору повідомлення yjÎY джерелом Y приймається рішення щодо того, яке з повідомлень xiÎX передане. Прийнявши це рішення, джерело Y виробляє кількість інформації про стан джерела X, яка дорівнює HX. Проте до цього джерело Y вже має H(X/Y) бітів інформації про X, тому кількість переданої по каналу зв'язку інформації як кількість нового відсутнього знання визначається різницею HX і H(X/Y):

I(X, Y)=H(X)-H(X/Y).                                                                                     (1)

Отже, інформаційні втрати в каналі визначаються умовною ентропією одного джерела щодо іншого, а кількість переданої інформації - безумовною ентропією джерела і інформаційними втратами за формулою (1).

З властивості симетричності взаємної ентропії випливає рівність

H(X)+H(Y/X)=H(Y)+H(X/Y).                                                                            (2)

Віднявши від обох частин цієї рівності суму H(X/Y)+H(Y/X), дістанемо

H(X)-H(X/Y)=H(Y)-H(Y/X).                                                                                  (3)

Звідси випливає властивість симетричності взаємної інформації

I(X, Y)=I(Y, X).                                                                                     (4)

  Скориставшись виразами (2), (3), (4), маємо

I(X,Y)=HX-H(X/Y)=HX-(H(X,Y)-HY)=HX+HY-H(X,Y),                                                     (5)

I(Y,X)=HY-H(Y/X)=HY-(H(Y,X)-HX)=HY+HX-H(Y,X),                                                      (6)

чим доводяться властивість 4 кількості інформації.

 

3 Пропускна здатність дискретного каналу. Основна теорема про кодування дискретного джерела

Максимально можлива швидкість передачі інформації по каналу називається пропускною здатністю, або ємністю  каналу зв'язку С.

.                                                                   (7)

Очевидно, що вираз (7) досягає максимуму при абсолютній статистичній залежності джерел XY, тобто за відсутності або при малому рівні завад. У цьому випадку H(X/Y)=0, і оскільки ентропія максимальна у разі рівноімовірних повідомлень, то формула (7) набуває вигляду:

        .                                                                                      (8)

Вираз (1.50) визначає пропускну здатність за відсутності завад.

У разі, коли в каналі наявні завади, умовна ентропія на його вході і виході H(X/Y) знаходиться в діапазоні 0 £ H(X/Y) £ H(X). Тоді пропускна здатність каналу визначається за формулою

 .                                                                                   (9)

При зменшенні рівня завад пропускна здатність каналу C прямує до максимального значення (8), а при збільшенні рівня завад – до нуля.

Основна теорема кодування дискретного джерела, сформульована і доведена К. Шенноном1, полягає в такому.

Припустимо, що при передачі інформації використовується канал без шуму. Розглянемо безнадмірні (рівноймовірні) вхідні повідомлення, що характеризуються максимальною ентропією H(X)max. У цьому випадку може бути досягнута максимальна швидкість передачі в каналі

,                                                                             (10)

де V=1/T; T - тривалість передачі одного елементарного повідомлення (символу) xilogk - максимальна ентропія джерела з алфавітом об'ємом k.

  Якщо статистична надлишковість джерела інформації більше нуля, то швидкість передачі інформації по каналу

.                                                                                          (11)

Як доведено К. Шенноном1при будь-якій статистичній надмірності джерела інформації існує такий спосіб кодування повідомлень, при якому може бути досягнута швидкість передачі інформації по каналу без шуму, скільки завгодно близька до його пропускної здатності.Таким чином, умовою узгодженості джерела інформації і каналу передачі є відповідність продуктивності першого пропускній здатності другого.

Теорема Шеннона про кодування дискретного джерела за відсутності завад1 стверджує про таке.

Якщо пропускна здатність каналу без шуму перевищує швидкість створення джерелом повідомлень - його продуктивність, тобто

,

то існує спосіб кодування/ декодування повідомлень джерела з ентропією H(X), що забезпечує скільки завгодно високу надійність зіставлення прийнятих кодових комбінацій переданим, інакше - такого способу немає.

За наявності завад в каналі основна теорема кодування узагальнюється такою теоремою:

Якщо для будь-якого повідомлення дискретного джерела X задана ймовірність його спотворення в каналі e, то для будь-якого e > 0 існує спосіб передачі інформації зі швидкістю

,

скільки завгодно близькою до

,

при якому ймовірність помилки в каналі буде менше e. Цей спосіб утворює завадостійкий код.

Фано доведена зворотна теорема кодування джерела за наявності завад[1]:

Якщо швидкість передачі інформації по каналу зв'язку з шумом то можна знайти таке e > 0, що ймовірність помилки при передачі повідомлення при будь-якому методі кодування/ декодування буде не менше e (очевидно e зростає із зростанням ).

 

ЛАБОРАТОРНА РОБОТА №5

 

Тема: КОДУВАННЯ ІНФОРМАЦІЇ. КОД ШЕННОНА-ФАНО.

 

Мета роботи: вивчення поняття кодування, порівняння первинних рівномірних та нерівномірних кодів, побудованих за різними методиками.

 

5.1 Теоретичні відомості

5.1.1 Кодування інформації

Під кодуванням у загальному випадку розуміють перетворення алфавіту повідомлення Aі}, ( i = 1,2…K) в алфавіт деяким чином обраних кодових символів Â{aj}, ( j = 1,2…N)... Звичайно (але не обов'язково) розмір алфавіту кодових  символів  Âj} менше або набагато менше розміру алфавіту джерела Ai}.

Кодування повідомлень може переслідувати різні цілі. Наприклад, це  кодування з метою засекречування переданої інформації. При цьому елементарним повідомленням хi з алфавіту Aiставляться у відповідність послідовності, наприклад, цифр або букв зі спеціальних кодових таблиць, відомих лише відправникові й одержувачеві інформації.

Іншим прикладом кодування може служити перетворення дискретних повідомлень хi  з  одних систем числення в інші (з десяткової в двійкову,  і т.д., з непозиційної в позиційну, перетворення буквеного алфавіту в цифровий і т.д.).

Кодування в  каналі, або завадостійке кодування інформації, може бути використане для зменшення кількості помилок, що виникають при передачі по каналі з перешкодами.

Нарешті, кодування повідомлень може вироблятися з метою скорочення обсягу  інформації і підвищення швидкості її передачі або скорочення смуги частот, необхідних для передачі. Таке кодування називають ощадливим, безнадлишковим,  або ефективним кодуванням, а  також стисненням даних. У даному розділі буде йти мова саме про такий рід кодуванні.

Перш ніж перейти до питання ефективного кодування, коротко пояснимо суть самої процедури кодування.

Будь-яке дискретне повідомлення хi з алфавіту джерела  A{ x}  обсягом у  символів можна закодувати послідовністю відповідним чином обраних кодових символів а з алфавіту Â{ а}.

Наприклад, будь-яке число (а  xi можна вважати числом) можна записати в заданій позиційній системі числення в такий спосіб:

xi = M = an-1×m n-1 + an-2×m n-2 +…+a0×m0,

де m – основа  системи числення; a… an-1  - коефіцієнти при степенях mаÌ0, m – 1.

Нехай, наприклад,  значення  хi = M = 59 , тоді  його  код по основі  m = 8, буде мати вигляд

M = 59 = 7·81  + 3·80 =738.

Код того ж числа, але по основі m = 4  буде виглядати в такий спосіб: 

M = 59 = 3×42 + 2×41+ 3×40 = 3234

Нарешті, якщо основа коду  m = 2,       то

M = 59  = 1×25 + 1×24 + 1×23 + 0×22 + 1×21 + 1×20  = 1110112.

Таким чином, числа 73323 і 111011 можна вважати, відповідно, вісімковим, четвірковим і двійковим кодами числа M = 59.

В принципі основа коду може бути будь-якою, однак найбільше поширення одержали дввійкові коди, або коди з основою 2, для яких розмір алфавіту кодових символів Â{ адорівнює двом, аj Ì 0,1. Двійкові, тобто коди, що містять тільки нулі й одиниці, дуже просто формуються і передаються по каналах зв'язку і, головне, є внутрішньою мовою цифрових ЕОМ, тобто без усяких перетворень можуть оброблятися цифровими засобами. Тому, коли мова йде про кодування і коди, найчастіше мають на увазі саме двійкові коди.  Надалі будемо розглядати в основному двійкові кодування.

 

5.1.2 Способи представлення кодів

Найпростішим способом представлення або завдання кодів є кодові таблиці, що ставлять у відповідність повідомленням хi  відповідні їм коди (таблиця 5.1).

Таблиця 5.1 – Кодова таблиця для алфавіту з 8 символів кирилиці

Буква хi

Число   хi

Код

з  основою 10

Код

з  основою 4

Код

з  основою 2

А

0

0

00

000

Б

1

1

01

001

У

2

2

02

010

Г

3

3

03

011

Д

4

4

10

100

Е

5

5

11

101

Ж

6

6

12

110

З

7

7

13

111

 

 

Іншим наочним і зручним способом опису кодів є їхнє представлення у виді кодового дерева (рисунок 5.1).

Для того, щоб побудувати кодове дерево для  даного коду, починаючи з деякої точки - кореня кодового дерева - проводяться галузі - 0 або 1.  На вершинах кодового дерева знаходяться букви алфавіту джерела, причому  кожній  букві відповідають своя вершина і свій шлях від кореня до вершини. Наприклад, букві А відповідає код  000,  букві В – 010, букві Е – 101 і т.д.

Корінь

 

0                                 1

0                          1                       0                          1

 

 

1          0          1          0          1             0            1             0

А         Б         В         Г          Д            Е           Ж           З

1          2          3          4          5             6             7            8

 

 

 

 

 
 

Рисунок 5.1 – Кодове дерево для алфавіту з 8 символів кирилиці

 

Код, отриманий з використанням кодового дерева, зображеного на рис.5.1,  є рівномірним трьохрозрядним кодом

Рівномірні коди дуже широко використовуються в силу своєї простоти і зручності процедур кодування-декодування: кожній букві – однакове число біт; прийняв задане число біт – шукай у кодовій таблиці відповідну букву.

 

5.1.3 Нерівномірні коди

Поряд з рівномірними кодами можуть застосовуватися і нерівномірні коди, коли кожна буква з алфавіту джерела кодується різним числом символів, приміром,  А -  10,  Б – 110,  У – 1110  і т.д.

Кодове дерево для нерівномірного кодування може виглядати, наприклад, так, як показано на рисунку 5.2.

При використанні цього коду буква  А буде кодуватися, як  1, Б - як 0,  У – як  11 і т.д. Однак можна помітити, що,  закодувавши, приміром,  текст  АББА =  1001 , ми не зможемо його однозначно декодировать, оскільки такий же код дають фрази:  ЖА = 1001, АЕА = 1001 і ГД = 1001.

Такі коди, що не забезпечують однозначного декодування, називаються  непрефіксними, кодами і не можуть на практиці застосовуватися без спеціальних поділяючих символів. Прикладом застосування такого типу кодів може служити азбука Морзе.

Рисунок 5.2 – Кодове дерево для нерівномірного кодування

 

В азбуці Морзе кожній букві або цифрі повідомлення ставиться у відповідність  деяка послідовність точок (короткий сигнал) і тире (в три рази довший), які розділяють короткими паузами; пропуск між буквами  відмічається довгою паузою, а пропуск між словами ще в два рази довшою паузою. Хоч цей код використовує тільки точки і тире його можна вважати трійковим, так як кожне закодоване повідомлення  містить три елементарних сигнали: короткі сигнали (точки), довгі (тире), довгі паузи.

Код Бодо у відповідність кожній букві ставить послідовності з п’яти елементарних сигналів – посилок сигналу і паузи одинакової довжини. Так як при цьому всі букви передаються комбінаціями сигналів одної довжини, то в коді Бодо не потрібно спеціального знаку , який відділяє одну букву від іншої – наперед відомо, що через кожні п’ять елементарних сигналів закінчується одна буква і починається інша.

Можна побудувати нерівномірні коди, що допускають однозначне декодування. Для цього необхідно, щоб усім буквам алфавіту відповідали лише вершини кодового дерева, наприклад, такого, як показано на  рисунку 5.3.  Тут жодна кодова комбінація не є початком іншої, більш довгої, тому неоднозначності декодування не буде. Такі нерівномірні коди називаються префіксними.

 

Рисунок 5.3 – Кодове дерево для коду що допускає однозначне декодування

 

Прийом і декодування нерівномірних кодів – процедура набагато більш складна, ніж для рівномірних. При цьому ускладнюється апаратура декодування і синхронізації, оскільки надходження елементів повідомлення (букв) стає нерегулярним. Так, приміром, прийнявши перший 0, декодер повинен подивитися в кодову таблицю і з'ясувати, якій букві відповідає прийнята послідовність. Оскільки такої букви немає, він повинен чекати приходу наступного символу. Якщо наступним символом буде 1, тоді декодування першої букви завершиться – це буде Б, якщо ж другим прийнятим символом знову буде  0, прийдеться чекати третього символу і т.д.

Розглянемо приклад  кодування повідомлень  хi   з  алфавіту обсягом   K = 8  за допомогою довільного n-розрядного двікового коду.

Нехай джерело повідомлення видає деякий текст з алфавітом від  А до З и однаковою імовірністю букв  Р(х) = 1/8.

Кодуючий пристрій  кодує ці букви рівномірним трьохрозрядним кодом (див. табл. 3.1).

Визначимо основні інформаційні характеристики  джерела з таким алфавітом:

– ентропія джерела          ;

– надмірність джерела                 ;

– середнє число символів у коді           ;

– надмірність коду                         .

Таким чином, при кодуванні повідомлень з рівноймовірними буквами надмірність обраного (рівномірного) коду виявилася рівної нулеві.

 

Нехай тепер імовірності появи в тексті різних букв будуть різними (таблиця 3.2).

Таблиця 5.2 – Імовірності появи символів

А

Б

У

Г

Д

Е

Ж

З

Ра=0.6

Рб=0.2

Рв=0.1

Рг=0.04

Рд=0.025

Ре=0.015

Рж=0.01

Рз=0.01

 

Ентропія джерела  в цьому випадку,  природно, буде меншою і складе    = 1.781.

Середнє число символів на одне повідомлення при використанні того ж рівномірного трьохрозрядного коду

Надмірність коду в цьому випадку буде

,

або досить значною величиною (у середньому 4 символи з 10 не несуть ніякої інформації).

 

5.1.4 Статистичне кодування

У зв'язку з тим, що при кодуванні нерівноймовірних повідомлень рівномірні коди мають велику надмірність, було запропоновано використовувати нерівномірні коди, тривалість кодових комбінацій яких була б погоджена з імовірністю випадання різних букв. Таке кодування називається статистичним.

Нерівномірний код при статистичному кодуванні вибирають так, щоб більш ймовірні букви передавалися за допомогою більш коротких комбінацій коду, менш ймовірні - за допомогою більш довгих. У результаті зменшується середня довжина кодової групи в порівнянні з випадком рівномірного кодування. Приклад нерівномірного префіксного коду подано в таблиці 5.3.

 

Таблиця 5.3 – Приклад нерівномірного префіксного коду

Буква

Імовірність

Рi

Кодове дерево

Код

ni

n× Pi

А

Б

У

Г

Д

Е

Ж

З

0.6

0.2

0.1

0.04

0.025

0.015

0.01

0.01

1

01

001

0001

00001

000001

0000001

00000001

1

2

3

4

5

6

7

8

0.6

0.4

0.3

0.16

0.125

0.08

0.07

0.08

 

Середнє число символів для такого коду складе    

а надмірність коду             

тобто на порядок менше, ніж при рівномірному кодуванні.

 

5.1.5 Код Шеннона-Фано

Іншим найпростішим способом статистичного кодування є кодування по методу Шеннона-Фано. Кодування відповідно до цього алгоритму виробляється так:

– спочатку всі букви з алфавіту повідомлення записують у порядку зменшення їхніх імовірностей;

– потім усю сукупність букв розбивають на дві приблизно рівні по сумі імовірностей групи;  одній з них (у групі може бути будь-яке число символів, у тому числі – один) привласнюють символ “1”, іншої  - “0”;

– кожну з цих груп знову розбивають (якщо це можливо) на дві частин і кожній з частин привласнюють  “1” і “0” і т.д.

Процедура кодування по методу Шеннона-Фано подана в таблиці 5.4.

 

Таблиця 5.4 – Процедура кодування по методу Шеннона-Фано

Буква

Р(х)

I

II

III

IV

V

Код

ni × Pi

А

0.6

1

 

 

 

 

1

0.6

Б

0.2

0

1

1

 

 

011

0.6

В

0.1

0

 

 

010

0.3

Г

0.04

0

1

 

 

001

0.12

Д

0.025

0

1

 

0001

0.1

Е

0.015

0

 

00001

0.075

Ж

0.01

1

000001

0.06

З

0.01

0

000000

0.06

 

Для отриманого в такий спосіб  коду середнє число двійкових символів, що приходяться на одну букву,  дорівнює

,

Надмірність коду складе             

Тобто також істотно меншу величину, ніж для рівномірного коду.

 

5.2 Завдання

1. а) Побудувати рівномірний код  

    б) Побудувати оптимальний нерівномірний код Шеннона–Фано для передачі M повідомлень за допомогою коду з алфавітом а, якщо повідомлення на виході з джерела з’являються з ймовірностями p(xi).

   в) Побудувати кодове дерево для отриманого коду.

Використати варіанти завдань наведені в таблиці 5.5.

Таблиця 5.5 – Розподіл дискретної випадкової величини

Вар.

M

а

P(x1)

P(x2)

P(x3)

P(x4)

P(x5)

P(x6)

P(x7)

P(x8)

P(x9)

P(x10)

1

10

4

0,22

0,1

0,11

0,05

0,08

0,32

0,06

0,03

0,01

0,02

2

9

4

0,21

0,11

0,13

0,1

0,2

0,11

0,04

0,06

0,04

3

8

4

0,2

0,12

0,05

0,13

0,14

0,15

0,1

0,11

4

10

3

0,19

0,13

0,09

0,1

0,11

0,14

0,03

0,1

0,04

0,07

5

9

3

0,18

0,14

0,4

0,11

0,01

0,03

0,04

0,04

0,05

6

8

3

0,17

0,15

0,1

0,03

0,15

0,3

0,02

0,08

7

10

5

0,36

0,18

0,19

0,04

0,05

0,05

0,012

0,05

0,05

0,018

8

9

5

0,3

0,15

0,16

0,06

0,16

0,1

0,05

0,01

0,01

9

8

5

0,11

0,09

0,08

0,15

0,06

0,16

0,13

0,22

10

10

4

0,06

0,08

0,3

0,12

0,14

0,09

0,03

0,06

0,08

0,04

11

9

4

0,15

0,35

0,01

0,06

0,11

0,15

0,07

0,02

0,08

12

8

4

0,08

0,076

0,4

0,032

0,25

0,06

0,05

0,052

13

10

3

0,22

0,1

0,05

0,015

0,008

0,25

0,15

0,1

0,05

0,057

14

9

3

0,05

0,09

0,04

0,08

0,07

0,15

0,36

0,15

0,01

15

8

3

0,05

0,2

0,1

0,3

0,15

0,13

0,025

0,045

16

10

4

0,2

0,11

0,3

0,2

0,02

0,03

0,05

0,01

0,06

0,02

17

9

4

0,31

0,106

0,2

0,14

0,03

0,12

0,06

0,02

0,014

18

8

4

0,39

0,1

0,04

0,16

0,09

0,08

0,13

0,01

19

10

3

0,2

0,01

0,16

0,4

0,02

0,03

0,08

0,01

0,07

0,02

20

9

3

0,31

0,2

0,1

0,05

0,04

0,08

0,03

0,01

0,18

21

8

3

0,39

0,2

0,1

0,05

0,09

0,08

0,08

0,01

22

10

5

0,25

0,11

0,15

0,15

0,02

0,02

0,06

0,03

0,18

0,03

23

9

5

0,29

0,2

0,04

0,05

0,11

0,08

0,13

0,01

0,09

24

8

5

0,27

0,2

0,2

0,15

0,03

0,08

0,06

0,01

25

10

4

0,31

0,006

0,15

0,1

0,12

0,02

0,03

0,03

0,104

0,13

26

9

4

0,29

0,2

0,04

0,06

0,09

0,08

0,149

0,01

0,081

27

8

4

0,26

0,19

0,1

0,15

0,15

0,08

0,058

0,012

28

10

3

0,35

0,15

0,15

0,08

0,07

0,07

0,05

0,03

0,03

0,02

29

9

3

0,37

0,16

0,14

0,11

0,09

0,06

0,03

0,02

0,02

30

9

3

0,31

0,2

0,1

0,05

0,04

0,08

0,03

0,01

0,18

 

 

2. Задати дискретне джерело повідомлень, що вибирає повідомлення з множини літер прізвища, імені, по-батькові українською мовою (використати дані лабораторної роботи №1).  Для ансамблю повідомлень побудувати коди:

-          рівномірний двійковий код з мінімальною довжиною,

-          двійковий ОНК Шеннона-Фано,

Коди представити у табличній формі та у вигляді кодового дерева.

 

5.3  Приклади  розв’язання  задач

1. Побудувати оптимальний нерівномірний код (ОНК) Шеннона–Фано для передачі 13 повідомлень за допомогою коду з алфавітом 4, якщо повідомлення над виході з джерела з’являються з ймовірностями 0.25, 0.1, 0.05, 0.02, 0.03, 0.05, 0.11, 0.04, 0.01, 0,15, 0.01, 0,08, 0.1.

Розв’язання:

1) Розташуємо множину повідомлень у порядку спадання ймовірностей.

2) Визначаємо квант поділу 1/а=1/4=0.25.

3) Впорядковані за ймовірністю розбиваємо , по можливості, на 4 рівно ймовірні групи: ;

4) За результатами першого поділу груп як перший символ кодових комбінацій присвоюємо послідовно якісні ознаки алфавіту а згідно з 3-ю процедурою першої універсальної методики побудови ОНК.

5) Утворені групи, крім першої, розбиваємо на підгрупи. Друга та третя групи мають до 4-х повідомлень, тому як другий символ кодових комбінацій їм присвоюємо відповідно три та чотири якісні ознаки алфавіту а.

6) Четверта група має 7 повідомлень, тому розбиваємо її на рівно ймовірні підгрупи. Квант поділу 0,25:4=0,0625. Поділ присвоєння ознак виконуємо доти, поки після чергового поділу в утворених підгрупах залишиться не більше як одне повідомлення.

Отриманий код наведено в таблиці 5.6.

Таблиця 5.6 – Оптимальний нерівномірний код Шеннона–Фано

Номер повідомлення

Ймовірність повідомлення

Кодова комбінація ОНК

   

1

0,25

0

 

2

0,15

10

 

3

0,11

11

 

4

0,1

20

 

5

0,1

21

 

6

0,08

22

 

7

0,05

300

 

8

0,05

301

 

9

0,04

310

 

10

0,03

311

 

11

0,02

312

 

12

0,01

3130

 

13

0,01

3131

 

Побудуємо кодове дерево (рисунок 5.4).

Рисунок 5.4 – Кодове дерево побудоване за методикою Шенона-Фано

 

2. Джерело повідомлень   ІВАНОВ_ІВАН_ІВАНОВИЧ

 

A={І, В, А, Н, О, И, Ч, _}

літера

І

В

А

Н

О

И

Ч

_

pi

0.15

0.25

0.15

0.15

0.10

0.05

0.05

0.10

 

Рівномірний двійковий код з мінімальною довжиною

Кількість різних повідомлень, що генерує джерело, k=8. Тому для рівномірного двійкового коду мінімальна довжина кодового слова складає

                                                      n=nсер=3

Кодова таблиця має вигляд      

літера

код

І

000

В

001

А

010

Н

011

О

100

И

101

Ч

110

_

111

 

Двійковий ОНК Шеннона-Фано

Кодова таблиця має вигляд

літера

pi

Поділ на групи

Код

перша

друга

третя

четверта

В

0,25

0,55

 

0

0,25

0

 

 

00

І

0,15

0,30

1

0,15

0

010

А

0,15

0,15

1

011

Н

0,15

0,45

 

 

1

0,25

0

0,15

0

100

О

0,10

0,10

1

101

_

0,10

0,20

 

1

0,10

0

110

И

0,05

0,10

1

0,05  0

1110

Ч

0,05

0,05  1

1111

Кодове дерево має вигляд

Для того щоб перевірити оптимальність коду відносно довжини кодових комбінацій, визначаємо середню довжину nсер кодової комбінації ОНК. У разі оптимальності ця довжина не повинна перевищувати довжину рівномірного коду, яким можна закодувати k=8 повідомлень, тобто qn= 2n = 8(n = 3):

nсер = = 0,25 • 2 + (0,15 + 0,15 + 0,15 + 0,1 + 0,1) • 3 + (0,05 + 0,05) • 4 = 2,85 < 3.

ЛАБОРАТОРНА РОБОТА №6

 

Тема: КОДУВАННЯ ІНФОРМАЦІЇ. ОПТИМАЛЬНИЙ КОД ХАФФМАНА.

 

Мета роботи: порівняння первинних рівномірних та нерівномірних кодів, побудованих за різними методиками.

 

6.1 Теоретичні відомості

Оптимальний код Хаффмана

Один з перших алгоритмів ефективного кодування інформації був запропонований Д. А. Хаффманом в 1952 році. Ідея алгоритму полягає в наступному: знаючи ймовірності символів в повідомленні, можна описати процедуру побудови кодів змінної довжини, що складаються з цілого кількості бітів. Символам з більшою ймовірністю присвоюються більш короткі коди. Коди Хаффмана володіють властивістю префіксності, що дозволяє однозначно їх декодувати. Класичний алгоритм Хаффмана на вході отримує таблицю частот входження символів у повідомленні. Далі на підставі цієї таблиці будується дерево кодування Хаффмана.

§  Символи вхідного алфавіту утворюють список вільних вузлів. Кожен лист має вагу, який може дорівнювати або ймовірності, або кількості входжень символу в стиснутому повідомленні.

§  Вибираються два вільних вузла дерева з найменшими вагами.

§  Створюється їх батько з вагою, рівною їх сумарній вазі.

§  Батько додається в список вільних вузлів, а двоє його дітей (нащадків) видаляються з цього списку.

§  Одній дузі, котра виходить з батька, ставиться у відповідність біт 1, іншій - біт 0.

§  Кроки, починаючи з другого, повторюються до тих пір, поки в списку вільних вузлів не залишиться тільки один вільний вузол. Він і буде вважатися коренем дерева.

Припустимо, у нас є наступна таблиця частот:

Цей процес можна представити як побудова дерева, коріння якого - символ з сумою ймовірностей об'єднаних символів, що вийшов при об'єднанні символів з останнього кроку, його n0 нащадків - символи з попереднього кроку і т. д. Щоб визначити код для кожного із символів, що входять до повідомлення, ми повинні пройти шлях від листа дерева, відповідного цьому символу, до кореня дерева, накопичуючи біти при переміщенні по гілках дерева. Отримана таким чином послідовність бітів є кодом даного символу, записаним у зворотному порядку. Для даної таблиці символів коди Хаффмана будуть виглядати наступним чином.

Оскільки жоден з отриманих кодів не є префіксом іншого, вони можуть бути однозначно декодовані при читанні їх з потоку. Крім того, найбільш частий символ повідомлення А закодований найменшою кількістю біт, а найбільш рідкісний символ Д - найбільшим. При цьому загальна довжина повідомлення, що складається з наведених у таблиці символів, складе 87 біт (у середньому 2,2308 біта на символ). При використанні рівномірного кодування загальна довжина повідомлення склала б 117 біт (рівно 3 біта на символ). Зауважимо, що ентропіяджерела, незалежним чином породжує символи з зазначеними частотами складає ~ 2,1858 біта на символ, тобто надмірність побудованого для такого джерела коду Хаффмана, що розуміється, як різниця середнього числа біт на символ від ентропії, становить менше 0,05 біт на символ. Класичний алгоритм Хаффмана має ряд істотних недоліків. Для відновлення вмісту стиснутого повідомлення декодер повинен знати таблицю частот, якою користувався кодер. Отже, довжина стиснутого повідомлення збільшується на довжину таблиці частот, яка повинна надсилатися попереду даних, що може звести нанівець всі зусилля зі стиснення повідомлення. Крім того, необхідність наявності повної частотної статистики перед початком власне кодування вимагає двох проходів за повідомленням: одного для побудови моделі повідомлення (таблиці частот і дерева), другий для себе власне кодування.

 

6.2 Завдання

1. Побудувати рівномірний та  оптимальний нерівномірний код Хаффмана для передачі M повідомлень за допомогою коду з алфавітом а, якщо повідомлення над виході з джерела з’являються з ймовірностями p(xi). Побудувати кодове дерево для отриманого коду. Провести порівняльний аналіз та оцінку одержаних результатів.  Використати варіанти завдань наведені в таблиці 6.1.

Таблиця 6.1 – Розподіл дискретної випадкової величини

Вар.

M

а

P(x1)

P(x2)

P(x3)

P(x4)

P(x5)

P(x6)

P(x7)

P(x8)

P(x9)

P(x10)

1

10

4

0,22

0,1

0,11

0,05

0,08

0,32

0,06

0,03

0,01

0,02

2

9

4

0,21

0,11

0,13

0,1

0,2

0,11

0,04

0,06

0,04

3

8

4

0,2

0,12

0,05

0,13

0,14

0,15

0,1

0,11

4

10

3

0,19

0,13

0,09

0,1

0,11

0,14

0,03

0,1

0,04

0,07

5

9

3

0,18

0,14

0,4

0,11

0,01

0,03

0,04

0,04

0,05

6

8

3

0,17

0,15

0,1

0,03

0,15

0,3

0,02

0,08

7

10

5

0,36

0,18

0,19

0,04

0,05

0,05

0,012

0,05

0,05

0,018

8

9

5

0,3

0,15

0,16

0,06

0,16

0,1

0,05

0,01

0,01

9

8

5

0,11

0,09

0,08

0,15

0,06

0,16

0,13

0,22

10

10

4

0,06

0,08

0,3

0,12

0,14

0,09

0,03

0,06

0,08

0,04

11

9

4

0,15

0,35

0,01

0,06

0,11

0,15

0,07

0,02

0,08

12

8

4

0,08

0,076

0,4

0,032

0,25

0,06

0,05

0,052

13

10

3

0,22

0,1

0,05

0,015

0,008

0,25

0,15

0,1

0,05

0,057

14

9

3

0,05

0,09

0,04

0,08

0,07

0,15

0,36

0,15

0,01

15

8

3

0,05

0,2

0,1

0,3

0,15

0,13

0,025

0,045

16

10

4

0,2

0,11

0,3

0,2

0,02

0,03

0,05

0,01

0,06

0,02

17

9

4

0,31

0,106

0,2

0,14

0,03

0,12

0,06

0,02

0,014

18

8

4

0,39

0,1

0,04

0,16

0,09

0,08

0,13

0,01

19

10

3

0,2

0,01

0,16

0,4

0,02

0,03

0,08

0,01

0,07

0,02

20

9

3

0,31

0,2

0,1

0,05

0,04

0,08

0,03

0,01

0,18

21

8

3

0,39

0,2

0,1

0,05

0,09

0,08

0,08

0,01

22

10

5

0,25

0,11

0,15

0,15

0,02

0,02

0,06

0,03

0,18

0,03

23

9

5

0,29

0,2

0,04

0,05

0,11

0,08

0,13

0,01

0,09

24

8

5

0,27

0,2

0,2

0,15

0,03

0,08

0,06

0,01

25

10

4

0,31

0,006

0,15

0,1

0,12

0,02

0,03

0,03

0,104

0,13

26

9

4

0,29

0,2

0,04

0,06

0,09

0,08

0,149

0,01

0,081

27

8

4

0,26

0,19

0,1

0,15

0,15

0,08

0,058

0,012

28

10

3

0,35

0,15

0,15

0,08

0,07

0,07

0,05

0,03

0,03

0,02

29

9

3

0,37

0,16

0,14

0,11

0,09

0,06

0,03

0,02

0,02

30

9

3

0,31

0,2

0,1

0,05

0,04

0,08

0,03

0,01

0,18

 

 

2. Побудовати двійковий код Хаффмана для прізвища, імені, по-батькові українською мовою. Знайти середню довжину коду та надмірність коду.

3. Оформити звіт.

 

6.3 Приклад виконання завдання

Побудувати оптимальний нерівномірний код (ОНК) Хаффмана для передачі 13 повідомлень за допомогою коду з алфавітом 4, якщо повідомлення над виході з джерела з’являються з ймовірностями 0.25, 0.1, 0.05, 0.02, 0.03, 0.05, 0.11, 0.04, 0.01, 0,15, 0.01, 0,08, 0.1.

Розв’язання:

1)    Множину з М = 13 повідомлень розташовуємо в порядку спадання ймовірностей.

2)    Оскільки а = 4, об’єднуємо останні 4 повідомлення й утворюємо нове умовне повідомлення з ймовірністю, що дорівнює сумі ймовірностей об’єднаних повідомлень.

3)    Утворену множену з 13-4=11 повідомлень розташовуємо в порядку спадання ймовірностей.

4)    Знову об’єднуємо останні 4 повідомлення та впорядковуємо множину повідомлень у порядку спадання ймовірностей. Цю процедуру повторюємо, поки сумарна ймовірність не досягне одиниці.

5)    Будуємо кодове дерево (рисунок 6.1). Його гілкам присвоюємо якісні ознаки кодового алфавіту.

Рисунок 6.1 – Кодове дерево побудоване за методикою Хаффмана

 

6)    Кодові комбінації  ОНК заносимо до таблиці 6.2. Вони визначаються послідовністю якісних ознак, які зустрічаються на шляху від кореня до певної вершини кодового дерева.

 

Таблиця 6.2 – Побудова коду  Хаффмана

Номер повідомлення

Ймовірність повідомлення

Ймовірності повідомлень при об’єднаннях

Кодова
комбінація
ОНК

перш
ому

другому

третьому

четвертому

1

0,25

0,25

0,25

0,39

1

1

2

0,15

0,15

0,21

0,25

 

2

3

0,11

0,11

0,15

0,21

 

00

4

0,1

0,1

0,11

0,15

 

01

5

0,1

0,1

0,1

 

 

02

6

0,08

0,08

0,1

 

 

03

7

0,05

0,07

0,08

 

 

21

8

0,05

0,05

 

 

 

22

9

0,04

0,05

 

 

 

23

10

0,03

0,04

 

 

 

200

11

0,02

 

 

 

 

201

12

0,01

 

 

 

 

202

13

0,01

 

 

 

 

203

ЛАБОРАТОРНА РОБОТА № 7

 

Тема: Коди, що виявляють помилки

 

Мета роботипорівняння рівномірних та нерівномірних кодів, що виявляють помилки, побудованих за різними методиками.

 

7.1 Теоретичні відомості

Особливість кодів, що виявляють помилки, полягає у тому, що кодові комбінації, які входять до складу таких кодів,  відрізняються одна від одної кодовою відстанню не меншою  за  d min  = 2.

Такі коди умовно можна розділити на дві групи: коди, в яких використовуються всі комбінації, але до кожної з них за обумовленим правилом додаються  r  перевірочних елементів, та коди, які одержують шляхом зменшення кількості дозволених комбінацій.

До першої групи кодів, що виявляють помилки,  відносяться  такі лінійні коди:  з перевіркою на парність, з простим повторенням, інверсний ( Бауера ), кореляційний; нелінійні коди: з перевіркою на непарність, код Бергера.  Прикладом  коду  другої групи є  код  з  постійною вагою. Код  з  числом одиниць в комбінації, кратним трьом, може належати до першої або до другої групи кодів у залежності від методики його побудови.

Код  з  перевіркою  на  парність  є найбільш поширеним кодом, який використовується для виявлення поодиноких помилок  і  всіх помилок непарної кратності.  Код містить  ( n – 1 )  інформаційних  та  один перевірочний елемент  і  позначається  як  ( n , – 1 ) - код.

Перевірочний елемент визначається як сума за модулем 2 всіх інформаційних елементів:     тобто кодова комбінація коду утворюється  доповненням комбінації  k - елементного первинного коду одним елементом таким чином,  щоб кількість одиниць у новому - розрядному  ( + 1 )  коді була парною. Код має  кодову відстань   dmin = 2.

Для виявлення помилки на приймальному боці виконують перевірку на парність всієї прийнятої кодової комбінації за допомогою визначення кодового синдрому     де  – прийняті на приймальному боці відповідно інформаційні та перевірочний елементи.

Вважається, що при  s1 = 0  помилки в комбінації нема, при  s1 = 1  –  помилка є.  Код виявляє всі помилки непарної кратності.

Надмірність коду   = 1 – / ( + 1 )  = 1 / ( k + 1 ).

Код  з  перевіркою  на  непарність  відрізняється від  коду з перевіркою на парність тим, що кожна його кодова комбінація має непарне число одиниць,  тобто додатковий перевірочний елемент  формують виходячи  з  числа одиниць у первинній кодовій комбінації:  при парному числі одиниць перевірочний елемент дорівнює одиниці,  при  непарному – нулю.  Для виявлення помилки в кодовій комбінації на приймальному боці виконується перевірка на непарність. Код є роздільним нелінійним кодом довжини  n  з  n – 1  інформаційними та одним перевірочним елементами  і  має таку ж спроможність виявлення помилки та надмірність,  як  і  код  з  перевіркою на парність.

Код з простим повторенням   ( з  повторенням без інверсії )  є  роздільним лінійним кодом.  Код містить  k  інформаційних та  r = kперевірочних елементів. У цьому коді  r  перевірочних елементів  є  простим повторенням  k  інформаційних  елементів  первинної  кодової  комбінації:  b i  =  i ,  де     =  1 . . . k . Через те, що код має  d min = 2,  він може бути використаний для виявлення поодиноких помилок.  Процедура виявлення помилок у прийнятій кодовій комбінації полягає у порівнянні однойменних інформаційних  і  перевірочних елементів.  Їх  незбіг говорить про наявність помилок у прийнятій комбінації. Код дозволяє виявити не тільки однократні помилки, а  й  деякі помилки більшої кратності,  за винятком   так званих “дзеркальних” помилок,  коли в інформаційній і перевірочній послідовностях кодової комбінації в результаті дії завад спотворюються елементи,  які знаходяться на однакових за номером розрядах.

Надмірність  коду   R  =  1 –  / ( 2 k )  = 1 / 2.

Інверсний  код  ( код  Бауера ) є  роздільним лінійним кодом  з повторенням  з  інверсією,  який має  k  інформаційних  та  k  перевірочних елементів.  Його відмінність від коду з  простим повторенням полягає у тому, що значення перевірочних елементів у ньому залежать від значення суми за модулем  2  всіх  інформаційних елементів. При тобто при парному числі одиниць у первинній кодовій комбінації перевірочні елементи просто повторюють інформаційні  ( b i = a i ,  де  =1 . . . ). При   тобто при непарному числі одиниць у первинній кодовій комбінації, перевірочні елементи повторюють інформаційні в інвертованому вигляді  ( у  зворотному  коді ):  i = a i Å 1,   де  i= 1 . . . k.

Для виявлення помилок декодером у послідовності, що складається  з  2 k  елементів,  спочатку підсумовують одиниці, які знаходяться у перших  k  елементах.  Якщо їх кількість парна,  решта  k  елементів приймається у позитиві. Обидві зареєстровані частини  кодової комбінації поелементно порівнюються ( перший елемент з першим, другий – з другим  і т.д.).  При наявності хоча б одного незбігу  вся послідовність  елементів бракується.  Якщо кількість одиниць серед перших  k  елементів прийнятої комбінації непарна,  решта  k  елементів  приймається у негативі ( інвертуються ).  Після чого виконується поелементне порівняння.  Наявність незбігу призводить до відбракування кодової комбінації.  Така побудова коду дозволяє виявити  дуже багато варіантів спотворення елементів. 

Надмірність  коду  R  =  1 –  / ( 2 k )  = 1 / 2.

Кореляційний  код  передбачає кодування кожного елемента первинної кодової комбінації. При цьому "0"  записується як  "01",  а  "1" – як  "10".  Так, наприклад, первинній кодовій комбінації 100101 буде відповідати комбінація  100101100110  кореляційного коду.  В технічній літературі такий двійковий запис дуже часто називають  Манчестер - код.  Приймальний пристрій на кожному такті,  який складається  з  двох сусідніх елементів кореляційного коду,  повинен зафіксувати перехід  0 ® 1  або  1 ® 0. У разі  прийняття двох нулів або двох одиниць приймальний пристрій фіксує наявність помилки.

Такий код дозволяє виявляти  помилки будь-якої кратності у кожній парі елементів одного такту, але не здатний виявити так звані "дзеркальні" двократні помилки, коли сусідні елементи одного такту під впливом завад змінюються на протилежні.

Надмірність  коду    = 1 –  k / ( 2 )  = 1 / 2.

До переваг коду можна віднести, крім відсутності постійної складової у напрузі кодованого сигналу при передачі одиниць та нулів по каналу зв'язку імпульсами постійного струму різної полярності, також можливість самосинхронізації генератора приймача, тому що приймання кожного біта супроводжується фронтом сигналу, який приймається, у центрі біта.

Код  Бергера  є найбільш поширеним  з  несистематичних кодів. У такому коді перевірочні елементи, які дописуються у кінці первинної кодової комбінації, – це  інвертований запис двійкового числа, яким записується сума одиниць у кодовій комбінації k – елементного первинного коду, що кодується кодом  Бергера. При цьому число r  перевірочних елементів визначається як найменше ціле, для якого виконуються умови  r ³ log 2(k+1).  Так, наприклад,  при k=8, отримаємо  log2(8+1)=log 29=3,16993, тобто  = 4.

Для виявлення помилки у декодері виконується операція підрахунку числа одиниць в інформаційній частині прийнятої кодової комбінації. Це число записується у двійковій формі, інвертується і порівнюється з перевірочною частиною прийнятої кодової комбінації.  Їх незбіг вказує на наявність  помилки.

Надмірність  коду    = 1 –  r / n.

Код з постійною вагою, тобто з постійним числом одиниць та нулів у комбінаціях,  часто називають кодом на одне сполучення.  Загальна кількість кодових комбінацій коду з  постійною вагою

 ,

де  m  –  число одиниць у комбінації  довжини  n.

Такий код утворюється з простого двійкового коду відбором комбінацій, які мають однакову кількість одиниць  m. У декодері підраховується кількість одиниць у прийнятій кодовій комбінації. Невідповідність кількості одиниць числу m  говорить про наявність помилки у кодовій комбінації.

Код з постійною вагою має мінімальну кодову відстань  d min = 2  і  виявляє всі помилки непарної кратності,  а  також всі помилки  парної кратності, які призводять до порушення умови   m = const.

Надмірність  коду   R  = 1 – ( log 2 C/ n

Код  з  числом  одиниць  у  комбінації,  кратним  трьом, можна утворити або шляхом додавання до кожної комбінації первинного коду  двох перевірочних елементів, або зменшенням кількості дозволених кодових комбінацій первинного коду за допомогою накладання додаткової  умови – кількість одиниць у кожній комбінації повинна бути кратною трьом  ( 0, 3, 6, . . . )

У першому випадку до первинної кодової комбінації додаються два перевірочні розряди,  які мають такі значення, що сума одиниць у кодовій комбінації стає кратною трьом. Так, наприклад, комбінація первинного коду  01100  закодована кодом з числом одиниць, кратним трьом,   буде  мати   вигляд  0110010,   комбінація   01000  0100011,  1010  101010,   101100  10110000,   101110  10111011, 0111110  011111010   тощо.

У другому випадку з усіх кодових комбінацій первинного коду вибирають тільки ті комбінації, які мають вагу = 0, 3, 6, 9, . . . Всі інші комбінації заборонені для вживання.

Код дозволяє виявити всі поодинокі помилки та деякі помилки більшої кратності.

Здатність коду виявляти помилкові комбінації майже така ж, як  і  коду з постійною вагою.

Надмірність коду з доповненням до необхідної кількості одиниць ( кратності ):  R  =  1 –  k / ( + 2 ),  а  для коду, який утворюється шляхом відбору комбінацій з відповідною кількістю одиниць  з   повного числа комбінацій простого коду:

    R = 1 – [ log 2 CCC+ . . . + C) ] / 

де  b  –  ціла частина  n / 3.

 

Приклади  розв’язання  задач

Задача 1

Закодувати комбінацію 1110101 двійкового простого коду   ( = 7 )  двійковими кодами, що виявляють помилки:  з перевіркою на парність і простим повторенням. Виявити однократну помилку та порівняти надмірності цих кодів.

Розв’язання.  Кодова комбінація коду з перевіркою на парність буде мати вигляд:   A 1 = 11101011,  а  коду з простим повторенням –  А 2 = 11101011110101.

Нехай  у  комбінації коду з перевіркою на парність  виникла однократна помилка,  вектор якої  Е 1 = 00000100.  Тоді сума  А Å Е 1 = 11101111.

 У цьому разі сума за модулем 2 елементів одержаної на приймальному боці кодової комбінації дорівнює 1, тобто непарна, що вказує на наявність у ній помилки. Надмірність коду  1 = 1 – 7 / 8 = 0,125.

Нехай в комбінації коду з простим повторенням вектор однократної помилки буде   Е 2 = 00000100000000. Тоді сума  А Å Е = 11101111110101.  Порівнюючи першу  і  другу частини кодової комбінації ( одержуючи їх суму за модулем 2 ), отримаємо остачу, яка не буде дорівнювати нулю ( 1110111 Å 1110101 = 0000010 ), що  вказує на наявність помилки у прийнятій кодовій комбінації. Надмірність коду   2 = 0,5. Таким чином   1.

Задача  2

Закодувати комбінацію 01000 двійкового простого коду   ( = 5 )  двійковими кодами, що виявляють помилки: з числом одиниць у комбінації, кратним трьом,  та інверсним ( Бауера ).  Виявити однократну помилку  і  порівняти надмірності цих кодів.

Розв’язання.  Кодова комбінація коду  з  числом одиниць, крат-ним трьом, буде мати вигляд:  А = 0100011, а  інверсного коду –А = 0100010111.

Нехай у комбінації коду з числом одиниць, кратним трьом, виникла однократна  помилка, вектор  якої      Е = 0000100. Тоді сума

А Å Е 1 = 0100111. У цьому разі вага одержаної кодової комбінації  w* = 4, тобто відрізняється від  w = 3, що вказує на наявність у ній помилки.  Надмірність коду  1 = 1 –  5 / 7 = 2 / 7.

Нехай  у  комбінації інверсного коду виникла однократна помилка, вектор якої E 2 = 0000100000. Тоді сума А 2 Å Е = 0100110111. У декодері виконується перевірка кількості одиниць у першій половині кодової комбінації,  яка дорівнює 2. Це означає, що друга половина комбінації повинна прийматися у позитиві ( без інверсії ). Порівнюючи першу і другу ( неінвертовану ) частини прийнятої кодової комбінації одержимо незбіг у чотирьох розрядах, що вказує на наявність у ній помилки.  Надмірність коду 2   = 0,5. Таким чином   >1.

Задача  3

Закодувати комбінацію 010101 двійкового простого коду   ( = 6 ) двійковими кодами, що виявляють помилки:  з перевіркою на непарність  і  кореляційним. Виявити однократну помилку та порівняти надмірності цих кодів.

Розв’язання. Кодова комбінація коду з перевіркою на непарність буде мати вигляд: А = 0101010, а  кореляційного –  A = 011001100110.

Нехай у комбінації коду з перевіркою на непарність виникла однократна помилка, вектор якої Е = 0000100. Тоді сума А 1 Å Е = 0101110. У декодері перевіряється за модулем 2 сума елементів одержаної кодової комбінації. У цьому разі вона буде дорівнювати 0, тобто парна, що вказує на наявність в комбінації помилки. Надмірність коду  1 = 1 – 6 / 7  = 1 / 7.

Нехай у комбінації кореляційного коду виникла однократна помилка, вектор якої Е = 000010000000.  Тоді сума  А Å Е = 011011100110. Як відомо,  декодування кодової комбінації у декодері ведуть тактами по два елементи у кожному такті. При цьому два елементи одного такту не повинні мати однакове значення, тобто не повинно бути сполучень 00 та 11. У даному разі у третьому такті ( парі елементів ) буде отримано сполучення 11, що вказує на наявність помилки у прийнятій комбінації. Надмірність коду  2 =  0,5. Таким  чином   1.

Задача  4

Закодувати комбінацію 1001111 двійкового простого коду   ( = 7 ) двійковими кодами, що виявляють помилки: інверсним ( Бауера ) та  Бергера. Виявити однократну помилку  і  порівняти надмірності  цих  кодів.

Розв’язання.  Кодова комбінація інверсного коду, з огляду на непарну кількість одиниць у первинній комбінації, буде мати вигляд:А = 10011110110000, а коду Бергера – А = 1001111010 (тому що, r = log ( 7 + 1 ) = log 2 8 = 3,  510 = 1012,  інверсія  101 ® 010 ).

Нехай у комбінації інверсного коду виникла однократна помилка, вектор якої Е = 00000100000000.Тоді сума  А Å Е = 10011010110000. У декодері підраховується кількість одиниць у першій половині кодової комбінації, яка у даному разі дорівнює 4. Це означає, що друга половина комбінації повинна прийматися у позитиві.  Порівнюючи  першу та другу  ( неінвертовану ) частини прийнятої кодової комбінації, одержимо незбіг у шести розрядах, що вказує на наявність у ній помилки. Надмірність  коду   =  0,5.

Нехай у комбінації коду Бергера виникла однократна помилка, вектор якої  Е = 0010000000. Тоді  сума   А Å Е= 1011111010.

При прийманні у декодері підраховується кількість одиниць в інформаційній частині кодової комбінації, яка дорівнює шести. У двійковій формі запису це буде 110, інвертуючи яку одержуємо – 001. Порівнюємо перевірочні елементи прийнятої кодової комбінації та одержані у декодері шляхом обчислення кількості одиниць в інформаційній частині  прийнятої комбінації. Їх незбіг ( 010 – 001 ) вказує на наявність помилки у прийнятій кодовій комбінації. Надмірність  коду  = 0,3.  Таким чином  2.

 

7.2 Завдання

1. Закодувати комбінацію А двійкового простого коду двійковими  кодами, що виявляють помилки, згідно варіанта, поданого в таблиці 1. Показати на прикладі виявлення  помилок, кількість яких визначається заданим варіантом,  та порівняти надмірності цих кодів.

Таблиця  1.

варі-анта

Первинна  кодова           комбінація  А       двійкового

простого  коду

Двійковий код, що виявляє

  помилки

Кількість помилок,

яка виявляється  першим / другим кодом

1

100101010100

ПРП, КБ

1/1

2

11101101101

ПРН, ПП

1/1

3

11011010

КК, КБ

1/1

4

0000011100

ПВ(4), ПП

1/1

5

0000011000

ПВ(3), ОК3

1/1

6

10111101011

ІК, КБ

3/1

7

11101010101

ІК, ПП

3/1

8

0011101100

ІК,  КК

3/1

9

11000010100

ІК, ПВ(5)

3/1

10

00101010100

ПВ(6), ПРП

1/1

11

100101010100

ПВ(5), ПРН

1/1

12

101111010

КК, ПП

1/1

13

1110010111

КК, КБ

1/1

14

100101011110

ПРП, ПП

1/1

15

100101010100

ПРН, ОК3

1/1

16

110000101011

ІК, КБ

3/1

17

010101010101

ІК, ПП

3/1

18

1011101101

ІК, КБ

3/1

19

1100001011

ІК, ПВ(5)

3/1

20

1000000101

ПВ(4), ПРП

1/1

21

1001010101

ПВ(7), ПРН

1/1

22

10111

КК, ПП

1/1

23

11100101

КК, ОК3

1/1

24

100101011110

ПРП, ПП

1/1

25

100101010100

ПРН, ОК3

1/1

Умовні  позначення  двійкових кодів,  що виявляють помилки: ПРП – з  перевіркою на парність;  ПРН – з  перевіркою на непарність; ПП – з  простим  повторенням;  ІК – інверсний;  КК – кореляційний; КБ – Бергера; ОК3 – з числом одиниць, кратним трьом; ПВ(w) – з постійною вагою   w.

 

2. Задати дискретне джерело повідомлень, що вибирає повідомлення akÎА, де А - множина літер прізвища, імені, по-батькові українською мовою. Розрахувати ансамбль джерела повідомлень, пов'язавши з кожним дискретним повідомленням ai ймовірність pi його вибору джерелом. Для ансамблю повідомлень побудувати коди:

-        код із перевіркою на парність

-        код із перевіркою на непарність

-        код із простим повторенням

-        інверсний код

-        кореляційний код

-        код зі сталою вагою

-        код із кількістю одиниць у комбінації, кратною трьом.

Порівняти коди за надмірністю. Закодувати перші три літери прізвища. Змінити один з символів та показати процес виявлення помилки для одного з кодів.

 

7.3  Приклади  розв’язання  задач

Джерело повідомлень

ІВАНОВ_ІВАН_ІВАНОВИЧ

A={І, В, А, Н, О, И, Ч, _}

літера

І

В

А

Н

О

И

Ч

_

pi

0.15

0.25

0.15

0.15

0.10

0.05

0.05

0.10

 

 

Код із перевіркою на парність

Для побудови кодової таблиці використовуємо таблицю рівномірного двійкового коду (k – кількість інформаційних розрядів), додаючи до кожної кодової комбінації перевірний розряд за правилом .

Мінімальна довжина кодового слова складає     n=k+1      k=3                 n=4

Кодова таблиця має вигляд

літера

рівномірний двійковий код

код із перевіркою на парність

І

000

0000

В

001

0011

А

010

0101

Н

011

0110

О

100

1001

И

101

1010

Ч

110

1100

_

111

1111

Надмірність коду     Rнад=1-k/(k+1)=1/(k+1)      , тобто           Rнад=1/(3+1)=0,25

 

Повідомлення для передачі перших трьох літер прізвища:

С=0000 0011 0101

Виявлення помилки при передачі повідомлення.

Нехай в комбінації коду виникла однократна помилка, вектор якої E=0010 0000 0000. Тоді сума СÅE=0010 0011 0101. Сума за модулем 2 елементів першої кодової комбінації дорівнює 1, тобто непарна, що вказує на наявність у ній помилки.

 

Код із перевіркою на непарність

Для побудови кодової таблиці використовуємо таблицю рівномірного двійкового коду (k – кількість інформаційних розрядів), додаючи до кожної кодової комбінації перевірний розряд за правилом .

Мінімальна довжина кодового слова складає   n=k+1        k=3                 n=4

Кодова таблиця має вигляд

літера

рівномірний двійковий код

код із перевіркою на непарність

І

000

0001

В

001

0010

А

010

0100

Н

011

0111

О

100

1000

И

101

1011

Ч

110

1101

_

111

1110

 Надмірність коду    Rнад=1-k/(k+1)=1/(k+1)      ,                       Rнад=1/(3+1)=0,25

 

Повідомлення для передачі перших трьох літер прізвища

С=0001 0010 0100

Виявлення помилки при передачі повідомлення.

Нехай в комбінації коду виникла однократна помилка, вектор якої E=0010 0000 0000. Тоді сума СÅE=0011 0010 0100. Сума за модулем 2 елементів першої кодової комбінації дорівнює 0, тобто парна, що вказує на наявність у ній помилки.

 

Код із простим повторенням

Для побудови кодової таблиці використовуємо таблицю рівномірного двійкового коду (k – кількість інформаційних розрядів), додаючи до кожної кодової комбінації r=k перевірних елементів.

Мінімальна довжина кодового слова складає  n=k+r          k=r=3              n=6

Кодова таблиця має вигляд

літера

рівномірний двійковий код

код із простим повторенням

І

000

000000

В

001

001001

А

010

010010

Н

011

011011

О

100

100100

И

101

101101

Ч

110

110110

_

111

111111

Надмірність коду   Rнад=1-k/(2k)             Rнад=0,5

Повідомлення для передачі перших трьох літер прізвища

С=000000 001001 010010

Виявлення помилки при передачі повідомлення.

Нехай в комбінації коду виникла однократна помилка, вектор якої E=001000 000000 000000. Тоді сума СÅE=001000 001001 010010. Перевіряючи першу та другу частини кодової комбінації (додаючи їх за модулем 2), в першій кодовій комбінації дістаємо остачу, яка не дорівнюватиме нулю:

001                 001                 010

       Å 000             Å 001             Å 010

001                 000                 000

що вказує на наявність у ній помилки.

 

Інверсний код

Для побудови кодової таблиці використовуємо таблицю рівномірного двійкового коду (k – кількість інформаційних розрядів), додаючи до кожної кодової комбінації r=k перевірних елементів: за умови  перевірні елементи просто повторюють інформаційні bi=аi, де і=1...k, а за умови  перевірні елементи повторюють інформаційні в інвертованому вигляді: bi=аiÅ1, де і=1...k.

Мінімальна довжина кодового слова складає

n=k+r                         k=r=3                         n=6

Кодова таблиця має вигляд

літера

рівномірний двійковий код

інверсний код

І

000

000000

В

001

001110

А

010

010101

Н

011

011011

О

100

100011

И

101

101101

Ч

110

110110

_

111

111000

 

Надмірність коду    Rнад=1-k/(2k)                                   Rнад=0,5

 

Повідомлення для передачі перших трьох літер прізвища

С=000000 001110 010101

Виявлення помилки при передачі повідомлення.

Нехай в комбінації коду виникла однократна помилка, вектор якої E=000000 010000 000000. Тоді сума СÅE=000000 011110 010101. Перевіряючи першу та другу частини кодової комбінації (додаючи їх за модулем 2), в другій кодовій комбінації дістаємо остачу, яка не дорівнює нулю:

000                 011                 010

       Å 000             Å 110             Å 101

               0                     0                     1

000                 101                 000

що вказує на наявність у ній помилки.

 

Кореляційний код

Для побудови кодової таблиці використовуємо таблицю рівномірного двійкового коду (k – кількість інформаційних розрядів), додаючи до кожної кодової комбінації r=k перевірних елементів. Перевірні розряди розташовані між інформаційними, записуємо 0 — як 01, а 1 — як 10.

Мінімальна довжина кодового слова складає   n=k+r         k=r=3              n=6

Кодова таблиця має вигляд

літера

рівномірний двійковий код

кореляційний код

І

000

010101

В

001

010110

А

010

011001

Н

011

011010

О

100

100101

И

101

100110

Ч

110

101001

_

111

101010

Надмірність коду  Rнад=1-k/(2k)              Rнад=0,5

 

Повідомлення для передачі перших трьох літер прізвища

С=010101 010110 011001

Виявлення помилки при передачі повідомлення.

Нехай в комбінації коду виникла однократна помилка, вектор якої E=000000 010000 000000. Тоді сума СÅE=010101 000110 011001. Декодування комбінації при її прийманні провадиться тактами по два елементи в кожному. При цьому елементи одного такту не повинні мати однакове значення, тобто не повинно бути сполучень 00 і 11. В четвертому такті є сполучення 00, що вказує на наявність помилки в комбінації.

 

Код зі сталою вагою

Загальна кількість комбінацій цього коду визначається виразом 

де m — кількість одиниць у кодовій комбінації завдовжки n.

Такий код утворюється з двійкового простого коду відбором комбінацій, що мають однакову кількість одиниць m. Знаючи потрібну кількість кодових комбінацій, підберемо m та n так, щоб Cnm була найближчою до неї.

n=4     m=2                Cnm=6<8

n=4     m=3                Cnm=4<8

n=5     m=2                Cnm=10

n=5     m=3                Cnm=10

n=5     m=4                Cnm=5<8

n=6     m=2                Cnm=15

n=6     m=3                Cnm=20

n=6     m=4                Cnm=15

Виберемо                n=5     m=2

Кодова таблиця має вигляд

літера

код зі сталою вагою

І

00011

В

00101

А

01001

Н

10001

О

00110

И

01010

Ч

10010

_

01100

Повідомлення для передачі перших трьох літер прізвища

С=00011 00101 01001

Виявлення помилки при передачі повідомлення.

Нехай в комбінації коду виникла однократна помилка, вектор якої E=00000 01000 00000. Тоді сума СÅE=00011 01101 01001. Приймальний пристрій, підраховуючи кількість одиниць у прийнятій кодовій комбінації, виявляє помилки, якщо кількість одиниць відрізнятиметься від m. В другій кодовій комбінації кількість одиниць відрізняється від m, що вказує на наявність у ній помилки.

Надмірність коду   Rнад=1-(log2Cnm)/n               Rнад=1-(log210)/5=0,3356

 

Код із кількістю одиниць у комбінації, кратною трьом

Для побудови кодової таблиці використовуємо таблицю рівномірного двійкового коду (k – кількість інформаційних розрядів), додаючи до кожної кодової комбінації r=2 перевірних елементів так, щоб кількість одиниць у кожній комбінації була кратною трьом.

Кодова таблиця має вигляд

літера

рівномірний двійковий код

Код із кількістю одиниць у комбінації, кратною трьом

І

000

00000

В

001

00111

А

010

01011

Н

011

01101

О

100

10011

И

101

10101

Ч

110

11001

_

111

11100

Надмірність коду   Rнад=1-2/(k+2)                                  Rнад=1-2/(3+2)=0,6

Повідомлення для передачі перших трьох літер прізвища

С=00000 00111 01011

Виявлення помилки при передачі повідомлення.

Нехай в комбінації коду виникла однократна помилка, вектор якої E=00000 01000 00000. Тоді сума СÅE=00000 01111 01011. Приймальний пристрій, підраховуючи кількість одиниць у прийнятій кодовій комбінації, виявляє помилки, якщо кількість одиниць відрізнятиметься від 3. В другій кодовій комбінації кількість одиниць відрізняється від 3, що вказує на наявність у ній помилки.

ЛАБОРАТОРНА РОБОТА № 8

 

Тема: Коди, що виправляють помилки. Код Хемінга

 

Мета роботи: порівняння кодів, що виправляють помилки, побудованих за різними методиками.

 

8.1 Завдання

1 Задавши дискретне джерело повідомлень без пам'яті, що вибирає повідомлення akєА, де А - множина літер прізвища, імені, по-батькові українською мовою, розрахувати ансамбль джерела повідомлень, пов'язавши з кожним дискретним повідомленням ai ймовірність pi його вибору джерелом. Для ансамблю повідомлень побудувати двійкові коди, здатні виправляти поодинокі помилки (vвп=1):

-          лінійний систематичний груповий (блоковий) код

-          код Хеммінга

-          циклічний код

-          код із багатократним повторенням

-          ітеративний код

2 Порівняти коди за надмірністю.

3 Закодувати перші три літери прізвища. Змінити один з символів та показати процес виправлення помилки для одного з кодів.

 

8.2  Приклади  розв’язання

Джерело повідомлень

ІВАНОВ_ІВАН_ІВАНОВИЧ

A={І, В, А, Н, О, И, Ч, _}

літера

І

В

А

Н

О

И

Ч

_

pi

0.15

0.25

0.15

0.15

0.10

0.05

0.05

0.10

 

 

Лінійний систематичний груповий (блоковий) код

Побудова твірної матриці та визначення комбінацій лінійного систематичного двійкового групового коду, здатного виправляти поодинокі помилки (vвп=1).

Через те що N=2k=23=8, маємо k=3. Отже, кількість рядків твірної матриці Gn,k дорівнює 3, а кількість її стовпців визначається довжиною коду n=k+r. Кількість перевірних розрядів r=3 (урахувавши, що dmin=2vвп+1=3). Тоді кількість стовпців підматриці Cr,k дорівнює 3, а твірної матриці Gn,k - 6.

Згідно з правилом побудови підматриці Cr,k кількість одиниць у кожному її рядку має бути не меншою ніж dmin-1=3-1=2, а кодова відстань між рядками — не меншою ніж dmin-2=3-2=1. Тому з триелементних комбінацій для підматриці Cr,k вибираємо тільки ті, які задовольняють ці умови, тобто 101,011, 110.

Оскільки як інформаційна підматриця Ek твірної матриці Gn,k вибирається одинична підматриця, дописавши до неї перевірну підматрицю, дістанемо твірну матрицю лінійного систематичного групового коду, здатного виправляти однократні помилки:

 

 

За допомогою цієї матриці визначаємо всі вісім комбінацій даного коду:

1.           000000

2.           100101

3.           010011

4.           001110

5.           110110(2 + 3);

6.           101011 (2 + 4);

7.           011101 (3 + 4);

8.           111000(2 + 3 + 4).

Для побудови перевірної матриці лінійного систематичного двійкового групового коду, здатного виправляти однократні помилки, скористаємось твірною матрицею.

Перевірна матриця Н повинна мати r=3 рядки та n=6 стовпців. Вона складається з двох підматриць: D(3,3), що містить по три стовпці та рядки, кожний рядок якої відповідає стовпцю перевірної підматриці С(3,3) твірної матриці G(6,3); одиничної підматриці Е(3). Отже,

 

 

Перевірні елементи коду згідно з цією матрицею визначаються як b1=а1+а3b2=а2+a3b3=а1+а2.

Користуючись перевірною матрицею H(6,3), виконуємо кодування повідомлень.

 

Кодова таблиця має вигляд

літера

рівномірний двійковий код

перевірні розряди b1=а1+а3

b2=а2+a3

b3=а1+а2

лінійний систематичний груповий код

І

000

000

000000

В

001

110

001110

А

010

011

010011

Н

011

101

011101

О

100

101

100101

И

101

011

101011

Ч

110

110

110110

_

111

000

111000

 

Надмірність коду

Rнад=1-k/n                                                       Rнад=1-3/6=0,5

 

Повідомлення для передачі перших трьох літер прізвища

С=000000 001110 010011

 

Виявлення та виправлення помилки при передачі повідомлення.

Нехай в комбінації коду виникла однократна помилка, вектор якої E=000000 000000 001000. Тоді сума С+E=000000 001110 011011.

На приймальному боці для виявлення та виправлення однократної помилки в прийнятій кодовій комбінації виконується перевірка — визначається синдром помилки. Для матриці H(6,3) маємо

S11+а3+b1S2=а2+a3+b2S3=а1+а2+b3

000000 S1=0+0+0=0; S2=0+0+0=0; S3=0+0+0=0                       - без помилок;

001110 S1=0+1+1=0; S2=0+1+1=0; S3=0+0+0=0                       - без помилок;

011011 S1=0+1+0=1; S2=1+1+1=1; S3=0+1+1=0                       - помилка.

Синдром має вигляд 110, що відповідає третьому стовпцю перевірної матриці H(6,3), тобто помилка знаходиться в третьому розряді прийнятої кодової комбінації. Для її виправлення інвертуємо значення цього розряду. Виправлена комбінація матиме вигляд 010011.

 

Код Хеммінга

Для розрахунку основних параметрів коду Хеммінга використаємо співвідношення n=k+r. Звідки

k=3                    n=6                r=3

Характерна особливість перевірної матриці коду з dmin=3 полягає у тому, що її стовпці є різними ненульовими комбінаціями завдовжки r.

 

 

Перевірні розряди розміщуються між інформаційними так, щоб номер i-го стовпця матриці H і номер розряду кодової комбінації відповідали двійковому поданню числа і. Тоді синдром, знайдений з перевірних рівнянь, буде двійковим поданням номера розряду кодової комбінації, в якій виникла помилка. Для цього перевірні розряди мають знаходитися не в кінці кодової комбінації, а на номерах позицій, які подаються степенем двійки (20, 21, 22, 23,... ,2r-1).

Згідно з матрицею формуємо систему перевірних рівнянь, за допомогою яких знаходимо перевірні розряди:

u1=u3+u5u2=u3+u6u4=u5+u6.

Кодова таблиця має вигляд

літера

рівномірний двійковий код

u3u5u6

перевірні розряди u1=u3+u5

u2=u3+u6

u4=u5+u6

код Хеммінга

 

І

000

000

000000

В

001

011

010101

А

010

101

100110

Н

011

110

110011

О

100

110

111000

И

101

101

101101

Ч

110

011

011110

_

111

000

001011

 

Надмірність коду

Rнад=1-k/n                                                       Rнад=1-3/6=0,5

 

Повідомлення для передачі перших трьох літер прізвища

С=000000 010101 100110

 

Виявлення та виправлення помилки при передачі повідомлення.

Нехай в комбінації коду виникла однократна помилка, вектор якої E=000000 000000 001000. Тоді сума С+E=000000 010101 101110.

На приймальному боці для виявлення та виправлення однократної помилки в прийнятій кодовій комбінації виконується перевірка — визначається синдром помилки.

               S1=u4+u5+u6S2=u2+u3+u6S3=u1+u3+u5

000000 S1=0+0+0=0; S2=0+0+0=0; S3=0+0+0=0                       - без помилок;

010101 S1=1+0+1=0; S2=1+0+1=0; S3=0+0+0=0                       - без помилок;

101110 S1=1+1+0=0; S2=0+1+0=1; S3=1+1+1=1                       - помилка.

Синдром має вигляд 011, тобто помилка знаходиться в третьому розряді прийнятої кодової комбінації. Для її виправлення інвертуємо значення цього розряду. Виправлена комбінація матиме вигляд 100110.

 

Циклічний код

Щоб побудувати циклічний код, необхідно вибрати твірний поліном Р(х). Його степінь визначається кількістю r перевірних елементів у комбінації циклічного коду, причому значення r при dmin=3 можна знайти з виразу 2r-1³n або 2r³k+r+1. Отже, при k=3 маємо r=3, твірний поліном:Р(х)=x3+х+1.

Для побудови твірної матриці (формування її рядків) беремо комбінації Q(x) двійкового простого коду, які містять одиницю в одному розрядіQi(x), де i=1,2,…,k. Ці комбінації множимо на хr і знаходимо остачу від ділення хrQi(x)/P(x), що дорівнює Ri(x).

Отже, для циклічного (6,3)-коду з n=6, k=3 і твірним поліномом Р(х)=x3+х+1, беремо триелементні одиничні комбінації Qi двійкового простого коду: Q1(х)=1 (001); Q2(x)=х (010); Q3(x)=х2 (100). Вибрані комбінації Qi(x) множимо на х3 (r=n-k=6-3=3), ділимо на Р(х)=x3+х+1 і знаходимо остачі:

 

 

 

Твірна матриця матиме вигляд

 

 

Перевірна матриця Н повинна мати r=3 рядки та n=6 стовпців. Вона складається з двох підматриць: D(3,3), що містить по три стовпці та рядки, кожний рядок якої відповідає стовпцю перевірної підматриці С(3,3) твірної матриці G(6,3); одиничної підматриці Е(3). Отже,

 

 

Перевірні елементи коду згідно з цією матрицею визначаються як b1=а1+а2b2=а1+а2+a3b3=а1+а3.

Користуючись перевірною матрицею H(6,3), виконуємо кодування повідомлень.

 

Кодова таблиця має вигляд

літера

рівномірний двійковий код

перевірні розряди b1=а1+а2

b2=а1+а2+a3

b3=а1+а3

циклічний код

І

000

000

000000

В

001

011

001011

А

010

110

010110

Н

011

101

011101

О

100

111

100111

И

101

100

101100

Ч

110

001

110001

_

111

010

111010

Надмірність коду   Rнад=1-k/n                                            Rнад=1-3/6=0,5

 

Повідомлення для передачі перших трьох літер прізвища

С=000000 001011 010110

 

Виявлення та виправлення помилки при передачі повідомлення.

Нехай в комбінації коду виникла однократна помилка, вектор якої E=000000 000000 001000. Тоді сума С+E=000000 001011 011110.

На приймальному боці для виявлення та виправлення однократної помилки в прийнятій кодовій комбінації виконується перевірка — визначається синдром помилки.

S11+а2+b1S2=а1+а2+a3+b2S3=а1+а3+b3

000000 S1=0+0+0=0; S2=0+0+0+0=0; S3=0+0+0=0                   - без помилок;

001011 S1=0+0+0=0; S2=0+0+1+1=0; S3=0+1+1=0                   - без помилок;

011110 S1=0+1+1=0; S2=0+1+1+1=1; S3=0+1+0=1                   - помилка.

Синдром має вигляд 011, що відповідає третьому стовпцю перевірної матриці H(6,3), тобто помилка знаходиться в третьому розряді прийнятої кодової комбінації. Для її виправлення інвертуємо значення цього розряду. Виправлена комбінація матиме вигляд 010011.

 

Виявлення та виправлення помилки при передачі повідомлення, що ґрунтується на застосуванні твірного полінома Р(х).

Поліном прийнятої комбінації циклічного коду F¢(x)=F(x)+Е(х).

На приймальному боці декодер виконує перевірне ділення комбінації F¢(x) на поліном Р(х), використаний при кодуванні інформації:

Оскільки остача від ділення в третій кодовій комбінації не дорівнює нулю, робимо висновок про наявність помилки в прийнятій кодовій комбінації.

Для визначення місця помилки користуємося методом гіпотез:

• будуємо гіпотезу про помилку в молодшому розряді комбінації F¢(x), тобто вважаємо, що вектор помилки Е1(х)=1®E1=000001. Виконавши додавання F¢+E1 поділивши результат на поліном Р(х) з метою підтвердження (в разі нульової остачі) або спростування (в разі ненульової остачі) гіпотези, дістанемо

тобто остача ненульова й гіпотеза відкидається;

• будуємо гіпотезу про помилку в п’ятому розряді комбінації F¢(x), тобто вважаємо, що вектор помилки Е2(х)=2®E2=000010. Виконавши додавання F¢+E2 та поділивши результат на поліном Р(х) з метою підтвердження або спростування гіпотези, матимемо

тобто остача ненульова й гіпотеза відкидається;

• будуємо гіпотезу про помилку в четвертому розряді комбінації F¢(x), тобто вважаємо, що вектор помилки Е3(х)=3®E3=000100. Виконавши додавання F¢+E3 та поділивши результат на поліном Р(х) з метою підтвердження або спростування гіпотези, знайдемо

тобто остача ненульова й гіпотеза відкидається;

• будуємо гіпотезу про помилку в третьому розряді комбінації F¢(x), тобто вважаємо, що вектор помилки Е4(х)=4®E4=001000. Виконавши додавання F¢+E4 та поділивши результат на поліном Р(х) з метою підтвердження або спростування гіпотези, дістанемо

тобто помилка дійсно є в третьому розряді, а початкова комбінація циклічного коду має вигляд F=010110®F(x)=x4+х2+x.


Русский язык и культура речи

перейти к оглавлению

1. ЭЛЕМЕНТЫ И УРОВНИ ЯЗЫКА

Характеризуя язык как систему, необходимо определить, из каких элементов он состоит. В большинстве языков мира выделяются следующие единицы: фонема (звук), морфема, слово, словосочетание и предложение. Единицы языка неоднородны по своему строению: простые (фонемы) и сложные (словосочетания, предложения). При этом более сложные единицы всегда состоят из более простых.

Самая простая единица языка – это фонема, неделимая и сама по себе...

Идеология

1.Идеология как социальный феномен, её сущность. Содержание идеологииСоциально-исторической системой представлений о мире стала идеология как система рационально- логического обоснования поведения людей, их ценностей, норм взаимоотношений, целей и т.д. Идеология как явление во многом сходна с религией и с наукой. От науки она восприняла доказательность и логичность своих постулатов, но, в отличие от науки, идеология призвана давать оценку явлениям действительности (что хорошо, что...

Политология. Универсальная шпаргалка

перейти к оглавлению

1. Место политологии среди гуманитарных наук

Политология развивается в тесном взаимодействии с другими гуманитарными науками. Их всех объединяет общий объект исследования — жизнь общества во всем многообразии ее конкретных проявлений.

Сегодня невозможно изучать сложные политические процессы, не учитывая взаимодействие общественных (гуманитарных) наук.

1) Политология тесно связана с экономикой. Экономика дает соответствующее обоснование реализации экономических...

законы диалектики

Основные законы диалектики.

1)Закон единства и борьбы противоположностей.

Этот закон является «ядром» диалектики, т.к. определяет источник развития, отвечает на вопрос, почему оно происходит.

Содержание закона: источник движения и развития мира находится в нем самом, в порождаемых им противоречиях.

Противоречие – это взаимодействие противоположных сторон, свойств и тенденций в составе той или иной системы или между системами. Диалектическое противоречие есть только там, где...

Математические формулы. Шпаргалка для ЕГЭ с математики

Формулы сокращенного умножения

(а+b)2 = a2 + 2ab + b2

(а-b)2 = a2 – 2ab + b2

a2 – b2 = (a-b)(a+b)

a3 – b3 = (a-b)( a2 + ab + b2)

a3 + b3 = (a+b)( a2 – ab + b2)

(a + b)3 = a3 + 3a2b+ 3ab2+ b3

(a – b)3 = a3 – 3a2b+ 3ab2- b3

Свойства степеней

a0 = 1 (a≠0)

am/n = (a≥0, n ε N, m ε N)

a- r = 1/ a r (a>0, r ε Q)

m...