Arhitectura calculatoarelor

Cursul 2

Reprezentarea informatiilor

Informatie Definirea informatiei

– notiune primara - greu de definit– “mesaj” care aduce o clarificare privind starea unui proces care

are mai multe stari

Cantitatea de informatie - entropia informationala– marime dependenta de gradul de dezordine al unui sistem, de

numarul maxim de stari posibile – exemple: aruncarea unei monede, aruncarea unui zar

– Shannon (1948)

x1 x2 ... xn E = - pi log2 pi

p1 p2 .... pn

- pt. 2 stari echiprobabile

E = - 2*0,5*log2 0,5 = 1 unitatea de informatie

Informatii si date pt. 2 stari echiprobabile

E = - 2*0,5*log2 0,5 = 1 unitatea de informatie

bit = binary digit pt. n stari echiprobabile

E = - log2 1/n = log2 n

data - forma de reprezentare a informatiei– data = forma – informatia = continut (semantica)

calculatorul prelucreaza date – prin interpretare (decodificare) se obtin informatii – program - secventa de prelucrare a datelor

informatica = information + automatique

Tipuri de informatie informatii numerice informatii logice de tip text informatii multimedia:

– audio– imagine– video

semnale ??????

Reprezentarea informatiilor numerice Sisteme de numeratie:

– set de simboluri– set de reguli de reprezentare– baza = numarul de simboluri folosite– sisteme ponderale/neponderale

Exemple de sisteme de numeratie– Sistemul zecimal:

• simboluri: 0, 1, ... 9

– Sistemul hexazecimal• simboluri: 0, 1, ... 9, A, B, C, D, E, F

– Sistemul binal:• simboluri: 0, 1

Reprezentarea numerelor Reprezentarea numerelor intregi pozitive

– N 0 xmxm-1xm-2....x0

– 0xi<b, xm0

– N = xm*bm + xm-1*bm-1 + .... + x0*b0

Reprezentarea numerelor zecimale

– N 0 xmxm-1xm-2....x0.x-1x-2...x-n

– 0xi<b, xm0, x-n0

– N = xm*bm + xm-1*bm-1 + .... + x0*b0 + x-1*b-1+x-2*b-2 + ... +x-n*b-n

Conversii dintr-o baza in alta Partea intreaga

N= (...(xm+0)b+xm-1)b+ ...+x1)b+x0

N=N1b+x0

N1=N2b+x1

...

Nm = 0*b+xm

Partea zecimalaN = Nîntr.+Nzec.

Nzec = x-1b-1+x-2b-2+ ...

x-1 = [Nzec*b]

Nzec*b = x-1 +N2zec

x-2= [N2zec*b]

.......

Converii binar-octal-hexazecimal

3 cifre binare = o cifra octala 4 cifre binare = o cifra hexazecimala Regula de conversie:

– se grupeaza cate 3 respectiv cate 4 biti incepand de la semnul zecimal spre stanga si spredreapta

– se complecteaza cu biti de 0

Exemple0011.1011.1110,0111.11002=3BE,7C16

001.110.111.110,011.111.2 =1676,378

Reprezentarea numerelor cu semn

Conventii de preprezentare:– semn si marime

– complement fata de 1

– complement fata de 2 !!! Important - sa se precizeze lungimea de reprezentare

Marime si semn:– bitul cel mai semnificativ - bit de semn (0-poz; 1-neg.)– restul bitilor - valoarea absoluta a numarului

– dezavantaj: probleme la implementarea operatiilor aritmetice

– exemplu: -7 1000.0111

Reprezentarea numerelor negative Complement fata de 1 (C1)

– regula: se complementeaza fiecare pozitie binara a reprezentarii valorii absolute

– bitul cel mai semnificativ - bit de semn– exemplu: -7 7=0000.0111

-7=1111.1000

Complement fata de 2 (C2)– regula1: se aduna 1 la complement fata de 1– regula2: se copiaza bitii de 0 incepand din dreapta, inclusiv primul

bit de 1, dupa care se complementeaza fiecare bit– exemplu: -22 22=0001.0110

-22=1110.1001C1+

1

1110.1010C2

Reprezentarea numerelor negative

Operatii aritmetice in C2:– adunare

(7 0000.0111)

-7 1111.1001 249

4 0000.0100 4

-3 1111.1101 253

(3 0000.0011)

– Scadere-7 1111.1001 - -7 1111.1001 +

4 0000.0100 - 4 1111.1100

-13 1111. 0101

(+13 0000.1011)

Reprezentarea in virgula flotanta Scopul:

– pt. reprezentarea numerelor foarte mari sau foarte mici

Observatii: – reprezentare discreta !!!!– nu se reprezinta toate numerele reale – limitari: numere ff. mari sau ff. mici

Exemplu de reprezentare exponentiala:– 5 cifre zecimale: 3 mantisa+ 2 cifre exponent– 0,1<mantisa<1 - forma standardizata

Reprezentarea in virgula flotanta

Observatii:– plaja foarte mare de valori

– rezolutie absoluta variabila (1096 sau 10-102)

– rezolutie relativa constanta

– este dificila reprezentarea valorii 0

– este dificila reprezentarea infinitului

– cum sa se aloce cifrele intre exponent si mantisa ?

0-0,999*1099 -0,1*10-99 0,1*10-99 0,999*1099

Reprezentarea in virgula flotanta

Formatul reprezentarii:– numarul de biti:

• 32 -simpla precizie (1 semn, 8 caracteristica 23 mantisa)• 64 - dubla precizie (1 semn, 11 caracteristica 52

mantisa)• 80 - precizie extinsa

– campuri: semn, mantisa, caracteristica

– caracteristica = exponent +1/2(interval exponent)– exemplu: exponent pe 8 biti

caracteristica= exponent +128

S Caracteristica Mantisa

Sisteme de codificare Coduri ponderale

– binar-zecimal (BCD) - numere zecimale reprezentate in binar, pe 4 biti

• sunt coduri nefolosite• necesita corectii la operatiile aritmetice• ex: 19+3=22 19+8=27

0001.1001 0001.1001

0000.0011 0000.1000

0001.1100 1CH 0010.0001 21H

0000.0110 +6 0000.0110 +6

0020.0010 22 0010.0111 27Corectie

Coduri ponderale si neponderale

– BCD despachetat - o cifra zecimala / octet – BCD impachetat - 2 cifre zecimale / octet– Codul 2421 - ex: 9 ->1111,

5->0101 sau 1100(ambiguitate)

Coduri neponderale:– BCD cu paritate: 4+1 bit

• ex: 4-> 01001, 5-> 01010

– 2 din 5: 2 biti de 1 din 5• ex: 0->11000, 1->00011, 2->00101

– exces 3: BCD+3• ex: 0->0011, 1->0100, ... 8-> 1011, 9->1100 (simetrie)

Obiectivele unui sistem de codificare

reprezentarea informatiilor intr-o forma cat mai simpla

facilitarea implementarii operatiilor aritmetice detectia si corectia erorilor (paritate, CRC,

suma de control) utilizarea unui spatiu minim de memorare

(compactarea informatiei) protectia impotriva accesului neautorizat

(securitate)

Coduri detectoare si corectoare de erori – Bit de paritate :

• informatie+1 bit de paritate• detecteaza numai erorile care au un numar

impar de biti modificati (1, 3, ...)• eficienta slaba

– Matrice cu paritate orizontala si verticala:• detectie mai buna a erorilor 0011 0• verificare pe blocuri de date 1000 1

1100 0

1110 1

1001 0

Detectia si corectia erorilor Detectia erorilor

– pe baza de redondanta - coduri nefolosite– distanta Hamming (d)- numarul minim de biti prin care

difera doua coduri valide• d(BCD+p)=2 ex: 0 00000

1 00011• numarul de biti eronati detectatii de un cod (e):

– e d-1 ; ex: BCD+p - detecteaza eroare de 1 bit

Coduri corectoare de erori:– coduri Hamming– distante mai mari– numarul de biti corectati de un cod (c)

Coduri corectoare de erori Codul Hamming pe 7 biti

– 4 biti de date + 3 biti de paritate

– p1<- c3,c5,c7– p2<-c3, c6, c7– p4<-c5, c6,c7

p1 p2 c3 p4 c5 c6 c7

0 0 0 1 1 1 0 data transmisa

0 0 1 1 1 1 0 data receptionata

0 1 1 0 p1 gresita

0 1 1 0 p2 gresita

1 1 1 0 p4 corecta

p1 p2 c3 p4 c5 c6 c7

011=3=>c3 eronat

Detectia erorilor pe blocuri de date

Suma de control – se insumeaza pe 16 biti continutul unui bloc de

date si la sfarsit se scrie complementul

– la verificare suma trebuie sa fie 0 (ex: bios) Cod ciclic redondant (CRC)

– polinoame de divizare: • se divizeaza cu un polinom si se scade restul

• la verificare restul trebuie sa fie 0

• eficienta foarte mare in detectarea erorilor

• usor de implementat cu componente digitale

– exemplu: CRC-16 = x16+x15+x2+1

Coduri pentru compresia datelor RLE - Run Length Encoding

– pentru codificarea informatiilor video– cursa: repetarea aceleiasi valori de pixel

• codificat prin perechea: (numar, valoare)

– secventa: secventa de biti de valori diferite• codificare prin: (numar, valori_de_pixeli)

– numar_cursa=1-n– numar_secventa=m-1

Alte metode de compresie:– Lempel-Ziv-Welsh (LZW)– Codificarea Huffman– JPEG, MPEG, MP3