Circuiti Logici - math.unipd.itaceccato/Intro_2011_2012/... · 12 • Le operazioni AND e OR sono...
Transcript of Circuiti Logici - math.unipd.itaceccato/Intro_2011_2012/... · 12 • Le operazioni AND e OR sono...
Circuiti Logici
Pagina web del corso: http://www.math.unipd.it/~aceccato
Macchina hardware e macchina software
Agli albori il computer era essenzialmente una CPU collegata ad una piccola RAM
Ogni istruzione codificata in linguaggio macchina
La sequenza in binario direttamente nella RAM
Programmi che risiedono nel computer stesso e facilitano il suo uso (il più importante è il SISTEMA OPERATIVO)
ORA
macchina hardware
macchina software
utente
traduce per noi in linguaggio macchina
Agli albori dell'informatica, l’utente programmava in binario (Ling.Mac.) scrivendo i programmi nella RAM
Macchina hardware e macchina software
Sistema Operativo: coordina tra loro le varie parti della macchina, facilita l'inserimento di dati e programmi (risiede sia in piccola parte nella ROM che nella memoria secondaria)
ATTENZIONE: la CPU di un computer può eseguire solo istruzioni in linguaggio macchina
Linguaggi di programmazione ad alto livello
Compilatori: programmi che traducono i programmi scritti con linguaggi di programmazione ad alto livello in linguaggio macchina
Macchina hardware e macchina software
MacchinaHardware
Sistema Operativo
Compilatori ed applicativi diversi
Hardware
Filosofia di costruzione
"tante componenti semplici, se ben organizzate, possono realizzare funzionalita` complesse"
L’ Hardware di un computer
•Hardware = insieme dei circuiti elettronici
•Tali circuiti sono ottenuti assemblando un gran numero di componenti elementari dette “porte”
•Relazione tra circuiti elementari e operazioni logiche
• 3 tipi di circuito fondamentali: and, or, not
and, or, not
Operazione logica: operazione che agisce sui valori di verita’ vero e falso: dati due valori di verita’ come operandi ritorna un
valore di verita’ come risultato
And: operazione binaria; il risultato e’ vero solo se entrambi gli operandi sono veri
Or: operazione binaria; il risultato e’ vero solo se uno degli operandi e’ vero
Not: operazione unaria; il risultato e’ vero solo se l’operando e’ falso
Porte logiche
IDEA: identificare il valore di verità FALSO con 0 (assenza di corrente)
Identificare il valore di verità VERO con 1 (presenza di corrente)
1010
L’algebra di BooleL’algebra di Boole
1111
• Contempla due costanti 00 e 11 (falsofalso e verovero)• Corrispondono a due stati che si escludono a vicenda• Possono descrivere lo stato di apertura o chiusura di
un generico contatto o di un circuito a più contatti
• Sui valori booleani si definiscono le operazioniANDAND, OROR, NOTNOT
0 1
George Boole (1810-1864) George Boole (1810-1864) L’algebra di Boole L’algebra di Boole −− 1 1
1212
• Le operazioni AND e OR sono operazioni binarie, l’operazione NOT è unaria
• Nella valutazione delle espressioni booleane esiste una relazione di precedenza fra gli operatori NOT, AND e OR, nell’ordine in cui sono stati elencati
• Gli operatori dell’algebra booleana possono essere rappresentati in vari modi
Spesso sono descritti semplicemente come AND, OR e NOT
Nella descrizione dei circuiti appaiono sotto forma di porte logicheporte logiche
In matematica si usano + per OR e × per AND, mentre si rappresenta il NOT con una barra posta sopra l’espressione che viene negata
L’algebra di Boole L’algebra di Boole −− 2 2
Completezza di and, or, e not
16 operazioni logiche binarie (tante quante possibili scelte di 4 valori nella colonna dei risultati)
2 operazioni logiche unarie
Tutte possono essere ottenute componendo and, or, e not
1414
• Si definisce l’operazione di somma logicasomma logica (OR):il valore della somma logica è il simbolo 1 se il valore di almeno uno degli operandi è il simbolo 1
0+0 = 00+1 = 11+0 = 11+1 = 1
0
0
0
1
0+0 0+11
1
1
0
1+0 1+1
L’operazione di OR L’operazione di OR
1515
• Si definisce l’operazione di prodotto logicoprodotto logico (AND):il valore del prodotto logico è il simbolo 1 se il valore di tutti gli operandi è il simbolo 1
0×0 = 00×1 = 01×0 = 01×1 = 1
11
1×1
01
1×0
10
0×1
00
0×0
L’operazione di ANDL’operazione di AND
1616
• Si definisce l’operatore di negazionenegazione (NOT):l’operatore inverte il valore della costante su cui opera
• Dalla definizione…
0 = 11 = 0
La negazione NOT La negazione NOT
0 = 0 1 = 1
⇒ A B A ⇒ Bfalso falso verofalso vero verovero falso falsovero vero vero
A B A ⇒ B0 0 10 1 11 0 01 1 1
R B
A
A ⇒ B equivale a (NOT A) OR B A B NOT A (NOT A) OR B0 0 1 10 1 1 11 0 0 01 1 0 1
EQUIVALENZA
≡A B A ≡ B0 0 10 1 01 0 01 1 1
B
A
R
A ≡ B equivale a (A ⇒ B) AND (B ⇒ A)
A B A ⇒ B B ⇒ A (A ⇒ B)AND(B ⇒ A)0 0 1 1 10 1 1 0 01 0 0 1 01 1 1 1 1
Tavole di verità e circuiti
- Dato un qualsiasi circuito e’ sempre possibiledefinire la tavola di verita’ (in un solo modo)
- Data una tavola di verita’ si possono costruirein generale piu’ circuiti che la realizzano
Dal circuito alla tavola di verità
- Modo 1) Si calcola, per ogni possibileconfigurazione degli ingressi, l’uscitadelle porte fino alle uscite del circuito
- Modo 2) Si calcola la formula logicacorrispondente al circuito e si calcolanole tabelle di verita’ partendo dalleformule intermedie piu’ semplici fino allaformula data
Dalla tabella di verita’ ad un circuito Tanti input quante sono le dimensioni della tabella Un solo output Un or la cui uscita e’ l’output Tanti and quanti sono gli 1 della tabella Input degli and: 1 se diretto, 0 se negato
A B A ≠ B0 0 0
0 1 11 0 11 1 0
B
A
R
!!! Chiaramente il circuito cosi’ costruito nonnecessariamente e’ il piu’ semplice (ovvero con ilminor numero possibile di porte logiche utilizzate)
Nand e nor
Non servono tre operazioni (and, or, not)
Basta una tra :
nand (not and) e nor (not or)
NAND NOR A B A NAND Bfalso falso verofalso vero verovero falso verovero vero falso
A B A NOR Bfalso falso verofalso vero falsovero falso falsovero vero falso
10 1
01 111 0
10 0RA B
00 1
01 101 0
10 0RA B
A
B R
R A
B
NAND e NOR
Una CPU si puo` realizzare stampando su siliciouna griglia di milioni di porte logiche tutte uguali:NAND o NOR.
I vantaggi dell'architettura NOR sono un'elevataaffidabilità nel tempo ed un veloce accesso inlettura.Le memorie NAND, hanno in genere densità piùelevate e migliori velocità in scrittura.
AND
OR
A R
NOT
A R
B
R
B
A
A nand A (A nand B) nand (A nand B)
(B nand B) nand (A nand A)
Esercizio 1 (formule)
Quale e’ la tavola di verita’ della formula (not(A) B) OR NOT(A) ?
A B Not(A) R
0
0
1
1
0
1
0
1
1
1
0
0
1
1
1
1
Not(A)B
0
1
1
1
Esercizio 2 (formule)
Quale e’ la tavola di verita’ della formula A or (A and not(B)) ?
A B A and not(B)Not(B) R
0
0
1
1
0
1
0
1
1
0
1
0
0
0
1
0
0
0
1
1
Esercizio 3 (circuiti)
Si disegni un circuito logico che realizza la seguente tavola di verita’:
29
A B R0 0 00 1 11 0 11 1 0
B
A
R
Dare la tavola di verita’ della formula(NOT(A) NOT(B)) OR (NOT(A) AND B)NOT(A) NOT(B) = NOT(NOT(A)) or NOT(B)==A or NOT(B)(A or NOT(B)) OR (NOT(A) and B)
A B A or not(B)Not(A) R
0
0
1
1
0
1
0
1
1
1
0
0
1
0
1
1
1
1
1
1
Not(B) Not(A) and B
1
0
1
0
0
1
0
0
Esercizio 4
Circuito (NOT(A) NOT(B)) OR (NOT(A) AND B)
Esercizio 4
or
R
AB
and
and
and
or
orand
...due aspetti...
Le formule logiche si possono utilizzare per formalizzare asserzioni anche molto complesse
Si possono comporre circuiti semplici per ottenenere circuiti che realizzano nuove operazioni piu`complesse
Esempio 1 Siccome un rettangolo è un quadrato se ha altezza
uguale alla base allora un rettangolo che non è un quadrato non ha altezza uguale alla base
Formalizzazione:A=”è un quadrato”B=”ha altezza uguale alla base”
(B==>A) ==> (NOT A ==> NOT B)
Tabella di verità 1
A B B==> A NOT A ==> NOT B
F
0 0 1 1 11 0 1 1 10 1 0 0 11 1 1 1 1
Esempio 2 Il professore non è contento se gli studenti
disturbano, allora se il professore non è contento gli studenti disturbano
Formalizzazione:A=”il prof è contento”B=”gli studenti disturbano”
(B==>NOT A) ==> (NOT A ==> B)
Tabella di verità 2
A B NOT A NOT B B ==> NOT A NOT A ==>B (B==>NOT A) ==>(NOT A ==>B)
0 0 1 1 1 0 0
0 1 1 0 1 1 1
1 0 0 1 1 1 1
1 1 0 0 0 1 1
Alcune definizioni...
Formula SODDISFACIBILE (almeno un 1 in tabella)
Formula INSODDISFACIBILE (tutti 0 in tabella)
Formula VALIDA (tutti 1 in tabella) (TAUTOLOGIA)
F VALIDA <==> not F INSODDISFACIBILE
Esempio di utilizzo di circuiti: Somma tra binariLa somma di due numeri interi in rappresentazionebinaria si effettua in modo analogo alla somma diinteri in rappresentazione decimale: si sommano adue a due le cifre corrispondenti a partire dadestra e se la somma e` maggiore o uguale allabase (2 per la rappresentazione binaria, 10 per larappresentazione decimale, ecc.) si ha un riportoche si deve sommare alle due cifre successive.
Somma binaria
Riporto: 1 1 1 1 0 0
0111002 + 1001112 = ----------- 10000112
Colonna per colonna, da destra a sinistra Riporto se la somma su una colonna supera la base
Tre cifre binarie (prima riga, seconda riga, riporto), somma =1 se una o tre sono 1, riporto = 1 se almeno due sono 1
10000110 riporti 1010011 + 1100011 = ---------- 10110110
Iniziamo con un circuito che faccia la somma su una colonna
Abbiamo tre cifre binarie X, Y, R in input mentre in output vogliamo ottenere la somma S ed il riporto R'
Tabella di verità X Y R S R' 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1
Supponiamo di avere i circuiti che calcolano somma e riporto
SOMMA
XYR
S
RIPORTO
XYR
R'
Possiamo allora combinare i circuiti SOMMA e RIPORTO per ottenere il seguente circuito 1-ADD
SOMMAXYR
S
RIPORTOR'
1-ADD
Il circuito RIPORTO puo` essere realizzato nel seguente modo
X
Y
R
R'
RIPORTO
Basta infatti verificare la corrispondente tabella di verita’
(Il nuovo riporto è q se almeno due di esse sono 1, 0 altrimenti)
R
Y
R
X
CIRCUITO SOMMA(la somma di tre cifre è 1 se o tutte e tre sono 1 oppure una sola vale 1)
A questo punto componendo K circuiti 1-ADD e` possibile realizzare un circuito K-ADD che somma due numeri binari di K cifre.
Vediamo l'esempio della somma di due numeri binari di 4 cifre.
Y3 Y2 Y1 Y0 X3 X2 X1 X0
1-add 1-add 1-add 1-add0 riporto iniziale
riporto finale inutile
risultato
Somma di numeri di 4 bit
S0S1S2S3
0R0R1R2R3
0 1 1 0 0 1 1 1
1-add 1-add 1-add 1-add
1 1 0 1
00110
Esempio
0111 + 0110 = ------ 1101
Attenzione
Si e` trascurato il problema del cosiddetto overflow, cioe’ il risultato e’ troppo grande per essere contenuto nei bit disponibili.
Per esempio: 0111 + 1110 = ------ 10101