85997 (Методы минимизации логических функций), страница 2

Распределенные наборы 4-го ранга
i=0	i=1	i=2	i=3	i=4
0000	0010	0011 0101 0110 1010	0111 1011	1111

Сравнивая соседние группы и распределяя полученные наборы по положению символа ‘*’ получим:

Наборы 3-го ранга
1 2 3 4 5 6 7 8 9 10 11		00*0 001* 0*10 *010 0*11 *011 01*1 011* *111 101* 1*11
Распределенные наборы 3-го ранга
1	2		3	4
*010 *011 *111	0*10 0*11 1*11		00*0 01*1	001* 011* 101*

Распределенные наборы 2-го ранга
12	14	24
**11	*01*	0*1*

Примечание. Во всех выше приведенных таблицах простые импликанты отмечены жирным шрифтом с подчеркиванием.

Анализируя, видим, что СДНФ примет следующий вид:

Простые импликанты
1 2 3 4 5	0*1* *01* **11 00*0 01*1

Или в алгебраической форме:

F(X₁X₂X₃X₄) = X₁X₃ V X₂X₃ V X₃X₄ V X₁X₂X₄ V X₁X₂X₄.

1. Метод карт Карно.

Метод карт Карно – это один из графических методов минимизации функции. Эти методы основаны на использовании особенности зрительного восприятия, так как с его помощью можно практически мгновенно распознать те или иные простые конфигурации.

Преимуществами метода карт Карно над другими методами являются:

А) простота отыскания склеивающихся компонент;

Б) простота выполнения самого склеивания;

В) нахождение всех минимальных форм функции.

Построим таблицу метода карт Карно.

	X1X2	X1X2	X1X2	X1X2
X3X4	■
X3X4		■
X3X4	■	■	■	■
X3X4	■	■		■

Теперь накроем совокупность всех квадратов с метками минимальным количеством правильных прямоугольников. Таких прямоугольников в нашем случае будет 5: три четырехклеточных и два двухклеточных. Этим прямоугольникам соответствуют следующие простые импликанты:

для первого – X₃X₄;

для второго – X₁X₃;

для третьего – X₂X₃;

для четвертого – X₁X₂X₄;

для пятого – X₁X₂X₄;

Минимальная ДНФ будет выглядеть так:

F(X₁X₂X₃X₄) = X₁X₃ V X₂X₃ V X₃X₄ V X₁X₂X₄ V X₁X₂X₄.

Сравнивая метод карт Карно с другими методами минимизации функции можно сделать вывод, что первый больше всего подходит для ручного исполнения. Время ручной работы значительно сокращается (за счет наглядного представления склеивающихся импликант). Программная реализация данного метода имеет свои сложности. Так, очень сложно будет реализовать оптимальный выбор правильных прямоугольников, особенно для большого числа аргументов.

1.3.5 Метод неопределенных коэффициентов

Этот метод может быть использован для любого числа аргументов. Но так как этот метод достаточно громоздок, то применяется только в тех случаях, когда число аргументов не более 5-6.

В методе неопределенных коэффициентов используются законы универсального и нулевого множеств и законы повторения. В начале все коэффициенты неопределенны (отсюда и название метода).

Построим матрицу неопределенных коэффициентов для четырех аргументов. В этом случае мы будем иметь систему из 16-ти уравнений.

Система приведена на следующей странице.

Приравняем все коэффициенты 0 в тех строках, которым соответствует 0 в векторе столбце. Затем приравняем 0 соответствующие коэффициенты в других строках. После этих преобразований система примет следующий вид:

V = 1

V V V V V V = 1

V V V V V V = 1

V = 1

V V V = 1

V V V V V V = 1

V V V = 1

V V V V V = 1

V V V = 1

Теперь в каждой строке необходимо выбрать коэффициент минимального ранга и приравнять его единице, а остальные коэффициенты – 0. После этого вычеркиваем одинаковые строки, оставляя при этом одну из них (те строки, у которых все коэффициенты равны 0, также вычеркиваются).

= 1

= 1

= 1

= 1

= 1

Запишем теперь конъюнкции, соответствующие коэффициентам, равным единицам. Мы получим минимальную ДНФ.

F(X₁X₂X₃X₄) = X₁X₃ V X₂X₃ V X₃X₄ V X₁X₂X₄ V X₁X₂X₄.

Итак, мы получили несколькими способами минимальную ДНФ, Во всех случаях она получилась одинаковой, то есть любой из описанных методов может быть использован для минимизации функции. Однако эти методы существенно отличаются друг от друга как по принципу нахождения МДНФ, так и по времени исполнения. Для ручных расчетов очень удобен метод карт Карно. Он нагляден, не требует рутинных операций, а выбрать оптимальное расположение правильных прямоугольников не составляет большого труда. В то время как машинная реализация данного метода осложняется необходимостью нахождения оптимального расположения прямоугольников. Естественно применение других методов (метод Квайна, метод Квайна-Маккласки, метод неопределенных коэффициентов) для ручных расчетов нецелесообразно. Они больше подойдут для машинной реализации, так как содержат большое число повторяющихся простых операций.

Задание 2.

2.1 Схема алгоритма для метода Квайна

1. Начало.

2. Ввести матрицу ДСНФ исходной функции.

3. Проверить на склеиваемость i-ю (i=1,m-1: где m – количество строк в ДСНФ) и j-ую (j=i+1, m) строки. Если строки склеиваются, то перейти к пункту 6, в противном случае перейти к пункту 5.

4. Формировать массив простых импликант, предварительно пометив символом ‘*’ ту переменную, по которой данные строки склеиваются.

5. Перейти к пункту 2.

6. Строку, которая не склеилась ни с одной другой строкой записать в конечный массив.

7. Перейти к пункту 2.

8. Вывод полученной матрицы.

9. Конец.

Логическая схема алгоритма в нотации Ляпунова

_{1 1}

V_HV₁Z₁V₂V₃V₄V_K

V_H – начало.

V₁ – ввести матрицу ДСНФ исходной функции.

V₂ – формировать массив простых импликант, предварительно пометив символом ‘*’ ту переменную, по которой данные строки склеиваются.

V₃ – строку, которая не склеилась ни с одной другой строкой записать в конечный массив.

V₄ – вывод полученной матрицы.

Z₁ – если строки склеиваются, то перейти к пункту 3, в противном случае перейти к пункту 5.

V_K – конец.

Граф-схема алгоритма.

V₁

V₂

V₃

V₄

0

Описание машинных процедур

Procedure Stuck(S1, S2: Diz; IndexS1, IndexS2 : byte);

Данная процедура склеивает два, передаваемых ей дизъюнкта. Дизъюнкты задаются в параметрах S1, S2. Индексы IndexS1, IndexS2 определяют индексы этих дизъюнктов в главном рабочем массиве . Алгоритм работы процедуры следующий: сначала ищется количество склеивающихся символов. Если их 0, то они одинаковые, и в конечный массив записывается только один из них. Если 1, то определяется местоположение символа, по которому данные две дизъюнкции склеиваются, и заменяем этот символ на ‘*’. Все полученные результаты заносятся в массив REZ.

Все остальные функции и процедуры программы связаны с действиями над массивами, то есть не имеют непосредственного отношения к данному методу нахождения МДНФ. Поэтому нет смысла их описывать.

2.2 Схема алгоритма для метода Петрика

1. Начало.

2. Ввести матрицу ДСНФ исходной функции и простые импликанты, полученные в методе Квайна.

3. Составить таблицу меток.

4. По таблице меток построить конъюнкцию дизъюнкций, каждая из которых есть совокупность тех импликант, которые в данном столбце имеют метки.

5. Произвести раскрытие скобок в полученном выражении с учетом законов поглощения.

6. Выбрать одну из полученных конъюнкций и представить ее как совокупность соответсвующих простых импликант.

7. Если выбранная комбинация не является минимальной, то перейти к пункту 6, в противном случае перейти к пункту 8.

8. Формировать МДНФ.

9. Вывод полученной матрицы.

10. Конец.

Логическая схема алгоритма в нотации Ляпунова.