Arhitectura Sistemelor de Calcul (Adrian Atanasiu)

5/20/2018 Arhitectura Sistemelor de Calcul (Adrian Atanasiu)

1/200

Cuprins

Introducere 3

Capitolul 1: Arhitectura unui sistem de calcul 51.1.Organizarea de baza 51.2.Structura generala a masinilor de calcul 71.3.Micro-controllere 121.4.Ce nseamna Arhitectura unui calculator 13

Capitolul 2: Reprezentarea numerelor n calculator 152.1.Coduri de reprezentare a datelor 15

2.1.1.Coduri ponderate si neponderate 162.1.2.Reprezentarea zecimal codificat binar 172.1.3.Codul ASCII 18

2.2.Reprezentarea numerelor n sistemele de calcul 202.2.1.Reprezentarea numerelor ntregi 202.2.2.Operatii cu numere ntregi 212.2.3.Reprezentarea numerelor reale n virgula mobila 232.2.4.Operatii n virgula mobila 26

2.3.Exercitii 28

Capitolul 3: Algebre si functii booleene 293.1.Definirea algebrelor booleene 293.2.Proprietati ale algebrelor booleene 303.3.Alte operatii booleene 313.4.Functii booleene 333.5.Forme canonice 363.6.Inele booleene 383.7.Exercitii 39

Capitolul 4: Sisteme digitale 414.1.Circuite combinationale 41

4.1.1.Porti 414.1.2.Circuite 45

4.2.Extensii 46

204


2/200

4.3.Cicluri 504.4.Exercitii 52

Capitolul 5: Sisteme 0DS 55

5.1.Decodificatori 555.2.Codificatori 595.3.Demultiplexori 625.4.Multiplexori 645.5.Codificatori cu prioritate 695.6.Sumatori 75

5.6.1.Circuit digital pentru incrementare 795.6.2.Circuit digital pentru scadere 80

5.7.Circuite de comparare 83

5.8.Circuite de deplasare 865.9.Multiplicatori 88

5.10.Circuit logic programabil 905.11.Unitatea aritmetica si logica 945.12.Exercitii 96

Capitolul 6: Sisteme 1 DS (Memorii) 996.1.Caracteristicile sistemelor cu un ciclu 996.2.Cicluri stabile si instabile 1006.3.Zavoare elementare 102

6.3.1.Zavoare elementare cu ceas 1046.3.2.Zavorul de date 105

6.4.Structura master-slave 1066.4.1.Flip-flop cu ntarziere 107

6.5.Memoria RAM 1096.6.Registri 110

6.6.1.Registrul serial 1106.6.2.Registrul paralel si registrul serial - paralel 111

6.7.Exercitii 112

Capitolul 7: Sisteme 2 DS (Automate) 113

7.1.Definitii de baza 1137.2.Flip-Flopuri 117

7.2.1.Automatul T Flip-Flop 1177.2.2.Automatul JKFlip-Flop 118

7.3.Numaratori (counteri) 1207.4.Stive 124

205


3/200

7.5.Circuite aritmetice 1257.5.1.Sumator serial 1257.5.2.Circuit aritmetic serial-paralel 1267.5.3.Sumatoare prefix 1277.5.4.Multiplicator 1297.5.5.Circuit pentru produsul scalar (MAC) 133

7.6.Reprezentarea automatelor finite 1367.6.1.Automat pentru MAC 1377.6.2.Automat pentru recunoasterea unei secvente binare 141

7.7.Automate de control 1437.8.Transformarea automatelor n circuite combinationale 1477.9.Exercitii 148

Capitolul 8: Sisteme 3DS (Procesori) 151

8.1.Automate JK-registri 1518.2.Registri numaratori 1568.3.Automat aritmetic si logic 1588.4.Automate stiva 1608.5.Procesorul elementare 163

Capitolul 9: Sisteme 4 DS 1679.1.Tipuri de sisteme de ordin 4 1679.2.Stive organizate ca nDS 170

Capitolul 10: Structura unui computer la nivel de performanta 17110.1.Structuri standard 17210.2.Masurarea performantelor unui sistem 17410.3.Modele bazate pe cozi 175

Solutii si indicatii la problemele propuse 179

Bibliografie 203

Cuprins 204

206


4/200

Capitolul 1

Arhitectura unui sistem de calcul

Pentru nceput sa trecem n revista organizarea generala a unui sistem actual de calcul.

1.1 Organizarea de baza

Structura si compunerea logica a programelor care pot fi prelucrate de o masina de calculau fost elaborate anterior definirii structurii hard; ele se bazeaza pe teza lui Church1,enuntata n prima parte a anilor 30. Ulterior ea a fost completata de Turing.

Definitia 1.1 O metoda (procedura) M asociata rezolvarii unei probleme se numesteefectiva (sau mecanica) daca:

-Mse poate exprima printr-un numar finit de comenzi (instructiuni), fiecare comanda

putand fi definita pe baza unui alfabet finit de simboluri.- Mpoate produce rezultatul dorit ntr-un numar finit de pasi;- Mpoate fi descrisa n mod logic, fara a folosi mijloace externe.

In 1933 Barwise stabileste criteriile pe care trebuie sa le satisfaca un computer:

Nu va stoca raspunsurile la toate problemele posibile.

Va rezolva numai probleme pentru care i s-a dat o procedura de rezolvare.

Timpul necesar rezolvarii unei probleme este finit.

Turing, la randul lui, aduce n anii

40 o serie de precizari de ordin formal asupra posi-bilitatilor de calcul pe care le poate avea un computer.Masina definita de el (Masin a Turing) este modelul matematic al calculatoarelor de

mai tarziu.1Pe scurt enuntul acesteia este: O functief : N N este efectiv calculabila daca si numai daca este

recursiva.

5


5/200

6 CAPITOLUL 1. ARHITECTURA UNUI SISTEM DE CALCUL

. . . . . . Banda memorie

Cap citire/scriere

Procesor

O masina se compune dintr-un procesor (generator de instruct iuni), o banda de memoriecare se poate misca n ambele sensuri, si un cap de citire/scriere fix.

La fiecare tact, banda se misca cu o pozitie spre stanga sau dreapta, permitand exe-

cutarea unei comenzi.O astfel de comanda (sau instructiune) este reprezentata n procesor sub forma unuiquadruplu (Sh, Ti, Oj, Sk), cu urmatoarea semnificatie:

Daca starea procesorului este Sh si simbolul citit pe banda este Ti, atuncimasina efectueaza operatiaOj si trece procesorul n starea Sk.

sau - ca o varianta formalizata:

ifstare= Sh andinput= Ti then output:= Oj andstare:= Sk

Operatiile permise pe o masina Turing sunt:

1. Oj =Tj: simbolul Tj este scris pe banda n locul lui Ti;

2. Oj =R: banda se deplaseaza spre dreapta cu o locatie;

3. Oj =L: banda se deplaseaza spre stanga cu o locatie;

4. Oj =H: calculul se opreste.

Se demonstreaza ca orice calculator este echivalent din punct de vedere al posibilitatilorde calcul cu o masina Turing, iar aceasta conform Tezei lui Church poate aborda oriceproblema ce admite o rezolvare algoritmica.

Nu vom prezenta detalii ale acestor asertiuni, ele constituind subiectul altor domeniide cercetare, mult mai generale si fara multa legatura cu ceea ce vrem sa prezentam naceasta carte.


6/200

1.2. STRUCTURA GENERAL A A MASINILOR DE CALCUL 7

1.2 Structura generala a masinilor de calcul

Structura functionala a unei masini de calcul (sau Computer) n forma actuala a fost

definita n 1947 de von Neumann (1903 - 1957), modificarile ulterioare fiind nesemnifica-tive.

In principal ea contine trei componente de baza:

1. O unitate centrala de prelucrare (CP U) compusa din: o unitate de calcul (aritmeticasi logica) si o unitate de control.

Rolul ei principal este de a localiza si executa comenzi.

2. Una sau mai multe unitati de stocare a datelor (memorii); aici sunt pastrate datelesi programele calculatorului (programe care formeaza componenta de software sauprograme utilizator).

3. Periferice (intrare/iesire): unitati de transfer a informatiei spre si dinspre utilizator.

Memorie

Control

Periferice

intrare/iesire

Instructiuni

DateUnitate

aritmetica-logica

CPU

Aceste componente hard comunica ntre ele printr-un sistem de magistrale. Principalulsoft inclus este sistemul de operare, care asigura majoritatea functiilor de prelucrare alesistemului.

Sunt trei tipuri majore de instructiuni folosite de un calculator: de transfer de date,de prelucrare date si de control al programelor.Definirea setului de instructiuni si modul lor de prelucrare caracterizeaza n general

puterea unui calculator.Pe baza acestei structuri au fost construite calculatoarele din prima generat ie (anii

40 50).


7/200


Structura unui astfel de calculator (cum au fost ENIAC, EDVAC, IAS, UNIVAC) este

Memoriaprincipala

Programe si date

pentru executie

ControlInstructiuni

Date

CPU

Prelucrare

date

Programe,

date,

comenzi

Echipamenteintrare/iesire

(memorie secundara,

tastaturaimprimanta etc)

Impactul cel mai mare asupra dezvoltarii sistemelor de calcul l-au avut nsa calcula-toarele din generatia a treia, reprezentantul specific fiindIBM/360 (existent si n dotareaUniversitatii Bucuresti, ncepand cu anul 1967).

Schema generala a structurii unui astfel de calculator este prezentata pe pagina urmatoare.

Notatiile folosite (devenite standard odata cu generatia a treia de calculatoare):

DP U- Unitatea de prelucrare a datelor

CP U- Unitatea de control a programului

ALU- Unitatea aritmetica si logica

IO - Intrare / iesire

SR - Registru de stari

IR- Registru de instructiuni

AR- Registru de calcul pentru instructiuni aritmetice

P C- Registru de control al programului


8/200


. . .

DPUALU

Fixed - pointALU

Decimal

ALUFloating - point

4 registri de 64 biti

n virgula mobila16 registri generali

de 32 biti

IR AR SR PC

PSW (Program status word)

Decoder instructiuni

(poate fi micro-programat)

Semnale

control CPU

Periferic

IO

Periferic

IO

Interfata

IO

Procesor

IO

Procesor

IO

Unitatea de control a

memoriei principale

Memoria

principala

Caracteristici ale calculatoarelor din generatia 3 (IBM/360 IBM/390)

Introduc ideea de standardizare a constructiei, pentru a accepta limbaje de progra-mare universale.

Constituie baza arhitecturii calculatoarelor actuale.

Introduc unitatile de informatie: octet (byte), cuvant (word), cuvant dublu, registru.

Introduc ideea de micro - programare.


9/200


Sistemul actual uzual de calcul este computerul, tratat ca unitate independenta (P Csau statie de lucru) dedicata unui singur utilizator.

Structura lui este:

Magistrala sistem

Interfatamagistrala

Cache

CP U

M

HDDcontrol

Videocontrol

Tastaturacontrol

Reteacontrol

MemorieHDD

Monitor Tastatura Retea

Control interfata periferice

Magistrala I O (locala)

Microprocesor

Principalul element hard este un microprocesor realizat pe un chip, care contine oversiune a arhitecturii definite de von Neumann.

El asigura un CP U si este responsabil cu aducerea, decodificarea si executarea instruc-tiunilor.

Datele si instructiunile au un format standard de grupuri formate din 32 biti (cuvinte);acestea sunt unitatile de baza prelucrate de computer.

CP Ueste caracterizat printr-un set de circa 200 instructiuni care realizeaza transferulsi prelucrarea datelor precum si operatii de control al programelor (cu o structura ramasan general aceeasi n timp).

CP Upoate fi suplimentata cu alt chip (interior sau exterior) numit co-procesor, careimplementeaza functii specializate, cum ar fi prelucrarea de interfete grafice.

Rolul memoriei principaleM este de a stoca programe si date prelucrate deCP U.Ea este o memorie cu acces aleator (RAM - random access memory), formata din o

secventa liniara de componente (de obicei grupuri de 8 biti, numite bytessau octeti).Fiecare byte are asociat o adresa unica, care permiteC P U sa citeasca sau sa schimbe

(scrie) continutul (pe baza unor instructiuni de ncarcare sau memorare).


10/200


Memoria principala M este completata de o memorie secundara, mai mare dar mailenta (din punct de vedere al accesului), de obicei situata pe hardiscuri (HDD).

Harddiscurile formeaza o componenta a sistemului de intrare/iesire (IO).De asemenea, o memorie intermediara, numita cachepoate fi inserata ntre CP U si

M.

Deci un calculator contine mai multe tipuri de memorie, care pot fi ierarhizate nregistrele CP U: memoria cache, memoria principala si memoria secundara.

Aceasta structura complexa rezulta din faptul ca cele mai rapide componente de memo-rie sunt si cele mai scumpe; deci ierarhizarea asiguraC P Ucu un acces rapid la un numarmare de date, la un pret relativ scazut.

Scopul unui sistemIO este de a permite utilizatorului sa comunice cu calculatorul.

ComponenteleI Osunt atasate la calculatorul gazda prin intermediul unor porturiI O,a caror functie este de a controla transferul de date ntre componenta de intrare/iesire simemoria principala.

O astfel de componenta are asignata un set de adrese tip memorie care permit utilizareade instructiuni de intrare/iesire ce pot fi implementate aproape identic cu instructiunilede ncarcare respectiv stocare.

Dar deoarece operatiile de intrare/iesire sunt foarte lente, C P Uare nevoie de un timpmult mai lung pentru a accesa un cuvant aflat n sistemul I Odecat unul din memoria M.

Componentele traditionale de intrare/iesire sunt tastaturarespectivecranul de moni-tor, adaptate n special pentru procesarea informatiei de tip text.

Adaugarea unei componente punctuale, tip mousepermite introducerea ecranului nlista componentelor de intrare; el asigura comunicarea utilizator - computer via imaginigrafice. Interfete audio pentru generarea si recunoasterea sunetelor extind aria de lucrua calculatorului n sistemele multimedia.


11/200


1.3 Micro-controllere

Reducerea impresionanta a dimensiunilor si scaderea costurilor componentelor principale

ale unui calculator a permis construirea unor computere specializate pentru anumite pro-bleme, numite micro-controllere.

Ele au circuite de control specifice, sau sunt lipsite total de componenta logica (cumar fi de exemplu circuitul de control al unei masini de spalat automate).

Programele sunt stocate n memoria ROM(read only memory), care formeaza oparte a memoriei principale folosite de micro-controller.

Acesta este construit direct n obiectul controlat, ntr-o zona adesea invizibila si inac-cesibila utilizatorului.

Un micro-controller programat sa efectueze operatiile unei aplicatii poate nlocui cir-cuitele de control specifice acelei aplicatii, adesea cu o reducere de cost apreciabila.

Majoritatea calculatoarelor actual operabile sunt micro-controllere construite n di-verse aparate utilizate n cele mai variate medii.

Scaner

codprodus

Tastatura

Monitor

siimprimanta

Cititorcard

PortIO Port I O Port IO Port IO

Magistrala sistem

CP U(microprocesor)

Port IORAM ROM Port IO

Micro-controler

Calculatorcentral

Sprereteaua

telefonica

Schema de mai sus descrie una din primele aplicatii ale unui micro-controller: un punctde vanzare terminal care nlocuieste casa ntr-un supermarket.


12/200

1.4. CE INSEAMN A ARHITECTURA UNUI CALCULATOR 13

Micro-controllerul folosit are structura unui computer conventional.El este construit n jurul unei magistrale de sistem de care sunt atasate un micropro-

cesor (cu rol de CP U), cel putin un chip ROMpentru stocarea programului si cel putin

un chip RAMpentru lucru si stocarea datelor.Toate perifericele IOsunt conectate la sistem folosind porturi IOcu interfete standard.

Perifericele tipice unei astfel de aplicatii sunt: tastatura, o imprimanta pentru eli-berarea chitantelor, un monitor, un scanerpentru codurile de bare ale produselor si uncititor de card(credit sau debit).

Acest ultim periferic necesita o conectare la o retea telefonica pentru autorizarea car-dului.

Ultima componenta este o legatura la un calculator central, folosit pentru informatii

de pret, controlul stocului de produse etc.

1.4 Ce nseamna Arhitectura unui Calculator

Termenul de Arhitectura a calculatorului a fost folosit prima oara de firma IBM n 1964.Necesitatea lui a aparut deoarece n acea perioada tehnologia hardware permitea o

avansare rapida a proceselor de calcul, nlocuind frecvent o structura cu alta; tehnolo-gia software nu avea posibilitatea de a tine pasul, orice noua structura hard necesitandprograme noi.

Pentru a avea posibilitatea de a folosi la noile componente hard coduri program dejascrise, ceva trebuia mentinut stabil.

Corpul de cercetatori ai firmei IBM (leaderul necontestat n domeniul tehnicii de calculdin acea perioada) a decis stabilizarea setului de operatii elementare necesare programa-torului.

Definitia 1.2 Arhitectura unui calculator este imaginea logica si functionala a unui com-puter cu care lucreaza un programator.

Odata aceasta arhitectura stabilita, cele doua componente ale unui computer: hardware(multimea pieselor care formeaza calculatorul) si software (multimea programelor rulate

de calculator) se pot dezvolta independent una de alta.

O buna perioada de timp arhitectura putea fi doar mbunatatita, fiind adaugate noifacilitati, dar nefiind eliminata nici o functie.

Deci un program scris pentru o prima versiune a arhitecturii va functiona pe oriceversiune ulterioara.


13/200


Rezumand, architectura calculatorului este o interfata ntre hardul si softul unui com-puter si presupune:

o masina capabila sa realizeze o multime finita de operatii elementare,

o memorie, continand o descriere a modului cum pot fi folosite functiile elementarepentru a realiza procese de calcul,

un mecanism de control care permite utilizarea descrierii pentru a pune masina salucreze, n doua variante:

executnddescrierea

interpretnddescrierea.

unde, prin executie se ntelege o actiune de un pas asociata fiecarui elemental descrierii, iar prin interpretare se ntelege o secventa de actiuni asociate fiecaruielement al descrierii.

Evident, n ambele variante, actiunile vor depinde direct de modul de definire al des-crierii.

Lucrarea de fata abordeaza elementele fundamentale necesare construirii arhitecturiiunui calculator. Sunt schitate notiunile teoretice si structurile celor mai simple circuitecare formeaza unitatea logico-aritmetica, unitatea centrala de prelucrare precum si com-ponentele de memorie.

Celor care vor sa aprofundeze domeniul le recomand referintele bibliografice precum

si numeroase site-uri de Internet dedicate sistemelor de calcul.


14/200

Capitolul 2

Reprezentarea numerelor n

calculator

2.1 Coduri de reprezentare a datelor

Utilizarea codurilor a aparut pentru a asigura o comunicare ntre un utilizator si un sistemde calcul (specific unui calculator); principalul obstacol care este depasit printr-un cod dereprezentare a datelor consta n corelarea dintre modul n care sunt prelucrate datele decatre o persoana fizica (care gandeste n sistemul zecimal) si un computer (unde sistemulde baza este cel binar).

Definitia 2.1 Fiind date doua multimi finite si nevide A (alfabet sursa) si B (alfabetcod), o codificare este o aplicatie injectiva1 : A B +.

Observatia 2.1 S-a notat cuB+ multimea secventelor nevide de caractere formate cuelemente dinB. De exemplu, dacaB={0, 1} atunciB+ ={0, 1, 00, 01, 10, 11, 000, . . .}.

MultimeaC=(A) se numeste cod, iar elementele sale sunt cuvinte - cod.

Daca B are numai doua simboluri, codificarea se numeste binara, iar (A) este un codbinar.

Desi simple, codurile binare sunt de obicei lungi si deci greu de manipulat.Adesea este mai convenabil sa grupam simbolurile binare formand alfabete mai com-

plexe.Astfel, formand grupuri de cate patru simboluri binare, se obtine codul hexazecimal:

1O aplicatiefeste injectiva daca din egalitatea f(x) = f(y) rezulta x = y si nimic altceva.

15


15/200

16 CAPITOLUL 2. REPREZENTAREA NUMERELOR IN CALCULATOR

0 0000 4 0100 8 1000 C 11001 0001 5 0101 9 1001 D 11012 0010 6 0110 A 1010 E 1110

3 0011 7 0111 B 1011 F 1111

Reprezentarea n aceasta baza (care foloseste simbolurile auxiliare A , B , C, D, E, F pentru numerele 10, 11, 12, 13, 14 si respectiv 15) se indica adesea prin indicele 16 asezatla sfarsit. De exemplu,

(61)16= (0110 0001)2

Daca nu exista nici o confuzie, atunci indicii care semnaleaza baza se ignora.

Utilizarea acestui cod este aproape universal acceptata.Astfel, memoria calculatorului lucreaza cu biti grupati n bytes(sau octeti).

Un octet se reprezinta de obicei nu ca o secventa de 8 cifre binare, ci ca o pereche decifre hexazecimale.

Astfel, de exemplu (00101101)2 se scrie (2D)16, (01100000)2 se reprezinta prin (60)16etc.

2.1.1 Coduri ponderate si neponderate

Codurile binare sau hexazecimale nu sunt singurele modalitati de codificare a numerelorn calculator.

Practic, plecand de la reprezentarea binara, se poate construi o paleta larga de coduri.Ele sunt clasificate n

coduri ponderate;

coduri neponderate.

Codurile ponderateasociaza unei cifre zecimale un grup de patru cifre binare, fiecarei cifrebinare fiindu-i asociata o pondere corespunzatoare puterii lui 2 din cadrul codului.

Codul hexazecimal - binar prezentat mai sus este un exemplu de cod ponderat. Elmai este numit adesea si codul8421.

Codurile neponderateasociaza unei cifre zecimale un grup de patru cifre binare, faraa avea semnificatia unei ponderi.

Cele mai cunoscute astfel de coduri sunt codurile Exces 3 si Gray.

Codul Exces 3 este rezultat din codul hexazecimal prin adunarea numarului 3 (scrisn binar) la fiecare cifra.


16/200

2.1. CODURI DE REPREZENTARE A DATELOR 17

In acest fel, prin complementarea cifrelor binare care formeaza codul cifreiise obtinecodul cifrei 9 i.

Pentru codul Gray, caracteristic este faptul ca orice codificare a unui numar difera decodificarea succesorului sau prin exact o cifra binara.

Cele doua coduri sunt reprezentate n tabelul urmator:

Cifra 0 1 2 3 4 5 6 7 8 9Exces3 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100

Gray 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101

2.1.2 Reprezentarea zecimal codificat binar

Aproape toate calculatoarele folosesc pentru memorarea cifrelor zecimale reprezentarean cod 8421.

Insa, deoarece sistemele de calcul lucreaza cu octeti, desi sunt suficiente 4 biti pentruo cifra zecimala, se folosesc doua modalitati de codificare:

Forma condensata (mpachetata), n care, pe cele 8 pozitii ale unui octet suntreprezentate doua cifre zecimale exprimate n binar;

Forma dilatata (despachetata), n care pe fiecare octet se retine o singura cifra

zecimala pe ultimii patru pozitii binare.Primele patru pozitii ale fiecarui octet sunt ocupate de o marcaM.

Exemplul 2.1 Numarul342 este memorat pe doi octeti n forma mpachetat a

0 0 0 0 0 0 1 1 0 1 0 0 0 0 1 0

2430

si pe trei octeti n forma despachetata:

M 0 0 1 1 M 0 1 0 0 M 0 0 1 0

43 2


17/200


2.1.3 Codul ASCII

Char Cod Char Cod Char Cod

(20)16 @ (40)16 (60)16! (21)16 A (41)16 a (61)16 (22)16 B (42)16 b (62)16# (23)16 C (43)16 c (63)16$ (24)16 D (44)16 d (64)16% (25)16 E (45)16 e (65)16& (26)16 F (46)16 f (66)16 (27)16 G (47)16 g (67)16( (28)16 H (48)16 h (68)16) (29)16 I (49)16 i (69)16

(2A)16 J (4A)16 j (6A)16+ (2B)16 K (4B)16 k (6B)16 (2C)16 L (4C)16 l (6C)16

(2D)16 M (4D)16 m (6D)16. (2E)16 N (4E)16 n (6E)16/ (2F)16 O (4F)16 o (6F)160 (30)16 P (50)16 p (70)161 (31)16 Q (51)16 q (71)162 (32)16 R (52)16 r (72)163 (33)16 S (53)16 s (73)164 (34)16 T (54)16 t (74)165 (35)16 U (55)16 u (75)166 (36)16 V (56)16 v (76)167 (37)16 W (57)16 w (77)168 (38)16 X (58)16 x (78)169 (39)16 Y (59)16 y (79)16: (3A)16 Z (5A)16 z (7A)16; (3B)16 [ (5B)16 { (7B)16

< (3C)16 \ (5C)16 (7C)16= (3D)16 ] (5D)16 } (7D)16> (3E)16 (5E)16 (7E)16? (3F)16 (5F)16 DEL (7F)16

Un cod foarte important folosit n reprezentarea standard a simbolurilor alfabetice sinumerice este codulASCII (AmericanStandardCode forInformationInterchange).

El are 28 = 256 simboluri sursa, codificate n secvente binare de lungime 8; tabelulde mai sus cuprinde simbolurile printabile avand codurile ASCII n intervalul [32, 127] (n


18/200

2.1. CODURI DE REPREZENTARE A DATELOR 19

domeniul [0, 31] nu sunt simboluri printabile, iar n zona [128, 255] se definesc simboluriauxiliare, care nu sunt pe tastatura).

De exemplu, litera A, va avea codul hexazecimal - binar

(41)16= (01000001)2

caruia n zecimal i corespunde numarul 65.De remarcat modalitatea diferita de codificare a cifrelor zecimale.In codul ASCII se codifica caracterele; deci n aceasta codificare, cifrele 0, 1, . . . , 9

sunt considerate caractere si prelucrate ca atare.De exemplu, nu se pot face operatii aritmetice obisnuite cu ele, ci doar cu codurile

ASCII asociate.

Codul ASCII nu este singurul cod construit pentru caractere.

Cel mai cuprinzator cod folosit care cuprinde caracterele si semnele tuturor alfa-betelor utilizate pe tastaturi este Unicode.

Folosind o notare numerica pe 32 sau 16 biti, el ofera un cod unic pentru fiecarecaracter, indiferent de platforma folosita, de program sau limbaj.

Unicode este solicitat drept standard de XML, Java, ECMAScript (JavaScript), LDAP,CORBA 3.0, WML etc.

Pentru orice detaliu privind versiunile Unicode, se poate folosi site-ulhttp://www.unicode.org.


19/200


2.2 Reprezentarea numerelor n sistemele de calcul

In calculatoare, sistemul de numeratie utilizat este cel binar.

Reprezentarea numerelor n acest sistem se face n mai multe forme, n functie de tipullor; pentru fiecare tip, operatiile aritmetice elementare sunt efectuate de catre dispozitivespeciale nglobate n arhitectura calculatorului (ceea ce asigura o viteza sporita de calcul).

2.2.1 Reprezentarea numerelor ntregi

Reprezentarea n memoria calculatorului a numerelor ntregi (numita si reprezentare al-gebrica) se realizeaza pe un numar fix de n pozitii binare (de regula n= 8, 16, 32, 64 sau128).

Aceasta reprezentare poate fi schematizata n modul urmator:

n n1 n2 2 1

S

. . . . . .

Prima pozitie din stanga (a n-a pozitie binara) este numitabit de semn; ea este ocupatade un bit care are valoarea 0 daca numarul este nenegativ, 1 daca numarul este negativ.

Ai-a cifra binara este coeficientul lui 2i1 n reprezentarea numarului n baza 2.Deci cel mai mare numar ntreg care se poate reprezenta pe n biti este

12n2 + 12n3 + . . . + 121 + 120 = 2n1 1

De exemplu, pentru n = 16, acesta este 215 1 = 32.767.In schimb, cel mai mic numar care poate fi memorat este2n1; el are reprezentarea

n n1n2 2 1

1 0 0 00. . . . . .

S

In cazul n = 16, acesta este 215

=32.768.

Deci pe 16 pozitii binare pot fi reprezentate toate numerele ntregi din intervalul[32.768, 32.767].


20/200

2.2. REPREZENTAREA NUMERELOR IN SISTEMELE DE CALCUL 21

2.2.2 Operatii cu numere ntregi

Adunarea a doua numere ntregi se efectueaza n binar, pozitie cu pozitie, de la dreapta

spre stanga; dispozitivul aritmetic al sistemelor de calcul care efectueaza adunarea senumeste sumator.

Exemplul 2.2 Sa efectuam adunarea23 + 15 folosind reprezentarea pe8 cifre binare (unoctet). Efectuarea acestei operatii este redata de figura urmatoare:

0 0 0 1 0 1 1 1

11110000

0 0 1 0 0 1 1 0

23+15=38

Pentru scadere se foloseste acelasi dispozitiv aritmetic care realizeaza adunarea.Motivatia consta n faptul ca orice scadere se poate scrie sub forma unei adunari

x y=x + (y).Pentru aceasta este necesara o reprezentare a numerelor negative astfel ncat sa per-

mita aplicarea relatiei de mai sus.

Sunt cunoscute trei astfel de reprezentari:

1. Cod direct, care coincide cu reprezentarea algebrica (folosind bitul de semn);

2. Cod invers(saucod complementar la1): se obtine prin nlocuirea fiecarei cifre binareacu 1 a;

3. Cod complementar (la2): se obtine din codul invers, la care n faza a doua seaduna numarul 1.

Exemplul 2.3 Sa reprezentam n fiecare din cele trei forme, pe 16 biti (doi octeti),numarul320.(1) Deoarece320 = (101000000)2, reprezentarea lui320 n cod direct este:

1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0

(2) Codul invers se obtine din reprezentarea numarului320, prin complementarea tuturorcifrelor binare:

1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1


21/200


(3) Pentru codul complementar, se aduna1 la codul invers:

1 1 1 1 1 1 1 0 1 1 0 0 0 0 0 0

Scaderea se transforma n adunare prin reprezentarea scazatorului n cod invers sau codcomplementar.

Deoarece marea majoritate a implementarilor folosesc codul complementar, ne referimla aceasta maniera de operare.

Motivarea matematica este foarte simpla.

Sa presupunem ca avem un numar ntreg, reprezentat n binar (pe n biti) sub formaanan1 . . . a2a1, unde

a=

n1

i=1

ai2i1

iar an este bitul de semn.

Atunci reprezentarea luia n cod complementar este

a=n1

i=1

(1 ai)2i1 + 1 =

n1

i=1

2i1 n1

i=1

ai2i1 + 1 = 2n1 1 a + 1 = 2n1 a

Decia= 2n1 a

si diferentab ase poate scrie

b a= b + a 2n1

De remarcat ca numarul 2n1 nu afecteaza pozitiile binare ale numarului, ci numaibitul de semn.

Revenind la algoritm, pentru scaderea b ase efectueaza urmatorii pasi:

1. Se trece a n cod complementar;

2. Se face adunarea dintreb siascris n noua reprezentare;

3. Daca rezultatul este negativ, acesta este reprezentat tot n cod complementar;

4. Daca apare transport la pozitia alocata semnului, acesta se ignora.


22/200


Exemplul 2.4 Sa se efectueze32 41 cu reprezentare n cod complementar a scazatoru-lui, pe8 cifre binare.

32 = (100000)2, 41 = (101001)2.

Efectuarea operatiei de scadere este redata prin schema urmatoare:

+41 n cod direct

+32 n cod direct

41 n cod complementar

+1

0 0 1 0 1 0 0 1

0110101100000100

1 1 0 1 0 1 1 1

11101111 32 + (41) =9 n cod complementar

2.2.3 Reprezentarea numerelor reale n virgula mobila

Numerele reale se reprezinta n interiorul unui sistem de calcul sub forma fractionara,ntr-o codificare numita virgula mobila(floating point).

In prima faza, orice numar este adus la formaN=1, f2e

unde:

Neste numarul care trebuie reprezentat n virgula mobila,

f - partea fractionara a lui N,

1, f se numeste mantisa si trebuie sa respecte relatia de normalizare1 |1, f|< 2;

2 este baza sistemului de numeratie (sistemul binar),

e este exponentul bazei sistemului de numeratie.

Exemplul 2.5 NumarulN= 25 se scrie n virgula mobila sub forma

25 = (11001)2= 1, 100124

.

Exemplul 2.6 Numarul 31

32se va scrie sub forma unui numar n virgul a mobila astfel:

31

32=

24 + 23 + 22 + 21 + 20

25 = 21+22 +23+24 +25 = (0, 11111)2= 1, 11112

1.


23/200


Exemplul 2.7 Pentru N = 1

8 reprezntarea n virgula mobila este:

1

8 = 23 =

(0, 001)2=1, 023.

De observat ca practic inegalitatea de normalizare coincide cu pozitionarea virgulei ncadrul numarului binar dupa prima cifra 1, concomitent cu modificarea corespunzatoarea exponentului bazei.

Reprezentarea numerelor n virgula mobila are doua forme standard:

1. reprezentarea n virgula mobila simpla precizie;

2. reprezentarea n virgula mobila dubla precizie.

Reprezentarea n simpla precizie se face pe un cuvant (32 pozitii binare) sub forma:

S

32 31 24 23 1fC=e + 127

Prima pozitie (S) reprezinta semnul numarului N; el este codificat cu 0 daca N >0si 1 daca N


24/200


Deci

032 31 24 23 1

1 0 0 1 0 0 0 0 . . . . . . . . . 0 01 0 0 0 0 0 1 1

Exemplul 2.9 Pentru 31

32= 1, 111121 (Exemplul 2.6) avemS= 0, f= 1111,

C=1 + 127 = 126 = (01111110)2, deci

032 31 24 23 1

1 1 1 1 0 0 0 0 . . . . . . . . . 0 00 1 1 1 1 1 1 0

Exemplul 2.10 Numarul1

8=1, 023 (Exemplul 2.7) areS= 1, f= 0 si

C=3 + 127 = 124 = (01111100)2, deci

132 31 24 23 1

0 0 0 0 0 0 0 0 . . . . . . . . . 0 00 1 1 1 1 1 0 0

Reprezentarea n virgula mobila dubla precizie se realizeaza pe 64 pozitii binare(cuvant dublu), a carui structura este

S

64 63 53 52 1fC=e + 1023

In acest caz, caracteristica este reprezentata pe 11 cifre binare, avand posibilitatea de anmagazina o valoare maxima 211 1 = 2047, ceea ce corespunde unui exponente= 20471023 = 1024.

Partea fractionara ocupa 52 pozitii binare.

Exemplul 2.11 Sa reprezentam n virgula mobila dubla precizie numarul 124, 0625.Vom avea124, 0625 = (1111100, 0001)2= 1, 11110000012

6, deciS= 1, f= 1111000001,C=e + 1023 = 6 + 1023 = 1029 = (10000000101)2.

Reprezentarea este

164 63 53 52 1

1 1 1 1 0 0 0 0 0 1 0 0 . . . . . . . . . 01 0 0 0 0 0 0 0 1 0 1


25/200


La ambele forme de reprezentare n virgula mobila, cifra 1 dinaintea virgulei nu sereprezinta; observatia este utila atunci cand se doreste obtinerea numarului real din unadin formele de reprezentare n virgula mobila.

Exemplul 2.12 Un numar n virgul a mobila are forma:11000010 11001111 00001111 00100001

Urmarind forma de reprezentare, se constata ca:- Prima cifraS= 1 indica un numar negativ;- Urmatoarele8 cifre binare specifica valoarea caracteristicii

C= 10000101 = 133, decie= 133127 = 6;- Partea fractionara ocupa ultimele23 cifre binare f = 10011110000111100100001.Deci numarul este

N=1, 10011110000111100100001 26 =1100111, 10000111100100001 =103, 5296.

2.2.4 Operatii n virgula mobila

Adunarea si scaderea a doua numere n virgula mobila se efectueaza astfel:

1. Se compara cei doi exponenti pentru a-l determina pe cel mai mare;

2. Se aliniaza mantisa numarului cu exponent mai mic, prin deplasarea virguleicorespunzatoare exponentului mai mare;

3. Se aduna (scad) mantisele aliniate, pastrand exponentul comun;4. Eventual se normalizeaza mantisa, concomitent cu modificarea rezultatului.

Exemplul 2.13 Sa se efectueze adunarea n virgula mobila 3

4+ 7.

x=3

4=

21 + 20

22 = 21 + 22 = (0, 11)2= 1, 12

1,

y= 7 = (111)2= 1, 1122.

Deoarecey are exponentul mai mare, x se va alinia corespunzator:

x= 1, 1121 = 0, 001122

Acumx + y= (0, 0011 + 1, 11)22 = 1, 111122.Nu este necesara normalizarea mantisei.


26/200


Exemplul 2.14 Sa calculam n virgul a mobila349:x= 34 = (100010)2= 1, 0012

5,y= 9 = (1001)2= 1, 0012

3 = 0, 0100125.

Decix y= (1, 000100, 01001)25 = 0, 1100125.Normalizand, se obtine

x y= 1, 100124 = (11001)2= 25

Operatiile de nmultire si mpartire presupun:

1. Adunarea (scaderea) exponentilor;

2. Inmultirea (mpartirea) mantiselor;

3. Eventuala normalizare a mantisei.

Exemplul 2.15 Sa se efectueze n virgula mobila59:x= 5 = (101)2= 1, 012

2, y = 9 = (1001)2= 1, 00123.

x y= (1, 011, 001)22+3 = 1, 0110125 = (101101)2= 45.

Exemplul 2.16 Sa se efectueze n virgula mobila5 : 10.x= 5 = (101)2= 1, 012

2, 10 = (1010)2= 1, 0123.

x; y= (1, 01 : 1, 01)223 = 1, 021 = (0, 1)2= 0, 5.


27/200


2.3 Exercitii

1. Sa se treaca din baza 10 n baza 2 numerele

18926; 7772; 7863, 15; 0, 7.

2. Sa se treaca din baza 2 n baza 10 numerele1101100010100110; 100010101001, 0011011001.

3. Sa se efectueze calculele11 + 32600, 59910692, 9862 + 2004318552.

4. Sa se defineasca scaderea a doua numere ntregi folosind ca reprezentare codul invers.

5. Sa se scrie n virgula mobila numerele

6489; 0, 1;

85

256 .

6. Sa se reprezinte numerele scrise n virgula mobila n exercitiul anterior, pe

(1) 32 pozitii binare (simpla precizie);

(2) 64 pozitii binare (dubla precizie).

7. Ce numar real are reprezentarea n simpla precizie000010010011010110100011010101011.

8. Aceeasi problema pentru numarul a carui reprezentare n dubla precizie este:10001001001001000011101101010100001001010110100100001010000110101.

9. Sa se efectueze n virgula mobila calculele

8 + 7

32;

25

36 799; 36112, 495; 38398/73.

10. Sa se detalieze operatiile de adunare si scadere cu numere reprezentate n formacondensata.


28/200

Capitolul 3

Algebre si functii boolene

3.1 Definirea algebrelor booleene

Elementul teoretic fundamental necesar pentru analiza si sinteza circuitelor care formeazaarhitectura unui calculator este cel de Algebra Boole1.

Definitia 3.1 O algebra Boole este un sistemB= (B, , , 0, 1) cu proprietatile:

1. a,b,c B (a b) c= a (b c); (asociativitatea lui)

2. a,b,c B (a b) c= a (b c); (asociativitatea lui)

3. a, b B a b= b a; (comutativitatea lui)

4. a, b B a b= b a; (comutativitatea lui)

5. 0 B unic astfel ncata B a 0 = 0 a= a; (element unitate pentru)

6. 1 B unic astfel ncata B a 1 = 1 a= a; (element unitate pentru)

7. a,b,c B a (b c) = (a b) (a c); (distributivitatea lui fat a de)

8. a,b,c B a (b c) = (a b) (a c); (distributivitatea lui fat a de)

9. a B, a B a a= 0, a a= 1. (complement)O prima observatie este ca o algebra booleana are cel putin doua elemente 0 si 1, iar

0 = 1.

1George Boole (1815 - 1864): matematician si filosof englez, considerat prin prisma algebrelor carei poarta numele unul din fondatorii informaticii teoretice.

29


29/200

30 CAPITOLUL 3. ALGEBRE SI FUNCTII BOOLENE

Exemplul 3.1 Fie Q o multime. MultimeaQ= {P|P Q} = 2Q formeaza o algebraBoole cu operatiile de reuniune si intersectie.

Elementul0 este multimea vida, iar elementul1 este multimeaQ.

Axiomele din Definitia 3.1 se verifica imediat.

Exemplul 3.2 MultimeaB= {0, 1} cu operatiile 0 10 0 11 1 1

0 10 0 01 0 1

formeaza de asemenea o algebra booleanaB= (B, , , 0, 1).

3.2 Proprietati ale algebrelor booleene

In acest paragraf vom face o trecere n revista a principalelor proprietati ndeplinite de oalgebra Boole.

Teorema 3.1 Intr-o algebra booleana sunt verificate legile de idempotent a:

a a= a, a a= a.

Demonstratie: Vom aveaa a= (a a) 1 = (a a) (a a) =a (a a) =a 0 =a.

Pentru a doua relatie vom proceda similar (prin dualitate):a a= (a a) 0 = (a a) (a a) =a (a a) =a 1 =a.

Teorema 3.2 a 1 = 1, a 0 = 0.

Demonstratie:a 1 = (a 1) 1 = (a 1) (a a) =a (1 a) =a a= 1,a 0 = (a 0) 0 = (a 0) (a a) =a (0 a) =a a= 0.

Teorema 3.3 a (a b) =a, a (a b) =a. (absorbtie)

Demonstratie:a (a b) = (a 1) (a b) =a (1 b) =a (b 1) =a 1 =a,a (a b) = (a a) (a b) =a (a b) =a.


30/200

3.3. ALTE OPERATII BOOLEENE 31

Teorema 3.4 Pentru oricea B, a este unic.

Demonstratie: Presupunem prin absurd ca exista doua complementea, a1 ale lui a.

Conform Definitiei 3.1, avema a= a a1= 1, a a= a a1= 0.

Atuncia1= 1a1= (aa)a1=a1(aa) = (a1a)(a1a) = 0(a1a) = (aa)(a1a) =(a a1) a= 1 a= a.

Teorema 3.5 a= a.

Demonstratie: a este complementul lui a. Dar si a este complementul lui a.Deoarece complementul este unic (Teorema 3.4), rezulta a= a.

Deci, putem considera complementara ca o aplicatie bijectiva :B B.

Teorema 3.6 a b= a b, a b= a b. (regulile De Morgan)

Demonstratie: Vom demonstra ca (a b) (a b) = 1 si (a b) (a b) = 0; deci a bsi a b sunt complementare.

Din Teorema 3.4 rezulta atunci a b= a b.Vom avea

(ab)(ab) = [(ab)a][(ab)b] = [(ba)a][a(bb)] = [b(aa)](a1) =(b 1) 1 = 1 si(a b) (a b) = [a (a b)] [b (a b)] = [(a a) b] [b (b a)] = 0 [(b b) a] = 0.

Pentru a doua relatie se procedeaza similar.

3.3 Alte operatii booleene

Inafara celor trei operatii folosite pana acum de o algebra booleana (, , ), mai suntcunoscute si alte operatii.

Astfel, putem enumera:

1. Diferenta simetrica: a b= (a b) (a b);

2. Operatorul Sheffer: a|b= a b;

3. Echivalenta: a b= (a b) (a b);

4. Implicatia: a b= b a.


31/200


Observatia 3.1 In arhitectura calculatorului, implementarea operatorului este notatacuXOR, iar | cuNAND.

Cei patru operatori au o serie de proprietati specifice ale caror demonstratii le lasam caexercitiu.

Propozitia 3.1

1. 0 0 = 1 1 = 0, 0 1 = 1 0 = 1;

2. este asociativa si comutativa;

3. a 0 =a, a 1 =a;

4. a a= 0, a a= 1;

5. a b= c = a c= b;

6. a b= c = a b c= 0;

7. a (b c) = (a b) (a c).

Propozitia 3.2

1. a b= a b;

2. a b= a b;

3. a b= (a b) (b a);

Propozitia 3.3 Afirmatiile

1. a b= 0;

2. a b= 1;

3. a= b;

sunt echivalente.


32/200

3.4. FUNCTII BOOLEENE 33

3.4 Functii booleene

In continuare vom considera o algebra booleana particulara (vezi si Exemplul 3.2)

A= ({0, 1}, +, , 0, 1) unde+ 0 10 0 11 1 1

0 10 0 01 0 1

Mai avem 0 = 1, 1 = 0. Axiomele unei algebre booleene se verifica imediat.In mod uzual, operatorul se omite (similar cu operatorul de nmultire din mate-

matica).Vom nota de asemenea{0, 1}n = {0, 1} {0, 1} . . . {0, 1}

n ori

.

Definitia 3.2 O functie booleanaf(x1, x2, . . . , xn) este o aplicatief : {0, 1}n {0, 1}.

Exemplul 3.3 Pentrun= 2 se pot construi16 functii booleene de doua variabile:

x1 x2 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f150 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 10 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 11 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 11 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

In general pentru n oarecare vom avea:

Propozitia 3.4 Pentru oricen 1 se pot defini22n

functii booleene den variabile.

Demonstratie: Este imediata, deoarece{0, 1}n are 2n elemente, iar{0, 1} numai doua.

Definitia 3.3 Fief, g: {0, 1}n {0, 1}. Definim

f+g = h prinh(x1, x2, . . . , xn) =f(x1, x2, . . . , xn) +g(x1, x2, . . . , xn);

f g= h prinh(x1, x2, . . . , xn) =f(x1, x2, . . . , xn) g(x1, x2, . . . , xn);

f=g pring(x1, x2, . . . , xn) =f(x1, x2, . . . , xn).

Exemplul 3.4 Sa consideramn= 2 si functiile booleene (f5 sif1 din Exemplul 3.3):f 0 10 0 11 0 1

g 0 10 0 01 0 1

Atunci functiilef+g, fg, f sig sunt definite conform urmatorului tablou:


33/200


x1 x2 f g f+g f g f g0 0 0 0 0 0 1 10 1 1 0 1 0 0 1

1 0 0 0 0 0 1 11 1 1 1 1 1 0 0

Deci operatiile cu functii sunt definitepunct cu punct; reprezentarea lor sub forma tabelaraconstituie o modalitate convenabila de calcul deoarece folosesc n mod direct formuleledin tabelele de operatii ale algebrei booleene A.

Teorema 3.7 Fie Fn multimea functiilor booleene de n (n 1) variabile. SistemulFn= (Fn, +, , 0, 1) formeaza o algebra booleana (algebra Boole a functiilor booleene denvariabile).

Demonstratie: Axiomele algebrei boolene se verifica usor, folosind Definitia 3.3. Functia0 este definita

0(x1, x2, . . . , xn) = 0, xi {0, 1} (1 i n),

iar functia1 prin

1(x1, x2, . . . , xn) = 1, xi {0, 1} (1 i n).

Definitia 3.4 Fie Fn algebra Boole a functiilor booleene de n variabile. Se numestepondere o aplicatiew : Fn N definitaw(f) = card(f1(1)) (numarul de elementedin{0, 1}n care au imaginea1 prinf).

Exemplul 3.5 In Exemplul 3.3 sunt listate elementele algebrei F2. Ponderile acestorelemente sunt listate n tabelul urmator:

f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15w 0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4

Urmatorul rezultat este imediat.

Teorema 3.8

1. w(f) +w(f) = 2n;

2. w(f+g) +w(f g) =w(f) +w(g).

Vom ncerca n continuare sa definim o reprezentare a functiilor booleene, utila n con-struirea circuitelor liniare.

Aceasta reprezentare se bazeaza pe notiunea de minterm.


34/200

3.4. FUNCTII BOOLEENE 35

Definitia 3.5 Fien (n 1)un numar ntreg sii [0, 2n1]. Consideram(i1, i2, . . . , in)2reprezentarea binara a luii:

i=

nk=1

ik2nk

ik {0, 1}.

Atunci functia mintermmi(x1, x2, . . . , xn) Fn este definita prin

mi(x1, x2, . . . , xn) =

1 daca x1= i1, x2=i2, . . . , xn=in0 altfel

Vom nota n continuare i = (i1, i2, . . . , in)2 reprezentarea binara a numarului ntreg i [0, 2n 1].

Propozitia 3.5

1. mimj = 0 dacai =j .

2. mimi = mi.Demonstratie: Imediat.

Teorema 3.9 Orice functie booleana poate fi reprezentata n mod unic ca suma de mintermi.

Demonstratie: Prin inductie dupa k = w(f).k= 0: trivial;k= 1: orice astfel de functie este un minterm.k k+1: Sa presupunem ca feste o functie de pondere k + 1. Deci exista un ntreg

i= (i1, i2, . . . , in)2 astfel ca f(i1, i2, . . . , in) = 1.Atunci conform Teoremei 3.8 f(x1, x2, . . . , xn) =mi(x1, x2, . . . , xn)+g(x1, x2, . . . , xn)

unde w(g) k.Unicitatea este si ea imediata.

Corolarul 3.1 Orice functie booleanaf Fn este de forma

f(x1, x2, . . . , xn) =iI

mi(x1, x2, . . . , xn)

undeI {0, 1, . . . , 2n 1}.

Corolarul 3.2 Dacaf(x1, x2, . . . , xn) =

iI

mi(x1, x2, . . . , xn), g(x1, x2, . . . , xn) =iJ

mi(x1, x2, . . . , xn)

atuncif(x1, x2, . . . , xn) +g(x1, x2, . . . , xn) =

iIJ

mi(x1, x2, . . . , xn),

f(x1, x2, . . . , xn)g(x1, x2, . . . , xn) =

iIJ

mi(x1, x2, . . . , xn),

f(x1, x2, . . . , xn) =iI

mi(x1, x2, . . . , xn).


35/200


Exemplul 3.6 Fien= 2 si functia booleana:f(x1, x2) =m0(x1, x2) +m2(x1, x2) +m3(x1, x2)

Un tabel cu valorile tuturor functiilor minterm de doua variabile si cu valorile functiei

f este:

x1 x2 m0(x1, x2) m1(x1, x2) m2(x1, x2) m3(x1, x2) f0 0 1 0 0 0 10 1 0 1 0 0 01 0 0 0 1 0 11 1 0 0 0 1 1

3.5 Forme canonice

Scopul acestui paragraf este de a asocia fiecarei functii booleene fo expresie booleanascrisa sub o forma unica. Aceasta se va numi forma canonica a luif sau forma normaldisjunctiva a luif.

O consecinta importanta a acestei reprezentari va fi aceea ca putem verifica echivalentaa doua expresii cercetand daca acestea pot fi reduse la aceeasi forma canonica (deci nu vommai face apel la constructia tabelelor de valori a functiei asociate, destul de costisitoaredin punct de vedere al complexitatii).

Definitia 3.6 Un literal este o variabila sau complementul ei.

Definitia 3.7 FieBn= {x1, x2, . . . , xn}. O expresie este un minterm sau un produs

fundamental n algebra BooleBn= (Bn, +, , 0, 1) daca si numai daca este concatenareaan literali distincti.

Exemplul 3.7 Cei opt mintermi dinB3 suntx1x2x3 x1x2x3 x1x2x3 x1x2x3x1x2x3 x1x2x3 x1x2x3 x1x2x3

Mintermii vor fi notati n felul urmator: fie (i1, i2, . . . , in) {0, 1}n.Atunci un minterm standard este

xi11

xi22

. . . xinn

unde

xijj =

xj pentru ij = 0xj pentru ij = 1

(1 j n).

Exemplul 3.8 x01

x12

x13

= x1x2x3, x1

1x02

x03

= x1x2x3 etc.


36/200

3.5. FORME CANONICE 37

Observatia 3.2 Fiecare mintermxi11xi22 . . . x

inn corespunde functiei booleene

mi(x1, x2, . . . , xn) undei= (i1, i2, . . . , in)2.

Teorema 3.10 Dacaf este o functie booleana de o variabila (f F1) atunci

f(x) =xf(1) +xf(0).

Demonstratie: Sa consideram cele doua valori posibile pe care le poate lua variabilabooleana x.

Pentru x= 1 vom avea

f(1) = 1 f(1) + 0 f(0) =f(1).

Similar pentru asignarea x= 0.

Deci egalitatea se verifica pentru toate asignarile posibile ale variabilei.Urmatoarea teorema da forma canonica pentru orice functie booleana de n variabile.

Teorema 3.11 Dacaf este o functie booleana den variabile (f Fn) atunci

f(x1, x2, . . . , xn) =1

i1=0

1i2=0

. . .1

in=0

f(i1, i2, . . . , in)xi11

xi22

. . . xinn.

Aceasta este forma normal disjunctiva a functieif.

Demonstratie: Prin inductie dupa numarul nde variabile.Pentru n= 1 avem rezultatul dat de Teorema 3.10.Sa presupunem Teorema 3.11 adevarata pentru n 1 variabile, adica

f(x1, x2, . . . , xn) =1

i2=0

. . .1

in=0

f(x1, i2, . . . , in)xi22

. . . xinn.

Pe de alta parte, f(x1, i2, . . . , in) =x0

1f(0, i2, . . . , in) +x

1

1f(1, i2, . . . , in) si, dupa nlo-

cuire

f(x1, x2, . . . , xn) =1

i2=0

. . .1

in=0

(x01

f(0, i2, . . . , in) +x1

1f(1, i2, . . . , in))x

i22

. . . xinn =

1i1=0

. . .1

in=0

f(i1, i2, . . . , in)xi11

xi22

. . . xinn.

Corolarul 3.3 Forma normal disjunctiva a unei functii booleene este unica.

Demonstratie: Sa presupunem ca exista doua forme normale diferite corespunzatoare luif.

Deci exista cel putin un (i1, i2, . . . , in) {0, 1}n pentru care coeficientii din cele douaexpresii sunt diferiti.

Consideram asignarea definita prin x1=i1, . . . , xn = in.


37/200


Evaluand prima expresie obtinem f(i1, i2, . . . , in) = 1(0), iar pentru a doua expresief(i1, i2, . . . , in) = 0(1), ceea ce contrazice faptul ca ambele expresii reprezinta f.

Fiind data o functie booleana f, sa vedem cum se poate scrie forma sa normal dis-junctiva.

Cel mai sugestiv este sa aratam aceasta printr-un exemplu.

Exemplul 3.9 Fief F3 definita de urmatorul tabel:x1 0 0 0 0 1 1 1 1x2 0 0 1 1 0 0 1 1x3 0 1 0 1 0 1 0 1f 0 1 0 1 0 1 0 1

Pe linia luif, primul element este0.Deci termenul corespunzator estef(0, 0, 0)x0

1x02

x03

= 0 x1x2x3= 0.

Deoarece a+ 0 = a, contributia oricarei coloane unde valoarea lui f este 0 poate fiignorata.

Daca valoarea luif este1, termenul respectiv va fi pastrat.Decif(x1, x2, x3) =x

0

1x02

x13

+x01

x12

x13

+x11

x02

x13

+x11

x12

x13

= x1x2x3+x1x2x3+x1x2x3+x1x2x3.

3.6 Inele booleene

Definitia 3.8 Un inel boolean este un inel unitar n care orice element este idempotent.

FieB= (B, , , 0, 1) o algebra Boole, n care definim operatiile (pentru orice x, y B):

x y= (x y) (x y), x y = x y.

Structura (B, , ) formeaza o structura de inel boolean.Regulile de comutativitate si asociativitate fata de se deduc din postulatele algebrei

booleeneB.Din relatiax 1 = 1 x= x rezulta ca 1 este element neutru.In plus, orice element este idempotent, pentru ca x x= x.Pentru : comutativitatea rezulta n mod banal.

Pentru asociativitate:(xy)z= ((xy)z)(x y z) = [((xy)(xy))z][(x y) (x y)z] =[(xy z)(xy z)][(xy)(xy)z] = (xy z)(xy z)(xy z)(xy z),relatie simetrica n x, y ,z . Deci (x y) z= x (y z).

Elementul nul este 0 pentru ca x 0 = (x 0) (x 0) = (x 1) 0 =x.Fiecare element este propriul sau invers, deoarece


38/200

3.7. EXERCITII 39

x x= (x x) (x x) = 0 0 = 0.Aceasta relatie se poate scrie 2x= 0, ceea ce nseamna ca avem un inel de caracteristica

2 (proprietate care se poate demonstra pentru orice inel boolean).

Distributivitatea se verifica similar:xy xz= ((xy)x z))(x y (xz)) = (xy (xz))((xy)xz) =

(x y z) (x y z) =x [(y z) (y z)] =x (y z).

Teorema 3.12 Orice inel boolean (B, +, ) se poate structura ca o algebra Boole, cuoperatiile

x y= x+y+x y, x y=x y.

Demonstratie: Se verifica axiomele Definitiei 3.1, unde complementara este definita prinx= 1 +x. In particular, vom avea:

x x= x+x+x x= x+ (1 +x) +x (1 +x) = 1 + 4x= 1,x x= x x= x (1 +x) =x+x= 0.

Se poate stabili deci o corespondenta biunivoca ntre inelele booleene si algebrelebooleene.

Aceasta conduce la o serie de aplicatii interesante, n special prin inducerea pro-prietatilor structurilor algebrice n domeniul algebrelor Boole.

3.7 Exercitii

1. Sa se arate ca ntr-o algebra booleana au loc relatiile:

a (a b) =a b, a (a b) =a b.

2. Intr-o algebra Boole se defineste o relatie de ordine prin

a b b= a b

Sa se arate ca a b b a.

3. a b a b= 0 a b= 1.

4. a b= 0 b a.

5. Demonstrati afirmatiile din Propozitiile 3.1, 3.2 si 3.3.

6. Sa se arate ca pe Fn se poate defini o distanta prin relatia(f, g) =w(f+g) w(f g).

Sa se construiasca un tabel cu distantele elementelor lui F2.


39/200


7. Demonstrati Teorema 3.8, Propozitia 3.5 si Corolarul 3.2.

8. Fie Ao multime finita nevida. Structurati 2A sub forma de inel boolean.

9. Daca f Fn, atuncif(x1, . . . , xn) =f(x1, . . . , xn1, 0) + [f(x1, . . . , xn1, 0) +f(x1, . . . , xn1, 1)]xn.

10. Construiti un algoritm de generare a formei normal conjunctive asociata unei functiibooleene.

11. Sa se arate echivalenta expresiilor booleene

[b (a c) (a c)] (b c), (a b c) (a b c) (a b c) (a b c).

12. Sa se arate ca expresiile booleene

a (a b) (b c), b (a b)

sunt echivalente. Sa se scrie forma normal disjunctiva si normal conjunctiva afunctiei asociate.


40/200

Capitolul 4

Sisteme digitale

4.1 Circuite combinationaleOdata cu acest capitol vom ncepe un studiu sistematic al elementelor fundamentale deconstructie a circuitelor.

Definitia 4.1 Un circuit este un graf orientat cu cel putin o intrare si cel putin o iesire,care are doua tipuri de noduri: conectori si porti.

Intrarile unui circuit primesc semnale, sub forma unor seturi de valori din mult imea{0, 1}n (nfiind numarul de intrari ale circuitului).

Definitia 4.2 Un circuit combinational (CLC1

) este o retea arborescenta n care iesireala momentul (tactul) t depinde numai de intrarile la momentul (tactul) t.

Un circuit este activdaca iesirea sa este 1; n caz contrar, circuitul este inactiv.

4.1.1 Porti

Cele mai simple circuite sunt circuitele constante 0 si 1; de obicei primul este marcatprintr-un punct ., iar al doilea printr-o linie .

O variabila booleana (logica)a poate controla un circuit, activandu-l (daca ia valoarea1) sau dezactivandu-l (la valoarea 0).

Indiferent daca modul de activare/dezactivare este de tip mecanic, electric, electro-magnetic, integrat, imprimat, neural, ideea de baza este aceeasi: pentru ntelegere, vomconsidera circuitul sub forma unei linii legata la o sursa permanenta de curent, linientrerupta de o poarta al carei rol este de a nchide sau deschide circuitul:

1Denumirea completa este Circuit Logic Combinational.

41


41/200

42 CAPITOLUL 4. SISTEME DIGITALE

a a

a= 0 (dezactivat) a= 1 (activat)

Poarta poate fi deschisa (dezactivata) prin intermediul unui arc, care n pozitie de repaos(a= 0) este destins.

Daca a = 1, acest arc este comprimat si nchide poarta, activand astfel circuitul, princare trece (de fapt) valoarea lui a.

Vom nota un astfel de circuit prin a .

Sa definim modul de combinare al circuitelor elementare, folosind operat iile booleene(disjunctie, conjunctie, negatie).

Implementarea acestor operatii se realizeaza prin circuite numite porti.

Poarta AND:

Fie a, b doua variabile booleene. Pentru ab (sau n funct ie de notatie a b) sepoate construi circuitul

a b

(1)

a b

a b(2) (3)

0 10 0 01 0 1

(1) este structura functionala a circuitului, (2) este notatia logica, iar (3) - tabelade operatie a operatorului AND operatorul dintr-o algebra Boole.

Se observa ca valoarea de iesire este 1 daca si numai daca a= b = 1.

Simbolul portiiAND (Figura (2)) poate fi generalizat la n intrari a1, . . . , an, obti-nandu-se o poarta ANDn.

Poarta OR:

Pentru poarta care realizeaza circuitul a+b (a b n notatie booleana), structurafunctionala este reprezentata n Figura (1), simbolul logic de Figura (2), iar tabelade operatii - de Figura (3):


42/200

4.1. CIRCUITE COMBINATIONALE 43

a

b

a b

a + b

(1) (2) (3)

+ 0 10 0 11 1 1

Evident, si aceasta poarta poate fi extinsa la nintrari: ORn.

Poarta N OT:

O poarta pentru realizarea operatiei de complementare (negatie) a variabilei booleeneaeste Figura (1):

a

a a a(1) (2) (3)

Se observa ca circuitul este nchis prin pozitia relaxata a arcului (a = 0); la com-primarea acestuia (a= 1) circuitul se dezactiveaza (deschide).

Simbolul logic este (2), iar uneori chiar (3).

Inafara acestor operatii, n construct ia circuitelor se mai folosesc trei tipuri supli-mentare de porti: NAND, NOR si XOR.

Poarta NAND:

Este un circuit care implementeaza expresia booleana a b. Figura (2) reprezintao alta implementare, obtinuta n urma relatiei De Morgan: a b= a b.

Simbolul logic al portiiNAND este Figura (3).

a b(1)

b

a (2)

a b

a b(3)


43/200


Tabela de operatii a operatorului NAND (similar operatorului Sheffer din algebraBoole) este

|| 0 1

0 1 11 1 0

Poarta N OR:

Este un operator mai putin folosit n teoria algebrelor Boole (nu corespunde unuioperator logic consacrat).

Reprezinta operatiaa b= a b.

a b

a b

a b

Tabela de operatii este:NOR 0 1

0 1 01 0 0

De fapt acesti operatori (NAND si N OR) se obtin prin legarea n serie a doua

porti: o poarta AND (respectiv OR) si o poarta NOT.Teoretic ei se pot generaliza la NANDn (respectiv N ORn).

Poarta XOR:

Este implementarea operatiei sau logic ab ba (operatorul dintr-o algebraBoole):

a

b

a

b

(1)

a b

ab ba

(2) (3)

0 10 0 11 1 0


44/200

4.1. CIRCUITE COMBINATIONALE 45

4.1.2 Circuite

In linii mari, arhitectura unui calculator se bazeaza pe construirea de circuite care formeaza

diverse componente ale unui computer (n special unitatea logico-aritmetica, unitatile dememorie, magistralele de sincronizare, structuri de control).

Cele mai simple circuite sunt cele combinationale.Conform Definitiei 4.2, un circuit combinational este o structura arborescenta con-

struita folosind un numar finit de porti.De exemplu, circuitul urmator nu este combinational:

a

b

In general vom considera circuitele combinationale cu un numar de intrari (noduri deintrare) egal cu numarul de variabile si avand o singura iesire (nod final).

Definitia 4.3 Fie X un circuit combinational de intraria1, . . . , an. Se numeste functiede transmisie a lui X functia booleana fX(a1, . . . , an) cu proprietatea ca fX = 1 daca sinumai daca exista un drum activ de la nodurile de intrare la nodul final.

Teorema 4.1 Doua circuite combinationaleX, Y sunt echivalente dacafX=fY.

Exemplul 4.1 Sa consideram functia booleanaf(a,b,c) = bc(a b). Un circuit combi-national care o implementeaza este

a

bc

f(a,b,c)

Cum aceasta expresie este nsa egala cubcab= 0, pentru ea se poate construi un circuitechivalent redus la un simplu punct.

Evident, acesta este mult mai simplu (nu are nici o poarta, n comparatie cu circuitul

initial cu doua porti).

Definitia 4.4 Complexitatea unui circuit combinational este dat de numarul de porti.

Nu vom face o prezentare a notiunilor de complexitate (spatiu sau timp), acestea fiindidentice cu cele folosite n algoritmica.


45/200


4.2 Extensii

Putem construi ntreaga arhitectura a unui calculator plecand de la un element teoretic

de baza numit sistem digital.

Definitia 4.5 Fie V un alfabet finit nevid si m, n doua numere naturale. Se numestesistem digital structuraS= (X , Y , f ) undeX=Vn, Y =Vm, f :XY.

Un exemplu simplu de sistem digital este circuitul combinational, exprimabil printr-ofunctie booleana.

In aceasta carte vom considera numai sistemele digitale binare, unde V ={0, 1}. Deaceea nu va fi nici o ambiguitate daca vom desemnasistemele digitale binarecu termenulgeneral de sisteme digitale.

Functiaf se numeste functie de transfer.De asemenea, cazurile n = 0 sau m = 0 corespund unor sisteme digitale speciale

(de iesirerespectiv intrare) care vor fi studiate separat. In continuare consideram numaim n= 0.

Sistemele digitale date prin Definitia 4.5 se pot reprezenta grafic sub forma urmatoare:

S

n

m

Y

X

unde prin convent ie un flux de n date se reprezenta printr-o singura sageatamarcata cu valoarea lui n:

n

A= (a1, a2, . . . , an)

a1a2 an

. . .


46/200

4.2. EXTENSII 47

Operatiile de baza care se pot defini pentru sistemele digitale sunt cele de legare nserie si n paralel, operatii numite extensii.

Definitia 4.6 Fie sistemele digitaleSi = (Xi, Yi, fi), i= 1, 2 unde

X1= {0, 1}n, Y1= X2= {0, 1}

m, Y2= {0, 1}p

Se numeste extensie seriala sistemul digitalS= (X , Y , f ) unde X= X1, Y = Y2, iarfunctia de transferf :XY este definita prinf=f2 f1.

Grafic, are loc urmatoarea operatie:

S1

S2

n

m

p

X1

Y2

SS1 S2

m

n

X1 X2

Y1 Y2

p

m

=

Definitia 4.7 Fie Si = (Xi, Yi, fi), (i = 1, 2) doua sisteme digitale. Extensia paralelaS1 S2 este sistemul

S= (X1 X2, Y1 Y2, f12)

undef12:X1 X2Y1 Y2 este definitaf12(x, y) = (f1(x), f2(y)).

Grafic, are loc operatia de combinare:

S1 S2

n1

m1

n2

m2

X1

Y1

X2

Y2

S1 S2

n1+ n2

m1+ m2

n1

n2

m1 m2

X1 X2

Y1 Y2

= S

De remarcat ca ntr-o extensie paralela cele doua sisteme digitale nu interactioneaza.


47/200


Exemplul 4.2 Sa consideram sistemele digitaleS1= ({x1

1, x1

2}, {y1

1}, f1) si

S2= ({x2

1, x2

2, x2

3}, {y2

1, y2

2}, f2) date de figura

S1 S2

x11

x12

x21

x22

x23

y11

y21

y22

Extensia paralelaS1 S2 este

S1 S2

x11

x12

x21

x22x2

3

y11

y21

y22

iar extensia seriala a luiS2 cuS1:

S1

S2

x21

x22

x23

y11

y21

=x11

y22

=x12

Definitia 4.8 Fie sistemele digitaleSi = (Xi, Yi, fi), (1 i 4) cuXi ={0, 1}ni, Yi =

{0, 1}mi sim1+ m2= n3+ n4. O extensie serial-paralela este sistemul

S= (X1

X2

, Y3

Y4

, f)

unde f : X1X2 Y3Y4 este definita f = f34f12 (f12 si f34 sunt functiile detransfer ale extensiilor paraleleS1 S2 respectivS3 S4).

Grafic, o extensie serial - paralela are forma


48/200

4.2. EXTENSII 49

S1 S2

n1+ n2

n1

n2

m1

m1+ m2

n3

m2

n4

S3 S4

m3 m3+ m4

m4

X1 X2

Y3 Y4

S

Exemplul 4.3 Un circuit combinational care incrementeaza (s= 0) sau decrementeaza(s= 1) un numarx1x0 format din doi biti, poate fi definit astfel:

INC DEC

M U X M U X

x1x0

s

y1 y0

INCR(incrementare),DECR(decrementare),M UX(selectie) sunt circuite combinatio-nale (care vor fi definite mai tarziu), iar circuitul final rezultat prin extensia serial -paralela este evident tot combinational.


49/200


4.3 Cicluri

Pentru cresterea gradului de complexitate al circuitelor digitale se defineste o noua opera-

tie numita ciclu.

Definitia 4.9 Fie sistemul digital S1 = (X X1, Y Y1, h) unde X1 = Y1. Notamh= (f, f1) undef :X X1Y , f1: X X1Y1.

Prin identificarea (conectarea seriala) a luiY1 cuX1 se obtine o ciclu si noul sistemare forma S = (X , Y , g), unde g : X Y este definita g(x) = f(x, f1(x, y)); f1 senumeste functie de tranzitie si verific a definitia recursivay = f1(x, f1(x, y)).

Vom avea deci urmatoarea situatie:

S1

n

m

p

m

X X1

Y Y1

S1

n

p

m

X X1=Y1

Y S

S

n

p

X

Y

Dupa cum se observa n Definitia 4.5, apare o noua variabila ascunsa care ia valori nmultimeaQ= X1=Y1; atunci f :X QY, f1:X QQ.

Multimea Q caracterizeaza comportarea interna a sistemului digital; aceasta com-portare se mai numeste stare internasau pe scurt stare.

Efectul fundamental al comportarii interne consta n evolutia sistemului pe spatiul de

valori Q, fara modificari ale intrarii X.

Pentru una Xaplicat constant la intrare, iesirea poate prezenta diverse variatii. Deaceea, spunem caautonomia unui sistem creste ca urmare a introducerii acestuiantr-o ciclu.

De obicei noile elemente legate de stare sunt introduse n definitia sistemului; astfel,el se va scrie S= (X,Y,Q,f1, g).

Exemplul 4.4 Sa consideram sistemulS1= (XX1, Y , f ) undeX={0, 1}, X1=Y ={0, 1}2, iarfeste definit de tabelul

X X1 Y X X1 Y0 00 01 1 00 010 01 00 1 01 100 10 00 1 10 110 11 10 1 11 00


50/200

4.3. CICLURI 51

Prin identificarea (legarea seriala a) luiY cuX1 se obtine un nou sistemS.Tranzitiile sale sunt ilustrate mai jos (se face abstractie de timpul real cat este aplicat

un semnal la intrare).

S1

2

XX1

Y

S

00 01

1011

0

0, 1

10

1

0

1

Iesirea sistemului S1 este aceeasi cu cea a sistemuluiS.Dupa nchiderea ciclului (X1 = Y), sistemul S1 capata n functie de tranzitie un

comportament al iesirii autonom de intrare.De exemplu, intrarea (constanta) 11111 . . . n sistemul S va determine iesirea ciclica

01 10 11 00 01 . . .

Definitia 4.10 Comportarea unui sistem digital S este autonoma daca si numai dacapentru o intrare constanta, iesirea are un comportament dinamic.

Sa introducem acum notiunea de subciclu.

Definitia 4.11 Un ciclu A este inclus n alt ciclu B daca A apartine unui sistem care

face parte dintr-o extensie seriala nchis a prin ciclulB.Spunem caA este subciclu al luiB.

De exemplu, n figura urmatoare, (1) este subciclu al lui (2).

S1

S2

X

(1)

(2)

Y

Se poate da acum o definitie a sistemelor digitale de ordin n.


51/200


Definitia 4.12 Un sistem de ordinn(n 0) n DSse defineste recursiv astfel:

1. Orice circuit combinational (fara cicluri) este un0 DS.

2. Un(n + 1) DSsistem se obtine dintr-unnDSadaugand un ciclu care includetoate celen cicluri anterioare.

3. Oricen DSse obtine prin aplicarea regulilor anterioare.

De-a lungul acestei carti se va arata urmatoarea corespondenta ierarhica pentru n DS, care corespunde arhitecturii unui calculator:

0 DS: sunt circuite combinationale (fara autonomie);

1 DS

: circuite de memorie (cu autonomie pe spatiul starilor); 2 DS: automate finite (cu autonomie pe tipul de comportare);

3 DS: procesoare (cu autonomie pe interpretarea starilor interne);

4 DS: calculatoare

4.4 Exercitii

1. Construiti circuite care realizeaza portile AND, OR, NOT,N OR si XOR folosind

numai portiNAND.

2. Construiti circuite care realizeaza portileAND,OR, NOT,N ANDsiX ORfolosindnumai portiN OR.

3. Se da circuitul:

abc

x

y

Construiti tabela sa de adevar.


52/200

4.4. EXERCITII 53

4. Se da functia booleana definita prin tabelula 0 0 0 0 1 1 1 1b 0 0 1 1 0 0 1 1

c 0 1 0 1 0 1 0 1f(a,b,c) 0 1 1 1 0 0 1 1

Sa se construiasca un circuit care implementeaza aceasta functie.

5. Construiti un circuit care implementeaza functia booleana

f(a,b,c) =abc + abc + abc

6. Aceeasi problema pentru functia booleana

g(

a,b,c,d,e) =

a(

bc

bc) +

b(

cd

e)

7. Sunt echivalente urmatoarele doua functii booleene ?

f(a,b,c) =abc + abc g(a,b,c) = (a c)b

8. Scrieti o functie booleana descrisa de circuitul urmator:

a

bc

f(a,b,c)

Aranjati raspunsul n forma normal disjunctiva, apoi forma normal conjunctiva.

9. Sa se construiasca un circuit cu doua porti pentru implementarea functiei booleene

f(a, b) =ab + ab


53/200

Capitolul 5

Sisteme 0 DS

Acestea sunt cele mai simple tipuri de sisteme digitale, caracterizate complet prin funct iibooleene.

Astfel, multe functii digitale pot fi generate plecand de la circuitele elementare care lerealizeaza, la care se adauga o regula recursiva (pentru executarea functiei independentde marimea intrarii).

Vom trece n revista cele mai importante sisteme care pot fi descrise n acest mod.

5.1 Decodificatoare

Un sistem digital are drept multime de valori de intrare n-tupluri binare din {0, 1}n.Semnalul care vine printr-un canal fizic trebuie transferat ntai ntr-o astfel de valoare,acceptata de intrarea sistemului.

De aceea, prima problema care trebuie rezolvata este standardizarea si determinareaexacta a semnalului receptionat.

Aceasta este una din principalele functii ale unui sistem digital. Inainte de a generaun raspuns semnalului primit, trebuie sa stim cesemnal s-a primit.

Circuitul care ndeplineste acest deziderat se numeste decodificator.

Cel mai simplu decodificator este decodificatorul elementar (EDCD), care ca scopdeterminarea valorii unui bit.

Schema sa de constructie este data de Figura (a) sau (b), iar reprezentarea simbolica Figura (c) respectiv (d):

55


54/200

56 CAPITOLUL 5. SISTEME0 DS

x0 y0y1

(a)

x0

y1

y0(b)

EDCD

x0

y0 y1

(c)

EDCD

x0

y0 y1

(d)

Decodificatorul elementar a fost obtinut prin extensia paralela a circuitelor care realizeazacele mai simple functii f(x0) = y1 = x0 (functia identica) si g(x0) = y0 = x0 (functiaNOT).

Se observa ca permanent una si numai una din liniile de iesire are valoarea 1 (este

activa): daca este activa iesireay0, atunci intrarea a avut valoarea

0

, iar daca este activaiesirea y1, intrarea a avut valoarea 1.

Determinarea valorii exacte a bitului de intrare x0 se face deci afland ce iesire a de-codificatorului este activa.

Pentru a izola iesirea din canal (sau din alt sistem digital) de intrarea n decodificator(lucru recomandat n practica), ntre cele doua circuite se mai insereaza o poarta logica;cum singurul operator unar utilizat este N OT, el se va adauga printr-o extensie seriala,obtinandu-se un EDCD cu buffer(figura (b)).

In acest fel, comportamentul unui EDCD este protejat de eventuale probleme alecircuitului care asigura intrarea.

Generalizand, obiectivul acestei sectiuni este aceea de a construi un decodificator(DC D) cu n intrari (DCDn) pentru decodificarea semnalelor formate din nbiti.

Ulterior, orice sistem digital va avea intrarea conectata la iesirea unui de-codificator.

Definitia 5.1 UnDCDn este un circuit combinational cu intrareaX={0, 1}n formata

dinn biti(xn1, . . . , x1, x0) si iesireaY reprezentata prinm= 2n bitiym1, . . . , y0.

Fiecare iesire este activa numai pentru o anumita configuratie binara de intrare, si reciproc fiecare configuratie de intrare activeaza un singur bit de iesire.

Structura unui DCDn se defineste recursiv. Astfel:1. Un DCD1 este un EDCD reprezentat n figura (b);

2. Un DCDn (n 2) se obtine combinand un DC Dn1 cu un DCD1 dupa regula dinfigura urmatoare:


55/200

5.1. DECODIFICATOARE 57

. . . . . .

DCDn1

(xn2, . . . , x0)

n1

xn1

y0y1

y2n1

y0 y1 y2n11 y2n1 y2n1

DCDn

Singura dificultate n aceasta constructie consta n adancimea (numarul mare de niveleale) structurii.

In plus, sistemul contine pe aceste nivele un total de 2n + 2n1 +. . .+ 2 = 2n+1 2portiAND (nafara celor 2nportiN OT).

Deci un DCDn construit pe baza definitiei recursive de mai sus, are o complexitateexponentiala.

Ea poate fi micsorata substantial, reducand adancimea decodificatorului, de la ordinulnpana la ordinul 1, pe baza urmatoarei observatii: intrarea n fiecareAN Deste de forma(a); folosind asociativitatea, cele doua componente AND pot fi nlocuite cu una singura,

avand trei intrari, cum este n (b):

x0x1

x2

x0x1x2

y

(b)y

(a)

=

Noul DCD va avea numai n 1 nivele.Procedeul se repeta de nca n 1 ori; n final se obtine un DCDn cu n intrari, 2n

invertoare, 2n iesiri, dar numai 2n portiAND, toate situate pe un singur nivel.


56/200


Exemplul 5.1 Pentrun= 3 vom avea decodificatorulDCD3 cu schema:

y0 y1 y2 y3 y4 y5 y6 y7

000 100 010 110 001 101 011 111

x0

x1

x2

1

01010

Pentru un mesaj de forma 110, intrarea va fi x0 := 1, x1 := 1, x0 := 0. Urmarindcircuitul decodificatorDCD3, se obtiney3= 1 siyi = 0 pentrui= 3.

Ca o remarca, iesirea activa dintr-un DCDn va fi yi daca si numai daca reprezentarea nbinar a lui ieste xn1xn2 . . . x0.


57/200

5.2. CODIFICATORI 59

5.2 Codificatori

Dupa cum s-a vazut, un decodificator sistematizeaza intrarea ntr-un sistem digital.

In particular, el pune o problema sub o forma standard. Raspunsul la aceasta problemaeste generat de un codificator.

Definitia 5.2 Un (2n, p) - codificator este un circuit cu m = 2n intrari dintre care lafiecare moment numai una este activa; pentru fiecare intrare el genereaza o configuratiebinara de lungime p. Circuitul consta din p porti OR sau din p porti NAND, fiecarepoarta avand maximm intrari.

Un codificator nu este definit niciodata independent: intrarile lui sunt de fapt n vari-abile care activeaza un DC Dn, iar cele m = 2

n iesiri ale acestuia reprezinta intrarile ncodificator. Vom completa ulterior Definitia 5.2.

Exemplul 5.2 Un sumator complet este un circuit combinational cun= 3 intrari:

DCD3

CB

A

x2 x1 x0

y0y1y2y3y4y5y6y7

C+ S

A, B sunt numerele (de un bit) care se aduna, iarCeste bitul suplimentar de deplasare(de la nsumarea altor doi biti precedenti). Sunt doua iesiri: S - valoarea sumei binaredintreA siB, siC+ - valoarea noii deplasari.

Pentru constructie vom folosi:- Un decodificatorDCD3 ale carui porti de iesire sunt complementate (n acest exem-plu);

- Un codificator compus din doua portiNAND, fiecare cu cate4 intrari.Deci avem de-a face cu un(8, 2) - codificator. Pentru a vedea cum lucreaza, vom tine

cont de urmatoarea tabela de decodificare:


58/200


y0 y1 y2 y3 y4 y5 y6 y7A x0 0 1 0 1 0 1 0 1B x1 0 0 1 1 0 0 1 1

C x2 0 0 0 0 1 1 1 1

Sa presupunem ca avemA= 1, B= 0, C= 1; aceasta corespunde situatieiy5= 1, yi=0 (i = 5). Deci din DCD3 va iesi y5 = 0, yi = 1. Rezultatele celor doua porti NANDsunt:

S=y1 y2 y4 y7= 1 1 1 1 = 1 = 0

C+=y3 y5 y6 y7= 0 = 1

Intr-adevar, suma1 + 0 + 1 este0, iar transportul1.

Observatia 5.1 In exemplul 5.2, daca iesirile decodificatorului nu ar fi complementate,

atunci codificatorul ar avea porti OR n loc de NAND; aceasta rezulta din relatiile DeMorgan:

p q=p q

In general, operatorul OR corespunde notiunii de codificare iar AND - celei de deco-dificare (OR distruge identitatea componentelor, pe cand AND prefigureaza o anumitaconfiguratie binara).

Daca dorim sa reprezentam toate functiile binare cu 3 intrari si 2 iesiri, vor fi necesaredoua portiNAND cu cel mult opt intrari fiecare.

Cele 216 functii logice posibile vor fi implementate folosind circuitul din Exemplul 5.2n care se pun punctele (conectorii) conform iesirilor din tabela care defineste functialogica respectiva.

Circuitul rezultat poate fi interpretat si ca o memorie fixa.Intr-adevar, daca se considera intrarile drept adrese, atunci la fiecare adresa exista

stocata o anumita valoare binara, conform distributiei conectorilor.Astfel, folosind Exemplul 5.2, la adresa 010 este stocat cuvantul 01, la adresa 110

cuvantul stocat este 10, s.a.m.d.

Acest tip de memorie este numit read only memory(ROM).

Exemplul 5.3 Sa consideram functia booleana cu3 intrari si3 iesiri definit a prin

f(x0, x1, x2) = (x0x1+ x2, (x0+ x1)x2, x0x1+ x1x2+ x2x0).

Tabelul ei de valori va fi


59/200

5.2. CODIFICATORI 61

y0 y1 y2 y3 y4 y5 y6 y7x0 0 1 0 1 0 1 0 1x1 0 0 1 1 0 0 1 1

x2 0 0 0 0 1 1 1 1f1(x0, x1, x2) 1 1 1 1 0 0 0 1f2(x0, x1, x2) 0 0 0 0 0 1 1 1f3(x0, x1, x2) 0 1 1 1 1 1 1 0

unde s-a notatf1(x0, x1, x2) =x0x1+ x2,f2(x0, x1, x2) = (x0+ x1)x2,f3(x0, x1, x2) =x0x1+ x1x2+ x2x0.Functia f(x0, x1, x2) = (f1(x0, x1, x2), f2(x0, x1, x2), f3(x0, x1, x2)) este implementata

de circuitul codificator:

DCD3

y0y1y2y3y4y5y6y7

x2x1x0

f1 f2 f3

Folosind deci astfel de circuite, orice functie booleana f :Vn Vp poate fi implementatade un (2n, p) - codificator.

Prin urmare, codificatorul este un circuit universal, capabil sa implementeze oricefunctie logica.

Cum orice functie logica se poate defini pe baza unei tabele de adev ar, rezulta ca uncircuit ROM este universal.


60/200


5.3 Demultiplexori

Demultiplexorulelementar (EDMUX) permite transferul unui semnalEspre doua desti-

natii distincte (y0 sau y1), conform unei anumite functii de selectiex0.Circuitul asociat acestui deziderat este reprezentat n Figura (a).

In practica, pentru securizarea intrarilor la circuitele driver-ului, schema sa se complicaprin folosirea unui decodificator elementar (EDCD) pentru selectarea celor doua porti siun buffer invertor pentru demultiplexarea intrarii; de asemenea, portileAN D se nlocuiesccu portiNAND.

Se obtine astfel circuitul (b), a carui reprezentare simbolica este (c):

x0

y1=x0E y0=x0E

E

(a)

x0

y0 y1

E

EDCD

(b)

EDMUX

Ex0

y0 y1

(c)

Definitia 5.3 Un demultiplexor cun intrari (DMUXn) transfera semnalul de intrareEla una din cele m= 2n iesiri ym1, . . . , y0, n conformitate cu un codul binar de selectie

xn1, . . . , x0.

O prima solutie pentru implementarea unui demultiplexor consta n generalizarea schemei(b): anume, utilizarea unui decodificator cu n intrari si m= 2n porti NAND, conectateca n figura:

n

DCDn(xn1, . . . , x0)

y0 y1 . . . ym1

E

. . .

y0 y1 ym1


61/200

5.3. DEMULTIPLEXORI 63

Observatia 5.2 A nu se face confuzie de notatie: variabilele yi din interiorul DCDnsunt variabile interne ale acestui circuit. Ele difera calitativ de variabileleyicare formeazaiesirea dinDMUXn.

Deoarece pe nivelul de iesire al unui decodificator se afla porti AND, un procedeu simi-lar cu cel de la decodificatori permite reconstruirea unui DMUX cu m porti NANDcontrolate de n EDCD-uri.

De asemenea, plecand de la definitia recursiva a decodificatorilor, se poate construi odefinitie recursiva si pentru demultiplexori.

Exemplul 5.4 Sa construim un circuitDMUX3.Pentru simplificare, vom renunta la complementarile de securitate.De asemenea, vom combina cele opt portiAND3 de la iesirea dinDC D3 (varianta pe

un singur nivel) cu portileAND dinDMUX, obtinand opt portiAND4, toate situate peun singur nivel.

Cu aceste conventii, structura circuitului este:

y0 y1 y2 y3 y4 y5 y6 y7

x0

x1

x2

E

De exemplu, pentru a trimite semnalul E la adresa y6 se foloseste codul de selectiex2= 1, x1= 1, x0= 0 (deoarece reprezentarea lui6 n binar este110).

In acest fel, iesireay6devine activa si preia semnalulE, iar celelalte iesiri sunt blocatede valoarea 0 emisa deDCD3.


62/200


5.4 Multiplexori

Functia inversa unui DMUX este multiplexarea(M U X): un circuit care aduna ntr-un

singur loc informatia venita din mai multe zone.Ea este de asemenea si o functie de comunicare, asigurand interconectarea dintre

blocuri distincte ale unui sistem digital.Un multiplexor elementar (EM UX) este un selectorcare transmite semnaluli1saui0

spre y, n functie de valoarea codului de selectiex0.Circuitul este prezentat mai jos, unde un EDCD cu intrarea x0 deschide numai una

din cele doua portiAND, nsumate apoi n y printr-o poarta OR:

x0

i0 i1

y= x0i1+ x0i0

EM UX

i1i0

x0

y

Definitia generala a acestui circuit este:

Definitia 5.4 Un multiplexor (M UXn) este un circuit combinational cun biti de control(xn1, . . . , x0), care selecteaza la iesirea y numai o intrare din cele m = 2

n posibilitatiim1, . . . , i1, i0.

DC Dn

(xn1, . . . , x0)

y0

n

y1

ym1

i0 i1

. . .

im1

y


63/200

5.4. MULTIPLEXORI 65

O implementare posibila foloseste un DCDn legat serial cu o structura AND OR, can figura anterioara.

Iesirea din decodificator activeaza numai o poarta AND, care transfera la iesire in-

trarea selectata.Acestui circuit i se poate aplica proprietatea de asociativitate ntre portile AND ale

iesirilor din decodificator si portile AND suplimentare (ca la DCD-uri).

Se poate da si o definitie recursiva a unui multiplexor, de complexitate mult redusa:

Definitia 5.5 M U Xn poate fi construit printr-o conectare serial a a unui EM UX cudouaM U Xn1 conectate paralel; n plus, M UX1=EM UX.

M UXn1 M U Xn1

EM UX

n1

n1

(xn2, . . . , x0)

i0 . . . im/21 im/2 . . . im1

i0 . . . im/21 i0 . . . im/21

y y

xn1 x0

i0 i1

y

y

Desi un multiplexor este (prin definitie) un circuit de selectie, el poate fi utilizat si pentrurealizarea unor functii booleene.

Astfel, sa consideram xn1 . . . , x0ca variabile booleene de intrar

Arhitectura Sistemelor de Calcul (Adrian Atanasiu)

Documents

Transcript of Arhitectura Sistemelor de Calcul (Adrian Atanasiu)