Кількісні інформаційні характеристики дискретних джерел повідомлень і каналів

20

Кількісні інформаційні характеристики дискретних джерел повідомлень і каналів

Функції інформації

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

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

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

Інформація передається, обробляється у вигляді окремих повідомлень.

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

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

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

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

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

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

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

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

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

а) управлінської, яка виявляється у всіх елементах повсякденного життя і в трудовій діяльності, і покликана допомогти людині у виборі варіанту власної поведінки або варіанту цілеспрямованої дії на об'єкти і процеси реального миру;

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

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

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

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

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

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

При введенні кількісної міри інформації (Норберт Вінер і Клод Шеннон) було прийнято смисловий зміст повідомлень (семантику) не враховувати, а обмежитися тільки формальними ознаками, важливими з погляду передачі повідомлень по каналах зв'язку. У результаті враховуються тільки число N повідомлень, що підлягають передачі, і ймовірності р(х_i) надходження їх на вхід каналу. Всю сукупність повідомлень представляють у вигляді деякої системи Х із станами x_i

, (1)

де: x_i - окремі повідомлення (або їх типи, класи), p(x_i) - апріорна ймовірність появи повідомлень x_i.

В результаті передачі повідомлення x_i по каналу зв'язку буде одержане повідомлення y_j. Воно може з деякою ймовірністю бути схоже на будь-яке з (x₁, x₂,…x_N) повідомлень. Зокрема воно може бути схоже на передане повідомлення xi. Апостеріорна (післядослідна) ймовірність присутності x_i в y_j дорівнює p(x_i/ y_j).

У основу міри кількості інформації встановлені зміни ймовірності появи повідомлень від апріорного значення p (x_i) на вході каналу до апостеріорного значення p (xi/yj) на виході каналу, пов'язані із викривленнями інформації у каналі.

Порівнюючи ймовірність р(x_i) і p (x_i/y_j) можна встановити міру кількості інформації, переданої через даний канал. Зручною мірою виявився логарифм відношення апостеріорної ймовірності до апріорної.

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

. (2)

Основою логарифма можуть бути: 2, е 2,72, або 10. Залежно від основи міняються одиниці вимірювання кількості інформації (біти дв. од.; ніт нат. од.; хартлі (діти) дес. од.)

Властивості кількості інформації I(x_i; y_i):

1. Властивість симетрії. Інформація, що міститься в y_j щодо x_i, дорівнює інформації, що міститься в x_i щодо y_j. Це стає очевидним, якщо чисельник і знаменник в (1) помножити на p (yi) і виробити перетворення:

,

оскільки p (x_i, y_j) = p (y_j), p(x_i/ y_j) = p (x_i), p (y_j/ x_i) - ймовірність сумісної появи y_j і x_i.

В результаті вказаної властивості величину I(x_i;y_j) називають кількістю взаємної інформації між x_i і y_j.

2. Властивість адитивності. Інформація, що міститься в парі символів y_j, z_k щодо x_i, дорівнює сумі інформації, що міститься в y_j щодо x_i і інформації, що міститься в z_k щодо x_i за умови, що значення y_j відоме

. (3)

Кількість власної інформації у x_i визначається з (2) при p(x_i/ y_j) = 1

. (4)

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

З урахуванням введеного поняття (4) можна перетворити вираз (2) до вигляду

,

де I (x_i / y_j) = -log p (x_i / y_j) умовна власна інформація.

Середня кількість взаємної інформації виходить шляхом усереднювання (2) по всіх i і j :

.

Ентропія. Властивості ентропії

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

(5)

Властивості ентропії:

1. Ентропія H(X) ненегативна: H(X) > 0.

2. Ентропія H(X) < logN.

3. Величина logN = D називається інформаційною пропускною спроможністю алфавіту (інформаційною місткістю алфавіту).

4. Якщо N = 2, то p(x₁) = p, p(x₂) = 1p,

H(Х)= - p log p - (1p) log (1p).

5. Найвища невизначеність, а відтак і максимум ентропії досягається при p = 0,5 і тоді

H(Х) = -log 0,5 = log 2 = 1,

тобто місткість двійкового алфавіту дорівнює 1 біт.

Залежність H(X) від величини р показано на рис. 7.

6. Ентропія для об'єднаних ансамблів:

. (6)

7. Часткова умовна ентропія

. (7)

Рис. 1. Залежність H(X) від величини р

Середнє значення часткових умовних ентропій називається умовною ентропією

. (8)

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

Якщо врахувати, що математичне очікування є результат усереднювання по всіх станах, то вирази (5), (6) і (8) можна записати у вигляді



,

,

де М - математичне очікування. З теорії ймовірності відомо, що

p(x, у) = p(x) p(у/x) = p(y) p(x/y).

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

H(X,Y) = H(X) + H(Y/X),

H(X,Y) = H(Y) + H (X/Y). (9)

У іншій формі (9) має вигляд

H(X) H (X/Y) = H(Y) H (Y/X). (10)

Ліву частину (10) можна інтерпретувати як середню кількість інформації I(X, Y), доставлену в пункт прийому, яка дорівнює середній кількості переданої інформації H(X) мінус середню кількість інформації H (X/Y), втрачену унаслідок дії шумів:

I(X, Y) = H(X) H (X/Y).

Права частина (10) містить ентропію шуму H(Y/X) при відомому сигналі X:

H(Y/X) = H(Y) H (Y/X).

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

Ентропія систем з безперервною безліччю станів обчислюється за правилами аналізу дискретних систем з попереднім квантуванням щільності ймовірності w (x) з кроком Дх.

Тоді число станів в системі буде дорівнювати

,

а ймовірність станів p(x_i)= w (x_i) Дх.

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

.

Після перетворень і устремління Дх ?до нуля одержуємо

(11)

Величина H*(X) називається приведеною ентропією. Вона дорівнює:

 (12)

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

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

.

Продуктивність вимірюється в бітах на секунду. Позначивши величину 1/Т як швидкість (елементів в секунду), маємо

.

Аналогічним чином, тобто розділивши в формулах (3) (10) значення ентропії та кількості інформації на Т і позначаючи

, ,

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

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

.

Це співвідношення наочно ілюструється на рисунку 8.

Рис. 2. Співвідношення між характеристиками каналу та швидкістю передачі інформації

На цьому рисунку H^/(U) продуктивність джерела переданого сигналу U, а “продуктивність” каналу, тобто повна власна інформація в прийнятому сигналі за одиницю часу. Величина є втратою інформації або ненадійністю каналу в одиницю часу, а швидкість створення помилкової, сторонньої інформації в каналі, яка не має відношення до U і обумовлена присутніми в каналі завадами. За визначенням Шеннона ненадійність каналу є ентропією входу, коли вихід відомий, тобто її можна вважати мірою середньої невизначеності прийнятого сигналу. Величина ж є ентропія виходу, коли вхід відомий і служить мірою середньої невизначеності переданого сигналу.

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

.

Пропускна спроможність дискретного каналу

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

,

де U і Z ансамблі повідомлень на вході і виході каналу. З чотирьох фігуруючих тут ентропій лише H(U) власна інформація джерела переданих символів, яка визначається джерелом вхідного сигналу і не залежить від властивостей каналу. Решта трьох ентропій в загальному випадку залежить як від властивостей джерела, так і від каналу. Уявимо собі, що на вхід каналу можна подавати символи від різних джерел, що характеризуються різними розподілами імовірності P(U), при одних і тих же значеннях швидкості передачі символів і алфавітах M. Для кожного такого джерела кількість інформації, переданої по каналу, приймає своє значення. Вочевидь, існує якесь джерело вхідного сигналу з деяким розподілом P(U), для якого величина I(U,Z) є максимальною. Максимальна по розподілу P(U) кількість переданої інформації, узята за всілякими джерелами вхідного сигналу, характеризує сам канал, і називається пропускною спроможністю каналу з розрахунку на один символ:

біт на символ, (11а)

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

біт на символ, (11б)

яку і називають просто пропускною спроможністю каналу. Пропускна спроможність каналу задовольняє системі нерівностей

, (12)

причому С = 0 при незалежних вході і виході каналу, тобто H(U/Z) = H(U) (обрив каналу або сильні завади). Обмежене значення

(12а)

спостерігається у тому випадку, коли завад в каналі немає H(U/Z) = H(Z/U) = 0. При цьому H(U) = H(Z) = I(U, Z), якщо врахувати, що при заданому M,

(див. властивість 2 ентропії). Таким чином, пропускна спроможність дискретного каналу без шуму визначається рівністю (12а), а за наявності шуму

. (12б)

Термін “без пам'яті” означає, що імовірність помилки в каналі не залежить від того, які символи передавалися раніше і як вони були прийняті. Відповідно до (13а) біт на символ.

Неважко показати, що відповідно до (1.38) і (13) маємо

(13а),

отже

.

У правій частині (13) та, відповідно до даного рівняння, від P(U) залежить тільки H(Z), отже слід мінімізувати тільки її. Відповідно до другої властивості ентропії, максимальне значення , і реалізується воно тоді, коли всі прийняті сигнали Z_j є рівноімовірними і незалежними. Легко переконатися, що ця умова виконується, коли , тоді

.

Відповідно до (13) при кожному значенні j для один з доданків цієї суми при j = k дорівнює , а всі інші . При цьому

і

(14).

Звідси пропускна спроможність каналу

(14а).

Для двійкового симетричного каналу N = 2 і (14а) приймає вигляд

(15).

Залежність, , побудована відповідно до (15), показана на рисунку 9.



Рис. 3. Залежність С/v = f (P)

При P = 0,5 пропускна спроможність двійкового каналу C = 0 оскільки при такій імовірності помилки вихідну послідовність двійкових символів можна одержати, зовсім не передаючи сигналу по каналу, а вибираючи їх навмання, тобто при P = 0,5 послідовності на вході і виході є незалежними (обрив каналу). Те, що пропускна спроможність при P = 1 в двійковому каналі така ж, що і при P = 0 (канал без шумів) пояснюється тим, що при P = 1 достатньо всі вихідні символи інвертувати, щоб правильно відновити початковий сигнал.

Узгодження дискретного джерела з дискретним каналом. Ефективне або статистичне кодування

Припустимо, що ми маємо дискретний канал, імовірність виникнення помилки в якому є близькою до нуля (у ідеалі = 0). Такий канал називають ідеальним каналом або каналом без шуму. Відповідно до (13а) пропускна спроможність каналу визначається

.

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

Рис. 4. Схема побудови системи передачі інформації

Склад цієї системи обумовлений наступними обставинами. Як мовилося вище, для того, щоб швидкість передачі інформації у каналі дорівнювала його пропускній спроможності, на вході каналу повинне діяти дискретне джерело з певними статистичними властивостями, які максимізують величину I(Z,Z*). Зокрема, у випадку ідеального каналу без завад, що цікавить нас тут, таке джерело повинно мати максимальну ентропію або нульову надлишковість, тобто видавати незалежні рівно імовірні повідомлення. У той же час, своєю постановки задачі, ми зажадали мати змогу передавати повідомлення від довільного джерела з будь-якими статистичними властивостями, тобто від такого, що має ненульову надмірність. Таким чином виникає необхідність використання кодера (а так само декодера, що виконує зворотні йому операції) з функціями узгодження в статичному значенні повідомлень джерела зі входом каналу. Задача цього узгодження зрештою зводиться до усунення надмірності повідомлень. Кодер здійснює кодування повідомлень, тобто кожному дискретному повідомленню за певним правилом ставлять у відповідність послідовність символів з алфавіту об'ємом М. При цьому по відношенню до входу каналу видані кодером символи самі є дискретними елементами повідомлень, статичні властивості яких повинні відрізнятися від статичних властивостей повідомлень початкового джерела.

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

H_в(U)= _C ·H(U) = _K·log M = С, (16)

звідки маємо

= _С = H(U)/ log M, (16а)

де H(U) ентропія джерела переданих повідомлень, _К і _С середні кількості символів відповідно повідомлення і коду переданих в одиницю часу; = _КС середня кількість символів коду, що доводяться на одне повідомлення.

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

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

пам'яттю джерела;

нерівномірністю повідомлень.

Універсальним способом зменшення надлишковості, яка обумовлена пам'яттю джерела, є укрупнення елементарних повідомлень. При цьому кодування здійснюється довгими блоками базовими кодовими словами. Зв'язки імовірності між блоками є меншими ніж між окремими елементами повідомлень і, чим довшими є блоки, тим меншою є залежність між ними. Значення укрупнення пояснимо на прикладі буквеного тексту: якщо зв'язки імовірності між буквами в будь-якій мові відносно сильні, то між словами вони значно менше, ще менше між фразами, ще менше між абзацами. Тому, застосовуючи кодування слів, фраз, абзаців ми можемо достатньо повно усунути надмірність обумовлену зв'язками імовірності. Проте при цьому зростає затримка передачі повідомлень, оскільки спочатку потрібно дочекатися формування всього довгого блоку повідомлень і лише потім його закодувати і передавати. Зменшення надмірності, яке є обумовленим нерівномірністю повідомлень, може бути досягнутим завдяки застосуванню нерівномірних кодів. Основна ідея побудови таких кодів полягає у тому, що найімовірнішим повідомленням ставляться у відповідність найкоротші блоки кодових символів (кодові комбінації), а якнайменше імовірно довшим. Через нерівномірність таких кодів і випадкового характеру повідомлення U передача без втрат інформації з постійною швидкістю проходження кодових символів K може бути забезпечено лише за наявності буферного накопичувача з великою пам'яттю, і, отже, при допустимості великих затримок.