Оптимальне кодування

Размещено на http://www.allbest.ru/

ВСТУП

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

1) Вимірювання кількості інформації,

2) Вивчення властивостей інформації,

3) Розробка оптимальних методів кодування, що забезпечують максимальну пропускну здатність каналів зв'язку за наявності завад.

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

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

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

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

Задача № 1

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

Таблиця 1.1 - Статистична схема джерела

a1	a2	a3	a4	a5
0,1	0,3	0,2	0,35	0,05

Кількість інформації в кожному з символів можна обчислити за формулою[2]:

І_і =(1.1)

Ентропія - це середня кількість інформації, яка припадає на один символ повідомлення. Ентропія визначається за формулою[1]:

H (1.2)

Надмірність коду повідомлення визначається за такими формулами[1]:

Абсолютна надмірність: (1.3)

Відносна надмірність: (1.4)

де H_max=log m - максимальна ентропія за розміру алфавіту m.

Знайдемо кількість інформації у кожному із символів (формула 1.1) :

І₁ == 3,322

І₂ == 1,737

І₃ == 2,322

І₄ == 1,515

І₅ == 4,322

Визначимо ентропію джерела та максимальну ентропію (формула 1.2) :

H

H_max=

Тоді надмірності визначимо за формулами 1.3-1.4 :

=11,11 %

Висновок

Ентропія - це середня кількість інформації, яка припадає на один символ повідомлення вона завжди на перевищує log m. Ентропія починає зменшуватися якщо символи стають не рівноімовірними аж до нуля якщо імовірність появи одного з символів наближається до одиниці.

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

Задача № 2

Для джерела повідомлень (задача 1) побудувати код Шенона-Фано, знайти надмірність коду.

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

Основні етапи[3]:

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

- Символи отриманого алфавіту m2 ділять на дві частини, сумарні ймовірності символів яких максимально близькі один одному.

- В префіксному коді для першої частини алфавіту присвоюється двійкова цифра «0», другої частини - «1».

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

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

На таблиці 2.1 представлено код для данного по задачі джерела.

Таблиця 2.1 - Код Шеннона фано для данного джерела

Індекс символу аі	Імовірність	Код
4	0.35	0
2	0.3	1	0
3	0.2	1	1	0
1	0.1	1	1	1	0
5	0.05	1	1	1	1

Вираховуємо максимальну ентропію коду:

H_max= log 2=1

Для обрахування ентропії H треба знайти ймовірності появи символів 1 та 0 в коді для елементів, скориставшись формулами частоти появи символу[1]:

P(x_k)=,

де - кількість символів коду що відповідають символу , - повна кількість символів кодової комбінації.

p(1)= =

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

H

Знаходимо абсолютну та відносну надмірність:

Висновок

Задане джерело повідомлення було закодовано кодом за методом Шенона-Фано. Символи джерела можуть приймати значення 1 та 0, утворюючи дві групи коду відповідно.

Ентропія коду ближче до максимуму ніж незакодованої послідовності і дуже близька до максимального значення, отже, кодування є оптимальним.

Для отримання ймовірностей появи 1 та 0 тип повідомлення прийнято за типовий, в якому ймовірність появи елемента рівна частоті появи елемента.

Задача № 3

Для джерела повідомлень (задача 1) побудувати код Шенона-Фано, який забезпечує надмірність, меншу 0,5% (блочний код).

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

Таблиця 3.1 - Код Шеннона фано для данного джерела

Індекси комбінації аі аj	Імовірність	Код
44	0,1225	0	0	0
42	0,105	0	0	1
24	0,105	0	1	0
22	0,09	0	1	1	0
43	0,07	0	1	1	1
34	0,07	1	0	0	0
32	0,06	1	0	0	1
23	0,06	1	0	1	0
33	0,04	1	0	1	1	0
41	0,035	1	0	1	1	1
14	0,035	1	1	0	0	0
21	0,03	1	1	0	0	1
12	0,03	1	1	0	1	0
31	0,02	1	1	0	1	1
13	0,02	1	1	1	0	0	0
54	0,0175	1	1	1	0	0	1
45	0,0175	1	1	1	0	1	0
52	0,015	1	1	1	0	1	1
25	0,015	1	1	1	1	0	0
53	0,01	1	1	1	1	0	1
35	0,01	1	1	1	1	1	0	0
11	0,01	1	1	1	1	1	0	1
51	0,005	1	1	1	1	1	1	0
15	0,005	1	1	1	1	1	1	1	0
55	0,0025	1	1	1	1	1	1	1	1

Розрахунки наведені далі аналогічні розрахункам з попередньої задачі.

Вираховуємо максимальну ентропію коду:

H_max= log 2=1

p(0)= =

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

H

Знаходимо абсолютну та відносну надмірність:

%

Висновок

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

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

Задача № 4

Для ансамблю символів джерела (таблиця 1.1). Побудувати код Хафмена

а) m=2, б) m=3, визначення надмірності коду:

код інформаційний ентропія шенон

Таблиця 1.1 - Статистична схема джерела

a1	a2	a3	a4	a5	a6	a7	a8
0,37	0,24	0,05	0,18	0,08	0,03	0,04	0,01

а) Формування додаткових допоміжних букв для випадку m=2 не потрібне, адже умова кодування 2 n₀2 є однозначна для визначення n₀

Отже за n₀=2 код можна формується так (результат наведено в таблиці 3.2):

1

0,61___1

0,39 0,39 ___0

а1= 0,37 0,37 0,37 0,37 0,37 0,37 ___1

а2= 0,24 0,24 0,24 0,24 0,24 0,24 ___0

0,21 ___1

а4= 0,18 0,18 0,18 0,18 0,18 ___0

0,13 ___1

а5= 0,08 0,08 0,08 0,08 ___0

0,08 ___1

а3= 0,05 0,05 0,05 ___0

а7= 0,04 0,04 ___1

0,04 ___0

а6= 0,03 ____1

а8= 0,01 ____0

Таблиця 3.2 - Код Хафмена для джерела m=2

a1	a2	a3	a4	a5	a6	a7	a8
11	10	0110	00	010	011101	01111	011100

Розрахунки аналогічні попередній задачі.

H_max= log2=1

p(0)==

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

H

Знаходимо абсолютну та відносну надмірність:

%

б) Формування додаткових допоміжних букв для випадку m=3 потрібне, умова кодування 2 n₀3, = j, j- ціле число, M- число символів повідомлення.

Отже, n₀=2, тоді умова (8-2)/(3-1)=6/2=3 виконується.

 1

0,39___2

а1= 0,37 0,37 0,37 0,37___1

а2= 0,24 0,24 0,24 0,24 ___0

а4= 0,18 0,18 0,18 ___2

0,13 ___1

а5= 0,08 0,08 0,08 ___0

а3= 0,05 0,05 ___2

а7= 0,04 0,04 ___1

0,04 ___0

а6= 0,03 ____1

а8= 0,01 ____0

Таблиця 3.3 - Код Хафмена для джерела m=3

a1	a2	a3	a4	a5	a6	a7	a8
1	0	212	22	20	2101	211	2100

H_max= log3=1,585

p(2)==

p(1)==

p(0)= 1- =

H

Знаходимо абсолютну та відносну надмірність:

%

Висновок

Кодуючи ансамбль символів джерела кодом Хаффмана, для значень алфавіту m=2 (таблиця 3.2), та m=3 (таблиця 3.3) знайшли надмірність коду, що складає:

Для m=2 : D=2,764 %

Для m=3: D=2,069 %

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

Висновки

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

Було побудовано кодові послідовності для данних джерел за алгоритмами Хаффмана, та Шенона-Фано: блочним та звичайним

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

Для ансамблю з 5 символів було побудовано код Шенона-Фано, та знайдено надмірність коду:

Порівняно з вхідними данним результат покращився на порядок.

Для того ж джерела блочний код дав на 4 порядки кращий результат:

%

Побудова коду Хаффмана для ансамблю символів джерела зроблена для різних значень алфавіту дає змогу порівняти значення надмірності кодів при збільшенні числа алфавіту.

Для m=2 : D=2,764 %

Для m=3: D=2,069 %

Результати обчислень відрізняються на 0,7%, з чого можна зробити висновок, що збільшення букв алфавіту кодування призвело до зменшення надмірності коду.

Навики і знання, отримані при виконанні роботи, являються фундаментальними для студента спеціальності «Телекомунікаційні системи та мережі», так як дають уявлення про закономірності передачі та прийому повідомлень і найзагальніші поняття такі як інформація, ентропія, надмірність.

Перелік посилань

1. В. Г. Абакумов, «Электронные промышленные устройства», 1978, «Вища школа», Киев, 369 ст;

2. Ю.П. Жураковський, В.П. Полторак, «Теорія інформації та кодування», 2001, «Вища школа», Київ, 255 ст.

3. А. М. Яглом, И. М. Яглом. Вероятность и информация. -- М.: «Наука», 1973.

Размещено на Allbest.ru

...