Appunti di reti logiche

Algebra booleana

Operazioni fondamentali

AND, OR, NOT

• AND: Z = X∙Y
• OR: Z = X + Y
• NOT: Z = X

X = 0, Z = 1

X = 1, Z = 0

Porte logiche

Diagrammi temporali

Ideali: XYX•Y

Reali: XYX•Y

ΔT_g = tempo di propagazione (gate delay)

Il ritardo può dipendere da diversi tipi di transizione degli ingressi. Per semplicità, considero il ritardo in generale della porta.

Reti

• 9-3-20

Algebra booleana

• Operatori fondamentali: AND - OR - NOT

• AND: Z = X Y oppure Z = X·Y
• Z = 1
• OR: Z = X + Y
• Z = 0
• Z = 1 se X = 1 oppure Y = 1
• NOT: Z = X
• X = 0, Z = 1

Porte logiche

Diagrammi temporali

• Ideali: Diagrammi temporali reali
• X = ritardo
• Tempo di propagazione (gate delay)

Il ritardo può dipendere dai diversi tipi di transizione degli ingressi. Per semplicità, considero il ritardo in generale della porta.

Porte a più ingressi

F = ABC

C = ABC + C + DEF

Porte universali

• NAND (NOT AND): Z = X ⋅ Y
• NOR (NOT OR): Z = X + Y
• XOR (OR esclusivo): Z = X ⊕ Y
• X ⊕ Y ⟺ X ⋅ Y + X ⋅ Y
• XNOR (NOR esclusivo): Z = X ⊙ Y
• X ⊙ Y ⟺ X ⋅ Y + X ⋅ Y

(⊙ è la somma binaria senza considerare il riporto)

Simboli delle porte

• NAND:
• NOR:
• XOR:
• XNOR:

Algebra booleana

Esistono due tipi di funzioni booleane, ad una sola uscita o multiuscita. Una funzione booleana può essere descritta tramite: espressione booleana, tabella di verità, diagramma logico.

Proprietà

1. Commutativa: X + Y = Y + X, X ⋅ Y = Y ⋅ X
2. Associativa: X + (Y + Z) = (X + Y) + Z, X ⋅ (Y ⋅ Z) = (X ⋅ Y) ⋅ Z
3. Distributiva: X ⋅ (Y + Z) = X ⋅ Y + X ⋅ Z, X + Y ⋅ Z = (X + Y) ⋅ (X + Z)

Reti

• 13-3-20

Identità

• X + 0 = X
• X + 1 = 1
• X • 1 = X
• X • 0 = 0

Teoremi

• Teorema sulla doppia negazione: X = X
• Teorema di Morgan: X + Y = X • Y
• Teorema di idempotenza: X • X = X, X + X = X
• Teorema sulla complementazione: X X = 0
• Teorema del consenso: X • Y + X • Z • Y • Z = X • Z

Forme canoniche

Esistono due tipi di forme canoniche.

1. Somma di prodotti, chiamati anche mintermini (SOP).
2. Prodotto di somme, chiamati anche maxtermini (POS).

Mintermini

Data una tabella di verità si può ricavare l'espressione logica della funzione osservando la SOP per cui la funzione vale 1. Un mintermine è un prodotto in cui tutte le variabili compaiono non solo nella forma diretta o negata. Un mintermine rappresenta una specifica combinazione, per cui assume valore 1. Dalle n variabili esistono 2ⁿ mintermini. O per tutte le altre.

Maxtermini

POS per cui la funzione vale 0. Ricavo somma di variabili. Un maxtermine vale 0 solo per una combinazione. 2ⁿ maxtermini. Un mintermine ed un maxtermine identificati dallo stesso codice sono uno complemento dell'altro.

ES: (dalle tabelle sulle slide 17) ma: ₀Y₂ = Y² = X+Y Z = XYZ = M₁

Somma di prodotti

Una funzione booleana può essere scritta in forma algebrica sommando tutti i mintermini che fanno assumere valore 1 alla funzione. La somma di mintermini può essere semplificata. La configurazione circuitale che rappresenta la SOP è nota come implementazione a due livelli.

Prodotto di somme

Moltiplico tutti i maxtermini che fanno assumere 0 alla funzione. Il prodotto può essere semplificato. È sempre chiamata implementazione a due livelli.

ES: POS

ABC Z

• 0 0 0 1
• ABC 0 0 1 1
• 0 1 0 A + BC
• 0 1 1 1
• 1 0 0 A + BC
• 1 0 1 A + BC
• 1 1 0 1
• 1 1 1 A + B + C Z = (A + B + C) (A B + C) (A B + C) = M₀, M₂, M₆ = TM (0,2,6)

Criteri di costo

Ci sono due criteri principali: uno tiene conto del numero di lettere, e uno del numero di ingressi.

1. Il costo è pari al numero di lettere nell'espressione (non t)