Reti logiche

Reti combinatorie

Progettare una rete combinatoria comporta una sequenza di passi: generalmente si parte da una descrizione del problema fornita in linguaggio naturale (italiano) e si vuole arrivare a un circuito composto dagli elementi digitali di base, ovvero le porte logiche. Si è visto che esiste una corrispondenza diretta tra la rappresentazione circuitale e la rappresentazione mediante una o più espressioni booleane. Per questo si può affermare che l'obiettivo della progettazione è quello di elaborare una specifica semi-formale come quella in linguaggio naturale fino a trasformarla in una descrizione formale costituita da una o più espressioni booleane. Spesso la descrizione iniziale di un problema non è completa ma richiede una parziale riscrittura mirata ad eliminare ogni ambiguità.

Formalizzazione

Ha lo scopo di tradurre la specifica in un linguaggio più adatto alla successiva manipolazione. Nel caso delle reti combinatorie si utilizzano le tabelle di verità.

Sintesi

Consiste nel passare dalla tabella di verità a una espressione algebrica per la funzione che esse rappresentano (prima forma canonica).

Ottimizzazione

Fissato un criterio di qualità, le tecniche di ottimizzazione hanno lo scopo di manipolare l'espressione di partenza risultante dalla sintesi in modo da ottenerne una che sia funzionalmente equivalente ma con caratteristiche migliori.

Mappe di Karnaugh

Il metodo delle mappe di Karnaugh permette di trasformare il problema della minimizzazione di una espressione dal piano algebrico al piano geometrico e topologico.

Espansione

La fase di espansione ha lo scopo di trasformare una espressione algebrica in modo da costruire termini prodotto costituiti dal minor numero possibile di letterali. Si basa sull'applicazione iterativa di due regole dell'algebra (P indica un termine prodotto):

• xP + x'P = (x+x') P = 1 P = P
• P + P = P

Un implicante di una funzione è un termine prodotto che coinvolge solo alcune variabili di f e tale per cui la funzione vale 1. Quando il termine prodotto coinvolge tutte le variabili è anche un mintermine. L'espansione deve essere ripetuta fino a che è possibile; in termini più precisi e formali si dice che lo scopo dell'espansione è quello di individuare tutti e soli gli implicanti primi, cioè gli implicanti con il minor numero di letterali possibile (non è più possibile sottoporlo ad espansione).

Distanza di Hamming

Il concetto di distanza di Hamming si applica a coppie di sequenze di cifre binarie di uguale lunghezza e indica il numero di cifre diverse tra le due sequenze. Grazie al concetto di distanza di Hamming ed alla rappresentazione dei prodotti mediante stringhe binarie (riporto 1 quando una variabile appare in forma naturale e 0 quando appare in forma negata) si può riassumere la regola per la semplificazione dicendo che due termini prodotto sono semplificabili se e solo la loro distanza di Hamming è uguale a 1. Le mappe di Karnaugh sono una rappresentazione di una funzione booleana studiata per mettere in evidenza le coppie di mintermini o di implicanti a distanza di Hamming unitaria.

Reti combinatorie

La rappresentazione delle funzioni mediante n-cubi ha la proprietà di evidenziare per costruzione i mintermini di una data funzione che risultano essere adiacenti. In particolare, tale rappresentazione non si limita ad evidenziare le coppie di mintermini adiacenti bensì, più in generale, tutti i raggruppamenti di mintermini semplificabili mediante espansioni successive. Una mappa di Karnaugh altro non è che una trasposizione di un n-cubo su due dimensioni, in modo da essere più facilmente maneggiabile. È importante notare che tale trasposizione, o proiezione, deve mantenere la proprietà di adiacenza che caratterizzano i vertici degli n-cubi. Le mappe di Karnaugh evidenziano mintermini semplificabili come celle adiacenti.

Condizioni di indifferenza

Le condizioni di indifferenza (don't care) sono da considerarsi delle utili risorse che, introducendo alcuni gradi di libertà nella funzione, permettono potenzialmente di pervenire a n-cubi di dimensioni maggiori ovvero a termini prodotto con un numero minore di implicanti.

Copertura

Una copertura è un sottoinsieme di tutti gli implicanti primi in grado di coprire tutti gli 1 della funzione (mintermini). In generale, fissata una funzione, e di conseguenza l'insieme di tutti i suoi implicanti primi, il problema della copertura non ammette una soluzione unica. Di particolare interesse è la copertura minima, cioè la copertura formata dal minor numero possibile di implicanti. Il problema della ricerca della copertura minima consiste nell'individuare il minor numero possibile di implicanti sufficienti a coprire tutti gli uni della funzione. Si definisce implicante essenziale un implicante che risulta essere l'unico a coprire un dato mintermine (un uno sulla mappa) mentre si definisce implicante completamente ridondante un implicante che copre mintermini già coperti da altri implicanti essenziali. La copertura di una funzione sarà costituita da tutti gli implicanti essenziali e da nessuno degli implicanti completamente ridondanti.

Quine - McCluskey

Il metodo delle mappe di Karnaugh non si presta alla sintesi di funzioni complesse ed inoltre, in alcuni casi, può risultare difficile individuare i raggruppamenti di dimensione massima (implicanti primi) e individuarne un sottoinsieme per coprire in modo efficiente la funzione data. Il metodo di Quine-McCluskey supera queste limitazioni e fornisce una soluzione generale ed efficiente al problema della sintesi di funzioni su due livelli.

Caratteristiche del metodo

In particolare, il metodo permette di:

• Sintetizzare funzioni di un numero qualsiasi di variabili
• Sintetizzare contemporaneamente più funzioni
• Ottimizzare le funzioni sia rispetto al numero di implicanti sia rispetto al numero di letterali

Espansione

La fase di espansione si basa sull'applicazione iterativa delle due regole dell'algebra:

• xP + x'P = P
• P = P + P

- On-set: insieme delle combinazioni di ingressi cui corrispondono gli 1 della funzione.

- Off-set: insieme delle combinazioni di ingressi cui corrispondono gli 0 della funzione.

- Dc-set: insieme delle condizioni di indifferenza della funzione.

Il metodo di Quine-McCluskey consiste nel confrontare ogni mintermine della lista con ogni altro, verificando... (testo incompleto)