Reti logiche

ALGORITMO DI KARNAUGH

Funzione di commutazione a n variabili,

Partendo dalla che mettendo in relazione

Ingressi – Uscite attiva (=1)

indica quando un’uscita è in base ai valori degli ingressi,

tabella di verità: tutti i possibili

si crea la La rappresentazione tabellare che mostra

valori degli ingressi corrispondenti valori di uscita.

di una funzione logica e i

Una volta costruita la Tabella di Verità, i valori vengono trasposti su una Mappa di

identificando il numero di variabili

Karnaugh, (Con n variabili, la mappa avrà 2 ⁿ

disponendole codificate con valori in Gray Code un bit cambia

celle) e (In cui solo

alla volta tra valori adiacenti).

Se un mintermine è presente nella tabella di verità (La funzione vale 1 per quella

1

combinazione di ingressi), si segna un nella cella corrispondente, se no 0.

raggruppare i mintermini adiacenti

L’obiettivo è (1) con queste regole:

Solo celle con 1 possono essere raggruppate in gruppi potenza di 2.

- Le celle possono essere raggruppate orizzontalmente e verticalmente.

- La mappa è toroidale (Le celle ai bordi possono connettersi tra loro).

- copertura minima fase

Per ottimizzare la rappresentazione bisogna trovare la sua con la

di Espansione: Unire mintermini in gruppi più grandi per eliminare le variabili superflue.

Bisogna Trovare gli implicanti primi, selezionare gli implicanti essenziali ed

Eliminare i completamente ridondanti, infine scrivere la funzione ridotta.

Esempio Mappa di Karnaugh:

Mappa K:

B

0 1

A +-------

0 | 0 | 1

1 | 1 | 1

KARNAUGH SE: Semplifico a mano, poche variabili (5-6), visualizzare i

mintermini, semplificazione rapida e intuitiva dei circuiti semplici.

QUINE MC CLUNSKY SE: Si vuole identificare gli implicanti primi, ottimizzazione

esatta automatica, procedura algoritmica rigorosa, più di 4-5 variabili.

Metodo di Quine Mc Clunsky algoritmo sistematico minimizzazione

Il è un per la

esatta delle funzioni logiche. tante variabili

Si usa quando la funzione ha e si vuole

tre insiemi:

Per descrivere una funzione, si usano

una minimizzazione ottima.

trovare

ON-set: 1, OFF-set: 0

I mintermini dove la funzione = I mintermini dove la funzione =

Don’t Care set (DC-set): indifferenti

e I mintermini (Usati per semplificare)

4 relazioni fondamentali: Non hanno elementi in comune

Questi insiemi rispettano

e tutti uniti formano l’Insieme completo dei 2 mintermini.

ⁿ

FASE 1: Espansione. Individuare gli implicanti primi

Convertire i mintermini binario.

1. dell’ON-set e del DC-set in

Raggrupparli numero di 1

2. in base al presenti in ciascun termine (Peso di Hamming).

Confronta ogni termine gruppo adiacente:

3. di un gruppo con quelli del

Se distanza di Hamming = 1 Si combinano in un termine con un trattino -.

→

Esempio: 0001 e 0011 distanza = 1 combinazione = 00-1.

→ →

Segna come usati

4. i termini che vengono combinati.

5. Ripeti la combinazione tra i nuovi termini finché non si può più combinare nulla.

non usati in una combinazione implicanti primi

6. Tutti i termini sono detti

FASE 1.5: Dominanze. Per ridurre complessità tabella prima di selezionare implicanti.

Dominanza di Righe: Se una riga (Implicante) copre un sottoinsieme dei

mintermini coperti da un’altra riga può essere eliminata (Non è più utile).

Dominanza di Colonne: Se una colonna (Mintermine) è coperta da un solo

implicante, quest’ultimo è essenziale e va subito selezionato.

FASE 2: Copertura. la funzione: il numero minimo di

Minimizzare Scegliere

implicanti tutti i mintermini dell’ON-set

che copre

tabella di copertura, Colonne

1. Si crea la con = Mintermini dell’ON-set e come

Righe copre

= Implicanti primi, scrivendo una X dove un implicante un mintermine.

da un solo implicante,

2. Se un mintermine è coperto allora quell’implicante è

essenziale va incluso subito

e

Elimina dalla tabella le colonne (mintermini) già coperti

3. Completare la copertura non

4. scegliendo il minimo numero di implicanti

essenziali che coprano i rimanenti mintermini

PORTE LOGICHE

Sono componenti elettronici che eseguono operazioni logiche sui segnali:

0 1

= Livello basso (Assenza di tensione) e = Livello alto (Presenza di tensione).

Ogni porta logica riceve un segnale in ingresso e restituisce un segnale in uscita.

Le porte logiche possono essere costruite con diverse tecnologie elettroniche:

- Diode Logic (DL): diodi resistenze.

Usa e

- Resistor-Transistor Logic (RTL): resistenze transistor.

Usa e

Era usata nei primi computer, ma consuma molta energia.

- Diode-Transistor Logic (DTL): RTL

Migliora la con diodi per ridurre consumo

- Transistor-Transistor Logic (TTL): transistor bipolari.

Solo Circuiti anni ’90.

- Emitter-Coupled Logic (ECL): supercomputer.

Veloce, consuma molto. Per

- Complementary MOS Logic (CMOS): MOSFET

Transistor per ridurre il

consumo energetico. È la tecnologia usata nei circuiti moderni.

Porte Logiche di Base:

Porta NOT (Inverter): 0 1 1 0

1. Inverte il valore logico: e

→ →

interruttore invertito:

È come un se è acceso, spegne; se è spento, accende.

Porta AND: 1 solo se tutte le entrate sono 1,

2. Restituisce altrimenti 0.

serie,

Se hai 2 interruttori in la lampadina si accende solo se entrambi sono ON.

Porta OR: 1 se almeno una delle entrate è 1,

3. Restituisce altrimenti 0.

parallelo: almeno uno è ON.

Due interruttori in la lampadina si accende se

Porte Funzionalmente Complete: realizzare qualsiasi altra porta logica.

Possono

Porta NAND (NOT AND):

1. Restituisce l’opposto di una AND.

Porta NOR (NOT OR):

2. Restituisce l’opposto di una OR.

Porte Speciali:

Porta XOR (Exclusive OR): 1 solo se le entrate sono diverse.

1. addizionatori e circuiti aritmetici.

Usata per uno è premuto, non entrambi.

Due pulsanti: la luce si accende solo se ma

Porta XNOR (Exclusive NOR): 1 solo se le due entrate sono uguali.

2.

Circuiti Logici: Combinano più porte logiche per eseguire operazioni complesse.

3-input AND: tutte 3-input NAND

• Restituisce 1 solo se le entrate sono 1 e

3-input OR: almeno una 3-input NOR

• Restituisce 1 se delle entrate è 1 e

ritardo di propagazione,

N.B: Quando il segnale attraversa una porta logica c’è un

che influenza la velocità del circuito e dipende dalla realizzazione dei componenti.

Il ritardo totale si calcola contando il numero di porte logiche presenti tra i segnali o

Critical Path:

considerando il Il percorso più lungo tra ingressi e uscite.

RETI LOGICHE COMBINATORIE (RLC) e SEQUENZIALI

Una rete logica è un insieme di porte logiche (AND, OR, NOT, XOR) interconnesse per

elaborare segnali digitali e sono alla base dei circuiti digitali, il loro compito è eseguire

operazione booleane sui segnali di input per avere un output. Due tipi di reti logiche:

Rete Combinatoria o Rete Logica Statica: solo

Il valore delle uscite dipende dai

valori attuali degli ingressi, non ha memoria e non dipende da stati precedenti.

Operano in maniera stabile e predicibile, il funzionamento è definito da una funzione

booleana che collega ingressi e uscite senza alcuna dipendenza temporale o evolutiva.

Esempi: Sommatore, Decoder, Multiplexer, Porte Logiche AND, OR, NOT, XOR, etc.

Rete sequenziale o Rete Logica Dinamica: dipende sia dagli ingressi

L’uscita

attuali che dagli stati precedenti, possibile grazie all’uso di memorie come i Flip-Flop

o altri dispositivi di memoria che permettono di conservare l’informazione nel tempo.

Esempi: Registri, Contatori, Macchine a Stati Finiti.

Se le transizioni di stato avvengono in maniera sincronizzata con un segnale di clock

Reti Logiche Sincrone.

parliamo di Gli elementi della rete (Flip-flop o porte logiche),

vengono aggiornati e operano in modo coordinato in base al segnale.

memoria,

Contengono la capacità di mantenere informazioni sugli stati precedenti.

Esempi: Macchine a stati finiti Sincrone, Contatori, Registri e FF (D) Sincroni, ALU.

se le transizioni di stato non sono sincronizzate clock

Altrimenti da un segnale di

Reti Logiche Asincrone. direttamente agli

parliamo di Queste reti rispondono

ingressi e modificano il loro stato quando si verifica un cambiamento negli ingressi,

senza aspettare un impulso di clock.

Esempi: Flip-Flop asincroni (SR), Macchine a Stati Finiti Asincrone.

PROGETTAZIONE DI UNA RETE LOGICA COMBINATORIA

1. Si parte da una descrizione chiara del problema in linguaggio naturale.

2. Si Definiscono quali componenti digitali servono

3. Si Costruire una tabella di verità che mostri la relazione ingressi - uscite.

4. Si Scrivono le funzioni che descrivono il circuito, lo si creare con le porte.

5. Si Minimizza il numero di porte per ridurre il costo e migliorare le prestazioni, con la

1° forma canonica (SOP) o 2° forma canonica (POS).

Minimizzazione esatta: Quine-McCluskey o K-Map)

1. Con metodi rigorosi (come

per trovare la forma più compatta possibile della funzione.

Ottimizzazione d’area:

2. Riduce il numero di porte logiche per occupare meno spazio

sul chip, bilanciando la velocità e i costi di produzione.

CIRCUITI COMBINATORI DI BASE o RETI LOGICHE STATICHE

le uscite dipendono esclusivamente

Sono una classe di circuiti logici digitali in cui

dai valori attuali degli ingressi senza alcuna memoria degli stati precedenti.

Oltre alle porte logiche AND, OR, NOT, possiamo avere:

Multiplexer: seleziona uno tra diversi segnali di ingresso

è un circuito combinatorio che e

instrada verso una singola uscita, selettori.

lo sulla base di segnali di controllo chiamati

2 ingressi n linee di selezione singola uscita

Ha dati e e una che assume il valore

ⁿ

dell’ingresso selezionato dal numero binario formato dagli n selettori.

Non ha memoria, ogni uscita dipende solo dagli ingressi correnti.

quindi

È molto utilizzato per la gestione di bus di dati e per instradamenti controllati.

Demultiplexer: Operazione inversa del multiplexer, è un circuito combinatorio che

riceve un solo segnale di ingresso segnali di controllo degli n

e, sulla base dei

n

selettori, instrada su una delle 2 uscite.

lo

Solo 1 uscita è attiva per ogni combinazione dei selettori e assume il valore

dell’ingresso, tutte le altre restano a zero.

distribuzione controllata di segnali attivare

È usato per la su più linee, ad esempio per

selettivamente dispositivi o registri in sistemi di memoria e controllo digitale.

Decoder: è un circuito combinatorio