Elemente de aritmetica binara

1. Scopul lucrarii

Se vor readuce aminte principalele formate de reprezentare a numerelor in baza 2 (unsigned integer, complement fata de 2 si virgula mobila) si se vor prezenta algoritmii si schemele corespunzatoare circuitelor aritmetice de insumare.

2. Formate de reprezentare a numerelor

Unsigned integer

Cu ajutorul acestui format se reprezinta pe N biti numerele naturale din intervalul . Regula de reprezentare este:

iar cuvantul in baza 2 este . In conventia utilizata, bitul b₀ joaca rol de msb (cel mai semnificativ), iar b_N-1 este msb (bitul cel mai putin semnificativ).

Este cel mai simplu format de reprezentare si din acest motiv, principalele circuite aritmetice utilizate in aceasta lucrare pleaca de la acest format si se modifica pentru a se adapta la celelalte formate.

Regula de reprezentare a unui numar natural presupune impartirea succesiva a numarului si apoi a caturilor obtinute la 2, pana catul ramas este 0. Resturile impartirilor la 2 reprezinta intocmai cuvantul cautat in ordine inversa.

Reprezentarea in complement fata de 2

Este cel mai folosit format de stocare a numerelor in virgula fixa. Spre diferenta de cazul anterior, permite stocarea atat a numerelor pozitive, cat si a celor negative. In reprezentarea pe N biti, primul bit, notat de aceasta data cu b₀ joaca rol de bit de semn. Un numar negativ are acest bit egal cu 1, iar unul pozitiv are acest bit 0.

Numerele se pot reprezenta in complement fata de 2 atat in format intreg, in domeniul , cat si in format fractionar, in domeniul cu pasul . In prelucrarea numerica a semnalelor, deseori se prefera lucrul in format fractionar si din acest motiv ne vom concentra asupra acestui caz.

In cazul unui numar fractionar, avem formula de conversie:

Observatii

Bitul a⁽⁰⁾ joaca intr-adevar rol de bit de semn. Daca a⁽⁰⁾=1, atunci

In acelasi timp, daca a⁽⁰⁾=0 atunci

Cel mai mic numar reprezentabil este

pentru cuvantul

Cel mai mare numar reprezentabil este

pentru cuvantul .

Cuanta de reprezentare este sau .

Numarul (semnul semnifica negarea logica a unui bit) mai poate fi scris ca:

Sau .

Cum reprezentarea in complement fata de 2 a numarului este aceeasi cu a numarului , rezulta ca regula de reprezentare a opusului unui numar impune doua etape: negarea logica a celor N biti si adunarea cu 2^-(N-1), deci cu cuvantul .

Reprezentarea unui numar fractionar se poate face exact folosind dezvoltarea in serie de puteri:

Se poate lesne observa ca reprezentarea in complement fata de 2 reprezinta o trunchiere a seriei la doar N termeni. Prin urmare se deduce ca in reprezentarile in virgula fixa, apare o eroare de cuantizare, cauzata de trunchierea mentionata, de modul cu atat mai mic cu cat numarul de biti creste (din serie se iau mai multi termeni).

Un numar fractionar A se poate reprezenta in complement fata de 2 folosind urmatorul algoritm.

o       Se ia si se trunchiaza sau se rotunjeste catre cel mai apropiat intreg:

o       Intregul pozitiv calculat mai sus se reprezinta in unsigned pe N biti, dupa regula de la paragraful 2.1, rezultand cuvantul

o       Daca numarul initial A este negativ, trebuie calculat opusul sau dupa regula enuntata

Trunchierea converteste un numar catre cel mai apropiat numar reprezentabil pe N biti spre 0. Rotunjirea converteste un numar catre cel mai apropiat numar reprezentabil. Din acest motiv zgomotul de cuantizare introdus prin cele doua metode, chiar daca are aceeasi varianta, are medii statistice diferite: in cazul trunchierii, aceasta este , iar in cazul rotunjirii, ea este nula.

Eroarea de cuantizare se poate pune in evidenta si prin faptul ca doua numere diferite se pot reprezenta identic pe un anumit numar de biti. De exemplu, in cazul unei reprezentari prin rotunjire pe 4 biti a numerelor 0.243 si 0.3, aceasta se face identic: [0 0 1 0]. In cazul trunchierii, cele doua numere se reprezinta insa diferit: [0 0 0 1], respectiv [0 0 1 0].

Reprezentarea in complement fata de 2 se poate extinde, asa cum s-a precizat deja si pentru numere intregi cu semn. Regula de reprezentare devine:

adica reprezentarea de la numere fractionare inmultita cu 2^N-1.

Regula de reprezentare a numarului intreg A din domeniul este urmatoarea:

se ia modulul si se reprezinta pe N biti in unsigned

daca numarul initial este negativ, se aplica regula de calculare a opusului, prin negare si adunare cu 1.

Reprezentarea in format Semn-Modul (Sign Magnitude)

Expresia conversiei unei fractii A in acest format este:

Bitul a⁽⁰⁾ este bit de semn, iar reprezinta modulul fractiei. Asa cum se poate remarca si din formula, regula de reprezentare a unui numar A, din domeniul este:

se reprezinta numarul in complement fata de 2

daca numarul initial este negativ, se neaga bitul de semn a⁽⁰⁾.

Observatii

Reprezentarea este identica celei in complement fata de 2 pentru numere pozitive.

Opusul unui numar se gaseste prin simpla negare a bitului de semn.

Exista doua reprezentari ale lui 0, si , ca si cum 0 ar fi un numar cu semn.

Din motivul de mai sus, -1 nu se poate reprezenta in acest format. Cel mai mic numar este , corespunzator lui , iar cel mai mare este evident opusul acestuia, , adica .

Reprezentarea in virgula mobila

In locul reprezentarii liniare a numerelor in functie de o serie de puteri, pentru acoperirea unei game mai largi de numere, se poate apela la formatul in virgula mobila, sub forma

unde M este mantisa (presupusa pozitiva), iar E este exponentul.

Semnul poate fi tratat separat sau integrat in mantisa.

Aceasta reprezentare suporta mai multe formate. Formatul standard de reprezentare, standardizat IEEE 754 este precizeaza ca un cuvant de cod in precizie simpla contine:

un bit de semn

8 biti pentru exponent

23 de biti pentru fractie

Exponentul ia valori intre (valoarea -128 este rezervata).

Mantisa este de forma , unde f reprezinta partea fractionara a mantisei, care este efectiv stocata in cuvant.

Semnul este 0 sau 1, dupa cum numarul este pozitiv, respectiv negativ.

Observatii

Cel mai mic numar reprezentabil in modul este , fata de ca in cazul unei reprezentari fractionare in virgula fixa pe acelasi numar de biti (32).

Cel mai mare numar reprezentabil in modul este , fata de aproximativ 1, in cazul unei reprezentari fractionare in virgula fixa pe acelasi numar de biti (32).

Este de notat principiul de reprezentare in virgula mobila, ce poate fi adaptat oricarui alt caz, nu neaparat ca in standard. Un exemplu ar fi reprezentarea de mai jos

adaptata reprezentarii numerelor fractionare:

In acest caz, exponentul se reprezinta in unsigned, pe N_e biti, iar mantisa ca o fractie pozitiva in format fractionar (de exemplu complement fata de 2). Apare restrictia ca mantisa sa apartina intervalului . Din acest motiv, primul bit al mantisei este mereu 1 (fiind mai mare sau egal ca 0.5) si poate fi exclus din reprezentare. Rezolutia de reprezentare a mantisei este atunci .

Daca si , de exemplu, cuvantul de cod este reprezentat pe 8 biti, iar cuvantul 11001010 ar trebui interpretat in felul urmator:

Bitul de semn este 1, deci numarul este negativ.

cuvantul mantisei este 1001, deci

cuvantul exponentului este , deci E=2.

Numarul este atunci 0.1328125.

Observatii

cel mai mic numar reprezentabil in modul este

cel mai mare numar reprezentabil este

3. Sumatoare numerice

Sumatoare pentru intregi fara semn

Sumarea se face exact ca in baza 10. Prin urmare sumatorul este exact cel descris in Lucrarea 2.

Sumatoare pentru complement fata de 2

Ca si in cazul intregilor fara semn, se poate aplica algoritmul clasic de sumare, deja prezentat.

De remarcat este insa ca in acest caz, ca si in cel precedent, pot aparea erori in rezultatele adunarii daca apare fenomenul de depasire. Pe scurt la insumarea C=A+B, apare depasire daca .

Depasirea poate aparea numai la insumarea a doi operanzi de acelasi semn si se poate constata aparitia depasirii in cazul in care rezultatul este de semn diferit fata de al operanzilor.

Un prim exemplu propune adunarea numerelor pe 4 biti: 0.5 si 0.75.

Se constata ca rezultatul adunarii este negativ, desi operanzii sunt pozitivi.

Vom lua aceleasi numere cu semn schimbat:

cu schimbarea semnului rezultatului.

Exista urmatoarea regula de depasire. Daca x este rezultatul ideal al adunarii, atunci rezultatul furnizat de adunare este:

Fig. 3. . Efectul cuantizarii asupra rezultatului adunarii

Deoarece in multe aplicatii, pot aparea depasiri intamplatoare, rare si care nu depasesc cu mult valorile limita, se mai adopta regula de saturare, cu legea:

Fig. 3. . Efectul saturarii asupra rezultatului insumarii

Uneori, in aplicatii, adoptarea acestei reguli se justifica. Chiar daca se iau masuri impotriva depasirii unei anumite game dinamice la intrare, pot aparea fenomene (zgomot de tip impuls de exemplu) ce genereaza depasirea. Este util ca acestea sa fie saturate, in locul adoptarii regulii anterioare.

De exemplu, daca se doreste insumarea pe 6 biti a numerelor 0.8125 [011010] si 0.3125 [001010], rezultatele adunarii ideale, fara saturare si cu saturare sunt:

ideal: 0.8125+0.3125=1.125

fara saturare: 0.8125+0.3125-2=-0.875

cu saturare: 0.96875

Prin urmare, aritmetica cu saturare este recomandata in cazul in care apar depasiri de ordin mic, ce se pot transforma in erori relative mai mici decat in cazul in care nu se foloseste (caz in care de altfel, rezultatului i se schimba semnul!).

Avantajul major insa al aritmeticii fara saturare apare la adunarea mai multor operanzi. Sa presupunem ca avem de insumat trei operanzi: 0.875, 0.5 si -0.75, pe 4 biti. Chiar daca rezultatul final este de modul subunitar, 0.625, dupa efectuarea primei adunari, apare depasire: 0.875+0.5=1.375. daca lucram cu saturare, vom avea urmatoarea succesiune de operatii:

Fig. 3. . Adunare cu saturare

Din cauza aparitiei saturarii la efectuarea primei operatii, rezultatul final nu este cel corect.

Sa luam acum exemplul adunarii fara saturare.

Fig. 3. . Adunare fara saturare

Se observa un aspect interesant. Chiar daca rezultatul primei adunari este incorect, deoarece a aparut depasirea, rezultatul final este totusi cel corect. Putem trage urmatoarea concluzie: daca suma mai multor termeni este de modul subunitar, dupa adunarile succesive fara saturare, se va obtine la final un rezultat corect, chiar daca rezultatele intermediare sunt incorecte. Aceasta afirmatie nu este valabila in cazul aritmeticii cu saturare.

Sumatoare in format SM

Marele dezavantaj al acestei reprezentari il constituie tocmai faptul ca operatiile aritmetice sunt mai complexe decat in cazul reprezentarii in complement fata de 2. Concluzia deriva din faptul ca reprezentarea nu este o combinatie liniara a tuturor bitilor din cauza aparitiei factorului in fata seriei de puteri.

Observatia de mai sus se poate verifica pe un exemplu oarecare.

Cea mai intuitiva schema de sumator este cea care in prealabil face conversia operanzilor in complement fata de 2, realizeaza adunarea simplu, in acest format, dupa care reconverteste rezultatul in format SM.

Fig. 3. . Sumator in format SM

Algoritmul de mai sus are ascunse in interior 4 sumatoare, din moment ce blocurile de conversie au nevoie de calculul modulului, prin urmare de circuite de calcul a opusului numerelor, in care apar la randul lor adunari cu (00.1).

Sumatoare in virgula mobila

Vom lua formatul de virgula mobila pentru numere fractionare, propus la 2.4. Fiecare numar este exprimat ca

unde , iar mantisa este exprimata in reprezentare Sign-Magnitude (adica bitul de semn este separat propriu-zis de modul).

Ne propunem calcularea sumei .

Conditia primara pentru a calcula suma este de a aduce cei doi termeni la acelasi exponent. Sa presupunem ca . Atunci

Deoarece , numarul si poate fi reprezentat corect in format SM.

Prin urmare, sumatorul furnizeaza rezultatul dupa urmatoarele etape:

Compara E₁ si E₂ si daca , inverseaza operanzii.

Deplaseaza la dreapta operandul cu biti.

Efectueaza adunarea in SM a operanzilor si . Deplasarea suplimentara la dreapta cu un bit ne asigura de evitarea aparitiei vreunei depasiri, pentru ca ambii operanzi vor fi de modul mai mic decat 0.5.

Numarul obtinut trebuie readus in formatul de virgula mobila. De aceea trebuie sa ne asiguram ca indeplineste conditiile impuse mantisei si anume .

Se deplaseaza M' la stanga cu B biti pana cand .

, iar exponentul este

4. Desfasurarea lucrarii

In ModelSIM, asa cum s-a mentionat deja, exista operatorul aritmetic '+'. De aceea, de cate ori va fi nevoie de o astfel de operatie, nu se va instantia sumatorul din Lucrarea 2, chiar daca furnizeaza acelasi rezultat.

Circuite de calcul al modulului

Se vor proiecta circuite care, primind un operand pe N biti, ii calculeaza modulul in fiecare din cele trei formate pentru numere cu semn: SM, complement fata de 2, virgula mobila. Deoarece modulul este un numar cu semn stiut, iesirea trebuie sa fie pe N-1 biti.

Care este cel mai complex circuit din cele trei?

Circuite de conversie

Se va proiecta un circuit combinational care converteste un numar exprimat in format SM in complement fata de 2, pe acelasi numar de biti.

Se va proiecta un circuit combinational care converteste un numar exprimat in complement fata de 2 in format SM, pe acelasi numar de biti.

Imaginati un algoritm de conversie a unui numar din SM in virgula mobila si invers.

Proiectati un circuit secvential care implementeaza algoritmul de mai sus. Numerele de biti ale operanzilor de intrare, respectiv de iesire sunt parametrizabile.

Sumatoare

Proiectati un sumator in complement fata de 2, care functioneaza cu saturare. Sumatorul va functiona pe ceas si va furniza iesirea in doua tacte de ceas.

Proiectati un sumator in SM, care furnizeaza iesirea in trei tacte de ceas.

Proiectati un sumator secvential in virgula mobila. In cat timp va fi furnizat la iesire rezultatul?

Scazatoare

Sa se proiecteze trei circuite care efectueaza scaderea a doi operanzi A si B, reprezentati pe acelasi numar de biti, N, in fiecare din cele trei formate pentru numere cu semn, prezentate in rezumatul teoretic.