Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
12
Projektowanieukładówkombinacyjnych
MinimalizacjafunkcjimetodąQuine’a-McCluskeya
Minimalizacjęfunkcjilogicznejmożnaprzeprowadzićrównieżwielomainnymi
metodamiiJednąznajważniejszychjestmetodawywodzącaswąnazwęodnazwiskjej
twórcówWillardaViQuine’aiEdwardaJiMcCluskeyaiOpracowanyprzeznich
algorytmjestszerokostosowanywprogramachkomputerowychwspomagających
minimalizacjęi
MetodaQuine’a-McCluskeyaskładasięznastępującychkroków:
1iWypisaniewnaturalnymkodziebinarnymwszystkichsłówkodowych,dlaktórych
funkcjaprzyjmujewartość1(jedynkifunkcji)i
2iPogrupowanietychsłówwgrupyojednakowejliczbiejedynekwsłowie(tzwi
indeksie)i
3iPorównaniedlagrupoindeksieiorazi+1wszystkichparsłów,zktórychjedno
należydogrupyoindeksiei,adrugiedogrupyoindeksiei+1iJeżeliporównywane
słowaróżniąsiętylkowartościąjednegobitu,tonależyzapisaćjewnowejgrupie,
wstawiającsymbol„
─
”zamiastróżniącegosiębituiObaporównywanesłowa
oznaczasięjakoużytewpołączeniuiWtensposóbutworzonazostajenowagrupa
słów,wktórychwystępujejedensymbol„
─
”i
4iDlanowychgruppowtarzanesąproceduryporównywania,podobniejakwpunkcie3i
Dodatkowymwymaganiem,dopołączeniadwóchsłówzsąsiednichgrup,jest
występowaniesymbolu„
─
”wtymsamymmiejscuwobuporównywanychsłowachi
Wtensposóbuzyskujesiękolejnyzestawgrupzdwomasymbolami„
─
”wkażdym
słowiei
5iPostępowanieanalogiczneażdomomentu,wktórympozostanietylkojednagrupa
iwszystkiezawartewniejsłowamajątęsamąliczbęsymboli„
─
”lubniema
żadnychmożliwościdalszegołączeniasłówi
6iWypisaniewszystkichsłów,któreniezostałyużytewpołączeniachiWtensposób
uzyskujesięlistęimplikantówfunkcji,któremogąwejśćdojejpostaciminimalneji
7iUtworzeniedwuwymiarowejtablicy,którejwierszesąopisanezapomocą
wybranychwprocesiesklejaniaimplikantów,zaśkolumny-wszystkimisłowami,
dlaktórychfunkcjaprzyjmujewartość1(tablicaQuine’a)i
8iDlakażdegowierszatablicyQuine’azaznaczenietychkolumn,wktórychznajdują
sięjedynkifunkcjipokrywaneprzezimplikantzdanegowierszai
9iWybórminimalnegozbioruimplikantówpokrywającegowszystkiejedynkifunkcji
zapomocąmetodeliminacjiiTakizbiórtworzypostaćminimalnąfunkcjii
1
