Пространство на случайни събития
През 1946 г. американският статистик Джон Тюки предлага името BIT
Представете си пространство от случайни събитиякойто се състои от хвърляне на една фалшива монета, от двете страни на която е орел. Кога пада орел? Ясно е, че винаги. Ние знаем това предварително, защото нашето пространство е така уредено. Падането на орел е надеждно събитие, т.е. неговата вероятност е равна на 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-буквена азбука на руски езикезик (не се различава "е" и "е", както и "ъ" и "ь"). Ако всички букви се срещат в езика със същата вероятност, тогава ентропията на символ ще бъде H = 5 бита, но ако вземем предвид реалните честоти на символите, ентропията ще бъде по-малка: H = 4.35 бита. (Това е почти два пъти по-малко, отколкото при традиционното кодиране, когато знакът се предава като байт - 8 бита).
Но ентропията на характера в езика е още по-ниска. Вероятността за поява на следващия знак не е напълно предопределена от средната честота на знака във всички текстове. Кой символ ще последва зависи от вече пренесените знаци. Например, в съвременния руски език след символа "ъ" не може да се следва символа на съгласен звук. След две последователни гласни "е", третата гласна "е" следва изключително рядко, с изключение на думата "дълго гърло". Това означава, че следващият знак до известна степен е предопределен. Ако вземем под внимание такова предопределение на следващия символ, неопределеността (т.е. информацията) на следващия символ ще бъде дори по-малка от 4.35. Според някои оценки следващият знак на руски език е предопределен от структурата на езика с повече от 50%, т.е. при оптимално кодиране цялата информация може да бъде предадена чрез изтриване на половината от буквите от съобщението.
Друго нещо е, че не всяко писмо може да бъде прекършено безболезнено. Висока честота "о" (и обикновено гласни), например, е лесно да се зачеркне, но рядко "е" или "е" е доста проблематично.
Естественият език, на който общуваме помежду си, е силно излишен и следователно надежден; ако сме чули нещо неправилно, няма проблем, информацията пак ще бъде предадена.
Но докато Шанън не представи мярката за информация, не можахме да разберем, че езикът е излишен и до каква степен можем да компресираме съобщенията (и защо текстовите файлове са толкова добре компресирани от архиватора).
Излишък на естествен език
В статията "За това как ние vorpsimanie tektkt"(името звучи точно по този начин!) е взет фрагмент от романа „Благородно гнездо” на Иван Тургенев и е подложен на някаква трансформация: 34% от буквите са изтрити от фрагмента, но не и случайни. Първата и последната букви с думи бяха оставени, само гласните бяха зачертани, а не всички. Целта беше не само да се получи възможност да се възстанови цялата информация за преобразувания текст, но и да се гарантира, че лицето, което чете този текст, не изпитва никакви особени трудности поради липсващи букви.
Защо е сравнително лесно да се чете това повреденотекст? Той всъщност съдържа необходимата информация за възстановяване на цели думи. Говорителят на руски език има определен набор от събития (думи и цели изречения), които използва при разпознаване. Освен това говорещият има на разположение и стандартни езикови структури, които му помагат да възстанови информация. Например,"Тя е благ"- с голяма вероятност може да се чете като- Тя беше по-чувствителна.. Но взети отделно"Тя е още бла", по-скоро ще бъде възстановен като"Беше по-бяла". Тъй като в ежедневната комуникация се занимавамес канали, в които има шум и смущения, ние сме доста добри във възстановяването на информация, но само тази, която вече знаем предварително. Например фразата"Нейните черти не са ни най-малко приятни, хтиа нмго рспхли и пръски"чете добре с изключение на последната дума"Впръскване" - "събрано". Тази дума я няма в съвременния лексикон. При бързо четене на дума"Splls"чете се по-скоро като „слепени заедно“; когато е бавен, той просто обърква.
Сигнална дигитализация
Звук или акустични колебания е синусоида. Това може да се види например на екрана на звуковия редактор. За да предадете точно звука, ще ви е необходим безкраен брой стойности - цялата синусова вълна. Това е възможно с аналогова връзка. Той пее - слушайте, контактът не се прекъсва, докато песента продължава.
При цифровата комуникация по канал можем да предаваме само краен брой стойности. Това означава ли, че звукът не може да се възпроизведе точно? Оказва се, че не.
Различните звуци са различно модулирана синусоида.Предаваме само дискретни стойности (честоти и амплитуди), а синусоидната вълна не трябва да се предава - приемащото устройство може да я генерира.Той генерира синусоида и се наслагва върху неямодулация, създадена от стойности, предавани по комуникационен канал. Има точни принципи кои дискретни стойности трябва да се предават, така че звукът на входа на комуникационния канал да съвпада със звука на изхода, където тези стойности се наслагват върху някаква стандартна синусоида (това е теоремата на Котелников относно).
Теоремата на Котелников (в литературата на английски език - теоремата на Найквист - Шанън, теоремата за четене)- фундаментално твърдение в областта на цифровотообработка на сигнала, свързваща непрекъснати и дискретни сигнали и заявяваща, че „всяка функция F(t), състояща се от честоти от 0 до f1, може да бъде непрекъснато предавана с всякаква точност, като се използват числа, следващи едно след друго през 1/(2*f1) секунди
Кодиране срещу смущения. Кодове на Хеминг
Ако на ненадежден канал за предаванеКодираният текст на Иван Тургенев, макар и с някои грешки, ще доведе до доста смислен текст. Но ако трябва да прехвърлим всичко до малко, задачата ще бъде неразрешена: не знаем кои бита са грешни, защото грешката е случайна. Дори контролната сума не винаги спестява.
Ето защо днес при предаването на даннимрежите са склонни не толкова към оптимално кодиране, в което максималният обем информация може да бъде изтласкан в канала, а по-скоро до такова кодиране (очевидно излишно), в което грешките могат да бъдат възстановени - точно както когато четем думите в фрагмента на Иван Тургенев.
Има специални кодове за коригиране на грешки, които ви позволяват да възстановите информацията след повреда. Един от тях е кодът на Хемминг.Да приемем, че целият ни език се състои от три думи:111000, 001110, 100011. И източникът на съобщението, и получателят знаят тези думи. И знаем, че в комуникационния канал възникват грешки, но при предаване на една дума не се изкривява повече от един бит информация.
Да предположим, че първо предаваме думата 111000. В резултат на това не повече от една грешка (идентифицирахме грешката) може да се превърне в една от думите:
1) 111000,011,000, 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. Казват, че нашият код е фиксирал една грешка.
Корекцията се дължи на два фактора.Първо, получателят познава целия „речник“пространството на събитието на получателя на съобщението съвпада с пространството на този, който е предал съобщението. Когато кодът беше предаден само с една грешка, излезе дума, която не беше в речника.
Второ, думите в речника бяха избрани по специален начин.Дори ако възникне грешка, получателят не можебърка една дума с друга. Например, ако речникът се състои от думите „дъщеря“, „точка“, „подутина“ и по време на предаването резултатът е „вочка“, тогава получателят, знаейки, че такава дума не съществува, няма да може коригирайте грешката - всяка от трите думи може да се окаже вярна. Ако в речника има „точка“, „галка“, „клон“ и знаем, че не е разрешена повече от една грешка, то „вочка“ определено е „точка“, а не „галка“. В кодовете за коригиране на грешки думите са избрани точно така, че да бъдат „разпознаваеми“ дори след грешка. Единствената разлика е, че кодът „азбука“ има само две букви - нула и една.
Изобилието на такова кодиране е много голямо и броят на думите, които можем да предадем, е относително малък.Трябва да изключим всяка дума от речника,което в случай на грешка може да съвпадне с целия списък, съответстващ на предадените думи (например думите „дъщеря“ и „точка“ не могат да бъдат в речника). Но точното предаване на съобщения е толкова важно, че се изразходват големи усилия за изследване на устойчиви на грешки кодове.
сензация
Понятия за ентропия (или несигурност и. \ Tнепредсказуемост) на съобщението и излишъкът (или предопределеността и предвидимостта) съвсем естествено съответстват на нашите интуитивни идеи за измерване на информацията. Колкото по-непредсказуемо е посланието (колкото по-голяма е ентропията, толкова по-малка е вероятността), толкова повече информация носи. Сензацията (например среща с крокодил на Тверска) е рядко събитие, нейната предсказуемост е много ниска и следователно информационната стойност е висока. Често информацията се нарича новина - съобщения за току-що настъпили събития, за които все още не знаем нищо. Но ако ни кажат за втория и третия път за едни и същи думи, излишъкът на посланието ще бъде страхотен, неговата непредсказуемост ще падне до нула и ние просто няма да слушаме, махайки се от говорещия с думите "Знам, знам". Затова медиите се опитват толкова трудно да бъдат първите. Това съответствие с интуитивното чувство за новост, което поражда наистина неочаквани новини, изигра важна роля във факта, че статията на Шанън, която не е била предназначена за общия читател, се превръща в сензация, която пресата възприема като универсален ключ към познанието за природата. - от лингвисти и литературни критици до биолози.
НоИнформационна концепция на Шанън - строга математическа теорияи прилагането му извън теорията на комуникацията е много ненадеждно. Но в самата теория на комуникацията тя играе централна роля.
Семантична информация
Шанън, въвеждайки понятието ентропия като мяркаинформация, получиха възможност да работят с информация - преди всичко да я измерват и оценяват характеристики като капацитет на канала или оптимално кодиране. Но основното предположение, което позволи на Шанън да работи успешно с информация, беше предположението, че генерирането на информация е случаен процес, който може да бъде успешно описан от гледна точка на теорията на вероятностите.Ако процесът не е случаен, т.е. той се подчинява на законите (още повече, че не винаги е ясно, както се случва на естествен език), тогава разсъжденията на Шанън не са приложими за него.Нищо, което Шанън казва, няма нищо общо със смислеността на информацията.
Докато говорим за символи (или букви от азбуката),можем да спорим по отношение на случайни събития, но веднага щом стигнем до думите на езика, ситуацията ще се промени драстично. Речта е процес, който е специално организиран и тук структурата на съобщението е не по-малко важна от символите, с които се предава.
Съвсем наскоро изглеждаше, че не можем да направим нищо.направено, за да се доближи поне по някакъв начин до измерването на смислеността на текста, но през последните години ситуацията започна да се променя. И това се дължи преди всичко на прилагането на изкуствени невронни мрежи към задачите за машинен превод, автоматично обобщаване на текстове, извличане на информация от текстове и генериране на отчети на естествен език. Всички тези задачи включват трансформиране, кодиране и декодиране на значима информация, съдържаща се в естествен език. И постепенно се формира представа за загубите на информация по време на такива трансформации и следователно за степента на значима информация. Но днес яснотата и точността, които има информационната теория на Шанън, все още не са налице в тези трудни проблеми.