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 » 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