Розрахунок оптимального коду за методикою Шеннона-Фано

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

ЗМІСТ

Зміст

Анотація

Введення

Зміст завдання

Теоретична частина

Практична частина

а) розрахунки

б) програма

Висновок

а) результати роботи програми

б) блок-схема

Література

АНОТАЦІЯ

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

До роботи додається програма, написана мовою програмування високого рівня (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) Розрахунки

  1. розраховується початкові ймовірності для неравновероятних символів алфавіту.

  2. виконує нормування зазначених ймовірностей.

  3. розраховується ентропія алфавіту з рівноймовірно символів.

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

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

  6. будується оптимальний код за методом Шеннона-Фано.

Розрахунок ймовірностей.

Проміжні значення:

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

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

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

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 2 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 2 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 2 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 2 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













11 0

4

p21 = 0,0500


1

0,25

0


0

0,05

1 0











1 0 00

5

p1 = 0,0417


1


0


0

0,0690

1

0,0357

1









1 0 0 11

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







1 01101

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





1 010001

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,002 6

1

1 01010111

21

p5 = 0,0024


1


0


1


0


1

0,0147

0


1


1

0,002 4

0

101010110

22

p4 = 0,0022


1


0


1


0


1


0


0

0,00 22

0



10101000

23

p3 = 0,0020


1


0


1


0


1


0


0

0,003 8

1

0,00 20

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,2 500

A [4] (p21)

0,0500

1000

4

0,2 000

A [5] (p 1)

0,0417

10011

5

0, 2083

A [6] (p20)

0,0333

10010

5

0,1 667

A [7] (p19)

0,0238

101111

6

0,1 429

A [8] (p18)

0,0179

1011100

7

0,1 250

A [9] (p17)

0,0139

101101

6

0, 0833

A [10] (p16)

0,0111

101110

6

0,0 667

A [11] (p15)

0,0091

1010011

7

0,06 36

A [12] (p14)

0,0076

10100100

8

0,0 6 06

A [13] (p13)

0,0064

1010001

7

0,044 9

A [14] (p12)

0,0055

1010011

7

0,0 385

A [15] (p11)

0,0048

10101111

8

0,038 1

A [16] (p10)

0,0042

101011100

9

0,03 75

A [17] (p9)

0,0037

10101101

8

0,02 94

A [18] (p 8)

0,0033

10101110

8

0,0 261

A [19] (p 7)

0,0029

10101010

8

0,02 34

A [20] (p 6)

0,0026

101010111

9

0,02 37

A [21] (p 5)

0,0024

101010110

9

0,021 4

A [22] (p 4)

0,0022

10101000

8

0,01 73

A [23] (p 3)

0,0020

101010011

9

0,017 8

A [24] (p 2)

0,0018

101010010

9

0,01 63

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

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

Оптимальний код (вийшов результат):

Буква


Імовірність

появи букви

Кодове слово

Кількість символів в кодовому слові

p i l i

P 1

0,055

000

3

0,165

P2

0, 0 53

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,0 33

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,0 27

11001

5

0,135

P20

0,0 26

11010

5

0,130

P21

0,0 25

110110

6

0,150

P22

0,0 23

110111

6

0,138

P23

0,0 22

11100

5

0,110

P24

0,0 20

111010

6

0,120

P25

0,0 19

111011

6

0,114

P26

0,0 18

111100

6

0,108

P27

0,0 17

111101

6

0,102

P28

0,0 16

111110

6

0,096

P29

0,0 13

1111110

7

0,091

P30

0,0 12

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,0 12

11111110








0,012

P3

0,0 13

1111110







0,013


P4

0,0 16

111110






0,016



P5

0,0 17

111101





0,035

0,017



P6

0,0 18

111100






0,018



P7

0,0 19

111011




0,061

0,039

0,019



P8

0,0 20

111010






0,020



P9

0,0 22

11100





0,022




P10

0,0 23

110111



0,130

0,074

0,048

0,023



P11

0,0 25

110110






0,025



P12

0,0 26

11010





0,026




P13

0,0 27

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,0 33

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, 0 53

0010




0,053





P31

0, 0 55

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.

Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Курсова
291.4кб. | скачати


Схожі роботи:
Розрахунок оптимального коду за методикою Шеннона Фано
Розрахунок оптимального теплообмінника за параметрами ефективності теплопередачі
Розрахунок оптимального рівня ціни обсягу виробництва та продажу
Розрахунок і побудова ТКТ вибір оптимального індикатора та визначення індикаторної похибки при
Відкриття та характеристика генетичного коду
Побудова групового корректірующегоій коду обсягом 9 слів
Про можливість універсального коду внутрішнього представлення програми
Закономірність зміни ефективності накопичення сигналу двійкового коду
Техніка роботи з методикою Айзенка
© Усі права захищені
написати до нас