Reti logiche

(1)

Fondamenti di Informatica - Reti logiche

FONDAMENTI DI INFORMATICA

Prof. PIER LUCA MONTESSORO Facoltà di Ingegneria Università degli Studi di Udine

Reti logiche

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 2 Questo insieme di trasparenze (detto nel seguito slide) è protetto dalle leggi sul copyright e dalle disposizioni dei trattati internazionali. Il titolo ed i copyright relativi alle slides (ivi inclusi, ma non limitatamente, ogni immagine, fotografia, animazione, video, audio, musica e testo) sono di proprietà dell’autore prof. Pier Luca Montessoro, Università degli Studi di Udine.

Le slide possono essere riprodotte ed utilizzate liberamente dagli istituti di ricerca, scolastici ed universitari afferenti al Ministero della Pubblica Istruzione e al Ministero dell’Università e Ricerca Scientifica e Tecnologica, per scopi istituzionali, non a fine di lucro. In tal caso non è richiesta alcuna autorizzazione.

Ogni altro utilizzo o riproduzione (ivi incluse, ma non limitatamente, le riproduzioni su supporti magnetici, su reti di calcolatori e stampe) in toto o in parte è vietata, se non esplicitamente autorizzata per iscritto, a priori, da parte dell’autore.

L’informazione contenuta in queste slide è ritenuta essere accurata alla data della pubblicazione. Essa è fornita per scopi meramente didattici e non per essere utilizzata in progetti di impianti, prodotti, reti, ecc. In ogni caso essa è soggetta a cambiamenti senza preavviso. L’autore non assume alcuna responsabilità per il contenuto di queste slide (ivi incluse, ma non limitatamente, la correttezza, completezza, applicabilità, aggiornamento dell’informazione).

In ogni caso non può essere dichiarata conformità all’informazione contenuta in queste slide.

In ogni caso questa nota di copyright e il suo richiamo in calce ad ogni slide non devono mai essere rimossi e devono essere riportati anche in utilizzi parziali.

Nota di Copyright

Progettazione di reti logiche

• Specifiche (mappe di Karnaugh per circuiti semplici, linguaggi formali per sistemi complessi)

• Rete di porte logiche elementari

• Circuito elettronico (circuito integrato, piastra, ecc.)

sintesi

realizzazione

Esempio: half adder

• Riceve in ingresso due addendi da un bit ciascuno

• Fornisce in uscita un bit di somma ed uno di riporto (due funzioni logiche)

A

B

S

R

Esempio: half adder

0 1

1 0

0

1

0 1

A B

S

0 0

0 1

0

1

0 1

A B

R

La sintesi in questo caso non è necessaria:

si riconoscono le porte elementari EXOR e AND

Esempio: half adder

A

B

S

R

(2)

Sintesi

• Oggi la progettazione si basa su strumenti software per la sintesi automatica

• Un algoritmo semplice per reti di ridotta complessità si basa sulla “copertura delle mappe di Karnaugh”

Forme canoniche:

AND-OR (somme di prodotti)

• Ogni AND assume il valore 1 in corrispondenza di una casella della mappa contenente un 1

• Mettendo in OR i risultati degli AND si ottiene una funzione che vale 1 in corrispondenza di tutte le caselle che contengono un 1

Forme canoniche:

AND-OR (somme di prodotti)

0 1 0 0

0 0 0 1

00 01 11 10 0

1 AB C

ABC ABC A

B C

ABC+ABC

Fome canoniche:

OR-AND (prodotti di somme)

• Ogni OR assume il valore 0 in corrispondenza di una casella della mappa contenente uno 0

• Mettendo in AND i risultati degli OR si ottiene una funzione che vale 0 in corrispondenza di tutte le caselle che contengono uno 0

Forme canoniche:

OR-AND (prodotti di somme)

1 1 0 1

1 0 1 1

00 01 11 10 0

1 AB C

A

B C

(A+B+C)(A+B+C) A+B+C

A+B+C

Copertura delle mappe di Karnaugh

• Permette di ottenere un circuito con un numero minimo di porte logiche e ingressi per porta, senza bisogno di semplificazione algebrica

0 0 0 0

0 1 1 0

00 01 11 10 0

1 AB C

ABC+ABC = (A+A)BC = BC

=1

(3)

Copertura delle mappe di Karnaugh

• Si coprono “cubi”, cioè gli insiemi di 2 ⁿ uni (per forma AND-OR) o zeri (per forma OR-AND) adiacenti

• Per ogni cubo il termine corrispondente contiene soltanto gli ingressi il cui valore non varia nelle caselle coperte

• Gli ingressi sono presi diretti (in AND- OR, negati in OR-AND) se a 1, negati (diretti) se a 0

Copertura delle mappe di Karnaugh

• Esempio di copertura per la forma AND- OR

0 0 1 1

0 1 1 0

00 01 11 10

0 1 AB C

AC+BC

Copertura delle mappe di Karnaugh

• Ricordare che topologicamente le mappe di Karnaugh sono dei tori

• Inoltre, una casella può essere coperta più volte

1 0 1 1

0 0 0 0

00 01 11 10 0

AB C

1 AC+BC

Esempio: full adder

• Riceve in ingresso due addendi da un bit ciascuno e un bit di riporto

(proveniente dalla colonna precedente)

• Fornisce in uscita un bit di somma ed uno di riporto (due funzioni logiche)

A

R

_i-1

S

R

i

B

Esempio: full adder

0 1

1 0

0

1

00 01

A B

S

porta EXOR a 3 ingressi

0 1

1 0

11 10

0 0

0 1

0

1

00 01

A B

R

1 0

1 1

11 10

AB+BC+AC

Reti logiche combinatorie e reti logiche sequenziali

• Nelle reti viste finora (reti combinatorie) le uscite in un certo istante dipendono esclusivamente dagli ingressi applicati nel medesimo istante (trascurando i ritardi di propagazione dei segnali)

• Nelle reti sequenziali le uscite sono

funzione dello stato degi ingressi nello

stesso istante e negli istanti precedenti

(4)

Reti logiche sequenziali (asincrone)

circuito combinatorio

... ...

...

... ...

ingressi primari uscite primarie

ingressi secondari uscite secondarie

variabili di stato

Esempio: Flip-Flop SR

S

R

Q

Q’

Esempio: Flip-Flop SR

S

R

Q

rete Q’

combinatoria

variabile di stato

Esempio: Flip-Flop SR

S R Q Q’

0 0 (non interessa)

0 1 1 0

1 0 0 1

1 1 ? ?

(dipende dal precedente valore)

S

R

Q

Q’

Esempio: Flip-Flop SR

S

R

Q

Q’

S R Q|

_t-1

Q’|

_t-1

Q Q’

0 0 - - (non interessa)

0 1 - - 1 0

1 0 - - 0 1

1 1 0 1 0 1

1 1 1 0 1 0

cioè ...

Esempio: Flip-Flop SR

S R Q Q’

0 0 (non interessa)

0 1 1 0

1 0 0 1

1 1 Q|

_t-1

Q’|

_t-1

1 1 Q|

t-1

Q’|

t-1

“set”

(ingresso S attivo basso)

“reset”

(ingresso R attivo basso)

R e S inattivi: memoria

(5)

Reti logiche sequenziali sincrone

circuito combinatorio

... ...

...

... ...

ingressi primari uscite primarie

ingressi secondari uscite secondarie

variabili di stato FF

FF clock

Reti logiche sequenziali sincrone

• I flip-flop permettono di mantenere stabili le variabili di stato mentre il precedente stato di ingresso si propaga nel circuito combinatorio

• Il segnale di clock abilita la propagazione dei nuovi valori

• La frequenza di clock delle CPU dei computer (es. 450 MHz) è la frequenza di tale segnale di sincronismo

Porte logiche e transistor

• È possibile realizzare dispositivi elettronici che si comportano come gli operatori dell’algebra di Boole

• Componente fondamentale: il transistor

Transistor

• Modello semplificato:

gate

source

drain

source

drain I

I

La corrente I passa se la tensione sul gate è zero

La corrente I passa se la tensione sul gate è positiva (per esempio 5 V)

Porta logica NOT

+5 V

0 V

input output

Porta logica NOT

+5 V

0 V 0 V = 0 logico

5 V = 1 logico

(6)

Porta logica NOT

+5 V

0 V 5 V = 1 logico

0 V = 0 logico

Porta logica NAND

0 V

input output

+5 V

Porta logica NAND

0 V

+5 V

5 V = 1 logico 0 V = 0 logico

0 V = 0 logico

Porta logica NAND

0 V

+5 V

5 V = 1 logico 5 V = 1 logico

0 V = 0 logico

Porta logica NAND

+5 V

5 V = 1 logico 0 V = 0 logico

5 V = 1 logico

Porta logica NAND

+5 V

0 V = 0 logico 5 V = 1 logico

5 V = 1 logico

(7)

Componenti di un elaboratore

• In un calcolatore troviamo:

– la CPU, un enorme circuito sequenziale contentente dei registri (insiemi di flip-flop), l’unità di controllo (un circuito sequenziale), l’unità logico-aritmetica (un circuito che può essere in parte combinatorio e in parte sequenziale)

– la memoria centrale (v. oltre)

– controller e altri dispositivi, quasi sempre circuiti sequenziali molto complessi

Memorie: registri

• Gruppi di flip-flop all’interno di circuiti sequenziali più complessi

• Esempio: 32 flip-flop per memorizzare un dato su 32 bit

Memorie: RAM (Random Access Memory)

• Organizzate a bit, byte o word indirizzabili tramite un numero

• Tipicamente utilizzate per la memoria centrale degli elaboratori

• Possono essere statiche (basate su flip-flop, limitata densità, alti costi) o dinamiche (basate sulla carica elettrica immagazzinabile in un transistor, per cui è necessario il

“refresh” per rigenerarla periodicamente)

• Sono volatili: perdono il contenuto in assenza di alimentazione

Memorie: ROM (Read-Only Memory)

• Memorie a sola lettura (il contenuto è impostato in sede di fabbricazione)

• Non volatili (mantengono il contenuto anche in assenza di alimentazione)

• Utilizzate nella fase di bootstrap:

all’accensione del computer i programmi del sistema operativo vengono caricati in memoria centrale (volatile) grazie all’esecuzione di un programma di

caricamento residente in una memoria ROM

Memorie

• PROM: “programmable”, permettono di scrivere il contenuto tramite un apposito dispositivo (una sola volta)

• EPROM: “erasable”, il contenuto può essere cancellato e riscritto tramite un apposito dispositivo

• EEPROM: “electrically erasable”:

riprogrammabili senza doverle rimuovere dal circuito stampato

Memorie

• Flash EPROM: riscrivibili come le RAM, ma non volativi, basate su transistor con un gate in più (floating gate) isolato;

numero di riscritture limitato: da 100.000

a 1 milione circa

Reti logiche

FONDAMENTI DI INFORMATICA

Prof. PIER LUCA MONTESSORO Facoltà di Ingegneria Università degli Studi di Udine

Reti logiche

Nota di Copyright

Progettazione di reti logiche

• Specifiche (mappe di Karnaugh per circuiti semplici, linguaggi formali per sistemi complessi)

• Rete di porte logiche elementari

• Circuito elettronico (circuito integrato, piastra, ecc.)

sintesi

realizzazione

Esempio: half adder

• Riceve in ingresso due addendi da un bit ciascuno

• Fornisce in uscita un bit di somma ed uno di riporto (due funzioni logiche)

A

B

S

R

Esempio: half adder

0 1

1 0

A B

S

0 0

0 1

A B

R

La sintesi in questo caso non è necessaria:

si riconoscono le porte elementari EXOR e AND

Esempio: half adder

A

B

S

R

Sintesi

• Oggi la progettazione si basa su strumenti software per la sintesi automatica

• Un algoritmo semplice per reti di ridotta complessità si basa sulla “copertura delle mappe di Karnaugh”

Forme canoniche:

AND-OR (somme di prodotti)

• Ogni AND assume il valore 1 in corrispondenza di una casella della mappa contenente un 1

• Mettendo in OR i risultati degli AND si ottiene una funzione che vale 1 in corrispondenza di tutte le caselle che contengono un 1

Forme canoniche:

AND-OR (somme di prodotti)

0 1 0 0

0 0 0 1

ABC ABC A

B C

ABC+ABC

Fome canoniche:

OR-AND (prodotti di somme)

• Ogni OR assume il valore 0 in corrispondenza di una casella della mappa contenente uno 0

• Mettendo in AND i risultati degli OR si ottiene una funzione che vale 0 in corrispondenza di tutte le caselle che contengono uno 0

Forme canoniche:

OR-AND (prodotti di somme)

1 1 0 1

1 0 1 1

A

B C

(A+B+C)(A+B+C) A+B+C

A+B+C

Copertura delle mappe di Karnaugh

• Permette di ottenere un circuito con un numero minimo di porte logiche e ingressi per porta, senza bisogno di semplificazione algebrica

0 0 0 0

0 1 1 0

ABC+ABC = (A+A)BC = BC

=1

Copertura delle mappe di Karnaugh

• Si coprono “cubi”, cioè gli insiemi di 2 n uni (per forma AND-OR) o zeri (per forma OR-AND) adiacenti

• Per ogni cubo il termine corrispondente contiene soltanto gli ingressi il cui valore non varia nelle caselle coperte

• Gli ingressi sono presi diretti (in AND- OR, negati in OR-AND) se a 1, negati (diretti) se a 0

Copertura delle mappe di Karnaugh

• Esempio di copertura per la forma AND- OR

0 0 1 1

0 1 1 0

00 01 11 10

0 1 AB C

AC+BC

Copertura delle mappe di Karnaugh

• Ricordare che topologicamente le mappe di Karnaugh sono dei tori

• Inoltre, una casella può essere coperta più volte

• Si coprono “cubi”, cioè gli insiemi di 2 ⁿ uni (per forma AND-OR) o zeri (per forma OR-AND) adiacenti