laborator AC

2014/10/15 00:48 1/16 Laboratorul 0 - Recapitulare

AC Wiki - https://elf.cs.pub.ro/ac/wiki/

Laboratorul 0 - Recapitulare

Circuite combinaionale

Circuitele logice combinaionale aplic funcii logice pe intrri pentru a obine ieirile. Valorile deieire depind astfel doar de valorile de intrare, iar cnd starea unei intrri se schimb, se reflectimediat pe ieiri.

Fig. 1: Diagrama bloc pentru un circuit combinaional cu n intrri i m ieiri

Logica combinaional poate fi reprezentat prin:

diagrame structurale la nivel de pori logiceltabele de adevrlexpresii boolene (funcii logice)l

Circuitele combinaionale sunt folosite n procesoare n cadrul componentelor de calcul, iar cele maides ntlnite sunt:

multiplexoarele i demultiplexoarelelcodificatoarele i decodificatoarelelsumatoarelelcomparatoarelelmemoriile ROM (read-only, nu pstreaz stare)l

Un exemplu de folosire a sumatoarelor este n cadrul Unitilor Aritmetice-Logice (UAL) din interiorulprocesoarelor.

Pori logice

Porile logice reprezint componentele de baz disponibile n realizarea circuitelor combinaionale. Eleoglindesc operaiile din algebra boolean, algebr care st la baza teoriei circuitelor combinaionale.n Tab. 1 sunt prezentate cele mai ntlnite pori logice mpreun cu operaia boolean pe care oimplementeaz.

Denumire Simbol Operator Tabel de adevr

Last update: 2014/10/14 22:13 lab:lab00 https://elf.cs.pub.ro/ac/wiki/lab/lab00

https://elf.cs.pub.ro/ac/wiki/ Printed on 2014/10/15 00:48

Inversor (NOT) f = !aa f0 11 0

Poarta SAU(OR) f = a || b

a b f0 0 00 1 11 0 11 1 1

Poarta I(AND) f = a && b

a b f0 0 00 1 01 0 01 1 1

PoartaSAU-NU(NOR)

f = !(a || b)

a b f0 0 10 1 01 0 01 1 0

PoartaI-NU(NAND)

f = !(a && b)

a b f0 0 10 1 11 0 11 1 0

PoartaSAU EXCLUSIV

(XOR)f = a ^ b

a b f0 0 00 1 11 0 11 1 0

PoartaSAU EXCLUSIV NU

(XNOR)f = !(a ^ b)

a b f0 0 10 1 01 0 01 1 1

Tab. 1: Porile logice de baz

Sumatorul elementar

Sumatoarele (adders), folosite cel mai mult n unitile aritmetice logice ale procesoarelor, realizeazadunri pe un numr dat de bii, furniznd la ieirea circuitului suma i transportul (carry) rezultat nurma operaiei.

Exist mai multe tipuri de sumatoare pentru adunarea numerelor pe n bii, iar acestea se bazeaz pesumatoare simple de 1 bit, care pot fi de dou tipuri:

sumatorul elementar parial (Half adder) - nsumeaz doi operanzi pe 1 bit i ofer la ieire sumalacestora i transportul.



sumatorul elementar complet (Full adder) - nsumeaz doi operanzi pe 1 bit i un transport i oferlla ieire suma acestora i transportul.

Fig. 2: Diagrama bloc pentru half adder

Fig. 3: Diagrama bloc pentru fulladder

Sumatorul elementar parial

Acest sumator este n continuare descris prin expresiile boolene, tabelul de adevr i schema logic.

Inputs Outputsa b sum c_out0 0 0 00 1 1 01 0 1 01 1 0 1

Tab. 2: Tabelul de adevr pentru half adder

Din tabelul de adevr se pot deduce urmtoarele formule:

sum = a ^ bc_out = a && b

Conform acestor formule putem exprima circuitul prin pori logice, ca n Fig. 4:

Fig. 4: Schema logic pentru half adder Despre tabele de adevr i deducerea expresiilor boolene (click aici)



Dintr-un tabel de adevr, pentru fiecare output se va deduce o funcie/expresie aplicnd urmtoarelereguli:

se ia fiecare rnd pentru care funcia are valoarea 1, care va forma un termen1.termenii sunt formai din parametrii funciei legai prin I2.dac parametrul are valoarea 1 se consider n form direct3.dac parametrul are valoarea 0 se consider n form negat4.se aplic SAU ntre toi termenii dedui5.

Pentru sumatorului elementar parial avem:

n multe cazuri aceste formule sunt prea complexe, coninnd multe operaii i necesitnd multepori logice pentru a fi implementate. Pentru a reduce complexitatea formulelor rezultate se poateaplica un procedeu de minimizare. Minimizarea se poate realiza folosind teoremele algebrei boolene,prin reducerea dimensiunii termenilor sau chiar eliminarea lor, sau grafic, prin diagrame Karnaugh.

Sumatorul elementar complet

Inputs Outputsa b c_in sum c_out0 0 0 0 00 1 0 1 01 0 0 1 01 1 0 0 10 0 1 1 00 1 1 0 11 0 1 0 11 1 1 1 1Tab. 3: Tabelul de adevr pentru full adder

Din tabelul de adevr se pot deduce urmtoarele formule:

sum = a ^ b ^ c_inc_out = ((a ^ b) && c_in) || (a && b)

Conform acestor formule putem exprima circuitul prin pori logice sau putem folosi sumatoareelementare pariale, ca n Fig. 5:



Fig. 5: Schema logic pentru full adder Codul C pentru full adder

void full_adder(int a, int b, int c_in, // inputs int *sum, int *c_out) // outputs{ *sum = a ^ b ^ c_in; *c_out = ((a ^ b) && c_in) || (a && b);}

Multiplexorul 4:1

Un multiplexor digital este un circuit combinaional care implementeaz o funcie de selecie a uneiadintre intrrile sale.

intrril intrri de seleciel

o ieirel

Fig. 6: Diagrama bloc a multiplexorului 4:1



Fig. 7: Schema logic amultiplexorului 4:1

Alegerea semnalului de ieire se face pe baza intrrilor de selecie, care reprezint n baza 2 numrulintrrii ce trebuie selectate. n exemplul din Fig. 6 avem schema bloc a unui multiplexor cu 4 intrri,iar acesta are nevoie de dou intrri de selecie. Circuitului din imagine i se mai pot aduga o intrarede activare (EN - enable) i o ieire inversat.

Funcia invers a multiplexorului este realizat de ctre circuitele de demultiplexare, care preiau unsemnal de intrare i folosesc intrrile de selecie pentru a-l transmite pe una din ieirile posibile.

S2 S1 out0 0 I10 1 I21 0 I31 1 I4Tab. 4: Selecia intrrilor

Deoarece multiplexorul 4:1 are 6 intrri, tabelul de adevr devine destul de mare i nu mai esteindicat de pornit de la acesta pentru obinerea funciei logice. Din descrierea funcionrii circuitului (Tab. 4) i proprietile porii AND, putem deduce termenii formulei:

Conform formulei se poate realiza circuitul cu pori logice din Fig. 7.

Codul C pentru un multiplexor 4:1

Multiplexor 4:1

void mux41(int s1, int s2, // selection inputs int i1, int i2, int i3, int i4, // inputs int *out) // output



{ switch((s2



Fig. 9: Schema sumatorului cu transport succesiv, pe 16 bii

Dei are un design simplu, dezavantajul acestui sumator este c este lent, fiecare sumator elementarateptnd transportul de la sumatorul precedent. Exist alte sumatoare, cum ar fi cel cu transportanticipat (eng. carry-lookahead adder), care ofer o funcionare mai rapid, eliminnd ateptareapropagrii transportului.

Circuite secveniale

Spre deosebire de circuitele logice combinaionale, cele secveniale (eng: sequential logic) nu maidepind exclusiv de valoarea curent a intrrilor, ci i de strile anterioare ale circuitului.

Logica secvenial poate fi de dou tipuri: sincron i asincron. n primul caz, cel cu care vom lucrai la laborator, este folosit un semnal de ceas care comand elementul/elementele de memorare,acestea schimbndu-i starea doar la impulsurile de ceas. n al doilea caz, ieirile se modific atuncicnd se modific i intrrile, neexistnd un semnal de ceas pentru elementele de memorare.Circuitele secveniale asincrone sunt mai greu de proiectat, pot aprea probleme de sincronizare isunt folosite mai rar.

n continuare ne vom referi doar la circuitele secveniale sincrone.

Fig. 10: Schema bloc a unui circuit secvenial sincron



Bistabilul D

Elementele de memorare din circuitele secveniale pot fi implementate prin bistabile (eng. flip-flops).Acestea stocheaz valori n funcie de valoarea de la intrare i de semnalul de ceas. Valoarea stocatpoate fi schimbat doar atunci cnd ceasul realizeaz o tranziie activ (un semnal de ceas poate fiactiv pe front cresctor (eng. rising edge) sau pe front descresctor (eng. falling edge)).

Exist 4 tipuri principale de bistabile: D, T, SR i JK, iar n acest laborator ne vom axa pe bistabilul D.Acesta are un design simplu i este folosit n general pentru implementarea registrelor din procesoare(cea mai mic i mai rapid unitate de stocare din ierarhia de memorie).

Fig. 11: Diagrama bloc pentru bistabilul D

Intrrile i ieirile circuitului sunt:

D - valoarea (data) de stocatlclk - semnalul de ceas, considerat activ pe front cresctor n descrierile urmtoarelQ - starea curentl!Q - starea curent negatl

Ca mod de funcionare, ecuaia caracteristic a sa este Qnext = D, adic starea urmtoare (Qnext)a bistabilului depinde doar de intrarea D, fiind independent de starea curent (Q), dup cum seobserv i din Tab. 5.

D Q Qnext0 0 00 1 01 0 11 1 1Tab. 5: Tabelul de tranziii pentru bistabilul D

Pentru a nelege mai uor comportamentul bistabilelor, pe lang tabelele de tranziii mai sunt utile idiagramele de semnale (eng. timing diagrams), cum este cea din Fig. 12, unde se poate observa cumieirea Q se schimb doar pe frontul cresctor de ceas i devine egal cu intrarea D n momentultranziiei ceasului.



Fig. 12: Diagrama de semnale pentru bistabilul D

Automate finite

Prin automate finite (eng. Finite-state machine - FSM) nelegem de fapt un circuit secvenial sincronaa cum a fost el descris anterior. De obicei, proiectarea unui automat finit pornete de la o descriereinformal a modului n care automatul trebuie s funcioneze. Primul pas n realizarea automatuluieste descrierea formal a funcionrii acestuia. Dou dintre metodele prin care un automat finit poatefi descris sistematic sunt:

Diagrama de stri (Fig. 13) prezint ntr-un mod grafic funcionarea unui automat finit. Strilelautomatului sunt reprezentate prin noduri, iar tranziiile sunt reprezentate prin arce ntre stareasurs i starea destinaie. Fiecare arc este marcat cu condiia necesar pentru a fi efectuat otranziie. De asemenea, eventualele semnale de ieire ale automatului sunt marcate n dreptulstrilor care genereaz acele ieiri.

Fig. 13: Exemplu de diagram de stri

Starea curent x y Starea urmtoareS0 1 0 S1S1 0 1 S0

Tab. 6: Exemplu de tabel de tranziii Tabelul de tranziii (Tab. 6) prezint funcionarea unui automat finit sub form de tabel. Fiecarelrnd al tabelului reprezint o tranziie a automatului i conine starea curent, starea urmtoare iintrrile necesare pentru a activa tranziia.

n continuare vom proiecta dou automate finite simple:

Recunoaterea secvenei "ba"

Se dorete proiectarea unui automat finit capabil s recunoasc secvena ba. Automatul primete laintrare n mod continuu caractere codificate printr-un semnal de un bit (caracterele posibile sunt ai b). Ieirea automatului va consta dintr-un semnal care va fi activat (valoarea 1) atunci cnd laintrare am avut prezent irul ba.

Click pentru rezolvare

Vom ncepe proiectarea automatului prin identificarea intrrilor i ieirilor. Din descriere observm cintrarea este format dintr-un singur semnal de 1 bit (automatul va avea i o intrare de ceas, nsaceasta nu este considerat intrare propriu zis de date). Deoarece codificarea caracterelor nu estespecificat vom presupune c valoarea 0 indic un caracter a, iar valoarea 1 indic un caracter b.Ieirea este format deasemenea dintr-un semnal de 1 bit cu valoarea 1 atunci cnd secvena



cutat a fost gsit i 0 n rest.

Vom realiza n continuare diagrama de stri a automatului. La pornire, vom initializa automatul ntr-ostare pe care o vom numi S0. Dac la prima tranziie de ceas intrarea are valoarea:

0 (caracterul a) - vom avansa ntr-o stare pe care o vom numi Sa care ne spune c intrarealprecedent a fost a1 (caracterul b) - vom avansa ntr-o stare pe care o vom numi Sb care ne spune c intrarealprecedent a fost b

n continuare vom analiza ce se ntmpl atunci cnd automatul este n starea Sa. Dac la intrareavem valoarea:

0 (caracterul a) - automatul va rmne n acest stare, care ne spune c intrarea precedent alfost a1 (caracterul b) - automatul va trece n Sb, care ne spune c intrarea precedent a fost bl

Dac ne aflm n starea Sb i automatul primete la intrare valoarea:

0 (caracterul a) - automatul a ntlnit secvena dorit ba (fiind n starea Sb intrarea precedentla fost b, iar intrarea curent este a); vom avansa ntr-o stare pe care o vom numi SA n carevom activa ieirea automatului; de asemenea, aceast stare ne spune i c intrarea precedent afost a, lucru folosit pentru a putea recunoate i urmtoarele secvene ba care vor mai fintlnite la intrare1 (caracterul b) - automatul va rmne n aceast stare, care ne spune c intrarea precedent alfost b

Dac ne aflm n starea SA i automatul primete la intrare valoarea:

0 (caracterul a) - automatul va trece n starea Sa care ne spune c intrarea precedent a fost a,lns nu vom activa ieirea automatului deoarece automatul nu a vzut i caracterul b1 (caracterul b) - automatul va trece n starea Sb care ne spune cp intrarea precedent a fost bl

n momentul de fa comportamentul automatului a fost descris complet, toate cele 4 striidentificate avnd definite tranziiile pentru toate combinaiile semnalelor de intrare. Fig. 14 prezintdiagrama de stri a automatului.



Fig. 14: Automatul de recunoatere a secvenei "ba"

O dat determinat diagrama de stri a automatului, putem trece la implementarea acestuia ntr-unlimbaj cunoscut (C/C++/C#/Java):

Automatul de recunoatere a secvenei "ba"

void FSM_ba(int in, // FSM input: 0 - a, 1 - b int out) { // FSM output: 0 - not found, 1 - found int state = 0; // FSM state: 0 - S0, 1 - Sa, 2 - Sb, 3 - SA while(1) { switch(state) { case 0: out = 0; break; case 1: out = 0; break; case 2: out = 0; break; case 3: out = 1; break: } read_inputs(); switch(state) {



case 0: if(in == 0) state = 1; else state = 2; break; case 1: if(in == 0) state = 1; else state = 2; break; case 2: if(in == 0) state = 3; else state = 2; break; case 3: if(in = 0) state = 1; else state = 2: break: }}

Trecere de pietoni semaforizat

Se dorete realizarea unei treceri de pietoni semaforizate. Duratele de timp pentru cele 2 culori vor fi:rou - 60 sec, verde - 30 sec.

Click pentru rezolvare

Vom ncepe proiectarea automatului prin identificarea intrrilor i ieirilor. Deoarece descriereainformal nu conine informaii despre intrrile i ieirile necesare vom folosi oricte intrri i ieiriavem nevoie pentru implementarea comportamentului. Un minim de ieiri pentru automat reprezintsemnalele de comand pentru culorile semaforului pentru pietoni i pentru maini. Cele 5 semnalevor fi:

p_rosu - aprindere culoare roie pentru pietonilp_verde - aprindere culoare verde pentru pietonilm_rosu - aprindere culoare roie pentru mainilm_galben - aprindere culoare galben pentru mainil



m_verde - aprindere culoare verde pentru mainil

Pentru a msura duratele de timp am putea folosi semnalul de ceas al automatului, introducndmultiple stri cu tranziii necondiionate, n care o culoare a semaforului este inut aprins. Avnd nvedere ns c semnalul de ceas pentru un automat are o perioad de ceas mic (



int p_verde, int m_rosu, int m_galben, int m_verde) { int state = 0; // FSM state: 0 - m_verde, 1 - m_galben,2 - m_rosu while(1) { read_inputs(); p_rosu = 0; p_verde = 0; m_rosu = 0; m_galben = 0; m_verde = 0; switch(state) { case 0: p_rosu = 1; m_verde = 1; T = 50; if(done == 1) state = 1; else state = 0; break; case 1: p_rosu = 1; m_galben = 1; T = 10; if(done == 1) state = 2; else state = 1; break; case 2: p_verde = 1; m_rosu = 1; T = 30; if(done == 1) state = 0; else state = 2; break; }}



Resurse

PDF laborator

From:https://elf.cs.pub.ro/ac/wiki/ - AC Wiki

Permanent link:https://elf.cs.pub.ro/ac/wiki/lab/lab00

Last update: 2014/10/14 22:13

Laboratorul 0 - RecapitulareCircuite combinaionalePori logiceSumatorul elementarSumatorul elementar parialSumatorul elementar complet

Multiplexorul 4:1Sumatorul cu transport succesiv

Circuite secvenialeBistabilul DAutomate finiteRecunoaterea secvenei "ba"Trecere de pietoni semaforizat

Resurse

laborator AC

Documents

Transcript of laborator AC