Минимизация систем ПФ

Комбинационные схемы многих цифровых устройств являются многовыходными, поэтому аналитическое описание таких схем представляет собой совокупность переключательных функций, каждая из которых описывает один из выходов КС. Таким образом, m-выходная КС может быть задана системой m ПФ, где – выходные сигналы:

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

Рассмотрим систему ПФ, каждая функция которой задана в СДНФ:

Минимизация каждой функции по отдельности дает следующую систему ПФ:

Для технической реализации такой системы ПФ в базисе И-ИЛИ-НЕ потребуются (без учета инверторов) два четырехвходовых элемента «И», два трехвходовых элемента «И», один двухвходовый элемент «И» и два элемента «ИЛИ», один из которых двухвходовый, а второй – трехвхо­довый.

Для наглядности изобразим исходную систему ПФ в виде карт Карно (табл. 4.22, 4.23) и выполним склеивания в соответствии с выделенными в этих картах совокупностями единиц.

Тогда минимальная система ПФ запишется следующим образом:

Таблица 4.22 Таблица 4.23

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

Решение задачи минимизации систем ПФ рассмотрим на основе модифицированного метода Квайна [4]. Будем полагать, что функции системы заданы в виде ДНФ.

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

На первом шаге минимизации необходимо сформировать полное множество элементарных произведений минимизируемой системы. При этом необходимо использовать представление всех ПФ в СДНФ. Каждому элементу множества А следует присвоить индекс, содержащий номера функций системы, в которые входит это элементарное произведение. Пусть элементы сформированного множества А образуют СДНФ булевой функции g.

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

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

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

Пусть подлежащая минимизации система ПФ задана имеет вид

Сформируем полное множество элементарных конъюнкций, каждому элементу множества присвоим индекс, соответствующий номеру функции, содержащей это произведение.

Из элементов множества А составим СДНФ функции g:

Выполним склеивания по формуле

.

Результаты склеивания будем записывать в отдельных строках.

Осуществив поглощения, получим

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

Импликантная матрица Квайна представлена в табл. 4.24.

Таблица 4.24

Консти­туенты 1 функции g	Простые импликанты
			+
	+				+
			+		+
		+
	+			+
		+	+
	+
			+
		+
		+
				+
						+
	+
					+
					+		+
						+	+

После обработки импликантной матрицы можно записать:

.

Запишем минимальную систему ПФ, включая в ДНФ i-й функции простые импликанты, в индексе которых содержится i:

На рис. 4.2 изображен пример практической реализации КС, описываемой полученной минимальной системой ПФ.

4.8. Минимизация ПФ
в универсальных базисах И-НЕ, ИЛИ-НЕ

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

Базисы Пирса и Шеффера связаны с каноническим базисом формулами де Моргана, которые в общем виде записываются следующим образом:

Минимизация логических функций в базисах И-НЕ, ИЛИ-НЕ требует разработки специальных правил преобразования для выполнения склеиваний и поглощений. Гораздо более простым подходом является применение хорошо разработанных методов минимизации ПФ для канонического базиса И-ИЛИ-НЕ (например, метод Квайна, метод Блейка – Порецкого) с последующим переходом к базису Пирса или Шеффера. Строго говоря, при таком способе минимизации в общем случае получаются не минимальные, а близкие к минимальным формы представления ПФ.

Пусть подлежащая минимизации ПФ задана в СДНФ или СКНФ. Рассмотрим универсальный метод перехода к базисам И-НЕ, ИЛИ-НЕ.

Введем следующие обозначения. Каждую конституенту 1, входящую в СДНФ логической функции, представим в виде элементарной конъюнкции , а каждую конституенту 0, входящую в СКНФ, – в виде элементарной дизъюнкции :

Тогда СДНФ и СКНФ в общем виде можно записать как

Воспользовавшись законом де Моргана, получим

В приведенных выражениях инверсии и могут быть выражены через операции «стрелка Пирса» и «штрих Шеффера»:

откуда

Таким образом, для перехода от произвольной ДНФ к базису И-НЕ (штрих Шеффера) необходимо в исходном выражении: поставить знак инверсии над всем выражением, заменить все знаки дизъюнкции на знаки конъюнкции, над каждым дизъюнктивным членом, входившим в ДНФ, поставить знак инверсии (заменить все знаки дизъюнкции и конъюнкции на знак операции «штрих Шеффера»).

Для перехода от произвольной КНФ к базису ИЛИ-НЕ (стрелка Пирса) необходимо в исходном выражении: поставить знак инверсии над всем выражением, заменить все знаки конъюнкции на знаки дизъюнкции, над каждым конъюнктивным членом, входившим в КНФ, поставить знак инверсии (заменить все знаки дизъюнкции и конъюнкции на знак операции «стрелка Пирса»).

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

Осуществим переход от КНФ к базису ИЛИ-НЕ (стрелка Пирса).

Осуществим переход от ДНФ к базису И-НЕ (штрих Шеффера).

При таком переходе могут возникать ситуации, когда в записи ПФ, кроме операций И-НЕ (ИЛИ-НЕ), присутствуют операции инверсии НЕ. Инверторы могут быть представлены в универсальных базисах в соответствии с формулами

т.е. в качестве инвертора выступает элемент И-НЕ (ИЛИ-НЕ), все входы которого объединены в один.

При синтезе КС в универсальных базисах может возникнуть необходимость в переходе от представления функции в ДНФ к представлению в базисе ИЛИ-НЕ или в переходе от представления функции в КНФ к представлению в базисе И-НЕ. В такой ситуации можно пользоваться следующими формулами:

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

Для перехода к базису 2И-НЕ:

Для перехода к базису 2ИЛИ-НЕ:

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

Таблица 4.25

	x2
x1
				x3
		x4

Минимальные ДНФ и КНФ для этой функции можно записать в виде

Поскольку минимальная КНФ содержит меньшее число букв, используем ее для получения формы представления, близкой к минимальной, в базисе ИЛИ-НЕ.

Преобразуем полученную форму переключательной функции к представлению в базисе 2ИЛИ-НЕ.

.

На рис. 4.3 изображена КС, соответствующая полученной в результате минимизации ПФ, представленной в базисе 2ИЛИ-НЕ. В качестве инверторов также используются логические элементы 2ИЛИ-НЕ.

Вопросы для самоконтроля

1. Для чего необходимо выполнять процедуру минимизации ПФ и систем ПФ?

2. Дайте определение импликанты ПФ и простой импликанты ПФ.

3. Сформулируйте основную идею метода минимизации ПФ с помощью карт Карно. В чем заключаются достоинства и недостатки такого метода?

4. Сформулируйте основные этапы минимизации ПФ по методу Квайна. Для чего предназначена импликантная матрица Квайна и как она используется в процессе минимизации ПФ?

5. В чем заключаются отличия метода Квайна – Мак-Класки от базового метода Квайна?

6. Сформулируйте основные этапы минимизации ПФ по методу Блейка – Порецкого.

7. В чем заключаются особенности минимизации ПФ, заданных в конъюнктивной форме, не полностью определенных ПФ, систем ПФ и ПФ, представляемых в универсальных базисах Пирса и Шеффера?

5. Моделирование работы
и синтез автоматов с памятью