Lo stesso messaggio può essere codificato in modi diversi. Il codice più vantaggioso è quello che impiega il minor tempo nella trasmissione dei messaggi. Se la trasmissione di ogni elemento di un simbolo (ad esempio 0 o 1) richiede lo stesso tempo, il codice ottimale sarà tale che il numero minimo di simboli elementari sarà speso per trasmettere un messaggio di una determinata lunghezza. I codici Shannon - Fano sono prefissi, ad es. nessuna parola in codice è un prefisso di un'altra. Questa proprietà consente di decodificare in modo univoco qualsiasi sequenza di parole in codice
Consideriamo il principio di costruzione di uno dei primi algoritmi di compressione, che è stato formulato dagli scienziati americani Shannon e Fano usando l'esempio delle lettere dell'alfabeto russo. L'algoritmo utilizza codici di lunghezza variabile, ad es. un carattere comune è codificato con un codice di lunghezza più corta, uno raro - un codice più lungo.
Per comporre un tale codice, ovviamente, è necessario conoscere la frequenza di occorrenza delle lettere nel testo russo. Queste frequenze sono mostrate nella tabella 1. Le lettere nella tabella sono disposte in ordine decrescente di frequenza.
Tabella 1
Frequenza di comparsa delle lettere dell'alfabeto russo
Utilizzando la tabella è possibile comporre il codice più economico in base a considerazioni relative alle informazioni. Ovviamente il codice sarà più economico quando ogni simbolo elementare trasmetterà la massima informazione. Consideriamo un simbolo elementare (cioè che rappresenta il suo segnale) come un sistema fisico con due possibili stati: 0 e 1. L'informazione che questo simbolo fornisce è uguale all'entropia di questo sistema ed è massima nel caso in cui entrambi gli stati sono ugualmente probabili; in questo caso il simbolo elementare veicola l'informazione 1 (binaria). Pertanto, la base per una codifica ottimale sarà il requisito che i caratteri elementari nel testo codificato si presentino in media con la stessa frequenza.
L'idea della codifica è che i caratteri codificati (lettere o combinazioni di lettere) siano divisi in due gruppi approssimativamente ugualmente probabili: per il primo gruppo di caratteri, il primo posto della combinazione è 0 (il primo carattere del numero binario che rappresenta il personaggio); per il secondo gruppo - 1. Inoltre, ogni gruppo è nuovamente diviso in due sottogruppi approssimativamente ugualmente probabili; per i simboli del primo sottogruppo si mette 0 al secondo posto; per il secondo sottogruppo - uno, ecc.
Dimostriamo il principio della costruzione del codice Shannon-Fano usando l'esempio del materiale dell'alfabeto russo (vedi Tabella 1). Contiamo le prime sei lettere (da "-" a "t"); sommando le loro probabilità (frequenze), si ottiene 0,498; tutte le altre lettere da "n" a "f" avranno approssimativamente la stessa probabilità di 0,502. Le prime sei lettere (da "-" a "t") avranno in primo luogo il segno binario 0. Le restanti lettere (da "n" a "f") avranno in primo luogo 1. Inoltre, divideremo ancora il primo gruppo in due sottogruppi approssimativamente ugualmente probabili: da "-" a "o" e da "e" a "t"; per tutte le lettere del primo sottogruppo al secondo posto mettiamo zero e il secondo sottogruppo - uno. Il processo continuerà finché non rimarrà esattamente una lettera in ogni suddivisione, che sarà codificata con un certo numero binario. Il meccanismo di costruzione è mostrato nella tabella 2 e il codice stesso è mostrato nella tabella 3.
Tavolo 2
Il meccanismo per costruire il codice Shannon - Fano sull'esempio dell'alfabeto russo
| Segni binari | |||||||||
| Lettere | 1° | 2° | 3° | 4° | 5° | 6° | 7° | 8° | 9° |
| - | |||||||||
| oh | |||||||||
| e | |||||||||
| un | |||||||||
| e | |||||||||
| T | |||||||||
| n | |||||||||
| Con | |||||||||
| R | |||||||||
| v | |||||||||
| io | |||||||||
| a | |||||||||
| m | |||||||||
| D | |||||||||
| P | |||||||||
| in | |||||||||
| io sono | |||||||||
| S | |||||||||
| S | |||||||||
| b, b | |||||||||
| B | |||||||||
| G | |||||||||
| h | |||||||||
| questo | |||||||||
| X | |||||||||
| F | |||||||||
| Yu | |||||||||
| w | |||||||||
| C | |||||||||
| SCH | |||||||||
| eh | |||||||||
| F |
Tabella 3
Il risultato della codifica delle lettere dell'alfabeto russo con il codice Shannon - Fano
Esempio 4. Scriviamo la frase "metodo di codifica" utilizzando il codice Shannon - Fano.
Soluzione: Usiamo la tabella 3 e otteniamo il seguente risultato:
(1001) s (110011) n (001) o (1001) s (001) o (111010) b (000) spazio
(10111) a (001) o (110010) d (0110) e (10100) r (001) o (10101) c
(0101) a (1000) n (0110) e (110110) i
Si noti che non è necessario separare le lettere l'una dall'altra con un carattere speciale, poiché anche senza questa decodifica viene eseguita in modo univoco a causa della proprietà del prefisso: nessuna parola di codice più corta è l'inizio di una parola di codice più lunga. Infatti, la tabella 3 mostra che i più brevi sono i codici per i caratteri "spazio" e "o". In questo caso, nessun altro codice più lungo ha all'inizio della sequenza 000 ("spazio") e 001 ("o"). Lo stesso si può osservare per tutte le altre sequenze binarie del codice Shannon - Fano, che sono mostrate nella Tabella 3.
Va notato che qualsiasi errore di codifica (combinazione accidentale di 0 o 1 caratteri) con un tale codice è fatale, poiché la decodifica dell'intero testo successivo all'errore diventa impossibile.
Esempio 5. Determinare se il codice che abbiamo considerato è ottimale in assenza di errori?
Soluzione: Troviamo l'informazione media per un simbolo elementare (0 o 1) e confrontiamola con l'informazione massima possibile, che è uguale a uno. Per fare ciò, troviamo prima l'informazione media contenuta in una lettera del testo trasmesso, cioè l'entropia per lettera (vedi formula 8):
Secondo la tabella 1, determiniamo il numero medio di caratteri elementari per lettera:
Pertanto, le informazioni per carattere sono molto vicine al limite superiore di uno e questo codice è molto vicino all'ottimale.
In caso di utilizzo di un codice binario a cinque bit, informazioni per carattere:
Esempio 6. Lascia che un messaggio (una parola in russo) venga ricevuto tramite il canale di comunicazione codificato con il codice Shannon-Fano: 10111001110010010010100.
È necessario decodificare la sequenza data.
Soluzione: Il processo di decodifica si basa sulla proprietà del prefisso del codice e viene eseguito da sinistra a destra. La tabella 3 mostra che la lunghezza minima del codice è di tre bit. Conta tre bit dall'inizio della parola di codice ricevuta, otteniamo - 101. Non esiste un codice simile nella tabella, quindi aggiungiamo un altro bit, otteniamo - 1011. Anche questo codice non è nella tabella, quindi è necessario aggiungere un altro bit, otteniamo la combinazione - 10111, che corrisponde alla lettera "k". La codeword 10111 è esclusa dalla codeword ricevuta e viene sostituita dal simbolo originale (lettera "k"). Il processo di decodifica delle lettere rimanenti del messaggio ricevuto è simile.
Il processo di decodifica completo è mostrato nella Tabella 4. Il segno “-” nella tabella significa che il codice selezionato è assente nella Tabella 3.
Tabella 4
Processo di decodifica dei messaggi
| Sequenza codice ricevuta | ||||||||||||||||||||||
| - | ||||||||||||||||||||||
| - | ||||||||||||||||||||||
| a | ||||||||||||||||||||||
| a | oh | |||||||||||||||||||||
| a | oh | - | ||||||||||||||||||||
| a | oh | - | ||||||||||||||||||||
| a | oh | - | ||||||||||||||||||||
| a | oh | D | ||||||||||||||||||||
| a | oh | D | - | |||||||||||||||||||
| a | oh | D | e | |||||||||||||||||||
| a | oh | D | e | - | ||||||||||||||||||
| a | oh | D | e | - | ||||||||||||||||||
| a | oh | D | e | R |
Quindi, la parola ottenuta come risultato della decodifica della parola in codice ricevuta è "codificatore".
Il codice ottimale può essere determinato da quello in cui ogni carattere binario trasmetterà la massima informazione. In virtù delle formule di Hartley e Shannon, la massima entropia si ottiene con eventi equiprobabili, pertanto il codice binario sarà ottimale se i caratteri 0 e 1 ricorrono con uguale frequenza nel messaggio codificato.
Consideriamo come esempio la codifica binaria ottimale delle lettere dell'alfabeto russo insieme al carattere spazio "-". Riteniamo che le probabilità della comparsa dei simboli dell'alfabeto russo nel messaggio siano note, ad esempio quelle fornite nella tabella 3.
Tabella 3 Frequenza delle lettere della lingua russa (ipotesi)
K. Shannon e R. Fano proposero indipendentemente nel 1948-1949. un metodo per costruire un codice basato sul soddisfacimento della condizione di uguale probabilità dei simboli 0 e 1 in un messaggio codificato.
Tutti i caratteri codificati (lettere) sono divisi in due gruppi in modo che la somma delle probabilità dei caratteri del primo gruppo sia uguale alla somma delle probabilità dei caratteri del secondo gruppo (cioè la probabilità che il messaggio contenga un carattere del primo gruppo è uguale alla probabilità che il messaggio contenga un carattere del secondo gruppo).
Per i simboli del primo gruppo, il valore della prima cifra del codice è assegnato uguale a "0", per i simboli del secondo gruppo - uguale a "1".
Inoltre, ogni gruppo è diviso in due sottogruppi, in modo che le somme delle probabilità dei segni in ciascun sottogruppo siano uguali. Per i simboli del primo sottogruppo di ciascun gruppo, il valore della seconda cifra del codice è assegnato uguale a "0", per i simboli del secondo sottogruppo di ciascun gruppo - "1". Questo processo di divisione dei simboli in gruppi e codifica continua finché un simbolo rimane nei sottogruppi.
Un esempio di codifica dei caratteri dell'alfabeto russo è fornito nella tabella. 4
Tabella 4. Un esempio di codifica delle lettere dell'alfabeto russo utilizzando il codice Shannna-Fano.
L'analisi dei codici forniti nella tabella porta alla conclusione che i simboli ricorrenti sono codificati in sequenze binarie più brevi e quelle che si verificano raramente in quelle più lunghe. Ciò significa che, in media, per codificare un messaggio di una certa lunghezza, sono necessari meno simboli binari 0 e 1 rispetto a qualsiasi altro metodo di codifica.
Allo stesso tempo, la procedura per la costruzione del codice Shannon-Fano soddisfa il criterio di distinguibilità di Fano. Il codice è prefissato e non richiede un carattere speciale che separi le lettere l'una dall'altra per la decodifica univoca di un messaggio binario.
Pertanto, il problema della codifica a correzione di errori è una vasta area di ricerca teorica e applicata. I compiti principali in questo caso sono i seguenti: trovare codici che correggano efficacemente errori del tipo richiesto; trovare metodi di codifica e decodifica e modi semplici per implementarli.
Questi problemi sono più sviluppati in relazione ai codici sistematici. Tali codici vengono utilizzati con successo nella tecnologia informatica, in vari dispositivi digitali automatizzati e nei sistemi di trasmissione di informazioni digitali.
Conclusione
Abbiamo coperto un'attività di codifica che include:
1.Garantire l'efficienza della trasmissione delle informazioni eliminando la ridondanza.
2. Garantire l'affidabilità (immunità ai disturbi) della trasmissione delle informazioni
3. Coordinamento della velocità di trasferimento delle informazioni con la capacità del canale
Il problema della codifica è uno dei concetti principali dell'informatica, poiché la codifica precede la trasmissione e l'archiviazione delle informazioni e, di conseguenza, è la base per la loro implementazione di successo.
Quando si trasmettono messaggi sui canali di comunicazione, possono verificarsi interferenze che possono portare alla distorsione dei caratteri ricevuti. Questo problema viene risolto utilizzando la codifica di correzione degli errori. La codifica resistente al rumore delle informazioni trasmesse consente di rilevare e correggere gli errori nella parte ricevente del sistema. I codici utilizzati nella codifica di correzione degli errori sono chiamati codici di correzione. Per la prima volta, Claude Shannon ha condotto una ricerca sulla codifica efficiente. Per la teoria della comunicazione, due teoremi dimostrati da Shannon sono di fondamentale importanza.
Nel lavoro sono stati considerati questi teoremi e si può giungere alla conclusione che il primo influisce sulla situazione con la codifica durante la trasmissione di un messaggio su una linea di comunicazione, in cui non vi sono interferenze che distorcono le informazioni, ad es. questo teorema è uno standard, quali dovrebbero essere i codici di correzione del rumore.Il secondo teorema si riferisce a linee di comunicazione reali con interferenze.
Se consideriamo esempi di codifica, basati sul primo teorema di Shannon, allora possiamo giungere alla conclusione che questa codifica è abbastanza efficace, poiché il codice risultante non ha praticamente ridondanza, ma, sfortunatamente, c'è molta interferenza nella comunicazione reale linee, e un tale risultato è irraggiungibile. Pertanto, il codice di Shannon non è efficiente come, ad esempio, il codice di Huffman. Ma, nonostante ciò, va notato che Claude Shannon è stato uno dei fondatori della teoria della codifica e il suo lavoro ha dato un enorme contributo allo sviluppo dell'informatica.
Bibliografia:
1. Rivista "Radio", numero 9, 1999.
Scienze, Mosca
2. Klovsky D.D. Teoria della trasmissione del segnale. -M.: Comunicazione, 1984.
3. Kudryashov B.D. Teoria dell'informazione. Libro di testo per le università Casa editrice PETER,
4. Ryabko B.Ya. Fionov A.N. Un metodo efficace di adattamento
codifica aritmetica per sorgenti con grandi alfabeti
// Problemi di trasmissione delle informazioni 1999 V.35, Issue pp.95 - 108.
5. Semenyuk V.V. Codifica economica di informazioni discrete SPb .:
SPbGITMO (TU), 2001
6. Dmitriev V.I. Teoria dell'informazione applicata. M.: Scuola superiore,
7. Nefedov V.N., Osipova V.A. Corso di matematica discreta. M.: MAI,
8. Kolesnik V.D. Poltyrev G.Sh. Corso di teoria dell'informazione. M.: Scienza,
Codifica ottimale
Il teorema dei codici di Shannon. Metodi di codifica ottimale lettera per lettera. Criteri di ottimalità del codice. Codifica a blocchi. Sistema di codifica delle informazioni di testo unificato.
codifica,minimizzazione della ridondanza del codice,si chiama ottimale.
La questione dell'esistenza di tali codici è l'essenza di uno dei principali teoremi della teoria dell'informazione: il teorema della codifica dimostrato da K. Shannon. Ecco una delle formulazioni equivalenti di questo teorema.
teorema di codifica. Messaggi di una fonte di informazione arbitraria Z con entropia H(Z)può essere sempre codificato con sequenze dell'alfabeto B,composto da M caratteri,Così,che la lunghezza media del codice sarà arbitrariamente vicina al valore 
,ma non meno di lei.
A causa della sua complessità, la dimostrazione di questo teorema non viene considerata.
Il teorema afferma che la differenza può essere resa arbitrariamente piccola. Questo è il compito dei metodi di codifica ottimali.
Torniamo alla considerazione di una fonte di informazioni alfabetica che genera messaggi in caratteri alfabetici UN... Poiché la ridondanza del codice è data dalla formula
è ovvio che meno è ottimale il codice. Per diminuire i caratteri ricorrenti dovrebbero essere codificati con parole più brevi e viceversa. Tutti i metodi di codifica ottimali si basano su questo requisito. Inoltre, per garantire la decodifica di un codice irregolare, è importante osservare principio del prefisso: Nessun codice deve essere l'inizio di un altro codice.
Ecco due dei metodi più noti per la codifica ottimale lettera per lettera. Per semplicità di presentazione, prenderemo come codice l'alfabeto binario.
Passaggio 1. Disponiamo i simboli dell'alfabeto originale nell'ordine di non aumento delle loro probabilità. (Li scriviamo su una stringa.)
Passaggio 2. Senza modificare l'ordine dei simboli, li dividiamo in due gruppi in modo che le probabilità totali dei simboli nei gruppi siano il più uguali possibile.
Passaggio 3. Assegniamo al gruppo a sinistra "0" e al gruppo a destra "1" come elementi dei loro codici.
Passaggio 4. Sfoglia i gruppi. Se il numero di elementi nel gruppo è più di uno, vai al passaggio 2. Se c'è un elemento nel gruppo, la creazione del codice è completa.
Riso. 4.1. Albero binario corrispondente alla codifica Shannon-Fano
Considera l'operazione dell'algoritmo descritto usando l'esempio della codifica dell'alfabeto 
, i cui simboli si presentano con probabilità (0,25; 0,05; 0,25; 0,1; 0,25; 0,1), rispettivamente. Il risultato della codifica è mostrato in Fig. 4.1.
È ovvio che il processo di costruzione del codice nel caso generale contiene ambiguità, poiché non possiamo sempre dividere la sequenza in due sottoinsiemi ugualmente probabili. Sia a sinistra che a destra, la somma delle probabilità sarà maggiore. Il criterio migliore è una minore ridondanza del codice. Si noti inoltre che la corretta lettura del codice - dalla radice dell'albero al simbolo - farà sì che sia prefissato.
Considera l'algoritmo per il calcolo dei codici Shannon-Fano (per chiarezza, prendiamo la sequenza "aa bbb cccc ddddd" come esempio). Per calcolare i codici è necessario creare una tabella di simboli messaggio univoci c (io) e le loro probabilità p (c (i)) e ordinarlo in ordine di probabilità del simbolo non crescente.
| c (io) | p (c (i)) |
| D | 5 / 17 |
| C | 4 / 17 |
| spazio | 3 / 17 |
| B | 3 / 17 |
| un | 2 / 17 |
Inoltre, la tabella dei simboli è divisa in due gruppi in modo che ciascuno dei gruppi abbia approssimativamente la stessa frequenza nella somma dei simboli. Il primo gruppo è impostato all'inizio del codice a "0", il secondo a "1". Per calcolare i successivi bit dei codici carattere, questa procedura viene ripetuta in modo ricorsivo per ogni gruppo che contiene più di un carattere. Quindi, per il nostro caso, otteniamo i seguenti codici carattere:
Lunghezza del codice s (io) nella tabella risultante è int (-lg p (c (i))), se i sivol possono essere suddivisi in gruppi con la stessa frequenza, altrimenti la lunghezza del codice è int (-lg p (c (i))) + 1.
39 bit di lunghezza. Considerando che l'originale era lungo 136 bit, otteniamo un rapporto di compressione di ~ 28% - non così male.
Guardando la sequenza risultante, sorge la domanda: "Come puoi decomprimere questo ora?" Non possiamo, come nel caso della codifica, sostituire ogni 8 bit del flusso di input con un codice a lunghezza variabile. Durante la decompressione, dobbiamo fare il contrario: sostituire il codice a lunghezza variabile con un carattere a 8 bit. In questo caso, sarebbe meglio usare un albero binario, le cui foglie saranno dei simboli (analogo all'albero di Huffman).
La codifica Shannon-Fano è un metodo di compressione abbastanza antico, e oggi non riveste particolare interesse pratico (se non come esercizio nel corso delle strutture dati). Nella maggior parte dei casi, la lunghezza della sequenza compressa, secondo questo metodo, è uguale alla lunghezza della sequenza compressa utilizzando la codifica di Huffman. Ma su alcune sequenze si formano ancora codici Shannon-Fano non ottimali, quindi la compressione con il metodo di Huffman è considerata più efficiente. Ad esempio, considera una sequenza con il seguente contenuto di caratteri: "a" - 14, "b" - 7, "c" - 5, "d" - 5, "e" - 4. Il metodo Huffman la comprime a 77 bit , ma Shannon-Fano fino a 79 bit.
|
Come ci siamo divisi in gruppi? Abbastanza semplice:
A causa di questa ambiguità, alcune persone hanno persino pensieri del genere: "... il programma a volte assegna alcuni simboli ..." e così via - ragionando sulla lunghezza dei codici. Se non stai scrivendo AI, una cosa come "il programma a volte" fa qualcosa di ridicolo. Un algoritmo correttamente implementato funziona rigorosamente.
L'algoritmo per costruire il codice di compressione Shannon - Fano è il seguente.
1. Tutti i simboli di una sorgente discreta sono disposti in ordine decrescente di probabilità della loro comparsa (Tabella 4.2).
Tabella 4.2. Costruire il codice Shannon-Fano
2. La colonna di simboli formata è divisa in due gruppi in modo tale che le probabilità totali di ciascun gruppo differiscano poco l'una dall'altra.
3. Il gruppo superiore è codificato dal simbolo "1" e quello inferiore - dallo "0".
4. Ciascun gruppo è diviso in due sottogruppi con probabilità totali simili; il sottogruppo superiore è codificato dal simbolo "1" e quello inferiore - da "0".
5. Il processo di divisione e codifica continua finché ogni sottogruppo contiene un simbolo del messaggio di origine.
6. Viene registrato un codice per ogni carattere della fonte; il codice si legge da sinistra a destra.
Utilizzando il codice uniforme più semplice, per codificare i sei elementi dell'alfabeto di origine sarebbero necessari tre caratteri binari per ogni lettera del messaggio. Se viene utilizzato il codice Shannon-Fano, il numero medio di caratteri per lettera è
