Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции - Теория информации и кодирования (укр яз) - файл приклад лаб.doc


Загрузка...
Лекции - Теория информации и кодирования (укр яз)
скачать (889.4 kb.)

Доступные файлы (7):

завдання лаб.doc59kb.27.05.2010 12:51скачать
з_лек1.pps
з_лек2.pps
з_лек3.pps
з_лек4.pps
з_лек5.pps
приклад лаб.doc796kb.09.02.2010 13:05скачать

приклад лаб.doc

  1   2   3
Реклама MarketGid:
Загрузка...
ЛАБОРАТОРНА РОБОТА №1


Тема: Ансамблі та джерела повідомлень


Мета роботи: порівняння джерел повідомлень.


Завдання

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

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

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

Визначити продуктивність обох джерел припустивши, що вони вибирають всі свої повідомлення за один і той самий проміжок часу  = cep = 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


Висновки

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

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


Тема: Первинні коди


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


Завдання

Задати дискретне джерело повідомлень без пам'яті, що вибирає повідомлення akА, де А - множина літер прізвища, імені, по-батькові українською мовою.

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

Для ансамблю повідомлень побудувати коди:

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

  • код Грея,

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

  • двійковий ОНК Хаффмена.

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

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


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

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

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


Код Грея

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

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

літера

код

код Грея

І

000

000

В

001

001

А

010

011

Н

011

010

О

100

110

И

101

111

Ч

110

101

_

111

100

n=nсер=3


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

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

літера

pi

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

Код

перша

друга

третя

четверта

В

0,25

0,55

0,25







00

І

0,15

0,30

0,15




010

А

0,15

0,15




011

Н

0,15

0,45

0,25

0,15




100

О

0,10

0,10




101

_

0,10

0,20

0,10




110

И

0,05

0,10

0,05

1110

0,05

1111

Ч

0,05


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



Для того щоб перевірити оптимальність коду відносно довжини кодових комбінацій, визначаємо середню довжину 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.


^ Двійковий ОНК Хаффмена

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

літера

pi

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

Код

1

2

3

4

5

6

7

В

0,25

0,25

0,25

0,25

0,30

0,45

0,55

1

00

І

0,15

0,15

0,20

0,25

0,25

0,30

0,45




010

А

0,15

0,15

0,15

0,20

0,25

0,25







011

Н

0,15

0,15

0,15

0,15

0,20










100

О

0,10

0,10

0,15

0,15













101

_

0,10

0,10

0,10
















110

И

0,05

0,10



















1110

Ч

0,05






















1111


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



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

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


Висновки

Серед наведених кодів найменшу середню довжину кодової комбінації мають ____ і ____ коди, крім того, код ___ дає можливість ____, отже він і є найбільш оптимальним для заданого джерела.

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


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


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


Завдання

Задати дискретне джерело повідомлень без пам'яті, що вибирає повідомлення akА, де А - множина літер прізвища, імені, по-батькові українською мовою.

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

Для ансамблю повідомлень побудувати коди:

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

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

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

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

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

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

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

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

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


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

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

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, що вказує на наявність у ній помилки.


Висновки

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


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


  1   2   3



Скачать файл (889.4 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации