CODIFICAREA INFORMATIEI

Ca parte integrata a prelucrarii informatiilor cu ajutorul calculatorului, codificarea urmareste transpunerea informatiei din forma ei primara intr-o forma accesibila calculatorului. Mecanismul codificarii trebuie sa fie simplu, astfel incat sa poata fie simplu, astfel incat sa poata fi automatizat eficient.

Definirea codului

Se poate crea un model matematic cuprinzator si general al procesului de codificare. Notam prin:

multimea simbolurilor primare de informatie. Dupa caz, S poate fi multimea caracterelor ce se pot tipari, o multime de cuvinte dintr-un anumit limbaj sau dintr-o limba, o submultime finita de numere, etc. Notam prin:

un alfabet al codificarii, in care elementele a_i le vom numi litere. Cu ajutorul literelor alfabetului A, elementele multimii S, vor fi reprezentate intr-o noua forma, forma codificata. Vom nota prin Aⁿ multimea tuturor cuvintelor de lungime n formate cu litere din A. Deci:

.

Prin A⁺ vom nota multimea tuturor cuvintelor ce se pot forma cu litere din A. Deci:

Definitie O aplicatie injectiva , se numeste codificare a simbolurilor din S, sau mai simplu cod.

Un cod pentru care toate cuvintele de cod au aceeasi lungime n se numeste uniform, iar n se numeste lungimea codului. In acest caz avem

.

Codurile care nu sunt uniforme se numesc coduri neuniforme.

Exemplu simplu de cod

In paragraful precedent am stabilit o corespondenta intre cifrele zecimale si reprezentarea lor binara. In acest caz avem de-a face cu un cod uniform, in care:

Acest cod poarta numele de cod BCD (Binary Code Decimal).

Problema decodificarii

Deoarece functia de codificare C este injectiva, rezulta ca functia este bijectiva. In acest caz problema decodificarii se pune astfel: fiind dat un cuvant , sa se determine , astfel incat C(S_j) = w sau sa se raspunda ca nu exista un astfel de S_j. Cu alte cuvinte, trebuie evaluata in w functia:

.

Pentru codurile uniforme, problema decodificarii este simpla. In schimb ea se complica la codurile neuniforme.

O posibila rezolvare a decodificarii la codurile neuniforme consta in introducerea unui simbol consacrat ca element despartitor intre 2 secvente C(w₁) si C(w₂) consecutive. Codul Morse foloseste in acest scop "pauza" de diverse lungimi. Utilizarea unui astfel de simbol determina cresterea numarului de litere cu care se codifica o succesiune de simboluri din S.

Codificarea caracterelor

Fie

multimea caracterelor tiparibile existente. Pentru codificarea acestor caractere in vederea prelucrarii lor automate, standardele internationale impune o serie de restrictii. Dupa cum se va vedea, aceste restrictii sunt foarte utile in prelucrarea automata a datelor.

Consideram multimile:

- multimea caracterelor speciale

- multimea caracterelor functionale, care nu apar la

tiparire, ci doar controleaza tiparirea.

Vom nota .

functia de codificare se defineste astfel:

unde n este 127 sau 255. Daca consideram reprezentarea binara avem de-a face cu un cod omogen pe 7 sau 8 biti.

.

Standardele de codificare impun urmatoarele conditii:

1)

2)

3)

4) Intervale:

si multimea C(S)

au intersectiile vide 2 cate 2.

Un prim sistem de codificare stabilit a fost EBCDIC (Extended Binary Decimal Interchange Code), care foloseste pentru codificare numerele intregi din intervalul [0,255]. Calculatoarele medii si mari, precum si cele mai vechi folosesc acest cod de reprezentare.

In prezent, cel mai folosit sistem de codificare este ASCII (American Standard Code for Information Interchange) care foloseste pentru codificare numerele intregi din intervalul [0,127]. Fata de conditiile 1 4 de mai sus, acest cod mai verifica relatiile:

5)

.

Proiectantii calculatoarelor din familia IBM-PC au extins codificarea ASCII, codificand o paleta larga de caractere grafice, litere ale alfabetului grec, cateva simboluri matematice, etc.

In acest scop s-au folosit numere din intervalul 128 255. Avem de-a face, astfel, cu un cod omogen pe 8 biti.

Necesitatile actuale de comunicare cu ajutorul calculatorului au impus din ce in ce mai mult un nou sistem de codificare, de data aceasta un cod omogen pe 16 biti. Este vorba de sistemul UNICODE, care include practic toate simbolurile tiparibile ale limbilor de pe glob, precum si o foarte larga paleta de caractere grafice speciale. De exemplu, cel mai nou limbaj de programare, Java, foloseste aceasta codificare a caracterelor.

Reprezentarea (codificarea numerelor intregi)

In practica constructiei calculatoarelor sunt cunoscute 3 coduri de reprezentare: codul direct, codul invers si codul complementar. Primele 2 coduri au fost folosite doar la calculatoarele din prima generatie.

Reprezentarea in cod complementar

Fie un numar intreg x, unde .

Numarul x reprezentat in cod complementar in conventie intreaga inseamna:

.

Regula practica pentru determinarea reprezentarii:

a) Daca numarul este pozitiv, atunci se transforma in binar si se reprezinta in zona standard de memorie aleasa, incadrat la dreapta in acea zona.

b) Daca numarul este negativ, se reprezinta initial modulul sau, apoi se inverseaza toti bitii acestei reprezentari obtinand codul invers. In final se aduna cifra 1 in binar in pozitia cea mai putin semnificativa, obtinandu-se codul complementar fata de 2.

In cod complementar pe n biti orice numar x cu are o reprezentare unica. Exista o configuratie unica de biti care nu reprezinta un numar. Aceasta este: 10000. pentru pastrarea consistentei in reprezentare, unele implementari atribuie acestei configuratii valoarea -2^n-1. pentru diferitele valori ale lui n, intervalele care se pot reprezenta sunt:

n = 8 [-127,127]

n = 16 [-32767,32767]

n = 32 [-2147483647, 2147438647]

Exemple

Sa se reprezinte numarul 125₍₁₀₎ in cod complementar .

Se transforma numarul 125 in baza 2, apoi se reprezinta in cod direct pe 16 pozitii binare.

125₍₁₀₎ = 1111101₍₂₎

15 14 . . . 2 1 0

Sa se reprezinte numarul -26₍₁₀₎ in cod complementar.

Se face initial reprezentarea modulului numarului : 26₍₁₀₎ = 11010₍₂₎

Reprezentarea numarului +26 in virgula fixa este :

15 14 . . . 2 1 0

- Se inverseaza toti bitii acestei reprezentari :

15 14 . . . 2 1 0

- Se aduna 1 in pozitia cea mai putin semnificativa :

15 14 . . . 2 1 0

si se obtine astfel reprezentarea numarului negativ -26₍₁₀₎ in virgula cod complementar.

Suma algebrica in mod complementar

Codul complementar este cel mai folosit de catre sistemele de calcul pentru aritmetica numerelor intregi. pentru a defini suma algebrica, vom privi [x]_c ca pe un sir de n biti, reprezentand un numar in baza 2.

Practic, reprezentand numerele in cod complementar, si presupunand ca nu apare depasire, operatiile de adunare si de scadere ale numerelor intregi se pot efectua cu ajutorul operatiei de adunare. Sau mai bine spus, a scadea un numar s dintr-un numar d inseamna a aduna algebric reprezentarile in cod complementar ale lui s si d.

Pentru operatiile de inmultire si impartire in cod complementar exista multi algoritmi. Alegerea acestora ramane in sarcina proiectantilor de procesare matematice, Practic si operatiile de inmultire (impartire se pot efectua pe baza operatiilor de adunare, prin deplasari ale reprezentarilor interne ale numerelor) .

Codificarea (reprezentarea) numerelor reale

Un numar real x, x 0 este scris cu mantisa intre 1 si 2, daca x se scrie, in baza 2, astfel:

.

Este evident ca orice numar real nenul accepta o astfel de repezentare. Aceasta reprezentare se numeste reprezentare in virgula flotanta (mobila).

Spre exemplu: 128,25₍₁₀₎ = 10000000,01₍₂₎ = 1,00000001₍₂₎

Pentru reprezentarea unui numar in virgula flotanta, sunt necesare trei zone:

zona pentru reprezentarea semnului s, care este un bit cu valoarea 0 pentru + si 1 pentru -;

zona pentru reprezentarea mantisei. Mantisa este numarul 1,m. Partea intreaga nu se reprezinta, ca avand intotdeauna valoarea 1. Din partea fractionara se retine un numar constant si finit de cifre:

zona pentru reprezentarea exponentului e. Pentru reprezentarea exponentului se utilizeaza un numar fixat de biti; pentru a se putea pune in evidenta si semnul exponentului, in zona exponentului se inscrie valoarea e+q, unde q poarta numele de deplasament. Expresia e+q poarta numele de caracteristica a numarului real x.

Adoptarea acestui mod de reprezentare s-a facut din ratiune de constructie a calculatoarelor.

Societatea de calculatoare IEEE a fost cea care s-a preocupat si a elaborat norme de reprezentare a numerelor in virgula flotanta (mobila). Practic toate firmele care fabrica astazi calculatoare si-au insusit aceste norme si le-au implementat. Pe langa standardele IEEE, firma Borland foloseste la implementarea Turbo Pascal alte doua moduri de reprezentare. Aceste moduri de reprezentare sunt redate in figura 1.

Fig.1 Standardele de reprezentare a numerelor reale

Standardele IEEE deosebesc 5 cazuri care pot sa apara la reprezentarea unui numar:

1) Daca -q < e < q+1, atunci x = (-1)^s 1, m 2^e

2) Daca e = -q, si m 0, atunci x = (-1)^s 0, m 2^e

3) Daca e = -q, si m = 0, atunci x = (-1)^s 0, (zero pozitiv sau negativ)

4) Daca e = q + 1, si m = 0, atunci x = (-1)^s , (pozitiv sau negativ)

5) Daca e = q + 1, si m 0, atunci reprezentarea nu indica nici un numar.

Specificarea lui depinde de calculator si de limbaj.

Conventiile TURBO PASCAL deosebesc 3 cazuri:

1) Daca -q < e < q+1, atunci x = (-1)^s 1, m 2^e

2) Daca e = -q, si m = 0, atunci x = 0

3) Daca e = -q, si m 0, atunci reprezentarea nu indica nici un numar.

Valorile aproximative de minim si MAXIM reprezentand valorile de cel mai mic, reprezinta cel mai mare numar reprezentabil depind de numarul bitilor caracteristici. Efectuand calcule se obtin:

- pentru caracteristica reprezentata pe 8 biti (IEEE simpla precizie si tipul REAL TURBO PASCAL).

minim 10^-38, MAXIM

Pentru caracteristica pe 11 biti (IEEE dubla precizie):

minim 10^-308, MAXIM

Exemple de reprezentari. mai intai vom arata cum se converteste un numar real in virgula flotanta. Se considera numarul: (-3572,54)₁₀

pe care intentionam sa-l reprezentam in formatul IEEE simpla precizie, IEEE dubla precizie si REAL Turbo Pascal.

Mai intai ii vom converti in baza 16, retinand 14 cifre hexazecimale semnificative, care sunt suficiente pentru reprezentarile pe care le avem in vedere, si obtinem numarul:

(-DF4,8A3D708A3D7)₁₆

Acest numar il trecem in baza 2 si obtinem:

(-110111110100, 10001010001111010111000010001010001111010111)₂.

Acum il punem in forma nominalizata, asa cum am aratat mai sus, si retinem numai 52 de cifre dupa virgula:

(-1,1011111010010001010001111010111000010001010001111010)₂

Din aceasta forma vom prelua, incepand cu bitul dupa virgula, atatia biti cati sunt necesari pentru partea de mantisa a fiecarei reprezentari. Rescriem numarul rezultat in baza 16:

(-1,BE1947AE1147)₁₆

Semnul fiind "-" bitul de semn s va fi 1.

Exponentul e = (11)₁₀ valabil pentru toate cele trei reprezentari.

Caracteristica c difera la cele trei reprezentari:

- simpla precizie:

c = e +127 = (138)₁₀ = (8A)₁₆ = (10001010)₂.

- dubla precizie:

c = e +1023 = (134)₁₀ = (40A)₁₆ = (10000001010)₂.

- TURBO Pascal:

c = e +129 = (140)₁₀ = (8C)₁₆ = (10001100)₂.

In sfarsit, colationand cele trei zone: semn, caracteristica si mantisa, in locurile si numarul de biti specificati, obtinem cele trei reprezentari:

C55F48A3

Simpla precizie:

Dubla precizie.

	C0ABF9147AF1147A

Pentru varianta TURBO PASCAL, avem:

		DF48A3D7088C