Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Bruno Fadini » 7.Minimizzazione - Parte I - Modulo 2


Corso di Reti logiche

Minimizzazione – Parte I

Argomenti

  • Costo matematico e minimizzazione
  • Il processo di minimizzazione
  • Ricerca dei PI
  • Ricerca dei nucleo

Costo matematico e minimizzazione

  • Vantaggi di una forma “ridotta”
    • Maggiore compattezza dal punto di vista dell’algebra della logica
    • Realizzazione più economica dal punto di vista delle reti
  • Come valutare il COSTO di una funzione?
    • Costo di letterali, di porte, di ingressi
    • Costo di superficie occupata nel chip
  • L’obiettivo è la minimizzazione del costo
    • Minimizzazione matematica ≈ minimizzazione effettiva
  • IL PROCESSO CHE STUDIEREMO, nato all’epoca di altre tecnologie, È TUTTORA VALIDO COME PRIMO APROCCIO AL PROBLEMA

Costo matematico e minimizzazione

  • Non esiste un procedimento matematico per la determinazione della forma minima assoluta
  • Nella pratica si è interessati a determinare una forma elementare minima cioè una forma minima fra tutte quelle possibili a 2 livelli di tipo P (o dualmente di tipo S).
  • … o comunque la forma elementare mima è un buon punto di partenza per una minimizzazione effettiva
  • ed in teoria esistono metodi per minimizzare fra le forme elementari; porremo pertanto come segue il problema.
  • TROVARE LA FORMA ELEMENTARE MINIMA DI UNA FUNZIONE

Costo matematico e minimizzazione

Si può dimostrare che:

  • Una funzione può essere espressa come somma di soli suoi primi implicanti (in forma PI)
  • Una forma elementare che minimizzi i valori dei costi CL e CI è una forma PI
  • Fra le forme minime a 2 livelli che minimizzano CP ne esiste almeno una PI

Una forma minima (o una delle forme minime) si può sempre trovare fra le forme PI

  • Forma minima => PI
  • PI ≠> Forma minima

Il processo di minimizzazione

Minimizzazione ed implicanti

  • Minimizzazione: selezionare un numero minimo di PI in grado di “coprire” la funzione
  • Un PI “copre” i mintermini da cui è implicato
  • PI essenziale: è l’unico a “coprire” un mintermine della funzione.
  • Nucleo (N) di y: somma dei primi implicanti essenziali
  • Forma minima di y: y=N+R (con N o R eventualmente vuoti)
Nucleo (N) di y

Nucleo (N) di y


Il processo di minimizzazione

Le fasi per la minimizzazione

y=N+R

  • Ricerca di tutti i PI
    • ogni forma minima è una forma PI
  • Ricerca dei PI essenziali (formano N)
  • Copertura: ricerca dello (eventuale) R

Ricerca dei PI (Fase 1)

Metodo di Quine-Mc Cluskey (Quine)

  • Metodo del consenso ripetuto. aX+aX=X
  1. Per funzioni di n variabili si parte da k=n
  2. Si cercano i consensi fra le clausole d’ordine k, che sono clausole d’ordine k-1
  3. Se si è generato almeno un consenso con k, si pone k=k-1 e si prosegue dal punto 2
  4. Sono PI tutti gli implicanti che non hanno generato consenso

NELLA VERSIONE ORIGINALE (Quine) IL METODO PROCEDE ALGEBRICAMENTE

Ricerca dei PI (Fase 1)

Metodo di Quine-McCluskey (McCluskey)

AFFINA E SISTEMATIZZA I CONFRONTI CHE IDENTIFICANO I CONSENSI

  • Piuttosto che algebricamente, una clausola è indicata attraverso una stringa di “1″ (letterale affermato),”0″ (letterale negato) e “-” (letterale mancante)
  • Le clausole vengono raggruppate in classi contenenti ciascuna un egual numero di “1″ e ordinate per numero di “1″ della classe.
  • Il consenso può essere generato solo tra clausole appartenenti a classi contigue

I CONFRONTI AVVENGONO SOLO FRA CLAUSOLE DI CLASSI CONTIGUE, CON IL “-” IN POSIZIONE OMOLOGA

Ricerca dei PI (Fase 1)

Metodo grafico (Karnaugh)

  • I primi implicanti sono i sottocubi di “area massima”
    • si ricavano dall’ispezione visiva degli “1″ della funzione
Mappa di Karnaugh

Mappa di Karnaugh


Ricerca del nucleo (Fase 2)

Ricerca su “matrice di copertura”

  • y=N+R; N=Σ Ei; PI essenziale= unico a coprire un 1
  • Matrice di copertura:
    • Sulle righe i PI, sulle colonne i mintermini
    • Un “1″ all’incrocio se il PI “copre il mintermine (il mintermine implica il PI)
  • Un PI essenziale è associato ad una colonna con un solo “1″
  • Con la ricerca di tutti i PI essenziali si trova il nucleo

Ricerca del nucleo (Fase 2)

Ricerca su mappa di Karnaugh (in figura)

  • Con ispezione visiva si individuano gli “1″ coperti da un unico PI
  • Questi PI sono essenziali
Ricerca su mappa di Karnaugh

Ricerca su mappa di Karnaugh


Prossima lezione

Minimizzazione – Parte II – Modulo 2

I materiali di supporto della lezione

B. Fadini, A. Esposito, Teoria e Progetto delle Reti Logiche, Napoli Liguori Ed., II ed, 1994. Cap. II

U. De Carlini, B. Fadini, Macchine per l'elaborazione delle informazioni, Napoli Liguori Ed., II ed., 1995 (Capitoli III e VII)

B. Fadini, N. Mazzocca, Reti Logiche – Complementi ed Esercizi, Napoli Liguori Ed. 1995

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion