retele, retele de calculatoare

Upload: gorbuleakvalera

Post on 14-Oct-2015

389 views

Category:

Documents


6 download

DESCRIPTION

Retele de calculatoare, Retele de calculatoare , Retele de calculatoareRetele de calculatoareRetele de calculatoareRetele de calculatoare Retele de calculatoare Retele de calculatoare

TRANSCRIPT

  • Retele de calculatoare

    Principii

    Radu-Lucian Lupsa

  • Aceasta este editia electronica a cartii Retele de calculatoare, publicata laCasa Cartii de Stiinta, ^n 2008, ISBN: 978-973-133-377-9.

    Drepturile de autor apartin subsemnatului, Radu-Lucian Lupsa.Subsemnatul, Radu-Lucian Lupsa, acord oricui doreste dreptul de a copia

    continutul acestei carti, integral sau partial, cu conditia atribuirii corecte autorului sia pastrarii acestei notite.

    Cartea poate descarcata gratuit de la adresahttp://www.cs.ubbcluj.ro/~rlupsa/works/retele.pdf

  • c 2008, Radu-Lucian Lupsa5

    Cuprins

    Principii

    Cuprins 5

    Prefata 13

    1 Introducere 15

    1.1 Serviciile oferite de retea . . . . . . . . . . . . . . . . . . . . . . . . . 15

    1.2 Principalele elemente ale unei retele de calculatoare . . . . . . . . . . 20

    1.3 Premise generale ^n elaborarea si implementarea protocoalelor ^n retele. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

    2 Notiuni de teoria informatiei 25

    2.1 Problema codicarii informatiei pentru un canal discret . . . . . . . . 26

    2.2 Coduri cu proprietatea de prex . . . . . . . . . . . . . . . . . . . . . 29

    2.2.1 Reprezentarea arborescenta a codurilor prex . . . . . . . . . . . 29

    2.2.2 Decodicarea ^n cazul codurilor prex . . . . . . . . . . . . . . . 31

    2.2.3 Lungimile cuvintelor unui cod prex . . . . . . . . . . . . . . . . 33

    2.3 Coduri optime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

    2.3.1 Cantitatea de informatie . . . . . . . . . . . . . . . . . . . . . . 40

    2.3.2 Lungimea medie a cuvintelor de cod . . . . . . . . . . . . . . . . 41

    2.3.3 Generarea codului optim prin algoritmul lui Human . . . . . . 44

    2.3.4 Compresia sierelor . . . . . . . . . . . . . . . . . . . . . . . . . 50

    2.4 Coduri detectoare si corectoare de erori . . . . . . . . . . . . . . . . . 51

    2.4.1 Modelul erorilor . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

    2.4.2 Principiile codurilor detectoare si corectoare de erori . . . . . . . 53

    2.4.3 Ca^teva coduri detectoare sau corectoare de erori . . . . . . . . . 55

    2.4.3.1 Bitul de paritate . . . . . . . . . . . . . . . . . . . . . . . . 55

    2.4.3.2 Paritate pe linii si coloane . . . . . . . . . . . . . . . . . . . 55

    2.4.3.3 Coduri polinomiale . . . . . . . . . . . . . . . . . . . . . . . 56

    2.4.4 Coduri detectoare si corectoare de erori ^n alte domenii . . . . . 57

  • c 2008, Radu-Lucian Lupsa6 Cuprins

    3 Nivelul zic 593.1 Problema transmisiei informatiei la nivelul zic . . . . . . . . . . . . 593.2 Transmiterea semnalelor . . . . . . . . . . . . . . . . . . . . . . . . . 60

    3.2.1 Modicarile suferite de semnale . . . . . . . . . . . . . . . . . . . 603.2.2 Analiza transmiterii semnalelor cu ajutorul transformatei Fourier

    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623.3 Codicarea informatiei prin semnale continue . . . . . . . . . . . . . 65

    3.3.1 Scheme de codicare . . . . . . . . . . . . . . . . . . . . . . . . . 653.3.2 Modulatia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 683.3.3 Multiplexarea ^n frecventa . . . . . . . . . . . . . . . . . . . . . 713.3.4 Capacitatea maxima a unui canal de comunicatie . . . . . . . . . 71

    3.4 Transmisia prin perechi de conductoare . . . . . . . . . . . . . . . . . 723.4.1 Constructia cablului . . . . . . . . . . . . . . . . . . . . . . . . . 723.4.2 Proprietati ale mediului . . . . . . . . . . . . . . . . . . . . . . . 743.4.3 Legatura magistrala . . . . . . . . . . . . . . . . . . . . . . . . . 753.4.4 Considerente practice . . . . . . . . . . . . . . . . . . . . . . . . 76

    3.5 Transmisia prin unde radio . . . . . . . . . . . . . . . . . . . . . . . . 773.5.1 Propagarea undelor . . . . . . . . . . . . . . . . . . . . . . . . . 78

    3.5.1.1 Polarizarea . . . . . . . . . . . . . . . . . . . . . . . . . . . 783.5.1.2 Absorbtia si reexia . . . . . . . . . . . . . . . . . . . . . . 793.5.1.3 Difractia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 793.5.1.4 Interferenta undelor . . . . . . . . . . . . . . . . . . . . . . 803.5.1.5 Divergenta undelor . . . . . . . . . . . . . . . . . . . . . . . 80

    3.5.2 Antene . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 803.5.2.1 Directivitatea . . . . . . . . . . . . . . . . . . . . . . . . . . 813.5.2.2 Polarizarea . . . . . . . . . . . . . . . . . . . . . . . . . . . 833.5.2.3 Tipuri de antene . . . . . . . . . . . . . . . . . . . . . . . . 83

    3.5.3 Raza de actiune a unei legaturi radio . . . . . . . . . . . . . . . 833.5.3.1 Obstacolele . . . . . . . . . . . . . . . . . . . . . . . . . . . 833.5.3.2 Linia orizontului . . . . . . . . . . . . . . . . . . . . . . . . 843.5.3.3 Utilizarea satelitilor articiali ai Pama^ntului . . . . . . . . . 843.5.3.4 Zgomotul . . . . . . . . . . . . . . . . . . . . . . . . . . . . 853.5.3.5 Scaderea puterii cu distanta . . . . . . . . . . . . . . . . . . 863.5.3.6 Emisia directionata si polarizata . . . . . . . . . . . . . . . 86

    3.5.4 Spectrul radio si alocarea lui . . . . . . . . . . . . . . . . . . . . 863.5.5 Particularitati ale sistemelor de comunicatie prin radio . . . . . 88

    3.5.5.1 Topologia legaturii . . . . . . . . . . . . . . . . . . . . . . . 883.5.5.2 Fiabilitatea . . . . . . . . . . . . . . . . . . . . . . . . . . . 893.5.5.3 Securitatea . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

    3.6 Transmisia optica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 893.6.1 Constructia mediului . . . . . . . . . . . . . . . . . . . . . . . . 90

    3.6.1.1 Conectarea brelor optice . . . . . . . . . . . . . . . . . . . 913.6.2 Propagarea semnalului optic . . . . . . . . . . . . . . . . . . . . 91

    3.6.2.1 Moduri de propagare . . . . . . . . . . . . . . . . . . . . . . 91

  • c 2008, Radu-Lucian LupsaCuprins 7

    3.6.2.2 Caracteristici ale mediului . . . . . . . . . . . . . . . . . . . 923.6.2.3 Multiplexarea ^n lungimea de unda . . . . . . . . . . . . . . 92

    3.6.3 Considerente practice . . . . . . . . . . . . . . . . . . . . . . . . 93

    4 Nivelul legaturii de date 954.1 Detectarea si corectarea erorilor . . . . . . . . . . . . . . . . . . . . . 964.2 Controlul accesului la mediu . . . . . . . . . . . . . . . . . . . . . . . 97

    4.2.1 Protocoale bazate pe asigurarea unui interval exclusiv de emisie . 984.2.2 Protocoale bazate pe coliziuni si retransmitere . . . . . . . . . . 994.2.3 Protocoale mixte . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

    4.3 Retransmiterea pachetelor pierdute . . . . . . . . . . . . . . . . . . . 1024.3.1 Principiul conrmarilor pozitive si retransmiterilor . . . . . . . . 1034.3.2 Trimiterea ^n avans a mai multor pachete . . . . . . . . . . . . . 1084.3.3 Spatiul numerelor de conrmare . . . . . . . . . . . . . . . . . . 109

    4.4 Controlul uxului . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1144.4.1 Cereri de suspendare si de continuare . . . . . . . . . . . . . . . 1154.4.2 Mecanismul pas cu pas . . . . . . . . . . . . . . . . . . . . . . . 1154.4.3 Mecanism combinat cu retransmiterea pachetelor pierdute . . . . 116

    4.5 Multiplexarea ^n timp . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

    5 Nivelul retea si nivelul transport 1195.1 Retransmiterea datelor de catre nodurile intermediare . . . . . . . . . 120

    5.1.1 Retransmiterea ^n retele bazate pe datagrame . . . . . . . . . . . 1225.1.2 Retransmiterea ^n retele bazate pe conexiuni . . . . . . . . . . . 122

    5.2 Algoritmi de dirijare . . . . . . . . . . . . . . . . . . . . . . . . . . . 1255.2.1 Calculul drumurilor cu informatii complete despre graful retelei . 1275.2.2 Calculul drumurilor optime prin schimb de informatii de distanta . 1285.2.3 Dirijarea ierarhica . . . . . . . . . . . . . . . . . . . . . . . . . . 1365.2.4 Metode particulare de dirijare . . . . . . . . . . . . . . . . . . . 139

    5.2.4.1 Inundarea . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1395.2.4.2 I^nvatarea rutelor din adresele sursa ale pachetelor . . . . . 140

    5.2.5 Metode de difuziune . . . . . . . . . . . . . . . . . . . . . . . . . 1405.3 Functionarea la trac ridicat . . . . . . . . . . . . . . . . . . . . . . . 141

    5.3.1 Alegerea pachetelor de transmis . . . . . . . . . . . . . . . . . . 1425.3.2 Controlul congestiei . . . . . . . . . . . . . . . . . . . . . . . . . 1435.3.3 Formarea (limitarea) tracului . . . . . . . . . . . . . . . . . . . 1445.3.4 Rezervarea resurselor . . . . . . . . . . . . . . . . . . . . . . . . 145

    5.4 Nivelul transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1465.5 Interconectarea retelelor . . . . . . . . . . . . . . . . . . . . . . . . . 147

    6 Metode si protocoale criptograce 1496.1 Asigurarea condentialitatii . . . . . . . . . . . . . . . . . . . . . . . 151

    6.1.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1516.1.2 Refolosirea cheilor . . . . . . . . . . . . . . . . . . . . . . . . . . 1546.1.3 Problema spargerii unui cifru . . . . . . . . . . . . . . . . . . . . 155

  • c 2008, Radu-Lucian Lupsa8 Cuprins

    6.1.4 Algoritmi de criptare utilizati ^n practica . . . . . . . . . . . . . 1576.1.5 Criptograe asimetrica (cu cheie publica) . . . . . . . . . . . . . 163

    6.1.5.1 Utilizarea criptograei asimetrice . . . . . . . . . . . . . . . 1646.2 Autenticarea mesajelor . . . . . . . . . . . . . . . . . . . . . . . . . 165

    6.2.1 Functii de dispersie criptograce . . . . . . . . . . . . . . . . . . 1666.2.1.1 Utilizarea functiilor de dispersie . . . . . . . . . . . . . . . . 167

    6.2.2 Functii de dispersie cu cheie . . . . . . . . . . . . . . . . . . . . . 1686.2.3 Semnatura digitala . . . . . . . . . . . . . . . . . . . . . . . . . . 1696.2.4 Vericarea prospetimii mesajelor . . . . . . . . . . . . . . . . . . 1716.2.5 Combinarea criptarii, autenticarii si vericarii prospetimii . . . 173

    6.3 Stabilirea cheilor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1736.3.1 Stabilirea cheilor ^n prezenta unui adversar pasiv . . . . . . . . . 176

    6.3.1.1 Stabilirea cheilor prin criptograe asimetrica . . . . . . . . 1766.3.1.2 Stabilirea cheii prin metoda Die-Hellman . . . . . . . . . 1776.3.1.3 Atacul man-in-the-middle . . . . . . . . . . . . . . . . . . . 178

    6.3.2 Stabilirea cheilor ^n prezenta unui adversar activ . . . . . . . . . 1786.3.3 Stabilirea cheilor cu ajutorul unui tert de ^ncredere . . . . . . . . 1806.3.4 Certicarea cheilor publice . . . . . . . . . . . . . . . . . . . . . 1826.3.5 Transportul prin utilizatori umani . . . . . . . . . . . . . . . . . 183

    6.4 Numere aleatoare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1856.4.1 Generatoare zice . . . . . . . . . . . . . . . . . . . . . . . . . . 1866.4.2 Generatoare de numere pseudoaleatoare . . . . . . . . . . . . . . 1866.4.3 Generatoare utilizate ^n practica . . . . . . . . . . . . . . . . . . 188

    6.5 Autenticarea utilizatorilor . . . . . . . . . . . . . . . . . . . . . . . . 1886.5.1 Stocarea parolelor . . . . . . . . . . . . . . . . . . . . . . . . . . 1886.5.2 Parole de unica folosinta . . . . . . . . . . . . . . . . . . . . . . 189

    Protocoale

    Cuprins 195

    7 Codicari de interes practic 2037.1 Probleme privind reprezentarea numerelor ^ntregi . . . . . . . . . . . 203

    7.1.1 Reprezentari pe biti . . . . . . . . . . . . . . . . . . . . . . . . . 2037.1.1.1 Bitul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2047.1.1.2 Siruri de biti . . . . . . . . . . . . . . . . . . . . . . . . . . 2047.1.1.3 Reprezentarea pe biti a numerelor ^ntregi . . . . . . . . . . 205

    7.1.2 Reprezentari pe octeti . . . . . . . . . . . . . . . . . . . . . . . . 2067.1.2.1 Octeti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2067.1.2.2 Siruri de octeti . . . . . . . . . . . . . . . . . . . . . . . . . 2087.1.2.3 Reprezentarea numerelor pe un numar ^ntreg de octeti . . . 2087.1.2.4 Reprezentarea numerelor pe un sir arbitar de biti . . . . . . 210

    7.1.3 Probleme privind reprezentarea lungimii sirurilor . . . . . . . . . 2127.1.4 Alte metode de reprezentare a numerelor ^ntregi . . . . . . . . . 214

  • c 2008, Radu-Lucian LupsaCuprins 9

    7.2 Codicarea textelor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2157.2.1 Codicarea ASCII . . . . . . . . . . . . . . . . . . . . . . . . . . 2167.2.2 Codicarile ISO-8859 . . . . . . . . . . . . . . . . . . . . . . . . 2177.2.3 Codicarile Unicode . . . . . . . . . . . . . . . . . . . . . . . . . 218

    7.2.3.1 Codicarea UTF-8 . . . . . . . . . . . . . . . . . . . . . . . 2207.2.3.2 Codicarile UTF-16 . . . . . . . . . . . . . . . . . . . . . . 2207.2.3.3 Codicarile UTF-32 . . . . . . . . . . . . . . . . . . . . . . 221

    7.3 Reprezentarea datei si orei . . . . . . . . . . . . . . . . . . . . . . . . 2217.3.1 Masurarea timpului . . . . . . . . . . . . . . . . . . . . . . . . . 2227.3.2 Obiectivele ^n alegerea reprezentarii timpului ^n calculator . . . . 2247.3.3 Formate utilizate ^n practica . . . . . . . . . . . . . . . . . . . . 225

    7.3.3.1 Formatul utilizat de posta electronica . . . . . . . . . . . . 2257.3.3.2 ISO-8601 si RFC-3339 . . . . . . . . . . . . . . . . . . . . . 2267.3.3.3 Timpul POSIX . . . . . . . . . . . . . . . . . . . . . . . . . 2277.3.3.4 TAI 64 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227

    7.4 Recodicari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2287.4.1 Codicarea hexazecimala . . . . . . . . . . . . . . . . . . . . . . 2287.4.2 Codicarea ^n baza 64 . . . . . . . . . . . . . . . . . . . . . . . . 2297.4.3 Codicari bazate pe secvente de evitare . . . . . . . . . . . . . . 229

    8 Programarea ^n retea | introducere 2318.1 Interfata de programare socket BSD . . . . . . . . . . . . . . . . . . . 231

    8.1.1 Comunicatia prin conexiuni . . . . . . . . . . . . . . . . . . . . . 2328.1.1.1 Deschiderea conexiunii de catre client . . . . . . . . . . . . 2338.1.1.2 Deschiderea conexiunii de catre server . . . . . . . . . . . . 2338.1.1.3 Comunicatia propriu-zisa . . . . . . . . . . . . . . . . . . . 2348.1.1.4 I^nchiderea conexiunii . . . . . . . . . . . . . . . . . . . . . . 234

    8.1.2 Comunicatia prin datagrame . . . . . . . . . . . . . . . . . . . . 2358.1.3 Principalele apeluri sistem . . . . . . . . . . . . . . . . . . . . . 237

    8.1.3.1 Functia socket() . . . . . . . . . . . . . . . . . . . . . . . . 2378.1.3.2 Functia connect() . . . . . . . . . . . . . . . . . . . . . . . 2378.1.3.3 Functia bind() . . . . . . . . . . . . . . . . . . . . . . . . . 2388.1.3.4 Functia listen() . . . . . . . . . . . . . . . . . . . . . . . . 2398.1.3.5 Functia accept() . . . . . . . . . . . . . . . . . . . . . . . . 2398.1.3.6 Formatul adreselor . . . . . . . . . . . . . . . . . . . . . . . 2408.1.3.7 Interactiunea dintre connect(), listen() si accept() . . . 2428.1.3.8 Functiile getsockname() si getpeername() . . . . . . . . . 2428.1.3.9 Functiile send() si recv() . . . . . . . . . . . . . . . . . . 2438.1.3.10 Functiile shutdown() si close() . . . . . . . . . . . . . . . 2458.1.3.11 Functiile sendto() si recvfrom() . . . . . . . . . . . . . . 245

    8.1.4 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2468.1.4.1 Comunicare prin conexiune . . . . . . . . . . . . . . . . . . 2468.1.4.2 Comunicare prin datagrame . . . . . . . . . . . . . . . . . . 249

    8.2 Formatarea datelor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252

  • c 2008, Radu-Lucian Lupsa10 Cuprins

    8.2.1 Formate binare . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2528.2.1.1 Tipuri ^ntregi . . . . . . . . . . . . . . . . . . . . . . . . . . 2528.2.1.2 Siruri de caractere si tablouri . . . . . . . . . . . . . . . . . 2548.2.1.3 Variabile compuse (struct-uri) . . . . . . . . . . . . . . . . 2558.2.1.4 Pointeri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257

    8.2.2 Formate text . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2578.2.3 Probleme de robustete si securitate . . . . . . . . . . . . . . . . 2578.2.4 Probleme privind costul apelurilor sistem . . . . . . . . . . . . . 258

    8.3 Probleme de concurenta ^n comunicatie . . . . . . . . . . . . . . . . . 260

    9 Retele IEEE 802 2639.1 Retele IEEE 802.3 (Ethernet) . . . . . . . . . . . . . . . . . . . . . . 263

    9.1.1 Legaturi punct la punct prin perechi de conductoare . . . . . . . 2669.1.2 Legaturi prin bre optice . . . . . . . . . . . . . . . . . . . . . . 2729.1.3 Legaturi prin cablu magistrala . . . . . . . . . . . . . . . . . . . 2749.1.4 Repetoarele si comutatoarele . . . . . . . . . . . . . . . . . . . . 2779.1.5 Dirijarea efectuata de comutatoare (switch-uri) . . . . . . . . . . 2799.1.6 Facilitati avansate ale switch-urilor . . . . . . . . . . . . . . . . . 279

    9.1.6.1 Switch-uri congurabile . . . . . . . . . . . . . . . . . . . . 2799.1.6.2 Filtrare pe baza de adrese MAC . . . . . . . . . . . . . . . 2809.1.6.3 Trunking . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2809.1.6.4 Legaturi redundante . . . . . . . . . . . . . . . . . . . . . . 2819.1.6.5 Retele virtuale (VLAN) . . . . . . . . . . . . . . . . . . . . 281

    9.1.7 Considerente privind proiectarea unei retele . . . . . . . . . . . . 2829.2 Retele IEEE 802.11 (Wireless) . . . . . . . . . . . . . . . . . . . . . . 283

    9.2.1 Arhitectura retelei . . . . . . . . . . . . . . . . . . . . . . . . . . 2839.2.2 Accesul la mediu . . . . . . . . . . . . . . . . . . . . . . . . . . . 2859.2.3 Generarea pachetelor beacon . . . . . . . . . . . . . . . . . . . . 2869.2.4 Securitatea retelelor 802.11 . . . . . . . . . . . . . . . . . . . . . 286

    10 Internetul 29110.1 Arhitectura retelei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29110.2 Protocolul IP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292

    10.2.1 Structura pachetului IP . . . . . . . . . . . . . . . . . . . . . . . 29310.2.2 Bazele dirijarii pachetelor IP . . . . . . . . . . . . . . . . . . . . 294

    10.2.2.1 Subretele si interfete . . . . . . . . . . . . . . . . . . . . . . 29410.2.2.2 Prexul de retea . . . . . . . . . . . . . . . . . . . . . . . . 29510.2.2.3 Tabela de dirijare . . . . . . . . . . . . . . . . . . . . . . . . 296

    10.2.3 Scrierea ca text a adreselor si prexelor . . . . . . . . . . . . . . 29810.2.3.1 Scrierea adreselor IP . . . . . . . . . . . . . . . . . . . . . . 29810.2.3.2 Scrierea prexelor de retea . . . . . . . . . . . . . . . . . . . 300

    10.2.4 Alocarea adreselor IP si prexelor de retea . . . . . . . . . . . . 30010.2.4.1 Alocarea pe utilizari . . . . . . . . . . . . . . . . . . . . . . 30110.2.4.2 Alocarea adreselor si dirijarea ierarhica . . . . . . . . . . . . 301

  • c 2008, Radu-Lucian LupsaCuprins 11

    10.2.5 Erori la dirijare si protocolul ICMP . . . . . . . . . . . . . . . . 30210.2.5.1 Pachete nelivrabile . . . . . . . . . . . . . . . . . . . . . . . 30310.2.5.2 Diagnosticarea functionarii rutelor . . . . . . . . . . . . . . 30510.2.5.3 Ciclarea pachetelor IP . . . . . . . . . . . . . . . . . . . . . 30510.2.5.4 Congestia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30610.2.5.5 Redirectionarea . . . . . . . . . . . . . . . . . . . . . . . . . 306

    10.2.6 Alte chestiuni privind dirijarea pachetelor . . . . . . . . . . . . . 30710.2.6.1 Dimensiunea maxima a pachetelor si fragmentarea . . . . . 30710.2.6.2 Calitatea serviciului . . . . . . . . . . . . . . . . . . . . . . 308

    10.2.7 Congurarea si testarea unei retele IP locale . . . . . . . . . . . 30910.2.7.1 Alegerea parametrilor . . . . . . . . . . . . . . . . . . . . . 30910.2.7.2 Congurarea parametrilor de retea pe diverse sisteme de op-

    erare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31210.2.7.3 Testarea si depanarea retelelor . . . . . . . . . . . . . . . . 313

    10.3 Nivelul transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31410.3.1 Conexiuni cu livrare garantata: protocolul TCP . . . . . . . . . 314

    10.3.1.1 Principiul conexiunii TCP . . . . . . . . . . . . . . . . . . . 31510.3.1.2 Comunicatia bidirectionala . . . . . . . . . . . . . . . . . . 32010.3.1.3 Deschiderea si ^nchiderea conexiunii . . . . . . . . . . . . . 32010.3.1.4 Alegerea numarului initial de secventa . . . . . . . . . . . . 32310.3.1.5 I^nchiderea fortata a conexiunii . . . . . . . . . . . . . . . . 32410.3.1.6 Identicarea aplicatiei destinatie . . . . . . . . . . . . . . . 32510.3.1.7 Corespondenta ^ntre functiile socket() si actiunile modulu-

    lui TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32610.3.1.8 Controlul uxului . . . . . . . . . . . . . . . . . . . . . . . . 32710.3.1.9 Stabilirea time-out-ului pentru retransmiterea pachetelor . . 32710.3.1.10Algoritmul lui Nagle si optimizarea numarului de pachete . 32810.3.1.11Trimiterea datelor speciale (out of band) . . . . . . . . . . . 328

    10.3.2 Datagrame nesigure: UDP . . . . . . . . . . . . . . . . . . . . . 32910.4 Identicarea nodurilor dupa nume: sistemul DNS . . . . . . . . . . . 330

    10.4.1 Numele de domeniu . . . . . . . . . . . . . . . . . . . . . . . . . 33010.4.2 Structura logica a bazei de date DNS . . . . . . . . . . . . . . . 33210.4.3 I^mpartirea ^n domenii de autoritate . . . . . . . . . . . . . . . . 33310.4.4 Mecanismul de interogare a serverelor . . . . . . . . . . . . . . . 33410.4.5 Sincronizarea serverelor pentru un domeniu . . . . . . . . . . . . 33510.4.6 Cautarea numelui dupa IP . . . . . . . . . . . . . . . . . . . . . 336

    10.5 Legaturile directe ^ntre nodurile IP . . . . . . . . . . . . . . . . . . . 33710.5.1 Rezolvarea adresei | ARP . . . . . . . . . . . . . . . . . . . . . 337

    10.6 Congurarea automata a statiilor | DHCP . . . . . . . . . . . . . . 33910.7 Situatii speciale ^n dirijarea pachetelor . . . . . . . . . . . . . . . . . 341

    10.7.1 Filtre de pachete (rewall) . . . . . . . . . . . . . . . . . . . . . 34110.7.2 Retele private . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34610.7.3 Translatia adreselor (NAT) . . . . . . . . . . . . . . . . . . . . . 347

    10.7.3.1 Translatia adresei sursa . . . . . . . . . . . . . . . . . . . . 347

  • c 2008, Radu-Lucian Lupsa12 Cuprins

    10.7.3.2 Translatia adresei destinatie . . . . . . . . . . . . . . . . . . 35010.7.4 Tunelarea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351

    11 Aplicatii ^n retele 35311.1 Posta electronica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353

    11.1.1 Formatul mesajelor . . . . . . . . . . . . . . . . . . . . . . . . . 35411.1.1.1 Antetul mesajelor . . . . . . . . . . . . . . . . . . . . . . . . 35511.1.1.2 Extensii MIME . . . . . . . . . . . . . . . . . . . . . . . . . 35811.1.1.3 Atasarea sierelor si mesaje din mai multe parti . . . . . . 35911.1.1.4 Codicarea corpului mesajului si a atasamentelor . . . . . . 360

    11.1.2 Transmiterea mesajelor . . . . . . . . . . . . . . . . . . . . . . . 36211.1.2.1 Protocolul SMTP . . . . . . . . . . . . . . . . . . . . . . . . 36211.1.2.2 Determinarea urmatorului MTA . . . . . . . . . . . . . . . 36511.1.2.3 Congurarea unui MTA . . . . . . . . . . . . . . . . . . . . 366

    11.1.3 Securitatea postei electronice . . . . . . . . . . . . . . . . . . . . 36811.2 Sesiuni interactive la distanta . . . . . . . . . . . . . . . . . . . . . . 371

    11.2.1 Protocolul ssh . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37311.2.1.1 Conexiunea ssh protejata criptograc . . . . . . . . . . . . 37311.2.1.2 Metode de autenticare ^n ssh . . . . . . . . . . . . . . . . . 37611.2.1.3 Multiplexarea conexiunii, tunelarea si aplicatii . . . . . . . 379

    11.2.2 Sistemul X-Window . . . . . . . . . . . . . . . . . . . . . . . . . 37911.3 Transferul sierelor ^n retea . . . . . . . . . . . . . . . . . . . . . . . 380

    11.3.1 Protocolul ftp . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38111.3.2 Protocolul HTTP . . . . . . . . . . . . . . . . . . . . . . . . . . 382

    11.3.2.1 Structura cererilor si a raspunsurilor . . . . . . . . . . . . . 38311.3.2.2 URL-urile . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38411.3.2.3 Alte facilitati HTTP . . . . . . . . . . . . . . . . . . . . . . 38511.3.2.4 Proxy HTTP . . . . . . . . . . . . . . . . . . . . . . . . . . 38611.3.2.5 Conexiuni securizate: SSL/TLS . . . . . . . . . . . . . . . . 38711.3.2.6 Utilizarea TLS pentru web . . . . . . . . . . . . . . . . . . 389

    11.4 PGP/GPG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39011.4.1 Structura cheilor GnuPG . . . . . . . . . . . . . . . . . . . . . . 390

    11.4.1.1 Chei primare si subchei . . . . . . . . . . . . . . . . . . . . 39111.4.1.2 Utilizatori si identitati . . . . . . . . . . . . . . . . . . . . . 39211.4.1.3 Generarea si modicarea cheilor . . . . . . . . . . . . . . . . 39211.4.1.4 Controlul perioadei de valabilitate a cheilor . . . . . . . . . 39311.4.1.5 Gestiunea cheilor secrete . . . . . . . . . . . . . . . . . . . . 395

    11.4.2 Transmiterea si certicarea cheilor publice . . . . . . . . . . . . . 39511.4.2.1 Transmiterea cheilor publice . . . . . . . . . . . . . . . . . . 39511.4.2.2 Vericarea autenticitatii cheilor . . . . . . . . . . . . . . . . 397

    11.4.3 Transmiterea mesajelor criptate sau semnate . . . . . . . . . . . 399

    Bibliograe 401

    Index 405

  • c 2008, Radu-Lucian Lupsa13

    Prefata

    I^n contextul prezent al dezvoltarii retelelor de calculatoare, este inutilsa mai subliniem importanta acestui domeniu.

    Lucrarea de fata se adreseaza ^n principal programatorilor de aplicatii^n retea si administratorilor de retele complexe. Sunt presupuse, din parteacititorului, cunostinte de baza de programare, precum si privind functionareasistemelor de operare.

    Ca un avertisment pentru programatori, mentionam ca, desi lucrareatrateaza chestiuni de nivel mult mai cobora^t deca^t cel al platformelor si bib-liotecilor utilizate ^n mod normal ^n aplicatiile ^n retea, este totusi utila ^nvederea unei bune ^ntelegeri a acestor platforme si biblioteci.

    Tot ceea ce are legatura ^ntr-un fel sau altul cu calculatoare are douacaracteristici: se dezvolta foarte repede si est foarte complex. Retelele decalculatoare nu fac exceptie. Ca urmare, este extrem de usor pentru oricinesa se piarda ^n nenumaratele detalii ^n permanenta schimbare.

    Consideram ca, ^n orice domeniu, o buna prezentare trebuie sa porneascade la principiile de baza. Principiile de baza se sunt (relativ) simple si evolueazamult mai lent deca^t constructiile tehnice elaborate pe baza lor. I^n consecinta,prima parte a lucrarii de fata, principii, este dedicata studierii problemelor cetrebuie rezolvate de o retea de calculatoare, precum si a principiilor constructieiposibilelor solutii ale acestor probleme.

    Partea a doua a lucrarii, protocoale, prezinta ca^teva dintre cele mairaspa^ndite protocoale si mecanisme utilizate ^n retelele de calculatoare. Ea esteconstruita pentru a oferi cititorului o privire de ansamblu asupra protocoalelorstudiate. Aceasta privire de ansamblu poate sucienta pentru unii cititori,^n caz contrar ind probabil necesara citirea efectiva a standardelor.

    Lucrarea de fata este rodul experientei autorului ^n activitati legatede administrarea retelei de calculatoare a Departamentului de Informatica alFacultatii de Matematica si Informatica din cadrul Universitatii Babes-BolyaiCluj-Napoca, ^n predarea unui curs de Retele de calculatoare la aceasta fac-

  • c 2008, Radu-Lucian Lupsa14 Prefata

    ultate, precum si din activitatea de cercetare desfasurata de-a lungul anilor, ^nspecial de nevoile practice din cadrul contractului de cercetare PNII 11003/2007- Sistem decizional bazat pe tehnici de tip multi-agent pentru generarea, opti-mizarea si managementul registrelor nationale de boli cronice netransmisibile -CRONIS. Seturile mari de date ce se vehiculeaza ^n sistemul medical, precumsi nevoia de condentialitate si securitate a lor, cer o foarte buna cunoasteresi punere ^n practica a notiunilor legate de codicarea informatiei, de metodesi protocoale criptograce, de aplicatii ^n retele etc.

  • c 2008, Radu-Lucian Lupsa15

    Capitolul 1

    Introducere

    Prin retea de calculatoare ^ntelegem un sistem (consta^nd din com-ponente hard si soft) care interconecteaza niste calculatoare, permita^nd unorprograme ce se executa pe aceste calculatoare sa comunice ^ntre ele.

    De notat ca, ^n uzul comun, termenul de retea de calculatoare mai aresi sensul de sistem de calcul, construit din mai multe calculatoare interconec-tate ^ntr-o retea, care se comporta ca un sistem unitar, de exemplu, prezintaaceleasi conturi de utilizatori pe toate calculatoarele.

    1.1. Serviciile oferite de retea

    Se spune ca orice problema bine formulata este pe jumatate rezolvata.Prin urmare, pentru ^nceput, vom stabili mai exact ce se doreste de la o reteade calculatoare.

    I^ntr-o retea de calculatoare avem mai multe calculatoare pe care seexecuta procese utilizator. Rolul retelei este de-a oferi acestor procese posi-bilitatea de-a comunica ^ntre ele. Din punctul de vedere al programatoruluiacestor procese, reteaua ofera niste functii, din nucleul sistemului de oper-are sau din biblioteci standard, apelabile de catre aceste procese (g. 1.1).Ansamblul acestor functii constituie interfata de programare (engl. API |Application Programming Interface) a retelei.

    Principalele functii oferite de retea, apelabile de catre un proces uti-lizator, sunt o functie care trimite date de la procesul curent spre partenerulsau partenerii de comunicatie si o functie care receptioneaza datele trimise spreprocesul curent. I^n aceste functii este necesara desemnarea destinatarului sprecare procesul emitator doreste transmiterea datelor, respectiv a emitatoruluidinspre care procesul receptor solicita sa primeasca date. I^n acest scop, ecare

  • c 2008, Radu-Lucian Lupsa16 1.1. Serviciile oferite de retea

    calculator

    Processursa

    Procesdestinatie

    calculator

    Retea

    interfata deprogramare (API)

    send()

    recv()

    Figura 1.1: Reteaua de calculatoare, din punctul de vedere al proceselor aplicatie.Functionalitatea retelei este oferita prin functii apelabile din procesele utilizator.Reteaua ofera o aplicatiilor o cale de transmisie a datelor (linia punctata). Constructiaefectiva a retelei nu este vizibila aplicatiilor.

    entitate ce poate comunica ^n retea trebuie sa aiba asociata o adresa (un sirde biti, construit dupa anumite reguli, identica^nd unic o anumita entitate).

    Pe la^nga aceste functii de baza, reteaua mai ofera functii pentru con-gurarea diferitilor parametrii. O parte dintre acesti parametri xeaza rolulsi locul diverselor componente ^n cadrul retelei (de exemplu, ecare calculatortrebuie sa-si cunoasca propria adresa). Alti parametrii sunt legati de calitateaserviciilor oferite de retea (debit de transfer de date, timp de propagare, etc).

    Datele transmise de procesele utilizator sunt de obicei siruri arbitrarede octeti. Rolul retelei este de-a transmite ^ntocmai sirul de octeti trimisde procesul sursa catre procesul destinatie. Semnicatia, pentru procesuldestinatie, a unui sir de octeti transmis face obiectul unei ^ntelegeri (proto-col) ^ntre procesele utilizator. La proiectarea retelei nu ne intereseaza ce facprocesele utilizator cu datele transferate; la proiectarea programelor utilizatornu ne intereseaza cum lucreaza reteaua pentru a transmite datele.

    I^n continuare vom trece ^n revista principalele caracteristici ale ser-viciului oferit de retea proceselor de aplicatie.

    O comunicatie poate , dupa numarul destinatarilor:

    punct la punct , daca exista un singur destinatar. I^n mod obisnuit, des-tinatarul este selectionat explicit de catre procesul emitator; o astfel decomunicatie este numita unicast . Uneori ^nsa, de exemplu ^n cazul ^ncare un serviciu este oferit de mai multe servere, echivalente din punctulde vedere al clientului, este favorabil ca reteaua sa aleaga destinatarulcomunicatiei, ^n functie de distanta fata de emitator, dintr-o multime

  • c 2008, Radu-Lucian LupsaCapitolul 1. Introducere 17

    specicata de destinatari posibili. Un astfel de comunicatie se numesteanycast .

    difuziune, daca exista mai multi destinatari. Distingem difuziune com-pleta (engl. broadcast), ^n care destinatari sunt toate calculatoarele dintr-o retea, si difuziune selectiva (engl. multicast), ^n care destinatarii sunto submultime aleasa a calculatoarelor din retea.

    Serviciul de comunicatie oferit de retea poate de tip conexiune saude tip transport de datagrame:

    I^n cazul conexiunilor, ^n cadrul comunicatiei ^ntre doua procese se distingtrei faze:

    - deschiderea conexiunii, ^n cadrul careia sunt facute niste pregatiri,inclusiv alocarea unor resurse pentru comunicatie;

    - comunicatia propriu-zisa, ^n care unul sau ambele procese transmiteun sir de pachete sau de biti celuilalt proces;

    - ^nchiderea conexiunii, ^n cadrul careia se elibereaza resursele alocatela deschidere.

    I^n cazul transportului de datagrame, procesul emitator pregateste unansamblu, numit datagrama (prin analogie cu telegrama), cuprinza^ndun sir de biti destinat procesului receptor si anumite informatii necesarelivrarii (adresa destinatarului). Apoi transmite datagrama retelei de cal-culatoare, care o transmite procesului receptor. Mai multe datagrametrimise de acelasi proces sursa catre acelasi proces destinatie sunt trans-mise independent una de alta, ceea ce duce, ^n general, la posibilitateainversarii ordinii de receptie fata de ordinea de emisie a datagramelor.

    Principalii parametri de calitate ai serviciului oferit de retea sunt:

    Capacitatea de transport oferita de retea, sau debitul maxim acceptat , esteraportul dintre numarul de biti transportati ^n cadrul unei comunicatiisi timpul ^n care acestia sunt transmisi. Echivalent, capacitatea esteinversul duratei medii ^ntre trecerea, printr-un punct dat al retelei, adoi biti consecutivi ai unei comunicatii.

    Timpul de transfer a unui bloc de date este timpul scurs de latrecerea, printr-un punct dat, a primului bit al blocului pa^na la trecerea,prin acelasi punct, a ultimului bit. Timpul de transfer este egal curaportul dintre dimensiunea blocului si debitul cu care se face transferul.

    Capacitatea oferita de retea unei legaturi poate sa varieze datoritavariatiei debitului altor comunicatii care partajeaza aceleasi echipamente.

  • c 2008, Radu-Lucian Lupsa18 1.1. Serviciile oferite de retea

    Exista aplicatii, de exemplul legate de transfer de siere, pentrucare este important ca reteaua sa ofere o capacitate medie ca^t mai mare.Penttru alte aplicatii, cum ar telefonia, transmisia video (de exemplupentru teleconferinte) sau alte aplicatii ^n timp real, este important sanu scada niciodata capacitatea legaturii sub o anumita valoare minima,^nsa o capacitate mai mare nu este utila.

    Timpul de propagare ^ntre doua entitati este timpul scurs ^ntre mo-mentul ^n care entitatea sursa emite un bit si momentul ^n care acel bitajunge la destinatie. Timpul de propagare rezulta din ^nsumarea tim-pului de propagare a semnalului de-a lungul mediului de comunicatiecu diversii timpi de asteptare a datelor ^n diverse zone tampon. De re-marcat ca timpul de propagare a semnalului este egal cu distanta de laemitator la receptor ^mpartita la viteza de propagare a semnalului, iarviteza de propagare nu poate depasi viteza luminii ^n vid; din acest mo-tiv, de exemplu, timpul de propagare prin legaturi prin satelit nu poate mai scurt de ca^teva zecimi de secunda.

    Timpul scurs de la ^nceputul transmisiei unui bloc de date de catreemitator pa^na la nalul receptiei blocului de catre receptor este egal cusuma dintre timpul de transfer si timpul de propagare.

    Uneori, ^n loc de timpul de propagare se utilizeaza o alta marime,timpul dus-^ntors, care este timpul scurs de la transmiterea unui mesajde catre o partenerul de comunicatie pa^na la primirea raspunsului dinpartea acestuia. Timpul dus-^ntors este suma dintre timpii de propa-gare pentru cele doua sensuri si timpul de procesare pentru crearearaspunsului.

    Evident, timpul de propagare e bine sa e ca^t mai scurt, ^nsadiferite aplicatii au cerinte diferite:

    - La unele aplicatii timpul de propagare nu este prea important. Deexemplu, la transferul unui sier mare, la care oricum timpul detransfer este mare, timpul de propagare inuenteaza foarte putintimpul total necesar transmiterii sierului.

    - La difuzarea de materiale audio sau video, un timp de propagaremare nu este deranjant, ^nsa este important ca el sa e constant^n timp. Aceasta pentru ca nu este deranjant daca o transmisiede televiziune este cu ca^teva secunde ^n ^nta^rziere fata de eveni-mentele transmise, ^nsa este important sa nu e momente ^n careimaginea ,,^ngheata\ datorita cresterii timpului de propagare simomente ^n care imaginea ,,sare ^nainte\ datorita scurtarii timpu-lui de propagare.

  • c 2008, Radu-Lucian LupsaCapitolul 1. Introducere 19

    - Timpul de propagare (sau, echivalent, timpul dus-^ntors) este im-portant sa e scurt ^n special pentru aplicatii ^n care entitatile cecomunica transmit mesaje scurte si trebuie sa astepte raspunsulla mesajul precedent pentru a putea genera mesajul urmator. Ex-emple de astfel de aplicatii sunt: telefonie, videoconferinte, sesiuniinteractive la distanta.

    Posibilitatea existentei erorilor de transmisie: Erorile de transmisieapar ca urmare a diverselor perturbatii ce afecteaza transmiterea sem-nalelor. Exista metode de-a micsora orica^t de mult probabilitatea caun mesaj sa e afectat de erori, ^nsa niciodata aceasta probabilitate nupoate facuta zero (probabilitatea unei erori poate facuta ^nsa maimica deca^t, de exemplu, probabilitatea unui cataclism devastator caresa distruga toata reteaua). Metodele de reducere a probabilitatii erorilorde transmisie sunt studiate ^n x 2.4 si x 4.1.

    Transmisia sigura ^nseamna ca ecare mesaj al entitatii sursa sa ajungaexact ^ntr-un singur exemplar la destinatie (sa nu se piarda si sa nu eduplicat) si mai multe mesaje transmise de catre o aceeasi sursa spre oaceeasi destinatie sa ajunga la destinatie ^n ordinea ^n care au fost trans-mise de sursa. Mesajele se pot pierde datorita erorilor de transmisie, asupraaglomerarii sau a defectarii unor echipamente din retea sau chiardin cauza ca emitatorul transmite cu debit mai mare deca^t este capa-bil receptorul sa preia informatia transmisa. Duplicarea sau inversareamesajelor pot cauzate de modicari ale conguratiei sau ^ncarcariiretelei ^n timpul trecerii pachetelor prin retea. Realizarea transmisieisigure este studiata ^n x 4.3 si x 4.4.

    Transmisia sigura este evident utila, ^nsa vine cu un anumit cost.Cel mai adesea, costul este cresterea si uctuatia timpului de propagare,deoarece mesajele pierdute trebuie retransmise. La o transmisie audio-video, este adesea preferabila pastrarea unui timp de propagare redus,cu pretul pierderii, din ca^nd ^n ca^nd, a unor fractiuni de secunda dematerial audio-video.

    Securitatea comunicatiei ^nseamna ca un adversar care controleaza oparte din retea sa nu poata obtine informatia transmisa, sa nu poatamodica datele transmise fara ca acest lucru sa e detectat de catrereceptor si sa nu poata impersona vreuna dintre entitatile ce comunica.Securitatea comunicatiei se obtine prin metode criptograce, studiate ^ncapitolul 6.

  • c 2008, Radu-Lucian Lupsa20 1.2. Principalele elemente ale unei retele de calculatoare

    1.2. Principalele elemente ale unei retele de calcula-toare

    Pentru ca doua dispozitive aate la distanta unul de celalalt sa poatacomunica, este nevoie ca cele doua dispozitive sa e legate printr-un mediu decomunicatie care permite propagarea variatiei unei marimi zice. Mediul zic,^mpreuna cu dispozitivele de adaptare ^ntre reprezentarea locala a informatieisi reprezentarea pe mediul de transmisie constituie nivelul zic al retelei.Nivelul zic este deci un modul care permite transmisia unui sir de biti ^ntredoua dispozitive legate direct unul de celalalt. Constructiv, nivelul zic esteconstituit din: cablul electric, bra optica sau, dupa caz, antenele de emisie-receptie, eventuale amplicatoare sau repetoare, placile de retea din calcula-toare si driver -ele placilor de retea. Constructia nivelului zic este studiata ^ncapitolul 3.

    De obicei, serviciul oferit de nivelul zic sufera de anumite neajun-suri, cum ar probabilitatea mare a erorilor si transmisia nesigura. Pentrucontracararea acestora, de-o parte si de alta a nivelului zic se plaseaza ca^teun modul de adaptare; aceste doua module constituie nivelul legaturii de date.Nivelul legaturii de date este construit partial prin hard (parte a placii deretea) si partial prin soft (parte a driver -ului placii de retea). Constructianivelului legaturii de date este studiata ^n capitolul 4.

    Nivelul zic ^mpreuna cu nivelul legaturii de date ofera o legaturabuna ^ntre doua calculatoare conectate direct printr-un mediu zic. Ar neeconomic sa cerem sa existe o legatura directa ^ntre oricare doua calcula-toare; este preferabil sa putem transmite date prin intermediul unui lant decalculatoare (sau alte dispozitive) legate zic ecare cu urmatorul din lant.Realizarea unei astfel de legaturi cade ^n sarcina nivelului retea, constituitdin ca^te un modul ^n ecare calculator al retelei. Modulul de retea este con-struit prin soft, ^n nucleul sistemului de operare al ecarui calculator din retea.Constructia si functionarea nivelului retea este studiata ^n capitolul 5.

    De obicei, serviciul oferit direct de catre nivelul retea nu poate utilizat direct de catre programele utilizator. De aceea, ^ntre modului de reteasi programul utilizator se mai interpune un modul, constituind (^mpreuna cumodulul omolog de pe calculatorul partener de comunicatii) nivelul transport.Nivelul transport este constituit din parti ale nucleului sistemului de operaresi, uneori, biblioteci legate ^n programele utilizator.

    Relatiile dintre aceste componente sunt reprezentate ^n gura 1.2.

    Fiecare dintre nivele ofera nivelului superior o interfata care cuprinde^n principal functii de trimitere si de receptie a datelor. Aceste functii sunt

  • c 2008, Radu-Lucian LupsaCapitolul 1. Introducere 21

    Modullegaturazica

    Modullegaturazica

    Modullegaturazica

    Modullegaturazica

    Nod nal

    legaturade date

    Modullegaturade date

    Aplicatie

    Modultransport

    Modulde retea

    Modulul de retea

    Modul Modullegaturade date

    Mediu zic Mediu zic

    Nod nal

    Aplicatie

    Modultransport

    Modulde retea

    Modullegaturade date

    Nod intermediar

    Nivelul aplicatie

    Nivelul transport

    Nivelul legaturii

    de date

    Nivelul retea

    Nivelul zic

    Figura 1.2: Componentele unei parti dintr-o retea de calculatoare. Sunt guratedoar componentele implicate ^n comunicatia dintre doua aplicatii. Cele doua aplicatiise executa pe doua calculatoare ^ntre care nu exista o legatura directa, dar exista olegatura printr-un nod intermediar.

    similare celor oferite de retea aplicatiilor (asa cum am vazut ^n x 1.1), dar ser-viciile oferite sunt mai primitive. Astfel, nivelul zic ofera nivelului legaturii dedate servicii de transfer de date, dar numai ^ntre calculatoare conectate directsi cu riscul ca datele sa e alterate ^n timpul transferului sau sa se piarda com-plet. Nivelul legaturii de date ofera nivelului retea servicii de transfer de datemai sigure, dar ^n continuare cu restrictia ca transferul este posibil doar ^ntrecalculatoare conectate direct. Nivelul retea ofera nivelului transport serviciide transfer de date ^ntre orice doua calculatoare din retea, dar ^nca neadec-vate utilizarii directe de catre aplicatii (lipsa transmisiei sigure, comunicatieposibila doar pentru un singur proces aplicatie la un moment dat, etc.).

    Constructia ecaruia dintre nivele este independenta de constructiacelorlalte (conteaza doar interfata dintre ele si parametrii de calitate a servi-ciului oferit de un nivel celui imediat superior). De exemplu, ^n proiectareanivelului retea, nu ne intereseaza nici ce aplicatii vor utiliza reteaua (acelasinivel retea din Internet este utilizat de aplicatii de posta electronica, web,telefonie prin Internet si videoconferinte), nici cum este construit nivelul zic(perechi de conductoare, bre optice sau legaturi radio prin satelit).

    Modulele, de pe acelasi nivel, din noduri diferite ^si transmit unulaltuia (utiliza^nd ^n acest scop serviciile oferite de nivelul inferior) doua tipuri

  • c 2008, Radu-Lucian Lupsa22 1.2. Principalele elemente ale unei retele de calculatoare

    de date: datele utile a caror transfer este cerut de nivelul superior si datede control necesare coordonarii activitatilor modulelor din cadrul nivelului.Regulile de reprezentare a acestor date, de organizare a acestora ^n mesaje,precum si regulile dupa care se trimit mesajele ^ntre modulele aceluiasi nivelalcatuiesc protocolul de comunicatie al nivelului respectiv.

    Functionarea corecta a unei retele necesita respectarea, de catre toatemodulele implicate, a protocoalelor de comunicatie stabilite.

    1.3. Premise generale ^n elaborarea si implementareaprotocoalelor ^n retele

    Pe la^nga ratiunile pur functionale, studiate pe larg ^n capitolele urma-toare, ^n elaborarea si implementarea protocoalelor intervin ratiuni practice,pe care le vom ^nsira pe scurt ^n continuare:

    Deoarece o retea este formata din multe componente, frecventa cu carese ^nta^mpla ca cel putin o componenta a unei retele sa nu functionezecorect este mare. Este necesar ca o defectiune sa afecteze ca^t mai putindin retea, iar componentele a caror defectare duce la caderea ^ntregiiretele trebuie sa e ca^t mai putine, eventual nici una.

    Gasirea unei pene ^ntr-un sistem complex este, ^n general, dicila. Reteauatrebuie sa ofere mecanisme prin care orice defectiune sa e usor de lo-calizat.

    Implementari diferite ale unui protocol se pot abate ^n moduri diferite dela specicatia protocolului. Este bine ca mici abateri ale parteneruluide comunicatie sa e tolerate. Rezulta de aici principiul ca o imple-mentare trebuie sa e stricta cu ceea ce transmite si toleranta cu ceeace receptioneaza.

    Reteaua trebuie sa functioneze astazi, sau, un plan bun azi este mai bundeca^t un plan perfect ma^ine (maxima atribuita generalului americanGeorge Patton, circa 1944). Momentul standardizarii unui protocol esteextrem de delicat: daca este standardizat ^nainte ca problema de rezolvatsa e bine ^nteleasa si solutiile posibile bine analizate, rezulta un protocolprost; daca standardizarea apare prea ta^rziu, dupa ce s-a raspa^ndit dejaun protocol acceptabil, exista riscul creerii unui protocol perfect, dar pecare nu-l foloseste nimeni deoarece ^nlocuirea sistemelor existente ar mai scumpa deca^t avantajul adus de protocolul mai bun.

    Protocoalele totusi evolueaza, iar oprirea ^ntregii retele ^n vederea schimbariiechipamentelor afectate de schimbarea protocolului nu este rezonabila.

  • c 2008, Radu-Lucian LupsaCapitolul 1. Introducere 23

    Ca urmare, la o schimbare de protocol trebuie avut ^n vedere existentaunei perioade de tranzitie ^n timpul careia echipamentele noi trebuie sapoata comunica cu cele vechi. Tranzitia este mult usurata daca proto-colul vechi prevede anumite facilitati. O posibilitate este ca ^n protocolsa se prevada o faza de negociere ^n care ecare entitate anunta ce versi-uni de protocol si ce extensii de protocol cunoaste, iar apoi comunicatiadecurge conform versiunii celei mai recente si cu cele mai multe exten-sii suportate de ambii parteneri. Alta posibilitate este stabilirea, dela prima versiune a protocolului, a actiunilor unui dispozitiv, ce im-plementeaza o versiune veche a protocolului, la primirea unui mesajneprevazut ^n acea versiune.

    Cerinte diferite ale diferitelor aplicatii duc la tendinta de-a elabora proto-coale complexe, care sa satisfaca pe toata lumea. Protocoale complexeduc la implementari scumpe si cu riscuri mari de-a avea erori. Estepreferabil un protocol care sa ofere ca^teva operatii simple care sa poata combinate dupa dorinta aplicatiei ce-l utilizeaza. Daca o astfel deabordare nu este fezabila, duca^nd la un protocol prea complex, se re-curge la protocoale ce au posibilitatea de-a implementate doar partial;metodele utilizabile ^n acest scop sunt similare cu cele descrise mai suspentru facilitarea evolutiei protocoalelor.

  • c 2008, Radu-Lucian Lupsa24 Capitolul 1. Introducere

  • c 2008, Radu-Lucian Lupsa25

    Capitolul 2

    Notiuni de teoria informatiei

    Teoria informatiei se ocupa cu studiul metodelor de codicare a in-formatiei ^n vederea transmiterii sau stocarii acesteia. I^n cadrul teoriei infor-matiei se studiaza si cum se poate masura cantitatea de informatie transmisa^ntr-un mesaj si cum se poate masura ecienta unei anumite codicari.

    Prin informatie ^ntelegem cunostintele unei entitati.

    I^n cele ce urmeaza, ne va interesa problema transmiterii unei infor-matii de la o sursa la o destinatie. Informatia de transmis nu este cunoscutainitial nici de destinatie, nici de sistemul de transmitere. Ca urmare, a prioriinformatia de transmis poate vazuta ca o variabila aleatoare.

    Comunicatia dintre sursa si destinatie se desfasoara prin intermediulunui canal de comunicatie. Canalul de comunicatie este capabil sa transmitae o marime variabila ^n timp, numita semnal (^n esenta, o functie realacontinua), caz ^n care canalul este numit continuu, e un sir de simboluridintr-o multime nita, caz ^n care canalul este numit discret .

    Deoarece canalul nu poate transmite direct informatia sursei, ^ntresursa si canal avem nevoie de un dispozitiv, numit emitator , care transformainformatia utila, produsa de sursa, ^ntr-un semnal sau, dupa caz, ^ntr-un sir desimboluri. Similar, ^ntre canal si destinatie se plaseaza un dispozitiv, numitreceptor , al carui rol este de-a efectua operatia inversa, si anume de-a ex-trage din semnal sau din sirul de simboluri informatia utila pentru destinatie(g. 2.1).

    DestinatieSursa ReceptorCanalEmitator

    Figura 2.1: Transmisia informatiei de la sursa la destinatie

  • c 2008, Radu-Lucian Lupsa26 Capitolul 2. Notiuni de teoria informatiei

    Semnalul sau, dupa caz, sirul de simboluri ce tranziteaza canalul senumeste reprezentarea informatiei . Regulile de corespondenta dintre informa-tia utila si reprezentarea sa poarta denumirea de schema de reprezentare ainformatiei, schema de codicare a informatiei sau cod .

    Ca exemplu, o limba scrisa este o schema de reprezentare a infor-matiei, pentru un canal discret a carui multime de simboluri contine literelealfabetului limbii respective, precum si spatiul si semnele de punctuatie. Untext scris ^ntr-o limba este o reprezentare a informatiei, iar conceptele dintextul respectiv sunt efectiv informatia continuta ^n text.

    Ca un al doilea exemplu, limba vorbita este o alta schema de reprezentarea informatiei, canalul pentru care este construita ind de tip continuu.

    Schema de codicare a informatiei se presupune ca este stabilita ^nprealabil si este cunoscuta ata^t emitatorului ca^t si receptorului. De asemenea,^n constructia schemei de reprezentare a informatiei se tine cont de carac-teristicile canalului si de caracteristici generale ale informatiilor ce trebuie sase poata transmite, ^nsa la elaborarea ei nu se cunosc informatiile ce trebui-esc efectiv transmise. De exemplu, la elaborarea unei scheme de codicare aliterelor dintr-un text utiliza^nd un canal ce poate transmite doar simbolurile0 si 1 se poate tine cont de frecventa obisnuita a literelor ^ntr-un text, dar nusi de textul efectiv de transmis.

    Restul capitolului trateaza scheme de reprezentare a informatiei pen-tru canale discrete. Vom studia ^n continuare:

    proprietati generale ale codurilor, problema minimizarii numarului de simboluri necesare a transmise prin

    canal, precum si masurarea cantitatii de informatie,

    problema codicarii ^n cazul ^n care canalul altereaza sirul de simboluripe care ^l transmite (canal cu perturbatii).

    2.1. Problema codicarii informatiei pentru un canaldiscret

    I^n cazul unui canal discret, canalul poate transmite un sir de sim-boluri dintr-o multime S, numita multimea simbolurilor de cod sau alfabetulcanalului. Elementele lui S se numesc simboluri de cod sau, scurt, simboluri.Multimea S este nita si are cel putin doua elemente. De regula S = f0; 1g.

    Pentru sirurile de simboluri de cod vom utiliza urmatoarele notatii:

    S reprezinta multimea sirurilor nite de elemente din S. u v reprezinta concatenarea sirurilor u si v.

  • c 2008, Radu-Lucian LupsaCapitolul 2. Notiuni de teoria informatiei 27

    juj reprezinta lungimea sirului u; avem ju vj = juj+ jvj, 8u; v 2 S. " este sirul vid; avem j"j = 0 si u " = " u = u, 8u 2 S.

    Informatia transmisa de catre sursa consta dintr-un sir de mesaje.Fiecare mesaj este un element dintr-o multimeM de mesaje posibile. Mesajeleprovin din universul utilizatorului sistemului; ele pot propozitii, litere, nu-mere, etc.

    Multimea de mesaje M este nevida si cel mult numarabila. De celemai multe ori M este nita.

    Denitia 2.1 Numim functie de codicare sau cod orice functie injectivac : M ! S, unde M este multimea de mesaje, cel mult numarabila, iarS este multimea simbolurilor de cod, nita si ava^nd cel putin doua elemente.

    Fiecare mesaj m 2M va codicat prin sirul c(m) 2 S.

    Denitia 2.2 Numim cuva^nt de cod orice sir de simboluri de cod w 2 S cuproprietatea ca exista un mesaj m 2M astfel ^nca^t w = c(m).

    Numim multimea cuvintelor de cod multimea W = c(M).

    Un sir de mesaje (m1; : : : ;mk) 2M (undeM desemneaza multimeasirurilor nite de mesaje din M) va codicat prin sirul format prin con-catenarea codicarilor mesajelor:

    c(m1) c(m2) : : : c(mk):

    De remarcat ca ^n urma concatenarii se pierd delimitarile dintre codicarilemesajelor individuale. Ca urmare, pentru ca receptorul sa poata decodicafara ambiguitati orice transmisie a emitatorului este necesara o proprietatesuplimentara a codului, aceea de-a unic decodabil:

    Denitia 2.3 Un cod c :M ! S se numeste: cod unic decodabil, daca functia c^ :M ! S data prin

    c^(m1;m2; : : : ;mk) = c(m1) c(m2) c(mk) (2.1)

    este injectiva.

    cod cu proprietatea de prex sau cod prex, daca nu exista m1;m2 2M ,cu m1 6= m2, astfel ^nca^t c(m1) sa e prex pentru c(m2) si ^n plusc(m) 6= ", 8m 2M .

  • c 2008, Radu-Lucian Lupsa28 2.1. Problema codificarii informatiei pentru un canal discret

    cod de lungime xa, daca exista o constanta l 2 IN n f0g astfel ^nca^tjc(m)j = l, 8m 2M ; valoarea l se numeste lungimea codului;

    Propozitia 2.4 Au loc urmatoarele proprietati:

    1. Orice cod de lungime xa este cod prex.

    2. Orice cod prex este unic decodabil.

    Demonstratia este imediata.

    Exemplul 2.1: Consideram multimea mesajelor M = fa; b; c; dg si multimeasimbolurilor de cod S = f0; 1g. Urmatorul cod are proprietatea de prex.

    a 7! 0b 7! 101c 7! 11d 7! 100

    Exemplul 2.2: Urmatorul cod, obtinut prin oglindirea cuvintelor codului dinexemplul anterior, este unic decodabil dar nu are proprietatea de prex:

    a 7! 0b 7! 101c 7! 11d 7! 001

    Codul nu este prex ^ntruca^t cuva^ntul de cod 0 care este codicarea mesajuluia este prex al cuva^ntului de cod 001 care este codicarea mesajului d.

    De notat ca un cod obtinut prin oglindirea cuvintelor unui cod prexse numeste cod sux si ^ntotdeauna este unic decodabil.

    Exemplul 2.3: Codul de mai jos nu este unic decodabil:

    a 7! 0b 7! 1c 7! 01

    Codul nu este unic decodabil ^ntruca^t sirul de simboluri de cod 01 poate codifcarea mesajului c sau a sirului de mesaje ab.

  • c 2008, Radu-Lucian LupsaCapitolul 2. Notiuni de teoria informatiei 29

    2.2. Coduri cu proprietatea de prex

    Desi simple, codurile de lungime xa nu sunt adecvate ^n urmatoareledoua cazuri:

    pentru obtinerea unui cod ecient, adica ava^nd cuvinte ca^t mai scurte,daca probabilitatile diverselor mesaje din M sunt diferite (M este mul-timea mesajelor sursei);

    dacaM nu este nita (de exemplu,M este multimea numerelor naturale).I^n aceste situatii, trebuie sa ne extindem la clase mai largi deca^t cea

    a codurilor de lungime xa. Asa cum vom vedea ^n continuarea paragrafuluide fata, clasa codurilor prex este sucienta ^n situatiile enumerate mai sus si,^n acelasi timp, permite decodicarea destul de simpla a transmisiei.

    2.2.1. Reprezentarea arborescenta a codurilor prexUnui cod prex c :M ! S i se poate atasa un arbore ^n care:

    pentru ecare nod intern, muchiile descendente sunt cel mult ^n numarde jSj si sunt etichetate cu simboluri distincte din S;

    ecare frunza este etichetata cu ca^te un mesaj distinct din M ; cuva^ntul de cod al unui mesaj este format din simbolurile de cod ale

    muchiilor de pe lantul ce uneste radacina cu frunza atasata mesajului.

    Constructia arborelui se face conform algoritmului 2.1 (Genereaza ar-bore).

    Exemplul 2.4: Pentru codul din exemplul 2.1 arborele este reprezentat ^ngura 2.2.

    0 1

    a

    0

    0 1

    1

    d b

    c

    Figura 2.2: Arborele atasat unui cod prex

    Exemplul 2.5: Fie codul prex pentru multimea mesajelor

    M = fa;b; c;d; e; f; g;hg

  • c 2008, Radu-Lucian Lupsa30 2.2. Coduri cu proprietatea de prefix

    Algoritmul Genereaza arboreintrarea: M multime nita nevida

    c :M ! S cod prexiesirea: T arborele asociat codului calgoritmul:

    creeaza T format doar din radacinar:=radacina lui Tpentru m 2M executa

    (s1; : : : ; sl):=c(m)x:=rpentru i:=1; l executa

    daca nu exista muchie descendenta de la x etichetata cu si atuncidaca x are asociat un mesaj atunci

    eroare: c nu este cod este prexsfa^rsit dacacreaza y descendent al lui x si eticheteaza (x; y) cu si

    sfa^rsit dacax:=descendentul lui x pe muchia etichetata si

    sfa^rsit pentrudaca x nu e frunza atunci

    eroare: c nu este cod este prexsfa^rsit dacaasociaza m nodului x

    sfa^rsit pentrusfa^rsit algoritm

    Algoritmul 2.1: Generarea arborelui asociat unui cod prex

  • c 2008, Radu-Lucian LupsaCapitolul 2. Notiuni de teoria informatiei 31

    si multimea simbolurilor de cod S = f0; 1; 2g:a 7! 0b 7! 10c 7! 11d 7! 12e 7! 200f 7! 201g 7! 21h 7! 22

    Arborele atasat este reprezentat ^n gura 2.3.

    0 1 2

    0 1 2 0 1 2

    0 1

    a

    b c d

    e f

    g h

    Figura 2.3: Arborele atasat codului prex din exemplul 2.5.

    2.2.2. Decodicarea ^n cazul codurilor prexDaca avem un sir de mesaje codicat printr-un cod prex, decodi-

    carea se poate face prin algoritmul 2.2. Acesta ruleaza ^n timp proportionalcu numarul de simboluri de cod din reprezentarea datelor de decodicat.

    De remarcat ca ecare mesaj este decodicat de ^ndata ce ultimulsimbol din reprezentarea sa a fost citit si prelucrat. Acest lucru este posibilnumai pentru codurile prex; din acest motiv, codurile prex se mai numescsi coduri instantanee.

    Exemplul 2.6: Fie codul prex din exemplul 2.5 (vezi g. 2.3) si e sirul dedecodicat:

    s = 0112000

  • c 2008, Radu-Lucian Lupsa32 2.2. Coduri cu proprietatea de prefix

    Algoritmul Decodeazaintrarea: T arborele unui cod prex c :M ! S

    s = (s1; s2; : : : ; sl) 2 S un sir nit de simboluri de codiesirea: m = (m1;m2; : : : ;mk) 2 M sirul mesajelor a caror codicare este

    s1; : : : ; slalgoritmul:

    m:="x:=radacina lui Tpentru i:=1; l executa

    daca nu exista muchie descendenta de la x etichetata cu si atuncieroare: s nu este concatenare de cuvinte de cod

    sfa^rsit dacax:=descendentul ui x pe muchia etichetata cu sidaca x este frunza atunci

    adauga la m mesajul asociat lui xx:=radacina lui T

    sfa^rsit dacasfa^rsit pentrudaca x nu este radacina lui T atunci

    eroare: s nu este concatenare de cuvinte de codsfa^rsit daca

    sfa^rsit algoritm

    Algoritmul 2.2: Decodicarea unei reprezentari printr-un cod prex

  • c 2008, Radu-Lucian LupsaCapitolul 2. Notiuni de teoria informatiei 33

    Decodicarea se face astfel: La ^nceput x este radacina arborelui. Luam dinsirul s primul element; acesta are valoarea 0. Cobora^m ^n arbore de-a lungulmuchiei etichetate cu 0 si ajungem la frunza etichetata ,,a\. Deoarece amajuns la o frunza, punem mesajul din eticheta frunzai | adica ,,a\ | ^n sirulde mesaje decodicat si revenim la radacina. Urmeaza simbolul de cod 1;cobora^m de-a lungul muchiei 1 si ajungem ^n nodul parinte ale nodurilor ,,b\,,,c\ si ,,d\. Urmeaza simbolul 1; cobora^m de-a lungul muchiei 1 si ajungem lafrunza ,,c\; adaugam ,,c\ la sirul de mesaje si revenim la radacina. Continua^nd^n acelasi fel, vom obtine ^n continuare mesajele ,,e\ si ,,a\. Sirul de mesajetransmis este deci ,,acea\.

    2.2.3. Lungimile cuvintelor unui cod prexI^n cele ce urmeaza, vom examina o conditie necesara si sucienta

    pentru existenta unui cod prex cu lungimi date ale cuvintelor, iar apoi vomarata ca aceasta conditie este de asemenea necesara pentru existenta unui codunic decodabil.

    Teorema 2.5 Fiind data o multime de mesaje M cel mult numarabila si omultime de simboluri S nita ava^nd cel putin 2 elemente distincte, pentruorice cod c : M ! S cu proprietatea de prex, lungimile cuvintelor de codli = jc(i)j, i 2M , satisfac urmatoarea inegalitate (inegalitatea lui Kraft):X

    i2MjSjli 1 (2.2)

    si, reciproc, daca numerele naturale (li)i2M satisfac inegalitatea (2.2) atunciexista un cod prex c :M ! S ava^nd lungimile cuvintelor jc(i)j = li, 8i 2M .

    Demonstratie. Vom nota ^n continuare d = jSj si K =Pm2M dlm .Vom demonstra ^nta^i prima implicatie, pentru cazul ^n care multimea

    mesajelor M este nita. Demonstratia va construita prin inductie dupamaximul k al lungimilor cuvintelor de cod (k = maxm2M lm).

    Pentru k = 1, ^nseamna ca toate cuvintele de cod sunt de lungime 1 si^n consecinta sunt ^n numar de cel mult d. Ca urmare

    K =Xm2M

    d1 = jM j d1 d d1 = 1:

    Presupuna^nd inegalitatea lui Kraft adevarata pentru coduri de lungimemaxima k = k0, pentru un k0 2 IN arbitrar, sa demonstram ca are loc sipentru coduri de lungime maxima k = k0+1. Pentru aceasta, sa construimmultimile de mesaje

    Mx = fm 2M : primul simbol din c(m) este xg ; x 2 S:

  • c 2008, Radu-Lucian Lupsa34 2.2. Coduri cu proprietatea de prefix

    Se observa imediat ca (Mx)x2S sunt disjuncte doua ca^te doua si ca reuniunealor este M . Ca urmare

    K =Xx2S

    Xm2Mx

    dlm :

    Pentru ecare x 2M , restrictia lui c la Mx, cjMx , este de asemenea un codprex. Distingem ^n continuare trei cazuri:

    DacaMx are cel putin 2 elemente, rezulta ca toate cuvintele de cod aleelementelor din Mx au lungime mai mare sau egala cu 2, deoarece ^ncaz contrar singurul cuva^nt de cod de lungime 1, anume x, ar prexpentru toate celelalte. Elimina^nd din toate cuvintele de cod primulsimbol obtinem un nou cod prex pentru Mx. Acest cod prex aretoate cuvintele de cod lungime cel mult k0 si ca urmare, conformipotezei de inductie, satisface inegalitatea lui Kraft, adicaX

    m2Mxd(lm1) 1;

    de unde Xm2Mx

    dlm 1d:

    Daca Mx are un singur element, cuva^ntul de cod asociat acestui ele-ment are lungime cel putin 1 si ca urmare din nouX

    m2Mxdlm 1

    d:

    Daca Mx = ;, avemP

    m2Mx dlm = 0 1d .

    I^nsuma^nd acum pentru toate submultimile Mx, obtinem:

    K =Xx2S

    Xm2Mx

    d(lm) Xx2S

    1

    d= 1:

    I^n cazul unei multimi M numarabile, construim

    Ml = fm 2M : jc(m)j lg ; l 2 IN

    si notam

    Kl =X

    m2Mkd(lm):

    Deoarece, pentru ecare l 2 IN, cjMl este un cod prex, rezulta Kl 1,8l 2 IN. Dar (Kl)l2IN este un subsir al sirului sumelor partiale ale unei

  • c 2008, Radu-Lucian LupsaCapitolul 2. Notiuni de teoria informatiei 35

    Algoritmul Construieste codintrarea: (lm)m2M IN satisfaca^nd (2.2)iesirea: c :M ! S cod prex cu jc(m)j = lm, 8m 2Malgoritmul:

    E:=f"gpentru l=1,maxm2M lm executa

    E0:=;pentru w 2 E executa

    pentru x 2 S executaE0:=E0 [ fw xg

    sfa^rsit pentrusfa^rsit pentruE:=E0

    pentru m 2M : lm = l executac(m):= o valoare arbitrara din EE:=E n fc(m)g

    sfa^rsit pentrusfa^rsit pentru

    sfa^rsit algoritm

    Algoritmul 2.3: Constructia unui cod prex cu lungimi date ale cuvintelor de cod

  • c 2008, Radu-Lucian Lupsa36 2.2. Coduri cu proprietatea de prefix

    permutari a seriei cu termeni pozitiviP

    m2M dlm . De aici rezulta ca seria

    este convergenta si suma ei K este la ra^ndul ei mai mica sau egala cu 1.Sa demonstram acum reciproca, si anume ca inegalitatea lui Kraft

    implica existenta unui cod prex. Constructia codului va realizata dealgoritmul 2.3. Demonstram ^n continuare corectitudinea acestui algoritm.

    Vom nota ^n cele ce urmeaza cu Ek valoarea lui E ^n cadrul iteratieil = k imediat dupa executia instructiunii E:=E0.

    Mai ^nta^i, pentru a demonstra ca lungimile cuvintelor de cod sunt^ntr-adevar cele dorite, sa aratam ca toate cuvintele din Ek au lungime k.I^ntr-adevar, la prima iteratie cuvintele din E1 se obtin prin concatenareaca^te unui simbol din S la sirul vid. Apoi, cuvintele din Ek+1 se obtin dincuvintele ramase din Ek dupa atribuirea unora ca si cuvinte de cod prinadaugarea la nal a ca^te unui simbol din S. Ca urmare, cuvintele din Ek+1sunt de lungime k.

    Sa aratam acum ca se obtine un cod prex. Daca un cuva^nt din Ekeste atribuit unui mesaj, cuva^ntul de cod respectiv este eliminat din Ek.Cuvintele ce vor atribuite ^n continuare pot avea prexe de lungime kdoar dintre cuvintele ramase ^n Ek.

    Mai trebuie aratat ca exista ^ntotdeauna ^n E o valoare de atribuit luic(m). Pentru aceasta, vom arata caX

    m2Mlmk

    dklm jEkj (2.3)

    La prima iteratie, jEkj = d siXm2Mlmk

    dklm = d K d = jEj

    Presupuna^nd ca (2.3) are loc la iteratia cu l = k, la iteratia urmatoare, ^ncare l = k + 1, avemX

    m2Mlmk+1

    dk+1lm = d Xm2M

    lmk+1

    dklm =

    = d

    0B@Xm2Mlmk

    dklm Xm2Mlm=k

    dklm

    1CA = d(jEkj jfm 2M : lm = kgj) == jEk+1j

    unde ultima egalitate rezulta din modul de constructie a lui Ek+1 din Ekprin eliminarea unui numar de elemente egal cu numarul de cuvinte de

  • c 2008, Radu-Lucian LupsaCapitolul 2. Notiuni de teoria informatiei 37

    cod de lungime k urmata de ^nlocuirea ecarui cuva^nt ramas cu d cuvinteobtinute prin adaugarea ecarei litere posibile din S.

    Observam acum ca suma din inegalitatea (2.3) are un numar de termenide valoare 1 egal cu numarul de cuvinte de lungime k de obtinut si, caurmare, exista ^n Ek suciente cuvinte.}

    Exemplul 2.7: Dorim construirea unui cod prex pentru multimea M =fa;b; c;d; eg si multimea de simboluri de cod S = f0; 1g cu urmatoarelelungimi ale cuvintelor de cod: la = 3, lb = 1, lc = 3, ld = 3, le = 3.

    Rezolvare: mai ^nta^i vericam daca este satisfacuta inegalitatea luiKraft: X

    m2MjSjlm = 23 + 21 + 23 + 23 + 23 = 1 1;

    inegalitatea este satisfacuta si prin urmare exista un cod prex.

    Constructia propriu-zisa este aratata ^n gura 2.4. Cerculetele de-semneaza nodurile corespunzatoare elementelor din multimea E.

    Radacinaarborelui

    (a) Initializarea:E = f"g

    0 1

    b

    (b) Iteratial = 1: E =f1g si a fostplasat ,,b\

    0 1

    0 1b

    (c) Iteratia l = 2:E = f10; 11g

    a

    b

    0 1

    0 1

    0 1 0 1

    dc e

    (d) Ultima iteratie, l = 3: E = ;si codul este complet generat

    Figura 2.4: Constructia unui cod prex cu lungimi xate ale cuvintelor de cod(exemplul 2.7)

  • c 2008, Radu-Lucian Lupsa38 2.2. Coduri cu proprietatea de prefix

    Vom arata ^n continuare ca inegalitatea lui Kraft este o conditie nece-sara pentru existenta codurilor unic decodabile, nu doar a celor prex. Avem:

    Teorema 2.6 (McMillan) Pentru orice cod unic decodabil c :M ! jSj areloc inegalitatea:

    nXm2M

    dlm 1 (2.4)

    unde lm = jc(m)j, m 2M si d = jSj.Demonstratie. Consideram mai ^nta^i cazul ca^nd M este nita. Sa notamcu E =

    Pnm2M d

    lm . Sa luam un k 2 IN arbitrar si sa calculam:

    Ek =X

    (m1;:::;mk)2Mkdlm1 : : : dlmk

    =X

    (m1;:::;mk)2Mkd(lm1+:::+lmk )

    (2.5)

    Regrupam acum termenii din (2.5) dupa valorile sumei lm1 + : : : + lmk .Pentru aceasta, vom nota cu N(k; l) numarul de termeni din dezvoltarea(2.5) pentru care lm1 + : : :+ lmk = l. Cu alte cuvinte,

    N(k; l) =(m1; : : : ;mk) 2Mk : lm1 + : : :+ lmk = l :

    Mai observam cak lm1 + : : :+ lmk lmax k

    unde lmax este maximul lungimii cuvintelor de cod (lmax = maxm2M lm).Obtinem:

    Ek =

    lmax kXl=k

    N(k; l) dl: (2.6)

    Sa observam acum ca N(k; l) este numarul de siruri de k mesaje pentrucare lungimea codicarii sirului este l. Deoarece codul este unic decodabil,aceste codicari sunt distincte si ca urmare N(k; l) este cel mult egal cunumarul de siruri distincte de l simboluri de cod, adica

    N(k; l) dl:I^nlocuind ^n (2.6), obtinem:

    Ek lmax kXl=k

    dl dl = lmax k k + 1 lmax k; (2.7)

    adicaEk lmax k: (2.8)

  • c 2008, Radu-Lucian LupsaCapitolul 2. Notiuni de teoria informatiei 39

    Aceasta inegalitate are loc pentru orice k 2 IN. Daca am avea E > 1,atunci pentru un k sucient de mare am avea Ek > lmax k; prin urmareE 1.

    Daca M este numarabila, construim multimile

    Mk = fm 2M : jc(m) kg ; 8k 2 IN

    si notam Ek =P

    m2Mk dlm . Pentru ecare k 2 IN, Mk este nita si cjMk

    este un cod unic decodabil. Ca urmare, Ek 1 pentru ecare k 2 IN.Observam acum ca E = limk!1Ek 1.}

    Corolarul 2.7 Pentru orice cod unic decodabil, exista un cod prex cu ace-leasi lungimi ale cuvintelor de cod.

    2.3. Coduri optime

    Deoarece stocarea sau transmiterea ecarui simbol de cod implica uncost (timp necesar transmisiei, spatiu zic pe suportul de informatie, etc), estenatural sa cautam un cod pentru care numarul de simboluri de cod necesaretransmiterii sirului de mesaje al sursei este ca^t mai mic. Se impun ^nsa ca^tevaprecizari cu privire la aceasta minimizare.

    Mai ^nta^i, codul trebuie elaborat necunosca^nd informatia particularape care urmeaza s-o trimita sursa. Prin urmare, nu se poate cere minimizarealungimii reprezentarii informatiei transmise efectiv de sursa. Se va minimizadeci numarul mediu de biti necesari reprezentarii unui mesaj al sursei.

    I^n al doilea ra^nd, acest numar mediu de biti se considera ^n sensprobabilistic, de valoare medie a unei variabile aleatoare. Anume, ecare mesajal sursei poate considerat o variabila aleatoare cu valori din multimea Mde mesaje ale sursei. Lungimea reprezentarii mesajului este de asemenea ovariabila aleatoare, a carei valoare medie este ceea ce dorim sa minimizam.

    Probabilitatile diferitelor mesaje ale sursei se pot estima pe diversecai e analiza^nd teoretic fenomenele pe baza carora functioneaza sursa, eanaliza^nd statistic siruri de mesaje trimise de sursa. Ca exemplu, daca mesajelesursei sunt litere ce alcatuiesc un text ^ntr-o anumita limba, se poate deter-mina statistic frecventa ecarei litere, precum si frecventele unor succesiunide litere.

  • c 2008, Radu-Lucian Lupsa40 2.3. Coduri optime

    2.3.1. Cantitatea de informatieCantitatea de informatie purtata de un mesaj este o masura a incer-

    titudinii pe care destinatarul o avea imediat ^nainte de primirea mesajului sicare este eliminata ^n urma primirii mesajului.

    Cantitatea de informatie purtata de un mesaj trebuie deci sa e micadaca pentru destinatar evenimentul anuntat de mesaj era aproape sigur simare daca este un eveniment total neasteptat. Este de dorit, de asemenea,ca masura informatiei sa e aditiva, ^n sensul ca privind ca un singur mesajo succesiune de doua mesaje, cantitatea de informatie purtata de mesajulcompus sa e suma cantitatilor de informatie purtate de cele doua mesajeseparat.

    Asa cum vom vedea ^n continuare, cantitatea de informatie purtatade un mesaj va xa o limita inferioara teoretica a numarului de simboluri decod necesare codicarii mesajului.

    De notat ca cantitatea de informatie nu are nici o legatura cu utili-tatea informatiei.

    Denitia 2.8 Fie o sursa care emite un sir de mesaje m1;m2; : : : ;mt 2 M .Cantitatea de informatie adusa de mesajul mt este

    info(mt) = log2 Pr(mtjm1;m2; : : : ;mt1):Altfel spus, cantitatea de informatie adusa de un mesaj mt ^n contex-

    tul (adica urma^nd dupa) m1, m2,. . . ,mt1 este minus logaritmul probabilitatiica al t-lea mesaj sa e mt, conditionata de faptul ca mesajele precedente aufost m1, m2,. . . ,mt1.

    I^n cazul unei surse ergotice, adica pentru care probabilitatea ca unmesaj sa aiba o anumita valoare este independenta de mesajele anterioare side pozitia (numarul de ordine) mesajului ^n sirul de mesaje, putem, pentruecare m 2 M , sa notam cu pm probabilitatea ca un anumit mesaj din sirulde mesaje sa aiba valoarea m. Atunci cantitatea de informatie adusa de unmesaj m este info(m) = log2 pm.

    Unitatea de masura pentru cantitatea de informatie este bitul.A nu se confunda bitul cu sensul de unitate de masura pentru canti-

    tatea de informatie cu bitul cu sensul de cifra binara. Exista o legatura ^ntreaceste notiuni, si anume, asa cum vom vedea, pentru a transmite un bit deinformatie avem nevoie cel putin de un bit (cifra binara).

    Exemplul 2.8: Daca emitatorul anunta receptorului rezultatul aruncarii uneimonede, mesajul a cazut cu fata ^n sus poarta o cantitate de informatie egalacu log2 12 = (1) = 1bit.

  • c 2008, Radu-Lucian LupsaCapitolul 2. Notiuni de teoria informatiei 41

    Exemplul 2.9: I^n textul acestei lucrari, 10,7% dintre litere sunt ,,a\, si doar1,1% sunt ,,b\. Cu aceste cunostinte, receptorul se va astepta de la ecarelitera sa e ,,a\ cu probabilitate de 10,7% si ,,b\ cu probabilitate de 1,1%. I^naceste conditii, ecare litera ,,a\ poarta log2 0;107 3;224 biti de informatie,si ecare litera ,,b\ poarta log2 0;011 6;5 biti.

    Exemplul 2.10: Presupunem ca emitatorul informeaza receptorul asuprarezultatului aruncarii unui zar. Daca emitatorul trimite mesajul numarul este^ntre 1 si 4 cantitatea de informatie este log2 46 0;58 biti. Daca emitatorulanunta acum ca numarul este 3, probabilitatea acestui caz, cu informatiiledisponibile imediat ^nainte, este 14 , de unde cantitatea de informatie purtatade mesajul numarul este 3 este log2 14 = 2 biti. Sa observam ca, dacaemitatorul ar spus de la ^nceput numarul este 3, cantitatea de informatietransmisa ar fost log2 16 2;58 biti.

    Denitia 2.9 Fie o sursa de informatie ce emite mesaje dintr-o multime M ,ecare mesaj m 2 M ava^nd o probabilitate pm de-a emis. Se numesteentropia sursei de informatie cantitatea

    H = Xm2M

    pm log pm (2.9)

    Cu alte cuvinte, entropia este cantitatea medie de informatie permesaj.

    2.3.2. Lungimea medie a cuvintelor de cod

    Denitia 2.10 Fie o sursa ce emite mesaje dintr-o multimeM . Pentru ecarem 2 M , e pm probabilitatea mesajului m si e c : M ! S un cod unicdecodabil. Se numeste lungimea medie a cuvintelor codului c valoarea

    l =Xm2M

    pm jc(m)j:

    Denitia 2.11 Un cod unic decodabil c : M ! S se numeste cod optimdaca lungimea medie a cuvintelor sale este mai mica sau egala deca^t lungimeamedie a cuvintelor oricarui cod unic decodabil c0 :M ! S.

    Exista urmatoarea limita inferioara pentru lungimea medie a cuvin-telor de cod:

  • c 2008, Radu-Lucian Lupsa42 2.3. Coduri optime

    Teorema 2.12 Fie o sursa ce emite mesaje dintr-o multimeM , eH entropiasursei si e c : M ! S un cod unic decodabil. Atunci lungimea medie l acuvintelor codului c satisface

    l Hlog2 jSj

    : (2.10)

    I^n particular, daca jSj = 2, atunci rezulta l H. Cu alte cuvinteavem nevoie cel putin de un simbol binar (un bit) pentru a transmite un bitde informatie.

    Denitia 2.13 Se numeste ecienta unui cod raportul = Hl log2 jSj

    , unde H

    este entropia sursei, l este lungimea medie a cuvintelor de cod, iar S estemultimea simbolurilor de cod.

    Se numeste redundanta relativa valoarea 1 .Ecienta si redundanta relativa sunt numere cuprinse ^ntre 0 si 1.Valoarea minima, data teorema 2.12, pentru lungimea medie a cu-

    vintelor de cod poate atinsa efectiv, adica se poate obtine ecienta = 1,doar ^n anumite cazuri. Motivul pentru care ea nu poate ^ntotdeauna atinsaeste data de natura discreta a simbolurilor de cod. Ideal, lungimea cuvintelorde cod ar trebui sa e lm = logjSj pm. Pentru aceste valori inegalitatea luiKraft este satisfacuta:X

    m2MjSjlm =

    Xm2M

    jSj( logjSj pm) =Xm2M

    pm = 1 1;

    prin urmare ar exista un cod unic decodabil si limita din teorema 2.12 ar atinsa:

    l =Xm2M

    pm logjSj pm

    =

    Xm2M

    pm log2 pmlog2 jSj

    =1

    log2 jSj Xm2M

    pm log2 pm!=

    H

    log2 jSj:

    Acest lucru se poate realiza ^nsa numai daca lm = logjSj pm sunt toate^ntregi.

    I^n cazul general putem doar sa alegem ca lungimi ale cuvintelor decod valorile mai mari, lm = d logjSj pme. Pentru aceste valori avem

    logjSj pm lm < logjSj pm + 1de unde rezulta:

  • c 2008, Radu-Lucian LupsaCapitolul 2. Notiuni de teoria informatiei 43

    Teorema 2.14 Fie o sursa ergotica ce emite mesaje dintr-o multime M , eH entropia sursei si e S o multime de simboluri de cod. Atunci exista uncod c : M ! S unic decodabil a carui lungime medie l a cuvintelor de codsatisface

    H

    log2 jSj l < H

    log2 jSj+ 1: (2.11)

    Rezultatul teoremei precedente poate ^mbunatatit daca ^n loc saconsideram mesajele sursei ca ind mesajele din M consideram succesiunide mesaje din M , construim un cod pentru acestea din urma si determinamraportul dintre lungimea medie a cuva^ntului de cod si numarul de mesaje dinM codicate prin acesta. I^n detaliu, constructia este urmatoarea:

    Fixam k 2 IN. Consideram o a doua sursa, ale carei mesaje vor suc-cesiuni de k mesaje ale sursei originale. Multimea de mesaje ale noii surse esteprin urmare Mk. Probabilitatile mesajelor sunt p(m1;:::;mk) = pm1 : : : pmk .Vom nota cu Hk entropia noii surse. Avem

    Hk =X

    (m1;:::;mk)2Mkp(m1;:::;mk) log2 p(m1;:::;mk) =

    =X

    (m1;:::;mk)2Mkpm1 : : : pmk (log2 pm1 + : : :+ log2 pmk) =

    =kXi=1

    X(m1;:::;mk)2Mk

    pm1 : : : pmk log2 pmi =

    =kXi=1

    0@ X(m1;:::;mi1;mi+1;:::;mk)2Mk1

    pm1 : : : pmi1 pmi+1 : : : pmk

    1A 0@ X

    mi2Mpmi log2 pmi

    1A ==

    kXi=1

    1 H =

    =k H

    Conform teoremei 2.14, exista un cod c : Mk ! S pentru carelungimea medie a cuvintelor de cod, l(k), satisface

    Hklog2 jSj

    l(k) < Hklog2 jSj

    + 1:

  • c 2008, Radu-Lucian Lupsa44 2.3. Coduri optime

    Numarul mediu de simboluri de cod utilizate pentru a transmite un mesaj din

    M este l(k)

    k , care este delimitat de

    H

    log2 jSj l

    (k)

    k 2 si n nu este de forma (jSj 1)k + 1 cu k 2 IN, astfelca nu s-ar putea uni de ecare data exact jSj arbori, la prima unire se voruni (n 2) mod (jSj 1) + 2 arbori, astfel ^nca^t la toate celelalte uniri sa seuneasca ca^te jSj arbori si ^n nal sa rama^na exact un arbore.Exemplul 2.11: Fie o sursa ava^nd multimea mesajelor posibile

    M = fa;b; c;d; eg

    cu probabilitatile corepsunzatoare pa = 0;35, pb = 0;15, pc = 0;15, pd = 0;15,pe = 0;20 si e alfabetul canalului S = f0; 1g. Generarea codului optim seface astfel (vezi g. 2.5):

    I^n prima faza creem noduri izolate corespunzatoare mesajelor sursei(g. 2.5(a));

    Alegem doua noduri cu cele mai mici probabilitati si le unim. Acestea pot ,,b\ cu ,,c\, ,,b\ cu ,,d\ sau ,,c\ cu ,,d\. Oricare dintre alegeri duce la un

  • c 2008, Radu-Lucian LupsaCapitolul 2. Notiuni de teoria informatiei 45

    Algoritmul Humanintrarea: M multime nita de mesaje

    pm 2 (0; 1), m 2 M , probabilitatile mesajelor;P

    m2M pm = 1 S =fs1; s2; : : : ; sdg multime nita de simboluri de cod, d 2

    iesirea: c :M ! S cod prexalgoritmul:

    E:=Md0:=(jM j 2) mod (jSj 1) + 2ca^t timp jEj > 1 executa

    alege e1; : : : ; ed0 2 E cu pei pe , 8i 2 f1; : : : ; d0g ; 8e 2 E nfe1; : : : ; ed0g

    creaza t unicpentru i 2 f1; : : : ; d0g executa

    pune ei ca u al lui ts(t;ei):=si

    sfa^rsit pentrupt:=

    Pd0i=1 pei

    E:=(E n fe1; : : : ; ed0g) [ ftgd0:=d

    sfa^rsit ca^t timpc:=codul prex asociat unicului arbore din E

    sfa^rsit algoritm

    Algoritmul 2.4: Algoritmul lui Human

  • c 2008, Radu-Lucian Lupsa46 2.3. Coduri optime

    cod optim. Sa alegem ,,b\ cu ,,c\. Calculam si probabilitatea arboreluirezultat: 0;15 + 0;15 = 0;3. (g. 2.5(b)).

    I^n continuare unim din nou arborii de probabilitati minime; acum acestiasunt ,,d\ si ,,e\ (g. 2.5(c)).

    Avem acum doua posibilitati: arborele ce contine pe ,,b\ si pe ,,c\ poate unit e cu arborele format din ,,a\, e cu arborele format din ,,d\ si,,e\. Alegem a doua varianta.

    I^n nal unim cei doi arbori ramasi.Avem acum codurile mesajelor: c(a) = 0, c(b) = 100, c(c) = 101, c(d) = 110,c(e) = 111. Lungimea medie a cuvintelor de cod este

    l = 0;35 1 + 0;15 3 + 0;15 3 + 0;15 3 + 0;2 3 = 2;3

    Pentru comparatie, entropia este

    H = 0;35 log2 0;35 + 0;15 log2 0;15 + 0;15 log2 0;15++ 0;15 log2 0;15 + 0;2 log2 0;2

    2;226121

    d

    0.35 0.15 0.15 0.15

    ba

    0.20

    ec(a) Pasul 1

    b c

    0.35

    a

    0.30

    d

    0.15 0.20

    e

    (b) Pasul 2

    0.35

    a

    0.30

    cb

    0.35

    d e(c) Pasul 3

    0.35

    a

    cb d e

    0.65

    (d) Pasul 4

    a

    cb d e

    0 1

    0 1 10

    10

    (e) Arborele nal

    Figura 2.5: Functionarea algoritmului Human, exemplul 2.11

  • c 2008, Radu-Lucian LupsaCapitolul 2. Notiuni de teoria informatiei 47

    Daca la pasul 4 s-ar ales cealalta posibilitate, ar rezultat multimeade arbori din gura 2.6(a) si ^n nal arborele asociat codului prex din gura 2.6(b).Sa observam ca se obtine exact aceeasi lungime medie a cuvintelor de cod:

    l = 0;35 2 + 0;15 3 + 0;15 3 + 0;15 2 + 0;2 2 = 2;3

    b c

    0.65

    a

    0.35

    ed

    (a) Pasul 4

    b c

    a ed

    0 1

    0 1 1

    0 1

    0

    (b) Arborele nal

    Figura 2.6: Varianta alternativa pentru pasii 4 si 5 (exemplul 2.11)

    Exemplul 2.12: Fie o sursa ava^nd multimea mesajelor posibile

    M = fa;b; c;d; e; fgcu probabilitatile corepsunzatoare pa = 0;4, pb = 0;15, pc = 0;15, pd = 0;1,pe = 0;1, pf = 0;1 si e alfabetul canalului S = f0; 1; 2g.

    Constructia codului prin algoritmul lui Human este prezentata ^ngura 2.7. Lungimea medie a cuvintelor de cod este l = 1;6, entropia esteH 2;346439 si avem

    H

    log2 jSj 2;346439

    1;5849625 1;4804382 1;6 = l

    Teorema 2.15 Codul obtinut prin algoritmul Human este optim.

    Pentru demonstratie avem nevoie de ca^teva leme ce descriu pro-prietati ale unui cod optim. I^n cele ce urmeaza vom nota cu L(c) lungimeamedie a cuvintelor unui cod c.

    Lema 2.16 Fie M multimea mesajelor sursei, e pm, m 2M , probabilitatilemesajelor sursei, e S alfabetul canalului si e c : M ! S un cod optim.Pentru orice mesaje m1;m2 2M , daca pm1 < pm2 atunci jc(m1)j jc(m2)j.

  • c 2008, Radu-Lucian Lupsa48 2.3. Coduri optime

    0.15

    b

    0.15

    c d e f

    0.10.10.1

    a

    0.4

    (a) Pasul 1

    0.15

    b

    0.15

    ca

    0.4 0.2

    d e

    f

    0.1

    (b) Pasul 2

    a

    0.4 0.4

    cb f

    0.2

    d e(c) Pasul 3

    1 20

    0 1 2 0 1a

    cb f d e(d) Arborele nal

    Figura 2.7: Functionarea algoritmului lui Human, exemplul 2.12

    Demonstratie. Presupunem contrariul: 9m1;m2 2 M , pm1 < pm2 sijc(m1)j < jc(m2)j. Construim atunci un alt cod, c0 : M ! S, prin in-terschimbarea cuvintelor de cod asociate mesajelor m1 si m2:

    c0(m) =

    8

  • c 2008, Radu-Lucian LupsaCapitolul 2. Notiuni de teoria informatiei 49

    lungimile cuvintelor de cod, putem, fara a restra^nge generalitatea, sa pre-supune ca c este cod prex.

    Consideram arborele asociat codului c. Vom numi numarul de pozitiilibere ale unui nod intern (un nod ce are cel putin un u) valoarea jSj minusnumarul de i. Observam urmatoarele:

    Cu exceptia penultimului nivel, ecare nod intern are zero pozitiilibere I^ntr-adevar, ^n caz contrar s-ar putea muta o frunza de peultimul nivel ca descendent al nodului cu cel putin o pozite libera;prin aceasta operatie ar scadea lungimea cuva^ntului de cod core-spunzator si ca urmare ar scadea lungimea medie a cuvintelor decod, contrazica^nd ipoteza ca c este optim.

    Suma numerelor pozitiilor libere ale nodurilor penultimului nivel estecel mult jSj 2. Daca arborele are ^naltime 1, atunci unicul nodintern este radacina, aceasta are cel putin 2 i, deoarece jM j 2, si,^n consecinta, numarul pozitiilor libere este cel mult jSj 2. Con-sideram acum un arbore de ^naltime cel putin 2 si sa presupuna^ndprin absurd ca am avea jSj 1 pozitii libere. Fie t un nod intern depe penultimul nivel si e k numarul de descendenti ai sai. Nodul tare jSjk pozitii libere, deci mai rama^n cel putin k 1 pozitii liberela celelalte noduri. Mutam k 1 dintre descendentii lui t pe pozitiilibere ale altor noduri ale penultimului nivel; lungimile cuvintelor decod se pastreaza. Acum t are un singur descendent. Putem eliminanodul t subordona^nd unicul sau descendent direct parintelui lui t;^n acest fel lungimea cuva^ntului de cod corespunzator scade cu 1 silungimea medie a cuva^ntului de cod scade cu o valoare nenula, ceeace contrazice din nou ipoteza ca c e optim.

    Pentru un arbore cu k noduri interne si cu numarul total de pozitiilibere 0, numarul de frunze, care este egal cu numarul n de mesaje, esten = k (jSj1)+1. Acest lucru se demonstreaza imediat prin inductie dupak. Daca arborele are ^n total j pozitii libere, prin completarea acestora cufrunze ar rezulta un arbore cu 0 pozitii libere si n+ j frunze; prin urmare

    n = k (jSj 1) + 1 jNota^nd q = jSj j 2, avem

    n = k (jSj 1) + q jSj+ 3 = (k 1) (jSj 1) + 2 + qDeoarece 0 j jSj 2 rezulta 0 q jSj 2 de unde

    q = (n 2) mod (jSj 1)Penultimul nivel contine cel putin un nod intern, de unde rezulta ca

    pe ultimul nivel exista cel putin jSj j frunze. Cum jSj j = q+2 rezultaca pe ultimul nivel avem cel putin

    q + 2 = (n 2) mod (jSj 1) + 2

  • c 2008, Radu-Lucian Lupsa50 2.3. Coduri optime

    frunze.}

    Demonstratia teoremei 2.15. Fie n numarul de mesaje. Vom demonstra

    prin inductie dupa numarul k =l

    n1jSj1

    m.

    Pentru k = 1, adica n jSj, algoritmul lui Human face o singuraunicare, rezulta^nd cuvinte de cod de lungime 1 pentru toate mesajele.Un astfel de cod este optim, deoarece cuvinte de cod de lungime mai micadeca^t 1 nu sunt permise.

    Presupunem acum ca algoritmul Human genereaza codul optim pen-tru un k dat si sa-i demonstram optimalitatea pentru k + 1. Sa luam decio multime de mesaje M cu k(jSj 1) + 1 jM j (k + 1)(jSj 1), sanotam cu pm, m 2M , probabilitatile mesajelor, sa notam cu ch codul gen-erat de algoritmul lui Human si cu co un cod prex optim pentru aceeasimultime de mesaje si aceleasi probabilitati si sa notam cu L(ch), respec-tiv L(co) lungimile medii ale cuvintelor de cod corespunzatoare. Avem dedemonstrat ca L(ch) L(co).

    Deoarece co este un cod optim, aplica^nd lema 2.17 deducem ca coare cel putin (n 2) mod (jSj 1) + 2 cuvinte de lungime maxima. Dinlema 2.16, deducem ca acestea sunt cuvintele corespunzatoare mesajelor cuprobabilitatile cele mai mici, adica e mesajele e1; : : : ; ed0 alese de algoritmullui Human pentru prima unicare, e mesaje de aceleasi probabilitati; ^nal doilea caz putem, prin interschimbari de cuvinte de cod, sa facem ca cele(n2) mod (jSj1)+2 cuvinte de lungime maxmima din co sa e cele alese^n prima etapa a algoritmului lui Human, fara ca prin aceasta sa pierdemoptimalitatea lui co. De asemenea, prin interschimbari de cuvinte de cod,putem face ca celor (n 2) mod (jSj 1) + 2 mesaje alese de algoritmul luiHuman sa le corespunda prin co cuvinte de cod ce difera doar prin ultimulsimbol.

    Creem acum un cod c0o : (M n fe1; : : : ; ed0g) [ ftg ! S, unde t esteun obiect nou introdus, da^nd ca valoare pentru c(t) prexul comun al luic(e1),. . . ,c(ed0). I^n acelasi mod, creem un cod c

    0h pornind de la ch. Observam

    acum ca, nota^nd pt =Pd0

    i=1 pei , avem L(c0o) = L(co)pt si analog, L(c0h) =

    L(ch) pt. Sa mai remarcam ca