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

Minimizzazione – Parte II

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 M_j
- a_ij=1 se M_j -> P_ii (P_ii copre M_j)

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

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

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

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

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

Dette:

la minimizzazione può procedere come segue:

La ricerca dei PI avviene su y₁ (esclusione i PI fatti di soli punti di indifferenza);
La copertura avviene dei soli mintermini di y₀

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

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

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