vladutiu - partea ii

22
2. Dispozitive de adunare si scadere 2.1 Sumatorul serial (Serial adder) Este un automat secvential a carui comportare este data de tabelul de stari. Avem 2 stari posibile din punct de vedere functional: - starea la care se aduna la un moment dat 2 biti si din starea anterioara nu a provenit transport(carry); - starea la care se aduna la un moment dat 2 biti si avem transport. Vom prezenta în continuare tabelul tranzitiilor: Inputs Outpu ts x i y i c i -1 z i c i 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1 La construirea sumatorului folosim bistabile de tip JK: Ecuatiile corespunzatoare unei celule sumator complet sunt: a b

Upload: claudiu-mv

Post on 26-Sep-2015

41 views

Category:

Documents


2 download

DESCRIPTION

Curs Vladutiu pentru Slavici

TRANSCRIPT

2

2. Dispozitive de adunare si scadere

2.1 Sumatorul serial (Serial adder)

Este un automat secvential a carui comportare este data de tabelul de stari. Avem 2 stari posibile din punct de vedere functional:

- starea la care se aduna la un moment dat 2 biti si din starea anterioara nu a provenit transport(carry);

- starea la care se aduna la un moment dat 2 biti si avem transport.

Vom prezenta n continuare tabelul tranzitiilor:

InputsOutputs

xiyici-1zici

00000

00110

01010

01101

10010

10101

11001

11111

La construirea sumatorului folosim bistabile de tip JK:

Ecuatiile corespunzatoare unei celule sumator complet sunt:

a

b

La versiunea data avem si o alternativa daca dupa tabel am fi ales un bistabil de tip D (delay element). La fiecare impuls de clock adun 2 full adder cell bit, rezulta ca daca vreau sa adun doua numere a n biti avem nevoie de n impulsuri de clock. Din nefericire un sumator serial executa suma ntr-un numar de impulsuri de clock egal cu n, daca operanzii au n biti si de accea, uzual, se apeleaza la sumatoare paralele.

2.2 Sumatoare paralele

1.2.1 Ripple-carry-adderRCA (Sumator cu transport propagat serial)

Un sumator cu transport propagat serial se obtine prin legarea n serie(cascada) a n celule sumator complet, daca avem operanzi pe n biti.

Caracteristica: Operatia propriu-zisa se executa ntr-un singur impuls de clock numai ca perioada acestui clock trebuie sa acopere intervalul de timp necesar propagarii transportului n maniera seriala prin ntreaga schema. Daca delay-ul(ntrzierea) printr-un circuit poarta este d, atunci perioada clock-ului trebuie sa fie T2nd.

Operatia de scadere se bazeaza pe adunarea complementului, si pentru generarea complementului vom apela la o adaugare la schema:

2.2.2 Scazatoare binare (Binary full subtracter)

Cnd operatia dominanta ca frecventa este scaderea se impune favorizata ipoteza unui scazator binar, adica sa avem o schema de tipul RCA obtinuta prin cascadarea a n celule scazatoare complete(full subtracter) a caror sinteza se realizeaza pornind de la urmatorul tabel de adevar:

InputsOutputs

x0y0c1z0V

00000

00111

01010

01100

10010

10100

11001

11110

unde este borrow in, iar este borrow out.

Ecuatiile fundamentale ale unui scazator complet sunt:

Se obtine un scazator complet din celule diferenta.

2.2.3. Carry-lookahead-adderCLA(Sumator cu transport anticipat)

La anterioarele solutii faptul ca transportul trebuia propagat n maniera seriala greva asupra performantei solutiei si s-a plecat de la ideea mbunatatirii timpului de propagare a transportului prin generarea n mod anticipat al transportului ntr-o maniera care sa tina cont de istorica valorica a operanzilor.

-variabila de generare a transportului;

-variabila de propagare a transportului;

n maniera recursiva avem:

Avantajul:

Avem doar 5 nivele logice n fata de 2n nivele logice ca la ripple-carry-adder pentru obtinerea sumei.Cele 5 nivele logice sunt:

1 - generarea lui p si g;

2,3 - generarea lui carry;

4,5 - SAU-EXCLUSIV pentru suma(se realizeaza pe 2 nivele logice).

Dezavantaje:

creste numarul intrarilor din SI-urile pentru carry si SAU-rile(pentru bitul i avem i+1 intrari);

creste fan-out-ul p-urilor, adica numarul de circuite pe care le poate alimenta. De exemplu fan-out-ul lui este egal cu n;

structura este neregulata si creste n complexitate si de aceea apar probleme la implementare.

Toate aceste dezavantaje au deschis o problema a constructiei CLA si problema acestei constructii se bazeaza pe urmatorul rationament:

Generaliznd relatiile de mai sus avem:

Aceste relatii sunt valabile daca si si

De exemplu pentru i=0, k=3 iar j=0,1,2 :

Schema CLA este prezentata n cele ce urmeaza:

n termeni de VLSI (very large scale integration) schema se implementeaza foarte usor castigndu-se spatiu de siliciu. Complexitatea circuitului n termeni de spatiu este , iar n termeni de timp este . Dependent de tehnologie este posibil ca solutia CLA sa o combinam cu solutia RCA pentru ca aceasta combinatie s-ar putea sa duca la o combinatie favorabila n termeni de timp/cost.

O solutie hibrida cu RCA este prezentata n urmatoarea figura:

Mai exista nca o solutie hibrida sugerata de figura urmatoare:

2.2.4 Carry-skip adder (CSkA)

Aceasta solutie este situata ca si cost si performanta de siliciu ntre RCA si CLA, si ea porneste de la ecuatia corespunzatoare lui CLA:

S-a ajuns la urmatoarea solutie tehnica:

Aceasta solutie tehnica se bazeaza pe faptul ca n ceea ce priveste tehnologia CMOS prin precharging este posibil sa se realizeze initial carry-urile cu 0(intersegment), prezentate mai sus. Carry-ul se poate genera simultan pentru toate segmentele, ignornd carry-ul care intra n portile SI.n situatia n care din intrari pentru un anumit segment nu s-a generat carry datorita carry-ului de intare n segment, este posibil totusi sa fie generat carry dar acesta nu va fi generat n maniera seriala conform solutiei RCA ci va omite(skip) propagarea seriala prin traversarea portii SI conditionata pe intrari de factorul logic , care n maniera CLA reprezinta produsul . Se spune ca corespunzator fiecarui segment care este RCA se genereaza termeni de tipul G. Termenii , se obtin mult mai simplu dect termenii , .Termenii de tip P sunt generati la segmentele externe. Sa admitem ca n primul segment RCA avem n general k ranguri si sa admitem ca pe 2 niveluri logice avem o ntrziere d. n aceste conditii n situatia cea mai defavorabila cnd avem o propagare de transport este valabila relatia de mai jos:

numarul de segmente interne

numarul de segmente externe

unde:

Tad- timpul maxim n care sumatorul aduna doua numere

k- numarul de ranguri corespunzatoare unui segment

n- numarul total de ranguri ale sumatorului

d- ntrzierea pe 2 niveluri logice

De exemplu, pentru schema noastra timpul de propagare maxim este:

Se poate obtine o solutie mai performanta daca se mparte sumatorul n segmente inegale( se apeleaza la un artificiu).

Aceasta solutie are timpul de propagare:

Concluzie:

Este posibil ca prin divizarea numarului de ranguri al sumatorului n segmente inegale RCA sa se obtina o solutie mai performanta dect cea corespunzatoare mpartirii n segmente RCA egale.

2.2.5 Carry-select adder (CSeA)

Este o alta modalitate de a efectua operatia de adunare paralelizat, evident pe baza unei investitii suplimentare care este sugerata de figura de mai jos.

n anumite tehnologii faptul ca semnalul de carry trebuie sa comande foarte multe intrari duce la ntrzieri si de aceea semnalul trebuie amplificat. Carry-ul real selecteaza suma parallel calculata(anterior calculata). Problema care se pune este cum sa se faca mpartirea intrarilor n segmente RCA astfel inct adunarea sa se faca n forma cea mai favorabila.

Vom face o comparatie ntre toate solutiile de sumatoare prezentate pna acum:

TypeSpaceTime

RCAO(n)O(n)

CLAO(n log2n)O(log2n)

CskAO(n)O()

CSeAO(n)O()

2.2.6 Manchester (Kilborn) adder

Este un sumator asemanator solutiei RCA care prezinta un lant serial, care poarta o denumire specifica Manchester Chain, si care este implementat nu cu porti logice lente ci cu comutatoare(switch-uri) rapide situate de-a lungul lantului dupa cum sugereaza figura urmatoare:

-swich generation(comutatorul de generare a transportului);

-0 carry(adica nu se genereaza carry);

-swich plus(comutatorul de propagare a transportului care vine de la rangul anterior).

Daca avem atunci se propaga oricum 1 logic, iar daca avem atunci se propaga oricum 0 logic.

Solutia a revenit odata cu epoca VLSI prin asa numitele pass transistors, de exemplu la AMD-29050(Lynch-Swartzlnder). n termeni de VLSI aceste celule se implementeaza favorabil, de mare viteza.

2.2.7 Carry-completion adder (CCA)

Pna la aceasta solutie am considerat ca am lucrat sincron. Ea urmareste ca n dependenta de configuratiile binare particulare ale operanzilor sa determin terminarea operatiei ntr-o maniera asincrona. n vederea implementari acestei idei se uziteaza suplimentar de doua linii de carry:

carry0, care se genereaza fie cnd ambii biti care se aduna de catre o celula sunt 0, fie cnd unul dintre ei este 1, dar din rangul anterior nu a venit transport(incoming carry);

carry1,care se genereaza cnd cei doi biti care se aduna de catre o celula sunt 1, dar din rangul anterior a venit transport.

Pentru a implementa aceasta idee, clasica structura de full adder se modifica prin adaosul revendicat de propagarea celor doua tipuri de carry: carry0 si carry1.Vom avea:

Carry-completion adder-ul are urmatoarea figura:

Este posibil sa apara semnalul parazit carry-completion signal(CC), care are urmatoarea forma:

Circuitul SI are un numar mare de intrari(53) si nu poate fi realizat pe un singur nivel, ceea ce reprezinta o scadere(pentru ca apar ntrzieri).

2.2.8 Parity checked adder.Duplication carry.Carry-dependent sum adder

Avnd n vedere proliferarea aplicatiilor la care se doreste maximizat atributul de fiabilitate sau de toleranta la defectare, tot mai frecvent se apeleaza la solutii orientate, croite, spre a permite atingerea dezideratelor de fiabilitate. Drept consecinta unul din controalele foarte des raspndite n domeniul calculatoarelor e controlul de paritate uzitat din cele mai vechi timpuri pentru verificarea informatiei, se doreste extins n ceea ce priveste acoperirea operatiilor aritmetice si logice.

n situatia n care la dispozitivul de nsumare se manifesta un defect se impune controlul corectei functionari a acestuia. Defectul mai probabil e sa fie singular, si din paleta de defecte posibile vom considera defectul de tip logic,adica blocarii la 0(stuck-at-0) sau 1(stuck-at-1) logic(o intrare sau o iesire ramne agatata pe o valoare si nu se mai misca de pe ea). Pentru controlul posibilelor defecte dintr-un calculator n general una din strategiile foarte raspndite consta n asa numitul control de paritate. Asta implica prin definitie ca fiecare cuvnt rezultat n calculator sa fie alcatuit dintr-un numar, fie par (even parity), fie impar(odd parity) de unitati binare.

Pentru aceasta codificare este necesar sacrificiul unui bit suplimentar ce trebuie adaugat cuvntului format din bitii utili. Cuvntul codificat ntr-un cod de paritate (para/impara) e emis pe magistrala, si la receptia cuvntului se verifica paritatea si daca corespunde atunci se considera ca emisia s-a efectuat corect, iar daca nu se verifica se spune ca s-a detectat o eroare(provocata de un defect). Acest control este utilizat la transmiterea informatiei la memorie. Punem n discutie problema nsumarii controlate prin paritate. Fara a pierde din generalitate admitem ca lucram n pariate para.

Avem doi operanzi:

carora le atasam 2 biti de paritate:

Suma lor este cu bitul de paritate .

Pot sa efectuez un control al operatiei de adunare care sa se bazeze pe schema prezentata anterior.

Checker-ul este o portiune de control care se ataseaza sumatorului propri-zis pentru a se controla operatiile care se fac cel mai des.

Daca defectul se manifesta pe lantul de carry atunci numarul de biti de carry mpreuna cu numarul de biti de suma eronati e ntotdeauna par(burst error), si prezenta unui astfel de tip de defect nu poate fi detectat prin controlul de paritate. Un astfel de exemplu cu situatia de stuck-at-1 este prezentat n continuare:

Un exemplu de burst error cu situatia de stuck-at-0 l prezentam n continuare:

n cazul cnd eroarea nu poate fi detectata avem doua solutii:

A) Carry-dependent sum adder

Ideea fundamentala a acestei solutii este ca atunci cnd este n eroare sa fie provocata n mod artificial si afectarea prin eroare a bitului imediat inferior al sumei, adica .

Provocnd un pachet de erori cu un numar impar de erori poate fi pus n evidenta controlul de paritate.

B) Duplicarea lantului de carry

Am conturat clasica structura de carry lookahead. Am prezentat solutia de verificare a sumatoarelor si am dat versiuni prin care la defecte singulare ca de exemplu blocare la o valoare apar doua noi tipuri de sumatoare: sumatoare cu duplicarea lantului de carry si sumatoare care depind de carry.

2.2.9 Conditional-sum adder (CSuA)

Principiul sumatoarelor cu suma conditionata consta n generarea sumei gradual pe pasi, n fiecare pas efectundu-se suma pe stagii formate din perechi att n situatia n care se genereaza carry ct si n cazul n care nu se genereaza carry. Stagiile initiale formate din perechi de biti se dubleaza ca dimensiune la fiecare pas, la pasul 2 avem un grup de 4 biti, la pasul 3 avem 8 biti, etc. La fiecare se dubleaza numarul bitilor de suma corecti. Schema consta dintr-o constructie piramidala formata din niveluri, unde n reprezinta numarul de biti ai cuvintelor nsumate. Detaliind principiul expus avem urmatoarea secventa de pasi:

Pas1: Pentru fiecare pereche de biti se genereaza bitii de suma respectiv carry n conditiile n care din rangul anterior soseste pe de o parte carry0 si carry1.

Pas2: Se genereza 2 stagii formate din perechi si se selecteaza n dependenta de valoarea lui carry interstagii, valorile corespunzatoare pentru suma si carry.

Pas3: Se repeta pasul 2 n mod iterativ dublndu-se la fiecare iteratie dimensiunea stagiilor, proces care se continua pna la epuizarea bitilor.

Stage i

7

6

5

4

3

2

1

0

A

1

0

0

1

0

1

0

1

B

0

0

1

0

1

1

0

1

SCCSCSCSCSCSCSCSCS

S=0C=00100010101000010

C=110011010100101

S=1C=001

001

1100101

0

C=101

110

010

1

1

S=2C=001

0

1

110

1

1

0

C=101

1

0

0

S=3C=001

0

0

0

0

1

1

0

C=1////////////////////////////////////////////////////////////////

Stagii:

Detaliul circuitului:

Apar niste forme degenerate ale carry-ului si sumei:

2.2.10 Carry-save adder(CSA)

Aceasta solutie se caracterizeaza prin faptul ca este alcatuit din mai multe niveluri de celule sumatoare complet disjuncte.

O astfel de structura de sumatoare permite nsumareala fiecare nivel nu a doi operanzi ci a trei operanzi. Ea apare ca foarte utila la accelerarea operatiei de nmultire, care se bazeaza pe adunari repetate. Mentionam ca pentru a obtine suma corecta bazata pe CSA la salvarea transportului este obligatoriu ca ultimul nivel de nsumare sa fie reprezentat de un sumator clasic(de exemplu un RCA).

Daca la fiecare etaj de carry-save mpanam un nivel de registre atunci operatia de nmultire se poate executa n flux, pe masura ce nivelul de carry-save aduna operanzii se poate efectua o suprapunere de operatii pe mai multe nivele. Are loc un overlap total prin care pot accelera operatia de nmultire simultan si care duce la cresterea capacitatii.

Este evident ca la nivelul unui singur bit produsul aritmetic coincide cu produsul logic.

2.2.11 Decimal ripple carry adder

La adunarea numerelor zecimale reprezentate n BCD pot fi utilizate toate solutiile de adunare prezentate anterior si pentru simplitate vom expune problema n contextul RCA, scop n care prezentam urmatoarea schema:

EMBED WPDraw30.Drawing

_1042043270.unknown

_1042044392.unknown

_1042044660.unknown

_1042044834.unknown

_1042045505.unknown

_1042045559.unknown

_1042045667.unknown

_1042047253.unknown

_1042045776.unknown

_1042045567.unknown

_1042045540.unknown

_1042044915.unknown

_1042045449.unknown

_1042044849.unknown

_1042044737.unknown

_1042044792.unknown

_1042044819.unknown

_1042044744.unknown

_1042044713.unknown

_1042044720.unknown

_1042044668.unknown

_1042044585.unknown

_1042044627.unknown

_1042044645.unknown

_1042044610.unknown

_1042044477.unknown

_1042044524.unknown

_1042044430.unknown

_1042043944.unknown

_1042044243.unknown

_1042044311.unknown

_1042044329.unknown

_1042044250.unknown

_1042044120.unknown

_1042044234.unknown

_1042044108.unknown

_1042043327.unknown

_1042043841.unknown

_1042043853.unknown

_1042043729.unknown

_1042043301.unknown

_1042043319.unknown

_1042043292.unknown

_1042042643.unknown

_1042042892.unknown

_1042043112.unknown

_1042043227.unknown

_1042043253.unknown

_1042043158.unknown

_1042043025.unknown

_1042043063.unknown

_1042043008.unknown

_1042042762.unknown

_1042042790.unknown

_1042042821.unknown

_1042042782.unknown

_1042042711.unknown

_1042042738.unknown

_1042042681.unknown

_1042042268.unknown

_1042042451.unknown

_1042042549.unknown

_1042042608.unknown

_1042042520.unknown

_1042042306.unknown

_1042042368.unknown

_1042042282.unknown

_1042041780.unknown

_1042042028.unknown

_1042042064.unknown

_1042041929.unknown

_1042041861.unknown

_1042041243.unknown

_1042041754.unknown

_1042041214.unknown