CCI, IA, KHCI

Lucrarea -Reprezentari si conversii ale informatiei in calculator

Notiuni fundamentale

Sisteme de numeratie

Un numar se reprezinta ca o secventa de cifre, de exemplu: 1234 1011,01 XXV

In general numerele reale se reprezinta intr-un format de tipul:

cn-1cn-2.ck.c c ,c c .c-m unde ck reprezinta cifra din pozitia k.

Fiecare numar se caracterizeaza prin:

• valoare
• reprezentare

In timp ce valoarea unui numar este unica, exista o infinitate de reprezentari posibile ale numarului. In practica prezinta interesnumai acele reprezentari care respecta un set bine precizat de reguli. Aceste reguli trebuie sa permita determinarea univoca a valorii numarului atunci cand se cunoaste o reprezentare a sa.

Clasificari ale sistemelor de numeratie

In functie de legatura intre valoare si pozitia cifrei in reprezentarea unui numar, SN se impart in doua clase:

• SN simbolice (nepozitionale);
• SN pozitionale.

Exemplu: Sistemul de numeratie Roman. In reprezentarea numarului XXX cifra X are valoarea 10 indiferent de pozitia ocupata.

Un SNP se caracterizeaza prin:

1) Un numar intreg r numit radacina sau baza sistemului de numeratie; acest numar reprezinta numarul de cifre distincte permise pentru reprezentarea numarului in fiecare pozitie a reprezentarii numarului;

2) Un alfabet ordonat format din r cifre distincte;

3) O pondere asociata fiecarei pozitii din reprezentarea numarului.

Observatie! Reprezentari identice pot desemna numere (valori) diferite in functie de setul de reguli utilizate pentru reprezentare.

Se numeste sistem de numeratie simbolic un sistem de numeratie in care valoarea unei cifre nu depinde neaparat de pozitia ei in cadrul reprezentarii.

Se numeste sistem de numeratie pozitional (SNP) acel sistem de numeratie in care valoarea unei cifre depinde de pozitia ei in secventa de reprezentare

Exemplu: Sistemul de numeratie zecimal are baza r=10, alfabetul si in reprezentarea numerelor reale fiecare cifra are ponderea 10k unde k este pozitia cifrei in raport cu virgula (k>=0 pentru partea intreaga si k<0 pentru parte fractionara).

Exemplu: Sistemul de numeratie zecimal unde cifrele 0.9 pot fi utilizate in orice pozitie.

Exemplu: masurarea timpului (12 luni, 31 zile, 24 ore, 60 minute, 60 secunde).

Din punctul de vedere al ponderilor, SNP pot fi impartite in doua clase:

• SNP cu ponderi naturale
• SNP cu ponderi artificiale

Un SNP se numeste omogen daca numarul cifrelor admise pentru fiecare pozitie a reprezentarii este acelasi.

Un SNP se numeste mixt daca numarul de cifre admise pentru pozitii diferite este diferit.

Un SNP are ponderi naturale daca:

1) Pentru partea intreaga a reprezentarii ponderea pozitiei din extrema dreapta este 1 iar pentru toate celelalte pozitii ponderea este data de produsul numarului de cifre admise de fiecare pozitie la dreapta pana la virgula.

2) Pentru partea fractionara, ponderea fiecarei pozitii reprezinta inversul produsului numarului de cifre admise pentru acea pozitie si toate pozitiile spre stanga pana la virgula.

Observatie! Pe baza definitiei de mai sus,in cazul SNP omogene cu baza r, pozitia k din reprezentarea (1) a numarului are ponderea rk.

Exemplu: Pentru numarul 1234,56 reprezentat in sistemul de numeratie zecimal, cifrele vor avea urmatoarele ponderi:

Daca aceeasi reprezentare se considera in sistemul octal (r=8), ponderile cifrelor vor fi:

Se numeste SNP cu ponderi artificiale orice SNP care incalca una din regulile definitiei anterioare.

Exemplu: Se considera o reprezentare a numerelor intregi in care pozitia cea mai semnificativa are ponderea -rk iar celelalte pozitii au ponderea ri

Din punctul de vedere al numarului de simboluri utilizate pentru reprezentarea cifrelor se disting:

• SN cu reprezentare directa;
• SN cu reprezentare codificata.

Se spune ca un SN este cu reprezentare directa daca fiecare cifra este reprezentata printr-un simbol distinct.

Se spune ca un SN este cu reprezentare codificata daca numarul de simboluri utilizate pentru reprezentarea cifrelor este mai mic decat numarul de cifre admise. In acest caz fiecare cifra se reprezinta printr-o combinatie (cod) a simbolurilor admise.

Exemplu: Fiecare din cele 10 cifre ale SN zecimal are o reprezentare distincta.

Exemplu: Reprezentarea cifrelor zecimale in codul Morse, unde fiecare cifra se reprezinta ca o combinatie de puncte si linii.

Reprezentarea numerelor in SNP omogene cu ponderi naturale

a) Reprezentarea numerelor intregi

Exemplu: Numarul zecimal 75 poate fi reprezentat in baza 8 sub forma 113 deoarece

Observatie! In cadrul cursului vor fi abordate numai sisteme de numeratie omogene cu ponderi naturale datorita largii lor utilizari in rezolvarea unor probleme fundamentale ale tehnicii de calcul.

Fie N un numar intreg si r baza unui SNP omogen cu ponderi naturale. Reprezentarea numarului N in baza r (se noteaza N(r)) este data de secventa N(r) =an-1an-2a a unde ai este o cifra permisa de baza , ai I pentru i I [0;(n-2)] si an-1 I [1,,(r-1)] iar valoarea numarului N este definita prin relatia polinomiala:

Observatii!

• O1 Relatia (1.2) se mai numeste si dezvoltarea dupa puterile lui r a numarului N.
• O2 Acelasi numar se reprezinta in moduri diferite in diverse baze. Cu cat baza are valoare mai mare, lungimea reprezentarii scade.

Exemplu: Numarul zecimal 75 poate fi reprezentat in baza 8 sub forma 113 deoarece 75=7*10+5=1*64+1*8+3.

Proprietate: reprezentarea unui numar intreg in baza r este unica.

• Cifra din extrema dreapta a reprezentarii unui numar se numeste cifra cea mai putin semnificativa a numarului.
• Cifra din extrema stanga a reprezentarii unui numar se numeste cifra cea mai semnificativa a numarului.

b) Reprezentarea numerelor reale

Orice numar real poate fi descompus intr-o parte reala si o parte fractionara.

R(r)=an-1.a a ,a a a-m (1.3)

unde:

Valoarea numarului R este data de valoarea polinomului

Proprietati:

• P1 Inmultirea cu r a unui numar real reprezintat in baza r este echivalenta cu deplasarea cu o pozitie spre stanga a cifrelor reprezentarii; prin dreapta se introduce 0.
• P2 Impartirea cu r a unui numar real reprezentat in baza r este echivalenta cu deplasarea cu o pozitie spre dreapta a cifrelor reprezentarii; prin stanga se introduce 0.

Cele doua proprietati au o importanta deosebita in realizarea unor operatii aritmetice in calculator. In principiu, reprezentarea numerelor reale conform celor discutate anterior poate include un numar infinit de ranguri. In tehnica de calcul si in general in activitatea umana, din considerente fizice nu se pot utiliza decat un numar finit de ranguri.

In timp ce partea intreaga are o reprezentare unica in orice baza r, partea fractionara poate avea o infinitate de reprezentari posibile in aceeasi baza, in functie de numarul de ranguri luate in considerare (lungimea reprezentarii). Din aceasta cauza se pune problema determinarii unor criterii de apreciere a lungimii minime de reprezentare pentru diverse situatii concrete.

Metode generale de conversie; Prezentare generala

Se numeste conversie din baza p (baza initiala) in baza q (baza finala) a unui numar dat R, trecerea de la reprezentarea acelui numar in baza p la reprezentarea numarului in baza q.

Pentru a realiza aceasta operatie exista 3 metode generale de conversie si anume:

1. metoda conversiei cu calcule in baza initiala;

2. metoda conversiei cu calcule in baza finala;

3. metoda conversiei cu calcule in baza intermediara.

Denumirea de 'metode generale de conversie' se datoreaza faptului ca ele pot fi aplicate pentru conversia din orice baza initiala in orice baza finala.

Pe langa aceste metode, pentru anumite sisteme de numeratie particulare, frecvent utilizate, au fost puse la punct metode de conversie specifice, usor de manipulat si care permit in general obtinerea mult mai rapida a rezultatului comparativ cu metodele generale de conversie.

Metoda conversiei cu calcule in baza initiala

Conversia numerelor intregi

Fie I un numar intreg reprezentat in baza p cu n cifre:

unde ai i=0,.,n-1 cifre in baza p.

Se cere reprezentarea acestui numar in baza q:

Exista urmatorul algoritm de conversie:

Datorita modului de desfasurare a calculelor, metoda se mai numeste si metoda impartirilor succesive.

Observatii!

O1 Metoda conduce intotdeauna la o reprezentare in baza q pe un numar finit de ranguri deoarece la fiecare pas I_1(p)<I(p) deci la un moment dat se va obtine I_1(p)<q_p si la pasul urmator catul va fi 0.

O2 Reprezentarea in baza q este unica.

O3 Cifrele din I(q) se obtin in ordine inversa, incepand cu cifra cea mai putin semnificativa.

O4 Metoda se recomanda pentru conversiile din baza 10 intr-o baza q oarecare, deoarece suntem obisnuiti cu operatia de impartire in baza 10.

Exemple:

Conversia numerelor fractionare

Fie F un numar fractionar reprezentat in baza p pe m ranguri

Se cere reprezentarea acestui numar in baza q

Exista urmatorul algoritm de conversie:

P1) i=-1

P2) Se inmulteste F(p) cu valoarea qp. Calculele se efectueaza in baza p. Se obtin un intreg I(p) si o parte fractionara F1(p).

P3) Se scrie I(p) ca o cifra in baza q notata I (q) si rezulta b-i=I (q).

P4) F(p)=F1(p)

i=i+1

P5) Daca F(p)=0 se trece la P6.

Daca a fost obtinut numarul de ranguri impus pentru reprezentarea numarului, se trece la pasul P6. Daca F(p) 0 si nu a fost atins numarul minim de ranguri pentru reprezentarea numarului, se reiau calculele de la pasul P2.

P6) STOP

Datorita modului de desfasurare a calculelor, metoda se mai numeste si metoda inmultirilor succesive.

Observatii!

O1 Metoda se recomanda in special la conversia din baza initiala 10 intr-o baza finala q oarecare, dar poate fi aplicata relativ simplu si pentru alte baze initiale p≠10.

O2 Chiar daca reprezentarea in baza p are un numar finit de ranguri, reprezentarea in baza q poate sa aiba un numar infinit de ranguri (reprezentare periodica simpla, periodica mixta sau aperiodica).

O3 Deoarece in calculator numerele nu pot fi reprezentate decat pe un numar finit de ranguri, in situatia in care rezulta o reprezentare pe un numar infinit de ranguri sau o reprezentare prea lunga, se pune problema trunchierii reprezentarii. In acest caz trebuie stabilita pe baza unui criteriu obiectiv lungimea minima admisibila pentru reprezentarea in baza q astfel incat eroarea de reprezentare obtinuta sa fie acceptabila.

O4 Datorita trunchierilor pot exista diverse reprezentari in baza q ale aceluiasi numar din baza p in functie de lungimea reprezentarii.

Exemple:

E1. Se considera numarul zecimal F =0,0625 si se cere reprezentarea sa in baza 8.

Conversia numerelor reale

Fie R(p) reprezentarea in baza p a numarului real R. Se cere reprezentarea in baza q a aceluiasi numar, adica R(q). Pentru realizarea conversiei, R(p) se descompune in partea intreaga I(p) si partea fractionara F(p). Se utilizeaza metoda impartirilor succesive pentru conversia lui I(p) si metoda inmultirilor succesive pentru conversia lui F(p) (eventual cu trunchiere).

Reunind cele doua rezultate se obtine R(q).

Metoda conversiei cu calcule in baza finala

Metoda se aplica unitar pentru partea intreaga si partea fractionara.

Dezvoltarea dupa puterile lui p a acestui numar are forma:

Se scrie fiecare cifra a reprezentarii ca numar in baza q adica a_{n- 1(q)} si p ca un numar in baza q adica p_q; cu aceste notatii relatia devine:

Efectuand toate calculele din relatia in baza q, se obtine in final chiar R(q).

Exemple:

Metoda conversiei cu calcule in baza intermediara

Fie R(p) reprezentarea in baza p a numarului real R si se cere reprezentarea R(q) a aceluiasi numar.

Conversia se poate realiza in doua etape:

1) Utilizand metoda conversiei cu calcule in baza finala se determina reprezentarea R(r) a numarului dat in baza intermediara r.

2) Utilizand metoda conversiei cu calcule in baza initiala, pornind de la R(r) se determina R(q).

Observatie! Metoda se recomanda in special pentru conversia reprezentarii dintr-o baza p oarecare in baza 10. Pentru numere intregi metoda poate fi aplicata relativ usor pentru orice baza finala q.

Observatii!

O1) Metoda se recomanda pentru doua baze p si q oarecare, iar ca baza intermediara baza r=10 pentru simplitatea calculelor.

O2) Exista situatii practice cand este util sa se utilizeze alte baze intermediare (de exemplu baza 2).

O3) Metoda poate ridica probleme atunci cand reprezentarea in baza intermediara este un numar cu partea fractionara pe un numar infinit de ranguri.

Sisteme de numeratie utilizate in tehnica de calcul

Prezentare generala

La ora actuala, pe langa sistemul zecimal, in tehnica de calcul se utilizeaza pe scara larga doua sisteme de numeratie:

- sistemul binar (baza 2)

- sistemul hexazecimal (baza 16).

Evident este utilizat si sistemul zecimal dar acesta nu este specific tehnicii de calcul, ci omului. Sistemul binar sta la baza tuturor operatiilor utilizate in calculatoare, sistemul hexazecimal fiind introdus pentru o mai usoara reprezentare a informatiei din calculator din punctul de vedere al omului. Alegerea acestui sistem (baza 16) s-a datorat legaturii deosebit de simple ce exista intre reprezentarea in baza 2 si reprezentarea in baza 16 ale unui numar dat.

Sistemul de numeratie binar; Caracteristici

Baza p=2.; Alfabetul: .

O cifra binara se numeste bit (plural biti). Denumirea vine de la cuvintele engleze binary digit care inseamna 'cifra binara'.

Bitul reprezinta unitatea informationala (unitatea de masura a informatiei).

La ora actuala, datorita volumului din ce in ce mai mare de date pastrate si prelucrate in calculator, se utilizeaza in special urmatorii multipli ai bitului:

Desi din punct de vedere matematic acest sistem de numeratie nu este un sistem de numeratie optim, el s-a impus datorita urmatoarelor proprietati:

exista foarte multe dispozitive si fenomene fizice caracterizate prin doua stari stabile ce pot fi puse incorespondenta cu cele doua cifre binare, cum ar fi:

• contact inchis/deschis al unui releu;
• dioda blocata/in conductie;
• nivel inalt/scazut de tensiune;
• sensul de magnetizare;
• sensul curentului printr-un circuit;
• tranzistor blocat/saturat;
• adevarat/fals;
• bec aprins/stins;
• etc.

aritmetica binara este asemanatoare aritmeticii in baza 10, usor de inteles si utilizat;

metodele de proiectare a dispozitivelor numerice binare se bazeaza pe un aparat matematic riguros, relativ simplu si usor de manipulat;

pretul de cost al dispozitivelor numerice binare este in continua scadere in timp ce performantele sunt in continua crestere.

Printre dezavantajele utilizarii sistemului de numeratie binar pot fi amintite:

lungimea foarte mare a reprezentarilor (de aproximativ 4 ori mai lungi decat in sistemul zecimal);

necesitatea unor conversii la toate operatiile de intrare/iesire pentru a trece de la reprezentarea tipic umana la reprezentarea in calculator si invers;

algoritmi sofisticati si consumatori de timp pentru realizarea unor operatii aritmetice tipice cum ar fi inmultirea, impartirea, extragerea radicalilor etc.

probleme legate de precizia rezultatelor datorita conversiilor si trunchierilor.

Metode de conversie specifice

Datorita necesitatii realizarii frecvente a conversiilor intre baza 10 si baza 2 sau invers, au fost puse la punct metode de conversie rapida bazate pe utilizarea tabelelor cu puterile lui 2.

Metoda descompunerii in suma a puterilor lui 2

P1) Utilizand tabela puterilor lui 2, se descompune numarul zecimal dat intr-o suma a puterilor lui 2.

P2) In reprezentarea binara, pentru fiecare putere prezenta se

introduce 1 iar pentru fiecare putere absenta se introduce 0.

Metoda scaderilor succesive

Este o varianta sistematica a metodei precedente.

Fie N un numar reprezentat in baza 10.

P1) In tabelul puterilor lui 2 se cauta puterea lui 2 cea mai mare care este inca mai mica decat numarul N.

P2) Se scade din N puterea lui 2 identificata la 1 si se retine aceasta putere in suma puterilor lui 2 in care vom descompune numarul.

P3) Se inlocuieste N cu diferenta obtinuta.

P4) Se micsoreaza cu o unitate puterea lui 2 si se calculeaza diferenta dintre N si noua putere.

P5) Daca diferenta obtinuta este 0 sau a fost atinsa precizia de reprezentare impusa, se retine in suma puterea lui 2 si se trece la pasul P6. Daca diferenta este pozitiva, se retine puterea lui 2 in suma puterilor lui 2 si se revine la pasul P3. Daca diferenta este negativa, se revine la pasul P4.

P6) In reprezentarea binara, pentru fiecare putere prezenta se introduce 1 iar pentru fiecare putere absenta se introduce 0.

P7) STOP

Sistemul de numeratie hexazecimal

Baza: p=16. Alfabetul:

Acest sistem de numeratie a inceput sa fie utilizat pe scara larga atunci cand s-a trecut in calculatoarele moderne la organizarea informatiei in grupe de 8 biti numite octeti deoarece permite o reprezentare mai compacta si comoda a informatiei decat sistemele binar si octal.

Legatura intre reprezentarea binara si reprezentarea hexazecimala a aceluiasi numar este data de urmatoarele doua teoreme:

T1 Fiind dat un numar in reprezentare hexazecimala N , echivalentul binar al numarului se obtine prin inlocuirea fiecarei cifre hexazecimale cu echivalentul binar pe 4 biti al cifrei si eliminand eventualele zerouri nesemnificative de la capete.

T2 Fiind dat un numar in reprezentare binara N , pentru a determina echivalentul octal al numarului se utilizeaza urmatoarea metoda:

1) Pornind de la virgula spre stanga si spre dreapta, se formeaza grupe de cate 4 biti (completand eventual cu 0 la capete).

2) Se scrie echivalentul zecimal al fiecarei tetrade.

3) Se scrie ca cifra hexazecimala fiecare din numerele zecimale calculate anterior. Numarul obtinut este chiar echivalentul hexazecimal al numarului binar dat.

Observatii:

O1) In cazul conversiei din baza 8 in baza 16 sau invers, se recomanda ca baza intermediara baza 8, nu baza 10.

O2) Sistemele de numeratie octal si hexazecimal au relevanta numai pentru om. In calculator se prelucreaza numai informatie reprezentata binar !

O3) Pentru conversiile din baza 16 in baza 8 sau baza 16, se pot utiliza metodele rapide prezentate la sistemul binar, folosind in locul tabelelor cu puterile lui 2 tabele cu puterile lui 8 respectiv 16.

Coduri binar-zecimale; Prezentare generala

Se numeste cod binar-zecimal un cod in care fiecare cifra zecimala este reprezentata ca o combinatie de cifre binare.

Pentru a avea o codificare corecta este necesar ca fiecarei cifre zecimale sa i se asigneze o combinatie binara unica in cadrul codului. Deci, pentru codificarea celor 10 cifre zecimale sunt necesare 10 combinatii binare distincte. Se va lua in considerare cazul in care toate combinatiile binare dintr-un anumit cod binar-zecimal au aceeasi lungime n (au acelasi numar de biti).

Avand in vedere ca folosind n biti pot fi generate 2ⁿ combinatii distincte, pentru a putea genera un cod binar-zecimal este necesar sa fie indeplinita conditia:

2ⁿ >10 si rezulta rezulta imediat: n>log 10

Valoarea minima este n=4, adica lungimea minima admisa pentru combinatiile unui cod binar-zecimal este 4 biti.

Este evident ca pot fi generate o infinitate de coduri binarzecimale. Chiar pentru n=4 pot fi generate foarte multe coduri binarzecimale distincte. In practica s-au impus doar cateva coduri binarzecimale cu anumite particularitati utile.

Exemple de coduri binar-zecimale

Codul binar-zecimal 8421

Este un cod binar-zecimal pe 4 biti, ponderat cu ponderi naturale. Denumirea codului este data de ponderile celor patru biti. Este cunoscut si sub numele de cod binar-zecimal natural.

O combinatie de cod se determina ca echivalentul binar pe 4 ranguri al cifrei zecimale corespunzatoare.

Daca se cunoaste o combinatie b b b b a codului, cifra corespunzatoare se determina cu relatia:

c=8b +4b +2b +b

Este probabil cel mai utilizat cod binar-zecimal la ora actuala.

Codul binar-zecimal Exces 3

Face parte dintr-o familie de coduri binar-zecimale numite Exces N. Este un cod binar-zecimal pe 4 biti neponderat, cu autocomplementare.

Combinatia de cod pentru o cifra zecimala c se determina ca o combinatie binara pe 4 ranguri a numarului c+3.

Daca se cunoaste o combinatie b b b b a codului, cifra corespunzatoare se determina cu relatia:

c=8b +4b +2b +b -3

Codul binar-zecimal GRAY

Este un cod binar-zecimal pe 4 biti, neponderat. Face parte dintr-o familie mai larga de coduri GRAY. proprietatea de baza a codurilor din aceasta familie este acea ca pentru doua cifre zecimale consecutive combinatiile de cod difera intr-o singura pozitie.

Pentru a determina combinatia de cod g g g g a cifrei zecimale c, se porneste de la combinatia de cod b b b b a codului binarzecimal 8421 pentru aceeasi cifra si se utilizeaza relatiile de calcul:

g =b3

g =b b

g =b b

g =b b

unde este operatorul suma modulo 2 definit prin urmatorul tabel