Metodo di Petrick

Da Wikipedia, l'enciclopedia libera.

Il metodo di Petrick è un algoritmo di risoluzione dei mintermini contenuti in una tabella degli implicanti primi ricavata con il metodo di Quine-McCluskey. Tale metodo, che semplifica la copertura trasponendola in forma algebrica, risulta scomodo per tabelle molto grandi, in quanto valuta tutte le possibili soluzioni, ma è facilmente implementabile in un computer tramite algoritmi di branch and bound.

Il metodo di Petrick opera seguendo questi passaggi:[1]

  1. Riduzione della tabella degli implicanti primi eliminando le righe contenenti implicanti primi essenziali (e le rispettive colonne);
  2. Etichettatura delle righe della tabella ridotta (P_1, P_2, P_3, P_4, ecc.);
  3. Costruzione di una funzione logica P tale che sia vera quando tutte le colonne sono coperte (P è costituita da un prodotto di somme, dove ogni termine di somma ha la forma (P_{i0} + P_{i1} + \cdots + P_{iN}), in cui P_{ij} rappresentano una riga che copre la colonna i);
  4. Minimizzazione di P in somma di prodotti applicando l'equivalenza X + XY = X (ciascun termine nel risultato rappresenta una soluzione, ovvero un insieme di righe che copre tutti i mintermini della tabella);
  5. Determinazione delle soluzioni minime individuando quei termini che contengono il minor numero di implicanti primi;
  6. Conteggio del numero dei letterali in ciascun implicante primo dei termini trovati precedentemente e ricerca del numero totale di letterali;
  7. Scelta dei termini formati dal minor numero totale di letterali e scrittura delle corrispondenti somme di implicanti primi.

Esempio[modifica | modifica sorgente]

Supponiamo di voler ridurre la seguente funzione:[1]

f(A,B,C) =\sum m(0,1,2,5,6,7)

Usando il metodo di Quine-McCluskey si perviene alla seguente tabella degli implicanti primi:

                | 0 1 2 5 6 7
 ---------------|------------
   K (0,1) a'b' | X X
   L (0,2) a'c' | X   X
   M (1,5) b'c  |   X   X
   N (2,6) bc'  |     X   X
   P (5,7) ac   |       X   X
   Q (6,7) ab   |         X X

In base alle coperture segnate con una X nella tabella soprastante, si ricava il seguente prodotto di somme delle righe, dove le righe vengono addizionate e le colonne moltiplicate tra loro:

(K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q)

Usando la proprietà distributiva e le equivalenze:

  • X + XY = X
  • XX = X
  • X+X=X

l'espressione precedente viene semplificata e trasformata in somma di prodotti come segue:

(K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q)

= (K+LM)(N+LQ)(P+MQ)

= (KN+KLQ+LMN+LMQ)(P+MQ)

= KNP + KLPQ + LMNP + LMPQ + KMNQ + KLMQ + LMNQ + LMQ

Applicando l'equivalenza:

X + XY = X

l'espressione viene ulteriormente ridotta, diventando:

 KNP + KLPQ + LMNP + LMPQ + KMNQ + KLMQ + LMNQ + LMQ =

= KNP + KLPQ + LMNP + LMQ + KMNQ

A questo punto scegliamo i prodotti col minor numero di termini, che in quest'esempio sono:

  • KNP
  • LMQ

Infine, scegliamo i termini col minor numero totale di letterali; pertanto, i due prodotti si espandono entrambi in 6 letterali totali:

  • KNPa'b'+ bc'+ ac
  • LMQa'c'+ b'c + ab

Note[modifica | modifica sorgente]

  1. ^ a b (EN) Jim Frenzel - ECE 349 - Background Study in Digital Computer Fundamentals - Lecture 10
matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica