На правах рекламы:
ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Авторитетность издания

ВАК - К1
RSCI, ядро РИНЦ

Добавить в закладки

Следующий номер на сайте

4
Ожидается:
09 Сентября 2024

Программа минимизации функций алгебры логики методом Мак-Класки

Статья опубликована в выпуске журнала № 2 за 1997 год.
Аннотация:
Abstract:
Авторы: Дмитриев Г.А. (kirsanich@mail.ru) - Тверской государственный технический университет (профессор), г. Тверь, Россия, доктор технических наук, Марголис Б.И. (borismargolis@yandex.ru) - Тверской государственный технический университет (зав. кафедрой), г. Тверь, Россия, доктор технических наук, Комиссарчик В.Ф. () -
Ключевое слово:
Ключевое слово:
Количество просмотров: 21809
Версия для печати

Размер шрифта:       Шрифт:

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

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

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

Таблица 1

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

N

X1

X2

 X3

 X4

 Y

 0

 0

 0

 0

 0

 0

 1

 0

 0

 0

 1

 0

 2

 0

 0

 1

 0

 0

 3

 0

 0

 1

 1

 1

 4

 0

 1

 0

 0

 1

 5

 0

 1

 0

 1

 1

 6

 0

 1

 1

 0

 0

 7

 0

 1

 1

 1

 1

 8

 1

 0

 0

 0

 0

 9

 1

 0

 0

 1

 1

 10

 1

 0

 1

 0

 0

 11

 1

 0

 1

 1

 1

 12

 1

 1

 0

 0

 1

 13

 1

 1

 0

 1

 1

 14

 1

 1

 1

 0

 0

 15

 1

 1

 1

 1

 0

Здесь Х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

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

M

 Конституэнта

 N

 1

 X2

4

2

-/-

-/-

 -/-

X3X4

X2X4

 X1X4

 X1X2

3

5

9

12

3

-/-

-/-

 X2X3X4

 X1X3X4

 X1X2X4

7

11

13

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

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

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

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

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

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

Таблица 3

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

M

 Импликанта

 NN

 

 M

 Импликанта

 NN

1

-/-

X2

X2

4-5

4-12

 

1

-/-

X2

 X2

4-5,

12-13,

4-12,

5-13

2

-/-

-/-

-/-

-/-

-/-

-/-

X3X4

X2X4

X3X4

X1X4

X2X4

X1X4

X1X2

3-7

5-7

3-11

9-11

5-13

9-13

12-13

 

2

-/-

-/-

-/-

-/-

X3X4

X2X4

X3X4

X1X4

X1X4

 
               

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

Таблица 4

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

Конституэнты

Импликанты

X3X4

X2

X2X4

X2X3X4

X1X4

X1X3X4

X1X2

X1X2X4

X2

0

1

1

0

0

0

1

1

X3X4

1

0

0

1

0

0

0

0

X2X4

0

0

1

1

0

0

0

0

X3X4

1

0

0

0

0

1

0

0

X1X4

0

0

0

0

1

1

0

0

X1X4

0

0

0

0

1

0

0

1

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

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

Таблица 5

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

Конституэнты

 Импликанты

X3X4

X2X3X4

X1X4

X1X3X4

Число

 единиц

Перекры-вающихся

X3X4

1

1

0

0

2

2

X2X4

0

1

0

0

1

1

X3X4

1

0

0

1

2

2

X1X4

0

0

1

1

2

2

X1X4

0

0

1

0

1

1

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

Таблица 6

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

Конституэнты

 Импликанты

X3X4

X2X3X4

X1X4

X1X3X4

Число

 единиц

Перекры-вающихся

X3X4

1

1

0

0

2

1

X3X4

1

0

0

1

2

2

X1X4

0

0

1

1

2

1

На этом этапе существенными оказались импликанты 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 с.


Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=1032
Версия для печати
Статья опубликована в выпуске журнала № 2 за 1997 год.

Возможно, Вас заинтересуют следующие статьи схожих тематик: