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

Bruno Fadini » 8.Minimizzazione - Parte II - Modulo 2


Corso di Reti logiche

Minimizzazione – Parte II

Argomenti

  • Copertura minima
  • Minimizzazione di funzioni incomplete
  • Algoritmi di quasi-minimo
  • Minimizzazione in forma S
  • Forme minime NAND e NOR
  • Minimizzazione di reti a più uscite

Copertura

Riepilogo da lezione precedente

  • Le 3 fasi del processo di minimizzazione
    • Ricerca di tutti i PI
    • Ricerca del nucleo
    • Copertura
  • Matrice di Copertura (MdC)
    • Righe: implicanti PIi. Colonne: mintermini Mj
    • aij=1 se Mj -> Pii (Pii copre Mj)

Copertura (Fase 3)

Iterazione sulla matrice di copertura

  • Avendo selezionato alcune righe e coperto alcune colonne, le une e le altre possono essere eliminate dalla MdC
  • Se ne trae una nuova MdC per il prosieguo del processo
  • Così, al termine della fase 2, si eliminano le righe corrispondenti agli implicanti essenziali e tutte le colonne da questi già ricoperte
  • Si ottiene dunque la MdC all’inizio della fase 3:
    • coprire con le righe rimaste le colonne rimaste

Copertura (Fase 3)

Metodo di Petrick

  • Metodo di riferimento, operativamente adatto a piccole MdC
  • Si basa sulla logica delle proposizioni applicata alla MdC
    • ciascuna colonna può essere ricoperta in alternativa (or) da uno degli implicanti con un 1 sulla colonna
    • la copertura completa si ottiene coprendo la prima colonna e la seconda e così via (and)
  • Copertura= (A+ …)⋅(A+C …)(B+D …) = AB … + ACD + …
  • Ponendo in forma P l’espressione di copertura nata in forma S, si ottengono le possibili coperture
  • Fra queste si sceglie quella (o quelle) minima

Copertura (Fase 3)

Metodo di Righe e colonne dominanti

  • Riga (colonna) dominata da un’altra: ha 1 solo dove li ha l’altra
    • D dominata da E
    • P9 domina P1 e P8
  • Teorema:
    • Eliminando le righe dominate e le colonne dominanti da una matrice M, si ottiene una matrice M’ equivalente (che rappresenta, cioè, il medesimo problema di copertura)
  • Implicanti essenziali secondari: associati ad una riga che, in seguito alla eliminazione, è la sola a coprire una colonna

Copertura (Fase 3)

Copertura minima – Algoritmo completo

  • ricerca dei primi implicanti (PI) ed individuazione di quelli essenziali (Fasi 1 e 2);
  • inclusione nella forma minima dei PI essenziali; loro eliminazione dalla matrice, unitamente con i mintermini ricoperti;
  • eliminazione delle righe dominate e delle colonne dominanti;
  • individuazione dei PI essenziali “secondari” della matrice così ridotta;
  • ripetizione dei passi 2, 3, 4 finché è possibile.

Algoritmi di quasi-minimo

  • Per molte variabili, i tempi di esecuzione dell’algoritmo di minimo possono essere proibitivi
  • Si ricorre allora ad algoritmi di quasi-minimo (non trattati)

Minimizzazione di funzioni incomplete

Scegliere, fra tutte le funzioni compatibili (f.c.), quella di costo minimo

Dette:

  • y la funzione incompleta
  • y1 la f.c. avente tutti i don’t care uguali ad 1
  • y0 la f.c. avente tutti i don’t care uguali a 0

la minimizzazione può procedere come segue:

  • La ricerca dei PI avviene su y1 (esclusione i PI fatti di soli punti di indifferenza);
  • La copertura avviene dei soli mintermini di y0

Minimizzazione in forma S

  • Metodi algebrico e tabellare: procedimento duale
  • Metodo grafico (Mappe di Karnaugh)
    • Si pongono in evidenza gli 0 piuttosto che gli 1
    • Le clausole-somma sono individuate leggendo
    • I letterali affermati in corrispondenza degli 0 e negati in corrispondenza degli 1
  • Copertura: nulla cambia
  • La forma minima S di una funzione y è la duale della forma minima P del suo negato

Forme minime NAND e NOR a 2 livelli

Per le reti NAND e NOR si adoperano rispettivamente le forme minime P (AND-OR) ed S (OR-AND)

Minimizzazione di una rete a più uscite

  • La minimizzazione di una rete a n ingressi ed m uscite equivale a quella di m funzioni delle medesime n variabili
  • Il costo complessivo non è in generale la sommatoria dei costi minimi delle singole funzioni
  • Esistono metodi (non trattati) per la minimizzazione che sfruttano l’uso al primo livello di clausole comuni

Prossima lezione

Un tool per la minimizzazione – Esercitazione: display a 7 segmenti – 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