Petricks metod

I boolesk algebra är Petricks metod (även känd som Petrick-funktion eller branch-and-bound- metod) en teknik som beskrevs av Stanley R. Petrick (1931–2006) 1956 för att bestämma alla lägsta summa-of-product-lösningar från en primär implikant diagram . Petricks metod är väldigt tråkig för stora sjökort, men den är lätt att implementera på en dator. Metoden förbättrades av Insley B. Pyne och Edward Joseph McCluskey 1962.

Algoritm

1. Minska prime implicant-diagrammet genom att eliminera de väsentliga prime implicant-raderna och motsvarande kolumner.
2. Märk raderna i det reducerade primtal implikantdiagrammet $P_{1}$ , $P_{2}$ , $P_{3}$ , $P_{4 }$ osv.
3. Bilda en logisk funktion $P$ som är sann när alla kolumner är täckta. P består av en produkt av summor där varje summaterm har formen $(P_{i0}+P_{i1}+$$\cdots$${ \displaystyle +P_{iN})}$ , där varje $P_{ij}$ representerar en rad som täcker kolumn $i$ .
4. Tillämpa De Morgans lagar för att expandera $P$ till en summa av produkter och minimera genom att tillämpa absorptionslagen $X+XY=X$ .
5. Varje term i resultatet representerar en lösning, det vill säga en uppsättning rader som täcker alla mintermer i tabellen. För att bestämma minimilösningarna, hitta först de termer som innehåller ett minsta antal primära implikanter.
6. Därefter, för var och en av termerna i steg fem, räkna antalet literaler i varje prime implikant och hitta det totala antalet literals.
7. Välj termen eller termerna som består av det minsta totala antalet bokstaver och skriv ut motsvarande summor av primära implikanter.

Exempel på Petricks metod

Följande är funktionen vi vill minska:

$f(A,B,C)=\summa m(0,1,2,5,6,7)=A'B'C'+A'B'C+A' BC'+AB'C+ABC'+ABC$

Det främsta implikantdiagrammet från Quine-McCluskey-algoritmen är som följer:

	0	1	2	5	6	7	⇒	A	B	C
K = m(0,1)							⇒	0	0	—
L = m(0,2)							⇒	0	—	0
M = m(1,5)							⇒	—	0	1
N = m(2,6)							⇒	—	1	0
P = m(5,7)							⇒	1	—	1
Q = m(6,7)							⇒	1	1	—

Baserat på ✓-märkena i tabellen ovan, bygg en produkt av summorna av raderna där varje rad läggs till och kolumner multipliceras med varandra:

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

Använd den distribuerande lagen för att omvandla det uttrycket till en summa av produkter. Använd även följande ekvivalenser för att förenkla det slutliga uttrycket: X + XY = X och XX = X och X+X=X

= (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

Använd nu igen följande ekvivalens för att ytterligare reducera ekvationen: X + XY = X

= KNP + KLPQ + LMNP + LMQ + KMNQ

Välj produkter med minst termer, i det här exemplet finns det två produkter med tre termer:

KNP LMQ

Välj term eller termer med minst antal bokstaver. I vårt exempel expanderar de två produkterna båda till totalt sex bokstaver vardera:

KNP expanderar till a'b' + bc' + ac LMQ expanderar till a'c' + b'c + ab

Så båda kan användas. I allmänhet är tillämpningen av Petricks metod tråkig för stora diagram, men den är lätt att implementera på en dator.

Vidare läsning

• Krambeck, Donald (2016-02-17). "Prime implicant simplification using Petrick's Method" . Allt om kretsar . EETech Media, LLC. Arkiverad från originalet 2017-04-12 . Hämtad 2020-04-03 .
• Petrick, Stanley R. (1965). A Recognition Procedure for Transformational Grammars (PhD-avhandling). Massachusetts Institute of Technology .
•      Bolton, Martin (1990). "4. Minimering". Skriven vid University of Bristol, Bristol, Storbritannien. I Dagless, Erik L. (red.). Digital systemdesign med programmerbar logik . Electronic Systems Engineering Series (1 upplaga). Wokingham, Storbritannien: Addison-Wesley Publishers Ltd. s. 100–101, 115. ISBN 0-201-14545-6 . LCCN 90000007 . ISBN 978-0-201-14545-8 ark:/13960/t2f83p38r . Hämtad 2021-04-17 . {{ citera bok }} : CS1 underhåll: url-status ( länk ) (xiv+379+1 sidor)

externa länkar

• Handledning om Quine-McCluskey och Petricks metod
• Petrick C++ implementering baserat på handledningen ovan