Квајн–Макласкијев алгоритам

Из Википедије, слободне енциклопедије

Квајн–Макласкијев алгоритам (енгл. Quine–McCluskey algorithm, метод простих импликаната) је метод који се користи за минимализацију логичких функција који су открили W.V. Quine и Edward J. McCluskey 1956. године. Овај метод је врло функционалан, баш као и карноове карте, али његова таблична форма га чини лакшим и практичнијим за програмирање, такође, даје и детерминистички пут проналажења минималне форме који управо гарантује да је добијена истинитосна функција минимална. Зову га још и таблични метод.

Метод чине два корака:

  1. Проналажење простих инпликаната функције.
  2. Користи те просте импликанте у табели простих импликаната да пронађе само битне просте импликанте функције, као и друге просте импликанте који су потребни да покрију целу функцију.

Комплексност[уреди]

Иако практичнији од карнових карти, када као улаз функција добија више од четири променњиве, Квајн–Макласкијев алгоритам има такође ограничен спектар употребе, јер проблем спада у НП-тешке проблеме: време извршавања Квајн–Макласкијевог алгоритма расте експоненцијално са порастом променљивих. Може се показати да је за функцију од n променњивих горња граница броја примарних импликаната 3n/n. За n = 32 може бити преко 6.5 * 1015 простих импликаната. Функције са великим бројем променљивих морају бити минимализоване са неоптималним хеуристичним методама, заправо алгоритам ESPRESSO је стандард.[1]

Пример[уреди]

Корак 1: проналажење простих импликаната[уреди]

Минимализоваћемо једну произвољну функцију:

f(A,B,C,D) =\sum m(4,8,10,11,12,15) + d(9,14).  \,

Израз назначује да ће излазна вредност функције f бити 1 за улазне вредности 4,8,10,11,12 и 15 (означене са 'm'). Такође, говори да нам излазна вредност уколико улазни подаци одговарају децималним бројевима 9 и 14 нису битне. ('d' означава небитне вредности).

A B C D f
m0 0 0 0 0 0
m1 0 0 0 1 0
m2 0 0 1 0 0
m3 0 0 1 1 0
m4 0 1 0 0 1
m5 0 1 0 1 0
m6 0 1 1 0 0
m7 0 1 1 1 0
m8 1 0 0 0 1
m9 1 0 0 1 x
m10 1 0 1 0 1
m11 1 0 1 1 1
m12 1 1 0 0 1
m13 1 1 0 1 0
m14 1 1 1 0 x
m15 1 1 1 1 1

Лако се може формирати израз канонског збира производа из ове табеле, управо сумирајући колоне на којима се као излазна вредност добија 1 (без небитних вредности).

f_{A,B,C,D} = A'BC'D' + AB'C'D' + AB'CD' + AB'CD + ABC'D' + ABCD,

Ова функција није минимална. Да би је оптимизовали, потребно је груписати све чланове Функције, тако да сви чланови једне групе имају исти број цифара "1" у својој бинарној представи. Небитне вредности су такође убачене у таблу тако да се могу комбиновати са члановима функције.

Број јединица Мин члан Бинарна репрезензација
1 m4 0100
m8 1000
2 m9 1001
m10 1010
m12 1100
3 m11 1011
m14 1110
4 m15 1111

У овом тренутку можемо почети са комбиновањем чланова функције са другим члановима. Уколико се два члана разликују на тачно једном месту(у бинарном облику) та цифра бива замењена цртицом '-', што имплицира да она није битна. Чланови који више не могу бити комбиноване су означене са '*'. Када се прелази са комбинација величине два, на комбинације величине четри, сматрати '-' као трећу вредност битова. Пример: -110 и -100 или -11- могу бити комбиноване, међутим, -110 и 011- не могу. (Напомена: места на којима се налазе '-' морају да се поклапају.)

Број јединица Мин члам 0-коцка величина 2 импликаната величина 4 импликаната
1 m4 0100 m(4,12) -100* m(8,9,10,11) 10--*
m8 1000 m(8,9) 100- m(8,10,12,14) 1--0*
-- -- -- m(8,10) 10-0 --
2 m9 1001 m(8,12) 1-00 m(10,11,14,15) 1-1-*
m10 1010 -- --
m12 1100 m(9,11) 10-1 --
-- -- -- m(10,11) 101- --
3 m11 1011 m(10,14) 1-10 --
m14 1110 m(12,14) 11-0 --
4 m15 1111 m(11,15) 1-11 --
m(14,15) 111-

Напомена: У овом примеру, ни један члан величине 4 се не може комбиновати у наставку. Ово имплицира да је крај првог корака алгоритма, уколико би била могућа даља комбиновања алгоритам би требало наставити (чланови величине 8 ).

Корак 2: табела простих импликаната[уреди]

Ни један од чланова не може бити даље комбинован, дакле можемо приступити проналажењу битних примарних импликаната. Редове таблице представљају импликанти који су настали, док колоне чине чланови функције. Небитне вредности нису постављене као засебне колоне - оне су сувишне за овај део алгоритма јер их не морамо имплементирати(нису обавезни као улази).

4 8 10 11 12 15 => A B C D
m(4,12)* X X -100 => - 1 0 0
m(8,9,10,11) X X X 10-- => 1 0 - -
m(8,10,12,14) X X X 1--0 => 1 - - 0
m(10,11,14,15)* X X X 1-1- => 1 - 1 -

Овде, сваки од битних простих импликаната је означен * - други прост импликант може бити покривен трећим и четвртим, и трећи прост импликант може бити покривен другим и првим, међутим то није ни битно. Ако је прост импликант од суштинског значаја, као што је и очекивано, потребно га је укључити у минималну форму. У неким случајевима, битни прости импликатори не покривају све чланове функције, у том случају додатна процедура алгоритма мора бити упошљена. Једноставна "додатна процедура" је пресуђивање и грешка, али више систематичнији начин је Патриков метод. У овом примеру, битни прости импликатори не покривају све чланове, дакле, у овом случају могу се комбиновати битни импликанти са једним од два небитна па се тако добија једно од два могућа решења:

f_{A,B,C,D} = BC'D' + AB' + AC\ .
f_{A,B,C,D} = BC'D' + AD' + AC.\ .

Оба решења су еквивалентна оргиналном , не минималном решењу:

f_{A,B,C,D} = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD.\ .

Види још[уреди]

Референце[уреди]

  1. ^ V.P. Nelson e.a., Digital Circuit Analysis and Design, Prentice Hall, 1995, pag. 234

Спољашње везе[уреди]