Лекція 04. Кількість інформації в повідомленнях
Курс “Теорія інформації та кодування”

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

Підхід ТІК до оцінювання кількості інформації
Інформаційна ємність повідомлень
Інформативність дискретних повідомлень
Інформативність безперервних повідомлень

4.1 Підхід ТІК до оцінювання кількості інформації

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

- структурний (інформаційна ємність повідомлень);
- статистичний (інформативність повідомлень);
- семантичний (сенс - змістовність, доцільність тощо) (рис.4.1).

Рисунок 4.1 Огляд підходів до вимірювання інформації

Основні риси цих напрямків наступні:
- інформаційна ємність повідомлення визначає, скільки інформації потенційно воно може нести. При цьому спираються на їх «габарити». Зокрема для дискретних повідомлень це кількість знаків та обсяг використовуваного алфавіту, а для безперервних — їх довжина в часі та максимальна частота відповідного спектру. Образно таке можна порівняти з ємністю «упаковки», в якій буде передаватися інформація;

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

- кількісна оцінка сенсу - предмет семантичного підходу. Умовно зміст можна порівняти із якістю змісту упаковки. Очевидно, що його оцінка залежить від підходів («смаків») і завдань одержувача. Втім, для деяких аспектів сенсу можливі об'єктивні кількісні оцінки. Наприклад, можна оцінити доцільність одержуваних відомостей через ймовірність досягнення мети. Або підрахувати ступінь істинності всього повідомлення, спираючись на міру істинності його окремих складових. Однак, такі підходи вочевидь не універсальні. В цілому ТІК не розглядає питання сенсу повідомлень.

Надалі ми зосередимось на розгляді саме інформаційної ємності та інформативності.

Контрольні запитання
1) Назвіть основні підходи до визначення кількості інформації. Поясніть образну аналогію із заповненням упаковки її вмістом.
2) Якими параметрами дискретних та безперервних повідомлень визначається їх інформаційна ємність.
3) Чому саме інформативність повідомлень можна пов'язувати із імовірностями використання їх елементів.
4) Чому структурний і статистичний підходи до вимірювання інформації широко використовуються, а семантичний підхід застосовується у виняткових випадках.


4.2 Інформаційна ємність повідомлень

Ємність дискретних повідомлень

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

Рисунок 4.2 Міри інформаційної ємності

Показникова міра оцінює максимальну кількість унікальних поєднань знаків в повідомленні QL= NL (тут назва міри походить від виду використаної математичної функції). Наприклад, розглянемо кодування чисел в десятковій системі. Тут запис числа цифрами можна трактувати як повідомлення. Зокрема, запис числа із трьох десяткових цифр (L=3, N=10) дозволяє закодувати Q3=103=1000 чисел (від 0 до 999), а у випадку із шістьма lдесятковими цифрами (L=6, N=10) Q6=106=1000000.

Такий підхід є досить універсальним: дійсно, для будь-якого алфавіту кожному поєднанню знаків можна привласнити індивідуальний сенс. Однак, при очевидній простоті і наочності показова міра має важливі недоліки: по-перше, при скільки-небудь значних довжинах повідомлень значення Q стають величезними і з ними незручно працювати; по-друге, тут відсутня важлива властивість повідомлень — так звана адитивність, а саме кількість інформації не пропорційна їх довжині (наприклад, два тризначних числа можуть мати кожне до 1000 значень, а їх об'єднання - число з шести цифр - може мати вже до 1000000 значень).

Логарифмічна міра дозволяє усунути згадані недоліки. Використаємо в якості міри інформації величину IL = logmNL = L logmN. Тут кількість інформації, яку може нести повідомлення, пропорційно його довжині (логарифмічна міра аддитивна), а порядок величин стає цілком доступним для огляду. Наприклад, при m=2 та досить великому значенні N = 65536, (що характерно, наприклад, для двухбайтного кодування звуку), величина IL = Lхlog265536 = Lх16). Отже, логарифмічна міра інформації досить зручна і компактна. На практиці застосовується саме вона.

Якщо величину QL можна було трактувати як максимально можливе число поєднань знаків у повідомленні, то значення IL визначає необхідну кількість розрядів для його кодування. Так, в розглянутому вище прикладі для повідомлення з L = 1000 знаків (наприклад, 1000 семплів звукового повідомлення) необхідно 1000х16=16000 двійкових розрядів. При цьому потрібно враховувати, що точна відповідність числу розрядів виходить тільки якщо обсяг алфавіту N кратний ступеню двійки. У разі, коли наприклад N = 10, отримаємо log2N≈3,3219. При цьому для повідомлення довжиною L = 1000 знаків знадобиться I = 3322 двійкових розрядів (з урахуванням округлення до цілого).

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

Рисунок 4.3 Інформаційна ємність безперервних повідомлень

Як ми знаємо, згідно теореми Котельнікова безперервну залежність можна точно відтворити по дискретним відлікам при частоті дискретизації fd = 2 fmax. Отже, при такій дискретизації інформація не втрачається і інформаційна ємність вихідного безперервного повідомлення u(t) тривалістю T є відповідною ємності послідовності відліків u(i) кількістю L=2fmaxT. При цьому інформаційна ємність послідовності відліків u(i) теоретично лишається нескінченною, оскільки кожне їх значення є безперервним. Втім величини u(i) одномірні замість двомірної для вихідної u(t). Тобто, як кажуть математики, потужність безперервної величини внаслідок дисретизації стає меншою.

Однак розрізняти значення безперервної величини, які відрізняються нескінченно мало, фізично неможливо. На практиці таке обмеження характеризується так званою роздільною здатністю. Формально їй може відповідати крок Δu між рівнями квантування u(i). Роздільна здатність разом із діапазоном Umax-Umin визначає потрібну кількість рівнів квантування N=(Umax-Umin)/Δu. Таким чином приходимо до практичної формули інформаційної ємності IL= 2fmaxх log2N, де кількість рівнів квантування N визначається роздільною здатністю та діапазоном зміни відповідної неперевної величини.

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

Рисунок 4.4 Одиниці виміру клькості інформації

Один біт - кількість інформації, що відповідає її елементарному кванту - бінарного вибору. Біт може мати одне з двох протилежних значень (в зв'язку з цим іноді говорять про «стать» біта - sex оf bit). Ці значення, зокрема, реалізуються як стани двійкового розряду коду (0 або 1). Стосовно повідомлень таке означає використання двійкового алфавіту. При цьому кількість інформації для одного двійкового знаку I(1) = logm2 = 1 досягається тільки при підставі логарифма m = 2. Таким чином, одиниця виміру біт передбачає саме використання підстави 2 при логарифмуванні.

Оскільки в принципі можливе використання в формулі для кількості інформації також інших підстав логарифму m, можуть існувати і альтернативні одиниці її вимірювання. Зокрема, m = 10 відповідає одиниця "діт", а m = e - "ніт". Це можна порівняти з використанням валют: та сама вартість при різних валютних курсах відповідатиме різній кількості грошових одиниць. Однак валюта "біти" (m = 2) займає унікальне положення, оскільки об'єктивно відповідає саме мінімальному кванту інформації. До того ж, як відомо, технічна реалізація двійкового коду є найбільш простою.

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

Контрольні запитання
1) Запишіть формули для визначення інформаційної ємності дискретних повідомлень із використанням показникової та логарифмічної форми.
2) Охарактеризуйте переваги логарифмічної форми вимірювання інформації, які визначають її переважне використання.
3) Чому після дискретизації безперервного повідомлення за часом його інформаційна ємність лишається теоретично безкінечною.
4) Які фізичні обмеження визначають практичну оцінку інформаційної ємності безперервних повідомлень.
5) Поясніть походження різних одиниць виміру кількості інформації. В чому унікальність одиниці біт.


4.3 Інформативність дискретних повідомлень

Модель дискретного джерела повідомлень
Для оцінювання інформативності дискретних повідомлень використовується модель так званого «дискретного джерела» рис.4.5.

Рисунок 4.5. Модель дискретного джерела повідомлень

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

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

- наявність імовірностей створює невизначеність при очікуванні будь-якого наступного знаку. Для розрахунку величини невизначеності використовується математична функція ентропії H, яка має розміність біт/знак (надалі ми детально розглянемо спосіб завдання та властивості такої функції). Коли черговий знак послідовності з'являється, невизначеність Н усувається і замість неї маємо інформацію кількістю I=H;

- найбільш простою і водночас корисною є так звана модель джерела «без пам'яті», де поява знаків вважається незалежною від передісторіі, а їх імовірності p1...pN - безумовними (відповідно ентропія тут також називається безумовною). Зокрема саме таку модель використав Клод Шеннон для своїх досліджень щодо інформативності повідомлень та їх ефективного кодування;

- більш повна модель джерела «із пам'яттю» враховує наявність зв'язків між сусідніми знаками в послідовності (дійсно, імовірності появи різних типів букв в тексті вочевидь будуть різнитись в залежності від попередніх букв). В цій моделі властивості джерела задаються так званими умовними імовірностями — наприклад pi/j (зокрема в такому запису відображена імовірність появи i-го знаку алфавіту за умовою, що попереднім був знак j-го типу). Кількість попередніх знаків, що враховуються, називають також «глибиною пам'яті» k джерела. Відповідно ентропія в цьому випадку також зветься умовною — H(k). Вочевидь при врахуванні більшої глибини передисторії ентропія (а разом з нею інформативність джерела) може зменшуватись. Як ми далі побачимо, це важливо враховувати при стисканні коду повідомлень.

Визначення безумовної ентропії
Розглянемо спосіб визначення безумовної ентропії, розрахунок якої базується на безумовних імовірностях появи знаків (рис.4.6).

Рисунок 4.6. Формула для визначення безумовної ентропії

Формула для розрахунку безумовної інформаційної ентропії (надалі просто ентропії) була запропонована Клодом Шенноном і має вигляд:
Н = - Σ pi log2 pi (i = 1 ... N) (4.1)

Тут ентропія H визначається як середньозважене значення невизначностей появи окремих типів знаків Нi = - log2pi (як “вагові” коефіцієнти виступають їх імовірності pi). При цьому знак «-» компенсує від'ємність логарифмів дробних величин.

Легко бачити, що із зменшенням імовірності знака розрахункова величина його інформативності зростає. Наприклад, можливостям 1/2, 1/4 і 1/8 будуть відповідати значення інформативності 1, 2 і 3 біт / знак (саме це потрібно від складових функції ентропії згідно підходу, де інформативність відповідає новізні та непрогнозованості).

Застосування логарифмів дозволяє узгодити статистичний та структурний підходи. Так в разі, коли ймовірності всіх N знаків алфавіту однакові (при цьому pi = 1/N), наведена формула ентропії дає значення інформативності Нi = - log2(1/N) = log2N. Тут значення інформативності знаків збігається з їх інформаційною ємністю.

Властивості функції ентропії
Загальні властивості функції безумовної ентропії безпосердньо витікають із її формули і відображають її сенс (зокрема ці властивості ілюструє рис.4.7):

Рисунок 4.7 Властивості безумовної ентропії

- значення функції не від'ємні (H>=0). Зокрема позитивні значення відповідають наявності невизначеності, а нульове — її відсутності;

- максимум функції ентропії (в загальному випадку Н=log2N, а для двійкового алфавіту на рис.4.7 Н=1) відповідає випадку, коли всі знаки однаково імовірні. Дійсно, в такому випадку немає підстав передбачати перевагу появи будь-якого знаку порівняно з іншими;

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

Суттєво, що зміна значень H при змінах розполілу імовірностей знаків є дуже нерівномірною: ентропія суттєво зменшується тільки коли якісь знаки сильно переважають інші в імовірності появи (приклади на рис.4.7).

Розрахунок умовної ентропії
Обчислення умовної ентропії виконується з урахуванням умовних ймовірностей появи знаків (рис.4.8):

Рисунок 4.8 Розрахунок умовної ентропії
- зокрема, якщо відомо, що черговому знаку передував знак j-го типу, то відповідна «частна» ентропія може бути обчислена за формулою:
Н(1)j = - Σ pi/j log2 pi/j (j = 1 ... N) (4.3)
де pi/j - умовні ймовірності появи всіх i-х знаків після заданого j-го.

Тепер, усреднюючи значення Н(1)j з урахуванням їх "ваги" (імовірностей знаків), отримаємо значення умовної ентропії з глибиною історії в один крок k=1:
Н(1) = - Σ pj Σ pi/j log2 pi/j (i = 1 ... N, j = 1 ... N) (4.4)

Наступна формула дозволяє обчислити значення умовної ентропії з глибиною історії k = 2:
Н(2) = - Σ pi Σ pj Σ pi/j,l log2 pi/j,l (i = 1 ... N, j = 1 ... N, l = 1 ... N) (4.5)

Аналогічно обчислюються значення ентропії і при великих значеннях k.
При цьому кожен крок збільшення глибини історії означає зростання мірності таблиці умовних імовірностей. Зокрема, при k = 1 ми будемо працювати з двовимірної таблицею розміром nxn = n2, при k = 2 - з тривимірною розміром n3 і т.д. (Рис.4.8). При цьому кожне значення умовної ймовірності потрібно підраховувати. Очевидно, що зростання громіздкості обчислень на практиці обмежує глибину обліку передісторії знаків.

Контрольні питання
1) Охарактеризуйте модель джерела дискретних повідомлень: якими параметрами задається джерело в моделі з пам'яттю та без пам'яті; що характеризує величина ентропії і як вона ентропія пов'язана із інформацією; в чому різняться безумовна та умовна ентропія.
2) Запишіть формулу безумовної ентропії. Поясніть її зв'язок з формулою невизначеності появи окремих знаків.
3) Назвіть основні властивості функції безумовної ентропії. Яке її максимальне значення, наприклад, при обсязі алфавіту джерела N = 32
4) Використвуючи рис.4.8, поясніть формули для розрахунку умовної ентропії для випадків глибини історії k=1 та k=2. Як може впливати збільшення глибини історії на значення ентропії того самого джерела повідомлень.


4.4 Інформативність безперервного джерела

Особливості безперервного джерела повідомлень

На відміну від моделі дискретного джерела, яке генерує послідовність знаків і відповідно описується ансамблем імовірностей їх появи, неперерне джерело може створювати будь-які значення величин. Отже і розподіл їх імовірностей повинен мати безперервний характер (рис.4.9).

Рисунок 4.9 Співставлення описів дискретного та безперервного джерела

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

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

Повна ентропія безперервного джерела
Розглянемо ентропію безперервного джерела по аналогії з дискретним — рис.4.10:

Рисунок 4.10 Повна ентропія безперервного джерела

- нехай функція щільності ймовірності f (u) квантується із кроком Δu. Тоді площа стовпчика Δu f (ui) відповідає ймовірності pi формула ентропії за аналогією набуде вигляду:
HΔu (U) = - Σ [Δu f (ui)] log2 [Δu f (ui)] (4.6);

- щоб коректно перейти від дискретних величин до безперервним, виконується граничний перехід при Δu → 0. Опис виведення винесено в необов'язкове доповнення *. Тут же наведемо кінцевий результат:
H (U) = - ∫ f (u) logi f (u) du - logi Δu (4.7)
Це і є формула ентропії безперервної величини, яку прийнято називати повною;

- перший доданок схоже на формулу ентропії дискретного джерела, в якій дискретні ймовірності pi замінені безперервною функцією щільності ймовірності f (u), а знак суми - інтегралом. При цьому інтеграл певний (в межах від Umin до Umax) і має кінцеве значення. Другий доданок спрямовується до нескінченності при Δu → 0. Це цілком логічно, оскільки невизначеність значень безперервної величини дійсно нескінченна. Але для практичних потреб бажано перейти до кінцевих величинам.

* Доповнення. З огляду на відоме правило, що логарифм добутку дорівнює сумі логарифмів співмножників, формулу (4.6) можна представити як суму двох складових:
HΔu (U) = - Σ [Δu f (ui)] {log2Δu + log2f (ui)} = - Σ [f (ui) log2f (ui)] Δu - log2Δu Σf (ui) Δu
Тепер, вважаючи, що Δu → 0, отримаємо:
- перший доданок
Σ [f (uі) log2 f (uі)] Δu ≈ ∫ f (u) log2 f (u) du;
- другий доданок
- log2Δu Σf (uі) Δu = - log2 Δu, оскільки Σ f (uі) Δu = ∫ f (u) du = 1.

Різностна ентропія
Для виключення нескінченності віднімемо від (4.7) останній доданок:
H * (U) = H (U) - (- log2 Δu) = - ∫ f (u) log2 f (u) du (4.8).

Отриману величину H * (U) називають різностною ентропією (використовується також термін відносна ентропія). Її зручно використовувати для зіставлення безперервних випадкових величин, які розрізняються своїми розподілами f (u).
Величину різностної ентропії H * (U) зручно інтерпретувати як відмінність повної ентропії розглянутої величини U від від ентропії -log2Δu деякої базової випадкової величини. Показано, що така базова величина повинна мати рівномірний розподіл в межах зміни u від 0 до 1.

Властивості різностної ентропії (РЕ) ілюструє рис.4.11:

Рисунок 4.11 Різностна ентропія

- РЕ може бути як позитивно, так і негативною. Дійсно, Н*(U) визначається по відношенню до ентропії величини, рівномірно розподіленим від 0 до 1. Але аналогічна величина, розподілена в більш вузькому діапазоні очевидно характеризується меншою невизначеністю;

- РЕ збільшується зі зростанням дисперсії величини U. Очевидно, що чим більше розкид значень випадкової величини, тим вище невизначеність. Додамо, що значення Н*(U) крім дисперсії залежить також від виду розподілу щільності ймовірностей f (u). Нижче ми розглянемо цей момент детальніше;

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

Важливі випадки розподілів з максимальною ентропією
Особливий інтерес представляють випадки розподілів, для яких величина ентропії при заданій дисперсії є максимальною (рис.4.12):

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

 - випадок 1. Якщо для безперервної випадкової величини фіксовані межі її діапазону, то максимальним буде значення ДЕ для рівномірного розподілу щільності ймовірності f(u). Такий варіант повністю аналогічний нагоди дискретного джерела;

- формула розрахунку величини H*(U) для рівномірного розподілу f(u) в діапазоні від a до b матиме вигляд:
H * (U) = -∫ [1 / (b-a)] log2 [1 / (b-a)] du = log2 (b-a) (4.9)
При цьому дисперсія визначається як D = σ2 = (b-a) 2/12;

- випадок 2. Якщо для безперервної випадкової величини обмежена її дисперсія, то максимальна ентропія буде у нормального (Гауссова) розподілу щільності ймовірності. Такий варіант характерний, зокрема, для передачі сигналів, для яких обмежується потужність (яка пропорційна дисперсії);

- формула для визначення РЕ також виводиться виходячи їх (4.9). В результаті виходить
 H * (U) = log2 √ (2πσ2e) (4.10)
(Тут e - константа Ейлера приблизно рівна 2,72);

- кількісне порівняння розглянутих випадків виконаємо на прикладі, коли значення РЕ H*(U) = 0. Тоді під знаком логарифма в обох формулах повинна бути 1. При цьому для рівномірного розподілу D = σ2 = 1/12 = 0,083 і σ = 0,289. Для нормального розподілу виходячи з (4.10) D = σ2 = 1/(2πe) = 0,058 і σ = 0,242. У разі нормального розподілу для досягнення того-ж значення H*(U) необхідна величина дисперсії в 0,083 / 0,058 = 1,42 рази менше, ніж при рівномірному розподілі. Така пропорція збережеться незалежно від заданої величини РЕ, оскільки вона визначається співвідношенням формул (4.9) і (4.10).

Контрольні питання
1) Як встановлюється відповідність між дискретним і безперервним підходами до визначення ентропії. Поясніть це за допомогою рис.4.9.
2) Запишіть підсумкову формулу для визначення ентропії безперервної величини. Чому вона дає нескінченне значення ентропії. Наскільки це відповідає інтуїтивним уявленням.
3) Поясніть поняття різностної ентропії і запишіть формулу для її визначення.
4) Сформулюйте і поясніть за допомогою рис.4.11 основні властивості різностної ентропії безперервного джерела
5) Запишіть формули різностної ентропії для рівномірного і нормального розподілів щільності ймовірності. Проілюструйте за допомогою цих формул основні властивості РЕ.
6) Використовуючи формули (4.9) і (4.10), розрахуйте пропорцію величини дисперсії для рівномірного і нормального розподілів для випадку, коли H * (U).
О дисциплине ТИК
Почему «Теория информации и кодирования» - одна из самых интересных дисциплин, которые изучают будущие системщики и защитники информации?

В ней сочетаются золотая классика и самая актуальная современность computer-science.

продолжение
О сайте
Здесь вы найдете материалы, которые помогут в изучении дисциплины “Теория информации и кодирования” (ТИК) в том виде, как она преподается на кафедре ЭВМ ДИИТа.

На сайте размещены методические материалы:
  • электронный конспект лекций;
  • методическое обеспечение к лабораторным работам;
  • полезные ссылки.

продолжение
© 2008-2019 • Теория информации и кодирования
UP