Синтез комбинационных схем с несколькими выходами

На практике комбинационные схемы с одним выходом встречаются относительно редко. Обычно схемы имеют несколько выходов, причем значения сигналов на этих выходах зависят от одних и тех же входных сигналов. Работа схемы, имеющей n и k входов описывается совокупностью k:

каждая, из которых определяет закон функционирования схемы по одному выходу. Если провести минимизацию логических функций, независимо друг от друга, то схема, реализующая эту систему уравнений, будет содержать k изолированных фрагмента. Но в общем случае схему можно упростить за счет объединения отдельных участков в разных фрагментах, выполняющих одинаковые функции. Например, для реализации двух логических функций:

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

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

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

Рассмотрим метод минимизации системы лог. функций методом меток.

Этот метод предусматривает выполнение следующих этапов:

- нахождение простых импликант системы лог. функций;

- определение простых импликант для минимального представления системы лог. функций;

- запись каждой лог. функции в ДНФ.

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

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

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

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

Рассмотрим пример. Пусть даны три функции, каждая из которых зависит от четырех переменных:

здесь

В виде карт Карно эта система будет выглядеть следующим образом:

Рис. 3.6. Карты Карно для системы функций

Найдем все простые импликанты для этих функций, т. е. СДНФ:

, (3.19)

Затем необходимо найти путем совмещения карт СДНФ логических произведений всех сочетаний функций: .

Рис. 3.7. Карты Карно для сочетаний логических функций

В результате получим следующие СДНФ:

. (3.20)

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

Метка – это имена функций, участвовавших в ее образовании.

Так для данного примера импликанта получит метку , получит метку , получит метку . При этом, если одна и та же импликанта присутствует в нескольких системах (3.19) и (3.20) то выбирается выражение с импликантой более высокого ранга.

В заголовке столбцов матрицы записывают все конституенты «1» системы лог. функций. Каждой конституенте приписывается метка, указывающая в какие функции входит данная конституента; для каждой метки отводится отдельная колонка.

Например, конституента «1» имеет метку , т. к. она входит в функции и , а в функцию не входит.

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

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

В таблице 3.3 колонки с номерами 1, 6, 12, 14 и 15 имеют единственный (+). Соответствующие этим (+) импликанты отмечены символом (√). Этим же символом отмечены внизуу таблицы все колонки, перекрытые выбранными импликантами.

После этого найдем импликанты, перекрывающие остальные колонки. В рассматриваемом примере такой выбор очевиден, т. к. неотмеченными остались колонки 10 и 11, которые перекрываются одной импликантой . Данная импликанта и перекрываемые ею колонки отмечены в таблице символом (*).

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