Reti logiche

Sintesi Combinatoria

Algebra Booleana Sistema Algebrico definito dalla quintupla (B, +, *, 0, 1), dove:

-B e l'insieme dove vengono definite le operazioni

-, * sono le operazioni di OR e AND

-0,1 sono elementi speciali di B: 0 elem. neutro di +, 1 elem. neutro di *

Nell'algebra Booleana le variabili possono assumere solo i valori 0 e 1.

Si considera inoltre un'operaz. a un elemento detta complementazione o negazione (NOT)

q q'

0 1

1 0

Algebra di Commutazione

Algebra Booleana a due valori, una funz. di commutazione a m variabili e una funz. del tipo: f:{0,1}^m->{0,1}

Una funz. di commutazione puo essere rappresentata tramite una tabella di verita

-Letterale: coppia formata da variabile e valore.

Il letterale x e l'associazione (x,1): x e vera se il valore in ingresso di x e 1.

Il letterale !x e l'associazione (x,0): x e vera se il val. in ingresso di x e 0.

In modo equivalente dato q £(0,1) un letterale e espresso come x^q, dove x¹=x e x⁰=x'

-Termine Prodotto: prodotto logico o congiunzione (AND) di piu letterali

Minterm: termine prodotto dove compaiono tutte le variabili della funz., tale per cui la configuraz. dei val. delle variabili genera un val. 1 della funzione stessa.

Implicante: termine prodotto dove compaiono alcune variabili della punt. tale per cui corrisponde a 1.

- Termine Somma: Somma logica/disgiunzione (OR) di piu letterali.

Maxtermine: Termine somma in cui compaiono i letterali di tutte le variabili della funz., tale per cui nella funz. corrisponde a 1.

Implicato: Termine somma in cui compaiono solo alcuni letterali delle variabili della funz., tale per cui nella funz. corrisponde a 1.

Proprieta:

• Elemento neutro: a+0 = a    a*1 = a
• Idempotenza: a+a = a    a*a = a
• Inverso: a+a' = 1    a*a' = 0
• 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
• Assorbimento: a+(a*b) = a    a*(a+b) = a
• Leggi di De Morgan: (a+b)' = a'*b'    (a*b)' = a'+b'
• Principio di dualita: Ogni identita puo essere trasf. in un'altra identita invertendo + e *, 0 e 1.

Funz. booleana: Di m variabili puo essere rappresentata da un'espressione booleana formata da letterali, costanti ed operatori. Il numero di espressioni booleane che possono rappresentare una funz. e infinito.

Forme canoniche: Somma di Prodotti (SoP), Prodotto della Somma (PoS).

Karnaugh

Metodo per ricavare la formula minima, si ricava la forma minima usando la regola di riduzione: ₀z + ₀ z = (₀ + ₀ )z = z

con z termine prodotto di m-1 variabili. La riduzione puo' essere svolta iterativamente.

La formula di riduzione puo' essere applicata alle espressioni booleane, il problema sta nell'identificare sia tutti i termini su cui applicare la riduzione; sia tutti i termini che parteciperanno a piu' riduzioni contempor.

E replicarli.

Metodo delle mappe di Karnaugh: Consente di risolvere direttamente i problemi indentiq: sia dovuti alla replica. di term.

E' un metodo grafico: applicazione facile per un num. di var. fino a 4.

• Complesso per 5 o 6 var.
• Inattuabile per piu' di 6 var.

• Sia legati all'identif. dei term.
• Da raggruppare.

Una mappa di Karnaugh e' uno schema deducibile dalla rappresentazione geometrica delle config. binarie.

Distanza di Hamming: numero di bit che cambia nel passare da una configurazione binaria ad un'altra.

L'applicazione delle regole di riduzione consiste nell'identificare le configurazioni binarie associate ai termini prodotto che hanno distanza di Hamming unitaria.

Una funzione di commutazione a m var. puo' essere rappresentata tramite tabella di verita', oppure in modo equivalente tramite rappresentazione cartesiana.

Tabella di verita'

Rippr. cartesiana

Nella rappr. cart. di una funz. in uno spazio a m dimensioni, collegando i vertici le cui config. sono a distanza di Hamming unitaria, si ottiene un m-cubo:

- Spazio a 1 dimensione (1 var.):

- Spazio a 2 dimensioni (2 var.):

- Spazio a 3 dimensioni (3 var.):

Metodo di rappresentazione non maneggevole, gia solo per 3 dimensioni e complicata la valutazione della funz.

Si passa allo sviluppo nel piano dei cubi; al cubo sviluppato nel piano, che ha 2^m vertici, si sovrappone una griglia (mappa) con 2^m caselle organizzate secondo righe e colonne. Una mappa cosi realizzata e detta mappa di Karnaugh:

• Le configurazioni assunte dalle variabili di ingresso danno origine agli indici di riga e colonna della mappa.
• In ogni casella si inserisce il valore della funzione considerata nella configuraz. delle coordinate.
• Due caselle adiacenti contengono configuraz. con distanza di Hamming pari a 1.

Lo sviluppo nel piano di un 3-cubo implica un taglio del cubo che deve mantenere l'adiacenza dei vertici.

CARATTERISTICHE DELLA MAPPA:

• INDICI DI RIGA E COLONNA: DUE CONFIGURAZIONI SONO ADIACENTI SE TRA LORO C'E UNA VARIAZIONE DI UN SOLO bit.
• IMPLICANTE E' UN TERMINE PRODOTTO CHE CONTIENE SOLO ALCUNI LETTERALI.

METODO:

1. INDIVIDUARE GLI IMPLICANTI PRIMI E GLI IMPLICANTI PRIMI ESSENZIALI (ESPANSIONE):
   • IMPLICANTE PRIMO: TERMINE PRODOTTO ASSOCIATO AD UN RAGGRUPPA