Spazio evento casuale
Nel 1946 lo statistico americano John Tukey propose il nome BIT
Immagina uno spazio di eventi casualiche consiste nel lanciare una moneta finta, su entrambi i lati è un'aquila. Quando cade un'aquila? È chiaro che sempre. Lo sappiamo in anticipo, perché il nostro spazio è così organizzato. La caduta di un'aquila è un evento affidabile, cioè la sua probabilità è uguale a 1. Daremo molte informazioni se diciamo di un'aquila caduta? No. La quantità di informazioni in tale messaggio, saremo considerati pari a 0.
Ora lanciamo la bella moneta:da un lato c'è testa e dall'altro croce, come dovrebbe essere. Testa o croce saranno due eventi diversi che compongono il nostro spazio di eventi casuali. Se riportiamo l'esito di un sorteggio, si tratterà effettivamente di nuove informazioni. Se esce testa, riporteremo 0, se croce è 1. Per riportare questa informazione, abbiamo bisogno solo di 1 bit.
Cosa è cambiato?L'incertezza è apparsa nel nostro spazio eventi. Abbiamo qualcosa da raccontare a qualcuno che non lancia nemmeno una moneta e non vede l’esito del lancio. Ma per comprendere correttamente il nostro messaggio, deve sapere esattamente cosa stiamo facendo e cosa significano gli 0 e gli 1.I nostri spazi per gli eventi devono corrispondere e il processo di decodifica è univoco per ripristinare il risultato del lancio.Se lo spazio degli eventi del trasmettitore e del ricevitore non coincide o non c'è possibilità di decodificazione univoca del messaggio, l'informazione rimarrà solo rumore nel canale di comunicazione.
Se ne lanci due indipendentemente e contemporaneamentemonete, allora ci saranno quattro diversi risultati ugualmente probabili: testa-testa, testa-croce, croce-testa e croce-croce. Per trasmettere informazioni avremo bisogno di 2 bit e i nostri messaggi saranno i seguenti: 00, 01, 10 e 11. Ci sono il doppio delle informazioni. Ciò è accaduto perché l’incertezza è aumentata. Se proviamo a indovinare il risultato di un simile lancio accoppiato, abbiamo il doppio delle possibilità di sbagliarci.
Maggiore è l'incertezza dello spazio degli eventi, maggiore è la quantità di informazioni contenute nel messaggio sul suo stato.
Complichiamo un po' il nostro spazio eventi.Finora tutti gli eventi accaduti sono stati ugualmente probabili. Ma negli spazi reali non tutti gli eventi hanno la stessa probabilità. Diciamo che la probabilità che il corvo che vediamo sia nero è vicina a 1. La probabilità che il primo passante che incontreremo per strada sia un uomo è circa 0,5. Ma incontrare un coccodrillo per le strade di Mosca è quasi impossibile. Intuitivamente, comprendiamo che un rapporto su un incontro con un coccodrillo ha un valore informativo molto maggiore rispetto a un corvo nero.Minore è la probabilità di un evento, maggiori sono le informazioni nel messaggio su un evento del genere.
Lascia che lo spazio dell'evento non sia così esotico. Restiamo alla finestra e guardiamo le macchine che passano. Passano le macchine di quattro colori, che dobbiamo segnalare. Per fare questo, codifichiamo i colori: nero - 00, bianco - 01, rosso - 10, blu - 11. Per riportare esattamente quale auto ha guidato, abbiamo solo bisogno di trasferire 2 bit di informazioni.
Ma per un bel po 'di tempo a guardare le macchine,notiamo che il colore delle auto è distribuito in modo non uniforme: nero - 50% (ogni secondo), bianco - 25% (ogni quarto), rosso e blu - 12,5% (ogni otto). Quindi è possibile ottimizzare le informazioni trasmesse.
La maggior parte delle auto sono nere, quindiindichiamo il nero - 0 - il codice più corto e lasciamo che il codice di tutto il resto inizi da 1. Della metà rimanente, il bianco - 10, e i colori rimanenti iniziano da 11. Infine, indichiamo il rosso - 110 e il blu - 111.
Ora, passando informazioni sul colore della macchina, possiamo codificarlo più da vicino.
Entropia di Shannon
Lasciamo che il nostro spazio eventi sia composto da neventi diversi. Quando si lancia una moneta con due teste si verifica esattamente uno di questi eventi, quando si lancia una moneta normale ce ne sono esattamente 2, quando si lanciano due monete o si guardano le automobili ce ne sono esattamente 4. Ogni evento ha una probabilità che si verifichi. Quando si lancia una moneta con due teste, si verifica un evento (che cade testa) e la sua probabilità è p1 = 1. Quando si lancia una moneta equilibrata, si verificano due eventi, sono ugualmente probabili e la probabilità di ciascuno è 0,5: p1 = 0,5, p2 = 0,5. Quando si lanciano due monete equilibrate, si verificano quattro eventi, tutti ugualmente probabili e la probabilità di ciascuno è 0,25: p1 = 0,25, p2 = 0,25, p3 = 0,25, p4 = 0,25. Quando si osservano le automobili, ci sono quattro eventi e hanno probabilità diverse: nero - 0,5, bianco - 0,25, rosso - 0,125, blu - 0,125: p1 = 0,5, p2 = 0,25, p3 = 0,125, p4 = 0,125.
Questa non è una coincidenza.Shannon ha scelto l'entropia (una misura di incertezza nello spazio degli eventi) in modo tale che siano state soddisfatte tre condizioni:
- 1L'entropia di un evento affidabile, la cui probabilità è 1, è uguale a 0.
- L'entropia di due eventi indipendenti è uguale alla somma delle entropie di questi eventi.
- L'entropia è massima se tutti gli eventi sono ugualmente probabili.
Tutti questi requisiti sono pienamente coerenti con il nsidee sull’incertezza dello spazio dell’evento. Se c'è un solo evento (il primo esempio), non c'è incertezza. Se gli eventi sono indipendenti – l'incertezza della somma è uguale alla somma delle incertezze – semplicemente si sommano (l'esempio del lancio di due monete). E infine, se tutti gli eventi sono ugualmente probabili, allora il grado di incertezza del sistema è massimo. Come nel caso del lancio di due monete, tutti e quattro gli eventi sono ugualmente probabili e l'entropia è 2, è maggiore che nel caso delle automobili, quando ci sono anche quattro eventi, ma hanno probabilità diverse - in questo caso l'entropia è 1,75.
La quantità H gioca un ruolo centrale nella teoria dell'informazione come misura dell'informazione, della scelta e dell'incertezza.
Claude Shannon
Claude Elwood Shannon- Ingegnere americano, crittoanalista ematematico. Considerato il "padre dell'era dell'informazione". Fondatore della teoria dell'informazione, che ha trovato applicazione nei moderni sistemi di comunicazione ad alta tecnologia. Forniti concetti fondamentali, idee e loro formulazioni matematiche che attualmente costituiscono la base per le moderne tecnologie di comunicazione.
Nel 1948, propose di usare la parola "bit"per indicare la più piccola unità di informazione. Ha anche dimostrato che l'entropia da lui immessa è equivalente all'incertezza dell'informazione nel messaggio trasmesso. Gli articoli di Shannon "Teoria della comunicazione matematica" e "Teoria della comunicazione nei sistemi segreti" sono considerati fondamentali per la teoria dell'informazione e la crittografia.
Durante la seconda guerra mondiale, Shannon lavorò ai Bell Laboratories per sviluppare sistemi crittografici, che in seguito lo aiutarono a scoprire metodi di codifica per la correzione degli errori.
Shannon ha dato un contributo chiave alla teoria degli schemi probabilistici, teoria dei giochi, teoria degli automi e teoria dei sistemi di controllo - aree della scienza che fanno parte del concetto di cibernetica.
codifica
E gettati monete, e le macchine di passaggio non lo sonosono simili ai numeri 0 e 1. Per segnalare eventi che si verificano negli spazi, è necessario pensare a un modo per descrivere questi eventi. Questa descrizione è chiamata codifica.
I messaggi possono essere codificati in un numero infinito di modi diversi. Ma Shannon ha dimostrato che il codice più corto non può essere più piccolo in bit dell’entropia.
Ecco perché l'entropia di un messaggio è una misurainformazioni nel messaggio. Poiché in tutti i casi considerati il numero di bit durante la codifica è pari all'entropia, ciò significa che la codifica è stata ottimale. Insomma, non è più possibile codificare messaggi sugli eventi dei nostri spazi.
Con una codifica ottimale, non puoi perdere odistorcere un singolo bit trasmesso nel messaggio. Se si perde anche un solo bit l'informazione risulterà distorta. Ma tutti i canali di comunicazione reali non forniscono la certezza al 100% che tutte le parti del messaggio raggiungeranno il destinatario senza distorsioni.
Per risolvere questo problema devi fareil codice non è ottimale, ma ridondante. Ad esempio, trasmetti insieme al messaggio il suo checksum, un valore appositamente calcolato ottenuto durante la conversione del codice del messaggio e che può essere verificato ricalcolando alla ricezione del messaggio. Se il checksum trasmesso corrisponde a quello calcolato, la probabilità che la trasmissione sia priva di errori sarà piuttosto elevata. E se il checksum non corrisponde, è necessario richiedere una ritrasmissione. Questo è più o meno il modo in cui funziona oggi la maggior parte dei canali di comunicazione, ad esempio quando si trasmettono pacchetti di informazioni su Internet.
Messaggi in linguaggio naturale
Considera lo spazio dell'evento che consisteda post in linguaggio naturale. Questo è un caso speciale, ma uno dei più importanti. Gli eventi qui saranno i caratteri trasmessi (lettere di un alfabeto fisso). Questi personaggi si trovano nella lingua con diverse probabilità.
Il simbolo più frequenza (ad esempio quelloè più spesso trovato in tutti i testi scritti in russo) è uno spazio: di mille caratteri, uno spazio medio si trova 175 volte. Il secondo in frequenza è il simbolo "o" - 90, seguito da altre vocali: "e" (o "e" - non li distingueremo) - 72, "a" - 62 e i - 62, e solo ulteriormente la prima consonante "t" - 53. E la "f" più rara - questo simbolo si trova solo il doppio per mille caratteri.
Useremo l'alfabeto di 31 lettere del russolingua (non differisce "e" ed "e", così come "ъ" e "ü"). Se tutte le lettere sono state incontrate nella lingua con la stessa probabilità, allora l'entropia per simbolo sarebbe H = 5 bit, ma se prendiamo in considerazione le frequenze reali dei simboli, l'entropia sarà inferiore: H = 4,35 bit. (Questo è quasi due volte inferiore rispetto alla codifica tradizionale, quando un carattere viene trasmesso come un byte - 8 bit).
Ma l'entropia del personaggio nella lingua è ancora più bassa. La probabilità di occorrenza del prossimo carattere non è completamente predeterminata dalla frequenza media del personaggio in tutti i testi. Quale personaggio seguirà dipende dai personaggi già trasferiti. Ad esempio, nel russo moderno dopo che il simbolo "ъ" non può seguire il suono del simbolo della consonante. Dopo due vocali consecutive "e", la terza vocale "e" segue estremamente raramente, a meno che nella parola "collo lungo". Cioè, il prossimo personaggio è in una certa misura predeterminato. Se prendiamo in considerazione tale predeterminazione del prossimo simbolo, l'incertezza (cioè l'informazione) del prossimo simbolo sarà ancora inferiore a 4.35. Secondo alcune stime, il seguente simbolo in russo è predeterminato dalla struttura della lingua di oltre il 50%, cioè con una codifica ottimale, tutte le informazioni possono essere trasmesse eliminando metà delle lettere dal messaggio.
Un'altra cosa è che non tutte le lettere possono essere cancellate in modo sicuro. La "o" ad alta frequenza (e generalmente le vocali), ad esempio, è facile da cancellare, ma la "f" o "e" rara è piuttosto problematica.
Il linguaggio naturale in cui comunichiamo tra di noi è altamente ridondante, e quindi affidabile, se abbiamo capito male qualcosa, va bene, l’informazione verrà comunque trasmessa;
Ma fino a quando Shannon ha introdotto la misura delle informazioni, non siamo riusciti a capire che il linguaggio è ridondante e in quale misura possiamo comprimere i messaggi (e perché i file di testo sono così ben compressi dall'archiver).
Ridondanza in linguaggio naturale
Nell'articolo "A proposito di come vorpsimanie tektkt"(il nome suona esattamente come questo!) un frammento del romanzo Noble Nest di Ivan Turgenev è stato preso e sottoposto a qualche trasformazione: il 34% delle lettere, ma non casuali, sono state eliminate dal frammento. La prima e l'ultima lettera in parole furono lasciate, solo le vocali furono cancellate, e non tutte. L'obiettivo non era solo quello di ottenere l'opportunità di recuperare tutte le informazioni sul testo convertito, ma anche di garantire che la persona che leggeva questo testo non avesse particolari difficoltà a causa della mancanza di lettere.
Perché è relativamente facile leggerlo corrottotesto? In realtà contiene le informazioni necessarie per ricostruire intere parole. Un madrelingua russo ha un certo insieme di eventi (parole e intere frasi) che usa per riconoscersi. Inoltre, il parlante ha a disposizione anche strutture linguistiche standard che lo aiutano a recuperare le informazioni. Per esempio,"Lei è blae blee"- con un'alta probabilità può essere letto come"Era più sensibile.". Ma presi separatamente"Lei è più bla", piuttosto, verrà ripristinato come"Era più bianca". Poiché nella comunicazione quotidiana ci occupiamocon i canali in cui sono presenti rumore e interferenze, siamo abbastanza bravi a ripristinare le informazioni, ma solo quelle che già conosciamo in anticipo. Ad esempio, la frase"Le sue caratteristiche non sono per niente piacevoli, htya nmngo rspkhli e splash"si legge bene tranne l'ultima parola"Splash" - "rallied". Questa parola non è nel lessico moderno. Quando si legge velocemente una parola"Splls"sembra più "attaccato insieme"; quando è lento, semplicemente sconcerta.
Digitalizzazione del segnale
Il suono, o oscillazioni acustiche, è una sinusoide. Questo può essere visto, ad esempio, sulla schermata dell'editor audio. Per trasmettere con precisione il suono, avrai bisogno di un numero infinito di valori - l'intera onda sinusoidale. Questo è possibile con una connessione analogica. Canta: tu ascolti, il contatto non si interrompe mentre la canzone dura.
Nella comunicazione digitale su un canale possiamo trasmettere solo un numero finito di valori. Ciò significa che il suono non può essere riprodotto accuratamente? Risulta no.
Suoni diversi sono un'onda sinusoidale modulata in modo diverso.Trasmettiamo solo valori discreti (frequenze e ampiezze) e l'onda sinusoidale non ha bisogno di essere trasmessa - il dispositivo ricevente può generarla.Genera una sinusoide e si sovrappone ad essamodulazione creata da valori trasmessi su un canale di comunicazione. Esistono principi esatti in base ai quali i valori discreti devono essere trasmessi in modo che il suono in ingresso al canale di comunicazione coincida con il suono in uscita, dove questi valori sono sovrapposti ad una sinusoide standard (questo è il teorema di Kotelnikov Di).
Teorema di Kotelnikov (nella letteratura in lingua inglese - il teorema di Nyquist - Shannon, il teorema della lettura)- una dichiarazione fondamentale nel campo del digitaleelaborazione del segnale, collegando segnali continui e discreti e affermando che “qualsiasi funzione F(t), costituita da frequenze da 0 a f1, può essere trasmessa continuamente con qualsiasi precisione utilizzando numeri che si susseguono per 1/(2*f1) secondi
Codifica anti-interferenza. Codici di Hamming
Se su un canale inaffidabile da trasmettereIl testo in codice di Ivan Turgenev, sebbene con alcuni errori, si tradurrà in un testo abbastanza significativo. Ma se abbiamo bisogno di trasferire tutto fino a un po ', il compito sarà irrisolto: non sappiamo quali bit siano sbagliati, perché l'errore è casuale. Anche il checksum non sempre salva.
Ecco perché oggi quando si trasmettono datile reti tendono non tanto alla codifica ottimale, in cui la quantità massima di informazioni può essere spinta nel canale, ma piuttosto a tale codifica (ovviamente ridondante) in cui gli errori possono essere recuperati - proprio come quando leggiamo le parole nel frammento di Ivan Turgenev.
Esistono speciali codici di correzione degli errori che consentono di recuperare le informazioni dopo un errore. Uno di questi è il codice di Hamming.Diciamo che tutta la nostra lingua è composta da tre parole:111000, 001110, 100011. Sia la fonte del messaggio che il destinatario conoscono queste parole. E sappiamo che si verificano errori in un canale di comunicazione, ma quando si trasmette una parola, non viene distorto più di un bit di informazione.
Supponiamo di prima passare la parola 111000. Di conseguenza, non più di un errore (abbiamo identificato l'errore) può trasformarsi in una delle parole:
1) 111000,011.000, 101000, 110000, 111100, 111010, 111001.
Quando si trasmette la parola 001110, qualsiasi parola può essere:
2) 001110,101110, 011110, 000110, 001010, 001100, 001111.
Infine, per il 100011 possiamo arrivare alla reception:
3) 100011,000011, 110011, 101011, 100111, 100001, 100010.
Nota che tutti e tre gli elenchi non sono a coppie.intersecano. In altre parole, se all'altra estremità del canale di comunicazione appare una parola dall'elenco 1, il destinatario sa per certo che la parola 111000 è stata trasmessa a lui, e se compare una parola dall'elenco 2, la parola 001110 e dalla lista 3, la parola 100011. In questo caso Dicono che il nostro codice ha corretto un errore.
La correzione è avvenuta a causa di due fattori.Innanzitutto, il destinatario conosce l'intero "dizionario", cioè lo spazio degli eventi del destinatario del messaggio coincide con lo spazio di colui che ha trasmesso il messaggio. Quando il codice è stato trasmesso con un solo errore, è uscita una parola, che non era nel dizionario.
In secondo luogo, le parole del dizionario sono state scelte in modo speciale.Anche se si verificasse un errore, il destinatario non potrebbe farloconfondere una parola con un'altra. Ad esempio, se il dizionario fosse composto dalle parole "figlia", "punto", "bump" e durante la trasmissione il risultato fosse "vochka", il destinatario, sapendo che tale parola non esiste, non sarebbe in grado di correggere l'errore: una qualsiasi delle tre parole potrebbe risultare corretta. Se il dizionario include “punto”, “daw”, “ramo” e sappiamo che non è consentito più di un errore, allora “vochka” è sicuramente un “punto” e non un “daw”. Nei codici di correzione degli errori le parole vengono scelte proprio in modo che siano “riconoscibili” anche dopo un errore. L'unica differenza è che il codice "alfabeto" ha solo due lettere: zero e uno.
La ridondanza di tale codifica è molto grande e il numero di parole che possiamo quindi trasmettere è relativamente piccolo.Dobbiamo escludere qualsiasi parola dal dizionario,che, in caso di errore, può coincidere con l'intero elenco corrispondente alle parole trasmesse (ad esempio, le parole “figlia” e “punto” non possono essere presenti nel dizionario). Ma la trasmissione accurata dei messaggi è così importante che vengono spesi grandi sforzi nella ricerca di codici resistenti agli errori.
sensazione
Concetti di entropia (o incertezza eimprevedibilità) del messaggio e la ridondanza (o predeterminazione e prevedibilità) corrispondono molto naturalmente alle nostre idee intuitive sulla misura delle informazioni. Più il messaggio è imprevedibile (maggiore è la sua entropia, perché c'è meno probabilità), più informazioni porta. Una sensazione (per esempio, un incontro con un coccodrillo su Tverskaya) è un evento raro, la sua prevedibilità è molto bassa e quindi il valore dell'informazione è alto. Spesso le informazioni si chiamano notizie - segnalazioni di eventi appena accaduti, su cui ancora non sappiamo nulla. Ma se ci raccontano la seconda e la terza volta delle stesse parole, la ridondanza del messaggio sarà grande, la sua imprevedibilità scenderà a zero, e semplicemente non ascolterò, sventolando dall'altoparlante con le parole "Lo so, lo so". Pertanto, i media stanno cercando così duramente di essere i primi. Questa corrispondenza con la sensazione intuitiva di novità, che dà origine a notizie davvero inaspettate, ha giocato un ruolo importante nel fatto che l'articolo di Shannon, che non era destinato al lettore generale, è diventato una sensazione, adottata dalla stampa, che gli scienziati di varie specialità hanno accettato come chiave universale per la conoscenza della natura - da linguisti e critici letterari a biologi.
MaConcetto di informazioni di Shannon - teoria matematica rigorosae la sua applicazione al di fuori della teoria della comunicazione è molto inaffidabile. Ma nella teoria della comunicazione stessa, gioca un ruolo centrale.
Informazioni semantiche
Shannon, introducendo il concetto di entropia come misurainformazioni, ho avuto l'opportunità di lavorare con le informazioni, prima di tutto misurarle e valutare caratteristiche come la capacità del canale o la codifica ottimale. Ma il presupposto principale che ha permesso a Shannon di operare con successo con le informazioni è stato il presupposto che la generazione di informazioni sia un processo casuale che può essere descritto con successo in termini di teoria della probabilità.Se il processo è non casuale, vale a dire, obbedisce alle leggi (inoltre, non è sempre chiaro, come accade nel linguaggio naturale), quindi il ragionamento di Shannon non è applicabile ad esso.Niente di quello che dice Shannon ha nulla a che fare con il fatto che l'informazione sia significativa.
Mentre stiamo parlando di personaggi (o lettere dell'alfabeto),possiamo ben argomentare in termini di eventi casuali, ma non appena arriveremo alle parole della lingua, la situazione cambierà drasticamente. Il linguaggio è un processo appositamente organizzato, e qui la struttura del messaggio non è meno importante dei caratteri con cui viene trasmessa.
Proprio di recente sembrava che non potessimo fare nulla.fatto per avvicinarsi almeno in qualche modo alla misurazione della significatività del testo, ma negli ultimi anni la situazione ha cominciato a cambiare. Ciò è dovuto principalmente all’applicazione delle reti neurali artificiali ai compiti di traduzione automatica, riepilogo automatico di testi, estrazione di informazioni dai testi e generazione di resoconti in linguaggio naturale. Tutti questi compiti implicano la trasformazione, la codifica e la decodifica delle informazioni significative contenute nel linguaggio naturale. E gradualmente si forma un'idea delle perdite di informazioni durante tali trasformazioni, e quindi della portata delle informazioni significative. Ma oggi la chiarezza e l’accuratezza della teoria dell’informazione di Shannon non sono ancora disponibili in questi difficili problemi.