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

Основною задачею теорії інформації та кодування як самостійної дисципліни є оптимальне використання інформаційних характеристик джерел інформації і каналів зв’язку для побудови кодів, які забезпечують задану достовірність передачі інформації з максимально можливою швидкістю при мінімально можливій вартості передачі інформації [3, с. 11].

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

Теорією інформації називається розділ кібернетики, в якому математичними методами вивчаються способи вимірювання кількості інформації, що міститься в яких-небудь повідомленнях, та способи її передачі [3, с. 11].

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

Для успішного вирішення класичних задач теорії інформації та кодування слід пам’ятати основні положення, на яких базується ця дисципліна, а саме:

• інформація при вирішенні задач теорії інформації та кодування розглядається узагальнено, без урахування її змісту;

• теорія інформації оперує не з фізичними системами передачі інформації, а з їх математичними моделями.

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

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

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

• кодування з метою забезпечення максимальної ефективності використання ресурсів систем передачі інформації та зменшення витрат на передачу інформації (оптимальне кодування);

• кодування з метою забезпечення безпомилкової передачі інформації (перешкодостійке кодування).

Тема 1 Кількісна оцінка інформації

Заняття 1

Математичні основи теорії інформації. Міра Хартлі. Ентропія.

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

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

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

N = mⁿ . (1.1)

Примітка 1.1. Замість виразу “алфавіт складається з m символів” в теорії інформації можуть використовуватись формулювання “алфавіт має m якісних ознак” або (для цифрових алфавітів) ”основа системи числення дорівнює m”.

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

Розв’язок.

Згідно з умовою визначаємо: m=3, n=2. Таким чином, згідно з формулою (1.1), загальна кількість повідомлень, яка може бути складена з такого алфавіту без повторень, дорівнює:

N = 3² = 9 .

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

00 10 20

01 11 21

02 12 22 .

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

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

Приклад 1.2. Визначити кількість можливих станів системи, яка складається з двох підсистем, кожна з яких може випадковим чином переходити в один з трьох станів.

Розв’язок.

Згідно з умовою визначаємо: n=2, m=3. Оскільки кількість n для кожної з m підсистем однакова, у відповідності з формулою (1.1) визначаємо загальну кількість можливих станів системи в цілому:

N = 3² = 9 .

Певною особливістю вирішення відрізняється зворотна задача, яка полягає у визначенні мінімальної розрядності повідомлень n, достатньої для складання визначеної кількості повідомлень (N) в алфавіті з відомим показником m. Оскільки розрахункове значення n може бути дробовим, а розрядність повідомлення може бути лише цілим числом, шукане значення розрядності визначається як найменше ціле число, не менше від розрахункового значення n (n_{розрахункове}  n_шукане < n_{розрахункове}+1, де n_шукане – натуральне число).

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

Розв’язок.

Згідно з умовою визначаємо кількість можливих повідомлень N=33, кількість символів алфавіту m=2 (двійковий код). З (1.1) отримуємо формулу для обчислення значення кількості символів в повідомленні n:

n = log_m N .

За отриманою формулою визначаємо n:

n = log₂ 33 = 5.02 .

Оскільки отримане значення дробове, визначаємо найменше ціле число, не менше від розрахункового значення n. Шукане значення розрядності повідомлень дорівнює 6 (5.02  6 < 5.02+1).

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

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

Кількісна оцінка в теорії інформації виконується з точки зору ефективності використання ресурсів систем передачі інформації (каналів зв’язку і т.д.). Цілком виправданим при цьому є вибір для виміру кількості інформації одиниць, які визначають ступінь зайнятості ресурсів системи при передачі коду інформаційного повідомлення. Очевидно, що ресурси системи передачі інформації будуть використані найефективніше, якщо інформація буде передаватися повідомленням з найменшою можливою довжиною (розрядністю). Тому в якості одиниці виміру кількості інформації обрано 1 розряд коду, в якому представляються інформаційні повідомлення. Так, якщо інформація кодується в найбільш поширеній в цифрових обчислювальних системах двійковій системі числення, то одиницею виміру буде один двійковий розряд, тобто 1 біт. В десятковій системі числення кількість інформації вимірюється в десяткових розрядах і одиницею виміру є 1 діт (1діт3.32 біт) і т.д.

Як же визначити, скільки розрядів повинне містити повідомлення для передачі певної кількості інформації, або, інакше кажучи, як визначити, скільки інформації міститься в повідомленні?

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

І = log_l N , (1.2)

де N – кількість повідомлень, які формуються для передачі інформації; l - основа системи числення, в якій вимірюється кількість інформації.

Як видно з формули (1.2), основа логарифму безпосередньо визначає одиниці виміру кількості інформації.

Підстановкою значення N з формули (1.1) в (1.2) можна отримати:

І = log_l mⁿ = n log_l m . (1.3)

З формули (1.3) можна зробити висновок, що при l=m (log_l m = 1) кількість інформації І в повідомленні дорівнює його розрядності n.

Для оцінки кількості інформації в двійковій системі числення з (1.2) можна отримати наступну формулу:

І = log₂ N (біт) . (1.4)

Відповідно, для десяткової системи числення:

І = log₁₀ N = lg N (діт) . (1.5)

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

Розв’язок.

Згідно з умовою кількість повідомлень N=16. За формулою (1.4) визначаємо кількість біт інформації в одному повідомленні:

І = log₂ 16 = 4 біта .