Appunti completi corso Reti Logiche

Il corso di reti logiche

Il corso di reti logiche parla della progettazione di sistemi digitali e della loro sintesi, analizzando le metodologie di progetto. Parleremo velocemente di logica combinatoria (perché la abbiamo vista tante volte) e anticiperemo la parte di logica sequenziale. La sintesi è il passaggio che va dal comportamento alla struttura della macchina: per dire, i MOSFET di una porta logica sono la struttura fisica, mentre la funzione logica è il MODELLO che il nostro circuito deve rispettare. Ecco, la sintesi unisce questi due concetti (modello astratto e implementazione).

Il nostro prof inizia facendo una digressione infinita in cui parla della Legge di Moore e del Productivity Gap... Dei primi ingegneri che disegnavano i poligoni di ogni singolo transistor mentre ora ci sono i software che modellano i circuiti con le standard cell (un po' come nella programmazione ora ci sono i compilatori e non si usa più l'Assembly). Ci dice pure che i programmatori di Assembly erano contrari all'uso dei compilatori... Poveri illusi.

Poi fa un altro discorsone sui softwaristi contro gli hardwaristi, per cui un softwarista può migliorare il suo codice quanto vuole ma arriva ad una efficienza massima insuperabile, perché dipende dall'hardware. E l'hardwarista cerca invece di alzare questo limite, soprattutto per i sistemi hard real-time, per cui l'hardware stesso deve garantire il rispetto dei limiti di tempo imposti. Ah e una cosa interessante è che ci ha detto che una porta logica non può avere più di 3 ingressi (massimo 4), altrimenti le resistenze parassite dei MOSFET modificano le tensioni in modo eccessivo e il comportamento del circuito non è più quello desiderato (ottimo esempio per contrapporre il modello alla realtà).

Algebra di Boole

Il primo argomento è ovviamente il più banale di tutti: l'algebra di Boole. Sarà anche banale ma ci sono cose interessanti da dire. Per esempio: che cos'è un'algebra? Beh il termine corretto è struttura algebrica ed è un insieme munito di una o più operazioni. E che cos'è un'operazione? È una funzione che porta da S×S a S, ovvero per ogni coppia ordinata dell'insieme porta all'insieme stesso. Per cui l'addizione è un'operazione definita in N, ma la sottrazione non è definita in N.

L'algebra booleana dà vita ad un sistema algebrico definito da una quintupla: un insieme di supporto K su cui si definiscono le operazioni, gli operatori AND e OR e due valori che sono gli elementi neutri delle due operazioni, per cui otteniamo ({0, 1} + * 0 1). L'algebra di commutazione è l'algebra a due valori. Quindi la booleana è un'algebra di commutazione, e può essere scalare (da B a B) oppure vettoriale (da B a mB, cioè più ingressi e più uscite).

L'algebra booleana è quella più utile tra le algebre di commutazione, perché dà vita al mondo digitale, che ha vinto la battaglia contro l'analogico. Quest'ultimo ormai si usa solo laddove non c'è alternativa, ma altrove si usa sempre il digitale, perché è potente, robusto e permette l'encryption. Avere solo due valori rende il singolo bit povero di informazione, ma diminuisce la probabilità di errore.

Immagina avere un'algebra a otto valori: distinguere gli otto valori logici è difficile perché basta una piccola quantità di rumore per alterare la percezione dei valori (esempio del prof con le tonalità di grigio). Si è dimostrato che la codifica ideale per trasmettere l'informazione è quella ternaria, basata su tre valori (immagina bianco, grigio, nero, sono facili da distinguere). Ma siccome è difficile da realizzare, si è scelto il sistema binario, che è quello che si avvicina di più ed è facile da realizzare (bianco o nero). Il rumore però esiste lo stesso ed è per questo che esistono codici rilevatori e correttori.

I primi segnalano la presenza di errori nella trasmissione, ma non identificano l'errore, mentre i correttori sono anche in grado di rilevare l'errore e di correggerlo. Un esempio di codice rilevatore è la duplicazione dei bit inviati: se inviamo 00 oppure 11 siamo certi che abbiamo inviato prima il bit 0 e poi il bit 1. Se invece riceviamo 01 sappiamo che c'è stato un errore, ma non possiamo dire quale. I codici correttori permettono invece di trovare l'errore e correggerlo, ma funzionano sempre sotto opportune ipotesi. Un esempio è l'uso della triplicazione del bit con l'ipotesi che un solo bit è sbagliato: in questo modo se riceviamo 001 sappiamo che c'è un errore, ma sappiamo anche che il bit che si voleva inviare è 0. E questi sono esempi banali ma potenti!

Esistono numerosi meccanismi di rilevatori e correttori di errori sia in forma di sistemi meccanici che di sistemi elettronici. Un sistema meccanico è quello usato nei CD, che sono ricoperti di una sostanza che anche in presenza di graffi riesce a riflettere correttamente il laser. Anche la televisione digitale utilizza dei codici correttivi assurdi. Eppure nonostante questo il CD troppo rovinato è da buttare via e la TV digitale a volte non si vede (va beh ma ad Orsenigo non funziona un cazzo si sa). Anche il famoso bit di parità appartiene alla famiglia di questi codici. La figata è che questi codici sono codificabili attraverso l'algebra e le sue proprietà, che rendono potente il mondo digitale.

Tabelle di verità e forme canoniche

Con l'algebra di Boole possiamo descrivere il comportamento di un circuito attraverso le tabelle di verità. Ma come tiriamo fuori l'equazione data la tabella di verità? Lo vedremo fra poco. Iniziamo però con alcune piccole definizioni per confonderci le idee: una funzione logica è funzione di variabili (che possono essere A, B, C, D...) ma la presenza di queste variabili come, per esempio, A e !A, si chiama letterale.

Altre due definizioni interessanti e importanti sono:

• Mintermine: quando nel termine prodotto compaiono tutti i letterali della funzione. Se non compaiono tutti i termini abbiamo un implicante (un termine prodotto a cui mancano degli elementi).
• Maxtermine: quando nel termine somma compaiono tutti i letterali della funzione. Se non compaiono tutti i termini abbiamo un implicato (un termine somma a cui mancano degli elementi).

Nota che nell'Algebra Booleana vale il principio di dualità, ovvero che data una proprietà, se inverti gli AND con gli OR e gli 0 con gli 1 ottieni una proprietà che è ancora valida! È così che si semplifica la memorizzazione delle pallose proprietà algebriche che purtroppo bisogna sapere a memoria perché all'esame è richiesta la semplificazione di funzioni logiche astruse.

• Elemento neutro: A * 1 = A, A + 0 = A
• Elemento nullo: A * 0 = 0, A + 1 = 1
• Idempotenza: A * A = A, A + A = A
• Inverso: A * !A = 0, A + !A = 1
• Commutativa: A * B = B * A, A + B = B + A
• Associativa: (A * B) * C = A * (B * C), (A + B) + C = A + (B + C)
• Distributiva: A * (B + C) = (A * B) + (A * C), A + (B * C) = (A + B) * (A + C)
• Assorbimento: A * (A + B) = A, A + (A * B) = A
• Assorbimento del complemento: !A * (A + !B) = !A * !B, A + (!A * B) = A + B
• Leggi di De Morgan: !(A * B) = !A + !B, !(A + B) = !A * !B

Semplificazione delle espressioni algebriche

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.

Il teorema di espansione di Shannon

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_n) vale la seguente uguaglianza:

f(x₀, x₁, x₂...x_n) = x₀ * f(1, x₁, x₂...x_n) + !x₀ * f(0, x₁, x₂...x_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...!

Riduzione dei costi e minimizzazione

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.

Mappe di Karnaugh e distanza di Hamming

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...

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.

Metodo di McCluskey

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.