Appunti completi di Elettronica digitale

NAND.

Considerazioni conclusive

Sono quindi possibili 4 forme di sintesi fondamentali:

OR-AND

• AND-OR

• NAND-NAND

• NOR-NOR

•

In generale, si sa che è sempre possibile esprimere la funzione in ognuna di

queste 4 forme.

Abbiamo in ogni caso determinato che qualsiasi funzione può essere

realizzata mediante operatori AND, OR e NOT. Questi costituiscono una base

universale, in grado di poter esprimere qualsiasi funzione.

Nella realtà, anche NOT e AND, e NOT e OR costituiscono una base universale,

in quanto l’operatore mancante può essere ottenuto complementando ingressi

ed uscite dell’altro (De Morgan). Anche i NAND sono una base universale,

così come i NOR, come abbiamo visto rispettivamente nelle rappresentazioni

NAND-NAND e NOR-NOR.

Per la minimizzazione di aree e ritardi, rimane comunque conveniente avere

una grande varietà di celle disponibili in libreria.

si trovano inoltre anche operatori composti, come

In libreria o

+

.

Esercizio

Come esercizio provare la sintesi della funzione �

A B C F

0 0 0 0 1

0 0 1 0 1

0 1 0 0 1

0 1 1 1 0

1 0 0 1 0 16

2. Logica combinatoria

1 0 1 0 1

1 1 0 0 1

1 1 1 1 0

Con tutti e 4 i metodi.

Osserveremo che l’espressione può essere semplificata in modo aggiuntivo,

considerando semplificazioni come

̅ + =

Semplificazioni algebriche

Andiamo adesso ad affrontare la possibilità, una volta trovata una sintesi,

di semplificare l’espressione trovata.

Ci avvaliamo della funzione trovata in precedenza, espressa nella sintesi

AND-OR: ′ ′ ′ ′ ′

(, , ) = + + + +

Il criterio che si applica, che costituisce un primo step alla

semplificazione, è la minimizzazione del numero dei letterali, ossia delle

ricorrenze delle variabili nelle espressioni.

Iniziamo da 15 letterali, per cui una riduzione è d’obbligo.

Andiamo ad applicare la proprietà ̅

+ =

alla nostra espressione, ottenendo

′ ′ ′ ′ ′ ′ ′

( ( (

(, , ) = =

+ + ) + + ) + + )

′ +

=

Questa ultima espressione potrebbe apparire come minima, ma può essere

semplificata attraverso una seconda proprietà

̅

+ = +

L’applicazione di questa proprietà ci permette di ottenere un’espressione

equivalente minimizzata ′

(, , ) = + = +

Si ottiene quindi un’espressione composta da 3 letterali, e inoltre priva di

inverter (questa seconda caratteristica è un effetto casuale, e non è il

fine del procedimento).

La realizzazione di questa espressione con celle elementari sarà

estremamente più semplice e meno dispendiosa in termini di risorse, se si

andrà ad utilizzare questa forma ridotta.

Altre semplificazioni

Si vanno successivamente ad applicare un’altra serie di ottimizzazioni, che

possono anche aumentare il numero di letterali, al fine di incontrare le

specifiche predeterminate. 17

2. Logica combinatoria

Queste variazioni aggiunte, e anche la semplificazione per minimizzazione

dei letterali, sono generalmente processi automatizzati a livello

informatico.

Conoscere queste procedure e questi meccanismi, ci permetterà di comprendere

ed utilizzare meglio gli strumenti di sintesi automatica.

Applicazione di De Morgan e sintesi NAND NAND

Applicando De-Morgan possiamo trasformare l’espressione logica nella sua

equivalente, anche partendo direttamente dalla sua rappresentazione grafica:

gli OR diventano NAND con negazioni in ingresso, l’AND diventa NAND con

negazione in uscita, che annulla la negazione adiacente. Il not diventa un

NAND con ingressi cortocircuitati (quest’ultimo passo non è necessario).

Come abbiamo visto anche per la forma canonica, possiamo portare tutto anche

in NOR-NOR.

Forme canoniche a 2 livelli

Le forme canoniche a due livelli appartengono alle 4 categorie che abbiamo

analizzato:

NAND-NAND

• AND-OR

• NOR-NOR

• OR-AND

•

Ricordiamo che convenzionalmente il not non viene contato come livello, per

cui le sintesi che abbiamo analizzato sono da considerarsi a 2 livelli.

Osserveremo anche delle funzioni fondamentali realizzate mediante sintesi

multilivello, ma non analizzeremo algoritmi di sintesi multilivello.

La sintesi multilivello esiste in quanto in alcuni casi, risulta più

conveniente mantenere un numero di livelli superiori.

In alcuni casi, infatti, una sintesi a due livelli porta all’”esplosione”

della complessità della sintesi, ossia genera un’enorme quantità di porte

logiche. 18

2. Logica combinatoria

Generalmente, i moderni tool di sintesi, portano la sintesi fino ai due

livelli, ed iniziano successivamente delle operazioni di ottimizzazione che

possono arrivare, nei casi più estremi, fino al sessantesimo livello, ma che

nella maggior parte dei casi si fermano entro il decimo livello.

Mappe di Karnaugh

Le mappe di Karnaugh consentono di minimizzare funzioni logiche semplici

(fino a 4 ingressi, ma anche di più), in modo più veloce e intuitivo.

Almeno per ora, consideriamo che la sintesi rappresenta una combinazione di

operatori elementari, il cui comportamento è descritto proprio dalla tavola

di verità.

In particolare, possiamo realizzare mappe di Karnaugh a 2 (2x2), 3(4x2) e 4

(4x4) ingressi, in cui ogni casella corrisponde ad una riga della tavola di

verità.

Introduzione mediante esempio

Consideriamo la funzione descritta dalla seguente tavola

0 0 0

0 1 0

1 0 1

1 1 1

Questa può essere rappresentata dalla seguente mappa di Karnaugh, che deve

avere numero di caselle corrispondente al numero di righe della tabella di

verità

Possiamo andare a svolgere la sintesi di questa funzione mediante i

mintermini, utilizzando la tabella della verità:

� =

= +

Ma possiamo anche considerare la mappa.

Osserviamo la presenza dei due zeri in verticale, e li consideriamo come un

tutt’uno, ignorando la variabile che varia da un caso all’altro.

= 19

2. Logica combinatoria

Regole di raggruppamento

Per sintetizzare la funzione partendo dalla mappa di Karnaugh, è necessario

andare a raggruppare gli ma questo è possibile solamente in alcune

1,

specifiche circostanze.

Possiamo andare a formalizzare la procedura di raggruppamento:

Si considerano gli adiacenti in orizzontale o verticale (non in

• 1

diagonale).

Si prendono i gruppi di 1 adiacenti composti da 1, 2, 4, 8, 16 caselle

• Tali gruppi sono detti cubi

• Ogni cubo viene sintetizzato da un termine detto “implicante”

• La sintesi termina quando finiscono gli 1.

•

In caso di 3 o 4 ingressi, i valori verranno organizzati in coppie, aventi

ordine rigoroso.

Esempio variabili

Andiamo ad analizzare la seguente mappa, al fine di sintetizzare la relativa

funzione:

Osserviamo la presenza di due gruppi, e andiamo a sintetizzarli entrambi:

̅� ̅

= +

Dove il primo elemento (implicante) dell’uscita è ottenuto considerando il

gruppo evidenziato in verde, ignorando la variabile che non influenza il

,

cambiamento, ed il secondo elemento è ottenuto considerando il cubo rosso,

in cui viene ignorata la variazione della variabile B. 20

2. Logica combinatoria

Raggruppamenti a pac-man

Possiamo osservare che sono considerabili come adiacenti anche elementi che

“scavalcano” la fine della tabella, come nel caso del gruppo rosso nella

seguente mappa

Questo è dovuto al fatto che i cubi sono identificabili come serie di

elementi che variano tra di loro rispetto ad una sola variabile.

Lo stesso vale anche per più estremi per cui, considerando la seguente

funzione, possiamo scrivere

Ripresa di elementi

Osserviamo che vengono “ripresi” elementi già selezionati in quanto la

sintesi si mantiene corretta in tutti i casi, ma in questo modo di minimizza

il numero di letterali utilizzati.

Raggruppando con sovrapposizione, si otterrà più di un implicante che vale 1

simultaneamente, il che comporta una sovrapposizione logica, che non varia

l’uscita, ma che permette una semplificazione fisica.

Se non venissero raggruppati (per errore) degli 1 raggruppabili, la sintesi

ottenuta sarebbe valida, ma non minima. 21

2. Logica combinatoria

Indifferenze sulle uscite (Don’t cares)

Si riscontrano particolari situazioni in cui, determinate combinazioni di

ingressi, non dovrebbero mai presentarsi, in quanto le unità digitali con

cui stiamo lavorando non prevedono tali combinazioni.

Possiamo considerare ad esempio il controllore di un treno con due uscite,

che indicano se il treno è fermo, e se il treno ha superato i 100km/h.

Questi due ingressi non possono mai presentarsi contemporaneamente, per cui

presupporremo che questi ingressi non potranno mai verificarsi in

simultanea.

D’altro canto, il progettista può permettersi di ignorare una combinazione

anomala solo in alcuni contesti, per cui si determina generalmente, in

queste condizioni di incongruenza, di portare il sistema ad uno stato

“sicuro” (nel nostro caso, ad esempio, azionare i freni).

Se si sceglie di semplificare il progetto, ignorando l’evenienza anomala, il

sistema avrà un determinato comportamento. Se si sceglie invece di

considerare questo ingresso anomalo, si ottiene invece un comportamento

differente.

Va quindi svolta una scelta funzionale, che deve essere determinata anche

dalle caratteristiche del progetto. Un treno giocattolo può subire

conseguenze come un deragliamento, senza causare problemi: una determinata

probabilità di deragliamento può essere considerata accettabile per un

giocattolo, ma non per un treno reale.

Progettare ignorando le incongruenze

Andiamo per ora ad assume