KNOW INTUIT, Лекция, Примерен метод

Метод на Quine-McCluskey

Основното неудобство на метода на Куайн е, че при търсене на прости импликанти е необходимо да се правят сравнения по двойки първо на всички съставки на единицата, а след това на продуктите, получени в резултат на слепването.

За да опрости тази процедура, McCluskey предложи алгоритъм, чиято същност е следната:

концепцията за цифров еквивалент се въвежда за всяко произведение съгласно следното правило: цифров еквивалент се присвоява на определено произведение с помощта на числата 0 и 1 и - (тире). Променливата, включена в продукта в пряка форма, се присвоява единица ( 1 ), в обратна - нула ( 0 ), липсата на променлива се обозначава с тире;
във всеки продукт променливите са подредени само в един ред, а именно във възходящ ред;
на залепване подлежат само тези произведения, при които тиретата са разположени съответно, броят на нулите (или единиците) се различава с единица и съответно са разположени по същия начин.

Продуктът x1x2 x 4 за функция, зависеща от пет променливи, трябва да бъде свързан със следния цифров набор: x1x2 x 4: 11-0-

Ето графично представяне на процеса на намиране на основни импликанти за функцията, представена в следния SDNF:

Нека запишем функционалния израз като дизюнкция на цифрови еквиваленти:

При графичния метод за намиране на прости импликанти всички цифрови набори първо се разделят на групи и тези групи се подреждат в следния ред: първо идва група от цифрови еквиваленти, съдържащи само нули (може да има един такъв набор), след това следва група с набори, съдържащи по една единица, след това две и т.н. Чрез сравняване на набори от съседни групи се установявавъзможността за залепване, прави се необходимата маркировка и се изписва резултатът от залепването. Процесът продължава, докато е възможно залепването. Всички неслепени набори, както и крайните резултати от слепването, дават прости импликанти. Декодирането на получените цифрови еквиваленти е очевидно.

За нашия пример изглежда така:

Цифрови еквиваленти Съставни части на единицата Знаци при залепване Резултат от залепването Знаци за залепване

1000	*	10-0	-
0101	*
1010	*	-101	-
1101	*

Така че простите следствия са:

10-0 и -101, т.е.

Метод на импликантната матрица

За намиране на минималната форма на функция се използва методът на импликантните матрици. Същността на метода е следната: съставя се импликантна матрица, чиито колони се наричат съставни части на единицата, а редовете се наричат прости импликанти. След това намираме минималното покритие на всички съставни части на единството с най-простите импликанти. В същото време се търси такъв минимален набор от прости импликанти, които съвместно покриват всички съставни части на единицата на оригиналната функция. Фактът на покритие се отбелязва в клетката на матрицата със символа * (звездичка), в случай че импликантът покрива съответната съставна част (е нейна собствена част). От всички прости импликанти първо се избират само тези, които покриват само съставните части на единството (има само един покривен символ в колоната на матрицата), след което се извършва изброяването.

Прости импликанти Съставни единициА Б В Г Д Е

r	*	*	*
стр	*	*	*
р	*	*
м	*
н	*	*

От матрицата се вижда, че минималната форма на функцията задължително ще включва импликантите n (покрива конституента F), импликантата r (покрива конституента D). Същото важи и за импликанта p . Що се отнася до останалото, трябва да изберете минималния набор.

Тези. тази функция има две еднакво минимални форми.

Забележка: важно обстоятелство, което усложнява минимизирането на функциите, е наличието на изброяване на различни опции при търсене на оптимално покритие.