ЗМІСТ
Зміст
Анотація
Введення
Зміст завдання
Теоретична частина
Практична частина
а) розрахунки
б) програма
Висновок
а) результати роботи програми
б) блок-схема
Література
АНОТАЦІЯ
У цій роботі по даному числу символів в алфавіті розраховуються їх ймовірності, кількість інформації, якщо символи зустрічаються з рівними ймовірностями і з різними ймовірностями, недовантаження символів, швидкість передачі повідомлень і надмірність повідомлень. Крім того, в даній роботі будується оптимальний двійковий код за методикою Шеннона - Фано. Виконання цієї курсової роботи закріплює наші знання з дисципліни «Теорія інформації».
До роботи додається програма, написана мовою програмування високого рівня (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/2p 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 на різницю ентропії джерела повідомлень і умовної ентропії джерела повідомлень щодо прийнятого сигналу:
або
У загальному випадку
Якщо символи джерела повідомлень неравновероятни і взаємозалежні, то ентропія джерела обчислюється за формулою загальної умовної ентропії.
Для симетричних бінарних каналів, в яких сигнали передаються за допомогою двох якісних ознак і ймовірність помилкового прийому
пропускна здатність таких каналів
Для симетричного бінарного каналу
Для симетричних дискретних каналів зв'язку з числом якісних ознак m> 2 пропускна здатність
Визначення надлишкового ПОВІДОМЛЕНЬ. ОПТИМАЛЬНИЙ КОДУВАННЯ
Якщо ентропія джерела повідомлень не дорівнює максимальної ентропії для алфавіту з цим кількістю якісних ознак (маються на увазі якісні ознаки алфавіту, за допомогою яких складаються повідомлення), то це, перш за все, означає, що повідомлення даного джерела могли б нести більшу кількість інформації. Абсолютна недовантаження на символ повідомлень такого джерела:
ΔD = (Н макс-Н) біт / символ
Для визначення кількості "зайвої" інформації, яка закладена в структурі алфавіту або в природі коду, вводиться поняття надмірності. Надмірність, з якою ми маємо справу в теорії інформації, не залежить від змісту повідомлення і зазвичай заздалегідь відома зі статистичних даних. Інформаційна надмірність показує відносну недовантаження на символ алфавіту і є безрозмірною величиною:
де
Крім загального поняття надмірності існують приватні види надлишковості (надмірність, обумовлена неравновероятним розподілом символів в повідомленні, надмірність, викликана статистичної зв'язком між символами повідомлення).
Надмірність, яка закладена в природі даного коду, виходить в результаті нерівномірного розподілу в повідомленнях якісних ознак цього коду і не може бути задана однією цифрою на підставі статистичних випробувань. Так при передачі десяткових цифр двійковим кодом максимально завантаженими бувають тільки ті символи вторинного алфавіту, які передають значення, що є цілочисельними ступенями двійки. В інших випадках тією ж кількістю символів може бути передано більшу кількість цифр (повідомлень). Наприклад, трьома двійковими розрядами ми можемо передати і цифру 5, і цифру 8. Фактично для передачі повідомлення достатньо мати довжину кодової комбінації.
Фактично для передачі повідомлення достатньо мати довжину кодової комбінації
де N - загальна кількість переданих повідомлень.
L можна представити і як
де
Однак цю цифру необхідно округлити до найближчого цілого числа (у велику сторону), так як довжина коду не може бути виражена дробовим числом.
У загальному випадку, надмірність від округлення:
де
Надмірність необхідна для підвищення завадостійкості кодів і її вводять штучно у вигляді додаткових
Для зменшення надмірності використовують оптимальні коди. При побудові оптимальних кодів найбільшого поширення набули методики Шеннона-Фано і Хаффмена. Згідно з методикою Шеннона-Фано побудова оптимального коду ансамблю з повідомлень зводиться до наступного:
1) безліч з повідомлень розташовується в порядку убування ймовірностей;
2) початковий ансамбль кодованих сигналів розбивається на дві групи таким чином, щоб сумарні ймовірності повідомлень обох груп були по можливості рівні.
Якщо рівної ймовірності в підгрупах не можна досягти, то їх ділять так, щоб у верхній частині (верхній підгрупі) залишалися символи, сумарна ймовірність яких менше сумарної ймовірності символів у нижній частині (нижній підгрупі);
3) першої групи присвоюється символ 0, а другій групі - символ 1;
4) кожну з утворених підгруп ділять на дві частини таким чином, щоб сумарні ймовірності новостворених підгруп були по можливості рівні;
5) першим групам кожної з підгруп знову присвоюється 0, а другим - 1. Таким чином, ми отримуємо друга цифри коду. Потім кожна з чотирьох груп знову ділиться на рівні (з точки зору сумарної ймовірності) частині до тих пір, поки в кожній з підгруп не залишиться по одній букві.
Побудований код називають оптимальним нерівномірним кодом (ОНК).
ПРАКТИЧНА ЧАСТИНА
a) Розрахунки
1) розраховується початкові ймовірності для неравновероятних символів алфавіту.
2) виконує нормування зазначених ймовірностей.
3) розраховується ентропія алфавіту з рівноймовірно символів.
4) проводиться розрахунок ентропії алфавіту з неравновероятнимі символами і недовантаження в цьому випадку.
5) з урахуванням заданих тривалостей символів обчислюється швидкість передачі і надмірність.
6) будується оптимальний код за методом Шеннона-Фано.
Розрахунок ймовірностей.
Визначення кількості інформації на символ повідомлення, складеного з даного алфавіту.
Кількість інформації на символ повідомлення для символів даного алфавіту, що зустрічаються з рівними ймовірностями:
H max = log 24 лютого = ln 24/ln 2 = 4,5850 біт / символ
Кількість інформації на символ повідомлення для символів даного алфавіту, що зустрічаються в сполученні з різними ймовірностями:
H = - (0,0417 * log 2 0,0417 + 0,0018 * log 2 0,0018 + 0,020 * log 2 0,0020 + 0,0022 * log 2 0,0022 + 0,0024 * log 2 0, 0024 + 0,0026 * log 2 0,0026 + 0,0029 * log 2 0,0029 + 0,0033 * log два 0,0033 + 0,0037 * log 2 0,0037 + 0,0042 * log 2 0, 0042 + 0,0048 * log 2 0,0048 + 0,0055 * log 2 0,0055 + 0,0064 * log два 0,0064 + 0,0076 * log 2 0,0076 + 0,0091 * log 2 0, 0091 + 0,0111 * log 2 0,0111 + 0,0139 * log 2 0,0139 + 0,0179 * log два 0,0179 + 0,0238 * log 2 0,0238 + 0,0333 * log 2 0, 0333 + 0,0500 * log 2 0,0500 + 0,0833 * log 2 0,0833 + 0,1667 * log два 0,1667 + 0,5000 * log 2 0,5000) =
= 2,6409 біт / символ
Недовантаження символів в даному випадку:
N = Н max - Н = 4,5850 - 2,6409 = 1,9441 біт / символ
Обчислення швидкості передачі інформації.
С = - (0,0417 * log 2 0,0417 + 0,0018 * log дві 0,0018 + 0,020 * log два 0,0020 + 0,0022 * log два 0,0022 + 0,0024 * log 2 0, 0024 + 0,0026 * log 2 0,0026 + 0,0029 * log 2 0,0029 + 0,0033 * log два 0,0033 + 0,0037 * log 2 0,0037 + 0,0042 * log 2 0, 0042 + 0,0048 * log 2 0,0048 + 0,0055 * log 2 0,0055 + 0,0064 * log два 0,0064 + 0,0076 * log 2 0,0076 + 0,0091 * log 2 0, 0091 + 0,0111 * log 2 0,0111 + 0,0139 * log 2 0,0139 + 0,0179 * log два 0,0179 + 0,0238 * log 2 0,0238 + 0,0333 * log 2 0, 0333 + 0,0500 * log 2 0,0500 + 0,0833 * log 2 0,0833 + 0,1667 * log два 0,1667 + 0,5000 * log 2 0,5000) /
(1 * 0,0417 + 2 * 0,0018 + 3 * 0,020 + 4 * 0,0022 + 5 * 0,0024 + 6 * 0,0026 + 7 * 0,0029 + 8 * 0,0033 + 9 * 0 , 0037 + 10 * 0,0042 + 11 * 0,0048 + 12 * 0,0055 + 13 * 0,0064 + 14 * 0,0076 + 15 * 0,0091 + 16 * 0,0111 + 17 * 0,0139 + 18 * 0,0179 + 19 * 0,0238 + 20 * 0,0333 + 21 * 0,0500 + 22 * 0,0833 + 23 * 0,1667 + 24 * 0,5000) = 0,1244 біт / сек
Надмірність повідомлень, складених з даного алфавіту.
D = 1 - (Н / Н max) = 1 - (2,6409 / 4,5850) = 0,4240
Зміст
Анотація
Введення
Зміст завдання
Теоретична частина
Практична частина
а) розрахунки
б) програма
Висновок
а) результати роботи програми
б) блок-схема
Література
АНОТАЦІЯ
У цій роботі по даному числу символів в алфавіті розраховуються їх ймовірності, кількість інформації, якщо символи зустрічаються з рівними ймовірностями і з різними ймовірностями, недовантаження символів, швидкість передачі повідомлень і надмірність повідомлень. Крім того, в даній роботі будується оптимальний двійковий код за методикою Шеннона - Фано. Виконання цієї курсової роботи закріплює наші знання з дисципліни «Теорія інформації».
До роботи додається програма, написана мовою програмування високого рівня (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/2p 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 на різницю ентропії джерела повідомлень і умовної ентропії джерела повідомлень щодо прийнятого сигналу:
або
У загальному випадку
Якщо символи джерела повідомлень неравновероятни і взаємозалежні, то ентропія джерела обчислюється за формулою загальної умовної ентропії.
Для симетричних бінарних каналів, в яких сигнали передаються за допомогою двох якісних ознак і ймовірність помилкового прийому
пропускна здатність таких каналів
Для симетричного бінарного каналу
Для симетричних дискретних каналів зв'язку з числом якісних ознак m> 2 пропускна здатність
Визначення надлишкового ПОВІДОМЛЕНЬ. ОПТИМАЛЬНИЙ КОДУВАННЯ
Якщо ентропія джерела повідомлень не дорівнює максимальної ентропії для алфавіту з цим кількістю якісних ознак (маються на увазі якісні ознаки алфавіту, за допомогою яких складаються повідомлення), то це, перш за все, означає, що повідомлення даного джерела могли б нести більшу кількість інформації. Абсолютна недовантаження на символ повідомлень такого джерела:
ΔD = (Н макс-Н) біт / символ
Для визначення кількості "зайвої" інформації, яка закладена в структурі алфавіту або в природі коду, вводиться поняття надмірності. Надмірність, з якою ми маємо справу в теорії інформації, не залежить від змісту повідомлення і зазвичай заздалегідь відома зі статистичних даних. Інформаційна надмірність показує відносну недовантаження на символ алфавіту і є безрозмірною величиною:
де
Крім загального поняття надмірності існують приватні види надлишковості (надмірність, обумовлена неравновероятним розподілом символів в повідомленні, надмірність, викликана статистичної зв'язком між символами повідомлення).
Надмірність, яка закладена в природі даного коду, виходить в результаті нерівномірного розподілу в повідомленнях якісних ознак цього коду і не може бути задана однією цифрою на підставі статистичних випробувань. Так при передачі десяткових цифр двійковим кодом максимально завантаженими бувають тільки ті символи вторинного алфавіту, які передають значення, що є цілочисельними ступенями двійки. В інших випадках тією ж кількістю символів може бути передано більшу кількість цифр (повідомлень). Наприклад, трьома двійковими розрядами ми можемо передати і цифру 5, і цифру 8. Фактично для передачі повідомлення достатньо мати довжину кодової комбінації.
Фактично для передачі повідомлення достатньо мати довжину кодової комбінації
де N - загальна кількість переданих повідомлень.
L можна представити і як
де
Однак цю цифру необхідно округлити до найближчого цілого числа (у велику сторону), так як довжина коду не може бути виражена дробовим числом.
У загальному випадку, надмірність від округлення:
де
Надмірність необхідна для підвищення завадостійкості кодів і її вводять штучно у вигляді додаткових
Для зменшення надмірності використовують оптимальні коди. При побудові оптимальних кодів найбільшого поширення набули методики Шеннона-Фано і Хаффмена. Згідно з методикою Шеннона-Фано побудова оптимального коду ансамблю з повідомлень зводиться до наступного:
1) безліч з повідомлень розташовується в порядку убування ймовірностей;
2) початковий ансамбль кодованих сигналів розбивається на дві групи таким чином, щоб сумарні ймовірності повідомлень обох груп були по можливості рівні.
Якщо рівної ймовірності в підгрупах не можна досягти, то їх ділять так, щоб у верхній частині (верхній підгрупі) залишалися символи, сумарна ймовірність яких менше сумарної ймовірності символів у нижній частині (нижній підгрупі);
3) першої групи присвоюється символ 0, а другій групі - символ 1;
4) кожну з утворених підгруп ділять на дві частини таким чином, щоб сумарні ймовірності новостворених підгруп були по можливості рівні;
5) першим групам кожної з підгруп знову присвоюється 0, а другим - 1. Таким чином, ми отримуємо друга цифри коду. Потім кожна з чотирьох груп знову ділиться на рівні (з точки зору сумарної ймовірності) частині до тих пір, поки в кожній з підгруп не залишиться по одній букві.
Побудований код називають оптимальним нерівномірним кодом (ОНК).
ПРАКТИЧНА ЧАСТИНА
a) Розрахунки
1) розраховується початкові ймовірності для неравновероятних символів алфавіту.
2) виконує нормування зазначених ймовірностей.
3) розраховується ентропія алфавіту з рівноймовірно символів.
4) проводиться розрахунок ентропії алфавіту з неравновероятнимі символами і недовантаження в цьому випадку.
5) з урахуванням заданих тривалостей символів обчислюється швидкість передачі і надмірність.
6) будується оптимальний код за методом Шеннона-Фано.
Розрахунок ймовірностей.
| Проміжні значення: k-1 ... P k = S p n / (m - k + 1). n-1 | Остаточний результат: р 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,1800 p 22 = 0,3000 p 23 = 0,6000 p 24 = 1,8000 | 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,0500 p 22 = 0,0833 p 23 = 0,1667 p 24 = 0,5000 |
Кількість інформації на символ повідомлення для символів даного алфавіту, що зустрічаються з рівними ймовірностями:
H max = log 24 лютого = ln 24/ln 2 = 4,5850 біт / символ
Кількість інформації на символ повідомлення для символів даного алфавіту, що зустрічаються в сполученні з різними ймовірностями:
H = - (0,0417 * log 2 0,0417 + 0,0018 * log 2 0,0018 + 0,020 * log 2 0,0020 + 0,0022 * log 2 0,0022 + 0,0024 * log 2 0, 0024 + 0,0026 * log 2 0,0026 + 0,0029 * log 2 0,0029 + 0,0033 * log два 0,0033 + 0,0037 * log 2 0,0037 + 0,0042 * log 2 0, 0042 + 0,0048 * log 2 0,0048 + 0,0055 * log 2 0,0055 + 0,0064 * log два 0,0064 + 0,0076 * log 2 0,0076 + 0,0091 * log 2 0, 0091 + 0,0111 * log 2 0,0111 + 0,0139 * log 2 0,0139 + 0,0179 * log два 0,0179 + 0,0238 * log 2 0,0238 + 0,0333 * log 2 0, 0333 + 0,0500 * log 2 0,0500 + 0,0833 * log 2 0,0833 + 0,1667 * log два 0,1667 + 0,5000 * log 2 0,5000) =
= 2,6409 біт / символ
Недовантаження символів в даному випадку:
N = Н max - Н = 4,5850 - 2,6409 = 1,9441 біт / символ
Обчислення швидкості передачі інформації.
С = - (0,0417 * log 2 0,0417 + 0,0018 * log дві 0,0018 + 0,020 * log два 0,0020 + 0,0022 * log два 0,0022 + 0,0024 * log 2 0, 0024 + 0,0026 * log 2 0,0026 + 0,0029 * log 2 0,0029 + 0,0033 * log два 0,0033 + 0,0037 * log 2 0,0037 + 0,0042 * log 2 0, 0042 + 0,0048 * log 2 0,0048 + 0,0055 * log 2 0,0055 + 0,0064 * log два 0,0064 + 0,0076 * log 2 0,0076 + 0,0091 * log 2 0, 0091 + 0,0111 * log 2 0,0111 + 0,0139 * log 2 0,0139 + 0,0179 * log два 0,0179 + 0,0238 * log 2 0,0238 + 0,0333 * log 2 0, 0333 + 0,0500 * log 2 0,0500 + 0,0833 * log 2 0,0833 + 0,1667 * log два 0,1667 + 0,5000 * log 2 0,5000) /
(1 * 0,0417 + 2 * 0,0018 + 3 * 0,020 + 4 * 0,0022 + 5 * 0,0024 + 6 * 0,0026 + 7 * 0,0029 + 8 * 0,0033 + 9 * 0 , 0037 + 10 * 0,0042 + 11 * 0,0048 + 12 * 0,0055 + 13 * 0,0064 + 14 * 0,0076 + 15 * 0,0091 + 16 * 0,0111 + 17 * 0,0139 + 18 * 0,0179 + 19 * 0,0238 + 20 * 0,0333 + 21 * 0,0500 + 22 * 0,0833 + 23 * 0,1667 + 24 * 0,5000) = 0,1244 біт / сек
Надмірність повідомлень, складених з даного алфавіту.
D = 1 - (Н / Н max) = 1 - (2,6409 / 4,5850) = 0,4240
Побудова оптимального коду
| 1 | p24 = 0,5000 | 0,5 | 0 | 0 | ||||||||||||||||
| 2 | p23 = 0,1667 | 0,5 | 1 | 0,25 | 1 | 0,1666 | 1 | 111 | ||||||||||||
| 3 | p22 = 0,0833 | 1 | 1 | 0,0833 | 0 | 110 | ||||||||||||||
| 4 | p21 = 0,0500 | 1 | 0,25 | 0 | 0 | 0,05 | 1 0 | 1000 | ||||||||||||
| 5 | p1 = 0,0417 | 1 | 0 | 0 | 0,0690 | 1 | 0,0357 | 1 | 10011 | |||||||||||
| 6 | p20 = 0,0333 | 1 | 0 | 0,1190 | 0 | 1 | 0,0333 | 0 | 10010 | |||||||||||
| 7 | p19 = 0,0238 | 1 | 0 | 1 | 1 | 0,0428 | 1 | 0,0178 | 1 | 101111 | ||||||||||
| 8 | p18 = 0,0179 | 1 | 0 | 1 | 1 | 1 | 0,025 | 0 | 0,0138 | 0 | 1011100 | |||||||||
| 9 | p17 = 0,0139 | 1 | 0 | 1 | 1 | 0 | 0,025 | 1 | 101101 | |||||||||||
| 10 | p16 = 0,0111 | 1 | 0 | 1 | 0,0666 | 1 | 1 | 0 | 101110 | |||||||||||
| 11 | p15 = 0,0091 | 1 | 0 | 1 | 0,0642 | 0 | 0 | 1 | 0,0090 | 1 | 1010011 | |||||||||
| 12 | p14 = 0,0076 | 1 | 0 | 1 | 0 | 0 | 1 | 0,0102 | 0 | 0,0054 | 0 | 10100100 | ||||||||
| 13 | p13 = 0,0064 | 1 | 0 | 1 | 0 | 0 | 0,0166 | 0 | 0,0064 | 1 | 1010001 | |||||||||
| 14 | p12 = 0,0055 | 1 | 0 | 1 | 0 | 0 | 0,0166 | 1 | 0,0064 | 1 | 1010011 | |||||||||
| 15 | p11 = 0,0048 | 1 | 0 | 1 | 0 | 0,0333 | 1 | 1 | 1 | 0,0047 | 1 | 10101111 | ||||||||
| 16 | p10 = 0,0042 | 1 | 0 | 1 | 0 | 1 | 1 | 0,0088 | 1 | 0 | 0,0032 | 0 | 101011100 | |||||||
| 17 | p9 = 0,0037 | 1 | 0 | 1 | 0 | 1 | 1 | 0,0078 | 0 | 0,0036 | 1 | 10101101 | ||||||||
| 18 | p8 = 0,0033 | 1 | 0 | 1 | 0 | 1 | 1 | 0,0078 | 1 | 0,0036 | 0 | 10101110 | ||||||||
| 19 | p7 = 0,0029 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 10101010 | ||||||||||
| 20 | p6 = 0,0026 | 1 | 0 | 1 | 0 | 1 | 0,0167 | 0 | 1 | 0,0026 | 1 | 0,0026 | 1 | 101010111 | ||||||
| 21 | p5 = 0,0024 | 1 | 0 | 1 | 0 | 1 | 0,0147 | 0 | 1 | 1 | 0,0024 | 0 | 101010110 | |||||||
| 22 | p4 = 0,0022 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0,0022 | 0 | 10101000 | |||||||||
| 23 | p3 = 0,0020 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0,0038 | 1 | 0,0020 | 1 | 101010011 | |||||||
| 24 | p2 = 0,0018 | 1 | 0 | 1 | 0 | 1 | 0 | 0,0083 | 0 | 1 | 0,0018 | 0 | 101010010 |
| Буква | Імовірність появи букви | Кодові слова | Кількість символів в кодовому слові | P i · l i |
| A [1] (p24) | 0,5000 | 0 | 1 | 0,5 |
| A [2] (p23) | 0,1667 | 111 | 3 | 0,50001 |
| A [3] (p22) | 0,0833 | 110 | 3 | 0,2500 |
| A [4] (p21) | 0,0500 | 1000 | 4 | 0,2000 |
| A [5] (p 1) | 0,0417 | 10011 | 5 | 0,2083 |
| A [6] (p20) | 0,0333 | 10010 | 5 | 0,1667 |
| A [7] (p19) | 0,0238 | 101111 | 6 | 0,1429 |
| A [8] (p18) | 0,0179 | 1011100 | 7 | 0,1250 |
| A [9] (p17) | 0,0139 | 101101 | 6 | 0,0833 |
| A [10] (p16) | 0,0111 | 101110 | 6 | 0,0667 |
| A [11] (p15) | 0,0091 | 1010011 | 7 | 0,0636 |
| A [12] (p14) | 0,0076 | 10100100 | 8 | 0,0606 |
| A [13] (p13) | 0,0064 | 1010001 | 7 | 0,0449 |
| A [14] (p12) | 0,0055 | 1010011 | 7 | 0,0385 |
| A [15] (p11) | 0,0048 | 10101111 | 8 | 0,0381 |
| A [16] (p10) | 0,0042 | 101011100 | 9 | 0,0375 |
| A [17] (p9) | 0,0037 | 10101101 | 8 | 0,0294 |
| A [18] (p8) | 0,0033 | 10101110 | 8 | 0,0261 |
| A [19] (p7) | 0,0029 | 10101010 | 8 | 0,0234 |
| A [20] (p6) | 0,0026 | 101010111 | 9 | 0,0237 |
| A [21] (p5) | 0,0024 | 101010110 | 9 | 0,0214 |
| A [22] (p4) | 0,0022 | 10101000 | 8 | 0,0173 |
| A [23] (p3) | 0,0020 | 101010011 | 9 | 0,0178 |
| A [24] (p2) | 0,0018 | 101010010 | 9 | 0,0163 |
Визначення кількості інформації на символ повідомлення. Побудова оптимального коду.
З початок безліч з повідомлень розташуємо в порядку убування ймовірностей. Потім, розіб'ємо дане безліч на дві групи таким чином, щоб сумарні ймовірності повідомлень обох груп були по можливості рівні. Але оскільки рівність не досягається, то ми їх ділимо так, щоб у верхній частині залишалися символи, сумарна ймовірність яких менше сумарної ймовірності символів у нижній частині. Першій групі присвоюємо символ 0, а другої групи = символ 1. кожну з утворених підгруп ділимо на дві частини таким чином, щоб сумарні ймовірності новостворених підгруп були по можливості рівні. Першим групам кожної з підгруп знову присвоюємо 0, а другим 1. таким образам ми отримуємо ми отримуємо друга цифри коду. Потім кожну з чотирьох груп знову ділимо на рівні частини до тих пір, поки в кожній з підгруп не залишиться по одній букві.
Оптимальний код (вийшов результат):
Буква | Імовірність появи букви | Кодове слово | Кількість символів в кодовому слові | p i ∙ l i |
| P1 | 0,055 | 000 | 3 | 0,165 |
| P2 | 0,053 | 0010 | 4 | 0,212 |
| P3 | 0,051 | 00110 | 5 | 0,255 |
| P4 | 0,050 | 00111 | 5 | 0,250 |
| P5 | 0,048 | 0100 | 4 | 0,192 |
| P6 | 0,046 | 0101 | 4 | 0,176 |
| P7 | 0,044 | 0110 | 4 | 0,114 |
| P8 | 0,043 | 01110 | 5 | 0,215 |
| P9 | 0,041 | 011110 | 6 | 0,246 |
| P10 | 0,040 | 011111 | 6 | 0,240 |
| P11 | 0,039 | 1000 | 4 | 0,156 |
| P12 | 0,038 | 10010 | 5 | 0,190 |
| P13 | 0,036 | 10011 | 5 | 0,180 |
| P14 | 0,035 | 1010 | 4 | 0,140 |
| P15 | 0,033 | 10110 | 5 | 0,165 |
| P16 | 0,032 | 101110 | 6 | 0,192 |
| P17 | 0,030 | 101111 | 6 | 0,180 |
| P18 | 0,029 | 11000 | 5 | 0,145 |
| P19 | 0,027 | 11001 | 5 | 0,135 |
| P20 | 0,026 | 11010 | 5 | 0,130 |
| P21 | 0,025 | 110110 | 6 | 0,150 |
| P22 | 0,023 | 110111 | 6 | 0,138 |
| P23 | 0,022 | 11100 | 5 | 0,110 |
| P24 | 0,020 | 111010 | 6 | 0,120 |
| P25 | 0,019 | 111011 | 6 | 0,114 |
| P26 | 0,018 | 111100 | 6 | 0,108 |
| P27 | 0,017 | 111101 | 6 | 0,102 |
| P28 | 0,016 | 111110 | 6 | 0,096 |
| P29 | 0,013 | 1111110 | 7 | 0,091 |
| P30 | 0,012 | 11111110 | 8 | 0,096 |
| P31 | 0,010 | 11111111 | 8 | 0,080 |
| P1 | 0,010 | 11111111 | 0,520 | 0,277 | 0,147 | 0,086 | 0,051 | 0,035 | 0,022 | 0,010 |
| P2 | 0,012 | 11111110 | 0,012 | |||||||
| P3 | 0,013 | 1111110 | 0,013 | |||||||
| P4 | 0,016 | 111110 | 0,016 | |||||||
| P5 | 0,017 | 111101 | 0,035 | 0,017 | ||||||
| P6 | 0,018 | 111100 | 0,018 | |||||||
| P7 | 0,019 | 111011 | 0,061 | 0,039 | 0,019 | |||||
| P8 | 0,020 | 111010 | 0,020 | |||||||
| P9 | 0,022 | 11100 | 0,022 | |||||||
| P10 | 0,023 | 110111 | 0,130 | 0,074 | 0,048 | 0,023 | ||||
| P11 | 0,025 | 110110 | 0,025 | |||||||
| P12 | 0,026 | 11010 | 0,026 | |||||||
| P13 | 0,027 | 11001 | 0,056 | 0,027 | ||||||
| P14 | 0,029 | 11000 | 0,029 | |||||||
| P15 | 0,030 | 101111 | 0,243 | 0,130 | 0,095 | 0,062 | 0,030 | |||
| P16 | 0,032 | 101110 | 0,032 | |||||||
| P17 | 0,033 | 10110 | 0,033 | |||||||
| P18 | 0,035 | 1010 | 0,035 | |||||||
| P19 | 0,036 | 10011 | 0,113 | 0,074 | 0,036 | |||||
| P20 | 0,038 | 10010 | 0,038 | |||||||
| P21 | 0,039 | 1000 | 0,039 | |||||||
| P22 | 0,040 | 011111 | 0,471 | 0,262 | 0,168 | 0,124 | 0,081 | 0,040 | ||
| P23 | 0,041 | 011110 | 0,041 | |||||||
| P24 | 0,043 | 01110 | 0,043 | |||||||
| P25 | 0,044 | 0110 | 0,044 | |||||||
| P26 | 0,046 | 0101 | 0,094 | 0,046 | ||||||
| P27 | 0,048 | 0100 | 0,048 | |||||||
| P28 | 0,050 | 00111 | 0,209 | 0,154 | 0,101 | 0,050 | ||||
| P29 | 0,051 | 00110 | 0,051 | |||||||
| P30 | 0,053 | 0010 | 0,053 | |||||||
| P31 | 0,055 | 000 | 0,055 |
ТЕКСТ ПРОГРАМИ:
uses Crt, Graph;
const k = 24;
type
mass = array [1 .. k] of real;
var
i, x: integer;
s, H, Hmax, deltaD, sum, C, sumTiPi, D: real;
p, a: mass;
code: array [1 .. k] of string [20];
{Процедура побудови оптимального коду за методикою Шеннона-Фано}
procedure shannona (b: mass);
procedure divide (var nS: integer; n1, n2: integer);
var
s, s1, s2: real;
begin
s: = 0;
for i: = n1 to n2 do s: = s + a [i];
s1: = 0; s2: = 0;
i: = n1-1;
repeat
inc (i);
s1: = s1 + a [i];
s2: = s1 + a [i +1];
until abs (s/2-s1) <abs (s/2-s2);
nS: = i;
for x: = n1 to nS do
if (s/2-s1)> = 0 then code [x]: = code [x] + "0"
else code [x]: = code [x] + 1 ";
for x: = nS +1 to n2 do
if (s/2-s1) <0 then code [x]: = code [x] + "0"
else code [x]: = code [x] + 1 ";
end;
var
tmp: real;
j, n1, n2, nS: integer;
begin
for i: = 1 to k do code [i ]:='';
for i: = 1 to k do a [i]: = b [i];
for i: = 1 to k do
for j: = k downto (i +1) do
if a [i] <a [j]
then
begin
tmp: = a [i];
a [i]: = a [j];
a [j]: = tmp;
end;
j: = 1;
repeat
divide (nS, j, k);
n1: = nS;
while (nS-j)> 0 do divide (nS, j, nS);
j: = nS +1;
n2: = n1;
while (n1-j)> 0 do divide (n1, j, n1);
j: = n2 +1;
until j> (k-1);
end;
procedure zastavka;
var dr, reg, err: integer;
begin
dr: = detect; reg: = detect;
initgraph (dr, reg, 'd: \ tp7 \ tpu \');
err: = graphresult;
if err <> grok then
begin
writeln ('Помилка ініціалізації графічного модуля!');
halt;
end;
setcolor (19);
settextstyle (3,0,4);
outtextxy (150,40, 'Розрахунково-графічна робота');
outtextxy (240,65, 'на тему');
setcolor (14);
settextstyle (4,0,4);
outtextxy (50,125,'''Побудова оптимального коду методом Шеннона-Фано''');
settextstyle (6,0,2);
setcolor (19);
outtextxy (325,250, 'Виконав:');
settextstyle (6,0,2);
setcolor (10);
outtextxy (400,250, 'Калінін С. А. ПС -11');
outtextxy (200,450, 'Натисніть будь-яку клавішу');
readln;
closegraph;
end;
procedure vivod;
begin
textcolor (lightgreen);
writeln ('Оптимальний код:'); {висновок кінцевої таблиці}
writeln ('Символ': 7, 'Імовірність': 13, 'Оптимальний код': 20, 'Кількість зн.': 15, 'Ймовірно .* Чісл.зн.': 20);
for i: = 1 to k do
begin
write ('p [', i: 2, ']');
write (p [i]: 0:4, '');
write (code [i]: 20, '');
write (length (code [i]): 15, '');
write ((p [i] * length (code [i])): 0:4);
if i <> k then writeln;
end;
end;
begin
zastavka;
clrscr;
{1.1 а) Кількість інформації на символ повідомлення,
складеного з алфавіту рівноймовірно символів}
Hmax: = ln (k) / ln (2);
{1.1 б) Розрахунок ймовірностей для неравновероятних символів}
p [1]: = 0.15;
sum: = p [1];
for i: = 2 to k do
begin
p [i]: = sum / (k +1- i);
sum: = sum + p [i];
end;
clrscr;
textcolor (11);
writeln ('Проміжні значення ймовірностей:');
writeln;
textcolor (10);
for i: = 1 to 14 do
writeln ('Імовірність p [', i: 2, '] =', p [i]: 4:4);
readkey;
clrscr;
textcolor (11);
writeln ('Проміжні значення ймовірностей:');
writeln;
textcolor (10);
for i: = 15 to k do
writeln ('Імовірність p [', i: 2, '] =', p [i]: 4:4);
writeln;
textcolor (11);
for i: = 1 to k do s: = s + p [i];
writeln ('Сума ймовірностей =', s: 4:2);
readkey;
H: = 0;
sumTiPi: = 0;
for i: = 1 to k do
begin
p [i]: = p [i] / sum;
{1.1 б) Розрахунок ентропії для алфавіту неравновероятних символів}
H: = H + p [i] * (ln (1 / p [i]) / ln (2));
sumTiPi: = sumTiPi + i * p [i];
end;
clrscr;
textcolor (11);
writeln ('Остаточні значення:');
writeln;
textcolor (10);
for i: = 1 to 14 do
writeln ('Імовірність p [', i: 2, '] =', p [i]: 4:4);
readkey;
clrscr;
textcolor (11);
writeln ('Остаточні значення:');
writeln;
textcolor (10);
for i: = 15 to k do
writeln ('Імовірність p [', i: 2, '] =', p [i]: 4:4);
writeln;
textcolor (11);
s: = 0;
for i: = 1 to k do s: = s + p [i];
writeln ('Сума ймовірностей =', s: 4:2);
readkey;
{1.1 б) Визначення недовантаження символів}
deltaD: = Hmax-H;
{1.2 Розрахунок швидкості передачі повідомлення}
C: = H / SumTiPi;
{1.3 Розрахунок надмірності повідомлення}
D: = 1-H/Hmax;
{Виклик процедури побудови оптимального коду}
shannona (p);
{Виведення результатів}
clrscr;
textcolor (11);
{Writceln ('Кількість символів алфавіту =', k ,'.');}
writeln ('1 .1 Кількість інформації на символ повідомлення: ');
writeln ('a) для алфавіту рівноймовірно таблиця:');
textcolor (10); writeln ('Hmax =', Hmax: 7:4, 'біт / символ');
textcolor (11); writeln ('b) для алфавіту неравновероятних таблиця:');
textcolor (10); writeln ('H =', H: 7:4, 'біт / символ');
textcolor (11); write ('Недовантаження:');
textcolor (10); writeln ('дельтаD =', deltaD: 7:4, 'біт / символ');
textcolor (11); writeln;
Writeln ('1 .2 Швидкість передачі інформації: ');
textcolor (10); writeln ('C =', C: 7:4, 'біт / сек');
textcolor (11); writeln;
Writeln ('1 .3 Надмірність повідомлень: ');
textcolor (10); writeln ('D =', D: 7:4);
writeln;
TextColor (11);
write ('Натисніть будь-яку клавішу для виведення таблиці резултате побудови.');
readkey;
clrScr;
vivod;
readkey;
end.
Висновок:
У моїй роботі я використовував теоретичний матеріал і розроблену на мові (високого рівня) Turbo Pascal програму. Мною було розраховано кількість інформації на символ повідомлення, складеного з алфавіту, що складається з 24 символу, для двох випадків:
1] якщо символи алфавіту зустрічаються з рівними ймовірностями;
2] якщо ймовірності не рівні.
Також я визначив кількість недовантаження символів у другому випадку, обчислив кількість інформації на символ повідомлення та швидкість передачі повідомлень, складених з таких символів, знайшов надмірність повідомлень, складених з даного алфавіту. Побудував оптимальний код повідомлення, застосовуючи методику Шеннона-Фано: за допомогою послідовного розподілу безлічі ймовірностей на групи за принципом рівності сум ймовірностей я склав у відповідність кожному символу найбільш оптимальну двійкову комбінацію. Таким чином, був отриманий оптимальний двійковий код для алфавіту з 31 символу.
В результаті виконання роботи були отримані наступні результати:
· Кількість інформації на символ для равновероятного алфавіту - 4,585 біт / сим;
· Кількість інформації на символ для неравновероятного алфавіту - 2,6409 біт / сим;
· Недовантаження символів - 1,9441 біт / сим;
· Швидкість передачі інформації - 0,1244 біт / сек;
· Надмірність повідомлення - 0,4240;
· Побудований наступний оптимальний код:
| Символ | Імовірність появи | Код | Кількість символів | |
| p [1] | 0.0417 | 0 | ||
| p [2] | 0.0018 | 111 | ||
| p [3] | 0.0020 | 110 | ||
| p [4] | 0.0022 | 1000 | ||
| p [5] | 0.0024 | 10011 | ||
| p [6] | 0.0026 | 10010 | ||
| p [7] | 0.0029 | 101111 | ||
| p [8] | 0.0033 | 1011100 | ||
| p [9] | 0.0037 | 101101 | ||
| p [10] | 0.0042 | 101101 | ||
| p [11] | 0.0048 | 1010011 | ||
| p [12] | 0.0055 | 10100100 | ||
| p [13] | 0.0064 | 1010001 | ||
| p [14] | 0.0076 | 1010001 | ||
| p [15] | 0.0091 | 10101111 | ||
| p [16] | 0.0111 | 101011100 | ||
| p [17] | 0,0139 | 10101101 | ||
| p [18] | 0,0179 | 10101101 | ||
| p [19] | 0,0238 | 10101010 | ||
| p [20] | 0,0333 | 101010111 | ||
| p [21] | 0,0500 | 101010110 | ||
| p [22] | 0,0833 | 10101000 | ||
| p [23] | 0,1667 | 101010011 | ||
| p [24] | 0,5000 | 101010010 |
Список використаної літератури:
1. Бауер Ф. Інформатика, М. 1992.
2. Колесник В.Д. Курс теорії інформації, М. 1982.
3. Фаронов В. В. Turbo Pascal 7.0. Навчальний посібник, М. 2000.
4. Цимбалу В.П. Задачник по теорії інформації та кодування, Київ. 1976.
5. Марченко А.І. Програмування в середовищі Turbo Pascal 7.0.