Біт, інформаційна ентропія Шеннона і код Хеммінга. Як виміряти будь-яку інформацію і передати її без втрат

Простір випадкових подій

У 1946 році американський вчений-статистик Джон Тьюки запропонував назву БІТ

(BIT, BInary digiT - «двійкове число» - «Хайтек»)- одне з головних понять XX століття. Тьюки обрав біт для позначення одного двійкового розряду, здатного приймати значення 0 або 1. Клод Шеннон у своїй програмній статті «Математична теорія зв'язку» запропонував вимірювати в бітах кількість інформації. Але це не єдине поняття, введене і досліджене Шенноном в його статті.

Уявімо собі простір випадкових подій,яке складається з кидання однієї фальшивої монети, на обох сторонах якої орел. Коли випадає орел? Ясно, що завжди. Це ми знаємо заздалегідь, оскільки так влаштовано наше простір. Випадання орла - достовірна подія, тобто його ймовірність дорівнює 1. Чи багато інформації ми повідомимо, якщо скажемо про випав орле? Ні. Кількість інформації в такому повідомленні ми будемо вважати рівним 0.

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

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

Якщо незалежно і одночасно кидати двімонети, то різних рівноймовірно результатів буде вже чотири: орел-орел, орел-решка, решка-орел і решка-решка. Щоб передати інформацію, нам знадобиться вже 2 біта, і наші повідомлення будуть такими: 00, 01, 10 і 11. Інформації стало в два рази більше. Це сталося, тому що виросла невизначеність. Якщо ми спробуємо вгадати результат такого парного кидання, то маємо в два рази більше шансів помилитися.

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

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

Нехай простір подій не така екзотична. Ми просто стоїмо біля вікна і дивимося на проїжджаючі машини. Повз проїжджають автомобілі чотирьох кольорів, про які нам необхідно повідомити. Для цього ми закодируем кольору: чорний - 00, білий - 01, червоний - 10, синій - 11. Щоб повідомити про те, який саме автомобіль проїхав, нам достатньо передати 2 біта інформації.

Але досить довго спостерігаючи за автомобілями,помічаємо, що колір автомобілів розподілено нерівномірно: чорних - 50% (кожен другий), білих - 25% (кожен четвертий), червоних і синіх - по 12,5% (кожен восьмий). Тоді можна оптимізувати передану інформацію.

Найбільше чорних автомобілів, томупозначимо чорний - 0 - найкоротший код, а код всіх інших нехай починається на 1. З решти половина білі - 10, а решту кольору починаються на 11. На закінчення позначимо червоний - 110, а синій - 111.

Тепер, передаючи інформацію про колір автомобілів, ми можемо закодувати її щільніше.

Ентропія по Шеннону

Нехай наш простір подій складається з nрізних подій. При киданні монети з двома орлами така подія рівно одне, при киданні однієї правильної монети - 2, при киданні двох монет або спостереженні за автомобілями - 4. Кожному події відповідає ймовірність його настання. При киданні монети з двома орлами подія (випадання орла) одне і його ймовірність p1 = 1. При киданні правильної монети подій два, вони різновірогідні і ймовірність кожного - 0,5: p1 = 0,5, p2 = 0,5. При киданні двох правильних монет подій чотири, всі вони різновірогідні і ймовірність кожного - 0,25: p1 = 0,25, p2 = 0,25, p3 = 0,25, p4 = 0,25. При спостереженні за автомобілями подій чотири, і вони мають різні ймовірності: чорний - 0,5, білий - 0,25, червоний - 0,125, синій - 0,125: p1 = 0,5, p2 = 0,25, p3 = 0,125, p4 = 0,125.

Це не випадковий збіг. Шеннон так підібрав ентропію (міру невизначеності в просторі подій), щоб виконувалися три умови:

  • 1Ентропія достовірної події, ймовірність якого 1, дорівнює 0.
  • Ентропія двох незалежних подій дорівнює сумі ентропій цих подій.
  • Ентропія максимальна, якщо всі події рівноймовірно.

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

Величина H грає центральну роль в теорії інформації як міра кількості інформації, можливості вибору і невизначеності.

Клод Шеннон

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

У 1948 році запропонував використовувати слово «біт»для позначення найменшої одиниці інформації. Він також продемонстрував, що введена ним ентропія еквівалентна мірі невизначеності інформації в переданому повідомленні. Статті Шеннона «Математична теорія зв'язку» і «Теорія зв'язку в секретних системах» вважаються основними для теорії інформації та криптографії.

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

Шеннон вніс ключовий внесок в теорію імовірнісних схем, теорію ігор, теорію автоматів і теорію систем управління - області наук, що входять в поняття «кібернетика».

кодування

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

Кодувати повідомлення можна нескінченним числом різних способів. Але Шеннон показав, що найкоротший код не може бути менше в бітах, ніж ентропія.

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

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

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

Повідомлення на природній мові

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

Самим частотним символом (тобто таким, якийнайчастіше зустрічається у всіх текстах, написаних російською мовою) є пробіл: з тисячі символів в середньому пробіл зустрічається 175 разів. Другим за частотою є символ «о» - 90, далі йдуть інші голосні: «е» (або «е» - ми їх розрізняти не будемо) - 72, «а» - 62, «і» - 62, і тільки далі зустрічається перший приголосний «т» - 53. А найрідкісніший «ф» - цей символ зустрічається лише двічі на тисячу знаків.

Будемо використовувати 31-буквений алфавіт російськогомови (в ньому не відрізняються «е» і «е», а також «ь» і «ь»). Якби всі букви зустрічалися в мові з однаковою ймовірністю, то ентропія на символ була б Н = 5 біт, але якщо ми врахуємо реальні частоти символів, то ентропія виявиться менше: Н = 4,35 біт. (Це майже в два рази менше, ніж при традиційному кодуванні, коли символ передається як байт - 8 біт).

Але ентропія символу в мові ще нижче. Імовірність появи наступного символу в повному обсязі зумовлена ​​середньою частотою символу в усіх текстах. Те, який символ буде, залежить від символів вже переданих. Наприклад, в сучасній російській мові після символу "ь" не може слідувати символ приголосного звуку. Після двох поспіль голосних "е" третій голосний «е» слід вкрай рідко, хіба тільки в слові «довгошиї». Тобто наступний символ в деякій мірі зумовлений. Якщо ми врахуємо таку зумовленість наступного символу, невизначеність (тобто інформація) наступного символу буде ще менше, ніж 4,35. За деякими оцінками, наступний символ в російській мові зумовлений структурою мови більш ніж на 50%, тобто при оптимальному кодуванні всю інформацію можна передати, викресливши половину букв у повідомленні.

Інша справа, що не всяку букву можна безболісно викреслити. Високочастотну «о» (і взагалі голосні), наприклад, викреслити легко, а ось рідкісні «ф» або «е» - досить проблематично.

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

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

Надмірність природної мови

У статті «Про те, як ми ворпсіманіем теcкт»(Назва звучить саме так!) Був узятий фрагмент роману Івана Тургенєва «Дворянське гніздо» і підданий деякого перетворення: з фрагмента було викреслено 34% букв, але не випадкових. Були залишені перші і останні букви в словах, викреслювалися тільки голосні, причому в повному обсязі. Метою було не просто отримати можливість відновити всю інформацію по перетвореному тексту, а й домогтися того, щоб людина, що читає цей текст, не відчував особливих труднощів через пропуски букв.

Чому порівняно легко читати цей зіпсованийтекст? У ньому дійсно міститься необхідна інформація для відновлення цілих слів. Носій російської мови в своєму розпорядженні певним набором подій (слів і цілих речень), які він використовує при розпізнаванні. Крім того, в розпорядженні носія ще й стандартні мовні конструкції, які допомагають йому відновлювати інформацію. наприклад, «Вона бла блее чвствтльна» - з високою ймовірністю можна прочитати як «Вона була більш чутлива». Але взята окремо фраза «Вона бла блее», Скоріше, буде відновлена ​​як «Вона була біліше». Оскільки ми в повсякденному спілкуванні маємо справуз каналами, в яких є шум і перешкоди, то досить добре вміємо відновлювати інформацію, але тільки ту, яку ми вже знаємо заздалегідь. Наприклад, фраза «Чрти її НЕ бли лшни пріятнсті, хтя нмнго рспхлі і спллсь» добре читається за винятком останнього слова «Спллсь» - «спливла». Цього слова немає в сучасному лексиконі. При швидкому читанні слово «Спллсь» читається швидше як «злиплися», при повільному - просто ставить в тупик.

Оцифровка сигналу

Звук, або акустичні коливання - це синусоїда. Це видно, наприклад, на екрані звукового редактора. Щоб точно передати звук, знадобиться нескінченну кількість значень - вся синусоїда. Це можливо при аналоговому з'єднанні. Він співає - ви слухаєте, контакт не переривається, поки триває пісня.

При цифрового зв'язку по каналу ми можемо передати тільки кінцеве кількість значень. Чи означає це, що звук не можна передати точно? Виявляється, немає.

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

Теорема Котельникова (в англомовній літературі - теорема Найквіста - Шеннона, теорема відліків) - фундаментальне твердження в області цифровоїобробки сигналів, що зв'язує безперервні і дискретні сигнали і з якого випливає, що «будь-яку функцію F (t), що складається з частот від 0 до f1, можна безперервно передавати з будь-якою точністю за допомогою чисел, що слідують один за одним через 1 / (2 * f1) секунд.

Завадостійке кодування. коди Хеммінга

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

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

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

Припустимо, ми спочатку передаємо слово 111000. У результаті не більше ніж однієї помилки (помилки ми виділили) воно може перетворитися в одне зі слів:

1) 111000, 011000, 101000, 110000, 111100, 111010, 111001.

При передачі слова 001110 може вийти кожне зі слів:

2) 001110, 101110, 011110, 000110, 001010, 001100, 001111.

Нарешті, для 100011 у нас може вийти на прийомі:

3) 100011, 000011, 110011, 101011, 100111 100001, 100010.

Зауважимо, що всі три списки попарно НЕперетинаються. Іншими словами, якщо на іншому кінці каналу зв'язку з'являється будь-яке слово зі списку 1, одержувач точно знає, що йому передавали саме слово 111000, а якщо з'являється будь-яке слово зі списку 2 - слово 001110, а зі списку 3 - слово 100011. У цьому випадку кажуть, що наш код виправив одну помилку.

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

По-друге, слова в словнику були підібрані особливим чином. Навіть при виникненні помилки одержувач не мігпереплутати одне слово з іншим. Наприклад, якщо словник складається зі слів «дочка», «точка», «купина», і при передачі виходило «вочка», то одержувач, знаючи, що такого слова не буває, виправити помилку не зміг би - будь-яка з трьох слів може виявитися правильним. Якщо ж в словник входять «точка», «галка», «гілка» і нам відомо, що допускається не більше однієї помилки, то «вочка» це явно «точка», а не «галка». У кодах, що виправляють помилки, слова вибираються саме так, щоб вони були «впізнавані» навіть після помилки. Різниця лише в тому, що в кодовому «алфавіті» всього дві літери - нуль і одиниця.

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

сенсація

Поняття ентропії (або невизначеності інепередбачуваності) повідомлення і надмірності (або зумовленості і передбачуваності) дуже природно відповідають нашим інтуїтивним уявленням про міру інформації. Чим більше непередбачувано повідомлення (тим більше його ентропія, тому що менша ймовірність), - тим більше інформації воно несе. Сенсація (наприклад, зустріч з крокодилом на Тверській) - рідкісна подія, його передбачуваність дуже мала, і тому велика інформаційна вартість. Часто інформацією називають новини - повідомлення про тільки що події, що відбулися, про які ми ще нічого не знаємо. Але якщо про те, що трапилося нам розкажуть другий і третій раз приблизно тими ж словами, надмірність повідомлення буде велика, його непередбачуваність впаде до нуля, і ми просто не будемо слухати, відмахуючись від оратора зі словами «Знаю, знаю». Тому ЗМІ так намагаються бути першими. Ось це відповідність інтуїтивного відчуття новизни, яке народжує дійсно несподівана звістка, і зіграло головну роль в тому, що стаття Шеннона, абсолютно не розрахована на масового читача, стала сенсацією, яку підхопила преса, яку прийняли як універсальний ключ до пізнання природи вчені найрізноманітніших спеціальностей - від лінгвістів і літературознавців до біологів.

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

семантична інформація

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

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

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