Реферати українською » Информатика, программирование » Розрахунок оптимального коду за методикою Шеннона-Фано


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

Страница 1 из 3 | Следующая страница

>СОДЕРЖАНИЕ

Зміст

Анотація

Запровадження

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

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

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

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

б) програма

Укладання

а) результати своєї роботи програми

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

Література


>АННОТАЦИЯ

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

До роботи додається програма, написана мовою програмування високого рівня (TurboPascal).

>SUMMARY

>Inthiswork on thegivennumbeofsymbols in thealphabettheirprobabilities,amount of the informationifsymbolsmeetequalprobabilities andwithdifferentprobabilities,speed of messagetransfer andredundancy ofmessagespay off.Besides in thegivenwork theoptimumbinarycodebytechnique ofShennon andFanoisunderconstruction.Performance ofthiscourseworkfixesourknowledge ondiscipline «TheTheory of the Information».


ЗАПРОВАДЖЕННЯ

Інформатика і обчислювальної техніки – це область науку й техніки, що включає сукупність коштів, засобів і методів людської діяльності, вкладених у створення і застосування пристроїв зв'язку, систем збору, збереження і обробки інформації.

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

Однією з методів захисту є кодування.

Кодування – це відображення повідомлень кодом за певним правилу присвоєння символів.

Код – цього правила, яке описує відображення одного набору знаків на другий набір знаків (чи слів).Кодом також називають і безліч образів у своїй відображенні.

Оптимальний код – це найефективніший випадок кодування з травня нульової надмірністю. При усуненні надмірності піддається суттєвому зниженню кількість символів, необхідних кодованих повідомлень. У результаті зменшується час передачі, знижується необхідний обсяг пам'яті.

Отже, знання методів обробки інформації базове для інженерів, робота яких пов'язане з обчислювальними системами і мережами. Надмірність - додаткові кошти на, запроваджувані до системи підвищення її надійності й захищеності.

Отже, інформатика займається вивченням оброблення і передачі.

Діяльність відбивається застосування базових понять інформатики.


>СОДЕРЖАНИЕЗАДАНИЯ

Для проведення розрахунків розробити програму мовою ПАСКАЛЬ.

1.1. Кількість символів алфавітуk =m (номер варіанта завдання) + 10. Визначити кількість інформації на символ повідомлення, що складається з цього алфавіту:

і якщо символи алфавіту зустрічаються із рівними імовірностями;

б) якщо символи алфавіту зустрічаються у міжнародному сполученні з імовірностями:

р1 = 0,15;p2 =p1/(>k-1);p3 = (>p1 +p2 )/(>k-2) ...

>k-1

>p>k = pn /(>k –k + 1).

>n=1

Сума всіх ймовірностей мусить бутиравой одиниці, тому:

       >pі

 рі = -----

          >k

 pj

 >j=1

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

1.2. Кількість символів алфавіту =m (номер варіанта завдання).Вероятности появи символів рівні відповідно

р1 = 0,15;p2 =p1/(>k-1);p3 = (>p1 +p2 )/(>k-2) ...

>k-1

>p>k = pn /(>k –k + 1).

>n=1

>Длительности символів1 = 1 сік;2 = 2 сік;

>>k =>k-1 + 1.

Чому дорівнює швидкість передачі повідомлень, що складаються з таких символів?

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

і якщо символи алфавіту зустрічаються із рівними імовірностями;

Визначити, наскільки недозавантажені символи у другий випадок.

1.3. Повідомлення складаються з алфавіту із кількістю символів =m. Можливість появи символів алфавіту дорівнює відповідно:

р1 = 0,15;p2 =p1/(>k-1);p3 = (>p1 +p2 )/(>k-2) ...

>k-1

>p>k = pn /(>k –k + 1).

>n=1

Знайти надмірність повідомлень, що складаються з даного алфавіту.

Побудувати оптимальний код повідомлення.


ТЕОРЕТИЧНА ЧАСТИНА

>КОЛИЧЕСТВЕННАЯ ОЦІНКА ІНФОРМАЦІЇ

Загальна кількістьнеповторяющихся повідомлень, що може бути складається з алфавітуm шляхом комбінування по n символів у міжнародному сполученні,

N =mn

Невизначеність, яка припадає на символ первинного (кодованого) алфавіту, що складається зравновероятних івзаимонезависимих символів,

H =log2m

Оскільки інформація є невизначеність,снимаемая і при отриманні повідомлення, кількість інформації то, можливо представлено як твір загальної кількості повідомленьk на середню ентропію H, що припадає одне повідомлення:

I =k*H біт

Для випадківравновероятних івзаимонезависимих символів первинного алфавіту кількість інформацієюk повідомленнях алфавітуm одно:

I =k*log2m біт

Длянеравновероятних алфавітів ентропія на символ алфавіту:

>mm

H =pі*>log2(>1/2pі)=->pі*>log2>pібит/символ

>i=1i=1

А інформацією повідомленні, складеному зkнеравновероятних символів,

>m

I = ->k*pі*>log2>pі біт

>i=1

>ВЫЧИСЛЕНИЕ ШВИДКОСТІ ПЕРЕДАЧІ ІНФОРМАЦІЇ ІПРОПУСКНОЙСПОСОБНОСТИКАНАЛОВ ЗВ'ЯЗКУ

За відсутності перешкод швидкість передачі визначається кількістю інформації, стерпним символом сполучення одиницю часу, і дорівнює

З =n*H,

де n - кількість символів, вироблюваних джерелом повідомлень за одиницю часу; H - ентропія (невизначеність),снимаемая і при отриманні одного символу повідомлень, вироблюваних даним джерелом.

Швидкість передачі також може бути представлена як

 >бит/сек,

детау - час передачі одногодвоичного символу.

Для повідомлень, що складаються зравновероятнихвзаимонезависимих символів рівної тривалості, швидкість передачі:


>C=(1/)*log2mбит/сек

Що стосуєтьсянеравновероятних символів рівної тривалості:

>m

З =(>1/)*pі*>log2>pібит/сек

>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 = P.Spn /(>m -k + 1).

 >n-1

Остаточний результат:

 рі =pі/(>pі)

>p1 = 0,1500

>p2 = 0,0065

>p3 = 0,0071

>p4 = 0,0078

>p5 = 0,0086

>p6 = 0,0095

>p7 = 0,0105

>p8 = 0,0118

>p9 = 0,0132

>p10 = 0,0150

>p11 = 0,0171

>p12 = 0,0198

>p13 = 0,0231

>p14 = 0,0273

>p15 = 0,0327

>p16 = 0,0400

>p17 = 0,0500

>p18 = 0,0643

>p19 = 0,0857

>p20 = 0,1200

>p21 = 0,1800

>p22 = 0,3000

>p23 = 0,6000

>p24 = 1,8000

рі = 3,6

>p1=0,0417

>p2=0,0018

>p3=0,0020

>p4=0,0022

>p5=0,0024

>p6=0,0026

>p7=0,0029

>p8=0,0033

>p9=0,0037

>p10=0,0042

>p11=0,0048

>p12=0,0055

>p13=0,0064

>p14=0,0076

>p15=0,0091

>p16=0,0111

>p17=0,0139

>p18=0,0179

>p19=0,0238

>p20=0,0333

>p21=0,0500

>p22=0,0833

>p23=0,1667

>p24=0,5000

рі = 1

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

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

H>max =log2 24 =ln24/ln 2 = 4,5850бит/символ

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

H = – (>0,0417*log20,0417 +0,0018*log20,0018 +0,020*log2 0,0020 +0,0022*log20,0022 +0,0024*log20,0024 +0,0026*log20,0026 +0,0029*log20,0029 +0,0033*log20,0033 +0,0037*log20,0037 +0,0042*log20,0042 +0,0048*log20,0048 +0,0055*log20,0055 +0,0064*log20,0064 +0,0076*log20,0076 +0,0091*log20,0091 +0,0111*log20,0111 +0,0139*log20,0139 +0,0179*log20,0179 +0,0238*log20,0238 +0,0333*log20,0333 +0,0500*log20,0500 +0,0833*log20,0833 +0,1667*log20,1667 +0,5000*log20,5000) =

= 2,6409бит/символ


>Недогруженность символів у разі:

N = М>max – М = 4,5850 – 2,6409 = 1,9441бит/символ

>Вичисление швидкості передачі.

З= – (>0,0417*log20,0417 +0,0018*log20,0018 +0,020*log2 0,0020 +0,0022*log20,0022 +0,0024*log20,0024 +0,0026*log20,0026 +0,0029*log20,0029 +0,0033*log20,0033 +0,0037*log20,0037 +0,0042*log20,0042 +0,0048*log20,0048 +0,0055*log20,0055 +0,0064*log20,0064 +0,0076*log20,0076 +0,0091*log20,0091 +0,0111*log20,0111 +0,0139*log20,0139 +0,0179*log20,0179 +0,0238*log20,0238 +0,0333*log20,0333 +0,0500*log20,0500 +0,0833*log20,0833 +0,1667*log20,1667 +0,5000*log20,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 из 3 | Следующая страница

Схожі реферати:

Навігація