Software & Systems

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

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

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

Таблица 1

Пример цифровой таблицы истинности

Здесь Х1, X2, X3, X4 – входные сигналы; Y– выходной сигнал; N– номер комбинации. Единицы в таблице соответствуют прямым значениям логических переменных, а нули – инверсным. Тогда исходная логическая функция в СНДФ (совершенно нормальной дизъюнктивной форме) описывается выражением:

Y=X3X4+X2+X2X4+ X2X3X4+X1X4+X1X3X4+ X1X2+X1X2X4 .                                           (1)

Введем некоторые определения [2]. Конституэнтой называется логическое произведение, в которое входят все входные переменные. Импликанта – логическое произведение, в которое входят не все входные переменные. Поглощение – логическое суммирование одинаковых конституэнт или импликант. Склеивание – логическое суммирование конституэнт или импликант, отличающихся инверсностью одной переменной.

В методе Мак-Класки основными правилами упрощения логической фунции являются законы склеивания

 X1X2 + X1 = X1                                         (2)

и поглощения

X1 + X1 = X1                                                     (3)

Все конституэнты, соответствующие наличию сигнала на выходе (Y = 1), разбиваются на группы по числу переменных, имеющих прямое значение.

Таблица 2

Разбиение конституэнт на группы

Номер группы М соответствует числу прямых переменных в конституэнте; N – номер конституэнты.

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

1) конституэнты находятся в соседних группах;

2) разница номеров конституэнт равна степени двойки;

3) большему номеру склеиваемой конституэнты соответствует больший номер группы.

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

Таблица 3

Склеивание конституэнт

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

Таблица 4

Исходная импликантная матрица

Матрица заполняется нулями и единицами, удостоверяющими вхождение (1) или невхождение (0) той или иной импликанты в ту или иную конституэнту. Если в каком-либо из столбцов таблицы имеется только одна единица, то соответствующая ей импликанта называется существенной. Существенная импликанта войдет в конечное выражение для минимизируемой функции, так как без нее не будет получено покрытие всего множества значений функции. Число единиц в строке существенной импликанты, таким образом, всегда больше числа единиц, перекрывающихся с другими импликантами. На данном этапе построения матрицы существенной будет являться импликанта X2.

Далее из матрицы можно исключить строку с существенной импликантой и покрываемые ей столбцы.

Таблица 5

Импликантная матрица на втором этапе построения

При отсутствии существенных импликант преимущество отдается импликантам с большим числом единиц, а импликанты с минимальным числом единиц исключаются из матрицы. В данном случае исключению из таблицы подлежат X2X4 и X1X4, после чего матрица строится снова.

Таблица 6

Импликантная матрица на последнем этапе

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

Ymin = X2+X3X4+X1X4.       (4)

При машинной реализации программа содержит следующие процедуры.

1. Процедура перевода десятичного числа в двоичный код.

Так как номер конституэнты соответствует ее представлению в двоичном коде,то после перевода номеров содержащихся в логической функции конституэнт в двоичный код и записи в строковом виде получается следующий массив конституэнт con: ('0011', '0100', '0101', '0111', '1001', '1011', '1100', '1101').

2. Процедура разбиения конституэнт на группы.

Все имееющиеся конституэнты разбиваются на группы по числу прямых переменных и сортируются в порядке возрастания номера группы. Выходом процедуры является отсортированный массив impl:('0100', 0011', '0101', 1001', '1100', '0111', '1011', '1101') и массив номеров групп groupe: (1,2,2,2,2,3,3,3).

3. Процедура склеивания конституэнт в соседних группах.

В результате последовательного склеивания получаем массив impl_new: ('010#', '#100', '0#11', '01#1', '#011', '10#1', '#101', '1#01', '110#') на первом этапе и ('#10#', '0#11', '01#1', '#011', '10#1', '1#01') на втором этапе склеивания, где диезом (#) обозначается отсутствующий разряд.

4. Процедура построения импликантной матрицы.

В соответствие массиву impl_new ставятся массивы с числом единиц в строке one: (4, 2, 2, 2, 2, 2) и числом перекрывающихся единиц one_com: (2, 2, 2, 2, 2, 2). В конечный массив impl_min заносится существенная импликанта '#10#'. Далее массивы единиц переписываются в виде one: (0,2,1,2,2,1) и one_com: (0,2,1,2,2,1) и из impl_new исключаются '01#1' и '1#01'. Массивы единиц переписываются в виде one: (0,2,0,2,2,0) и one_com: (0,1,0,2,1,0). В конечный массив impl_min заносятся существенные на данном этапе импликанты '0#11' и '10#1', а из impl_new исключается импликанта '#011'. В итоге массив impl_min для минимальной формы выглядит следующим образом: ('#10#', '0#11', '10#1').

5. Процедура вывода в буквенной форме.

Наконец, массив impl_min переписывается в буквенном виде и выводится на экран в виде конечной суммы (4).

Программа написана на языке Турбо-Паскаль и отлажена на компьютерах типа IBM PC 286/386.

Список литературы

1. Поспелов Д.А. Логические методы анализа и синтеза схем.- М.: Энергия, 1974. - 368 с.

2. Телемеханика: Учебное пособие для специальности "Автоматика и телемеханика" вузов/ Под ред. к.т.н., доц. В.М.Новицкого.- М.: Высшая школа, 1967. - 424 с.