Teoria Codurilor

Curs
9.3/10 (4 voturi)
Domeniu: Alte domenii
Conține 20 fișiere: pdf
Pagini : 238 în total
Cuvinte : 78203
Mărime: 2.34MB (arhivat)
Cost: Gratis
Profesor îndrumător / Prezentat Profesorului: Adrian Atanasiu
curs de coduri de la Universitatea Bucuresti

Extras din document

Codificare ¸si decodificare

1.1 Codificare

Definit¸ia 1.1 Fiind date mult¸imile A (alfabetul sursØa) ¸si B (alfabetul cod), o codificare

este o aplicat¸ie injectivØa K : A ! B¤.

Elementele mult¸imii K(A) µ B¤ se numesc cuvinte-cod, iar K(A) se nume¸ste cod.

DacØa B are numai douØa simboluri, codificarea K se nume¸ste binarØa.

Exemplul 1.1 Printre secvent¸ele binare de lungime 5, numØarul celor care au doi

de 1 este C2

5 = 10. Ele pot fi folosite pentru a codifica cifrele din scrierea zecimalØa

(Tabelul 1.1).

Tabelul 1.1: Codul ”doi-din-cinci”

Simbol zecimal Cuvˆant cod

1 11000

2 10100

3 01100

4 10010

5 01010

6 00110

7 10001

8 01001

9 00101

0 00011

Mesajul 0017300 are codul 110001000101100. De remarcat cØa ˆ1ntre cuvintele cod

nu se lasØa nici un spat¸iu, deoarece ”spat¸iu” poate fi el ˆ1nsusi un simbol-cod. Astfel

de exemplu, codul Morse are alfabetul B = f:;¡; spat¸iug.

Decodificarea se face foarte simplu: se ˆ1mparte mesajul codificat ˆ1n grupe de cˆate

cinci caractere ¸si se vede cifra din tabel corespunzØatoare grupei respective. Repartizarea

cuvintelor cod a fost fØacutØa pentru a realiza ¸si o decodificare pe baza unei

1

2 PRELEGEREA 1. CODIFICARE S¸I DECODIFICARE

formule. Astfel, dacØa a0a1a2a3a4 este cuvˆantul - cod, el corespunde cifrei k datØa de

algoritmul:

begin

x := a1 + 2a2 + 4a3 + 7a4;

if x = 11 then k := 0 else k := x;

end.

Definit¸ia 1.2 Pentru o codificare K : A ! B¤, se nume¸ste ”codificare a mesajelor

(textului) sursØa” aplicat¸ia K¤ : A¤ ! B¤ definitØa recursiv prin:

² K¤(²) = ² (² este cuvˆantul vid);

² K¤(a®) = K¤(a)K¤(®); 8a 2 A; ® 2 A¤.

Definit¸ia 1.3 Codificarea K este ”unic decodabilØa” dacØa K¤ este injectivØa.

Codificarea datØa ˆ1n Exemplul 1.1 este - dupØa cum s-a observat - unic decodabilØa.

Acest lucru nu este totdeauna posibil. DacØa luØam de exemplu codificarea

K(a) = 00; K(b) = 10; K(c) = 101; K(d) = 110; K(e) = 1001;

ea nu este unic decodabilØa; astfel K¤(bd) = K¤(cb) = 101110 .

Definit¸ia 1.4 1. O codificare K : A ! B¤ ˆ1n care toate cuvintele cod au lungimea

n se nume¸ste ”codificare-bloc de lungime n”, iar K(A) este un ”cod-bloc

de lungime n”.

2. O codificare K : A ! B¤ se nume¸ste ”instantanee” dacØa K(A) are proprietatea

prefixului (dacØa ®; ®¯ 2 K(B) atunci ¯ = ²).

Codul definit ˆ1n Exemplul 1.1 este un cod - bloc de lungime 5.

Codurile bloc sunt eficiente ˆ1n cazul cˆand simbolurile sursØa au frecvent¸e egale de

aparit¸ie; ˆ1n caz contrar, ele devin greoaie ¸si sunt preferabile codurile instantanee cu

lungimi variabile ale cuvintelor cod.

Preview document

Teoria Codurilor - Pagina 1
Teoria Codurilor - Pagina 2
Teoria Codurilor - Pagina 3
Teoria Codurilor - Pagina 4
Teoria Codurilor - Pagina 5
Teoria Codurilor - Pagina 6
Teoria Codurilor - Pagina 7
Teoria Codurilor - Pagina 8
Teoria Codurilor - Pagina 9
Teoria Codurilor - Pagina 10
Teoria Codurilor - Pagina 11
Teoria Codurilor - Pagina 12
Teoria Codurilor - Pagina 13
Teoria Codurilor - Pagina 14
Teoria Codurilor - Pagina 15
Teoria Codurilor - Pagina 16
Teoria Codurilor - Pagina 17
Teoria Codurilor - Pagina 18
Teoria Codurilor - Pagina 19
Teoria Codurilor - Pagina 20
Teoria Codurilor - Pagina 21
Teoria Codurilor - Pagina 22
Teoria Codurilor - Pagina 23
Teoria Codurilor - Pagina 24
Teoria Codurilor - Pagina 25
Teoria Codurilor - Pagina 26
Teoria Codurilor - Pagina 27
Teoria Codurilor - Pagina 28
Teoria Codurilor - Pagina 29
Teoria Codurilor - Pagina 30
Teoria Codurilor - Pagina 31
Teoria Codurilor - Pagina 32
Teoria Codurilor - Pagina 33
Teoria Codurilor - Pagina 34
Teoria Codurilor - Pagina 35
Teoria Codurilor - Pagina 36
Teoria Codurilor - Pagina 37
Teoria Codurilor - Pagina 38
Teoria Codurilor - Pagina 39
Teoria Codurilor - Pagina 40
Teoria Codurilor - Pagina 41
Teoria Codurilor - Pagina 42
Teoria Codurilor - Pagina 43
Teoria Codurilor - Pagina 44
Teoria Codurilor - Pagina 45
Teoria Codurilor - Pagina 46
Teoria Codurilor - Pagina 47
Teoria Codurilor - Pagina 48
Teoria Codurilor - Pagina 49
Teoria Codurilor - Pagina 50
Teoria Codurilor - Pagina 51
Teoria Codurilor - Pagina 52
Teoria Codurilor - Pagina 53
Teoria Codurilor - Pagina 54
Teoria Codurilor - Pagina 55
Teoria Codurilor - Pagina 56
Teoria Codurilor - Pagina 57
Teoria Codurilor - Pagina 58
Teoria Codurilor - Pagina 59
Teoria Codurilor - Pagina 60
Teoria Codurilor - Pagina 61
Teoria Codurilor - Pagina 62
Teoria Codurilor - Pagina 63
Teoria Codurilor - Pagina 64
Teoria Codurilor - Pagina 65
Teoria Codurilor - Pagina 66
Teoria Codurilor - Pagina 67
Teoria Codurilor - Pagina 68
Teoria Codurilor - Pagina 69
Teoria Codurilor - Pagina 70
Teoria Codurilor - Pagina 71
Teoria Codurilor - Pagina 72
Teoria Codurilor - Pagina 73
Teoria Codurilor - Pagina 74
Teoria Codurilor - Pagina 75
Teoria Codurilor - Pagina 76
Teoria Codurilor - Pagina 77
Teoria Codurilor - Pagina 78
Teoria Codurilor - Pagina 79
Teoria Codurilor - Pagina 80
Teoria Codurilor - Pagina 81
Teoria Codurilor - Pagina 82
Teoria Codurilor - Pagina 83
Teoria Codurilor - Pagina 84
Teoria Codurilor - Pagina 85
Teoria Codurilor - Pagina 86
Teoria Codurilor - Pagina 87
Teoria Codurilor - Pagina 88
Teoria Codurilor - Pagina 89
Teoria Codurilor - Pagina 90
Teoria Codurilor - Pagina 91
Teoria Codurilor - Pagina 92
Teoria Codurilor - Pagina 93
Teoria Codurilor - Pagina 94
Teoria Codurilor - Pagina 95
Teoria Codurilor - Pagina 96
Teoria Codurilor - Pagina 97
Teoria Codurilor - Pagina 98
Teoria Codurilor - Pagina 99
Teoria Codurilor - Pagina 100
Teoria Codurilor - Pagina 101
Teoria Codurilor - Pagina 102
Teoria Codurilor - Pagina 103
Teoria Codurilor - Pagina 104
Teoria Codurilor - Pagina 105
Teoria Codurilor - Pagina 106
Teoria Codurilor - Pagina 107
Teoria Codurilor - Pagina 108
Teoria Codurilor - Pagina 109
Teoria Codurilor - Pagina 110
Teoria Codurilor - Pagina 111
Teoria Codurilor - Pagina 112
Teoria Codurilor - Pagina 113
Teoria Codurilor - Pagina 114
Teoria Codurilor - Pagina 115
Teoria Codurilor - Pagina 116
Teoria Codurilor - Pagina 117
Teoria Codurilor - Pagina 118
Teoria Codurilor - Pagina 119
Teoria Codurilor - Pagina 120
Teoria Codurilor - Pagina 121
Teoria Codurilor - Pagina 122
Teoria Codurilor - Pagina 123
Teoria Codurilor - Pagina 124
Teoria Codurilor - Pagina 125
Teoria Codurilor - Pagina 126
Teoria Codurilor - Pagina 127
Teoria Codurilor - Pagina 128
Teoria Codurilor - Pagina 129
Teoria Codurilor - Pagina 130
Teoria Codurilor - Pagina 131
Teoria Codurilor - Pagina 132
Teoria Codurilor - Pagina 133
Teoria Codurilor - Pagina 134
Teoria Codurilor - Pagina 135
Teoria Codurilor - Pagina 136
Teoria Codurilor - Pagina 137
Teoria Codurilor - Pagina 138
Teoria Codurilor - Pagina 139
Teoria Codurilor - Pagina 140
Teoria Codurilor - Pagina 141
Teoria Codurilor - Pagina 142
Teoria Codurilor - Pagina 143
Teoria Codurilor - Pagina 144
Teoria Codurilor - Pagina 145
Teoria Codurilor - Pagina 146
Teoria Codurilor - Pagina 147
Teoria Codurilor - Pagina 148
Teoria Codurilor - Pagina 149
Teoria Codurilor - Pagina 150
Teoria Codurilor - Pagina 151
Teoria Codurilor - Pagina 152
Teoria Codurilor - Pagina 153
Teoria Codurilor - Pagina 154
Teoria Codurilor - Pagina 155
Teoria Codurilor - Pagina 156
Teoria Codurilor - Pagina 157
Teoria Codurilor - Pagina 158
Teoria Codurilor - Pagina 159
Teoria Codurilor - Pagina 160
Teoria Codurilor - Pagina 161
Teoria Codurilor - Pagina 162
Teoria Codurilor - Pagina 163
Teoria Codurilor - Pagina 164
Teoria Codurilor - Pagina 165
Teoria Codurilor - Pagina 166
Teoria Codurilor - Pagina 167
Teoria Codurilor - Pagina 168
Teoria Codurilor - Pagina 169
Teoria Codurilor - Pagina 170
Teoria Codurilor - Pagina 171
Teoria Codurilor - Pagina 172
Teoria Codurilor - Pagina 173
Teoria Codurilor - Pagina 174
Teoria Codurilor - Pagina 175
Teoria Codurilor - Pagina 176
Teoria Codurilor - Pagina 177
Teoria Codurilor - Pagina 178
Teoria Codurilor - Pagina 179
Teoria Codurilor - Pagina 180
Teoria Codurilor - Pagina 181
Teoria Codurilor - Pagina 182
Teoria Codurilor - Pagina 183
Teoria Codurilor - Pagina 184
Teoria Codurilor - Pagina 185
Teoria Codurilor - Pagina 186
Teoria Codurilor - Pagina 187
Teoria Codurilor - Pagina 188
Teoria Codurilor - Pagina 189
Teoria Codurilor - Pagina 190
Teoria Codurilor - Pagina 191
Teoria Codurilor - Pagina 192
Teoria Codurilor - Pagina 193
Teoria Codurilor - Pagina 194
Teoria Codurilor - Pagina 195
Teoria Codurilor - Pagina 196
Teoria Codurilor - Pagina 197
Teoria Codurilor - Pagina 198
Teoria Codurilor - Pagina 199
Teoria Codurilor - Pagina 200
Teoria Codurilor - Pagina 201
Teoria Codurilor - Pagina 202
Teoria Codurilor - Pagina 203
Teoria Codurilor - Pagina 204
Teoria Codurilor - Pagina 205
Teoria Codurilor - Pagina 206
Teoria Codurilor - Pagina 207
Teoria Codurilor - Pagina 208
Teoria Codurilor - Pagina 209
Teoria Codurilor - Pagina 210
Teoria Codurilor - Pagina 211
Teoria Codurilor - Pagina 212
Teoria Codurilor - Pagina 213
Teoria Codurilor - Pagina 214
Teoria Codurilor - Pagina 215
Teoria Codurilor - Pagina 216
Teoria Codurilor - Pagina 217
Teoria Codurilor - Pagina 218
Teoria Codurilor - Pagina 219
Teoria Codurilor - Pagina 220
Teoria Codurilor - Pagina 221
Teoria Codurilor - Pagina 222
Teoria Codurilor - Pagina 223
Teoria Codurilor - Pagina 224
Teoria Codurilor - Pagina 225
Teoria Codurilor - Pagina 226
Teoria Codurilor - Pagina 227
Teoria Codurilor - Pagina 228
Teoria Codurilor - Pagina 229
Teoria Codurilor - Pagina 230
Teoria Codurilor - Pagina 231
Teoria Codurilor - Pagina 232
Teoria Codurilor - Pagina 233
Teoria Codurilor - Pagina 234
Teoria Codurilor - Pagina 235
Teoria Codurilor - Pagina 236
Teoria Codurilor - Pagina 237
Teoria Codurilor - Pagina 238
Teoria Codurilor - Pagina 239
Teoria Codurilor - Pagina 240
Teoria Codurilor - Pagina 241
Teoria Codurilor - Pagina 242
Teoria Codurilor - Pagina 243
Teoria Codurilor - Pagina 244
Teoria Codurilor - Pagina 245
Teoria Codurilor - Pagina 246
Teoria Codurilor - Pagina 247
Teoria Codurilor - Pagina 248

Conținut arhivă zip

  • Teoria Codurilor
    • cod1.pdf
    • cod10.pdf
    • cod11.pdf
    • cod12.pdf
    • cod13.pdf
    • cod14.pdf
    • cod15.pdf
    • cod16.pdf
    • cod17.pdf
    • cod18.pdf
    • cod19.pdf
    • cod2.pdf
    • cod20.pdf
    • cod3.pdf
    • cod4.pdf
    • cod5.pdf
    • cod6.pdf
    • cod7.pdf
    • cod8.pdf
    • cod9.pdf

Alții au mai descărcat și

Microeconomie - Grile pentru Examen

1. Definirea pieţei ca spaţiu economic înseamnă că: a) piaţa nu are întotdeauna o determinare geografică; b) piaţa este o confruntare abstractă...

Operatii Unitare

Aplicaţia 1. O pompă transportă un lichid cu densitatea de 960 kg/m3 dintr-un rezervor cu presiunea atmosferică într-un aparat în care presiunea...

Avantajele realizării modelului digital al terenului în Autocad

1. INTRODUCERE Principalele surse de date pentru un model tridimensional al terenului sunt accesibile prin: ridicări topografice terestre prin...

Recenzie Relatii Internationale

De ce mint liderii. Adevărul despre minciunile din politica internațională John J. Mearsheimer Sincer să fiu, am ales această carte deoarece m-a...

Legislatia Calitatii

Termen Definitie CONSUMATORI Persoana fizica sau grupuri de persoane fizice care nu desfasoara activitati economice OPERATORI ECONOMICI Persoana...

Toleranțe - subiecte orale

EXAMEN la TOLERANTE, Subiectul oral nr. 1 Pentru ansamblul din figura sa se prescrie un ajustaj între rulment si arbore si un ajustaj între...

Impactul Amenajarilor Hidrotehnice Asupra Mediului

Impactul produs de amenajările hidrotehnice asupra mediului reprezintă o temă complexă dezbătută atăt pe plan intern căt si internaţional. Primele...

Bazele Informaticii

1. PRELUCRAREA DOCUMENTELOR Telematica este definită ca fiind tehnica transmiterii la mare distanţă şi valorificării informaţiilor care combină...

Te-ar putea interesa și

Tehnici și Algoritmi de Codare

PRESCURTĂRI 1. INTRODUCERE O temă des cercetată în telefonia mobilă este eficienţa spectrală, care deobicei are înţelesul de densitatea...

Etica afacerilor - Factor de dezvoltare a organizației

Introducere “Dacă vrei să cunoști principiile etice pe care le împartășește o companie, uităte la felul în care tratează oamenii: clienții,...

Codul binar Golay

În domeniul matematicii și a ingineriei electronice, un cod Golay binar este un tip de cod de corectare liniară a erorilor utilizat în...

Analiza Semiotica - Ruy Blas, Victor Hugo, Actul I, Scena I

Fragmentul debutează cu didascaliile care echivalează cu descrierea romanescă a spaţiului, timpului şi personajelor. Atât detaliile privind...

Comunicarea prin Simboluri - Studiu de Caz Codul lui da Vinci

Pentru Saussure, simbolul este rezultatul uniunii semnificantului cu semnificatul, altfel spus, a formei expresiei şi a formei conţinutului. (Tran,...

Introducere în Semiotică

TUTORAT 1 UNIVERSUL SEMNULUI O INTRODUCERE Pentru a oferi noi repere societatii postmoderne a revolutiilor comunicarii si exploziei mediatice si...

Design

CAPITOLUL 1. PROBLEMATICA DESIGNULUI TEHNOSFERA SI FENOMENUL TEHNIC Peste tot, in sec 20, apare evidenta preocuparea ca obiectul produs...

Filosofie

I. Specificul si rosturile filosofiei "În timp ce în stiinta e vorba despre lucruri chiar atunci când se vorbeste despre om (omul adica e privit...

Ai nevoie de altceva?