Файл: Дроздов Е.А. Многопрограммные цифровые вычислительные машины.pdf

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

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

Х^Х2Х3 \/ х ^х2 х 3

лишней двоичной переменной оказывается хи так как значение истинности формулы зависит от значений истинности только Хг и *з. Действительно,

jcxjcajc3 V х гх 2 х 3 — х 2х 3 (jq V *1) = х 2х 3 • 1 = х 2 х 3.

Рассмотренный пример показывает, что при минимизации целе­ сообразно выявлять соседние конъюнкции, которые «склеиваются», образуя эквивалентную конъюнкцию пониженного ранга.

Действия, отвечающие методу непосредственных преобразова­ ний, обычно проводятся в следующем порядке:

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

2.Упрощение исходной логической формулы путем применения

квыявленным группам соответствующих законов и операций.

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

4.Упрощение преобразованной промежуточной логической фор­ мулы с получением предварительно минимальной формы в виде некоторой д. н. ф.

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

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

87

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

Например, в формуле

Л Л V Х 2Х 3 V X 1*S,

не упрощаемой более путем применения основных законов алгебры логики, если не считать возможных действий по выносу за скобку, член Х\Х3 является лишним и его можно опустить. Действительно, £1*3= 1, если Х\ =1 и *з=1; тогда остальные два члена формулы

принимают вид 1 'Х2 \ / х 2‘ 1, что эквивалентно единице; таким об­ разом, истинность исходной формулы не зависит от члена *1*3:

Х хХ2 V х 2Х й V X lX3 — Х \Х2 V Х2Х 3-

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

В ряде случаев минимизации оказывается целесообразным вво­

либо являющиеся лишними. Введение лишних членов осуществляет­ ся согласно следующему правилу: если дизъюнктивная нормальная форма функции F(xь х2, • ■ хп) содержит конъюнкции QP=XiQPi

и QT=XiQr1, то функция F{(хь хъ ..., х„) =F(x ,, х2, . ■ хп) VQpiQm

Синтез логической схемы заключается в ее построении по задан­ ным условиям работы соответствующего узла машины. Эти усло­ вия определяют количество входов и выходов узла, а также закон соответствия наборов входных и выходных сигналов. Для этого проводятся определенные действия, связанные с использованием основных положений алгебры логики:

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

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

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

88

4. Построение логической схемы по минимизированным логиче­ ским функциям.

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

Этап минимизации логических функций имеет особенности так­ же тогда, когда производится синтез схем с несколькими выхода­ ми. Такие схемы называют (п, £)-полюсниками, считая п количе­ ством входов, a k — количеством выходов. Для получения наиболее простой схемы (п, £)-полюсника при минимизации и преобразова­ нии описывающих его функций необходимо стремиться к тому, чтобы в выражениях функций по одним выходам максимально ис­ пользовались выражения функций (или их частей) по другим вы­ ходам.

В качестве примера рассмотрим случай синтеза логической схе­ мы (4, 2)-полюсника, таблица работы которого представлена ниже (табл. 3.3). Поскольку таблица работы логического многополюсни­ ка уже задана, то синтез его схемы начинаем со второго этапа, т. е. этапа получения аналитических выражений для функций выходов Ei и У2При синтезе схемы считаем, что заданный набор состав­ ляют элементы И, ИЛИ и НЕ.

89

Из табл. 3.3 функции У\ и У2 выводятся в виде следующих со­ вершенных дизъюнктивных нормальных форм:

Y 4 = Х4Х2Х3Х4 \ / X4X2X3X4 \ f X 4X2X3X4 \ / X 4X2X3X4 \ f

Произведем минимизацию этих логических функций методом непосредственных преобразований. Склеивание соседних конъюнк­ ций функции У] и применение операции выноса за скобки приво­ дят к следующим последовательным преобразованиям этой функции:

Уг = х {х 2х й (х, V х 4) V AiA3a4(х2 V х2) V хадхад V

V X xX 2X s (Х 4\ / Х 4) V X[X3X4 (x2 V A2) V XjX2X3X4 =

= XjX^Xj V X jX 3X 4 V A!X2X3X4 V Ayx2x3 V X 4X 3X4 V a 4x 2x 3x 4 = = X 4X 3 (x2 V A 4) V A2X4 (X jX3 V Ayx3) V A 4X 3 (x2 V X4) =

= (X 2 V A 4) ( x {X s V A ]X 3) V a 2x 4 (x , x 3 V A 4X 3) =

В минимизированном выражении для У1 в скобках содержатся функции неравнозначности и равнозначности переменных Х\ и х3. Для упрощения реализации функции У; ее целесообразно предста­ вить так:

УГ" = x^xi [ а д (X! V х 3)] Vа2х4 [ а д (Xj V х 3)].

Минимизация функции У2 приводит к следующим преобразо­ ваниям:

мента (НЕ и И), так как отрицание х2х4 формируется при реализа­ ции У""".

Собственно построение логической схемы заключается в после­ довательной замене элементарных логических операций реализуе­

90