Petrickova metoda - Petricks method - Wikipedia

v Booleova algebra, Petrickova metoda[1] (také známý jako Petrickova funkce[2] nebo rozvětvené a vázané metoda) je technika popsaná Stanley R. Petrick (1931–2006)[3][4] v roce 1956[5][6] pro stanovení všech minimálních řešení součtu produktů od a primární implicitní graf.[7] Petrickova metoda je pro velké grafy velmi zdlouhavá, ale je snadno implementovatelná na počítači.[7] Metoda byla vylepšena o Insley B. Pyne a Edward Joseph McCluskey v roce 1962.[8][9]

Algoritmus

  1. Snižte graf primárního implikantu odstraněním základních řádků implicitního implikantu a odpovídajících sloupců.[7]
  2. Označte řádky redukovaného primárního implicitního grafu , , , , atd.[7]
  3. Vytvořte logickou funkci což je pravda, když jsou pokryty všechny sloupce. P sestává z produktu součtů, kde každý součtový člen má formu , kde každý představuje řádek pokrývající sloupec .[7]
  4. Snížit na minimální součet produktů vynásobením[pozn. 1] a použití absorpční zákon .[7]
  5. Každý výraz ve výsledku představuje řešení, tj. Sadu řádků, která pokrývá všechny mintermy v tabulce. Chcete-li určit minimální řešení, nejprve najděte termíny, které obsahují minimální počet hlavních implikantů.[7]
  6. Dále pro každý z výrazů nalezených v kroku pět spočítejte počet literálů v každém prime implicantu a najděte celkový počet literálů.[7]
  7. Vyberte výraz nebo výrazy složené z minimálního celkového počtu literálů a napište příslušné součty hlavních implikantů.[7]

Příklad Petrickovy metody

Následuje funkce, kterou chceme omezit:[10]

Hlavní implicitní graf z Algoritmus Quine-McCluskey je následující:

012567⇒ABC
K = m (0,1)✓✓⇒00—
L = m (0,2)✓✓⇒0—0
M = m (1,5)✓✓⇒—01
N = m (2,6)✓✓⇒—10
P = m (5,7)✓✓⇒1—1
Q = m (6,7)✓✓⇒11—

Na základě značek ✓ v tabulce výše vytvořte součin součtů řádků, kde je přidán každý řádek, a sloupce jsou vynásobeny společně:

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

Použijte zákon o distribuci a proměňte tento výraz na součet produktů. Ke zjednodušení konečného výrazu použijte také následující ekvivalence: X + XY = X a XX = X a 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

Nyní použijte následující ekvivalenci k dalšímu zmenšení rovnice: X + XY = X

 = KNP + KLPQ + LMNP + LMQ + KMNQ

Vyberte produkty s nejmenším počtem výrazů, v tomto příkladu existují dva produkty se třemi výrazy:

 KNP LMQ

Vyberte termín nebo termíny s nejmenším celkovým počtem literálů. V našem příkladu se oba produkty rozšiřují na celkem šest literálů:

KNP expanduje na a'b '+ bc' + acLMQ expanduje na a'c '+ b'c + ab

Lze tedy použít kterýkoli z nich. Obecně platí, že použití Petrickovy metody je pro velké grafy zdlouhavé, ale je snadné ji implementovat na počítači.[7]

Poznámky

  1. ^ To způsobí exponenciální vyhodnocení počtu sloupců.

Reference

  1. ^ Lind, Larry Frederick; Nelson, John Christopher Cunliffe (01.04.1977). „2.3.6. Výběr požadovaných hlavních implikantů“. Analýza a návrh sekvenčních digitálních systémů. Elektrické a elektronické inženýrství (1. vyd.). Londýn a Basingstoke, Velká Británie: Macmillan Press Ltd. 19, 77. doi:10.1007/978-1-349-15757-0. ISBN  0-333-19266-4. Archivováno od původního dne 2020-04-30. Citováno 2020-04-30. (4 + viii + 146 + 6 stránek)
  2. ^ Svoboda, Antonín; White, Donnamaie E. (2016) [2012, 1985, 01. 08. 1979]. "9.9. Petrickovo funkční řešení pro minimální ΣΠ tvar y" (PDF). Pokročilé techniky návrhu logických obvodů (PDF) (přepsané elektronické vydání). Garland STPM Press (původní vydání) / WhitePubs Enterprises, Inc. (nové vydání). str. 148–150. ISBN  978-0-8240-7014-4. LCCN  78-31384. Archivováno (PDF) od originálu na 2017-04-14. Citováno 2017-04-15. [1] [2]
  3. ^ „Životopisná poznámka“. Archivováno od originálu dne 2017-04-13. Citováno 2017-04-12. Stanley R. Petrick se narodil v roce Cedar Rapids, Iowa dne 16. srpna 1931. Navštěvoval Rooseveltova střední škola a získal titul B. S. z matematiky na Iowská státní univerzita v roce 1953. V letech 1953 až 1955 se zúčastnil MIT v aktivní službě jako důstojník letectva a titul M. M. získal na katedře elektrotechniky v roce 1955. Byl zvolen do Sigma Xi v roce 1955.
    Pan Petrick byl spojován s Radou pro aplikovanou matematiku v Laboratoři datových věd na Air Force Cambridge Research Laboratories od roku 1955 a jeho nedávná studia na MIT částečně podporovala AFCRL. V letech 1959–1962 působil jako lektor matematiky ve večerní maturitě v Liberci Severovýchodní univerzita.
    Pan Petrick je v současné době členem Linguistic Society of America, Lingvistický kruh v New Yorku, Americká matematická asociace, Sdružení pro výpočetní techniku a Sdružení pro strojový překlad a výpočetní lingvistiku.
  4. ^ „Nekrology - Cedar Rapids - Stanley R. Petrick“. Noviny. 2006-08-05. str. 16. Archivováno od originálu dne 2017-04-13. Citováno 2017-04-12. […] CEDAR RAPIDS Stanley R. Petrick, 74 let, dříve Cedar Rapids, zemřel 27. července 2006 v Presbyterian / St. Luke's Hospital, Denver, Colo., Po 13letém boji s leukémií. Vzpomínková bohoslužba se bude konat 14. srpna ve United Presbyterian Church v Laramie ve státě Wyo., Kde žil mnoho let. […] Stan Petrick se narodil v Cedar Rapids 6. srpna 1931 Catherine Hunt Petrick a Fred Petrick. Vystudoval Rooseveltovu střední školu v roce 1949 a získal titul BS titul z matematiky z Iowská státní univerzita. Stan si vzal Mary Ethel Buxton v roce 1953.
    Vstoupil do amerického letectva a byl přidělen jako studentský důstojník studující digitální výpočty na MIT, kde získal titul M.S. stupeň. Poté byl přidělen do oboru aplikované matematiky v Air Force Cambridge Research Laboratory a zatímco tam získal titul Ph.D. v lingvistice.
    Strávil 20 let ve skupině teoretické a výpočetní lingvistiky na katedře matematických věd IBM je T. J. Watson Research Center, provádějící výzkum v teorii formálního jazyka. Působil jako asistent ředitele odboru matematických věd, předseda Zvláštní zájmové skupiny pro symbolickou a algebraickou manipulaci Sdružení pro výpočetní techniku a prezident Sdružení pro výpočetní lingvistiku. Byl autorem mnoha technických publikací.
    Učil tři roky v Severovýchodní univerzita a 13 let na Pratt Institute. Dr. Petrick se připojil k University of Wyoming v roce 1987, kde se podílel na vývoji a implementaci Ph.D. programu v katedře a sloužil jako poradce diplomové práce pro mnoho postgraduálních studentů. V roce 1995 odešel do důchodu. […]     (Pozn. Zahrnuje fotografii Stanley R. Petricka.)
  5. ^ Petrick, Stanley R. (10.06.1956). Přímé stanovení nepodstatných forem booleovské funkce ze souboru hlavních implicitů. Bedford, Cambridge, Massachusetts, USA: Air Force Cambridge Research Center. Technická zpráva AFCRC TR-56-110.
  6. ^ Lewin, Douglas (1974) [1968]. Logický design přepínacích funkcí (1981, dotisk vydání 2. vydání). Thomas Nelson and Sons Ltd. / Van Nostrand Reinhold Co., Ltd. str. 60. ISBN  0-442-30747-0. ISBN  0-17-771044-6. NCN 420-5805-4.
  7. ^ A b C d E F G h i j Roth, Jr., Charles H. (1992). Základy logického designu (4. vyd.). ISBN  0-31492218-0.
  8. ^ Pyne, Insley B .; McCluskey Jr., Edward Joseph (1962). "Snížení redundance při řešení hlavních implicitních tabulek". HNĚV. Transakce na elektronických počítačích. EC-11 (4): 473–482.
  9. ^ Choudhury, Arun K. (únor 1968). „I. B. Pyne a E. J. McCluskey Jr., Snížení nadbytečnosti při řešení hlavních implicitních tabulek. Transakce IRE na elektronických počítačích, svazek EC-11 (1962), str. 473–482“. The Journal of Symbolic Logic. Recenze. Sdružení pro symbolickou logiku (ASL). 32 (4): 540–541. doi:10.2307/2270229. JSTOR  2270229.
  10. ^ Frenzel, James „Jim“ F. (2007). „Přednáška č. 10: Petrickova metoda“. ECE 349 - Základní studie základů digitálních počítačů. Moskva, Idaho, USA: Ústav elektrotechniky a výpočetní techniky, University of Idaho. Archivováno z původního dne 2017-04-12. Citováno 2019-08-08. [3]

Další čtení

externí odkazy