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