ЗМІСТ
Зміст
Анотація
Введення
Зміст завдання
Теоретична частина
Практична частина
а) розрахунки
б) програма
Висновок
а) результати роботи програми
б) блок-схема
Література
АНОТАЦІЯ
У цій роботі по даному числу символів в алфавіті розраховуються їх ймовірності, кількість інформації, якщо символи зустрічаються з рівними ймовірностями і з різними ймовірностями, недовантаження символів, швидкість передачі повідомлень і надмірність повідомлень. Крім того, в даній роботі будується оптимальний двійковий код за методикою Шеннона - Фано. Виконання цієї курсової роботи закріплює наші знання з дисципліни «Теорія інформації».
До роботи додається програма, написана мовою програмування високого рівня (Turbo Pascal).
SUMMARY
In this work on the given numbeof symbols in the alphabet their probabilities, amount of the information if symbols meet equal probabilities and with different probabilities, speed of message transfer and redundancy of messages pay off. Besides in the given work the optimum binary code by technique of Shennon and Fano is under construction. Performance of this course work fixes our knowledge on discipline «The Theory of the Information».
ВСТУП
Інформатика і обчислювальна техніка - це область науки і техніки, яка включає сукупність засобів, способів і методів людської діяльності, спрямованих на створення і застосування пристроїв зв'язку, систем збору, зберігання і обробки інформації.
У багатьох випадках зберігається і передана інформація може становити інтерес для осіб, які бажають використовувати її в корисливих цілях.
Одним з методів захисту є кодування.
Кодування - це відображення повідомлень кодом за певним правилом присвоєння символів.
Код - це правило, що описує відображення одного набору знаків у інший набір знаків (або слів). Кодом також називають і безліч образів при цьому відображенні.
Оптимальний код - це найбільш ефективний випадок кодування з нульовою надмірністю. При усуненні надмірності істотно знижується кількість символів, необхідних для кодованих повідомлень. Внаслідок цього зменшується час передачі, знижується необхідний обсяг пам'яті.
Таким чином, знання методів обробки інформації є базовим для інженерів, робота яких пов'язана з обчислювальними системами та мережами. Надмірність - додаткові кошти, що вводяться в систему для підвищення її надійності та захищеності.
Таким чином, інформатика займається вивченням обробки і передачі інформації.
У роботі відбивається застосування базових понять інформатики.
ЗМІСТ ЗАВДАННЯ
Для проведення розрахунків розробити програму на мові ПАСКАЛЬ.
1.1. Кількість символів алфавіту k = m (номер варіанта завдання) + 10. Визначити кількість інформації на символ повідомлення, складеного з цього алфавіту:
а) якщо символи алфавіту зустрічаються з рівними ймовірностями;
б) якщо символи алфавіту зустрічаються в повідомленні з ймовірностями:
р 1 = 0,15; p 2 = p 1 / (k -1); p 3 = (p 1 + p 2) / (k -2) ...
k -1
p k = Σ p n / (k - k + 1).
n = 1
Сума всіх ймовірностей повинна бути Равою одиниці, тому:
p i
р i = -----
k
Σ p j
j = 1
Визначити, наскільки недовантажені символи в другому випадку.
1.2. Кількість символів алфавіту = m (номер варіанта завдання). Ймовірності появи символів рівні відповідно
р 1 = 0,15; p 2 = p 1 / (k -1); p 3 = (p 1 + p 2) / (k -2) ...
k -1
p k = Σ p n / (k - k + 1).
n = 1
Тривалості символів τ 1 = 1 сек; τ 2 = 2 сек;
τ k = τ k -1 + 1.
Чому дорівнює швидкість передачі повідомлень, складених з таких символів?
Визначити кількість інформації на символ повідомлення, складеного з цього алфавіту:
а) якщо символи алфавіту зустрічаються з рівними ймовірностями;
Визначити, наскільки недовантажені символи в другому випадку.
1.3. Повідомлення складаються з алфавіту з числом символів = m. Імовірність появи символів алфавіту дорівнює відповідно:
р 1 = 0,15; p 2 = p 1 / (k -1); p 3 = (p 1 + p 2) / (k -2) ...
k -1
p k = Σ p n / (k - k + 1).
n = 1
Знайти надмірність повідомлень, складених з даного алфавіту.
Побудувати оптимальний код повідомлення.
ТЕОРЕТИЧНА ЧАСТИНА
Кількісна оцінка ІНФОРМАЦІЇ
Загальне число неповторюваних повідомлень, яке може бути складено з алфавіту m шляхом комбінування з n символів в повідомленні,
N = m n
Невизначеність, яка припадає на символ первинного (кодованого) алфавіту, складеного з рівноймовірно і взаємонезалежні символів,
H = log 2 m
Так як інформація є невизначеність, знімна при отриманні повідомлення, то кількість інформації може бути представлено як добуток загального числа повідомлень k на середню ентропію H, що припадає на одне повідомлення:
I = k * H біт
Для випадків рівноймовірно і взаємонезалежні символів первинного алфавіту кількість інформації в k повідомленнях алфавіту m одно:
I = k * log 2 m біт
Для неравновероятних алфавітів ентропія на символ алфавіту:
mm
H = Σ p i * log 2 (1 / 2 p i) =- Σp i * log 2 p i біт / символ
i = 1 i = 1
А кількість інформації в повідомленні, складеному з k неравновероятних символів,
m
I =-k * Σ p i * log 2 p i біт
i = 1
ОБЧИСЛЕННЯ ШВИДКОСТІ ПЕРЕДАЧІ ІНФОРМАЦІЇ ТА пропускної спроможності каналів зв'язку
В умовах відсутності перешкод швидкість передачі інформації визначається кількістю інформації, стерпним символом повідомлення в одиницю часу, і дорівнює
C = n * H,
де n - кількість символів, що виробляються джерелом повідомлень за одиницю часу; H - ентропія (невизначеність), знімна при отриманні одного символу повідомлень, вироблюваних даними джерелом.
Швидкість передачі інформації також може бути представлена як
біт / сек,
де тау - час передачі одного двійкового символу.
Для повідомлень, складених з рівноймовірно взаємонезалежні символів рівної тривалості, швидкість передачі інформації:
C = (1 / τ) * log 2 m біт / сек
У разі неравновероятних символів рівної тривалості:
m
C = (1 / τ) * Σp i * log 2 p i біт / сек
i = 1
У разі неравновероятних і взаємонезалежні символів різної тривалості:
Пропускна здатність (або ємність каналу зв'язку) - є максимальна швидкість передачі інформації з даного каналу зв'язку. Під каналом зв'язку мається на увазі сукупність засобів, призначених для передачі інформації від даного джерела повідомлень до адресата. Вираз для пропускної здатності відрізняється тим, що пропускну здатність характеризує максимальна ентропія:
З макс = біт / сек
Для двійкового коду:
З макс біт / сек
При наявності перешкод пропускна здатність каналу зв'язку обчислюється як добуток кількості прийнятих в секунду знаків n на різницю ентропії джерела повідомлень і умовної ентропії джерела повідомлень щодо прийнятого сигналу:
біт / сек (15)
або
біт / сек
У загальному випадку
біт / сек (16)
Якщо символи джерела повідомлень неравновероятни і взаємозалежні, то ентропія джерела обчислюється за формулою загальної умовної ентропії.
Для симетричних бінарних каналів, в яких сигнали передаються за допомогою двох якісних ознак і ймовірність помилкового прийому , А ймовірність правильного прийому , Втрати враховуються за допомогою умовної ентропії виду
біт / сек (17)
пропускна здатність таких каналів
біт / сек (18)
Для симетричного бінарного каналу
біт / сек (19)
Для симетричних дискретних каналів зв'язку з числом якісних ознак m> 2 пропускна здатність
біт / сек (20)
Визначення надлишкового ПОВІДОМЛЕНЬ. ОПТИМАЛЬНИЙ КОДУВАННЯ
Якщо ентропія джерела повідомлень не дорівнює максимальної ентропії для алфавіту з цим кількістю якісних ознак (маються на увазі якісні ознаки алфавіту, за допомогою яких складаються повідомлення), то це, перш за все, означає, що повідомлення даного джерела могли б нести більшу кількість інформації. Абсолютна недовантаження на символ повідомлень такого джерела:
Δ D = (Н макс-Н) біт / символ
Для визначення кількості "зайвої" інформації, яка закладена в структурі алфавіту або в природі коду, вводиться поняття надмірності. Надмірність, з якою ми маємо справу в теорії інформації, не залежить від змісту повідомлення і зазвичай заздалегідь відома зі статистичних даних. Інформаційна надмірність показує відносну недовантаження на символ алфавіту і є безрозмірною величиною:
,
де = Μ - коефіцієнт стиснення (відносна ентропія). Н і Н макс беруться стосовно одного й того ж алфавіту.
Крім загального поняття надмірності існують приватні види надлишковості (надмірність, обумовлена неравновероятним розподілом символів в повідомленні, надмірність, викликана статистичної зв'язком між символами повідомлення).
Надмірність, яка закладена в природі даного коду, виходить в результаті нерівномірного розподілу в повідомленнях якісних ознак цього коду і не може бути задана однією цифрою на підставі статистичних випробувань. Так при передачі десяткових цифр двійковим кодом максимально завантаженими бувають тільки ті символи вторинного алфавіту, які передають значення, що є цілочисельними ступенями двійки. В інших випадках тією ж кількістю символів може бути передано більшу кількість цифр (повідомлень). Наприклад, трьома двійковими розрядами ми можемо передати і цифру 5, і цифру 8. Фактично для передачі повідомлення достатньо мати довжину кодової комбінації.
Фактично для передачі повідомлення достатньо мати довжину кодової комбінації
де N - загальна кількість переданих повідомлень.
L можна представити і як
де і - Відповідно якісні ознаки первинного та вторинного алфавітів. Тому для цифри 5 у двійковому коді можна записати
дв. симв.
Однак цю цифру необхідно округлити до найближчого цілого числа (у велику сторону), так як довжина коду не може бути виражена дробовим числом.
У загальному випадку, надмірність від округлення:
де , K - округлене до найближчого цілого числа значення . Для нашого прикладу
Надмірність необхідна для підвищення завадостійкості кодів і її вводять штучно у вигляді додаткових символів. Якщо в коді всього n розрядів і з них несуть інформаційне навантаження, то характеризують абсолютну коригувальну надмірність, а величина характеризує відносну коригувальну надмірність.
Для зменшення надмірності використовують оптимальні коди. При побудові оптимальних кодів найбільшого поширення набули методики Шеннона-Фано і Хаффмена. Згідно з методикою Шеннона-Фано побудова оптимального коду ансамблю з повідомлень зводиться до наступного:
1) безліч з повідомлень розташовується в порядку убування ймовірностей;
2) початковий ансамбль кодованих сигналів розбивається на дві групи таким чином, щоб сумарні ймовірності повідомлень обох груп були по можливості рівні.
Якщо рівної ймовірності в підгрупах не можна досягти, то їх ділять так, щоб у верхній частині (верхній підгрупі) залишалися символи, сумарна ймовірність яких менше сумарної ймовірності символів у нижній частині (нижній підгрупі);
3) першої групи присвоюється символ 0, а другій групі - символ 1;
4) кожну з утворених підгруп ділять на дві частини таким чином, щоб сумарні ймовірності новостворених підгруп були по можливості рівні;
5) першим групам кожної з підгруп знову присвоюється 0, а другим - 1. Таким чином, ми отримуємо друга цифри коду. Потім кожна з чотирьох груп знову ділиться на рівні (з точки зору сумарної ймовірності) частині до тих пір, поки в кожній з підгруп не залишиться по одній букві.
Побудований код називають оптимальним нерівномірним кодом (ОНК).
ПРАКТИЧНА ЧАСТИНА
a) Розрахунки
розраховується початкові ймовірності для неравновероятних символів алфавіту.
виконує нормування зазначених ймовірностей.
розраховується ентропія алфавіту з рівноймовірно символів.
проводиться розрахунок ентропії алфавіту з неравновероятнимі символами і недовантаження в цьому випадку.
з урахуванням заданих тривалостей символів обчислюється швидкість передачі і надмірність.
будується оптимальний код за методом Шеннона-Фано.
Розрахунок ймовірностей.
Проміжні значення: k -1 ... P k = S p n / (m - k + 1). n -1 | Остаточний результат: р i = P i / ( p i) |
p 1 = 0,1500 p 2 = 0,0065 p 3 = 0,0071 p 4 = 0,0078 p 5 = 0,0086 p 6 = 0,0095 p 7 = 0,0105 p 8 = 0,0118 p 9 = 0,0132 p 10 = 0,0150 p 11 = 0,0171 p 12 = 0,0198 p 13 = 0,0231 p 14 = 0,0273 p 15 = 0,0327 p 16 = 0,0400 p 17 = 0,0500 p 18 = 0,0643 p 19 = 0,0857 p 20 = 0,1200 p 21 = 0, 1 серпня 2000 p 22 = 0, 3000 p 23 = 0, 60 00 p 24 = 1, 80 00 р i = 3, 6 | p 1 = 0,0417 p 2 = 0,0018 p 3 = 0,0020 |
p 4 = 0,0022
p 5 = 0,0024
p 6 = 0,0026
p 7 = 0,0029
p 8 = 0,0033
p 9 = 0,0037
p 10 = 0,0042
p 11 = 0,0048
p 12 = 0,0055
p 13 = 0,0064
p 14 = 0,0076
p 15 = 0,0091
p 16 = 0,0111
p 17 = 0,0139
p 18 = 0,0179
p 19 = 0,0238
p 20 = 0,0333
p 21 = 0,0 500
p 22 = 0,0 833
p 23 = 0, 1667
p 24 = 0, 5000
р i = 1