Willekeurige evenementruimte
In 1946 stelde de Amerikaanse statisticus John Tukey de naam BIT voor
Stel je een ruimte voor van willekeurige gebeurtenissendie bestaat uit het gooien van een nepmedaille, aan beide zijden waarvan een adelaar is. Wanneer valt een adelaar? Het is duidelijk dat altijd. We weten dit van tevoren, omdat onze ruimte zo is ingericht. Het vallen van een adelaar is een betrouwbare gebeurtenis, dat wil zeggen, de waarschijnlijkheid is gelijk aan 1. Geven we veel informatie als we het hebben over een gevallen adelaar? Nee. De hoeveelheid informatie in zo'n bericht, zullen we als gelijk aan 0 worden beschouwd.
Laten we nu de eerlijke munt omdraaien:aan de ene kant zijn het koppen en aan de andere kant staarten, zoals het hoort. Het landen van kop of munt zal twee verschillende gebeurtenissen zijn die onze ruimte van willekeurige gebeurtenissen vormen. Als we de uitkomst van één worp melden, is dat inderdaad nieuwe informatie. Als er kop wordt gedropt, rapporteren we 0, en als de munt 1 is. Om deze informatie te rapporteren hebben we slechts 1 bit nodig.
Wat is er veranderd?Er is onzekerheid ontstaan in onze evenementenruimte. We hebben er iets over te vertellen aan iemand die zelf geen munt gooit en de uitkomst van de toss niet ziet. Maar om onze boodschap goed te begrijpen, moet hij precies weten wat we doen en wat de nullen en de enen betekenen.Onze evenementruimten moeten overeenkomen en het decoderingsproces is uniek om het resultaat van de worp te herstellen.Als de gebeurtenisruimte van zender en ontvanger niet samenvalt of er geen mogelijkheid is tot ondubbelzinnige decodering van het bericht, blijft de informatie alleen maar ruis in het communicatiekanaal.
Als je er twee onafhankelijk en tegelijkertijd gooitmunten, dan zullen er vier verschillende, even waarschijnlijke resultaten zijn: kop-kop, kop-munt, munt-kop en staart-staart. Om informatie te verzenden hebben we 2 bits nodig en onze berichten zijn als volgt: 00, 01, 10 en 11. Er is twee keer zoveel informatie. Dit gebeurde omdat de onzekerheid toenam. Als we de uitkomst van zo'n gepaarde worp proberen te raden, hebben we twee keer zoveel kans dat we het mis hebben.
Hoe groter de onzekerheid van de evenementenruimte, hoe meer informatie de boodschap over de toestand ervan bevat.
Laten we onze evenementenruimte een beetje ingewikkelder maken.Tot nu toe zijn alle gebeurtenissen die hebben plaatsgevonden even waarschijnlijk. Maar in echte ruimtes hebben niet alle gebeurtenissen dezelfde waarschijnlijkheid. Laten we zeggen dat de kans dat de kraai die we zien zwart zal zijn bijna 1 is. De kans dat de eerste voorbijganger die we op straat tegenkomen een man zal zijn, is ongeveer 0,5. Maar een krokodil tegenkomen in de straten van Moskou is bijna onmogelijk. Intuïtief begrijpen wij dat een reportage over een ontmoeting met een krokodil een veel grotere informatiewaarde heeft dan over een zwarte kraai.Hoe lager de kans op een gebeurtenis, hoe meer informatie in het bericht over een dergelijke gebeurtenis.
Laat de ruimte van het evenement niet zo exotisch zijn. We staan gewoon voor het raam en kijken naar de passerende auto's. Er komen auto's van vier kleuren voorbij, die we moeten melden. Om dit te doen, coderen we de kleuren: zwart - 00, wit - 01, rood - 10, blauw - 11. Om precies te melden welke auto reed, moeten we slechts 2 stukjes informatie overbrengen.
Maar al geruime tijd kijken naar de auto's,We merken op dat de kleur van auto's ongelijk verdeeld is: zwart - 50% (elke seconde), wit - 25% (elke vierde), rood en blauw - 12,5% (elke achtste) Vervolgens kunt u de verzonden informatie optimaliseren.
De meeste auto's zijn zwart, duslaten we zwart - 0 - de kortste code aanduiden, en laat de code van de rest beginnen bij 1. Van de resterende helft begint wit - 10, en de overige kleuren beginnen bij 11. Laten we ten slotte rood - 110 en blauw aanduiden - 111.
Als we nu informatie over de kleur van de auto doorgeven, kunnen we deze nauwkeuriger coderen.
Shannon Entropy
Laat onze evenementenruimte bestaan uit nverschillende evenementen. Bij het opgooien van een munt met twee koppen is er precies één zo'n gebeurtenis, bij het opgooien van één eerlijke munt zijn er precies 2, bij het opgooien van twee munten of het kijken naar auto's is er precies 4. Elke gebeurtenis heeft een waarschijnlijkheid dat deze plaatsvindt. Bij het gooien van een munt met twee kop is er één gebeurtenis (het vallen van de kop) en de kans is p1 = 1. Bij het gooien van een eerlijke munt zijn er twee gebeurtenissen, deze zijn even waarschijnlijk en de kans op beide is 0,5: p1 = 0,5, p2 = 0,5. Bij het gooien van twee eerlijke munten zijn er vier gebeurtenissen, ze zijn allemaal even waarschijnlijk en de waarschijnlijkheid van elk is 0,25: p1 = 0,25, p2 = 0,25, p3 = 0,25, p4 = 0,25. Bij het observeren van auto's zijn er vier gebeurtenissen en deze hebben verschillende kansen: zwart - 0,5, wit - 0,25, rood - 0,125, blauw - 0,125: p1 = 0,5, p2 = 0,25, p3 = 0,125, p4 = 0,125.
Dit is geen toeval.Shannon koos voor entropie (een maatstaf voor onzekerheid in de evenementruimte), zodat aan drie voorwaarden werd voldaan:
- 1De entropie van een betrouwbare gebeurtenis, waarvan de waarschijnlijkheid 1 is, is gelijk aan 0.
- De entropie van twee onafhankelijke evenementen is gelijk aan de som van de entropieën van deze evenementen.
- Entropie is maximaal als alle gebeurtenissen even waarschijnlijk zijn.
Все эти требования вполне соответствуют нашим представлениям о неопределенности пространства событий. Если событие одно (первый пример) — никакой неопределенности нет. Если события независимы — неопределенность суммы равна сумме неопределенностей — они просто складываются (пример с бросанием двух монет). И, наконец, если все события равновероятны, то степень неопределенности системы максимальна. Как в случае с бросанием двух монет, все четыре события равновероятны и энтропия равна 2, она больше, чем в случае с автомобилями, когда событий тоже четыре, но они имеют разную вероятность — в этом случае энтропия 1,75.
Величина H играет центральную роль в теории информации в качестве меры количества информации, возможности выбора и неопределенности.
Клод Шеннон
Claude Elwood Shannon — американский инженер, криптоаналитик и математик. Считается «отцом информационного века». Основатель теории информации, нашедшей применение в современных высокотехнологических системах связи. Предоставил фундаментальные понятия, идеи и их математические формулировки, которые в настоящее время формируют основу для современных коммуникационных технологий.
In 1948 stelde voor om het woord "bit" te gebruikenom de kleinste eenheid informatie aan te geven. Hij toonde ook aan dat de entropie die hij invoerde gelijk is aan de onzekerheid van de informatie in het uitgezonden bericht. Shannon's artikelen "Mathematische Theorie van Communicatie" en "Theorie van Communicatie in Geheime Systemen" worden beschouwd als fundamenteel voor informatietheorie en cryptografie.
Во время Второй мировой войны Шеннон в Bell Laboratories занимался разработкой криптографических систем, позже это помогло ему открыть методы кодирования с коррекцией ошибок.
Shannon leverde een belangrijke bijdrage aan de theorie van probabilistische schema's, speltheorie, automatentheorie en controlesysteemtheorie - wetenschapsgebieden die deel uitmaken van het concept van cybernetica.
codering
En gegooide munten en passerende auto's zijn dat nietzijn vergelijkbaar met de nummers 0 en 1. Om gebeurtenissen in ruimtes te rapporteren, moet u een manier bedenken om deze gebeurtenissen te beschrijven. Deze beschrijving wordt codering genoemd.
Кодировать сообщения можно бесконечным числом разных способов. Но Шеннон показал, что самый короткий код не может быть меньше в битах, чем энтропия.
Именно поэтому энтропия сообщения и есть мера информации в сообщении. Поскольку во всех рассмотренных случаях количество бит при кодировании равно энтропии, — значит кодирование прошло оптимально. Короче закодировать сообщения о событиях в наших пространствах уже нельзя.
При оптимальном кодировании нельзя потерять или исказить в сообщении ни одного передаваемого бита. Если хоть один бит потеряется, то исказится информация. А ведь все реальные каналы связи не дают 100-процентной уверенности, что все биты сообщения дойдут до получателя неискаженными.
Для устранения этой проблемы необходимо сделать код не оптимальным, а избыточным. Например, передавать вместе с сообщением его контрольную сумму — специальным образом вычисленное значение, получаемое при преобразовании кода сообщения, и которое можно проверить, пересчитав при получении сообщения. Если переданная контрольная сумма совпадет с вычисленной, вероятность того, что передача прошла без ошибок, будет довольно высока. А если контрольная сумма не совпадет, то необходимо запросить повторную передачу. Примерно так работает сегодня большинство каналов связи, например, при передаче пакетов информации по интернету.
Natuurlijke taalboodschappen
Overweeg de evenementruimte die bestaatvan berichten in natuurlijke taal. Dit is een speciaal geval, maar een van de belangrijkste. De gebeurtenissen hier zijn de uitgezonden tekens (letters van een vast alfabet). Deze tekens worden gevonden in de taal met verschillende waarschijnlijkheden.
Het meest frequentiesymbool (dat wil zeggen één datis het vaakst te vinden in alle teksten die in het Russisch zijn geschreven) is een spatie: duizend tekens, een gemiddelde ruimte wordt 175 keer gevonden. De tweede in frequentie is het symbool "o" - 90, gevolgd door andere klinkers: "e" (of "e" - we zullen ze niet onderscheiden) - 72, "a" - 62 en i - 62, en alleen verder de eerste medeklinker "t" - 53. En de zeldzaamste "f" - dit symbool wordt slechts tweemaal per duizend tekens gevonden.
We zullen het 31-letterige alfabet van het Russisch gebruikentaal (het verschilt niet "e" en "e", evenals "ъ" en "ь"). Als alle letters met dezelfde waarschijnlijkheid in de taal zouden worden aangetroffen, zou de entropie per symbool H = 5 bits zijn, maar als we rekening houden met de reële frequenties van de symbolen, zal de entropie minder zijn: H = 4,35 bits. (Dit is bijna twee keer minder dan bij traditionele codering, wanneer een karakter wordt uitgezonden als een byte - 8 bits).
Maar de entropie van het personage in de taal is nog lager. De waarschijnlijkheid van het voorkomen van het volgende teken wordt niet volledig vooraf bepaald door de gemiddelde frequentie van het teken in alle teksten. Welk teken volgt, hangt af van de personages die al zijn overgedragen. Bijvoorbeeld, in het moderne Russisch nadat het symbool "ъ" het medeklinkersymboolgeluid niet kan volgen. Na twee opeenvolgende klinkers "e" volgt de derde klinker "e" uiterst zelden, tenzij in het woord "long-necked". Dat wil zeggen dat het volgende karakter tot op zekere hoogte vooraf is bepaald. Als we rekening houden met zo'n vooraf bepaaldheid van het volgende symbool, zal de onzekerheid (dat wil zeggen de informatie) van het volgende symbool zelfs minder zijn dan 4.35. Volgens sommige schattingen is het volgende symbool in het Russisch met meer dan 50% vooraf bepaald door de structuur van de taal, dat wil zeggen dat bij optimale codering alle informatie kan worden overgedragen door de helft van de letters uit het bericht te verwijderen.
Een ander ding is dat niet elke letter veilig kan worden verwijderd. Hoogfrequente "o" (en in het algemeen klinkers) is bijvoorbeeld gemakkelijk door te strepen, maar zeldzame "f" of "e" is behoorlijk problematisch.
Естественный язык, на котором мы общаемся друг с другом, высоко избыточен, а потому надежен, если мы что-то недослышали — нестрашно, информация все равно будет передана.
Maar totdat Shannon de mate van informatie introduceerde, konden we niet begrijpen dat de taal overbodig is, en in welke mate we berichten kunnen comprimeren (en waarom tekstbestanden zo goed worden gecomprimeerd door de archiver).
Natuurlijke taal overtolligheid
In het artikel "Over hoe wij vorpsimanie tektkt"(de naam klinkt precies zo!) een fragment van Ivan Turgenev's Noble Nest-roman werd genomen en onderworpen aan enige transformatie: 34% van de letters, maar niet willekeurige, werden uit het fragment verwijderd. De eerste en laatste letters in woorden waren over, alleen klinkers werden verwijderd en niet allemaal. Het doel was niet alleen om de kans te krijgen om alle informatie over de geconverteerde tekst te herstellen, maar ook om ervoor te zorgen dat de persoon die deze tekst las, geen bijzondere problemen ondervond door het missen van brieven.
Почему сравнительно легко читать этот испорченный текст? В нем действительно содержится необходимая информация для восстановления целых слов. Носитель русского языка располагает определенным набором событий (слов и целых предложений), которые он использует при распознавании. Кроме того, в распоряжении носителя еще и стандартные языковые конструкции, которые помогают ему восстанавливать информацию. Например, "Ze is blae blee" — с высокой вероятностью можно прочесть как "Ze was gevoeliger.". Но взятая отдельно фраза "Ze is meer blas", скорее, будет восстановлена как "Ze was witter". Поскольку мы в повседневном общении имеем дело с каналами, в которых есть шум и помехи, то довольно хорошо умеем восстанавливать информацию, но только ту, которую мы уже знаем заранее. Например, фраза "Haar functies zijn niet in het minst prettig, htya nmngo rspkhli and splash" хорошо читается за исключением последнего слова "Splash" - "rally". Этого слова нет в современном лексиконе. При быстром чтении слово "Splls" читается скорее как «слиплись», при медленном — просто ставит в тупик.
Signaaldigitalisatie
Geluids- of akoestische oscillaties zijn een sinusoïde. Dit is bijvoorbeeld te zien op het geluidbewerkingsscherm. Om het geluid nauwkeurig over te brengen, hebt u een oneindig aantal waarden nodig - de hele sinusgolf. Dit is mogelijk met een analoge verbinding. Hij zingt - je luistert, het contact wordt niet onderbroken zolang het lied duurt.
При цифровой связи по каналу мы можем передать только конечное количество значений. Значит ли это, что звук нельзя передать точно? Оказывается, нет.
Разные звуки — это по-разному модулированная синусоида. We verzenden alleen discrete waarden (frequenties en amplitudes) en de sinusgolf zelf hoeft niet te worden verzonden - het ontvangende apparaat kan deze genereren. Он порождает синусоиду, и на нее накладывается модуляция, созданная по значениям, переданным по каналу связи. Существуют точные принципы, какие именно дискретные значения надо передавать, чтобы звук на входе в канал связи совпадал со звуком на выходе, где эти значения накладываются на некоторую стандартную синусоиду (об этом как раз теорема Котельникова).
Stelling van Kotelnikov (in Engelstalige literatuur - de Nyquist - Shannon-stelling, de leesstelling) — фундаментальное утверждение в области цифровой обработки сигналов, связывающее непрерывные и дискретные сигналы и гласящее, что «любую функцию F(t), состоящую из частот от 0 до f1, можно непрерывно передавать с любой точностью при помощи чисел, следующих друг за другом через 1/(2*f1) секунд.
Anti-interferentiecodering. Hamming codes
Als op een onbetrouwbaar kanaal om te verzendenIvan Turgenev's gecodeerde tekst, hoewel met een aantal fouten, zal resulteren in een redelijk betekenisvolle tekst. Maar als we alles tot een beetje moeten overdragen, is de taak niet opgelost: we weten niet welke stukjes fout zijn, omdat de fout willekeurig is. Zelfs de checksum bespaart niet altijd.
Dat is de reden waarom vandaag bij het verzenden van gegevens opnetwerken zijn niet zozeer gericht op optimale codering, waarbij de maximale hoeveelheid informatie in het kanaal kan worden gepusht, maar eerder op een dergelijke codering (overduidelijk overbodig) waarin fouten kunnen worden hersteld - net als wanneer we de woorden in het fragment van Ivan Turgenev lezen.
Er zijn speciale foutcorrectiecodes waarmee u informatie kunt herstellen na een fout. Een daarvan is de Hamming-code. Допустим, весь наш язык состоит из трех слов: 111000, 001110, 100011. Эти слова знают и источник сообщения, и приемник. И мы знаем, что в канале связи случаются ошибки, но при передаче одного слова искажается не более одного бита информации.
Stel dat we eerst het woord 111000 doorgeven. Als gevolg daarvan niet meer dan één fout (we hebben de fout geïdentificeerd) kan het in een van de woorden veranderen:
1) 111000, 011.000, 101000, 110000, 111100, 111010, 111001.
Bij het verzenden van het woord 001110, kan elk van de woorden worden verkregen:
2) 001110, 101110, 011110, 000110, 001010, 001100, 001111.
Eindelijk, voor 100011 kunnen we bij de receptie terecht:
3) 100011, 000011, 110011, 101011, 100111, 100001, 100010.
Merk op dat alle drie de lijsten niet paarsgewijs zijn.kruisen. Met andere woorden, als aan het andere einde van het communicatiekanaal een willekeurig woord uit lijst 1 verschijnt, weet de ontvanger zeker dat het woord 111000 aan hem is verzonden en verschijnt er een woord uit lijst 2, het woord 001110 en uit lijst 3 verschijnt het woord 100011. Ze zeggen dat onze code één fout heeft opgelost.
Исправление произошло за счет двух факторов. Ten eerste kent de ontvanger het volledige "woordenboek", d.w.z. de gebeurtenisruimte van de berichtontvanger valt samen met de ruimte van degene die het bericht heeft verzonden. Toen de code met slechts één fout werd verzonden, kwam er een woord uit dat niet in het woordenboek stond.
Ten tweede werden de woorden in het woordenboek op een speciale manier gekozen. Даже при возникновении ошибки получатель не мог перепутать одно слово с другим. Например, если словарь состоит из слов «дочка», «точка», «кочка», и при передаче получалось «вочка», то получатель, зная, что такого слова не бывает, исправить ошибку не смог бы — любое из трех слов может оказаться правильным. Если же в словарь входят «точка», «галка», «ветка» и нам известно, что допускается не больше одной ошибки, то «вочка» это заведомо «точка», а не «галка». В кодах, исправляющих ошибки, слова выбираются именно так, чтобы они были «узнаваемы» даже после ошибки. Разница лишь в том, что в кодовом «алфавите» всего две буквы — ноль и единица.
De redundantie van een dergelijke codering is erg groot en het aantal woorden dat we aldus kunnen overbrengen, is relatief klein. Нам ведь надо исключать из словаря любое слово, которое может при ошибке совпасть с целым списком, соответствующим передаваемым словам (например, в словаре не может быть слов «дочка» и «точка»). Но точная передача сообщения настолько важна, что на исследование помехоустойчивых кодов тратятся большие силы.
sensatie
Concepten van entropie (of onzekerheid enonvoorspelbaarheid) van het bericht en redundantie (of voorspelling en voorspelbaarheid) komen op natuurlijke wijze overeen met onze intuïtieve ideeën over de mate van informatie. Hoe onvoorspelbaarder het bericht (hoe groter de entropie, omdat er minder kans is), hoe meer informatie het bevat. Een sensatie (bijvoorbeeld een ontmoeting met een krokodil op Tverskaya) is een zeldzame gebeurtenis, de voorspelbaarheid ervan is erg laag en daarom is de informatiewaarde hoog. Vaak wordt informatie nieuws genoemd - rapporten van gebeurtenissen die zojuist zijn voorgekomen, waarover we nog steeds niets weten. Maar als ze ons over de tweede en derde keer vertellen over dezelfde woorden, zal de redundantie van de boodschap groot zijn, zal de onvoorspelbaarheid tot nul herleid worden en zullen we gewoon niet luisteren, zwaaiend weg van de spreker met de woorden "Ik weet het, ik weet het". Daarom proberen de media zo hard om de eerste te zijn. Deze correspondentie met het intuïtieve gevoel voor nieuwigheid, dat echt onverwacht nieuws oproept, speelde een grote rol in het feit dat het artikel van Shannon, dat niet bedoeld was voor de algemene lezer, een sensatie werd, die de pers oppikte als een universele sleutel tot kennis van de natuur. - van taalkundigen en literaire critici tot biologen.
Но Shannon-informatieconcept - strenge wiskundige theorieen de toepassing ervan buiten de communicatietheorie is zeer onbetrouwbaar. Maar in de theorie van de communicatie zelf speelt het een centrale rol.
Semantische informatie
Шеннон, введя понятие энтропии как меры информации, получил возможность работать с информацией — в первую очередь, ее измерять и оценивать такие характеристики, как пропускная способность каналов или оптимальность кодирования. Но главным допущением, которое позволило Шеннону успешно оперировать с информацией, было предположение, что порождение информации — это случайный процесс, который можно успешно описать в терминах теории вероятности. Als het proces niet-willekeurig is, dat wil zeggen, het voldoet aan de wetten (bovendien is het niet altijd duidelijk, zoals het gebeurt in de natuurlijke taal), dan is de redenering van Shannon daar niet op van toepassing. Все, что говорит Шеннон, никак не связано с осмысленностью информации.
Terwijl we het hebben over karakters (of letters van het alfabet),we kunnen goed argumenteren in termen van willekeurige gebeurtenissen, maar zodra we de woorden van de taal begrijpen, zal de situatie drastisch veranderen. Spraak is een proces dat speciaal is georganiseerd, en hier is de structuur van het bericht niet minder belangrijk dan de karakters waarmee het wordt uitgezonden.
Еще недавно казалось, что мы ничего не можем сделать, чтобы хоть как-то приблизиться к измерению осмысленности текста, но в последние годы ситуация начала меняться. И связано это прежде всего с применением искусственных нейронных сетей к задачам машинного перевода, автоматического реферирования текстов, извлечению информации из текстов, генерированию отчетов на естественном языке. Во всех этих задачах происходит преобразование, кодирование и декодирование осмысленной информации, заключенной в естественном языке. И постепенно складывается представление об информационных потерях при таких преобразованиях, а значит — о мере осмысленной информации. Но на сегодняшний день той четкости и точности, которую имеет шенноновская теория информации, в этих трудных задачах еще нет.