1.1 Розв’язок задачі №1

На сьогоднішній день у теорії інформації виділяють три основні напрямки:

Структурний – розглядає дискретне представлення масивів інформації та вимірювання

простим підрахунком інформаційних елементів чи комбінаторним методом, який

припускає найпростіше кодування масивів.

Статистичний – оперує поняттям ентропії як міри невизначеності, яка враховує

ймовірність появи тих чи інших повідомлень.

Семантичний – враховує доцільність, цінність, корисність чи істотність інформації.

При структурному підході використовують міру Хартлі чи логарифмічну міру:

I = n*log(m), 1.1.1

де m – кількість символів в абетці,

n – кількість символів у повідомленні.

В нашому випадку m=8, n=10:

I = 10*log(8) = 30 біт

При статистичному підході кількість інформації знаходять за такою формулою:

1.1.2

Знайдемо кількість інформації у повідомленнях підставивши дані табл.1 у формулу

1.1.2:

I = -10*(0.15*log(0.15)+0.15*log(0.15)+0.03*log(0.03)+0.1*log(0.1)+0.02*log(0.02)+

+0.3*log(0.3)+0.1*log(0.1)+0.15*log(0.15)) = 10*2.679 = 26.79 біт

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

інформації більша ніж при статистичному. Це тому, що при структурному підході не

враховуються ймовірності появи символів.

1.2 Розв’язок задачі №2

Кореляційна функція та енергетичний спектр зв’язані одне з одним взаємно-

обратним перетворенням Фур’є:

1.2.1

1.2.2

Для знаходження кореляційної функції скористаємось формулою 1.2.2:

відомо, що :

звідси випливає, що кореляційна функція :

Інтервал кореляції – числова характеристика, яка служить для оцінки „швидкості

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

1.2.3

використовуючи формулу 1.2.1, де та формулу 1.2.3 отримаємо:

1.2.4

Знайдемо інтервал кореляції використовуючи формулу 1.2.4 :

Ширина спектра :

В нашому випадку , а

тому

побудуємо графік при α=4 с^-1 :

побудуємо графік при τ = 10 с :

1 .3 Розв’язок задачі №3

Якщо джерело виробляє повідомлення, що складаються з фіксованого набору

символів х з імовірностями р(х_i), то при оптимальному кодуванні вони замінюються

символами коду z чи комбінаціями символів коду так, щоб кількість інформації на один

символ коду була максимальна. Для випадку, коли відсутній статистичний зв'язок між

символами повідомлення Шеннона і Фано розроблена методика побудови коду,

близького до оптимального, який дає оптимальний результат, у тому випадку, коли

імовірності р(х_i) виражаються негативними ступенями двійки. В оптимальному

коді,який називається Шеннона-Фано, використовуються символи 0 чи 1, тобто

оптимальний код є двійковим. Побудуємо цей код. Для цього скористаємося наступним

алгоритмом.

1. Символи вихідного повідомлення (букви) розташовуються в порядку убування

їхніх імовірностей і розбиваються на дві групи так, щоб суми імовірностей у групах

були приблизно однакові.

2. Як перший символ коду всім буквам, що ввійшли в першу групу, приписується

одиниця, а буквам другої групи - нуль.

3. Кожна з отриманих підгруп знову розбивається на дві підгрупи приблизно з

однаковими імовірностями.

4. Буквам перших підгруп як наступний символ коду приписується одиниця, а до

букв другої групи - нуль і так далі.

Розбивка на підгрупи відбувається доти , поки в кожній підгрупі не залишиться по

одній букві.

Інтерпретація рішення приведена в таблиці 1.3.1.

Буквы алфав.	Вероятности	Подгруппы	Кодированные комбинации
1 а6	0.3	1 0 0 0 1 0 0 0	11
а1	0.15		10
1 1 a2	0.15		011
a8	0.15		010
1 a4	0.1		001
0 a7	0.1		0001
1 а3	0.03		00001
а5	0.02		00000

Оцінимо ефективність методу Шеннона-Фано, визначивши ентропію отриманого

коду. Для цього визначимо ймовірність появи символу коду:

p(1)=(2*0.3+4*0.15+2*0.1+0.03)/(2*0.3+8*0.15+7*0.1+5*0.03+5*0.02)=0.52

p(0)=1-p(1)=0.48

Тоді ентропія

H= –p(1)log₂p(1)– p(0)log₂p(0)=-0.52*log(0.52)-0.48*log(0.48)=0.9988 бит.

Визначимо надмірність коду D_отн:

D_отн =1-(H/Hmax)=1-0.9988/1=0.0012

Код Шеннона–Фано розрахован на використання двійкової абетки.Хаффменом

було запропанована методика, дозволяюча побудуватиоптималний код з мінімальною

надмірністю при будь-якії основі коду m.

Правило побудови коду полягає в наступному:

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

2. n₀ найменш ймовірних літер об’єднують у одну допоміжну, ймовірність якої визначаєтьсясумою ймовірностей літер, що входять до неї. Кількість n₀ вихначаэться з умови так щоб виконувалось співвідношення

де M – кількість символів повідомлення; j – ціле число.

3. В якості останніх символів коду, що приписується літерам, які ввійшли до допоміжної літери, вибирають n₀ різних символів коду.

4. Літери, що залишились та допоміжну літеру розташовують у порядку убування ймовірностей.

5. Складається друга допоміжна літера, в яку входять m найменшймовірних літер. Літерам, що ввійшли присваіваються різні символи коду і т.д.

Утворення допоміжних літер здійснюється до тих пір, поки не буде отримана одна

літера з ймовірністю, яка дорівнює одиниці. Утворення кодових комбінацій

здійснюється з урахуванням всіх символів, приписаних літерам на всіх етапах їх

об’єднання.

Інтерпретація рішення приведена в таблиці 1.3.2.

Таблица 1.3.2

Буквы алфав.	Вероятности	Подгруппы	Комбинации
а6	0.3	1 0.6 1 0.4 0 0.4 0.3 1 0.3 0.3 0 0.3 0.3 0.25 1 0.25 0.15 0 0.3 0.15 0.15 0.15 1 0.3 0.15 0.15 0 0.15 0.15 0.15 0.15 1 0.15 0.1 0 0.1 0.1 1 0.05 0 1 0	11
а1	0.15		00
a2	0.15		101
a8	0.15		001
a4	0.1		010
a7	0.1		1110
а3	0.03		10110
а5	0.02		00110

Оцінимо ефективність методу Хаффмена, визначивши ентропію отриманого

коду. Для цього визначимо ймовірність появи символу коду:

p(1)=(2*0.3+3*0.15+4*0.1+3*0.03+2*0.02)/(2*0.3+8*0.15+7*0.1+5*0.03+5*0.02)=0.57

p(0)=1-p(1)=0.43

Тоді ентропія

H= –p(1)log₂p(1)– p(0)log₂p(0)=-0.57*log(0.57)-0.43*log(0.43)=0.985 бит.

Визначимо надмірність коду D_отн :

D_отн =1-(H/Hmax)=1-0.985/1=0.015

Як можна бачити, надмірність коду Хаффмена більша ніж надмірність коду

Шеннона-Фано, тобто код Шеннона-Фано білш наближений до оптимального.