Авторитетность издания
Добавить в закладки
Следующий номер на сайте
Программа минимизации функций алгебры логики методом Мак-Класки
Аннотация:
Abstract:
Авторы: Дмитриев Г.А. (kirsanich@mail.ru) - Тверской государственный технический университет (профессор), г. Тверь, Россия, доктор технических наук, Марголис Б.И. (borismargolis@yandex.ru) - Тверской государственный технический университет (зав. кафедрой), г. Тверь, Россия, доктор технических наук, Комиссарчик В.Ф. () - | |
Ключевое слово: |
|
Ключевое слово: |
|
Количество просмотров: 21809 |
Версия для печати |
При синтезе однотактных устройств алгебры логики приходится осуществлять минимизацию логической функции, описывающей условия их работы. Минимизацией называется аналитическое или графическое преобразование первоначальной формулы, приводящее к получению структурной схемы с минимальным числом элементов [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 с. |
Постоянный адрес статьи: http://swsys.ru/index.php?page=article&id=1032 |
Версия для печати |
Статья опубликована в выпуске журнала № 2 за 1997 год. |
Возможно, Вас заинтересуют следующие статьи схожих тематик:
- О программной реализации геоинформационных систем
- Комплекс программных средств для аналитических иерархических процессов экспертного оценивания
- Искусственный интеллект в грядущем десятилетии
- Сравнительный анализ некоторых алгоритмов распознавания
- Метод интегрированного описания топологических отношений в геоинформационных системах
Назад, к списку статей