Рабочих и запрещенных наборов

Минимизация логических функций на основе поразрядного сравнения

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

Этот метод позволяет производить минимизацию СДНФ функции с любым числом переменных, однако так же, как и предыдущий метод, дает лишь одну из частных минимальных форм – ТДНФ.

Основа метода заключается в том, что логическая функция должна быть задана в символической форме в восьмеричной системе счисления, а минимизация должны производиться поразрядно. Для каждого разряда восьмеричного рабочего числа подбираются такие соседние цифры, чтобы не получить запрещенных чисел. Затем, используя трехразрядную решетку (куб) соседних чисел, следует найти для каждого разряда восьмеричного числа свой обобщенный код с максимальным числом тире. Напомним, что один разряд в восьмеричной системе счисления представляет собой 3 разряда в двоичной.

По полученным обобщенным кодам определяются члены ДНФ. Использование восьмеричной системы счисления объясняется удобством перевода чисел из двоичной системы в восьмеричную и наоборот.

Рассмотрим более подробно метод поразрядного сравнения с использованием восьмеричной системы счисления.

Суть метода состоит в последовательном нахождении простых импликант функции путем поразрядного сравнения рабочих наборов со всем множеством запрещенных наборов. Рабочие наборы, покрытые ранее найденными простыми импликантами, исключаются из рассмотрения, это позволяет сократить объем вычислений. Поиск простых импликант прекращается после определения полной их совокупности. Из полученной полной совокупности определяются одна или несколько приведенных систем простых импликант, образующих тупиковые ДНФ.

Методика нахождения простой импликанты заключается в том, что выбирается один из разрядов рассматриваемого рабочего числа (в восьмеричной системе счисления), для выбранного разряда путем сравнения остальных разрядов рабочего числа с соответствующими разрядами запрещенных чисел определяются его запрещенные значения, т.е. такие, которые при подстановке в рабочий набор вместо рассматриваемого разряда образуют один из запрещенных наборов. Зная истинное значение восьмеричного числа (набора) и его запрещенное значение, нетрудно определить совокупность значений этого разряда, который при поочередной подстановке их вместо рассматриваемого образуют группу соседних склеиваемых наборов, отличающихся друг от друга значениями только рассматриваемого разряда.

Решение этой задачи фактически сводится к минимизации логической функции трех переменных с помощью 3-разрядной решетки (куба) соседних чисел и обобщенных кодов.

Пусть для некоторой функции от шести переменных задано рабочее число (восьмеричное) 56 и запрещенное восьмеричное число 26:

Напомним, что каждое рабочее число соответствует члену СДНФ. Восьмеричная система позволяет очень легко переходить к СДНФ. Каждый разряд восьмеричного числа – это 3 разряда двоичного числа. В данном примере 6 переменных

Определим возможные соседние числа для старшего разряда числа 56, т.е. для 5. В каждом разряде можно добавлять условные числа, но так, чтобы не получить запрещенного. Запрещенным является число 26, тогда очевидно, что цифру 5 в старшем разряде можно дополнять любыми цифрами из 0, 1, 2, 3, 4, 5, 6, 7 (полный куб), кроме 2. Надо найти в запрещенных числах те, которые совпадают с рабочим числом в младшем разряде, и цифру их старшего разряда (у нас 2) считать запрещенной.

Результат запишем следующим образом:

Цифра 5, стоящая над чертой указывает заданное значение старшего разряда рабочего числа, а цифра 2, стоящая под чертой, – запрещенное значение этого разряда, т.е. значение старшего разряда запрещенного числа, у которого значение младшего разряда совпадает с младшим разрядом рабочего числа.

Старшему разряду 5 рабочего числа 56 соответствует триада значений переменных x ₆, x ₅, x ₄, поэтому задача сводится к минимизации функции трех переменных

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

Запишем:

Эта запись означает, что функцию, заданную одним рабочим числом 56, мы доопределили до четырех рабочих чисел: 16, 36, 56, 76.

Теперь нужно аналогичным образом минимизировать младший разряд рабочего числа. Надо найти соседние цифры для младшего разряда 6, такие, чтобы при старшем разряде не получить запрещенного числа 26. Так как 2 в старшем разряде нет, очевидно, этими цифрами могут быть любые от 0 до 7, а значит, запрещенных чисел для 6 нет. Запишем это следующим образом:

где

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

Заметим, что в результате минимизации мы доопределяли разряды рабочего числа (старший до четырех, младший до восьми значений), и, значит, импликанта x ₄ покрывает всего 32 числа (набора), из которых одно (56) является заданным рабочим, а остальные 31 – условными. Поэтому в общем случае после рассмотрения одного из рабочих чисел следует исключить из дальнейшего рассмотрения те рабочие числа, которые покрываются уже полученной импликантой.

Минимизация методом поразрядного сравнения не однозначна, возможны различные варианты решений.

Для получения всех решений надо рассмотреть все возможные варианты объединения по кубу соседних чисел и из полученных решений (простых импликант) выбрать минимальное.

Для данного примера это записывается следующим образом:

Видим, что поставленной задаче удовлетворяют три решения, т.е. рабочее число 56 (при запрещенном 26) покрывается каждой из трех простых импликант В данном случае все они состоят из одной буквы, поэтому выбор любой из них безразличен. В общем же случае при рассмотрении всех вариантов выбирают то решение (импликанту), которое имеет наименьшее количество букв, т.е. ОК с большим числом тире.

Методика минимизации СДНФ с помощью поразрядного сравнения наборов следующая:

1. Получить функцию в символической форме в восьмеричной системе счисления.

2. Взять любое рабочее число и для одного из его разрядов определить запрещенные числа.

3. Пользуясь кубом соседних чисел, определить для рассматриваемого разряда соседние числа, образующие обобщенный код с максимальным числом тире.

4. Найти поочередно для каждого из остальных разрядов рабочего восьмеричного числа запрещенные и соседние числа, образующие обобщенные коды с максимальным числом тире.

Заметим, что при выполнении пп.3 и 4 могут возникнуть различные варианты объединения соседних чисел в фигуры. Обычно в инженерной практике берут один из вариантов, приводящий к образованию обобщенного кода с максимальным числом тире. В общем же случае следует рассматривать все возможные варианты.

5. Логические суммы чисел каждого из разрядов заменить обобщенными кодами и, зная базу, определить член ДНФ.

Совершенно очевидно, что описанная выше процедура приводит к определению простой импликанты, покрывающей рассматриваемое рабочее число, т.е. полученный член ДНФ есть простая импликанта.

Так как при определении простой импликанты (члена ДНФ) для одного рабочего числа к нему добавлялись поразрядно условные числа, то полученной простой импликантой могут покрываться еще и другие рабочие числа, надобность в рассмотрении которых теперь отпадает.

6. Исключить из рассмотрения те восьмеричные рабочие числа, которые реализуются полученным членом ДНФ (покрываются полученной простой импликантой).

7. Для оставшихся восьмеричных рабочих чисел выполнить операции согласно пп.2-6. Указанная процедура производится до тех пор, пока все рабочие числа минимизируемой логической функции не будут покрыты найденными простыми импликантами. В результате получаем совокупность простых импликант (членов ДНФ), дизъюнкция которых принимается за одну из частных минимальных форм.

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

В общем же случае, особенно при производстве минимизации с помощью ЦВМ, полученная полная система простых импликант может содержать избыточные члены, т.е. не быть приведенной. Поэтому необходимо для нахождения тупиковых ДНФ составить частичную импликантную таблицу (таблицу покрытия). Эта таблица является частичной, так как нет уверенности, что получены все простые импликанты.

8. Все полученные простые импликанты записать в частичную импликантную таблицу (таблицу покрытий), по которой определить одну или несколько тупиковых ДНФ логической функции, из которых выбрать минимальную.

Отметим еще раз, что метод поразрядного сравнения позволяет минимизировать СДНФ с любым числом переменных.

Рассмотрим примеры.

Пример 3.12 Минимизировать логическую функцию, заданную в символической форме:

Рассмотрим рабочее число 37:

Проверим, какие рабочие числа покрывают этот член ДНФ (простая импликанта). Из выражения при поразрядном умножении видно, что покрываются рабочие числа 37 и 31. Осталось число 22. Рассмотрим его:

Итак,

Решим тот же пример, но начнем минимизацию с младшего разряда:

Так как в запрещенных числах в старшем разряде цифры 3 нет нигде, то для 7 в младшем разряде запрещенных нет, или Для старшего разряда в этом случае запрещенные 0 и 1, поскольку при них получаются 00, 10, 16. Получили x ₅. Очевидно, полученный член ДНФ x ₅ покрывает все рабочие числа 37, 22, 31.

Итак, y = x ₅.

Видим, что данный вариант дает самую минимальную форму.

Таким образом, конечный результат часто зависит и от порядка рассмотрения разрядов при минимизации.

Пример 3.13 Минимизировать логическую функцию:

Начнем рассмотрение с рабочего числа 73, с его младшего разряда:

Покрыты рабочие числа 73, 52, 56.

Рассмотрим число 66:

Покрыты числа 66, 67.

Осталось непокрытым рабочее число 43. Рассмотрим его:

Импликанта x ₆ x ₁ покрывает рабочие числа 43, 67, 73. Импликанта x ₆ x ₂ покрывает все рабочие числа, так как у нее старший разряд состоит из цифр старших разрядов всех рабочих чисел, а младший разряд – из цифр младших разрядов всех рабочих чисел.

Итак получили две тупиковые формы:

Очевидно, что .

Таким образом, надо брать тот вариант объединения, где встречается больше нужных цифр.

Так если число 73 начать со старшего разряда, то получим:

.

Покрыты все рабочие числа. Значит .

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

Таким образом, пользователь всегда выбирает наилучший вариант рассмотрения и объединения разрядов рабочих чисел.

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

Так для примера 3.13, получили 4 импликанты: x ₆ x ₄, x ₆ x ₅, x ₆ x ₁, x ₆ x ₂.

Строим частичную импликантную таблицу для получения системы простых импликант (таблица 3.5):

Получили две ТДНФ: и

	Таблица 3.5
	Импликанты	Рабочие числа	Обозначение
	x 6 x 4	+			+	+		A
	x 6 x 5	+	+				+	B
	x 6 x 1	+		+			+	C
	x 6 x 2	+	+	+	+	+	+	D

Очевидно, что минимальной ДНФ является

Заметим, что при ручной работе проектировщик еще до построения таблицы импликант увидит, что простая импликанта x ₆ x ₂ покрывает все рабочие числа, а все остальные импликанты отбросит. Однако при расчете на ЦВМ машина рассматривает все рабочие числа последовательно, причем отбрасывания уже покрытых чисел не делается. Полученный ответ содержит большую избыточность. Построение таблицы импликант (покрытий) в этих случаях является обязательным.