Același mesaj poate fi codificat în moduri diferite. Cel mai avantajos cod este cel care petrece cel mai mic timp transmisiei mesajelor. Dacă transmiterea fiecărui element al unui simbol (de exemplu, 0 sau 1) durează același timp, atunci codul optim va fi astfel încât numărul minim de simboluri elementare să fie cheltuit pentru a transmite un mesaj de o anumită lungime. Codurile Shannon - Fano sunt prefixe, adică niciun cuvânt de cod nu este un prefix al altuia. Această proprietate vă permite să decodați fără ambiguitate orice secvență de cuvinte de cod
Să luăm în considerare principiul construirii unuia dintre primii algoritmi de compresie, care a fost formulat de oamenii de știință americani Shannon și Fano folosind exemplul literelor alfabetului rus. Algoritmul folosește coduri de lungime variabilă, de ex. un caracter comun este codificat cu un cod de lungime mai scurtă, unul rar - un cod mai lung.
Pentru a compune un astfel de cod, evident, trebuie să cunoașteți frecvența de apariție a literelor în textul rus. Aceste frecvențe sunt prezentate în tabelul 1. Literele din tabel sunt aranjate în ordinea descrescătoare a frecvenței.
tabelul 1
Frecvența apariției literelor alfabetului rus
Folosind tabelul, puteți compune cel mai economic cod pe baza considerațiilor legate de informații. Evident, codul va fi cel mai economic atunci când fiecare simbol elementar va transmite maximum de informații. Să considerăm un simbol elementar (adică reprezentând semnalul său) ca un sistem fizic cu două stări posibile: 0 și 1. Informația pe care o dă acest simbol este egală cu entropia acestui sistem și este maximă în cazul în care ambele stări sunt la fel de probabile; în acest caz, simbolul elementar transmite informația 1 (binara). Prin urmare, baza pentru codificare optimă va fi cerința ca caracterele elementare din textul codificat să apară în medie la fel de des.
Ideea codificării este că caracterele codificate (litere sau combinații de litere) sunt împărțite în două grupuri aproximativ la fel de probabile: pentru primul grup de caractere, primul loc al combinației este 0 (primul caracter al numărului binar reprezentarea personajului); pentru al doilea grup - 1. În plus, fiecare grup este din nou împărțit în două subgrupuri aproximativ la fel de probabile; pentru simbolurile primului subgrup, 0 este pus pe locul doi; pentru al doilea subgrup - unul etc.
Să demonstrăm principiul construirii codului Shannon-Fano folosind exemplul materialului alfabetului rus (vezi Tabelul 1). Să numărăm primele șase litere (de la „-” la „t”); însumând probabilitățile (frecvențele) lor, obținem 0,498; toate celelalte litere de la „n” la „f” vor avea aproximativ aceeași probabilitate de 0,502. Primele șase litere (de la „-” la „t”) vor avea semnul binar în primul rând 0. Restul literelor (de la „n” la „f”) vor avea în primul rând 1. Mai departe, vom împărți din nou primul grup în două subgrupuri aproximativ la fel de probabile: de la „-” la „o” și de la „e” la „t”; pentru toate literele primului subgrup de pe locul doi punem zero, iar al doilea subgrup - unul. Procesul va continua până când rămâne exact o literă în fiecare subdiviziune, care va fi codificată cu un anumit număr binar. Mecanismul de construcție este prezentat în Tabelul 2, iar codul în sine este prezentat în Tabelul 3.
masa 2
Mecanismul de construire a codului Shannon - Fano pe exemplul alfabetului rus
| Semne binare | |||||||||
| Scrisori | 1 | al 2-lea | al 3-lea | al 4-lea | al 5-lea | al 6-lea | al 7-lea | al 8-lea | al 9-lea |
| - | |||||||||
| O | |||||||||
| e | |||||||||
| A | |||||||||
| și | |||||||||
| T | |||||||||
| n | |||||||||
| Cu | |||||||||
| R | |||||||||
| v | |||||||||
| l | |||||||||
| La | |||||||||
| m | |||||||||
| d | |||||||||
| P | |||||||||
| la | |||||||||
| eu sunt | |||||||||
| s | |||||||||
| s | |||||||||
| b, b | |||||||||
| b | |||||||||
| G | |||||||||
| h | |||||||||
| al | |||||||||
| X | |||||||||
| f | |||||||||
| Yu | |||||||||
| w | |||||||||
| c | |||||||||
| SCH | |||||||||
| eh | |||||||||
| f |
Tabelul 3
Rezultatul codificării literelor alfabetului rus cu codul Shannon - Fano
Exemplul 4. Să scriem expresia „metoda de codificare” folosind codul Shannon - Fano.
Soluţie: Să folosim tabelul 3 și să obținem următorul rezultat:
(1001) s (110011) n (001) o (1001) s (001) o (111010) b (000) spațiu
(10111) până la (001) o (110010) d (0110) și (10100) r (001) o (10101) c
(0101) a (1000) n (0110) și (110110) i
Rețineți că nu este nevoie să separați literele unele de altele cu un caracter special, deoarece chiar și fără această decodare se realizează fără ambiguitate datorită proprietății prefixului: niciun cuvânt de cod mai scurt nu este începutul unui cuvânt de cod mai lung. Într-adevăr, Tabelul 3 arată că cele mai scurte sunt codurile pentru caracterele „spațiu” și „o”. În acest caz, niciun alt cod mai lung nu are la începutul secvenței 000 ("spațiu") și 001 ("o"). Același lucru poate fi observat pentru toate celelalte secvențe binare ale codului Shannon - Fano, care sunt prezentate în Tabelul 3.
Trebuie remarcat faptul că orice eroare de codificare (amestecare accidentală a 0 sau 1 caractere) cu un astfel de cod este fatală, deoarece decodarea întregului text în urma erorii devine imposibilă.
Exemplul 5. Stabiliți dacă codul pe care l-am considerat este optim în absența erorilor?
Soluţie: Să găsim informația medie pentru un simbol elementar (0 sau 1) și să o comparăm cu informația maximă posibilă, care este egală cu unu. Pentru a face acest lucru, găsim mai întâi informația medie conținută într-o literă a textului transmis, adică entropia pe literă (vezi formula 8):
Conform tabelului 1, determinăm numărul mediu de caractere elementare pe literă:
Astfel, informațiile pe caracter sunt foarte aproape de limita sa superioară de unu, iar acest cod este foarte aproape de optim.
În cazul utilizării unui cod binar pe cinci biți, informații pe caracter:
Exemplul 6. Lăsați un mesaj (un cuvânt în rusă) să fie primit prin canalul de comunicare codificat cu codul Shannon-Fano: 10111001110010010010100.
Este necesar să decodați secvența dată.
Soluţie: Procesul de decodare se bazează pe proprietatea prefixului codului și se realizează de la stânga la dreapta. Tabelul 3 arată că lungimea minimă a codului este de trei biți. Numărează trei biți de la începutul cuvântului de cod primit, obținem - 101. Nu există un astfel de cod în tabel, așa că mai adăugăm un bit, obținem - 1011. De asemenea, acest cod nu este în tabel, prin urmare, este necesar să mai adăugăm un bit, obținem combinația - 10111, care corespunde literei „k”. Cuvântul de cod 10111 este exclus din cuvântul de cod primit și este înlocuit cu simbolul original (litera „k”). Procesul de decodare a literelor rămase din mesajul primit este similar.
Procesul complet de decodare este prezentat în Tabelul 4. Semnul „-” din tabel înseamnă că codul selectat este absent în Tabelul 3.
Tabelul 4
Procesul de decodare a mesajelor
| Secvența de cod primită | ||||||||||||||||||||||
| - | ||||||||||||||||||||||
| - | ||||||||||||||||||||||
| La | ||||||||||||||||||||||
| La | O | |||||||||||||||||||||
| La | O | - | ||||||||||||||||||||
| La | O | - | ||||||||||||||||||||
| La | O | - | ||||||||||||||||||||
| La | O | d | ||||||||||||||||||||
| La | O | d | - | |||||||||||||||||||
| La | O | d | e | |||||||||||||||||||
| La | O | d | e | - | ||||||||||||||||||
| La | O | d | e | - | ||||||||||||||||||
| La | O | d | e | R |
Deci, cuvântul obținut ca urmare a decodării cuvântului de cod primit este „encoder”.
Codul optim poate fi determinat de cel în care fiecare caracter binar va transmite maximum de informație. În virtutea formulelor Hartley și Shannon, entropia maximă este atinsă cu evenimente equiprobabile, prin urmare, codul binar va fi optim dacă caracterele 0 și 1 apar la fel de des în mesajul codificat.
Să luăm ca exemplu codificarea binară optimă a literelor alfabetului rus împreună cu caracterul de spațiu „-”. Credem că probabilitățile de apariție a simbolurilor alfabetului rus în mesaj sunt cunoscute, de exemplu, cele prezentate în tabelul 3.
Tabelul 3 Frecvența literelor limbii ruse (ipoteză)
K. Shannon și R. Fano au propus în mod independent în 1948-1949. o metodă de construire a unui cod bazată pe îndeplinirea condiției de probabilitate egală a simbolurilor 0 și 1 dintr-un mesaj codificat.
Toate caracterele (litere) codificate sunt împărțite în două grupuri, astfel încât suma probabilităților caracterelor din primul grup să fie egală cu suma probabilităților caracterelor din al doilea grup (adică probabilitatea ca mesajul să conțină un caracter din primul grup este egal cu probabilitatea ca mesajul să conţină un caracter din al doilea grup).
Pentru simbolurile primului grup, valoarea primei cifre a codului este atribuită egală cu „0”, pentru simbolurile celui de-al doilea grup - egală cu „1”.
În plus, fiecare grup este împărțit în două subgrupe, astfel încât sumele probabilităților semnelor din fiecare subgrup să fie egale. Pentru simbolurile primului subgrup al fiecărui grup, valoarea celei de-a doua cifre a codului este atribuită egală cu „0”, pentru simbolurile celui de-al doilea subgrup al fiecărui grup - „1”. Acest proces de împărțire a simbolurilor în grupuri și codificare continuă până când un simbol rămâne în subgrupuri.
Un exemplu de codificare a caracterelor alfabetului rus este dat în tabel. 4
Tabelul 4. Un exemplu de codificare a literelor alfabetului rus folosind codul Shannna-Fano.
Analiza codurilor date în tabel duce la concluzia că simbolurile care apar frecvent sunt codificate în secvențe binare mai scurte, iar cele care apar rar - în cele mai lungi. Aceasta înseamnă că, în medie, pentru a codifica un mesaj de o anumită lungime, sunt necesare mai puține simboluri binare 0 și 1 decât în cazul oricărei alte metode de codare.
În același timp, procedura de construire a codului Shannon-Fano satisface criteriul de distincție Fano. Codul are prefix și nu necesită un caracter special care separă literele unele de altele pentru decodarea fără ambiguitate a unui mesaj binar.
Astfel, problema codificării corectării erorilor este un domeniu vast de cercetare teoretică și aplicată. Sarcinile principale în acest caz sunt următoarele: găsirea codurilor care corectează eficient erorile de tipul necesar; găsirea metodelor de codificare și decodare și modalități simple de implementare a acestora.
Aceste probleme sunt cel mai dezvoltate în raport cu codurile sistematice. Astfel de coduri sunt utilizate cu succes în tehnologia computerelor, în diverse dispozitive digitale automatizate și în sistemele digitale de transmitere a informațiilor.
Concluzie
Am acoperit o sarcină de codare care include:
1.Asigurarea eficienței transmiterii informațiilor prin eliminarea redundanței.
2. Asigurarea fiabilității (imunitate la zgomot) a transmiterii informațiilor
3. Coordonarea ratei de transfer de informații cu capacitatea canalului
Problema codificării este unul dintre conceptele principale ale informaticii, deoarece codificarea precede transmiterea și stocarea informațiilor și, în consecință, stă la baza implementării cu succes a acestora.
La transmiterea mesajelor prin canalele de comunicație, pot apărea interferențe care pot duce la distorsiunea caracterelor primite. Această problemă este rezolvată folosind codificarea de corectare a erorilor. Codarea rezistentă la zgomot a informațiilor transmise permite detectarea și corectarea erorilor în partea receptoare a sistemului. Codurile utilizate în codificarea de corectare a erorilor se numesc coduri de corectare. Pentru prima dată, Claude Shannon a efectuat cercetări privind codificarea eficientă. Pentru teoria comunicării, două teoreme dovedite de Shannon sunt de o importanță capitală.
În lucrare s-au luat în considerare aceste teoreme și se poate ajunge la concluzia că prima afectează situația cu codificarea la transmiterea unui mesaj pe o linie de comunicație, în care nu există interferențe care distorsionează informația, adică. această teoremă este un standard, ceea ce ar trebui să fie coduri de corectare a zgomotului.A doua teoremă se referă la liniile reale de comunicație cu interferență.
Dacă luăm în considerare exemple de codare, bazate pe prima teoremă Shannon, atunci putem ajunge la concluzia că această codificare este destul de eficientă, deoarece codul rezultat practic nu are redundanță, dar, din păcate, există multă interferență în comunicarea reală. linii, iar un astfel de rezultat este de neatins. Prin urmare, codul Shannon nu este la fel de eficient ca, de exemplu, codul Huffman. Dar, în ciuda acestui fapt, trebuie remarcat faptul că Claude Shannon a fost unul dintre fondatorii teoriei codificării, iar munca sa a adus o contribuție uriașă la dezvoltarea informaticii.
Bibliografie:
1. Revista „Radio”, numărul 9, 1999.
Științe, Moscova
2. Klovsky D.D. Teoria transmisiei semnalului. -M .: Comunicare, 1984.
3. Kudryashov B.D. Teoria informației. Manual pentru universități Editura PETER,
4. Ryabko B.Ya.Fionov A.N. O metodă eficientă de adaptare
codificare aritmetică pentru surse cu alfabete mari
// Probleme de transmitere a informațiilor 1999 V.35, Issue pp.95 - 108.
5. Semenyuk V.V. Codificare economică a informațiilor discrete SPb .:
SPbGITMO (TU), 2001
6. Dmitriev V.I. Teoria aplicată a informației. M .: Liceu,
7. Nefedov V.N., Osipova V.A. Curs de matematică discretă. M.: MAI,
8. Kolesnik V.D. Poltyrev G.Sh. Curs de teoria informației. M.: Știință,
Codificare optimă
Teorema de codificare a lui Shannon. Metode optime de codare literă cu literă. Criterii de optimizare pentru cod. Codare bloc. Sistem unificat de codificare a informațiilor text.
Codificarea,minimizând redundanța codului,se numeste optim.
Întrebarea existenței unor astfel de coduri este esența uneia dintre principalele teoreme ale teoriei informației - teorema de codificare demonstrată de K. Shannon. Iată una dintre formulările echivalente ale acestei teoreme.
Teorema de codificare. Mesaje ale unei surse arbitrare de informații Z cu entropie H(Z)poate fi întotdeauna codificat cu secvențe din alfabetul B,format din M caractere,Asa de,că lungimea medie a cuvântului de cod va fi în mod arbitrar apropiată de valoare 
,dar nu mai puțin decât ea.
Datorită complexității sale, demonstrarea acestei teoreme nu este luată în considerare.
Teorema afirmă că diferența poate fi făcută arbitrar de mică. Aceasta este sarcina metodelor optime de codare.
Să revenim la luarea în considerare a unei surse de informații alfabetice care generează mesaje în caractere alfabetice A... Deoarece redundanța codului este dată de formula
este evident că cu cât este mai puțin, cu atât este mai optim codul. Pentru scădere caracterele care apar frecvent ar trebui să fie codificate cu cuvinte mai scurte și invers. Toate metodele optime de codare se bazează pe această cerință. În plus, pentru a asigura decodarea unui cod neuniform, este important să se observe principiul prefixului: Niciun cuvânt de cod nu trebuie să fie începutul altui cuvânt de cod.
Iată două dintre cele mai cunoscute metode de codificare optimă literă cu literă. Pentru simplitatea prezentării, vom lua alfabetul binar ca cod.
Pasul 1. Aranjam simbolurile alfabetului original în ordinea necreșterii probabilităților lor. (Le scriem într-un șir.)
Pasul 2. Fără a schimba ordinea simbolurilor, le împărțim în două grupe astfel încât probabilitățile totale ale simbolurilor din grupuri să fie cât mai egale.
Pasul 3. Atribuim grupului din stânga „0” și grupului din dreapta „1” ca elemente ale codurilor lor.
Pasul 4. Parcurgeți grupurile. Dacă numărul de elemente din grup este mai mare de unul, mergeți la Pasul 2. Dacă există un element în grup, construirea codului pentru acesta este completă.
Orez. 4.1. Arborele binar corespunzător codificării Shannon-Fano
Luați în considerare funcționarea algoritmului descris folosind exemplul de codificare a alfabetului 
, ale căror simboluri apar cu probabilități (0,25; 0,05; 0,25; 0,1; 0,25; 0,1), respectiv. Rezultatul codificării este prezentat în Fig. 4.1.
Este evident că procesul de construire a codului în cazul general conține ambiguitate, deoarece nu putem împărți întotdeauna secvența în două submulțimi la fel de probabile. Fie în stânga, fie în dreapta, suma probabilităților va fi mai mare. Criteriul cel mai bun caz este redundanța codului mai mică. De asemenea, rețineți că citirea corectă a codului - de la rădăcina arborelui până la simbol - va asigura că acesta este prefixat.
Luați în considerare algoritmul pentru calcularea codurilor Shannon-Fano (pentru claritate, să luăm ca exemplu secvența „aa bbb cccc ddddd”). Pentru a calcula codurile, trebuie să creați un tabel cu simboluri unice pentru mesaje c (i)și probabilitățile lor p (c (i)), și sortați-l în ordinea necrescătoare a probabilității simbolului.
| c (i) | p (c (i)) |
| d | 5 / 17 |
| c | 4 / 17 |
| spaţiu | 3 / 17 |
| b | 3 / 17 |
| A | 2 / 17 |
În plus, tabelul de simboluri este împărțit în două grupuri, astfel încât fiecare dintre grupuri are aproximativ aceeași frecvență în suma simbolurilor. Primul grup este setat la începutul codului la „0”, al doilea la „1”. Pentru a calcula următorii biți ai codurilor de caractere, această procedură se repetă recursiv pentru fiecare grup care conține mai mult de un caracter. Astfel, pentru cazul nostru, obținem următoarele coduri de caractere:
Lungimea codului s (i)în tabelul rezultat este int (-lg p (c (i))), dacă sivolele pot fi împărțite în grupuri cu aceeași frecvență, în caz contrar, lungimea codului este int (-lg p (c (i))) + 1.
39 de biți lungime. Având în vedere că originalul avea o lungime de 136 de biți, obținem un raport de compresie de ~ 28% - nu chiar atât de rău.
Privind secvența rezultată, apare întrebarea: „Cum poți decomprima asta acum?” Nu putem, ca și în cazul codificării, să înlocuim fiecare 8 biți ai fluxului de intrare cu un cod de lungime variabilă. Când decomprimăm, trebuie să facem opusul - înlocuiți codul cu lungime variabilă cu un caracter de 8 biți. În acest caz, cel mai bine ar fi să folosiți un arbore binar, ale cărui frunze vor fi simboluri (analog arborelui Huffman).
Codarea Shannon-Fano este o metodă de compresie destul de veche, iar astăzi nu prezintă un interes practic deosebit (cu excepția unui exercițiu în cursul structurilor de date). În majoritatea cazurilor, lungimea secvenței comprimate, conform acestei metode, este egală cu lungimea secvenței comprimate folosind codarea Huffman. Dar pe unele secvențe, codurile Shannon-Fano neoptimale sunt încă formate, prin urmare, compresia prin metoda Huffman este considerată a fi mai eficientă. De exemplu, luați în considerare o secvență cu următorul conținut de caractere: "a" - 14, "b" - 7, "c" - 5, "d" - 5, "e" - 4. Metoda Huffman o comprimă la 77 de biți , dar Shannon-Fano până la 79 de biți.
|
Cum ne-am împărțit în grupuri? Destul de simplu:
Din cauza acestei ambiguități, unii chiar au astfel de gânduri: „... programul uneori atribuie unor simboluri...” și așa mai departe - raționând cu privire la lungimea codurilor. Dacă nu scrieți AI, atunci un astfel de lucru precum „programul uneori” face ceva sună ridicol. Un algoritm implementat corect funcționează strict.
Algoritmul pentru construirea codului de comprimare Shannon - Fano este următorul.
1. Toate simbolurile unei surse discrete sunt aranjate în ordinea descrescătoare a probabilităților de apariție (Tabelul 4.2).
Tabelul 4.2. Construirea codului Shannon-Fano
2. Coloana formată de simboluri este împărțită în două grupe astfel încât probabilitățile totale ale fiecărui grup să difere puțin unele de altele.
3. Grupul superior este codificat prin simbolul „1”, iar cel inferior - cu „0”.
4. Fiecare grup este împărțit în două subgrupe cu probabilități totale similare; subgrupul superior este codificat prin simbolul „1”, iar cel inferior - cu „0”.
5. Procesul de împărțire și codificare continuă până când fiecare subgrup conține un simbol al mesajului sursă.
6. Se înregistrează un cod pentru fiecare caracter al sursei; codul se citește de la stânga la dreapta.
Folosind cel mai simplu cod uniform, pentru a codifica cele șase elemente ale alfabetului sursă ar fi nevoie de trei caractere binare pentru fiecare literă a mesajului. Dacă se folosește codul Shannon-Fano, atunci numărul mediu de caractere pe literă este
