Metode de Comprimare de Date

Capitolul 1.

Prezentarea problemei compresiei de imagini

1.1 Fundamente

1.1.1 Reprezentarea imaginii

1.1.2 Cuantificarea imaginii

1.1.3 Modelarea matematică a imaginii

1.1.4 Introducere în problema compresiei de date

Tipuri de redundanță

1.1.5.1 Redundanța în codificare

1.1.5.2 Redundanța spatială .

1.1.5.3 Redundanța psihovizuală

1.1.6 Criterii de fidelitate

1.2. Modelarea procesului de compresie de imagini

1.3. Elemente de teoria informației

1.3.1 Măsurarea informației

1.3.2 Canalul de informații

1.4. Teoreme fundamentale de codificare

1.4.1 Teorema de codificare fără erori

1.4.2 Teorema de codificare de canal

1.4.3 Teorema de codificare a sursei

1.4.4 Aplicații

1.5 Compresia fără erori

1.5.1 Codificarea în lungime variabilă

1.5.1.2 Alte coduri de lungime variabilă utilizate

1.5.2 Codificarea aritmetică

1.5.3 Codificarea în planuri de biți

1.5.4 Codificarea imaginilor binare

1.5.4.1 Codificarea regiunilor constante

1.5.4.2 Codificarea dinamică unidimensională

1.5.4.2 Codificarea dinamică bidimensională

1.5.5 Codificarea predictivă fără pierderi

1.6 Comprimarea cu pierderi

1.6.1 Codificarea predictivă cu pierderi

1.6.2 Codificarea transformatei

Capitolul 2.

Algoritmi de compresie a imaginilor

Capitolul 2.

Algoritmi de compresie a imaginilor

2.1 Codificarea Huffman

2.1.1 Descrierea algoritmului

2.1.2 Implementare în C

2.2 Compresia LZW

2.2.1 Descriere generală

2.2.2 Implementare în C

2.3 Codificarea predictivă

2.3.1 Descrierea algoritmului

2.3.2 Calculul coeficienților funcției de predicție.

Implementare în C.

2.4 Codificarea transformatei

2.4.1 Descriere generală

2.4.2 Selecția transformatei

2.4.3 Selecția dimensiunii subimaginilor

2.4.4 Alocarea de biți

2.5 Codificarea secvențelor de imagini

2.5.1Codificarea imaginilor TV prin compensarea mișcării

2.6 Codificarea imaginilor color

Capitolul 3.

Tehnici informaționale

3.1 Concepte de bază

3.2 Măsurarea conținutului de informație al unei imagini

3.2.1 Introducere

3.2.2 Măsurarea informației și entropia Shannon

3.2.2.1 Măsura de informație. Definiție. Reprezentare

3.2.2.2 Entropia Shannon

3.3 Compresia fără pierderi de informație

3.3.1 Conținutul de informație al unei surse discrete

3.3.2 Coduri prefix de compactare a datelor

3.3.3 Coduri-bloc de compactare a datelor

3.3.4 Limite asimptotice de eroare

3.3.5 Coduri-arbore de compactare a datelor

3.4 Compresia cu pierderi de informație

3.4.1.Comunicarea realizată de un canal cu pierderi

3.4.2 Compresia cu distorsionarea informatiei

3.4.2.1 Masura de distorsie. Definitie. Proprietati.

3.4.2.2 Conținutul de informație al datelor comprimate. Functia de distorsie

Capitolul 4.

Descrierea aplicației

=== Capitolul 3 ===

Capitolul 3.

Tehnici informaționale

3.1 Concepte de bază

Un sistem informațional reprezintă un ansamblu format dintr-o sursă de informații, un canal și un utilizator, la care se adaugă un sistem de comunicare. Vom dezvolta teoria compresiei datelor pentru sursele discrete fără memorie, acesta fiind cazul cel mai puțin important în aplicații din două motive:

1 – multe surse au memorie, iar memoria constituie o formă de redundanță pe care codurile de compresie de date o pot înlătura

2 – majoritatea surselor sunt continue.

Prin urmare, compresia surselor discrete fără memorie nu prea are aplicații în practică. Totuși, cele mai multe idei teoretice pot fi înțelese prin studierea acestui model simplu.

O sursă de informații discretă este descrisă complet de ansamblul (A, z), unde A = {a0,a1,…,aJ-1} reprezintă alfabetul sursei, ce constă în totalitatea elementelor ce stau la baza compunerii unui mesaj, iar z = {P(a0),…,P(aJ-1)} reprezintă distribuția de probabilitate asociată mulțimii A. Întrucât simbolurile de probabilitate 0 ale sursei pot fi ignorate din alfabetul sursei, putem presupune că p(aj) > 0. Orice două surse caracterizate de aceeași distribuție de probabilitate a simbolurilor de ieșire vor defini aceeași problemă de compresie a datelor, simbolurile putând fi redenumite. Astfel, alfabetul sursei nu prezintă importanță în procesul de compactare, ci doar dimensiunea acestuia și distribuția de probabilitate asociată.

Canalul este mediul fizic prin intermediul căruia se realizează transferul de informații de la sursă la utilizator. Acestuia i se asociază un ansamblu (B, v), unde B = {b0,…,bK-1} reprezintă alfabetul canalului (de reproducere), iar v este distribuția de probabilitate corespunzătoare, care descrie complet ieșirea canalului, deci și informația recepționată de utilizator. Alfabetul de reproducere coincide adesea cu alfabetul sursei, acest aspect nefiind strict necesar. Sistemul de comunicare mediază transferul de informație de la sursă la canal, prin intermediul unui codificator și de la canal la utilizator prin intermediul unui decodificator.

Un sistem de compresie a imaginilor este în primul rând un sistem informațional. În continuare ne propunem să analizăm, în contextul oferit de teoria informației, care sunt limitările și posibilitățile procesului de codificare și transfer (comunicare) în cadrul unui astfel de sistem informațional.

3.2 Măsurarea conținutului de informație al unei imagini

3.2.1 Introducere

În sistemele de procesare a imaginii, și în primul rând în cele de comunicare (transmitere) se pune deseori problema măsurării (evaluarii) conținutului de informație specific unei imagini. O imagine cu un conținut redus de informație nu va fi transmisă în forma sa originală, ci va fi comprimată, cu un anume grad acceptat de distorsie, înainte de a fi transmisă.

O măsura clasică de evaluare obiectivă a informației este entropia Shannon.

Considerând funcția de imagine f și o mulțime S de puncte, definim imaginea-suport a mulțimii S ca fiind restricția funcției f la mulțimea S. O măsură a conținutului de informație al unei imagini se bazează pe numărul minim de transformări ce pot fi aplicate nivelurilor de gri ale pixelilor pentru a obține o imagine cu nivel de gri constant. Fie h:{0,1,…,L-1}→N histograma lui f, unde h(i) reprezintă numărul de pixeli caracterizați de nivelul de gri i. Definim măsura de informație a imaginii PIM(f) astfel:

Se observă că PIM(f) = 0 dacă și numai dacă f(x,y) = constant, pentru orice (x,y)NxN. Pe de altă parte, PIM(f) este maximă dacă și numai dacă f are o histogramă uniformă (adica h(i) = constant, 0 i L-1). Fie N(f) numărul total de pixeli din f. Atunci f are o histogramă uniformă dacă și numai dacă PIM(f) = N(f) (L-1) / L. Cu alte cuvinte, PIM(f) este direct proportională cu conținutul de informație deținut de f.

Dacă S1,S2,…,Sn reprezintă o partiție a mulțimii de puncte S, atunci:

Se definește măsura normalizată de informație a unei imagini prin următoarea relație: NPIM(f) = PIM(f) / N(f) . La codificarea imaginii, se utilizează PIM și NPIM pentru a decide asupra descompunerii lui f. De exemplu, dacă NPIM(f) este mai mică decât un prag dat, nu mai este necesară descompunerea lui f. Pe de altă parte, dacă NPIM(f) se apropie de maxim, iar pentru orice subimagine f / S, NPIM(f / S) se apropie de asemenea de maxim, atunci imaginea este aproape aleatoare, nemaifiind necesară descompunerea ei.

Notând

se obține:

Se poate defini o măsură generalizată, PIMk, prin numărul minim de modificări ale nivelurilor de gri ale unei imagini în vederea transformării sale într-una cu k niveluri de gri:

Prin urmare:

3.2.2 Măsurarea informației și entropia Shannon

3.2.2.1 Măsura de informație. Definiție. Reprezentare

Pentru orice n natural, considerăm mulțimea distribuțiilor de probabilitate complete n-are:

unde se va nota

În general, o măsură este privită ca o secvență (familie) de funcții Fn:ΓnR având o serie de proprietăți ce urmează a fi descrise ulterior.

Elementele mulțimii Γn reprezintă probabilități într-un spațiu de n elemente. În teoria codificării, Γn reprezintă mulțimea distribuțiilor de frecvență ale simbolurilor utilizate în codificarea mesajelor. În contextul de față, pi reprezintă frecvența relativă a nivelului de gri i într-o imagine.

Presupunem că o imagine se caracterizează prin nivelurile de gri i =1,2,…,n cu frecvențele (p1,p2,…,pn)n. Acestei imagini i se asociază o anumită măsură In(p) (presupunem că imaginea este încadrată de pătratul unitate), pe care o vom numi generic PIM (picture information measure).

3.2.2.2 Entropia Shannon

Ieșirea unei surse discrete de informații este o secvență aleatoare de simboluri conținute într-un alfabet de J simboluri {a0,a1,…,aJ-1}.Această secvență este produsă în acord cu o lege de probabilitate prestabilită. O sursă a cărei ieșire nu este aleatoare poate fi prezisă complet pe baza evoluției sale anterioare (infinită). Această ieșire nu conține informații, prin urmare nu prezintă importanță din punct de vedere informațional.

Dacă un simbol-sursă aj apare cu probabilitatea p(aj), volumul de informații asociat apariției simbolului aj se definește prin I(aj) = -log p(aj), unde baza logaritmului poate fi 2 sau e. Logaritmul natural este utilizat în fundamentarea teoretică, iar logaritmul în baza 2 este mai convenabil în rezultatele numerice.

Dacă, în cazul unei surse discrete fără memorie, probabilitatea de selecție a simbolului-sursă aj este p(aj), atunci informația generată de fiecare dată când se selectează simbolul aj este –log2p(aj) biți. Legea numerelor mari afirmă că dacă simbolul aj este selectat, în medie, de np(aj) ori dintr-un total de n selecții, atunci volumul mediu de informații rezultat după n ieșiri ale sursei este:

np(a0)log2 p(a0)-1+…+np(aJ-1)log2 p(aJ-1)-1 biți.

Împărțind această relație prin n obținem volumul mediu de informații pe simbol-sursă sau entropia:

Așadar, entropia Shannon standard asociată unui set de n evenimente se definește prin:

și are următoarele proprietăți:

Simetrie:

Normalitate: H2(,) = 1

Expansibilitate:

Aditivitate:

Aditivitate tare:

Recursivitate:

Continuitate: Hn este continua pe n.

Decisivitate: Hn(1,0,0,…,0) = 0

Maximalitate:

Concavitate:

3.2.2.3 Proprietăți ale măsurii de informație

Entropia Shannon se utilizează în principal la evaluarea conținutului de informație al unei imagini în procesele de codificare și transmitere a acestor informații. Întrucât interesul pricipal constă în extragerea informației dintr-o imagine, vom analiza proprietățile de bază necesare unei măsuri de informație:

P1. Continuitate: transformări mici în frecvența nivelurilor de gri vor produce modificări mici în măsura de informație picturală (o proprietate similară se numește stabilitate).

P2. Simetrie

P3. Concavitate: dă inegalitatea de concavitate, care ne asigură că PIM descrește pe măsură ce se coboară în arbore.

P4. Maximalitate: PIM este maximă când nivelurile de gri sunt distribuite uniform.

P5. Decisivitate: în cazul în care imaginea este descrisă de un singur nivel de gri, PIM este 0.

P6. Senzitivitate: în cazul descompunerii unui nivel de gri (cu frecvența p1+p2), valoarea PIM va fi mai mică sau egală cu cea anterioară descompunerii. Adică:

P7. Expansivitate: nivelurile de gri adăugate însă neutilizate nu vor afecta măsura de informație.

O variabilă aleatoare poate fi condiționată de o serie de informații laterale. În acest caz, vom nota distribuția sa de probabilitate cu Q = {Qk/j} sau P = {Pj/k}. Pentru orice valoare fixată a lui j sau k, avem o distribuție de probabilitate , deci și o entropie (entropia în Y condiționată de j, respectiv entropia în X condiționată de k). Acestea sunt definite astfel:

Putem defini de asemenea entropiile condiționale:

Entropiile condiționale pot fi gândite în termenii unui canal a cărui intrare este reprezentată de variabila aleatoare X și a cărui ieșire este dată de variabila aleatoare Y. H(X/Y) corespunde incertitudinii intrării canalului din punctul de vedere al receptorului, iar H(Y/X) corespunde incertitudinii ieșirii din punct de vedere al emițătorului. De regulă, aceste două valori nu coincid.

Teorema 3.1: Informația laterală nu mărește incertitudinea medie:

H(X/Y) H(X).

Demonstrație: Vom utiliza inegalitatea log x 1 – (1/x).

Observație: Entropia unui bloc de variabile aleatoare se definește astfel:

Dacă variabilele aleatoare sunt independente, atunci:

unde pl(aj) este probabiliatea ieșirii aj în variabila aleatoare situată la poziția l.

Teorema 3.2: Entropia este aditivă pentru evenimente aleatoare independente.

Demonstrație:

Teorema 3.3: Pentru orice cuvânt-sursă de lungime-bloc n,

cu egalitate dacă și numai dacă sursa este fără memorie.

Demonstrație: Fie pn(aj1,…,ajn) distribuția de probabilitate a blocului (X1,…,Xn) și fie pl(ajl) probabilitatea ieșirii ajl în variabila aleatoare Xl. Atunci:

Rezultă (utilizând inegalitatea log x 1-(1/x)):

cu egalitate dacă și numai dacă argumentul logaritmului specificat anterior este 1.

3.3 Compresia fără pierderi de informație

Datele provenite de la o sursă discretă pot fi redundante și, prin urmare, ineficient manipulate în raport cu resursele sistemului de comunicație. În cadrul unui sistem de compresie fără pierderi de informație, rolul unui cod de compresie a datelor este de a reprezenta ieșirea sursei de date cât mai compact (motiv pentru care astfel de coduri au fost numite coduri de compactare). Practic, codurile de compactare reduc considerabil numărul de biți necesari în reprezentarea ieșirii sursei, comparativ cu o reprezentare binară oarecare.

3.3.1 Conținutul de informație al unei surse discrete

O secvență de simboluri-sursă va fi reprezentată la codificare printr-un șir de simboluri ale alfabetului de cod { b0,b1,…,bK-1}. Acest alfabet este de regulă binar. Un cod de compactare a datelor reprezintă așadar o modalitate de reprezentare a unui mesaj-sursă printr-o secvență de simboluri binare. În cadrul sistemului informațional, codificatorul asigură o regulă de corespondență, care asociază fiecărei secvențe de intrare o unică secvență de codificare, iar decodificatorul introduce o regulă de reconstituire a mesajului pe baza secvenței codificate.

După codificare, întregul cuvânt de cod poate fi apoi introdus în text (în contextul originar). Punctuația cuvântului de cod – cum ar fi marcarea de început sau de sfârșit sau delimitarea subblocurilor interne – este considerată de regulă ca aparținând implicit cuvântului de cod. Uneori (mai rar) simbolurile de punctuație sau blank-urile sunt accesibile la nivel de protocol de sistem și nu sunt concepute ca parte a secvenței de cod.

Pe scurt, conținutul de informație al unei surse este numărul de biți pe simbol-sursă necesar în medie codificării optime de compactare adresată sursei respective. Vom vedea că conținutul de informație al unei surse fără memorie caracterizată de distribuția de probabilitate p este măsurat de entropia sa H(p). Entropia unei surse reprezintă cantitatea medie de informații pe simbol generată de sursa respectivă. Altfel spus, entropia este numărul mediu de biți necesari pentru a specifica simbolul selectat de sursă.

Când sursa de informații selectează un simbol, se generează un volum mediu de informații egal cu entropia H(p). O codificare binară a unei surse de entropie H biți pe simbol va utiliza în medie cel puțin H cifre binare pentru reprezentarea simbolului sursă. Mai mult, pentru orice >0, este posibilă construirea unui codificator care să reprezinte simbolul de ieșire utilizând, în medie, mai puțin de H(p)+ cifre binare. In general, apropierea de limită se realizează la codificarea secvențelor lungi de simboluri.

Secvența de simboluri-sursă poate fi foarte lungă astfel încât codificatorul n-o poate codifica instantaneu. Prin urmare este necesară o strategie de împărțire a secvenței în segmente pentru codificare, pentru ca ulterior, să se recurgă la concatenarea lor. In cazul în care codificarea segmentelor succesive este independentă de cea a segmentelor anterioare, codul se numește cod-bloc. Dacă codificarea reține și folosește o serie de informații oferite de segmentele anterior codificate, codul se numește cod-arbore.

Un cod-bloc de lungime fixă (n,r) codifică n simboluri-sursă în r biți de cod, unde n și r sunt fixate. Sirurile mai mari de n simboluri sunt împărțite în blocuri de câte n simboluri . Fiecare bloc se codifică separat, cuvintele de cod urmând a fi apoi concatenate. Există Jn blocuri de lungime n, posibile variante de ieșiri ale sursei și se utilizează [log2Jn] biți pentru construcția unui cuvânt de cod binar pentru fiecare bloc de lungime n. Se obține prin urmare o rată de aproximativ log2J biți pe simbol.

Există coduri mai eficiente, care utilizează aproximativ H(p) biți pe simbol-sursă. Pentru codificare la o rată apropiată de valoarea entropiei, un cod-bloc de lungime fixă va introduce posibilitatea unei erori, deși această eroare are o probabilitate oricât de mică. Un cod-bloc eficient pentru compactarea sursei asigură aproximativ nH(p) biți pe cuvânt-sursă de lungime n, prin urmare există cam 2nH(p) cuvinte de cod. Acestea se asociază cuvintelor-sursă cu cea mai mare probabilitate. Rămân prin urmare multe cuvinte-sursă cărora nu li se asociază un cuvânt de cod, așadar acestea nu pot fi codificate. Vom vedea că, pentru n suficient de mare, probabilitatea apariției unui cuvânt-sursă necodificabil devine foarte mică.

Codurile-bloc de lungime variabilă obțin de asemenea o rată de compresie (compactare) apropiată de entropia sursei, evitând însă apariția blocurilor necodificabile. Un astfel de cod împarte un șir lung de simboluri în blocuri de dimensiune n, fiecare bloc urmând a fi codificat în r biți, unde n și r variază. Lungimea cuvintelor de cod asociate variază invers proporțional cu probabilitatea blocului.

Se impune condiția ca reprezentarea să fie neambiguă. Dacă toate secvențele-sursă se codifică neambiguu, codul se numește unic decodabil. Mai precis, un cod este unic decodabil dacă pentru orice secvență-sursă de lungime finită, șirul corespunzător de cuvinte de cod concatenate este unic determinat (diferă de șirul de cuvinte de cod concatenate al oricărui alt șir de aceeași lungime).

Teorema 3.4: Un cod unic decodabil ce conține K simboluri în alfabetul de cod și M cuvinte de cod de lungimi l0,l1,…lM-1 satisface următoarea inegalitate (Kraft):

Demonstrație: Fie N>0 întreg arbitrar și considerăm un șir de N cuvinte concatenate c1,…,cN, de lungimi lm1,…,lmN. În scopul de a verifica, pentru toate șirurile de cuvinte de cod astfel construite, că orice două șiruri de lungime i sunt distincte, se utilizează următoarea identitate:

În membrul drept al acestei relații există un termen distinct corespunzător fiecărui șir posibil de N cuvinte de cod concatenate. Mai mult, suma lm1+…+lmN reprezintă lungimea totală (în simboluri de cod) a șirului respectiv de cuvinte concatenate.

Notând cu Ai numărul șirurilor cu o lungime totală de i simboluri de cod formate prin concatenarea a N cuvinte de cod, putem rescrie relația astfel:

unde L reprezintă valoarea maximă a lungimilor lm.

Întrucât codul este unic decodabil, toate secvențele de cuvinte de cod cu o lungime totală de i simboluri sunt distincte. Rezultă AiKi și

Întrucât (LN)1/N = e(1/N)log(LN), rezultă, prin trecere la limită după N:

Teorema 3.5: Pentru orice cod unic decodabil, lungimea medie l a cuvântului de cod pe simbol sursă codificat satisface relația: l logK H(p).

Demonstrație: Vom presupune că baza b a logaritmului este e (în caz contrar, vom înmulți inegalitatea prin logbe).

Utilizând inegalitatea log x x-1, rezultă:

Pe baza rezultatului din teorema precedentă, inegalitatea devine:

H(p) – l log K 1-1 = 0

și astfel demonstrația este încheiată.

Teorema 3.5 se aplică tuturor codurilor unic decodabile și pune în evidență semnificația funcției de entropie. Vom vedea în cele ce urmează că rata oricărei codificări depășește limita inferioară, dată de entropie, deși cu o variabilă arbitrar de mică.

Toate considerațiile referitoare la sursele fără memorie pot fi extinse și în cazul multor surse care prezintă memorie. Așa cum am specificat deja, o sursă de informații este fără memorie dacă simbolurile succesive generate de sursă sunt statistic independente. Altfel spus, o sursă este fără memorie dacă selecția oricărui simbol nu este influențată de selecțiile făcute anterior. In cazul în care selecția simbolurilor anterioare influențează selecția unui simbol următor, spunem că sursa posedă memorie.

3.3.2 Coduri prefix de compactare a datelor

Așa cum am specificat, codurile prefix sunt o categorie de coduri de lungime variabilă, a căror structură asigură implicit și punctuația codului, nemaifiind necesară introducerea de simboluri speciale de punctuație. Un astfel de cod prefix este codul Huffman construit în cap.1.

În continuare, vom interpreta entropia în sensul lungimii de bloc medie a unui cod prefix determinat de un alfabet de K simboluri.

Teorema 3.6: Lungimea-bloc medie

a unui cod prefix de compactare pentru sursa p satisface inegalitatea:

Demonstrație: Un cod prefix este unic decodabil. Prin urmare, demonstrația primei părți a acestei teoreme este asigurată de teorema 3.2.

Pentru a demonstra cea de-a doua parte, alegem lj = [(-log pj) / log K]. Deci pj K-lj. Prin sumare după j rezultă:

Inegalitatea Kraft este satisfăcută, deci există un cod prefix corespunzător mulțimii de lungimi-bloc descrisă mai sus. Din definiția lui lj rezultă:

Corolar: Fie >0 și o sursa fără memorie cu distribuția de probabilitate p dată. Se poate construi un cod prefix pentru codificarea acestei surse astfel încât

Demonstrație: Fie n astfel încât (1/n)<. Considerăm blocurile-sursă de lungimi n. Aceste ieșiri-bloc au entropia nH(p). Din teorema precedentă rezultă că se poate construi un cod prefix astfel încât

rezultă enunțul corolarului.

Observație:Corolarul de mai sus afirmă posibilitatea construcției unui cod prefix cu o lungime-bloc medie oricât de apropiată de entropia sursei.

Teorema 3.7: Codul prefix binar de lungime-bloc medie minimă cu alfabetul de cod format din K simboluri corespunzător unei surse de J simboluri dată are următoarele proprietăți: 1. Dacă pj > pj atunci lj lj.

2. Celor mai puțin probabile două ieșiri ale sursei li se asociază cuvinte de cod de aceeași lungime-bloc.

3. Dacă există două sau mai multe cuvinte de cod cu aceeași lungime-bloc, atunci două din acestea coincid în toate cifrele, mai puțin ultima (sunt diferențiate doar prin ultima cifră).

Demonstrație: 1. Dacă pj > pj și lj >lj, prin interschimbarea cuvintelor de cod j și j se obține un cod mai bun.

2.Din condiția de prefix rezultă că nu există un cuvânt de cod care să fie prefix al oricăruia din cele două cel mai puțin probabile cuvinte de cod. Să presupunem că aceste două cuvinte ar avea lungimi diferite. Atunci ultimul simbol al cuvântului de cod mai lung poate fi șters. Această ștergere nu poate conduce la un cuvânt de cod deja existent, prin urmare va conduce la o codificare prefix nouă cu o lungime medie mai mică decât a codului considerat inițial.

3. Presupunem că toate cuvintele de cod de o lungime dată diferă la înlăturarea ultimului simbol. Nu există un cuvânt de cod mai scurt care să fie prefix al oricăruia dintre ele, deci prin înlăturarea ultimului simbol al tuturor cuvintelor de această lungime se obține un nou cod prefix cu o lungime medie mai mică.

Teorema 3.7 oferă baza construcției codului prefix binar optim pentru o sursă dată. Vom presupune, fără a restrânge generalitatea, că cele două cuvinte de cod implicate la punctul 3 al teoremei sunt cele mai puțin probabile cuvinte de cod cu lungimea-bloc respectivă, întrucât cuvintele de cod cu aceeași lungime se pot interschimba fără a afecta lungimea-bloc medie a codului. Astfel, dacă am asociat cuvinte de cod tuturor simbolurilor, cu excepția celor mai puțin probabile două simboluri și dacă am construit toate literele, mai puțin ultima, pentru unul din aceste două cuvinte de cod rămase, vom ști imediat cum să completăm codul.

Considerațiile de mai sus sugerează următoarea procedură: se combină cele două simboluri-sursă cel mai puțin probabile într-un nou simbol artificial, a cărui probabilitate va fi egală cu suma probabilităților celor două simboluri originale. Se obține astfel o nouă sursă cu J-1 simboluri și se încearcă găsirea unui cod optim pentru această sursă. Pentru a obține cuvintele de cod asociate celor două cel mai puțin probabile simboluri ale sursei originale, se va considera cuvântul de cod corespunzător cuvântului artificial, căruia i se adaugă 0, respectiv 1.

Teorema 3.8: Presupunem că cele mai puțin probabile două simboluri-sursă se combină intr-un singur simbol artificial și fie C codul optim al acestei surse artificiale nou obținută. Pe baza codului C construim codul C astfel: se adaugă un 0 și un 1 cuvântului de cod corespunzător simbolului artificial (obținând astfel cuvintele de cod asociate celor două simboluri cel mai puțin probabile ale sursei inițiale). Toate celelalte cuvinte de cod din C sunt identice cu corespondentele lor din C. Codul C este optim pentru sursa originală.

Demonstrație: Fie pj1 și pj2 cele mai mici două probabilități. Teorema 3.7 afirmă că putem restrânge căutarea codului optim la acea sferă de coduri pentru care cuvintele de cod de indici j1 și j2 sunt printre cele mai lungi și diferă doar în ultima poziție.

In indexarea codului C vom șterge indicele j2. Relația dintre lungimile Lj (j j2) ale cuvintelor de cod corespunzătoare codului C și lungimile lj ale codului C este dată de: Lj1+1 ,j = j1 sau j2

lj =

Lj ,altfel

Rezultă:

Pentru stabilirea codului optim C al problemei artificiale, se va repeta procedura descrisă de teorema precedentă. Se combină noile două simboluri cu cele mai mici probabilități și se caută codul optim C al sursei nou obținută. Procedura se repetă până se obține o sursă artificială de două simboluri, cărora li se asociază cuvintele de cod 0, respectiv 1.

Observație: Codul descris de teorema 3.8 este codul Huffman descris și exemplificat în capitolul 1.

3.3.3 Coduri-bloc de compactare a datelor

Codurile-bloc diferă de codurile prefix prin faptul că toate cuvintele de cod au aceeași lungime. Un cuvânt-sursă este codificat printr-un bloc de simboluri situate într-un alfabet de cod (dat), utilizând numărul minim posibil de simboluri de cod pe simbol-sursă. De exemplu, presupunem că cifrele zecimale emise de sursă sunt codificate în cuvinte de cod binare. Vom vedea că pentru codurile bloc, ca și în cazul codurilor prefix, numărul necesar de cifre binare pe simbol sursă este egal cu entropia sursei.

Un alt element specific codurilor-bloc constă în aceea că nu acoperă întotdeauna întreaga sursă (permite pierderea anumitor date-sursă). Singura modalitate de a evita acest lucru este de a considera r astfel încât Kr Jn , întrucât sursa are Jn ieșiri posibile de lungime n, ce urmează a fi reprezentate prin Kr posibile secvențe de cod de lungime r. In acest caz însă rata codului nu aproximează entropia, întrucât codul acoperă și blocurile de ieșire care nu apar aproape niciodată.

Definiție: Un cod-bloc de lungime-bloc n și dimensiune M este o mulțime C ={cm} formată din M cuvinte de cod de lungime n; fiecare cuvânt de cod este o secvență de n simboluri sursă de ieșire.

In general M = 2r (sau Kr). Coeficientul r/n se numește rata codului.

Primele M-1 cuvinte de cod ale mulțimii C se numesc cuvinte de cod normale, iar ultimul cuvânt de cod se utilizeaza ca indicator de eroare. Secvența de ieșire a sursei se împarte în blocuri de lungime n. Fiecare bloc (cuvânt sursă) poate fi sau nu în C. Dacă este în C, rămâne neschimbat. Dacă nu, este înlocuit prin indicatorul de eroare, care informează decodificatorul că procesul de codificare a eșuat. Sirul de cuvinte-sursă codificate se reprezintă compact prin înlocuirea fiecărui cuvânt de cod prin indexul binar corespunzător. Fiecare bloc va fi reprezentat astfel printr-un număr binar de r biți.

Decodificatorul inversează procesul de codificare, înlocuind fiecare număr binar de r biți prin cuvântul de cod corespunzător, exceptând cazul în care întâlnește cuvântul implicit (caz în care cuvântul sursă se consideră pierdut).

Considerăm un bloc de n ieșiri al unei surse fără memorie x = (aj1,…,ajn), în care simbolul aj apare în x de nj ori. Vectorul (n0,…,nJ-1) poartă numele de compoziția cuvântului-sursă x. Probabilitatea lui x este dată de

Întrucât nj / n tinde la pj din legea numerelor mari, atunci:

Vom enunța în continuare o teoremă referită adesea cu numele de proprietatea de echipartiție asimptotică. În mare, această teoremă afirmă că aproape toate secvențele de ieșire sunt aproape echiprobabile.

Teorema 3.9 (Shannon – McMillan): Fiind dată o sursă discretă fără memorie p de entropie H(p), pentru orice >0, se poate alege n suficient de mare astfel încât mulțimea tuturor cuvintelor-sursă posibile de lungime n să poată fi partiționată în două mulțimi T și TC care să satisfacă următoarele condiții:

Probabilitatea unei secvențe din TC este mai mică decât .

Probabilitatea de apariție a unei secvențe x din T este aproximativ e-nH(p), în sensul că – n-1log p(x) – H(p)< .

Cardinalul mulțimii T, notat T, se află situat în intervalul [(1-)2n(H(p)- ) , 2n(H(p)+ )].

Demonstrație: Fie T = {x / -log p(x) – nH(p) < n}. Evident, T satisface proprietatea 2. Din inegalitatea Cebîșev rezultă:

Pentru a demonstra 3, considerăm H = H(p) și vom scrie:

Corolar:

, unde Pr[TC] reprezintă probabilitatea ca o secvență de lungime n să aparțină mulțimii TC.

Mulțimea T conține secvențele tipice generate de sursă. Teorema 3.9 afirmă că probabilitatea de apariție a unei secvențe atipice este neglijabilă. Există în jur de 2nH secvențe tipice.

Definiție: Considerăm o sursă fără memorie p, cu entropia H(p) și >0. Se definește mulțimea secvențelor tipice slabe (secvențelor -tipice slabe) astfel:

unde baza logaritmului coincide cu cea utilizată în calculul entropiei.

În mod similar se definește mulțimea secvențelor tipice tari (secvențelor -tipice tari):

unde nj(x) reprezintă numărul de apariții ale simbolului j în secvența x.

In timp ce secvențele tipice slabe expun aproximativ entropia aparentă corespunzătoare, secvențele tipice tari expun aproximativ frecvența relativă a simbolurilor. Ambele tipuri de secvențe pot fi încadrate într-o categorie globală de secvențe tipice.

Vom aplica în continuare teorema Shannon-McMillan la codificarea blocurilor x = (aj1,…,ajn) ale unei surse discrete fără memorie prin cuvinte de cod de lungime n formate din simboluri ce provin de la un alfabet de dimensiune K, în ipoteza că numărul de cuvinte de cod este mai mic decât numărul de secvențe-sursă (altfel nu există compactare).

La reconstituirea mesajului-sursă, în cazul în care decodificatorul întâlnește cuvântul implicit, intervine un eșec în decodificare. Vom demonstra în continuare că probabilitatea intervenției unui eșec în decodificare poate fi redusă oricât de mult.

Teorema 3.10 (Prima teoremă a lui Shannon): Secvențele de lungime n produse de o sursă discretă fără memorie p cu entropia H(p) se codifică prin cuvinte de cod de lungime r compuse din simboluri ce provin de la un alfabet de dimensiune K. Pentru orice >0, se poate obține o probabilitate de intervenție a unui eșec la decodificare mai mică decât în condițiile în care rlogK > nH(p) , pentru n suficient de mare.

Demonstrație: Din teorema Shannon McMillan rezultă:

T = { x: e-n(H – ) > p(x) > e-n(H+) }, unde H se exprimă în unități naturale. Prin urmare numărul de secvențe-sursă din T este mai mic decât en(H+).

Alegem astfel încât rlogK n(H(p) + ).

Întrucât numărul de cuvinte de cod de lungime r este Kr, se observă că numărul de cuvinte de cod este cel puțin en(H+). Astfel putem asocia câte un cuvânt de cod fiecărei secvențe tipice. Prin urmare, mulțimea de secvențe nedecodabile se găsește în TC și pentru n suficient de mare pe < .

Teorema 3.11 (Teorema reciprocă): Fie >0 . Considerăm sursa discretă fără memorie p cu entropia H(p), căreia i se asociază un alfabet de cod de dimensiune K și fie R astfel încât R log K < H(p). Atunci, pentru toate codurile de rată R cu lungimea sevenței suficient de mare, probabilitatea intervenției unui eșec în decodificare pe satisface relația pe > 1 – .

Demonstrație: R. Blahut – “Principles and Practice of Information Theory”, Addison Wesley, 1987.

3.3.4 Limite asimptotice de eroare

Teorema Shannon afirmă că pentru n suficient de mare, o secvență de lungime n poate fi reprezentată neambiguu prin intermediul unui cod-bloc cu o probabilitate oricât de apropiată de 1, asigurând o rată de cod mai mare decât entropia sursei. Nu s-a stabilit însă cât de mare ar trebui să fie lungimea n a secvenței pentru a obține o probabilitate de eșec în decodificare mai mică decât o valoare prestabilită pe. Vom analiza în continuare variația acestui factor de probabilitate în raport cu n. Vom vedea că pentru o rată fixată R, probabilitatea descrește exponențial cu lungimea blocului, coeficientul de descreștere fiind exprimat de o funcție F(R)

Definiție: Considerăm o sursă discretă fără memorie cu o distribuție de probabilitate p. Definim funcția de încredere F(R) pentru compactarea datelor astfel:

Șirul de simboluri emis de o sursă discretă poate fi împărțit în secvențe de lungime n. Mulțimea secvențelor astfel obținute poate fi privită ca o mulțime de simboluri ale unei noi surse cu Jn simboluri în alfabetul de ieșire. Vom nota cu Fn(R) funcția de încredere corespunzătoare sursei de n-tupluri. Pentru cazul unei surse fără memorie, legătura dintre Fn(R) și F(R) este dată de următoarea teoremă:

Teorema 3.12: Fie pn(x) distribuția de probabilitate a blocurilor de lungime n formate din simboluri independente, identic distribuite. Atunci: Fn(nR) = nF(R).

Demonstrație:

Deci minimul se atinge pentru o distribuție produs. Prin urmare, toate proiecțiile lui pn sunt identice, și astfel demonstrația este încheiată.

Funcția F(R) are următoarele proprietăți:

1.F(R) este o funcție convexă și crescătoare. Se anulează pentru R H(p) și este strict crescătoare în intervalul H(p) R log J.

2. F(R) se poate reprezenta astfel:

Vom explicita în continuare comportarea asimptotică în raport cu lungimea de bloc n a probabilității de eșec în decodificare

Teorema 3.13: Este posibilă selectarea a M-1 secvențe-sursă de lungime n în vederea codificării astfel încât: pe e-nF(R)

M enR

Demonstrație: Alegem un prag T dat de formula:

unde s parametrizează F(R) în punctul R. Definim următoarea mulțime de cuvinte-sursă:

U = {x : p(x) > e –nT}

Considerăm funcția indicator a complementarei mulțimii U:

Din definiția lui U rezultă:

În mod similar, considerând funcția indicator a mulțimii U rezultă:

Corolar: O mulțime ce satisface condițiile de performanță date de teorema 3.13 este:

Funcția F(R) asigură dependența corectă de n a probabilității pe, așa cum vom vedea în teorema următoare, care dă limita inferioară a lui pe și demonstrează că exponenții dați de teorema anterioară sunt optimi. Teorema exclude cazul de distribuție echiprobabilă, care nu poate fi compactată, întrucât nu există un R corespunzător condiției.

Teorema 3.14: Fie >0. Vom presupune, pentru cazul unei surse discrete fără memorie de distribuție p că H(p) < R < log J. Atunci, pentru n suficient de mare, toate codurile cu enR cuvinte de cod vor avea o probabilitate de eșec la decodificare pe e-n[F(R)+].

Demonstrație: Teorema nu se aplică pentru cazul de distribuție echiprobabilă, întrucât ar rezulta H(p) = log J.

Fie R > R. Pentru orice distribuție p în afară de cea echiprobabilă, se poate găsi o distribuție de probabilitate fictivă p* astfel încât H(p)<R<R = H(p*)<log J. Din reciproca teoremei de codificare Shannon, pentru orice mulțime U cu cel mult enR elemente și n suficient de mare, rezultă:

Din legea numerelor mari, pentru n suficient de mare rezultă:

Fie U mulțimea de secvențe-sursă ce urmează a fi codificate. Atunci:

Prin urmare: pe e-n[F(R)+-(1/n)log(1-2)]. Intrucât R poate fi ales astfel încât F(R) să fie oricât de apropiat de R, iar și sunt oricât de mici și n suficient de mare, rezultă în concluzie: pe e-n[F(R)+].

3.3.5 Coduri-arbore de compactare a datelor

Entropia unei surse este – pj log pj, iar lungimea medie a unui cod Huffman este pjlj. Pentru ca rata codificării să fie egală cu entropia este necesară alegerea lungimii cuvântului de cod astfel încât lj = log pj. Întrucât lungimea cuvântului de cod trebuie să fie un număr întreg, această relație nu poate fi satisfăcută, cu excepția câtorva (foarte puține) cazuri. O modalitate eficientă este de a utiliza codul Huffman la nivelul blocurilor-sursă. O altă modalitate constă în utilizarea unui cod-arbore, care diferă de un cod-bloc prin aceea că nu este posibilă, în general, împărțirea cuvântului de cod într-o secvență concatenată de blocuri independente. În cadrul acestei categorii intra codificarea aritmetica, prezentata in capitolul 1.

Considerăm problema de compresie definită de o sursă binară cu alfabetul {a0= 0,a1=1} și distribuția de probabilitate p = (p0, p1). Regula iterativă generală este următoarea: după n-1 biți-sursă, se obține un interval [An-1, Bn-1). Dacă cel de-al n-lea simbol-sursă transmis este 0, următorul bit specifică un nou interval cu marginile

An = An-1

Bn = An-1 + p(Bn-1 – An-1) .

Dacă simbolul este 1, se specifică un interval cu marginile:

An = An-1 + p(Bn-1 – An-1)

Bn = Bn-1

Astfel, intervalul specificat de fiecare secvență de simboluri-sursă are o lungime egală cu probabilitatea secvenței respective. Lungimea intervalului scade pe măsură ce crește lungimea secvenței. O secvență infinită specifică exact un punct, iar o secvență de lungime finită specifică un subinterval mic din [0,1).

Pe măsură ce secvența-sursă crește, intervalul original [0,1) se subdivide din ce în ce mai mult. Numărul de poziții semnificative în numerele reale An și Bn crește. In consecință, codificarea aritmetica nu este practica datorită problemelor de precizie. Orice lungime am alege pentru An și Bn, va fi depășită la un moment dat. Erorile de calcul, oricât de mici, vor cauza erori de codificare și decodificare.

Aceste neajunsuri ale codificarii aritmetice pot fi eliminate prin amplificarea, într-o primă fază, a intervalului obținut la iterația n prin factorul 2m+Ln, unde m fixat și Ln este ales în funcție de date, și plasarea ulterioară a punctelor marginale ale intervalului specificat într-o mulțime fixată de puncte. Rolul punctului marginal normalizat stâng 2m+LnAn este preluat de întregul Cn, iar lungimea 2m+Ln(Bn – An) a intervalului este înlocuită cu WnN. Întregul fixat m determină numărul de biți de precizie utilizați în măsurarea intervalului.

Parametrii Cn și Wn se inițializează cu C0 = 0 și W0 = 2m –1. Dacă cel de-al n-lea simbol-sursă este 0, atunci se actualizează pe baza următoarelor relații:

Cn = 2sCn-1

Wn = 2s[Wn-1p0+],

iar dacă este 1: Cn = 2s (Cn-1 + Wn-1 – [Wn-1p1+])

Wn = 2s[Wn-1p1+],

unde s se alege astfel încât 2m-1 Wn <2m.

Prin alegerea lui s, parametrul Wn rămâne mărginit, dar Cn tinde spre infinit pe măsură ce n crește. Biții cuvântului de cod coincid cu biții superiori ai lui Cn ce părăsesc codificatorul la iterația n.

Factorul de amplificare Ln nu se calculează și nici nu este utilizat explicit de codificator și decodificator. El poate crește oricât de mult și este determinat recursiv astfel:

Ln = Ln-1 + s, L0 = 0.

Pentru a ne asigura că s este bine definit, este necesară condiția Wn 0, satisfăcută în condițiile alegerii lui m astfel încât pi > 2-m, i. Intrucât Wn 2m-1, rezultă că [Wn-1p0 + ] și [Wn-1p0 + ] sunt nenule. Deci Wn se menține întotdeauna pozitiv și parametrul s este bine definit. Alegerea unei valori mari pentru m corespunde unei granularități fine în calcul și conduce la un cod-arbore ce va compacta datele cu o rată cât mai apropiată de entropie.

3.4 Compresia cu pierderi de informație

În cadrul procesului de compresie cu pierderi de informație, se pot diferenția două aspecte: 1 – canalul de transmitere este predispus la erori

2 – se acceptă un oarecare coeficient de distorsie în favoarea unei mai bune comprimări a datelor.

Vom analiza pe rând aceste două aspecte.

3.4.1.Comunicarea realizată de un canal cu pierderi

În practică, cele mai multe canale sunt predispuse la erori. Vom analiza în cele ce urmează limitele de comunicare realizate de un canal cu pierderi. Obiectivul vizat este optimizarea procesului de transmitere a informației prin canal, astfel încat distorsia imaginii recepționate de utilizator să fie cât mai redusă. Codul de canal va introduce un anume tip de redundanță în transmisie, astfel încât semnalul distorsionat receptat la ieșirea din canal să poată fi decodificat corespunzător.

3.4.1.1 Informația transmisă printr-un canal

În cele ce urmează, vom analiza volumul de informație ce poate fi transmisă printr-un canal. În termeni operaționali, ne interesează găsirea unei modalități de utilizare a canalului care să asigure recuperarea întregului mesaj transmis cu o probabilitate de eroare neglijabilă.

Informația mutuală I(X;Y), definită prin I(X;Y) = H(X) – H(X/Y) = H(Y) – H(Y/X), reflectă măsura variației incertitudinii intrării X în condițiile în care se observă o ieșire particulară Y. Din considerente computaționale, forma cea mai utilizată este I(X;Y) = H(Y) – H(Y/X).

Maximizarea informației mutuale. Informația mutuală depinde de alegerea ansamblului de intrare. Ne propunem ca obiectiv maximizarea informației mutuale realizată de un canal prin alegerea unui ansamblu optim de intrare. Vom defini capacitatea unui canal Q ca fiind informația mutuală maximă:

Distribuția PX care asigură maximul se numește distribuție optimă de intrare și se notează PX* . Pot exista mai multe distribuții optime care realizează aceeași valoare a informației mutuale. Așa cum vom vedea, capacitatea unui canal măsoară rata la care un canal poate transmite mesaje (informații) cu o probabilitate de eroare oricât de mică.

3.4.1.2 Teorema de codificare a unui canal predispus la erori

Definitie: Un cod-bloc (N,K) pentru canalul Q este o listă de M = 2K cuvinte de cod {x(1), x(2),…, x(M)}, fiecare de lungime N: x(m)AN(X). Cu ajutorul acestui cod, putem codifica un semnal m{1, 2,…, 2K} prin x(m).Rata codului este R = K / N biti.

Un decodificator al unui cod-bloc (N,K) este o aplicatie de la AN(Y) la {0,1,2,…,2K}. Simbolul suplimentar m = 0 se utilizeaza ca indicator de eroare.

Probabilitatea de eroare-bloc a unui ansamblu format dintr-un cod si un decodificator, pentru un canal dat si o distributie de probabilitate data in conditiile emiterii unui semnal codificat P(min) este:

Probabilitatea maxima de eroare-bloc:

Decodificatorul optim al unui cod de canal este cel care minimizeaza probabilitatea de interventie a unei erori-bloc. El decodifica o iesire y asociindu-i intrarea m care are probabilitatea conditionala P(m/y) cea mai mare:

Probabilitatea de eroare elementara pb se defineste in ipoteza ca m se reprezinta ca un vector binar s de lungime K; este probabilitatea medie ca un bit din sout sa nu coincida cu bitul corespunzator din sin.

Teorema a doua a lui Shannon (de codificare cu pierderi):

1.Capacitatea oricarui canal discret fara memorie are urmatoarea proprietate: >0 si R<C, pentru N suficient de mare, exista un cod-bloc de dimensiune N si rata mai mare ca R si un algoritm de decodificare care sa asigure o probabilitate maxima de interventie a unei erori-bloc mai mica decat

2. Pentru o probabilitate elementara de eroare pb acceptabila, se poate obtine o rata de pana la R(pb), unde

3. Pentru o probabilitate de eroare elementara pb data, nu se pot obtine rate mai mari decat R(pb) definita anterior.

Putem realiza o verificare intuitiva a teoremei analizand comportamentul canalului extins. Orice intrare particulara X produce, cu o probabilitate mare, o iesire dintr-un subspatiu mic al alfabetului de iesire. Se poate determina prin urmare o submultime neconfuza de intrari care sa produca secvente disjuncte de iesire. Sa ne imaginam o secventa de intrare X dintr-un ansamblu XN al canalului extins, unde X este un ansamblu arbitrar definit pe alfabetul de intrare. Consideram numarul de secvente de iesire probabile y. Numarul total de secvente tipice de iesire y, unde x provine din ansamblul XN este 2NH(Y), toate avand probabilitate similara. Pentru orice secventa tipica particulara de intrare x, exista in jur de 2NH(Y/X) secvente probabile. Ne vom restrange doar la intrarile tipice x astfel incat iesirile tipice corespunzatoare sa nu se suprapuna. Marginea superioara anumarului de intrari neconfuze este 2NH(Y) – NH(Y/X) = 2NI(X;Y). Valoarea maxima a acestei limite se atinge in conditiile in care X este un ansamblu care maximizeaza I(X;Y), caz in care numarul de intrari neconfuze va fi mai mic sau egal cu 2NC.

Vom incerca o formalizare a argumentelor intuitive prezentate anterior. Definim cuvintele de cod x(m) ce provin din ansamblul XN, si consideram selectia aleatoare a unui cuvant de cod si a iesirii de canal corespunzatoare y definita prin ansamblul (XY)N.Vom utiliza un decodificator care decodifica un semnal receptionat y asociindu-i m daca x(m) si y se afla in relatie de combinare tipica, notiune ce urmeaza a fi definita ulterior pe scurt. Suportul demonstratiei va consta in determinarea urmatoarelor probabilitati:

ca secventa de cod de intrare reala sa nu fie in combinatie tipica cu secventa de iesire.

ca un cuvant de cod de intrare fals sa fie in combinatie tipica cu secventa de iesire.

Vom arata ca pentru N suficient de mare, ambele probabilitati tind spre 0 atata timp cat codul are mai putin de 2NC cuvinte de cod.

Definitie: O pereche de secvente x, y de lungime N sunt in relatie de combinare tipica (cu coeficientul de toleranta ) in raport cu distributia de probabilitate P(x,y) daca sunt verificate urmatoarele conditii:

Vom nota cu JN multimea tuturor perechilor de secvente de lungime N aflate in relatie de combinare tipica.

Teorema de combinare tipica: Fie x si y doua secvente determinate de ansamblul (XY)N,

definit prin:

Atunci: 1. Probabilitatea ca x si y sa fie in combinatie tipica tinde spre 1 pentru N.

2. JN 2N(H(X,Y) + )

3. Daca x~XN si y~YN, adica daca x si y sunt independente si au aceeasi distributie marginala ca P(x,y), atunci P((x,y)JN) 2-N(I(X;Y) – 3).

Demonstratie: David J.C. MacKay, p.215

Demonstratia teoremei de codificare cu pierderi.

Evaluarea probabilitatii de eroare a fiecarui sistem particular de codificare/decodificare este relativ dificila. Meritul teoremei lui Shannon a fost ca, in locul constructiei unui sistem optim si evaluarii ulterioare a probabilitatii sale de eroare sa calculeze probabilitatea medie de eroare-bloc pentru toate codurile si sa demonstreze ca aceasta valoare medie este mica. Prin urmare exista coduri cu probabilitate mica de interventie a unei erori-bloc. Pentru a demonstra ca probabilitatea maxima de eroare este de asemenea mica, se modifica unul din codurile obtinute prin inlaturarea celor mai ineficiente 50% din cuvintele de cod.

Construim un sistem de codificare/decodificare, de rata R, astfel:

Se fixeaza P(x) si se genereaza aleator cele 2NR cuvinte de cod ale unui cod bloc (N, NR=K), notat C, astfel incat:

Codul este cunoscut atat de receptor cat si de transmitator.

Se alege aleator un mesaj din multimea {1, 2, …,2NR} si se transmite x(m). Semnalul receptat este y, pentru care

Semnalul se decodifica prin intermediul unui decodificator de combinare tipica: se decodifica y prin m daca (x(m), y) sunt in combinatie tipica si nu exista m astfel incat (x(m), y) sa fie de asemenea in combinatie tipica; in caz contrar se declara esec de decodificare (m = 0).

Observatie: Acesta nu este algoritmul optim de decodificare, insa este foarte usor de analizat.

Daca mm intervine o eroare in codificare.

Exista trei tipuri de probabilitati de eroare:

1 – Probabilitatea de interventie a unei erori – bloc pentru un cod particular C (oarecum dificil de evaluat):

pB(C) = P(mm / C)

2 – Probabilitatea medie de interventie a unei erori aplicata tuturor codurilor posibile (mult mai usor de evaluat):

3 – Probabilitatea maxima de interventie a unei erori-bloc specifica unui cod C:

Ne propunem sa demonstram ca exista un cod C cu rata specificata si o probabilitate maxima de eroare mica. Vom obtine acest rezultat calculand in prealabil probabilitatea medie de interventie a unei erori-bloc, <pB>.Daca se poate obtine o astfel de probabilitate mai mica decat un numar > 0, rezulta ca exista cel putin un cod C a carui probabilitate de eroare-bloc este mai mica decat . In final vom demonstra ca acest cod, a carui probabilitate maximala de eroare este necunoscuta, poate fi modificat, obtinandu-se astfel un cod cu o probabilitate de eroare foarte mica.

Exista doua surse de eroare la decodificarea in combinare tipica:

1 – iesirea y nu este in combinatie tipica cu cuvantul de cod transmis x(m).

2 – mai exista un cuvant de cod in combinatie tipica cu y.

Prin simetria constructiei codului, probabilitatea medie de eroare a tuturor codurilor nu depinde de valoarea m selectata; prin urmare, putem presupune fara a pierde din generalitate ca m = 1.

Probabilitatea ca (x(1), y) sa nu fie in combinatie tipica tinde spre 0, argumentatia in favoarea acestei afirmatii fiind asigurata de teorema de combinare tipica. Notand cu limita superioara a acestei probabilitati, care verifica 0 (N). Asadar, , N() astfel incat P((x(1), y)JN) .

Pentru m 1, P((x(m), y)JN) 2-N(I(X;Y)-3) din partea a treia a teoremei mai sus mentionate. Rezulta:

Deci <pB> < 2 pentru N suficient de mare, daca R < I(X;Y) – 3.

Vom face in continuare trei modificari:

1 – Alegem distributia optima de intrare a canalului P(x). Conditia R < I(X;Y) – 3 devine R<C – 3.

2 – Cum probabilitatea medie de eroare asupra tuturor codurilor este mai mica decat 2, rezulta ca exista un cod cu probabilitatea de eroare pB(C) < 2.

3 – Pentru a demonstra ca nu doar media, ci si probabilitatea maximala de eroare, pBM poate deveni oricat de mica, modificam codul prin indepartarea celor mai ineficiente jumatate din cuvintele de cod – cele predispuse in cea mai mare masura la a crea erori. Cele ramase vor avea probabilitatea conditionala de eroare mai mica decat 4. Noul cod va avea 2NR-1 cuvinte de cod, adica s-a redus neglijabil rata de la R la R-(1/N), iar pBM < 4.

In concluzie, am obtinut un cod de rata R – (1/N), unde R<C-3 si probabilitatea maxima de eroare este mai mica decat 4. Obtinem prima parte din enuntul teoremei considerand R = (R+C)/2, = /4, <(C – R)/3 si N suficient de mare pentru restul conditiilor.

3.4.1.3 Comunicarea peste capacitate

Am demonstrat ca, pentru orice canal discret fara memorie, exista o zona accesibila a planului R, pb (fig 3.).

pb

Zona admisa

C R

Am demonstrat de asemenea ca orice canal predispus la erori de transmisie poate fi transformat intr-un canal binar esential fara erori cu o rata care tinde crescator spre C biti/ciclu. Vom extinde limita zonei admise pentru rate de eroare nenule.

Avand in vedere ca putem “transforma” un canal cu pierderi intr-unul perfect cu o rata mai mica de transmitere, este suficient sa consideram comunicarea cu erori printr-un canal fara pierderi. Cat de repede se poate realiza comunicarea printr-un canal fara pierderi, daca erorile sunt permise?

Sa consideram un canal binar fara pierderi in comunicare si presupunem ca dorim sa asiguram comunicarii o rata mai mare decat capacitatea canalului, de 1 bit. De exemplu, daca solicitam dispozitivului de transmisie sa comunice la o rata de R = 2 biti / ciclu, atunci se va pierde jumatate din informatia transmisa. Care este cea mai buna modalitate de abordare a acestei situatii, in cazul in care obiectivul vizat este obtinerea celei mai mici probabilitati de eroare elementara posibila? O metoda simpla este de a comunica 1/R din sirul de biti ai mesajului sursa si de a-i ignora pe restul. Receptorul va prezice aleator fractia lipsa, 1 – (1/R), probabilitatea medie de eroare elementara obtinuta fiind pb = ½ (1 – (1/R)).

Se poate obtine un rezultat mai bun, in sensul minimizarii pb, prin extinderea riscului de denaturare asupra tuturor bitilor. Valoarea optima este pb = H2-1(1 – (1/R)) si vom prezenta in continuare metoda de abordare corespunzatoare. Vom folosi codul (N,K) pentru canale binare simetrice cu pierderi, definind dispozitivul de compresie pe baza decodificatorului asociat codului. Presupunem ca un astfel de cod are o rata R=K/N si ca este capabil sa realizeze corectarea erorilor introduse de un canal simetric binar a carui probabilitate de tranzitie este q. Exista coduri de rata R astfel incat R1-H2(q). Sa observam ca, daca asociem unui canal simetric binar un astfel de cod de lungime N atunci:

distributia de probabilitate a iesirilor este aproape uniforma in conditiile in care entropia iesirii este egala cu entropia sursei plus entropia asociata producerii erorilor.

Decodificatorul optim al codului, in aceasta situatie, translateaza vectorul receptionat de lungime N intr-un vector ce difera prin qN biti de vectorul receptionat.

Mesajul care se doreste a fi transmis se segmenteaza in blocuri de lungime N. Se transfera fiecare bloc decodificatorului si se obtine un semnal mai scurt, de K biti, ce urmeaza a fi comunicat prin intermediul canalului fara pierderi. Pentru a decodifica transmisia, se transfera mesajul de K biti codificatorului asociat codului original. Mesajul reconstituit difera de mesajul original in unele pozitii – de regula qN dintre ele. Astfel, probabilitatea de eroare elementara va fi pb = q, iar rata de compresie R = N/K = 1/R = 1 / (1 – H2(pb)).

Asociind acest model de compresie sistemului de comunicare fara erori caracterizat de capacitatea C, obtinem o zona permisa descrisa de:

Zona nepermisa

Sursa, codificatorul, canalul cu pierderi si decodificatorul definesc un lant Markov: P(m,x,y,m) = P(m) P(x/m) P(y/x) P(m/y). Din definitia capacitatii canalului rezulta I(X;Y) NC si cum I(m;m) I(X;Y) (David J.C. MacKay, p220) rezulta I(m; m) NC. Presupunem ca sistemul realizeaza o rata R si o probabilitate de eroare elementara pb. Rezulta I(m;m)NR(1 – H2(pb)). Cum I(m;m) > NC nu este permisa rezulta ca R > C / (1 – H2(pb)) nu este permisa.

3.4.1.4 Variante ale teoremei de codificare

Teorema de codificare cu pierderi prezentata si demonstrata anterior este oarecum generala. Ea afirma posibilitatea de realizare a unei comunicari cu o rata R si o probabilitate de eroare utilizand coduri cu lungimea de bloc N suficient de mare, nespecificand insa cat de mare trebuie sa fie N pentru a obtine valorile R si dorite.

Teorema de codificare cu pierderi (versiunea cu N-dependenta explicita)

Pentru un canal discret fara memorie, pentru valori precizate ale N si R, exista coduri-bloc de lungime N a caror probabilitate medie de eroare satisface pBe-NEr(R), unde Er(R) este exponentul de codificare aleatoare a canalului, o functie convexa, descrescatoare si pozitiva, definita pentru 0R<C.

Nota: Definitia explicita a termenului Er(R) este data in Gallanger(1968), p.139.

Observatie: Er(R)0 daca RC.

3.4.2 Compresia cu distorsionarea informatiei

3.4.2.1 Masura de distorsie. Definitie. Proprietati.

Uneori se dorește reprezentarea ieșirii unei surse cu o rată mai mică decât entropia sursei. Nu există nici un astfel de cod de compactare, prin urmare nici o reprezentare care utilizează un cod de compactare nu va descrie ieșirea sursei exact. O astfel de reprezentare distorsionată se numește cod de compresie a datelor . Un cod de compresie omite în mod intenționat detaliile fine ale datelor. Ieșirea sursei nu va fi recuperată exact; intervine o anumită distorsie . Prin urmare, obiectivul principal urmărit în construirea codurilor de compresie constă în minimizarea distorsiei.

Ne propunem să determinăm cantitatea de informație necesară pentru descrierea ieșirii sursei cu o rată maximă de distorsie permisă.

O matrice de distorsie este o matrice de dimensiune JxK cu elemente nenegative ρjk, unde elementul jk specifică distorsia asociată codificării celui de-al j-lea simbol al sursei prin simbolul k de reproducere. Cel mai mare element al matricei se notează cu ρm.

De regulă ρm este finit, iar matricea de distorsie asigură implicit o limită a distorsiei. Se poate presupune că, pentru orice simbol-sursă, există cel puțin un simbol de reproducere astfel încât distorsia rezultată în urma reprezentării respective să fie nulă. Altfel, se înlocuiește matricea de distorsie cu o nouă matrice, dată de elementele ρ'jk = ρjk – mink ρjk. Distorsia medie a unei scheme de compresie ce utilizează ρ'jk diferă de cea care utilizează ρjk prin

adică printr-o constantă independentă de codul de compresie. Nu se afecteaza cu nimic generalitatea dacă vom presupune că această constantă este nulă.

O matrice de distorsie asociată unui bloc de litere de lungime n este o matrice KnxJn cu elemente ρ(x,y) nenegative, unde elementul ρ(x,y) specifică distorsia apărută la reprezentarea cuvântului-sursă x prin cuvântul de reproducere y. Adesea ρ(x,y) are o structură simplă, numită măsură singulară de distorsie, în care distorsia prezentă în cadrul unui bloc este dată de suma distorsiilor specifice fiecărui simbol al blocului:

ρ(x,y) = ρj1k1+ρj2k2+…+ρjnkn.

In caz contrar, se numeste măsură de distorsie dependentă de context. O astfel de măsură este mult mai potrivită pentru aplicațiile practice, însă modelarea sa matematică este foarte dificilă. Prin urmare, vom studia prim categorie.

O matrice de distorsie importantă este matricea de distorsie în probabilități de erori, în cazul căreia alfabeturile coincid, iar 0 , dacă j=k

ρjk =

, altfel

Această matrice indică faptul că fiecare eroare este referită ca o unitate de distorsie.

Definiție: Un cod – bloc de compresie de date de dimensiune M și caracterizat prin lungimea de bloc n este o mulțime C ce constă în M cuvinte de cod de lungime n, fiecare cuvânt de cod fiind o secvență de n simboluri de reproducere.

O modalitate de utilizare a codurilor de compresie a datelor este următoarea: mulțimea de cuvinte de cod se partiționează în două mulțimi disjuncte C1 și C2. Mulțimea C1 conține primele M-1 cuvinte de cod, numite cuvinte de cod normale, iar mulțimea C2 conține doar ultimul cuvânt, numit indicator de eroare. Fiecare cuvânt – sursă de lungime n se codifică prin intermediul primelor M-1 cuvinte de cod astfel încât distorsia blocului să fie minimă și să nu depășească un prag maxim permis, notat nD. In caz contrar, cuvântului-sursă i se asociază indicatorul de eroare, situație în care se spune că intervine un eșec în codificare.

Cuvântul-sursă de ieșire este aleator, astfel că distorsia-bloc a codului C este tot o variabilă aleatoare, prin urmare valoarea sa referă distorsia medie a blocului, notată ρ(C), dată de formula ρ(C) = E ρ(x,y(x)), unde y(x) reprezintă cuvântul de cod prin care s-a codificat x. Vom analiza limitele de rată necesare fiecărui cod-bloc de compresie astfel încât media distorsiei singulare să satifacă relația (1/n) ρ(C) D. Acest lucru conduce la concluzia că, în cazul unor codificări corespunzătoare, aproape toate cuvintele de cod au distorsia-bloc mai mica sau egala cu nD.

Rata minimă ce poate fi obținută în cazul unui cod cu o distorsie medie singulară D se notează cu B(D) și se numește funcție de distorsie a sursei. Aceasta măsoară conținutul condensat (redus) de informație la distorsia D.

3.4.2.2 Conținutul de informație al datelor comprimate. Functia de distorsie

Compresia datelor este un proces determinist. Același bloc de simboluri-sursă va produce întotdeauna același bloc de simboluri de reproducere. Mai mult, atunci când atenția se restrânge asupra unui singur simbol-sursă de ieșire (sau a unui subbloc relativ mic) fără eventuale cunoștințe asupra simbolurilor anterioare ori a poziției acestui simbol în bloc, atunci simbolul de reproducere nu este predeterminat. Astfel, la nivelul unui singur simbol, simbolul bk prin care se codifică aj poate fi privit ca o variabilă aleatoare, deși la nivel de bloc, codificarea este deterministă. Această variabilă aleatoare este descrisă de o matrice de tranziție Q, a cărei entropie Q(bk/aj), abreviată Qkj, dă probabilitatea ca simbolul aj să fie codificat prin bk. Vom gândi Q ca o descriere a unui canal artificial fără memorie care aproximează compresia datelor. De fiecare dată când sursa transmite simbolul aj, acesta este codificat prin simbolul bk cu probabilitatea Qk/j.

Vom arăta că într-un cod de compresie construit corespunzător, simbolul de reproducere bk va apare, condițional cu simbolul-sursă aj, cu probabilitatea Qk/j astfel încât informația medie mutuală dintre cele două simboluri să fie minimă în condiții de distorsie medie. Intr-un cod-bloc de lungime a blocului n, informația mutuală medie dintre cuvântul-sursă și cuvântul de cod este

I(Xn;Yn) = H(Yn) – H(Yn/Xn)

Dar H(Yn/Xn) = 0, întrucât codificarea se face determinist. Prin urmare minimizarea informației mutuale este echivalentă cu minimizarea entropiei H(Yn).

Definiție: Funcția de distorsie a sursei B(D) este dată de formula

iar 2D = {Q: d(Q) D}, unde d(Q) reprezinta distorsia medie, definita prin:

Funcția B(D) se măsoară în biți dacă se utilizează logaritmul în baza 2 și se va utiliza ulterior în teorema de codificare. Intuitiv, dacă se specifică o distorsie medie D, atunci orice cod de compresie va utiliza în medie cel puțin B(D) biți pe simbol-sursă și reciproc, este posibilă efectuarea unei compresii la o rată oricât de apropiată de B(D) (nu

mai mică) prin alegerea unui cod corespunzător de compresie.

Funcția B(D) depinde de distribuția de probabilitate p. Când va fi nevoie să punem în evidență această dependență, vom scrie B(p, D). Pentru o dimensiune fixă a alfabetului-sursă J și o matrice de distorsie {jk}, va exista o distribuție de probabilitate a alfabetului-sursă pentru care compresia e cea mai dificilă.

Definim B*(D) = maxp B(p,D). Prin urmare, rezultă B(p,D) B*(D), p.

Uneori este mai convenabilă utilizarea inversei lui B(D). Aceasta se defineste prin interschimbarea elementelor în definiția lui B(D).

Pentru sursele simple, B(D) poate fi evaluată prin determinarea analitică a minimului. Pentru problemele mai dificile, există un algoritm eficient de calcul. Vom demonstra că dacă simbolurile-sursă sunt echiprobabile, iar matricea de distorsie este una în probabilități de eroare, atunci distribuția condițională de probabilitate Q, care asigură funcția B(D) are aceeași valoare pentru orice element diagonal. Intuitiv, aceasta afirmă că dacă sursa și matricea de distorsie tratează toate elementele la fel, atunci în secvența comprimată erorile vor apărea cu aceeași probabilitate pentru fiecare simbol.

Teorema 3.15: B(D) este o functie descrescatoare, convexa si continua definita pe intervalul 0 D Dmax, unde

Demonstratie: Vom demonstra teorema pe intervalul 0<D<Dmax.

Daca D<0 2D = , deci B(D) nu poate fi definita.

Daca D0 2D2D daca D>D, de unde rezulta ca B(D) B(D).

Fie Dmax cea mai mica distorsie medie care poate fi obtinuta cu informatie 0, adica cea mai mare distorsie tolerata de sursa respectiva. Intrucat I(p;Q) = 0 Qk/j = Qk. Deci expresia distorsiei medii devine:

Cea mai mica valoare D este Dmax. Distorsia Dmax se obtine prin alegerea simbolului bk, unde k realizeaza minimul anterior.

Pentru a demonstra convexitatea lui B(D) se aleg doua puncte arbitrare (D,B(D)) si (D,B(D)) si matricele de tranzitie Q si Q corespunzatoare. Fie [0,1] si Qk/j = Qk/j + (1-)Qk/j. Se obtine o distributie de probabilitate conditionala. Distorsia medie asociata lui Q este:

si Q2D. Deci B(D)I(p;Q). Cum I(p;Q) este convexa in Q rezulta:

B(D) I(p;Q)+(1-)I(p;Q), prin urmare: B(D+(1-)D) B(D)+(1-)B(D).

Intrucat B(D) este convexa pe [0,Dmax], este continua pe (0, Dmax).

Functia B(D) se poate exprima cu ajutorul unui multiplicator Lagrange astfel:

unde asupra lui Q nu se impune nici o constrangere cu exceptia conditiei sa fie o matrice de probabilitati de tranzitie. Pentru fiecare alegere a multiplicatorului Lagrange s, minimul se atinge pentru cate o matrice de tranzitie Q*. Astfel, multiplicatorul Lagrange s devine parametru independent. Valoarea lui D pentru care a fost gasita solutia e data de formula:

Obiectivul urmarit este de a da un algoritm eficient de calcul pentru B(D). Vom enunta in continuare, fara demonstratie, o teorema care extinde problema curenta de minimizare la o problema de minimizare dubla:

Teorema 3.16: Functia de distorsie B(D) se poate exprima ca dublu minim astfel:

unde si Q* realizeaza minimul. Pentru Q fixat, membrul drept este minimizat de , iar pentru q fixat, minimul se realizeaza pentru .

Corolar:

unde q* realizeaza B(Ds).

Teorema 3.17: Consideram dat parametrul s<0 si fie . Fie q(0) un vector de probabilitate cu componente nenule. Definim recurent sirul q(k) astfel:

Atunci: si , unde si (Ds, B(Ds)) este un punct al curbei B(D) parametrizat de s.

Demonstratie: Vom nota prescurtat I(q) = I(p;Q(q)) si V(q) = I(q) – sD(q), unde . Pentru a demonstra ca V(q) este descrescatoare, se utilizeaza teorema 3.16, fixand initial q si minimizand dupa Q, apoi invers. Minimizarea dupa Q ne conduce la o valoare W(q(r)) situata intre V(q(r+1)) si V(q(r)), data de formula:

In urma minimizarilor succesive se obtine secventa descrescatoare:

…V(q(r)) W(q(r)) V(q(r+1)) W(q(r+1)) …

Compunerea celor doua operatii anterioare da definitia recursiva a sirului q(r) din teorema, construit astfel incat q(r) are doar componente pozitive si V(q(r)) este descrescatoare. Intrucat V(q(r)) este marginit, V(q(r)) converge catre un numar V. Ramane de demonstrat ca V=B(D)-sD.

Consideram Q(r+1) = Q(q(r)). Fie q* astfel incat V(q*)=B(D) – sD si Q*=Q(q*). Atunci:

Rezulta:

Deci:

Prin sumare dupa r, rezulta:

Schimband semnul, obtinem inegalitatea: , unde L este functia de discriminare, definita prin care descrie informatia obtinuta in urma unei masuratori asupra valorii de adevar a unei ipoteze date in comparatie cu a doua alternativa.

Cum W(q(r))>V(q*) iar sirul este descrescator, rezulta ca W(q(r))-V(q*) > 0 si va tinde spre zero pentru r, ceea ce implica W(q(r))V(q*).

Teorema 3.18:

unde

Demonstratie: Fie s0, As si Q2D. Cum , rezulta:

Deci . Pentru anumite valori ale s si (in particular pentru ,unde s si q* obtin B(D) ) inegalitatea de mai sus devine egalitate.

Teorema 3.19: Consideram dat parametrul s 0, si fie .Presupunem ca q este un vector oarecare de probabilitate si . Atunci, in punctul sunt adevarate afirmatiile:

(i)

(ii)

Demonstratie: (i) Matricea cu elementele este o matrice de tranzitie ce asigura o distorsie D. Atunci:

(ii) Din teorema 3.18 rezulta ca s 0, unde este un vector oarecare astfel incat jpjjAjk 1.

Fie si .

Rezulta:

Prezentam in continuare algoritmul pentru calculul functiei de distorsie:

Intrare: s, qk=qk0.

Calculeaza

Calculeaza .

Daca TU-TL< atunci mergi la pasul 4.

Altfel mergi la pasul 2.

Stop.

Observatie: Daca notam Bn(D) functia de distorsie la nivel de bloc de lungime n a unei surse fara memorie, atunci Bn(nD) = nB(D). (Demonstratie: R. Blahut – “Principles and Practice of Information Theory”,Addison Wesley 1987)

3.4.2.3 Teoreme de codificare.

Definitie: Fie jk o matrice de distorsie singulara. Definim functia de incredere asociata codurilor de compresie pentru surse discrete fara memorie de distributie de probabilitate p astfel: , sau echivalent,

,unde .

Functia de incredere F(R,D) are urmatoarele proprietati:

1.Pentru D fixat F(R,D) este definita pentru rate RB*(D), unde B*(D) este cea mai mare valoare a functiei de distorsie a oricarei surse descrisa de alfabetul si matricea de distorsie specificate.

2.F(R,D) este convexa si crescatoare in ambele argumente.

3.

Teorema 3.20: Este posibila selectarea a M = enR secvente de cod de lungime n astfel incat probabilitatea de aparitie a unei secvente-sursa care nu se poate codifica cu o distorsie bloc de cel mult nD sa satisfaca conditia pee-nF(R,D)+o(n), unde o(n)0 (pt n)

Demonstratie: R. Blahut – “Principles and Practice of Information Theory”, Addison Wesley 1987

Teorema a treia a lui Shannon: Pentru orice sursa discreta fara memorie cu masura de distorsie marginita se poate determina un cod-bloc de rata R si lungime n suficient de mare astfel incat distorsia medie singulara sa fie mai mica decat D, in conditiile in care R>B(D).

Demonstratie: Rezulta pe baza teoremei 3.20 si a proprietatii 3, mentionate anterior.

Teorema reciproca (Shannon): Rata oricarui cod-bloc de lungime n si distorsie medie singulara D asociat unei surse discrete fara memorie satisface proprietatea RB(D).

Demonstratie: Fie x o secventa-sursa de lungime n si y o secventa de reproducere de lungime n.

Definim urmatoarea matrice de probabilitate conditionala:

Distorsia-bloc medie a codului este: Pe baza definitiei functiei B(D), cum Bn(nD) = nB(D), rezulta:

Pe baza definitiei lui rezulta: ,

unde .Intrucat q(y)0 numai pentru secvente de cod rezulta:

.

Teoremele a doua si a treia ale lui Shannon pentru compresia cu pierderi (de transmisie prin canal si de codificare a sursei) pot fi combinate intr-un singur enunt (teorema de transmitere a informatiei). Alfabetul sursei poate diferi de alfabetul canalului, aspect nesemnificativ atata timp cat continutul sursei (B(D)) si capacitatea canalului se exprima in unitati consistente, de exemplu biti/simbol.

Teorema (de transmitere a informatiei): Secventa emisa de o sursa discreta fara memorie de continut informational B(D) poate fi reprodusa cu o distorsie de cel mult D la iesirea oricarui canal discret fara memorie de capacitate C, daca C >B(D).

Demonstratie: Vom demonstra initial ca secventa emisa de sursa se poate reproduce cu o distorsie de maxim D+, pentru orice >0.

Alegem astfel incat C – B(D) si un cod de compresie a sursei astfel incat distorsia medie sa nu depaseasca D, iar rata codului R<B(D)+(/2). Existenta unui astfel de cod este asigurata de teorema a treia a lui Shannon. Entropia codificatorului de sursa nu depaseste B(D)+(/2), asadar, pe baza teoremei a doua a lui Shannon, mesajele sursei pot fi transmise cu o probabilitate de eroare oricat de mica, pentru o rata de cod de cel mult B(D)+(/2)+(/2). Probabilitatea de eroare elementara fiind mica, distorsia aditionala datorata erorilor de canal va fi de asemenea oricat de mica, datorita faptului ca distorsia cauzata de o eroare de decodificare la nivel de bloc variaza liniar, in timp ce probabilitatea unei astfel de erori de decodificare descreste exponential in functie de lungimea blocului. Intregul sistem poate asigura o distorsie mai mica decat D+.

Inlocuind D cu D-, obtinem o distorsie a sistemului D daca C>B(D-) pentru orice . Intrucat B(D) este continua, rezulta ca sistemul obtine distorsia D daca C>B(D).

In practica, numarul de simboluri produse de sursa in fiecare secunda nu corespunde in mod necesar cu numarul de simboluri acceptate de canal in fiecare secunda. Prin urmare este necesara normalizare sistemului de transmitere a informatiei in functie de intervalul de timp.

Teorema de transmitere a informatiei (varianta): Mesajele unei surse discrete fara memorie de continut informational B(D) biti/simbol care emite 1/Ts simboluri pe secunda pot fi reproduse cu o distorsie de maxim D la iesirea unui canal de capacitate C biti/simbol, care transmite 1/Tc simboluri pe secunda, daca .

=== Capitolul 4 ===

Capitolul 4.

Descrierea aplicației

Gândită ca o completare demonstrativă a studiului teoretic întreprins în capitolele anterioare asupra problemei compresiei de imagini, aplicația care însoțește lucrarea de față realizează compresia fișierelor text specificate de utilizator. Procedurile de compresie, respectiv de decompresie sunt realizate în limbajul C și se bazează pe algoritmul LZW descris pe larg în capitolul 2, iar interfața grafică asociată este concepută în Visual C++ 6.0.

….interfata…………..

La lansarea aplicației, prin intermediul interfeței grafice ilustrată în figura 4.1, se solicită utilizatorului introducerea (specificarea) numelui fișierului text ce urmează a fi comprimat, operație care poate fi realizată prin acționarea cu ajutorul mouse-ului a butonului “Introducere fișier”. Textul introdus va conține maxim 7 caractere, plus extensia (.txt). Operația propriu-zisă de compresie se realizează prin acționarea butonului de comandă “comprimare”. La sfârșitul executării procedurii de compresie, se obțin două fișiere rezultat: “test.lzw” – fișierul obținut în urma aplicării metodei LZW de compresie asupra fișierului specificat, și “test.txt” – fișierul reconstituit, care este identic cu fișierul care a fost supus procedurii de compresie.

Vizualizarea fișierelor rezultat se poate realiza prin intermediul butonului “vizualizare”. Prin acționarea butonului “ieșire” se părăsește aplicația.

Analiza rezultatelor

Evaluarea și analiza rezultatelor aplicării unei proceduri de compresie, indiferent de algoritmul care stă la baza conceperii ei, este un proces oarecum dificil, întrucât nivelul (rata) de comprimare depinde într-o mare măsură de trăsăturile particulare ale imaginii (în cazul nostru al textului) asupra căreia urmează a fi aplicată procedura respectivă.

Metoda LZW de compresie conservă întregul conținut de informație al fișierului ( este o metodă reversibilă, fără pierderi de informație) și obține rezultate bune în cazul aplicării ei asupra unor fișiere imagine care conțin date (șiruri de caractere) repetitive, motiv pentru care funcționează foarte bine la comprimarea fișierelor text. Se obțin valori ale ratei de compresie în jur de 2:1 sau chiar mai bune.

Programul a fost testat pentru fișirele exemplu test1.txt (55 kB) și test2.txt (5 kB). În urma aplicării procedurii de compresie s-au obținut fișierele rezultat test1.lzw (25 kB) respectiv test2.lzw (3 kB). Prin urmare, în cazul primei testări, s-a obținut o rată de compresie de 2.2:1, iar în cazul celei de-a doua testări, o rată de 1.6:1.

Figura 4.2(a) prezintă o pagină de text a fișierului inițial “test1.txt”, iar 4.2(b) aceeași pagină de text a fișierului rezultat în urma reconstituirii. Se observă că cele două pagini de text sunt identice.

Fig. 4.2: (a) O pagină din fișierul inițial “test1.txt”;

(b) Aceeași pagină a fișierului rezultat după aplicarea procedurilor de compresie și

decompresie.