Appunti completi corso Reti Logiche

DEL COMPLEMENTO

LEGGI DI DE !(A * B) = !A + !B !(A + B) = !A * !B

MORGAN

Ricordando che, data una funzione booleana espressa tramite tabella di verità, il nostro

problema è trovarne l'espressione algebrica, dobbiamo sapere che ne esistono infinite.

Per dimostrarlo basta utilizzare le proprietà qua sopra e applicarle ricorsivamente. Il punto

è che, tra le infinite che esistono, dobbiamo sceglierne una “che ci piace”. Cosa vuol dire

che ci piace? Dipende dall'OBIETTIVO che abbiamo, che deve essere ben definito:

migliori prestazioni, minori costi, minori consumi energetici? Per decidere se

un'espressione algebrica rispecchia l'obiettivo richiesto è necessario anche trovare una

CIFRA DI MERITO che possa dirci in modo univoco se una soluzione è migliore di

un'altra. La cifra di merito deve essere unica, ovvero uno scalare, altrimenti non avremmo

metodi oggettivi per scegliere (un po' come quando scegli il computer: non hai una singola

figura di merito, perché guardi le specifiche che sono tutte diverse e finisce sempre che

scegli con un trade-off e andando a fiducia). Nel nostro corso l'obiettivo sarà la riduzione

dei costi e la cifra di merito per definire il costo sarà il numero di letterali.

Tra tutte le espressioni algebriche che esistono, ce ne sono un paio particolarmente

importanti: le FORME CANONICHE. Siccome le hai già viste nel corso di ACSO non ci

dilunghiamo tanto a spiegarle:

PRIMA FORMA CANONICA (somma di prodotti): si prendono le configurazioni

– della funzione che generano 1 in uscita, le si mettono in AND fra loro in modo che

diano output 1 ottenendo dei mintermini e si uniscono tutti i mintermini in OR.

SECONDA FORMA CANONICA (prodotto di somme): si prendono le

– configurazioni della funzione che generano 0 in uscita, le si mettono in OR fra loro

in modo che diano output 0 ottenendo dei maxtermini e si uniscono tutti i

maxtermini in AND.

La forma canonica ovviamente è brutta circuitalmente, ci sono millemila semplificazioni

che si possono fare. Ma per adesso non ci interessa, perché l'obiettivo è trovare

un'espressione algebrica tra le tante e basta. La forma canonica per di più non è altro che

l'implementazione delle ROM! La ROM è un circuito che può contenere qualsiasi funzione

booleana in forma canonica disponendo i MOSFET su una matrice. Poi sai benissimo dal

corso di elettronica come si sono evolute le ROM primordiali fino alle attuali FLASH.

Ora diamo un formalismo teorico e d'ora in poi lavoreremo solo sulla prima forma

canonica, in quanto la seconda funziona dualmente. Il formalismo in questione è il

TEOREMA DI ESPANSIONE DI SHANNON. È figo perché permette di dimostrare

facilmente la correttezza delle forme canoniche. Esso dice che, data una funzione

booleana f(x , x , x ...x ) vale la seguente uguaglianza:

0 1 2 n

f(x , x , x ...x ) = x *f(1, x , x ...x ) + !x *f(0, x , x ...x )

0 1 2 n 0 1 2 n 0 1 2 n

La dimostrazione te la lascio come esercizio. Sta di fatto che questo teorema inutile è la

dimostrazione delle forme canoniche eheheheeh

Per concludere, avevamo detto che l'uso delle proprietà algebriche permette di

semplificare le forme canoniche trasformandole in altre più semplici e con meno letterali.

Tuttavia il procedimento non è algoritmico: il risultato dipende dalla scelta delle proprietà

da usare e dall'ordine con cui le applichiamo. Inoltre non sappiamo nemmeno se il risultato

finale è la forma minima, cioè quella che non si può ulteriormente ridurre. Per questo

motivo la semplificazione tramite proprietà algebriche non è la via che si sceglie...!

Ricapitolando, il nostro scopo è avere una funzione che riduca il costo, e naturalmente il

costo dipende dal modello che scegliamo noi per misurarlo. Il prof ha parlato a lungo su

cosa significa modellare dal punto di vista della fisica o degli algoritmi: possiamo scegliere

un modello semplice ma più approssimato, oppure uno preciso ma che richiede più

energie (chiaro esempio negli algoritmi euristici). Il nostro modello per il costo è molto

semplice: il numero di letterali. Essendo un modello semplice è anche uno stimatore,

ovvero non è un'indicazione precisa sul costo della rete finale: di fatto il costo non dipende

solo dalla funzione da implementare in sé, ma anche dalla tecnologia utilizzata. Basti

pensare che in CMOS le porte logiche di base sono le NAND e le NOR, ma non le AND e

OR, che invece sono le porte di base della tecnologia ECL.

Nella spiegazione delle forme canoniche avevamo assunto una cosa che non è sempre

garantita, ovvero che la funzione sia definita per qualsiasi input in ingresso. Ma spesso

possiamo trovarci in condizioni in cui un certo input non si verifica mai (o non dovrebbe

verificarsi) per cui l'output non è definito. Come ci si comporta in questi casi? Si chiamano

CONDIZIONI DI INDIFFERENZA e complicano tutto, perché il numero di tabelle della

verità possibili aumenta esponenzialmente con i gradi di libertà (cioè output liberi).

Per ridurre il costo, ovvero i letterali, ricorreremo alla MINIMIZZAZIONE, il cui scopo è

ridurre il numero di mintermini (o maxtermini) e i letterali all'interno di ciascuno di essi. Il

risultato rimarrà comunque A DUE LIVELLI, come previsto dalle forme canoniche. Se non

ci fosse il vincolo dei due livelli dovremmo fare una sintesi multilivello, che non studieremo.

Come detto nella lezione scorsa, il primo passo per la definizione della forma minima è la

stesura della forma canonica (che d'ora in poi sarà sempre la prima) e dopo ciò possiamo

utilizzare vari metodi. Quello che vedremo in questa lezione è l'uso delle MAPPE DI

KARNAUGH.

Prima di vederle, definiamo il concetto di DISTANZA DI HAMMING tra due configurazioni:

è semplicemente il numero di bit diversi. Quindi tra 000 e 111 la distanza di Hamming è 3.

Questa distanza può essere espressa con figure geometriche, dove ogni vertice

rappresenta una configurazione. La distanza di Hamming è il numero di lati da

attraversare per passare da una configurazione all'altra. La cosa si fa molto divertente

quando si va oltre la terza dimensione... n

A questo punto possiamo costruire la Mappa di Karnaugh: consiste in una matrice con 2

caselle. Come indici di righe e indici di colonne usiamo i valori possibili delle variabili (di

solito gli indici sono composti da più di una variabile) ordinati con distanza di Hamming 1.

Questo perché ciò che noi facciamo non è altro che la proiezione sul piano dell'n-cubo che

rappresenta tutte le configurazioni possibili della funzione in analisi. Anche per questo

motivo dobbiamo considerare la prima e ultima riga/colonna come adiacenti fra loro! A

questo punto riempiamo la matrice scrivendo in ogni casella il valore della funzione con

quella configurazione. Avremo così una bella matrice piena di 0 e di 1. Arrivati qua il primo

passo da compiere è individuare gli IMPLICANTI PRIMI e gli IMPLICANTI PRIMI

ESSENZIALI. In pratica dobbiamo raggruppare gli 1 della funzione formando dei rettangoli

che abbiano area che sia una potenza di due e la più grande possibile. Ognuno di questi

rettangoli corrisponde ad un implicante primo. Si chiamano primi perché non sono altro

che gli implicanti con area maggiore, e come tali sono quelli che richiedono il minor

numero di letterali, perciò ci piacciono di più. Tuttavia tra tutti questi implicanti primi alcuni

sono da definirsi essenziali, ovvero sono indispensabili perché coprono degli 1 che non

sono coperti da nessun altro implicante. Se un implicante copre degli 1 che sono tutti

quanti coperti da un altro implicante, allora non è essenziale, perché può essere sostituito

dagli altri. A questo punto, per ogni implicante primo scelto, scriviamo la sua forma

analitica (basta vedere quali sono le variabili che non cambiano e scriviamo il suo letterale

corrispondente). Lo so, a scrivere non si capisce un cazzo: è più facile a farsi che a dirsi.

Ricordati che lo scopo di tutto questo è avere il minor numero possibile di implicanti: solo

gli essenziali e quelli PARZIALMENTE RIDONDANTI.

Si capisce facilmente che il metodo di Karnaugh funziona con funzioni fino a quattro

variabili, inizia a diventare ostico con 5 o 6 variabili e diventa inutilizzabile oltre le sei.

Tuttavia è ancora utile per quelle funzioni in cui ci sono le condizioni di indifferenza, ovvero

configurazioni in cui non ci interessa se l'uscita è 1 o 0. Karnaugh permette di sfruttare

queste condizioni a nostro vantaggio! Semplicemente, nella matrice, indichi le condizioni di

indifferenza con un trattino. Poi, su una seconda matrice, tratti tutte queste condizioni

come se fossero degli 1, ma “facoltativi”, ovvero non hai il vincolo di doverli coprire. Lo

scopo è utilizzarli per permettere l'espansione massima degli implicanti. Se le condizioni di

indifferenza permettono l'espansione degli implicanti, allora li consideriamo come degli 1

(perché di fatto riducono il numero di letterali), se invece non danno alcun contributo li

consideriamo come 0.

Nella lezione scorsa abbiamo visto come sintetizzare una rete logica attraverso il metodo

di Karnaugh. Abbiamo visto che è bello e semplice, ma ha dei difetti importanti: è

praticamente inutilizzabile oltre le 5-6 variabili e non è un metodo che si può automatizzare

con un algoritmo. Tuttavia riesce a gestire facilmente le condizioni di indifferenza.

Il nostro prof come al solito si perde sempre nelle sue digressioni che però sono molto utili.

Del tipo per quale motivo usiamo i sistemi sincroni? Nei circuiti il clock spesso non è

neanche uno solo: ce ne sono tanti, operano a frequenze diverse ed è presente su ogni

componente del chip. Non potremmo farne a meno? Beh ha risposto in un mondo molto

semplice: se progetti in modo asincrono o sei un guru o sei un coglione :) Sostanzialmente

è complicatissimo operare in asincrono: il funzionamento di un circuito digitale che

conosciamo è quello che avviene A REGIME, senza considerare i transitori tra uno stato e

l'altro. Se operassimo in asincrono dovremmo sapere cosa succede nei transitori ed è una

mazzata sui piedi, perché i transitori si trattano con equazioni differenziali assurde e

soprattutto inutili ai fini dello scopo del circuito. Invece con il clock non ci interessa nulla

cosa accade nei transitori, perché gli effetti del circuito si vedono solo a regime, quando

tutte le transizioni sono completate.

Ma la lezione del giorno è sul METODO DI McCLUSKEY, un metodo di sintesi alternativo

che si può automatizzare e funziona anche con tante variabili (nell'ordine dell