Cenni alle reti logiche - dit.unitn.itpalopoli/courses/Calc/CalcLect3.pdf · Cosa sono le reti...
Transcript of Cenni alle reti logiche - dit.unitn.itpalopoli/courses/Calc/CalcLect3.pdf · Cosa sono le reti...
Cosa sono le reti logiche?
• Fino ad ora abbiamo visto § Rappresentazione dell’informazione § Assembler
• L’obbie:vo di questo corso è mostrare come si proge>o una computer
• Quindi abbiamo adesso bisogno di fare una piccola digressione su come si proge>ano I circuiA logici
• Avremo un corso specifico su questo…..
Valori logici
• I computer moderni sono realizzaA tramite circuiA ele>ronici
• Tra>andosi di elemenA digitali avremo due livelli fondamentali § Alto, Asserito (1): associato alla tensione di alimentazione Vdd
§ Basso, negato (0): associato alla massa (tensione = 0)
• Altri livelli di tensione sono non significaAvi e assunA solo in fase transitoria
Reti logiche
• Le porte logiche sono dei circuiA che trasformano alcuni valori logici in ingresso in altri valori logici in uscita
• Le porte logiche sono di due Api § Combinatorie
ü Relazione funzionale tra ingresso e uscita ü Non hanno memoria ü L’uscita dipende solo dal valore dell’ingresso
§ Sequenziali ü L’uscita dipende dalla storia degli ingressi passaA e non solo dal valore a>uale
ü Hanno memoria (de>a anche stato della rete)
Tabella di verità
• Una possibile maniera di specificare una rete logica combinatoria è tramite una tabella di verità che elenca I valori delle uscite in corrispondenza dei vari ingressi
INPUT OUTPUT
A B C D E F
0 0 0 0 0 0
0 0 1 1 0 0
0 1 0 1 0 0
0 1 1 1 1 0
1 0 0 1 0 0
1 0 1 1 1 0
1 1 0 1 1 0
1 1 1 1 0 1
Algebra di boole
• Una maniera più compa>a è di specificare le funzioni logiche combinatorie tramite espressioni algebriche definite con l’algebra di boole
• Esistono tre operatori di base § AND
ü viene rappresentato tramite il simbolo di prodo>o. Esempio A•B. ü Produce 1 se entrambi gli operandi sono uno e zero negli altri casi
§ OR ü rappresentato tramite il simbolo della somma (+). Esempio A+B ü Produce zero se e solo se entrambi gli operandi sono 0
§ Not ü Rappresentato da una barra. Esempio: Ā ü Ha l’effe>o di inverAre il valore logico
Algebra di Boole
• Ci sono una serie di regole che ci perme>ono di manipolare facilmente le espressioni logiche § IdenAtà: A+0=A, A•1=A § Regola zero e uno: A + 1 = 1, A•0=0 § Regola dell’inversa A + Ā=1, A•Ā=0 § Regola commutaAva: A+B=B+A, A•B=B•A § Regola AssociaAva: A+(B+C)=(A+B)+C, A•(B•C)=(A•B)•C
§ Regola distribuAva: A•(B+C)=(A•B)+(A•C), A+B•C=(A+B)(A+C)
Algebra di Boole
• In più esistono dure regole molto importanA, de>e di De Morgan
• Queste leggi ci dicono che se abbiamo una nand, o una nor tu: gli altri operatori logici si possono ricavare
A ·B = A+B
A+B = A ·B
Algebra di Boole Esempio
• Torniamo alla nostra tabella
INPUT OUTPUT
A B C D E F
0 0 0 0 0 0
0 0 1 1 0 0
0 1 0 1 0 0
0 1 1 1 1 0
1 0 0 1 0 0
1 0 1 1 1 0
1 1 0 1 1 0
1 1 1 1 0 1
• Possiamo vedere facilmente D = A+B + C
F = A ·B · C
Algebra di Boole - Esempio
• Torniamo alla nostra tabella
INPUT OUTPUT
A B C D E F
0 0 0 0 0 0
0 0 1 1 0 0
0 1 0 1 0 0
0 1 1 1 1 0
1 0 0 1 0 0
1 0 1 1 1 0
1 1 0 1 1 0
1 1 1 1 0 1
E vale 1: § Se A=1, B=1, C=0 oppure
§ Se A=1, C=1 B = 0 oppure
§ Se B=1, C=1, A= 0
E = (A ·B · C) + (A · C ·B) + (B · C ·A)
E = (A+B + C) · (A+ C +B) · (B + C +A)
• O usando De Morgan
Porte logiche
• In realtà esistono dei circuiA ele>ronici (porte logiche) che mi implementano gli operatori booleani fondamentali
AND OR NOT
Porte logiche
• Le porte si possono combinare tra di loro (con il not che può essere semplificato tramite un cerchio)
A+B
Alcuni circuiti
• MulAplexor
• Deviatore che sulla base di un input di controllo, determina quale degli input passa.
Forme canonica SP
• Abbiamo visto che Arare fuori un’espressione logica da una tabella di verità è semplice
• Basta prendere ciascuna riga uguale a 1 e scrivere un termine di prodo>o logico de>ato dalla configurazione degli ingressi
• A quel punto si può fare la somma di tu: I prodo: individuaA
Altro esempio
• Consideriamo come ulteriore esempio:
INPUT OUTPUT A B C D 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1
D = (A ·B · C) + (A ·B · C) + (A ·B · C) + (A ·B · C)
PLA
• La stru>ura che abbiamo visto si compone di due stadi: la prima è una barriera di AND (cde: anche mintermini) e una barriera di OR
• La dimensione totale del PLA è data dalla somma di Piano AND (numero di mintermini e loro complessità) e del piano OR (Numero di uscite)
• Cara>erisAche importanA: § Ci sono porte logiche solo per le configurazione che prudcono 1
§ Se un mintermine è condiviso tra varei uscita, basta una sola entry
Esempio • Ritorniamo all’esempio
INPUT OUTPUT
A B C D E F
0 0 0 0 0 0
0 0 1 1 0 0
0 1 0 1 0 0
0 1 1 1 1 0
1 0 0 1 0 0
1 0 1 1 1 0
1 1 0 1 1 0
1 1 1 1 0 1
Esempio • Implementazione tramite porte logiche
D = A+B + C
F = A ·B · CE = (A ·B · C) + (A · C ·B) + (B · C ·A)
Esempio • Una diversa rappresentazione (usando i punA nei piani and e or)
D = A+B + C
F = A ·B · CE = (A ·B · C) + (A · C ·B) + (B · C ·A)
Costo
• Le funzioni logiche possono essere implementate in maniera diversa (più o meno efficiente)
• Per COSTO di una rete logica si intende normalmente la somma del numero di porte e del numero di ingressi della rete (indipendentemente dal fa>o che siano posiAvi o negaA)
• E’ possibile trovare delle implementazioni di una rete che hanno cosA diversi
Minimizzazione di funzioni logiche
• La minimizzazione di alcune espressioni logiche è banale, in altri casi è necessario applicare le regole algebriche in modo “furbo”
• Es. f(x1, x2, x3) = x1x2x3 + x1x2x3 + x1x2x3 + x1x2x3
= x1x2(x3 + x3) + x1x2(x3 + x3)
= x1x2 + x1x2
= (x1 + x1)x2
= x2
Minimizzazione
• Esistono metodi di minimizzazione sistemaAci basaA sull’applicazione iteraAva di queste regole
• Altri metodi sono basaA su rappresentazioni grafiche (mappe di Karnaugh), ma si applicano solo a casi più semplici
• Questo argomento si chiama “sintesi logica” e per gli interessaA è coperto nel corso di reA logiche
Array di elementi logici
• Molto spesso si costruiscono array di elemenA che operano su daA complessi
• Ad esempio come realizzare un mulAplexer che opera su un bus a 32 bit uAlizzando elemenA a un bit
• BUS: insieme di file (ad esempio 32) che viene visto come un singolo segnale logico