Кількісна оцінка ІНФОРМАЦІЇ

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

. (1)

Невизначеність, що припадає на символ первинного (кодованого) [1] алфавіту, складеного з равновероятностних і взаімонезавісімих символів,

. (2)

Основа логарифма впливає лише на зручність обчислення. У разі оцінки ентропії:

а) в двійкових одиницях

б) у десяткових одиницях

де ;

в) у натуральних одиницях

де

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

(3)

Для випадків равновероятностних і взаімонензавісімих символів первинного алфавіту кількість інформації в повідомленнях до алфавіту m одно

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

(5)

Для неравновероятностних алфавітів ентропія на символ алфавіту

(4)

При вирішенні задач, в яких ентропія обчислюється як сума добутків ймовірностей на їх логарифм, незалежно від того, чи є вони безумовними , умовними < img src = "http://localhost/uploads/posts/2009-10/1255895824_Lekcii_po_kolichestvennoiy_ocenke_informacii_12.gif" alt = "" width = "64" height = "25" /> або ймовірностями спільних подій .

Кількість інформації визначається виключно характеристиками первинного алфавіту, обсяг - характеристиками вторинного алфавіту. Обсяг [2] інформації

(6)

де lср - середня довжина кодових слів вторинного алфавіту. Для рівномірних кодів (всі комбінації коду містять однакову кількість розрядів)

де n - довжина коду (число елементарних посилок в коді). Згідно (3), обсяг дорівнює кількості інформації, якщо lср = Н, тобто у випадку максимальної інформаційної навантаження на символ повідомлення. У всіх інших випадках .

Наприклад, якщо кодувати в коді Бодо деякі рівноймовірно алфавіт, що складається з 32 символів, то

Якщо закодувати в коді Бодо російська 32-літерний алфавіт, то без урахування кореляції між літерами кількість інформації

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

Тема 2. Умовна ентропія та ентропія об'єднання

Поняття умовної ентропії у теорії інформації використовується при визначенні взаємозалежності [3] між символами кодованого алфавіту, для визначення втрат при передачі інформації з каналів зв'язку, при обчисленні ентропії об'єднання.

У всіх випадках при обчисленні умовної ентропії в тому чи іншому вигляді використовуються умовні ймовірності.

Якщо при передачі n повідомлень символ А з'явився m раз, символ У з'явився l разів, а символ А разом із символом В - к разів, то ймовірність появи символу А ; ймовірність появи символу В ; ймовірність спільного появи символів А і В ; умовна ймовірність появи символу А щодо символу В і умовна ймовірність появи символу У відносно символу А

(7)

Якщо відома умовна ймовірність, то можна легко визначити і ймовірність спільного появи символів А і В, використовуючи вирази (7)

(8)

Від класичного вираження (4) формула умовної ентропії відрізняється тим, що в ній ймовірності - умовні:

(9)

(10)

де індекс i обраний для характеристики довільного стану джерела повідомлення А, індекс j обраний для характеристики довільного стану адресата В.

Розрізняють поняття приватної і загальної умовної ентропії. Вираз (9) та (10) представляють собою приватні умовні ентропії.

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

(11)

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

Так як є імовірність спільного появи двох подій , то формула (11) можна записати наступним чином :

(12)

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

У загальному випадку, якщо ми передаємо m сигналів А і очікуємо отримати m сигналів, вплив перешкод у каналі зв'язку повністю описується канальної матрицею, яку ми наводимо нижче:

       У   А            b1 b2 ... bj ... bm             а1   а2   ...   АI   ...   

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

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

(13)

(14)

(15)

(16)

       У   А            b1 b2 ... bj ... bm             а1   а2   ...   АI   ...   

аm            ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..        ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...          

(17)

(18)

(19)

тема 3. Обчислення інформаційних втрат при передачі повідомлень по каналах зв'язку з шумами

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

Якщо перешкод немає або їх рівень настільки низький, що вони не в змозі знищити сигнал або імітувати корисний сигнал під час відсутності передачі, то при передачі ми будемо твердо впевнені, що отримаємо -- сигнал, відповідний переданому ai-му сигналу. Події А і В статистично жорстко пов'язані, умовна ймовірність максимальна, а умовна ентропія

!!!! 1

так як !!!!. У цьому випадку кількість інформації, що міститься в прийнятому ансамблі повідомлень В, так само ентропії переданих повідомлень ансамблю А, тобто I (В, А) = Н (А).

При високому рівні перешкод будь-який з прийнятих сигналів bj може відповідати будь-якого прийнятого сигналу ai, статистичний зв'язок між переданими та прийнятими сигналами відсутній. У цьому випадку ймовірності !!!!!! Є ймовірність незалежних подій і !!!!!!

!!!! 1

так як!! 11, тобто умовна ентропія дорівнює безумовній, а кількість інформації, що міститься в В, щодо А одно нулю:

!!!!

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

!!!!!

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

!!!! 1

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

!! 1!

а з використанням умовної ентропії

!!!

Для обчислення середньої кількості інформації, що міститься в прийнятому ансамблі повідомлень У відносно переданого ансамблю повідомлень А в умовах дії перешкод, користуються такими виразами, виведеними безпосередньо з виразу (25):

!!!!!!!!

Для обчислення часто зручно застосовувати вирази (26-28) у вигляді

!!!!!!!

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

!!!!!!!

Знаючи умовні і безумовні ймовірності, можна знайти Н (А), Н (В), Н (А/В) і Н (В/А).

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

ТЕМА 5. ВИЗНАЧЕННЯ НАДЛИШКОВОГО ПОВІДОМЛЕНЬ. ОПТИМАЛЬНЕ КОДУВАННЯ

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

Для визначення кількості «зайвої» інформації, яка закладена в структурі алфавіту або в природі коду, вводиться поняття надмірності. Надмірність, з якою ми маємо справу в теорії інформації, не залежить від змісту повідомлення і зазвичай заздалегідь відома зі статистичних даних [4]. Інформаційна надмірність показує відносну недовантаженими на символ алфавіту і є безрозмірною величиною:

(45)

де - коефіцієнт стиснення (відносна ентропія) . і беруться щодо одного і того ж алфавіту.

Крім загального поняття надмірності існують приватні види надмірності.

Надмірність, обумовлена неравновероятним розподілом символів у повідомленні,

(46)

Надмірність, викликана статистичної зв'язком між символами повідомлення,

(47)

Повна інформаційна надмірність

(48)

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

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

Фактично для передачі повідомлення достатньо мати довжину кодової комбінації

,

де N - загальна кількість переданих повідомлень.

L можна представити і як

,

де і -відповідно якісні ознаки первинного та вторинного алфавітів. Тому для цифри 5 у двійковому коді можна записати

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

де - округлене до найближчого цілого числа значення . Для нашого прикладу

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

Інформаційна надмірність - звичайно явище природне, закладена вона в первинному алфавіті. Коригуюча надмірність -- явище штучне, закладена вона у кодах , представлених у вторинному алфавіті.

Найбільш ефективним способом зменшення збитковості повідомлення є побудова оптимальних кодів.

Оптимальні коди [5] - коди з практично нульовою надмірністю. Оптимальні коди мають мінімальну середню довжину кодових слів - L. Верхня та нижня межі L визначаються з нерівності

(49)

де Н - ентропія первинного алфавіту, т - число якісних ознак вторинного алфавіту.

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

(50)

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

(51)

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

Суть блокового кодування можна з'ясувати на прикладі подання десяткових цифр у двійковому коді. Так, при передачі цифри 9 в двійковому коді необхідно затратити 4 символу, тобто 1001. Для передачі цифри 99 при політерний кодуванні - 8, при поблочно - 7, так як 7 двійкових знаків достатньо для передачі будь-якої цифри від 0 до 123; при передачі цифри 999 співвідношення буде 12 - 10, при передачі цифри 9999 співвідношення буде 16 - 13 і т. д. В загальному випадку «вигода» блокового кодування виходить і за рахунок того, що в блоках відбувається вирівнювання ймовірностей окремих символів, що веде до підвищення інформаційного навантаження на символ.

При побудові оптимальних кодів найбільшого поширення знайшли методики Шеннона-Фано і Хаффмена.

Згідно з методикою Шеннона - Фано побудова оптимального коду ансамблю з повідомлень зводиться до наступного:

1-й крок. Безліч з повідомлень розташовується в порядку убування ймовірностей.

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

3-й крок. Першій групі присвоюється символ 0, другої групи символ 1.

4-й крок. Кожну з освічених підгруп ділять на дві частини таким чином, щоб сумарні ймовірності новостворених підгруп були по можливості рівні.

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

Згідно з методикою Хаффмена, для побудови оптимального коду N символи первинного алфавіту виписуються в порядку убування ймовірностей. Останні символів, де [6] і - ціле число, об'єднують в деякий новий символ з імовірністю, яка дорівнює сумі ймовірностей об'єднаних символів Останні символи з урахуванням утвореного символу знову об'єднують, отримують новий, допоміжний символ, знову виписують символи в порядку убування ймовірностей з урахуванням допоміжного символу і т. д. до тих пір, поки сума ймовірностей т залишилися символів після -го виписування в порядку убування ймовірностей не дасть в сумі ймовірність, що дорівнює 1. На практиці звичайно, не роблять багаторазового виписування ймовірностей символів з урахуванням ймовірності допоміжного символу, а обходяться елементарними геометричними побудовами, суть яких зводиться до того, що символи кодованого алфавіту попарно об'єднуються в нові символи, починаючи з символів, що мають найменшу ймовірність. Потім з урахуванням новостворених символів, яким присвоюється значення сумарної імовірності двох попередніх, будують кодове дерево, у вершині якого стоїть символ з імовірністю 1. При цьому відпадає необхідність у впорядкування символів кодованого алфавіту в порядку убування ймовірностей.

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

Максимально ефективними будуть ті ОНК, у яких

Для двійкових кодів

(52)

так як log22 = 1. Очевидно, що рівність (52) задовольняється за умови, що довжина коду у вторинному алфавіті

Величина точно дорівнює Н, якщо , де п - будь-яке ціле число. Якщо й не є цілим числом для всіх значень літер первинного алфавіту, то і, згідно з основною теореми кодування [7], середня довжина кодового слова наближається до ентропії джерела повідомлень у міру укрупнення кодованих блоків.

Ефективність ОНК. оцінюють за допомогою коефіцієнта статистичного стиснення:

(53)

який характеризує зменшення кількості двійкових знаків на символ повідомлення при застосуванні ОНК у порівнянні із застосуванням методів нестатістіческого кодування і коефіцієнта відносної ефективності

(54)

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

Для найбільш загального випадку неравновероятних і взаімонезавісімих символів

Для випадку неравновероятних і взаємозалежних символів

ТЕМА 6. Виявлення і виправлення помилок У ПОВІДОМЛЕННЯХ Поняття про ідею корекції помилок

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

10110 - передана кодова комбінація;

10010 - 1-а прийнята комбінація;

10100 --а прийнята комбінація;

00110 - 3-я прийнята комбінація;

10110 - накопичена комбінація.

Як бачимо, незважаючи на те, що у всіх трьох прийнятих комбінаціях були помилки, накопичена не містить помилок [8].

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

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

(55)

де - число одиниць у кодовому слові. Якщо б не існувало умови постійного ваги, то кількість комбінацій коду могло б бути набагато більшою, а саме . Прикладом коду з постійним вагою може служити стандартний телеграфний код № 3 (див. додаток 4). Комбінації цього коду побудовані таким чином, що на 7 тактів, протягом яких повинна бути прийнята одна кодова комбінація, завжди припадають три струмові і чотири безтоковие посилки. Збільшення або зменшення кількості струмових посилок говорить про наявність помилки.

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

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

Коди без надмірності виявляти, а тим паче виправляти помилки не можуть [9]. Мінімальна кількість символів, в яких будь-які дві комбінації коду відрізняються один від одного, називається кодовою відстанню. Мінімальна кількість символів, в яких всі комбінації коду відрізняються один від одного, називається мінімальною кодовою відстанню. Мінімальна код?? ше відстань - параметр, визначає перешкодостійкість коду і закладену в коді надмірність. Мінімальним кодовою відстанню визначаються коригуючі властивості кодів.

У загальному випадку для виявлення r помилок мінімальна кодова відстань

(56)

Мінімальна кодова відстань, необхідне для одночасного виявлення та виправлення помилок,

(57)

де s - число виправляємо помилки.

Для кодів, тільки що виправляють помилки,

(58)

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

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

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

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

(59)

60)

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

. (61)

Для практичних розрахунків при визначенні числа контрольних розрядів кодів з мінімальною кодовою відстанню зручно користуватися виразами:

(62)

якщо відома довжина повної кодової комбінації п, і

(63)

якщо при розрахунках зручніше виходити з певної кількості інформаційних символів [10].

Для кодів, що виявляють все триразові помилки