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.
curs de coduri de la Universitatea Bucuresti
Documentul este oferit gratuit,
trebuie doar să te autentifici in contul tău.
