Lezione 2Circuiti logici

Mauro Piccolopiccolo@di.unito.it

Bit e configurazioni di bit

Bit: una cifra binaria (binary digit) 0 oppure 1

Sequenze di bit per rappresentare l'informazione Numeri Caratteri di un testo Immagini Suoni ....

Circuiti Logici

Realizzano operazioni booleane AND OR NOT …

Giustapposizioni di porte logiche (gate)

NOT

Ingresso Uscita

0 1

1 0

Ingresso Uscita

AND

Ingresso A Ingresso B Uscita

0 0 0

0 1 0

1 0 0

1 1 1

Ingresso A

Ingresso BUscita

OR

Ingresso A

Ingresso B

Uscita

Ingresso A Ingresso B Uscita

0 0 0

0 1 1

1 0 1

1 1 1

XOR

Ingresso A Ingresso B Uscita

0 0 0

0 1 1

1 0 1

1 1 0

Ingresso AUscita

Ingresso B

Come sono costruite le porte logiche?

I valori logici 1,0 vengono rappresentati da segnale alto (+5 volt) e segnale basso (0 volt)

Le porte logiche sono costruite utilizzando i transistor

Il transistor e' un dispositivo elettronico che puo' essere utilizzato come un veloce interruttore

Come sono costruite le porte logiche?

• Un transistor ha tre punti principali, il collettore, la base e l'emettitore

• Quando Vin e' alto Vout e' basso e viceversa

• In questo modo viene facilmente realizzata una porta NOT

Come realizzare altre operazioni booleane?

Tutte le altre operazioni booleane possono essere ottenute mediante giustapposizioni di porte logiche AND, OR e NOT

NANDIngresso

AIngresso

BUscita

0 0 1

0 1 1

1 0 1

1 1 0

Ingresso AUscita

Ingresso B

Simuliamo il NAND (1)

0

0

10

Ingresso A

Ingresso B

Uscita

0 0 1

Simuliamo il NAND (2)

1

1

01

Ingresso A

Ingresso B

Uscita

1 1 0

NORIngresso

AIngresso

BUscita

0 0 1

0 1 0

1 0 0

1 1 0

UscitaIngresso B

Ingresso A

Abbreviazioni

Porta NAND Porta NOR

XOR

A XOR B e' vero sse A e' vero e B e' falso oppure A e' falso e B e' vero

Ingresso A

Ingresso B

Uscita

0 0 0

0 1 1

1 0 1

1 1 0

Simuliamo lo XOR (1)

Ingresso A

Ingresso B

Uscita

1 0 1

1

0

0

1

0

1

1

Simuliamo lo XOR (2)

Ingresso A

Ingresso B

Uscita

1 0 1

Ingresso A

Ingresso B

Uscita

0 1 1

0

1

1

0

1

0

1

Simuliamo lo XOR (3)

Ingresso A

Ingresso B

Uscita

0 0 0

0

0

1

1

0

0

0

Sintesi di circuiti

• Costruiamo il circuito corrispondente ad una tabella di verita'

– Consideriamo tutte le righe della tabella di verita' con uscita 1

– Per ciascuna di esse costruiamo un circuito utilizzando solo porte AND e NOT che vale 1 solo quando tutti gli ingressi coincidono con gli ingressi della riga

– Riuniamo tutte le uscite precedenti tramite una porta OR

L'implicazione

Ingresso A

Ingresso B

Uscita

0 0 1

0 1 1

1 0 0

1 1 1

A implica B e' vero sse A e' vero e B e' vero oppure A e' falso e B e' vero oppure A e' falso e B e' falso

Esercizio

• Qual'e' la tabella di verita' associata al seguente circuito?

• Risposta: la stessa dell'implicazione.

Ancora sintesi di circuiti

• Abbiamo visto che

– ad una tabella di verita' possono corrispondere piu' circuiti

– da un punto di vista progettuale, occorre costruire circuiti con il minimo numero di porte

• Vediamo un altro algoritmo di sintesi di circuiti

Sintesi di circuiti (2)

Consideriamo tutte le righe della tabella di verita' con uscita 0

Per ciascuna di esse costruiamo un circuito utilizzando solo porte OR e NOT che vale 0 solo quando tutti gli ingressi coincidono con gli ingressi della riga

Riuniamo tutte le uscite precedenti tramite una porta AND

Tuttavia i circuiti si possono ulteriormente semplificare usando un po' di matematica

Algebra booleana

La struttura <{0,1},+,., > dove

- + e' l'operatore OR

- . e' l'operatore AND

- e' l'operatore NOT

viene detta algebra booleana

Funzioni booleane

Una qualsiasi funzione con n variabili f : {0,1}n → {0,1}viene detta funzione booleana

Qualsiasi funzione booleana puo' essere descritta mediante tabelle di verita'

Ci sono 2

2n funzioni booleane con n variabili

Operatori universali

Un insieme finito di funzioni booleane si dicono operatori universali se qualsiasi funzione booleana puo' essere fattorizzata in termini di questi operatori

Thm: AND, OR e NOT sono operatori universali

Thm: Un insieme di operatori e' universale se e solo se AND, OR e NOT possono essere definiti in termini di questi operatori

L'operatore NAND

NAND (|) e' un operatore universale

x + y = (x|x)|(y|y)

x y = (x|y)|(x|y)

x = x|x

Esercizio: dimostrare che NOR ( ) e' universale

Proprieta' dei reticoli

Proprieta' delle algebre booleane

Proprieta' fondamentali

Sintesi di circuiti (1)

Sintesi di circuiti (2)

Reti combinatorie e sequenziali

Rete combinatoria: una rete in cui lo stato di uscita dipende esclusivamente dagli stati di ingresso

Rete sequenziale: una rete in cui lo stato di uscita dipende, oltre che dagli stati di ingresso, anche dalla storia precedente della rete

Il problema del pedone

?

Individuazione delle variabili logiche di ingresso e uscita

Ingresso R (stato lampada rossa) 1 = accesa 0 = spenta

Ingresso V (stato lampada verde) 1= accesa 0 =spenta

Ingresso C (stato carreggiata) 1 = occupata 0 = libera

Uscita A (attraversamento) 1= attraversa 0 = non attraversare

Tabella di verita'

Sintetizzare il circuito

Flip flop

Un circuito sequenziale in grado di memorizzare un bit

Sintesi di un flip flop

Individuazione delle variabili logiche di ingresso, stato, uscita:

– Ingresso D (dato) 0,1

– Ingresso C (clock) 1 = memorizza, 0 = non memorizzare

– Uscita-stato Q (valore memorizzato) 0,1

Sintesi di un flip flop

Tabella di verita'

Sintesi di un flip flop

Circuito

Un altro modo di costruire un flip flop