circuiti logici - università degli studi di padova
TRANSCRIPT
![Page 1: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/1.jpg)
Circuiti Logici
Pagina web del corso: http://www.math.unipd.it/~aceccato
![Page 2: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/2.jpg)
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
![Page 3: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/3.jpg)
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
![Page 4: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/4.jpg)
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
![Page 5: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/5.jpg)
Macchina hardware e macchina software
MacchinaHardware
Sistema Operativo
Compilatori ed applicativi diversi
![Page 6: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/6.jpg)
Hardware
Filosofia di costruzione
"tante componenti semplici, se ben organizzate, possono realizzare funzionalita` complesse"
![Page 7: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/7.jpg)
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
![Page 8: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/8.jpg)
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
![Page 9: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/9.jpg)
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)
![Page 10: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/10.jpg)
1010
L’algebra di BooleL’algebra di Boole
![Page 11: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/11.jpg)
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
![Page 12: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/12.jpg)
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
![Page 13: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/13.jpg)
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
![Page 14: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/14.jpg)
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
![Page 15: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/15.jpg)
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
![Page 16: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/16.jpg)
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
![Page 17: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/17.jpg)
⇒ 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
![Page 18: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/18.jpg)
≡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
![Page 19: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/19.jpg)
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
![Page 20: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/20.jpg)
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
![Page 21: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/21.jpg)
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
![Page 22: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/22.jpg)
!!! Chiaramente il circuito cosi’ costruito nonnecessariamente e’ il piu’ semplice (ovvero con ilminor numero possibile di porte logiche utilizzate)
![Page 23: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/23.jpg)
Nand e nor
Non servono tre operazioni (and, or, not)
Basta una tra :
nand (not and) e nor (not or)
![Page 24: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/24.jpg)
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
![Page 25: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/25.jpg)
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.
![Page 26: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/26.jpg)
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)
![Page 27: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/27.jpg)
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
![Page 28: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/28.jpg)
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
![Page 29: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/29.jpg)
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
![Page 30: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/30.jpg)
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
![Page 31: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/31.jpg)
Circuito (NOT(A) NOT(B)) OR (NOT(A) AND B)
Esercizio 4
or
R
AB
and
and
and
or
orand
![Page 32: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/32.jpg)
...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
![Page 33: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/33.jpg)
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)
![Page 34: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/34.jpg)
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
![Page 35: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/35.jpg)
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)
![Page 36: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/36.jpg)
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
![Page 37: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/37.jpg)
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
![Page 38: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/38.jpg)
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.
![Page 39: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/39.jpg)
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
![Page 40: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/40.jpg)
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'
![Page 41: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/41.jpg)
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
![Page 42: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/42.jpg)
Supponiamo di avere i circuiti che calcolano somma e riporto
SOMMA
XYR
S
RIPORTO
XYR
R'
![Page 43: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/43.jpg)
Possiamo allora combinare i circuiti SOMMA e RIPORTO per ottenere il seguente circuito 1-ADD
SOMMAXYR
S
RIPORTOR'
1-ADD
![Page 44: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/44.jpg)
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)
![Page 45: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/45.jpg)
R
Y
R
X
CIRCUITO SOMMA(la somma di tre cifre è 1 se o tutte e tre sono 1 oppure una sola vale 1)
![Page 46: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/46.jpg)
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.
![Page 47: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/47.jpg)
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
![Page 48: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/48.jpg)
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
![Page 49: Circuiti Logici - Università degli studi di Padova](https://reader030.vdocumenti.com/reader030/viewer/2022012712/61ab770e9a0043532c265724/html5/thumbnails/49.jpg)
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