Міністерство освіти і науки РФ
Пензенський державний університет
Кафедра «Інформаційної безпеки систем та технологій»
Пояснювальна записка до курсової роботи
по темі:
«Розрахунок інформаційних характеристик джерел повідомлень, сигналів і кодів»
ПГУ 2.010905.001 ПЗ
Дисципліна: Теорія інформації
Пенза, 2008р.
Реферат
АНСАМБЛЬ ПОВІДОМЛЕННЯ, дискретних повідомлень, ДЖЕРЕЛО ПОВІДОМЛЕНЬ, КАНАЛ БЕЗ ШУМУ, канал з шумом, ЕФФЕТІВНОЕ КОДУВАННЯ, завадостійкого кодування, ЕНТРОПІЯ.
Об'єктом дослідження є джерела повідомлень, сигнали і кодів.
Метою роботи є розрахунок інформаційних характеристик джерела повідомлень, сигналів і кодів.
У процесі роботи було зроблено розрахунок різних інформаційних характеристик джерел повідомлень, сигналів і кодів.
У результаті роботи всі завдання були вирішені і всі вимоги завдання були виконані.
Зміст
Реферат
Введення
1. Розрахунок інформаційних характеристик джерел дискретних повідомлень
1.1 Завдання № 1.30
1.2 Завдання № 1.48
1.3 Завдання № 1.67
2. Розрахунок інформаційних характеристик дискретного каналу
2.1 Завдання № 2.24
2.2 Завдання № 2.58
3. Узгодження дискретного джерела з дискретним каналом без шуму. Ефективне кодування
3.1 Завдання № 3.24
3.2 Завдання № 3.54
3.3 Завдання № 3.84
3.4 Завдання № 3.114
4. Узгодження дискретного джерела з дискретним каналом з шумом. Завадостійке кодування
4.1 Завдання № 4.24
4.2 Завдання № 4.54
Висновок
Список використаних джерел
Введення
Ефективна організація обміну інформації набуває все більшого значення як умова успішної практичної діяльності людей. Обсяг інформації, необхідної для нормального функціонування сучасного суспільства, зростає приблизно пропорційно квадрату розвитку промислового потенціалу. Частка робочої сили зайнятої питаннями забезпечення інформацією починає перевищувати частку робочої сили зайнятої безпосередньо у виробництві. Тому науки, що вивчають структуру і закономірності протікання інформаційних процесів, до числа яких належить і теорія інформації (ТІ), в такій ситуації стають виключно актуальними.
Дисципліна пов'язана з попередніми їй дисциплінами "Вища математика", "Теорія ймовірності та матстатістіка", "Дискретна математика" і наступними дисциплінами "Комп'ютерна електроніка", "Обчислювальні системи", "Мережі ЕОМ", "Надійність, контроль, діагностика та експлуатація ЕОМ" , "Основи захисту інформації" та ін
Основним завданням теорії інформації як самостійної дисципліни є оптимальне використання інформаційних характеристик джерел повідомлень і каналів зв'язку для побудови кодів, яка забезпечує задану достовірність інформації, що передається з максимально можливою швидкістю і мінімально можливою вартістю передачі повідомлень. Приватними завданнями при цьому є: проблеми вимірювання кількості інформації, вивчення властивостей інформації, вивчення методів завадостійкого кодування, дослідження взаємодії систем і елементів систем методами теорії інформації, рішення завдань прикладного характеру.
У цій роботі проводиться розрахунок основних інформаційних характеристик джерела повідомлень, сигналів і каналів. Теорія інформації являє собою гілку статистичної теорії зв'язку. Інформація передається, і зберігається у вигляді повідомлень. Повідомлення - це інформація представлена в будь-якій формі. Перший розділ курсової роботи носить назву: «Розрахунок інформаційних характеристик джерела дискретного повідомлення». Змінюється в часі фізичний процес, що відображає передане повідомлення називається сигналом. Сигнал передається по каналу зв'язку. Другий розділ роботи називається: «Розрахунок інформаційних характеристик дискретного каналу». У двох розділах вирішуються завдання за темами: узгодження дискретного джерела з дискретним каналом з шумом і без шуму, ефективне і завадостійке кодування. Їх рішення грунтуються на постулатах таких вчених як Шеннон, Хаффман, Фано.
1. Розрахунок інформаційних характеристик джерел дискретних повідомлень
1.1 Завдання № 1.30
Розподіл ймовірностей дискретної випадкової величини має вигляд:
Визначити число n значень випадкової величини, при яких ентропія H p (X) рівномірного розподілу буде дорівнює ентропії H (X) заданого розподілу.
Рішення:
Визначимо ентропію заданого розподілу. Для знаходженні ентропії даного дискретного ансамблю скористаємося формулою (1.4), що відповідає визначенню ентропії (Ентропія - це середня кількість інформації, що міститься в одному повідомлення джерела). Обчислимо ентропію розподілу:
Рівномірний розподіл передбачає рівні ймовірності всіх можливих результатів, при цьому ентропія
З умови, що
знаходимо:
Відповідь: при обсязі алфавіту n = 7, ентропія H p (X) рівномірного розподілу буде дорівнює ентропії H (X) заданого розподілу.
1.2 Завдання № 1.48
Знайти ентропію шуму H (U / Z) в двійковому симетричному каналі без пам'яті, якщо ентропія джерела на вході каналу H (U) = 3400 (біт), ентропія ансамблю на виході каналу H (Z) = 6800 (біт), ненадійність каналу H (U / Z) = 700 (біт).
Рішення:
Ентропія шуму в двійковому симетричному каналі без пам'яті будемо шукати за формулою
Висловимо, невідоме нам, кількість інформації
Підставляючи цю формулу у вихідну, отримаємо вираз для знаходження ентропії шуму в двійковому симетричному каналі
Відповідь: ентропія шуму в двійковому симетричному каналі H (U / Z) = 4100 (біт).
1.3 Завдання № 1.67
Приймає сигнал може мати амплітуду А 1 (подія Х 1) або А 2 (подія Х 2), а також зсув фаз
Обчислити кількість інформації, одержуваної про фазовий зсуві сигналу, якщо стане відомою його амплітуда.
Рішення:
Кількість інформації про фазовий зсуві при відомій амплітуді будемо шукати за формулою (1.13) лекції
Знайдемо ентропію Y:
Що б знайти ентропію, знайдемо ймовірності появи подій Y 1 і Y 2:
Знайдемо ймовірності появи подій Х 1 і Х 2:
Підставляючи значення у вищу формулу, знайдемо значення ентропії:
За формулою (1.9) лекції знайдемо
Підставляючи отримані значення у формулу, отримаємо, що
Тоді, кількість інформації про фазовий зсуві при відомій амплітуді дорівнюватиме
Відповідь: кількість інформації про фазовий зсуві при відомій амплітуді
2. Розрахунок інформаційних характеристик дискретного каналу
2.1 Завдання № 2.24
На вхід дискретного симетричного каналу без пам'яті поступають виконавчі символи U 1 = 0 і U 2 = 1 з апріорними ймовірностями P (U 1) = 0,85 і P (U 2) = 0,15. Перехідні ймовірності P (Zj / U i) в такому каналі задаються співвідношенням
де р - ймовірність помилки, р = 0,05. визначити всі апостеріорні ймовірності.
Рішення:
Ситуація в каналі характеризується схемою, зображеної на малюнку:
SHAPE \ * MERGEFORMAT
Рис. 2.1
Так як р - ймовірність помилки, отже ймовірність правильного прийому - q, причому
Знайдемо перехідні ймовірності:
У такому каналі кожен кодовий символ може бути прийнятий з помилковою ймовірністю:
Але не всі інформація, переїдають по каналу, може бути помилковою. Таким чином, правильно передана інформація описується наступним розподілом ймовірностей:
За формулою Байєса визначимо апостеріорні ймовірності:
Відповідь: апріорні ймовірності в даному каналі рівні: P (U 1 / Z 1) = 0,96; P (U 1 / Z 2) = 0,23; P (U 2 / Z 1) = 0,04; P ( U 2 / Z 2) = 0,77.
2.2 Завдання № 2.58
По каналу зв'язку передається повідомлення з ансамблю
Середня тривалість передачі одного елемента повідомлення в каналі τ = 0,44 мс. Шум у каналі відсутній. Визначити пропускну здатність каналу та швидкість передачі інформації.
Рішення:
Відповідно до (1.25.а) лекції, у разі, коли шум у каналі відсутній
Швидкість розрахуємо за формулою
Обсяг алфавіту даного повідомлення дорівнює восьми, тобто М = 8. знайдемо пропускну здатність
Швидкість передачі інформації по каналу є твори кількості інформації, що передається по каналу на швидкість:
Кількість інформації будемо шукати за формулою (1.13) лекції
Так як шум у каналі відсутня, то
Тоді, кількість інформації
Визначимо ентропію заданого розподілу. Для знаходженні ентропії даного ансамблю скористаємося формулою (1.4):
Підставляючи в отриману раніше формулу, отримаємо
Відповідь: пропускна здатність каналу С = 18184 (біт / с); швидкість передачі інформації V, = 5546,12.
3. Узгодження дискретного джерела з дискретним каналом без шуму. Ефективне кодування
3.1 Завдання № 3.24
Закодувати двійковим кодом Фано ансамбль повідомлень
Закодувати довільну комбінацію, що складається з п'яти символів ансамблю А; Визначити потенційний мінімум середньої кількості символів коду, що припадають на одне повідомлення ансамблю А; Визначити середню кількість символів розробленого коду Фано, що припадають на одне повідомлення з ансамблю А; Розрахувати ефективність розробленого коду.
Рішення:
Для зручності розташуємо ймовірності появи повідомлень у порядку убування:
Виберемо з ансамблю А довільну комбінацію з п'яти символів і закодуємо їх отриманим кодом Фано:
А 9 А 3 А 5 А 7 А 4
110111111101111111110011110.
Потенційний мінімум будемо шукати за формулою (2.12) лекції:
Так як код є двійковим, тоді підставу коду N = 2. Отже:
Тоді потенційний мінімум буде дорівнює ентропії джерела:
Знайдемо ентропію джерела, користуючись мірою Шеннона:
Розрахуємо середню кількість символів, що припадають на одне повідомлення:
М - обсяг алфавіту коду (М = 2);
P i - ймовірність появи події;
n - кількість символів в коді.
Згідно (2.12.а) лекції ефективність коду знаходимо, як:
Відповідь: потенційний мінімум
3.2 Завдання № 3.54
Закодувати кодом Фано, з об'ємом алфавіту М = 5, ансамбль
Закодувати довільну комбінацію, що складається з п'яти символів ансамблю А; Визначити потенційний мінімум середньої кількості символів коду, що припадають на одне повідомлення ансамблю А; Визначити середню кількість символів розробленого коду Фано, що припадають на одне повідомлення з ансамблю А; Розрахувати ефективність розробленого коду.
Рішення:
Для зручності розташуємо ймовірності появи повідомлень у порядку убування:
Виберемо з ансамблю А довільну комбінацію з п'яти символів і закодуємо їх отриманим кодом Фано:
А 1 А 2 А 3 А 4 А 5
321021004321044444321
Потенційний мінімум будемо шукати за формулою (2.12) лекції:
Так як код є четверичная, тоді підставу коду N = 5. Отже:
Знайдемо ентропію джерела, користуючись мірою Шеннона:
Тоді потенційний мінімум
Розрахуємо середню кількість символів, що припадають на одне повідомлення:
М - обсяг алфавіту коду (М = 5);
P i - ймовірність появи події;
n - кількість символів в коді.
Згідно (2.12.а) лекції ефективність коду знаходимо, як:
Відповідь: потенційний мінімум
3.3 Завдання № 3.84
Закодувати двійковим кодом Хаффмана ансамбль повідомлень
Пензенський державний університет
Кафедра «Інформаційної безпеки систем та технологій»
Пояснювальна записка до курсової роботи
по темі:
«Розрахунок інформаційних характеристик джерел повідомлень, сигналів і кодів»
ПГУ 2.010905.001 ПЗ
Дисципліна: Теорія інформації
Пенза, 2008р.
Реферат
АНСАМБЛЬ ПОВІДОМЛЕННЯ, дискретних повідомлень, ДЖЕРЕЛО ПОВІДОМЛЕНЬ, КАНАЛ БЕЗ ШУМУ, канал з шумом, ЕФФЕТІВНОЕ КОДУВАННЯ, завадостійкого кодування, ЕНТРОПІЯ.
Об'єктом дослідження є джерела повідомлень, сигнали і кодів.
Метою роботи є розрахунок інформаційних характеристик джерела повідомлень, сигналів і кодів.
У процесі роботи було зроблено розрахунок різних інформаційних характеристик джерел повідомлень, сигналів і кодів.
У результаті роботи всі завдання були вирішені і всі вимоги завдання були виконані.
Зміст
Реферат
Введення
1. Розрахунок інформаційних характеристик джерел дискретних повідомлень
1.1 Завдання № 1.30
1.2 Завдання № 1.48
1.3 Завдання № 1.67
2. Розрахунок інформаційних характеристик дискретного каналу
2.1 Завдання № 2.24
2.2 Завдання № 2.58
3. Узгодження дискретного джерела з дискретним каналом без шуму. Ефективне кодування
3.1 Завдання № 3.24
3.2 Завдання № 3.54
3.3 Завдання № 3.84
3.4 Завдання № 3.114
4. Узгодження дискретного джерела з дискретним каналом з шумом. Завадостійке кодування
4.1 Завдання № 4.24
4.2 Завдання № 4.54
Висновок
Список використаних джерел
Введення
Ефективна організація обміну інформації набуває все більшого значення як умова успішної практичної діяльності людей. Обсяг інформації, необхідної для нормального функціонування сучасного суспільства, зростає приблизно пропорційно квадрату розвитку промислового потенціалу. Частка робочої сили зайнятої питаннями забезпечення інформацією починає перевищувати частку робочої сили зайнятої безпосередньо у виробництві. Тому науки, що вивчають структуру і закономірності протікання інформаційних процесів, до числа яких належить і теорія інформації (ТІ), в такій ситуації стають виключно актуальними.
Дисципліна пов'язана з попередніми їй дисциплінами "Вища математика", "Теорія ймовірності та матстатістіка", "Дискретна математика" і наступними дисциплінами "Комп'ютерна електроніка", "Обчислювальні системи", "Мережі ЕОМ", "Надійність, контроль, діагностика та експлуатація ЕОМ" , "Основи захисту інформації" та ін
Основним завданням теорії інформації як самостійної дисципліни є оптимальне використання інформаційних характеристик джерел повідомлень і каналів зв'язку для побудови кодів, яка забезпечує задану достовірність інформації, що передається з максимально можливою швидкістю і мінімально можливою вартістю передачі повідомлень. Приватними завданнями при цьому є: проблеми вимірювання кількості інформації, вивчення властивостей інформації, вивчення методів завадостійкого кодування, дослідження взаємодії систем і елементів систем методами теорії інформації, рішення завдань прикладного характеру.
У цій роботі проводиться розрахунок основних інформаційних характеристик джерела повідомлень, сигналів і каналів. Теорія інформації являє собою гілку статистичної теорії зв'язку. Інформація передається, і зберігається у вигляді повідомлень. Повідомлення - це інформація представлена в будь-якій формі. Перший розділ курсової роботи носить назву: «Розрахунок інформаційних характеристик джерела дискретного повідомлення». Змінюється в часі фізичний процес, що відображає передане повідомлення називається сигналом. Сигнал передається по каналу зв'язку. Другий розділ роботи називається: «Розрахунок інформаційних характеристик дискретного каналу». У двох розділах вирішуються завдання за темами: узгодження дискретного джерела з дискретним каналом з шумом і без шуму, ефективне і завадостійке кодування. Їх рішення грунтуються на постулатах таких вчених як Шеннон, Хаффман, Фано.
1. Розрахунок інформаційних характеристик джерел дискретних повідомлень
1.1 Завдання № 1.30
Розподіл ймовірностей дискретної випадкової величини має вигляд:
Визначити число n значень випадкової величини, при яких ентропія H p (X) рівномірного розподілу буде дорівнює ентропії H (X) заданого розподілу.
Рішення:
Визначимо ентропію заданого розподілу. Для знаходженні ентропії даного дискретного ансамблю скористаємося формулою (1.4), що відповідає визначенню ентропії (Ентропія - це середня кількість інформації, що міститься в одному повідомлення джерела). Обчислимо ентропію розподілу:
Рівномірний розподіл передбачає рівні ймовірності всіх можливих результатів, при цьому ентропія
З умови, що
знаходимо:
Відповідь: при обсязі алфавіту n = 7, ентропія H p (X) рівномірного розподілу буде дорівнює ентропії H (X) заданого розподілу.
1.2 Завдання № 1.48
Знайти ентропію шуму H (U / Z) в двійковому симетричному каналі без пам'яті, якщо ентропія джерела на вході каналу H (U) = 3400 (біт), ентропія ансамблю на виході каналу H (Z) = 6800 (біт), ненадійність каналу H (U / Z) = 700 (біт).
Рішення:
Ентропія шуму в двійковому симетричному каналі без пам'яті будемо шукати за формулою
Висловимо, невідоме нам, кількість інформації
Підставляючи цю формулу у вихідну, отримаємо вираз для знаходження ентропії шуму в двійковому симетричному каналі
Відповідь: ентропія шуму в двійковому симетричному каналі H (U / Z) = 4100 (біт).
1.3 Завдання № 1.67
Приймає сигнал може мати амплітуду А 1 (подія Х 1) або А 2 (подія Х 2), а також зсув фаз
Обчислити кількість інформації, одержуваної про фазовий зсуві сигналу, якщо стане відомою його амплітуда.
Рішення:
Кількість інформації про фазовий зсуві при відомій амплітуді будемо шукати за формулою (1.13) лекції
Знайдемо ентропію Y:
Що б знайти ентропію, знайдемо ймовірності появи подій Y 1 і Y 2:
Знайдемо ймовірності появи подій Х 1 і Х 2:
Підставляючи значення у вищу формулу, знайдемо значення ентропії:
За формулою (1.9) лекції знайдемо
Підставляючи отримані значення у формулу, отримаємо, що
Тоді, кількість інформації про фазовий зсуві при відомій амплітуді дорівнюватиме
Відповідь: кількість інформації про фазовий зсуві при відомій амплітуді
2. Розрахунок інформаційних характеристик дискретного каналу
2.1 Завдання № 2.24
На вхід дискретного симетричного каналу без пам'яті поступають виконавчі символи U 1 = 0 і U 2 = 1 з апріорними ймовірностями P (U 1) = 0,85 і P (U 2) = 0,15. Перехідні ймовірності P (Zj / U i) в такому каналі задаються співвідношенням
де р - ймовірність помилки, р = 0,05. визначити всі апостеріорні ймовірності.
Рішення:
Ситуація в каналі характеризується схемою, зображеної на малюнку:
SHAPE \ * MERGEFORMAT
канал |
U 1 = 0 |
Z 1 = 0 |
U 2 = 1 |
Z 2 = 1 |
шум |
Рис. 2.1
Так як р - ймовірність помилки, отже ймовірність правильного прийому - q, причому
Знайдемо перехідні ймовірності:
У такому каналі кожен кодовий символ може бути прийнятий з помилковою ймовірністю:
Але не всі інформація, переїдають по каналу, може бути помилковою. Таким чином, правильно передана інформація описується наступним розподілом ймовірностей:
За формулою Байєса визначимо апостеріорні ймовірності:
Відповідь: апріорні ймовірності в даному каналі рівні: P (U 1 / Z 1) = 0,96; P (U 1 / Z 2) = 0,23; P (U 2 / Z 1) = 0,04; P ( U 2 / Z 2) = 0,77.
2.2 Завдання № 2.58
По каналу зв'язку передається повідомлення з ансамблю
Середня тривалість передачі одного елемента повідомлення в каналі τ = 0,44 мс. Шум у каналі відсутній. Визначити пропускну здатність каналу та швидкість передачі інформації.
Рішення:
Відповідно до (1.25.а) лекції, у разі, коли шум у каналі відсутній
Швидкість розрахуємо за формулою
Обсяг алфавіту даного повідомлення дорівнює восьми, тобто М = 8. знайдемо пропускну здатність
Швидкість передачі інформації по каналу є твори кількості інформації, що передається по каналу на швидкість:
Кількість інформації будемо шукати за формулою (1.13) лекції
Так як шум у каналі відсутня, то
Тоді, кількість інформації
Визначимо ентропію заданого розподілу. Для знаходженні ентропії даного ансамблю скористаємося формулою (1.4):
Підставляючи в отриману раніше формулу, отримаємо
Відповідь: пропускна здатність каналу С = 18184 (біт / с); швидкість передачі інформації V, = 5546,12.
3. Узгодження дискретного джерела з дискретним каналом без шуму. Ефективне кодування
3.1 Завдання № 3.24
Закодувати двійковим кодом Фано ансамбль повідомлень
| А 1 | А 2 | А 3 | А 4 | А 5 | А 6 | А 7 | А 8 | А 9 | А 10 | А 11 | А 12 |
| 0,088 | 0,065 | 0,035 | 0,062 | 0,06 | 0,059 | 0,097 | 0,3 | 0,068 | 0,044 | 0,054 | 0,122 |
Рішення:
Для зручності розташуємо ймовірності появи повідомлень у порядку убування:
| А 8 | 0,3 | 0 |
| А 12 | 0,122 | 10 |
| А 7 | 0,097 | 100 |
| А 1 | 0,088 | 101 |
| А 9 | 0,068 | 110 |
| А 2 | 0,065 | 1110 |
| А 4 | 0,062 | 11110 |
| А 6 | 0,059 | 111110 |
| А 11 | 0,054 | 1111110 |
| А 10 | 0,044 | 1111110 |
| А 3 | 0,035 | 11111110 |
| А 5 | 0,006 | 11111111 |
Виберемо з ансамблю А довільну комбінацію з п'яти символів і закодуємо їх отриманим кодом Фано:
А 9 А 3 А 5 А 7 А 4
110111111101111111110011110.
Потенційний мінімум будемо шукати за формулою (2.12) лекції:
Так як код є двійковим, тоді підставу коду N = 2. Отже:
Тоді потенційний мінімум буде дорівнює ентропії джерела:
Знайдемо ентропію джерела, користуючись мірою Шеннона:
Розрахуємо середню кількість символів, що припадають на одне повідомлення:
М - обсяг алфавіту коду (М = 2);
P i - ймовірність появи події;
n - кількість символів в коді.
| P 1 = 0,088 | n 1 = 3 |
| P 2 = 0,065 | n 2 = 4 |
| P 3 = 0,035 | n 3 = 8 |
| P 4 = 0,062 | n 4 = 5 |
| P 5 = 0,006 | n 5 = 8 |
| P 6 = 0,059 | n 6 = 6 |
| P 7 = 0,097 | n 7 = 3 |
| P 8 = 0,3 | n 8 = 1 |
| P 9 = 0,068 | n 9 = 3 |
| P 10 = 0,044 | n 10 = 7 |
| P 11 = 0,054 | n 11 = 7 |
| P 12 = 0,122 | n 12 = 2 |
Згідно (2.12.а) лекції ефективність коду знаходимо, як:
Відповідь: потенційний мінімум
3.2 Завдання № 3.54
Закодувати кодом Фано, з об'ємом алфавіту М = 5, ансамбль
| А 1 | А 2 | А 3 | А 4 | А 5 | А 6 | А 7 | А 8 | А 9 | А 10 | А 11 | А 12 |
| 0,082 | 0,122 | 0,503 | 0,04 | 0,012 | 0,002 | 0,005 | 0,034 | 0,124 | 0,006 | 0,0395 | 0,0305 |
Рішення:
Для зручності розташуємо ймовірності появи повідомлень у порядку убування:
| А 3 | 0,503 | 0 |
| А 9 | 0,124 | 10 |
| А 2 | 0,122 | 210 |
| A 1 | 0,082 | 3210 |
| А 4 | 0,04 | 43210 |
| А 11 | 0,0395 | 443210 |
| А 8 | 0,034 | 4443210 |
| А 12 | 0,0305 | 44443210 |
| А 5 | 0,012 | 44444321 |
| А 10 | 0,006 | 44444432 |
| А 7 | 0,005 | 44444443 |
| А 6 | 0,002 | 44444444 |
Виберемо з ансамблю А довільну комбінацію з п'яти символів і закодуємо їх отриманим кодом Фано:
А 1 А 2 А 3 А 4 А 5
321021004321044444321
Потенційний мінімум будемо шукати за формулою (2.12) лекції:
Так як код є четверичная, тоді підставу коду N = 5. Отже:
Знайдемо ентропію джерела, користуючись мірою Шеннона:
Тоді потенційний мінімум
Розрахуємо середню кількість символів, що припадають на одне повідомлення:
М - обсяг алфавіту коду (М = 5);
P i - ймовірність появи події;
n - кількість символів в коді.
| P 1 = 0,82 | n 1 = 4 |
| P 2 = 0,122 | n 2 = 3 |
| P 3 = 0,503 | n 3 = 1 |
| P 4 = 0,004 | n 4 = 5 |
| P 5 = 0,012 | n 5 = 8 |
| P 6 = 0,002 | n 6 = серпня |
| P 7 = 0,005 | n 7 = 8 |
| P 8 = 0,034 | n 8 = 7 |
| P 9 = 0,124 | n 9 = 2 |
| P 10 = 0,006 | n 10 = 8 |
| P 11 = 0,0395 | n 11 = 6 |
| P 12 = 0,0305 | n 12 = 8 |
Згідно (2.12.а) лекції ефективність коду знаходимо, як:
Відповідь: потенційний мінімум
3.3 Завдання № 3.84
Закодувати двійковим кодом Хаффмана ансамбль повідомлень
| А 1 | А 2 | А 3 | А 4 | А 5 | А 6 | А 7 | А 8 | А 9 | А 10 | А 11 | А 12 |
| 0,082 | 0,122 | 0,503 | 0,04 | 0,012 | 0,002 | 0,005 | 0,034 | 0,124 | 0,006 | 0,0395 | 0,0305 |
Закодувати довільну комбінацію, що складається з п'яти символів ансамблю А; Визначити потенційний мінімум середньої кількості символів коду, що припадають на одне повідомлення ансамблю А; Визначити середню кількість символів розробленого коду Хаффмана, що припадають на одне повідомлення з ансамблю А; Розрахувати ефективність розробленого коду.
Рішення:
Для зручності закодованість розташуємо ймовірності появи повідомлень у порядку убування. Дві останні ймовірності об'єднуємо в одну допоміжну букву, якої приписується сумарна ймовірність. Ймовірно, не враховуються в об'єднанні, і сумарна ймовірність знову розташуємо в порядку убування. Отриманий ряд ймовірностей записуємо в таблицю і дві останні знову об'єднуємо. Процес будемо повторювати до останньої допоміжної літери, з імовірністю, рівній одиниці.
Потім будується кодове дерево, в процесі якого здійснюється кодування: верхня точка дерева дорівнює одиниці; з неї направляється дві гілки, причому, гілки з більшою ймовірністю приписується значення «1», а з меншою - «0». Таке послідовне розгалуження продовжується до тих пір, поки не добираються ймовірності кожної літери.
SHAPE \ * MERGEFORMAT
Рис. 3.1
Потім, рухаючись по кодовому дереву зверху вниз, записуємо для кожної літери відповідну їй кодову комбінацію:
Виберемо з ансамблю А довільну комбінацію з п'яти символів і закодуємо їх отриманим кодом Хаффмана:
А 1 А 2 А 7 А 6 А 4
011100100010111000101100000.
Потенційний мінімум будемо шукати за формулою (2.12) лекції:
Так як код є двійковим, тоді підставу коду N = 2. Отже:
Знайдемо ентропію джерела, користуючись мірою Шеннона:
Розрахуємо середню кількість символів, що припадають на одне повідомлення:
М - обсяг алфавіту коду (М = 2);
P i - ймовірність появи події;
n - кількість символів в коді.
Згідно (2.12.а) лекції ефективність коду знаходимо, як:
Відповідь: потенційний мінімум
3.4 Завдання № 3.114
Закодувати кодом Хаффмана, з об'ємом алфавіту М = 5, ансамбль
Закодувати довільну комбінацію, що складається з п'яти символів ансамблю А; Визначити потенційний мінімум середньої кількості символів коду, що припадають на одне повідомлення ансамблю А; Визначити середню кількість символів розробленого коду Хаффмана, що припадають на одне повідомлення з ансамблю А; Розрахувати ефективність розробленого коду.
Рішення:
Для зручності закодованість розташуємо ймовірності появи повідомлень у порядку убування. Чотири останні ймовірності об'єднуємо в одну допоміжну букву, якої приписується сумарна ймовірність. Ймовірно, не враховуються в об'єднанні, і сумарна ймовірність знову розташуємо в порядку убування. Отриманий ряд ймовірностей записуємо в таблицю і чотири останні знову об'єднуємо. Процес будемо повторювати до останньої допоміжної літери, з імовірністю, рівній одиниці.
Потім будується кодове дерево, в процесі якого здійснюється кодування: верхня точка дерева дорівнює одиниці; з неї направляється чотири гілки, причому, гілки з більшою ймовірністю приписується значення «4», а з меншою - «0». Таке послідовне розгалуження продовжується до тих пір, поки не добираються ймовірності кожної літери.
SHAPE \ * MERGEFORMAT
Рис.3.2
Потім, рухаючись по кодовому дереву зверху вниз, записуємо для кожної літери відповідну їй кодову комбінацію:
Виберемо з ансамблю А довільну комбінацію з п'яти символів і закодуємо їх отриманим кодом Хаффмана:
А 8 А 7 А 6 А 5 А 4
2023023023322.
Потенційний мінімум будемо шукати за формулою (2.12) лекції:
Так як код є четверичная, тоді підставу коду N = 5. Отже:
Знайдемо ентропію джерела, користуючись мірою Шеннона:
Тоді потенційний мінімум
Розрахуємо середню кількість символів, що припадають на одне повідомлення:
М - обсяг алфавіту коду (М = 5);
P i - ймовірність появи події;
n - кількість символів в коді.
Згідно (2.12.а) лекції ефективність коду знаходимо, як:
Відповідь: потенційний мінімум
4. Узгодження дискретного джерела з дискретним каналом з шумом. Завадостійке кодування
4.1 Завдання № 4.24
Визначити надлишкового оптимального за Шеннону коду (існування якого затверджується теоремою для каналу з шумом) з об'ємом алфавіту М = 3 і середньою кількістю символів, переданих в одиницю часу - V k, призначеного для безпомилкової передачі інформації по каналу з пропускною здатністю С. Знайти мінімально можливу надмірність оптимального коду для симетричного каналу з імовірністю помилки Р = 0,1.
Рішення:
Відповідно до (1.12) лекції, надмірність джерела дискретного повідомлення з об'ємом алфавіту М називається величина
Причому, якщо ввести поняття продуктивності
Те величину
Так як передача інформації передбачає, що безпомилкове кодування повинно бути однозначним, тобто втрати інформації при кодуванні повинні бути відсутніми. Це означає, що продуктивність каналу повинна бути дорівнює продуктивності джерела повідомлення, тобто
Відповідно з умовою (2.15) теореми Шеннона
або для оптимального коду
Тому, остаточна формула для обчислення надмірності буде виглядати:
Відповідно до § 1.6 лекції, середня кількість символів, що передаються в одиницю часу будемо визначати за формулою (1.27.а):
Підставляючи отримане значення в виведену формулу надмірності, отримаємо:
Відповідь: мінімальна можлива надмірність оптимального коду для симетричного каналу з імовірністю помилки Р = 0,1 і обсягом алфавіту М = 3 буде дорівнює
4.2 Завдання № 4.54
Побудувати виробляє матрицю G лінійного двійкового блокового коду, здатного виправляти одиночну помилку при передачі дискретних повідомлень джерела, що представляють собою послідовність десяткових цифр з діапазону 0 ... M-1 (з об'ємом алфавіту M = 1981). Користуючись розробленою матрицею G, сформувати кодову комбінацію для повідомлення i (i = 1569). Побудувати відповідну виробляє матриці G перевірочну матрицю H і з її допомогою сформувати кодову комбінацію для повідомлення i. По виду синдрому знайти і виправити помилку в прийнятої кодової комбінації (додатково заданої викладачем). Визначити, чи є розроблений код кодом Хеммінга.
Рішення:
Твірна матриця G лінійного двійкового блокового коду має розмірність (n; k). Так як код є двійковим, то
Звідси знаходимо k:
Матриця G лінійного двійкового коду складається з двох матриць:
Побудуємо матрицю I: I - це одинична матриця, розмірності (k; k), при k = 11
Побудуємо матрицю П: П - має розмірність (k; nk), k - число рядків, а n - число стовпців.
Матрицю П будемо будувати за певними правилами:
1. так як код повинен виправляти одиничну помилку, отримаємо, що справна здатність буде дорівнює одиниці, тобто
В одній стоці матриці повинна бути не менш d - 1 одиниць. Знайдемо d як
2. всі рядки повинні бути різними;
3. число елементів в стоці повинен бути мінімальний.
Використовуючи правила побудови, отримаємо матрицю П:
n - k = 4
k = 11
n = 15
Після побудови допоміжних матриць, можна побудувати матрицю G:
Перевірочна матриця Н має розмірність (nk; k) і являє собою транспоновану матрицю П:
Користуючись розробленою матрицею G, сформуємо кодову комбінацію для повідомлення - i (i = 1569). Переведемо її з десяткового в двійковий вид: 1569
Дозволена комбінація
Вийде кодова комбінація V i
Отримана комбінація складається з інформаційних і перевірочних розрядів:
Кожен перевірочний розряд представляє собою суму інформаційних розрядів, взятих з деяким коефіцієнтом
j = 1:
j = 2:
j = 3:
j = 4:
1. з інформаційних розрядами задається комбінація, яка визначає перевірочні розряди;
2. складаємо за модулем два отримані перевірочні розряди з тими, які мають місце у прийнятій комбінації. Результатом є синдром.
Для того, що б за допомогою синдрому знайти помилку, знайдемо матрицю Н перевірочну:
де I - одинична матриця, розмірності (nk; nk)
Спробуємо знайти помилку за допомогою синдрому: нехай отримана наступна комбінація - [101000001111100]. Скористаємося правилом знаходження синдрому:
1. з інформаційних розрядами визначаємо перевірочні розряди вихідного коду - [1001];
2. складаємо за модулем два отримані перевірочні розряди і ті, які мають місце у прийнятій комбінації:
[1001]
Тепер будуємо перевірочну матрицю Н перевірочну:
Знайдемо в Н перевірочної стовпець, що співпадає з комбінацією синдрому. Номер цього стовпця вказує на номер стовпця в прийнятій комбінації, в якій допущена помилка. У нашому випадку комбінація синдрому збігається з 2 стовпцем Н перевірочну.
Для виправлення цієї помилки треба інвертувати значення цього розряду. Тоді у нас виходить - [111000001111100].
Код Хеммінга, це код (n; k), що визначається:
Отримана мною матриця має розмірність
Висновок
В результаті виконання курсової роботи були прорешени завдання з наступних тем: розрахунок інформаційних характеристик джерел дискретних повідомлень, розрахунок інформаційних характеристик дискретного каналу, узгодження дискретного джерела з дискретним каналом без шуму, ефективне кодування, узгодження дискретного джерела з дискретним каналом з шумом, завадостійке кодування. Отримані при цьому знання, як слід очікувати, будуть успішно використовуватися надалі.
Вирішені завдання можуть бути простим прикладом застосування знання основ теорії інформації для практичних цілей.
В результаті виконання роботи всі вимоги завдання були виконані.
Список використаних джерел
1. Прикладна теорія інформації: Навч. Для студ. ВНЗ по спец. «Автоматизовані системи обробки інформації та управління». - М.: Вищ. шк., 1989. - 320с.: Іл.
Рішення:
Для зручності закодованість розташуємо ймовірності появи повідомлень у порядку убування. Дві останні ймовірності об'єднуємо в одну допоміжну букву, якої приписується сумарна ймовірність. Ймовірно, не враховуються в об'єднанні, і сумарна ймовірність знову розташуємо в порядку убування. Отриманий ряд ймовірностей записуємо в таблицю і дві останні знову об'єднуємо. Процес будемо повторювати до останньої допоміжної літери, з імовірністю, рівній одиниці.
| А 3 | 0,503 | 0,503 | 0,503 | 0,503 | 0,503 | 0,503 | 0,503 | 0,503 | 0,503 | 0,503 | 0,503 | 1 |
| А 9 | 0,124 | 0,124 | 0,124 | 0,124 | 0,124 | 0,124 | 0,124 | 0,1555 | 0,2175 | 0,2795 | 0,497 | |
| А 2 | 0,122 | 0,122 | 0,122 | 0,122 | 0,122 | 0,122 | 0,122 | 0,124 | 0,1555 | 0,2175 | ||
| A 1 | 0,082 | 0,082 | 0,082 | 0,082 | 0,082 | 0,082 | 0,0955 | 0,122 | 0,124 | |||
| А 4 | 0,04 | 0,04 | 0,04 | 0,04 | 0,0555 | 0,0735 | 0,082 | 0,0955 | ||||
| А 11 | 0,0395 | 0,0395 | 0,0395 | 0,0395 | 0,04 | 0,0555 | 0,0735 | |||||
| А 8 | 0,034 | 0,034 | 0,034 | 0,034 | 0,0395 | 0,04 | ||||||
| А 12 | 0,0305 | 0,0305 | 0,0305 | 0,0305 | 0,034 | |||||||
| А 5 | 0,012 | 0,012 | 0,013 | 0,025 | ||||||||
| А 10 | 0,006 | 0,007 | 0,012 | |||||||||
| А 7 | 0,005 | 0,006 | ||||||||||
| А 6 | 0,002 |
SHAPE \ * MERGEFORMAT
1 |
0,, 503 |
0,497 |
0,2795 |
0,2175 |
0,124 |
0,1555 |
0,082 |
0,0735 |
0,0395 |
0,034 |
0,122 |
0,0955 |
0,04 |
0,0555 |
0,0305 |
0,025 |
0,013 |
0,012 |
0,007 |
0,006 |
0,005 |
0,002 |
Рис. 3.1
Потім, рухаючись по кодовому дереву зверху вниз, записуємо для кожної літери відповідну їй кодову комбінацію:
| P 1 = 0,82 | 0111 | n 1 = 4 |
| P 2 = 0,122 | 001 | n 2 = 3 |
| P 3 = 0,503 | 1 | n 3 = 1 |
| P 4 = 0,004 | 0000 | n 4 = 4 |
| P 5 = 0,012 | 000100 | n 5 = 6 |
| P 6 = 0,002 | 00010110 | n 6 = серпня |
| P 7 = 0,005 | 00010111 | n 7 = 8 |
| P 8 = 0,034 | 01100 | n 8 = 5 |
| P 9 = 0,124 | 010 | n 9 = 3 |
| P 10 = 0,006 | 0001010 | n 10 = 7 |
| P 11 = 0,0395 | 01101 | n 11 = 5 |
| P 12 = 0,0305 | 00011 | n 12 = 5 |
А 1 А 2 А 7 А 6 А 4
011100100010111000101100000.
Потенційний мінімум будемо шукати за формулою (2.12) лекції:
Так як код є двійковим, тоді підставу коду N = 2. Отже:
Знайдемо ентропію джерела, користуючись мірою Шеннона:
Розрахуємо середню кількість символів, що припадають на одне повідомлення:
М - обсяг алфавіту коду (М = 2);
P i - ймовірність появи події;
n - кількість символів в коді.
Згідно (2.12.а) лекції ефективність коду знаходимо, як:
Відповідь: потенційний мінімум
3.4 Завдання № 3.114
Закодувати кодом Хаффмана, з об'ємом алфавіту М = 5, ансамбль
| А 1 | А 2 | А 3 | А 4 | А 5 | А 6 | А 7 | А 8 | А 9 | А 10 | А 11 | А 12 |
| 0,082 | 0,122 | 0,503 | 0,04 | 0,012 | 0,002 | 0,005 | 0,034 | 0,124 | 0,006 | 0,0395 | 0,0305 |
Рішення:
Для зручності закодованість розташуємо ймовірності появи повідомлень у порядку убування. Чотири останні ймовірності об'єднуємо в одну допоміжну букву, якої приписується сумарна ймовірність. Ймовірно, не враховуються в об'єднанні, і сумарна ймовірність знову розташуємо в порядку убування. Отриманий ряд ймовірностей записуємо в таблицю і чотири останні знову об'єднуємо. Процес будемо повторювати до останньої допоміжної літери, з імовірністю, рівній одиниці.
| А 3 | 0,503 | 0,503 | 0,503 | 1 |
| А 9 | 0,124 | 0,124 | 0,251 | |
| А 2 | 0,122 | 0,122 | 0,124 | |
| A 1 | 0,082 | 0,082 | 0,122 | |
| А 4 | 0,04 | 0,0555 | ||
| А 11 | 0,0395 | 0,04 | ||
| А 8 | 0,034 | 0,0395 | ||
| А 12 | 0,0305 | 0,034 | ||
| А 5 | 0,012 | |||
| А 10 | 0,006 | |||
| А 7 | 0,005 | |||
| А 6 | 0,002 |
SHAPE \ * MERGEFORMAT
1 |
0,503 |
0,0555 |
0,122 |
0,082 |
0,124 |
0,04 |
0,0395 |
0,034 |
0,0305 |
0,251 |
0,012 |
0,002 |
0,005 |
0,006 |
Рис.3.2
Потім, рухаючись по кодовому дереву зверху вниз, записуємо для кожної літери відповідну їй кодову комбінацію:
| P 1 = 0,82 | 24 | n 1 = 2 |
| P 2 = 0,122 | 0 | n 2 = 1 |
| P 3 = 0,503 | 3 | n 3 = 1 |
| P 4 = 0,004 | 22 | n 4 = 2 |
| P 5 = 0,012 | 233 | n 5 = 3 |
| P 6 = 0,002 | 230 | n 6 = 3 |
| P 7 = 0,005 | 231 | n 7 = 3 |
| P 8 = 0,034 | 20 | n 8 = 2 |
| P 9 = 0,124 | 1 | n 9 = 1 |
| P 10 = 0,006 | 232 | n 10 = 3 |
| P 11 = 0,0395 | 21 | n 11 = 2 |
| P 12 = 0,0305 | 234 | n 12 = 3 |
А 8 А 7 А 6 А 5 А 4
2023023023322.
Потенційний мінімум будемо шукати за формулою (2.12) лекції:
Так як код є четверичная, тоді підставу коду N = 5. Отже:
Знайдемо ентропію джерела, користуючись мірою Шеннона:
Тоді потенційний мінімум
Розрахуємо середню кількість символів, що припадають на одне повідомлення:
М - обсяг алфавіту коду (М = 5);
P i - ймовірність появи події;
n - кількість символів в коді.
Згідно (2.12.а) лекції ефективність коду знаходимо, як:
Відповідь: потенційний мінімум
4. Узгодження дискретного джерела з дискретним каналом з шумом. Завадостійке кодування
4.1 Завдання № 4.24
Визначити надлишкового оптимального за Шеннону коду (існування якого затверджується теоремою для каналу з шумом) з об'ємом алфавіту М = 3 і середньою кількістю символів, переданих в одиницю часу - V k, призначеного для безпомилкової передачі інформації по каналу з пропускною здатністю С. Знайти мінімально можливу надмірність оптимального коду для симетричного каналу з імовірністю помилки Р = 0,1.
Рішення:
Відповідно до (1.12) лекції, надмірність джерела дискретного повідомлення з об'ємом алфавіту М називається величина
Причому, якщо ввести поняття продуктивності
Те величину
Так як передача інформації передбачає, що безпомилкове кодування повинно бути однозначним, тобто втрати інформації при кодуванні повинні бути відсутніми. Це означає, що продуктивність каналу повинна бути дорівнює продуктивності джерела повідомлення, тобто
Відповідно з умовою (2.15) теореми Шеннона
або для оптимального коду
Тому, остаточна формула для обчислення надмірності буде виглядати:
Відповідно до § 1.6 лекції, середня кількість символів, що передаються в одиницю часу будемо визначати за формулою (1.27.а):
Підставляючи отримане значення в виведену формулу надмірності, отримаємо:
Відповідь: мінімальна можлива надмірність оптимального коду для симетричного каналу з імовірністю помилки Р = 0,1 і обсягом алфавіту М = 3 буде дорівнює
4.2 Завдання № 4.54
Побудувати виробляє матрицю G лінійного двійкового блокового коду, здатного виправляти одиночну помилку при передачі дискретних повідомлень джерела, що представляють собою послідовність десяткових цифр з діапазону 0 ... M-1 (з об'ємом алфавіту M = 1981). Користуючись розробленою матрицею G, сформувати кодову комбінацію для повідомлення i (i = 1569). Побудувати відповідну виробляє матриці G перевірочну матрицю H і з її допомогою сформувати кодову комбінацію для повідомлення i. По виду синдрому знайти і виправити помилку в прийнятої кодової комбінації (додатково заданої викладачем). Визначити, чи є розроблений код кодом Хеммінга.
Рішення:
Твірна матриця G лінійного двійкового блокового коду має розмірність (n; k). Так як код є двійковим, то
Звідси знаходимо k:
Матриця G лінійного двійкового коду складається з двох матриць:
Побудуємо матрицю I: I - це одинична матриця, розмірності (k; k), при k = 11
Побудуємо матрицю П: П - має розмірність (k; nk), k - число рядків, а n - число стовпців.
Матрицю П будемо будувати за певними правилами:
1. так як код повинен виправляти одиничну помилку, отримаємо, що справна здатність буде дорівнює одиниці, тобто
В одній стоці матриці повинна бути не менш d - 1 одиниць. Знайдемо d як
2. всі рядки повинні бути різними;
3. число елементів в стоці повинен бути мінімальний.
Використовуючи правила побудови, отримаємо матрицю П:
n - k = 4
k = 11
n = 15
Після побудови допоміжних матриць, можна побудувати матрицю G:
Перевірочна матриця Н має розмірність (nk; k) і являє собою транспоновану матрицю П:
Користуючись розробленою матрицею G, сформуємо кодову комбінацію для повідомлення - i (i = 1569). Переведемо її з десяткового в двійковий вид: 1569
Дозволена комбінація
Вийде кодова комбінація V i
Отримана комбінація складається з інформаційних і перевірочних розрядів:
Кожен перевірочний розряд представляє собою суму інформаційних розрядів, взятих з деяким коефіцієнтом
j = 1:
j = 2:
j = 3:
j = 4:
1. з інформаційних розрядами задається комбінація, яка визначає перевірочні розряди;
2. складаємо за модулем два отримані перевірочні розряди з тими, які мають місце у прийнятій комбінації. Результатом є синдром.
Для того, що б за допомогою синдрому знайти помилку, знайдемо матрицю Н перевірочну:
де I - одинична матриця, розмірності (nk; nk)
Спробуємо знайти помилку за допомогою синдрому: нехай отримана наступна комбінація - [101000001111100]. Скористаємося правилом знаходження синдрому:
1. з інформаційних розрядами визначаємо перевірочні розряди вихідного коду - [1001];
2. складаємо за модулем два отримані перевірочні розряди і ті, які мають місце у прийнятій комбінації:
[1001]
Тепер будуємо перевірочну матрицю Н перевірочну:
Знайдемо в Н перевірочної стовпець, що співпадає з комбінацією синдрому. Номер цього стовпця вказує на номер стовпця в прийнятій комбінації, в якій допущена помилка. У нашому випадку комбінація синдрому збігається з 2 стовпцем Н перевірочну.
Для виправлення цієї помилки треба інвертувати значення цього розряду. Тоді у нас виходить - [111000001111100].
Код Хеммінга, це код (n; k), що визначається:
Отримана мною матриця має розмірність
Висновок
В результаті виконання курсової роботи були прорешени завдання з наступних тем: розрахунок інформаційних характеристик джерел дискретних повідомлень, розрахунок інформаційних характеристик дискретного каналу, узгодження дискретного джерела з дискретним каналом без шуму, ефективне кодування, узгодження дискретного джерела з дискретним каналом з шумом, завадостійке кодування. Отримані при цьому знання, як слід очікувати, будуть успішно використовуватися надалі.
Вирішені завдання можуть бути простим прикладом застосування знання основ теорії інформації для практичних цілей.
В результаті виконання роботи всі вимоги завдання були виконані.
Список використаних джерел
1. Прикладна теорія інформації: Навч. Для студ. ВНЗ по спец. «Автоматизовані системи обробки інформації та управління». - М.: Вищ. шк., 1989. - 320с.: Іл.