arhitectura calculatoarelor
DESCRIPTION
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 - PowerPoint PPT PresentationTRANSCRIPT
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